Tag: Python

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 8 of Advent of Code, titled Handheld Halting.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 8 challenge.

The Day 8 challenge, part one

The challenge

Here’s the text from part one of the challenge:

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?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into a Jupyter Notebook running a Python kernel.

This involves pasting it into a triple-quoted string and then assigning its value to the variable main_raw_input:

main_raw_input = """acc +37
acc -4
nop +405
jmp +276
acc +39
acc +40
acc -3
jmp +231
acc +44
acc +12
jmp +505
acc +35
jmp +282
acc +23
jmp +598
nop +392
acc +18
acc +44
acc +18
jmp +297
nop +460
jmp +152
nop +541
acc +33
jmp -11
acc -5
acc +9
jmp +327
acc +30
acc -1
acc -3
jmp +50
acc +22
acc +18
acc +33
acc +37
jmp +57
acc -17
acc -6
acc -2
jmp +535
acc -15
jmp +279
acc +34
acc +44
acc +41
jmp +349
acc +2
acc +6
nop +351
nop +252
jmp +505
jmp +1
jmp +1
nop +61
jmp +524
nop +351
jmp +399
acc +1
nop +397
acc +39
nop +141
jmp +134
acc +46
acc +14
acc +26
jmp +236
acc +7
acc -6
acc +35
jmp +397
acc +15
jmp +140
acc +3
acc -4
acc +37
acc +12
jmp +86
jmp +416
jmp +1
jmp +55
acc -19
jmp +536
jmp +1
acc -11
acc +15
jmp -61
acc +25
jmp -25
acc +50
acc +43
jmp +1
jmp +140
acc +46
nop -53
acc +1
nop +440
jmp +488
jmp +396
nop +443
acc +41
jmp +168
acc +25
nop +383
acc +12
acc -19
jmp +21
acc +29
acc +30
jmp +497
jmp +502
jmp +417
nop +351
acc -15
jmp +243
acc +21
acc +16
jmp +332
acc +28
acc +22
acc +38
jmp +476
acc +8
acc -11
jmp +458
acc +9
jmp +246
acc +40
acc +31
acc +26
jmp +218
acc +27
acc +9
nop +347
jmp +478
nop +28
nop +106
acc +25
acc -15
jmp +397
acc +31
jmp +231
acc -4
nop +136
acc +14
jmp +181
jmp +361
acc +16
acc +11
jmp -108
nop +299
acc +21
acc -2
jmp -106
jmp +246
acc +31
jmp +407
jmp +377
acc +43
acc -12
nop +142
acc +8
jmp -91
jmp +1
acc +34
acc +5
acc +31
jmp +12
acc +34
acc +7
acc +34
acc +20
jmp -45
acc -11
acc +41
acc +10
jmp +310
nop -106
jmp -36
acc +23
acc +46
acc +46
jmp +112
acc +41
nop +179
acc +17
nop +356
jmp +147
acc +42
nop +49
jmp +119
acc +0
acc +7
acc -18
acc -8
jmp +11
acc +12
acc +38
acc +39
jmp +281
nop +186
jmp +162
acc +44
acc +20
jmp +153
jmp +395
acc +49
jmp +1
acc +2
jmp +1
jmp -31
jmp +301
nop +97
jmp -102
jmp +262
acc +28
acc -15
acc +44
acc -13
jmp +191
jmp +281
acc +36
acc +1
nop +15
jmp +211
acc +6
acc -4
jmp +42
acc +34
acc +0
jmp +104
jmp +311
jmp +84
acc +43
acc -8
acc -10
acc +38
jmp -90
acc +49
jmp +303
nop +132
jmp +301
nop +60
acc +37
nop +96
jmp +182
acc +16
acc +18
nop +152
acc +19
jmp +325
jmp -63
acc +28
jmp +56
acc +18
acc +29
acc +33
jmp -115
acc +47
acc +19
jmp +1
nop +41
jmp +1
jmp -207
nop -62
acc -9
acc +42
acc -12
jmp -56
acc +28
jmp -163
acc +25
acc +17
jmp -217
acc +7
jmp +272
acc +43
acc +22
jmp +70
acc -17
jmp -117
acc +24
acc +26
nop -275
jmp -46
nop +87
acc +19
acc +28
jmp -34
acc +4
acc +9
acc +6
jmp +1
jmp +28
acc -6
nop -67
acc -10
jmp +271
acc +40
acc +25
acc -4
jmp -63
acc +46
jmp +78
acc +41
nop -126
nop +70
jmp +1
jmp +172
nop +270
jmp +30
jmp +1
acc +38
nop +68
acc +29
jmp +253
acc -18
jmp -89
acc +18
acc +30
jmp +147
acc +24
acc +11
acc +50
jmp -225
jmp -210
acc -18
acc +1
acc +38
jmp +1
jmp -79
acc +45
acc +12
jmp +209
jmp -207
acc +32
acc +4
acc +32
acc +14
jmp +83
acc +13
acc +1
acc +46
acc +38
jmp +28
nop +153
acc -17
jmp -73
acc +11
jmp +248
acc +29
acc +45
acc +16
jmp +96
jmp -273
acc +34
jmp +87
nop +99
acc -3
jmp -74
acc +12
nop -119
jmp -141
acc -18
nop -79
acc +1
acc +6
jmp +9
acc +3
acc +44
acc +39
jmp -165
acc +6
jmp +44
acc +25
jmp -133
acc +0
jmp +14
jmp +1
acc +1
jmp -223
jmp +71
nop -1
acc +22
acc +11
jmp -274
jmp -330
acc +45
jmp +1
acc +15
jmp -158
jmp -128
acc +50
acc +26
jmp -73
nop +99
jmp +71
acc +35
acc +7
jmp +192
acc +13
jmp +190
acc +4
acc -1
acc +40
acc -15
jmp +50
acc +29
jmp -337
jmp -75
acc +41
jmp +1
jmp -387
acc +28
acc +18
acc +19
jmp -62
nop -196
jmp -410
jmp +1
acc -17
jmp -267
acc +22
jmp -301
nop -98
acc -15
jmp -124
acc +45
acc -18
acc +15
acc +42
jmp -296
nop -10
acc +29
jmp -371
acc +3
jmp +1
nop +61
acc +5
jmp -361
acc -5
nop -326
jmp -379
acc -10
jmp +1
acc +44
jmp -231
acc +3
jmp -94
acc +1
jmp +113
jmp -336
acc +4
jmp -299
acc -13
jmp +1
acc +13
jmp +143
acc -11
acc -19
acc +18
nop -390
jmp -27
acc +42
jmp -232
acc +15
jmp -228
acc +21
acc +39
acc +47
acc +6
jmp +57
acc +28
acc +27
acc +50
jmp -397
acc +12
jmp -445
acc +30
jmp -352
acc -4
acc +26
acc +48
jmp +1
jmp -205
jmp +22
nop -284
acc -1
nop -361
acc +0
jmp -368
acc -17
nop -223
jmp -41
acc +4
acc +46
jmp +79
jmp -370
jmp -260
acc +42
jmp -14
acc +30
acc +50
acc +13
jmp -61
acc +46
jmp -63
nop -55
nop -320
jmp -11
acc +10
jmp -424
jmp -11
acc +3
jmp -71
acc +42
acc -13
jmp +4
nop -155
nop -138
jmp +62
acc +11
acc +19
acc +15
acc +17
jmp -73
acc -11
jmp -273
acc +8
acc +6
acc -7
acc +41
jmp -311
jmp -111
jmp -260
jmp +50
jmp -60
jmp +1
nop -89
acc +36
acc +14
jmp -220
nop -415
acc +28
jmp -402
acc +41
jmp -165
acc +9
acc -13
acc -18
acc +18
jmp -504
acc -9
acc +29
acc +44
jmp -444
acc +5
acc +47
jmp -545
acc +23
acc +7
nop -240
jmp -320
jmp -141
jmp +1
acc +28
nop -287
jmp -118
acc +44
acc -7
jmp -550
acc +10
acc +20
acc -3
jmp -401
acc +45
acc +36
jmp -375
jmp -485
acc +9
jmp -338
jmp -510
jmp -196
acc -16
jmp -372
acc +0
jmp -380
acc -3
nop -473
nop -361
jmp -311
acc +0
nop +20
jmp -436
acc +9
jmp +1
jmp -215
acc +19
jmp -451
jmp -43
acc -13
acc -10
acc -5
jmp -208
acc -11
jmp -156
acc +11
acc -2
nop -357
jmp -73
acc +21
jmp -159
acc +28
acc -16
acc +12
acc +1
jmp -282
jmp -131
acc -11
acc +45
acc +0
acc +28
jmp +1"""

Building the data structure

With the data imported, the next step was to build an appropriate data structure. Since today’s puzzle was based on simplified microprocessor instructions, I thought that the data structure should do the same.

I wanted my data structure to look like the table below, which shows the instructions from extracted from the first five lines of the data given to me:

Index	Opcode	Operand
0	acc	37
1	acc	-4
2	nop	405
3	jmp	276
4	acc	39

Here’s the function that I wrote to convert the input data into the data structure:

def input_to_instructions(input_data):
    instructions = []
    
    split_input = input_data.splitlines()
    
    for item in split_input:
        instruction = {}
        opcode_operand = item.split()
        instruction["opcode"] = opcode_operand[0]
        instruction["operand"] = int(opcode_operand[1])
        instructions.append(instruction)
        
    return instructions

With the function defined, here’s how I used it to create the data structure, which I assigned to a variable named instructions:

>>> instructions = input_to_instructions(main_raw_input)
>>> print (instructions)

[{'opcode': 'acc', 'operand': 37},
 {'opcode': 'acc', 'operand': -4},
 {'opcode': 'nop', 'operand': 405},
 {'opcode': 'jmp', 'operand': 276},
 {'opcode': 'acc', 'operand': 39},

...

]

I then wrote accumulator_value_at_first_repeat(), the function that would use the data structure contained within instructions to solve the first challenge:

def accumulator_value_at_first_repeat(instructions):
    program_length = len(instructions)
    program_counter = 0
    accumulator = 0
    executed_instructions = set()
    repeat_instruction_encountered = False
    
    while 0 <= program_counter < program_length:
        current_instruction = instructions[program_counter]
        
        if program_counter in executed_instructions:
            repeat_instruction_encountered = True
            break
        else:
            executed_instructions.add(program_counter)
            
        if current_instruction["opcode"] == "jmp":
            program_counter += current_instruction["operand"]
            continue
        elif current_instruction["opcode"] == "acc":
            accumulator += current_instruction["operand"]
        elif current_instruction["opcode"] == "nop":
            pass
        else:
            print("Something went wrong in accumulator_value_at_first_repeated_instruction().")
            print(f"pc = {program_counter} acc = {accumulator}")
            print(f"instruction:\n{instruction}")
            
        program_counter += 1
    
    if repeat_instruction_encountered:
        print(f"The accumulator's contents at the first repeated instruction is: {accumulator}.")
    else:
        print("Reached end of instructions without repeating any of them.")

When run, it sets up the following variables:

• program_length: The number of instructions in the data structure.
• program_counter: The program’s equivalent of the “program counter (PC)” register in a microprocessor; contains the index the instruction to be executed.
• accumulator: The program’s equivalent of an accumulator in a microprocessor. For those of you who aren’t familiar with what happens at the microprocessor level, think of the accumulator as a “scratchpad” variable where you do all the math.
• executed_instructions: A set (which means that every value in it is unique) of the indices of all the instructions that have already been executed. We use it to determine if a given instruction has already been run, at which point we should stop the program and see what the value in the accumulator is.
• repeat_instruction_encountered: A flag that should be set to True when an instruction is about to be executed a second time.

The function’s main loop performs a greatly simplified version of a microprocessor’s “fetch-decode-execute” cycle:

1. Fetch the current instruction, which is the one whose index is specified by program_counter.
2. See if the instruction has been executed before. If this is the case, exit the loop; otherwise, recording this instruction as having been executed.
3. Decode the current instruction:
   • If the instruction is jmp, add the operand value to program_counter and go back to the start of the loop.
   • If the instruction is acc, add the operand value to accumulator.
   • If the instruction is nop, do nothing.
   • If the instruction is anything else, display an error message.
4. After the loop is done, if the repeat_instruction_encountered flag is set, we’ve found the value we’re looking for — display it! Otherwise, display a message saying that we’ve reached the end of the instructions without ever repeating one.

I ran the function…

>>> accumulator_value_at_first_repeat(instructions)

The accumulator's contents at the first repeated instruction is: 1801.

…and got my result: 1801.

The Day 8 challenge, part two

The challenge

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?

Here’s the function I wrote to solve this challenge:

def accumulator_value_and_halt_at_first_repeat(instructions, switch_opcode_address=-1):
    program_length = len(instructions)
    program_counter = 0
    accumulator = 0
    executed_instructions = set()
    
    while 0 <= program_counter < program_length:
        current_instruction = instructions[program_counter]
        
        if program_counter in executed_instructions:
            return {
                "halted": False,
                "program_counter": program_counter,
                "accumulator": accumulator
            }
        else:
            executed_instructions.add(program_counter)
            
        opcode = current_instruction["opcode"]
        operand = current_instruction["operand"]
            
        if program_counter == switch_opcode_address:
            print(f"Changing opcode at address {program_counter}")
            if opcode == "jmp":
                print("- Changing jmp to nop")
                opcode = "nop"
            elif opcode == "nop":
                print("- Changing nop to jmp")
                opcode = "jmp"
            
        if opcode == "jmp":
            program_counter += operand
            continue
        elif opcode == "acc":
            accumulator += operand
        elif opcode == "nop":
            pass
        else:
            print("Something went wrong in accumulator_value_at_first_repeated_instruction().")
            print(f"pc = {program_counter} acc = {accumulator}")
            print(f"instruction:\n{instruction}")
            
        program_counter += 1
            
    return {
                "halted": True,
                "program_counter": program_counter,
                "accumulator": accumulator
            }

The function, accumulator_value_and_halt_at_first_repeat(), is an expanded version of the function from part one, accumulator_value_at_first_repeat().

In addition to a set of instructions, it takes an additional parameter: the address of an instruction that should be changed — either from jmp to nop, or from nop to jmp.

The function still performs the “fetch-decode-execute” loop, and it exits the loop if it’s about to execute an instruction that’s already been executed. The main difference is that if the current instruction is the one flagged for change, it changes the instruction appropriately.

I wrote the accumulator_value_and_halt_at_first_repeat() function to be used by the function below:

def run_instructions_with_mods(program):
    
    for index in range(len(program)):
        instruction = program[index]
        if instruction["opcode"] != "acc":
            print(f"Found jmp or nop at address: {index}")
            result = accumulator_value_and_halt_at_first_repeat(program, index)
            if result["halted"]:
                print(f"Found it! {result}")
                break
            else:
                print(f"Not the correct instruction.")

This function goes through all the instructions in the set, looking for any jmp or nop instructions. When it finds one, it runs the program using accumulator_value_and_halt_at_first_repeat(), marking the jmp or nop instruction as the one to be changed.

This lets us modify the program, one jmp or nop instruction at a time, in order to find which change to a jmp or nop instruction is the one that allows the program to reach the end of the instructions.

Here’s an abridged version of what happened when I ran the function:

>>> run_instructions_with_mods(instructions)

Found jmp or nop at address: 2
Changing opcode at address 2
- Changing nop to jmp
Not the correct instruction.
Found jmp or nop at address: 3
Changing opcode at address 3
- Changing jmp to nop
Not the correct instruction.
Found jmp or nop at address: 7
Not the correct instruction.
Found jmp or nop at address: 10
Changing opcode at address 10
- Changing jmp to nop
Not the correct instruction.

...


Found jmp or nop at address: 207
Changing opcode at address 207
- Changing jmp to nop
Not the correct instruction.
Found jmp or nop at address: 209
Changing opcode at address 209
- Changing jmp to nop
Not the correct instruction.
Found jmp or nop at address: 210
Changing opcode at address 210
- Changing jmp to nop
Found it! {'halted': True, 'program_counter': 623, 'accumulator': 2060}

I entered 2060 as my answer, and step two was complete.

Solutions for other days in Advent of Code 2020

• Day 1: Report Repair
• Day 2: Password Philosophy
• Day 3: Toboggan Trajectory
• Day 4: Passport Processing
• Day 5: Binary Boarding
• Day 6: Custom Customs
• Day 7: Handy Haversacks

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 6 of Advent of Code, titled Custom Customs.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 6 challenge.

The Day 6 challenge, part one

The challenge

Here’s the text from part one of the challenge:

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?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into a Jupyter Notebook running a Python kernel.

This involves pasting it into a triple-quoted string and assigning it to the variable raw_input, and then splitting it using two newline characters in a row as a delimiter, producing a list named split_input:

raw_input = """wdcmlzfnugqtvjbsahi
easrkmocxbpjgi

xrpnegqlcsyodhjfutzakmiwvb
mgilapxjtrndbheyqzckfouwsv

scynhfozmlvbqkarwj
qhvjkmbyxcfonlazdw
vjhzfnapwclkqiomyb

bpourq
ujpmoqs
obqup

v
v
v
v
v

hwjlda
thkdjo
mlhdjw
edyfjvh
djh

xvjadplfcwmkeriug
adgtscyjipewvulr

hmkipduz
mdzkupi

vtyizwcdm
zdvtcyiwm
mfzcywvtid
iydclntzvmw

ps
pm
pm
p
pm

nglatdiw
twialgd
igsadtwl
iadgtwl
igawltd

jqoxkavs
askoxvqj
aqjvxskho
javqkxso
kaxjoqsv

ltkjfoxes
aifogkepx
ufcekybmzx
tigxeahnkf

xzfqbsnhmrviju
rmfvsbihpujq
hstfumvgrobijq

bga
ye

sg
gs
sg
gs
sg

knipbjmtrqoawe
rtaebqkmopjiwn
ewbuqcaijonmrpk
trnmpeqkobjiwa

puifme
ufb
fvp
rntzlyxwokfcg

nufjzpyawbqsdgi
ogcmpsdqaxvnzwetklh

qmdxnfrjobatzwgcyse
rdxtqseawzobygcmfjn

dbot
dwetlp
odtr

utbqx
bxuqt
xtbqu
quxbit

rvthuiqbljzaofgwy
ldftrsjvwoiayzuekcg
dtxmalyuifznvprkcwgoj

twc
w
pwg

rmzaoylipcwkvuqesbhn
kpuvhqlwyrabmszecnoi
cwaylknbrhvzmiupseqo
qlwiyczkevsnarhbpumo

cgr
grch
cgsr
rgce

eso
ose
soe

swimuzq
zqwsmliu
iqzurwsmh
iswqzum
wzhumsqi

amolqcs
sqoayj
sjazqxyo
aqhxsot
ozsajqkx

qbkyhzfspewgrtlv
pyeqtcbskf
jxbsonqtaykpef
tqskfmyboeup
bdjtfqypokse

yrtwqacluozbg
vwtfgzmcqobraj
opctryzqawbg

v
v
v
nv

dclgejbqrwtkvsxfa
ovgkhjyiqwbmefc

vpkx
jmydw
fxa
xa

gwtocmzslfqk
olkgwzcftsmq
ogmsfzlwqckt

uwxdl
wdux
oxuwdt
dxwu

ab
smej
t

iwhlqdermv
menrvqd
jemdqvr

n
n
a
n

jqcvetapkbsyu
twndyfrixzhvmsogu

xsz
zxs
zxs
szx
sxz

fsatbzpvqjknlrm
pbnljkratfzvsmq
qtrasmjnlkfvbpz
bsjavlmpqktrnzf
qajlbkzvmtsnfrp

utlchvariswzqjmx
almujswrcthzvfqix

p
j
p
n

cgsxwk
uwkcxj
xpwethnkcyb

gywc
wcgy
ctyugw
gwcy
wgyc

afmtuw
muatfw

ujwmnirvkdygtqcabh
takwqdjgzcuivrhnom
cawvrnxfjmghdtkiuq

srgt
ma

urnymxabthi
rtxnailuqvoyph
duytknrwiehaxz
rhaumscngtyix

gawbhtkqruyjel
rlcqbuhawkmyfgjte
jhbyqgkraetwlou
gxbtrnadlejwhyquks
ujfkleagybrtwhq

dctkngohsxaljfrbvmey
mlbvxaksifyneodgjctrh
lmkfobtyxngsjvrdahec
srkyveohxfmcjdlbtnag
lbguestydkjxfopnvmhcar

pjrhgzdwcmxq
cgwhmqpjdrxz

meipjv
mivpje
jevmip
peimjv
vmpeji

zkcavufyr
fyzuarckv
fvnacqgksry
yvcrfak
crfvyka

pqynikfxd
dynxqlifpk

laozucfdek
kpeauocdlz
uoldfsekzac
dmekaclyhnuzo

hwubponvt
vwytnphobu
vpnbgtwuoh
wpouhvbtn

wcxlspod
fmedwbtjops
pwnoscid

ufenjp
ngfxpe
njbpfc
vqnthfazdp
pmfjng

qrphaykit
qkysrta
jbwdtqrxzav

wjqfz
jqfaz

meuxikpsdw
kjimpsdwxu
dmxpwikujs

fjbsnmcgxz
bpfimjnzduh

urtkjpo
cthod

voclmdguaw
oczdlntgmeir

zipf
fipz

nbwcexytjzripskmo
kwpzrmtxiosejcb
tsrcoebzpiwjmxk

jafcwtsukrodynhvqge
pubrlchazvetosyigqjdk

qminshlycutrdwx
vigzpqbmunacrjftokl

hweisfpycjdzouvmbnkq
nqjxscbvmuwhzfakdo

qtndfjcglrkoyux
jqtrlgfkducxnomy
tqnrjxckgfaupdoly

pbe
b

n
n
n
n
n

nsc
ns
nse

qzkxif
vkfqizx
kfzqix
zixkfq
ifzxkq

nvshwafe
vbewacnh
nvwmeah

ziafwxcnmebko
cdfrxmk
fkmpxc

y
y
y
y
y

yauxbwtcvgoq
ywcvotagxbqiu
gqwyvbacouxtn
uobqrcgwtvayx
qcgwoytbxuav

r
nr
a
r

xjrkwdnbyuscfgqtphiov
brshqnjcoukxitvywfdpg
vrxlptbcyfdwhgkouqijns

fqcvwudyiotjblzpxshgnmkrae
ouhrqwtgnjeyxiamfzpdscbkl

lnch
nhclmg
ldhzcny

uzfeomrwi
ydgkhjbx
qcylp

hagpbecorwyvfdz
rstplobhmfnxvykdewc
hfruowdvyjgbpzce

rgdiznuxa
dragzniue
jzysdgpuvkowqin
lugrndiz
nbdcfugzi

eqponlctfbwgk
kyjniulbegpdchtwoaq
onczetbplkwqg

thevzsrc
zcewrsv
vczueosky
wmzlcsve

sxeqojwkarhyutcdnzp
rjnuwzxpmeysdoctlaq
pzqxeratsdnkuovcwjy

qexjbo
cqunbaprhwyjfe
ilvegkbszdt
efbmqj

wm
wm
hm
wm
m

texosjaiycpqn
mntxspgikeldwycjarq
nysqtaceipjux
phiqznsyxjcvoabet
neqytxcuipsajvf

z
nozy

ydfcsvgbikjphamr
wskfdahgpvmrcjby
kpsirchfmjavbdgy
pslxjrugtzydaokemvbcfqh

t
pyt

fu
fu
d
yj
fnl

qxkevrhpna
kmvyorduqe

sfnmyevqwka
fvmyieawqks
kvfhmctdqjaslywe
ywfkvqeanms
kufwyqmaesvh

ulvtwepimynb
ehmpnylubtvwi
wplevtunmyib
lpbwnvtuyeim
unvpbgtjiaylmcwes

zfxkceynsu
xdfzysnuie
efzgxunsy
nzydesxfu

jneurlkfzxbq
xekznblfurqj
rbzljfkqnxeu
zueknrbxjfylq
xzferlbjqnku

tr
f
egtr
jmu
s

aeq
qae
eqa
aeq

bsgjrilayoezwndvtq
giadlcryjwobhznqesvft

guxfyzespj
zusejpfgxy
zxygjuefps

xvmlgpzjdrubqa
jfmbdvzeyrlup
ruzchykmbpwdvloj
vhmuebldrjzpo
bhvcmrypulzjiwds

cfsjzamyhtoxq
xoysjqfzmhtac
qocxatmfshjzy

vdhsifmynta
nsmfhdtya
tsnfhamdy
dafyqtsnmh

rfybkqmh
qoumrd

l
y
l
y
w

vlmerz
mlvrze
zvrmle
zelrvm
mzlrve

rnb
gdcb

pbtergc
tecfjgr

ogzsajwvdiplrtxbhfcnky
btjzlswhikyofgcpvrnda
tbwinagrhfyscvlejkdop
dakhrbipqglmovjyncswtf
bhyljrdpsktgfiancwov

qolmnyvhtwe
uwkecxshldmoy
zwblsockyumh
miywfgjhaopr

u
u
q

zdxynqmev
bdexmzyiqcn

bwtqagf
tnmwfaqbj

p
p
p
p
p

yjgicnxerbsu
xpzfqirsjh
exswmarikbj
mjxgrsi

tvzkbxugmcnshproiw
czxtirownbmpksuvgh
cnofirbgmhzuspvtxwk
gmctsrohkxwzupvbni
vsgbzcmktxihonwupr

dyaoim
aiom
ozimual
oxaim
biyotma

saliju
evzhxcobk
lj

txhebw
etwhbx
uhwxtbe

eyaixfrdhoqksc
eakiqsrocxyhd

vkr
kvr
kvr

surjoh
ubh
ubmahe
uh

vhkcawrno
vowahrnkc
oknarvwhc
cnkhvwoar
wvhkanrco

ntpfemsvialxgrwqzc
kcwegrtispxnyd
phstgwixebnucr
xpwjtenscoigr

sfanq
xgtzfrn
ulfinpkv

kdwnyjuzctiqpgf
ngtcrjipqfyh
ypfvcqntirgjh

urmtsh
svihtu
utmph
juthydwafcqx
uthve

sk
ks
sk

zxbvcrgyqfjtoeiudwpkhsm
igkswrpohqudcfjxzmvytb
cpatkzfuoyqgvrsmibhxjdw

kvgumiabnoh
bvaiomgnukhc
mkhnvusbagio
hamiobunkgv
umsgovkahbin

yrceuq
rmdbpa
nkvxjslwg

lkt
fl
vil

whn
hn
hn

gvebcszypdlkqm
zcyhdlpqgsvke
cdzbylqkpsuveg
pzsyxlgdaiofcqwvek
gmcpvyqzeskld

ryzfspdtbwxiomhkjnlu
tqihvployrmksbunzfwc

dualjxigyrzb
durysxjlgzaib
srgxulazbjyid
lrgaubjydzxi
azritbxdpljyg

cfahxspjelitdnobuvqywk
vwmkoxulnypfiatgjbhrcsq

f
f
f
f
f

grbmahpise
mbireyxhalgs

bcrkvuwqt
trubckq
rbuqtkc
trkbcuq
rubtqkc

zxpbejmvhrutwlkq
gtvrzphoqcbnmju
pjazbvqurgmysht
fhsptiumrvjqbz

kpszjieflb
blsijkefzp
zksjiefpbgl
ilbzrksajpfe
sglzbepfjik

nxwohsipd
zitjrlvfgsoym
bqsiopuc
aoisd

wj
j
fzpglynjeu
jk
ikj

abzftcqvgsrnexpmho
pxvlybndrtqimzhosacgef
nocqfzerjaubxthgmwspv

psauzryot
vmdhbwe
lfc
gsri
sqya

lkjudnqterhyscgx
eckqhlxybrngudstj
wotecvlyrpgqmijxkhsd

htpc
caph
hpustjc
nyhcedmgp

ezaljkfpiyvroud
hbiwxfstmldkecnvpgqo

kiqvzyjrthmblu
ahszlduemxcij

wirunkh
hwqdknyirul
kxwuhirn
hkirwnu
ierwunkh

vcgno
snmicvo
ncomjisv
coynuv
lconfdvpz

tgqkhowsyfbzpcur
zcqsugtwhrpfy
fgydqpcjswrlzeuth
thgpcfyzqeursw

rwpci
cipwr

ptrlaqebo
pebtlaqor
qboxepatr
epbartoq

fypd
dpyf
ypfd
fdpy

c
c
c
d
c

gxysqiamkpc
mpiacyqxkgs

mvqbskuzefy
zcsqebma
ztbnlhe

snx
xsn
nkxs
snx

joyblxztkswmvnec
gdcrhykmfseqapibzu

oqzmprikt
fhlgxucda

ygrjkfazu
kjiagrzyfu

btg
o
v
oc

bnqyz
ebdfls

vjhocqkamygbplu
dbwsyefuxzntijrc

kmlb
kqsbl

vhjsdxrfpokyznibwgtmu
syvkmzfjgpdwixrnbutoh
uzbjgvhdkpynmtfoxsrlwi
jpkxwvyrgftzioubhsmnd
ykjmzvsqnhxwgbrutoipdf

hwby
yvbmhl
echgiyabjpf
krbouyh
hrynotb

tobipzwfxy
pfxwytizob
hsfwzpbotiyax

znrgilpcfse
seinczlpgrf
nircgepszfl
rcegzsiflpn
lzgrcpensfi

tupvbxcgfnmh
fpqntvibgxhmc
npbtvxghfm
tvxfhmbnipg
rnvxmhfjgpbt

inysghdka
wbc

noktsjqvmzxheplrcfgiuwda
dlogmasfzwhupjrkcntixqev

zhwfbs
bzcwh

igqkpctmafr
jietalnfksqp

ewlanjvgdbpm
lpjangwvem
vpngjwmeal
glvwnpejam
enlgwjmvpa

niocufzwrk
kirmuzfocvw

juqervaxni
cudjqavnix
iuvjndcaxq
xvniqajugd
vxunjiaq

lmayozkep
koazylep
aeykzlop

ejgotzhrxbsnqimu
lrspkgobcaywmjfvhd

uazxfrony
uoaxynzrf
yunaorxfz

lowmgiuxpnakzsq
qwaomukglnx
ubgkoyqanwlvmx
lowaqgyxunkhm

alfoj
floj

yglkurfahidmoxtvz
muykfdrzivlothga
devylsarcupgoihkmftz
rmtgkalydnhvozubfi
ahrzqodkgxyuitvmfl

gmdoshlaixnc
xhmicdgosanl
hiqgvbulakdmoxcpn
hoiamdsngcxtl

egnprq
ash

oabx
abxfo

vomitazdbflqhkue
lvemipubdafohztkq
dkabtiylqgzuovehmf

euanfbq
skufxtami
nefauc

fadpbjxvzeghqkriy
xpaqfzjvybdhrkieg
jeqghzxrdyvakpfbwi
ygvakzbdpqrxjfeiht

dhvmgjoqzknbwyl
hvnlobmydwzqkjg
vbzljhdqgnmwoyk

s
k
sk
d

svzubcigpeqdthfmxnj
djogszbcnvefqthiuxmp

vgkpjwymduqfxcztoasne
swgapuymcvqnjodtkfzxe

stgv
yvbts
iokqv

h
h
h
ujxw

uz
uz
uz

cdh
lhg
mkh
quroafxhipsev

d
d
dg

lbrsefwhxagdmpqjiocuvyn
uobfgnhvsqwzlkjyraicdpm

uwnvthio

yudxpkhrngb
selctamwozqvf

ueiypcnoa
nidaehvt
akencir

ozcru
uoflar
pwoxuyvm

nrgaujbldiwxvq
sdvuirgaynbj

synqkzdlpebticorvwxmaug
ekyatuvbpohmxnfdgczirwql
ztvwupairdeqmckgbnylxo
alngerwtckpvmioxbduzyq

dqygzrkuowejsm
zyikwtjsver
yzjrsvawceik

lqduw
iudw
wdrue

zxnrflac
lx
lvx
otlwkx
wxyl

q
q
q
q
q

aigmyqxscvhde
csegmkqdnvyahix
gvqixcdheysam
dsmyaexgivqhc
shiqmxgdeycva

nbmovulhpai
yfcobuiaetpdvmln
mnopuvlbia
wviopnmluabk
uvamohipklnb

cibznrjtsgoafdlkx
cethszlarinx
xcsztairehnlp
szhnatlxicr
mpselnxatyzric

qxdzauyvbc
qxzvabdcuy
zyxabucqsdv

uzxvatmprofyjcliwgbdsqnek
kynesjvmoifucbpqwxlzrdtga

mepouwaj
cutjoxvpa
apojcvftd
opwdaj
njhzgqrikyapslo

efqisyl
elfqsiy
sfiqley

if
wvzghe
xn
dnxu

afuolgsxdckypbenqjhmr
euqojgbfzphxmnrysda
xsbwrdmnfqyphaegjuo
xsfuhpgnbjmwqoaeryd

xjyizvdsbkfmhenwop
mueiojtyqnag

bjlvkzugwqspcihmxr
mlugrxwjqsvibczhkp
vikuscpzwqhmgjxrbl
pxzbksqmjlcgihurvw

payfmlnhgtzsrxke
yeknlfshmrgztx

p
p
p
p

gnmcwdtquesz
ztdscnkg
zdancosjgt
cdntzsg
zcjgbpstrnd

ugxawjehznr
gujxqzrwhnea
rewagunjzhx

krvmqtuiwsezbjcdhployaxngf
xkwsubhjlfvparcgomyenidzqt

jrglbkzcwtuayno
iwydqmzt
tdwfeyz

jnvchaxzotqd
jdaohpexnt

yifrdlua
asridu

rchuily
brliyc
icyl
nclfjxiytvs
hiycrl

fj
fj
jf
jf

hncwvidj
ncijh
qjhrin
zsxiheynj
jvihaqnc

zkraj
zkjrl
akjzr
zsvjrk

culpozwn
copkslvruwt
fhwlecupo

cuibdzoagynvrkw
dobjkzuxvrcyinag
ipsduzkvybnoacrmeqg

gjwfeblzasoirpvhcqtxu
dcfqurpiaxslgjhbyzwmeno

agi
sa
vuhaksj
zatyex

xponks
ojnkpsx

cqeiyuforpx
bxfnzrs
xhfnvdr
rfx

tqowdj
dw
diwfu
dfewgi
wd

dyvjwabnuzgx
bjdyglxvzonw
dxbwnyvagjz
zyiwdcgrbjexvn
xjngvztwbdy

ob
ob
bo
ob

cp
cp
cg

cnwlshdkyboxmpvtz
ndswvmyzjeuprbgchl
ayzkbswhlnfptcvdqm

cmfyketonuixwdgpav
xeyngtvuwfcdik
xdufiwcnekvtgy
zuvyixgbsdhwnjkelcf
xwdfvucyinekgr

vwznkidlhxuaosfr
rhakozvwgfisdunl
korahvzwdsyilnuf
fhniwvurokxszald

rlhewm
whpr
wraqfh

szpvechrdnybfjmog
vgptfyjmbdcxzshe
zhsfqepvtygnbjmdc
yzhjalgcusdpfbmveik

xapwbucizkl
qgs
yoehs
jrsge
vjgdtm

vxyuftcbpl
uycftxlbpv
vtxflpbycu
pbcxfvtlyu
xylavcftupb

yhbadxqs
hqdxsay
zphxtaqsd
asdoeqxhfnj

tlmrid
osmrjwlvge

hfprkgzljcs
slghpczfjrk
flcjzshpgrk
hzfcjsgklpr
rgphlfjkzcs

jizfvmyocxq
kogmzyjiqv
ujnqwpaszvhymro
gxomvzjcqy

ie
ie
piec
ei

tvaxzm
txamv

puqcatmbe
bcuqto
ubsiqhzgc

vkqogu
oqfhigvudm
voqubg

zlfapsjxtm
umalzjpfosxt
jplsftaxzm
tafzxlpqsbjm

zicyojr
ilzcyr
hzcrtleyvipf
zicypr
yicezur

ehigkrowmvjylnxb
tihkwoxbjelnmrvy
nkjbmxwhoelrviy
vnojlkwxrmhbeiy
lvkhxnowmjeyrib

bpzgcrtoisywvned
acdwbrytesguv

b
qb
ba
bh
b

hntmvbilk
tnmbzvl
vbfnmt
yvnomuxbtw

ib
ib
lib

jefqbsd
iyhzrvcngl

zaeqfuhynlbxipwvgotkd
kagozfcnbirmpuesywdv

wfulhibnvtapkyrq
ibleqfykavprunmxwth
raulpqfwbhvintyk
vnwrklhufytbapiq
bknqpvrytfuhlwai

wtgqajfmk
mwbfcjukqga
fmghkjwaq
gfawqmjk
fjwmkgaq

lxk
t
w
w
mf

mnzbcw
rad
ejpxykvhu
zslo

fatkelbspwjyhoqrdui
qsngucrzamvx

ldwhapn
wnma
awn
wnau
naw

fnrgykvulp
vyrlupngk
kynprgualvq

oz
oz
oz
zo

dehqmlkfyxpvujagbtcwio
huapickwemyblxodftjvgq
pagblyvnjotwekuhcfxiqm
qjythibopgxaeckmwvluf

huclkitbnrad
uhdoictnrklba
tlcbauhdinrk

pamdyrxtj
pktnmarybxjd

tr
drt
rkt
tor
rt

gjrclwxyuk
isqmdbf
eoivmdfpt

qvg
i
ui

j
l
u
lu
osd

zmdknlf
nzlfmdk
dmznfkl
dzlnkfm

ozdievpxm
mzoxdiepv
idpzexovm
ovdemzxpi

cbyrndpwk
kozyrncdp
ujcksndxphyf
dnbpkyc

e
e
e
w

tpndq
igpajc

gihvnzfacujpoelxqkr
mqfjnrodzkuvxaipel
okwanixqlpjufevr
rxipfjtasnekyulqvob

jmgeixvhaoknq
qloihgekvjxman
ajoghikvmpxnqe
ingovjkaehqmx

szualfd
zsulfaw

osajgkmyfvri
hwmisgbaqf

bvzm
izwrn
zsfd
mz

kixhabnoqpzsg
gpnxaikqobzsh
argcboiqznkxsph
oaqgicsndhkbzxp
jzxhpstoinqbkga

fkisv
fvisdrk
vkmisf
ksifqv
ifspvk

ovwqbshjirpg
iohbgfjqcrvt

efsqtnoywmkzrv
gwsotczmkdyqlrve
zmverktswfynqo

rwtuihvjqofszxaykn
riqntxydpcakjbgo

mzkndrhabvj
gywofampnlxbhsi
hbtenma
rcamubhn
bmndhkja

afsnkue
pfcvirzydqbetlk

zftwoivcr
rtvzwix
kzjwtrgi
hitwzor

harkxeinjtgpy
tprbwighzeksymcv

qecrsugzdho
uwdxocqyftnbzhl
dcrzqhuso
sdchqozu

cu
u
u
u

whlfczpqa
yfzhpqc
zpfobxkhqc
cfzhqp
fcozqhp

erbnkjqouhg
qsthnrjiwxvzkaf
yncqejdukrh
klqubphrnj

ikvyfmlpacez
mzeiplkacvfy
lyfzipvcmeqak

qo
h

neuzqjk
ixqhknj
pvbrygdacs

xf
ef
f
f

t
t

j
z
ybx
a

ewbmvucapsxkig
ksiprxbvagwfme
agdmiwexvsbpk
egisawxkpmbv

dykmbtv
dtjkmyv
mvkdtyc
ydkmtv

zw
o
i
oi
r

hjybnqczotxgeiaup
cpygejxuzhonitqab
jnauyiohtcepqbzgx
uaqtnyicgezoxjpbh
nptbcijxzuoeayqgh

owynpg
wpyn
pnwy
ywpn

fqoishlxzarmkc
dstzjmxrvfckuoi
xsmozrfcik
zmgsrcwiofxpku
igrkebsfoxcmdz

moas
xdcfmoa

xltpwzrf
erbhflxwzntp
tnsrbxlawpzf
rtzwuoxipfl

yesonitqag
etigoaqmynshc
tpneigasoqy

pnmvfgwyierqukct
tcnuigmqpeyrwvk

qza
zaqr
zqa
qza
qza

dyphutng
ghntydup
thpudywng
tpudyhgn

gofac
homgpwae
govmnaw
azsgo
apgmyuo

bsvqmnidyogzuewtk
qitsokmnewdbuy
iqskwxyonmuetdb
kbmsundoywiqte

uoqj
jvs
yjazt
j

r
o
nv
oy
r

u
ru

avofjnwdehrpyklqugzimtx
gfjlwkrahzqvneodmutpyxi
mgpjlfuxoyvzwqtdhaeknir
ryfqedjgpnikawmtxhvuloz
gidrokyntxavfwpmqelhzujc

k
mzp

jfpow
jfop
pfjo

qokte
eno
woef

qnart
utaqr

ajqivchfpem
upvqhcjmafe
pvewjfhmcqa
vmjpecaqhf
cahpfemjvq

ayw
kp

rixwjogsfhuyvebnp
vexwuhjyogrfisnbp
psyfwhrxeogjubnvi
yjvswhnrogixbufpe

eylbtgqvronjfzphw
brhqvoptnjeygwflz
rwhlpzbgjvoneyqtf
hcvlnbegyrfwtpozjq
ynwefqphlvrotbjzg

xyu
xy

bj
j
j
j

kocgiwr
ibksgowc
ijkcwog
wiegjcaok

rlt
ltr
lrt
rlt
lrt

xjoc
jcoxz
cxjo

r
r
amrtqgfw
udr
sderl

vonauts
atxsyvco
psroawlevbjdgk
smvzhqoya

ubwotjecsqhadvkf
ufqkjtesadhvcbow

pbqsuatrzk
rsquzpobk
pqsrbzkdu
zqcusrkpvb
spbkqrzu

vqwcinpb
aiejfduvpht
zowvpinrxqml

zufk
kwe
k
mk
wko

lydtzkhwajf
xrphuebsogm
nsucmhgqpx

mwhlnfotz
shvfwmanl

xfywodzc
fyoxchw
howycfx
owyhfxc
xwocyf

hri
rv
lzr
r
nrfc

mkd
yvjkoguaxip
nwkz
bcktdsmqf
sznkw

flhbygto
ftbylhoa
otbyflh
yhbtfol

rnphowmiy
hpwrmoyis
iunworypmh
diyrwhnmpo

qlhfdcg
plju
rl
nalk
lep

xwcropjbzkdegnufsqiht
rcidlowgxnsktqpbheyzfju
ctfxzgvprnhbqeodkwjisu

wgzu
fkbuxrwg
gwjyuhzn
nhjyzuwg

rwbm
wmkrs

itzekynp
dkepiunyt
vmwlbgkcipnseqr

xlkbgo
kgz
kag

i
x
htq
sot
f

kuqperwixsgvbctyjfdn
qjcdstpxvyuwifnbre
atqumpwrefdxvoijcznys
rfxdcuispnewjtkyqv

imdwuntbahxvj
daniwhemzxtjb
nhmajglidtxvwb
tbjinhxwymad
csaqnhdtfrmjobwkix

esjkcgpf
gmfszpk
pfgksj

i
i
i
i

alnj
zucmhenrtoq
bkn
nifp
nvi

mjkagdfsilctvpwhuq
wufhtjlgpaivcqdsmk
qutsghdvkmcwfaijlp
vutlpwschfkamqjdgi
isjwtmqkvfgalupcdh

ynsgxmfoelkd
yxmvgkd
vgmykxd
gmyhkdx
ygxmkdz

vldyroebks
osverdjlyb
eszyrudvblo
rvdqomlcbtygse
oredlbvsy

o
o
o
o
jvmo

jbkpwnc
dtwrpiqbsf
vlayehgxmozu

khc
crkylh
ewticaxphkd
fhncmk
khcf

ofvtnbpayduik
ufbiatxvpdoyn
oibfupdrtvyna
favdotpyixuqnb
ywatimcefbgvpsoundz

ismcgzfqbxdlv
zlwdsivqcbgmf
szcbqidfgvlm

fgjx
xjf
fxpjm
xjf

etuipyaxvmjszkf
aeyjvuwzspkim
pajvmizekyus

nmbyxzehsagcdfjvt
hzbaxdfyjevntgc
dvthajbznegxfcy

ftwqrgzohp
hexzqdjsrfwmu

eubmrcntqyxpsjozvilgadhkfw
zjfrdtwiuyoaepcnmkslqvgxbh
keiurfhgmzovydqapcxjswntbl
umkocxlwagfbzepjyirtvdsnhq
kngzxjrshovmdbtclwfiqepyua

lyomqhdu
mylowqh

chlwr
rhwcl
crlhw
wcplrfh

tamkofzcpq
tomgsjqca

bj
vfwbi
gb
gbz

njaecfkliuwm
cnvkfwualmij
iaunwmfelckj
hjifcqxumnkalw

iht
orlie
afsxupiz

nocfkzrdstjqwu
ehisrtpqnwgaymbuc

qxgt
gtoxcj
txgr

hoxsgkdiqtfz
gtfisxozhvdk
gofksdtxihz
izghftsdokx

i
x
a
i
i

knqftuisvegdjw
ymogrc
yacpbrog
gxlp

sa
k
k
w
b

speodbqvngkjrl
nfslobmegdpkjvqr
rpgbneasdkljqvo
dnvklcgjiorqpubse

y
y
y
y
y

pahzx
axpz
axzp

ya
a
ay
ta

haposzk
lromwgtifpz
xobjpszq
pujonz
ndopyqvz

wqfl
kwuqelft
lfbvwq

cqgefyksvhwpalxdbrimoznu
spvyfeucqnigwxbkzrmadl
sxlwrdbyvgzpqmnuacfejti

ou
uo
uo
ou
uo

oridzvksnfuep
vsrpfexizdoq

nxo
qgx

xybutqfszdhl
ybsdlqfxutz
zlxuydqbtsf

tl
tbla
rtel
jtgxlohyc

w
vrgofi
kcjt

xkqnrf
pxqnr
xrqn
qrxnp
qxrn

pabnotufrs
bornptsda
sptobanru
mjzonarsplybgt
uranspoqbtx

gncfptk
qyodies

tiln
lt
lt
lt

ecbxuofajgshqk
crehbqksaoifjux
klibxfuhqejocaws
csbxhojuatefkq
gjaqcexhkofbus

egjflivrcywdtu
gyiedbfovxt
qsviadhygtef
gihexypfdvnt

niotdwkarb
jbimonfkl

j
z

yfob
bymsrul
byqu

dsycgzhtioxrpwvlen
edskiwvnhozrcypglt

ygcjblprwkiehz
esfjghqbliczwpuk
ieghcjlpzkwmb

mcephzsxawni
imazphsnexw
mxezwnhysipa
wsheabqmnipxzd
pcmwhysneazxi

yovtlfcuiwxmskzjqeghr
gbcvlityzjxqmfoswkue
mqlgfwkvysjuzntieoxc

hivam
amfuvi
aemv
mxahvg

lze
le
lze
lepd

jwpm
wjmc
gcmjw
mjdaw
jwm

s
sxuq
su
ns
uqs

csqmipzdnhxkvfgt
hxdfqvptigsmcn
snhpfmtgqivcxd
scihxqwpmdntfvg

nrsmoa
rsnma
sramn
nasmr
msnar

yihjeplactzrdfb
ztfekaljidry

qwhty
gweh
zksdnuipmhal
oxtwrhcbjq
qhcvb

ybemxa
jseoixkvc
ugdxepl

tofhpsgaul
lqushgofp
lfphogsu
goplhsuf
lhsugpof

gdwzk
xqw

wmiagjvocxrzkhdtfu
xhwscvljdqryibpgofma

rgacswftbpxydum
rsmtxdypgofuacwb
rwqkufstdjxmnalgbpyc
thzabcdwprgyxmsfu
caywrpsduftgxbvm

dujpzvsb
jusdvpabr
odvjbsup
budpvjs
kpujbsvd

gfpncwmjrdlx
rwmcfnbdplgj

djw
jdw
wjd
diwvjn
jwdb

h
k
z
k
v

al
lpa
la

chinjymkwe
vnwgcemkp
kvcemyxnj
enkcm
krlceuqnfom

glewafm
ngqawfvul

fia
rup
j
rmp
ju

dgvtfbxow
wvtjgbdxf
gxtbwvd
tbndgxzqvw

kuycgeanqwh
unkhyceqgaw
aykcweqguhn
ceqhwkunyag

vcighoudqlamkrt
dnyhemguilvqtao
hxzoubfvgiqajtlwm
ovqepnmgladtihu
oatnlremuvsigqh

nd
wdn
xnea
ribpvsfynoctmqh
n

rpflnskacoq
laqojrp
liprwqao
aojlprq
oarqipl

jvk
zwmvj
jv
vj

vydxlwk
vxywd
xdyzurw

lqghripoewbjdvy
qbpcdjlwhovrey
pledvrqbwhsojanf
hjqdbptlmwzeogvr
rqjwohdipuvble

h
h

ot
t
t

fyxkdhnwalez
weakhydnlxzf

xhqawsrol
guxblwar
lvkjrydiwxmptea
wfaxnrgl

famd
xmd
md
fmd
damj

istm
smbj
mwbs
msw
ms

raszvfpwdmeich
awfmvlizcperdh
pjviuhacmzfwdryqe

t
t
t
t
t

b
b

uemjsklzft
teukljfmzs
ztfjulsemk
jkfesztmlu
jlumszeftk

toczuxmkslrhpvijeg
mopultekcxzv
xukmoedpltczva
kpolveuzxmtc
pktdovemcxzul

agvfm
jvogqfiau
vdaogf

c
gqd

sgfpy
sgfbpl

jretxvqmfghp
tureqgfvjm
ijtyqezrgvnfml
mergqtjfv

ubzsrptcgxwdoe
tebrzfpwuxgds
wbdrxtfpgsuez
gvnuhzpdebwaxtrs

gdqmje
gqtcpdmfe
rxqyiehnogmsbdv

fqwzlinbormheg
mjorlniezb

ia
ai
ia
ai

xghswfuabdlqicnyekmt
bgetcxwalnkdiysfuh
sigwankrfuhtcxedlby
nlwxfucbhgtdseikya
khawdecfngultbyixs

cwzgvbuqlsyetoiajnpm
asjpbudkhoinqgtzryfwevxc

zbpfxictqy
udpyqtxizcgef
zptxicfhqy
hpqcfbzixyt
zxhqpyftic

oirypkjhxfcwdqeagu
hwoqyupdrjigbmvxsa
kxdhpangqieuroyjw

fegnzr
rzfgne
erfnzg
znfreg

pvuafthmr
dvpmwcyg"""

split_input = raw_input.split("\n\n")

Each item in the split_input list represents the collected answers for a group. If a group has more than one person in it, a newline character separates each person’s answers.

In the sample of split_input shown below:

• The first line shows the answers for the first group, which is made up of two people.
• The fifth line shows the answers for the fifth group, which is made up of five people. All of them answered yes to only one question: Question v.

['wdcmlzfnugqtvjbsahi\neasrkmocxbpjgi',
 'xrpnegqlcsyodhjfutzakmiwvb\nmgilapxjtrndbheyqzckfouwsv',
 'scynhfozmlvbqkarwj\nqhvjkmbyxcfonlazdw\nvjhzfnapwclkqiomyb',
 'bpourq\nujpmoqs\nobqup',
 'v\nv\nv\nv\nv',

...

]

Finally, I split each item in split_items, using the newline character as the separator:

groups = [line.splitlines() for line in split_input]

The result was a list that I named groups, where:

• Each item in groups represents a group of passengers
• Each group is a list, where each item in the list represents the answers for one passenger in that group.

Here’s a sample of groups:

[['wdcmlzfnugqtvjbsahi', 'easrkmocxbpjgi'],
 ['xrpnegqlcsyodhjfutzakmiwvb', 'mgilapxjtrndbheyqzckfouwsv'],
 ['scynhfozmlvbqkarwj', 'qhvjkmbyxcfonlazdw', 'vjhzfnapwclkqiomyb'],
 ['bpourq', 'ujpmoqs', 'obqup'],
 ['v', 'v', 'v', 'v', 'v'],

...

]

With the input data massaged into something that could easily be processed in Python, it was time to get to work.

Strategy

The goal was to get the total of all the “yes” answers for all the groups, keeping in mind that if any person in the group answers “yes” to a given question, the group is considered to have answered “yes” to that question.

Consider a group of three people. If:

• the first person in the group answered “yes” to questions a, b, and c,
• the second person in the group answered “yes” to questions d, e, and f,
• and the third person in the group answered “yes” to questions g, h, and i…

…the the group is considered to have answered yes to questions a though i.

To put it mathematically, a group’s answers was the union of the answers of everyone in the group.

With that in mind, I wrote this function:

def count_union_group_answers(groups):
    count = 0
    
    for group in groups:
        if len(group) == 1:
            # If there’s only one person in the group,
            # the group’s “yes” answers are that person’s “yes” answers.
            count += len(group[0])
        else:
            # If there’s more than one person in the group,
            # the group’s “yes” answers are the union
            # of everyone’s yes answers.
            union_of_answers = set(group[0]).union(*group[1:])
            count += len(union_of_answers)

    return count

This function takes advantage of the fact that while Python’s union() is a set method, it can take one or more non-set arguments, as long as it can convert the arguments into a set.

For example, this code:

set(['a', 'b', 'c']).union("def", "ghi")

results in this set:

{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'}

I rearranged the set so that its items would appear in alphabetical order so that it would be easier to read. This is fine, because with sets, there is no order.

Now that I had count_union_group_answers(), I could apply it to groups…

count_union_group_answers(groups)

…and get the answer for part one: 6504.

The Day 6 challenge, part two

The challenge

Here’s the text of 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?

Strategy

This time, the goal was to get the total of all the “yes” answers for all the groups, keeping in mind that the group is only considered to have answered “yes” to a given question if every person in the group answered “yes” to that question.

Consider a group of three people. If:

• the first person in the group answered “yes” to questions a, b, and c,
• the second person in the group answered “yes” to questions a, e, and f,
• and the third person in the group answered “yes” to questions a, h, and i…

…the the group is considered to have answered yes to question a, and nothing else.

To put it mathematically, a group’s answers was the intersection of the answers of everyone in the group.

All I had to do was tweak the count_union_group_answers() function from part one to find the intersection of group members’ answers…

def count_intersection_group_answers(groups):
    count = 0

    for group in groups:
        if len(group) == 1:
            # If there’s only one person in the group,
            # all the answers count.
            count += len(group[0])
        else:
            # If there’s more than one person in the group,
            # only answers common to all people count.
            intersection_of_answers = set(group[0]).intersection(*group[1:])
            count += len(intersection_of_answers)

    return count

…and then apply count_intersection_group_answers() to groups…

count_intersection_group_answers(groups)

This gave me the answer for part two: 3351.

Recommended reading

• GeeksForGeeks: Sets in Python
• Real Python: Sets in Python
• The official Python documentation: Sets

Solutions for other days in Advent of Code 2020

• Day 1: Report Repair
• Day 2: Password Philosophy
• Day 3: Toboggan Trajectory
• Day 4: Passport Processing
• Day 5: Binary boarding
• Day 7: Handy Haversacks
• Day 8: Handheld Halting

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 5 of Advent of Code, titled Binary Boarding.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 5 challenge.

The Day 5 challenge, part one

The challenge

Here’s the text from part one of the challenge:

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?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into Python. This involves pasting it into a triple-quoted string and assigning it to the variable raw_input, and then splitting it using the newline character as a delimiter, producing a list named split_input:

raw_input = """BBFFFFBRLL
BFBBBBFLLL
FBBBFBFLLR
BFBBBFBLRR
FBBFFBFLRR
FFBFFBFRRR
FBFBBBBLLL
BFFBFFFRLR
BFFBFFFRLL
BFBBFBFRRL
FBFFFFBLRR
BBFFBFBLLR
BBFBFFBRLR
BFBFBFFRLR
FBFFBFBRRL
BFFFFBFRLR
FFBBBBBRLR
BFFFBFBLLR
FBBBBBBRLL
FBBFBFBRRL
FBFBFBFLRL
FFBFBBFRLL
BFBFFBFRRL
FBBBBFBLLR
FFBBFBFLRR
BFBFBBFRRL
FBFFFBBLLR
FBBFFBFRRR
FFFBFBBLRL
FBBBBFBRRL
BFBFBBFLRL
BBFFBFBLRL
BBFFFFFLRL
BBFBBFFRLR
FFBFBBBRRL
FBFFFFFRLR
FFFBBFFLRR
BFFFBFFLRL
BFBFFFBRLR
BBFBFBFLRR
FBBBBFFRRR
FBFFFBFRLL
FBFFFFFLRL
BFFFFFBLRR
FFFBBBFLRL
FBFBBBFRLL
FFBFBBBLRR
FBFFFFFRLL
FFBFFFFLRR
BBFBFBBRRL
FFFBFBBLRR
BFFBFBBRRR
FFBBFFBLRL
BFBBBFFRRL
FFBBFFFRLL
FBFFBFBLRR
FBBFBBBRLL
FBBFFFBRLR
FBFFBFFLRL
FFFBFBBRRR
BBFFFBBRLL
BFBFBBBRRR
BBFFBFFLRR
FFBFFBBLLL
FFFBBBFLLL
FBBFBBBRRL
BBFBFBFLLR
BFBFFFFRLL
BFFBBFFRLR
BFBBFFFRLR
BBFFFBBRRL
BFBFFBFLRR
FBBFFFBRRR
FFBFFFBLLR
BFFFFBBRLR
BBFFBBFRRR
BFBBBFBLLL
FFBBBFBLRR
FFBFFBFLRL
FFFBBBBRLR
BFBFFFBRRR
BBFFBFFRRL
BFFBBFFLRR
FFFBFBBLLL
FBBBBBFLLL
BFBFFBFLLR
BBFBFBBRRR
FBFBBFBRLR
FBBFFBFRLL
BFBBFFBLRL
BFBBFFFRRL
FBFFBBFRLR
FBBFBBBLRL
FBFFBFFLLR
FFFBBFBRLR
FBBFFBBLLR
FFFBBBFRRL
BBFBBFFRRL
FFBBBFFRLR
BFFFFBBRRR
FBBBBBFRLR
BBFBFFBRRR
BFFBFBFRLL
BFBFFFFLRL
FBBBFFBRRR
FBBFBBFLLL
BFFFFBFLLR
BBFFFFBLLR
FFBFBFFLRR
FBBBFBBRRL
BFFFBBFLRL
FBFFFBFLLL
BBFFFFFRLR
FFFBBBFRLL
FFBBBFBRLL
BFFBFFBRLR
BBFFBBFLRR
FBBBBFBLRR
BFFBFFBLRL
FFBFFFFRLR
FBBBBBBRRL
FBBFFFBLLR
FBFFFFFLLR
FBBFBBFRLL
BFFBFFFRRL
FBBFFBFLLR
FFBBFFBLLR
FBBBFBBRLR
BFFBBBFLLR
FFBBFBFRRR
FFFBFBBRLL
FBFFFBBRRL
BFFFBBBLRL
BBFFBBBLLL
FBFBBFBLRL
BBFFFBBLRL
FBBBBFBLRL
BBFFBBFLLL
FBFBBFFRRR
BFBBFBFLRL
FBFFBBFLRL
BFBFBFBLRL
BFBBFBBLRL
FFFBBFBLLR
FFFBFBFRRL
FBBBFBFRRR
FBBBFFBLLR
BFFFBBFLRR
BFFFBFFLRR
BBFFFBFRRR
FFFBBFBLRR
BFFFFFFRRL
FBBFFFFLLR
BBFBFFFRRR
FBBBFFFRRR
BFBFFFFRLR
BFBBFFFRLL
FFBBBFBLLR
BFFBBBFLLL
FBFFFBFRRL
FFBFFFFRRR
FFBBBBFRRL
FFBFFFBLRR
FBBBBFBRRR
BBFFBFFLLL
FBBBBFFLLR
FBFFBBFLLL
BFBBBFBRLL
FBBFFFFRLL
FBBFBFBRLR
BFFBBFBLRR
FFBFBFBRLL
BBFFBBFRLL
FFBFBBFLLL
BFFBBFBLLL
FBFFFFFRRL
FBFFBFBLRL
FFBFFBFRLL
BFBBBBBRRR
FBFFBFBLLR
FFBFFFBLRL
FFBFFBBLRR
BFBFFBBRRL
FFBFBFBRLR
FFBFBFFLRL
BBFBBFFLRL
FFBFFBFLLR
FFFBBBBLRR
BFFBFBBRRL
FFBBFBBRLR
BFFBFBFLLR
FFBBFBBRRR
BBFFBBBRRR
BFFFBFFLLR
BFBBBFFRRR
BFBBFBBLLL
FFBBFBBLLL
FBFBFBBLLR
FFBBBFFLRR
FFBFFBFLLL
BFFBFFBLLL
FBFBBBFLLL
BBFBFBBRLL
FBFFBFBRRR
BBFBFFFRLL
BBFBFFFRRL
BFFFFBBLRL
BFBFFFFRRL
FFBFFBFRRL
FBBFBBFLRR
BFFFBBBRRL
FFBFFFBLLL
FFBBBBBLLR
BFBFBFBLRR
FFBBFFFLRL
FBBBBBBRRR
FBFBFFBLLL
FBFFBBBRRL
BFFBFFFRRR
BFBBFFBRRR
BBFBBFFLRR
BBFBFFBRRL
BBFFBBBLLR
FBFFFFBRLR
BBFFFFFRRR
BFBFFBFRLL
FBBBFBBRLL
FFBBFBFRLR
BFBFBFBRLR
FFBBBFFLLR
FBFFFFFLRR
FBFFBFFRLR
BFBBBBFRLR
FBFBBFBLRR
FBBBBFBRLR
BFBFFBBRLL
FFBBFBFLLL
FFBFBFBLLL
FFBFBFBRRR
BFBFBFBLLR
BFBBBBBRRL
FBBBBBFRRR
BBFBFFBLRL
FBBBBFFRLR
BBFFFFFLLR
FBBFFBBLRR
FBFFFFBRRR
BFFFBBFRLL
FBFBFFBLRR
BFBBFBBRRL
BFFFFBFRRL
FFBFFFBRRR
FFBFBBBRLL
BBFFFFFRRL
BFBBFBBLRR
FBBFBFFRRR
BFFBFFBLRR
BFFFBBFLLL
BFBFFFBRLL
BBFBBFBLLL
BFBFBFFRLL
FFFBBBFLLR
FBBBFFFRLL
BFBFFBFRRR
FFBBFFFRRR
BBFFFBBRRR
BFFFFBFLRR
BFFFFFFRRR
BBFFBFBLRR
FBBBBBBRLR
BBFFBFFLLR
BFFBBBBLLR
FBBBBFFLRR
FFBBBFFRRL
FBFBBFFLLL
BBFFBBBRLL
FBFFBFBLLL
BFFBFBBRLR
FBBFFFBLRL
FFBFBFFLLL
FBBBFBFLRL
FFFBBFFLRL
FBBBBFFRRL
BFBFBBBRRL
BFFFBBBLLR
FBFBFBBLRL
BFBBFFBLRR
BBFBFFFLRR
FBFFBBBLRR
FFBFFBBRLL
BFBFFFFLRR
BBFBFFBRLL
FBBBFBFRLL
BFBBBFFLRL
BFFBBBBRRL
BFFBBBBLRR
FFBBFBFRLL
FBFBFFFLLL
BFFFFFFLRL
BFBBBFBRRL
FFFBBBBRRL
FBFFFFBLRL
FBBBBBFRLL
FFBBFFFLRR
FBBFBBFLLR
BFBFBBFRLL
BFBFFFBLLR
BFBFBBBLRL
FFBFFFBRLR
BFFBBBFRRL
BFBBBBBLRR
FBFFFBBRLL
FBFBFBBRRR
FFFBFBBRLR
BFBFBBFLRR
FBFBFBBLLL
FFBBFFBRLL
FBBFBFBRRR
BFFFFFBRRL
FBBBFBBLLL
BBFBFFBLLL
FFBFBFBLLR
FFBBBFBRRL
FBFBFBFLLL
BFBFBBFRLR
FBBFBFFRLR
FFBFFBBRRR
BFFBFFBLLR
FBFFFBFLRL
FBFFFFFRRR
FFBBFBBRLL
FBFFBFFRLL
BBFFFBFLRR
BFBBBFFRLL
FBFBBBBLRL
FFFBBBBLLL
BBFFFFBRRR
FBBBBBBLLL
FFBFBFBLRL
BFFBFFBRRL
FFBBFBBLRR
BFBFFBFLLL
FBBBBFFRLL
FFFBBFBRLL
BFFFBFBLLL
BBFBBFBRLL
FFBFFBBLLR
BBFFFFBLRL
BBFBBBFLLR
BFBBFFBRLR
BFFFFBFLLL
BBFFBBFLLR
BBFBFFFLLL
FBBBFFFLLL
BFBBFBBRRR
FFBBBBFRRR
BBFBBFBRLR
BFBBFFFLLL
FFBFFFFLLR
FBFBFFBLLR
FBBBFFFLLR
BFBBBBFLRR
FBBFBFFLRR
FBFBBFBRRL
BFFBFFFLLL
FBBFBBFRRR
FBFFBBBRLL
FBFBBBBRRL
FFFBBBFRRR
FBFBFFBRRL
FFBBFBFLLR
BFBFBBBLLL
FFBFFBFLRR
BFBFBBFRRR
FBBBBBBLLR
BFFBFBFRRR
FBFFFBFRRR
BBFFFBFLLL
FBBFFBBRRR
BFBFBFBLLL
BBFFBBBLRR
FFBFFFFRRL
FFBFBBFLLR
FFFBBBFRLR
FFFBBFBLLL
FBFBBFFLLR
FBFBFBFRRR
BFBBFFFRRR
BFBFFBBRRR
FBFBBFFRLR
FFBFBBFRLR
BFFBBFFRRR
BFBFBBFLLL
FFFBBFBRRR
BFFBBFFRLL
FFBFFFFLLL
FFBBBFFRLL
BBFBBFBRRL
BBFBFFBLRR
FFBFFBBRRL
FBBFBBFRRL
BBFFFFBLLL
BFBBFFBRLL
FFBFBFFRLL
BFBBFFFLLR
FBBFFBBRLR
BFBFFBFLRL
BFBBFBBRLL
FFBBBFFRRR
FBFBBFFLRL
BFBBFBFRLR
FFBBFFBRRL
FBFFBBFLLR
FBFBBBFLLR
BFFFBBFRRL
FFFBBBBRRR
BFFFBBBRRR
FBBFBFFRRL
BBFFFFBRRL
BBFFFBBLLR
BFBBFBFRRR
BFFFFBBRRL
FBBFBBFLRL
FBBFBBBRLR
FBFBFFFLRL
BFFBFBFRRL
FBFBBBFLRL
BFBBBBBLRL
FFBFFFBRLL
BFFBBFBLRL
FBFBFBFRLR
BFFBBFFLLL
BFBBBBBLLL
FFBFBBFLRR
BBFBFBFRRR
FFFBBFFRRR
BFFFBFFRRL
BBFBFFFRLR
BBFBFFFLLR
BFFFFFFLRR
FBBFBBFRLR
FFBBBFFLRL
FBFBFFFRLR
FFBFBFFLLR
BFBFFBBLRR
BFFBBBFRLL
FBBFFBBLRL
BFBBFFBLLR
FBFFBFFRRR
BFFBBBFRLR
BFBFBBBLLR
BFFFFBBLLR
BFFBFBFLLL
BFBBFFFLRR
BFFFFFFRLR
BBFFBFFLRL
BFBFBFFLLR
BBFFFFFLRR
FFBFBBFLRL
FBFBFFBRRR
FFBBBBFRLR
BBFBBBFLLL
BFFFFBBRLL
FBFBBBFRRR
BFFBFBFRLR
FFFBBFFLLR
FBBFBFFLLL
FFFBFBBRRL
BFBBBBFLRL
FFBFFBFRLR
FBFFBFBRLL
FBBBFBFLRR
BBFFBBFRLR
FBBBBBFLRR
FBFFFFBRLL
BFFBFFFLRL
BFBFFFFLLL
BBFFBFBRLR
BFBBBFBLLR
FBBFFBBRLL
FBFBFBFRLL
BBFBFBBLRL
BFFBFBBLRL
FFBBBFBLRL
FFBBFBBLLR
BFFBFBFLRR
FBBBFBFRRL
BFFBBBFLRL
BFBBFBBLLR
BFBFFFBLRR
FBFFBBBLRL
FBFFBFFLLL
BBFFBFFRRR
BFFBFBBRLL
BFFFBFFRRR
BFFBBBBLRL
FBBFFBFRLR
FBFFBFFRRL
FBFFFBBRRR
BBFFFFBLRR
FBBBFFFLRL
FFBBBBFLRL
BFFFBFFLLL
BFBBBFFRLR
FFBFBBFRRL
FBFBBBFLRR
FFFBBBFLRR
BFFFBFBRLR
FBBBFBBLRR
FFBBBFFLLL
FFFBFBFRLR
FBBFFFBRLL
FBBFBBBRRR
BFBFFFFRRR
BFBBBFBLRL
BBFFFBBLRR
BFBFFBBLLR
BFBBFBFLLR
BBFFBBBRRL
FBBFFFFLLL
BBFBFFBLLR
BFBBBBBLLR
FFBFFBBRLR
FFBBBFBRLR
FBFBBBBLRR
FBBFBFBLRR
BBFFBBFRRL
BBFFBFFRLL
FBBBFFBLRR
BFFFBFBRRR
BFFBFFFLRR
FFBBFBBRRL
FBFBBBBRRR
BBFBBFFLLL
FBFFBBBLLL
FBBFFFBLRR
BFBBFFBLLL
FBFFFFBLLL
BFBFBBBLRR
BFFFFFBLLR
BFFBBFBLLR
FBFFBFFLRR
FBBFBBBLLR
FFBBBBBRLL
BFFFBBFLLR
FFBFBBBLRL
FBFBBBFRRL
BFFFFBFLRL
FBBFFBFRRL
FFFBBFBRRL
FFBBBBBRRL
BBFFFBFLRL
FBBFFFFLRR
BFBBBBFRLL
BFFBFFBRRR
FFBBFFFLLL
BFFBBBBRLR
BFBBFFFLRL
BFBFFBBLRL
BBFFFBFRLR
FBFBFBFLLR
BBFFFBBRLR
FBBBFFBLLL
FBBBFFFRRL
BFFFFFFRLL
FFBFBFFRRR
BFFFBFBRLL
FBBBFFFRLR
BFBBBFFLLL
FBBFBFBLLL
FFBBFFFLLR
BFFFBBFRLR
BBFFFBFRLL
FBBBBBBLRL
BFBFBFBRLL
FBBBBBFRRL
BBFBFFFLRL
BFBBBBFRRR
BFBFFFBLRL
FFBFBFBRRL
BFBFBFBRRR
FFBFFFFRLL
BBFBBFFLLR
FFBFBBBLLR
BBFBBBFLRL
FBFBBBBRLL
FFBBBBFLRR
FFBFFBBLRL
BBFFBBBRLR
BFBBFBFLLL
FBFBFFBLRL
BFFFFFBLLL
FBFFBFBRLR
FBBBBFBLLL
FBBFFBFLRL
BFFFBBBLLL
FBBFBFFLRL
FFFBBFFLLL
BFBFBFFRRL
BFFFFFBRLL
BFFBFBFLRL
BFFBBFBRRL
BFBBFFBRRL
FFFBBBBLRL
FFBFBBBRRR
FBFBBFBRRR
FFBBBBFLLL
BBFFBFBRLL
FBFFBBFRLL
FBFBFFFLLR
BFFFFBFRRR
FFBBBFBLLL
FBBBFFBLRL
BFFFBBBLRR
FFFBFBFRRR
FBFFFBBRLR
FBFBFFFLRR
FBBBFBBLRL
FBBBFBBRRR
BBFBFBBLRR
BFFBBBFLRR
BFFFFFFLLR
BBFBFBFRLL
BFFBFBBLLL
FFBBBBFLLR
BFFFFBBLRR
FBFBFFFRLL
BFBFFFBRRL
BBFBFBBLLR
FFFBFBBLLR
FBFFBBBRRR
FBBFBFFLLR
FBFBFBBRLL
BFFBBBBRRR
BFFBFFFLLR
BFBFBFBRRL
BFBBBBFLLR
FBBFBFBLLR
BFFFFFBRLR
FBFFFBBLLL
BBFFFFFLLL
FFBBBBBLRR
FFBBFBBLRL
BBFFFFFRLL
FBFBBFFRRL
FFBFBBBLLL
BFFFBBBRLR
FBBBFBFRLR
FBBFFFFLRL
FFBBFFBRRR
FBFBFBFLRR
BFBFBBBRLL
BFBFBFFLLL
FBFFBBBLLR
BFFFBFBLRL
FBBFFFFRRR
FBBBBBFLLR
BFFFFBBLLL
FBBFBFBLRL
BFFFBBFRRR
BBFFBFBRRR
BBFFBFBRRL
FFFBBBBRLL
BBFFBBBLRL
BFBBFBBRLR
BBFBBFBLLR
BFBBFBFLRR
FBFFFFBRRL
BFFBFBBLRR
BBFFBFBLLL
FBBBFBBLLR
FBFBBFBLLL
BBFBFBFRLR
BFFBBBBLLL
BFFBFFBRLL
BBFBBFBLRR
FBFFBBFLRR
BBFFBFFRLR
BFFFBFFRLR
FBFBBFFRLL
BFFBBBFRRR
FBBBFBFLLL
BBFBBBFLRR
FBBFFBFLLL
BBFBBFBLRL
FBFFFBBLRL
FBFBBFBRLL
BFBBBBFRRL
BFFFBFFRLL
BFBFBBBRLR
FFBFFFFLRL
FFBFFFBRRL
FBFFBBFRRR
BBFFFFBRLR
BFFFBFBLRR
BBFFBBFLRL
FFBBFFFRRL
FBFBFBBRLR
FBBFBFFRLL
FBBBFFBRLL
FBBFBBBLLL
FBBFFBBRRL
BFBFBBFLLR
FFBBFFBLRR
FFBBBBBLLL
BBFFFBFLLR
FBFBBBBRLR
BFBFBFFLRL
FFBBBBBRRR
BFBFFBFRLR
FBBBBFBRLL
BFBBBBBRLL
BFBBBBBRLR
FBBBBFFLLL
FBBFFFBLLL
BBFBFBFLLL
BFFFFFBLRL
FBBFBFBRLL
BBFBFBBRLR
BFFBFBBLLR
FFBBFBFLRL
FBFBBBFRLR
FBBBFFBRLR
FBFFFBFLRR
BFBFBFFLRR
BFFFFFBRRR
BFFBBFBRLL
FBFBFBFRRL
BBFBBFFRRR
FBBFBBBLRR
FBFFBBBRLR
BBFBFBBLLL
FFBFBBFRRR
FBFBBFBLLR
BFBFBFFRRR
BBFBBFBRRR
FFBFBBBRLR
FBFBFBBRRL
BFBFFFBLLL
FBFBFFBRLL
FBFFFBFRLR
FBFFFBBLRR
FBBFFFFRLR
BFBBFBFRLL
FBFBFBBLRR
FFBBBFBRRR
FBBFFFFRRL
FBFBBFFLRR
FBBBFFBRRL
FBFFFBFLLR
FFBFBFFRLR
FBBFFBBLLL
FFFBBFFRLR
BFFFFFFLLL
FFFBBBBLLR
FFBFBFFRRL
BBFBBFFRLL
FFFBBFFRLL
BBFFFBFRRL
FFBBFFBLLL
FBFFBBFRRL
BFBBBFBRLR
BFBFFBBRLR
FBFBFFFRRR
BFBBBFFLLR
FBFBFFFRRL
BFFBBFFLLR
FBFBBBBLLR
FFBBFFBRLR
FBFFFFFLLL
BBFBFBFRRL
FBBBBFFLRL
BFBBBFBRRR
BFFBBFFLRL
BFFBBFFRRL
BBFBFBFLRL
FBBFFFBRRL
BFFFBFBRRL
FBFFFFBLLR
FFBBFBFRRL
BFFBBBBRLL
BFBFFFFLLR
FFBBFFFRLR
BFBFFBBLLL
BFFBBFBRRR
BFFFBBBRLL
FFFBBFBLRL
FFBFBFBLRR
FFFBBFFRRL
FFBBBBBLRL
BFBBBFFLRR
FBBBBBFLRL
FBBBFFFLRR
BFFBBFBRLR
BBFFFBBLLL
FBBBBBBLRR
FBFBFFBRLR
FFBBBBFRLL"""

split_input = raw_input.split("\n")

Strategy

They dropped a hint in the title of the challenge: Binary Boarding.

They dropped a hint by saying the airlines seats people using binary space partitioning instead of zones.

They dropped a hint when they said that the row numbers range from 0 to 127, and that a seven-character sequence determined your row. Only two characters could be used in that sequence, F and B.

(Additional hint for those of you who didn’t study binary numbers: The numbers 0 through 127 can be represented using seven bits.)

They dropped a hint when they said that the seat numbers (which they called column numbers) range from 0 to 7, and that a three-character sequence determined your seat. Only two characters could be used in that sequence, L and R.

(Additional hint for those of you who didn’t study binary numbers: The numbers 0 through 7 can be represented using three bits.)

The “FB” and “LR” sequences are just binary numbers in disguise.

Solving this challenge involves:

• Converting the “FB” and “LR” strings into binary strings.
• Converting those binary strings into decimal numbers.
• Doing the math on those numbers to get the seat IDs.

Converting the “FB” and “LR” strings into binary strings and converting those binary strings into decimal numbers

For each “FB” string, I wanted to convert the Fs to 0s and Bs to 1s. In order to do this, I used Python’s string.maketrans() method to build a character translation table and its string.translate() method to make the translation using that table.

The result was this function:

def convert_FB_to_01(string):
    translation_table = string.maketrans("FB", "01")
    return string.translate(translation_table)

The first line in the function uses string.maketrans() to define a translation table. string.maketrans() takes two arguments:

1. The characters to be translated.
2. The corresponding resulting characters.

In this case, I only want F to be translated into 0 and B to be translated into 1. All other characters translated using this table will remain unchanged.

The second line does the actual translating, using the translation table as its guide.

With the function defined, I could then use it to create a list of all the rows, expressed as binary strings:

binary_rows = [convert_FB_to_01(line[:7]) for line in split_input]

This line of code creates a new list, binary_rows, by taking the first seven characters of each line of input data — the “FB” string — and converting it to binary.

Here’s a sample of the result:

['1100001', '1011110', '0111010', '1011101', '0110010', 
'0010010', '0101111', '1001000', '1001000', '1011010', ...]

The next step was to convert binary_rows into a list of its numeric equivalents:

decimal_rows = [int(binary_row, 2) for binary_row in binary_rows]

This line of code, creates a new list, decimal_rows, by converting each binary string into its decimal numeric equivalent. It does this by using the int() function to convert strings to integers, and the extra argument specifies that value represented in the string is in base 2, a.k.a. binary.

Here’s a sample of the result:

[97, 94, 58, 93, 50, 
18, 47, 72, 72, 90, ...

It was time to do the same thing with the “LR” strings. This was pretty much the same operation as with the “FB” strings.

First, an LR-to-01 converter:

def convert_LR_to_01(string):
    translation_table = string.maketrans("LR", "01")
    return string.translate(translation_table)

Then, a list comprehension to use that converter:

binary_columns = [convert_LR_to_01(line[-3:]) for line in split_input]

This line of code creates a new list, binary_columns, by taking the last three characters of each line of input data — the “LR” string — and converting it to binary.

Finally, convert these numbers into decimal:

decimal_columns = [int(binary_column, 2) for binary_column in binary_columns]

I now had two lists that I could use to do the math:

• decimal_rows: The “FB” sequences, converted into decimal numbers.
• decimal_columns: The “LR” sequences, converted into decimal numbers.

Doing the math to get the seat IDs

As stated in the problem definition, the ID for any given seat is (its row number * 8) + (its seat number). I needed to build a list of seat IDs using decimal_rows and decimal_columns.

Here’s the code I used to do it:

decimal_rows_and_columns = zip(decimal_rows, decimal_columns)
seat_ids = [item[0] * 8 + item[1] for item in decimal_rows_and_columns]

The first line uses zip() to take two lists to make a single list filled with tuples. Each tuple has an item from the first list and a corresponding item from the second list. Here’s an example of zip() in action:

>>> list(zip(['a', 'b', 'c'], [1, 2, 3]))
[('a', 1), ('b', 2), ('c', 3)]

The second line uses the newly-created decimal_rows_and_columns as a basis for creating a new list of seat IDs.

Once the seat_ids list was created, it was a matter of using the max() function to get the highest ID value, which was the solution for part one. In my case, the value was 883.

The Day 5 challenge, part two

The challenge

Here’s the text of 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.

What is the ID of your seat?

Strategy

It’s a full flight, so my seat should be the only one missing from the list. I could find this seat by doing the following:

• Sorting the seats in ascending order.
• Iterating through the seats, while keeping an eye out for a “gap”. That gap is my seat.

Solution

Here’s the code I used to solve part two:

sorted_seat_ids = sorted(seat_ids)

last_seat_ids_index = len(sorted_seat_ids) - 1
current_index = 0
my_seat_id = None

while current_index < last_seat_ids_index - 1:
    if sorted_seat_ids[current_index + 1] - sorted_seat_ids[current_index] == 2:
        my_seat_id = sorted_seat_ids[current_index] + 1
        break
        
    current_index += 1
    
if my_seat_id:
    print(f"My seat is {my_seat_id}.")
else:
    print("Better check that algorithm!")

It creates a list of sorted seat IDs, which it then loops through. While looping through it, it checks to see if the ID of the seat immediately after the current one is 2 higher than the current ID. If it is, we’ve found the gap, and the ID of my seat is the ID of the current seat plus one.

In my case, the seat ID was 532. I entered that value and solved part two.

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 4 of Advent of Code, a.k.a. “The Toboggan Puzzle”.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 4 challenge.

The Day 4 challenge, part one

The challenge

Here’s the text from part one of the challenge:

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?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into Python. This involves pasting it into a triple-quoted string and assigning it to the variable raw_input.

raw_input = """pid:827837505 byr:1976
hgt:187cm
iyr:2016
hcl:#fffffd
eyr:2024

hgt:189cm byr:1987 pid:572028668 iyr:2014 hcl:#623a2f
eyr:2028 ecl:amb

pid:#e9bf38 hcl:z iyr:2029 byr:2028 ecl:#18f71a hgt:174in eyr:2036

hcl:#cfa07d byr:1982 pid:573165334 ecl:gry eyr:2022 iyr:2012 hgt:180cm

cid:151 hcl:#c0946f
ecl:brn hgt:66cm iyr:2013 pid:694421369
byr:1980 eyr:2029

ecl:brn
pid:9337568136 eyr:2026
hcl:#6b5442
hgt:69cm iyr:2019 byr:2025

cid:66 hcl:#efcc98 pid:791118269 iyr:2013
eyr:2020 ecl:grn hgt:183cm byr:1993

eyr:2022
hgt:160cm iyr:2016 byr:1969 pid:767606888 ecl:gry hcl:#6b5442

hgt:157cm eyr:2026 ecl:oth hcl:#efcc98 byr:1938 iyr:2014

byr:1931 iyr:2015
ecl:gry
hgt:76in
cid:227 hcl:#09592c eyr:2024 pid:276365391

ecl:gry hgt:170cm iyr:2014 cid:285 pid:870052514
hcl:#866857 byr:1925 eyr:2025

eyr:2021
byr:1960 pid:569950896
iyr:2010 hgt:179cm hcl:#888785 cid:167

hgt:154in cid:194
pid:8142023665 byr:2010 hcl:7d22ff ecl:utc iyr:2026 eyr:1976

ecl:blu eyr:2030 hgt:192cm
pid:363860866 iyr:2019 hcl:#ceb3a1 byr:1963

byr:1947 hgt:167cm hcl:#7d3b0c ecl:amb
cid:70 eyr:2022 iyr:2019 pid:756932371

hgt:185cm pid:871945454
iyr:2020
hcl:#866857 ecl:amb
byr:1989 cid:184 eyr:2030

byr:1935 pid:322117407
hgt:153cm iyr:2011
cid:244 eyr:2022 hcl:#efcc98 ecl:hzl

ecl:blu hcl:#5e6c12
eyr:2029 iyr:2011 hgt:191cm byr:1992

hcl:#7d3b0c eyr:2029
hgt:163cm
pid:625292172 byr:1932 ecl:brn
iyr:2020

hgt:158cm
eyr:2030 iyr:2016 byr:1969
cid:173 pid:092921211 hcl:#602927 ecl:grn

hcl:#733820
iyr:2016 eyr:2029
ecl:hzl hgt:180cm pid:292904469 byr:1984

ecl:amb pid:901224456 hgt:190cm
iyr:2013
hcl:#733820
byr:1922

pid:262285164 iyr:2010
byr:2018 eyr:2026 hcl:#602927 hgt:179cm ecl:gmt cid:349

byr:1956 eyr:2027 pid:351551997 hgt:71in cid:277 hcl:#cfa07d iyr:2010 ecl:grn

eyr:2027 hcl:#602927 hgt:157cm ecl:gry
cid:128 byr:1953
pid:231551549 iyr:2012

iyr:2011 pid:771266976
cid:264 byr:1955 hcl:#b6652a
hgt:189cm ecl:blu
eyr:2030

eyr:2026 pid:698455242
byr:1949 ecl:gry hgt:190cm
iyr:2013 hcl:#efcc98 cid:139

ecl:blu hgt:181cm byr:1977 iyr:2011 eyr:2022
pid:454163967 hcl:#b6652a

pid:534506872 hgt:155cm iyr:2012
byr:1968
cid:333 eyr:2024 hcl:#623a2f
ecl:amb

hgt:162cm
iyr:2020
hcl:#733820 eyr:2027 byr:1995 ecl:gry pid:084994685

iyr:2016 byr:1990
ecl:amb pid:185689022 eyr:2025
hgt:184cm hcl:#866857

byr:2016 hcl:z iyr:2022 hgt:166in
eyr:2040

byr:1943 hgt:152cm hcl:#cfa07d ecl:hzl iyr:2016 cid:300 pid:376088014

iyr:2020 eyr:2026 hcl:#602927 ecl:gry byr:1962 pid:453907789 hgt:172cm

eyr:2023 hgt:185cm
hcl:#623a2f pid:963767258 byr:1977
iyr:2019 ecl:oth

hgt:159cm byr:1965 cid:349 ecl:blu pid:962908167
iyr:2013 eyr:2024
hcl:#fffffd

eyr:2026
pid:912822238 hgt:66in byr:1985 iyr:2018 hcl:#c0946f ecl:hzl

hgt:167cm hcl:#ceb3a1
byr:1990 eyr:2027 ecl:grn
iyr:2011 pid:642877667

hcl:#7d3b0c byr:1921 pid:976412756 hgt:192cm
iyr:2013 ecl:gry

iyr:2030 pid:283599139
eyr:2039 cid:203
hcl:f943cb
hgt:111

hgt:190cm
iyr:2027 ecl:blu hcl:z
byr:2004 eyr:2039
pid:734570034

hcl:#6b5442 hgt:191cm
ecl:oth byr:1989 pid:669414669 cid:196 iyr:2016 eyr:2023

ecl:brn eyr:2028 byr:1965 pid:630674502 hcl:#602927 iyr:2020 hgt:61in

iyr:2016 eyr:2022 cid:225
hcl:#733820 ecl:hzl hgt:166cm
byr:1934
pid:232742206

ecl:amb hcl:#602927 eyr:2029
pid:897535300
hgt:189cm byr:1952
iyr:2017

pid:853604345
hgt:161cm cid:269
hcl:#fffffd eyr:2030 iyr:2011 ecl:grn byr:1966

hgt:151cm hcl:#18171d eyr:2026 ecl:grn iyr:2016 pid:176cm
byr:2000

hcl:#341e13
eyr:2022
pid:536989527 cid:73 byr:1971
ecl:hzl

pid:739005658 hcl:#b6652a
eyr:2026 hgt:154cm ecl:hzl
iyr:2019 byr:1935

pid:373465835 ecl:oth byr:1932 cid:333 hgt:165cm
hcl:#b6652a eyr:2021 iyr:2014

byr:1967 pid:486658617 hcl:#18171d hgt:174cm
eyr:2021 iyr:2015 ecl:gry cid:53

eyr:2024
cid:124 iyr:2017 hgt:152cm pid:095649305 hcl:#341e13
byr:1920 ecl:oth

hcl:#623a2f
byr:1951 pid:993284548
cid:106
hgt:186cm
ecl:amb iyr:2017 eyr:2029

cid:308 pid:080673934
hgt:193cm
byr:1967 hcl:#623a2f iyr:2016 ecl:hzl
eyr:2021

iyr:2010 eyr:2024 byr:1946 hgt:156cm
cid:199
ecl:blu hcl:#866857

ecl:blu byr:1955 eyr:2022 cid:95 pid:139391569
iyr:2019 hgt:180cm
hcl:#efcc98

ecl:brn pid:579889368
eyr:2023 hgt:158cm byr:1935
iyr:2018 hcl:#cfa07d

byr:1920 pid:90919899 hcl:#18171d
hgt:152cm
eyr:2029 ecl:oth iyr:2014

byr:1961 eyr:2024
ecl:#d401e3 iyr:2011 hgt:172cm pid:919145070
cid:100
hcl:#efcc98

ecl:gry
hgt:168cm
hcl:#888785 byr:1942 pid:731032830 iyr:2014
eyr:2028

hcl:#6b5442 pid:265747619 hgt:191cm
cid:217
eyr:2028
iyr:2019 ecl:amb
byr:1948

iyr:2011 ecl:brn
hgt:183cm hcl:#fffffd cid:258 byr:1983
pid:835909246

byr:2030
iyr:2024 ecl:#f66808
hcl:fd548d cid:183
pid:#fced33
hgt:160in

ecl:utc hgt:183in hcl:a92c31 pid:0394222041
iyr:2008
eyr:1976 byr:2020

pid:126195650 iyr:2019 hcl:#341e13
ecl:blu
hgt:150cm
eyr:2025
byr:1964

cid:71 iyr:2016 hgt:157 ecl:grt
hcl:#18171d pid:#1ab5ea eyr:2027

eyr:2026 hcl:#b5266f
byr:1971
cid:269 hgt:192cm iyr:2012
pid:736578840 ecl:amb

pid:152109472 hcl:#ceb3a1 ecl:grn hgt:188cm eyr:2027
byr:1923

hcl:#341e13 pid:535175953 hgt:63in eyr:2028 iyr:2015 byr:1999 ecl:gry

hgt:183cm pid:611738968 byr:2001
eyr:2020 hcl:#a97842 iyr:2014
ecl:gry

eyr:2038 ecl:gmt pid:113210210 iyr:2012 byr:2011
hcl:z
hgt:157cm

hgt:157cm
pid:699449127
iyr:2014 ecl:gry byr:1980 hcl:#fffffd eyr:2029

iyr:2028 hcl:z pid:152cm
eyr:2039
ecl:#4760fb hgt:177in
byr:2017

eyr:2026 hcl:#efcc98
iyr:2020 hgt:180cm ecl:hzl pid:747449965 byr:2016

byr:1974 iyr:2019
cid:89 eyr:2023 pid:421418405
hcl:#fffffd hgt:192cm
ecl:gry

hcl:26c2ef eyr:2029 cid:309 byr:1931 ecl:grn pid:#4eb099 iyr:2024
hgt:174cm

ecl:gry
hgt:183cm
cid:281
eyr:2022 pid:050492569
byr:1968 hcl:c88145
iyr:2015

eyr:2028
iyr:2014 pid:712984515 hgt:187cm cid:206 hcl:#866857 byr:1927
ecl:brn

byr:1936 hgt:61in ecl:oth iyr:2012 pid:447813841
hcl:#c0946f
cid:126 eyr:2021

ecl:gry pid:791970272
eyr:2020
byr:1932 hcl:#623a2f hgt:161cm
iyr:2015

hcl:#c0946f
byr:1935 pid:721144576 eyr:2025 hgt:162cm
iyr:2017 ecl:oth

byr:1959
pid:551109135
ecl:hzl hgt:68in
eyr:1977 hcl:#888785
iyr:1955 cid:100

hgt:190in eyr:1993 pid:8358180772 iyr:1975
ecl:oth
byr:2024
hcl:3de172

eyr:2030 hgt:190cm hcl:#a40ef3 byr:1935 pid:484932501
ecl:amb iyr:2016

iyr:2015
byr:1964
hgt:176cm
pid:819552732 hcl:#c0946f ecl:amb cid:263
eyr:2024

hgt:65cm cid:59 eyr:2027 pid:074880819 ecl:utc iyr:2023
byr:1954 hcl:#623a2f

byr:1954 hgt:167cm iyr:2020
eyr:2023 hcl:#602927
pid:280295309
ecl:hzl cid:168

hgt:168cm pid:311043701 iyr:2017 byr:1965
ecl:hzl
eyr:2026 hcl:#fffffd

hcl:#fffffd ecl:grn pid:672987232 iyr:2012 eyr:2022 hgt:66in

iyr:2012 ecl:#6f4f9f
hgt:133 byr:1937
eyr:1953 pid:7177768428 hcl:#602927

iyr:2010
byr:1922 hcl:#c0946f
eyr:2029 ecl:gry
hgt:165cm
pid:893045052

iyr:2013 eyr:2028 hcl:#866857 pid:137143403
ecl:brn hgt:170cm byr:1940 cid:194

hgt:161cm
eyr:2027 pid:3966920279 ecl:gry iyr:2015 byr:1997 hcl:#cfa07d

ecl:amb
hgt:157cm byr:1971
pid:562746894 cid:305 hcl:#0b0e1a eyr:2021 iyr:2016

hcl:8b821d hgt:157cm pid:187cm cid:298 eyr:1926 iyr:2019
ecl:amb
byr:2030

hgt:155cm hcl:#341e13 byr:1924 pid:779847670
ecl:hzl iyr:2015
eyr:2024

pid:768590475 hcl:#a97842 iyr:2014 cid:128 eyr:2029
ecl:oth hgt:164cm byr:1990

iyr:2019 hgt:181cm cid:342
eyr:2020 ecl:gry byr:2001
hcl:#623a2f
pid:473165431

byr:1928 eyr:2026 hcl:#42a9cb iyr:2010
ecl:grn hgt:157cm pid:638074984

eyr:2028
byr:1951
pid:239781647 iyr:2020 hgt:156cm
ecl:hzl cid:215 hcl:#efcc98

pid:636605355 ecl:hzl
iyr:2017 cid:323 eyr:2025
byr:1995
hcl:#18171d hgt:187cm

byr:1933 hcl:#866857 hgt:152cm ecl:oth iyr:2014 pid:900790914 eyr:2030 cid:267

ecl:brn byr:1999 eyr:2027 hcl:#623a2f iyr:2017
pid:853165955
hgt:152cm

eyr:2030 pid:316704688 hcl:#c0946f ecl:brn iyr:2014 hgt:193cm

iyr:2012 byr:1928
hgt:154cm pid:570535769 hcl:#623a2f eyr:2026 ecl:hzl

iyr:2016 cid:252 eyr:2030 hcl:#888785
hgt:177cm ecl:grn byr:2002 pid:568715162

pid:570999226 iyr:2012 hgt:150cm
byr:2024
ecl:brn hcl:z eyr:2029

pid:174002299 iyr:2019 hcl:#cfa07d ecl:brn byr:1927
cid:77 hgt:159cm eyr:2027

ecl:#d16191 eyr:2022 pid:166cm hgt:165cm hcl:#18171d iyr:2015

pid:112585759
hcl:#341e13 eyr:2025 byr:1962 hgt:164cm ecl:hzl iyr:2018

pid:478415905 eyr:2025 cid:315
ecl:amb hgt:91
iyr:2014 hcl:#cc9d80
byr:1985

pid:561885837 hcl:#7d3b0c
hgt:169cm
byr:1921 iyr:2014 cid:178
eyr:2022 ecl:gry

ecl:#c87497 hcl:5321a2 eyr:2020 hgt:74in
pid:#7a62c6 iyr:1976

eyr:2037
pid:858202391 hgt:162cm
ecl:grn byr:2003
cid:278
iyr:2010 hcl:cbf662

ecl:blu iyr:2012 hgt:183cm hcl:#623a2f pid:848200472 byr:1997 eyr:2027

byr:1942
hgt:164cm
pid:464257339
iyr:2016
hcl:#7d3b0c ecl:gry

iyr:2012 hcl:#ceb3a1
hgt:193cm ecl:amb
pid:667987561 eyr:2024 byr:1960

hgt:187cm
pid:222340640
iyr:2018 eyr:2022
ecl:oth
byr:1957
hcl:#336667 cid:83

eyr:2025 iyr:2015 hcl:#733820
ecl:brn
pid:131195653

hgt:185cm eyr:2026
ecl:amb byr:1998 pid:938587659 hcl:#733820
iyr:2016

ecl:oth pid:300949722
eyr:2028 iyr:2016
byr:1933
hgt:179cm
hcl:#cfa07d

byr:1974 iyr:2019
ecl:hzl hcl:#c0946f eyr:2024 pid:484547079
cid:112
hgt:185cm

eyr:2022 iyr:2018 hcl:#fffffd pid:118568279
hgt:153cm ecl:gry byr:1941 cid:341

iyr:2018
eyr:2027 hcl:#888785
byr:1970 hgt:165cm pid:773715893
ecl:amb

hcl:#623a2f hgt:156cm byr:1938 iyr:2012 pid:745046822
ecl:amb
eyr:2030

iyr:2012
pid:097961857
eyr:2023 hgt:66in hcl:#fffffd byr:1962 ecl:utc

byr:1943 hgt:150cm
iyr:2012
pid:740693353 eyr:2023
hcl:#18171d cid:101 ecl:blu

iyr:2018 pid:183728523 byr:1924 hgt:154cm eyr:2030
cid:167 ecl:blu hcl:#ceb3a1

hgt:69cm
eyr:2025 hcl:z ecl:brn byr:1982 pid:250782159
iyr:2011

byr:1998 iyr:2018 hcl:#341e13 eyr:2022 hgt:157cm pid:497100444 cid:266 ecl:gry

eyr:2027 iyr:2011 hcl:#6b5442 hgt:156cm pid:494073085
byr:1998
ecl:hzl

byr:1947 hcl:#b6652a
iyr:2011 pid:228986686 eyr:2030 hgt:175cm cid:70 ecl:brn

eyr:2026 hgt:159cm
byr:1946 pid:534291476
iyr:2018 ecl:gry cid:225
hcl:#18171d

pid:439665905
cid:311 ecl:amb iyr:2018
eyr:2030
hgt:186cm byr:1950
hcl:#cfa07d

pid:250175056 hcl:#efcc98
byr:1981 cid:262 hgt:154cm ecl:gry iyr:2020 eyr:2027

pid:461335515 iyr:2014 hcl:#f1cf00 hgt:180cm ecl:amb eyr:2027
byr:1956

iyr:2014 eyr:2030 cid:194
pid:234623720 hcl:#733820
hgt:164cm byr:1929
ecl:blu

byr:1992
eyr:2024 hcl:#ef8161 cid:216
ecl:brn hgt:177cm iyr:2018
pid:101726770

hcl:#341e13 hgt:178cm iyr:2016 eyr:2029 byr:1945 pid:045325957 ecl:grn cid:99

ecl:gry
iyr:2012
cid:52 hgt:168cm byr:1943
hcl:#cfa07d
pid:899608935 eyr:2030

cid:241
byr:1934 hgt:161cm eyr:2027 iyr:2011 hcl:#c0946f ecl:amb pid:346857644

iyr:2019 hgt:178cm
hcl:#c0946f byr:1957
eyr:2026
ecl:brn pid:222885240

ecl:blu
eyr:2021 cid:312 hcl:#733820 hgt:186cm iyr:2012 byr:1969
pid:821704316

hcl:#6b5442 cid:159
hgt:180cm
iyr:2018
eyr:2028
ecl:hzl byr:1966
pid:#e0238e

pid:622400994 eyr:2022 hcl:#5b6635 iyr:2012 byr:1980
hgt:190cm ecl:oth

byr:1976 ecl:gry eyr:2020 iyr:2020 hgt:171cm pid:219878671 hcl:#6b5442

hgt:163cm byr:1968
pid:003521394 ecl:oth
iyr:2010
cid:61 hcl:#888785

cid:115 pid:810722029 hgt:166cm byr:1955
ecl:blu eyr:2030 iyr:2018

hgt:176cm
eyr:2025
pid:617393532 hcl:#733820 byr:1975 iyr:2018 ecl:grn

hcl:#733820 byr:1979 pid:838168666
hgt:190cm ecl:oth cid:330
eyr:2029 iyr:2018

eyr:1940 hgt:67cm iyr:2009 ecl:gry pid:#e76a62 byr:2020 hcl:z

hgt:190cm ecl:brn pid:396113351
byr:1956 iyr:2010
hcl:#6b5442 eyr:2024
cid:256

hcl:#efcc98
hgt:178cm byr:1984 iyr:2013 pid:752620212 eyr:2021 ecl:gry

iyr:2014 hcl:#a97842
hgt:166cm ecl:blu eyr:2024
byr:1935
pid:836748873

cid:236 ecl:amb hgt:168cm iyr:2010 hcl:#602927 byr:1950 eyr:2026 pid:404810674

eyr:2030 ecl:grn
byr:1975 pid:064596263 hgt:193cm
iyr:2019 cid:71 hcl:#a97842

iyr:2014
pid:298386733 hcl:#c0946f
hgt:180cm ecl:hzl cid:115 byr:1940 eyr:2023

iyr:1960 hgt:139 ecl:#9db7b8 byr:1980 pid:#ef597b cid:54 eyr:2028 hcl:fdcda3

iyr:2015 byr:1954 ecl:blu hgt:62in hcl:#ceb3a1 pid:253593755 eyr:2028

eyr:2025 ecl:blu pid:216388098 iyr:2017 byr:1968 hgt:151cm hcl:#602927

eyr:2022 hcl:#a97842
pid:606979543 iyr:2013 ecl:grn cid:63
hgt:186cm byr:1992

ecl:gry
hgt:168cm hcl:#18171d iyr:2017 pid:670898814 byr:1983
eyr:2022

hgt:155cm ecl:grn iyr:2012 pid:837979074 eyr:2024 hcl:#888785 byr:1972

iyr:2015 pid:970743533 hcl:#866857 eyr:2027
byr:1921 ecl:brn

eyr:2022
hgt:160cm
byr:1964 hcl:#efcc98 iyr:2019 ecl:oth pid:141923637

byr:2029 pid:3313111652 ecl:brn eyr:2034
iyr:2013 hgt:193cm hcl:z

pid:853890227 eyr:2029
hcl:#efcc98 iyr:2021 byr:2003 ecl:#037c39 hgt:160cm

iyr:1927
byr:1992
eyr:2030
hcl:#efcc98
ecl:amb hgt:152cm pid:436765906

iyr:2014
hcl:#c0946f pid:207052381
eyr:2024 ecl:hzl
hgt:177cm
byr:1923

ecl:blu
iyr:2014
eyr:2025 hgt:165cm
hcl:#733820 pid:343011857 byr:1967

ecl:xry
eyr:2028
iyr:2011 hgt:166in hcl:#c0946f
pid:805297331
cid:167 byr:1926

byr:1947
pid:468012954 eyr:2026 ecl:oth iyr:2018 hgt:170cm hcl:#b6652a

hcl:#6b5442 ecl:brn
hgt:180cm cid:233
pid:029789713
byr:1920 iyr:2010 eyr:2024

iyr:2010 eyr:2027
hgt:156cm
hcl:#c0946f
byr:1960 pid:312723130 ecl:hzl

eyr:2023 byr:1959 iyr:2010 hgt:186cm pid:066768932 ecl:grn hcl:#602927 cid:310

eyr:2030 pid:460535178 hgt:171cm ecl:gry iyr:2020 byr:1934 hcl:#888785

hgt:64cm eyr:2021 byr:1995 cid:336
ecl:gmt pid:926714223 iyr:2017 hcl:#18171d

eyr:2022 iyr:2010
ecl:grn pid:285994301 cid:215
hgt:186cm byr:1978

hgt:63in hcl:#866857
pid:386128445 iyr:2020 byr:1971 eyr:2021 ecl:gry

hgt:183cm hcl:#733820 iyr:2015
ecl:blu pid:216205626 eyr:2022 byr:1941

cid:150 ecl:amb pid:872515243 byr:1926
eyr:1996
hcl:#dedc39 hgt:67in iyr:2020

byr:1927 ecl:brn cid:153 iyr:2011
pid:165190810 hcl:#fffffd
eyr:2028 hgt:64in

pid:502603734
byr:1966 iyr:2015 hgt:176cm cid:205 ecl:brn hcl:#fffffd eyr:2021

hcl:#18171d hgt:158cm byr:1943 iyr:2019
pid:058840094
eyr:2023

byr:1962 hcl:#b6652a ecl:grn
cid:297
iyr:2010 pid:990422650
hgt:154cm eyr:2020

eyr:1934 iyr:2011
ecl:gry
hcl:z byr:2004 hgt:63cm pid:6173356201

pid:329432364 eyr:2029
ecl:grn hcl:#18171d iyr:2013
hgt:158cm byr:1960

hcl:#efcc98 iyr:2016 hgt:186cm cid:215
pid:852781253 eyr:2027 ecl:blu byr:1937

hcl:#623a2f ecl:gry iyr:2020 byr:1972 hgt:182cm pid:073426952 eyr:2027

hcl:#3317b9 byr:1950 pid:304511418 hgt:177cm cid:124 eyr:2020 ecl:hzl iyr:2014

eyr:2029
pid:034754507 byr:1936
cid:265 ecl:#b50997 hgt:183cm
hcl:#623a2f iyr:1924

eyr:2024 byr:1927 cid:243 ecl:gry hcl:#6b5442 pid:714355627 hgt:160cm
iyr:2016

hgt:152cm
ecl:gry hcl:#a97842
eyr:2029 byr:1952
pid:555308923 iyr:2010

byr:2008
pid:19681314 hgt:180in iyr:2030 ecl:gry cid:272
eyr:2023
hcl:#b6652a

cid:234
iyr:2014 byr:1940 ecl:hzl pid:042231105 hcl:#3bf69c hgt:172cm eyr:2029

hcl:#efcc98 pid:831567586 hgt:190cm iyr:2017
byr:1966 eyr:2024 ecl:blu

hcl:#341e13 ecl:blu
eyr:2022 cid:161 pid:197839646 iyr:2014

hcl:#cfa07d
byr:1957
iyr:2019 hgt:181cm
pid:543775141 ecl:oth eyr:2021

hcl:z
pid:#596c41 eyr:2035
byr:2008 iyr:1975
ecl:#c66ee6
hgt:150in

ecl:grn
hcl:#7d3b0c iyr:2016
pid:804255369 eyr:2028 byr:1983 hgt:69in cid:82

eyr:2022
iyr:2013 hgt:191cm ecl:gry
hcl:#a97842 pid:186827268 byr:1969

pid:871672398 eyr:2026 byr:1946 ecl:oth
iyr:2015
hcl:#866857 hgt:185cm

byr:1973
hgt:150cm
pid:905076707
iyr:2017
hcl:#2edf01 ecl:oth cid:221 eyr:2026

eyr:2024 ecl:grn pid:955444191 hcl:z iyr:2015 byr:2008 hgt:151cm

byr:1958 hcl:#fffffd pid:218986541 cid:203 ecl:brn hgt:154cm
iyr:2014
eyr:2026

hcl:#623a2f byr:1964 ecl:oth iyr:2010 pid:525843363 hgt:164cm eyr:2025

ecl:blu iyr:2013 hgt:193cm byr:1990 pid:612387132 hcl:#18171d cid:280 eyr:2028

ecl:oth eyr:2022
pid:110447037 hgt:187cm byr:1967 hcl:#efcc98

byr:1930
eyr:2026 hgt:159cm
iyr:2011
ecl:hzl hcl:#6b5442 pid:923471212

cid:350
eyr:2029 pid:823592758 iyr:2018
ecl:grn byr:1972 hgt:167cm hcl:#18171d

cid:76 eyr:2027 hcl:#6b5442 pid:099579798 byr:1930
iyr:2020
ecl:gry hgt:153cm

byr:1957 ecl:brn
hcl:z iyr:2016 pid:352677969 hgt:189cm
eyr:2029

cid:143 eyr:2035 pid:602952079
ecl:#9b73f0 hcl:#602927
iyr:2022 byr:1975
hgt:174cm

byr:1971 pid:741305897 hgt:192cm
ecl:amb hcl:#888785 eyr:2028 iyr:2011

ecl:oth iyr:2016
byr:1942 hgt:189cm hcl:#888785 eyr:2024 pid:054290182

hcl:#a97842
byr:1945
ecl:amb pid:370849304
eyr:2028
iyr:2016 hgt:168cm

hgt:154cm iyr:2015 eyr:2030 byr:1952 ecl:hzl hcl:#341e13 pid:996518075

byr:1941 ecl:amb iyr:2014
hcl:#fffffd pid:560990286 eyr:2022 hgt:173cm

ecl:blu byr:1974
hgt:150cm hcl:#ceb3a1 eyr:2020 iyr:2013
pid:827415351

hcl:#623a2f eyr:2027 iyr:2011 pid:913199234 ecl:oth
byr:1990 hgt:178cm

ecl:blu byr:1989 hcl:#b6652a
eyr:2026 pid:724881482 hgt:185cm iyr:2014

cid:115 pid:255002731 eyr:2025 ecl:amb
byr:1934 iyr:2020 hcl:#7d3b0c

hgt:150cm byr:1969 ecl:blu iyr:2023
hcl:#866857 pid:754288625 eyr:2029

iyr:2011 hcl:#7d3b0c ecl:hzl
byr:1930
hgt:188cm
eyr:2023
pid:256556076 cid:136

iyr:2025 byr:1978
ecl:#fe30a9 hcl:#efcc98 eyr:2029
pid:392032459 hgt:178cm

eyr:2027 iyr:2017 hgt:160in
byr:1990 pid:131099122 hcl:#623a2f ecl:amb

ecl:grn
byr:1978
eyr:2029 hcl:#18171d
hgt:165cm pid:172369888
cid:93
iyr:2011

ecl:hzl
hcl:#733820 iyr:2010 eyr:2029 pid:127253449
hgt:156cm
byr:1963

hcl:#6c8530
iyr:2020
byr:1929 eyr:2021 hgt:177cm ecl:oth pid:347925482

eyr:2037 iyr:2026
pid:163cm
hgt:174in byr:2007 hcl:c1305f cid:134
ecl:#0cf85c

iyr:2011 pid:033811215
hcl:#a97842 byr:2002 eyr:2021 hgt:186cm
ecl:brn

hcl:#a97842
iyr:2020 eyr:2029 byr:1972 pid:535511110 hgt:160cm ecl:oth

ecl:grn cid:89 hgt:193cm pid:73793987 iyr:2021 eyr:2027 byr:1939 hcl:z

hcl:#623a2f
hgt:182cm cid:154
pid:873863966 iyr:2018 byr:1999 ecl:brn eyr:2031

iyr:2014 eyr:2029
cid:71 hcl:#fffffd byr:1924 hgt:63in
ecl:gry pid:897972798

hgt:76cm
hcl:z eyr:1955
iyr:2012 byr:2001 pid:9425090 ecl:hzl

eyr:2021
pid:501861442
ecl:grn hcl:#d71ae9
byr:1977
hgt:167cm iyr:2015

iyr:2014
hgt:170cm ecl:gry byr:1928 cid:314 hcl:#602927 eyr:2029
pid:836710987

eyr:2027 hcl:#efcc98 ecl:amb iyr:2016 byr:1995 pid:603705616 hgt:179cm

eyr:2030 hcl:#602927 cid:105 byr:1943 ecl:hzl
pid:381601507
hgt:188cm iyr:2020

iyr:2011
byr:1993 hcl:#c0946f pid:292649640 hgt:139 ecl:hzl cid:268
eyr:1999

cid:339 byr:1928
ecl:brn eyr:2022 hcl:#733820 hgt:191cm pid:282733347 iyr:2019

hgt:176cm
byr:1935 ecl:brn cid:252 eyr:2023 pid:105060622 iyr:2020 hcl:#18171d

ecl:hzl eyr:2029
hgt:193cm pid:770254253
hcl:#efcc98 iyr:2020 byr:1926

pid:977785261 eyr:2022 iyr:2015 byr:1978
hcl:#733820 hgt:172cm
ecl:brn

byr:2021
hgt:160in
ecl:gmt
eyr:2032 cid:345 pid:179cm
hcl:8f5c13 iyr:2029

iyr:2018 hgt:182cm ecl:gry
pid:897076789 eyr:2023 hcl:#866857
byr:1980

hgt:88 eyr:2039 cid:99 byr:2007 hcl:a1bb42 ecl:#a2f6bb
pid:2264966188
iyr:2022

iyr:2012 cid:59 ecl:gry eyr:2021
byr:1931
hgt:172cm hcl:#7d3b0c pid:862416147

byr:1962 eyr:2025
ecl:grn
hcl:#866857 hgt:180cm iyr:2014 pid:313647071

eyr:2030 hgt:157cm byr:1985
iyr:2020
hcl:#7d3b0c pid:911544768
ecl:grn

hgt:175cm
byr:1938
iyr:2020 ecl:amb hcl:#602927 eyr:2026 pid:144411560

iyr:2019 ecl:amb hcl:#888785 eyr:2025 hgt:187cm
pid:942054361 byr:1939

cid:168 pid:722146139 byr:1952 ecl:grn
iyr:2014 hgt:97
hcl:z
eyr:2023

eyr:2024 pid:567528498 ecl:gry iyr:2012 byr:1990
hcl:#733820 hgt:193cm
cid:293

hcl:#bc352c pid:321838059 byr:1930 hgt:178cm cid:213 eyr:2023 ecl:amb
iyr:2017

hgt:173cm byr:1925 pid:070222017 iyr:2013 hcl:#ceb3a1 ecl:gry eyr:2024"""

I then split() the string into a list, split_input, using two newline characters as the delimiter:

split_input = raw_input.split("\n\n")

Here’s a sample of the result:

['pid:827837505 byr:1976\nhgt:187cm\niyr:2016\nhcl:#fffffd\neyr:2024',
 'hgt:189cm byr:1987 pid:572028668 iyr:2014 hcl:#623a2f\neyr:2028 ecl:amb',
 'pid:#e9bf38 hcl:z iyr:2029 byr:2028 ecl:#18f71a hgt:174in eyr:2036',
 'hcl:#cfa07d byr:1982 pid:573165334 ecl:gry eyr:2022 iyr:2012 hgt:180cm',
 'cid:151 hcl:#c0946f\necl:brn hgt:66cm iyr:2013 pid:694421369\nbyr:1980 eyr:2029',

...

'cid:168 pid:722146139 byr:1952 ecl:grn\niyr:2014 hgt:97\nhcl:z\neyr:2023',
 'eyr:2024 pid:567528498 ecl:gry iyr:2012 byr:1990\nhcl:#733820 hgt:193cm\ncid:293',
 'hcl:#bc352c pid:321838059 byr:1930 hgt:178cm cid:213 eyr:2023 ecl:amb\niyr:2017',
 'hgt:173cm byr:1925 pid:070222017 iyr:2013 hcl:#ceb3a1 ecl:gry eyr:2024']

At this point, each item in the list had its individual components delimited by a mix of spaces and newlines. I used this line of code to convert and newlines to spaces:

split_input_2 = [string.replace("\n", " ") for string in split_input]

Here’s a sample of the result:

['pid:827837505 byr:1976 hgt:187cm iyr:2016 hcl:#fffffd eyr:2024',
 'hgt:189cm byr:1987 pid:572028668 iyr:2014 hcl:#623a2f eyr:2028 ecl:amb',
 'pid:#e9bf38 hcl:z iyr:2029 byr:2028 ecl:#18f71a hgt:174in eyr:2036',
 'hcl:#cfa07d byr:1982 pid:573165334 ecl:gry eyr:2022 iyr:2012 hgt:180cm',

...

'cid:168 pid:722146139 byr:1952 ecl:grn iyr:2014 hgt:97 hcl:z eyr:2023',
 'eyr:2024 pid:567528498 ecl:gry iyr:2012 byr:1990 hcl:#733820 hgt:193cm cid:293',
 'hcl:#bc352c pid:321838059 byr:1930 hgt:178cm cid:213 eyr:2023 ecl:amb iyr:2017',
 'hgt:173cm byr:1925 pid:070222017 iyr:2013 hcl:#ceb3a1 ecl:gry eyr:2024']

I now had an list of single-line strings, each one representing a passport, with each passport’s information delimited by spaces.

My next step was to split() each passport string into a list:

split_input_3 = [string.split() for string in split_input_2]

The result was a master list of password lists. Here’s a sample:

[['pid:827837505',
  'byr:1976',
  'hgt:187cm',
  'iyr:2016',
  'hcl:#fffffd',
  'eyr:2024'],
 ['hgt:189cm',
  'byr:1987',
  'pid:572028668',
  'iyr:2014',
  'hcl:#623a2f',
  'eyr:2028',
  'ecl:amb'],
 ['pid:#e9bf38',
  'hcl:z',
  'iyr:2029',
  'byr:2028',
  'ecl:#18f71a',
  'hgt:174in',
  'eyr:2036'],

...

['hcl:#bc352c',
  'pid:321838059',
  'byr:1930',
  'hgt:178cm',
  'cid:213',
  'eyr:2023',
  'ecl:amb',
  'iyr:2017'],
 ['hgt:173cm',
  'byr:1925',
  'pid:070222017',
  'iyr:2013',
  'hcl:#ceb3a1',
  'ecl:gry',
  'eyr:2024']]

I wanted to convert each password list into a dictionary, so I wrote this function…

def convert_to_dictionary(password_list):
    dictionary = {}
    
    for item in password_list:
        item_parts = item.split(":")
        key = item_parts[0]
        value = item_parts[1]
        dictionary[key] = value
        
    return dictionary

…which I then used that ever-so-useful Python tool, the list comprehension:

passports = [convert_to_dictionary(item) for item in split_input_3]

I now had a list of passport dictionaries:

[{'pid': '827837505',
  'byr': '1976',
  'hgt': '187cm',
  'iyr': '2016',
  'hcl': '#fffffd',
  'eyr': '2024'},
 {'hgt': '189cm',
  'byr': '1987',
  'pid': '572028668',
  'iyr': '2014',
  'hcl': '#623a2f',
  'eyr': '2028',
  'ecl': 'amb'},
 {'pid': '#e9bf38',
  'hcl': 'z',
  'iyr': '2029',
  'byr': '2028',
  'ecl': '#18f71a',
  'hgt': '174in',
  'eyr': '2036'},
 {'hcl': '#cfa07d',
  'byr': '1982',
  'pid': '573165334',
  'ecl': 'gry',
  'eyr': '2022',
  'iyr': '2012',
  'hgt': '180cm'},

...

{'hcl': '#bc352c',
  'pid': '321838059',
  'byr': '1930',
  'hgt': '178cm',
  'cid': '213',
  'eyr': '2023',
  'ecl': 'amb',
  'iyr': '2017'},
 {'hgt': '173cm',
  'byr': '1925',
  'pid': '070222017',
  'iyr': '2013',
  'hcl': '#ceb3a1',
  'ecl': 'gry',
  'eyr': '2024'}]

Strategy

With the input data massaged into a decent data structure, it was time to test the passports to see if they were valid. Valid passports have have all the required keys.

I wrote this function to test the validity of a given passport:

def is_valid_passport(passport):
    has_birth_year = "byr" in passport
    has_issue_year = "iyr" in passport
    has_expiration_year = "eyr" in passport
    has_height = "hgt" in passport
    has_hair_color = "hcl" in passport
    has_eye_color = "ecl" in passport
    has_passport_id = "pid" in passport
    has_country_id = "cid" in passport
    
    return (
        has_birth_year and
        has_issue_year and
        has_expiration_year and
        has_height and
        has_hair_color and
        has_eye_color and
        has_passport_id
    )

With is_valid_passport() written, I could apply it to every passport by way of a list comprehension:

valid_passports = [passport for passport in passports if is_valid_passport(passport)]
print(len(valid_passports))

My result: 228. I entered it into the solution text field, and Advent of Code told me that I was correct! It was time for part two.

The Day 4 challenge, part two

The challenge

Here’s the text of 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?

Strategy

In part one, it was about testing for the presence of required keys. This time, it was about testing for valid values.

To that end, I wrote this function…

def has_valid_values(passport):
    has_valid_birth_year = 1920 <= int(passport["byr"]) <= 2002
    has_valid_issue_year = 2010 <= int(passport["iyr"]) <= 2020
    has_valid_expiration_year = 2020 <= int(passport["eyr"]) <= 2030
    
    has_valid_height = False
    height_units = passport["hgt"][-2:]
    if height_units == "cm":
        height = int(passport["hgt"][:-2])
        has_valid_height = 150 <= height <= 193
    elif height_units == "in":
        height = int(passport["hgt"][:-2])
        has_valid_height = 59 <= height <= 76
        
    def is_valid_hex_string(string):
        test_value = string.lower()
        is_valid = True

        for character in string:
            if character not in "0123456789abcdef":
                is_valid = False
                break

        return is_valid
        
    has_valid_hair_color = False
    if len(passport["hcl"]) == 7:
        digits = passport["hcl"][1:]
        has_valid_hair_color = is_valid_hex_string(digits)
            
    has_valid_eye_color = passport["ecl"] in ["amb", "blu", "brn", "gry", "grn", "hzl", "oth"]
    
    def is_valid_passport_id(value):
        is_valid = False
        
        if len(value) == 9:
            is_valid = True

            for character in value:
                if character not in "0123456789":
                    is_valid = False
                    break
        
        return is_valid
    
    has_valid_passport_id = is_valid_passport_id(passport["pid"])
                
        
    return (
        has_valid_birth_year and
        has_valid_issue_year and
        has_valid_expiration_year and
        has_valid_height and
        has_valid_hair_color and
        has_valid_eye_color and
        has_valid_passport_id
    )

…which I then used in a list comprehension, which served as a filter on the validated passports from part one:

truly_valid_passports = [passport for passport in valid_passports if has_valid_values(passport)]
print(len(truly_valid_passports))

My result was 175, which was correct. Day 4 was done!

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 3 of Advent of Code, a.k.a. “The Toboggan Puzzle”.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 3 challenge.

The Day 3 challenge, part one

The challenge

Here’s the text from part one of the challenge:

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?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into Python. This involves pasting it into a triple-quoted string and assigning it to the variable raw_input.

raw_input = """...#...###......##.#..#.....##.
..#.#.#....#.##.#......#.#....#
......#.....#......#....#...##.
...#.....##.#..#........##.....
...##...##...#...#....###....#.
...##...##.......#....#...#.#..
..............##..#..#........#
#.#....#.........#...##.#.#.#.#
.#..##......#.#......#...#....#
#....#..#.#.....#..#...#...#...
#.#.#.....##.....#.........#...
......###..#....#..#..#.#....#.
##.####...#.............#.##..#
....#....#..#......#.......#...
...#.......#.#..#.........##.#.
......#.#.....###.###..###..#..
##..##.......#.#.....#..#....#.
..##.#..#....#.............##.#
....#.#.#..#..#........##....#.
.....####..#..#.###..#....##..#
#.#.......#...##.##.##..#....#.
.#..#..##...####.#......#..#...
#...##.......#...####......##..
...#.####....#.#...###.#.#...#.
....#...........#.##.##.#......
.....##...#.######.#..#....#..#
.#....#...##....#..######....#.
...#.....#...#####.##...#..#.#.
.....#...##........##.##.##.###
#.#..#....##....#......#....#.#
......##...#.........#....#.#..
###..#..##......##.#####.###.##
#.....#..##.##....#...........#
##..#.#..##..#.#.....#......#..
.#.##.#..#.#....##..#..#....#..
.#......##..##.#...#..#.......#
#....##.##..###..###......##.#.
....###..##.......#.###.#....#.
..##........#........##.....#..
.#..#.....#...####.##...##.....
....#.#.#.....#.##..##.....#..#
..............#.....#...#.....#
.#.....#......###...........#.#
.....#.#......#.##..#..........
.#......###............#.#.##..
.#.#....##.#..###.....#.##..#.#
.......#.#.#..#..#..#...##..#.#
.#.###...##.#.#.####.#.#...#...
...#.#....#......##.##.#.......
#...#.....##....#........##....
.....###...#.##.#......##.#..#.
..#...##.##.###..#..#......####
.#.##.#..#.##..##..........##..
..#.#.#..#.#.....#...###.....#.
..#..#.#....#.##.............##
.......#..###..#.#...#.....##.#
####.#.#......#..#.##.........#
..........#.....#..##......###.
..#..............#...#..##.....
......#.#.#..#.##.....####..##.
.##.#..#.#....#.......#..#.....
..#..#..#.##.#....###.#.#.#.#.#
.....#....#......###..#........
#.#.#..#...###.....#......#.##.
...#.#....#.#......#........#..
..#...###.#...#..#....##...#..#
.###.##..#..#...###.#..#.####..
#....#..##..##..#......#...##..
#.#..#...#..#...###..#.#.##....
##....#....##.####...#.#.###...
##.#...#.......#.##.##....#...#
..#.#..........#..#.#.#....#..#
..#........#...#....#....#....#
..#..#....#.......#........#...
......#....#....##.#....#.#.##.
.##...###.##.##....##.#...###..
.....##..#.#.....###..#.....###
....##.#.##...##..##........#..
#...#..##.#.#....#......#...#..
.###.##.#........#.####....#...
#.##.....#..#...#..##.##..#.#..
.....#.#..#....#..#...##.##.#..
.#......#####...##...#.#.###.#.
#......##....#.....#......##.#.
#.#.##.###.#......#####..#.....
........###.#...#..#.#........#
....#....###..#.##.#...#....#..
..........#..#.#....#...#.#...#
#.##......###.#.#.#....####...#
...#.#....#........##.#.....##.
.....##..#.#.#..###...##...#...
#...#...#....#....##........#..
.....#.........##.#......#..#..
#.....##..#.###.....#....##.##.
...#..#..#.#........##...##.#.#
..#..##.###.....#.#.....###.##.
..###.........#...##.....###...
...###...##.#...##....##.......
.#.#..#...###..#.#....#....#...
##..#.......#....#.#...#..#..#.
..#......#....####..##..#.###.#
..#.......##........#.#.#..#...
.#.......#.##.#.##.#.......#..#
###...#...#...#...#..#...#...##
..#..........#..###........##..
.##..#....##......##........#.#
......#.##......#......##...#.#
.#.#....#.#.#........#......#..
.#.#..#....####..##...##....#..
.#...##..#..#..#####....##.#...
.##.#.#...#...#.#...#.##.#...#.
###.#...##..#.###.#.....#.##.#.
#.....#.###.#.#...#..#....#.#..
..##..#....#......#.........###
.#...#...##......#...#.####....
..#.##...##..............#.#..#
..#......#..##...........#..#.#
..#####...#..#.......##...###..
..##..#....#.#...###.#...#.....
..#....#..#.#.......#..#.#.#...
.##..#.#.....##....#.......#...
...#.#..###...##....#....##..#.
.....##..#...##.####....##...#.
.......#.........#...#.##..####
........###..#..#.##.###..#....
.#.#..#.##.##.........#...#....
.###......#.....#....##....####
.##..##...........#.....#.....#
#.#.#.#.#.#.##..#.#.#..#.##....
.##.##...##..#....##..###..####
#..##.#......#...###.........#.
#..#...#..##..#..##.....##...#.
#...##..#...##.#.###.#...#.....
.###.....#.......#...#.##.###.#
..........#.#......#...###...##
..##....#.#..#....#.###...#..##
#.#..#....##.##..##.........##.
#.....#.##.###.#..#....##...#..
...#........##...#..###..######
#..#.#.#.#...#....#....###.#..#
...##.##.##.....##..#........#.
..#.#....#..#.......#...##.##.#
###.##.......##..#.####...#.#..
....#.#.....##.....#.#.##...#..
.#..##..#.....#.#..#...#..#..#.
.###....##...#......#.....#....
##.##.###......#...#...###.#...
#...#.##...#.#....##.....####..
#.#.#.#...###...##.............
..#....#.....##.#...#......#...
....#...#......#...#..#...#.#..
.###..#.....#..#...#....#...#..
..#...#.#..###.......#..#.#...#
#...###.##.....#....#..#.#..##.
...#.##.#.##......#.#.#.##.....
........####...##...##..#....#.
.#.#....#....#.#...##.###...##.
#.#...###.#.#.#....#....#.#....
.####.#..#.#....#..#.#..#..#...
#####...#...#...#....#.#.#..##.
..###.##.###...#..........#.##.
##.....#...#....###..###.#.#.#.
#..##.#..#..#..#...#.#...###..#
##....#.#...##......#.#...#...#
.##..........#.#....#...#.##..#
....#....####.#.####......#.###
..##.#.....####.#.####.......#.
#.##.##.#.....#.##......##...#.
......###..#.....#.....##......
..#..#....#.#...#.....#......##
##..#..#..###.#.#..#..##.....#.
#....#.#.....#####...#.#.......
.....#..#....#.#.#..#...#...#..
............#.##......##.##.#.#
....#...#.#........###....#....
..#..#...###.#....##..#..###.##
#.##....#...#.....##..#.##.#...
...##..###...#.#.....##.#......
.#..#.##.#####..#.......#..###.
...#.##...###.....####.#.#.....
.#......##.#.#.#.#.##.#.....#..
..#.##.#..##.......#.#.....##..
..................#....#...#...
.##.#..#.#.#..#.......#.#..##.#
....#........#......#..####..#.
#...#...##..##.#..#.......##...
#..#..#..#..#........####..#.#.
..#.#......#..#.##.##.#.#...#.#
...#..#......#.#.###.#.##..##..
..#...##.....#..#...##..#.#....
#.........#....#..#....##.##..#
..#..#.#....#..#...#.##.....#..
...#..#...#.#.....#..##..#.#...
....#........#.#....##..##..#..
#.....#.#..#.......#.##.....#..
.#.###.###...##...##..###...#..
.##.##.......#.#......#.....#.#
...#....##....#..#..........#.#
..#.##.........#.#.....#.....#.
...#.##..##.......##..##...#...
#.##......##.##..#.....##...##.
#.#.#..##...#.#............#.#.
....#.....#......##...#.#.....#
...#.#......#.#...###.......#..
......##..###....#.#...#.#####.
..#..#.#.#...##.#...###..##..#.
##.##.#.#.##.#..#....#...#...#.
#..#....######.##.#...#...#.#..
.#..#.##....#..#.#.......#....#
....#....#......##....##.#.#...
.###......#..#..#.......####..#
.#.#.....#..###...........##...
.##..##.##.....####..#..#..##..
..#..##.#......#...###.##..#.#.
....##..#.....###..#.##....##.#
#..#......#....#.........#.....
.#...#.....#.#..#..##....#.....
.##..#...#..##.#..#...........#
..#..##........##.......#..#...
#.....#....#....#.#.#...##.#...
...#...#.#.#..#.##.#.#...#.....
..#..#.#....#....###....#.#.#..
...###..#...#..#....#.....#....
...#...#.#..#.....#...###......
##......#..........#.#.#..#.#.#
....#.....#.....#..#..#.#.#.#..
...####...#.##...#.#..#....#.#.
#.##........##.............#.##
#.#.#.#.#.....................#
.#.###....#..##.##.##....#.....
#.#...#.####.###...#..#..#.#...
.##...#..###.......##..#.#.....
#.#.#.#...#...#.##.....#.......
.##.#.#.#......####..#.#.......
###..........#......#...##...#.
.........##...#.##...#.#.......
...#.#.....#...#..#...#..##..#.
.#..###...#.#.........###....#.
##..#...#........#.........##..
.....#...#.#...#.#.#...........
..#....##...#.#..#..#.##....##.
.##....#.#.....##.#..#..#...##.
..##......#.#...#.#.......##.#.
##...#..#...##.#........#.##...
#......#.##..#.#..#.###.......#
#.#...#.....#.#......#.#.#.....
#.....#..#.......#....##.#.#..#
###.#....#..##.#.##....#....#..
#.##.##....#.#..#.#...#....#...
####...#####...#.....#....##.#.
....#.#...#.#.##.#.#.##.#.#.###
#.....##.#.....#.#......#.#..#.
.#....##.#..#........#...##.#..
......#...#....##....##....##..
..###.....#....##.#...#..#.....
#....##...##.##..##.#...#...#..
#..#...#...#.#....##..#.#....#.
......................#.....#..
.#..#...#.........#....##...###
.##.#.#...##...#...#...#..#....
.#.###....#.#............##..#.
###..##.#.#.#.#....##...#......
.##................####...##.##
.#.#.........##....#.#.##.##.#.
....#...#...#...##...#.##.#..#.
.#.#........#..##.....#..#....#
##.#..#.#....#.....#...#...#...
.#...##....#.....##....#..#.#.#
####.....#..#....#......###.##.
##..##.#....###.....#...#......
.##.#...#.....#.#..#.#..#.#...#
.....#.#..#..#..###.#...###.#..
.#.#.##.#..#.#..#...#..#.......
..#.....#....#.##.##.##.......#
.#..##....###...#..............
#....#...#.#.......#....##.#...
....#.#..##.#....#..#.#....#.#.
#.........##...#.#.............
#.#.......##.....#...##..##.#.#
.......#....#..##...#..#######.
.#.#...##........#..#.....#.#..
.#.......#..#......#.##.##...##
.........#............#....#..#
.#......#...##...##...#....###.
.........#...#.#.###.......#...
###.#..#.#.#.#......##...#.#...
.#.........##.#....###....#.#..
#.#....#..#.##.#..#....##...#..
###.#...#..#..##........#.###..
.....#....#..#........#..#.##.#
..#.....##......#....#..#.#.#..
.#.........#.....#.....#.......
......#....#.###..#.#....#....#
..#.#..#.#.###.........#..#..#.
..#..#.#.#.........#....##.#.#.
#.......#........##...##....#..
##..#..#...###...#..##..#..#.#.
##..#..#....#.#..##..#..#.#..#.
..##.....##.#..#.#........###..
..#.#..#..##........#...#....##
.##..#....##..#..#..#..#.#....#
#....#.....##........#.....#.##
......#....#.#..#......#.##....
.......#..#..#......##.........
......#...#..##.....#......#..#
#..#..#....##....#........##..#
##....#...#.#.....#####........
...#.#..#.#.##.#.##..##...#....
..#..#..#..#..#....#..#..##...#
.#.....#....##.##....##.....#..
#...#.....#.....#.#...#.#....#.
.###...#..##....#..#...#.###...
....#..##..#.......#.##.##..###
#.......##.....#.......#.#...##
#.....#.#.#....#.#......#.#.#..
..##.....#..###......##........
.....#...#..##....#......#.....
#..#..#....#.#...#..###.......#
.....#.....#....#..#...#.#..##.
#####........#...#..#..##..#.#.
.#..#...#.##....#.#..#......###
#.###.#..#.....##..##....#...#.
.#...#.#####....##..........##."""

I then split() the string into a list, using the newline character as the delimiter. I named the resulting list map_basis, since it’s the basis for a complete map of the hill:

map_basis = raw_input.split("\n")

I did a quick len(map_basis) check to see how long a list I was dealing with. It had 323 items.

Strategy

Looking at the question, it became clear to me that the most important problem was to come up with the answer to this question:

Given a set of coordinates, is there a tree at that location?

First, let’s consider the coordinate system of the problem. It’s not unlike screen coordinates, with the origin — (0, 0) — located at the upper left corner of the screen. x increases as you go right, and y increases as you go down:

All the strings in map_basis are 31 characters wide, and the actual map repeats itself in the x-direction starting at character index 31. This means that for any given line:

• The character at index 31 is the same as the character at index 0.
• The character at index 32 is the same as the character at index 1.
• The character at index 33 is the same as the character at index 2.
• The character at index 34 is the same as the character at index 3.
• And so on…

This means that for any x-coordinate on the actual hill (let’s call it x_hill_coordinate), its corresponding x-coordinate on the map (let’s call it x_map_coordinate) can be defined by:

x_map_coordinate = x_hill_coordinate mod 31

The map doesn’t repeat itself in the y-direction. Any y-coordinate on the actual hill has the same corresponding y-coordinate on the map.

With that in mind, I defined this function:

def is_tree_at_coordinates(hill_x, hill_y):
    map_x = hill_x % 31
    return map_basis[hill_y][map_x] == "#"

This function should return True if and only if there is a tree at the coordinates (hill_x, hill_y).

Going down the hill

Now that I had a function that could tell me where the trees were, it was time to go down the hill! I wrote this function, which takes arguments for rightward and downward movement for each “step”. It then “travels” down the hill, counting trees along the way:

def tree_count_for_slope(right_increment, down_increment):
    right_coordinate = 0
    down_coordinate = 0
    tree_count = 0

    while down_coordinate < len(map_basis):
        if is_tree_at_coordinates(right_coordinate, down_coordinate):
            tree_count += 1
        right_coordinate += right_increment
        down_coordinate += down_increment

    return tree_count

For my input data, the tree count was 230.

The Day 3 challenge, part two

The challenge

Here’s the text of 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 completing part one, I had also completed the crucial piece of part two! Let this be a lesson to Advent of Code participants: Creating a good data structure or interface for the input data will make coming up with the answers that much easier.

The solution was simply to plug in the values above into my tree_count_for_slope() function and multiply the results together:

print(
    tree_count_for_slope(1, 1) * 
    tree_count_for_slope(3, 1) * 
    tree_count_for_slope(5, 1) * 
    tree_count_for_slope(7, 1) * 
    tree_count_for_slope(1, 2)
)

This gave me the solution for my data: 9533698720.

And with that, I had completed Day 3!

If you have any questions, feel free to post them in the comments.

Solutions for other days in Advent of Code 2020

Solutions for other days in Advent of Code 2020

• Day 1: Report Repair
• Day 2: Password Philosophy
• Day 4: Passport Processing
• Day 5: Binary boarding
• Day 6: Custom Customs
• Day 7: Handy Haversacks
• Day 8: Handheld Halting

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

For those of you not familiar with Advent of Code, here’s a quick description, taken straight from their “About” page…

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.

You don’t need a computer science background to participate – just a little programming knowledge and some problem solving skills will get you pretty far. Nor do you need a fancy computer; every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.

Advent of Code has been around since 2015, and each year, its puzzles have all been centered around a “Save Christmas” theme. Over the past five holidays seasons, programmers all over the world have solved problems using code in order to:

• Helping Santa with various tasks (2015)
• Assisting Santa with his rivalry with the Easter Bunny (2016)
• Debugging the “Naughty or Nice” system (2017)
• Saving Santa from evil time travelers who are altering history to erase him from existence (2018)
• Rescuing Santa, who’s stranded at the edge of the solar system (2019)

This year’s puzzles are about saving the well-earned vacation you’re taking, after having saved Christmas five years in a row. Day 1’s puzzles had you fix an expense report that you had to deal with before you could go on vacation, and I posted my Python solution yesterday.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 2 challenge.

The Day 2 challenge, part one

Here’s the text from part one of the challenge:

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?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through the usual process of bringing it into Python by pasting it into a triple-quoted string and assigning it to the variable raw_input.

I then split the string into an array, using the newline character as the delimiter. I named the array split_input.

Here’s the code, with the data abridged for brevity:

raw_input = """3-5 f: fgfff
6-20 n: qlzsnnnndwnlhwnxhvjn
6-7 j: jjjjjwrj
8-10 g: gggggggggg
5-6 t: ttttttft
6-11 h: khmchszhmzm
4-6 q: qqbjqqqj

...

3-6 h: hdhjhhhhchh
11-12 r: zrrkcrrrrrlh
7-9 v: vhqvlvwvzqwqvrxvjnf
1-5 r: rvmjr"""

split_input = raw_input.split("\n")

Formatting the data

One of the best things you can do while taking on an Advent of Code puzzle is to convert the data set you’re given into a format that will make it easier to solve the problem. The second part of the puzzle is usually based on the same data, and having it already in a helpful format will save you a lot of time.

With that in mind, my next step was to define a function that would convert each line in split_input into a dictionary. For example, when given the following line…

6-11 h: khmchszhmzm

…the function would produce the following dictionary:

{
"min": 6,
"max": 11,
"char": h,
"password": khmchszhmzm
}

Here’s the function:

def convert_to_password_and_policy_dict(line):
    password_and_policy_dict = {}
    password_and_policy_list = line.split()
    
    min_max = password_and_policy_list[0].split("-")
    password_and_policy_dict["min"] = int(min_max[0])
    password_and_policy_dict["max"] = int(min_max[1])
    
    password_and_policy_dict["char"] = password_and_policy_list[1][0]
    
    password_and_policy_dict["password"] = password_and_policy_list[2]
    
    return password_and_policy_dict

I used convert_to_password_and_policy_dict() in a list comprehension to convert split_input into a list of “password and policy” dictionaries named passwords_and_policies:

passwords_and_policies = [convert_to_password_and_policy_dict(password_and_policy) for password_and_policy in split_input]

Here’s a peek at passwords_and_policies’ contents:

>>> passwords_and_policies
[{'min': 3, 'max': 5, 'char': 'f', 'password': 'fgfff'},
 {'min': 6, 'max': 20, 'char': 'n', 'password': 'qlzsnnnndwnlhwnxhvjn'},
 {'min': 6, 'max': 7, 'char': 'j', 'password': 'jjjjjwrj'},
 {'min': 8, 'max': 10, 'char': 'g', 'password': 'gggggggggg'},
 {'min': 5, 'max': 6, 'char': 't', 'password': 'ttttttft'},

...

 {'min': 6, 'max': 12, 'char': 'g', 'password': 'dmgggpgggwczggghggm'},
 {'min': 3, 'max': 6, 'char': 'h', 'password': 'hdhjhhhhchh'},
 {'min': 11, 'max': 12, 'char': 'r', 'password': 'zrrkcrrrrrlh'},
 {'min': 7, 'max': 9, 'char': 'v', 'password': 'vhqvlvwvzqwqvrxvjnf'},
 {'min': 1, 'max': 5, 'char': 'r', 'password': 'rvmjr'}]

I then wrote a function that takes a “password and policy” dictionary and returns True if the dictionary’s password meets its policy:

def meets_password_policy(password_and_policy):
    char_count_in_password = password_and_policy["password"].count(password_and_policy["char"])
    return password_and_policy["min"] <= char_count_in_password <= password_and_policy["max"]

I used that function as the criteria for a filter() to create a list of only “password and policy” dictionaries whose passwords met their policies:

valid_passwords = list(filter(meets_password_policy, passwords_and_policies))

The solution to the first puzzle is the number of dictionaries in the resulting list, valid_passwords:

>>> len(valid_passwords)
564

I entered this result and completed the first challenge.

The Day 2 challenge, part two

Here’s the text from part two of the challenge:

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?

Since I already had the data in a nice, usable format, solving part two of the puzzle was easy. I simply wrote a new function that takes a “password and policy” dictionary and returns True if the dictionary’s password meets the policy described in part two:

def meets_new_password_policy(password_and_policy):
    first_position = password_and_policy["min"]
    char_in_first_position = password_and_policy["password"][first_position - 1] == password_and_policy["char"]
    
    second_position = password_and_policy["max"]
    char_in_second_position = password_and_policy["password"][second_position - 1] == password_and_policy["char"]

    return char_in_first_position ^ char_in_second_position

Note the return statement. While Python has the and and or keywords for logical and and or, it uses the ^ character for logical exclusive or.

I used that function as the criteria for a filter() to create a list of only “password and policy” dictionaries whose passwords met their policies, according to the new rules:

new_valid_passwords = list(filter(meets_new_password_policy, passwords_and_policies))

The solution to the second puzzle is the number of dictionaries in the resulting list, new_valid_passwords:

>>> len(new_valid_passwords)
325

Upon entering that result, the Day 2 challenge was complete!

Other days’ solutions:

Here are my solutions for other days in Advent of Code 2020:

• My solution to Advent of Code 2020’s Day 1 challenge, in Python
• My solution to Advent of Code 2020’s Day 3 challenge, in Python