sushi.js

function getMaxEatenDiscountCount_foreach(N, D, K) {
    let eaten = new Set();
    let eatSum = 0;
    let eatCounter = 0;
    D.forEach((dish) => {
        if (!eaten.has(dish)) {
            eatSum++;
            eaten.add(dish);
            eatCounter++;
        }
        if (eatCounter > K) {
            eaten.delete(eaten.values().next().value);
            eatCounter--;
        }
    });
    return eatSum;
}

function getMaxEatenDiscountCount_forloop(N, D, K) {
    let eaten = new Set();
    let eatSum = 0;
    let eatCounter = 0;
    for (dish in D) {
        if (!eaten.has(dish)) {
            eatSum++;
            eaten.add(dish);
            eatCounter++;
        }
        if (eatCounter > K) {
            eaten.delete(eaten.values().next().value);
            eatCounter--;
        }
    };
    return eatSum;
}

function getMaxEatenDiscountCount_arraylookup(N, D, K) {
    let MaxD = Math.max.apply(null, D)
    let eaten = new Array(MaxD + 1)
    let index = []
    let eatCounter = 0
    let eatSum = 0
    D.forEach((dish) => {
        if (!eaten[dish]) {
            eatSum++;
            eaten[dish] = true;
            eatCounter++;
            index.push(dish);
        }
        if (eatCounter > K) {
            let oldest_dish = index.shift();
            eaten[oldest_dish] = false;
            eatCounter--;
        }
    });
    return eatSum;
}


function randomInt(N) {
    return Math.floor(Math.random() * N);
}

function randomIntArray(N, size) {
    return Array.from({length:size}, (_,i) => randomInt(N));
}

function test(fn) {
    N = 6; D = [1,2,3,3,2,1]; K = 1;
    console.log("test1: ", fn(N, D, K) == 5)
    N = 6; D = [1,2,3,3,2,1]; K = 2;
    console.log("test2: ", fn(N, D, K) == 4)
    N = 7; D = [1,2,1,2,1,2,1]; K = 2;
    console.log("test3: ", fn(N, D, K) == 2)
}

function check(i, fn1, fn2) {
    let N = 50000;
    let MaxD = 100000;
    let D = randomIntArray(MaxD, N);
    let K = 25000;
    if (fn1(N, D, K) != fn2(N, D, K)) {
        console.log(i, ": found problem: fn1=", fn1(N,D,K), " fn2=", fn2(N,D,K));
    }
}

function ultimate_test() {
    let N = 50000;
    let MaxD = 100000;
    let D = randomIntArray(MaxD, N);
    let K = 25000;

    console.time('getMaxEatenDiscountCount_foreach');
    getMaxEatenDiscountCount_foreach(N, D, K);
    console.timeEnd('getMaxEatenDiscountCount_foreach');

    console.time('getMaxEatenDiscountCount_forloop');
    getMaxEatenDiscountCount_forloop(N, D, K);
    console.timeEnd('getMaxEatenDiscountCount_forloop');

    console.time('getMaxEatenDiscountCount_arraylookup');
    getMaxEatenDiscountCount_arraylookup(N, D, K);
    console.timeEnd('getMaxEatenDiscountCount_arraylookup');
}

// ultimate_test()
for (var i = 0; i < 10; i++) {
    check(i, getMaxEatenDiscountCount_foreach, getMaxEatenDiscountCount_arraylookup)
}