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
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 ";
}
;