Penney's game is a game where two players bet on being the first to see a particular sequence of heads or tails in consecutive tosses of a fair coin.

It is common to agree on a sequence length of three then one player will openly choose a sequence, for example:

 Heads,  Tails,  Heads, or HTH for short.

The other player on seeing the first players choice will choose his sequence. The coin is tossed and the first player to see his sequence in the sequence of coin tosses wins.



Example

One player might choose the sequence HHT and the other THT.

Successive coin tosses of HTTHT gives the win to the second player as the last three coin tosses are his sequence.



Task
Create a program that tosses the coin, keeps score and plays Penney's game against a human opponent.

 Who chooses and shows their sequence of three should be chosen randomly.
 If going first, the computer should randomly choose its sequence of three.
 If going second, the computer should automatically play the optimum sequence.
 Successive coin tosses should be shown.


Show output of a game where the computer chooses first and a game where the user goes first here on this page.



See also
 The Penney Ante Part 1 (Video).
 The Penney Ante Part 2 (Video).


REM >penney
PRINT "*** Penney's Game ***"
REPEAT
  PRINT ' "Heads you pick first, tails I pick first."
  PRINT "And it is... ";
  WAIT 100
  ht% = RND(0 - TIME) AND 1
  IF ht% THEN
    PRINT "heads!"
    PROC_player_chooses(player$)
    computer$ = FN_optimal(player$)
    PRINT "I choose "; computer$; "."
  ELSE
    PRINT "tails!"
    computer$ = FN_random
    PRINT "I choose "; computer$; "."
    PROC_player_chooses(player$)
  ENDIF
  PRINT "Starting the game..." ' SPC 5;
  sequence$ = ""
  winner% = FALSE
  REPEAT
    WAIT 100
    roll% = RND AND 1
    IF roll% THEN
      sequence$ += "H"
      PRINT "H  ";
    ELSE
      PRINT "T  ";
      sequence$ += "T"
    ENDIF
    IF RIGHT$(sequence$, 3) = computer$ THEN
      PRINT ' "I won!"
      winner% = TRUE
    ELSE
      IF RIGHT$(sequence$, 3) = player$ THEN
        PRINT ' "Congratulations! You won."
        winner% = TRUE
      ENDIF
    ENDIF
  UNTIL winner%
  REPEAT
    valid% = FALSE
    INPUT "Another game? (Y/N) " another$
    IF INSTR("YN", another$) THEN valid% = TRUE
  UNTIL valid%
UNTIL another$ = "N"
PRINT "Thank you for playing!"
END
:
DEF PROC_player_chooses(RETURN sequence$)
LOCAL choice$, valid%, i%
REPEAT
  valid% = TRUE
  PRINT "Enter a sequence of three choices, each of them either H or T:"
  INPUT "> " sequence$
  IF LEN sequence$ <> 3 THEN valid% = FALSE
  IF valid% THEN
    FOR i% = 1 TO 3
      choice$ = MID$(sequence$, i%, 1)
      IF choice$ <> "H" AND choice$ <> "T" THEN valid% = FALSE
    NEXT
  ENDIF
UNTIL valid%
ENDPROC
:
DEF FN_random
LOCAL sequence$, choice%, i%
sequence$ = ""
FOR i% = 1 TO 3
  choice% = RND AND 1
  IF choice% THEN sequence$ += "H" ELSE sequence$ += "T"
NEXT
= sequence$
:
DEF FN_optimal(sequence$)
IF MID$(sequence$, 2, 1) = "H" THEN
  = "T" + LEFT$(sequence$, 2)
ELSE
  = "H" + LEFT$(sequence$, 2)
ENDIF