Двойной, XOR и сделай это снова

20

Определим функцию g как g (n) = n XOR (n * 2) для любого целого числа n> 0 .

Учитывая x> 0 , найдите наименьшее целое число y> 0 такое, что g k (y) = x для некоторого k> 0 .

пример

x = 549

549 = 483 XOR (483 * 2)     (as binary: 1000100101 = 111100011 XOR 1111000110)
483 = 161 XOR (161 * 2)     (as binary:  111100011 =  10100001 XOR  101000010)

Это означает, что g 2 (161) = 549 . Мы не можем идти дальше, так как нет такого n , что g (n) = 161 . Таким образом, ожидаемый результат для x = 549 равен y = 161 .

правила

  • Вы не должны поддерживать недействительные записи. Пара (y, k) гарантированно существует для входного значения x .
  • Это код-гольф , поэтому выигрывает самый короткий ответ в байтах!

Контрольные примеры

     3 -->     1
     5 -->     1
     6 -->     2
     9 -->     7
    10 -->     2
    23 -->    13
    85 -->     1
   549 -->   161
   960 -->    64
  1023 -->   341
  1155 -->   213
  1542 -->     2
  9999 -->  2819
 57308 --> 19124
 57311 -->   223
983055 -->     1
code-golf bitwise Arnauld
источник
3
Связанный OEIS: A048274, который является последовательностьюa(n) = g(n)
Джузеппе

Ответы:

5

Java 8, 68 57 53 52 байта

n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}

-5 байт благодаря @ OlivierGrégoire .

Попробуйте онлайн.

Объяснение:

n->{                 // Method with integer as both parameter and return-type
  for(int i=0;i<n;)  //  Loop `i` in the range (1,n)
    i-=(i*2^i)==n?   //   If `i*2` XOR-ed with `i` equals `n`
        n=i          //    Set `n` to `i`, and set `i` to 0 to reset the loop
       :             //   Else:
        -1;          //    Increase `i` by 1 to go to the next iteration
  return n;}         //  Return `n` after the entire loop
Кевин Круйссен
источник
1
n->{for(int i=0;i<n;)i-=(i*2^i)==n?n=i:-1;return n;}(52 байта). Извините ^^ '
Оливье Грегуар
@ OlivierGrégoire Еще умнее, спасибо!
Кевин Круйссен
for(int i=0;n>i-=i+i^i^n?-1:n=i;);?
Тит
@ Titus Боюсь, это не сработает в Java (хотя я использовал этот подход в своем итеративном ответе JavaScript ). В Java i+i^i^n?это не логическое значение, поэтому он даже не будет компилироваться. Кроме того, n>i-=...потребуется скобка ( n>(i-=...)), и n=iона не разрешена в предложении else в тернарном if, только в предложении if (это последнее, я не знаю почему, но, к сожалению, именно так и есть в Java) ).
Кевин Круйссен
1
@KevinCruijssen "и n=iне допускается в другом предложении троичного-if". Потому что Java будет разбирать его как (i-=(i*2^i)!=n?-1:n)=iнедопустимый.
Оливье Грегуар
3

JavaScript, 53 байта

f=x=>(i=0,y=(G=x=>x&&(i^=x&1)+2*G(x>>1))(x),i?x:f(y))

Gis g^-1, который установлен iв 0случае успеха, установлен iв 1случае сбоя.

ТТГ
источник
1
Это был подход , который я пытался использовать , хотя я придумал версию с 50-байтовой: f=n=>(g=n=>n<2?0/!n:n%2+2*g(n/2^n%2))(n)?f(g(n)):n. К сожалению, скучный подход на 12 байтов короче.
Нил
3

Pyth , 13 12 10 байт

Сохранено 1 байт благодаря @MrXcoder, и еще 2 байта после их предложения

fqQ.W<HQxy

Попробуйте онлайн

Объяснение:

fqQ.W<HQxyZZT   Implicit: Q=eval(input()), trailing ZZT inferred

f               Return the first T in [1,2,3...] where the following is truthy
   .W       T     Functional while - loop until condition is true, starting value T
     <HQ            Condition: continue while iteration value (H) less than input
        xyZZ        Body: xor iteration value (Z) with double (y) iteration value (Z)
 qQ               Is the result of the above equal to input?
Sok
источник
1
Вы можете сбросить трейлинг Tна 12 байтов.
Мистер Кскодер
3

R , 73 65 байт

f=function(x){for(i in 1:x)if(x==bitwXor(i,i*2)){i=f(i);break};i}

Попробуйте онлайн!

Большое спасибо Giuseppe (-8) из-за ваших настроек, таких простых, но очень эффективных

DS_UNI
источник
1
в отличие от вашего предыдущего ответа, поскольку эта функция рекурсивна, вам действительно нужно, f=так как функция должна быть связана для fправильной работы. Это, как говорится, хорошая работа, и взять +1 от меня!
Джузеппе
2
Вы также можете переиграть свою логику и получить ее до 65 байт
Джузеппе
2

JavaScript, 38 36 байт

f=(n,x=n)=>x?x^x+x^n?f(n,--x):f(x):n

Попробуйте онлайн - начинает выдавать ошибки переполнения где-то между 9999& 57308.

мохнатый
источник
2

Желе , 8 7 байт

Используйте ⁺¿для возврата последнего ненулевого элемента (спасибо Деннису за -1 байт)

^Ḥ)i$⁺¿

Попробуйте онлайн!

Грубая сила побеждает снова :(

user202729
источник
1
^Ḥ)i$⁺¿сохраняет байт.
Деннис
И это в 2 раза медленнее.
user202729
2

C (gcc) , 57 56 55 51 байт

  • Сэкономил байт благодаря функциюcatcat ; !=~  -.
  • Сохранено байт пять байтов благодаря Rogem ; используя троичное выражение и причуды gcc.
X(O,R){for(R=1;R;O=R?R:O)for(R=O;--R&&(R^2*R)-O;);}

Попробуйте онлайн!

Джонатан Фрех
источник
1
+1 заX(O,R)
JayCe
@ceilingcat Хорошее предложение, спасибо.
Джонатан Фрех
for(R=1;R;O=R?R:O)сохраняет байт.
R=O;в конце кажется ненужным, экономя еще 4 байта.
@Rogem Кажется, спасибо.
Джонатан Фрех
2

Z80Golf , 22 байта

00000000: 1600 1803 4216 007a b830 097a 82aa b828  ....B..z.0.z...(
00000010: f314 18f3 78c9                           ....x.

Порт Java-ответа @ KevinCruijssen

Пример с вводом 9-Попробуйте онлайн!

Пример с вводом 85-Попробуйте онлайн!

Монтаж:

;d=loop counter
;b=input and output
f:
	ld d,0
	jr loop
	begin:
	ld b,d
	ld d,0
	loop:
		ld a,d
		cp b
		jr nc,end	; if d==b end
		ld a,d
		add d		; mul by 2
		xor d
		cp b
		jr z,begin	; if (d*2)^d==b set b to d
		inc d
		jr loop
	end:
	ld a,b
	ret

Пример сборки для вызова функции и вывода результата:

ld b,9 ; input to the function, in this case 9
call f
add 30h ; ASCII char '0'
call 8000h ; putchar
halt
Logern
источник
Если aвместо счетчика сделать счетчик циклов d, вы можете заменить ld d,0инструкции в xor aобоих случаях, что сэкономит два байта.
Миша Лавров
1

JavaScript (Node.js), 48 45 38 байт

f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n

-7 байт благодаря @Neil, создающему рекурсивную версию моей итерационной версии ниже. Не работает для больших тестовых случаев.

Попробуйте онлайн.

Итеративная 45-байтовая версия, которая работает для всех тестовых случаев:

n=>{for(i=0;i<n;)i-=i*2^i^n?-1:n=i;return n;}

Порт моего Java ответа.
-3 байта благодаря @Arnauld .

Попробуйте онлайн.

Кевин Круйссен
источник
1
Вы можете сделать i-=i*2^i^n?-1:n=i(но, к сожалению, не на Java).
Арно
@Arnauld Понял, что логическое в Java что-то возможно только 1в JS. Благодарность!
Кевин Круйссен
1
38 байтов, записанных рекурсивно (не работает для больших входов):f=(n,i=0)=>i<n?i*2^i^n?f(n,i+1):f(i):n
Нил
1

Рубин , 39 байт

f=->x,y=x{y<1?x:x==y^y*2?f[y]:f[x,y-1]}

Попробуйте онлайн!

Как и ожидалось для рекурсивной версии, жалуется на «слишком большой уровень стека» в последних тестовых случаях.

Кирилл Л.
источник
1

Желе , 11 9 байт

BÄḂṛḄß$Ṫ?

Попробуйте онлайн!

Советы: используйте рекурсивную функцию вместо циклов.

Очень быстро, к сожалению, проигрывает подход грубой силы.

Обратите внимание, что:

  • Для й> 0 , Р (х)> х .
  • popcount (f (x)) является четным, где popcount (n) - количество битов, установленных в n .
  • Если n имеет четный подсчет, то существует такой x , что f (x) = n .
  • Пусть B (x) - двоичное представление x , а Ṗ (l) - список l с удаленным последним элементом. Тогда B (x) является накопленным XOR of (B (f (x))) .

Итак, мы неоднократно:

  • Вычислить его двоичное представление ( B)
  • затем возьмите накопленный XOR (используйте ^\или ÄḂ, они имеют тот же эффект).
  • Проверьте, не является ли ( ?) хвост (последний элемент) ( Ṫ) накопленного XOR ненулевым (нечетное количество)
    • Если это так, преобразовать двоичный список обратно в десятичный и рекурсивный.
    • Если нет, возвращает input ( ṛ).
user202729
источник
9 байт:B^\⁸Ḅß$Ṫ?
Дрянная монахиня
1

Forth (gforth) , 71 байт

: f 0 begin 2dup dup 2* xor = if nip 0 else 1+ then 2dup < until drop ;

Попробуйте онлайн!

объяснение

0                 \ add an index variable to the top of the stack
begin             \ start an indefinite loop
  2dup            \ duplicate the top two stack items (n and i)
  dup 2* xor =    \ calculate i xor 2i and check if equal to n
  if nip 0        \ if equal, drop n (making i the new n) and use 0 as the new i
  else 1+         \ otherwise just increment i by 1
  then            \ end the if-statement
  2dup <          \ duplicate the top two stack items and check if n < i
until             \ if previous statement is true, end the loop
drop              \ drop i, leaving n on top of the stack
reffu
источник
1

Perl 6 , 44 байта

{({first {($^a+^2*$a)==$_},^$_}...^!*).tail}

Попытайся

Expanded:

{  # bare block lambda with implicit parameter $_

  (
    # generate a sequence

    # no need to seed the sequence with $_, as the following block will
    # default to using the outer $_
    # $_, 

    { # parameter $_

      first
        {  # block with placeholder parameter $a

          ( $^a +^ 2 * $a ) # double (numeric) xor
          == $_             # is it equal to the previous value
        },

        ^$_  # Range up to and excluding the previous value ( 0..^$_ )
    }

    ...^  # keep doing that until: (and throw away last value)

    !*    # it doesn't return a trueish value

  ).tail  # return the last generated value
}
Брэд Гилберт b2gills
источник
1

PHP, 49 байт

Основано на ответах Кевина Круйссена. 

for($x=$argn;$x>$i-=$i*2^$i^$x?-1:$x=$i;);echo$x;

Запустите как трубу с -nrили попробуйте онлайн .

Titus
источник
1

F #, 92 байта

let rec o i=
 let r=Seq.tryFind(fun x->x^^^x*2=i){1..i-1}
 if r.IsNone then i else o r.Value

Попробуйте онлайн!

Рекурсивно проверяет числа от 1 до i-1. Если есть совпадение, проверьте меньшее для этого числа. Если совпадений нет, верните введенный номер.

Ciaran_McCarthy
источник
1

JavaScript (Node.js) , 40 байт

f=n=>g(n)%2?n:f(g(n)/2)
g=x=>x&&x^g(x/2)

Попробуйте онлайн!

Спасибо Шегги за -1 байт.

Порт моего желе ответа .

Наконец, есть язык, где этот подход короче ( упс ). (Я пробовал Python и Java , это не работает)

Может кто-нибудь объяснить, почему я могу использовать /2вместо >>1?

user202729
источник
1
x/2работает из-за арифметического занижения. Любое число IEEE 754 в конечном итоге будет оценено как 0, если его разделить на 2 достаточных раза. (А десятичная часть просто игнорируется, когда выполняется XOR, так что это не влияет на результат.)
Арно
40 байтов
лохматый
@ Шагги Удивлен, что это работает. Я знаю, что это работает для Python, Lua и т. Д., Но не для Javascript.
user202729
falseВернулся на последней итерации неявно приводится к 0путем побитового оператора XOR.
Мохнатый
@ Shaggy На самом деле, нетfalse , не участвует . JS &&ведет себя почти идентично Python / Lua and.
user202729
1

K (нгн / к) , 32 26 байт

{$[*|a:2!+\2\x;x;2/-1_a]}/

Попробуйте онлайн!

{ } это функция с аргументом x

/ применяет его до схождения

$[ ; ; ] если-то-иначе

2\xдвоичные цифры x(это характерно для ngn / k)

+\ частичные суммы

2! мод 2

a: назначить в a

*|last - перевернуть ( |) и получить first ( *)

если выше 1, xбудут возвращены

в противном случае:

-1_a отбросить последний элемент a

2/ расшифровать двоичный файл

СПП
источник
0

C, 62 байта

На основе Java Кевина Круйссена:

int n(int j){for(int i=0;i<j;)i-=(i*2^i)==j?j=i:-1;return j;}

Тестировать:

#include <stdio.h>
int n(int j);
#define p(i) printf("%6d --> %5d\n", i, n(i))
int main(void)
{
    p(3);
    p(5);
    p(6);
    p(9);
    p(10);
    p(23);
    p(85);
    p(549);
    p(960);
    p(1023);
    p(1155);
    p(1542);
    p(9999);
    p(57308);
    p(57311);
    p(983055);
}

При запуске тестовая программа выводит:

     3 -->     1
     5 -->     1
     6 -->     2
     9 -->     7
    10 -->     2
    23 -->    13
    85 -->     1
   549 -->   161
   960 -->    64
  1023 -->   341
  1155 -->   213
  1542 -->     2
  9999 -->  2819
 57308 --> 19124
 57311 -->   223
983055 -->     1

C 54 байта

Работает только с C89 или K & R C:

n(j){for(i=0;i<j;)i-=(i*2^i)==j?j=i:-1;return j;}

JustinCB
источник
int n(int j){for(int i=0;j>i-=i*2^i^j?-1:j=i;);return j;}Эти 57 байтов работают?
Тит
0

Wolfram Language (Mathematica) , 58 байт

Min[{#}//.x_:>Select[Range@#,MemberQ[x,#|BitXor[#,2#]]&]]&

Попробуйте онлайн!

Начинается со списка, содержащего только ввод. Итеративно заменяет список всеми целыми числами, которые уже есть в нем, или отображаются в нем с помощью операции double-and-xor. Затем //.говорит сделать это до достижения фиксированной точки. Ответ является наименьшим элементом результата.

Миша лавров
источник