# Professor at MIT needs an AP!

The 5-card magic trick involves a magician whose assistant gives them 4 shown cards and a hidden one, in this order, and the magician must guess the hidden one.

# WARNING: Solution below! Leave now or get spoiled with it.

### The solution

The trick here is that the five cards are given in a specific order!

$$\c_1,...,c_5\$$ are the 5 cards in the given order.

$$\x_n\$$ is the card number of $$\c_n\$$ in $$\NO=[\text{A,2,3,4,5,6,7,8,9,T,J,Q,K}]\$$ (number order).

$$\a+b\$$, where $$\a\$$ is a card number and $$\b\$$ is an integer, is equal to the card number $$\b\$$ steps to the right of $$\a\$$ in $$\NO\$$, wrapping to the beginning if necessary.

$$\s_n\$$ is the suit of $$\c_n\$$ in $$\SO=[\clubsuit,\diamondsuit,\heartsuit,\spadesuit]\$$ (suit order).

$$\a\circ b\$$, where $$\a\$$ is a card number and $$\b\$$ is a suit, denotes the card with card number $$\a\$$ and suit $$\b\$$.

$$\a, where $$\a\$$ and $$\b\$$ are cards, is true if $$\a\$$'s suit is to the left of $$\b\$$'s suit in $$\SO\$$, or their suits are equal and $$\a\$$'s card number is to the left of $$\b\$$'s card number in $$\NO\$$.

$$\a>b\$$, where $$\a\$$ and $$\b\$$ are cards, is true if $$\a is false.

$$\PI(a,b,c)\$$, where $$\a\$$, $$\b\$$ and $$\c\$$ are cards, is the permutation index of this ordering of them, specified by the table below:
$$\\begin{array}{|c|c|}\hline\text{Comparison}&PI(a,b,c)\\\hline ac>a&2\\\hline a>ba&3\\\hline acbb>c&6\\\hline\end{array}\$$

The solution to the 5-card magic trick is problem is:$$c_5=(x_1+PI(c_2,c_3,c_4))\circ s_1$$

### The challenge

So far, so good. However, doing the computation specified above is already asked for here. Instead, your challenge is, given the 5 cards in no specific order, to order them properly. This means that the first four cards in the output will represent the fifth. In other words, be the assistant. Requirements:

• $$\s_5=s_1\$$.
• $$\x_5=x_1+PI(c_2,c_3,c_4)\$$ (that is, this must be possible).

### Example

Let's consider the set 7H,2D,6D,5C,6C. First of all, we take the 25 pairs:

7H,7H 7H,2D 7H,6D 7H,5C 7H,6C
2D,7H 2D,2D 2D,6D 2D,5C 2D,6C
6D,7H 6D,2D 6D,6D 6D,5C 6D,6C
5C,7H 5C,2D 5C,6D 5C,5C 5C,6C
6C,7H 6C,2D 6C,6D 6C,5C 6C,6C


Then, we obviously remove the 5 pairs that contain the same card twice, they don't exist in a single deck:

      7H,2D 7H,6D 7H,5C 7H,6C
2D,7H       2D,6D 2D,5C 2D,6C
6D,7H 6D,2D       6D,5C 6D,6C
5C,7H 5C,2D 5C,6D       5C,6C
6C,7H 6C,2D 6C,6D 6C,5C


Afterwards, since the suits must be the same, different suits in a pair is a no-no:


2D,6D
6D,2D
5C,6C
6C,5C      

Finally, we check if it's possible to get from the first card to the second by adding at most 6, removing half of the remaining pairs:


2D,6D

5C,6C


Now we have the valid pairs: 2D,6D and 5C,6C. The first card of each pair is card 1, while the last is card 5.

We're going to go with 5C,6C here for easiness. The whole set is 7H,2D,6D,5C,6C, so, removing the 2 cards in the pair we've chosen, we have 7H,2D,6D. These cards will represent 6 - 5 = 1, so we have to order them like "min, mid, max". 7H > 2D < 6D < 7H, or simply 2D < 6D < 7H, so we now have 2D,6D,7H.

The last step is to put all of this together, so our result will be 5C,2D,6D,7H,6C.

### Clarifications

• You may use 10 instead of T.
• You may use one of ♠♥♦♣, ♤♡♢♧ or ♠♡♢♣ instead of CDHS, respectively.
• This is , the shortest code wins.

### Test cases

You can output one or more of the valid solutions included for each test case.

8S,TD,5C,QS,TS -> 8S,5C,QS,TD,TS
... 8S,TD,TS,5C,QS
... TS,5C,8S,TD,QS

JD,KH,4S,9D,8S -> 9D,KH,8S,4S,JD
... 4S,JD,KH,9D,8S

4H,4D,TH,KH,2C -> 4H,KH,4D,2C,TH
... TH,4D,2C,4H,KH
... KH,4D,TH,2C,4H

3S,KS,8S,KH,9H -> 9H,8S,KS,3S,KH
... 3S,KS,9H,KH,8S
... 8S,3S,9H,KH,KS
... KS,KH,9H,8S,3S

KH,TS,3C,7H,JD -> 7H,TS,JD,3C,KH

4C,KC,TD,JD,QS -> KC,JD,QS,TD,4C
... TD,4C,KC,QS,JD

AC,5H,8D,6D,8S -> 6D,AC,8S,5H,8D

AS,TC,3S,2H,9C -> 9C,2H,AS,3S,TC
... AS,9C,2H,TC,3S

4C,JS,AS,8H,JC -> JC,JS,AS,8H,4C
... JS,JC,4C,8H,AS

4H,QS,TH,QC,AC -> QC,4H,QS,TH,AC
... 4H,QS,QC,AC,TH


# Node.js, 190186 180 bytes

f=(a,p,g=c=>"A23456789TJQK".search(c)+10,[A,B,C,D,E]=a.sort(_=>p>>i++&1,i=0))=>A[k=1]!=E|[B,C,D].sort((a,b)=>k=k*2|a+g(a)>b+g(b))|(k^4)%6+1-(g(E)-g(A)+13)%13?f(a,-~p):a


Try it online!

## How?

### Identifying and comparing the card numbers

The helper function $$\g\$$ returns an index representing the number of a given card.

g = c => "A23456789TJQK".search(c) + 10


We add $$\10\$$ to force two digits for all entries, so that these indices can be safely sorted in lexicographical order. Therefore an Ace is $$\10\$$ and a King is $$\22\$$.

Given 2 cards $$\a\$$ and $$\b\$$ in "NS" format, we can compare them by suit first and number second with:

a + g(a) > b + g(b)


### Generating the permutations of the input

We recursively try all $$\120\$$ possible permutations of the input array $$\a\$$ by successively sorting it with different permutation seeds $$\p\$$. The cards are separately loaded into $$\A\$$, $$\B\$$, $$\C\$$, $$\D\$$ and $$\E\$$.

[A, B, C, D, E] = a.sort(_ => p >> i++ & 1, i = 0)


This code shows when each permutation is first encountered. It takes $$\699\$$ iterations to try all of them.

### Testing the suits

The first obvious test is to make sure that the first and last cards are of the same suit. We reject the permutation if they're not equal.

A[k = 1] != E // we also initialize k, which is used right after that


### Testing the distance

We compute the distance between the first card number and the last card number with:

(g(E) - g(A) + 13) % 13


Now comes the most tricky part. We have to test whether the order of the 3 other cards ($$\B\$$, $$\C\$$ and $$\D\$$) correctly describes this distance.

This test relies on the way the sort() algorithm of Node.js is working.

Assuming that the callback function of sort() is always returning a positive integer, Node.js will sort the array $$\[A,B,C]\$$ by applying these 3 steps:

1. compare $$\A\$$ with $$\B\$$
2. compare $$\A\$$ with $$\C\$$
3. compare $$\B\$$ with $$\C\$$

Let's consider the following code:

[1, 2, 3].sort((a, b) => k = k * 2 | (a > b), k = 1)


We have $$\A ($$\1<2\$$), $$\A ($$\1<3\$$) and $$\B ($$\2<3\$$). All comparisons processed in the callback function are falsy and $$\k\$$ is simply multiplied by $$\2^3\$$. So, we end up with $$\k=8\$$.

Now, if we do:

[3, 2, 1].sort((a, b) => k = k * 2 | (a > b), k = 1)


All comparisons are now thruthy, which generates the bitmask $$\k=15\$$.

Each permutation generates a unique bitmask, which is mapped to a unique distance:

 A, B, C | A>B | A>C | B>C | k  | distance
---------+-----+-----+-----+----+----------
1, 2, 3 |  0  |  0  |  0  |  8 |    1
1, 3, 2 |  0  |  0  |  1  |  9 |    2
2, 1, 3 |  1  |  0  |  0  | 12 |    3
2, 3, 1 |  0  |  1  |  1  | 11 |    4
3, 1, 2 |  1  |  1  |  0  | 14 |    5
3, 2, 1 |  1  |  1  |  1  | 15 |    6


Given $$\k\$$, we can convert it to the distance by doing:

$$d=((k\operatorname{xor}4)\bmod 6)+1$$

  k | xor 4 | mod 6 | +1
----+-------+-------+----
8 |   12  |   0   |  1
9 |   13  |   1   |  2
12 |    8  |   2   |  3
11 |   15  |   3   |  4
14 |   10  |   4   |  5
15 |   11  |   5   |  6


Putting everything together, we have the following test:

[B, C, D]
.sort((a, b) =>
k = k * 2 | a + g(a) > b + g(b)
)
| (k ^ 4) % 6 + 1
- (g(E) - g(A) + 13) % 13


# Python 3, 260 248 232 bytes

N="A23456789TJQK".find
D=lambda x,y="KC":(N(y)+~N(x))%13+15*abs(ord(x)-ord(y))
def f(l):a,e,b,c,d=[[x,y]+sorted({*l}-{x,y},key=D)for x in l for y in l if D(x,y)<6];print(a,*map(eval,"bbccddcdbdbcdcdbcb"[D(a,e)::6]),e)


Try it online!

-12 bytes thanks to Eric the Outgolfer
-14 bytes by removing a list comprehension

# Clean, 225220 209 bytes

import StdEnv,Data.List
n=['A23456789TJQK':n]

filter(\[[x,s],b,c,d,e]#[p,q,r:_]=map snd(sort(zip2[(elemIndices a n,b)\\[a,b]<-[b,c,d]][1..]))
=[snd(span((<>)x)n)!!(p+if(p>q)0if(q<r)(q+r)q),s]==e)o permutations


Try it online!

As a composed function, :: [[Char]] -> [[Char]], with some helpers.

Expanded:

n = ['A23456789TJQK': n] // infinitely repeating card number list

filter (...) o permutations // filter the permutations of the argument by ...
\[[x, s], b, c, d, e] // deconstruct each permutation via pattern matching
#[p, q, r: _] = ... // define p, q, r as ...
map snd (...) // the second component of every element in ...
sort (...) // the sorted list of ...
zip2 ... [1..] // pairs of ... and the numbers 1, 2, 3, ..
[... \\ [a, b] <- [b, c, d]] // ... for every pair of number a and house b in [b, c, d]
(elemIndices a n, b) // pair of the value of that card number and the house
= ... == e // check ... for equality against the last card
[..., s] // ..., paired with house s
snd (span ((<>) x) n) !! (...) // the card number ... places from x
p + ... // this is kinda obvious
if(p > q) 0 ... // if p is greater than q, zero, else ...
if(q < r) (q + r) q // if q is less than r, q + r, else q


# Ruby, 175 bytes

->a{g=->j{j.tr('ATJQKCHS','1:;<=)_z').sum}
e=b=a.sort_by{|i|g[i]}
4.times{|i|(d=g[b[i+1]]-g[b[i]])<13&&(a=b[i,2];e=d)}
[a[e/7],*(b-a).permutation.to_a[e<7?e-1:12-e],a[e/7-1]]}


Try it online!

A lambda function taking an array of cards as strings

Commented

->a{g=->j{j.tr('ATJQKCHS','1:;<=)_z').sum}
#helper function converts card to integer, ATJQK to 1:;<= and CHS to )_z then sum ascii values

e=b=a.sort_by{|i|g[i]}
#sort according to g. we declare 2 variables here in order to avoid undefined variable error at pre-interpretation check stage.

4.times{|i|(d=g[b[i+1]]-g[b[i]])<13&&(a=b[i,2];e=d)}
#compare each pair of values. if in same suit, store the pair of cards to a
#and the value difference to e. Loop exits with the last suitable pair stored

[a[e/7],*(b-a).permutation.to_a[e<7?e-1:12-e],a[e/7-1]]}
#return array containing the two cards of the same suit in the correct order
#with the correct permutation of the remaining cards (b-a) in the middle


# Jelly, 41 bytes

ØD;“TJQK”¤io2)1¦€µUḊỤ3R¤œ¿+""Om4%13E
Œ!ÇƇ


A monadic Link accepting a list of lists of characters returning a list of all valid arrangements in the same format.

Try it online! (footer formats the result as a grid to avoid the implicit smashing print as performed by the Link's code when run as a full program)

Or see a test-suite.

I have a sneaking suspicion another approach will be much more terse. I shall have to revisit this challenge later!

...hmm, I had another poke around and got another 41 byter (test):

O¹*@<74\$?€€29%⁽:0%⁴UµṪ_Ḣ%13Ḍ⁼Ụ3R¤œ¿Ɗ
Œ!ÇƇ