Created
May 8, 2025 19:57
-
-
Save cowens/2578eb80f8a7b7d39da3f16353722de1 to your computer and use it in GitHub Desktop.
This file contains hidden or 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
package main | |
import ( | |
"fmt" | |
"math/rand" | |
) | |
type Deck struct { | |
order []int | |
names []string | |
} | |
func riffle(deck Deck) Deck { | |
deckLen := len(deck.order) | |
// find a spot 25% to 75% through the deck of cards to cut the deck at | |
cut := rand.Intn(deckLen/2 - deckLen/4) + deckLen/4 | |
// cut the deck into two sides | |
left := deck.order[0:cut] | |
right := deck.order[cut:deckLen] | |
// 50% chance of starting with the left side of the cut | |
takeFromLeft := rand.Float64() < .5; | |
riffled := make([]int, deckLen) | |
// fill riffled from the bottom | |
i := deckLen | |
for i > 0 { | |
// create a packet of one to five cards from the current side | |
packetSize := rand.Intn(5) + 1 | |
// to DRY this code, you would have to use pointers which seems | |
// messier than the cut & paste | |
if takeFromLeft { | |
// packet size is the rest of this side if the other | |
// side is empty or the random packet size is larger | |
// than the cards left in this side | |
if len(right) == 0 || packetSize > len(left) { | |
packetSize = len(left) | |
} | |
// copy the packet to the output | |
start := len(left)-packetSize | |
copy(riffled[i-packetSize:i], left[start:len(left)]) | |
// remove the packet from this side | |
left = left[:start] | |
} else { | |
// packet size is the rest of this side if the other | |
// side is empty or the random packet size is larger | |
// than the cards left in this side | |
if len(left) == 0 || packetSize > len(right) { | |
packetSize = len(right) | |
} | |
// copy the packet to the output | |
start := len(right)-packetSize | |
copy(riffled[i-packetSize:i], right[start:len(right)]) | |
// remove the packet from this side | |
right = right[:start] | |
} | |
// take from the other side in the next iteration | |
takeFromLeft = !takeFromLeft | |
// move the index back in riffled because we added packetSize | |
// cards to the output | |
i -= packetSize | |
} | |
return Deck{ riffled, deck.names } | |
} | |
func nRiffle(deck Deck, n int) Deck { | |
for i := 0; i < n; i++ { | |
deck = riffle(deck) | |
} | |
return deck | |
} | |
func nRiffleWithCut(deck Deck, n int) Deck { | |
for i := 0; i < n; i++ { | |
deck = riffle(deck) | |
// extra cut after riffle 2 to see if that helps the last card | |
// move around more easily | |
if i == 2 { | |
deckLen := len(deck.order) | |
cut := rand.Intn(deckLen/2 - deckLen/4) + deckLen/4 | |
deck.order = append(deck.order[cut:deckLen], deck.order[0:cut]...) | |
} | |
} | |
return deck | |
} | |
func (deck Deck) count(card int) int { | |
count := 0 | |
for i := range deck.order { | |
if deck.order[i] == card { | |
count++ | |
} | |
} | |
return count | |
} | |
func analyze(deck Deck, n int, ideal []float64) { | |
N := 1_000_000 | |
var cards = make([][]int, len(deck.order)) | |
for i := range deck.order { | |
cards[i] = make([]int, len(deck.names)) | |
} | |
for i := 0; i < N; i++ { | |
riffled := nRiffleWithCut(deck, n) | |
for j, card := range riffled.order { | |
cards[j][card]++ | |
} | |
} | |
mins := make([]float64, len(deck.names)) | |
for i := range deck.names { | |
mins[i] = 100 | |
} | |
maxes := make([]float64, len(deck.names)) | |
for i, _ := range cards { | |
for j, n := range cards[i] { | |
percent := float64(n)/float64(N)*100 | |
mins[j] = min(mins[j], percent) | |
maxes[j] = max(maxes[j], percent) | |
} | |
} | |
fmt.Printf("riffled %d times\n", n) | |
for i, _ := range maxes { | |
fmt.Printf("\t%20s ideal %2.2f%% min %2.2f%% max %2.2f%%\n", deck.names[i], ideal[i], mins[i], maxes[i]) | |
} | |
fmt.Println() | |
} | |
func main() { | |
//deck := Deck { []int{ 1, 2, 3, 4, 5, 6, 7, 8 }, []string{} } | |
deck := Deck{ | |
[]int{ | |
0, | |
1, 1, | |
2, 2, 2, | |
3, 3, 3, 3, | |
4, 4, 4, 4, 4, | |
5, 5, 5, 5, 5, 5, | |
6, 6, 6, 6, 6, 6, 6, | |
7, 7, 7, 7, 7, 7, 7, 7, | |
8, 8, 8, 8, 8, 8, 8, 8, 8, | |
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, | |
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, | |
11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, | |
12, 12, 12, | |
13, 13, 13, | |
14, 14, 14, | |
15, 16, 17, 18, 19, 20, | |
}, | |
[]string{ | |
"1", // 1 | |
"2", // 2 | |
"3", // 3 | |
"4", // 4 | |
"5", // 5 | |
"6", // 6 | |
"7", // 7 | |
"8", // 8 | |
"9", // 9 | |
"10", // 10 | |
"11", // 11 | |
"12", // 12 | |
"second chance", // 3 | |
"flip three", // 3 | |
"freeze", // 3 | |
"+2", // 1 | |
"+4", // 1 | |
"+6", // 1 | |
"+8", // 1 | |
"+10", // 1 | |
"x2", // 1 | |
}, | |
} | |
ideal := make([]float64, len(deck.order)) | |
for i, _ := range deck.names { | |
ideal[i] = float64(deck.count(i)) / float64(len(deck.order)) * 100 | |
} | |
for n := 1; n <= 10; n++ { | |
analyze(deck, n, ideal) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment