4
\$\begingroup\$

Given infinite different integers, order them into a sequence \$a_1, a_2, a_3, ...\$ such that \$a_i>a_{i+1}\$ iff \$i\$ is even(or odd, as long as it's constant for all possible inputs and all \$i\$). In other word, make the sequence go alternately up and down (or down first, as long as it's constant).

Examples:

ℤ => 0,1,-1,2,-2,3,-3,...
ℕ => 0,2,1,4,3,6,5,8,7,...

ℤ => -1,1,-2,2,-3,3,... is invalid, as 0 never appears, claiming it appears infinitely far away doesn't help. Also it is worth to mention that these two examples covers all possible input types(No maximum or minimum / One border exists).


Default sequence IO applies. You can take input as an unordered(aka. you can't specify the order it has) sequence or a function checking if a value is in the set.

Shortest code in each language wins.

\$\endgroup\$
8
  • \$\begingroup\$ A question about terminology: perhaps this stems from different takes on the term "infinite", but doesn't "infinite different integers" imply that the output is always the same, just all integers in the interleaved pattern shown in the example? To ask another way, doesn't the question as given mean that the output is always the same? \$\endgroup\$
    – Etheryte
    Jun 8 at 13:44
  • 2
    \$\begingroup\$ @Etheryte Infinite different integers doesn't imply that all of the integers will be present. The set of even integers is also infinite, for example. (Or, just using the example in the challenge itself, the set of natural numbers \$\mathbb{N}\$) \$\endgroup\$
    – hyper-neutrino
    Jun 8 at 13:45
  • \$\begingroup\$ @hyper-neutrino Ah okay, thanks a lot for clarifying, yeah that makes sense. \$\endgroup\$
    – Etheryte
    Jun 8 at 13:46
  • 1
    \$\begingroup\$ Is it permitted to input an array and sort it into this pattern, and then claim that you can theoretically provide an infinitely large array and it will work after infinitely many steps? Asking based on the other (offline) solution. \$\endgroup\$
    – hyper-neutrino
    Jun 8 at 22:08
  • \$\begingroup\$ I also don’t understand how input is supposed to be taken \$\endgroup\$
    – Jonah
    Jun 8 at 23:05
4
\$\begingroup\$

Python 3.8 (pre-release), 140 bytes

k=lambda:[int(input())]
S=sorted
c,*p=S(k()+k()+k())
u=0
while 1:print(c);p=S(p+k());p.remove(c:=[x for x in p if x-p[u]if(x>c)^-u][u]);u=~u

Try it online!

-3 bytes thanks to l4m2
-9 bytes thanks to Wasif
-5 bytes thanks to l4m2
-9 bytes thanks to Don Thousand
-13 bytes thanks to Don Thousand
-11 bytes thanks to Don Thousand
-3 bytes thanks to l4m2
-2 bytes thanks to l4m2
-6 bytes thanks to ovs
-4 bytes thanks to Don Thousand
-12 bytes thanks to l4m2
-5 bytes thanks to ophact

\$\endgroup\$
16
  • \$\begingroup\$ This doesn't work. It doesn't guarantee that all inputs will eventually be outputted. \$\endgroup\$ Jun 8 at 15:53
  • \$\begingroup\$ @DonThousand Can you find a specific countercase? I am not actually convinced this problem is solvable yet but I need more cases to keep trying to fix my program until I can eventually prove or disprove it. \$\endgroup\$
    – hyper-neutrino
    Jun 8 at 15:56
  • \$\begingroup\$ @hyper-neutrino Will do in a bit. I am pretty convinced that this problem is not solvable as well. \$\endgroup\$ Jun 8 at 15:57
  • 1
    \$\begingroup\$ @hyper-neutrino 172 \$\endgroup\$ Jun 8 at 16:50
2
\$\begingroup\$

Jelly, 28 bytes

i»2$ịḟñ@ḟ
;ƓṢNÞƭçṄ}
Ɠ;Ɠ$⁺çṂƊ

Try it online!

A full program that reads an infinite unsorted series from STDIN and writes it in an order meeting the criteria in the question (up-down-up-down…).

Uses a modified version of @hyper-neutrino’s Python algorithm.

Explanation

Helper link 1

Takes a sorted list of 4 integers (x) as well as the most recent output (y) and calls helper link 2 with the same list after filtering out the most recent output as the left argument and the next output as the right argument.

i         | Index of y in x
 »2$      | Max of this and 2
    ịḟ    | Index into x after filtering out y (call this z)
      ñ@ḟ | Call helper link 2 with the filtered y on the left and z on the right

Helper link 2

Takes a list of 3 integers on the left (v) and the next output on the right (w). Appends a new input to the list, sorts it, prints the output and calls helper link 1 with the new sorted list and the output just printed

;Ɠ        | Append next input to list
  ṢNÞƭ    | Sort upwards on first call, downwards on next call and alternate for each subsequent call
      çṄ} | Call helper link 1 with the sorted list on the left and w on the right

Main link

Ɠ        | Input from STDIN
 ;Ɠ$     | Append next input
       Ɗ | Following as a monad:
    ⁺    | - Append next inlut
     çṂ  | - Call helper link 2 with all three inputs on left and min of first two on right
\$\endgroup\$
2
\$\begingroup\$

JavaScript (SpiderMonkey), 74 bytes

x=>y=>i=g=z=>print(x-(x=(z+=Math.random(i=!i)>.5&&y-(y=z))>x!=i?x:z)+z)||g

Try it online!

I cannot find out any discuss about function reusable requirements for infinite inputs... I hope this one is acceptable..

To my understanding, this should work with probability 1.

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

Japt, 21 17 bytes

Uses an even-sized moving window with a size of at least 4, moving it 2 slots on every iteration. This way we can't get stuck on intermediate values, while also not needing separate handling for upwards or downwards movement. Originally, I used a window 4 elements wide, but using A = 10 saves a byte due to automatic comma insertion.

Uses reducing to move through the array, mapping works just the same but is a few bytes longer.

Cut off 4 bytes thanks to Shaggy.

rÈiYÑXjYÑA Íó)c}N
r              }N // Reduce the input with the initial value of the inputs array.
     Xj  A        // Get A = 10 items from the input
       YÑ         // at iterator index * 2 so we're always at even steps.
           Íó     // Sort and interleave to get the zig-zag pattern.
 Èi               // Insert the result back into the array
   YÑ             // at the same index,
             )c   // and flatten out all nested arrays.

Try it here.

A short manual example with a window size of 4:

[..., -5, -4, -3, -2, -1,  0,  1,  2, ...]
      ~~~~~~~~~~~~~~

[..., -5, -3, -4, -2, -1,  0,  1,  2, ...]
              ~~~~~~~~~~~~~~

[..., -5, -3, -4, -1, -2,  0,  1,  2, ...]
                      ~~~~~~~~~~~~~~

[..., -5, -3, -4, -1, -2,  1,  0,  2, ...]
                               ~~~~~~~~~~
\$\endgroup\$
4
  • \$\begingroup\$ []cU is just N. \$\endgroup\$
    – Shaggy
    Jun 10 at 22:54
  • \$\begingroup\$ And c flattens the array completely when no argument is passed so no need for the 2. \$\endgroup\$
    – Shaggy
    Jun 10 at 23:00
  • \$\begingroup\$ @Shaggy Nice, thanks a lot! I struggled a lot to find a reasonably short way to work the reduce with an array, N didn't even cross my mind. \$\endgroup\$
    – Etheryte
    Jun 11 at 10:18
  • \$\begingroup\$ What was the version you had using map? We may be able to get that down shorter. \$\endgroup\$
    – Shaggy
    Jun 11 at 10:24

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.