Advent of Code, Day 16

Day 16 of Advent of Code is here!

See all of my other solutions here. If you’re interested, check out what my colleagues at Slalom are doing with their Advent of Code! You can see this and my other solutions on github.

Do your best!

I highly encourage you to get through the day’s challenge on your own. Certainly refer to this and other’s examples to help you get through it. I would love to hear how you did! Did you find a better approach than I did? Do tell!

There’s a lot of looping in this one, were you able to get away from so many?

Day 16: Ticket Translation

Part I

“Start by determining which tickets are completely invalid; these are tickets that contain values which aren’t valid for any field. Ignore your ticket for now. Consider the validity of the nearby tickets you scanned. What is your ticket scanning error rate?” ref

The data looks like this, fun eh?

I went ahead and removed the your ticket lines, since the problem wants us to ignore that data for now. Let’s get that data:

const fs = require('fs');
const allLines = fs.readFileSync('./input.txt', 'utf-8').trim().split('\n');

Next I split the data into rules and tickets

const rules = allLines.slice(0, allLines.indexOf(''))
const tickets = allLines.slice(allLines.indexOf('') + 2)

My data has an empty line between the two, so I’m slice()ing the array by that empty line. The tickets is slicing off 2 more rows since the empty line is in this chunk, and the words nearby tickets which I don’t need.

Next I loop through the rules, finding all of the valid numbers

rules.forEach(rule => {
  const ranges = rule.match(/([0-9]*-[0-9]*)/ig)
  loadNumbers(ranges[0])
  loadNumbers(ranges[1])
})

The match() will group my number ranges and output those to the first and second elements in my array. Then I call loadNumbers:

const allowedValues = new Map()
const loadNumbers = (range) => {
  const numbers = range.match(/([0-9]*)/ig)
  for(let i = Number(numbers[0]); i <= Number(numbers[2]); i += 1) {
    allowedValues.set(i, i)
  }
}

I then get the two numbers in the range with another match(), then loop from low to high, adding them to a Map() object called allowedValues. I am using a Map over an array as Maps are MUCH faster in lookups.

I also explored using regex for determining if a number is within a range. Sadly, it’s not that easy. Given a range, like 33-169, a regex to find numbers would look something like 3[3-9]|4[0-9]|5[0-9]... and so on. Regex looks at every character singly, so [3-9] looks at 1 character and allows 3-9. Prepend a 3 and now it’ll find 33 to 39. Then we have to do 40s, 50s, all the way up to 169. Yucky.

Once we have all the valid numbers, I loop through the tickets and identify which ones are invalid.

tickets.forEach(ticket => {
  const codes = ticket.split(',')
  codes.forEach(code => {
    if(!allowedValues.get(Number(code))) invalidValues.push(Number(code))
  })
})

Each ticket is a list of comma separated numbers, so we split it. Then for each of those codes we try to get that code, if we can’t get it, then it’s invalid.

Finally, we add all those bad boys together with a reduce() to get our answer.

console.log(invalidValues.reduce((a, b) => a + b))

Part II

“Now that you’ve identified which tickets contain invalid values, discard those tickets entirely. Use the remaining valid tickets to determine which field is which. Using the valid ranges for each field, determine what order the fields appear on the tickets. The order is consistent between all tickets: if seat is the third field, it is the third field on every ticket, including your ticket. Once you work out which field is which, look for the six fields on your ticket that start with the word departure. What do you get if you multiply those six values together?“

I started with the code from Part 1 above, including the same input (with my ticket removed). Let’s see what changes.

I loop through the rules, working with a little more data

rules.forEach(rule => {
  const ranges = rule.match(/([a-z\s]*): ([0-9]*-[0-9]*) or ([0-9]*-[0-9]*)/i)
  loadNumbers(ranges[1], ranges[2])
  loadNumbers(ranges[1], ranges[3])
})

My match() is now getting the field name along with the range. This will help associate the number value to the field name.

loadNumbers is now

const ticketLocationValues = new Map()

const loadNumbers = (name, range) => {
  const numbers = range.match(/([0-9]*)/ig)
  const locationRange = ticketLocationValues.get(name) || []
  for(let i = Number(numbers[0]); i <= Number(numbers[2]); i += 1) {
    allowedValues.set(i, i)
    locationRange.push(i)
  }
  ticketLocationValues.set(name, locationRange)
}

I’m doing the same range split and counting numbers. But I’ve added this ticketLocationValues Map object. This will store an object of the field name and the valid numbers for that field.

Next let’s loop through the tickets

let validTicketsCount = 0
const finalPositions = new Map()
tickets.forEach(ticket => {
  const codes = ticket.split(',').map(code => Number(code))
  if(codes.every(code => allowedValues.get(code))) {
    validTicketsCount += 1
    codes.forEach((code, index) => {
      ticketLocationValues.forEach((value, key) => {
        if(value.includes(code)) {
          const positions = finalPositions.get(index) || []
          positions.push(key)
          finalPositions.set(index, positions)
        }
      })
    })
  }
})

• As we loop the tickets, we split them again to get the codes. Note the slight difference here from Part 1. I’m mapping the split data and converting them from strings to numbers. In part 1, I converted them to numbers when I used them. This was is definitely a cleaner approach. Don’t be afraid to revisit and refactor your own code!
• I use an every() to see if every code in this ticket is valid. Part 1 we were actually collecting the invalid values so an every() wouldn’t work.
• If the ticket is valid, I increment validTicketsCount, we’ll need that a little later
• Then for each code in the ticket, I loop through the ticketLocationValues (the Map() that has the field name and the valid numbers) and if the value (the array of numbers) has this code, then I load it into another Map() called finalPositions which is storing the index of the value and the possible fields that index could contain.

At this point, finalPositions will have indexes with an array of possible fields. Now we loop through these finalPositions

const totalsPerPosition = []
finalPositions.forEach((value, key) => {
  const position = value.reduce((a, b) => {
    if(!a[b]) {
      a[b] = 0
    }
    a[b] += 1
    return a
  }, {})

  const possibleLabels = []
  Object.keys(position).forEach(posi => {
    if(position[posi] === validTicketsCount) {
      possibleLabels.push(posi)
    }

  })
  totalsPerPosition.push(possibleLabels)
})

• the value of a finalPosition is an array, so I want to reduce this down into an object of field names, with a count of how many times this index had a possible value for the field name. For example, if index 0 in 49 out of 50 tickets satisfied the “departure location” field numbers, then I’ll have { "departure location": 49 } (With my data I have over 3,500 values in the array).
• The output of this, position, should look like { "departure location": 49, "arrival location": 50, etc }
• Then I loop through all of those values from position and if the number is the same as the validTicketsCount (counter from the last block of code) I push that into a new array totalsPerPosition.

My variable naming is terrible, I’m sorry.

The HUGE assumption now is that there will be one index with one label on it, and sure enough there is!

Index 11 has a label of price, since that’s the only one for 11, it can’t be the label anywhere else. If we now remove price from the other indexes, we find index 2 now has one label. If we then take that out from everyone else, we’ll find another, and another. Yup, lots more looping.

let reducedFields = [...totalsPerPosition]
const passedFields = []
while(reducedFields.some(t => t.length > 1)) {
  const oneFieldFound = reducedFields.filter((t, i) => t.length === 1 && !passedFields.includes(t[0]))
  if(oneFieldFound.length > 1) console.error('BUSTED', oneFieldFound)
  const fieldName = oneFieldFound[0][0]
  passedFields.push(fieldName)
  reducedFields = reducedFields.map(f => f.length > 1 ? f.filter(r => r !== fieldName) : f)
}

• Using a while(), I only want to run this if there are still indexes that have more than one label associated to them
• I then find that one index that has one value. I had to put fields as we were processing them into passedFields because they’ll all have 1 at the end, and this filter would then find all of them. I only want the one index that has one label that we haven’t processed yet.
  • I could’ve used a find() here instead of a filter(), but since I wasn’t sure the data would play (why would it be that easy) I played it safe. Now knowing the data and the answer, I could switch this to a find() and get rid of the next line.
• I threw a check in here, if that filter pulls back more than one, then we have a problem. Thankfully this didn’t trigger
• I then grab the field name. Note the [0][0]. A filter() returns an array of items that satisfy the condition. I only want the first one, so the first [0] is to grab the first one from the filtered results. This value that is returned is an array itself (an array of field names), so I need the first label in this index, so the second [0] is needed
• I throw that field name into passedFields so I know I processed it already when we loop again
• Finally, I update reducedFields, filtering out this fieldName from all of the other index values.
• Now loop and do it all again

At the end of this, I now have an array reducedFields which has a single field name in each index. That’s our map! Now apply it to my ticket:

const myTicket = [53,67,73,109,113,107,137,131,71,59,101,179,181,61,97,173,103,89,127,139]

const total = myTicket
  .filter((t, i) => reducedFields[i][0].match(/departure/))
  .reduce((a, b) => a * b)

console.log(total, 'departure value')

I filter my ticket using the reducedFields as my map, looking for the value of the same index location as my ticket value that has departure in it. We multiply it all together in the reduce() to get our final total!

How did it go for you?

How did you find the answer on your own? How did you do it? Anything stump you? I’d love to hear how you did! Please comment below! I have also loaded up just the challenge and code from this and my other days on github, you can follow along there too: pretty Git pages or the code in the repo.