Code Jam 2013 รอบ 1B และ 1C

สั้นๆ ครับ ปีนี้ขยันน้อย สมองไม่ค่อยแล่น รอบ 1B และ 1C เลยไม่ได้ส่งซักข้อ Orz

แต่ก็ได้ไอ้นี่มาจากข้อ Pogo (ข้อ B จากรอบ 1C) แม้จะสวยดีแต่ก็ไม่ได้ช่วยตอบคำถามข้อนี้แต่อย่างใด 55+



update: ตอนแรกคิดอออกมาได้ตารางข้างบน แล้วก็เพิ่งมานึกออกว่า algo ผิดเพราะลืมไปว่าการเดินตกจุดเดิมซ้ำด้วย move ที่ไม่เท่ากันนั้นมี่ค่าต่างกันสำหรับการเดินรอบต่อไป เลยแก้ออกมาจนได้รูปด้านล่าง....... กลายเป็นว่าง่ายเลยข้อนี้ T T (เอา 38 คะแนนของตรูคืนมาาาา)

เซ็นทรัลลำปาง

เมื่อวานมีโอกาสได้แวะไปลำปางแบบด่วนๆ (ไปเย็นกลับค่ำ) เลยแวะสำรวจเล็กน้อย และพบว่ามันมาทรงเดียวกับเซ็นทรัลพิษณุโลกเลย เพียงแต่สั้นกว่า (มาก)

• อย่างไรก็ดี เซ็นทรัลลำปางก็มีข้อดี (?) ที่เหนือกว่าเซ็นทรัลพิษณุโลกอย่างมาก คือตำแหน่งที่ตั้งนั้นอยู่ใจกลางเมืองพอดี แถมยังติดสถานศึกษาอย่างโรงเรียนลำปางกัลยาณีและบุญวาทย์วิทยาลัยแถวๆ นั้นอีก ก็น่าจะดึงคนได้เยอะดีพอสมควร
• แต่คนกลับไม่เยอะอย่างที่คิด ขนาดเป็นวันศุกร์ตอนเย็น ที่จอดรถยังโล่งๆ คนน้อยกว่าเซ็นทรัลกาดสวนแก้วเชียงใหม่อีก (อาจเป็นเพราะสัปดาห์นี้หยุดยาว 3 วันก็ได้)
• ที่งงคือลานจอดรถด้านหลังก็ค่อนข้างใหญ่ แต่ทำไมถึงมาจอดถนนใหญ่หน้าห้างกันเยอะแยะ หรือนี่เป็นเรื่องปรกติของคนลำปางกันไปแล้ว
• ว่าด้วยเรื่องลักษณะอาคาร อย่างที่บอกไปแล้วว่ามันคือเซ็นทรัลพิษณุโลก ก็คือมีส่วนที่เป็นห้าง 3 ชั้น พร้อมชั้นที่คล้ายๆ จะเป็นชั้นใต้ดินไว้จอดรถอีก 1 ชั้น
• โรงหนังที่นี่เป็น SF แฮะ สงสัยจะได้แวะเที่ยวบ่อยๆ ซะแล้ว :P
• มี McDonald, KFC, Yamazaki, Swensens, Shabushi, Sukishi, Santafe, Jeffer แต่ไม่มี Sizzler
• Starbucks ไม่มีคนเลย
• แต่ iStudio คนแวะเข้าออกตลอด
• ของน้อยมาก หา Lego ไม่ค่อยได้เลย เพลงคลาสสิกใน B2S ยิ่งไม่ต้องพูดถึง

อันที่จริงแล้วผมเชียร์ให้ลำปางเป็นจุดศูนย์กลางภาคเหนือมากกว่าเชียงใหม่นะ ว่ากันตามภูมิประเทศแล้ว ตรงนี้เป็นจุดยุทธศาสตร์สำคัญเลยเพราะไปได้ทั้งตาก เชียงใหม่ เชียงราย (ลำปางเชียงรายใช้เวลาพอๆ กับเชียงใหม่เชียงราย) แถมการเดินทางจากภาคกลางขึ้นมาจนถึงลำปาง ก็ถือว่าใช้เวลาได้เหมาะสมดี (จากลำปางไปเชียงใหม่ต้องเพิ่มอีก 1.5 ชั่วโมง)

เสียดายที่เชียงใหม่แย่งชิงคนไปได้หมด ซึ่งน่าจะเกิดขึ้นเพราะการตั้งมหาวิทยาลัยเชียงใหม่เมื่อกว่า 40 ปีก่อน ทำให้คนในวัยกำลังเริ่มทำงานเลือกที่จะตั้งหลักปักฐานใกล้กับมหาวิทยาลัยที่จบการศึกษา ด้วยเหตุผลทั้ง connection กับมหาวิทยาลัย, แรงงานจากรุ่นน้องที่ศึกษาอยู่, ความหนาแน่นของผู้คน ฯลฯ

ก็ต้องดูต่อไปว่าการมาของเซ็นทรัลลำปาง จะช่วยชุบชีวิตเมืองนี้ให้กลับมายิ่งใหญ่ได้หรือไม่ครับ

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

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 แล้วครับ ;)

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 คงรู้สึกเฉยๆ แต่ถ้าเป็นเด็กวิจิตร/ถาปัดก็อาจจะถือว่าเป็นแดนศักดิ์สิทธิ์ที่ควรไปสักการะบ่อยๆ ก็ได้นะ

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)

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

42

เนื่องจากเมื่อวานเป็นวันคล้ายเกิดของ Douglas Adams ซึ่งถ้าเขามีชีวิตอยู่ก็จะอายุขึ้นปีที่ 61 แล้ว Google เลยทำ Doodle รำลึกถึงนักเขียนนิยายชื่อก้องคนนี้ให้ได้เล่นกันครับ


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

• ประตูถอนหายใจ ที่เปิดออกมาก็จะเจอกับเจ้าหุ่นมาร์วินผู้แบกโลก (เวอร์ชันหนังมาร์วินหัวโตกว่านี้มาก)
• คอนโซลยานที่คอยพ่นเทปสื่ออารมณ์ ถ้ามัวอ่านแต่ข้อความในเทปนี้คงไม่ได้ทำอะไรพอดี
• ที่เป็นแท่งๆ นั่นคือนิ้วอิเล็กทรอนิกส์สำหรับโบกยาน - เวลาฝรั่งเค้าโบกรถจะเหยียดแขนสุดแล้วชูนิ้วโป้งขึ้น (เวอร์ชันหนังเครื่องนี้กลายเป็นแหวนสวมนิ้วแทน)
• เครื่องซับอีธาเซนโซเมตริก เอาไว้รับสัญญาณของยานอวกาศที่อาจบังเอิญบินผ่านมาให้ได้โบก
• ชาจากเครื่องชงเครื่องดื่มอัตโนมัติ ที่จะพยายามอ่านความคิดของคนสั่งว่าต้องการเครื่องดื่มอะไร แต่ทำไมเครื่องดื่มทุกแก้วที่ผลิตได้ถึงมีรสชาติที่ไม่ต่างกันเลย?
• ตัวหนังสือคู่มือนักโบก หัวใจหลักของเรื่องนี้ พร้อมข้อความอันเป็นมิตรว่า "อย่าได้ตกใจ"
• กระเป๋าเดินทางที่สูญหายของอาเธอร์ แล้วอยู่ๆ ก็โดนพ่นออกมาจากถังขยะห้วงเวลา
• ผ้าเช็ดตัว อุปกรณ์สารพัดประโยชน์ที่นักโบกต้องมีคู่กายเสมอ

และนี่คือเรื่องราวต่างๆ ที่สามารถอ่านได้จากหนังสือคู่มือนักโบก

• ปลาแปลภาษาที่คอยกินคลื่นเสียงเป็นอาหาร แล้วขับถ่ายออกมาเป็นสัญญาณประสาทในภาษาของผู้ที่ใส่ปลานี่ไว้ในหู
• คำจำกัดความของโลกโดยหนังสือเล่มนี้ เนื่องจากไม่ค่อยมีเนื้อหาสาระใดๆ จึงสามารถเขียนอธิบายได้สั้นๆ แค่ว่า "แทบปราศจากภยันอันตราย"
• เคล็ดลับสำหรับการบิน.... ก็เพียงแค่หกล้มให้ไม่โดนพื้นแค่นั้นเอง
• รสชาติของเครื่องดื่มสุดยอดแห่งจักรวาล แพน-กาแลคติค การ์เกิล บลัสเตอร์
• ระบบการเดินทางด้วยหลักการความไม่น่าจะเป็นของยานหัวใจทอง ที่สามารถเดินทางจากปลายจักรวาลด้านหนึ่งไปสู่อีกด้านได้ในพริบตา
• ต้นกำเนิดของจักรวาลที่เราอาศัยอยู่ ที่จริงแล้วก็เป็นเพียงการสั่งน้ำมูกของยักษ์เท่านั้น
• มนุษย์ที่คิดว่าตัวเองฉลาดที่สุดบนโลก แท้จริงแล้วก็ฉลาดน้อยกว่าปลาโลมาและหนูเสียอีก
• ความสำคัญของผ้าเช็ดตัวที่นักโบกทุกคนต้องมีคู่กาย
• จุดจบของโลกใบเล็กๆ จากพวกโวกอนที่ป่าเถื่อน
• คอมพิวเตอร์สุดฉลาดล้ำคิดลึก ที่ตอบคำถามสุดยอดของชีวิต จักรวาล และทุกสรรพสิ่งได้ว่าเท่ากับ 42

Swap ตัวแปร

โปรแกรมที่เล็กและง่ายรองจาก hello world ที่โปรแกรมเมอร์หลายคนต้องผ่านตามาบ้าง คือโปรแกรม (ฟังก์ชัน) สำหรับสลับค่าตัวแปรนั่นเอง

แต่ก่อนจะลงลึกที่รายละเอียด มาดู simple yet best practice ใน Pyhton กันก่อน :P

a, b = b, a

---

อธิบายก่อนว่าการเข้าถึง data ในคอมพิวเตอร์ จะคล้ายๆ กับคนที่มีแขนข้างเดียว คือหยิบของได้ทีละ 1 อย่าง ไม่สามารถหยิบของพร้อมกัน 2 อย่างแล้ววางสลับที่กันทันทีได้เหมือนในชีวิตจริง

วิธีแก้ปัญหาที่ตรงไปตรงมาภายใต้ข้อจำกัดนี้ คือหยิบของชิ้นแรกไปวางไว้ในที่ว่างก่อน หยิบของชิ้นที่สองไปวางแทนที่ๆ ของชิ้นแรกเคยอยู่ แล้วค่อยกลับไปหยิบของชิ้นแรกวางแทนที่ๆ ของชิ้นสองเคยอยู่

จะอธิบายให้คอมพิวเตอร์เข้าใจได้ ก็ต้องบอกด้วยว่าที่ว่างนั้นคือตรงไหน (พูดลอยๆ ไม่ได้ เดี๋ยวกลับไปหาไม่เจอ) เช่นนี้

int t;

t = a;
a = b;
b = t;

ปัญหาของการย้ายแบบนี้ คือมันเป็นการมองในเชิง object โลกมนุษย์ ซึ่งไม่ได้ใกล้เคียงกับกิจกรรมที่เกิดขึ้นใน memory เลย มันไม่ใช่การย้ายของด้วยซ้ำ แต่เป็นการทำสำเนาสิ่งของแล้วย้ายที่สลับไปมาต่างหาก

อนึ่ง วิธีนี้ยังมีข้อเสียตรงที่มันใช้พื้นที่ว่างเพิ่มเติมสำหรับเก็บข้อมูลระหว่างทางอีก แล้วมันจะมีทางมั้ยที่จะสลับที่ตัวแปรโดยไม่ต้องอาศัยตัวแปรอื่นเข้ามาทำหน้าที่เป็นที่พักข้อมูล?

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

a = a + b;
b = a - b;
a = a - b;

แบบนี้ก็เกือบดีแล้ว แต่ยังมีข้อควรระวังคือ overflow เนื่องจากมันเป็นวิธีทางคณิตศาสตร์ แถมโปรแกรมแบบนี้ก็ยังไม่ค่อยสวยงามเท่าไหร่ด้วย

ถ้าจะมองให้เป็นไปในทางคอมพิวเตอร์จริงๆ ต้องเปลี่ยนการดำเนินการ +, - ไปใช้ xor แทน เช่นนี้

a ^= b;
b ^= a;
a ^= b;

ซึ่งสามารถลดรูปได้อีกขั้นจนเหลือเพียงบรรทัดเดียวว่า

a ^= b ^= a ^= b;

อย่างไรก็ตาม การมองว่าคอมพิวเตอร์เปรียบเหมือนคนที่มีแขนข้างเดียวนั้น ก็คงไม่ถูกต้องอีกต่อไปแล้ว (เป็นการมองแบบ Turing machine ซึ่งตกยุคไปชาติเศษๆ) เพราะในปัจจุบัน คอมพิวเตอร์มีแขนเหล่านี้เพิ่มมากขึ้น และสามารถเข้าถึงข้อมูลได้หลายตำแหน่งในเวลาเดียวกัน แต่การเขียนโปรแกรมให้ทำงานแบบ parallel ให้ได้ดีนั้น ก็ไม่ใช่เรื่องง่ายซักเท่าไหร่นัก หน้าตาของโปรแกรมอาจจะออกมาเช่นนี้

process [1, 2]:
  goto address [a, b]
  read into process memory
  sync with process [2, 1]
  goto address [b, a]
  write from process memory

---

ส่วนภาษาเชิง functional ที่ไม่ยอมให้มี mutable อย่างการสลับเปลี่ยนค่าตัวแปร ก็ยังสามารถทำท่านี้ได้โดยใช้เทคนิคตั้งชื่อตัวแปรสลับที่กันใน environment ที่ต่างกัน (ภาษาเค้าเรียกว่า Monad) ต่อไปนี้คือตัวอย่างใน Haskell

do (a,b) <- return (b,a)
   someMagic a b
   ...

หรือแบบนี้ใน Lisp (สังเกตการใช้คำสั่ง let เพื่อสลับตัวแปร)

(let ([a b]
      [b a])
  (magic-happens a b ...))

---

สุดท้ายนี้กลับไปดู Python ที่เรียบง่ายอีกรอบ แท้จริงแล้วมันคือการสั่ง

container = b, a
a, b = container

แปลได้ว่า แรกสุดมันจะเก็บค่าตัวแปร b และ a ตามลำดับลง container ชนิดหนึ่ง (ใน Python มันคือ tuple) แล้วหลังจากนั้นจึงดึงตัวแปรออกจาก container นี้มาให้ตัวแปร a และ b ตามลำดับ แนวคิดแบบนี้ค่อนข้าง general มาก และสามารถนำไปใช้กับกรณีที่มีตัวแปรให้สลับเยอะกว่านี้ได้ด้วย เช่น

a, b, c, d = d, -b, -c, a

ลำดับ Farey และ วงกลม Ford

ปีที่แล้วเล่น Project Euler ไปได้หลายข้อ แล้วก็สะดุดตากับข้อที่น่าสนใจ เลยเอามาขยายผลต่อจนได้เป็นเรื่องนี้ขึ้นมา

อธิบายสั้นๆ คือลำดับ Farey เป็นลำดับของเศษส่วนอย่างต่ำตั้งแต่ 0/1 ไปจนถึง 1/1 เพราะฉะนั้นตัวเลขอย่าง 2/4 จึงไม่นับ (หรือถ้าจะนับ ก็ทำให้มันเป็น 1/2 ก่อน)

อย่างไรก็ดี ถ้านิยามอย่างนี้เราจะมีปัญหาว่าลำดับ Farey มันดันเป็นลำดับอนันต์ซะหนิ ดังนั้นเลยเพิ่มข้อจำกัดไปว่า ลำดับ Farey อันดับ n จะบรรจุเศษส่วนอย่างต่ำ ที่ตัวส่วนมีค่าน้อยกว่าเท่ากับ n เท่านั้น

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

ส่วนวงกลม Ford ก็เป็นวงกลมที่นำเอาลำดับ Farey ไปวาดแสดงผลได้อย่างสวยงาม ;)

รายละเอียดทั้งหมดอยู่ในเอกสารฉบับนี้ ไม่ต้องกลัวว่าเป็นภาษาคณิตศาสตร์แล้วจะเข้าใจยาก เพราะมีโปรแกรมที่เขียนด้วย Python ให้ไปแกะโค้ดเล่นกันด้วย

ปล. blog ตอนนี้ เขียนเป็นพิเศษให้ @flurrywong @FordAntiTrust ฮะ <3

วาเลนไทน์

วาเลนไทน์ที่ผ่านมาไปสอบสัมภาษณ์ป.โท วิศวะคอม มก. (อาจารย์ที่สอบสัมภาษณ์เค้าก็เข้าใจเลือกวันเนาะ)

ตกใจนิดหน่อยที่สอบเข้าได้ที่ 1 (ได้ 69%) ทั้งที่ไม่ได้อ่านหนังสือสอบเลย อาจารย์บอกว่าได้คะแนนคณิตศาสตร์เยอะดี สมกับที่เรียนคณิตศาสตร์มา 555+

• คณิตศาสตร์: 18/25 => 21% จาก 30% เห็นตอนแรกบอกจะมี 50 ข้อ เปิดเจอแค่ 25 ข้อค่อยโล่งใจหน่อย
• ภาษาอังกฤษ: 32/50 => 19% จาก 30% เสียดายที่ทำไม่ทัน ทิ้งดิ่งเยอะมาก
• ความรู้คอมฯ: 3x/50 => 29% จาก 40% คำถามเชิงลึกกระจายหลายหัวข้อมาก มาอ่านเอาสัปดาห์เดียวไม่น่าได้

แต่เรื่องสอบอ่ะ มันไม่ได้ดีใจเท่าของรางวัลที่ได้ในวันรุ่งขึ้นหรอก <3