Find the two entries that sum to 2020 and then multiply those two numbers together.
I could have naively used for
loops,
but I wanted to try to avoid that.
So I used [].find()
:
const numbers = `
1721
979
366
299
675
1456
`
.trim()
.split('\n')
.map((s) => parseInt(s, 10))
const targetSum = 2020
let result
numbers.find((x, i) => {
const y = numbers.slice(i + 1).find((y) => x + y === targetSum)
if (!y) return false
result = x * y
return true
})
console.log(result)
Okay, this is also quite naive. But that's okay! I'm here having fun, not leetcoding.
The mutable result
variable bothers me a bit.
But I wanted to avoid looping through numbers
more often than necessary,
which would be the case with a solution like this:
const x = numbers.find((x, i) =>
numbers.slice(i + 1).find((y) => x + y === targetSum)
)
const y = numbers.find((y) => x + y === targetSum)
const result = x * y
And using e.g. filter()
instead of find()
would mean that we couldn't break out of the loop early
(when the result has been found).
Same as Part 1, but find three numbers.
That's easy,
let's just™ add an inner [].find()
:
let result
numbers.find((x, i) =>
numbers.slice(i + 1).find((y, j) => {
const z = numbers.slice(j + 1).find((z) => x + y + z === targetSum)
if (!z) return false
result = x * y * z
return true
})
)
console.log(result)
Just for funsies,
I eventually also tried using simple for
loops
to see if they would be more readable:
function getResult() {
for (let i = 0; i < numbers.length; i++) {
const x = numbers[i]
for (let j = i + 1; j < numbers.length; j++) {
const y = numbers[j]
for (let k = j + 1; k < numbers.length; k++) {
const z = numbers[k]
if (x + y + z === targetSum) {
return x * y * z
}
}
}
}
}
console.log(getResult())
My eyes!
Here's one more, maybe a bit more readable than the previous:
function getResult() {
for (const [i, x] of numbers.entries()) {
for (const [j, y] of numbers.slice(i + 1).entries()) {
for (const [k, z] of numbers.slice(j + 1).entries()) {
if (x + y + z === 2020) {
return x * y * z
}
}
}
}
}
console.log(getResult())
Or maybe not.
My solutions are not the prettiest.
I would have liked to use maybe [].reduce()
and come up with an elegant solution,
but I couldn't.
Surely there must exist a nice and easy solution to this problem?
After some googling, I learned that this is called a subset sum problem. Part 1 can also be called "two sum problem."
After more googling, I couldn't find any short yet readable solution. Except this Ruby solution by /u/Sharparam/ on Reddit:
input = ARGF.readlines.map(&:to_i)
puts input.combination(2).find { |p| p.sum == 2020 }.reduce(&:*)
puts input.combination(3).find { |t| t.sum == 2020 }.reduce(&:*)
So I also learned about the
Ruby's Array#combination()
method.
It seems quite cool!