Ninety-Nine Boxes

Author: Theodore Odeluga

The source files for this project can be downloaded from here

This is a Node command line project and Node.js can be downloaded from here

Instructions for running a command line program with Node.js can be found here

I got the idea for this exercise from a discussion about the efficiency of search algorithms based on speed and accuracy.

While we imagined an analogy of someone searching 99 boxes, this was of course a high-level discussion of a bigger subject.

Real-world systems obviously involve thousands or even (in the case of a search engine) billions of records.

The conundrum of a needle-in-the-haystack is ages old.

The choice is always to either take a “brute-force” approach (search at random) or do something more sophisticated.

No testing is required to realise the former is the least efficient but I put two functions together for illustration.

For a more efficient alternative, I hit upon the idea of a “start-wide-and-narrow-down” approach.

My rationale was that if a search area was large enough, there was a stronger chance that the target would reside nearer the upper limit of the search.

Naturally, the converse is true if the search space is “small”.

In the code, the random_method function simply generates a random number each time it “guesses” the numeric value of the virtual box containing an imaginary key.

Analytical_method follows the wide-to-narrow approach described above.

Here’s a description of the code in action.

After the activation of select_box, a random number is generated and made available to both functions.

Each function then follows its own unique design to solve the problem. At present, the application is made to run each function separately (you can modify the program to run them simultaneously).

In both cases a variable is tested against the randombox variable for a match. Once one is found, the run object is cleared and the program terminates.

//random_method()




/*Test for match and output result.

	  Stop program if match found.*/
	  
	if(myrandom == randombox){

		console.log(" Function 1: Box "

		+ randombox + " found! ");

		clearInterval(run);

	}

//analytical_method()


if(check == randombox){

	console.log(" key found in " +
 
	" box " + randombox + " in " +

	seconds2 + " seconds! ");

	clearInterval(run2);

}

Analytical_method is similar to random_method except for one significant difference. In the former, an iterator (i) eventually exceeds the value of the selected number and searches using this as an upper value in a numeric range. You can see from the results how analytical_method beats random_method in tests for timing.

//random_method();



Processing...

The selected box is: 3

 function 1: Searching.  Search has taken 1 seconds.  myrandom = 21 //1

 function 1: Searching.  Search has taken 2 seconds.  myrandom = 81 //2

 function 1: Searching.  Search has taken 3 seconds.  myrandom = 10 //3

 function 1: Searching.  Search has taken 4 seconds.  myrandom = 79 //4

 function 1: Searching.  Search has taken 5 seconds.  myrandom = 75 //5

 function 1: Searching.  Search has taken 6 seconds.  myrandom = 14 //6

 function 1: Searching.  Search has taken 7 seconds.  myrandom = 22 //7

 function 1: Searching.  Search has taken 8 seconds.  myrandom = 65 //8

 function 1: Searching.  Search has taken 9 seconds.  myrandom = 46 //9

 function 1: Searching.  Search has taken 10 seconds.  myrandom = 13 //10

 function 1: Searching.  Search has taken 11 seconds.  myrandom = 30 //11

 function 1: Searching.  Search has taken 12 seconds.  myrandom = 53 //12

 function 1: Searching.  Search has taken 13 seconds.  myrandom = 80 //13

 function 1: Searching.  Search has taken 14 seconds.  myrandom = 74 //14

 function 1: Searching.  Search has taken 15 seconds.  myrandom = 35 //15

 function 1: Searching.  Search has taken 16 seconds.  myrandom = 2 //16

 function 1: Searching.  Search has taken 17 seconds.  myrandom = 5 //17

 function 1: Searching.  Search has taken 18 seconds.  myrandom = 56 //18

 function 1: Searching.  Search has taken 19 seconds.  myrandom = 36 //19

 function 1: Searching.  Search has taken 20 seconds.  myrandom = 16 //20

 function 1: Searching.  Search has taken 21 seconds.  myrandom = 93 //21

 function 1: Searching.  Search has taken 22 seconds.  myrandom = 87 //22

 function 1: Searching.  Search has taken 23 seconds.  myrandom = 24 //23

 function 1: Searching.  Search has taken 24 seconds.  myrandom = 33 //24

 function 1: Searching.  Search has taken 25 seconds.  myrandom = 30 //25

 function 1: Searching.  Search has taken 26 seconds.  myrandom = 60 //26

 function 1: Searching.  Search has taken 27 seconds.  myrandom = 68 //27

 function 1: Searching.  Search has taken 28 seconds.  myrandom = 69 //28

 function 1: Searching.  Search has taken 29 seconds.  myrandom = 57 //29

 function 1: Searching.  Search has taken 30 seconds.  myrandom = 28 //30

 function 1: Searching.  Search has taken 31 seconds.  myrandom = 94 //31

 function 1: Searching.  Search has taken 32 seconds.  myrandom = 24 //32

 function 1: Searching.  Search has taken 33 seconds.  myrandom = 4 //33

 function 1: Searching.  Search has taken 34 seconds.  myrandom = 62 //34

 function 1: Searching.  Search has taken 35 seconds.  myrandom = 85 //35

 function 1: Searching.  Search has taken 36 seconds.  myrandom = 95 //36

 function 1: Searching.  Search has taken 37 seconds.  myrandom = 40 //37

 function 1: Searching.  Search has taken 38 seconds.  myrandom = 60 //38

 function 1: Searching.  Search has taken 39 seconds.  myrandom = 12 //39

 function 1: Searching.  Search has taken 40 seconds.  myrandom = 79 //40

 function 1: Searching.  Search has taken 41 seconds.  myrandom = 28 //41

 function 1: Searching.  Search has taken 42 seconds.  myrandom = 22 //42

 function 1: Searching.  Search has taken 43 seconds.  myrandom = 3 //43

 Function 1: Box 3 found!

In this execution of the program, the command line output shows even a value as small as 3 can generate up to 43 searches if using random_method.

However, a larger number such as 49 could be done in 5 with the alternative.

//analytical_method();

Processing... The selected box is: 49 function 2: Searching. Search has taken 0 seconds. function 2: Searching. Search has taken 1 seconds. function 2: Searching. Search has taken 2 seconds. function 2: Searching. Search has taken 3 seconds. function 2: Searching. Search has taken 4 seconds. key found in box 49 in 5 seconds!

Here's the entire program for convenience.

let j; let i = 0; let seconds = 0; let seconds2 = 0; let myrandom; let randombox; let boxes = 98; let run; let run2; let k; let check = 0;

 

console.log("Processing...");

function selected_box(){

	randombox = Math.round(Math.random()*98);
 
	console.log("The selected box is: " + randombox);
    
}

//Brute force

function random_method(){
	
	//Test numbers at random and time the process

	myrandom = Math.round(Math.random()*98);
 
	seconds++;
	
	//Output time taken so far

	console.log(" function 1: Searching. " +

	" Search has taken " + seconds + " seconds. " +

	" myrandom = " + myrandom);
	
	/*Test for match and output result.

	  Stop program if match found.*/
	  
	if(myrandom == randombox){

		console.log(" Function 1: Box "
 
		+ randombox + " found! ");

		clearInterval(run);

	}

} 


//Rational method

function analytical_method(){
	    
		/*Time process and output time taken so far*/

		console.log(" function 2: Searching. " +

		" Search has taken " + seconds2 +

		" seconds. ");

		i++;

		seconds2++;
		
		/*Extend range to search by 10
 
		  until extension exceeds random

		  value being searched.*/
		  
		if(i < randombox){

			i += 10;

		}
	    
		/*If range to search has been extended

		  beyond randombox value by 'i' iterator,

		  set this excess value as the end of the

		  range to search.*/
		  
		if(i > randombox){

			for(k=0; k < i; k++){
				
				//Continue checking

				check++;
				
				/*Stop the program and output

				  the result if a match is found.*/
				  
				if(check == randombox){

					console.log(" key found in " +
 
					" box " + randombox + " in " +

					seconds2 + " seconds! ");

					clearInterval(run2);
					
				}

			}

		}

	} //Close function		


//run = setInterval(random_method, 1000); //Test brute force method

selected_box();

run2 = setInterval(analytical_method, 1000); //Test rational method

Conclusion

This is a simplified version of a bigger subject that would otherwise involve much larger numbers. Indeed, the solution represented by analytical_method would have to be improved considerably in this regard.

Experiment with different values. See how adjusting the amount of increase to the i iterator improves (or doesn’t) the effectiveness of the better method. It shouldn’t be too much of a stretch. A bigger haystack just needs a better algorithm.