Nekops-Nu Sequences

Nekops-Nu Sequences (the lazy way)

[Go to the original problem at Hackerrank]

Problem statement

 

Nekops-Nu sequence

A Nekops-Nu sequence is no more than a run-length encoding (RLE). You take a sequence and for each run of identical numbers, you output the number of repetitions and the number itself.

The sequence thus generated can be itself run-length encoded. By applying the RLE recursively we can generate a sequence of sequences.

 

Input

The input consists of one line with numbers separated by spaces. The first number, N, is the number of sequences to compute (i.e, how many times we have to apply the RLE function). The remaining numbers are the starting sequence.

 

Output

First line of the output should consist of the original sequence. The second line is the RLE of the original sequence. The second line is the RLE of the RLE of the original sequence... you get it? The last line must contain the number of elements of the last sequence. The output must have N+2 lines.

 As an additional annoyance, we are told that the sequences must be center aligned, and padded with "." characters to the width of the longest one.

Original problem statement

 

This [pdf] is the problem, as it was posted in the competition.

Solution

 

RLE in python

The first step is googling "python RLE". This stackoverflow question mentions the groupby() function which (almost) does what we want:

def neknu(s):
    nk = []
    for d, l in groupby(s):
        nk.append(len(list(l)))
        nk.append(d)

    return nk

 

Centering

Another easy one. The builtin str class has a center() method that lets us specify the padding character. Not only that: if it has to add an odd number of padding characters, the left side will have one more character than the right side, just as required by the challenge:

longest = max(len(s) for s in Seqs)
print "\n".join(s.center(longest, '.') for s in Seqs)

The Code

# Nekops-Nu sequences, by Juan I. Carrano | IEEEXtreme 8.0 (2014)

from itertools import groupby

sk, p, sseq = raw_input().partition(' ')

k = int(sk)
seq0 = [int(n) for n in sseq.split()]

Seqs = [" ".join(str(s) for s in seq0)]

def neknu(s):
    nk = []
    for d, l in groupby(s):
        nk.append(len(list(l)))
        nk.append(d)

    return nk

lastl = len(seq0)

for dummy in xrange(k):
    seq0 = neknu(seq0)
    lastl = len(seq0)
    Seqs.append(" ".join(str(s) for s in seq0))

longest = max(len(s) for s in Seqs)

print "\n".join(s.center(longest, '.') for s in Seqs)
print lastl

Files

The solution, testcases and  original problem statement are available at this Drive folder.