138 lines
2.6 KiB
Go
138 lines
2.6 KiB
Go
package main
|
|
|
|
import (
|
|
"bufio"
|
|
"bytes"
|
|
"fmt"
|
|
"log"
|
|
"os"
|
|
"strconv"
|
|
"strings"
|
|
)
|
|
|
|
func scanComma(data []byte, atEOF bool) (advance int, token []byte, err error) {
|
|
if atEOF && len(data) == 0 {
|
|
return 0, nil, nil
|
|
}
|
|
if i := bytes.IndexByte(data, ','); i > 0 {
|
|
return i + 1, data[0:i], nil
|
|
}
|
|
if atEOF {
|
|
if len(data) > 0 && data[len(data)-1] == '\n' {
|
|
return len(data), data[0 : len(data)-1], nil
|
|
}
|
|
return len(data), data, nil
|
|
}
|
|
return 0, nil, nil
|
|
|
|
}
|
|
|
|
func check(err error) {
|
|
if err != nil {
|
|
log.Fatal(err)
|
|
}
|
|
}
|
|
|
|
func intPow(base int, exponent int) int {
|
|
|
|
if exponent == 0 {
|
|
return 1
|
|
} else if exponent == 1 {
|
|
return base
|
|
}
|
|
|
|
val := base
|
|
remaining_mults := exponent - 1
|
|
for ; remaining_mults > 0; remaining_mults-- {
|
|
val = val * base
|
|
}
|
|
return val
|
|
}
|
|
|
|
func makeCandidateInt(prefix int, n_repeats int) (int, error) {
|
|
prefixStr := strconv.Itoa(prefix)
|
|
|
|
var candidateBuilder strings.Builder
|
|
|
|
for ; n_repeats > 0; n_repeats-- {
|
|
candidateBuilder.WriteString(prefixStr)
|
|
}
|
|
|
|
return strconv.Atoi(candidateBuilder.String())
|
|
|
|
}
|
|
|
|
func largestPrefix(rangeEnd string) (int, error) {
|
|
if len(rangeEnd)%2 == 0 {
|
|
return strconv.Atoi(rangeEnd[0 : len(rangeEnd)/2])
|
|
} else {
|
|
prefixLen := (len(rangeEnd) - 1) / 2
|
|
return intPow(10, prefixLen) - 1, nil
|
|
}
|
|
}
|
|
|
|
func sumInt(seq []int) int {
|
|
sum := 0
|
|
|
|
for _, val := range seq {
|
|
sum += val
|
|
}
|
|
return sum
|
|
}
|
|
|
|
func getInvalidsForRange(start int, end int) []int {
|
|
maxPrefix, err := largestPrefix(strconv.Itoa(end))
|
|
check(err)
|
|
|
|
invalidIds := make(map[int]struct{})
|
|
|
|
fmt.Printf("Considering range %d - %d, max prefix %d\n", start, end, maxPrefix)
|
|
for candidatePrefix := 1; candidatePrefix <= maxPrefix; candidatePrefix++ {
|
|
for n_repeats := 2; ; n_repeats++ {
|
|
candidateInt, err := makeCandidateInt(candidatePrefix, n_repeats)
|
|
check(err)
|
|
|
|
if candidateInt > end {
|
|
break
|
|
}
|
|
|
|
if (start <= candidateInt) && (candidateInt <= end) {
|
|
fmt.Printf("Can use %d\n", candidateInt)
|
|
invalidIds[candidateInt] = struct{}{}
|
|
}
|
|
}
|
|
}
|
|
|
|
invalidIdList := make([]int, 0, len(invalidIds))
|
|
|
|
for invalidId := range invalidIds {
|
|
invalidIdList = append(invalidIdList, invalidId)
|
|
|
|
}
|
|
return invalidIdList
|
|
}
|
|
|
|
func main() {
|
|
file, err := os.Open("two.txt")
|
|
check(err)
|
|
defer file.Close()
|
|
|
|
invalidIdSum := 0
|
|
|
|
scanner := bufio.NewScanner(file)
|
|
scanner.Split(scanComma)
|
|
|
|
for scanner.Scan() {
|
|
idRange := scanner.Text()
|
|
|
|
idRangeSplit := strings.SplitN(idRange, "-", 2)
|
|
|
|
rangeStart, err := strconv.Atoi(idRangeSplit[0])
|
|
check(err)
|
|
rangeEnd, err := strconv.Atoi(idRangeSplit[1])
|
|
check(err)
|
|
|
|
invalidIdSum += sumInt(getInvalidsForRange(rangeStart, rangeEnd))
|
|
}
|
|
fmt.Printf("%d\n", invalidIdSum)
|
|
}
|