From 2cc0f9607872b8bd4fc6be2656a7b7a769b538b2 Mon Sep 17 00:00:00 2001 From: Adrien Hopkins Date: Tue, 7 Nov 2023 07:50:23 -0500 Subject: Reduce golang requirement to go1.18 go1.21, the previous requirement, was released a few months ago, so not all systems have adopted it. go1.18 is old enough that most systems should support it, but it introduces generics, which my testing code is highly dependent on, so I can't easily go any earlier. --- factors/prime_factorization.go | 4 +-- factors/slices.go | 27 +++++++++++++++++ factors/table_test.go | 66 ++++++++++++++++++++++++++++++------------ factors/type.go | 11 +++---- 4 files changed, 80 insertions(+), 28 deletions(-) create mode 100644 factors/slices.go (limited to 'factors') diff --git a/factors/prime_factorization.go b/factors/prime_factorization.go index 52df2c1..f758448 100644 --- a/factors/prime_factorization.go +++ b/factors/prime_factorization.go @@ -2,7 +2,6 @@ package factors import ( "fmt" - "slices" "strings" ) @@ -69,8 +68,7 @@ func (factors PrimeFactorization) Size() int { // String returns a string representation of the prime factorization, // which looks like "2^2 × 3". func (factors PrimeFactorization) String() string { - primesSorted := factors.Primes() - slices.Sort(primesSorted) + primesSorted := sortUints(factors.Primes()) parts := make([]string, 0, factors.Size()) for _, p := range primesSorted { diff --git a/factors/slices.go b/factors/slices.go new file mode 100644 index 0000000..f2462cf --- /dev/null +++ b/factors/slices.go @@ -0,0 +1,27 @@ +package factors + +import "sort" + +func sortUints(s []uint) []uint { + sort.Slice(s, func(i, j int) bool { return s[i] < s[j] }) + return s +} + +func maxUints(s []uint) uint { + max := uint(0) + for _, n := range s { + if n > max { + max = n + } + } + return max +} + +func contains[S ~[]E, E comparable](s S, e E) bool { + for _, element := range s { + if e == element { + return true + } + } + return false +} diff --git a/factors/table_test.go b/factors/table_test.go index e288c3b..828d80b 100644 --- a/factors/table_test.go +++ b/factors/table_test.go @@ -2,8 +2,6 @@ package factors import ( "fmt" - "maps" - "slices" "testing" ) @@ -41,7 +39,7 @@ var primeFactorCases = map[uint]PrimeFactorization{ func TestPrimeFactorize(t *testing.T) { equal := func(a, b PrimeFactorization) bool { - return maps.Equal(a.exponents, b.exponents) + return mapEquals(a.exponents, b.exponents) } tableTest(t, PrimeFactorize, primeFactorCases, equal, "PrimeFactorize") } @@ -66,7 +64,7 @@ var factorCases = map[uint][]uint{ } func TestFactors(t *testing.T) { - tableTest(t, Factors, factorCases, setEquals, "Factors") + tableTest(t, Factors, factorCases, setEquals[uint], "Factors") } var totativeRatioCases = map[uint]float64{ @@ -81,7 +79,8 @@ func totativeRatio(n uint) float64 { } func TestTotativeRatio(t *testing.T) { - tableTest(t, totativeRatio, totativeRatioCases, stdEquals, "TotativeRatio") + tableTest(t, totativeRatio, totativeRatioCases, stdEquals[float64], + "TotativeRatio") } var totientCases = map[uint]uint{ @@ -90,7 +89,7 @@ var totientCases = map[uint]uint{ } func TestTotativeCount(t *testing.T) { - tableTest(t, Totient, totientCases, stdEquals, "Totient") + tableTest(t, Totient, totientCases, stdEquals[uint], "Totient") } var totativeDigitCases = map[uint32][]uint32{ @@ -121,7 +120,7 @@ var totativeDigitCases = map[uint32][]uint32{ } func TestTotativeDigits(t *testing.T) { - tableTest(t, TotativeDigits, totativeDigitCases, slices.Equal, + tableTest(t, TotativeDigits, totativeDigitCases, sliceEquals[uint32], "TotativeDigits") } @@ -142,7 +141,7 @@ var factorScoreCases = map[uint]float64{ func TestFactorScore(t *testing.T) { // factors.Score is accurate enough that we can test for exact floats! - tableTest(t, Score, factorScoreCases, stdEquals, "Score") + tableTest(t, Score, factorScoreCases, stdEquals[float64], "Score") } var basicRankCases = map[uint]string{ @@ -160,7 +159,7 @@ var basicRankCases = map[uint]string{ } func TestBasicRank(t *testing.T) { - tableTest(t, BasicRank, basicRankCases, stdEquals, "BasicRank") + tableTest(t, BasicRank, basicRankCases, stdEquals[string], "BasicRank") } var gcdCases = map[struct{ a, b uint32 }]uint32{ @@ -181,7 +180,7 @@ func gcdTest(c struct{ a, b uint32 }) uint32 { } func TestGCD(t *testing.T) { - tableTest(t, gcdTest, gcdCases, stdEquals, "gcd") + tableTest(t, gcdTest, gcdCases, stdEquals[uint32], "gcd") } var mtcCases = map[uint32]uint64{ @@ -194,7 +193,7 @@ var mtcCases = map[uint32]uint64{ } func TestMTC(t *testing.T) { - tableTest(t, MTC, mtcCases, stdEquals, "MTC") + tableTest(t, MTC, mtcCases, stdEquals[uint64], "MTC") } var sanCases = map[uint]bool{ @@ -212,7 +211,7 @@ func isSAN(n uint) bool { } func TestSAN(t *testing.T) { - tableTest(t, isSAN, sanCases, stdEquals, "isSAN") + tableTest(t, isSAN, sanCases, stdEquals[bool], "isSAN") } var expOrdCases = map[uint]bool{ @@ -223,7 +222,8 @@ var expOrdCases = map[uint]bool{ } func TestExponentsOrdered(t *testing.T) { - tableTest(t, exponentsOrdered, expOrdCases, stdEquals, "exponentsOrdered") + tableTest(t, exponentsOrdered, expOrdCases, stdEquals[bool], + "exponentsOrdered") } var practicalCases = map[uint]bool{ @@ -237,7 +237,7 @@ var practicalCases = map[uint]bool{ } func TestPractical(t *testing.T) { - tableTest(t, practical, practicalCases, stdEquals, "practical") + tableTest(t, practical, practicalCases, stdEquals[bool], "practical") } var typeCases = map[uint]CompositenessType{ @@ -255,7 +255,7 @@ var typeCases = map[uint]CompositenessType{ } func TestType(t *testing.T) { - tableTest(t, Type, typeCases, stdEquals, "Type") + tableTest(t, Type, typeCases, stdEquals[CompositenessType], "Type") } // ====== DIGIT MAP TESTS ====== @@ -302,7 +302,7 @@ var digitMapCases = map[uint][]DigitType{ } func TestDigitMap(t *testing.T) { - tableTest(t, DigitMap, digitMapCases, slices.Equal, "DigitMap") + tableTest(t, DigitMap, digitMapCases, sliceEquals[DigitType], "DigitMap") } // ensures GetDigitType(d, r) == DigitMap(r)[d]; @@ -383,12 +383,28 @@ func splitTest(a uintPair) uintPair { } func TestSplit(t *testing.T) { - tableTest(t, splitTest, splitCases, stdEquals, "Split") + tableTest(t, splitTest, splitCases, stdEquals[uintPair], "Split") } // to be used as the equal paramater for tableTest func stdEquals[T comparable](a, b T) bool { return a == b } +func mapEquals[K, V comparable](a, b map[K]V) bool { + for k, av := range a { + bv, ok := b[k] + if !ok || bv != av { + return false + } + } + for k, bv := range b { + av, ok := a[k] + if !ok || bv != av { + return false + } + } + return true +} + func setEquals[E comparable](a, b []E) bool { // use maps to simulate sets // aSet[a] == true means set contains a, false means not @@ -400,5 +416,19 @@ func setEquals[E comparable](a, b []E) bool { for _, j := range b { bSet[j] = true } - return maps.Equal(aSet, bSet) + return mapEquals(aSet, bSet) +} + +func sliceEquals[E comparable](a, b []E) bool { + if len(a) != len(b) { + return false + } + + for i := 0; i < len(a); i++ { + if a[i] != b[i] { + return false + } + } + + return true } diff --git a/factors/type.go b/factors/type.go index 919baef..3e116af 100644 --- a/factors/type.go +++ b/factors/type.go @@ -1,7 +1,5 @@ package factors -import "slices" - // The set of all colossaly abundant numbers that are small enough // to be stored in a uint64. // The first 15 are also the first 15 superior highly composites. @@ -69,9 +67,9 @@ const ( // Type determines the [CompositenessType] of a number. func Type(n uint) CompositenessType { - if slices.Contains(colossallyAbundantNums[:], uint64(n)) { + if contains(colossallyAbundantNums[:], uint64(n)) { return ColossallyAbundant - } else if slices.Contains(superabundantNums[:], uint64(n)) { + } else if contains(superabundantNums[:], uint64(n)) { return Superabundant } else if exponentsOrdered(n) { return OrderedExponent @@ -99,7 +97,7 @@ func exponentsOrdered(n uint) bool { } pf := PrimeFactorize(n) - maxPrime := slices.Max(pf.Primes()) + maxPrime := maxUints(pf.Primes()) for prime, prevPrime := uint(3), uint(2); prime <= maxPrime; { if pf.Exponent(prime) > pf.Exponent(prevPrime) { @@ -122,8 +120,7 @@ func practical(n uint) bool { } pf := PrimeFactorize(uint(n)) - primes := pf.Primes() - slices.Sort(primes) + primes := sortUints(pf.Primes()) // algorithm from Wikipedia for i := 0; i < pf.Size()-1; i++ { -- cgit v1.2.3