23
2
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.
1The 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? – trichoplax – 2017-04-12T18:06:22.567
3No: 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, so42 42 41
is such a state. – Greg Martin – 2017-04-12T18:11:18.210Does the user have the right to choose "which way the differences are shifted"? For example, the starting state
3 4 5 8
goes to either5 1 1 3
or1 1 3 5
, depending on a predetermined wraparound convention; can we (consistently) choose our favorite of these two conventions? – Greg Martin – 2017-04-12T18:12:44.8101@GregMartin it does not effect the output which way you decide to shift. – Post Rock Garf Hunter – 2017-04-12T18:15:21.740
If "eventually periodic" is being used to mean the loop does not include the initial state, then all zeroes would be periodic (with period 1). Perhaps different terminology would reduce the potential for confusion. – trichoplax – 2017-04-12T18:16:50.233
3Indeed, 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. – Greg Martin – 2017-04-12T18:17:55.460
2I'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. – xnor – 2017-04-12T21:00:01.7233A bound of the number of steps to reach zero: A list with
n
elements and maximumm
takes at mostn * bit_length(m)
steps. So,n*m
is also an upper bound. A stronger upper bound ist(n) * bit_length(m)
, wheret(n)
is the largest power of 2 that's a factor ofn
. – xnor – 2017-04-12T21:10:20.913