Hi guys,

Posting solution and explanation to the following meta puzzle

Though level of puzzle is 3, the solution is straightforward.

After observing the grid we can came to following conclusions:

1. Entrance column doesn't matter, as we can always rotate the row, so every element in the row can be first entrance element. So the problem can be solved by greedy algorithm - collecting the maximum coins in every row.

2. In the case when row contains only ">" we can't go down to next row, but we can gather all coins.

3. If we can go down, then there are three cases:
   *we can traverse row and collect maximum possible coins
   *we cannot traverse row, but there is coin on row, so after rotating the row we can gather it and go down
   * we can't traverse and no coins, but there's at least a dot or "v", so we can go down

Using observations we can easily build solution, only thing left is to figure out how to collect the maximum coins in 3.1. We can traverse the row twice or just join two rows and count maximum coins between ">" and "V".

I hope solution make it clearer

Here the solution:

from typing import List
# Write any import statements here

def getMaxCollectableCoins(R: int, C: int, G: List[List[str]]) -> int:
  # Write your code here
  def traverse(r):
    if r==R:
      return 0
    row = G[r]+G[r]
    is_coin = can_down=is_left=move_left= False
    max_coins=cur = coins= 0
    for i in row:
      if i=="*":
        coins+=1
        is_coin= True
        if move_left==True: 
          cur+=1
      elif i=="v":
        can_down= True
        if move_left:
          max_coins = max(max_coins, cur)
          cur = 0
          move_left=False
      elif i==">":
        is_left =True
        move_left=True
      else:
        can_down = True
    ans = 0
    if max_coins!=0:
      ans= max_coins+traverse(r+1)
    elif is_coin: 
      ans = 1+traverse(r+1)
    elif can_down: 
      ans = traverse(r+1)
    if max_coins==0 and is_left==True:
      ans= max(ans, coins//2)
    return ans
  return traverse(0)
      
    
      

!!! Please Upvote !!! :)