New Order #2: Turn My Way
$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".
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 code-golf, so the shortest answers in bytes wins
Final note
See the following related (but not equal) PP&CG questions:
- Finding the next Gray code (input and output in binary)
- Generate the all Gray codes of length n
code-golf sequence
asked yesterday
agtoeveragtoever
1,158421
$endgroup$
add a comment |
$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".
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 code-golf, so the shortest answers in bytes wins
Final note
See the following related (but not equal) PP&CG questions:
- Finding the next Gray code (input and output in binary)
- Generate the all Gray codes of length n
code-golf sequence
asked yesterday
agtoeveragtoever
1,158421
$endgroup$
add a comment |
$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".
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 code-golf, so the shortest answers in bytes wins
Final note
See the following related (but not equal) PP&CG questions:
- Finding the next Gray code (input and output in binary)
- Generate the all Gray codes of length n
code-golf sequence
asked yesterday
agtoeveragtoever
1,158421
$endgroup$
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".
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 code-golf, so the shortest answers in bytes wins
Final note
See the following related (but not equal) PP&CG questions:
- Finding the next Gray code (input and output in binary)
- Generate the all Gray codes of length n
code-golf sequence
code-golf sequence
asked yesterday
agtoeveragtoever
1,158421
asked yesterday
agtoeveragtoever
1,158421
asked yesterday
agtoeveragtoever
1,158421
asked yesterday
agtoeveragtoever
1,158421
asked yesterday
agtoeveragtoever
1,158421
1,158421
add a comment |
add a comment |
10 Answers
10
active
oldest
votes
$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
answered yesterday
ArnauldArnauld
79.4k796330
$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
yesterday
1
$begingroup$
@agtoever I've updated it to a non-recursive version.
$endgroup$
– Arnauld
yesterday
add a comment |
$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
answered yesterday
Nick KennedyNick Kennedy
82137
$endgroup$
add a comment |
$begingroup$
Java (JDK), 142 138 124 123 132 130 98 bytes
- increased to account for import, saved a byte thanks to @kevin-cruijssen
- switched collection to int array thanks to @olivier-grégoire
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!
answered 23 hours ago
Daniel WiddisDaniel Widdis
1495
$endgroup$
1
$begingroup$
I'm afraid imports has to be included in the byte-count. You can however golf theimport java.util.*;+Set s=new HashSet();tovar 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
21 hours ago
1
$begingroup$
Saved 2 more bytes usingStackrather thanHashSet. A lot slower but works!
$endgroup$
– Daniel Widdis
20 hours ago
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
20 hours ago
2
$begingroup$
You can still golf it to 126 bytes with the second golf I suggested in my first comment. :)
$endgroup$
– Kevin Cruijssen
19 hours ago
2
$begingroup$
98 bytes.
$endgroup$
– Olivier Grégoire
19 hours ago
|
show 11 more comments
$begingroup$
Wolfram Language (Mathematica), 74 bytes
Last@Nest[#~Join~{Min[BitXor[Last@#,2^Range[0,20]]~Complement~#]}&,{0},#]&
Try it online!
answered yesterday
J42161217J42161217
13.3k21251
$endgroup$
add a comment |
$begingroup$
APL (Dyalog Extended), 46 bytes
{⍵⌷2∘{(~⍺∊⍵)∧1=≢⍸≠⌿↑⌽∘⊤¨⍺,⊃⌽⍵:⍵,⍺⋄⍵∇⍨⍺+1}⍣⍵⊢1}
Try it online!
answered yesterday
voidhawkvoidhawk
1,34125
$endgroup$
add a comment |
$begingroup$
Stax, 19 bytes
±↔Φd┌û╓°╡ñ|Q5┌¿Éúb≈
Run and debug it
It's very slow, but not nearly as slow as the 17 byte solution I was working on. I think there's still some golfing potential. I will add an explanation after I get rid of the bloat.
answered yesterday
recursiverecursive
5,5891322
$endgroup$
add a comment |
$begingroup$
Charcoal, 65 bytes
≔⁰θＦＮ«⊞υθ≔¹ηＷ¬‹θ⊗η≦⊗ηＷ∧›η¹∨¬＆θη№υ⁻θη≧÷²ηＷ№υ⁻｜θη＆θη≦⊗η≔⁻｜θη＆θηθ»Ｉθ
Try it online! Link is to verbose version of code. Explanation:
≔⁰θ
Initialise the result to 0.
ＦＮ«
Loop n times.
⊞υθ
Save the previous result so that we don't use it again.
≔¹ηＷ¬‹θ⊗η≦⊗η
Find the highest bit in the previous result.
Ｗ∧›η¹∨¬＆θη№υ⁻θη≧÷²η
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.
Ｗ№υ⁻｜θη＆θη≦⊗η
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.
»Ｉθ
Output the final result at the end of the loop.
answered yesterday
NeilNeil
81.9k745178
$endgroup$
add a comment |
$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)
answered 20 hours ago
Kevin CruijssenKevin Cruijssen
41k566211
$endgroup$
add a comment |
$begingroup$
Python 2, 81 bytes
1-based indexing
l=[0];p=0
exec"n=0nwhile(p^n)&(p^n)-1or n in l:n+=1np=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!
answered yesterday
ovsovs
19.3k21160
$endgroup$
1
$begingroup$
Maximum input 32767 isn't supported (the default recursion depth isn't system-dependent).
$endgroup$
– Erik the Outgolfer
yesterday
$begingroup$
Even the given test case 9999 isn't supported. :)
$endgroup$
– Daniel Widdis
21 hours ago
$begingroup$
@EriktheOutgolfer Changed it to an iterative approach, probably still doesn't finish in time on TIO, but runs locally just fine.
$endgroup$
– ovs
19 hours ago
$begingroup$
@ovs Oh, timeouts alone don't matter.
$endgroup$
– Erik the Outgolfer
17 hours ago
add a comment |
$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.
answered 8 hours ago
dfeuerdfeuer
895910
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f181825%2fnew-order-2-turn-my-way%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
10 Answers
10
active
oldest
votes
10 Answers
10
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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
answered yesterday
ArnauldArnauld
79.4k796330
$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
yesterday
1
$begingroup$
@agtoever I've updated it to a non-recursive version.
$endgroup$
– Arnauld
yesterday
add a comment |
$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
answered yesterday
ArnauldArnauld
79.4k796330
$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
yesterday
1
$begingroup$
@agtoever I've updated it to a non-recursive version.
$endgroup$
– Arnauld
yesterday
add a comment |
$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
answered yesterday
ArnauldArnauld
79.4k796330
$endgroup$
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
answered yesterday
ArnauldArnauld
79.4k796330
edited yesterday
answered yesterday
ArnauldArnauld
79.4k796330
answered yesterday
ArnauldArnauld
79.4k796330
answered yesterday
ArnauldArnauld
79.4k796330
79.4k796330
$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
yesterday
1
$begingroup$
@agtoever I've updated it to a non-recursive version.
$endgroup$
– Arnauld
yesterday
add a comment |
$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
yesterday
1
$begingroup$
@agtoever I've updated it to a non-recursive version.
$endgroup$
– Arnauld
yesterday
$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
yesterday
$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
yesterday
1
1
$begingroup$
@agtoever I've updated it to a non-recursive version.
$endgroup$
– Arnauld
yesterday
$begingroup$
@agtoever I've updated it to a non-recursive version.
$endgroup$
– Arnauld
yesterday
add a comment |
$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
answered yesterday
Nick KennedyNick Kennedy
82137
$endgroup$
add a comment |
$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
answered yesterday
Nick KennedyNick Kennedy
82137
$endgroup$
add a comment |
$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
answered yesterday
Nick KennedyNick Kennedy
82137
$endgroup$
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
answered yesterday
Nick KennedyNick Kennedy
82137
edited yesterday
answered yesterday
Nick KennedyNick Kennedy
82137
answered yesterday
Nick KennedyNick Kennedy
82137
answered yesterday
Nick KennedyNick Kennedy
82137
82137
add a comment |
add a comment |
$begingroup$
Java (JDK), 142 138 124 123 132 130 98 bytes
- increased to account for import, saved a byte thanks to @kevin-cruijssen
- switched collection to int array thanks to @olivier-grégoire
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!
answered 23 hours ago
Daniel WiddisDaniel Widdis
1495
$endgroup$
1
$begingroup$
I'm afraid imports has to be included in the byte-count. You can however golf theimport java.util.*;+Set s=new HashSet();tovar 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
21 hours ago
1
$begingroup$
Saved 2 more bytes usingStackrather thanHashSet. A lot slower but works!
$endgroup$
– Daniel Widdis
20 hours ago
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
20 hours ago
2
$begingroup$
You can still golf it to 126 bytes with the second golf I suggested in my first comment. :)
$endgroup$
– Kevin Cruijssen
19 hours ago
2
$begingroup$
98 bytes.
$endgroup$
– Olivier Grégoire
19 hours ago
|
show 11 more comments
$begingroup$
Java (JDK), 142 138 124 123 132 130 98 bytes
- increased to account for import, saved a byte thanks to @kevin-cruijssen
- switched collection to int array thanks to @olivier-grégoire
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!
answered 23 hours ago
Daniel WiddisDaniel Widdis
1495
$endgroup$
1
$begingroup$
I'm afraid imports has to be included in the byte-count. You can however golf theimport java.util.*;+Set s=new HashSet();tovar 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
21 hours ago
1
$begingroup$
Saved 2 more bytes usingStackrather thanHashSet. A lot slower but works!
$endgroup$
– Daniel Widdis
20 hours ago
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
20 hours ago
2
$begingroup$
You can still golf it to 126 bytes with the second golf I suggested in my first comment. :)
$endgroup$
– Kevin Cruijssen
19 hours ago
2
$begingroup$
98 bytes.
$endgroup$
– Olivier Grégoire
19 hours ago
|
show 11 more comments
$begingroup$
Java (JDK), 142 138 124 123 132 130 98 bytes
- increased to account for import, saved a byte thanks to @kevin-cruijssen
- switched collection to int array thanks to @olivier-grégoire
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!
answered 23 hours ago
Daniel WiddisDaniel Widdis
1495
$endgroup$
Java (JDK), 142 138 124 123 132 130 98 bytes
- increased to account for import, saved a byte thanks to @kevin-cruijssen
- switched collection to int array thanks to @olivier-grégoire
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!
answered 23 hours ago
Daniel WiddisDaniel Widdis
1495
edited 10 hours ago
answered 23 hours ago
Daniel WiddisDaniel Widdis
1495
answered 23 hours ago
Daniel WiddisDaniel Widdis
1495
answered 23 hours ago
Daniel WiddisDaniel Widdis
1495
1495
1
$begingroup$
I'm afraid imports has to be included in the byte-count. You can however golf theimport java.util.*;+Set s=new HashSet();tovar 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
21 hours ago
1
$begingroup$
Saved 2 more bytes usingStackrather thanHashSet. A lot slower but works!
$endgroup$
– Daniel Widdis
20 hours ago
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
20 hours ago
2
$begingroup$
You can still golf it to 126 bytes with the second golf I suggested in my first comment. :)
$endgroup$
– Kevin Cruijssen
19 hours ago
2
$begingroup$
98 bytes.
$endgroup$
– Olivier Grégoire
19 hours ago
|
show 11 more comments
1
$begingroup$
I'm afraid imports has to be included in the byte-count. You can however golf theimport java.util.*;+Set s=new HashSet();tovar 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
21 hours ago
1
$begingroup$
Saved 2 more bytes usingStackrather thanHashSet. A lot slower but works!
$endgroup$
– Daniel Widdis
20 hours ago
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
20 hours ago
2
$begingroup$
You can still golf it to 126 bytes with the second golf I suggested in my first comment. :)
$endgroup$
– Kevin Cruijssen
19 hours ago
2
$begingroup$
98 bytes.
$endgroup$
– Olivier Grégoire
19 hours ago
1
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
21 hours ago
$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
21 hours ago
1
1
$begingroup$
Saved 2 more bytes using
Stack rather than HashSet. A lot slower but works!$endgroup$
– Daniel Widdis
20 hours ago
$begingroup$
Saved 2 more bytes using
Stack rather than HashSet. A lot slower but works!$endgroup$
– Daniel Widdis
20 hours ago
1
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
20 hours ago
$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
20 hours ago
2
2
$begingroup$
You can still golf it to 126 bytes with the second golf I suggested in my first comment. :)
$endgroup$
– Kevin Cruijssen
19 hours ago
$begingroup$
You can still golf it to 126 bytes with the second golf I suggested in my first comment. :)
$endgroup$
– Kevin Cruijssen
19 hours ago
2
2
$begingroup$
98 bytes.
$endgroup$
– Olivier Grégoire
19 hours ago
$begingroup$
98 bytes.
$endgroup$
– Olivier Grégoire
19 hours ago
|
show 11 more comments
$begingroup$
Wolfram Language (Mathematica), 74 bytes
Last@Nest[#~Join~{Min[BitXor[Last@#,2^Range[0,20]]~Complement~#]}&,{0},#]&
Try it online!
answered yesterday
J42161217J42161217
13.3k21251
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 74 bytes
Last@Nest[#~Join~{Min[BitXor[Last@#,2^Range[0,20]]~Complement~#]}&,{0},#]&
Try it online!
answered yesterday
J42161217J42161217
13.3k21251
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 74 bytes
Last@Nest[#~Join~{Min[BitXor[Last@#,2^Range[0,20]]~Complement~#]}&,{0},#]&
Try it online!
answered yesterday
J42161217J42161217
13.3k21251
$endgroup$
Wolfram Language (Mathematica), 74 bytes
Last@Nest[#~Join~{Min[BitXor[Last@#,2^Range[0,20]]~Complement~#]}&,{0},#]&
Try it online!
answered yesterday
J42161217J42161217
13.3k21251
answered yesterday
J42161217J42161217
13.3k21251
answered yesterday
J42161217J42161217
13.3k21251
answered yesterday
J42161217J42161217
13.3k21251
13.3k21251
add a comment |
add a comment |
$begingroup$
APL (Dyalog Extended), 46 bytes
{⍵⌷2∘{(~⍺∊⍵)∧1=≢⍸≠⌿↑⌽∘⊤¨⍺,⊃⌽⍵:⍵,⍺⋄⍵∇⍨⍺+1}⍣⍵⊢1}
Try it online!
answered yesterday
voidhawkvoidhawk
1,34125
$endgroup$
add a comment |
$begingroup$
APL (Dyalog Extended), 46 bytes
{⍵⌷2∘{(~⍺∊⍵)∧1=≢⍸≠⌿↑⌽∘⊤¨⍺,⊃⌽⍵:⍵,⍺⋄⍵∇⍨⍺+1}⍣⍵⊢1}
Try it online!
answered yesterday
voidhawkvoidhawk
1,34125
$endgroup$
add a comment |
$begingroup$
APL (Dyalog Extended), 46 bytes
{⍵⌷2∘{(~⍺∊⍵)∧1=≢⍸≠⌿↑⌽∘⊤¨⍺,⊃⌽⍵:⍵,⍺⋄⍵∇⍨⍺+1}⍣⍵⊢1}
Try it online!
answered yesterday
voidhawkvoidhawk
1,34125
$endgroup$
APL (Dyalog Extended), 46 bytes
{⍵⌷2∘{(~⍺∊⍵)∧1=≢⍸≠⌿↑⌽∘⊤¨⍺,⊃⌽⍵:⍵,⍺⋄⍵∇⍨⍺+1}⍣⍵⊢1}
Try it online!
answered yesterday
voidhawkvoidhawk
1,34125
answered yesterday
voidhawkvoidhawk
1,34125
answered yesterday
voidhawkvoidhawk
1,34125
answered yesterday
voidhawkvoidhawk
1,34125
1,34125
add a comment |
add a comment |
$begingroup$
Stax, 19 bytes
±↔Φd┌û╓°╡ñ|Q5┌¿Éúb≈
Run and debug it
It's very slow, but not nearly as slow as the 17 byte solution I was working on. I think there's still some golfing potential. I will add an explanation after I get rid of the bloat.
answered yesterday
recursiverecursive
5,5891322
$endgroup$
add a comment |
$begingroup$
Stax, 19 bytes
±↔Φd┌û╓°╡ñ|Q5┌¿Éúb≈
Run and debug it
It's very slow, but not nearly as slow as the 17 byte solution I was working on. I think there's still some golfing potential. I will add an explanation after I get rid of the bloat.
answered yesterday
recursiverecursive
5,5891322
$endgroup$
add a comment |
$begingroup$
Stax, 19 bytes
±↔Φd┌û╓°╡ñ|Q5┌¿Éúb≈
Run and debug it
It's very slow, but not nearly as slow as the 17 byte solution I was working on. I think there's still some golfing potential. I will add an explanation after I get rid of the bloat.
answered yesterday
recursiverecursive
5,5891322
$endgroup$
Stax, 19 bytes
±↔Φd┌û╓°╡ñ|Q5┌¿Éúb≈
Run and debug it
It's very slow, but not nearly as slow as the 17 byte solution I was working on. I think there's still some golfing potential. I will add an explanation after I get rid of the bloat.
answered yesterday
recursiverecursive
5,5891322
edited yesterday
answered yesterday
recursiverecursive
5,5891322
answered yesterday
recursiverecursive
5,5891322
answered yesterday
recursiverecursive
5,5891322
5,5891322
add a comment |
add a comment |
$begingroup$
Charcoal, 65 bytes
≔⁰θＦＮ«⊞υθ≔¹ηＷ¬‹θ⊗η≦⊗ηＷ∧›η¹∨¬＆θη№υ⁻θη≧÷²ηＷ№υ⁻｜θη＆θη≦⊗η≔⁻｜θη＆θηθ»Ｉθ
Try it online! Link is to verbose version of code. Explanation:
≔⁰θ
Initialise the result to 0.
ＦＮ«
Loop n times.
⊞υθ
Save the previous result so that we don't use it again.
≔¹ηＷ¬‹θ⊗η≦⊗η
Find the highest bit in the previous result.
Ｗ∧›η¹∨¬＆θη№υ⁻θη≧÷²η
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.
Ｗ№υ⁻｜θη＆θη≦⊗η
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.
»Ｉθ
Output the final result at the end of the loop.
answered yesterday
NeilNeil
81.9k745178
$endgroup$
add a comment |
$begingroup$
Charcoal, 65 bytes
≔⁰θＦＮ«⊞υθ≔¹ηＷ¬‹θ⊗η≦⊗ηＷ∧›η¹∨¬＆θη№υ⁻θη≧÷²ηＷ№υ⁻｜θη＆θη≦⊗η≔⁻｜θη＆θηθ»Ｉθ
Try it online! Link is to verbose version of code. Explanation:
≔⁰θ
Initialise the result to 0.
ＦＮ«
Loop n times.
⊞υθ
Save the previous result so that we don't use it again.
≔¹ηＷ¬‹θ⊗η≦⊗η
Find the highest bit in the previous result.
Ｗ∧›η¹∨¬＆θη№υ⁻θη≧÷²η
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.
Ｗ№υ⁻｜θη＆θη≦⊗η
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.
»Ｉθ
Output the final result at the end of the loop.
answered yesterday
NeilNeil
81.9k745178
$endgroup$
add a comment |
$begingroup$
Charcoal, 65 bytes
≔⁰θＦＮ«⊞υθ≔¹ηＷ¬‹θ⊗η≦⊗ηＷ∧›η¹∨¬＆θη№υ⁻θη≧÷²ηＷ№υ⁻｜θη＆θη≦⊗η≔⁻｜θη＆θηθ»Ｉθ
Try it online! Link is to verbose version of code. Explanation:
≔⁰θ
Initialise the result to 0.
ＦＮ«
Loop n times.
⊞υθ
Save the previous result so that we don't use it again.
≔¹ηＷ¬‹θ⊗η≦⊗η
Find the highest bit in the previous result.
Ｗ∧›η¹∨¬＆θη№υ⁻θη≧÷²η
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.
Ｗ№υ⁻｜θη＆θη≦⊗η
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.
»Ｉθ
Output the final result at the end of the loop.
answered yesterday
NeilNeil
81.9k745178
$endgroup$
Charcoal, 65 bytes
≔⁰θＦＮ«⊞υθ≔¹ηＷ¬‹θ⊗η≦⊗ηＷ∧›η¹∨¬＆θη№υ⁻θη≧÷²ηＷ№υ⁻｜θη＆θη≦⊗η≔⁻｜θη＆θηθ»Ｉθ
Try it online! Link is to verbose version of code. Explanation:
≔⁰θ
Initialise the result to 0.
ＦＮ«
Loop n times.
⊞υθ
Save the previous result so that we don't use it again.
≔¹ηＷ¬‹θ⊗η≦⊗η
Find the highest bit in the previous result.
Ｗ∧›η¹∨¬＆θη№υ⁻θη≧÷²η
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.
Ｗ№υ⁻｜θη＆θη≦⊗η
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.
»Ｉθ
Output the final result at the end of the loop.
answered yesterday
NeilNeil
81.9k745178
answered yesterday
NeilNeil
81.9k745178
answered yesterday
NeilNeil
81.9k745178
answered yesterday
NeilNeil
81.9k745178
81.9k745178
add a comment |
add a comment |
$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)
answered 20 hours ago
Kevin CruijssenKevin Cruijssen
41k566211
$endgroup$
add a comment |
$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)
answered 20 hours ago
Kevin CruijssenKevin Cruijssen
41k566211
$endgroup$
add a comment |
$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)
answered 20 hours ago
Kevin CruijssenKevin Cruijssen
41k566211
$endgroup$
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)
answered 20 hours ago
Kevin CruijssenKevin Cruijssen
41k566211
edited 19 hours ago
answered 20 hours ago
Kevin CruijssenKevin Cruijssen
41k566211
answered 20 hours ago
Kevin CruijssenKevin Cruijssen
41k566211
answered 20 hours ago
Kevin CruijssenKevin Cruijssen
41k566211
41k566211
add a comment |
add a comment |
$begingroup$
Python 2, 81 bytes
1-based indexing
l=[0];p=0
exec"n=0nwhile(p^n)&(p^n)-1or n in l:n+=1np=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!
answered yesterday
ovsovs
19.3k21160
$endgroup$
1
$begingroup$
Maximum input 32767 isn't supported (the default recursion depth isn't system-dependent).
$endgroup$
– Erik the Outgolfer
yesterday
$begingroup$
Even the given test case 9999 isn't supported. :)
$endgroup$
– Daniel Widdis
21 hours ago
$begingroup$
@EriktheOutgolfer Changed it to an iterative approach, probably still doesn't finish in time on TIO, but runs locally just fine.
$endgroup$
– ovs
19 hours ago
$begingroup$
@ovs Oh, timeouts alone don't matter.
$endgroup$
– Erik the Outgolfer
17 hours ago
add a comment |
$begingroup$
Python 2, 81 bytes
1-based indexing
l=[0];p=0
exec"n=0nwhile(p^n)&(p^n)-1or n in l:n+=1np=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!
answered yesterday
ovsovs
19.3k21160
$endgroup$
1
$begingroup$
Maximum input 32767 isn't supported (the default recursion depth isn't system-dependent).
$endgroup$
– Erik the Outgolfer
yesterday
$begingroup$
Even the given test case 9999 isn't supported. :)
$endgroup$
– Daniel Widdis
21 hours ago
$begingroup$
@EriktheOutgolfer Changed it to an iterative approach, probably still doesn't finish in time on TIO, but runs locally just fine.
$endgroup$
– ovs
19 hours ago
$begingroup$
@ovs Oh, timeouts alone don't matter.
$endgroup$
– Erik the Outgolfer
17 hours ago
add a comment |
$begingroup$
Python 2, 81 bytes
1-based indexing
l=[0];p=0
exec"n=0nwhile(p^n)&(p^n)-1or n in l:n+=1np=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!
answered yesterday
ovsovs
19.3k21160
$endgroup$
Python 2, 81 bytes
1-based indexing
l=[0];p=0
exec"n=0nwhile(p^n)&(p^n)-1or n in l:n+=1np=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!
answered yesterday
ovsovs
19.3k21160
edited 19 hours ago
answered yesterday
ovsovs
19.3k21160
answered yesterday
ovsovs
19.3k21160
answered yesterday
ovsovs
19.3k21160
19.3k21160
1
$begingroup$
Maximum input 32767 isn't supported (the default recursion depth isn't system-dependent).
$endgroup$
– Erik the Outgolfer
yesterday
$begingroup$
Even the given test case 9999 isn't supported. :)
$endgroup$
– Daniel Widdis
21 hours ago
$begingroup$
@EriktheOutgolfer Changed it to an iterative approach, probably still doesn't finish in time on TIO, but runs locally just fine.
$endgroup$
– ovs
19 hours ago
$begingroup$
@ovs Oh, timeouts alone don't matter.
$endgroup$
– Erik the Outgolfer
17 hours ago
add a comment |
1
$begingroup$
Maximum input 32767 isn't supported (the default recursion depth isn't system-dependent).
$endgroup$
– Erik the Outgolfer
yesterday
$begingroup$
Even the given test case 9999 isn't supported. :)
$endgroup$
– Daniel Widdis
21 hours ago
$begingroup$
@EriktheOutgolfer Changed it to an iterative approach, probably still doesn't finish in time on TIO, but runs locally just fine.
$endgroup$
– ovs
19 hours ago
$begingroup$
@ovs Oh, timeouts alone don't matter.
$endgroup$
– Erik the Outgolfer
17 hours ago
1
1
$begingroup$
Maximum input 32767 isn't supported (the default recursion depth isn't system-dependent).
$endgroup$
– Erik the Outgolfer
yesterday
$begingroup$
Maximum input 32767 isn't supported (the default recursion depth isn't system-dependent).
$endgroup$
– Erik the Outgolfer
yesterday
$begingroup$
Even the given test case 9999 isn't supported. :)
$endgroup$
– Daniel Widdis
21 hours ago
$begingroup$
Even the given test case 9999 isn't supported. :)
$endgroup$
– Daniel Widdis
21 hours ago
$begingroup$
@EriktheOutgolfer Changed it to an iterative approach, probably still doesn't finish in time on TIO, but runs locally just fine.
$endgroup$
– ovs
19 hours ago
$begingroup$
@EriktheOutgolfer Changed it to an iterative approach, probably still doesn't finish in time on TIO, but runs locally just fine.
$endgroup$
– ovs
19 hours ago
$begingroup$
@ovs Oh, timeouts alone don't matter.
$endgroup$
– Erik the Outgolfer
17 hours ago
$begingroup$
@ovs Oh, timeouts alone don't matter.
$endgroup$
– Erik the Outgolfer
17 hours ago
add a comment |
$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.
answered 8 hours ago
dfeuerdfeuer
895910
$endgroup$
add a comment |
$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.
answered 8 hours ago
dfeuerdfeuer
895910
$endgroup$
add a comment |
$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.
answered 8 hours ago
dfeuerdfeuer
895910
$endgroup$
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.
answered 8 hours ago
dfeuerdfeuer
895910
edited 8 hours ago
answered 8 hours ago
dfeuerdfeuer
895910
answered 8 hours ago
dfeuerdfeuer
895910
answered 8 hours ago
dfeuerdfeuer
895910
895910
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f181825%2fnew-order-2-turn-my-way%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
