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\$
  • \$\begingroup\$ You should require at least one of the output value to be decimal, otherwise we could return the input everytime. \$\endgroup\$ – The random guy Apr 17 '18 at 13:16
  • \$\begingroup\$ @Therandomguy when graphed it must form a perfectly straight line \$\endgroup\$ – Arnauld Apr 17 '18 at 13:16
  • \$\begingroup\$ Oooooh. i didn't see this. It should spice things up. \$\endgroup\$ – The random guy Apr 17 '18 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 '18 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 '18 at 14:54
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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 78 bytes using a!=b instead of any(a-b) \$\endgroup\$ – ovs Apr 17 '18 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 '18 at 14:48
  • \$\begingroup\$ (because it's provable that the probability for a randomly chosen line to be valid is nonzero) \$\endgroup\$ – user202729 Apr 17 '18 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.

| improve this answer | |
\$\endgroup\$
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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Jelly, 31 bytes

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

Try it online!

Warning: Floating-point inaccuracies.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Doesn't terminate for [1,2,3,4,5,5] in 30 seconds on TIO. Some explanation please? \$\endgroup\$ – user202729 Apr 17 '18 at 15:18
  • \$\begingroup\$ @user202729 Most probably floating-point inaccuracies. I'll check it out. \$\endgroup\$ – Erik the Outgolfer Apr 17 '18 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)
| improve this answer | |
\$\endgroup\$
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!

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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