Search code examples
scalafunctional-programmingpointfree

find unique matrices from a larger matrix

I'm fairly new the functional programming, so I'm going through some practice exercises. I want to write a function, given a matrix of unique naturals, let's say 5x5, return a collection of unique matrices of a smaller size, say 3x3, where the matrices must be intact, i.e. created from values that are adjacent in the original.

01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Simple. Just slide across, then down, one by one in groups of 3, to get something that looks like:

01 02 03 | 02 03 04 | 03 04 05 | 06 07 08
06 07 08 | 07 08 09 | 08 09 10 | 11 12 13
11 12 13 | 12 13 14 | 13 14 15 | 16 17 18

or, in Scala,

List(List(1, 2, 3), List(6, 7, 8), List(11, 12, 13))
List(List(2, 3, 4), List(7, 8, 9), List(12, 13, 14))
List(List(3, 4, 5), List(8, 9, 10), List(13, 14, 15))
List(List(6, 7, 8), List(11, 12, 13), List(16, 17, 18))

and so on and so on...

So I venture out with Scala (my language of choice because it allows me to evolve from imperative to functional, and I've spent the last few years in Java.

val array2D = "01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25".grouped(3).map(_.trim.toInt).grouped(5)
val sliced = array2D.map(row => row.sliding(3, 1).toList).sliding(3, 1).toList

Now I have a data structure I can work with, but I don't see a functional way. Sure I can traverse each piece of sliced, create a var matrix = new ListBuffer[Seq[Int]]() and imperatively create a bag of those and I'm done.

I want to find a functional, ideally point-free approach using Scala, but I'm stumped. There's got to be a way to zip with 3 or something like that... I've searched the ScalaDocs and can't seem to figure it out.

Solution

  • You got halfway there. In fact, I was having trouble figuring out how to do what you had done already. I broke up your code a bit to make it easier to follow. Also, I made array2D a List, so I could play with the code more easily. :-)

    val input = "01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25"
val intArray = (input split " " map (_.toInt) toList)
val array2D = (intArray grouped 5 toList)
val sliced = array2D.map(row => row.sliding(3, 1).toList).sliding(3, 1).toList

    Ok, so you have a bunch of lists, each one a bit like this:

    List(List(List( 1,  2,  3), List( 2,  3,  4), List( 3,  4,  5)), 
     List(List( 6,  7,  8), List( 7,  8,  9), List( 8,  9, 10)), 
     List(List(11, 12, 13), List(12, 13, 14), List(13, 14, 15)))

    And you want them like this:

    List(List(List(1, 2, 3), List(6, 7,  8), List(11, 12, 13)), 
     List(List(2, 3, 4), List(7, 8,  9), List(12, 13, 14)), 
     List(List(3, 4, 5), List(8, 9, 10), List(13, 14, 15)))

    Does that feel right to you? Each of the three sublists is a matrix on its own:

    List(List(1, 2, 3), List(6, 7,  8), List(11, 12, 13))

    is

    01 02 03
06 07 08
11 12 13

    So, basically, you want to transpose them. The next step, then, is:

    val subMatrices = sliced map (_.transpose)

    The type of that thing is List[List[List[Seq[Int]]]]. Let's consider that a bit... The 2D matrix is represented by a sequence of a sequence, so List[Seq[Int]] corresponds to a matrix. Let's say:

    type Matrix = Seq[Seq[Int]]
val subMatrices: List[List[Matrix]] = sliced map (_.transpose)

    But you want one one list of matrices, so you can flatten that:

    type Matrix = Seq[Seq[Int]]
val subMatrices: List[Matrix] = (sliced map (_.transpose) flatten)

    But, alas, a map plus a flatten is a flatMap:

    type Matrix = Seq[Seq[Int]]
val subMatrices: List[Matrix] = sliced flatMap (_.transpose)

    Now, you want the unique submatrices. That's simple enough: it's a set.

    val uniqueSubMatrices = subMatrices.toSet

    Or, if you wish to keep the result as a sequence,

    val uniqueSubMatrices = subMatrices.distinct

    And that's it. Full code just to illustrate:

    type Matrix = Seq[Seq[Int]]
val input = "01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25"
val intArray = (input split " " map (_.toInt) toList)
val array2D: Matrix = (intArray grouped 5 toList)
val sliced: List[List[Matrix]] = (array2D map (row => row sliding 3 toList) sliding 3 toList)
val subMatrices: List[Matrix] = sliced flatMap (_.transpose)
val uniqueSubMatrices: Set[Matrix] = subMatrices.toSet

    It could be written as a single expression, but unless you break it up into functions, it's going to be horrible to read. And you'd either have to use the forward pipe (|>, not in the standard library), or add these functions implicitly to the types they act on, or it will be difficult to read anyway.