Last active
March 11, 2021 23:42
-
-
Save pdkl95/6a8d162495a4e8fa4167ea43b4d3ed80 to your computer and use it in GitHub Desktop.
Kruskal Count Card Trick
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!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> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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