Last active
July 5, 2023 19:58
-
-
Save righ1113/07496bd006fa8bd3e2e14e7460035607 to your computer and use it in GitHub Desktop.
8パズルは181440通り in Egison, Haskell
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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の共通元は無い | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; > 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}}] | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; > 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