Discussion on: AoC Day 5: Alchemical Reduction

[Mustafa Haddara]

I actually managed to complete Part A with an O(n²) algorithm, before realizing that would be too slow for part B...then I realized I could use a stack to implement an O(n) algorithm.

function reduction(chain)
    chain = reduction_one_pass(chain)
    return length(chain)
end

function reduction_one_pass(chain)
    result = [chain[1]]
    i = 2
    while i <= length(chain)
        a = result[end]
        b = chain[i]
        i+=1

        while a != b && uppercase(a) == uppercase(b)
            deleteat!(result, length(result))  # remove a

            # get new a,b
            if length(result) > 0
                a = result[end]
            else
                a = ""
            end
            b = chain[i]
            i+=1
        end

        # b doesn't match last char on stack
        push!(result, b)
    end
    return join(result, "")
end

function main()
    filename = ARGS[1]  # julia arrays are 1-indexed!
    input = split(read(filename, String), "\n")[1]
    test_input = "dabAcCaCBAcCcaDA"

    println(reduction(input))
end

main()

Part B is iterating through all letters in the alphabet, doing the string replace and then, doing the same reduction as Part A, while tracking the minimum reduced length. I feel like there's a better way to do that, but...never figured it out.

function find_biggest_reduction(chain)
    smallest = -1

    # there's gotta be a pattern here but I can't quite figure it out
    # so we're brute forcing it
    char_A = Int("a"[1])
    for i in char_A:char_A+25
        letter = Char(i)
        sub = replace(replace(chain, letter=>""), uppercase(letter)=>"")
        reduced = reduction_one_pass(sub)
        println("$letter -> length: $(length(reduced))")
        if length(reduced) < smallest || smallest == -1
            smallest = length(reduced)
        end
    end
    return smallest
end

I logged my output and saw that, for my input, v reduced far better than anything else.

a -> length: 10432
b -> length: 10448
c -> length: 10510
d -> length: 10484
e -> length: 10450
f -> length: 10528
g -> length: 10424
h -> length: 10490
i -> length: 10480
j -> length: 10480
k -> length: 10444
l -> length: 10386
m -> length: 10426
n -> length: 10454
o -> length: 10476
p -> length: 10412
q -> length: 10476
r -> length: 10420
s -> length: 10426
t -> length: 10452
u -> length: 10456
v -> length: 4684
w -> length: 10468
x -> length: 10366
y -> length: 10476
z -> length: 10486

My gut tells me there's some pattern in the input that would tell you which char to remove, and that way you only have to do the reduction once (as opposed to 26 times).

[Ryan Palo]

I looked at that, but when it wasn't definitively the letter that showed up the most, I didn't look very much further.

I bet you're right though, there's some "clustering factor" or something that would tip you off for which letter is most productive.