A solver for Towers of Hanoi written in Par. Thanks to faiface for helping me figure out how to handle the recursion and other things I was having some trouble with.
Last active
December 3, 2025 00:53
-
-
Save DeedleFake/49505b717b5d4e5c1f9613e9424c18c4 to your computer and use it in GitHub Desktop.
Towers of Hanoi solver in Par.
This file contains hidden or 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
| dec Hanoi : [Nat] List<State> | |
| def Hanoi = [n] Move(box State(n), n, .one!, .three!) | |
| type State = (List<Nat>, List<Nat>) List<Nat> | |
| dec State : [Nat] State | |
| def State = [n] (Nat.Range(1, Nat.Add(n, 1))) (*()) *() | |
| type Pole = either { .one!, .two!, .three! } | |
| dec Move1 : [State, Pole, Pole, dual List<State>] (dual List<State>) State | |
| def Move1 = [state, from, to, yield] do { | |
| let (piece) state = state->State.Pop(from) | |
| let state = piece.case { | |
| .err! => do { Debug.Log("bad") } in state, | |
| .ok piece => state->State.Push(to, piece), | |
| } | |
| yield.item(state) | |
| } in (yield) state | |
| dec Move : [State, Nat, Pole, Pole] List<State> | |
| def Move = [state, n, from, to] chan yield { | |
| yield.item(state) | |
| let (yield: dual List<State>) state: State = Nat.Repeat(Nat.Sub(n, 1)).begin.case { | |
| .end! => Move1(state, from, to, yield), | |
| .step next => do { | |
| let tmp = FindThirdPole(from, to) | |
| let (yield) state = let to = tmp in next.loop | |
| let (yield) state = Move1(state, from, to, yield) | |
| let (yield) state = let from = tmp in next.loop | |
| } in (yield) state, | |
| } | |
| yield.end! | |
| } | |
| dec FindThirdPole : [Pole, Pole] Pole | |
| def FindThirdPole = [p1, p2] p1.case { | |
| .one! => p2.case { .one! => .one!, .two! => .three!, .three! => .two! }, | |
| .two! => p2.case { .one! => .three!, .two! => .two!, .three! => .one! }, | |
| .three! => p2.case { .one! => .two!, .two! => .one!, .three! => .three! }, | |
| } | |
| dec State.Pop : [State, Pole] (Option<Nat>) State | |
| def State.Pop = | |
| let pop = List.Pop(type Nat) | |
| in [(p1, p2) p3, pole] pole.case { | |
| .one! => let (v) p1 = pop(p1) in (v) (p1, p2) p3, | |
| .two! => let (v) p2 = pop(p2) in (v) (p1, p2) p3, | |
| .three! => let (v) p3 = pop(p3) in (v) (p1, p2) p3, | |
| } | |
| dec State.Push : [State, Pole, Nat] State | |
| def State.Push = [(p1, p2) p3, pole, v] pole.case { | |
| .one! => (.item(v) p1, p2) p3, | |
| .two! => (p1, .item(v) p2) p3, | |
| .three! => (p1, p2) .item(v) p3, | |
| } | |
| dec List.Pop : [type a] [List<a>] (Option<a>) List<a> | |
| def List.Pop = [type a] [list] list.case { | |
| .end! => (.err!) *(), | |
| .item(v) list => (.ok v) list, | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment