26
\$\begingroup\$

Given a sorted array of unique positive integers \$A\$ \$(A_0<A_1<\cdots<A_{n-1})\$, and an integer \$t\$, where \$A_0\le t\le A_{n-1}\$. Output the value \$i\$ such that:

  • If \$t \in A\$, \$A_i=t\$.
  • If \$t \notin A\$, \$ \left(i-\left\lfloor i\right\rfloor\right)\cdot A_{\left\lceil i\right\rceil} +\left(\left\lceil i\right\rceil - i\right)\cdot A_{\left\lfloor i\right\rfloor} = t \$. In other words, linearly interpolate between the indices of the two elements of \$A\$ that most narrowly bound \$t\$.

In the above formula, \$\left\lfloor i\right\rfloor\$ means rounding \$i\$ down to integer; \$\left\lceil i\right\rceil\$ means rounding \$i\$ up to integer.

You may also choose 1-indexed array, though you need to adjust the formula and the test cases below accordingly.

Rules

  • This is , shortest code in bytes wins.
  • Floating point errors in output are allowed, but reasonable floating point precision is required. For testcases listed here, your output should be correct with at least 2 decimal places precision.
  • Fraction output is allowed as long as fractions are reduced to their lowest terms.
  • It is fine to use any built-ins in your language. But if built-ins trivialize the question, consider submitting a non-trivial one too.

Testcases

[42], 42 -> 0
[24, 42], 24 -> 0
[24, 42], 42 -> 1
[1, 3, 5, 7, 8, 10, 12], 1 -> 0
[1, 3, 5, 7, 8, 10, 12], 7 -> 3
[1, 3, 5, 7, 8, 10, 12], 12 -> 6
[24, 42], 33 -> 0.5
[24, 42], 30 -> 0.3333333333333333
[1, 3, 5, 7, 8, 10, 12], 2 -> 0.5
[1, 3, 5, 7, 8, 10, 12], 9 -> 4.5
[100, 200, 400, 800], 128 -> 0.28
[100, 200, 400, 800], 228 -> 1.14
[100, 200, 400, 800], 428 -> 2.07
\$\endgroup\$
4
  • 1
    \$\begingroup\$ May we assume the list is non-empty? And what happens if \$ t \$ is outside the range (min ~ max) of the list (e.g. [1, 3, 7], 9)? \$\endgroup\$
    – pxeger
    Nov 12 '21 at 8:04
  • 2
    \$\begingroup\$ @pxeger \$A_0\le t \le A_{n-1}\$. And the list \$A\$ is always non-empty (otherwise, \$A_0\$ in above formula is not defined). \$\endgroup\$
    – tsh
    Nov 12 '21 at 8:05
  • 1
    \$\begingroup\$ You'll be the death of me yet, sideways pitchfork operator! \$\endgroup\$
    – Nate T
    Nov 12 '21 at 12:20
  • 1
    \$\begingroup\$ Wonderfully, Mathematica can do this with builtins: InverseFunction[Interpolation[#,InterpolationOrder->1]][N@#2]&. But it's really long, and also doesn't handle the case where A has only one element. \$\endgroup\$ Nov 13 '21 at 6:06

18 Answers 18

10
\$\begingroup\$

Python 2, 59 bytes

f=lambda l,t,p=0:l<[t]and 1+f(l[1:],t,l[0])or(t-p)/(l[0]-p)

Try it online!

Outputs one-indexed. Recursively loops through the list element , each time adding 1 to the eventual index output, until reaching an element that's at least t. Then, outputs the fraction of the way t is between the current element and previous element p. This avoids needing to explicitly track which index we're at.

62 bytes

lambda l,t:sum(t>y or(t-x)/(y-x)for x,y in zip([0]+l,l)if x<t)

Try it online!

One-indexed. Same idea as the 64-byte code below. Interprets the input as "intervals" (x, y) of two consecutive elements of the list, starting with left endpoint 0. The output is the sum over each interval of the fraction of it that's less below t, which is 1 for intervals fully below t and 0 for those fully above it.

lambda l,t:sum(min(1,max(0,(t-x)/(y-x)))for x,y in zip([0]+l,l))

Try it online!

The summand is (t-x)/(y-x) clamped between 0 and 1.

\$\endgroup\$
2
  • \$\begingroup\$ max(0,(t-x)/(y-x)) can be max(0,t-x)/(y-x) \$\endgroup\$
    – tsh
    Nov 12 '21 at 9:54
  • \$\begingroup\$ @tsh I just included the min/max code to illustrate the clamping formula, but let me know if you see a way to cut it down further below 62. \$\endgroup\$
    – xnor
    Nov 12 '21 at 9:58
5
\$\begingroup\$

JavaScript (ES6), 45 bytes

Expects (t)(A).

t=>g=([c,...a],p=0)=>t>c?1+g(a,c):(t-c)/(c-p)

Try it online!

\$\endgroup\$
5
\$\begingroup\$

MATL, 10 bytes

YYhtfi3$Yn

Inputs are A, then t. The output is 1-based.

Try it online! Or verify all test cases.

Explanation

YY     % Push infinity
h      % Implicit input: row vector A, of length n. Concatenate. This attaches
       % infinity at the end of the vector. This is necessary because
       % interpolation requires a vector of at least 2 entries. The value
       % infinity is used so that it doesn't interfere with the interpolation
tf     % Duplicate, find. This gives the row vector [1 2 3 ... n+1]
i      % Input: integer number t.
3$Yn   % 3-input linear interpolation. Implicit display
\$\endgroup\$
5
\$\begingroup\$

Python 3.10, 79 75 67 65 59 bytes

lambda a,t:(t-a[i:=sum(x<t for x in a)])/(a[i]-[0,*a][i])+i

Attempt This Online!

Needs Python 3.10 to use := inside a subscript.

  • t-a[0]and guards against the edge case where a has only one element
  • sum(x<t for x in a) finds the index of the first item x where x<t
  • (t-a[i]/(a[i+1]-a[i])+i just does the linear interpolation

-4 bytes thanks to Kevin Cruijssen

-6 bytes thanks to tsh

-6 bytes thanks to xnor

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Can't 1for x in a if x<t simply be x<t for x in a? \$\endgroup\$ Nov 12 '21 at 8:31
  • 2
    \$\begingroup\$ len(a)-1 -> t-a[0]; (t-(x:=a[i:=...]))...(a[i+1]-x) -> (t-a[i:=...])...(a[i+1]-a[i]) \$\endgroup\$
    – tsh
    Nov 12 '21 at 8:43
  • 2
    \$\begingroup\$ lambda a,t:t-a[0]and(t-a[i:=sum(x<t for x in a)])/(a[i]-a[i-1])+i \$\endgroup\$
    – tsh
    Nov 12 '21 at 8:51
  • 1
    \$\begingroup\$ A different way to handle where i==0: lambda a,t:(t-a[i:=sum(x<t for x in a)])/(a[i]-[0,*a][i])+i \$\endgroup\$
    – xnor
    Nov 12 '21 at 10:03
4
\$\begingroup\$

Python 3 + numpy, 52 bytes

lambda a,t:interp(t,a,argsort(a))
from numpy import*

Try it online!

As ais sorted with no duplicates we can use argsort to save a byte over r_[:len(a)]. Note that the "no duplicates" is important because numpy doesn't use timsort by default but an unstable qsort.

or (same length)

lambda a,t:interp(t,*unique(a,1))
from numpy import*

Try it online!

This uses numpy.unique (which is a nop on a since a has sorted unique values) with the return_index switch set. This returns the indices of the unique values v in the input. As a has sorted unique values this returns 0,1,...,len(a)-1

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

05AB1E (legacy), 18 17 13 12 bytes

-D¹¥/ā+s®›Ïθ

First input is the list \$A\$, second input is \$t\$. The output \$i\$ is 1-based.

-1 byte switching to the legacy version of 05AB1E, where [1]/[]=[1] instead of []. In the new version of 05AB1E we therefore had to add a before the θ to account for single-item input-lists. Unfortunately, d was is_int instead of >=0 in the legacy version, so we have to replace it with ®› (>-1) instead, netting at -1 byte.

Try it online or verify all test cases.

Explanation:

-             # Subtract each value in the first (implicit) input-list from the
              # second (implicit) input-integer
 D            # Duplicate this list
  ¹           # Push the first input-list again
   ¥          # Pop and push its deltas / forward differences
    /         # Divide the items at the same positions in the two lists
     ā        # Push a list in the range [1,length] (without popping)
      +       # Add that to each value in the list
       s      # Swap to get the duplicated list again
        ®›    # Check for each whether it's larger than -1 (non-negative)
          Ï   # Only keep the items at the truthy indices
           θ  # Pop and leave the last item
              # (after which the result is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

R, 57 55 bytes

Or R>=4.1, 48 bytes by replacing the word function with \.

-2 bytes thanks to @Dominic van Essen.

function(A,t,r=which(A>=t)[1])r-((A-t)/diff(c(0,A)))[r]

Try it online!

1-indexed.

I couldn't make any built-in linear approximation work, but it doesn't mean that such solution doesn't exist @Dominic van Essen could.

\$\endgroup\$
2
2
\$\begingroup\$

Charcoal, 25 bytes

IΣEθ∧κ⌈⟦⁰⌊⟦¹∕⁻η§θ⊖κ⁻ι§θ⊖κ

Try it online! Link is to verbose version of code. Explanation: Port of @xnor's 64-byte Python solution.

   θ                        Input array
  E                         Map over elements
     κ                      Current index
    ∧                       Logical And
              η             Input value
             ⁻              Minus
               §θ⊖κ         Previous element
            ∕               Divided by
                    ι       Current element
                   ⁻        Minus
                     §θ⊖κ   Previous element
         ⌊⟦¹                Clamp above to 1
      ⌈⟦⁰                   Clamp below to 0
 Σ                          Take the sum
I                           Cast to string
                            Implicitly print
\$\endgroup\$
2
\$\begingroup\$

Perl 5, 75 bytes

sub f{($t,$a,$b)=(@_,9e9);$a<=$t&&$t<=$b?($t-$a)/($b-$a):1+f(@_[0,2..$#_])}

Try it online!

Perl5 versions from 5.32 (TIO has 5.28) got chained comparisons capability which means $a<=$t&&$t<=$b can be shortened to $a<=$t<=$b and save 4 bytes.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I'm not sure you're allowed to limit the input arbitrarily to 9e9 but maybe you can prefix a 0 to the list (which is allowed because the input is guaranteed positive) to the same effect, and call the output 1-indexed, possibly even saving 2 bytes? \$\endgroup\$
    – Neil
    Nov 12 '21 at 15:46
2
\$\begingroup\$

Ruby, 50 bytes

f=->l,n,z=0{a,*l=l;a<n ?1+f[l,n,a]:1.0*(n-a)/a-=z}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

R, 41 bytes

function(A,t)approx(B,seq(B<-c(A,0)),t)$y

Try it online!

Almost-trivial use of approx built-in: upvote pajonk's non-trivial R answer instead...

\$\endgroup\$
2
\$\begingroup\$

Haskell, 42 bytes

q 0
q p(h:r)t|h<t=1+q h r t|d<-h-p=(t-p)/d

Try it online!

Main function is q 0, outputs one-indexed.

43 bytes

l%t|let(h:r)?p|h<t=1+r?h|d<-h-p=(t-p)/d=l?0

Try it online!

\$\endgroup\$
2
\$\begingroup\$

C (clang), 74 71 63 bytes

float r;f(*a,t){for(r=0;*a<t;r++)a++;r-=(*a-t)/(*a-*--a+1e-9);}

Try it online!

  • Saved 3 thanks to @upkajdt suggestion to use a variable instead of printing it.

  • Saved 5 thanks for @ths suggestion to make divisor ~0 by adding 1e-9 to it.

  • Saved another 3 by using float r instead of int n as index counter.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Could be 66 byte if some errors is allowed: float r;n;f(*a,t){for(n=0;*a<t;n++)a++;r=n-(*a-t)/(*a-*--a+1e-9);} \$\endgroup\$
    – tsh
    Nov 13 '21 at 16:25
  • \$\begingroup\$ @tsh good one! I added these tests [1,999999] with 2, 999998, 1 and 999999 and it seems to work fine \$\endgroup\$
    – AZTECCO
    Nov 14 '21 at 1:33
1
\$\begingroup\$

Wolfram Language (Mathematica), 44 bytes

Sum[(i=0;{1/(#-i),x<=(i=#)}&/@#2),{x,#}]&

Try it online!

Input [t, A]. Returns 1-indexed.

The private-use character is \[Piecewise], which is usually a less byte-efficient If/Which.

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

Pip -x, 36 bytes

Yb>=_FIa#y-:$/(-[bMXy]+MN:b<=_FIa)|1

Takes the array and the number as command-line arguments. Replit! Or, with a header to simulate the -x flag, Try it online!

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

APL+WIN, 42 bytes

Prompts for vector followed by integer. 1 indexed.

(m/⍳↑⍴m)+(i-m/v)÷(m←<\(i←⎕)≤v)/v-¯1↓0,v←,⎕

Try it online! Thanks to Dyalog Classic

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

Haskell, 76 73 71 bytes

s!x|(t,y:_)<-span(<x)s,u<-last$0:t=fromIntegral(length$t)-1+(x-u)/(y-u)

Try it online

(I hate explicit conversion (in golfing))

\$\endgroup\$
2
  • \$\begingroup\$ nowhere \$\endgroup\$
    – AZTECCO
    Nov 12 '21 at 17:54
  • \$\begingroup\$ Thanks! Always forget this trick. \$\endgroup\$
    – daylily
    Nov 13 '21 at 0:50
0
\$\begingroup\$

Perl 5 + -M5.10.0 -a, 57 bytes

$_>"@F"&&$p<="@F"?say$.-3+("@F"-$p)/($_-$p):0,$p=$_ for<>

Try it online!

Explanation

Naiive approach, but using some Perl var tricks.

-a stores the first input value (the target) in @F which, since we know will only be one value, we can access via "@F". With this we can loop through all other lines of input (for<>) checking if we're greater than the current value and if the $previous was less than of equal to the target and the current ($_) is greater than the target then we output (say) the current index ($. holds the current, 1-indexed, line of input being processed) plus the ratio of the differences between the current and previous, and previous and target.

\$\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.