EPTThe Big Programming Thread - Page 472
| Forum Index > General Forum |
Thread Rules 1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution. 2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20) 3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible. 4. Use [code] tags to format code blocks. | ||
|
obesechicken13
United States10467 Posts
| ||
|
Manit0u
Poland17743 Posts
On April 28 2014 08:34 cilinder007 wrote: I have a programming challenge I can't quite seem to get the right awnser to, it goes like this You were hired by a director of a small company with N employees to set up the network between the employees who have to send a weekly report to each of the other employees as a different part or their report is important for each employee, depending on the importance of their work they have to send a report Ki number of times per week You have measured the time it takes for a message to be delivered between each 2 employees Due to budget cuts the network will only have N-1 connections between they employees and because of the simplicity of the technology you are using when one message is sent the entire network has to wait for it to be delivered (only 1 message at a time) What you get is N -the number of employees, you get Ki which is the muber of times a report from worker i is to be sent per week, Tij which indicates the time a message traveles from employee i to employee j 1<=N<=13 0<=Ki<=10^3 0<=Tij<=10^3 Tij = Tji, Tii = 0 At first I assumed the most optimal network would be a star (tree) and all it would take is to determine which node to be in the center and since we were limited to an N at most 13 I decided to just brute force it and try them all, but that attempt failed as apparently this was not the most optimal network configuration (or so the test cases showed me) Then I thought maybe this would be solved by finding a minimum spanning tree or each full graph made from the employees, but since there are multiple minimum spanning trees and not all of them are equaly good for this problem that failed on paper already I am currently a bit out of ideas, so a hint as to what direction I should be looking towards would be great Set up a google drive feature or an svn for the emplyees. Sorry, my mind is blank after 9 hours of trying to fix errors in the project and resolving commit issues between 4 people who decided to work on the same exact thing all day long. | ||
|
RoyGBiv_13
United States1275 Posts
On April 29 2014 02:33 spinesheath wrote: If my resulting graph has no edge from employee a to employee b, but edges from a to c and from c to b, is the time from a to b defined as Tab or as Tac + Tcb? Our graph is always a tree. It has to be connected or else one employee couldn't message everyone else. It has N nodes and N-1 edges. Therefore it is a tree, and we are most likely looking for a Minimum Spanning Tree by some weight function we don't know yet. Assuming the graph is guaranteed to be a tree (I'd be careful about this assumption), then you can get away with just using a depth first/breadth first search instead of generating a minimal spanning tree. Let me know if you need an psuedocode example of these algorithms. Note that a graph that has a cycle in it cannot be a tree. | ||
|
spinesheath
Germany8679 Posts
On April 29 2014 03:59 RoyGBiv_13 wrote: Assuming the graph is guaranteed to be a tree (I'd be careful about this assumption), then you can get away with just using a depth first/breadth first search instead of generating a minimal spanning tree. Let me know if you need an psuedocode example of these algorithms. Note that a graph that has a cycle in it cannot be a tree. A connected graph with N nodes and N-1 edges is a tree. By definition. Or by colloray if you use another definition. And what do you intend to achieve with a search here? | ||
|
RoyGBiv_13
United States1275 Posts
On April 29 2014 04:57 spinesheath wrote: A connected graph with N nodes and N-1 edges is a tree. By definition. Or by colloray if you use another definition. And what do you intend to achieve with a search here? Ah, I misread the problem statement... I was thinking you had to generate the time between employees within the network, not generate the network.... "You have measured the time it takes for a message to be delivered between each 2 employees" + Show Spoiler [really bad solution] + The algorithm you're looking for is a greedy algorithm, where the metric you're optimizing is based on the distance between nodes and the frequency which they send out messages. First, find a way to measure the metric: Start at node A and search (using a depth first search) until you get to B, add up lengths between nodes. Repeat this process for every node. Throw this data into a function that takes into account Ki and whatnot in order to determine a score based on distance between nodes and frequency they send out reports. Now, search the problem space: There are 13 nodes at most, and they can each have up to 12 children. A brute force would cycle between each node and number of children it has as the head, then iterate over each of its children, adding up to N children and removing them, scoring every possibility. You can optimize this by adding in a projected score heuristic. If a projected score is already worse than the current best score, then you don't need to follow that branch any further, as it will just get worse as you add in more nodes. Additional optimizations could include paying attention to the symmetry of the problem space in order to rule out half or more of the potential solutions. | ||
|
Ben...
Canada3485 Posts
On April 29 2014 07:30 RoyGBiv_13 wrote: Ah, I misread the problem statement... I was thinking you had to generate the time between employees within the network, not generate the network.... "You have measured the time it takes for a message to be delivered between each 2 employees" + Show Spoiler [really bad solution] + The algorithm you're looking for is a greedy algorithm, where the metric you're optimizing is based on the distance between nodes and the frequency which they send out messages. First, find a way to measure the metric: Start at node A and search (using a depth first search) until you get to B, add up lengths between nodes. Repeat this process for every node. Throw this data into a function that takes into account Ki and whatnot in order to determine a score based on distance between nodes and frequency they send out reports. Now, search the problem space: There are 13 nodes at most, and they can each have up to 12 children. A brute force would cycle between each node and number of children it has as the head, then iterate over each of its children, adding up to N children and removing them, scoring every possibility. You can optimize this by adding in a projected score heuristic. If a projected score is already worse than the current best score, then you don't need to follow that branch any further, as it will just get worse as you add in more nodes. Additional optimizations could include paying attention to the symmetry of the problem space in order to rule out half or more of the potential solutions. Sounds an awful lot like Djikstra's Algorithm for shortest path on a weighted graph (which is indeed a greedy algorithm, though Djikstra uses a weird pseudo-breadth first search because it looks at the weights of each connected edge to a given vertex, and moves to the vertex with which the connecting edge is the lowest weight if that vertex has not been visited yet). It finds the shortest path from a given node to each other node so long as there exists some path to that node. In this case, one could treat the time it takes to send a message between two connected employees/nodes/whatevertheyares as your edge weight, thus finding the shortest time. Djikstra is really easy to implement if you use a pair of arrays to keep track of which nodes have been visited and the tentative total path weight between the starting node and the node being examined (alternatively, you can have a boolean field in your vertex that will state whether the vertex has been visited or not). By the time you hit the last unvisited node, you will have the minimal path from your starting node to every other connected node on the graph. You'll note that in the wiki article, they set the tentative distance between the start node and a given node to infinity. This is because the algorithm will only overwrite that tentative distance if it the new path distance is less than the one stored. This is how it always will result in minimal distances. The algorithm can be modified to give either the minimal path itself, or the minimal weight. If you have your implementation set up so that the weight is stored in each edge, you can easily get both. | ||
|
Shield
Bulgaria4824 Posts
| ||
|
spinesheath
Germany8679 Posts
A -ab- B -bc- C -cd- D then: ab is used 3 * Ka + Kb + Kc + Kd times bc is used 2 * Ka + 2 * Kb + 2 * Kc + 2 * Kd times cd is used Ka + Kb + Kc + 3 * Kd times that's because I have to use ab to go from A to B, from A to C and from A to D. Now let's find the real algorithm. If I pick any edge ab and seperate my set of nodes into 2 sets, one on a's side, called Sa and one on b's side called Sb, then the weight of ab is: ((Number of nodes in Sa) * (Sum Ki over all nodes in Sb) + (Number of nodes in Sb) * (Sum Ki over all nodes in Sa)) * Tab If minimize over all possible splits Sa and Sb for each node and take the resulting weights for a greedy MST algorithm, will the result be optimal? I think it will, but I don't have a proof readily at hand. The critical part is whether minimizing over all possible splits Sa and Sb actually produces the correct weight function. Could I split differently, take a slightly worse weight, and gain better results overall? I messed up again, fixed the weight function. I also have to calculate the weight function and keep track of the split for the minimum weight, then calculate the weight function again but for each split separately... | ||
|
Shield
Bulgaria4824 Posts
On April 30 2014 00:57 darkness wrote: Is there software that analyses Java classes and then produces UML diagram? I think it would save a lot of time. Answer: UMLet What do you guys do when you have too many classes (20+) that need to be displayed on a class diagram? Stuff gets really complex to look at.  | ||
|
Birdie
New Zealand4438 Posts
| ||
|
Shield
Bulgaria4824 Posts
On May 01 2014 07:38 Birdie wrote: Is UML actually useful in the real world? I'm sitting in a class for it right now and it seems like IT rubbish that is no practical use for a developer, and seems quite abstract and wasted. But I have no work experience in the real world and could be completely wrong. I have no work experience, but I can tell you a few things. Some jobs require applicants to know UML. UML is still a good way to introduce you to what class is what and what is linked to what. Would you rather dive into code to find out? UML is summary to me. Then, Javadoc gives me more concrete description of what (methods, classes) does what. Finally, code itself to get yourself really updated. Edit: One challenge I've experienced with UML is scalability. The more classes you have, the harder (at least for me) it gets. | ||
|
Blisse
Canada3710 Posts
| ||
|
obesechicken13
United States10467 Posts
I hear some people did like them for systems that got complicated though. | ||
|
WolfintheSheep
Canada14127 Posts
Well, I guess that's like all programming documentation. You don't do it for yourself, or the team that's been writing the code from Day 1. It's for everyone having to maintain it down the road. I'm currently in a position where I'd kill for some UMLs or workflow diagrams. | ||
|
MichaelEU
Netherlands816 Posts
So yeah, I'd say it's mostly for people who join in later down the road. | ||
|
aksfjh
United States4853 Posts
On May 01 2014 14:43 WolfintheSheep wrote: Main point of UMLs and similar diagrams is for someone who is just stepping into a monstrous block of coding for the first time. Well, I guess that's like all programming documentation. You don't do it for yourself, or the team that's been writing the code from Day 1. It's for everyone having to maintain it down the road. I'm currently in a position where I'd kill for some UMLs or workflow diagrams. Workflow diagrams are much more useful. UML is stuck in this weird place where it's too detailed to be useful at a glance, but not detailed enough to use for somebody working on the system. | ||
|
Frudgey
Canada3367 Posts
I'm currently in a Summer job that requires me to use C++. I'm going to be working on my laptop for the majority of the Summer but I don't have C++ on it. My question is do any of you know where I can get C++ and a compiler for it? And roughly how much will it cost? I tried looking this up on the internet, but it was hard to get concrete answers. If anyone could provide me with links that would be much appreciated. Also if this isn't the right place to ask then I apologize. EDIT: I should probably mention that I'm using Windows 8 right now, if that helps at all. | ||
|
Scheme
United Kingdom210 Posts
On May 01 2014 23:31 Frudgey wrote: Hi all, I'm currently in a Summer job that requires me to use C++. I'm going to be working on my laptop for the majority of the Summer but I don't have C++ on it. My question is do any of you know where I can get C++ and a compiler for it? And roughly how much will it cost? I tried looking this up on the internet, but it was hard to get concrete answers. If anyone could provide me with links that would be much appreciated. Also if this isn't the right place to ask then I apologize. EDIT: I should probably mention that I'm using Windows 8 right now, if that helps at all. You can download VIsual Studio professional 2013 for free if you are a student: https://www.dreamspark.com/ Otherwise Visual Studio express C++ for free as well. link Hope that helps. EDIT: 2013 not 2014 | ||
|
NihiLStarcraft
Denmark1413 Posts
On May 01 2014 23:31 Frudgey wrote: Hi all, I'm currently in a Summer job that requires me to use C++. I'm going to be working on my laptop for the majority of the Summer but I don't have C++ on it. My question is do any of you know where I can get C++ and a compiler for it? And roughly how much will it cost? I tried looking this up on the internet, but it was hard to get concrete answers. If anyone could provide me with links that would be much appreciated. Also if this isn't the right place to ask then I apologize. EDIT: I should probably mention that I'm using Windows 8 right now, if that helps at all. You don't need to 'get' C++, it's not an interpreted language. All you need is a compiler to turn your source files into machine code which can then be executed by your computer! There's a bunch of free C++-compilers out there, since you are on Windows and seem to be very new to the language I would advice for the Microsoft Visual C++ Express IDE, since it comes with a compiler and it's easy to get started with. | ||
|
nunez
Norway4003 Posts
| ||
| ||
