Solving a “Layton Puzzle” with Prolog | Hacker News Reader

Solving a “Layton Puzzle” with Prolog

buttondown.com

110 pointsTomte28 comments

Don't understand why the article uses SWI's constraint libs when the problem is easily solved using pure ISO Prolog with code readily linked from the article even ie Pablo's solution at [2].

Just paste that code into [1] and append the line (or place it at the start, doesn't matter)

    :- initialization(colin_score(X)).

to tell Prolog which top-level goal to solve and hit Execute to see the solution in your browser.

[1]: https://quantumprolog.sgml.net/browser-demo/browser-demo.htm...

[2]: https://morepablo.com/2010/09/some-professor-layton-prolog.h...

It's hardly SWI's lib, clpFD is available almost identically in Sicstus, Ciao, GNU, B† and others. As to why? I dunno I guess for a lot of us constraint programming just comes to hand very naturally. It often feels more Prolog-y to us than non-constraint approaches.

†B-Prolog of course morphed into Picat which is also mentioned and Picat also leans heavy on clp so if the author is more familiar with Picat it would be even more natural to use clpFD.

It can be more briefly solved without constraints than the linked code, brute-forcing through the possible correct-answer permutations:

    member_of(List, X) :-  % helper swaps args for use with maplist.
        member(X, List).

    score(Given, Correct, Adder, NewScore) :-
        (Given = Correct                   % Prolog if/else
        ->  NewScore is Adder + 10
        ;   NewScore = Adder).

    puzzle(ColinScore) :-
        length(CorrectAnswers, 10),        % ten unknown correct answers,
        maplist(member_of([a,b]), CorrectAnswers),   % each 'a' or 'b'

        % compare player answers to correct answers, add their scores.
        foldl(score, [b,b,a,b,a,b,b,a,b,b], CorrectAnswers, 0, 70), % Mary
        foldl(score, [b,a,a,a,b,a,b,a,a,a], CorrectAnswers, 0, 50), % Dan
        foldl(score, [b,a,a,a,b,b,b,a,b,a], CorrectAnswers, 0, 30), % Lisa
        foldl(score, [b,b,a,a,a,b,b,a,a,a], CorrectAnswers, 0, ColinScore).

Then:

    ?- puzzle(ColinScore).
    ColinScore = 60

It's fine for a toy puzzle and it uses fewer resources than invoking the constraint solver, but it's a poor way to approach a puzzle or real world task with a larger search space.

The `(if -> then; else)` syntax introduces a cut, which I found hides possible solutions.

I believe that is not a concern in my code; if "a=a" then commiting to that cannot hide any possible solutions where either side of the equals could be different because we've already tested and found them equal (they unify). One can avoid that worry by swapping in this version instead:

    score(X, X, Adder, NewScore) :-
        NewScore is Adder + 10.

    score(X, Y, Adder, Adder) :-
        dif(X, Y).

Leaving choicepoints where I don't want them is an annoying part of Prolog when I know the answer is deterministic - that's where I used zcompare/3 in my other answer in this thread, but it's far too much effort to write that pattern for every test situation. For people who object to `is` then make it `succ(Adder, NewScore)` and adjust the player scores down by a factor of ten as per the blog post. For people who comment that succ/2 doesn't always work, note that the Adder is always initialised to 0 in the foldl goal so succ/2 always has one instantiated value.

[It just wouldn't be a Prolog solution if it wasn't hard to write, hard to read, hard to verify that it's working properly, full of single letter variable names OrLongWordVariableNames and immediately making people talk about cut and constraint handlers and ISO compatibility and Prolog internals rather than the problem. On that note, PabloLife's code has "flip(correct, incorrect)" which is imperatively named but doesn't do anything imperative, uses nested lists instead of Number-Answer pairs which is more visually cluttered and uses more memory...].

Very fun post! If folks haven't seen it, Knuth's latest release looks at constraint satisfaction. Really fun discussion on the relations between different ways to model this sort of problem. Happy to add this book to my list!

I would also challenge the author to consider puzzles a bit more. Sprinkling fun into the topics goes a long way. Specifically, do both! Talk about how you can reframe a "real world" problem in terms of some puzzles we may have played as kids. Invite us to play more as adults.

if anyone wants a "human" solution

1) there are 4 questions that everyone answered the same way (let's say this earned everyone A points)

2) in the rest of the questions, 7-point and 5-point students gave opposite answers

that means that 7-A (rest of 7-point student's correct answers) equals to 5-(4-A) (rest of 5-point student's incorrect answers)

7-A = 1+A => A=3

That means 3-point student scored 3 points together with everyone else, and answered rest of the questions wrong

From this it's trivial to find the hidden score and why there are 4 possible answer keys

It seems to have been designed to be easy to solve by hand.

My approach:

1. Dan and Lisa agree on 8 out of 10 answers.

2. Dan, by changing two of Lisa's answers, has gained 20 points. Dan is right about both of those answers (6 and 9).

3. Mary is wrong about answers 6 and 9.

4. Mary has a total of three mistakes.

5. There are 8 possible answer keys, because Mary only has one mistake left to distribute among the other 8 answers.

6. On four of those possible answer keys, Lisa scores 50 points. Those are invalid.

7. Mary's mistake must be in answer to question 1, 3, 7, or 8.

8. On all four of those questions, Colin agrees with Mary.

9. Colin scores 30 points collectively on questions 1, 3, 7, and 8, plus 10 points each on questions 2, 5, and 9. 60 points.

It definitely has been designed to be solved by hand or possibly even in your head. Nintendo aren't in the habit of handing out Advent of Code questions in their games. Honestly, the sophistication of the puzzle design is extremely admirable.

A puzzle from a game in this series https://en.wikipedia.org/wiki/Professor_Layton

What nostalgia!I haven't played any since one of the early 3DS ones. And there's an incoming one for the switch too!

One of my favorite series from when I was younger. I only ever played the DS ones, not the 3DS ones. That was the 2008-2011 timeframe -- 14-17 years ago!

It’s this one from Professor Layton and the Diabolical Box: https://layton.fandom.com/wiki/Puzzle:Colin%27s_Score

It was fun to try to golf this a bit with Z3Py. I'm not an expert at writing for Z3, so it might be possible to do better, but here is a solution in 7 lines:

    import z3
    res = [("bbababbabb", 7), ("baaababaaa", 5), ("baaabbbaba", 3), ("bbaaabbaaa", z3.Int("x"))]
    key = [z3.Int(f"k{i}") for i in range(10)]
    z = z3.Solver()
    z.add([z3.Sum([ord(a) == k for a, k in zip(r[0], key)]) == r[1] for r in res])
    z.check()
    print(z.model()[res[-1][1]])

almost-one-liner (though it will give you the full model):

    import z3; z3.solve([z3.Sum([ord(a) == z3.Int(f"k{i}") for i, a in enumerate(r[0])]) == r[1] for r in [("bbababbabb", 7), ("baaababaaa", 5), ("baaabbbaba", 3), ("bbaaabbaaa", z3.Int("x"))]])

my take - more writeup style for people new to z3

https://happyhacks.bearblog.dev/solving-a-layton-puzzle-with...

Related: https://news.ycombinator.com/item?id=35623625 (2023) "Why Did Prolog Lose Steam (2010)"

Anecdotally, some years ago the Zebra Puzzle [1] made the rounds in my team. Two people solved it: myself, a young intern, who mapped out the constraints as a physical puzzle that I was able to solve visually, and a more seasoned colleague who used Prolog.

[1] https://en.wikipedia.org/wiki/Zebra_Puzzle

FYI, a very compact Prolog version of the Zebra/Einstein puzzle can be loaded into the editor for execution using "Load example" on [1].

[1]: https://quantumprolog.sgml.net/browser-demo/browser-demo.htm...

Doing the puzzle with “pencil and paper” logic is actually quite approachable and fun! I recommend it. Hint: you don’t need to run constraint satisfaction! There are some insightful shortcuts to be made

The puzzle is easy enough to solve by brute force, but it seems like rather a lot to solve by hand for a very junior-targeted game.

Heuristics could reduce trial-and-error to a reasonable search space, but is there a purely deductive way to solve this by hand?

With the 4 common answers (all 4 people answered them the same) we know that no more than 3 of them can be correct (because Lisa scored 3 points). We also know at least one must be correct (otherwise Mary can't score 7).

Examine what Mary and Dan have in common besides those 4... Nothing. They disagreed on each of the remaining 6 answers.

We can break this down into three cases, either 1, 2, or 3 of the common answers are correct:

1 - Impossible. Mary gets 6 of the remaining correct, Dan gets 4 of the 6 remaining correct, but they have none in common so this doesn't work.

2 - Impossible. Mary gets 5 of the remaining correct, Dan gets 3 of the remaining correct, but again their answers disagree so they cannot share a common answer out of the 6 remaining.

3. Mary needs 4 of the remaining 6 and Dan needs 2, this is feasible.

At this point you can ignore the 4 common ones other than to say Colin has at least a score of 3.

Since we now know that everything outside those common ones are incorrect for Lisa, cross everything off that Lisa and Colin share of the 6 non-common answers. There are only 3 that disagree with Lisa so they must be correct (because everything Lisa answered here is wrong). This gives Colin a final score of 6, three in common with everyone and three from disagreeing with Lisa.

The reason there are 4 keys in Hillel's solution is actually kind of funny, they don't matter. Those 4 keys only disagree on which of the 4 common answers are incorrect. They agree everywhere else.

EDIT: Presentation and some typos

I'm more of a visual person when it comes to puzzles like these so here's my take:

        1 2 3 4 5 6 7 8 9 10
  Mary  B B A B A B B A B B   7
  Dan   B A A A B A B A A A   5
  Lisa  B A A A B B B A B A   3
  Colin B B A A A B B A A A   ?

First I remove the answers that everyone agreed on. We know that one of these 4 answers is wrong because of Lisa.

        1 2 3 4 5 6 7 8 9 10
  Mary  _ B _ B A B _ _ B B   7
  Dan   _ A _ A B A _ _ A A   5
  Lisa  _ A _ A B B _ _ B A   3
  Colin _ B _ A A B _ _ A A   ?

Next we can assume anything matching Lisa's remaining answers are wrong, so I will put an x for those. These we 100% know are wrong answers.

        1 2 3 4 5 6 7 8 9 10
  Mary  _ B _ B A x _ _ x B   7
  Dan   _ x _ x x A _ _ A x   5
  Lisa  _ x _ x x x _ _ x x   3
  Colin _ B _ x A x _ _ A x   ?

If you count both the remaining answers and the blanks, you'll see they equal to their score + 1. That 1 being that unknown of the 4 original blank columns where everyone agreed.

So the answer for Colin would by 6 because he has 7 remaining answers.

> Next we can assume anything matching Lisa's remaining answers are wrong

This is incorrect. The assumption is true, but that's just a coincidence - you haven't justified it.

Dan and Lisa's answers agree on all but problems 6 and 9, and Dan got two more correct than Lisa. So Dan is correct on both 6 and 9. Therefore, Mary is incorrect on 6 and 9. So she got seven of the other eight correct, and Dan got three of the other eight correct. But on those eight problems, Mary and Dan disagree on only problems 2, 3, 5, and 10, therefore Mary got all four of those correct. Then Mary got three of problems 1, 4, 7, 8 correct, but everyone answered the same way on those, so Colin got three right on those problems as well. Then read off the deduced answer key for the other six problems to get Colin's final score.

To be fair, this is one of the hardest puzzles in the game.

I got to writing this Prolog/constraint version which you can try on SWISH by clicking https://swish.swi-prolog.org/p/FYMhJEmj.pl then clicking the blue 'Run' button in the lower right corner.

    :-use_module(library(clpfd)).

    % score/3 has mode ++- and maps
    % a given answer and a correct answer to a score.
    score(Given, Correct, Score) :-
        zcompare(Order, Given, Correct),
        score_(Order, Score).

    score_(=, 10).   % 10 points if given matches correct,
    score_(<, 0).    % else 0 points
    score_(>, 0).

    puzzle(ColinTotal, ColinScores, CorrectAnswers) :-
        A = 0,                      % false
        B = 1,                      % true
        length(CorrectAnswers, 10), % ten unknown correct answers,
        CorrectAnswers ins 0..1,    % all either true or false.

        % compare player answers with correct answers, add their scores.
        maplist(score, [B,B,A,B,A,B,B,A,B,B], CorrectAnswers, Mary),
        sum(Mary, #=, 70),
        maplist(score, [B,A,A,A,B,A,B,A,A,A], CorrectAnswers, Dan),
        sum(Dan, #=, 50),
        maplist(score, [B,A,A,A,B,B,B,A,B,A], CorrectAnswers, Lisa),
        sum(Lisa, #=, 30),
        maplist(score, [B,B,A,A,A,B,B,A,A,A], CorrectAnswers, ColinScores),
        sum(ColinScores, #=, ColinTotal).

Then this query:

    ?- puzzle(ColinTotal, ColinScores, CorrectAnswers).

Solves without a constraint solver search and gives four possible solutions, each giving the same score for Colin which I've aligned by hand for this comment:

    ColinTotal = 60,
    ColinScores =    [10, 10, 10,  0, 10,  0, 10,  0, 10,  0],
    CorrectAnswers = [ 1,  1,  0,  1,  0,  0,  1,  1,  0,  1]

    ColinTotal = 60,
    ColinScores =    [10, 10, 10,  0, 10,  0,  0, 10, 10,  0],
    CorrectAnswers = [ 1,  1,  0,  1,  0,  0,  0,  0,  0,  1]

    ColinTotal = 60,
    ColinScores =    [10, 10,  0,  0, 10,  0, 10, 10, 10,  0],
    CorrectAnswers = [ 1,  1,  1,  1,  0,  0,  1,  0,  0,  1]

    ColinTotal = 60,
    ColinScores =    [ 0, 10, 10,  0, 10,  0, 10, 10, 10,  0],
    CorrectAnswers = [ 0,  1,  0,  1,  0,  0,  1,  0,  0,  1]

Questions 2,4,5,6,9,10 have a fixed correct answer and 1,3,7,8 can vary and the puzzle is still coherent and solvable.

I once used Sentient[0] to solve a similar puzzle in a different game that I think made a puzzle that required a constraint solver as a joke on the player. I'm a bit saddened to see that the repo hasn't been updated in 6 years, and a node update broke the binary installed on my computer, I find it a much more ergonomic environment than Prolog, hopefully someone else will pick up the mantle.

[0]: https://sentient-lang.org/

well as long as we're swaping our own answers here is mine:

  %%% This works in swi as is
  %%% in ciao we need to include some modules
  %:- use_module(library(numlists)).
  %:- use_module(library(hiordlib)).
  %:- use_package(clpfd).

  main :-
   M = [b,b,a,b,a,b,b,a,b,b],
   D = [b,a,a,a,b,a,b,a,a,a],
   L = [b,a,a,a,b,b,b,a,b,a],
   C = [b,b,a,a,a,b,b,a,a,a],
   score(K,M,7), score(K,D,5), score(K,L,3),
   score(K,C,S),
   write(S). 
  
  score(K,T,S) :-
   maplist(eq_OZ,K,T,SL),
   sum_list(SL,S).
  
  eq_OZ(X,X,1).
  eq_OZ(X,Y,0) :- dif(X,Y).
  
  
  %%% ciao doesn't have dif/2 so we use this
  %eq_OZ(X,Y,0) :- X #\= Y.

Reply on news.ycombinator.com