Problem #224
Tags:
scheme
data-structures
special
c-1
c-0
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 cons
es).
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.
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:
N
nested lists, then result should consist of unknown-beforehand amount of
nested lists, each of them having N
elements (last could be shorter).N
elements (to construct result of them).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.
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))