The beginner’s mind

I recently ran across CodinGame which is similar to CodeWars but is framed as a series of games you’re writing the logic for instead of textural problems to solve. Needless to say this appeals to me. Happily they support Haskell so I dove in and started in on the tutorial. Blammo! No problem. Onwards to problem #1 in the easy category… two hours later, I finally had a solution that worked. Now if this had been C# it would have been a 5 minute problem tops, but the point of this kind of exercise is precisely that I’m not working in something familiar. I’ve done a few of the katas on CodeWars in Haskell and while somewhat challenging, the easy problems were indeed pretty straightforward. This problem however was much more difficult because it was framed as an imperative problem and that has a much higher impedance mismatch with the normal way of doing things in Haskell. I figured this might be a good example to point out a very different way of approaching what should be a very easy to visualize problem.

So in this scenario, you have Thor who must be guided to the light of power. At the beginning of the program you’re provided with Thor’s starting x/y coordinates as well as the x/y of the light. You write to standard out a direction in the form of N, S, E, W, NW, NE, SE, SW over and over until Thor reaches the destination (or the run times out after 100 moves). So this seems pretty straightforward, you could keep track of your x/y, increment or decrement it as you move and each iteration compare where you are to the target and output the correct direction accordingly. Easy peasy.

I did start out somewhat in this vein, I knew I wasn’t going to be mutating a global variable but my idea was to have a function that took the current x/y and target x/y and did the comparison and outputted the correct direction. This is doable in Haskell just like in C# although you would use recursion instead of a while loop, but otherwise it’s pretty similar. Thinking about this problem for a moment though, I realized you actually know right from the start how many moves in each direction you will need. Using that you could construct the entire list of moves to get to the target and then all that’s left would be to iterate over that list printing out the values one at a time.

Here is the code listing (also in the screenshot at the bottom for reference). The structure of the functions and the all the input!!xyz lines were provided at the start of the problem.

import System.IO
import Control.Monad

main :: IO ()
main = do
  hSetBuffering stdout NoBuffering -- DO NOT REMOVE
 
  input_line <- getLine
  let input = words input_line
  let lightX = read (input!!0) :: Int -- the X position of the light of power
  let lightY = read (input!!1) :: Int -- the Y position of the light of power
  let initialTX = read (input!!2) :: Int -- Thor's starting X position
  let initialTY = read (input!!3) :: Int -- Thor's starting Y position
 
  -- my code starts here
  let startToTargetX = lightX - initialTX
  let targetToStartX = initialTX - lightX
  let startToTargetY = lightY - initialTY
  let targetToStartY = initialTY - lightY
 
  let count = max (max startToTargetY targetToStartY) (max startToTargetX targetToStartX)
  let vertical = replicate startToTargetY "S" ++ replicate targetToStartY "N" ++ repeat ""
  let horizontal = replicate startToTargetX "E" ++ replicate targetToStartX "W" ++ repeat ""
  let pairs = zip vertical horizontal
  let directions = map (uncurry (++)) (take count pairs)
 
  loop directions

loop :: [String] -> IO ()
loop [final] = putStrLn final
loop (current:rest) = do
  putStrLn current
  loop rest
loop [] = return ()

Each move is potentially some combination of vertical and horizontal movement and I did not know which direction would contain more moves, so I used Haskell’s lazyness to not have to care. I calculated the total number of moves to get to the target, which is simply the maximum of the horizontal and vertical distances. Then I built up a list of instructions for both directions and appended infinite empty strings to the end. I passed both the horizontal and vertical instruction lists into a zip function that paired them into an infinite list of tuples, and then I took from that list of tuples a number of elements equal to the count I had calculated earlier. Finally for each pair I took the two elements and combined them to build the final string using map. Uncurry for reference, takes a function that normally takes 2 params, and converts it to a function that takes a pair (tuple), that way I can use the standard ++ function with the tuple that got built up by zip.

The main loop function then was just responsible for printing out each value. The first case is matched when there is only one element in the list, which simply outputs that element. The second case is matched when there is at least 2 elements in the list. The final case of

loop [] = return ()

is there just to satisfy the compiler that can’t know that we will never call loop with an empty list, however it will never be executed in this solution.

I’m not claiming this is the best way to do things in Haskell, but it seems vastly more idiomatic than copying an imperative style. Hopefully it’s interesting to see how different a solution can be when you’re working with a different toolbox.