11
\$\begingroup\$

Description

You are given the results of a range function where every element has been rounded down to the nearest whole number. Your goal is to recover the original list.

For example, the following function (in Python3) will produce an input for your program:

from numpy import arange, floor
def floored_range(A, B, C):
    return list(floor(arange(A, B, C)))

The output of your program should be a valid guess of the original data. Here, valid guess means that it must exactly match the input when floored and it must be a possible output of a range function (ie, when graphed it must form a perfectly straight line).

Examples

Input: [1,2,3,4]  
Output: [1,2,3,4]  

Input: [1,2,3,4]  
Output: [1.9,2.7,3.5,4.3]  

Input: [1,2,3,4,5,5]  
Output: [1.9,2.7,3.5,4.3,5.1,5.9]  

Input: [1,1,2,2,3,3,4,4]  
Output: [1,1.5,2,2.5,3,3.5,4,4.5]  

Input: [1,1,2,3,3,4]  
Output: [1,1.7,2.4,3.1,3.8,4.5]

Input: [56, 54, 52, 50, 48, 45, 43, 41, 39, 37, 35, 32, 30, 28, 26, 24, 22, 19, 17, 15, 13, 11]
Output: [56.7  , 54.541, 52.382, 50.223, 48.064, 45.905, 43.746, 41.587,
   39.428, 37.269, 35.11 , 32.951, 30.792, 28.633, 26.474, 24.315,
   22.156, 19.997, 17.838, 15.679, 13.52 , 11.361]
\$\endgroup\$
15
  • \$\begingroup\$ You should require at least one of the output value to be decimal, otherwise we could return the input everytime. \$\endgroup\$ Apr 17, 2018 at 13:16
  • \$\begingroup\$ @Therandomguy when graphed it must form a perfectly straight line \$\endgroup\$
    – Arnauld
    Apr 17, 2018 at 13:16
  • \$\begingroup\$ Oooooh. i didn't see this. It should spice things up. \$\endgroup\$ Apr 17, 2018 at 13:18
  • 1
    \$\begingroup\$ Using the formula in the question, A, B, C can be any three floats. The input floored range can, for example, start at 56.7, end at 10.2 and have a step size of -2.159. The only thing that matters is that the points you output, when floored, exactly match the input. I've added an example showing that. \$\endgroup\$
    – Kyle G
    Apr 17, 2018 at 13:51
  • 2
    \$\begingroup\$ @Rod As I see it, the point of the original second test case was to illustrate that several outputs are possible for the same input \$\endgroup\$
    – Luis Mendo
    Apr 17, 2018 at 14:54

7 Answers 7

3
\$\begingroup\$

Octave, 82 bytes

function y=f(x)
while any(floor(y=linspace(x(1)+rand,x(end)+rand,numel(x)))-x),end

Running time is non-deterministic, but the code ends in finite time with probability 1.

Try it online!

Explanation

The code defines a function of x that outputs y. The function consists of a while loop.

In each iteration, the right amount (numel(x)) of linearly spaced values are generated (linspace), starting at x(1)+rand and ending at x(end)+rand. These two calls to the rand function give random offsets between 0 and 1, which are applied to the initial and final values of x.

The loop is repeated for as long as any of the floored results differs (-) from the corresponding entry in x.

\$\endgroup\$
3
  • \$\begingroup\$ 78 bytes using a!=b instead of any(a-b) \$\endgroup\$
    – ovs
    Apr 17, 2018 at 14:41
  • \$\begingroup\$ @ovs Unfortunately that doesn't work, because it stops as soon as some output entry equals that in the input, not when all do. See second entry of the second output in your link \$\endgroup\$
    – Luis Mendo
    Apr 17, 2018 at 14:48
  • \$\begingroup\$ (because it's provable that the probability for a randomly chosen line to be valid is nonzero) \$\endgroup\$
    – DELETE_ME
    Apr 17, 2018 at 15:17
3
\$\begingroup\$

Python 3, 189 bytes

def f(l):
 R=range(len(l));e=1-1e-9
 for j in R:
  for I in range(j*4):
   i=I//4;L=[((l[i]+I//2%2*e)*(x-j)-(l[j]+I%2*e)*(x-i))/(i-j)for x in R]
   if[x//1 for x in L]==l:return L
 return l

Try it online!

Cubic time.

Has some numerical issues.

\$\endgroup\$
0
3
\$\begingroup\$

R, 86 bytes

function(n){while(any(n-(x=seq(n[1]+runif(1),tail(n,1)+runif(1),l=sum(n|1)))%/%1))0;x}

Try it online!

R port of Luis Mendo's answer; it does issue a number of warnings because of any coercing to logical but these can be ignored.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 168 bytes

def f(l):r=range(len(l));g=lambda n:[(l[b]+n-l[a])/(b-a)for a in r for b in r if b>a]or[0];s=(max(g(-1))+min(g(1)))/2;m=min(a*s-l[a]for a in r);return[a*s-m for a in r]

Try it online! Explanation: g calculates the limiting values for C that lie just outside the range for A and B to exist. The average is then taken to give a usable value for C, and then the lowest possible range is then generated.

\$\endgroup\$
0
\$\begingroup\$

Jelly, 31 bytes

ṾṚ”.;V×LḶ$}+©1ị$}IEȧḞ⁼¥ʋ
0ç1#®ḷ

Try it online!

Warning: Floating-point inaccuracies.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Doesn't terminate for [1,2,3,4,5,5] in 30 seconds on TIO. Some explanation please? \$\endgroup\$
    – DELETE_ME
    Apr 17, 2018 at 15:18
  • \$\begingroup\$ @user202729 Most probably floating-point inaccuracies. I'll check it out. \$\endgroup\$ Apr 17, 2018 at 18:33
0
\$\begingroup\$

JavaScript (Node.js), 94 bytes, assuming input length > 1

f=x=>(t=x.map(_=>a+=b,b=x[1]+(c=Math.random)(a=x[0]+c())-a,a-=b)).map(Math.floor)+''==x?t:f(x)

Try it online!

97 bytes

f=x=>(t=x.map(_=>a+=b,b=x[1]+(c=Math.random)(a=x[0]+c())-a||0,a-=b)).map(Math.floor)+''==x?t:f(x)
\$\endgroup\$
1
0
\$\begingroup\$

Python 2, 212 bytes

def f(l):
 C=[(0,1.,0,1.)]
 for a,A,b,B in C:
  x,y=(A+a)/2,(B+b)/2;r=[l[0]+x+i*(l[-1]+y-l[0]-x)/(~-len(l)or 1)for i in range(len(l))];C+=[(x,A,y,B),(a,x,y,B),(x,A,b,y),(a,x,b,y)]
  if[n//1for n in r]==l:return r

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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