Apr 27, 2013

Code Jam 2013 รอบ 1A

รอบนี้ตอนแรกว่าจะปล่อยผ่านเพราะอุตสาห์มากทม.ทั้งที อยากไปร่วมฟาร์มเสา 8 กับเหล่า agent ทั้งหลายด้วย

แต่คิดไปคิดมา คราวก่อนก็วืดเพราะมีแต่ไปคาราโอเกะ เลยคิดว่าควรให้ importance และ energy กับการแข่งให้มากที่สุดจะดีกว่า

รอบนี้เหมือนจะเป็น math จ๋าเลย แค่ข้อแรกที่ถามว่าจะระบายธนูได้กี่วง ก็ต้องใช้ความรู้เรื่องพื้นที่วงกลม + สมการกำลังสอง + อนุกรมเข้ามาช่วย

เราเริ่มจากสังเกตว่าวงกลมแรกจะใช้สีระบายไป 2r + 1 วงกลมถัดๆ มาใช้ 2r + 1 + 4 และ 2r + 1 + 8 ดังนั้นจะตั้งเป็นสมการได้ว่า

used_color(n) = (2r+1) + (2r+1 + 4) + (2r+1 + 8) + ... + (2r+1 + 4(n-1))
              = summation (2r+1 + 4k) for k in [0 .. n-1]
              = n(2r+1) + 4 * summation k for k in [0 .. n-1]
              = n(2r+1) + 4n(n-1)/2
              = n(2r+1) + 2n(n-1)

แต่เนื่องจากสิ่งที่เรารู้คือ t = used_color(n) และต้องการคำนวณกลับเพื่อหา n ดังนั้น

0 = n(2r+1) + 2n(n-1) - t
  = 2n^2 - (2r-1)n - t

ก็จะได้ว่า

a = 2
b = 2r - 1
c = -t
n = (-b ± sqrt(b^2 - 4ac)) / 2a

ถึงตอนนี้ก็แค่แก้สมการข้างบน ได้คำตอบมา 2 อันก็เลือกเอาคำตอบที่มากกว่า 0 แล้วปัดเศษทิ้งครับ



ข้อสองคิดวิธี optimize ไม่ออก เลยเขียน recursive ไป (loop ใหญ่สุดของแบบเล็กคือ 60 ล้าน ก็ยัง brute-force ออกในเวลาที่รับได้) แต่เสียดายที่คิดผิด debug ไม่ทัน

ส่วนข้อสามแนวคิดคือหาตัวคูณร่วมน้อยของเลขทั้ง set ที่เค้าให้ แล้วก็แยกตัวประกอบมันออกมาเป็น list นึง ทีนี้ถ้า list มันใหญ่กว่าขนาดของการ์ดทั้งหมดก็ merge ตัวเลขใน list นี้ด้วยการคูณจนกว่ามันจะมีขนาดเท่ากับการ์ด เท่านี้เอง (อันนี้ออกแค่ข้อเล็ก)

อันดับระหว่างแข่งคือ 18xx พอจบรอบตรวจคะแนนจริงก็เด้งกลับมาที่ 1377 เพราะข้อที่ส่งไปถูกหมด (แต่ก็ยังไม่เพียงพอสำหรับผ่านเข้ารอบต่อไปอยู่ดี) ... ไม่เป็นไรรอบหน้าเอาใหม่ เนอะ ^^)v

Apr 14, 2013

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


เนื่องจากไม่อยากให้เกิดเหตุการณ์แบบรอบ 1 ของปีที่แล้ว ปีนี้เลยนอนเอาแรงไม่บ้าพลังถ่างตาทำตั้งแต่เช้ามืด ทำให้กว่าจะได้เริ่มอ่านโจทย์ก็บ่าย 2 เข้าไปแล้ว

ปีนี้ความตั้งใจแรกคือจะพยายามเขียนส่งให้ได้หลายๆ ภาษา คือฝึก ML, Lisp, Bash อะไรพวกนี้จนคิดว่าน่าจะคล่องพอเอามาใช้แก้โจทย์ปัญหาจริงๆ ได้แล้ว น่าเสียดายที่รับ input ไม่เป็น เลยกลับมาตายรังด้วย Python เหมือนเดิม (แต่ก็มี Haskell โผล่มาครึ่งข้อ) ไม่แน่ใจว่ารอบต่อๆ ไปจะเขียน C++ ทันหรือเปล่า เพราะโดนจำกัดเวลาเหลือแค่ 2.5 ชั่วโมงแล้ว

ข้อแรกโจทย์ extended เกม OX ให้ใหญ่ขึ้นเป็นตาราง 4x4 แถมยังอนุญาตให้มี wildcard (เป็นได้ทั้ง X และ O) อย่างมาก 1 ที่บนกระดาน ก็ถามว่าเกมตอนนี้ใครชนะ หรือว่าเสมอ หรือว่ายังเล่นไม่จบ

เคยเจอคำถามเกี่ยวกับ grid แบบนี้มาพอสมควร อันที่จริงก็ต้องไล่เช็คทั้งแนวตั้ง แนวนอน และก็แนวทะแยงซ้ายขวาเลย แต่เพิ่งมาสำนึกได้ว่าเขียนแบบนั้นมี code ซ้ำกันเยอะๆ จะเริ่ม maintenance ยากละ เลยสังเกตว่าถ้าหมุน grid ให้ได้เป็นแบบนี้

1 2 3      7 4 1
4 5 6  =>  8 5 2
7 8 9      9 6 3

จะสามารถ reuse code ส่วนที่เช็คแนวนอนมาเช็คแนวตั้งได้ด้วย เช่นเดียวกับ code เช็คแนวทะแยง การ implement แค่ส่วนนี้คงมีวิธีเจ๋งๆ ให้เลือกใช้เยอะอยู่ ส่วนผมที่มาจากสาย functional เลือกใช้ transpose . reversed ครับ

def transpose(grid):
    return [''.join(line) for line in zip(*grid)]

def chk_hori(grid):
    for line in grid:
        if all(c in 'XT' for c in line):
            return 'X won'
        if all(c in 'OT' for c in line):
            return 'O won'

def chk_diag(grid):
    if all(grid[i][i] in 'XT' for i in range(len(grid))):
        return 'X won'
    if all(grid[i][i] in 'OT' for i in range(len(grid))):
        return 'O won'

def chk_won(grid):
    for _ in range(2):
        for chk in [chk_hori, chk_diag]:
            answer = chk(grid)
            if answer:
                return answer
        grid = transpose(reversed(grid))

def chk_full(grid):
    return not any('.' in line for line in grid)

for case in range(int(input())):
    grid = [input() for _ in range(4)]
    input()
    answer = chk_won(grid)
    if not answer:
        answer = 'Draw' if chk_full(grid) else 'Game has not completed'
    print('Case #{}: {}'.format(case+1, answer))



ข้อถัดมาถามว่าสามารถใช้เครื่องตัดหญ้าอัตโนมัติ (ที่ดันวิ่งตรงไปข้างหน้าได้อย่างเดียว) ตัดหญ้าให้แต่ละช่องมีความสูงตาม pattern ที่วางไว้ได้หรือเปล่า

พบว่า algorithm ง่ายกว่าที่คิด คือดูว่าแต่ละจุดบนสนามหญ้านั้น ต้องมีความสูงเท่ากับความสูงหญ้าที่สูงที่สุดในแนวนอนหรือแนวตั้งเท่านั้น เพราะถ้าเกิดมีจุดที่สูงกว่าทั้งแนวนอนและแนวตั้งพร้อมกัน จะทำให้ไม่สามารถตัดหญ้าในช่องนั้นให้ต่ำกว่าค่าสูงสุดได้

def transpose(lawn):
    return [list(line) for line in zip(*lawn)]
    
def beautiful_garden(lawn, n, m):
    tlawn = transpose(lawn)
    def chk(y, x):
        return lawn[y][x] in [max(tlawn[x]), max(lawn[y])]
    return all(all(chk(y, x) for x in range(m)) for y in range(n))
            
for case in range(int(input())):
    n, m = [int(i) for i in input().split()]
    lawn = [[int(i) for i in input().split()] for _ in range(n)]
    answer = 'YES' if beautiful_garden(lawn, n, m) else 'NO'
    print('Case #{}: {}'.format(case+1, answer))



ข้อที่ 3 ให้ว่ามีเลข palindrome ที่รากที่สองของมันก็ยังเป็น palindrome ด้วยทั้งหมดกี่ตัวในช่วงที่กำหนด ซึ่งมีความรู้สึกว่าถ้าเล่นกับ palindrome แล้ว Haskell จะสวยงามมาก แต่ก็ไปตายที่ test กลางเลยกลับไปใช้ Python แทน

import Data.List.Split (splitOn)

boolAsNum b = if b then 1 else 0

isSquare x = root^2 == x
    where root = sqrt x

isPalindrome x = y == reverse y
    where y = show x

countFair x y
    | x > y     = 0
    | otherwise = (boolAsNum $ all isPalindrome [x,x^2]) + countFair (x+1) y

eachLoop nosLoop = do
    raw <- getLine
    let rawSqrtNum = [sqrt $ read x | x <- splitOn " " raw]
        [start, stop] = [f x | (f,x) <- zip [ceiling, floor] rawSqrtNum]
    putStrLn $ "Case #" ++ (show nosLoop) ++ ": " ++ (show $ countFair start stop)

main = do
    allLoop <- getLine
    sequence_ [eachLoop n | n <- [1..read allLoop]]

ส่วนนี่คือ Python ที่ optimize ไปนิดหน่อยสำหรับความยากปานกลาง โดยส่วนที่วนสร้างเลข palindrome ตัวถัดไปยังไม่ได้ optimize สำหรับโจทย์นี้โดยเฉพาะเลย (ว่าแล้วก็ต้องเขียนเก็บเข้า lib ตัวเองซะแล้ว)

odd = lambda x: x % 2 == 1
square = lambda n: int(n ** 0.5) ** 2 == n
palindrome = lambda n: str(n) == str(n)[::-1]

def int_sqrt(n):
    if n == 0: 
        return 0
    a, b = divmod(n.bit_length(), 2)
    x = 2 ** (a + b)
    while True:
        y = x + n // x 
        y //= 2
        if y >= x: 
            return x
        x = y

def next_palindrome(n):
    s = str(n)
    size = len(s)

    fst = s[:size//2+1] if odd(size) else s[:size//2]
    lst = s[-size//2:]

    size_old_fst = len(fst)
    if fst <= lst[::-1]:
        fst = str(int(fst) + 1)

    lst = fst[:-1] if len(fst) > size_old_fst else fst
    return int(fst[:-1] + lst[::-1]) if odd(size) else int(fst + lst[::-1])

def palindrome_range(start, stop):
    while start < stop:
        if palindrome(start):
            yield start
        start = next_palindrome(start)

for case in range(int(input())):
    start, stop = [int(n) for n in input().split()]

    start = int_sqrt(start) + (0 if square(start) else 1)
    stop = int_sqrt(stop)

    answer = sum(palindrome(pal**2) for pal in palindrome_range(start, stop+1))
    print('Case #{}: {}'.format(case+1, answer))



ส่วนข้อ 4 ไม่ได้ทำ เพราะสังเกตเห็น pattern ของข้อ 3 เลยกะจะแก้ความยากระดับโหดสุด (input ใหญ่ได้ถึง 10^100) แต่ลอง optimize ดูแล้วทำทันแค่ 10^80 เท่านั้น ก็เลยต้องตัดใจไปตามระเบียบ แต่แต้มแค่นี้ก็เพียงพอสำหรับรอบ 1 แล้วครับ ;)

Apr 8, 2013

TCDC เชียงใหม่

tl; dr มันคือห้องสมุดฮายโซวสำหรับ designer นั่นเองครับ



วิธีการเดินทางก็ไม่ยาก ถ้ามาจากแจ่งหมูกะทะ (แจ่งศรีภูมิ) ให้ไปทางริมแม่น้ำปิง (ทางที่จะไปเจดีย์ขาว) พอถึงอีกไฟแดงนึงก็เลี้ยวซ้ายเลย TCDC อยู่ซ้ายมือครับ

ที่น่าทึ่งก็คือใน Google Street View ยังไม่มีอาคารนี้เลย นับว่าสร้างได้เร็วมากๆ (แต่มองจาก satellite mode เห็นหลังคาแล้วนะ)



ตัวอาคารทำจากวัสดุเทียบเคียงไม้สร้างเป็นทรงเรขาคณิตเรียบๆ ออกแนว modern-minimalism มี 3 ชั้น (ผมหาทางขึ้นชั้น 3 ไม่เจอ -- แต่ช่างมันเพราะเป็นชั้นสำหรับเจ้าหน้าที่) เนื่องด้วยความเรียบ (เกินไป) ของมันเลยทำให้ไม่รู้ว่าจะถ่ายรูปมุมไหนดี แถมยังมีบริเวณที่ห้ามถ่ายรูปอีกด้วย - -"

ส่วนนี่เป็น model งานออกแบบอาคาร TCDC แบบอื่นๆ ที่ไม่สามารถนำมาสร้างจริงได้ แต่ก็สวยใช่เล่น



ด้านพื้นที่ใช้สอย ชั้นล่างสุดเป็นส่วนแสดงนิทรรศการ ไปคราวนี้เจองาน "เล่าเรื่อง เมืองใหม่ Chiang Mai Revisited" โดยเน้นเขตเศรฐกิจอย่างย่านนิมมานเหมินทร์ที่เปลี่ยนไปมากในช่วงไม่กี่ปีที่ผ่านมานี้ครับ



ส่วนชั้นสองเป็นห้องสมุด designer ที่ไม่ได้มีแต่หนังสือศิลปะอย่างเดียว แต่ยังจัดบริเวณที่เป็น material lib ไว้ด้วย (ตัวอย่างของ material แบบต่างๆ ที่นิยมใช้ในงานออกแบบเช่น เนื้อผ้า กระเบื้อง กระดาษ กระจก -- ห้ามถ่ายรูปแล้ว) ซึ่งส่วนตัวผมว่ามันยังน้อยไปหน่อย จริงๆ แล้วเอาหนังสือออกให้ไปหมดเพื่อแสดงแต่ material เลยก็น่าจะได้นะ?

จบดื้อๆ แบบนี้แหละครับ สำหรับผมที่ไม่ใช่สาย art คงรู้สึกเฉยๆ แต่ถ้าเป็นเด็กวิจิตร/ถาปัดก็อาจจะถือว่าเป็นแดนศักดิ์สิทธิ์ที่ควรไปสักการะบ่อยๆ ก็ได้นะ

Apr 7, 2013

Bit Flag

ในภาษาสมัยใหม่ เราคงคุ้นเคยกับการเขียนฟังก์ชั่น (และเรียกใช้) แบบนี้

def foo(n, m, a=False, b=False, c=False):
    if a:
        n += 42
    if b:
        n *= 7
    if c:
        n **= 2
    return n % m

...

foo(5, 99)
foo(5, 99, a=True)
foo(5, 99, c=True)
foo(5, 99, c=True, b=True, a=True)

โชคร้ายที่ระบบ keyword argument ไม่ได้เป็นแบบนี้ทุกภาษา อย่างเช่นใน PHP ถ้าจะเปิดตัว flag c เพียงตัวเดียว ก็ยังคงต้องบอกว่า a, b ถูกปิดอยู่ด้วย (ต้องบอกสถานะของ flag ทุกตัวที่อยู่ก่อนหน้า c)

ทางออกง่ายๆ แต่ทำให้ syntax ดูรุงรังหน่อยคือการให้ argument ส่วนที่เป็น flag ใช้ datatype แบบ hash table เช่นนี้

function foo($n, $m, $options=array()) {
    if (array_key_exists('a', $options) && $options['a'])
        $n += 42;
    if (array_key_exists('b', $options) && $options['b'])
        $n *= 7;
    if (array_key_exists('c', $options) && $options['c'])
        $n *= $n;
    return $n % $m;
}   

...

foo(5, 99);
foo(5, 99, array('a' => true));
foo(5, 99, array('c' => true));
foo(5, 99, array('c' => true, 'b' => true, 'a' => true));

ทางออกที่คลาสสิก (แต่ปวดหัว) กว่าคือการใช้ bit flag แบบนี้

const int A = 0x01;
const int B = 0x02;
const int C = 0x04;

int foo(int n, int m, int options) {
    if (options & A)
        n += 42;
    if (options & B)
        n *= 7;
    if (options & C)
        n *= n;
    return n % m;
}

...

foo(5, 99, 0);
foo(5, 99, A);
foo(5, 99, C);
foo(5, 99, C|B|A);

หลายคนอาจบอกว่าการใช้ bit flag นั้นมีข้อดีเหนือกว่า keyword argument ตรงที่สามารถ store สถานะของ flag เก็บไว้ใน data ตัวหนึ่ง (เพื่อที่จะนำไปใช้ซ้ำในที่อื่น) ซึ่งข้อได้เปรียบนี้ไม่เป็นความจริงเลยสำหรับภาษาที่แตก array, hash table ลงไปเป็น argument ได้

args = [5, 99]
flags = {'b': True, 'c': True}

foo(*args, **flags) == foo(5, 99, b=True, c=True)

ก็เลือกใช้ความสามารถเหล่านี้ตามความสะดวกของแต่ละภาษานะครับ อย่าไปฝืนมันมากถ้าตัวภาษามันไม่ได้ออกแบบให้ทำเรื่องยากๆ บางเรื่องไว้แต่แรก