crates-alias-algo.ts

import { task } from "hardhat/config";
import fs from "fs";
import { range, reduce } from "lodash";

const sumWeights = () => {
  const reducer = (p, c, i) => {
    if (c[0] <= 0)
      throw {
        name: "WeightError",
        message: `Invalid weight ${c[0]} at index ${i}. Weight cannot be negative or zero.`,
      };
    return p + c[0];
  };
  return (a) => Array.prototype.reduce.call(a, reducer, 0);
};

const walker = (weightMap) => {
  const n = weightMap.length;
  const sum = sumWeights()(weightMap);
  const weights = weightMap.map((x) => (x[0] * n) / sum);

  const shorts = [];
  const longs = [];
  for (let i = 0, len = weights.length; i < len; ++i) {
    const p = weights[i];
    if (p < 1) {
      shorts.push(i);
    } else if (p > 1) {
      longs.push(i);
    }
  }

  const inx = Array.from(Array(n)).map((_) => 0);

  while (shorts.length && longs.length) {
    const j = shorts.pop();
    const k = longs[longs.length - 1];
    inx[j] = k;
    weights[k] -= 1 - weights[j];
    if (weights[k] < 1) {
      shorts.push(k);
      longs.pop();
    }
  }

  return (powBasis: number) => {
    return {
      run: (seed: any, shr: number) => {
        const traitSeed = seed.shr(shr).mask(16) as any;
        const trait = traitSeed.mod(weights.length);
        const sample = traitSeed.shr(8);
        const weightValue = Math.floor(weights[trait] * Math.pow(2, powBasis));
        const k = sample.lt(weightValue) ? trait : inx[trait];
        return weightMap[k][1];
      },
      probabilities: weights.map((v) => Math.floor(v * Math.pow(2, powBasis))),
      alias: inx,
    };
  };
};

const crate1 = {
  "300": {
    p: 250,
    v: "300",
  },
  "22": {
    p: 10,
    v: "22",
  },
  "301": {
    p: 25,
    v: "301",
  },
  "302": {
    p: 35,
    v: "302",
  },
  "303": {
    p: 40,
    v: "303",
  },
  "304": {
    p: 45,
    v: "304",
  },
  "305": {
    p: 50,
    v: "305",
  },
  "306": {
    p: 100,
    v: "306",
  },
  "307": {
    p: 120,
    v: "307",
  },
  "308": {
    p: 130,
    v: "308",
  },
  "309": {
    p: 140,
    v: "309",
  },
  "310": {
    p: 150,
    v: "310",
  },
  "311": {
    p: 160,
    v: "311",
  },
  "312": {
    p: 200,
    v: "312",
  },
  "313": {
    p: 200,
    v: "313",
  },
  "314": {
    p: 200,
    v: "314",
  },
  "315": {
    p: 200,
    v: "315",
  },
  "316": {
    p: 200,
    v: "316",
  },
  "317": {
    p: 200,
    v: "317",
  },
  "318": {
    p: 200,
    v: "318",
  },
  "319": {
    p: 200,
    v: "319",
  },
  "320": {
    p: 200,
    v: "320",
  },
  "321": {
    p: 200,
    v: "321",
  },
  "322": {
    p: 200,
    v: "322",
  },
  "323": {
    p: 200,
    v: "323",
  },
  "324": {
    p: 200,
    v: "324",
  },
  "325": {
    p: 200,
    v: "325",
  },
};

task(
  "generate-bb-crate-alias",
  "Generates bb crate alias method values"
).setAction(async (taskArgs, hre) => {
  const crateConfigs = [];

  const crates = [
    {
      label: "Base Crate",
      data: crate1,
    },
  ];

  for (let i = 0; i < crates.length; i++) {
    const { label, data } = crates[i];

    const values = reduce(
      data,
      (acc, value, key) => {
        acc.push([value.p, key]);
        return acc;
      },
      []
    );

    const table = walker(values);

    const { run, probabilities, alias } = table(8);

    const selected = range(0, 1501).map((_) =>
      run(
        hre.ethers.BigNumber.from(hre.ethers.utils.randomBytes(32)),
        16 * (i + 1)
      )
    );

    const f = selected.reduce((acc, item) => {
      const { v: traitLabel } = crates[i].data[String(item)];
      if (!acc[traitLabel]) {
        acc[traitLabel] = 1;
      } else {
        acc[traitLabel] += 1;
      }
      return acc;
    }, {});

    crateConfigs.push({
      index: i,
      group: label,
      freqs: f,
      percents: reduce(
        f,
        (acc, value, key) => {
          acc[key] = value / selected.length;
          return acc;
        },
        {}
      ),
      probabilities,
      alias,
    });
  }

});