Advent of Code Day 14 - Part 1 Suddenly, a scheduled job activates the system's disk defragmenter. Were the situation different, you might sit and watch it for a while, but today, you just don't have that kind of time. It's soaking up valuable system resources that are needed elsewhere, and so the only option is to help it finish its task as soon as possible.
The disk in question consists of a 128x128 grid; each square of the grid is either free or used. On this disk, the state of the grid is tracked by the bits in a sequence of knot hashes.
A total of 128 knot hashes are calculated, each corresponding to a single row in the grid; each hash contains 128 bits which correspond to individual grid squares. Each bit of a hash indicates whether that square is free (0) or used (1).
The hash inputs are a key string (your puzzle input), a dash, and a number from 0 to 127 corresponding to the row. For example, if your key string were flqrgnkx, then the first row would be given by the bits of the knot hash of flqrgnkx-0, the second row from the bits of the knot hash of flqrgnkx-1, and so on until the last row, flqrgnkx-127.
The output of a knot hash is traditionally represented by 32 hexadecimal digits; each of these digits correspond to 4 bits, for a total of 4 * 32 = 128 bits. To convert to bits, turn each hexadecimal digit to its equivalent binary value, high-bit first: 0 becomes 0000, 1 becomes 0001, e becomes 1110, f becomes 1111, and so on; a hash that begins with a0c2017... in hexadecimal would begin with 10100000110000100000000101110000... in binary.
Continuing this process, the first 8 rows and columns for key flqrgnkx appear as follows, using # to denote used squares, and . to denote free ones:
.#.#.#.#
....#.#.
.##.#...
.#...#..
| |
V V
In this example, 8108 squares are used across the entire 128x128 grid.
Given your actual key string, how many squares are used?
Your puzzle input is vbqugkhl.
In [ ]:
# When conversted to binary, how many of the 16,384 are used(1)
In [ ]:
def convertToAscii(data):
# print(" data going in", data)
newdata =[]
for x in data:
newdata.append(ord(x))
return(newdata)
def flipslice(knot, current, length):
piece = knot[current:current+length] # This will go to the end
#Check if we got it all
if (current + length) > 256:
piece = piece + knot[:(length - len(piece))]
for index, value in enumerate(reversed(piece)):
knot[(current+index)% 256] = value
# print("Knot after flip ", knot)
def createdensehash(block):
dhash = 0
for x in block:
dhash = x ^ dhash
return(dhash)
In [ ]:
def knothash(input):
current, jump, skip = 0, 0, 0
densehash = []
knot = list(range(256)) # Not sure if this is 256 or 128 or ?
lengths = convertToAscii(input)
lengths = lengths + [17, 31, 73, 47, 23]
# print("The input sequence is ", lengths)
for x in range(64):
for length in lengths:
# print("Working with length ", length, "skip ", skip, "current ", current)
jump = (skip + length)
if length > 256:
print("We are twisting more then the whole list ... TWF", length, size)
else:
flipslice(knot, current, length)
current = (current + jump) % 256
skip += 1
# print("The sparse hash after 64 rounds ", knot)
# Third, create a dense hash
for i in range(0,256,16):
densehash.append(createdensehash(knot[i:i+16]))
#print("I think this is wrong.", densehash)
# Change the values to hexadecimal
answer = ''
for x in densehash:
answer = answer + (format(x, '02x'))
return(answer)
In [ ]:
puzzle = 'vbqugkhl' # my input
# puzzle = 'flqrgnkx' # The sample should be 8108
print("Heads up (input): ", puzzle)
grid = [0] * 128 # Todo this is wrong but my sanity needs it
count = 0
for key, value in enumerate(grid):
hashinput = puzzle + '-' + str(key)
hexvalue = knothash(hashinput) # retunrs a hexadecimal digit
binaryvalue =''
# print(key, '. hexvalue ', hexvalue)
for c in hexvalue:
# print(c, " ", (bin(int(c,16))[2:]).zfill(4))
binaryvalue = binaryvalue + (bin(int(c,16))[2:]).zfill(4)
# print(' BinaryValue', binaryvalue)
grid[key] = binaryvalue
count = count + binaryvalue.count('1')
print("Total Filled (flqrgnkx should be 8108)",count)
# Note 2547 is too low
#9906, 9632 is too high
Advent of Code Day 14 - Part 2 Now, all the defragmenter needs to know is the number of regions. A region is a group of used squares that are all adjacent, not including diagonals. Every used square is in exactly one region: lone used squares form their own isolated regions, while several adjacent squares all count as a single region.
In the example above, the following nine regions are visible, each marked with a distinct digit:
11.2.3..-->
.1.2.3.4
....5.6.
7.8.55.9
.88.5...
88..5..8
.8...8..
88.8.88.-->
| |
V V
Of particular interest is the region marked 8; while it does not appear contiguous in this small view, all of the squares marked 8 are connected when considering the whole 128x128 grid. In total, in this example, 1242 regions are present.
How many regions are present given your key string?
In [ ]:
def checkforbuddies(grid, irow, icol, name):
global regions
global extra
bird = ''
if irow == -1 or icol == -1:
return()
regions[irow][icol] = str(name)
try:
if grid[irow][icol+1] == full and regions[irow][icol+1] == 'x':
checkforbuddies(grid, irow, icol+1, name)
if grid[irow+1][icol] == full and regions[irow+1][icol] == 'x':
checkforbuddies(grid, irow+1, icol, name)
if grid[irow][icol-1] == full and regions[irow][icol-1] == 'x':
checkforbuddies(grid, irow, icol-1, name)
if grid[irow-1][icol] == full and regions[irow-1][icol] == 'x':
checkforbuddies(grid, irow-1, icol, name)
except:
try:
if icol == 127:
if grid[irow+1][icol] == full and regions[irow+1][icol] == 'x':
checkforbuddies(grid, irow+1, icol, name)
if grid[irow][icol-1] == full and regions[irow][icol-1] == 'x':
checkforbuddies(grid, irow, icol-1, name)
if grid[irow-1][icol] == full and regions[irow-1][icol] == 'x':
checkforbuddies(grid, irow-1, icol, name)
if irow == 127:
if grid[irow][icol+1] == full and regions[irow][icol+1] == 'x':
checkforbuddies(grid, irow, icol+1, name)
if grid[irow][icol-1] == full and regions[irow][icol-1] == 'x':
checkforbuddies(grid, irow, icol-1, name)
if grid[irow-1][icol] == full and regions[irow-1][icol] == 'x':
checkforbuddies(grid, irow-1, icol, name)
except:
print("Not sure how we got here ", irow, icol)
extra +=1
return()
In [ ]:
# Note: Not re-writing above since I have grid (a 128 by 128) with values
# grid = ['##.#.#..', '.#.#.#.#', '....#.#.', '#.#.##.#', '.##.#...', '##..#..#', '.#...#..', '##.#.##.']
# 1173 is too low
import sys
full = '1'
empty = '0'
glen = len(grid)
extra = 0
regions = [['x']*glen for i in range(glen)]
regioncount = 0
for row, value in enumerate(grid):
for col, colvalue in enumerate(value):
if colvalue == full and regions[row][col] == 'x': # is it a 1 and not part of a region yet
regioncount += 1
# print("Going in with (", regions[row][col], ") row ", row, "col ",col, "Count", regioncount)
checkforbuddies(grid, row, col, regioncount)
elif colvalue == empty:
regions[row][col] = '0'
print("For test expecting 1242 on sample ", regioncount)
print(extra)
Things I've learned
Advent of Code Day 13 - Part 1 You need to cross a vast firewall. The firewall consists of several layers, each with a security scanner that moves back and forth across the layer. To succeed, you must not be detected by a scanner.
By studying the firewall briefly, you are able to record (in your puzzle input) the depth of each layer and the range of the scanning area for the scanner within it, written as depth: range. Each layer has a thickness of exactly 1. A layer at depth 0 begins immediately inside the firewall; a layer at depth 1 would start immediately after that.
For example, suppose you've recorded the following:
0: 3 1: 2 4: 4 6: 4 This means that there is a layer immediately inside the firewall (with range 3), a second layer immediately after that (with range 2), a third layer which begins at depth 4 (with range 4), and a fourth layer which begins at depth 6 (also with range 4). Visually, it might look like this:
0 1 2 3 4 5 6 [ ] [ ] ... ... [ ] ... [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] Within each layer, a security scanner moves back and forth within its range. Each security scanner starts at the top and moves down until it reaches the bottom, then moves up until it reaches the top, and repeats. A security scanner takes one picosecond to move one step. Drawing scanners as S, the first few picoseconds look like this:
Picosecond 0: 0 1 2 3 4 5 6 [S] [S] ... ... [S] ... [S] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Picosecond 1: 0 1 2 3 4 5 6 [ ] [ ] ... ... [ ] ... [ ] [S] [S] [S] [S] [ ] [ ] [ ] [ ] [ ]
Picosecond 2: 0 1 2 3 4 5 6 [ ] [S] ... ... [ ] ... [ ] [ ] [ ] [ ] [ ] [S] [S] [S] [ ] [ ]
Picosecond 3: 0 1 2 3 4 5 6 [ ] [ ] ... ... [ ] ... [ ] [S] [S] [ ] [ ] [ ] [ ] [ ] [S] [S] Your plan is to hitch a ride on a packet about to move through the firewall. The packet will travel along the top of each layer, and it moves at one layer per picosecond. Each picosecond, the packet moves one layer forward (its first move takes it into layer 0), and then the scanners move one step. If there is a scanner at the top of the layer as your packet enters it, you are caught. (If a scanner moves into the top of its layer while you are there, you are not caught: it doesn't have time to notice you before you leave.) If you were to do this in the configuration above, marking your current position with parentheses, your passage through the firewall would look like this:
Initial state: 0 1 2 3 4 5 6 [S] [S] ... ... [S] ... [S] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Picosecond 0: 0 1 2 3 4 5 6 (S) [S] ... ... [S] ... [S] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 ( ) [ ] ... ... [ ] ... [ ] [S] [S] [S] [S] [ ] [ ] [ ] [ ] [ ]
Picosecond 1: 0 1 2 3 4 5 6 [ ] ( ) ... ... [ ] ... [ ] [S] [S] [S] [S] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 [ ] (S) ... ... [ ] ... [ ] [ ] [ ] [ ] [ ] [S] [S] [S] [ ] [ ]
Picosecond 2: 0 1 2 3 4 5 6 [ ] [S] (.) ... [ ] ... [ ] [ ] [ ] [ ] [ ] [S] [S] [S] [ ] [ ]
0 1 2 3 4 5 6 [ ] [ ] (.) ... [ ] ... [ ] [S] [S] [ ] [ ] [ ] [ ] [ ] [S] [S]
Picosecond 3: 0 1 2 3 4 5 6 [ ] [ ] ... (.) [ ] ... [ ] [S] [S] [ ] [ ] [ ] [ ] [ ] [S] [S]
0 1 2 3 4 5 6 [S] [S] ... (.) [ ] ... [ ] [ ] [ ] [ ] [ ] [ ] [S] [S] [ ] [ ]
Picosecond 4: 0 1 2 3 4 5 6 [S] [S] ... ... ( ) ... [ ] [ ] [ ] [ ] [ ] [ ] [S] [S] [ ] [ ]
0 1 2 3 4 5 6 [ ] [ ] ... ... ( ) ... [ ] [S] [S] [S] [S] [ ] [ ] [ ] [ ] [ ]
Picosecond 5: 0 1 2 3 4 5 6 [ ] [ ] ... ... [ ] (.) [ ] [S] [S] [S] [S] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 [ ] [S] ... ... [S] (.) [S] [ ] [ ] [ ] [ ] [S] [ ] [ ] [ ] [ ]
Picosecond 6: 0 1 2 3 4 5 6 [ ] [S] ... ... [S] ... (S) [ ] [ ] [ ] [ ] [S] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 [ ] [ ] ... ... [ ] ... ( ) [S] [S] [S] [S] [ ] [ ] [ ] [ ] [ ] In this situation, you are caught in layers 0 and 6, because your packet entered the layer when its scanner was at the top when you entered it. You are not caught in layer 1, since the scanner moved into the top of the layer once you were already there.
The severity of getting caught on a layer is equal to its depth multiplied by its range. (Ignore layers in which you do not get caught.) The severity of the whole trip is the sum of these values. In the example above, the trip severity is 03 + 64 = 24.
Given the details of the firewall you've recorded, if you leave immediately, what is the severity of your whole trip?
In [ ]:
path = 'day13.txt'
with open(path, 'r') as file:
content = file.read().splitlines()
size = int((content[-1]).partition(':')[0]) + 1
print(size)
ranges = [0] * size
for index, value in enumerate(content):
depth = int((content[index]).partition(':')[0])
ranger = int((content[index]).partition(':')[2])
ranges[depth] = ranger
In [ ]:
def costOfScan(spot):
hit = (ranges[spot] - 1)*2
# print(spot, ranges[spot], spot % ranges[spot])
if (spot % hit) == 0:
return(spot * ranges[spot])
return(0)
myspot, cost = 0, 0
# Walk straight from 0 to size
# depending on where I am, check where the scanner is
# If I am entering a scanner, then calculate the cost
# Note: For both use cases the 0 spot is a hit (of 0)
for index, value in enumerate(ranges):
if value != 0:
cost = cost + costOfScan(index)
print("Severity : ", cost)
Advent of Code Day 13 - Part 2 Now, you need to pass through the firewall without being caught - easier said than done.
You can't control the speed of the packet, but you can delay it any number of picoseconds. For each picosecond you delay the packet before beginning your trip, all security scanners move one step. You're not in the firewall during this time; you don't enter layer 0 until you stop delaying the packet.
In the example above, if you delay 10 picoseconds (picoseconds 0 - 9), you won't get caught:
State after delaying: 0 1 2 3 4 5 6 [ ] [S] ... ... [ ] ... [ ] [ ] [ ] [ ] [ ] [S] [S] [S] [ ] [ ]
Picosecond 10: 0 1 2 3 4 5 6 ( ) [S] ... ... [ ] ... [ ] [ ] [ ] [ ] [ ] [S] [S] [S] [ ] [ ]
0 1 2 3 4 5 6 ( ) [ ] ... ... [ ] ... [ ] [S] [S] [S] [S] [ ] [ ] [ ] [ ] [ ]
Picosecond 11: 0 1 2 3 4 5 6 [ ] ( ) ... ... [ ] ... [ ] [S] [S] [S] [S] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 [S] (S) ... ... [S] ... [S] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Picosecond 12: 0 1 2 3 4 5 6 [S] [S] (.) ... [S] ... [S] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 [ ] [ ] (.) ... [ ] ... [ ] [S] [S] [S] [S] [ ] [ ] [ ] [ ] [ ]
Picosecond 13: 0 1 2 3 4 5 6 [ ] [ ] ... (.) [ ] ... [ ] [S] [S] [S] [S] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 [ ] [S] ... (.) [ ] ... [ ] [ ] [ ] [ ] [ ] [S] [S] [S] [ ] [ ]
Picosecond 14: 0 1 2 3 4 5 6 [ ] [S] ... ... ( ) ... [ ] [ ] [ ] [ ] [ ] [S] [S] [S] [ ] [ ]
0 1 2 3 4 5 6 [ ] [ ] ... ... ( ) ... [ ] [S] [S] [ ] [ ] [ ] [ ] [ ] [S] [S]
Picosecond 15: 0 1 2 3 4 5 6 [ ] [ ] ... ... [ ] (.) [ ] [S] [S] [ ] [ ] [ ] [ ] [ ] [S] [S]
0 1 2 3 4 5 6 [S] [S] ... ... [ ] (.) [ ] [ ] [ ] [ ] [ ] [ ] [S] [S] [ ] [ ]
Picosecond 16: 0 1 2 3 4 5 6 [S] [S] ... ... [ ] ... ( ) [ ] [ ] [ ] [ ] [ ] [S] [S] [ ] [ ]
0 1 2 3 4 5 6 [ ] [ ] ... ... [ ] ... ( ) [S] [S] [S] [S] [ ] [ ] [ ] [ ] [ ] Because all smaller delays would get you caught, the fewest number of picoseconds you would need to delay to get through safely is 10.
What is the fewest number of picoseconds that you need to delay the packet to pass through the firewall without being caught?
In [ ]:
def onScanner(spot, delay, hit):
if (spot + delay) % hit == 0:
# print("Hit: spot, time, hit", spot, delay, hit)
return(True)
else:
return(False)
def youSafe(scanners, delay):
for key, hit in scanners.items():
if onScanner(key, delay, hit):
return(False)
print("You are safe!!!! ", delay )
return(True)
In [ ]:
path = 'day13.txt'
delay = 0
with open(path, 'r') as file:
content = file.read().splitlines()
scanners = {}
myhits = set()
for index, value in enumerate(content):
hits = (int((content[index]).partition(':')[2]) -1 ) * 2
scanners[int((content[index]).partition(':')[0])] = hits
myhits.add(hits)
safe = False
while not safe:
delay += 1
safe = youSafe(scanners, delay)
if delay > 4941460:
print("This is not right")
break
print("Delay : ", delay)
Things I learned
Advent of Code Day 12 - Part 1 Walking along the memory banks of the stream, you find a small village that is experiencing a little confusion: some programs can't communicate with each other.
Programs in this village communicate using a fixed system of pipes. Messages are passed between programs using these pipes, but most programs aren't connected to each other directly. Instead, programs pass messages between each other until the message reaches the intended recipient.
For some reason, though, some of these messages aren't ever reaching their intended recipient, and the programs suspect that some pipes are missing. They would like you to investigate.
You walk through the village and record the ID of each program and the IDs with which it can communicate directly (your puzzle input). Each program has one or more programs with which it can communicate, and these pipes are bidirectional; if 8 says it can communicate with 11, then 11 will say it can communicate with 8.
You need to figure out how many programs are in the group that contains program ID 0.
For example, suppose you go door-to-door like a travelling salesman and record the following list:
0 <-> 2 1 <-> 1 2 <-> 0, 3, 4 3 <-> 2, 4 4 <-> 2, 3, 6 5 <-> 6 6 <-> 4, 5 In this example, the following programs are in the group that contains program ID 0:
Program 0 by definition. Program 2, directly connected to program 0. Program 3 via program 2. Program 4 via program 2. Program 5 via programs 6, then 4, then 2. Program 6 via programs 4, then 2. Therefore, a total of 6 programs are in this group; all but program 1, which has a pipe that connects it to itself.
How many programs are in the group that contains program ID 0?
In [ ]:
path = 'day12.txt'
with open(path, 'r') as file:
content = file.read().splitlines()
In [ ]:
# Can you get to 0 ?
# NOTE THIS DOES NOT WORK. It stops too shallow
def canCallZero(pipes, checked):
isconnected = False
isconnected = '0' in pipes
if not isconnected:
for x in pipes:
if x in checked:
return(False)
else:
checked.append(x)
if canCallZero(phonebank[int(x)], checked):
return(True)
return(isconnected)
# This works by walking the zero tree
def addToPartyLine(pipes,connected):
for x in pipes:
if x not in connected:
connected.append(x)
#print("Working on ", phonebank[int(x)])
addToPartyLine(phonebank[int(x)], connected)
return(connected)
In [ ]:
phonebank = []
for index, value in enumerate(content):
temp = value.replace(',','').rsplit(' ')
phonebank.append(temp[2:])
# print(phonebank)
count = 0
whosin = []
'''
# This does NOT work
for index, value in enumerate(phonebank):
if canCallZero(value,[]):
whosin.append(index)
count += 1
print("Total programs connected to Zero: ", count)
print(whosin)
'''
# This works
count = 1
connected = ['0']
connected = addToPartyLine(phonebank[0], connected)
print(len(connected), connected)
Advent of Code Day 12 - Part 2 There are more programs than just the ones in the group containing program ID 0. The rest of them have no way of reaching that group, and still might have no way of reaching each other.
A group is a collection of programs that can all communicate via pipes either directly or indirectly. The programs you identified just a moment ago are all part of the same group. Now, they would like you to determine the total number of groups.
In the example above, there were 2 groups: one consisting of programs 0,2,3,4,5,6, and the other consisting solely of program 1.
How many groups are there in total?
In [ ]:
phonebank = []
for index, value in enumerate(content):
temp = value.replace(',','').rsplit(' ')
phonebank.append(temp[2:])
# print(phonebank)
whosin = []
count = 0
for index, value in enumerate(phonebank):
if str(index) not in whosin:
count += 1
connected = [str(index)] # we know it is connected to itself
whosin.extend( addToPartyLine(phonebank[index], connected))
# print(whosin)
print("Total number of independent rings:", count)
What I learned
Advent of Code Day 11 - Part 1 Crossing the bridge, you've barely reached the other side of the stream when a program comes up to you, clearly in distress. "It's my child process," she says, "he's gotten lost in an infinite grid!"
Fortunately for her, you have plenty of experience with infinite grids.
Unfortunately for you, it's a hex grid.
The hexagons ("hexes") in this grid are aligned such that adjacent hexes can be found to the north, northeast, southeast, south, southwest, and northwest:
\ n / nw +--+ ne / \ -+ +- \ / sw +--+ se / s \ You have the path the child process took. Starting where he started, you need to determine the fewest number of steps required to reach him. (A "step" means to move from the hex you are in to any adjacent hex.)
For example:
ne,ne,ne is 3 steps away. ne,ne,sw,sw is 0 steps away (back where you started). ne,ne,s,s is 2 steps away (se,se). se,sw,se,sw,sw is 3 steps away (s,s,sw).
In [ ]:
puzzle = open('day11.txt', 'r').read()
test1 = 'ne,ne,ne' # is 3 steps away.
test2 = 'ne,ne,sw,sw' # is 0 steps away (back where you started).
test3 = 'ne,ne,s,s' # is 2 steps away (se,se).
test4 = 'se,sw,se,sw,sw' # is 3 steps away (s,s,sw).
In [ ]:
# Thanks to Charles Fu, I am going to divide up the grid into three, 120 degree coordinates
# North - X does not move, Y +, Z -
# South - X does not move, Y -, Z +
# NE - X +, Y does not move, Z -
# SE - X +, Y -, Z does not move
# NW - X - , Y +, Z does not move
# SW - X -, Y does not move, Z +
path = puzzle.split(",")
x, y, z = 0,0,0
for value in path:
if value == 'n':
x,y,z = x, y+1, z-1
elif value == 's':
x,y,z = x, y-1, z+1
elif value == 'ne':
x,y,z = x+1, y, z-1
elif value == 'se':
x,y,z = x+1, y-1, z
elif value == 'nw':
x,y,z = x-1, y+1, z
elif value == 'sw':
x,y,z = x-1, y, z+1
else:
print("Something went wrong with the parsing")
print(x,y,z)
# Distance is 1/2 * (|x| + |y|+ |z|) since we started at 0,0,0
distance = .5 * (abs(x) + abs(y) + abs(z))
print(distance)
Advent of Code Day 11 - Part 2 How many steps away is the furthest he ever got from his starting position
In [ ]:
# see above for this logic
path = puzzle.split(",")
distance, furthest = 0,0
x, y, z = 0,0,0
for value in path:
if value == 'n':
x,y,z = x, y+1, z-1
elif value == 's':
x,y,z = x, y-1, z+1
elif value == 'ne':
x,y,z = x+1, y, z-1
elif value == 'se':
x,y,z = x+1, y-1, z
elif value == 'nw':
x,y,z = x-1, y+1, z
elif value == 'sw':
x,y,z = x-1, y, z+1
else:
print("Something went wrong with the parsing")
# How far did he go? Did he go further?
distance = .5 * (abs(x) + abs(y) + abs(z))
furthest = max(distance, furthest)
print("Where he is now ", distance)
print("Furthest He went ", furthest)
What I learned
Advent of Code Day 10 - Part 1 You come across some programs that are trying to implement a software emulation of a hash based on knot-tying. The hash these programs are implementing isn't very strong, but you decide to help them anyway. You make a mental note to remind the Elves later not to invent their own cryptographic functions.
This hash function simulates tying a knot in a circle of string with 256 marks on it. Based on the input to be hashed, the function repeatedly selects a span of string, brings the ends together, and gives the span a half-twist to reverse the order of the marks within it. After doing this many times, the order of the marks is used to build the resulting hash.
4--5 pinch 4 5 4 1 / \ 5,0,1 / \/ \ twist / \ / \ 3 0 --> 3 0 --> 3 X 0 \ / \ /\ / \ / \ / 2--1 2 1 2 5 To achieve this, begin with a list of numbers from 0 to 255, a current position which begins at 0 (the first element in the list), a skip size (which starts at 0), and a sequence of lengths (your puzzle input). Then, for each length:
The list is circular; if the current position and the length try to reverse elements beyond the end of the list, the operation reverses using as many extra elements as it needs from the front of the list. If the current position moves past the end of the list, it wraps around to the front. Lengths larger than the size of the list are invalid.
Here's an example using a smaller list:
Suppose we instead only had a circular list containing five elements, 0, 1, 2, 3, 4, and were given input lengths of 3, 4, 1, 5.
In this example, the first two numbers in the list end up being 3 and 4; to check the process, you can multiply them together to produce 12.
However, you should instead use the standard list size of 256 (with values 0 to 255) and the sequence of lengths in your puzzle input. Once this process is complete, what is the result of multiplying the first two numbers in the list?
In [ ]:
import numpy as np
puzzle = [18,1,0,161,255,137,254,252,14,95,165,33,181,168,2,188]
size = 256
test = [3, 4, 1, 5]
size = 5
In [ ]:
current, jump, skip = 0, 0, 0
# lengths, size = test , 5
lengths, size = puzzle, 256
knot = list(range(size))
# print("Start", knot, "/n")
def flipslice():
piece = knot[current:current+length] # This will go to the end
#Check if we got it all
if (current + length) > size:
piece = piece + knot[:(length - len(piece))]
for index, value in enumerate(reversed(piece)):
knot[(current+index)%size] = value
#print("Knot after flip ", knot)
for length in lengths:
# print("Working with length ", length, "skip ", skip, "current ", current)
jump = (skip + length)
if length > size:
print("We are twisting more then the whole list ... TWF", length, size)
else:
flipslice()
current = (current + jump) % size
skip += 1
# print("End", knot)
print("Answer: ", knot[0]*knot[1])
In [ ]:
# Trying to use numpy wrap is warping my brain!!
# TODO BAD CODE
current, jump, skip = 0, 0, 0
lengths, size = test , 5
knot = np.arange(size)
print(knot)
for length in lengths:
print("Working with length ", length, "skip ", skip, "current ", current)
jump = (skip + length)
piece = knot.take(range(current,jump), mode="wrap")[::-1]
print("piece = ", piece)
knot
current = (current + jump) % size
skip += 1 # At the end you increment
Advent of Code Day 10 - Part 2 he logic you've constructed forms a single round of the Knot Hash algorithm; running the full thing requires many of these rounds. Some input and output processing is also required.
First, from now on, your input should be taken not as a list of numbers, but as a string of bytes instead. Unless otherwise specified, convert characters to bytes using their ASCII codes. This will allow you to handle arbitrary ASCII strings, and it also ensures that your input lengths are never larger than 255. For example, if you are given 1,2,3, you should convert it to the ASCII codes for each character: 49,44,50,44,51.
Once you have determined the sequence of lengths to use, add the following lengths to the end of the sequence: 17, 31, 73, 47, 23. For example, if you are given 1,2,3, your final sequence of lengths should be 49,44,50,44,51,17,31,73,47,23 (the ASCII codes from the input string combined with the standard length suffix values).
Second, instead of merely running one round like you did above, run a total of 64 rounds, using the same length sequence in each round. The current position and skip size should be preserved between rounds. For example, if the previous example was your first round, you would start your second round with the same length sequence (3, 4, 1, 5, 17, 31, 73, 47, 23, now assuming they came from ASCII codes and include the suffix), but start with the previous round's current position (4) and skip size (4).
Once the rounds are complete, you will be left with the numbers from 0 to 255 in some order, called the sparse hash. Your next task is to reduce these to a list of only 16 numbers called the dense hash. To do this, use numeric bitwise XOR to combine each consecutive block of 16 numbers in the sparse hash (there are 16 such blocks in a list of 256 numbers). So, the first element in the dense hash is the first sixteen elements of the sparse hash XOR'd together, the second element in the dense hash is the second sixteen elements of the sparse hash XOR'd together, etc.
For example, if the first sixteen elements of your sparse hash are as shown below, and the XOR operator is ^, you would calculate the first output number like this:
65 ^ 27 ^ 9 ^ 1 ^ 4 ^ 3 ^ 40 ^ 50 ^ 91 ^ 7 ^ 6 ^ 0 ^ 2 ^ 5 ^ 68 ^ 22 = 64 Perform this operation on each of the sixteen blocks of sixteen numbers in your sparse hash to determine the sixteen numbers in your dense hash.
Finally, the standard way to represent a Knot Hash is as a single hexadecimal string; the final output is the dense hash in hexadecimal notation. Because each number in your dense hash will be between 0 and 255 (inclusive), always represent each number as two hexadecimal digits (including a leading zero as necessary). So, if your first three numbers are 64, 7, 255, they correspond to the hexadecimal numbers 40, 07, ff, and so the first six characters of the hash would be 4007ff. Because every Knot Hash is sixteen such numbers, the hexadecimal representation is always 32 hexadecimal digits (0-f) long.
Here are some example hashes:
The empty string becomes a2582a3a0e66e6e86e3812dcb672a272. AoC 2017 becomes 33efeb34ea91902bb2f59c9920caa6cd. 1,2,3 becomes 3efbe78a8d82f29979031a4aa0b16a9d. 1,2,4 becomes 63960835bcdc130f0b66d7ff4f6a5a8e. Treating your puzzle input as a string of ASCII characters, what is the Knot Hash of your puzzle input? Ignore any leading or trailing whitespace you might encounter.
In [ ]:
puzzle = '18,1,0,161,255,137,254,252,14,95,165,33,181,168,2,188'
puzzle = '1,2,4'
size = 256
In [ ]:
def convertToAscii(data):
print(" data going in", puzzle)
newdata =[]
for x in data:
newdata.append(ord(x))
return(newdata)
def flipslice():
piece = knot[current:current+length] # This will go to the end
#Check if we got it all
if (current + length) > size:
piece = piece + knot[:(length - len(piece))]
for index, value in enumerate(reversed(piece)):
knot[(current+index)%size] = value
#print("Knot after flip ", knot)
def createdensehash(block):
dhash = 0
for x in block:
dhash = x ^ dhash
return(dhash)
In [ ]:
# First, convert input to asci + add special
current, jump, skip = 0, 0, 0
densehash = []
size = 256
knot = list(range(size))
lengths = convertToAscii(puzzle)
lengths = lengths + [17, 31, 73, 47, 23]
# print("The input sequence:", lengths)
# Second, has this 64 times without resetting the ski and current
for x in range(64):
for length in lengths:
# print("Working with length ", length, "skip ", skip, "current ", current)
jump = (skip + length)
if length > size:
print("We are twisting more then the whole list ... TWF", length, size)
else:
flipslice()
current = (current + jump) % size
skip += 1
print("The sparse hash after 64 rounds ", knot)
# Third, create a dense hash
for i in range(0,256,16):
densehash.append(createdensehash(knot[i:i+16]))
print(densehash)
# Finally change the values to hexadecimal
answer = ''
for x in densehash:
answer = answer + (format(x, '02x'))
print(answer)
What I learned
Advent of Code Day 9 - Part 1 A large stream blocks your path. According to the locals, it's not safe to cross the stream at the moment because it's full of garbage. You look down at the stream; rather than water, you discover that it's a stream of characters.
You sit for a while and record part of the stream (your puzzle input). The characters represent groups - sequences that begin with { and end with }. Within a group, there are zero or more other things, separated by commas: either another group or garbage. Since groups can contain other groups, a } only closes the most-recently-opened unclosed group - that is, they are nestable. Your puzzle input represents a single, large group which itself contains many smaller ones.
Sometimes, instead of a group, you will find garbage. Garbage begins with < and ends with >. Between those angle brackets, almost any character can appear, including { and }. Within garbage, < has no special meaning.
In a futile attempt to clean up the garbage, some program has canceled some of the characters within it using !: inside garbage, any character that comes after ! should be ignored, including <, >, and even another !.
You don't see any characters that deviate from these rules. Outside garbage, you only find well-formed groups, and garbage always terminates according to the rules above.
Here are some self-contained pieces of garbage:
<>, empty garbage.
{}, 1 group. {{{}}}, 3 groups. {{},{}}, also 3 groups. {{{},{},{{}}}}, 6 groups. {<{},{},{{}}>}, 1 group (which itself contains garbage). {,,,}, 1 group. {{},{},{},{}}, 5 groups. {{<!>},{<!>},{<!>},{}}, 2 groups (since all but the last > are canceled). Your goal is to find the total score for all groups in your input. Each group is assigned a score which is one more than the score of the group that immediately contains it. (The outermost group gets a score of 1.)
{}, score of 1.
{{{}}}, score of 1 + 2 + 3 = 6.
{{},{}}, score of 1 + 2 + 2 = 5.
{{{},{},{{}}}}, score of 1 + 2 + 3 + 3 + 3 + 4 = 16.
{,,,}, score of 1.
{{
In [ ]:
# get input
test1 = '{}' # 1 group, score 1
test2 = '{{{}}}' # 3 group
test3 = '{{},{}}' # 3 group
test4 = '{{{},{},{{}}}}' # 3 group
test5 = '{<a>,<a>,<a>,<a>}' # 3 group
test6 = '{{<ab>},{<ab>},{<ab>},{<ab>}}' # 3 group
test7 = '{{<!!>},{<!!>},{<!!>},{<!!>}}'
test8 = '{{<a!>},{<a!>},{<a!>},{<ab>}}'
puzzle = open('day09.txt', 'r').read() # Read as a string
In [ ]:
# Loop through the string counting the nest while ignoring the garbage along the way
score = 0
opengroups = 0
prev = '' # This is a hack for the '!', fix later todo
stream = puzzle
isgarbage = False
for index, value in enumerate(stream):
if prev == '!':
prev = ''
elif value == '!':
prev = '!'
elif value == '{' and isgarbage == False:
opengroups += 1
score = score + opengroups # todo check this
elif value == '}' and isgarbage == False:
opengroups -= 1
elif value == '<' and isgarbage == False:
isgarbage = True
elif value == '>':
isgarbage = False
print("Open groups (should be 0) = ", opengroups)
print("Total groups = ", score)
Advent of Code Day 9 - Part 2 Now, you're ready to remove the garbage.
To prove you've removed it, you need to count all of the characters within the garbage. The leading and trailing < and > don't count, nor do any canceled characters or the ! doing the canceling.
<>, 0 characters.
In [ ]:
%%timeit
# Loop through the string counting the nest while ignoring the garbage along the way
# original (with enumerate)
heftybags = 0
prev = '' # This is a hack for the '!', fix later todo
stream = puzzle
isgarbage = False
for index, value in enumerate(stream):
if prev == '!':
prev = ''
elif value == '!':
prev = '!'
elif value == '<' and isgarbage == False:
isgarbage = True
elif value == '>':
isgarbage = False
elif isgarbage == True:
heftybags += 1
#print("Total Garbage ",heftybags )
In [ ]:
%%timeit
# Loop through the string counting the nest while ignoring the garbage along the way
# what if we just use a loop
heftybags = 0
prev = '' # This is a hack for the '!', fix later todo
stream = puzzle
isgarbage = False
for value in stream:
if prev == '!':
prev = ''
elif value == '!':
prev = '!'
elif value == '<' and isgarbage == False:
isgarbage = True
elif value == '>':
isgarbage = False
elif isgarbage == True:
heftybags += 1
In [ ]:
%%timeit
# Get out early
# What if we optimize what we check
heftybags = 0
prev = '' # This is a hack for the '!', fix later todo
stream = puzzle
isgarbage = False
for value in stream:
if isgarbage:
if prev == '!':
prev = ''
elif value == '!':
prev = '!'
elif value == '>':
isgarbage = False
else:
heftybags += 1
else: # not garbage ignore unless starting garbage '<'
if value == '<':
isgarbage = True
# print(heftybags)
What I learned
Advent of Code Day 8 You receive a signal directly from the CPU. Because of your recent assistance with jump instructions, it would like you to compute the result of a series of unusual register instructions.
Each instruction consists of several parts: the register to modify, whether to increase or decrease that register's value, the amount by which to increase or decrease it, and a condition. If the condition fails, skip the instruction without modifying the register. The registers all start at 0. The instructions look like this:
b inc 5 if a > 1 a inc 1 if b < 5 c dec -10 if a >= 1 c inc -20 if c == 10 These instructions would be processed as follows:
Because a starts at 0, it is not greater than 1, and so b is not modified. a is increased by 1 (to 1) because b is less than 5 (it is 0). c is decreased by -10 (to 10) because a is now greater than or equal to 1 (it is 1). c is increased by -20 (to -10) because c is equal to 10. After this process, the largest value in any register is 1.
You might also encounter <= (less than or equal to) or != (not equal to). However, the CPU doesn't have the bandwidth to tell you what all the registers are named, and leaves that to you to determine.
What is the largest value in any register after completing the instructions in your puzzle input?
In [ ]:
path = 'day08.txt'
f = open(path, 'r')
content = f.read()
In [ ]:
f.seek(0)
tempreg = set() # use set to remove dups
instructions = []
temp = []
for line in f:
temp = line.rstrip('').replace('\n','').split(" ")
instructions.append(temp)
tempreg.add(temp[0])
tempreg.add(temp[4])
registers = dict.fromkeys(tempreg,0)
#print(registers)
#print(instructions)
for index, value in enumerate(instructions):
exp1 = "if registers[\'" + value[4] + "'] " + value[5] + " " + value[6] +':'
exp2 = " registers[\'" + value[0] + "'] "
if value[1] == 'inc':
exp3 = ' += ' + value[2]
else:
exp3 = ' -= ' + value[2]
exp = exp1 + exp2 + exp3
# print(exp)
exec(exp)
# print(registers)
mymax = max(registers, key=registers.get)
print("Largest value in a registry", registers[mymax])
Advent of Code - Day 8 Part 2 To be safe, the CPU also needs to know the highest value held in any register during this process so that it can decide how much memory to allocate to these operations. For example, in the above instructions, the highest value ever held was 10 (in register c after the third instruction was evaluated).
In [ ]:
f.seek(0)
tempreg = set() # use set to remove dups
instructions = []
temp = []
for line in f:
temp = line.rstrip('').replace('\n','').split(" ")
instructions.append(temp)
tempreg.add(temp[0])
tempreg.add(temp[4])
registers = dict.fromkeys(tempreg,0)
mymax = registers[max(registers, key=registers.get)]
print("My Max at the start ", mymax)
for index, value in enumerate(instructions):
exp1 = "if registers[\'" + value[4] + "'] " + value[5] + " " + value[6] +':'
exp2 = " registers[\'" + value[0] + "'] "
if value[1] == 'inc':
exp3 = ' += ' + value[2]
else:
exp3 = ' -= ' + value[2]
exp = exp1 + exp2 + exp3
exec(exp)
if mymax < registers[max(registers, key=registers.get)]:
mymax = registers[max(registers, key=registers.get)]
# print(registers)
print("Largest value in a registry", mymax)
What I learned from Day 8 ...
Advent of Code Day 7 - Part 1 Wandering further through the circuits of the computer, you come upon a tower of programs that have gotten themselves into a bit of trouble. A recursive algorithm has gotten out of hand, and now they're balanced precariously in a large tower.
One program at the bottom supports the entire tower. It's holding a large disc, and on the disc are balanced several more sub-towers. At the bottom of these sub-towers, standing on the bottom disc, are other programs, each holding their own disc, and so on. At the very tops of these sub-sub-sub-...-towers, many programs stand simply keeping the disc below them balanced but with no disc of their own.
You offer to help, but first you need to understand the structure of these towers. You ask each program to yell out their name, their weight, and (if they're holding a disc) the names of the programs immediately above them balancing on that disc. You write this information down (your puzzle input). Unfortunately, in their panic, they don't do this in an orderly fashion; by the time you're done, you're not sure which program gave which information.
For example, if your list is the following:
pbga (66) xhth (57) ebii (61) havc (66) ktlj (57) fwft (72) -> ktlj, cntj, xhth qoyq (66) padx (45) -> pbga, havc, qoyq tknk (41) -> ugml, padx, fwft jptl (61) ugml (68) -> gyxo, ebii, jptl gyxo (61) cntj (57) ...then you would be able to recreate the structure of the towers that looks like this:
gyxo
/
ugml - ebii
/ \
| jptl
|
| pbga
/ /
tknk --- padx - havc
\ \
| qoyq
|
| ktlj
\ /
fwft - cntj
\
xhth
In this example, tknk is at the bottom of the tower (the bottom program), and is holding up ugml, padx, and fwft. Those programs are, in turn, holding up other programs; in this example, none of those programs are holding up any other programs, and are all the tops of their own towers. (The actual tower balancing in front of you is much larger.)
Before you're ready to help them, you need to make sure your information is correct. What is the name of the bottom program?
In [ ]:
path = 'day07.txt'
f = open(path, 'r')
import copy
content = f.read()
In [ ]:
f.seek(0)
subTowers = {}
bottom = ''
for line in f:
temp = line.rstrip('').replace(',','').replace('\n','').split(" ")
if '->' in temp:
# print(" the carrot is at ", temp.index('->')) #going to be 2
subTowers[temp[0]] = temp[3:]
# print("The number of subtowers = ", st, subTowers)
for key, na in subTowers.items():
# is key in any other val?
bottom = key
# print(key, " Looking for this item")
for iKey, iVal in subTowers.items():
#print(" Looking inside ", b, " for this key ", key)
if key in iVal: # todo this is broken after 1st time!
bottom = 'nope'
#print(" Found it in ", iVal)
break
if bottom != 'nope':
print("Got it! ", key)
break
# I should break out of something here
# need a break when we find bottom todo
print(bottom)
Advent of Code Day 7 - Part 2 The programs explain the situation: they can't get down. Rather, they could get down, if they weren't expending all of their energy trying to keep the tower balanced. Apparently, one program has the wrong weight, and until it's fixed, they're stuck here.
For any program holding a disc, each program standing on that disc forms a sub-tower. Each of those sub-towers are supposed to be the same weight, or the disc itself isn't balanced. The weight of a tower is the sum of the weights of the programs in that tower.
In the example above, this means that for ugml's disc to be balanced, gyxo, ebii, and jptl must all have the same weight, and they do: 61.
However, for tknk to be balanced, each of the programs standing on its disc and all programs above it must each match. This means that the following sums must all be the same:
ugml + (gyxo + ebii + jptl) = 68 + (61 + 61 + 61) = 251 padx + (pbga + havc + qoyq) = 45 + (66 + 66 + 66) = 243 fwft + (ktlj + cntj + xhth) = 72 + (57 + 57 + 57) = 243 As you can see, tknk's disc is unbalanced: ugml's stack is heavier than the other two. Even though the nodes above ugml are balanced, ugml itself is too heavy: it needs to be 8 units lighter for its stack to weigh 243 and keep the towers balanced. If this change were made, its weight would be 60.
Given that exactly one program is the wrong weight, what would its weight need to be to balance the entire tower?
In [ ]:
f.seek(0)
weights = {}
for line in f:
temp = line.rstrip('').replace(',','').replace('\n','').split(" ")
if '->' in temp:
weights[temp[0]] = temp[3:]
weights[temp[0]].append(int(temp[1].replace('(','').replace(')','')))
else:
weights[temp[0]] = int(temp[1].replace('(','').replace(')',''))
ow = copy.deepcopy(weights)
# print(weights)
def totalWeight(akey):
if isinstance(weights[akey], int):
return(weights[akey])
else:
total = weights[akey][-1]
nodes = {}
for i in weights[akey][:-1]:
weight = totalWeight(i)
total = total + weight
nodes[i] = weight # ugh
weights[akey] = total
# are all the nodes equal?
if not all(value == weight for value in nodes.values()):
print("We have a bad set: ", nodes, "in key ", akey)
# Can I stop at the first one?
# It will be the big one
mymin = min(nodes, key=nodes.get)
mymax = max(nodes, key=nodes.get)
delta = nodes[mymax] - nodes[mymin]
print("Answer is ", ow[mymax][-1] - delta, "node ", mymax)
return total
totalWeight('mwzaxaj')
# totalWeight('tknk')
What I learned on Day 7
Advent of Code Day 6 - Part 1 A debugger program here is having an issue: it is trying to repair a memory reallocation routine, but it keeps getting stuck in an infinite loop.
In this area, there are sixteen memory banks; each memory bank can hold any number of blocks. The goal of the reallocation routine is to balance the blocks between the memory banks.
The reallocation routine operates in cycles. In each cycle, it finds the memory bank with the most blocks (ties won by the lowest-numbered memory bank) and redistributes those blocks among the banks. To do this, it removes all of the blocks from the selected bank, then moves to the next (by index) memory bank and inserts one of the blocks. It continues doing this until it runs out of blocks; if it reaches the last memory bank, it wraps around to the first one.
The debugger would like to know how many redistributions can be done before a blocks-in-banks configuration is produced that has been seen before.
For example, imagine a scenario with only four memory banks:
The banks start with 0, 2, 7, and 0 blocks. The third bank has the most blocks, so it is chosen for redistribution. Starting with the next bank (the fourth bank) and then continuing to the first bank, the second bank, and so on, the 7 blocks are spread out over the memory banks. The fourth, first, and second banks get two blocks each, and the third bank gets one back. The final result looks like this: 2 4 1 2. Next, the second bank is chosen because it contains the most blocks (four). Because there are four memory banks, each gets one block. The result is: 3 1 2 3. Now, there is a tie between the first and fourth memory banks, both of which have three blocks. The first bank wins the tie, and its three blocks are distributed evenly over the other three banks, leaving it with none: 0 2 3 4. The fourth bank is chosen, and its four blocks are distributed such that each of the four banks receives one: 1 3 4 1. The third bank is chosen, and the same thing happens: 2 4 1 2. At this point, we've reached a state we've seen before: 2 4 1 2 was already seen. The infinite loop is detected after the fifth block redistribution cycle, and so the answer in this example is 5.
Given the initial block counts in your puzzle input, how many redistribution cycles must be completed before a configuration is produced that has been seen before?
In [ ]:
path = 'day06.txt'
f = open(path, 'r')
content = f.read()
banks = [int(n) for n in content.split()]
size = len(banks)
print(banks, size)
In [ ]:
final = []
banks = [int(n) for n in content.split()]
state = ''.join(str(e) for e in banks)
count = 0
while state not in final:
final.append(''.join(str(e) for e in banks)) #put the state in final
bigindex = banks.index(max(banks))
bigvalue = banks[bigindex]
banks[bigindex] = 0
for x in range(bigvalue):
next = bigindex + x + 1 # think about why +1
banks[next % size] += 1
state = ''.join(str(e) for e in banks)
count = count + 1
# print('bigindex', bigindex, 'bigvalue', bigvalue, banks, state, 'count ', count)
print('Repeater ', state)
print("Count von Count ", count)
Advent of Code Day 6 - Part 2 Out of curiosity, the debugger would also like to know the size of the loop: starting from a state that has already been seen, how many block redistribution cycles must be performed before that same state is seen again?
In the example above, 2 4 1 2 is seen again after four cycles, and so the answer in that example would be 4.
How many cycles are in the infinite loop that arises from the configuration in your puzzle input?
In [ ]:
repeater = state
state = ''
print('Repeater ', repeater, "banks ", banks)
count = 0
while state != repeater:
bigindex = banks.index(max(banks))
bigvalue = banks[bigindex]
banks[bigindex] = 0
for x in range(bigvalue):
next = bigindex + x + 1 # think about why +1
banks[next % size] += 1
state = ''.join(str(e) for e in banks)
count = count + 1
print('Count von Count ', count, 'state ', state, 'repeater ', repeater)
What I've learned:
Advent of Code Day 5 - Part 1 An urgent interrupt arrives from the CPU: it's trapped in a maze of jump instructions, and it would like assistance from any programs with spare cycles to help find the exit.
The message includes a list of the offsets for each jump. Jumps are relative: -1 moves to the previous instruction, and 2 skips the next one. Start at the first instruction in the list. The goal is to follow the jumps until one leads outside the list.
In addition, these instructions are a little strange; after each jump, the offset of that instruction increases by 1. So, if you come across an offset of 3, you would move three instructions forward, but change it to a 4 for the next time it is encountered.
For example, consider the following list of jump offsets:
0 3 0 1 -3 Positive jumps ("forward") move downward; negative jumps move upward. For legibility in this example, these offset values will be written all on one line, with the current instruction marked in parentheses. The following steps would be taken before an exit is found:
(0) 3 0 1 -3 - before we have taken any steps. (1) 3 0 1 -3 - jump with offset 0 (that is, don't jump at all). Fortunately, the instruction is then incremented to 1. 2 (3) 0 1 -3 - step forward because of the instruction we just modified. The first instruction is incremented again, now to 2. 2 4 0 1 (-3) - jump all the way to the end; leave a 4 behind. 2 (4) 0 1 -2 - go back to where we just were; increment -3 to -2. 2 5 0 1 -2 - jump 4 steps forward, escaping the maze. In this example, the exit is reached in 5 steps.
How many steps does it take to reach the exit?
In [ ]:
# use numpy for efficiency and performance?
import numpy as np
path = 'day05a.txt'
f = open(path, 'r')
content = f.read().rstrip().split('\n')
content = [ int(x) for x in content]
print(content)
In [ ]:
a = np.array(content, dtype=int)
In [ ]:
steps = 0
index = 0
jump = 0
a = np.array(content, dtype=int)
while True:
try:
jump = a[index]
a[index] = a[index] + 1
index = index + jump
steps = steps + 1
except:
print("I think we escapted ", steps)
break
Advent of Code Day 5 - Part 2 Now, the jumps are even stranger: after each jump, if the offset was three or more, instead decrease it by 1. Otherwise, increase it by 1 as before.
Using this rule with the above example, the process now takes 10 steps, and the offset values after finding the exit are left as 2 3 2 3 -1.
How many steps does it now take to reach the exit?
In [ ]:
steps = 0
index = 0
jump = 0
a = np.array(content, dtype=int)
while True:
try:
jump = a[index]
if jump >= 3:
a[index] = a[index] - 1
else:
a[index] = a[index] + 1
index = index + jump
steps = steps + 1
except:
print("I think we escapted ", steps)
break
What I learned Day 5
Advent of Code Day 4 - Part 1 A new system policy has been put in place that requires all accounts to use a passphrase instead of simply a password. A passphrase consists of a series of words (lowercase letters) separated by spaces.
To ensure security, a valid passphrase must contain no duplicate words.
For example:
aa bb cc dd ee is valid. aa bb cc dd aa is not valid - the word aa appears more than once. aa bb cc dd aaa is valid - aa and aaa count as different words. The system's full passphrase list is available as your puzzle input. How many passphrases are valid?
In [ ]:
# read a line from a file to a list and set
# compare size
import os
path = 'day04.txt'
f = open(path, 'r')
content = f.read()
In [ ]:
f.seek(0)
total = 0
temp = []
for line in f:
temp = line.rstrip().split(" ")
myset = set(temp)
if len(temp) == len(myset):
total = total + 1
# print(temp, listlen, myset, setlen)
print(total)
Advent of Code - Day 4 - Part 2 For added security, yet another system policy has been put in place. Now, a valid passphrase must contain no two words that are anagrams of each other - that is, a passphrase is invalid if any word's letters can be rearranged to form any other word in the passphrase.
For example:
abcde fghij is a valid passphrase. abcde xyz ecdab is not valid - the letters from the third word can be rearranged to form the first word. a ab abc abd abf abj is a valid passphrase, because all letters need to be used when forming another word. iiii oiii ooii oooi oooo is valid. oiii ioii iioi iiio is not valid - any of these words can be rearranged to form any other word. Under this new system policy, how many passphrases are valid?
In [ ]:
%%timeit
# Get the line. (don't have to) Take out any with repeaters
f.seek(0)
total = 0
%timeit -n 3
for line in f:
temp = line.rstrip().split(" ")
myset.clear()
for word in temp:
word = ''.join(sorted(word))
myset.add(word)
if len(myset) == len(temp):
total = total + 1
%lsmagic
What I learned from Day 4:
Advent of Code - Day 3 - Part 1 You come across an experimental new kind of memory stored on an infinite two-dimensional grid.
Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then counting up while spiraling outward. For example, the first few squares are allocated like this:
17 16 15 14 13 18 5 4 3 12 19 6 1 2 11 20 7 8 9 10 21 22 23---> ... While this is very space-efficient (no squares are skipped), requested data must be carried back to square 1 (the location of the only access port for this memory system) by programs that can only move up, down, left, or right. They always take the shortest path: the Manhattan Distance between the location of the data and square 1.
For example:
Data from square 1 is carried 0 steps, since it's at the access port. Data from square 12 is carried 3 steps, such as: down, left, left. Data from square 23 is carried only 2 steps: up twice. Data from square 1024 must be carried 31 steps. How many steps are required to carry the data from the square identified in your puzzle input all the way to the access port?
In [ ]:
import math
In [ ]:
port = 1 # ring = 0 , moves = 1 , rows 1
port = 15 #ring 2, moves 2, row 5
port = 47 # ring 3, moves 4, row 7
port = 1024 # ring 16, moves 31, row ?
port = 23 # ring 2, moves 2
port = 12 # ring
port = 361527
ring = 0
rowlen = 0
high = 0
rowlen = math.ceil(math.sqrt(port)) # Hmmm ... this might not be right if even
if rowlen % 2 == 0:
rowlen = rowlen + 1
high = math.pow(rowlen, 2)
ring = (rowlen -1)/2
offset = (ring -(high - port))%ring
print('The port ', port, 'is on ring ', ring, ' row of length ', rowlen, ' high num of ', high, ' offset of ', offset)
moves = ring + offset
print("Moves of ", moves, " from the port ", port)
Advent of Code - Day 3 - Part 2 As a stress test on the system, the programs here clear the grid and then store the value 1 in square 1. Then, in the same allocation order as shown above, they store the sum of the values in all adjacent squares, including diagonals.
So, the first few squares' values are chosen as follows:
Square 1 starts with the value 1. Square 2 has only one adjacent filled square (with value 1), so it also stores 1. Square 3 has both of the above squares as neighbors and stores the sum of their values, 2. Square 4 has all three of the aforementioned squares as neighbors and stores the sum of their values, 4. Square 5 only has the first and fourth squares as neighbors, so it gets the value 5. Once a square is written, its value does not change. Therefore, the first few squares would receive the following values:
147 142 133 122 59 304 5 4 2 57 330 10 1 1 54 351 11 23 25 26 362 747 806---> ... What is the first value written that is larger than your puzzle input? 361527
In [ ]:
# I cheated and went to this page - https://oeis.org/A141481
import pandas as pd
In [ ]:
# now with an array
# create a 5x5 array
# This is boring me ... not done
myzero = 2
ring = 0
myarray = [[0] * 5] * 5
print(myarray)
mydf = pd.DataFrame(myarray)
mydf.at[myzero,myzero] = 1
done = True
# loop here
while done == True:
ring = ring + 1
x = myzero
y = myzero + ring
mydf.at[x,y] = mydf.at[x,y-1] + mydf.at[x-1,y] + mydf.at[x,y+1 ]
done = False
mydf
Advent of Code - Day 2 - Part 1 As you walk through the door, a glowing humanoid shape yells in your direction. "You there! Your state appears to be idle. Come help us repair the corruption in this spreadsheet - if we take another millisecond, we'll have to display an hourglass cursor!"
The spreadsheet consists of rows of apparently-random numbers. To make sure the recovery process is on the right track, they need you to calculate the spreadsheet's checksum. For each row, determine the difference between the largest value and the smallest value; the checksum is the sum of all of these differences.
For example, given the following spreadsheet:
5 1 9 5 7 5 3 2 4 6 8 The first row's largest and smallest values are 9 and 1, and their difference is 8. The second row's largest and smallest values are 7 and 3, and their difference is 4. The third row's difference is 6. In this example, the spreadsheet's checksum would be 8 + 4 + 6 = 18.
In [ ]:
# data is at https://adventofcode.com/2017/day/2/input
# Get a row (?Do I use Beautiful Soup? )
# Find the largest, find the smallest,
#Add the difference to the total
import os
path = 'input.txt'
# path = 'input2.txt'
f = open(path, 'r')
content = f.read()
In [ ]:
f.seek(0)
total = 0
for line in f:
values = [int(n) for n in line.split()]
low = values[0]
high = values[0]
for x in values:
if x > high:
high = x
if x < low:
low = x
# print('high ', high, ' low ', low )
total = total + (high-low)
print('Total of (high-low) for each row', total)
In [ ]:
# With pandas
import pandas as pd
#df = pd.read_csv('input.txt', sep=" ", header=None)
df = pd.read_csv('input2.txt', sep=" ", header=None)
print((df.max(axis=1) - df.min(axis=1)).sum(axis=0))
df
Advent of Code - Day 2 - Part 2 "Great work; looks like we're on the right track after all. Here's a star for your effort." However, the program seems a little worried. Can programs be worried?
"Based on what we're seeing, it looks like all the User wanted is some information about the evenly divisible values in the spreadsheet. Unfortunately, none of us are equipped for that kind of calculation - most of us specialize in bitwise operations."
It sounds like the goal is to find the only two numbers in each row where one evenly divides the other - that is, where the result of the division operation is a whole number. They would like you to find those numbers on each line, divide them, and add up each line's result.
For example, given the following spreadsheet:
5 9 2 8 9 4 7 3 3 8 6 5 In the first row, the only two numbers that evenly divide are 8 and 2; the result of this division is 4. In the second row, the two numbers are 9 and 3; the result is 3. In the third row, the result is 2. In this example, the sum of the results would be 4 + 3 + 2 = 9.
What is the sum of each row's result in your puzzle input?
In [ ]:
# Note: Input has not changed
f.seek(0)
total = 0
for line in f:
values = [int(n) for n in line.split()]
for x in values:
for y in values:
if y%x == 0:
if x != y:
# print('x = ', x, "y= ", y, "y/x =", (y/x))
total = total + (y/x)
print('Value of Total= ', total)
In [ ]:
# With Pandas (imported Pandas and made a dataframe above df)
What I learned from Day 2:
In [ ]:
# This is not working
# from bs4 import BeautifulSoup as be
# import requests
#import re
#url = 'http://adventofcode.com/2017/day/2/input' #Try to use this & get credentials
#url = 'http://localhost:8888/edit/input.html'
#page = requests.get(url)
#soup = be(page.content)
#soup
print("bye")
Advent of Code - Day 1 - Part 1 It goes on to explain that you may only leave by solving a captcha to prove you're not a human. Apparently, you only get one millisecond to solve the captcha: too fast for a normal human, but it feels like hours to you.
The captcha requires you to review a sequence of digits (your puzzle input) and find the sum of all digits that match the next digit in the list. The list is circular, so the digit after the last digit is the first digit in the list.
For example:
1122 produces a sum of 3 (1 + 2) because the first digit (1) matches the second digit and the third digit (2) matches the fourth digit. 1111 produces 4 because each digit (all 1) matches the next. 1234 produces 0 because no digit matches the next. 91212129 produces 9 because the only digit that matches the next one is the last digit, 9. What is the solution to your captcha?
In [ ]:
captcha = '77736991856689225253142335214746294932318813454849177823468674346512426482777696993348135287531487622845155339235443718798255411492778415157351753377959586612882455464736285648473397681163729345143319577258292849619491486748832944425643737899293811819448271546283914592546989275992844383947572926628695617661344293284789225493932487897149244685921644561896799491668147588536732985476538413354195246785378443492137893161362862587297219368699689318441563683292683855151652394244688119527728613756153348584975372656877565662527436152551476175644428333449297581939357656843784849965764796365272113837436618857363585783813291999774718355479485961244782148994281845717611589612672436243788252212252489833952785291284935439662751339273847424621193587955284885915987692812313251556836958571335334281322495251889724281863765636441971178795365413267178792118544937392522893132283573129821178591214594778712292228515169348771198167462495988252456944269678515277886142827218825358561772588377998394984947946121983115158951297156321289231481348126998584455974277123213413359859659339792627742476688827577318285573236187838749444212666293172899385531383551142896847178342163129883523694183388123567744916752899386265368245342587281521723872555392212596227684414269667696229995976182762587281829533181925696289733325513618571116199419759821597197636415243789757789129824537812428338192536462468554399548893532588928486825398895911533744671691387494516395641555683144968644717265849634943691721391779987198764147667349266877149238695714118982841721323853294642175381514347345237721288281254828745122878268792661867994785585131534136646954347165597315643658739688567246339618795777125767432162928257331951255792438831957359141651634491912746875748363394329848227391812251812842263277229514125426682179711184717737714178235995431465217547759282779499842892993556918977773236196185348965713241211365895519697294982523166196268941976859987925578945185217127344619169353395993198368185217391883839449331638641744279836858188235296951745922667612379649453277174224722894599153367373494255388826855322712652812127873536473277'
# captcha = '777367' #21
count = 0
length = len(captcha)
print('len ', length)
# increment through the string to see if current number is the same as the next
# Total those numbers
# Check to see if the last equals the first
for i in range(length-1):
x = captcha[i]
next = captcha[i+1]
if x == next:
count = count + int(x)
# check the last
if captcha[length-1] == captcha[0]:
count = count + int(captcha[length-1])
print(count)
In [ ]:
# with enumerate
captcha = '777367' #21
count = 0
mylen = len(captcha)
for index, value in enumerate(captcha):
print(index, value)
if value == captcha[(index+1)% mylen]:
count = count + int(value)
print(count)
Advent of Code - Day 1 - Part 2 You notice a progress bar that jumps to 50% completion. Apparently, the door isn't yet satisfied, but it did emit a star as encouragement. The instructions change:
Now, instead of considering the next digit, it wants you to consider the digit halfway around the circular list. That is, if your list contains 10 items, only include a digit in your sum if the digit 10/2 = 5 steps forward matches it. Fortunately, your list has an even number of elements.
For example:
1212 produces 6: the list contains 4 items, and all four digits match the digit 2 items ahead. 1221 produces 0, because every comparison is between a 1 and a 2. 123425 produces 4, because both 2s match each other, but no other digit has a match. 123123 produces 12. 12131415 produces 4. What is the solution to your new captcha?
In [ ]:
captcha = '77736991856689225253142335214746294932318813454849177823468674346512426482777696993348135287531487622845155339235443718798255411492778415157351753377959586612882455464736285648473397681163729345143319577258292849619491486748832944425643737899293811819448271546283914592546989275992844383947572926628695617661344293284789225493932487897149244685921644561896799491668147588536732985476538413354195246785378443492137893161362862587297219368699689318441563683292683855151652394244688119527728613756153348584975372656877565662527436152551476175644428333449297581939357656843784849965764796365272113837436618857363585783813291999774718355479485961244782148994281845717611589612672436243788252212252489833952785291284935439662751339273847424621193587955284885915987692812313251556836958571335334281322495251889724281863765636441971178795365413267178792118544937392522893132283573129821178591214594778712292228515169348771198167462495988252456944269678515277886142827218825358561772588377998394984947946121983115158951297156321289231481348126998584455974277123213413359859659339792627742476688827577318285573236187838749444212666293172899385531383551142896847178342163129883523694183388123567744916752899386265368245342587281521723872555392212596227684414269667696229995976182762587281829533181925696289733325513618571116199419759821597197636415243789757789129824537812428338192536462468554399548893532588928486825398895911533744671691387494516395641555683144968644717265849634943691721391779987198764147667349266877149238695714118982841721323853294642175381514347345237721288281254828745122878268792661867994785585131534136646954347165597315643658739688567246339618795777125767432162928257331951255792438831957359141651634491912746875748363394329848227391812251812842263277229514125426682179711184717737714178235995431465217547759282779499842892993556918977773236196185348965713241211365895519697294982523166196268941976859987925578945185217127344619169353395993198368185217391883839449331638641744279836858188235296951745922667612379649453277174224722894599153367373494255388826855322712652812127873536473277'
# captcha = '12131415' # 4
# captcha = '1212' # 0
# captcha = '123425' # 4
# captcha = '123123' # 12
# captcha = '1212' # 6
count = 0
length = len(captcha)
halflen = int(length/2)
print('length ', length, 'half length ', halflen)
# increment through the string to see if the current char is the same as half one
# Total those numbers
#Check to see if the last equals the first
for i in range(length-1):
x = captcha[i]
next = captcha[(i+halflen)% length]
if x == next:
count = count + int(x)
# check the last
if captcha[length-1] == captcha[halflen-1]:
count = count + int(captcha[length-1])
print(count)
What I learned\remembered from Day 1 :
In [ ]: