Thoughts of a Psych/Code Monkey/Guitarist

Ok, so I've just officially passed Uni, only getting under an HD in one subject throughout the last 3 years (missed by one single solitary percent in 2nd year computer systems. Oh how it mocks me), admittedly putting not much effort into most subjects or even attending more than about 10hrs per week, so now I figure it's time to put some of this knowledge of the last three or so years to good use. Starting with this summer - I have to do an internship at SAAB systems (army stuff, not car stuff) for the next 3 months. While the coding is boring, the 1-hr commute twice a day is a pain, and being stuck 30mins from anywhere for 40hrs a week is inconvenient, it's ok - the ppl are nice (mostly, even if my supervisor doesn't thinks I'm a bit of a slow worker :S), there's free diet coke, and the work is pretty easy so no pressure. I guess it's something for the resume, if little else. It's just weird, having so much stuff I want to do, but never enough time to d

Problem I - Mr Thomspon's Problem Ok, so think of the numbers as nodes on a graph. Put an edge between two numbers if they sum to one of the possible sum numbers. Your answer is then the maximum matching of the graph. Not suprisingly, and (in the interests of creativity in the problems and their solutions),= unfortunately, there already exists a standard algorithm for finding the max. matching. Jack Edmonds detailed this algorithm in a paper in 1965 called 'Paths, Trees and Flowers' which does exactly what is required in the problem. Rather than writing about it again here, I'll redirect you to a lecture by one of his colleagues which describes it better than I could. Personally, having this in seems too hard for an ACM regional, as noone is expected to know of this algorithm, and the only other way to solve it is an optimised brute force, yet these would no doubt still be too slow if custom test-cases could be prepared [a la TopCoder challenge phase]. Instead, it w

Problem E - A Fitting Advertisement It wouldn't be an SPP ACM Regional without its fair share of bugs, and this problem provided them for us. Given a histogram (i.e. heights across X value), find whether rectangles fit inside it. Sounds simple, with small catches - the heights can be zero, though that changes not much, and it doesn't matter which orientation you have for the rectangle, though again, you can just treat it as two different rectangles, and OR the results together, not too bad. Ok, so as submissions come in, people whose code looks right are failing. A bit of testing by the judges leads to the discovery that some of the rectangles you are placing have their width (or height) zero, which is explicitly disallowed in the problem specification. What's more, it's hard to know when a zero-sized rectangle fits within the histogram - the most 'logical' to me would be that it always fits, as it has zero area, yet the official judgement was different. Here

Question H - Automatic Marking I usually like tree problems, they often have ncie recursive solutions using little code - a good example is Paths from the regional in 2005. This still was good in that sense, however the extra parsing/validation was a bit of a paint. Because of the fiddly-ness of the input, this again is one where it's more profitable to spend much time planning, rather than coding. In this case, I found it simplest to write my own tree structure, then separate it into sections which: Parse the input into a tree, returning null for an invalid tree Find where the single '?' is in the tree - returning a pointer, so you can.... Replace the '?' with each letter, and validate the tree using the rules they give. The use of a pointer here makes it easy to change the '?', and while the re-validation might be a bit slow compared to figuring out the valid range in one pass of the tree, it seems like it should still be fast enough, and results in les

Problem D - Challenging "Butts" Despite the interesting name, and somewhat tedious flavourtext, the actual underlying question was, to me, the best of the set (close to problem C). So, ignoring the darts stuff, we're given a circular track which is split radially into N >= 3 sectors, and also halved along the centre of the track, giving us 2N zones in total. We then are given numbers, and have to place them one per zone, such that the sum of differences across all zones sharing a border is a maximum. It turns out that one greedy assignment will work - start in one sector, place the highest on the outside and the lowest on the inside, move to the next sector, place the next highest on the inside and the next lowest on the outside, etc... However, why this works is not immediately obvious. From what I've heard many groups submitted this without proof of correctness - while it's an ok strategy if the proof would take some time, doing this could be costly, and ext

Problem G - DNA Chopper Ok, getting past the added flavourtext, what it turns out you have to do is this: Given a list of n numbers, continuously remove two numbers from the list and put their sum back into the list, and add the sum to your total cost - stopping once you only have one number in the list. Find the minimum cost of doing this. [Unfortunately?] It just so happens that this is a well-known and solved problem, helping in the area of compression (to see how, I'd recommend reading about Huffman Coding ). It also so happens that it's used in numerous contests (e.g. TopCoder problem ' DiskCut ' and various other ACM contests ) so anyone who's done many matches is likely to have seen this. The algorithm for solving it is pretty much the greedy approach to that mentioned above - in the 'remove two numbers step', you simply remove the two lowest numbers. This can be done quickly, and in very little code, using a priority queue (set up to remove the lowe

Problem C - Self-divisible Numbers Personally, I'd rate this as the 2nd best problem of the set [and not just because I know who wrote it =p] - why? Well, firstly, it's original, approacable, easy to understand, and not heavy on textbook algorithms. Secondly, because it seems so easy..... You're given two numbers (call them lower and upper), and instructions on how to tell if a number has a certain property ('self-divisible'), and have to output the number of self-divisible numbers between lower and upper [inclusive]. The property is easy to test, so all you do is read in lower, upper, do a for-loop between them, count the self-divisible numbers and you're done - ... Except this is the first question where bounds are important. Each of the numbers 'consists of K digits, 0 <> - so your numbers are as big as 10 400 . This means: You cannot read them as ints. No, you can't even read them in as long long (or long in Java). Yes, you can use a BigIntege

Problem B - Rating Points Exchange Apologies in advance to anyone new to programming contests, who just happened to have this problem as the second ever programming problem they see. Not that it's a bad problem - every contest seems to need at least one messy, fiddly, floating-point-error-prone problem to show that not everything is nice and discrete. Like many other of its type, the problem was basically: using floating point ratings, apply a formula we give you to them, and output the result after doing it many times. Oh, and the formula has about 10 rules. Don't worry, even the World finals has questions like this (although slightly more tricky), in a way it's a good test to see how familiar you are with your language, and pedantic you can be testing. As the algorithm is given in the problem statement, I can't say much, except re-iterate the important point: Don't use floating point numbers when you can avoid them. You'll notice that all calculations in this

Problem F - The Zits Code Kudos to the writer for merging a comic reference [even including a pic of Jeremy at the start] - with a dig at Dan Brown. Anyway, after question A this seemed the second most popular question, possibly as it tells you exactly what to do, the difficulty lies in finding a nice code-able way of doing it. The exact encryption scheme is given to you - use a square grid, spiral the message through it, pad the rest with '$', and return the grid read one row at a time. Finding the size of the grid is simple - ceil(sqrt(size of input)) for those mathematically inclined, however it's safer and easier to calculate that with a loop - as is passing with '$' and forming the output, the tricky part left then is spiralling. To see how it's done, look at the the sample 6x6 grid they give, and the path we take around it: [using (0, 0) as the top left, and (5, 5) as the bottom right, as this is where they'd go in an array) At (0, 0), facing east, t

Question A - Text Formatting The first question of the ACM is usually the warmup, and it was no exception this year. The problem's title pretty much sums up what it's about - given lots of lines, tokenize, word wrap, output the number of lines. Which also describes how to solve it: Parse the input cases, one at a time, by reading each line and splitting into tokens (good for this is Scanner in Java or stringstream in C++). Count the number of lines and the #characters on the current line. For each word, either add it to the current line (plus the two spaces) if it fits, or put it at the start of the next line. And that's it - (untested) code can be found here . Personally, I had thought more teams should have been able to solve this, however it's possibly due to some of the tricks (e.g. not adding extra two spaces at the start of a new line) and maybe because string input is usually seen as nastier to handle than numbers [it seems, anyway]. Still, an ok warmup nonethe

This weekend the South Pacific ACM regional contest was held - this is a yearly programming contest for university teams of three throughout Australia and New Zealand. Unfortunately, my having come top of Australia for the last two years, there was a rule saying we couldn't compete this year (or ever again) however instead we helped out with the submission judging. There were many teams competing, though the number of successes per team was low (as expected - this is a hard contest!), partially due to a number of regretable errors in the testing data given to us [*sigh*, it always happens, don't ask]. Also, no official solutions or data is ever made public, so instead I thought I'd present an analysis of solutions here over the next week, with explanation and code for each question starting tomorrow. For now, the problems aren't yet up, but eventually will be available here.

Election time is slowly approaching - which means voting. Democratic voting seems an ok way to do things, but it does have a few side-effects. While I know there's no perfect voting system , and I'm not suggesting any changes, my thoughts on why elections aren't that interesting: My vote counts for too much: I'm a debt-less uni student, not renting, working for a US company, and most likely will be not in this country in a few years, it'd be nice if I could somehow optionally weight my vote downwards, but that's not (legally) allowed. Actually, my vote doesn't matter: My local MP is Alexander Downer - it's not like he's not going to win by many votes, so who I vote for doesn't really make much difference at all. Now, the usual response from people when I say this is: " But what if everyone thought this way? ". To which my response is always that they'll think that way whether I do or not, it still doesn't make any difference. Th

Challenge: Next time you're waiting, listening to music, near someone doing the same - set both your players to random, then swap headphones. Share the fun; do the iPod Shuffle Shuffle.

Las Vegas was Hot, Hotham was Cool! {gotta love the english language}. Anyway, something worth watching:

I'll be in LV for the next week (competing, see here for info, and there'll even be a live webcast of the final here ) then Skiing for the week after. If you want to reach me (for some strange reason) I should be checking phone / email occasionally, but apologies in advance for any delays. I'm taking a camera (odd for me, I know) so hopefully will have some pictures to put here later. Adios, until then.

Vocabulary changes with the each generation. Credit used to be something given when it was due - a reward, bestowed on those who worked hard for it. Inventors were given credit for their findings, artists recognised 'to their credit'. Times have changed however - the age of Credit is upon us, though this is not nearly as appealing as its previous meaning. No, this Credit is the opposite - 'money borrowed with the understanding that it will be repaid'. Often value given before it has been earned, the popularity behind credit cards has led to a generation who spends before earning. While making sense for once-offs (single payments with a definite deadline, slightly before the payer is guaranteed to have enough), a more common practice is to use these cards to buy everything in advance. For some reason, Credit is often treated as ' free money ' - a card with $5000 limit is seen as free $5000 that can be spent at will. Never mind the ludicrously high interest rate (

Do you follow this religion? - Followers meet up often, many groups who follow it meet once per week, usually Friday, Saturday or Sunday. Devotees sometimes confirm their faith before sleeping each night. Friends can meet for whole weekends, wanting to practise this religion. It has spawned many songs, even dances. If your parents follow it, you're more likely to. When it's introduced into new cultures, it's believed to usually have a negative impact, and sometimes warps the minds of younger followers until they're fanatic believers. No, this isn't Christianity, or any standard belief system. It's followers are also more likely to crash a car, smoke, and take illegal drugs. It's often tied to aggressive behaviour, mindless behaviour, loss of control, yet it's still widely popular. Welcome to being drunk, the new religion. It's your choice to believe, just don't try to convert me.

Originally, I was skeptical about cameras in phones. Now I'm still skeptical, just slightly less: Hilton Sydney does everything, even swipe-card instructions From the same elevator, but a much nicer usage of physics Big Brother game - each word is an anagram of the one above, plus one letter, apparently.... Look familiar? 'tis Adelaide Uni's unique seating arrangements Finally, can you guess the animal? "Cute" doesn't count

So, recently I've been doing some work reviewing program designs, i.e. finding bugs, recommending areas for improvement. I think someone should do that to MSN: I must admit, at least they have the irony of putting them for the thinking smiley and the eyes-rolling smiley.

One of the ideas behind Survival of the fittest is that the 'stronger' members of a species will reproduce more, so their stronger genes will appear more and help assist the survival of a species. The problem is however, what happens when you reach a point that the 'strong' properties aren't useful any more. Who needs a spear thrower these days? The importance of a fit, baby-carrying body is reduced substantially when modern medicine helps you stay alive. Either way, one would think that this could then lead to development of mental, rather than physical, abilities. Unfortunately, this is not the case - while it is socially expected that people will try to look their best (c.f: Shows like the Biggest Loser), it is not expected that people will think their best. In fact - thanks to our friends drugs and alcohol, it is socially expected that people will become LESS intelligent when interacting with others. Anyway, here's a maths interpretation of some possible

Google adsense banner at blogwatcher ::

And now for something completely different: We bring you to the apartment of Rob Stongetti, a man who claims to have created the world's first good looking myspace profile. To tell us about his acheivement, we__ Hold on a second! That's not completely different. I BEG your pardon?! You just then said that something completely different would appear. Yes? You've just witnessed a segue from a lady attacking a Starbucks with a novelty pencil, to you, a man with a command of web-page constitution, I'm sorry if my non-sequitur meter is broken. Can't you see? Both plot the tale of an eccentric protagonist, relying on the viewer's humour to provide a strange commentary on modern day capitalsim....and neither featured a red porcupine named Roger. ...Who are you? The King of comparative literature? *whooosh* DID SOMEONE CALL???? What noooooooow? You shall bow in my presence, for I, Hunter Codswallop, am the King of comparative literature. Oh my, I don't believe th

It has happened - proof of the world's slump into mediocrity. Our university's concert has its own myspace . That's right, a concert is "in my extended network". Unfortunately, in a web like that there is no room for this blog - Sayōnara, Adios, Cya! The codemonkey will keep thinking, but no longer blog. ...and, somewhere in the distance, one of the three readers of this blog said "oh". Edit: I'll still might occasionally post poems/lyrics/short stories, as CS isn't the best subject in terms of creative output....

In the unlikely event that an observer to this blog has remained a reader after the last few entries, and the long gaps between them, I present to you the blogvella "The Tale of Thuc, the first Wraith Dragon to ever talk to herself". Prologue: In a time not unlike our own, in a land not unlike present day earth, there lived a colony much unlike our own kind. Their kind flew. Their kind are exceptionally skilled in martial warfare and live by sucking the life from their prey. Their kind are Wraith Dragons , much feared for their telepathic communication and abilities in regeneration. Among this settlement however, there is one who has recently distinguished themselves from the others - one who has a talent unknown to the others, and who because of this evades their elders, instead spending time training themselves for battles among assassins, sourcerer and other rogues in far off lands. All of this because this Wraith Dragon - born to the name Thuc but feared by her enemies

OMG - Federbear! If you haven't seen any tennis recently, here he is checking out chicago: And here's one of Federbear blogging!: Ok, I have a feeling that I just lost my last few readers. Next blog topic, by special request - The Tale of Thuc, the first Dragon to ever talk to herself.

So, what does a programmer do when taking a week off? Program a website, of course! Well...I have been contracted to help out the Debating SA website, so figured I'd do some practice with a website of my own. A while ago, someone had come up with the idea of a fantasy stock market where 'companies' were TopCoder members, and their 'prices' were related to their rating. So here it is: http://padster.gyronet.org/tc/TCX/ With over 110 members, and averaging 2000 hits a day, seems like it's doing well :D The test will come just after the next SRM, the first time when share prices actually change. Back on designing - I've managed to somehow get 4 1sts in a row, so car insurance is covered! :D and soccer is back!! cool -have a good week all

Happy Bond Year ('007) to all! I'm not really one for resolutions - I figure, if something's good enough to do, you should not need the last digit of the date to change before you do it - but I have set a few aims for the year. E.g. getting a medal in the ACM finals, reaching a TopCoder onsite again, getting HDs for all my uni subjects {still not sure if the 84 will stand from last semester}. Another is related to my most recent aim - eventually getting a car. Currently aiming at one of these: Unfortunately, when getting an insurance quote, I get hit with a few additional costs due to being young, male, and not having driven for long (yes, that's on top of being young...). Anyway, the hope is to cover insurance from TopCoder designs over the summer - 22% done so far, still a bit of a way to go. The final resolution is to learn as much of Octavarium as possible - still a long way to go there too :p Ooh, and thanks to those helping bug-fix padster::gyronet tools {tag boar