Skip to content

Instantly share code, notes, and snippets.

@pdkl95
Last active March 11, 2021 23:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save pdkl95/6a8d162495a4e8fa4167ea43b4d3ed80 to your computer and use it in GitHub Desktop.
Save pdkl95/6a8d162495a4e8fa4167ea43b4d3ed80 to your computer and use it in GitHub Desktop.
Kruskal Count Card Trick
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Kruskal Count test</title>
<style type="text/css">
.hearts, .diamonds {
color: #c00;
}
.cards {
border-collapse: separate;
border-spacing: 5px 6px;
margin-left: 1em;
}
.cards td {
width: 28px;
height: 36px;
}
.cards td.pad {
padding: 3px;
}
.cards td.card {
padding: 2px;
background-color: #fdfdfd;
border: 1px solid #444;
border-radius: 4px;
box-shadow: 1px 1px 3px -1px rgba(0,0,0,0.4);
text-align: center;
font-weight: bold;
font-size: 18px;
}
.cards td.highlight {
padding: 0px;
border-width: 3px;
border-style: dotted;
border-color: #71AA38;
border-radius: 6px;
box-shadow: 0px 0px 2px 1px #7FFF00;
}
</style>
</head>
<body>
<header>
<h1>Kruskal Count test</h1>
</header>
<p>
A demonstration of Kruskal Count Card Trick, as seen here:<br>
<br>
<a href="http://faculty.uml.edu/rmontenegro/research/kruskal_count/kruskal.html">http://faculty.uml.edu/rmontenegro/research/kruskal_count/kruskal.html</a><br>
<br>
Author: pdkl95 (2020)<br>
License: This script is placed into the public domain.<br>
</p>
<h2>Single Shuffeled Deck</h2>
<p>
The Kruskal Count sequences in a randomly shiffeled deck of
cards. Reload the page to reshuffel.
</p>
<button id="shuffle_btn">Shuffle</button>
<h3>Random Deck</h3>
<table id="show_deck" class="cards">
</table>
<h3>First <span id="num_sequences">10</span> Kruskal Count sequences</h3>
<ol id="sequences">
</ol>
<script type="text/javascript">
function get_element(element_id) {
var el = document.getElementById(element_id);
if (el) {
return el;
} else {
throw "Missing elemewnt id=\"" + element_id + "\"";
}
}
var ui = {
deck: get_element("show_deck"),
sequences: get_element("sequences"),
num_sequences: get_element("num_sequences"),
shuffle_btn: get_element("shuffle_btn")
};
function Suit(symbol, name) {
this.symbol = symbol;
this.name = name;
}
Suit.all = [];
/*
* Face.all is a list of all card faces within each suit
*
* Each face's #value is the number of cards to advance
* down the deck in the Kruskal Count.
*/
function Face(symbol, name, value) {
this.symbol = symbol;
this.name = name;
this.value = value;
}
Face.all = [];
function Card(suit, face) {
this.suit = suit;
this.face = face;
this.name = '' + this.face.name + ' of ' + this.name;
this.symbol = '' + this.face.symbol + this.suit.symbol;
this.value = this.face.value;
}
Card.all = [];
Card.prototype.create_cell = function (id_prefix) {
var el = document.createElement('td');
el.classList.add('card');
el.classList.add(this.face.name);
el.classList.add(this.suit.name);
el.innerHTML = this.symbol;
return el;
};
function Deck() {
this.cards = Card.all.slice(0);
this.shuffle();
}
Deck.prototype.shuffle = function () {
var i;
for(i = this.cards.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * i);
var temp = this.cards[i];
this.cards[i] = this.cards[j];
this.cards[j] = temp;
}
};
Deck.prototype.card_after = function (index) {
var next_index = index + this.cards[index].value;
if (next_index < this.cards.length) {
return next_index;
} else {
return null;
}
};
Deck.prototype.chain_from = function (index) {
var next_index = this.card_after(index);
var head = [index];
if (next_index) {
var chain = head.concat(this.chain_from(next_index));
return chain;
} else {
return head;
}
};
Deck.prototype.card_chain_from = function (index) {
var chain = this.chain_from(index);
var cards = [];
for (var i = 0; i < chain.length; i++) {
cards.push(this.cards[chain[i]]);
}
return cards;
};
function define_standard_deck() {
Suit.all.push(new Suit('♦', 'diamonds'));
Suit.all.push(new Suit('♣', 'clubs'));
Suit.all.push(new Suit('♥', 'hearts'));
Suit.all.push(new Suit('♠', 'spades'));
Face.all.push(new Face('A', 'ace', 1));
Face.all.push(new Face('2', 'two', 2));
Face.all.push(new Face('3', 'three', 3));
Face.all.push(new Face('4', 'four', 4));
Face.all.push(new Face('5', 'five', 5));
Face.all.push(new Face('6', 'six', 6));
Face.all.push(new Face('7', 'seven', 7));
Face.all.push(new Face('8', 'eight', 8));
Face.all.push(new Face('9', 'nine', 9));
Face.all.push(new Face('J', 'jack', 5));
Face.all.push(new Face('Q', 'queen', 5));
Face.all.push(new Face('K', 'king', 5));
for (var suit of Suit.all) {
for (var face of Face.all) {
Card.all.push(new Card(suit, face));
}
}
}
function generate_deck() {
var deck = new Deck();
return deck;
}
function show_deck(deck, rows) {
var num_cards = deck.cards.length;
var rowlen = num_cards / rows;
if ((rows * rowlen) != num_cards) {
throw "" + num_cards + " cards cannot be divided into " + rows + " rows";
}
ui.deck.innerHTML = '';
var i = 0;
for (var r=0; r < rows; r++) {
var newrow = document.createElement('tr');
newrow.id = "deck_row_" + r;
for (var c=0; c < rowlen; c++) {
var card = deck.cards[i];
var cell = card.create_cell();
cell.id = "deck_card_" + i;
card.deck_id = cell.id;
newrow.appendChild(cell);
i += 1;
}
ui.deck.appendChild(newrow);
}
}
function show_sequences(deck, n) {
ui.num_sequences.innerHTML = n;
ui.sequences.innerHTML = '';
var chains = [];
var maxlen = 0;
for (var i = 0; i < n; i++) {
var chain = deck.card_chain_from(i);
chains.push(chain);
if (chain.length > maxlen) {
maxlen = chain.length;
}
}
for (var i = 0; i < n; i++) {
var chain = chains[i];
var row = document.createElement('tr');
var deck_cells = [];
if (chain.length < maxlen) {
var pad = maxlen - chain.length;
for (; pad > 0; pad--) {
var padcell = document.createElement('td');
padcell.classList.add('pad');
row.appendChild(padcell);
}
}
for (var j = 0; j < chain.length; j++) {
var card = chain[j];
deck_cells.push(document.getElementById(card.deck_id));
var cell = card.create_cell();
cell.id = 'kruskal_seq_' + i + '_card_' + j;
row.appendChild(cell);
}
var table = document.createElement('table');
table.id = 'kruskal_seq_' + i;
table.classList.add('cards');
table.classList.add('sequence');
table.appendChild(row);
(function () {
var ii = i;
var dc = deck_cells;
table.addEventListener('mouseenter', function () {
for (var cell of dc) {
cell.classList.add('highlight');
}
});
table.addEventListener('mouseleave', function () {
for (var cell of dc) {
cell.classList.remove('highlight');
}
});
}());
var li = document.createElement('li');
li.appendChild(table);
ui.sequences.appendChild(li);
}
}
function new_deck_and_sequences() {
var deck = generate_deck();
window.deck = deck;
show_deck(deck, 4);
show_sequences(deck, 5);
}
document.addEventListener("DOMContentLoaded", function() {
define_standard_deck();
new_deck_and_sequences();
ui.shuffle_btn.addEventListener('click', function () {
new_deck_and_sequences();
});
});
</script>
</body>
</html>
#!/bin/env ruby
#############################################################################
# #
# A demonstration of Kruskal Count Card Trick, as seen here: #
# http://faculty.uml.edu/rmontenegro/research/kruskal_count/kruskal.html #
# #
# Original Script Author: pdkl95 (2018) #
# License: This script is placed into the public domain. #
# #
#############################################################################
########################################################################
# first, a few convenience classes to build a deck of cards
# Suit.all is a list of all suits
class Suit < Struct.new(:symbol, :name)
def self.all
@all ||= []
end
def self.create(*args)
suit = new(*args)
all << suit
suit
end
create 'D', 'diamonds'
create 'C', 'clubs'
create 'H', 'hearts'
create 'S', 'spades'
end
# Face.all is a list of all card faces within each suit
#
# Each face's #value is the number of cards to advance
# down the deck in the Kruskal Count.
class Face < Struct.new(:symbol, :name, :value)
def self.all
@all ||= []
end
def self.create(*args)
face = new(*args)
all << face
face
end
def to_i
value
end
create 'A', 'ace', 1
(2..10).each do |n|
str = n.to_s
create str, str, n
end
create 'J', 'jack', 5
create 'Q', 'queen', 5
create 'K', 'king', 5
end
# Card.all is a sorted array of all cards in the deck.
# (you should probably #dup before making changes)
class Card < Struct.new(:suit, :face)
def self.all
@all ||= []
end
def self.create(*args)
card = new(*args)
all << card
card
end
def name
"#{face.name} of #{suit.name}"
end
def symbol
"#{face.symbol}#{suit.symbol}"
end
def to_s
symbol
end
def inspect
"#<Card \"#{name}\">"
end
def value
face.value
end
def to_i
value
end
Suit.all.each do |suit|
Face.all.each do |face|
create suit, face
end
end
end
# The actual shuffeled deck of cards
class Deck
# each new Deck is randomly shuffled with the Fisher-Yates shuffle
# adapted from: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
#
# the shuffle is deterministic and repeatable when an RNG seed is provided
attr_reader :cards
def initialize(rng_seed = nil)
@cards = Card.all.dup
rng = if rng_seed.nil?
Random.new
else
unless rng_seed.is_a? Integer
rng_seed = rng_seed.to_i
end
Random.new(rng_seed)
end
(0..(length-2)).each do |i|
j = rng.rand(i...length)
tmp = cards[i]
cards[i] = cards[j]
cards[j] = tmp
end
end
def length
@length ||= Card.all.length
end
def to_s
"Deck[#{cards.join(', ')}]"
end
def inspect
to_s
end
def card_after(index)
next_index = index + cards[index].value
if next_index < length
next_index
else
nil
end
end
def chain_from(index)
next_index = card_after(index)
head = [index]
if next_index
head + chain_from(next_index)
else
head
end
end
def index_to_s(index)
card = "#{cards[index]}".rjust(3)
"(#{index}, #{card})"
end
def chain_to_s(chain)
chain.map do |index|
index_to_s(index)
end.join(" -> ")
end
def chain_str_from(start)
chain_to_s(chain_from(start))
end
def print_chain(start)
puts chain_str_from(start)
end
end
# right-justify output to align the matching chain ends
def rjust_strings(list)
max_len = list.map do |str|
str.length
end.max
list.map do |str|
str.rjust(max_len)
end
end
def show_deck_chains(range, deck)
puts deck
puts
heads = range.map(&:to_s)
chains = range.map do |start|
deck.chain_str_from(start)
end
jheads = rjust_strings(heads)
jchains = rjust_strings(chains)
jheads.zip(jchains).each do |pair|
puts pair.join(': ')
end
end
########################################################################
# main()
range = (0..9)
if ARGV.length > 0
first = true
ARGV.each do |seed|
if first
first = false
else
puts
end
puts "RNG seed: #{seed}"
show_deck_chains(range, Deck.new(seed))
end
else
show_deck_chains(range, Deck.new)
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment