Looking up shapes in a lists of lists

Question

Program description

1. Aim of the program

My program is meant to calculate locations of shapes in a 20X15 sized plane. I have a list of shapes carrying the shape type, its id, its radius or height, and its prospective [X,Y] location on the plane. I have a different list of binary operations carrying only the shape type, its id, and its location relationship with another shape. With this information in the operations list, I should compute the [X,Y] locations of the shapes: Below is a description of the two lists:

List of shapes

I have a list of shapes: each shape is a list of the form:

[[shape, id],height/radius, [X,Y]]

A list of such shapes would look something like the below when it is printed out by Prolog:

[[[diamond,1],4,[_7948,_7954]],[[circle,3],6,[_7894,_7900]],[[square,1],4,[_7840,_7846]],[[circle,1],5,[_7786,_7792]]|_7800]

List of operations

A list of operations that should be carried out on the shapes each operation is of the form:

[[[circle,1],below,[square,1]]]

This means that circle 1 should appear below square 1 on the X,Y plane

Such a list when printed out by prolog would look something like the following:

[[[circle,1],below,[square,1]]|_8016]

2. The program

So I have computeShapeLocations/2. Its first argument is a list of operations and the second list is a list of shapes. It recursively goes over the list of operations getting the shape ids on both sides of the operation. eg circle 1 - below - sqaure 1 and sends the two shapes to the correct function to calculate the locations using CLPFD. For two shapes with a relative positioning of 'below' I use computeShapesBelow/2 which takes two shapes each of the form [[shape, id],height/radius, [X,Y]].

Steps in ComputeShapeLocations/2: 1. Get an operation of the form [[[circle,1],below,[square,1]]] from the list of operations 2. Fetch first id (circle 1), then type of relationship (below) then second id (square 1). 3. Fetch the shapes from the shapes list (ShapesOut) 4. Send the shapes to computeShapesBelow/2. This just uses clpfd to compare radius or height and the dimensions of my X,Y plane.

:- use_module(library(clpfd)).
computeShapeLocations([],_ShapesOut).
computeShapeLocations([Operation|Rest],ShapesOut) :- writeln(ShapesOut),                                                                             
                                      writeln([Operation|Rest]),                                                                             
                                      nth0(0,Operation,Subject1),                                                                            
                                      nth0(1,Operation,below),                                                                           
                                     nth0(2,Operation,Subject2),                                                                             
                                     Shape1 = [Subject1,H,Loc],                                                                          
                                     Shape2 = [Subject2,H2,Loc2],                                                                        
                                     member(Shape1,ShapesOut),
                                     member(Shape2,ShapesOut),                                                                  
                                     writeln(Shape1),                                                                            
                                     writeln(Shape2),                                                            
                                     writeln(Subject1),                                                                          
                                      writeln(Subject2),
                                     computeShapeBelow(Shape1,Shape2),                                       
                                  computeShapeLocations(Rest,ShapesOut).
computeShapeBelow(Shape1,Shape2) :- nth0(2,Shape1,Location1),                                    
                                    nth0(2,Shape2,Location2),                                                                            
                                    writeln(Shape1),                                                                             
                                    writeln(Shape2),                                                                             
                                   nth0(1,Shape1,Dim1),                                                                          
                                   nth0(1,Shape2,Dim2),                                                                          
                                   nth0(0,Location1,Xcord1),                                                                             
                                   nth0(0,Location2,Xcord2),                                                                          
                                  nth0(1,Location1,Ycord1),                                                                          
                                  nth0(1,Location2,Ycord2),                                                                       
                                  Ycord1 #> Dim1, Ycord1 #< 15-Dim1,                                                                          
                                  Xcord1 #> Dim1, Xcord1 #< 20-Dim1,                                                                          
                                  Ycord2 #> Dim2, Ycord2 #<  15-Dim2,                                                                         
                                  Xcord2 #> Dim2, Xcord2 #<  20-Dim2,                                                                         
                                  Ycord2 #> Ycord1+Dim2+Dim1.

The problem: In computeShapeLocations/2 my lookup is just bizarre( see step three above in steps of computeShapeLocations/2). I use member(ShapeId, ListOFshapesList) to fetch shapes from listofshapes given their ids [shape,id]. I then print out the results( writeln(Shape1), writeln(Shape2))and the image below shows just how the behavior is wrong. For the first shape (circle,1), the result is good and computeShapesBelow/2 even comes up with a proper limit of its X,Y location (6..14 and 6..9). For the second shape (Shape2 or square 1). It does not behave as expected and the clpfd limits result in lower infinities.

The reason is because this second search of [square,1] ignores an entry of [[square, 1], 4, [_2166, _2172]] which is in the list and instead somehow adds an extra [[square, 1], _2250, [_2262|...]] which it then uses to mess up my results.

Answer 1

In my opinion, the source of your problem is being obscured by two simple problems. I don't have all your code and I don't really know what you're trying to do, so I'll just talk about what I see and how I would proceed.

The first problem is that you are not making effective use of unification. For instance, you can replace this:

nth0(0,Operation,Subject1),
nth0(1,Operation,below),
nth0(2,Operation,Subject2),

With this:

[Subject1,below,Subject2] = Operation,

But, moreover, you don't really need Operation on its own, so you can move that into the head of your clause:

computeShapeLocations([[Subject1,below,Subject2]|Rest],ShapesOut) :-

As you start to make these changes your code will contract quite a bit and it should become a lot easier to see what is going on. What would make it even easier to understand would be using less listy representations. For instance, it's a little easier for me to understand what is going on in this command list:

[below(circle(1), square(1)), below(circle(2), square(1)), ...]

or even this, which you can do by adding an :- op declaration:

[circle(1) below square(1), circle(2) below square(1), ...]

and then your pattern matches will look even simpler, like:

compute(Shape1 below Shape2) :- ...

Similarly, for your shapes, it would be a little easier to understand what is going on if you have a little more structure:

shape(circle(1), 4, X@Y)

is a little more obvious to me than

[[circle,1], 4, [X,Y]]

I find it a little odd that you've got unbound variables inside your input list. I gather you're hoping they'll obtain values later on. I suppose there's nothing wrong with this approach, I'm just surprised to see a mixture of ground and nonground acting as inputs.

Your second source of trouble is that you're mixing several kinds of procedure together. I'm pretty sure you have a DCG parsing step going on somewhere. By parsing into this weak, listy representation in there, you're forcing yourself to do more work inside these methods destructuring your lists and obtaining their meaning. Consider:

command([Shape1,below,Shape2]) --> shape(Shape1), "below", shape(Shape2).

versus

command(Shape1 below Shape2) --> shape(Shape1), "below", shape(2).

Or,

shape_type(circle) --> "circle".  shape_type(square) --> "square".
shape_name(shape(Name, Size, X@Y)) --> 
    shape_type(T), integer(ID), 
    integer(Size), 
    integer(X), integer(Y), 
    { Name =.. [T, ID] }.

versus whatever you have now.

IOW, you could create structure during the parse that will simplify your life during the processing. Similarly, doing a lot of what looks to me like debug I/O is making your processing more complex.

find_shape(ShapeId, Shapes, Shape) :-
    Shape = shape(ShapeId, _, _),
    member(Shape, Shapes).

computeShapeLocations([], _).
computeShapeLocations([ShapeId1 below ShapeId2|Rest], Shapes) :-
    find_shape(ShapeId1, Shapes, Shape1),
    find_shape(ShapeId2, Shapes, Shape2),
    computeShapeBelow(Shape1, Shape2),
    computeShapeLocations(Rest, Shapes).

computeShapeBelow(shape(_, D1, X1@Y1), shape(_, D2, X2@Y2)) :-
    Y1 #> D1, Y1 #< 15 - D1,
    X1 #> D1, X1 #< 20 - D1,
    Y2 #> D2, Y2 #< 15 - D2,
    X2 #> D2, X2 #< 20 - D2,
    Y2 #> Y1 + D2 + D1.

I think if I were staring at this I would find it a bit easier to debug.