Aunt Sue

Advent of Code 2015 Day 16

Part 1

1. 1 out of 500 - seems easy enough
2. Writing a working algorithm

1 out of 500 - seems easy enough

My assumption:

• When finished checking each Aunt's gift attributes for properties and values that all match a few of the ones in the actual gift...
• ...There will only be one
• Because if there was more than one, how could I attempt to further eliminate options?

Writing a working algorithm

First, I'll store the actual gift as an object:

const gift = {
  children: 3,
  cats: 7,
  samoyeds: 2,
  pomeranians: 3,
  akitas: 0,
  vizslas: 0,
  goldfish: 5,
  trees: 3,
  cars: 2,
  perfumes: 1
}

Each line of input follows this pattern:

Sue (1-500): (compound: [0-10],?){3}

I need to extract:

• An ID: 1-500
• Three compounds
• Three amounts: 0-10

This regex should handle the task:

/\d+|\w+/g

• \d+ matches any contiguous digits
• \w+ matches any contiguous letters
• | matches either the bit to the left or the bit to the right

Using that regex on this example:

Sue 234: goldfish: 9, cats: 4, cars: 7

Should return an array like this:

['Sue', '234', 'goldfish', '9', 'cats', '4', 'cars', '7']

Next, I need to convert that into an object like this:

{
  id: 234,
  goldfish: 9,
  cats: 4,
  cars: 7
}

And add it to an array containing the objects representing all Aunt Sue's.

Here's my algorithm in JavaScript:

const Sues = input.reduce(
  (list, gift) => {
    let [,id,c1,a1,c2,a2,c3,a3] = 
      [...gift.matchAll(/\d+|\w+/g)].map(match => match[0])
    let obj = {}
    obj[id] = +id
    obj[c1] = +a1
    obj[c2] = +a2
    obj[c3] = +a3
    list.push(obj)
    return list
  }, []
)

Lastly, I have to find the real Aunt Sue.

My algorithm as pseudocode:

For each gift from a Sue
  Generate a nested array of each compound and its value
  Check whether the gift contains that exact value for each compound
  Keep the gift only if each compound and its value match those in the actual gift

Return the ID of the only gift that matched

My algorithm as JavaScript:

return sues.filter(
  sue => Object.entries(sue)
    .slice(1)
    .map(el => gift[el[0]] == el[1])
    .every(el => el == true)
)[0].id

It generated the correct answer!

Part 2

1. Ranges, just to be more difficult
2. Misunderstanding the challenge
3. Writing a working algorithm
4. Writing a faster algorithm

Ranges, just to be more difficult

• cats and trees: >
• pomeranians and goldfish: <

How will this affect my algorithm?

Misunderstanding the challenge

• I thought I had to check whether the number in the actual gift was within a range dictated by each Aunt Sue's gift's compound value
• But it is the other way around: I have to check whether the number in each Aunt Sue's gift's compound's value is within a range dictated by the actual gift

Writing a working algorithm

My updated gift object now accounts for the ranges:

const gift = {
  children: 3,
  cats: [8,9,10],
  samoyeds: 2,
  pomeranians: [0,1,2],
  akitas: 0,
  vizslas: 0,
  goldfish: [0,1,2,3,4],
  trees: [4,5,6,7,8,9,10],
  cars: 2,
  perfumes: 1
}

My control flow for determining whether a compound's value is a match started as a switch statement:

switch (compound) {
  case 'cats':
    // is value in the range?
    break;
  case 'trees':
    // is value in the range?
    break;
  case 'pomeranians':
    // is value in the range?
    break;
  case 'goldfish':
    // is value in the range?
    break;
  default:
    // is value equivalent?
}

Then I realized it could be much more concise using ternary operator syntax:

['cats','trees','pomeranians','goldfish']
  .includes(compound) ? 
  gift[compound].includes(value) : 
  gift[compound] == value

Everything else from my Part 1 algorithm remained unchanged.

It generated the correct answer!

Writing a faster algorithm

• Using reduce() and filter iterates through the full input list of 500 gifts twice
• 1000 iterations is no biggie, sure
• But I'm just looking for one result
• Can't I do all these operations to only as many input lines needed until I find my match?

Instead of:

Generate an array of objects from the input list
Check each object for a match of every compound and value
Return the only object that matched

I could use find() to reduce a lot of unnecessary work:

Search the input list of strings for the first - and only - match where:
  After extracting the values using regex
  And creating an object
  And comparing that object's compound's values to the actual gift
  All are a match

I do the same work, but only on as many list items as is necessary to find the match!

My faster algorithm in JavaScript:

input.find(gift => {
  let [,id,c1,a1,c2,a2,c3,a3] = 
    [...gift.matchAll(/\d+|\w+/g)].map(match => match[0])
  let obj = {}
  obj.id = +id
  obj[c1] = +a1
  obj[c2] = +a2
  obj[c3] = +a3
  return Object.entries(obj)
    .slice(1)
    .map(pair => 
      ['cats','trees','pomeranians','goldfish']
        .includes(el[0]) ? 
        gift[pair[0]].includes(pair[1]) : 
        gift[pair[0]] == pair[1]
    )
    .every(bool => bool == true)
})

Comparing slow and fast algorithms:

I did it!!

• I solved both parts!
• Using regex and Array methods like reduce(), filter(), map(), includes() and find()
• I recognized an opportunity to make my algorithms faster, and implemented it!
• I kind of solved Part 2 on extra-hard mode by misunderstanding how the compound's values worked!

I'm glad that this puzzle wound up being as relatively easy as it seemed.

Sometimes a lob is preferred to a curveball.