Okay, now I know why I didn't think of it your way. Your selection criteria are not the same as Creamsteak's selection criteria:
You want to pick one value from each row, and one value from each column. You cannot pick any specific number twice. Your goal is to pick the highest possible total set value.
Consider the following case: array([[9, 0, 0, 0], [0, 8, 0, 7], [0, 0, 7, 6], [0, 7, 6, 5]]) Here's what your algorithm picks: Step 1) (0,0), (1,1), (2,2), (3,1) Step 2) nothing, nothing, nothing, (1,3) Step 3) (2,3), (3,2) and (3,3) i.e. your algorithm picks precisely all of the nonzero values.
However, I don't think this meets Creamsteak's selection criteria - by his terms, you need to pick one element for the topmost row, and one element for the leftmost column, but you cannot pick the 9 in the top-left corner both times. Hence you would necessarily need to pick one of the zeros.
Oh, and here's a pathological case for your own criteria and algorithm, Timo: array([[3, 0, 0, 0, 0], [0, 9, 9, 9, 0], [0, 9, 0, 9, 0], [0, 9, 9, 9, 0], [4, 0, 0, 0, 3]])Your algorithm would select the the 3 from the first row and the 4 from the last row in step 1, and then it would have to pick the 3 from the last column in step 2. Then it would pick 7 9's from the middle, for a total of 73. However, the optimal solution is to pick the two 3's, and then all 8 9's from the middle, for a total of 78.
On the plus side, that means we have another problem to work on! Timo's criteria are less demanding, but we haven't got a good solution for them yet.
EDIT: Adjusted version of Timo's algorithm: 1) For every row select highest value. 2) For every column select highest value, counting how many of these were already selected in step 1. 3) Now select the k highest unselected values in the matrix, where k is the number of doubly-selected values you counted in step 2. It's still O(n^2), but it handles the above case correctly, as far as I can tell.
Pathological case for the adjusted version: array([[1, 0, 0, 2], [0, 9, 9, 9], [0, 9, 9, 9], [2, 9, 9, 9]]) Timo's algorithm (with or without the adjustment) would pick the two 2's, and 6 9's, for a total of 58. However, the optimal solution would pick the 1, and 7 9's, for a total of 64.
It was added on September 3rd apparently. One of the moderators closed a thread I had started on my problem because it was "too similar". He also told me I could discuss it in the forum that opens up once you solve said problem. So I solved it (just like doing homework, which I didn't miss at all). I'm overall disappointed with the forum (mostly just optimized solutions of that problem), but the one thing I got from it that was useful was the "Hungarian Algorithm", which may be worth a look. I hadn't heard of it before, thought maybe others might be interested.
Havn't looked at the code yet (and actually I've been reading all over the internets on all kinds of things related). You are correct about the difference in criteria.
My algorithm is the same one I described earlier - mark the highest in each row and each column, then resolve double-marking by moving each mark to the highest-value connected unmarked spot. I'm not entirely sure it works at the moment, but I strongly suspect that it does. It would probably be good to try some test cases and compare to, say, your 3x3 algorithm.
The 3x3 is just different. You can oversimplify it to basically an if/else.
The result is always the highest 6 values unless the lowest 3 values are in a single row or column (in which case it's the highest 5 values and the 7th highest value).
In the 2x2 case you always mark every element, and in the 1x1 case there is no solution. The 3x3 also has a trivial solution, as you said.
However, if my algorithm is correct for the nxn case, then it must work for the 3x3 case - if it were to fail on any 3x3 example, the algorithm would clearly be incorrect. That's why I suggested testing against the 3x3. You could also test it vs your brute force 4x4, but presumably the latter is quite slow.
Ideally, though, I'd like to prove that my algorithm always finds the optimal solution. That can't be done with testing alone, of course.
Possible solution to Timo's problem: Apply what is essentially the Hungarian algorithm - just maximising instead of minimising - to mark n values, then just pick the highest n out of the remaining unmarked values in the matrix. This would be O(n^3) due to the Hungarian algorithm. However, I'm not sure that this actually finds the optimal solution for Timo's problem.
However, I'm not sure that this actually finds the optimal solution for Timo's problem.
I'm guessing that the best way to improve my problem is to put in a 4a) step where you relax over constrained patterns (like the 3,3,4 in your pathological example) IF the lowest selected value < highest unselected value AND the released value < (highest unselected val - lowest selected val) == diff. If diff is still positive you should add a step 4b) where you try to resolve over constraints like the 1,2,2 case from your second pathology. Both of these are at least (I think) O(n^3).
What makes me feel sad is that some of the stuff I read today blew my mind... and I'm supposed to be a programmer. Plus... I still hate doing binary shifts. I still get confused. People that just throw those into their code all the time... arg...
It took a couple minutes, and I accidently overwrote a file I didn't mean to (but it's backed up). I had to change my code from before, because this is a different solution, but this is trying to find every possible solution for every possible combination.
Output was this:
BigBoss = 14728425858
So in theory, if I didn't screw anything up in my changes, and your algorithm works for this, you should be able to get the same "total" (BigBoss) of all maximized selections.
Edit: I flipped the if statement and screwed up the picked reset. Recalculating.
387 420 489 is a hell of a lot of test cases. I ran part of the test, and it takes ~4 seconds to calculate 10000 cases, and so I think it would take around 2 days to do all ~400 million of your cases.
Can you come up with a reasonable subset of the 3x3 test cases?
Yeah with matrix rotation you definitely only have to test 1/4 of them. Further than that, You actually only need to test 9^2 I think. One for each correct "pick order".
I was actually going to generate a small test-set of 81 since I think I can do that, just figuring out how to write the code. But that works too, and shouldn't be hard to add.
Edit: Er wait... do you just mean every possible arrangment of 1 through 9? I'm not immediately sure if that covers every possible case... since duplication is an issue. Or I'm just getting tired.
Well I am the sleeping now. I'll figure something out tomorrow. Thanks though, has been interesting. I've never programmed in eight different languages in a day (including work in that). Very odd.
I'm not even totally sure what I just made, but there's (162?) matrices each hitting a different basic pattern (I think?). The test run gave me a total of 2069 for all of them.
For your test file, I got a result of 2069 with both your algorithm (3 smallest / 2 smallest and 4th-smallest) and with my own.
I also tried another approach - taking only the first X cases of the aforementioned 9**9. For one hundred thousand cases, I found that it took me ~7 seconds using your shortcut, while my general algorithm took ~80 seconds, and so for all 9**9 I estimate it would take around 4 hours with the shortcut, and around 43 hours doing it with my algorithm.
I'm pretty sure my implementation of your shortcut is a good one, so it's strange that it would be so much slower than yours. I think it's primarily a matter of primitive arrays in Java vs numpy arrays - there's a lot of inevitable overhead in a Python program. EDIT: Yep. Implementing the exact same algorithm in Java gets much, much faster results.
It's significantly faster than the python version - around 100 times faster, which is enough that one can reasonably compare results for all of the 3x3 test cases.
I was using it to estimate how long it would take to solve via brute force (in this case, brute force being n! complexity of picking each possible order to pick stats in). Commenting out the output lines speeds it up quite a bit obviously.
Another random fact, this was the project where I learned that the java compiler (at least at the time I was working on it) did not do as much optimization as you would think... and literally removing a bunch of open and close parenthisis made it faster. Though I'm pretty sure setting it up to use bitmasks and memoisation would save me more time now.
It's O((2n)!), not O(n!) complexity though, right? The two are actually different. Anyways, you now have a Java implementation of my algorithm, so you can test it against your brute force approach.
Comments
array([[9, 0, 0, 0],[0, 8, 0, 7],
[0, 0, 7, 6],
[0, 7, 6, 5]])
Here's what your algorithm picks:
Step 1)
(0,0), (1,1), (2,2), (3,1)
Step 2)
nothing, nothing, nothing, (1,3)
Step 3)
(2,3), (3,2) and (3,3)
i.e. your algorithm picks precisely all of the nonzero values.
However, I don't think this meets Creamsteak's selection criteria - by his terms, you need to pick one element for the topmost row, and one element for the leftmost column, but you cannot pick the 9 in the top-left corner both times. Hence you would necessarily need to pick one of the zeros.
array([[3, 0, 0, 0, 0],Your algorithm would select the the 3 from the first row and the 4 from the last row in step 1, and then it would have to pick the 3 from the last column in step 2. Then it would pick 7 9's from the middle, for a total of 73.[0, 9, 9, 9, 0],
[0, 9, 0, 9, 0],
[0, 9, 9, 9, 0],
[4, 0, 0, 0, 3]])
However, the optimal solution is to pick the two 3's, and then all 8 9's from the middle, for a total of 78.
On the plus side, that means we have another problem to work on! Timo's criteria are less demanding, but we haven't got a good solution for them yet.
EDIT: Adjusted version of Timo's algorithm:
1) For every row select highest value.
2) For every column select highest value, counting how many of these were already selected in step 1.
3) Now select the k highest unselected values in the matrix, where k is the number of doubly-selected values you counted in step 2.
It's still O(n^2), but it handles the above case correctly, as far as I can tell.
array([[1, 0, 0, 2],[0, 9, 9, 9],
[0, 9, 9, 9],
[2, 9, 9, 9]])
Timo's algorithm (with or without the adjustment) would pick the two 2's, and 6 9's, for a total of 58.
However, the optimal solution would pick the 1, and 7 9's, for a total of 64.
Damn. Timo's problem is a hard one too.
It was added on September 3rd apparently. One of the moderators closed a thread I had started on my problem because it was "too similar". He also told me I could discuss it in the forum that opens up once you solve said problem. So I solved it (just like doing homework, which I didn't miss at all). I'm overall disappointed with the forum (mostly just optimized solutions of that problem), but the one thing I got from it that was useful was the "Hungarian Algorithm", which may be worth a look. I hadn't heard of it before, thought maybe others might be interested.
The original problem was this: http://invisiblecastle.com/stats/grid/
You have to have a value that corresponds to Str, one to Dex, one to Con, one to Int, one to Wis, and one to Cha.
I'll look at the code.
I'm not entirely sure it works at the moment, but I strongly suspect that it does. It would probably be good to try some test cases and compare to, say, your 3x3 algorithm.
The result is always the highest 6 values unless the lowest 3 values are in a single row or column (in which case it's the highest 5 values and the 7th highest value).
However, if my algorithm is correct for the nxn case, then it must work for the 3x3 case - if it were to fail on any 3x3 example, the algorithm would clearly be incorrect. That's why I suggested testing against the 3x3. You could also test it vs your brute force 4x4, but presumably the latter is quite slow.
Ideally, though, I'd like to prove that my algorithm always finds the optimal solution. That can't be done with testing alone, of course.
I founds my code, but I'm going to have to butter it back up.
However, I'm not sure that this actually finds the optimal solution for Timo's problem.
I just ran this: http://pastebin.com/mv834EyH
It took a couple minutes, and I accidently overwrote a file I didn't mean to (but it's backed up). I had to change my code from before, because this is a different solution, but this is trying to find every possible solution for every possible combination.
Output was this:
BigBoss = 14728425858
So in theory, if I didn't screw anything up in my changes, and your algorithm works for this, you should be able to get the same "total" (BigBoss) of all maximized selections.
Edit: I flipped the if statement and screwed up the picked reset. Recalculating.
BigBoss = 14703496002 over 9^9 entries.
Can you come up with a reasonable subset of the 3x3 test cases?
Edit: Er wait... do you just mean every possible arrangment of 1 through 9? I'm not immediately sure if that covers every possible case... since duplication is an issue. Or I'm just getting tired.
I'm not even totally sure what I just made, but there's (162?) matrices each hitting a different basic pattern (I think?). The test run gave me a total of 2069 for all of them.
For your test file, I got a result of 2069 with both your algorithm (3 smallest / 2 smallest and 4th-smallest) and with my own.
I also tried another approach - taking only the first X cases of the aforementioned 9**9. For one hundred thousand cases, I found that it took me ~7 seconds using your shortcut, while my general algorithm took ~80 seconds, and so for all 9**9 I estimate it would take around 4 hours with the shortcut, and around 43 hours doing it with my algorithm.
I'm pretty sure my implementation of your shortcut is a good one, so it's strange that it would be so much slower than yours. I think it's primarily a matter of primitive arrays in Java vs numpy arrays - there's a lot of inevitable overhead in a Python program.
EDIT: Yep. Implementing the exact same algorithm in Java gets much, much faster results.
http://pastebin.com/vXcau8hA
as well as JUnit4 Test Case for the 3x3 tests:
http://pastebin.com/UfgcYEpP
It's significantly faster than the python version - around 100 times faster, which is enough that one can reasonably compare results for all of the 3x3 test cases.
http://pastebin.com/QhA6rKG7
I was using it to estimate how long it would take to solve via brute force (in this case, brute force being n! complexity of picking each possible order to pick stats in). Commenting out the output lines speeds it up quite a bit obviously.
Another random fact, this was the project where I learned that the java compiler (at least at the time I was working on it) did not do as much optimization as you would think... and literally removing a bunch of open and close parenthisis made it faster. Though I'm pretty sure setting it up to use bitmasks and memoisation would save me more time now.
Anyways, you now have a Java implementation of my algorithm, so you can test it against your brute force approach.