Inspirowany przez xkcd .

Wyzwanie polega na ustaleniu, czy liczba stanowi dobrą kombinację w grze 2048 . Twój wpis będzie liczbą, taką jak:

8224

A wyjście będzie to, czy ta liczba będzie zrobić dobry 2048 kombi, który dla tego wejścia byłby truelub yeslub 1lub inny sposób wskazuje na pozytywny wynik.

Dla tych, którzy nie są zaznajomieni z gry, oto proste wyjaśnienie: potęgami dwójki są rozmieszczone na siatce, tak: [2] [2]. Płytki można przesuwać w dowolnym kierunku, a jeśli spotykają się dwa identyczne kafelki, stają się one kolejną siłą dwóch (tak więc [2] [2]po przesunięciu w lewo lub w prawo [4]). Możesz też po prostu wypróbować grę tutaj .

Co oznacza „dobra kombinacja 2048”? Oznacza dowolną liczbę, która gdyby była w grze „2048”, mogłaby być połączona w jedną liczbę. (Zero oznacza puste miejsce i w razie potrzeby można je zignorować). Pamiętaj, że liczby mogą składać się z wielu cyfr! Jednak liczby nie mogą się zmieniać między ruchami. Oto kilka przykładów / przypadków testowych („Dobry” oznacza dobrą kombinację, a „Zły” oznacza niezadowalający):

• Dobry: 8224 (8224 -> 844 -> 88 -> 16)
• Dobry: 2222 (2222 -> 44 -> 8)
• Dobra: 22048 (22048 -> 448 -> 88 -> 16)
• Źle: 20482 (nie można łączyć zewnętrznych 2, ani nie można łączyć 2048 i 2)
• Dobry: 20482048 (20482048 -> 4096)
• Źle: 210241024 (210241024 -> 22048, ale teraz jest to [2] [2048] i nie można ich łączyć, ponieważ liczby nie mogą się zmieniać między ruchami)
• Dobrze: 2048 (to już jedna liczba)
• Źle: 2047 (to nie jest potęga 2)
• Źle: 11 (w grze nie ma 1)
• Dobrze: 000040000000 (zera to puste spacje)

Różne zasady:

• Dane wejściowe mogą być z dowolnego uzasadnionego miejsca, tj. STDIN, argument funkcji, plik itp.
• Dane wyjściowe mogą być również w dowolnym miejscu uzasadnionym, tj. STDOUT, wartość zwracana przez funkcję, plik itp.
• Zignoruj ​​rozmiar siatki - 22222222nadal powinien generować wartość true.
• Nie jest to maksymalna liczba, która może być, o ile jest to potęga dwóch. Dlatego możliwymi liczbami są dowolne potęgi dwóch większe od 0.
• Dla tych, którzy martwią się zerami powodującymi niejednoznaczność, tak nie jest. Na przykład 22048może być parsowany jako jeden [2] [2048]lub [2] [2] [0] [4] [8]. Pierwszy nie działa, ale drugi działa, więc powinien wypisać true.
• To jest golf golfowy , więc wygra najkrótszy kod w bajtach!

GolfScript, 137 znaków

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

Dane wejściowe należy podać na STDIN. Dane wyjściowe to 0/ 1dla złych / dobrych liczb. Większość kodu jest niezbędna do parsowania możliwych danych wejściowych.

Ta krótsza wersja (113 znaków) wykonuje prosty test zmiany, który nie działałby poprawnie w przypadku wprowadzania danych 224422.

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

Wszystkie przypadki testowe można sprawdzić online .

Python: 457 422 znaków

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

Funkcja f (s) pobiera ciąg cyfr i odpowiednio wyświetla „dobre” lub „złe”. Zdecydowałem się nie używać 0 jako spacji, ponieważ spacje nie mają znaczenia w grze i powodują dwuznaczność podczas analizowania ciągów (czy 22048 jest dobre czy złe?). To używa tylko liczb do 2048, ale można to zmienić bez dodawania znaków. Kosztem około 10 znaków mogę również wydrukować wszystkie etapy łączenia liczb. I zdaję sobie sprawę, że ten kod nie jest jeszcze wystarczająco golfowy; nie martw się, nadchodzą zmiany.

Haskell: 285 254 253 237 230 227

użycie - wystarczy załadować go do ghci i przekazać ciąg do h.

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

Kod:

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)

Komentarz: ijest to sprawdzenie, czy liczba jest potęgą 2, zostanie to rozegrane przez języki z nieznacznym przewrotem. %rekurencyjnie generuje wszystkie parsowania, które są listami potęg 2 lub 0. czrzuca płytki. lrekursywnie sprawdza, czy płytki są składane po lewej lub dobre. gsprawdza, czy płytki można składać w lewo lub w prawo. Liczby na kafelkach nie są ograniczone - np. h ((show (2^200))++(show (2^200)))Zwraca true dla 2 kafelków oznaczonych „1606938044258990275541962092341162602522202993782792835301376”.

Edytowano, aby naprawić błąd, który nie spowodował prawidłowego zwinięcia „88222288888” po prawej stronie, ale także znalazł więcej możliwości gry w golfa.

Perl, 175–336 bajtów

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}

Utrzymanie nienaruszonych podstawowych elementów:

$_=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 .. nice ..

2)

oooh ... 2 ... miło ...

22

oooh ... 22 ... 4 ... miło ...

42

ooh .. nic ..

422

ooh .. 422 .. 44 .. 8 .. fajnie ..

322

O. nic.

336

O. nic.

4224

ooh .. nic ..

4228

ooh .. 4228 .. 448 .. 88 .. 16 .. fajnie ..

16022481602248

ooh .. 1604481602248 .. 16088160448 .. 1601616088 .. 3216016 .. 3232 .. 64 .. ładne ..

[ 64 i 256 prowadzą do słabo rozwiązywalnych dwuznaczności, z którymi chciwe dopasowanie nie jest w stanie sobie poradzić ... ale są to ładne liczby bajtów. ]

2048

oooh ... 2048 ... miło ...

Delfy 572 582 znaków

Edytowany kod, limit jest ustawiony na 2 ^ 30, więc nie przekroczy wartości MaxInt w Delphi.

Grał w golfa

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.

Nie golfił

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.

EDYTOWAĆ

Zainteresowałem się więc i zastanawiałem, ile z tych kombinacji pasuje do układanki, i przetestowałem ją.

Dla innych, którzy również są ciekawi, wykonaj również test;)

Ale ok, oto wyniki:
20736 combinations were tested and 1166 were great combinations

Muszę powiedzieć kombinacje 3 lub więcej zer zostały pominięte (sens prawda?)
Kombinacje są niemal unikatowe, czyli kombinacje 2248, 8224, 8422i 4228wszystkie były liczone jako wielki kombinacji.

Mathematica - 218 bajtów

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}]&

Wersja bez golfa:

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}
]

Internal\PartitionRagged` magia pochodzi z tego pytania .

To rozwiązanie obsługuje dowolne rozmiary siatki i dowolnie duże liczby.

Oto 195-bajtowa wersja, która działa jak rzeczywista gra z maksymalnie 4 płytkami (tak f[22222222]jest 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}]&

gdzie wymieniłem

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

z

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

fjest funkcją. Przykłady:

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

Małe wyjaśnienie:
pzwraca wszystkie sposoby podziału listy.
qfiltruje te, które składają się tylko z potęg 2, (wyłączając 1, ale włączając 0).
cpróbuje zwinąć ciąg.
riteruje prawe i lewe zwinięcie, aż pozostanie tylko 1 element lub łańcuch nie będzie składany.