dd

[Olyadtemesgen]

Ussue Overview: The current implementation of the getCatch function uses the sort.SearchInts method to find matching elements between myPicks and winningNumbers. While this approach works correctly, it has a time complexity of O(m * log(n)), where m is the length of myPicks, and n is the length of winningNumbers. To enhance the performance of the getCatch function and reduce the time complexity, we propose implementing getCatch2 using the two-pointer technique.

Proposed Solution: I have implemented a more efficient version of the getCatch function, called getCatch2, that leverages the fact that both myPicks and winningNumbers are sorted. By using the two-pointer technique, we can find the common elements between the two arrays with a time complexity of O(m + n), where m is the length of myPicks, and n is the length of winningNumbers

package game

import (
    "crypto/rand"
    "fmt"
    "math/big"
    "sort"
    "sync"
    "sync/atomic"
)

const (
    ITERATIONS = 10000000
    NUM_SLOTS  = 10 // Number of spot games to simulate
    BATCH_SIZE = 1000
)

func main() {

    var wg sync.WaitGroup

    for i := 1; i <= NUM_SLOTS; i++ {
        myPicks := generateAndFetch(i)
        wg.Add(1)
        go func(picks []int, slot int) {
            defer wg.Done()
            simulateKenoGame(picks, slot)
        }(myPicks, i)
    }

    wg.Wait()

    // for i := 1; i <= 10; i++ {
    //  for j := 0; j <= i; j++ {
    //      p := CalculateTheoreticalProbability(i, j)
    //      fmt.Printf("%.10f ", p)
    //  }
    //  fmt.Println()
    // }

}

func simulateKenoGame(myPicks []int, spot int) {
    numOccurences := make([]int64, spot+1)

    batches := ITERATIONS / BATCH_SIZE
    remainingIterations := ITERATIONS % BATCH_SIZE

    var wg sync.WaitGroup

    wg.Add(batches)

    for batch := 0; batch < batches; batch++ {
        fmt.Printf("\rRunning batch %d, of %d spot ", batch, spot)
        go func() {
            defer wg.Done()
            batchNumOccurences := make([]int64, spot+1)
            for i := 0; i < BATCH_SIZE; i++ {
                fmt.Printf("\r => Running iteration %d, of %d spot ", i, spot)
                shuffledNumbers := generateAndFetch(20)
                sort.Ints(shuffledNumbers)
                catch := getCatch(myPicks, shuffledNumbers)
                batchNumOccurences[catch]++
            }

            for idx, numOccurence := range batchNumOccurences {
                atomic.AddInt64(&numOccurences[idx], numOccurence)
            }
        }()
    }

    // Handle remaining iterations
    for i := 0; i < remainingIterations; i++ {
        shuffledNumbers := generateAndFetch(20)
        sort.Ints(shuffledNumbers)
        catch := getCatch(myPicks, shuffledNumbers)
        atomic.AddInt64(&numOccurences[catch], 1)
    }

    wg.Wait()

    fmt.Println()
    sum := 0.00
    resultText := "\n\n%d spot game: (user picks %d numbers)\n"
    for idx, numOccurence := range numOccurences {
        odd := float64(numOccurence) / float64(ITERATIONS)
        theoOdd := CalculateTheoreticalProbability(spot, idx)
        resultText += "            probability of matching " + fmt.Sprint(idx) + " in " + fmt.Sprint(spot) + " spot game: " + fmt.Sprint(odd) + "\n"
        resultText += "theoretical probability of matching " + fmt.Sprint(idx) + " in " + fmt.Sprint(spot) + " spot game: " + fmt.Sprint(theoOdd) + "\n"
        sum += odd
    }
    // resultText += "\ntotal probability (should be 1): " + fmt.Sprint(sum) + "\n\n"
    fmt.Printf(resultText, spot, spot)
}

/*
This function returns the catch which is
how many of the user's numbers matched the winning 20.

    CAN THIS BE IMPORVED || MADE FASTER ??
*/
func getCatch(myPicks, winningNumbers []int) int {
    catch := 0
    for _, myPick := range myPicks {

        index := sort.SearchInts(winningNumbers, myPick)
        //        fmt.Println(i, ":", winningNumbers)
        if index < len(winningNumbers) && winningNumbers[index] == myPick {
            //   fmt.Println("\x1b[33mFOUND!\x1b[0m")
            catch++
        }
    }
    return catch
}

// If both are sorted at first we can just get the catch numbers with time complexity O(m + n) ie m = len(myPicks) and n = len(winningNumbers) with two-pointer technique
func getCatch2(myPicks, winningNumbers []int64) int {
    catch := 0
    picksLength := len(myPicks)

    winningNumbersLength := len(winningNumbers)
    picksIndex := 0
    winningNumbersIndex := 0
    //
    for (picksIndex < picksLength) && (winningNumbersIndex < winningNumbersLength) {
        if myPicks[picksIndex] == winningNumbers[winningNumbersIndex] {
            catch++
            picksIndex++
            winningNumbersIndex++
        } else if myPicks[picksIndex] < winningNumbers[winningNumbersIndex] {
            picksIndex++
        } else {
            winningNumbersIndex++
        }
    }
    return catch
}

func generateAndFetch(size int) []int {
    if size < 1 || size > 80 {
        panic("size should be between 1 and 80")
    }
    n := 80
    arr := make([]int, n)

    // Populate the array with integers from 1 to 80 :)
    for i := 0; i < n; i++ {
        arr[i] = i + 1
    }

    shuffleArray(arr)

    // Fetch the first 20 numbers from the shuffled array
    return arr[:size]
}

// from go-backend-poker/utils/random
// GetSecureRandom allegedly gets a fair random secure value
func GetSecureRandom(min, max int) int {

    if max <= 0 {
        panic("can't define input as <=0")
    }
    // rand.Int() returns a uniform random value in [0, max). It panics if max <= 0
    // https://pkg.go.dev/crypto/rand#Int
    nbig, err := rand.Int(rand.Reader, big.NewInt(int64(max)))
    if err != nil {
        panic(err)
    }
    n := int(nbig.Int64())

    return min + n
}

// fischer-yates shuffle algorithm - is this secure??
func shuffleArray(arr []int) {
    length := len(arr)
    for i := length - 1; i > 0; i-- {
        j := GetSecureRandom(0, i+1)
        arr[i], arr[j] = arr[j], arr[i]
    }
}

// https://en.wikipedia.org/wiki/Keno#Probability_calculation

func CalculateTheoreticalProbability(spot, catch int) float64 {
    nCrSpot := NChooseR(spot, catch)
    nCrComplement := NChooseR(80-spot, 20-catch)
    nCrTotal := NChooseR(80, 20)

    // Calculate the probability using big.Float to handle large numbers
    probability := new(big.Float).SetInt(nCrSpot)
    probability.Mul(probability, new(big.Float).SetInt(nCrComplement))
    probability.Quo(probability, new(big.Float).SetInt(nCrTotal))

    probFloat64, _ := probability.Float64()
    return probFloat64
}

// No Packages ?? (- _ -)
func factorial(n int) *big.Int {
    if n < 0 {
        return big.NewInt(0)
    }

    fact := big.NewInt(1)
    for i := 1; i <= n; i++ {
        fact.Mul(fact, big.NewInt(int64(i)))
    }
    return fact
}

// NChooseR calculates the binomial coefficient "n choose r" - note that it's doing integer division just because
func NChooseR(n, r int) *big.Int {
    if n < r {
        return big.NewInt(0)
    }

    numerator := factorial(n)
    denominator := new(big.Int).Mul(factorial(r), factorial(n-r))

    result := new(big.Int).Div(numerator, denominator)
    return result
}

[Olyadtemesgen]

** Alternative way to implement the getCatch function using sorting and two pointers technique

func getCatch2(myPicks []int, winningNumbers []int) int {

    sort.Ints(myPicks)

    // myPicks = qsort(myPicks)

    catch := 0
    picksLength := len(myPicks)
    winningNumbersLength := len(winningNumbers)
    picksIndex := 0
    winningNumbersIndex := 0

    for (picksIndex < picksLength) && (winningNumbersIndex < winningNumbersLength) {
        if myPicks[picksIndex] == winningNumbers[winningNumbersIndex] {
            catch++
            picksIndex++
            winningNumbersIndex++
        } else if myPicks[picksIndex] < winningNumbers[winningNumbersIndex] {
            picksIndex++
        } else {
            winningNumbersIndex++
        }
    }
    return catch
}