Description of the puzzle
This is the third codingame challenge where the enterprise is in danger of dawning towards the surface of an unknown planet, it is at risk of crashing against towering mountains.
We are tasked of Helping Kirk and Spock to destroy the mountains and save the enterprise!
Strategy to solve this puzzle
Passing the mountain in the middle
Easiest way to pass this is to hard code the solution, since there is only one mountain to destroy at xs = 3.
if sx == 3 then putStrLn "FIRE" else putStrLn "HOLD"
Passing the mountain on the right side
Well we can’t obviously use our hard coded solution anymore, so we will use this simple strategy:
As soon as we detect that the ship is above a mountain with any height, we shoot at it.
So basically it’s just “Shoot on sight”.
do m <- mountains let (_,p) = head $ filter (\(h,_) -> h > 0) $ m `zip` [0..] if sx == p then putStrLn "FIRE" else putStrLn "HOLD"
Passing the high mountain in the middle
In the third test we have a mountain in the middle that will need to be shot three times.
Our previous implementation passes this test, so nothing to be done there since shooting on sight as soon as we fly over the mountain is good enough.
Passing all the short mountains
This test we have short mountains everywhere. I didn’t expect the current implementation to pass this test since it’s still a bit naive, but it does !
Again we shoot as soon as we fly over a mountain. With the gun ship reload time we can see that we miss a few times.
Passing mountains with different height
Aha! This time we fail, the reason is that since we focus the first mountain first, we don’t see the big one coming in the middle and we quickly crashes into it. We should focus first on the highest coming one and forget about the lower ones since we still have plenty of time later on to destroy them.
So the solution is quite simple, instead of shooting at sight we now prepare ourselves to shoot at the highest one !
do m <- mountains let (_,p) = head $ filter (\(h,p) -> h > 0) $ sortBy (\(h1,_) (h2,_) -> compare h2 h1) $ m `zip` [0..] if sx == p then putStrLn "FIRE" else putStrLn "HOLD"
Some thoughts
During this challenge I actually go tricked by Haskell laziness !
I Wasted an hour trying to figure out why this piece of code was causing mayhem:
let mountains = replicateM 8 $ do input_line <- getLine let mh = read input_line :: Int return mh (some more code here that does not uses mountains...)
When I ran my solution for the first test (where I used the hard coded strategy), it failed badly.
The console was sending me crazy positions about the mountains and the ship position.
I started to write a message on the codingame forum to complain that this lab was bugged…then I thought…maybe I could try my solution in C#, and the test passed !
So there were a difference in the execution for Haskell and C# when communicating with the console, and the only one I could thought of was: laziness. Haskell is lazy and won’t evaluate an expression until it is really used somewhere.
To better understand laziness, look at this C# code:
// This code will be always executed no matter what
List<int> mountains = new List();
for (int i = 0; i < 8; i++)
{
mountains.Add(int.Parse(Console.ReadLine()));
}
// Some more code that doesn't use mountains
But in Haskell:
-- this will never be evaluated let mountains = replicateM 8 $ do input_line <- getLine let mh = read input_line :: Int return mh (some more code here that doesn't use mountains ...)
This code will never be executed ! Because Haskell is lazy, if we never use the mountains list later on, Haskell won’t bother evaluating this expression since we never used it (which is pretty smart and efficient).
And this was the case in my hard coded solution, I never used the mountains list (which is fine since I just want to hard code the solution and so I don’t want to deal yet with the list of mountains).
Since the mountains list was never evaluated, then my program was never reading the list of mountains heights from the console! Thus, mountains heights were accumulating in the console output leading to the crazy behavior I was getting: Instead of reading the next ship position after each turn, I was getting instead the next mountain height 🙂
The solution to this problem was to force the evaluation of the mountains expression, for example by outputting the list in the debug console temporary for just passing this test with my hard coded solution.
My solution
import System.IO
import Control.Monad
import Data.List
main :: IO ()
main = do
hSetBuffering stdout NoBuffering -- DO NOT REMOVE
-- Auto-generated code below aims at helping you parse
-- the standard input according to the problem statement.
loop
loop :: IO ()
loop = do
input_line <- getLine
let input = words input_line
let sx = read (input!!0) :: Int
let sy = read (input!!1) :: Int
let mountains = replicateM 8 $ do
input_line <- getLine
let mh = read input_line :: Int -- represents the height of one mountain, from 9 to 0. Mountain heights are provided from left to right.
return mh
do
m <- mountains
let (_,p) = head $ filter (\(h,p) -> h > 0) $ sortBy (\(h1,_) (h2,_) -> compare h2 h1) $ m `zip` [0..]
if sx == p then putStrLn "FIRE"
else putStrLn "HOLD"
--hPutStrLn stderr ("pos: " ++ show sx)
-- either: FIRE (ship is firing its phase cannons) or HOLD (ship is not firing).
loop
Conclusion
We are actually starting to reach the point where we need a little bit of thinking for the challenges.
I don’t know yet what to think about Haskell laziness, most of the time you don’t feel it but when things goes wrong it can get pretty hard to figure out why things don’t behave as expected.
