Tag Info

New answers tagged

0

Here is how I would tackle this problem. For simplicity, let's just assume that G is connected (The algorithm to be described below can be easily extended for the case when G is not connected). First, for any feedback-edge set F, it must be true that the graph G' = (V, E-F) doesn't have any cycle. This follows directly from the definition of feedback-edge ...


3

A common way to read data coming into the computer is to buffer it from a stream. Streams sometimes have an undefined length. All we know for sure is we can "get next character from stream". Normally we'd add the character from the stream to the end of the buffer (think FIFO queue). The size of the buffer doesn't necessarily have to be the size of the ...


1

Here is one such scheme. It is only a brief idea, I did not check it carefully for potential fallacies. Before starting, we perform the following configuration: For every natural number N (1, 2, 3, ...), choose a bit shuffling function for N bits. Procedure for converting query integer I to response integer J Given a query integer I, convert it ...


0

I made a slightly different algorithm: def share(available, members): # find across how many members we must distribute and what the total sum of those values is total = available for idx, member in enumerate(members): total += member count = idx+1 if (idx >= len(members)-1): break if (total / ...


1

This is easy. Walk down the tree (quad tree or R-Tree, etc) until you find the lowest node that contains the “search point”. Then look at the parent of that node, and check all points that is contained within the parent (including sub notes) If you have not found enough points, then move on to the parent’s parent etc. Remember That the nearest point ...


0

This algorithm is basically a merge join: the two arrays are first sorted, and then two cursors are declared (one per array). The cursors can move independently along the arrays (forward iteration only), depending on the result of the comparisons. It minimizes the resulting number of comparisons. Obviously, it does not really calculate the intersection of ...


0

I totally understand you. I too worked for nearly 20 years doing software engineering. And I've seen some of those challenges and they are difficult even for a seasons and educated engineer. The only difference is I wasn't lacking in algorithms or data structures but rather other areas. My recommendations are as follows: iTunesU, search for courses on ...


1

I use a two state, two stack model similar to the Shunting Yard algorithm. The two states are the unary state and the binary state. In each state, you handle tokens (or issue errors) and then either continue the same state or switch to the other state. In the unary state, if you find an open paren, (, it is operator grouping, and, you stay in the unary ...


1

It's an opening bracket which follows directly after a identifier. So when you meet a open bracket you check whether the last token you parsed was a identifier or a operator. If it was an operator then it's a just a subexpression if not then it's part of a function call. Comments should be dealt with before the you parse the token stream. This turns you ...


0

I'm not sure what the upper bound of the best case would be good for, but at times it may be useful to identify the lower bound for the worst case for the best possible algorithm that could perform a given task. Such information could be useful if one has an algorithm that e.g. runs in time O(N^2lgN) and is trying to decide if one should try to find ...


6

Just extending Karl Bielefeldt idea for a 2 walls reflections: A and B are given (the tanks). You first must list all walls that A can see and a list of all walls B can see. Then you make pairs where the first wall is in the fist list and the second wall is different from the first wall and is in the second list. You need to make this test for all possible ...


8

Given a direct line of sight, the problem is obviously trivial. However, we are dealing with reflection. Properly finding out which parts of the scene can be seen is challenging when implementing reflection as part of a ray tracer, since this might miss some openings. A “binary search” between two promising angles is also not viable: due to the reflections, ...


1

You have neat diagrams showing how to direct rays, so I'll leave the details on how to determine a pair of reflecting surfaces. Let's call the surface that must be hit first surface A, and the second, B. Try to hit the (visible) edges of B by shooting at A. In other words, determine the points where one would see reflections of the ends of B if looking at ...


3

You can take advantage of the fact that the angle leaving the ricochet must be the same as the angle entering it. For a given horizontal wall with y-coordinate c and two fixed tanks with coordinates (a,b) and (d,e), there is only one angle which satisfies the equation below. Just solve for x to get the distance along the wall at which you must aim. Two ...


-2

First off, remember in physics class when you talked about refraction of light? Well your problem can be solved using those principles. The angle of incidence is equal to the angle of reflection. so the enemy tank needs to run through every possible angle for the first bounce so that the second bounce may hit the player. Keep going with the ray tracing idea ...


1

At some point you just need to graduate to a proper parser, because there are too many things to track and too many boundary cases. Adding function calls to the peg.js example grammar, you get. primary = integer / "(" additive:additive ")" { return additive; } / function_call function_call = [a-z]+ "(" args ")" args = (additive ("," ...


1

Treat the comma as an infix operator. Then max(1,3,7)*4+5 becomes + / \ * 5 / \ max 4 | , / \ , 7 / \ 1 3 The comma should have a lower precedence than your calculation operators (+ - * / etc.).


-1

I think you're looking for this: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.510.1758&rep=rep1&type=pdf It details how to create an optimal dictionary-representing DAWG.


0

Yes, but it should be the opposite way: DFS is similar to PreOrder. Term PreOrder is more relevant to binary trees and parsers. It is used to compare with other traversal orders of a binary tree: InOrder, PostOrder and PreOrder. Topological Sort is similar to Post Order traversal (push the node into stack after visiting all the adjacent nodes).


-1

As others pointed out here and on http://stackoverflow.com/questions/4948780/magic-numbers-in-boosthash-combine, the number is indeed constructed from the golden ratio. But there is another important reason why numbers such as pi, phi or e are used in cryptographic functions. Of course, in principle, any "reasonably random" bit sequence could be used as a ...


1

You seem to be at least O(n^2) (see big O notation) as you loop over all boxes in the world in “Begin()”, then for each box, you loop over all boxes in the world in ExtractLargest(). So a world with 10 unrelated boxes will take 4 times longer than a world with 5 unrelated boxes. You therefore need to limit the number of boxes that ExtractLargest() has to ...


6

You can make use of the fact that when BoxIsFilledWithCubes(c,x,y,z) returns true, then it is not necessary to check in BoxIsFilledWithCubes(c,x+1,y,z) all those cubes in the coordinate range "(c,x,y,z)" again. You need only to check those cubes with the new x-coordinate c.x + (x+1). (Same is true for y+1, or z+1). More generally, by splitting up a box ...


5

Build up an octree with a leaf node aabb size of the size of your box. While traversing the octree you can cheaply merge nodes. Completely filled nodes are trivial to merge (new box = parent aabb), while for partially filled nodes, you can use a variant of your current algorithm to check merge-ability.


2

A good guideline is that your tests should exercise all the code that you've written. If different inputs cause different code paths to be executed, it is a good idea to choose your test inputs so that every path is covered. More thorough testing also tries to ensure that every path is covered under different circumstances, particularly with extreme ...


3

prefix trie: It's a degenerate DFA without cycles. For implementation you have a int state and a int nextState[256] for each state. For Matching states you would make the state number for it negative so you know when it's reached.


2

In principle a search Trie is what you want, but you'd have to profile your actual data to find out when that actually performs better (it might always be worse unless you can find a cache-friendly layout). Edit based on comments: Are you matching a stream or discrete packets? If the former, and you need to handle matches spanning the boundary between ...


3

If looks like a O(n³) solution. Your instinct is correct: by resetting variables you are looping. Note: if we only consider the loop instruction we would, mistakenly, think it was O(∞). However the problem is O(n). Therefore you can do better.


3

To balance the other answer - this particular case is a question of math literacy rather than creativity. This is just a tiny piece of the centuries old baggage of knowledge that should have been imprinted into you in school (most likely together with the little Gauss story mentioned in the comments). While you don't need math to program, there are certain ...


2

Because the factor log n grows slowly, a qualitative description for O(n log n) would be "almost linear". Depending on your audience the class of O(n log n) algorithms might be well known, as for example this is the case with fast sorting on n items by comparisons.


0

The maximum execution time of this algorithm is O (sqrt (n)), which will be achieved if n is prime or the product of two large prime numbers. Average execution time is tricky; I'd say something like O (sqrt (n) / log n), because there are not that many numbers with only large prime factors.


49

There is a jargon term linearithmic meaning exactly this. I don't believe that it's universally understood by all programmers, so if you're not careful then it will obscure more than it informs. Personally I don't normally use it, and if I did then I'd probably define it on first use, for example "this article considers linearithmic (O(N log N)) ...


11

It is sometimes called "loglinear", although that word actually means something different. I would just stick with "N log N", though, as @Philip's answer suggests.


4

You are asking essentially for the secret of creativity. I'm sorry; there is no secret that anyone could tell you. Finding new solutions, concepts, proof etc. is, by definition, an unpredictable thing, and it's the most prominent thing that we haven't successfully computerized yet. (If it's any consolation to you, the way in which someone invented a clever ...


58

"N log N" is as good as you're going to get, and should be well understood by professional programmers. You can't expect there to be a single word to describe every complexity class that exists.


2

I believe the direct answer is simply that functions are not operators. From the page you linked: If the token is a function token, then push it onto the stack. This is all it needs to say, since the function case (prefix to postfix) is much simpler than the operator case (infix to postfix). For the follow-up questions: The notions of precedence and ...


3

Well, do you or don't you have the data in a normal database? If you do, there is no way around querying all possible matches from the data base (with a long query full of OR operators) and then sorting the result however you see fit. In other words, you're not looking for a search algorithm, but for sorting functions. You can only solve this problem with ...


1

Usually the benefit from using non-deterministic algorithms is simple: Runtime. It is often used in Monte-Carlo algorithms, which basically try a predefined number of possibilities (i.e. "Is this text German?" - "No", "Is this text spanish?" - "No", "Well, no idea then".). While the deterministic solution would be to try every single possibility, which is ...


5

Your solution seems to try to tackle average reading time of nodes and all paths from them. This will, of course, work, provided it's properly implemented. The problem with this approach is that the quantities you calculate are not reusable. The average reading time of a node depends on how you got to it. Hence the quadratic behaviour of your naive ...


2

Its a multipart piece of information you need to communicate. First off, you provide the timestamp. That is what you validate against for the 'was submitted within 15 minutes'. Secondly, you have a hash of the timestamp with some additional salt. The salt is known only to you (on the server). If the time stamp was altered, the hash of the altered time ...


0

Why should I do it? So we create a form, and we'll have an endpoint where that data can get submitted. Which means anyone can submit data there and see what happens. So we need to validate on two things: that it's being submitted by a user (which .NET will handle for us), and that they're submitting data via a requested form and not just willy-nilly ...


1

I looked at the source code of the dictionary and noticed the use of "buckets". I'm not exactly sure how a dictionary sorts objects into buckets but it's a simple task with integers. The main problem, I've logiced, is converting the input into an index that's small as possible yet doesn't collide with other inputs' indexes to make the array the outputs are ...


3

This answer is merely provided to reduce the frustration. In general, a person is better advised to learn how to conduct performance benchmarking properly before asking such a question. If your "keys" exclusively consist of consecutive integers, you can use an integer array. Zero-based consecutive integers can be used as array index as-is. Non-zero-based ...


3

First, your definition of your numbers can lead to non-fractions (e.g., p=2, q=0). Second, to summarize your idea: Store all your fractions as integers Perform an integer sort Convert all your integers back to fractions Seems like a lot of unnecessary memory and time when a lot of sorting algorithms can be done using a simple comparison sort and you can ...


0

What you are trying to do is typically a series of image processing problems. Have a look at algorithms in ImageJ such as the canny edge detector for finding edges in an image. This will produce a greyscale image where edges are lighter in color than non edges. These can sometimes do the job of finding the edge well enough with a little contextual help on ...


1

It looks like you don't want >= and <=, because then touching boxes are considered colliding. Use > and < instead.


0

There are so many different cases to consider when developing collision detection that it can get confusing. I'd recommend implementing the Separating Axis Theorem(SAT) to detect collisions between convex objects. It takes into account position and rotation of objects and lets you handle the collisions. You can take a look at this video I made a few months ...


1

The best way is to divide the problem space first, so you only have to consider how many farmers want how many seeds of a particular fruit type and quality. You can do this in a single iteration. You need to know how many of each fruit and seed type is being requested. Then divide the number of seeds of each quality by the desired number, rounding down, and ...


-1

This looks like variation of nonogram puzzle. You can find some inspiration from existing nonogram solvers. It seems that you would need to add constraint about boxes not touching diagonally.


1

When solving a puzzle like this, there are two things you can do: Look for places where you can apply some pattern to cross out a square or plant a tree there with certainty Make a guess, and proceed until it either comes to an unsolveable situation (in which case you backtrack to your previous guess), or you finish. For this particular puzzle, the ...


5

If you are allowed to remember past data, A* is indeed your best bet. I used it on Google's Ant AI challenge, which only has a small radius of view. The main difference with a limited field of view is you do a lot more walking around just to explore, but that's unavoidable. A* will give you a pretty good list of where to explore, without having to visit ...



Top 50 recent answers are included