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\$
10
  • 7
    \$\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 '20 at 19:04
  • \$\begingroup\$ @xnor Good suggestion. I've added one where the goal is the first element. \$\endgroup\$ – Wheat Wizard Apr 3 '20 at 19:08
  • \$\begingroup\$ Does a theoretically infinite list fall within the rules? \$\endgroup\$ – S.S. Anne Apr 4 '20 at 0:15
  • \$\begingroup\$ @S.S.Anne I'm not sure what a theoretically infinite list is. \$\endgroup\$ – Wheat Wizard Apr 4 '20 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 '20 at 0:27

21 Answers 21

22
\$\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!

\$\endgroup\$
2
  • \$\begingroup\$ This is good. How hard was it to come up with? \$\endgroup\$ – S.S. Anne Apr 4 '20 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 '20 at 1:25
7
\$\begingroup\$

Haskell, 33 bytes

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

Try it online!

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

\$\endgroup\$
5
  • 1
    \$\begingroup\$ \nN=next has cost a byte \$\endgroup\$ – Jonathan Allan Apr 3 '20 at 20:07
  • \$\begingroup\$ @JonathanAllan thanks for pointing it out. \$\endgroup\$ – ovs Apr 3 '20 at 20:48
  • \$\begingroup\$ Python 3.8 is already released, by the way. \$\endgroup\$ – user2357112 supports Monica Apr 4 '20 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 '20 at 18:07
  • \$\begingroup\$ a*(b:=a-l())>v*b for a byte saved \$\endgroup\$ – Olivier Grégoire Apr 7 '20 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.

\$\endgroup\$
0
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).

\$\endgroup\$
6
  • \$\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 '20 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 '20 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 '20 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 '20 at 2:13
  • \$\begingroup\$ You should be able to remove the 1 in 1i$m \$\endgroup\$ – user41805 Apr 16 '20 at 5:11
4
\$\begingroup\$

convey, 144 92 bytes

 v<<<<<<<<<<<
>;  >">>??>=@]
"">>,<1[v)>#,
v}^>)?:`(#>#^
v{^"9>v]^",^
>;@">>@`"#^
1>0   >>>^

Try it online!

Gif

Input is given as a list of integers with the first integer being the goal and the remaining being the list. Since there is no way to accept infinite input, this program instead only consumes a prefix of the input. You can see this in that there is a very long relay line to stop additional input.

Explanation

To start we need to split the first element off the input, to be used. To do this I use a simple switch, and because we want to use the input a bunch I feed it into a sort of generating vortex to continuously pump out new copies.

Explanation 0

Now we split the main stream in two, and calculate the differences on one of the parts. This will tell us if the list is ascending or descending.

Explanation 1 (Ascending)

Explanation 1 (Descending)

Now we use the difference stream to redirect the main stream, to the two different comparison sites. If the list is ascending we want to go until the element is greater than or equal to n if it is descending we want to go until it is less than or equal to n.

Explanation 2

So that stream coming out now will give us some ones and then at some point switch to zeros. What we are concerned about is the first number that gives a zero. We want to know if it is equal to n. So we create another stream and get whether that is equal to n.

Explanation 3

At this point I'm going to stop with the gifs, since they really look like the end product mostly. We redirect the streams with each other, discarding all the elements before the comparison starts giving zero. Then we use a lock to grab just the first equality. We output this and send a signal to stop taking input. With no input the machine slowly winds down and halts.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Congratulations, you are the first other convey user! I'm really happy that it's apparently usable for someone else, thanks! :-) If there is a fixed number of elements, you can often use ? instead of @, e.g. at the top instead of 01@v…>(, ?v…>(. Or at the bottom ? to just have one element: this should be equivalent. And there seems to be a bug that & omits every second item in this configuration, will try to fix that now. \$\endgroup\$ – xash Dec 12 '20 at 15:40
  • \$\begingroup\$ @xash Thank you convey is a lot of fun! I figured how to use ? a bit on my second try (which is a lot shorter). On the topic of bugs is # supposed to act like a queue? It has been a bit of a source of frustration for me and I don't see it in the docs. \$\endgroup\$ – Wheat Wizard Dec 12 '20 at 16:18
  • \$\begingroup\$ … finally fixed # and & passing all my tests and both your solutions. They shouldn't queue, but I guess the paths shouldn't block each other. Nice second solution! \$\endgroup\$ – xash Dec 12 '20 at 17:35
2
\$\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.

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

Ruby, 39 bytes

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

Try it online!

\$\endgroup\$
1
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.
\$\endgroup\$
5
  • \$\begingroup\$ You need to include {} in a dfn, because by itself it isn't a valid function \$\endgroup\$ – user41805 Apr 4 '20 at 16:50
  • \$\begingroup\$ @user41805 Are you sure? :'( \$\endgroup\$ – RGS Apr 4 '20 at 17:07
  • \$\begingroup\$ @RGS Yes. \$\endgroup\$ – Adám Apr 5 '20 at 10:09
  • \$\begingroup\$ @Adám damn it, went from "winning by 1 byte" to "2nd place by 1 byte" :) \$\endgroup\$ – RGS Apr 5 '20 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 '20 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.

\$\endgroup\$
6
  • \$\begingroup\$ Is the 11th byte y or I? \$\endgroup\$ – Greg Martin Apr 4 '20 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 '20 at 16:49
  • \$\begingroup\$ 0‹ can be d by switching the two branches. \$\endgroup\$ – Grimmy Apr 6 '20 at 8:06
  • 1
    \$\begingroup\$ Here's a 7 \$\endgroup\$ – Grimmy Apr 6 '20 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 '20 at 8:29
2
\$\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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Ah, good point. \$\endgroup\$ – Kevin Cruijssen Apr 6 '20 at 8:58
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
\$\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.

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

\$\endgroup\$
1
  • \$\begingroup\$ You don't need $$k^2>(g(0)-n)^2$$, $$k$$ being some larger is not a problem \$\endgroup\$ – l4m2 Apr 20 '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!

\$\endgroup\$
4
  • 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 '20 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 '20 at 17:41
  • \$\begingroup\$ How would it stop in case of the second case? (6 in -1,-2,...) \$\endgroup\$ – Varad Mahashabde Apr 6 '20 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 '20 at 20:55
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.

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I don't think this works for decreasing input sequences: Try it online! \$\endgroup\$ – math junkie Apr 3 '20 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

\$\endgroup\$
0
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).

\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat Thanks! \$\endgroup\$ – Varad Mahashabde Apr 7 '20 at 8:35
0
\$\begingroup\$

Ruby, 56 bytes

f=->a,g,t=1{a==g[t]||(g[2]-g[1])*(g[t]-a)<0&&f[a,g,t+1]}

Recursively, checks if current term g[t] == a, then return true. Else, check if the product of difference g[2] - g[1] and a - g[t] are of opposite sign, if yes, then return false

Try it online!


Ruby, 40 bytes

Port of dingledooper's Python answer!

->a,g{(1..(a-g[0]).abs+1).map(&g).any?a}

Try it online!

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

Wolfram Language (Mathematica), 31 bytes

#2@Range@Abs[#-#2@0]~MemberQ~#&

Port of dingledooper's python 2 solution.

Try it online!

Other similar attempts:

⌊#⌋==#&&#>=1&@InverseFunction[#2]@#&

and:

Tr[1^Solve[#2@x==#,x,PositiveIntegers]]==1&

9 bytes

Mathematica doesn't have iterators or generators in the same way python does, but Regions and Domains take their place. If you allow Regions as an equivalent,

{#}∈#2&

just tests if the 1d point of the first argument is in the Region. RAW (Rules as written) don't allow Regions, so I'm going to leave the port as the main answer.

Try it online!

The best solution is just Mathematica's built-in Element over a domain, but Domains do not seem to be able to be defined by the users, only the premade handful exist.

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