domino gymnastics, including transitive closure

[Roger|Dyalog]

A discussion on key veered into a discussion on domino. I am moving the latter to here.

From Roger Hui, 2020-05-04 08:00:

Veli-Matti, do you know of the puzzle, compute the average of a vector x in APL in as few character as possible? Posed by one of your countryman many years ago.

From Veli-Matti Jantunen, 2020-05-04 13:11:

Of course - I never met Timo Seppälä, but I have heard so many tales...

      ⍵⌹⍵=⍵

or

      (⊢⌹=⍨)

for Adám :)

From Roger Hui, 2020-05-04 13:53:

V. good.☺ The puzzle has nothing to do with key but a lot to do with your previous post. Said post indicated that you are a connoisseur of domino so I thought I’d ask.

A proof of correctness of ⍵⌹⍵=⍵ can be found in A History of APL in 50 Functions, §2.

From Adám Brudzewsky, 2020-05-04 14:06:

Paul Mansour says he "once heard you could justify the words in a char mat with it" (Domino). Is there such a thing?

From Roger Hui, 2020-05-04 14:56

Paul Mansour says he "once heard you could justify the words in a char mat with it" (Domino). Is there such a thing?

It depends on what’s meant by “with domino” and how contrived are you allowed to be.

      g←{(+/∧\' '=⍵)⌽⍵}

      x←↑'    foo' 'upon' '  thee  '  '  Cogito  ergo sum '
      ⊂ x
┌───────────────────┐
│    foo            │
│upon               │
│  thee             │
│  Cogito  ergo sum │
└───────────────────┘
      ⊂ g x
┌───────────────────┐
│foo                │
│upon               │
│thee               │
│Cogito  ergo sum   │
└───────────────────┘

(Misalignments in the display are due to defects in the APL Chat Forum software.)

The function +/ is essential to the solution, or rather, summation is. We’d just considered ⍵⌹⍵=⍵ for computing the average, and the sum is just the average times the number of items, whence:

      g1←{((≢ × ⊢ ⌹ =⍨)⍤1 ∧\' '=⍵)⌽⍵}

      (g ≡ g1) x
1

There is a harder problem solvable with domino. Given a character vector ⍵ of words separated by a space, replace some of the spaces with newline characters such that no line is wider than ⍺ characters, and each line contains the maximum number words that fit. (You may assume that none of the words are longer than ⍺.) You should get the original ⍵ if you replace the newline characters in the result by spaces. Of course, you can solve this problem without domino and in fact domino would not be what you’d use in practice.

From Phil Last, 2020-05-05 03:27

There is a harder problem solvable with domino.

This was referred to as "transitive clusure" when I first read about it. It was one of the one-liners I used to be able to trot out at will but as I never understood why it worked I never actually used it in practice.

[Roger|Dyalog]

There is a harder problem solvable with domino.

This was referred to as "transitive clusure" when I first read about it. It was one of the one-liners I used to be able to trot out at will but as I never understood why it worked I never actually used it in practice.

Transitive closure is discussed in A History of APL in 50 Functions, §35. Why domino works for the problem can be explained in one or two sentences:

Let A be an adjacency matrix of a directed graph. The expression ((≢A)↑1)⌹A is based on the equation for the infinite series

      ÷1-x ←→ (x*0)+(x*1)+(x*2)+ …

for numbers translated into the matrix realm, using the identity matrix instead of 1 , ⌹ instead of ÷ , and +.× instead of × (implicit in *).

In a few days I will post non-domino and domino solutions to the puzzle (“the harder problem”) posted yesterday.

[jayfoad]

This paper by Bob Smith discusses matrix divide and transitive closure in the context of parsing quoted strings: http://www.sudleyplace.com/APL/Dont%20Quote%20Me.pdf

[Phil Last]

... the problem can be explained in one or two sentences:

Let A be an adjacency matrix of a directed graph.
[...]
for numbers translated into the matrix realm, ...

which is why I never understood it.

[Roger|Dyalog]

This paper by Bob Smith discusses matrix divide and transitive closure in the context of parsing quoted strings: http://www.sudleyplace.com/APL/Dont%20Quote%20Me.pdf

Bob Smith is also the author of a ⌹ solution to “the harder problem”, published in the IPSA Newsletter, volume 7, number 2, 1979-03 and -04, on page 14 of the PDF file. Smith worked for STSC in 1979; his solution caused a sensation at IPSA. Arthur Whitney and I discussed it at the time.

[Roger|Dyalog]

There is a harder problem solvable with domino. Given a character vector ⍵ of words separated by a space, replace some of the spaces with newline characters such that no line is wider than ⍺ characters, and each line contains the maximum number words that fit. (You may assume that none of the words are longer than ⍺.) You should get the original ⍵ if you replace the newline characters in the result by spaces. Of course, you can solve this problem without domino and in fact domino would not be what you’d use in practice.

The problem can be solved as in Some Uses of { and } [Hui 1987, §1.2], translated into current Dyalog APL and improved by using facilities not then available.

      tc  ← {(⍳∘n ↑ ⊢) 1↓ 0{(⊃⍵)=⊃⌽⍵:⍺ ⋄ (⍺,⍵[⍺])∇ ⍵[⍵]}⍵,n←≢⍵}
      fit ← {⎕av[3]@(e[tc(e,≢⍵)⍸(1+⍺)+e←¯1,⍸' '=⍵])⊢⍵}

For example:

      t←'Whether or not it is clear to you,'
      t←t,' no doubt the universe is unfolding as it should.'
      t←t,' The quick brown fox jumps over the lazy dog.' 
      t←t,' There was never yet philosopher'
      t←t,' that could endure the toothache patiently.' 

      w←20 ⋄ w⍴'-' ⋄ w fit t ⋄ w⍴'-' 
--------------------
Whether or not it is
clear to you, no
doubt the universe
is unfolding as it
should. The quick
brown fox jumps over
the lazy dog. There
was never yet
philosopher that
could endure the
toothache patiently.
--------------------
      w←45 ⋄ w⍴'-' ⋄ w fit t ⋄ w⍴'-' 
---------------------------------------------
Whether or not it is clear to you, no doubt
the universe is unfolding as it should. The
quick brown fox jumps over the lazy dog.
There was never yet philosopher that could
endure the toothache patiently.
---------------------------------------------

The solution works as follows: In function fit, e are the indices of where words end, and includes where lines would end. (It is convenient to assume that there is a fictitious word which ended at position ¯1.) If the previous line ended at e[j], then the current line would end at e[e⍸(1+⍺)+e[j]]. For 20 fit t, the values are as follows:

      ⍵ ⋄ '.e'[(⍳≢⍵)∊e]
Whether or not it is clear to you, no doubt the universe is unfolding as it   …
.......e..e...e..e..e.....e..e....e..e.....e...e........e..e.........e..e..e  …

      (⍳≢e) ⍪ e ⍪ (e⍸(1+⍺)+e) ,[¯0.5] e[e⍸(1+⍺)+e]
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16  17  18  19  20  21  22 
¯1  7 10 14 17 20 26 29 34 37 43 47 56 59 69 72 75  83  87  93  99 103 109 … 
 5  6  7  8  9  9 11 11 11 12 13 13 16 16 18 19 19  21  21  23  24  25  26  
20 26 29 34 37 37 47 47 47 56 59 59 75 75 87 93 93 103 103 114 118 123 128

(Misalignments in the display are due to defects in the APL Chat Forum software.)

The vector e⍸(1+⍺)+e specifies a direct acyclic graph with each node having zero or one outgoing edge. (We use the very similar (e,≢⍵)⍸(1+⍺)+e in a tactical move, using ≢⍵ to indicate nodes which have no outgoing edges.) tc ⍵ computes the transitive closure for such a graph, all the nodes reachable from node 0.

      ⊢ i← (e,≢t)⍸(1+20)+e
5 6 7 8 9 9 11 11 11 12 13 13 16 16 18 19 19 21 21 23 24 25 26 27 28 29 30 …
      tc i
5 9 12 16 19 23 27 30 32 35
      (⍳≢e) ⍪ i ,[¯0.5] '.↑'[(⍳≢e)∊0,tc i] 
0 1 2 3 4 5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  
5 6 7 8 9 9 11 11 11 12 13 13 16 16 18 19 19 21 21 23 24 25 26 27 28 29 30  …
↑ . . . . ↑  .  .  .  ↑  .  .  ↑  .  .  .  ↑  .  .  ↑  .  .  .  ↑  .  .  .

tc i indicates that from node 0, node 5 is reached; from node 5, node 9 is reached; from node 9, node 12 is reached; …; from node 32, node 35 is reached.

tc uses “repeated squaring” (⍵[⍵]). The inner dfn is evaluated O(⍟n) times and the total time is O(n×⍟n). It is more efficient in both time and space than a ⌹ solution.

[Roger|Dyalog]

More on transitive closure. The problem of fitting words within a specified width induces a directed acyclic graph where each node has zero or one outgoing edge, and it is required to find all the nodes reachable from node 0. This simple version of transitive closure is solvable by several different APL functions.

An example of such a graph:

      ⎕rl←7*5    ⍝ for reproducible random numbers
      y←100⌊+\1+?100⍴2

      ((⍳≢y) ,[¯0.5] y
0 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15 16 …  97  98  99
2 3 5 7 8 10 11 12 13 15 17 19 21 22 24 25 27 … 100 100 100

(Misalignments in the display are due to defects in the APL Chat Forum software.)

There is an edge from 0 to 2, from 1 to 3, from 2 to 5, and so on. Node number ≢y (here 100) is used to indicate that there is no outgoing edge from a node (here, 97 98 99 have no outgoing edge).

What are the nodes reachable from node 0? tc from the previous post provides the answer:

      tc ← {(⍳∘n ↑ ⊢) 1↓ 0{(⊃⍵)=⊃⌽⍵:⍺ ⋄ (⍺,⍵[⍺])∇ ⍵[⍵]}⍵,n←≢⍵}

      tc y
2 5 10 17 29 51 87

The graph can also be represented as a square boolean matrix A, where A[i;j] is 1 if and only if there is an edge from node i to node j.

      A ← (⍳2⍴≢y) ∊ (⍳≢y),¨y
      A
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 …
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
   …

A indicates nodes reachable in 1 step; A∨.∧A indicates nodes reachable in 2 steps; A∨.∧A∨.∧A nodes eachable in 3 steps; A∨.∧A∨.∧A∨.∧A nodes reachable in 4 steps, and so on. Whence

      I← ∘.=⍨ ⍳≢A
      I ∨ A ∨ (A∨.∧A) ∨ (A∨.∧A∨.∧A) ∨ (A∨.∧A∨.∧A∨.∧A) ∨ ...   ⍝ (*)

are the nodes reachable in any number of steps, the reachable nodes. The equation for the infinite series for numbers is

      ÷1-x ←→ (x*0)+(x*1)+(x*2)+ …

Translated into the boolean matrix realm, using the identity matrix instead of 1 , ∨.∧ instead of × (implicit in *), and ⌹ instead of ÷, the expression (*) becomes

      ⌹I-A

and the nodes reachable from node 0 are row 0 of this matrix.

      ⍸ 0 ⌷ ⌹I-A
0 2 5 10 17 29 51 87

Another solution is possible. If A1←A∨I, then A1∨.∧...∨.∧A1 with n occurrences of A1, are the nodes reachable in n steps or less, whence ∨.∧⍨⍣n⊢A1 are the nodes reachable in 2*n steps or less, ∨.∧⍨⍣≡A1 are the reachable nodes, and ⍸0⌷∨.∧⍨⍣≡A1, indices of row 0 of this matrix, are the nodes reachable from node 0.

      ⍸ 0⌷ ∨.∧⍨⍣≡ A1
0 2 5 10 17 29 51 87

      (⌹I-A) ≡ ∨.∧⍨⍣≡A1
1

A benchmark comparing the three solutions:

      cmpx '0,tc y' '⍸0⌷⌹I-A' '⍸0⌷∨.∧⍨⍣≡A1'
  0,tc y      → 7.51E¯6 |     0% ⎕                             
  ⍸0⌷⌹I-A     → 1.51E¯4 | +1917% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  ⍸0⌷∨.∧⍨⍣≡A1 → 1.70E¯5 |  +126% ⎕⎕⎕

Both the tc solution and the ∨.∧⍨⍣≡ solution use “repeated squaring”, ⍵[⍵] for tc and ∨.∧⍨ for ∨.∧⍨⍣≡. tc is O(n×⍟n); ⌹ is O(n*3); and ∨.∧⍨⍣≡ is O((n*3)×⍟n). Because of this, we expect that the timing advantage for tc to increase with argument size. And so it does:

      ⎕rl←7*5
      y←800⌊+\1+?800⍴2
      A←(⍳2⍴≢y)∊(⍳≢y),¨y
      I←∘.=⍨⍳≢A
      A1←I∨A

      cmpx '0,tc y' '⍸0⌷⌹I-A' '⍸0⌷∨.∧⍨⍣≡A1'
  0,tc y      → 1.56E¯5 |       0%                               
  ⍸0⌷⌹I-A     → 2.21E¯2 | +141350% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  ⍸0⌷∨.∧⍨⍣≡A1 → 2.93E¯4 |   +1775%