Codejam Qualification Round 2014

โค้ดแจมปีนี้โจทย์ชักจะยากขึ้นเรื่อยๆ ครับ (ผมยังติดใจความง่ายของ 2011 อยู่เลยเนี่ย)

ปีนี้ผมดันทำ A เสร็จแล้วไปลุย C เลย ปรากฏว่าไม่ผ่านแล้วหมดแรงอยู่ตรงนั้น กว่าจะกลับมาทำ B ก็ห้าทุ่ม -_-’ (ผมเองรู้สึกว่าผม burnout มาสักพักแล้ว ไม่ได้โค้ดแบบจริงจังมาสักสามสี่วันได้ หลังจากจัดเกมงูไปยาวๆ)

โค้ดปีนี้ครับ (Gist มันแยกไฟล์ไม่ได้ ผมลืมไปว่าต้องโพสต์แยกกัน)

A

ข้อ A ใช้วิธีง่ายๆ ครับคือหา intersect มา แล้วดูว่ามีกี่ตัว ถ้ามีตัวเดียวก็ตอบตัวนั้นเลย

B

ข้อ B ผมเสียเวลาบั๊กไปหลายพักเพราะคำนวณ timeToTargetIfFarm ผิด ลืมคิดเวลาเก็บเงินซื้อฟาร์มไป (และมีคิดติดลบด้วย) พอแก้เติม max(0, cookie-farm) ไปให้ถูก และ timeToTargetIfFarm += timeToNextFarm ก็เรียบร้อย ผ่านไปถึง B-large เลย

C

ข้อ C ผมใช้วิธีถมดำแล้วถมขาวจากซ้ายบนเอา โดยคิดเอาว่าต้องถมกี่แถวแล้วลองถมดู เช็คคำตอบด้วยการจิ้มซ้ายบนสุดแล้วหาว่ามีจุดที่ไม่ได้เปิดมั้ย ถ้าไม่มีก็ตอบ แต่ผิด ไม่รู้ผิดอะไรเหมือนกัน :/

D

ข้อ D โจทย์ยาวมากครับ และมันไม่ได้ให้วิธีคิดมาด้วย ผมเองไม่ถนัดโจทย์แนวๆ optimization/game theory เลยเลยข้ามไปเลยแล้วกัน

จริงๆ ข้อ B ถ้าเป็นปีก่อนๆ ผมคงจะข้ามไปด้วย แต่ปีนีั้เห็นหลายคนทำแล้วเลยว่าจะทำมั่ง และ grader ผมเองเคยออกโจทย์แนวๆ นี้เหมือนกัน (แต่เป็น int หมด) เลยเอาวิธีคิดเดียวกับข้อที่ตัวเองออกมาใช้

Cross compile แพคเกจ Arch Linux ลง Raspberry Pi (ArchLinuxARM)

ได้ Pi มาเล่นสักพักแล้วครับ แล้วทำงานที่คิดว่าต่อไปจะมีหลายๆ เครื่องใช้ ก็เลยว่าจะทำแพคเกจให้เรียบร้อยดีกว่า ทีนี้จะคอมไพล์อะไรใน Pi มันก็แสนนาน เอามาทำในคอมดีกว่า ก็ใช้วิธีดังนี้ครับ

สิ่งที่ต้องการ

Host OS ต้องเป็น Arch Linux เหมือนกัน

วิธี

  1. โหลด compiler ของ pi มาก่อนที่ https://github.com/raspberrypi/tools ผมเอาไว้ที่ /home/whs/pi/tools
  2. เขียน makepkg.conf เอง ซึ่งเป็นไฟล์กำหนดค่าของคำสั่ง makepkg ที่ใช้ทำแพคเกจ โดยก๊อปมาจาก /etc/makepkg.conf
CARCH="armv6h"
CHOST="arm-bcm2708hardfp-linux-gnueabi"
CC="/home/whs/pi/tools/arm-bcm2708/arm-bcm2708hardfp-linux-gnueabi/bin/arm-bcm2708hardfp-linux-gnueabi-gcc"
CXX="/home/whs/pi/tools/arm-bcm2708/arm-bcm2708hardfp-linux-gnueabi/bin/arm-bcm2708hardfp-linux-gnueabi-g++"
strip() {
    /home/whs/pi/tools/arm-bcm2708/arm-bcm2708hardfp-linux-gnueabi/bin/arm-bcm2708hardfp-linux-gnueabi-strip $*
}
CPPFLAGS="-D_FORTIFY_SOURCE=2"
CFLAGS="-mfpu=vfp -mfloat-abi=hard -march=armv6zk -mtune=arm1176jzf-s -O2 -pipe -fstack-protector --param=ssp-buffer-size=4"
CXXFLAGS="-mfpu=vfp -mfloat-abi=hard -march=armv6zk -mtune=arm1176jzf-s -O2 -pipe -fstack-protector --param=ssp-buffer-size=4"
LDFLAGS="-Wl,-O1,--sort-common,--as-needed,-z,relro"
MAKEFLAGS="-j5"

ใส่ในหัวข้อ ARCHITECTURE, COMPILE FLAGS นะครับ ไม่ใช่ทั้งไฟล์ และอย่าลืมแก้พาธต่างๆ (ผมเขียนตัวใหม่ไว้แล้วที่ทำเป็นตัวแปร แต่อยู่อีกเครื่อง ไว้มาแก้อีกที)

สำหรับ MAKEFLAGS นั้นใส่ -j ตามจำนวนคอร์ เช่นผมมี 4 ก็ใส่ -j5 (4+1) หรือเลขอื่นๆ ตามสะดวก เป็นจำนวนเธรดการคอมไพล์

ในนี้สังเกตว่าผมทำฟังก์ชั่น strip เอง เพราะ makepkg มัน hardcode strip ให้ใช้ของ host ซึ่ง strip binary ของ arm ไม่ได้

  1. พวกตัวแปรที่เซตไว้ในนี้ต้องส่งไปให้คำสั่ง make อีกทีนึงด้วย ฉะนั้นใน PKGBUILD ก็ต้องใส่คำสั่ง
for i in CC CXX CFLAGS CXXFLAGS CARCH CHOST
do
  export $i
done

ไว้ก่อนคำสั่ง make เพื่อให้ make ใช้ CC ของ target สำหรับ npm ใช้ export npm_config_arch=$CARCH อีกบรรทัดหนึ่ง (น่าจะมีผลเฉพาะการลงแพคเกจที่มี binary file)

อันนี้ใช้ได้สำหรับแอพที่ไม่ได้ link กับ library อื่นๆ นะครับ ถ้า link กับ library อื่นจะยุ่งยากกว่านี้ ผมยังทดลองวิธีต่างๆ อยู่ แต่คร่าวๆ คือจำเป็นจะต้องเอาการ์ด pi มาเสียบไว้ที่เครื่องเวลาคอมไพล์ หรือก๊อปไฟล์ข้างในลงเครื่อง เพราะจำเป็นจะต้องมีไฟล์ .so ของไลบรารีไว้ในการ link

Install package ใน ArchLinuxARM SD Card

ถ้ามีความจำเป็นจะต้องติดตั้งแพคเกจใน ArchLinuxARM โดยไม่ต้องการบูท Pi สามารถใช้ pacman ของเครื่องแม่ลงแพคเกจไปได้โดยไม่ต้อง chroot ครับ (แน่นอนว่า chroot ไม่ได้ด้วยเพราะคนละสถาปัตยกรรม)

  1. copy pacman.conf ใน pi ออกมา (ผมพยายามหาวิธีที่ไม่ต้องทำแล้วแต่ไม่เวิร์ค)
  2. แก้ไข pacman.conf แก้ RootDir และอื่นๆ ที่ตามมาระบุ mount point ของ pi นำหน้าด้วย (เช่น RootDir = /run/media/whs/pi/)
  3. ข้างล่างเกือบสุดที่มี Include เยอะๆ ใส่ mount point เช่นเดียวกัน (จุดนี้คือทำไมต้องก๊อป pacman.conf ออกมา ตัว rootdir จริงๆ ระบุผ่าน command line argument ได้)

เสร็จแล้วใช้ pacman --config=pacman.conf เพื่อติดตั้งแพคเกจได้เลยครับ เช่น pacman --config=pacman.conf -Sy เพื่ออัพเดตแพคเกจ

ข้อควรระวัง แพคเกจหลายตัวมี post install script ที่จะรันไม่ได้หรืออาจทำระบบแม่พังได้ ฉะนั้นไม่จำเป็นจริงๆ ไม่ควรใช้วิธีนี้

-qv