HackerRank ‘Count Luck’ Solution

H
Short Problem Definition:

Hermione Granger is lost in the Forbidden Forest while collecting some herbs for a magical potion. The forest is magical and has only one exit point, which magically transports her back to the Hogwarts School of Witchcraft and Wizardry.

Link

Count Luck

Complexity:

time complexity is O(n)

space complexity is O(n)

Execution:

I solve this challenge using DFS and dynamic programming. I iterate over all n positions (denoted with .) using DFS. For each node, I remember the number of crossroads Hermione encountered up to that point. DFS does not guarantee to find the optimal solution in terms of path length.

Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#!/usr/bin/py
from collections import defaultdict
 
def hermionesWand(arr, K, max_x, max_y):
    # find both entry and exit points
    for idx, line in enumerate(arr):
        for inner_idx in xrange(len(line)):
            if line[inner_idx] == 'M':
                h = (idx, inner_idx)
            if line[inner_idx] == '*':
                e = (idx, inner_idx)
 
    st = [h]
    tracker = defaultdict(int)
    tracker[h] = 0
 
    # iterate the DFS list
    while st:
        curr = st.pop()
 
        # exit found
        if (curr == e):
            return tracker[curr] == K
 
        # save all exits that were not visited before
        inner_st = set()
        if (curr[0] > 0 and (arr[curr[0]-1][curr[1]] == "." or arr[curr[0]-1][curr[1]] == "*"))
        and (curr[0]-1, curr[1]) not in tracker:
            inner_st.add((curr[0]-1, curr[1]))
        if (curr[1] > 0 and (arr[curr[0]][curr[1]-1] == "." or arr[curr[0]][curr[1]-1] == "*"))
        and (curr[0], curr[1]-1) not in tracker:
            inner_st.add((curr[0], curr[1]-1))
        if (curr[0] < max_y -1 and (arr[curr[0]+1][curr[1]] == "." or arr[curr[0]+1][curr[1]] == "*"))
        and (curr[0]+1, curr[1]) not in tracker:
            inner_st.add((curr[0]+1, curr[1]))
        if (curr[1] < max_x -1 and (arr[curr[0]][curr[1]+1] == "." or arr[curr[0]][curr[1]+1] == "*"))
        and (curr[0], curr[1]+1) not in tracker:
            inner_st.add((curr[0], curr[1]+1))
 
        # a crossroad
        if len(inner_st) > 1:
            tracker[curr] += 1
 
        # save the nodes to DFS list
        for n in inner_st:
            tracker[n] = tracker[curr]
            st.append(n)
 
    return False
 
if __name__ == '__main__':
    t = int(raw_input())
    for _ in xrange(t):
        n, m = map(int, raw_input().split())
        a = []
        for line in xrange(n):
            a.append(list(raw_input()))
        k = int(raw_input())
        if hermionesWand(a, k, m, n):
            print "Impressed"
        else:
            print "Oops!"

About the author

Add comment

Archives

Categories