Tag Info

New answers tagged

0

If you think about the problem a bit, it should be obvious that of the eight queens, one must be on the first line, one must be on the second line, and so on. So the only thing you need to find is where in the first line the first queen is, where in the second line the second queen is, and so on. Here is an excellent data structure for that: int position ...


1

This is a simple Python implementation: from random import random def select(container, weights): total_weight = float(sum(weights)) rel_weight = [w / total_weight for w in weights] # Probability for each element probs = [sum(rel_weight[:i + 1]) for i in range(len(rel_weight))] for (i, element) in enumerate(container): if ...


2

You say, "encompass smaller polygons," but then you seem to treat these polygons as points. If they are indeed effectively points, as opposed to extended polygons, then you are seeking to solve the Traveling Salesman Problem, or TSP, which is a heavily studied (and difficult) problem. Your instance is not a pure TSP, because you have a bounding, ...


3

I am not going to code it but I will give you a math approach. Assuming you know the resulting width with two different font sizes: font size 1 (s1) implies text width 1 (w1) (the small value) font size 2 (s2) implies text width 2 (w2) (the bigger value) then your linear estimate of size (s3) that will fit the required width (w) is from using manipulating ...


2

I'd like to add to SF's solution a bit. Not sure if I am correct in my analysis, but anyway: If your preprocessing is free (considering search will be done enough times) you can preprocess each word in a dict by producing for it an entity like the index SF mentioned. So each word becomes a number like 01000100011101.... (up to the last letter a set of ...


0

I have a conceptual solution for you that some of the largest online shops use for related products setup: Install Solr instance. Upon addition of your product into the database, parse the title and generate a number of tags from it and store them in Solr along with the products. Adjust tags weight as needed and enjoy the results. For example, tags "wine" ...


0

You can put anything you want into the evaluation function, but the obvious one would be to score the number of 2 and 3 in-a-rows that are not blocked. Quarto would be an ideal candidate to use MCTS instead of alpha-beta.


2

First thing is to know the partitions of the number 5 (the team size you want to assembly). There are algorithms to generate the partitions of a number but since the number is small and fixed you don't need to worry about it. The partitions of 5 are: {5}, {4,1}, {3,2}, {3,1,1}, {2,2,1), {2,1,1,1}, and {1,1,1,1,1}. Make 5 lobby lists (L1,L2,L3,L4,L5). One ...


1

Calculate the total rank of all players in a single lobby. Match with other lobby based on that. (+- 1.5 range pretty much) Isn't it as simple as this?


4

Consider: Mode 1 is only more efficient when you have a run of the same tens digit. Mode 1 saves 1 character for each same tens digit, except the first It costs 2 characters to switch to mode 1. Therefore Mode 1 only becomes advantageous after 4 similar 10s characters (costs 2, saves 3) For example, consider if you are running in mode 0. A switch to mode ...


3

Taking clues from LINQ, a typical way to workaround this fundamental impossibility is to implement a Take function, which takes the first N values from the lazy collection (or enumerator) and then process only those N values. To use it, the user must specify how many values to "take" each time. Collections which are already sorted or histogrammed (binned ...


4

In short, no, there is no way to do sorting on an incomplete collection unless you will delay sorting until the very end wen the collection is already present. Longer version: Sorting by definition involves evaluating the entire set of items and arranging them in the right order. I doubt you can do sorting on the the collection without having the entire ...


3

This is not a traveling salesman problem if there is no prohibition on revisiting a system. The problem for Question 1 is canonically referred to as the minimum mean cycle problem, which has polynomial-time algorithms. This is a subroutine in some min-cost flow algorithms. Question 2 is sort of ill-defined because there won't be a best route in general; ...


1

Personally I don't know the reasoning behind those books and I don't claim to have any unique insight on this issue. However, external merge sort can be implemented in exactly two stages, and neither stage contain recursive subdivision. In other words, in both stages, there is only one level of subdivision. Choose number of subdivision N. Stage 1: ...


-1

Assume both A and B have a million members, and you have sorted A and B. How many pairs can you form with A [0]? To find out, you add A [0] + B [0], A [0] + B [1], A [0] + B [2] etc. You stop when the result is too large, and then you know how many. Say A [0] + B [920178] is not too large, but A [0] + B [920179] is too large, then you can form 920179 pairs ...


0

Your problem is floating-point number formats. They're basically stored as Sign*Man*2^Exp. For 32 bits floating point types, there's only 9 bits of exponent available, and even 64 bits FP uses a mere 11 bits. But once you take the log of that value, you're effectively user the far large magnitude field to store your original exponent. There's also ...


7

TL:DR; Your code is already correct and "clean". I see a lot of people waffling around the answer but everyone is missing the forest through the trees. Let's do the full computer science and mathematical analysis to completely understand this question. First, we note that we have 3 variables, each with 3 states: <, =, or >. The total number of ...


2

The key to doing this efficiently is exploiting the fact that if a1 < a2, then pair(a2) \subseteq pair(a1), where pair(a) = {b \in B : a + b <= S}. Example Java code: Arrays.sort( A ); Arrays.sort( B ); int count = 0; int j = B.length - 1; for( int i = 0; i < A.length; ++i ) { while( j >= 0 ) { if( A[i] + B[j] <= S ) { ...


4

Working with log-probabilities helps with the problem of intermediate values overflowing (and underflowing). Instead of calculating L = P(x1|C)P(x2|C)..., you calculate log L = log P(x1|C) + log P(x2|C) + .... You can do two things with log L: If you're trying to maximize likelihood, you can directly maximize log-likelihood instead since log is monotonic ...


-1

I've had more of a think about this, so since my issue was mostly visual confirmation that all comparisons used the same variables, I think this might be a useful approach: a = countAs(); b = countBs(); c = countCs(); if (FIRST_IS_LARGEST(a, b, c)) status = MOSTLY_A; else if (SECOND_IS_LARGEST(a, b, c)) status = MOSTLY_B; else if ...


0

If you are interested in drawing concentric circles and don't mind performing a broard sweep of the AABB then the test to perform on each pixel is: distanceFromCenter <= radius && distanceFromCenter > (radius - someThreshold) Or as a more concrete example: void drawCircle(Point center, int radius, int thickness, Color color) { for (var ...


4

Look into Traveling Salesperson Problems and optimization. You are basically optimizing a TSP for all your four questions. The specific details will vary based on your problem size (if you have 10 nodes you can just brute force it, if you have 1000 you will have to be more efficient). The wikipedia site on TSPs suggests a large number of algorithms to ...


0

It is important that the circle is filled using concentric passes You can't draw anything "perfect" using "concentric passes" on Cartesian coordinate system, which is ultimately what you need to do. The pixels just don't align with your N-step-radius circles. But, you can make a good approximate. And the method you use should depend on what your ...


9

Factorize logic, return early As suggested in comments, it would be sufficient to simply wrap your logic in a function and exit early with return's in order to simplify things a lot. Also, you could factorize a bit of functionnality by delegating tests to another function. More concretely: bool mostly(max,u,v) { return max > u && max > v; ...


1

The most simple approach I can think of is: start with a fully filled circle in pink, and (use @Mandrill's answer for example), and draw only the white circles afterwards over the pink circle, using your existing Midpoint algorithm. That will leave no black spots, all the black spots get the color you started with. However, if you do not want to draw ...


5

@msw told you to use an array instead of a,b,c, and @Basile told you refactor the "max" logic into a function. Combining these two ideas leads to val[0] = countAs(); // in the real code, one should probably define val[1] = countBs(); // some enum for the indexes 0,1,2 here val[2] = countCs(); int result[]={DONT_KNOW, MOSTLY_A, MOSTLY_B, MOSTLY_C}; ...


-1

You probably should use a macro or a function MAX giving the maximum of two numbers. Then you just want: status = MAX(a,MAX(b,c)); You might have defined #define MAX(X,Y) (((X)>(Y))?(X):(Y)) but be cautious -notably about side effects- when using macros (since MAX(i++,j--) would behave strangely) So better define a function static inline int ...


2

Not exactly what you asked but I think just a vertical scan is easier: line((x_center-r,y_center)-(x_center+r,y_center)) for(y=y_center+1;y_center+r;y++) { w=sqrt((r+y)(r-y)) x_min=x_center-w x_max=x_center+w y_mirror=2*y_center-y line((x_min,y)-(x_max,y)) line((x_min,y_mirror)-(x_max,y_mirror)) } So if a circle in your screen has ...


3

The midpoint algorithm gives you the set of points lying "exactely" a given distance from the center. What you would want to do is to use another algorithm where you test if the distance is lower than (and not equal to) the radius. The brute force algorithm would be to check every cell in the grid, but if you really want to be efficient, you could perform ...


0

a=extractMin; res=getMin; insert(a);return res; [Folks: when answers are posted as comments, would you please add them as an answer and close the question. Thanks]


-2

A good place to start might be the Algorithms class on Coursera. You will get a broad overview of some important algorithms and data structures, video lectures, programming exercises, theory problems, and you can look at the references for more pointed information on certain problem. https://class.coursera.org/algo-007


0

The binary tree/segment tree-based solutions are indeed pointing in the right direction. One might object that they require a lot of extra memory, however. There are two solutions to these problems: Use an implicit data structure instead of a binary tree Use an M-ary tree instead of a binary tree The first point is that because the tree is highly ...


0

Analyzing complex algorithms requires lot mathematical background. For a refresher on analysis of standard algorithms you can refer to books. If you need a starting point for analysis of algorithms i would suggest to read some books on algorithms. The best book i can refer for analyzing algorithms is Introduction to Algorithms. If you would like to attend ...


-1

What you can try is to find the analytical expression that is equal to the cost of the algorithm you are working with. In many cases, this expression might be a sum (usually for nested loops). However, for a recursive algorithm, you might express it's cost with a recursive formula that you will have to solve. For example, the cost of a binary search may be ...


0

The π vector surely keeps the node u with which you came in node v. This helps when you have to build the BFS tree of the graph. Although it is not necessary, this technique reduces a lot the complexity when you have to perform more time the BFS (ex. the Edmonds–Karp algorithm for computing the maximum flow between two nodes in a graph). In this case you ...


0

Here is an O(n*log(k)) amortized* runtime and O(k) exact storage solution where n is the iteration limit and k is the number of divisors to test against. Algorithm: Preconditions: n is a non-negative integer, k is a positive integer, and each divisor supplied is a positive integer. Create a heap priority queue containing of (multiple, divisor, string) ...


0

The first thing to do is to get a precise specification of the task. "FizzBuzz" has two divisors (3 and 5), one word "Fizz" to be printed if the first divisor is present, and another "Buzz" to be printed if the second divisor is present. I seem to remember a variation where for numbers divisible by 15 the result wasn't "FizzBuzz" but "Fizzbuzz" or something ...


0

No because MD5 is a hash function not an encryption function it return a print of your string not an equivalent of the string. You can imagine this like a shadow if you have an object and his shadow you can said if the shadow represent your object (or any other object casting the same shadow) or not. But you can't have all informations on your object using ...


1

You are building a set of graphs. You start out and start walking the list of relationships you have gotten back. A -> C So, lets make a graph that represents that. A - C And then you've got: B -> D Neither B nor D are represented in any of the graphs currently. So now you have: A - C B - D And then C -> E, so we hunt up C and ...


11

I believe the use of π here is actual “parent of”. So in this case, the “parent” of v  is u because we're looking at all nodes adjacent to u. This verbiage can be found here (PDF link).


0

Generating the n-th combination is called a "unranking" algorithm. Note that permutations and combinations can often equated by the way the problem is parameterized. Without knowing exactly what the problem is, it is difficult to recommend the exact right approach, and in fact, for most combinatoric problems there are usually several different ...


1

Additionally to what @miniBill already wrote: after trimming the shape (or "moving" the shape to the lower left edge inside your m x n matrix), interpret the result as a binary number. Now do the same with the other 7 rotations & reflections, which yields you 8 numbers. Pick the minimum from those 8 values and assign this number to your original matrix, ...


1

You can simply "trim" the shapes (remove rows and columns full of 0) and then try the 8 rotations + reflections. This also gives you another heuristic: after trim the size must be the same or a rotation


0

Databases has special index type for such kind of searches based on Minimum Bounding Boxes, called r-tree. Let's assume that we have 1M places defined by x/y in our database and we want to find all points in radius from our position we first need to build MBR containing search circle (center point in this same place and edges 2r), search data and in next ...


3

I was hoping there would be some kind of database optimization Databases with spatial / geospatial extensions allow to store spatial objects and fast query operations like "is point in certain area", supported by so-called spatial indexes. The exact set of features as well as the syntax differs from DBMS to DBMS, but I do not know of a database which ...


0

You want to find things in a two-dimensional space easily. That is similar to the more common problem of finding things in a one-dimensional space; the solution there is to sort your data and then find things in it in O(log n) time via binary search. You can't do exactly the same thing for two-dimensional data because the ordering is not the same for the ...


3

I eventually got the answer I wanted by a smarter dynamic programming approach. The insight was to realize that although the nature of my problem didn't allow for a total ordering of all the elements, it did allow for a partial ordering of all the elements. The challenge, then, was to calculate the coverings in that partial order. To do that, I used the ...


2

Unless I'm mistaken: There are 20^5 = 3,200,000 ways to pick 5 numbers out of 20 (with repeating, with duplicates) If you don't allow for "duplicates" (picking the same number more than once), you're left with n! / (n - k)!, in this case 20! / (20 - 5)! = 1,860,480. These are k-permutations. If, then, you don't allow for "repeating" (having collections ...


1

Ok, now it became a bit clearer what the problem is. As I see it, every number can only be used once, so a list in the form of 50 100 50 50 20 30 50 50 100 50 is not possible. Initialize an empty stack. Start from the beginning of the list and the end of the list and if the numbers are the same push them onto the stack. Advance one forward and backwards and ...


1

The data structure is obviously recursively defined, and thus, a recursive solution is trivial: def count_elements(*elements) return Hash.new(0) if elements.empty? count = 0 element = elements.first count += 1 while element == elements[count] && count < elements.size count_elements(*elements.drop(count)).tap {|elements| ...



Top 50 recent answers are included