New answers tagged

0

Though I am not a lawyer... You are conflating several issues. So, let's try to tease them apart. There is copyright which applies to any code of sufficient size (more than a few lines?) that is re-used in another context. Here you need to abide by the copyright license of the code, which could range from forbidden to allowed. Open Source generally ...


3

Yes, it is. Concepts that people communicate to others in online forums are intended to be adopted by others. There is neither a tradition nor a legal basis for banning others from reusing the same algorithm (copyright protects only specific expressions of ideas, not the ideas themselves, trade secret status does not apply, and algorithms cannot be patented)...


1

I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique. The assumption that cryptographic hash functions are more unique is wrong, and in fact it can be shown to be often backwards in practice. In truth: Cryptographic hash functions must be ...


0

In your example solution, jobs 1 and 2 manage to group similar values within the same source but jobs 3 and 4 don't. All jobs keep their total workload under 50. This example solution appears to be the result of a greedy algorithm that grabs the first possible match. In general, greedy algorithms have five components: A candidate set, from which a ...


3

Thanks to @mattecapu for the useful Google search term of "backtracking algorithm". That gave me the food for thought I needed. My current intuition is that it might be better to fill in the center seats—which have 4 neighbors—first, and save the corner seats—which have only 2 neighbors—for last. So I arrange the 16 empty seats into a linked-list in this ...


0

So, it sounds like you want something relatively fluid. If yesterday was a snow day you could add it the day after and then rerun calculations to look at the workloads (theoretically) required to meet deadlines. Just thinking on the fly here: Jobs: Job ID, Name, Start Date, End Date Depts: Dept ID, Name, WeekType JobHours: Job ID, Dept ID, Allotted Hours ...


5

When Java encounters this + operator, it compiles the addition to byte code, specifically an iadd instruction. What the computer does when executing this instruction depends on how the virtual machine on which this program is executed was programmed. It might delegate to an ADD opcode from some processor's instruction set. It might consult an internal ...


1

As a commenter said, look up 'Audio Resampling'. Also, maybe buy the book called 'The Art of Digital Audio' or similar. Basically, what you are doing is linear interpolation, should work. But resampling at a much higher rate should allow you to pick samples (from the denser set) close to the sample points you need for e.g 2.5 speedup. Analyzing the error ...


1

I have little mathematical background but I do see an approach that might work. I would assign a value to each coordinate in the grid that is determined by the amount and closeness of dotted neighbors. Then apply a threshold: only keep the coordinates that exceed the threshold value. Those will form the result path.


0

The key to this is to extend the range of the counter that you are using to track time. Just keep a "number of overflows" 32bit counter that you increment each time the millis() value wraps, and use your counter and the millis() value to form a 64-bit counter -- that will give you a wrap time of 50 * 2^32 (or about 200 billion) days -- probably longer than ...


0

Possibly the most efficient way is to store all the tasks by their filter keys, so you'd keep track of key1 and associate task1 and task5 with it. You can then iterate through each input key to add the set of tasks for that key to a result set and then count the number of times each task appears in the results. For each task that appears the number of times ...


0

If you want to simulate a random variable with binomial distribution, just go ahead and do that. If you just want a quick and dirty number whose average approaches the expected number of deleted items, just use a uniform random variable with a suitable range, e.g.: (rand() * 0.6 + 0.4) * num_of_items Where rand() is uniform on [0; 1], rand() * 0.6 is ...


0

Its not clear what the purpose or requirement for this is, so I don't know if this will meet them. But you could loop over all objects, keeping a count mod 10, and deleting on 1-7. To add randomness start the count at a random value between 1 and 10. That would technically give you a 70%, effectively random deletion without a million random numbers. ...


2

As others have noted, you can use the binomial distribution. But I suggest you avoid trying to write your own algorithm, it is easy to screw that up. Instead, many languages have libraries that can generate binomial random variables. C++ has Boost.Random: http://www.boost.org/doc/libs/1_61_0/doc/html/boost/random/binomial_distribution.html Python has has ...


9

To get the number of items remaining, you need to sample from a binomial distribution, namely the distribution B(n, 0.3) where n is the original number of items. You can do this using only a single random number using the inverse transform method. A problem you might encounter is that computing the inverse CDF for the binomial distribution explicitly is (I'...


1

You would generate a random number between 1 and 10. If random integer is less than or equal to 7 then do nothing, else add 1 to a running sum. Iterate this function n times for the size of the input parameter n. The result is the number of objects destroyed which can be used to derive the number survived. This O(n) operational complexity and O(1) memory ...


1

If you insist on using millis() to index the array, then you either have to make the array size a factor of the max millis() value, or you have to reset the millis() value to zero when your array wraps. But these seem like bad ideas and I don't understand why you are using millis() to index the array. Think of the array as a circular (ring) buffer. Create ...


0

This is quick idea how I would do it: Divide red line into points at appropriate interval For each point, find closes point on white line. Shift each point towards found point slightly. Maybe apply "bleed" that also shifts neighborhood points in same direction, but at reduced amplitude. Repeat steps 2-3 until lines are close enough. Maybe create an error ...


1

Assuming Brute Force is not an acceptable approach, your problem is NP Hard, meaning that you cannot effectively solve this for worst case operational complexity. This solution can be optimized though. This is basically an Optimization Problem. You are required to find the best solution for a discrete set of variables. Granted the number of possible ...


2

Standard sorting is very much possible, and it is exactly what you should be doing here. the problem differs in that the ordering is unknown There is no difference. A standard sorting algorithm does not know the "rank" or "strength" of any of the items it is sorting ahead of time. In fact, it never knows it. All it knows is that there is a way of asking "...


2

So you are looking for ranking items by minimizing pairwise comparison. It is exactly what standard sorting algorithm optimally does in O(n*ln(n)) comparison. (The proof of optimality is on text books such as Introduction of algorithms) Concerning the problem of just having the first k elements sorted, it is called partial sorting and can be optimally ...


0

You need an expression evaluator, as an abstract syntax tree interpreter. What an interpreter does is: start with some known state, e.g. variables, (blank) outputs, etc.. Then it execute statements to update that state. To execute expression statements, you might use a recursive expression evaluator, which would do something like this: for a constant ...


2

This is effectively partitioning a multiset of prime factors. The simple algorithm to partition an integer is via a recursive function which takes as parameters the value remaining to partition, the maximum part, and suitable accumulator(s). E.g. if the handling of the final partition is done with a visit function then _partitionInteger(int n, int maxPart, ...


0

I will ignore factor 1 because you could add it as many times as you want. To solve the problem you need a procedure that produces the list of factorizations of N with the additions requirement that all factor are below or equal some max M. To produce the factorizations of N Build the sorted list of divisors. Get the largest divisor D. produce the list ...


0

In very general terms: write out all prime factors of the number of interest in a long array or list (i. e. instead of [(2, 3) (5,2)], use [2, 2, 2, 5, 5]) map a function over this that returns all possible permutations of this list. (to increase performance, filter out duplicates in the resulting list-of-lists) Map over each of these permuted lists a ...


1

Just to provide a very short answer. This works for most kinds of recursive functions. You don't need to go through the recursion is your head. You just need to write the function for the given parameter, say a list of elements, while assuming that the function already works if you call it with any smaller list of elements. Similarly in your mergeSort ...


2

I was hoping that someone could provide me with insight as to how I should think about these two recursion calls, and how its obvious it had to be this way. There are basically two things that you need to master: You need to be able to recognize that a problem is potentially amenable to a recursive solution. You need to be able to formulate the recursive ...


4

Psychologically, recursion in programming is similar to "proof by induction" in mathematics. (In case you're not familiar with proof by induction, it consists in proving "If P is true for n=m then it is true for n=m+1", observing that P is true for n=0 [or n=1, if you prefer], and deducing that P is true for all n). With mathematical induction, different ...


4

The recursive MergeSort is a "divide and conquer" algorithm. The code you provided in your example basically does this (in plain English): Find the middle point Sort the left half, Sort the right half. Merge the two halves back together. The key to understanding how this works recursively is that, when it goes to sort the left half, it divides that into ...


4

Recursion's general principle is to solve a problem by assuming a smaller problem can be solved, and accounting for the difference between the smaller problem and the one currently being asked to solve. Many recursive algorithms, e.g. recursive factorial, assume a smaller-by-1 problem and then given that answer, solve the delta between that (smaller by one)...


2

Here is a suggestion. I assume you want the maximum disk-area overlap, but this idea also works if you just want to maximize the number of circles partially covered. Let r be the radius of the covering disk whose center you seek. Grow the radii of all the other disks by r. Call the resulting set of enlarged circles/disks C. Now compute the overlap depth of ...


-3

Okay Avg is given by Avg= Total/Num. of Occurrence; Now from your question what will be Total Total = 1*10 + 2*27 + 3*15 + 4*34 +5*56 => 525; Now Num of Occurrence = 10+27+15+34+56 => 142; so Avg = 525/142 = 3.6971 I hope this solves your problem.


7

The problem is inviting you to overthink it. You can solve it by making sure you don't give each rule more power over you than it deserves. This is a requirements gathering problem. Always boil a requirement down to the real needs. Don't let it create added assumptions about what it needs. What you're missing is that the RL part of the problem (elbow ...


0

It's a much simpler problem because one group will take one table. Take the smallest table, seat the most valuable group that fits. Take the second table and again seat the most valuable group that fits. And so on.


0

To tackle this problem I would follow a different approach: A table can only be used once and only people from the same group can sit at it. What you want to do is sort all your groups of guests by decreasing amount that they will spend in the restaurant, and then allocate them to the smallest table that can accommodate them, or move to the next group if no ...


0

You are probably best served by using existing implementations of compression and decompression. Your existing implementation seems similar to the HuffYUV codec, so it might be worth trying that to see if it works well enough for you.


4

You've got temporal prediction, but no spatial. For better compression at the cost of speed, you should be able to use the pixels above and to the left of the current pixel in the current frame as predictors, as well as the pixel at the same location in the previous frame. The reason for only looking up and left is the same as the reason for only looking at ...


2

Now you've fixed the post, it is rarely a good idea trying to understand an algorithm from the implementation. It is much easier to develop the algorithm and the code. Let's start with a simple thing: Given a start position in an array, how many array elements can we add from the starting position so that the sum is not greater than t? That is, given an ...


2

There are (almost) no "generally reserved greek symbols" in mathematical or algorithmic texts. The only exceptions I can think of are the letter π=3.1415926...., the letter ε for "a small real value" the letter Σ for summations the letter Π for produkts Even those can have a different meaning depending on the context, but when ...


1

One way to prove the code works is to use a loop invariant to reason about the program in a similar way to David Gries in his book, "The Science of Programming." I'm a bit rusty, so any suggestions for improvements would be welcome. For brevity I've renamed the array from 'minutes' to 'a' and removed extraneous brackets. To aid with explanation, define a ...


2

From the documentation page you linked: Parameters since_id Returns results with an ID greater than (that is, more recent than) the specified ID. There are limits to the number of Tweets which can be accessed through the API. If the limit of Tweets has occured since the since_id, the since_id will be forced to the oldest ID available. Store ...


1

Implementation isn't complicated using recursion. Below is an example of how to solve the satisfiability problem in C#. This is just trying to satisfy each customer with one stone. There might be leftover available stones that a buyer might want which can be added to the bought lists to make the buyers more than satisfied. enum Stone { DiamondRound, ...


3

I'd say it's a 1D array, given that a stone and its variant make a single item. Is it a wrong assumption? Your algorithm should be correct, however it is truly a brute-force solution. My simple suggestion: sort these items by the amount of people, who have them in their "favourites". Assign the items to people in this order, expanding a tree bounded by ...


1

Backtracking is a good approach. If your implementation gets to complicated you should read some example implementations of backtracking. Remark: Backtracking is not 'trying every possible combination' because you do not try any combination, where already after a few assignments there could no longer be a valid over all assignment. See Early stopping ...


1

Keep segments in sorted order (list, binary tree, whatever...) When adding a new segment, search list, binary tree, whatever to see if it either end of the new segment overlaps an existing segment. If it does, remove/split into new set of segments according to your combining rule (in your example, averaging the overlapping parts). I don't think there is a ...


2

Why not read Frye's article? Here is a digest. You do need modular arithmetic to sieve candidates. Mod 5 works like charm (200 times reduction of the search space). You need to split it in A^4+B^4 and D^4-C^4. The program itself is written in Lisp. The implementation is reasonably straightforward, while the underlying math is neat. First He sieves out ...


0

You are looking to solve a problem that originates from a mismatch between the type of information you want to work with (ordered sequence) and the data you have (unordered set). A good strategy to fix this is to make sure that information and data match, because then the program will be straightforward. So I'd recommend the following approach: Build an ...


0

The easiest way is brute force. Generate all the ways to order the numbers and apply the operators, then see if any matches the target value. This will scale very badly, but can be improved with heuristics. Using your example, we can notice that we only need to try division when it will come out to an integer (assuming you don't mean / as truncating integer ...


3

Modular arithmetic is the key. First of all, take the total and add all its bytes together. If any carries occur, add those into the total as well (for instance, F0+F6=E7). Continue until you have a single-byte value. The process works just as well if you start by adding 32-bit words to 32-bit words until you have a 32-bit result and then the 16-bit "top ...


4

Create one data structure that creates all sums of two fourth powers in ascending order, and another one that creates all positive differences of two fourth powers in ascending order. Then compare the numbers from both lists in ascending order. That way you have only O (n^2) numbers to check instead of O (n^3). Basically, search for a^4 + b^4 = c^4 - d^4. ...



Top 50 recent answers are included