Tag Info

New answers tagged

0

There are two things you need to do: (1) start with plausible heuristics (2) test the generated grid. Some plausible heuristics would include (for example): Match frequency of letters in English: ETAOIN SHRDLU etc etc. See here. Maintain vowel balance (about 40%). No more than 1 or 2 rare letters (ZJQX) and no Q without U. Other heuristics related to the ...


2

You want to enumerate recursively the set of sublists of 1 :: 2 :: 3 :: 4 :: [] which sums to 5. (The :: is the OCaml notation for the list construction.) The recursive step in list processing is splitting the list in its head 1 and its tail 2 :: 3 :: 4 :: [] — can we describe our set in these terms? There is two kinds of sublists of 1 :: 2 :: 3 :: 4 :: [] ...


4

Lets take an array of size n. There 2n possible subarrays of this array. Lets take the example array of size 4: [1, 2, 3, 4]. There are 24 sub arrays. Sub array of the empty set ([]) is the 0th one (0000). The subarray of [1], is the second one (0001), the subarray of [2] is the second one... (0010) and the subarray [1, 2] is the third one (0011). You ...


1

I'm assuming for the purpose of this exercise that you don't want any repeats. For example, the combinations for [1..4] are [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4], [1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4]] If not, the process is really the same for all recursive functions: figure out your bases cases, and figure out your larger problem ...


0

I think you are doing it backwards. Don't start with the schedule table, start with a table/array/whatever of all the game combinations (the 45 games). From there, it's a simple process to assign the games to a day, based on a team only playing once a day. And since matchups only happen once (Team A only plays Team B once) the scheduling is easy because you ...


0

Sometimes people use a head node with no data (a.k.a. a sentinel) rather than handling a NULL pointer for an empty list. This is discussed at Head node in linked lists on Stack Overflow and mentioned at sentinel node on Wikipedia. This can simplify code due to not needing special case handling for empty lists. The Wikipedia page also suggests it can improve ...


3

the algorithm itself is easy: create an array with all the weights' cumulative sum. After that you generate a [0-1) uniform random number and just binary search that number multiplied with the sum of the weights and the index will be the number you will need to generate.


1

I am looking for a way of saying: Increase the weight of o1 by 1. Increase the weight of o2 by 1. Increase the weight of o1 by 1. Now give me the results sorted by their weight. This seems like a job for a priority queue, where the priority_number is the weight you want to assign.


0

For sorting you can override __lt__ and others compare function: import heapq class Item(object): def __init__(self, o, weight): self.o = o self.weight = weight def increase_weight(self, amount=1): self.weight += amount def __lt__(self, other): return self.weight < other.weight def __str__(self): ...


3

I will try my hand at an answer, and fully expect to hear what's wrong with it soon. :) So first, I think the problem may be more easily tackled by thinking of the pair of ranges instead as defining a rectangle. Suppose you have [(0,2), (3,4)]. Another way to view this is the rectangle in Cartesian coordinates of (0,3) to (2,4). Overlap of both ranges can ...


2

You could of course store the weight in each object, or store a directory of instances in the class, if you create or control the classes. If not, you may be interested in the Counter class, a dictionary that maps into numeric values. It can be extended to map objects to weights. Here's a sketch: from collections import Counter class Weights(object): ...


2

Third time's the charm, I hope. I combined my original idea to sort the list first with Snowman's suggestion of using set theory. The basic algorithm is: Sort the pairs in lexicographic order by the first range. Group adjacent pairs by if just the first ranges overlap. I prove below that lexicographically sorted ranges will never overlap without being ...


1

Use a class class Thing(object): def __init__(self, o): self.o = o self.weight = weight You can make a list of Things, or a dict, or whatever works for you.


1

If you maintain a separate data structure along side your heap, this would likely solve your problem. This is the approach that the LinkedHashMap uses (a linked list along side the HashMap) to allow for an LRU cache and well known ordering of the entries in the LinkedHashMap (insertion order) (grepcode LinkedHashMap.Entry). This data structure would look ...


3

You can use a Double-End Priority Queue for this. There are a number of implementation methods available and the structure is routinely available in many libraries. Most Java libraries call it a MinMaxPriorityQueue though. It offers O(1) retrieval of Min and Max (Newest/Oldest) in O(1) time. In order to fulfill your space requirement, you'd need to use an ...


0

There is a way to do this if the mode will appear at least 50% of the time: def mode(numbers): mode, count = 0, 0 for number in numbers: if not count: mode, count = number, 1 elif number == mode: count += 1 else: count -= 1 return mode If the mode doesn't have this property, then I ...


2

The function can be written in a more mathematical form as: unknown(1) = 1 unknown(x) = unknown(x - 1) + x * x [if x is not 1] To see why this is the same as the sum of squares, you can substitute the second line into itself recursively and observe the pattern that emerges: unknown(x) = unknown(x - 1) + x * x ...


2

This is the sum of squares of natural numbers. The sum of first n natural numbers can be represented mathematically by: n*(n+1)*(2n+1)/6


4

Well it recursively calculates x2 + (x-1)2 + (x-2)2 + ⋯ + 22 + 1.


2

Yes, there are two better and faster approaches. Simpler problem : for each tile, choose the best thumb (with possible duplication). Ok, that's cheating, but can only lead to better visual result. Your take is algorithmically more interesting, and boils down to "linear assignment problem", assuming you take MSE as match costs whose sum must be minimal. ...


1

If the last tiles are your problem, you should try to place them early on, somehow ;) One approach would be to look at the tile that is the furthest away from the top x% of its matches (intuitively I'd go with 33%) and place that on its best match. That's the best match it can get anyway. Furthermore you could choose not to use the best match for the worst ...


1

Counting sorts fail when there are large key values (the k in the O(n)). This means that if you have a large variety of key values, counting sort will be slow. Radix sort can help solve that problem but it does nothing for other issue. Both counting and radix sort are only valid for integer keys. While not a terribly serious limitation, it does mean that ...


3

I'm reasonably sure that's an NP-hard problem. To find a 'perfect' solution you have to try every possibility exhaustively, and that is exponential. One approach would be to use the greedy fit and then try to improve it. That could be by taking a badly placed image (one of the last ones) and finding another place to put it, then taking that image and moving ...


1

Multiply each value with a weight, the timestamp will be small while the number of upvotes will be large.


1

Are you guaranteed to get to any rectangle from any other? (are there any gaps?) I'm presuming so, otherwise you can't determine what the relative coordinates are for the map. In that case, pick one arbitrarily and make that 0,0. Then it becomes a simple matter of walking the graph and assigning coordinates. If you require no negatives, then you'll need a ...


0

How often will a value be repeated? If the answer is "rarely", you may be better off storing the entire series, as the various Map / counter options probably use more memory. Only when there is a fair amount of repeats are they an advantage.


2

The mode is the most commonly occurring single value. Fairly obviously, you just have to count occurrences of each value as it arrives and then at the end search the counts to find the largest. There are some interesting variations. If and only if (a) the values are integers (b) you know the range in advance (c) you know the upper bound of the count then ...


5

To calculate the mode from an unreasonably large data set (or stream) containing only a finite number of discrete elements (such as integers in a small range), use a table to count the occurrence of each element, where the element in the data set is the key in our table. We then go through the data set and increment that element's counter. At any point we ...


0

This just comes to my mind as I was working with a different problem. When I came back I realized that Falk Huffner has already mentioned the tip. Anyway, no more fingering, one can show the reduction as follows to the decision version of the problem (whether there is an ordering of bands so that you have a value x) First use a modified version of ...


2

This is not solvable if the required number of appointments cannot be written as a sum of the available Package.Quantity numbers. But maybe that requirement is too strict. Why not say that you want to offer the client the cheapest available sum of packages? E.g. if he wants 8 appointments but you can't match 8, you give him e.g. 5+4 packages. Let your ...


2

For a genetic algorithm you need chromosomes and a fitness function. The chromosomes represent choices of route. Looks like 5 chromosomes, one for each city in order, but there could be a smarter way. The fitness function is calculated from the chosen route. Score higher for visiting more cities and for shorter distance and lower cost of the chosen route. ...


1

To get a Gaussian distribution, roll all numbers independently. Apply your predicate (e.g. Sum of numbers lies within [-1, 1]). If it fails, re-roll all numbers. When your predicate succeeds, you are done. This will, on average, terminate on some fixed iteration (if the predicate is ever satisfiable, and your RNG is not broken). Be sure to use an epsilon ...


2

The simple way to tell how "close" one solution is to another is to determine its standard error. Standard error is the standard deviation of answers you get. Then you divide the distance between two solutions by the standard error. If the answer is less than 1, that's pretty close, because you could get that big of a difference just by randomness. If less ...


1

They don't have to check them all I expect that when a transaction report is received by the brokerage, the brokerage checks for conditional buy-sell orders on the stock just traded that would be triggered by the new transaction. This would scale easily because stocks could be partitioned across servers. And "checking conditional buy-sell orders" doesn't ...


1

Figure out the complexity of the algorithm (its Big O) Measure the time it takes to perform one iteration (if it is constant), or measure several iterations and amortize the time it takes. That's it. To get the running time for a particular n, just take the amount of time for 1 iteration, and plug it into your big O. So, for example, if your Big O is ...


-3

If you follow SOLID, ACID, DRY you will find your way intuitively but needs specific experience. If a simple assumtation resolve to false, have the courage for radical changes.


8

A good guideline that helps knowing when to create a "large", general and abstract solution, and when to just solve the specific problem, is The Rule Of Three. The Rule Of Three is often applied to duplication: i.e. "if code is duplicated more then twice, move it to a function". However it also applies to the abstraction vs. solving-the-specific-problem ...


0

I'd start out by simplifying the problem. If you have N numbers from [A,B], they will add up to a value between N*A and N*B. Just subtract A from each number and N*A from the target X. So, without loss of generality we can look for N numbers between [0, B'] which add up to X'. Again, this can be simplified by dividing X' by B'. The resulting problem is ...


3

As said before, this question actually doesn't have an answer: The restrictions imposed on the numbers make the randomness questionable at best. However, you could come up with a procedure that returns a list of numbers like that: Let's say we have picked the first two numbers randomly as -0.8 and -0.7. Now the requirement is to come up with 3 'random' ...


3

If "spare time" is defined as the time in between the events, then your list format makes it very easy to convert you list of events to a list of spare times: Add midnight to both the start and end of your list Go over the new list and remove any interval of less than 0 seconds (or whatever threshold you want). With your example events, this would give ...


0

One option to solve this problem is to build a search tree. The goal state will be the sum of all nodes along your current path equal X. Each node is a different value between the range, so the number of nodes at each level will be abs(A) + abs (B). Explore all the paths and get all the possible solutions. Then choose one at random from the list of ...


0

You can start with any 5 random numbers in the range, but then you just need to pay attention to which are negative and which are positive. Case (A) : All 5 numbers are positive. Here you can just divide by their sum. The sum is guaranteed to be greater than each individual number, since each number N is positive. Then you have 0 < N < 1 for ...


2

The basic approach is: Identify all the factors. Assign a weight to each factor. If the factor itself has a scale, assign a scaling formula (eg linear, log, capped, whatever) based on additional weights. If there are dependencies, express those as a formula based on additional weights. Add up all the resulting values. The problem now is that you have a ...


2

Simple, as long as you know how many. You need N numbers called V1 to Vn. The required sum is S. Generate N random numbers (in any convenient range). They are R1 to Rn. Calculate their sum as SR. Scale each number so Vn = Rn * S / SR. You may produce a tiny rounding error, but I doubt this will be a problem. If the number N is supposed to be random, ...


1

After struggling for a day trying to shoehorn fake nodes and edges into my poorly designed code, I'm beginning to think that SJuan76's suggestion is really quite elegant. I can't prove that it works in all cases, but I've run through a few examples by hand and it seems to do okay. Start with plain old Dijkstra's Algorithm. Make the following minor changes: ...


1

I should think a data mining approach would work, probably with a neural network to map inputs (user actions) to outputs (game win/ loose). Record many games and use these to train the neural net. At run time let this trained 'net decide what's important and produce a numeric measure, which you graph.


3

You should be able to adapt Dijkstra's algorithm. Just add two points A & B to your graph, which are connected to one of the subgraphs each. Then calculate the shortest path between the two points A & B. The shortest path between the two subgraphs should be the path that you get after removing A & B from the result.


1

I recommend a depth-first search like you already tried, but put some additional constraints on it. For example, a path that loops (revisits nodes) is clearly undesirable when looking for the shortest path: simply remove that loops, and you found a path shorter by N where N is the number of nodes in the loop. With any algorithm it makes sense to set up the ...


1

generally this is called path finding You seemed to have tried 2 depth first searches. I suggest using a breadth first search (keep all paths of length n and then use those to find all paths of length n+1). If this exceeds your memory then instead you can use a iterative deepening approach. This is a depth first that you break off at length n and if you ...


1

It seems to me that, as you retrieve the list of subitems, rather than pushing them on a stack you should process each subitem asynchronously by processing each on its own Task. Only when all Tasks have completed (Task.WhenAll) do you take their results, push them on the stack and return. Obviously you don't want a million Tasks so perhaps you only do this ...



Top 50 recent answers are included