79663267

Date: 2025-06-12 09:43:43
Score: 1
Natty:
Report link

I recognize two separate questions:

  1. How do I enter manually information from a picture/diagram to Prolog code without making mistakes?
  2. How do I represent a labyrinth like this one, if I want to find a (shortest?) path through it?

Prolog has a "de-facto" standard for compile-time code re-writing, using expand_term/2 and term_expansion/2. Those are available at least in SWI-Prolog, GNU-Prolog, and SICStus Prolog.

With this you can transform your valid Prolog source code to other valid Prolog code. This helps because it relieves you (the programmer) from thinking about "how is this information going to be used" while you are still at the stage of just writing down the information (do you see the relation to relational database design?)

For example: I might find it easiest to just write down the doors that I see in the labyrinth. I will just write them down in a list, going by "rows" from top to bottom, and left to right on each imaginary row. I end up with something like this:

doors([
    h-g, g-f,
    h-i, f-k,
    k-e,
    i-j, g-k, e-d,
    j-i, k-d,
    d-c,
    j-b,
    b-a]).

This is already useful for cross-checking, I can count how many doors I have in total or how many roooms/locations I have:

?- doors(Ds), length(Ds, N).
Ds = [h-g, g-f, h-i, f-k, k-e, i-j, g-k, e-d, ... - ...|...],
N = 13.

?- doors(Ds), setof(R, S^( member(R-S, Ds) ; member(S-R, Ds) ), Rooms), length(Rooms, N).
Ds = [h-g, g-f, h-i, f-k, k-e, i-j, g-k, e-d, ... - ...|...],
Rooms = [a, b, c, d, e, f, g, h, i|...],
N = 11.

Both numbers check out, I do count on the picture 13 doors and 10 rooms with a as the 11th outside location.

I can already see that there are two distinct doors between rooms j and i, would going through one or the other be considered a different path? I will leave the door there, but I will model the connections between rooms to be unique. I will not do this by removing the door from my original list though.

The original design of the connections is in fact useful; it models the labyrinth as an undirected graph, where a <--> b is modeled as { a --> b, b --> a }. This very nicely fits with the path/trail/walk definition proposed by @false.

Here is one way to achieve this (full program so far):

term_expansion(doors(Ds), Connections) :-
    findall(connection(A,B),
            (   member(A-B, Ds)
            ;   member(B-A, Ds)
            ), C0),
    sort(C0, Connections).

doors([
    h-g, g-f,
    h-i, f-k,
    k-e,
    i-j, g-k, e-d,
    j-i, k-d,
    d-c,
    j-b,
    b-a]).

You can how check what connections you have going out of rooms i or j (note there is two doors but now only one connection between the two):

?- connection(i, X).
X = h ;
X = j.

?- connection(j, X).
X = b ;
X = i.

Great. Using the path/trail/walk definition I linked above, we get:

?- path(connection, Path, a, e).
Path = [a, b, j, i, h, g, f, k, d, e] ;
Path = [a, b, j, i, h, g, f, k, e] ;
Path = [a, b, j, i, h, g, k, d, e] ;
Path = [a, b, j, i, h, g, k, e] ;
false.

This seems correct. How would you try to search for the shortest path? This is a good question, and the obvious answer is "use another algorithm" (not the one provided by path/4). However, iterative deepening can be used to trivially use path/4 to find the shortest path first.

Reasons:
  • Blacklisted phrase (1): How do I
  • Blacklisted phrase (1): How would you
  • RegEx Blacklisted phrase (1): I want
  • Long answer (-1):
  • Has code block (-0.5):
  • Contains question mark (0.5):
  • High reputation (-1):
Posted by: TA_intern