Coding Problem Question

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. 

   /**
    * 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: 

  boolean You_bloody_have_to_use_your_brains_and_possibly_some_pen_and_paper_to_check_out_trivia_arithmetics=true;
bring you any help? 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. 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

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

EditText of this page (last edited August 23, 2006) or FindPage with title or text search