28:null 29:["$","title",null,{"children":"AOC Utilities | linard-y | Observable"}] 2f:T4c0,### `AOC.sequenceCyle()` Detect possibly infinitely repeating sequences (cycles) of items in a sequence generator. 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. 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.30: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(""); }31:T672,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, group: group, occurrences: occurrences, cloneArray: cloneArray, transposeArray: transposeArray, rotateArray: rotateArray, chunk: chunk, overwrite: overwrite, equalArrays: equalArrays, takeWhile: takeWhile, map2: map2, map3: map3, zipWith: zipWith, scanl: scanl, vAdd: vAdd, vSubtract: vSubtract, vScale: vScale, vMagnitude: vMagnitude, vNorm: vNorm, vDot: vDot, addToFreqTable: addToFreqTable, eliminate: eliminate, invertMap: invertMap, gInit: gInit, gMap: gMap, gMapWithLocation: gMapWithLocation, gAdjacency: gAdjacency, union: union, unions: unions, intersection: intersection, intersections: intersections, difference: difference, mapSet: mapSet, filterSet: filterSet, pairwiseCombinations: pairwiseCombinations, combinations: combinations, permutations: permutations, cartesianProduct: cartesianProduct, select: select, selectLargest: selectLargest, factors: factors, highestCommonFactor: highestCommonFactor, extendedEuclid: extendedEuclid, chineseRemainderTheorem: chineseRemainderTheorem, lowestCommonMultiple: lowestCommonMultiple, sequenceCycle: sequenceCycle, decToBinary: decToBinary, decToHex: decToHex, hexToBinary: hexToBinary, binaryToHex: binaryToHex, timer: timer, assert: assert, repeatWhile: repeatWhile, binarySearch: binarySearch, ocr: ocr })32:[] 2c:{"id":"51af19fa04316703","slug":null,"title":"AOC Utilities","thumbnail":"eeb6553f8ba495e0d116bc3088ad29d3af36ce1144772455279510799392605f","access_level":"public","create_time":"$D2023-12-12T07:13:07.248Z","update_time":"$D2023-12-12T07:13:07.248Z","view_time":null,"first_public_time":"$D2023-12-12T07:13:07.248Z","fork":{"id":"7bad949c15ad5fb1","slug":"aoc-utilities","title":"AOC Utilities","owner":{"id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood"}},"stars":0,"starred":false,"owner":{"type":"team","id":"9784867a3e59436b","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":"starter_2024"},"version":3186,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"c6e84137b8a39d94","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":null}],"members":[{"type":"individual","id":"c6e84137b8a39d94","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"5a7d4476817b0d1c","slug":"advent-of-code-2022","title":"Advent of Code 2022","owner":{"id":"9784867a3e59436b","login":"linard-y","name":""}},"type":"notebook","body":{"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. `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**`import {AOC} from \"@jwolondon/aoc-utilities\"`**","pinned":false,"hidden":false,"mode":"md"},{"id":416,"value":"## 1. Functional Utilities","pinned":false,"hidden":false,"mode":"md"},{"id":774,"value":"### `AOC.identity()`\n\nNotwithstanding 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:\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":771,"value":"identity = function(x) {\n return x;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":417,"value":"### `AOC.partial()`\n\nEasy 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":420,"value":"function partial(fn, firstArg) {\n return (...lastArgs) => fn(firstArg, ...lastArgs);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2235,"value":"### `AOC.type()`\nUnion 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":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":2618,"value":"### `AOC.mapObj()`\nCreate 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":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":3173,"value":"### `AOC.push()`\nThe 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":3179,"value":"function push(x, xs) {\n xs.push(x);\n return xs;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":362,"value":"## 2. Parsing","pinned":false,"hidden":false,"mode":"md"},{"id":369,"value":"### `AOC.linesToNumbers()`\n\nConvert 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":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":379,"value":"## 3. Array Functions","pinned":false,"hidden":false,"mode":"md"},{"id":863,"value":"### `AOC.equalArrays()`\n\nTests 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":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":1828,"value":"### `AOC.sum()`\n\nThe 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":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":1876,"value":"### `AOC.product()`\n\nThe 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":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":1880,"value":"### `AOC.mean()`\n\nThe 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":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":1890,"value":"### `AOC.gMean()`\n\nThe [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":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":1903,"value":"### `AOC.hMean()`\n\nThe [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":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":1913,"value":"### `AOC.median()`\n\nThe 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":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":397,"value":"### `AOC.sort()`\n\nSort 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":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":1431,"value":"### `AOC.range()`\n\nGenerate 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":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":717,"value":"### `AOC.splitAt()`\n\nSplit 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":721,"value":"function splitAt(i, xs) {\n return [xs.slice(0, i), xs.slice(i)];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":733,"value":"### `AOC.group()`\n\nGroup 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":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":763,"value":"### `AOC.occurrences()`\n\nCount 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":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":778,"value":"### `AOC.cloneArray()`\n\nClone 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":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":2775,"value":"### `AOC.transposeArray()`\nGiven 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":2781,"value":"function transposeArray(arr) {\n return arr[0].map((_, i) => arr.map((row) => row[i]));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2251,"value":"### `AOC.rotateArray()`\nCreate 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":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":2562,"value":"### `AOC.overwrite()`\n\nOverwrite 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":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":827,"value":"### `AOC.chunk()`\n\nChunk 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":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":907,"value":"### `AOC.takeWhile()`\n\nCreate 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":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":2910,"value":"### `AOC.zipWith()`\n\nCombine the elements of any number of arrays with the 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\",]) // [ [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```\n\nThis provides a more flexible alternative to the deprecated `AOC.map2()` and `AOC.map3()` functions as it works with any number of input arrays.","pinned":false,"hidden":false,"mode":"md"},{"id":2912,"value":"function zipWith(fn, ...arrays) {\n const shortestLength = arrays.reduce(\n (minLength, arr) => Math.min(minLength, arr.length),\n Infinity\n );\n const result = [];\n for (let i = 0; i < shortestLength; i++) {\n result.push(fn(...arrays.map((arr) => arr[i])));\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2302,"value":"### `AOC.scanl()`\nLike `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":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":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":2510,"value":"### `AOC.vAdd()` and `AOC.vSubtract()`\n\nAdd 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":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":2521,"value":"### `AOC.vScale()`\nScalar 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":2469,"value":"function vScale(v, s = 1) {\n return v.map((a) => a * s);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2532,"value":"### `AOC.vMagnitude()`\nThe 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":2479,"value":"function vMagnitude(v) {\n return Math.hypot(...v);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2537,"value":"### `AOC.vNorm()`\nCreate 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":2497,"value":"function vNorm(v) {\n return vScale(v, 1 / vMagnitude(v));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2547,"value":"### `AOC.vDot()`\nThe 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":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":1306,"value":"## 5. Frequency Distributions and Maps","pinned":false,"hidden":false,"mode":"md"},{"id":1663,"value":"### `AOC.addToFreqTable()`\n\nAllow 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":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":2104,"value":"### `AOC.eliminate()`\nReduce 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":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":2194,"value":"### `AOC.invertMap()`\n\nSwap 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":2200,"value":"function invertMap(dict) {\n return new Map([...dict.entries()].map(([k, v]) => [v, k]));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"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":1277,"value":"### `AOC.gInit()`\n\nInitialise 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":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":819,"value":"### `AOC.gMap()`\n\nMap 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":822,"value":"function gMap(fn, grid) {\n return chunk(grid.flat().map(fn), grid[0].length);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":850,"value":"### `AOC.gMapWithLocation`\n\nMap 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":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":2986,"value":"### `AOC.gAdjacency()`\n\nCalculates 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":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":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":549,"value":"### `AOC.union()`\n\nUnion 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":512,"value":"function union(a, b) {\n return new Set([...a, ...b]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":553,"value":"### `AOC.unions()`\n\nUnion 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":522,"value":"function unions(ss) {\n return ss.reduce(union, new Set());\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":556,"value":"### `AOC.intersection()`\n\nIntersection 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":516,"value":"function intersection(a, b) {\n return new Set([...a].filter(x => b.has(x)));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":560,"value":"### `AOC.intersections()`\n\nIntersection 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":530,"value":"function intersections(ss) {\n return ss.slice(1).reduce(intersection, ss[0]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":564,"value":"### `AOC.difference()`\n\nSet 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":519,"value":"function difference(a, b) {\n return new Set([...a].filter(x => !b.has(x)));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":590,"value":"### `AOC.mapSet()`\n\nMap 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":594,"value":"function mapSet(a, fn) {\n return new Set([...a].map(fn));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":603,"value":"### `AOC.filterSet()`\n\nFilter 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":607,"value":"function filterSet(a, fn) {\n return new Set([...a].filter(fn));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":617,"value":"## 8. Combinatorics","pinned":false,"hidden":false,"mode":"md"},{"id":1419,"value":"### `AOC.pairwiseCombinations()`\n\nGenerate 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":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":684,"value":"### `AOC.combinations()`\n\nChoose 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":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":1033,"value":"### `AOC.permutations()` \n\nAll 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":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":1123,"value":"### `AOC.cartesianProduct()`\n\n[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":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":2961,"value":"### `AOC.select()`\n\nFind 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":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":2951,"value":"### `AOC.selectLargest()`\n\nLike `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":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":2333,"value":"## 9. Number Theory","pinned":false,"hidden":false,"mode":"md"},{"id":2335,"value":"### `AOC.factors()`\nAll 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":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 lowerFactors = [];\n const upperFactors = [];\n const sqrt = Math.sqrt(n);\n\n for (let i = 1; i <= sqrt; i++) {\n if (n % i === 0) {\n lowerFactors.push(i);\n if (i !== sqrt) {\n // To avoid adding the square root twice\n upperFactors.unshift(n / i); // Adding larger factors in reverse order\n }\n }\n }\n return lowerFactors.concat(upperFactors);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2337,"value":"### `AOC.highestCommonFactor()`\nHighest 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":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":2850,"value":"### `AOC.extendedEuclid()`\n\nApplies 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":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":2893,"value":"### `AOC.chineseRemainderTheorem()`\n\nApplies 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":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":2339,"value":"### `AOC.lowestCommonMultiple()`\nSmallest 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":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":2638,"value":"$2f","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":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()`\n\nConvert 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":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":3002,"value":"### `AOC.decToHex()`\n\nConvert 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":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":3052,"value":"### `AOC.hexToBinary()`\n\nConvert 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":3049,"value":"function hexToBinary(hex) {\n return parseInt(hex, 16).toString(2).padStart(4, \"0\");\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3080,"value":"### `AOC.binaryToHex()`\n\nConvert 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":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":311,"value":"## 11. General Utilities","pinned":false,"hidden":false,"mode":"md"},{"id":351,"value":"### `AOC.timer()`\n\nFor 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":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":1287,"value":"### `AOC.assert()`\n\nCompare 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":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":1398,"value":"### `AOC.repeatWhile()`\nTight 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":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":2690,"value":"### `AOC.binarySearch()`\n\nGiven 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, arr.length - 1, 777); // 4\n```","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":2794,"value":"### `AOC.ocr()`\n\nSome 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":2796,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"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`import {Graph} from \"@jwolondon/gds-graph\"`","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":"$31","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}} 2d:"$2c:body"