AOC23 - 3 December
2023-12-3
Today's Challenge Is a tough cookie. Speaking of which, I just finished glazing my last batch of Hazelnut cookies and can finally dedicate myself to a personal treat! First I will solve my daily origami, then this monster of a puzzle:
Ok first things first, let me get ready and copy my folder Structure and boot up elm reactor so I can get started. I got out my calculator and summed up all but the number 58, which is the only number that is not touching special symbols in any directions, just to confirm, if I understood the prompt.
Up until now the solution was relatively easy, and similar because the core of the processing always involved reading line for line, map them to some number and sum them. Which is easily done in a functional language like elm. However this time we need to build a smarter interconnected data structure. Almost like a grid of chars and then check around symbols for any adiacent numbers. This is the final algorithm:
- transform input text to grid of characters
- transform character positions to x, y for simplicity
- locate the positions of special symbols (from what I can see every char except for a-z, digits or ".")
- if we hit an adjacent digit around the symbols puzzle it together to its full value
- Collect all the numbers and sum them
This time I think I am going to draw the grid of characters as little boxed fields under the text input to reflect the domain of our puzzle. Highlighting the fields with special symbols.
There is a lot to do, so let's start with modeling the data.
type alias Position = {x : Int, y : Int}
type CharType = Special Char | Digit Char
type alias CellContent = Maybe CharType
type alias Cell = {pos : Position, content : CellContent}
type alias Grid = List Cell
type Msg = OnInputChange String
type alias Model =
{ result : String
, input : String
, grid : Grid
}
I think this is very straightforward. In terms of Interaction we just have a text input being input (our puzzle input). This puzzle Input is being represented by a Grid, which is a List of Cells each with a position and a Content. The Content is Maybe Chartype. It is Just Digit Char, Just Special Char if it is relevant and Nothing if it is a dot. I think this is the most idiomatic way to model our data. For displaying the Grid as Dom elements I am also directly storing the Grid representation of the text in the program model.
In terms of algorithms we have a few to implement:
parseGrid : String -> Grid
parseGrid str = []
displayGrid : Grid -> Html msg
displayGrid grid = div [] []
processInput : Grid -> Int
processInput grid = 0
Let's parse a grid!
Text Parsing to Grid representation
The last two days I used Regex for text parsing, which turned out in a "Maybe hell" having to resolve each with annoying default values, resulting in a very tedious activity.
Process wise I think I am going to:
- Split each line doing it in an accumulative fashion to keep track of the row index, becoming my Y coordinate
- Then row by row I am parsing each symbol into content for cells again keeping track of the position, becoming the X coordinate
- This will result in a list of cell lists, which I will finally concat to a grid.
parseGrid : String -> Grid
parseGrid str =
String.lines str |>
List.indexedMap parseRow |>
List.concat
parseRow : Int -> String -> List Cell
parseRow rowId str = []
I seriously seriously seriously love functional programming. Look how easy this is to read. Let's try to keep that elegance.
parseRow : Int -> String -> List Cell
parseRow rowId str =
String.toList str |>
List.indexedMap (parseCell rowId)
parseCell : Int -> Int -> Char -> Cell
parseCell rowId posOnRow char =
let
position = {x = posOnRow, y = rowId}
inside =
if Char.isDigit char then Just <| Digit char
else if char /= '.' then Nothing
else Just <| Special char
in
{ pos = position, content = inside }
I think next time I don't even bother writing out my algorithm breakdown, because my elm implementation basically already spells it out for you pretty clearly >.<. We are done with the parsing. Now to check if the representation is correct let's build ourselves a dom grid!.
Building a DOM Grid
So, while thinking this through I noticed that maybe it could come in handy having the width and height of the grid, in terms of how many rows and cells per row we actually have.
type alias Grid =
{ cells : List Cell
, width : Int
, height : Int
}
To get them we just need to count the entries of each list. First height is the number of rows, then width is the number of cells per row in our first rows entry.
parseGrid : String -> Grid
parseGrid str =
let
rows = String.lines str |>
List.indexedMap parseRow
allcells = List.concat rows
gridwidth = List.length <| Maybe.withDefault [] <| List.head rows
gridheight = List.length rows
in
{ cells = allcells
, width = gridwidth
, height = gridheight
}
Now one cigarette later and armed with a fresh cup of herbal christmas tea, let's deal with the rendering of the grid (this is not necessary to solve the puzzle, it is just an added bonus challenge for myself)
Judging from my input I can tell that there is maybe 50+ characters per line, so I will need to check how to fit them all. This is more a frontend challenge, involving css and layouting. I guess I go for flex-box and try to fit them all. Or I use the grid width to determine the max size of a div based on my window width, for now not caring about responsiveness.
Or actually let's just set a fixed size for my entire grid. I am not quite ready to get messy with Browser interaction, Tasks and Subscriptions.
Oh no, my Grid is now a List of Cells, not a List of Rows of Cells. For displaying nested divs, however I need them to be nested ideally. So I will have to account for that.
splitArrayEvery : Int -> List (List a) -> Array.Array a -> List (List a)
splitArrayEvery every listoflists array =
let
remaining = (Array.length array) - every
in
if remaining <= 0 then List.append listoflists <| [Array.toList array]
else
let
newList = List.append listoflists <| [Array.toList <| Array.slice 0 (every - 1) array]
leftOver = Array.slice every ((Array.length array) - 1) <| array
in
splitArrayEvery every newList leftOver
I created a recursive functions that slices an array into parts every X entries. If the input array is smaller than that value it gets appended to the List of List (Array is converted back to a list). This should give me nested rows.
Oh well, thats....
Small.
I might have to rethink how to render it. Also I have one huge div on the bottom. Something went wrong.
I think this is caused by the maxWidth not being a floating point, and therefor having a slight mismatch in the fit by a little offset, causing one of the cells to slip out.
displayRow : List Cell -> Html msg
displayRow cellsInRow =
let
num = List.length cellsInRow
maxWidth = 600 // num
in
div
[style "display" "flex", style "flex-direction" "row"] <|
List.map <| cellsInRow maxWidth
displayCell : Int -> Cell -> Html msg
displayCell width cell =
div
[ style "width" <| (String.fromInt width) ++ "px"
, style "height" <| (String.fromInt width) ++ "px"
, style "border" "1px solid black"
]
[]
Now actually putting some style in and increasing the width of the grid
displayCell : Int -> Cell -> Html msg
displayCell width cell =
let
cellStyle =
case cell.content of
Nothing -> [style "background-color" "grey"]
Just (Digit _) -> [style "background-color" "black", style "color" "white"]
Just (Special _) -> [style "background-color" "yellow"]
content =
case cell.content of
Nothing -> ""
Just (Digit c) -> String.fromList [c]
Just (Special c) -> String.fromList [c]
in
div
( List.append
[ style "width" <| (String.fromInt width) ++ "px"
, style "height" <| (String.fromInt width) ++ "px"
, style "text-align" "center"
, style "padding" "2px"
]
cellStyle)
[text content]
The visualizing of the grid has already paid off! I can see that my Special and Nothing have been flipped.
Why?
...
inside =
if Char.isDigit char then Just <| Digit char
else if char == '.' then Nothing
else Just <| Special char
...
For some reason I inverted the equality check for the dot character.
There we go. This is nice. Let's solve the puzzle now. But before that, I will make dinner. I will probably start to write accessor functions to work with the grid in the domain of coordinates.
Writing accessors for a grid
So first of all, I need to decide if I am going to iterate over the numbers and check if they are next to special symbols, or iterate over the special symbols and look for adjacent numbers. There is also the problem of overlapping matches. When multiple digits of one number are touching a special symbol.
So I think I am going to assemble all the numbers, store their coordinates, check if any of the coordinates have a neighboring symbol. This will also be in line with the visualization, so I don't have a discrepancy in the data structures again. Resulting in this algorithm:
- Collect all digits, and parse them to Int, while storing their associated positions
- For every number's positions iterate and check if they are neighboring a special symbol
- Filter out those that don't touch
- Sum the numbers
Let's start bottom up and implement the logic to get the Neighbor Cells. We start with a central cell, that is surrounded on all sides by other cells. Special cases like corner and edge cells instead return a few Nothing.
getNeighbors : Grid -> Cell -> List (Maybe Cell)
getNeighbors grid cell =
List.map (getNeighbor grid cell) <|
[ (-1, -1), (0, -1), (1, -1)
, (-1, 0), (1, 0)
, (-1, 1), (0, 1), (1, 1)
]
getNeighbor : Grid -> Cell -> (Int, Int) -> Maybe (Cell)
getNeighbor grid cell offset = getCell grid {x = cell.pos.x + (Tuple.first offset), y = cell.pos.y + (Tuple.second offset)}
getCell : Grid -> Position -> Maybe (Cell)
getCell grid pos = List.head <| List.filter (\a -> a.pos == pos) grid.cells
Now this is another level of expressiveness. Not only does this read like English, the code itself is the visual representation of the task. And the maybe type covers all the edge cases.
Grouping Numbers
Next bigger task is to group the digits to numbers and collect their positions. Let's have a look at our grid again and see what features we can observe which we can use for our algorithm. First of all, numbers are written from left to right. So a valid number start has no neighbor on the left. So:
- Find all Cells with digits with no neighbor to the left containing a digit
- For each of these cells navigate to the right until we have no digit neighbor and collect all the digits
- Merge digits and parse to Int
- Collect the Groups cells.
groupDigits: Grid -> List (List Cell)
groupDigits grid =
List.filter (\a ->
(isCellDigit a.content)
&& (getNeighbor grid a (-1, 0)) == Nothing) grid.cells |>
List.map (\a -> scanLineForDigits grid [a])
scanLineForDigits : Grid -> List Cell -> List Cell
scanLineForDigits grid list =
let rightOf = getNeighbor grid (Maybe.withDefault
{pos = {x = -2, y = -2}, content = Nothing }
(List.reverse list |> List.head)) (1, 0)
in
case rightOf of
Nothing -> list
Just cell -> scanLineForDigits grid <| List.append list [cell]
groupToInt : List Cell -> Maybe Int
groupToInt groupOfDigits =
List.map .content groupOfDigits |>
Maybe.Extra.values|>
List.filter (\a ->
case a of
Digit _ -> True
_ -> False) >> List.map unwrapChar |>
String.fromList |>
String.toInt
And with this in place finding the final solution is quite easy
processInput : Grid -> Int
processInput grid =
groupDigits grid |>
List.filter (\a ->
List.any (\cell ->
(getNeighbors grid cell |>
Maybe.Extra.values |>
List.map .content |>
List.filter isCellSpecial |>
List.length) > 0)
a
) |>
List.map groupToInt |>
Maybe.Extra.values |>
List.sum
Let's try it.
I have a huge number as result. If I log my group of digits I see the reason:
Way to big these numbers. So now I have to debug a bit.
Let's get visual again.
...
cellStyle =
case cell.content of
Nothing -> [style "background-color" "grey"]
Just (Digit _) ->
[ style "background-color" <|
if List.any (\a -> List.member cell a) connected
then "green"
else "black"
, style "color" "white"
]
Just (Special _) -> [style "background-color" "yellow"]
...
Good news and bad news. The Visualization shows that my algorithm is correct. That's the good news.
Bad news is, that it takes forever to process because I have multiple nested list calls, and eventho it shows correctly my result is still wrong.
Also my linter in VSCode stopped working. This is getting tedious and it is getting late.
For starters, I changed this function:
groupToInt : List Cell -> Maybe Int
groupToInt groupOfDigits =
List.map .content groupOfDigits |>
List.map unwrapDigit |>
Maybe.Extra.values |>
String.fromList |>
String.toInt
unwrapDigit : Maybe CharType -> Maybe Char
unwrapDigit wrappedDigit =
Maybe.andThen (\a ->
case a of
(Digit c) -> Just c
_ -> Nothing) wrappedDigit
The frustrating thing is, that when I try with the sample input of the prompt, it works:
But I noticed, that except for my lower row, every row is cut short of one cell. So I will investigate that next.
...
newList = List.append listoflists <| [Array.toList <| Array.slice 0 (every) array]
...
That fixed that problem, but still no success. It tells me, I am too high, so I might have false positives.
But no matter how hard I look, I can't spot any mismatches in my visual grid. Finally, found something!
There is a "824591", "978259", "79660" in there. So some edge cases have been stuck together. Let's find out why!
Found it, so theoretically it should stop assembling numbers, but it merges them.
I think I finally found the culprit.
case rightOf of
Nothing -> list
Just cell ->
if not (isCellDigit cell.content)
then list
else scanLineForDigits grid <| List.append list [cell]
I Just check if the right cell is Nothing, but instead it should be anything other than digit.
Well... That fixed my problem but is still not the right solution.
Oh, nevermind, I forgot to remove something I tried out before when filtering the special symbols.
Finally!
Ok, I am going to try to do this one as fast as I can. Filter all the specials for "*" count the adjacent numbers, multiply them and sum them.
What I changed:
...
result = String.fromInt <| (findGears inputGrid |> List.map (\gear -> (Tuple.first gear) * (Tuple.second gear) ) |> List.sum)
...
type alias Gear = (Int, Int)
findGears : Grid -> List Gear
findGears grid =
List.filter (\a -> isCellSpecial (Just '*') a.content) grid.cells |>
List.map (getNeighbors grid)) |>
List.map (\a -> (Maybe.Extra.values a |> List.filter (\a2 -> isCellDigit a2.content) |> List.foldl (collectUniqueDigitCells grid) []) |>
List.filterMap (\a ->
if List.length a == 2
then
let
empty = {content = Nothing, pos = { x = -2, y = -2}}
one = scanLineForDigits grid [Maybe.withDefault empty <| List.head a]
two = scanLineForDigits grid [Maybe.withDefault empty <| List.head <| Maybe.withDefault [] <| List.tail a]
in
Just ( Maybe.withDefault 0 <| groupToInt one, Maybe.withDefault 0 <| groupToInt two)
else Nothing
)
collectUniqueDigitCells : Grid -> Cell -> List Cell -> List Cell
collectUniqueDigitCells grid cellToCheck digitCells =
let
leftMost = getLeftMostDigit grid cellToCheck
in
if List.member leftMost digitCells
then digitCells
else List.append digitCells [leftMost]
getLeftMostDigit : Grid -> Cell -> Cell
getLeftMostDigit grid cell =
let leftOf = getNeighbor grid cell (-1, 0)
in
case leftOf of
Nothing -> cell
Just leftCell ->
if isCellDigit leftCell.content
then getLeftMostDigit grid leftCell
else cell
Its not pretty. But it is also 3am now, so.
Yeah...
Takeaway
Today I learned that often the data structure for solving a problem is not the same as the one needed for representing it. This ties into a very interesting line of thought of mine. Also today I learned the benefit of having the entire frontend ecosystem at my disposal while programming. I could programmatically evaluate the style of elements based on their state in code, layout them and fill them. This sort of expressiveness has been unparalleled for me before. As last note, eventho I said I used the UI part of the challenge to challenge myself, I must say it often helps to reason about a problem and identify patterns.
On the negative side, I learned that modeling your data wrong and losing track of it, can lead to very bad follow-up bugs that are hard to debug. So I should be more thorough with my Type design.
See you on the next challenge!