fizzbuzz.go

package main

import (
	"math"
)

// approximateFizzBuzzBufferLen approximates the length of the buffer needed
// to store the sequence generated by a call to fizzbuzz with given parameters.
// It should always return a buffer length close (about +-10 bytes) to the real
// final buffer length needed.
// It applies the given formula:
// result = [O(S1) - O(Lcm)] * [L(S1) - A1] + [O(S2) - O(Lcm)] * [L(S2) - A2] + [O(Lcm) * (L(Lcm) - ALcm] + D + C
// where
// O is a function giving the number of occurrences of a given string in limit numbers
// L is a function giving the number of bytes of a given string
// S1, S2, Lcm are str1, str2, and str1 + str2 respectively
// A1, A2, ALcm are the average numbers of characters per number in the contiguous sequence:
//  M,M+1,...,limit
//  where M is the smallest number containing as many characters as the input number
//  A1 is average for S1, A2 that of S2 and ALcm that of Lcm respectively
// D is the number of digits in the sequence of numbers from 1 to limit
// C is the number of commas in the generated sequence, that is limit - 1
func approximateFizzBuzzBufferLen(d1, d2, limit int, str1, str2 string) int {
	lenS1, lenS2 := len(str1), len(str2)
	lenLcm := lenS1 + lenS2
	lcm := lcm(d1, d2)
	// numbers of occurrences of each replacer based on its "assigned" divisor
	oS1, oS2, oLcm := limit/d1, limit/d2, limit/lcm
	// number of digits in the contiguous number sequence from 1 to limit
	D := numberOfDigits(limit)

	// process min numbers with same number of digits as d1, d2 and lcm
	mpS1, _ := minimalPowerOf10(d1)
	mpS2, _ := minimalPowerOf10(d2)
	mpLcm, _ := minimalPowerOf10(lcm)

	// process average of added characters by replacement of divisors with
	// their corresponding strings
	AS1 := float64(D-numberOfDigits(lenS1-1)) / float64(limit-(mpS1-1))
	AS2 := float64(D-numberOfDigits(lenS2-1)) / float64(limit-(mpS2-1))
	ALcm := float64(D-numberOfDigits(lenLcm-1)) / float64(limit-(mpLcm-1))

	// process each bracketed part independently for readability
	bufferSizeS1 := float64(oS1-oLcm) * (float64(lenS1) - AS1)
	bufferSizeS2 := float64(oS2-oLcm) * (float64(lenS2) - AS2)
	bufferSizeLcm := float64(oLcm) * (float64(lenLcm) - ALcm)
	nbCommas := limit - 1

	// merge everything
	bufferSize := D + nbCommas + int(math.Ceil(bufferSizeS1+bufferSizeS2+bufferSizeLcm))
	return bufferSize
}

// fizzBuzz is the main function of the project, it processes the output
// of the fizzbuzz procedure for the five given parameters.
// It is designed to make the least allocations possible and will not perform
// any check on inputs.
func fizzBuzz(d1, d2 int, limit int, str1, str2 string) []byte {

	// add 100 to be certain to have at least enough space
	buf := make([]byte, approximateFizzBuzzBufferLen(d1, d2, limit, str1, str2) + 100)
	n := 0
	len1, len2, len3 := len(str1), len(str2), len(str1) + len(str2)
	g := newGen()
	for i := 1; i <= limit; i++ {
		// benchmarked using lcm of d1 and d2 here but it seems to be
		// less performant (surprisingly...)
		if i%d1 == 0 && i%d2 == 0 {
			copy(buf[n:], str1 + str2)
			n += len3
		} else if i%d1 == 0 {
			copy(buf[n:], str1)
			n += len1
		} else if i%d2 == 0 {
			copy(buf[n:], str2)
			n += len2
		} else {
			n += g.fillNext(buf[n:])
		}

		buf[n] = ','
		n++
		g.inc()
	}

	return buf[:n-1]
}