Advent of Code

Advent of Code

Advent of Code 2020 – Day 9

Ramen Junkie 0Comment

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.

Advent of Code

Advent of Code 2020 – Day 8

Ramen Junkie 0Comment

Day 8 may be the first real trouble I have had so far. Part 1 wasn’t too bad, but Part 2 has had me stuck for a bit.

The job is to troubleshoot bad code for a handheld device. It gets stuck in an infinite loop. The input is a string of commands that either increment an accumulator, or jump forward or back in the code. Sometimes there is no action.

Part 1 was to execute the code without ever repeating a command.

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


accumulator=0
location=0
commands_executed=[]

while(location<=len(lines)):
  command = lines[location][:3]
  amount = int(lines[location][4:])

  #print command
  #print amount
  
  if command == 'acc':
    accumulator+=amount
    location+=1
  if command == 'jmp':
    location+=amount
  if command == 'nop':
    location+=1
  
  if location not in commands_executed:
    commands_executed.append(location)
  else:
    break
  #print commands_executed



print accumulator

Basically, run each command, tracking which have been executed, then, when you reach a repeat, which will cause a loop, you exit.

Part 2 had me for a bit, but mostly because I missed what it was looking for. The object is to change one of the jump or no operation commands, to cause the loop to break and the code to complete. My original approach and thought was, that at some point in the loop, the code would swoop down to the bottom of the commands, and then loop away. So I was checking for if the code was close to the end, then changing the jump or no-operation there.

What I needed to be doing was changing each one, and then testing it through the solve loop to see if it would complete or not (no loops).

Basically, run the code, anytime there is a jump or no-op, flip it and check for a loop. If not, keep going on the original path.

def solver(accumulator, location, commands_executed, switcher):

  while(True):
    if lines[location] == "":
      print accumulator
      return False

    command = lines[location][:3]
    amount = int(lines[location][4:])

    #print command
    #print amount
  
    if switcher==1 and command == 'jmp':
      switcher = 0
      command = 'nop'
    if switcher==1 and command == 'nop':
      switcher = 0
      command = 'jmp'


    if command == 'acc':
      accumulator+=amount
      location+=1
    if command == 'jmp':
      location+=amount
    if command == 'nop':
      location+=1

    if location not in commands_executed:
      commands_executed.append(location)
    else:
      break
    #print commands_executed

  return True


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


accumulator=0
location=0
breaker = True
commands_executed=[]

while(breaker):
  while(True):
    command = lines[location][:3]
    amount = int(lines[location][4:])

    #print command
    #print amount
    if command == "":
      print accumulator

    if command == 'acc':
      accumulator+=amount
      location+=1
    if command == 'jmp':
      breaker = solver(accumulator,location, commands_executed, 1)
      location+=amount
    if command == 'nop':
      breaker = solver(accumulator,location, commands_executed, 1)
      location+=1

    if location not in commands_executed:
      commands_executed.append(location)
    else:
      break
    #print commands_executed

I tried to get some recursion going here but I couldn’t work it out so I just did it with repeated code blocks. Because this is why I dislike recursion. If I need to pass around and check for changing conditionals, I may as well put them in a regular loop.

Advent of Code

Advent of Code 2020 – Day 7

Ramen Junkie 0Comment

The challenge for Day 7 is the first that really tripped me up. The basic concept wasn’t too hard, but I had a lot of stabs in the dark trying to massage the code into working properly. Part of the problem in my case is that it really needed to use recursion, which I really hate. When you have a small error, and it’s recursive, it just snowballs into a huge error.

Part 1 wasn’t too hard, you have a bunch of different colored bags, and they contain some number of other colored bags. Here is the sample data set:

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

The task was to count how many bags will eventually contains a shiny gold bag. The hardest part was processing the input, because it’s all text based, so there is some string searching and manipulating to check for bag types.

My other minor issue was, I had a brain fart, and started working off the sample data set instead of the actual data set, which is considerably larger. I had written up 4 or 5 if style statements, because “there’s like ten bags here, easy”, before realizing my mistake and checking the actual data set, which has, many many more bags. Too many to build simple if based counting statements for.

Anyway, my code for part 1:


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

bags=0
check=["shiny gold"]
checked=[]

while(check):
  #print check[0]
  for line in lines:
    endloc = line.find("contain")
    if check[0] in line[endloc:]:
      bags+=1
      #print endloc
      container=line[:endloc-1]
      if container[-1:] == "s":
        container = container[:-1]


      if container not in checked:
        check.append(container)
        checked.append(container)
      #print line[endloc:]
      #print check[0]
      #print line[:endloc-1]
  #print bags
  check.pop(0)
  #print check

print len(checked)

#print checked
print bags

Fairy simple, start with anything that contains a “Shiny Gold Bag”, then check for anything containing those bags, and check for anything containing those bags, until there is nothing left to check.

Part 2 was trickier, because it went the other direction. It’s also where the recursion came into play. For those who don’t know what recursion is, it’s essentially when a function, references itself, within a function.

Say you want to check bags for bags and count them, so you have a function that says “open a bag, and count how many are inside, then open any bags inside and count those bags, then open any bags inside and count those bags, then open any bags inside and count those bags….

And so on. Until you open a bag and it contains no bags, then you just return 1, for the empty bag itself. Then the recursion will sort of rubber-band back on itself in this case, and multiply the bag counts in each bag by how many of each bag there existed.

Anyway, here is the code:


def sum(arr):
    result = sum(arr)
    return result

def bagcheck(quantity, current):
  total=int(quantity)
  #print checked  
  for line in lines:
    endloc = line.find("contain")
    if current in line[:endloc]:
      content = line[endloc+7:-1].split(',')
      #print content
      for i in content:
        if i != ' no other bags':
          #print total
          if i[-1] == "s":
            i=i[:-1]
          #print i[1]
          #print i[3:]
          if i not in checked:
            check.append(i)
            checked.append(i)
          #total += int(i[1])
          total += int(quantity) * bagcheck(i[1], i[3:])
        else: total=quantity
       
  print current+" has inside "+str(total)+" and there are "+quantity+" of them, total of "+str(total)
  return int(total)

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

bags=0
check=[" 1 shiny gold"]
checked=[]
total=0

if check[0] != ' no other bags':
  bags=(bagcheck(check[0][1],check[0][3:]))
    #print bags

print bags-1

It worked out, I am not entirely sure how, because I spent so many times moving and adjusting +1s and multiplying this by that, or that by that other thing, until it worked.

Both parts gave my some initial trip ups because of bags versus bag, which is why there are places that check for and remove the s on the end of a bag type. Because when you check for “bags” and there is only one “bag”, you won’t see the singular bag. But if you search for “bag”, you will find “bags”.

Advent of Code

Advent of Code 2020 – Day 5

Ramen Junkie 0Comment

So Day 5, ended up being a bit easier than I though it would be. The puzzle involves locating your seat on the plane using Binary. Tickets have a code on them like “FBFBBFFRLR” and the code corresponds to “Front, Back, Left, Right. I started off working up some conditionals that would add or subtract values.

Then I had a brief epiphany moment, that the values are literally just Binary values using letters instead of 1s and 0s. So instead I wrote a quick bit that would convert each seat value into a binary number for Column and Row, then both Part 1 and Part 2 was some quick math checks. Part 1 was to calculate the highest seat number, Part 2 was to find the missing seat that was your seat.

I used basically the same code for both.

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

row='0b'
col='0b'

largest=0
ids=[]

#binary Exclusion
#0-127
#0-7

for line in lines:
  if line != '':
     for i in line:
       if i == 'F':
         row=row+'0'
       if i == 'B':
         row=row+'1'
       if i == 'L':
         col=col+'0'
       if i == 'R':
         col=col+'1'
     current=(eval(row))*8+eval(col)
     ids.append(current)

     if current>largest:
       largest=current


     row='0b'
     col='0b'

ids=sorted(ids)
#print ids

prev=ids[0]
now=ids[1]

for next in ids[2:]:
   if next-1 != now:
     print next-1
   prev=now
   now=next



print largest

This one seemed daunting but went by super quick once I figured out the trick.

Advent of Code

Advent of Code 2020 – Day 4

Ramen Junkie 0Comment

The task for Day 4 is to validate a series of passports by checking that they have valid data on them. For the first part, the passports are simply validated by verifying that they have all of the fields that they should have:

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

For my approach, I first loaded the data from the file (this is a common theme in these), and then went about searching line by line. Here is my code for Part 1:

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

buildline = ''
valid_fields = ['byr','iyr','eyr','hgt','hcl','ecl','pid']
passengers = []
num_fields = len(valid_fields)
#print num_fields
valid_passports=0
num_valid=0

for line in lines:
  if line != '':
    buildline+=' '+line
  else:
    #print buildline
    linearray=buildline.split(' ')
    linearray=linearray[1:]
    for x in linearray:
      #print x[0:3]
      if(x[0:3] in valid_fields):
        num_valid+=1
    #print linearray
    if num_valid == num_fields:
      valid_passports+=1

    #passengers.append(linearray)
    num_valid = 0
    buildline = ''

#print passengers
print valid_passports

Each passport in the file has multiple lines, separated by blank lines. So for each line, it first checks to see if it’s a blank or not. If it’s not a blank, it compiles the line into a single passport line for processing. Once it hits a blank line, it know it has captured all of the data for that particular passport, and processes the data.

The processing is done by splitting the data into an array, then processing through each entry in the array, looking for one of the required fields. It verifies that a passport is valid by checking to see if the number of fields counted is equal to the length of the fields array.

While the array building is sloppy, and probably could have been done by adding the lines directly to an array, instead of a string that’s then split, I am rather proud of a few bits of this code. Comparing the valid field count to the valid fields array means that it would be trivial to add additional valid fields.

Also the check is particularly nice. It would have been easy to do the check using a basic search on each line. The problem is, this could confuse the program if say, “Hair Color” contains invalid data of “byr” (Birthyear). It would think it found the Birthyear field, but it has not. The field is always the first three characters in a valid passport here, so using “if(x[0:3] in valid_fields):” means it always only checks the first 3 characters.

Part 2 added another layer to the validation to make sure the individual fields actually contained properly formatted, valid data. The basic process is the same, it just involved a lot more if statements to check for the various conditions required. My code is below:

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

buildline = ''
valid_fields = ['byr','iyr','eyr','hgt','hcl','ecl','pid']
valid_eyes = ['amb','blu','brn','gry','grn','hzl','oth']
valid_color = ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f']
passengers = []
num_fields = len(valid_fields)
#print num_fields
valid_passports=0
num_valid=0
is_valid=0

for line in lines:
  if line != '':
    buildline+=' '+line
  else:
    #print buildline
    linearray=buildline.split(' ')
    linearray=linearray[1:]
    for x in linearray:
      if(x[0:3] == "byr" and len(x[4:]) == 4):
        if 1920<=int(x[4:])<=2002:
          num_valid+=1

      if(x[0:3] == "iyr" and len(x[4:]) == 4):
        if 2010<=int(x[4:])<=2020:
          num_valid+=1

      if(x[0:3] == "eyr" and len(x[4:]) == 4):
        if 2020<=int(x[4:])<=2030:
          num_valid+=1

      if(x[0:3] == "ecl"):
        if x[4:] in valid_eyes:
          num_valid+=1

      if(x[0:3] == "pid") and (len(x[4:]) == 9):
          num_valid+=1

      if(x[0:3] == "hgt" and x[-2:] == 'cm'):
          if 150<=int(x[4:-2]) <= 193:
            num_valid+=1
      if(x[0:3] == "hgt" and x[-2:] == 'in'):
          if 59<=int(x[4:-2]) <= 76:
            num_valid+=1

      if(x[0:3] == 'hcl' and len(x[4:]) == 7):
          #print x[4:]
          #for n in x[5:]:
           # if n not in valid_color:
            #  is_valid=0
          num_valid+=1

    if num_valid == num_fields:
      valid_passports+=1

    #passengers.append(linearray)
    is_valid = 0
    num_valid = 0
    buildline = ''

#print passengers
print valid_passports

Not a lot of fanciness here, but it uses the same basic principle of counting the valid fields up and comparing them to the length. The difference being that if you needed to add a required field, you would also need to add a conditional for that statement.

« Previous Page — Next Page »