DojoDeveloppement/Lundi5Juillet2010

AgileFrance | DojoDeveloppement | DernieresNouvelles | Preferences | AideEnLigne

Participants :

Rétrospective du /Lundi28Juin2010 :

Cartesian Product of n lists, randori, Ruby
'At some point I was lost'
- Couldn't understand how we came to the result
- anti-pattern: 'the magic moment' - where things work after a non-trivial move... but why?
We failed to work from outside in, using (known) algorithms - and attempted to find them back, from bottom-up
- it worked... but wasn't graceful (and not really TDD)
... but at least it did work in the end.
... and we had the time to review and clean the code
Would it be too short for a kata?

Et ce soir...

Randori /JeuDeLaVie, Ruby
Kata Cartesian Product of n lists, Ruby (Sujet retenu)

Le code de la soirée :

cartesian_product_test.rb

require 'test/unit'
require 'cartesian_product'


class CartesianProductTest < Test::Unit::TestCase

  def test_acceptance
    lists = [[1, 2, 3], [4], [5, 6], [7, 8]]
    expected_product = [
      [1, 4, 5, 7], [1, 4, 5, 8], [1, 4, 6, 7], [1, 4, 6, 8],
      [2, 4, 5, 7], [2, 4, 5, 8], [2, 4, 6, 7], [2, 4, 6, 8],
      [3, 4, 5, 7], [3, 4, 5, 8], [3, 4, 6, 7], [3, 4, 6, 8]
      ].sort
    assert_equal expected_product, cartesian_product(lists).sort
  end

  def test_one_set_of_one_element_gives_one_tuple_of_one_element
    assert_equal [[1]], cartesian_product([[1]])
    assert_equal [[2]], cartesian_product([[2]])
  end

  def test_one_set_of_two_elements_gives_two_tuples_of_one_element_each
    assert_equal [[1], [2]], cartesian_product([[1, 2]])
  end

  def test_two_sets_of_one_element_each_give_one_tuple_of_two_elements
    assert_equal [[1, 2]], cartesian_product([[1], [2]])
    assert_equal [[3, 4]], cartesian_product([[3], [4]])
  end

  def test_apply_some_set_to_empty_product
    assert_equal [[1], [2]], apply([[]], [1, 2])
  end

  def test_once_upon_a_time_there_was_a_partial_product_with_more_than_one_tuple
    assert_equal [[1, 3], [2, 3]], apply([[1], [2]], [3])
  end

  def test_it_grew_along_the_way_in_the_forest_eating_a_trail_of_mushrooms
    assert_equal [[1, 4], [2, 4], [3, 4]], apply([[1], [2], [3]], [4])
  end
end

cartesian_product.rb

def cartesian_product sets
  sets.inject([[]]) { |partial_result, next_set| apply partial_result, next_set}
end

def apply partial_product, set
  set.inject([]) do |result, element|
    result += partial_product.map { |tuple| tuple + [element] }
  end
end

Tests.hs

module Main
where
import Test.HUnit
import Cartesian

main = do runTestTT tests

tests = TestList [
  "One singleton gives one singleton" ~: TestList [
      cartesian [Set [1]] ~?= [Tuple [1]],
      cartesian [Set [2]] ~?= [Tuple [2]]
    ],

  "One set of two elements gives two singletons" ~:
    cartesian [Set [1, 2]] ~?= [Tuple [1], Tuple [2]],

  "Two singletons give one tuple of two elements" ~:
    cartesian [Set [1], Set [2]] ~?= [Tuple [1, 2]],

  "Adding something to an empty product" ~:
    distribute [Tuple []] (Set [77]) ~?= [Tuple [77]],

  "Three singletons give one tuple of three elements" ~:
    cartesian [Set [1], Set [2], Set [3]] ~?= [Tuple [1, 2, 3]],

  "Can distribute a three element set" ~:
    distribute [Tuple [1]] (Set [99, 101, 103])
      ~?= [Tuple [1, 99], Tuple [1, 101], Tuple [1, 103]],

  "Had better handle two plus one" ~:
    cartesian [Set [1,7], Set [5]] ~?= [Tuple [1,5], Tuple [7,5]],

  "Accept THIS" ~:
    cartesian [Set [1, 2, 3], Set [4], Set [5, 6], Set [7, 8]] ~?=
      [Tuple [1, 4, 5, 7], Tuple [1, 4, 5, 8], Tuple [1, 4, 6, 7], Tuple [1, 4, 6, 8],
       Tuple [2, 4, 5, 7], Tuple [2, 4, 5, 8], Tuple [2, 4, 6, 7], Tuple [2, 4, 6, 8],
       Tuple [3, 4, 5, 7], Tuple [3, 4, 5, 8], Tuple [3, 4, 6, 7], Tuple [3, 4, 6, 8]
      ]
  ]

Cartesian.hs

module Cartesian
where

data Set a = Set [a]
data Tuple a = Tuple [a]
  deriving (Show, Eq)

cartesian :: [Set a] -> [Tuple a]
cartesian sets = foldl distribute [Tuple []] sets 
      
distribute :: [Tuple a] -> Set a -> [Tuple a]
distribute tuples (Set ys) = concatMap (\(Tuple zs) -> map (\e -> Tuple (zs ++ [e])) ys) tuples