:)

In this this Kata you need to make your program without any capital letters

Generally you're correct but there are specific limitations in this kata which prevent you from doing that

Done

ok, I got something good enough

Good enough for me :)

because of CPU cache misses

Yup this makes sense, although diagonals probably won't benifit much from this... (Tho I wouldn't be suprised if they did)

well, th ething I wasn't getting is that I was using the slow solution when I thought I was running mine... XD

oh hahaha NVM what i said then...

OK that's true... I still think it's "smart" tho ;)

I just implemented the new test (500X500 connect 80) and I think it works perfectly!

All of our solutions pass with time to spare, while the slow solution doesn't pass.
It's possible that a sloppy implementation of a good algorithm won't pass (in the first attempt atleast) but I think that's inevitable. A bit of optimizing isn't a bad thing.

Edit- The time is still all over the place ~3000ms different each attempt but I think it's still fine (maybe if I make the first few moves in the center it'll be more consistant)

Wow! Seems like I missed a lot...

But some O(1) solutions might have a larger constant factor than others

That's the problem... In theory if I could use big enough boards (I would need enough time) then the difference would be extreme and easy to distinguish. However with the time constraint of 12000ms I'm having trouble figuring out a good test to distinguish the two.

win condition nearly equal to the boarf size IS BAD as well

This is interesting... Maybe if I make a big enough board maybe even 500X500 connect 50~ and make it extremly unfair 500/1 or something then I could get almost all (other than the first few) to be O(n) with the slow solution. And this way we dont have "wasted moves" each time we make a new board, cuz we'll just make one board. And maybe if the first few aren't really random rather placed more in the center that'll help.. I can't work on this tommorow but hopefully either today or sunday.

That points towards a fourth algorithm

That's smart, didn't think of that. I'm okay with that solution passing aswell so we don't need to worry aboout it for now. (unless you guys think otherwise?) And actually as you said that's O(n) in case of a win so probably won't be good anyway.

Thanks a bunch for all the help so far :D

that's not the number of tests that you need to increase, but the size of them and the win_condition

it's big enough already

I'm not sure I understand... Are you suggesting to leave the tests like they were or make them bigger?
If I leave them, then a nonoptimised solution could pass

Edit- I also ran your solution a bunch of times and they all passed...?

Fixed

Correct, my bad.. I'll fix it.

Yup, Numpy is only better for specific tasks, not all of them.
I also tried out numpy at the start to see if it was any faster, but saw that plain python was actually better.

Glad you liked it :)

Sorry about that, The test casess were pretty bad...