We'll go over solutions to these on Tuesday. Meanwhile, you are strongly encouraged to try to work them out for yourselves. Please post your ideas or difficulties you run into, in the comments.
I was looking at 6.6, and have a question pertaining to the term "even" which Pat just arrived at a few minutes ago as well.
The input: line # of chars 1 16 2 16 3 31 4 39 5 49 6 38 7 38 (including the \n char in all lines)
The output: line # of chars 1 38 2 39 3 37 4 38 5 36 6 38 (same as above)
The input has total chars 227 and output has 226 due to the input has 7 total lines and output has 6 total lines.
It seems that the output uses L = 39 chars including \n but how does it arrive to this value?
We both were thinking perhaps take the average of the input which would be 227/7 = 33 but that is too low so if excluded the first two really short lines of 16 then 195/5 = 39!?!
Therefore, the main problem/concern is to take the input of a script, and calculate the L to make it "even" to output the pretty print script, I think.
Thus, if the calculation of the L is the main key to making it even, would doing an average of the input lines like above be a good idea?
L is part of the input. In this case, L might have been anything from 39 to 45 or so, although the question didn't say so. With a bigger L like 50, we could get a better solution by fitting the quotation on 5 lines instead of 6.
That is what Pat had thought too, but I must make everything more difficult than it is ;)
Now that it is simplfied with the L, then I am thinking there would be roughly (total number of chars = C) / L subproblems i.e. number of lines, and the first recursive call would have C - L chars (or a little more or less depending if the word goes past L) to compute and keeping a cnt : when cnt > L need to stop and move back to the previous space and so on, then pass (C - cnt) chars to the next call???
I would suggest that you all try to approach these problems by thinking about: (1) what should the subproblems be? and (2) how can I reduce from one subproblem to some number of smaller ones?
These questions can't usually be answered separately---they feed into each other.
If you have an idea for (1), but are stuck on (2), keep in mind that sometimes the key is to add an additional variable into your answer to (1).
@Krista, figuring out the number of subproblems should come AFTER you've answered questions (1) and (2). Also, you seem to be suggesting a greedy algorithm. But you shouldn't necessarily try to fill up the first line. For instance if L=10 and the input is: 1 2 3 4 5 6 (11 chars in all, including the spaces) the output should be 1 2 3 4 5 6
I was looking at 6.6, and have a question pertaining to the term "even" which Pat just arrived at a few minutes ago as well.
ReplyDeleteThe input:
line # of chars
1 16
2 16
3 31
4 39
5 49
6 38
7 38
(including the \n char in all lines)
The output:
line # of chars
1 38
2 39
3 37
4 38
5 36
6 38
(same as above)
The input has total chars 227 and output has 226 due to the input has 7 total lines and output has 6 total lines.
It seems that the output uses L = 39 chars including \n but how does it arrive to this value?
We both were thinking perhaps take the average of the input which would be 227/7 = 33 but that is too low so if excluded the first two really
short lines of 16 then 195/5 = 39!?!
Therefore, the main problem/concern is to take the input of a script, and calculate the L to make it "even" to output the pretty print script, I think.
Thus, if the calculation of the L is the main key to making it even, would doing an
average of the input lines like above be a good idea?
Also, noticed something weird I posted this question at 2:24 pm and it says 1:24 pm...did I forget the time change :O !!!
DeleteL is part of the input. In this case, L might have been anything from 39 to 45 or so, although the question didn't say so. With a bigger L like 50, we could get a better solution by fitting the quotation on 5 lines instead of 6.
DeleteThat is what Pat had thought too, but I must make everything more difficult than it is ;)
DeleteNow that it is simplfied with the L, then I am thinking there would be roughly (total number of chars = C) / L subproblems i.e. number of lines, and the first recursive call would have C - L chars (or a little more or less depending if the word goes past L) to compute and keeping a cnt : when cnt > L need to stop and move back to the previous space and so on, then pass (C - cnt) chars to the next call???
I would suggest that you all try to approach these problems by thinking about:
Delete(1) what should the subproblems be? and
(2) how can I reduce from one subproblem to some number of smaller ones?
These questions can't usually be answered separately---they feed into each other.
If you have an idea for (1), but are stuck on (2), keep in mind that sometimes the
key is to add an additional variable into your answer to (1).
@Krista, figuring out the number of subproblems should come AFTER you've answered questions (1) and (2). Also, you seem to be suggesting a greedy algorithm. But you shouldn't necessarily try to fill up the first line. For instance if L=10 and the input is:
1 2 3 4 5 6 (11 chars in all, including the spaces)
the output should be
1 2 3
4 5 6
Is 6.6 the least square problem?
Delete