Liars of the Round Table

logic-01.js

/*
 * There are 6 dwarfs sitting at a round table.
 * Each of them said: "Both of my neighbors are liars."
 * What is the smallest number of liars that can sit at this table?
 * What is the largest number of liars that can sit at this table?
 */

// (12, 6) -> [0, 0, 1, 1, 0, 0]
const intToBits = (i, size) => [...i.toString(2).padStart(size, "0")].map(Number);

const checkBit = (bits, index) => {
    const lastIndex = bits.length - 1;
    const target = bits[index];
    const lNeighbor = index === lastIndex ? bits[0] : bits[index + 1];
    const rNeighbor = index === 0 ? bits[lastIndex] : bits[index - 1];
    return target && !lNeighbor && !rNeighbor ||
        !target && (lNeighbor || rNeighbor);
}

const checkAllBits = (bits) => bits.every((_, index) => checkBit(bits, index));

const getFalseCount = (bits) => bits.filter((bit) => !bit).length;

// Brute force
const getMinMaxCounts = (size) => {
    let min = size, max = 0;
    for (let i = 0; i < 2 ** size; i++) {
        const bits = intToBits(i, size);
        if (checkAllBits(bits)) {
            const count = getFalseCount(bits);
            if (count < min) min = count;
            if (count > max) max = count
        }
    }
    return { min, max };
}

// Inferred
const getMinMaxCounts2 = (size) => {
    const min = Math.floor((size + 1) / 2); // https://oeis.org/A004526
    const max = Math.floor(2 * size / 3);   // https://oeis.org/A004523
    return { min, max };
}

// for (size = 3; size < 26; size++) {
//     console.log({ size, ...getMinMaxCounts(size) });
// }

for (size = 3; size < 26; size++) {
    console.log({ size, ...getMinMaxCounts2(size) });
}

/*
{ size: 3, min: 2, max: 2 }
{ size: 4, min: 2, max: 2 }
{ size: 5, min: 3, max: 3 }
{ size: 6, min: 3, max: 4 }
{ size: 7, min: 4, max: 4 }
{ size: 8, min: 4, max: 5 }
{ size: 9, min: 5, max: 6 }
{ size: 10, min: 5, max: 6 }
{ size: 11, min: 6, max: 7 }
{ size: 12, min: 6, max: 8 }
{ size: 13, min: 7, max: 8 }
{ size: 14, min: 7, max: 9 }
{ size: 15, min: 8, max: 10 }
{ size: 16, min: 8, max: 10 }
{ size: 17, min: 9, max: 11 }
{ size: 18, min: 9, max: 12 }
{ size: 19, min: 10, max: 12 }
{ size: 20, min: 10, max: 13 }
{ size: 21, min: 11, max: 14 }
{ size: 22, min: 11, max: 14 }
{ size: 23, min: 12, max: 15 }
{ size: 24, min: 12, max: 16 }
{ size: 25, min: 13, max: 16 }
*/