@feersum Well you can basically run subset sum twice to assign directions to the individual rods. First you find all subsets that give you equal total lengths. You make that subset horizontal, and all remaining rods vertical. And then for both of the sets, you find all subsets with exactly half the length, and assign them to up/right. And then you just need to check if the resulting arrangement is a valid polyomino.
The advantage would be that subset sum has a search space of 2^n instead of 3^n
but in the end it might be much easier to truncate the search space with the backtracking you already have so that the better complexity doesn't outweigh it.
well split the set into two groups whose rod lengths sum to the same number. because you need to go as far down as you went up (or as far left as you went right)
well the two passes of subset sum give you an assignment of UDLR to each rod, and it already guarantees that the loop is closed. then you only need to check for counter-clockwise traversal and that there's no self-intersection
I'm not even that good... but the few things I can do tend to work well enough to do them unconsciously while thinking or being bored... until I need to change my pen...
Nothing we do is in VS, so TFS would seem a bit of an odd move. Though I haven't looked into it much, I assume it's main feature is easy integration with VS.
Interesting. I might look into it. Sad to say, though, it might be fighting a losing battle either way. The practices used here aren't so much "practices" as much as "just do your work and we'll throw it together later".
Github would be a nice step up from CVS, for sure :(
Tell the computer to do the math
This challenge is partly an algorithms challenge, involves some math and is partly simply a fastest code challenge.
For some positive integer n, consider a uniformly random string of 1s and 0s of length n and call it A. Now also consider a second uniformly cho...
Maybe @MartinBüttner The blurry version gets turned into the clearer version :D I didn't believe that box blur converged to Gaussian but apparently it does
First thing I noticed: If the score is simply the highest n with no time limit, you can basically win by having a bunch of CPU time at your disposal, no?
@Geobits this is only sort of true. First. it is slightly non-trivial to write correct code at all. Second, the most naive method will be billions of times slower than a clever method
@Geobits so if you have 10 times more cpu power it won't help much if you have a worse method
@Geobits but if you have billion times more it might :)
@Lembik it's not like you'll have one naive and one clever submission. you'll get a bunch of clever submissions, and they might not be that many orders of magnitude apart.
still, it turned out that feersum's machine was about 1.5 times faster than mine, whereas Sp3000's was about the same, so comparing the scores they obtained themselves wouldn't really have been fair
Tell the computer to do the math
This challenge is partly an algorithms challenge, involves some math and is partly simply a fastest code challenge.
For some positive integer n, consider a uniformly random string of 1s and 0s of length n and call it A. Now also consider a second uniformly cho...
