Advent of Code 2020 – Day 13

Today’s lesson in extremely, incredibly, stupidly, inefficient methodology, is brought to you by, the letter “i” and the number “640856202464541”. Day 13 consisted of calculating bus departure times. Part 1 was stupidly simple. You have a list of buses, each bus makes a regular round trip to wherever, and the round trip always takes the same amount of minutes. At some point in the past, the buses all left at once.

Say the buses were 4, 5, and 6, each number also being the minutes for a round trip. Every 4 minutes, bus 4 returns, every 5 minutes bus 5 returns, every 6 minutes, bus 6 returns. If you are available to leave at 9 minutes, which bus leaves first. In this example, the first bus to return would be 5 (5*2=10)

Part 1 was easy, start at your departure time, check to see if any of the numbers divide into it evenly, if not, increment by one and repeat.

with open('day13data.txt') as f:
    lines = [line.rstrip() for line in f]

time = int(lines[0])
raw = lines[1].split(',')
busses= [] 

for i in raw:
  if i != 'x':
    busses.append(int(i))

print time
print busses

for x in busses:
  bus_time=x*(round((float(time)/float(x))+.5))
  wait=bus_time-time
  print "For bus "+str(x)+": "+str(bus_time)+" and you will wait: "+str(wait)+" Ans: "+str(x*wait)

The trickiest part is that the data contained non existent buses, labeled with an “x”. These are not a factor for part 1, so they just get stripped out.

Part 2 is where the pain in the ass was. For Part 2, you have to find a starting time where each bus, will leave, one minute apart, according to their offset. This includes the “missing” buses. So for the quick example I had above of 4,5,6, this time would occur at well, 4 minutes, because I made them sequential, but the next one would occur at 64,65,66 (16*4, 13*5, 11*6). This gets even more complicated when you add in the blanks, for example, 4,x,5,x,6 occurs at 68,70,72. As you spread the numbers apart and rearrange them to be non sequential, it complicates everything more.

I actually figured out the methodology pretty quickly, and wrote a working, good bit of code pretty quickly, my problem, was picking a starting point. I am sure there is some numerology methods (I am pretty sure you can do something using remainders), to calculate even an approximate starting point. In my standard of ugly code, I was just brute forcing it.

with open('day13data.txt') as f:
    lines = [line.rstrip() for line in f]

lines_array = lines[1].split(',')
times = []
counter=0
#First for sample Data Set day13datab.txt, second for real data
#multiplier=152600
multiplier=15630639084400
offsets=[]
busses=[]

for i in lines_array:
  if i != 'x':
    busses.append(i)
    offsets.append(lines_array.index(i))

#print busses
#print offsets

while (1):
  for i in offsets:
    times.append(((int(busses[0]))*multiplier)+i)

  #print times
  counter=1
  for j in busses[1:]:
    #print j
    if (times[counter]/float(j)).is_integer():
      counter+=1
    else:
      break
        
  #print times
  #print counter
  if counter == len(busses):
    break
  counter = 0
  times =[]
  multiplier+=1
  #print multiplier

print times

The problem is, this takes a very, very, very, very, very, long time. I left this code running for hours on my server and it didn’t finish, I honestly feel like it could very likely run for days, weeks, years, and never finish. The iteration on my multiplier that gives the correct set, for my data (every person has a different data set) was 15,630,639,084,501. 15 TRILLION.

So I fudged it a bit, because I was pretty sure my code was good, but I didn’t have an eternity to wait. So I found someone else’s code, found the correct answer, then worked out my starting offset from there. Sure enough, when I start at 15,630,6390,084,400. It quickly finds the correct answer.

If I needed this code for something important, I would certainly try to clean it up. I even started working on an iteration that would sort out my bus list to start with the largest number, instead of iterating the list every (low value) it would iterate every (high value), which in my case I believe was something like 15 versus 900. This was trickier than a straight sort though because I had a second list of offsets that I needed to also re order. I got this code working for the sample data set, but it failed in my proper data set because, while the sample data set started with the lowest bus number, the actual data set did not, and I had not calculated for that.

PS, yes, I misspelled “busses” in my code

Advent of Code 2020 – Day 12

So far, I think Day 12 has been my favorite puzzle. Not too hard, not too easy, it feels like an actually useful problem to solve instead of some arbitrary manipulation of a bunch of numbers.

This puzzle involved moving a boat based on a set of instructions. The only part that felt off was that sometimes the boat moves forward, and sometimes it just sort of, slides in one cardinal direction.

def rotator(degrees, current):
  change = degrees+current
  if change < 0:
    change = change+360
  if change >=360:
    change = change-360
  #print change
  return change  
 

with open('day12data.txt') as f:
    lines = [line.rstrip() for line in f]

xpos=0
ypos=0
#0 is East
orientation=0
cardinals = ["E","S","W","N"]

for i in lines:
  #print i
  next_orient=i[0]
  amount=int(i[1:])

  print "Ship Moves: "+next_orient+" direction "+str(amount)+" times"

  if next_orient == "L":
    orientation = rotator(-amount,orientation)
  if next_orient == "R":
    orientation = rotator(amount,orientation)
  if next_orient == "F":
    next_orient = cardinals[(orientation/90)]
  #print amount
  #print next_orient
  #print cardinals[(orientation/90)]
  if next_orient == "N":
    xpos=xpos+amount
  if next_orient == "S":
    xpos=xpos-amount
  if next_orient == "E":
    ypos=ypos+amount
  if next_orient == "W":
    ypos=ypos-amount


  print xpos
  print ypos
print abs(xpos)+abs(ypos)

This whole thing was a pretty straight forward string of conditionals, and a few functions to rotate the orientation. I am actually particularly proud of how I handled the orientation here, using an array. Your orientation is expressed in degrees, which when divided by 90 gives you a number 0, 1, 2, or 3, which become indexes in an array of cardinal directions.

Part two changed things a bit, and solved the “how does a boat facing east move north” question. Instead of moving the boat, you move a navigational buoy. The boat old moves when you get a forward command, and it moves towards the buoy. 

def rotator(degrees, current):
  global xpos
  global ypos
  change = degrees+current
  if change < 0:
    change = change+360
  if change >=360:
    change = change-360
  #print change
  #return change
  if change == 90 or change == 270:
   temp=xpos
   xpos=-ypos
   ypos=temp
  if change == 180 or change == 270:
   xpos=-xpos
   ypos=-ypos
 

with open('day12data.txt') as f:
    lines = [line.rstrip() for line in f]

xpos=1
ypos=10
shipx=0
shipy=0
#0 is East
orientation=0
cardinals = ["E","S","W","N"]

for i in lines:
  #print i
  next_orient=i[0]
  amount=int(i[1:])

  if next_orient == "L":
    rotator(-amount,orientation)
  if next_orient == "R":
    rotator(amount,orientation)
  if next_orient == "N":
    xpos=xpos+amount
  if next_orient == "S":
    xpos=xpos-amount
  if next_orient == "E":
    ypos=ypos+amount
  if next_orient == "W":
    ypos=ypos-amount
  if next_orient == "F":
    shipx=shipx+(xpos)*amount
    shipy=shipy+(ypos)*amount

  print "Ship Moves: "+next_orient+" direction "+str(amount)+" times"

  print "Beacon: "+str(xpos)+"E/W "+str(ypos)+"N/S"
  print "Ship: "+str(shipx)+"E/W "+str(shipy)+"N/S"
print abs(shipx)+abs(shipy)
print shipx
print shipy

The sad part is, RIP clever Orientation gimmick, though the array is still in there for posterity. When the buoy rotates, it doesn’t face a different direction, it rotates around the ship, so the functions just became swapped coordinates instead of degrees corresponding to an orientation.

Advent of Code 2020 – Day 9

The puzzle for Day 9 ended up being fairly easy. It’s basically striding across some arrays for values. The task was to decrypt a fake code set by exploiting a known bug. Sounds fancy, but that’s just the story for the day, there isn’t any real complex hacking going on here or anything.

What you get is a string of numbers output from the device, to find the “exploit” you have to find the first number that doesn’t fit the pattern. The pattern being that each number (after a preamble set of numbers) is the sum of two of the previous numbers, within a range.

with open('day9data.txt') as f:
    lines = [line.rstrip() for line in f]

position = 25

while(True):
  valid_nums=lines[position-25:position]
  valid = 0
  current = int(lines[position])
  print current
  for i in valid_nums:
    check = current - int(i)
    #print str(current) +"-"+ i +"="+str(check)
    if str(check) in valid_nums:
      #print check
      valid=1
  print valid
  if valid == 1:
    print position
    position+=1
  else: 
    print current
    break

So for Part 1, read in the code, set the starting position of 25 (for the 25 number preamble), then take the 26th number, then run some loops across the previous 25 numbers, adding each number to each other number, until you find the 26th number. If it works, move on tot he next number, until it doesn’t.

Part two, is to execute the “exploit” by finding a continuous set of numbers, that add up to the result of the first set of numbers. For the sake of keeping the code universally useful, Part 1 gets run again to find the key value.

After wards, it’s more loops adding up numbers. Start at the first value, start adding until the sum is greater than the key value, then reset, and start again at the next number. Until the sum equal the exploit value. Then return the result, which in this case was the sum of the first and last number int he continuous run of numbers.

with open('day9data.txt') as f:
    lines = [line.rstrip() for line in f]

position = 25

while(True):
  valid_nums=lines[position-25:position]
  valid = 0
  current = int(lines[position])
  #print current
  for i in valid_nums:
    check = current - int(i)
    #print str(current) +"-"+ i +"="+str(check)
    if str(check) in valid_nums:
      #print check
      valid=1
  #print valid
  if valid == 1:
    #print position
    position+=1
  else: 
    break
      
print current

start=0
position=start
total=0
sum_array=[]

while(total != current):
  if total < current:
    total+=int(lines[position])
    position+=1
    #print total
  else:
    start+=1
    position=start
    total=0

for i in lines[start:position]:
  sum_array.append(int(i))

sum_array = sorted(sum_array)

print sum_array
print int(sum_array[0])+int(sum_array[-1])

There may be a quicker way to find these value but just straight brute forcing it on both fronts works pretty well.