Advent of code 2020

In [ ]:
from notebook.services.config import ConfigManager
c = ConfigManager()
c.update('notebook', {"CodeCell": {"cm_config": {"autoCloseBrackets": False}}})
Out[ ]:
{'CodeCell': {'cm_config': {'autoCloseBrackets': False}}}
In [ ]:
import timeit
import typing

def default_cleaner(line):
    return line

def read_and_clean(day: int, cleaner=default_cleaner):
    """Read from input{day}.txt, return list of stripped lines
    """
    filename = f"input{day}.txt"
    with open(filename) as f:
        ll = f.readlines()
    lines =  [cleaner(line.strip()) for line in ll]
    print(f"Input {lines[:2]} ... {lines[-2:]}")
    return lines

def noprint(*args, **kwargs):
    pass

--- Day 1: Report Repair ---

After saving Christmas five years in a row, you've decided to take a vacation at a nice resort on a tropical island. Surely, Christmas will go on without you.

The tropical island has its own currency and is entirely cash-only. The gold coins used there have a little picture of a starfish; the locals just call them stars. None of the currency exchanges seem to have heard of them, but somehow, you'll need to find fifty of these coins by the time you arrive so you can pay the deposit on your room.

To save your vacation, you need to get all fifty stars by December 25th.

Collect stars by solving puzzles. Two puzzles will be made available on each day in the Advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

Before you leave, the Elves in accounting just need you to fix your expense report (your puzzle input); apparently, something isn't quite adding up.

Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together.

For example, suppose your expense report contained the following:

1721 979 366 299 675 1456

In this list, the two entries that sum to 2020 are 1721 and 299. Multiplying them together produces 1721 * 299 = 514579, so the correct answer is 514579.

Of course, your expense report is much larger. Find the two entries that sum to 2020; what do you get if you multiply them together?

--- Part Two ---

The Elves in accounting are thankful for your help; one of them even offers you a starfish coin they had left over from a past vacation. They offer you a second one if you can find three numbers in your expense report that meet the same criteria.

Using the above example again, the three entries that sum to 2020 are 979, 366, and 675. Multiplying them together produces the answer, 241861950.

In your expense report, what is the product of the three entries that sum to 2020?

In [ ]:
lines = read_and_clean(1, int)
Input [1440, 1511] ... [1596, 1925]
In [ ]:
from itertools import combinations
from operator import mul
from functools import reduce

    
nums = [int(line) for line in lines]

def find_sum(nums, total=2020, nitems=2):
    groups = combinations(nums, nitems)
    for group in groups:
        s = sum(group)
        if s == total:
            ans = reduce(mul, group)
            break
    return group, ans

print(find_sum(nums))
print(find_sum(nums, nitems=3))
((1093, 927), 1013211)
((481, 19, 1520), 13891280)
In [ ]:
 

--- Day 2: Password Philosophy ---

Your flight departs in a few days from the coastal airport; the easiest way down to the coast from here is via toboggan.

The shopkeeper at the North Pole Toboggan Rental Shop is having a bad day. "Something's wrong with our computers; we can't log in!" You ask if you can take a look.

Their password database seems to be a little corrupted: some of the passwords wouldn't have been allowed by the Official Toboggan Corporate Policy that was in effect when they were chosen.

To try to debug the problem, they have created a list (your puzzle input) of passwords (according to the corrupted database) and the corporate policy when that password was set.

For example, suppose you have the following list:

1-3 a: abcde 1-3 b: cdefg 2-9 c: ccccccccc

Each line gives the password policy and then the password. The password policy indicates the lowest and highest number of times a given letter must appear for the password to be valid. For example, 1-3 a means that the password must contain a at least 1 time and at most 3 times.

In the above example, 2 passwords are valid. The middle password, cdefg, is not; it contains no instances of b, but needs at least 1. The first and third passwords are valid: they contain one a or nine c, both within the limits of their respective policies.

How many passwords are valid according to their policies?

--- Part Two ---

While it appears you validated the passwords correctly, they don't seem to be what the Official Toboggan Corporate Authentication System is expecting.

The shopkeeper suddenly realizes that he just accidentally explained the password policy rules from his old job at the sled rental place down the street! The Official Toboggan Corporate Policy actually works a little differently.

Each policy actually describes two positions in the password, where 1 means the first character, 2 means the second character, and so on. (Be careful; Toboggan Corporate Policies have no concept of "index zero"!) Exactly one of these positions must contain the given letter. Other occurrences of the letter are irrelevant for the purposes of policy enforcement.

Given the same example list from above:

1-3 a: abcde is valid: position 1 contains a and position 3 does not.
1-3 b: cdefg is invalid: neither position 1 nor position 3 contains b.
2-9 c: ccccccccc is invalid: both position 2 and position 9 contain c.

How many passwords are valid according to the new interpretation of the policies?

In [ ]:
lines = read_and_clean(2, str.split)

def is_valid(line):
    nrange, char, pw = line #.split()
    lh = nrange.split('-')
    lh = [int(x) for x in lh]
    char = char[0]
    nc = len([c for c in pw if c == char])
    #print(line, lh, char, pw, nc)
    if nc >= lh[0] and nc <= lh[1]:
        #print('OK')
        return True
    else:
        return False

valid_count = 0
for line in lines:
    if is_valid(line):
        valid_count += 1
        
print(f"{valid_count} lines are valid")        

[is_valid(line) for line in lines].count(True)
Input [['4-8', 'n:', 'dnjjrtclnzdnghnbnn'], ['5-6', 'r:', 'rrrrcqr']] ... [['10-16', 'n:', 'lvknnwnnvsmnnnnhn'], ['12-13', 'r:', 'rrrpjrrrrrrtfrkwmr']]
622 lines are valid
Out[ ]:
622
In [ ]:
def is_valid2(line):
    nrange, char, pw = line #.split()
    lh = nrange.split('-')
    lh = [int(x) - 1 for x in lh]
    char = char[0]
        #print(line, lh, char, pw, nc)
    if ((pw[lh[0]] == char and pw[lh[1]] != char) or
        (pw[lh[0]] != char and pw[lh[1]] == char)):
        #print('OK')
        return True
    else:
        return False

valid_count = 0
for line in lines:
    if is_valid2(line):
        valid_count += 1
        
print(f"{valid_count} lines are valid")
263 lines are valid

--- Day 3: Toboggan Trajectory ---

With the toboggan login problems resolved, you set off toward the airport. While travel by toboggan might be easy, it's certainly not safe: there's very minimal steering and the area is covered in trees. You'll need to see which angles will take you near the fewest trees.

Due to the local geology, trees in this area only grow on exact integer coordinates in a grid. You make a map (your puzzle input) of the open squares (.) and trees (#) you can see. For example:

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

These aren't the only trees, though; due to something you read about once involving arboreal genetics and biome stability, the same pattern repeats to the right many times:

..##.........##.........##.........##.........##.........##.......  --->
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##.....  --->
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#  --->

You start on the open square (.) in the top-left corner and need to reach the bottom (below the bottom-most row on your map).

The toboggan can only follow a few specific slopes (you opted for a cheaper model that prefers rational numbers); start by counting all the trees you would encounter for the slope right 3, down 1:

From your starting position at the top-left, check the position that is right 3 and down 1. Then, check the position that is right 3 and down 1 from there, and so on until you go past the bottom of the map.

The locations you'd check in the above example are marked here with O where there was an open square and X where there was a tree:

..##.........##.........##.........##.........##.........##.......  --->
#..O#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....X..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#O#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..X...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.X#.......#.##.......#.##.......#.##.......#.##.....  --->
.#.#.#....#.#.#.#.O..#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........X.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.X#...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...#X....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...X.#.#..#...#.#.#..#...#.#.#..#...#.#  --->

In this example, traversing the map using this slope would cause you to encounter 7 trees.

Starting at the top-left corner of your map and following a slope of right 3 and down 1, how many trees would you encounter?

In [ ]:
lines = read_and_clean(3)
Input ['.............#...#....#.....##.', '.#...##.........#.#.........#.#'] ... ['.............#...##.....#......', '.#...##..##.#.........#.##...#.']
In [ ]:
def count_trees(lines, slopex, slopey):
    linelen = len(lines[0])
    x = 0
    tree_count = 0
    for i in range(0, len(lines), slopey):
        line = lines[i]
        here = line[x]
        if here == '#':
            tree_count += 1
        x += slopex
        x %= linelen
    
    return tree_count

tree_count = count_trees(lines, 3, 1)
print(f"{tree_count} trees")
167 trees

--- Part Two ---

Time to check the rest of the slopes - you need to minimize the probability of a sudden arboreal stop, after all.

Determine the number of trees you would encounter if, for each of the following slopes, you start at the top-left corner and traverse the map all the way to the bottom:

Right 1, down 1.
Right 3, down 1. (This is the slope you already checked.)
Right 5, down 1.
Right 7, down 1.
Right 1, down 2.

In the above example, these slopes would find 2, 7, 3, 4, and 2 tree(s) respectively; multiplied together, these produce the answer 336.

What do you get if you multiply together the number of trees encountered on each of the listed slopes?

In [ ]:
slopes = ((1,1), (3, 1), (5, 1), (7,1), (1, 2))
product = 1
for slope in slopes:
    tc = count_trees(lines, *slope)
    print(tc)
    product *= tc
    
print(f"Product of results {product}")
53
167
54
67
23
Product of results 736527114

--- Day 4: Passport Processing ---

You arrive at the airport only to realize that you grabbed your North Pole Credentials instead of your passport. While these documents are extremely similar, North Pole Credentials aren't issued by a country and therefore aren't actually valid documentation for travel in most of the world.

It seems like you're not the only one having problems, though; a very long line has formed for the automatic passport scanners, and the delay could upset your travel itinerary.

Due to some questionable network security, you realize you might be able to solve both of these problems at the same time.

The automatic passport scanners are slow because they're having trouble detecting which passports have all required fields. The expected fields are as follows:

byr (Birth Year)
iyr (Issue Year)
eyr (Expiration Year)
hgt (Height)
hcl (Hair Color)
ecl (Eye Color)
pid (Passport ID)
cid (Country ID)

Passport data is validated in batch files (your puzzle input). Each passport is represented as a sequence of key:value pairs separated by spaces or newlines. Passports are separated by blank lines.

Here is an example batch file containing four passports:

ecl:gry pid:860033327 eyr:2020 hcl:#fffffd byr:1937 iyr:2017 cid:147 hgt:183cm

iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884 hcl:#cfa07d byr:1929

hcl:#ae17e1 iyr:2013 eyr:2024 ecl:brn pid:760753108 byr:1931 hgt:179cm

hcl:#cfa07d eyr:2025 pid:166559648 iyr:2011 ecl:brn hgt:59in

The first passport is valid - all eight fields are present. The second passport is invalid - it is missing hgt (the Height field).

The third passport is interesting; the only missing field is cid, so it looks like data from North Pole Credentials, not a passport at all! Surely, nobody would mind if you made the system temporarily ignore missing cid fields. Treat this "passport" as valid.

The fourth passport is missing two fields, cid and byr. Missing cid is fine, but missing any other field is not, so this passport is invalid.

According to the above rules, your improved system would report 2 valid passports.

Count the number of valid passports - those that have all required fields. Treat cid as optional. In your batch file, how many passports are valid?

In [ ]:
lines = read_and_clean(4)
Input ['ecl:amb', 'pid:690616023'] ... ['iyr:1945', 'eyr:1935 hgt:159cm']
In [ ]:
required_fields = ["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"]

def read_passports(lines):
    passports = []
    passport = []
    for line in lines:
        if not len(line):
            passports.append((" ".join(passport)).split())
            passport = []
        else:
            passport.append(line) 

    if len(passport):                        
        passports.append(" ".join(passport).split())

    for passport in passports:
        passport.sort() # not necessary, but makes lines easier to compare visually
        
    return passports

def valid1(passport):
    fields = [f.split(':')[0] for f in passport]
    if len(fields) == 8 or (len(fields) == 7 and not 'cid' in fields):
        return True
    else:
        return False
    
passports = read_passports(lines)

ok = 0
for passport in passports:
      if valid1(passport):
            ok += 1
            
print(f"{ok} passports are OK")
170 passports are OK

--- Part Two ---

The line is moving more quickly now, but you overhear airport security talking about how passports with invalid data are getting through. Better add some data validation, quick!

You can continue to ignore the cid field, but each other field has strict rules about what values are valid for automatic validation:

byr (Birth Year) - four digits; at least 1920 and at most 2002.
iyr (Issue Year) - four digits; at least 2010 and at most 2020.
eyr (Expiration Year) - four digits; at least 2020 and at most 2030.
hgt (Height) - a number followed by either cm or in:
    If cm, the number must be at least 150 and at most 193.
    If in, the number must be at least 59 and at most 76.
hcl (Hair Color) - a # followed by exactly six characters 0-9 or a-f.
ecl (Eye Color) - exactly one of: amb blu brn gry grn hzl oth.
pid (Passport ID) - a nine-digit number, including leading zeroes.
cid (Country ID) - ignored, missing or not.

Your job is to count the passports where all required fields are both present and valid according to the above rules. Here are some example values:

byr valid: 2002 byr invalid: 2003

hgt valid: 60in hgt valid: 190cm hgt invalid: 190in hgt invalid: 190

hcl valid: #123abc hcl invalid: #123abz hcl invalid: 123abc

ecl valid: brn ecl invalid: wat

pid valid: 000000001 pid invalid: 0123456789

Here are some invalid passports:

eyr:1972 cid:100 hcl:#18171d ecl:amb hgt:170 pid:186cm iyr:2018 byr:1926

iyr:2019 hcl:#602927 eyr:1967 hgt:170cm ecl:grn pid:012533040 byr:1946

hcl:dab227 iyr:2012 ecl:brn hgt:182cm pid:021572410 eyr:2020 byr:1992 cid:277

hgt:59cm ecl:zzz eyr:2038 hcl:74454a iyr:2023 pid:3556412378 byr:2007

Here are some valid passports:

pid:087499704 hgt:74in ecl:grn iyr:2012 eyr:2030 byr:1980 hcl:#623a2f

eyr:2029 ecl:blu cid:129 byr:1989 iyr:2014 pid:896056539 hcl:#a97842 hgt:165cm

hcl:#888785 hgt:164cm byr:2001 iyr:2015 cid:88 pid:545766238 ecl:hzl eyr:2022

iyr:2010 hgt:158cm hcl:#b6652a ecl:blu byr:1944 eyr:2021 pid:093154719

Count the number of valid passports - those that have all required fields and valid values. Continue to treat cid as optional. In your batch file, how many passports are valid?

In [ ]:
def byr(value):
    """    
    byr (Birth Year) - four digits; at least 1920 and at most 2002.
    """
    value = int(value)
    return value >= 1920 and value <= 2002

def iyr(value):
    """ iyr (Issue Year) - four digits; at least 2010 and at most 2020.
    """
    value = int(value)
    return value >= 2010 and value <= 2020

def eyr(value):
    """ eyr (Expiration Year) - four digits; at least 2020 and at most 2030.
    """    
    value = int(value)
    return value >= 2020 and value <= 2030

def ecl(value):
    """ ecl (Eye Color) - exactly one of: amb blu brn gry grn hzl oth.
    """
    return value in ['amb', 'blu', 'brn', 'gry', 'grn', 'hzl', 'oth']

def hcl(value):
    """ hcl (Hair Color) - a # followed by exactly six characters 0-9 or a-f.
    """
    if len(value) != 7:
        return False
    if value[0] != '#':
        return False
    return all([c in "0123456789abcdef" for c in value[1:]])
    
def hgt(value):
    """ hgt (Height) - a number followed by either cm or in:
        If cm, the number must be at least 150 and at most 193.
        If in, the number must be at least 59 and at most 76.
    """
    if value.endswith("cm"):
        hv = int(value[:-2])
        return hv >= 150 and hv <= 193 
    elif value.endswith("in"):
        hv = int(value[:-2])
        return hv >= 59 and hv <= 76 
    return False

def pid(value):
    """ pid (Passport ID) - a nine-digit number, including leading zeroes.
    """
    if len(value) != 9:
        return False
    return all([c in "0123456789" for c in value])
    
    
def cid(value):
    """  cid (Country ID) - ignored, missing or not.
    """
    return True


field_validators = {
    "byr": byr,
    "iyr": iyr,
    "eyr": eyr,
    "ecl": ecl,
    "hgt": hgt,
    "hcl": hcl,
    "pid": pid,
    "cid": cid
}

def valid2(passport):
    """Validate passport
    Assumes no duplicated fields, and no horribly malformed ones
    """
    if not valid1(passport):
        return False

    for field in passport:
        ftype, value = field.split(":")
        try:
            if not field_validators[ftype](value):
                return False
        except:
            return False
        
    return True
  

ok = 0
for passport in passports:
      if valid2(passport):
            ok += 1
            
print(f"{ok} passports are OK for part 2")
103 passports are OK for part 2

--- Day 5: Binary Boarding ---

You board your plane only to discover a new problem: you dropped your boarding pass! You aren't sure which seat is yours, and all of the flight attendants are busy with the flood of people that suddenly made it through passport control.

You write a quick program to use your phone's camera to scan all of the nearby boarding passes (your puzzle input); perhaps you can find your seat through process of elimination.

Instead of zones or groups, this airline uses binary space partitioning to seat people. A seat might be specified like FBFBBFFRLR, where F means "front", B means "back", L means "left", and R means "right".

The first 7 characters will either be F or B; these specify exactly one of the 128 rows on the plane (numbered 0 through 127). Each letter tells you which half of a region the given seat is in. Start with the whole list of rows; the first letter indicates whether the seat is in the front (0 through 63) or the back (64 through 127). The next letter indicates which half of that region the seat is in, and so on until you're left with exactly one row.

For example, consider just the first seven characters of FBFBBFFRLR:

Start by considering the whole range, rows 0 through 127.
F means to take the lower half, keeping rows 0 through 63.
B means to take the upper half, keeping rows 32 through 63.
F means to take the lower half, keeping rows 32 through 47.
B means to take the upper half, keeping rows 40 through 47.
B keeps rows 44 through 47.
F keeps rows 44 through 45.
The final F keeps the lower of the two, row 44.

The last three characters will be either L or R; these specify exactly one of the 8 columns of seats on the plane (numbered 0 through 7). The same process as above proceeds again, this time with only three steps. L means to keep the lower half, while R means to keep the upper half.

For example, consider just the last 3 characters of FBFBBFFRLR:

Start by considering the whole range, columns 0 through 7.
R means to take the upper half, keeping columns 4 through 7.
L means to take the lower half, keeping columns 4 through 5.
The final R keeps the upper of the two, column 5.

So, decoding FBFBBFFRLR reveals that it is the seat at row 44, column 5.

Every seat also has a unique seat ID: multiply the row by 8, then add the column. In this example, the seat has ID 44 * 8 + 5 = 357.

Here are some other boarding passes:

BFFFBBFRRR: row 70, column 7, seat ID 567.
FFFBBBFRRR: row 14, column 7, seat ID 119.
BBFFBBFRLL: row 102, column 4, seat ID 820.

As a sanity check, look through your list of boarding passes. What is the highest seat ID on a boarding pass?

--- Part Two ---

Ding! The "fasten seat belt" signs have turned on. Time to find your seat.

It's a completely full flight, so your seat should be the only missing boarding pass in your list. However, there's a catch: some of the seats at the very front and back of the plane don't exist on this aircraft, so they'll be missing from your list as well.

Your seat wasn't at the very front or back, though; the seats with IDs +1 and -1 from yours will be in your list.

In [ ]:
# Confirm that it is simple binary conversion
[0b1000110111, 0b0001110111, 0b1100110100]  # B,R = 1, F,L = 0
Out[ ]:
[567, 119, 820]
In [ ]:
def seat_id1(line):
    """Convert each letter to equivalent binary digits"""
    line = line.replace('F', '0')
    line = line.replace('B', '1')
    line = line.replace('L', '0')
    line = line.replace('R', '1')
    return int(line, 2)

tt = str.maketrans("FLBR", "0011")
def seat_id(line):
    """Use translation table to convert letters to binary digits"""
    return int(line.translate(tt), 2)

assert(seat_id("BFFFBBFRRR") == 567)
assert(seat_id("BBFFBBFRLL") == 820)

ids = sorted(read_and_clean(5, seat_id))

print("Max ID", max(ids))
Input [372, 551] ... [142, 169]
Max ID 842
In [ ]:
# Part 2
for i in range(len(ids) - 1):
    if ids[i+1] - ids[i] > 1:  # non-consecutive integers
        print("My seat id", ids[i] + 1)
        break
My seat id 617

--- Day 6: Custom Customs ---

As your flight approaches the regional airport where you'll switch to a much larger plane, customs declaration forms are distributed to the passengers.

The form asks a series of 26 yes-or-no questions marked a through z. All you need to do is identify the questions for which anyone in your group answers "yes". Since your group is just you, this doesn't take very long.

However, the person sitting next to you seems to be experiencing a language barrier and asks if you can help. For each of the people in their group, you write down the questions for which they answer "yes", one per line. For example:

abcx abcy abcz

In this group, there are 6 questions to which anyone answered "yes": a, b, c, x, y, and z. (Duplicate answers to the same question don't count extra; each question counts at most once.)

Another group asks for your help, then another, and eventually you've collected answers from every group on the plane (your puzzle input). Each group's answers are separated by a blank line, and within each group, each person's answers are on a single line. For example:

abc

a
b
c

ab
ac

a
a
a
a

b

This list represents answers from five groups:

The first group contains one person who answered "yes" to 3 questions: a, b, and c.
The second group contains three people; combined, they answered "yes" to 3 questions: a, b, and c.
The third group contains two people; combined, they answered "yes" to 3 questions: a, b, and c.
The fourth group contains four people; combined, they answered "yes" to only 1 question, a.
The last group contains one person who answered "yes" to only 1 question, b.

In this example, the sum of these counts is 3 + 3 + 3 + 1 + 1 = 11.

For each group, count the number of questions to which anyone answered "yes". What is the sum of those counts?

In [ ]:
def group_lines(lines):
    """
    gather groups of lines separated by a blank line into a list of lists
    """
    groups = []
    group = []
    for line in lines:
        if line == "":
            groups.append(group)
            group = []
        else:
            group.append(line)
            
    if len(group):
        groups.append(group)
        
    return groups


groups = group_lines(read_and_clean(6))
Input ['clvxybjp', 'kripatlzy'] ... ['ghltscmpfadkienz', 'nsdemfhgpzklctia']
In [ ]:
def unique_letters(group):
    s = set()
    for member in group:
        s = s.union(member) 
        
    return s


sum([len(unique_letters(g)) for g in groups])
Out[ ]:
6457

--- Part Two ---

As you finish the last group's customs declaration, you notice that you misread one word in the instructions:

You don't need to identify the questions to which anyone answered "yes"; you need to identify the questions to which everyone answered "yes"!

Using the same example as above:

abc

a
b
c

ab
ac

a
a
a
a

b

This list represents answers from five groups:

In the first group, everyone (all 1 person) answered "yes" to 3 questions: a, b, and c.
In the second group, there is no question to which everyone answered "yes".
In the third group, everyone answered yes to only 1 question, a. Since some people did not answer "yes" to b or c, they don't count.
In the fourth group, everyone answered yes to only 1 question, a.
In the fifth group, everyone (all 1 person) answered "yes" to 1 question, b.

In this example, the sum of these counts is 3 + 0 + 1 + 1 + 1 = 6.

For each group, count the number of questions to which everyone answered "yes". What is the sum of those counts?

In [ ]:
def common_letters(group):
    s = set(group[0])
    for member in group:
        s = s.intersection(member) 
        
    return s

sum([len(common_letters(g)) for g in groups])
Out[ ]:
3260

--- Day 7: Handy Haversacks ---

You land at the regional airport in time for your next flight. In fact, it looks like you'll even have time to grab some food: all flights are currently delayed due to issues in luggage processing.

Due to recent aviation regulations, many rules (your puzzle input) are being enforced about bags and their contents; bags must be color-coded and must contain specific quantities of other color-coded bags. Apparently, nobody responsible for these regulations considered how long they would take to enforce!

For example, consider the following rules:

light red bags contain 1 bright white bag, 2 muted yellow bags. dark orange bags contain 3 bright white bags, 4 muted yellow bags. bright white bags contain 1 shiny gold bag. muted yellow bags contain 2 shiny gold bags, 9 faded blue bags. shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags. dark olive bags contain 3 faded blue bags, 4 dotted black bags. vibrant plum bags contain 5 faded blue bags, 6 dotted black bags. faded blue bags contain no other bags. dotted black bags contain no other bags.

These rules specify the required contents for 9 bag types. In this example, every faded blue bag is empty, every vibrant plum bag contains 11 bags (5 faded blue and 6 dotted black), and so on.

You have a shiny gold bag. If you wanted to carry it in at least one other bag, how many different bag colors would be valid for the outermost bag? (In other words: how many colors can, eventually, contain at least one shiny gold bag?)

In the above rules, the following options would be available to you:

A bright white bag, which can hold your shiny gold bag directly.
A muted yellow bag, which can hold your shiny gold bag directly, plus some other bags.
A dark orange bag, which can hold bright white and muted yellow bags, either of which could then hold your shiny gold bag.
A light red bag, which can hold bright white and muted yellow bags, either of which could then hold your shiny gold bag.

So, in this example, the number of bag colors that can eventually contain at least one shiny gold bag is 4.

How many bag colors can eventually contain at least one shiny gold bag? (The list of rules is quite long; make sure you get all of it.)

In [ ]:
def make_rule(line):
    """Parse input line into 'rule'
    
    >>> make_rule('clear purple bags contain 5 faded indigo bags, 3 muted purple bags.')
    ('clear purple', ['faded indigo', 'muted purple'], [5, 3])
    >>> make_rule('muted crimson bags contain no other bags.')
    ('muted crimson', [], [])
    """
    ss = line.replace(' bags', '')  # remove noise words
    ss = line.replace(' bag', '')
    ss = ss.replace('.', '')
    bag, contains = ss.split('contain')
    bag = bag.strip()[:-1]  # remove trailing plural s
    cl = contains.split(',')
    cl = [c.strip() for c in cl]
    rules = []
    counts = []
    for c in cl:
        cf = c.split(' ')
        try:
            nb = int(cf[0])
            cn = ' '.join(cf[1:])
            if nb > 1:  # remove trailing 's'
                cn = cn[:-1]
            rules.append(cn)
            counts.append(nb)
        except ValueError:
            #print(line, bag, rl)
            pass
        

    return bag, rules, counts


print(
    make_rule('clear purple bags contain 5 faded indigo bags, 1 rose gold bag, 3 muted purple bags.'),
    make_rule('muted crimson bags contain no other bags.'),
    '\n'
)

rules = read_and_clean(7, make_rule)
('clear purple', ['faded indigo', 'rose gold', 'muted purple'], [5, 1, 3]) ('muted crimson', [], []) 

Input [('clear purple', ['faded indigo', 'muted purple'], [5, 3]), ('bright teal', ['striped plum'], [4])] ... [('dim tomato', ['drab lime', 'vibrant tomato'], [3, 4]), ('mirrored maroon', ['drab coral'], [3])]
In [ ]:
# now, how to find bags that can contain shiny gold bag?
# This is the first hard challenge!
        
def reachable(origin, rules, seen=None, level=0):
    if seen is None:
        seen = set()
    seen.add(origin)
    #print(' '*level, origin)
    for bag, contents, _ in rules:
        if bag in seen:
            continue  # skip ones that we already know about
        if origin in contents:   # this bag can contain origin
            seen = reachable(bag, rules, seen, level + 1)
            # Note assignment not required, cos seen is passed by reference and mutated
    # Get here when origin is not in contents of any unseen bags
    return seen

r = reachable('shiny gold', rules)
# r contains original 'shiny gold', so subtract 1 to get all reachable from there
len(r) - 1
Out[ ]:
185

--- Part Two ---

It's getting pretty expensive to fly these days - not because of ticket prices, but because of the ridiculous number of bags you need to buy!

Consider again your shiny gold bag and the rules from the above example:

faded blue bags contain 0 other bags.
dotted black bags contain 0 other bags.
vibrant plum bags contain 11 other bags: 5 faded blue bags and 6 dotted black bags.
dark olive bags contain 7 other bags: 3 faded blue bags and 4 dotted black bags.

So, a single shiny gold bag must contain 1 dark olive bag (and the 7 bags within it) plus 2 vibrant plum bags (and the 11 bags within each of those): 1 + 17 + 2 + 211 = 32 bags!

Of course, the actual rules have a small chance of going several levels deeper than this example; be sure to count all of the bags, even if the nesting becomes topologically impractical!

Here's another example:

shiny gold bags contain 2 dark red bags. dark red bags contain 2 dark orange bags. dark orange bags contain 2 dark yellow bags. dark yellow bags contain 2 dark green bags. dark green bags contain 2 dark blue bags. dark blue bags contain 2 dark violet bags. dark violet bags contain no other bags.

In this example, a single shiny gold bag must contain 126 other bags.

How many individual bags are required inside your single shiny gold bag?

In [ ]:
# Make a dict key=colour, value = list of contents and count pairs
# so we can get from a given colour to the colours and counts of required contents
rdl = [(r[0], list(zip(r[1], r[2]))) for r in rules]
bags_data = dict(rdl)
bags_data['shiny gold']
Out[ ]:
[('plaid bronze', 5),
 ('bright fuchsia', 4),
 ('light violet', 2),
 ('clear plum', 1)]
In [ ]:
def total_inside(bag_colour, bags, level=0):
    """Calculate the total number of bags inside a bag of 
    the given colour, given a bags database
    level parameter is just used for debug recursion visualization
    """
    #print(' ' * level, bag_colour)
    contents = bags[bag_colour]
    if not contents: # Be clear that recursion ends when bag has no contents, returns 0 
        return 0     # not strictly necessary cos for loop will drop thru anyway
    
    total = 0
    for colour, count in contents:
        # Each bag includes itself + *its* contents, repeated 'count' times
        total += count * (1 + total_inside(colour, bags, level+1))
    
    if level > 100:  # Just in case...
        raise ValueError("Recursion too deep")
    return total

total_inside('shiny gold', bags_data)
Out[ ]:
89084

--- Day 8: Handheld Halting ---

Your flight to the major airline hub reaches cruising altitude without incident. While you consider checking the in-flight menu for one of those drinks that come with a little umbrella, you are interrupted by the kid sitting next to you.

Their handheld game console won't turn on! They ask if you can take a look.

You narrow the problem down to a strange infinite loop in the boot code (your puzzle input) of the device. You should be able to fix it, but first you need to be able to run the code in isolation.

The boot code is represented as a text file with one instruction per line of text. Each instruction consists of an operation (acc, jmp, or nop) and an argument (a signed number like +4 or -20).

acc increases or decreases a single global value called the accumulator by the value given in the argument. For example, acc +7 would increase the accumulator by 7. The accumulator starts at 0. After an acc instruction, the instruction immediately below it is executed next.
jmp jumps to a new instruction relative to itself. The next instruction to execute is found using the argument as an offset from the jmp instruction; for example, jmp +2 would skip the next instruction, jmp +1 would continue to the instruction immediately below it, and jmp -20 would cause the instruction 20 lines above to be executed next.
nop stands for No OPeration - it does nothing. The instruction immediately below it is executed next.

For example, consider the following program:

nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6

These instructions are visited in this order:

nop +0 | 1 acc +1 | 2, 8(!) jmp +4 | 3 acc +3 | 6 jmp -3 | 7 acc -99 | acc +1 | 4 jmp -4 | 5 acc +6 |

First, the nop +0 does nothing. Then, the accumulator is increased from 0 to 1 (acc +1) and jmp +4 sets the next instruction to the other acc +1 near the bottom. After it increases the accumulator from 1 to 2, jmp -4 executes, setting the next instruction to the only acc +3. It sets the accumulator to 5, and jmp -3 causes the program to continue back at the first acc +1.

This is an infinite loop: with this sequence of jumps, the program will run forever. The moment the program tries to run any instruction a second time, you know it will never terminate.

Immediately before the program would run an instruction a second time, the value in the accumulator is 5.

Run your copy of the boot code. Immediately before any instruction is executed a second time, what value is in the accumulator?

In [ ]:
def program_line(line):
    fields = line.split()
    return [fields[0], int(fields[1])]
                          
program = read_and_clean(8, program_line)
Input [['jmp', 583], ['acc', 9]] ... [['acc', 28], ['jmp', 1]]
In [ ]:
def run(program):
    acc = 0
    visited = []
    pc = 0

    while True:
        if pc == len(program):
            looped = 0  # Normal termination
            break
        elif pc > len(program):
            looped = -1  # Error
            break  
        elif pc in visited:
            #print(f"Visiting {pc} again, acc = {acc}")
            looped = 1  # Infinite loop found
            break
        
        visited.append(pc)

        opcode, value = program[pc]
            #print(f"{pc} {opcode} {value} {acc}")
        if opcode == 'nop':
            pc += 1
        elif opcode == 'acc':
            acc += value
            pc += 1
        elif opcode == 'jmp':
            pc += value
        else:
            print(f"Unexpected {opcode}")
        
    return acc, looped
    
run(program)
Out[ ]:
(2051, 1)

--- Part Two ---

After some careful analysis, you believe that exactly one instruction is corrupted.

Somewhere in the program, either a jmp is supposed to be a nop, or a nop is supposed to be a jmp. (No acc instructions were harmed in the corruption of this boot code.)

The program is supposed to terminate by attempting to execute an instruction immediately after the last instruction in the file. By changing exactly one jmp or nop, you can repair the boot code and make it terminate correctly.

For example, consider the same program from above:

nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6

If you change the first instruction from nop +0 to jmp +0, it would create a single-instruction infinite loop, never leaving that instruction. If you change almost any of the jmp instructions, the program will still eventually find another jmp instruction and loop forever.

However, if you change the second-to-last instruction (from jmp -4 to nop -4), the program terminates! The instructions are visited in this order:

nop +0 | 1 acc +1 | 2 jmp +4 | 3 acc +3 | jmp -3 | acc -99 | acc +1 | 4 nop -4 | 5 acc +6 | 6

After the last instruction (acc +6), the program terminates by attempting to run the instruction below the last instruction in the file. With this change, after the program terminates, the accumulator contains the value 8 (acc +1, acc +1, acc +6).

Fix the program so that it terminates normally by changing exactly one jmp (to nop) or nop (to jmp). What is the value of the accumulator after the program terminates?

In [ ]:
example= [program_line(l) for l in """nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
nop -4
acc +6""".split('\n')]
run(example)
Out[ ]:
(8, 0)
In [ ]:
import copy

def mutate(instruction):
    """Mutate nop and jmp, return True
    OR return False on no change
    """
    if instruction[0] == 'nop':
        instruction[0] = 'jmp'
    elif instruction[0] == 'jmp':
        instruction[0] = 'nop'
    else:
        return False

    return True


def find_good_program(program):
    newprog = copy.deepcopy(program)
    for pc in range(len(newprog)):
        # Search for jmp and nop to swap over
        if mutate(newprog[pc]):
            acc, looped = run(newprog)
            if looped == 0:  # Normal termination
                break
            mutate(newprog[pc])  # Undo this mutation before moving on
        
    return acc, newprog    


acc, _ = find_good_program(program)
print(f"Accumulator={acc}")
Accumulator=2304

--- Day 9: Encoding Error ---

With your neighbor happily enjoying their video game, you turn your attention to an open data port on the little screen in the seat in front of you.

Though the port is non-standard, you manage to connect it to your computer through the clever use of several paperclips. Upon connection, the port outputs a series of numbers (your puzzle input).

The data appears to be encrypted with the eXchange-Masking Addition System (XMAS) which, conveniently for you, is an old cypher with an important weakness.

XMAS starts by transmitting a preamble of 25 numbers. After that, each number you receive should be the sum of any two of the 25 immediately previous numbers. The two numbers will have different values, and there might be more than one such pair.

For example, suppose your preamble consists of the numbers 1 through 25 in a random order. To be valid, the next number must be the sum of two of those numbers:

26 would be a valid next number, as it could be 1 plus 25 (or many other pairs, like 2 and 24).
49 would be a valid next number, as it is the sum of 24 and 25.
100 would not be valid; no two of the previous 25 numbers sum to 100.
50 would also not be valid; although 25 appears in the previous 25 numbers, the two numbers in the pair must be different.

Suppose the 26th number is 45, and the first number (no longer an option, as it is more than 25 numbers ago) was 20. Now, for the next number to be valid, there needs to be some pair of numbers among 1-19, 21-25, or 45 that add up to it:

26 would still be a valid next number, as 1 and 25 are still within the previous 25 numbers.
65 would not be valid, as no two of the available numbers sum to it.
64 and 66 would both be valid, as they are the result of 19+45 and 21+45 respectively.

Here is a larger example which only considers the previous 5 numbers (and has a preamble of length 5):

35 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576

In this example, after the 5-number preamble, almost every number is the sum of two of the previous 5 numbers; the only number that does not follow this rule is 127.

The first step of attacking the weakness in the XMAS data is to find the first number in the list (after the preamble) which is not the sum of two of the 25 numbers before it. What is the first number that does not have this property?

In [ ]:
nums = read_and_clean(9, int)
Input [19, 20] ... [135541709682585, 57812792009627]
In [ ]:
from itertools import combinations

def find_invalid(nums, prelen=25):
    for i in range(len(nums) - prelen):
        valid = set([sum(c) for c in combinations(nums[i:i+prelen], 2)])
        ans = nums[i + prelen]
        if not ans in valid:
            break
    return ans

invalid = find_invalid([int(n) for n in "35 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576".split()], 5)
print(invalid)

invalid = find_invalid(nums)
invalid
127
Out[ ]:
556543474

--- Part Two ---

The final step in breaking the XMAS encryption relies on the invalid number you just found: you must find a contiguous set of at least two numbers in your list which sum to the invalid number from step 1.

Again consider the above example:

35 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576

In this list, adding up all of the numbers from 15 through 40 produces the invalid number from step 1, 127. (Of course, the contiguous set of numbers in your actual list might be much longer.)

To find the encryption weakness, add together the smallest and largest number in this contiguous range; in this example, these are 15 and 47, producing 62.

What is the encryption weakness in your XMAS-encrypted list of numbers?

In [ ]:
def find_weakness(nums, invalid):
    ln = len(nums)
    found = False
    
    for start in range(ln):
        for length in range(2, ln - start):
            subrange = nums[start:start+length]
            subsum = sum(subrange)
            if subsum == invalid:
                found = True
                break
        if found:
            break
            
    minval = min(subrange)
    maxval = max(subrange)
    return minval + maxval

find_weakness(nums, invalid)
Out[ ]:
76096372

--- Day 10: Adapter Array ---

Patched into the aircraft's data port, you discover weather forecasts of a massive tropical storm. Before you can figure out whether it will impact your vacation plans, however, your device suddenly turns off!

Its battery is dead.

You'll need to plug it in. There's only one problem: the charging outlet near your seat produces the wrong number of jolts. Always prepared, you make a list of all of the joltage adapters in your bag.

Each of your joltage adapters is rated for a specific output joltage (your puzzle input). Any given adapter can take an input 1, 2, or 3 jolts lower than its rating and still produce its rated output joltage.

In addition, your device has a built-in joltage adapter rated for 3 jolts higher than the highest-rated adapter in your bag. (If your adapter list were 3, 9, and 6, your device's built-in adapter would be rated for 12 jolts.)

Treat the charging outlet near your seat as having an effective joltage rating of 0.

Since you have some time to kill, you might as well test all of your adapters. Wouldn't want to get to your resort and realize you can't even charge your device!

If you use every adapter in your bag at once, what is the distribution of joltage differences between the charging outlet, the adapters, and your device?

For example, suppose that in your bag, you have adapters with the following joltage ratings:

16 10 15 5 1 11 7 19 6 12 4

With these adapters, your device's built-in joltage adapter would be rated for 19 + 3 = 22 jolts, 3 higher than the highest-rated adapter.

Because adapters can only connect to a source 1-3 jolts lower than its rating, in order to use every adapter, you'd need to choose them like this:

The charging outlet has an effective rating of 0 jolts, so the only adapters that could connect to it directly would need to have a joltage rating of 1, 2, or 3 jolts. Of these, only one you have is an adapter rated 1 jolt (difference of 1).
From your 1-jolt rated adapter, the only choice is your 4-jolt rated adapter (difference of 3).
From the 4-jolt rated adapter, the adapters rated 5, 6, or 7 are valid choices. However, in order to not skip any adapters, you have to pick the adapter rated 5 jolts (difference of 1).
Similarly, the next choices would need to be the adapter rated 6 and then the adapter rated 7 (with difference of 1 and 1).
The only adapter that works with the 7-jolt rated adapter is the one rated 10 jolts (difference of 3).
From 10, the choices are 11 or 12; choose 11 (difference of 1) and then 12 (difference of 1).
After 12, only valid adapter has a rating of 15 (difference of 3), then 16 (difference of 1), then 19 (difference of 3).
Finally, your device's built-in adapter is always 3 higher than the highest adapter, so its rating is 22 jolts (always a difference of 3).

In this example, when using every adapter, there are 7 differences of 1 jolt and 5 differences of 3 jolts.

Here is a larger example:

28 33 18 42 31 14 46 20 48 47 24 23 49 45 19 38 39 11 1 32 25 35 8 17 7 9 4 2 34 10 3

In this larger example, in a chain that uses all of the adapters, there are 22 differences of 1 jolt and 10 differences of 3 jolts.

Find a chain that uses all of your adapters to connect the charging outlet to your device's built-in adapter and count the joltage differences between the charging outlet, the adapters, and your device. What is the number of 1-jolt differences multiplied by the number of 3-jolt differences?

In [ ]:
nums = sorted(read_and_clean(10, int))

nums.append(nums[-1] + 3)  # Add built in adapter
nums.insert(0,0)  # Add outlet
diffs = []
for i in range(len(nums) - 1):
    diffs.append(nums[i+1] - nums[i])
    
len(diffs),diffs.count(1) *diffs.count(3)
Input [99, 151] ... [55, 83]
Out[ ]:
(102, 2312)

--- Part Two ---

To completely determine whether you have enough adapters, you'll need to figure out how many different ways they can be arranged. Every arrangement needs to connect the charging outlet to your device. The previous rules about when adapters can successfully connect still apply.

The first example above (the one that starts with 16, 10, 15) supports the following arrangements:

(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22) (0), 1, 4, 5, 6, 7, 10, 12, 15, 16, 19, (22) (0), 1, 4, 5, 7, 10, 11, 12, 15, 16, 19, (22) (0), 1, 4, 5, 7, 10, 12, 15, 16, 19, (22) (0), 1, 4, 6, 7, 10, 11, 12, 15, 16, 19, (22) (0), 1, 4, 6, 7, 10, 12, 15, 16, 19, (22) (0), 1, 4, 7, 10, 11, 12, 15, 16, 19, (22) (0), 1, 4, 7, 10, 12, 15, 16, 19, (22)

(The charging outlet and your device's built-in adapter are shown in parentheses.) Given the adapters from the first example, the total number of arrangements that connect the charging outlet to your device is 8.

The second example above (the one that starts with 28, 33, 18) has many arrangements. Here are a few:

(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31, 32, 33, 34, 35, 38, 39, 42, 45, 46, 47, 48, 49, (52)

(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31, 32, 33, 34, 35, 38, 39, 42, 45, 46, 47, 49, (52)

(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31, 32, 33, 34, 35, 38, 39, 42, 45, 46, 48, 49, (52)

(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31, 32, 33, 34, 35, 38, 39, 42, 45, 46, 49, (52)

(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31, 32, 33, 34, 35, 38, 39, 42, 45, 47, 48, 49, (52)

(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45, 46, 48, 49, (52)

(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45, 46, 49, (52)

(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45, 47, 48, 49, (52)

(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45, 47, 49, (52)

(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45, 48, 49, (52)

In total, this set of adapters can connect the charging outlet to your device in 19208 distinct arrangements.

You glance back down at your bag and try to remember why you brought so many adapters; there must be more than a trillion valid ways to arrange them! Surely, there must be an efficient way to count the arrangements.

What is the total number of distinct ways you can arrange the adapters to connect the charging outlet to your device?

In [ ]:
# Naïve solution leads to combinatorial explosion! 
# Notice that there is only one way to cross a 3 jolt boundary, so multiple ways only happen in runs of
# 1 jolt differences, separate runs are independent
# So first, collect the length of all runs of ones in the differences

one_runs = []
run = 0
for i in range(len(diffs)):
    if diffs[i] == 1:
        run += 1
    else:
        if run:
            one_runs.append(run)
        run = 0

print(f"{one_runs=}")
print(f"Max run {max(one_runs)}")

# Work out by hand how many ways through a run of ones, max step = 3
# 0 (1)
# 1 = 1 (1)
# 2 = 1+1 or 2 (2)
# 3 = 1+1+1 1+2 2+1 3  (4)
# 4 = 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 3+1 1+3 (7)
# N = 1+patterns(N-1) 2+patterns(N-2) 3+patterns(N-3) (ways(N-1) + ways(N-2) + ways(N-3))

ways = [1, 1, 2, 4, 7, 12, 23]  # Index = run length, value = ways through

way_combos = [ways[x] for x in one_runs]  # Convert run lengths to way countsb
print(f"{way_combos=}")
print(f"{reduce(mul, way_combos)=}")  # total ways is product of independent way counts
one_runs=[4, 1, 3, 4, 4, 2, 3, 3, 3, 3, 4, 3, 1, 3, 2, 4, 2, 4, 3, 2, 4, 4, 2]
Max run 4
way_combos=[7, 1, 4, 7, 7, 2, 4, 4, 4, 4, 7, 4, 1, 4, 2, 7, 2, 7, 4, 2, 7, 7, 2]
reduce(mul, way_combos)=12089663946752

--- Day 11: Seating System ---

Your plane lands with plenty of time to spare. The final leg of your journey is a ferry that goes directly to the tropical island where you can finally start your vacation. As you reach the waiting area to board the ferry, you realize you're so early, nobody else has even arrived yet!

By modeling the process people use to choose (or abandon) their seat in the waiting area, you're pretty sure you can predict the best place to sit. You make a quick map of the seat layout (your puzzle input).

The seat layout fits neatly on a grid. Each position is either floor (.), an empty seat (L), or an occupied seat (#). For example, the initial seat layout might look like this:

In [ ]:
initial11 = """L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL"""

Now, you just need to model the people who will be arriving shortly. Fortunately, people are entirely predictable and always follow a simple set of rules. All decisions are based on the number of occupied seats adjacent to a given seat (one of the eight positions immediately up, down, left, right, or diagonal from the seat). The following rules are applied to every seat simultaneously:

If a seat is empty (L) and there are no occupied seats adjacent to it, the seat becomes occupied.
If a seat is occupied (#) and four or more seats adjacent to it are also occupied, the seat becomes empty.
Otherwise, the seat's state does not change.

Floor (.) never changes; seats don't move, and nobody sits on the floor.

In [ ]:
#After one round of these rules, every seat in the example layout becomes occupied:

outputs11_1 = [
"""#.##.##.##
#######.##
#.#.#..#..
####.##.##
#.##.##.##
#.#####.##
..#.#.....
##########
#.######.#
#.#####.##""",

#After a second round, the seats with four or more occupied adjacent seats become empty again:

"""#.LL.L#.##
#LLLLLL.L#
L.L.L..L..
#LLL.LL.L#
#.LL.LL.LL
#.LLLL#.##
..L.L.....
#LLLLLLLL#
#.LLLLLL.L
#.#LLLL.##""",

#This process continues for three more rounds:

"""#.##.L#.##
#L###LL.L#
L.#.#..#..
#L##.##.L#
#.##.LL.LL
#.###L#.##
..#.#.....
#L######L#
#.LL###L.L
#.#L###.##""",

"""#.#L.L#.##
#LLL#LL.L#
L.L.L..#..
#LLL.##.L#
#.LL.LL.LL
#.LL#L#.##
..L.L.....
#L#LLLL#L#
#.LLLLLL.L
#.#L#L#.##"""
,
"""#.#L.L#.##
#LLL#LL.L#
L.#.L..#..
#L##.##.L#
#.#L.LL.LL
#.#L#L#.##
..L.L.....
#L#L##L#L#
#.LLLLLL.L
#.#L#L#.##"""
]
#At this point, something interesting happens: the chaos stabilizes and further applications of these rules cause no seats to change state! Once people stop moving around, you count 37 occupied seats.

#Simulate your seating area by applying the seating rules repeatedly until no seats change state. How many seats end up occupied?

--- Part Two ---

As soon as people start to arrive, you realize your mistake. People don't just care about adjacent seats - they care about the first seat they can see in each of those eight directions!

Now, instead of considering just the eight immediately adjacent seats, consider the first seat in each of those eight directions. For example, the empty seat below would see eight occupied seats:

.......#.
...#.....
.#.......
.........
..#L....#
....#....
.........
#........
...#.....

The leftmost empty seat below would only see one empty seat, but cannot see any of the occupied ones:

.............
.L.L.#.#.#.#.
.............

The empty seat below would see no occupied seats:

.##.##.
#.#.#.#
##...##
...L...
##...##
#.#.#.#
.##.##.

Also, people seem to be more tolerant than you expected: it now takes five or more visible occupied seats for an occupied seat to become empty (rather than four or more from the previous rules). The other rules still apply: empty seats that see no occupied seats become occupied, seats matching no rule don't change, and floor never changes.

Given the same starting layout as above, these new rules cause the seating area to shift around as follows:

In [ ]:
outputs_11_2 = [
    
"""#.##.##.##
#######.##
#.#.#..#..
####.##.##
#.##.##.##
#.#####.##
..#.#.....
##########
#.######.#
#.#####.##""",

"""#.LL.LL.L#
#LLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLL#
#.LLLLLL.L
#.LLLLL.L#""",

"""#.L#.##.L#
#L#####.LL
L.#.#..#..
##L#.##.##
#.##.#L.##
#.#####.#L
..#.#.....
LLL####LL#
#.L#####.L
#.L####.L#""",

"""#.L#.L#.L#
#LLLLLL.LL
L.L.L..#..
##LL.LL.L#
L.LL.LL.L#
#.LLLLL.LL
..L.L.....
LLLLLLLLL#
#.LLLLL#.L
#.L#LL#.L#""",

"""#.L#.L#.L#
#LLLLLL.LL
L.L.L..#..
##L#.#L.L#
L.L#.#L.L#
#.L####.LL
..#.#.....
LLL###LLL#
#.LLLLL#.L
#.L#LL#.L#""",

"""#.L#.L#.L#
#LLLLLL.LL
L.L.L..#..
##L#.#L.L#
L.L#.LL.L#
#.LLLL#.LL
..#.L.....
LLL###LLL#
#.LLLLL#.L
#.L#LL#.L#"""
]

Again, at this point, people stop shifting around and the seating area reaches equilibrium. Once this occurs, you count 26 occupied seats.

Given the new visibility method and the rule change for occupied seats becoming empty, once equilibrium is reached, how many seats end up occupied?

In [ ]:
seating = read_and_clean(11)
Input ['LLLLLLLLLLL..LLLLLL.LLLLL.LLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLL.LLLLLL.LL.LLLLLLLL..LLLLL', 'LLLLL..L.LLL.L.LLLL.LLLLLLLLLLLLLL.LLLLLL.LLLLLLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLLL.LLLLLL..LLLL'] ... ['LLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLL.LLLLLL.LLLLL', 'LLLLLL.LLLLL.LLLLLL.LLLLLLLLLLLLLL.LLLLLL.LL.LLLLLL.LLLLLLLLLL.LLL.LLLLLL..LLLL.LLLLLLLLLLLL']
In [ ]:
# 2D Cellular automaton using rule. Data is list of strings. Strings are row data.
def update(seat_states, rule):  
    """Update states according to the rule function"""
    new_rows = []
    anychanged = 0
    for y in range(len(seat_states)):
        new_row = ''
        for x in range(len(seat_states[0])):
            position = x, y
            new_state, change = rule(seat_states, position)
            new_row += new_state
            anychanged += change
        new_rows.append(new_row)
        
    return new_rows, anychanged


def settle(seat_states, newstate):
    """Repeatedly update seat state until it doesn't change on update"""
    anychanged = 1
    while anychanged:
        seat_states, anychanged = update(seat_states, newstate)
   
    return sum([l.count('#') for l in seat_states])
In [ ]:
def look_near(lines, pos, direction):
    """Look at neighbour in direction given"""
    x = pos[0]
    y = pos[1]
    x += direction[0]
    y += direction[1]
    if x < 0 or y < 0 or x == len(lines[0]) or y == len(lines):
        return 0  # crossed the edge
    if lines[y][x] == '#':
        return 1
    if lines[y][x] == 'L':
        return 0
    return 0

def look_far(lines, pos, direction):
    """Look along line in given direction, until seat or wall encountered"""
    x, y = pos
    while True:
        x += direction[0]
        y += direction[1]
        if x < 0 or y < 0 or x == len(lines[0]) or y == len(lines):
            return 0  # crossed the edge
        if lines[y][x] == '#':
            return 1
        if lines[y][x] == 'L':
            return 0

        pzm = (1, 0, -1)

directions = ((1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0, -1), (1, -1))
        
def newstate(seats:typing.List[str], 
             position: typing.Tuple[int, int], 
             crowded:int, 
             looker: typing.Callable) -> typing.Tuple[int, int]:
    """
    Return (new state at position), (changed flag)
    """
    x, y = position
    current = seats[y][x]
    if  current == '.':
        return '.', 0

    crowding = 0
    for direction in directions:
        crowding += looker(seats, position, direction)

    if crowding >= crowded and current == '#':
        return 'L', 1
    elif crowding == 0 and current == 'L':
        return '#', 1
    else:
        return current, 0

       
def newstate1(seating, pos):
    return newstate(seating, pos, 4, look_near)


def newstate2(seating, pos):
    return newstate(seating, pos, 5, look_far)
In [ ]:
#Test against supplied example
print('\nPart 1\n')
ans = initial11.split('\n')
for i in range(len(outputs11_1)):
    ans, changed = update(ans, newstate1)
    ref = outputs11_1[i].split('\n')
    print(i, changed, ans==ref)
    
print('\n'.join(ans))

print('\nPart 2\n')
ans = initial11.split('\n')
for i in range(len(outputs_11_2)):
    ans, changed = update(ans, newstate2)
    ref = outputs_11_2[i].split('\n')
    print(i, changed, ans==ref)
    
print('\n'.join(ans))
Part 1

0 71 True
1 51 True
2 31 True
3 21 True
4 7 True
#.#L.L#.##
#LLL#LL.L#
L.#.L..#..
#L##.##.L#
#.#L.LL.LL
#.#L#L#.##
..L.L.....
#L#L##L#L#
#.LLLLLL.L
#.#L#L#.##

Part 2

0 71 True
1 64 True
2 46 True
3 35 True
4 13 True
5 5 True
#.L#.L#.L#
#LLLLLL.LL
L.L.L..#..
##L#.#L.L#
L.L#.LL.L#
#.LLLL#.LL
..#.L.....
LLL###LLL#
#.LLLLL#.L
#.L#LL#.L#
In [ ]:
# Finally, the answers to day 11
print("Part 1 and 2 answers")
print(settle(seating, newstate1), settle(seating, newstate2), sep='\n')
Part 1 and 2 answers
2254
2004

--- Day 12: Rain Risk ---

Your ferry made decent progress toward the island, but the storm came in faster than anyone expected. The ferry needs to take evasive actions!

Unfortunately, the ship's navigation computer seems to be malfunctioning; rather than giving a route directly to safety, it produced extremely circuitous instructions. When the captain uses the PA system to ask if anyone can help, you quickly volunteer.

The navigation instructions (your puzzle input) consists of a sequence of single-character actions paired with integer input values. After staring at them for a few minutes, you work out what they probably mean:

Action N means to move north by the given value.
Action S means to move south by the given value.
Action E means to move east by the given value.
Action W means to move west by the given value.
Action L means to turn left the given number of degrees.
Action R means to turn right the given number of degrees.
Action F means to move forward by the given value in the direction the ship is currently facing.

The ship starts by facing east. Only the L and R actions change the direction the ship is facing. (That is, if the ship is facing east and the next instruction is N10, the ship would move north 10 units, but would still move east if the following action were F.)

For example:

F10 N3 F7 R90 F11

These instructions would be handled as follows:

F10 would move the ship 10 units east (because the ship starts by facing east) to east 10, north 0.
N3 would move the ship 3 units north to east 10, north 3.
F7 would move the ship another 7 units east (because the ship is still facing east) to east 17, north 3.
R90 would cause the ship to turn right by 90 degrees and face south; it remains at east 17, north 3.
F11 would move the ship 11 units south to east 17, south 8.

At the end of these instructions, the ship's Manhattan distance (sum of the absolute values of its east/west position and its north/south position) from its starting position is 17 + 8 = 25.

Figure out where the navigation instructions lead. What is the Manhattan distance between that location and the ship's starting position?

In [ ]:
def command(line):
    return line[0], int(line[1:])

commands = read_and_clean(12, command)

example_commands = [('F', 10), ('N', 3), ('F', 7), ('R', 90), ('F', 11)]
Input [('W', 5), ('F', 66)] ... [('L', 90), ('F', 62)]
In [ ]:
compass = 'NESW'
current_direction = 'E'
current_position = (0, 0)  #  E/W, N/S  N,E are +ve

def navigate(command, current_direction, current_position):
    action, value = command
    if action == 'N':
        current_position = (current_position[0], current_position[1] + value)
    elif action == 'S':
        current_position = (current_position[0], current_position[1] - value)
    elif action == 'E':
        current_position = (current_position[0] + value, current_position[1])
    elif action == 'W':
        current_position = (current_position[0] - value, current_position[1])
    elif action in 'RL':  # changing directions
        rotation = value // 90
        if action == 'L':
            rotation = -rotation
        ci = compass.find(current_direction)
        ci = (ci + rotation) % 4
        current_direction = compass[ci]
    elif action == 'F':  # Move in current direction
        current_direction, current_position = navigate((current_direction, value), current_direction, current_position)
    else:
        raise ValueError("Unknown Action", action)
   
    #print(f"{command=} {current_direction=} {current_position=}")
    return current_direction, current_position

route = [current_position]
for command in commands:
    current_direction, current_position = navigate(command, current_direction, current_position)
    route.append(current_position)
    
print(current_direction, current_position)
manhattan_distance = sum([abs(x) for x in current_position])
print(f"Day 12 part 1 answer is {manhattan_distance}")
W (1209, -394)
Day 12 part 1 answer is 1603
In [ ]:
import matplotlib.pyplot as pp
pp.plot(*zip(*route))
pp.grid()

--- Day 12 Part Two ---

Before you can give the destination to the captain, you realize that the actual action meanings were printed on the back of the instructions the whole time.

Almost all of the actions indicate how to move a waypoint which is relative to the ship's position:

Action N means to move the waypoint north by the given value.
Action S means to move the waypoint south by the given value.
Action E means to move the waypoint east by the given value.
Action W means to move the waypoint west by the given value.
Action L means to rotate the waypoint around the ship left (counter-clockwise) the given number of degrees.
Action R means to rotate the waypoint around the ship right (clockwise) the given number of degrees.
Action F means to move forward to the waypoint a number of times equal to the given value.

The waypoint starts 10 units east and 1 unit north relative to the ship. The waypoint is relative to the ship; that is, if the ship moves, the waypoint moves with it.

For example, using the same instructions as above:

F10 moves the ship to the waypoint 10 times (a total of 100 units east and 10 units north), leaving the ship at east 100, north 10. The waypoint stays 10 units east and 1 unit north of the ship.
N3 moves the waypoint 3 units north to 10 units east and 4 units north of the ship. The ship remains at east 100, north 10.
F7 moves the ship to the waypoint 7 times (a total of 70 units east and 28 units north), leaving the ship at east 170, north 38. The waypoint stays 10 units east and 4 units north of the ship.
R90 rotates the waypoint around the ship clockwise 90 degrees, moving it to 4 units east and 10 units south of the ship. The ship remains at east 170, north 38.
F11 moves the ship to the waypoint 11 times (a total of 44 units east and 110 units south), leaving the ship at east 214, south 72. The waypoint stays 4 units east and 10 units south of the ship.

After these operations, the ship's Manhattan distance from its starting position is 214 + 72 = 286.

Figure out where the navigation instructions actually lead. What is the Manhattan distance between that location and the ship's starting position?

In [ ]:
direction = 'E'
position = (0, 0)  # E/W, N/S  N,E are +ve
waypoint = (10, 1)


def navigate(command, position, waypoint):
    action, value = command
    if action == 'F':  # Move in current direction
        position = (position[0] + value * waypoint[0], position[1] + value * waypoint[1])
    elif action == 'N':
        waypoint = (waypoint[0], waypoint[1] + value)
    elif action == 'S':
        waypoint = (waypoint[0], waypoint[1] - value)
    elif action == 'E':
        waypoint = (waypoint[0] + value, waypoint[1])
    elif action == 'W':
        waypoint = (waypoint[0] - value, waypoint[1])
    elif action in 'RL':  # rotate waypoint
        rotation = value
        if action == 'L':
            rotation = -rotation % 360
        if rotation == 90:
            waypoint = (waypoint[1], -waypoint[0])
        elif rotation == 180:
            waypoint = (-waypoint[0], -waypoint[1])
        elif rotation == 270:
            waypoint = (-waypoint[1], waypoint[0])
        else:
            raise ValueError("Unknown rotation", value)
    else:
        raise ValueError("Unknown Action", action)
   
    #print(f"{command=} {position=} {waypoint=}")
    return position, waypoint

route = [position]
for command in commands:
    position, waypoint = navigate(command, position, waypoint)
    route.append(position)
    
print(position, waypoint)
manhattan_distance = sum([abs(x) for x in position])
print(f"Day 12 part 2 answer is {manhattan_distance}")
(30806, -22060) (-81, 23)
Day 12 part 2 answer is 52866
In [ ]:
import matplotlib.pyplot as pp
pp.plot(*zip(*route))
pp.grid()
In [ ]:
# Day 12 Part 1 Turtle Version

# Don't need to track state here, because the turtle keeps track of its own state.

def navigate(command):
    action, value = command
    if action in 'NESW':
        saved_heading = turtle.heading()
        if action == 'N':
            turtle.setheading(90)
            turtle.forward(value)
        elif action == 'S':
            turtle.setheading(270)
            turtle.forward(value)
        elif action == 'E':
            turtle.setheading(0)
            turtle.forward(value)
        elif action == 'W':
            turtle.setheading(180)
            turtle.forward(value)
            
        turtle.setheading(saved_heading)        
        
    elif action == 'L':
            turtle.left(value)
    elif action == 'R':
            turtle.right(value)
    elif action == 'F':  # Move in current direction
        turtle.forward(value)
    else:
        raise ValueError("Unknown Action", action)
 
if False:  # Don't want to run this generally, it is very slow, won't work on the web etc.
    import turtle
    turtle.reset()
    turtle.speed("fastest")

    turtle.setworldcoordinates(-100,-1000,1500,1000)  # Depends on your input data

    for command in commands:
        navigate(command)

    print(turtle.pos())

    manhattan_distance = sum([abs(x) for x in turtle.pos()])
    manhattan_distance = round(manhattan_distance, 0)
    print(f"Day 12 part 1 answer is {manhattan_distance}")
    turtle.bye()

--- Day 13: Shuttle Search ---

Your ferry can make it safely to a nearby port, but it won't get much further. When you call to book another ship, you discover that no ships embark from that port to your vacation island. You'll need to get from the port to the nearest airport.

Fortunately, a shuttle bus service is available to bring you from the sea port to the airport! Each bus has an ID number that also indicates how often the bus leaves for the airport.

Bus schedules are defined based on a timestamp that measures the number of minutes since some fixed reference point in the past. At timestamp 0, every bus simultaneously departed from the sea port. After that, each bus travels to the airport, then various other locations, and finally returns to the sea port to repeat its journey forever.

The time this loop takes a particular bus is also its ID number: the bus with ID 5 departs from the sea port at timestamps 0, 5, 10, 15, and so on. The bus with ID 11 departs at 0, 11, 22, 33, and so on. If you are there when the bus departs, you can ride that bus to the airport!

Your notes (your puzzle input) consist of two lines. The first line is your estimate of the earliest timestamp you could depart on a bus. The second line lists the bus IDs that are in service according to the shuttle company; entries that show x must be out of service, so you decide to ignore them.

To save time once you arrive, your goal is to figure out the earliest bus you can take to the airport. (There will be exactly one such bus.)

For example, suppose you have the following notes:

939 7,13,x,x,59,x,31,19

Here, the earliest timestamp you could depart is 939, and the bus IDs in service are 7, 13, 59, 31, and 19. Near timestamp 939, these bus IDs depart at the times marked D:

time bus 7 bus 13 bus 59 bus 31 bus 19 929 . . . . . 930 . . . D . 931 D . . . D 932 . . . . . 933 . . . . . 934 . . . . . 935 . . . . . 936 . D . . . 937 . . . . . 938 D . . . . 939 . . . . . 940 . . . . . 941 . . . . . 942 . . . . . 943 . . . . . 944 . . D . . 945 D . . . . 946 . . . . . 947 . . . . . 948 . . . . . 949 . D . . .

The earliest bus you could take is bus ID 59. It doesn't depart until timestamp 944, so you would need to wait 944 - 939 = 5 minutes before it departs. Multiplying the bus ID by the number of minutes you'd need to wait gives 295.

What is the ID of the earliest bus you can take to the airport multiplied by the number of minutes you'll need to wait for that bus?

In [ ]:
l = read_and_clean(13)
mytime = int(l[0])
bus_list = l[1].split(',')
bus_ids = sorted([int(x) for x in bus_list if x != 'x'])

delays = []
for bus_id in bus_ids:
    delay = bus_id - mytime % bus_id 
    delays.append((delay, bus_id))
    
delays.sort()

print(delays)
print(f"Answer = {delays[0][0] * delays[0][1]=}")
Input ['1000066', '13,x,x,41,x,x,x,37,x,x,x,x,x,659,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,19,x,x,x,23,x,x,x,x,x,29,x,409,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,17'] ... ['1000066', '13,x,x,41,x,x,x,37,x,x,x,x,x,659,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,19,x,x,x,23,x,x,x,x,x,29,x,409,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,17']
[(6, 41), (7, 37), (10, 17), (11, 13), (18, 19), (20, 23), (28, 29), (296, 659), (348, 409)]
Answer = delays[0][0] * delays[0][1]=246

--- Part Two ---

The shuttle company is running a contest: one gold coin for anyone that can find the earliest timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs at that subsequent minute. (The first line in your input is no longer relevant.)

For example, suppose you have the same list of bus IDs as above:

7,13,x,x,59,x,31,19

An x in the schedule means there are no constraints on what bus IDs must depart at that time.

This means you are looking for the earliest timestamp (called t) such that:

Bus ID 7 departs at timestamp t.
Bus ID 13 departs one minute after timestamp t.
There are no requirements or restrictions on departures at two or three minutes after timestamp t.
Bus ID 59 departs four minutes after timestamp t.
There are no requirements or restrictions on departures at five minutes after timestamp t.
Bus ID 31 departs six minutes after timestamp t.
Bus ID 19 departs seven minutes after timestamp t.

The only bus departures that matter are the listed bus IDs at their specific offsets from t. Those bus IDs can depart at other times, and other bus IDs can depart at those times. For example, in the list above, because bus ID 19 must depart seven minutes after the timestamp at which bus ID 7 departs, bus ID 7 will always also be departing with bus ID 19 at seven minutes after timestamp t.

In this example, the earliest timestamp at which this occurs is 1068781:

time bus 7 bus 13 bus 59 bus 31 bus 19 1068773 . . . . . 1068774 D . . . . 1068775 . . . . . 1068776 . . . . . 1068777 . . . . . 1068778 . . . . . 1068779 . . . . . 1068780 . . . . . 1068781 D . . . . 1068782 . D . . . 1068783 . . . . . 1068784 . . . . . 1068785 . . D . . 1068786 . . . . . 1068787 . . . D . 1068788 D . . . D 1068789 . . . . . 1068790 . . . . . 1068791 . . . . . 1068792 . . . . . 1068793 . . . . . 1068794 . . . . . 1068795 D D . . . 1068796 . . . . . 1068797 . . . . .

In the above example, bus ID 7 departs at timestamp 1068788 (seven minutes after t). This is fine; the only requirement on that minute is that bus ID 19 departs then, and it does.

Here are some other examples:

The earliest timestamp that matches the list 17,x,13,19 is 3417.
67,7,59,61 first occurs at timestamp 754018.
67,x,7,59,61 first occurs at timestamp 779210.
67,7,x,59,61 first occurs at timestamp 1261476.
1789,37,47,1889 first occurs at timestamp 1202161486.

However, with so many bus IDs in your list, surely the actual earliest timestamp will be larger than 100000000000000!

What is the earliest timestamp such that all of the listed bus IDs depart at offsets matching their positions in the list?

In [ ]:
import functools
from math import sqrt


@functools.lru_cache(maxsize=128)
def factors(n):
    """prime factorization of n
    return tuple factors of n or
    return (n,) if n is prime
    """
    for factor in range(2, int(sqrt(n)) + 1):
        quotient, remainder = divmod(n, factor)
        if remainder == 0:  # i is smallest factor of n
            return (factor,) + factors(quotient)
    return (n,)  # prime


def is_prime(n):
    return len(factors(n)) < 2
In [ ]:
buses = []
busids = []
for i, bus in enumerate(bus_list):
    if bus != 'x':
        buses.append((i, int(bus)))
        busids.append(int(bus))
        

# are all bus_ids prime? Does this help?
print(f"{all([is_prime(busid) for _, busid in buses])=}")

maxn = reduce(mul, busids)   # cycle of all coprime multiples, answer is less than this... o.O
print(f"{maxn=}")

print(f"{buses=}")
for bus in buses:
    print(bus, (bus[0] - bus[1]) % 13)
all([is_prime(busid) for _, busid in buses])=True
maxn=1145159583560291
buses=[(0, 13), (3, 41), (7, 37), (13, 659), (32, 19), (36, 23), (42, 29), (44, 409), (61, 17)]
(0, 13) 0
(3, 41) 1
(7, 37) 9
(13, 659) 4
(32, 19) 0
(36, 23) 0
(42, 29) 0
(44, 409) 12
(61, 17) 5

Hmmm, searching everything will take way too long, but notice some interesting things about the specific numbers

(0, 13),   n + 0 =  k0 * 13   n + 13 = (k0 + 1) * 13  = k0' * 13
(3, 41),   n + 3 =  k3 * 41
(7, 37),   n + 7 =  k7 * 37
(13, 659), n + 13 = k13 * 659 n + 13 =                  k13 * 659
(32, 19),  n + 32 = k32 * 19  n + 13 = (k32 - 1) * 19 = k32' * 19
(36, 23),  n + 36 = k36 * 23  n + 13 = (k36 - 1) * 23 = k36' * 23
(42, 29),  n + 42 = k42 * 29  n + 13 = (k42 - 1) * 29 = k42' * 29
(44, 409), n + 44 = k44 * 409
(61, 17),  n + 61 = k61 * 17

Five of the requirements can be rearranged so that (n + 13) is a constant times a prime number. Therefore n+13 is k (product of those primes). I.e. `n + 13 = k (13 19 23 29 659)orn = k (13 19 23 29 659) - 13ork 108569591 - 13` Stepping through these reduces the search space considerably! about 10^7 max. Mostly checking just one of the remaining 4 constraints will fail.

In [ ]:
def search():

    n0 = 13 * 659 * 19 * 23 * 29
    #print(f"Step={n0}")
    #print(f"Max iterations = {(maxn - minn) // n0}")

    n13 = 0
    iterations = 0
    if True:
        while n13 < maxn:
            n13 += n0
            iterations += 1
            n = n13 - 13

            if (n + 44 ) % 409:
                continue
            if (n + 3) % 41:
                continue
            if (n + 7) % 37:
                continue
            if (n + 61) % 17:
                continue
            #print(f"Found {n}")

            # Following should be guaranteed by construction
            if n % 13:
                continue
            if (n + 13) % 659:
                continue
            if (n + 36) % 23:
                continue
            if (n + 32) % 19:
                continue
            if (n + 42) % 29:
                continue

            #print(f"Checked {n}")
            break
    return n
        
print("Answer =", search())

print(timeit.timeit(search, number=1), "seconds")
Answer = 939490236001473
1.5265711869997176 seconds
In [ ]:
"""Hmm.  Looking at other solutions, Chinese Remainder Theorem comes up... 
The Chinese remainder theorem states that a linear system of congruence equations with 
pairwise relatively prime moduli has a unique solution modulo the product of the moduli of the system.
"""
from itertools import count
from math import gcd

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

# https://github.com/LubosKolouch/AdventOfCode_2020/blob/main/day_13.py

def sieve(buses):
    time, interval = buses[0]  # start with period of bus at zero offset
    bs = sorted(buses[1:], key=lambda x: x[1], reverse=True)  # biggest first
    for minute, period in bs:
        #print(time, interval, minute, period)
        for time in count(time, interval):  # Search for first time when current bus...
            if (time + minute) % period == 0: # has correct time relationship to previous bus(es)
                break

        interval = lcm(interval, period)  # After this, they will have same relationship every lcm, so
                                  # only look at those intervals from now on

print('Day13 Part 2:')

def tf():
    sieve(buses)
    
print(timeit.timeit(tf, number=100) / 100, "seconds")
Day13 Part 2:
8.346804999746382e-05 seconds
In [ ]:
# Day 13 part 2 third (and fastest) method

def extended_gcd(aa, bb):
    """
    Calculate the gcd (greatest common divisor) of aa and bb, and bezout coefficients x, y
    
    Returns gcd, x, y such that x * aa + y * bb = gcd
    
    From https://www.rosettacode.org/wiki/Modular_inverse#Python
    """
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y

    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
 
def bezout_coeffs(a, m):
    g, x, y = extended_gcd(a, m)
    return x, y

#def modinv(a, m):
#    g, x, y = extended_gcd(a, m)
#    if g != 1:
#        raise ValueError
#    return x % m


def bezout_solution(eqns):
    """
    Solve the linear system of congruence equations 
    eqns = ((a, n), ...)  a is remainder, n is modulus
    
    Implementation of https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Using_the_existence_construction
    Algorithm derived from here https://www.omnicalculator.com/math/chinese-remainder
    """
    N = reduce(mul, [coeffs[1] for coeffs in eqns])
    x = 0
    for a, n in eqns:
        m = N // n  # m = product of all other moduli
        u, v = bezout_coeffs(n, m)
        e = v * m
        x += a * e

    return x % N
   
eqns = [(-b[0], b[1]) for b in buses]
print("Day 13 part 2", bezout_solution(eqns))

def tf():
    bezout_solution(eqns)

print(timeit.timeit(tf, number=100) / 100, "seconds")
Day 13 part 2 939490236001473
4.177138998784358e-05 seconds

--- Day 14: Docking Data ---

As your ferry approaches the sea port, the captain asks for your help again. The computer system that runs this port isn't compatible with the docking program on the ferry, so the docking parameters aren't being correctly initialized in the docking program's memory.

After a brief inspection, you discover that the sea port's computer system uses a strange bitmask system in its initialization program. Although you don't have the correct decoder chip handy, you can emulate it in software!

The initialization program (your puzzle input) can either update the bitmask or write a value to memory. Values and memory addresses are both 36-bit unsigned integers. For example, ignoring bitmasks for a moment, a line like mem[8] = 11 would write the value 11 to memory address 8.

The bitmask is always given as a string of 36 bits, written with the most significant bit (representing 2^35) on the left and the least significant bit (2^0, that is, the 1s bit) on the right. The current bitmask is applied to values immediately before they are written to memory: a 0 or 1 overwrites the corresponding bit in the value, while an X leaves the bit in the value unchanged.

For example, consider the following program:

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0

This program starts by specifying a bitmask (mask = ....). The mask it specifies will overwrite two bits in every written value: the 2s bit is overwritten with 0, and the 64s bit is overwritten with 1.

The program then attempts to write the value 11 to memory address 8. By expanding everything out to individual bits, the mask is applied as follows:

value:  000000000000000000000000000000001011  (decimal 11)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result: 000000000000000000000000000001001001  (decimal 73)

So, because of the mask, the value 73 is written to memory address 8 instead. Then, the program tries to write 101 to address 7:

value:  000000000000000000000000000001100101  (decimal 101)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result: 000000000000000000000000000001100101  (decimal 101)

This time, the mask has no effect, as the bits it overwrote were already the values the mask tried to set. Finally, the program tries to write 0 to address 8:

value:  000000000000000000000000000000000000  (decimal 0)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result: 000000000000000000000000000001000000  (decimal 64)

64 is written to address 8 instead, overwriting the value that was there previously.

To initialize your ferry's docking program, you need the sum of all values left in memory after the initialization program completes. (The entire 36-bit address space begins initialized to the value 0 at every address.) In the above example, only two values in memory are not zero - 101 (at address 7) and 64 (at address 8) - producing a sum of 165.

Execute the initialization program. What is the sum of all values left in memory after it completes?

In [ ]:
input14 = read_and_clean(14)
Input ['mask = 1X11X010X000X0X101X00100011X10100111', 'mem[40278] = 36774405'] ... ['mem[3121] = 139148', 'mem[53666] = 26824']
In [ ]:
ex14_1 = """mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0""".split('\n')

ans14_1 = 165

def read_mem(line):
    ll = line.split('=')
    addr = int(ll[0][4:-2])
    val = int(ll[1])
    return addr, val
    
def read_mask(line):
    l = line.split('=')[1].strip()
    zeros = l.replace('X', '1')
    zeromask = int(zeros, 2)
    ones = l.replace('X', '0')
    onemask = int(ones, 2)
    
    return zeromask, onemask, l


def day14_part1(data):
    mem = {}
    zm = ~0
    om = 0

    for line in data:
        if line.startswith('mem'):
            addr, val = read_mem(line)
            v1 = val & zm
            v2 = v1 | om
            #print(f"{addr}\nv{val:>36b} {val}\nw{v1:>36b} {v1}\nx{v2:b} {v2}")
            mem[addr] = v2
        elif line.startswith('mask'):
            zm, om, _ = read_mask(line)
            #print(f"z{zm:b}\no{om:b}")
        else:
            print("BAD",line)

    return sum(mem.values())

print(f"{day14_part1(ex14_1) = } should be {ans14_1}")
day14_part1(input14)
day14_part1(ex14_1) = 165 should be 165
Out[ ]:
16003257187056

--- Part Two ---

For some reason, the sea port's computer system still can't communicate with your ferry's docking program. It must be using version 2 of the decoder chip!

A version 2 decoder chip doesn't modify the values being written at all. Instead, it acts as a memory address decoder. Immediately before a value is written to memory, each bit in the bitmask modifies the corresponding bit of the destination memory address in the following way:

If the bitmask bit is 0, the corresponding memory address bit is unchanged.
If the bitmask bit is 1, the corresponding memory address bit is overwritten with 1.
If the bitmask bit is X, the corresponding memory address bit is floating.

A floating bit is not connected to anything and instead fluctuates unpredictably. In practice, this means the floating bits will take on all possible values, potentially causing many memory addresses to be written all at once!

For example, consider the following program:

mask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1

When this program goes to write to memory address 42, it first applies the bitmask:

address: 000000000000000000000000000000101010  (decimal 42)
mask:    000000000000000000000000000000X1001X
result:  000000000000000000000000000000X1101X

After applying the mask, four bits are overwritten, three of which are different, and two of which are floating. Floating bits take on every possible combination of values; with two floating bits, four actual memory addresses are written:

000000000000000000000000000000011010  (decimal 26)
000000000000000000000000000000011011  (decimal 27)
000000000000000000000000000000111010  (decimal 58)
000000000000000000000000000000111011  (decimal 59)

Next, the program is about to write to memory address 26 with a different bitmask:

address: 000000000000000000000000000000011010  (decimal 26)
mask:    00000000000000000000000000000000X0XX
result:  00000000000000000000000000000001X0XX

This results in an address with three floating bits, causing writes to eight memory addresses:

000000000000000000000000000000010000  (decimal 16)
000000000000000000000000000000010001  (decimal 17)
000000000000000000000000000000010010  (decimal 18)
000000000000000000000000000000010011  (decimal 19)
000000000000000000000000000000011000  (decimal 24)
000000000000000000000000000000011001  (decimal 25)
000000000000000000000000000000011010  (decimal 26)
000000000000000000000000000000011011  (decimal 27)

The entire 36-bit address space still begins initialized to the value 0 at every address, and you still need the sum of all values left in memory at the end of the program. In this example, the sum is 208.

Execute the initialization program using an emulator for a version 2 decoder chip. What is the sum of all values left in memory after it completes?

In [ ]:
# How many memory locations may be modified? about 16K = not outrageous
sum([2**l.count('X') for l in input14 if l.startswith('ma')])
Out[ ]:
16512
In [ ]:
 
In [ ]:
ex14_2 = """mask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1""".split('\n')

ans14_2 = 208

dbgprint = noprint

def flaky_mem_store(mem, addr, val, ex):
    # ex looks like "000000000000000000000000000000X0000X"
    xofs = []  # offsets of X from right i.e. bit positions
    for i,c in enumerate(ex):
        if c == 'X':
            xofs.append(len(ex) - 1 - i)
    xofs.sort()  # looks like [0, 5]
    
    for i in range(2 ** len(xofs)):  # 2^N permutations of bits. e.g. 0,1,2,3
        maddr = addr  # Modified address
        for bi in range(len(xofs)):  # bit index. e.g. 0,1
            offset = xofs[bi]     # e.g. 0, 5
            mask = (1 << offset)  # Bit at offset 
            if i & (1 << bi):
                maddr = maddr | mask  
            else:
                maddr = maddr & ~mask
        
        mem[maddr] = val   


def day14_part2(data):
    mem = {}
    om = ~0
    ex = '0' * 36
    for line in data:
        if line.startswith('mem'):
            addr, val = read_mem(line)
            addr |= om  # ones mask set bits
            flaky_mem_store(mem, addr, val, ex)
        elif line.startswith('mask'):
            _, om, ex = read_mask(line)
        else:
            print("BAD",line)
            
    return sum(mem.values())

print(f"{day14_part2(ex14_2) = } should equal {ans14_2}")
print(f"{day14_part2(input14) = } should equal 3219837697833")
day14_part2(ex14_2) = 208 should equal 208
day14_part2(input14) = 3219837697833 should equal 3219837697833

Day 15 --- Day 15: Rambunctious Recitation ---

You catch the airport shuttle and try to book a new flight to your vacation island. Due to the storm, all direct flights have been cancelled, but a route is available to get around the storm. You take it.

While you wait for your flight, you decide to check in with the Elves back at the North Pole. They're playing a memory game and are ever so excited to explain the rules!

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.

So, after the starting numbers, each turn results in that player speaking aloud either 0 (if the last number is new) or an age (if the last number is a repeat).

For example, suppose the starting numbers are 0,3,6:

Turn 1: The 1st number spoken is a starting number, 0.
Turn 2: The 2nd number spoken is a starting number, 3.
Turn 3: The 3rd number spoken is a starting number, 6.
Turn 4: Now, consider the last number spoken, 6. Since that was the first time the number had been spoken, the 4th number spoken is 0.
Turn 5: Next, again consider the last number spoken, 0. Since it had been spoken before, the next number to speak is the difference between the turn number when it was last spoken (the previous turn, 4) and the turn number of the time it was most recently spoken before then (turn 1). Thus, the 5th number spoken is 4 - 1, 3.
Turn 6: The last number spoken, 3 had also been spoken before, most recently on turns 5 and 2. So, the 6th number spoken is 5 - 2, 3.
Turn 7: Since 3 was just spoken twice in a row, and the last two turns are 1 turn apart, the 7th number spoken is 1.
Turn 8: Since 1 is new, the 8th number spoken is 0.
Turn 9: 0 was last spoken on turns 8 and 4, so the 9th number spoken is the difference between them, 4.
Turn 10: 4 is new, so the 10th number spoken is 0.

(The game ends when the Elves get sick of playing or dinner is ready, whichever comes first.)

Their question for you is: what will be the 2020th number spoken? In the example above, the 2020th number spoken will be 436.

Here are a few more examples:

Given the starting numbers 1,3,2, the 2020th number spoken is 1.
Given the starting numbers 2,1,3, the 2020th number spoken is 10.
Given the starting numbers 1,2,3, the 2020th number spoken is 27.
Given the starting numbers 2,3,1, the 2020th number spoken is 78.
Given the starting numbers 3,2,1, the 2020th number spoken is 438.
Given the starting numbers 3,1,2, the 2020th number spoken is 1836.

Given your starting numbers, what will be the 2020th number spoken?

--- Part Two ---

Impressed, the Elves issue you a challenge: determine the 30000000th number spoken. For example, given the same starting numbers as above:

Given 0,3,6, the 30000000th number spoken is 175594.
Given 1,3,2, the 30000000th number spoken is 2578.
Given 2,1,3, the 30000000th number spoken is 3544142.
Given 1,2,3, the 30000000th number spoken is 261214.
Given 2,3,1, the 30000000th number spoken is 6895259.
Given 3,2,1, the 30000000th number spoken is 18.
Given 3,1,2, the 30000000th number spoken is 362.

Given your starting numbers, what will be the 30000000th number spoken?

In [ ]:
data15 = [13,16,0,12,15,1]
#data15 = [0, 3, 6]
#data15 = [3, 1, 2]

last = data15[-1]  # Keep final number out, need to know if it is new or not
data = data15[:-1]

pos = len(data)

print(pos,data, last)

d = {}
for i, n in enumerate(data):
    d[n] = i
    
targets = (2020, 30000000)
target = targets[-1]
while pos < target + 2:
    if pos + 1 in targets:  # counting from 1, while pos counts from zero
        print(f"{pos+1=},{last=}")
    if not last in d:
        d[last] = pos
        last = 0
    else:
        new = pos - d[last]
        d[last] = pos
        last = new

    pos += 1
5 [13, 16, 0, 12, 15] 1
pos+1=2020,last=319
pos+1=30000000,last=2424

--- Day 16: Ticket Translation ---

As you're walking to yet another connecting flight, you realize that one of the legs of your re-routed trip coming up is on a high-speed train. However, the train ticket you were given is in a language you don't understand. You should probably figure out what it says before you get to the train station after the next flight.

Unfortunately, you can't actually read the words on the ticket. You can, however, read the numbers, and so you figure out the fields these tickets must have and the valid ranges for values in those fields.

You collect the rules for ticket fields, the numbers on your ticket, and the numbers on other nearby tickets for the same train service (via the airport security cameras) together into a single document you can reference (your puzzle input).

The rules for ticket fields specify a list of fields that exist somewhere on the ticket and the valid ranges of values for each field. For example, a rule like class: 1-3 or 5-7 means that one of the fields in every ticket is named class and can be any value in the ranges 1-3 or 5-7 (inclusive, such that 3 and 5 are both valid in this field, but 4 is not).

Each ticket is represented by a single line of comma-separated values. The values are the numbers on the ticket in the order they appear; every ticket has the same format. For example, consider this ticket:

.--------------------------------------------------------. | ????: 101 ?????: 102 ??????????: 103 ???: 104 | | | | ??: 301 ??: 302 ???????: 303 ??????? | | ??: 401 ??: 402 ???? ????: 403 ????????? | '--------------------------------------------------------'

Here, ? represents text in a language you don't understand. This ticket might be represented as 101,102,103,104,301,302,303,401,402,403; of course, the actual train tickets you're looking at are much more complicated. In any case, you've extracted just the numbers in such a way that the first number is always the same specific field, the second number is always a different specific field, and so on - you just don't know what each position actually means!

Start by determining which tickets are completely invalid; these are tickets that contain values which aren't valid for any field. Ignore your ticket for now.

For example, suppose you have the following notes:

class: 1-3 or 5-7 row: 6-11 or 33-44 seat: 13-40 or 45-50

your ticket: 7,1,14

nearby tickets: 7,3,47 40,4,50 55,2,20 38,6,12

It doesn't matter which position corresponds to which field; you can identify invalid nearby tickets by considering only whether tickets contain values that are not valid for any field. In this example, the values on the first nearby ticket are all valid for at least one field. This is not true of the other three nearby tickets: the values 4, 55, and 12 are are not valid for any field. Adding together all of the invalid values produces your ticket scanning error rate: 4 + 55 + 12 = 71.

Consider the validity of the nearby tickets you scanned. What is your ticket scanning error rate?

--- Part Two ---

Now that you've identified which tickets contain invalid values, discard those tickets entirely. Use the remaining valid tickets to determine which field is which.

Using the valid ranges for each field, determine what order the fields appear on the tickets. The order is consistent between all tickets: if seat is the third field, it is the third field on every ticket, including your ticket.

For example, suppose you have the following notes:

class: 0-1 or 4-19 row: 0-5 or 8-19 seat: 0-13 or 16-19

your ticket: 11,12,13

nearby tickets: 3,9,18 15,1,5 5,14,9

Based on the nearby tickets in the above example, the first position must be row, the second position must be class, and the third position must be seat; you can conclude that in your ticket, class is 12, row is 11, and seat is 13.

Once you work out which field is which, look for the six fields on your ticket that start with the word departure. What do you get if you multiply those six values together?

In [ ]:
data16 = read_and_clean(16)
trules = data16[:20]
tmy_ticket = data16[22]
ttickets = data16[25:]
Input ['departure location: 27-840 or 860-957', 'departure station: 28-176 or 183-949'] ... ['873,831,550,312,418,126,147,293,374,243,574,225,876,552,318,359,306,229,763,210', '196,494,73,806,648,121,839,449,187,554,424,928,250,797,227,189,127,125,173,424']
In [ ]:
def parse_rule(rule):
    name, rest = rule.split(':')
    ranges = rest.split(' or ')
    ranges = [r.split('-') for r in ranges]
    ranges = [(int(x), int(y)) for x, y in ranges]
    return name, ranges

rules = [parse_rule(r) for r in trules]

def parse_ticket(t):
    return [int(n) for n in t.split(',')]
            
tickets = [parse_ticket(t) for t in ttickets]
my_ticket = parse_ticket(tmy_ticket)

def range_ok(rr, n):
    ok = False
    for r in rr:
        #print(n,range)
        if r[0] <= n  and n <= r[1]:
            ok = True
            break

    return ok


def find_invalid(rules, ticket):
    bad = []
    for n in ticket:
        ok = False
        for rn, rr in rules:
            if range_ok(rr, n):
                ok = True
                break
            
        if not ok:
            bad.append(n)
            
    return bad
 
bad = []
good_tickets = []
for ticket in tickets:
    #rint(ticket)
    br = find_invalid(rules, ticket)
    if br:
        bad.extend(br)
    else:
        good_tickets.append(ticket)
    
print(f"Part 1 {sum(bad)=}")

len(tickets), len(good_tickets)
Part 1 sum(bad)=19070
Out[ ]:
(235, 190)
In [ ]:
rules[15]
Out[ ]:
('seat', [(39, 328), (351, 970)])
In [ ]:
def locate_invalid(rule, ticket):
    """return list of all positions in ticket that violate rule"""
    bad = []
    for i, n in enumerate(ticket):
        ok = range_ok(rule[1], n)
        if not ok:
            #print(i, n, range, 'bad', rule)
            bad.append(i)
        #    break
            
    return bad


exclusions = []  # One entry per rule
for rule in rules:
    bads = set()  # Set of indices where at least one ticket violates the rule
    for i, ticket in enumerate(good_tickets):
        bad = locate_invalid(rule, ticket)
        bads = bads | set(bad)

    exclusions.append((rule, bads))  # Group rule and its field exclusions

exclusions.sort(key = lambda x: len(x[1]))
In [ ]:
field_offsets = []
allpos = set(range(20))
for j in range(20):
    for i, ((rulename, _), rule_excl) in enumerate(exclusions):
        okset = allpos ^ rule_excl
        if len(okset) == 1:  # Found a rule where only one index is OK
            okidx = list(okset)[0]
            field_offsets.append((okidx, rulename))
            for e in exclusions:
                e[1].add(okidx)  # Exclude the found index from all rules
            break

field_offsets.sort()
field_offsets
Out[ ]:
[(0, 'zone'),
 (1, 'departure location'),
 (2, 'departure track'),
 (3, 'row'),
 (4, 'duration'),
 (5, 'price'),
 (6, 'departure station'),
 (7, 'arrival platform'),
 (8, 'train'),
 (9, 'wagon'),
 (10, 'route'),
 (11, 'arrival station'),
 (12, 'class'),
 (13, 'arrival track'),
 (14, 'type'),
 (15, 'arrival location'),
 (16, 'departure date'),
 (17, 'departure time'),
 (18, 'seat'),
 (19, 'departure platform')]
In [ ]:
prod = 1

for value, name in field_offsets:
    if name.startswith('departure'):
        prod *= my_ticket[value]
        print(name, value, my_ticket[value], prod)
        
prod
departure location 1 53 53
departure track 2 73 3869
departure station 6 97 375293
departure date 16 103 38655179
departure time 17 59 2280655561
departure platform 19 71 161926544831
Out[ ]:
161926544831

--- Day 17: Conway Cubes ---

As your flight slowly drifts through the sky, the Elves at the Mythical Information Bureau at the North Pole contact you. They'd like some help debugging a malfunctioning experimental energy source aboard one of their super-secret imaging satellites.

The experimental energy source is based on cutting-edge technology: a set of Conway Cubes contained in a pocket dimension! When you hear it's having problems, you can't help but agree to take a look.

The pocket dimension contains an infinite 3-dimensional grid. At every integer 3-dimensional coordinate (x,y,z), there exists a single cube which is either active or inactive.

In the initial state of the pocket dimension, almost all cubes start inactive. The only exception to this is a small flat region of cubes (your puzzle input); the cubes in this region start in the specified active (#) or inactive (.) state.

The energy source then proceeds to boot up by executing six cycles.

Each cube only ever considers its neighbors: any of the 26 other cubes where any of their coordinates differ by at most 1. For example, given the cube at x=1,y=2,z=3, its neighbors include the cube at x=2,y=2,z=2, the cube at x=0,y=2,z=3, and so on.

During a cycle, all cubes simultaneously change their state according to the following rules:

If a cube is active and exactly 2 or 3 of its neighbors are also active, the cube remains active. Otherwise, the cube becomes inactive.
If a cube is inactive but exactly 3 of its neighbors are active, the cube becomes active. Otherwise, the cube remains inactive.

The engineers responsible for this experimental energy source would like you to simulate the pocket dimension and determine what the configuration of cubes should be at the end of the six-cycle boot process.

For example, consider the following initial state:

.#.
..#
###

Even though the pocket dimension is 3-dimensional, this initial state represents a small 2-dimensional slice of it. (In particular, this initial state defines a 3x3x1 region of the 3-dimensional space.)

Simulating a few cycles from this initial state produces the following configurations, where the result of each cycle is shown layer-by-layer at each given z coordinate (and the frame of view follows the active cells in each cycle):

Before any cycles:

z=0
.#.
..#
###


After 1 cycle:

z=-1
#..
..#
.#.

z=0
#.#
.##
.#.

z=1
#..
..#
.#.


After 2 cycles:

z=-2
.....
.....
..#..
.....
.....

z=-1
..#..
.#..#
....#
.#...
.....

z=0
##...
##...
#....
....#
.###.

z=1
..#..
.#..#
....#
.#...
.....

z=2
.....
.....
..#..
.....
.....


After 3 cycles:

z=-2
.......
.......
..##...
..###..
.......
.......
.......

z=-1
..#....
...#...
#......
.....##
.#...#.
..#.#..
...#...

z=0
...#...
.......
#......
.......
.....##
.##.#..
...#...

z=1
..#....
...#...
#......
.....##
.#...#.
..#.#..
...#...

z=2
.......
.......
..##...
..###..
.......
.......
.......

After the full six-cycle boot process completes, 112 cubes are left in the active state.

Starting with your given initial configuration, simulate six cycles. How many cubes are left in the active state after the sixth cycle?

In [ ]:
data17 = read_and_clean(17)
Input ['#####...', '.#..##..'] ... ['.#.#.###', '#.#.#..#']
In [ ]:
from copy import deepcopy

# in 6 cycles data can expand 6 steps in all directions.
cycles = 6

def layer_to_matrix(ll):
    return [list(l) for l in ll]

def make_world(data, cycles=6):
    pad_lr = '.' * cycles
    pad_tb = pad_lr + '.' * len(data[0]) + pad_lr

    empty_layer = []
    empty_line = pad_tb
    for i in range(2 * cycles + len(data17)):
        empty_layer.append(empty_line)

    pad17 = [pad_lr + l + pad_lr for l in data]
    layer17 = [pad_tb] * cycles + pad17 + [pad_tb] * cycles



    world = []
    for i in range(cycles):
        world.append(layer_to_matrix(empty_layer))
    world.append(layer_to_matrix(layer17))
    for i in range(cycles):
        world.append(layer_to_matrix(empty_layer))
        
    return world
          

def print_layer(m):
    for r in m:
        for c in r:
            print(c, end='')
        print()
   

def print_world(world):
    for i, m in enumerate(world):
        print(f"Layer {i}")
        print_layer(m)
   

def count_active(world):
    """Recursive version will count any dimensional world"""
    active = 0
    for z in world:
        if type(z) == str:
            if z == '#':
                active += 1
        else:
            active += count_active(z)
    return active


def count_neighbours(world, z,y,x):
    neighbours = 0
    for zz in range(z-1, z+2):
        if zz < 0:
            continue
        for yy in range(y-1, y+2):
            if yy < 0: 
                continue
            for xx in range(x-1, x+2):
                if xx < 0:
                    continue
                try:
                    if world[zz][yy][xx] == '#':
                        neighbours += 1 
                except IndexError:
                    pass
                
    if world[z][y][x] == '#':  # don't count self
        neighbours -= 1 
                
    return neighbours


def evolve(world, z,y,x):
    neighbours = count_neighbours(world, z,y,x)
    current = world[z][y][x]
    if current == '#':
        if neighbours < 2 or neighbours > 3:
            current = '.'
    else:
        if neighbours == 3:
            current = '#'
            
    return current


def update_world(world):
    new_world = deepcopy(world)
    for z in range(len(world)):
        for y in range(len(world[0])):
            for x in range(len(world[0][0])):
                #print(x,y,z)
                new_world[z][y][x] = evolve(world, z,y,x)
    return new_world      


world = make_world(data17, cycles)

for i in range(6):
    world = update_world(world)

count_active(world)
Out[ ]:
313
In [ ]:
# Part 2: 4D version.  
# It would be nice to generalise this to N dimensions, but can I be bothered?

size = 22
dimensions = 4

def empty_world(size, dimensions):
    """Initialise an N-dimension hypercube with edges of length size
    """
    world = []
    if dimensions > 1:
        for i in range(size):
            world.append(empty_world(size, dimensions - 1))
    else:
        for i in range(size):
            world.append('.')                      
    
    return world

def world_dimensions(world):
    if type(world[0]) != list:
        return (len(world), )
    else:
        return (len(world),) + world_dimensions(world[0])
        

def init_world(world, start):
    ys = len(start)
    yofs = (len(world) - ys) // 2
    xs = len(start[0])
    xofs = (len(world) - xs) // 2
    for y in range(ys):
        for x in range(xs):
            world[size // 2][size // 2][y + yofs][x + xofs] = start[y][x]
            
    return world

def init_world2(world, start):
    wd = world_dimensions(world)
    sd = world_dimensions(start)
    
    slice = world
    for i in range(len(wd) - len(sd)):
        slice = slice[wd[i] // 2]
    
    ys = len(start)
    yofs = (len(world) - ys) // 2
    xs = len(start[0])
    xofs = (len(world) - xs) // 2
    for y in range(ys):
        for x in range(xs):
            world[size // 2][size // 2][y + yofs][x + xofs] = start[y][x]
            
    return world

    
def count_neighbours(world, w, z, y, x):
    neighbours = 0
    for ww in range(w-1, w+2):
        if ww < 0:
            continue
        for zz in range(z-1, z+2):
            if zz < 0:
                continue
            for yy in range(y-1, y+2):
                if yy < 0: 
                    continue
                for xx in range(x-1, x+2):
                    if xx < 0:
                        continue
                    try:
                        if world[ww][zz][yy][xx] == '#':
                            neighbours += 1 
                    except IndexError:
                        pass
                
    if world[w][z][y][x] == '#':  # don't count self
        neighbours -= 1 
                
    return neighbours


def evolve(world, w, z,y,x):
    neighbours = count_neighbours(world, w, z,y,x)
    current = world[w][z][y][x]
    if current == '#':
        if neighbours < 2 or neighbours > 3:
            current = '.'
    else:
        if neighbours == 3:
            current = '#'
            
    return current


def update_world(world):
    new_world = deepcopy(world)
    for w in range(len(world)):
        for z in range(len(world[0])):
            for y in range(len(world[0][0])):
                for x in range(len(world[0][0][0])):
                    new_world[w][z][y][x] = evolve(world, w, z,y,x)
    return new_world      


start = layer_to_matrix(data17)
world = empty_world(size, dimensions)
world = init_world(world, start)

print(world_dimensions(start))

for i in range(6):
    world = update_world(world)

count_active(world)
(8, 8)
Out[ ]:
2640

--- Day 18: Operation Order ---

As you look out the window and notice a heavily-forested continent slowly appear over the horizon, you are interrupted by the child sitting next to you. They're curious if you could help them with their math homework.

Unfortunately, it seems like this "math" follows different rules than you remember.

The homework (your puzzle input) consists of a series of expressions that consist of addition (+), multiplication (*), and parentheses ((...)). Just like normal math, parentheses indicate that the expression inside must be evaluated before it can be used by the surrounding expression. Addition still finds the sum of the numbers on both sides of the operator, and multiplication still finds the product.

However, the rules of operator precedence have changed. Rather than evaluating multiplication before addition, the operators have the same precedence, and are evaluated left-to-right regardless of the order in which they appear.

For example, the steps to evaluate the expression 1 + 2 3 + 4 5 + 6 are as follows:

1 + 2 3 + 4 5 + 6 3 3 + 4 5 + 6 9 + 4 5 + 6 13 5 + 6 65 + 6 71

Parentheses can override this order; for example, here is what happens if parentheses are added to form 1 + (2 3) + (4 (5 + 6)):

1 + (2 3) + (4 (5 + 6)) 1 + 6 + (4 (5 + 6)) 7 + (4 (5 + 6)) 7 + (4 * 11 ) 7 + 44 51

Here are a few more examples:

2 * 3 + (4 * 5) becomes 26.
5 + (8 * 3 + 9 + 3 * 4 * 3) becomes 437.
5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4)) becomes 12240.
((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2 becomes 13632.

Before you can help with the homework, you need to understand it yourself. Evaluate the expression on each line of the homework; what is the sum of the resulting values?

In [ ]:
    data18 = read_and_clean(18)
Input ['4 * 5 + 7 * 2 + 8', '((3 * 6 + 2) * 7 + (5 * 4 + 6 + 8)) + 2 * 7 * 5'] ... ['8 * (9 * 7 * 5 + (9 + 8 * 4)) * 9 + (9 * 9 * (3 * 8 + 4) * 9)', '(7 + 4 + 6 * (5 * 3)) * 5 * 8']
In [ ]:
(1 + (2 * (3 + (4 * (5 + (6))))))
((((((1) + 2) * 3) + 4) * 5) + 6)

e1 = '1 + 2 * 3 + 4 * 5 + 6'
e2 = '1 + (2 * 3) + (4 * (5 + 6))'

e = '((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2'

def tokenise(expression):
    s = expression.replace('(', '( ').replace(')', ' )')
    ts = s.split()

    tokens = []
    for t in ts:
        try:
            tv = int(t)
        except:
            tv = t
        tokens.append(tv)
        
    return tokens


def evaluate(tokens, recurse = 0):
    op = None
    value = None
    i = 0
    while True:
        if i >= len(tokens):
            return value
        token = tokens[i]

        if token == '(':
            token,  j = evaluate(tokens[i+1:], recurse + 1)
            i += j + 1
        if token == ')':
            return value, i
        
        if token == '*' or token == '+':
            op = token
        else:  # evaluate operators in order seen
            if op == '*':
                value = value * token
                op = None
            elif op == '+':
                value = value + token
                op = None
            else:
                value = int(token)
        #print(recurse * '>', i, token, value)
        i += 1
    
    return value, i

def calculate(expression):
    return evaluate(tokenise(expression))

nums = [calculate(s) for s in data18]
            
sum(nums)       
Out[ ]:
209335026987

--- Part Two ---

You manage to answer the child's questions and they finish part 1 of their homework, but get stuck when they reach the next section: advanced math.

Now, addition and multiplication have different precedence levels, but they're not the ones you're familiar with. Instead, addition is evaluated before multiplication.

For example, the steps to evaluate the expression 1 + 2 3 + 4 5 + 6 are now as follows:

1 + 2 3 + 4 5 + 6 3 3 + 4 5 + 6 3 7 5 + 6 3 7 11 21 * 11 231

Here are the other examples from above:

1 + (2 * 3) + (4 * (5 + 6)) still becomes 51.
2 * 3 + (4 * 5) becomes 46.
5 + (8 * 3 + 9 + 3 * 4 * 3) becomes 1445.
5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4)) becomes 669060.
((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2 becomes 23340.
In [ ]:
examples = [
    ("10", 10),
    ("1 + (2 * 3) + (4 * (5 + 6))", 51),
    ("2 * 3 + (4 * 5)", 46),
    (" 5 + (8 * 3 + 9 + 3 * 4 * 3)", 1445),
    ("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))", 669060),
    ("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2", 23340),
]
In [ ]:
from pyparsing import *
from operator import add, sub, mul, truediv

ParserElement.enablePackrat()
#sys.setrecursionlimit(3000)

integer = pyparsing_common.integer
variable = Word(alphas, exact=1)
operand = integer | variable

expop = Literal("^")
signop = oneOf("+ -")
multop = oneOf("* /")
plusop = oneOf("+ -")
factop = Literal("!")

# To use the infixNotation helper:
#   1.  Define the "atom" operand term of the grammar.
#       For this simple grammar, the smallest operand is either
#       and integer or a variable.  This will be the first argument
#       to the infixNotation method.
#   2.  Define a list of tuples for each level of operator
#       precendence.  Each tuple is of the form
#       (opExpr, numTerms, rightLeftAssoc, parseAction), where
#       - opExpr is the pyparsing expression for the operator;
#          may also be a string, which will be converted to a Literal
#       - numTerms is the number of terms for this operator (must
#          be 1 or 2)
#       - rightLeftAssoc is the indicator whether the operator is
#          right or left associative, using the pyparsing-defined
#          constants opAssoc.RIGHT and opAssoc.LEFT.
#       - parseAction is the parse action to be associated with
#          expressions matching this operator expression (the
#          parse action tuple member may be omitted)
#   3.  Call infixNotation passing the operand expression and
#       the operator precedence list, and save the returned value
#       as the generated pyparsing expression.  You can then use
#       this expression to parse input strings, or incorporate it
#       into a larger, more complex grammar.
#
expr = infixNotation(
    operand,
    [
        ("!", 1, opAssoc.LEFT),
        ("^", 2, opAssoc.RIGHT),
        (signop, 1, opAssoc.RIGHT),
        (plusop, 2, opAssoc.LEFT),
        (multop, 2, opAssoc.LEFT),
    ],
)

   
ops = {
    '*' : mul,
    '+' : add
}
    
def eval_parsed(pe):
    for se in pe:
        print(se)


def eval_parsed(parse_tree):
    op = None
    value = None
    for element in parse_tree:    
        if isinstance(element, list):
            element = eval_parsed(element)
        
        if isinstance(element, str):
            op = element
        elif op:
            value = ops[op](value, element) 
            op = None
        else:
            value = element

    return value
 
    
if False:
    for eqn, ans in examples:
        parsed = expr.parseString(eqn)
        pl = parsed.asList()
        result = eval_parsed(pl)
        print(result, ans, result==ans)

if True:
    results = []
    for e in data18:
        results.append(eval_parsed(expr.parseString(e).asList()))

    print("Day 18 Part 2", sum(results))
Day 18 Part 2 33331817392479

--- Day 19: Monster Messages ---

You land in an airport surrounded by dense forest. As you walk to your high-speed train, the Elves at the Mythical Information Bureau contact you again. They think their satellite has collected an image of a sea monster! Unfortunately, the connection to the satellite is having problems, and many of the messages sent back from the satellite have been corrupted.

They sent you a list of the rules valid messages should obey and a list of received messages they've collected so far (your puzzle input).

The rules for valid messages (the top part of your puzzle input) are numbered and build upon each other. For example:

0: 1 2 1: "a" 2: 1 3 | 3 1 3: "b"

Some rules, like 3: "b", simply match a single character (in this case, b).

The remaining rules list the sub-rules that must be followed; for example, the rule 0: 1 2 means that to match rule 0, the text being checked must match rule 1, and the text after the part that matched rule 1 must then match rule 2.

Some of the rules have multiple lists of sub-rules separated by a pipe (|). This means that at least one list of sub-rules must match. (The ones that match might be different each time the rule is encountered.) For example, the rule 2: 1 3 | 3 1 means that to match rule 2, the text being checked must match rule 1 followed by rule 3 or it must match rule 3 followed by rule 1.

Fortunately, there are no loops in the rules, so the list of possible matches will be finite. Since rule 1 matches a and rule 3 matches b, rule 2 matches either ab or ba. Therefore, rule 0 matches aab or aba.

Here's a more interesting example:

0: 4 1 5 1: 2 3 | 3 2 2: 4 4 | 5 5 3: 4 5 | 5 4 4: "a" 5: "b"

Here, because rule 4 matches a and rule 5 matches b, rule 2 matches two letters that are the same (aa or bb), and rule 3 matches two letters that are different (ab or ba).

Since rule 1 matches rules 2 and 3 once each in either order, it must match two pairs of letters, one pair with matching letters and one pair with different letters. This leaves eight possibilities: aaab, aaba, bbab, bbba, abaa, abbb, baaa, or babb.

Rule 0, therefore, matches a (rule 4), then any of the eight options from rule 1, then b (rule 5): aaaabb, aaabab, abbabb, abbbab, aabaab, aabbbb, abaaab, or ababbb.

The received messages (the bottom part of your puzzle input) need to be checked against the rules so you can determine which are valid and which are corrupted. Including the rules and the messages together, this might look like:

0: 4 1 5 1: 2 3 | 3 2 2: 4 4 | 5 5 3: 4 5 | 5 4 4: "a" 5: "b"

ababbb bababa abbbab aaabbb aaaabbb

Your goal is to determine the number of messages that completely match rule 0. In the above example, ababbb and abbbab match, but bababa, aaabbb, and aaaabbb do not, producing the answer 2. The whole message must match all of rule 0; there can't be extra unmatched characters in the message. (For example, aaaabbb might appear to match rule 0 above, but it has an extra unmatched b on the end.)

How many messages completely match rule 0?

In [ ]:
data19 = read_and_clean(19)
Input ['25: 6 54 | 28 122', '52: 27 54 | 25 122'] ... ['bbbaabaaababaaaabbaabbaaaabbbabaabababaa', 'bababbaababbababaabbabaa']
In [ ]:
from collections import UserList

class alternative(UserList):
    """List of alternatives, str is regular expression to match
    """
    def __str__(self):
        s = '(?:' + str(self[0])
        for item in self[1:]:
            s += '|' + str(item)
        return s + ')'
    
    def __repr__(self):
        return "any([" + ','.join([repr(s) for s in self]) + "])"
    
    def absorb(self, idx):
        self.extend(self[idx])
        del self[idx]


class sequence(UserList):

    def __str__(self):
        return ''.join([str(s) for s in self])
    
    def __repr__(self):
        return "all([" + ','.join([repr(s) for s in self]) + "])"
    
    
class oneormore(UserList):
    def __str__(self):
        return '(?:' + ''.join([str(s) for s in self]) + ')+'
    
    def __repr__(self):
        return "some([" + ','.join([repr(s) for s in self]) + "])"
    

a = alternative((1,2))
b = alternative((a, "ba"))
b.absorb(0)
c = sequence((a,'aa', b))
d = oneormore((c))
print(d)
d
(?:(?:1|2)aa(?:ba|1|2))+
Out[ ]:
some([any([1,2]),'aa',any(['ba',1,2])])
In [ ]:
def unpack_rule(r):
    idx, s = r
    if s.startswith('"'):
        return [idx, s.strip('"')]
    
    ls = s.split('|')       
    lt = [sequence([int(x) for x in opt.strip().split()]) for opt in ls]
    if len(lt) > 1:
        res = alternative()
        for opt in lt:
            res.append(opt)
      
        return [idx, res]
    else:
        return [idx, lt[0]]


def parse19(data):
    rules = []
    messages = []
    for l in data:
        fields = l.split(':')
        if len(fields) == 1:  # doesn't contain ':', it is a message
            if len(fields[0]):
                messages.append(fields[0])
        else:  # it is a rule
            rules.append((int(fields[0]), fields[1].strip()))
   
    rules.sort()
    return dict([unpack_rule(r) for r in rules]), messages

myprint = noprint
def expand(rules, rule):  
    """Recursively expand the rule.
    Numbers are replaced by the rule they reference.
    Sequential list of all strings is merged to single string
    Class alternative represents a list of alternatives never merged together
    Ordinary list represent sequential items
    Items in lists and alternatives are recursively expanded
    """
    myprint("Expand", rule)
    if isinstance(rule, int):
        myprint('Substituting', rule, rules[rule])
        rule = rules[rule]

    
    if isinstance(rule, sequence):
        myprint("Sequence")
        for i, item in enumerate(rule):
            rule[i] = expand(rules, item)
        if all([isinstance(x, str) for x in rule]):
            myprint("Collapsing")
            rule = ''.join(rule)
    elif isinstance(rule, oneormore):
        myprint("One or more")
        for i, item in enumerate(rule):
            rule[i] = expand(rules, item)
    elif isinstance(rule, alternative):
        myprint("Alternatives")
        for i, item in enumerate(rule):
            rule[i] = expand(rules, item)
    # str, oneormore unchanged
    
    return rule
In [ ]:
data = """0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"

ababbb
bababa
abbbab
aaabbb
aaaabbb""".split('\n')

data = data19

rules, messages = parse19(data)    
expand(rules, rules[0])  # Modifies rule in-place

import re
good = re.compile(str(rules[0]))
finds = [good.fullmatch(m) for m in messages]
print(sum([bool(m) for m in finds]))
print(rules[0])
279
(?:(?:a(?:(?:b(?:(?:ba|ab)(?:b|a)a|(?:b(?:b|a)(?:b|a)|abb)b)|a(?:b(?:a(?:(?:b|a)a|bb)|bba)|aa(?:b|a)(?:b|a)))a|(?:a(?:bbba|a(?:(?:ba|ab)b|aaa))|b(?:(?:aba|bbb)a|(?:a(?:bb|ab)|bab)b))b)|b(?:(?:b(?:b(?:bba|a(?:bb|ab))|a(?:(?:bb|ab)b|(?:ba|ab)a))|a(?:(?:(?:b|a)(?:b|a)b|(?:ba|ab)a)a|(?:(?:ba|ab)a|(?:(?:b|a)a|bb)b)b))a|(?:(?:b(?:aab|b(?:bb|ab))|a(?:a(?:bb|ab)|b(?:aa|ba)))b|(?:(?:(?:ba|ab)a|(?:(?:b|a)a|bb)b)b|(?:aba|(?:a(?:b|a)|ba)b)a)a)b))a|(?:a(?:(?:a(?:b(?:b|a)(?:b|a)a|(?:bba|a(?:aa|ba))b)|b(?:a(?:a(?:b|a)|ba)(?:b|a)|b(?:b(?:a(?:b|a)|ba)|a(?:bb|ab))))b|(?:(?:(?:a(?:b|a)|ba)(?:b|a)a|(?:a(?:(?:b|a)a|bb)|b(?:a(?:b|a)|ba))b)b|(?:b(?:bbb|aaa)|a(?:(?:ba|ab)b|aaa))a)a)|b(?:a(?:b(?:(?:b(?:(?:b|a)a|bb)|a(?:aa|ab))b|(?:bab|a(?:a(?:b|a)|ba))a)|a(?:a(?:a(?:a(?:b|a)|ba)|bbb)|bb(?:b|a)(?:b|a)))|b(?:b(?:(?:aba|bab)b|(?:a(?:(?:b|a)a|bb)|b(?:a(?:b|a)|ba))a)|a(?:(?:aaa|b(?:ab|b(?:b|a)))a|(?:a(?:bb|ab)|b(?:aa|ba))b))))b)(?:(?:a(?:(?:b(?:(?:ba|ab)(?:b|a)a|(?:b(?:b|a)(?:b|a)|abb)b)|a(?:b(?:a(?:(?:b|a)a|bb)|bba)|aa(?:b|a)(?:b|a)))a|(?:a(?:bbba|a(?:(?:ba|ab)b|aaa))|b(?:(?:aba|bbb)a|(?:a(?:bb|ab)|bab)b))b)|b(?:(?:b(?:b(?:bba|a(?:bb|ab))|a(?:(?:bb|ab)b|(?:ba|ab)a))|a(?:(?:(?:b|a)(?:b|a)b|(?:ba|ab)a)a|(?:(?:ba|ab)a|(?:(?:b|a)a|bb)b)b))a|(?:(?:b(?:aab|b(?:bb|ab))|a(?:a(?:bb|ab)|b(?:aa|ba)))b|(?:(?:(?:ba|ab)a|(?:(?:b|a)a|bb)b)b|(?:aba|(?:a(?:b|a)|ba)b)a)a)b))a|(?:a(?:(?:a(?:b(?:b|a)(?:b|a)a|(?:bba|a(?:aa|ba))b)|b(?:a(?:a(?:b|a)|ba)(?:b|a)|b(?:b(?:a(?:b|a)|ba)|a(?:bb|ab))))b|(?:(?:(?:a(?:b|a)|ba)(?:b|a)a|(?:a(?:(?:b|a)a|bb)|b(?:a(?:b|a)|ba))b)b|(?:b(?:bbb|aaa)|a(?:(?:ba|ab)b|aaa))a)a)|b(?:a(?:b(?:(?:b(?:(?:b|a)a|bb)|a(?:aa|ab))b|(?:bab|a(?:a(?:b|a)|ba))a)|a(?:a(?:a(?:a(?:b|a)|ba)|bbb)|bb(?:b|a)(?:b|a)))|b(?:b(?:(?:aba|bab)b|(?:a(?:(?:b|a)a|bb)|b(?:a(?:b|a)|ba))a)|a(?:(?:aaa|b(?:ab|b(?:b|a)))a|(?:a(?:bb|ab)|b(?:aa|ba))b))))b)(?:(?:(?:a(?:(?:(?:bbb|bba)a|(?:aab|bbb)b)b|(?:b(?:(?:ab|b(?:b|a))a|(?:a(?:b|a)|ba)b)|a(?:a(?:ba|ab)|b(?:(?:b|a)a|bb)))a)|b(?:b(?:b(?:aab|bbb)|a(?:(?:aa|ab)b|(?:ba|ab)a))|a(?:b(?:abb|b(?:(?:b|a)a|bb))|a(?:ba|ab)(?:b|a))))a|(?:a(?:a(?:(?:(?:b|a)(?:b|a)b|baa)b|a(?:b|a)(?:b|a)a)|b(?:a(?:bbb|bba)|b(?:a(?:aa|ba)|bbb)))|b(?:a(?:(?:a(?:ba|ab)|bab)a|(?:a(?:aa|ba)|b(?:ba|ab))b)|b(?:(?:b(?:(?:b|a)a|bb)|a(?:aa|ab))a|(?:(?:ba|ab)a|(?:ab|b(?:b|a))b)b)))b)b|(?:a(?:(?:a(?:b(?:(?:b|a)(?:b|a)b|(?:a(?:b|a)|ba)a)|a(?:a(?:ba|ab)|b(?:(?:b|a)a|bb)))|b(?:(?:(?:a(?:b|a)|ba)b|(?:(?:b|a)a|bb)a)a|(?:bbb|(?:b|a)(?:b|a)a)b))b|(?:a(?:ab(?:b|a)(?:b|a)|b(?:(?:(?:b|a)a|bb)b|baa))|b(?:a(?:(?:aa|ab)a|(?:a(?:b|a)|ba)b)|bb(?:aa|ba)))a)|b(?:b(?:a(?:b(?:(?:bb|ab)b|(?:ba|ab)a)|aa(?:b|a)(?:b|a))|b(?:a(?:(?:aa|ba)a|(?:a(?:b|a)|ba)b)|b(?:a(?:b|a)(?:b|a)|bba)))|a(?:(?:b(?:bab|baa)|a(?:bbb|a(?:aa|ab)))a|(?:b(?:bba|(?:bb|ab)b)|a(?:bab|a(?:a(?:b|a)|ba)))b)))a)
In [ ]:
 

--- Part Two ---

As you look over the list of messages, you realize your matching rules aren't quite right. To fix them, completely replace rules 8: 42 and 11: 42 31 with the following:

  8: 42 | 42 8
  11: 42 31 | 42 11 31

This small change has a big impact: now, the rules do contain loops, and the list of messages they could hypothetically match is infinite. You'll need to determine how these changes affect which messages are valid.

Fortunately, many of the rules are unaffected by this change; it might help to start by looking at which rules always match the same set of values and how those rules (especially rules 42 and 31) are used by the new versions of rules 8 and 11.

(Remember, you only need to handle the rules you have; building a solution that could handle any hypothetical combination of rules would be significantly more difficult.)

Oh FFS recursive expressions!

In [ ]:
data = data19

rules, messages = parse19(data)   

#   8: 42 | 42 8  
# This one is ok, can be handled by (...)+ in an RE
rules[8] = oneormore([42])

rules8 = alternative([
    sequence([42]), 
    sequence([42, 42,]), 
    sequence([42, 42, 42]), 
    sequence([42, 42, 42, 42]), 
    sequence([42, 42, 42, 42, 42]), 
])

#  11: 42 31 | 42 11 31
# Oh boy.  42^n31^n 
# https://stackoverflow.com/questions/3644266/how-can-we-match-an-bn UGH
# Expand the recursive definition manually until no more messages match
rules[11] = alternative([
    sequence([42,31]), 
    sequence([42,42,31,31]), 
    sequence([42,42,42,31,31,31]),
#    sequence([42,42,42,42,31,31,31,31]),
])

expand(rules, rules[0])  # Modifies rule in-pace

import re
good = re.compile(str(rules[0]))
finds = [good.fullmatch(m) for m in messages]
print(sum([bool(m) for m in finds]))
#print(rules[0])
381

--- Day 20: Jurassic Jigsaw ---

The high-speed train leaves the forest and quickly carries you south. You can even see a desert in the distance! Since you have some spare time, you might as well see if there was anything interesting in the image the Mythical Information Bureau satellite captured.

After decoding the satellite messages, you discover that the data actually contains many small images created by the satellite's camera array. The camera array consists of many cameras; rather than produce a single square image, they produce many smaller square image tiles that need to be reassembled back into a single image.

Each camera in the camera array returns a single monochrome image tile with a random unique ID number. The tiles (your puzzle input) arrived in a random order.

Worse yet, the camera array appears to be malfunctioning: each image tile has been rotated and flipped to a random orientation. Your first task is to reassemble the original image by orienting the tiles so they fit together.

To show how the tiles should be reassembled, each tile's image data includes a border that should line up exactly with its adjacent tiles. All tiles have this border, and the border lines up exactly when the tiles are both oriented correctly. Tiles at the edge of the image also have this border, but the outermost edges won't line up with any other tiles.

For example, suppose you have the following nine tiles:

Tile 2311:
..##.#..#.
##..#.....
#...##..#.
####.#...#
##.##.###.
##...#.###
.#.#.#..##
..#....#..
###...#.#.
..###..###

etc

By rotating, flipping, and rearranging them, you can find a square arrangement that causes all adjacent borders to line up:

```#...##.#.. ..###..### #.#.#####.
..#.#..#.# ###...#.#. .#..######
.###....#. ..#....#.. ..#.......
###.##.##. .#.#.#..## ######....
.###.##### ##...#.### ####.#..#.
.##.#....# ##.##.###. .#...#.##.
#...###### ####.#...# #.#####.##
.....#..## #...##..#. ..#.###...
#.####...# ##..#..... ..#.......
#.##...##. ..##.#..#. ..#.###...

#.##...##. ..##.#..#. ..#.###...
##..#.##.. ..#..###.# ##.##....#
##.####... .#.####.#. ..#.###..#
####.#.#.. ...#.##### ###.#..###
.#.####... ...##..##. .######.##
.##..##.#. ....#...## #.#.#.#...
....#..#.# #.#.#.##.# #.###.###.
..#.#..... .#.##.#..# #.###.##..
####.#.... .#..#.##.. .######...
...#.#.#.# ###.##.#.. .##...####

...#.#.#.# ###.##.#.. .##...####
..#.#.###. ..##.##.## #..#.##..#
..####.### ##.#...##. .#.#..#.##
#..#.#..#. ...#.#.#.. .####.###.
.#..####.# #..#.#.#.# ####.###..
.#####..## #####...#. .##....##.
##.##..#.. ..#...#... .####...#.
#.#.###... .##..##... .####.##.#
#...###... ..##...#.. ...#..####
..#.#....# ##.#.#.... ...##.....

For reference, the IDs of the above tiles are:

1951    2311    3079
2729    1427    2473
2971    1489    1171

To check that you've assembled the image correctly, multiply the IDs of the four corner tiles together. If you do this with the assembled tiles from the example above, you get 1951 3079 2971 * 1171 = 20899048083289.

Assemble the tiles into an image. What do you get if you multiply together the IDs of the four corner tiles?

In [ ]:
input20 = read_and_clean(20)
Input ['Tile 1579:', '.#.##.#..#'] ... ['..#.###..#', '']
In [ ]:
from collections import defaultdict

# 144 10x10 tiles
# How to represent tile data for comparison?  Convert edges to binary numbers.
# Both in CW and CCW directions.  10 bit edges have 1024 possibilities


                
def edge_to_number(s):  # Return normal, flipped
    s = s.replace('#', '1').replace('.', '0')
    return int(s, 2), int(s[::-1], 2)

def tile_row(tile, row):
    return tile[row]


def tile_column(tile, col):
    l = [row[col] for row in tile]
    s = ''.join(l)
    return s

def tile_to_edgeids(tile):
    # Normal orientation is L->R T->B
    top = edge_to_number(tile_row(tile, 0))    
    bottom = edge_to_number(tile_row(tile, 9))    
    right = edge_to_number(tile_column(tile, 9))    
    left = edge_to_number(tile_column(tile, 0))
    
    return [top, right, bottom, left]



def parse20(lines):
    i = 0
    tiles = {}
    edge_dict = defaultdict(set)  # for each edge value, which tiles have it
    
    while i < len(lines):
            tile_id = int(lines[i].split()[1].strip(':'))
            tile = lines[i+1:i+11]

            ids = tile_to_edgeids(list(tile))
            tiles[tile_id] = (tile_id, ids, 'T', False)

            allids = ids[0] + ids[1] + ids[2] + ids[3]
            for nid in allids:
                edge_dict[nid].add(tile_id)
            i += 12
            
    return tiles, edge_dict

tiles, edges = parse20(input20)
#print("Edges", edges)


# want to find tiles that have one or two edges that don't match with any other tile.
# These are candidates for corners and outer edges

def find_corners(tiles, edges):
    corners = []
    outer_edges = []
    inners = []
    
    for tile in tiles.values():
        num_unmatched = 0
        tileid, ids, orientation, flipped = tile
        selfset = set([tileid])  # Going to remove self from set of tiles that have given edgeid
        edge_matches = []
        for edgeids in ids:  # top, right, bottom, left
            s1 = edges[edgeids[0]] - selfset  # normal
            s2 = edges[edgeids[1]] - selfset  # flipped
            ss = s1 | s2  # All tiles that have an edge matching one on current tile
            if len(ss):
                edge_matches.append(list(ss)[0])
            else:
                edge_matches.append(None)
                
        nomatch = edge_matches.count(None)        
        if nomatch == 1:
            #print("^^^^ EDGE ^^^^")
            outer_edges.append((tile, edge_matches))
        elif nomatch == 2:
            #print("^^^^ CORNER ^^^^")
            corners.append((tile, edge_matches))
        else:
            inners.append((tile, edge_matches))
            
    return corners, outer_edges, inners

    
             
print("Find corners")
corners, outers, inners = find_corners(tiles, edges)
matched_tiles = corners + outers + inners

print(len(corners), len(outers), len(inners), len(matched_tiles))


# Don't need to assemble the matrix to answer part 1
corner_ids = [corner[0][0] for corner in corners]
reduce(mul, corner_ids)
Find corners
4 40 100 144
Out[ ]:
79412832860579
In [ ]:
# Redesign with a Tile class for part 2
directions = "TRBL"

T=0
R=1
B=2
L=3

def flip(t):
    return t[1], t[0]


def string_reverse(s):
    r = ''
    for c in s:
        r = c + r
    return r

        
class Tile(object):
    def __init__(self, tile_id, pattern):
        self._id =  tile_id
        self.pattern = pattern
        self.edges = tile_to_edgeids(list(pattern)) # TRBL
        self.allids = self.edges[0] + self.edges[1] + self.edges[2] + self.edges[3] 
        self.neighbours = [0] * 4  # TRBL

    def find_neighbours(self, edges):
        self.neighbours = []
        selfset = set((self._id,))
        for edgeids in self.edges:  # top, right, bottom, left
            s1 = edges[edgeids[0]] - selfset  # normal
            s2 = edges[edgeids[1]] - selfset  # flipped
            ss = s1 | s2  # All tiles that have an edge matching one on current tile
            if len(ss):
                self.neighbours.append(list(ss)[0])
            else:
                self.neighbours.append(0)
                
    def is_corner(self):
        return self.neighbours.count(0) == 2
    
 
    def rotate_cw(self):
        left= self.edges[L]  # Rotate edges
        self.edges[L] = self.edges[B]
        self.edges[B] = flip(self.edges[R])
        self.edges[R] = self.edges[T]
        self.edges[T] = flip(left)
        # Rotate neighbours
        self.neighbours = [self.neighbours[L]] + self.neighbours[T:L]
        # Rotate pattern
        pattern = [''] * len(self.pattern)
        for r, line in enumerate(self.pattern):
            for i, c in enumerate(line):
                pattern[i] = c + pattern[i]
        self.pattern = pattern
                
       
    def flip_lr(self):
        left= self.edges[L]  # Flip edges
        self.edges[L] = self.edges[R]
        self.edges[R] = left
        self.edges[B] = flip(self.edges[B])
        self.edges[T] = flip(self.edges[T])

        # Flip neighbours
        self.neighbours = [self.neighbours[T], self.neighbours[L], self.neighbours[B], self.neighbours[R]]
        # Flip pattern
        self.pattern = [string_reverse(line) for line in self.pattern]
           
    def rotate_ccw(self):
        self.rotate_cw()
        self.rotate_cw()
        self.rotate_cw()
        
    def flip_tb(self):
        self.rotate_cw()
        self.flip_lr()
        self.rotate_ccw()
        
    def flip_diag(self):
        self.rotate_cw()
        self.flip_lr()
    
    def match(self, other, direction):
        """Reorient self to match other in given direction from self"""
        while self.neighbours[direction] != other._id:
            #print('CW')
            self.rotate_cw()

        opposite = (direction + 2) % 4
        if self.edges[direction][0] != other.edges[opposite][0]:
            if direction in (T, B):
                self.flip_lr()  # Neigbour above or below. Flip edge touching neighbour
            else:
                self.flip_tb()
        
    def __str__(self):
        return f"Tile {self._id} {self.edges} {self.neighbours}"
    
    def pattern_str(self):
        return '\n'.join(self.pattern)
    

def parse20c(lines):
    i = 0
    tiles = {}
    edge_dict = defaultdict(set)  # for each edge value, which tiles have it
    
    while i < len(lines):
            tile_id = int(lines[i].split()[1].strip(':'))
            pattern = lines[i+1:i+11]
            tile = Tile(tile_id, pattern)
            tiles[tile_id] = tile

            for nid in tile.allids:
                edge_dict[nid].add(tile_id)
            i += 12
            
    return tiles, edge_dict

tiles, edges = parse20c(input20)
        
def update_neighbours(tiles, edges):
    for tile in tiles.values():
        tile.find_neighbours(edges)

update_neighbours(tiles, edges)

corners = [tile for tile in tiles.values() if tile.is_corner()]
if True:
    print('Corners')
    for tile in corners:
        print(tile)
        #print(tile.pattern_str())

        
if False:
    # Testing rotation operations
    t = tiles[3433]
    print(t)
    print(t.pattern_str())
    t.rotate_ccw()
    print(t)
    print(t.pattern_str())
    t.flip_tb()
    print(t)
    print(t.pattern_str())
Corners
Tile 3433 [(839, 907), (890, 379), (256, 2), (620, 217)] [2837, 0, 0, 1973]
Tile 3833 [(864, 27), (285, 738), (1007, 991), (997, 671)] [0, 0, 3943, 1013]
Tile 2011 [(573, 753), (578, 265), (230, 412), (1002, 351)] [0, 3793, 3491, 0]
Tile 3001 [(508, 254), (260, 130), (420, 150), (348, 234)] [1429, 1279, 0, 0]

Reassemble the actual image Now, you're ready to search for sea monsters! Because your image is monochrome, a sea monster will look like this:

                  # 
#    ##    ##    ###
 #  #  #  #  #  #

When looking for this pattern in the image, the spaces can be anything; only the # need to match. Also, you might need to rotate or flip your image before it's oriented correctly to find sea monsters. In the above image, after flipping and rotating it to the appropriate orientation, there are two sea monsters (marked with O):

.####...#####..#...###..
#####..#..#.#.####..#.#.
.#.#...#.###...#.##.O#..
#.O.##.OO#.#.OO.##.OOO##
..#O.#O#.O##O..O.#O##.##
...#.#..##.##...#..#..##
#.##.#..#.#..#..##.#.#..
.###.##.....#...###.#...
#.####.#.#....##.#..#.#.
##...#..#....#..#...####
..#.##...###..#.#####..#
....#.##.#.#####....#...
..##.##.###.....#.##..#.
#...#...###..####....##.
.#.##...#.##.#.#.###...#
#.###.#..####...##..#...
#.###...#.##...#.##O###.
.O##.#OO.###OO##..OOO##.
..O#.O..O..O.#O##O##.###
#.#..##.########..#..##.
#.#####..#.#...##..#....
#....##..#.#########..##
#...#.....#..##...###.##
#..###....##.#...##.##.#

Determine how rough the waters are in the sea monsters' habitat by counting the number of # that are not part of a sea monster. In the above example, the habitat's water roughness is 273.

How many # are not part of a sea monster?

Answer:

In [ ]:
# Reassemble the image
# Edges are (top, right, bottom, left)   each pair (normal, flipped)
   
# Orientations are WRT top: TRBL  , flipped = True or False
# corners[2]  # Top and Left are empty, so make this the top left corner.

# All this works when there is no ambiguity. i.e. no multiple matches

for tile in corners:
    if tile.neighbours[L] == 0 and tile.neighbours[T] == 0:
        top_left_corner = tile

# Starting with a seed in the top left corner, fill rows by matching neighbours,
# rotating and flipping until the edges match up.
# Then start next row with tile that matches one above.
square_side = 12
rows = []
for r in range(square_side):
    if r == 0:
        row = [top_left_corner]  
    else:
        above = rows[r - 1][0]
        here = tiles[above.neighbours[B]]
        here.match(above, T)
        row = [here]
        
    for i in range(square_side - 1):  # build along row
        current = row[-1]             # From last tile   
        next_tile = tiles[current.neighbours[R]]  # Get its neigbour to the right
        next_tile.match(current, L)  # reorient to match
        row.append(next_tile)        # and put in place

    rows.append(row)

    
picture = []  # Tiles are 10x10, with borders all round.
for row in rows:  # of tiles
    for cr in range(1,9): # cr points to a row in a tile picture. Drop rows 0 and 9
        line = ""
        for col in row:  # col is a tile
            line = line + col.pattern[cr][1:9]
        picture.append(line)
        
#print('\n'.join(picture))

monster = [
#01234567890123456789
"                  # ", 
"#    ##    ##    ###",
" #  #  #  #  #  #   "   
#01234567890123456789
]


# Offsets of '#' in lines of monster picture
def see_monster(picture, r, c):
    nmonster = (
        (18,),
        (0,5,6,11,12,17,18,19),
        (1,4,7,10,13,16)
    )

    maxmc = 19
    for mr, mcc in enumerate(nmonster):
        for mc in mcc:
            if picture[r + mr][c + mc] != '#':
                return False
    return True


def find_monsters(Tile):
    nm = 0
    for r in range(len(picture) - 2):
        for c in range(len(picture[0]) - 19):
            if see_monster(pt.pattern, r, c):
                #print(f"Monster at {r},{c}")
                nm += 1
    return nm



# Check all orientations and flips
pt = Tile(1, picture)  # Tile class implements flip and rotate operations
for f in range(2):
    for i in range(4):
        nm = find_monsters(pt)
        if nm:
            num_monsters = nm
            print(num_monsters)
            if num_monsters:  # Without this, see that only one of 8 orientations has any monsters
                break         # so break out
        pt.rotate_cw()
    if num_monsters:  # Without this, see that only one of 8 orientations has any monsters
        break         # so break out
    pt.flip_lr()
    

print("NM",num_monsters)
monster_octothorpe_n = ''.join(monster).count('#')
picture_octothorpe_n = ''.join(picture).count('#')

print("Day 20 part 2 =", picture_octothorpe_n - monster_octothorpe_n * num_monsters)
25
NM 25
Day 20 part 2 = 2155

--- Day 21: Allergen Assessment ---

You reach the train's last stop and the closest you can get to your vacation island without getting wet. There aren't even any boats here, but nothing can stop you now: you build a raft. You just need a few days' worth of food for your journey.

You don't speak the local language, so you can't read any ingredients lists. However, sometimes, allergens are listed in a language you do understand. You should be able to use this information to determine which ingredient contains which allergen and work out which foods are safe to take with you on your trip.

You start by compiling a list of foods (your puzzle input), one food per line. Each line includes that food's ingredients list followed by some or all of the allergens the food contains.

Each allergen is found in exactly one ingredient. Each ingredient contains zero or one allergen. Allergens aren't always marked; when they're listed (as in (contains nuts, shellfish) after an ingredients list), the ingredient that contains each listed allergen will be somewhere in the corresponding ingredients list. However, even if an allergen isn't listed, the ingredient that contains that allergen could still be present: maybe they forgot to label it, or maybe it was labeled in a language you don't know.

For example, consider the following list of foods:

mxmxvkd kfcds sqjhc nhms (contains dairy, fish) trh fvjkl sbzzf mxmxvkd (contains dairy) sqjhc fvjkl (contains soy) sqjhc mxmxvkd sbzzf (contains fish)

a b c d        dairy, fish
a       e f g  dairy
    c     f    soy
a   c       g  fish

b,d,e, g cannot be allergens

The first food in the list has four ingredients (written in a language you don't understand): mxmxvkd, kfcds, sqjhc, and nhms. While the food might contain other allergens, a few allergens the food definitely contains are listed afterward: dairy and fish.

The first step is to determine which ingredients can't possibly contain any of the allergens in any food in your list. In the above example, none of the ingredients kfcds, nhms, sbzzf, or trh can contain an allergen. Counting the number of times any of these ingredients appear in any ingredients list produces 5: they all appear once each except sbzzf, which appears twice.

Determine which ingredients cannot possibly contain any of the allergens in your list. How many times do any of those ingredients appear?

In [ ]:
def clean21(line):
    ingreds, allergens = line.split('(')
    ingreds = ingreds.strip().split()
    allergens = allergens.strip(')')
    allergens = allergens[9:]
    allergens = allergens.split(',')
    allergens = [a.strip() for a in allergens]
    
    return set(ingreds), set(allergens)
    
foods = read_and_clean(21, clean21)
Input [({'zcdcdf', 'dqbjj', 'qpxhfp', 'nnrn', 'svhqc', 'jzlflq', 'nhvx', 'fxsxh', 'jxmg', 'rdn', 'kpsdtv', 'mctnbp', 'cxbqtf', 'fnpdz', 'hpnnf', 'nsmss', 'kxddqq', 'nnlg', 'kdggj', 'sltqs', 'brfpl', 'tcl', 'kxzkbk', 'fdm', 'bmvpz', 'btfh', 'kdxmz', 'hlvl', 'slhjm', 'zkmbc', 'tddgr', 'fllssz', 'fvvrc', 'cmmpcm', 'nnffp', 'xfrhjm', 'jkbrhq', 'krjt', 'dxftvrth', 'xxrck', 'dqnd', 'qjxbtlc', 'jmpj', 'zggxkc', 'zmsh', 'ljzcbx', 'nddjz', 'kmvqht', 'bvlksl', 'jpcsh', 'kkxjgg', 'vfs', 'pngbxj', 'zbnv', 'pcjsl', 'prs', 'rgxnd', 'fhbldf', 'sxvr', 'mpzz', 'nfjl', 'qndk', 'ckrj', 'xgf', 'hmm', 'pmjzb', 'lhnd', 'rvfhqbz', 'mzjhbl', 'smrks', 'nvhhp', 'nzp', 'szjdxh', 'stf', 'pbbhtd', 'kgbzf', 'xzrn', 'jcfsd', 'brfpvc', 'czvgtl', 'xpjdsc', 'dhqfbv', 'qjnqkj', 'ccsxr', 'cdqqt', 'tmcql'}, {'shellfish', 'wheat'}), ({'zcdcdf', 'ckrj', 'rmpf', 'fnzgd', 'dbjtns', 'dqbjj', 'xgf', 'rblrbnhp', 'tcl', 'qlhm', 'svsq', 'rtct', 'svhqc', 'nhvx', 'lnljt', 'lmxrnmg', 'znnf', 'mzjhbl', 'xfrhjm', 'vlfgsn', 'jvgxg', 'kfjf', 'llhzxnrz', 'fxsxh', 'kcj', 'nvhhp', 'mqls', 'kpsdtv', 'dxjdbh', 'zggxkc', 'jmpj', 'hdm', 'xbtfvdn', 'szjdxh', 'kgbzf', 'jrrqzc', 'jcfsd', 'fgvhf', 'bvlksl', 'cxbqtf', 'slhjm', 'czvgtl', 'rrnhxk', 'tddgr', 'fllssz', 'hpnnf', 'pzk', 'fvvrc', 'kksxbr', 'dnjjt', 'rgxnd', 'czplkc', 'sfxmr', 'kdggj', 'pzmg', 'sxbjr', 'hrrbkv', 'tvxxn', 'xjkk', 'nzlpn'}, {'shellfish', 'soy', 'dairy'})] ... [({'zcdcdf', 'dqbjj', 'brfpl', 'ckrj', 'dbjtns', 'qpxhfp', 'nnrn', 'hvgxt', 'pmjzb', 'tcl', 'qlhm', 'dxftvrth', 'rtct', 'zvvffr', 'nhvx', 'xdzlvg', 'mzjhbl', 'bmvpz', 'kcj', 'fxsxh', 'lzmfqvz', 'rdn', 'mqls', 'jnpbc', 'jhc', 'szjdxh', 'hlvl', 'jrrqzc', 'kgbzf', 'tdkfbq', 'lbxd', 'cxbqtf', 'slhjm', 'czvgtl', 'bzbm', 'rkgqk', 'pngbxj', 'dhqfbv', 'fzmcnxjx', 'zbnv', 'xhlfkd', 'fllssz', 'mvzs', 'vmnfl', 'fvvrc', 'qgqqm', 'kgvmlg', 'dztlx', 'rgxnd', 'kdggj', 'cmmpcm', 'pzmg', 'hrrbkv', 'sxvr', 'nnffp', 'djffq', 'xjkk', 'lkr', 'cdqqt', 'tpmkh', 'rrbklsh'}, {'wheat'}), ({'qpxhfp', 'dsghqp', 'zcdcdf', 'bzkfh', 'pcxfhk', 'jqvppk', 'jrdpn', 'pmjzb', 'xgqzlrd', 'trfmsz', 'xxrck', 'xdzlvg', 'lmxrnmg', 'zpmqcv', 'mzjhbl', 'gmdxrp', 'llhzxnrz', 'gcmzg', 'btfh', 'bnjmx', 'fxsxh', 'nvhhp', 'mqls', 'kpsdtv', 'kdxmz', 'znkx', 'glnj', 'dxjdbh', 'hdm', 'xbtfvdn', 'qkkkvb', 'jrrqzc', 'xzrn', 'kgbzf', 'hblgrjgp', 'bvlksl', 'fgvhf', 'kmvqht', 'gfth', 'czvgtl', 'tksln', 'bzbm', 'rkgqk', 'pngbxj', 'vfs', 'fllssz', 'vmnfl', 'fvvrc', 'prs', 'rgxnd', 'kbrdv', 'kdggj', 'ztx', 'pzmg', 'zzzgx', 'djffq', 'tvxxn', 'sxvr', 'nnffp', 'lkr', 'prmglh', 'mpzz', 'kzmfh', 'qndk', 'ktqn'}, {'nuts', 'wheat', 'dairy'})]
In [ ]:
allergens = set()
ingredients = set()
for food in foods:
    ingredients |= food[0]
    allergens |= food[1]

possible = {}
all_possible = set()
for allergen in allergens:
    common = set(ingredients)
    for food in foods:
        if allergen in food[1]:
            ingreds = set(food[0])
            common &= ingreds
    possible[allergen] = common
    all_possible |= common
    
not_possible = set(ingredients) - all_possible

answer = 0
for ingredient in not_possible:
    for ingredients, _ in foods:
        if ingredient in ingredients:
            answer += 1

answer
Out[ ]:
1885

--- Part Two ---

Now that you've isolated the inert ingredients, you should have enough information to figure out which ingredient contains which allergen.

In the above example:

mxmxvkd contains dairy.
sqjhc contains fish.
fvjkl contains soy.

Arrange the ingredients alphabetically by their allergen and separate them by commas to produce your canonical dangerous ingredient list. (There should not be any spaces in your canonical dangerous ingredient list.) In the above example, this would be mxmxvkd,sqjhc,fvjkl.

Time to stock your raft with supplies. What is your canonical dangerous ingredient list?

In [ ]:
for i in range(len(allergens)):   # Repeatedly refine possible pairings
    for k, v in possible.items():
        if isinstance(v, str):
            continue
        if len(v) == 1:  # This pairing is mandatory
            known = list(v)[0]
            possible[k] = known  # replace 1 element set with its contents
            for k, v in possible.items():
                if not isinstance(v, str):
                    v -= set([known])  # Remove the used item from all other sets

# Part 2 answer
','.join([x[1] for x in sorted(list(possible.items()))])
Out[ ]:
'fllssz,kgbzf,zcdcdf,pzmg,kpsdtv,fvvrc,dqbjj,qpxhfp'
--- Day 22: Crab Combat ---

It only takes a few hours of sailing the ocean on a raft for boredom to sink in. Fortunately, you brought a small deck of space cards! You'd like to play a game of Combat, and there's even an opponent available: a small crab that climbed aboard your raft before you left.

Fortunately, it doesn't take long to teach the crab the rules.

Before the game starts, split the cards so each player has their own deck (your puzzle input). Then, the game consists of a series of rounds: both players draw their top card, and the player with the higher-valued card wins the round. The winner keeps both cards, placing them on the bottom of their own deck so that the winner's card is above the other card. If this causes a player to have all of the cards, they win, and the game ends.

For example, consider the following starting decks:

Player 1:
9
2
6
3
1

Player 2:
5
8
4
7
10

This arrangement means that player 1's deck contains 5 cards, with 9 on top and 1 on the bottom; player 2's deck also contains 5 cards, with 5 on top and 10 on the bottom.

The first round begins with both players drawing the top card of their decks: 9 and 5. Player 1 has the higher card, so both cards move to the bottom of player 1's deck such that 9 is above 5. In total, it takes 29 rounds before a player has all of the cards:

-- Round 1 --
Player 1's deck: 9, 2, 6, 3, 1
Player 2's deck: 5, 8, 4, 7, 10
Player 1 plays: 9
Player 2 plays: 5
Player 1 wins the round!

-- Round 2 --
Player 1's deck: 2, 6, 3, 1, 9, 5
Player 2's deck: 8, 4, 7, 10
Player 1 plays: 2
Player 2 plays: 8
Player 2 wins the round!

-- Round 3 --
Player 1's deck: 6, 3, 1, 9, 5
Player 2's deck: 4, 7, 10, 8, 2
Player 1 plays: 6
Player 2 plays: 4
Player 1 wins the round!

-- Round 4 --
Player 1's deck: 3, 1, 9, 5, 6, 4
Player 2's deck: 7, 10, 8, 2
Player 1 plays: 3
Player 2 plays: 7
Player 2 wins the round!

-- Round 5 --
Player 1's deck: 1, 9, 5, 6, 4
Player 2's deck: 10, 8, 2, 7, 3
Player 1 plays: 1
Player 2 plays: 10
Player 2 wins the round!

...several more rounds pass...

-- Round 27 --
Player 1's deck: 5, 4, 1
Player 2's deck: 8, 9, 7, 3, 2, 10, 6
Player 1 plays: 5
Player 2 plays: 8
Player 2 wins the round!

-- Round 28 --
Player 1's deck: 4, 1
Player 2's deck: 9, 7, 3, 2, 10, 6, 8, 5
Player 1 plays: 4
Player 2 plays: 9
Player 2 wins the round!

-- Round 29 --
Player 1's deck: 1
Player 2's deck: 7, 3, 2, 10, 6, 8, 5, 9, 4
Player 1 plays: 1
Player 2 plays: 7
Player 2 wins the round!


== Post-game results ==
Player 1's deck: 
Player 2's deck: 3, 2, 10, 6, 8, 5, 9, 4, 7, 1

Once the game ends, you can calculate the winning player's score. The bottom card in their deck is worth the value of the card multiplied by 1, the second-from-the-bottom card is worth the value of the card multiplied by 2, and so on. With 10 cards, the top card is worth the value on the card multiplied by 10. In this example, the winning player's score is:

   3 * 10
+  2 *  9
+ 10 *  8
+  6 *  7
+  8 *  6
+  5 *  5
+  9 *  4
+  4 *  3
+  7 *  2
+  1 *  1
= 306

So, once the game ends, the winning player's score is 306.

Play the small crab in a game of Combat using the two decks you just dealt. What is the winning player's score?
In [ ]:
input22 = read_and_clean(22)
deck1 = [int(n) for n in input22[1:26]]
deck2 = [int(n) for n in input22[28:]]

def bout(deck1, deck2):
    c1 = deck1[0]
    c2 = deck2[0]
    if c1 > c2:
        #print("d1 won")
        deck2 = deck2[1:]
        deck1 = deck1[1:]
        deck1.extend([c1, c2])
    elif c2 > c1:
        deck1 = deck1[1:]
        deck2 = deck2[1:]
        deck2.extend([c2, c1])
    else:
        print("draw")
    
    return deck1, deck2
        
def combat(deck1, deck2):
    rounds = 0
    while len(deck1) > 0 and len(deck2) > 0:
        deck1, deck2 = bout(deck1, deck2)
        rounds += 1
    return deck1, deck2

d1, d2 = combat(deck1, deck2)
winner1 = d1 if len(d1) else d2

def answer(deck):
    n = 0
    for i in range(1, len(deck)+1):
        n += deck[-i] * i

    return n

answer(winner1)
Input ['Player 1:', '27'] ... ['39', '8']
Out[ ]:
32162

--- Part Two ---

You lost to the small crab! Fortunately, crabs aren't very good at recursion. To defend your honor as a Raft Captain, you challenge the small crab to a game of Recursive Combat.

Recursive Combat still starts by splitting the cards into two decks (you offer to play with the same starting decks as before - it's only fair). Then, the game consists of a series of rounds with a few changes:

Before either player deals a card, if there was a previous round in this game that had exactly the same cards in the same order in the same players' decks, the game instantly ends in a win for player 1. Previous rounds from other games are not considered. (This prevents infinite games of Recursive Combat, which everyone agrees is a bad idea.)
Otherwise, this round's cards must be in a new configuration; the players begin the round by each drawing the top card of their deck as normal.
If both players have at least as many cards remaining in their deck as the value of the card they just drew, the winner of the round is determined by playing a new game of Recursive Combat (see below).
Otherwise, at least one player must not have enough cards left in their deck to recurse; the winner of the round is the player with the higher-value card.

As in regular Combat, the winner of the round (even if they won the round by winning a sub-game) takes the two cards dealt at the beginning of the round and places them on the bottom of their own deck (again so that the winner's card is above the other card). Note that the winner's card might be the lower-valued of the two cards if they won the round due to winning a sub-game. If collecting cards by winning the round causes a player to have all of the cards, they win, and the game ends.

Here is an example of a small game that would loop forever without the infinite game prevention rule:

Player 1: 43 19

Player 2: 2 29 14

During a round of Recursive Combat, if both players have at least as many cards in their own decks as the number on the card they just dealt, the winner of the round is determined by recursing into a sub-game of Recursive Combat. (For example, if player 1 draws the 3 card, and player 2 draws the 7 card, this would occur if player 1 has at least 3 cards left and player 2 has at least 7 cards left, not counting the 3 and 7 cards that were drawn.)

To play a sub-game of Recursive Combat, each player creates a new deck by making a copy of the next cards in their deck (the quantity of cards copied is equal to the number on the card they drew to trigger the sub-game). During this sub-game, the game that triggered it is on hold and completely unaffected; no cards are removed from players' decks to form the sub-game. (For example, if player 1 drew the 3 card, their deck in the sub-game would be copies of the next three cards in their deck.)

In [ ]:
# Use tuples for decks to ensure that subgames get copies rather than references.
# Also tuples are hashable which enables efficient encoding of game state for
# duplicate state checking

deck1 = tuple([int(n) for n in input22[1:26]])
deck2 = tuple([int(n) for n in input22[28:]])
decks = (deck1, deck2)

# Example data
example = ((9, 2, 6, 3, 1), (5, 8, 4, 7, 10))
example_answer = 291


def tuple_pop(t):
    return t[0], t[1:]


def recursive_bout(decks, recurse=0):
    deck1, deck2 = decks
    c1, deck1 = tuple_pop(deck1)
    c2, deck2 = tuple_pop(deck2)
    if c1 <= len(deck1) and c2 <= len(deck2):  # Recursive game rule
        rd1 = deck1[:c1]
        rd2 = deck2[:c2]
        d1, d2 = recursive_combat((rd1, rd2), recurse + 1)
        if len(d1):
            deck1 = deck1 + (c1, c2)
        else:
            deck2 = deck2 + (c2, c1)
    else:
        if (c1 > c2):
            deck1 = deck1 + (c1, c2)
        else:
            deck2 = deck2 + (c2, c1)
    
    return deck1, deck2
 
    
def recursive_combat(decks, recurse=1):
    
    game_states = set([hash(decks)])  # Detect any infinite loops
    
    while len(decks[0]) > 0 and len(decks[1]) > 0:
        decks = recursive_bout(decks, recurse)
        state = hash(decks)
        if state in game_states:  # Player 1 wins on return to identical state
            return (tuple([1]), tuple())
        else:
            game_states.add(state)
        
    return decks


def game22(decks):
    d = recursive_combat(decks)
    winner2 = d[0] if len(d[0]) else d[1]
    return answer(winner2)

print(f"Example {game22(example) = } Should equal {example_answer}")

print(f"{game22(decks) = }")
Example game22(example) = 291 Should equal 291
game22(decks) = 32534

-- Day 23: Crab Cups ---

The small crab challenges you to a game! The crab is going to mix up some cups, and you have to predict where they'll end up.

The cups will be arranged in a circle and labeled clockwise (your puzzle input). For example, if your labeling were 32415, there would be five cups in the circle; going clockwise around the circle from the first cup, the cups would be labeled 3, 2, 4, 1, 5, and then back to 3 again.

Before the crab starts, it will designate the first cup in your list as the current cup. The crab is then going to do 100 moves.

Each move, the crab does the following actions:

The crab picks up the three cups that are immediately clockwise of the current cup. They are removed from the circle; cup spacing is adjusted as necessary to maintain the circle.
The crab selects a destination cup: the cup with a label equal to the current cup's label minus one. If this would select one of the cups that was just picked up, the crab will keep subtracting one until it finds a cup that wasn't just picked up. If at any point in this process the value goes below the lowest value on any cup's label, it wraps around to the highest value on any cup's label instead.
The crab places the cups it just picked up so that they are immediately clockwise of the destination cup. They keep the same order as when they were picked up.
The crab selects a new current cup: the cup which is immediately clockwise of the current cup.

For example, suppose your cup labeling were 389125467. If the crab were to do merely 10 moves, the following changes would occur:

-- move 1 -- cups: (3) 8 9 1 2 5 4 6 7 pick up: 8, 9, 1 destination: 2

-- move 2 -- cups: 3 (2) 8 9 1 5 4 6 7 pick up: 8, 9, 1 destination: 7

-- move 3 -- cups: 3 2 (5) 4 6 7 8 9 1 pick up: 4, 6, 7 destination: 3

-- move 4 -- cups: 7 2 5 (8) 9 1 3 4 6 pick up: 9, 1, 3 destination: 7

-- move 5 -- cups: 3 2 5 8 (4) 6 7 9 1 pick up: 6, 7, 9 destination: 3

-- move 6 -- cups: 9 2 5 8 4 (1) 3 6 7 pick up: 3, 6, 7 destination: 9

-- move 7 -- cups: 7 2 5 8 4 1 (9) 3 6 pick up: 3, 6, 7 destination: 8

-- move 8 -- cups: 8 3 6 7 4 1 9 (2) 5 pick up: 5, 8, 3 destination: 1

-- move 9 -- cups: 7 4 1 5 8 3 9 2 (6) pick up: 7, 4, 1 destination: 5

-- move 10 -- cups: (5) 7 4 1 8 3 9 2 6 pick up: 7, 4, 1 destination: 3

-- final -- cups: 5 (8) 3 7 4 1 9 2 6

In the above example, the cups' values are the labels as they appear moving clockwise around the circle; the current cup is marked with ( ).

After the crab is done, what order will the cups be in? Starting after the cup labeled 1, collect the othe

r cups' labels clockwise into a single string with no extra characters; each number except 1 should appear exactly once. In the above example, after 10 moves, the cups clockwise from 1 are labeled 9, 2, 6, 5, and so on, producing 92658374. If the crab were to complete all 100 moves, the order after cup 1 would be 67384529.

Using your labeling, simulate 100 moves. What are the labels on the cups after cup 1?

Your puzzle input is 389547612.

In [ ]:
start = "389547612"
#start = "389125467"  # example
cups = tuple([int(c) for c in start])

def shuffle(cups, moves):
    n = len(cups)
    for move in range(moves):
        pickup = cups[1:4]
        rest = cups[0:1] + cups[4:]
        dest = rest[0] - 1
        if dest == 0:
            dest = 9
        while dest in pickup:
            dest = dest - 1
            if dest == 0:
                dest = 9
        insert = rest.index(dest)
        cups = rest[:insert+1] + pickup + rest[insert+1:]
        cups = cups[1:] + cups[0:1]
        #print(pickup, dest, cups)

    return cups
        #print(pickup, rest, dest, insert, cups)

    
print(shuffle(cups, 100))
(4, 5, 2, 8, 6, 3, 9, 7, 1)

--- Part Two ---

Due to what you can only assume is a mistranslation (you're not exactly fluent in Crab), you are quite surprised when the crab starts arranging many cups in a circle on your raft - one million (1000000) in total.

Your labeling is still correct for the first few cups; after that, the remaining cups are just numbered in an increasing fashion starting from the number after the highest number in your list and proceeding one by one until one million is reached. (For example, if your labeling were 54321, the cups would be numbered 5, 4, 3, 2, 1, and then start counting up from 6 until one million is reached.) In this way, every number from one through one million is used exactly once.

After discovering where you made the mistake in translating Crab Numbers, you realize the small crab isn't going to do merely 100 moves; the crab is going to do ten million (10000000) moves!

The crab is going to hide your stars - one each - under the two cups that will end up immediately clockwise of cup 1. You can have them if you predict what the labels on those cups will be when the crab is finished.

In the above example (389125467), this would be 934001 and then 159792; multiplying these together produces 149245887792.

Determine which two cups will end up immediately clockwise of cup 1. What do you get if you multiply their labels together?


So, brute force will take way too long. How to predict the sequence, or make operations much more efficient?

In [ ]:
# Gonna make a linked list where the "value" of each cell is also the "address" of the cell.
# and the address of the next cell is what is stored in the list called links 
# In this system:
# n = value
# links[n] = next(value)
# links[n] == succ(cupsz.index(n))
# Original problem has values starting at one, python lists index from zero, so transform the input
# accordingly.
# Need to transform back for final calculations


def readn(links, ptr, n):
    l = []
    for i in range(n):
        end_read = ptr
        l.append(ptr)
        ptr = links[ptr]
        
    return l, end_read


def strl(links, ptr, count=len(links), delim=','):
    """Print as original 1-based values"""
    l, _ = readn(links, ptr, count)
    l = [str(v+1) for v in l]
    return delim.join(l)


def move(links, current):
    maxcup = len(links)

    p1 = links[current]
    p2 = links[p1]
    p3 = links[p2]
    pickup = (p1, p2 , p3)
    
    dest = (current - 1) % maxcup
    while dest in pickup:
        dest = (dest - 1) % maxcup
    
    # In tuple assignment, all values are read before any are written
    links[dest],    links[p3],   links[current] = \
    links[current], links[dest], links[p3]
    
    return links[current]  


def shuffle(links, current, moves):
    for m in range(moves):
        current = move(links, current)
    return current
        

# Part 1

# Move to zero based indexing
cupsz = [c-1 for c in cups]
maxcup = len(cupsz)
links = [None] * len(cupsz)

for i in range(len(cupsz) - 1):
    links[cupsz[i]] = cupsz[i+1]
links[cupsz[-1]] = cupsz[0]
    
current = cupsz[0]

shuffle(links, current, 100)

print("Day 23 part 1:", strl(links, links[0], count=len(links) - 1, delim=""))

# Part 2
cupsz = [c-1 for c in cups]
maxcup = 1_000_000
links = list(range(1, maxcup+1))
links[-1] = 0

# Splice in old data
links[-1] = cupsz[0]  # wraparound link
for i in range(len(cupsz) - 1):
    links[cupsz[i]] = cupsz[i+1]
links[cupsz[-1]] = len(cupsz)  # link out to rest of long list
    
current = cupsz[0]

shuffle(links, current, 10_000_000)

a = links[0]
b = links[a] 

print("Day 23 part 2:", (a + 1) * (b + 1))  # +1 transform back to 1-based system
Day 23 part 1: 45286397
Day 23 part 2: 836763710

--- Day 24: Lobby Layout ---

Your raft makes it to the tropical island; it turns out that the small crab was an excellent navigator. You make your way to the resort.

As you enter the lobby, you discover a small problem: the floor is being renovated. You can't even reach the check-in desk until they've finished installing the new tile floor.

The tiles are all hexagonal; they need to be arranged in a hex grid with a very specific color pattern. Not in the mood to wait, you offer to help figure out the pattern.

The tiles are all white on one side and black on the other. They start with the white side facing up. The lobby is large enough to fit whatever pattern might need to appear there.

A member of the renovation crew gives you a list of the tiles that need to be flipped over (your puzzle input). Each line in the list identifies a single tile that needs to be flipped by giving a series of steps starting from a reference tile in the very center of the room. (Every line starts from the same reference tile.)

Because the tiles are hexagonal, every tile has six neighbors: east, southeast, southwest, west, northwest, and northeast. These directions are given in your list, respectively, as e, se, sw, w, nw, and ne. A tile is identified by a series of these directions with no delimiters; for example, esenee identifies the tile you land on if you start at the reference tile and then move one tile east, one tile southeast, one tile northeast, and one tile east.

Each time a tile is identified, it flips from white to black or from black to white. Tiles might be flipped more than once. For example, a line like esew flips a tile immediately adjacent to the reference tile, and a line like nwwswee flips the reference tile itself.

Here is a larger example:

sesenwnenenewseeswwswswwnenewsewsw
neeenesenwnwwswnenewnwwsewnenwseswesw
seswneswswsenwwnwse
nwnwneseeswswnenewneswwnewseswneseene
swweswneswnenwsewnwneneseenw
eesenwseswswnenwswnwnwsewwnwsene
sewnenenenesenwsewnenwwwse
wenwwweseeeweswwwnwwe
wsweesenenewnwwnwsenewsenwwsesesenwne
neeswseenwwswnwswswnw
nenwswwsewswnenenewsenwsenwnesesenew
enewnwewneswsewnwswenweswnenwsenwsw
sweneswneswneneenwnewenewwneswswnese
swwesenesewenwneswnwwneseswwne
enesenwswwswneneswsenwnewswseenwsese
wnwnesenesenenwwnenwsewesewsesesew
nenewswnwewswnenesenwnesewesw
eneswnwswnwsenenwnwnwwseeswneewsenese
neswnwewnwnwseenwseesewsenwsweewe
wseweeenwnesenwwwswnew

In the above example, 10 tiles are flipped once (to black), and 5 more are flipped twice (to black, then back to white). After all of these instructions have been followed, a total of 10 tiles are black.

Go through the renovation crew's list and determine which tiles they need to flip. After all of the instructions have been followed, how many tiles are left with the black side up?

In [ ]:
def clean24(s):
    dl = []
    first = ""
    for c in s:
        if c in "ns":
            first = c
            continue
        else:
            if first:
                direction = first + c    
            else:
                direction = c
            first = ""
        dl.append(direction)
        
    assert "".join(dl) == s
        
    return dl


paths = read_and_clean(24, clean24)

example = '''sesenwnenenewseeswwswswwnenewsewsw
neeenesenwnwwswnenewnwwsewnenwseswesw
seswneswswsenwwnwse
nwnwneseeswswnenewneswwnewseswneseene
swweswneswnenwsewnwneneseenw
eesenwseswswnenwswnwnwsewwnwsene
sewnenenenesenwsewnenwwwse
wenwwweseeeweswwwnwwe
wsweesenenewnwwnwsenewsenwwsesesenwne
neeswseenwwswnwswswnw
nenwswwsewswnenenewsenwsenwnesesenew
enewnwewneswsewnwswenweswnenwsenwsw
sweneswneswneneenwnewenewwneswswnese
swwesenesewenwneswnwwneseswwne
enesenwswwswneneswsenwnewswseenwsese
wnwnesenesenenwwnenwsewesewsesesew
nenewswnwewswnenesenwnesewesw
eneswnwswnwsenenwnwnwwseeswneewsenese
neswnwewnwnwseenwseesewsenwsweewe
wseweeenwnesenwwwswnew'''.split('\n')
example = [clean24(l) for l in example]
In [ ]:
# transform hex to square grid, that allows consistent directions ie. opposite directions are inverses
# Nw followed by SW results in W
#    NW NE
# W  x  E
# SW SE

hex_steps = {
    "w": (-1, 0),
    "nw": (0, 1),
    "ne": (1, 1),
    "e": (1, 0),
    "se": (0, -1),
    "sw": (-1, -1)
}

def vec_add(v1, v2):
    return v1[0] + v2[0], v1[1] + v2[1]


def walk(path, position=(0, 0)):
    for step in path:
        position = vec_add(position, hex_steps[step])
                           
    return position

def false():
    return False

def walk_paths(paths):
    tiles = {}

    for path in paths:
        tile = walk(path)
        tv = tiles.get(tile, False)
        tiles[tile] = not tv
        #print(tile, tiles[tile])
 
    return tiles

def count_black(tiles):
    tv = list(tiles.values())
    return tv.count(True)

count_black(walk_paths(paths))

--- Part Two ---

The tile floor in the lobby is meant to be a living art exhibit. Every day, the tiles are all flipped according to the following rules:

Any black tile with zero or more than 2 black tiles immediately adjacent to it is flipped to white.
Any white tile with exactly 2 black tiles immediately adjacent to it is flipped to black.

Here, tiles immediately adjacent means the six tiles directly touching the tile in question.

The rules are applied simultaneously to every tile; put another way, it is first determined which tiles need to be flipped, then they are all flipped at the same time.

In the above example, the number of black tiles that are facing up after the given number of days has passed is as follows:

Day 1: 15 Day 2: 12 Day 3: 25 Day 4: 14 Day 5: 23 Day 6: 28 Day 7: 41 Day 8: 37 Day 9: 49 Day 10: 37

Day 20: 132 Day 30: 259 Day 40: 406 Day 50: 566 Day 60: 788 Day 70: 1106 Day 80: 1373 Day 90: 1844 Day 100: 2208

After executing this process a total of 100 times, there would be 2208 black tiles facing up.

How many tiles will be black after 100 days?

In [ ]:
def count_adjacent_black(tile, tiles):
    """Count adjacent black (True) tiles according to hex tile direction map"""
    count = 0
    for d in hex_steps.values():
        if tiles.get(vec_add(tile, d), False):
            count += 1
    return count


def expand_with_white(tile, fd, tiles):
    """Ensure a black tile is surrounded by tiles, adding white if needed"""
    if tiles[tile]:
        for d in hex_steps.values():
            neigh = vec_add(tile, d)
            try:
                _ = tiles[neigh]
            except KeyError:
                fd[neigh] = False

def iterate(tiles):
    fd = {}   # need to use a separate dict to avoid modifying tiles while iterating over it.
    for tile in tiles:
        expand_with_white(tile, fd, tiles)

    tiles = {**tiles, ** fd}
    
    to_flip = []  # Must check all tiles, then flip them.  Record tiles to flip here
    for tile in tiles:
        n = count_adjacent_black(tile, tiles)
        if ((tiles[tile] and (n==0 or n>2)) or
            (not tiles[tile] and n == 2)):
            to_flip.append(tile)
            
    for tile in to_flip:
        tiles[tile] = not tiles[tile]

    return tiles
        
 
tiles = walk_paths(paths)  # Regenerate each time, because tiles is modified during run
        
for iteration in range(100):
    tiles = iterate(tiles)
    
count_black(tiles)  

The handshake used by the card and the door involves an operation that transforms a subject number. To transform a subject number, start with the value 1. Then, a number of times called the loop size, perform the following steps:

Set the value to itself multiplied by the subject number.
Set the value to the remainder after dividing the value by 20201227.

The card always uses a specific, secret loop size when it transforms a subject number. The door always uses a different, secret loop size.

The cryptographic handshake works like this:

The card transforms the subject number of 7 according to the card's secret loop size. The result is called the card's public key.
The door transforms the subject number of 7 according to the door's secret loop size. The result is called the door's public key.
The card and door use the wireless RFID signal to transmit the two public keys (your puzzle input) to the other device. Now, the card has the door's public key, and the door has the card's public key. Because you can eavesdrop on the signal, you have both public keys, but neither device's loop size.
The card transforms the subject number of the door's public key according to the card's loop size. The result is the encryption key.
The door transforms the subject number of the card's public key according to the door's loop size. The result is the same encryption key as the card calculated.

If you can use the two public keys to determine each device's loop size, you will have enough information to calculate the secret encryption key that the card and door use to communicate; this would let you send the unlock command directly to the door!

For example, suppose you know that the card's public key is 5764801. With a little trial and error, you can work out that the card's loop size must be 8, because transforming the initial subject number of 7 with a loop size of 8 produces 5764801.

Then, suppose you know that the door's public key is 17807724. By the same process, you can determine that the door's loop size is 11, because transforming the initial subject number of 7 with a loop size of 11 produces 17807724.

At this point, you can use either device's loop size with the other device's public key to calculate the encryption key. Transforming the subject number of 17807724 (the door's public key) with a loop size of 8 (the card's loop size) produces the encryption key, 14897079. (Transforming the subject number of 5764801 (the card's public key) with a loop size of 11 (the door's loop size) produces the same encryption key: 14897079.)

What encryption key is the handshake trying to establish?

In [ ]:
k = (11562782,
18108497,
5764801,
17807724,     
     
    )

def transform1(subject, value=1):
    value = value * subject
    value = value % 20201227
    return value

if False:
    subject = 7
    value = 1
    for i in range(20_000_000):
        value = transform1(subject, value)
        if value in k:
            print(i, value)
  
def transform(subject, loopsize):
    value = 1
    for i in range(loopsize + 1):
        value = transform1(subject, value)
    
    return value
# Loopsize, value
# 17580933 11562782
# 19976407 18108497
transform(18108497, 17580933)