JavaScript: Array, 41–53

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23const total = (xs) => xs.reduce((t, n) => t + n, 0);
const mean = (xs) => (xs.length === 0 ? NaN : total(xs) / xs.length);

function median(xs) {
  if (xs.length === 0) return NaN;
  const sorted = [...xs].sort((a, b) => a - b);       // a copy, and numeric
  const mid = Math.floor(sorted.length / 2);
  return sorted.length % 2 ? sorted[mid] : (sorted[mid - 1] + sorted[mid]) / 2;
}

const spread = (xs) => (xs.length === 0 ? NaN : Math.max(...xs) - Math.min(...xs));

const readings = [4, 1, 9, 1, 100];

console.log('readings :', readings);
console.log('mean     :', mean(readings), '<- dragged upwards by the 100');
console.log('median   :', median(readings), '<- unmoved by it');
console.log('range    :', spread(readings));
console.log('even count:', median([1, 2, 3, 4]), '<- the average of 2 and 3');
console.log('--- the comparator matters ---');
console.log('median([10, 9, 1]) :', median([10, 9, 1]));
console.log('a default sort gives:', [10, 9, 1].sort(), 'so the middle would be', [10, 9, 1].sort()[1]);
console.log('input afterwards   :', readings);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18function modes(xs) {
  const counts = xs.reduce((m, v) => m.set(v, (m.get(v) ?? 0) + 1), new Map());
  if (counts.size === 0) return [];
  const best = Math.max(...counts.values());
  return [...counts].filter(([, n]) => n === best).map(([v]) => v);
}

// When one answer is required, say in the name which one you took.
const firstMode = (xs) => modes(xs)[0];

const trips = ['bus', 'keke', 'bus', 'okada', 'bus'];

console.log('modes(trips)      :', modes(trips));
console.log('a tie             :', modes([1, 1, 2, 2]), '<- both, in first-seen order');
console.log('all distinct      :', modes([1, 2, 3]), '<- everything ties at one');
console.log('empty             :', modes([]));
console.log('firstMode of a tie:', firstMode([2, 2, 1, 1]));
console.log('NaN can be a mode :', modes([NaN, NaN, 1]).map(String));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27// Run an operation against a fresh array and report whether it was changed.
const changed = (run) => {
  const a = [3, 1, 2];
  run(a);
  return !same(a, [3, 1, 2]);
};

const mutators = [
  (a) => a.push(9), (a) => a.pop(), (a) => a.shift(), (a) => a.unshift(0),
  (a) => a.splice(1, 1), (a) => a.sort(), (a) => a.reverse(), (a) => a.fill(0),
];

const copiers = [
  (a) => a.map((n) => n), (a) => a.filter(() => true), (a) => a.slice(),
  (a) => a.concat([4]), (a) => a.flat(), (a) => a.join('-'),
];

console.log('mutating methods changed the array:', mutators.map(changed));
console.log('copying methods left it alone      :', copiers.map(changed));
console.log('--- what the mutators hand back ---');
console.log("push(2)        ->", [1].push(2), '(the new length)');
console.log('pop()          ->', [1, 2].pop(), '(the element removed)');
console.log('shift()        ->', [1, 2].shift(), '(the first element)');
console.log('unshift(0)     ->', [1].unshift(0), '(the new length)');
console.log('splice(0, 2)   ->', [1, 2, 3].splice(0, 2), '(an array of what went)');
console.log('sort()         ->', [2, 1].sort(), '(the same array)');
console.log('pop() on empty ->', [].pop(), '(undefined, and no error)');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22const original = [[1, 2], { seats: 9 }, new Date('2024-03-01')];

const shallow = [...original];
shallow[0].push(3);                        // reaches into the original

const deep = structuredClone(original);
deep[0].push(99);                          // does not

const viaJson = JSON.parse(JSON.stringify(original));

const clonedFunction = (() => {
  try { structuredClone([() => 1]); return 'cloned'; } catch (e) { return e.name; }
})();

console.log('the copy is a new array   :', shallow !== original);
console.log('but the inner array is not:', original[0], '<- the 3 arrived here too');
console.log('structuredClone           :', deep[0], ' original still', original[0]);
console.log('--- what JSON does on the way through ---');
console.log('the Date became           :', typeof viaJson[2], JSON.stringify(viaJson[2]).slice(0, 12) + '...');
console.log('structuredClone kept it   :', deep[2] instanceof Date);
console.log('undefined inside an object:', JSON.parse(JSON.stringify([{ a: undefined }])));
console.log('cloning a function        :', clonedFunction);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18const sparse = [1, , 3];                   // the middle slot does not exist
const deleted = [1, 2, 3];
delete deleted[1];                         // the same thing, made deliberately
const explicit = [1, undefined, 3];        // NOT sparse: three real values

let visits = 0;
sparse.forEach(() => { visits++; });

console.log('length     :', sparse.length, '<- the hole is counted');
console.log('1 in sparse:', 1 in sparse, ' 1 in explicit:', 1 in explicit);
console.log('Object.keys:', Object.keys(sparse), '<- only the real slots');
console.log('forEach visited', visits, 'of 3');
console.log('--- who skips, who fills, who drops ---');
console.log('map        :', [1, , 3].map(() => 9), 'hole kept?', !(1 in [1, , 3].map(() => 9)));
console.log('filter     :', [1, , 3].filter(() => true), '<- dropped');
console.log('Array.from :', Array.from([1, , 3]).map(String), '<- filled in');
console.log('spread     :', [...[1, , 3]].map(String), '<- filled in');
console.log('reduce     :', [1, , 3].reduce((a, b) => a + b), '<- skipped, so 4');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25function encode(xs) {
  const runs = [];
  for (const v of xs) {
    const current = runs.at(-1);
    if (current !== undefined && current[0] === v) current[1] += 1;
    else runs.push([v, 1]);
  }
  return runs;
}

const decode = (runs) => runs.flatMap(([v, n]) => Array(n).fill(v));

// The compact text form, which is what "RLE" usually means.
const encodeText = (text) => encode([...text]).map(([c, n]) => c + n).join('');

const letters = ['a', 'a', 'b', 'c', 'c', 'c'];

console.log('encode      :', encode(letters));
console.log('decode      :', decode(encode(letters)));
console.log('round trip  :', same(decode(encode(letters)), letters));
console.log('not adjacent:', encode(['a', 'b', 'a']), '<- three runs, not two');
console.log('text form   :', encodeText('aaabbc'));
console.log('--- === is the comparison, for better and worse ---');
console.log("[1, '1']    :", encode([1, '1']), '<- two runs');
console.log('[NaN, NaN]  :', encode([NaN, NaN]).length, 'runs, because NaN !== NaN');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29function groupConsecutive(xs, together = (a, b) => a === b) {
  return xs.reduce((groups, v) => {
    const current = groups.at(-1);
    if (current !== undefined && together(current.at(-1), v)) current.push(v);
    else groups.push([v]);
    return groups;
  }, []);
}

const adjacent = (a, b) => b === a + 1;

// Page ranges: sort, group the consecutive runs, then print each run.
const compressRanges = (nums) =>
  groupConsecutive([...new Set(nums)].sort((a, b) => a - b), adjacent)
    .map((run) => (run.length === 1 ? String(run[0]) : `${run[0]}-${run.at(-1)}`))
    .join(',');

const shifts = [
  { name: 'Ada', dept: 'ops' },
  { name: 'Bola', dept: 'ops' },
  { name: 'Chi', dept: 'eng' },
];

console.log('equal neighbours :', groupConsecutive([1, 1, 2, 2, 2, 3]));
console.log('a later repeat   :', groupConsecutive([1, 2, 1]), '<- three groups');
console.log('consecutive ints :', groupConsecutive([1, 2, 3, 7, 8, 10], adjacent));
console.log('compressed       :', compressRanges([3, 1, 2, 8, 7, 10]));
console.log('unsorted, ungrouped:', groupConsecutive([3, 1, 2], adjacent), '<- sort first');
console.log('by a field       :', groupConsecutive(shifts, (a, b) => a.dept === b.dept).map((g) => g.length));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function longestIncreasingRun(xs) {
  let best = [];
  let current = [];
  for (const v of xs) {
    if (current.length === 0 || v > current.at(-1)) current.push(v);
    else current = [v];                       // the run ends; start again here
    if (current.length > best.length) best = [...current];   // a copy, on purpose
  }
  return best;
}

const readings = [1, 2, 1, 3, 5, 2, 4, 6, 7];
const found = longestIncreasingRun(readings);

console.log('input   :', readings);
console.log('runs    : [1,2] [1,3,5] [2,4,6,7]');
console.log('longest :', found, 'length', found.length);
console.log('a tie   :', longestIncreasingRun([1, 2, 0, 3]), '<- both are 2 long, the first wins');
console.log('strictly increasing, so equals break it:', longestIncreasingRun([1, 1, 2]));
console.log('decreasing:', longestIncreasingRun([3, 2, 1]));
console.log('empty     :', longestIncreasingRun([]));
console.log('contiguous in the input?', readings.join(',').includes(found.join(',')));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30function partition(xs, keep) {
  const yes = [];
  const no = [];
  xs.forEach((x, i) => (keep(x, i) ? yes : no).push(x));
  return [yes, no];
}

// More than two outcomes needs a key rather than a boolean.
const partitionBy = (xs, keyOf) => xs.reduce((m, x) => {
  const key = keyOf(x);
  return m.set(key, [...(m.get(key) ?? []), x]);
}, new Map());

let onePass = 0;
partition([1, 2, 3, 4], (n) => { onePass++; return n % 2 === 1; });

let twoPasses = 0;
const odd = (n) => { twoPasses++; return n % 2 === 1; };
[1, 2, 3, 4].filter(odd);
[1, 2, 3, 4].filter((n) => !odd(n));

const [pass, fail] = partition([1, 2, 3, 4], (n) => n % 2 === 1);
const sizes = [...partitionBy([1, 2, 3, 4, 5, 6], (n) => n % 3)].map(([k, g]) => [k, g.length]);

console.log('odd / even   :', partition([1, 2, 3, 4], (n) => n % 2 === 1));
console.log('destructured :', pass, fail);
console.log('by index     :', partition(['a', 'b', 'c'], (_, i) => i % 2 === 0));
console.log('nothing passes:', partition([1, 2], () => false));
console.log('predicate calls: partition', onePass, ' two filters', twoPasses);
console.log('three ways by n % 3:', sizes);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20function permutations(xs) {
  if (xs.length <= 1) return [xs.slice()];
  return xs.flatMap((v, i) => {
    const rest = [...xs.slice(0, i), ...xs.slice(i + 1)];   // everything except v
    return permutations(rest).map((tail) => [v, ...tail]);
  });
}

const factorial = (n) => (n <= 1 ? 1 : n * factorial(n - 1));

const three = permutations([1, 2, 3]);
const four = permutations([1, 2, 3, 4]);

console.log('permutations of [1,2,3]:');
for (const p of three) console.log('  ', p.join(''));
console.log('count for 4 values:', four.length, ' 4! =', factorial(4));
console.log('all distinct      :', new Set(four.map((p) => p.join(','))).size);
console.log('empty input       :', permutations([]), '<- one ordering, the empty one');
console.log('duplicates        :', permutations([1, 1]), '<- two orderings that look the same');
console.log('10! =', factorial(10), ' 12! =', factorial(12), '<- why this does not scale');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;
  let comparisons = 0;

  while (low <= high) {                       // <= , or a one-element range is skipped
    const mid = Math.floor((low + high) / 2);
    comparisons++;
    if (sorted[mid] === target) return { index: mid, comparisons };
    if (sorted[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return { index: -1, comparisons };
}

const evens = Array.from({ length: 1024 }, (_, i) => i * 2);
const unsorted = [5, 1, 9];

console.log('find 500      :', binarySearch(evens, 500));
console.log('find 501      :', binarySearch(evens, 501), '<- not present');
console.log('find the last :', binarySearch(evens, 2046));
console.log('a linear scan would have taken', evens.indexOf(2046) + 1, 'reads');
console.log('2 ** 11 =', 2 ** 11, 'which is why 11 comparisons cover 1024 values');
console.log('--- unsorted input ---');
console.log('binarySearch([5,1,9], 5):', binarySearch(unsorted, 5).index, '<- wrong, and it does not complain');
console.log('indexOf says             :', unsorted.indexOf(5));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33function merge(a, b, key = (x) => x) {
  const out = [];
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) {
    out.push(key(a[i]) <= key(b[j]) ? a[i++] : b[j++]);      // <= : ties take from a
  }
  return [...out, ...a.slice(i), ...b.slice(j)];             // whatever is left is sorted
}

function mergeSort(xs) {
  if (xs.length <= 1) return xs.slice();
  const mid = Math.floor(xs.length / 2);
  return merge(mergeSort(xs.slice(0, mid)), mergeSort(xs.slice(mid)));
}

const left = [1, 4, 7];
const right = [2, 3, 9];

const tiedLeft = [{ v: 1, side: 'L' }];
const tiedRight = [{ v: 1, side: 'R' }];
const tied = merge(tiedLeft, tiedRight, (x) => x.v).map((x) => x.side);

const merged = merge(left, right);

console.log('left    :', left);
console.log('right   :', right);
console.log('merged  :', merged);
console.log('sorted? :', merged.every((v, i) => i === 0 || merged[i - 1] <= v));
console.log('ties    :', tied, '<- the left-hand element first');
console.log('one empty:', merge([], [1, 2]));
console.log('mergeSort:', mergeSort([5, 3, 8, 1, 9, 2]));
console.log('inputs afterwards:', left, right);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33// The obvious version: correct, and it re-reads every window.
const windowMaxNaive = (xs, k) =>
  Array.from({ length: Math.max(0, xs.length - k + 1) }, (_, i) => Math.max(...xs.slice(i, i + k)));

// One pass. `window` holds indexes whose values decrease from front to back.
function windowMax(xs, k) {
  if (!Number.isInteger(k) || k < 1) throw new RangeError('k must be a positive integer');
  const out = [];
  const window = [];
  let removals = 0;

  for (let i = 0; i < xs.length; i++) {
    while (window.length > 0 && xs[window.at(-1)] <= xs[i]) { window.pop(); removals++; }
    window.push(i);
    if (window[0] <= i - k) { window.shift(); removals++; }   // the front fell out of range
    if (i >= k - 1) out.push(xs[window[0]]);
  }
  return { values: out, removals };
}

const xs = [1, 3, -1, -3, 5, 3, 6, 7];

const refused = (() => {
  try { windowMax(xs, 0); return 'no error'; } catch (e) { return e.constructor.name; }
})();

console.log('input      :', xs);
console.log('windows of 3, one per line:');
for (let i = 0; i + 3 <= xs.length; i++) console.log('  ', xs.slice(i, i + 3), '->', Math.max(...xs.slice(i, i + 3)));
console.log('windowMax  :', windowMax(xs, 3).values);
console.log('naive      :', windowMaxNaive(xs, 3));
console.log('removals   :', windowMax(xs, 3).removals, 'for', xs.length, 'elements');
console.log('k of 0     :', refused);