Life In 19x19 http://lifein19x19.com/ |
|
L19 Programming Problem Championship: Round 3 (Graphs) http://lifein19x19.com/viewtopic.php?f=8&t=14222 |
Page 3 of 4 |
Author: | quantumf [ Sun May 14, 2017 2:30 pm ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
Any suggestions for how to construct a tough/pathological problem for BuildDependencies? I've tried very long (100,000 files that depend in sequence on one another) and very wide (100,000 files that depend on a single file), but my code is near instantaneous with these, and yet I'm getting TLE on test 2. Are we expected to deal with circular dependencies? |
Author: | gamesorry [ Sun May 14, 2017 3:09 pm ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
quantumf wrote: Are we expected to deal with circular dependencies? I think there are no circular dependencies in test data (I didn't handle such cases). |
Author: | jeromie [ Sun May 14, 2017 3:19 pm ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
quantumf wrote: Any suggestions for how to construct a tough/pathological problem for BuildDependencies? I've tried very long (100,000 files that depend in sequence on one another) and very wide (100,000 files that depend on a single file), but my code is near instantaneous with these, and yet I'm getting TLE on test 2. Are we expected to deal with circular dependencies? There is extra, unused data in the file, I.e. Files that do not need to be rebuilt. It is those extra unconnected files that gave my algorithm fits. (I think.) |
Author: | Solomon [ Sun May 14, 2017 5:38 pm ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
Well I managed to get E and F as I'd hoped (I think I spent more time tinkering with input and forgetting about cin.ignore() than the actual algorithm for E...), but with only 30 minutes before I have to visit family and not coming back until past the deadline, it looks like I won't be able to squeeze D in (although I'll most likely be pondering the problem at the dinner table...). |
Author: | gamesorry [ Sun May 14, 2017 6:58 pm ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
Overlooking the following statement for Problem F costs me 26 trials to figure out: (I even used 'try - except ValueError' statements to catch the weird input exception) "The input for each room consists of one or more lines" but finally I got all problems despite the huge penalties Edit: Ah, it seems some of you have already pointed out the pitfall ... |
Author: | peti29 [ Mon May 15, 2017 12:21 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
I'm really interested in a solution for Build Dependencies... |
Author: | Solomon [ Mon May 15, 2017 8:28 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
Leaderboard
I'll get around to writing up Problem F (XYZZY) (the key algorithm is either Bellman-Ford or Shortest Path Faster Algorithm (SPFA), but you can't just use either out-of-the-box; having a hard time explaining this succinctly and clearly (--> my lack of true understanding!)), or bernds, gamesorry, or jeromie can post their explanation of it if they have time. Code posted for A, B and D, didn't bother for C since it looks like most people got it but happy to provide if requested (or someone else who got the problem). Problem A (Coast Length) Problem B (Arctic Network) Problem C (Dominoes 2) Problem E (Build Dependencies) |
Author: | peti29 [ Mon May 15, 2017 9:11 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
This round has been a little bit bitter for me even though I got C for first try which was refreshing. Maybe C# is at disadvantage after all? The story of my solution for A: Solomon: I'll need to look at your code some more before I get what you're doing there. |
Author: | bernds [ Mon May 15, 2017 9:16 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
Problem A (Coast Length) Solomon wrote: Problem B (Arctic Network) Quote: Problem C (Dominoes 2) Quote: Problem D (Chess) Problem E (Build Dependencies) Quote: Problem F (XYZZY) Getting the hide and quote tags right is harder than some of the problems... how do people feel, do we actually need to hide discussion (I can see hiding the code)? |
Author: | ugoertz [ Mon May 15, 2017 9:22 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
Thanks, Solomon, for setting up another contest. I liked the problems since for all of them there were enough sucessful submissions, also in Python, to prove that hitting the time limit means that the choice of algorithm is not ideal. (Although maybe true, this was not as obvious for the second round.) Besides this, this time my usual approach of "inventing" the required algorithm myself rather than looking at books or so turned out to be particularly unsuitable ... (given that I never studied any graph theory algorithms before ). Nevertheless, I enjoyed thinking about the problems, and find the comments about your approaches very instructive. I had some ideas about A, B, and D, but did not have time to implement them. (I think that in D, processing all ='s first and identifying all those nodes reduces the problem to one where only <'s are given. This just means detecting the (non-)existence of a cycle in a directed graph, right?) I might have a correct (but too slow) solution for E, but I could be missing something ... When I first attempted to do problem F I definitively underestimated this problem, and I see now that my submitted programs cannot work. At the end I had the idea to first find a spanning tree, starting from the start node, and as a second step to find all cycles in the graph (at this point I did some research and found Johnson's algorithm). Then one could check, in each case, whether running through the cycle costs energy (then we can ignore it), or whether it increases the energy (in this case, if we can reach a node of the cycle from the start node without running out of energy, and can reach the final node from the cycle, then we win). I did not implement this though. Any comments? Best, Ulrich |
Author: | Solomon [ Mon May 15, 2017 9:29 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
peti29 wrote: This round has been a little bit bitter for me even though I got C for first try which was refreshing. Maybe C# is at disadvantage after all? The story of my solution for A: Solomon: I'll need to look at your code some more before I get what you're doing there. I went ahead and added my implementation for A in case it might help... |
Author: | Solomon [ Mon May 15, 2017 9:30 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
bernds wrote: Getting the hide and quote tags right is harder than some of the problems... how do people feel, do we actually need to hide discussion (I can see hiding the code)? Good point, I agree that we should just keep code hidden but discussion of solutions should be okay not to hide...
|
Author: | Kirby [ Mon May 15, 2017 9:37 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
I only read two of the problem statements. Problem A (coast problem): My first attempt was to first fill in any lakes, and then iterate through each cell to see if it bordered water. To fill the lakes, I had a routine to check for a path to the outside. Then if I found none, I did flood fill on the lake to turn it into land. This was too slow. I ended up changing the initial map to add a border of water around the edge. Then, I started at position (0,0), then did a search for all land edges. This was fast enough to pass the test cases. Problem C (domino one): I tried both with array and hash table to add each of the "rules" (domino X tips domino Y) to a list. Then, I'd take the domino that was tipped, query the array/hash table, and see which dominoes it tipped over. For each of those dominoes, I queried the array/hash table to see what ones they tipped over. This seemed to me to be a simple and straightforward way to solve the problem. But I'd either run out of memory or run out of time. I got frustrated/angry, because it seemed like it should be an efficient solution to the problem. So I quit, and didn't work on the problems, anymore. I guess I was kind of a baby in my reaction to Problem B, but it was too depressing to continue. |
Author: | Bill Spight [ Mon May 15, 2017 9:41 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
bernds wrote: Getting the hide and quote tags right is harder than some of the problems... how do people feel, do we actually need to hide discussion (I can see hiding the code)? Nowadays I hide most of my long posts (outside of This 'n' That), as a courtesy to those who want to skip over them. You can more easily scroll past them if they are hidden. |
Author: | bernds [ Mon May 15, 2017 9:46 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
Kirby wrote: Problem C (domino one): Have you worked with graphs before? There are typically two ways of representing them, either with a two-dimensional array that holds information for each node pair i and j whether there is an edge between them, or by associating a list of edges with each node.I tried both with array and hash table to add each of the "rules" (domino X tips domino Y) to a list. Then, I'd take the domino that was tipped, query the array/hash table, and see which dominoes it tipped over. For each of those dominoes, I queried the array/hash table to see what ones they tipped over. This seemed to me to be a simple and straightforward way to solve the problem. But I'd either run out of memory or run out of time. I got frustrated/angry, because it seemed like it should be an efficient solution to the problem. So I quit, and didn't work on the problems, anymore. Here's my dominoes2 attempt, which shows one way of organizing the edges as a list (or rather a dynamically expanded array but it's the same thing really). Also, an iterative traversal algorithm. I've used variants of these pieces in several of the problems, but this here is the most basic form. |
Author: | jeromie [ Mon May 15, 2017 9:58 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
I did the same thing as Kirby for Problem A (coastline). I found it kind of funny that I used a flood fill algorithm to solve that one based on the problem statement. For Problem C (Dominoes), I made each domino a node in a linked list with a push method. As long as a domino was not already knocked over, it would set itself and all of its children to a fallen state. At the end I just iterated through the list of dominoes and counted how many were fallen. (I could have improved performance by keeping track of how many were fallen as they were pushed over, but this was fast enough.) For Problem F (xyzzy), I did a modified breadth first search based on the algorithm for finding the shortest path through a weighted graph. I didn't do true cycle testing because I was afraid it would be too slow, so I just added a line that checked if I had visited the same node 100 times. If I did (and energy was increasing each time), I just set the current player energy to 100000 and blocked that node from being visited again. I suppose it's a bit of a cheat, but I figured the heuristic would be good enough for this problem. The only other one I had time to attempt was the build dependency problem. I implemented a topological sorting algorithm that I'm pretty sure was correct, but it was too slow on some of the inputs. The topological sort removes nodes that no longer have a parent, and I think my algorithm bogged down because there were "parent" nodes that were irrelevant to the problem. (For instance if C depends on A and B and A is the file we change, the fact that B is a parent of C is irrelevant.) I handled this case in the algorithm, but it depended on a lot of (expensive) checks for list membership. I'm pretty sure that if I pruned the unnecessary nodes from the graph before running the topological sort that it would have been fast enough, but I didn't have a chance to go back and make the change. |
Author: | Solomon [ Mon May 15, 2017 10:21 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
ugoertz wrote: When I first attempted to do problem F I definitively underestimated this problem, and I see now that my submitted programs cannot work. At the end I had the idea to first find a spanning tree, starting from the start node, and as a second step to find all cycles in the graph (at this point I did some research and found Johnson's algorithm). Then one could check, in each case, whether running through the cycle costs energy (then we can ignore it), or whether it increases the energy (in this case, if we can reach a node of the cycle from the start node without running out of energy, and can reach the final node from the cycle, then we win). I did not implement this though. Any comments? Haven't heard of Johnson's algorithm, but I'll take a look and see if I can swap it out with my Bellman-Ford implementation and get it to work!
|
Author: | Kirby [ Mon May 15, 2017 10:27 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
bernds wrote: Kirby wrote: Problem C (domino one): Have you worked with graphs before? There are typically two ways of representing them, either with a two-dimensional array that holds information for each node pair i and j whether there is an edge between them, or by associating a list of edges with each node.I tried both with array and hash table to add each of the "rules" (domino X tips domino Y) to a list. Then, I'd take the domino that was tipped, query the array/hash table, and see which dominoes it tipped over. For each of those dominoes, I queried the array/hash table to see what ones they tipped over. This seemed to me to be a simple and straightforward way to solve the problem. But I'd either run out of memory or run out of time. I got frustrated/angry, because it seemed like it should be an efficient solution to the problem. So I quit, and didn't work on the problems, anymore. Here's my dominoes2 attempt, which shows one way of organizing the edges as a list (or rather a dynamically expanded array but it's the same thing really). Also, an iterative traversal algorithm. I've used variants of these pieces in several of the problems, but this here is the most basic form. I've worked with graphs before, yes. For this approach, I was storing a collection of edges. Here was my first attempt: I didn't think it's that unreasonable - each key in the dictionary represents a node, which has a hashset of nodes (i.e. edges). Once the first domino is tipped, I jump around the dictionary to find the next item. I can see that you are actually setting a bitmap. I suppose that's more efficient than the dictionary structure I used. The way I see it, though, adding a given edge is done in O(1) time. Traversing the list of dominoes is on the order of the number of dominoes in the chain. But I see that my approach doesn't account for cycles in the graph. I just thought about that. Maybe that's why I ran into problems? :-p |
Author: | bernds [ Mon May 15, 2017 10:49 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
Kirby wrote: I didn't think it's that unreasonable - each key in the dictionary represents a node, which has a hashset of nodes (i.e. edges). I might not know enough Java, but this sounds unnecessarily complicated. A mapping from an integer to something else is just an array, or a vector, especially when you know the number of elements beforehand. Surely Java has things like that? So that's the natural way to store data for the nodes. And if you know your algorithm is going to want to look at all edges for a given node, it makes sense to store them in something simple like a list or a growable vector/array. The more complex data structures might work but it seems wasteful and for more complex problems you'd need to consider how much time it takes to traverse them.Quote: But I see that my approach doesn't account for cycles in the graph. I just thought about that. Maybe that's why I ran into problems? :-p Could be
|
Author: | Kirby [ Mon May 15, 2017 11:14 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
bernds wrote: Kirby wrote: I didn't think it's that unreasonable - each key in the dictionary represents a node, which has a hashset of nodes (i.e. edges). I might not know enough Java, but this sounds unnecessarily complicated. A mapping from an integer to something else is just an array, or a vector, especially when you know the number of elements beforehand. Surely Java has things like that? So that's the natural way to store data for the nodes. And if you know your algorithm is going to want to look at all edges for a given node, it makes sense to store them in something simple like a list or a growable vector/array. The more complex data structures might work but it seems wasteful and for more complex problems you'd need to consider how much time it takes to traverse them.Yep, I used an array next, and ran out of memory. The reason I opted for a dictionary as the first choice is that, for a large number of dominoes and a small number of rules, the data structure doesn't have to be very big. Using an array, you have to allocate such that there's an index for every different value of n, so the array could be pretty big, even when there aren't that many rules (unless you create your own hashing mechanism). Anyway, I did try an array keeping the rest the same, and ran out of memory. (It's written in C#, by the way.) Quote: Quote: But I see that my approach doesn't account for cycles in the graph. I just thought about that. Maybe that's why I ran into problems? :-p Could be Yeah, if cycles are acceptable, my solution doesn't handle that. I jump around the hash table (or array), following each of the Y nodes in a rule saying that X knocks down Y. I never take anything out of the mapping, a cycle will produce an infinite loop. If that's all the problem was, this was just a case of me not understanding the implications of the problem. I was frustrated that something that seemed efficient kept failing - maybe I was blinded by that, if this is all the problem was. |
Page 3 of 4 | All times are UTC - 8 hours [ DST ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |