I didn't solve this problem in time, but I think I might still have a way to solve it.
Basically, you can make a list where each entry represents a number in the arithmetic grid. For each entry, have a list where each entry contains dictionaries mapping sums to sequences of a given length. Make a dictionary mapping the numbers you're looking for to their solutions (map each entry to None for now). Then, for each sequence length, you start at each number A and visit only its adjacent signs C -- then the numbers B adjacent to those. Take all the sequences you had attached to A from the previous length, add C and B to them, and attach them to the cell you visited. I'm basically describing a breadth-first search using all the numbered squares as starting points. Obviously, you could end up with a lot of sequences dangling off of a cell! The trick is that some cells will have multiple sequence that arrives at them that have the same length and sum. In that case, just store the lexicographically smaller one. I haven't tried this out yet, but theoretically this will prevent your program from overflowing memory! --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
