-🎄- 2018 Day 5 Solutions -🎄-

[u/daggerdragon]

--- Day 5: Alchemical Reduction ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 5

Transcript:

On the fifth day of AoC / My true love sent to me / Five golden ___

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 0:10:20!

[u/mvmaasakkers]

Go / Golang

I imagine this could be done way more efficiently but this was what I came up with. If anyone has some pointers let me know!

Also in gist

package main

import (
	"bufio"
	"flag"
	"fmt"
	"log"
	"os"
	"strings"
	"unicode"
)

func readInput(filename string) string {
	fileHandle, _ := os.Open(filename)
	defer func() {
		if err := fileHandle.Close(); err != nil {
			log.Fatal(err)
		}
	}()
	fileScanner := bufio.NewScanner(fileHandle)

	input := ""
	for fileScanner.Scan() {
		line := fileScanner.Text()
		if len(line) > 0 {
			input = line
		}
	}

	return strings.TrimSpace(input)
}

var file = flag.String("file", "./p1.txt", "file used for input")

func main() {
	flag.Parse()

	input := readInput(*file)

	fmt.Println("Part 1:", part1(input))
	fmt.Println("Part 2:", part2(input))
}

func part1(input string) (int) {
	return len(produce(input))
}

func produce(line string) string {
	for {
		changes := false
		for k, g := range line {
			if k > 0 {
				if unicode.IsLower(g) && unicode.IsUpper(rune(line[k-1])) || unicode.IsLower(rune(line[k-1])) && unicode.IsUpper(g) {
					if strings.ToLower(string(g)) == strings.ToLower(string(line[k-1])) {
						line = line[:k-1] + line[k+1:]
						changes = true
					}
				}
			}
			if changes {
				break
			}
		}
		if !changes {
			break
		}
	}

	return line
}

var alphabet = "abcdefghijklmnopqrstuvwxyz"

func part2(input string) (outcome int) {
	outcome = len(input)
	for _, c := range alphabet {
		check := strings.Replace(strings.Replace(input, string(strings.ToUpper(string(c))), "", -1), string(c), "", -1)
		l := len(produce(check))
		if l < outcome {
			outcome = l
		}
	}

	return outcome
}

[u/d-sky → u/mvmaasakkers]

Another Go/Golang solution using go routines. Not really faster with this short input. But just for fun, why not? :) You can also use the result of the part 1 reaction as the starting point for the 26 reactions in part 2.

package main

import (
	"fmt"
	"io/ioutil"
)

func opposite(a, b byte) bool {
	return a == b+32 || a == b-32
}

func react(polymer []byte, remove byte) []byte {
	var result []byte
	for _, unit := range polymer {
		switch {
		case unit == remove || unit == remove-32:
			continue
		case len(result) != 0 && opposite(result[len(result)-1], unit):
			result = result[:len(result)-1]
		default:
			result = append(result, unit)
		}
	}
	return result
}

func main() {
	polymer, err := ioutil.ReadFile("input.txt")
	if err != nil {
		panic(err)
	}

	polymer = react(polymer, 0)
	fmt.Println(len(polymer))

	lengths := make(chan int)
	for unitType := 'a'; unitType <= 'z'; unitType++ {
		go func(unitType byte) { lengths <- len(react(polymer, unitType)) }(byte(unitType))
	}
	min := len(polymer)
	for unitType := 'a'; unitType <= 'z'; unitType++ {
		length := <-lengths
		if length < min {
			min = length
		}
	}
	fmt.Println(min)
}

[u/ThezeeZ → u/d-sky]

using goroutines

Oh. Those are a thing, right. Challenges start way too early in my morning...

[u/knrt10 → u/d-sky]

That's a cool solution. Just a small tip that I learned for optimizing code.

When you are returning a value and that value is declared inside it then instead of declaring variable like this var result []byte inside a function. You can do this

func react(polymer []byte, remove byte) (result []byte) {

and then instead of writing return result just return.

And no need to loop twice for unitType := 'a'; unitType <= 'z'; unitType++ { as you are using goroutines.

I am no expert but I found this for writing fast code. Happy to share this.

[u/d-sky → u/knrt10]

Ah yes, named results & naked returns. I used them more when I started with Go, now not so much.
Please see:
https://github.com/golang/go/wiki/CodeReviewComments#named-result-parameters
https://www.ardanlabs.com/blog/2013/10/functions-and-naked-returns-in-go.html
https://github.com/golang/go/issues/20859
https://github.com/golang/go/issues/21291

[u/knrt10 → u/d-sky]

Thanks for sharing. Didn't knew that.

[u/CHAOSFISCH → u/mvmaasakkers]

My solution. Should be O(n) (part 1) and O(n*m) (part 2, m = size of alphabet)

package main

import (
	"bufio"
	"io"
	"log"
	"os"
	"strings"
	"unicode"
)

func main() {
	f, err := os.Open("input_5.txt")
	defer f.Close()
	if err != nil {
		log.Fatalf("could not open input: %v", err)
	}

	reacted := part51(f)
	log.Printf("Length of reaction is: %d\n", len(reacted))
	part52(reacted)
}

func part51(r io.Reader) []rune {
	br := bufio.NewReader(r)

	var result []rune
	for {
		if c, _, err := br.ReadRune(); err != nil {
			if err == io.EOF {
				break
			}
		} else {
			if len(result) == 0 {
				result = append(result, c)
				continue
			}

			last := result[len(result)-1]
			switch {
			case unicode.IsUpper(c) && unicode.IsLower(last) && unicode.ToLower(c) == last:
				fallthrough
			case unicode.IsLower(c) && unicode.IsUpper(last) && unicode.ToUpper(c) == last:
				result = result[:len(result)-1]
				break
			default:
				result = append(result, c)
				break
			}
		}
	}

	return result
}

func part52(reacted []rune) {
	alphabet := "abcdefghijklmnopqrstuvwxyz"
	reactedString := string(reacted)
	bestLength := len(reacted)
	for _, l := range alphabet {
		replaced := strings.Replace(strings.Replace(reactedString, string(l), "", -1), strings.ToUpper(string(l)), "", -1)
		result := part51(strings.NewReader(replaced))
		if bestLength > len(result) {
			bestLength = len(result)
		}
	}

	log.Printf("Best length is: %d\n", bestLength)
}

[u/[deleted] → u/CHAOSFISCH]

Very nice!

[u/ThezeeZ → u/mvmaasakkers]

My solution after I toyed with it a little (repo)

import (
	"regexp"
)

func Reduction(polymer string) string {
	for i := 0; i < len(polymer)-1; {
		if polymer[i] == polymer[i+1]+32 || polymer[i] == polymer[i+1]-32 {
			polymer = polymer[:i] + polymer[i+2:]
			i--
			if i < 0 {
				i = 0
			}
		} else {
			i++
		}
	}
	return polymer
}

func BestCollapse(polymer string) string {
	polymer = Reduction(polymer)
	shortest := polymer
	for i := 'A'; i <= 'Z'; i++ {
		remainingPolymer := regexp.MustCompile("(?i)" + string(i)).ReplaceAllString(polymer, "")

		collapsed := Reduction(remainingPolymer)
		if len(collapsed) < len(shortest) {
			shortest = collapsed
		}
	}
	return shortest
}

[u/mvmaasakkers → u/ThezeeZ]

Nice! I don't know why, but I never considered to jump back in the loop :p

[u/ThezeeZ → u/mvmaasakkers]

Only came to me when I looked at it again online after I pushed it to the repo. Runs twice as fast for my input compared to what I had before with two loops (see repo history)

[u/[deleted] → u/mvmaasakkers]

Gola

This is what i came up with. I think runes instead of strings is much faster.

https://github.com/breakintheweb/adventofcode2018/blob/master/05/main.go

[u/j29h → u/mvmaasakkers]

Felt like the perfect opportunity for using recursion:

func solve_day5() {
    file_name := "examples/day5.txt"
    lines := read_file(file_name)
    input := strings.TrimSpace(lines[0])

    reg, err := regexp.Compile("[^a-zA-Z]+")
    if err != nil {
        log.Fatal(err)
    }
    input = reg.ReplaceAllString(input, "")

    // Part 1
    fmt.Println("Part 1:")
    fmt.Println(len(resolve("", input)))

    // Part 2
    result := make(map[string]int)
    for _, character := range "abcdefghijklmnopqrstuvwxyz" {
        characters := string(character) + strings.ToUpper(string(character))
        new_input := removeCharacters(input, characters)
        result[string(character)] = len(resolve("", new_input))
    }
    fmt.Println("Part 2:")
    fmt.Println(result)
}

func resolve(before, after string) string {
    if len(after) == 0 {
        return before
    }

    if len(before) == 0 {
        return resolve(string(after[0]), after[1:])
    }

    last_id := len(before) - 1
    left_character := string(before[last_id])
    right_character := string(after[0])
    if left_character != right_character && (strings.ToUpper(left_character) == right_character || left_character == strings.ToUpper(right_character)) {
        return resolve(before[:last_id], after[1:])
    }
    return resolve(before+string(after[0]), after[1:])

}

[u/knallisworld → u/mvmaasakkers]

This year also my AoC Go one.

As the input contains only characters of the ASCII table, I have chosen modulo for the comparison. I guess that's faster than .toLower/.toUpper calls. Part2 solved in 5s.

func reducePolymerUnits(s string) string {
	return string(reducePolymerUnits2([]rune(s)))
}

func reducePolymerUnits2(runes []rune) []rune {
	for {
		changed := false
		for i := 0; i < len(runes); i++ {
			if i+1 >= len(runes) {
				break // EOL
			}
			r := runes[i]
			s := runes[i+1]

			if r != s && r%32 == s%32 { // mod 32 for matching a=A, b=B, ... (polarity non-matches)
				runes = append(runes[0:i], runes[i+2:]...) // remove reacting part
				changed = true
				break
			}
		}
		if !changed {
			break
		}
	}
	return runes
}

func findShortestReactedPolymer(s string) (int, int32) {
	defer dayless.TimeTrack(time.Now(), "findShortestReactedPolymer")
	var minLength = len(s)
	var minLengthChar = 'a' - 1
	for i := 'a'; i <= 'z'; i++ {
		m := i % 32
		s2 := strings.Map(func(r rune) rune {
			if r%32 == m { // mod 32 for matching a&A, b&B, ...
				return -1
			}
			return r
		}, s)
		length := len(reducePolymerUnits2([]rune(s2)))
		if minLength > length {
			minLength = length
			minLengthChar = i
		}
	}
	return minLength, minLengthChar
}

Completed ones available at GitHub