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
}