Well... there is one little problem I have been meaning to toy with for a long time. Which does have real world applicability. It's the problem of rapidly finding all the objects in a two dimensional space that are some distance away from a given point. Think geolocation for example.I would like to see challenges that result in some useful code. Absurd is getting old.
A couple years ago I worked with a student to develop a fast algorithm to do essentially that, except in 3D and instead of the closest point out of N points to one location there were also N locations. This was used to find differences in point-cloud data collected using 3D scans. The slow algorithm is O(n^2) whereas we managed O(n log^2 n).Heater wrote: ↑Sun Oct 20, 2019 11:54 pmJohn_Spikowski,Well... there is one little problem I have been meaning to toy with for a long time. Which does have real world applicability. It's the problem of rapidly finding all the objects in a two dimensional space that are some distance away from a given point. Think geolocation for example.I would like to see challenges that result in some useful code. Absurd is getting old.
Let me frame it like this:
1) Space will be represented by a square grid of 4194304 points in two dimensions. That's 2048 points in each direction. 0 to 2047 in x, 0 to 2047 in y.
2) One 16th of the grid points will be occupied by objects. That's 262144 objects. The objects positions are distributed randomly among the available grid points. No more than one in each position. The objects have no size, they are "point like".
3) A "target" point is selected at random.
The problem is to find all the objects within some distance of the target (Distance TBD). As quickly as possible.
Sound interesting? Up for the challenge?
Usual rules would apply: One language only used. No use of libraries that are not a standard part of the language spec. Open source only. Must run on a Raspberry Pi...
For the purposes of the challenge the objects only have position (x, y). With the range specified.Will objects have properties?
These days the Linux kernel is written in C and C is written in the C++ programming language. Maybe someday C++ will be written in Python or maybe Basic.
I was reserving grade E for the programs I write, but experimental works just as well.
What is the accuracy of a piece of spaghetti as a measuring tool?
Not very good, though with many pieces the accuracy improves as does ones knowledge about the inaccuracy. I much prefer raspberry pie because spaghetti frequently gets caught in my throat. More information is here.
Once upon a time they would break how fast they could crunch through seti@honme units, ClimatePrediction, Rosetta@Home or Find-A-Drug or LHC and then BOINC messed it all up and benchmarking didn't work so well, graphics card became better than CPU's for a lot of them and we'll ...Heater wrote: ↑Sun Oct 20, 2019 11:08 pmFor sure people don't want to waste time on useless things on their shiny new and expensive super computers.
But they do brag about how fast they are at running industry standard bench marks. Which is very important, national pride and all that.
So why not beating the world record for the digits of Pi as a benchmark? Sounds like a natural to me.
Is it because they would be embarrassed by how slow that would make their big expensive machines look compared to amateur lash ups of a few PC boxes?
I think you are saying something like we do for out air quality project (PM2.5 sensors).Heater wrote: ↑Mon Oct 21, 2019 6:50 am@John_Spikowski,For the purposes of the challenge the objects only have position (x, y). With the range specified.Will objects have properties?
Of course that does not prevent one from building those coordinates into whatever object model you have of the otherway around extending that base property.
Great, you already have a solution in mind. Let's stick to 2D for us simple minded folk.
Actually there are a couple of changes I'd like to make to the problem spec.
1) Previously we have had issues actually timing things. Like the "warm up time" of interpreter engines and cache filling. Like the time taken to print the results. To that end we should specify it so that the actual algorithm time is measured. After all in a real, long running, applications it's the algorithms run time that matters not all that other junk. We should arrange the run time is longer, like requiring to find the distances of some number of different targets, such that run time is many seconds or a minute say.
2) I'd like to specify that always producing a complete list of all possible points within the range is not required.
To that second point, imagine you are somewhere in a big city and you want a list of restaurants within 2km of your location. That might be a big list. You might be happy with just being told of 5 of them that are nearby. Not even the 5 nearest ones necessarily, for example 5 that are all off in the same direction down a particular street would do for you to check out. But not outside the range.
I'm not sure how to express that idea properly yet or how we would evaluate and compare the results of different approaches, which would likely be different.
Thanks for the link. Enjoy your raspberry Pi(e).
The Italian Job?Heater wrote: Strangely enough the algorithm I have in mind to tackle this problem involves spaghetti.
Yes, the challenge is kind of inspired by that geographical problem.I think you are saying something like we do for out air quality project (PM2.5 sensors).
We have result in an SQL (or similar) database, they all have their GNSS location.
I have my Pi with GNSS (or phone, or Alexa) and ask it to give me the current reading.
I can grab the nearest by actual distance from my current point.
I can also grab the nearest 5 and take an average, or remove any that haven't sent data back for a while.
I first did this in Python3, cheap and easy as we don't have that many points to loop through at the moment but moved it to the server in some language (php/SQL?).
Scale it up to 1000s of point and the Python3 would be slow probably.
Code: Select all
SELECT * FROM Places WHERE (Lat => 1.2393 AND Lat <= 1.5532) AND (Lon >= -1.8184 AND Lon <= 0.4221) AND acos(sin(1.3963) * sin(Lat) + cos(1.3963) * cos(Lat) * cos(Lon - (-0.6981))) <= 0.1570;