Kürzlich habe ich eine Frage zu Diffy-Spielen gepostet, die unbeantwortet geblieben ist. Das ist in Ordnung, die Frage ist wirklich schwierig, aber ich möchte eine einfachere Frage zu Diffy-Spielen stellen, damit wir den Ball ins Rollen bringen können.

Wie funktioniert Diffy?

Von Find Diffy Games kopiert

Das Diffy-Spiel funktioniert wie folgt: Sie beginnen mit einer Liste nicht negativer Ganzzahlen, die wir in diesem Beispiel verwenden werden

3 4 5 8

Dann nehmen Sie die absolute Differenz zwischen benachbarten Zahlen

 (8)  3   4   5   8
    5   1   1   3

Dann wiederholst du. Sie wiederholen, bis Sie feststellen, dass Sie in eine Schleife eingetreten sind. Und dann fängt das Spiel in der Regel wieder von vorne an.

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

Die meisten Spiele enden in einer Folge von Nullen, was als Verlust betrachtet wird, aber einige wenige Spiele bleiben in größeren Schleifen stecken.

Aufgabe

Bestimmen Sie anhand des Anfangszustands eines Diffy-Spiels, ob das Spiel schließlich einen Zustand aller Nullen erreicht. Sie sollten für jeden der beiden Zustände einen Wert für Wahr oder Falsch ausgeben. Was was entspricht ist egal.

Ziel ist es, die Anzahl der Bytes in Ihrer Quelle zu minimieren.

Pyth, 6 Bytes

suaV+e

Testsuite

Dieses Programm ist sehr höflich. 0 (falsch) bedeutet alle Nullen, alles andere (wahr) bedeutet nicht alle Nullen.

Wie es funktioniert:

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 Bytes

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

Reine Funktion, die eine Liste nichtnegativer Ganzzahlen als Eingabe und Rückgabe von Trueoder verwendet False.

Abs[#-RotateLeft@#]&ist eine Funktion, die eine Runde des schwierigen Spiels ausführt. (Technisch gesehen soll es sein RotateRight, aber die ultimative Antwort ist nicht betroffen, und hey, freies Byte) . So Nest[...,#,R]führt eine RRunden des Diffy Spiels, und dann 1>Max@feststellt, ob das Ergebnis nur aus Nullen bestehen.

Woher wissen wir, wie viele verschiedene Spielrunden wir machen Rmüssen? Wenn mder größte Wert in der Eingabe ist, beachten Sie, dass wir niemals eine ganze Zahl erzeugen, die größer ist als die mAnzahl der Runden, die wir durchführen. Die Gesamtzahl der Listen der Länge lvon nichtnegativen ganzen Zahlen, die alle durch begrenzt sind, mist (m+1)^l. Wenn wir also (m+1)^lRunden des schwierigen Spiels durchführen, haben wir bis dahin garantiert zweimal eine Liste gesehen und befinden uns somit im periodischen Teil des Spiels. Insbesondere endet das Spiel nur dann mit allen Nullen, wenn das Ergebnis der (m+1)^lRunden des Spiels die Liste aller Nullen ist. Dieser Ausdruck Max[1+#]^Tr[1^#]berechnet.

Jelly , 13 Bytes

Ṁ‘*L
ṙ1ạ
ÇÑ¡Ṁ

Gibt 0 (falsch) aus, wenn der Zustand "Alle Nullen" erreicht wird, andernfalls wird ein wahrer Wert (eine positive Ganzzahl) zurückgegeben.

Probieren Sie es online!

Verwendet die Beobachtung zuerst von Greg Martin gemacht , dass die Zahlen in der Matrix können niemals die Domäne verlassen [0, m] wobei m das maximale Element in der Eingabe ist, so durchführt (m + 1) ^l Runden wo l die Länge ist der Eingang genügen.

Wie?

Ṁ‘*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 Bytes

Gibt 0 für alle Nullen und einen positiven ganzzahligen Wert für true aus

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

Online Version

Erweitert

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 Bytes

Gibt Null für ein Spiel zurück, das mit allen Nullen endet, andernfalls eine positive Zahl.

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

nutzt die gleiche Tatsache von Greg Martin und verwendet das eingebaute Diff, um das Diffy zu machen

Röda , 80 Bytes

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

Probieren Sie es online!

Ungolfed:

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 Bytes

Gibt 1 zurück, wenn es mit Nullen endet, andernfalls mit 0 .

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

Probieren Sie es online!

Erläuterung

Verwendet die obere Schranke von Runden: max(input)*len(input)erklärt durch xnor im Kommentarbereich.

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 Bytes

Gibt 0(was effektiv falsein J ist) für ein entartetes Spiel zurück, das mit allen Nullen endet. Gibt 1( true) zurück, wenn die n-te Iteration eine Zahl ungleich Null enthält, wobei n gleich der größten Ganzzahl in der ursprünglichen Sequenz multipliziert mit der Länge der Liste ist. Siehe Greg Martins Antwort, in der erklärt wird, warum dies wahr ist.

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

Übersetzung:

• Was ist das Zeichen *
• vom größten Wert >./
• Wenn Sie Folgendes so oft wie möglich wiederholen ^:( )
• Die Länge der Liste #multipliziert mit *dem größten Wert in der Liste >./:
  • nimm den absoluten Wert |&von
  • der Unterschied zwischen der Liste (- )und
  • Die Liste wurde um eins gedreht 1&|.

Beispiele:

   *>./|&(-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 Bytes

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)

Erläuterung

Rekursive Funktion, die sich selbst aufruft, solange der Zähler (der mit dem Maximalwert in der Liste plus eins hoch der Länge der Liste [ = (max + 1)**length] beginnt ) nicht Null ist. Bei jedem Aufruf wird der Zähler dekrementiert, und wenn er Null erreicht, werden alle Elemente in der Liste gegen Null geprüft. Wenn alle gleich Null sind, kehrt das Programm zurück trueund falseansonsten.

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

Wenn Sie Eingaben über HTTP get vornehmen, werden z. B. ?3&4&5&8einige Bytes gespart.

Gibt 1 aus, wenn alle Nullen erreicht sind oder sonst nichts.

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

Übernimmt die Liste der Argumente über die Kommandozeile. Ich habe das Gefühl, dass dies noch weiter verbessert werden kann (siehe @Titus).

Python 3.6, 101 Bytes

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)

Nimmt ein Tupel von Zahlen und gibt False zurück, wenn es mit Nullen endet, und True, wenn es eine Schleife ausführt.

JavaScript (ES6), 84 83 Bytes

Gibt truefür ein Spiel zurück, das mit allen Nullen endet, falseansonsten.

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)

Prüfung

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