[Simown]

This week's Python Challenge is aimed for those of you nursing sore heads from New Year's Eve Festivities. That is, it's not extremely challenging. However, it's got a few little hurdles to get over, so it should be a good way to occupy your fuzzy brain while you knock back a few glasses of the hair of the dog what bit you.

The challenge is to implement the game "Bagels" as described in David Ahl's collection of "Basic Games". A link to the original article, with BASIC source code is provided, in case that might be helpful.

The game is simplicity itself:

The computer picks a three-digit number. The player's task is to guess the number by submitting three-digit guesses. The computer provides feedback thusly:

- If the guess is entirely correct, the player wins.
- If the guess includes at least one digit that is in the correct place, the computer reports "Fermi".
- If the guess includes at least one digit contained in the target number, but it's in the wrong place, the computer reports "Pico".
- If the guess is entirely wrong, the computer reports "Bagels".

Only one response will be provided for a given guess, so if the target is 123 and the guess is 132, the response will be "Fermi" and not "Fermi, Pico".

You get twenty guesses.

That's it.

Your first task is to implement the game for a human solver. The computer will pick a number, and the human player will determine what it was.

For extra sport, write a computer that can zero in on a number you provide. How many guesses does your computer player require to find the correct number?

Hint
Be careful of how you handle leading zeros in the input. If you convert the input to integer form, be careful not to lose any information, or at least to ensure you recover the information you lose.

This post has been edited by Simown: 05 January 2013 - 05:25 PM

[fashionnugget]

Why not? I haven't posted in like a year.

Spoiler

import random

def check_guess(answer, guess):
    if guess == answer:
        return "You win!"
    for x in range(min(len(answer), len(guess))):
        if answer[x] == guess[x]:
            return "Fermi"
    for x in guess:
        if x in answer:
            return "Pico"
    return "Bagels"

def main():
    answer = str(int(random.random()*999))
    guess = ""
    lives = 20

    while check_guess(answer, guess) != "You win!":
        guess = raw_input("Lives: " + str(lives) +  " Guess a number [0, 999]: ")
        print check_guess(answer, guess)
        if lives == 0:
            print "You lose! The answer was " + answer + "."
            break
        lives -= 1

main()

[macosxnerd101]

Here is my solution for the basic stage (in Java). Now to get to work on the AI portion.

Spoiler

package test;

import java.util.Scanner;
import java.util.Random;

class BagelChallenge{

    private String bagelNumber;
    
    public BagelChallenge(){
        Random rand = new Random();
        bagelNumber = rand.nextInt(1000) + "";
        System.out.println(bagelNumber);
    }
    
    public State getState(String guess){
        if(guess.length() != 3){
            throw new IllegalArgumentException("Guess length must equal 3. Guess length: " + guess.length());
        }
        
        if(guess.equals(bagelNumber)){
            return State.BAGEL;
        }
        
        
        for(int i = 0; i < guess.length(); i++){
            if(guess.charAt(i) == bagelNumber.charAt(i)){
                return State.FERMI;
            }
        }
            
        State temp = State.LOSS;
        
        for(int i = 0; i < guess.length(); i++){
            for(int j = 0; j < bagelNumber.length(); j++){
                if(guess.charAt(i) == bagelNumber.charAt(j)){
                    temp = State.PICO;
                }
            }
        }
        
        return temp;
    }
    
}

enum State { 
    LOSS, PICO, FERMI, BAGEL 
}

class Main{

    public static void main(String[] args){
        BagelChallenge generateNumber = new BagelChallenge();
        
        Scanner scan = new Scanner(System.in);
        
        State status = State.LOSS;
        
        for(int i = 0; i < 20 && status != State.BAGEL; i++){
            System.out.println("Enter a three-digit number");
            String input = scan.nextLine();
            
            status = generateNumber.getState(input);
            System.out.println(status);
        }
    
    }
    
}

[CasiOo]

macosxnerd101, on 03 January 2013 - 01:01 AM, said:

Here is my solution for the basic stage (in Java). Now to get to work on the AI portion.

Spoiler

package test;

import java.util.Scanner;
import java.util.Random;

class BagelChallenge{

    private String bagelNumber;
    
    public BagelChallenge(){
        Random rand = new Random();
        bagelNumber = rand.nextInt(1000) + "";
        System.out.println(bagelNumber);
    }
    
    public State getState(String guess){
        if(guess.length() != 3){
            throw new IllegalArgumentException("Guess length must equal 3. Guess length: " + guess.length());
        }
        
        if(guess.equals(bagelNumber)){
            return State.BAGEL;
        }
        
        
        for(int i = 0; i < guess.length(); i++){
            if(guess.charAt(i) == bagelNumber.charAt(i)){
                return State.FERMI;
            }
        }
            
        State temp = State.LOSS;
        
        for(int i = 0; i < guess.length(); i++){
            for(int j = 0; j < bagelNumber.length(); j++){
                if(guess.charAt(i) == bagelNumber.charAt(j)){
                    temp = State.PICO;
                }
            }
        }
        
        return temp;
    }
    
}

enum State { 
    LOSS, PICO, FERMI, BAGEL 
}

class Main{

    public static void main(String[] args){
        BagelChallenge generateNumber = new BagelChallenge();
        
        Scanner scan = new Scanner(System.in);
        
        State status = State.LOSS;
        
        for(int i = 0; i < 20 && status != State.BAGEL; i++){
            System.out.println("Enter a three-digit number");
            String input = scan.nextLine();
            
            status = generateNumber.getState(input);
            System.out.println(status);
        }
    
    }
    
}

If you make an interface for the AI's to implement, then I will happily use your example and make an AI to it

[Simown]

Oh no, what have I done? First section done in Python with some nice little tricks for a bit of fun. Works fine but could do with some better error-checking really.

Spoiler

import random

def bagels():
  def guess(guess):
    return 0 if (guess == pick) else "Fermi" if (any([pick[i] == guess[i] for i in range(len(guess))])) else "Pico" if any((map(lambda x: x in list(pick), list(guess)))) else "Bagels"
  
  pick = str('%03d' % random.randint(0, 999))
  guesses = 20
  while(guesses > 0):
    g = guess(raw_input("Enter a number: "))
    if g: print g 
    else:
      print("You win!")
      return
    guesses -= 1
  print("Game Over. Thanks for playing")

bagels()

This post has been edited by Simown: 05 January 2013 - 03:51 PM

[darek9576]

Is it common in Python to return different data types? Like here, you return 0 under one condition, otherwise you return a string.

This post has been edited by darek9576: 05 January 2013 - 02:15 PM

[AdamSpeight2008]

Python is Dynamic language, you can return whatever you want.

[Simown]

darek9576, on 05 January 2013 - 09:13 PM, said:

Is it common in Python to return different data types? Like here, you return 0 under one condition, otherwise you return a string.

You can, but I don't think it's common - I'd say it certainly wasn't good practice. In Python all non-empty strings are going to evaluate to True (like most languages?) and the 0 to False, which means that the "You win!" will print only if 0 is returned. I could have substituted the empty string in there (which probably would make more sense to maintain the same data type)

Honestly, it's not the kind of code you'd want to maintain or actually use, just showing off some Pythonisms

This post has been edited by Simown: 05 January 2013 - 04:55 PM

[darek9576]

I know Python allows to return different types but my question was whether it's a good practice. Thanks for the answer.

[AdamSpeight2008]

A VB.net version for comparison, using Event to decouple to output.
Uses the iterator feature for input.

Spoiler

Bagles

Public Class Bagles
  Private _SecretDigits As New List(Of Integer)
  Private GuessNumber As Integer = 0
  Private _MaxGuess As Integer
  Private _Ended As Boolean = False
  Public Property EndOfGame As Boolean
    Get
      Return _Ended
    End Get
    Private Set(value As Boolean)
      _Ended = value
    End Set
  End Property


  Public Sub New(d As IEnumerable(Of Integer), Optional maxGuess As Integer = 20)
    _SecretDigits.AddRange(d)
    _MaxGuess = maxGuess
  End Sub

  Public Event Win()
  Public Event Fermi()
  Public Event Bagles()
  Public Event Pico()
  Public Event NumberOfGuessChanged(Left As Integer)
  Public Event GameOver(SecretDigits As IEnumerable(Of Integer))

  Private Sub UpdateGuess()
    GuessNumber += 1
     RaiseEvent NumberOfGuessChanged(_MaxGuess - GuessNumber)
     If GuessNumber >= _MaxGuess Then
      EndOfGame = True
      RaiseEvent GameOver(_SecretDigits)
    End If
 
  End Sub

  Public Sub EvaluateGuess(g As Integer())
    If GuessNumber >= _MaxGuess Then
      RaiseEvent GameOver(_SecretDigits)
    Else
      Dim c = _SecretDigits.Where(Function(v, i) v = g(i)).Count
      If c = _SecretDigits.Count Then
        EndOfGame = True
        RaiseEvent Win()
      ElseIf c > 0 Then
        RaiseEvent Fermi()
      ElseIf (From gn In g, dn In _SecretDigits Where gn = dn).Any Then
        RaiseEvent Pico()
      Else
        RaiseEvent Bagles()
      End If
      If Not EndOfGame then UpdateGuess()
    End If
  End Sub

End Class

Console Version

Option Explicit On
Option Strict On
Module Module1

  Sub Main()
    Console.WriteLine("BAGELS")
    Dim n() As Integer = GetDigits(Function() rnd.Next(0, 10), 3).ToArray
    PressAnyKeyToContinue()
    Console.Clear()

    Dim s As New Bagles(n, 20)
    AddHandler s.GameOver, Sub() Console.WriteLine(" GAME OVER")
    AddHandler s.NumberOfGuessChanged, Sub(left) Console.WriteLine(" {0} Guesses Left", left)
    AddHandler s.Pico, Sub() Console.WriteLine(" Pico")
    AddHandler s.Fermi, Sub() Console.WriteLine(" Fermi")
    AddHandler s.Bagles, Sub() Console.WriteLine(" Bagles")
    AddHandler s.Win, Sub()
                        Console.WriteLine(" WIN")
                      End Sub
    AddHandler s.GameOver, Sub(SecretDigits As IEnumerable(Of Integer))
                             Console.WriteLine("You Lost")
                             Console.Write("Digits were ")
                             SecretDigits.ToList.ForEach(AddressOf Console.Write)
                             Console.WriteLine()
                           End Sub

    Do
      s.EvaluateGuess(Function()
                        Console.WriteLine()
                        Console.Write("Guess: ")
                        Return GetDigits(, 3).ToArray
                      End Function())
    Loop Until s.EndOfGame
    PressAnyKeyToContinue()

  End Sub

  Public Sub PressAnyKeyToContinue()
    Console.WriteLine()
    Console.WriteLine("Press Any Key To Continue")
    Console.ReadKey()
  End Sub

  Private rnd As New Random

  Public Iterator Function GetNumbers(DigitSource As Func(Of Integer)) As IEnumerable(Of Integer)
    While True
      Yield DigitSource()
    End While
  End Function
  Public Function GetDigits(Optional NumSource As Func(Of Integer) = Nothing,
                            Optional Amount As Integer = 20) As IEnumerable(Of Integer)
    If NumSource Is Nothing Then NumSource = AddressOf GetDigit
    If Amount <= 0 Then Amount = 1
    Return GetNumbers(NumSource).Take(Amount)
  End Function
  Public Function GetDigit() As Integer
    Dim c As ConsoleKeyInfo
    Do
      c = Console.ReadKey
    Loop Until (c.KeyChar >= "0"c) AndAlso (c.KeyChar <= "9"c)
    Return Integer.Parse(c.KeyChar.ToString())
  End Function
End Module

This post has been edited by AdamSpeight2008: 05 January 2013 - 05:54 PM

[blackcompe]

A Scala version.

Spoiler

Bagels.scala

import scala.util.Random

/**
 * The application entry point.
 */
object Bagels extends App {

     /**
      * Check the given guess against the given target and generate
      * a {@link Response}.
      *
      * @param target
      *             The target number.
      *
      * @param guess
      *             The guess number.
      *
      * @return A {@link Response} indicating the result of the guess.
      *         {@link Response.INIT} will never be returned.
      */
     def checkGuess(target: String, guess: String): Response = {
          if (target.length != guess.length)
               throw new IllegalArgumentException("Target and guess strings must be of equal length.");
          if (target.equals(guess))
               return Response.WIN;
          for (i <- 0 to target.length - 1) {
               if (target.charAt(i) == guess.charAt(i))
                    return Response.FERMI
          }
          for (i <- 0 to guess.length - 1) {
               if (target.contains(guess.charAt(i) + ""))
                    return Response.PICO
          }
          return Response.BAGELS;
     }

     /**
      * Run the game with the given number of digits in the target,
      * the given number of allowed guesses, and the given solver.
      *
      * @param digits
      *             The number of digits in the target number.
      *
      * @param guesses
      *             The number of guesses the solver can make.
      *
      * @param solver
      *             A {@link Solver} whose {@link Solver.guess} method will
      *             be called to retrieve guesses.
      */
     def run(digits: Int, guesses: Int, solver: Solver) {

          val target = ("%0" + digits + "d").format(
               new Random().nextInt(
                    scala.math.pow(10, digits).toInt))

          def acceptGuess(response: Response, remaining: Int) {
               if (remaining == 0) {
                    println("You lose. You ran out guesses!")
                    return
               }
               val guess = solver.guess(response, remaining)
               val guessResponse = checkGuess(target, guess)
               if (guessResponse.equals(Response.WIN)) {
                    println("You win! It took you " + (20 - (remaining - 1)) + " guesses.")
                    return
               }
               println("[Game] Received guess: " + guess + "\n[Game] Response: " + guessResponse)
               acceptGuess(guessResponse, remaining - 1)
          }
          
          acceptGuess(Response.INIT, guesses)
     }

     //Start the game
     val digits = 3
     val guesses = 20
     val solver = new HumanSolver(digits, guesses) //AutoSolver(digits, guesses)
     run(digits, guesses, solver)

}

Response.java

/**
 * An enum for relaying the game response to a solver class.
 * 
 * The response is either Init, Fermi, Pico, Bagels, or Win. Init indicates that
 * the game has just started and there is no response because no guesses have
 * been made yet. Fermi indicates at least one digit in the guess is in the
 * correct place. Pico indicates at least one digit in the guess is correct but
 * is in the wrong place. Bagels indicates the guess is completely wrong. Win
 * indicates the correct solution has been found.
 */
enum Response
{
     INIT
     {
          public String toString()
          {
               return "Init";
          }
     },
     FERMI
     {
          public String toString()
          {
               return "Fermi";
          }
     },
     PICO
     {
          public String toString()
          {
               return "Pico";
          }
     },
     BAGELS
     {
          public String toString()
          {
               return "Bagels";
          }
     },
     WIN
     {
          public String toString()
          {
               return "Win";
          }
     }
}

Solver.scala

/**
 * A base class for solver implementations for the Bagels game.
 * The number of digits in the target number and the number of
 * allowed guesses is provided in the constructor.
 */
abstract class Solver(digits: Int, guesses: Int) {

     /**
      * Return the next guess given the response for the previous
      * guess and the number of remaining guesses.
      *
      * @param response
      *             The response for the previous guess. The first time this method
      *             is called, {@link Response.INIT} will be sent.
      *
      * @param remaining
      *             The number of guesses left.
      *
      * @return A <code>digits</code>-digit integer as a {@link String} with leading
      *         zeros prepended as needed. E.g. for a three-digit number, the value 1
      *         is returned as 001.
      */
     def guess(response: Response, remaining: Int): String
}

HumanSolver.scala

/**
 * A human solver implementation for the Bagels game.
 * The number of digits in the target number and the number of
 * allowed guesses is provided in the constructor.
 */
class HumanSolver(digits: Int, guesses: Int) 
extends Solver(digits, guesses) {

     /**
      * {@inheritDoc}
      */
     def guess(response: Response, remaining: Int): String = {
          val prompt = ("[Human] Enter a " + digits 
                        + "-digit number [" 
                        + remaining + " tries remaining]: ")
          while (true) {
               print(prompt)
               val guess = readLine()
               if (guess.matches("\\d{3}"))
                    return guess
          }
          return null
     }
}

AutoSolver.scala

/**
 * A automated solver implementation for the Bagels game.
 * The number of digits in the target number and the number of
 * allowed guesses is provided in the constructor.
 */
class AutoSolver(digits: Int, guesses: Int)
     extends Solver(digits, guesses) {

     /**
      * {@inheritDoc}
      */
     def guess(response: Response, remaining: Int): String = ???
}

If you know Java and you want to try to implement the auto solver, do the following:

Spoiler

• Install the Scala compiler. If you're running Windows the MSI installer will set the Path variable so you can instantly open the command prompt and run the scalac (Compiler) and scala (Interpreter) programs. If you're on Linux the package manager will set everything up as well.
  
  
• Fill in the guess method with pure Java code, and uncomment the AutoSolver(digits, guesses) statement in Bagels.scala.
  
  
• Compile the with Scala source with scalac *.scala and Response.java with javac Response.java. A class file will be generated for each source file.
  
  
• Run the program with scala Bagels.

This post has been edited by blackcompe: 07 January 2013 - 09:17 PM

[blackcompe]

I can't find any information on a standard algorithm to solve this problem. I believe that anything I'd implement would solve it in about 15 steps on average, and that's just coding the logic I'd use to solve it. Any thoughts?

[Simown]

I wouldn't think there was a standard algorithm either. I've been playing with this and I can't make a correct guess *every* time yet, is the one you are thinking of more reliable? That's probably the best algorithm you could get for this problem? I wouldn't know either.

[blackcompe]

Quote

I wouldn't think there was a standard algorithm either. I've been playing with this and I can't make a correct guess *every* time yet, is the one you are thinking of more reliable?

No, my algorithm wouldn't solve it every time.

[Simown]

I think basically, there is too many possibilities before you can hone in on a number, this challenge is actually slightly different from the BASIC one, as Jon made the restriction only one answer can be returned i.e. Bagels, Pico or Fermi not multiple clues - if you could return more than one "hint", you could make a better guess I assume.

However, I don't think this can be algorithmically solved anyway, it's just mimicking human logic as you say. The BASIC challenge says, assuming you can return Pico or Fermi for each digit or Bagels you should be able to solve every one in 8 moves or less. I'm going to try it that way and see where I get