14
\$\begingroup\$

Background

Very skilled card handlers are capable of a technique whereby they cut a deck perfectly in half, then perfectly interleave the cards. If they start with a sorted deck and perform this technique flawlessly 52 times in a row, the deck will be restored to sorted order. Your challenge is to take a deck of cards an integer array and determine whether it can be sorted using only Faro shuffles.

Definition

Mathematically, a Faro shuffle is a permutation on 2 n elements (for any positive integer n) which takes the element in position i (1-indexed) to position 2 i (mod 2 n+1). We would also like to be able to handle odd-length lists, so in that case, just add one element to the end of the list (a Joker, if you have one handy) and Faro shuffle the new list as above, but ignore the added dummy element when checking the list's order.

Goal

Write a program or function that takes a list of integers and returns or outputs  a truthy if some number of Faro shuffles would cause that list to be sorted in nondescending order (even if that number is zero--small lists should give a truthy). Otherwise,  return or output a falsy.

Examples

[1,1,2,3,5,8,13,21]  => True
[5,1,8,1,13,2,21,3] => True
[9,36,5,34,2,10,1] => True
[1,0] => True
[0] => True
[] => True
[3,2,1] => True
[3,1,2] => False
[9,8,7,6,5,4,3,2,1,0] => True
[9,8,7,6,5,4,3,2,0,1] => False
[3,1,4,1,5,9,2,6,9] => False
[-1,-1,-1,-2] => True

Scoring

This is so shortest source in bytes wins.

Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ To avoid confusion with any fellow card handlers, it should be noted that there are two kinds of Faro shuffles. An in-shuffle and an out-shuffle. The method described here is an in-shuffle. Interestingly, it takes only 8 out-shuffles to return a deck to its original order. More Info \$\endgroup\$
    – BrainSteel
    Dec 12, 2015 at 15:22
  • \$\begingroup\$ Isn't this just "in-shuffle N+1 times and see if any of the lists along the way are sorted"? \$\endgroup\$
    – lirtosiast
    Dec 12, 2015 at 16:16
  • \$\begingroup\$ Actually n times is sufficient, because doing it 2n times is guaranteed to find all possible permutations, but you'll get at least one of either ascending or descending order in the first n. \$\endgroup\$
    – quintopia
    Dec 12, 2015 at 16:20
  • 1
    \$\begingroup\$ Related. Related. \$\endgroup\$
    – Martin Ender
    Dec 12, 2015 at 16:32
  • 1
    \$\begingroup\$ doesnt the first element always stay in the first position? \$\endgroup\$
    – Eumel
    Dec 13, 2015 at 16:28

2 Answers 2

Reset to default
3
\$\begingroup\$

Pyth - 26 25 24 bytes

Uses cumulative reduce to apply Faro shuffle multiple times and keep all the results. Then, it maps through it and checks if they are invariant under sorting, then uses sum to check is any are true. Returns a positive or zero.

smSI-db.usC_c2NQsC.tc2Qb

Test Suite.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

MATL, 41 bytes

itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx

The output is 1 or 0.

Explanation

i              % get input array
tn2\           % is size odd?
?              % if that's the case
  YNh          % concat NaN at the end
]              % end if
tn             % get size of input array
t1+:           % vector 1:n+1, where n is input size, so loop will be entered even with []
"              % for loop
  x[]2e!PY)    % delete result from previous iteration and do the shuffling
  ttZN~)       % remove NaN, if there's any
  tS=A         % check if array is sorted
  t.           % copy the result. If true, break loop
]              % end for
wx             % remove unwanted intermediate result

Example

>> matl itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx
> [1,1,2,3,5,8,13,21]
1
Improve this answer
\$\endgroup\$

Your Answer

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

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