public
Created

Escape from Zurg puzzle

  • Download Gist
gistfile1.fs
F#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
open System
 
let MAX_TIME = 60
 
type Toy =
| Toy of string * int
 
type Direction =
| Start
| End
 
type Move =
| Move of Direction * Toy list
 
module List =
let rec combinations items =
[
match items with
| [] -> ()
| x::xs ->
for y in xs do yield x, y
yield! combinations xs
]
 
let rec Solve cost moves atStart atEnd dir =
seq {
if cost > MAX_TIME then ()
elif Set.isEmpty atStart then yield cost, List.rev moves
else
match dir with
| Start ->
for Toy(_, time) as toy in atEnd do
let move = Move(dir, [toy])
yield! Solve (cost + time) (move :: moves) (Set.add toy atStart) (Set.remove toy atEnd) End
| End ->
let combinations = List.combinations (Set.toList atStart)
for (Toy(_, time1) as toy1), (Toy(_, time2) as toy2) in combinations do
let move = Move(dir, [toy1; toy2])
let toys = set [toy1; toy2]
yield! Solve (cost + (max time1 time2)) (move :: moves) (atStart - toys) (atEnd + toys) Start
}
 
let toys =
set [
Toy("Buzz", 5)
Toy("Woody", 10)
Toy("Rex", 20)
Toy("Hamm", 25)
]
 
Solve 0 [] toys Set.empty End
|> Seq.iter (printfn "%A")

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.