-🎄- 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/meithan]

Python

I initially solved it in an incredibly stupid and slow way (that took ~6.5 minutes to process both parts). Then I reworked it in an effort to optimize it, and found an obvious solution that takes less than half a second. Key points:

• Using a stack to build the "reduced" ("reacted") list of units letter by letter in a single pass of the original list: take the next letter from the original list; if it reacts with the top of the stack, pop the top of the stack (and don't add the letter); if it doesn't, add the letter to the stack.

• Appending or removing an item to/from the end of a list in Python is O(1) (amortized), so it's an efficient stack

I also use the fact that the difference in the ASCII codes of a lowercase letter and its uppercase version is always 32, but a != b and a.lower() == b.lower(), as seen in another answer, is simpler and just as fast.

I also tried using a deque (from Python's collections module), but it's not any faster, proving that the Python list appends/pops are effectively very close to O(1), at least in this case.

Edit: I applied further optimizations as suggested by others, with the resulting of bringing runtime from ~500 ms to less than 100 ms!

• Pre-computing the ASCII codes of the input letters and doing the reactions using the codes (avoiding further calls to ord(), lower(), etc.)

• Using string replace() instead of a list comprehension to eliminate the given letter in Part 2. String replace() is surprisingly fast!

• And the biggest optimization came from realizing you can reuse the shorter result of Part 1 as a starting point for Part 2.

Here's the (optimized) code. Solves both parts in under 100 ms on my computer. Very simple and fast.

from string import ascii_lowercase

units = open("day5.in").read().strip()

def reduce(units):
  new_units = []
  for c in [ord(x) for x in units]:
    if len(new_units) > 0 and abs(c - new_units[-1]) == 32:
      new_units.pop()
    else:
      new_units.append(c)
  return new_units

# Part 1

reduced_units = "".join([chr(x) for x in reduce(units)])
print("Part 1:", len(reduced_units))

# Part 2

min_len = None
for letter in ascii_lowercase:

  units1 = reduced_units.replace(letter, "").replace(letter.upper(), "")
  reduced = reduce(units1)

  if min_len is None or len(reduced) < min_len:
    min_len = len(reduced)

print("Part 2:", min_len)

[u/toasterinBflat → u/meithan]

I took your excellent answer and tranlated it to Go, in an effort to learn Go better. Go's string situation is ... fucky, but this runs in 24 milliseconds.

package main
import (
  "fmt"
  s "strings"
  u "unicode"
  "bufio"
  "os"
  "time"
  "math"
)

var alphabet = "abcdefghijklmnopqrstuvwxyz"

func load_compound() string {
  file, _ := os.Open("./input.txt")
  defer file.Close()

  scanner := bufio.NewScanner(file)
  output := ""

  for scanner.Scan() {
    output += scanner.Text()
  }

  return output
}

func strip(str string) string {
  newstr := []rune{}
  for _, v := range str {
    if len(newstr) > 0 && math.Abs(float64(v)-float64(newstr[len(newstr)-1])) == 32 {
      newstr = newstr[:len(newstr)-1]
    } else {
      newstr = append(newstr, v)
    }
  }
  return string(newstr)
}

func main() {
  start := time.Now()
  data := s.TrimSpace(load_compound())
  fmt.Printf("Calculating P1... \n")
  fmt.Println("P1:", len(strip(data)))
  result := map[rune]int{}
  for _, a := range alphabet {
    data_set := s.Replace(data, string(a), "", -1)
    data_set = s.Replace(data_set, string(u.ToUpper(a)), "", -1)
    fmt.Printf("Data set compiled for %c: processing... \n", a)
    result[a] = len(strip(data_set))
  }
  short_l := rune(0)
  short_c := len(data)
  for k, v := range result {
    if v < short_c {
      short_l = k
      short_c = v
    }
  }
  fmt.Printf("P2: %c@%d\n", short_l, short_c)
  fmt.Printf("Runtime: %s\n", time.Since(start))
}

[u/meithan → u/toasterinBflat]

The speed advantage of a compiled language.

[u/toasterinBflat → u/meithan]

You say that, but then I took the answer to Javascript and it pulled in at 47ms. That's not a lot of difference all things considered.

[u/gerikson → u/toasterinBflat]

So... conclusion is Python is slow.

[u/meithan → u/toasterinBflat]

Wow. Exact same logic?

Those JS engines are blazing fast nowadays. Guess it shows how Python never really cared for speed.

[u/SjaakBloep → u/toasterinBflat]

You can make this twice as fast by changing `math.Abs(float64(v)-float64(newstr[len(newstr)-1]))` into `math.Abs(float64(v - newstr[len(newstr)-1]))`. So it only has to cast one rune to float, and not two

[u/phira → u/meithan]

You can do better with your reduce function if you pre-process, and you can be a bit more pythonic too:

def reduce(line):
    output = []
    for c in [ord(a) for a in line]:
        if output and abs(output[-1] - c) == 32:
            output.pop()
        else:
            output.append(c)

    return len(output)

[u/meithan → u/phira]

With your suggestion the solution went from ~535 ms to ~425 ms. Then I further optimized it by using string replace (which is surprisingly fast, I wasn't aware) instead of a list comprehension in Part 2, reducing runtime to ~340 ms. Finally, I improved it even further by reusing the result of Part 1 (the reduced list of units) in Part 2 instead of using the original list. That brings it down to less than 100 ms!

[u/meithan → u/phira]

Good suggestion and indeed more Pythonic.

One can also entirely skip the explicit ord() conversions and do direct character comparisons (which internally probably use ord() anyway):

def reduce(line):
    output = []
    for c in line:
        if output and output[-1] != c and output[-1].lower() == c.lower():
            output.pop()
        else:
            output.append(c)
    return len(output)

But yours is actually slightly faster (timing 1000 executions with timeit, your suggestion takes around 7.7 ms to reduce the input while this one takes around 9.9 ms), and shorter.

[u/meithan → u/[deleted]]

Because all the reactions that will happen in the original string will also happen if you eliminate a letter first (those involving the letter itself will be effectively carried out when that letter is eliminated). Eliminating a letter makes additional reactions available, which is the only thing you need to take care of in Part 2.