Advent of Code 2015 Problem Set
Day 10
There’s a lot to be said for doing the Advent of Code in December along with a few thousand other programmers. It’s fun to be part of something with others and you get to all the neat and wacky solutions that others come up with.
On the other hand, going at my own page with the 2015 problem set allows for interesting little coincidences to form. What I did one day (when I was at about Day 7) was to go through all the remaining days and write some first impression ideas at solutions. This got my brain thinking about what I needed for each day. One day, before getting to the Day 10 problems, I was idly flipping through the book Learn You a Haskell for Great Good! As I was trying to decide if it would be one of the languages I’d add for 2016. I ended up coming across a built-in library that would have made solving Day 10 a real breeze. Day 10 is the Look and Say sequence. I’m sure by paying close attention to that Wiki entry I could have figured out an algorithm. But, basically I just needed to group together each repeated number and then I could take the length of that list/array to find out how many numbers. That becomes part of the new number. Unfortunately, as far as I could see, that functionality was not built into Python. So my Python code looked like this:
"""Find length of the a number after a look-and-say game."""
import copy
def create_number_lists(game_input):
current_number = 0
number_count = 0
return_list = []
for number in game_input:
if len(game_input) == 1:
return [(1, int(number))]
if int(number) != current_number:
if number_count != 0:
return_list.append((number_count, int(current_number)))
current_number = int(number)
number_count = 1
else:
number_count += 1
return_list.append((number_count, int(current_number)))
return return_list
def recombine(number_list):
return "".join(
str(number) for num_tuple in number_list for number in num_tuple
)
if name == "main":
puzzle_input = '1321131112'
loop_count = 0
puzzle_output = ""
while loop_count < 40:
puzzle_output = recombine(create_number_lists(puzzle_input))
puzzle_input = puzzle_output
loop_count += 1
print(f"The length of puzzle_output ({puzzle_output}) is {len(puzzle_output)}")
Meanwhile look at how much cleaner this is in Ruby using chunk_while:
def look_and_say_round(game_input)
game_input_array = game_input.split(//)
game_input_array.chunk_while { |a, b| a == b }
.flat_map { |chunk| "#{chunk.size}#{chunk.first}" }
.join('')
end
if $PROGRAM_NAME == FILE
input = "1321131112"
loop_count = 0
until loop_count == 40
puzzle_output = look_and_say_round(input)
input = puzzle_output
loop_count += 1
end
puts "Length of output after 40 roundes of look and say is #{puzzle_output.length}"
end
Revisiting the code to write this blog post, I think I can probably reduce that code down to one line (in the look_and_say_round function) if I wanted to sacrifice a bit of readability. The Perl code falls somewhere in the middle. I easily found a CPAN module to do the equivalent of chunk_while. However, I’m not as conversant in Perl so I don’t know if I’m being a little extra verbose here:
!/usr/bin/perl
use v5.20;
use warnings;
use Array::GroupBy qw(igroup_by);
sub look_and_say_round{
my $game_input = $_[0]; my @numbers = split("", $game_input); my $number_iterator = igroup_by(data => \@numbers, compare => sub{$_[0] eq $_[1]},); my $look_and_say_text = ''; while (my $grouped_array = $number_iterator->()) { my $length = @{$grouped_array}; my $number = @{$grouped_array}[0]; $look_and_say_text = $look_and_say_text . "$length$number"; } return $look_and_say_text;
}
my $puzzle_input = "1321131112";
my $loop_count = 0;
my $puzzle_output;
until ($loop_count == 40){
$puzzle_output = look_and_say_round($puzzle_input); $puzzle_input = $puzzle_output; $loop_count++;
}
my $output_length = length($puzzle_output);
say "The final number is $puzzle_output with a length of $output_length";
Day 11
Day 11 wasn’t too hard for any language. It basically gave some password generation rules and required you to increment passwords in a certain way. However, there was a bit of elegance in the Ruby solution that I guess points towards part of the reason why folks tend to REALLY love this language. First, let me show you my Python code:
import re
def rule_one(password: str) -> bool:
"""Check if a password includes a straight of at least 3 letters."""
for index, letter in enumerate(password):
if index == (len(password) - 3):
return False
current_letter_ascii_value = ord(letter)
if ord(password[index + 1]) == current_letter_ascii_value + 1 and\
ord(password[index + 2]) == current_letter_ascii_value + 2:
return True
def rule_two(password: str) -> bool:
"""Check if a password contains i, o, or l."""
return 'i' not in password and 'o' not in password and 'l' not in password
def rule_three(password: str) -> bool:
"""Check for at least two different, non-overlapping pairs of letters."""
rule_three_regex = re.compile(r'(\w)\1')
all_pairs = re.findall(rule_three_regex, password)
if len(all_pairs) < 2: return False if len(set(all_pairs)) > 1:
return True
def increment_password(password: str) -> str:
"""Given a password, increment the last letter by 1."""
if password[-1] == 'z':
return increment_password(password[:-1]) + 'a'
return password[:-1] + chr(ord(password[-1]) + 1)
def find_next_valid_password(password: str) -> str:
"""Find the next password that meets all the criteria"""
while True:
if rule_one(password) and rule_two(password) and rule_three(password):
return password
password = increment_password(password)
puzzle_input = "hxbxwxba"
first_new_password = find_next_valid_password(puzzle_input)
second_new_password = find_next_valid_password(increment_password(first_new_password))
print(f"Santa's first new password is {first_new_password}")
print(f"Santa's second new password is {second_new_password}")
Both rule_one and increment_password are a little inelegant. I spent a bunch of time trying to figure out a better rule_one with regex and I couldn’t. And for the password incrementing, I had to convert it to asii to get the next letter and then come back to string. Ruby, however, was so nice!
def rule_one(password)
characters = password.split(//)
triple_straight = characters.chunk_while { |i, j| i.next == j }.filter{|chunk| chunk.length >= 3}
triple_straight.length >= 1
end
def rule_two(password)
!password.include? "i" and !password.include? "o" and !password.include? "l"
end
def rule_three(password)
pairs = password.scan(/(\w)\1/)
pairs.length >= 2
end
if $PROGRAM_NAME == FILE
current_password = "hxbxwxba"
puts "Santa's starting password is: #{current_password}"
until rule_one(current_password) and rule_two(current_password) and rule_three(current_password)
current_password = current_password.next
end
puts "Santa's next password should be: #{current_password}"
puts "Then Santa's password expired again!"
current_password = current_password.next
until rule_one(current_password) and rule_two(current_password) and rule_three(current_password)
current_password = current_password.next
end
puts "Santa's next password should be: #{current_password}"
end
First of all, the return of chunk_while allows rule_one to work SO, SO well. But the best part is that Ruby’s “something.next” method just works so perfectly both here and in the password incrementing code. This works especially well because it does the right thing where “az” increments to “ba”. It just is so beautiful for doing this and I love the resulting code! Looking back at this now, I see that there is some code there in the “main” loop which I could have refactored out into a function.
Day 12
Usually part 2 of an Advent of Code problem is just a bit more complex, introducing complications that may mess with shortcuts or assumptions the programmer made in part 1. But every once in a while, the code needed for part 2 is radically different than the code for part 1. For part 1 I was able to use a simple regular expression to get the answer. The code is simple (as usual I’ve actually over-complicated things a bit with my code so that I can use unit tests to test against the examples given)
import re
from sys import maxsize, path
path.insert(0, '../../input_parsing')
import parse_input
def find_numbers(line: str):
regex = re.compile(r'(-*\d+)')
numbers = re.findall(regex, line)
return [int(number) for number in numbers]
def sum_number_list(number_list: list[int]) -> int:
return sum(number_list)
if name == "main":
lines = parse_input.input_per_line('../input.txt')
total = sum([sum_number_list(find_numbers(line)) for line in lines])
print(f"The sum of all numbers in the document is {total}")
But for part 2, I actually had to create a JSON parser of sorts.
import json
from sys import path
path.insert(0, '../../input_parsing')
import parse_input
def find_numbers(elf_json):
summation = 0
if isinstance(elf_json, list):
for item in elf_json:
summation += find_numbers(item)
elif isinstance(elf_json, int):
return elf_json
elif isinstance(elf_json, str):
return 0
else:
for key, value in elf_json.items():
if "red" in elf_json.values():
return 0
elif isinstance(value, int):
summation += value
elif isinstance(value, list):
summation += find_numbers(value)
elif isinstance(value, dict):
summation += find_numbers(value)
else:
# this is a color string
summation += 0 # this used to be a print statement
return summation
if name == "main":
json_string = parse_input.input_per_line('../input.txt')
total = json.loads(json_string[0])
print(f"The sum of all numbers in the document (unless it's got a red property) is {find_numbers(total)}")
Prophecy Practicum
This is a project I’m working on for a buddy in order to fulfill a need he has with a spiritual practice he’s involved in. As I mentioned before, moving from Flask to Django allowed me to make lots of progress on the project. In May I finally reached the v1.0 milestone and it was ready for users to try out. As I write this in June, the first cohort has gone through it and I’m waiting to see what modifications we need to make. Additionally, I have a couple features I’m trying to figure out.
ELDonation Tracker for Extra Life
I started off May fixing a bug where DonorDrive had changed their API output and it messed up my Avatar image output. While investigating the API changes, I found out they had added in APIs for milestones, badges, and incentives. This led to the release of v6.1. Next up for this project will be v7.0 where I move the API code out to its own project so that it can be useful as a Python reference API for DonorDrive, independent of Extra Life.
Harry Potter Word Frequency Calculator
I had a conversation with Scarlett about how puzzle solvers (cryptographers) use word frequency to help solve their puzzles. And I told her that the most often used word in English is “the”. She was a little skeptical, so I wrote a program to do word frequency analysis on Harry Potter and the Philosopher’s Stone. Since it was my first time using my chosen epub library, I just took it one chapter at a time to get a better understanding of how it works.
from collections import Counter
import ebooklib
from ebooklib import epub
import re
philosopher_stone = epub.read_epub("/home/ermesa/eBooks/J.K. Rowling/Harry Potter and the Sorcerer's Stone (441)/Harry Potter and the Sorcerer's Stone - J.K. Rowling.epub")
items = philosopher_stone.get_items_of_type(ebooklib.ITEM_DOCUMENT)
items_list = list(items)
remove_html_tags_regex = re.compile(r'<[^>]+>')
chapter_one = remove_html_tags_regex.sub('', items_list[6].get_body_content().decode())
chapter_one_words = chapter_one.split()
print(Counter(chapter_one_words))
And here’s the output:
Counter({'the': 187, 'a': 105, 'and': 95, 'to': 93, 'he': 87, 'was': 84, '.': 81, 'of': 72, 'his': 66, 'in': 55, 'He': 49, '—': 49, 'that': 48, 'on': 44, 'as': 41, 'had': 39, 'Dursley': 38, 'it': 36, 'have': 32, 'at': 32, 'Mr.': 30, 'said': 28, 'Professor': 28, 'be': 27, 'I': 27, 'al
l': 25, 'were': 23, 'Mrs.': 21, 'you': 21, 'didn’t': 21, 'but': 21, 'out': 21, 'It': 21, 'been': 21, 'she': 20, 'for': 20, 'her': 19, 'they': 18, 'Dumbledore': 18, 'very': 17, 'people': 17, 'over': 17, 'into': 17, 'cat': 17, 'McGonagall': 16, 'with': 15, 'not': 15, 'The': 14, 'him':
14, 'Harry': 14, 'up': 13, 'this': 13, 'back': 13, 'if': 12, 'so': 11, 'it.': 11, 'about': 11, 'couldn’t': 11, 'down': 11, 'know': 11, 'their': 10, 'would': 10, 'could': 10, 'what': 10, 'never': 10, 'even': 10, 'them': 10, 'just': 9, 'man': 9, 'there': 9, 'no': 9, 'like': 9, 'somethi
ng': 9, 'thought': 9, 'by': 9, 'see': 9, 'owls': 9, 'looked': 9, '“I': 9, 'Dumbledore,': 9, 'Privet': 8, 'did': 8, 'think': 8, 'Potter': 8, 'seen': 8, 'street': 8, 'around': 8, 'little': 8, 'who': 8, 'eyes': 8, 'are': 8, 'number': 7, 'because': 7, 'which': 7, 'Dudley': 7, 'got': 7, '
corner': 7, 'when': 7, 'from': 7, 'next': 7, 'can': 7, 'he’s': 7, 'Hagrid': 7,... it keeps going, but I've cut it off here
It’s actually not that surprising to see “Harry” so low in chapter one. It’s more about describing the nature of Privet Drive and Dumbledore and the other wizards than it is about Harry. I may do a bit more with this code to create some fun graphs. If you want to expand on this, the first thing you’d want to do is force every word to lowercase before counting it so that ‘a’ and “A” are counted as the same word.
DragonRuby
I took a look at the idea of participating in the DragonRuby game jam. But it’s WAY more work than using Unity or Unreal so I chose other tasks over this one. But it was neat to play around with and I may return to it someday.
Top comments (0)