Help / JforC / Loopless Code VI: Temporary Variables
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help J for C Programmers
25. Loopless Code VI: Temporary Variables
The algorithms that are hardest to put into loopless form are the ones that chug through the items of an array, modifying a set of temporary variables that control the operation at each step. I am going to show you how to put one example of such an algorithm into loopless form. The resulting structure can be used for many such problems.
The example problem is a simulation. In a certain church most of the worshippers are devout, but the front pew is always packed with knaves. Collection is taken every Sunday. Each knave brings two coins to throw in, but, being a knave, he first removes the two most-valuable coins from the plate before adding his own. Given p, the contents of the plate when it reaches the front row (a list of coin-values) and k, the coins brought by the knaves (an nx2 array), what is the final contents of the plate, and what does each knave make off with? For test data, we will use
p =. 100 25 100 50 5 10
giving the contents of the plate as it enter the knaves' row, ,and
]k =. _2 ]\ 50 50 100 25 5 10 25 50 25 10 50 50 100 25 5 10 25 50 25 10
as the coins to be thrown in by the greedy knaves.
After trying for a clever solution for a little while we give up and decide we are going to have to simulate the action of each knave. We start by writing a verb knave to perform a knave's action. The design of this verb requires a little careful joinery to make it useful later: we will invoke it as x knave y where x is an item of k, i. e. the input for one knave, and y is the result from applying knave for the previous knave; the result of knave must have the same format as the y operand of knave; finally, the result of knave must include whatever we want as the final solution of the problem.
The trick is that the result of knave, which will be the input to the next invocation of knave, must carry all the information needed by the next invocation of knave; this is the way information is passed from knave to knave. The main design decision is to figure out what the format of the y operand of knave will be.
Obviously we need to know the contents of the plate as it is given to each knave. Also, the purpose of knave is to calculate what coins are removed, so those coins should be part of the result. We decide that the y operand of knave will consist of those two things, in the order (coins removed),(plate contents), and we already know that the x operand will have the format of an item of k, i. e. the knave's two coins. Now we are ready to code knave .
It should look at the plate-contents portion of its right argument, sort it into order of size, take the two biggest values as the result of interest, and use the rest (with the knave's own coins added) as the plate contents to be passed to the next knave. The coins that were removed are put into their place at the beginning of the result vector. In J this will be:
knave =: dyad define
xlen =. #x NB. number of coins added/removed
splate =. \:~ xlen }. y NB. extract plate contents, sort
(xlen {. splate) , (xlen }. splate) , x NB. build result
)
Let's test it. The y operand to the first invocation of knave will have a couple of placeholders in the place where the coins removed by the previous knave would be, followed by the initial contents of the plate. In other words,
]inity =. ({:k),p
25 10 100 25 100 50 5 10
Here we used the last item of k as a placeholder. The values don't matter but we want the right shape so the program will still work if we change the number of coins in k . Applying this value to the first knave we get
50 50 knave inity 100 100 50 25 10 5 50 50
Yes, that's right: the first two items of the result are the two dollar coins the knave took, and he threw his coins in at the end.
Before we go on we can't help noticing that taking the first two items of splate and then dropping those same items--that's needless work. We can simplify knave to
knave =: dyad : '(\:~ (#x) }. y) , x'
Now we need to apply knave sequentially on all items of k . We have learned enough J to write a sentence to do that, but because this is a recurring problem I have written a conjunction LoopWithInitial to hide the complexity (we'll look at its details in a moment). This conjunction takes the verb knave, the initial value inity, and the array k and applies knave repeatedly, with each item of k taking a turn as x with the y set to the result from the previous invocation of knave :
]res =. knave LoopWithInitial inity k 100 100 50 25 10 5 50 50 50 50 50 25 10 5 100 25 100 50 25 25 10 5 5 10 25 25 10 10 5 5 25 50 50 25 10 10 5 5 25 10
We see the result after each application of knave (if you want to see the input alongside the result, type k ,&<"_1 res). The contents of the plate are included in res as well; we can extract the desired result simply as
2 {."1 res
100 100
50 50
100 50
25 25
50 25
Once you have defined the verb and the initial value, you can use LoopWithInitial to solve problems of this kind.
You may skip the rest of this chapter if you are not curious about how LoopWithInitial works. It performs the following steps:
LoopWithInitial =: conjunction define by =. <"_1 y NB. 1 box items of y ry =. |. by NB. 2 reverse order for \. ey =. ry , <n NB. 3 append initial value r =. u&.>/\. ey NB. 4 apply u in boxes er =. }: r NB. 5 remove initial value rr =. |. er NB. 6 put in original order >rr NB. 7 remove boxing )
Since the initial value is going to be appended to the y operand, and they have dissimilar shapes, it is necessary to box each item of y as well as the initial value. Once the items of y are boxed, they are put into reverse order, because as we have seen u/\. is much faster than u/\ . Then the initial value is appended to the reversed boxed y . With that preparation complete, the operation can be performed: u&.>/\. applies u&.> (in words: unbox each operand, apply u, and rebox) starting at the end of the reversed y . The first application of u&.> will be between the original first element of y and the initial value; the next application will be between the original second element of y and the result of the first application; and so on. The results from the applications of u&.> are collected in an array. Finally, the preparation steps are undone, discarding the initial value, reversing the array into original order, and unboxing the result.
The actual implementation of LoopWithInitial is a bit more elegant than that schematic representation. Observe that step 7 is the inverse of step 1, step 6 of 2, and step 5 of 3; each pair is an opportunity to use u&.v, and the actual verb produced by LoopWithInitial is:
knave LoopWithInitial inity knave&.>/\.&.(,&(<25 10 100 25 100 50 5 10))&.|.&.(<"_1)
which performs all the steps of the longer form. We will examine this conjunction in a later chapter.
You may object that since the left operand of LoopWithInitial is applied to each item, it still has to be interpreted for each item, so nothing is gained by avoiding the loop. An astute observation, but in the second part of this book we will learn how to write verbs that are not reinterpreted for each item.
Finally, you may observe that the temporary vector, which only needs to be a list, turns into a rank-2 array by the time we have passed it through each item. Doesn't that waste a lot of space? Yes, it does, and if your problem is big enough that the space matters, you may have a valid application for a loop. An alternative would be to make the temporary vector a public variable accessed by knave in the same way that temporary variables would be used in C.
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help J for C Programmers