Alice Bob Coin Optimal Solution

Question

Consider this question I found on hackerrank: Coins Problem

Alice and Bob were sitting in the sun; drinking orange juice; and watching some migrating ducks fly to Africa. “Look”, noted Alice, “one of the ducks left a trail of golden coins on the floor”. “Great!” exclaimed Bob, “let‟s play a game with this line of coins. We will take turns, where each one of us will flip one coin from „head‟ into „tail‟ state”. “Ok”, agreed Alice and added, “but when we flip a coin, we can also opt to flip the coin immediately after it, even if that coin is a „tail‟, in which case it becomes a „head‟”. “And whoever can not play - loses” cried both of them simultaneously. Cunning Bob knew that he could count on witty IEEEXtreme contestants to help him win. Can you help him do that? Task Your task is to write a program that given a string of H/T letters, computes a winning move for the flip-coin game, if there is one, or reports that there in no winning move, if this is the case. A winning move is a legal move such that either the player wins immediately (because there are no more coins to flip), or else, after any subsequent move by the opponent there is a winning move for the player.

For example, if the input is TTTT then Bob lost the game (there is no “head” so he can not play and thus he lost). For the input TTTTHTTTT, Bob wins by flipping the fifth coin; for the input TTHHT, Bob wins by flipping both “Heads” (third and fourth coins); for the input THHTHTHT, Bob wins if he flips coins 2 and 3.

Input The input file to be read from the console contains one line in which there is a string entirely composed of the letters H and T, representing the state of the coins, as explained.

Output The output file, to be written at the console, contains one line, with one number. A positive number N means that flipping the Nth coin is a winning move. A negative number, written –N, means that flipping the Nth and the N+1th coins is a winning move. Zero, written 0, means that there is no winning move. Note that, in general, there can be several winning moves, for a given list of coins. Your program can output any of them.

I tried a recursive backtracking solution however 'C' throws a Segmentation Fault error due to Stackoverflow. Here is my code:(It partially works)

    #include <stdio.h>

    int main()

    {

    char a[100];

    scanf("%s",a);

    printf("%d",check(a));



}

int check(char a[])

{

    //printf("%s\n",a);

    int i=0;

    for(i=0;i<strlen(a);i++){

        if(a[i]=='H'){

            a[i]='T';

            a[i+1]=a[i+1]=='H'?'T':'H';

            if(check(a)){

                a[i+1]=a[i+1]=='H'?'T':'H';

                if(check(a))a[i]='H';

                else return (i+1);

            }

            else return -(i+1);

        }

    }

    //printf("Lost\n");

    return 0;

}

Could anyone help me?

it must be an out-of-bounds array access. a debugger can help you. — Karoly Horvath
If this kind of problem interests you then you should study the Game of Nim. Many games -- perhaps including this one -- are actually Nim in disguise. — Eric Lippert

Trenin Trenin · Accepted Answer · 2014-02-05T18:57:04

You are not properly undoing all the moves that you attempt. If you don't undo the moves, you can never backtrack.

Also, you are returning numbers from check which is being used as a boolean function.

Here is a sample that works.

#include <stdio.h>
#include <string.h>

//#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define FLIP(x) ( ((x)=='H') ? 'T' : 'H' )


bool check(char* a) {
  DEBUG("%s\n",a);

  // Loop over the string.
  for (int i=0; i<strlen(a); i++) {
    // If this coin is a head, try flipping it.
    if (a[i]=='H') {
      // Try flipping just this coin.
      a[i]=FLIP(a[i]);
      // See if it is a win or a loss for the other player.
      if (!check(a)) {
        // A loss for the other player means a win for us!
        // Undo our last move.
        a[i]=FLIP(a[i]);
        return true;
      }
      // A win for the other player.  
      // See if flipping the next coin makes a difference.
      if (i+1 < strlen(a)) {
        a[i+1]=FLIP(a[i+1]);
        // See if it is a win or a loss for the other player.
        if (!check(a)) {
          // A loss for the other player means a win for us!
          // Undo our last two moves.
          a[i]=FLIP(a[i]);
          a[i+1]=FLIP(a[i+1]);
          return true;
        }
        // Still a loss.  Undo this move.
        a[i+1]=FLIP(a[i+1]);
      }
      // Still a loss.  Undo this move.
      a[i]=FLIP(a[i]);
    } // if (a[i]=='H')
  } // for (int i=0; i<strlen(a); i++)

  // Loss.
  return false;
}

int main() {
  char a[100];
  scanf("%s",a);
  if (check(a)) {
    printf("Winner!\n");
  } else {
    printf("Loser!\n");
  }
}

Alice Bob Coin Optimal Solution

3 Answers