It's 22:04
The idiot upstairs is making noise, moving heavy things across a concrete floor,
this is why I need to live in a house, I can't stand that kind of thing, and at
the same time I want to be able to make noise myself whenever I want.
Anyways, besides that, and being less productive than desired at work, the day
has been nice. Had a nice pizza for lunch yesterday, and a good burger today,
so, I wonder how I should poison myself tomorrow. After work I did a little bit
of C++, pulled down my bouncy-ball project from github, got it compiling and
started writing stuff, so now the balls react when they hit eachother. Making
them react to impacting eachother in a believable way without simulating forces
is a bit tricky, but I think it's maybe a bit more interesting, I got something
working now, so I'll likely rewrite it to be more real physics, with inertia and
masses and all that stuff :) While writing the code that checks collisions, I
noticed I was basically checking every ball against every other ball, which is
a lot more checks than are required, and it is close to O(n^2), so I thought
about it and drew a little picture, 4 balls as an example:
Ball Checks
1 | | | 3 checks
2 <-+ | | 2 checks
3 <---+ | 1 check
4 <-----+ Last ball has been checked by all.
So that's (n-1)+(n-2)+(n-3) Checks, or 4 checks, and no need to guard against
checking a ball against itself. I thought the sum could be expressed by the
sum of the sequence (n-1)..(n-n) I know n-n is 0, but I thought it'd be a nice
way to end it. Anyway, it happens that there's a name for this kind of number,
it's a triangular number. Maybe I was just lucky with my drawing, but it so
happens that the number of | coincides with the sum of the checks need to be
done. The reason I drew it was because I had trouble determining if all the
possible combinations of balls were checked against each other. They are, since
the direction of the check does not matter (there's no reason to check both
A and B, and B and A), which did become obvious to me at once.
There's a nice formula on wikipedia for Triangular numbers which I can't at all
understand, because I'm not schooled in mathematics, but I'm going to get up to
speed on set theory and discrete mathematics one of these days, I proise!
But it gives the same result as far as I can see, well, it's not entirely a
triangular number, it's a triangular number with the base widest row missing,
because we do not want to compare any balls to themselves. Anyway, close enough
to be intresting, if you wanted, you could do (n-0)..(n-n) to get it.
No art was created today.. and now, sleepytime!
