Search Results

Search found 15 results on 1 pages for 'simucal'.

Page 1/1 | 1 

• How to prepare for a programming competition? Graphs, Stacks, Trees, oh my! [closed]

  - by Simucal

  Last semester I attended ACM's (Association for Computing Machinery) bi-annual programming competition at a local University. My University sent 2 teams of 3 people and we competed amongst other schools in the mid-west. We got our butts kicked. You are given a packet with about 11 problems (1 problem per page) and you have 4 hours to solve as many as you can. They'll run your program you submit against a set of data and your output must match theirs exactly. In fact, the judging is automated for the most part. In any case.. I went there fairly confident in my programming skills and I left there feeling drained and weak. It was a terribly humbling experience. In 4 hours my team of 3 people completed only one of the problems. The top team completed 4 of them and took 1st place. The problems they asked were like no problems I have ever had to answer before. I later learned that in order to solve them some of them effectively you have to use graphs/graph algorithms, trees, stacks. Some of them were simply "greedy" algo's. My question is, how can I better prepare for this semesters programming competition so I don't leave there feeling like a complete moron? What tips do you have for me to be able to answer these problems that involve graphs, trees, various "well known" algorithms? How can I easily identify the algorithm we should implement for a given problem? I have yet to take Algorithm Design in school so I just feel a little out of my element. Here are some examples of the questions asked at the competitions: ACM Problem Sets Update: Just wanted to update this since the latest competition is over. My team placed 1st for our small region (about 6-7 universities with between 1-5 teams each school) and ~15th for the midwest! So, it is a marked improvement over last years performance for sure. We also had no graduate students on our team and after reviewing the rules we found out that many teams had several! So, that would be a pretty big advantage in my own opinion. Problems this semester ranged from about 1-2 "easy" problems (ie bit manipulation, string manipulation) to hard (graph problems involving fairly complex math and network flow problems). We were able to solve 4 problems in our 5 hours. Just wanted to thank everyone for the resources they provided here, we used them for our weekly team practices and it definitely helped! Some quick tips that I have that aren't suggested below: When you are seated at your computer before the competition starts, quickly type out various data structures that you might need that you won't have access to in your languages libraries. I typed out a Graph data-structure complete with floyd-warshall and dijkstra's algorithm before the competition began. We ended up using it in our 2nd problem that we solved and this is the main reason why we solved this problem before anyone else in the midwest. We had it ready to go from the beginning. Similarly, type out the code to read in a file since this will be required for every problem. Save this answer "template" someplace so you can quickly copy/paste it to your IDE at the beginning of each problem. There are no rules on programming anything before the competition starts so get any boilerplate code out the way. We found it useful to have one person who is on permanent whiteboard duty. This is usually the person who is best at math and at working out solutions to get a head start on future problems you will be doing. One person is on permanent programming duty. Your fastest/most skilled "programmer" (most familiar with the language). This will save debugging time also. The last person has several roles between assessing the packet of problems for the next "easiest" problem, helping the person on the whiteboard work out solutions and helping the person programming work out bugs/issues. This person needs to be flexible and be able to switch between roles easily.

  Read the article

• Ball to Ball Collision - Detection and Handling

  - by Simucal

  With the help of the Stack Overflow community I've written a pretty basic-but fun physics simulator. You click and drag the mouse to launch a ball. It will bounce around and eventually stop on the "floor". My next big feature I want to add in is ball to ball collision. The ball's movement is broken up into a x and y speed vector. I have gravity (small reduction of the y vector each step), I have friction (small reduction of both vectors each collision with a wall). The balls honestly move around in a surprisingly realistic way. I guess my question has two parts: What is the best method to detect ball to ball collision? Do I just have an O(n^2) loop that iterates over each ball and checks every other ball to see if it's radius overlaps? What equations do I use to handle the ball to ball collisions? Physics 101 How does it effect the two balls speed x/y vectors? What is the resulting direction the two balls head off in? How do I apply this to each ball? Handling the collision detection of the "walls" and the resulting vector changes were easy but I see more complications with ball-ball collisions. With walls I simply had to take the negative of the appropriate x or y vector and off it would go in the correct direction. With balls I don't think it is that way. Some quick clarifications: for simplicity I'm ok with a perfectly elastic collision for now, also all my balls have the same mass right now, but I might change that in the future. In case anyone is interested in playing with the simulator I have made so far, I've uploaded the source here (EDIT: Check the updated source below). Edit: Resources I have found useful 2d Ball physics with vectors: 2-Dimensional Collisions Without Trigonometry.pdf 2d Ball collision detection example: Adding Collision Detection Success! I have the ball collision detection and response working great! Relevant code: Collision Detection: for (int i = 0; i < ballCount; i++) { for (int j = i + 1; j < ballCount; j++) { if (balls[i].colliding(balls[j])) { balls[i].resolveCollision(balls[j]); } } } This will check for collisions between every ball but skip redundant checks (if you have to check if ball 1 collides with ball 2 then you don't need to check if ball 2 collides with ball 1. Also, it skips checking for collisions with itself). Then, in my ball class I have my colliding() and resolveCollision() methods: public boolean colliding(Ball ball) { float xd = position.getX() - ball.position.getX(); float yd = position.getY() - ball.position.getY(); float sumRadius = getRadius() + ball.getRadius(); float sqrRadius = sumRadius * sumRadius; float distSqr = (xd * xd) + (yd * yd); if (distSqr <= sqrRadius) { return true; } return false; } public void resolveCollision(Ball ball) { // get the mtd Vector2d delta = (position.subtract(ball.position)); float d = delta.getLength(); // minimum translation distance to push balls apart after intersecting Vector2d mtd = delta.multiply(((getRadius() + ball.getRadius())-d)/d); // resolve intersection -- // inverse mass quantities float im1 = 1 / getMass(); float im2 = 1 / ball.getMass(); // push-pull them apart based off their mass position = position.add(mtd.multiply(im1 / (im1 + im2))); ball.position = ball.position.subtract(mtd.multiply(im2 / (im1 + im2))); // impact speed Vector2d v = (this.velocity.subtract(ball.velocity)); float vn = v.dot(mtd.normalize()); // sphere intersecting but moving away from each other already if (vn > 0.0f) return; // collision impulse float i = (-(1.0f + Constants.restitution) * vn) / (im1 + im2); Vector2d impulse = mtd.multiply(i); // change in momentum this.velocity = this.velocity.add(impulse.multiply(im1)); ball.velocity = ball.velocity.subtract(impulse.multiply(im2)); } Source Code: Complete source for ball to ball collider. Binary: Compiled binary in case you just want to try bouncing some balls around. If anyone has some suggestions for how to improve this basic physics simulator let me know! One thing I have yet to add is angular momentum so the balls will roll more realistically. Any other suggestions? Leave a comment!

  Read the article

• Open source C# projects that have high code quality?

  - by Simucal

  Question: What are some open source C# projects I can download that implement many best-practices and have a relatively high code quality? Please accompany your answer with some of the reasons you consider the code is of high quality. Suggestions so far: SharpDevelop NHibernate Boo Rhino Mocks Mono Paint.NET - Not Open Source ASP.NET MVC Framework .Net Framework Source Code The Weekly Source Code (Scott Hanselman's Series) Microsoft's Pattern and Practices

  Read the article

• How do you draw like a Crayon?

  - by Simucal

  Crayon Physics Deluxe is a commercial game that came out recently. Watch the video on the main link to get an idea of what I'm talking about. It allows you to draw shapes and have them react with proper physics. The goal is to move a ball to a star across the screen using contraptions and shapes you build. While the game is basically a wrapper for the popular Box2D Physics Engine, it does have one feature that I'm curious about how it is implemented. Its drawing looks very much like a Crayon. You can see the texture of the crayon and as it draws it varies in thickness and darkness just like an actual crayon drawing would look like. The background texture is freely available here. Close up of crayon drawing - Note the varying darkness What kind of algorithm would be used to render those lines in a way that looks like a Crayon? Is it a simple texture applied with a random thickness and darkness or is there something more going on?

  Read the article

• How can I write a clean Repository without exposing IQueryable to the rest of my application?

  - by Simucal

  So, I've read all the Q&A's here on SO regarding the subject of whether or not to expose IQueryable to the rest of your project or not (see here, and here), and I've ultimately decided that I don't want to expose IQueryable to anything but my Model. Because IQueryable is tied to certain persistence implementations I don't like the idea of locking myself into this. Similarly, I'm not sure how good I feel about classes further down the call chain modifying the actual query that aren't in the repository. So, does anyone have any suggestions for how to write a clean and concise Repository without doing this? One problem I see, is my Repository will blow up from a ton of methods for various things I need to filter my query off of. Having a bunch of: IEnumerable GetProductsSinceDate(DateTime date); IEnumberable GetProductsByName(string name); IEnumberable GetProductsByID(int ID); If I was allowing IQueryable to be passed around I could easily have a generic repository that looked like: public interface IRepository<T> where T : class { T GetById(int id); IQueryable<T> GetAll(); void InsertOnSubmit(T entity); void DeleteOnSubmit(T entity); void SubmitChanges(); } However, if you aren't using IQueryable then methods like GetAll() aren't really practical since lazy evaluation won't be taking place down the line. I don't want to return 10,000 records only to use 10 of them later. What is the answer here? In Conery's MVC Storefront he created another layer called the "Service" layer which received IQueryable results from the respository and was responsible for applying various filters. Is this what I should do, or something similar? Have my repository return IQueryable but restrict access to it by hiding it behind a bunch of filter classes like GetProductByName, which will return a concrete type like IList or IEnumerable?

  Read the article

• Does anyone else get worn out using Scrum, finishing sprint after sprint?

  - by Simucal

  I'm with a pretty small startup and we started using a form of a Scrum/Agile development cycle. In many ways I enjoy Scrum. We have relatively short sprints (2 weeks) and I like the Burndown Chart to track the teams progress. I also like the Feature Board so I always know what I should be doing next. It feels good taking down a feature's card from the board, completing it and then putting it in the burn down pile. However, we are now entering in our 18th Sprint release cycle and I'm starting to feel a little burnt out. It isn't that I don't like job or my co-workers, it is just that these sprints are... well, sprints. From start to finish I literally feel like I'm racing against the clock to maintain our development velocity. When we are done with the sprint we spend one day planning the next sprints feature set and estimates and then off we go again. For people who work in a mature Agile/Scrum development process, is this normal? Or are we missing something? Is there normally time in a Scrum enviornment that is unassigned/untracked to get done some minor things and to clear your head?

  Read the article

• What are some resources for learning Lambda Calculus?

  - by Simucal

  So the Wikipedia entry on Lambda Calculus was interesting but I've finished it. I wish to dive a little deeper and get a better understanding of Lambda Calculus. Can anyone recommend what they consider to be the best book or primer to Lambda Calculus?

  Read the article

• What programming languages do the top tier Universities teach?

  - by Simucal

  I'm constantly being inundated with articles and people talking about how most of today's Universities are nothing more than Java vocational schools churning out mediocre programmer after mediocre programmer. Our very own Joel Spolsky has his famous article, "The Perils of Java Schools." Similarly, Alan Kay, a famous Computer Scientist (and SO member) has said this in the past: "I fear — as far as I can tell — that most undergraduate degrees in computer science these days are basically Java vocational training." - Alan Kay (link) If the languages being taught by the schools are considered such a contributing factor to the quality of the school's program then I'm curious what languages do the "top-tier" computer science schools teach (MIT, Carnegie Mellon, Stanford, etc)? If the average school is performing so poorly due in large part the languages (or lack of) that they teach then what languages do the supposed "good" cs programs teach that differentiate them? If you can, provide the name of the school you attended, followed by a list of the languages they use throughout their coursework. Edit: Shog-9 asks why I don't get this information directly from the schools websites themselves. I would, but many schools websites don't discuss the languages they use in their class descriptions. Quite a few will say, "using high-level languages we will...", without elaborating on which languages they use. So, we should be able to get a pretty accurate list of languages taught at various well known institutions from the various SO members who have attended at them.

  Read the article

• Generate colors between red and green for a power meter?

  - by Simucal

  I'm writing a java game and I want to implement a power meter for how hard you are going to shoot something. I need to write a function that takes a int between 0 - 100, and based on how high that number is, it will return a color between Green (0 on the power scale) and Red (100 on the power scale). Similar to how volume controls work: What operation do I need to do on the Red, Green, and Blue components of a color to generate the colors between Green and Red? So, I could run say, getColor(80) and it will return an orangish color (its values in R, G, B) or getColor(10) which will return a more Green/Yellow rgb value. I know I need to increase components of the R, G, B values for a new color, but I don't know specifically what goes up or down as the colors shift from Green-Red. Progress: I ended up using HSV/HSB color space because I liked the gradiant better (no dark browns in the middle). The function I used was (in java): public Color getColor(double power) { double H = power * 0.4; // Hue (note 0.4 = Green, see huge chart below) double S = 0.9; // Saturation double B = 0.9; // Brightness return Color.getHSBColor((float)H, (float)S, (float)B); } Where "power" is a number between 0.0 and 1.0. 0.0 will return a bright red, 1.0 will return a bright green. Java Hue Chart: Thanks everyone for helping me with this!

  Read the article

• What is the best way to translate this recursive python method into Java?

  - by Simucal

  In another question I was provided with a great answer involving generating certain sets for the Chinese Postman Problem. The answer provided was: def get_pairs(s): if not s: yield [] else: i = min(s) for j in s - set([i]): for r in get_pairs(s - set([i, j])): yield [(i, j)] + r for x in get_pairs(set([1,2,3,4,5,6])): print x This will output the desire result of: [(1, 2), (3, 4), (5, 6)] [(1, 2), (3, 5), (4, 6)] [(1, 2), (3, 6), (4, 5)] [(1, 3), (2, 4), (5, 6)] [(1, 3), (2, 5), (4, 6)] [(1, 3), (2, 6), (4, 5)] [(1, 4), (2, 3), (5, 6)] [(1, 4), (2, 5), (3, 6)] [(1, 4), (2, 6), (3, 5)] [(1, 5), (2, 3), (4, 6)] [(1, 5), (2, 4), (3, 6)] [(1, 5), (2, 6), (3, 4)] [(1, 6), (2, 3), (4, 5)] [(1, 6), (2, 4), (3, 5)] [(1, 6), (2, 5), (3, 4)] This really shows off the expressiveness of Python because this is almost exactly how I would write the pseudo-code for the algorithm. I especially like the usage of yield and and the way that sets are treated as first class citizens. However, there in lies my problem. What would be the best way to: 1.Duplicate the functionality of the yield return construct in Java? Would it instead be best to maintain a list and append my partial results to this list? How would you handle the yield keyword. 2.Handle the dealing with the sets? I know that I could probably use one of the Java collections which implements that implements the Set interface and then using things like removeAll() to give me a set difference. Is this what you would do in that case? Ultimately, I'm looking to reduce this method into as concise and straightforward way as possible in Java. I'm thinking the return type of the java version of this method will likely return a list of int arrays or something similar. How would you handle the situations above when converting this method into Java?

  Read the article

• Parsing basic math equations for children's educational software?

  - by Simucal

  Inspired by a recent TED talk, I want to write a small piece of educational software. The researcher created little miniature computers in the shape of blocks called "Siftables". [David Merril, inventor - with Siftables in the background.] There were many applications he used the blocks in but my favorite was when each block was a number or basic operation symbol. You could then re-arrange the blocks of numbers or operation symbols in a line, and it would display an answer on another siftable block. So, I've decided I wanted to implemented a software version of "Math Siftables" on a limited scale as my final project for a CS course I'm taking. What is the generally accepted way for parsing and interpreting a string of math expressions, and if they are valid, perform the operation? Is this a case where I should implement a full parser/lexer? I would imagine interpreting basic math expressions would be a semi-common problem in computer science so I'm looking for the right way to approach this. For example, if my Math Siftable blocks where arranged like: [1] [+] [2] This would be a valid sequence and I would perform the necessary operation to arrive at "3". However, if the child were to drag several operation blocks together such as: [2] [\] [\] [5] It would obviously be invalid. Ultimately, I want to be able to parse and interpret any number of chains of operations with the blocks that the user can drag together. Can anyone explain to me or point me to resources for parsing basic math expressions? I'd prefer as much of a language agnostic answer as possible.

  Read the article

• How do emulators work and how are they written?

  - by Simucal

  How do emulators work? When I see NES / SNES or C64 emulators, it astounds me. Do you have to emulate the processor of those machines by interpreting it's particular assembly instructions? What else goes into it? How are they typically designed? Can you give any advice for someone interested in writing an emulator (particularly a game system)?

  Read the article

• How should I generate the partitions / pairs for the Chinese Postman problem?

  - by Simucal

  I'm working on a program for class that involves solving the Chinese Postman problem. Our assignment only requires us to write a program to solve it for a hard-coded graph but I'm attempting to solve it for the general case on my own. The part that is giving me trouble is generating the partitions of pairings for the odd vertices. For example, if I had the following labeled odd verticies in a graph: 1 2 3 4 5 6 I need to find all the possible pairings / partitions I can make with these vertices. I've figured out I'll have i paritions given: n = num of odd verticies k = n / 2 i = ((2k)(2k-1)(2k-2)...(k+1))/2 So, given the 6 odd verticies above, we will know that we need to generate i = 15 partitions. The 15 partions would look like: 1 2 3 4 5 6 1 2 3 5 4 6 1 2 3 6 4 5 ... 1 6 ... Then, for each partition, I take each pair and find the shortest distance between them and sum them for that partition. The partition with the total smallest distance between its pairs is selected, and I then double all the edges between the shortest path between the odd vertices (found in the selected partition). These represent the edges the postman will have to walk twice. At first I thought I had worked out an appropriate algorithm for generating these partitions / pairs but it is flawed. I found it wasn't a simple permutation/combination problem. Does anyone who has studied this problem before have any tips that can help point me in the right direction for generating these partitions?

  Read the article

• How do you keep track of your programming TODOs?

  - by Simucal

  I'm one of those people who can't get anything done without a to-do list. If it isn't on the list it doesn't exist. Notepad Method: When I'm programming I've been keeping notepad open with a list of to-do's for my current project. I'll constantly re-arrange these based off priority and I cross them off and move them to the completed section when I'm finished with that particular task. Code Comments: Some programmers pepper their projects source code with: // TODO: Fix this completely atrocious code before anyone sees it Plus, I know that there are some tools that show you a list of all TODOs in your code as well. Website Task Tracker: Remember The Milk Backpack Manymoon Voo2do Gmail Tasks TeuxDeux TodoDodo Ta-da lists ... and many more What have you found to be the best method of keeping track of your to-do lists for multiple projects? Related Question: What can someone do to get organized around here? Related Question: Getting Organized; the to-do list.

  Read the article

• Zip Code to City/State and vice-versa in a database?

  - by Simucal

  I'm new to SQL and relational databases and I have what I would imagine is a common problem. I'm making a website and when each user submits a post they have to provide a location in either a zip code or a City/State. What is the best practice for handling this? Do I simply create a Zip Code and City and State table and query against them or are there ready made solutions for handling this? I'm using SQL Server 2005 if it makes a difference. I need to be able to retrieve a zip code given a city/state or I need to be able to spit out the city state given a zip code.

  Read the article

1