12/31/14

Codility ‘StoneWall’ Solution

Short Problem Definition:

Cover “Manhattan skyline” using the minimum number of rectangles.

Link

StoneWall

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

The explanation to this challenge has been posted on the Codility web, you can read it here.

Solution:
def solution(H):
    block_cnt = 0
    
    stack = []
    
    for height in H:
        # remove all blocks that are bigger than my height
        while len(stack) != 0 and stack[-1] > height:
            stack.pop()
        
        if len(stack) != 0 and stack[-1] == height:
            # we already paid for this size
            pass
        else:
            # new block is required, push it's size to the stack
            block_cnt += 1
            stack.append(height)
            
    return block_cnt

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
12/30/14

Codility ‘MaxDoubleSliceSum’ Solution

Short Problem Definition:

Find the maximal sum of any double slice.

Link

MaxDoubleSliceSum

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

To solve this task, you need to keep track of two slice arrays. The optimal double slice can be found at an index that has the maximal sum of those two arrays. It can not be the 0th or the last index.

Solution:
def solution(A):
    ending_here = [0] * len(A)
    starting_here = [0] * len(A)
    
    for idx in xrange(1, len(A)):
        ending_here[idx] = max(0, ending_here[idx-1] + A[idx])
    
    for idx in reversed(xrange(len(A)-1)):
        starting_here[idx] = max(0, starting_here[idx+1] + A[idx])
    
    max_double_slice = 0
    
    for idx in xrange(1, len(A)-1):
        max_double_slice = max(max_double_slice, starting_here[idx+1] + ending_here[idx-1])
        
        
    return max_double_slice

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
12/29/14

Codility ‘MaxSliceSum’ Solution

Short Problem Definition:

Find a maximum sum of a compact subsequence of array elements.

Link

MaxSliceSum

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

Can be solved by slightly adapting the golden_max_slice from the tutorial, not allowing empty slices.

Solution:
def golden_max_slice(A):
    max_ending = max_slice = -1000000
    for a in A:
        max_ending = max(a, max_ending +a)
        max_slice = max(max_slice, max_ending)
        
    return max_slice

def solution(A):
    return golden_max_slice(A)

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
12/28/14

Codility ‘FibFrog’ Solution

Short Problem Definition:

Count the minimum number of jumps required for a frog to get to the other side of a river.

Link

FibFrog

Complexity:

expected worst-case time complexity is O(N*log(N))

expected worst-case space complexity is O(N)

Execution:

This problem can be solved by in a Dynamic Programming way. You need to know the optimal count of jumps that can reach a given leaf. You get those by either reaching the leaf from the first shore or by reaching it from another leaf.

The N*log(N) time complexity is given by the fact, that there are approximately log(N) Fibonacci numbers up to N and you visit each position once.

As for the sequence hack: there are 26 Fibonacci numbers smaller than 100k, so I just preallocate an array of this size.

Solution:
def get_fib_seq_up_to_n(N):
    # there are 26 numbers smaller than 100k
    fib = [0] * (27)
    fib[1] = 1
    for i in xrange(2, 27):
        fib[i] = fib[i - 1] + fib[i - 2]
        if fib[i] > N:
            return fib[2:i]
        else:
            last_valid = i
    
    
    
def solution(A):
    # you can always step on the other shore, this simplifies the algorithm
    A.append(1)

    fib_set = get_fib_seq_up_to_n(len(A))
    
    # this array will hold the optimal jump count that reaches this index
    reachable = [-1] * (len(A))
    
    # get the leafs that can be reached from the starting shore
    for jump in fib_set:
        if A[jump-1] == 1:
            reachable[jump-1] = 1
    
    # iterate all the positions until you reach the other shore
    for idx in xrange(len(A)):
        # ignore non-leafs and already found paths
        if A[idx] == 0 or reachable[idx] > 0:
            continue

        # get the optimal jump count to reach this leaf
        min_idx = -1
        min_value = 100000
        for jump in fib_set:
            previous_idx = idx - jump
            if previous_idx < 0:
                break
            if reachable[previous_idx] > 0 and min_value > reachable[previous_idx]:
                min_value = reachable[previous_idx]
                min_idx = previous_idx
        if min_idx != -1:
            reachable[idx] = min_value +1

    return reachable[len(A)-1]

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
12/27/14

Codility ‘Ladder’ Solution

Short Problem Definition:

Count the number of different ways of climbing to the top of a ladder.

Link

Ladder

Complexity:

expected worst-case time complexity is O(L)

expected worst-case space complexity is O(L)

Execution:

We first compute the Fibonacci sequence for the first L+2 numbers. The first two numbers are used only as fillers, so we have to index the sequence as A[idx]+1 instead of A[idx]-1. The second step is to replace the modulo operation by removing all but the n lowest bits. A discussion can be found on Stack Overflow.

Solution:
def solution(A, B):
    L = max(A)
    P_max = max(B)
 
    fib = [0] * (L+2)
    fib[1] = 1
    for i in xrange(2, L + 2):
        fib[i] = (fib[i-1] + fib[i-2]) & ((1 << P_max) - 1)
 
    return_arr = [0] * len(A)
 
    for idx in xrange(len(A)):
        return_arr[idx] = fib[A[idx]+1] & ((1 << B[idx]) - 1)
 
    return return_arr

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
12/23/14

Codility ‘NumberSolitaire’ Solution

Short Problem Definition:

In a given array, find the subset of maximal sum in which the distance between consecutive elements is at most 6.

Link

NumberSolitaire

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

Prototypical Dynamic Programming. Remember all sub-solutions and use them to compute the next step. I prefixed the array by 6 min_values to use the same computation for the whole algorithm (besides the first). Do not forget to set the minimal_value small enough to handle a purely negative input array.

Solution:
NR_POSSIBLE_ROLLS = 6
MIN_VALUE = -10000000001

def solution(A):
    sub_solutions = [MIN_VALUE] * (len(A)+NR_POSSIBLE_ROLLS)
    sub_solutions[NR_POSSIBLE_ROLLS] = A[0]
    
    # iterate over all steps
    for idx in xrange(NR_POSSIBLE_ROLLS+1, len(A)+NR_POSSIBLE_ROLLS):
        max_previous = MIN_VALUE
        for previous_idx in xrange(NR_POSSIBLE_ROLLS):
            max_previous = max(max_previous, sub_solutions[idx-previous_idx-1])
        # the value for each iteration is the value at the A array plus the best value from which this index can be reached
        sub_solutions[idx] = A[idx-NR_POSSIBLE_ROLLS] + max_previous
    
    return sub_solutions[len(A)+NR_POSSIBLE_ROLLS-1]

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
12/22/14

Codility ‘WireBurnouts’ 2012 Psi Solution

Short Problem Definition:

While removing edges from a mesh grid, find the moment when there ceases to be a connection between opposite corners.

Link

WireBurnouts

Complexity:

expected worst-case time complexity is O(N2*log(N));

expected worst-case space complexity is O(N2)

Execution:

This problem screams for the use of a union-find. The hard part was to identify that union-find has no effective delete operation and you first need to add all remaining wires and start from the end. I created a wrapper class to effectively pack the input data into a set. Parsing the whole input for each union candidate (the not in burnouts part) would result in O(N²xN²). By using a set (hash O(1) in Python, RB-tree O(log(N)) in C++)   you are down to N² x log(N). The union operation is also guaranteed to be log(N).

Beware though. (0,0) is the bottom left corner. First coordinate is X (right) and second coordinate is Y(up). I, for some reason, am used for the first coordinate to describe the row(down).

You can view my complete task timeline here. How can someone solve this in 30 minutes? It took me longer to type the solution…

Solution:

Continue reading


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
12/18/14

Eclipse for C++ Development on Windows 7 64-bit Broken Console

It is the year 2014 and for some reason Eclipse CDT (both 32 and 64bit version) since Ganimede won’t output anything the programmer wants to print to the C++ console. The other side effect is, that it is impossible to start the gdb debugger. This problem has been posted all around the web since 2010 and yet it persists with Luna.

EmptySpace

I was able to compile the source using Eclipse, but had to switch to the Cygwin console and execute the binary manually. Doing this is a tedious process and wastes a lot of time. The bad news is, that I have found no solution for Cygwin. The good news is, that the MinGW linker will accept static gcc libraries linkage. So, for the rest of this guide, I will be assuming that you can use the MinGw GNU. Continue reading


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
12/14/14

Hard Work Over the Holidays

First of all, I would like to thank everyone who has subscribed to my blog and has been reading my posts.

I did not post during the last few weeks as I was on a much needed vacation in the beautiful country of Myanmar. If you ever wanted to get away from the internet, make this place your choice! Temples (and their music which you will start to hate), Buddhas (which you will count first and ignore afterwards), nowhere-else-to-be-found food (always with chicken) and floating gardens (floating food, how awesome is that!).

On my return I was contacted by Codility (whose challenges kinda became the main topic of my posts lately). As it happens, we, the bloggers, received a gift package (that made me more enthusiastic than it should). Yaaay! So here is the extremely bad photo I made today!

SupportCodility

So, without much talk, I should say that I have put myself to the task of completing the Solutions page over the holidays. There is not much to do anyways (besides overeating and watching Die Hard and Home Alone). At the time of writing, there are eight unfinished tasks (mostly because I do not know how to solve them) and one hell of a lot of Challenges that need to be posted. In contract to the tasks, I already have some of those solved.

Happy coding everyone!


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
12/12/14

Codility ‘ArrayInversionCount’ Solution

Short Problem Definition:

Compute number of inversion in an array.

Link

ArrayInversionCount

Complexity:

expected worst-case time complexity is O(N*log(N));

expected worst-case space complexity is O(N)

Execution:

Any sorting algorithm with a NlogN runtime will do the trick. It is important to count all (remaining) bigger elements on the left side. Do not forget to check for the maximal return value!

Solution:
MAX_NR = 1000000000

def mergeSort(alist):
    inversion_count = 0
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        inversion_count += mergeSort(lefthalf)
        if (inversion_count > MAX_NR):
            raise

        inversion_count += mergeSort(righthalf)
        if (inversion_count > MAX_NR):
            raise

        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i]<=righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
                inversion_count += len(lefthalf)-i
                if (inversion_count > MAX_NR):
                    raise
            k=k+1

        while i<len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1

    return inversion_count

def solution(A):
    try:
        return mergeSort(A)
    except:
        return -1

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin