iximeow
commented
1 week ago ah yeah, that's my bad --
and it makes a faulty assumption to just push what left received back onto the stack
my faulty assumption was more that if left needs to eject a shape, that it is good to trade that shape to middle. but it's not aware that middle might match what needs to leave left, so it never recovers from the unprofitable trade. a slightly smaller fix to what exists: when handling neededSwaps.middle.length == 1, check if the shape to move away from left is this.insideGuardianMiddle, and if it is, we know the trade has to go to right instead. the whole problem space is small enough that i think One More Kludgey If might be fine...
anyway, that would make the first instruction
Place Square on left and Circle on right
at which point the remaining needed swaps would be the middle shape (circle) and right's triangle, with left needing no swaps. so the arm for if (neededSwaps.middle.length) would still do the right thing and suggest a swap of middle and right for step 2 of
Place Circle on middle and Triangle on right
Last night we were using your tool, and we found at least one confirmed combination of inside and outside inputs that the tool provides an incorrect set of steps.
In the picture, you can see that we have Square Circle Triangle inside and Prism Cylinder Cone outside.
The provided steps were:
This results in step 1 changing left to a Cone and middle to a Cube. Then step 2 results in changing left to Pyramid and right to a Sphere.
Algorithm Update:
I looked through the algorithm, and the problem seems to come up in the condition where each aisle has a swap, left and right do a swap, and it makes a faulty assumption to just push what left received back onto the stack. You instead likely need to do some logic to see if either object is currently as the correct solution, but the algorithm does not have memory of the current state of each aisle's object. I think the better solution would be to make this into a state machine, but that solution would probably be better for a more complicated problem.
Instead, I've added some logic to account for what each aisle is in search of (wishlist). We then have produced a set of actions that are possible (swaps) and a list we can consume from until we know it's in the correct solution state. This helps to prioritize swapping things an aisle doesn't want towards aisles that both have an available swap and want to receive that swap. Since we only send shapes to the places they are on the wishlist, we can immediately slice those off the wishlist, then we check if the sender wanted what they got in return. If they want it, we slice from their wishlist or push it on their swap list.
I think this should shore up any loose ends, since we're keeping track of what we don't want and what we need to be considered the correct solution. This likely means some of the extraneous conditions in the algorithm will not be reached, but I haven't gone through to spruce anything up.
Problem not the most beautiful/efficient solution, but I think we're working with small enough lists that the indexOf checks won't slow things down too much. If you know a faster option, feel free to optimize.
Steps with the updated code:
Step 1 should make left a Pyramid and right a Cylinder. Notice that the first step now tries to put left's first swap into a location that has it on the wishlist (previously, it swapped the Square to middle even though that gave middle two Squares). Next, step 2 makes left a Cone and middle a Prism. This gives us the correct solution.