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")
}