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

2 comments:

sugree said...

โอย โอย โอย ลืมไปว่ามันตัด span กับ div ทิ้ง ใส่เพิ่มให้แล้วครับ

iporsut said...

เข้าใจง่ายดีจริงๆพี่
เจอโค้ดแบบของคุณ bow ที่ใช้ python
ผมงงตาย