Password Strength – "at least one"

at_least_one.js

/** Convenient utilities in functional form */
const reduce = Function.prototype.call.bind(Array.prototype.reduce);
const filter = Function.prototype.call.bind(Array.prototype.filter);
const pow = Math.pow;
const log2 = Math.log2;
const size = (set) => set.size;

/** Iterable conversions */
const toSet = (iterable) => new Set(iterable);
const toArray = (iterable) => [...iterable];
const toString = (iterable) => toArray(iterable).join("");
const toSetOfSets = (iterable) => toSet([...(iterable || [])].map(toSet))

/** Set operations */
const emptySet = () => toSet([]);
const union = (a, b) => toSet([...a, ...b]);
const isSubsetOf = (subset, superset) => [...subset].every((e) => superset.has(e));
const areEqualSets = (a, b) => size(a) === size(b) && isSubsetOf(a, b);

/** Mimic the mathematical sum operator */
const sumAll = (iterable, expression) => reduce(
	toArray(iterable),
	(total, element) => total + expression(element),
	0,
);

/** Mimic the mathematical big union (bigcup) operator */
const unionAll = (iterable, expression) => reduce(
	toArray(iterable),
	(result, element) => union(result, expression(element)),
	emptySet(),
);

/**
 * Produce the power set of a given set
 * @param {Set} set - The set
 */
const powerSet = (set) => {
	if (size(set) === 0) {
		return toSet([emptySet()]);
	}

	const [next, ...rest] = set;
	return unionAll(
		powerSet(toSet(rest)),
		(subsetOfRest) => toSet([
			subsetOfRest,
			union(subsetOfRest, toSet([next]))
		]),
	);
};

/**
 * Recipe type definition
 * @typedef {Object} Recipe
 * @property {Set<Set>|Array<Set>} required - The set of character sets that must be represented in the password
 * @property {Set<Set>|Array<Set>} optional - The set of character sets that may be represented in the password or may not
 * @property {number} length - The length of the password
 */

/**
 * Produce number of possible outputs of the given password recipe
 * @param {Recipe} recipe - The recipe for generating the password
 */
const possibleStrings = ({ required, optional, length }) => {
	const optionalSets = toSetOfSets(optional);
	const requiredSets = toSetOfSets(required);

	// totalCount is the total number of permutations possible when a
	// password of length n is generated from the set R, which is the
	// union of all sets in the password recipe.
	const n = length;
	const R = unionAll(
		union(requiredSets, optionalSets),
		(s) => s
	);
	const totalCount = pow(size(R), n);

	// Each of these sets of sets represents a password recipe that we
	// will reject and thus must subtract from our total count.
	// We want to reject all subsets of the set of required sets except
	// the set of required sets itself.
	// For example, if L and D are required, rejectedSubsets
	// will contain {L} and {D} and will not contain {L, D}.
	// Optional sets are not part of this at all because they will
	// simply be tacked on at the end.
	const rejectedSubsets = filter(
		toArray(powerSet(requiredSets)),
		(set) => !areEqualSets(requiredSets, set),
	);

	// When requiredSets is {{}} (it is a set containing only the empty set),
	// powerSet(requiredSets) will also be {{}};
	// thus, rejectedSubsets will be empty, the reducing
	// function below will not run, and rejectedCount will be 0,
	// terminating the recursion.
	const rejectedCount = sumAll(
		rejectedSubsets,
		(subset) => possibleStrings({
			required: subset,
			optional,
			length
		}),
	);

	return totalCount - rejectedCount;
};

/**
 * Produce the entropy in bits of the given password recipe
 * @param {Recipe} recipe - The recipe for generating the password
 */
const entropy = (recipe) => log2(possibleStrings(recipe));


const upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const lower = "abcdefghijklmnopqrstuvwxyz";
const digits = "0123456789";
const expectations = [
	{ required: [""], length: 1, result: 0 },
	{ required: ["a"], length: 0, result: 0 },
	{ required: ["a"], length: 1, result: 1 },
	{ required: ["a"], length: 5, result: 1 },
	{ required: ["abcde"], length: 1, result: 5 },
	{ required: ["abcde"], length: 2, result: 25 },
	{ required: ["a", "1"], length: 2, result: 2 },
	{ required: ["ab", "123"], length: 2, result: 12 },

	{ required: [upper, lower, digits], length: 0, result: 0 },
	{ required: [upper, lower, digits], length: 1, result: 0 },
	{ required: [upper, lower, digits], length: 2, result: 0 },
	{ required: [upper, lower, digits], length: 3, result: 40560 },
	{ required: [upper + lower, digits], length: 3, result: 96720 },

	{ required: [upper], length: 3, result: 17576 },
	{ optional: [upper], length: 3, result: 17576 },
	{ required: [upper + lower + digits], length: 3, result: 238328 },
	{ optional: [upper, lower, digits], length: 3, result: 238328 },

	{ required: ["a", "1"], length: 1, result: 0 },
	{ required: ["a"], optional: ["1"], length: 1, result: 1 },
	{ required: ["a"], optional: ["A", "1"], length: 2, result: 5 },
	{ required: ["a"], optional: ["A1"], length: 2, result: 5 },
	{ required: ["a", "A"], optional: ["1"], length: 2, result: 2 },
	{ required: ["a", "A"], optional: ["1"], length: 3, result: 12 },
]

const test = () => expectations.every((e) => {
	const { required, optional, length, result } = e;
	const expected = result;
	const actual = possibleStrings({ required, optional, length });
	const testResult = actual === expected;

	if (!testResult) {
		console.error(
			`Expected: ${expected}`
			+ `\nActual: ${actual}`
			+ `\nTest: ${JSON.stringify(e)}`
		);
	}

	return testResult;
});

The consumer of PossibleStrings will need to check that the return value isn't 0 before trying to take a logarithm of it. This also serves as a nice test of whether the combined constraints can be satisfied.