Ostatnio napisałem na pytanie o grach Diffy który upadł bez odpowiedzi. To dobrze, pytanie jest naprawdę trudne, ale chciałbym zadać łatwiejsze pytanie na temat gier Diffy, abyśmy mogli uruchomić piłkę.

Jak działa Diffy

Skopiowano z Find Diffy Games

Gra Diffy działa w następujący sposób: Zaczynasz od listy liczb całkowitych nieujemnych, w tym przykładzie użyjemy

3 4 5 8

Następnie bierzesz absolutną różnicę między sąsiednimi liczbami

 (8)  3   4   5   8
    5   1   1   3

Potem powtarzasz. Powtarzaj, dopóki nie uświadomisz sobie, że wszedłeś w pętlę. A potem ogólnie gra zaczyna się od nowa.

3 4 5 8
5 1 1 3
2 4 0 2
0 2 4 2
2 2 2 2
0 0 0 0
0 0 0 0

Większość gier kończy się ciągiem zer zerowych, co uznaje się za stan utraty, ale kilka rzadkich gier utknie w większych pętlach.

Zadanie

Biorąc pod uwagę stan początkowy gry Diffy, określ, czy gra ostatecznie osiąga stan wszystkich zer. Powinieneś wypisać wartość Prawdy lub Falsy dla każdego z dwóch stanów. Który odpowiada, co nie ma znaczenia.

Celem jest zminimalizowanie liczby bajtów w źródle.

Pyth, 6 bajtów

suaV+e

Zestaw testowy

Ten program jest bardzo uprzejmy. 0 (fałsz) oznacza wszystkie zera, wszystko inne (prawda) oznacza nie wszystkie zera.

Jak to działa:

suaV+e
suaV+eGGGQ    Variable introduction.
 u       Q    Apply the following function repeatedly to its previous result,
              starting with the input. Stop when a value occurs which has
              occurred before.
  aV          Take the absolute differences between elements at the same indices of
        G     The previous list and
    +eGG      The previous list with its last element prepended.
s             The repeated value is returned. Sum its entries. This is zero (falsy)
              if and only if the entries are all zero.

Mathematica, 52 bajty

1>Max@Nest[Abs[#-RotateLeft@#]&,#,Max[1+#]^Tr[1^#]]&

Czysta funkcja przyjmująca listę nieujemnych liczb całkowitych jako dane wejściowe i zwracające Truelub False.

Abs[#-RotateLeft@#]&to funkcja, która wykonuje jedną rundę gry diffy. (Technicznie tak powinno być RotateRight, ale ostateczna odpowiedź pozostaje nienaruszona, a hej, wolny bajt.) Więc Nest[...,#,R]wykonuje Rrundy gry diffy, a następnie 1>Max@wykrywa, czy wszystkie wyniki są zerami.

Skąd wiemy, ile rund różni Rsię robić? Jeśli mjest to największa wartość na wejściu, zauważ, że nigdy nie wygenerujemy liczby całkowitej większej niż mbez względu na to, ile rund wykonamy. Łączna liczba list długości lnieujemnych liczb całkowitych wszystkich ograniczona mjest przez (m+1)^l. Jeśli więc przeprowadzimy (m+1)^lrundę gry diffy, gwarantujemy, że do tego czasu zobaczymy kilka list, a zatem będziemy w okresowej części gry. W szczególności gra kończy się zerami tylko wtedy, gdy wynikiem (m+1)^lrund jest lista wszystkich zer. To wyrażenie jest tym, co się liczy Max[1+#]^Tr[1^#].

Galaretka , 13 bajtów

Ṁ‘*L
ṙ1ạ
ÇÑ¡Ṁ

Zwraca 0 (falsey), jeśli zostanie osiągnięty stan zerowy, w przeciwnym razie zwracana jest prawdziwa wartość (dodatnia liczba całkowita).

Wypróbuj online!

Wykorzystuje spostrzeżenie poczynione po raz pierwszy przez Grega Martina, że liczby w tablicy nie mogą nigdy opuścić domeny [0, m], gdzie m jest maksymalnym elementem na wejściu, więc wykonanie (m + 1) ^l rund, gdzie l jest długością wejścia wystarczać.

W jaki sposób?

Ṁ‘*L - Link 1, number of rounds to perform: list a
Ṁ    - maximum of a
 ‘   - incremented
   L - length of a
  *  - exponentiate

ṙ1ạ - Link 2, perform a round: list x
ṙ1  - rotate x left by 1
  ạ - absolute difference (vectorises) with x

ÇÑ¡Ṁ - Main link: list a
  ¡  - repeat:
Ç    -     the last link (2) as a monad
 Ñ   -     the next link (1) as a monad times
   Ṁ - return the maximum of the resulting list

PHP, 144 bajtów

wypisz 0 dla wszystkich zer i dowolną dodatnią liczbę całkowitą dla true

<?for($r[]=$_GET[0];!$t;){$e=end($r);$e[]=$e[$c=0];for($n=[];++$c<count($e);)$n[]=abs($e[$c-1]-$e[$c]);$t=in_array($n,$r);$r[]=$n;}echo max($n);

Wersja online

Rozszerzony

for($r[]=$_GET;!$t;){
    $e=end($r);  # copy last array
    $e[]=$e[$c=0]; # add the first item as last item
    for($n=[];++$c<count($e);)$n[]=abs($e[$c-1]-$e[$c]); # make new array
    $t=in_array($n,$r); # is new array in result array
    $r[]=$n; # add the new array
}
echo max($n); # Output max of last array

R (3.3.1), 87 bajtów

Zwraca zero dla gry kończącej się wszystkimi zerami, a w przeciwnym razie liczbę dodatnią.

z=scan();sum(Reduce(function(x,y)abs(diff(c(x,x[1]))),rep(list(z),max(z+1)^length(z))))

wykorzystuje ten sam fakt Grega Martina i używa wbudowanego mechanizmu różnicowego, aby wykonać różnicę

Röda , 80 bajtów

f l...{x=[{peek a;[_];[a]}()|slide 2|abs _-_];[sum(x)=0]if[x in l]else{x|f*l+x}}

Wypróbuj online!

Nie golfowany:

function f(l...) { /* function f, variadic arguments */
    x := [ /* x is a list of */
        { /* duplicate the first element of the stream to the last position */
            peek a /* read the first element of the stream */
            [_]    /* pull all values and push them */
            [a]    /* push a */
        }() |
        slide(2) | /* duplicate every element except first and last */
        abs(_-_)   /* calculate the difference of every pair */
    ]
    /* If we have already encountered x */
    if [ x in l ] do
        return sum(x) = 0 /* Check if x contains only zeroes */
    else
        x | f(*l+x) /* Call f again, with x appended to l */
    done
}

05AB1E , 13 bajtów

Zwraca 1, jeśli kończy się zerami, a 0 w przeciwnym razie.

Z¹g*F¤¸ì¥Ä}_P

Wypróbuj online!

Wyjaśnienie

Wykorzystuje górną granicę rund: max(input)*len(input)wyjaśnione przez xnor w sekcji komentarzy.

Z              # get max(input)
 ¹g            # get length of input
   *           # multiply
    F          # that many times do:
     ¤         # get the last value of the current list (originally input)
      ¸        # wrap it
       ì       # prepend to the list
        ¥      # calculate deltas
         Ä     # calculate absolute values
          }    # end loop
           _   # negate each (turns 0 into 1 and everything else to 0)
            P  # calculate product

J, 22 bajty

Zwraca 0(która jest faktycznie falsew J) dla zdegenerowanej gry kończącej się wszystkimi zerami. Zwraca 1( true), jeśli n-ta iteracja zawiera niezerową liczbę, gdzie n jest równe największej liczbie całkowitej w oryginalnej sekwencji pomnożonej przez długość listy. Zobacz odpowiedź Grega Martina wyjaśniającą, dlaczego to prawda.

*>./|&(-1&|.)^:(#*>./)

Tłumaczenie:

• Jaki jest znak *
• o największej wartości >./
• gdy iterujesz następujące liczby razy ^:( )
• długość listy #pomnożona przez *największą wartość na liście >./:
  • Wartość bezwzględna |&z
  • różnica między listą (- )a
  • lista obrócona o jeden 1&|.

Przykłady:

   *>./|&(-1&|.)^:(#*>./) 1 1 0
1
   *>./|&(-1&|.)^:(#*>./) 42 42 41
1
   *>./|&(-1&|.)^:(#*>./) 3 4 5 8
0
   *>./|&(-1&|.)^:(#*>./) 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 1
0

JavaScript (ES6), 95 92 90 bajtów

f=(a,b=(Math.max(...a)+1)**(c=a.length))=>b?f(a.map((v,i)=>v-a[++i%c]),b-1):a.every(v=>!v)

Wyjaśnienie

Funkcja rekurencyjna, która wywołuje się tak długo, jak długo licznik (który zaczyna się od maksymalnej wartości na liście powiększonej o potęgę długości listy [ = (max + 1)**length]) nie jest równy zero. Przy każdym wywołaniu licznik jest zmniejszany, a gdy osiągnie zero, wszystkie elementy na liście są sprawdzane względem zera. Jeśli wszystkie są równe zero, program powraca truei falseinaczej.

PHP, 123 115

for($a=$_GET,$b=[];!in_array($a,$b);){$b[]=$c=$a;$c[]=$c[0];foreach($a as$d=>&$e)$e=abs($e-$c[$d+1]);}echo!max($a);

przyjmowanie danych wejściowych przez HTTP get np. ?3&4&5&8oszczędza kilka bajtów.

Drukuje 1, jeśli osiągnie wszystkie zera lub nic innego.

for($e=$argv,$r=[];!in_array($e,$r);$q=$e[0]){$e[0]=end($e);$r[]=$e;foreach($e as$k=>&$q)$q=abs($q-$e[$k+1]);}echo!max($e);

pobiera listę argumentów z wiersza poleceń. Mam wrażenie, że można grać w golfa jeszcze bardziej (patrząc na @Titus).

Python 3.6, 101 bajtów

def f(t):
 x={}
 while x.get(t,1):x[t]=0;t=(*(abs(a-b)for a,b in zip(t,t[1:]+t[:1])),)
 return any(t)

Pobiera krotkę liczb i zwraca False, jeśli kończy się na zera, i True, jeśli się zapętla.

JavaScript (ES6), 84 83 bajty

Zwraca truegrę zakończoną wszystkimi zerami, w falseprzeciwnym razie.

f=(a,k=a)=>k[b=a.map((n,i)=>Math.abs(n-a[(i||a.length)-1]))]?!+b.join``:f(k[b]=b,k)

Test

f=(a,k=a)=>k[b=a.map((n,i)=>Math.abs(n-a[(i||a.length)-1]))]?!+b.join``:f(k[b]=b,k)

console.log(f([3,4,5,8])); // ends in zeros
console.log(f([1,0,1]));   // does not end in zeros
console.log(f([7]));       // ends in zeros