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

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 