30:T453,For storing sets of items (via their indices) that can be aggregated into sets when they are connected in some way. Allows fast querying such as - _Are these two things connected?_ - _If I connect these two things (via `union(n1,n2)`), what groups do I get?_ - _How many separate groups are there?_ Useful when needing to rapidly count numbers of components (disjoint sets) that arise from nodes connected via edges in a graph. For example: ```javascript const ds = new AOC.DisjointSet(5); // Values 0..4 initially each in their own singleton set ds.union(1, 4); // Merge the sets containing 1 and 4 ds.union(0, 3); // Merge the sets containing 0 and 3 ds.union(3, 2); // Merge the sets containing 2 and 3 ds.find(3) === ds.find(4); // Are 3 and 4 in the same connected component? (false) ds.find(2) === ds.find(0); // Are 2 and 0 in the same connected component? (true) ds.components; // How many connected components? (2) ``` One of its common applications is via [Kruskall's algorithm](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm) for calculating minimum spanning trees (MSTs) from a graph.31:T5f3,Detect possibly infinitely repeating sequences (cycles) of items in a sequence generator. The items created by the generating function should be primitives (e.g. numbers or strings) to enable comparison. The repeated sequence does not need to start from the beginning of the list to be detected. This uses [Brent's algorithm](https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algorithm) with the option of specifying a maximum length for cases where there is the possibility of no repeats in an infinite sequence. Given a maximum sequence length, a start value and a function that generates the next value in a sequence, return the length of the cycle and the zero-indexed position in the sequence of the first element of the cycle. If there is no cycle detected less than the maximum sequence length, will return an empty array. The point at which the function generates a value that has been generated previously, we know we have a cycle. For example, suppose we have the function `(x) => (x*x + 1) % 255` (generating the sequence `[3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101...]`). ```javascript AOC.sequenceCycle(10, 3, (x) => (x * x + 1) % 255); // [6, 2] ``` indicating the cycle is 6 items long starting at position 2 (zero-based) in the sequence. Calling ```javascript AOC.sequenceCycle(100, 3, (x) => x + 1) ``` Generates an empty array as there is no repeating sequence. For cycles that may contain multiple instances of a value before repeating, consider `AOC.arrayCycle()`.32:Tc62,function ocr(screen, letterWidth = 5) { if (letterWidth != 5) { // Allow different letter widths in the future. return "?"; } const letterMap5 = { "░██░░█░░█░█░░█░████░█░░█░█░░█░": "A", "███░░█░░█░███░░█░░█░█░░█░███░░": "B", "░██░░█░░█░█░░░░█░░░░█░░█░░██░░": "C", "███░░█░░█░█░░█░█░░█░█░░█░███░░": "D", "████░█░░░░███░░█░░░░█░░░░████░": "E", "████░█░░░░███░░█░░░░█░░░░█░░░░": "F", "░██░░█░░█░█░░░░█░██░█░░█░░███░": "G", "█░░█░█░░█░████░█░░█░█░░█░█░░█░": "H", "░███░░░█░░░░█░░░░█░░░░█░░░███░": "I", "░░██░░░░█░░░░█░░░░█░█░░█░░██░░": "J", "█░░█░█░█░░██░░░█░█░░█░█░░█░░█░": "K", "█░░░░█░░░░█░░░░█░░░░█░░░░████░": "L", "░█░█░█░█░██░█░██░█░██░░░██░░░█": "M", "█░░█░██░█░██░█░█░██░█░██░█░░█░": "N", "░██░░█░░█░█░░█░█░░█░█░░█░░██░░": "O", "███░░█░░█░█░░█░███░░█░░░░█░░░░": "P", "░██░░█░░█░█░░█░█░░█░░██░░░░░█░": "Q", "███░░█░░█░█░░█░███░░█░█░░█░░█░": "R", "░███░█░░░░█░░░░░██░░░░░█░███░░": "S", "░███░░░█░░░░█░░░░█░░░░█░░░░█░░": "T", "█░░█░█░░█░█░░█░█░░█░█░░█░░██░░": "U", "█░░░██░░░█░█░█░░█░█░░█░█░░░█░░": "V", "█░░░██░░░██░█░██░█░██░█░█░█░█░": "W", "█░░█░█░░█░░██░░░██░░█░░█░█░░█░": "X", "█░░░██░░░█░█░█░░░█░░░░█░░░░█░░": "Y", "░████░░░░█░░░█░░░█░░░█░░░░████": "Z" }; const screenCols = screen[0].length; const letters = []; for (let col = 0; col < screenCols; col += letterWidth) { const letterCols = screen.map((row) => row.slice(col, col + letterWidth)); const letter = letterCols.flat().join(""); letters.push(letterMap5[letter] || "?"); } return letters.join(""); }33:T764,AOC = ({ identity: identity, partial: partial, type: type, mapObj: mapObj, push: push, linesToNumbers: linesToNumbers, sum: sum, product: product, mean: mean, gMean: gMean, hMean: hMean, sort: sort, range: range, median: median, splitAt: splitAt, partition: partition, groupBy: groupBy, group: group, occurrences: occurrences, cloneArray: cloneArray, transposeArray: transposeArray, rotateArray: rotateArray, chunk: chunk, overwrite: overwrite, equalArrays: equalArrays, takeWhile: takeWhile, mapWhile: mapWhile, map2: map2, map3: map3, zip: zip, zipWith: zipWith, unzip: unzip, scanl: scanl, vAdd: vAdd, vSubtract: vSubtract, vScale: vScale, vMagnitude: vMagnitude, vNorm: vNorm, vDot: vDot, addToFreqTable: addToFreqTable, eliminate: eliminate, invertMap: invertMap, mergeMaps: mergeMaps, gInit: gInit, gMap: gMap, gMapWithLocation: gMapWithLocation, gIterator: gIterator, gAdjacency: gAdjacency, union: union, unions: unions, intersection: intersection, intersections: intersections, difference: difference, mapSet: mapSet, filterSet: filterSet, DisjointSet: DisjointSet, pairwiseCombinations: pairwiseCombinations, combinations: combinations, permutations: permutations, braceletPermutations: braceletPermutations, cartesianProduct: cartesianProduct, select: select, selectLargest: selectLargest, factors: factors, highestCommonFactor: highestCommonFactor, extendedEuclid: extendedEuclid, chineseRemainderTheorem: chineseRemainderTheorem, lowestCommonMultiple: lowestCommonMultiple, sequenceCycle: sequenceCycle, arrayCycle: arrayCycle, decToBinary: decToBinary, decToHex: decToHex, hexToBinary: hexToBinary, binaryToHex: binaryToHex, timer: timer, assert: assert, repeatWhile: repeatWhile, binarySearch: binarySearch, ocr: ocr })34:[{"id":"00f32d49a85be4e295fb8712821a7d4e3142eda074f9c6930e3abab4e9a07219fa55fa4b01164982212d115e5c3add0f570e2d57bdd3d8f5d5855810c93a3f9d","href":"https://static.observableusercontent.com/files/00f32d49a85be4e295fb8712821a7d4e3142eda074f9c6930e3abab4e9a07219fa55fa4b01164982212d115e5c3add0f570e2d57bdd3d8f5d5855810c93a3f9d","name":"image.png","type":"image/png","lastModified":1696093331303.58,"size":311861}] 2e:{"title":"AOC Utilities","cells":[{"id":0,"value":"# AOC Utilities\n\n*A collection of utilities for common javascript operations. Originally developed for [Advent of Code](https://adventofcode.com) they tend to reflect a more functional approach either explicitly (e.g. `partial`) or with functional-friendly operations (e.g. `zip`, `takeWhile`, `filterSet`).*","pinned":false,"hidden":false,"mode":"md"},{"id":2450,"value":"toc(\"h2\", \"\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":2455,"value":"To use any of these functions:\n\n```javascript\nimport {AOC} from \"@jwolondon/aoc-utilities\"\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3624,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":416,"value":"## 1. Functional Utilities","pinned":false,"hidden":false,"mode":"md"},{"id":3366,"value":"### `AOC.identity()`","pinned":false,"hidden":false,"mode":"md"},{"id":771,"value":"identity = function(x) {\n return x;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":774,"value":"Notwithstanding the fact that [most languages cannot define true identity functions](https://dev.to/rekreanto/why-it-is-impossible-to-write-an-identity-function-in-javascript-and-how-to-do-it-anyway-2j51), this identity function returns its first argument. Useful for some functional operations such as filtering an array of booleans. For example,\n\n```javascript\n[true, false, false, false, true].filter(AOC.identity).length; // 2\n```\nor simple cloning of an array:\n\n```javascript\nconst myArray = [1, 2, 3];\nconst newArray = myArray.map(AOC.identity); // [1, 2, 3]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3370,"value":"### `AOC.partial()`","pinned":false,"hidden":false,"mode":"md"},{"id":420,"value":"function partial(fn, firstArg) {\n return (...lastArgs) => fn(firstArg, ...lastArgs);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":417,"value":"Easy creation of partial functions and currying. Given a function with n parameters, create a new function with n-1 parameters when the first argument is provided. For example,\n\n```javascript\nconst add = (a, b) => a + b;\nconst addFive = AOC.partial(add, 5);\n \naddFive(10); // 15\n```\n\nTo supply more than one parameter, nest the partial applications.","pinned":false,"hidden":false,"mode":"md"},{"id":3376,"value":"### `AOC.type()`","pinned":false,"hidden":false,"mode":"md"},{"id":2246,"value":"function type(type, values) {\n return {\n case: (cases) => cases[type].apply(null, values),\n label: type\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2235,"value":"Union type creation. Useful when you wish to create enumerated types that may also carry data (similar to Elm's custom types or Haskell's `data`). For example, to create a union type with three variants, two of which carry data values:\n\n```javascript\nUser = ({\n Registered: (name, accountID) => AOC.type(\"Registered\", [name, accountID]),\n Visitor: (name) => AOC.type(\"Visitor\", [name]),\n Anonymous: AOC.type(\"Anonymous\", [])\n})\n```\n\nYou can then apply the equivalent of a `switch` to respond to each variant:\n\n```javascript\nfunction showUser(usr) {\n return usr.case({\n Registered: (name, accountID) => \"Registered with id \" + accountID,\n Visitor: (name) => \"Visitor with name \" + name,\n Anonymous: () => \"Anonymous user\"\n });\n}\n```\n\nFor simple comparisons with selected variant names, can reference the built in `label` property. For example,\n\n```javascript\nif (usr.label === \"Registered\") {\n// ...\n}\n```\n","pinned":false,"hidden":false,"mode":"md"},{"id":3380,"value":"### `AOC.mapObj()`","pinned":false,"hidden":false,"mode":"md"},{"id":2620,"value":"function mapObj(obj, fn) {\n return Object.fromEntries(\n Object.entries(obj).map(([k, v]) => [k, fn(k, v)])\n );\n }","pinned":false,"hidden":false,"mode":"ojs"},{"id":2618,"value":"Create a new object from an existing one and a `(key,value)` mapping function. For example,\n\n```javascript\nconst favourites = {\n Jo: [\"carrots\", \"peas\", \"apples\"],\n Sam: [\"oranges\"],\n Eliza: [\"pizza\", \"fizzy drink\"]\n };\n\nAOC.mapObj(favourites, (name, items) => items.length); // {Jo: 3, Sam: 1, Eliza: 2}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3384,"value":"### `AOC.push()`","pinned":false,"hidden":false,"mode":"md"},{"id":3179,"value":"function push(x, xs) {\n xs.push(x);\n return xs;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3173,"value":"The standard array prototype `push()` for adding items to the end of an array returns the new array length rather than the array itself. While the modifications are made in-place, it can still be useful to return the array, for example when used in a single line `reduce()` function. `AOC.push()` replicates the `push()` prototype, but returns the reference to the modified array. For example,\n\n```javascript\nAOC.push(\"d\", [\"a\", \"b\", \"c\"]) // Returns the modified array [\"a\", \"b\", \"c\", \"d\"]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3622,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":362,"value":"## 2. Parsing","pinned":false,"hidden":false,"mode":"md"},{"id":3390,"value":"### `AOC.linesToNumbers()`","pinned":false,"hidden":false,"mode":"md"},{"id":363,"value":"function linesToNumbers(str) {\n return str\n .trim()\n .split(\"\\n\")\n .filter((s) => s.trim().length > 0)\n .map(Number);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":369,"value":"Convert text into an array of numbers. Assumes input is numbers, one per line and will ignore blank lines. For example,\n\n```javascript\nAOC.linesToNumbers(`\n12\n14\n\n16\n\n`); // [12, 14, 16]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3528,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":379,"value":"## 3. Array Functions","pinned":false,"hidden":false,"mode":"md"},{"id":3531,"value":"### `AOC.equalArrays()`","pinned":false,"hidden":false,"mode":"md"},{"id":868,"value":"function equalArrays(a, b) {\n if (Array.isArray(a)) {\n return (\n Array.isArray(b) &&\n a.length === b.length &&\n a.every((val, index) => equalArrays(val, b[index]))\n );\n }\n return a === b;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":863,"value":"Tests whether the contents of two arrays are equal. Assumes arrays contain either primitives or are nested arrays of primitives. For example,\n\n```javascript\nAOC.equalArrays([1, 2, 3], [1, 2, 3]); // True\nAOC.equalArrays([1, 2, 3], [\"1\", \"2\", \"3\"]); // False\nAOC.equalArrays([1, [2, 3]], [1, 2, 3]); // False\nAOC.equalArrays([1, [2, 3]], [1, [2, 3]]); // true\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3535,"value":"### `AOC.sum()`","pinned":false,"hidden":false,"mode":"md"},{"id":380,"value":"function sum(xs) {\n return xs.filter(Number.isFinite).reduce((a, b) => a + b, 0);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1828,"value":"The sum of numbers in an array. Non-numeric values and types such as nested arrays, Booleans or strings, will be ignored. For example,\n\n```javascript\nAOC.sum([1, 2, [100, 200], 3, true, 4, \"5\", , \"cat\", 10]); // 1+2+3+4+10 = 20\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3539,"value":"### `AOC.product()`","pinned":false,"hidden":false,"mode":"md"},{"id":387,"value":"function product(xs) {\n return xs.filter(Number.isFinite).reduce((a, b) => a * b, 1);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1876,"value":"The product of numbers in an array. Non-numeric values and types such as nested arrays, Booleans or strings, will be ignored. For example,\n\n```javascript\nAOC.product([1, 2, [100, 200], 3, true, 4, \"5\", , \"cat\", 10]); // 1*2*3*4*10 = 240\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3543,"value":"### `AOC.mean()`","pinned":false,"hidden":false,"mode":"md"},{"id":1382,"value":"function mean(xs) {\n const numericXs = xs.filter(Number.isFinite);\n return sum(numericXs) / numericXs.length;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1880,"value":"The mean (average) of numbers in an array. Non-numeric values and types such as nested arrays, Booleans or strings, will be ignored. For example,\n\n```javascript\nAOC.mean([1, 2, 3, true, 4, \"5\"]); // (1+2+3+4)/4 = 2.5\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3547,"value":"### `AOC.gMean()`","pinned":false,"hidden":false,"mode":"md"},{"id":1463,"value":"function gMean(xs) {\n return Math.exp(mean(xs.filter(Number.isFinite).map(Math.log)));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1890,"value":"The [geometric mean](https://en.wikipedia.org/wiki/Geometric_mean) of numbers in an array. Non-numeric values and types such as nested arrays, Booleans or strings, will be ignored. For example,\n\n```javascript\nAOC.gMean([2, true, 8, \"5\"]); // sqrt(2*8) = 4\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3551,"value":"### `AOC.hMean()`","pinned":false,"hidden":false,"mode":"md"},{"id":1478,"value":"function hMean(xs) {\n const numericXs = xs.filter(Number.isFinite);\n return 1 / mean(numericXs.map((x) => 1 / x));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1903,"value":"The [harmonic mean](https://en.wikipedia.org/wiki/Harmonic_mean) of numbers in an array. Non-numeric values and types such as nested arrays, Booleans or strings, will be ignored. For example,\n\n```javascript\nAOC.hMean([1, true, 4, \"5\", 4]); // 3 / (1/1 + 1/4 + 1/4) = 2\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3555,"value":"### `AOC.median()`","pinned":false,"hidden":false,"mode":"md"},{"id":1361,"value":"function median(xs) {\n const sorted = sort(xs.map(identity)); // Copy array so original is not sorted.\n return sorted[Math.floor((sorted.length - 1) / 2)];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1913,"value":"The median of values in an array. If possible, will attempt to treat values as numeric when sorting. If the number of items is even, the left of the two central sorted values is returned. For example,\n\n```javascript\nAOC.median([1, 10, 4, 3, 2]); // 1 , 2 , *3* , 4 , 10\nAOC.median([\"cat\", \"ant\", \"dog\", \"bear\"]); // ant , *bear* , cat , dog\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3559,"value":"### `AOC.sort()`","pinned":false,"hidden":false,"mode":"md"},{"id":398,"value":"function sort(xs, desc = false) {\n if (isNaN(xs[0])) {\n return desc ? xs.sort().reverse() : xs.sort();\n }\n return desc ? xs.sort((a, b) => b - a) : xs.sort((a, b) => a - b);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":397,"value":"Sort respecting numerical values (default JavaScript array sort is lexicographical). Sort order will be ascending unless the optional second parameter is true, in which case order will be descending. Note that like the standard JavaScript sort, this will sort an array in place. To create a new sorted array, apply `map(AOC.identity)` first. For example,\n\n```javascript\nconst myArray = [2, 10, 4, 3];\nconst sorted = AOC.sort(myArray.map(AOC.identity)); // [2, 3, 4, 10]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3563,"value":"### `AOC.range()`","pinned":false,"hidden":false,"mode":"md"},{"id":1435,"value":"function range(a, b) {\n const [mn, mx] = [Math.min(a, b), Math.max(a, b)];\n const arr = [...Array(mx - mn + 1).keys()].map((x) => x + mn);\n return a < b ? arr : arr.reverse();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1431,"value":"Generate an array containing consecutive integers between the given pair of values inclusive. For example,\n\n```javascript\nAOC.range(4,7); // [4, 5, 6, 7]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3567,"value":"### `AOC.splitAt()`","pinned":false,"hidden":false,"mode":"md"},{"id":721,"value":"function splitAt(i, xs) {\n return [xs.slice(0, i), xs.slice(i)];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":717,"value":"Split an array at the given (zero-indexed) position creating two new arrays. Negative positions will set the split point relative to the end of the array. For example, \n\n```javascript\nAOC.splitAt(-2, [1, 2, 3, 4, 5]); // [[1, 2, 3], [4, 5]]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3626,"value":"### `AOC.partition()`","pinned":false,"hidden":false,"mode":"md"},{"id":3630,"value":"function partition(pred, xs) {\n const [tVals, fVals] = [[], []];\n xs.forEach((x) => {\n if (pred(x)) {\n tVals.push(x);\n } else {\n fVals.push(x);\n }\n });\n return [tVals, fVals];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3638,"value":"Partition an array to two arrays, allocating each array value to one of the two depending on whether the given predicate function applied to each element. For example,\n\n```javascript\nAOC.partition((x) => x % 2 === 0, AOC.range(1, 5)); // [ [2, 4], [1, 3, 5] ]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3726,"value":"### `AOC.groupBy()`","pinned":false,"hidden":false,"mode":"md"},{"id":3740,"value":"function groupBy(pred, xs) {\n const groups = [];\n let current = [];\n\n for (const item of xs) {\n if (pred(item)) {\n if (current.length > 0) {\n groups.push(current);\n current = [];\n }\n continue;\n }\n current.push(item);\n }\n\n if (current.length > 0) {\n groups.push(current);\n }\n return groups;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3750,"value":"Partitions an array by identifying delimiters determined by a given predicate that is applied to each array item. The delimiter values are not returned in the grouped array. For example,\n\n```javaScript\nAOC.groupBy((d) => d % 3 === 0, [1, 2, 3, 4, 5, 6, 7]) // [[1,2], [4,5], [7]]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3571,"value":"### `AOC.group()`","pinned":false,"hidden":false,"mode":"md"},{"id":737,"value":"function group(xs) {\n const groupReducer = (grps, x) => {\n let lastGroup = grps.at(-1);\n if (!lastGroup || lastGroup.at(-1) !== x) {\n grps.push([x]);\n } else {\n lastGroup.push(x);\n }\n return grps;\n };\n return xs.reduce(groupReducer, []);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":733,"value":"Group consecutive elements in a list, placing each group in its own array. For example, \n\n```javascript\nAOC.group([ 1, 2, 2, 3, 1, 1, 1, 2 ]); // [[1], [2, 2], [3], [1, 1, 1], [2]]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3575,"value":"### `AOC.occurrences()`","pinned":false,"hidden":false,"mode":"md"},{"id":762,"value":"function occurrences(y, xs) {\n return xs.reduce((total, c) => (c === y ? total + 1 : total), 0);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":763,"value":"Count the number of occurrences of `y` in an array. For example,\n\n```javascript\nAOC.occurrences(\"a\", [...\"abracadabra\"]); // 6\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3579,"value":"### `AOC.cloneArray()`","pinned":false,"hidden":false,"mode":"md"},{"id":779,"value":"function cloneArray(arr) {\n const clone = [];\n arr.forEach(v => {\n if (Array.isArray(v)) {\n clone.push(cloneArray(v));\n } else {\n clone.push(v);\n }\n });\n return clone;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":778,"value":"Clone an array. This will deep copy multi-dimenisonal arrays but assumes that all array elements are themselves arrays or primitives. For example,\n\n```javascript\nconst arr = [1, 2, [\"a\", \"b\"]];\nconst newArr = AOC.cloneArray(arr);\n// newArr === arr is false but AOC.equalArrays(newArr, arr) is true.\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3583,"value":"### `AOC.transposeArray()`","pinned":false,"hidden":false,"mode":"md"},{"id":2781,"value":"function transposeArray(arr) {\n return arr[0].map((_, i) => arr.map((row) => row[i]));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2775,"value":"Given a 2d array, transpose 'rows' and 'columns'. For example,\n\n```javaScript\nconst arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]];\nconst tArray = transposeArray(arr); // [[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3587,"value":"### `AOC.rotateArray()`","pinned":false,"hidden":false,"mode":"md"},{"id":2291,"value":"function rotateArray(arr, n = 1) {\n n = n % arr.length;\n return arr.slice(-n, arr.length).concat(arr.slice(0, -n));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2251,"value":"Create a new array from an existing one rotated by _n_ steps (default 1) such that the list _n_ elements are moved to the front. A negaitve value of _n_ rotates in the opposite direction. For example,\n\n```javascript\nconst arr = [\"a\", \"b\", \"c\", \"d\"];\nAOC.rotateArray(arr); // [\"d\", \"a\", \"b\", \"c\"]\nAOC.rotateArray(arr, -1); // [\"b\", \"c\", \"d\", \"a\"]\nAOC.rotateArray(arr, 2); // [\"c\", \"d\", \"a\", \"b\"]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3591,"value":"### `AOC.overwrite()`","pinned":false,"hidden":false,"mode":"md"},{"id":2571,"value":"function overwrite(xs, ys, offset = 0) {\n xs.splice(offset, ys.length, ...ys);\n return xs;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2562,"value":"Overwrite the contents of the first array with the contents of the second. If the second array is shorter, the extra elements of the first are left unaltered. If the second array is longer, the contents for the first are entirely replaced with the second. Can optionally offset where in the first array the overwriting happens. Applies the changes in place but also returns the modified array. For example,\n\n```javascript\nconst xs = [1, 2, 3, 4, 5];\nconst ys = [10, 20];\nconst zs = [100, 200, 300, 400];\n\nAOC.overwrite(xs, ys, 1); // xs is now [1, 10, 20, 4, 5]\nAOC.overwrite(ys, zs); // ys is now [100, 200, 300, 400]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3595,"value":"### `AOC.chunk()`","pinned":false,"hidden":false,"mode":"md"},{"id":830,"value":"function chunk(arr, n) {\n return arr.reduce((chunks, val) => {\n let last = chunks.at(-1);\n if (!last || last.length === n) {\n chunks.push([val]);\n } else {\n last.push(val);\n }\n return chunks;\n }, []);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":827,"value":"Chunk an array into an array of arrays of a given size. The last element may be smaller than the chunk size if the array is not a multiple of the chunk size. The operation leaves the original array intact and creates a shallow copy in the chunked array. For example,\n\n```javascript\nAOC.chunk([1, 2, 3, 4, 5, 6, 7], 3); // [[1, 2, 3], [4, 5, 6], [7]]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3599,"value":"### `AOC.takeWhile()`","pinned":false,"hidden":false,"mode":"md"},{"id":910,"value":"function takeWhile(fn, xs) {\n const result = [];\n for (const x of xs) {\n if (!fn(x)) {\n return result;\n }\n result.push(x);\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":907,"value":"Create a new array by taking values from a given one while the given predicate is true. As soon as it becomes false, no more values will be copied. For example,\n\n```javascript\nAOC.takeWhile((x) => x < 10, [1, 6, 10, 2]); // [1, 6]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3603,"value":"### `AOC.mapWhile()`","pinned":false,"hidden":false,"mode":"md"},{"id":3294,"value":"function mapWhile(mapFn, predFn, xs) {\n const result = [];\n for (const x of xs) {\n const y = mapFn(x);\n if (!predFn(y)) {\n return result;\n }\n result.push(y);\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3296,"value":"Like `AOC.takeWhile()` except it applies the given mapping function (first parameter) to each element before testing against the predicate (second function) to determine when to terminate. Returns all the mapped values while the predicate evaluation was true. Because JavaScript does not perform lazy evaluation, this function is useful for cases where the mapping function might be costly, so minimises the times the mapping takes place. \n\n```javascript\nAOC.mapWhile(Math.log, (x) => x < 3, [10, 20, 30, 40, 50]) // [2.303, 2.996]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3607,"value":"### `AOC.zip()`","pinned":false,"hidden":false,"mode":"md"},{"id":3246,"value":"function zip(...cols) {\n return zipWith((...col) => col, ...cols);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3238,"value":"Combine any number of column arrays into an array of tuples (row arrays). If the input arrays are of different lengths, the resulting array will be the size of the smallest one. For example\n\n```javascript\nAOC.zip([1, 2, 3], [\"a\", \"b\", \"c\",]) // [ [1,\"a\"], [2,\"b\"], [3,\"c\"] ]\nAOC.zip([1, 2, 3], [\"a\", \"b\"]) // [ [1,\"a\"], [2,\"b\"] ]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3611,"value":"### `AOC.zipWith()`","pinned":false,"hidden":false,"mode":"md"},{"id":2912,"value":"function zipWith(fn, ...arrays) {\n const minLen = arrays.reduce(\n (minLength, arr) => Math.min(minLength, arr.length),\n Infinity\n );\n const result = new Array(minLen);\n for (let i = 0; i < minLen; i++) {\n result[i] = fn(...arrays.map((arr) => arr[i]));\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2910,"value":"Generalisation of `AOC.zip` combining column arrays with a given zipping function (first parameter). If the input arrays are of different lengths, the resulting array will be the size of the smallest one. For example,\n\n```javascript\nAOC.zipWith((a, b) => [a, b], [1, 2, 3], [\"a\", \"b\", \"c\",]) // Equivalent to AOC.zip(), giving [ [1,\"a\"], [2,\"b\"], [3,\"c\"] ]\nAOC.zipWith((a, b) => a - b, [1, 2, 3], [5, 4, 3]) // [-4, -2, 0]\nAOC.zipWith((...arrs) => Math.min(...arrs), [10, 4, 3], [6, 7, 9], [4, 4, 4]) // [4,4,3]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3615,"value":"### `AOC.unzip()`","pinned":false,"hidden":false,"mode":"md"},{"id":3223,"value":"function unzip(xss) {\n return xss.reduce(\n (acc, xs) => acc.map((row, i) => [...row, xs[i]]),\n Array(xss[0].length)\n .fill()\n .map(() => [])\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3229,"value":"Given an array of tuples (row arrays), split them into separate column arrays. The inverse of `AOC.zip(tuples)`. For example,\n\n```javascript\nAOC.unzip([ [1, \"a\"], [2, \"b\"], [3, \"c\"]]) // [ [1, 2, 3], [\"a\", \"b\", \"c\"] ]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3619,"value":"### `AOC.scanl()`","pinned":false,"hidden":false,"mode":"md"},{"id":2304,"value":"function scanl(xs, f, init) {\n return xs.map(\n (\n (acc) => (e) =>\n (acc = f(acc, e))\n )(init)\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2302,"value":"Like `reduce()` except that each iteration of the reduction function is stored in an array. `xs` (first parameter) provides the source of values to pass to the accumulating function `f` (second parameter) after being initialised with `init` (3rd parameter). The accumulating function should have the form `f(acc,x)` For example, a sequence of factorials:\n\n```javascript\nAOC.scanl([1, 2, 3, 4, 5], (acc, x) => x*acc, 1); // [1, 2, 4, 6, 24, 120]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3505,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":2432,"value":"## 4. Vectors\n\nConvenience functions for working with vectors of any length. Note that AoC usually works with integers so beware floating point errors when calculating vector magnitudes and normalised vectors when results are expected to be integers.","pinned":false,"hidden":false,"mode":"md"},{"id":3508,"value":"### `AOC.vAdd()` and `AOC.vSubtract()`","pinned":false,"hidden":false,"mode":"md"},{"id":2464,"value":"function vAdd(v1, v2) {\n return map2(v1, v2, (a, b) => a + b);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2474,"value":"function vSubtract(v1, v2) {\n return map2(v1, v2, (a, b) => a - b);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2510,"value":"Add or subtract two vectors. For example,\n\n```javascript\nconst v1 = [1, 2, 3];\nconst v2 = [10, 20, 30];\nAOC.vAdd(v1, v2); // [11, 22, 33]\nAOC.vSubtract(v2,v1); // [9, 18, 27]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3513,"value":"### `AOC.vScale()`","pinned":false,"hidden":false,"mode":"md"},{"id":2469,"value":"function vScale(v, s = 1) {\n return v.map((a) => a * s);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2521,"value":"Scalar multiply a vector of any length. For example,\n```javascript\nAOC.vScale([1, 2, 3], 10); // [10, 20, 30]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3517,"value":"### `AOC.vMagnitude()`","pinned":false,"hidden":false,"mode":"md"},{"id":2479,"value":"function vMagnitude(v) {\n return Math.hypot(...v);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2532,"value":"The magnitude (length) of a vector of any length. For example,\n```javascript\nAOC.vMagnitude([5, 12]); // 13\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3521,"value":"### `AOC.vNorm()`","pinned":false,"hidden":false,"mode":"md"},{"id":2497,"value":"function vNorm(v) {\n return vScale(v, 1 / vMagnitude(v));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2537,"value":"Create a normalised version of a vector (one whose magnitude is 1). For example,\n```javascript\nAOC.vNorm([30, 40]); // [0.6, 0.8]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3525,"value":"### `AOC.vDot()`","pinned":false,"hidden":false,"mode":"md"},{"id":2485,"value":"function vDot(v1, v2) {\n return v2.reduce((acc, a, i) => acc + a * v1[i], 0);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2547,"value":"The dot product of two vectors. For example,\n```javascript\nAOC.vDot([1, 4], [2, 2]); // 10\nAOC.vDot([3, 4], [3, 4]); // 25\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3503,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":1306,"value":"## 5. Frequency Distributions and Maps","pinned":false,"hidden":false,"mode":"md"},{"id":3361,"value":"### `AOC.addToFreqTable()`","pinned":false,"hidden":false,"mode":"md"},{"id":1309,"value":"function addToFreqTable(freqTable, v, n = 1) {\n const freq = freqTable.get(v);\n return freqTable.set(v, freq ? freq + n : n);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1663,"value":"Allow the accumulation of frequencies of any primitives in a [Map](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map). For example,\n\n```javascript\nconst fTable = new Map();\n[...\"abracadabra\"].forEach((c) => AOC.addToFreqTable(fTable, c));\n// fTable contains {\"a\" => 5, \"b\" => 2, \"r\" => 2, \"c\" => 1, \"d\" => 1}\n```\n\nCan optionally supply a third parameter indicating by how much to increase frequency when item added to the map. For example,\n\n```javascript\nconst scores = { bronze: 1, silver: 2, gold: 3 };\nconst mTable = new Map();\n[\"gold\", \"bronze\", \"gold\"].forEach((m) =>\n AOC.addToFreqTable(mTable, m, scores[m])\n); // {\"gold\" => 6, \"bronze\" => 1}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3357,"value":"### `AOC.eliminate()`","pinned":false,"hidden":false,"mode":"md"},{"id":2106,"value":"function eliminate(dict) {\n const singletons = new Map([...dict].filter(([k, v]) => v.size === 1));\n\n if (singletons.size === dict.size) {\n // All sets are singletons, so directly convert them into values.\n return new Map([...singletons].map(([k, v]) => [k, [...v][0]]));\n }\n\n const confirmed = unions([...singletons.values()]);\n\n if (confirmed.size === 0) {\n console.warn(\"AOC.setEliminate cannot solve.\", dict);\n return new Map();\n }\n\n // Remove the singleton element from all non-singleton sets.\n return eliminate(\n new Map(\n [...dict].map(([k, v]) =>\n v.size === 1 ? [k, v] : [k, difference(v, confirmed)]\n )\n )\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2104,"value":"Reduce a `Map` of `key => Set` to a `Map` of `key => value` via elimination. Assumes each value in the union of sets can be allocated to only one key. Requires at least one singleton set on each iteration of elimination to solve. If cannot be solved, an empty `Map` is returned. For example,\n\n```javaScript\nconst dict = new Map([\n [1, new Set([\"cat\", \"dog\", \"fish\"])],\n [2, new Set([\"dog\"])],\n [3, new Set([\"fish\", \"dog\"])]\n ]);\nAOC.eliminate(dict); // {1 => \"cat\", 2 => \"dog\", 3 => \"fish\"}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3353,"value":"### `AOC.invertMap()`","pinned":false,"hidden":false,"mode":"md"},{"id":2200,"value":"function invertMap(dict) {\n return new Map([...dict.entries()].map(([k, v]) => [v, k]));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2194,"value":"Swap the keys and values of a `Map`. Assumes both are a unique sets. If values are not unique, later values, as determined by original key order, will replace earlier values when transformed into keys. For example,\n\n```javascript\nAOC.invertMap(\n new Map([\n [1, \"a\"],\n [2, \"b\"],\n [3, \"c\"],\n [4, \"a\"]\n ]);\n) // {\"a\" => 4, \"b\" => 2, \"c\" => 3}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3349,"value":"### `AOC.mergeMaps()`","pinned":false,"hidden":false,"mode":"md"},{"id":3336,"value":"function mergeMaps(map1, map2, fn = (a, b) => a + b) {\n if (map2.size === 0) {\n return new Map(map1);\n }\n const mergedMap = new Map(map1);\n for (const [k, v] of map2) {\n mergedMap.set(k, mergedMap.has(k) ? fn(mergedMap.get(k), v) : v);\n }\n return mergedMap;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3333,"value":"Combines two maps creating a new merged map. Where a key exists in both maps, the value associated with that key will be, by default, the sum of the two values, otherwise the key-value pairs from both maps are added to the merged map. For example,\n```javascript\nAOC.mergeMaps(\n new Map([[1, 10],[2, 20],[3, 30]]),\n new Map([[3, 100],[4, 200]])\n) // {1 => 10, 2 => 20, 3 => 130, 4 => 200}\n```\n\nCan be customised with any combining function (third parameter) that takes two values as parameters to create a combined value. For example,\n\n```javascript\nAOC.mergeMaps(\n new Map([[1, 10],[2, 20],[3, 30]]),\n new Map([[3, 100],[4, 200]]),\n Math.min\n) // {1 => 10, 2 => 20, 3 => 30, 4 => 200}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3501,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":816,"value":"## 6. Grid Functions\n\n_Convenince functions that work on 2d arrays of primitives. Useful for raster processing._","pinned":false,"hidden":false,"mode":"md"},{"id":3476,"value":"### `AOC.gInit()`","pinned":false,"hidden":false,"mode":"md"},{"id":1280,"value":"function gInit(nRows, nCols, val = 0) {\n const grid = [];\n\n for (let row = 0; row < nRows; row++) {\n grid[row] = [];\n for (let col = 0; col < nCols; col++) {\n grid[row][col] = val;\n }\n }\n return grid;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1277,"value":"Initialise a grid with the given number of rows and columns and the given value. Fills the grid with 0s if not specified. For example,\n\n```javascript\nAOC.gInit(3, 2, \"a\"); // [[\"a\", \"a\"], [\"a\", \"a\"], [\"a\", \"a\"]]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3480,"value":"### `AOC.gMap()`","pinned":false,"hidden":false,"mode":"md"},{"id":822,"value":"function gMap(fn, grid) {\n return chunk(grid.flat().map(fn), grid[0].length);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":819,"value":"Map the values of a 2d grid with the given function returning a new grid with the mapped values. Leaves the input grid unchanged. For example,\n\n```javascript\nconst grid = AOC.gInit(3, 2, 1);\nconst newGrid = AOC.gMap((n) => n * 10, grid); // [[10, 10], [10, 10], [10, 10]]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3484,"value":"### `AOC.gMapWithLocation()`","pinned":false,"hidden":false,"mode":"md"},{"id":853,"value":"function gMapWithLocation(fn, grid) {\n const numRows = grid.length;\n const numCols = grid[0].length;\n const g2 = [];\n for (let row = 0; row < numRows; row++) {\n const r = [];\n for (let col = 0; col < numCols; col++) {\n r.push(fn(row, col, grid[row][col]));\n }\n g2.push(r);\n }\n return g2;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":850,"value":"Map the values of a 2d grid with the given function `f(row,col,val)` where _row_ and _col_ are the grid location and `val` is the grid value at that location. For example,\n\n```javascript\nconst [nRows, nCols] = [4, 3];\nconst grid = AOC.gInit(nRows, nCols);\nconst newGrid = AOC.gMapWithLocation((r, c, _) => r * nCols + c, grid);\n// [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, 10, 11]]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3676,"value":"### `AOC.gIterator()`","pinned":false,"hidden":false,"mode":"md"},{"id":3679,"value":"function* gIterator(grid) {\n for (let r = 0; r < grid.length; r++) {\n for (let c = 0; c < grid[0].length; c++) {\n yield [r, c, grid[r][c]];\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3691,"value":"An iterator that will scan a 2d grid from top-left in row-prime order providing a _`[row, col, gridVal]`_ triplet at each step. Can be useful for reducing functions and for processes that do not need to generate new grids.\nFor example,\n\n```javaScript\nconst [nRows, nCols] = [4, 3];\nconst grid = AOC.gInit(nRows, nCols);\nconst sum = d3.sum([...gIterator(grid)], ([r, c, _]) => r * nCols + c); // 66 (sum of 0,1,2...11)\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3488,"value":"### `AOC.gAdjacency()`","pinned":false,"hidden":false,"mode":"md"},{"id":2988,"value":"function gAdjacency(n = 1, includeOrigin = false) {\n const adj = d3.cross(d3.range(-n, n + 1), d3.range(-n, n + 1));\n return includeOrigin ? adj : adj.filter((d) => !(d[0] === 0 && d[1] === 0));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2986,"value":"Calculates the offsets from a grid location to its adjacent neighbours. The first parameter is the number of adjacency 'rings' to generate (defaulting to 1). The second parameter allows the zero-offset origin point (`[0,0]`) to be included if `true`. For example,\n\n```javascript\nAOC.gAdjacency(); // [ [-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1] ,[1,0] ,[1,1] ]\nAOC.gAdjacency(3, true); // [ [-3,-3], [-3,-2], [-3,-1] ... [3,3]] including [0,0]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3491,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":509,"value":"## 7. Set Functions\n\nWhile ES6 has a [Set](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set) object, it lacks some basic bulk set operations. These are added here as convenience functions. Partially based on these [set functions](https://exploringjs.com/impatient-js/ch_sets.html).","pinned":false,"hidden":false,"mode":"md"},{"id":3447,"value":"### `AOC.union()`","pinned":false,"hidden":false,"mode":"md"},{"id":512,"value":"function union(a, b) {\n return new Set([...a, ...b]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":549,"value":"Union of sets `a` and `b`. For example,\n\n```javascript\nconst animals = new Set([\"ant\", \"bear\", \"cat\"]);\nconst fruit = new Set([\"plum\", \"apple\"]);\nAOC.union(animals, fruit); // {\"ant\", \"bear\", \"cat\", \"plum\", \"apple\"}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3452,"value":"### `AOC.unions()`","pinned":false,"hidden":false,"mode":"md"},{"id":522,"value":"function unions(ss) {\n return ss.reduce(union, new Set());\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":553,"value":"Union of an array of sets. For example,\n\n```javascript\nconst things = [new Set([\"ant\", \"bear\", \"cat\"]), new Set([\"plum\", \"apple\"])];\nAOC.unions(things); // {\"ant\", \"bear\", \"cat\", \"plum\", \"apple\"}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3456,"value":"### `AOC.intersection()`","pinned":false,"hidden":false,"mode":"md"},{"id":516,"value":"function intersection(a, b) {\n return new Set([...a].filter(x => b.has(x)));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":556,"value":"Intersection of sets `a` and `b`. For example,\n\n```javascript\nconst fruit = new Set([\"apple\", \"orange\", \"banana\"]);\nconst colours = new Set([\"red\", \"yellow\", \"orange\"]);\nAOC.intersection(fruit, colours); // {\"orange\"}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3460,"value":"### `AOC.intersections()`","pinned":false,"hidden":false,"mode":"md"},{"id":530,"value":"function intersections(ss) {\n return ss.slice(1).reduce(intersection, ss[0]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":560,"value":"Intersection of an array of sets. For exmple,\n\n```javascript\nconst things = [\n new Set([\"apple\", \"orange\", \"banana\"]),\n new Set([\"red\", \"yellow\", \"orange\"]),\n new Set([\"smith\", \"007\", \"drew\", \"orange\"])\n];\nAOC.intersections(things); // {\"orange\"}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3464,"value":"### `AOC.difference()`","pinned":false,"hidden":false,"mode":"md"},{"id":519,"value":"function difference(a, b) {\n return new Set([...a].filter(x => !b.has(x)));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":564,"value":"Set of items in set `a` that are not in set `b`. For example,\n\n```javascript\nconst fruit = new Set([\"apple\", \"orange\", \"banana\"]);\nconst colours = new Set([\"red\", \"yellow\", \"orange\"]);\nAOC.difference(fruit, colours); // {\"apple\", \"bananas\"}\nAOC.difference(colours, fruit); // {\"red\", \"yellow\"}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3468,"value":"### `AOC.mapSet()`","pinned":false,"hidden":false,"mode":"md"},{"id":594,"value":"function mapSet(a, fn) {\n return new Set([...a].map(fn));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":590,"value":"Map the contents of a set with a given function. For example,\n\n```javascript\nconst fruit = new Set([\"apple\", \"orange\", \"banana\"]);\nAOC.mapSet(fruit, (s) => s.toUpperCase()); // {\"APPLE\", \"ORANGE\", \"BANANA\"}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3472,"value":"### `AOC.filterSet()`","pinned":false,"hidden":false,"mode":"md"},{"id":607,"value":"function filterSet(a, fn) {\n return new Set([...a].filter(fn));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":603,"value":"Filter a set with the given predicate function. For example, fruit that contain an 'e':\n\n```javascript\nconst fruit = new Set([\"apple\", \"orange\", \"banana\"]);\nAOC.filterSet(fruit, (s) => s.includes(\"e\")); // {\"apple\", \"orange\"}\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3761,"value":"### `AOC.DisjointSet()`","pinned":false,"hidden":false,"mode":"md"},{"id":3765,"value":"class DisjointSet {\n constructor(n) {\n this.rank = Array(n).fill(0);\n this.parent = d3.range(0, n);\n this.components = n;\n }\n find(x) {\n if (this.parent[x] !== x) {\n this.parent[x] = this.find(this.parent[x]);\n }\n return this.parent[x];\n }\n\n union(x, y) {\n const xRoot = this.find(x);\n const yRoot = this.find(y);\n if (xRoot === yRoot) {\n return false; // No merging as already in the same set.\n }\n if (this.rank[xRoot] < this.rank[yRoot]) {\n this.parent[xRoot] = yRoot;\n } else if (this.rank[yRoot] < this.rank[xRoot]) {\n this.parent[yRoot] = xRoot;\n } else {\n this.parent[yRoot] = xRoot;\n this.rank[xRoot] = this.rank[xRoot] + 1;\n }\n this.components--;\n return true;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3769,"value":"$30","pinned":false,"hidden":false,"mode":"md"},{"id":3493,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":617,"value":"## 8. Combinatorics","pinned":false,"hidden":false,"mode":"md"},{"id":3423,"value":"### `AOC.pairwiseCombinations()`","pinned":false,"hidden":false,"mode":"md"},{"id":1413,"value":"function pairwiseCombinations(xs) {\n return xs.map((v, i) => xs.slice(i + 1).map((w) => [v, w])).flat();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1419,"value":"Generate all combinations (therefore ignoring order) of size 2 from an array. For example,\n\n```javascript\nAOC.pairwiseCombinations([1, 2, 3]); // [[1, 2], [1, 3], [2, 3]]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3427,"value":"### `AOC.combinations()`","pinned":false,"hidden":false,"mode":"md"},{"id":686,"value":"function combinations(k, xs, prefix = []) {\n if (k == 0) {\n return [prefix];\n }\n return xs.flatMap((x, i) =>\n combinations(k - 1, xs.slice(i + 1), [...prefix, x])\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":684,"value":"Choose all combinations (i.e. where order is unimportant) of size `k` from a given array of items. For example,\n\n```javascript\nAOC.combinations(3, [1, 2, 3, 4]); // [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3431,"value":"### `AOC.permutations()` ","pinned":false,"hidden":false,"mode":"md"},{"id":1040,"value":"function permutations(xs) {\n const result = [xs.slice()];\n const len = xs.length;\n const c = new Array(len).fill(0);\n let i = 1;\n\n while (i < len) {\n if (c[i] < i) {\n const k = i % 2 && c[i];\n const p = xs[i];\n xs[i] = xs[k];\n xs[k] = p;\n c[i]++;\n i = 1;\n result.push(xs.slice());\n } else {\n c[i] = 0;\n i++;\n }\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1033,"value":"All permutations (i.e where order of items matters) of a given array of items. For example,\n\n```javascript\nAOC.permutations([1, 2, 3]); \n// [\n// [1, 2, 3],\n// [2, 1, 3],\n// [3, 1, 2],\n// [1, 3, 2],\n// [2, 3, 1],\n// [3, 2, 1]\n// ]\n```\n","pinned":false,"hidden":false,"mode":"md"},{"id":3813,"value":"### `AOC.braceletPermutations()` ","pinned":false,"hidden":false,"mode":"md"},{"id":3811,"value":"function braceletPermutations(xs) {\n const cmp = (a, b) => (a < b ? -1 : a > b ? 1 : 0);\n const n = xs.length;\n\n const anchor = xs[0]; // Ignore rotations\n const ys = xs.slice(1); // Permute remainder\n const result = [];\n\n const accept = () => {\n // Store only one of ys and reverse(ys).\n const d = cmp(ys[0], ys.at(-1));\n if (d !== 0) {\n return d < 0;\n }\n // For ties, compare ys and reverse(ys)\n for (let i = 0, j = ys.length - 1; i < ys.length; i++, j--) {\n const dj = cmp(ys[i], ys[j]);\n if (dj !== 0) {\n return dj < 0;\n }\n }\n return true;\n };\n\n if (accept()) {\n result.push([anchor, ...ys]);\n }\n\n const len = ys.length;\n const c = new Array(len).fill(0);\n let i = 1;\n\n while (i < len) {\n if (c[i] < i) {\n const k = i % 2 === 0 ? 0 : c[i];\n [ys[i], ys[k]] = [ys[k], ys[i]];\n c[i]++;\n i = 1;\n\n if (accept()) {\n result.push([anchor, ...ys]);\n }\n } else {\n c[i] = 0;\n i++;\n }\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3817,"value":"All circular permutations ignoring reflected sequences (i.e. one permutation per dihedral group). For example, `[1, 2, 3]` has only one circular permutation (itself), and \n\n```javaScript\nAOC.braceletPermutations([1, 2, 3, 4])\n// [\n// [1, 2, 3, 4],\n// [1, 3, 2, 4],\n// [1, 2, 4, 3]\n// ]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3435,"value":"### `AOC.cartesianProduct()`","pinned":false,"hidden":false,"mode":"md"},{"id":1127,"value":"function cartesianProduct(...arrays) {\n return arrays.reduce((xs, ys) =>\n xs.flatMap((x) => ys.map((y) => [x, y].flat()))\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1123,"value":"[Cartesian product](https://en.wikipedia.org/wiki/Cartesian_product) of any number of arrays. For example,\n\n```javascript\nAOC.cartesianProduct([1, 2, 3], [\"a\", \"b\"]);\n// [\n// [1, \"a\"],\n// [1, \"b\"],\n// [2, \"a\"],\n// [2, \"b\"],\n// [3, \"a\"],\n// [3, \"b\"]\n// ]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3439,"value":"### `AOC.select()`","pinned":false,"hidden":false,"mode":"md"},{"id":2962,"value":"function select(xs) {\n if (xs.length === 0) {\n return [];\n }\n\n const [x, ...xTail] = xs;\n const tailResult = select(xTail);\n const currentTuple = [x, xTail];\n const updatedTailResult = tailResult.map(([y, ys]) => [y, [x, ...ys]]);\n return [currentTuple, ...updatedTailResult];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2961,"value":"Find all combinations of the elements in a given array in the form of (e, rest of the array). For example,\n\n```javascript\nAOC.select([1,2,3,4]); // [ [1,[2,3,4]], [2,[1,3,4]], [3,[1,2,4]], [4,[1,2,3]]]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3443,"value":"### `AOC.selectLargest()`","pinned":false,"hidden":false,"mode":"md"},{"id":2953,"value":"function selectLargest(xs) {\n return select(xs).map(([e, rest]) => [e, rest.filter((y) => y < e)]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2951,"value":"Like `AOC.select()` except each list of 'rest of array' are those smaller than `e`. For example,\n\n```javascript\nAOC.selectLargest [ 1, 2, 3, 4 ]; // [ [ 1, [] ], [ 2, [ 1 ] ], [ 3, [ 1, 2 ] ], [ 4, [ 1, 2, 3 ] ] ]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3495,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":2333,"value":"## 9. Number Theory","pinned":false,"hidden":false,"mode":"md"},{"id":3419,"value":"### `AOC.factors()`","pinned":false,"hidden":false,"mode":"md"},{"id":2341,"value":"function factors(n) {\n if (n < 1) {\n throw new Error(\"Number must be greater than 0 to calculate factors.\");\n }\n if (n === 1) {\n return [1];\n }\n\n const [lower, upper] = [[], []];\n const sqrt = Math.sqrt(n);\n\n for (let i = 1; i <= sqrt; i += 1) {\n if (n % i === 0) {\n lower.push(i);\n if (i !== sqrt) {\n // To avoid adding the square root twice\n upper.push(n / i);\n }\n }\n }\n\n return lower.concat(upper.reverse());\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2335,"value":"All the factors (divisors with no remainder) of a given natural number. A prime will have factors of just 1 and the prime itself. For example,\n\n```javascript\nAOC.factors(12); // [1, 2, 3, 4, 6, 12]\nAOC.factors(13); // [1, 13]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3415,"value":"### `AOC.highestCommonFactor()`","pinned":false,"hidden":false,"mode":"md"},{"id":2380,"value":"function highestCommonFactor(a, b) {\n if (a === 0 && b === 0) {\n return 1;\n }\n while (b != 0) {\n const t = b;\n b = a % b;\n a = t;\n }\n return Math.abs(a);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2337,"value":"Highest common factor (HCF) of two numbers. By definition, if the HCF is 1, the numbers are [coprime](https://en.wikipedia.org/wiki/Coprime_integers). Note that for convenience, this also returns a value when both numbers are 0 (1), when one is zero (the non-zero number) and when values are negative (the HCF of their positive equivalents). For example,\n\n```javascript\nAOC.highestCommonFactor(12, 16); // 4\nAOC.highestCommonFactor(12, 13); // 1\nAOC.highestCommonFactor(-9, 27); // 9\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3410,"value":"### `AOC.extendedEuclid()`","pinned":false,"hidden":false,"mode":"md"},{"id":2851,"value":"function extendedEuclid(a, b) {\n if (b === 0) {\n return [a, 1, 0];\n } else {\n const [g, x, y] = extendedEuclid(b, a % b);\n return [g, y, x - Math.floor(a / b) * y];\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2850,"value":"Applies the [extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) that calculates not only the highest common factor (${tex`hcf`}) of two numbers ${tex`a`} and ${tex`b`}, but also the values ${tex`x`} and ${tex`y`} such that\n\n${tex`ax+by=hcf(a,b)`}\n\nFor example,\n\n```javascript\nAOC.extendedEuclid(5,12); // [1, 5, -2] i.e. HCF is 1, x is 5 and y is -2\nAOC.extendedEuclid(24, 12); // [12, 0, 1] i.e. HCF is 12, x is 0 and y is 1\nAOC.extendedEuclid(240, 46); // [2, -9, 47] i.e. HCF is 2, x is -9 and y is 46\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3406,"value":"### `AOC.chineseRemainderTheorem()`","pinned":false,"hidden":false,"mode":"md"},{"id":2900,"value":"function chineseRemainderTheorem(n, a) {\n const prod = n.reduce((acc, val) => acc * val, 1);\n const partialResults = n.map(\n (mod, i) => (a[i] * prod * extendedEuclid(prod / mod, mod)[1]) / mod\n );\n return partialResults.reduce((acc, val) => acc + val, 0) % prod;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2893,"value":"Applies the [Chinese remainder theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem). For some integer ${tex`n`}, given a list of divisors and their respective remainders, will calculate the remainder of ${tex`n`} divided by the product of the divisors. For example,\n\n```javascript\nAOC.chineseRemainderTheorem([3, 5, 7], [2, 3, 2]); // 23 because n % (3*5*7) is 23 if n%3 is 2 and n%5 is 3 and n%7 is 2\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3402,"value":"### `AOC.lowestCommonMultiple()`","pinned":false,"hidden":false,"mode":"md"},{"id":2411,"value":"function lowestCommonMultiple(...args) {\n const lcmPair = (a, b) => {\n return Math.abs(a * b) / highestCommonFactor(a, b);\n };\n return args.reduce((acc, n) => lcmPair(acc, n), 1);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2339,"value":"Smallest number that is divisible by the given numbers. For example,\n\n```javascript\nAOC.lowestCommonMultiple(4, 6); // 12\nAOC.lowestCommonMultiple(5, 13, 23); // 1495 (product if all are primes)\nAOC.lowestCommonMultiple(...AOC.range(1, 20)) // 232792560\n``` ","pinned":false,"hidden":false,"mode":"md"},{"id":3398,"value":"### `AOC.sequenceCyle()`","pinned":false,"hidden":false,"mode":"md"},{"id":2647,"value":"function sequenceCycle(maxCycleLength, x0, f) {\n const iterate = (n, initial, fn) => {\n let x = initial;\n for (let i = 0; i < n; i++) {\n x = fn(x);\n }\n return x;\n };\n\n const findLambda = (tortoise, hare, lam, p) =>\n maxCycleLength > 0 && lam > maxCycleLength\n ? \"Nothing\"\n : tortoise === hare\n ? lam\n : p === lam\n ? findLambda(hare, f(hare), 1, p * 2)\n : findLambda(tortoise, f(hare), lam + 1, p);\n\n const findMu = (tortoise, hare, mu) =>\n tortoise === hare ? mu : findMu(f(tortoise), f(hare), mu + 1);\n\n const lambda = findLambda(x0, f(x0), 1, 1);\n if (lambda === \"Nothing\") {\n return [];\n }\n return [lambda, findMu(x0, iterate(lambda, x0, f), 0)];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2638,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":3394,"value":"### `AOC.arrayCycle()`","pinned":false,"hidden":false,"mode":"md"},{"id":3192,"value":"function arrayCycle(xs) {\n for (let start = 0; start < xs.length; start++) {\n for (let len = 1; len <= (xs.length - start) / 2; len++) {\n let repeat = true;\n // Does the sequence repeat for the first time?\n for (let i = start; i < start + len; i++) {\n if (xs[i] !== xs[i + len]) {\n repeat = false;\n break;\n }\n }\n if (repeat) {\n // Does the sequence repeats to the end?\n for (let j = start + 2 * len; j < xs.length; j++) {\n if (xs[j] !== xs[j - len]) {\n repeat = false;\n break;\n }\n }\n if (repeat) {\n return [len, start];\n }\n }\n }\n }\n return []; // No repeating sequence found\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3188,"value":"Detect possibly infinitely repeating sequences (cycles) of items in a given array. Items should be primitives (e.g. numbers or strings) to enable comparison. The repeated sequence does not have to start at the beginning of the array. Returns the length of the cycle and the zero-indexed position in the sequence of the first element of the cycle. If there is no cycle detected within the array, it will return an empty array.\n\nUnlike `AOC.sequenceCycle()`, this method can be applied to cycles that may contain multiple instances of a value. For example, the following identifies a sequence of length 3 (`1,3,5`) starting at zero-indexed position 4 in the array:\n\n```javascript\nAOC.arrayCycle([1, 2, 3, 4, 1, 3, 5, 1, 3, 5]); // [3, 4]\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3497,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":919,"value":"## 10. Number Conversion","pinned":false,"hidden":false,"mode":"md"},{"id":3072,"value":"_(For conversions from hex to decimal and binary to decimal, use JavaScript's `parseInt(h,16)` and `parseInt(b,2)` respectively.)_","pinned":false,"hidden":false,"mode":"md"},{"id":939,"value":"### `AOC.decToBinary()`","pinned":false,"hidden":false,"mode":"md"},{"id":920,"value":"function decToBinary(dec, digits = 0) {\n const padDigit = dec < 0 ? '1' : '0';\n // Unsigned right-shift by 0 positions coerces the number into an unsigned integer.\n return (dec >>> 0).toString(2).padStart(digits, padDigit);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3650,"value":"Convert a decimal number to a binary string. Can optionally specify the minimum number of digits. If the number contains any digits after a decimal point, they are ignored. Negative numbers will be represented with 2s complement. For example,\n\n```javascript\nAOC.decToBinary(127,32); // \"00000000000000000000000001111111\"\nAOC.decToBinary(-1); // \"11111111111111111111111111111111\"\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3002,"value":"### `AOC.decToHex()`","pinned":false,"hidden":false,"mode":"md"},{"id":3004,"value":"function decToHex(n, digits = 2) {\n return (\n (n < 0 ? \"-\" : \"\") +\n Math.round(Math.abs(n)).toString(16).padStart(digits, \"0\")\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3653,"value":"Convert a decimal number to a hex string. Can optionally specify the minimum number of digits (default 2). Will round real numbers to nearest integer.\n\n```javascript\nAOC.decToHex(127); // \"7f\"\nAOC.decToHex(-14.5, 4); // \"-000f\"\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3052,"value":"### `AOC.hexToBinary()`","pinned":false,"hidden":false,"mode":"md"},{"id":3049,"value":"function hexToBinary(hex) {\n return parseInt(hex, 16).toString(2).padStart(4, \"0\");\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3656,"value":"Convert a hex string to a binary string. In this each hex digit will always be padded to 4 digits.\n\n```javascript\nAOC.hexToBinary(\"f\"); // \"1111\"\nAOC.hexToBinary(\"ff00aa\"); // \"111111110000000010101010\"\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3080,"value":"### `AOC.binaryToHex()`","pinned":false,"hidden":false,"mode":"md"},{"id":3084,"value":"function binaryToHex(bin, digits = 0) {\n return parseInt(bin, 2).toString(16).padStart(digits, \"0\");\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3659,"value":"Convert a binary string to a hex string. Can optionally specify the minimum number of digits.\n\n```javascript\nAOC.binaryToHex(\"1111\"); // \"f\"\nAOC.binaryToHex(\"111111110000000010101010\", 8); // \"00ff00aa\"\n```","pinned":false,"hidden":false,"mode":"md"},{"id":3499,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":311,"value":"## 11. General Utilities","pinned":false,"hidden":false,"mode":"md"},{"id":351,"value":"### `AOC.timer()`","pinned":false,"hidden":false,"mode":"md"},{"id":2,"value":"function timer(fn, input, repeats = 1) {\n const t0 = performance.now();\n let result;\n for (let i = 0; i < repeats; i++) {\n result = fn(input);\n }\n const t1 = performance.now();\n const time = (t1 - t0) / repeats;\n const dps = time > 0.1 ? (time > 1 ? (time > 10 ? 0 : 1) : 2) : 3;\n return result + \". Completed in \" + time.toFixed(dps) + \" milliseconds.\";\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3662,"value":"For reporting the time it takes to complete a function. Useful for empirical algorithm efficiency estimation. First parameter is the function to run, the second, its input and the third optional parameter indicating the number of times to call the function (default once). The result is a message reporting the result of the function and the average time for completion in milliseconds. For example,\n\n```javascript\nconst isPrime = (n) => {\n const m = Math.floor(Math.sqrt(n));\n for (let i = 2; i <= m; i++) {\n if (n % i == 0) {\n return false;\n }\n }\n return true;\n};\n\nAOC.timer(isPrime, 87178291199, 10); // \"true. Completed in 9.7 milliseconds.\"\n```","pinned":false,"hidden":false,"mode":"md"},{"id":1287,"value":"### `AOC.assert()`","pinned":false,"hidden":false,"mode":"md"},{"id":1291,"value":"function assert(\n obs,\n exp = \"value not yet provided\",\n msg = \"✗ Assertion failed\"\n) {\n if (obs === exp) {\n return md`✓`;\n } else {\n throw msg + `: expected ${exp}, while observed value was ${obs}.`;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3665,"value":"Compare observed with expected results. Useful for refactoring when you want to confirm you haven't introduced any regressions. Correct assertions generate a tick symbol while false ones generate a red error message. For example,\n\n```javascript\nconst isPalindrome = (s) => AOC.equalArrays([...s], [...s].reverse());\n\nAOC.assert(isPalindrome(\"abba\"), true);\n// ✓\n\nAOC.assert(isPalindrome(\"Abba\"), true);\n// ✗ Assertion failed: expected false, while observed value was true.\n```","pinned":false,"hidden":false,"mode":"md"},{"id":1398,"value":"### `AOC.repeatWhile()`","pinned":false,"hidden":false,"mode":"md"},{"id":1402,"value":"function repeatWhile(predicateFn, maxIterations = 10000) {\n for (let i = 0; i < maxIterations; i++) {\n if (!predicateFn()) {\n return;\n }\n }\n throw `repeatWhile exit condition never satisfied in ${maxIterations} iterations.`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3668,"value":"Tight while loops that run the risk of never satisfying their exit condition can lock an Observable page. This safe version can limit the number of iterations before exiting. The first parameter is a predicate function to evaluate on each iteration. The second optional parameter can set a maximum number of iterations before exiting with an exception (default of 10000). For example,\n\n```javascript\nconst collatz = (n) => (n % 2 == 0 ? n / 2 : 3 * n + 1);\nlet current = 999999;\nAOC.repeatWhile(() => (current = collatz(current)) > 2, 1000); \n// No exception because takes less than 1000 iterations. \n```","pinned":false,"hidden":false,"mode":"md"},{"id":2690,"value":"### `AOC.binarySearch()`","pinned":false,"hidden":false,"mode":"md"},{"id":2692,"value":"function binarySearch(fn, min, max, target) {\n // Assumes function is linear, but could be positve or negative wrt to argument\n const dir = fn(max) >= fn(min) ? 1 : -1;\n let lwr = min;\n let upr = max;\n while (lwr <= upr) {\n const m = Math.floor((lwr + upr) / 2);\n if (dir * fn(m) < dir * target) {\n lwr = m + 1;\n } else if (dir * fn(m) > dir * target) {\n upr = m - 1;\n } else {\n return m;\n }\n }\n // No match with target found.\n return undefined;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3671,"value":"Given some monotonic function f(n), find the value of n that evaluates to the given target. Starts with the given lower and upper bounds and refines search space with O(log n) efficiency. If no integer value is found within the limits, returns `undefined`.\n\nFor example, to find the index of a given value in an array:\n\n```javascript\nconst xs = [0, 1, 7, 77, 777, 7777];\nreturn AOC.binarySearch((i) => xs[i], 0, xs.length - 1, 777); // 4\n```","pinned":false,"hidden":false,"mode":"md"},{"id":2794,"value":"### `AOC.ocr()`","pinned":false,"hidden":false,"mode":"md"},{"id":2796,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":3674,"value":"Some puzzles generate a screen of pixels that when viewed show a simple text message. Using a standard pixel 'fonts' this function will translate a screen with a given character width fonts into their text equivalent. Assumes pixels are represented with the unicode block symbols representing on `█` and off `░`.\n\nFor example,\n\n```javascript\nconst screen = [\n \"░██░░░██░░░██░░\",\n \"█░░█░█░░█░█░░█░\",\n \"█░░█░█░░█░█░░░░\",\n \"████░█░░█░█░░░░\",\n \"█░░█░█░░█░█░░█░\",\n \"█░░█░░██░░░██░░\"\n];\nreturn ocr(screen); // \"AOC\"\n```","pinned":false,"hidden":false,"mode":"md"},{"id":1261,"value":"---\n## Data Structure Libraries\n\n_These are not included in the `AOC` namespace, but can be useful data structures for common Advent of Code challenges._","pinned":false,"hidden":false,"mode":"md"},{"id":1271,"value":"### Double-ended queue\n\nFast implementation, can be used for standard queues and stacks too. See the [API documentation](https://docs.page/invertase/denque/api) for details.","pinned":false,"hidden":false,"mode":"md"},{"id":1259,"value":"Denque = require(\"denque@2/index.js\").catch(() => window[\"Denque\"])","pinned":false,"hidden":false,"mode":"ojs"},{"id":1390,"value":"### Priority queue\nFor a simple priority queue class with `put()`, `get()` and `isEmpty()`:","pinned":false,"hidden":false,"mode":"md"},{"id":2815,"value":"class PriorityQueue {\n constructor() {\n this.elements = [];\n }\n\n isEmpty() {\n return this.elements.length === 0;\n }\n\n put(item, priority) {\n this.elements.push({ item, priority });\n this.elements.sort((a, b) => a.priority - b.priority);\n }\n\n get() {\n return this.elements.shift().item;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2813,"value":"For a more fully implemented priority queue with `add()`, `remove()`, `poll()`, `peek()` etc. See the [API documentation](https://github.com/lemire/FastPriorityQueue.js/) for details.","pinned":false,"hidden":false,"mode":"md"},{"id":1393,"value":"PQ = require(\"https://bundle.run/fastpriorityqueue@0.7.1\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":2726,"value":"{\n const pets = new PQ((obj1, obj2) => obj1.score > obj2.score);\n pets.add({ pet: \"Alpaca\", score: 27 });\n pets.add({ pet: \"Spider\", score: 0 });\n pets.add({ pet: \"Axolotyl\", score: 99 });\n return [pets.poll(), pets.poll(), pets.poll()].map((p) => p.pet);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2226,"value":"### Linked Lists\nLibrary of various linked lists including singly and doubly linked lists, both linear and circular. Useful for tasks with lots of internal list rearrangement. See the the [API documentation](https://github.com/Floofies/LinkedList) for details.","pinned":false,"hidden":false,"mode":"md"},{"id":2228,"value":"LL = (await import(\"https://cdn.skypack.dev/listlib@1.0.2?min\")).default","pinned":false,"hidden":false,"mode":"ojs"},{"id":2327,"value":"### Graph Data Structure\nFor graph storage, shortest path detection, topological sorting etc. see [GDS graph](https://observablehq.com/@jwolondon/gds-graph). Use with\n\n```javaScript\nimport {Graph} from \"@jwolondon/gds-graph\"\n```","pinned":false,"hidden":false,"mode":"md"},{"id":1725,"value":"---\n\n## Appendices","pinned":false,"hidden":false,"mode":"md"},{"id":2942,"value":"_Depricated functions_","pinned":false,"hidden":false,"mode":"md"},{"id":968,"value":"function map2(xs, ys, fn) {\n const arr = [];\n for (let i = 0; i < Math.min(xs.length, ys.length); i++) {\n arr.push(fn(xs[i], ys[i]));\n }\n return arr;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1496,"value":"function map3(xs, ys, zs, fn) {\n const arr = [];\n for (let i = 0; i < Math.min(xs.length, ys.length, zs.length); i++) {\n arr.push(fn(xs[i], ys[i], zs[i]));\n }\n return arr;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2445,"value":"_For automatic table of contents_","pinned":false,"hidden":false,"mode":"md"},{"id":2442,"value":"function toc(selector = \"h1,h2,h3\", heading = \"Table of Contents\") {\n return Generators.observe((notify) => {\n let headings = [];\n\n function observed() {\n const h = Array.from(document.querySelectorAll(selector));\n if (h.length !== headings.length || h.some((h, i) => headings[i] !== h)) {\n notify(\n html`${heading}

${DOM.text(h.textContent)}`,\n { onclick: (e) => (e.preventDefault(), h.scrollIntoView()) }\n );\n })}`\n );\n }\n }\n\n const observer = new MutationObserver(observed);\n observer.observe(document.body, { childList: true, subtree: true });\n observed();\n return () => observer.disconnect();\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":357,"value":"_Places all utility functions in a single AOC object for protected namespace:_","pinned":false,"hidden":false,"mode":"md"},{"id":318,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}