443,973 Members | 1,901 Online Need help? Post your question and get tips & solutions from a community of 443,973 IT Pros & Developers. It's quick & easy.

# A problem to get your teeth stuck into..

 P: n/a Given a set of intervals {i1, i2, i3, ...} a list is produced; the base items (0) are placed one at a time into the stream and after the ix one a interval item (1, 2, 3, etc) of the correct type is created. When intervals intersect the order is kept (most frequent first). For example, given the intervals {2, 5, 10} I produce a stream of objects as follows; 0 0 1 0 0 1 0 2 0 1 0 0 1 0 0 1 2 3 0 0 1 0 0 1 0 2 0 1... So the object at index 0 in the list is of type 0, the object at index 2 in the list is of type 1, the object at index 16 in the list is of type 3. The assumption can be made that intervals specified in the supplied list are ordered most frequent first - although the same interval could appear twice. There could be any number of intervals in the list. Can anyone write an algorithm to solve the following, Given the list index and the set of intervals return the object expected at that position? In the above example, I'd expect; calcExpectedValue(0, {2, 5, 10}) to return 0. calcExpectedValue(2, {2, 5, 10}) to return 1. calcExpectedValue(16, {2, 5, 10}) to return 3. I'm thinking it should be fairly simple but I've not been able to come up with an elegant solution? I've obviously abstracted the problem but it does have a bearing on work I am doing (it's to check the results of a test case are in expected order). Nov 17 '05 #1
3 Replies

 P: n/a ge*****************@yahoo.co.uk wrote in news:1120217133.260792.306840 @g49g2000cwa.googlegroups.com: Given a set of intervals {i1, i2, i3, ...} a list is produced; the base items (0) are placed one at a time into the stream and after the ix one a interval item (1, 2, 3, etc) of the correct type is created. When intervals intersect the order is kept (most frequent first). For example, given the intervals {2, 5, 10} I produce a stream of objects as follows; 0 0 1 0 0 1 0 2 0 1 0 0 1 0 0 1 2 3 0 0 1 0 0 1 0 2 0 1... So the object at index 0 in the list is of type 0, the object at index 2 in the list is of type 1, the object at index 16 in the list is of type 3. The assumption can be made that intervals specified in the supplied list are ordered most frequent first - although the same interval could appear twice. There could be any number of intervals in the list. Can anyone write an algorithm to solve the following, Given the list index and the set of intervals return the object expected at that position? In the above example, I'd expect; calcExpectedValue(0, {2, 5, 10}) to return 0. calcExpectedValue(2, {2, 5, 10}) to return 1. calcExpectedValue(16, {2, 5, 10}) to return 3. I'm thinking it should be fairly simple but I've not been able to come up with an elegant solution? I've obviously abstracted the problem but it does have a bearing on work I am doing (it's to check the results of a test case are in expected order). First of all, you have a small error in your stated outputs... calcExpectedValue(16, {2, 5, 10}) should be 2, not 3... while calcExpectedValue(17, {2, 5, 10}) IS 3. Anyway... There are two things to realize here... 1) Since you are inserting data, you have an "offset" problem where you can't represent the output based on a F(p) that doesn't involve sums. This means you can't use a one-line expression. :) It would help if you think of the output as a "zero at every position" with the other objects being inserted "between" posistions. Consider the table below... the numbers across the top are "nominal" positions (not the actual position in the stream), and the numbers down the left represent the index of the object being inserted in the stream. (Index '0' is the '0' object). 0 1 2 3 4 5 6 7 8 9 0 x x x x x x x x x x 1 x x x x x 2 x x 3 x In this case, there are 18 outputs. From this point on we will assume the object outputs are included with the "previous" nominal position. You can see that there is now a regular and predictable pattern, but the position isn't the position in the stream so we still have a problem... BUT this shows that... 2) The type of thing you are doing will result in a repeating pattern after LCM(2, 5, 10) zero's have been output and all subsequent values have been output. In other words, after the 18th value (real zero- indexed position 17 - the last output), there will have 10 0's output (10 is the LCM of 2,5,10), and all of the objects have been output. After this point, the pattern will repeat, so we never have to work with any position in the stream > LCM. If p > NumOutputs, we simply scale p back to the position in the pattern: P = p % NumOutputs. (p is the actual file position you are asking about, while P is the real pattern position). The question now is how do we figure out the output at any real position in the stream pattern. Lets work backwards... At nominal position N, there have been: Object 0: N + 1 Object 1: (N+1) / 2 (integer division) Object 2: (N+1) / 5 (integer division) Object 3: (N+1) / 10 (integer division) Thus, AFTER outputs have been written for nominal position N (including the objects), the file position P is... P = N + 1 + (N+1)/2 + (N+1)/5 + (N+1)/10 (all integer division) We would like to solve for N, but because we are using integer division, we can't do this like normal. But we don't really have to because we are going to write an algorithm, not a formula. Unfortunately I can't pin down any easy way to do this except follow the mechanics of what I've already described. So as long as I've convinced you of the repeating pattern aspect, it should be easy now... The way I would do it is: Build a chart like the one above... a) Calculate the number of nominal positions - this is the LCM of each of your intervals, and create an array (or arraylist) with this number of elements b) The contents of each element will be another arrayList, the contents of which will be object 0 followed by the objects that should be output at that nominal position Then to figure out the output at position p, count the elements until you get to position p and return that element. So for example: using System; using System.Collections; namespace Intervals { public class MyClass { static int[] Intervals = new int[] { 2, 5, 10 }; static ArrayList[] NomPs = null; static int NumOutputs = 0; public static void Main() { // Build the chart int lcm = LCM(Intervals); NomPs = new ArrayList[lcm]; // Populate the chart for(int i=0; i= NomPs[i].Count) p -= NomPs[i].Count; else return (int)NomPs[i][p]; } return -1; } private static int LCM(int[] vals) { int lcm = 1; for(int i=0; i

 P: n/a mdb wrote in news:Xn****************************@207.46.248.16: private static int LCM(int[] vals) { int lcm = 1; for(int i=0; i

 P: n/a Many thanks for taking the time to do that, I hadn't expected such a complete answer. calcExpectedValue(16, {2, 5, 10}) should be 2, not 3... whilecalcExpectedValue(17, {2, 5, 10}) IS 3. You're correct - I took that from my working notes rather than program output and I can't read my own writing. The way you've done it is in fact the same way I'd solved it; populate an array with the group that repeats, mod the required index by the length of that array and then use the result to get an index in to the array to get the repeated element. Seeing as you've come to a similar solution - makes me feel happier with doing it this way. Again - many thanks! Nov 17 '05 #4

### This discussion thread is closed

Replies have been disabled for this discussion. 