This is the second of the APR problem pages.

Data Structures

We will use LiveCode Community Edition, that can be downloaded free from RunRev.  I will not explain how this works since the LiveCode site does that in detail (e.g. in the beginners' guide).

We start by providing a text entry field in which the user can type a list of switch descriptions.  This field will look like a table with three columns and a line for each switch description.  I used a text field with the table option, tab stops at 30 pixels and a maximum of 3 editable columns.  I coloured the grid lines and chose to display only 16 lines since I only have 16 Lego Duplo switches.  I also put a label field on top and another lable field at the left to show the numbers of the switches.  It looks like this:

Unfortunately typing into such a field will make the field scroll horizontally if the last visible column is used.  To avoid that I made four columns visible, then put a locked graphic with the card's background colour on top of the fourth column to hide it.  In the above image I already typed the switch descriptions of the oval with a diagonal.

We add a button to compute the APR, and a field "Diagnostic" where we will put the result and any other message about the computation:

Validating the User's Input

As soon as the user has typed some switch descriptions in the switches field, we must check the validity of the input.

We will use the letters of the alphabet to name segments and label both segment ends by the segment's letter and either the digit 1 or 2.

That limits us to 26 segments, which is enough for 16 switches:  8 pairs need 3x8=24 segments.

The switches field contains a line for each switch, with three points (segment end labels) on each line, separated by the tab character.

A function ValidSwitches can perform this check:

For writing LiveCode programs I use some naming conventions that help me find my way among the variables I need to declare.  I will assume that you have read them.

Line 1:  declares the 26 upper case letters, used for segment names.

Line 3:  the function Clean() returns the given string without leading and trailing blanks and tabs.  It is one of a set of general routines that can be used in any stack's script.

Line 5:  ensures that we can use the item chunks of the switches.

Line 8:  checks each switch is described by three segment ends.

Line 14:  checks that each point name is of the form letter+digit where digit must be one of 1 or 2.

There is of course no verification that the given descriptions do correspond to some real layout.

The Switches Field

This is the script of the Switches field.  It gets the message CloseField when the user clicks somewhere else (except on Mac OSX) and this handler stops all processing if the user makes a typing error.

The Compute Button

A first attempt at the script of that button is to set up the first version of the table of reachable points.

Because it is interesting to see how the table filled up, we will keep its first state in a variable lFirstReachable, so we can compare later.

Obviously we clear out the diagnostics first, then set up an empty table.

Before we go into the filling of the table, we consider this:  we can travel over a switch in both directions, each of which gives two marks in the table.  Take the example of the switch described by C1 A1 B1 :  going forward we actually come from C2, the other end of segment C.  Given our convention of labelling segment ends, to find the label of the other end of a segment means just changing the digit 1 into the digit 2, or 2 into 1.

We will index the tables by numbers rather than segment end labels because we will need to iterate over all rows and columns, which is easier to express in numeric loops.  We will therefore have to "translate" the points (segment end labels) into numbers while filling the table the first time:

A1 → 1; A2 → 2; B1 → 3; B2 → 4; C1 → 5; …

That is easily done by finding the place of the label's letter in the alphabet, multiplying by 2 and subtracting 1, and then adding the label's number and finally subtracting 1.

For that we use two routines numr and altnumr:

The function altnumr returns the number corresponding to the other segment end of a given point, i.e. it will return 6, the number of point C2 when given C1

The SetupReachable routine can now fill up the table from the switch descriptions:

It gets its formal parameters by address, i.e. it can change the variables given in the MouseUp handler (this is indicated by the @-sign in front of the formal parameter name).  Lines 2 to 5 should be easy to understand.  The repeat loop runs over each switch description.  For each switch it puts marks into the table fReachable.  Finally it returns the total number of points to be considered, which is just the number of rows of the table.

Making it visible

Let's make the table visible in a field.  Make a table field, with 15 pixels to the tab stop and set the margin to 6.

We now extend the mouse-up handler of the compute button:

I used a lower-case "o" instead of the checkmark, to avoid font problems on other platforms.

When the compute button is clicked, the Reachable field gets to show:

Iterating the Table

The last bit of code will deal with iterating filling of the table to see if the APR property is true or not.

We do this with a procedure ("command" in LiveCode"):

I called it MultiplyReachable because the computation resembles the multiplication of matrices.

Line 3 keeps a copy of the given table, so we can compare at each iteration if the table has changed, and stop as soon as it no longer does.

Line 4 is the start of the main iteration loop.  It will run until

Line 5 just keeps the user informed of progress (though this is only observable in extremely large tables or on slow computers).

Lines 6 and 7 are the double loop over rows and columns looking for a reachable point, and when found, lines 9 to 11 then look at that point's reachable points to copy them over into the found one, thus filling more cells in the table.

Finally, line 15 checks to see if the table has changed, and if not stops the iterations.  If the table has changed, it preserves the new state to check against next time.

The procedure returns the number of iterations it performed.

Final Display

The only thing left to do is to tell the user the result.

To do that we could just output "APR=true" or "APR=false", but we will make it a little more attractive.  We change the code of the MouseUp handler of the Compute button to this:

In line 6 we did the initial setup of the reachables table using the switch descriptions..  In line 7 we keep that original setup so we can display the original check marks differently from the added ones, and do the iterations on a copy.

Line 8 does the work.

Lines 9 to 12 prepare the display, which we will do in field "Reachable".

Lines 13 to 18 just put a mark in the field's cells that correspond to a reachable element in the table.  Line 17 counts the total number of marks we place.  They will by default be coloured black.  Then in 21 to 28 we use the first setup to colour the original marks red and make them bold.

Line 29 checks if the number of marks placed is equal to the total number of cells in the table (nxn) and puts a corresponding message in the diagnostics field.

The resulting display (after clicking the Compute button) looks like:

For the layout:

we get:

Polishing

There is much left that we can do to improve this program.  We should use the cards of the stack so we can put more than one layout definition into it;  we should be able to past an image of the layouts onto the cards;  we should make the table larger or let it scroll, and it should have legends on its sides.

I have implemented much of that, and its code is available for inspection.

I just still do not know why it always finds the solution after only two iterations.

There is a remark to make though.  We compute the next iteration of the matrix in a peculiar way:  we start from the previous state, but progressively we use the new state.  For example, suppose that the first line of the new state has several new cells filled in, and the second line refers to the first line.  We would normally change the second line by looking only at the first line in the previous matrix, but the program uses the new state, in which some cells have already been changed.  This is not an error, but it does give an advantage:  for filling information in the second line we are already using information from the first that we have just computed.  If you write a version of the multiplication that uses only the previous state, it will take more than two iterations before the matrix stops changing!