How (not) to distribute 100 apples in 10 crates with python. | Hacker News Reader

How (not) to distribute 100 apples in 10 crates with python.

mail.python.org

57 pointsbgraves18 comments

It seems like an overengineered solution. A robot arm with image analysis? Why not just stick the apples in a hopper, put in a little door to release one apple at a time, and then just move the hopper back and forth (using a Python script) on a track along the line of crates?

You could also attempt to build a purely physical apparatus sans code to distribute them randomly, but it would take a lot of work to prove it was unbiased. The best solution might be a roulette-wheel style arrangement where the apples are emptied into the middle and move out towards the edges as the wheel spins (you might want to make the crates counter-rotate as you did this). Not bruising the apples might be a challenge.

I'm not sure how they're going to stop the pythons from eating the Apples, but if I had to do his homework this is what I'd probably do.

    import random
    boxes = [[] for x in range(10)]
    for apple in range(100):
        random.choice(boxes).append(apple)

    ## don't do it like this
    # [random.choice(boxes).append(apple) for apple in range(100)]

why do you not recommend a list comprehension?

List comprehensions are wonderful, but in his example it's not being used to generate an actual list (each .append() will return None), just as a strange alternate format for a for loop.

It would be really strange to do

    [random.choice(boxes).append(apple) for apple in range(100)]

when even if you wanted to do it on one line the normal syntax works and would be less likely to confuse:

    for apple in range(100): random.choice(boxes).append(apple)

If you're responding to a poorly-disguised lazy homework solution request, then the really strange version is the one you should give. Any student who tries to turn it in will arouse the suspicion of the grader, and they'll deserve it.

I had assumed the student would find a decent solution long before this hn thread.

Exactly right.

This is a pretty awesome response to a not so well disguised homework problem.

A simple way to do it is to imagine your apples sitting in a row, assign each one a random number, and sort them by those random numbers. Then the first ten apples go in one crate, the next ten apples go in the next crate, and so on.

But for some reason these guys always seem to want code, not a discussion of how the code might work.

I think a more flexible way might be to shuffle the boxes, placing each box into a ring data structure, and placing each apple into the next box.

As we'd expect each box to contain more than one apple this should reduce shuffling.

But yeah, I agree, they always want code not how it might work.

That assumes they want an even distribution of apples in each crate. My reading of the problem would suggest that for each apple we should choose a random box and insert the apple into said box.

The question seems like a poorly phrased discussion of the pigeonhole principle.

Well, you can extend the parent's solution by throwing in 9 "end of current box" markers with the 100 apples before randomizing the order, rather than declaring them to be every 10 apples after sorting. This is probably not an efficient solution from a programming perspective, but it's similar how you would count the number of distinct such arrangements in combinatorics.

As you said, not very practical from a programming perspective, but it's an interesting way of looking at the problem. Thanks.

http://developer.amazonwebservices.com/connect/entry.jspa?ca... may be of service to help ensure true randomness. It may be necessary to create a voting protocol to prevent malicious mechanical turkers from removing entropy from your boxes, and that should also make it suitably self-policing that you will minimize risk of Apple theft. Considering that Apples are among the most expensive consumer electronics, this would be among any poor student's highest concerns.

Am I missing the joke here?

I don't think the OP was talking about real, physical apples. Paragraph 3 off the response is the payoff, basically.

  M, N = 10, 100
  apples = xrange(N)
  L = random.sample(apples, N)
  crates = [L[i:i+M] for i in xrange(0, N, M)]

You are not randomly placing apples in crates. You are putting sequential groups of 10 in crates. 10 is the average number of apples that will be in each crate, but it is possible no crate has 10 apples in it.

Reply on news.ycombinator.com