12/31/14

# Codility ‘StoneWall’ Solution

##### Short Problem Definition:

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

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.

12/30/14

# Codility ‘MaxDoubleSliceSum’ Solution

##### Short Problem Definition:

Find the maximal sum of any double slice.

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 =  * len(A)
starting_here =  * 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.

12/29/14

# Codility ‘MaxSliceSum’ Solution

##### Short Problem Definition:

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

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.

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.

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 =  * (27)
fib = 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.

12/27/14

##### Short Problem Definition:

Count the number of different ways of climbing to the top of a 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 =  * (L+2)
fib = 1
for i in xrange(2, L + 2):
fib[i] = (fib[i-1] + fib[i-2]) & ((1 << P_max) - 1)

return_arr =  * 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.

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.

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

# 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.

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.

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:

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

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! 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.

12/12/14

# Codility ‘ArrayInversionCount’ Solution

##### Short Problem Definition:

Compute number of inversion in an array.

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.

12/11/14

# Codility ‘OddOccurrencesInArray’ Solution

##### Short Problem Definition:

Find value that occurs in odd number of elements.

OddOccurrencesInArray

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

This problem can be found in many algorithm books. A xor A cancels itself and B xor 0 is B. Therefore A xor A xor B xor C xor C is B.

##### Solution:
```def solution(A):
missing_int = 0
for value in A:
missing_int ^= value
return missing_int
```

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