A Little challenge - Searching for numbers "within" a range

[TonyM]

Folks,

I thought I would share a little challenge with you. This is a challenge I will overcome, and I will share my ultimate solution, but I am happy if someone wants to contribute, or enjoys an intellectual/coding challenge.

I Have a range of locations, they are defined by post codes / Zip codes, sometimes they are a range and sometimes individual numbers

☐ Sydney Metro: 1000 - 1335 , 2760 -2770 

☐ Sydney CBD: 1100 - 1299, 2000, 2001, 2007, 2009

I am keen to keep it simple, and not need to generate all the numbers within a range yet I need to be able to search for a specific number. 

For example If I was to search for 1100 it would clearly be in the above range 1000 - 1335 yet 1100 is not in the posts codes, it exists between two post codes.

My Thought is to have a Filter that defines the post codes in range such as;

"[range[1000,1099]] [range[2760,2770]]"

and 

"[range[1100,1299]] 2000 2001 2007 2009"

Not withstanding the inconsistencies in the above data (to be remedied)  I would like to be able to search for a number that may be specified specifically or implied in a range, and identify the tiddler in which it is listed.

I have a few ideas, but wondering if anyone has a great idea?

• Generate a Data Tiddler with all postcodes from my ranges, key number value region tiddler
• When searching re-generate all numbers and search there in

Regards

tony

 

[Mark S.]

You could put each range in it's own field as a comma separated value in its own tiddler and tagged as needed. Individual values would also be entered as ranges. For instance

title: range 1

range: 1100,1299

tags: CBD

title: range 2

range: 2000,2000

tags: CBD

Then this code could compile the ranges on the fly and test for whether a value was in a group of ranges

<$vars pre="[range[" sfx="]] " mynum="1200">
<$list filter="[tag[CBD]get[range]addprefix<pre>addsuffix<sfx>]" variable="ranges">
<$list filter="[subfilter<ranges>suffix<mynum>prefix<mynum>]">IN RANGE</$list>
</$list>
</$vars>

Maybe?

-- Mark

[TonyM]

Mark,

Thanks for that suggestion, and the juggling to test for a value. Since I expect users to update it, the range when. Setting a single value will need to be hidden from them.

You have made me think that a data tiddler for each group eg CBD may work.

I discovered an inconsistency in the data which makes me question if I will need to validate the data before or on update which makes it a little more complex like detect an overlapping range.

I do know australia post offers postcode selection tools, perhaps I should look there.

Lets see if there are more ideas.

Thanks
Tony

[Mal]

Hi Tony,

I would be inclined to expand each list of postcodes and put them in a list field. This would allow really simple search code and the resulting tiddler would not be all that large.

I know this was not your challenge, but just saying...

Mal

[TonyM]

Mal,

That was my first thought, but I learned while "valid post codes exist in a range, not all postcodes in that range exist". If I manufacture postcodes I may be giving an undue suggestion that the post code is valid, but I suppose we are doing that anyway.

I may still take that approach, and use the range operator to generate them

Tony

[Mark S.]

Maybe put the "real" values in a data dictionary, and verify against that.

-- Mark

[S. S.]

Tony,

The method of going through a table by halves is very effective and fast where a number (N) lies inside a given range.
Now how you could do this using TiddlyWiki is the challenge!

The below simple method can look up a table of a million range entries in milliseconds.

1. Count the number of entries in your table. Say you have 10,000 post codes.
   Likely the table will be less than 1,000 entries as they are ranges - let us say it is 1,000 ranges (X)
   First Line is 0 (FL) : FL = 0
   Note the post code entry that is in the middle position of this table - the X/2 = 500th entry in the table (Integer value)
   This is the Search Line(SL) : SL = INT(X/2)
2. Check if your number (N) is
   greater than the start value of this middle entry's post code range
   AND less than the end value of this range.
   If it is, you have found the correct range. - Stop here.
   If not ...
 3a. Check if the post code N is NOT in any range in your table (needed as you narrow down your search)
     If FL=SL then the Code is Missing - Stop here.
 3b. If N is greater than the start value of the range
     Make FL = SL
     check against the higher next half point table entry position: (FL + X)/2  = 750 (Rounded value)
     Repeat step #2
 3b. ELSE (meaning N is less than the start value of the range)
     Make X = SL
     check against the lower next half point table entry position: (FL + X)/2 = 250 (Integer value)
     and Repeat step #2
 4. Continue until you reach the end point - I believe 2^10 calculations (1,024) for this size of table.

I doubt you will end up doing it this way, as TiddlyWiki out of the box doesn't seem to be geared for this kind of manipulation.
Still, it was fun laying you the logic for you!

Cheers

[TonyM]

S S ,

A Form of Binary search? Nice algorithm. In this case the lookup will be rare, and typically only when changing the Postcodes on a particular region. So I suspect in this case it would be overkill.

Also being postcodes the data is not simply a list of numbers from 1000 to 9000 as the first number represents an Australian state, and some have much less post codse, with some codes representing millions of Square kilometers. 

I suppose my main objective is to make the application of changes easy, and in someway's that is simply to allow the user to set numbers and ranges. It is then interpreting them on the fly that is my greater concern in this application. But I will keep this in mind.

I have no doubt your algoritium could be essential in other data cases.

How do you think it would be implemented in TiddlyWiki?

Regards

Tony

[TonyM]

Mark,

I am thinking this may be the way. A Button on a given area would generate the post codes from the range and individual ones and update a data tiddler. In this way if there is an overlap with another area the last one will win. It need only be done on the change of an area.

Now I need to bring the the areas (with Post codes) into a region and Regions into States.

Thanks all for the feedback so far

Regards

Tonyt

[S. S.]

Tony,

I have no idea what a binary search is. I am not a programmer!
Now I did the difficult part, laying out the logic, which works!
I'll leave the easy part to the programmers.

Cheers!

On Wednesday, February 20, 2019 at 9:31:09 AM UTC+7, TonyM wrote:

S S ,

A Form of Binary search? Nice algorithm.

. . .

[TonyM]

FYI:

As you divide the Problem by two (2) each time, two is synonymous with binary. So you have suggested a version of "binary search".

You can even do this without numbers. For example if you can't connect to google search.

Your Browser, on your desktop, on your home network, your home router, your ISP, on the internet, google servers, google search

You could see if the problem is your home router, then to the left or right of your Home Router depending on success or failure.

You should be proud of re-inventing the wheel, it's a sign of genius, of local invention, if not the first or global invention.

Regards

Tony