30:T8c6,class Tree { constructor(object) { this.root = new Node(object) this.leaves = this.root.getLeaves() } isReduced() { return (this.maxDepth() <= 4) && (this.maxValue() < 10) } maxDepth() { return Math.max(...this.leaves.map( leafNode => leafNode.depth())) } maxValue() { return Math.max(...this.leaves.map( leafNode => leafNode.value)) } getLeftmostIndexDeeperThan(depth) { for (let idx = 0; idx < this.leaves.length; idx++) { if (this.leaves[idx].depth() > depth) return idx } return null } getLeftmostIndexGreaterThan(value) { for (let idx = 0; idx < this.leaves.length; idx++) { if (this.leaves[idx].value > value) return idx } return null } reduce() { while (!this.isReduced()) { if (this.maxDepth() > 4) { // we need to explode let explodeIdx = this.getLeftmostIndexDeeperThan(4) let toTheLeft = null let toTheRight = null if (explodeIdx > 0) toTheLeft = this.leaves[explodeIdx - 1] if (explodeIdx < this.leaves.length - 2) toTheRight = this.leaves[explodeIdx + 2] let newLeaf = this.leaves[explodeIdx].parent.explode(toTheLeft, toTheRight) this.leaves.splice(explodeIdx, 2, newLeaf) } else { // we need to split let splitIdx = this.getLeftmostIndexGreaterThan(9); let splitted = this.leaves[splitIdx].split(); this.leaves.splice(splitIdx, 1, splitted[0], splitted[1]) } } } toString() { return this.root.toString() } add(t2) { let clone = new Tree(txtToObject(t2.toString())) let newRoot = new Node(null) newRoot.left = this.root this.root.parent = newRoot newRoot.right = clone.root clone.root.parent = newRoot this.root = newRoot this.leaves.push(...clone.leaves) this.reduce() } getMagnitude() { return this.root.getMagnitude() } }31:Tede,class Node { constructor(value, parent=null, isLeaf=false) { if (isLeaf) { this.value = value this.left = null this.right = null } else { if (value === null) { this.left = null this.right = null } else { if (typeof value.left === "number") this.left = new Node(value.left, this, true) else this.left = new Node(value.left, this) if (typeof value.right === "number") this.right = new Node(value.right, this, true) else this.right = new Node(value.right, this) } } this.parent = parent this.isLeaf = isLeaf } getLeaves() { if (this.isLeaf) return [this] let leaves = [] leaves.push(...this.left.getLeaves()) leaves.push(...this.right.getLeaves()) return leaves } leftmost() { if (this.isLeaf) return this else return this.left.leftmost() } rightmost() { if (this.isLeaf) return this else return this.right.rightmost() } depth() { if (this.parent === null) return 0 else return 1 + this.parent.depth() } isReduced() { return (this.maxChildrenValue() < 10) && (this.maxChildrenDepth() <= 4) } maxChildrenDepth() { let left = this.left.isLeaf ? this.left.depth() : this.left.maxChildrenDepth() let right = this.right.isLeaf ? this.right.depth() : this.right.maxChildrenDepth() return Math.max(left, right) } maxChildrenValue() { let left = this.left.isLeaf ? this.left.value : this.left.maxChildrenValue() let right = this.right.isLeaf ? this.right.value : this.right.maxChildrenValue() return Math.max(left, right) } nodeToTheLeft() { if (this.parent === null) { return null } if (this.parent.right === this) { return this.parent.left.rightmost() } return this.parent.nodeToTheLeft() } nodeToTheRight() { if (this.parent === null) { return null } if (this.parent.left === this) { return this.parent.right.leftmost() } return this.parent.nodeToTheRight() } explode(toTheLeft, toTheRight) { if (!(this.left.isLeaf && this.right.isLeaf)) { console.error("Can't explode non-leaves pairs") return } if (toTheLeft !== null) { toTheLeft.value += this.left.value } if (toTheRight !== null) { toTheRight.value += this.right.value } this.isLeaf = true this.left = null this.right = null this.value = 0 return this } split() { if (!this.isLeaf) { console.error("Can't split non leaf node") return } let left = Math.floor(this.value / 2) let right = Math.ceil(this.value / 2) this.isLeaf = false this.left = new Node(left, this, true) this.right = new Node(right, this, true) return [this.left, this.right] } toString() { if (this.isLeaf) return `${this.value}` else return `[${this.left.toString()},${this.right.toString()}]` } getMagnitude() { if (this.isLeaf) return this.value return 3 * this.left.getMagnitude() + 2 * this.right.getMagnitude() } }32:[{"id":"0ebd62cce87b55a6bc1d0165896015fd6830bb873f0759c9c3dc6c6dc0ada21b5ec145449a371dabf079def498263fd24f2c94d566a356878171a6e55b93f6ce","href":"https://static.observableusercontent.com/files/0ebd62cce87b55a6bc1d0165896015fd6830bb873f0759c9c3dc6c6dc0ada21b5ec145449a371dabf079def498263fd24f2c94d566a356878171a6e55b93f6ce","name":"18_input.txt","type":"text/plain","lastModified":1640188593186.791,"size":3324}] 2e:{"title":"Day 18: Snailfish","cells":[{"id":0,"value":"# Day 18: Snailfish","pinned":false,"hidden":false,"mode":"md"},{"id":3,"value":"## Part 1","pinned":false,"hidden":false,"mode":"md"},{"id":59,"value":"viewof addUpTo = Inputs.range([1, inputSnailNumbers.length], {label: \"Add up to {x} numbers\", step: 1, value:1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":45,"value":"addedInput = {\n let nbr = new Tree(txtToObject(inputSnailNumbers[0].toString()))\n for (let idx = 1; idx < addUpTo; idx++) {\n let nbr2 = inputSnailNumbers[idx]\n nbr.add(nbr2)\n }\n\n return nbr\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"addedInput.getMagnitude()","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"## Part 2","pinned":false,"hidden":false,"mode":"md"},{"id":93,"value":"{\n let maxMagnitude = 0\n for (let idx1 = 0; idx1 < inputSnailNumbers.length; idx1++) {\n for (let idx2 = 0; idx2 < inputSnailNumbers.length; idx2++) {\n let nbr1 = new Tree(txtToObject(inputSnailNumbers[idx1].toString()))\n let nbr2 = new Tree(txtToObject(inputSnailNumbers[idx2].toString()))\n nbr1.add(nbr2)\n let magnitude = nbr1.getMagnitude()\n if (magnitude > maxMagnitude)\n maxMagnitude = magnitude\n }\n }\n return maxMagnitude\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":11,"value":"# Input","pinned":false,"hidden":false,"mode":"md"},{"id":76,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":70,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":67,"value":"function txtToObject(txt) {\n return JSON.parse(txt.replace(/\\[/g, \"{\\\"left\\\":\")\n .replace(/\\]/g, \"}\")\n .replace(/,/g, \", \\\"right\\\":\"))\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":56,"value":"inputSnailNumbers = input.map( txt => new Tree(txtToObject(txt)))","pinned":true,"hidden":false,"mode":"ojs"},{"id":21,"value":"test = processSnailNumber(\"[[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":50,"value":"input = FileAttachment(\"18_input.txt\").text().then( txt => txt.trim().split(\"\\n\"))","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}