Tag Info

Hot answers tagged

27

The restrictions in copyleft licenses like the GPL apply to modified versions of your code as well as your original code. So they can't just tweak the whitespace or brace style and then delete your license statement. However, you can't patent/copyright/copyleft/whatever an "algorithm" in its most abstract sense. You can put a license on your favorite ...


12

If you want to prevent a patentable thing from being patented and then "closed off" from the greater community you could do a defensive disclosure. Cuis Smalltalk, for instance, did this with some new anti-aliasing techniques: http://www.defensivepublications.org/publications/prefiltering-antialiasing-for-general-vector-graphics ...


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).


9

I see some valuable information in the other answers and the comments, but also some misinformation, so I try to give a summary and add some additional things. Will I have some advantage if I open source the algorithm under copyleft licence (GPL etc.)? By publishing the source code of an implementation of your algorithm under GPL (I assume that is what ...


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; ...


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 ...


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}; ...


5

You can't "copyleft" an algorithm. "Copyleft" relies upon copyright protection for its enforceability, but algorithms are not copyrightable, so you can't "copyleft" an algorithm. In other words, your question might be based on a faulty premise. Copyright can only be used to protect a specific implementation, not the idea of the algorithm. So, you could ...


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 ...


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 ...


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 ...


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

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 ...


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; ...


3

Copyleft doesn't have anything to do with copyright or patent protection. It doesn't provide any protection to you, the copyright holder, that you wouldn't otherwise already have. It has everything to do with distribution, however. Copyleft protects users of your code by requiring you and anyone else who uses their code to distribute the entire source ...


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 ...


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 ...


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 ...


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 ...


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 ...


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 ) { ...


2

You can slice up the problem in subprocess (pseudocode): array[] GetArrays(j, n) if(n = 0) return one empty array if(j = 0) return one array of n zeroes array[] zero = map(prepend 0, GetArrays(j, n-1)) array[] one = map(prepend 1, GetArrays(j - 1, n - 1)) return concat(zero, one)


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 ...


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 ...


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, ...


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 ...


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


1

First, since we only care about the y-distance and will be drawing a horizontal line, we only need to think about the y-coordinates of the points and the y-coordinate that defines the line. The distance between a point and our line will be the absolute difference between the y-coordinate of the point and the y-coordinate that defines the line. So, ...



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