Path Counting

I recently saw a neat little problem on Brilliant.org about counting the number of different paths you can take through a complex series of pathways. The main constraint is that you can't travel down the same "hallway" twice. Here is a picture of the pathways and a possible solution given in the problem description:




As you may notice, each of the small boxes is a smaller version of the larger structure, so by figuring out all of paths through one of the small boxes, you can compute the total number of paths through the entire structure. You are meant to solve the problem using programming but I decided to try to do it with pen and paper first. I managed to count out 33 different ways to get through each smaller box which led to a wrong answer. I decided to make a program that would simulate and print out the possible paths through the smaller segments to see which ones I had missed and also compute the final solution. Here is my code:

 import copy  

 base_node_map = [["x" if l !=3 else "e" for l in range(7)],  
   ['x', 'o', 'p', 'o', 'p', 'o', 'x'],  
   ['x', 'p', 'o', 'p', 'o', 'p', 'x'],  
   ['x', 'o', 'p', 'o', 'p', 'o', 'x'],  
   ['x', 'p', 'o', 'p', 'o', 'p', 'x'],  
   ['x', 'o', 'p', 'o', 'p', 'o', 'x'],  
   ["x" for l in range(7)]]  

 def print_node_map(node):  
   for line in node:  
     print (line)  
   print("-----------------------------------------")  

 starting_position = (5,3)  
 count = 0  
 total_routes = 0  
 paths = []  

 def find_routes(node_map, position):  
   current_node_map = copy.deepcopy(node_map)  
   directions = [(position[0]+1,position[1])]+[(position[0]-1,position[1])]\  
         +[(position[0],position[1]-1)]+[(position[0],position[1]+1)]  
   valid_moves = []  
   for i,d in enumerate(directions):  
     path = current_node_map[d[0]][d[1]]  
     if path == "e":  
       print_node_map(current_node_map)  
       global count  
       count +=1  
       global paths  
       paths.append(current_node_map)  
     if path == "p":  
       valid_moves.append((d[0]+(d[0]-position[0]), d[1]+(d[1]-position[1]),i))  
   for v in valid_moves:  
     new_node_map = copy.deepcopy(current_node_map)  
     new_node_map[directions[v[2]][0]][directions[v[2]][1]] = "R"  
     find_routes(new_node_map, v[:2])  

 find_routes(base_node_map, starting_position)  

 def num_segments(node_map):  
   R_count = 0  
   for line in node_map:  
     for v in line:  
       if v == "R":  
         R_count+=1  
   return R_count  

 for p in paths:  
   total_routes+= count**num_segments(p) 
 
 print(total_routes)  

Turns out there are a total of 35 possible paths, which led to my inaccurate pen and paper solution. The answer is 35^2+(35^4)*6+(35^6)*2+(35^8)*20+(35^10)*6 = 16596325314442475. Darn! I was so close to getting it without programming!