# Is it a shuffle?

Yesterday I asked this question about riffle shuffles. It seems that yesterdays question was a bit too hard so this question is a related but much easier task.

Today you are asked to determine if a permutation is in fact a riffle shuffle. Our definition of riffle shuffle is adapted from our last question:

The first part of the shuffle is the divide. In the divide partition the deck of cards in two. The two subsections must be continuous, mutually exclusive and exhaustive. In the real world want to make your partition as close to even as possible, however in this challenge this is not a consideration, all partitions including ones that are degenerate (one partition is empty) are of equal consideration.

After they have been partitioned, the cards are spliced together in such a way that cards maintain their relative order within the partition they are a member of. For example, if card A is before card B in the deck and cards A and B are in the same partition, card A must be before card B in the final result, even if the number of cards between them has increased. If A and B are in different partitions, they can be in any order, regardless of their starting order, in the final result.

Each riffle shuffle can then be viewed as a permutation of the original deck of cards. For example the permutation

1,2,3 -> 1,3,2

is a riffle shuffle. If you split the deck like so

1, 2 | 3

we see that every card in 1,3,2 has the same relative order to every other card in it's partition. 2 is still after 1.

On the other hand the following permutation is not a riffle shuffle.

1,2,3 -> 3,2,1

We can see this because for all the two (non-trivial) partitions

1, 2 | 3
1 | 2, 3

there is a pair of cards that do not maintain their relative orderings. In the first partition 1 and 2 change their ordering, while in the second partition 2 and 3 change their ordering.

Given a permutation via any reasonable method, determine if it represents a valid riffle shuffle. You should output two distinct constant values one for "Yes, this is a riffle shuffle" and one for "No, this is not a riffle shuffle".

This is so answers will be scored in bytes with less bytes being better.

## Test Cases

1,3,2 -> True
3,2,1 -> False
3,1,2,4 -> True
2,3,4,1 -> True
4,3,2,1 -> False
1,2,3,4,5 -> True
1,2,5,4,3 -> False
5,1,4,2,3 -> False
3,1,4,2,5 -> True
2,3,6,1,4,5 -> False
• Can the output be inconsistent, but truthy / falsy in our language? Like (Python, where, among the integers only 0 is falsy) 0 for falsy but any integer in [1, +∞) for truthy? – Mr. Xcoder Jan 2 '18 at 16:50
• @Mr.Xcoder I don't like the truthy/falsy values because they are rather hard to define well. Answers should stick to the current rules. – Wheat Wizard Jan 2 '18 at 16:53
• Suggested test case: [3,1,4,2,5]. – Ørjan Johansen Jan 2 '18 at 17:28
• Can we take permutations of [0, ..., n-1] instead of [1, ..., n] as input? – Dennis Jan 2 '18 at 22:37

# JavaScript (ES6), 47 bytes

Takes input as an array of integers. Returns a boolean.

([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

### Test cases

let f =

([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

;[
[1,3,2      ],  // -> True
[3,2,1      ],  // -> False
[3,1,2,4    ],  // -> True
[2,3,4,1    ],  // -> True
[4,3,2,1    ],  // -> False
[1,2,3,4,5  ],  // -> True
[1,2,5,4,3  ],  // -> False
[3,1,4,2,5  ],  // -> True
[2,3,6,1,4,5]   // -> False
]
.forEach(a => console.log(JSON.stringify(a) + ' -> ' + f(a)))

### How?

The input array A is a valid riffle shuffle if it consists of at most two distinct interlaced sequences of consecutive integers.

The challenge rules specify that we're given a permutation of [1...N]. So we don't need to additionally check that the sorted union of these sequences actually results in such a range.

We use a counter x initialized to A[0] and a counter y initially undefined.

For each entry z in A, starting with the 2nd one:

• We check whether z is equal to either x+1 or y+1. If yes, we increment the corresponding counter.
• Else: if y is still undefined, we initialize it to z.
• Else: we make the test fail.