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"
"********"
"       *"
"****** *"
"*    * *"
"* *  * *"
"* **** *"
"*      *"
"********"