0

I am trying to solve "the grid search" problem on hacker rank using functional programming. Please view the problem description on hackerrank. https://www.hackerrank.com/challenges/the-grid-search/problem

I want to use only recursion and functional programming primitives such as map, filter, etc. My current solution checks to see if it can find the pattern at the start of the array, if it can't, then I call recursively on the tail of the array. I came up with the following:

def checkLine(str1, str2):
    return str1 in str2

def checkGroup(group1, group2):
    return False not in list(map(lambda x: checkLine(x[0], x[1]), zip(group1, group2)))

def gridSearch(G, P):
    # Write your code here
    if len(G) < len(P):
        return "NO"
    if checkGroup(P, G):
        return "YES"
    else:
        return gridSearch(G[1:], P)

The issue is that I am running into stack overflow when both the array is very large. I know you can avoid stack overflow by using tail recursion but I'm not quite sure how to accomplish that here. Can anyone give an example of how solve this problem functionally but also avoid stack overflow?

Sterling
  • 161
  • 6
  • 2
    You can increase the recursion limit, but doing so causes HackerRank to return a wrong answer. Are you sure your code is correct? – BrokenBenchmark May 19 '22 at 00:08
  • 2
    " I know you can avoid stack overflow by using tail recursion " You cannot. CPython does not do tail-call optimization. Indeed, your grid-search function is already tail recursive. Fundamentally, you should just use iteration in Python when you want to use deep recursion. Python is not a functional programming langauge (although, it borrows from the paradigm, e.g. list comprehensions). – juanpa.arrivillaga May 19 '22 at 00:10
  • See [Does Python optimize tail recursion?](https://stackoverflow.com/q/13591970/5987). – Mark Ransom May 19 '22 at 00:11
  • @BrokenBenchmark It passed about 10 of the test cases but failed for the others that had very large input. Thanks for the replies. I see now that function I wrote is already tail recursive. – Sterling May 19 '22 at 02:23

0 Answers0