day19

day19.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func analyzeDesignFormation(availableTowels []string, requested string) (int, bool) {
	n := len(requested)
	combinationCounts := make([]int, n+1) // combinationCounts[i] indicates the number of ways to form requested[:i]
	combinationCounts[0] = 1              // Base case: one way to form an empty string

	// Build the combinationCounts table
	for i := 1; i <= n; i++ {
		for _, towel := range availableTowels {
			towelLen := len(towel)
			if i >= towelLen && requested[i-towelLen:i] == towel {
				combinationCounts[i] += combinationCounts[i-towelLen]
			}
		}
	}

	return combinationCounts[n], combinationCounts[n] > 0 // Return the number of combinations and a boolean indicating if it can be formed
}

func main() {
	// Open the input file
	file, err := os.Open("input.txt")
	if err != nil {
		fmt.Printf("Error opening file: %v\n", err)
		return
	}
	defer file.Close()

	// Read the file line by line
	scanner := bufio.NewScanner(file)
	lines := []string{}
	for scanner.Scan() {
		lines = append(lines, scanner.Text())
	}
	if err := scanner.Err(); err != nil {
		fmt.Printf("Error reading file: %v\n", err)
		return
	}

	// Parse the input
	if len(lines) < 2 {
		fmt.Println("Invalid input format: not enough lines")
		return
	}

	// First line: list of available colors
	availableTowels := strings.Split(strings.TrimSpace(lines[0]), ", ")

	// Remaining lines (after the blank line): requested designs
	var requestedTowels []string
	for _, line := range lines[2:] { // Skip the blank line
		line = strings.TrimSpace(line)
		if line != "" {
			requestedTowels = append(requestedTowels, line)
		}
	}

	// Count total number of combinations to form all designs
	totalCombinations := 0
	totalFormable := 0
	for _, towel := range requestedTowels {
		combinations, formable := analyzeDesignFormation(availableTowels, towel)
		totalCombinations += combinations
		if formable {
			totalFormable++
		}
	}

	// Print the total result
	fmt.Printf("Total number of combinations to form all designs: %d\n", totalCombinations)
	fmt.Printf("Total number of designs that can be formed: %d\n", totalFormable)
}