Advent of Code - Wrapping up 2020

Given a list of integers,

• Part One requires you to find two numbers which sum upto 2020 and then return their product.
• Part Two requires you to find three numbers which sum upto 2020 and then return their product.

Given a list of strings, find the number of strings which satify a given "policy".

• Part One specifies the policy as a given character count being within a given range.
• Part Two specifies the policy as a given character being present in exacty one of the two given locations.

Pretty straightforward array traversal with little modulo trick to handle the infinite recurrence towards the right.

Hardly a thinker. Just a lot of careful coding to pick out "passports" (each being a dictionary key-value pairs) which have necessary keys and values that satisfy certain specified constaints.

Interesting one. The algorithm for deriving the seat id is essentially binary search and part two is a minor extension that is just a slight variation of LeetCode Easy Missing number

Another straightforward one.

• Part one needs you to find the number of questions anyone has answered yes (logical OR).
• Part two needs you to find the number of questions everyone has answered yes (logical AND).

Converting the list of rules to a more code-consumable form (I chose a dictionary) is an important first part in solving this problem. I went with a recursive solution with memoization for Part One and utilized the concept of recursive grounding for Part two (or atleast that's what I think it is called). In recursive grounding you start off with set of knowns (the answer for bags which cannot contain any other color is 0) and slowly expand your "known" (or grounded) set by computing the plausible "unknowns". Part two cannot be solved if the containment structure is topologically impossible.

Part one is a step-by-step mimic of code execution following the NOPs and JMPs and keeping track of the accumulator, till you hit a line you have already executed.

For part two, since it's a given that you need only one swap and input is not insanely big, I tried brute-forcing it (try every swap) and it was fast enough! There might be a more optimal way to do it, not entirely sure at this point. Onward for now!

Part one - Sort the array. Track the flow making sure the constraints are met and keep track of the differences.

Part two - Finally a chance to write a dynamic programming solution!

The crux of the logic for this problem is in finding the neighbours. Once that's implemented, to compute the next state, all you have to do is iterate through each cell, identify it's neighbourhood occupancy and accordingly update it's own occupancy. Keep iterating from one state to the next till it stabilizes. I am using deepcopy to make a copy of the current state as occupancy changes are done simulataneously and also due to how assignment works in python.

This is all you need to know to solve Day 12.

Note: Non-90 degree angle rotations would make this problem much more difficult.

Part One

• A 0 or 1 in the mask overrides the corresponding bit in value.
• A X in the mask leaves the bit unchanged in the value.

For achieving this transformation, decompose the given mask into an AND mask and an OR mask to be applied one after the other. The AND mask carries over the bits in X as it is and zeros out the positions that need to be overriden. The OR mask then places the appropriate 0/1 (s) in the zeroed out positions.

Part Two

• A 0 in the mask leaves the bit unchanged in the value.
• A 1 in the mask overrides the bit in the value.
• A X in the mask makes it a "schrodinger" bit. Can be a 0 or a 1.

For achieving this transformation, decompose the given mask into an AND mask, an OR mask and a collection of possible OR masks for Xs (capturing the various resolved configurations). The AND mask carries over the bits in 0 as it is and zeros out the positions that need to be overriden. The OR mask then places the ones in the appropriate zeroed out positions. The collection of OR masks for Xs are then be applied to place the resolved 0/1 (s). There would be 2^{Numbers of Xs} possible OR masks

A little breather after a couple of Medium-Hard days. Used a dictionary for memory and just simulated game play.

A significant part of Part One is parsing all the input and making it code-consumable. But don't worry, Part One in entirety is an investment for Part Two.

In Part One, you have to find all the invalid values. To tackle it more generically (in hindsight of Part Two), I identify all satifying contraints for a given value and report back ones which have zero satifying constaints.

For Part Two, you attempt to utilize your knowledge of these satifying constaints for each value to uniquely identify what the ticket field can be. A value satifying a contraint essentially means that the corresponding field is a potential candidate for being the right assignment. I tackle this iteratively. Values with only one potential candidate can get assigned right away. With these out of the mix, we obtain a reduce problem set. Repeat until we have uniquely identified all assignments or hit a blocker where we conclude that it is not possible.

Brute-forced it.

Can it be done more optimally? I don't know at the moment. Taking the win. Might come back later.

Infix expression evaluation - straight out of DSA 101. Enjoyed the trip down memory lane :)

Another one straight out of CS undergrad and this one is from Compilers. These rules essentially form a Formal Grammar. Since the grammar doesn't have any loops you can recursively resolve the rules to pull out a regex expression for "0". After you get the regex, it's as simple as iterating through all the strings and seeing if it's a match.

Part Two attempts to jog a little bit more of your undergrad memory. Do you remember how to expand recursive rules? What regex special characters can you leverage here? Can you take advantage of your knowledge of the length of strings in the input to come up with less complex regex?

Wow, wasn't this problem jurassic! Easily the most intense day this year.

Part One was not too hard. I didn't even have to put together the whole image since all you need are the corners. Find tiles which have two unmatching edges - meaning two outside edges - and you have found the corners.

Part Two was a mammoth. I am tired, whew. I am going to just let you read the code for this one.

Day 16, is that you again?

Simulated gameplay. Did nothing fancy. Taking the easy win and onward!

Another gameplay simulation. My naive first attempt worked for Part One but Part Two was not all welcoming to that (can't just skate through two consecutive days can I?).

What I needed was a more efficient data structure. Circular and list-like. Hmm. Circular Linked List!

There are various ways for you to traverse hexagonal grids. I use doubled coordinates as it made the most intuitive sense to me.

I think Eric was feeling a tad generous with it being Christmas and all. Just one part and brute-force-able. Thank you very much!

Having to implement modular exponentiation may have possibly made it a little more demanding but lucky for me, I am using python.