3
\$\begingroup\$

In this challenge you will take a non-empty (finite) list of (possibly infinite) lists of positive integers, and your task is to output the longest one. An infinite list is longer than a finite list of any length, and any two infinite lists are equally long.

You're guaranteed that there won't be any ties for longest between two distinct lists. That is, if two lists are tied for longest, whether they are finite or infinite, they will be equal so it won't matter which one you output.

Standard rules apply for outputting an infinite list.

This is . The goal is to minimize the size of your source code as measured in bytes.

A useful note from xnor:

I think it's important for solvers to realize that you have to be outputting list entries as you go in some situations. There's no hope to find which list is longest then fully output it.

Test cases

[1,1,1,1,1,1,1,1]
[2,2,2]
[]
=>
[1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1]
[2,2,2,9,9,9,9,9,9]
[]
=>
[2,2,2,9,9,9,9,9,9]
[1,2,3]
[1,2,3]
[2,4]
=>
[1,2,3]
[1,2,3,4,5,6,7,8,9,10,11,12,...]
[1,2,3,4,5,6,7,8,12]
[9,2]
=>
[1,2,3,4,5,6,7,8,9,10,11,12,...]
[2,6,4,5,6,7,8,9,10,11,12,13,...]
[2,6,4,5,6,7,8,9,10,11,12,13,...]
=>
[2,6,4,5,6,7,8,9,10,11,12,13,...]
[2,6,4,5,6,7,8,9,10,11,12,13,...]
[2,6,4,5]
[9,8,12,3]
=>
[2,6,4,5,6,7,8,9,10,11,12,13,...]
[1,2,3,4,5,6,7,8,9,10,11,12,...]
[1,2,3,4,5,6,7,8,9,10,11,12,...]
[1,2,3,4,5,6,7,8,12]
[9,2]
=>
[1,2,3,4,5,6,7,8,9,10,11,12,...]

The following cases are examples of undefined behavior, you may do whatever you wish including looping forever.

[1,2,3]
[1,2,3]
[2,6,7]
[2,4,6,8,10,12,14,16,...]
[1,3,5,7,9,11,13,15,...]
\$\endgroup\$
20
  • 2
    \$\begingroup\$ Could you give a bit of clarity (or examples) about the input format(s). For instance, examples of how we might determine whether one-or-more input lists are infinite, without keeping reading from them until all-but-one of them have ended. Edit: or is that the idea of the challenge...? \$\endgroup\$ Oct 4, 2023 at 15:18
  • 2
    \$\begingroup\$ @DominicvanEssen You cannot determine in finite time if a possibly infinite list is finite or infinite. This means you have to start outputting without fully knowing how long the longest list is. \$\endgroup\$
    – Wheat Wizard
    Oct 4, 2023 at 15:20
  • 1
    \$\begingroup\$ I'm not sure I've fully got my head around this. If the input is [list of all odd numbers, list of all even numbers, list of just 1..10] then the first two items are the same length (infinite), right? But we can't ever be sure of it (because one of them might eventually stop), so how can we start outputting...? \$\endgroup\$ Oct 4, 2023 at 15:23
  • 5
    \$\begingroup\$ I think it's important for solvers to realize that you have to be outputting list entries as you go in some situations. There's no hope to find which list is longest then fully output it. \$\endgroup\$
    – xnor
    Oct 4, 2023 at 15:53
  • 7
    \$\begingroup\$ It kinda feels like this challenge is trying to be intentionally cryptic; there's only really one valid way to go about it, but the challenge seems to avoid describing what that is. It really just makes it harder to read, and since the valid solution isn't necessarily going to be intuitive (I didn't think of it until my second or third read-through) or even possible in some languages (i.e., any that take input from STDIN or some other single stream of data, without a really creative input format), it just makes the challenge artifically harder and more confusing. \$\endgroup\$ Oct 4, 2023 at 16:33

7 Answers 7

8
\$\begingroup\$

Python, 74 74 bytes

f=lambda i,n,m=0:1<len(r:={x(n)for x in i if x(m)})and f(i,n,m+1)or sum(r)

Attempt This Online!

Previous version had a bug

Potentially infinite lists are represented as functions that take an index and return the value at that index. If the index is out of bounds the function returns a zero.

\$\endgroup\$
6
\$\begingroup\$

Haskell, 67 58 bytes

foldl1(#)
(a:b)#(x:y)|a==x=a:b#y
c#z|(1<$c)>(1<$z)=c|0<1=z

Attempt This Online!

-9 thanks to AnttiP mixing pattern failure and guard failure

Test harness truncates to run all the cases in one go, but it can be run infinitely.

Since the algorithm may be non-obvious and not everyone can read Haskell:

Explanation

foldl1 (#)

The function submission operating on a list of lists just reduces the list by a function of two lists, the infix operator #. (Since the input is guaranteed non-empty, foldl1 won't error.)

(a:b) # (x:y)
  | a == x = a : (b # y)

The critical part for handling duplicate infinite lists: if the first element of both lists is the same, then put that element in the output list and recur on the remainders of both.

c # z
  | (1 <$ c) > (1 <$ z) = c
  | otherwise = z

And here's the part that actually takes the longest list, if the previous clause failed. Since one of the lists can still be infinite, an actual length comparison is out of the question, but replacing every element of both lists with 1, a lexicographic comparison will terminate as soon as it reaches the point where one list ends and not the other.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ You can save 9 bytes by moving the list comparison to the last line Attempt This Online! \$\endgroup\$
    – AnttiP
    Oct 4, 2023 at 21:06
5
\$\begingroup\$

Ruby, 124 123 bytes

Input is an array of Enumerators. Zips answers together until enough of them reach the ends of their sequences that the ones that remain are all equivalent, prints that, and keeps going.

->a{g=->{a.map{_1.next rescue p}};t=a;(t=g[]
t=t.zip(g[]).map{_2&&[*_1,_2]}while(t&t-[p])[1]
r,=t-[p];p *r)while(t-[p])[0]}

Attempt This Online!

Explanation
->a{                              # Lambda definition
    g=->{a.map{_1.next rescue p}} # Lambda to take the next element of each Enumerator
                                  #  If it throws StopIteration, output nil instead
    t=a                           # Set t to a as dummy value for while loop
    (                             # Start of instructions to loop over
      t=g[]                       #  Overwrite t with the next elements
                                  #  Start of a one-line while loop
      t=                          #   Set t to
        t.zip(g[])                #    t zipped with the next elements
                                  #    (will look like this: [[1,2,3],4])
         .map{                    #    Map over the zipped result
              _2                  #     If next element is nil, return just that
                &&                #     Otherwise,
                  [*_1,_2]        #     Combine the elements together
         }
       while(t&t-[p])[1]          #  Loop while at least 2 unique non-nil elements of t
                                  #  Now we know which elements can be safely printed
      r,=t-[p]                    #  Set r to first non-nil element of t
      p *r                        #  Print all such elements one at a time
    )while(t-[p])[0]              # Loop while at least one element of t is not nil
}

Ruby, 20 bytes, technically against the spirit of the challenge

Input is an array of specific kinds of Enumerator::Lazy objects constructed from Arrays or Ranges, but not created manually with Enumerator.new. Returns an Enumerator::Lazy that can be iterated through later to print results.

Finite arrays can be written simply as [...].lazy. (The function also accepts the arrays directly, but for the sake of the exercise everything is passed in uniformly so no class-checking is done.)

Infinite arrays take the form of (0..).lazy.map{...}. For example, even numbers can be represented as (0..).lazy.map{|i|i*2}, the infinite array [2,6,4,5,6,7,8,9,10,11,12,13,...] in the examples can be written as (0..).lazy.map{|i|i==1?6:i+2}, and something more complicated like the Fibonacci sequence can use some custom function, e.g. (0..).lazy.map{|i|SomeFunction(i)}

With this method, infinite arrays will have a size of infinity, and finite arrays will have a size equal to their length. (This is why I'm not allowing enumerators constructed with Enumerator.new, because they have a size of nil.)

->a{a.max_by &:size}

Attempt This Online!

\$\endgroup\$
4
  • \$\begingroup\$ This seems like a perfectly reasonable way to do infinite lists in ruby, not sure why someone downvoted \$\endgroup\$
    – noodle man
    Oct 4, 2023 at 19:57
  • 2
    \$\begingroup\$ @noodleman Admittedly it's not explicitly stated in the post, but the whole point of the challenge is that you can't know if a list is infinite or not. As a contrived example, consider the sequence of states of some turing machine. This is a valid potentially infinite list but there is no algorithm that could determine whether that list is finite or not. (I'm not the downvoter though) \$\endgroup\$
    – AnttiP
    Oct 4, 2023 at 20:25
  • \$\begingroup\$ @AntiiP I guess that makes sense, but OP should absolutely have made that more clear \$\endgroup\$
    – noodle man
    Oct 4, 2023 at 20:28
  • \$\begingroup\$ @AntiiP I added a version that should fit the spirit of the challenge, although it's twice as long. \$\endgroup\$
    – Value Ink
    Oct 4, 2023 at 21:34
2
\$\begingroup\$

Python, 146 bytes

Uses generators for IO, sadly much longer than the other Python solution

def f(L):
 while(Q:=[[[],l]for l in L]):
  while(Q:=[(k+[q],l)for k,l in Q if(q:=next(l,0))])*(len({str(k)for k,l in Q})>1):0
  yield from Q[0][0]

Attempt This Online!

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

R, 92 bytes

f=\(L,n,m=1,g=\(i)sapply(L,\(f)f(i)))`if`(sum(table(x<-g(n)[!!g(m)])|1)>1,f(L,n,m+1),max(x))

Attempt This Online!

Based on AnttiP's answer.

Takes input as list of functions and index (1-based) of the output sequence. Functions take index and return sequence value or 0 if it's out of bounds.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ -2 bytes using x[1] instead of max(x), I think... \$\endgroup\$ Oct 5, 2023 at 12:17
1
\$\begingroup\$

JavaScript (Node.js), 74 bytes

k=>f=(x,i=0)=>new Set(y=x.flatMap(c=>1/c(i)?c(k):[])).size>1?f(x,i+1):y[0]

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Your code doesn't work if there are multiple infinite lists (e.g. f([i=>i,i=>i])). \$\endgroup\$
    – AnttiP
    Oct 5, 2023 at 13:21
  • \$\begingroup\$ @AnttiP Should be fixed \$\endgroup\$
    – l4m2
    Oct 5, 2023 at 13:32
1
\$\begingroup\$

R, 88 76 bytes

Edit: -10 bytes by stealing some ideas from pajonk's R answer.

\(l,g=\(n)sapply(c(l,l),\(f)f(n)))\(i){while(sd(x<-g(i)[g(T)>0]))T=T+1;x[1]}

Attempt This Online!

Input as a list of functions that each return the i-th element of a (possibly finite, possibly infinite) list. Output is the function corresponding to the longest list.

This could be 2 bytes shorter if it's re-arranged to take an additional argument, i, and directly output the i-th element of the longest list indexed by the input functions (the I/O-format used by pajonk's R answer).


Original, 86-byte approach is here.

\$\endgroup\$

Your Answer

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

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