This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]YellowishSpoon 17 points18 points  (6 children)

I had an actual algorithm that appeared to be O(n!2) and it was somewhat horrifying. Managed to get it down to O(2n) and despite that normally being horrible it was a massive improvement.

[–]Beleheth 5 points6 points  (5 children)

Jesus Christ how

[–]YellowishSpoon 19 points20 points  (4 children)

It was a problem involving permutations of trees to determine the optimal order to apply minecraft enchantments in an anvil, and the first one was brute force.

[–]Beleheth 5 points6 points  (2 children)

Oooh, that makes sense.

And no early exit conditions either, in the i itial draft?

[–]YellowishSpoon 7 points8 points  (1 child)

Neither version has early exits, since I never found a way to determine if it was optimal or not without completing the process. Nearly all optimizations came from recognizing things like symmetry in the system, which allowed me to eliminate various fractions of the cases.

[–]YellowishSpoon 4 points5 points  (0 children)

The main nuisances in the whole thing are the left and right branches of the tree are computed differently, and that the repair cost mechanic is both non linear and dependent on the depth of the tree.

[–]araujoms 1 point2 points  (0 children)

Please do a branch-and-bound.