Skip to content

Instantly share code, notes, and snippets.

@davidallsopp

davidallsopp/diamond4.md

Last active Aug 29, 2015
Embed
What would you like to do?
Diamond kata using symmetry and a Scala Worksheet

This is one of my attempts (the 4th) at the diamond kata, in Scala (See Ron Jeffries' article: http://ronjeffries.com/articles/diamond3/three-of-diamonds.html). This version makes explicit use of the symmetry of the diamond by generating one quadrant of it, then reflecting that quadrant twice to generate the entire diamond.

UPDATE: I have added my 2nd and 3rd (and now 5th, and 6th in Haskell) solutions for comparison at the bottom of the page. The 1st solution is somewhere out of reach at the time of writing! The serious business of TDD degenerates into a bit of an obfuscated one-liner contest at this point ;-)

UPDATE: see also Ron Jeffries' article (http://ronjeffries.com/articles/diamond/diamond.html) which also uses the symmetry - I didn't read this one until afterwards.

I wrote it as an Eclipse Scala worksheet. These worksheets evaluate and display the results of each expression whenever an edit is made, rather like a persistent REPL. This provides great visibility and feedback on your code, so I find it very useful for trying out ideas.

NB: I have slightly condensed and reformatted the worksheet output (e.g. removed the type annotations and changed newlines) so that it fits better on the GitHub layout.

object diamond {

    val chars = 'A' to 'C'              
                        //> NumericRange(A, B, C)
    
    val topright = chars.map { y => chars.map { x => if (x == y) x else '-' } }
                        //> Vector(Vector(A, -, -), Vector(-, B, -), Vector(-, -, C))
                                        
    val top = topright.map(r => r.reverse ++ r.tail)
                        //> Vector(Vector(-, -, A, -, -), 
                        //|        Vector(-, B, -, B, -), 
                        //|        Vector(C, -, -, -, C))
                                        
    val all = (top ++ top.reverse.tail).map(_.mkString).mkString("\n")
                                        //> --A--
                                        //| -B-B-
                                        //| C---C
                                        //| -B-B-
                                        //| --A--
}

There isn't a full history here, but hopefully you can see that it's straightforward, with this design, to finish each step then move onto the next.

In one of my earlier solutions I TDD'd with pass/fail unit tests within the worksheet (similar to below), but they didn't seem to assist the design as much as this very fine-grained feedback - I spent a lot of time on Red. The tests did detect a number of mistakes and false assumptions, so they were certainly useful.

Seb Rose's observation about the "Gorilla" approach versus the "Moose" approach (http://claysnow.co.uk/recycling-tests-in-tdd/) made a lot of sense at this point - the test is too coarse to allow a small change to Green, but finer-grained tests are only stepping stones - they aren't capturing "correct" behaviour, only "better" behaviour.

This solution seemed much more straightforward, but that's possibly just because I've tried several solutions now and glanced at a few other folks's approaches.

def test(end: Char, expected: String) = {
    val actual = diamond(end)
    assert(actual == expected.stripMargin, actual)
  } 

  test('A', "A")

  test('B',
    """|-A-
       |B-B
       |-A-""")

  test('C',
    """|--A--
       |-B-B-
       |C---C
       |-B-B-
       |--A--""")

On the other hand, one generally needs to "finish off" worksheet code by wrapping it into coarser-grained functions, at which point the fine-grained feedback vanishes, because the individual expressions are no longer in scope at the top-level (and in any case we'd move the code from worksheets into normal source files). One could, of course, write tests for each of the steps above (topright, top and all), and make each into a function, but normally I'd have wrapped all the code into a single function:

  def diamond(last: Char) = {
    val chars = 'A' to last
    val topright = chars.map { y => chars.map { x => if (x == y) x else '-' } }
    val top = topright.map(r => r.reverse ++ r.tail)
    (top ++ top.reverse.tail).map(_.mkString).mkString("\n")
  }

There's a dilemma here - I could have split out each of these lines into a function with its own tests - but then my tests would be closely coupled to the details of the implementation. I would also have a lot of functions in scope that ideally would be private.

We could instead try to find different tests that capture invariants, such that we can grow the implementation to meet each invariant in turn. This might allow us to get from red to green more rapidly. Capturing invariants fits with the use of property-based testing, which is often more powerful than manually-determined unit test examples. However, for the diamond problem, we can end up with a lot of tests that cover no more ground than the simple A, AB, ABC tests, and are much less clear - one cannot easily see the purpose of the code from such tests.

It's interesting that the same tests (here, I mean the "Gorilla" tests A, AB, ABC as shown above) can result in such a wide range of implementations (and also shows, I suppose, that these tests are not closely coupled to the implementation). Surely that also shows that this particular selection of tests is not really driving the design much?

##Other solutions

Both of these need a special case for the first and last rows, which is a bit ugly.

###2nd - recursive

  def diamond(end: Char) = {
    def go(c: Char, pad: Int): String = {
      val left = (" " * (end.toInt - c.toInt))
      val line = left + c + (if (pad < 0) "" else (" " * pad) + c)
      if (c == end) line
      else List(line, go((c.toInt + 1).toChar, pad + 2), line).mkString("\n")
    }
    go('A', -1)
  }

###3rd - makes partial use of symmetry (reflecting top-to-bottom)

This one makes use of a little up-front thinking about how the width of the padding (at the edges and in the middle) varies. We generate all the rows as tuples of (letter, middle-padding, end-padding), then just render them.

  def diamond(max: Char) = {
    val rows = ('A' to max).map { c => (c, 2 * (c - 'A') - 1, max - c) }
    val range = rows ++ rows.reverse.tail
    def pad(i: Int) = "-" * i
    range.map { case (l, m, e) => pad(e) + l + (if (m < 0) "" else pad(m) + l) + pad(e) }
  }

This can be turned into a one-liner. Not quite as short as the Ruby one, but not bad for a statically-typed language. See later for another Scala one that's shorter than Ruby...

val r=('A'to'Z').map{c=>(c,2*(c-65)-1,90-c)};(r++r.reverse.tail).foreach{case(l,m,e)=>println("-"*e+l+(if(m<0)""else"-"*m+l)+"-"*e)}

Now that I've added multiple solutions, I notice that I've used three different names (last, end and max) to refer to the same concept (the final character to use for the widest row).

###5th

This is inspired by Jonas Elfström's one-liner

object diamond5 {
  val chars = 'A' to 'D'                          
                            //> NumericRange(A, B, C, D)
                            
  val ys = chars ++ chars.reverse.tail            
                            //> Vector(A, B, C, D, C, B, A) 
                            
  val xs = chars.tail.reverse ++ chars            
                            //> Vector(D, C, B, A, B, C, D)
                            
  (for { y <- ys; x <- xs } yield if (x == y) x else '-').grouped(xs.length).map(_.mkString).mkString("\n")
                            //> ---A---
                            //| --B-B--
                            //| -C---C-
                            //| D-----D
                            //| -C---C-
                            //| --B-B--
                            //| ---A---
}

###6th - in Haskell

Also inspired by Jonas Elfström's one-liner in Ruby (https://twitter.com/jonelf/status/539409551800692737). And slightly shorter ;-)

let c=['A'..'C'];d=reverse c in mapM_ putStrLn$chunksOf 5$(\x y->if(x==y)then x else '-')<$>c++tail d<*>d++tail c

However, it does require a few imports, so is arguably cheating. The properly-formatted and parameterised version isn't actually much longer, and is reasonably idiomatic Haskell (as far as I can tell - I'm no expert).

module Diamond where

import Control.Applicative
import Data.List.Split

main = diamond 'D'

diamond max = mapM_ putStrLn $ chunksOf width $ char <$> (c ++ tail d) <*> (d ++ tail c)
  where char x y = if x == y then x else '-'
        c = ['A'..max]; d = reverse c
        width = 2 * length c - 1

A bit of explanation of the longest line: this applies the binary function char across the two lists of characters (c ++ tail d) and (d ++ tail c), for example ABCBA and CBABC. We use "Applicative" notation (the <$> and <*>). The end result is that the function is applied to all pair-wise combinations from the input lists.

We then split the resulting list of characters into lines of the right length, using chunksOf, then map the putStrLn function over all of the lines to display them (using mapM_ rather than plain map because we are in the IO monad, which I'm not going to attempt to explain ;-)

The other $ operators are just to deal with precedence - each one is equivalent to putting parentheses around everything that follows.

###6a - list comprehension

Using a list comprehension turns out to be even shorter:

let c=['A'..'C'];d=reverse c in mapM_ putStrLn$chunksOf 5$[if(x==y)then x else '-'|x<-c++tail d,y<-d++tail c]

Or even shorter with nested comprehension:

let c=['A'..'C'];d=reverse c in mapM_ putStrLn[[if(x==y)then x else '-'|x<-d++tail c]|y<-c++tail d]

...and we now don't need any imports, so it's a genuine one-liner.

The non-obfuscated version is below:

diamond end = mapM_ putStrLn [[char x y | x <- xs] | y <- ys]
  where char x y = if x == y then x else '-'
        c = ['A'..end]    -- e.g. ABC
        d = reverse c     -- e.g. CBA
        xs = d ++ tail c  -- e.g. CBABC
        ys = c ++ tail d  -- e.g. ABCBA

###6b - in Python

The Python equivalent of the Haskell one-liner is a bit less satisfactory, and slightly longer since we have to write a range using integers, rather than characters e.g. 'A'..'C'. It uses the nasty extended slice syntax to reverse the list (see http://stackoverflow.com/a/3940137/699224).

c=range(65,68);d=c[::-1];print"\n".join(["".join([chr(x)if(x==y)else'-'for x in d+c[1:]])for y in c+d[1:]])

###6c - Scala again (now shorter than the Ruby benchmark!)

val c='A'to'D';(c++c.reverse.tail)map(y=>(c.reverse++c.tail)map(x=>if(x==y)x else'-')mkString)foreach println

(gives a compiler warning for postFixOps, but whatever...)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment