Skip to content
Create a gist now

Instantly share code, notes, and snippets.

Embed URL


Subversion checkout URL

You can clone with
Download ZIP
Escape from Zurg puzzle
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
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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.