Friday, March 07, 2008

snail-shell

เมื่อวานนั่งเขียนโจทย์เกี่ยวกับ shell-snail ใน codenone ด้วย Haskell
แต่ใน codenone มันทำ syntax highlight ไม่ได้
ก็เลยมาขอฉายซ้ำใน blog อีกที

เริ่มจากโจทย์ก่อน
ให้เขียนโปรแกรมที่รับค่า N และนำมา plot graph ให้ได้ตามนี้

กรณี N=3
***
*
***

กรณี N=4
****
*
* *
****

กรณี N=5
*****
*
*** *
* *
*****

กรณี N=6
******
*
**** *
* * *
* *
******


คิดจะเขียนโปรแกรมด้วย Haskell ก็ต้องคิดแบบ recursive เป็นหลัก
จะเห็นว่าที่ dimension N ใดๆ จะมี sub picture ที่ (N-2) ซ้อนอยู่ในนั้นด้วย
แต่จะซ้อนอยู่ในลักษณะกลับหัวกลับหาง (คือ flip ทาง horizontal ที่หนึ่งก่อน แล้วค่อย flip ทาง vertical อีกที)

ลองดูรูป N=6 จะเห็นว่าเกิดจาก

N=4

****
*
* *
****

กลับหัวกลับหางเป็น

****
* *
*
****

แล้วนำไปซ้อนกับรูป พื้นฐาน ที่ N=6

******
*
*
*
*
******


ดังนั้น นิยามของรูปของเราก็คือ

รูป N = (รูป (N-2) กลับหัวกลับหาง) ซ้อนกับ รูปพื้นฐาน N

เขียนเป็น function ได้ว่า

pic n = (flip_all (pic n-2)) `over` base n


เนื่องจากโปรแกรมเราเป็น recursive ดังนั้นมันก็ต้องมี รูปที่เป็นจุดเริ่มต้นให้มันด้วย
ซึ่งในกรณีนี้ก็คือ N=1 และ N=2
pic 1 = ["*"]
pic 2 = ["**"," *"]
pic n = (flip_all (pic n-2)) `over` base n

นิยามของ base n ก็ง่ายๆนั่นคือ
เอา '****' มาประกบหัวและหางเข้ากับ ' *'
โดยมีความกว้างและความสูงเท่ากับค่า N
-- base 3 = ["***",
-- " *",
-- "***"]
--
-- base 4 = ["****",
-- " *",
-- " *",
-- "****"]
--
-- for n = 4
-- hbar = "****"
-- rbar = " *"
--
base n = [hbar] ++ (replicate (n-2) rbar) ++ [hbar]
where hbar = replicate n '*'
rbar = (replicate (n-1) ' ') ++ ['*']

function ถัดไปก็คือ flip_all
ซึ่งเกิดจาก flip_vertical compose กับ flip_horizontal
--
--render $ flip_horizontal $ pic 4
--
-- "****"
-- "* "
-- "* *"
-- "****"
flip_vertical = reverse
flip_horizontal = map reverse
flip_all = flip_vertical . flip_horizontal

function ที่ดูจะยุ่งยากสุด ก็คือ function ที่ใช้วางรูปซ้อนกัน
เพื่อความง่ายในการซ้อน เราเลยเพิ่ม helper function ที่ใช้ในการปรับขนาดรูปให้เท่ากันเสียก่อน
ก่อนที่จะนำมาซ้อนกัน
-- patch (base 3) 5 = ["     ",
-- " ",
-- "*** ",
-- " * ",
-- "*** "]
--
patch xs n = replicate diff blankline ++
[ x ++ (replicate diff ' ') | x <- xs]
where blankline = replicate n ' '
diff = n - (length xs)


-- ["****", [" ", ["****",
-- " *", over "*** ", => "****",
-- " *", "* ", "* *",
-- "****"] "*** "] "****"]
--
over xs ys = zipWith over' xs ys
where over' linex liney = zipWith over'' linex liney
over'' x y | x == ' ' = y
| otherwise = x

ปรับนิยาม pic ของเราให้ใช้ patch function ช่วยปรับขนาดก่อนวางทาบกัน
pic 1 = ["*"]
pic 2 = ["**"," *"]
pic n = (patch (flip_all $ pic (n-2)) n) `over` base n


ส่วนการ render นั้นมันมีเรื่อง IO มาเกี่ยวข้องด้วย
ก็ต้องใช้ function พวก mapM (M มาจาก Monad) เข้ามาช่วย
render n = do 
print $ "N = " ++ (show n)
mapM print (pic n)


ลองสั่ง run ดู
*Main> mapM render [1..8]
"N = 1"
"*"
"N = 2"
"**"
" *"
"N = 3"
"***"
" *"
"***"
"N = 4"
"****"
" *"
"* *"
"****"
"N = 5"
"*****"
" *"
"*** *"
"* *"
"*****"
"N = 6"
"******"
" *"
"**** *"
"* * *"
"* *"
"******"
"N = 7"
"*******"
" *"
"***** *"
"* * *"
"* *** *"
"* *"
"*******"
"N = 8"
"********"
" *"
"****** *"
"* * *"
"* * * *"
"* **** *"
"* *"
"********"

Related link from Roti

Wednesday, March 05, 2008

Yak shaving

"Yak shaving" is a programmer's slang term for the distance between a task's start and completion and the tangential tasks between you and the solution. If you ever wanted to mail a letter, but couldn't find a stamp, and had to drive your car to get the stamp, but also needed to refill the tank with gas, which then let you get to the post office where you could buy a stamp to mail your letter—then you've done some yak shaving.


อันนี้เป็นอีกนิยามหนึ่ง

Any seemingly pointless activity which is actually necessary to solve a problem which solves a problem which, several levels of recursion later, solves the real problem you're working on.


สำหรับผม บางครั้ง Yak shaving ีมันก็สนุก จนอดใจที่จะไม่ลงไปแตะไม่ได้

ช่วงนี้ใช้ python เขียน script สำหรับ deploy java applicaion บน cluster อยู่
มันมี Yak shaving น้อยดี

Related link from Roti