Moo's virtual world

Somehow things always come as a bunch. You see a squid on TV, and then your friend invites you to that new squiddy restaurant, and the next day it start raining squids! Ok, maybe not, but now you know what I mean. So that's what happened with me and fitting.

First, my friend got this test for a programming job where he had to come up with an algorithm (and code it) to do the following: Given a big square and a bunch of smaller squares, find if it is possible to fit all the small ones in the big one (no overlap of course) and if it is possible, give an example. Well, after thinking and thinking and coming up with a couple of different ways that didn't work, we sort of figured out there was no straightforward way to do this. It's the kind of problem that you have to solve by trial and error. (If you disagree, I'd like to hear your ideas) Not very satisfying after hours of intense reflection. And it's also not very efficient. And you still have to figure out how to program "try everything". Anyway, unless you are an avid square fitter, skip the next paragraph.

Here are some ideas if anybody cares. First, you have to sort the smaller squares. You start by placing the biggest one and you continue with the second biggest and so on. When you place a square, you put it in a corner. Obviously, if you put it in the middle of the free space, you're splitting the remaining available space into many smaller areas and the next square might not fit. So you have to keep track of every corner of empty area. I suggest keeping track of every rectangular free area. When you place a square, you replace one rectangle area with two smaller ones(on the two free sides of the square you just placed), and you can modify the size of a couple of other areas around there. That is the hard part, correctly adjusting all the areas. But once that's done, you can just call the procedure recursively for each square and voilà. That gives 4(N+1)! possible ways to try and fit N squares... way too much. But I think we can do a lot better. I think if you maximize the free area into large "squarry" areas (e.g. 4x4>3x20) at each step, it's the best way to put it, i.e. if it doesn't work that way, it can't work any other way. But I didn't prove that. Enough about squares.

Then, I come across this contest about fitting little chocolates into the trunk of a car. Guess how many can fit and win the car! Ok, so it's not the same kind of problem, the first was theoretical and the second more experimental. Being a physicist of the first kind, I still bought the chocolates and proceeded to do some precision measurements and error analysis to come up with the best possible estimate. But I didn't win. Otherwise I'd know by now (they were supposed to contact the winner yesterday). Major bummer dude. Anyway, you can see a detailed report of my efforts in my next post.

This concludes the proceedings.