Advent of Code 2017


python AOC puzzles programming

Ho Ho Ho 🎄🎅 The Advent of Code is finally here! I know… I am only 4 days late, but I have been away and only had time to sit down and write this up.

For those that do not know what this is, Advent of Code is an annual coding event in which a coding challenge is revealed every day in December leading up to Xmas. Sounds like fun?

The whole ideA of things like this is to encourage people to have fun. The challenges are such that it can be used to sharpen your existing coding skills of to learn from these challenges. Each puzzle is formed of two parts, one must complete the first part before jumping into the second one… ah and one last thing. You get a personalized input for each puzzle!

In my case, I wanted to do this last year but with finishing up my thesis, starting a new job, and being my first Xmas spent in the UK I just did not have the time nor the focus to do it. So this year as soon as I had the chance I jumped into it and encouraged friends and colleagues to join. 🌟🌟

So far most of the RSE team of Sheffield and our awesome friends from Sitran and the library are doing this too! I will add links to some of their amazing solutions at the end of this post so that you can have a nosey (they are all a clever bunch).

Day 1: Inverse Captcha

The description of the problem is quite thorough and it sets the scenario for the Xmas quest you are about to start, so I encourage you go and read it yourself.

TL;DR: Santa’s elves are having trouble printing the list for the Crimbo presents and you’re helping them to fix 50 bugs (or the 50 puzzles). This first challenge requires you to solve a captcha to prove you’re not human.

Part 1:

You are given a series of digits (your input) and find the sum of al the digits that match the next digit in the list. Also since your list is circular the first digit in the list is also the last digit.

So let’s say we have the following list of digits:

AOC puzzle 1

As it is the list 1122 would give as a result 6 since 1 + 2 = 3 as the first digit matches the second and the third matches the fourth.

If the list were instead 91212129 it would result in 9 as this is the only number that matches the following one.

The first approach could then consist on creating a function that would take the input data, then move from one digit to the other and check if the digit we are looking at (i) has the same value as the digit after it (i + 1). If these two digits are the same we can then add their value to a variable called total in this example:

def check_digits(my_input):
  total = 0
  for i in range(len(my_input)):
    if my_input[i] == my_input[i + 1]:
      total += int(my_input[i])
    return total

Now… the above solution does not go back to the beginning of the listand in fact gives you an exception since you are attempting to go over the actual lenght of your list. Now there are a few things you could do: a) compare the number to the digit preceding it so that:

def check_digits(my_input):
  total = 0
  for i in range(len(my_input)):
    if my_input[i] == my_input[i - 1]:
      total += int(my_input[i])
    return total

which gets rid of that out of bounds exception or b) Imagine that our list repeats for a number of times (e.g. 112211221122...).

Shall this be the case, and using the logic of the above functions, when we get tp the 5th element we would be in fact, looking at the 1st element in the original one. This would be true as well for the 9th, 13th, and every other n * 4+ 1 since out original input had 4 digist in. Being this the case, we could use the modulus operator % to get the remainder between the digit we are observing and the length of out original list:

def check_digits(my_input):
  total = 0
  for i in range(len(my_input)):
    if my_input[i] == my_input[(i + 1) % len(my_input)]:
      total += int(my_input[i])
    return total

Success!!! This gives us our first star! ⭐️

Part 2:

In this bit instead of having a circular list and checking for consecutive identical digits, we have look for these halfway around the list (NB: we have an even number of digits). So instead of looking at the i + 1 element, we will take the length of our list and divide it by 2 len(my_input) // 2 and add that to i. Again, we use the modulus operator:

def check_digits2(my_input):
  total = 0
  for i in range(len(my_input)):
    if my_input[i] == my_input[(i + (len(my_input) // 2)) % len(my_input)]:
      total += int(my_input[i])
    return total

Success!!! This gives us our second star! ⭐️

🔥 Bonus!

Now, since Python allows us to map functions and use list comprehension so the above functions can be replaced by the one line versions:

def captcha1(x):
    return sum(map(int,[ x[i] for i in range(len(x)) if x[i] == x[i - 1] ]))

def captcha2(x):
    return sum(int(x[i]) for i in range(len(x)) if x[i] == x[i - len(x) // 2])

comparing to i - 1, but this could easily be substituted by (i + 1) % len(x).

This is in fact the approach I used but I thought I would go around more options for those less familiar with map and list comprehensions.

And that is puzzle 1! I will add more solutions (probably not all of them… but you can check these out in my GitHub repository) which I will update every day… and where I will be adding polyglot solutions too: maybe some R, C++, FORTRAN and if I am adventurous some Ruby.

Other solutions (in other languages and by other people)


Advent of Code 2017

Ho Ho Ho 🎄🎅 The Advent of Code is finally here! I know… I am only 4 days late, but I have been away and only had time to sit down and write this up.

2nd RSE conference: an insider view

I know! I have failed to post regularly, but in this occasion I have an excellent excuse: I have been super busy at work and I also went back home for some so much needed holidays!

Archive

  • 2017
comments powered by Disqus