Day 5 - Simple and yet still too complex

In today's assignment, it was not very complex to find a solution. But even in a solution you still can make things too complex. Would I've made a small drawing of what I was doing, I could have made my solution even more simple. Also using some of Haskells features helps to clean up the code.

The first thing you have to do is to read in a very long story that you need to convert a letter code into a seat number. Once you drill down to the essence, you will see that basically, the letters represent the 0's and 1's in a binary number. F and B for the row number, L and R for column number. The final seat number is calculated by multiplying the row number by 8 and adding the column number. Your input is a list of all letter codes, and you need to find the maximum seat number. This is my initial solution

convert :: [Char] -> Int
convert = go 64 4 0 0 where
  go :: Int -> Int -> Int -> Int -> [Char] -> Int
  go _ _  c r       []  = r * 8 + c
  go h h2 c r ('L':xs) = go h (h2 `div` 2) c r xs
  go h h2 c r ('R':xs) = go h (h2 `div` 2) (c+h2) r xs
  go h h2 c r ('F':xs) = go (h `div` 2) h2 c r xs
  go h h2 c r ('B':xs) = go (h `div` 2) h2 c (r+h) xs

solve1 = maximum . map convert

Looks quite simple, but as you can see there is quite some duplication, this could be improved. But since this is still a competition I worked on part 2 first. You still have to convert the list again, but now find the missing seat number (which is your seat, since you have lost your number.) Reusing convert this is part 2

findMissing (x:y:xs) | (x + 1) /= y = x
                     | otherwise    = findMissing (y:xs)
                     
solve2 = findMissing . sort . map convert

First, the seat numbers get sorted and then given to a simple recursive function that checks for two seats if they have sequential numbers. Third place in the day, back to 9th overall.

My first 'mistake' was that I treated the rows and columns as separate things. A better look at what was going on binary would have helped. Let me explain what I mean.

First 8 letters are for the Row, the last 3 letters for the column. Lets take this simple example BFBFBFBFRLR, so the row part which binary converts to 10101010, which is 170. The column part is 101 which is 5. So the seat number is 170 * 8 + 5. The trick is in the multiplication and addition. Multiplying shifts the row part three positions to the left. The addition put the 3 column bits in the space created by the shift.

• RRRRRRRR * 8 = RRRRRRRR000 (R are the Row bits)
• RRRRRRRR000 + CCC = RRRRRRRRCCC (C are the column bits)

We could have treated our rows and columns as one binary number, B and R (1), F and L (0). In code, this would already simplify things a lot.

convert :: [Char] -> Int
convert = go 512 0 where
  go :: Int -> Int -> [Char] -> Int
  go _ c       []  = c
  go h c ('L':xs) = go (h `div` 2) c     xs
  go h c ('R':xs) = go (h `div` 2) (c+h) xs
  go h c ('F':xs) = go (h `div` 2) c     xs
  go h c ('B':xs) = go (h `div` 2) (c+h) xs

Much less variables, and also more duplication because there is no difference in rows and columns. Except for the letter and if we add h to c there is no difference for the last 4 lines. We can use this.

convert :: [Char] -> Int
convert = go 512 0 where
  go :: Int -> Int -> [Char] -> Int
  go _ c       []  = c
  go h c (x:xs) = go (h `div` 2) (c + b x) xs where
    b 'R' = h
    b 'B' = h
    b 'L' = 0
    b 'F' = 0

We introduce a really simple function to encapsulate the differences, this could have been done with an if as well, but in this way, it is very concise.

Next optimization is by not starting with the highest bit (512), but treating the highest bit as the lowest and (left) shifting in the lower bits. If our first letter is a '1' we use that. In the next iteration, we multiply what we have so far by 2 (shifting left by 1) and we add 1 or 0 for the next letter. We repeat this process and in the and we have multiplies our first '1' by 512. The second letter by 256 and so on. This eliminates the h variable in our code.

convert :: [Char] -> Int
convert = go 0 where
  go :: Int -> [Char] -> Int
  go c       []  = c
  go c (x:xs) = go (2 * c + b x) xs where
    b 'R' = 1
    b 'B' = 1
    b 'L' = 0
    b 'F' = 0

We have seen this pattern of recursing over each element of our list (in this case the letters) and applying a function on them (taking the result of the previous iteration) in our previous examples. Since this is quite common, there is a function in Haskell for it: foldl, which takes the function and a list as arguments. This cleans up things op even more

convert :: [Char] -> Int
convert = foldl go 0 where
  go :: Int -> Char -> Int
  go c x = 2 * c + b x where
    b 'R' = 1
    b 'B' = 1
    b 'L' = 0
    b 'F' = 0

Compare this version with the first, I am very pleased with it. I hope you are too, please join me for the next day.