Advent of Code 2015 Day 16
Part 1
- 1 out of 500 - seems easy enough
- 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
- Ranges, just to be more difficult
- Misunderstanding the challenge
- Writing a working algorithm
- Writing a faster algorithm
Ranges, just to be more difficult
-
cats
andtrees
:>
-
pomeranians
andgoldfish
:<
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()
andfilter
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
andArray
methods likereduce()
,filter()
,map()
,includes()
andfind()
- 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)