Advent of Code 2020

Advent of Code 2020 – Day 7

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 2020 – Day 5

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 2020 – Day 4

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.

Advent of Code 2020 – Day 3

Day 3 was the first that really presented some problems, and I admit, I did a “cheaty trick” to solve it. Part 1 and 2 use the same code as well, because Part 2 was a simple variation of Part 1.

For Day 3, you get a “map” of a forest with Trees. You have to count how many trees will need to be avoided for a particular path through the forest. The path is a straight line along a particular slope, (over right, down some). here is the sample forest:

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

So, the problem I ran into, is that the hash (#) in Python, creates comments. I am sure there is a way, but I could not figure out how to escape out the hash to compare and count it in an ‘if’ statement. So what I did instead of was replace all the #s in my map code, with ‘T’s. I can look for ‘T’s all day.

With that, here is a my solution:

def split_str(s):
  return [ch for ch in s]

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

trees = 0
slopex = 1
slopey = 2
posx=0
posy=0
line_loop=len(lines[1])
distance=len(lines)-2
#print distance

while (posy<distance):
  #print trees
  posx=posx+slopex
  posy=posy+slopey
  #print str(posy)+"/"+str(distance)
  if(posx>=line_loop):
    posx=posx-line_loop
  #print str(posx)+","+str(posy)
  print str(lines[posy][posx])
  whatis=str(lines[posy][posx])
  if (whatis == "T"):
    trees+=1
  print trees

The way the problem works is, the forest repeats to the right infinitely. So step one was getting the width of the forest repeat sequence, so I could loop my position back around as needed. Otherwise it’s a simple matter of updating the position of ‘row’ and ‘col’, checking if it needs to loop (is row position greater than the loop, if so subtract the loop value), then check for a T(ree).

Part 2 was the same problem, except you check several slopes and multiply the results together. To solve this I just adjusted my slope variables and then used a calculator to multiply the results.

I could have changed the code to ask for the slope each run, or even have it loop through several slopes until you tell it to end, when it would multiply the results itself, but frankly, I don’t have that kind of time. This is a fun side project to do while watching TV at night.

Advent of Code 2020 – Day 2

Day two is a little more complicated than Day 1 was. Today’s challenge is to take a blob of passwords, and verify if they are acceptable or not, per the “company standard” at the time of the creation of each password.

For example:

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

For part 1, on line 1, the letter a should appear at least 1 time and at most 3 times. For line 2, the letter b should appear at least 1 time and at most 3 times. For line 3, the letter c should appear at least 2 times and at most 9 times.

My solution for Day 2, Part 1 is below:

number_valid = 0
toolow = 0
toohigh = 0
number_of_entries = 0

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

for x in lines:
  dashloc = x.find("-")
  spaceloc = x.find(" ")
  colloc = x.find(":")
  mincount=int(x[0:dashloc])
  maxcount=int(x[int(dashloc)+1:spaceloc])
  limitchar=x[int(spaceloc+1):int(colloc)]
  password = x[int(colloc+2):]
  checkvalue = int(password.count(limitchar))
  if(mincount <= checkvalue <= maxcount):
    number_valid=number_valid+1
  if(checkvalue<mincount):
    toolow+=1
  if(checkvalue>maxcount):
    toohigh+=1
  if(mincount>=maxcount):
    print "Problem?"

print number_valid
#print toolow
#print toohigh
#print number_valid+toolow+toohigh

On a note, I’ve got some debugging bits still in there, that are commented out. After reading the file in, I’ve initialized some variables I’ll be using in the code. Then I start looping through the data.

This is where my janky code really gets to shine, as I am sure there is a better way to handle this. First step is to locate the special characters separating the data, from the exampe, “1-3 a:abcde”, these are a dash, a space and a colon. With these located, I’ve extracted the min and max values, the letter I’m tracking, and the password itself.

After getting these core values, it’s simple enough to count the occurrences of the letter, then verify it against the min/max values and count how many are valid.

I had a bit of trouble at first because I had used “password = x[int(colloc+2):-1]” instead of “password = x[int(colloc+2):]”. I’m not a master of a lot of programming languages, but I am familiar with enough of them that I get the syntax confused a lot (I keep forgetting the colon on ifs and loops in Python). I forget which language uses -1 for “go to tot he end of a range”, but I am pretty sure there is one, because I did this a lot at first.

Part 2 changes things up a bit. Instead of the first numbers representing a range of how many, it demands that the special letter appears at one of those two positions, but not both.

My solution for part 2 is below:

number_valid = 0
number_of_entries = 0

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

for x in lines:
  first=0
  second=0
  dashloc = x.find("-")
  spaceloc = x.find(" ")
  colloc = x.find(":")
  mincount=int(x[0:dashloc])-1
  maxcount=int(x[int(dashloc)+1:spaceloc])-1
  limitchar=x[int(spaceloc+1):int(colloc)]
  password = x[int(colloc+2):]
  if(password[mincount]==limitchar):
    first=1
  if(password[maxcount]==limitchar):
    second=1
  if ((first==1) or (second==1)):
    if(first !=second):
      number_valid+=1

print number_valid
#print toolow
#print toohigh
#print number_valid+toolow+toohigh

More sloppy code, i didn’t even change the variable names. Now, instead of counting and comparing, I’m checking for the special character in each position, and toggling a variable if it’s there or not, then making sure it’s nor present in both. This is where the new variables “first” and “second” come in.

This biggest challenge on Day 2 was that it required more manipulation of the input data.

Github Repository of my Solutions