Acknowledgments
Morten Kromberg is the other co-author of this text but the blogging software prevents his being listed as such.
We are indebted to Jay Foad, Nick Nikolov, John Scholes, and Fiona Smith for comments on successive drafts of the MS.
The Problem
The diamond kata is a programming exercise used in the agile development, XP and TDD communities. [0, 1, 2, 3]. It first came to our attention in 2012 in discussions with Gianfranco Alongi of Ericcson AB, Sweden, and again more recently in [3]. The following problem description is from [2] (the description varies slightly in each of the above references).
We’re going to write a program that builds a diamond picture like this, for some set of letters from A to whatever:
--A--
-B-B-
C---C
-B-B-
--A--
Solutions in Dyalog APL
We are actually going to solve a slightly different problem: the function will have two arguments. The left argument is a scalar of the background element; the right argument is a vector of the “letters” to be used. The result described in the opening section can be produced as:
'-' dia 'ABCD'
---A---
--B-B--
-C---C-
D-----D
-C---C-
--B-B--
---A---
(In an APL session, what you enter is indented and the resultant output is aligned at the left margin. As well, in this text, we sometimes present the indented-input/output pairs across the page.)
Making the argument the actual letters rather than the number of letters or the last letter, facilitates working with “alphabets” other than A-Z. For example:
0 dia 3 1 4 2
0 0 0 3 0 0 0
0 0 1 0 1 0 0
0 4 0 0 0 4 0
2 0 0 0 0 0 2
0 4 0 0 0 4 0
0 0 1 0 1 0 0
0 0 0 3 0 0 0
The diamond result is readily seen to be composed of reflections of one of the quadrants. For example, '-' dia 'ABCD' (shown above) is composed of reflections of
A---
-B--
--C-
---D
The functions ⌽ (reverse last axis) and ⊖ (reverse first axis) provide the requisite reflections. If q is the quadrant shown above, then:
⌽q q
---A A---
--B- -B--
-C-- --C-
D--- ---D
⌽⊖q ⊖q
D--- ---D
-C-- --C-
--B- -B--
---A A---
There are various ways to stitch the quadrants together (and to drop the common middle row or column) to get the required result. The following is a terse way:
f←{⍉⍵⍪1↓⊖⍵}
f ⌽q f f ⌽q f⍣2 ⌽q
---D--- ---A--- ---A---
--C-C-- --B-B-- --B-B--
-B---B- -C---C- -C---C-
A-----A D-----D D-----D
-C---C- -C---C-
--B-B-- --B-B--
---A--- ---A---
The same pattern (metakata?) of f⍣2 involving ⍉ can be used to compute the minors of a matrix [4].
It remains to produce the quadrant q. We note that it is a diagonal matrix and resembles the identity matrix for which creation many techniques are known. We use two of the 34 different methods in [5].
The first method: For a vector with n letters, if each vector is followed by n copies of the background element, then the 2⍴n reshape of that rotates each row an additional step to the right, and the result is the required diagonal matrix.
n←≢v←'ABCD'
v,'-'⍴⍨s←2⍴n s ⍴ v,'-'⍴⍨s←2⍴n
A---- A---
B---- -B--
C---- --C-
D---- ---D
The second method: for the proposed merge operator [6] ⍺ f merge ⍵ is an array like ⍵ with ⍺ at positions selected by f. As such, it is a functional version of selective assignment. Merge with 1 1∘⍉ as the operand does the trick.
4 4⍴⍳16 1 1∘⍉ 4 4⍴⍳16
1 2 3 4 1 6 11 16
5 6 7 8
9 10 11 12
13 14 15 16
'-'⍴⍨2⍴n 'ABCD' (1 1∘⍉merge) '-'⍴⍨2⍴n
---- A---
---- -B--
---- --C-
---- ---D
Putting it together:
dia ← {{⍉⍵⍪1↓⊖⍵}⍣2⌽s⍴⍵,⍺⍴⍨s←2⍴≢⍵}
diam ← {{⍉⍵⍪1↓⊖⍵}⍣2⌽⍵(1 1∘⍉merge)⍺⍴⍨2⍴≢⍵}
'-' dia 'ABCD' 0 dia 3 1 4 2
---A--- 0 0 0 3 0 0 0
--B-B-- 0 0 1 0 1 0 0
-C---C- 0 4 0 0 0 4 0
D-----D 2 0 0 0 0 0 2
-C---C- 0 4 0 0 0 4 0
--B-B-- 0 0 1 0 1 0 0
---A--- 0 0 0 3 0 0 0
'-' diam 'ABCD' 0 diam 3 1 4 2
---A--- 0 0 0 3 0 0 0
--B-B-- 0 0 1 0 1 0 0
-C---C- 0 4 0 0 0 4 0
D-----D 2 0 0 0 0 0 2
-C---C- 0 4 0 0 0 4 0
--B-B-- 0 0 1 0 1 0 0
---A--- 0 0 0 3 0 0 0
Further Examples
↑∘⎕a¨ 0 1 5 3 ⍝ four prefixes of the alphabet
┌┬─┬─────┬───┐
││A│ABCDE│ABC│
└┴─┴─────┴───┘
'.' dia¨ ↑∘⎕a¨ 0 1 5 3 ⍝ apply dia to each prefix
┌┬─┬─────────┬─────┐
││A│....A....│..A..│
││ │...B.B...│.B.B.│
││ │..C...C..│C...C│
││ │.D.....D.│.B.B.│
││ │E.......E│..A..│
││ │.D.....D.│ │
││ │..C...C..│ │
││ │...B.B...│ │
││ │....A....│ │
└┴─┴─────────┴─────┘
'.' {{⍉⍵⍪1↓⊖⍵}⍣2⌽s⍴⍵,⍺⍴⍨s←2⍴≢⍵}¨ ↑∘⎕a¨ 0 1 5 3
┌┬─┬─────────┬─────┐
││A│....A....│..A..│
││ │...B.B...│.B.B.│
││ │..C...C..│C...C│
││ │.D.....D.│.B.B.│
││ │E.......E│..A..│
││ │.D.....D.│ │
││ │..C...C..│ │
││ │...B.B...│ │
││ │....A....│ │
└┴─┴─────────┴─────┘
The last input expression is standalone (replacing dia in the penultimate input expression with its definition) and you can try it in a http://tryapl.org session.
Testing
Tests are often descriptive rather than prescriptive, asserting what a result should be rather than how to compute it. For that reason they tend to be more robust and easier to develop than the actual function. For example, it is much easier to test that r is a root of a polynomial than to compute it, or to check that S is a solution to an NP-complete problem than to derive it.
In this instance, we did not write the tests before writing the diamond functions, but we easily could have. The same expressive power in APL that enabled terse solutions of the diamond kata also enabled their concise and comprehensive testing.
testd d checks that d is a correct result of a diamond function, and returns a 1 if it is. Like the diamond functions, testd treats d in its totality, as an object (matrix) rather than as individual lines. This treatment allows straightforward statement of properties that would be more laborious otherwise. (For example, d≡⊖d and d≡⌽d assert that d is symmetric in the horizontal and vertical axes.)
assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕signal 8 ⋄ shy←0}
testd←{ ⍝ test the result of a diamond function
assert (2=⍴⍴⍵)∧=/⍴⍵: ⍝ square matrix
assert (0=≢⍵)∨1=2|≢⍵: ⍝ dimensions are 0 or odd
assert ⍵≡⌽⍵: ⍝ symmetric in vertical axis
assert ⍵≡⊖⍵: ⍝ symmetric in horizontal axis
n←⌈2÷⍨≢⍵ ⍝ number of input "letters"
q←(n,-n)↑⍵ ⍝ upper right quadrant
assert (q=⍬⍴⍵)∨∘.=⍨⍳n: ⍝ background or diagonal
1 ⍝ 1 iff everything OK
}
testd '-' dia 'ABCD'
1
testd 0 dia 3 1 4 2
1
If a check fails (or if there is an outright programming error), execution suspends at the first line with the error. While suspended an interactive debugging environment is provided for investigating the problem.
testd 'ABCD'
assertion failure
testd[1] assert(2=⍴⍴⍵)∧=/⍴⍵: ⍝ square matrix
∧
⍵
ABCD
⍴⍵
4
⍴⍴⍵
1
testd is not a complete test, because it does not “know” what the specified background element or what the “letters” were. The operator T provides a complete test:
T←{ ⍝ test a diamond function ⍺⍺
d←⍺ ⍺⍺ ⍵ ⍝ result of diamond function
assert testd d: ⍝ checks not knowing arguments
n←≢⍵ ⍝ number of input "letters"
assert (⍴d)≡0 0⌈¯1+2×n: ⍝ dimensions are 0 or ¯1+2×n
assert (1≥n)∨⍺=⍬⍴d: ⍝ background element
assert ⍵≡1 1⍉(n,-n)↑d: ⍝ "letters" in diagonal of quadrant
1 ⍝ 1 iff everything OK
}
⍺ dia T ⍵ checks that ⍺ dia ⍵ produces a correct result, and returns a 1 if it does (and suspends at the first line of error if it does not).
'-' dia T 'ABCD' '-' diam T 'ABCD'
1 1
0 dia T 3 1 4 2 0 diam T 3 1 4 1 5 9
1 1
The following expression tests '-' dia x where x is a prefix of the alphabet ⎕a, from 0 to 26 letters:
'-' (dia T)∘(⍴∘⎕a)¨ ¯1+3 9⍴⍳27
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
The following expression tests 0 dia n?n for n from 0 to 99. The “letters” are n?n, a random permutation of order n:
0 (dia T)∘(?⍨)¨ 10 10⍴¯1+⍳100
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
References
- Rose, Seb, Recycling Tests in TDD, Claysnow Blog, 2014-11-23.
- Cockburn, Alistair, Thinking Before Programming, Alistair Cockburn Blog, 2014-11-29.
- Jeffries, Ron, TDD on the Diamond Problem, RonJeffries.com Blog, 2014-11-29.
- Rusk, John, An Experiment in Think-First Development, AgileWiki Blog, 2014-12-01.
- Hui, Roger, and Kenneth E. Iverson, J Introduction and Dictionary,1990-2014; \. entry
- Hui, Roger, Identity Matrix, Jwiki Essay, 2005-11-18.
- Scholes, John, Merge, Dfns, 2012-03-30.
- Legrand, Bernard, Mastering Dyalog APL, 2009-11.
NOTE: A full description and tutorial of the language can be found in [7].
Follow
