Automating the Blue Prince Parlor Puzzle
This is a continuation of last week's post. Please read that one first!
In that post, we built an engine that could take puzzles of the following form:
blue: the gems are in a box with a true statement
white: the gems are in a box with a false statement
black: The white box is true
Given the rules:
- There will always be at least one box that makes only true statements.
- There will always be at least one box that makes only false statements.
- There is a prize in exactly one box.
translated into logic like
const BlueStatement = Or(
And(BlueBoxIsTrue, BlueBoxHasGems),
And(WhiteBoxIsTrue, WhiteBoxHasGems),
And(BlackBoxIsTrue, BlackBoxHasGems),
);
const WhiteStatement = Or(
And(BlueBoxIsFalse, BlueBoxHasGems),
And(WhiteBoxIsFalse, WhiteBoxHasGems),
And(BlackBoxIsFalse, BlackBoxHasGems),
);
const BlackStatement = WhiteBoxIsTrue;
and outputs the solution:
gems are in blue box
Today we're going to build the next layer of this and be able to solve some limited subset of the puzzles by parsing the English text directly by building up a little parser combinator library.
We need to define a couple terms and then everything else will fall out pretty naturally.
A partial parse is a pair of a value and a remainder to be parsed:
const Partial = (v, r) => {
return {
map: f => Partial(f(v), r),
take: () => v,
remainder: () => r,
pair: () => [v, r],
};
};
A parser is a function which takes a string and returns an iterator of all the possible partial parses that can result from that string.
The Constant parser strips some prefix off of the front of a string, or it fails:
const Constant = str => function*(x) {
if (x.startsWith(str)) {
yield Partial(str, x.slice(str.length));
}
};
const milkParser = Constant("milk");
console.log([...milkParser("milk and eggs")].map(x => x.pair()));
console.log([...milkParser("eggs and milk")].map(x => x.pair()));
Gives
[ [ 'milk', ' and eggs' ] ]
[]
The first line denotes a successful parse, because the iterator returned a value, and the second line denotes an unsuccessful parse.
We're going to complicate this model just slightly, we're going to wrap all of our parsers solely so we can attach postfix methods to them. This might look like it adds unnecessary noise but I promise it will make some things much nicer down the road.
const P = p => {
let f = function*(x) {
yield* p(x);
};
f.map = f => P(function*(x) {
for (let y of p(x)) {
yield y.map(f);
}
});
return f;
}
So our definition of Constant just becomes
let Constant = str => P(function*(x) {
if (x.startsWith(str)) {
yield Partial(str, x.slice(str.length));
}
});
We can build up a couple helpful tools to combine parsers from here. An Optional combinator returns a new version of a parser that might not be applied:
const Optional = parser => P(function*(x) {
yield Constant("")(x);
yield* parser(x);
});
const milkParser = Optional(Constant("milk"));
console.log([...milkParser("milk and eggs")].map(x => x.pair()));
Now there are two ways to parse this: either we don't succeed on the first parse, or we do. The result shows this:
[ [ null, 'milk and eggs' ], [ 'milk', ' and eggs' ] ]
The Concat operator takes a set of parsers and applies them one after the other. In my opinion it's easiest to write recursively: the concatenation of zero parsers is a parser that always matches an empty string, and the concatenation of p, ...ps is p concatenated to Concat(...ps):
let Concat = (...parsers) => P(function*(x) {
if (parsers.length === 0) {
// Will parse nothing and yield empty array.
yield* Constant("").map(() => [])(x);
return;
}
let [p, ...ps] = parsers;
let restParser = Concat(...ps);
for (let parse of p(x)) {
for (let restParse of restParser(parse.rest())) {
yield parse.cons(restParse);
}
}
});
This is going to be the trickiest thing we do here, so make sure you understand it! This is a deceptively powerful definition. It lets us parse some stuff that our model in Parsing is Search failed on. Consider the example of the regular expression abc(def)?def, which we can express as:
console.log([...abcParser("abcdef")].map(x => x.pair()));
console.log([...abcParser("abcdefdef")].map(x => x.pair()));
This outputs:
[ [ [ 'abc', null, 'def' ], '' ] ]
[ [ [ 'abc', null, 'def' ], 'def' ], [ [ 'abc', 'def', 'def' ], '' ] ]
Note that the second string, abcdefdef shows two valid parses, with one of them not reaching the end of the input. It's reasonable for us to require our parsers to parse the entire string, so we can add a new tool that requires this:
const Eof = parser => function*(x) {
for (let result of parser(x)) {
if (result.rest() === '') {
yield result;
}
}
};
abcParser = Eof(abcParser);
The reason this parsing technique can handle what is a search problem is that it is doing a search: it's doing a depth-first search over all the valid parses.
The last tool we need is a way to select from one of multiple parsers. This is easy enough:
const OneOf = (...parsers) => P(function*(x) {
for (let p of parsers) {
yield* p(x);
}
});
We have enough tools now to parse our first box puzzle. Let's start with
blue: only one box is true
white: only one box contains the gems
black: the gems are in the white box
One thing I like about parsing with this technique is that we can start very simple, by parsing our literal example, and then generalize from there.
let puzzle = `blue: only one box is true
white: only one box contains the gems
black: the gems are in the white box`;
const Space = Constant(" ");
const Newline = Constant("\n");
const PuzzleParser = Concat(
Constant("blue: only one box is true"), Newline,
Constant("white: only one box contains the gems"), Newline,
Constant("black: the gems are in the white box"),
);
console.log([...PuzzleParser(puzzle)].map(x => x.pair()));
This outputs what we might expect:
[
[
[
'blue: only one box is true',
'\n',
'white: only one box contains the gems',
'\n',
'black: the gems are in the white box'
],
''
]
]
Let's generalize a bit:
const Statement = OneOf(
Constant("only one box is true"),
Constant("only one box contains the gems"),
Constant("the gems are in the white box"),
)
const PuzzleParser = Concat(
Constant("blue: "), Statement, Newline,
Constant("white: "), Statement, Newline,
Constant("black: "), Statement,
);
We can check this still works:
[
[
[
'blue: ',
'only one box is true',
'\n',
'white: ',
'only one box contains the gems',
'\n',
'black: ',
'the gems are in the white box'
],
''
]
]
Generalizing further:
const Adjective = OneOf(
Constant("is true"),
Constant("contains the gems"),
);
const Color = OneOf(
Constant("blue"),
Constant("white"),
Constant("black"),
);
const Statement = OneOf(
Concat(
Constant("only one box "),
Adjective
),
Concat(
Constant("the gems are in the "),
Color,
Constant(" box"),
)
);
Now we might want to start adding some structure to our parses so we can eventually translate them into propositional logic. Having these loose strings around is not very productive for interpreting them semantically. We can make use of our map operation to imbue meaning after we do a parse:
const Adjective = OneOf(
Constant("is true").map(() => ({"type": "IS_TRUE"})),
Constant("contains the gems").map(() => ({"type": "CONTAINS_GEMS"})),
);
const Color = OneOf(
Constant("blue"),
Constant("white"),
Constant("black"),
);
const Statement = OneOf(
Concat(
Constant("only one box "),
Adjective
).map(([, adjective]) => ({
type: "ONLY_ONE_BOX",
adjective,
})),
Concat(
Constant("the gems are in the "),
Color,
Constant(" box"),
).map(([, color, ]) => ({
type: "GEMS_IN_COLOR",
color,
})),
)
const PuzzleParser = Eof(Concat(
Constant("blue: "), Statement, Newline,
Constant("white: "), Statement, Newline,
Constant("black: "), Statement,
).map(([
, blue, ,
, white, ,
, black
]) => ({
blue, white, black,
})));
Now running our parser on our puzzle we get:
{
blue: { type: 'ONLY_ONE_BOX', adjective: { type: 'IS_TRUE' } },
white: { type: 'ONLY_ONE_BOX', adjective: { type: 'CONTAINS_GEMS' } },
black: { type: 'GEMS_IN_COLOR', color: 'white' }
}
We could go a bit further in enhancing our parser here but I think you get the idea, and could make those extensions yourself. We can now figure out how to translate these parse trees into our propositional logic from before.
We will call this process Build, for no reason other than it sounds nice to me. So our whole pipeline will be:
Parseto bring a string to a syntax tree,Buildto bring a syntax tree to a propositional logic formula, andSolveto bring a propositional logic formula to a resolution to the puzzle.
Build is a pretty straightforward tree-walk:
const Build = puzzle => {
return {
blue: BuildStatement("blue", puzzle.blue),
white: BuildStatement("white", puzzle.white),
black: BuildStatement("black", puzzle.black),
};
};
const BuildAdjective = (context, adjective) => {
switch (adjective.type) {
case "IS_TRUE":
switch (context) {
case "blue": return logic.BlueBoxIsTrue;
case "white": return logic.WhiteBoxIsTrue;
case "black": return logic.BlackBoxIsTrue;
default: throw new Error(`unknown context ${context}`);
}
case "CONTAINS_GEMS":
switch (context) {
case "blue": return logic.BlueBoxHasGems;
case "white": return logic.WhiteBoxHasGems;
case "black": return logic.BlackBoxHasGems;
default: throw new Error(`unknown context ${context}`);
}
default:
throw new Error(`unhandled adjective type ${adjective.type}`);
};
};
const BuildStatement = (context, statement) => {
switch (statement.type) {
case "ONLY_ONE_BOX":
let isBlue = BuildAdjective("blue", statement.adjective);
let isWhite = BuildAdjective("white", statement.adjective);
let isBlack = BuildAdjective("black", statement.adjective);
return logic.Or(
logic.And(logic.Not(isWhite), isBlue, logic.Not(isBlack)),
logic.And(isWhite, logic.Not(isBlue), logic.Not(isBlack)),
logic.And(logic.Not(isWhite), logic.Not(isBlue), isBlack),
);
case "GEMS_IN_COLOR":
switch (statement.color) {
case "blue": return logic.BlueBoxHasGems;
case "white": return logic.WhiteBoxHasGems;
case "black": return logic.BlackBoxHasGems;
default: throw new Error("bad color");
}
default:
throw new Error(`unhandled statement type ${statement.type}`);
};
};
let built = Build(parsed);
console.log("blue:", logic.WriteTopLevel(built.blue));
console.log("white:", logic.WriteTopLevel(built.white));
console.log("black:", logic.WriteTopLevel(built.black));
This outputs:
blue: ((¬WhiteBoxIsTrue ∧ BlueBoxIsTrue ∧ ¬BlackBoxIsTrue) ∨ (WhiteBoxIsTrue ∧ ¬BlueBoxIsTrue ∧ ¬BlackBoxIsTrue) ∨ (¬WhiteBoxIsTrue ∧ ¬BlueBoxIsTrue ∧ BlackBoxIsTrue
))
white: ((¬WhiteBoxHasGems ∧ BlueBoxHasGems ∧ ¬BlackBoxHasGems) ∨ (WhiteBoxHasGems ∧ ¬BlueBoxHasGems ∧ ¬BlackBoxHasGems) ∨ (¬WhiteBoxHasGems ∧ ¬BlueBoxHasGems ∧ Black
BoxHasGems))
black: WhiteBoxHasGems
Which squinting, looks right.
We can plug this into our solver from last week:
console.log(logic.Solve(built));
Which outputs, as we'd hope:
{ type: 'SUCCESS', gemBox: 'white' }
Which we can think about a bit and decide we agree with.
It's pretty easy to extend our grammar and builder from here, translating all kinds of statements into logic. I'll leave that as an (enjoyable!) exercise. Lots of kinds of expressions need some additional context, like the text of the other expressions on the boxes, in order to interpret.
The initial framing of this problem was: if you're making a game like Blue Prince, you might want to be able to automatically verify that the logic puzzles you've written are valid. These things are tricky and easy to fool yourself with. And if we extend our grammar sufficiently, we can do just that. But we've actually written our grammar in a clever way, and we can do something even fancier now. Because our implementation of the parser was so abstract, we can run it in reverse: instead of recognizing and parsing parlor box puzzles, we can use the same grammar to generate them.
Of course, the parser only guarantees that the strings we generate are syntactically valid; they look like a parlor box puzzle, but they might not follow the rules and give only a single solution...except, well, we also have a tool for taking such puzzles and checking that they have a single solution! We just built one!
First, we need to replace Partial with GenPartial, it does the same thing, except it ignores maps, and for concatenating results, it just appends strings rather than concatenating lists:
const GenPartial = (v) => {
return {
map: f => GenPartial(v),
take: () => v,
rest: () => null,
pair: () => [v, null],
cons: (other) => GenPartial(v + other.take()),
};
};
Then we need GenConstant, which is the same as Constant except it always yields the value we gave it as a GenPartial:
let GenConstant = str => P(function*(x) {
yield GenPartial(str);
});
And that's it! We just need to abstract the rest of our parsers over which version of Constant they use:
const MakeParser = Constant => {
let Optional = parser => (function*(x) {
... all the code we just wrote ...
return PuzzleParser;
}
const PuzzleParser = MakeParser(Constant);
const PuzzleGenerator = MakeParser(GenConstant);
Now we can run PuzzleGenerator:
for (let p of PuzzleGenerator()) {
console.log(p.take())
console.log('----');
}
blue: only one box is true
white: only one box is true
black: only one box is true
----
blue: only one box is true
white: only one box is true
black: only one box contains the gems
----
blue: only one box is true
white: only one box is true
black: the gems are in the blue box
----
blue: only one box is true
white: only one box is true
black: the gems are in the white box
----
blue: only one box is true
white: only one box is true
black: the gems are in the black box
----
blue: only one box is true
white: only one box contains the gems
black: only one box is true
... and a bunch more ...
To get a stream of syntactically valid puzzles.
Then we can filter down to the ones that work.
for (let p of PuzzleGenerator()) {
let parse = [...PuzzleParser(p.take())][0].take();
let built = Build(parse);
let solved = logic.Solve(built);
if (solved.type === "SUCCESS") {
console.log(p.take());
console.log('----');
}
}
You can see the list for this grammar here.
As we grow this grammar the number of possible puzzles grows very quickly, so enumerating all of the puzzles will become impractical very fast. Left as an exercise to sample from the space of strings instead!
As a caveat to this, it doesn't currently support multiple statements per box. This is not too hard but requires a little tweaking of the game rules.
Anyway, that's all I got. If you want to play around with the messy code you can find it here. Have a good one.