<file_sep>require('./index');

describe('required', () => {
  const arr = [1, 2, 3, 2, 4, 1, 5, 1, 6];
  const fn = (val => val % 3);

  test('default', () => {
    const a = arr.groupBy();
    const b = new Map([
      [1, [1, 1, 1]],
      [2, [2, 2]],
      [3, [3]],
      [4, [4]],
      [5, [5]],
      [6, [6]],
    ]);
    expect(a).toEqual(b);
  });

  test('custom', () => {
    const a = arr.groupBy(fn);
    const b = new Map([
      [1, [1, 4, 1, 1]],
      [2, [2, 2, 5]],
      [0, [3, 6]],
    ]);
    expect(a).toEqual(b);
  });
});

describe('custom', () => {
  const foo = () => {};
  const bar = { a: 42 };
  const arr = [
    1, NaN, 2, 'foo', null, 'bar', 0b1,
    'foo', NaN, undefined, null, 0, '', '',
    foo, bar, bar, foo, undefined, 652,
  ];
  const fn = (val => val % 3);
  const err = 'Not a function';

  test('null', () => {
    expect(() => arr.groupBy(null)).toThrowError(err);
  });

  test('invalid', () => {
    expect(() => arr.groupBy(42)).toThrowError(err);
  });

  test('default', () => {
    const a = arr.groupBy();
    const b = new Map([
      [1, [1, 1]],
      [NaN, [NaN, NaN]],
      [2, [2]],
      ['foo', ['foo', 'foo']],
      [null, [null, null]],
      ['bar', ['bar']],
      [undefined, [undefined, undefined]],
      [0, [0]],
      ['', ['', '']],
      [foo, [foo, foo]],
      [bar, [bar, bar]],
      [652, [652]],
    ]);
    expect(a).toEqual(b);
  });

  test('custom', () => {
    const a = arr.groupBy(fn);
    const b = new Map([
      [1, [1, 1, 652]],
      [NaN, [NaN, 'foo', 'bar', 'foo', NaN, undefined, foo, bar, bar, foo, undefined]],
      [2, [2]],
      [0, [null, null, 0, '', '']],
    ]);
    expect(a).toEqual(b);
  });

  test('immutable', () => {
    const a = arr;
    arr.groupBy(fn);
    expect(arr).toEqual(a);
  });
});
<file_sep>const quaddouble = require('./index');

describe('required', () => {
  test('(45568411115, 11223344) -> true', () => {
    expect(quaddouble(45568411115, 11223344)).toBe(true);
  });

  test('(11112344445, 442253) -> true', () => {
    expect(quaddouble(11112344445, 442253)).toBe(true);
  });

  test('(12222345, 123452) -> false', () => {
    expect(quaddouble(12222345, 123452)).toBe(false);
  });

  test('(12345, 12345) -> false', () => {
    expect(quaddouble(12345, 12345)).toBe(false);
  });
});

describe('custom', () => {
  test('(4556841.1115, 0.11223344) -> false', () => {
    expect(quaddouble(4556841.1115, 0.11223344)).toBe(false);
  });

  test('(121122111222, 0) -> false', () => {
    expect(quaddouble(121122111222, 0)).toBe(false);
  });

  test('(1 / 3, 33) -> true', () => {
    expect(quaddouble(1 / 3, 33)).toBe(true);
  });

  test('(0b100001, 0b1001) -> false', () => {
    expect(quaddouble(0b100001, 0b1001)).toBe(false);
  });
});
<file_sep>import { GameStrategy, playMultipleTimes } from '.'

describe('default', () => {
  test('change', () => {
    const probabilityOnChange = playMultipleTimes(GameStrategy.CHANGE)
    expect(probabilityOnChange).toBeCloseTo(2 / 3)
  })

  test('insist', () => {
    const probabilityOnInsist = playMultipleTimes(GameStrategy.INSIST)
    expect(probabilityOnInsist).toBeCloseTo(1 / 3)
  })
})
<file_sep>class Item<TValue = unknown> {
  // eslint-disable-next-line no-use-before-define
  public next: Item<TValue> | undefined
  public value: TValue

  public constructor(value: TValue) {
    this.next = undefined
    this.value = value
  }
}

export class List<TValue = unknown> {
  private head: Item<TValue> | undefined

  public constructor(size: number, generateValue: () => TValue) {
    let i: number = size
    let item: Item<TValue> | undefined
    let tail: Item<TValue> | undefined
    while (--i >= 0) {
      item = new Item(generateValue())
      if (tail) tail.next = item
      else this.head = item
      tail = item
    }
  }

  public reverse(): this {
    let current: Item<TValue> | undefined = this.head
    let next: Item<TValue> | undefined
    let prev: Item<TValue> | undefined

    while (current) {
      next = current.next
      current.next = prev
      prev = current
      current = next
    }

    this.head = prev
    return this
  }

  public values(): TValue[] {
    const values: TValue[] = []
    let item: Item<TValue> | undefined = this.head
    while (item) {
      values.push(item.value)
      item = item.next
    }
    return values
  }
}
<file_sep>class Heap {
  private static heapify(a: number[]): void {
    let swaps: number = 0

    const parent = (i: number): number => {
      if (i === 0) return 0
      else {
        return i % 2 === 0
          ? (i - 2) / 2 // i = 2p + 2
          : (i - 1) / 2
      } // i = 2p + 1
    }

    const swap = (a: number[], i1: number, i2: number): void => {
      const v = a[i1]
      a[i1] = a[i2]
      a[i2] = v
      swaps++
    }

    const bubble = (a: number[], i: number): void => {
      while (true) {
        const p = parent(i)
        if (a[i] > a[p]) {
          swap(a, i, p)
          i = p
        } else {
          break
        }
      }
    }

    for (let i = 0, l = a.length; i < l; i++) {
      bubble(a, i)
    }

    console.info(Math.round(swaps / a.length))
  }

  private readonly a: number[]

  public constructor(a: number[]) {
    const h: number[] = a.slice()
    Heap.heapify(h)

    this.a = h
  }

  public print(): void {
    let l = 1
    let i = 0
    while (i < this.a.length) {
      console.log(this.a.slice(i, i + l))
      i += l
      l *= 2
    }
  }
}

for (let i = 0; i < 8; i++) {
  const numbers: number[] = new Array(Math.pow(10, i)).fill(0).map((_, i) => i)
  const heap: Heap = new Heap(numbers)
  // heap.print()
}
<file_sep>'use strict';

function look (graph, component, queue) {
  var vertex, i;
  while (queue.length) {
    vertex = graph[queue.shift()];
    vertex.component = component;
    for (i = 0; i < vertex.length; i++) {
      if (!graph[vertex[i]].component) queue.push(vertex[i]);
    }
  }
}

function check (graph) {
  for (var i = 0; i < graph.length; i++) {
    if (!graph[i].component) return i;
  }
  return null;
}

module.exports = function (graph) {
  var start = 0;
  var component = 1;
  do {
    look(graph, component, [start]);
    start = check(graph);
    component++;
  } while (start);
  return graph;
};
<file_sep>'use strict';
var list = require('./list');
var action = require('./' + (process.argv[2] || 'reverse'));
var len = Math.round(process.argv[3]) || 30;

var list1 = list(len);
list1.print();

var list2 = action(list1);
list2.print();
<file_sep>'use strict';

function RandomArray (length) {
  for (var i = 0; i < length; i++) {
    this.push(Math.round(Math.random() * length));
  }
}

RandomArray.prototype = Object.create(Array.prototype);
RandomArray.prototype.constructor = RandomArray;

RandomArray.prototype.copy = function (arr) {
  var i = arr.length;
  while (--i >= 0) this[i] = arr[i];
  return this;
};

RandomArray.prototype.print = function () {
  if (this.length < 40) console.log(this.join(','));
  return this;
};

RandomArray.prototype.swap = function (i, j) {
  var val = this[i];
  this[i] = this[j];
  this[j] = val;
  return this;
};

module.exports = RandomArray;
<file_sep>// https://leetcode.com/problems/add-two-numbers/

describe('', () => {
  function foo(l1: number[], l2: number[]): number[] {
    let sum: number
    let next: number = 0
    let i: number = 0
    const result: number[] = []
    while (l1[i] !== undefined || l2[i] !== undefined || next) {
      sum = (l1[i] ?? 0) + (l2[i] ?? 0) + (next ?? 0)
      result.push(sum % 10)
      next = sum > 9 ? 1 : 0
      i++
    }
    return result
  }

  test('', () => expect(foo([2, 4, 3], [5, 6, 4])).toEqual([7, 0, 8]))
  test('', () => expect(foo([0], [0])).toEqual([0]))
  test('', () => expect(foo([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9])).toEqual([8, 9, 9, 9, 0, 0, 0, 1]))
})
<file_sep>describe('', () => {
  enum Direction {
    DOWN,
    UP,
  }

  class Heap {
    private static readonly Direction: typeof Direction = Direction
    private static readonly getIndexChildren = (i: number): number[] => [2 * i + 1, 2 * i + 2]
    private static readonly getIndexParent = (i: number): number =>
      (i % 2 === 1 ? i - 1 : i - 2) / 2

    private static heapifyParent(ns: number[], i: number, direction: Direction): void {
      if (i < 0) return

      let ilargest = i
      const [ileft, iright] = Heap.getIndexChildren(i)
      const imax = ns.length

      if (ileft < imax && ns[ileft] > ns[ilargest]) ilargest = ileft
      if (iright < imax && ns[iright] > ns[ilargest]) ilargest = iright

      if (ilargest !== i) {
        const tmp = ns[i]
        ns[i] = ns[ilargest]
        ns[ilargest] = tmp

        Heap.heapifyParent(
          ns,
          direction === Heap.Direction.DOWN ? ilargest : Heap.getIndexParent(i),
          direction,
        )
      }
    }

    private static print(ns: number[]): void {
      for (let i = 0; i < ns.length; i = 2 * i + 1) {
        console.log(ns.slice(i, 2 * i + 1))
      }
    }

    //

    private _ns: number[]

    public constructor(ns: number[] = []) {
      this._ns = []
      for (const n of ns) this.push(n)
    }

    //

    public getNs(): number[] {
      return this._ns.slice()
    }

    public pop(): number | undefined {
      const nfirst = this._ns[0]
      const nlast = this._ns.pop()
      if (this._ns.length !== 0 && nlast !== undefined) this._ns[0] = nlast
      Heap.heapifyParent(this._ns, 0, Heap.Direction.DOWN)
      return nfirst
    }

    public print(): void {
      Heap.print(this._ns)
    }

    public push(n: number): void {
      const length = this._ns.push(n)
      Heap.heapifyParent(this._ns, Heap.getIndexParent(length - 1), Heap.Direction.UP)
    }
  }

  test('', () => {
    const h = new Heap()

    for (let i = 1; i < 12; i++) h.push(i)
    expect(h.getNs()).toEqual([11, 10, 6, 7, 9, 2, 5, 1, 4, 3, 8])

    for (let i = 1; i < 12; i++) h.pop()
    expect(h.getNs()).toEqual([])
  })
})
<file_sep>const round = new RegExp(/\(\)/, 'g');
const square = new RegExp(/\[]/, 'g');
const curly = new RegExp(/\{\}/, 'g');
const empty = '';

module.exports = function validbraces(input) {
  let str = input.slice(0);
  let length = 0;
  while (str.length !== length) {
    length = str.length;
    str = str
      .replace(round, empty)
      .replace(square, empty)
      .replace(curly, empty);
  }
  return !length;
};

/*
 * Примечание:
 *
 * O(n^2) конечно не очень, зато коротко и просто,
 * и в требованиях к решению нет ничего кроме тестов.
 *
 * Быстрее будет стандартный скобочный алгоритм с использованием стека
 * (push на открытии скобки, pop и проверка корректности на закрытии).
 */
<file_sep>import { List } from '.'

describe('default', () => {
  const create = (size: number): List =>
    new List(size, (): number => Math.floor(Math.random() * 10))
  const verify = (list: List): void =>
    expect(
      list
        .values()
        .reverse()
        .join(','),
    ).toEqual(
      list
        .reverse()
        .values()
        .join(','),
    )

  test('size 0', () => verify(create(0)))
  test('size 1', () => verify(create(1)))
  test('size 2', () => verify(create(2)))
  test('size 4', () => verify(create(4)))
  test('size 1024', () => verify(create(1024)))
})
<file_sep>// https://leetcode.com/problems/two-sum

describe('', () => {
  function foo(nums: number[], sum: number): number[] {
    const seen = new Map<number, number>()
    for (let i = 0, l = nums.length; i < l; i++) {
      const n = nums[i]
      const complement = sum - n
      if (seen.has(complement)) return [seen.get(complement)!, i]
      else seen.set(n, i)
    }
    return []
  }

  test('', () => expect(foo([2, 7, 11, 15], 9)).toEqual([0, 1]))
  test('', () => expect(foo([3, 2, 4], 6)).toEqual([1, 2]))
  test('', () => expect(foo([3, 3], 6)).toEqual([0, 1]))
})
<file_sep>'use strict';

function look (graph, component, index) {
  var vertex = graph[index];
  if (!vertex.component) {
    vertex.component = component;
    for (var i = 0; i < vertex.length; i++) {
      look(graph, component, vertex[i]);
    }
  }
}

function check (graph) {
  for (var i = 0; i < graph.length; i++) {
    if (!graph[i].component) return i;
  }
  return null;
}

module.exports = function (graph) {
  var start = 0;
  var component = 1;
  do {
    look(graph, component, start);
    start = check(graph);
    component++;
  } while (start);
  return graph;
};
<file_sep>function checker(num1, num2) {
  const str1 = num1.toString();
  const str2 = num2.toString();
  return (digit) => {
    const re4 = new RegExp(`${digit}{4}`);
    const re2 = new RegExp(`${digit}{2}`);
    return re4.test(str1) && re2.test(str2);
  };
}

module.exports = function quaddouble(num1, num2) {
  const check = checker(num1, num2);
  for (let i = 0; i <= 9; i++) if (check(i)) return true;
  return false;
};

/*
 * Примечание:
 * можно было бы смотреть по одной цифре в цикле только арифметикой,
 * и сохранять найденные значения в хеш таблицу (можно в объект или массив),
 * может быть немножко быстрее бы работало (хотя хз, это надо тестировать),
 * но зато так код гораздо короче и поддерживаемее.
 */
<file_sep>// https://leetcode.com/problems/longest-substring-without-repeating-characters/

describe('', () => {
  function foo(s: string): number {
    let ileft = 0
    let iright = 0
    let char
    let seen = new Set()
    let result = 0
    while (iright < s.length) {
      char = s[iright]
      if (!seen.has(char)) {
        seen.add(char)
        iright++
      } else {
        result = Math.max(result, iright - ileft)

        seen = new Set()
        ileft = iright
        while (ileft - 1 >= 0 && s[ileft - 1] !== char) {
          ileft--
          seen.add(s[ileft])
        }
      }
    }
    return result
  }

  test('', () => expect(foo('abcabcbb')).toEqual(3))
  test('', () => expect(foo('bbbbb')).toEqual(1))
  test('', () => expect(foo('pwwkew')).toEqual(3))
})
<file_sep>'use strict';

function Node (index, next) {
  this.i = index;
  this.next = next || null;
}

Node.prototype.array = function () {
  var node = this;
  var array = [];
  do {
    array.push(node.i);
    node = node.next;
  } while (node);
  return array;
};

Node.prototype.print = function () {
  console.log.apply(console, this.array());
};

module.exports = function (size) {
  var first, curr, last;
  for (var i = 0; i < size; i++) {
    curr = new Node(i);
    if (!first) first = curr;
    if (last) last.next = curr;
    last = curr;
  }
  return first;
};
<file_sep>const validbraces = require('./index');

describe('required', () => {
  test('() -> true', () => {
    expect(validbraces('()')).toEqual(true);
  });

  test('[) -> false', () => {
    expect(validbraces('[)')).toEqual(false);
  });

  test('{}[]() -> true', () => {
    expect(validbraces('{}[]()')).toEqual(true);
  });

  test('([{}]) -> true', () => {
    expect(validbraces('([{}])')).toEqual(true);
  });

  test('())({}}{()][][ -> false', () => {
    expect(validbraces('())({}}{()][][')).toEqual(false);
  });
});

describe('custom', () => {
  test('(() -> false', () => {
    expect(validbraces('(()')).toEqual(false);
  });

  test('([)] -> false', () => {
    expect(validbraces('([)]')).toEqual(false);
  });

  test('{{}[[]}] -> false', () => {
    expect(validbraces('{{}[[]}]')).toEqual(false);
  });

  test('([{}()]({})([])) -> true', () => {
    expect(validbraces('([{}()]({})([]))')).toEqual(true);
  });

  test('((((((()))))))) -> false', () => {
    expect(validbraces('((((((())))))))')).toEqual(false);
  });
});
<file_sep>'use strict';
var MAX = 1000;

function random (max) {
  return Math.round(Math.random() * max);
}

function gcd (min, max) {
  var guess = max % min;
  if (min % guess === 0) return guess;
  else return gcd(guess, min);
}

var a = random(MAX);
var b = random(MAX);
console.log('(' + a + ', ' + b + ') -> ' + gcd(Math.min(a, b), Math.max(a, b)));
<file_sep>'use strict';

function reverse (start) {
  var prev, next, curr = start;
  while (curr) {
    next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

module.exports = reverse;
<file_sep>/*
  Given an integer number N > 0, return a number of ways to get N chicken nuggets from McDonalds, if they only sell packs of 6, 9 and 20, or undefined if it's not possible.
*/

// 18:15 -> + implementation 18:25 -> + debug 18:35 -> + details 18:50 -> + deduplicate 19:00

const numberOfWays = ((): ((n: number) => void) => {
  const availablePackSizes: number[] = [7, 9, 20]
  const alreadyCalculatedAnswers: Array<Array<Array<number | undefined>>> = [[[]]]
  // eslint-disable-next-line max-lines-per-function
  return (n: number): Array<Array<number | undefined>> => {
    const highestAlreadyCalculatedIndex: number = alreadyCalculatedAnswers.length
    if (n < highestAlreadyCalculatedIndex) return alreadyCalculatedAnswers[n]
    else {
      for (let i = highestAlreadyCalculatedIndex; i <= n; i++) {
        availablePackSizes.forEach((packSize: number): void => {
          const indexBeforeAddingTheCurrentPack: number = i - packSize
          if (
            indexBeforeAddingTheCurrentPack >= 0 &&
            // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
            alreadyCalculatedAnswers[indexBeforeAddingTheCurrentPack] !== undefined
          ) {
            if (!alreadyCalculatedAnswers[i]) alreadyCalculatedAnswers[i] = []
            alreadyCalculatedAnswers[i].push(
              ...alreadyCalculatedAnswers[indexBeforeAddingTheCurrentPack].map((answer) => [
                ...answer,
                packSize,
              ]),
            )
          }
        })
      }
      if (alreadyCalculatedAnswers[n]) {
        for (const answer of alreadyCalculatedAnswers[n]) {
          answer.sort((a, b) => (a && b ? a - b : 0))
        }
        alreadyCalculatedAnswers[n] = Array.from(
          new Map(
            alreadyCalculatedAnswers[n].map((answer: Array<number | undefined>) => {
              return [answer.join(','), answer]
            }),
          ).values(),
        )
      }
      return alreadyCalculatedAnswers[n]
    }
  }
})()

for (let n = 0; n <= 50; n++) {
  console.log(n, ' -> ', numberOfWays(n))
}
<file_sep>'use strict';
var RandomArray = require('./RandomArray');
var sort = require('./' + (process.argv[2] || 'quick'));
var len = Math.round(process.argv[3]) || 1000;

console.time('1000 iterations');
for (var i = 0; i < 1000; i++) sort(new RandomArray(len));
console.timeEnd('1000 iterations');
<file_sep>'use strict';

function partition (arr, lo, hi) {
  var i = lo;
  var pi = hi;
  var pv = arr[hi];
  while (i < pi) {
    if (arr[i] < pv) i++;
    else {
      arr.swap(i, pi - 1);
      arr.swap(pi - 1, pi);
      pi--;
    }
  }
  return pi;
}

function sort (arr, lo, hi) {
  if (lo < hi) {
    var p = partition(arr, lo, hi);
    sort(arr, lo, p - 1);
    sort(arr, p + 1, hi);
  }
}

module.exports = function (arr) {
  sort(arr, 0, arr.length - 1);
  return arr;
};
<file_sep>export enum GameStrategy {
  CHANGE,
  INSIST,
}

const defaultNumberOfBoxes: number = 3
const defaultNumberOfPlays: number = 1e5

const getRandomBox = (numberOfBoxes: number): number => {
  return Math.floor(Math.random() * numberOfBoxes)
}

const getRandomBoxExcept = (numberOfBoxes: number, ...forbiddenBoxes: number[]): number => {
  let box: number
  do {
    box = getRandomBox(numberOfBoxes)
  } while (forbiddenBoxes.includes(box))
  return box
}

const playOnce = (gameStrategy: GameStrategy, numberOfBoxes: number): boolean => {
  const prizeBox: number = getRandomBox(numberOfBoxes)
  const firstGuessBox: number = getRandomBox(numberOfBoxes)
  const emptyBox: number = getRandomBoxExcept(numberOfBoxes, prizeBox, firstGuessBox)
  const secondGuessBox: number =
    gameStrategy === GameStrategy.CHANGE
      ? getRandomBoxExcept(numberOfBoxes, firstGuessBox, emptyBox)
      : firstGuessBox
  return secondGuessBox === prizeBox
}

export const playMultipleTimes = (
  gameStrategy: GameStrategy,
  numberOfBoxes: number = defaultNumberOfBoxes,
  numberOfPlays: number = defaultNumberOfPlays,
): number => {
  let score: number = 0
  let i: number = numberOfPlays
  // eslint-disable-next-line @typescript-eslint/no-magic-numbers
  while (--i >= 0) score += playOnce(gameStrategy, numberOfBoxes) ? 1 : 0
  return score / numberOfPlays
}
<file_sep>'use strict';
var DENSITY = 0.15;

function Graph (size) {
  var i, j;
  var edge, edgescount;

  // generate vertices
  for (i = 0; i < size; i++) this.push([]);

  // generate edges
  for (i = 0; i < size; i++) {
    edgescount = Math.floor(Math.random() * size * DENSITY);
    for (edge = 0; edge < edgescount; edge++) {
      j = Math.floor(Math.random() * size);
      if (j !== i) {
        if (this[i].indexOf(j) === -1) this[i].push(j);
        if (this[j].indexOf(i) === -1) this[j].push(i);
      }
    }
  }

  // sort edges
  for (i = 0; i < size; i++)
    this[i].sort(function (a, b) {
      return (a - b);
    });
}

Graph.prototype = Object.create(Array.prototype);
Graph.prototype.constructor = Graph;

Graph.prototype.print = function () {
  console.log(this);
  return this;
};

module.exports = Graph;
<file_sep>describe('', () => {
  function f() {
    return 42
  }

  test('', () => expect(f()).toEqual(42))
})
