Assume we are given a string variable named word. We are playing a game with 2 players, player A, and player B.

Each player, at their respective turn (with player A always beginning), chooses either the first or the last letter of the string and gets points based on the ordered count of that letter in the ABC (i.e. a = 1, b = 2, c = 3 and so on, so it's ord(char) - 96 in python). Then the other player is given the same string but without the letter that was chosen.

At the end of the game, whoever has the most points wins.

We are given that player B's strategy is a greedy strategy, meaning he will always choose the best option from the current given options (so if the word was "abc" he would choose the letter "c" because it's better for him at the moment).

We define a string to be "good" if no matter what player A picks in his turn, at any given point in the game, player B will always win.

Need: I need to create a function that recursively finds whether a word is considered "good" (returns True), and if not it returns False.

Restriction: The only allowed input is the word, so the function would look like: is_word_good(word).

If needed, memoization is allowed.

I tried wrapping my head around this problem but I am having difficulties solving it recursively, specifically, I cannot find a way to efficiently pass/save the cumulative score between the function calls. Maybe I'm missing something that makes the problem simpler.

I would've added a code but I kept deleting my ideas and trying to redo them. My main idea was to (maybe) save using memoization every word and the respective score each player can get at that word, and the score will depend on the chosen letter currently recursion of chosen letters later on in the recursion. I failed to implement it correctly (let alone efficiently).

Example of expected outputs:

>>> is_word_good("abc")
False
>>> is_word_good("asa")
True

Help would be appreciated!

CodePudding user response：

It is usual for such problem to have a "wrapper" function, with only parameters for the problem, here it would be :

def is_word_good(word: str) -> bool:
    ...

But this function can use other functions. For example, you can create a "solver" method with many more parameters (about the current state of the solution) :

def _solving__is_word_good(current_word: str, player_A_points: int, player_B_points: int, player_turn) -> bool:
    ...

So that your main ("wrapper") function will just do :

    return _solving__is_word_good(
        current_word=word,
        player_A_points=0,
        player_B_points=0,
        player_turn=A,
    )

And this second function will do the heavy lifting (and could be memoized, look for functools.lru_cache).