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...
†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.
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. 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...].
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.
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
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.
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]])
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"))]])
https://happyhacks.bearblog.dev/solving-a-layton-puzzle-with...
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://quantumprolog.sgml.net/browser-demo/browser-demo.htm...
Heuristics could reduce trial-and-error to a reasonable search space, but is there a purely deductive way to solve this by hand?
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
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.
This is incorrect. The assumption is true, but that's just a coincidence - you haven't justified it.
:-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. %%% 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.