Slanted Triangles

Code Along

A code-along is a story about coding in which you are encouraged to “code up” all the examples in the story. In a code-along you should not cut-and-paste.

This code along explores how predicates, mappings, and traversals can be used to create a variety of slanted triangles. Slides for this code-along can be found here.

Example 1

In this example, an artifact will be constructed using the following property p.

p (x,y,z) ≝  x – y + z = 0

Table 1 shows the evaluation results of p for various coordinates.

We will construct an artifact by placing a BLUE brick in every cell in our virtual space whose coordinate satisfies the property p. The resulting artifact is the slanted triangle shown in Figures 1 and 2.

Let us analyize for a bit why our artifact has this particular shape. Our analysis begins with enumerating the coordinates of our virtual space for which our property evaluates to true. For the coordinate (0,0,0) the property is satisfied since 0 – 0 + 0 = 0. Now let us increment y and analyze for which values of x and z, coordinates of the form (x,1,z) will evaluate to true. In the case when y = 1, the coordinates that satisfy p are { (1,1,0), (0,1,1) }.

In the case when y = 2, the coordinates that satisfy p are: { (2,2,0), (1,2,1), (0,2,2) }. We can perform a similar analysis for y = 3,  y = 4, and so on. A central question in our analysis is the following:

For a given value of y, how many cells satisfy the property p?

We would like to understand, in general terms (i.e., for arbitrary values of y), the relationship that exists between y and the propery p. Let y = n. In mathematical terms, the question we are asking is: “How many solutions are there to the following equation?”

x + z = n

An easy way to figure out the answer to this question is to represent the values of x, z, and n in unary “match stick” notation. Table 2 shows the values of x and z that are solutions when n = 4.

Note that the algorithm used to generate successive solutions involves removing a “match stick” from the “z pile” and adding it to the “x pile”. The initial solution is when x = 0 and z = 4. From this initial solution, match sticks can be moved from z to x four times. This yields a total of 5 solutions.

In general, when y = n, there will be n+1 solutions to the equation x – y + z = 0. This formula explains the triangle shape that results. Namely, as y increases, xz-diagonals of increasing length are created.

Consider the two-dimensional xz-plane corresponding to y = n. Note that in this xz-plane the following coordinates will satisfy property p.

(0,n) … (n,0)

These coordinates form a diagonal line whose length is n+1.

Let us now take a look at the code that implements the slanted triangle we have described. In the program below, the virtual space is a cube whose side is denoted by the variable d. The maximum value along any axis in this virtual space is d – 1. The variable max is bound to this value. A function brickFn is declared that when given a 3D coordinate as input will return a brick as its output. More specifically, a BLUE brick is returned when the following equation

x – y + z = 0

evaluates to true (i.e., the coordinate satisfies p); otherwise an EMPTY brick is returned. The function brickFn is passed as an input to the traverseWithin function which, when executed, applies brickFn to every coordinate in the entire virtual space: (0,0,0) … (max,max,max). For each coordinate (x,y,z) processed, the traverseWithin function will update the cell (x,y,z) with the result of the call “brickFn (x,y,z)”. As a consequence, every cell in the resulting virtual space will contain either a BLUE brick or an EMPTY brick. Furthermore, the cells containg BLUE bricks will be precisely those whose coordinates satisfy p.

open Level_5; 

val d   = 64;
val max = d - 1;

fun brickFn (x,y,z) =
    if x - y + z = 0 then BLUE 
    else EMPTY;

build (d,d,d);

traverseWithin (0,0,0) (max,max,max) brickFn;

show "slanted triangle";

Example 2

This example slightly restructures the code of the previous example. Specifically, the body of the brickFn function is replaced by a let-block. This let-block declares a variable, called putBlue, which is bound to the value of the Boolean expression in which we are interested. The body of the let-block consists of a conditional expression which evaluates to a BLUE brick when putBlue is true and evaluates to an EMPTY brick otherwise.

open Level_5; 

val d   = 64;
val max = d - 1;

fun brickFn (x,y,z) =
    let
        val putBlue = x - y + z = 0;
    in    
         if putBlue then BLUE 
         else EMPTY
    end;

build (d,d,d);

traverseWithin (0,0,0) (max,max,max) brickFn;

show "slanted triangle";

Example 3

This example slightly restructures the code of the previous example. Specifically, a function, called shouldBeBlue, is declared that when applied to a 3D coordinate will return a Boolean value. Functions that return Boolean values are often referred to as predicates. Using this termonology, we refer to the function shouldBeBlue as a predicate.

In the body of brickFn, the variable putBlue is now bound to the result of a call to shouldBeBlue.  Note that since brickFn does not directly make use of the internal structure of a 3D point (i.e., its x, y, and z values) it is sufficient to abstract the formal parameter (x,y,z) to the variable point.

open Level_5; 

val d   = 64;
val max = d - 1;

fun shouldBeBlue (x,y,z) = x - y + z = 0;

fun brickFn point =
    let
        val putBlue = shouldBeBlue point;
    in    
         if putBlue then BLUE 
         else EMPTY
    end;

build (d,d,d);

traverseWithin (0,0,0) (max,max,max) brickFn;

show "slanted triangle";

Example 4

In this example another slanted triangle, this time RED, is added to our construction. Observe that our BLUE slanted triangle begins with a single bit-brick at (0,0,0) and finishes with a diagonal row of bricks over the following range:

(0,max,max) … (max,max,0)

We would like to add a similar slanted triangle that begins with a single RED bit-brick at (max,0,max) and also ends with a diagonal row of RED bricks over the following range:

(0,max,max) … (max,max,0)

Note that the shape of the RED triangle that we are constructing is equivalent to the shape of the BLUE triangle created by the predicate p. Aside from their color, the only difference between the two triangles is their orientation. Knowing this, it should be possible to create a function that translates (i.e., maps) points in the RED triangle to corresponding points in the BLUE triangle. Figure 3 shows one possible mapping.

Figure 4 shows initial portions of both triangles for cells whose coordinates have y values in the range: 0 … 3. Note that the reason why the BLUE and RED triangles are so close together is that teh Bricklayer program that created this composite artifact used a virtual space whose dimensions were (8,8,8). So in Figure 4, max = 7.

Table 3 describes the correspondence, shown in Figure 3, in symbolic terms.

Can you see the pattern that connects RED cells with corresponding BLUE cells?

Our next task is to generalize this 2-dimensional correspondence (i.e., the pattern shown in Table 3) and express it in terms of arbitrary (x,z).

Question: Suppose you were told that the coordinate (x,z),  for some unknown value of y, contained a BLUE brick. What is the corresponding coordinate that contains a RED brick?

Answer: The coordinate containing the corresponding RED brick is (max – x, max – z).

Question: Suppose you were told that the coordinate (x,z),  for some unknown value of y, contained a RED brick. What is the corresponding coordinate that contains a BLUE brick?

Answer: The coordinate containing the corresponding BLUE brick is (max – x, max – z).

The following expression specifies the correspondence between BLUE/RED and RED/BLUE cells for an arbitrary xz-plane.

(x,z) ⇔ (max – x, max – z)

Specifically, (x,z) contains a BLUE brick if and only if (max – x, max – z) contains a RED brick. Furthermore, it is also the case that (x,z) contains a RED brick if and only if (max – x, max – z) contains a BLUE brick.

Our last analysis step is to include y in our correspondence. The inclusion of y, shown below, turns out not to be difficult. Why?

(x,y,z) ⇔ (max – x, y, max – z)

At this point we have defined a correspondence between the BLUE and RED artifacts. This allows us to translate points that belong to the RED artifact to corresponding points in the BLUE artifact and vice versa. In a formal setting, such translations are typically called mappings. In mathematics, different kinds of mappings are studied. The kind of mapping we have defined here is special and is called a one-to-one correspondence. A one-to-one correspondence is also referred to, in more technical terms, as a bijection.

The following SML function implements the one-to-one correspondence we have defined.

fun map (x,y,z) = (max – x, y, max – z)

Using the function map, we will construct the BLUE and RED artifact shown in Figure 5 as follows. Our program will traverse the virtual space (0,0,0) … (max,max,max) and will do the following for each coordinate encountered.

1. Check to see if a BLUE brick should be placed at the coordinate. That is, check to see if the coordinate satisfies the property p.
2. If not, then check to see if a RED brick should be placed at the coordinate. This can be done by checking to see if the mapped coordinate satisfies the property p. If so, then a RED brick should be put at the (unmapped) coordinate.

In the program below, the property p is renamed to shouldbeBlue, since it is this property that defines the BLUE artifact. The predicate shouldBeRed defines the red artifact. Note that the predicate shouldBeRed is defined in terms of shouldBeBlue. Specifically, a point satisfies shouldBeRed if and only if its mapped version satisfies shouldBeBlue.

The body of brickFn declares the Boolean variables putBlue and putRed and binds them to the results of a call to shouldBeBlue and shouldBeRed respectively. The body of the let-block consists of a nested conditional expression that (1) evaluates to a BLUE brick when putBlue is true, (2) evaluates to a RED brick when putBlue is false and putRed is true, and (3) evaluates to an EMPTY brick when both putBlue and putRed are false.

Question: Are there any points for which putBlue and putRed are simultaneously true?

Answer: Yes. Consider the xz-plane associated with y = max. For this xz-plane both predicates will true for all coordinates in the following range.

 (0, max), (1, max – 1), … ,(max – 1, 1), (max, 0)

Note that the highest diagonal (i.e., when y = max) is BLUE (instead of RED). Why is this? How would the code need to be transformed to make the highest diagonal RED?

open Level_5; 

val d   = 64;
val max = d - 1;

fun map (x,y,z) = (max - x, y, max - z);

fun shouldBeBlue (x,y,z) = x - y + z = 0;
fun shouldBeRed point    = shouldBeBlue (map point);

fun brickFn point =
    let
        val putBlue = shouldBeBlue point;
        val putRed  = shouldBeRed  point;
    in    
              if putBlue then BLUE 
         else if putRed  then RED 
         else EMPTY
    end;

build (d,d,d);

traverseWithin (0,0,0) (max,max,max) brickFn;

show "slanted triangle";

Example 5

In this example another slanted triangle, this time GREEN, is added to our construction. Rather than having the “tip” of the triangle be at the bottom (i.e., y = 0) and the “base” of the triangle at the top (y = max), as is the case for the BLUE and RED triangles, the tip of the GREEN triangle will be at the top (i.e., y = max) and its base will be at the bottom (i.e., y = 0). Furthermore, we want to position this GREEN triangle so that the BLUE, RED and GREEN triangles fit together as shown in Figures 7 and 8.

Reviewing our previous analysis, we conclude that the following coordinates denote the base corners where the BLUE and RED triangles overlap.

(0,max,max)   and   (max, max, 0)

The goal of this example is to construct a GREEN triangle whose “tip” is located at the coordinate (0,max,max) and whose base corners overlap with the tips of the BLUE and RED triangles, (0,0,0) and (max,0,max).

To create the GREEN triangle, we will use the same technique we used for creating the RED triangle. Specirfically, we will create a one-to-one correspondence between cells in the GREEN and BLUE triangles. Note that, from the perspective of y values, the GREEN triangle is upside-down relative to the BLUE triangle. For the moment, let us ignore this and consider a simpler case where the BLUE and GREEN triangles both have their “tips” at the bottom.

Table 4 describes the correspondence, shown in Figure 6, in symbolic terms.

Can you see the pattern that connects GREEN cells with corresponding BLUE cells?

Our next task is to generalize this 2-dimensional correspondence (i.e., the pattern shown in Table 4) and express it in terms of arbitrary (x,z).

The following expression specifies the correspondence between BLUE/GREEN and GREEN/BLUE cells for an arbitrary xz-plane.

(x,z) ⇔ (x, max – z)

Specifically, (x,z) contains a BLUE brick if and only if (x, max – z) contains a GREEN brick. Furthermore, it is also the case that (x,z) contains a GREEN brick if and only if (x, max – z) contains a BLUE brick.

Our last analysis step is to define a one-to-one correspondence that takes y into account. It is at this stage where we incorporate a y mapping that accounts for the fact that the GREEN triangle that we actually want to build has its tip at the top and base at the bottom.

Table 5 describes the one-to-one correspondence between poritions of the BLUE and GREEN triangles in symbolic terms.

Table 5 provides the insight that gives rise to the following one-to-one correspondence.

(x,y,z) ⇔ (x, max – y, max – z)

At this point we have defined a one-to-one correspondence between the BLUE and GREEN triangles. This allows us to translate points that are part of the GREEN triangle to corresponding points in the BLUE triangle and vice versa.

We will construct the BLUE-RED-GREEN artifact shown in Figures 7 and 8 as follows. Our program will traverse the virtual space (0,0,0) … (max,max,max) and will do the following for each coordinate encountered.

1. Check to see if a BLUE brick should be placed at the coordinate. This can be done by checking to see if the coordinate satisfies the predicate shouldBeBlue.
2. If not, then check to see if a RED brick should be placed at the coordinate. This can be done by applying the mapRedToBlue function to the coordinate and then checking to see if the mapped coordinate satisfies the shouldBeBlue predicate.
3. If not, then check to see if a GREEN brick should be placed at the coordinate. This can be done by applying the mapGreenToBlue function to the coordinate and then checking to see if the mapped coordinate satisfies the shouldBeBlue predicate.

open Level_5; 

val d   = 64;
val max = d - 1;

fun mapRedToBlue   (x,y,z) = (max - x, y      , max - z);
fun mapGreenToBlue (x,y,z) = (x      , max - y, max - z);

fun shouldBeBlue  (x,y,z) = x - y + z = 0;
fun shouldBeRed   point   = shouldBeBlue (mapRedToBlue point);
fun shouldBeGreen point   = shouldBeBlue (mapGreenToBlue point);

fun brickFn point =
    let
        val putBlue   = shouldBeBlue   point;
        val putRed    = shouldBeRed    point;
        val putGreen  = shouldBeGreen  point;
    in    
              if putBlue  then BLUE 
         else if putRed   then RED 
         else if putGreen then GREEN
         else EMPTY
    end;

build (d,d,d);

traverseWithin (0,0,0) (max,max,max) brickFn;

show "slanted triangle";