Tuesday, February 23, 2016

Self-descriptive numbers: Prolog vs. MIP

In http://stackoverflow.com/questions/35485185/puzzle-taken-from-gardner a small problem is given:

image

I.e. there are 6 zeroes in the number, 2 ones, 1 two, and 1 six. This is called a self-descriptive number. The post is talking about a Prolog solution. Of course we can use a MIP solver instead of Prolog:

numbers

The solution looks ok:

---- VAR n  digit i

              LOWER          LEVEL          UPPER         MARGINAL

digit0        -INF            6.0000        +INF             .         
digit1        -INF            2.0000        +INF             .         
digit2        -INF            1.0000        +INF             .         
digit3        -INF             .            +INF             .         
digit4        -INF             .            +INF             .         
digit5        -INF             .            +INF             .         
digit6        -INF            1.0000        +INF             .         
digit7        -INF             .            +INF             .         
digit8        -INF             .            +INF             .         
digit9        -INF             .            +INF             .         

The very short Prolog code as mentioned in the post is:

:- use_module(library(clpfd)).
ten_cells(Ls) :- numlist(0, 9, Nums), pairs_keys_values(Pairs, Nums, Ls), global_cardinality(Ls, Pairs).

It is extremely short but not exactly very readable or intuitive (I guess that was not one of the design criteria for Prolog – see here for a discussion about write-only languages with a particularly illuminating APL example showcasing this concept). I prefer here the mathematical optimization model. A plus for the Prolog version is that it also verifies there is only a single solution for n=10.