Group matrix 9x9 elements into 3 row by 3 cols in Scala

Question

Let's say i have the following matrix:


val grid = Array(
  Array( 1, 2, 3,  4, 5, 6,  7, 8, 9), 
  Array(11,12,13, 14,15,16, 17,18,19), 
  Array(21,22,23, 24,25,26, 27,28,29), 

  Array(31,32,33, 34,35,36, 37,38,39), 
  Array(41,42,43, 44,45,46, 47,48,49), 
  Array(51,52,53, 54,55,56, 57,58,59), 

  Array(61,62,63, 64,65,66, 67,68,69), 
  Array(71,72,73, 74,75,76, 77,78,79), 
  Array(81,82,83, 84,85,86, 87,88,89)
)

How can i, preferably in functional way, convert them this matrix:


val gridWithFields = Array(
  Array(1,2,3, 11,12,13, 21,22,23),
  Array(4,5,6, 14,15,16, 21,22,23),
  Array(7,8,9, 17,18,19, 27,28,29),
  ... 
)

*Updated*
I've done some benchmarking, but not sure wether memory result are correct or not. Any way here they are:

@maxmc for's solution

alg1 in Cycles: 10    Time: 2712683ns Memory: 459572
alg1 in Cycles: 100   Time: 914297ns  Memory: 458191
alg1 in Cycles: 1000  Time: 85102ns   Memory: 457944
alg1 in Cycles: 10000 Time: 68742ns   Memory: 457943

@Daniel C. Sobral solution

alg2 in Cycles: 10    Time: 3747031ns Memory: 458889
alg2 in Cycles: 100   Time: 1796564ns Memory: 457951
alg2 in Cycles: 1000  Time: 186215ns  Memory: 457220
alg2 in Cycles: 10000 Time: 122642ns  Memory: 456708

@Or Peles solution

alg3 in Cycles: 10    Time: 741475ns Memory: 457472
alg3 in Cycles: 100   Time: 542181ns Memory: 457914
alg3 in Cycles: 1000  Time: 248020ns Memory: 457911
alg3 in Cycles: 10000 Time: 119105ns Memory: 457919

@Hbf solution

alg4 in Cycles: 10    Time: 179093ns Memory: 457472
alg4 in Cycles: 100   Time: 121072ns Memory: 457069
alg4 in Cycles: 1000  Time: 78123ns  Memory: 456719
alg4 in Cycles: 10000 Time: 75948ns  Memory: 455913

@Eastsun solution

alg5 in Cycles: 10    Time: 144037ns Memory: 457512
alg5 in Cycles: 100   Time: 40672ns  Memory: 457059
alg5 in Cycles: 1000  Time: 42236ns  Memory: 456119
alg5 in Cycles: 10000 Time: 46480ns  Memory: 455952

I've tested it on MacMini(2012). Memory results are realy strange, so sources are here, if there are some bad mistakes and anti-patterns please tell me =) https://github.com/Stimphonier/MatrixBench

I suppose that instead of `Array(4,5,6, 14,15,16, 21,22,23)` you meant `Array(4,5,6, 14,15,16, 24,25,26)` and that the `...` in the end should actually be three `...`'s after each inner array, right? — Hbf, Feb 26 '13 at 14:11
see also http://stackoverflow.com/questions/5193781/java-scala-library-for-algebra-mathematics — oluies, Feb 26 '13 at 15:19
It would be great if you quickly benchmarked (time, maybe also memory consumption) the various proposed solutions and reported on the results. It shouldn't take long and it would definitely be helpful for the community. — Malte Schwerhoff, Feb 27 '13 at 09:19
@mhs I've done some benchmarking, but not sure if the results are correct — 4lex1v, Feb 27 '13 at 12:14
@Alexlv: You shoud put `System.gc(); Thread.sleep(1000);System.gc(); Thread.sleep(1000)` at the begin of your `time` method to make the Memory result more exact. — Eastsun, Feb 27 '13 at 13:31
@Eastsun Yes, that works much better, but takes time. I'll update bit later — 4lex1v, Feb 27 '13 at 13:47
Fixed memory results, still not 100% correct, but hardcore benching takes too much time. — 4lex1v, Feb 28 '13 at 06:39

score 4 · Answer 1 · answered Feb 26 '13 at 14:43

4

The 'for' approach:

for(x <- 0 until 9 by 3) yield
  (for {
    row <- 0 until 9;
    col <- x until x + 3 by 3;
    i <- col until col + 3
  } yield grid(row)(i)).toArray

answered Feb 26 '13 at 14:43

maxmc

4,218
1
25
21

score 4 · Answer 2 · answered Feb 26 '13 at 14:49

Group and transpose. I'm going to show the REPL session where I figured out the correct order.

First thing, there's a grouping in your data -- which you clearly indicated with spaces. Every three lines, and inside each line every three element. So the first thing we want to do is make the grouping explicit.

scala> grid.map(row => (row grouped 3).toArray)
res7: Array[Array[Array[Int]]] = Array(Array(Array(1, 2, 3), Array(4, 5,
 6), Array(7, 8, 9)), Array(Array(11, 12, 13), Array(14, 15, 16), Array(
17, 18, 19)), Array(Array(21, 22, 23), Array(24, 25, 26), Array(27, 28,
29)), Array(Array(31, 32, 33), Array(34, 35, 36), Array(37, 38, 39)), Ar
ray(Array(41, 42, 43), Array(44, 45, 46), Array(47, 48, 49)), Array(Arra
y(51, 52, 53), Array(54, 55, 56), Array(57, 58, 59)), Array(Array(61, 62
, 63), Array(64, 65, 66), Array(67, 68, 69)), Array(Array(71, 72, 73), A
rray(74, 75, 76), Array(77, 78, 79)), Array(Array(81, 82, 83), Array(84,
 85, 86), Array(87, 88, 89)))

scala> (res7 grouped 3).toArray
res8: Array[Array[Array[Array[Int]]]] = Array(Array(Array(Array(1, 2, 3)
, Array(4, 5, 6), Array(7, 8, 9)), Array(Array(11, 12, 13), Array(14, 15
, 16), Array(17, 18, 19)), Array(Array(21, 22, 23), Array(24, 25, 26), A
rray(27, 28, 29))), Array(Array(Array(31, 32, 33), Array(34, 35, 36), Ar
ray(37, 38, 39)), Array(Array(41, 42, 43), Array(44, 45, 46), Array(47,
48, 49)), Array(Array(51, 52, 53), Array(54, 55, 56), Array(57, 58, 59))
), Array(Array(Array(61, 62, 63), Array(64, 65, 66), Array(67, 68, 69)),
 Array(Array(71, 72, 73), Array(74, 75, 76), Array(77, 78, 79)), Array(A
rray(81, 82, 83), Array(84, 85, 86), Array(87, 88, 89))))

Let's see if we got it right:

scala> res8(0)
res9: Array[Array[Array[Int]]] = Array(Array(Array(1, 2, 3), Array(4, 5,
 6), Array(7, 8, 9)), Array(Array(11, 12, 13), Array(14, 15, 16), Array(
17, 18, 19)), Array(Array(21, 22, 23), Array(24, 25, 26), Array(27, 28,
29)))

Yes, that's exactly the unit of data we want to transform. Let's try it out:

scala> res9.transpose
res10: Array[Array[Array[Int]]] = Array(Array(Array(1, 2, 3), Array(11,
12, 13), Array(21, 22, 23)), Array(Array(4, 5, 6), Array(14, 15, 16), Ar
ray(24, 25, 26)), Array(Array(7, 8, 9), Array(17, 18, 19), Array(27, 28,
 29)))

As desired! So let's do it to the whole matrix:

scala> res8 map (_.transpose)
res11: Array[Array[Array[Array[Int]]]] = Array(Array(Array(Array(1, 2, 3
), Array(11, 12, 13), Array(21, 22, 23)), Array(Array(4, 5, 6), Array(14
, 15, 16), Array(24, 25, 26)), Array(Array(7, 8, 9), Array(17, 18, 19),
Array(27, 28, 29))), Array(Array(Array(31, 32, 33), Array(41, 42, 43), A
rray(51, 52, 53)), Array(Array(34, 35, 36), Array(44, 45, 46), Array(54,
 55, 56)), Array(Array(37, 38, 39), Array(47, 48, 49), Array(57, 58, 59)
)), Array(Array(Array(61, 62, 63), Array(71, 72, 73), Array(81, 82, 83))
, Array(Array(64, 65, 66), Array(74, 75, 76), Array(84, 85, 86)), Array(
Array(67, 68, 69), Array(77, 78, 79), Array(87, 88, 89))))

And now we only have to flatten it back. We need to flatten it in the reverse order in which we grouped it:

scala> res11.flatten
res12: Array[Array[Array[Int]]] = Array(Array(Array(1, 2, 3), Array(11,
12, 13), Array(21, 22, 23)), Array(Array(4, 5, 6), Array(14, 15, 16), Ar
ray(24, 25, 26)), Array(Array(7, 8, 9), Array(17, 18, 19), Array(27, 28,
 29)), Array(Array(31, 32, 33), Array(41, 42, 43), Array(51, 52, 53)), A
rray(Array(34, 35, 36), Array(44, 45, 46), Array(54, 55, 56)), Array(Arr
ay(37, 38, 39), Array(47, 48, 49), Array(57, 58, 59)), Array(Array(61, 6
2, 63), Array(71, 72, 73), Array(81, 82, 83)), Array(Array(64, 65, 66),
Array(74, 75, 76), Array(84, 85, 86)), Array(Array(67, 68, 69), Array(77
, 78, 79), Array(87, 88, 89)))

scala> res12.map(_.flatten)
res13: Array[Array[Int]] = Array(Array(1, 2, 3, 11, 12, 13, 21, 22, 23),
 Array(4, 5, 6, 14, 15, 16, 24, 25, 26), Array(7, 8, 9, 17, 18, 19, 27,
28, 29), Array(31, 32, 33, 41, 42, 43, 51, 52, 53), Array(34, 35, 36, 44
, 45, 46, 54, 55, 56), Array(37, 38, 39, 47, 48, 49, 57, 58, 59), Array(
61, 62, 63, 71, 72, 73, 81, 82, 83), Array(64, 65, 66, 74, 75, 76, 84, 8
5, 86), Array(67, 68, 69, 77, 78, 79, 87, 88, 89))

Or, as a one liner:

grid.map(_.grouped(3).toArray).grouped(3).toArray.map(_.transpose).flatten.map(_.flatten)

Thank you for you explanation, didn't know about transpose method =) — 4lex1v, Feb 28 '13 at 06:39

Malte Schwerhoff · Answer 3 · 2013-02-26T14:34:21.930

val n: Array[Array[Int]] =
  grid.grouped(3)
      .toArray
      .flatMap(_.map(_.grouped(3).toArray)
                .transpose
                .map(_.flatten))

n.foreach(r => {r.foreach(e => print(e + " ")); println})

// 1 2 3 11 12 13 21 22 23 
// 4 5 6 14 15 16 24 25 26 
// 7 8 9 17 18 19 27 28 29 
// 31 32 33 41 42 43 51 52 53 
// 34 35 36 44 45 46 54 55 56 
// 37 38 39 47 48 49 57 58 59 
// 61 62 63 71 72 73 81 82 83 
// 64 65 66 74 75 76 84 85 86 
// 67 68 69 77 78 79 87 88 89

It should be possible to remove the explicit toArray calls by putting a corresponding implicit def into scope.

score 2 · Answer 4 · answered Feb 26 '13 at 14:26

What about this?

type Grid = Array[Array[Int]]

def transform(grid: Grid): Grid = {
  def transformLine(grid: Grid) =
    grid.map(_.grouped(3).toArray).transpose.map(_.flatten)
  grid.grouped(3).flatMap(transformLine).toArray
}

scala> transform(grid) map(_.deep) foreach println
Array(1, 2, 3, 11, 12, 13, 21, 22, 23)
Array(4, 5, 6, 14, 15, 16, 24, 25, 26)
Array(7, 8, 9, 17, 18, 19, 27, 28, 29)
Array(31, 32, 33, 41, 42, 43, 51, 52, 53)
Array(34, 35, 36, 44, 45, 46, 54, 55, 56)
Array(37, 38, 39, 47, 48, 49, 57, 58, 59)
Array(61, 62, 63, 71, 72, 73, 81, 82, 83)
Array(64, 65, 66, 74, 75, 76, 84, 85, 86)
Array(67, 68, 69, 77, 78, 79, 87, 88, 89)

Totally inefficient because of a lot of implicit conversions and intermediate results, but it is functional and shouldn't be a problem unless you need to do it hundreds of times in a second...

Eastsun · Accepted Answer · 2013-02-27T04:00:11.160

Here it is, a short and efficient solution, may be the shortest and most efficient one:

scala> val matrix = Array.tabulate(9, 9){ (r, c) => grid(r/3*3+c/3)(r%3*3+c%3) }
matrix: Array[Array[Int]] = 
Array(Array(1, 2, 3, 11, 12, 13, 21, 22, 23), 
      Array(4, 5, 6, 14, 15, 16, 24, 25, 26), 
      Array(7, 8, 9, 17, 18, 19, 27, 28, 29), 
      Array(31, 32, 33, 41, 42, 43, 51, 52, 53), 
      Array(34, 35, 36, 44, 45, 46, 54, 55, 56), 
      Array(37, 38, 39, 47, 48, 49, 57, 58, 59), 
      Array(61, 62, 63, 71, 72, 73, 81, 82, 83), 
      Array(64, 65, 66, 74, 75, 76, 84, 85, 86), 
      Array(67, 68, 69, 77, 78, 79, 87, 88, 89)
)

Thanks, really liked your solution – 4lex1v Feb 28 '13 at 06:29 — 4lex1v, Feb 28 '13 at 06:29

score 1 · Answer 6 · answered Feb 26 '13 at 14:10

Quick and dirty (but functional) hack:

(0 until grid(0).size/3).toArray.
  map(i =>
    grid.flatMap(a => a.drop(i*3).take(3))
  )

For the grid you are providing, this yields:

Array(
  Array(1, 2, 3, 11, 12, 13, 21, 22, 23, /*...*/, 71, 72, 73, 81, 82, 83),
  Array(4, 5, 6, 14, 15, 16, 24, 25, 26, /*...*/, 74, 75, 76, 84, 85, 86), 
  Array(7, 8, 9, 17, 18, 19, 27, 28, 29, /*...*/, 77, 78, 79, 87, 88, 89)
)

score 1 · Answer 7 · answered Feb 26 '13 at 14:36

In a single line:

grid.grouped(3).map(g => g.transpose.grouped(3).map(_.flatten.sorted)).flatten.toArray

res25: Array[Array[Int]] = Array(Array(1, 2, 3, 11, 12, 13, 21, 22, 23), Array(4 , 5, 6, 14, 15, 16, 24, 25, 26), Array(7, 8, 9, 17, 18, 19, 27, 28, 29), Array(3 1, 32, 33, 41, 42, 43, 51, 52, 53), Array(34, 35, 36, 44, 45, 46, 54, 55, 56), A rray(37, 38, 39, 47, 48, 49, 57, 58, 59), Array(61, 62, 63, 71, 72, 73, 81, 82, 83), Array(64, 65, 66, 74, 75, 76, 84, 85, 86), Array(67, 68, 69, 77, 78, 79, 87 , 88, 89))

Group matrix 9x9 elements into 3 row by 3 cols in Scala

7 Answers7