El lunes, 22 de julio de 2013 13:25:47 UTC-5, ajlopez escribió: > Ah! > > > The algorithm only attacks the problem of "finding the greatest sets", 0 > (maybe the matrix has all 0), 1 or more sets of the same size. > > > If this algorithm is correct, then we could attack the full problem. As I > mentioned in my previous email, I don't sure if we have TWO OR MORE greatest > sets, if we could choose only the first, or we should visit every branch. > > > > Angel "Java" Lopez > @ajlopez > > > > > > On Sun, Jul 21, 2013 at 11:27 PM, Andres Duque <[email protected]> wrote: > > El domingo, 21 de julio de 2013 20:46:28 UTC-5, Andres Duque escribió: > > > > > El domingo, 21 de julio de 2013 15:29:39 UTC-5, ajlopez escribió: > > > > > > > Hi people! > > > > > > > > > > > > > > > > > > > > > Andres, I just coding my algorithm using TDD, in C#: > > > > > > > > > > > > > > > > > > > > > https://github.com/ajlopez/TddRocks/tree/master/MatrixSet > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > It's still a bit tricky, no comments... but commitments by test. So, the > > > history of commits shows the evolution of the algorithm. > > > > > > > > > > > > > > > > > > > > > It returns the set of greatest sets in a given matrix, with boolean cells > > > (true or false, instead 0 or 1). > > > > > > > > > > > > > > > > > > > > > > > > > > > > Apparently, it works, but no proof yet. Take into account, that we need > > > to research which one of the greatest sets we should choose, or if we > > > need to visit all branches. > > > > > > > > > > > > > > > > > > > > > It's far from your concern about performance, but I thinks is something > > > to research. A la Kent Beck: make it works, make it right, make it fast > > > ;-) > > > > > > > > > > > > > > > > > > > > > > > > > > > > If you can compile/run C#, give a list of matrix here, your results for > > > the greatest test, and I can run them against the program. > > > > > > > > > > > > > > > > > > > > > Angel "Java" Lopez > > > > > > > @ajlopez > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > On Sat, Jul 20, 2013 at 7:30 PM, Andres Duque <[email protected]> > > > wrote: > > > > > > > > > > > > > > El sábado, 20 de julio de 2013 14:03:36 UTC-5, ajlopez escribió: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Hi people! > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Andres, thanks for your detailed response. Now I see the light ;-) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > I don't understand why you want to combine round trips from nowhere to > > > > nowhere, with combinations ;-) But I started to understand, with your > > > > paragraph: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > The only constrain to group them is thh possible combinations are > > > > present in the original pairs. After it the idea is to maximize the > > > > group size and minimize the total number the groups. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > For the example the grouping: 1, 2 --> A, C is possible because all the > > > > possible combinations (1-A, 1-C, 2-A, 2-C) are present in the original > > > > pairs (note recommendations 1, 3, 4, and 5) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Ok. I depicted an algorithm, not coded yet. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > - We must find the greatest combination of "1" that comply with your > > > > criteria > > > > > > > > > > > > > > > - We can enumerate all the combinations of "1", but it could be better > > > > to have a way to enumerate them, in order > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > So, the position is: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1110 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1011 > > > > > > > > > > > > > > > 0001 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > avoiding distracting spaces. Let starts from left to right, top to > > > > bottom. We started with: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1*** > > > > > > > > > > > > > > > .*** > > > > > > > > > > > > > > > .*** > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Then, we search in the * positions, from left to right, top to bottom, > > > > the first 1 that could be added to the solution. It is at first row, > > > > second column: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 11** > > > > > > > > > > > > > > > ..** > > > > > > > > > > > > > > > ..** > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Then, we search in * for the first 1 that can be added to the set. It > > > > is: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 111* > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > ...* > > > > > > > > > > > > > > > ...* > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > The search stops, because the first row, fourth column is a 0, > > > > eliminates all the column, no more columns. The found set is size 3. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Backtrack. And repeat. Eventually, we will find: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1.1. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1.1. > > > > > > > > > > > > > > > .... > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > as a bigger set. And so on. We find the bigger set that starts with an > > > > 1 at first column, first row. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Repeat with other 1, and so on. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > In this way, we will obtain the biggest set, without repetition. No > > > > sort is needed. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > We choose the biggest one, remove them, and start again. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Two problems: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > - What happens if TWO or more sets have the same biggest size? The only > > > > way I see, is, courage, visit every branch > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > - Maybe, there is a better solution (in number of groups) taking a size > > > > 3 set, than taking a 4 set. But if I understood you, you ordered the > > > > solutions first by size, then by number of groups, am I right? > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > The interesting part of the above algorithm, it is not need sorting, > > > > and equates columns vs rows, it is symmetric. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Angel "Java" Lopez > > > > > > > > > > > > > > > @ajlopez > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > On Wed, Jul 17, 2013 at 3:54 PM, Andres Duque <[email protected]> > > > > wrote: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Thanks Angel for you reply. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > El miércoles, 17 de julio de 2013 08:13:20 UTC-5, ajlopez escribió: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Hi! > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Interesting... but I still don't grasp the terminology. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > What is a "round trip recommendation"? > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Round trip recommendation is an itinerary with outbound flight(s) and > > > > inbound flight(s). You start in point A to point B a later return to > > > > original point (A) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > A - B - A. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Why outbound flights are numbers and inbound flights are letters? > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > It's only a way to make easier to understand the problem without > > > > confusing with the details. In the real life outbound could be AF085 > > > > (one or more flights in connection). > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Where are the "airports"? > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > For this problem it doesn't matter since they are always the same, > > > > i.e., the source information for this problem is the response for an > > > > availability request for two or more points. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > What is the criteria for grouping? > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > The only constrain to group them is thh possible combinations are > > > > present in the original pairs. After it the idea is to maximize the > > > > group size and minimize the total number the groups. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > For the example the grouping: 1, 2 --> A, C is possible because all the > > > > possible combinations (1-A, 1-C, 2-A, 2-C) are present in the original > > > > pairs (note recommendations 1, 3, 4, and 5) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Angel "Java" Lopez > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > @ajlopez > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > On Wed, Jul 17, 2013 at 9:10 AM, Andres Duque <[email protected]> > > > > > wrote: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Hi all, > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > I have this real life problem, maybe someone could find a > > > > > better/easier solution than mine :-). I need to optimize and > > > > > generalize the solution. This process will be executed +1M times each > > > > > day, therefore, any millisecond saved will be useful. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > PROBLEM > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > You have round trip recommendations (at this time I'm simplifying it > > > > > only to two points but the problem must be generalized to several > > > > > points): > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > N Outbound Inbound > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1 1 A > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 2 1 B > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 3 1 C > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 4 2 A > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 5 2 C > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 6 2 D > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 7 3 D > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > The goal is to build groups of combinable Inbound/Outbound flights > > > > > maximizing the group sizes a minimizing the number of groups (both > > > > > are related). > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > For the example we could build 3 optimal groups: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1st Group (4 possible combinations) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Outbound flights: 1, 2 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Inbound flights: A, C > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 2nd Group (2 possible combinations) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Outbound flights: 2, 3 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Inbound flights: D > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 3rd Group (1 possible combinations) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Outbound flights: 1 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Inbound flights: B > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > As you can see, there are several possible solutions but it maximize > > > > > the groups size: 4, 2, 1 (possible combinations) and minimize the > > > > > number of groups: 3. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Note the original problem must consider several points (not limited > > > > > to round trip). > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > I tried with: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > * A greedy algorithm but it doesn't find biggest groups in some > > > > > scenarios. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > * A LCS algorithm adaptation but I could find a suitable one > > > > > (http://en.wikipedia.org/wiki/Longest_common_subsequence_problem) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Now I have a heuristic solution but maybe its not the best/easier > > > > > approach and it's hard to extend it to several points. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > INITIAL SOLUTION > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Build a matrix with the recommendations: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > A B C D > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1 X X X > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 2 X X X > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 3 X > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Later sort this matrix by columns and later by rows in desc order, > > > > > think X like bit '1' and no connection like '0' where left-most, > > > > > top-most is higher. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > After sort by columns: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > A C B D > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1 1 1 1 0 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 2 1 1 0 1 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 3 0 0 0 1 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > After sort by rows (no changes): > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > A C B D > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1 1 1 1 0 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 2 1 1 0 1 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 3 0 0 0 1 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Now we find biggest rectangles of 1's using an optimal algorithm > > > > > (maybe precalculating 1's at right of each cell. With it, we can > > > > > identify the 3 groups: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1st group: 1, 2 --> A, C > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 2nd group: 2, 3 --> D > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 3rd group: 1 --> B > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Note above is better solution than: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1st group: 1 --> A, C, B > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 2nd group: 2 --> A, C > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 3rd group: 2, 3 --> D > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > because with the 1st one we have a group of 4 recommendations (bigger > > > > > than 3 recommendations for the 2nd solution). > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Any idea is welcome. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > -- > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > You received this message because you are subscribed to the Google > > > > > Groups "Google Code Jam" group. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > To unsubscribe from this group and stop receiving emails from it, > > > > > send an email to [email protected]. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > To post to this group, send email to [email protected]. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > To view this discussion on the web visit > > > > > https://groups.google.com/d/msgid/google-code/94ccbb62-7829-4cd2-a803-c5a042e84db6%40googlegroups.com. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > For more options, visit https://groups.google.com/groups/opt_out. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > -- > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > You received this message because you are subscribed to the Google > > > > Groups "Google Code Jam" group. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > To unsubscribe from this group and stop receiving emails from it, send > > > > an email to [email protected]. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > To post to this group, send email to [email protected]. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > To view this discussion on the web visit > > > > https://groups.google.com/d/msgid/google-code/a759d324-df90-49a0-a8cd-a9c9f84ab355%40googlegroups.com. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > For more options, visit https://groups.google.com/groups/opt_out. > > > > > > > > > > > > > > > > > > > > > > > > > > > > Thanks Angel but I didn't fully understand you algorithm. > > > > > > > > > > > > > > > > > > > > > > > > > > > > I understood: > > > > > > > > > > > > > > > > > > > > > > > > > > > > 1. We start with the 1st '1' left-most top-most. > > > > > > > > > > > > > > 2. Found (1) we search a '1' in the '*'s same (left-most top-most) (only > > > adjacent ???) > > > > > > > > > > > > > > 3. You talked about backtrack, do you mean I must backtrack over each '1' > > > added to the group? > > > > > > > > > > > > > > 4. I didn't understand how you found group size 4 after find the group > > > size. > > > > > > > > > > > > > > 5. After find a group we turn '1' to '0' for the found group. > > > > > > > > > > > > > > 6. Return to step 1 until we don't have '1's > > > > > > > > > > > > > > > > > > > > > > > > > > > > Regards, > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > -- > > > > > > > > > > > > > > You received this message because you are subscribed to the Google Groups > > > "Google Code Jam" group. > > > > > > > > > > > > > > To unsubscribe from this group and stop receiving emails from it, send an > > > email to [email protected]. > > > > > > > > > > > > > > To post to this group, send email to [email protected]. > > > > > > > > > > > > > > To view this discussion on the web visit > > > https://groups.google.com/d/msgid/google-code/9be51b3c-25f5-48a2-aec0-fc9603a72f31%40googlegroups.com. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > For more options, visit https://groups.google.com/groups/opt_out. > > > > > > > > > > > > Hi Angel, > > > > > > > > > > > > I just downloaded your application and migrated it to VS2010. It is > > compiling and running. I'll explore it and run some samples, I will give > > you my findings. > > > > > > > > > > > > Thanks very much for you support with this problem. > > > > > > > > > > > > Regards > > > > Two additional test cases: > > > > Matrix matrix = new Matrix("1110", "1101", "1101", "1101"); > > Matrix matrix = new Matrix("1111", "1111", "1000", "0111"); > > > > They found the greatest group (size=9) but they didn't find the other groups > (2). As far as I understood from GetGreatestSets it loops the whole matrix > inserting all the groups but it didn't do. Note test cases > GetHorizontalRectangularSetSizeSix and GetSquareSetSizeFour as well (same > issue). > > > > > > Regards, > > > > -- > > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > > > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > > To post to this group, send email to [email protected]. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/5e914b3a-071c-42b9-92c5-5a358d44b5a4%40googlegroups.com. > > > > > For more options, visit https://groups.google.com/groups/opt_out.
Hi Angel, ok, understood the current scope. In some tests I have done it looks work fine. About your question, yes, we must include all groups needed to represent all the recommendation from original input. Regards, -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/45ab3290-a790-4f27-9e1c-6981a4512707%40googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
