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.


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.

  • 1
    \$\begingroup\$ The task wording seems to imply that any game that does not reach a state of all zeroes is therefore periodic. Earlier, periodic is defined as including the initial state in the repeated sequence. Does this mean that any sequence eventually reaches either all zeroes or the initial state? \$\endgroup\$ Apr 12, 2017 at 18:06
  • 3
    \$\begingroup\$ No: adding a positive constant to any nonzero periodic state results in a state that neither returns to itself nor goes to all zeros. For example, 1 1 0 is periodic, so 42 42 41 is such a state. \$\endgroup\$ Apr 12, 2017 at 18:11
  • 3
    \$\begingroup\$ Indeed, for the specific question being asked, one doesn't even need a notion of "periodic". "Eventually reaches a state of all zeros" is self-contained and clear. \$\endgroup\$ Apr 12, 2017 at 18:17
  • 2
    \$\begingroup\$ I've proven a partial characterization: If the list length n is odd, the game doesn't go to zero unless all the numbers are equal. If the length is a power of 2, it always goes to zero. \$\endgroup\$
    – xnor
    Apr 12, 2017 at 21:00
  • 3
    \$\begingroup\$ A bound of the number of steps to reach zero: A list with n elements and maximum m takes at most n * bit_length(m) steps. So, n*m is also an upper bound. A stronger upper bound is t(n) * bit_length(m), where t(n) is the largest power of 2 that's a factor of n. \$\endgroup\$
    – xnor
    Apr 12, 2017 at 21:10

13 Answers 13


Pyth, 6 bytes


Test suite

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

How it works:

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.
  • 6
    \$\begingroup\$ thats a suave solution \$\endgroup\$ Apr 13, 2017 at 10:16

Mathematica, 52 bytes


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.


Jelly, 13 bytes


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.


Ṁ‘*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
  • \$\begingroup\$ Could this be improved with xnor's bound? \$\endgroup\$
    – Wheat Wizard
    Apr 13, 2017 at 18:46
  • \$\begingroup\$ @WheatWizard I think it would cost a byte. (It might be possible to get a shorter method by collecting all results until they are not unique, but I have not found it). \$\endgroup\$ Apr 13, 2017 at 23:30

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


    $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
  • 1
    \$\begingroup\$ array_push ? But why ? \$\endgroup\$
    – Christoph
    Apr 13, 2017 at 8:30
  • 1
    \$\begingroup\$ also if using $_GET as input you should assume it contains a string. \$\endgroup\$
    – Christoph
    Apr 13, 2017 at 9:08
  • 1
    \$\begingroup\$ @Christoph ?0[0]=1&0[1]=1&0[2]=0 or ?0[]=1&0[]=1&0[]=0 is an array of strings but this does not matter. But you are right I could make it shorter with ?0=1&1=1&2=0 why not àrray_push` I am sure that you or Titus find better ways to short this. \$\endgroup\$ Apr 13, 2017 at 11:02
  • 1
    \$\begingroup\$ array_push($e,$e[$c=0]); is simply exactly the same as $e[]=$e[$c=0]; and you even use the syntax already ($r[]=$n). You already use max now so you should also replace end($r) with $n because $n is always equal to end($r) when the echo is executed. \$\endgroup\$
    – Christoph
    Apr 13, 2017 at 11:12
  • \$\begingroup\$ @Christoph It seems so that yesterday was not my day. Thank you. You have bring me to my idea for a new entry in the tips section \$\endgroup\$ Apr 13, 2017 at 11:44

R (3.3.1), 87 bytes

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


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

  • \$\begingroup\$ provided that xnor's bound is correct (from the comments), this could be two bytes shorter by using max(z)*length(z) but I'm not convinced of the correctness \$\endgroup\$
    – Giuseppe
    Apr 17, 2017 at 16:10

Jelly, 7 bytes


Try it online!

Outputs 0 (falsey) if it is degenerate, and 1 (truthy) if not

How it works

ṙ1ạµÐLẸ - Main link. Takes an array A on the left
   µ    - Group the links to the left into a monad f(A):
ṙ1      -   Rotate A one step to the left
  ạ     -   Take the absolute differences with A
    ÐL  - Repeatedly apply f(A) on A until reaching a fixed point
      Ẹ - Yield 0 if all 0s, else 1

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!


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 */
        x | f(*l+x) /* Call f again, with x appended to l */

05AB1E, 13 bytes

Returns 1 if it ends in zeroes and 0 otherwise.


Try it online!


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

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.



  • 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&|.


   *>./|&(-1&|.)^:(#*>./) 1 1 0
   *>./|&(-1&|.)^:(#*>./) 42 42 41
   *>./|&(-1&|.)^:(#*>./) 3 4 5 8
   *>./|&(-1&|.)^:(#*>./) 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 1
  • 1
    \$\begingroup\$ That is not what Greg Martin's claim is. However, xnor has better bounds in the comments above (but still not just the largest integer). The simplest is to multiply the greatest value with the length. \$\endgroup\$ Apr 13, 2017 at 4:40
  • \$\begingroup\$ Good catch. I wasn't paying enough attention. I'll fix the solution. \$\endgroup\$
    – Dane
    Apr 13, 2017 at 5:50

JavaScript (ES6), 95 92 90 bytes



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.


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


Python 3.6, 101 bytes

def f(t):
 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.


JavaScript (ES6), 84 83 bytes

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




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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.