Задача:

С учетом целочисленного ввода выясните, является ли это число Циклопом.

Вы можете спросить, что такое число Циклопа? Ну, это число, двоичное представление которого имеет только один 0в центре!

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

Input | Output | Binary  | Explanation
--------------------------------------
0     | truthy | 0       | only one zero at "center"
1     | falsy  | 1       | contains no zeroes
5     | truthy | 101     | only one zero at center
9     | falsy  | 1001    | contains two zeroes (even though both are at the center)
10    | falsy  | 1010    | contains two zeroes
27    | truthy | 11011   | only one zero at center
85    | falsy  | 1010101 | contains three zeroes
101   | falsy  | 1100101 | contains three zeroes
111   | falsy  | 1101111 | only one zero, not at center
119   | truthy | 1110111 | only one zero at center

Входные данные:

• Целое число или эквивалентные типы. ( int, long, decimalИ т.д.)

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

Выход:

• Истина или ложь.

• Выходные данные «Правда / ложь» должны соответствовать спецификациям используемого языка для «Правда / ложь». (например, C имеет значение 0false, ненулевое значение true)

Правила соревнований:

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

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

Основные правила:

• Это код-гольф , поэтому самые короткие ответы в байтах выигрывают!

• Лазейки по умолчанию запрещены.

• К вашему ответу применяются стандартные правила с правилами ввода / вывода по умолчанию .

Это моя первая задача по Программированию Пазлов и Code Golf , поэтому любые отзывы о том, как я должен совершенствоваться, будут высоко оценены!

Japt, 8 байт

1¥¢q0 äè

Запустите его онлайн

Объяснение:

1¥¢q0 äè   
                                                              119
  ¢          // Convert the input into a binary string        "1110111"
   q0        // Split the string on "0"                       ["111","111"]
      ä      // Reduce each item by:                            a     b
       è     //   Seeing how many times a is found in b       [1]
 1¥          // == 1; See if the result equals 1              True                                         

Идея состоит в том, чтобы разбить двоичную строку в 0, что даст два элемента, если есть только один 0. Затем мы видим, соответствует ли первый элемент второму, чтобы убедиться, что он является палиндромным. Если двоичная строка содержит несколько 0s, то при редукции будет возвращен массив из нескольких элементов, и это ==1условие не будет выполнено . Если двоичная строка содержит ее 0, но не является палиндромной, äèона вернется, 0поскольку bсодержит 0совпадения a.

Python 2 , 30 байт

lambda n:(2*n^2*n+3)**2==8*n+9

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

Обратите внимание, что 2*n^2*n+3это побитовый xor 2*nи 2*n+3, потому что это приоритет оператора Python.

Машинный код x86, 17 байт

8D 47 01 31 F8 89 C2 F7 D2 0F AF C2 8D 44 78 02 C3

Вышеуказанные байты определяют функцию, которая принимает 32-разрядное целочисленное входное значение (в EDIрегистре для этого примера, следуя общему соглашению о вызовах System V, но вы можете фактически выбрать практически любой входной регистр, который вы хотите, не влияя на размер получаемого результата). код) и возвращает результат (в EAXрегистре), указывающий, является ли входное значение числом Циклопа.

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

Логика принятия решения заимствована из ответа Нейла : поскольку число Циклопа имеет вид , мы можем использовать серию операций переворота битов для проверки вход.$n = (2 ^ k + 1) (2 ^ { k - 1 } - 1)$

Примечание: возвращаемое значение - истина / ложь, но семантика обратная, так что функция возвращает ложь для числа Циклопа. Я утверждаю, что это законно, потому что машинный код не имеет «спецификации для правдивости / ложности», что является требованием в вопросе. (См. Ниже альтернативную версию, если вы думаете, что это обман.)

В мнемонике языка ассемблера это:

; EDI = input value
; EAX = output value (0 == Cyclops number)
8D 47 01           lea    eax, [edi + 1]          ; \ EAX = ((EDI + 1) ^ EDI)
31 F8              xor    eax, edi                ; /
89 C2              mov    edx, eax                ; \ EDX = ~EAX
F7 D2              not    edx                     ; /
0F AF C2           imul   eax, edx                ; EAX *= EDX
8D 44 78 02        lea    eax, [eax + edi*2 + 2]  ; EAX  = (EAX + (EDI * 2) + 2)
C3                 ret                            ; return, with EAX == 0 for Cyclops number

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

Как и было обещано, если вы думаете, что обманывать инвертирование семантики истины / фальши даже в машинном коде, где нет реальных стандартов или соглашений, добавьте еще три байта, всего 21 байт :

; EDI = input value
; AL  = output value (1 == Cyclops number)
8D 47 01           lea    eax, [edi + 1]          ; \ EAX = ((EDI + 1) ^ EDI)
31 F8              xor    eax, edi                ; /
89 C2              mov    edx, eax                ; \ EDX = ~EAX
F7 D2              not    edx                     ; /
0F AF C2           imul   eax, edx                ; EAX *= EDX
8D 44 78 01        lea    eax, [eax + edi*2 + 1]  ; EAX  = (EAX + (EDI * 2) + 1)
40                 inc    eax                     ; EAX += 1
0F 94 C0           setz   al                      ; AL = ((EAX == 0) ? 1 : 0)
C3                 ret                            ; return, with AL == 1 for Cyclops number

Первая половина этого кода такая же, как и в оригинале (через imulинструкцию). Это leaпочти то же самое, но вместо добавления константы 2 добавляется только константа 1. Это потому, что следующая incинструкция увеличивает значение в EAXрегистре на 1, чтобы установить флаги. Если установлен флаг «ноль», setzинструкция будет установлена ALна 1; в противном случае ALбудет установлено значение 0. Это стандартный способ, которым компилятор C будет генерировать машинный код для возврата a bool.

Изменение константы, добавленной в leaинструкцию, очевидно, не меняет размер кода, и incинструкция очень мала (всего 1 байт), но setzинструкция занимает довольно много 3 байта. К сожалению, я не могу придумать более короткий способ написания этого.

Регулярное выражение (ECMAScript), 60 58 57 60 58 байт

Вход в унарном виде, как длина строки s.$n$x

ПРЕДУПРЕЖДЕНИЕ О СПОЙЛЕРЕ : для квадратного корня это регулярное выражение использует вариант обобщенного алгоритма умножения, который неочевиден и может быть полезной головоломкой для самостоятельной разработки. Для получения дополнительной информации см. Объяснение этой формы алгоритма в « Найти число Рокко» .

-2 байта, позволяя возвращаться в поиске$z$ -1 байта благодаря Grimy , ища от наименьшего к наибольшему, а не наоборот +3 байта, чтобы обработать ноль -2 байта, перемещая захват квадратного корня за пределы предвиденияz
$z$

Это работает путем нахождения , идеальной квадратной степени 2, для которой . Это может удовлетворить только наибольшая совершенная квадратичная степень 2, не превышающая , но благодаря оптимизации для гольфа регулярное выражение пробует их все, начиная с наименьшего. Поскольку каждый соответствует числу циклопов, только самый большой из них может привести к совпадению.$z$$n=2(n-z)+\sqrt{z}+1$$n$

^(x*)(?!(x(xx)+)\2*$)(x(x*))(?=(?=(\4*)\5+$)\4*$\6)x\1$|^$

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

^                 # N = tail
(x*)              # tail = Z, with the smallest value that satisfies the following
                  # assertions (which is no different from the largest value that
                  # would satisfy them, since no more than one value can do so);
                  # \1 = N - Z

(?!(x(xx)+)\2*$)  # Assert Z is a power of 2

# Assert Z is a perfect square, and take its square root
(x(x*))           # \4 = square root of Z; \5 = \4 - 1; tail = N - \1 - \4
(?=(\4*)\5+$)     # iff \4*\4 == Z, then the first match here must result in \6==0
(?=\4*$\6)        # test for divisibility by \4 and for \6==0 simultaneously

# Assert that N == \1*2 + \4 + 1. If this fails, then due to a golf optimization,
# the regex engine will backtrack into the capturing of \4, and try all smaller
# values to see if they are the square root of Z; all of these smaller values will
# fail, because the \4*\4==Z multiplication test only matches for one unique value
# of \4.
x\1$

|^$               # Match N==0, because the above algorithm does not

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

p=>~p==(p^=p+1)*~p/2

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

Может быть, это правильно, может быть.

Спасибо, Грими, 1 байт сохранен.

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

f=(p,q)=>p&1?f(p/2,q+q|2):!(p^q)

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

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

p=>/^(1*)0\1$/.test(p.toString(2))

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

Perl 6 , 23 байта

{.base(2)~~/^(1*)0$0$/}

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

Решение на основе регулярных выражений

Japt , 25 19 10 9 байт

¢êÅ©1¶¢èT

Спасибо @Shaggy за -1 байт

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

Mathematica (язык Wolfram), 32 31 байт

1 байт сохранен благодаря J42161217!

OddQ@Log2[#+Floor@Sqrt[#/2]+2]&

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

Чистая функция, принимающая целое число в качестве входных данных и возвращающая Trueили False. Основываясь на том факте (забавно доказать!), Что число nявляется циклопом тогда и только тогда, когда nплюс квадратный корень из n/2плюс 2округляет до нечетной степени 2. (Можно заменить Floorодним Ceilingили Roundдо тех пор, пока один также заменяется +2на +1.) Возвращает Trueна входе 0.

Рубин , 24 байта

->x{x+x+2==(1+x^=x+1)*x}

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

Japt, 8 байт

¢ðT ¥¢Êz

Спасибо Луису Фелипе де Хесусу Муньосу за исправление моего представления!

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

Старое решение на основе регулярных выражений, 15 байтов

¤f/^(1*)0\1$/ l

Возвращает 1 для истины, 0 для ложных.

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

Желе ,  8  7 байт

-1 благодаря Эрику Outgolfer (используйте встроенный isPalindrome ŒḂ, вместо ⁼Ṛ$)

B¬ŒḂ⁼SƊ

Монадическая ссылка, принимающая целое число, которое приводит к 1(truey) или 0(falsey).

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

Как?

B¬ŒḂ⁼SƊ - Link: integer             e.g. 1    9          13         119
B       - to base 2                      [1]  [1,0,0,1]  [1,1,0,1]  [1,1,1,0,1,1,1]
 ¬      - logical NOT (vectorises)       [0]  [0,1,1,0]  [0,0,1,0]  [0,0,0,1,0,0,0]
      Ɗ - last three links as a monad:
  ŒḂ    -   is a palindrome?             1    1          0          1
     S  -   sum                          0    2          1          1
    ⁼   -   equal?                       0    0          0          1

Haskell , 32 байта

f n=or[2*4^k-2^k-1==n|k<-[0..n]]

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

Регулярное выражение (ECMAScript), 53 47 байт

-6 байт благодаря как Deadcode, так и Grimy

^((?=(x*?)(\2((x+)x(?=\5$))+x$))(?!\2{6})\3x)*$

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

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

ḃD↔Dḍ×ᵐ≠

Это предикат, который успешно выполняется, если его ввод представляет собой число Циклопа, и завершается неудачей, если его ввод не является числом Циклопа. Успех / неудача - самая фундаментальная концепция правды / фальши в брахилоге.

Попробуйте онлайн! Или найдите все достоверные результаты до 10000 .

объяснение

          Input is an integer
ḃ         Get its binary representation, a list of 1's and 0's
 D        Call that list D
  ↔       When reversed...
   D      It's the same value D
    ḍ     Dichotomize: break the list into two halves
          One of these halves should be all 1's; the other should contain the 0
     ×ᵐ   Get the product of each half
       ≠  Verify that the two products are not equal

Это успешно, только если дан номер Циклопа, потому что:

• Если двоичное представление не является палиндромом, D↔Dпроизойдет сбой; в дальнейшем мы можем предположить, что это палиндром.
• Если имеется более одного нуля, обе половины будут содержать хотя бы один ноль. Таким образом, продукты будут как ноль, так и не ×ᵐ≠получится.
• Если нет нуля, обе половины будут содержать только единицы. Таким образом, продукты будут как один, так и не ×ᵐ≠получится.
• Это оставляет случай, когда есть ровно один ноль; поскольку мы уже знаем, что у нас есть палиндром, это должно быть центральным. Он появится в одной половине, в результате чего произведение этой половины будет равно нулю; вторая половина будет содержать все, поэтому его продукт будет один. Тогда мы имеем 1 ≠ 0, ×ᵐ≠успешно, и весь предикат успешно.

Рубин , 27 24 байта

Преобразовать в двоичный файл и проверить с помощью регулярного выражения. Возвращает, 0если true, nilесли false.

-3 байта благодаря ГБ .

->n{"%b"%n=~/^(1*)0\1$/}

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

Еще на два байта есть прямой порт решения Python:

->n{(2*n^2*n+3)**2==8*n+9}

05AB1E , 8 (или 9) байтов

bD0¢sÂQ*

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

Возвращает 1если правдиво; 0или любое положительное целое число, кроме 1как фальси. В 05AB1E только 1правдиво, а все остальное ложно, но я не уверен, является ли это допустимым выводом, или если вывод должен быть двумя непротиворечивыми и уникальными значениями. Если второй, трейлинг Θможет быть добавлен, так что все выходы, кроме 1становятся 0:

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

Объяснение:

b     # Convert the (implicit) input-integer to a binary-string
 D    # Duplicate it
  0¢  # Count the amount of 0s
 s    # Swap to get the binary again
  ÂQ  # Check if it's a palindrome
 *    # Multiply both (and output implicitly)

  Θ   # Optionally: check if this is truthy (==1),
      # resulting in truthy (1) or falsey (0)

Арифметический подход будет 10 байтов:

LoD<s·>*Iå

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

Объяснение:

$a(n) = (2^n-1)*(2*2^n+1)$

L        # Create a list in the range [1, (implicit) input-integer]
 o       # For each integer in the list, take 2 to the power this integer
  D<     # Create a copy, and decrease each value by 1
  s·     # Get the copied list again, and double each value
    >    # Then increase each value by 1
  *      # Multiply the numbers at the same indices in both lists
     Iå  # Check if the input-integer is in this list
         # (and output the result implicitly)

Excel, 97 63 байта

=A1=2*4^(ROUND(LOG(A1,4),0))-2^(ROUND(LOG(A1,4),0))-1

Вычисляет 2 числа:

Дважды ближайшая сила 4
>Num|Binary|2*Power4|Binary
> 1| 1| 2* 1= 2| 10
> 2| 10| 2* 4= 8| 1000
> 4| 100| 2* 4= 8| 1000
> 20| 10100| 2*16=32|100000

1 плюс квадратный корень из ближайшей степени 4
>Num|Binary|1+√Power4|Binary
> 1| 1|1+ √1= 2| 10
> 2| 10|1+ √4= 3| 11
> 4| 100|1+ √4= 3| 11
> 20| 10100|1+ √16= 5| 101

Затем вычтите второе число из первого:

>Num|Binary|2*Power4|Binary|1+√Power4|Binary|a-b|Binary
> 1| 1| 2* 1= 2| 10|1+ √1= 2| 10| 0| 0
> 2| 10| 2* 4= 8| 1000|1+ √4= 3| 11| 5| 101
> 4| 100| 2* 4= 8| 1000|1+ √4= 3| 11| 5| 101
> 20| 10100| 2*16=32|100000|1+ √16= 5| 101| 27| 11011

И сравните этот результат с исходным числом

Старый метод

=DEC2BIN(A1)=REPLACE(REPT("1",1+2*INT(IFERROR(LOG(A1,2),0)/2)),1+IFERROR(LOG(A1,2),0)/2,1,"0")

Начните с Log-base-2 из A1 и округлите его до ближайшего четного числа, затем добавьте 1.

Затем создайте строку с таким количеством "1"s и замените средний символ на a, "0"чтобы создать число Циклопа с двоичной длиной, которая всегда нечетна, и равна или меньше 1 двоичной длины A1

Затем сравните его с двоичным представлением A1

R , 37 33 байта

(x=scan())%in%(2*4^(n=0:x)-2^n-1)

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

В R нет встроенной функции для преобразования в двоичную форму, поэтому я просто использовал одну из формул из OEIS для вычисления списка терминов из последовательности.

n<-0:xгенерирует щедрый список начальных значений. 2*4^(n<-0:x^2)-2^n-1)это формула из OEIS, а затем он проверяет, появляется ли вход в этой последовательности, используя %in%.

-2 байта, не обрабатывая отрицательные входные данные. -2 байта, помня, я могу изменить <-на =.

C (gcc), 26 байтов

f(n){n=~n==(n^=-~n)*~n/2;}

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

Порт Нейла ответ . Полагается на определенный порядок реализации операций.

C ++ (лязг), 38 байт

int f(int n){return~n==(n^=-~n)*~n/2;}

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

Не может опустить типы в C ++, не может опустить возвращение в Clang, в противном случае идентично.

C (gcc) ,  29 28  27 байтов

Сохранено 1 байт благодаря @ceilingcat

Порт 21-байтового ответа JS от @tsh .

f(p){p=2*~p==~(p=-~p^p)*p;}

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

J , 22 19 17 15 14 байт

-3 байта благодаря BolceBussiere!

-4 байта благодаря ngn!

-1 байт благодаря Traws!

J , 14 байт

1=1#.(*:|.)@#:

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

Желе , 9 байт

BŒḂaB¬S=1

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

Атташе , 22 байта

{Flip@_=_∧1=0~_}@Bin

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

альтернативы

27 байт: {BitXor[2*_,2*_+3]^2=8*_+9}

27 байт: {BitXor@@(2*_+0'3)^2=8*_+9}

27 байт: {Palindromic@_∧1=0~_}@Bin

28 байт: {BitXor[...2*_+0'3]^2=8*_+9}

28 байт: {BitXor[…2*_+0'3]^2=8*_+9}

28 байт: {Same@@Bisect@_∧1=0~_}@Bin

29 байт: {_[#_/2|Floor]=0∧1=0~_}@Bin

30 байтов: Same@Bin@{_+2^Floor[Log2@_/2]}

30 байтов: {_[#_/2|Floor]=0and 1=0~_}@Bin

Сетчатка 0.8.2 , 38 37 байт

.+
$*
+`^(1+)\1
$+0
10
1
^((1+)0\2)?$

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Изменить: После выяснения, предыдущее решение не обрабатывает ноль правильно. Объяснение:

.+
$*

Преобразовать из десятичной в одинарную.

+`^(1+)\1
$+0
10
1

Конвертировать из унарного в бинарный, используя метод из Retina wiki.

^((1+)0\2)?$

Проверьте наличие одинакового числа 1s до и после 0пустой строки или (как в приведенном выше преобразовании обрабатывается ноль).

Пакет, 39 37 байт

@cmd/cset/a"m=%1^-~%1,!(m/2*(m+2)-%1)

Пояснение: Число Циклопа имеет вид $n = (2 ^ k + 1) (2 ^ { k - 1 } - 1)$$m = 2 ^ k - 1$$n = \lfloor \frac m 2 \rfloor ( m + 2 )$$n$

Excel, 101 107 байт

-6 байт благодаря @Chronocidal.

=AND(ISEVEN(LOG(A1,2)),MID(DEC2BIN(A1),LEN(DEC2BIN(A1))/2+1,1)="0",LEN(SUBSTITUTE(DEC2BIN(A1),1,))=1)

Выполняет 3 проверки:

• Нечетная длина

ISEVEN(LOG(A1,2))

• Средний символ 0

MID(DEC2BIN(A1),LEN(DEC2BIN(A1))/2+1,1)="0"

• Есть один 0

LEN(SUBSTITUTE(DEC2BIN(A1),1,))=1

Регулярное выражение (ECMAScript), 65 59 57 58 байт

+1 байт для правильной обработки 0

^((((x*)xx)\3)x)?(?=(\1*)\2*(?=\4$)((x*)(?=\7$)x)*$)\1*$\5

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

Работает, утверждая, что вход имеет вид $(2^k - 1) (2^{k+1} + 1)$

VBA, 41 36 байт

x=2^Int([Log(A1,4)]):?[A1]=2*x^2-x-1

Запустите в окне «Немедленно» с отключенным явным объявлением. Ввод - это ячейка A1активного листа. Выводит True / False в ближайшее окно.

Использует ту же логику, что и в моем ответе Excel, чтобы найти число Циклопа с таким же количеством битов (или на 1 бит короче, если есть четное число!), А затем сравнивает его с входным значением.

Сохраняет несколько байтов при вычислении чисел Циклопа, уменьшая их до формы y = 2x^2 - x - 1 (где x = n-1для n-го числа Циклопа, или x = 2^Int(Log([A1])/Log(4))чтобы найти наибольшее число Циклопа с меньшим или равным числом битов) и сохраняя x в переменной

(-5 байт благодаря Тейлору Скотту !)

PHP , 74 байта

function($x){return($c=strlen($a=decbin($x)))&1&&trim($a,1)===$a[$c/2|0];}

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

Совершенно наивный нематематический подход, просто строки.

function cyclops( $x ) {
    $b = decbin( $x );     // convert to binary string (non-zero left padded)
    $l = strlen( $b );     // length of binary string
    $t = trim( $b, 1 );    // remove all 1's on either side
    $m = $b[ $l / 2 |0 ];  // get the middle "bit" of the binary string
    return 
        $l & 1 &&          // is binary string an odd length?
        $t === $m;         // is the middle char of the binary string the same as
                           // the string with left and right 1's removed? (can only be '0')
}

Или 60 байтов на основе алгоритма @ Chronocidal выше .

function($x){return decbin($x)==str_pad(0,log($x,2)|1,1,2);}

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

Haskell, 82 байта

import Text.Printf
(`all`[(==)<*>reverse,("0"==).filter(<'1')]).flip($).printf"%b"

И порт решения xnor Python:

Haskell, 47 байтов

import Data.Bits
\n->(2*n`xor`(2*n+3))^2==8*n+9