LAB 02.04 - Card trick

!wget --no-cache -O init.py -q https://raw.githubusercontent.com/fagonzalezo/ai4eng-unal/main/content/init.py
import init; init.init(force_download=False); init.get_weblink()

from local.lib.rlxmoocapi import submit, session
session.LoginSequence(endpoint=init.endpoint, course_id=init.course_id, lab_id="L02.04", varname="student");

import numpy as np
import pandas as pd
import itertools

Setup

make sure to watch the corresponding video to understand the card trick.

create a deck for a given configuration

The following function returns a list of card names. The shuffle argument is self evident. We use two letters as an arbitrary card name so that we have enough names for large configurations.

def create_deck(n_heaps, cards_per_heap, shuffle=False):
    n_cards = n_heaps * cards_per_heap
    
    chars = [chr(i) for i in np.arange(26)+65]
    names = [i+j for i,j in itertools.product(chars, chars)]    

    assert n_cards < len(names), "cannot have more than %d cards"%len(name)
    
    c = np.r_[names[:n_cards]]
    if shuffle:
        c = np.random.permutation(c)
    return c

create_deck(n_heaps=3, cards_per_heap=10, shuffle=False)

create_deck(n_heaps=3, cards_per_heap=7, shuffle=True)

create_deck(n_heaps=3, cards_per_heap=10, shuffle=True)

pick a card

the following function randomly picks a card from a deck

def pick_card(c):
    return np.random.choice(c)

c = create_deck(n_heaps=3, cards_per_heap=7, shuffle=True)
n = pick_card(c)
n

Task 1. Make the heaps

Complete the following funcion so that given desk (as a list returned by create_deck) distributes the cards in n_heaps according to the procedure of the card trick shown in the video.

The heaps must be a list of n_heaps lists, each one with len(c)/n_heaps card names.

n_heaps will be an odd number (so that later we can put the chosen heap in the middle of the others), and must be a divisor of the total number of cards in the deck (so that all heaps have the same number of cards)

For instance,

>>> n_heaps = 3
>>> c = create_deck(n_heaps=n_heaps, cards_per_heap=7)
>>> h = make_heaps(c, n_heaps)
>>> print("deck", c)
>>> print("heaps")
>>> h   

deck ['AA' 'AB' 'AC' 'AD' 'AE' 'AF' 'AG' 'AH' 'AI' 'AJ' 'AK' 'AL' 'AM' 'AN'
 'AO' 'AP' 'AQ' 'AR' 'AS' 'AT' 'AU']
heaps
[['AA', 'AD', 'AG', 'AJ', 'AM', 'AP', 'AS'],
 ['AB', 'AE', 'AH', 'AK', 'AN', 'AQ', 'AT'],
 ['AC', 'AF', 'AI', 'AL', 'AO', 'AR', 'AU']]

or also

>>> n_heaps = 5
>>> c = create_deck(n_heaps=n_heaps, cards_per_heap=3, shuffle=True)
>>> h = make_heaps(c, n_heaps)
>>> print("deck", c)
>>> print("heaps")
>>> h

deck ['AA' 'AJ' 'AM' 'AK' 'AH' 'AF' 'AD' 'AN' 'AB' 'AC' 'AG' 'AE' 'AL' 'AI'
 'AO']
heaps
[['AA', 'AF', 'AG'],
 ['AJ', 'AD', 'AE'],
 ['AM', 'AN', 'AL'],
 ['AK', 'AB', 'AI'],
 ['AH', 'AC', 'AO']]

def make_heaps(c, n_heaps=3):
    assert n_heaps%2==1, "must have an odd number of heaps"
    assert len(c)%n_heaps==0, "the length of the deck must be a multiple of the number of heaps"
    
    h = ... # YOUR CODE HERE
    return h

manually check your code

n_heaps = 3
c = create_deck(n_heaps=n_heaps, cards_per_heap=7)
h = make_heaps(c, n_heaps)

print("deck", c)
print("heaps")
h

n_heaps = 5
c = create_deck(n_heaps=n_heaps, cards_per_heap=3, shuffle=True)
h = make_heaps(c, n_heaps)

print("deck", c)
print("heaps")
h

submit your code

student.submit_task(globals(), task_id="task_01");

Task 2: Organize the heaps

Complete the following funcion so that given a set of heaps (such as the ones returned by the function of the previous task) and a card name:

  1. Finds what is the heap that contains the card

  2. Makes randomly two groups of n_heaps//2 heaps of the remaining heaps

    • if n_heaps=3 this will be two groups of one heap each, since 3//2=1

    • if n_heaps=5, it will be two groups of two heaps each, since 5//2=2

    • etc. (observe // is the integer division)

  3. Concatenates the cards in one group with the cards in the heap containing the given card name. with the cards of the second group

For example

>>> n_heaps = 3
>>> c = create_deck(n_heaps=n_heaps, cards_per_heap=7, shuffle=True)
>>> n = pick_card(c)
>>> print ("card picked", n)
>>> h = make_heaps(c, n_heaps)
>>> h

card picked AD
[['AP', 'AC', 'AE', 'AO', 'AQ', 'AF', 'AM'],
 ['AN', 'AT', 'AB', 'AJ', 'AU', 'AI', 'AS'],
 ['AR', 'AD', 'AA', 'AG', 'AH', 'AL', 'AK']]


>>> new_c = collect_heaps(h, n)
>>> print (new_c)

['AP', 'AC', 'AE', 'AO', 'AQ', 'AF', 'AM', 'AR', 'AD', 'AA', 'AG', 'AH', 'AL', 'AK', 'AN', 'AT', 'AB', 'AJ', 'AU', 'AI', 'AS']

def collect_heaps(h, n):
    
    r = ... # YOUR CODE HERE
    
    return r

manually check your code

n_heaps = 3
c = create_deck(n_heaps=n_heaps, cards_per_heap=7, shuffle=True)
n = pick_card(c)
print ("card picked", n)
h = make_heaps(c, n_heaps)
h

new_c = collect_heaps(h, n)
print (new_c)

submit your code

student.submit_task(globals(), task_id="task_02");

Task 3: Run the card trick

Complete the following function such that, when given a a deck of cards c, and picked card n and a number of heaps n_heaps, returns the position of the picked card after doing three times the collect. The position number must start at zero.

For instance:

  • For n_heaps=3 and cards_per_heap=7, the final position will always be 10 (which is 11 if you start counting at 1)

  • For n_heaps=3 and cards_per_heap=4, the final position will be sometimes 5 and sometimes 6 depending on the position of the picked card on the initial deck.

  • For n_heaps=5 and cards_per_heap=3, the final position will always be 7

You must return an int

def run(c, n, n_heaps=3):
    r = ... # YOUR ANSWER HERE
    return r

manually check your code

n_heaps = 3
c = create_deck(n_heaps=n_heaps, cards_per_heap=7)
picked = "AA"
print ("desk", c)
pos = run(c, picked, n_heaps=n_heaps)
print ("position of card %s is %d"%(picked, pos))

n_heaps = 3
c = create_deck(n_heaps=n_heaps, cards_per_heap=4)
picked = "AI"
print ("deck", c)
pos = run(c, picked, n_heaps=n_heaps)
print ("position of card %s is %d"%(picked, pos))

submit your code

student.submit_task(globals(), task_id="task_03");

Task 4: Run the trick using the math

Given:

  • \(n_h\): A number of heaps

  • \(c_h\): the number of cards per heap

  • \(i\): the position of a card

The new position of the card after one cycle of making and collecting the heaps will be:

\[c_h(n_h\div2)+i\div n_h\]

Complete the following function so that it has the same functionality of the previous task, but applying only this formula without using the simulation above. You MUST NOT ADD or remove lines from the function skeleton below, ONLY fill in the ...

You must get the same results as the previous task.

HINT: Use np.argwhere to get the initial position of the card in the deck

def mrun(c, picked_card, n_heaps=3):
    assert len(c)%n_heaps==0, "the number of heaps must be a divisor of the deck length"
    
    ch = len(c)//n_heaps # cards per heap
    nh = n_heaps
    
    i = ... # initial position of the card on the deck c
    p1 = ...  # the position of the card after the first round
    p2 = ...  # the position of the card after the second round
    p3 = ...  # the position of the card after the last round
    
    return p3

n_heaps = 3
c = create_deck(n_heaps=n_heaps, cards_per_heap=4)
picked = "AI"
print ("deck", c)
pos = mrun(c, picked, n_heaps=n_heaps)
print ("position of card %s is %d"%(picked, pos))

submit your code

student.submit_task(globals(), task_id="task_04");

You are done. Now, some considerations

using the math is always faster!!!

n_heaps = 3
c = create_deck(n_heaps=n_heaps, cards_per_heap=4)
picked = "AI"
print ("deck", c)

%timeit run(c, picked, n_heaps=n_heaps)

%timeit mrun(c, picked, n_heaps=n_heaps)

you can check if the trick works for a specific configuration

n_heaps = 3
cards_per_heap = 7

c = create_deck(n_heaps, cards_per_heap)

r = [[n, mrun(c,n, n_heaps=n_heaps)] for n in c]
print ("deck", c)
pd.DataFrame(r, columns=["card picked", "final position"])

n_heaps = 3
cards_per_heap = 4

c = create_deck(n_heaps, cards_per_heap)

r = [[n, mrun(c,n, n_heaps=n_heaps)] for n in c]
print ("deck", c)
pd.DataFrame(r, columns=["card picked", "final position"])