Functional way to get a matrix from text

Question

I'm trying to solve some Google Code Jam problems, where an input matrix is typically given in this form:

2 3 #matrix dimensions
1 2 3 4 5 6 7 8 9 # all 3 elements in the first row
2 3 4 5 6 7 8 9 0 # each element is composed of three integers

where each element of the matrix is composed of, say, three integers. So this example should be converted to

#!scala
Array(
     Array(A(1,2,3),A(4,5,6),A(7,8,9),
     Array(A(2,3,4),A(5,6,7),A(8,9,0),
)

An imperative solution would be of the form

#!python
input = """2 3
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 0
"""
lines = input.split('\n')
class Aclass:
    def __init__(self,a,b,c):
        pass

print lines[0]
m,n = (int(x) for x in lines[0].split())
array = []
row = []
A = []
for line in lines[1:]:
    for elt in line.split():
        A.append(elt)
        if len(A)== 3:
            row.append(Aclass(A[0],A[1],A[2]))
            A = []
    array.append(row)
    row = []

from pprint import pprint
pprint(array)

A functional solution I've thought of is

#!scala
def splitList[A](l:List[A],i:Int):List[List[A]] = {
  if (l.isEmpty) return List[List[A]]()
  val (head,tail) = l.splitAt(i)
  return head :: splitList(tail,i)
}

def readMatrix(src:Iterator[String]):Array[Array[TrafficLight]] = {
  val Array(x,y) = src.next.split(" +").map(_.trim.toInt)
  val mat = src.take(x).toList.map(_.split(" ").
          map(_.trim.toInt)).
          map(a => splitList(a.toList,3).
                map(b => TrafficLight(b(0),b(1),b(2))
                 ).toArray
                ).toArray
    return mat
  }

But I really feel it's the wrong way to go because:

1. I'm using the functional List structure for each line, and then convert it to an array. The whole code seems much less efficeint
2. I find it longer less elegant and much less readable than the python solution. It is harder to which of the map functions operates on what, as they all use the same semantics.

What is the right functional way to do that?

Answer 1

Lets try this then... seems your not too woried about language, so I'll just describe the code for it.

so we shall have our function that takes in this string, and returns a multi-dimensional array.

The first thing the funciton needs to do is read the string until it gets a space, then convert this sub string into a int and store it as 'rows', then do the same again but store it as 'columns'.

Next, it will need to loop through the remainder of the string, reading out numbers and storing them as ints in an array.

Then it needs to calculate the amount of numbers per cell, which should be "rows * columns / numbers_of_ints" That divide should be the one that would say "16 / 5 = 3" not "16 / 5 = 1" or 16 / 5 = 3.2222...".

Then we create our our array of length rows, where each element is an array of length columsn, where each element is and array of length 'numbers per cell'. This 3D array lets us still access each and every number stored.

now we need to loop through each cell and put its numbers into it.

for(i = 0 ; i < rows ; i = i + 1)
{
  for(j = 0 ; j < columns ; j = j + 1)
  {
    for(k = 0 ; k < numbers_per_cell ; k = k + 1)
    {
      matrix[i][j][k] = numbers[( i * columns ) + j + k]
    }
  }
}

You should now have a matrix which contains all of our numbers as a single int stored some where with in the array.

should look like

Array(
  Array(Array(1,2,3),Array(4,5,6),Array(7,8,9),
  Array(Array(2,3,4),Array(5,6,7),Array(8,9,0),
)

Hope this helps you. I will update it if I need explain something better, or some one has a suggestion.

Answer 2

val x = """2 3
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 0
"""

val a = x split "\n" map (_.trim.split(" "))
val rows = a(0)(0).toInt
val columns = a(0)(1).toInt

val matrix = (a drop 1) map (_ grouped columns toList) toList

And to print the result:

matrix.map(_.map(_.mkString("(",",",")")).mkString("(",",",")")).mkString("\n")

res1: String =
((1,2,3),(4,5,6),(7,8,9))
((2,3,4),(5,6,7),(8,9,0))

with the assumptions:

assert(rows == matrix.length)
assert(matrix.forall(_.forall(_.size == columns))) 

To produce an array tabulate fits better:

val a = x split "\n" map (_.trim.split(" "))
val rows = a(0)(0).toInt
val columns = a(0)(1).toInt
val matrix = Array.tabulate(rows, a(1).size / columns, columns)(
  (i,j,k) => a(i +  1)(j * columns + k))

Answer 3

Here's a version that works on Scala 2.7:

val x = """2 3
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 0
"""

val a = x.trim split "\n" map (_.trim.split(" "))
val rows = a(0)(0).toInt
val columns = a(0)(1).toInt

def intervals(n: Int) = (Stream from (0, n)) zip (Stream from (n, n))

val matrix = (a drop 1) map (v =>
  intervals(v.size / columns) 
  take columns 
  map Function.tupled(v.subArray) 
  toArray
) toArray

val repr = matrix map (
  _ map (
    _ mkString ("Array(", ", ", ")")
  ) 
  mkString ("Array(", ", ", ")")
) mkString ("Array(\n\t", ",\n\t", "\n)")

println(repr)