Codegolf - Складные Цифры

Учитывая число, определите, является ли оно складным числом.

Складное число — это такое число, что если вы возьмете его в двоичном представлении и «сложите» его пополам, то есть возьмем результат умножения XNOR первой половины числа и второй половины с цифрами в обратном порядке, вы получите ноль.

Если число имеет нечетное количество цифр в двоичном формате, его средняя цифра должна быть 1 и игнорируется при сворачивании.

Поскольку это может показаться немного запутанным, я приведу несколько примеров:

178

Двоичное представление числа 178:

 
 
 
 
 
 
 
 
 
 
 
 [1, 2, 6, 10, 12, 22, 28, 38, 42, 52, 56, 78, 90, 108, 120, 142, 150, 170, 178, 204, 212, 232, 240, 286, 310, 346, 370, 412, 436, 472, 496, 542, 558, 598, 614, 666, 682, 722, 738, 796, 812, 852, 868, 920, 936, 976, 992, 1086, 1134, 1206, 1254, 1338, 1386, 1458, 1506, 1596, 1644, 1716, 1764, 1848, 1896, 1968, 2016, 2110, 2142, 2222, 2254, 2358, 2390, 2470, 2502, 2618, 2650, 2730, 2762, 2866, 2898, 2978, 3010, 3132, 3164, 3244, 3276, 3380, 3412, 3492, 3524, 3640, 3672, 3752, 3784, 3888, 3920, 4000, 4032, 4222, 4318, 4462, 4558]
 
 
 
 
 
 
 
 
 
 
 
 

Чтобы сложить это, мы сначала разделили его пополам.

Переворачиваем вторую половину

И мы выполняем XNOR две половины:

Это ноль, поэтому это складное число.

1644

Двоичное представление числа 1644:

Чтобы сложить это, мы сначала разделили его пополам.

Средний бит равен 1, поэтому мы его выбрасываем.

Переворачиваем вторую половину

И мы выполняем XNOR две половины:

Это ноль, поэтому это складное число.

4254

Двоичное представление числа 4254:

Чтобы сложить это, мы сначала разделили его пополам.

Средний бит равен 0, поэтому это не складывающееся число.

Задача

Ваша задача — принять положительное число и вернуть истинное значение, если число сворачивается, и ложное, если это не так. Это код-гольф, поэтому постарайтесь сократить отсчет байтов.

Тестовые случаи

Вот первые 99 складывающихся чисел:

#код-гольф #число #двоичный #побитовый #задача-решения

Желе, 9 байты

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 {X:2 0N#X where maxs X:0b vs x;

c:count each X;

$[(not first last X)or(=). c;

not any(=).(::;reverse)@'(neg min c)#'X;0b]

};
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Попробуйте онлайн! или проверить все тестовые случаи.

Как это работает

05AB1E, 13 12 байт

Код:

Использует CP-1252 кодировка. Попробуйте онлайн!

Объяснение:

Сначала мы преобразуем число в двоичное, используя i,m; f(n){ m=n;i=0; while(m)i*=2,i+=m&1,m/=2; return(n+i+1)&(n+i); } . 1644 становится 11001101100. Мы разделили это на две части с помощью 0 . For example, 11001101100 станет:

Если количество бит нечетное, первая часть получит дополнительный бит. Мы .+ $* +`^(1*)\1(1?)\b $1 $.2 +`^ (.)(.*) (?!\1).$ $2 ^( 1)?$ everse the last string and append a zero using 1 . Причина этого в том, чтобы давать правдивые результаты только тогда, когда средний бит является 1 (1 исключающее ИЛИ 0 = 1 и 0 исключающее ИЛИ 0 = 0). Если среднего бита нет, 05AB1E просто проигнорирует последний бит (добавленный ноль):

Последнее, что нам нужно сделать, это выполнить поэлементное исключающее ИЛИ и возьмем произведение результата. Если на один элемент больше, программа просто пропустит последний элемент ( (i,n=i.toString(2))=>/^(1*)2?\1$/.test(+n+ +n.split``.reverse().join``) ) For example:

Становится:

И продукт этого 1, что правда.

Java 7, 152 145 142 138 134 байта

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

Без полос прокрутки:

JavaScript (ES6), 61 57 52 байта

Рекурсивно вычисляет:

где c(s) = s == "" || # Base case, we compared all the digits from # both halves. s == "1" || # We compared everything but left a 1 in the middle (s[1] != s[end] && # First digit neq last digit (XNOR gives 0). c(s[2:end-1])) # AND the XNOR condition is satisfied for the # 2nd to 2nd to last digit substring. f(x) = c(bin(x)) # Instead of a string f takes an integer now. is the rank of the highest bit set in the input.

Если входные данные имеют нечетное количество бит, средний бит подвергается операции XOR с помощью операции XOR. неопределенный (значение, возвращаемое c(s)=s==""||s=="1"||(s[1]!=s[end]&&c(s[2:end-1])) f(x)=c(bin(x)) on an empty array), which lets it unchanged. So, a 1,2,6,10,12,22,28,38,42,52,56,78,90,108,120,142,150,170,178,204,212,232,240,286,310,346,370,412,436,472,496,542,558,598,614,666,682,722,738,796,812,852,868,920,936,976,992,1086,1134,1206,1254,1338,1386,1458,1506,1596,1644,1716,1764,1848,1896,1968,2016,2110,2142,2222,2254,2358,2390,2470,2502,2618,2650,2730,2762,2866,2898,2978,3010,3132,3164,3244,3276,3380,3412,3492,3524,3640,3672,3752,3784,3888,3920,4000,4032,4222,4318,4462,4558,4726,4822,4966,5062,5242,5338,5482,5578,5746,5842,5986,6082,6268,6364,6508,6604,6772,6868,7012,7108,7288,7384,7528,7624,7792,7888,8032,8128,8318,8382,8542,8606,8814,8878,9038,9102,9334,9398,9558,9622,9830,9894 средний бит очищает вывод и for($r=1,$a=str_split(decbin($argv[1]));$a;)$r*=array_pop($a)!=($a?array_shift($a):0);$r*=$a?$a[0]:1;echo$r; middle bit doesn't alter the result of the other operations -- which is consistent with the challenge definition of a folding number.

Питон 2, 57 байт

Выходы через код выхода: ошибка для Фальси и отсутствие ошибок для Истины.

Преобразует входные данные в двоичный. Проверяет, не равны ли первый и последний символы, сохраняет и повторяет это после удаления этих символов.

Сравнение t % Imolicitly take input. Duplicate % STACK: 1644, 1644 Bn % Number of digits of binary expansion % STACK: 1644, 11 2/k % Divide by 2 and round down % STACK: 1644, 5 W % 2 raised to that % STACK: 1644, 32 &\ % Divmod % STACK: 12, 51 h % Concatenate horizontally % STACK: [12 51] B % Binary expansion. Each numnber gives a row, left-padded with zeros if needed % STACK: [0 0 1 1 0 0; 1 1 0 0 1 1] Z} % Split into rows % STACK: [0 0 1 1 0 0], [1 1 0 0 1 1] P % Reverse % STACK: [0 0 1 1 0 0], [1 1 0 0 1 1] =~ % True for entries that have different elements % STACK: [1 1 1 1 1 1] % Implicitly display gives an error if the first and last character are unequal by trying to evaluate the unassigned variable named 1644 . Если они равны, цепочка неравенств вместо этого замыкается. Когда мы доберемся до среднего элемента tBn2/kW&\hBZ}P=~ , the ri2b e# convert input to binary _W%.+ e# flip and sum (if folding all bits are 1 except middle) :* e# product is 0 or power of 2 (2 if middle folds) 3& e# keep only 1 or 2, everything else becomes 0 (false) цикл завершается в особом случае как OK.

Я подозреваю, что чисто арифметический подход будет короче с такой рекурсией ri2b_W%.+:*3& to chomp off binary digits from the end flipped and reversed, and detect when 2 и 10 are equal up to a center -eq . Однако есть тонкости с ведущими нулями и центром.

Python 2, 94 79 72 67 байт

Сэкономлено 12 байт благодаря @xnor

Определяет безымянную функцию во второй строке.

Объяснение (с добавлением некоторых пробелов):

Попробуйте это здесь!

Хаскелл, 89 88 86 байт

Работает путем побитового суммирования битового представления с его обратным и получением произведения. Если это 1 или 2, число является складывающимся числом (1, если сворачиваются четные биты, 2, если есть нечетные биты и единица в середине).

Питон 2, 100 99 95 94 байта

Это кажется немного длинным, но я буду продолжать работать над этим :) Распечатывает 10 if the number can be folded, 1,1 в противном случае.

^{Проверьте это здесь!}

^{спасибо Wheat Wizard за сохранение 1 байта :)}

^{спасибо Роду за 5-байтовое сохранение! :)}

><>, 37+3 = 40 байт

Ожидается, что входные данные будут присутствовать в стеке при запуске программы, поэтому +3 байта для 0,1 flag.

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

Желе, 13 байты

ПопробуйОнлайн
Или условия соответствия до 4558

Как?

Перл, 46 байт

Включает +1 за 1

Запустить с номером на STDIN

$n :

Я считаю, что это вообще работает, это ошибка Perl. Внутренний 11 should not be getting match position updates once it is modified. In this program the match position actually moves beyond the end of 10

Брахилог, 16 байт

В онлайне это не очень работает...

Принимает входные данные через входную переменную и выводит результаты в случае успеха или неудачи. Это во многом зависит от 1,1 , which has been in the language since April 30, but we forgot to ask to have it pulled on TIO so for the time being this only works on a local installation of the language. Either way it's probably an overly naive approach.

Брахилог (по TIO), 19 байт

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

1 is functionally equivalent to exit (если вы больше нигде не используете переменную L), но она также на три байта длиннее.

Python 2, 76 71 69 байт

-5 байт благодаря @Dennis ( 0 is present in $n , поэтому замените $n with e )
-2 байта благодаря @xnor (используйте умножение, -n in place of $n[-1] )

идея

Рекурсивная функция при первом вызове 2 is a number so it evaluates as less than the empty string, with t , и функция вызывается снова, но с -g cast to a binary string; the tail is either an empty string (even bit-length) or the middle bit, which returns true for empty or a .length ; на пути вниз он проверяет внешние биты на неравенство (эквивалент XOR) и рекурсивно обращается к внутренним битам, for .

Питон 2, 63 байта

Принты param($n)for($n=[convert]::ToString($n,2);$n.Length-gt2){if($n[0]-ne$n[-1]){$n=$n[1..($n.Length-2)]}else{0;exit}}($n-join'+'|iex)-eq1-or$n-eq10 или 0 . Принимает двоичное представление 1 and repeatedly removed the first and last characters as long as they are unequal. Checks whether what remains is the empty string or a central $b%2 . Это делается путем преобразования -and to $o и проверяем, равен ли результат $n[$b-$_] , which also avoid an index error on the empty string.

PowerShell v2+, 143 байта

Два возможных подхода, оба с одинаковым количеством байтов.

Метод 1:

Принимает ввод -!($b%2) , if it's [convert] обычно для 0 (a special case for this algorithm), increment it. Set 1 вывод быть $o (i.e., assume truthy), then loop from 1 до середины введенного числа, которое было -eq ed to binary. Note the $n для учета двоичных чисел нечетной длины.

На каждой итерации мы сравниваем текущую цифру param($n)if($n-eq1){$n++}$o=1;0..(($b=($n=[convert]::ToString($n,2)).length-1)/2-!($b%2))|%{$o*=$n[$_]-ne$n[$b-$_]};$o*(+"$($n[$b/2])",1)[$b%2] with the digit the same length from the end '1' и умножьте логический результат на '1' (essentially performing an '' на всех). После завершения цикла нам необходимо потенциально учитывать среднюю двоичную цифру, то есть псевдотроичную цифру в конце (массив, индексированный через 1 ). That s или False is left on the pipeline, and output is implicit.

Метод 2:

Принимает входные данные и выполняет тот же процесс, чтобы s=bin(input())[2:] while s[0]!=s[-1]:s=s[1:-1]or'1' print'1'==s the number to binary. Then we're in a n[1:-1] цикл до тех пор, пока '1' of the binary string is n пожиратель if n<'' han n . Когда мы в курсе, если первый f=lambda n:f(bin(n)[2:])if n<''else n in'1'or(n[0]!=n[-1])*f(n[1:-1]) and last and цифры (...)* ot in'1' качество, отрежьте эти две цифры от in('','1') and re-store it into '1' . В противном случае вывод '' и z₂ . Как только мы выходим из цикла, у нас либо есть (массив lᵛ↖Lz , ḃḍ{↔|h1&b↔}ᵗlᵛ↖Lz≠ᵐ , The input ḃ 's binary representation ḍ split in half { }ᵗ with its second half ↔| either reversed, or h1 if it starts with 1 &b relieved of its first element ↔ and then reversed ≠ has no duplicate elements z ᵐ in any pair of elements zipped from the two halves ₂ which are equal in length. , z₂ , или ḃḍ{↔|h1&b↔}ᵗz₂≠ᵐ ), or the binary string for two $_ , или 3 $_ . So, we need to test those two possibilities. For the first, we #!/usr/bin/perl -p $_=($_=sprintf"%b",$_)<s%.%!/\G1$/^$&^chop%eg folding.pl together with folding.pl <<< 178 и оцените результат и проверьте, что это -p (this is true for arrays Bœs2U0¦z0^/€Ạ - Main link: n B - binary œs2 - split into 2 slices (odd length will have first longer than second) 0¦ - apply to index 0 (the right hand one) U - reverse z0 - zip together with filler 0 (thus central 1 or 0 will pair with 0) /€ - reduce with for each ^ - XOR Ạ - All truthy? , Bœs2U0¦z0^/€Ạ , and -v , но это <,2-@:%2:v!?: =2lrv?=1l<+={$r0? 0=n;> for arrays a=bin(input())[2:] b=len(a) print(a[b/2]>=`b%2`)*all(c!=d for c,d in zip(a[:b/2],a[:~b/2:-1])) and 0 or strings 1 or f n|n<2=[n]|1>0=mod n 2:f(div n 2) g n=elem(product$zipWith(+)(f n)$reverse$f n)[1,2] ). The other half of the F = lambda s: # We define a function, F, which takes one argument, the string s, which returns the following: s in'1' # Gives true if s is '' or s is '1', the first case is a base case and the second is for the middle bit case. or(s[0] != s[-1]) # Or the first and last are different * F(s[1:-1]) # And check if s, without the first and last element is also foldable. lambda n: F(bin(n)[:-2]) # The main function, which calls F with the argument in binary form. проверяет, является ли F=lambda s:s in'1'or(s[0]!=s[-1])*F(s[1:-1]) lambda n:F(bin(n)[2:]) is 1 обычно для r (i.e., input of n ). Это логическое значение остается в конвейере, и вывод неявный.

CJam, 13 байт

Попробуйте онлайн! или создать список складывания чисел до заданного числа.

МАТЛ, 16 байт

Истина — это массив со всеми единицами. Проверьте критерии истинности/ложности здесь.

Попробуйте онлайн! Или Проверьте первые 20 тестовых случаев.

Объяснение

Давайте использовать ввод _ as an example.

PHP, 101 байт

или с журналом

108 байт с массивом

Истинные значения <10000

Юлия, 66 байт

Мой первый гольф! работает так же, как решение Python той же длины,

небольшие различия из-за языка (хотя я придумал это сам...).

Объяснение:

Алгоритм грубой силы. Давайте посмотрим, как далеко можно зайти в гольф.

Улучшенные исправления ошибок настройки теста...

МАТЛ, 13 байт

Истина — это массив со всеми единицами. Проверьте критерии истинности/ложности здесь.

Попробуйте онлайн! Или проверить первые 20 тестовых случаев.

Объяснение

Использование ввода [1, 1, 1, 1, 1, 1] as an example:

JavaScript, 71 байт

Определяет анонимную функцию.

Этот способ, возможно, не самый короткий, но, насколько я знаю, он единственный. Он добавляет число в двоичном формате к самому себе в обратном порядке, рассматривая его как десятичное, а затем проверяя, является ли результат действительным, с помощью регулярного выражения.

Ретина, 92 байта

Подсчет байтов предполагает кодировку ISO 8859-1.

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

Преобразовать в унарный. Преобразуйте это в двоичный формат. Разрежьте число пополам и удалите середину. 0¸« if there is. Reverse the first half. Switch its ones and zeros. Match if both halves are equal.

Сетчатка, 71 70 60 байт

Вероятно, мне еще многое предстоит узнать о Retina (например, рекурсивное регулярное выражение?). Объяснение: Шаг 1 преобразует десятичное число в унарное. Шаг 2 преобразует унарный код в псевдодвоичный. Шаг 3 удаляет цифры с обоих концов, если они не совпадают. Четвертый шаг соответствует необязательному последнему центральному 1, если необходимо. Изменить: сохранен 1 байт благодаря @mbomb007. Сэкономлено 10 байт за счет улучшения моего преобразования унарного кода в двоичный.

Питон 2, 61 59 байт

Сохранение двух байтов для преобразования сдвигов в умножения

Возврат 2ä for a folding number and anything else for non-folding. Uses the bit-twiddling approach.

С, 65 63 байта

Два байта для преобразования сдвигов в умножения

Пробелы уже исключены из bytecount, возвращают 0 для числа свертывания и все остальное для несвертывания. Использует подход битового вращения.

к, 77 байт

в качестве пояснения, перевод на Bœs2µḢ^UȦ Main link. Argument: n B Binary; convert n to base 2. œs2 Evenly split 2; split the base 2 array into chunks of equal-ish length. For an odd amount of digits, the middle digit will form part of the first chunk. µ Begin a new, monadic chain. Argument: [A, B] (first and second half) Ḣ Head; remove and yield A. U Upend; reverse the digits in [B]. ^ Perform vectorized bitwise XOR of the results to both sides. If A is longer than B, the last digit will remain untouched. n is a folding number iff the result contains only 1's. Ȧ Octave-style all; yield 1 iff the result does not contain a 0.