川渡り問題 in Egison

river.egi

--
-- River
--
-- $ egison                                       4.1.3
-- > loadFile "river.egi"


--
-- Data
--
-- (旅人, オオカミ, ヒツジ, キャベツ), 0:left 1:right
def state :=
  [(0, 0, 0, 0), (0, 1, 1, 1), (0, 0, 1, 1), (0, 0, 0, 1), (1, 1, 1, 1), (1, 1, 1, 2)]


--
-- Codes 未完成
--
def isTrans (x1, x2, x3, x4) (y1, y2, y3, y4) :=
  let z := x1 + x2 + x3 + x4 - (y1 + y2 + y3 + y4)
  in z = -1 || z = 0 || z = 1

-- 各状態に高々一回遷移する事を想定
def river :=
  matchAll state as multiset (integer, integer, integer, integer) with
  | ((#0, #0, #0, #0) & $x_1)
    :: (loop $i (2, $n) (($x_i & ?(\_->isTrans x_(i - 1) x_i)) :: ...)
        (((#1, #1, #1, #1) & ?(\_->isTrans x_n (1, 1, 1, 1))) :: _))
      -> (map (\i -> x_i) [1..n]) ++ [(1, 1, 1, 1)]


--
-- Tests
--
-- $ egison -t river.egi
assertEqual "test1"
  river
  [[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 1, 1), (1, 1, 1, 1)]]