33

Вчера, играя с моим ребенком, я заметил номер в его игрушечном поезде:

Таким образом, у нас есть которые можно разделить на или

4281

$4281$

4 - 2 - 8 - 1

$4-2-8-1$

2^{2} - 2^{1} - 2^{3} - 2^{0}

$2^2-2^1-2^3-2^0$

Очень простая задача: если в качестве входных данных ввести неотрицательное число, верните непротиворечивые значения истинности и фальси, которые показывают, можно ли каким-то образом разбить строковое представление числа (в базе 10 и без начальных нулей) на числа, являющиеся степенями 2 ,

Примеры:

4281      truthy (4-2-8-1)
164       truthy (16-4 or 1-64)
8192      truthy (the number itself is a power of 2)
81024     truthy (8-1024 or 8-1-02-4)
101       truthy (1-01)
0         falsey (0 cannot be represented as 2^x for any x)
1         truthy
3         falsey
234789    falsey
256323    falsey (we have 256 and 32 but then 3)
8132      truthy (8-1-32)

Tests for very large numbers (not really necessary to be handled by your code):
81024256641116  truthy (8-1024-256-64-1-1-16)
64512819237913  falsey

Это код-гольф , поэтому победит самый короткий код для каждого языка!

code-golf string number decision-problem Чарли
источник

2

@ StewieGriffin Первоначально я думал об ограничении входного числа диапазоном стандартного intтипа (4 байта), но на самом деле я не против, если ваш код не поддерживает очень большие числа. Просто укажите в своем ответе ограничения вашего кода.

Чарли

3

Предлагаемый контрольный пример: 101(ложно из-за 0) ... или это все еще должно быть правдой ( 1 - 01)?

Шиеру Асакото

1

@ShieruAsakoto Я тестировал 101случай с текущими ответами, и они все возвращаются true, потому что они могут быть разделены на 1-01две степени, так что я буду считать, что этот случай правдив.

Чарли

6

Просто оставив это здесь как совет для всех. Вот три возможных способа проверить, является ли число степенью 2: 1) Проверьте log2(n), не содержит ли десятичные цифры после запятой. 2) Проверьте, если n AND (n-1) == 0. 3) Создайте список квадратов и проверьте, есть ли nв этом списке.

Кевин Круйссен

1

« квадрат-нрс » должен быть « степенью 2 » в моем комментарии выше, конечно ..>.>

Кевин Круйссен

11

05AB1E , 9 8 байт

Ýos.œåPZ

-1 байт благодаря @Emigna , используя Z(max) для списка 0 и 1, чтобы имитировать anyкоманду для 1(truey).

Попробуйте онлайн или проверьте все контрольные примеры . (ПРИМЕЧАНИЕ. тЗаголовок 100должен получить только первые 100 степеней 2 чисел вместо первого входного значения степеней 2 чисел. Он также работает с входным значением степени 2, но довольно неэффективно и может тайм-аут на TIO, если вход достаточно велик.)

Объяснение:

Ý            # Create a list in the range [0,n], where n is the (implicit) input
             # (or 100 in the TIO)
             #  i.e. 81024 → [0,1,2,3,...,81024]
 o           # Raise 2 to the `i`'th power for each `i` in the list
             #  → [1,2,4,8,...,451..216 (nr with 24391 digits)]
  s          # Swap to take the input
   .œ        # Create each possible partition of this input
             #  i.e. 81024 → [["8","1","0","2","4"],["8","1","0","24"],...,["8102","4"],["81024"]]
     å       # Check for each if it's in the list of powers of 2
             #  → [[1,1,0,1,1],[1,1,0,0],...,[0,1],[0]]
      P      # Check for each inner list whether all are truthy
             #  → [0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0]
       Z     # Take the maximum (and output implicitly)
             #  → 1 (truthy)

Кевин Круйссен
источник

2

.œ.²1%O0åХорошо , мое решение было (9 байтов). Моя не удалась 0, однако.

Мистер Xcoder

@ Mr.Xcoder А, .²1%O0это тоже очень умно. Я думал об использовании, log2как это .²DïQ, но это потребовало бы карты вокруг него, чтобы сделать это для каждого числа, и это действительно не работало для крайнего случая 0.

Кевин Круйссен

8

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

f=(v,o=10)=>v&v-1|!v?v>o?f(v%o)&f(v/o|0)|f(v,o*10):0:1

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

ТТГ
источник

6

JavaScript (Node.js) , ₆₉ ₆₄ 58 байт

f=(x,m=10,q=!(x%m&x%m-1|!x))=>x<m?q:q&&f(x/m|0)||f(x,10*m)

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

Введите как число. Логическая часть довольно запутанная, поэтому понятия не имею, как ее распутать и от чего избавиться q.

-11 байт при проверке степени 2.

фонтанчик для питья
источник

5

JavaScript (Node.js) , 75 69 байт

-6 байт, спасибо @Arnauld. Максимум 32-битная поддержка

f=x=>+x?[...x].some((_,i)=>(y=x.slice(0,++i))&~-y?0:f(x.slice(i))):!x

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

Ввод в виде строки.

Сиеру Асакото
источник

5

Желе , 9 байт

ŒṖḌl2ĊƑ€Ẹ

Проверьте набор тестов!

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

Не работает для больших тестовых случаев из-за проблем с точностью.

ŒṖḌæḟƑ€2Ẹ

Проверьте набор тестов!

Как?

Программа I

ŒṖḌl2ĊƑ€Ẹ     Full program. N = integer input.
ŒṖ            All possible partitions of the digits of N.
  Ḍ           Undecimal (i.e. join to numbers).
   l2         Log2. Note: returns (-inf+nanj) for 0, so it doesn't fail.
     ĊƑ€      For each, check if the logarithm equals its ceil.
        Ẹ     Any. Return 0 if there are no truthy elements, 1 otherwise.

Программа II

ŒṖḌæḟƑ€2Ẹ     Full program. N = integer input.
ŒṖ            All possible partitions of the digits of N.
  Ḍ           Undecimal (i.e. join to numbers).
     Ƒ€       For each partition, check whether its elements are invariant under...
   æḟ  2      Flooring to the nearest power of 2.
        Ẹ     Any. Return 0 if there are no truthy elements, 1 otherwise.

Мистер Xcoder
источник

5

Python 2 , 72 70 байт

f=lambda n,m=10:n>=m/10and(n%m&n%m-1<1and(n/m<1or f(n/m))or f(n,m*10))

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

овс
источник

5

JavaScript, 59 байт

s=>eval(`/^(${(g=x=>x>s?1:x+'|0*'+g(x+x))(1)})+$/`).test(s)

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

Создает регулярное выражение типа /^(1|0*2|0*4|0*8|0*16|0*32|…|0*1)+$/степеней 2 и проверяет его s.

Разумеется, работает только с точностью до чисел JavaScript: в конечном итоге термины в регулярном выражении будут выглядеть 1.2345678e30(или Inf). Но так как степени 2 легко точно представить в плавающей точке, они никогда не будут неправильными целыми числами, что, я думаю, было бы более дисквалифицирующим.

@tsh сохранил 14 байтов. Neato!

Линн
источник

59 байтов

tsh

4

Python 2 , 85 байт

f=lambda n:bin(int(n)).count('1')==1or any(f(n[:i])*f(n[i:])for i in range(1,len(n)))

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

TFeld
источник

4

Perl 6 , 28 24 23 байта

-4 байта благодаря Джо Кингу

{?/^[0*@(2 X**^32)]+$/}

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

Управляет полномочиями до 2 ³¹ .

nwellnhof
источник

24 байта , перемещая 0*из интерполированной части

Джо Кинг,

3

APL (NARS), 154 символа, 308 байтов

∇r←f w;g;b;z;k
   g←{⍵≤0:1⋄t=⌊t←2⍟⍵}⋄→A×⍳∼w≤9⋄r←g w⋄→0
A: z←w⋄b←0⋄k←1
B: b+←k×10∣z⋄z←⌊z÷10
   →C×⍳∼g b⋄r←∇z⋄→0×⍳r
C: k×←10⋄→B×⍳z≠0
   r←0
∇
h←{⍵=0:0⋄f ⍵}

Функция для упражнения это ч. Алгоритм не кажется экспоненциальным или факториальным ... тест:

  h¨ 4281 164 8192 81024 101 
1 1 1 1 1 
  h¨ 0 1 3 234789 256323 8132
0 1 0 0 0 1 
  h 81024256641116
1
  h 64512819237913
0

RosLuP
источник

3

Python 2 , 57 байт

f=lambda n,k=10:k<11*n>n%k&n%k-1<(n<k)|f(n/k)|f(n,10*k)*n

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

Деннис
источник

2

Python 2 , 86 байт

lambda n:re.match('^(%s)*$'%'|'.join('0*'+`1<<k`for k in range(n)),`n`)and 0;import re

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

Джонатан Фрех
источник

2

Рубин , 55 байт

->n{a=*b=1;a<<b*=2until b>n;n.to_s=~/^(0*(#{a*?|}))*$/}

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

Выходные данные - 0если true и nilесли false.

гигабайт
источник

2

Рубин , 49 байтов

->n{n.to_s=~/^(0*(#{(0..n).map{|x|2**x}*?|}))*$/}

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

Работает только в теории. Принимает навсегда для больших значенийn

гигабайт
источник

2

PHP, 101 байт

Кажется, не могу получить это ниже 100; но я мог бы получить его до 100, если бы 101был ложный случай.

function f($s){for($x=.5;$s>=$x*=2;)if(preg_match("/^$x(.*)$/",$s,$m)?!~$m[1]||f(+$m[1]):0)return 1;}

$NULL$ $1$

варианты:

for($x=.5;$s>=$x*=2;)
while($s>=$x=1<<$i++)   # yields notices "undefined variable $i"

?!~$m[1]||f(+$m[1]):0
?~$m[1]?f(+$m[1]):1:0

PHP 5 или старше, 95 байт

function f($s){while($s>=$x=1<<$i++)if(ereg("^$x(.*)$",$s,$m)?$m[1]>""?f(+$m[1]):1:0)return 1;}

Titus
источник

2

Красный , 212 211 байт

func[n][g: func[x][(log-2 do x)% 1 = 0]repeat i 2 **((length? s: form n)- 1)[b: a:
copy[] k: i foreach c s[append b c if k % 2 = 0[alter a g rejoin b
b: copy[]]k: k / 2]append a g form c if all a[return on]]off]

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

Еще одна длинная отправка, но я не совсем недоволен, потому что нет встроенного средства для поиска всех подстрок в красном.

Более читабельно:

f: func [ n ] [
    g: func [ x ] [ (log-2 do x) % 1 = 0 ]
    repeat i 2 ** ((length? s: form n) - 1) [
        b: a: copy []
        k: i
        foreach c s [
            append b c
            if k % 2 = 0 [ 
                append a g rejoin b
                b: copy []
            ]
            k: k / 2 
        ]
        append a g form c
        if all a[ return on ]
    ]
    off
]

Гален Иванов
источник

2

Аксиома, 198 байт

G(a)==(a<=1=>2>1;x:=log_2 a;x=floor x)
F(n)==(n<=9=>G n;z:=n;b:=0;k:=1;repeat(b:=b+k*(z rem 10);z:=z quo 10;if G b and F z then return 2>1;k:=k*10;z<=0=>break);1>1)
H(n:NNI):Boolean==(n=0=>1>1;F n)

разгрызть и проверить

g(a)==(a<=1=>2>1;x:=log_2 a;x=floor x)
f(n)==
   n<=9=>g n
   z:=n;b:=0;k:=1
   repeat
      b:=b+k*(z rem 10);z:=z quo 10;
      if g b and f z then return 2>1
      k:=k*10
      z<=0=>break
   1>1
h(n:NNI):Boolean==(n=0=>1>1;f n)

(15) -> [[i,h i] for i in [4281,164,8192,81024,101]]
   (15)  [[4281,true],[164,true],[8192,true],[81024,true],[101,true]]
                                                      Type: List List Any
(16) -> [[i,h i] for i in [0,1,3,234789,256323,8132]]
   (16)  [[0,false],[1,true],[3,false],[234789,false],[256323,false],[8132,true]]
                                                      Type: List List Any
(17) -> [[i,h i] for i in [81024256641116, 64512819237913]]
   (17)  [[81024256641116,true],[64512819237913,false]]
                                                      Type: List List Any
(18) -> h 44444444444444444444444444
   (18)  true
                                                            Type: Boolean
(19) -> h 44444444444444444128444444444
   (19)  true
                                                            Type: Boolean
(20) -> h 4444444444444444412825444444444
   (20)  false
                                                            Type: Boolean
(21) -> h 2222222222222244444444444444444412822222222222210248888888888882048888888888888888
   (21)  true
                                                            Type: Boolean
(22) -> h 222222222222224444444444444444441282222222222225128888888888882048888888888888888
   (22)  true
                                                            Type: Boolean

RosLuP
источник

1

Japt `-!`, 12 байт

Принимает ввод в виде строки.

ÊÆòXÄÃex_&ZÉ

Попытайся

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

В 0случае выхода trueи , следовательно , случаи , такие как 1010также выход true.

Чарли

1

C # 157 байт

bool P(string s,int i=1)=>i>=s.Length?((Func<ulong,bool>)((x)=>(x!=0)&&((x&(x-1))==0)))(ulong.Parse(s)):(P(s,i+1)||(P(s.Substring(0,i))&&P(s.Substring(i))));

Вы можете попробовать это онлайн

Альфредо А.
источник

1

APL (NARS), 70 символов, 140 байтов

P←{k←↑⍴⍵⋄x←11 1‼k k⋄y←⍵⋄∪{x[⍵;]⊂y}¨⍳↑⍴x}
f←{⍵=0:0⋄∨/∧/¨y=⌊y←2⍟⍎¨¨P⍕⍵}

тест:

  f¨ 4281 164 8192 81024 101
1 1 1 1 1 
  f¨ 0 1 3 234789 256323 8132
0 1 0 0 0 1 
  f 126
0

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

  ⎕fmt P 'abc'
┌4──────────────────────────────────────────────────┐
│┌1─────┐ ┌2─────────┐ ┌2─────────┐ ┌3─────────────┐│
││┌3───┐│ │┌2──┐ ┌1─┐│ │┌1─┐ ┌2──┐│ │┌1─┐ ┌1─┐ ┌1─┐││
│││ abc││ ││ ab│ │ c││ ││ a│ │ bc││ ││ a│ │ b│ │ c│││
││└────┘2 │└───┘ └──┘2 │└──┘ └───┘2 │└──┘ └──┘ └──┘2│
│└∊─────┘ └∊─────────┘ └∊─────────┘ └∊─────────────┘3
└∊──────────────────────────────────────────────────┘

обратите внимание, что отсутствует элемент ((ac) (b)) или лучше ,, ¨ ('ac') 'b'

  ⎕fmt ,,¨('ac')'b'
┌2─────────┐
│┌2──┐ ┌1─┐│
││ ac│ │ b││
│└───┘ └──┘2
└∊─────────┘

RosLuP
источник

1

POSIX ERE, 91 байт

(0*([1248]|16|32|64|128|256|512|1024|2048|4096|8192|16384|32768|65536|131072|262144|524288))+

Это полностью измена, основанная на больших числах текста (не обязательно, чтобы их обрабатывал ваш код) в вопросе; он обрабатывает все значения в диапазоне размеров примеров. Очевидно, что может быть расширен до полного диапазона 32- или 64-битных целочисленных типов за счет размера. Я в основном написал это как демонстрацию того, как проблема естественным образом соответствует инструменту. Веселое упражнение - переписать его как программу, которая генерирует ERE для произвольного диапазона, а затем сопоставляет его.

Р..
источник

1

C (gcc) , `-DA=asprintf(&c,`+ 108 = 124 байта

p,c;f(a,i){c="^(0*(1";for(i=0;i<31;)A"%s|%d",c,1<<++i);A"%s))+$",c);regcomp(&p,c,1);a=!regexec(&p,a,0,0,0);}

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

Это создает регулярное выражение степеней от 2 до 2 ** 32, а затем сопоставляет входную строку с ним.

Logern
источник

1

Powershell, 56 байт

$x=(0..63|%{1-shl$_})-join'|0*'
"$args"-match"^(0*$x)+$"

Тестовый скрипт:

$f = {

    $x=(0..63|%{1-shl$_})-join'|0*'
    "$args"-match"^(0*$x)+$"

}

@(
    ,(4281            ,$true)
    ,(164             ,$true)
    ,(8192            ,$true)
    ,(81024           ,$true)
    ,(101             ,$true)
    ,(0               ,$false)
    ,(1               ,$true)
    ,(3               ,$false)
    ,(234789          ,$false)
    ,(256323          ,$false)
    ,(8132            ,$true)
    ,("81024256641116"  ,$true)
    ,("64512819237913"  ,$false)
) | % {
    $n, $expected = $_
    $result = &$f $n
    "$($result-eq$expected): $result <- $n"
}

Выход:

True: True <- 4281
True: True <- 164
True: True <- 8192
True: True <- 81024
True: True <- 101
True: False <- 0
True: True <- 1
True: False <- 3
True: False <- 234789
True: False <- 256323
True: True <- 8132
True: True <- 81024256641116
True: False <- 64512819237913

Объяснение:

Создает регулярное выражение типа ^(0*1|0*2|0*4|0*8|0*16|0*32|…)+$степеней 2 и проверяет его на аргументы.

Mazzy
источник

0

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

f=(x,c=v=1)=>x<v?x.match('^('+c+')+$'):f(x,c+'|'+(v*=2))

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

l4m2
источник

Можно ли разделить число на степени 2?

Ответы:

05AB1E , 9 8 байт

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

JavaScript (Node.js) , ₆₉ ₆₄ 58 байт

JavaScript (Node.js) , 75 69 байт

Желе , 9 байт

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

Как?

Python 2 , 72 70 байт

JavaScript, 59 байт

Python 2 , 85 байт

Perl 6 , 28 24 23 байта

APL (NARS), 154 символа, 308 байтов

Python 2 , 57 байт

Python 2 , 86 байт

Рубин , 55 байт

Рубин , 49 байтов

PHP, 101 байт

PHP 5 или старше, 95 байт

Красный , 212 211 байт

Более читабельно:

Аксиома, 198 байт

Japt `-!`, 12 байт

C # 157 байт

APL (NARS), 70 символов, 140 байтов

POSIX ERE, 91 байт

C (gcc) , `-DA=asprintf(&c,`+ 108 = 124 байта

Powershell, 56 байт

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

Можно ли разделить число на степени 2?

Ответы:

05AB1E , 9 8 байт

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

JavaScript (Node.js) , 69 64 58 байт

JavaScript (Node.js) , 75 69 байт

Желе , 9 байт

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

Как?

Python 2 , 72 70 байт

JavaScript, 59 байт

Python 2 , 85 байт

Perl 6 , 28 24 23 байта

APL (NARS), 154 символа, 308 байтов

Python 2 , 57 байт

Python 2 , 86 байт

Рубин , 55 байт

Рубин , 49 байтов

PHP, 101 байт

PHP 5 или старше, 95 байт

Красный , 212 211 байт

Более читабельно:

Аксиома, 198 байт

Japt -!, 12 байт

C # 157 байт

APL (NARS), 70 символов, 140 байтов

POSIX ERE, 91 байт

C (gcc) , -DA=asprintf(&c,+ 108 = 124 байта

Powershell, 56 байт

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

JavaScript (Node.js) , ₆₉ ₆₄ 58 байт

Japt `-!`, 12 байт

C (gcc) , `-DA=asprintf(&c,`+ 108 = 124 байта