Algorithms for Functional Programming

des.ts

type PermutationTable = Array<number>
type SBox = Array<Array<number>>
type CanCastToBigInt = number | bigint | string | BigNumber

const CHAR_BITS = 16
const DES_BITS_LIMIT = 64

const BITS_ROTATION_TABLE: Array<number> = [
  1, 1, 2, 2, 2, 2, 2, 2,
  1, 2, 2, 2, 2, 2, 2, 1,
]

const PERMUTED_CHOICE_1_TABLE: PermutationTable = [
  57, 49, 41, 33, 25, 17,  9,
   1, 58, 50, 42, 34, 26, 18,
  10,  2, 59, 51, 43, 35, 27,
  19, 11,  3, 60, 52, 44, 36,
  63, 55, 47, 39, 31, 23, 15,
   7, 62, 54, 46, 38, 30, 22,
  14,  6, 61, 53, 45, 37, 29,
  21, 13,  5, 28, 20, 12,  4,
]

const PERMUTED_CHOICE_2_TABLE: PermutationTable = [
  14, 17, 11, 24,  1,  5,
   3, 28, 15,  6, 21, 10,
  23, 19, 12,  4, 26,  8,
  16,  7, 27, 20, 13,  2,
  41, 52, 31, 37, 47, 55,
  30, 40, 51, 45, 33, 48,
  44, 49, 39, 56, 34, 53,
  46, 42, 50, 36, 29, 32,
]

const INITIAL_PERMUTATION_TABLE: PermutationTable = [
  58, 50, 42, 34, 26, 18, 10,  2,
  60, 52, 44, 36, 28, 20, 12,  4,
  62, 54, 46, 38, 30, 22, 14,  6,
  64, 56, 48, 40, 32, 24, 16,  8,
  57, 49, 41, 33, 25, 17,  9,  1,
  59, 51, 43, 35, 27, 19, 11,  3,
  61, 53, 45, 37, 29, 21, 13,  5,
  63, 55, 47, 39, 31, 23, 15,  7,
]

const FINAL_PERMUTATION_TABLE: PermutationTable = [
  40,  8, 48, 16, 56, 24, 64, 32,
  39,  7, 47, 15, 55, 23, 63, 31,
  38,  6, 46, 14, 54, 22, 62, 30,
  37,  5, 45, 13, 53, 21, 61, 29,
  36,  4, 44, 12, 52, 20, 60, 28,
  35,  3, 43, 11, 51, 19, 59, 27,
  34,  2, 42, 10, 50, 18, 58, 26,
  33,  1, 41,  9, 49, 17, 57, 25,
]

const EXPANSION_TABLE: PermutationTable = [
  32,  1,  2,  3,  4,  5,
   4,  5,  6,  7,  8,  9,
   8,  9, 10, 11, 12, 13,
  12, 13, 14, 15, 16, 17,
  16, 17, 18, 19, 20, 21,
  20, 21, 22, 23, 24, 25,
  24, 25, 26, 27, 28, 29,
  28, 29, 30, 31, 32,  1,
]

const S_BOXES: Array<SBox> = [
  [
    [14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7],
    [ 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8],
    [ 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0],
    [15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13],
  ],
  [
    [15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10],
    [ 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5],
    [ 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15],
    [13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9],
  ],
  [
    [10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8],
    [13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1],
    [13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7],
    [ 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12],
  ],
  [
    [ 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15],
    [13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9],
    [10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4],
    [ 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14],
  ],
  [
    [ 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9],
    [14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6],
    [ 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14],
    [11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3],
  ],
  [
    [12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11],
    [10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8],
    [ 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6],
    [ 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13],
  ],
  [
    [ 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1],
    [13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6],
    [ 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2],
    [ 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12],
  ],
  [
    [13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7],
    [ 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2],
    [ 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8],
    [ 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11],
  ]
]

const PERMUTATION_TABLE: PermutationTable = [
  16,  7, 20, 21, 29, 12, 28, 17,
   1, 15, 23, 26,  5, 18, 31, 10,
   2,  8, 24, 14, 32, 27,  3,  9,
  19, 13, 30,  6, 22, 11,  4, 25,
]

class BigNumber {
  value: bigint

  constructor(value: CanCastToBigInt) {
    this.value = this.normalizeValue(value)
  }

  add(right: CanCastToBigInt): BigNumber {
    return new BigNumber(this.value + this.normalizeValue(right))
  }

  sub(right: CanCastToBigInt): BigNumber {
    return new BigNumber(this.value - this.normalizeValue(right))
  }

  and(right: CanCastToBigInt): BigNumber {
    return new BigNumber(this.value & this.normalizeValue(right))
  }

  or(right: CanCastToBigInt): BigNumber {
    return new BigNumber(this.value | this.normalizeValue(right))
  }

  xor(right: CanCastToBigInt): BigNumber {
    return new BigNumber(this.value ^ this.normalizeValue(right))
  }

  shiftLeft(right: CanCastToBigInt): BigNumber {
    return new BigNumber(this.value << this.normalizeValue(right))
  }

  shiftRight(right: CanCastToBigInt): BigNumber {
    return new BigNumber(this.value >> this.normalizeValue(right))
  }

  toBigInt(): bigint {
    return this.value
  }

  toString(radix?: number): string {
    return this.value.toString(radix)
  }

  private normalizeValue(value: CanCastToBigInt): bigint {
    if (value instanceof BigNumber) {
      return value.toBigInt()
    }

    if (typeof value === 'bigint') {
      return value
    }

    return BigInt(value)
  }
}

class Code {
  value: BigNumber
  bits: number

  constructor(value: CanCastToBigInt, bits?: number) {
    this.value = new BigNumber(value)
    this.bits = this.normalizeBits(bits)
  }

  slice(start: number, bits?: number): Code {
    if (!bits) {
      bits = this.bits - start + 1
    }

    return new Code(
      this.value.shiftRight(this.bits - start - bits + 1).and(new BigNumber(1).shiftLeft(bits).sub(1)),
      bits
    )
  }

  split(quantity: number = 2): Array<Code> {
    const size = this.bits / quantity
    const groups = []

    for (let i = 0; i < quantity; i++) {
      groups.push(this.slice(size * i + 1, size))
    }

    return groups
  }

  rotateLeft(offset: number): Code {
    return new Code(
      this.value.shiftLeft(offset).and(new BigNumber(1).shiftLeft(this.bits).sub(1)).or(this.slice(1, offset).toBigInt()),
      this.bits
    )
  }

  combine(right: Code): Code {
    return new Code(
      this.value.shiftLeft(right.getBits()).or(right.toBigInt()),
      this.bits + right.getBits()
    )
  }

  xor(right: Code): Code {
    return new Code(
      this.value.xor(right.toBigInt()),
      this.bits
    )
  }

  padEnd(bits: number): Code {
    if (this.bits >= bits) {
      return this
    }

    return this.combine(new Code(0, bits - this.bits))
  }

  permute(table: PermutationTable): Code {
    const permutedBits = table.length
    const permutedValue = table.reduce((permuted: BigNumber, targetBit: number, currentBit: number): BigNumber => {
      return permuted.or(this.slice(targetBit, 1).toBigNumber().shiftLeft(permutedBits - currentBit - 1))
    }, new BigNumber(0))

    return new Code(permutedValue, permutedBits)
  }

  getBits(): number {
    return this.bits
  }

  toBigNumber(): BigNumber {
    return this.value
  }

  toBigInt(): bigint {
    return this.value.toBigInt()
  }

  toNumber(): number {
    return Number(this.toBigInt())
  }

  toString(radix: number = 16): string {
    return this.value.toString(radix).toUpperCase().padStart(this.bits / radix * 2, '0')
  }

  static fromText(text: string): Code {
    return new Code(
      text.split('').reduce((result: BigNumber, char: string): BigNumber => {
        return result.shiftLeft(CHAR_BITS).or(char.charCodeAt(0))
      }, new BigNumber(0)),
      text.length * CHAR_BITS
    )
  }

  toText(): string {
    const char = String.fromCharCode(this.slice(1, CHAR_BITS).toNumber())

    if (this.bits <= CHAR_BITS) {
      return char
    }

    return char + this.slice(CHAR_BITS + 1).toText()
  }

  private normalizeBits(bits: number | null | undefined): number {
    if (bits) {
      return bits
    }

    return this.value.toString(16).length * 4
  }
}

class DES {
  static encrypt(input: Code, key: Code): Code {
    const instance = new DES()

    return instance.des(input, instance.generateSubKeys(key))
  }

  static decrypt(input: Code, key: Code): Code {
    const instance = new DES()

    return instance.des(input, instance.generateSubKeys(key).reverse())
  }

  private des(input: Code, subkeys: Array<Code>): Code {
    const sliced: Code = input.slice(1, DES_BITS_LIMIT).padEnd(DES_BITS_LIMIT)
    const permuted: Code = sliced.permute(INITIAL_PERMUTATION_TABLE)

    let [left, right]: [Code, Code] = permuted.split() as [Code, Code]

    for (const subkey of subkeys) {
      const originalLeft: Code = left

      left = right
      right = this.feistel(right, subkey)
      right = right.xor(originalLeft)
    }

    const crypted = right.combine(left).permute(FINAL_PERMUTATION_TABLE)

    if (input.getBits() <= DES_BITS_LIMIT) {
      return crypted
    }

    return crypted.combine(this.des(input.slice(DES_BITS_LIMIT + 1), subkeys))
  }

  private feistel(code: Code, subkey: Code): Code {
    const expended: Code = code.permute(EXPANSION_TABLE)
    const groups: Array<Code> = expended.xor(subkey).split(8)
    const substituted: BigNumber = groups.reduce((result: BigNumber, group: Code, index: number): BigNumber => {
      const x: number = group.slice(1, 1).combine(group.slice(6, 1)).toNumber()
      const y: number = group.slice(2, 4).toNumber()

      return result.shiftLeft(4).or(S_BOXES[index][x][y])
    }, new BigNumber(0))

    return new Code(substituted, 32).permute(PERMUTATION_TABLE)
  }

  private generateSubKeys(key: Code): Array<Code> {
    const sliced: Code = key.slice(1, DES_BITS_LIMIT).padEnd(DES_BITS_LIMIT)
    const permuted: Code = sliced.permute(PERMUTED_CHOICE_1_TABLE)
    const subkeys: Array<Code> = []

    let [left, right]: [Code, Code] = permuted.split() as [Code, Code]

    for (const offset of BITS_ROTATION_TABLE) {
      left = left.rotateLeft(offset)
      right = right.rotateLeft(offset)
      subkeys.push(left.combine(right).permute(PERMUTED_CHOICE_2_TABLE))
    }

    return subkeys
  }
}

const key = new Code('0x01234567890ABCDEF')

console.log(
  DES.decrypt(
    DES.encrypt(
      Code.fromText('abc中文def中文ghi中文jkl中文mno'),
      key
    ),
    key
  ).toText()
)

graph.js

class Graph {
  nodes = {}
  adjacencyMatrix = {}

  addNode(node) {
    this.nodes[node] = node
    this.adjacencyMatrix[node] = {}
  }

  addEdge(a, b, distance = 1) {
    this.adjacencyMatrix[a][b] = distance
    this.adjacencyMatrix[b][a] = distance
  }

  findAdjacencies(node) {
    const adjacencies = []

    for (const address in this.adjacencyMatrix[node]) {
      if (this.adjacencyMatrix[node][address]) {
        adjacencies.push(this.nodes[address])
      }
    }

    return adjacencies
  }

  buildRoute(predecessor, target) {
    if (!(predecessor[target] instanceof Node)) {
      return [target.value]
    }

    return [...this.buildRoute(predecessor, predecessor[target]), target.value]
  }

  bfs(from, to) {
    const queue = []
    const predecessor = {}

    queue.push(from)
    predecessor[from] = -1

    while (queue.length) {
      const current = queue.shift()

      if (current === to) {
        break
      }

      this.findAdjacencies(current).forEach((adjacency) => {
        if (predecessor[adjacency]) {
          return
        }

        predecessor[adjacency] = current

        queue.push(adjacency)
      })
    }

    return this.buildRoute(predecessor, to)
  }

  dfs(from, to) {
    const predecessor = {}
    const visit = (node) => {
      if (node === to) {
        return
      }

      this.findAdjacencies(node).forEach((adjacency) => {
        if (predecessor[adjacency]) {
          return
        }

        predecessor[adjacency] = node

        visit(adjacency)
      })
    }

    predecessor[from] = -1

    visit(from)

    return this.buildRoute(predecessor, to)
  }

  bellmanFord(from, to) {
    const distance = {}
    const predecessor = {}

    for (const address in this.nodes) {
      distance[address] = Infinity
    }

    distance[from] = 0
    predecessor[from] = -1

    const relax = (node) => {
      let updated = false

      this.findAdjacencies(node).forEach((adjacency) => {
        const testDistance = distance[node] + this.adjacencyMatrix[node][adjacency]

        if (distance[adjacency] <= testDistance) {
          return
        }

        updated = true
        distance[adjacency] = testDistance
        predecessor[adjacency] = node

        relax(adjacency)
      })

      return updated
    }

    while (!relax(from)) {
      //
    }

    return this.buildRoute(predecessor, to)
  }

  dijkstras(from, to) {
    const distance = {}
    const predecessor = {}
    const options = {}

    for (const address in this.nodes) {
      distance[address] = Infinity
    }

    distance[from] = 0
    predecessor[from] = -1
    options[from] = 0

    while (this._isNotEmpty(options)) {
      const node = this.nodes[this._min(options)]

      delete options[node]

      this.findAdjacencies(node).forEach((adjacency) => {
        const testDistance = distance[node] + this.adjacencyMatrix[node][adjacency]

        if (distance[adjacency] <= testDistance) {
          return
        }

        distance[adjacency] = testDistance
        predecessor[adjacency] = node
        options[adjacency] = testDistance
      })
    }

    return this.buildRoute(predecessor, to)
  }

  aStar(from, to) {
    const estimatedDistance = {}
    const distance = {}
    const predecessor = {}
    const options = {}

    for (const address in this.nodes) {
      estimatedDistance[address] = graph.bfs(to, this.nodes[address]).length - 1
      distance[address] = Infinity
    }

    estimatedDistance[from] = 0
    distance[from] = 0
    predecessor[from] = -1
    options[from] = 0

    while (this._isNotEmpty(options)) {
      const node = this.nodes[this._min(options)]

      delete options[node]

      this.findAdjacencies(node).forEach((adjacency) => {
        const testDistance =
          distance[node]
          - estimatedDistance[node]
          + estimatedDistance[adjacency]
          + this.adjacencyMatrix[node][adjacency]

        if (distance[adjacency] <= testDistance) {
          return
        }

        distance[adjacency] = testDistance
        predecessor[adjacency] = node
        options[adjacency] = testDistance
      })
    }

    return this.buildRoute(predecessor, to)
  }

  _min(nodes) {
    let minNodeAddress = Object.keys(nodes)[0]
    let minValue = nodes[minNodeAddress]

    for (const address in nodes) {
      if (nodes[address] < minValue) {
        minNodeAddress = address
        minValue = nodes[address]
      }
    }

    return minNodeAddress
  }

  _isNotEmpty(nodes) {
    return Object.keys(nodes).length
  }
}

class Node {
  value = null
  address = null

  constructor(value) {
    this.value = value
    this.address = this.generateFakeMemoryAddress()
  }

  generateFakeMemoryAddress() {
    return `0x${Math.random().toString(16).slice(2, 14)}`
  }

  toString() {
    return `${this.address}`
  }
}

const graph = new Graph()
const nodeA = new Node('A')
const nodeB = new Node('B')
const nodeC = new Node('C')
const nodeD = new Node('D')
const nodeE = new Node('E')
const nodeF = new Node('F')
const nodeG = new Node('G')

graph.addNode(nodeA)
graph.addNode(nodeB)
graph.addNode(nodeC)
graph.addNode(nodeD)
graph.addNode(nodeE)
graph.addNode(nodeF)
graph.addNode(nodeG)

graph.addEdge(nodeA, nodeB, 9)
graph.addEdge(nodeA, nodeC, 2)
graph.addEdge(nodeB, nodeC, 6)
graph.addEdge(nodeB, nodeD, 3)
graph.addEdge(nodeB, nodeE, 1)
graph.addEdge(nodeC, nodeD, 2)
graph.addEdge(nodeC, nodeF, 9)
graph.addEdge(nodeD, nodeE, 5)
graph.addEdge(nodeD, nodeF, 6)
graph.addEdge(nodeE, nodeF, 3)
graph.addEdge(nodeE, nodeG, 7)
graph.addEdge(nodeF, nodeG, 4)

/*
 *     B - 1 - E
 *    /|\     /|\
 *   9 | 3   5 | 7
 *  /  |  \ /  |  \
 * A   6   D   3   G
 *  \  |  / \  |  /
 *   2 | 2   6 | 4
 *    \|/     \|/
 *     C - 9 - F
 */

console.log('bfs:', graph.bfs(nodeA, nodeG).join(' -> '))
console.log('dfs:', graph.dfs(nodeA, nodeG).join(' -> '))
console.log('bellman ford:', graph.bellmanFord(nodeA, nodeG).join(' -> '))
console.log('dijkstras:', graph.dijkstras(nodeA, nodeG).join(' -> '))
console.log('a star:', graph.aStar(nodeA, nodeG).join(' -> '))

search.js

const binarySearch = (needle, haystack, basis = 0) => {
  if (haystack.length === 0) return -1
  const center = Math.ceil((haystack.length - 1) / 2)
  if (haystack[center] === needle) return basis + center
  if (haystack[center] > needle) return binarySearch(needle, haystack.slice(0, center), basis)
  return binarySearch(needle, haystack.slice(center + 1), basis + center + 1)
}

console.log(binarySearch(18, [1, 3, 5, 7, 9, 12, 14, 16, 18, 20]))

sort.js

const last = (list) => list.slice(-1)[0]

const bubble = ([first, second, ...rest]) => {
  if (second === undefined) return [first]
  if (first > second) return [second, ...bubble([first, ...rest])]
  return [first, ...bubble([second, ...rest])]
}

const bubbleSort = (list) => {
  if (list.length === 0) return []
  if (list.length === 1) return list
  const sorted = bubble(list)
  return [...bubbleSort(sorted.slice(0, -1)), last(sorted)]
}

console.log('Bubble Sort:', bubbleSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0]))

const select = ([first, second, ...rest]) => {
  if (second === undefined) return [first]
  if (first > second) return [first, ...select([second, ...rest])]
  return [second, ...select([first, ...rest])]
}

const selectionSort = (list) => {
  if (list.length < 2) return list
  const sorted = select(list)
  return [last(sorted), ...selectionSort(sorted.slice(0, -1))]
}

console.log('Selection Sort:', selectionSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0]))

const insert = (target, [first, second, ...rest]) => {
  if (first === undefined) return [target]
  if (second === undefined) return first <= target ? [first, target] : [target, first]
  if (first <= target && target <= second) return [first, target, second, ...rest]
  return [first, ...insert(target, [second, ...rest])]
}

const insertionSort = ([first, ...rest]) => {
  if (rest.length === 0) return [first]
  return insert(first, insertionSort(rest))
}

console.log('Insertion Sort:', insertionSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0]))

const split = (list) => {
  const center = Math.ceil(list.length / 2)
  return [list.slice(0, center), list.slice(center)]
}

const merge = (left, right) => {
  if (left.length === 0) return right
  if (right.length === 0) return left
  if (left[0] < right[0]) return [left[0], ...merge(left.slice(1), right)]
  return [right[0], ...merge(left, right.slice(1))]
}

const mergeSort = (list) => {
  if (list.length < 2) return list
  let [left, right] = split(list)
  return merge(mergeSort(left), mergeSort(right))
}

console.log('Merge Sort:', mergeSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0]))

const swap = (list, a, b) => {
  [list[a], list[b]] = [list[b], list[a]]
}

const heapify = (list, target = 0) => {
  const left = 2 * target + 1
  const right = left + 1

  if (list[left] !== undefined) heapify(list, left)
  if (list[right] !== undefined) heapify(list, right)

  if (list[right] === undefined && list[target] > list[left]) {
    swap(list, target, left)
    return list
  }

  if (list[target] > list[right] && list[right] > list[left]) {
    swap(list, target, left)
    heapify(list, left)
    return list
  }

  if (list[target] > list[left] && list[left] > list[right]) {
    swap(list, target, right)
    heapify(list, right)
    return list
  }

  return list
}

const heapSort = (list) => {
  if (list.length === 0) return []
  const [first, ...rest] = heapify(list)
  return [first, ...heapSort(rest)]
}

console.log('Heap Sort:', heapSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0]))

const filter = ([first, ...rest], condition) => {
  if (first === undefined) return []
  if (condition(first)) return [first, ...filter(rest, condition)]
  return filter(rest, condition)
}

const quickSort = ([first, ...rest]) => {
  if (first === undefined) return []
  return [
    ...quickSort(filter(rest, n => n < first)),
    first,
    ...quickSort(filter(rest, n => n >= first))
  ]
}

console.log('Quick Sort:', quickSort([5, 4, 3, 2, 1, 6, 7, 8, 9, 0]))

const prepareBuckets = () => {
  return [[], [], [], [], [], [], [], [], [], []]
}

const putToBuckets = ([first, ...rest], digit, buckets) => {
  if (first === undefined) return buckets
  const radix = Math.floor(first / 10 ** (digit - 1)) % 10
  return putToBuckets(rest, digit, [
    ...buckets.slice(0, radix),
    [...buckets[radix], first],
    ...buckets.slice(radix + 1),
  ])
}

const sortInbuckets = ([first, ...rest], digit) => {
  if (first === undefined) return []
  if (first.length === 0) return sortInbuckets(rest, digit)
  return [bucketSort(first, digit - 1), ...sortInbuckets(rest, digit)]
}

const flatten = ([first, ...rest]) => {
  if (first === undefined) return []
  return [...first, ...flatten(rest)]
}

const bucketSort = (list, digit) => {
  if (digit === 0) return list
  if (digit === undefined) digit = Math.ceil(Math.log10(Math.max(...list)))
  return flatten(sortInbuckets(putToBuckets(list, digit, prepareBuckets()), digit))
}

console.log('Bucket Sort:', bucketSort([15, 34, 33, 42, 41, 46, 27, 28, 9, 0]))