Code Jam 2016 รอบคัดเลือก
วนมาอีกปีกับ Google Code Jam ครับ เหมือนเดิมคือตั้งใจจะทำโจทย์ตั้งแต่ตอน 6 โมงเช้า … แล้วก็เผลอหลับไปอีกแล้วแม้ว่าจะถ่างตารอมาได้ถึงตี 5 ก็ตาม 555
โชคดีหน่อยปีนี้ค่อนข้างว่าง ตื่นมาแล้วลุยโจทย์ได้เต็มที่ มีแค่แวะออกไปกินข้าวที่ MK ตอนเย็นๆ เท่านั้นเอง
พอมีเวลาคิดเหลือเฟือ ปีนี้เลยได้ปลดล็อก achievement ด้วยการใช้ภาษา Brainfuck (และภาษาอื่นๆ อีกมากมาย) ในการแข่งขันซักที
Counting Sheep
ข้อแรกไม่ยากเท่าไหร่ครับ แค่ตัดเลขโดดเมื่อเขียนแสดงในฐาน 10 ออกมาแล้วจำไว้ว่าเคยเห็นเลขโดดตัวไหนแล้วบ้าง กำหนดให้ $n,m,k\in\mathbb{N}$ เมื่อโจทย์ให้ค่า $n$ มา ถ้าเลือก $k, 10^k \ge n$ มาค่าหนึ่งแล้วหา $ m = \left\lceil \frac{10^{k+1}}{n} \right\rceil $ จะได้ว่าผลลัพธ์ของ $ nm $ มีเลขโดดแรกเป็น $1$ เห็นได้ชัดแล้วว่าสำหรับ $n$ ใดๆ พหุคูณของ $nm$ สามารถสร้างเลขโดดได้ทุกคำตอบแน่นอน ยกเว้นกรณีเดียวคือ $n=0$ เพราะจะทำให้ไม่สามารถคำนวณหาค่า $m$ ได้ (หารศูนย์)
ตัวอย่างเมื่อ $n=1692$ เลือก $k=4$ จะได้ $m=\left\lceil \frac{10^5}{1692} \right\rceil=60$ และ $nm = 101520$ หากสนใจแค่เลขโดดตัวแรกก็จะเหมือนท่องสูตรคูณแม่ 1 ซึ่งก็คือจะสามารถเห็นเลขโดดได้ทุกตัวนั่นเอง
เมื่อรู้ขอบเขตบนและข้อจำกัดการจบการทำงานของอัลกอริทึมแล้ว ต่อไปก็โค้ดได้เลย ซึ่งก็ตรงไปตรงมาเพียงแค่วนลูปคูณ $n$ ด้วย $1,2,3,\dots$ ไปเรื่อยๆ เพราะโจทย์ถามหาผลลัพธ์ที่ใกล้ที่สุดเท่านั้น
require 'set'
gets.to_i.times do |test|
ans = 'INSOMNIA'
unless (num = gets.to_i).zero?
ans = 0
rem = (0..9).to_set
until rem.size.zero? do
ans += num
rem -= ans.to_s.split('').map(&:to_i)
end
end
puts "Case ##{test+1}: #{ans}"
end
Revenge of the Pancakes
ส่วนข้อสองนี่ถือว่าง่ายและสนุกมาก เทคนิดคือให้มองแพนเค้กหลายๆ ชิ้นที่หันด้านเดียวกันเป็นชุดเดียว แล้วเติมแพนเค้กที่หันด้านที่ถูกต้องไว้ที่ท้ายสุด เรียบร้อยก็นับว่ามีแพนเค้กที่หันด้านต่างกันทั้งหมดกี่ชุด เท่านั้นเอง
โอเค อัลกอริทึมง่าย อ่านข้อมูลนำเข้าง่าย ก็เลยได้ฤกษ์เปิดซิงใช้ Brainfuck ทำข้อนี้ซะเลย
[-]>[-]+[[-]>[-],[+[-----------[>[-]++++++[<------>-]
<--<<[->>++++++++++<<]>>[-<<+>>]<+>]]]<]<
[>+>>>[-]>,>>[-]+
[<,----------
<<<[-]<[-]>>>>[<<<+<+>>>>-]<<<[>>>+<<<-]+
<[>>>>++++++++++<<<-<[-]]
>[<++++++[>>>>+++++++<<<<-]>>>>+>[-]<<<<-]
[-]<[-]>>>[<<<+>>>-]>[<<<+<->>>>-]
<<<[>>+<<-]<[>>>>+<<<<[-]]
>>>>[<<+>>[-]]
>]
>[-]+++++[<+++++++++++++>-]<++.
>[-]+++++[<++++++>-]<.
>[-]+++++[<++++>-]<--.
>[-]+++++[<--->-]<+.
>[-]+++++[<-------------->-]<+.
+++.
[-]<<<<<[-]<[>+>>>>>+<<<<<<-]>[<+>-]>>>>>
[>>+>+<<<-]>>>[<<<+>>>-]<<+>[<->[>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]
++++++++[<++++++>-]>[<<+>>-]>[<<+>>-]<<]>]<[->>++++++++[<++++++>-]]<[.[-]<]<[-]
>[-]+++++[<++++++++++++>-]<--.
>[-]+++++[<----->-]<-.
[-]<<<[>>>+<<<-]>>>
[>>+>+<<<-]>>>[<<<+>>>-]<<+>[<->[>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]
++++++++[<++++++>-]>[<<+>>-]>[<<+>>-]<<]>]<[->>++++++++[<++++++>-]]<[.[-]<]<[-]
++++++++++.[-]
<<<<<<<-]
ซึ่งเอาจริงๆ Brainfuck ก็ไม่ได้ยากอะไรเลยนะ เพียงแค่ว่ามันไม่มีชื่อตัวแปรให้ใช้ดีๆ ต้องมองว่าตัวแปรทุกตัวถูกเก็บในอาเรย์ จะเรียกใช้แต่ละทีก็อ้างดัชนีตรงๆ ไม่ได้ ต้องใช้วิธีเลื่อนพอยเตอร์ที่ชี้อาเรย์ซ้าย/ขวาเพื่อหาตัวแปรที่ต้องการ ดังนั้นการออกแบบตำแหน่งตัวแปรจึงสำคัญมาก โดยข้อนี้ผมออกแบบตำแหน่งตัวแปรต่างๆ ไว้ดังนี้
| ช่องที่ | ตัวแปร | ค่าที่เก็บ (ตัวอย่าง) |
|---|---|---|
| 1 | จำนวนข้อที่เหลือ | 4 |
| 2 | ตำแหน่งข้อปัจจุบัน | 1 |
| 3-4 | พื้นที่อเนกประสงค์ 1,2 | (ค่าว่าง) |
| 5 | ค่าคำตอบ | 2 |
| 6 | ตัวอักษรตัวที่ผ่านมา | - |
| 7 | ตัวอักษรตัวถัดไป | + |
| 8 | อ่านตัวอักษรต่อไป? | ใช่ |
| 9-… | พื้นที่อเนกประสงค์อื่นๆ | (ค่าว่าง) |
โดยส่วนโค้ดที่เป็นอัลกอริทึมของข้อนี้จริงๆ มีแค่บรรทัดที่ 4-13 และ 34 เท่านั้น ส่วนบรรทัดที่เหลือเป็นการจัดการกับการนำเข้า/ส่งออกข้อมูล
วิธีทำงานคร่าวๆ คือ
- บรรทัดที่ 4 ที่เริ่มทำงานแต่ละข้อ จะเพิ่มค่าตำแหน่งข้อปัจจุบันขึ้นมาก่อน (ช่องที่ 2) ล้างคำตอบให้เป็นศูนย์ (ช่อง 5) แล้วอ่านค่าตัวอักษรตัวแรกในข้อนั้นไปเก็บค่าไว้ในช่องเก็บตัวอักษรตัวที่ผ่านมา (ช่องที่ 6) พร้อมตั้งค่าให้อ่านตัวอักษรตัวต่อไป (ช่องที่ 8)
- บรรทัดที่ 5-6 อ่านค่าเข้ามาเก็บในช่องตัวอักษรตัวต่อไป (ช่องที่ 7) แล้วลบค่าออก 10 เพื่อจะได้ทดสอบว่า ตัวอักษรที่อ่านได้เป็นเครื่องหมายขึ้นบรรทัดใหม่หรือไม่?
- บรรทัดที่ 7 ถ้าตัวอักษรที่อ่านเข้ามาไม่ใข่เครื่องหมายขึ้นบรรทัดใหม่ ให้เพิ่มค่ากลับมา 10 เพื่อให้เป็นค่าเดิม
- บรรทัดที่ 8 แต่ถ้าตัวอักษรที่อ่านเข้ามาเป็นเครื่องหมายขึ้นบรรทัดใหม่ ให้เก็บค่าเครื่องหมาย + ลงไปในช่องตัวอักษรตัวต่อไป พร้อมทั้งตั้งค่าให้ไม่ต่องอ่านตัวอักษรตัวต่อไปแล้ว
- บรรทัดที่ 10-11 ทดสอบว่า ตัวอักษรตัวที่ผ่านมา มีค่าเท่ากับตัวอักษรตัวถัดไปหรือไม่? พร้อมทั้งย้ายค่าตัวอักษรตัวถัดไปเข้าไปเก็บแทนค่าตัวอักษรตัวก่อนหน้า
- บรรทัดที่ 12 ถ้าการทดสอบให้ผลลัพธ์ว่าตัวอักษรมีค่าไม่เท่ากัน ให้บวกหนึ่งเข้าไปในคำตอบ (ช่อง 5)
- บรรทัดที่ 13 ตรวจดูว่าจะอ่านตัวอักษรตัวต่อไปหรือไม่ ถ้าอ่านต่อก็ย้อนกลับไปทำบรรทัดที่ 5 ไล่ลงมาอีกครั้ง แต่ถ้าไม่ก็พิมพ์คำตอบในข้อนั้นๆ ออกมา
- บรรทัดที่ 34 เมื่อทำงานเสร็จหนึ่งข้อ ก็ไปลบจำนวนข้อที่เหลือลงมาหนึ่ง (ช่องที่ 1) หากไม่เหลือข้อที่ต้องทำแล้วก็ถือเป็นอันจบโปรแกรม
ข้อ 3 ถึกครับ หมดพลังไปกับข้อก่อน เลยคิดอัลกอริทึมดีๆ ไม่ออก รู้สึกละอายใจต่อโค้ด ไม่เอามาลงในนี้ละกันนะ ใครอยากเห็นไปหาดูเอง …
Fractiles
ส่วนข้อสุดท้ายก็ทำได้แต่ข้อมูลนำเข้าชุดเล็ก เพราะว่าข้อกำหนดมันง่ายกว่าข้อมูลชุดใหญ่ตรงที่ให้จำนวนเงิน $s$ มาเท่ากับจำนวนกระเบื้อง $k$ เลย ทำให้ทุกข้อในข้อมูลนำเข้าชุดเล็กนี้ สามารถหาคำตอบได้แน่นอน โดยวิธีคิดแบบง่ายนั้น จะพิจารณาแต่ละรูปแบบฐานที่มีกระเบื้องทองคำเพียงแค่ชิ้นเดียว และสลับกฎว่า กระเบื้องตะกั่วจะถูกแทนที่ด้วยกระเบื้องตะกั่วทั้งหมด และกระเบื้องทองทองจะถูกแทนที่ด้วยกระเบื้องตามรูปแบบฐาน (ดังนั้นสุดท้ายแล้วจะมีกระเบื้องทองคำเพียงแค่ชิ้นเดียว) เช่น ในกรณีที่รูปแบบฐานมีกระเบื้อง $k=3$ และที่มีกระเบื้องทองคำอยู่ตรงกลาง $g=2$ จะได้ว่า
\[\begin{align} C &= 1; & LGL \\ C &= 2; & LLL \; LGL \; LLL \\ C &= 3; & LLL \; LLL \; LLL \quad LLL \; LGL \; LLL \quad LLL \; LLL \; LLL \end{align}\]หากให้ $L(k,g,c)$ เป็นค่าที่ได้จากฟังก์ชันหาตำแหน่งกระเบื้องทองคำในรูปแบบดังกล่าว จะได้ว่า
\[\begin{align} L(3,2,1) &= 2 \\ L(3,2,2) &= 3 + 2 \\ &= 5 \\ L(3,2,2) &= 9 + 3 + 2 \\ &= 14 \\ L(3,2,c) &= 3^c + 3^{c-1} + \cdots + 3^1 + 3^0 + 1 \\ &= \frac{3^{c+1}-1}{3-1} + 1 \\ L(3,g,c) &= g \frac{3^{c+1}-1}{3-1} + 1 \\ L(k,g,c) &= g \frac{k^{c+1}-1}{k-1} + 1 \end{align}\]เมื่อได้ฟังก์ชันหลักแล้ว ก็ลุยเขียนโค้ดกันเลย
import Text.Printf (printf)
getInts :: IO [Int]
getInts = do
it <- getLine
return $ [read n | n <- words it]
printList :: [Int] -> IO ()
printList [] = do printf "\n"
printList (g:gs) = do
printf " %i" g
printList gs
geometricSeries :: Int -> Int -> Int
geometricSeries 1 _ = 1
geometricSeries base power = quot (base^power - 1) (base - 1)
goldLocations :: Int -> Int -> [Int]
goldLocations pattern complexity =
let basePosition = geometricSeries pattern complexity
in [placement * basePosition + 1 | placement <- [0..pattern-1]]
test :: Int -> IO ()
test t = do
[pattern,complexity,_] <- getInts
printf "Case #%i:" t
printList $ goldLocations pattern complexity
main :: IO ()
main = do
[loop] <- getInts
sequence_ [test t | t <- [1..loop]]
ทำเสร็จแล้วกลับมาคิดๆ ต่ออีกนิดนึง ก็รู้สึกเหมือนจะมองภาพออกว่าข้อนี้มันควรแก้ยังไงในแบบยาก … แต่เหนื่อยมากแล้ว ถ่างตาทำยันเช้า เวลาก็น่าจะเหลือไม่พอให้เก็บบั๊กอะไรครบหมดอีก เลยตัดใจนอนปีหน้าเอาใหม่ :p
author