Is my Diffy game degenerate?

Question

Recently I posted a question about Diffy games which has gone unanswered. Thats fine, the question is really hard, but I would like to make an easier question about Diffy games so that we can get the ball rolling.

---

How Diffy works

Copied from Find Diffy Games

The Diffy game works like as follows: You start with a list of non-negative integers, in this example we will use

3 4 5 8

Then you take the absolute difference between adjacent numbers

 (8)  3   4   5   8
    5   1   1   3

Then you repeat. You repeat until you realize you have entered a loop. And then generally the game starts from the beginning again.

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

Most games end in a string of all zeros, which is considered to be a lose state, but a rare few games get stuck in larger loops.

---

Task

Given the starting state of a Diffy game determine whether or not the game eventually reaches a state of all zeros. You should output a Truthy or Falsy value for each of the two states. Which corresponds to which does not matter.

The goal is to minimize the number of bytes in your source.

Answer 1

Pyth, 6 bytes

suaV+e

Test suite

This program is very suave. 0 (falsy) means all zeroes, anything else (truthy) means not all zeroes.

How it works:

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.

Answer 2

Mathematica, 52 bytes

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

Pure function taking a list of nonnegative integers as input and returning True or False.

Abs[#-RotateLeft@#]& is a function that executes one round of the diffy game. (Technically it should be RotateRight, but the ultimate answer is unaffected, and hey, free byte.) So Nest[...,#,R] executes R rounds of the diffy game, and then 1>Max@ detects whether the result is all zeros.

How do we know how many diffy-game rounds R to do? If m is the largest value in the input, notice that we will never produce an integer larger than m no matter how many rounds we do. The total number of lists of length l of nonnegative integers all bounded by m is (m+1)^l. So if we carry out (m+1)^l rounds of the diffy game, we are guaranteed to have seen some list twice by then, and thus will be in the periodic part of the game. In particular, the game ends in all zeros if and only if the result of (m+1)^l rounds of the game is the all-zeros list. That expression is what Max[1+#]^Tr[1^#] computes.

Answer 3

Jelly, 13 bytes

Ṁ‘*L
ṙ1ạ
ÇÑ¡Ṁ

Outputs 0 (falsey) if the all zero state will be reached, otherwise a truthy value (a positive integer) is returned.

Try it online!

Uses the observation first made by Greg Martin that the numbers within the array may never leave the domain [0,m] where m is the maximal element in the input, so performing (m+1)^l rounds where l is the input's length will suffice.

How?

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

Answer 4

PHP, 144 Bytes

print 0 for all zero and any positive integer value for 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);

Online Version

Expanded

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

Answer 5

R (3.3.1), 87 bytes

Returns zero for a game ending in all zeros, and a positive number otherwise.

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

leverages the same fact by Greg Martin and uses the builtin diff to do the diffy-ing

Answer 6

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

Try it 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
}

Answer 7

05AB1E, 13 bytes

Returns 1 if it ends in zeroes and 0 otherwise.

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

Try it online!

Explanation

Uses the upper bound of rounds: max(input)*len(input) explained by xnor in the comment section.

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

Answer 8

J, 22 bytes

Returns 0 (which is effectively false in J) for a degenerate game ending in all zeros. Returns 1 (true) if the nth iteration contains a non-zero number, where n is equal to the largest integer in the original sequence multiplied by the length of the list. See Greg Martin's answer explaining why this is true.

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

Translation:

• What is the sign *
• of the greatest value >./
• when you iterate the following as many times as ^:( )
• the length of the list # multiplied by * the greatest value in the list >./:
  • take the absolute value |& of
  • the difference between the list (- ) and
  • the list rotated by one 1&|.

Examples:

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

Answer 9

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)

Explanation

Recursive function that calls itself as long as the counter (which starts at the maximum value in the list plus one to the power of the length of the list [= (max + 1)**length]) is not zero. On every call, the counter is decremented, and when it hits zero, all elements in the list are checked against zero. If they all equal zero, the program returns true, and false otherwise.

Answer 10

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

taking input via HTTP get e.g. ?3&4&5&8 saves a few bytes.

Prints 1 if it reaches all zeros or nothing otherwise.

---

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

takes the list of arguments via command line. I've got the feeling this can be golfed even further (looking at @Titus).

Answer 11

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)

Takes a tuple of numbers and returns False if it ends in zeros and True if it loops.

Answer 12

JavaScript (ES6), 84 83 bytes

Returns true for a game ending in all zeros, false otherwise.

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