Point on non-linear range to linear and back?

Question

Greeting, I'm trying to solve the following puzzle:

I have a list of linear ranges which represent one big range.

                                          X'
 100    200 300    400 500    600 700     |       900    (X)
|----------|----------|----------|--------+----------|
 0                                        |       100    (Y)
                                          Y'

X consists of the following ranges (even and round numbers are just examples for ease of comprehension, they could be anything, no proportions here at all):

• from 100 to 200
• from 300 to 400
• from 500 to 600
• from 700 to 900

On the flip side, Y has just one range:

• from 0 to 100

Both X and Y are of the same length, just different units. Lets say one is dollars and another is percents (or any other similarly unrelated units). So Y'0 == X'100 and Y'100 == X'900.

Question: Given any point in Y, what is equivalent point in X and vise-versa, given a point in X - what is it in Y?

Is this a typical math problem? Does it have a name? Anything that would set me in the right direction would help.

Thank you.

Here's solution based on Igor Krivokon's answer. I had to remove multiplication by two to make it work.

input_range = [
  [100, 200],
  [300, 400],
  [500, 600],
  [700, 800]
]

range_sum = 0
lookup_list = []

input_range.each do |range_start, range_end|
  lookup_list.push [ range_start, range_sum ]
  range_sum += range_end - range_start
end

def get_percent(value, lookup_list, range_sum)
  result = 0

  lookup_list.reverse.each do |range_start, cummulative_sum|
    if value >= range_start
      result = value + cummulative_sum - range_start
      break
    end
  end

  return result.to_f / range_sum.to_f
end

def get_value(percent, lookup_list, range_sum)
  result = 0
  value = range_sum * percent

  lookup_list.reverse.each do |range_start, cummulative_sum|
    if value >= cummulative_sum
      result = value - cummulative_sum + range_start
      break
    end
  end

  return result.to_f
end

puts "Input range: #{input_range.inspect}"
puts "Continous range sum: #{range_sum}"
puts "Lookup list: #{lookup_list.inspect}"

input_range.each do |range|
  range.each do |start_or_end|
    puts "#{start_or_end} is at " + get_percent(start_or_end, lookup_list, range_sum).to_s
  end
end

[ 0, 0.25, 0.5, 0.75, 1 ].each do |percent|
  puts "#{percent} is at " + get_value(percent, lookup_list, range_sum).to_s
end

$> ruby ranges.rb

Input range: [[100, 200], [300, 400], [500, 600], [700, 800]]
Continous range sum: 400
Lookup list: [[100, 0], [300, 100], [500, 200], [700, 300]]
100 is at 0.0
200 is at 0.25
300 is at 0.25
400 is at 0.5
500 is at 0.5
600 is at 0.75
700 is at 0.75
800 is at 1.0
0 is at 100.0
0.25 is at 300.0
0.5 is at 500.0
0.75 is at 700.0
1 is at 800.0

$> ruby ranges.rb

Input range: [[100, 200], [300, 400], [500, 600], [700, 1000]]
Continous range sum: 600
Lookup list: [[100, 0], [300, 100], [500, 200], [700, 300]]
100 is at 0.0
200 is at 0.166666666666667
300 is at 0.166666666666667
400 is at 0.333333333333333
500 is at 0.333333333333333
600 is at 0.5
700 is at 0.5
1000 is at 1.0
0 is at 100.0
0.25 is at 350.0
0.5 is at 700.0
0.75 is at 850.0
1 is at 1000.0

It seems to work with any range I give it, back and forth.

Answer 1

Say you have one range (a, b) and another one (c, d). Now you have a number i for which a < i < b. You can "normalize" it by subtracting a and dividing by b - a - this gives you a value between 0 and 1. You can then use this value to transfer it into the other range by reversing this calculation with the other bounds, so to speak multiply it by (d - c) and add c.

Say the corresponding point in the other range is i'. Then,

i' = (i - a) / (b - a) * (d - c) + c

The term you are searching for is scaling and translation.

Answer 2

This is not really solvable because the problem is underspecified. Even for the same ranges, there can be different sliders like this:

1  100 101       1000
|-----|-----------|

1        100 101 1000
|-----------|-----|

For each range like [1..100] you need to know how which percent points on the slider correspond to it. In the above examples this could be something like [0%..33%] or [0%..66%]. Once you have this information, it's easy to determine in which of the ranges and at which position of that range a given data point is and to what value it corresponds.

Answer 3

How many ranges do you have? Is it acceptable that the algorithm is O(number of ranges)?

If so, below is the description of the algorithm. Let me explain it on your (original) example.

 100    200 300    400 500    600 700    800
|----------|----------|----------|----------|
 0%                                     100%

1) What you're doing to do is to map the value X in range A (100-800) to the value Y in continous range B (0-399) (as the total number of elements in your range is 400). Then it's easy to change position in B to percents, I will omit this part.

2) Create a list of records, where each records represents one range mapping.

struct RangeRecord {
  int start_in_a;
  int start_in_b;
};

In your case, you will get the following list:

{100, 0}, {300, 100}, {500, 200}, {700, 300}

3) When you need to map a number X from A to B, you iterate the list to find first record with start_in_a <= X.Then your value Y is

Y = X + start_in_b - start_in_a;

4) The algorithm is symmettric, you just iterate the list to find the first record with start_in_b <= Y, and then

X = Y + start_in_a - start_in_b.

Note 1. For error checking purposes, you might keep the range size in RangeRecord, as well.

Note 2. If O(number of ranges) is not good enough, keep the records as a tree instead of a list. You will need O(log(number of ranges)) operations then,

Answer 4

You have three things you need to adjust for in converting from some X' to Y' and vice versa:

1. The ranges start at different places.
2. One of them is discontinuous.
3. The size of each step is different between the two ranges.

It might be helpful (at least while developing your solutions) to consider a similar range Z, which is the range 0 to 503 and has a one-to-one mapping with the 504 possible values in X. That is, for each discontinuity, if the X value is greater than the upper end of the discontinuity, subtract 99 (the size of the discontinuity). Then X'100 = Z'0, X'200 = Z'100, X'300 = Z'101, X'400 = Z'201, X'500 = Z'202, etc. The introduction of the Z range resolves problems 1 and 2 in the list above.

To convert from Z to Y, you just multiply by 101/504, which scales Z onto Y.