Mind boggling card trick

Mind boggling card trick is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Matt Parker of the Stand Up Maths channel on you tube has a video of a card trick that creates a semblance of order from chaos.

The task is to simulate the trick in a way that mimicks the steps shown in the video.

1. Cards.

1. Create a pack of 52 cards, half red - half black.
2. Give the pack a good shuffle.

2. Deal from the randomised pack into three stacks.

1. Assemble the cards face down.
   1. Turn up the top card,
      1. if it is black then add the next card, unseen, to the black-stack.
      2. If it is red then instead add that next card, unseen, to the red-stack.
   2. Add the card you turned over to see what colour it was above, to the discard-stack.
      (You might optionally show these discard cards to give an idea of the randomness).
2. Repeat the above for the whole of the assembled pack.

3. Swap the same, random, number of cards between the two stacks.

1. Randomly choose the number of cards to swap.
2. Randomly choose that number of cards out of each stack to swap.
   (Without knowing those cards - they could be red or black cards from the stacks, we don't know).

4. Order from randomness?

1. Check the mathematician's assertion that: The number of black cards in the black pile equals the number of red cards in the red pile.

Show output on this page.

Factor

<lang factor>USING: accessors combinators.extras formatting fry generalizations io kernel math math.ranges random sequences sequences.extras ; IN: rosetta-code.mind-boggling-card-trick

SYMBOLS: R B ;

TUPLE: piles deck red black discard ;

initialize-deck ( -- seq )

   [ R ] [ B ] [ '[ 26 _ V{ } replicate-as ] call ] bi@ append
   randomize ;

<piles> ( -- piles )

   initialize-deck [ V{ } clone ] thrice piles boa ;
   

deal-step ( piles -- piles' )

   dup [ deck>> pop dup ] [ discard>> push ] [ deck>> pop ] tri
   B = [ over black>> ] [ over red>> ] if push ;
   

deal ( piles -- piles' ) 26 [ deal-step ] times ;

choose-sample-size ( piles -- n )

   [ red>> ] [ black>> ] bi shorter length [0,b] random ;

! Partition a sequence into n random samples in one sequence and ! the leftovers in another.

sample-partition ( vec n -- leftovers sample )

   [ 3 dupn ] dip sample dup
   [ [ swap remove-first! drop ] with each ] dip ;
   

perform-swaps ( piles -- piles' )

   dup dup choose-sample-size dup "Swapping %d\n" printf
   [ [ red>> ] dip ] [ [ black>> ] dip ] 2bi
   [ sample-partition ] 2bi@ [ append ] dip rot append
   [ >>black ] dip >>red ;
   

test-assertion ( piles -- )

   [ red>> ] [ black>> ] bi
   [ [ R = ] count ] [ [ B = ] count ] bi* 2dup =
   [ "Assertion correct!" ]
   [ "Assertion incorrect!" ] if print
   "R in red: %d\nB in black: %d\n" printf ;
   

main ( -- )

   <piles>                             ! step 1
   deal                                ! step 2
   dup "Post-deal state:\n%u\n" printf
   perform-swaps                       ! step 3
   dup "Post-swap state:\n%u\n" printf
   test-assertion ;                    ! step 4

MAIN: main</lang> A run:

Output:

Post-deal state:
T{ piles
    { deck V{ } }
    { red V{ B R B R R B B R R R R } }
    { black V{ R B R B B R B B R R R R R B B } }
    { discard
        V{ R B R B R B B B R R R B B B R B R R R R R R B R B R }
    }
}
Swapping 11
Post-swap state:
T{ piles
    { deck V{ } }
    { red V{ B R B B R R B R R R R } }
    { black V{ B R R B B R B R R R R B R B B } }
    { discard
        V{ R B R B R B B B R R R B B B R B R R R R R R B R B R }
    }
}
Assertion correct!
R in red: 7
B in black: 7

Another run:

Output:

Post-deal state:
T{ piles
    { deck V{ } }
    { red V{ R R R B B R B R R B } }
    { black V{ B R B B R B R B R R R R R R B R } }
    { discard
        V{ R R B R B B R B B R B R R B B R R R R R R R B R R B }
    }
}
Swapping 7
Post-swap state:
T{ piles
    { deck V{ } }
    { red V{ B R R R B R B B R B } }
    { black V{ R R B R R B R B B R R R R R B R } }
    { discard
        V{ R R B R B B R B B R B R R B B R R R R R R R B R R B }
    }
}
Assertion correct!
R in red: 5
B in black: 5

Go

<lang go>package main

import (

   "fmt"
   "math/rand"
   "time"

)

func main() {

   // Create pack, half red, half black and shuffle it.
   var pack [52]byte
   for i := 0; i < 26; i++ {
       pack[i] = 'R'
       pack[26+i] = 'B'
   }
   rand.Seed(time.Now().UnixNano())
   rand.Shuffle(52, func(i, j int) {
       pack[i], pack[j] = pack[j], pack[i]
   })

   // Deal from pack into 3 stacks.
   var red, black, discard []byte
   for i := 0; i < 51; i += 2 {
       switch pack[i] {
       case 'B':
           black = append(black, pack[i+1])
       case 'R':
           red = append(red, pack[i+1])
       }
       discard = append(discard, pack[i])
   }
   lr, lb, ld := len(red), len(black), len(discard)
   fmt.Println("After dealing the cards the state of the stacks is:")
   fmt.Printf("  Red    : %2d cards -> %c\n", lr, red)
   fmt.Printf("  Black  : %2d cards -> %c\n", lb, black)
   fmt.Printf("  Discard: %2d cards -> %c\n", ld, discard)

   // Swap the same, random, number of cards between the red and black stacks.
   min := lr
   if lb < min {
       min = lb
   }
   n := 1 + rand.Intn(min)
   rp := rand.Perm(lr)[:n]
   bp := rand.Perm(lb)[:n]
   fmt.Printf("\n%d card(s) are to be swapped.\n\n", n)
   fmt.Println("The respective zero-based indices of the cards(s) to be swapped are:")
   fmt.Printf("  Red    : %2d\n", rp)
   fmt.Printf("  Black  : %2d\n", bp)
   for i := 0; i < n; i++ {
       red[rp[i]], black[bp[i]] = black[bp[i]], red[rp[i]]
   }
   fmt.Println("\nAfter swapping, the state of the red and black stacks is:")
   fmt.Printf("  Red    : %c\n", red)
   fmt.Printf("  Black  : %c\n", black)

   // Check that the number of black cards in the black stack equals
   // the number of red cards in the red stack.
   rcount, bcount := 0, 0
   for _, c := range red {
       if c == 'R' {
           rcount++
       }
   }
   for _, c := range black {
       if c == 'B' {
           bcount++
       }
   }

   fmt.Println("\nThe number of red cards in the red stack     =", rcount)
   fmt.Println("The number of black cards in the black stack =", bcount)
   if rcount == bcount {
       fmt.Println("So the asssertion is correct!")
   } else {
       fmt.Println("So the asssertion is incorrect!")
   }

}</lang>

Output:

First sample run:

After dealing the cards the state of the stacks is:
  Red    : 15 cards -> [B R R R R B R B R B B R B B B]
  Black  : 11 cards -> [R B R B B R R B B B B]
  Discard: 26 cards -> [R R R R B B B B B B B R R R B B B R R R R R R B R R]

8 card(s) are to be swapped.

The respective zero-based indices of the cards(s) to be swapped are:
  Red    : [10  2 11 14 12  3  9  5]
  Black  : [ 7 10  3  0  5  8  6  1]

After swapping, the state of the red and black stacks is:
  Red    : [B R B B R B R B R R B B R B R]
  Black  : [B B R R B B B B R B R]

The number of red cards in the red stack     = 7
The number of black cards in the black stack = 7
So the asssertion is correct!

Second sample run:

After dealing the cards the state of the stacks is:
  Red    : 12 cards -> [B B R B R R R B B B R B]
  Black  : 14 cards -> [B R R R B R R B B R R B R R]
  Discard: 26 cards -> [R R B B B R R B B B R R R B B B R B B B R B R R R B]

2 card(s) are to be swapped.

The respective zero-based indices of the cards(s) to be swapped are:
  Red    : [ 1  6]
  Black  : [11 12]

After swapping, the state of the red and black stacks is:
  Red    : [B B R B R R R B B B R B]
  Black  : [B R R R B R R B B R R B R R]

The number of red cards in the red stack     = 5
The number of black cards in the black stack = 5
So the asssertion is correct!

Kotlin

Translation of: Go

<lang scala>// Version 1.2.61

import java.util.Random

fun main(args: Array<String>) {

   // Create pack, half red, half black and shuffle it.
   val pack = MutableList(52) { if (it < 26) 'R' else 'B' }
   pack.shuffle()

   // Deal from pack into 3 stacks.
   val red = mutableListOf<Char>()
   val black = mutableListOf<Char>()
   val discard = mutableListOf<Char>()
   for (i in 0 until 52 step 2) {
       when (pack[i]) {
           'B' -> black.add(pack[i + 1])
           'R' -> red.add(pack[i + 1])
       }
       discard.add(pack[i])
   }
   val sr = red.size
   val sb = black.size
   val sd = discard.size
   println("After dealing the cards the state of the stacks is:")
   System.out.printf("  Red    : %2d cards -> %s\n", sr, red)
   System.out.printf("  Black  : %2d cards -> %s\n", sb, black)
   System.out.printf("  Discard: %2d cards -> %s\n", sd, discard)

   // Swap the same, random, number of cards between the red and black stacks.
   val rand = Random()
   val min = minOf(sr, sb)
   val n = 1 + rand.nextInt(min)
   var rp = MutableList(sr) { it }.shuffled().subList(0, n)
   var bp = MutableList(sb) { it }.shuffled().subList(0, n)
   println("\n$n card(s) are to be swapped\n")
   println("The respective zero-based indices of the cards(s) to be swapped are:")
   println("  Red    : $rp")
   println("  Black  : $bp")
   for (i in 0 until n) {
       val temp = red[rp[i]]
       red[rp[i]] = black[bp[i]]
       black[bp[i]] = temp
   }
   println("\nAfter swapping, the state of the red and black stacks is:")
   println("  Red    : $red")
   println("  Black  : $black")

   // Check that the number of black cards in the black stack equals
   // the number of red cards in the red stack.
   var rcount = 0
   var bcount = 0
   for (c in red) if (c == 'R') rcount++
   for (c in black) if (c == 'B') bcount++
   println("\nThe number of red cards in the red stack     = $rcount")
   println("The number of black cards in the black stack = $bcount")
   if (rcount == bcount) {
       println("So the asssertion is correct!")
   }
   else {
       println("So the asssertion is incorrect!")
   }

}</lang>

Output:

First sample run:

After dealing the cards the state of the stacks is:
  Red    : 10 cards -> [R, R, B, R, R, B, B, R, R, R]
  Black  : 16 cards -> [B, B, R, R, R, R, B, R, R, B, R, B, B, R, R, B]
  Discard: 26 cards -> [R, B, B, B, R, R, B, B, B, R, B, B, B, B, R, B, R, B, R, R, R, R, B, B, B, B]

7 card(s) are to be swapped

The respective zero-based indices of the cards(s) to be swapped are:
  Red    : [3, 5, 6, 1, 4, 9, 7]
  Black  : [2, 0, 3, 15, 14, 12, 7]

After swapping, the state of the red and black stacks is:
  Red    : [R, B, B, R, R, B, R, R, R, B]
  Black  : [B, B, R, B, R, R, B, R, R, B, R, B, R, R, R, R]

The number of red cards in the red stack     = 6
The number of black cards in the black stack = 6
So the asssertion is correct!

Second sample run:

After dealing the cards the state of the stacks is:
  Red    : 11 cards -> [B, R, R, B, R, B, R, B, B, B, R]
  Black  : 15 cards -> [B, R, R, R, B, R, R, R, B, R, R, R, B, R, B]
  Discard: 26 cards -> [B, R, R, B, B, R, R, B, B, R, R, B, B, B, B, R, R, B, B, B, R, R, B, B, B, R]

3 card(s) are to be swapped

The respective zero-based indices of the cards(s) to be swapped are:
  Red    : [4, 2, 3]
  Black  : [0, 14, 2]

After swapping, the state of the red and black stacks is:
  Red    : [B, R, B, R, B, B, R, B, B, B, R]
  Black  : [R, R, B, R, B, R, R, R, B, R, R, R, B, R, R]

The number of red cards in the red stack     = 4
The number of black cards in the black stack = 4
So the asssertion is correct!

Python

The code is layed out to follow the task decription, leading to some deviations from the PEP8 guidelines <lang python>import random

1. 1. 1. Cards

n = 52 Black, Red = 'Black', 'Red' blacks = [Black] * (n // 2) reds = [Red] * (n // 2) pack = blacks + reds

1. Give the pack a good shuffle.

random.shuffle(pack)

1. 1. 2. Deal from the randomised pack into three stacks

black_stack, red_stack, discard = [], [], [] while pack:

   top = pack.pop()
   if top == Black:
       black_stack.append(pack.pop())
   else:
       red_stack.append(pack.pop())
   discard.append(top)

print('(Discards:', ' '.join(d[0] for d in discard), ')\n')

1. 1. 3. Swap the same, random, number of cards between the two stacks.
2. We can't swap more than the number of cards in a stack.

max_swaps = min(len(black_stack), len(red_stack))

1. Randomly choose the number of cards to swap.

swap_count = random.randint(0, max_swaps) print('Swapping', swap_count)

1. Randomly choose that number of cards out of each stack to swap.

def random_partition(stack, count):

   "Partition the stack into 'count' randomly selected members and the rest"
   sample = random.sample(stack, count)
   rest = stack[::]
   for card in sample:
       rest.remove(card)
   return rest, sample

black_stack, black_swap = random_partition(black_stack, swap_count) red_stack, red_swap = random_partition(red_stack, swap_count)

1. Perform the swap.

black_stack += red_swap red_stack += black_swap

1. 1. 4. Order from randomness?

if black_stack.count(Black) == red_stack.count(Red):

   print('Yeha! The mathematicians assertion is correct.')

else:

   print('Whoops - The mathematicians (or my card manipulations) are flakey')</lang>

A run.

Output:

(Discards: R B R R B B R R R B B B B R R R B R R B B B B R B R )

Swapping 11
Yeha! The mathematicians assertion is correct.

A second run:

Output:

(Discards: R B B R B B R B R R R B R R B B B B R R B R R B B R )

Swapping 2
Yeha! The mathematicians assertion is correct.

REXX

Programming notes:   This REXX version uses a neat trick that the Python entry uses:   instead of using a deck of
cards,   it just uses a "deck" of numbers.   Odd numbers represent red cards, even numbers represent black cards.
This could've been possibly simplified by using negative and positive numbers.

Also, code was added to perform any number of trials.   Code was also added to allow repeatability by specifying a
seed   value for the   random   BIF.

The size of the card deck can also be specified. <lang rexx>/*REXX pgm mimics a boggling card trick; separates cards into 3 piles based on color ···*/ parse arg trials # seed . /*obtain optional arguments from the CL*/ if trials== | trials=="," then trials= 500 /*Not specified? Then use the default.*/ if #== | #=="," then #= 52 /* " " " " " " */ if datatype(seed, 'W') then call random ,,seed /*if integer, use this as a RANDOM seed*/ ok=0 /*the number of "expected" good trials.*/

                        do trials               /*perform a number of trials to be safe*/
                        call create             /*odd numbers≡RED,  even numbers≡BLACK.*/
                        call shuffle            /*shuffle the deck a number of times.  */
                        call deal               /*put cards into three piles of cards. */
                        call swap               /*swap rand # of cards in  R & B  piles*/
                        call count              /*count #blacks in B, #reds in R  piles*/
                        end   /*trials*/        /*#: is the number of cards in the deck*/

pc= (100*ok/trials)'%' /*calculate the  % asserted correctly.*/ say "Correctness of the mathematician's assertion:" pc ' (out of' trials "trials)." exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ ?: return random(1, word( arg(1) #, 1) ) /*gen a random number from 1 ──► arg. */ create: @.=; do j=1 for #; @.j= j; end /*j*/; return isRed: return arg(1) // 2 /*if arg(1) is odd, the card is RED.*/ shuffle: do j=1 for #; x=?(); y=?(); parse value @.x @.y with @.y @.x; end; return /*──────────────────────────────────────────────────────────────────────────────────────*/ count: Rn=0; Bn=0; do j=1 for words(R); Rn=Rn+ isRed(word(R,j)) ; end

                                  do k=1  for words(B);  Bn=Bn+ (\isRed(word(B,k)));  end
        if Rn==Bn  then ok= ok+1;        return /*Was it a good trial?  Bump OK counter*/

/*──────────────────────────────────────────────────────────────────────────────────────*/ deal: R=; B=; D=; do j=1 for #%2 by 2 /*deal all the cards. */

                                  next= j+1;   card= @.next    /*obtain the next card. */
                                  if isRed(@.j)  then R=R card /*add to the  RED  pile?*/
                                                 else B=B card /* "   "  "  BLACK   "  */
                                  D= D @.j                     /* "   "  " discard  "  */
                                  end   /*j*/
        return                                                 /*discard pile not used.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/ swap: $= ?( min( words(R), words(B) ) ); Rc=; Bc= /*ensure we can swap $ cards.*/

                                  do $                    /*$:  is the number of swaps.*/
                                  R?= ?( words(R) )       /*a random card in  RED pile.*/
                                  B?= ?( words(B) )       /*"    "     "   " BLACK  "  */
   /* "reds"  to be swapped.*/    Rc= Rc word(R, R?);  R= delword(R, R?, 1)  /*del card*/
   /*"blacks"  "  "    "    */    Bc= Bc word(B, B?);  B= delword(B, B?, 1)  /* "    " */
                                  end   /*$*/
        R=R Bc;  B=B Rc;   return                         /*add swapped cards to piles.*/</lang>

output   when using the default inputs:

Correctness of the mathematician's assertion: 100%   (out of 500 trials).

Rust

Library: rand

<lang rust>extern crate rand; // 0.5.5 use rand::Rng; use std::iter::repeat;

1. [derive(Debug, Eq, PartialEq, Clone)]

enum Colour {

   Black,
   Red,

} use Colour::*;

fn main() {

   let mut rng = rand::thread_rng();
   
   //Create our deck.
   let mut deck: Vec<_> = repeat(Black).take(26)
       .chain(repeat(Red).take(26))
       .collect();
   
   rng.shuffle(&mut deck);
   
   let mut black_stack = vec![];
   let mut red_stack = vec![];
   let mut discarded = vec![];
   
   //Deal our cards.
   print!("Discarding:");
   while let (Some(card), Some(next)) = (deck.pop(), deck.pop()) {
       print!(" {}", if card == Black { "B" } else { "R" });
       match card {
           Red => red_stack.push(next),
           Black => black_stack.push(next),
       }
       discarded.push(card);
   }
   println!();
   
   // Choose how many to swap.
   let max = red_stack.len().min(black_stack.len());
   let num = rng.gen_range(1, max);
   println!("Exchanging {} cards", num);
   
   // Actually swap our cards.
   for _ in 0..num {
       let red = rng.choose_mut(&mut red_stack).unwrap();
       let black = rng.choose_mut(&mut black_stack).unwrap();
       std::mem::swap(red, black);
   }
   
   //Count how many are red and black.
   let num_black = black_stack.iter()
       .filter(|&c| c == &Black)
       .count();
   let num_red = red_stack.iter()
       .filter(|&c| c == &Red)
       .count();
       
   println!("Number of black cards in black stack: {}", num_black);
   println!("Number of red cards in red stack: {}", num_red);

}</lang>

Output:

Discarding: R R B B R R B R R B B B B B R R R B B B R R R B R R
Exchanging 5 cards
Number of black cards in black stack: 4
Number of red cards in red stack: 4

zkl

<lang zkl>cards:=[1..52].pump(List,"isEven","toInt").shuffle(); // red==1 stacks:=T(List(),List()); // black stack (0), red stack (1) blkStk,redStk := stacks; foreach card in (cards){ stacks[card].append(__cardWalker.next()) } println("Stacks:\n Black stack: ",blkStk,"\n Red stack: ",redStk);

numSwaps:=(1).random(1000); // do lots of swaps do(numSwaps){ blkStk.append(redStk.pop(0)); redStk.append(blkStk.pop(0)); } println("Post %d swaps:\n Black stack: %s\n Red stack: %s"

  .fmt(numSwaps,blkStk,redStk));

numBlack,numRed := blkStk.filter('==(0)).len(), redStk.filter().len(); if(numBlack==numRed)

  println("Agreed, black stack has same number of black cards \n  "
          "as red stack has number of red cards: ",numRed);

else println("Boo, differnt stack lenghts");</lang>

Output:

Stacks:
  Black stack: L(0,0,1,1,0,0,1,0,0,0,0)
  Red stack:   L(0,1,0,1,0,1,1,1,0,1,0,0,1,1,0)
Post 99 swaps:
  Black stack: L(0,0,1,1,0,0,0,1,1,0,0)
  Red stack:   L(1,0,0,0,0,0,1,0,1,0,1,1,1,0,1)
Agreed, black stack has same number of black cards 
  as red stack has number of red cards: 7