Tag Info

Hot answers tagged

8

No, it is not an impossible problem. There is a finite number of prime-numbers smaller than a given natural number, which means there is a finite number of ways they can be multiplied with while still being equal or less than the number. You can simply try them all until you found the correct solution. There are several algorithms for integer factorization ...


7

The short answer In order to license something to others, you have to hold the rights to it. So your ability to license your code covered by the patent may depend on what you can work out with the patent holder. The long answer There are a number of ways this can go. You can get a release from the patent holder. You can release your code and hope the ...


6

You've discovered the need for spatial indexing. R-trees are probably the most common approach. The basic idea is a tree structure with rectangular bounding boxes computed over all the children of a given node. That way searching for a region or a point can traverse the tree, pruning out any parts of the tree (most of it) where the bounding box is not a ...


5

There are a couple things to think about here - the structure of a card and the structure of the collection of cards... and all the while keeping in mind that this is Java and should be written with proper attention to object oriented principles. A card is a thing. Representing it entirely as a bit in a BitSet, or worse... doing your own bit manipulation ...


5

What you are asking for is possible given your constraints. Analysis A hash table's strength is its fast lookup and insertion speed. To get that speed, one must forsake any semblance of order in the table: i.e. entries are all jumbled up. A list is acceptable to use as a table entry because while traversal is O(n), the lists tend to be short assuming the ...


4

You basically have a tournament. In a round-robin tournament, 40 players can play 39 rounds and meet each player exactly once. The Wikipedia article on round robin tournaments has a description of a simple algorithm to generate the pairings for each round. There are also pre-computed tables on the Internet (look for Berger tables, for instance), but not ...


4

For the max stuff I'd use a heap, for the min a simple variable (to be potentially updated when the decrease operation lets the previous maximum fall all the way to the bottom of the heap).


4

Indeed, a tree is a good data structure for that. You can then create a BST which will allow to find by lookup a specific action based on the c1 to cn conditions. Obviously, this has a huge benefit of avoiding ugly code such as: if (c1) { if (c2) { if (c3) { ... } ... } ... } Whether the BST can be ...


4

After fidgeting around with the code a bit, I've got some better results. I went back to the original paper and ignored the wikipedia page. I've compared the algorithm to other quick select routines with some great results. Ok, here are the methods I have been playing with. Note these are for floating point and also that I changed my method from a void. ...


3

You are computing the sum of all the combinations of a set of numbers. The number of combinations you have is 2n, where n is the number of numbers. For example, if your array had 5 elements, it would be 25 which is 32. The combinations that you will be iterating through are the binary representations of 0..31. 00000 00001 00010 00011 ... 11111 This has ...


3

Siri typically doesn't "generate" sentences. She parses what you say and 'recognizes' certain keywords, sure, and for common responses, she will use a template, such as I found [N] restaurants fairly close to you or I couldn't find [X] in your music, [Username]. But most of her responses are canned, depending on her interpretation of your speech, in ...


3

If you need not strictly the global maximum but just a “fairly good” solution, you can approach this kind of problem by an approximation technique known as local search. The idea is that you start with a given solution and try to improve it by making “simple small steps”. In your case, such a step could be moving one ball from one box to another. Here is ...


3

Finding a factorization of a (usually large) number (often some bignum in practice) is an intractable problem : there is no known efficient (polynomial time) algorithm for that. But it is of course a decidable problem: you can try to divide that number N by every positive integer number I whose square I2 is not larger than N, and there is a finite (but often ...


3

1. No. You can do a LOT in game development with only the most shallow knowledge and understanding of Computer Science. You don't need CS knowledge to do graphic design, nor do you need it for most 3D design. You don't need CS to tell a story, which is essentially what most quest games do. You don't need CS to think about game-play and usability, and design ...


3

The short answer is yes. It depends on the complexity and innovation of the game being designed. Some games, say, Gravity Master, looks simple enough but actually requires a rigid body physics solver. All games involve programming; software with increasing functionality requires more programming, which I hope is obvious to you. The majority of games ...


3

For item quantities A, B, C and buckets quantity N, each bucket should keep close to A/N + B/N + C/N items, respectively of each kind. Actual putting the items should take O(N). You can distribute A mod N + B mod N + C mod N items slightly unevenly among buckets using round-robin choice: put a remaining item of type A into bucket #1, remaining item of type ...


3

You can check each point pair P[i],P[i+1] against each point pair P[j],P[j+1] If any of the lines segments they create intersect then the curve is not simple. Naively check each line: for(int i = 0; i < n-3; i++) for(int j = i+2; j < n-1; j++) if(doIntersect(new Line(P[i],P[i+1]), new Line(P[j],P[j+1])); I skip checking P[i],P[i+1] ...


3

Your grammar will be correct if your catch-all rule only consumes a single character and if you use prioritized choice in the grammar so that static is only attempted as a last resort. Of course, these single-character tokens are terribly inefficient. There are two ways to fix this: let the catch-all rule be static : [^\{]+ | . have your parser store a ...


2

It looks like all your items have the same size, in which case the solution is trivial. Count the total number of items, let's say that number is c. Say there are n buckets. Calculate x = floor (c / n) and y = c - n*x. Then y bins get filled with x+1 items, and n-y bins filled with x items. To make this an interesting problem, assume that the different ...


2

Using a binary tree for collision handling in a hash table isn't just possible - it has been done. Walter Bright is best known as the inventor of the D programming language, but also wrote an ECMAScript variant called DMDScript. In the past, a headline claim of DMDScript (or possibly an ancestor - I seem to remember the name DScript) was that its hashtables ...


2

I do not know what DP algorithms you tried, but here is one which solves your problem in O(M * N²), which is certainly better than O(N^M). The algorithm works inductively by increasing number of boxes. In each step, you store the maximum of f1+...+f_m, where m is the number of boxes in the particular step (0<=m<=M). For a given m, you solve the ...


2

What you are looking for is called a Spatial Index. In your case, you are looking for simplest case of getting all 2D points inside a rectangle. Even simple quad tree should be great improvement if you have lots of points. The problem of those kind of indexing algorithms and structures is that they are highly dependent of shape of the data. While they all ...


2

This is my full answer. At the end didn't understand the (i & mask >> j)part so I use an IF. To see if the elem is part of the sum. int[] elem = new int[] { 1, 2, 3, 4, 5 }; double maxElem = Math.Pow(2, elem.Length); for (int first = 0; first < maxElem; first++) { int mask = 1; int sum = 0; for (int run = 0; run < elem.Length; ...


2

Code doesn't infringe on patents. Code running on a computer can infringe on patents. There was a major (billion dollar) case where Microsoft wa accused of patent infringement, and it turned out that an infringing device was created at the moment when the software was installed on a computer, and not earlier. For example not when a million CDs or DVDs with ...


2

The worst-case is O(∞). The best-case is O(n2), because you have to generate n numbers, and for each number generated you have to search a list of length n whether or not the number is already in there.


2

You could argue that a curve is simple if there are no two line segments between points such that the lines intersect, meaning you could check if a curve is simple by verifying the absence of this condition. The algorithm would look something like: for each p1, p2 in pointlist for each p3, p4 in pointlist if line_segment(p1, p2) intersects ...


1

As it looks like these are primarily a list of exclusion filters, something like this might get you where you want to be (example in Java, includes calls to functions that probably don't exist as parts of the test): private static List<Predicate<Node>> AD_FILTERS = Arrays.asList( (node) -> node.getPreviousSibling().isIFrame(), (node) ...


1

It is a variation of Multi-armed bandit problem: In probability theory, the multi-armed bandit problem (sometimes called the K- or N-armed bandit problem) is a problem in which a gambler at a row of slot machines (sometimes known as "one-armed bandits") has to decide which machines to play, how many times to play each machine and in which order to play ...


1

You already have a function that can move a stack of any size, so use it: Use original hanoi to move a stack of 3 onto the odd stick. Move disc 4 to the even stick. Recurse for the remaining stack of 3. You basically have a more complicated choice of src and dst, but it's not terribly difficult. Note that many times, when you recurse your stack will ...


1

The problem you describe is the decision version of the longest path problem (ie. "Is there a path of length at least k?"). As Jimmy Hoffa noted, the problem is NP-complete. You could look into approximation algorithms for the LPP, particularly ones that exploit any special structure your graphs might have.



Only top voted, non community-wiki answers of a minimum length are eligible