So, it was day in the hackshop and our programming sysadmin was trying to fix a little display problem when showing thermometer data.
So, there are thermometers in both Fridges, Freezers, heating systems and others.
For alerts, you set a level (trigger level) and a time (count of samples) and simply trigger if the last X have been above the threshold level.
Not a big problem, simple, elegant, linear speed.
But when you show data, for example the "current temp, and this days max temp", and not working "real time" you need to look at a whole data-set of points, find the max, and show it. This isn't a difficult operation O(n log n) with a suitable sort operation.
Now, in real life, fridges and freezers have thermostats that cause temperatures to show up more like triangle waves than anything else. This is easy to deal with (you simply don't deal with it, see how easy!).
Then there are things like "automatic defrost".
Automatic defrost means that every X hours, the temperature in a freezer will spike up to ~+1 degree, and then down to -20 again, in a short time span ( ~35 minutes from start to end ). This then prevents frost from forming as badly as normally.
This also means that the day current/max temperatures _always_ are stuck at -20,+1 . A big gap, and not at all representing reality. Or well, representing, sort of how Westrbo Baptist Church represents Christianity.
So, we need to show only those high points, that have been high for a period of time T.
So, "max" for the day is the highest temperature V that has been at this point, or HIGHER for T samples. It's not enough that it's been T samples _total_ for the day, but they need to be consecutive.
The graphical Method
This is unknown in complexity, but could work. It's a good visualization, but I haven't gotten this to actually work.
* You draw your graph
* You draw a line along the max value.
* You move your line down,
* You find all intersections
* You trace the distance between your intersections.
* When your distance between intersections becomes > T, and the graph stays above it, you have found your first match.
The Mold in the Hills Method
* Pick a Threshold
* Start walking the list until you reach the threshold.
* Mark this point, walk forwards until you reach the next
* if this point is > T points away, you have a hill.
* Destroy all points T as you walk forwards to the next hill.
* Once you only have hills left, increase your threshold
* Keep destroying all data until you have no hills >T wide left. Done!
The window to the World Method
This is a bit quadric bruteforce version.
Point a window at the first T values.
* Sort a copy of this window
* Take the min & max values. The Min is your new highscore.
* re-center your window to start one step right of the Min value.
* sort your window
* compare min with your highscore, if higher, move one step right of your min, and store highscore.
* If your max is lower than your highscore, jump T units ahead.
* if your min is lower than your highscore, jump to the value closest to your highscore.
This method will take a ton of copies, and lots of sorting of your world.
The "I like lists" Method
Aka. I have no idea what I'm thinking anymore method. (never tried, might work, pigeonhole-principle )
* Prepare a copy of the first T values.
* find the min of that copy, that is your highscore.
* Center your world on the highscore ( skipping values forwards )
* check if your lowest point is still the highscore
* * if so, skip to one right of highscore, start looking forwards.
* if not, re-center your area around the lowest.
* once your lowest is higher than highscore, you have a jackpot and move on.
* walk forwards, keeping copies of the last T values.
So, if you want to try your hand at an elegant solution to this problem, please be my guest. A dataset can be downloaded from us.