Created
July 17, 2012 23:05
-
-
Save FunctionalFirst/3132740 to your computer and use it in GitHub Desktop.
Escape from Zurg puzzle
This file contains 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
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