23
\$\begingroup\$

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.

\$\endgroup\$
  • 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\$ – trichoplax Apr 12 '17 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\$ – Greg Martin Apr 12 '17 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\$ – Greg Martin Apr 12 '17 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 '17 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 '17 at 21:10

12 Answers 12

27
\$\begingroup\$

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.
\$\endgroup\$
  • 6
    \$\begingroup\$ thats a suave solution \$\endgroup\$ – Martijn Vissers Apr 13 '17 at 10:16
14
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Could this be improved with xnor's bound? \$\endgroup\$ – Sriotchilism O'Zaic Apr 13 '17 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\$ – Jonathan Allan Apr 13 '17 at 23:30
2
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ array_push ? But why ? \$\endgroup\$ – Christoph Apr 13 '17 at 8:30
  • 1
    \$\begingroup\$ also if using $_GET as input you should assume it contains a string. \$\endgroup\$ – Christoph Apr 13 '17 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\$ – Jörg Hülsermann Apr 13 '17 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 '17 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\$ – Jörg Hülsermann Apr 13 '17 at 11:44
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\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 '17 at 16:10
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • 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\$ – Ørjan Johansen Apr 13 '17 at 4:40
  • \$\begingroup\$ Good catch. I wasn't paying enough attention. I'll fix the solution. \$\endgroup\$ – Dane Apr 13 '17 at 5:50
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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