Pages

2020/12/08

Advent of Code 2020 - Day 5

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

This one is a breeze with the right idea. The common part is converting the seats into the numerical IDs. At first sight, it looks like a bisection scheme would fit the description perfectly: keep track of the upper and lower bound, and depending on the letter keep the high or low half-interval until it is reduced to a single number. Do that for the row and repeat for the column. It's not even hard to do, but it can be simplified.

Instead we can notice that the scheme it describes corresponds exactly to decimal encoded binary: each position encodes this half-interval concept by adding or not the corresponding power of two. So the first of the seven digits encoding the row leaves the number encoded with the other six bits in its [0, 63] range if it's 0, or moves it into the [64, 127] range, and so on.

Furthermore, multiplying by 8 is equivalent to shifting three positions to the left; then adding the column part just fills in those three positions. If we take the seat as given, and substitute the letters with 0s (for F, L) or 1s (for B, R), we only need to interpret that as a base-2 int to get the ID.

Part 1

Once we have the IDs, finding the maximum is trivial using the max built-in.

Part 2

Now we need to find the gap in the consecutive IDs, but the start and end are not known.

In reality we know the end, that was part 1. We can calculate the minimum in the same way, then go from minimum to maximum until we find the gap. That would require building a set of IDs to check each value in constant time. And it would be the most efficient approach (linear time to build the set, get minimum and maximum, and then traverse the range). The latest code does this with set operations. The resulting set should contain just one element, per the problem statement.

In the first commit for the day, I did it differently, in O(n log(n)),  by sorting the IDs, the traversing the sorted array looking at each value and the next. When the difference is greater than one, that's our gap.

Advent of Code 2020 - Day 4

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

Another one for parsing and validating.

Part 1

The parsing part is a little more complex than what we have seen so far, as we can no longer assume that a record corresponds to a line. Other than that, it's just colon-separated key, value pairs. So instead of building a record in one go, we start with an empty one, adding key, value pairs as they come until reaching a newline, which marks a record switch.

Two potential pitfalls to look out for. First, remember to add the record still being built at the end of the loop. Second, both at this step, and whenever closing a record and opening a new one, check whether the record has any contents; two consecutive blank lines or a blank line at the end of the file would introduce an empty record otherwise.

The validation in this part just needs to check if a record contains all required fields; once again generator expressions make this condition sound almost as natural language:

all(field in record for field in fields)

Then just go through all the records and count those that are valid.

Part 2

This part makes the validation a little bit more involved by specifying requirements for the values in each field. Just validate each.

Some are straightforward, especially after converting the value into a number. Others require a little more work. Some points of interest:

  • The sets defined at the top of the module allow a quick check of some fields. In particular, the pid field needs to be checked like this to ensure that it has leading zeroes to pad up to 9 digits.
  • Height needs to be treated with care, as the units are not always present, and assuming so may leave an empty string for the numeric part; therefore we require at least four characters, or return there as invalid. After that, it's easy.

Advent of Code 2020 - Day 3

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

A quick and easy one. This exercise consists on traversing a field defined by the input file following a given pattern, and counting how many of the positions traversed contain a '#' character (a tree in the puzzle). The pattern is given by a pair (r, c), meaning that each step advances r rows and c columns, with columns wrapping over if the width is exceeded.

Part 1

We are given a pattern, and we have to count the trees. Parsing the input is trivial and doesn't merit additional explanation.

The traversal itself is not especially complex, either. We update row and column with each step, using modulo arithmetic to easily wrap the columns around, and check if the new position is a tree. We end once we run out of rows.

Part 2

Rinse and repeat, with several patterns. If you were careful to use the condition row < height rather than row != height when checking the stopping condition everything will work, otherwise, some patterns may skip the row where row == height and never end.

Advent of Code 2020 - Day 2

 This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

Still on the warm-up phase, but we are already bringing in regular expressions. The patterns are easy enough to solve with basic string methods, but the regular expressions make it much clearer.

Part 1

We get a file in which each line is a constraint specification followed by a word, and we are asked to count how many lines are consistent (i.e. the word is valid according to the constraint). Each line is of the form:

n-m x: word

Here, n and m are integer numbers, and x is any single letter. The constraint is that the letter given by x must appear between n and m times in word.

So we have two tasks:

  1. Parse the file into paired costraint specifications and words
  2. Evaluate validity of each pair
The first task is straightforward matching on each line the regular expression:

(?P<min>\d+)-(?P<max>\d+) (?P<letter>[a-z]): (?P<pwd>[a-z]+)

We can then use the named groups to retrieve each relevant piece of information (and cast min and max to ints). With this small modification we can directly use the dictionary that we get from match.groupdict() as the specification.

Validation is equally straightforward. We can use a generator expression to compress counting the number of times the letter appears in the word while making it more readable than the equivalent loop:

sum(1 for c in spec['pwd'] if c == spec['letter'])

Compare it with:

total = 0
for c in spec['pwd']:
    if c == spec['letter']:
        total += 1

Part 2

For this part the validation rules change, so we keep the same parsing. The new validation rule is that the letter must appear in exactly one of the two given positions (interpreting n and m as 1-based indices).

The first gotcha is the 1-based indices. Not difficult, but easy to forget. Otherwise the validation seems to be quite direct as a XOR of the conditions that the letter at each of the two positions be the given letter:

(pwd[pos1] == letter) != (pwd[pos2] == letter)

However, this can lead to out-of-bounds errors, so there is some accounting to do before reaching this. If the word is so short that the first position is not even included, then it is not valid; if only the first position is within the word, the word is valid if the letter at that position is the given letter. If both are included, we fall back to the XOR.

Advent of Code 2020 - Day 1

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly. 

The first day is just a warm-up exercise, but still there are some subtleties, specifically in the complexity of possible solutions.

Part 1

The first part reduces to finding a pair of numbers in a list that add up to 2020. I checked the list for duplicates, and there are none, which makes the use of sets a viable option. We will see why this is important in a moment.

The naive approach would be to check each possible pair, which would result in quadratic complexity, not bad, but this can be easily achieved in linear time. By using sets, so that membership checks are constant time, otherwise these would be linear time and we would be back to quadratic.

The solution is taking each value n in the set, and checking whether target - n is in the set. If it does, we have our answer. We return it as n * (target - n) as the requested answer is the product of the numbers.

This requires two linear operations: building the set, and running through it once checking each number (the check is constant time, as mentioned above).

Part 2

The next exercise is finding three numbers that add up to 2020. If we hadn't gone for a linear solution in the first part, we would be looking at a cubic time solution for this one. As it is, we can manage to limit it to quadratic time, by checking for each number n whether there are two numbers in the rest of the set that add up to target - n, and this can be done using the approach from Part 1.

Of course, in all the discussion complexities are worst case. The algorithms will end as soon as the right answer is found, which can happen with the first numbers that it evaluates. In the worst case, it will try all potential combinations to determine that there isn't one that meets the requirements. In that case, the return value will be None.

Advent of Code 2020

 I have followed the Advent of Code site for several years now. I don't usually have the time to fully finish it, as the time required for the latest and hardest exercises becomes more than I can spare for it. But who knows? This year might be different. It has definitely been a very different year so far.

As an additional exercise, I will keep a log of the solutions here; one post per day. The code will be in this GitHub repo, if you want to follow it. The posts will deal with the rationale behind the solutions and the choices made.

There are some general aspects of the repo, that may be relevant to highlight. First, the exercises for each day are in a puzzleXX.py file, where XX is the corresponding day. The puzzle input if needed is in a file with the same name and .in extension. In some cases the puzzle gives a smaller example that is useful for testing, and those have a .in.test extension; since each puzzle has a read_input() method, changing the file that is read there will switch between the full and test input. Remember that the input files are personalized, so using mine will not give you the right answer for you, you'll need to substitute your own input files.

The different aoc.* scripts help in removing boilerplate. aoc.py allows to run specific puzzles and parts, with aoc and aoc.bat being thin wrappers (for Linux and Windows, respectively) so that part p of day d can be run with [./]aoc d p. All puzzles return the expected answer so it can be copied directly.

I will link to the posts for each day below, or you can use the aoc2020 tag to filter them.

Links to posts:


2015/08/12

Solving 0h h1 Puzzles

You might have stumbled across these puzzles, and maybe even suffered from some degree of addiction to them. In case you haven't, here's the gist.

The puzzle consists of a square grid of cells, which can be red or blue. Some of the cells are set to either colour at the begining, while most are blank. The task is to assign red or blue to all cells so that:
  • each row and column has the same number of red and blue cells
  • there are no more than two adjacent cells of the same colour in the same direction (horizontal or vertical)

The rules are deceptively simple; a good measure of reasoning goes into finding the solution, though. As you go through a few of them, patterns emerge. But can the solution be automated?

The large puzzle is a ten by ten grid; with about 20 pre-set, about 80 cells need to be decided. In a brute force fashion, that means about 2^80 combinations, or somewhat over 10^24. Clearly brute force is not going to cut it.

Exploiting the conditions that the solution must meet can add some intelligence. This limits the actual number of combinations, but it forces the algorithm to be a lot more clever when selecting which assignments to make. Enter constraint propagation.

In constraint propagation, the two constraints defined above limit the values that some of the cells can take, wiping out large swaths of combinations at once. Once the constraint propagation gets stuck, the next step is just trying out one or the other colour in one of the remaining cells, and see how it goes from there.

Let's look at the search space as a binary tree, with each level corresponding to one cell, and the two branches are each of the two colours. The procedure becomes:
  1. set the known cells to their colours
  2. propagate the constraints to set as many cells as possible
  3. if all cells get filled or the problem reaches inconsistency (there is no way to meet the constraints), the algorithm is done
  4. otherwise, select one of the remaining cells and arbitrarily assign one colour, and try to solve that (going back to 2, starting a recursion); if this solves the problem, success
  5. otherwise, try the other color (again, going back to 2, starting a recursion); if this solves the problem, again, success
  6. otherwise, the procedure ends, but reporting that the problem is unsolvable

This process recursively explores the binary tree, using constraint propagation as a shortcut whereever possible. In practice, I still have to find a puzzle where more than 10 branching operations are needed, as constraint propagation does most of the heavy lifting.

The solution procedure can be summarized in pseudocode as:

solve(problem):
    propagate_constraints(problem)
    if solved(problem) or infeasible(problem)
        return problem
    cell = get_unset_cell(problem)
    new_problem = problem + set(cell, red)
    candidate_solution = solve(new_problem)
    if solved(candidate_solution)
        return candidate solution
    new_problem = problem + set(cell, blue)
    candidate_solution = solve(new_problem)
    return candidate solution

The recursion is seen clearly in this pseudocode. If the constraint propagation does not directly solve the puzzle, a new problem is created by setting one cell to red, and passed over to the recursive call. If that returns with infeasibility, there is still the option of making it blue. After that, there is nothing else to be done: the cell can only be red or blue.

Up to now I have glossed over the actual constraint propagation. Each of the two constraints will have its own constraint propagation function.

For the first constraint, it is quite simple: cycle through each row and column; if the number of red cells is half the puzzle size, mark all unset cells in the row or column blue, and vice versa. That's all there is to it.

For the second one, a little more care is needed. Cycle through all cells, and for each one (that is not yet set) check:

  • the cells one and two positions above
  • the cells one and two positions below
  • the cell immediately above and the cell immediately below
  • the cells one and two positions to the right
  • the cells one and two positions to the left
  • the cell immediately to the right and the cell immediately to the left

If any of these sets has both cells set to the same colour, the current cell must be assigned the other colour. In practice a little more care is needed, as the cells close to the boundaries will not have all of the sets.

If you are wondering how to put all of this together and make it work, I have built a short Python program that implements this concept. Check it out at GitHub.

If you are looking for a way to solve the puzzles by hand, this is not your best option. Computers are terribly good at the laborious tasks of checking over and over every rule while propagating the constraints, keeping a list of the steps they take and backtracking when they reach a dead end to try a different path down the tree. We humans soon lose track of this even at small depths.

Instead, we can solve puzzles like this by latching onto more complex patterns, and thinking through the combinations that might succeed. It also works, but is much harder to automate.

Next time you want to sautomate the solution of a combinatorial problem where success is defined in terms of the rules that the solution must follow, give constraint propagation a chance. It goes much easier on your CPU than a brute force approach.