Efficcient Algorithm

Anything and Everything about Uplink

Moderators: bert_the_turtle, jelco, Chris, Icepick, Rkiver

Sonnybobiche
level3
level3
Posts: 432
Joined: Mon Dec 24, 2001 1:12 pm
Contact:

Postby Sonnybobiche » Wed Mar 31, 2004 1:35 am

The assignment is this:
You know a number between one and a hundred. Create a computer that can guess the number in the fewest turns possible by continually asking whether the number it has guessed is higher or lower than the actual number. (This is done in Java.)
My original attempt was to have it start at fifty and then either increment the guess number by ten or divide it by two, depending on the response. This worked, but ended up being kind of cheap if the number was something like 63, in which case it would go something like:
50
60
70
35
45
55
65
33
43
53
63 done.
This is obviously quite stupid because it takes such a long time. I challenge anyone to come up with something better.
If at first you don't succeed, skydiving is not for you...
ReflectingGod
level5
level5
Posts: 2725
Joined: Sun Mar 17, 2002 4:40 pm
Location: W. Australia

Postby ReflectingGod » Wed Mar 31, 2004 1:37 am

Any restraints on language used? Can I do it in C++?

I might have a go later....

Edit: How come when it knows the number is higher than 50 and 60, it guesses 35? That is not good...

(Edited by ReflectingGod at 8:38 am on Mar. 31, 2004)
ME!

Procrastination - Hard work often pays of after time, but laziness always pays off now!

**Bibo ergo sum!**
Stewsburntmonkey
level5
level5
Posts: 11553
Joined: Wed Jul 10, 2002 7:44 pm
Location: Nashville, TN
Contact:

Postby Stewsburntmonkey » Wed Mar 31, 2004 1:41 am

Using a binary search would give the best average time complexity.  Start at midpoint (50) and if it is higher try the midpoint of the new section (75), if it is less use (25).  Recurse until you find your number.  You are guaranteed a log2(100) run time (7 or less guesses).  :)
ReflectingGod
level5
level5
Posts: 2725
Joined: Sun Mar 17, 2002 4:40 pm
Location: W. Australia

Postby ReflectingGod » Wed Mar 31, 2004 1:42 am

That was exactly what I ws gonna do....
ME!



Procrastination - Hard work often pays of after time, but laziness always pays off now!



**Bibo ergo sum!**
Deepsmeg
level5
level5
Posts: 6510
Joined: Thu Mar 21, 2002 1:26 pm
Location: Register 2102
Contact:

Postby Deepsmeg » Wed Mar 31, 2004 1:53 am

I remember doing this at college a while ago

it was 1 to 1024, but i'll take it down to 128.

Let's work on 63...
Is it < 64?
Is it < 32?
Is it > 48?
Is it > 56?
Is it > 60?
Is it > 62?

Or something like that. but it got there through halving...
Image
Deepsmeg
level5
level5
Posts: 6510
Joined: Thu Mar 21, 2002 1:26 pm
Location: Register 2102
Contact:

Postby Deepsmeg » Wed Mar 31, 2004 2:02 am

Sub cmdGuess_Click()
Dim intNumber As Integer, intGuess As Integer
Dim strAnswer As String

strAnswer = InputBox ("Please enter a number between 1 and 100","50","Choose a number")
If Not(IsNumeric(strAnswer)) Then
   MsgBox "Bad number"
   Exit Sub
Else
   intNumber = CInt(strAnswer)
End If
If intNumber < 1 or intNumber > 100 Then
   MsgBox "Bad Number"
   Exit Sub
Else If
   Msgbox "I guess your number was, umm... err... " & strAnswer & "?"
End If
End Sub
Sonnybobiche
level3
level3
Posts: 432
Joined: Mon Dec 24, 2001 1:12 pm
Contact:

Postby Sonnybobiche » Wed Mar 31, 2004 2:05 am

No language restrictions, I'm just trying to find the most appropriate logic.
Tight code is also a plus.
If at first you don't succeed, skydiving is not for you...
Deepsmeg
level5
level5
Posts: 6510
Joined: Thu Mar 21, 2002 1:26 pm
Location: Register 2102
Contact:

Postby Deepsmeg » Wed Mar 31, 2004 2:15 am

My VB example is flawless!
It gets it right every time! (unless you use a decimal)
Stewsburntmonkey
level5
level5
Posts: 11553
Joined: Wed Jul 10, 2002 7:44 pm
Location: Nashville, TN
Contact:

Postby Stewsburntmonkey » Wed Mar 31, 2004 2:38 am

Heh, so it is.  ;)

Let me see if I can remember enough Java for the job:

private int number;  //you need to initalize this in some way
private int guess;
private int upper = 100;
private int lower = 0;

while (1)
{
 guess = (upper-lower)/2 + lower;
 System.out.println(guess);
 if (guess < number)
 {
   upper = guess - 1;
 }
 else if (guess > number)
 {
   lower = guess + 1;
 }
 else
 {
   break;
 }
}

System.out.println("Your number is " + guess + "." );

 
 
That should work, providing you properly initialize everything.  You could show off by using bit operators instead of the "/2" but that would obfuscate things.  :)

Edit: Perl sneaking in there.

(Edited by Stewsburntmonkey at 1:19 am on Mar. 31, 2004)
User avatar
Iris
level5
level5
Posts: 2423
Joined: Wed Apr 09, 2003 6:15 am
Location: Land of the Morning Calm

Postby Iris » Wed Mar 31, 2004 2:47 am

right on, Deepsmeg! lol!

here is my solution using Hotbasic:
---------------------------------------------------------
$apptype console
$typecheck on
$symboltable on

defint num_answer, num_guess, lowlimit, uplimit, iteration
defstr num_input$

input "Enter a number between 1 and 100 :"; num_input$
num_answer=int(val(num_input$))

lowlimit = 1 : uplimit = 100 : num_guess = 50

while num_guess <> num_answer
 if num_answer > num_guess then
   lowlimit = num_guess
   num_guess = int((num_guess + uplimit) / 2)
 else
   uplimit = num_guess
   num_guess = int((num_guess + lowlimit) / 2)
 end if
 inc(iteration)
 print "Guess #"; iteration; " is "; num_guess
wend

print "Answer has been matched in "; iteration; " tries."
pause
end
---------------------------------------------------------
compiled .exe is 4,608 bytes. enjoy!


(Edited by Iris at 1:59 am on Mar. 31, 2004)
Image
Darkshine
level5
level5
Posts: 1146
Joined: Sat Mar 23, 2002 2:39 pm
Location: Southsea

Postby Darkshine » Wed Mar 31, 2004 7:08 am

Yeah, this is a fairly basic problem most computing students get given. I have my VB solution around somewhere.. 7 or less is as good as you can get.

Good answers people ;)
ReflectingGod
level5
level5
Posts: 2725
Joined: Sun Mar 17, 2002 4:40 pm
Location: W. Australia

Postby ReflectingGod » Wed Mar 31, 2004 1:58 pm

OK, so not the prettiest code, but it works....

Code: Select all

#include <iostream>
#include <stdlib.h>

using namespace std;

int main(int argc, char *argv)
{
  
  int iActualNum;
  int iGuess;
  int iMax = 100;
  int iMin = 1;
  int iIterations = 0;
  
  bool bGoodInput = 0;
  
  cout << endl << "Enter a number between 1 and 100: ";
  cin >> iActualNum;
  
  do
  {
    iGuess = ((iMax-iMin)/2 + iMin);
    
    cout << endl << "Guess: " << iGuess;
    
    if(iGuess == iActualNum)
    {
        cout << endl << "Your number is " << iGuess;
    }
    
    else if (iGuess < iActualNum)
    {
       cout << endl << "Your number is greater than " << iGuess;
       iMin = iGuess;
    }
    
    else if (iGuess > iActualNum)
    {
        cout << endl << "Your number is less than " << iGuess;
        iMax = iGuess;
    }
    system("PAUSE");
  }while (iGuess != iActualNum);
  
  
    
  system("PAUSE");
  return 0;
}
ME!



Procrastination - Hard work often pays of after time, but laziness always pays off now!



**Bibo ergo sum!**
User avatar
Iris
level5
level5
Posts: 2423
Joined: Wed Apr 09, 2003 6:15 am
Location: Land of the Morning Calm

Postby Iris » Wed Mar 31, 2004 2:11 pm

another good contribution. anybody else want to have a take at this teaser in their favorite language? =)
Image
ReflectingGod
level5
level5
Posts: 2725
Joined: Sun Mar 17, 2002 4:40 pm
Location: W. Australia

Postby ReflectingGod » Wed Mar 31, 2004 2:17 pm

Someone do a brainfuck one, I dare ya!
ME!



Procrastination - Hard work often pays of after time, but laziness always pays off now!



**Bibo ergo sum!**
Deepsmeg
level5
level5
Posts: 6510
Joined: Thu Mar 21, 2002 1:26 pm
Location: Register 2102
Contact:

Postby Deepsmeg » Wed Mar 31, 2004 3:01 pm

A what one?

Return to “General”

Who is online

Users browsing this forum: No registered users and 1 guest