This problem was a fun one and it wasn’t too hard so I enjoyed it. It definitely didn’t keep me up all night so that was a plus! I ultimately solved it in three stages.
Stage one: brute force. First I created a func that given a deck size, would return the number of shuffles required to put it back to its original state. I was able to figure out the algorithm for this by doing a little trial and error on paper. Ends up it has to do with powers of 2 and modulo math. I let this run overnight (might as well right?) and found it continuing to chug away in the morning. Doing a bit of math, I found out that I was needing to get through each number up to 2 to the power of 60! Wow, that’s a big number and definitely not one you can brute force your way to. So I tried something else.
Stage two: reversing modulo. I had figured out that the algorithm had to do
with modulus math. Instead of brute forcing, I needed to find a way to devise
the answers. This meant reversing the modulo function. In other words, given
a mod b = c we know that the answers are going to be in the form
a = n*b + c where n is an integer. This solves for a, but I wanted to solve
for b which ends up being b = (a - c) / n. I used this formua for a while and
still found it to be incredibly slow.
Stage three: divisors of (a - c). I looked closer and realized that if n does
not divide (a - c) evenly, then there is no point in trying it. Therefore, I
tried creating a slice of all integers that divide (a - c) evenly and only
trying those. I was worried that creating this divisor slice would take an
insane amount of time. But it didn’t! And eventually I was lead to the answer
in just 19 seconds of program time. Pretty awesome!
Was this my first problem solved in Golang? Maybe! Funtimes!
package main
import (
"fmt"
"math"
)
// nextLocation gives the next location of a given card location.
func nextLocation(currentLocation, deckSize int) int {
return (currentLocation * 2) % (deckSize - 1)
}
var (
overageErr = fmt.Errorf("passed goal shuffle count")
oddErr = fmt.Errorf("deck size should not be odd")
)
// shufflesNeeded returns the total shuffles need to return a deck of size
// deckSize back to its original configuration.
func shufflesNeeded(deckSize, goal int) (int, error) {
if deckSize%2 != 0 {
return 0, oddErr
}
currentLocation := 1
shuffles := 0
for {
shuffles++
currentLocation = nextLocation(currentLocation, deckSize)
if currentLocation == 1 {
return shuffles, nil
}
if currentLocation == deckSize-2 {
return shuffles * 2, nil
}
if shuffles > goal {
return 0, overageErr
}
}
}
// getDivisors returns a slice of the divisors of num.
func getDivisors(num int) []int {
halfWay := int(math.Sqrt(float64(num))) + 1
d := []int{1, num}
for i := 2; i < halfWay; i++ {
if num%i == 0 {
d = append(d, i)
if div := num / i; div != i {
d = append(d, div)
}
}
}
return d
}
// sumShufflesNeeded returns the total of all deck sizes that are possible to
// shuffler perfectly in goal times.
func sumShufflesNeeded(goal int) int {
max := int(math.Pow(2, float64(goal))) - 1
var totalDeckSizes int
for _, n := range getDivisors(max) {
i := (max / n) + 1
if shuffles, _ := shufflesNeeded(i, goal); shuffles == goal {
totalDeckSizes += i
}
}
return totalDeckSizes
}
func main() {
result := sumShufflesNeeded(60)
fmt.Println(result)
}
package main
import "testing"
func TestShufflesNeeded(t *testing.T) {
testcases := []struct {
deckSize int
maxShuffles int
expected int
}{
{deckSize: 52, maxShuffles: 100, expected: 8},
{deckSize: 52, maxShuffles: 8, expected: 8},
{deckSize: 86, maxShuffles: 100, expected: 8},
{deckSize: 6, maxShuffles: 100, expected: 4},
{deckSize: 8, maxShuffles: 100, expected: 3},
{deckSize: 10, maxShuffles: 100, expected: 6},
{deckSize: 12, maxShuffles: 100, expected: 10},
{deckSize: 4, maxShuffles: 100, expected: 2},
{deckSize: 12, maxShuffles: 2, expected: 0},
}
for _, test := range testcases {
if actual, _ := shufflesNeeded(test.deckSize, test.maxShuffles); actual != test.expected {
t.Errorf("incorrect shufflesNeeded for deck size %d: actual=%d expected=%d",
test.deckSize, actual, test.expected)
}
}
}
func TestSumShufflesNeeded(t *testing.T) {
testcases := []struct {
goal int
expected int
}{
{goal: 3, expected: 8},
{goal: 4, expected: 22},
{goal: 5, expected: 32},
{goal: 6, expected: 96},
{goal: 7, expected: 128},
{goal: 8, expected: 412},
{goal: 9, expected: 586},
{goal: 10, expected: 1506},
{goal: 11, expected: 2162},
{goal: 12, expected: 8628},
{goal: 13, expected: 8192},
{goal: 14, expected: 22402},
{goal: 15, expected: 38878},
{goal: 16, expected: 111032},
{goal: 17, expected: 131072},
{goal: 18, expected: 472936},
{goal: 19, expected: 524288},
{goal: 20, expected: 1998354},
{goal: 21, expected: 2465922},
{goal: 22, expected: 5907608},
{goal: 23, expected: 8567138},
{goal: 24, expected: 38044940},
{goal: 25, expected: 34713702},
{goal: 26, expected: 89513986},
{goal: 27, expected: 155492948},
{goal: 28, expected: 462252066},
}
for _, test := range testcases {
if actual := sumShufflesNeeded(test.goal); actual != test.expected {
t.Errorf("incorrect sumShufflesNeeded for goal %d: actual=%d expected=%d",
test.goal, actual, test.expected)
}
}
}
func BenchmarkShufflesNeeded(b *testing.B) {
b.ReportAllocs()
for n := 0; n < b.N; n++ {
shufflesNeeded(52, 8)
}
}
func BenchmarkSumShufflesNeeded(b *testing.B) {
b.ReportAllocs()
for n := 0; n < b.N; n++ {
sumShufflesNeeded(8)
}
}