|
Recently, a question on QA here about implementing a Rock-Scissors-Paper (RSP) game [^], to which I responded, left me with a curiosity to see how efficiently/tersely I could implement the possible analysis of the result of game play.
Which got me interested in the more general question of how, given a complex matrix of values and criteria which can be expressed in typical De Morgan table form can be ... possibly ... analyzed by code in such a way that either an optimal implementation of the matrix (code-generation) is generated, or, some set of heuristics is generated that the programmer can interpret and use to write optimized code.
To use the RSP possible outcomes as a simple example, and excluding the obvious condition that if two "players" select the same "object," the game is a tie:
assume 0 => Rock , 1 => Scissors, 2 => Paper
0 1 true ... rock breaks scissors => player1 wins
1 2 true
2 0 true
0 2 false ... paper covers rock => player1 loses
1 0 false
2 1 false
Of course, it's straightforward to write a simple switch statement, or if/else/ chain to "solve" this.
"Eyeballing" such a table, and looking for "patterns" in the outcomes, the mind may naturally think about various boolean operations like XOR, or using modulo some number, looking for "heuristics;" look for "threshold" values that can "prune" the possible comparison matrix.
Looking further than this simple example, one can think about the complexity of an airfare reservations system where there might be twenty different factors resulting in the selection of the final airfare price from some list of pricing levels.
And, of course, the programmer will (hopefully) have (or create somehow) some clear description of the "business rules" that describe the calculation process.
Let's say the outcome in the airfare scenario is a matrix of 1000 combinations (to be conservative). To our brains it's pretty easy to look at the criteria and use the business rules to select the criterion (like passenger Age) that may have the most "impact" on the matrix of combinations: i.e., you'd want to first "prune" the matrix by a switch statement using Age as the selector.
And, it would be logical, as you eyeball the criteria to consider those with the fewest number of "states" and use testing those in the "outer" switch statements to reduce computation.
However, an interesting complication may be that some criterion with only one, or a few states may be, in practice, rarely of predictive value: that, imho, takes you into the analysis of the criterion based on context (world-knowledge, statistics of use, etc.). I want to exclude that from this post.
Then there are the interactions of variables; in the airfare scenario a discount for early booking may not apply to the fare calculation for accompanied children between age 5~11, for example. While some variables may be inherently "binary," such as, perhaps, the need for a wheelchair, many variables may have a number of "levels," like, for example, age broken out by infant, child, teen, adult, senior.
I'm sure that Decision Table theory which has been around for so long has generated some algorithms/heuristics for analyzing complex boolean matrices and optimizing code.
Appreciate your thoughts !
«I want to stay as close to the edge as I can without going over. Out on the edge you see all kinds of things you can't see from the center» Kurt Vonnegut.
modified 1-Nov-15 2:33am.
|
|
|
|
|
Problems of this sort I usually approach by first doing some data / frequency analysis.
Then start "slicing" (usually) from the variable that has the least unique values for a given context.
e.g. If I wanted to select all males in California, would I first slice on "gender" or on "State" (of residence)? The point is, it's hard to generalize on strategies and it all "depends". (This also applies to complex SQL queries which the "optimizer" isn't getting quite right since the optimizer depends on an a particular "execution plan").
|
|
|
|
|
I don't use a standard way to deal with this problem.
My solution is always context dependent and language dependent. No heuristics will do it for me.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
I know the brute force method. can someone help me find a good solution!!
Input Format
The first line contains an integer, T, which is the number of test cases. T test cases follow, each having a structure as described below:
The first line contains two space-separated integers, R and C, indicating the number of rows and columns in the grid G, respectively.
This is followed by R lines, each with a string of C digits, which represent the grid G.
The following line contains two tab-separated integers, r and c, indicating the number of rows and columns in the pattern grid P.
This is followed by r lines, each with a string of c digits, which represent the pattern P.
Constraints
1≤T≤5
1≤R,r,C,c≤1000
1≤r≤R
1≤c≤C
example
INPUT
2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99
output
Yes
No
pls help!!
|
|
|
|
|
Member 12083453 wrote: I know the brute force method. can someone help me find a good solution!!
Solution to what problem ?
You describe the data used, but not the problem you try to solve.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
This is quite straightforward. Read the control numbers and extract the remaining data sets based on those numbers.
|
|
|
|
|
Your description of the data's internal structure does not match the data shown.
"The first line contains an integer, T, which is the number of test cases."
The data shows #2, but it appears you have four test cases.
You need to carefully re-edit the question so your description is clear and the data "matches."
What makes you think that this there is an algorithm possible here which is anything beyond a series of steps to read the data and process it into some kind of objects-in-code ?
Try posting this question on QA, but only post it when you have code to show, and specific questions.
«I want to stay as close to the edge as I can without going over. Out on the edge you see all kinds of things you can't see from the center» Kurt Vonnegut.
|
|
|
|
|
A very stupid question. I have a problem where the scenario is similar to playing a game with the character may buy/ sell magic items one at a time in the inventory store; and the magic item may generate e.g. MP according to the purchased item. Each item can be sold after buying that item (the player can't sell the item that he/she didn't purchase). Also each day the inventory store may sell an item (so player can only decide buy it or not). The last constraint is a fixed time (e.g. 10 days) the player/ character can keep the item purchased.
I search on the internet, it seems this can be solved by dynamic programming or greedy algorithm. But I can't figure out the solution because many examples on the internet e.g. activities selection are different from this one. For instance I understand the following one, but can't map that to the question I have.
http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/
A sample data for this question:
- the inventory store will sell items for 8 days.
- initially the player/ character keeps 10 coins.
- the player/ character can keep the item for 20 days.
For each day the item to be sold
day 1: the item costs 9 coins with 2 MP generated per day; the inventory store will buy it back with 1 coin.
day 2: the item costs 10 coins with 1 MP generated per day; the inventory store will buy it back with 9 coins.
day 3: the item costs 2 coins with 2 MP generated per day; the inventory store will buy it back with 1 coin.
day 4: the item costs 11 coins with 4 MP generated per day; the inventory store will buy it back with 7 coins.
day 5: no item available.
day 6: the item costs 12 coins with 3 MP generated per day; the inventory store will buy it back with 1 coin.
day 7: no item available.
day 8: the item costs 20 coins with 4 MP generated per day; the inventory will buy it back with 5 coin.
Can anyone suggest some hints (e.g. how to divide the problem into sub ones) or point me to the doc that may have better explanation regarding to this question?
Many thanks
|
|
|
|
|
As a gamer, I'd ask myself what the optimal buying/selling moment is, and would try a naive approach in finding it. That means, look at what day today is, and see if selling today has an advantage over tomorrow, if tomorrow is a valid selling day. That prolly means coming up with a way to get a "score" for each day and calculating it. Can you express a MP in coins-value? If yes, then you could calculate the items "coins value for a given day".
It does sound a bit strange that I can keep the item longer than the store is opened, or that the store only sells a single item per day.
Bastard Programmer from Hell 
If you can't read my code, try converting it here[^]
|
|
|
|
|
A tree that has N nodes is given. Nodes have weights between -1000 and 1000. That is asked from me is to find maximum of multiplication of subtree nodes. Do you have any idea/algorithm to solve this problem?
Example tree and solution are given here: http://i.stack.imgur.com/5k83f.jpg[^]
|
|
|
|
|
Calculate all the products in post-order, keep track of the max.
|
|
|
|
|
Can you explain an example ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
I am trying to find all subtrees of n-ary tree. Only BFS or DFS does not work. Because the tree is not binary. For example:
1
/ \
2 3
/ \ /|\
4 6 5 7 8
/ \
9 10
I want to show all subtrees including this one
1
/ \
2 3
\ |
6 7
How can I extract this subtree from original one?
|
|
|
|
|
That's not a normal definition of "subtree". See: Tree (data structure) Terminology[^]
In any case, you can make your own traversal algorithm, that at each node, returns the set of that node with all of the combinations of the descendents.
So at your node 3, it would return:
(3)
(3 (5))
(3 (5 (9)))
(3 (5 (10)))
(3 (7))
(3 (8))
The three forms including node 5 are from the same process applied recursively to that node.
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
So I have a data set comprising of 20000 data points. Each data point consists of 200 features representative of a discrete sampling over a series of features describing the data point which can represent one of 16 cases or an unknown case. The data is classified using a Neural Network. The first problem i'm having is I am wondering if there is an algorithm or method of deciding which of the 200 features is most important so I can reduce the amount of data I am working with. My second problem is that half the data collected refer to an unknown case so it is classified as 0, while for the other cases there may be 20 data sets referring to case 1 and 2500 referring to case 9. Is there an algorithm to deal with this skew in the data because training the network is essentially setting all the weights to point to the 0 case because the 0 case can be any value that isn't explicitly one of the other cases.
|
|
|
|
|
Not really an answer but: If you really want to learn about Machine Learning and Classification systems, check out the Free, introductory Machine Learning online course from Caltech![^]
It won't give you the code, but you'll learn lots about how to do it yourself!
If you try taking the course, I suggest using Octave (a free Matlab-compatible system)[^] for practicing and homework.
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
Sweet, I'll definately check it out I had taken a previous one on coursera but that's about the extent of my knowledge.
|
|
|
|
|
By using 9 numbers which are 1 to 9 you should find the number of ways to get N using multiplication and addition.
For example, if 100 is given, you would answer 7.
The reason is that there are 7 possible ways.
100 = 12+3×4+5+6+7×8+9
100 = 1+2×3+4+5+67+8+9
100 = 1×2+34+5+6×7+8+9
100 = 12+34+5×6+7+8+9
100 = 1×2×3+4+5+6+7+8×9
100 = 1+2+3+4+5+6+7+8×9
100 = 1×2×3×4+5+6+7×8+9
If this question is given to you, how would you start?
|
|
|
|
|
I would start to doubt the assignment, or the teacher. This is more like a Code Fight challenge, or a Hackathon activity. Not a programming assignment.
There is no way, a beginner (if asked at even a Bachelors level) would be able to create a program, that takes an input (100) and creates a list. Would be much complex, and would take a lot of time.
The sh*t I complain about
It's like there ain't a cloud in the sky and it's raining out - Eminem
~! Firewall !~
|
|
|
|
|
To start with, I would think about a brute force approach, and narrow it down by adding more rules.
Make your algorithm start with 123456789
In the next iteration, make your algorithm obtain: 12345678*9
Next obtain, 12345678+9
and 1234567*89, 1234567+89, 1234567*8*9, 1234567*8+9,... and so on
If you write an algorithm to fill this series, you can easily see that there are 3^8 possibilities! It might look long enough but it actually is not! I took "three" because there are three possible states: 1. No operation, 2. addition, 3. multiplication. And there are 8 ways you can insert the arithmetic symbols, which is always in-between two numbers.
Now, though the value 3^8 = 6561 is very less, computing huge values won't do any good. What other information do we have? There can't be a '-' sign! That's a good clue. Because, now we know for sure that the value can't reduce and computing values such as 12345*6789 can't be always feasible. So, if there is a number in the expression greater than the required number, from your example, if there is a number greater than 100 in the expression, you don't have to compute the expression to know it is not equal. Simply checking for the "greater than" would help.
Now, we have made the problem shorter, starting with an inefficient brute force algorithm! Now lets make it even shorter. Did you observe that if the entered number is 100, the first few elements in the series would definitely not hold? Let's create a function,
term f(int x) // returns the term, given the term number.
to which if you pass on the term-number you could automatically obtain the element in O(1) time. I call it O(1) because the moment you convert the base-10 number passed on as an integer to the function f to a base-3 number, you have your term! Now each digit of the newly obtained number either becomes + or * or "nothing", and with this we may construct our term. Let's now define rules to skip every term containing numbers greater than 100. To do this, lets speculate and find the term that is at the 1000'th place in the series. Depending on whether the series is greater or lesser, move forwards or backwards in the series (if you are willing to find at-least one solution, or switch to brute force if you want to find all the possible answers).
This is how I would start with the problem. And I would write a quick code and test my hypothesis, and add on more rules to it and make it even more optimized.
|
|
|
|
|
I see that numbers are in order is it allowed to change order ?
Like using 100 = 1×2+38+4+5+6×7+9
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
modified 8-Oct-15 18:01pm.
|
|
|
|
|
ppolymorphe wrote: is it allowed to change order
I'd guess not, or else the original solution would have had more than 7 possibilities. If they can, then the possible solution space is over 300000 times bigger!
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
I do not know why order can not be changed. If we change order, mostly we get different result, because multiplication precedes summation. Of course, here are some options as X*1+2+3 or X*3+2+1 and so on. But if we mix multiplication and summation, then results are different. If we will follow standard rules then mentioned X examples are the same option/solution.
EDIT
I mean X*1+2+3 or X*1+3+2 not mixing multiplication with summation 
modified 16-Oct-15 11:32am.
|
|
|
|
|
The issue comes with the adjacency "operator" where adjacent digits of the input sequence can be interpreted as a multi-digit number. In the original example there was:
100 = 12+34+5×6+7+8+9
where the 1 and 2 were combined into 12 and the 3 and 4 were combined into 34.
If the order could be rearranged, then there are more possible multi-digit numbers:
51, 72, 43, etc.
This increases the complexity of the problem space and the number of possible solutions.
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
I have been reading this:https://en.wikipedia.org/wiki/Dijkstra's_algorithm[^]. It says,
Dijkstra's original algorithm does not use a min-priority queue and runs in time O(|V|^2) (where |V| is the number of nodes). The idea of this algorithm is also given in (Leyzorek et al. 1957). The implementation based on a min-priority queue implemented by a Fibonacci heap and running in O(|E|+|V|\log|V|) (where |E| is the number of edges) is due to (Fredman & Tarjan 1984). This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.
But whether or not we use a min-priority queue, shouldn't it be O(|V|^2)?
Lets consider the situation where every node in the graph is connected to every other node. And each of this node is double ended (i.e., if there is a link from A to B then there is also a link from B to A). If we were to make the algorithm update the distance of every node (from the source) then shouldn't we obviously be checking |V| nodes for each node in the graph? We need to compulsorily check each node for every other node we visit!
Now following this algorithm from Wikipedia:
1 function Dijkstra(Graph, source):
2 dist[source] ← 0 // Initialization
3
4 create vertex set Q
5
6 for each vertex v in Graph:
7 if v ≠ source
8 dist[v] ← INFINITY // Unknown distance from source to v
9 prev[v] ← UNDEFINED // Predecessor of v
10
11 Q.add_with_priority(v, dist[v])
12
13
14 while Q is not empty: // The main loop
15 u ← Q.extract_min() // Remove and return best vertex
16 for each neighbor v of u: // only v that is still in Q
17 alt = dist[u] + length(u, v)
18 if alt < dist[v]
19 dist[v] ← alt
20 prev[v] ← u
21 Q.decrease_priority(v, alt)
22
23 return dist[], prev[]
We can obviously see that the loop continues until all nodes in Q are visited. During each visit, every neighbor of v is checked. So this clearly checks every other node in the graph for each node that's visited (if we assume that every node is connected to every other node). So now we have,
O(|V|^2)
instead of,
O(|E|+|V|log|V|)
Where did I go wrong?
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
