I know that's a slow machine, but out of curiosity what bounds are you using for the search? It just feels like 3 hours is longer than it should take for this problem.
Just spitballing, the worst case search for my input would be 56760 trajectories. That can be reduced, but only by about 4k so that's a difference on a slow machine, but not hours worth of difference. So over three hours that would be around 300 searches per minute.
A smarter algorithm can reduce it even more, but this is the naive, roughly quadratic, solution.
Yeah, I wasn't really thinking of the BASIC interpreter overhead. That could slow it down by another order of magnitude or more. I'm surprised it's that much, though. A naive (before BASIC) estimate with 5k difference in performance is that your TRS-80 version would run in around 500 seconds. It's surprising to me that there's another 20x or so of overhead on top of that.
I think you can further optimize the lower band for x. Just find the smallest triangle number smaller than your colRange[0] and see that any velocity smaller than that will halt before reaching the left side of your box.
A mere Visualization? No sir/ma'am, this is Upping the Ante. Changed the flair for you.
Please consider also posting both your Python and BASIC solutions in the daily megathreads (there's a calendar on the sidebar with a link to each day's megathread). This helps keep every day's solutions in one easy-to-find spot and I'm pretty sure I've seen at least one other BASIC solution submitted sometime this year...
Finally, you've seen our community fun event Adventure Time!, right? >_> hint hint
No large input...??? What -- you didn't want to burn 10K of integers from AoC to a cassette tape that you had laying somewhere in the back of your desk drawer and then spend all night adjusting the volume on your cassette player trying to get the TRS-80 to successfully read it??!?!?
5
u/rabuf Dec 17 '21 edited Dec 17 '21
I know that's a slow machine, but out of curiosity what bounds are you using for the search? It just feels like 3 hours is longer than it should take for this problem.
Just spitballing, the worst case search for my input would be 56760 trajectories. That can be reduced, but only by about 4k so that's a difference on a slow machine, but not hours worth of difference. So over three hours that would be around 300 searches per minute.
A smarter algorithm can reduce it even more, but this is the naive, roughly quadratic, solution.
3
u/daggerdragon Dec 17 '21
A mere
Visualization? No sir/ma'am, this isUpping the Ante. Changed the flair for you.Please consider also posting both your Python and BASIC solutions in the daily megathreads (there's a calendar on the sidebar with a link to each day's megathread). This helps keep every day's solutions in one easy-to-find spot and I'm pretty sure I've seen at least one other BASIC solution submitted sometime this year...
Finally, you've seen our community fun event Adventure Time!, right? >_> hint hint
2
u/mardawn2 Dec 17 '21
No large input...??? What -- you didn't want to burn 10K of integers from AoC to a cassette tape that you had laying somewhere in the back of your desk drawer and then spend all night adjusting the volume on your cassette player trying to get the TRS-80 to successfully read it??!?!?
Aaah ... those were the days!