Haskellでクイズ「嫉妬深い男たち」を解く（５）

１．次の場面を求める

舟が一方の岸から他方の岸にわたり、今度は逆に折り返してきたときの場面を得る関数nextShotを考える。折り返しの時は、乗客となる候補がいくつかあるので、複数の場面が存在することとなる。この関数は、岸についたとき乗客を降ろし、その後で、舟に乗る候補を得ることで求められるので、mergeGroupをした後で、separateGroupを行うことで得られる。
関数nextShotは、左岸についたときの関数nextLShotと右岸についたときの関数nextRShotで実現される。

nextShot :: OneShot -> [OneShot]
nextShot x
     | toward x == LeftSide  = nextLShot x    
     | toward x == RightSide = nextRShot x
     | otherwise                 = error "Unexpected errors occur in mergeGroups." 

関数nextLShot は次のようになっている。mergeGroupsで左岸にいた人たちと乗船していた人たちを一緒にした後、この人たちから、左岸に残る人たちと乗船する人たちをseparateGroupで得て、次の場面を作り出す。

nextLShot :: OneShot -> [OneShot]
nextLShot x = [ OneShot {toward = RightSide, leftSide = left1, onBoat = boat1, rightSide = rightSide x} |
                y <- separateGroup $ leftSide $ mergeGroups x, let left1 = land y, let boat1 = boat y ]

関数nextRShotも同じである。

nextRShot :: OneShot -> [OneShot]
nextRShot x = [ OneShot {toward = LeftSide, leftSide = leftSide x, onBoat = boat1, rightSide = right1} |
                y <- separateGroup $ rightSide $ mergeGroups x, let right1 = land y, let boat1 = boat y ]

２．プログラムを完成させる

クイズ「嫉妬深い男たち」を解くための準備が整ったので、舟が川を行き来したとする。舟が渡る回数を\(n\)としたとき、(船が何回渡ったかで勘定するので、一往復は2回となる)。舟が\(n\)回渡った時の取りえる場面をデータ型Stepで表すこととする(すなわち、深さ優先検索を実行しているときの深度\(n\)での候補)。Stepはレコードで、フィールドは現在取りえる場面と過去に現れた場面からなっている。即ち次のようになっている。

data Step = Step {current :: [OneShot], past :: [OneShot]} deriving (Eq, Show) 

関数moveは、初期状態から始めて、舟が行き来をした時のStepの列を与えるものとする。ただし、同じパターンを繰り返さないために、過去に出てきた場面は選択しないようにしてある。Haskellで記述すると次のようになる。

move :: Step -> [OneShot]
move Step {current = current1, past = past1} = current1 ++ move Step {current = current2, past = past2}
     where cur = nub $ foldr (++) [ ] $ map nextShot current1
           current2 = filter (\x -> not (elem x past1)) cur
           past2 = current1 ++ past1

なお、上記の関数でnubが出てくるが、これはリストの構成要素が重複しているときは、一つだけにするものである。この関数を使用する時は、次のモジュールをロードしておく必要がある。

import Data.List (nub)

2.1 問題

moveの関数を実行し、どのように場面が変わっていくか様子を観察しなさい。次の例はtset5を初期状態とし、場面の推移をtest30で表したものである。

test30 = move Step {current = [test5], past = [ ]}
-- 次のものが解である。(但し、最後の乗船の様子を示している）
-- last $ take 65 test30　（夫婦が乗船している）
-- last $ take 67 test30　（妻二人が乗船している）

2.2 問題

関数moveを改良し、解が得られたら終了するようにしなさい。解はいくつもあるので、最初の解で終了するようにする。これが舟が行き来する回数が最も少ないものである。

2.3 問題

関数moveでは、行き来の回数が示されていないので、これが示されるようにしなさい。

2.4 問題

関数moveでは、どのような順序で乗船したかが分からないので、改良してこれが分かるようにしなさい。