DEV Community

Cover image for Aunt Sue
Robert Mion
Robert Mion

Posted on

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
}
Enter fullscreen mode Exit fullscreen mode

Each line of input follows this pattern:

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

I need to extract:

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

This regex should handle the task:

/\d+|\w+/g
Enter fullscreen mode Exit fullscreen mode
  • \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
Enter fullscreen mode Exit fullscreen mode

Should return an array like this:

['Sue', '234', 'goldfish', '9', 'cats', '4', 'cars', '7']
Enter fullscreen mode Exit fullscreen mode

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

{
  id: 234,
  goldfish: 9,
  cats: 4,
  cars: 7
}
Enter fullscreen mode Exit fullscreen mode

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
  }, []
)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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?
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
})
Enter fullscreen mode Exit fullscreen mode

Comparing slow and fast algorithms:
Algorithm performance comparison

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.

Top comments (0)