Codility Iota 2011 Coding Challenge - ShortestAdjSeq

Posted on Nov 25

Today, let’s challenge ourselves with Codility’s Iota 2011 challenge. The details of the challenge are in the link (I can’t copy them here because of copyright :) ).

Essentially, we are playing something very similar to the board game Dominoes. We are given an initial and final numbers, and a set of dominoes tiles (that is, pairs of numbers, that can be placed in both directions), and we have to find the length of the minimum set of matching tiles that connects the initial and the final number. The only rule, like in Dominoes, is that only tiles with matching adjacent values can be placed next to each other.


After building a lookup table for the Dominoes tiles (the adjacent numbers), we can quickly solve this by building incrementally the set of values that we can reach, and keeping track of how many steps it costed us to get there (classic dynamic programming :).

Here’s the code that can do that in O(N·log(N)) time, and O(N) space. It passes Codility’s testing framework.

def solution(A):
    # Check for corner case
    if A[0] == A[-1]:
        return 1

    # Build lookup table for adjacent values
    adjacent = {}
    previous = None
    for a in A:
        if previous:
            for first, second in [(a, previous), (previous, a)]:
                s = adjacent.get(first, set())
                adjacent[first] = s
        previous = a

    # Build reachability set
    reachability = {A[0]: 1}
    just_added = set([A[0]])
    while True:
        # round
        just_added_this_round = set()
        while just_added:
            element = just_added.pop()
            distance = reachability[element]
            for next_element in adjacent[element]:
                if next_element in reachability:
                if next_element == A[-1]:
                    return distance + 1
                reachability[next_element] = distance + 1
        just_added = just_added_this_round

if __name__ == '__main__':
    print 'Testing...'
    assert solution([1, 10, 6, 5, 10, 7, 5, 2]) == 4
    assert solution([1, 5, 3, 5, 9, 7, 5, 2, 4]) == 4
    assert solution([1, 1, 5, 3, 1]) == 1
    print 'Ok!'

comments powered by Disqus