My day 20 solution only works for Part 1. I am fairly confident the generally approach is okay, but something is getting me mixed up with the math for wrapping around.
The relevant code (which is wrong, somehow):
void AD20Actor::MixStep(TArray<FD20Mix>& Mixed, int Step) { ensure(Step>=0 && Step<Mixed.Num()); const int64 End = Mixed.Num(); const int64 From = Mixed[Step].Location; // handle positive wrap around int64 Too = From + Mixed[Step].Value; if (Too>=End) { // WORKS for PART 1? Too = Too % (End-1); // if (Too>=From) Too++; // Too = (Too % End); } // handle negative wrap around // WORKS for PART 1 else if (Too<=0) { auto Steps = -Too / (End-1); Too += (Steps+1) * (End-1); } if (Too==From) return; // shuffle everything AFTER the slot the moving item is moving from DOWN // shuffle everything AFTER the moving items destination UP for(int i=0;i!=Mixed.Num();++i) { int D = 0; if (Mixed[i].Location > From) D -= 1; if (Mixed[i].Location+D >= Too) D += 1; Mixed[i].Location = (Mixed[i].Location + D) % End; } Mixed[Step].Location = Too; }
I think it’s probably the wrapping that’s wrong, but I don’t really understand why.
For the last step, “4 moves between -3 and 0” – 4 starts in the 5th position, add 4 is 9, 2 past the end.
But 2 past the end puts it between 2 and -3. So what gives? Well when we “remove” the item, the array becomes 1 smaller, so I thought the wrap is at 6 not 7 and that puts this in the right location. My tests pass.
But Part 2 has us wrapping around not once, but thousands of times around in an array thousands of elements long. When I do that, my results don’t match the part 2 example results, and I’ve tried for far to long now at figuring it out.
So that’s it for me. My 2nd day I’ve failed to solve Part 2 in time for bed. Can you see what’s wrong? Please let me know if you can explain what I’ve missed… post a comments or reply on to me on Mastodon.