They try to teach us optimisation

Optimisation is a common task they give to you in computer science. For the uninitiated, it basically means to adopt some means to make your code run faster. Whatever this means is, it is up to your interpretation. Generally it is interpreted as having a better algorithm– compare this to the analogy of getting to school in the fastest possible method. You can choose to walk there, run there, travel to Malaysia and back on a bus before you reach there, or you can consult gothere.sg and take whatever route they advise there. The trade-off is between effort, money and time. Similarly, in computer science, how fast your algorithm runs is a trade-off between time, space (that is, the computer memory space) and effort on your part.

“Optimisation is done based on your data set,” as our wise Junwei states.

Lately, a new contest has popped up on our CS2020 game server. The task is to upload a java file which, given an input, produces the factorial of the input. It gives a grand total of, drumroll, one experience point.

For the truly desperate amongst us who are just 1 exp away from levelling up.

“This is a godsend!” says John the truly desperate. “I am 2 exp away from levelling! Now if only they would give another competition with 1 exp…”

Now the format of the competition stands as follows: you upload a java file to the server. The server does some awesome thing where they calculate the amount of time it takes to run your java file on their two test cases, assuming your java file produces the correct output, and then puts the time up on the leaderboard of the competition page for the whole of CS2020 to see.

Now one has to practise what one preaches, and that is exactly what Jun Wei is haunted by at every moment of the day– to optimise his code based on the data set that is thrown to him.

Notice I said there were two test cases for the competition leaderboard. There are various ways to write a factorial code, the most obvious way being to have a counter and keep multiplying the counter which increments at every loop to the next integer until it hits the input. You know, 1x2x3 for 3!, etc and etc.

Let me assure you that you will never get 0.12 seconds which is what is shortest time now with that code. If you do I’ll treat you to koi bubbletea.

Nor will you get 0.12 by putting the values into a table and then just extracting the value, stupid as this sounds. While extracting a value from a table is almost instantaneous, building the table is apparently more time consuming than repetitively multiplying.

Perhaps Joe, who was the only one sitting snugly at that position when we checked the website at noon before Junwei came up with it, can tell you how to get 0.12 seconds.

At this point in time there is a need to introduce Joe, our local hacker who tries to think of every possible way to thwart the system. The first glimpse we got of his hack0r skeelz was during our deathcube competition last semester, where we pitted against each other’s players to find the deathcube and bomb it first, along the way killing whatever drones we encounter with our lasers, lightsabers and magic spells. This is done through typing out code for these players, instructing them on what to do upon meeting certain situations– for example, if you’ve already visited a room, do not visit it again; if you see the deathcube as one of your present room’s neighbours, go to it, etc. Killing gets you 10 points while bombing the generator room gets you 100. Everything was running without a hiccup until round 4 started, round 4 being the round with Joe.

“LOL WHAT IS UP WITH JOE’S SCORE?” exclaimed the flabbergasted Schemers, who were staring at the score screen beside the game.

Joe’s player looked like it was swallowing up generator rooms every five seconds, with his score climbing to an impressive 400 within the first 20 seconds. This is impressive because there is only one generator room.

Not to mention, the game ends when you bomb the generator room.

Also, there will never be 10 drones for you to kill at one go each time to get 100 points.

Nor do you have enough weapons to kill all 10 drones, especially since your weapons take a turn to recharge every time you use them.

Do I have to mention the fact that they don’t deal enough damage to kill drones completely in one go individually?

Patrick smelled something fishy and decided to ban Joe from the game. You know, like you ban people who use bots in MMORPGs.

The secret behind Joe’s rapidly increasing score? Like every other Schemer’s player, he had his player question the room if it has a generator at every turn, and like every other player, he instructed his player to bomb it if it is. Unlike every other player, he included an extra method for his player: make his player answer true to the question “is-a player generator”.

This also means he committed hara kiri every time he respawned, that is, if someone hadn’t bombed him first.

Let me tell you the algorithm for 0.12 seconds:
1. Find lots of time
2. Make sure your control-c control-v is working
3. Control c control v
if (input == a){
System.out.println(b);
}
else
System.out.println(c);

where a is a constant you manually put in, b is the factorial of the constant, and c is the factorial of another constant, these two constants being what you are currently trying to guess as the two test cases. System.out.println is just a command to print out whatever’s in the brackets.

Yes, computing for dummies. With lots of time.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s