fast.go

package main

import (
	"fmt"
)

var basePattern = []int{0, 1, 0, -1}

const input = "59708072843556858145230522180223745694544745622336045476506437914986923372260274801316091345126141549522285839402701823884690004497674132615520871839943084040979940198142892825326110513041581064388583488930891380942485307732666485384523705852790683809812073738758055115293090635233887206040961042759996972844810891420692117353333665907710709020698487019805669782598004799421226356372885464480818196786256472944761036204897548977647880837284232444863230958576095091824226426501119748518640709592225529707891969295441026284304137606735506294604060549102824977720776272463738349154440565501914642111802044575388635071779775767726626682303495430936326809"

const numPhases = 100
const numRepetitions = 10000

func getPuzzleInput() []int {
	result := make([]int, len(input))
	for i, ch := range input {
		result[i] = int(ch - '0')
	}
	return result
}

func expandPattern(pattern []int, stepSize, desiredSize int) []int {
	expanded := make([]int, desiredSize)
	repetitionsLeft := stepSize
	for i, j := 0, 0; i < desiredSize; i++ {
		expanded[i] = pattern[j]
		repetitionsLeft--
		if repetitionsLeft == 0 {
			j = (j + 1) % len(pattern)
			repetitionsLeft = stepSize
		}
	}
	return expanded
}

func expandValues(values []int, numRepetitions int) []int {
	expandedValues := make([]int, len(values)*numRepetitions)
	for i := 0; i < numRepetitions; i++ {
		copy(expandedValues[i*len(values):i*len(values)+len(values)], values)
	}

	// XXX sanity check
	for i := 0; i < numRepetitions; i++ {
		offset := i * len(values)
		for j, v := range values {
			if v != expandedValues[offset+j] {
				panic("fuck fuck fuck")
			}
		}
	}

	return expandedValues
}

func applyRepeatedFFT3(values []int, numRepetitions, numPhases, offset int) []int {
	values = expandValues(values, numRepetitions)

	indices := make([][]int, numPhases)
	lastIndices := make([]int, 0, 8)
	for i := offset; i < offset+8; i++ {
		lastIndices = append(lastIndices, i)
	}
	indices[numPhases-1] = lastIndices

	for i := numPhases - 2; i >= numPhases-2; i-- {
		nextIndices := indices[i+1]
		seen := make([]bool, len(values))
		// XXX var name
		idx := make([]int, 0)

		for _, i := range nextIndices {
			stepSize := i + 1
			currentStateIndex := 1 // basePattern[0] is 0, so we can just skip that entirely

			for j := i; j < len(values); j += stepSize {
				mult := basePattern[currentStateIndex]
				currentStateIndex = (currentStateIndex + 1) % len(basePattern)
				end := j + stepSize
				if end >= len(values) {
					end = len(values)
				}

				if mult == 0 {
					continue
				}

				for k := j; k < end; k++ {
					if !seen[k] {
						seen[k] = true
						idx = append(idx, k)
					}
				}
			}
		}

		indices[i] = idx
	}

	// I *believe* this is correct
	for i := numPhases - 2; i >= 0; i-- {
		indices[i] = indices[numPhases-2]
	}

	for p := 0; p < numPhases; p++ {
		idx := indices[p]
		nextValues := make([]int, len(values))

		// XXX parallelize
		for _, i := range idx {
			r := 0

			stepSize := i + 1
			currentStateIndex := 1 // basePattern[0] is 0, so we can just skip that entirely

			for j := i; j < len(values); j += stepSize {
				mult := basePattern[currentStateIndex]
				currentStateIndex = (currentStateIndex + 1) & 0x04
				end := j + stepSize
				if end >= len(values) {
					end = len(values)
				}

				// XXX there might be redundant mults/adds happening here
				if mult == 0 {
					continue
				} else if mult == 1 {
					for k := j; k < end; k++ {
						r += values[k]
					}
				} else {
					for k := j; k < end; k++ {
						r -= values[k]
					}
				}
			}
			if r < 0 {
				r *= -1
			}
			nextValues[i] = r % 10
		}
		values = nextValues
		break // XXX DEBUG
	}
	return values
}

func main() {
	values := getPuzzleInput()
	offset := 5970807
	fmt.Println(applyRepeatedFFT3(values, numRepetitions, 10, offset)[offset : offset+8])
}

slow.go

package main

import (
	"fmt"
)

var basePattern = []int{0, 1, 0, -1}

const input = "59708072843556858145230522180223745694544745622336045476506437914986923372260274801316091345126141549522285839402701823884690004497674132615520871839943084040979940198142892825326110513041581064388583488930891380942485307732666485384523705852790683809812073738758055115293090635233887206040961042759996972844810891420692117353333665907710709020698487019805669782598004799421226356372885464480818196786256472944761036204897548977647880837284232444863230958576095091824226426501119748518640709592225529707891969295441026284304137606735506294604060549102824977720776272463738349154440565501914642111802044575388635071779775767726626682303495430936326809"

const numPhases = 100
const numRepetitions = 10000

func getPuzzleInput() []int {
	result := make([]int, len(input))
	for i, ch := range input {
		result[i] = int(ch - '0')
	}
	return result
}

func expandPattern(pattern []int, stepSize, desiredSize int) []int {
	expanded := make([]int, desiredSize)
	repetitionsLeft := stepSize
	for i, j := 0, 0; i < desiredSize; i++ {
		expanded[i] = pattern[j]
		repetitionsLeft--
		if repetitionsLeft == 0 {
			j = (j + 1) % len(pattern)
			repetitionsLeft = stepSize
		}
	}
	return expanded
}

func expandValues(values []int, numRepetitions int) []int {
	expandedValues := make([]int, len(values)*numRepetitions)
	for i := 0; i < numRepetitions; i++ {
		copy(expandedValues[i*len(values):i*len(values)+len(values)], values)
	}

	// XXX sanity check
	for i := 0; i < numRepetitions; i++ {
		offset := i * len(values)
		for j, v := range values {
			if v != expandedValues[offset+j] {
				panic("fuck fuck fuck")
			}
		}
	}

	return expandedValues
}

func applyRepeatedFFT3(values []int, numRepetitions, numPhases, offset int) []int {
	values = expandValues(values, numRepetitions)

	indices := make([][]int, numPhases)
	lastIndices := make([]int, 0, 8)
	for i := offset; i < offset+8; i++ {
		lastIndices = append(lastIndices, i)
	}
	indices[numPhases-1] = lastIndices

	for i := numPhases - 2; i >= numPhases-2; i-- {
		nextIndices := indices[i+1]
		seen := make([]bool, len(values))
		// XXX var name
		idx := make([]int, 0)

		for _, i := range nextIndices {
			stepSize := i + 1
			currentStateIndex := 1 // basePattern[0] is 0, so we can just skip that entirely

			for j := i; j < len(values); j += stepSize {
				mult := basePattern[currentStateIndex]
				currentStateIndex = (currentStateIndex + 1) % len(basePattern)
				end := j + stepSize
				if end >= len(values) {
					end = len(values)
				}

				if mult == 0 {
					continue
				}

				for k := j; k < end; k++ {
					if !seen[k] {
						seen[k] = true
						idx = append(idx, k)
					}
				}
			}
		}

		indices[i] = idx
	}

	// I *believe* this is correct
	for i := numPhases - 2; i >= 0; i-- {
		indices[i] = indices[numPhases-2]
	}

	for p := 0; p < numPhases; p++ {
		idx := indices[p]
		nextValues := make([]int, len(values))

		// XXX parallelize
		for _, i := range idx {
			r := 0

			stepSize := i + 1
			currentStateIndex := 1 // basePattern[0] is 0, so we can just skip that entirely

			for j := i; j < len(values); j += stepSize {
				mult := basePattern[currentStateIndex]
				currentStateIndex = (currentStateIndex + 1) & 0x04
				end := j + stepSize
				if end >= len(values) {
					end = len(values)
				}

				// XXX there might be redundant mults/adds happening here
				if mult == 0 {
					continue
				} else if mult == 1 {
					sum := 0
					for k := j; k < end; k++ {
						sum += values[k]
					}
					r += sum
				} else {
					sum := 0
					for k := j; k < end; k++ {
						sum += values[k]
					}
					r -= sum
				}
			}
			if r < 0 {
				r *= -1
			}
			nextValues[i] = r % 10
		}
		values = nextValues
		break // XXX DEBUG
	}
	return values
}

func main() {
	values := getPuzzleInput()
	offset := 5970807
	fmt.Println(applyRepeatedFFT3(values, numRepetitions, 10, offset)[offset : offset+8])
}