A TADS3/adv3 module providing several basic data types/data structures

[jbg]

One of the things I’ve been struggling with is the fact that dependency management is kinda kludgy in TADS3, so there’s some balance between “this would be cleaner if it was in its own module” versus “putting it in its own module means dealing with ugly hacks like header guard-based checks throwing errors and constantly tweaking makefiles”.

Anyway, a couple minor updates:

• Graph.testVertices(fn)

  Returns boolean true if the test function fn returns boolean true for each vertex.

• Rectangle.offset()

  Fixed a sign bug that occured when corners were on opposite sides of the origin.

• RTree.insert()

  Fixed a bug in node splitting that would sometimes incorrectly expand the bounding box to include the origin. Resolving this improves performance substantially in cases where it occurred (basically parts of the tree could effectively collapsed into a linked list that needed to be checked sequentially because bounding boxes could end up overlapping in slightly nonsensical ways). But not enough for me to change my earlier comments about QuadTree performing better for most “IF game” use cases.

All of this out of additional procgen map stuff I’m still working on. Which leads me to ask: is there anyone else out there working on something where they’d want procgen map generation (specifically in IF, more specifically in TADS3)? If so, what’s the actual design use case? I’m at the point where I’ve implemented most of the nuts and bolts I care about for the WIP, but I’m still going back and forth on what level of detail “should be” in individual per-game instances and how much “generic use case” logic should be built into the generators themselves.

Like right now my model is that the default generator generates nothing, and in a game you create instances of the relevant classes to write bespoke methods to declare, for example, if you’re picking between three options how you want the choice to be made (with no default behavior). If that makes sense.

[jbg]

A few more updates.

LineSegment

A new class implementing, as the name suggests, line segments.

A line segment is defined by two XY instances, which are the arguments for the class constructor.

Methods

• contains(xy)

  Returns boolean true if the given XY instance lies on the calling line segment.

• equals(ls)

  Returns boolean true if the given LineSegment instance has the same endpoints as the calling instance.

• coincident(ls)

  Returns boolean true if the given LineSegment shares exactly one endpoint with the calling instance.

• intersects(ls, ignoreEndpoints?)

  Returns boolean true if the given LineSegment intersects the calling instance. If the second argument is boolean true then intersections that occur only at one endpoint don’t count.

Matrix

A couple new methods:

• multiply(m)

  Multiplies the calling Matrix instance by the argument instance, returning a new Matrix instance containing the product.

• clone()

  Returns a copy of the calling matrix.

Graph

Updated adjacencyMatrix() to optionally take a list of vertex IDs as its argument. By default the adjacency matrix is constructed using a vertex list in ASCIIbetical order by vertex ID. Called with an argument it will be used for the vertex order instead.

XY

• isAdjacentToAll(lst)

  Like isAdjacent(), but accepts a list of XY instances and returns boolean true if each element of the list is adjacent (in the Moore neighborhood of) the calling XY instance.

All of these are bits of code being backported out of the procgen map code I’m working on.

Still on the fence about pulling the subgraph isomorphism stuff out too. On the one hand it’s more general than just the procgen stuff I’m using it for, but on the other hand it’s larger than everything in the base Graph implementation (including Vertex and Edge and the Dijkstra pathfinding stuff) put together. And although it’s generic graph theory stuff, I’m a little skeptical that there’s that much need for a subgraph isomorphism solver in general IF programming. Witness: TADS3 having managed to reach 2025 without a prior implementation (as far as I know).

[jbg]

A couple more minor updates.

TSProf

This is a class that uses the TS class to aid in the implementation of rudimentary performance profilers.

Properties

• label = 'tsProf'

  Label for output. Only used in the report() method.

Methods

• start(id)

  Starts a timer associated with the ID id.

• stop(id)

  Stops the timer associated with the ID id, if one exists.

• total(id)

  Returns the cumulative time elapsed for the timer id.

• report()

  Prints a list of all the timer IDs and their elapsed times.

The entire class is wrapped in a preprocessor conditional for _DEBUG, so it’ll only be compiled in for debugging builds.

The way I’m using this is:

• Create an instance, in this example __pgProf (for the procgen stuff I’m working on)
• Assign a unique-ish ID for each object, in this case syslogID
• Include a bunch of #define statements in a preprocessor conditional that checks for a compile-time flag. If set, the defines are:

#define pgProfStart(v) __pgProf.start(syslogID + '.' + v + '()')
#define pgProfStop(v) __pgProf.stop(syslogID + '.' + v + '()')
#define pgProfTotal(v) __pgProf.total(syslogID + '.' + v + '()')
#define pgProfReport() __pgProf.report()

…and if not, they are…

#define pgProfStart(v)
#define pgProfStop(v)
#define pgProfTotal(v) 0
#define pgProfReport()

Then in methods I’m trying to profile I call pgProfStart('someMethodName') at the start and pgProfStop('someMethodName') before any return.

Then at any point calling pgProfReport() will output a list of all the methods I’ve done this for and their cumulative execution time, labelled with the object/class name and method name, something like:

=====pgProf START=====
PermuteBt.accept(): .005
GraphGrid.placeNeighbors(): .014
GraphGrid.insertNext(): .002
=====pgProf END=====

Compiling without the preprocessor flag turns all the macros into NOPs, so they’re not even as expensive at runtime as a call to a method that immediately returns.

Dunno how many other TADS3 authors are doing things…messy…enough to require this kind of profiling, but if you are, here it is.

[jbg]

Another utility class/type.

BT

The BT class and its support classes provide a simple, fairly generic recursive backtracker. It’s intended to allow you to rewrite tail recursion logic to use an iterative, resumable solver instead.

Methods

• pop()

  Pops the top frame off the stack and returns it.

• push(f)

  Pushes the frame f onto the top of the stack.

• reject(f)

  Rejection method. This should return boolean true if the frame f and any frames derived from it should be rejected.

  Subclasses will want to implement their own logic here. The stock method only fails on invalid frames.

  Returning true from this method means “stop trying this solution, it will never work”. It does NOT just mean “this frame is invalid” (although an invalid frame is one of the possible failure modes)

• accept(f)

  Acceptance method. This should return boolean true if the frame f is a valid solution to the problem being solved.

  Subclasses will want to implement their own logic. The stock method just checks to see if a value is assigned to each variable being solved for.

  Returning true from this method means “stop processing, you’ve found the answer”.

• next(f)

  Returns the next frame following frame f.

  By default this will just be the next permutation of the variable/value assignments.

• step(f)

  Advances processing a single step starting from frame f.

  Returns boolean true if the next step yielded a solution, placing the solution itself at the top of the stack; boolean nil if the next step was rejected (that is, resulted in a permanent failure for the branch being explored); and the next frame if the step resulted in neither a solution nor a failure.

• run(f)

  Step through frames starting with frame f, continuing until either a frame is accepted (that is, a solution is found) or rejected (that is, no further solutions are available from the starting frame).

BTStack

Stack for the recursive backtracker. This generally won’t need to be interacted with directly unless you’re wrting a subclass of BT with a bunch of problem-specific logic.

Methods

• clear()

  Clears the stack.

• push(f)

  Pushes the frame f onto the top of the stack

• pop()

  Pops the top frame off the stack and returns it.

• validateFrame(f)

  Returns boolean true if f is a valid frame for this stack.

BTFrame

Stack frame for the recursive backtracker.

Properties

• vList = nil

  List of variables we’re trying to assign values to.

• pList = nil

  List of possible values to assign to the variables.

• result = nil

  List of assignments so far.

  NOTE: The indices in result correspond to indicies in vList. That is, the ith value of result is a possible assignment for the ith variable in vList. The values in result correspond to indices in pList. That is, they aren’t the values being assigned they’re the index of a value in pList.

Methods

• clone()

  Returns a copy of this frame.

• next()

  Returns the frame that follows this one. The stock class proceeds by simple permutation.

Explanation

This all might sound a little arcane if you’re not already familiar with the concepts, so here’s a simple, concrete example.

Let’s say we have three people, Alice, Bob, and Carol, and we’re having a very odd dinner party in which each person is given exactly one vegetable and no two people receive the same vegetable. The vegetables we have are asparagus, broccoli, carrots, and daikon.

We have the additional constraint that, for reasons not worth getting into here, Bob refuses to accept any vegetable whose name starts with B. So he can’t be assigned broccoli.

We could just assign permutations via tail recursion: we write a function that assigns the next available vegetable to the next person without a vegetable, and then call the function again recursively until we have assignments for each person.

The problem wth this method is what if we want to do the same thing tomorrow and don’t want to ever repeat the same assignments (until we run out of possible assignments)? We could solve this by keeping track of all past menu assignments, but then that gets out of hand in a hurry and we still end up having to iterate through the entire process every day (so the nth day will be faster than the n + 1th day, and so on…because each successive day we have to recurse deeper to find an unused solution).

Instead of doing that we can use a recursive backtracker. It uses just the most recent state to figure out how to proceed, and is guaranteed to cover every valid permuations.

To use the BT class to solve this problem we start out by defining our lists somewhere where we can refer to them:

veg = static [ 'asparagus', 'broccoli', 'carrots', 'daikon' ]
people = static [ 'Alice', 'Bob', 'Carol' ]

Now we declare an instance of BT and give it an accept() method that provides our novel constraint involving Bob’s preferences.

demoBacktracker: BT
        accept(frm) {
                if(!inherited(frm))
                        return(nil);

                return(frm.result[2] != 2);
        }
;

What’s going on here? The inherited() check just verifies that every variable has an assignment. That is, we’re only interested (here) in solutions in which each person is assigned a vegetable.

The frm.result[2] == 2 implements Bob’s dietary restrictions. The way to read this is that indices in the frame’s result vector (result) correspond to indices in the variable vector (BTFrame.vList). In our case the second element of vList will be Bob, so result[2] is “what is assigned to Bob”. The values in the result vector are indices in the value list. And in this case the second value is “broccoli”.

If we wanted to implment an actual alphabetic check (that is, if there were multiple vegetables that start with B and we want to exclude them all) we could perform the test on frm.pList[frm.result[2]].

To invoke the solver we create a BTFrame instance representing the problem we want it to solve:

f = new BTFrame(people, veg, nil);

That is, we want to come up with assignments for everyone in people using values from veg, and our current state (the third arg) is nil…we haven’t done any work yet.

We can then call the backtracker instance we created: with demoBacktracker.run(f). This will run until it finds a solution or runs out of things to try, returning true on success and nil on failure.

On success, the top of the backtracker’s stack will contain a stack frame containing a solution to the problem.

We can iterate over all of them with something like:

                while(f != nil) {
                        if(demoBacktracker.run(f) != nil) {
                                f = demoBacktracker.pop();

                                printFrame(f);

                                f = demoBacktracker.next(f);
                        }
                }

…where we’ve declared a printFrame() function elsewhere to display each result:

        printFrame(f) {
                local ar, i;

                ar = new Vector(f.result.length);
                for(i = 1; i <= f.result.length; i++)
                        ar.append('<<f.vList[i]>> has
                                <<f.pList[f.result[i]]>>');

                "<<stringLister.makeSimpleList(ar)>>.\n ";
        }

Running this gives us:

Alice has asparagus, Bob has carrots, and Carol has broccoli.
Alice has asparagus, Bob has carrots, and Carol has daikon.
Alice has asparagus, Bob has daikon, and Carol has broccoli.
Alice has asparagus, Bob has daikon, and Carol has carrots.
Alice has broccoli, Bob has asparagus, and Carol has carrots.
Alice has broccoli, Bob has asparagus, and Carol has daikon.
Alice has broccoli, Bob has carrots, and Carol has asparagus.
Alice has broccoli, Bob has carrots, and Carol has daikon.
Alice has broccoli, Bob has daikon, and Carol has asparagus.
Alice has broccoli, Bob has daikon, and Carol has carrots.
Alice has carrots, Bob has asparagus, and Carol has broccoli.
Alice has carrots, Bob has asparagus, and Carol has daikon.
Alice has carrots, Bob has daikon, and Carol has asparagus.
Alice has carrots, Bob has daikon, and Carol has broccoli.
Alice has daikon, Bob has asparagus, and Carol has broccoli.
Alice has daikon, Bob has asparagus, and Carol has carrots.
Alice has daikon, Bob has carrots, and Carol has asparagus.
Alice has daikon, Bob has carrots, and Carol has broccoli.

…which is all the possible assignments that satisfy our requirements.

If we’re just doing this…just enumerating all the possibilities…we could “just” compute the permutations. The thing that the recursive backtracker gives us is the ability to compute one solution and the at some later time if we want to continue the process where we left off, all we have to have is the last frame (which is just the two lists and the result vector), and we never have to iterate over any possibilities we’ve previously considered.

Here’s the complete code for the example problem with additional comments, now also demo/src/btTest.t in the dataTypes repo.

#charset "us-ascii"
//
// btTest.t
// Version 1.0
// Copyright 2022 Diegesis & Mimesis
//
// Test of the recursive backtracker.
//
// It can be compiled via the included makefile with
//
//      # t3make -f btTest.t3m
//
// ...or the equivalent, depending on what TADS development environment
// you're using.
//
// This "game" is distributed under the MIT License, see LICENSE.txt
// for details.
//
#include <adv3.h>
#include <en_us.h>

#include "dataTypes.h"

// Backtracker instance.  This is where we implement our instance-specific
// logic.
demoBacktracker: BT
        accept(frm) {
                // Generic test, which just makes sure there's an assignment
                // for each variable.
                if(!inherited(frm))
                        return(nil);

                // Bob rejects vegetables starting with B.
                // The *indices* in the result vector as the same as the
                // indices in the variable vector (vList).  So result[2]
                // means "the value assigned to the second variable",
                // and in this case the second variable is Bob.
                // The *values* of the result vector are indices in
                // the value vector (pList).  So result[2] = 2 means
                // we're a) checking the value assigned to Bob (that's
                // the lefthand side), and b) if the value is the second
                // one in the value vector, in this case "broccoli".
                // So this rule means that we're rejecting a result only
                // if it involves givving broccoli to Bob.
                return(frm.result[2] != 2);
        }
;

versionInfo: GameID;
gameMain: GameMainDef
        veg = static [ 'asparagus', 'broccoli', 'carrots', 'daikon' ]
        people = static [ 'Alice', 'Bob', 'Carol' ]

        newGame() {
                local f;

                // Create the initial query:  list of variables to
                // assign, list of possible assignments, and progress so
                // far.
                f = new BTFrame(people, veg, nil);

                // Contine as long as we have another frame to process.
                while(f != nil) {
                        // The return value of BT.run() is true if the
                        // backtracker found a solution, nil otherwise.
                        if(demoBacktracker.run(f) != nil) {
                                // If the return value from .run() was
                                // true, the solution it found will be
                                // the top of the stack.  Here we lift
                                // it off the stack.
                                f = demoBacktracker.pop();

                                // Print the contents of the frame.
                                printFrame(f);

                                // Pick the next frame in the sequence
                                // and continue.
                                f = demoBacktracker.next(f);
                        }
                }
        }

        // Print a single stack frame.
        printFrame(f) {
                local ar, i;

                // Make an array containing the assignments.
                // Note that the result vector, here f.result,
                // contains the *indices*, in f.pList, of the
                // assignments, NOT the values themselves.
                ar = new Vector(f.result.length);
                for(i = 1; i <= f.result.length; i++)
                        ar.append('<<f.vList[i]>> has
                                <<f.pList[f.result[i]]>>');

                // Have the string lister format the array.
                "<<stringLister.makeSimpleList(ar)>>.\n ";
        }
;

[jbg]

A few additions to the Graph class.

Graph

Methods

• clone()

  Returns a shallow copy of the calling graph.

  This creates a new Graph instance containing the same vertices and edges as the calling graph. It does not copy any data defined on the vertices or edges.

• difference(g)

  Returns a new Graph instance containg the difference of the calling graph and the argument graph. That is, a graph containing the vertices and edges that are in the calling graph that are not in the argument graph.

• equals(g)

  Returns boolean true if the argument graph equals the calling graph. That is, they both contain the same vertices and edges.

• intersection(g)

  Returns a new Graph instance containing the intersection of the calling graph and the argument graph. That is, a graph containing the vertices and edges that are in both graphs.

• union(g)

  Returns a new Graph instance containing the union of the calling graph and the argument graph. That is, all vertices and edges that are in either of the two graphs.

In the above methods, comparisons are made using vertex and edge IDs rather than instances.

This is probably more abstract than anything most people will need for most games, but I’ve been using a lot of graph theory stuff in my procgen code and it vaguely seems like the kind of thing that wants to live in the Graph class.

[jbg]

More graph theory stuff.

Graph

• isRegular()

  Returns boolean true if the degree of all vertices in the graph is the same.

• maximumDegree()

  Returns the degree of the vertex with the most edges.

• minimumDegree()

  Returns the degree of the vertex with the fewest edges.

Also added a simple implementation of disjoint-set/union-find operations:

DisjointSetForest

A simple container class for a forest containing multiple DisjointSet objects. Purely for convenience.

Methods

• add(v)

  Adds a DisjointSet instance to the forest.

• forEachSet(fn)

  Iterates over each DisjointSet instance in the forest, calling the argument function fn on each.

DisjointSet

An abstract disjoint-set data structure. This is used for efficient lookups of whether two given nodes (e.g. vertices in a graph) are connected.

The expected usage is that the parent and rank will be automagically computed by the module when an instance is used in find() and union() calls.

Properties

• id = nil

  Arbitrary ID for the element. Should only be set by the constructor.

• parent = nil

  Parent of the element. Should not be set directly.

• rank = 0

  Rank of the element. Should not be set directly.

Methods

• add(v)

  Initialize the DisjointSet instance, setting its parent to be itself and its rank to be zero.

  This is called automagically by the constructor, and generally shouldn’t be manually invoked.

• find(v)

  Returns the DisjointSet instance that is the top-level parent of the argument, which can be either a DisjointSet instance or the ID of a declared DisjointSet instance.

• getDisjointSet(id)

  Returns the DisjointSet instance with the given ID.

• union(v0, v1)

  Joins the two argument disjoint sets. The arguments can be either DisjointSet instances or IDs.

Example usage:

     // Create a forest to hold the disjoint sets
     local f = new DisjointSetForest();

     // Add elements "foo", "bar", and "baz" to the forest
     makeDisjointSet('foo', f);
     makeDisjointSet('bar', f);
     makeDisjointSet('baz', f);
     makeDisjointSet('quux', f);

     // Join "foo" and "bar"
     disjointSetUnion('foo', 'bar');
     // Join "foo" and "baz"
     disjointSetUnion('foo', 'baz');
     // Join "baz" and "quux"
     disjointSetUnion('baz', 'quux');

     // Sets p to be the top-level parent of "quux", which will be
     // the DisjointSet instance "bar".
     local p = disjointSetFind('quux');

I already have some code that’ll probably go on DisjointSetForest that converts a Graph into disjoint-set data and then uses Kruskal’s algorithm to compute a minimum spanning tree, but I haven’t cleaned it up yet.

Just trying to get back in the habit of doing regular updates/releases instead of going down recursive refactoring bunny trails while working on this kind of stuff.

All of this is coming out of procgen puzzle generation stuff I’m working on, where I want to be able to give a puzzle specification that grows “automatically” via the procgen logic, from the initial game state (where the player has unlocked nothing) to the endgame state (where everything is potentially unlocked) without having to hard-code breakpoints for each transition in the internal game state.

As a side-note, I’ll add that I’m back to using RTree for the spatial indexing for procgen map layout; up above I commented that I’d switch to QuadTree after doing performance testing. I thought it was surprising that QuadTree was performing better than RTree, and it turns out that it must’ve been an artifact of the test method or something, because in “real” game maps RTree has been performing substantially better.

[jbg]

New methods and a tweak to the usage of the stuff I just posted.

First, the new methods:

DisjointSetForest

Methods

• graphToForest(g)

  Uses the argument Graph instance to configure the forest, adding nodes for each Vertex in the graph and doing a union() for each edge.

  NOTE: This does not clear the forest beforehand. So if the the contents of the graph are all you want in the forest you’ll have to make sure the forest is empty yourself.

• kruskal(g, fn?)

  Returns a new Graph instance containing a minimum spanning tree of the argument g (which must be a Graph instance) computed using Kruskal’s algorithm.

  The optional second argument is an edge sorting function. If given, the function must accept two Edge instances as arguments and return an integer as per normal TADS3 sort() semantics. If no function is given the edge lengths will be used to sort edges.

  NOTE: This method modifies the forest. New nodes will be added for each vertex in the graph, and union()s will be performed for each edge. This also means that any disjoint-sets already in the forest when kruskal() is invoked will be part of the computed spanning tree. If these things are not desired, a new DisjointSetForest instance should be created before calling this method.

Moved methods

In addition to the above, almost all of the methods previously on DisjointSet are now on DisjointSetForest, and the global macros for doing disjoint-set operations have been removed. This is basically just to force the “namespace” of node IDs to be local to each individual forest.

This is basically just cleanup. The code started out as part of the procgen stuff I’m working on, which has a way of generating globally-unique IDs, so ID collisions weren’t really something I had to worry about. But breaking the disjoint-set logic out to be a standalone thing makes IDs having to be globally unique an obvious weakness. So I re-wrote it this way.

Anyway, the new basic semantics are identical to the example in my previous post, but the exact usage has changes a little:

     // Create a forest to hold the disjoint sets
     local f = new DisjointSetForest();

     // Add elements "foo", "bar", and "baz" to the forest
     f.makeSet('foo');
     f.makeSet('bar');
     f.makeSet('baz');
     f.makeSet('quux');

     // Join "foo" and "bar"
     f.union('foo', 'bar');
     // Join "foo" and "baz"
     f.union('foo', 'baz');
     // Join "baz" and "quux"
     f.union('baz', 'quux');

     // Sets p to be the top-level parent of "quux", which will be
     // a DisjointSet instance.
     local p = f.find('quux');

This is all just a) methods moving from DisjointSet to DisjointSetForest, and b) calling the method on an instance instead of using a macro to call it statically on the class.

[jbg]

A few more tweaks.

Vector

General

In module-provided methods on Vector, whenever elements need to be tested for equality the elements will be checked for a equals() method. If one is found, it will be called (via someElement.equals(otherElement)) and the two elements will be considered equal if the method returns boolean true.

If no equals() method is defined on a checked instance, basic equality (someElement == otherElement) will be used instead.

Methods that use this are Vector.union(), Vector.intersection(), Vector.complement(), Vector.isSubsetOf(), and Vector.equals().

This is to (hopefully) make the set-theoretic methods a little more useful for vectors containing bespoke data types instead of things like integers…which always want to be compared by value…and simulation objects…which almost always want to be compared for strict equality.

Methods

• isSubsetOf(v)

  Returns boolean true if the argument v, which must be an instance of Vector, contains each element of the calling vector.

• symmetricDifference(v)

  Returns a new Vector containing all the elements which are in exactly one of the two vectors (the argument vector v or the calling vector). That is, elements that are in one but not both.

Overloaded Operators

Several classes now overload some operators:

IntegerMatrix

• *

  If m is a IntegerMatrix instance and n is an integer, then m * n is equivalent to m.multiply(n).

Vector

• >> and <<

  If v is an instance of Vector and n is an integer, then v >> n is equivalent to v.rotateRight(n) and v << n is equivalent to v.rotateLeft(n).

XY

• +, -, *, /

  If x0 and x1 are instances of XY and n is an integer, then:

  • x0 + x1 is equivalent to x0.add(x1)
  • x0 - x1 is equivalent to x0.subtract(x1)
  • x0 * n is equivalent to x0.multiply(n)
  • x0 / n is equivalent to x0.divide(n)

Almost all usability stuff/API chrome.

[jbg]

Bump for another update.

AC3

The AC3 class provides an implementation of the Arc Consistency Algorithm #3, or AC-3, an algorithm for solving constraint satisfaction problems.

That is, given some number of variables with an allowed set of values and constraints on the relationships between values, figure out a) if there are any valid solutions, and b) if so, find them.

For example (borrowing from the wiki article on the algorithm), let’s say we have two integer variables, x and y, where 0 ≤ x ≤ 5 and 0 ≤ y ≤ 9, and we want to find all possible values of x and y that satisfy:

• x is even
• x + y = 4

Basic Usage

Create an instance:

    local g = new AC3();

Now declare the variables and their domains (the list of allowed values) with:

    // Define the variables and their domains
    g.addVariable('x', [ 0, 1, 2, 3, 4, 5 ]);
    g.addVariable('y', [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]);

Note: the variable IDs are arbitrary identifiers for the AC-3 logic to use internally. No corresponding TADS3 variables are created in the global namespace.

Now we define the constraints:

    // 'x' must be even
    g.addConstraint('x', { x: !(x % 2) });

    // x and y must satisfy x + y = 4
    g.addConstraint('x', 'y', { x, y: ((x + y) == 4) });

Note: in these examples I’m using variable names in the inline functions that correspond to the variable IDs, but this is just for clarity. g.addConstraint('x', 'y', { a, b: ((a + b) == 4) }) would work exactly the same.

Also note that you can call addConstraint() with two or three arguments for unary (single variable) or binary (two variable) constraints.

Having defined the variables and constraints you can now call g.solve(). This will return boolean true if the constraint satisfaction problem is solvable. You can iterate over all the variables with g.forEachVariable() and each instance’s domain will have been updated.

This by itself doesn’t give you the valid solutions. If you want them you can call g.getSolutions(). This will call solve() (so you don’t have to do that beforehand if all you care about is the solutions) and return an array. Each element will be a valid solution to the CSP, in the form of a LookupTable whose key-value pairs correspond to the variable assignments for that solution. In our example:

     local l = g.getSolutions();

…would result in l containing…

    [
        [ 'x' -> 0, 'y' -> 4 ],
        [ 'x' -> 2, 'y' -> 2 ],
        [ 'x' -> 4, 'y' -> 0 ]
    ]

That is, the solutions { x = 0, y = 4 }, { x= 2, y = 2 }, and { x = 4, y = 0 }.

Note

Note that although this example uses numeric values they don’t have to be. To revisit the dinner party vegetable assignment problem discussed in the BT documentation above, let’s say we have three guests, Alice, Bob, and Carol. There are four vegetables, asparagus, broccoli, carrots, and daikon. Alice and Carol will eat any vegetable but Bob still won’t abide broccoli. Additionally, Alice and Bob want to have the same thing, and Alice and Carol refuse to eat the same thing.

We get all possible meal assignments as:

                local g, l, str;

                g = new AC3();

                l = [ 'asparagus', 'broccoli', 'carrots', 'daikon' ];

                // Alice likes all the vegetables.
                g.addVariable('Alice', new Vector(l));

                // Bob can't handle broccoli.
                g.addVariable('Bob',
                        new Vector(l).subset({ x: x != 'broccoli' }));

                // Carol also likes all vegetables.
                g.addVariable('Carol', new Vector(l));

                // Alice and Bob want to have the same thing.
                g.addConstraint('Alice', 'Bob', { a, b: a == b });

                // Alice and Carol never have the same thing.
                g.addConstraint('Alice', 'Carol', { a, b: a != b });

                local r = g.getSolutions();
                if(r == nil) {
                        "\nERROR:  no solution\n ";
                        return;
                }
                str = new StringBuffer();
                r.forEach(function(x) {
                        x.forEachAssoc({ k, v: str.append('<<toString(k)>> has
                                <<toString(v)>>. ') });
                        str.append('\n');
                });
                "\n<<toString(str)>>\n ";

The output:

Alice has asparagus.  Bob has asparagus.  Carol has broccoli.
Alice has asparagus.  Bob has asparagus.  Carol has carrots.
Alice has asparagus.  Bob has asparagus.  Carol has daikon.
Alice has carrots.  Bob has carrots.  Carol has asparagus.
Alice has carrots.  Bob has carrots.  Carol has broccoli.
Alice has carrots.  Bob has carrots.  Carol has daikon.
Alice has daikon.  Bob has daikon.  Carol has asparagus.
Alice has daikon.  Bob has daikon.  Carol has broccoli.
Alice has daikon.  Bob has daikon.  Carol has carrots.

[Tomas]

This is a great addition! Good work!

[jjmcc]

At some point, you are no longer working on an entertainment, but on our new ruling roboligarchy.

[jbg]

At some point I am hopefully formerly working on it because it’s done.

That day is not today. Here’s a minor-ish extension to the AC-3 class that’s specifically for solving zebra puzzles. I split it into its own repo: zebraPuzzle github repo.

Zebra Puzzles

The original zebra puzzle (or at least the one that gives the genre that name) is:

1. There are five houses.
2. The Englishman lives in the red house.
3. The Spaniard owns the dog.
4. Coffee is drunk in the green house.
5. The Ukrainian drinks tea.
6. The green house is immediately to the right of the ivory house.
7. The Old Gold smoker owns snails.
8. Kools are smoked in the yellow house.
9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house.
11. The man who smokes Chesterfields lives in the house next to the man with the fox.
12. Kools are smoked in the house next to the house where the horse is kept.
13. The Lucky Strike smoker drinks orange juice.
14. The Japanese smokes Parliaments.
15. The Norwegian lives next to the blue house.

Now, who drinks water? Who owns the zebra?

The ZebraPuzzle Class

Most of the logic used by the ZebraPuzzle class is the same as the AC3 class. The main additions/modifications are:

• The assumption that each variable must be assigned to exactly one item. That is, there are five houses and five colors, with each house being a different color. No colors re-used, no colors un-used.

  This means that in addition to the explicit constraints that are added based on the lines in the problem statement, there are a bunch of implicit constraints.

• There is exactly one solution. This means that instead of the BT backtracker we can use a much simpler tail recursion method for backtracking.

• The constraints are all of a couple of basic types. This is almost all semantic sugar…you can still declare arbitrary constraints using your own callback functions, but we’ll also have a simpler syntax to handle the most common constraints (which are almost all of the form “the [something] is the [something else]”. That is, saying that red house is also the house with the guy from England, and so on.

Modelling the problem

Under the hood the class is creating a vertex for each variable and an edge for each constraint.

Each vertex contains the domain of the variable it corresponds to. All of these start out as a list of all the possible item assignments. In our example there are five houses, so each variable starts out with a domain of [ 1, 2, 3, 4, 5 ]. That is, each variable could be assigned to any item: ‘red’ could be assigned to house #1, house #2, house #3, house #4, or house #5.

As constraints are applied, the domain of each variable is reduced. The ninth statement (“Milk is drunk in the middle house.”) reduces the domain of the “milk” variable to be [ 3 ]. Because no other drink can also be house #3, that means, for example, the domain for “coffee” can immediately be reduced to [ 1, 2, 4, 5 ].

Since each house must have at least one variable from each vertex group (it must have a color, for example), any time a house number appears in only one domain in a vertex group that solves that variable and any other elements in its domain can be removed (possibly causing some other variable to become a singleton as a result).

I’m not going to go through all the logic (unless someone wants a more complete discription). Just explaining the basics of how the problem is represented under the hood.

Declaring The Problem

To solve the problem, convert the problem statement into a ZebraPuzzleConfig instance:

zebraConfig: ZebraPuzzleConfig
        variables = [
                'color' ->
                        [ 'red', 'green', 'ivory', 'yellow', 'blue' ],
                'country' ->
                        [ 'England', 'Spain', 'Ukraine', 'Norway', 'Japan' ],
                'drink' ->
                        [ 'coffee', 'tea', 'milk', 'orange juice', 'water' ],
                'brand' ->
                        [ 'Old Gold', 'Kool', 'Chesterfield', 'Lucky Strike',
                                'Parliament' ],
                'pet' ->
                        [ 'dog', 'snails', 'fox', 'horse', 'zebra' ]
        ]

        constraints = [
                [ 'England', 'red' ],
                [ 'Spain', 'dog' ],
                [ 'coffee', 'green' ],
                [ 'Ukraine', 'tea' ],
                [ 'green', 'ivory', { a, b: a == b + 1 } ],
                [ 'Old Gold', 'snails' ],
                [ 'Kool', 'yellow' ],
                [ 'milk', 3 ],
                [ 'Norway', 1 ],
                [ 'Chesterfield', 'fox', { a, b: abs(a - b) == 1 } ],
                [ 'Kool', 'horse', { a, b: abs(a - b) == 1 } ],
                [ 'Lucky Strike', 'orange juice' ],
                [ 'Japan', 'Parliament' ],
                [ 'Norway', 'blue', { a, b: abs(a - b) == 1 } ]
        ]
;

The variables declaration is an inline LookupTable whose keys are each an ID for a vertex group (color, pet, and so on) and whose values are lists of the properties in that group (“color” is “red”, “green”, “ivory”, and so on). The vertex group ID is arbitrary but needs to be consistent.

The constraints declaration is a list of constraints in one of two forms. The constraint:

    [ `England`, 'red' ]

represents the second statement. It means “the house the person from England lives in is the same number as the house which is red”.

The constraint:

        [ 'green', 'ivory', { a, b: a == b + 1 } ],

represents the sixth statement. It means “the number of the green house is the number of the ivory house plus one”. The function can be anything but must take two arguments, the numbers of the two houses.

Having created the config, it can be used to create a ZebraPuzzle instance:

     local g = new ZebraPuzzle(zebraPuzzleConfig);

The solve() method can be called to attempt to solve the puzzle. It will return a ZebraPuzzleSolution instance on success, or nil on failure.

    // Attempt to solve the puzzle.
    local r = g.solve();

    // Check the return value.
    if(r == nil)
        return(nil);

    // Output the solution.
    r.log();

This will output something like

Item 1:
   color: yellow
   country: Norway
   drink: water
   brand: Kool
   pet: fox
Item 2:
   color: blue
   country: Ukraine
   drink: tea
   brand: Chesterfield
   pet: horse
Item 3:
   color: red
   country: England
   drink: milk
   brand: Old Gold
   pet: snails
Item 4:
   color: ivory
   country: Spain
   drink: orange juice
   brand: Lucky Strike
   pet: dog
Item 5:
   color: green
   country: Japan
   drink: coffee
   brand: Parliament
   pet: zebra

The Format of ZebraPuzzleSolution

The ZebraPuzzleSolution instance has a .data property that you can use directly as well. It will consist of an array of LookupTable instances with each LookupTable corresponding to a single house. Something like:

    [
        [ 'color' -> 'yellow, 'country' -> 'Norway', 'drink' -> 'water',
            'brand' -> 'Kool', 'pet' -> 'fox ],
        [ 'color' -> 'blue', 'country' -> 'Ukraine', 'drink' -> 'tea',
            'brand' -> 'Chesterfield', 'pet' -> 'horse', ],
        [ 'color' -> 'red', 'country' -> 'England', 'drink' -> 'milk',
            'brand' -> 'Old Gold', 'pet' -> 'snails', ],
        [ 'color' -> 'ivory', 'country' -> 'Spain', 'drink' -> 'orange juice',
            'brand' -> 'Lucky Strike', 'pet' -> 'dog', ],
        [ 'color' -> 'green', 'country' -> 'Japan', 'drink' -> 'coffee',
            'brand' -> 'Parliament', 'pet' -> 'zebra', ]

    ]

Alternate Declaration Syntax

In addition to declaring the config object all at once, it can be created programmatically. For example:

    local cfg = new ZebraPuzzleConfig();

    cfg.addVariable('color', 'red');
    cfg.addVariable('color', 'green');
    cfg.addVariable('color', 'ivory');
    cfg.addVariable('color', 'yellow');
    cfg.addVariable('color', 'blue');

…or alternately…

    cfg.addVariable('pet',
        [ 'dog', 'snails', 'fox', 'horse', 'zebra' ]);

And constraints can be added via a similar syntax:

    cfg.addConstraint('England', 'red');
    cfg.addConstraint('green', 'ivory', { a, b: a == b + 1 });

Discussion

I shoved this into its own little module because it’s not really a datatype anymore. I kinda think maybe the BT and AC3 logic and this should be moved into their own constraint solver module.

In a different development environment I’d be more inclined to do what I started out doing…making lots of small, single-purpose modules instead of a smaller number of larger ones. But TADS3 doesn’t really make dependency management for that kind of thing easy.

Anyway, I figured things like the classic zebra problem were probably the kind of constraint satisfaction problem that most IF authors would probably be most concerned about, so I figured I’d knock this together as an example/illustration of how to implement a more specific solver using AC-3.