I thought about it for 15 mins, but couldn’t think of any mathematical tricks. I thought of lots of minor tricks, like comparing the number to the result and not adding any more multiplications if it’s over, things that would cut 10%-20% here and there, but nothing which fundamentally changes big O running time.

For reference, here’s my solution for part 2 in smalltalk. I just generated every possible permutation and tested it. Part 1 is similar, mainly I just used bit magic to avoid generating permutations.

(even if you haven’t used it, smalltalk is fairly readable, everything is left to right, except in parens)

day7p2: in
	| input | 
	
	input := in lines collect: [ :l | (l splitOn: '\:|\s' asRegex) reject: #isEmpty thenCollect: #asInteger ].
	
	^ (input select: [ :line |
		(#(1 2 3) permutationsWithRepetitionsOfSize: line size - 2) 
			anySatisfy: [ :num | (self d7addmulcat: line ops: num) = (line at: 1)]
	]) sum: #first.

d7addmulcat: nums ops: ops
	| final |
	
	final := nums at: 2.
	ops withIndexDo: [ :op :i |
		op = 1 ifTrue: [ final := final * (nums at: i + 2) ].
		op = 2 ifTrue: [ final := final + (nums at: i + 2) ].
		op = 3 ifTrue: [ final := (final asString, (nums at: i+2) asString) asInteger ]
	].

	^ final
  • morrowindOP
    1·
    15 hours ago

    Interesting. I’m doing naive string cat; it would probably be way faster with just math.

    Now that I think about it more carefully, you can effectively prune whole trees of options with checking, especially for cat.

    I wonder, did you get to benchmark both approaches?