Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Let's say I have a list of precipitation values by hour, each showing how much rain happened in the prior 24 hours, ordered by date. For example:

{
    '2012-05-24 12:00': 0.5, // .5" of rain from 5/23 12:00 - 5/24 11:59
    '2012-05-24 11:00': 0.6, // .6" of rain from 5/23 11:00 - 5/24 10:59
    '2012-05-24 10:00': 0.6, // .6" of rain from 5/23 10:00 - 5/24 09:59
    ...
    '2012-05-23 10:00': 0
}

Is there a strategy/algorithm to determine how much rain fell in each of the hours? I can't seem to wrap my head around this. I know that it's not as straightforward as just summing the diffs.

Visualization of Dataset

P(N)    [.....======================]
P(N-1)  [....======================.]
P(N-2)  [...======================..]
P(N-3)  [..======================...]
I want  [..........................=]

Many thanks for any help.

share|improve this question
    
Does .6" of rain from 5/23 11:00 - 5/24 10:59 mean that in that time span .6" of rain fell down or an average of .6" of rain during that period? –  System Down May 24 '12 at 17:47
    
The former. It's the sum of rain by hour, for the previous 24 hours. I want to figure out how to "break off" that last hour. –  Mike Griffith May 24 '12 at 17:53
1  
This surprisingly hard. Every value you record is made up of 24 unknown numbers summed up. You would need 24 equations to solve that, that is 24 equations that have the same exact unknowns in them but because you have a sliding window that's not the case. I can't imagine that this is "unsolvable", but it sure looks like it to me. Another way to think about it: You are gaining one unknown for every P(N-x) you add, so in the end the number of equations and unknowns even themselves out again. –  sebastiangeiger May 24 '12 at 18:08
3  
I'm wondering if this would be a better question for: cstheory.stackexchange.com –  FrustratedWithFormsDesigner May 24 '12 at 18:21
2  
@FrustratedWithFormsDesigner, or math.stackexchange.com? –  CaffGeek May 24 '12 at 19:08
show 1 more comment

5 Answers

up vote 8 down vote accepted

Assuming that the data set always consists of consecutive 24-hour windows (i.e., the first data point isn't a 1 hour window)...

This is not a solvable problem at least in the general case because there exists a counterexample where at least two rain patterns map to one data set.

  • Case 1: It rains 24" at 12:30 a.m. every day forever.
  • Case 2: It rains 1" at 30 minutes past every hour forever.

In both cases, your P(N) = 24" for all N.

Since there is no one scenario that can be derived from this one data set, the problem is not solvable in the generic sense.


As an aside, we can also demonstrate that it's not necessarily true that the problem is always unsolvable. Most simply, if P(N) = 0" for all N, there is only one possible rain pattern to account for it: zero inches of rain at every hour.


It is therefore the more interesting problem to identify what characteristics about the data set make the problem solvable. Trivially, if you have a data set with at least one N such that P(N) = 0", then you have a solution.

I would not be surprised if there were other properties that would make the problem solvable for a given data set. Finding those should be a fun challenge. At the same time, proving that none can exist is equally entertaining.

share|improve this answer
add comment

you need to iterate through the data until you find a 0 precipitation period then you calculate forward from that point as SnOrus describes. If no data point is 0 then I don't think this can be solved unless you define the earliest entry to be 1 hour after the beginning of time so points earlier than that are undefined.

it would also be possible to calculate backwards in time from a 0 reading, doing the same thing in reverse (though you will get at least 24 0s in a row.

share|improve this answer
    
The interesting constraint on the data that makes this possible is that precipitation can never be negative, so with a zero value, you know the 24 previous hours had to be zero. –  Scott Whitlock May 24 '12 at 20:16
add comment

P(n) - P(n-1) Bounded to >= 0

Where P() is the amount of precipitation recorded for the 24 hours prior to n.

... should give you the amount of rain in the hour prior to P(n).

share|improve this answer
    
That would calculate -.1 inches for 12:00. Sounds unlikely. If .2 inches was the 24 hour measure at 11:00 on the 23rd then the correct answer should be .1 –  Crazy Eddie May 24 '12 at 17:42
    
If N is "5/24 12:00pm", P(N) includes a window from 5/23 at 12:00pm through 5/24 at 11:59am. Then P(N-1) includes a window from 5/23 at 11:00am through 5/24 at 10:59am. I want to know what happened in the window from 11:00am-11:59am, but merely subtracting the two also introduces an extra "window" in the prior day. See updated description for visual representation. –  Mike Griffith May 24 '12 at 17:46
    
@MikeGriffith: See my edit. I believe I was right, but you need to bound the result to >= 0. (<= 0 would indicate that there was no rain). Unless I'm misunderstanding the problem. –  Steve Evers May 24 '12 at 17:56
    
@SnOrfus: You still have two unknown values at that point. –  Daenyth May 24 '12 at 18:06
add comment

This isn't a full answer, I'm at work and have already spent a bunch of time on it...further I'd need more data to see if my hunch is correct.

Let's call P(x) the 24 hour measure at time x.

Considder the following overlap scenario:

|H1|H2|H3.............|H23|H24|H25|H26 ................ |H46|H47|H48|
|-----------------P(X)--------|-----------------P(X-24)-------------|
   |----------------------P(X-1)--|

P(X) - P(X-1) + H25 = H1.

Thus you need to calculate H25. I believe that the solution is going to rest somewhere in a system created from P(X), P(X-1), and P(X-24).

share|improve this answer
add comment

For two consecutive hours n (now) and n-1 (the hour before now), you have the twenty-four hour precipitation sum (T) made up of 24 hourly precipitation numbers (P):

T(n) = P(n) + P(n-1) + P(n-2) + ... + P(n-22) + P(n-23)
T(n-1) = P(n-1) + P(n-2) + P(n-3) +... + P(n-23) + P(n-24)

So:

T(n) - T(n-1) = P(n) - P(n-24)

(Terms P(n-1)...P(n-23) are duplicated in both T(n) and T(n-1), so subtracting them gives 0.) Rearranging, you get:

P(n) = T(n) - T(n-1) + P(n-24)

Now, you can't figure out what P(n) is unless you know what P(n-24) is. You can go further back in the data to calculate P(n-24), but to get that you need P(n-25) and so on ad infinitum. What you need, then, is the precipitation value for any single hour that's longer ago than 24 hours. If you have that, you can calculate the hourly precipitation for all the subsequent hours.

share|improve this answer
1  
+1 "What you need, then, is the precipitation value for any single hour that's longer ago than 24 hours." Or a value of 0" for a 24 hour period. –  CaffGeek May 24 '12 at 19:24
    
@Chad That's certainly one way to get it. –  Caleb May 24 '12 at 20:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.