Skip to content

Instantly share code, notes, and snippets.

@FunctionalFirst
Created July 17, 2012 23:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save FunctionalFirst/3132740 to your computer and use it in GitHub Desktop.
Save FunctionalFirst/3132740 to your computer and use it in GitHub Desktop.
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
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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment