week2-bm

bm.ts

declare function require(name:string);
const { performance } = require('perf_hooks');

export class Timer{
    private _start: number;
    public start(){
        this._start = performance.now();
    }

    //returns time in ms
    public stop(){
        let s = performance.now();
        return s - this._start;
    }

}


enum Dir {
    EAST = 0b00,
    NORTH = 0b01,
    SOUTH = 0b10,
    WEST = 0b11
  }
  export class Ralph {

      public static dirReduc = (arr) => {
          return arr
            .map(str => Dir[str]) // 1. convert string to enum
            .reduce((dirs, nextDir) => {
              // first direction, or last direction not complementary
              if (dirs.length == 0 || dirs[dirs.length-1] + nextDir != 0b11)
                dirs.push(nextDir);
              // last direction is complementary, drop cur and prev dir
              else
                dirs.pop();
              return dirs;
            }, []) // 2. drop complementary sequences
            .map(ord => Dir[ord]); // 3. back to string
      }
  }


  type Direction = 'NORTH'|'SOUTH'|'EAST'|'WEST';
  export class Charlie {

      public static dirReduc = (arr: Direction[]) => {
          let newDirs = [];
          for(let i = 0; i < arr.length; i++){
              let current = arr[i];
              let next = arr[i+1];
              if( next &&
                  (current === 'NORTH' && next === 'SOUTH') ||
                  (current === 'SOUTH' && next === 'NORTH') ||
                  (current === 'EAST' && next === 'WEST') ||
                  (current === 'WEST' && next === 'EAST')
              ){
                  i++;
              }else{
                  newDirs.push(current);
              }
          }

          if(newDirs.length > 1 && newDirs.length !== arr.length){
              //check again
              return Charlie.dirReduc(newDirs);
          }
          return newDirs;
      }
  }

  export class Max {
    public static dirReduc = (directions) => {
        for (var i = 0; i < directions.length; i++) {
            if ((i + 1) < directions.length) {
                if ((directions[i] === 'NORTH' && directions[i + 1] === 'SOUTH') ||
                        (directions[i] === 'SOUTH' && directions[i + 1] === 'NORTH')) {
                    // we have a n/s pair, remove it and recursively pass the new array to be further reduced
                    directions.splice(i, 2);
                    return Max.dirReduc(directions);
                    /**
                    * What can't I do this:
                    * return G964.dirReduc(directions.splice(i, 2)); // infinite loop
                    */
                } else if ((directions[i] === 'EAST' && directions[i + 1] === 'WEST') ||
                        (directions[i] === 'WEST' && directions[i + 1] === 'EAST')) {
                    // we have a e/w pair, remove it and recursively pass the new array to be further reduced
                    directions.splice(i, 2);
                    return Max.dirReduc(directions);
                }
            }
        }

        return directions;
    }
}

export class Jay {
    public static dirReduc = (arr) => {
      let solution = [];
      while(solution.length !== arr.length){
        for (let i = 0; i <= arr.length; i++) {
          if (
            arr[i] === 'NORTH' && arr[i + 1] == 'SOUTH' ||
            arr[i] === 'SOUTH' && arr[i + 1] == 'NORTH' ||
            arr[i] === 'EAST' && arr[i + 1] == 'WEST' ||
            arr[i] === 'WEST' && arr[i + 1] == 'EAST'
          ) {
            i++;
          } else {
            if (arr[i]) {
                solution.push(arr[i]);
            }
          }
        }
        if (arr.length !== solution.length) {
          arr = solution;
          solution = [];
        }
      }
      return solution;
    }
  }


  export class David {

    public static dirReduc = (dir: string[]): string[] => {
      enum compass {
          north = 'NORTH',
          south = 'SOUTH',
          east = 'EAST',
          west = 'WEST'
      }
      enum anitCompass {
          north = compass.south,
          south = compass.north,
          east = compass.west,
          west = compass.east
      }
      const reducer = (): boolean =>{
          let foundPair = false;
          for(let i = 1; i < dir.length; i ++){
              if(compass[dir[i-1].toLowerCase()] === anitCompass[dir[i].toLowerCase()]){
                  foundPair = true;
                  //remove both from array, but keep their spacing so things dont get wackey
                  dir[i-1] = '';
                  dir[i] = ''
              }
          }
          dir = dir.filter((d) => {
              return d != ""
          });
          return foundPair;
      }
      while (reducer()){}
      return dir
    }
}


export class Tony {

    public static dirReduc = (arr) => {
        // [ 'NORTH', 'WEST', 'SOUTH', 'EAST' ] !=> [] ...

        return arr.reduce((a, d) => {
            const l = a[a.length - 1];

            if ((l === 'NORTH' && d === 'SOUTH') || (l === 'SOUTH' && d === 'NORTH') || (l === 'WEST' && d === 'EAST') || (l === 'EAST' && d === 'WEST')) {
                a.pop();
            }  else {
                a.push(d);
            }

            return a;
        }, []);
    }
}

let timer = new Timer();

let functions = {
    "ralph": Ralph.dirReduc,
    "jay": Jay.dirReduc,
    "charlie": Charlie.dirReduc,
    "max": Max.dirReduc,
    "tony": Tony.dirReduc,
    'david': David.dirReduc
}



let dirs = ['NORTH', 'SOUTH', 'EAST', 'WEST'];
let testSizes = [10, 100, 1000, 10000, 100000, 1000000];
testSizes.forEach(n => {
    let dirArry = [];
    for(let i = 0; i < n; i++){
        let dir = dirs[Math.floor(Math.random()*dirs.length)];
        dirArry.push(dir);
    }
    console.log(`=== Test Size: ${n}`);

    let results: {dev: string, time: number}[] = [];

    let devs =  Object.keys(functions);
    shuffleArray(devs); //randomize to reduce cacheing advantages

    devs.forEach(dev => {
        try{
            console.log(`running ${dev}`)
            let clonedArr = [...dirArry];
            functions[dev](clonedArr)//warmup

            timer.start();
            functions[dev](clonedArr)
            let time = timer.stop();
            results.push({
                dev,
                time
            });
        }catch(err){
            console.log(err)
        }
    });

    results.sort((a, b) => a.time - b.time);
    results.forEach((r,i) => {
        console.log(`${i+1}: ${r.dev} - ${r.time}`)
    })

});

function shuffleArray(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]]; // eslint-disable-line no-param-reassign
    }
}