"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
Piet Souris wrote:hi DJ,
excuses for the long wait! Shame on us...
Piet Souris wrote:
You now have the days (weights) in periods of half days, it might be a little more clear when you turn that into integers. Thus .5, .5, 1, 2, .5 with a "total capacity (Knapsack term)"of 2, making 1, 1, 2, 4, 1 with a capacity of 4. Then it is clear that for the red cell you take the max of the cell above, and the cell above, shifted one place to the left (since the weight is 1).
You wold then get the scheme:
j =
i element 0 1 2 3 4
0 - 0 0 0 0 0
1 7 0 7 7 7 7
2 6 0 7 13 13 13
3 9 0 7 13 16 22
4 9 0 7 13 16 22
5 8 0 8 15 21 24
So for the last line it holds:
8 = max(7, 0 + 8)
15 = max(13, 7 + 8)
21 = max(16, 13 + 8)
24 = max(22, 16 + 8)
and the right bottom element is the max alltogether.
Edit: I forgot to talk about the green cell. Well, the weight (nr of days) of the National Gallery is 1, but since your unit is a half day, tyou should look two columns to the left (that's why I advised to use integers for the weights). So the green cell is max(13 (cell above), 13 + 9) (the second 13 being the value of (globe, day 1).
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
Piet Souris wrote:hi DJ,
the pleasure is all mine, or whoever of this commumnity is helping you.
And to the cow suppliers: whoever you are, thanks!
But now for your latest question. What exactly is the problem? There are some variants, like longest common subsequence of two Strings, shortest subsequnce in String S that is not in String T, and the variants that use substrings instead of subsequences. I followed that Grokking book that you linked to in your opening post, and I came as far as the longest common subsequence. But they make the text unreadable, so I have to follow the diagrams (I like the book, on the look of it, though!). Should I have read further?
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
I hate signatures!
Piet Souris wrote:
The problem being that if the String is "agb", then the 'g' plays no role in the solution.
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
Campbell Ritchie wrote:Why are you forbidding letters to map back to themselves? That was a feature of the Enigma Machine which made it vulnerable to deciphering.
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
Hahahahahahahahahahahahaha!D.J. Quavern wrote:. . . I am not planning to attack Germany any time soon anyway.
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
Piet Souris wrote:hi DJ,
no that is not required. A subsequence is just a subset of the characters, with the same order as the original String. So, if our input string is "djquavern" then dqn" is a subsequence, "avr"is one, et cetera. Just some characters, albeit that the order of the characters are the same as where they appear in the input string. So, "qja" is not a subsequence. If you require for a subsequence that the letters must be contiguous, then we are talking about substrings. Thus "dqn" is a subsequence but it is not a substring.
And by requiring that a subsequence is also a subsequence of our alphabet, we make sure that that subsequence is neatlly ordered (i.e. "dqn" is out of the question since the n appears after the q).
Meanwhile, waiting for that point in your life...
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
Piet Souris wrote:Don't feel stupid, for this is a hard exercise, and I bet that not many were able to solve this.
I remember a Hackerrank exercise, where an array was given, with the question how many shifts were needed to get that array sorted. The arrays given were so large that brute force would take forever. Now, coming up with a clever idea was not difficult, but I needed a datastructure that I had never seen before. So, after days of very hard thinking, I came up with a beautiful structure that solved a 100.000 array in 2.5 seconds. So, with full pride I submitted my solution, only to find that five arrays gave a timeout error...
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
Piet Souris wrote:hi DJ,
please don't hold it against me, but there is something awkward I have to say. Here goes: your diagram has a tiny mistake!
First of all: when talking about row and col, these variables denote the length of the substrings we consider, and not, say, the characters at position string[row] or string[col]. If we talk about the element table[row][col], then we are talking about the longest common subsequence when considering the first 'row' characters of the first string, and the first 'col' characters of the second string. So, that is why that GeeksForGeeks routine started with:
since in that case we are considering a substring of length 0, and we know for sure that the lcs has no elements.'
In your code, you do consider row and col as the indices into the two strings.
The rest of the code is:
Now, let's make your scheme again. But, like the table I showed in the beginning of this topic, I start with a colum and a row of just zeroes, representing the situations where row = 0 or col = 0:
row char col
0 1 2 3 4
- a b a b
0 - 0 0 0 0 0
1 a 0 1 1 1 1
2 b 0 1 2 2 2
Why do we get a value of 1 at position (1, 3)? Well, since the letters match, we apply the rule "1 + value left above", so we get 1 + 0 = 1.
Can you spot the mistake in your table?
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
Piet Souris wrote:The zeroes that I added are not necessary, and I just read in the Grokking book that the author does not use them. It is just that I find these zeroes make the manual labour easier. If I am busy with the first row and I have to look to the left or up, or left and up, then there is a fysical row or column with zeroes, so that I do not need to think of these zeroes by hart. Well, it is a matter of personal taste. If you find them confusing, then just leave them out.
The GeeksForGeeks code has the extra line:
That takes care of the zeroes in row 0 and in col 0. The rest of the code is identical to the grokking code.
Piet Souris wrote:
What? How? How can he NOT use the zeros? How would you solve that without zeros?
Piet Souris wrote:
When I was doing a course in Python (about 5 years ago) I quite liked that wrapping of array indices. You never get an IndexOutOfBounds-exception, but on the other hand, that may also be a bit dangerous, if that is not the intention and you forget to put a test into the code.
A question: the first excercise was about that dragon with many heads and even more tails. Sohail and I were advocating a DP solution, while you choose for a more direct approach (if I understood correctly). Now, if you had to do that exercise again, what would you do now?
I honestly don't like it ! All my out of bounds error disappear but I have lots of unfathomable errors.
Well, for the hydra, I guess I need to make a table with several head and tail cutting opportunities and that my optimal result is zero?
Let me sleep on that!
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
If you leave out the zero-row and zero-column, then you have to think of that zero yourself,' çause it's not physically there. Now, that is absolutely not difficult, it takes some practising, but it keeps your table neat. Well, as I said: personal taste.DJ wrote:What? How? How can he NOT use the zeros? How would you solve that without zeros?
I hate signatures!
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
Piet Souris wrote:It has nothing to do with having these zeroes or not. Having them, like I do, just makes it a little more convenient for me. And it works for repeated sequences just as well. Here's an example of repeated sequences, without zeroes, and just keeping in mind these two rules:
1) if the characters match, then the value = 1 + value left above. If that value happens to be outside of the table, then take 0.
2) else take the maximum of the value left and the value above. Again, if either of these are outside the table, take 0 for such a value.
Let the strings be "abcd" and "abcdabcd". Then, without zeroes, we get this table
a b c d a b c d
a 1 1 1 1 1 1 1 1
b 1 2 2 2 2 2 2 2
c 1 2 3 3 3 3 3 3
d 1 2 3 4 4 4 4 4
Take the first row. We start with (a, a). These are equal, so we get the value = 1 + value left above. Now, that value is outside the table, so we take 0 and we get 1.
Stil on the first row, for the letters b, c, and d we get that we take the max of the values left and above. But since the values above are outside the table, we take 0, and so all the three values are 1. Next we get again (a, a). We apply the formula: 1 + value left above = 1 + outside the table = 1 + 0 = 1. Et cetera.
The fourth row: we start with (d, a), unequal, so we take the max of left and above, so 1. The same holds for (d,b) and (d, c): taking the max of the values left and above. Then we get (d,d). Equal, so we take 1 + value left above = 1 + 3 = 4. Et cetera. The last value is again (d, d) = 1 + 3 = 4. Done, without the zeroes and with repeats!
And don't worry: DP has nothing to do with BITs!
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
Piet Souris wrote:hi DJ,
then we have found our culprit!
Lets look at the first row of the table I gave in my previous post. We had this row:
a b c d a ...
a 1 1 1 1
When we come to the second (a, a), lcs[0][4], we see equality, so we apply the formula: 1 + value left above. The value "left above" is at position [-1][3].
What I do is that I notice that the indices are invalid, so I take as value: 0, and as a result my second (a, a) becomes 1 + 0 = 0.
But you get a 2 instead. That is because you are minimizing your indices to 0. Sp your reasoning is:
(a, a) = 1 + lcs[-1][3]
= 1 + lcs[0][3] (0 = max(0, -1))
= 1 + 1
= 2
Here is a way to do the Heads and Tails with DP. For this, we put the number of heads horizontally and the number of tails vertically. And we translate the rules into some formulas (like we have done sofar in DP). If (h, t) denotes the number of moves to target when we have h heads and t tails, we get these formulas:
(h + 2, t) = 1 + (h, t)
(h - 1, t + 2) = 1 + (h, t)
(h, t - 1) = 1 + (h, t)
provided the indices left are within the table (i.e. >= 0)
We start with (0, 0) = 0. From this we get that (2, 0), (-1, 2) and (0, -1) have a value of 1, but the last two are invalid. Having set a 1 in (2, 0), we put a circle around the 0 of (0,0) so that we can see that we have processed (0, 0).
Next, from (2, 0) we get (4, 0) = 2 and (1, 2) = 2. We encircle (2, 0) and go on processing (4, 0) and (2, 0). Et cetera!
We get this table:
h 0 1 2 3 4 5 6 ...
t
0 0 1 2 3 ...
1 3 4
2 2 3 4
3 4
4 3 4 5
5
...
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
I hate signatures!