143 lines
2.4 KiB
Go
143 lines
2.4 KiB
Go
package main
|
|
|
|
import (
|
|
"bufio"
|
|
"fmt"
|
|
"os"
|
|
"strings"
|
|
"time"
|
|
)
|
|
|
|
const FILE_PATH = "./input.txt"
|
|
|
|
//const FILE_PATH = "./sample.txt"
|
|
|
|
func LoadInput(filename string) ([]string, error) {
|
|
file, err := os.Open(filename)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
defer file.Close()
|
|
|
|
var lines []string
|
|
scanner := bufio.NewScanner(file)
|
|
for scanner.Scan() {
|
|
lines = append(lines, scanner.Text())
|
|
}
|
|
|
|
if err := scanner.Err(); err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
return lines, nil
|
|
}
|
|
|
|
type Puzzle struct {
|
|
poss []string
|
|
lines []string
|
|
}
|
|
|
|
type structuredInput = Puzzle
|
|
|
|
func TransformInput(lines []string) structuredInput {
|
|
return Puzzle{strings.Split(lines[0], ", "), lines[2:]}
|
|
}
|
|
|
|
var poss []string
|
|
var cachePart1 map[string]bool = make(map[string]bool)
|
|
|
|
func hasSolution(input string) bool {
|
|
if len(input) == 0 {
|
|
return true
|
|
}
|
|
|
|
value, ok := cachePart1[input]
|
|
|
|
if ok {
|
|
return value
|
|
}
|
|
|
|
var result = false
|
|
|
|
for i := 0; i < len(poss); i++ {
|
|
if len(input) >= len(poss[i]) && input[:len(poss[i])] == poss[i] && hasSolution(input[len(poss[i]):]) {
|
|
result = true
|
|
break
|
|
}
|
|
}
|
|
|
|
cachePart1[input] = result
|
|
return result
|
|
}
|
|
|
|
func Part1(input structuredInput) int {
|
|
var result = 0
|
|
poss = input.poss
|
|
|
|
for _, line := range input.lines {
|
|
if hasSolution(line) {
|
|
result++
|
|
}
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
var cachePart2 map[string]int = make(map[string]int)
|
|
|
|
func findSolutionCount(input string) int {
|
|
if len(input) == 0 {
|
|
return 1
|
|
}
|
|
|
|
value, ok := cachePart2[input]
|
|
|
|
if ok {
|
|
return value
|
|
}
|
|
|
|
var result = 0
|
|
|
|
for i := 0; i < len(poss); i++ {
|
|
if len(input) >= len(poss[i]) && input[:len(poss[i])] == poss[i] {
|
|
result += findSolutionCount(input[len(poss[i]):])
|
|
}
|
|
}
|
|
|
|
cachePart2[input] = result
|
|
return result
|
|
}
|
|
|
|
func Part2(input structuredInput) int {
|
|
var result = 0
|
|
poss = input.poss
|
|
|
|
for _, line := range input.lines {
|
|
result += findSolutionCount(line)
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
func main() {
|
|
var start time.Time
|
|
var elapsed time.Duration = 0
|
|
input, err := LoadInput(FILE_PATH)
|
|
if err != nil {
|
|
fmt.Println("Error loading input:", err)
|
|
return
|
|
}
|
|
|
|
structuredInput := TransformInput(input)
|
|
fmt.Println("Structured Input:", structuredInput)
|
|
|
|
start = time.Now()
|
|
fmt.Println("Solution Part 1: ", Part1(structuredInput))
|
|
elapsed = time.Since(start)
|
|
fmt.Printf("Part 1 took %s\n", elapsed)
|
|
|
|
start = time.Now()
|
|
fmt.Println("Solution Part 2: ", Part2(structuredInput))
|
|
elapsed = time.Since(start)
|
|
fmt.Printf("Part 2 took %s\n", elapsed)
|
|
}
|