Over in
CodingProblem RonJeffries asked for a routine to solve the following problem:
-
- You have an ordered collection, size N, of objects. Given K, answer an ordered collection of K ordered collections of size approximately N/K, such that the first contains the first N/K objects, the second the second N/K, etc.
He gave an example:
input = #(1 2 3 4 5 6 7 8 9 10)
k = 3
output = (for example) #(
#(1 2 3)
#(4 5 6)
#(7 8 9 10)
I don't understand where the subtlety is, and I'm starting to suspect that there must be some hidden assumptions somewhere.
Just in case I was missing something about the problem as I understood it, I wrote the following Python solution:
def ReturnSplit(input,K):
result = []
N = len(input)
while input:
s = N/K
result.append(input[:s])
input = input[s:]
N -= s
K -= 1
return result
N = 10
print ReturnSplit( range(N), 3 )
This seems to work exactly as I expected, and produces the results requested. It works whether the division rounds up or down. It's easy enough to turn into an iterator-style solution, and it's easy enough to index into
input and not reduce it in size.
The reasoning as to why it works is easy. Select the best fit, adjust your concept of what remains, and repeat. It's an iterative version of a recursive solution that's "obviously" right.
It seems to be correct, and the central loop seems obvious, as Ron requires.
What am I missing?
-- anon2
Wow, I haven't thought about this problem since last century!
And of course obvious to regular folks and obvious to the likes of me might be very different things.
I think that if we were to discover that code, we would have to reason about it quite a bit to figure out what it did. The variable names, s, N, K aren't helping, but they're not the real issue for me. The real issue is that there's this s thing, meaning sequence or something, and I have to figure out, "Oh, I see, it's zero for a while, then one, then two ...", then I have to figure out how far it goes, what goes into each segment, and so on.
I think that if faced with that code, I wouldn't know what it did. (Of course a test might show me, but the question was about the code itself.)
Today, given what I'm thinking about, I might try to use slices to return the sequences. Perhaps a loop to compute the slice indexes, really obviously: [0...sliceLength], [sliceLength...2*sliceLength] ..., producing a list of the right number of slicers, and then loop over the slicers, with a collect: kind of operation, to produce the subsequences. That might make clear how many there were and what each one contained. Maybe I'll fiddle with it, but probably not, as I'm on another trajectory just now.
The idea is not just to produce code that obviously works when we reason about it, knowing what is supposed to happen. The original problem we had was that we thought if we read the code a year later, we'd not instantly see what it did. I feel that someone reading the above code cold would not immediately say "Oh, that produces K subsequences of the original sequence."
OK, so the question isn't to make the code clear, the question is to make the code clear even if you don't know what the problem is. That's a different question from the one I was answering.
Here it is again but with some renaming and a reordering to show the invariant more clearly:
def SplitInputIntoLumpsOfEqualSize(input,number_of_lumps):
lumps_of_equal_size = []
number_of_elements_remaining = len(input)
while input:
size_of_next_lump = number_of_elements_remaining/number_of_lumps
number_of_elements_remaining -= size_of_next_lump
number_of_lumps -= 1
lumps_of_equal_size.append(input[:size_of_next_lump])
input = input[size_of_next_lump:]
return lumps_of_equal_size
Is that now ScreaminglyObvious?
I read with interest your comment about returning slicelengths. That's also easy to compute, and it just depends on how you want to carve up the operation, if at all. I think we all agree it's not hard - that's not the point. The point it (as I see it now) to create code that is obvious to a casual reader in isolation. There is certainly more than one way to do it.
One thing that is not screamingly obvious (to Y.T.) about the above is the division by the decreasing number of lumps. Yes, the second fourth is 1/3 of the remaining 3/4, the third fourth is 1/2 of the remaining 2/4, and so on. But IMO it's not obvious that that works.
I'm supposing that the input[:size] and input[size:] thingies would be obvious to me if I used that language. Given the contents of my personal head, I might prefer the starting and ending indexes to be explicit.
It would be nice if we didn't have to recompute the lump size every time through the loop, and I'm wondering whether with suitable rounding and the right stuff happening at the end of the array if it's short, if that could work nicely.
I'm still leaning toward the slicing idea, but I haven't coded anything, so I could be more wrong than usual. --
RonJeffries
I wonder if this is a difference in background. I read the above code and see a tail-recursive version that's obviously right. Basically it says: take off one lump of the best size possible, adjust the remainder and repeat. This will work because if this lump is a bit small you leave more behind than expected, so you'll take more next time.
Here's a version using slices:
def multiply_constant_by_list_giving_ints(k,l):
return map( lambda x:int(k*x) , l )
#
def FairShareStartPoints(input,number_of_pieces):
indexes_of_pieces = range(number_of_pieces)
input_size = len(input)
average_size = float(input_size) / number_of_pieces
return multiply_constant_by_list_giving_ints(average_size,indexes_of_pieces)
#
def FairShareBoundaries(input,number_of_pieces):
return FairShareStartPoints(input,number_of_pieces) + [input_size]
#
input = range(11)
number_of_pieces = 3
boundaries = FairShareBoundaries(input,number_of_pieces)
print "Boundaries are:", boundaries
print "Slices are:", zip(boundaries[:-1],boundaries[1:])
This prints the boundaries of the slices, so for input of 11 elements and three slices required, it prints [0,3,7,11]. Thus your slices are [0,3), [3,7), [7,11). It also prints the slice start and end, including the start, not including the end.
I've been thinking about this for a while, and I think I'm back to not understanding what you're asking for. I think some code (although not necessarily this code) is subtle, and subtle code cannot be understood by reading without thinking. I wonder if an extreme version of what you're asking is simply that you want the code to be obvious from reading without thinking.
Is that really a reasonable thing to ask for? Perhaps it can be our goal, perhaps it should be our goal, but is it truly reasonable to expect it of all code?
This, of course, comes back to what code is for. The real code, the stuff that gets compiled/interpreted and executed must convey the "what" and the "how". Sometimes the "why" is there, and it should be whenever possible. Sometimes, however, the "why" isn't clear from the "what" and "how". There are not identical concepts, and trying to coerce them into a single vehicle might be misguided.
Maybe, just maybe, the "why" should be in addition to the "what" and "how".
-- anon2
I guess I'm objecting to "subtle" code. I'd prefer code that requires less thinking than any of these examples do. In my opinion, we're not likely to randomly find people on the street who will look at the examples we've seen so far and say "oh, right. an obvious example of tail recursion. gotcha."
I prefer code that is simple and clear, but not subtle. As I said when I posted this example, I have not as yet found such code for this problem. -- R
Perhaps I mis-spoke myself. I believe that some code is absolutely clear as to what it is doing, but the reasons
why it works are subtle. In some of these cases I believe you cannot express in code why it works.
Examples always run the risk of turning out not to be good ones, and you, Ron, have the happy knack of being able to convert bad code into good code. However, here is an example of what I mean.
Consider a simple algorithm for shuffling a vector. For simplicity, I will be specific, write in
CeeLanguage, and assume the vector contains integers.
void shuffle_method_one(int *vector, int number_of_elements) {
for (
index_to_change=0;
index_to_change<number_of_elements;
index_to_change++)
{
swap_elements_in_vector(
random_integer_from_half_open_interval(0,number_of_elements),
index_to_change,
vector);
}
}
void shuffle_method_two(int *vector, int number_of_elements) {
for (
index_to_change=0;
index_to_change<number_of_elements;
index_to_change++)
{
swap_elements_in_vector(
random_integer_from_half_open_interval(index_to_change,number_of_elements),
index_to_change,
vector);
}
}
I think the code in both cases is very clear as to what they are doing, and how they are doing it. In truth, I have no doubt that you could make it clearer, because you seem to have the happy knack of taking anyone's apparently clear code and making it even better still. I would be delighted if you would do that to these examples.
I stand to be corrected, but I suspect that your revised code will still not make it clear as to
why the second routine ensures that all possible permutations are
equally likely, whereas the first routine does not.
It's not clear to me that existing programming languages allow us to include as a part of the active code the proof/explanation that an algorithm does what it claims. Careful choices of code structure, variable/routine/method names and division of labour can make it clear that the code does what it's supposed to do. It seems to me that you're asking for more. You're asking for the explanation of
why the algorithm works to be visible.
I don't think that's possible. I'd be pleased to be proven wrong.
-- anon2
Well, I'd certainly /prefer/ that even a subtle property like the uniformity of a distribution would be clear in the code, but in the original example, I've not yet seen code that seems to me to have the result pop out as I'd like.
In the example in hand, I believe that what makes the second case uniform is that it doesn't reuse items. If that's the case, it could perhaps be made clearer by building a method that said something about "selection without replacement".
If I could improve the code above to make it clearer, as I tried to do with earlier examples, that would suggest that the code wasn't as clear as it could be. How clear /should/ it be? Why not make code so clear that no-one can make it more clear?
I can't see any way of reworking this most recent example using the "selection without replacement" idea, while still retaining the original algorithm. It's not actually selection without replacement that's making it work.
Regarding code being maximally clear, I believe that different people, with their different backgrounds and different ways of thinking, find different things clear. I suspect we could find an example with different codings, A and B, where I find A clearer and you find B clearer. Proving that there is no coding C that is clearer for us both is hard, but I don't see why it couldn't happen. I've made this code as clear as I can to explain what it is doing, and I can see no way to make it clear why the second one "works" and the first one doesn't.
static Object[][] split( Object[] input, int K) {
int N= input.length;
int size= N/K;
Object[][] result= new Object[K][];
for (int i=0;i<K-1;i++) {
result[i]=new Object[K];
System.arraycopy(input,i*size,result[i],0,size);
//for (int j=0;j<size;j++) { result[i][j]= input[i*size+j];}
}
int sizeOfLastBucket= size+ N%K;
result[K-1]= new Object[sizeOfLastBucket];
System.arraycopy(input,(K-1)*size , result[K-1], 0, sizeOfLastBucket);
//for (int j=0;j<sizeOfLastBucket;j++) {result[K-1][j]= input[(K-1)*size+j];}
return result;
}
Anybody who doesn't reverse engineer the specification from the code above should better find another job. What's this problem doing on a wiki?
CategoryHowManyWaysToSkinaCat?
If given 11 items and asked for three buckets, doesn't this code produce buckets with 3, 3 and 5 items? I can see what it does, but I can't see why the buckets it produces are as close to being of equal size as possible. In fact, I think this code is wrong, and for me to think it's wrong proves Ron Jeffries' point, even if it turns out to be right.
- That's because Ron's specification is perfectly sloppy, but given that the buckets have to be exactly K in number, and given that he said: "the first one N/K, the second one N/K, etc", I take it only the last bucket will contain a different number. Also, he gave an example that's supposed to be edifying, so that's it for me. The "approximately N/K" part is completely meaningless. In any case, even if we are to speculate that "approximately" really means "each bucket has N/K or N/K+1, the latter only in the case that K does not divide N" with the smaller ones being placed in front, it's still a problem so trivial that one might consider giving it to high school students. Any discussion about the art of programming related to such trivia is bound to be meaningless.
- Dismissing part of the spec (namely "collections of size approximately N/K") as "completely meaningless" seems a little harsh. Given that it is there, almost by definition it is not intended to be completely meaningless.
- It had a meaning for Ron that he failed to communicate; what was intended was lost. "Approximately N/K" in the context of this spec is meaningless.
- To me the obvious interpretation is that each bucket should contain either floor(N/K) or ceil(N/K). Interpreting the definition as you do is tantamount to ignoring part of the specification simply because it doesn't fit your preconceptions.
- If that was the intended meaning, that was what any programmer ought to write in a spec. By the way, there's no need for "floor" and "ceil" since the context makes it clear that it's about integer operations . So let's assume that the first X have exactly N/K and the rest (K - X) have exactly N/K + 1. Actually it's easier to consider Y= K - X (the number of buckets with N/K + 1. It follows quite trivially that Y= N%K. So replace the one loop and the extra special row, with two loops, one [0, X) and the other [X , K). Still trivia. No matter how you choose to interpret the spec, the "problem" is reduced to trivial integer arithmetics.
- Now that you have shown that the specification can be tightened, write a routine that is not only correct (K buckets, each getting either floor(N/K) or ceil(N/K) elements) and is completely obvious from reading it why this requirement is met. You're right that it's not hard to write code that produces the correct answer. It's also easy to write code that obviously implements the algorithm you use (whatever it may be). Ron's point, as I understand it, is that it's hard to write code that makes it clear that the algorithm produces the right result.
- I say again, the problem is not to write code that produces the correct answer. The problem is to write code that obviously meets the specification. I think I can now see the difference, so I have learned something from this problem.
- Finally, please BeConstructive. So far, you seem to have just written code, and claimed that the specification is flawed and the problem is not worthy of consideration. If you think it's not going to teach you anything, don't bother reading or editing this page. If you think you have something to teach us about this question, please, BeConstructive, don't just criticize.
- "Don't just criticize" is yet another fine piece of nonsense in this discussion. Criticizing is being constructive. And I can bother to edit this page to point out the nonsense in this discussion just like you can bother to edit to claim the contrary. GetOverIt. Here's the "obvious" code:
/**
* splits the input into K buckets of which the first
* X = K -(N%K) have exactly N/K elements
* and the last Y= N%K have exactly N/K+1 elements
* all elements are in the order in which they were in the input array
*/
static Object[][] split( Object[] input, int K) {
int N= input.length;
int size= N/K;
int Y= N%K;
int X = K - Y;
Object[][] result= new Object[K][];
for (int i=0;i<X;i++) {
result[i]=new Object[size];
System.arraycopy(input,i*size,result[i],0,size);
}
for (int i=0;i<Y;i++) {
result[X+i]= new Object[size+1];
System.arraycopy(input, X*size + i*(size+1), result[X+i], 0, size+1);
}
return result;
}
This is "obvious" only in the sense that it allocates arrays of the right size. It's not obvious from reading it that I get the right number of each size. To see that, I have to work through the code to compute what all the numbers are. It's not obvious just from reading it that it's doing the right thing.
To be specific, when I read this code I ask the following questions:
- What are these magic numbers X, Y, and i?
- What do they mean?
- X, Y and i. If you cannot operate with 3 symbols, 2 of them being explained to you, both in the comment and in the bloody definition -- int Y= N%K which is never reassigned means that Y stands for N%K and X stands for K - N%K, and even the dumbest reader needs to pay attention that X+Y= K and the first loop has X iterations over the first X elements of the results array and the second loop is over the remaining Y elements, while the third symbol, "i", is the most trivial loop variable; then you should find another job.
- Why don't their names tell me that?
boolean You_bloody_have_to_use_your_brains_and_possibly_some_pen_and_paper_to_check_out_trivia_arithmetics=true;
bring you any help?
- Why are some arays allocated to be size and others of size 'size+1?
- Because. If you bother to read and if you bother to think, you'll get it instantaneously. If you do not want to think at all, then don't bother reading code. Find another job.
I hope these questions go some way to explaining why this code might not be considered "obvious" when found in the middle of a 10 million line maintenance nightmare.
- You can read the header comment, and even that should not be necessary to understand the code. Do a little bit of arithmetic trivia and repond to all your questions. Anybody who doesn't find it obvious should be judged incompetent, and if you're chasing the "obviousness" in the sense "no mental effort whatsoever" required, then you're way on the wrong track.
- The challenge in this problem was always to make the code as clear as possible. My question to you is - can your code be made clearer? Your response seems to say, "I don't care - it's the reader's problem." Is that right?
- It's not the writer's problem that some dumb reader wants to read code the way Harlequin Romance series is read in the subway. There will always be a lower bound, a minimal amount of mental effort than any reader of actual code is expected to fulfill. Beyond that, and even reaching that lower boundary is detrimental to the code, it's detrimental to the economics of programming, it's just nonsense as it drags our profession into the mud, chasing wild geese for the mythical dumb maintenance programmer. This is not a plea for intentionally obfuscated code; that would be on the other side of the spectrum, but this trivial problem right here is below that lower bound so copiously to the point of being laughable, or maybe pathetic depending on your sense of humour.
- In short, if I were to be called on to understand and fix a 10MLOC system, I would appreciate those parts that are not only right, but clear in intent, purpose and correctness. Having to expend mental effort doing "arithmetic trivia" makes such a job harder.
- That's why this is an interesting question. Here is a small, easy problem. Now make your code not just correct, but obviously correct with as little mental effort as possible.
So you
obviously are chasing the mythical self-documenting code that requires no mental effort. Yes, programming requires a minimal amount of integer arithmetic. Sometimes requires pen and paper. That's the nature of the beast.
The minute you complain about 2 and a half minutes of mental effort required to understand why the specification leads to Y=N%K, and X= K-Y, that minute you are disqualified from doing maintenance work. Because even if I put variable names that are singing to your ears, they'd be singing out of tune, and the mythical maintenance programmer, will stare at them and will "think" - "Ah, I understand it, see how these variable names are speaking to me?", but he'll not understand a damn thing, because programming (even maintenance programming) requires mental effort.
I'm not a programmer by training, but it seems to me that the question being explored is how to make code as clear as possible. You are saying that real code, proper code, has a lower bound beyond which it is uneconomical to go with regards clarity. You are saying that writers of code can and should expect some minimal level of ability and effort with regards modifying code, and that is true for both maintenance and enhancement. That's probably true, although I'm not qualified to say.
It also seems, however, that for the purposes of exploring the question of how clear and simple code can be made, it is often instructive to examine a small, apparently simple example out of context. It's like a "Spike" from XP. This small problem is being pushed and pushed and pushed, not because it is interesting by itself, and not because it would be appropriate to go to that level in practice, and not because it is interesting, but because we're examining just how far we can go in clarity of code. Reading about RonJeffries, that pretty much has to include the proviso "without comments".
Developing techniques that successfully go beyond the bounds of reason for a single, simple, almost trivial problem, allows the chance that those techniques can be applied to bigger, harder, more serious cases. In those cases, it's harder to do anything, so something that successfully goes beyond reason in the simple case has a chance of getting further in the harder cases.
I can see why this problem, given that point of view, might be considered reasonable.
-- CarolineWilliamson
- Your comment "Any discussion about the art of programming related to such trivia is bound to be meaningless" shows a breathtaking arrogance, given that the question has come from RonJeffries. No, I don't revere him, but I have over the years come to appreciate his insights. Have you considered that he has seen something that you haven't?
- Who cares what you think it shows? Meaningless is quite a gentle word, because it's worse, it's an example of how not to approach such programs.
- The logical place for you to go, given that, is to describe the obvious (to you, given that) way to improve the original question, since it is flawed but not unfixable. You already suggested backtracking from a solution to an improved spec, but given the overall discussion, I think it would improve the whole topic just to give a more bulletproof spec that meets the original intention, while improving on its details.
I know, that this topic (splitting a sequence into "more or less" equally long chunks) is part of
TheArtOfComputerProgramming. I just cant remember where it is mentioned. I think it could be where merging/sorting is discussed, but I could be wrong. I remember the analogy with a rectangle. There were some fine differences which dependend on the means of splitting. Consider the variants 3331 and 3322 for splitting 10 into 4 chunks. --
GunnarZarncke
FebruaryZeroSix