Guessing a number

starion

I have an application (from my previous post "combining strings") that basically trys to guess a number from 0000 to 9999.

I am not a math wiz, but I am looking for suggestions as to how I might statistically guess the correct number faster. All with the BS2 math set of course.

Thoughts anyone?

Tibo

Since you dont have any feed back from the phone stuff except when succeeding....I see no way to shorten that search....but it's me [noparse];)[/noparse]

T&E Engineer

I was not able to do a search for "combining strings" but it sounds like you want to guess a number at the top (e.g. 9999) and then say too high so you·have it guess a number at the bottom (0000) and then say too low so you pick the 1/2 way point 5000 and narrow the search with either too high or too low. Is this what you want it to do?

starion

I just have this thought in the back of my mind about when I learned to troubleshoot electronics years ago. Cutting the problem in half, cutting the half in half, etc.

Maybe I'm crazy, or had too much caffeine and little sleep last night [noparse]:)[/noparse]

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Every day I wake up, just the same,
waiting for something new;

Every night I have my self to blame,
for the dreams that haven't come true...

- James Taylor

Tom Walker

Without any feedback about your "guess" and without any psychological "hints", you really are shooting in the dark. If there were some kind of response (i.e. too high) then you could use a binary search. If you knew something about how the number was chosen (i.e. it's the first 4 digits of a phone number), then you could narrow down your field (i.e. phone numbers never start with 0 or 1).

Fortunately, "brute force" on a 4 digit number is relatively quick...

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Truly Understand the Fundamentals and the Path will be so much easier...

starion

Yes, that sounds about right. Just trying to hone down the current maximum time it takes (about 20 minutes) to something less, anything less would be an improvement. Although 20 minutes for the amount of time it saves us in the field is nothing, so maybe I should just let it go....nah...what would be the fun in that?

Post Edited (starion) : 3/4/2007 3:34:43 PM GMT

Newzed

I don't think there is a "short" way to do what you want.· However, you could try incrementing your starting search number 0000 by 2.· This would search only even numbers and you have a 50% chance it will work.· If not then start your search with 9999 and decrement by 2 each time.· This will give you all the odd numbers.· If experience tells you that the number has a greater chance of being odd as opposed to being even then you could reverse the search sequence.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Sid Weaver
Do you have a Stamp Tester yet?
http://hometown.aol.com/newzed/index.html

·

starion

Yes, that's kind of what I was thinking too, I just wanted to make sure I wasn't overlooking something obvious.

Clock Loop

If you know the max speed your "devices" COM port, I would think the FASTEST you can search for your number is at the speed of that COM port.

If the COM port speed is faster than your BS2, the only way is to go with SX development (thats a can of worms)

You could always search alternating the top and bottom working towards the center.

So the samps output would start like this:

0000
9999
0001
9998
0002
9997



Or you could work from the center out. (this is what I would do)

5000 -high number
4999 -low number
5001 -high number
4998 -low number
5002 -high number
4997 -low number
etc...

And just make code that incremented the High number up, and the low number down at every step.

Using a RANDOM mode would get nuts because you will need to keep track of ALL of your previous numbers you already tried, filling up your BS2 ram, and or EEPROM quite a bit.

starion

I guess I should have stated...my application takes about 20 minutes and 42 seconds to find code "9999" at 9600 baud (which is the default baud rate of the phone switch). I ran a stopwatch on it last night.

The phone switch itself will go up to 19200. But most installers never change the factory setting. I don't.

I think the "center out" approach makes sense. My perception of the codes I HAVE seen used in the field is that they are in the 4000-6000 range. But that's just my perception. I could be wrong.

Of course I totally forgot that probably the FIRST code I should check is the factory default code, since a percentage of installers never change it either...

Paul Baker

Starion, the method you are talking about is called binary searching, the numbers it chooses is predictable because of the subdivisions are in halves heres the begining of the tree:

           8750          /
      7500
     /    \
    /      6520
5000
    \      3750
     \    /
      2500
          \
           1250
 

It is the fastest method for searching a linear list, resulting in an average search time of O(log₂N) where N is the total number of elements (in this case 9999), O stands for order of complexity and is used to compare different algorithms time of execution in an abstract manner.



▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10

Clock Loop

Paul Baker said...
Starion, the method you are talking about is called binary searching, the numbers it chooses is predictable because of the subdivisions are in halves heres the begining of the tree:

8750
          / 

      7500 

     /    \ 

    /      6520 

5000 

    \      3750 

     \    / 

      2500 

          \ 

           1250 

  

It is the fastest method for searching a linear list, resulting in an average search time of O(log₂N) where N is the total number of elements (in this case 9999), O stands for order of complexity and is used to compare different algorithms time of execution in an abstract manner.

How would this be programmed? I can't vision it without using alot of variables.

Post Edited (BPM) : 11/28/2005 9:03:37 PM GMT

allanlane5

The problem with the Binary Search, as others have pointed out, is that it requires some feedback on if your 'guess' at the number was too high or too low. You do this with two variables -- one being the current position being checked, and a 'Delta' value which you add or subtract based on the feedback -- and then divide by two for the next add or subtract value.

But, it doesn't sound like you get that kind of feedback in your application. In your application, you either hit the number and get a 'success' feedback, or you miss the number and get a 'wrong' feedback. In this case, binary search is not going to help you.

So, as others have suggested, you can use a 'I know the distribution of this number, and it's often between 4000 and 6000' strategy to help you 'guess' numbers more likely to be correct. The 'try even' or 'try odd' approach is another way of doing it.

Note that sending 10,000 4-character strings is 40,000 characters, or 400,000 bits (using 10 bits per byte, having added a start bit and a stop bit to the 8 data bits).· At 9600 bits/sec, it should take 41.67 seconds just to send the data.

I don't know where the bottle-neck is in your process.· If it took 20 minutes to find the number (worst case) then it's taking you 8.3 seconds per guess.· I would assume the bottle-neck is the time-out before the system tells you your guess was wrong -- but there's probably no way to reduce the time-out time.

Post Edited (allanlane5) : 11/28/2005 9:37:31 PM GMT

Paul Baker

Ahh sorry, I was going to say lack of feedback is feedback itself, but for binary searching to work you need a directional feedback (higher/lower). I agree that the timeout for lack of success is your bottleneck. I would parameterize the expected latency and set the time out to encompass that latency with a margin for variation.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10

Post Edited (Paul Baker) : 11/28/2005 10:45:51 PM GMT

starion

It's actually a 4-digit code plus a 6 character word that never changes.

I did "pad" the SERIN's with the lowest possible setting of 1, but found that sometimes that was too short and it missed data, so I found through trial and error that a number of 10 was the most rock solid. Just a minor timing issue between the time the command is sent to the switch and when it responds, it's not instant. 20 minutes is not bad at all as far as I'm concerned, considering the alternative of having to wipe the phone switch and spend a couple of hours or more reprogramming it from scratch and trying to figure out how the previous installer set it up to make it do tricks.

Tom Walker

I realize that this may be too obvious, but is the option "reset to the factory default" not an option in this case?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Truly Understand the Fundamentals and the Path will be so much easier...

starion

Yes, it is, but when you do that, it clears all of the custom programming. For a large installation, this can take many, many hours to re-create, the entire time the phone system is only partially working, and will appear to be working wacky to the customer. This was designed to hack the code so that the programming could be preserved.

It is possible to create the programming structure offline and then dump it to the switch, but it still usually takes a couple of hours just to verify everything is working the way the customer is used to.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Every day I wake up, just the same,
waiting for something new;

Every night I have my self to blame,
for the dreams that haven't come true...

- James Taylor

Paul Baker

Seeing as this is a run infrequently application, I would be content with the long wait required and just accept it as a good enough solution.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10