- Be quicker than last year
- Do stupid stuff: not production code
So I did a String-replace on the input so that se -> a, sw -> b, nw -> c, ne -> d. I didn't even use constants,
so here a find variation of the magic-number antipattern
albeit in character form. Anyway, this made the input string easier to handle, with 1 character representing 1 move.
I implemented each line as a Guava's LineProcessor which is a nice fit for this kind of problem. Part 1 is quite
straightforward, where each line ends at a tile that becomes flipped.
Part 2 takes the flipped input and we apply another cool game of Conway-like rules similar to days 11 and 17. This one has an infinite space and this time each tile has 6 sides. Somehow I managed to implement the algorithm without needing to draw on hexagonal graph paper. I think once you settle on a coordinate system and encapsulate the logic to find neighbour coordinates the rest of part 2 falls in to place.
This could be a messy problem. Assuming we store our cups in an array or list:
- Picking up cups at the end of the array would require some cups to be picked from the end and some from the start
- Accessing elements by both their index (to find the next current cup) and by their value (destination list)
Although I suspected this would come back to bite me (although it doesn't always: YAGNI), because there are only 10 cups
in the input I was happy to model as a ring buffer. The JDK doesn't have one of these, but
Commons Collections has a LoopingIterator that does
the job nicely. I stored all of the cups in a LinkedList for insert/deletion speed, and used an additional TreeSet
to be able to easily use it to find the next available lower cup number for the destination cup. Good use of
data-structures here meant that part 1 only needed 1 if-statement which for a complicated algorithm, I was quite pleased
with. The downside is that to shift the cups required a full search of the LinkedList to find the desintation
position.
Part 2 is the same problem scaled up to 10,000,000 turns which the downside just mentioned proved to be a showstopper.
The problem with this puzzle is that it requires index-based access, hash-based access, and insertion/removal
performance. If Java's LinkedList exposed its nodes, it would be easy to hold references to each cup but that isn't
possible. Commons Collections has TreeList that offers good-enough performance for insert/remove and index-based
access but would still require searching the entire list to find the destination. I was quite stuck with this, and it's
the first puzzle I had to get a hint from the AoC Reddit for: and the hint was
to use an additional array to map the cup number to the next cup number. I've Java'ized this idea a bit, and used the
TreeMap class where the key is the cup number, and the value is the next cup number. It is basically a crude linked-
list implementation and it has cut out the need to use indexes altogether. The other nice thing is that the key-set in
a TreeMap is a NavigableSet, meaning I could use the same method as part 1 to find the lower cup value. Although
I was quite pleased with my part 1 solution, the part-2 solution is simpler and only uses 1 million-sized collection
instead of 2. I've left both solutions in the class anyway.
Part 1 can be implemented as described. Part 2 is a fun recursive puzzle, and has an additional infinite-game-
prevention check. I originally used Java's hashCode() to hash the two decks but I was worried it would not be unique
enough so I ended up writing a custom hash key in the course of hunting for a bug that turned out to be something else
anyway.
This is another eliminator/inferring puzzle, like day 16. The algorithm is quite similar to 16 but an initial step is also needed: an allergen can only belong to a single ingredient, so when an allergen is listed multiple times, I can intersect the ingredients of the 2 allergens to reduce the possibilities. Part 1 is to deduce the ingredients that cannot have an allergen, and part 2 is to deduce the allergen/ingredient links. I unknowingly did part 2 as part of the part 1 solution anyway, so only a little refactoring was required.
I was contemplating using Parboiled (see day 2) again today but then it struck me that the syntax rules are very
simple, with only sequences and choices. As a bit of a joke I tried expanding out rule 0 fully into a single regular
expression. I used the super-useful StringSubstitutor
from Apache Commons Text library. It was quite easy to load a
HashMap with the rules: replace all of the rule number references in each rule with variables:
12 | 16 -> ${12} | ${16}, and then remove all whitespace. For part 1 the resulting regular expression was over 4000
characters and I didn't expect it to work at all, but it ran in 14ms. In part 2 rules reference themselves. Recursive
parse-rules can usually be converted into rules that use repetition:
Rule 8: 42 | 42 8
=> 42
=> 42 42
=> 42 42 42
(42)+
Rule 8 can be converted very easily. But rule 11 is a bit more tricky:
Rule 11: 42 31 | 42 11 31
=> 42 31
=> 42 42 31 31
=> 42 42 42 42 31 31 31 31
=> 42 42 42 42 42 31 31 31 31 31
It can be represented by a sequence of 42s then the same number of 31s. This could be done via backreferences (I
think) but I would have to calculate the group number, which is not impossible, but instead I decided to cheat slightly.
And the puzzle input almost invites it by suggesting to only write a program that will handle the input, not any case.
So I replaced rule 11 with this:
42 31 | 42 42 31 31 | 42 42 42 42 31 31 31 31
(spaces added for easy reading). Of course, I had no idea whether 1 or 100 levels would be enough. Instead of
hardcoding it, I generated the regex using a parameter, then used JUnit 5's @ParameterizedTest to run the part 2
problem with sequential parameters. It was only 4 levels before the output stopped increasing. The generated regex
for part 2 is 30,009 characters.
Left-to-right expression parsing in part1? No need to construct a parser, I can tokenize and do the calculation in a
single pass. There are only single digits in the input and tests, so the parsing was kept to a minimum: I removed all
the spaces and split by character. Part 2 was a bit more complex, and different enough that I didn't end up reusing any
code from part 1. The reverse-precendence of multiply/addition foiled any plans of passing the entire input through an
expression engine. I'd already used Parboiled in Day 2, so I wasn't going to repeat it but it would have been a good
option for this puzzle. Instead I decided to hand-code a bottom-up parser evaluator StringBuilder's, splitting,
regular-expressions (first time I've used Regex in AoC-2020). I compute the inner-most bracketed part of the
expression and replace the evaluated section in the StringBuilder, then move outwards, as shown below. It's a bit
unrefined but it was fun to see the expression being reduced in a similar way to how a human would solve it.
8*6+(5*(3+2*8+2+7+4)+(7+5*6)*9)
8*6+(5*(3+2*8+2+7+4)+72*9)
8*6+(5*105+72*9)
8*6+7965
This is quite similar to day 11 and I could have used a similar solution, but I've done something better. At first,
the problem seems quite complicated, but the infinite grid acutally makes it simpler. The first leap I made is that I
only need to store active cubes. Using a Set of Cubes. Each cycle, I just iterate the enabled cubes and copy any
the pass the enabled-rule to a second Set. Any neighbours of the cube in question that aren't enabled (in the original
Set), I then apply the inactive-rule after getting their neighbours, and add any that pass the rule to the second
Set. The second Set is overwritten to be main Set, and is repeated for 6 cycles.
For part 2 I was expecting something like day-11 part 2, but instead the grid is expanded to 4-dimensions. My algorithm works for part 2 as well, I've just used a different Cube model. This solution does not scale well. Part 2 takes 14s on my laptop; the same cubes are processed more than once on each cycle which may be the problem, or the algorithm may be O(n4) for part 2.
The example steps for part 1 seems to produce a different result than I expect. Before any cycles:
z=0
.#.
..#
###
After 1 cycle:
z=0
#.#
.##
.#.
Surely the bottom-right cube has two enabled neighbours and should remain enabled? Nevertheless, the solution produces the right answer.
This was my favourite puzzle so far. It's a process of a number of different elimination rules. I created a data
structure, it's a bit clumsy - it's a Map of Sets, where key=field name, value=a set of the possible fields
(numbers) on a ticket that this could be valid for. The first (which is all of part 1), is to apply the rules to every
field on the ticket, and tickets that contain field values that don't pass any of the rules can be discarded. The
second elimination is to eliminate any field-name->field-number mappings that don't pass their corresponding rules. The
third elimination is to check whether there are any fields that only have 1 possible field number left, and eliminate
that field number from every other field mapping. Now at this point I was expecting to still have to deal with some
unresolved field mappings, and to have to do some inferencing using a tree search. But actually, these 3 eliminations
were enough to reduce the possible mappings to a one for each field.
For Part 1, I just implemented the algorithm at face value, keeping previous spoken values in a list, and searching for the index of the last 2 occurrences. This algorithm would have worked with part 2, but was too slow. I kept the part-1 implementation and wrote a different algorithm. This uses a HashMap to store a spoken value with the turn it was spoken in. I avoided needing to search for the second-last occurrence by keeping the previous spoken value in a variable instead. This algorithm is a bit more complicated in that there are numerous places where off-by-one bugs can creep in, and each iteration of the loop performs the write of the previous turn's value and the calculation of the next turn.
It would be quite easy to do this with a for-loop through a binary number represented as a String, in effect modelling a binary number as a String. I decided to try doing it with genuine bit masks however. In part 1, the mask is made up of the X characters, that must remain untouched, and the specified bits that must overwrite the corresponding bits in the value. I did this using two bitmasks derived from the supplied mask: one results in the non-"X" bits being cleared when AND'd with the value, and another that results in the non-"X" bits in the value being set to the same as the mask when OR'd with the result of applying the first mask.
Part 2 is subtly different. The specified bits in the mask must be OR'd, but the "X"-bits (floating) must overwrite those in the value. This I did with 3 masks: the first to clear the X-bits of the value, The second to apply one of the X-bit permutations to the value, and the third to OR the specified bits.
Bit of a vanilla solution, today, there is nothing particularly insightful or interesting to say!
This is a nice one. It is deceptively straightforward, but the implementation details, especially in part 2, benefit
from some finer grained unit tests than just the provided test inputs, because there are lots of moving parts that can
go wrong. As ever, I've over-engineered this solution to make it more fun. The rules about flipping occupied to
unoccupied status are a good match for a decision-table. The fine multi-matcher
library calls itself a rules engine, but I've used it before for a decision-table problem and it worked well. I like
that it's strongly typed unlike most other rules engines I've seen in Java, and I really like that attributes ("facts"
in some other rules engines) aren't restricted to being Java Bean properties, but are Java 8 Functions of the input.
So, to create our rules engine ("classifier", in multi-matcher speak), we need to create some data (attributes) and some rules ("constraints") to act on those attributes. The attributes need to be simple data types, and rules are simple operators (equals, greater-than, ...). A "not-equals" would be very useful, as would a few more advanced classifier rules, or some examples of adding custom rules. So, our attributes are as follows. The first two return ints and the rest booleans:
.withAttribute("thisSeat", this::thisSeat)
.withAttribute("countOccupied", this::countOccupied))
.withAttribute("above", this::aboveOccupied)
.withAttribute("below", this::belowOccupied)
.withAttribute("left", this::leftOccupied)
.withAttribute("right", this::rightOccupied)
.withAttribute("aboveLeft", this::aboveLeftOccupied)
.withAttribute("aboveRight", this::aboveRightOccupied)
.withAttribute("belowLeft", this::belowLeftOccupied)
.withAttribute("belowRight", this::belowRightOccupied)
... and some rules to act on the data.
MatchingConstraint.<String, Integer>named("becomes empty")
.eq("thisSeat", SeatingArea.occupied)
.ge("countOccupied", visibleOccupied)
.classification(SeatingArea.empty)
.build(),
MatchingConstraint.<String, Integer>named("becomes occupied")
.eq("thisSeat", SeatingArea.empty)
.eq("above", false)
.eq("below", false)
.eq("left", false)
.eq("right", false)
.eq("aboveLeft", false)
.eq("aboveRight", false)
.eq("belowLeft", false)
.eq("belowRight", false)
.classification(SeatingArea.occupied)
For part 2, the rules are a bit different. I refactored so the attributes Functions to be abstract methods, and
wrote separate implementations for leftOccupied and friends. To make things more interesting, I decided to store the
seating area as a 1D array using row-major ordering and it was this that caused most of my bugs :-) The solution has
quite a nice design, although there are algorithms and duplication that I wouldn't normally leave if it were
production code.
You have to read the puzzle carefully for part 1 because there is some behaviour at the beginning and end of the sequence that isn't obvious. In part 1, the only valid chain that uses every adapter is in ascending order. I sort the list of numbers and counted the number of differences between subsequent elements that is 1 or 3. Part 2 is an interesting puzzle. I did this on day 15, and I'd seen a meme on Reddit that implied that a recursive-tree algorithm was the wrong way to solve it, so I'd already came at this with a preconception, and I spent too much time thinking of a non-tree solution. But actually, a recursive tree solution is a good solution and is O(n) (excluding the sort).
Using the first example from the puzzle, our tree looks like this:
Basically, a path, but with branches that skip nodes. The part-2 algorithm is a fairly simple depth-first recursion, that counts the number of paths that reach the end-node. This is ok for the test input, but is extremely slow (never finishes) for the solution input for day-10, which has 102 numbers. I used some caching (I can't really call it a memoize as it's not done functionally) to add a dynamic programming optimization into the recursive tree. The cache is keyed on the previous node's rating but is stored on the node, so effectively the key is previous-rating and current-rating. It stores the result of traversing through the subnodes of a particular node. Interestingly, my first iteration only keyed on the current node (not combined with the previous rating) and all of the test data and the input data passed. I don't know if that was because the organisers have tried not to make the input data too complicated or whether my input was just like that.
For part 1, I used the sliding-windowing feature from the excellent Proton Pack
library. I've used a window of size 25 (5 for the example test) and compared the sum of the window'ed with the
subsequent number in the sequence. For part 2, initially I wrote a brute-force algorithm. It would take a sum of
every possible combination of window-size and position. Despite the brute-force, it still took only 2s to find the
answer, but nevertheless I don't usually like to use this technique (especially as Day8 was also a brute-force), so I've
written a faster solution using the prefix-sum data structure. I've ran both solutions 100 times to compare run times.
The prefix-sum algorithm is 219x faster. 
This took me back to AoC 2019 and the IntCode runtime which was great fun. This language is much simpler however. I've
done nothing clever, stupid, nor I have I used any new libraries today. In part 1, my program updates a set of "seen"
instructions, and upon each instruction will check and throw a InfiniteLoopException if it encounters an instruction
that has been ran before. For part 2, I refactored my ProgramRunner class so it would handle both parts. It's a
brute force algorithm, that, one at a time, swaps a JMP and NOP instruction and rerunning the program until an
InfiniteLoopException is not thrown. This is possibly the first time I've ever used the new Pattern Matching
instanceof experimental feature in Java 14 in actual code. I've also used the new switch expression, although my
IntelliJ formatting rules seem to have messed that up.
This is a nice parsing and tree/recursion problem rolled into one (although my solution uses neither a tree structure or a recursive algorithm). The parse is slightly more tricky than at first glance; there are four variants of the "contain" part of the sentence, and the colours can be made up of multiple words.
light blue bags contain 1 bright yellow bag.
blue bags contain 3 yellow bags.
blue bags contain 1 yellow bag, 5 green bags.
blue bags contain no other bags.
I used Commons Lang's StringUtils to chop up the line and extract the numbers and colours.
The first part is to count the number of ancestors of a node (a bag). A node can have multiple parents but there are no circular dependencies. The second part is to count the children, where each level multiplies the previous level. The concept is simple, but it's very easy to cause yourself a headache with the multiply, especially at the top and bottom of the tree.
Super-succinct Stream/reduction while being reasonably readable solutions for both parts, today. For part 1, I've used the same Guava double-line splitter technique as in Day 4. Then I took each multiline group, removed all the whitespace and split into distinct characters, then count the elements. Part 2 is similar, but we need to preserve characters per-line, I mapped each line (person) in the group to a set of its characters, then reduced the sets into a single set using an intersection. The count is the number of characters common to every person in the group. I was expecting a tough one today, but the difficulty has regressed!
The difficulty level has taken a step up today. It's the first problem that the algorithm can be implemented at face-
value, as described, and that also has a shorter and simpler solution. At first I tried cheekily submitting the highest
ID based on being in the back-most row and right-most column but they hadn't left that gap open. With a boarding
pass ID, I noticed they follow the same counting pattern as a binary number: FFFF,FFFB,FFBF,FFBB,... is equivalent to
0000,0001,0010,0011,.... Similarly, the column section LLL,LLR,LRL,LRR,... is equivalent to 000,001,010,011,....
The row/column numbers are 0-127 and 0-7 and after the calculation is a continuous sequence of integers from 11 to 850.
My solution is to split the row and the column part of the String, then convert the 2 Strings into base-2 numbers, then
do the calculation described in the problem. Part 1 is an unreadable oversized stream pipeline.
For part 2, because we know the ID of every seat, we can just sum them, then compare them to the sum of seat IDs of the seats we've seen in the input. The difference is our seat number.
Part 1 is a bit of a parsing problem. We have to handle passport records that may be split across multiple lines, and that fields can be in any order. I'm still avoiding regular-expressions of course, and I'm not going to repeat the over-engineering parser effort from day 2. The double-newline is an easy way of splitting passport records, then I used Guava's mighty-useful Map Splitter to create a Java Map of key/value pairs. Super-easy parsing with a not-too-horrible overly long stream statement. The validation requirements, although quite wordy in the problem, is really just everything is required except for country-ID.
Part 2 reads like a Bean Validation example from a textbook. I did try to find a nice alternative, but in the end I've
done it with Hibernate Validator. Validation, and testing validation, is not interesting (sorry, validator engineers)
and this part did feel a little bit like doing work. I used Apache Commons BeanUtils to populate a bean instance from
the Map that was parsed. For the height field, which can be in both inches or centimetres, I wanted to use a type with
a length and a unit, so I tried out the Units and Measures library
Indriya. It has a QuantityFormat that works along the same lines as
a SimpleDateFormat. It will parse 150 cm but definitely not 150cm. Even after reformatting the input, it then
did not handle inches as a unit(!). I reverted to using a String type and wrote a custom validator for that field.
This solution is over-engineering again of course, but it was still interesting to wire up Commons-BeanUtils and
Hibernate Validator without Spring involved.
There are 2 insights that can solve this problem:
- The repeating pattern is a sign that you can calculate cycled/wrapped horizontal positions using the modulus operator
- In part 1, the position can be calculated using the line number, width of input, and right-move size
- In part 2, need the down-move size in addition to the above.
In this problem I came across the old checked exception inside a lambda problem. Here I've tried the library Durian which has a few nice ways of dealing with it. Suppressing is fine here :)
In part 2, the input needed to be reset and re-read. I usually use Spring's Resource as an abstraction so I can read
the input as a String (ByteArrayResource) for unit tests or as a classpath file (ClasspathResource). I've replaced
the Resource with Guava's CharSource which is re-readable.
It would be easy to use regex's to extract the min, max, character and password from the input file but today's solution
is stupidly over-engineered. I've used the excellent Parboiled to generate a
parser for the grammar. Parboiled can generate ASTs, and here, for part 1, I've used Parboiled to generate a list of
PasswordEntry objects that have an isValidPart1 method with a simple less-than/greater expression. For part 2, the
same parser works just as well, but there is slightly a different isValidPart2 method.
In part 1, I used the fine combinatoricslib3 to generate 2-combination sets of the input numbers. Then I filtered it for the sum (of the 2-entry set) to be 2020, then multiply the matching combination. For part 2, I decided the same method could be used with a small change: I added a size parameter (=2 for part-1, =3 for part-2) and changed the multiply lambda to a reduce operation that will compute the product of the matching combination.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent