วงแหวนเว็บ

neizod's speculation

insufficient data for meaningful answer

Code Jam 2016 รอบคัดเลือก

Sunday, April 10, 2016, 11:27 PM

วนมาอีกปีกับ 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

neizod

author