33

Hier, alors que je jouais avec mon enfant, j'ai remarqué le numéro dans son petit train:

Donc, nous avons qui peuvent être divisés en ou

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$

Défi si simple: à partir d’un nombre non négatif en entrée, restituez des valeurs cohérentes de véracité et de falsey qui indiquent si la représentation sous forme de chaîne du nombre (en base 10 et sans zéros non majuscules) peut être en quelque sorte divisée en nombres qui ont une puissance de 2 .

Exemples:

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

C'est du code-golf , alors que le code le plus court pour chaque langue gagne!

code-golf string number decision-problem Charlie
la source

2

@StewieGriffin Au départ, je pensais à limiter le nombre d'entrée à la plage d'un inttype standard (4 octets), mais en réalité cela ne me dérange pas si votre code ne prend pas en charge les très grands nombres. Indiquez simplement dans votre réponse les limites de votre code.

Charlie

3

Cas de test suggéré: 101(fausseté à cause du 0) ... ou cela devrait-il toujours être vrai ( 1 - 01)?

Shieru Asakoto

1

@ShieruAsakoto J'ai testé le 101cas avec les réponses actuelles et elles nous sont toutes retournées true, car il peut être divisé en 1-01deux puissances de 2, je vais donc considérer ce cas comme une vérité.

Charlie

6

Je laisse juste ça ici comme astuce pour tout le monde. Voici trois manières possibles de vérifier si un nombre est une puissance de 2: 1) Vérifiez si log2(n)ne contient pas de chiffres décimaux après la virgule. 2) Vérifiez si n AND (n-1) == 0. 3) Créez une liste de carrés-nrs et vérifiez si nest dans cette liste.

Kevin Cruijssen

1

" square-nrs " devrait être " power of 2 " dans mon commentaire ci-dessus bien sûr ..>.>

Kevin Cruijssen

11

05AB1E , 9 à 8 octets

Ýos.œåPZ

-1 octet grâce à @Emigna en utilisant Z(max) pour la liste des 0 et 1 pour imiter une anycommande pour 1(vérité).

Essayez-le en ligne ou vérifiez tous les cas de test . (REMARQUE: l’ тen-tête 100ne contient que les 100 premiers chiffres de la puissance, au lieu de la première quantité de puissance en entrée de 2 chiffres. Il fonctionne également avec la puissance de 2 en entrée, mais il est plutôt inefficace et peut délai d'attente sur TIO si l'entrée est suffisamment grande.)

Explication:

Ý            # 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)

Kevin Cruijssen
la source

2

Nice, ma solution était .œ.²1%O0å(9 octets aussi). Le mien a échoué 0, cependant.

M. Xcoder

@ Mr.Xcoder Ah, .²1%O0c'est assez intelligent aussi. Je pensais utiliser la log2même chose .²DïQ, mais il faudrait une carte autour pour pouvoir le faire pour chaque numéro, et cela ne fonctionnait pas pour Edge-Case 0.

Kevin Cruijssen

8

JavaScript (Node.js) , 54 octets

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

Essayez-le en ligne!

tsh
la source

6

JavaScript (Node.js) , ₆₉ ₆₄ 58 octets

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

Essayez-le en ligne!

Entrez comme nombre. La partie logique est assez compliquée, donc aucune idée de la façon de la démêler et de s'en débarrasser q.

-11 octets lors de la vérification de la puissance de 2.

Barboteur
la source

5

JavaScript (Node.js) , 75 69 octets

-6 octets merci @Arnauld. Au plus 32 bits support

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

Essayez-le en ligne!

Entrée sous forme de chaîne.

Shieru Asakoto
la source

5

Gelée , 9 octets

ŒṖḌl2ĊƑ€Ẹ

Découvrez la suite de tests!

Alternative

Ne fonctionne pas pour les grands cas de test en raison de problèmes de précision.

ŒṖḌæḟƑ€2Ẹ

Découvrez la suite de tests!

Comment?

Programme 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.

Programme 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.

M. Xcoder
la source

5

Python 2 , 72 70 octets

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))

Essayez-le en ligne!

ovs
la source

5

JavaScript, 59 octets

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

Essayez-le en ligne!

Construit une regex comme /^(1|0*2|0*4|0*8|0*16|0*32|…|0*1)+$/des puissances de 2, et le teste s.

Bien sûr, cela ne fonctionne que jusqu’à la précision des nombres JavaScript: les termes de l’expression rationnelle finissent par ressembler à 1.2345678e30(ou Inf). Mais comme les puissances de 2 sont faciles à représenter avec précision en virgule flottante, elles ne seront jamais des entiers faux , ce qui serait plus disqualifiant, je pense.

@th enregistré 14 octets. Neato!

Lynn
la source

59 octets

tsh

4

Python 2 , 85 octets

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

Essayez-le en ligne!

TFeld
la source

4

Perl 6 , 28 24 23 octets

-4 octets grâce à Jo King

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

Essayez-le en ligne!

Poignées puissances jusqu'à 2 ³¹ .

Nwellnhof
la source

24 octets en déplaçant le 0*hors de la partie interpolée

Jo King

3

APL (NARS), 154 caractères, 308 octets

∇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 ⍵}

La fonction pour l'exercice c'est h. L'algorithme ne semble pas exponentiel ou factoriel ... test:

  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
la source

3

Python 2 , 57 octets

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

Essayez-le en ligne!

Dennis
la source

2

Python 2 , 86 octets

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

Essayez-le en ligne!

Jonathan Frech
la source

2

Ruby , 55 octets

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

Essayez-le en ligne!

La sortie est 0si vrai et nilsi faux.

GB
la source

2

Ruby , 49 octets

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

Essayez-le en ligne!

Ne fonctionne que dans la théorie. Prend toujours pour les grandes valeurs den

GB
la source

2

PHP, 101 octets

Je ne peux pas sembler avoir moins de 100; mais je pourrais l'obtenir à 100 si 101était un cas de fausseté.

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$

variations:

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 ou plus ancien, 95 octets

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

Titus
la source

2

Rouge , 212 211 octets

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]

Essayez-le en ligne!

Une autre soumission longue, mais je ne suis pas complètement insatisfaite, car il n’existe pas de fonction intégrée permettant de trouver toutes les chaînes en rouge.

Plus lisible:

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
]

Galen Ivanov
la source

2

Axiome, 198 octets

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)

ungolf et test

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
la source

1

Japt `-!`, 12 octets

Prend l'entrée sous forme de chaîne.

ÊÆòXÄÃex_&ZÉ

L'essayer

Hirsute
la source

Le 0cas produit trueet donc des cas tels que la 1010sortie true.

Charlie

1

C # 157 octets

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))));

Vous pouvez l' essayer en ligne

Alfredo A.
la source

1

APL (NARS), 70 caractères, 140 octets

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

tester:

  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

je n'essaie pas de faire d'autres gros chiffres ... Je dois noter que P n'est pas une partition normale, mais c'est une partition où tous les éléments sont des sous-ensembles qui ont un membre tous consécutifs, par exemple

  ⎕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
└∊──────────────────────────────────────────────────┘

noter qu'il manque l'élément ((ac) (b)) ou mieux ,, ¨ ('ac') 'b'

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

RosLuP
la source

1

POSIX ERE, 91 octets

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

Ceci est totalement tricher, basé sur le texte de grands nombres (pas vraiment besoin d'être manipulé par votre code) dans la question; il gère toutes les valeurs comprises dans la plage de taille des exemples. Évidemment, on peut étendre la gamme complète de types entiers de 32 ou 64 bits aux dépens de la taille. Je l'ai principalement écrit pour montrer comment le problème s'adapte naturellement à l'outil. Un exercice amusant consisterait à le réécrire en tant que programme qui génère l'ERE pour une plage arbitraire, puis le compare.

R ..
la source

1

C (gcc) , `-DA=asprintf(&c,`+ 108 = 124 octets

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);}

Essayez-le en ligne!

Cela crée une expression rationnelle des puissances de 2 à 2 ** 32, puis fait correspondre la chaîne d'entrée à celle-ci.

Logern
la source

1

Powershell, 56 octets

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

Script de test:

$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"
}

Sortie:

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

Explication:

Construit une regex comme ^(0*1|0*2|0*4|0*8|0*16|0*32|…)+$des puissances de 2 et le teste sur des arguments.

mazzy
la source

0

JavaScript (Node.js) , 56 octets

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

Essayez-le en ligne!

l4m2
la source

Le nombre peut-il être divisé en puissances de 2?

Réponses:

05AB1E , 9 à 8 octets

JavaScript (Node.js) , 54 octets

JavaScript (Node.js) , ₆₉ ₆₄ 58 octets

JavaScript (Node.js) , 75 69 octets

Gelée , 9 octets

Alternative

Comment?

Python 2 , 72 70 octets

JavaScript, 59 octets

Python 2 , 85 octets

Perl 6 , 28 24 23 octets

APL (NARS), 154 caractères, 308 octets

Python 2 , 57 octets

Python 2 , 86 octets

Ruby , 55 octets

Ruby , 49 octets

PHP, 101 octets

PHP 5 ou plus ancien, 95 octets

Rouge , 212 211 octets

Plus lisible:

Axiome, 198 octets

Japt `-!`, 12 octets

C # 157 octets

APL (NARS), 70 caractères, 140 octets

POSIX ERE, 91 octets

C (gcc) , `-DA=asprintf(&c,`+ 108 = 124 octets

Powershell, 56 octets

JavaScript (Node.js) , 56 octets

Le nombre peut-il être divisé en puissances de 2?

Réponses:

05AB1E , 9 à 8 octets

JavaScript (Node.js) , 54 octets

JavaScript (Node.js) , 69 64 58 octets

JavaScript (Node.js) , 75 69 octets

Gelée , 9 octets

Alternative

Comment?

Python 2 , 72 70 octets

JavaScript, 59 octets

Python 2 , 85 octets

Perl 6 , 28 24 23 octets

APL (NARS), 154 caractères, 308 octets

Python 2 , 57 octets

Python 2 , 86 octets

Ruby , 55 octets

Ruby , 49 octets

PHP, 101 octets

PHP 5 ou plus ancien, 95 octets

Rouge , 212 211 octets

Plus lisible:

Axiome, 198 octets

Japt -!, 12 octets

C # 157 octets

APL (NARS), 70 caractères, 140 octets

POSIX ERE, 91 octets

C (gcc) , -DA=asprintf(&c,+ 108 = 124 octets

Powershell, 56 octets

JavaScript (Node.js) , 56 octets

JavaScript (Node.js) , ₆₉ ₆₄ 58 octets

Japt `-!`, 12 octets

C (gcc) , `-DA=asprintf(&c,`+ 108 = 124 octets