Advent of Code 2020 - Day 23

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 exercise requires tracking the positions of numbers 1 through nine in a circular buffer, starting in the sequence given in the input, and performing 100 moves like this:

• Take the three number following the current one out.
• Select the destination as current number minus one, keep going down if it is not in the buffer (i.e. if it has been taken out), and wrap around to the highest value if you go below the lowest one.
• Insert the three numbers you took out next to the destination number.
• The new current number is the one next to the current one

Part1

We will represent the circular buffer as a deque. We will keep the current number at position 0 as a way to easily track it.

The step function performs one move. We start by looking at which is the current number, then rotate the buffer one place to the left, both updating the current position for the next step and setting the numbers that have to be taken at the beginning of the buffer so we can take them out using popleft. We next find the destination number (keep subtracting one as long as the destination is not in the buffer, i.e. while it is in the taken out triplet, with wraparound), and the corresponding position (index), and insert the numbers right after it. We insert them in reverse order at the same position, but we could also insert them in order incrementing the position with each step.

Part 2

For this part we will take 1,000,000 numbers. The initial ones are scrambled as given in the input, and after that in order. And also we perform 10,000,000 moves.

With these numbers, the approach from part 1 is too slow, it requires too many memory reorganizations when performing the moves.

To solve this we will build a data structure that doesn't require moving the data around: a linked list, where only the references of which number follows which need to be updated, and it can be done locally (in our previous version, taking out the initial numbers requires moving close to the full million numbers, and then all numbers after the destination for each insertion). Although I have to admit that I spent some time looking for a more mathematical approach.

We will create a CircularList class for this specific problem. It will keep a list of nodes, so that the node content (the number) matches the position in the list. Each node contains a value (the number) and a reference to the next node in the list. It will also have a head, a reference to the current number.

Since Python lists are 0-indexed, we will shift all numbers by -1 (it does not change the behaviour), and undo the change afterwards. There is no significant performance penalty: the subtraction need only be made for the initial 9 numbers, as the rest is generated already shifted; and only two numbers of the output need to be converted back.

A different option would be representing the linked list as a dictionary with the numbers as keys, and the successors as values. The way we have it is more explicit on the linked list concept, but the dictionary would be more efficient.

As we are making the class specific to the problem, we will give the initial sequence and the total size as inputs. We generate all the nodes, without connections, and then set the connections. For the first nine we need to follow the initial sequence (modified by the -1), and then they go in order, until the last one which connects back to the first number (not necessarily the first node!).

We build extract and insert methods to make the intent clearer. Inserting is relatively easy: we get the destination node, take its successor for later (the restart), and connect it instead to the head of the list to insert. Then we take the last node of the list we are inserting, and connect it to the restart.

Extraction is a little bit more complicated, but not much. We take the head, and move four steps through the links to record where it will restart. Then we build the extracted list by taking the three nodes following the head, and disconnecting the last of them from its successor. Finally we connect the head to the restart.

With this operations, the step is trivial, and now the problem is solved efficiently enough.

Advent of Code 2020 - Day 22

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 exercise consists of a simulation of a card game. We get as input two decks, each a sequence of integers (the values of the cards), for the two players. We read that in two stages, one per player, skipping the headers (that´s the purpose of the line = next(f) lines). We store the decks as deques, as we will be adding and removing items on both ends. We use appendleft to add the cards, so that the topmost one is at the end (so it can be popped).

Part 1

The game is quite straightforward. We play until one of the decks runs out (the condition for the while). In each step, we remove the topmost card from each deck, compare and put both at the end of the winner's deck. By keeping the same deque objects all the time we can check the winner by checking the ID of the deck (winner is deck1).

Since that is the way we check for the winner, we need to return the deck that still has cards, that's the winner. The line return deck1 or deck2 works exactly like that combining Python's truthiness evaluation and short-circuiting or.

Part 2

We now have a recursive version of the game.

The first difference is that we need to keep track of the states at different stages. We will keep them in a set, and represent each state as a tuple of two elements, each a tuple version of each deck. With that we can check at each step the winning condition of repeating a state.

The other difference is that, when we draw the cards, we check their values against the number of cards in the decks, and if either deck has fewer cards than the value of its current playing card we go into the recursive game. Otherwise, we play the usual game as before.

The recursive game is, as it would appear, just a recursive call to the game. We just need to be careful to use a copy of the decks for the recursive game, and check the winner against these copies.

Advent of Code 2020 - Day 21

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.

In this problem we get some foods (as the list of ingredients) and allergens contained (although some maybe omitted). We will read the input as a list of tuples, one tuple for each food containing the set of ingredients and the set of allergens.

Part 1

This part requires finding out the ingredients that do not contain any allergens. We will do it in two steps.

First, we will find the candidate ingredients for each allergen. We just go over each food, and add its ingredients to the set of candidates for each allergen it contains. The answer is the set of ingredients not in the union of the candidates to all allergens.

Part 2

We now need to identify the sources of each allergen. We will start from the candidates determined in part 1, and apply the same elimination strategy we applied for identifying fields in a previous problem.

Advent of Code 2020 - Day 20

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.

For this problem we get a set of tiles, each a (potentially rotated and/or flipped) fragment of a global image. Each tile is 10x10 with the inner 8x8 actually the image data, while the outer edges are there just to indicate matching of two tiles: to form the global image, the edges of adjacent tiles must match; that means applying different flipping and rotation to each tile to build a coherent whole.

Part 1

For this part we need to identify the corner tiles. We don't need to rebuild the whole image, just find the tiles with edges matching other tiles on two edges. Since we will need to do that for part 2, we will start to create a Tile class, that we will extend later; but if we were just concerned about this part, we wouldn't need this level of complexity.

We will initialize the tiles from the input, with the tile ID and the ten, ten-char lines. We need to keep the ID, keep the inner 8x8 part as the tile itself, and the boundaries. We need to establish a convention for storing the edges, to make sure that we are matching them in the right way (not really important at this stage, but unavoidable when rotating and flipping tiles to build the whole thing). We will store the edges in clockwise order starting at the top, horizontal edges left-to-right and vertical ones top-to-bottom. These directions need to be absolute like this; if we choose relative directions, such as clockwise, the bottom edge of one tile and the top edge of the tile below (for instance) would be stored in opposite directions, and would not match.

We will further consider all edges inverted as potential boundaries, to account for potential flips and rotations. With this, we can pair-wise compare the tiles and look for adjacency, which happens if the intersection of one tiles edges and the potential edges of the other one is non-empty. We use this condition to build an adjacency matrix using a dictionary with each tile ID as key and the set of compatible tiles as value. With this matrix, we just need to take the IDs of the tiles with degree 2 (i.e. the set of compatible tiles has two elements).

Part 2

For the second part we need to find sea monsters in the image, which means we need to assemble the whole image first. We will add some functionality to the tiles to help in this. First, the ability to rotate and flip themselves; these are quite straightforward, but we must take care to properly apply the operation to the edges. Next we will use the adjacency matrix to give each tile links to the tiles it matches with, so it has a direct way to refer to its neighbours.

We will build the image one row at a time. We choose any corner as the top left. The choice is irrelevant; the result of each choice can be converted in one of the others by rotating and/or flipping the image.

We will use the match function to apply the necessary operations to a tile until its top and left match the given tiles, using None for borders. This is as easy as rotating the tile until the top matches its target. If the left does not march like that, a horizontal flip must do the trick.

We match the right position of the initial corner. Then we can fill in the first row; we know the next tile is the right-neighbour of the previous one, and we match it to None and the previous tile.

Next we fill in subsequent rows, each starting with the bottom-neighbour of the first tile in the previous row, matched to that tile and None, and continuing matching to the corresponding tile in the previous row and the previous tile in the current row.

Once we are done, we stitch everything together into a single image.

Now for the monsters. We will define a monster by the positions of '#' characters with respect to the top left position in the 'window' that contains the monster, as well as the window's width and height.

To find the monsters we slide the window over the image, convolution-like, and at each position we check if all the monster positions contain a '#' in the image. If so, we mark those positions.

Since the image may be flipped or rotated we try all combinations until we find one with monsters.

Once we have that, we get the positions of all the '#' characters in the image. The answer to the problem is the size of the difference of the two sets. The difference of the sizes will not work, as there may be overlaps in the monsters.

Advent of Code 2020 - Day 19

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 problem consists of the validation of messages according to a set of nested rules. The simplest are just a string, others are a sequence of rules (which is to be interpreted as the message being partitionable into substrings that match exactly those rules in that order), and the more complex ones include multiple alternative sequences (i.e. at least one of those sequences must match).

Since the numbers of rules is not too large, we will attempt a simple approach to begin with, and refine it if needed. Let's build all potential matching patterns for each rule.

Part 1

We'll start by building a Rule class. It will hold the patterns (once evaluated), a rule 'specification', and a pointer to the set (actually a dictionary) of rules, so it can refer to other rules when evaluating the patterns. It will also provide the overall behaviour, like creating the Rule from the textual specification given in the input, accessing the patterns, and checking for a match. Then we will have subclasses that specialize the evaluation of patterns according to the three types of rules described above.

Reading the input is quite straightforward: in each line the colon separates the key (an int identifying the rule) and the specification fed to the Rule constructor. The resulting rule will be the corresponding value in the ruleset dictionary.

The Rule constructor is a class method that will decide which subclass to use depending on the specification. Each subclass has a different representation of its specification:

• Leaf Rules just have the string they match (stripped from the quotation marks)
• Sequence Rules have a list of the identifiers of the rules they concatenate
• Alternative Rules have a list whose elements (the alternatives) are in turn lists like those in Sequence Rules

Evaluation of the patterns is similarly different for each rule type, but they all generate a set containing all messages matching the rule.

Leaf Rules generate just one pattern, the string they match.

For Sequence Rules, we go back to itertools.product to generate the Cartesian product of patterns matched by each rule in the sequence.

For Alternative Rules, we apply the same procedure as for Sequence Rules on each alternative, and join those together (actually, we could just have Alternative Rules,  where Sequence Rules would have just one alternative).

Once all rules are built, we take rule zero, which is the one we need to check, and build its patterns (this is done implicitly in the first match, and cached for subsequent ones; it will recursively build the patterns of all rules that are referenced from it). Then we check the match against the messages.

The matching is trivial: is the message in the set of matching messages?

Part 2

This part introduces loops in two of the rules. Handling the general case would be complex, but we can examine the specific rules given here and notice what they mean.

Our root rule is (8, 11); rule 8 is (42 | 42, 8); rule 11 is (42, 31 | 42, 11, 31). So rule 8 is one or more 42s, and rule 11, though a little harder to see, is one or more 42s followed by the same number of 31s. So if we take this rule 11, and prepend to it at least one 42, our root rule becomes one or more 42s followed by one or more 31s, with strictly fewer 31s than 42s.

Since everything else is the same, we can look at the results of part 1 to see that all patterns for 42 and 31 are of the same length, so we can divide the message in chunks of that length. The it's a matter of checking that we have one or more chunks that match 42, that they cover more than half of the message, and that the rest match 31.

For additional efficiency, we can discard any message that doesn't divide neatly into these chunks.

Advent of Code 2020 - Day 18

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 problem is basically evaluating expressions with varying operator precedence rules. It screams abstract syntax trees (ASTs), but I am a little out of my depth there, not my area of expertise. I'm sure that there are more elegant ways to solve this, potentially using the , but I decided to build quite an ad-hoc approximation.

Part 1

Addition and multiplication have the same precedence for this part, operations are evaluated left-to-right, and parenthesis remain highest priority as usual.

We will begin building our simplified version of an AST by defining a Node class and a Leaf class. The Nodes will have an operation to perform and left and right attributes pointing to the arguments (all operators are binary). We use a property to recursively evaluate the operation. The Leaves just contain values, and offer the same property as the Nodes to return the value (this is the base case for the recursion).

With this, we only need to build the AST from the literal expression. We will do it in two steps: tokenizing and parsing. The former will convert the expression into its semantic components (tokens), while the latter will build the AST from the sequence of tokens.

We are actually complicating the tokenization a little bit by considering multi-digit numbers (after looking at the input, all numbers are single-digit), but it's not that bad, so we'll keep it.

Basically, we are just looking at each character, and returning the appropriate symbol for it: if it's a digit, convert it to a number and wrap it up as a Leaf; if it's a paren, it's its own symbol; if it's an operator, return the corresponding Node (without linking left and right for now).

To account for multi-digit numbers, we just keep appending digits to a number as long as we get digits, and when we get a paren or an operator we convert the accumulated number and reset the accumulator, besides producing the paren or operator symbol.

Since we will evaluate left-to-right, we will reverse the sequence of symbols. This allows for easier parsing; grouping the operations as they come will group them properly in this way, considering a recursive parsing, which is easier to grasp: the first operation is applying the rightmost operator on the rightmost value and the subtree resulting from parsing everything to the left of the operator (leaving parens out of the explanation for clarity).

So we can take this explanation, and use it as the template for the recursive parsing (this time including the parens):

1. Take the first token. If it's a Leaf, it becomes the root of the AST, if it's a closing paren the root is the (recursive) parsing of the following tokens, as we will return from the function when reaching an opening paren. The roles of opening and closing parens are intentionally inverted due to our inversion of the token stream.
2. If there are no more tokens, or the next token is an opening paren (which, remember, is actually closing the parenthesized sub-expression), return the AST (the current root).
3. Take the operator (the only remaining option for the next token) and assign the root to its right, then make the operator node the new root. Finally, assign to its left the (recursive) parsing of the rest of the sequence.

Evaluation of the expression is straightforward: tokenize, parse, return the value of the AST.

Part 2

In the first part we didn't have to look at the operators as both of them had the same precedence, so we just applied them as they came. For the second part addition takes precedence over multiplication (otherwise it would be too easy, as we could use the built-in eval function).

We will change strategy slightly now. We start by pre-parsing the token stream and making each parenthesized sub-expression a list (and remove the parens symbols). This is accomplished quite easily with a recursive implementation: tokens are kept as-is, starting a paren group gets a recursive call, end when reaching the end of a paren group or the end of the token stream.

The new parsing will recursively parse parenthesized sub-expressions, so that we always apply operations to flattened lists of Leaves and Nodes, but we need to consider that the Nodes may be tree roots already (from a parenthesized sub-expression). This means that we first parse the sub-expressions, then apply all the addition operators, then apply the multiplications, and we are left with the resulting tree. Since we will be doing all of this accumulating on a list, the result is a single-element list that we need to pop.

The application of the operators is the most delicate part of the exercise. Unlike in the first part, we cannot assume that any Node is an unbound operator, as there will be multiple passes, and parenthesized sub-expressions will be processed before. So, to check if a Node is the type of operator that we want to apply we need to check that it's the right type and also that its right attribute is not yet assigned. We define the isop function to check this throughout.

The first token goes directly into the sequence that will be returned. After that we have two possibilities:

• The new token is the type of operator we want to apply. If the latest token in the sequence is also of this type (which implies not having its right assigned) we assign the new token to its right (this is just for symmetry, this should never happen, and would actually leave the right of the new token unassigned and unassignable). In the normal case, we just pop the last token from the list, assign it to the left of the new one, and put the new one in the list.
• The new token is not an operator of interest. We just add it to the list, unless the currently last token is an operator, in which case this goes to its right.

What we are doing effectively is taking every operator of the specified type that hasn't been processed yet and connecting it to their right and left, taking care that there may be other operators around.

We now have all steps: tokenize (same as part 1), apply parens, apply the new parsing with multiple passes for the operators. Finally get the value of the resulting AST.

One interesting thing to note is the usefulness of iterators for all of the recursive implementations: when you pass the iterator to a recursive call it will keep drawing from the point where it was, rather than restart (which would happen with an array or list). This removes the need to keep track of the position across calls, which would make everything more cluttered (the additional variable in the function, in the signature so it can be passed in, and as a return value to know where to continue when the recursion returns).

Advent of Code 2020 - Day 17

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 is Conway's Game of Life (we have seen it before this year), only in higher dimensions. Since parts 1 and 2 just differ by the number of dimensions, we will just build a generic version that works in 2+ dimensions.

We will represent the state using a set of active cells. The input gives us the x and y coordinates for the active cells in the initial state (marked with '#'), and we just add zeros to pad the rest of dimensions.

Next we need to calculate the neighbours of a given cell. The 'steps' from the cell are given by the Cartesian product of {-1, 0, 1} for each dimension, excluding the specific combination (0, 0, ...), which corresponds to the cell itself. This is what we are doing in the line:

deltas = product(*(range(-1, 2) for _ in point))

Then we yield (cell + delta) for each delta, but we skip the zero vector (that's what the if any(delta) is there for). Note that product is itertools.product, which returns an iterator over the Cartesian product of its inputs.

We are now ready to calculate a step of the game. First, we will create a new state to update and return, so that we can refer to the old state throughout; in Game of Life all updates are simultaneous.

Since we are using a sparse representation, we cannot just go over all the board checking the rules, instead we need to explicitly build the set of candidate cells, the ones that may be active in the new state. Given the rules, that includes the currently active cells and their neighbours. A cell that is not neighbouring some currently active cells won't become active.

Then it's only a matter of checking the rules on the candidate cells and adding to the new state the ones that should be active there.

Just run for 6 steps with 3 and 4 dimensions respectively to get the solutions to parts 1 and 2.

Advent of Code 2020 - Day 16

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.

In this puzzle we have a bunch of items, each represented as a sequence of numbers. There are some fields, with constraints on the values that they can take, and we need to eventually identify which filed corresponds to each position in the sequence.

The input is not difficult to parse, but it needs to be done in stages:

1. The field rules, first splitting field from the ranges, then interpreting the ranges. One field per line, until a blank line is reached
2. The item we will use to validate (your ticket, per the problem description), a sequence of comma-separated ints.
3. The rest of items to be used for deducing the positions of the fields, a sequence like that in (2) per line.

Part 1

To begin with, we need to identify items with values that do not match any of the fields. We will create a valid_fields function that, given a number, returns the sets for which it is valid. We do this in validity, using the parsed filed rules from the input. validity returns the valid_fileds function.

The function itself is quite simple: take the number, and check for each field rule if it is within the corresponding interval(s); if so, that field goes into the returned set, otherwise it doesn't. This is readily expressed as a set comprehension, using any to iterate over potentially multiple intervals.

We can identify the invalid values, as they result in the empty set when run through this function.

Part 2

Now it's time to actually find out the positions of the fields. We will apply a form of constraint propagation, or elimination. We start with a set of feasible fields for each position, which includes all fields, then eliminate the possibilities that are not valid for some ticket.

For each item, we take the value in each position, and remove form the feasible fields for that position the fields for which the value is not valid, or conversely, we keep the intersection of feasible and valid. We need to be careful to check that the set of valid fields is not empty (we know there are invalid tickets from part 1), or alternatively we can eliminate the invalid tickets in a preprocessing pass.

We now have all the information contained in the items themselves encoded in the feasible sets. To finish, we need to apply and propagate a new constraint, one that is somewhat implicit: there is a one-to-one relationship between positions and fields.

In practice, we will keep track of all the positions that have been determined, i.e. they have a single field that is possible for them. We iterate over the positions, and add it to the determined set if there is a single feasible field or remove the determined fields from the feasible ones. We do this until all positions are determined.

Once we know which field is which, we can answer the question of multiplying the values in 'my ticket' for specific fields (those starting with 'departure').

Advent of Code 2020 - Day 15

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 puzzle asks us to run a game for a number of turns. From the problem description:

In this game, the players take turns saying numbers. They begin by taking turns reading from a list of starting numbers (your puzzle input). Then, each turn consists of considering the most recently spoken number:

• If that was the first time the number has been spoken, the current player says 0.
• Otherwise, the number had been spoken before; the current player announces how many turns apart the number is from when it was previously spoken.

Part 1

We will start by directly simulating an infinite game like this. We will use a generator (defined in the game function), and then just take as many turns as needed, as the question is the number said on the 2020th turn. To make it easier, we will use itertools.islice to run the desired number of turns.

We set up a memory using a dictionary which will keep track for each number the turn when it was last said. If it hasn't been said, it's not in the memory.

The start of the game consists of saying the seed numbers. We can just go through them, add them to the memory with the corresponding turn, and yield them. But we need to stop before the last one. This we need to treat slightly differently to jumpstart the game logic.

We increment the turn and say (yield) the last seed number, and keep it as last_number, then we enter the loop that is repeated indefinitely. First we decide what's the next number to say: zero if last_number is not in the memory, or the difference between the current turn and the turn when it was last said, taken from the memory (this is why we still haven't updated the turn, otherwise we would overcount the difference by one). We store the turn in which last_number was said, and then we can update the turn and say the new number. Note that the order of deciding the new number and storing the old one is interchangeable. Finally we just set the new number to be the last one in the next run of the loop.

Part 2

For this part, we need to go to the 30,000,000th turn. Since part 1 was almost instantaneous, we can try to just run the game for that long. It takes only a few seconds, which is good enough, so no additional work for this second part, except to change the target turn.

Advent of Code 2020 - Day 14

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 exercise is another software emulator. The input is a sequence of commands either specifying a mask or a write instruction consisting of address and value. The parsing is pretty simple as the format is very strict. We can easily write a generator to loop over the (parsed) instructions, prepending a command identifier to indicate if it's a mask or memory instruction.

Part 1

Since the writing will be rather sparse, we will use a dictionary to represent the memory, keeping track only of accessed addresses (the keys).

Whenever a memory instruction indicates to write a value into an address, the mask must be applied to the value first. The mask overwrites bits with 0 or 1 as indicated in the mask, leaving the positions marked with X unaltered.

Since Python treats ints with exactly the binary representation required for this, we can just transform the mask to do the work with a couple of bitwise logical operations. To set the ones, we can consider all Xs as zero and apply a bitwise or to the value. To set the zeros, we can consider all Xs as one and apply a bitwise and to the value.

If we call these the or-mask and the and-mask, respectively, we can update them with each mask command (using the built-in string.translate, then reading that as a binary int), and simply apply them in the memory commands transforming the value into (value & and_mask) | or_mask.

After processing all commands we just add up the values in the memory to get the requested answer.

Part 2

This part changes the behaviour. Now values are not modified, instead the mask is applied to the address. The application also changes: zeros leave the bit unchanged, ones set the bit to one (up to here is the bitwise or with the Xs as zeros), and the X bits take both possible values, resulting in multiple addresses (all potential combinations).

This means that we can take the original address and apply the or-mask. Then we apply a modified version of the and-mask: in this case we set the Xs to zeros as before, but also the zeros in the mask to ones (to avoid setting those zeros, that no longer applies). This gives us our base address, where every X bit is zero, and the rest are set to the proper values.

Now we need to efficiently generate all combinations of zeros and ones for the X bits. We start by building a list of switches, the corresponding integer value of each X bit. Adding zero, one, or more of the switches to the base address (as integers) will work exactly as flipping the corresponding bits. So we just need to return the base address with all combinations of zero switches (that's the base address), then adding each one-switch combination, then adding each two-switch combination, and so on until we return the base address plus the last, all-switches combination. Instead of manually building all the combinations, we take advantage of the combinations function in the itertools module to do it: very efficient, zero mistakes. Don't reinvent the wheel.

Now it's just a matter of updating the memory, writing the value to each of this addresses, and adding up the memory at the end.

I almost expected that this would not be quite efficient enough and that some smarter approach to register the patterns of Xs would be needed, but the masks are not too X-heavy, so it works out. I'm guessing that's intentional.

Advent of Code 2020 - Day 13

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.

In this puzzle, once you remove the decoration about buses, everything consists on cycles of given periods, and it screams modular arithmetic. The input is quite simple, a list of cycle periods with some xs; these just serve to set up the positions of the cycles, which will be used in the second part. A quick analysis of the cycle periods shows that all are prime numbers, which simplifies operations (the least common multiple of a group of prime numbers is their product).

Part 1

The question is, after translation, to find which cycle is the first to recur on or after a given time, and how long it will take.

We can easily calculate the time since the last recurrence of each period at a given time as time mod period. Then, the period less that is the remaining time until the next recurrence (unless the last recurrence was exactly at the given time, in which case we keep the zero).

We define a function to calculate this value for each period, apply it and keep the minimum.

Part 2

This one is a little tougher. We need to find the earliest time t so that each period recurs at t + p, where p is the position of the period in the period list (this is what the xs in the input are setting up).

What we will do here is construct a global cycle step by step. At each step we will add a new period.

The first step is easy: we can arbitrarily take -delay as the start of the cycle (where delay is the position of the first period), so that the initial recurrence at time zero fulfills the condition. The global cycle period is just the first period, so that the delay is kept. This is not explicit in the code as the first period is at position zero, so we can just keep the position.

To add the next period, we need to update the start of the cycle so that it the new delay matches. As long as we advance in increments of the global cycle the previous conditions hold. So we just do that, add one cycle at a time to the start time until the delay matches, that is (-delay = start) (mod cycle), which is expressed in a different way in lines 31 and 32 in the code. Then we update the global cycle by multiplying it by the new period that has been added (the advantage of all periods being prime numbers). This ensures that in the next iterations the conditions hold for all periods up to this one (the global cycle always is a multiple of each period included in it, so the delay is kept).

Rinse and repeat until all periods are included, with their corresponding delays.