raylee · February 12, 2022 15:55
diff --git a/letterbag.go b/letterbag.go
 // Package letterbag provides operations on bags of letters.
 package letterbag

 import "errors"

 // This implementation trades off perfect accuracy for speed and space. For a
 // more straightforward version substitute `type Bag [26]int` and adjust
 // accordingly.
 //
 // Below the 'a' to 'z' alphabet is represented by 26 prime numbers. Words are
 // mapped to integers modulo 1<<64 by multiplying their letter values together.
 // As multiplication is commutative (a*b == b*a), the result is independent of
 // the order of the letters in the word. It acts like a bag of letters.
 //
 // Letters can be added to the bag by multiplying a new letter's value, and
 // removed by dividing. Factoring retrieves the individual letters.
 //
 // As for accuracy, log base 103 of 1<<64 is > 9, so all words below ten letters
 // can fit without rollover. The space is sparse so the odds of a collision are
 // low, but non-zero.

 type Bag uint64

 const Empty = Bag(1)

 // The prime alphabet starts with 3 as 2 is not coprime with the author's
 // computer. ie, there is no integer we can multiply against 2 to get a
 // residue of 1 (because multiplying by 2 is the same as << 1). Leaving 2
 // out guarantees that each valid Bag will have a modular inverse.
 // I never claimed this wasn't tricky.
 var alphabet = []Bag{
 	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
 	47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
 }

 // NewBag returns a bag containing the letters in s.
 func NewBag(s string) Bag {
 	return Empty.Insert(s)
 }

 // Insert adds all English lowercase letters in s into the Bag.
 func (b Bag) Insert(s string) Bag {
 	for i := 0; i < len(s); i++ {
 		r := s[i]
 		if r >= 'a' && r <= 'z' {
 			b *= alphabet[r-'a']
 		}
 	}
 	return b
 }

 // Add returns a new bag containing b and other combined.
 func (b Bag) Add(other Bag) Bag {
 	return b * other
 }

 // Subtract letters in bag c from b. If c contains letters not in b, the result is
 // undefined.
 func (b Bag) Subtract(c Bag) Bag {
 	// Instead of returning b/c, we multiply b by the modular inverse of c. This
 	// allows us to handle cases where one or both Bags have rolled over. On the
 	// downside, this means we're multiplying to divide, to subtract.

 	i := modularInverse(uint64(c))
 	return b * Bag(i) // Which is the same as b.Add(i).
 }

 // modularInverse returns a value x such that (c*x) mod (1<<64) = 1.
 func modularInverse(c uint64) uint64 {
 	// Use Newton's method to find a zero of f(x) = 1/x - c. Each round doubles
 	// the accuracy. Taking the bottom three bits as a word, each valid state is
 	// its own inverse: (1*1, 3*3, 5*5, 7*7) mod 8 = (1, 1, 1, 1). Therefore
 	// starting with c as our initial guess gives 3+ bits of accuracy.

 	// For discussion why Newton's method is valid in modular arithmetic and a
 	// faster algorithm see https://arxiv.org/abs/1303.0328 and
 	// https://marc-b-reynolds.github.io/math/2017/09/18/ModInverse.html.

 	x := c       // 3 bits of accuracy
 	x *= 2 - x*c // doubled to 6
 	x *= 2 - x*c // 12
 	x *= 2 - x*c // 24
 	x *= 2 - x*c // 48
 	x *= 2 - x*c // 96

 	return x
 }

 // String attempts to convert a bag of letters to a string in alphabetical
 // order. If the bag contains unknown letters or overflowed, "?" is returned.
 func (composite Bag) String() string {
 	var s string
 	for i := 0; i < 26 && composite > 1; {
 		p := alphabet[i]
 		if composite%p == 0 {
 			s += string(rune('a' + i))
 			composite /= p
 		} else {
 			i++ // check the next prime
 		}
 	}
 	if composite > 1 {
 		return "?"
 	}
 	return s
 }

 func CodeReview() error {
 	return errors.New("too much magic")
 }
	// Package letterbag provides operations on bags of letters.
	package letterbag

	import "errors"

	// This implementation trades off perfect accuracy for speed and space. For a
	// more straightforward version substitute `type Bag [26]int` and adjust
	// accordingly.
	//
	// Below the 'a' to 'z' alphabet is represented by 26 prime numbers. Words are
	// mapped to integers modulo 1<<64 by multiplying their letter values together.
	// As multiplication is commutative (ab == ba), the result is independent of
	// the order of the letters in the word. It acts like a bag of letters.
	//
	// Letters can be added to the bag by multiplying a new letter's value, and
	// removed by dividing. Factoring retrieves the individual letters.
	//
	// As for accuracy, log base 103 of 1<<64 is > 9, so all words below ten letters
	// can fit without rollover. The space is sparse so the odds of a collision are
	// low, but non-zero.

	type Bag uint64

	const Empty = Bag(1)

	// The prime alphabet starts with 3 as 2 is not coprime with the author's
	// computer. ie, there is no integer we can multiply against 2 to get a
	// residue of 1 (because multiplying by 2 is the same as << 1). Leaving 2
	// out guarantees that each valid Bag will have a modular inverse.
	// I never claimed this wasn't tricky.
	var alphabet = []Bag{
	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
	47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
	}

	// NewBag returns a bag containing the letters in s.
	func NewBag(s string) Bag {
	return Empty.Insert(s)
	}

	// Insert adds all English lowercase letters in s into the Bag.
	func (b Bag) Insert(s string) Bag {
	for i := 0; i < len(s); i++ {
	r := s[i]
	if r >= 'a' && r <= 'z' {
	b *= alphabet[r-'a']
	}
	}
	return b
	}

	// Add returns a new bag containing b and other combined.
	func (b Bag) Add(other Bag) Bag {
	return b * other
	}

	// Subtract letters in bag c from b. If c contains letters not in b, the result is
	// undefined.
	func (b Bag) Subtract(c Bag) Bag {
	// Instead of returning b/c, we multiply b by the modular inverse of c. This
	// allows us to handle cases where one or both Bags have rolled over. On the
	// downside, this means we're multiplying to divide, to subtract.

	i := modularInverse(uint64(c))
	return b * Bag(i) // Which is the same as b.Add(i).
	}

	// modularInverse returns a value x such that (c*x) mod (1<<64) = 1.
	func modularInverse(c uint64) uint64 {
	// Use Newton's method to find a zero of f(x) = 1/x - c. Each round doubles
	// the accuracy. Taking the bottom three bits as a word, each valid state is
	// its own inverse: (11, 33, 55, 77) mod 8 = (1, 1, 1, 1). Therefore
	// starting with c as our initial guess gives 3+ bits of accuracy.

	// For discussion why Newton's method is valid in modular arithmetic and a
	// faster algorithm see https://arxiv.org/abs/1303.0328 and
	// https://marc-b-reynolds.github.io/math/2017/09/18/ModInverse.html.

	x := c // 3 bits of accuracy
	x = 2 - xc // doubled to 6
	x = 2 - xc // 12
	x = 2 - xc // 24
	x = 2 - xc // 48
	x = 2 - xc // 96

	return x
	}

	// String attempts to convert a bag of letters to a string in alphabetical
	// order. If the bag contains unknown letters or overflowed, "?" is returned.
	func (composite Bag) String() string {
	var s string
	for i := 0; i < 26 && composite > 1; {
	p := alphabet[i]
	if composite%p == 0 {
	s += string(rune('a' + i))
	composite /= p
	} else {
	i++ // check the next prime
	}
	}
	if composite > 1 {
	return "?"
	}
	return s
	}

	func CodeReview() error {
	return errors.New("too much magic")
	}