The Goal
Rules
Warning! This sequence can make you ill. The reasoning is simple but unusual: Read a line aloud whilst looking at the line above and you will notice that each line (except the first) makes an inventory of the previous line.
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
... - Line 3 shows 2 1 because the line 2 contains two 1, one after the other.
- Line 4 displays 1 2 1 1 because the line 3 contains one 2 followed by one 1.
- Line 5 displays 1 1 1 2 2 1because the line 4 contains one 1followed by one 2 followed by two 1.
This sequence refers to a technique used to encode ranges in order to compress identical values without losing any information. This type of method is used, amongst others, to compress images.
Your mission is to write a program that will display the line L of this series on the basis of an original number R (R equals 1 in our example).
Game Input
Line 1: The original number R of the sequence.
Line 2: The line L to display. The index of the first line is 1.
0 < L ≤ 25
Bash Solution
We get two numbers \(R\) and \(L\), the number to start with and the number of iterations to perform. The solution is then a recursive concatination of the relevant numbers:
read R
read L
for ((i=1; i<$L; i++)); do
t=""
p=""
j=0
for c in $R; do
if [[ "$p" == "" ]]; then
p=$c
((j++))
elif [[ "$p" == "$c" ]]; then
((j++))
else
t="$t$j $p "
p=$c
j=1
fi
done
R="$t$j $c"
done
echo $R