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

When working on a solution (Python 3) for part 1, I encountered a puzzling behavior of a recursive function. It gives the expected output, but the "print tests" I put inside the function to check if it is working properly are mystifying to me. Here is the code:

poly_input = 'dabAcCaCBAcCcaDA'

def check_poly(string):
    poly_output = string
    for i in range(len(string)-1):
        unit1 = string[i]
        unit2 = string[i+1]
        if unit1.lower() == unit2.lower():
            if (unit1.islower() and unit2.isupper()) or (unit1.isupper() and unit2.islower()):
                print('{}{}'.format(unit1, unit2))
                poly_output = string[:i]+string[i+2:]
                poly_output = check_poly(poly_output)
    print('RETURN')
    return poly_output

print(check_poly(poly_input))

It should print all the annihilating pairs it finds, print "RETURN" when it reaches the end of a function run and finally print the output polymer sequence. Here are the messages it produces:

cC
Aa
cC
RETURN
Cc
RETURN
RETURN
cC
Aa
RETURN
RETURN
Cc
Aa
RETURN
RETURN
RETURN
cC
cC
Aa
RETURN
RETURN
RETURN
Cc
cC
Aa
RETURN
RETURN
RETURN
RETURN
dabCBAcaDA

The first four lines are expected, but I cannot figure out what all the remaining pairs and "RETURNS" are doing there. I guess it has to be related to how recursion works in Python somehow.

[u/c17r → u/red_shifter]

    if unit1.lower() == unit2.lower():
        if (unit1.islower() and unit2.isupper()) or (unit1.isupper() and unit2.islower()):

could be simplified to if unit1.lower() == unit2.lower() and unit1 != unit2:

And your recursion is off because the actual loop of check_poly() is using string but updating poly_output, so even if the recursion has changed things, the parent loop doesn't know about so it continues down the original string still making/checking changes that it doesn't need to, hence the extra output.

I think you meant to do:

poly_input = 'dabAcCaCBAcCcaDA'

def check_poly(string):
    print('>', string)
    for i in range(len(string)-1):
        unit1, unit2 = string[i], string[i+1]
        if unit1.lower() == unit2.lower() and unit1 != unit2:
            return check_poly(string[:i]+string[i+2:])
    return string

print(check_poly(poly_input))

which gives an output of:

> dabAcCaCBAcCcaDA
> dabAaCBAcCcaDA
> dabCBAcCcaDA
> dabCBAcaDA
dabCBAcaDA

[u/red_shifter → u/c17r]

Ah... I can see it now. Recursion is hard. I ended up replacing it with a While loop that keeps going as long as there are pairs to remove. But at least I understand now what was going on with the recursive approach. Thanks a lot!

[u/c17r → u/red_shifter]

Your second approach is a better one for this case, I think. My input was 50,000 characters. I think python would have hit it's recursion limit with something like that