public
Created

Haskell solution to Google Code Jam problem BotTrust

  • Download Gist
BotTrust.hs
Haskell
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
-- Haskell solution to Google Code Jam 2011 problem, Bot Trust
-- http://code.google.com/codejam/contest/dashboard?c=975485#s=p0
 
import Data.List (find)
import Data.Maybe (fromMaybe)
import System.Environment (getArgs)
 
data Robot = Blue | Orange
deriving Eq
 
instance Show Robot where
show Blue = "B"
show Orange = "O"
 
data ButtonPress = ButtonPress Robot Int
 
instance Show ButtonPress where
show (ButtonPress robot number) = show robot ++ show number
 
data TestChamber = TestChamber
Int -- blue position
Int -- orange position
[ButtonPress] -- list of moves required
deriving Show
 
whichBot :: ButtonPress -> Robot
whichBot (ButtonPress bot _) = bot
 
position :: ButtonPress -> Int
position (ButtonPress _ p) = p
 
newChamber :: [ButtonPress] -> TestChamber
newChamber = TestChamber 1 1
 
-- Given a TestChamber, returns the number of moves required to solve it
solve :: TestChamber -> Int
solve (TestChamber _ _ []) = 0
solve tc = 1 + solve (step tc)
 
-- Given a TestChamber, returns a new TestChamber representing what the chamber would look like, one move later
step :: TestChamber -> TestChamber
step (TestChamber _ _ []) = error "The test is over. Please assume the party escort submission position."
step tc@(TestChamber _ _ bpbps@(ButtonPress nextBot x : bps)) =
TestChamber b o newBs
where
newBs = if x == positionOf nextBot tc then bps else bpbps
b = nextPositionFor Blue tc
o = nextPositionFor Orange tc
 
-- returns the position the robot is trying to get to (or zero if they're done)
nextPressFor :: Robot -> TestChamber -> Int
nextPressFor robot (TestChamber _ _ bps) =
case find ((robot ==) . whichBot) bps of
Just bp -> position bp
Nothing -> 0 -- It doesn't actually matter what we put here because this robot is done
 
-- returns the next position for the given robot. Equal to its current position, plus -1, 0, or 1
nextPositionFor :: Robot -> TestChamber -> Int
nextPositionFor robot tc
| nextPress == pos = pos
| nextPress < pos = pos-1
| nextPress > pos = pos+1
where pos = positionOf robot tc
nextPress = nextPressFor robot tc
positionOf Blue (TestChamber b _ _) = b
positionOf Orange (TestChamber _ o _) = o
 
main = do
args <- getArgs
case args of
[input,output] -> processFile input output
_ -> putStrLn "error: exactly two arguments needed"
 
processFile input output = do
fileContents <- readFile input
writeFile output (produceSolutionOutput fileContents)
 
produceSolutionOutput fileContents =
unlines $ map showChamber numberedChambers
where fileLines = tail $ lines fileContents
chambers = map lineToChamber fileLines
numberedChambers = zip [1..] chambers
showChamber (i, chamber) = "Case #" ++ (show i) ++ ": " ++ (show $ solve chamber)
 
lineToChamber :: String -> TestChamber
lineToChamber = newChamber . stringsToButtonPresses . tail . words
stringsToButtonPresses :: [String] -> [ButtonPress]
stringsToButtonPresses [] = []
stringsToButtonPresses (botString:posString:rest) =
let bp = (ButtonPress (stringToRobot botString) ((read posString)::Int))
in bp : stringsToButtonPresses rest
stringsToButtonPresses _ = error "Error parsing input"
 
stringToRobot "O" = Orange
stringToRobot "B" = Blue
stringToRobot s = error ("Expected 'O' or 'B', found '" ++ s ++ "'")
 
-- solve tc1 = 6
tc1 = newChamber [ButtonPress Orange 2, ButtonPress Blue 1, ButtonPress Blue 2, ButtonPress Orange 4]
 
-- solve tc2 = 100
tc2 = newChamber [ButtonPress Orange 5, ButtonPress Orange 8, ButtonPress Blue 100]
 
-- solve tc3 = 4
tc3 = newChamber [ButtonPress Blue 2, ButtonPress Blue 1]

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.