Hackerrank: Absolute Permutation - How do I make this code more efficient

Question

The problem is basically this: Return the permutation of the set of the first n natural numbers which satisfies the following property:

|pos(i) - i| = k
∀ i ∈ (1,n)
where pos(i) is the ith number in the permutation

If no such permutation exists, return -1.

Note: the input is the integer n.

The full problem is on HackerRank.

The code for the main algorithm:

try:
    for y in g.keys():
        g[y] = [y-k,y+k]
        if y - k <=0:
            g[y].remove(y-k)
        if y + k > n:
            g[y].remove(y+k)

    d = []
    for y in range(1,n+1):
        if len(g[y]) == 1:
            if g[y][0] not in d:
                d.append(g[y][0])
        if len(g[y]) == 2:
            if g[y][0] not in d:
                d.append(g[y][0])
                   
        
    if len(set(d)) == len(d) and len(d) == n:
        return d
    else:
        return [-1]
except:
    return [-1]

g is a previously defined dictionary containing the first n natural numbers as keys with each key initially being assigned a value of 0

the first block changes the value of the key y to the possible numbers that could be at position y in the permutation, namely, y - k or y + k

d is the list that will contain the final permutation. If the value for i in g has only one number, then that number is added to d. If it contains 2 numbers, the first number is added by default. If the first number is already in d, the second number is added. d is printed if, finally, d contains n elements and there are no repeating elements.

On hackerrank, 9 of the 13 test cases are successful, but the last 4 return a timeout error. I've run through the code step by step and it's clear that the second block is taking way too long for larger numbers. I know using list comprehension would make it faster, but I have no idea how to convert that into list comprehension.

How do I make this code more efficient?

Answer 1

You test not in d, where d is a list. That's slow. Use an additional set for those membership tests.

Simpler way: Note that the number 1 must go to position 1+k. It has nowhere else to go. Also, the only number that can go to position 1 is the number 1+k. So numbers 1 and 1+k must switch places. Similarly, the numbers 2 and 2+k must switch places (unless k<2). And so on. The entire first k numbers must switch with the next k numbers.

After that, the reasoning repeats, numbers (2k+1) and (2k+1)+k must switch. The entire third chunk of k numbers must switch with the fourth chunk of k numbers. And so on.

In other words, numbers in the first, third, fifth, etc chunk of k numbers must move k positions to the right and numbers in the other chunks of k numbers must move k positions to the left. In yet other words, add k to the odd-numbered chunks and subtract k from the even-numbered chunks.

A solution that tries to build it and discards it if it's invalid:

def absolutePermutation(n, k):
    p = [i+1 + (-k if k and i//k%2 else k) for i in range(n)]
    return p if max(p) == n else [-1]

Shorter but slower (still accepted):

def absolutePermutation(n, k):
    p = [i+1 + k*(-1)**(k and i//k) for i in range(n)]
    return p if max(p) == n else [-1]

Alternatively, check whether it'll work and build it only if it will. It will iff there's an even number of complete k-chunks, i.e., if n is divisible by 2k:

def absolutePermutation(n, k):
    if k == 0:
        return range(1, n+1)
    if n % (2*k):
        return [-1]
    return [i+1 + k*(-1)**(k and i//k) for i in range(n)]

Yet another, starting with the identity permutation and then swapping slices:

def absolutePermutation(n, k):
    K = 2 * k
    if k and n % K:
        return [-1]
    p = list(range(1, n+1))
    for i in range(k):
        p[i::K], p[i+k::K] = p[i+k::K], p[i::K]
    return p

A longer but quite nice version using the grouper recipe to give us the chunks:

def absolutePermutation(n, k):
    numbers = range(1, n+1)
    if k == 0:
        yield from numbers
    elif n % (2*k):
        yield -1
    else:
        chunks = grouper(numbers, k)
        for chunk in chunks:
            yield from next(chunks)
            yield from chunk

Answer 2

Many programming puzzles of this sort can be solved without brute-force computations if you can figure out the pattern. Rather than trying to implement a solution to the puzzle, it's often helpful to write some temporary code just to explore. The small script below does that. For each list size from 1 through max_n, we find the permutations having valid solutions, along with the corresponding k values.

Some patterns jump about pretty quickly. Odd-sized lists appear to support only k=0. Even-sized lists are interesting: take a close look, for example, at sizes 6 and 8.

import sys
from itertools import permutations

def main():
    max_n = int(sys.argv[1])
    fmt = '{:<6} {:<4} {}'
    div = '-' * 40
    print(fmt.format('SIZE', 'K', 'PERM'))
    for size in range(1, max_n + 1):
        print(div)
        for tup in permutations(range(1, size + 1)):
            diffs = [abs(j + 1 - x) for j, x in enumerate(tup)]
            ds = sorted(set(diffs))
            if len(ds) == 1:
                k = ds[0]
                print(fmt.format(size, k, tup))

main()

Output for max_n=9:

SIZE   K    PERM
----------------------------------------
1      0    (1,)
----------------------------------------
2      0    (1, 2)
2      1    (2, 1)
----------------------------------------
3      0    (1, 2, 3)
----------------------------------------
4      0    (1, 2, 3, 4)
4      1    (2, 1, 4, 3)
4      2    (3, 4, 1, 2)
----------------------------------------
5      0    (1, 2, 3, 4, 5)
----------------------------------------
6      0    (1, 2, 3, 4, 5, 6)
6      1    (2, 1, 4, 3, 6, 5)
6      3    (4, 5, 6, 1, 2, 3)
----------------------------------------
7      0    (1, 2, 3, 4, 5, 6, 7)
----------------------------------------
8      0    (1, 2, 3, 4, 5, 6, 7, 8)
8      1    (2, 1, 4, 3, 6, 5, 8, 7)
8      2    (3, 4, 1, 2, 7, 8, 5, 6)
8      4    (5, 6, 7, 8, 1, 2, 3, 4)
----------------------------------------
9      0    (1, 2, 3, 4, 5, 6, 7, 8, 9)