31
\$\begingroup\$

As input you will receive

  • An integer \$a\$

  • A list of integers that is infinite and strictly-monotonic1.

Your program should check in finite time if \$a\$ appears the list.

You should output one of two disctinct values. One if \$a\$ appears in the list and the other if \$a\$ does not.

This is so answers will be scored by their length in bytes with fewer bytes being better.


You may take an infinite lists in any of the following formats:

  • A list, stream, iterator or generator if your language allows them to be infinite.

  • A function or pointer to a function that outputs the next value when queried with no input.

  • A function or pointer to a function that outputs the \$n\$th value when passed \$n\$ as an input.

Additionally you may repeatedly query STDIN with the assumption that each query will provide the next term in the sequence.


Test cases

Since I cannot put infinite lists in the body of a challenge I will provide the first couple terms along with a description of the list and a definition in Haskell.

6
1 2 3 4 5 6 7 8 9 10 ... (positive integers) l=[1..]
 =>
True

6
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ... (negative integers) l=[-1,-2..]
 =>
False

109
0 2 4 6 8 10 12 14 16 18 20 ... (non-negative even integers) l=[0,2..]
 =>
False

-5
200 199 198 197 196 195 194 193 192 ... (integers smaller than 201) l=[200,199..]
 =>
True

256
1 2 3 5 8 13 21 34 55 89 144 ... (unique fibonacci numbers) l=1:2:zipWith(+)l(tail l)
 =>
False

1
1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 ... (integers less than 2) l=[1,0..]
 =>
True

1: A strictly monotonic sequence is either entirely increasing or entirely decreasing. This means if you take the differences between consecutive elements they will all have the same sign.

\$\endgroup\$
  • 6
    \$\begingroup\$ I think it would be good to have test cases where the target number appears as the first or second entry, since answers using them to determine direction might forget to actually check them. \$\endgroup\$ – xnor Apr 3 at 19:04
  • \$\begingroup\$ @xnor Good suggestion. I've added one where the goal is the first element. \$\endgroup\$ – Wheat Wizard Apr 3 at 19:08
  • \$\begingroup\$ Does a theoretically infinite list fall within the rules? \$\endgroup\$ – S.S. Anne Apr 4 at 0:15
  • \$\begingroup\$ @S.S.Anne I'm not sure what a theoretically infinite list is. \$\endgroup\$ – Wheat Wizard Apr 4 at 0:25
  • \$\begingroup\$ Meaning memory or memory model limits restrict the length of the list but given infinite memory and an unbounded memory model it would work. \$\endgroup\$ – S.S. Anne Apr 4 at 0:27

18 Answers 18

21
\$\begingroup\$

Python 2, 43 bytes

Takes as input the target integer \$a\$, and a lambda function \$g\$. Since the list is always either strictly increasing or decreasing, we only need to check if \$a\$ appears in the next \$ |a-g(0)|+1 \$ numbers.

lambda a,g:a in map(g,range(abs(a-g(0))+1))

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is good. How hard was it to come up with? \$\endgroup\$ – S.S. Anne Apr 4 at 1:22
  • 1
    \$\begingroup\$ Thanks! I wouldn't call it hard, since it was the first and only method I came up with. \$\endgroup\$ – dingledooper Apr 4 at 1:25
7
\$\begingroup\$

Haskell, 33 bytes

t#l@(a:r)=t==a||(a<t)==(l<r)&&t#r

Try it online!

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

Python 3.8 (pre-release), 61 bytes

def f(l,v):
 a=l()
 while(a-v)*(b:=a-l())>0:a-=b
 return a==v

Try it online!

Input is a function that returns the next value on every call and an integer.


Python 3.8 (pre-release), 70 69 bytes

1 byte shorter thanks to @JonathanAllan.

def g(l,v):
 a=next(l)
 while(a-v)*(b:=a-next(l))>0:a-=b
 return a==v

Try it online!

Input is a generator and an integer, can probably be shorter with one of other input formats.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ \nN=next has cost a byte \$\endgroup\$ – Jonathan Allan Apr 3 at 20:07
  • \$\begingroup\$ @JonathanAllan thanks for pointing it out. \$\endgroup\$ – ovs Apr 3 at 20:48
  • \$\begingroup\$ Python 3.8 is already released, by the way. \$\endgroup\$ – user2357112 supports Monica Apr 4 at 6:40
  • \$\begingroup\$ @user2357112 It's not manually typed out. That's just the way TIO has it on there. \$\endgroup\$ – S.S. Anne Apr 4 at 18:07
  • \$\begingroup\$ a*(b:=a-l())>v*b for a byte saved \$\endgroup\$ – Olivier Grégoire Apr 7 at 7:17
4
\$\begingroup\$

Haskell, 43 bytes

a#k@(b:c)|k>c=(-a)#map(0-)k|b<a=a#c|1>0=b>a

Try it online!

This outputs False if the integer is present and True if it is not although I have added a not to the handler because that sort of output is confusing to me.


Explanation

The first check we do is k>c, that is whether the input is greater than its own tail. Since this list is strictly monotonic the heads of these lists cannot be equal so k>c is a short way of comparing their heads. This check thus tells us whether the first element is larger than the second and by extension whether the input is decreasing. If the input is decreasing we negate everything to make it increasing

(-a)#map(0-)k

The next check is whether b<a, that is the head of the list is less than the thing we are looking for. If it is then we should find a later in the list so we discard b and go again

a#c

If that fails then a<=b meaning that either b is a or b should come before a. Since b is the first element we know that the only way for a to be present is for it to be b. Thus we halt returning

b>a

Which is a shorter way of writing b/=a since we know already that b>=a.

| improve this answer | |
\$\endgroup\$
  • 5
    \$\begingroup\$ I am pretty sure people are encouraged to answer their own posts but after giving a reasonable amount of time for other people to write their own answers. \$\endgroup\$ – RGS Apr 3 at 23:22
  • \$\begingroup\$ @RGS I started writing this answer half an hour after posting when there were already two answers. \$\endgroup\$ – Wheat Wizard Apr 4 at 0:01
  • 2
    \$\begingroup\$ The average time I've seen is around two days. \$\endgroup\$ – S.S. Anne Apr 4 at 0:17
  • 3
    \$\begingroup\$ I think half an hour doesn't qualify as "reasonable amount of time" :) in half an hour most people won't even have the chance to read your post, let alone answer it. \$\endgroup\$ – RGS Apr 4 at 8:23
  • \$\begingroup\$ @RGS Well I do. \$\endgroup\$ – Wheat Wizard Apr 4 at 14:07
4
\$\begingroup\$

Bash + GNU utilities, 47 44 43 42 bytes

read m
sed 1$[(m-($1))**2]q\;i$m|grep ^$1$

Try the test suite online!

3 bytes off thanks to user41805's pointing out that a single sed could be used to replace both the echo and the head.

1 more byte thanks to user41805 again.

And now 1 more from user41805.

The target integer (the integer \$a\$ in the challenge description) is passed as an argument, and the infinite list is read from stdin. (The challenge says: "Additionally you may repeatedly query STDIN with the assumption that each query will provide the next term in the sequence.")

The output is the program's exit code (0 for truthy, 1 for falsey).


Explanation:

The program reads the first number in the infinite list into \$m\$.

Let \$a\$ be the target integer that we're looking for (it's $1 in the program). In principle we need to check, after \$m\$, at most \$\left| m-a \right|\$ additional values in the infinite list, because we're starting at \$m\$ and either going up by at least 1 for each number in the list or going down by at least 1 for each number in the list.

However, the program actually checks (more than) \$(m-a)^2\$ additional values. That's OK, because \$(m-a)^2\ge\left|m-a\right|\$. We may be checking additional (unnecessary) values, but that's harmless.

The original version checked exactly \$(m-a)^2\$ additional numbers (using head). Unfortunately, replacing head -${n} with sed -${n}q doesn't work if the value of n is 0, so we need to enlarge the number of items checked. To do this, I simply prepend a 1 to the number (which takes one fewer byte than adding 1 to it).

The golfing benefit in doing all this is that, in bash, squaring a number requires fewer bytes than taking the absolute value of a number (as far as I can see).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You should be able to convert (echo $m;head -$[(m-($1))**2]) into a single sed 'call', and so remove the need for the parens \$\endgroup\$ – user41805 Apr 14 at 10:20
  • \$\begingroup\$ @user41805 Thanks -- I hadn't thought of using sed to replace both the echo and the head. (I had tried replacing head with sed early on but just doing that didn't shorten things.) \$\endgroup\$ – Mitchell Spector Apr 14 at 16:55
  • \$\begingroup\$ Nice including the 1 in front of the number, I missed that, this now allows you to bring 1i$m after the q statement, saving on the newline and the quotes. Additionally, the 1 can be dropped as well. Hm I wonder if awk would be shorter \$\endgroup\$ – user41805 Apr 15 at 5:42
  • \$\begingroup\$ @user41805 Thanks again -- reversing the order of the sed commands saved a byte. It got rid of the quotes, but the newline had to be replaced with the 2 characters \;. I haven't looked into using awk. \$\endgroup\$ – Mitchell Spector Apr 16 at 2:13
  • \$\begingroup\$ You should be able to remove the 1 in 1i$m \$\endgroup\$ – user41805 Apr 16 at 5:11
2
\$\begingroup\$

Ruby, 39 bytes

->a,g{[]!=[a]&(0..a*a+g[0]**2).map(&g)}

Try it online!

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

APL (Dyalog Unicode), 15 bytesSBCS

{⍵∊⍺⍺⍳1+|⍵-⍺⍺1}

Try it online! Uses dingledooper's idea.

{             } ⍝ Operator accepting function on the left and integer on the right
   ⍺⍺           ⍝ Apply the input function to
     ⍳           ⍝ the range of integers from 1 to
      1+         ⍝ 1 plus
        |        ⍝ the absolute value of
         ⍵-      ⍝ the input number minus
           ⍺⍺1   ⍝ the first value of the input function.
 ⍵∊              ⍝ Finally check if the input number is in that list.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You need to include {} in a dfn, because by itself it isn't a valid function \$\endgroup\$ – user41805 Apr 4 at 16:50
  • \$\begingroup\$ @user41805 Are you sure? :'( \$\endgroup\$ – RGS Apr 4 at 17:07
  • \$\begingroup\$ @RGS Yes. \$\endgroup\$ – Adám Apr 5 at 10:09
  • \$\begingroup\$ @Adám damn it, went from "winning by 1 byte" to "2nd place by 1 byte" :) \$\endgroup\$ – RGS Apr 5 at 10:18
  • 1
    \$\begingroup\$ @RGS Don't worry about it; you're still winning big in the "production languages" category! \$\endgroup\$ – Adám Apr 5 at 10:20
2
\$\begingroup\$

05AB1E, 14 13 bytes

D¥нdiIë(I(}.i

-1 byte thanks to @Grimmy.

05AB1E has infinite lists, but no functions. So it assumes the infinite list is already at the top of the stack. Assuming this is allowed for stack-based languages according to the meta, but it explicitly mentions functions, so not sure how to handle it here.

Alternatively, the infinite list can be put in a pre-defined variable (i.e. X), in which case this would be 15 bytes with that X as additional leading byte.

Try it online or verify all test cases. The second line of the header contains the infinite list(s). In the output the first 10 values are printed as example sublist, so you know which infinite list was used in the program.

Explanation:

05AB1E has a builtin to check if an integer is in an infinite list that is guaranteed to be non-decreasing, which is .i. Using that builtin, we have the following program:

D         # Duplicate the infinite list at the top of the stack
 ¥        # Take it's deltas / forward-differences
  н       # Pop and push the first difference of this list
   di     # If it's non-negative:
     I    #  Simply push the input-integer
    ë     # Else (it's negative):
     (    #  Negate all values in the infinite list
      I(  #  Push the input-integer, and negate it as well
    }     # After the if-else, where we now have a non-decreasing infinite list
     .i   # Check if the (possibly negative) input we pushed is inside this infinite list
          # (after which the result is output implicitly)

Note that this approach only works because the infinite list is guaranteed to be either only increasing or only decreasing. With an infinite list that is both (i.e. \$a(n) = \left\lfloor10\tan(n)\right\rfloor\$[0, 15, -22, -2, 11, -34, -3, 8, -68, -5, ...]), this approach of course wouldn't work.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Is the 11th byte y or I? \$\endgroup\$ – Greg Martin Apr 4 at 16:16
  • \$\begingroup\$ @GregMartin Oops.. error curing copy-paste from the test suite. It's supposed to be I (push input). Thanks for noticing. \$\endgroup\$ – Kevin Cruijssen Apr 4 at 16:49
  • \$\begingroup\$ 0‹ can be d by switching the two branches. \$\endgroup\$ – Grimmy Apr 6 at 8:06
  • 1
    \$\begingroup\$ Here's a 7 \$\endgroup\$ – Grimmy Apr 6 at 8:22
  • 1
    \$\begingroup\$ @Grimmy Nice approach! I think it might be better if you post it as a separated answer, since it's completely different from my approach with .i. :) \$\endgroup\$ – Kevin Cruijssen Apr 6 at 8:29
2
\$\begingroup\$

Pyth, 20 17 16 9 bytes

Takes a on STDIN, then a list of values on STDIN.

Edit: Wow, under 10 bytes now! Really shows how powerful Pyth is :P

}Q+JEmEaJ

Try it online!

Port of @dingledooper's Python answer.

}Q+JEmEaJ
 Q              # Initialize Q to be the first input from STDIN
   JE           # Initialize J to be the next input from STDIN
}Q              # Return true if Q is in:
  +             #   The union of 
   JE           #      - the first element of the sequence
     mEaJ(Q)    #      - abs(J-Q) more inputs from STDIN (Q appended implicitly)

8 bytes, if we can return the index of a in the list

x+JEmEaJ

Try it online!

x+JEmEaJ
x          (Q)  # Find index of Q in:
 +              #   The union of:
  JEmEaJ(Q)     # J and the next abs(J-Q) elements
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

GolfScript, 33 bytes

(@:k\-abs:r;0:g;{(k=g+:g;}r*;r!g+

Try it online!

This is a very, very quick and dirty way of doing this problem.

TL;DR

Check if the first number is the number we're looking for. If not, then find the difference between our number (finite) and the first number (finite) to get the maximum number of elements we need to search (finite). This is a clusterfuck, clumsy, and messy, but it does the job adequately. There's probably a builtin I'm missing, but I'll come back to this later to refine it and to make code short enough worthy of an explanation.

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

Charcoal, 24 bytes

NθNηNζW›Π⁻⟦θη⟧ζ⁰Nζ№⟦ηζ⟧θ

Try it online! Link is to verbose version of code. Reads each value as a separate line on STDIN and outputs - only if a appears in the monotonic list. Explanation:

Nθ

Input a.

NηNζ

Input the first two terms of the list.

W›Π⁻⟦θη⟧ζ⁰

Repeat while the last term of the list so far lies between a and the first term.

Nζ

Read another term from the list.

№⟦ηζ⟧θ

Output - if a is the first term or the term just read.

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

JavaScript (ES7), 49 bytes

Using @dingledooper's method

Takes input as (integer)(generating_function). Returns \$0\$ or \$1\$.

n=>g=>(F=k=>k*k>(g(0)-n)**2?0:g(k)-n?F(k+1):1)(0)

Try it online!


JavaScript (ES6), 54 bytes

Takes input as (integer)(generating_function). Returns a Boolean value.

n=>g=>(F=k=>(v=g(k),g(1)>g(0)?v<n:v>n)?F(k+1):v)(0)==n

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You don't need $$k^2>(g(0)-n)^2$$, $$k$$ being some larger is not a problem \$\endgroup\$ – l4m2 Apr 20 at 13:52
1
\$\begingroup\$

C (gcc), 59 bytes

t;f(a,p)int*p;{for(t=abs(a-*p)+2;t-->0;)t=*p++-a?t:-1;++t;}

Takes a pointer to an "infinite" array. The way I implement this is to only calculate the numbers that are used (and then a "safe buffer" at the end to make sure I don't have any off-by-one errors, but this won't skew the result).

Es un puerto de la solución de dingledooper.

-1 byte thanks to ceilingcat!

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice, but did you forget to remove that ‘n’ at the beginning, because I don’t really see the point of it. \$\endgroup\$ – dingledooper Apr 4 at 6:59
  • \$\begingroup\$ That was from the old way, with the generator function. I'll get rid of it when I have access to my computer. \$\endgroup\$ – S.S. Anne Apr 4 at 17:41
  • \$\begingroup\$ How would it stop in case of the second case? (6 in -1,-2,...) \$\endgroup\$ – Varad Mahashabde Apr 6 at 20:52
  • \$\begingroup\$ @VaradMahashabde That's what the abs is for in the initialization of the counter variable. \$\endgroup\$ – S.S. Anne Apr 6 at 20:55
1
\$\begingroup\$

05AB1E, 7 6 bytes

α¬>£0å

Try it online! or verify all test cases.

Takes the infinite list input via the stack, like Kevin's 05AB1E answer.

α              # absolute difference of the number with each element of the infinite list
               # this list contains 0 iff the original list contains the number
 ¬             # get the first element
  >            # increment
   £           # get the first n elements, where n = first element + 1
    0å         # check if 0 is in those elements
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Ah, good point. \$\endgroup\$ – Kevin Cruijssen Apr 6 at 8:58
0
\$\begingroup\$

Perl 5, 55 bytes

sub f{$f=pop;@L=($F=&$f,map&$f,0..abs$_[0]-$F);pop~~@L}

Try it online!

More or less a translation of @dingledooper's Python2 answer.

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

perl -lE, 34 bytes

$t=<>;{$_=<>;$_<$t?redo:say$_==$t}

Try it online!

Prints 1 followed by a newline if the first element of the list appears elsewhere; otherwise, it just prints a newline. The program terminates after reading the first number which is equal or larger than the first number.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think this works for decreasing input sequences: Try it online! \$\endgroup\$ – math junkie Apr 3 at 22:41
0
\$\begingroup\$

Java (JDK), 67 bytes

a->s->{int p=s.get(),n;for(;p*(n=p-s.get())>a*n;)p-=n;return p==a;}

Try it online!

Credits

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

C++ (gcc), 114 bytes 106 bytes

#include<iostream>
int f(int a){int p,t;std::cin>>t;if(t-=a)for(;p=t,std::cin>>t,t-=a,p*t>t*t;);return!t;}

Try it online!


Explanation :

Our only hope of finding \$\alpha\$ in the future terms of the list \$t\$ is if :

  • We don't skip over \$\alpha \implies\$ The difference of \$\alpha\$ and \$t_n\$ doesn't change signs \$\implies \left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right)>0 \space \forall \space n\in N, n > 1\$.(If it is zero, one of the terms is our target)
  • The series approaches our target \$\implies {\left| \alpha - t_n\right|} < {\left| \alpha - t_{n-1}\right|}\$

We can then combine these two conditions :
$$ {\left| \alpha - t_n\right|} < {\left| \alpha - t_{n-1}\right|} $$ $$ \implies {\left| \alpha - t_n\right|} \cdot {\left| \alpha - t_{n-1}\right|} < {\left( \alpha - t_{n-1}\right)}^2$$ $$ \text{Since we need that}\left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right)>0, $$ $$ \text{Condition } P \equiv \left( {\left| \alpha - t_n\right|} < {\left| \alpha - t_{n-1}\right|} \right) \land \left( \left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right)>0 \right) $$ $$ P \equiv \left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right) < {\left(\alpha - t_{n-1}\right)}^2 $$

Hence if \$P\$ is found to be false the either the target has been found or we have passed it (or never reach it).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @ceilingcat Thanks! \$\endgroup\$ – Varad Mahashabde Apr 7 at 8:35

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.