Codingame puzzle 3 – Kirk’s Quest – The Descent – Haskell Solution

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
Mountain in the middle - 1 Shot
Mountain in the middle – 1 Shot

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
Mountain on a side - 2 Shots
Mountain on a side – 2 Shots

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
Mountain in the middle - 3 Shots
Mountain in the middle – 3 Shots

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
All the mountains - 1 Shot for each
All the mountains – 1 Shot for each

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
Multiple mountains 1
Multiple mountains 1

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.

Codingame Puzzle 2 – Ragnarök – Power of Thor Haskell Solution

Description of the puzzle

In this second codingame puzzle, Thor has lost its hammer and we need to help him find its way back to Mjöllnir !

Strategy to solve this puzzle

Two things need to be done on each steps:

  1. Decide in which direction we should go depending on where we are and where the light is.
  2. Update our position with that new direction.

My solution


import System.IO
import Control.Monad

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.

    input_line <- getLine
    let input = words input_line
    let lx = read (input!!0) :: Int -- the X position of the light of power
    let ly = read (input!!1) :: Int -- the Y position of the light of power
    let tx = read (input!!2) :: Int -- Thor's starting X position
    let ty = read (input!!3) :: Int -- Thor's starting Y position
    loop lx ly tx ty

decide :: Int -> Int -> Int -> Int -> String
decide lx ly tx ty
    | lx > tx && ly == ty = "E"
    | lx < tx && ly == ty = "W"
    | ly > ty && lx == tx = "S"
    | ly < ty && lx == tx = "N"
    | lx > tx && ly > ty = "SE"
    | lx < tx && ly < ty = "NW"
    | ly > ty && lx < tx = "SW"
    | ly < ty && lx > tx = "NE"

update direction tx ty
    | direction == "N" = (tx,ty-1)
    | direction == "NE" = (tx+1,ty-1)
    | direction == "E" = (tx+1,ty)
    | direction == "SE" = (tx+1,ty+1)
    | direction == "S" = (tx,ty+1)
    | direction == "SW" = (tx-1,ty+1)
    | direction == "W" = (tx-1,ty)
    | direction == "NW" = (tx-1,ty-1)
    | otherwise = error direction

loop :: Int -> Int -> Int -> Int -> IO ()
loop lx ly tx ty = do
    input_line <- getLine
    let e = read input_line :: Int -- The level of Thor's remaining energy, representing the number of moves he can still make.

    -- hPutStrLn stderr "Debug messages..."

    -- A single line providing the move to be made: N NE E SE S SW W or NW

    let new = decide lx ly tx ty
    let (ntx,nty) = update new tx ty
    putStrLn  $ new

    loop lx ly ntx nty

Some thoughts

Haskell’s guards make the code really easy to read. I really enjoy the “rectangular” shape of the code which reminds me of truth tables thus it’s easy to quickly see if we handle all cases.

Conclusion

This second puzzle was actually easier for me than the first one. Maybe because in the first one I also had to understand how the whole environment was working, specially how you interact with the tests by using the standard input and output.

Codingame puzzle 1 – Onboarding Haskell solution

Description of the puzzle

This is the first puzzle from codingame.com, in this puzzle we have to defend a planet with a big laser cannon from the invading insectoid alien ships !

Strategy to solve this puzzle

To solve this puzzle we need to find which ennemy is the closest to us and shoot him, the way I’ve solved that is by using the sortBy function to sort ennemies by distance and blast off the closest one 😀

My solution


import System.IO
import Control.Monad
import Data.List

main :: IO ()
main = do
    hSetBuffering stdout NoBuffering -- DO NOT REMOVE

    -- The code below will read all the game information for you.
    -- On each game turn, information will be available on the standard input, you will be sent:
    -- -> the total number of visible enemies
    -- -> for each enemy, its name and distance from you
    -- The system will wait for you to write an enemy name on the standard output.
    -- Once you have designated a target:
    -- -> the cannon will shoot
    -- -> the enemies will move
    -- -> new info will be available for you to read on the standard input.

    loop

loop :: IO ()
loop = do
    input_line <- getLine
    let count = read input_line :: Int -- The number of current enemy ships within range

    let ennemies = replicateM count $ do
        input_line <- getLine
        let input = words input_line
        let enemy = input!!0 -- The name of this enemy
        let dist = read (input!!1) :: Int -- The distance to your cannon of this enemy
        return (enemy,dist)
    do
        en <- ennemies
        let (name,_) = head $ sortBy (\ (_,a) (_,b) -> compare a b ) en
        putStrLn name

    loop

Some thoughts

When you sort values you need to be able to compare them and I really like one implement type comparison in Haskell.

In most languages you will have to implement some interface like

int CompareTo(Object obj)

where the return value acts as following:

Less than zero this instance precedes obj in the sort order.
Zero this instance occurs in the same position in the sort order as obj.
Greater than zero this instance follows obj in the sort order.

For example if you want to compare two cars by year of make  you’d write some code like

int IComparer.Compare(object a, object b)
   {
      car c1=(car)a;
      car c2=(car)b;
      if (c1.year > c2.year)
         return 1;
      if (c1.year < c2.year)
         return -1;
      else
         return 0;
   }

I’ve never really liked the fact that you have to deal with that by using this kind of hack and it always takes me a few seconds to remember what it will mean if I return a negative number or a positive number.

Compare this to the Haskell implementation:


comparer Car {year=c1} Car {year=c2}
    | c1 >= c2 = GT
    | c1 == c2 = EQ
    | c1 <= c2 = LT

in Haskell you get to return meaningful values like: LT,GT and EQ.

Conclusion

I really enjoyed  solving this first puzzle, I’ve played around with the IDE and the user experience is really nice.

This is going to be a really fun way to keep learning more about Haskell since I finished my Edx course.