Advent of Code 2018 with Go

In the interest of testing out my new Gatsby blog setup here are a few solutions for the first few 2018 Advent of code problems. Go is an unpopular language for competitive programming problems but the simple syntax does make writing a solution feel kind of fun because you focus more on the problem and less on stylistic choices. Also I am learning Go and take any excuse to practice so I can grow up to be a big strong gopher some day.

Day 1

Given an input of signed integers, first return the total summation of the series, then monitor the state of the summation as it progresses and return the first sum that is reached twice. Multiple iterations of the summation are allowed for the second problem.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// Function to return a slice of ints given a file path
// where each line is a signed integer string
func readIntLines(path string) ([]int, error) {
	file, err := os.Open(path)
	if err != nil {
		return nil, err
	}
	defer file.Close()
	scanner := bufio.NewScanner(file)
	scanner.Split(bufio.ScanLines)
	var lines []int
	for scanner.Scan() {
		num, err := strconv.Atoi(scanner.Text())
		if err != nil {
			return nil, err
		}
		lines = append(lines, num)
	}
	return lines, nil
}

// Read file and calculate summation.
func main() {
	lines, err := readIntLines("input.txt")
	if err != nil {
		fmt.Println(err)
	}
	// Hold value of current sum and a map of
	// sum frequencies over time.
	sum := 0
	freq := map[int]int{}
	looking := true
	iterations := 0

	// Repeat until a duplicate frequency occurs.
	for looking {
		// Always return the frequency after one iteration.
		// For Part: 1 of problem.
		if iterations == 1 {
			fmt.Println(sum)
		}

		// Sum lines in input.
		for _, line := range lines {
			sum = sum + line
			// Print if a duplicate frequency is found.
			if _, ok := freq[sum]; ok {
				fmt.Printf("First recurring freq: %d\n", sum)
				looking = false
			}
			// Mark each frequency as it occurs.
			freq[sum] = freq[sum] + 1

		}
		iterations++
	}
}

Day 2

Given a list of strings first find any strings that have either two repetitions of a character, or three repretitions. Then find a pair of strings with only one character mismatching. Order counts.

package main

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

// Function to return a slice of strings from lines in a file.
func readLines(path string) ([]string, error) {
	file, err := os.Open(path)
	if err != nil {
		return nil, err
	}
	defer file.Close()
	scanner := bufio.NewScanner(file)
	scanner.Split(bufio.ScanLines)
	var lines []string
	for scanner.Scan() {
		if err != nil {
			return nil, err
		}
		lines = append(lines, scanner.Text())
	}
	return lines, nil
}

// Iterate through the characters in a string.
// Keep track of charMap state to track current reps of 2 or 3.
func countChars(s string) (bool, bool) {
	charMap := map[rune]int{}
	hasTwo := 0
	hasThree := 0
	for _, rune := range s {
		charMap[rune] = charMap[rune] + 1
		if charMap[rune] == 2 {
			hasTwo++
		} else if charMap[rune] == 3 {
			hasTwo--
			hasThree++
		} else if charMap[rune] == 4 {
			hasThree--
		}
	}
	return hasTwo > 0, hasThree > 0
}

// Count mismatches between two strings.
func countDiff(s string, s2 string) int {
	diff := 0
	for i := range s {
		if s[i] != s2[i] {
			diff++
		}
	}
	return diff
}

// Create a map of strings, where the key is the
// first or second half of the string.
func partition(list []string, prefix bool) map[string][]string {
	stringMap := map[string][]string{}
	for _, s := range list {
		idx := ""
		if prefix {
			idx = s[:len(s)/2]
		} else {
			idx = s[len(s)/2:]
		}
		stringMap[idx] = append(stringMap[idx], s)
	}
	return stringMap
}

func main() {
	ids, err := readLines("input.txt")
	if err != nil {
		fmt.Println(err)
	}

	// Find count of strings with two repetitions or 3 repetitions.
	// Multiply to get answer for problem 1.
	twos := 0
	threes := 0
	for _, id := range ids {
		// Check if this id has twos or threes instances.
		hasTwo, hasThree := countChars(id)
		if hasTwo {
			twos++
		}
		if hasThree {
			threes++
		}
	}
	fmt.Printf("%d times %d is: %d \n", twos, threes, twos*threes)

	// Find strings with one difference for problem 2.
	frontPartition := partition(ids, true)
	endPartition := partition(ids, false)
	results := []string{}

	// Group strings with same first half and find matches.
	for _, v := range frontPartition {
		for _, id := range v {
			for _, id2 := range v {
				if countDiff(id, id2) == 1 {
					results = append(results, id)
				}
			}
		}
	}

	// Group strings with same second half and find matches.
	for _, v := range endPartition {
		for _, id := range v {
			for _, id2 := range v {
				if countDiff(id, id2) == 1 {
					results = append(results, id)
				}
			}
		}
	}
	fmt.Println(results)
}

Day 3

Provided with a list of strings which represent a claim on space in a 1000X1000 grid. First detect any grid spaces which are double occupied. Then detect a claim which does not conflict on any space.

package main

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

// Struct representing a claim.
type claim struct {
	Number string
	Top    int
	Left   int
	Width  int
	Height int
}

// Function to return a slice of strings from lines in a file.
func readLines(path string) ([]string, error) {
	file, err := os.Open(path)
	if err != nil {
		return nil, err
	}
	defer file.Close()
	scanner := bufio.NewScanner(file)
	scanner.Split(bufio.ScanLines)
	var lines []string
	for scanner.Scan() {
		if err != nil {
			return nil, err
		}
		lines = append(lines, scanner.Text())
	}
	return lines, nil
}

// Split on deliminators in input format.
func splitFunction(r rune) bool {
	return r == '@' || r == ',' || r == ':' || r == 'x'
}

// Read an input line into a claim struct.
func parseLine(s string) claim {
	parts := strings.FieldsFunc(s, splitFunction)
	left, err := strconv.Atoi(strings.TrimSpace(parts[1]))
	top, err := strconv.Atoi(strings.TrimSpace(parts[2]))
	width, err := strconv.Atoi(strings.TrimSpace(parts[3]))
	height, err := strconv.Atoi(strings.TrimSpace(parts[4]))
	if err != nil {
		fmt.Println("Error parsing a claim.")
	}
	ret := claim{
		Number: strings.TrimSpace(parts[0]),
		Top:    top,
		Left:   left,
		Width:  width,
		Height: height,
	}
	return ret
}

// Given a claim, map claim to every space in grid that it occupies.
func assignClaim(c claim,
                 layout *[1001][1001][]claim,
                 overlaps map[string]bool
				) {
	for i := c.Left; i <= c.Width+c.Left-1; i++ {
		for j := c.Top; j <= c.Height+c.Top-1; j++ {
			layout[i][j] = append(layout[i][j], c)
			if len(layout[i][j]) > 1 {
				for _, key := range layout[i][j] {
					overlaps[key.Number] = true
				}
			}
		}
	}
}

// Iterate through array and count overlapping spaces.
func readDuplicates(layout *[1001][1001][]claim) int {
	duplicates := 0
	for i := 0; i <= 1000; i++ {
		for j := 0; j <= 1000; j++ {
			if len(layout[i][j]) > 1 {
				duplicates++
			}
		}
	}
	return duplicates

}

func main() {
	// Read File Into Array of Strings
	parcels, err := readLines("input.txt")
	if err != nil {
		fmt.Println(err)
	}
	layout := [1001][1001][]claim{}
	overlaps := map[string]bool{}

	// Iterate through parcels and map to 2d Array.
	for _, parcel := range parcels {
		claim := parseLine(parcel)
		assignClaim(claim, &layout, overlaps)
	}

	// Print the number of lines with overlaping claims.
	fmt.Println(readDuplicates(&layout))

	// Iterate through all parcels to find one
	// that has not been marked a duplicate ever.
	for _, parcel := range parcels {
		claim := parseLine(parcel)
		_, ok := overlaps[claim.Number]
		if !ok {
			fmt.Printf("Key not found value is: %s, \n", claim.Number)
		}
	}

}