Open Source WEB

今月の一行

2006-07-31 [Haskell] 入試問題(その10)

http://www.i.u-tokyo.ac.jp/edu/course/ci/pdf/ci-2006-programming-2nd.pdf の最後の問題，問題 4 にも挑戦してみよう．

この問題は付け加えられたルールがちょっと解りにくい． セルが削除された場合，インデックスの大きい側から詰めるとするのが簡単だが，

ただし，c0 が削除された場合は，もとの cn-1 つまり左のセルが c0 の位置 に入る．

とある．このただし書きは，c0を特別扱いすることが意図だと解釈すると． 関数 extrarule :: CellSpace -> CellSpace は 

-- Problem 4

extrarule :: CellSpace -> CellSpace
extrarule cs
 = case grouping cs of
     (n,gs@(g:_)) -> case n of
                       -1 -> cs'
                       0  -> if length g >= 3
                               then case head g of
                                      0 -> rotateL 1 cs'
                                      1 -> rotateR 1 cs' -- c0を特別扱い
                               else cs' 
                       _  -> rotateR n cs'
                     where cs' = concatMap add0del1 gs

grouping :: [Int] -> (Int, [[Int]])
grouping xs 
 = if ngs == 1 
     then (-1, gs)
     else if even ngs 
            then (0, gs)
            else case splitAt (ngs - 1) gs of
                   (hg:gs,[lg]) -> (length hg, gs++[lg++hg])
   where gs  = group xs
         ngs = length gs

add0del1 :: [Int] -> [Int]
add0del1 xs@(0:_) = if length xs >= 3 then 0:xs else xs
add0del1 xs@(1:_) = if length xs >= 3 then tail xs else xs

ただし書きを無視すると，extrarule 関数の定義は 

extrarule :: CellSpace -> CellSpace
extrarule cs
 = case grouping cs of
     (n,gs@(g:_)) -> case n of
                       -1 -> cs'
                       0  -> if length g >= 3
                               then case head g of
                                      0 -> rotateL 1 cs'
                                      1 -> cs' -- 但し書きを無視
                               else cs' 
                       _  -> rotateR n cs'
                     where cs' = concatMap add0del1 gs

となる．ううむ．

--nobsun

Name:
Comment:

There is no comment.

2006-07-28 [Haskell] 入試問題(その 9)

よおーし．3-3 にいってみよう． 

-- Problem 3-3

cs33 :: CellSpace            -- 問題 3-3 の初期セル空間
cs33 = take 860 $ concat $ iterate (0:) [0,1]

m33 :: StateFun              -- 問題 3-3 状態遷移関数
m33 = gen 129

a33 :: IO ()                 -- 問題 3-3 セル空間状態遷移の表示
a33 = printTransition 860 51 $ iterate (trans m33) cs33

a33 を評価すると．(かなり横に長いけど．．．) 

.#..#...#....#.....#......#.......#........#.........#..........#...........#............#.............#..............#...............#................#.................#..................#...................#....................#.....................#......................#.......................#........................#.........................#..........................#...........................#............................#.............................#..............................#...............................#................................#.................................#..................................#...................................#....................................#.....................................#......................................#.......................................#........................................#
......#...##...###...####...#####...######...#######...########...#########...##########...###########...############...#############...##############...###############...################...#################...##################...###################...####################...#####################...######################...#######################...########################...#########################...##########################...###########################...############################...#############################...##############################...###############################...################################...#################################...##################################...###################################...####################################...#####################################...######################################..
#####...#....#..#..#..##..#..###..#..####..#..#####..#..######..#..#######..#..########..#..#########..#..##########..#..###########..#..############..#..#############..#..##############..#..###############..#..################..#..#################..#..##################..#..###################..#..####################..#..#####################..#..######################..#..#######################..#..########################..#..#########################..#..##########################..#..###########################..#..############################..#..#############################..#..##############################..#..###############################..#..################################..#..#################################..#..##################################..#..###################################..#..####################################..#
####..#...##..................#.......##.......###.......####.......#####.......######.......#######.......########.......#########.......##########.......###########.......############.......#############.......##############.......###############.......################.......#################.......##################.......###################.......####################.......#####################.......######################.......#######################.......########################.......#########################.......##########################.......###########################.......############################.......#############################.......##############################.......###############################.......################################.......#################################.......##################################....
.##.....#....################...#####....#####..#..#####..##..#####..###..#####..####..#####..#####..#####..######..#####..#######..#####..########..#####..#########..#####..##########..#####..###########..#####..############..#####..#############..#####..##############..#####..###############..#####..################..#####..#################..#####..##################..#####..###################..#####..####################..#####..#####################..#####..######################..#####..#######################..#####..########################..#####..#########################..#####..##########################..#####..###########################..#####..############################..#####..#############################..#####..##############################..#####..###############################..#####..################################..##.
....###...##..##############..#..###..##..###.......###........###....#....###....##....###....###....###....####....###....#####....###....######....###....#######....###....########....###....#########....###....##########....###....###########....###....############....###....#############....###....##############....###....###############....###....################....###....#################....###....##################....###....###################....###....####################....###....#####################....###....######################....###....#######################....###....########################....###....#########################....###....##########################....###....###########################....###....############################....###....#############################....###....##############################......
###..#..#......############.......#........#..#####..#..######..#..##...##..#..##....##..#..##..#..##..#..##..##..##..#..##..###..##..#..##..####..##..#..##..#####..##..#..##..######..##..#..##..#######..##..#..##..########..##..#..##..#########..##..#..##..##########..##..#..##..###########..##..#..##..############..##..#..##..#############..##..#..##..##############..##..#..##..###############..##..#..##..################..##..#..##..#################..##..#..##..##################..##..#..##..###################..##..#..##..####################..##..#..##..#####################..##..#..##..######################..##..#..##..#######################..##..#..##..########################..##..#..##..#########################..##..#..##..##########################..##..#..##..###########################..##..#..##..############################..#####
##........####..##########..#####...######.....###.......####.........#...........##..........................................#...............##...............###...............####...............#####...............######...............#######...............########...............#########...............##########...............###########...............############...............#############...............##############...............###############...............################...............#################...............##################...............###################...............####################...............#####################...............######################...............#######################...............########################...............#########################...............##########################....####
#..######..##....########....###..#..####..###..#..#####..##..#######...#########....########################################...#############....#############..#..#############..##..#############..###..#############..####..#############..#####..#############..######..#############..#######..#############..########..#############..#########..#############..##########..#############..###########..#############..############..#############..#############..#############..##############..#############..###############..#############..################..#############..#################..#############..##################..#############..###################..#############..####################..#############..#####################..#############..######################..#############..#######################..#############..########################..##..###
....####......##..######..##..#.......##....#.......###........#####..#..#######..##..######################################..#..###########..##..###########.......###########........###########....#....###########....##....###########....###....###########....####....###########....#####....###########....######....###########....#######....###########....########....###########....#########....###########....##########....###########....###########....###########....############....###########....#############....###########....##############....###########....###############....###########....################....###########....#################....###########....##################....###########....###################....###########....####################....###########....#####################....###########....######################........##
.##..##..####......####.........#####....##...#####..#..######..###.......#####........####################################.......#########........#########..#####..#########..######..#########..##...##..#########..##....##..#########..##..#..##..#########..##..##..##..#########..##..###..##..#########..##..####..##..#########..##..#####..##..#########..##..######..##..#########..##..#######..##..#########..##..########..##..#########..##..#########..##..#########..##..##########..##..#########..##..###########..##..#########..##..############..##..#########..##..#############..##..#########..##..##############..##..#########..##..###############..##..#########..##..################..##..#########..##..#################..##..#########..##..##################..##..#########..##..###################..##..#########..##..####################..######...
..........##..####..##..#######..###..##....#..###.......####....#..#####..###..######..##################################..#####..#######..######..#######....###....#######....####....#######......#......#######......##......#######...............#######................#######........#........#######........##........#######........###........#######........####........#######........#####........#######........######........#######........#######........#######........########........#######........#########........#######........##########........#######........###########........#######........############........#######........#############........#######........##############........#######........###############........#######........################........#######........#################........#######........##################....####..##
.########......##........#####....#......##.....#..#####..##..##.....###....#....####....################################....###....#####....####....#####..##..#..##..#####..##..##..##..#####..####...####..#####..####....####..#####..#############..#####..##############..#####..######...######..#####..######....######..#####..######..#..######..#####..######..##..######..#####..######..###..######..#####..######..####..######..#####..######..#####..######..#####..######..######..######..#####..######..#######..######..#####..######..########..######..#####..######..#########..######..#####..######..##########..######..#####..######..###########..######..#####..######..############..######..#####..######..#############..######..#####..######..##############..######..#####..######..###############..######..#####..######..################..##..##.....
..######..####....######..###..##...####....###.....###..........###..#..##...##..##..##..##############################..##..#..##..###..##..##..##..###...............###................###....##..#..##....###....##..##..##....###....###########....###....############....###....####..#..####....###....####..##..####....###....####.......####....###....####........####....###....####....#....####....###....####....##....####....###....####....###....####....###....####....####....####....###....####....#####....####....###....####....######....####....###....####....#######....####....###....####....########....####....###....####....#########....####....###....####....##########....####....###....####....###########....####....###....####....############....####....###....####....#############....####....###....####....##############..........####
...####....##..##..####....#......#..##..##..#..###..#..########..#.........#..............############################...............#................#..#############..#..##############..#..##...........##..#..##............##..#..##..#########..##..#..##..##########..##..#..##..##.......##..##..#..##..##........##..##..#..##..##..#####..##..##..#..##..##..######..##..##..#..##..##..##...##..##..##..#..##..##..##....##..##..##..#..##..##..##..#..##..##..##..#..##..##..##..##..##..##..##..#..##..##..##..###..##..##..##..#..##..##..##..####..##..##..##..#..##..##..##..#####..##..##..##..#..##..##..##..######..##..##..##..#..##..##..##..#######..##..##..##..#..##..##..##..########..##..##..##..#..##..##..##..#########..##..##..##..#..##..##..##..##########..##..##..##..#..##..##..##..###########..##..##..##..#..##..##..##..############..########..##.
##..##..##..........##..##...####................#.......######.....#######...############..##########################..#############...##############.....###########.......############.........#########...........##########.............#######...............########.................#####...................######.....................###.......................####.........................#...........................##..........................................................................................#...............................##...............................###...............................####...............................#####...............................######...............................#######...............................########...............................#########...............................##########....######......
...........########........#..##..##############...#####..####..###..#####..#..##########....########################....###########..#..############..###..#########..#####..##########..#######..#######..#########..########..###########..#####..#############..######..###############..###..#################..####..###################..#..#####################..##..#######################...#########################....########################################################################################...#############################....#############################..#..#############################..##..#############################..###..#############################..####..#############################..#####..#############################..######..#############################..#######..#############################..########..##..####..####.
##########..######..######.........############..#..###....##....#....###.......########..##..######################..##..#########.......##########....#....#######....###....########....#####....#####....#######....######....#########....###....###########....####....#############....#....###############....##....#################.......###################........#####################..#..#######################..##..######################################################################################..#..###########################..##..###########################.......###########################........###########################....#....###########################....##....###########################....###....###########################....####....###########################....#####....###########################....######........##....##..
.########....####....####..#######..##########.......#..##....##...##..#..#####..######........####################........#######..#####..########..##...##..#####..##..#..##..######..##..###..##..###..##..#####..##..####..##..#######..##..#..##..#########..##..##..##..###########..##...##..#############..##....##..###############..#####..#################..######..###################.......#####################........####################################################################################.......#########################........#########################..#####..#########################..######..#########################..##...##..#########################..##....##..#########################..##..#..##..#########################..##..##..##..#########################..##..###..##..#########################..##..####..######....##.....
..######..##..##..##..##....#####....########..#####.......##....#.........###....####..######..##################..######..#####....###....######......#......###...............####........#........#........###........##........#####...............#######................#########......#......###########......##......#############....###....###############....####....#################..#####..###################..######..##################################################################################..#####..#######################..######..#######################....###....#######################....####....#######################......#......#######################......##......#######################...............#######################................#######################........#........#######################........##....####..##....####
...####..................##..###..##..######....###..#####....##...#######..#..##..##....####....################....####....###..##..#..##..####..####...####..#..#############..##..######...######...######..#..######....######..###..#############..#####..##############..#######..####...####..#########..####....####..###########..##..#..##..#############..##..##..##..###############....###....#################....####....################################################################################....###....#####################....####....#####################..##..#..##..#####################..##..##..##..#####################..####...####..#####################..####....####..#####################..#############..#####################..##############..#####################..######...######..#####################..######....##..##......##..##.
##..##..################......#........####..##..#....###..##....#..#####.............##..##..##..##############..##..##..##..#...............##....##..#..##.......###########........####..#..####..#..####.......####..##..####....#....###########....###....############....#####....##..#..##....#######....##..##..##....#########...............###########................#############..##..#..##..###############..##..##..##..##############################################################################..##..#..##..###################..##..##..##..###################...............###################................###################....##..#..##....###################....##..##..##....###################....###########....###################....############....###################....####..#..####....###################....####..##........####........
.........##############..####...######..##.........##..#......##.....###..###########..............############.................#############....##...........#####..#########..######..##.......##.......##..#####..##........##..##...##..#########..##..#..##..##########..##..###..##...........##..#####..##............##..#######..#############..#########..##############..###########...............#############................############################################################################...............#################................#################..#############..#################..##############..#################..##...........##..#################..##............##..#################..##..#########..##..#################..##..##########..##..#################..##..##.......##..##..#################..##..##......######..##..######.
########..############....##..#..####......#######.......####....###..#....#########..############..##########..###############..###########..##....#########..###....#######....####......#####....#####......###......######........#......#######...............########........#......#########......###......##########......#####....###########....#######....############....#########..#############..###########..##############..##########################################################################..#############..###############..##############..###############....###########....###############....############....###############......#########......###############......##########......###############........#######........###############........########........###############..........#####..........###############..........####..####........####..
.######....##########..##.........##..####..#####..#####..##..##..#.....##..#######....##########....########....#############....#########......##..#######....#..##..#####..##..##..####..###..##..###..####..#..####..####..######...####..#####..#############..######..######...####..#######..####..#..####..########..####..###..##..#########..##..#####..##..##########..##..#######....###########....#########....############....########################################################################....###########....#############....############....#############..##..#########..##..#############..##..##########..##..#############..####..#######..####..#############..####..########..####..#############..######..#####..######..#############..######..######..######..#############..########..###..########..#############..########..##....##..######..##...
..####..##..########......#######......##....###....###.............###......#####..##..########..##..######..##..###########..##..#######..####......#####..##.........###............##....#........#....##.......##....##....####..#..##....###....###########....####....####..#..##....#####....##.......##....######....##....#........#######........###........########........#####..##..#########..##..#######..##..##########..##..######################################################################..##..#########..##..###########..##..##########..##..###########........#######........###########........########........###########....##....#####....##....###########....##....######....##....###########....####....###....####....###########....####....####....####....###########....######....#....######....###########....######......##......####......##
...##........######..####..#####..####....##..#..##..#..###########..#..####..###........######........####........#########........#####....##..####..###......#######..#..##########....##...######...##....#####....##....##..##.........##..#..##..#########..##..##..##..##.........##..###..##....#####....##..####..##....##...######..#####..######..#..######..######..######..###........#######........#####........########........####################################################################........#######........#########........########........#########..######..#####..######..#########..######..######..######..#########..##....##..###..##....##..#########..##....##..####..##....##..#########..##..##..##..#..##..##..##..#########..##..##..##..##..##..##..##..#########..##..####..##...##..####..##..#########..##..####..####....####..##..####...
##....######..####....##....###....##..##................#########.......##....#..######..####..######..##..######..#######..######..###..##......##....#..####..#####.......########..##....#..####..#....##..###..##....##........#######.............#######..................#######......#......##..###..##......##......##....#..####....###....####.......####....####....####....#..######..#####..######..###..######..######..######..##################################################################..######..#####..######..#######..######..######..######..#######....####....###....####....#######....####....####....####....#######......##......#......##......#######......##......##......##......#######...............................#######................................#######........##......#......##........#######........##....##..##..##........##..##
#..##..####....##..##....##..#..##........##############..#######..#####....##.....####....##....####........####....#####....####....#......####....##.....##....###..#####..######......##.....##.....##......#......##....######..#####..###########..#####..################..#####..####...####......#......####....####....##.....##..##..#..##..##..#####..##..##..##..##..##..##.....####....###....####....#....####....####....####....################################################################....####....###....####....#####....####....####....####....#####..##..##..##..#..##..##..##..#####..##..##..##..##..##..##..##..#####..####....####...####....####..#####..####....####....####....####..#####..#############################..#####..##############################..#####..######....####...####....######..#####..######....##............######......#
........##..##........##...........######..############....#####....###..##....###..##..##....##..##..######..##..##..###..##..##..##...####..##..##....###....##..#....###....####..####....###....###....####...####....##..####....###....#########....###....##############....###....##..#..##..####...####..##..##..##..##....###.....................###..........................###..##..##..#..##..##..##...##..##..##..##..##..##..##..##############################################################..##..##..##..#..##..##..##..###..##..##..##..##..##..##..##..###...............................###................................###....##..##..##..#..##..##..##....###....##..##..##..##..##..##..##....###....###########################....###....############################....###....####..##..##..#..##..##..####....###....####..##....##########..####..####..
#######........######....#########..####....##########..##..###..##..#......##..#..........##..........####............#..............#..##..........##..#..##.......##..#..##..##....##..##..#..##..#..##..##..#..##..##......##..##..#..##..#######..##..#..##..############..##..#..##.............##..#..##..................##..#..###################..#..########################..#.........................#..............................############################################################...............................#................................#..#############################..#..##############################..#..##...........................##..#..##............................##..#..##..#########################..##..#..##..##########################..##..#..##..##.......................##..##..#..##..##......##..########....##....##..#
######..######..####..##..#######....##..##..########........#.........####.......########....########..##..##########...############.......########...........#####...............##.....................................####.................#####...............##########.............###########...........################.........#################.......######################.....#######################...############################..##########################################################..#############################...##############################.....###########################.......############################.........#########################...........##########################.............#######################...............########################.................#####################...................####......######..##....##......
.####....####....##........#####..##..........######..######...#######..##..#####..######..##..######........########..#..##########..#####..######..#########..###..#############....###################################..##..###############..###..#############..########..###########..#########..#########..##############..#######..###############..#####..####################..###..#####################..#..##########################....########################################################....###########################..#..############################..###..#########################..#####..##########################..#######..#######################..#########..########################..###########..#####################..#############..######################..###############..###################..#################..##..####..####......##....####.
..##..##..##..##....######..###......########..####....####..#..#####........###....####........####..######..######.......########....###....####....#######....#....###########..##..#################################........#############....#....###########....######....#########....#######....#######....############....#####....#############....###....##################....#....###################.......########################..##..######################################################..##..#########################.......##########################....#....#######################....###....########################....#####....#####################....#######....######################....#########....###################....###########....####################....#############....#################....###############........##....##..####....##..##..
#................##..####....#..####..######....##..##..##.......###..######..#..##..##..######..##....####....####..#####..######..##..#..##..##..##..#####..##...##..#########........###############################..######..###########..##...##..#########..##..####..##..#######..##..#####..##..#####..##..##########..##..###..##..###########..##..#..##..################..##...##..#################..#####..######################........####################################################........#######################..#####..########################..##...##..#####################..##..#..##..######################..##..###..##..###################..##..#####..##..####################..##..#######..##..#################..##..#########..##..##################..##..###########..##..###############..##..#############..######....##......##..##........#
..##############......##..##.....##....####..##............#####..#....####...............####......##..##..##..##....###....####.......................###......#......#######..######..#############################....####....#########......#......#######........##........#####........###........###........########........#........#########...............##############......#......###############....###....####################..######..##################################################..######..#####################....###....######################......#......###################...............####################........#........#################........###........##################........#####........###############........#######........################........#########........#############........###########....####..##....####........######..
#..############..####........###....##..##......##########..###.....##..##..#############..##..####................##..#..##..##..#####################..#..####...####..#####....####....###########################..##..##..##..#######..####...####..#####..######....######..###..######..#..######..#..######..######..######...######..#######..#############..############..####...####..#############..##..#..##..##################....####....################################################....####....###################..##..#..##..####################..####...####..#################..#############..##################..######...######..###############..######..#..######..################..######..###..######..#############..######..#####..######..##############..######..#######..######..###########..######..#########..##..##......##..##..######..####..#
....##########....##..######..#..##........####..########....#..###..........###########........##..##############.................###################.......##..#..##....###..##..##..##..#########################................#####....##..#..##....###....####..##..####....#....####.......####.......####....####....####..#..####....#####....###########....##########....##..#..##....###########...............################..##..##..##..##############################################..##..##..##..#################...............##################....##..#..##....###############....###########....################....####..#..####....#############....####.......####....##############....####....#....####....###########....####....###....####....############....####....#####....####....#########....####....#######..........####..........####....##....
###..########..##......####.........######..##....######..##.....#..########..#########..######......############..###############..#################..#####...........##..#................#######################..##############..###..##...........##..#..##..##........##..##...##..##..#####..##..#####..##..##..##..##..##.......##..##..###..##..#########..##..########..##...........##..#########..#############..##############................############################################................###############..#############..################..##...........##..#############..##..#########..##..##############..##..##.......##..##..###########..##..##..#####..##..##..############..##..##..##...##..##..##..#########..##..##..##..#..##..##..##..##########..##..##..##..###..##..##..##..#######..##..##..##..#####..########..##..########..##..##....###
##....######......####..##..#######..####......##..####......###.....######....#######....####..####..##########....#############....###############....###..#########.......##############..#####################....############....#......#########...............######........#..........###........###......................#####..........#........#######........######......#########......#######....###########....############..##############..##########################################..##############..#############....###########....##############......#########......###########........#######........############..........#####..........#########............###............##########..............#..............#######...............................########................#................#####................###....######........######..........##..##
#..##..####..####..##........#####....##..####......##..####..#..###..####..##..#####..##..##....##....########..##..###########..##..#############..##..#....#######..#####..############....###################..##..##########..##...####..#######..#############..####..######...########..#..######..#..####################..###..########...######..#####..######..####..####..#######..####..#####..##..#########..##..##########....############....########################################....############....###########..##..#########..##..############..####..#######..####..#########..######..#####..######..##########..########..###..########..#######..##########..#..##########..########..############...############..#####..#############################..######..##############...##############..###..##############..#..##..####..######..####..########......#
........##....##......######..###..##......##..####......##.......#....##........###..........##....##..######........#########........###########.........##..#####....###....##########..##..#################........########......#..##....#####....###########....##....####..#..######.......####.......##################....#....######..#..####....###....####....##....##....#####....##....###........#######........########..##..##########..##..######################################..##..##########..##..#########........#######........##########....##....#####....##....#######....####....###....####....########....######....#....######....#####....########.......########....######....##########..#..##########....###....###########################....####....############..#..############....#....############...........##....####....##....######..####..
#######....##....####..####....#......####......##..####....#####...##....######..#..########....##......####..######..#######..######..#########..#######......###..##..#..##..########........###############..######..######..####.......##..###..##..#########..##....##..##.......####..#####..##..#####..################..##...##..####.......##..##..#..##..##..##....##....##..###..##....##..#..######..#####..######..######........########........####################################........########........#######..######..#####..######..########..##....##..###..##....##..#####..##..##..##..#..##..##..##..######..##..####..##...##..####..##..###..##..######..#####..######..##..####..##..########.......########..##..#..##..#########################..##..##..##..##########.......##########..##...##..##########..#########....##..##..##....##..####....##..#
######..##....##..##....##..##...####..##..####......##..##..###..#....##..####.......######..##....####..##....####....#####....####....#######....#####..####..#...............######..######..#############....####....####....##..#####......#........#######......##........#####..##....###........###....##############......#......##..#####.......................##....##......#......##.........####....###....####....####..######..######..######..##################################..######..######..######..#####....####....###....####....######......##......#......##......###...............................####........##......#......##........#........####....###....####........##........######..#####..######...............#######################................########..#####..########......#......########....#######..##............##......##..##......
.####......##........##........#..##........##..####..........#.....##......##..#####..####......##..##......##..##..##..###..##..##..##..#####..##..###....##.....#############..####....####....###########..##..##..##..##..##......###..####...######..#####..####....######..###......##..#..######..#..##..############..####...####......###..#####################....##....####...####....#######..##..##..#..##..##..##..##....####....####....####....################################....####....####....####....###..##..##..##..#..##..##..##..####..####....####...####....####..#..#############################..##..######....####...####....######...######..##..##..#..##..##..######....######..####....###....####..#############..#####################..##############..######....###....######..####...####..######..##..#####......##########....####........####.
..##..####....######....######.......######......##..########...###....####......###....##..####........####..............#................###........#..##....###..###########....##..##..##..##..#########......................####..#....##..#..####....###....##..##..####....#..####.........####...........##########....##..#..##..####..#....###################..##....##..##..#..##..##..#####.............................##..##..##..##..##..##..##..##############################..##..##..##..##..##..##..##..#...............................##....##..##..##..#..##..##..##.......###########################........####..##..##..#..##..##..####..#..####.......................####..##..####....##..##..#..##..##....###########....###################....############....####..##..#..##..####....##..#..##....####........###..####..########..##..##..######..##..
#......##..##..####..##..####..#####..####..####......######..#..#..##..##..####..#..##......##..######..##..############...##############..#..######.......##..#....#########..##..................#######..####################..##.....##.........##..##..#..##..........##..##.....##..#######..##..#########..########..##.............##.....##..#################......##.....................###..###########################..............................############################.................................#############################....##...........................#####..#########################..######..##.......................##.......##..#####################..##........##..##...................##..#########..##..#################..##..##########..##..##...............##..##...........##..##..######..#....##....######............####......#
..####..........##........##....###....##....##..####..####..................##.........####......####........##########..#..############.......####..#####.......##..#######......################..#####....##################......###....#######...............########........###......#####........#######....######......###########....###......###############..####....###################..#....#########################..############################..##########################..###############################..###########################..##....#########################..###....#######################....####......#####################....#####......###################......######........#################......#######........###############........########..........#############........#########..........####.....##....##..####..##########..##..####..
#..##..########....######....##..#..##....##......##....##..################....#######..##..####..##..######..########.......##########..#####..##....###..#####......#####..####..##############....###..##..################..####..#..##..#####..#############..######..######..#..####..###..######..#####..##..####..####..#########..##..#..####..#############....##..##..#################.....##..#######################....##########################....########################....#############################....#########################......##..#######################....#..##..#####################..##..##..####..###################..##..###..####..#################..####..####..######..###############..####..#####..######..#############..######..######..########..###########..######..#######..########..##..###....##......##....########........##..#
........######..##..####..##...........##....####....##......##############..##..#####........##........####....######..#####..########....###......##..#....###..####..###....##....############..##..#........##############....##...........###....###########....####....####.......##....#....####....###........##....##....#######...........##....###########..##..........###############..###......#####################..##..########################..##..######################..##..###########################..##..#######################..####......#####################..##.........###################............##....#################........#....##....###############....##....##....####....#############....##....###....####....###########....####....####....######....#########....####....#####....######........#..##....####....##..######..######......
#######..####........##......#########....##..##..##....####..############........###..######....######..##..##..####....###....######..##..#..####.......##..#....##....#..##....##..##########.........######..############..##....#########..#..##..#########..##..##..##..##..#####....##...##..##..##..#..######....##....##..#####..#########....##..#########......########..#############....#..####..###################........######################........####################........#########################........#####################....##..####..###################......#######..#################..##########....##..###############..######...##....##..#############..##....##....##..##..##..###########..##....##..#..##..##..##..#########..##..##..##..##..##..####..##..#######..##..##..##..###..##..####..######.......##..##..##......####....####..#####

うわぁーっ．すごい．面白い．

--nobsun

Name:
Comment:

There is no comment.

2006-07-27 [Haskell] 入試問題(その 8)

3-1 は美しい絵が出た．では 3-2 はどうだろう． 

-- Problem 3-2

cs32 :: CellSpace                -- 問題 3-2 の初期セル空間
cs32 = take 123 [ if count n == 3 then 1 else 0 | n <- [0..] ]

count :: Int -> Int              -- 整数を二進数表示したときの1の数
count n = sum $ map snd $ takeWhile ((0,0)/=) $ iterate f dm
  where dm      = divMod n 2
        f (d,_) = divMod d 2

m32 :: StateFun                  -- 問題 3-2 状態遷移関数
m32 = gen 99

a32 :: IO ()                     -- 問題 3-2 セル空間遷移の表示
a32 = printTransition 123 51 $ iterate (trans m32) cs32

a32 を評価すると 

*Main> a32
.......#...#.##....#.##..##.#......#.##..##.#....##.#...#..........#.##..##.#....##.#...#........##.#...#.......#..........
#######..##.#.#.###.#.#.#.##..#####.#.#.#.##..###.##..##..#########.#.#.#.##..###.##..##..#######.##..##..######..#########
......#.#.##.#.#..##.#.#.#.#.#....##.#.#.#.#.#..##.#.#.#.#........##.#.#.#.#.#..##.#.#.#.#......##.#.#.#.#.....#.#.........
######.#.#.##.#..#.##.#.#.#.#..###.##.#.#.#.#..#.##.#.#.#..#######.##.#.#.#.#..#.##.#.#.#..#####.##.#.#.#..####.#..########
.....##.#.#.##..#.#.##.#.#.#..#..##.##.#.#.#..#.#.##.#.#..#......##.##.#.#.#..#.#.##.#.#..#....##.##.#.#..#...##..#........
#####.##.#.#.#.#.#.#.##.#.#..#..#.##.##.#.#..#.#.#.##.#..#..#####.##.##.#.#..#.#.#.##.#..#..###.##.##.#..#..##.#.#..#######
....##.##.#.#.#.#.#.#.##.#..#..#.#.##.##.#..#.#.#.#.##..#..#....##.##.##.#..#.#.#.#.##..#..#..##.##.##..#..#.##.#..#.......
####.##.##.#.#.#.#.#.#.##..#..#.#.#.##.##..#.#.#.#.#.#.#..#..###.##.##.##..#.#.#.#.#.#.#..#..#.##.##.#.#..#.#.##..#..######
...##.##.##.#.#.#.#.#.#.#.#..#.#.#.#.##.#.#.#.#.#.#.#.#..#..#..##.##.##.#.#.#.#.#.#.#.#..#..#.#.##.##.#..#.#.#.#.#..#......
###.##.##.##.#.#.#.#.#.#.#..#.#.#.#.#.##.#.#.#.#.#.#.#..#..#..#.##.##.##.#.#.#.#.#.#.#..#..#.#.#.##.##..#.#.#.#.#..#..#####
..##.##.##.##.#.#.#.#.#.#..#.#.#.#.#.#.##.#.#.#.#.#.#..#..#..#.#.##.##.##.#.#.#.#.#.#..#..#.#.#.#.##.#.#.#.#.#.#..#..#.....
##.##.##.##.##.#.#.#.#.#..#.#.#.#.#.#.#.##.#.#.#.#.#..#..#..#.#.#.##.##.##.#.#.#.#.#..#..#.#.#.#.#.##.#.#.#.#.#..#..#..####
.##.##.##.##.##.#.#.#.#..#.#.#.#.#.#.#.#.##.#.#.#.#..#..#..#.#.#.#.##.##.##.#.#.#.#..#..#.#.#.#.#.#.##.#.#.#.#..#..#..#....
#.##.##.##.##.##.#.#.#..#.#.#.#.#.#.#.#.#.##.#.#.#..#..#..#.#.#.#.#.##.##.##.#.#.#..#..#.#.#.#.#.#.#.##.#.#.#..#..#..#..###
##.##.##.##.##.##.#.#..#.#.#.#.#.#.#.#.#.#.##.#.#..#..#..#.#.#.#.#.#.##.##.##.#.#..#..#.#.#.#.#.#.#.#.##.#.#..#..#..#..#...
.##.##.##.##.##.##.#..#.#.#.#.#.#.#.#.#.#.#.##.#..#..#..#.#.#.#.#.#.#.##.##.##.#..#..#.#.#.#.#.#.#.#.#.##.#..#..#..#..#..##
#.##.##.##.##.##.##..#.#.#.#.#.#.#.#.#.#.#.#.##..#..#..#.#.#.#.#.#.#.#.##.##.##..#..#.#.#.#.#.#.#.#.#.#.##..#..#..#..#..#.#
##.##.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.##.##.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#..#.#.
.##.##.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.##.##.#..#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#..#.#.#
#.##.##.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.##.##..#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#..#.#.#.
.#.##.##.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#..#.#.#.#
#.#.##.##.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#..#.#.#.#.
.#.#.##.##.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#..#.#.#.#.#
#.#.#.##.##.##.##.##.##.#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#..#..#..#..#.#.#.#.#.
.#.#.#.##.##.##.##.##.##.#.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#..#..#..#..#.#.#.#.#.#
#.#.#.#.##.##.##.##.##.##.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#..#..#..#..#.#.#.#.#.#.
.#.#.#.#.##.##.##.##.##.##.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#.#.#..#..#..#..#.#.#.#.#.#.#
#.#.#.#.#.##.##.##.##.##.##.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#.#..#..#..#..#.#.#.#.#.#.#.
.#.#.#.#.#.##.##.##.##.##.##.#.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#..#..#..#..#.#.#.#.#.#.#.#
#.#.#.#.#.#.##.##.##.##.##.##.#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#..#..#..#..#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.##.##.##.##.##.##.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#..#..#..#..#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.##.##.##.##.##.##.#.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#..#..#..#..#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.##.##.##.##.##.##.#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#..#..#..#..#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##.##.##.##.##.##..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#..#..#..#..#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.##.##.##.##.##.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##..#..#..#..#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.##.##.##.##.##.#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.##.##.##.##.##..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

ちょっと目を細めてながめると，パターンが見える？

--nobsun

Name:
Comment:

There is no comment.

2006-07-26 [Haskell] 入試問題(その 7)

では早速，3-1 を解いてみよう． 

-- Problem 3-1

cs31 :: CellSpace    -- 問題 3-1 初期セル空間
cs31 = take 100 [ if n == 40 then 1 else 0 | n <- [0..] ]

m31 :: StateFun      -- 問題 3-1 状態遷移関数
m31 = gen 90

a31 :: IO ()         -- 問題 3-1 セル空間遷移の表示
a31 = printTransition 100 51 $ iterate (trans m31) cs31

a31 を評価すると 

*Main> a31
........................................#...........................................................
.......................................#.#..........................................................
......................................#...#.........................................................
.....................................#.#.#.#........................................................
....................................#.......#.......................................................
...................................#.#.....#.#......................................................
..................................#...#...#...#.....................................................
.................................#.#.#.#.#.#.#.#....................................................
................................#...............#...................................................
...............................#.#.............#.#..................................................
..............................#...#...........#...#.................................................
.............................#.#.#.#.........#.#.#.#................................................
............................#.......#.......#.......#...............................................
...........................#.#.....#.#.....#.#.....#.#..............................................
..........................#...#...#...#...#...#...#...#.............................................
.........................#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#............................................
........................#...............................#...........................................
.......................#.#.............................#.#..........................................
......................#...#...........................#...#.........................................
.....................#.#.#.#.........................#.#.#.#........................................
....................#.......#.......................#.......#.......................................
...................#.#.....#.#.....................#.#.....#.#......................................
..................#...#...#...#...................#...#...#...#.....................................
.................#.#.#.#.#.#.#.#.................#.#.#.#.#.#.#.#....................................
................#...............#...............#...............#...................................
...............#.#.............#.#.............#.#.............#.#..................................
..............#...#...........#...#...........#...#...........#...#.................................
.............#.#.#.#.........#.#.#.#.........#.#.#.#.........#.#.#.#................................
............#.......#.......#.......#.......#.......#.......#.......#...............................
...........#.#.....#.#.....#.#.....#.#.....#.#.....#.#.....#.#.....#.#..............................
..........#...#...#...#...#...#...#...#...#...#...#...#...#...#...#...#.............................
.........#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#............................
........#...............................................................#...........................
.......#.#.............................................................#.#..........................
......#...#...........................................................#...#.........................
.....#.#.#.#.........................................................#.#.#.#........................
....#.......#.......................................................#.......#.......................
...#.#.....#.#.....................................................#.#.....#.#......................
..#...#...#...#...................................................#...#...#...#.....................
.#.#.#.#.#.#.#.#.................................................#.#.#.#.#.#.#.#....................
#...............#...............................................#...............#...................
.#.............#.#.............................................#.#.............#.#.................#
..#...........#...#...........................................#...#...........#...#...............#.
.#.#.........#.#.#.#.........................................#.#.#.#.........#.#.#.#.............#.#
....#.......#.......#.......................................#.......#.......#.......#...........#...
...#.#.....#.#.....#.#.....................................#.#.....#.#.....#.#.....#.#.........#.#..
..#...#...#...#...#...#...................................#...#...#...#...#...#...#...#.......#...#.
.#.#.#.#.#.#.#.#.#.#.#.#.................................#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....#.#.#.#
........................#...............................#...............................#...#.......
.......................#.#.............................#.#.............................#.#.#.#......
......................#...#...........................#...#...........................#.......#.....

おおっ．

--nobsun

Name:
Comment:

There is no comment.

2006-07-25 [Haskell] 入試問題(その 6)

http://www.i.u-tokyo.ac.jp/edu/course/ci/pdf/ci-2006-programming-2nd.pdf の問題 3 にも挑戦してみよう．

その前に，1クロック後のセル空間を計算する関数(trans)と セル空間を表示する関数(showCellSpace)などを定義しておこう． 2006-07-21のプログラムに以下を追加． 

type CellSpace = [Int]

trans :: StateFun -> CellSpace -> CellSpace
trans f cs = map f $ zip3 (rotateR 1 cs) cs (rotateL 1 cs)

rotateL,rotateR :: Int -> CellSpace -> CellSpace
rotateL n xs = take (length xs) $ drop n $ cycle xs
rotateR n xs = rotateL (length xs - n) xs

showCellSpace :: Int -> CellSpace -> String
showCellSpace r cs | between 3 2000 (length cs) = take r $ map cell2char cs
                   | otherwise                  = error "size-out-of-range"
 where cell2char 0 = '.'
       cell2char 1 = '#'
       between l h n = l <= n && n <= h

大きさ 16 のセル空間 [1,0,0,1,1,1,0,1,0,1,0,1,0,1,0,0] を考えよう． これを問1の最初の状態遷移関数 255 で1クロック分遷移させてみよう． 最初が， 

*Main> showCellSpace 16 [1,0,0,1,1,1,0,1,0,1,0,1,0,1,0,0]
"#..###.#.#.#.#.."

遷移後は 

showCellSpace 16 $ trans (gen 255) [1,0,0,1,1,1,0,1,0,1,0,1,0,1,0,0]
"################"

たしかに全部 # になってしまった． 

printTransition :: Int -> Int -> [CellSpace] -> IO ()
printTransition crange trange
  = mapM_ putStrLn . map (showCellSpace crange) . take trange

printTransition では，0 〜 crange-1 番目のセルを 0 〜 trange-1 クロック まで表示する．

さっきのセル空間の遷移関数 240 番による▽sを今度は 0 〜 15 クロックまで 表示してみよう． 

*Main> printTransition 16 16 $ iterate (trans $ gen 240) [1,0,0,1,1,1,0,1,0,1,0,1,0,1,0,0]
#..###.#.#.#.#..
.#..###.#.#.#.#.
..#..###.#.#.#.#
#..#..###.#.#.#.
.#..#..###.#.#.#
#.#..#..###.#.#.
.#.#..#..###.#.#
#.#.#..#..###.#.
.#.#.#..#..###.#
#.#.#.#..#..###.
.#.#.#.#..#..###
#.#.#.#.#..#..##
##.#.#.#.#..#..#
###.#.#.#.#..#..
.###.#.#.#.#..#.
..###.#.#.#.#..#

たしかに状態が右へ動いているのがわかる．

--nobsun

Name:
Comment:

There is no comment.

2006-07-24 [Gauche] srfi-42で、リストを返す関数を使って生成したリストをフラットにする

surfi-42のlist-ecを使うと、リストを返す関数で生成したリストは当然「リストのリスト」になる。 

 gosh> (use srfi-42)
 #<undef>
 gosh> (list-ec (: i 12) (list 0 1))
 ((0 1) (0 1) (0 1) (0 1) (0 1) (0 1) (0 1) (0 1) (0 1) (0 1) (0 1) (0 1))

結果のリストをフラットにしたいときはappend-ecが使える。 

 gosh> (append-ec (: i 12) (list 0 1))
 (0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1)

--yasuyuki

Name:
Comment:

There is no comment.

2006-07-21 [Haskell] 入試問題(その 5)

http://www.i.u-tokyo.ac.jp/edu/course/ci/pdf/ci-2006-programming-2nd.pdf の問題 2-3 も考えた．

関数の返り値のパターンを考えると， 

  (1,1,1) → d0
△(1,1,0) → d1
  (1,0,1) → d2
▲(1,0,0) → d3
△(0,1,1) → d4
  (0,1,0) → d5
▲(0,0,1) → d6
  (0,0,0) → d7

状態遷移関数番号を二進数表記したときの，d1 と d4 および d3 と d6 を入 れ替えてやればよい．

2006-07-20 のプログラムに以下を追加 

swap :: Int -> Int -> [a] -> [a]
swap n m xs = case splitAt n xs of
                (xs',y:ys) -> case splitAt (m-n-1) ys of
                                (ys',z:zs) -> xs'++z:ys'++y:zs

invert :: Int -> Int
invert n = foldl (\ a d -> 2*a+d) 0 $ swap 3 6 $ swap 1 4 $ conv 8 n

もとめる関数は invert である．

check3 は invert した結果が自身と同じかどうかをチェックする関数である． すなわち，左右対称な状態遷移関数の番号かどうかがチェックできる． 

check3 :: Int -> Bool
check3 n = n == invert n

これで全状態遷移関数の番号をフィルターして個数を数えればよい． 

*Main> length $ filter check3 [0..255]
64

確かに 2-2 の結論と同じである．

パチパチ

--nobsun

Name:
Comment:

There is no comment.

2006-07-20 [Haskell] 入試問題(その 4)

http://www.i.u-tokyo.ac.jp/edu/course/ci/pdf/ci-2006-programming-2nd.pdf の問題 2-2 も考えた．

引数のパターンを考えると， 

  (1,1,1)
△(1,1,0)
  (1,0,1)
▲(1,0,0)
△(0,1,1)
  (0,1,0)
▲(0,0,1)
  (0,0,0)

非対称なのは2組，この2組の引数に関数を適用した結果のパターンは 2^2 = 4個 対称な引数は4個あるからこちらに関数を適用した結果のパターンは 2^4 = 16個

左右対称な関数は 4 * 16 = 64 個

これもちょいとプログラムを作ってたしかめることができる． 2006-07-19 のプログラムに以下を追加 

check2 :: StateFun -> Bool
check2 f = f (1,1,0) == f (0,1,1) && f (1,0,0) == f (0,0,1)

この check2 で全状態遷移関数をフィルターして個数を数えれば答えになる． 

*Main> length $ filter check2 $ map gen [0..255]
64

パチパチ

--nobsun

Name:
Comment:

There is no comment.

2006-07-19 [Haskell] 入試問題(その 3)

http://www.i.u-tokyo.ac.jp/edu/course/ci/pdf/ci-2006-programming-2nd.pdf の問題 2-1 も考えた．

引数の和は 0,1,2,3 の 4通りしかないから，2^4 = 16 個

状態遷移関数は要素数8の定義域から要素数2の値域への関数が，256個しか ないのだから，ちょいとプログラムを作ってたしかめることができる．

2006-07-18 のプログラムの先頭で，Data.List モジュール をインポートして 

import Data.List

以下を追加する． 

check1 :: StateFun -> Bool
check1 f = all (1==) $ map (length . nub . map f) arranged

arranged :: [[(Int,Int,Int)]]
arranged = groupBy f $ sortBy g domain
  where f (a,b,c) (p,q,r) = a+b+c == p+q+r
        g (a,b,c) (p,q,r) = compare (a+b+c) (p+q+r)

arranged は domain を和で分類したもの．これに関数を適用して，分類ごとに あたいが一種類であることを確認すればよい(check1).

この check1 で全状態遷移関数をフィルターして個数を数えれば答えになる． 

*Main> length $ filter check1 $ map gen [0..255]
16

パチパチ

--nobsun

Name:
Comment:

There is no comment.

2006-07-18 [Haskell] 入試問題(その 2)

2006-07-14の問題で，状態遷移関数の番号から，実際に 状態遷移関数を構成するプログラムがあると便利かも．というわけで作成して みた． 

type Fun a b = a -> b                        -- 関数

add :: Eq a => a -> b -> Fun a b -> Fun a b  -- 対応の追加
add x y f k = if x == k then y else f k

type StateFun = Fun (Int,Int,Int) Int        -- 状態遷移関数の型

gen :: Int -> StateFun                       -- 状態遷移関数の生成関数
gen n = foldr (uncurry add) (error "out of domain") (zip domain (conv 8 n))

conv :: Int -> Int -> [Int]                  -- 整数の二進数表現
conv d n = reverse $ take d $ map snd $ iterate f dm
  where dm      = divMod n 2
        f (d,_) = divMod d 2

domain :: [(Int,Int,Int)]                    -- 状態遷移関数の定義域
domain =  map (toTriple . conv 3) [7,6..0]
  where toTriple [x,y,z] = (x,y,z)

255 番の状態遷移関数は gen 255 で作れる．これで domain をマップすれば [1,1,1,1,1,1,1,1] なるだろう．また，gen 94 で domain をマップすれば [0,1,0,1,1,1,1,0] になるはず． 

*Main> map (gen 255) domain
[1,1,1,1,1,1,1,1]
*Main> map (gen 94) domain
[0,1,0,1,1,1,1,0]

パチパチ

--nobsun

Name:
Comment:

There is no comment.

2006-07-14 [misc] 入試問題(その 1)

東京大学大学院情報理工学系研究科創造情報学専攻(なんて長いなまえ^^;) では過去の入試問題が公開されている．

http://www.i.u-tokyo.ac.jp/edu/course/ci/pdf/ci-2006-programming-2nd.pdf

問1なら儂でも解けるかも．

  1. 全部が1になるような関数 全部の対応を書くと 
    (1,1,1) → 1
(1,1,0) → 1
(1,0,1) → 1
(1,0,0) → 1
(0,1,1) → 1
(0,1,0) → 1
(0,0,1) → 1
(0,0,0) → 1
    すべての引数の組み合わせで 1 になるのだから，状態遷移関数の全出力のならびは 
    (1,1,1,1,1,1,1,1)
    これを二進数として読めば，状態遷移関数の番号が 255 であることが わかる．
  2. 1クロックで状態が右方向に1セル分移動する関数 全部の対応を書くと 
    (1,1,1) → 1
(1,1,0) → 1
(1,0,1) → 1
(1,0,0) → 1
(0,1,1) → 0
(0,1,0) → 0
(0,0,1) → 0
(0,0,0) → 0
    すべての引数の組み合わせで次の状態が，今の左隣の状態になればよい． したがって，出力のならびは 
    (1,1,1,1,0,0,0,0)
    これを二進数として読めば，状態遷移関数の番号が 240 であることが わかる．

これでどうだ？

--nobsun

Name:
Comment:

There is no comment.

2006-07-13 [Gauche] 各要素が「0または1をとる乱数」から成る長さnのリストを得よ

別の方法を考えてみた． 

(use srfi-27)

(define (make-binary-random-list n)
  (map digit->integer (string->list (format #`"~,|n|,,'0b" (random-integer (expt 2 n))))))

これで本当に 0, 1 がランダムになるんだろうか？

--nobsun

Name:
Comment:

There is no comment.

2006-07-12 [Java] 各要素が「0または1をとる乱数」から成る長さnのリストを得よ

各要素が「0または1をとる乱数」から成る長さnのリストを得よ。

久しぶりにJavaで書いてみた。 

import java.util.Vector;

class RandList {
    static Vector<Integer> makeBinaryRandomList(int length) {
        Vector<Integer> bits = new Vector<Integer>();
        for (int i=0; i<length; i++) {
            bits.addElement(new Integer((int)(Math.random() * 2)));
        }
        return bits;
    }
    public static void main(String[] args) {
        System.out.println(makeBinaryRandomList(24));
    }
}

--yasuyuki

Name:
Comment:

There is no comment.

2006-07-11 [Gauche] 各要素が「0または1をとる乱数」から成る長さnのリストを得よ

各要素が「0または1をとる乱数」から成る長さnのリストを得よ。 

(use srfi-27)
(use srfi-42)

(define (make-binary-random-list length)
  (list-ec (: i length) (random-integer 2)))

--yasuyuki

Name:
Comment:
John1345: (Tue Sep 8 18:01:56 2009 )
Very nice site! is it yours too http://apeoixy.com/tqaav/4.html
John1345: (Tue Sep 8 18:01:57 2009 )
Very nice site!
name: (Wed Dec 30 14:24:33 2009 )
comment6,
Jxuppzro: (Sun Jan 10 06:57:54 2010 )
comment3,
QPtnCAkJjnwnr: (Sat Jan 15 08:04:32 2011 )
links/go.txt;25;25
DrZoibergLo: (Tue Nov 29 21:00:41 2011 )
ch7nHb http://www.QKiMt6vfLbn1bD0zxU9QchzPHO25ZYPy.com

2006-07-10 [quiz] 各要素が「0または1をとる乱数」から成る長さnのリストを得よ

各要素が「0または1をとる乱数」から成る長さnのリストを得よ。

ex. 

 gosh> (make-binary-random-list 24)
 (1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 1 0 1 0 1)

--yasuyuki

Name:
Comment:

There is no comment.

2006-07-07 [Gauche] 複数のアドレスやポートをlistenする

ネットワークサーバを書いていると、複数のアドレス+ポートをlistenしたいことがよくある。 IPv6とIPv4デュアルスタックなサーバ上だったりすれば普通にそうなるし。

で、 

(("10.37.129.2" . 80) ("localhost" . 8080))

を与えると、それをlistenするソケットのリストを返してくれる関数が欲しくなるわけだ。 

(use gauche.net)
(define (make-server-sockets* hosts)
  (define (%avoid-mapped-addr sock addr)
    (when (eq? (sockaddr-family addr) 'inet6)
      (socket-setsockopt sock |IPPROTO_IPV6| |IPV6_V6ONLY| 1)))
  (apply append! (map (lambda (h)
                        (make-server-sockets (car h) (cdr h)
                                             :reuse-addr? #t :backlog SOMAXCONN
                                             :sock-init %avoid-mapped-addr))
                      hosts)))

こんな感じ。 

gosh> (make-server-sockets* '(("10.37.129.2" . 8080) ("localhost" . 8080)))
(#<socket (listen "10.37.129.2:8080")> #<socket (listen "[::1]:8080")> #<socket (listen "127.0.0.1:8080")>)
gosh>

なお、%avoid-mapped-addrを:sock-initに渡しているのは、 その名の通り、IPv4マップドアドレスをlistenしないようにするための措置。 好みの問題かもしれないが、フィルタリングなどを考える時話がややこしくなるので、 基本的にIPv4マップドアドレスは使わないことにしている。

--び

Name:
Comment:

There is no comment.

2006-07-06 [CHTML] EUC-JPのページでDoCoMoの絵文字を表示する

DoCoMoのCHTMLはShift_JISで記述すべきだが、諸般の事情でEUC-JPを使わなければならない場合がありえる。

EUC-JPのページにDoCoMoの絵文字を埋め込むには16進数のUnicode実体参照を使う。 

&#xUUUU;

UUUUの部分は、絵文字を16進Unicodeで表した数字を入力する。

たとえば、 

&#xE6E2; <a href="link1" accesskey="1">ニュース・天気予報</a><br>
&#xE6E3; <a href="link2" accesskey="2">スポーツ</a><br>
&#xE6E4; <a href="link3" accesskey="3">ショッピング</a><br>

と書くと以下の通りに表示される。

ただし最近の機種ならEUCを表示できるが、古い機種でEUCを表示できないものがある。

また、willcomでは同じ方法でDoCoMo絵文字を表示できるが、auは文字化けする。

--yasuyuki

Name:
Comment:

There is no comment.

2006-07-05 [Gauche] MIMEヘッダフィールド名のキャピタライズ

処理の都合で 

content-type: text/html

みたいになっているヘッダフィールド名を 

Content-Type: text/hml

という見た目にしたい。いや、規格的に見たら前者でもかまわないんだけど、 何というか美的に後者でありたい(笑)。 

(define (capitalize-field-name out field-name)
  (call-with-input-string field-name
    (lambda (in)
      (with-port-locking in
        (lambda ()
          (letrec ((up (lambda (c)
                         (unless (eof-object? c)
                           (write-char (char-upcase c) out)
                           (down (read-char in)))))
                   (down (lambda (c)
                           (unless (eof-object? c)
                             (write-char (char-downcase c) out)
                             (if (char=? #\- c)
                                 (up (read-char in))
                                 (down (read-char in)))))))
            (up (read-char in))))))))

こんなのを定義して、 

gosh> (call-with-output-string (cut capitalize-field-name <> "content-type"))
"Content-Type"

だけど、capitalize-field-nameの定義がけっこう大げさな気がする。

--び

Name:
Comment:
び: (Fri Jul 14 19:43:14 2006 )
自己突っ込みだけど、こっちの方が簡単っぽい

(use gauche.collection)
(define (capitalize-field-name out field-name)
    (fold (lambda (c prev)
            (write-char ((if (char=? #\- prev) char-upcase char-downcase) c) out)
            c)
          #\-
          field-name)
    (undefined))
shiro: (Sat Jul 22 02:59:26 2006 )
(use srfi-13)
(string-titlecase "content-type") => "Content-Type"
び: (Sat Jul 22 06:46:49 2006 )
がーん。そんな便利なものが...

2006-07-04 [Namazu] HTMLフィルタがジェームズ・クラーク記法のHTMLの解釈に失敗する現象の回避方法

NamazuのHTMLフィルタはHTMLをパーズしているわけではなく、正規表現でタグをマッチさせているだけである。

このため、タグの途中に改行が入る、ジェームズ・クラーク記法と呼ばれる記法のHTMLでは解釈に失敗する。 

><head
><title>タイトル</title
></head
>

これを回避するには、NamazuのHTMLフィルタであるfilter/html.plで、インデックス対象の本文から改行をすべて削除し、行を連結してしまえば良い。 

sub html_filter ($$$$) {
    my ($contref, $weighted_str, $fields, $headings) = @_;

    $$contref =~ s/\r\n//g;
    $$contref =~ s/\r//g;
    $$contref =~ s/\n//g;

    html::escape_lt_gt($contref);

(以下略)

--yasuyuki

Name:
Comment:

There is no comment.

2006-07-03 [Ubuntu] FirefoxにDOMインスペクタがない?

Ubuntu LinuxでFirefoxをインストールして、いざDOMインスペクタを使おうとするとメニューにない。

https://addons.mozilla.org/firefox/ で探してもDOMインスペクタ単体では検索できない。

途方に暮れて、 

apt-cache search ^firefox

などと探してみると、 

 firefox-themes-ubuntu - Firefox themes matching the Ubuntu desktop look
 firefox-webdeveloper - web developer extension for the Firefox web browser
 firefox - lightweight web browser based on Mozilla
 firefox-dbg - Debugging information for firefox
 firefox-dev - Development files for Mozilla Firefox
 firefox-gnome-support - Support for Gnome in Mozilla Firefox
 firefox-dom-inspector - tool for inspecting the DOM of pages in Mozilla Firefox

何と別パッケージになっているではありませんか! 

sudo apt-get install firefox-dom-inspector

これでやっとDOMインスペクタが使える...

--yasuyuki

Name:
Comment:

There is no comment.

Created: 2006-07-11 18:30:56(+0900) by bizenn
Modified: 2006-08-08 11:26:56(+0900) by bizenn

このサイトは、 IPA の「平成15年度オープンソフトウエア活用基盤整備事業」 の委託事業として開発されたKahuaで試験的に運用しております。

Copyright (c) 2004-2007 株式会社タイムインターメディア　About Us