Algorithms

Algorithms.md

Algorithms

assignGroups.js

class Entry {
  constructor(name, choices = [], groups) {
    this.name = name;
    this.choices = choices;
    this.assigned = null;
  }
  
  assignToGroup(group) {
    this.assigned = group;
    group.add(this);
  }
}

class Group {
  constructor(name, max) {
    this.name = name;
    this.max = max;
    this.members = new Set();
  }
  
  get remaining() {
    return this.max - this.members.size;
  }
  
  add(member) {
    if(this.members.size < this.max) {
      this.members.add(member);
      return true;
    }
    
    return false;
  }
}
const groups = [
  new Group(1, 2),
  new Group(2, 1),
  new Group(3, 1),
  new Group(4, 1),
  new Group(5, 1),
]
const entries = [
  new Entry("Hans 1", [groups[0],groups[1],groups[2]]),
  new Entry("Hans 2", [groups[0],groups[1],groups[2]]),
  new Entry("Hans 3", [groups[0],groups[1],groups[2]]),
  new Entry("Hans 4", [groups[0],groups[1],groups[3]]),
  new Entry("Hans 5", [groups[0],groups[1],groups[3]]),
  new Entry("Hans 6", [groups[0],groups[4],groups[2]]),
]

const choose = (entries) => {
  let notAssigned = [];
  
  for(const entry of entries) {
    const g = entry.choices.shift();
    
    if(g.remaining > 0) {
      entry.assignToGroup(g)
    } else if(entry.choices.length > 0) {
      notAssigned.push(entry);
    }
  }
  
  if(notAssigned.length > 0) choose(notAssigned); 
}

choose(entries, groups);
console.log(entries, groups);

bogo.js

const randomNumber = (min, max) => ~~(Math.random() * (max - min) + min);

const shuffle = (list) => {
    const i = randomNumber(0, list.length);
    const j = randomNumber(0, list.length);
    [list[i], list[j]] = [list[j], list[i]];

    return list;
}

const isSorted = (array) => {
    for (const i in array) {
        if(i === 0) continue;
        if(array[i-1] > array[i]) {
            return false;
        }
    }

    return true;
}

const bogoSort = (array) =>  {
    let list = [...array];

    while(!isSorted(list)) {
        list = shuffle(list);
    }
    
    return list;
}

const generateRandomArray = (len, min, max) =>
  new Array(len).fill(0).map((_) => ~~(Math.random() * (max - min + 1) + min));

const equal = (a, b) => a.length === b.length && a.every((e, i) => e === b[i]);

const parseHrtimeToSeconds = (hrtime) =>  (hrtime[0] + (hrtime[1] / 1e9));

const speedTest = (func) => {
    const start = process.hrtime();
    func();
    return parseHrtimeToSeconds(process.hrtime(start));
}

for (let i = 1; i < 20; i++) {
    const list = generateRandomArray(i, 0, 1000);
    const time = speedTest(() => {
        const sorted = bogoSort(list);

        if(!isSorted(sorted)) {
            console.log(`Not sorted: `, sorted)
        }
    });

    console.log(i, time)
}

bogoSort.js

function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
}

const bogoSort = (array) =>  {
    let list = [...array];

    const isSorted = (array) => {
        for (const i in array) {
            if(i === 0) continue;
            if(array[i-1] > array[i]) {
                return false;
            }
        }
    }

    while(!isSorted(list)) {
        list = shuffle(list);
    }
    
    return list;
}

const generateRandomArray = (len, min, max) =>
  new Array(len).fill(0).map((_) => ~~(Math.random() * (max - min + 1) + min));

const equal = (a, b) => a.length === b.length && a.every((e, i) => e === b[i]);

const list = generateRandomArray(10, 0, 1000);

const sorted = [...list].sort((a, b) => a - b);
const insertion = bogoSort(list);

console.log("Random array:", list);
console.log(`Sorted:`, sorted);
console.log(`InsersionSort (correct=${equal(sorted, insertion)}):`, insertion);

fizzBuzz.js

console.log([...Array(100).keys()].map((_,i)=>(i+1)%15===0?"fizBuz":(i+1)%5===0?"buz":(i+1)%3===0?"fiz":(i+1)).join("\n"))

hanoi.js

const hanoi = (towers, count, src = 0, dest = 2) => {
  if (!count) count = towers[src].length;

  const middle = [0, 1, 2].find((x) => ![src, dest].includes(x));

  console.log(towers);

  if (count === 1) {
    towers[dest].unshift(towers[src].shift());
    return towers;
  }

  hanoi(towers, count - 1, src, middle);
  hanoi(towers, 1, src, dest);
  hanoi(towers, count - 1, middle, dest);
  return towers;
};

const towers = [[1, 2, 3, 4, 5, 6], [], []];
console.log(hanoi(towers));

h=(t,c,s,m,d)=>console.log(t)||c<2?t[d].push(t[s].pop()):(h(t,c-1,s,d,m),h(t,1,s,m,d),h(t,c-1,m,s,d));
const towers = [[6, 5, 4, 3, 2, 1], [], []];
h(towers);
console.log(towers);

insersionSort.js

const insertionSort = (array) =>  {
    const list = [...array];

    for (let i = 0; i < list.length; i++) {
        let j = i;
        
        while(j > 0 && list[j - 1] > list[j]) {
            [list[j], list[j-1]] = [list[j-1], list[j]];
            j--;
        }
    }
    
    return list;
}

const generateRandomArray = (len, min, max) =>
  new Array(len).fill(0).map((_) => ~~(Math.random() * (max - min + 1) + min));

const equal = (a, b) => a.length === b.length && a.every((e, i) => e === b[i]);

const list = generateRandomArray(100, 0, 1000);

const sorted = [...list].sort((a, b) => a - b);
const insertion = insertionSort(list);

console.log("Random array:", list);
console.log(`Sorted:`, sorted);
console.log(`InsersionSort (correct=${equal(sorted, insertion)}):`, insertion);

radixSort.js

const generateRandomArray = (len, min, max) =>
  new Array(len).fill(0).map((_) => ~~(Math.random() * (max - min + 1) + min));

const radixSortI = (array) => {
  const maxLength = `${Math.max(...array)}`.length;
  let list = array.map((x) => `${x}`.padStart(maxLength, '0'));

  const generateStacks = (count) => new Array(count).fill(0).map((_) => []);

  let stacks = generateStacks(10);

  for (let i = 1; i < maxLength + 1; i++) {
    for (const a of list) {
      const last = a[a.length - i];
      stacks[last].push(a);
    }

    list = stacks.reduce((a, s) => [...a, ...s], []);
    stacks = generateStacks(10);
  }

  return list.map((x) => +x);
};

radixSortII=a=>{
  m=`${Math.max(...a)}`.length;
  l=a.map(x=>`${x}`.padStart(m,'0'));
  g=l=>Array.from({length:l},_=>[]);

  g(m).reduce((s,_,i)=>{
    l.map(n=>{s[n[n.length-i-1]].push(n)});
    l=s.flat();
    return g(10);
  },g(10))
  return l.map(x=>+x);
};

/*
Version history:
radixSortII=a=>(m=`${Math.max(...a)}`.length,l=a.map(x=>`${x}`.padStart(m,'0')),g=l=>Array.from({length:l},_=>[]),g(m).reduce((s,_,i)=>l.map(n=>s[n[n.length-i-1]].push(n)),l=s.reduce((a,s)=>[...a,...s],[]),(g(10)),g(10))),l.map(x=>+x);
radixSortII=a=>(m=`${Math.max(...a)}`.length)&&(l=a.map(x=>`${x}`.padStart(m,'0')))&&(g=l=>Array.from({length:l},_=>[]))&&(g(m).reduce((s,_,i)=>l.map(n=>{s[n[n.length-i-1]].push(n)})&&(l=s.reduce((a,s)=>[...a,...s],[]))&&g(10),g(10)))&&l.map(x=>+x);
radixSortII=a=>(m=`${Math.max(...a)}`.length)&&(l=a.map(x=>`${x}`.padStart(m,'0')))&&(g=l=>Array.from({length:l},_=>[]))&&(g(m).reduce((s,_,i)=>l.map(n=>{s[n[n.length-i-1]].push(n)})&&(l=s.reduce((a,s)=>[...a,...s],[]))&&g(10),g(10)))&&l.map(x=>+x);
radixSortII=a=>(m=`${Math.max(...a)}`.length,l=a.map(x=>`${x}`.padStart(m,0)),g=l=>Array.from({length:l},_=>[]),g(m).reduce((s,_,i)=>l.map(n=>{s[n[n.length-i-1]].push(n)})&&(l=s.reduce((a,s)=>[...a,...s],[]))&&g(10),g(10)))&&l.map(x=>+x);
radixSortII=a=>(m=`${Math.max(...a)}`.length,l=a.map(x=>`${x}`.padStart(m,0)),g=l=>Array.from({length:l},_=>[]),g(m).map((_,i)=>(s=g(10),l.map(n=>s[n[n.length-i-1]].push(n)),l=s.reduce((a,s)=>[...a,...s]))))&&l.map(x=>+x)
radixSortII=a=>(m=Math.max(...a)+"".length,l=a.map(x=>`${x}`.padStart(m,0)),g=l=>Array.from({length:l},_=>[]),g(m).map((_,i)=>(s=g(10),l.map(n=>s[n[n.length-i-1]].push(n)),l=s.reduce((a,s)=>[...a,...s]))))&&l.map(x=>+x)
radixSortII=a=>(m=Math.max(...a)+''.length,l=a.map(x=>`${x}`.padStart(m,0)),g=l=>Array.from({length:l},_=>[]),g(m).map((_,i)=>(s=g(10),l.map(n=>s[n[n.length-i-1]].push(n)),l=s.reduce((a,s)=>[...a,...s]))))&&l.map(x=>+x)
radixSort=a=>(g=l=>Array(l).fill().map(_=>[]),m=`${Math.max(...a)}`.length,l=a.map(x=>Array(m).join(0)+x),g(m).map((_,i)=>(s=g(10),l.map(n=>s[n[n.length-i-1]].push(n)),l=s.flat())))&&l.map(x=>+x)
radixSort=a=>(g=l=>Array(l).fill().map(_=>[]),m=`${Math.max(...a)}`.length,l=a.map(x=>g(m).join(0)+x),g(m).map((_,i)=>(s=g(10),l.map(n=>s[n.at(-i)].push(n)),l=s.flat())))&&l.map(x=>+x) // not supported node < 16.0.0
*/

radixSort=a=>(g=l=>Array(l).fill().map(_=>[]),m=`${Math.max(...a)}`.length,l=a.map(x=>g(m).join(0)+x),g(m).map((_,i)=>(s=g(10),l.map(n=>s[n[n.length-i-1]].push(n)),l=s.flat())))&&l.map(x=>+x)
// -> length: 191 chars

const arr = generateRandomArray(100, 0, 1000);

const sorted = [...arr].sort((a,b)=>a-b);
const radixI =  radixSortI(arr);
const radixII =  radixSortII(arr);
const radix = radixSort(arr);

const equal = (a, b) => a.length === b.length && a.every((e, i) => e === b[i]);

console.log("Random array:", arr);
console.log(`Sorted:`, sorted);
console.log(`RadixI (correct=${equal(sorted, radixI)}):`, radixI);
console.log(`RadixII (correct=${equal(sorted, radixII)}):`, radixII);
console.log(`Radix oneliner (correct=${equal(sorted, radix)}):`, radix);