{"id":51,"date":"2012-06-17T22:01:33","date_gmt":"2020-02-18T06:52:45","guid":{"rendered":"https:\/\/redfrontdoor.org\/blg2\/?p=51"},"modified":"2020-02-19T16:03:21","modified_gmt":"2020-02-19T16:03:21","slug":"post-45","status":"publish","type":"post","link":"https:\/\/redfrontdoor.org\/blog\/?p=51","title":{"rendered":"Solving Professor Popalop’s puzzles in Prolog"},"content":{"rendered":"\n

This puzzle was in my daughter’s Dandy:<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

and I thought it would give me an opportunity to experiment with Prolog, which I’d been meaning to do for a while. I used SWI-Prolog<\/a>.<\/p>\n\n\n\n

Structure of the puzzle<\/h2>\n\n\n\n
\"\"<\/figure><\/div>\n\n\n\n

We’ll represent a block of nine boxes as a list. A box is the expression X\/Y\/C, meaning that creature type C occupies location X\/Y, where the top-left box is 1\/1. We’ll have a fragment similar to<\/p>\n\n\n\n

Bs = [1\/1\/_, 1\/2\/_, 1\/3\/_,\n      2\/1\/_, 2\/2\/_, 2\/3\/_,\n      3\/1\/_, 3\/2\/_, 3\/3\/_]<\/pre>\n\n\n\n
Our goal is to find which creature can go in each box.<\/p>\n\n\n\n
The different types of creature<\/h2>\n\n\n\n
Every box must have a creature in it.<\/p>\n\n\n\n
box_has_creature(_\/_\/p).\nbox_has_creature(_\/_\/h).\nbox_has_creature(_\/_\/b).<\/pre>\n\n\n\n
\"\"<\/figure><\/div>\n\n\n\n
We’ll use the variable name ‘Bs’ throughout to mean ‘boxes’. We now bring together the fixed creature (who always goes in the top-left box) and the fact that all boxes must have creatures in them.<\/p>\n\n\n\n
challenge(C) :- Bs = [1\/1\/C, 1\/2\/_, 1\/3\/_,\n                      2\/1\/_, 2\/2\/_, 2\/3\/_,\n                      3\/1\/_, 3\/2\/_, 3\/3\/_],\n                maplist(box_has_creature, Bs),\n                to be continued....<\/i><\/pre>\n\n\n\n
Rules for each creature type<\/h2>\n\n\n\n
The conditions that we must satisfy for the various creature types:<\/p>\n\n\n\n
<\/figure><\/td>
<\/figure><\/td>
<\/figure><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
talk about the occupants of neighbouring boxes, so we need a way to find what sorts of creatures are adjacent to a given box.<\/p>\n\n\n\n
Meaning of ‘adjacent’<\/h3>\n\n\n\n
The instructions give a handy hint:<\/p>\n\n\n\n
\"\"\/<\/figure><\/div>\n\n\n\n
which we can translate as<\/p>\n\n\n\n
one_away(X, Y) :- Y is X + 1.\none_away(X, Y) :- X is Y + 1.\n\nadjacent(X1\/Y1, X2\/Y2) :- X1 = X2, one_away(Y1, Y2).\nadjacent(X1\/Y1, X2\/Y2) :- Y1 = Y2, one_away(X1, X2).<\/pre>\n\n\n\n
We now start by finding all creatures which occupy boxes adjacent to a given box. This will be a list of between two (for corner boxes) and four (for the central box) creature types, possibly including duplicates.<\/p>\n\n\n\n
adj_creatures([], _X\/_Y, []).\n\nadj_creatures([X1\/Y1\/C | Bs], X\/Y, [C | Cs])\n    :- adjacent(X1\/Y1, X\/Y),\n       adj_creatures(Bs, X\/Y, Cs).\n\nadj_creatures([X1\/Y1\/_C | Bs], X\/Y, Cs)\n    :- \\+ adjacent(X1\/Y1, X\/Y),\n       adj_creatures(Bs, X\/Y, Cs).<\/pre>\n\n\n\n
Then we want to remove any duplicates, to get a list of just the different types of creature which are adjacent to a given box.<\/p>\n\n\n\n
adj_creature_types(Bs, X\/Y, Cs)\n    :- adj_creatures(Bs, X\/Y, AllCs),\n       sort(AllCs, Cs).<\/pre>\n\n\n\n
We are now ready to translate the conditions on each creature type.<\/p>\n\n\n\n
Popops<\/h3>\n\n\n\n
\"\"\/<\/figure><\/div>\n\n\n\n
We don’t need to worry about these creatures.<\/p>\n\n\n\n
Hopples<\/h3>\n\n\n\n
\"\"\/<\/figure><\/div>\n\n\n\n
The ‘hopple rule’ is satisfied for a given box in one of two ways. Either the creature in that box is not a hopple, or it is<\/i> a hopple and there is another hopple in some adjacent box.<\/p>\n\n\n\n
hopple_ok(_X\/_Y\/C, _Bs) :- C \\= h.\nhopple_ok(X\/Y\/h, Bs) :- adj_creature_types(Bs, X\/Y, Cs),\n                        member(h, Cs).\n<\/pre>\n\n\n\n
Bungos<\/h3>\n\n\n\n
\"\"\/<\/figure><\/div>\n\n\n\n
We approach the bungos in a similar way to the hopples. We obey the ‘bungo rule’ for a given box if its occupant is not a bungo, or if it is a bungo, and among its neighbours there is<\/i> a popop and there is not<\/i> a hopple.<\/p>\n\n\n\n
bungo_ok(_X\/_Y\/C, _Bs) :- C \\= b.\nbungo_ok(X\/Y\/b, Bs) :- adj_creature_types(Bs, X\/Y, Cs),\n                       member(p, Cs),\n                       \\+ member(h, Cs).<\/pre>\n\n\n\n
Rules apply to all boxes<\/h3>\n\n\n\n
We recurse our way through the list of boxes, checking that we obey the hopple rule and the bungo rule for each one:<\/p>\n\n\n\n
all_creatures_ok([], _AllBs).\nall_creatures_ok([X1\/Y1\/C | Bs], AllBs)\n    :- hopple_ok(X1\/Y1\/C, AllBs),\n       bungo_ok(X1\/Y1\/C, AllBs),\n       all_creatures_ok(Bs, AllBs).<\/pre>\n\n\n\n
Counting bungos<\/h2>\n\n\n\n
We create a predicate which is only satisfied for bungos, then find the list of all boxes which satisfy it, and see how long that list is.<\/p>\n\n\n\n
box_has_bungo(_\/_\/b).\ncount_bungos(Bs, N) :- include(box_has_bungo, Bs, BungoBs),\n                       length(BungoBs, N).<\/pre>\n\n\n\n
Output presentation<\/h2>\n\n\n\n
To make it easier to look at the results, extract from each box description X\/Y\/C just the occupying creature type (not the X\/Y location at the start), collecting them into a list.<\/p>\n\n\n\n
box_occupants([], []).\nbox_occupants([_X\/_Y\/C | Bs], [C | Cs]) :- box_occupants(Bs, Cs).<\/pre>\n\n\n\n
Find valid sleeping arrangements<\/h2>\n\n\n\n
Look for a valid sleeping arrangement where the top-left box is a C, and there are N bungos altogether, and the list of occupants is Cs.<\/p>\n\n\n\n
challenge(C, N, Cs) :- Bs = [1\/1\/C, 1\/2\/_, 1\/3\/_,\n                             2\/1\/_, 2\/2\/_, 2\/3\/_,\n                             3\/1\/_, 3\/2\/_, 3\/3\/_],\n                       maplist(box_has_creature, Bs),\n                       count_bungos(Bs, N),\n                       all_creatures_ok(Bs, Bs),\n                       box_occupants(Bs, Cs).<\/pre>\n\n\n\n
Find maximal bungos<\/h2>\n\n\n\n
I’m not so happy with the way I did this, but: we can just try out the possible alternatives in turn for the number of bungos, starting with the case that we can put bungos in all the boxes, and finishing with the case that no boxes contain bungos.<\/p>\n\n\n\n
possible_n_bungos(N) :- member(N, [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]).<\/pre>\n\n\n\n
We then try each possibility in turn, and when it finds the first working one (which will be the biggest), generate all solutions:<\/p>\n\n\n\n
challenge_best_solns(C, N, Cs) :- possible_n_bungos(N),\n                                  challenge(C, N, _)\n                                  ->\n                                  challenge(C, N, Cs).<\/pre>\n\n\n\n
Solving the challenges<\/h2>\n\n\n\n
Now can try it out:<\/p>\n\n\n\n
Challenge 1<\/h3>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
?- challenge_best_solns(h, N, Cs).\nN = 3, Cs = [h, p, b, h, p, p, p, b, b] ;\nN = 3, Cs = [h, p, b, h, p, b, p, p, b] ;\nN = 3, Cs = [h, p, b, h, p, b, p, b, p] ;\nN = 3, Cs = [h, p, b, h, p, b, h, p, b] ;\nN = 3, Cs = [h, h, p, p, p, p, b, b, b] ;\nN = 3, Cs = [h, h, p, p, p, b, b, p, b] ;\nN = 3, Cs = [h, h, p, p, p, b, b, b, p] ;\nN = 3, Cs = [h, h, h, p, p, p, b, b, b] ;\nfalse.\n<\/pre>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Challenge 2<\/h3>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
?- challenge_best_solns(b, N, Cs).\nN = 6, Cs = [b, p, b, p, b, b, b, b, p] ;\nN = 6, Cs = [b, p, b, b, p, b, b, p, b] ;\nN = 6, Cs = [b, p, b, b, b, p, p, b, b] ;\nN = 6, Cs = [b, p, b, b, b, b, p, b, p] ;\nN = 6, Cs = [b, b, p, p, b, b, b, p, b] ;\nN = 6, Cs = [b, b, p, p, b, b, b, b, p] ;\nN = 6, Cs = [b, b, b, p, p, p, b, b, b] ;\nfalse.\n<\/pre>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Challenge 3<\/h3>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
?- challenge_best_solns(p, N, Cs).\nN = 6, Cs = [p, b, p, b, b, b, b, p, b] ;\nN = 6, Cs = [p, b, b, b, b, p, p, b, b] ;\nN = 6, Cs = [p, b, b, b, b, p, b, p, b] ;\nfalse.\n<\/pre>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Prolog is cool<\/h1>\n\n\n\n
No doubt people who actually know Prolog could find better ways of doing this, and would have avoided the several dead-ends I went down while exploring. All the same, I found this puzzle to be a good way of getting a taste of Prolog. It is very pleasing how you can specify the constraints in a fairly natural way, and then as if by magic it produces the solutions.<\/p>\n","protected":false},"excerpt":{"rendered":"
This puzzle was in my daughter’s Dandy: and I thought it would give me an opportunity to experiment with Prolog, which I’d been meaning to do for a while. I used SWI-Prolog. Structure of the puzzle We’ll represent a block of nine boxes as a list. A box is the expression X\/Y\/C, meaning that creature type C occupies location X\/Y, where the top-left box is 1\/1. We’ll have a fragment similar to Bs = [1\/1\/_, 1\/2\/_, 1\/3\/_, 2\/1\/_, 2\/2\/_, 2\/3\/_, 3\/1\/_, 3\/2\/_, 3\/3\/_] Our goal is to find which creature can go in each box. The different types of creature Every box must have a creature in it. box_has_creature(_\/_\/p). box_has_creature(_\/_\/h). box_has_creature(_\/_\/b). We’ll use the variable name ‘Bs’ throughout to mean<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-51","post","type-post","status-publish","format-standard","hentry","category-uncategorized","comments-off"],"_links":{"self":[{"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/51","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=51"}],"version-history":[{"count":3,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/51\/revisions"}],"predecessor-version":[{"id":3762,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/51\/revisions\/3762"}],"wp:attachment":[{"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=51"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=51"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=51"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}