+ print $ part2 (fst armies) (snd armies)
+
+
+part1 :: Army -> Army -> Int
+part1 immuneArmy infectionArmy = uncurry remainingUnitCount endState
+ where endState = battle immuneArmy infectionArmy
+
+
+part2 immuneArmy infectionArmy = (minimalBoost, part1 immuneArmy' infectionArmy)
+ where boostUpper = findSuccessfulBoost 1 immuneArmy infectionArmy
+ minimalBoost = boostSearch 0 boostUpper immuneArmy infectionArmy
+ immuneArmy' = applyBoost minimalBoost immuneArmy
+
+
+findSuccessfulBoost boost immuneArmy infectionArmy =
+ if success
+ then boost
+ else findSuccessfulBoost (2 * boost) immuneArmy infectionArmy
+ where success = immuneSuccessWithBoost boost immuneArmy infectionArmy
+
+boostSearch lower upper _ _ | trace ("Searching in " ++ show (lower, upper)) False = undefined
+boostSearch lower upper immuneArmy infectionArmy =
+ if lower == upper
+ then lower
+ else boostSearch lower' upper' immuneArmy infectionArmy
+ where boost = lower + (upper - lower) `div` 2
+ success = immuneSuccessWithBoost boost immuneArmy infectionArmy
+ lower' = if success then lower else boost + 1
+ upper' = if success then boost else upper