15
\$\begingroup\$

Introduction (may be ignored)

Putting all positive numbers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive numbers. This is the second challenge in this series. The first challenge can be found here.

In this challenge, we use Gray codes to rearrage the natural numbers. A Gray code, or "reflected binary code" is a binary encoding in such a way that two successive values differ in only one bit. A practical application of this encoding is to use it in rotary encoders, hence my reference to "Turn My Way".

Rotary encoder for angle-measuring devices marked in 3-bit binary.

Note that this encoding leaves some degree of freedom. For example, following binary 1100, there are four possible following codes: 1101, 1110, 1000 and 0100. This is why I will define \$a(n)\$ as the smallest, not previously used value that differs only one character in binary encoding. This sequence corresponds with A163252.

Since this is a "pure sequence" challenge, the task is to output \$a(n)\$ for a given \$n\$ as input, where \$a(n)\$ is A163252.

Task

Given an integer input \$n\$, output \$a(n)\$ in integer format (not in binary format).

\$a(n)\$ is defined as the least positive integer not occurring earlier in the sequence such that \$a(n-1)\$ and \$a(n)\$ differ in only one bit when written in binary.

Note: 1-based indexing is assumed here; you may use 0-based indexing, so \$a(0) = 1; a(1) = 3\$, etc. Please mention this in your answer if you choose to use this.

Test cases

Input | Output
--------------
1     | 1
5     | 4
20    | 18
50    | 48
123   | 121
1234  | 1333
3000  | 3030
9999  | 9997

Rules

  • Input and output are integers (your program should at least support input and output in the range of 1 up to 32767)
  • Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour. In A163252, \$a(0)\$ is defined as 0. For this challenge, we will ignore this.
  • Default I/O rules apply.
  • Default loopholes are forbidden.
  • This is , so the shortest answers in bytes wins

Final note

See the following related (but not equal) PP&CG questions:

\$\endgroup\$

11 Answers 11

1
\$\begingroup\$

Stax, 19 17 bytes

êÑ{╚α8è╙mc┼σ▀»É▲ü

Run and debug it

It stops working at some point after the specified domain due to the hardcoded bit index iteration. (32767)

Unpacked, ungolfed, and commented, it looks like this.

z0,         push an empty array, literal zero, and the input, in that order
             - the zero represents the last calculated value in the sequence
             - the array contains all the previous ones
D           repeat the rest of the program n times (from input)
  +         append the last calculated value to the array
  17r       [0 .. 16] (these are the bit indices necessary to cover the input range)
  {|2nH|^m  calculate candidate values; previous value with each of these bits toggled 
  n-        remove all values previously calculated
  |m        keep the minimum candidate remaining

Run this one

\$\endgroup\$
  • \$\begingroup\$ You're 1 byte behind the shortest 05AB1E answer. Do you plan on optimizing this further? Otherwise I'll accept Kevin's answer... \$\endgroup\$ – agtoever Mar 24 at 6:47
  • 1
    \$\begingroup\$ If I have the opportunity I will work on it today, sometime in the next 14 hours. \$\endgroup\$ – recursive Mar 24 at 17:47
  • \$\begingroup\$ Allright. I'll keep it open for another day. Good luck! \$\endgroup\$ – agtoever Mar 24 at 18:42
  • \$\begingroup\$ @agtoever: Thanks. I'm done now. \$\endgroup\$ – recursive Mar 24 at 21:00
  • \$\begingroup\$ Well done! You win! Congratulations! \$\endgroup\$ – agtoever Mar 27 at 20:34
4
\$\begingroup\$

JavaScript (ES6), 65 bytes

1-indexed.

n=>{for(o=p=[k=1];o[k]|~-(i=p^k)&i?k++:k=o[p=k]=!!n--;);return p}

Try it online!

Commented

n => {                  // n = index of requested term
  for(                  // for loop:
    o =                 //   o = storage object for the terms of the sequence
    p =                 //   p = last term found in the sequence
      [k = 1];          //   k = current term
    o[k] |              //   if k was already encountered
    ~-(i = p ^ k) & i ? //   or (p XOR k) has more than 1 bit set:
      k++               //     increment k
    :                   //   else:
      k = o[p = k]      //     set o[k], set p to k
        = !!n--;        //     stop if n is equal to 0 or set k to 1; decrement n
  );                    // end of for()
  return p              // return p
}                       // end
\$\endgroup\$
  • \$\begingroup\$ On TIO, I get a stack overflow for n > ~1024. Any suggestions on how tot deal with that in Abu other environment? Rule: "your program should at least support input and output in theorie range of 1 up tot 32767" \$\endgroup\$ – agtoever Mar 19 at 20:46
  • 1
    \$\begingroup\$ @agtoever I've updated it to a non-recursive version. \$\endgroup\$ – Arnauld Mar 19 at 21:16
4
\$\begingroup\$

Jelly, 26 20 bytes

ṀBLŻ2*^1ị$ḟ⁸Ṃ;
0Ç⁸¡Ḣ

Try it online!

A full program that takes n as the single argument. Works for all test cases. Also note that, although not required, it handles n=0.

Explanation

Helper link: find next term and prepend

Ṁ              | maximum of list so far
 B             | convert to binary
  L            | number of binary digits
   Ż           | 0..above number
    2*         | 2 to the power of each of the above
      ^        | exclusive or with...
       1ị$     | ... the most recent term in the list so far
          ḟ⁸   | filter out anything used already
            Ṃ  | find the minimum
             ; | prepend to existing list

Main link

0              | start with zero
 Ç             | call the above link
  ⁸¡           | and repeat n times
    Ḣ          | take the last term added
\$\endgroup\$
3
\$\begingroup\$

Java (JDK), 142 138 124 123 132 130 98 bytes

n->{int s[]=new int[9*n],j,k=0;for(;n-->0;s[k=j]++)for(j=0;s[++j]>0|n.bitCount(j^k)>1;);return k;}

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm afraid imports has to be included in the byte-count. You can however golf the import java.util.*;+Set s=new HashSet(); to var s=new java.util.HashSet();. In addition, the rest can be golfed to: Integer i=0,j,k=0;for(;i++<n;s.add(k=j))for(j=0;s.contains(++j)|i.bitCount(j^k)>1;);return k;. Nice answer nonetheless, so +1 from me. :) \$\endgroup\$ – Kevin Cruijssen Mar 20 at 9:02
  • 1
    \$\begingroup\$ Saved 2 more bytes using Stack rather than HashSet. A lot slower but works! \$\endgroup\$ – Daniel Widdis Mar 20 at 10:00
  • 1
    \$\begingroup\$ Ah, of course, smart. And no matter how slow, if we can save a byte it's worth it for code-golf challenges. ;p I once had an answer that went from complexity \$O(n)\$ to \$O(n^n)\$ by saving a byte, haha xD \$\endgroup\$ – Kevin Cruijssen Mar 20 at 10:01
  • 2
    \$\begingroup\$ You can still golf it to 126 bytes with the second golf I suggested in my first comment. :) \$\endgroup\$ – Kevin Cruijssen Mar 20 at 10:27
  • 2
    \$\begingroup\$ 98 bytes. \$\endgroup\$ – Olivier Grégoire Mar 20 at 10:50
2
\$\begingroup\$

Python 2, 81 bytes

1-based indexing

l=[0];p=0
exec"n=0\nwhile(p^n)&(p^n)-1or n in l:n+=1\np=n;l+=p,;"*input()
print p

Try it online!


Python 2, 79 bytes

This takes a lot of time (9999 wasn't finished after running locally for 7 minutes)

l={0};p=0;n=input()
exec'p=min({p^2**k for k in range(n)}-l);l|={p};'*n
print p

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Maximum input 32767 isn't supported (the default recursion depth isn't system-dependent). \$\endgroup\$ – Erik the Outgolfer Mar 19 at 21:37
  • \$\begingroup\$ Even the given test case 9999 isn't supported. :) \$\endgroup\$ – Daniel Widdis Mar 20 at 8:32
  • \$\begingroup\$ @EriktheOutgolfer Changed it to an iterative approach, probably still doesn't finish in time on TIO, but runs locally just fine. \$\endgroup\$ – ovs Mar 20 at 10:23
  • \$\begingroup\$ @ovs Oh, timeouts alone don't matter. \$\endgroup\$ – Erik the Outgolfer Mar 20 at 12:06
  • \$\begingroup\$ Cool! I just tried it for n=9999 and it completed successfully after about an hour. +1. Yay! ;-) \$\endgroup\$ – agtoever Mar 29 at 10:17
1
\$\begingroup\$

Wolfram Language (Mathematica), 74 bytes

Last@Nest[#~Join~{Min[BitXor[Last@#,2^Range[0,20]]~Complement~#]}&,{0},#]&

Try it online!

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

APL (Dyalog Extended), 46 bytes

{⍵⌷2∘{(~⍺∊⍵)∧1=≢⍸≠⌿↑⌽∘⊤¨⍺,⊃⌽⍵:⍵,⍺⋄⍵∇⍨⍺+1}⍣⍵⊢1}

Try it online!

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

Charcoal, 65 bytes

≔⁰θFN«⊞υθ≔¹ηW¬‹θ⊗η≦⊗ηW∧›η¹∨¬&θη№υ⁻θη≧÷²ηW№υ⁻|θη&θη≦⊗η≔⁻|θη&θηθ»Iθ

Try it online! Link is to verbose version of code. Explanation:

≔⁰θ

Initialise the result to 0.

FN«

Loop n times.

⊞υθ

Save the previous result so that we don't use it again.

≔¹ηW¬‹θ⊗η≦⊗η

Find the highest bit in the previous result.

W∧›η¹∨¬&θη№υ⁻θη≧÷²η

While that bit is greater than 1, if the bit is set in the previous result, try subtracting that bit to see if the result is an unseen result. This ensures that the potential results are tried in ascending order of value.

W№υ⁻|θη&θη≦⊗η

Now try XORing that bit with the previous result, doubling the bit until an unseen result is found. This handles the cases when a bit needs to be set, again in ascending order of value, but also the case when the least significant bit needs to be toggled, which the previous loop doesn't bother to test (because it's golfier to test for that here). If the previous loop found an unseen result then this loop never runs; if it didn't then this loop will uselessly retest those results.

≔⁻|θη&θηθ

Update the result by actually XORing the bit with it.

»Iθ

Output the final result at the end of the loop.

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

05AB1E, 21 20 18 bytes

ÎFˆ∞.Δ¯θy^bSO¯yå_*

Pretty inefficient, so the larger the input, the longer it takes to get the result. Does work for input 0 as well, though.

Try it online or verify the first \$n\$ terms.

Explanation:

Î                # Push 0 and the input
 F               # Loop the input amount of times:
  ˆ              #  Pop the current number and add it to the global_array
  ∞.Δ            #  Inner loop starting at 1 to find the first number which is truthy for:
     ¯θy^        #   XOR the last number of the global_array with the loop-number `y`
         b       #   Convert it to binary
          SO     #   Sum it's binary digits
     ¯yå_        #   Check if the loop-number `y` is NOT in the global_array yet
            *    #   Multiply both (only if this is 1 (truthy), the inner loop will stop)
                 # (after the loops, output the top of the stack implicitly)
\$\endgroup\$
1
\$\begingroup\$

Haskell, 101 bytes

import Data.Bits
(u!n)0=n
(u!n)m|q<-minimum[x|r<-[0..62],x<-[xor(2^r)n],notElem x u]=(n:u)!q$m-1
[]!0

Try it online!

It seems a shame to incur an import just for xor, but I haven't found a good work-around yet. I also wonder if there's a better way to express the loop.

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

R, 90 bytes

function(n){A=1
while(sum(A|1)<n)A=c(min((x=bitwXor(A[1],2^(0:30)))[x>0&!x%in%A]),A)
A[1]}

Try it online!

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