Skip to content

Instantly share code, notes, and snippets.

@righ1113

righ1113/EightPuzzle.hs

Last active July 5, 2023 19:58
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save righ1113/07496bd006fa8bd3e2e14e7460035607 to your computer and use it in GitHub Desktop.
Save righ1113/07496bd006fa8bd3e2e14e7460035607 to your computer and use it in GitHub Desktop.
Download ZIP
8パズルは181440通り in Egison, Haskell
Raw
EightPuzzle.hs
module EightPuzzle where
import Data.List (permutations)
-- 参考記事：https://mathtrain.jp/8puzzle
{--
8 puzzle
1 2 3
4 5 6
7 8 _
--}
rangeEmpty :: [Int] -> Int
rangeEmpty [9, _, _, _, _, _, _, _, _] = 4
rangeEmpty [_, 9, _, _, _, _, _, _, _] = 3
rangeEmpty [_, _, 9, _, _, _, _, _, _] = 2
rangeEmpty [_, _, _, 9, _, _, _, _, _] = 3
rangeEmpty [_, _, _, _, 9, _, _, _, _] = 2
rangeEmpty [_, _, _, _, _, 9, _, _, _] = 1
rangeEmpty [_, _, _, _, _, _, 9, _, _] = 2
rangeEmpty [_, _, _, _, _, _, _, 9, _] = 1
rangeEmpty [_, _, _, _, _, _, _, _, 9] = 0
nOfR1 :: ([Int], Int) -> ([Int], Int)
nOfR1 ([1, a, b, c, d, e, f, g, h], cnt) = ([1, a, b, c, d, e, f, g, h], cnt)
nOfR1 ([a, 1, b, c, d, e, f, g, h], cnt) = ([1, a, b, c, d, e, f, g, h], cnt+1)
nOfR1 ([b, a, 1, c, d, e, f, g, h], cnt) = ([1, a, b, c, d, e, f, g, h], cnt+1)
nOfR1 ([c, a, b, 1, d, e, f, g, h], cnt) = ([1, a, b, c, d, e, f, g, h], cnt+1)
nOfR1 ([d, a, b, c, 1, e, f, g, h], cnt) = ([1, a, b, c, d, e, f, g, h], cnt+1)
nOfR1 ([e, a, b, c, d, 1, f, g, h], cnt) = ([1, a, b, c, d, e, f, g, h], cnt+1)
nOfR1 ([f, a, b, c, d, e, 1, g, h], cnt) = ([1, a, b, c, d, e, f, g, h], cnt+1)
nOfR1 ([g, a, b, c, d, e, f, 1, h], cnt) = ([1, a, b, c, d, e, f, g, h], cnt+1)
nOfR1 ([h, a, b, c, d, e, f, g, 1], cnt) = ([1, a, b, c, d, e, f, g, h], cnt+1)
nOfR2 :: ([Int], Int) -> ([Int], Int)
nOfR2 ([a, 2, b, c, d, e, f, g, h], cnt) = ([a, 2, b, c, d, e, f, g, h], cnt)
nOfR2 ([a, b, 2, c, d, e, f, g, h], cnt) = ([a, 2, b, c, d, e, f, g, h], cnt+1)
nOfR2 ([a, c, b, 2, d, e, f, g, h], cnt) = ([a, 2, b, c, d, e, f, g, h], cnt+1)
nOfR2 ([a, d, b, c, 2, e, f, g, h], cnt) = ([a, 2, b, c, d, e, f, g, h], cnt+1)
nOfR2 ([a, e, b, c, d, 2, f, g, h], cnt) = ([a, 2, b, c, d, e, f, g, h], cnt+1)
nOfR2 ([a, f, b, c, d, e, 2, g, h], cnt) = ([a, 2, b, c, d, e, f, g, h], cnt+1)
nOfR2 ([a, g, b, c, d, e, f, 2, h], cnt) = ([a, 2, b, c, d, e, f, g, h], cnt+1)
nOfR2 ([a, h, b, c, d, e, f, g, 2], cnt) = ([a, 2, b, c, d, e, f, g, h], cnt+1)
nOfR3 :: ([Int], Int) -> ([Int], Int)
nOfR3 ([a, b, 3, c, d, e, f, g, h], cnt) = ([a, b, 3, c, d, e, f, g, h], cnt)
nOfR3 ([a, b, c, 3, d, e, f, g, h], cnt) = ([a, b, 3, c, d, e, f, g, h], cnt+1)
nOfR3 ([a, b, d, c, 3, e, f, g, h], cnt) = ([a, b, 3, c, d, e, f, g, h], cnt+1)
nOfR3 ([a, b, e, c, d, 3, f, g, h], cnt) = ([a, b, 3, c, d, e, f, g, h], cnt+1)
nOfR3 ([a, b, f, c, d, e, 3, g, h], cnt) = ([a, b, 3, c, d, e, f, g, h], cnt+1)
nOfR3 ([a, b, g, c, d, e, f, 3, h], cnt) = ([a, b, 3, c, d, e, f, g, h], cnt+1)
nOfR3 ([a, b, h, c, d, e, f, g, 3], cnt) = ([a, b, 3, c, d, e, f, g, h], cnt+1)
nOfR4 :: ([Int], Int) -> ([Int], Int)
nOfR4 ([a, b, c, 4, d, e, f, g, h], cnt) = ([a, b, c, 4, d, e, f, g, h], cnt)
nOfR4 ([a, b, c, d, 4, e, f, g, h], cnt) = ([a, b, c, 4, d, e, f, g, h], cnt+1)
nOfR4 ([a, b, c, e, d, 4, f, g, h], cnt) = ([a, b, c, 4, d, e, f, g, h], cnt+1)
nOfR4 ([a, b, c, f, d, e, 4, g, h], cnt) = ([a, b, c, 4, d, e, f, g, h], cnt+1)
nOfR4 ([a, b, c, g, d, e, f, 4, h], cnt) = ([a, b, c, 4, d, e, f, g, h], cnt+1)
nOfR4 ([a, b, c, h, d, e, f, g, 4], cnt) = ([a, b, c, 4, d, e, f, g, h], cnt+1)
nOfR5 :: ([Int], Int) -> ([Int], Int)
nOfR5 ([a, b, c, d, 5, e, f, g, h], cnt) = ([a, b, c, d, 5, e, f, g, h], cnt)
nOfR5 ([a, b, c, d, e, 5, f, g, h], cnt) = ([a, b, c, d, 5, e, f, g, h], cnt+1)
nOfR5 ([a, b, c, d, f, e, 5, g, h], cnt) = ([a, b, c, d, 5, e, f, g, h], cnt+1)
nOfR5 ([a, b, c, d, g, e, f, 5, h], cnt) = ([a, b, c, d, 5, e, f, g, h], cnt+1)
nOfR5 ([a, b, c, d, h, e, f, g, 5], cnt) = ([a, b, c, d, 5, e, f, g, h], cnt+1)
nOfR6 :: ([Int], Int) -> ([Int], Int)
nOfR6 ([a, b, c, d, e, 6, f, g, h], cnt) = ([a, b, c, d, e, 6, f, g, h], cnt)
nOfR6 ([a, b, c, d, e, f, 6, g, h], cnt) = ([a, b, c, d, e, 6, f, g, h], cnt+1)
nOfR6 ([a, b, c, d, e, g, f, 6, h], cnt) = ([a, b, c, d, e, 6, f, g, h], cnt+1)
nOfR6 ([a, b, c, d, e, h, f, g, 6], cnt) = ([a, b, c, d, e, 6, f, g, h], cnt+1)
nOfR7 :: ([Int], Int) -> ([Int], Int)
nOfR7 ([a, b, c, d, e, f, 7, g, h], cnt) = ([a, b, c, d, e, f, 7, g, h], cnt)
nOfR7 ([a, b, c, d, e, f, g, 7, h], cnt) = ([a, b, c, d, e, f, 7, g, h], cnt+1)
nOfR7 ([a, b, c, d, e, f, h, g, 7], cnt) = ([a, b, c, d, e, f, 7, g, h], cnt+1)
nOfR8 :: ([Int], Int) -> ([Int], Int)
nOfR8 ([a, b, c, d, e, f, g, 8, h], cnt) = ([a, b, c, d, e, f, g, 8, h], cnt)
nOfR8 ([a, b, c, d, e, f, g, h, 8], cnt) = ([a, b, c, d, e, f, g, 8, h], cnt+1)
nOfReplace :: ([Int], Int) -> ([Int], Int)
nOfReplace = nOfR8 . nOfR7 . nOfR6 . nOfR5 . nOfR4 . nOfR3 . nOfR2 . nOfR1
-- *EightPuzzle> answer8
-- 181440 (= 9!/2)
answer8 :: Int
answer8 =
length $ filter (\x -> (odd . rangeEmpty) x == (odd . snd . nOfReplace) (x, 0)) $ permutations [1..9]
-- -----------------------------
nOfR7B :: ([Int], Int) -> ([Int], Int)
nOfR7B ([a, b, c, d, e, f, 8, g, h], cnt) = ([a, b, c, d, e, f, 8, g, h], cnt)
nOfR7B ([a, b, c, d, e, f, g, 8, h], cnt) = ([a, b, c, d, e, f, 8, g, h], cnt+1)
nOfR7B ([a, b, c, d, e, f, h, g, 8], cnt) = ([a, b, c, d, e, f, 8, g, h], cnt+1)
nOfR8B :: ([Int], Int) -> ([Int], Int)
nOfR8B ([a, b, c, d, e, f, g, 7, h], cnt) = ([a, b, c, d, e, f, g, 7, h], cnt)
nOfR8B ([a, b, c, d, e, f, g, h, 7], cnt) = ([a, b, c, d, e, f, g, 7, h], cnt+1)
nOfReplaceB :: ([Int], Int) -> ([Int], Int)
nOfReplaceB = nOfR8B . nOfR7B . nOfR6 . nOfR5 . nOfR4 . nOfR3 . nOfR2 . nOfR1
-- *EightPuzzle> answer8B
-- 181440 (= 9!/2)
answer8B :: Int
answer8B =
length $ filter (\x -> (odd . rangeEmpty) x == (odd . snd . nOfReplaceB) (x, 0)) $ permutations [1..9]
-- [1, 2, 3, 4, 5, 6, 7, 8, 9]は[1, 2, 3, 4, 5, 6, 8, 7, 9]に遷移できないから、
-- answer8とanswer8Bの共通元は無い
Raw
eightPuzzle2-N.egi
;; > egison -N
;; > loadFile("eightPuzzle2-N.egi")
;; 8 puzzle
;; 1 2 3
;; 4 5 6
;; 7 8 _
;; tree matcher
tree(a, b) = matcher
| <leaf $> as b ->
| <Leaf $x> -> {x}
| _ -> {}
| <lnode $ $> as (a, list(tree(a, b))) ->
| <Node $x $ts> -> {(x, ts)}
| _ -> {}
| <mnode $ $> as (a, multiset(tree(a, b))) ->
| <Node $x $ts> -> {(x, ts)}
| _ -> {}
| <descendant $> as tree(a, b) ->
| $t -> matchAll t as tree(a, b)
| loop($i, (1, _), <mnode _ <cons ... _>>, $x) -> x
| $val as () ->
| $tgt -> if val == tgt then {()} else {}
| $ as something ->
| $tgt -> {tgt}
;; ユーティリティ
pred(x) = if x <= 0 then 0 else x - 1 ;; no use
eqBeforeAfter(xs) = match xs as list(something)
| $x1 <:> $x2 <:> $xs -> if x1 == x2 then x1 else eqBeforeAfter([x2, @xs])
;; ########## 3 puzzle ##########
initTree = <Leaf [1, 2, 3, 4]>
initStac = []
nextThree(xs) = match xs as list(integer)
| (4 <:> $a <:> $b <:> $c <:> <nil>) -> [<Leaf [a, 4, b, c]>, <Leaf [b, a, 4, c]>]
| ($a <:> 4 <:> $b <:> $c <:> <nil>) -> [<Leaf [4, a, b, c]>, <Leaf [a, c, b, 4]>]
| ($a <:> $b <:> 4 <:> $c <:> <nil>) -> [<Leaf [a, b, c, 4]>, <Leaf [4, b, a, c]>]
| ($a <:> $b <:> $c <:> 4 <:> <nil>) -> [<Leaf [a, b, 4, c]>, <Leaf [a, 4, c, b]>]
;; tupleを入力してtupleを返す
nextTreeAndStac(tr, stac) = (
;; treeは、LeafをNodeに変えて、どんどん追加していく
(match tr as tree(list(integer), list(integer))
| <leaf $t> -> if member?(t, stac) then <Leaf t> else <Node t nextThree(t)>
| <lnode $t $ts> -> <Node t map(fst, map(nextTreeAndStac($, stac), ts))>
| _ -> <Leaf [0]>),
;; stacは、その時のtreeのLeafを追加していく
(unique(append(stac,
(matchAll tr as tree(list(integer), list(integer))
| <descendant <leaf $x>> -> x)
)))
)
;; > eqBeforeAfter(iterate(nextTreeAndStac, (initTree, initStac)))
;; [<Node {1 2 3 4} {<Node {1 2 4 3} {<Leaf {1 2 3 4}> <Node {4 2 1 3} {<Node {2 4 1 3} {<Leaf {4 2 1 3}> <Node {2 3 1 4} {<Node {2 3 4 1} {<Leaf {2 3 1 4}> <Node {4 3 2
;; 1} {<Leaf {3 4 2 1}> <Leaf {2 3 4 1}>}>}> <Leaf {2 4 1 3}>}>}> <Leaf {1 2 4 3}>}>}> <Node {1 4 3 2} {<Node {4 1 3 2} {<Leaf {1 4 3 2}> <Node {3 1 4 2} {<Node {3 1 2 4} {<Leaf {3 1 4 2}> <Node {3 4 2 1} {<Node {4 3 2 1} {<Leaf {3 4 2 1}> <Leaf {2 3 4 1}>}> <Leaf {3 1 2 4}>}>}> <Leaf {4 1 3 2}>}>}> <Leaf {1 2 3 4}>}>}> {{1 2 3 4} {1 2 4 3} {1 4 3 2} {4 2 1 3} {4 1 3 2} {2 4 1 3} {3 1 4 2} {2 3 1 4} {3 1 2 4} {2 3 4 1} {3 4 2 1} {4 3 2 1}}]
;; > length(snd(eqBeforeAfter(iterate(nextTreeAndStac, (initTree, initStac)))))
;; 12
;; #################################################
;; ########## 8 puzzle ##########
initTreeE = <Leaf [1, 2, 3, 4, 5, 6, 7, 8, 9]>
initStacE = []
nextEight(xs) = match xs as list(integer)
| (9 <:> $a <:> $b <:> $c <:> $d <:> $e <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [a, 9, b, c, d, e, f, g, h]>, <Leaf [c, a, b, 9, d, e, f, g, h]>]
| ($a <:> 9 <:> $b <:> $c <:> $d <:> $e <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [9, a, b, c, d, e, f, g, h]>, <Leaf [a, b, 9, c, d, e, f, g, h]>, <Leaf [a, d, b, c, 9, e, f, g, h]>]
| ($a <:> $b <:> 9 <:> $c <:> $d <:> $e <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [a, 9, b, c, d, e, f, g, h]>, <Leaf [a, b, e, c, d, 9, f, g, h]>]
| ($a <:> $b <:> $c <:> 9 <:> $d <:> $e <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [9, b, c, a, d, e, f, g, h]>, <Leaf [a, b, c, f, d, e, 9, g, h]>, <Leaf [a, b, c, d, 9, e, f, g, h]>]
| ($a <:> $b <:> $c <:> $d <:> 9 <:> $e <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [a, 9, c, d, b, e, f, g, h]>, <Leaf [a, b, c, 9, d, e, f, g, h]>, <Leaf [a, b, c, d, e, 9, f, g, h]>, <Leaf [a, b, c, d, g, e, f, 9, h]>]
| ($a <:> $b <:> $c <:> $d <:> $e <:> 9 <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [a, b, 9, d, e, c, f, g, h]>, <Leaf [a, b, c, d, e, h, f, g, 9]>, <Leaf [a, b, c, d, 9, e, f, g, h]>]
| ($a <:> $b <:> $c <:> $d <:> $e <:> $f <:> 9 <:> $g <:> $h <:> <nil>)
-> [<Leaf [a, b, c, 9, e, f, d, g, h]>, <Leaf [a, b, c, d, e, f, g, 9, h]>]
| ($a <:> $b <:> $c <:> $d <:> $e <:> $f <:> $g <:> 9 <:> $h <:> <nil>)
-> [<Leaf [a, b, c, d, e, f, 9, g, h]>, <Leaf [a, b, c, d, e, f, g, h, 9]>, <Leaf [a, b, c, d, 9, f, g, e, h]>]
| ($a <:> $b <:> $c <:> $d <:> $e <:> $f <:> $g <:> $h <:> 9 <:> <nil>)
-> [<Leaf [a, b, c, d, e, 9, g, h, f]>, <Leaf [a, b, c, d, e, f, g, 9, h]>]
;; tupleを入力してtupleを返す
nextTreeAndStacE(tr, stac) = (
(match tr as tree(list(integer), list(integer))
| <leaf $t> -> if member?(t, stac) then <Leaf t> else <Node t nextEight(t)>
| <lnode $t $ts> -> <Node t map(fst, map(nextTreeAndStacE($, stac), ts))>
| _ -> <Leaf [0]>),
(unique(append(stac,
(matchAll tr as tree(list(integer), list(integer))
| <descendant <leaf $x>> -> x)
)))
)
;; #################################################
;; 6時間走らせても終わらない……
;; > egison -N eightPuzzle2-N.egi
main(args) = print(show(
length(snd(eqBeforeAfter(iterate(nextTreeAndStacE, (initTreeE, initStacE)))))
))
;; bug: 同時にLeafになった同じものは、両方伸ばしてしまう
;; > nth(7, iterate(nextTreeAndStacE, (initTreeE, initStacE)))
;; [<Node {1 2 3 4 5 6 7 8 9} {<Node {1 2 3 4 5 9 7 8 6} {<Node {1 2 9 4 5 3 7 8 6} {<Node {1 9 2 4 5 3 7 8 6} {<Node {9 1 2 4 5 3 7 8 6} {<Leaf {1 9 2 4 5 3 7 8 6}> <Node {4 1 2 9 5 3 7 8 6} {<Leaf {9 1 2 4 5 3 7 8 6}> <Leaf {4 1 2 7 5 3 9 8 6}> <Leaf {4 1 2 5 9 3 7 8 6}>}>}> <Leaf {1 2 9 4 5 3 7 8 6}> <Node {1 5 2 4 9 3 7 8 6} {<Leaf {1 9 2 4 5 3 7 8 6}> <Node {1 5 2 9 4 3 7 8 6} {<Leaf {9 5 2 1 4 3 7 8 6}> <Leaf {1 5 2 7 4 3 9 8 6}> <Leaf {1 5 2 4 9 3 7 8 6}>}> <Node {1 5 2 4 3 9 7 8 6} {<Leaf {1 5 9 4 3 2 7 8 6}> <Leaf {1 5 2 4 3 6 7 8 9}> <Leaf {1 5 2 4 9 3 7 8 6}>}> <Node {1 5 2 4 8 3 7 9 6} {<Leaf {1 5 2 4 8 3 9 7 6}> <Leaf {1 5 2 4 8 3 7 6 9}> <Leaf {1 5
;; 2 4 9 3 7 8 6}>}>}>}> <Leaf {1 2 3 4 5 9 7 8 6}>}> <Leaf {1 2 3 4 5 6 7 8 9}> <Node {1 2 3 4 9 5 7 8 6} {<Node {1 9 3 4 2 5 7 8 6} {<Node {9 1 3 4 2 5 7 8 6} {<Leaf {1 9 3 4 2 5 7 8 6}> <Node {4 1 3 9 2 5 7 8 6} {<Leaf {9 1 3 4 2 5 7 8 6}> <Leaf {4 1 3 7 2 5 9 8 6}> <Leaf {4 1 3 2 9 5 7 8 6}>}>}> <Node {1 3 9 4 2 5 7 8 6} {<Leaf {1
;; 9 3 4 2 5 7 8 6}> <Node {1 3 5 4 2 9 7 8 6} {<Leaf {1 3 9 4 2 5 7 8 6}> <Leaf {1 3 5 4 2 6 7 8 9}> <Leaf {1 3 5 4 9 2 7 8 6}>}>}> <Leaf {1 2 3 4 9 5 7 8 6}>}> <Node {1 2 3 9 4 5 7 8 6} {<Node {9 2 3 1 4 5 7 8 6} {<Node {2 9 3 1 4 5 7 8 6} {<Leaf {9 2 3 1 4 5 7 8 6}> <Leaf {2 3 9 1 4 5 7 8 6}> <Leaf {2 4 3 1 9 5 7 8 6}>}> <Leaf {1 2
;; 3 9 4 5 7 8 6}>}> <Node {1 2 3 7 4 5 9 8 6} {<Leaf {1 2 3 9 4 5 7 8 6}> <Node {1 2 3 7 4 5 8 9 6} {<Leaf {1 2 3 7 4 5 9 8 6}> <Leaf {1 2 3 7 4 5 8 6 9}> <Leaf {1 2 3 7 9 5 8 4 6}>}>}> <Leaf {1 2 3 4 9 5 7 8 6}>}> <Leaf {1 2 3 4 5 9 7 8 6}> <Node {1 2 3 4 8 5 7 9 6} {<Node {1 2 3 4 8 5 9 7 6} {<Node {1 2 3 9 8 5 4 7 6} {<Leaf {9 2 3
;; 1 8 5 4 7 6}> <Leaf {1 2 3 4 8 5 9 7 6}> <Leaf {1 2 3 8 9 5 4 7 6}>}> <Leaf {1 2 3 4 8 5 7 9 6}>}> <Node {1 2 3 4 8 5 7 6 9} {
;; <Node {1 2 3 4 8 9 7 6 5}
;; {<Leaf {1 2 9 4 8 3 7 6 5}> <Leaf {1 2 3 4 8 5 7 6 9}>
;; ★★★<Leaf {1 2 3 4 9 8 7 6 5}>
;; }> <Leaf {1 2 3 4 8 5 7 9 6}>}> <Leaf {1 2 3 4 9 5 7 8 6}>}>}>}>
;; <Node {1 2 3 4 5 6 7 9 8} {<Node {1
;; 2 3 4 5 6 9 7 8} {<Node {1 2 3 9 5 6 4 7 8} {<Node {9 2 3 1 5 6 4 7 8} {<Node {2 9 3 1 5 6 4 7 8} {<Leaf {9 2 3 1 5 6 4 7 8}> <Leaf {2 3 9 1 5 6 4 7 8}> <Leaf {2 5 3 1 9 6 4 7 8}>}> <Leaf {1 2 3 9 5 6 4 7 8}>}> <Leaf {1 2 3 4 5 6 9 7 8}> <Node {1 2 3 5 9 6 4 7 8} {<Node {1 9 3 5 2 6 4 7 8} {<Leaf {9 1 3 5 2 6 4 7 8}> <Leaf {1 3 9 5
;; 2 6 4 7 8}> <Leaf {1 2 3 5 9 6 4 7 8}>}> <Leaf {1 2 3 9 5 6 4 7 8}> <Node {1 2 3 5 6 9 4 7 8} {<Leaf {1 2 9 5 6 3 4 7 8}> <Leaf {1 2 3 5 6 8 4 7 9}> <Leaf {1 2 3 5 9 6 4 7 8}>}> <Node {1 2 3 5 7 6 4 9 8} {<Leaf {1 2 3 5 7 6 9 4 8}> <Leaf {1 2 3 5 7 6 4 8 9}> <Leaf {1 2 3 5 9 6 4 7 8}>}>}>}> <Leaf {1 2 3 4 5 6 7 9 8}>}> <Leaf {1 2 3
;; 4 5 6 7 8 9}> <Node {1 2 3 4 9 6 7 5 8} {<Node {1 9 3 4 2 6 7 5 8} {<Node {9 1 3 4 2 6 7 5 8} {<Leaf {1 9 3 4 2 6 7 5 8}> <Node {4 1 3 9 2 6 7 5 8} {<Leaf {9 1 3 4 2 6 7 5 8}> <Leaf {4 1 3 7 2 6 9 5 8}> <Leaf {4 1 3 2 9 6 7 5 8}>}>}> <Node {1 3 9 4 2 6 7 5 8} {<Leaf {1 9 3 4 2 6 7 5 8}> <Node {1 3 6 4 2 9 7 5 8} {<Leaf {1 3 9 4 2 6
;; 7 5 8}> <Leaf {1 3 6 4 2 8 7 5 9}> <Leaf {1 3 6 4 9 2 7 5 8}>}>}> <Leaf {1 2 3 4 9 6 7 5 8}>}> <Node {1 2 3 9 4 6 7 5 8} {<Node {9 2 3 1 4 6 7 5 8} {<Node {2 9 3 1 4 6 7 5 8} {<Leaf {9 2 3 1 4 6 7 5 8}> <Leaf {2 3 9 1 4 6 7 5 8}> <Leaf {2 4 3 1 9 6 7 5 8}>}> <Leaf {1 2 3 9 4 6 7 5 8}>}> <Node {1 2 3 7 4 6 9 5 8} {<Leaf {1 2 3 9 4 6
;; 7 5 8}> <Node {1 2 3 7 4 6 5 9 8} {<Leaf {1 2 3 7 4 6 9 5 8}> <Leaf {1 2 3 7 4 6 5 8 9}> <Leaf {1 2 3 7 9 6 5 4 8}>}>}> <Leaf {1 2 3 4 9 6 7 5 8}>}> <Node {1 2 3 4 6 9 7 5 8} {<Node {1 2 9 4 6 3 7 5 8} {<Node {1 9 2 4 6 3 7 5 8} {<Leaf {9 1 2 4 6 3 7 5 8}> <Leaf {1 2 9 4 6 3 7 5 8}> <Leaf {1 6 2 4 9 3 7 5 8}>}> <Leaf {1 2 3 4 6 9 7
;; 5 8}>}>
;; <Node {1 2 3 4 6 8 7 5 9}
;; {<Leaf {1 2 3 4 6 9 7 5 8}>
;; <Node {1 2 3 4 6 8 7 9 5}
;; {<Leaf {1 2 3 4 6 8 9 7 5}> <Leaf {1 2 3 4 6 8 7 5 9}>
;; ★★★<Leaf {1 2 3 4 9 8 7 6 5}>
;; }>
;; }>
;; <Leaf {1 2 3 4 9 6 7 5 8}>}> <Leaf {1 2 3 4 5 6 7 9 8}>}>}>}> {{1 2 3 4 5 6 7 8 9} {1 2 3 4 5 9 7 8 6} {1 2 3 4 5 6 7 9 8} {1 2 9 4 5 3 7 8 6} {1 2 3 4 5 6 9 7
;; 8} {1 2 3 4 9 5 7 8 6} {1 2 3 4 9 6 7 5 8} {1 9 2 4 5 3 7 8 6} {1 2 3 9 5 6 4 7 8} {1 9 3 4 2 5 7 8 6} {1 2 3 9 4 5 7 8 6} {1 9 3 4 2 6 7 5 8} {1 2 3 9 4 6 7 5 8} {1 2 3 4 8 5 7 9 6} {1 2 3 4 6 9 7 5 8} {9 1 2 4 5 3 7 8 6} {9 2 3 1 5 6 4 7 8} {1 5 2 4 9 3 7 8 6} {9 1 3 4 2 5 7 8 6} {1 3 9 4 2 5 7 8 6} {9 2 3 1 4 5 7 8 6} {1 2 3 5 9
;; 6 4 7 8} {9 1 3 4 2 6 7 5 8} {1 2 3 7 4 5 9 8 6} {1 3 9 4 2 6 7 5 8} {9 2 3 1 4 6 7 5 8} {1 2 3 4 8 5 9 7 6} {1 2 3 7 4 6 9 5 8} {1 2 9 4 6 3 7 5 8} {1 2 3 4 8 5 7 6 9} {1 2 3 4 6 8 7 5 9} {4 1 2 9 5 3 7 8 6} {2 9 3 1 5 6 4 7 8} {1 5 2 9 4 3 7 8 6} {4 1 3 9 2 5 7 8 6} {2 9 3 1 4 5 7 8 6} {1 9 3 5 2 6 4 7 8} {1 5 2 4 3 9 7 8 6} {1 3
;; 5 4 2 9 7 8 6} {4 1 3 9 2 6 7 5 8} {2 9 3 1 4 6 7 5 8} {1 5 2 4 8 3 7 9 6} {1 2 3 7 4 5 8 9 6} {1 2 3 9 8 5 4 7 6} {1 2 3 5 6 9 4 7 8} {1 3 6 4 2 9 7 5 8} {1 9 2 4 6 3 7 5 8} {1 2 3 4 8 9 7 6 5} {1 2 3 5 7 6 4 9 8} {1 2 3 7 4 6 5 9 8} {1 2 3 4 6 8 7 9 5}}]
Raw
eightPuzzle3-N.egi
;; > egison -N
;; > loadFile("eightPuzzle3-N.egi")
;; 8 puzzle
;; 1 2 3
;; 4 5 6
;; 7 8 _
;; tree matcher
def tree(a, b) = matcher
| <leaf $> as b ->
| <Leaf $x> -> {x}
| _ -> {}
| <lnode $ $> as (a, list(tree(a, b))) ->
| <Node $x $ts> -> {(x, ts)}
| _ -> {}
| <mnode $ $> as (a, multiset(tree(a, b))) ->
| <Node $x $ts> -> {(x, ts)}
| _ -> {}
| <descendant $> as tree(a, b) ->
| $t -> matchAll t as tree(a, b)
| loop($i, (1, _), <mnode _ <cons ... _>>, $x) -> x
| $val as () ->
| $tgt -> if val == tgt then {()} else {}
| $ as something ->
| $tgt -> {tgt}
;; ユーティリティ
def eqBeforeAfter(xs) = match xs as list(something)
| $x1 <:> $x2 <:> $xs -> if x1 == x2 then x1 else eqBeforeAfter([x2, @xs])
def myMap(f, xs, stac) = match xs as list(something)
| <nil> -> []
| $x <:> $xs -> let (ret, stac2) = f(x, stac) in cons(ret, myMap(f, xs, stac2))
| _ -> [dead]
;; ########## 3 puzzle ##########
initTree = <Leaf [1, 2, 3, 4]>
initStac = []
def nextThree(xs) = match xs as list(integer)
| (4 <:> $a <:> $b <:> $c <:> <nil>) -> [<Leaf [a, 4, b, c]>, <Leaf [b, a, 4, c]>]
| ($a <:> 4 <:> $b <:> $c <:> <nil>) -> [<Leaf [4, a, b, c]>, <Leaf [a, c, b, 4]>]
| ($a <:> $b <:> 4 <:> $c <:> <nil>) -> [<Leaf [a, b, c, 4]>, <Leaf [4, b, a, c]>]
| ($a <:> $b <:> $c <:> 4 <:> <nil>) -> [<Leaf [a, b, 4, c]>, <Leaf [a, 4, c, b]>]
;; tupleを入力してtupleを返す
def nextTreeAndStac(tr, stac) = (
;; treeは、LeafをNodeに変えて、どんどん追加していく
(match tr as tree(list(integer), list(integer))
| <leaf $t> -> if member?(t, stac) then <Leaf t> else <Node t nextThree(t)>
| <lnode $t $ts> -> <Node t map(fst, map(nextTreeAndStac($, stac), ts))>
| _ -> <Leaf [0]>),
;; stacは、その時のtreeのLeafを追加していく
(unique(append(stac,
(matchAll tr as tree(list(integer), list(integer))
| <descendant <leaf $x>> -> x)
)))
)
;; > eqBeforeAfter(iterate(nextTreeAndStac, (initTree, initStac)))
;; [<Node {1 2 3 4} {<Node {1 2 4 3} {<Leaf {1 2 3 4}> <Node {4 2 1 3} {<Node {2 4 1 3} {<Leaf {4 2 1 3}> <Node {2 3 1 4} {<Node {2 3 4 1} {<Leaf {2 3 1 4}> <Node {4 3 2
;; 1} {<Leaf {3 4 2 1}> <Leaf {2 3 4 1}>}>}> <Leaf {2 4 1 3}>}>}> <Leaf {1 2 4 3}>}>}> <Node {1 4 3 2} {<Node {4 1 3 2} {<Leaf {1 4 3 2}> <Node {3 1 4 2} {<Node {3 1 2 4} {<Leaf {3 1 4 2}> <Node {3 4 2 1} {<Node {4 3 2 1} {<Leaf {3 4 2 1}> <Leaf {2 3 4 1}>}> <Leaf {3 1 2 4}>}>}> <Leaf {4 1 3 2}>}>}> <Leaf {1 2 3 4}>}>}> {{1 2 3 4} {1 2 4 3} {1 4 3 2} {4 2 1 3} {4 1 3 2} {2 4 1 3} {3 1 4 2} {2 3 1 4} {3 1 2 4} {2 3 4 1} {3 4 2 1} {4 3 2 1}}]
;; > length(snd(eqBeforeAfter(iterate(nextTreeAndStac, (initTree, initStac)))))
;; 12
;; #################################################
;; ########## 8 puzzle #############################
initTreeE = <Leaf [1, 2, 3, 4, 5, 6, 7, 8, 9]>
initStacE = []
def nextEight(xs) = match xs as list(integer)
| (9 <:> $a <:> $b <:> $c <:> $d <:> $e <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [a, 9, b, c, d, e, f, g, h]>, <Leaf [c, a, b, 9, d, e, f, g, h]>]
| ($a <:> 9 <:> $b <:> $c <:> $d <:> $e <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [9, a, b, c, d, e, f, g, h]>, <Leaf [a, b, 9, c, d, e, f, g, h]>, <Leaf [a, d, b, c, 9, e, f, g, h]>]
| ($a <:> $b <:> 9 <:> $c <:> $d <:> $e <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [a, 9, b, c, d, e, f, g, h]>, <Leaf [a, b, e, c, d, 9, f, g, h]>]
| ($a <:> $b <:> $c <:> 9 <:> $d <:> $e <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [9, b, c, a, d, e, f, g, h]>, <Leaf [a, b, c, f, d, e, 9, g, h]>, <Leaf [a, b, c, d, 9, e, f, g, h]>]
| ($a <:> $b <:> $c <:> $d <:> 9 <:> $e <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [a, 9, c, d, b, e, f, g, h]>, <Leaf [a, b, c, 9, d, e, f, g, h]>, <Leaf [a, b, c, d, e, 9, f, g, h]>, <Leaf [a, b, c, d, g, e, f, 9, h]>]
| ($a <:> $b <:> $c <:> $d <:> $e <:> 9 <:> $f <:> $g <:> $h <:> <nil>)
-> [<Leaf [a, b, 9, d, e, c, f, g, h]>, <Leaf [a, b, c, d, e, h, f, g, 9]>, <Leaf [a, b, c, d, 9, e, f, g, h]>]
| ($a <:> $b <:> $c <:> $d <:> $e <:> $f <:> 9 <:> $g <:> $h <:> <nil>)
-> [<Leaf [a, b, c, 9, e, f, d, g, h]>, <Leaf [a, b, c, d, e, f, g, 9, h]>]
| ($a <:> $b <:> $c <:> $d <:> $e <:> $f <:> $g <:> 9 <:> $h <:> <nil>)
-> [<Leaf [a, b, c, d, e, f, 9, g, h]>, <Leaf [a, b, c, d, e, f, g, h, 9]>, <Leaf [a, b, c, d, 9, f, g, e, h]>]
| ($a <:> $b <:> $c <:> $d <:> $e <:> $f <:> $g <:> $h <:> 9 <:> <nil>)
-> [<Leaf [a, b, c, d, e, 9, g, h, f]>, <Leaf [a, b, c, d, e, f, g, 9, h]>]
;; tupleを入力してtupleを返す
def nextTreeAndStacE(tr, stac) = (
(match tr as tree(list(integer), list(integer))
| <leaf $t> -> if member?(t, stac) then <Leaf t> else <Node t nextEight(t)>
| <lnode $t $ts> -> <Node t myMap(nextTreeAndStacE($, $), ts, stac)>
| _ -> <Leaf [0]>),
(unique(append(stac,
(matchAll tr as tree(list(integer), list(integer))
| <descendant <leaf $x>> -> x)
)))
)
;; #################################################
;; 2時間走らせてメモリ枯渇（メモリ16G＋仮想メモリ51G）
;; C:\me\Egison\eight>egison -N eightPuzzle3-N.egi
;; egison: getMBlocks: VirtualAlloc MEM_COMMIT failed: y[WO t@CｪｬｳｷｬｽﾟAｱﾌｮｹﾅｫﾜｹB
;; > egison -N eightPuzzle3-N.egi
def main(args) = print(show(
length(snd(eqBeforeAfter(iterate(nextTreeAndStacE, (initTreeE, initStacE)))))
))
;; bug: 同時にLeafになった同じものは、両方伸ばしてしまう
;; > nth(7, iterate(nextTreeAndStacE, (initTreeE, initStacE)))
;; [<Node {1 2 3 4 5 6 7 8 9} {<Node {1 2 3 4 5 9 7 8 6} {<Node {1 2 9 4 5 3 7 8 6} {<Node {1 9 2 4 5 3 7 8 6} {<Node {9 1 2 4 5 3 7 8 6} {<Leaf {1 9 2 4 5 3 7 8 6}> <Node {4 1 2 9 5 3 7 8 6} {<Leaf {9 1 2 4 5 3 7 8 6}> <Leaf {4 1 2 7 5 3 9 8 6}> <Leaf {4 1 2 5 9 3 7 8 6}>}>}> <Leaf {1 2 9 4 5 3 7 8 6}> <Node {1 5 2 4 9 3 7 8 6} {<Leaf {1 9 2 4 5 3 7 8 6}> <Node {1 5 2 9 4 3 7 8 6} {<Leaf {9 5 2 1 4 3 7 8 6}> <Leaf {1 5 2 7 4 3 9 8 6}> <Leaf {1 5 2 4 9 3 7 8 6}>}> <Node {1 5 2 4 3 9 7 8 6} {<Leaf {1 5 9 4 3 2 7 8 6}> <Leaf {1 5 2 4 3 6 7 8 9}> <Leaf {1 5 2 4 9 3 7 8 6}>}> <Node {1 5 2 4 8 3 7 9 6} {<Leaf {1 5 2 4 8 3 9 7 6}> <Leaf {1 5 2 4 8 3 7 6 9}> <Leaf {1 5
;; 2 4 9 3 7 8 6}>}>}>}> <Leaf {1 2 3 4 5 9 7 8 6}>}> <Leaf {1 2 3 4 5 6 7 8 9}> <Node {1 2 3 4 9 5 7 8 6} {<Node {1 9 3 4 2 5 7 8 6} {<Node {9 1 3 4 2 5 7 8 6} {<Leaf {1 9 3 4 2 5 7 8 6}> <Node {4 1 3 9 2 5 7 8 6} {<Leaf {9 1 3 4 2 5 7 8 6}> <Leaf {4 1 3 7 2 5 9 8 6}> <Leaf {4 1 3 2 9 5 7 8 6}>}>}> <Node {1 3 9 4 2 5 7 8 6} {<Leaf {1
;; 9 3 4 2 5 7 8 6}> <Node {1 3 5 4 2 9 7 8 6} {<Leaf {1 3 9 4 2 5 7 8 6}> <Leaf {1 3 5 4 2 6 7 8 9}> <Leaf {1 3 5 4 9 2 7 8 6}>}>}> <Leaf {1 2 3 4 9 5 7 8 6}>}> <Node {1 2 3 9 4 5 7 8 6} {<Node {9 2 3 1 4 5 7 8 6} {<Node {2 9 3 1 4 5 7 8 6} {<Leaf {9 2 3 1 4 5 7 8 6}> <Leaf {2 3 9 1 4 5 7 8 6}> <Leaf {2 4 3 1 9 5 7 8 6}>}> <Leaf {1 2
;; 3 9 4 5 7 8 6}>}> <Node {1 2 3 7 4 5 9 8 6} {<Leaf {1 2 3 9 4 5 7 8 6}> <Node {1 2 3 7 4 5 8 9 6} {<Leaf {1 2 3 7 4 5 9 8 6}> <Leaf {1 2 3 7 4 5 8 6 9}> <Leaf {1 2 3 7 9 5 8 4 6}>}>}> <Leaf {1 2 3 4 9 5 7 8 6}>}> <Leaf {1 2 3 4 5 9 7 8 6}> <Node {1 2 3 4 8 5 7 9 6} {<Node {1 2 3 4 8 5 9 7 6} {<Node {1 2 3 9 8 5 4 7 6} {<Leaf {9 2 3
;; 1 8 5 4 7 6}> <Leaf {1 2 3 4 8 5 9 7 6}> <Leaf {1 2 3 8 9 5 4 7 6}>}> <Leaf {1 2 3 4 8 5 7 9 6}>}> <Node {1 2 3 4 8 5 7 6 9} {
;; <Node {1 2 3 4 8 9 7 6 5}
;; {<Leaf {1 2 9 4 8 3 7 6 5}> <Leaf {1 2 3 4 8 5 7 6 9}>
;; ★★★<Leaf {1 2 3 4 9 8 7 6 5}>
;; }> <Leaf {1 2 3 4 8 5 7 9 6}>}> <Leaf {1 2 3 4 9 5 7 8 6}>}>}>}>
;; <Node {1 2 3 4 5 6 7 9 8} {<Node {1
;; 2 3 4 5 6 9 7 8} {<Node {1 2 3 9 5 6 4 7 8} {<Node {9 2 3 1 5 6 4 7 8} {<Node {2 9 3 1 5 6 4 7 8} {<Leaf {9 2 3 1 5 6 4 7 8}> <Leaf {2 3 9 1 5 6 4 7 8}> <Leaf {2 5 3 1 9 6 4 7 8}>}> <Leaf {1 2 3 9 5 6 4 7 8}>}> <Leaf {1 2 3 4 5 6 9 7 8}> <Node {1 2 3 5 9 6 4 7 8} {<Node {1 9 3 5 2 6 4 7 8} {<Leaf {9 1 3 5 2 6 4 7 8}> <Leaf {1 3 9 5
;; 2 6 4 7 8}> <Leaf {1 2 3 5 9 6 4 7 8}>}> <Leaf {1 2 3 9 5 6 4 7 8}> <Node {1 2 3 5 6 9 4 7 8} {<Leaf {1 2 9 5 6 3 4 7 8}> <Leaf {1 2 3 5 6 8 4 7 9}> <Leaf {1 2 3 5 9 6 4 7 8}>}> <Node {1 2 3 5 7 6 4 9 8} {<Leaf {1 2 3 5 7 6 9 4 8}> <Leaf {1 2 3 5 7 6 4 8 9}> <Leaf {1 2 3 5 9 6 4 7 8}>}>}>}> <Leaf {1 2 3 4 5 6 7 9 8}>}> <Leaf {1 2 3
;; 4 5 6 7 8 9}> <Node {1 2 3 4 9 6 7 5 8} {<Node {1 9 3 4 2 6 7 5 8} {<Node {9 1 3 4 2 6 7 5 8} {<Leaf {1 9 3 4 2 6 7 5 8}> <Node {4 1 3 9 2 6 7 5 8} {<Leaf {9 1 3 4 2 6 7 5 8}> <Leaf {4 1 3 7 2 6 9 5 8}> <Leaf {4 1 3 2 9 6 7 5 8}>}>}> <Node {1 3 9 4 2 6 7 5 8} {<Leaf {1 9 3 4 2 6 7 5 8}> <Node {1 3 6 4 2 9 7 5 8} {<Leaf {1 3 9 4 2 6
;; 7 5 8}> <Leaf {1 3 6 4 2 8 7 5 9}> <Leaf {1 3 6 4 9 2 7 5 8}>}>}> <Leaf {1 2 3 4 9 6 7 5 8}>}> <Node {1 2 3 9 4 6 7 5 8} {<Node {9 2 3 1 4 6 7 5 8} {<Node {2 9 3 1 4 6 7 5 8} {<Leaf {9 2 3 1 4 6 7 5 8}> <Leaf {2 3 9 1 4 6 7 5 8}> <Leaf {2 4 3 1 9 6 7 5 8}>}> <Leaf {1 2 3 9 4 6 7 5 8}>}> <Node {1 2 3 7 4 6 9 5 8} {<Leaf {1 2 3 9 4 6
;; 7 5 8}> <Node {1 2 3 7 4 6 5 9 8} {<Leaf {1 2 3 7 4 6 9 5 8}> <Leaf {1 2 3 7 4 6 5 8 9}> <Leaf {1 2 3 7 9 6 5 4 8}>}>}> <Leaf {1 2 3 4 9 6 7 5 8}>}> <Node {1 2 3 4 6 9 7 5 8} {<Node {1 2 9 4 6 3 7 5 8} {<Node {1 9 2 4 6 3 7 5 8} {<Leaf {9 1 2 4 6 3 7 5 8}> <Leaf {1 2 9 4 6 3 7 5 8}> <Leaf {1 6 2 4 9 3 7 5 8}>}> <Leaf {1 2 3 4 6 9 7
;; 5 8}>}>
;; <Node {1 2 3 4 6 8 7 5 9}
;; {<Leaf {1 2 3 4 6 9 7 5 8}>
;; <Node {1 2 3 4 6 8 7 9 5}
;; {<Leaf {1 2 3 4 6 8 9 7 5}> <Leaf {1 2 3 4 6 8 7 5 9}>
;; ★★★<Leaf {1 2 3 4 9 8 7 6 5}>
;; }>
;; }>
;; <Leaf {1 2 3 4 9 6 7 5 8}>}> <Leaf {1 2 3 4 5 6 7 9 8}>}>}>}> {{1 2 3 4 5 6 7 8 9} {1 2 3 4 5 9 7 8 6} {1 2 3 4 5 6 7 9 8} {1 2 9 4 5 3 7 8 6} {1 2 3 4 5 6 9 7
;; 8} {1 2 3 4 9 5 7 8 6} {1 2 3 4 9 6 7 5 8} {1 9 2 4 5 3 7 8 6} {1 2 3 9 5 6 4 7 8} {1 9 3 4 2 5 7 8 6} {1 2 3 9 4 5 7 8 6} {1 9 3 4 2 6 7 5 8} {1 2 3 9 4 6 7 5 8} {1 2 3 4 8 5 7 9 6} {1 2 3 4 6 9 7 5 8} {9 1 2 4 5 3 7 8 6} {9 2 3 1 5 6 4 7 8} {1 5 2 4 9 3 7 8 6} {9 1 3 4 2 5 7 8 6} {1 3 9 4 2 5 7 8 6} {9 2 3 1 4 5 7 8 6} {1 2 3 5 9
;; 6 4 7 8} {9 1 3 4 2 6 7 5 8} {1 2 3 7 4 5 9 8 6} {1 3 9 4 2 6 7 5 8} {9 2 3 1 4 6 7 5 8} {1 2 3 4 8 5 9 7 6} {1 2 3 7 4 6 9 5 8} {1 2 9 4 6 3 7 5 8} {1 2 3 4 8 5 7 6 9} {1 2 3 4 6 8 7 5 9} {4 1 2 9 5 3 7 8 6} {2 9 3 1 5 6 4 7 8} {1 5 2 9 4 3 7 8 6} {4 1 3 9 2 5 7 8 6} {2 9 3 1 4 5 7 8 6} {1 9 3 5 2 6 4 7 8} {1 5 2 4 3 9 7 8 6} {1 3
;; 5 4 2 9 7 8 6} {4 1 3 9 2 6 7 5 8} {2 9 3 1 4 6 7 5 8} {1 5 2 4 8 3 7 9 6} {1 2 3 7 4 5 8 9 6} {1 2 3 9 8 5 4 7 6} {1 2 3 5 6 9 4 7 8} {1 3 6 4 2 9 7 5 8} {1 9 2 4 6 3 7 5 8} {1 2 3 4 8 9 7 6 5} {1 2 3 5 7 6 4 9 8} {1 2 3 7 4 6 5 9 8} {1 2 3 4 6 8 7 9 5}}]
;; 上記bugはmyMapを使用して直った
;; > nth(8, iterate(nextTreeAndStacE, (initTreeE, initStacE)))
;; [<Node {1 2 3 4 5 6 7 8 9} {<Node {1 2 3 4 5 9 7 8 6} {<Node {1 2 9 4 5 3 7 8 6} {<Node {1 9 2 4 5 3 7 8 6} {<Node {9 1 2 4 5 3 7 8 6} {<Leaf {1 9 2 4 5 3 7 8 6}> <Node {4 1 2 9 5
;; 3 7 8 6} {<Leaf {9 1 2 4 5 3 7 8 6}> <Node {4 1 2 7 5 3 9 8 6} {<Leaf {4 1 2 9 5 3 7 8 6}> <Leaf {4 1 2 7 5 3 8 9 6}>}> <Node {4 1 2 5 9 3 7 8 6} {<Leaf {4 9 2 5 1 3 7 8 6}> <Leaf
;; {4 1 2 9 5 3 7 8 6}> <Leaf {4 1 2 5 3 9 7 8 6}> <Leaf {4 1 2 5 8 3 7 9 6}>}>}>}> <Leaf {1 2 9 4 5 3 7 8 6}> <Node {1 5 2 4 9 3 7 8 6} {<Leaf {1 9 2 4 5 3 7 8 6}> <Node {1 5 2 9 4 3 7 8 6}
;; {<Node {9 5 2 1 4 3 7 8 6} {<Leaf {5 9 2 1 4 3 7 8 6}> <Leaf {1 5 2 9 4 3 7 8 6}>}> <Node {1 5 2 7 4 3 9 8 6} {<Leaf {1 5 2 9 4 3 7 8 6}> <Leaf {1 5 2 7 4 3 8 9 6}>}> <Leaf {1 5 2 4 9 3 7 8 6}>}>
;; <Node {1 5 2 4 3 9 7 8 6} {<Node {1 5 9 4 3 2 7 8 6} {<Leaf {1 9 5 4 3 2 7 8 6}> <Leaf {1 5 2 4 3 9 7 8 6}>}> <Node {1 5 2 4 3 6 7 8 9} {<Leaf {1 5 2 4 3 9
;; 7 8 6}> <Leaf {1 5 2 4 3 6 7 9 8}>}> <Leaf {1 5 2 4 9 3 7 8 6}>}> <Node {1 5 2 4 8 3 7 9 6} {<Node {1 5 2 4 8 3 9 7 6} {<Leaf {1 5 2 9 8 3 4 7 6}> <Leaf {1 5 2 4 8 3 7 9 6}>}>
;; <Node {1 5 2 4 8 3 7 6 9} {<Leaf {1 5 2 4 8 9 7 6 3}> <Leaf {1 5 2 4 8 3 7 9 6}>}> <Leaf {1 5 2 4 9 3 7 8 6}>}>}>}> <Leaf {1 2 3 4 5 9 7 8 6}>}> <Leaf {1 2 3 4 5 6 7 8 9}>
;; <Node {1 2 3 4 9 5 7 8 6} {<Node {1 9 3 4 2 5 7 8 6} {<Node {9 1 3 4 2 5 7 8 6} {<Leaf {1 9 3 4 2 5 7 8 6}> <Node {4 1 3 9 2 5 7 8 6} {<Leaf {9 1 3 4 2 5 7 8 6}>
;; <Node {4 1 3 7 2 5 9 8 6} {<Leaf {4 1 3 9 2 5 7 8 6}> <Leaf {4 1 3 7 2 5 8 9 6}>}> <Node {4 1 3 2 9 5 7 8 6} {<Leaf {4 9 3 2 1 5 7 8 6}> <Leaf {4 1 3 9 2 5 7 8 6}>
;; <Leaf {4 1 3 2 5 9 7 8 6}> <Leaf {4 1 3 2 8 5
;; 7 9 6}>}>}>}> <Node {1 3 9 4 2 5 7 8 6} {<Leaf {1 9 3 4 2 5 7 8 6}> <Node {1 3 5 4 2 9 7 8 6} {<Leaf {1 3 9 4 2 5 7 8 6}> <Node {1 3 5 4 2 6 7 8 9} {<Leaf {1 3 5 4 2 9 7 8 6}>
;; <Leaf {1 3 5 4 2 6 7 9 8}>}> <Node {1 3 5 4 9 2 7 8 6} {<Leaf {1 9 5 4 3 2 7 8 6}> <Leaf {1 3 5 9 4 2 7 8 6}> <Leaf {1 3 5 4 2 9 7 8 6}> <Leaf {1 3 5 4 8 2 7 9 6}>}>}>}>
;; <Leaf {1 2 3 4 9 5 7 8 6}>}> <Node {1 2 3 9 4 5 7 8 6} {<Node {9 2 3 1 4 5 7 8 6} {<Node {2 9 3 1 4 5 7 8 6} {<Leaf {9 2 3 1 4 5 7 8 6}> <Node {2 3 9 1 4 5 7 8 6} {<Leaf {2 9 3 1 4 5 7 8 6}>
;; <Leaf {2 3 5 1 4 9 7 8 6}>}> <Node {2 4 3 1 9 5 7 8 6} {<Leaf {2 9 3 1 4 5 7 8 6}> <Leaf {2 4 3 9 1 5 7 8 6}> <Leaf {2 4 3 1 5 9 7 8 6}> <Leaf {2 4 3 1 8 5 7 9 6}>}>}> <Leaf {1 2 3 9
;; 4 5 7 8 6}>}> <Node {1 2 3 7 4 5 9 8 6} {<Leaf {1 2 3 9 4 5 7 8 6}> <Node {1 2 3 7 4 5 8 9 6} {<Leaf {1 2 3 7 4 5 9 8 6}> <Node {1 2 3 7 4 5 8 6 9} {<Leaf {1 2 3 7 4 9 8 6 5}>
;; <Leaf {1 2 3 7 4 5 8 9 6}>}>
;; <Node {1 2 3 7 9 5 8 4 6} {
;; <Leaf {1 9 3 7 2 5 8 4 6}> <Leaf {1 2 3 9 7 5 8 4 6}> <Leaf {1 2 3 7 5 9 8 4 6}> <Leaf {1 2 3 7 4 5 8 9 6}>
;; }>}>}>
;; <Leaf {1 2 3 4 9 5 7 8 6}>}> <Leaf {1 2 3 4 5 9 7 8 6}> <Node {1 2 3 4 8 5 7 9 6} {<Node {1 2 3 4 8 5 9 7 6} {<Node {1 2 3 9 8 5 4 7 6} {<Node {9 2 3 1 8 5 4 7 6} {<Leaf {2 9 3 1 8 5 4 7 6}>
;; <Leaf {1 2 3 9 8 5 4 7 6}>}> <Leaf {1 2 3 4 8 5 9 7 6}> <Node {1 2 3 8 9 5 4 7 6} {<Leaf {1 9 3 8 2 5 4 7 6}> <Leaf {1 2 3 9 8 5 4 7 6}> <Leaf {1 2 3 8 5 9 4 7 6}> <Leaf {1 2 3 8 7 5
;; 4 9 6}>}>}> <Leaf {1 2 3 4 8 5 7 9 6}>}> <Node {1 2 3 4 8 5 7 6 9} {<Node {1 2 3 4 8 9 7 6 5} {<Node {1 2 9 4 8 3 7 6 5} {<Leaf {1 9 2 4 8 3 7 6 5}> <Leaf {1 2 3 4 8 9 7 6 5}>}>
;; <Leaf {1 2 3 4 8 5 7 6 9}>
;; ★★★<Node {1 2 3 4 9 8 7 6 5} {
;; <Leaf {1 9 3 4 2 8 7 6 5}> <Leaf {1 2 3 9 4 8 7 6 5}> <Leaf {1 2 3 4 8 9 7 6 5}> <Leaf {1 2 3 4 6 8 7 9 5}>
;; }>}> <Leaf {1 2 3 4 8 5 7 9 6}>}>
;; <Leaf {1 2 3 4 9 5 7 8 6}>}>}>}> <Node {1 2 3 4 5 6 7 9 8} {<Node {1 2 3 4 5 6 9 7 8} {<Node {1 2 3 9 5 6 4 7 8} {<Node {9 2 3 1 5 6 4 7 8} {<Node {2 9 3 1 5 6 4 7 8}
;; {<Leaf {9 2 3 1 5 6 4 7 8}> <Node {2 3 9 1 5 6 4 7 8} {<Leaf {2 9 3 1 5 6 4 7 8}> <Leaf {2 3 6 1 5 9 4 7 8}>}> <Node {2 5 3 1 9 6 4 7 8} {<Leaf {2 9 3 1 5 6 4 7 8}> <Leaf {2 5 3 9
;; 1 6 4 7 8}> <Leaf {2 5 3 1 6 9 4 7 8}> <Leaf {2 5 3 1 7 6 4 9 8}>}>}> <Leaf {1 2 3 9 5 6 4 7 8}>}> <Leaf {1 2 3 4 5 6 9 7 8}> <Node {1 2 3 5 9 6 4 7 8} {<Node {1 9 3 5 2 6 4 7 8}
;; {<Node {9 1 3 5 2 6 4 7 8} {<Leaf {1 9 3 5 2 6 4 7 8}> <Leaf {5 1 3 9 2 6 4 7 8}>}> <Node {1 3 9 5 2 6 4 7 8} {<Leaf {1 9 3 5 2 6 4 7 8}> <Leaf {1 3 6 5 2 9 4 7 8}>}> <Leaf {1 2 3 5 9 6 4 7 8}>}>
;; <Leaf {1 2 3 9 5 6 4 7 8}> <Node {1 2 3 5 6 9 4 7 8} {<Node {1 2 9 5 6 3 4 7 8} {<Leaf {1 9 2 5 6 3 4 7 8}> <Leaf {1 2 3 5 6 9 4 7 8}>}> <Node {1 2 3 5 6 8 4 7 9} {<Leaf {1 2 3 5 6 9 4 7 8}>
;; <Leaf {1 2 3 5 6 8 4 9 7}>}> <Leaf {1 2 3 5 9 6 4 7 8}>}> <Node {1 2 3 5 7 6 4 9 8} {<Node {1 2 3 5 7 6 9 4 8} {<Leaf {1 2 3 9 7 6 5 4 8}> <Leaf {1 2 3 5
;; 7 6 4 9 8}>}> <Node {1 2 3 5 7 6 4 8 9} {<Leaf {1 2 3 5 7 9 4 8 6}> <Leaf {1 2 3 5 7 6 4 9 8}>}> <Leaf {1 2 3 5 9 6 4 7 8}>}>}>}> <Leaf {1 2 3 4 5 6 7 9 8}>}> <Leaf {1 2 3 4 5 6 7
;; 8 9}> <Node {1 2 3 4 9 6 7 5 8} {<Node {1 9 3 4 2 6 7 5 8} {<Node {9 1 3 4 2 6 7 5 8} {<Leaf {1 9 3 4 2 6 7 5 8}> <Node {4 1 3 9 2 6 7 5 8} {<Leaf {9 1 3 4 2 6 7 5 8}> <Node {4 1 3 7 2 6 9 5 8}
;; {<Leaf {4 1 3 9 2 6 7 5 8}> <Leaf {4 1 3 7 2 6 5 9 8}>}> <Node {4 1 3 2 9 6 7 5 8} {<Leaf {4 9 3 2 1 6 7 5 8}> <Leaf {4 1 3 9 2 6 7 5 8}> <Leaf {4 1 3 2 6 9 7 5 8}> <Leaf {4 1 3 2 5 6 7 9 8}>}>}>}>
;; <Node {1 3 9 4 2 6 7 5 8} {<Leaf {1 9 3 4 2 6 7 5 8}> <Node {1 3 6 4 2 9 7 5 8} {<Leaf {1 3 9 4 2 6 7 5 8}> <Node {1 3 6 4 2 8 7 5 9} {<Leaf {1 3 6
;; 4 2 9 7 5 8}> <Leaf {1 3 6 4 2 8 7 9 5}>}> <Node {1 3 6 4 9 2 7 5 8} {<Leaf {1 9 6 4 3 2 7 5 8}> <Leaf {1 3 6 9 4 2 7 5 8}> <Leaf {1 3 6 4 2 9 7 5 8}> <Leaf {1 3 6 4 5 2 7 9 8}>}>}>}>
;; <Leaf {1 2 3 4 9 6 7 5 8}>}> <Node {1 2 3 9 4 6 7 5 8} {<Node {9 2 3 1 4 6 7 5 8} {<Node {2 9 3 1 4 6 7 5 8} {<Leaf {9 2 3 1 4 6 7 5 8}> <Node {2 3 9 1 4 6 7 5 8} {<Leaf {2 9 3 1 4 6 7 5 8}>
;; <Leaf {2 3 6 1 4 9 7 5 8}>}> <Node {2 4 3 1 9 6 7 5 8} {<Leaf {2 9 3 1 4 6 7 5 8}> <Leaf {2 4 3 9 1 6 7 5 8}> <Leaf {2 4 3 1 6 9 7 5 8}> <Leaf {2 4 3 1 5 6 7 9 8}>}>}> <Leaf {1 2 3 9 4 6 7 5 8}>}>
;; <Node {1 2 3 7 4 6 9 5 8} {<Leaf {1 2 3 9 4 6 7 5 8}> <Node {1 2 3 7 4 6 5 9 8} {<Leaf {1 2 3 7 4 6 9 5 8}> <Node {1 2 3 7 4 6 5 8 9} {<Leaf {1 2 3
;; 7 4 9 5 8 6}> <Leaf {1 2 3 7 4 6 5 9 8}>}> <Node {1 2 3 7 9 6 5 4 8} {<Leaf {1 9 3 7 2 6 5 4 8}> <Leaf {1 2 3 9 7 6 5 4 8}> <Leaf {1 2 3 7 6 9 5 4 8}> <Leaf {1 2 3 7 4 6 5 9 8}>}>}>}>
;; <Leaf {1 2 3 4 9 6 7 5 8}>}> <Node {1 2 3 4 6 9 7 5 8} {<Node {1 2 9 4 6 3 7 5 8} {<Node {1 9 2 4 6 3 7 5 8} {<Node {9 1 2 4 6 3 7 5 8} {<Leaf {1 9 2 4 6 3 7 5 8}> <Leaf {4 1 2 9 6 3 7 5 8}>}>
;; <Leaf {1 2 9 4 6 3 7 5 8}> <Node {1 6 2 4 9 3 7 5 8} {<Leaf {1 9 2 4 6 3 7 5 8}> <Leaf {1 6 2 9 4 3 7 5 8}> <Leaf {1 6 2 4 3 9 7 5 8}> <Leaf {1 6 2 4 5 3 7 9 8}>}>}> <Leaf {1 2 3 4 6 9 7 5 8}>}>
;; <Node {1 2 3 4 6 8 7 5 9} {<Leaf {1 2 3 4 6 9 7 5 8}> <Node {1 2 3 4 6 8 7 9 5} {<Node {1 2 3 4 6 8 9 7 5} {<Leaf {1 2 3 9 6 8 4 7 5}> <Leaf {1 2 3
;; 4 6 8 7 9 5}>}> <Leaf {1 2 3 4 6 8 7 5 9}> ★★★<Leaf {1 2 3 4 9 8 7 6 5}>}>}> <Leaf {1 2 3 4 9 6 7 5 8}>}> <Leaf {1 2 3 4 5 6 7 9 8}>}>}>}> {{1 2 3 4 5 6 7 8 9} {1 2 3 4 5 9 7 8 6} {1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment