30:T6f1,function getTheoreticalBoundsX(target, trickShot=true, start=[0,0]) { let smallestTriangularFound = false let smallestValidCandidate = null let candidateSpeed = Math.floor((target.xmin - start[0]) / 4) while (!smallestTriangularFound) { let candidateValue = candidateSpeed * (candidateSpeed + 1) / 2 if (candidateValue < target.xmin) { // candidate speed does not reach the target, increase it or accept the previously found smallest valid candidate if (smallestValidCandidate !== null) smallestTriangularFound = true else candidateSpeed++ } else { if (candidateValue > target.xmax) { // candidate speed skips the target, decrease it candidateSpeed-- } else { // candidate speed leads to the target, store it as valid and keep looking for a smaller one if (smallestValidCandidate === null || smallestValidCandidate > candidateSpeed) { smallestValidCandidate = candidateSpeed } candidateSpeed-- } } } if (!trickShot) return {lower: smallestValidCandidate, upper: target.xmax} let highestValidCandidate = smallestValidCandidate candidateSpeed = smallestValidCandidate let highestTriangularFound = false while (!highestTriangularFound) { let candidateValue = candidateSpeed * (candidateSpeed + 1) / 2 if (candidateValue > target.xmax) { // candidate speed skips the target, return the highestValidCandidate found highestTriangularFound = true } else { // candidate speed leads to the target, store it as valid and keep looking for a higher one highestValidCandidate = candidateSpeed candidateSpeed++ } } return {lower: smallestValidCandidate, upper: highestValidCandidate} }31:T50b,function displayShotMD(target, speedX, speedY, showFullShotRange=false, start=[0, 0]) { let maxY = Math.max(-start[1], -target.ymin) let minY = Math.min(-start[1], -target.ymax, -start[1] - 20, start[1] - (speedY * (speedY + 1) / 2) * displayScale) let minX = Math.min(start[0], target.xmin) let maxX = Math.max(start[0], target.xmax, start[0] + (speedX * (speedX + 1) / 2)) let viewBoxHeight = showFullShotRange ? Math.abs(maxY - minY) + 2 : -(target.ymin) + 2 let md = `` return [md, maxYReached] }32:T67e,function getHitingSpeeds(target, start=[0, 0]) { let boundsX = getTheoreticalBoundsX(datasets[dataset], doTrickShot, start) let boundsY = getTheoreticalBoundsY(datasets[dataset], start) let validSpeeds = [] for (let candidateSpeedX = boundsX.lower; candidateSpeedX <= boundsX.upper; candidateSpeedX++) { for (let candidateSpeedY = boundsY.lower; candidateSpeedY <= boundsY.upper; candidateSpeedY++) { // compute the shot and see if it hits let pos = start.slice() let currentSpeedX = candidateSpeedX let currentSpeedY = candidateSpeedY let investigate = true while (investigate) { if (currentSpeedX === 0 && pos[0] < target.xmin) { // the probe will never reach the target investigate = false break } // Adjust horizontal speed and position if (currentSpeedX > 0) pos[0] += currentSpeedX-- else if (currentSpeedX < 0) pos[0] += currentSpeedX++ // Adjust vertical speed and position pos[1] += currentSpeedY-- if (pos[0] >= target.xmin && pos[0] <= target.xmax && pos[1] <= target.ymax && pos[1] >= target.ymin) { // The probe is inside the target investigate = false validSpeeds.push([candidateSpeedX, candidateSpeedY]) break } if (pos[0] > target.xmax) { // The probe overshoot the target investigate = false break } if (pos[1] < target.ymin) { // The probe went under the target investigate = false break } } } } return validSpeeds.length }33:[{"id":"0a1c48911c32d58186b8105f2b4b152bde43d954c1d6b41c49e3a5b859f0bc30340b95fa37e69fd78b7274d73b2107d6a23fb2b35544ebf9c86e4c8f433a3d45","href":"https://static.observableusercontent.com/files/0a1c48911c32d58186b8105f2b4b152bde43d954c1d6b41c49e3a5b859f0bc30340b95fa37e69fd78b7274d73b2107d6a23fb2b35544ebf9c86e4c8f433a3d45","name":"17_input.txt","type":"text/plain","lastModified":1639746080795.521,"size":36}] 2e:{"title":"Day 17: Trick Shot","cells":[{"id":0,"value":"# Day 17: Trick Shot","pinned":false,"hidden":false,"mode":"md"},{"id":3,"value":"## Part 1","pinned":false,"hidden":false,"mode":"md"},{"id":87,"value":"viewof dataset = Inputs.select([\"test\", \"input\"], {label: \"Dataset\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":295,"value":"viewof doTrickShot = Inputs.toggle({label: \"Do a trick shot !\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":181,"value":"viewof displayScale = Inputs.range([1, 5], {label: \"Display scale\", step: 1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"viewof speedX = {\n let bounds = getTheoreticalBoundsX(datasets[dataset], doTrickShot)\n return Inputs.range([bounds.lower, bounds.upper], {label: `Horizontal speed ([${bounds.lower},${bounds.upper}])`, step: 1})\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":203,"value":"viewof speedY = {\n let bounds = getTheoreticalBoundsY(datasets[dataset])\n return Inputs.range([bounds.lower, bounds.upper], {label: `Vertical speed ([${bounds.lower},${bounds.upper}])`, step: 1})\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":194,"value":"viewof shotStep = Inputs.range([0, 1000], {label: \"Shot step\", step: 1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":230,"value":"md`Max y reached : ${displayOutput[1]}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":233,"value":"md`${displayOutput[0]}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":115,"value":"displayOutput = displayShotMD(datasets[dataset], speedX, speedY)","pinned":true,"hidden":false,"mode":"ojs"},{"id":237,"value":"","pinned":true,"hidden":false,"mode":"ojs"},{"id":71,"value":"getTheoreticalBoundsX(test)","pinned":true,"hidden":false,"mode":"ojs"},{"id":267,"value":"getTheoreticalBoundsY(test)","pinned":true,"hidden":false,"mode":"ojs"},{"id":56,"value":"### Horizontal speed bounds\nFinding the lower bound for the horizontal speed means finding the speed at which the probe will enter the target's bounds on X with the lowest horizontal speed possible. Since the horizontal speed decreases by 1 at each step, this lower bound corresponds to the smallest [triangular number](https://en.wikipedia.org/wiki/Triangular_number) greater or equal to the target's `minX`.\n\nThe upper bound for which the probe would be shot within the target area is the speed at which the probe is sent to the target's `maxX` during the first step. However, if we are interested in sending the probe as high as possible, it is unlikely that it will end up within the target during the first step. Instead, we want to find the highest speed (starting from the lower bound) for which the shot is still within the target area.","pinned":false,"hidden":false,"mode":"md"},{"id":53,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":255,"value":"### Vertical speed bounds\nHere, we only consider the case where the target is lower than the starting position. No matter the shot speed and the highest position it reaches, the probe always ends up at the start height with a speed equal to `-1 * starting_vertical_speed - 1`. From this point, we can find the upper bound, which is the one for which the probe will skip the target area during the next step.\n\nThe lower bound is the (negative) speed at which the probe is shot directly at the lowest point of the target area.","pinned":false,"hidden":false,"mode":"md"},{"id":260,"value":"function getTheoreticalBoundsY(target, start=[0, 0]) {\n let candidateSpeed = 0\n let nextYPos = start[1] + candidateSpeed\n while (nextYPos >= target.ymin) {\n candidateSpeed--\n nextYPos = start[1] + candidateSpeed - 1\n }\n\n return {lower: target.ymin, upper: -candidateSpeed - 1}\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":106,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"## Part 2","pinned":false,"hidden":false,"mode":"md"},{"id":320,"value":"getHitingSpeeds(input)","pinned":true,"hidden":false,"mode":"ojs"},{"id":316,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":10,"value":"# Input","pinned":false,"hidden":false,"mode":"md"},{"id":91,"value":"datasets = ({\n test: test,\n input: input\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"function readInput(txt) {\n let [, xmin, xmax, ymin, ymax,] = txt.match(/x=(-?\\d+)\\.\\.(-?\\d+), y=(-?\\d+)\\.\\.(-?\\d+)/)\n return {\n xmin: parseFloat(xmin),\n xmax: parseFloat(xmax),\n ymin: parseFloat(ymin),\n ymax: parseFloat(ymax),\n width: Math.abs(xmax - xmin),\n height: Math.abs(ymax - ymin)\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":26,"value":"test = readInput(\"target area: x=20..30, y=-10..-5\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":23,"value":"input = FileAttachment(\"17_input.txt\").text().then( txt => readInput(txt))","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}