移植ついでにNode型の定義をリストの組から組のリストに変えてみた。
リストの組だと長さが異なるリストを許容してしまうことになるが、組のリストならその心配はない。
(追記)現在のF#だと内包表記が遅いみたいなので、内包表記をやめてみた。thx rst76
main.fs
type Point =
{X: int; Y: int;}
static member ( + ) (p: Point, q: Point) = {X = p.X + q.X; Y = p.Y + q.Y;}
static member ( - ) (p: Point, q: Point) = {X = p.X - q.X; Y = p.Y - q.Y;}
type Pair = Point * Point
type Node = Pair list
let move ((f, b) : Pair) (p : Point) : Pair =
(f + p, b - p)
let moves ((pf, pb) : Pair) ((qf, qb) : Pair) : Pair list =
let forward : Point = pf - qf
let left : Point = {X = forward.Y; Y = -forward.X;}
let right : Point = {X = -forward.Y; Y = forward.X;}
List.map (move (pf, pb)) [forward; left; right;]
let nexts (n: Node) : Node list =
match n with
| p1::p0::ps -> List.map (fun p2 -> p2::n) (moves p1 p0)
| _ -> []
let exists (p : Point) (ps : Pair list) =
List.exists (fun (pf, pb) -> p = pf || p = pb) ps
let solve (size: int) : Node list =
let center : Point = {X = size/2; Y = size/2;}
let p0 : Pair = (center, center)
let p1 : Pair = move p0 {X = 0; Y = 1;}
let initial : Node = [p1; p0;]
let atboundary (p : Point) : bool =
(p.X = 0) || (p.X = size) || (p.Y = 0) || (p.Y = size)
let rec solutions (n : Node) : Node list =
match n with
| (pf, pb)::ps when atboundary pf -> [n]
| (pf, pb)::ps when exists pf ps -> []
| p::ps -> List.collect solutions (nexts n)
| _ -> []
solutions initial
printfn "%d" (List.length (solve 8))