Inspiré par xkcd .

Votre défi est de déterminer si un nombre ferait une bonne combinaison dans le jeu 2048 . Votre entrée sera un nombre, tel que:

8224

Et la sortie sera de savoir si ce nombre ferait un bon combo 2048, qui pour cette entrée serait trueou yesou 1ou toute autre manière d'indiquer un résultat positif.

Pour ceux qui ne connaissent pas le jeu, voici une explication simple: les pouvoirs de deux sont disposés sur une grille, comme ceci: [2] [2]. Les tuiles peuvent être déplacées dans n'importe quelle direction, et si deux tuiles identiques se rencontrent, elles deviennent la puissance suivante de deux (donc [2] [2]lorsqu'elles sont déplacées vers la gauche ou vers la droite, elles deviennent [4]). Ou, vous pouvez simplement essayer le jeu ici .

Que signifie "une bonne combinaison 2048"? Cela signifie n'importe quel nombre qui, s'il était dans le jeu "2048", pourrait être combiné en un seul numéro. (Un zéro signifie un espace vide et peut être ignoré si nécessaire.) Notez que les nombres peuvent éventuellement être à plusieurs chiffres! Cependant, les nombres ne doivent pas changer entre les coups. Voici quelques exemples / cas de test (avec "Bon" indiquant une bonne combinaison et "Mauvais" signifiant pas bon):

• Bon: 8224 (8224 -> 844 -> 88 -> 16)
• Bon: 2222 (2222 -> 44 -> 8)
• Bon: 22048 (22048 -> 448 -> 88 -> 16)
• Mauvais: 20482 (ne peut pas combiner les 2 extérieurs, ni combiner un 2048 et un 2)
• Bon: 20482048 (20482048 -> 4096)
• Mauvais: 210241024 (210241024 -> 22048, mais c'est maintenant [2] [2048] et ne peut pas être combiné car les nombres ne peuvent pas changer entre les mouvements)
• Bon: 2048 (c'est déjà un chiffre)
• Mauvais: 2047 (ce n'est pas une puissance de 2)
• Mauvais: 11 (il n'y a pas de 1 dans le jeu)
• Bon: 000040000000 (les zéros sont des espaces vides)

Règles diverses:

• L'entrée peut être de n'importe où raisonnable, c'est-à-dire STDIN, argument de fonction, fichier, etc.
• La sortie peut également être raisonnable, c.-à-d. STDOUT, valeur de retour de fonction, fichier, etc.
• Ignorez la taille de la grille - 22222222devrait toujours afficher true.
• Il n'y a pas de maximum à ce que pourrait être le nombre, tant qu'il s'agit d'une puissance de deux. Par conséquent, les nombres possibles sont toute puissance de deux supérieure à 0.
• Pour ceux qui s'inquiètent des ambiguïtés des zéros, ce n'est pas le cas. Par exemple, 22048peut être analysé en tant que [2] [2048]ou [2] [2] [0] [4] [8]. Le premier ne fonctionne pas, mais le second fonctionne, il devrait donc afficher true.
• Il s'agit de code-golf , donc le code le plus court en octets gagnera!

GolfScript, 137 caractères

[0`]1$,4*,{2\)?`}%+:W;[]\]][]\{{:A;W{A 1=\?!},{[.A~@,>\@~+\].~!{0-.,/@+\0}*;}%~}%.}do+.{~}%,{{.-1%}%.&{[{.2$={+)}*}*]{1|(}%}%}*{,1=},!!

L'entrée doit être donnée sur STDIN. La sortie est 0/ 1pour les mauvais / bons nombres. La plupart du code est nécessaire pour analyser les entrées possibles.

Cette version plus courte (113 caractères) effectue un test de décalage simple qui ne fonctionnerait pas correctement pour une entrée comme 224422.

[0`]1$,4*,{2\)?`}%+:W;[]\]][]\{{:A;W{A 1=\?!},{[.A~@,>\@~+\].~!{0-.,/@+\0}*;}%~}%.}do+{W{~[.:S]/[S.+]*}/,1=},!!

Tous les cas de test peuvent être vérifiés en ligne .

Python: 457 422 caractères

z=range
def c(n):
 for x in z(1,12): 
  if int(n)==2**x:return 1
 return 0
def p(s):
 if s=='':return[]
 for i in z(len(s),0,-1):
  if c(s[:i])>0and p(s[i:])!=1:return [int(s[:i])]+p(s[i:])
 return 1
def r(a):
 if len(a)==1:return 1
 i,t=1,a[:1]
 while i<len(a):
  if a[i]==t[-1]:t[-1]*=2
  else:t+=[a[i]]
  i+=1
 if len(t)==len(a):return 0
 return r(t) 
def f(s):
 if p(s)==1or r(p(s))==0:print('bad')
 else:print('good')

La fonction f (s) obtient une chaîne de chiffres et sort «bon» ou «mauvais» en conséquence. J'ai choisi de ne pas utiliser 0 comme espace car les espaces n'ont pas de sens dans le jeu et ils créent une ambiguïté lors de l'analyse des chaînes (22048 est-il bon ou mauvais?). Cela n'utilise que des nombres jusqu'à 2048, mais cela peut être modifié sans ajouter de caractères. Au prix de 10 caractères environ, je peux également imprimer toutes les étapes de la combinaison des chiffres. Et je me rends compte que ce code n'est pas encore assez golfé; ne vous inquiétez pas, les modifications arrivent.

Haskell: 285 254 253 237 230 227

utilisation - il suffit de le charger dans ghci et de passer la chaîne à h.

*Main> h "210241024"
False
*Main> h (replicate 1024 '2') -- very long string
True
*Main> h (replicate 1023 '2') -- odd one out
False

Code:

t=i 0
i n=mod n 2<1&&(n<3||i(div n 2))
a%[]|i a=[[a]]|t=[];a%(b:c)=[a:d|d<-b%c,i a]++(a*10+b)%c
c(0:a)=c a;c(a:b:d)|a==b=(a+a):c d|t=a:c(b:d);c a=a
l a=c a/=a&&(g.c)a
g[a]=t;g a=l a||(l.reverse)a
h b=any g$0%(map(read.(:[]))b)

Commentaire: iest le contrôle si un nombre est une puissance de 2, ce sera dépassé par les langues avec un peu de twiddling. %génère récursivement toutes les analyses qui sont des listes de pouvoirs de 2 ou 0. créduit les tuiles. lteste récursivement si les tuiles sont repliables à gauche ou bien. gteste si les tuiles sont pliables à gauche ou à droite. Il n'y a pas de limite aux nombres sur les tuiles - par exemple, h ((show (2^200))++(show (2^200)))retourne vrai pour 2 tuiles marquées "1606938044258990275541962092341162602522202993782792835301376".

Modifié pour corriger un bug qui ne s'est pas effondré correctement "88222288888" vers la droite, mais a également trouvé plus de possibilités de golf.

Perl, 175-336 octets

while(<>){chomp;$n="nothing";$\=("."x(1+/^[2048]+$/+/^((\d+)0*\2)+$/+((sprintf"%b",
$_)!~/1.*1/)))."\n";($o=$\)=~y/.\n/oh/;print$o;$m=length;for$i(1..$m){$a=$_;$r=
qr((\d*[2468])0*\2)0*/;($b=substr$a,0,$i,"")=~s/$r/$2+$2/ge;@n=$"="$b$a";push@n,$"while$"
=~s/$r/$2+$2/ge;($"%2&&next)||($">>=1)while$">1;$n="nice";(print)for@n;last}print$n}

Garder juste l'essentiel intact:

$_=shift;$m=length;for$i(1..$m){$a=$_;$r=qr/((\d*[2468])0*\2)0*/;($b=substr$a,0,$i,"")=~
s/$r/$2*2/ge;$"="$b$a";1while$"=~s/$r/$2*2/ge;($"%2&&next)||($">>=1)while$">1;exit}die;

1

ooh .. 1 .. agréable ..

2

oooh ... 2 ... sympa ...

22

oooh ... 22 ... 4 ... sympa ...

42

ooh .. rien ..

422

ooh .. 422 .. 44 .. 8 .. sympa ..

322

Oh. rien.

336

Oh. rien.

4224

ooh .. rien ..

4228

ooh .. 4228 .. 448 .. 88 .. 16 .. sympa ..

16022481602248

ooh .. 1604481602248 .. 16088160448 .. 1601616088 .. 3216016 .. 3232 .. 64 .. nice ..

[ 64 et 256 conduisent à des ambiguïtés mal résolues auxquelles la correspondance gourmande ne peut pas faire face ... mais ce sont de bons nombres d'octets. ]

2048

oooh ... 2048 ... sympa ...

Delphi 572 582 caractères

Code édité, la limite est définie sur 2 ^ 30 afin qu'elle ne dépasse pas la valeur MaxInt dans Delphi.

Golfé

uses SysUtils,Classes;var t,j,c:integer;s,n:string;L:TStringList;function p(x:string):boolean;var r,i:int64;begin if x='0'then exit(1>0);i:=2;r:=StrToInt(x);while i<r do i:=i*2;p:=i=r;end;begin read(s);t:=0;L:=TStringList.Create;j:=1;while j<=Length(s)do begin for c:=9downto 1do begin n:=copy(s,j,c);if p(n)then break;end;if n>'0'then L.Add(n);j:=j+Length(n);end;for j:=0to L.Count-1do t:=t+StrToInt(L[j]);j:=0;repeat if j=L.Count-1then break;if L[j]=L[j+1]then begin L[j]:=IntToStr(StrToInt(L[j])*2);L.Delete(j+1);j:=0;end else inc(j);until L.Count=1;write(strtoint(L[0])=t);end.

Non golfé

uses
  SysUtils,
  Classes;

var
  t,j,c:integer;
  s,n:string;
  L:TStringList;
  function p(x:string):boolean;
  var
    r,i:int64;
  begin
    if x='0'then exit(1>0);
    i:=2;r:=StrToInt(x);
    while i<r do
      i:=i*2;
    p:=i=r;
  end;
begin
    read(s);
    t:=0;L:=TStringList.Create;
    j:=1;
    while j<=Length(s)do
    begin
      for c:=9downto 1do
      begin
        n:=copy(s,j,c);
        if p(n)then break;
      end;
      if n>'0'then L.Add(n);
      j:=j+Length(n);
    end;
    for j:=0to L.Count-1do
      t:=t+StrToInt(L[j]);
    j:=0;
    repeat
      if j=L.Count-1then break;
      if L[j]=L[j+1]then
      begin
        L[j]:=IntToStr(StrToInt(L[j])*2);
        L.Delete(j+1);j:=0
      end
      else
        inc(j);
    until L.Count=1;
    write(strtoint(L[0])=t);
end.

ÉDITER

Je suis donc devenu curieux et je me suis demandé combien de ces combinaisons conviendraient au puzzle et j'en ai testé un.

Pour les autres curieux, faites aussi un test;)

Mais ok voici les résultats:
20736 combinations were tested and 1166 were great combinations

Je dois dire que des combinaisons avec 3 ou plus de zéros ont été sautées (donc un sens droit?) Les
combinaisons sont presque uniques, ce qui signifie les combinaisons 2248, 8224, 8422et 4228ont tous été comptés comme une grande combinaison.

Mathematica - 218 octets

f=MemberQ[DeleteCases[Map[FromDigits,l~Internal`PartitionRagged~#&/@Join@@Permutations/@IntegerPartitions@Length[l=IntegerDigits@#],{2}],{___,x_,___}/;!IntegerQ[2~Log~x]||x<2]//.{a___,x_,x_,b___}:>{a,2x,b},{_Integer}]&

Version non golfée:

f[n_] := MemberQ[
  DeleteCases[
      Map[
        FromDigits, 
        Internal`PartitionRagged[l, #] & /@ 
          Join @@ Permutations /@ IntegerPartitions[Length[l = IntegerDigits[n]]], 
        {2}
      ],
      {___, x_, ___} /; x < 2 || ! IntegerQ[2~Log~x]
    ]
  ] //. {a___, x_, x_, b___} :> {a, 2 x, b}, 
  {_Integer}
]

La Internal\magie de PartitionRagged est tirée de cette question .

Cette solution gère des tailles de grille arbitraires et des nombres arbitrairement grands.

Voici une version de 195 octets qui fonctionne comme le jeu réel avec jusqu'à 4 tuiles seulement (ce qui f[22222222]est le cas False):

f=MemberQ[(d=DeleteCases)[d[ReplaceList[IntegerDigits@#,{a__,b___,c___,d___}:>FromDigits/@{{a},{b},{c},{d}}],0,2],{___,x_,___}/;!IntegerQ[2~Log~x]||x<2]//.{a___,x_,x_,b___}:>{a,2x,b},{_Integer}]&

où j'ai remplacé

Map[
  FromDigits, 
  Internal`PartitionRagged[l, #] & /@ 
    Apply[
      Join, 
      Permutations /@ IntegerPartitions[Length[l = IntegerDigits@#]]
    ], 
  {2}
]

avec

ReplaceList[
  IntegerDigits[n], 
  {a__, b___, c___, d___} :> FromDigits /@ {{a}, {b}, {c}, {d}}
]

Haskell - 260 263

import Data.Bits
p[x]=[[[x]]]
p(x:s)=do r@(h:t)<-p s;[[x]:r,(x:h):t]
q=filter(and.map(\n->(n::Integer)/=1&&n.&.(-n)==n)).map(filter(/=0)).map(map read).p
c(x:y:s)
 |x==y=2*x:c s
 |True=x:(c$y:s)
c x=x
r[x]=True
r l=c l/=l&&(r(c l)||r(c$reverse l))
f=or.map r.q

fest la fonction. Exemples:

> f"22228"
True
> f"20482044"
False

Une petite explication:
prenvoie toutes les façons de diviser une liste.
qfiltre ceux qui se composent uniquement de puissances de 2 (à l'exclusion de 1 mais dont 0).
cessaie de réduire une chaîne.
ritère les collapsus droit et gauche jusqu'à ce qu'il ne reste plus qu'un élément, ou que la chaîne soit incollapsable.