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;
});

This is going to be fun to write up! And it a spectacularly elegant solution as well.

The hardest part, I think, will be in explaining why the (non-recursive) expression for the three character set case does the right thing. That is, the rationale for that.

Do you mean for two character sets? The non-recursive equation you had works for two required sets but not for three.

Do you mean for two character sets? The non-recursive equation you had works for two required sets but not for three.

No. I was saying that we need to explain why mine gave the wrong results. So I think we need to explain why what you had (before you introduced recursion)

P3(S1, S2, S3, n) = |S1 ∪ S2 ∪ S3|^n - [(|S1|^n + |S2|^n + |S3|^n) + ([|S1 ∪ S2|^n - (|S1|^n + |S2|^n)] + [|S1 ∪ S3|^n - (|S1|^n + |S3|^n)] + [|S2 ∪ S3|^n - (|S2|^n + |S3|^n)])

is the right thing for three sets. Once that is grasped, we can then explain why

• That way will get exceedingly message when trying this for four sets (and worse for five, etc ...)
• But yields to a nice recursive statement

But I was trying to say that before we talk about the recursive (and general) characterization, we need to explain that the various terms in the non-recursive statement for P3 are about.

Ah, yes.

I've revised it one more time to abstract my uses of reduce into two functions that mimic mathematical expressions more closely, sumAll and unionAll. I also renamed some functions and removed a couple of preemptive conditional checks to make the algorithm match your mathematical expression more closely.

Thanks for going over the mathematical description. I want to make sure that it matches the algorithm.

I spent way too much time last night trying to make equation (12) moderately legible. But it doesn't really matter. No one is going to try to read it.

It's kind of cool that the final form doesn't need to state the base for recursion. Everything should nicely zero out and R is empty, giving just a number of A alone.

It's kind of cool that the final form doesn't need to state the base for recursion. Everything should nicely zero out and R is empty, giving just a number of A alone.

Yeah that's really cool. It ended up being a pretty tidy function after all. :)

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.