Transposing List of Lists

Problem #224

Tags: scheme data-structures special c-1 c-0

Who solved this?

No translations... yet

This problem is to be solved with Scheme interpreter - you may want to solve Introducing Scheme before, to get more details, or check instructions on using Scheme once more.

Languages of LISP family are famous for their dynamic data-structures built of pairs (called conses). In this problem we are going to manipulate such structures, i.e. combining conses in various ways.

Also, as this problem deals a lot with loops, note that Scheme has several ways of expressing them. However generally we prefer to use tail-recursive calls - which could be expressed directly or, more popularly, with the named let form.

Problem Statement

Regard list of lists. In interpreter it could be represented as following (note apostrophe):

'((1 2 3 4)(5 6 7 8)(9 10 11 12))

Suppose it represents a matrix (each nested list is a row). For matrix we know "transposition" operation, which replaces rows with columns (e.g. as flipping around diagonal):

      | 1   2   3   4 |               | 1   5   9 |
A  =  | 5   6   7   8 |       A'  =   | 2   6  10 |
      | 9  10  11  12 |               | 3   7  11 |
                                      | 4   8  12 |

Here A' denotes the transposed matrix (as in Matlab/Octave). Now write it back as another list of lists:

'((1 5 9)(2 6 10)(3 7 11)(4 8 12))

Your goal is to describe function (transpose x) which performs such operation. As the list of lists, unlike matrix, can have "rows" of different lengths, we extend the transposition operation:

  1. If original list consisted of N nested lists, then result should consist of unknown-beforehand amount of nested lists, each of them having N elements (last could be shorter).
  2. The process consists of two phases: "unwrapping" the input list-of-lists into single long list - and then "splitting" this long list into chunks of N elements (to construct result of them).
  3. Unwrapping goes by removal of 1st elements from every nested list in order, then removing all 2nd elements (really they become new firsts) and so on. If any of the nested list becomes empty before others, it is removed from the outer list.

For example, regard an input like this:

'((1 2 3 4) (5) (6 7 8))

We start "unwrapping" it, taking firstly elements 1, 5 and 6 from heads of nested lists. Note that second list becomes empty and we remove it. Next we take 2 and 6 and so on, resluting in:

'(1 5 6 2 7 3 8 4)

Now, as we initially had 3 nested lists, we should split this into chunks of 3 to create result:

`((1 5 6) (2 7 3) (8 4))

While this operation looks queer at first glance, it often happens for example in the case of processing several queues of equal priorities, or arranging results of several goods recommenders into single relevance list.

Input / Output

There should be no console input or output. The code just should have function definition. There could be additional useful function defines - but avoid leaving any executable statements outside of definitions, they may spoil the checking process.

Checker verifies your function returns list of lists first of all, and then their content. So you may start with trivial implementation returning empty list:

(define (transpose x)
    (list))
You need to login to get test data and submit solution.