Вдохновленный xkcd .

Ваша задача - определить, будет ли число составлять хорошую комбинацию в игре 2048 . Ваш ввод будет числом, таким как:

8224

И выводом будет то, будет ли это число составлять хорошую комбинацию 2048 года, что для этого ввода будет trueили, yesили 1или любым другим способом, будет указывать на положительный результат.

Для тех , кто не знаком с игрой, вот простое объяснение: полномочия двух расположены на сетке, как это: [2] [2]. Плитки можно перемещать в любом направлении, и если встречаются две одинаковые плитки, они становятся следующей степенью двойки (поэтому [2] [2]при перемещении влево или вправо становится [4]). Или вы можете просто попробовать игру здесь .

Что означает «хорошая комбинация 2048»? Это означает любое число, которое, если бы оно было в игре «2048», могло бы быть объединено в одно число. (Ноль означает пустой пробел , и при необходимости его можно проигнорировать.) Обратите внимание, что числа могут состоять из нескольких цифр! Однако числа не должны меняться между ходами. Вот несколько примеров / тестовых случаев («Хорошее» означает хорошую комбинацию, а «Плохое» означает плохое):

• Хорошо: 8224 (8224 -> 844 -> 88 -> 16)
• Хорошо: 2222 (2222 -> 44 -> 8)
• Хорошо: 22048 (22048 -> 448 -> 88 -> 16)
• Плохо: 20482 (нельзя комбинировать внешние 2, а также нельзя комбинировать 2048 и 2)
• Хорошо: 20482048 (20482048 -> 4096)
• Плохо: 210241024 (210241024 -> 22048, но теперь это [2] [2048] и не может быть объединено, так как числа не могут меняться между ходами)
• Хорошо: 2048 (это уже одно число)
• Плохо: 2047 (это не степень 2)
• Плохо: 11 (в игре нет 1)
• Хорошо: 000040000000 (нули - это пустые места)

Разные правила:

• Входные данные могут быть откуда угодно, например, STDIN, аргумент функции, файл и т. Д.
• Вывод также может быть где угодно, например, STDOUT, возвращаемое значение функции, файл и т. Д.
• Не обращайте внимания на размер сетки - 22222222все равно выведите true.
• Число не является максимальным для того, что может быть числом s, если оно является степенью двойки. Поэтому возможные числа - это любая степень двух, больше 0.
• Для тех, кто обеспокоен тем, что нули вызывают двусмысленность, это не так. Например, 22048может быть проанализирован как [2] [2048]или [2] [2] [0] [4] [8]. Первый не работает, но второй работает, поэтому он должен вывести true.
• Это код-гольф , поэтому выиграет самый короткий код в байтах!

GolfScript, 137 символов

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

Ввод должен быть дан на STDIN. Выход 0/ 1для плохих / хороших чисел. Большая часть кода необходима для анализа возможных входных данных.

Эта более короткая версия (113 символов) выполняет простой сдвиговый тест, который не будет работать правильно для ввода, как 224422.

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

Все тестовые случаи можно проверить онлайн .

Python: 457 422 символов

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

Функция f (s) получает строку цифр и выдает соответственно «хорошо» или «плохо». Я решил не использовать 0 в качестве пробелов, потому что пробелы не имеют смысла в игре, и они создают неоднозначность при разборе строк (это 22048 хорошо или плохо?). Используются только числа до 2048, но это можно изменить без добавления символов. По цене 10 символов или около того я также могу распечатать все шаги объединения чисел. И я понимаю, что этот код еще не в гольфе; не волнуйтесь, поправки идут.

Haskell: 285 254 253 237 230 227

использование - просто загрузите его в ghci и передайте строку в h.

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

Код:

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)

Комментарий: iэто проверка, является ли число степенью 2, это будет переигрываться языками с немного изменяющимся тоном. %рекурсивно генерирует все разборы, которые являются списками степеней 2 или 0. cсворачивает тайлы. lрекурсивно проверяет, являются ли плитки разборными слева или хорошо. gпроверяет, являются ли плитки разборными слева или справа. Число плиток не ограничено - например, h ((show (2^200))++(show (2^200)))возвращает значение true для 2 плиток с пометкой «1606938044258990275541962092341162602522202993782792835301376».

Отредактировано, чтобы исправить ошибку, из-за которой она не правильно свернула «88222288888» вправо, но также нашла больше возможностей для игры в гольф.

Perl, 175-336 байт

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}

Сохраняя только основные вещи в целости:

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

ооо .. 1 .. приятно ..

2

оооо ... 2 ... красиво ...

22

оооо ... 22 ... 4 ... красиво ...

42

ооо .. ничего ..

422

ооо .. 422 .. 44 .. 8 .. приятно ..

322

ой. ничего.

336

ой. ничего.

4224

ооо .. ничего ..

4228

ооо .. 4228 .. 448 .. 88 .. 16 .. красиво ..

16022481602248

ооо .. 1604481602248 .. 16088160448 .. 1601616088 .. 3216016 .. 3232 .. 64 .. приятно ..

[ 64 и 256 приводят к некоторым плохо разрешимым неоднозначностям, с которыми жадное сопоставление не может справиться ... но это хороший счетчик байтов. ]

2048

оооо ... 2048 ... хорошо ...

Delphi 572 582 персонажа

Отредактированный код, предел установлен на 2 ^ 30, поэтому он не будет превышать значение MaxInt в Delphi.

Golfed

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.

Ungolfed

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.

РЕДАКТИРОВАТЬ

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

Для других, кому тоже любопытно, сделайте тест тоже;)

Но хорошо, вот результаты:
20736 combinations were tested and 1166 were great combinations

Я должен сказать комбинации с 3 - мя или более нулей были пропущены (имеет смысл правильно?)
Комбинация почти уникальна, то есть комбинации 2248, 8224, 8422и 4228все были подсчитана как большая комбинация.

Mathematica - 218 байт

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

Безголовая версия:

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` берется из этого вопроса .

Это решение обрабатывает произвольные размеры сетки и произвольно большие числа.

Вот 195-байтовая версия, которая работает так же, как и в реальной игре, только с 4 тайлами (так и f[22222222]есть 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}]&

где я заменил

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

с

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

Хаскелл - 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

fэто функция. Примеры:

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

Небольшое объяснение:
pвозвращает все способы разбить список.
qфильтрует те, которые состоят только из степеней 2 (исключая 1, но включая 0).
cпытается свернуть строку.
rвыполняет итерацию вправо и влево до тех пор, пока не останется только 1 элемент или строка не может быть изменена.