Jan 12, 2015

On puzzles, Prolog and problem solving fallacies

Let's consider a puzzle:

Two friends are talking: "When the day after tomorrow becomes "yesterday", the day which we will then call "today" will have the same distance to Sunday as the day, which we were calling "today" when yesterday still was "tomorrow". Question: what was the day of the week when the friends were talking?

Uhm, what?..

Well, it's just a convoluted way to say that "the day Today+3 has the same distance to a Sunday as the day Today-2":

It's pretty easy to find the solution by just trying all the seven possibilities until the correct one is found.

However, who needs to think when one could write a program!

Let's do exactly that, using Prolog programming language. For example, SWI-Prolog can be used, and it also has an online frontend for quick experimenting.


Facts

In Prolog, we state the problem (plus some ground knowledge) declaratively, and then ask the runtime to "figure out" the solution for us. So let's start from the ground knowledge about the "tomorrow" relationship:

% "tomorrow":
tomorrow(su, mo).
tomorrow(mo, tu).
tomorrow(tu, we).
tomorrow(we, th).
tomorrow(th, fr).
tomorrow(fr, sa).
tomorrow(sa, su).

su, mo, tu, we, th, fr, sa, su are so-called atoms (they must start from the lowercase), tomorrow is a predicate, and what we did here is stating that "It is a true fact that Monday is a tomorrow to Sunday. It is a true fact that Tuesday is a tomorrow to Monday...It is a true fact that Sunday is a tomorrow to Saturday. It is known."

By listing these kind of facts, we create the knowledge base which can be later used for submitting queries about.

For example, a query "is Thursday tomorrow of Wednesday?" On which Prolog answers "true."

    ?- tomorrow(we, th).
    true.

Or, a query "is Friday tomorrow of Wednesday?" On which Prolog answers "false."

    ?- tomorrow(we, fr).
    false.

There are more interesting types of queries we can do using so-called free variables (which names must start from the uppercase):

    ?- tomorrow(we, X).
    X = th ;
    false.

What happened there is that we told: "we know that the first argument is Wednesday, but we don't know the second one (naming it X). Could you figure out for us which values could X take, so that the statement is true?". And Prolog happily infers for us all the possible values of X, listing them separated by a semicolon. In this case it's a single possible value ("Tuesday"), after which it writes "false" meaning "no more values" (this may differ for other Prolog implementations):

We can put the free variable into any position. For example "which day Wednesday is tomorrow of?"

    ?- tomorrow(X, we).
    X = tu ;
    false.

Or even, "what are the days so that one is tomorrow of another?". On which Prolog will print all the knowledge base it has so far, saying that "well, it can be any of these pairs, but nothing else that I know of":

    ?- tomorrow(X, Y).
    X = su, Y = mo ;
    X = mo, Y = tu ;
    X = tu, Y = we ;
    X = we, Y = th ;
    X = th, Y = fr ;
    X = fr, Y = sa ;
    X = sa, Y = su ;
    false.

Likewise, we can specify the knowledge about what "distance to Sunday" value is for different days of the week:

%  "distance to Sunday":
dist_to_sunday(su, 0).
dist_to_sunday(mo, 1).
dist_to_sunday(tu, 2).
dist_to_sunday(we, 3).
dist_to_sunday(th, 3).
dist_to_sunday(fr, 2).
dist_to_sunday(sa, 1).

Predicates

So far we've specified only facts (so-called "headless predicates", or "headless Horn clauses"), which were just stating that something is always true. We can create more complex predicates, which would reflect a logical implication (if the right part is true, then the left part is true). For example, here's how we specify "yesterday" based on "tomorrow":

% "yesterday":
yesterday(X, Y):- tomorrow(Y, X).

which means "Y is yesterday of X if X is tomorrow of Y". And again, we can make queries, e.g. asking "what is the day, that is yesterday of Sunday?":

    ?- yesterday(su, X).
    X = sa ;
    false.

Prolog will "figure out" that since in order for some day to be yesterday to Sunday, the latter must be tomorrow for that day, and Sunday is tomorrow to Saturday.

Predicates can have several statements at the right hand side, separated by comma, which means and:

%  "the day after tomorrow":
day_after_tomorrow(X, Y):- tomorrow(X, Z), tomorrow(Z, Y).

Y is the day after tomorrow to X, if there is some Z, such as Z is tomorrow to X and Y is tomorrow to Z.

    ?- day_after_tomorrow(su, X).
    X = tu ;
    false.

Problem statement

We now can put the full problem description into a separate predicate, which is basically a mapping of the problem formulation into a sequence of statements separated by comma.

Essentially, we state that there exist such days X (Today+3) and Y (Today-2), so that there is some distance-to-Sunday value D, which is the same for both X and Y:

%  the problem statement
conversation(Today) :-
    % the day after tomorrow becomes "yesterday":
    day_after_tomorrow(Today, X0), yesterday(X, X0),
    % the same distance to Sunday
    dist_to_sunday(X, D), dist_to_sunday(Y, D),
    % when yesterday still was still "tomorrow"
    yesterday(Today, Y0), tomorrow(Y, Y0).

Here's the online version of the code.


Solution

Now we can make a query: "what should be X, so that our problem statement is true?"

   ?- conversation(X).
   X = we ;
   false.

And the answer is: Wednesday!

Which makes sense, if we try to visualize it:


Problem MkII

Consider a slight modification to the problem:

Two friends are talking: "When the day after tomorrow becomes "yesterday", the day which we will then call "today" will have the same distance to Sunday as the day, which we were calling "today" when the day before yesterday still was "tomorrow". Question: what was the day of the week when the friends were talking?

The only difference from the original problem is that instead of (Today-2) we are talking about (Today-3):

And that's when having written a program kind of starts to pay off. We just add a definition of "the day before yesterday":

%  "the day before yesterday":
day_before_yesterday(X, Y):- day_after_tomorrow(Y, X).

And the new "conversation" predicate is modified correspondingly:

conversation(Today) :-
    % the day after tomorrow becomes "yesterday":
    day_after_tomorrow(Today, X0), yesterday(X, X0),
    % the same distance to Sunday
    dist_to_sunday(X, D), dist_to_sunday(Y, D),
    % when the day before yesterday still was still "tomorrow"
    day_before_yesterday(Today, Y0), tomorrow(Y, Y0).

(online version).

Running it reveals that the new answer is Sunday, which again makes sense:

   ?- conversation(X).
   X = su ;
   false.

Problem MkIII

One more slight modification:

Two friends are talking: "When the day after tomorrow becomes "yesterday", the day which we will then call "today" will have the same distance to Sunday (not the current week's one) as the day, which we were calling "today" when the day before yesterday still was "tomorrow". Question: what was the day of the week when the friends were talking?

Which means that when we measure the distance to Sunday, that Sunday should not be on the same week as "Today" that we are looking for:

This complicates things a bit, since now our "distances to Sunday" are different depending on the week.

A hack we could do is to separate the "previous week", "current week" and "next week" days, and do something like:

%  "distance to Sunday" for week before
dist_to_sunday(mo0, 1). dist_to_sunday(tu0, 2). dist_to_sunday(we0, 3).
dist_to_sunday(th0, 3). dist_to_sunday(fr0, 2). dist_to_sunday(sa0, 1).
dist_to_sunday(su0, 0).

%  "distance to Sunday" for the current week
dist_to_sunday(mo, 1). dist_to_sunday(tu, 2). dist_to_sunday(we, 3).
dist_to_sunday(th, 4). dist_to_sunday(fr, 5). dist_to_sunday(sa, 6).
dist_to_sunday(su, 7).

%  "distance to Sunday" for the week after
dist_to_sunday(mo1, 1). dist_to_sunday(tu1, 2). dist_to_sunday(we1, 3).
dist_to_sunday(th1, 3). dist_to_sunday(fr1, 2). dist_to_sunday(sa1, 1).
dist_to_sunday(su1, 0).

Which is a way too verbose as we'd need to do something similar with the "tomorrow" predicate as well.

What if we specified both "days" and "distances" as lists:

% list of days for three weeks in a row:
days([mo0, tu0, we0, th0, fr0, sa0, su0,   % previous week
      mo,  tu,  we,  th,  fr,  sa,  su,    % current week
      mo1, tu1, we1, th1, fr1, sa1, su1]). % next week

% corresponding distances to Sunday (which is not on current week)
distances([1, 2, 3, 3, 2, 1, 0,
           1, 2, 3, 4, 5, 6, 7,
           6, 5, 4, 3, 2, 1, 0]).

and then used these lists to set up the facts about both "distance_to_sunday" and "tomorrow"?.. We can do that by specifying some helper (recursive) predicates that work on lists. The first one is "lookup": it is supposed to be true when variables X and Y have the same index inside the corresponding lists (the 3rd and 4th predicate arguments):

% true when X and Y are at the same position in corresponding lists
lookup(X, Y, [X|_], [Y|_]).
lookup(X, Y, [_|T1], [_|T2]) :- lookup(X, Y, T1, T2).

The first line says that "this predicate is true when both X and Y are at the beginning of their corresponding lists". The second line says "otherwise, recursively assert the same for the list tails". Then, "dist_to_sunday" can be written as:

dist_to_sunday(X, D) :-
    days(L1), distances(L2), lookup(X, D, L1, L2).

which can be read as "X has distance to Sunday D, if if X and D stand at the same positions in the corresponding lists L1 (which is a list of days) and L2 (which is a list of distances).

Similarly, for "tomorrow" we create another helper predicate, "consecutive", which will be true if two given variables appear consecutively in some list:

% true when Y follows X in a list
consecutive(X, Y, [X, Y|_]).
consecutive(X, Y, [_|T]):- consecutive(X, Y, T).

tomorrow(X, Y) :- days(L), consecutive(X, Y, L).

The rest of the program remains the same as before. Here's the full online version.

Querying it gives the new answer, which is actually the same as before, except now "distances to Sunday" are indeed measured differently:

   ?- conversation(X).
   X = su ;
   false.

Problem MkIV

Finally, one more slight modification:

Two friends are talking: "When the day after tomorrow becomes "yesterday", the day which we will then call "today" will have the same distance to Sunday (not that day's week one) as the day, which we were calling "today" when the day before yesterday still was "tomorrow". Question: what was the day of the week when the friends were talking?

I.e. "distance to Sunday" now is measured even differently: the Sunday should not be on the same week as the day we are measuring distance from.

Looking at how distances-to-Sunday change this time, we can see that we are back to the simpler case when they repeat every week (except now with a different numbers). So we either could revert to the way the code was in the very first problem, or reuse the previous one and just shorten the arrays:

days([mo, tu, we, th, fr, sa, su, mo]).
distances([1, 2, 3, 4, 5, 6, 7, 1]).

The rest is the same as before, and here's the online version.

Regardless of what we do there, we get the answer to the query:

   ?- conversation(X).
   false.

Which means that there does not exist any such X that would satisfy the "conversation" predicate. Simply saying, there is no solution to this problem.

No solution?.. Really?..

That's what our program tells us, and it probably can not lie. It' has been correct so far, every time... right?

Well, "no solution" is also in a sense a solution, so mission accomplished!

Or is it? What about this one:

What if the friends were talking exactly during the midnight between Wednesday and Thursday?..

The fallacies of problem solving

So there actually is a solution. Of course, one could argue about its "correctness", pointing ambiguities and whatnot.

This does not change the point: too often we paint ourselves into the corner of some particular mind frame. Step by step, getting deeper into the details of the incidental complexity of the solution itself (rather than the original problem), at some point we lose the perspective and stop realizing which exactly problem is that we are solving, even though each step appears logical, maybe even elegant. And thus the domain of possible solutions gets artificially limited to whatever is dictated by the particular implementation. The boundaries of the box, that we keep thinking inside, get more and more rigid with every step, until "no solution" appears a viable and logical outcome.

It gets worse in case when originally we succesfully solved some other (but similar) problem, and then gradually refined the solution to the (seemingly, slightly) modified requirements.

Which often happens when developing software systems, where requirements are usually a moving target. How many times did you hear that something is "impossible" to do or there is "no solution" to some problem in a context of some existing software? Sometimes that very solution might be right there for taking, on the surface, where no one is seeing it. Because people were thinking they are solving some different problem than it really is.

There are ways of breaking out of this rigid mind cage. There are conventional wisdoms involving golden hammers, nails, kisses and what else. There are methodologies that already started aging but still have at their foundation the very idea of avoiding digging too deeply in the wrong direction before it's too late.

Even being aware of all that, it's still very tempting to follow the sweet track of what appears a nice/logical evolution of a code just to find out one fine day that it's not potent anymore. Like, at all.

So, in a sense, this was an "un-tutorial", a reminder that sometimes in order to find a solution one needs to unlearn whatever he thinks he knows about the problem.

No comments :