FiveThirtyEight Riddler — Prolog to the Rescue!

When querying in the interpreter, you can press ; to see more possible results.

In this case, after we hit the 17 result there were no more valid options, so Prolog returned false.

What happens if we give it an impossible claim like A is older than 18 and younger than 15??- between(10, 40, A), claim_older(A, 18), claim_younger(A, 15).


We can even specify claims about multiple people – this time the query is broken up into multiple lines to make it easier to read:?- between(10, 40, A), between(10, 40, B), claim_older(A, 15), claim_younger(A, 17), claim_older(B, 35).

A = 16,B = 36 ;A = 16,B = 37 ;A = 16,B = 38 ;A = 16,B = 39 ;A = 16,B = 40 ;false.

Prolog has spit out all of the possible pairs of ages that are valid for this scenario, neat!The Invention of LyingIn our first runs we were able to make claims but we always assumed those claims were true.

Per our problem statement, claims are only true if the claimant is under a certain age.

Let's define some additional rules for when a claim is made but the claimant is lying.

There are a few things to notice about our program now.

We are hard-coding the age of lying to 20 for now, we'll variablize this soon.

We've added the ability for a claim to have a Claimant as well – this the person making the claim.

We've added a second set of rules for each claim, now with one that supports a liar.

Notice the inverted comparison operators in each set of claims.

When Prolog looks through its rules it will find one that matches.

We can create an "or" condition by specifying multiple possibilities for each claim – one for a lying claimant and one for one who tells the truth.

We have added our claims and bounds to a run rule, this saves us some repetitive typing in the interpreter.

Now we can just query run(A, B) and see the results.

Let's do that now!?- run(A, B).

A = 15,B = 20 ;A = 16,B = 20 ;A = 17,B = 20 ;A = 18,B = 20 ;false.

Prolog has given us some pairs of ages that are valid given the rules we provided.

The possibilities boil down to 15 <= A <= 18, and B = 20.

If we look back to our original claims we basically had B claiming that A is older than 18 and younger than 15.

Since that is impossible, Prolog determined that B must be a liar.

But since liars are only at least 20 years old (since we hard coded that rule), B must be at least 20.

However, we also had A claiming that B was younger than 21.

Since we know A is between 15 and 18 (since B was a liar), we know A must be telling the truth (younger than 20).

So B indeed is younger than 21 and at least 20, or, in other words, B is 20.

Sexier RangesBet that's the first time you've seen those two words next to each other.

Prolog is great at giving us multiple solutions to the problem.

But we're going to be working a lot with ranges of ages.

For the previous example, it would have been great if rather than iterating through every possible set of ages Prolog could have told us the range of ages that were possible in one go.

Fortunately, Prolog provides a way to define "constraints" for values using something called Constraint Logic Programming.

Let's adapt our previous code to use constraints instead now.

Check out what's newWe import the clpfd module at the top of our program rules now, to get access to the constraint logic predicates.

We prefix our comparison operators with the # symbol.

So it's Person #< Age now instead of just Person < Age.

These operators are documented here if you'd like to read more about them.

We added a not_liar rule instead of using not(liar).

This is most likely due to my noob-ness with Prolog but I kept having trouble inverting the CLP constraint operators so I wrote it out explicitly.

Use A in 10.

40 instead of between(10, 40, A) in our run rule.

Now check out our output when we run — much more readable!?- run(A, B).

B = 20,A in 15.

18 ;false.

Variable LiarsUp until now, we've been assuming that everyone over 20 is a liar.

In reality, the age of that lying threshold is something we need to solve for as well.

We'll do this by making another variable for the lying age and pass that through with our claims.

We've pretty much just added an argument to each of our rules that will keep track of the lying age threshold.

We can test this by running again with our known threshold of 20.

?- run(A, B, 20).

B = 20,A in 15.

18 ;false.

Cool, same result, that makes sense!.But what if we want a variable lie threshold??- run(A, B, L).

A in 15.

18,A#>=L,L in 10.

18,B in 21.

40 ;​A in 15.

18,A#=<L+ -1,L in 16.

20,B#>=L,B#>=L,B in 16.

20 ;false.

This syntax is a little weirder but it makes sense if you parse it out.

I won't go into too much detail (it won't really matter when we plug in our actual claims) but here's the gist.

With a completely variable lie threshold (well, between 10 and 40 per our constraint) there are two solution possibilities.

We know B is a liar because of the impossible claim.

But what if A is a liar too.

Tying it all TogetherWe've got a pretty slick claiming system in a rather succinct format (imagine writing this code in another language!), now it's just time to fill out the actual claims from the problem statement and see what our solution is!.(obviously, spoilers ahead.

)A few quick things to note about the changes here:I've converted the run arguments to a list of islanders now, rather than explicitly saying A, B, etc.

Also, notice the ins syntax for a list rather than the in syntax for a single variable.

I've added claims for "equal" and "not equal" ages.

I probably could have gotten away with re-writing D's claim that E's age is not 17 in a different way, but I figured I'd be explicit.

I've loaded in the 10 claims from the problem statement.

And now if we run it, with our ages and lying threshold as variables, we will see our solution:?- run([A, B, C, D, E], L).

A = L, L = 19,B = 20,C = 18,D in 10.

16,E in 20.

40 ;false.

There you have it!.The age threshold is 19, making A (age 19), B (age 20) and E (age >= 20) all liars.

C (age 18) and D (age <= 16) are truth tellers.

I hope this post has at least minimally encouraged you to go explore some other programming languages or to scrounge up some interest in Prolog.

If you're curious or want to explore more, the completed and commented code from this tutorial is available on a GitHub gist here.

Also feel free to reach out to me with any questions, suggestions, or Prolog tips!.

. More details

Leave a Reply