After some brief searching, I found the best explanation for it: Glory. It's a "glory", a refractive effect caused by the sun shining onto the clouds.
Sunday, July 27, 2008
In all its glory
While on a plane trip, I saw a strange phenomenon:
See it? Let's make that a little clearer by adding contrast.
Cool, ain't it? First, I thought it was just a reflection of the window on the other side of the plane, but then I guess it wasn't, since there wasn't a window open. The faint apparition-like halo may have been just an illusion. Maybe I was gazing too much at the window. Maybe not...
After some brief searching, I found the best explanation for it: Glory. It's a "glory", a refractive effect caused by the sun shining onto the clouds.
After some brief searching, I found the best explanation for it: Glory. It's a "glory", a refractive effect caused by the sun shining onto the clouds.
Sunday, July 20, 2008
Codejamming
I tried the Codejam Qualification Round a few days ago, and it feels pretty hard for my level. I managed to score 55/75, and the 20 points lost was because of a tiny error in my program for question C (at least that's what I believe should be the problem; I tried the new, fixed program on a test data and this time it worked).
If you want to see the questions, please go to Google Codejam. I can offer the solution for any readers (see note at the very bottom).
A. Saving the Universe
This one should've been really easy, but unfortunately I screwed a lot things up, and ended up submitted several incorrect entries before getting the right answer.
Here's how I solved this problem:
Go through every query, from beginning to end, and make the best switch that minimizes the total number of switches. Make sure a counter is used to keep track of how many switches are made.
The real question here is: what constitutes a "best switch"? Well, after some thought, I realized that the best switch was the switch that maximizes the number of queries processed before changing to another search engine. So all I had to do was to try switching to each search engine and check how many queries it can process before it has to switch to another search engine. That was easy: just a simple maximization problem.
B. Train Timetable
While this is supposed to be a fairly easy problem, my solution kinda overcomplicated things, and it took me a whole day to figure out where the "bug" was.
Before I go onto the solution, I would like to note that a simple way to incorporate the "turnaround time", T, into the solution is to just assume that each train arrives T minutes later than what the schedule says (or equivalently, each train needs to depart T minutes earlier than what the schedule says).
My solution was to simply simulate all the trains as they go from station A & B and back. At every critical moment in time (explained later), the total number of trains that leave a station is counted. If somehow, the number of trains left at some station X is negative, then that means there's a deficiency in the number of trains. This deficiency is then added to the "required number of trains at station X" (this is what the whole question is asking for!) and the number of trains left at the station X is reset to zero. At the end of the day (when all the critical moments are processed/simulated), the "required number of trains at station X" is then output.
Note that I use the term "critical" to differentiate between moments of time that are uninteresting (e.g. when a train is mid-way/at a station, and nothing is happening) and those that are worthwhile to process (e.g. when a train departs or arrives). The simulator only needs to simulate critical moments in time.
C. Fly Swatter
This one was actually fairly easy, until I realized that I forgot to make a certain check to process the area. Okay, first things first.
This question simply asks you to find the ratio of the fly swatter area to a circular area of radius R... Oh wait, no: it says the fly is a sphere (of radius f), not a point! This might make things confusing. Since the fly is a sphere and not a point, it actually makes the fly easier to hit.
After some thought, I realized that an equivalent situation is when the area of the fly swatter has been extended by a distance of f, yet the fly is point-sized (positioned at the center of the spherical fly).
Now finding the fly swatter area is not easy. Instead of finding the area that is covered by the fly swatter, I decided to find the area of the holes in the fly swatter (which are either just squares or squares that are cut by circular arcs).
The side-length of each square is nearly the same side-length as the ones drawn in the Google Codejam diagram, but it must be subtracted by 2f. In order to find the areas of the squares that aren't perfect squares but cut by circular arcs (I call them "pseudo-squares"), you should set up a coordinate system and use integration. Now don't just do numeric integration (it'll take forever to get 6 decimal places), because an integral like:
can actually be simplified so that it's in terms of square roots and arcsines, which is less computationally intensive. In order to simplify calculations, don't bother calculating the area of the squares of the other quadrants of the fly swatter, since one quadrant is enough (it is symmetric, as the question states). Beware of cases when the width or height of the squares (or "pseudo-squares") is negative, which is often as a result of subtracting the actual height or width of the squares (or "pseudo-squares") by 2f. In such a case, make sure you check for this situation, and treat the square's area as zero.
After that, the rest is pure logic and iteration. Just be careful with the signs and how you get all those coordinates, and the rest should be pretty easy.
Feel free to ask me to email a copy of my code (in Python) for any of these 3 questions. (The code for question C has been corrected already, by the way.) I'm fairly confident that they are correct, but you can verify them with the Google Codejam Qualification Round practice questions just to be sure. You can put requests in the comments.
If you want to see the questions, please go to Google Codejam. I can offer the solution for any readers (see note at the very bottom).
A. Saving the Universe
This one should've been really easy, but unfortunately I screwed a lot things up, and ended up submitted several incorrect entries before getting the right answer.
Here's how I solved this problem:
Go through every query, from beginning to end, and make the best switch that minimizes the total number of switches. Make sure a counter is used to keep track of how many switches are made.
The real question here is: what constitutes a "best switch"? Well, after some thought, I realized that the best switch was the switch that maximizes the number of queries processed before changing to another search engine. So all I had to do was to try switching to each search engine and check how many queries it can process before it has to switch to another search engine. That was easy: just a simple maximization problem.
B. Train Timetable
While this is supposed to be a fairly easy problem, my solution kinda overcomplicated things, and it took me a whole day to figure out where the "bug" was.
Before I go onto the solution, I would like to note that a simple way to incorporate the "turnaround time", T, into the solution is to just assume that each train arrives T minutes later than what the schedule says (or equivalently, each train needs to depart T minutes earlier than what the schedule says).
My solution was to simply simulate all the trains as they go from station A & B and back. At every critical moment in time (explained later), the total number of trains that leave a station is counted. If somehow, the number of trains left at some station X is negative, then that means there's a deficiency in the number of trains. This deficiency is then added to the "required number of trains at station X" (this is what the whole question is asking for!) and the number of trains left at the station X is reset to zero. At the end of the day (when all the critical moments are processed/simulated), the "required number of trains at station X" is then output.
Note that I use the term "critical" to differentiate between moments of time that are uninteresting (e.g. when a train is mid-way/at a station, and nothing is happening) and those that are worthwhile to process (e.g. when a train departs or arrives). The simulator only needs to simulate critical moments in time.
C. Fly Swatter
This one was actually fairly easy, until I realized that I forgot to make a certain check to process the area. Okay, first things first.
This question simply asks you to find the ratio of the fly swatter area to a circular area of radius R... Oh wait, no: it says the fly is a sphere (of radius f), not a point! This might make things confusing. Since the fly is a sphere and not a point, it actually makes the fly easier to hit.
After some thought, I realized that an equivalent situation is when the area of the fly swatter has been extended by a distance of f, yet the fly is point-sized (positioned at the center of the spherical fly).
Now finding the fly swatter area is not easy. Instead of finding the area that is covered by the fly swatter, I decided to find the area of the holes in the fly swatter (which are either just squares or squares that are cut by circular arcs).
The side-length of each square is nearly the same side-length as the ones drawn in the Google Codejam diagram, but it must be subtracted by 2f. In order to find the areas of the squares that aren't perfect squares but cut by circular arcs (I call them "pseudo-squares"), you should set up a coordinate system and use integration. Now don't just do numeric integration (it'll take forever to get 6 decimal places), because an integral like:
can actually be simplified so that it's in terms of square roots and arcsines, which is less computationally intensive. In order to simplify calculations, don't bother calculating the area of the squares of the other quadrants of the fly swatter, since one quadrant is enough (it is symmetric, as the question states). Beware of cases when the width or height of the squares (or "pseudo-squares") is negative, which is often as a result of subtracting the actual height or width of the squares (or "pseudo-squares") by 2f. In such a case, make sure you check for this situation, and treat the square's area as zero.
After that, the rest is pure logic and iteration. Just be careful with the signs and how you get all those coordinates, and the rest should be pretty easy.
Feel free to ask me to email a copy of my code (in Python) for any of these 3 questions. (The code for question C has been corrected already, by the way.) I'm fairly confident that they are correct, but you can verify them with the Google Codejam Qualification Round practice questions just to be sure. You can put requests in the comments.
Thursday, July 10, 2008
Getting oriented with Ubuntu (for Windows users)
Okay, just for the record here, I'm also a beginner, just-migrated-from-Windows kinda person. But still I think I should share some of my own thoughts and experience about Ubuntu - from a newbie's perspective.
Installation
First things first: Ubuntu installation. This is the easiest part actually: just follow the instructions. One of the things that was unclear for me (and just to make sure I didn't make any mistakes as a newbie) was the Linux partitioning process. You see, a Windows-adapted user would think that one partition is enough (and I thought NTFS was good enough), but it's not!
(For a detailed review of Ubuntu partitioning, just go to this neat article.) Ubuntu needs a minimum of 2 partitions (1 would still work, but not recommended).
You might wonder if Ubuntu would support all your drivers. In my situation, things went fairly smoothly (referring to drivers). The only thing I had to do was to force the nVidia driver, which wasn't open-source, to be enabled (it's under System > Administration > Hardware Drivers). While it's true some things won't work here, like the QuickPlay buttons (rejoyce! that pesky QuickPlay won't work in Ubuntu!), or the Fingerprint Sensor (frankly, it started out useful, then became really annoying, because my arm sometimes touches it while typing, and hence activating the sensor unintentionally). Everything else seems to work: 3D acceleration, touchpad, mute and volume keys... Strangely easy.
Getting used to the interface
This part requires lot's and lot's of practice. Just to get people understand the basic interface, I'll explain this briefly. Note that "GNOME" is a word used to describe the kind of graphics Linux provides. Aside from the colorful GNOME interface, there's also what is called "KDE", although I've never seen that before (or I've seen it somewhere but didn't know).
The "bar" on top is the place where you:
Okay, aside from the interface difference, I think the rest of the interface are fairly easy to understand, like the windows etc.
Installing programs
This is going to be an essential, yet simple skill. It's not like Windows where you buy a disc or download a binary EXE installer file to install applications. All you need to know is that nearly all of the designed-for-Linux programs (free, open-source ones, of course) can be installed by simply visiting System > Administration > Synaptic Package Manager.
I think this program is specially designed for beginnerz who don't know a thing about the Linux file system or the command line (Terminal). So let's see how this thing works. First load it, then you'll see a list of weird-looking names. Those are the programs. Suppose you want to install Blender, then you just search for "blender", place a check-mark on the "blender" program that you found, and click "Apply" to install it. Note that you can't run all these 3 programs at the same time without having them conflicting:
(Note: sudo is a command that gives you "root" permission [i.e. "Admininistrator" permissions])
There are slightly more complex ways of installing programs that you'll eventually have to learn, but don't be overwhelmed. The easiest way to solve them is to look for answers on the Web.
Using Ubuntu
I'd say the Ubuntu interface is really intuitive, so I don't think there would be too much trouble doing stuff. You might have to wander a little on the first few days, since you probably don't know where things are, but over time you would get used to things. There's the same windows control and similar keyboard shortcuts (mostly), so I think the transition would be smooth.
Just a reminder, Ubuntu's "Explorer" equivalent is called Nautilus (file system browser) and you should be able to access it simply from the Places menu (just click one of those items). The equivalent "Internet Explorer" is simply Mozilla Firefox.
Whining for wine
Ignoring the pun in the title, you should probably be aware of a program called Wine, since it can allow many kinds of Windows programs to run on Linux. While I don't think it's perfect, it's worth a shot if you really want an important Windows program to run on your Ubuntu. In most cases, however, you should settle for a free, open-source version of a program rather than to force a Windows program to run on Ubuntu, if possible.
Installation
First things first: Ubuntu installation. This is the easiest part actually: just follow the instructions. One of the things that was unclear for me (and just to make sure I didn't make any mistakes as a newbie) was the Linux partitioning process. You see, a Windows-adapted user would think that one partition is enough (and I thought NTFS was good enough), but it's not!
(For a detailed review of Ubuntu partitioning, just go to this neat article.) Ubuntu needs a minimum of 2 partitions (1 would still work, but not recommended).
- One is the "/" partition, which is the root of the folder tree system. (Kinda like your ordinary "C:" drive, but not exactly the same.) This one should be moderately small, >5GB minimum, I think. (This drive is a must.)
- The other is the swap drive, which is basically a partition used specifically as a swap memory (i.e. a "page file" as Windows calls it). This one is somewhat small, ~2GB maybe. (I chose 5GB, just in case I needed more.)
- You can create an additional "/home" drive to store all your data files. If you choose to do so, just fill the remainder of your free space for this drive. (I did so myself.) The fact that the "/home" directory looks as if it's a subdirectory of the "/" root directory doesn't matter, since physically they are separate partitions.
You might wonder if Ubuntu would support all your drivers. In my situation, things went fairly smoothly (referring to drivers). The only thing I had to do was to force the nVidia driver, which wasn't open-source, to be enabled (it's under System > Administration > Hardware Drivers). While it's true some things won't work here, like the QuickPlay buttons (rejoyce! that pesky QuickPlay won't work in Ubuntu!), or the Fingerprint Sensor (frankly, it started out useful, then became really annoying, because my arm sometimes touches it while typing, and hence activating the sensor unintentionally). Everything else seems to work: 3D acceleration, touchpad, mute and volume keys... Strangely easy.
Getting used to the interface
This part requires lot's and lot's of practice. Just to get people understand the basic interface, I'll explain this briefly. Note that "GNOME" is a word used to describe the kind of graphics Linux provides. Aside from the colorful GNOME interface, there's also what is called "KDE", although I've never seen that before (or I've seen it somewhere but didn't know).
The "bar" on top is the place where you:
- Applications: load a program (or game, utility, accessory).
- Places: open the File Browser to view files and folders/directories. (This is equivalent to opening the Explorer in Windows.) It also has some Networking stuff in there too.
- System: manage settings and configuration stuff (i.e. "Control Panel" in the form of a menu). Most of them are fairly straightforward and user-friendly.
- There should be some icons right after the three menu items, and you can drag and place your favorite icons here (kinda like a "Quick Launch").
- On the far right, there's a panel that looks like the Windows "Notification Area". It has the clock and some miscellaneous icons.
Okay, aside from the interface difference, I think the rest of the interface are fairly easy to understand, like the windows etc.
Installing programs
This is going to be an essential, yet simple skill. It's not like Windows where you buy a disc or download a binary EXE installer file to install applications. All you need to know is that nearly all of the designed-for-Linux programs (free, open-source ones, of course) can be installed by simply visiting System > Administration > Synaptic Package Manager.
I think this program is specially designed for beginnerz who don't know a thing about the Linux file system or the command line (Terminal). So let's see how this thing works. First load it, then you'll see a list of weird-looking names. Those are the programs. Suppose you want to install Blender, then you just search for "blender", place a check-mark on the "blender" program that you found, and click "Apply" to install it. Note that you can't run all these 3 programs at the same time without having them conflicting:
- Update Manager
- Synaptic Package Manager
- Add/Remove... (which is an even more beginner version of the Synaptic Package Manager, for installing or removing programs).
sudo apt-get install [some-program-name]then you should know that you are installing a package from the command line.
(Note: sudo is a command that gives you "root" permission [i.e. "Admininistrator" permissions])
There are slightly more complex ways of installing programs that you'll eventually have to learn, but don't be overwhelmed. The easiest way to solve them is to look for answers on the Web.
Using Ubuntu
I'd say the Ubuntu interface is really intuitive, so I don't think there would be too much trouble doing stuff. You might have to wander a little on the first few days, since you probably don't know where things are, but over time you would get used to things. There's the same windows control and similar keyboard shortcuts (mostly), so I think the transition would be smooth.
Just a reminder, Ubuntu's "Explorer" equivalent is called Nautilus (file system browser) and you should be able to access it simply from the Places menu (just click one of those items). The equivalent "Internet Explorer" is simply Mozilla Firefox.
Whining for wine
Ignoring the pun in the title, you should probably be aware of a program called Wine, since it can allow many kinds of Windows programs to run on Linux. While I don't think it's perfect, it's worth a shot if you really want an important Windows program to run on your Ubuntu. In most cases, however, you should settle for a free, open-source version of a program rather than to force a Windows program to run on Ubuntu, if possible.
Friday, July 4, 2008
Dragging energy
If anyone noticed an error in the equations, feel free to contact me or report it in the comments.
Well, I didn't intend to turn this into a SciLearn post, but seeing as how I actually did a lot of working to get the answer, I might as well share the working and conclusion with everyone else. This is the question I was asking (I asked myself this question when considering whether cars burn more fuel when accelerating slowly or when accelerating rapidly):
(By the way, I've finally resorted to using LaTeX for rendering equations. [ credits ])
Answer for (1)
The answer for (1) is simple and obvious: Both require the same energy, i.e. the kinetic energy at velocity. So for both objects, E = m V2 / 2 where E is energy & m is the mass of each object.
Answer for (2)
(This is going to turn out to be a really long post.) The answer for 2 is a bit complicated. Start by considering object A:
Here, EdragA is the energy needed to overcome drag (not work done by drag, which is why there's a negative sign) and DA is the drag force.
Since drag is assumed linear:
where v is the speed of object A and k is a constant. v is a function of x, however, so it must be also substituted.
According to the uniform acceleration equation v2 = u2 + 2 a s:
Now we can put these equations back into our original drag energy equation.
Substitute the variables to find the drag energy:
This is how much energy object A requires to overcome drag.
For object B, the formula is the same, except the variables are slightly different:
Here, db is the distance traveled during part 1 of the motion.
For part 2 (during which object B also travels at constant speed until the total distance traveled is the same as that of object A), we need additional energy to mitigate the constant drag force that occurs at maximum speed V, until the total distance becomes d1. Therefore, during this period, the object travels a distance of (da - db).
Using "energy = force × distance" for a constant drag force D over a distance of (da - db) gives:
(The negative sign is, again, because we are calculating energy required to mitigate drag; anyway, that's not important here.)
Applying the same v2 = u2 + 2 a s for object A and B (part 1):
The total drag energy for object B is therefore:
Now that's a weird equation. At least it looks right. If aa = ab then obviously EdragA = EdragB, which makes sense. What if aa < ab, as specified by the question? Well, from the equation here, it's obvious that EdragA < EdragB. So this is our answer to (2):
Note: this equation cannot be used for aa > ab. If so, object B would have to go backward for part 2 of the motion, in order to negate the extra distance object B traveled as it slowly accelerated to V.
Answer for (3)
Alright, now onto question (3)! Okay, we are still using the same equations, except now we use a quadratic relationship between drag and speed:
Again, k stands for some constant.
For object A, start with the integral for EdragA:
For object B, use the same procedure as for question (2):
Once again, the same conclusion can be drawn, which also answers question (3):
Disappointingly, I realized that, upon closer examination of the sketched graphs shown above, I realized that it was surprisingly obvious that object B would definitely require more energy than object A, but, at least, we now have some equations that actually describe how much more energy object B would require compared to object A.
Well, I didn't intend to turn this into a SciLearn post, but seeing as how I actually did a lot of working to get the answer, I might as well share the working and conclusion with everyone else. This is the question I was asking (I asked myself this question when considering whether cars burn more fuel when accelerating slowly or when accelerating rapidly):
Object A accelerates uniformly with positive acceleration aa up to a speed V, traveling a distance of da.
An identical object B accelerates uniformly with positive acceleration ab (such that aa < ab) up to the same maximum speed of V (part 1), and continues to travel at the same speed until the same total distance of da is reached (part 2).
Which object requires greater energy with (1) no drag forces, (2) a linear drag force, or (3) a quadratic drag force?
(By the way, I've finally resorted to using LaTeX for rendering equations. [ credits ])
Answer for (1)
The answer for (1) is simple and obvious: Both require the same energy, i.e. the kinetic energy at velocity. So for both objects, E = m V2 / 2 where E is energy & m is the mass of each object.
Answer for (2)
(This is going to turn out to be a really long post.) The answer for 2 is a bit complicated. Start by considering object A:
Here, EdragA is the energy needed to overcome drag (not work done by drag, which is why there's a negative sign) and DA is the drag force.
Since drag is assumed linear:
where v is the speed of object A and k is a constant. v is a function of x, however, so it must be also substituted.
According to the uniform acceleration equation v2 = u2 + 2 a s:
Now we can put these equations back into our original drag energy equation.
Substitute the variables to find the drag energy:
This is how much energy object A requires to overcome drag.
For object B, the formula is the same, except the variables are slightly different:
Here, db is the distance traveled during part 1 of the motion.
For part 2 (during which object B also travels at constant speed until the total distance traveled is the same as that of object A), we need additional energy to mitigate the constant drag force that occurs at maximum speed V, until the total distance becomes d1. Therefore, during this period, the object travels a distance of (da - db).
Using "energy = force × distance" for a constant drag force D over a distance of (da - db) gives:
(The negative sign is, again, because we are calculating energy required to mitigate drag; anyway, that's not important here.)
Applying the same v2 = u2 + 2 a s for object A and B (part 1):
The total drag energy for object B is therefore:
Now that's a weird equation. At least it looks right. If aa = ab then obviously EdragA = EdragB, which makes sense. What if aa < ab, as specified by the question? Well, from the equation here, it's obvious that EdragA < EdragB. So this is our answer to (2):
Object B requires more energy than object A.You can easily find out how much more does it require by using the simplified equation above. (You might be urged to say that the conclusion is "obvious", but I really wanted to confirm this using math. After all I can't just say obvious and put a close to this question, which seems very interesting.)
Note: this equation cannot be used for aa > ab. If so, object B would have to go backward for part 2 of the motion, in order to negate the extra distance object B traveled as it slowly accelerated to V.
Answer for (3)
Alright, now onto question (3)! Okay, we are still using the same equations, except now we use a quadratic relationship between drag and speed:
Again, k stands for some constant.
For object A, start with the integral for EdragA:
For object B, use the same procedure as for question (2):
Once again, the same conclusion can be drawn, which also answers question (3):
Object B requires more energy than object A.In reality, drag works in a very complex way, but for a simplified situation, it seems that cars do burn more fuel when accelerating faster.
Disappointingly, I realized that, upon closer examination of the sketched graphs shown above, I realized that it was surprisingly obvious that object B would definitely require more energy than object A, but, at least, we now have some equations that actually describe how much more energy object B would require compared to object A.
Subscribe to:
Posts (Atom)
Posts
