feat(2021-day-07): find least fuel usage using complex expenditure

developher-net · developher-net · commit b3a27cc506c8 · 2021-12-14T07:18:48.000-08:00
Crabs have an exponential (logarithmic?) cost for movement.
Solves part 2
diff --git a/2021/day-07/crabs.js b/2021/day-07/crabs.js
@@ -1,16 +1,36 @@
 const sum = (x, y) => x + y
 
-const getFuel = (crabs, destination) => {
-  return crabs.map((crab) => Math.abs(crab - destination))
-    .reduce(sum)
+const getFuel = (crabs, destination, exponential = false) => {
+  const simpleCalc = (crab) => {
+    const distance = Math.abs(crab - destination)
+    return distance
+  }
+
+  const expoCalc = (crab) => {
+    const distance = Math.abs(crab - destination)
+    let fuel = 0
+    for (let x = 1; x <= distance; x++) {
+      fuel += x
+    }
+    return fuel
+  }
+
+  if (exponential) {
+    return crabs.map(expoCalc).reduce(sum)
+  }
+  return crabs.map(simpleCalc).reduce(sum)
 }
 
-const getLeastFuel = (crabs) => {
-  const positions = crabs
-  let fuel = crabs.length * crabs.length // assume a cluster of crabs super far away is the initial worst case
-  positions.forEach((position) => {
-    fuel = Math.min(fuel, getFuel(crabs, position))
-  })
+const getLeastFuel = (crabs, exponential = false) => {
+  const positions = JSON.parse(JSON.stringify(crabs)) // Deep copy to ensure we aren't mutating the original data
+  let fuel = 100000000 // assume a stupid high fuel count to start
+  const highest = positions.sort((a, b) => b - a)[0] // Find the largest position
+  for (let x = 0; x <= highest; x++) {
+    console.debug(`Checking position ${x}`)
+    const proposed = getFuel(crabs, x, exponential)
+    console.debug(`Needed fuel would be ${proposed}`)
+    fuel = Math.min(fuel, proposed)
+  }
   return fuel
 }
 
diff --git a/2021/day-07/crabs.test.js b/2021/day-07/crabs.test.js
@@ -20,4 +20,17 @@ describe('--- Day 7: The Treachery of Whales ---', () => {
       })
     })
   })
+  describe('Part 2', () => {
+    describe('getFuel() exponentially', () => {
+      it('counts how much fuel is exponentially needed to position all the crabs', () => {
+        expect(getFuel(testCrabs, 5, true)).to.equal(168)
+        expect(getFuel(testCrabs, 2, true)).to.equal(206)
+      })
+    })
+    describe('getLeastFuel() exponentially', () => {
+      it('determine the fuel exponentially spent for the least costly position', () => {
+        expect(getLeastFuel(testCrabs, true)).to.equal(168)
+      })
+    })
+  })
 })
diff --git a/2021/day-07/solution.js b/2021/day-07/solution.js
@@ -22,8 +22,8 @@ fs.readFile(filePath, { encoding: 'utf8' }, (err, initData) => {
 
   const part2 = () => {
     const data = resetInput()
-    console.debug(data)
-    return 'No answer yet'
+    const result = getLeastFuel(data, true)
+    return result
   }
   const answers = []
   answers.push(part1())
