Xmas / New Years

Firstly, a very happy 2010 to all readers. Not really a technical update this time, more just some pics from my first new years in Sydney. As some of you know, I was in SA over Xmas (shout-out to all those in Adelaide, especially those I didn't have time to catch up with) - which included two days away from phone & internet, a definite change from the usual Google life but a welcome relaxation nonetheless.

Then, back to NSW for two days of work and fireworks! This was my first ever NYE in Sydney, I've never seen the fireworks before so that's where I was headed. After finishing work around 6, I was headed to Rushcutter's Bay where some friends had camped out at a nice spot (Thanks Sophia et al!), as you can see in the picture, it included a view of the bridge, lots of grass to sit on, and not too far away from a few other fireworks sources too.

Some pics! Not too great because I only had a phone cam, but still, this is kinda what it's like: (second one is a test of Camera Tossing)

So that's about it, really short update this time. I'll leave you with the two most interesting drunk-stranger moments:

1. On the train home (always a good start...) a group of about 8 folks get on - I'd say probably late 20s, looking like they've had a few too many. They're talking loudly to each other but generally causing no-one any harm. Near the end of the trip, one of the more blokey looking guys turns to me & Katie and asks: "Hey...it's ok for guys to hug eachother, right? Guy's can do that, yeah?". After taking a little while to process the question and answer with a safe "...uh, yeah, sure" the guy then shouts down the other end of the train: "See Brian*, it's fine. Come on, give me a hug!". *I can't recall the guy's name, substituting with Brian instead.
2. About 30 mins after the midnight fireworks, we're in the middle of cleaning up and waiting for a large part of the crowd to leave. While sitting on a rug, Katie leaning next to me, some random drunk girl hugs me from behind, proclaiming: "Ooooh, you look lonely. Cheer up, Happy New Year!...." at this point is distracted by noticing Katie, and suddenly changes to "....ooh, you have a girlfriend...not so lonely then...have a great 2010!"
3. Bonus points to the courageous pair I passed on the walk home, who in response to any loud random drunken shouts of "woooo" or similar, would reply with "woooo....Binge drinking" in a really unenthusiastic voice.

Details, part 2

Editing

As promised, this is part 2 of the details of what I do at Google, on Wave - and that is working on the editor.

That is, the part that you type in / interact with when you're entering information on the page. When you compose an email, you're using an editor, when you modify a Word Document or write an SMS, you're using an editor. Likewise, when you create a wave and start typing, you're using an editor I help write (there are a few of us who work on it). So, what does someone working on the editor actually do?

Editing concern #1: Features

Wave uses a rich-text editor, which means we support font styles (e.g. bold, italic, coloured, sized, ..) plus allowing links, indentation, bullets, videos, images, ...etc. There are a few missing (tables, numbered lists, ...) so one thing we do is keep adding features as the are needed or seem useful.

Editing concern #2: Usability

Which leads nicely to another big part, getting the editor to work how people think it will. A simple example is things like shortcuts - if you select text and hit Ctrl-B, most people expect this to make the text bold. If you type in a right-aligned paragraph, and hit enter, you expect the next line to also be right-aligned by default. If you put your cursor inside a yellow word, and type, you want the letters you add to also be yellow.

Note that a lot of this is determined by researchers, for the coders it's often more the task of making it easy to customise - for example, if it's decided that, if you type at the end of link the new characters aren't linked (compared to typing at the end of a bold word and wanting bold characters), then we should be able to implement this without spending lots of effort.

Editing concern #3: Realtime

One of the strong points with Wave is that messages update as they type, so editing has to be able to take care of any situations that occur from these - for instance, what if you're typing and someone else deletes the line you're on, where should your selection go?

More importantly, if someone types a paragraph, say, 50 letters long, then the document you're viewing will update up to 50 times. If processing then displaying an update was slow, concurrent editing would be a huge pain - so there's quite a bit of complexity in our code to make sure that for each update, as little work as possible is done. By only updating the parts that have changed, the editing experience becomes much faster and smoother.

Editing concern #4: Internationalisation (a.k.a. I18N)

We're hoping that everyone around the world can use Wave - this means not just English speakers from US/UK/Oz/... but also those who use non-standard letters (e.g. the German ß character), non-roman characters (e.g. Cyrillic) right-to-left languages (e.g. Hebrew) and character-based (e.g. Chinese).

For at least the last case, it has added complexity due to the way the characters are usually written in editors - as you cannot get a keyboard big enough to have each character, they are entered as longer combinations of text, which needs to work in Wave. It just so happens that each computer type (Windows, Mac, Linux, ...) and browser (IE, Firefox, Chrome, ...) do things in their own way for these, which brings me to my last point...

Editing concern #5: Getting it working for everyone

Websites like Wave are viewed on web browsers - you currently are using one to view this blog, it could be Firefox, Chrome, Internet Explorer, or one of many others. Unfortunately, they all have their own separate quirks in how things work inside them, and we need to get our editor working in as many as possible (we currently support Chrome, Safari and Firefox). To add to this, the browsers themselves are programs, so they are changed or upgraded every so often, which occasionally break the way our editor interacts with them.

Thankfully it's becoming more standardised, but for now it means, when adding or changing behaviour, we sometimes must test all the different combinations, or add workarounds that are different for each browser type used. Fun...

But it's an interesting challenge which has and will keep me occupied. As my team recently blogged, we have now sent out more than a million invitations. Because editing is a part users spend a lot of time on when using Wave, it's possible that a million people have now used my code. Even if only 0.1% of those use a certain editor feature each day, that's still 1000 people per day whose editing experience I have helped, always a good feeling :)

For now, time to get adjusted to not having a long uni end-of-year break...

It looks like I'll be back in SA for Xmas then NSW for New Year's, see you then!

Details

I've realised that I've never actually said exactly what I'm doing here in Sydney, so thought I'd spend a few blog updates explaining it. So far, I've probably explained to the point of "I work for Google, coding for Google Wave", time to elaborate. Since I've started, my job in the team comprises mainly of two sections - Client and Editor - so I'll describe them both, starting this post with Client.

What is a Client?

In the Wave world, a 'Wave client' is something you use to view waves. For example, if you use Outlook or Gmail to view emails, these are both mail clients. As Google develops Google Wave, with it we have wave.google.com which, if you have an account, you can visit to log in and view/edit all you waves. This is our wave client - a website that shows waves.

What is involved in making the Google web client?

Websites are becoming more and more complex these days, building of a number of technologies - in particular:

- HTML is a language for specifying the content of a page. This includes things like text content, panels, images, ...

- CSS is a language for setting the styles of a page - stuff like colours, borders, layouts and fonts.

These two together are enough for static (i.e. non-changing) websites and many older sites were made of these two. As more dynamic content was desired, and extra functionality needed in sites, a third part became more widespread:

- JavaScript can be thought of as the programming language for websites - it allows you to define mini programs to change the html/css of a page, to grab information from elsewhere without reloading the site, to define complex actions on button clicks, etc..

I deal with all of JavaScript, HTML and CSS in my job, however they are not the most friendly of languages to use to develop large projects - thankfully, Google has a tool for making that easier:

- Java is a programming language growing in popularity for developing projects.

- GWT is a google toolkit for converting a Java project into a website made of JavaScript, HTML and CSS.

This is very useful as there are many tools that make writing and fixing Java code very simple, plus many useful libraries available in Java that others have written and can be reused. This combination (Java + GWT) is what I spend most of my time doing.

What do I do in the Client?

I am in no way the only Client developer - there are a number in my team, as our client is rather complex, does a lot of interesting stuff and in some ways is pushing the boundaries of what a website can do inside a browser. Other than editing (which I'll talk about next post), the main chunk of what I do in the client is the project that I was assigned when first starting at Google - the toolbar (see below). Along with this I help with some generic stuff (mostly hooking up behaviour in the right-most wave panel, but also some misc. behaviour, css/html, speed profiling, bug fixes etc..).

How come you're so slow at making a Toolbar?!

So, when I started, I was tasked with making the 'Edit toolbar'. Pretty simple - whenever in edit mode, we needed a bar of buttons to allow bold, italic, underline and a few other things. Within a week I got a really basic thing hooked up, and we started using that. Unfortunately, our need for buttons grew to proper customisable ones with configurable icons and possibly text, plus fancy overlapping separators, so the HTML and CSS grew more complex to accomodate. Eventually we needed users to add their own buttons, plus dropdowns for fonts, alignment, popups for links, etc... plus features like bold buttons displaying whether the current selection was bold, and the toolbar became close to what it is today:

Along the way, the requirement grew to add a normal 'view'-mode toolbar with buttons for actions you can perform on waves, complete with both icons and text, plus adding a toolbar to the search panel (in the middle) as well as a dropdown (the '...' below) that will show the buttons that are not visible if the panels are too narrow, plus later any options or buttons that aren't supposed to be displayed normally. And so, the edit toolbar and buttons were altered and the generic Toolbar was born, plus the More button:
The last toolbar that is currently in operation is the Playback toolbar - including normal icon-only buttons for navigation, plus the fun addition of a slider which again required updating button code to allow controllers on the toolbar. All the while, making sure it works properly in all supported browsers (Safari, Firefox, Chrome) plus looks fine in the small dropdown mode (as shown below) plus on mobile devices (iPhone and Androids).

And that's the current state the toolbar is in - most of the time is spent either coming up with nice generic ways of doing the actions across all browsers (e.g. when clicking buttons while editing, you want the editor to keep its selection, even though by default browsers all get rid of the selection on clicks), or adding in behavioural aspects (still to do is to display which font family/size/colour is selected, displaying menus when you click-and-hold, etc...)

Having said all that, despite the toolbar being a bit of a time sink for the behavioural aspects, it is nice to be working on such a visible and used aspect (plus pretty! Although I do none of that, it's all thanks to our talented UI designer), especially when Stephen Fry uses it!!!

Next week, I'll get into editing, and the miscellaneous other parts of the job (this week I've been primary oncall, which has meant two 2am and two 5am wakeups so far...). Til next time, happy Waving!

Launch!

So, it definitely has been a while since the last update, although I had always expected that due to the last bullet point in this list. In brief, what I've been occupying myself with includes:

• Mid September was mostly filled with work, mainly just increasing the stability of what I've been working on so people can use it for longer without it breaking...
  
• Near the end of September, everyone from Google visited the Hunter Valley for three days! They put us up at some vineyard/golf-course/retreat type place, some of the time was having meetings and mingling with the rest of the office, but there was also time for a pub trivia night, a wine blending & cooking classes lunch, a poker tournament (2nd place out of 30 or so!) and even laser clay pigeon shooting. An enjoyable 3 days, for sure. Driving up was also interesting, as it was on the day of the massive dust storm, so the entire way was red and dusty...
  
• Even closer to the end of September, I was lucky enough to visit Adelaide again for my Grandmother's birthday (special thanks to D-and-J of D-and-J Higgins for flying me over!). It was great to catch up with almost all of my closest relatives (including those normally in Victoria!), although that resulted in a very packed, albeit satisfying weekend.
  
• Then, right at the end of September (I guess technically 1st Oct here, but Sep 30 in the US) wave launched its "Consumer Preview". While still not a full open launch, we decided that we were basically stable enough, and with enough features, that we could open up to move to around 100,000 regular users. Users are coming in through an invite system designed to get collaborative groups on together, so currently we're growing at quite an amazing rate (and having all the fun related to getting many many more users :p).
  

So that's about it, mainly the launch has been what's kept me amazingly busy for the last month or so. It should be able to slow down for a little bit now (e.g. tonight I've just come back from a cruise around Sydney harbour with some Anita Borg finalists) and so I've had the chance to get my tax return in (first tax return the goverment has ever had to pay me! hurrah) plus boring stuff like car service and dentist/specialist stuff.

Awesome week & Lombard pics

I figured I just had to update this week after realising on thursday that I have it pretty nicely here in Sydney currently. What happened thursday, you ask? well..it started the day before with all Googlers receiving an army camo shirt and cap, and Thursday was paintball day! All of the engineers had an off-site, which included six games of paintball against the others in the office - including my boss! This resulted in lots of paint, spent paintballs, and even a shot to the neck from my new gf of a month, Katie - impressive bruises all around (which I still have!).

No, the more fun part came walking back into work AFTER paintball. Yes, I walked to work at 5:30 pm, in sneakers, a tshirt and tracksuit pants, listening to my mpp3 player and wearing a scarf so my welt was hidden. Why, you ask? Well, I had some stuff I wanted to finish early, but thursday is also they day where they have free beer and wine, plus free food after, and during which a few people from the office play board-games. So that was enjoyable, and after which I then also walked into timezone in town to practice some guitar hero arcade - because today (Sunday) there was a contest - came 5th, winning a free shirt and a $30 voucher (plus a figurine, meh, and soccer ball, for some reason...). So, all in all, a pretty cool week, hard to top any time soon!

Miscellaneous update 1, is that work is still going very well, and we now have a new target to aim at - 100,000 users by the end of september! eek...at least it's a bit quiet for now, but that'll change mid-september.
Update #2 is that my other lease on my old house has finally finished, which means bond back (once fridge is removed) and no more double rent! Which goes nicely into...
Update #3: long overdue pictures of my new Lombard St apartment! No, not the Lombard st in San Fransisco, but one in Sydney. My two new housemates are the afore-mentioned Katie Bell, a fellow Googler, as well as Greg Darke, a PhD student in IT at Sydney Uni. pics!
The first is taken in a park just outside - we're up on level two on one of those balconies. As you can see, it's part of a much large estate, so all the gardens (including weird tropical-themed walkway) are taken care of, and both Greg & I get our own car-park :)

Next picture is the view over the balcony! As you can see, another place I can see the centre of town from, which is nice - though this time much closer, and from the western side, so a short walk into work. And finally -


A picture of inside, notice Greg on the guitar and Katie on the drums. That's it from me, another update hopefully around late september early october after our work hunter valley visit, and 100k launch!

Picture-view

As promised, some pictures from my recent trip to Mountain View (MtV), California.
First off, a picture of what most of MtV looks like - I went for a long walk the second weekend I was there, and for about 2 or 3 hours, the entire trip looked like this:

Why would I walk for 3 hours, you say? Well, I needed the exercise (you don't get much in California, and with the food they serve, I feel I must have gained some weight...), but also guitars are much cheaper over there, I managed to pick up this! (A seven-string Ibanez 7321, have meant to get one for such a long time, finally I have one, and a coffin-shaped case to keep it in, which was fun getting through customs...)

Next up, what better to do with a group of programmers in the hub of Silicon Valley than visit all the geeky tech places, starting with NASA Ames:
As well as Apple headquarters:
and nVidia (plus yahoo, Xerox, facebook and a few others not pictured):
Nearby to work is also a tech museum, with a bunch things important in the history of computers (e.g. early Google machines, a Babbage difference engine, a Cray supercomputer,..) as well as an Enigma machine:
and the famous deep blue! (and before you asked, no, I did not play it...)
And finally, the non-tech part of San Fransicso; the drive to & from was fun (scenic, but also I ended up driving about 120kmph on the 'wrong' (=right) side of the road in an automatic Mazda 6), and in the city itself we managed to find this famous bridge:
And in case you were curious at the view up one of those really large spire pylon things: (for those playing at home, we ended up going exactly half way, then back again, so effectively walked accross it...)

But wait, there's more! Well...not on the trip-related subject, but I also recently found out that I won a University Medal for graduated students (I think maybe for honours students). 18 were given out this year, so it seems I might be able to be back in SA for one or two days to collect it, even if that means wearing academic dress again...

Next update will hopefully be soon, and about this house, after our house-warming this upcoming friday. Adios!

Text-only view

Firstly, I apologise for the lack of images - I've been unable to get my photos from my phone onto the work laptop I'm using here in the states, so the images will have to wait until I get back to Sydney before appearing here (but rest assured, they'll get here!)

Secondly, HAPPY BIRTHDAY to Emily, Gran and Dad for their respective birthdays on the 3rd, 7th and 9th this month - I'm sorry that I couldn't be in Adelaide for the weekend, but I hope it was fun!

Now, to update you all on how the last few weeks have gone - it's been crazy but amazing! So, I arrived in the US on Friday 22nd, and by that afternoon (US time, so effectively saturday morning) I was at the Googleplex! But not just at the Googleplex, I was actually setting up a machine, and within a few hours, writing code at the Googleplex. This trend continued into friday night, then started again for most of Saturday, Sunday and Monday - it was rather surreal, a bunch of us in a small visitors' area, making the finishing touches and bugfixes before our big thursday demo.

Finally, after the 5 or 6 days of changes, some press training, and numerous demo runthroughs, we were ready! Our team of about 50 or so developers (mostly from the Sydney office) all travelled down to San Fransico's Moscone centre, the location for this year's Google Developer conference, 'IO'. The Wave demo was the keynote on the thursday day 2, so we headed in our secret back entrance early, and what really struck me and a few other guys was the sight of attendees literally running to get seats up the front to see what we were announcing. You can check the video at the link in the post below, and I'll have a post all about it once I'm back in Syd, but in summary, it went really well! The reception has been amazing, just walking around IO and getting random people talking to me and the rest of the team - our youtube video is up to almost 2 million views in a little over a week, quite astounding.

That's about all for now, this week and next week are all just attending google training sessions, exploring around the HUGE campus we have here, and, of course, enjoying the Wave aftermath while trying to get our product stable, feature-laden and ready for a large consumer launch!

More soon, with pictures - Pat, Wave developer :)

Oooh, and for those that care about these sort of things, the Google share price is currently $444.32. On the morning of our keynote, it was $405.56, which means close to a 10% increase in stock price in the last week, and it's nice to think that at least some of that is hopefully due to my team - especially considering it was also a week where Microsoft announced the new upgrade of their competing search engine. And, for reference, the price on Feb 2 when I started was $340.57 ;)

Wave

Really quick update - the project I'm on at work has just been announced, so I can talk about it now! And hopefully will also be free more to enjoy and update you about my trip here to California, more shortly!

Update

It's official! My workplace has just been declared the #1 place to work in Australia!
Now, it's hard to say whether this is true, as I've really only worked at one place (well..maybe two if you count SAAB), but it is rather nice. The food is still excellent, we now have a new pool table, and I'm starting to enjoy the flexible working hours - recently I picked up some flu going around (NOT swine flu) and have been able to take a few days off, doing some work from home.

In the meantime, I've found out I get a three week trip to the US (providing the aforementioned flu thing doesn't get out of control)! All new fulltimers get to visit the homebase in mountain view for some training. Which means I'm out of sydney from 22nd May - 12th June, but also that I get to check out the famed Googleplex, complete with numerous cafes and even ball pit! I'll try to remember to take plenty of pictures. Apologies in advance to all those with birthdays in early June that I'm going to miss =(

Everything else going fine in syd - had diabetes and dentist checkups, everything looking good (except...yay! root canal. but only one), I might be relocating house shortly after returning from training, mostly due to cheaper & closer to work, just trying to arrange things this end.

I've been lazy and not taken any pictures this week, but instead, here's a video from a guy at work of what showed up over the harbour at work today:

Happy Easter!

Just a really quick update to say thanks to all those people I met up with in Adelaide over the easter weekend, twas a good (albeit busy) weekend. And to those I didn't see, apologies - the four days filled up faster than I had thought. I hope you all had a great weekend, and I might be back in Adelaide next long weekend (early June).

Until then, the next while will probably be rather busy again, so just a warning that responses from me may be a bit slow, but I'm still here! It'll all make sense eventually, I swear, but I can't tell you when :p

new Office()

(Apologies for the bad programmer joke in the title)

So, as promised, news this week from Sydney is all about the move to the new office in Pyrmont. It's a bit longer walk in every morning, but I don't mind it mainly because this is what it looks like - Firstly, our actual office. I'm on the sixth floor...that's right, there seem to be only five. Because mine is the small one up the very top, complete with balcony outside and large actual cafe, and the best views in the place!

If you're wondering what the view is like, here's one taken from  just outside the building, with a view similar to that out the window near my desk or out the balcony at the cafe. Notice the nice coat-hangery thing:
Now, it's true that I've been working quite late recently, apologies for being hard to get in contact with. After this week things should settle down a bit, but even now, working late isn't all that bad due to actual dinners served at work, plus the following view while eating dinner:

and this view on the walk home across darling harbour:

And that's about it for this update - not much else is happening, except maybe making another pumpkin pie (mmmmyum) and playing more soccer against ebay, now that we have a grassy area very close by. I've also booked flights for the easter long weekend, so anyone in Adelaide, I'll catch up with you then!

Moving (and shaking?)

To start with, just letting everyone know that yes, I did go hypoglycemic at work, but received some glucagon quickly and am now back to normal, and have arranged a slight insulin adjustment with a local specialist who I'm seeing again in a month.

But on to happier things - firstly, Kensington. It just so happens that my place here is within walking (and hearing) distance of the SCG, which was rather fortunate as on saturday the Sound Relief concert was held there, so saturday involved waking up at noon with Coldplay coming through the window, and having dinner to the sounds of Jet. Then sunday came complete with amazing sunset:
We also move Google office this weekend, to the new location on the pyrmont side of Darling Harbour - but with views of the bridge, I am told. I haven't seen it yet, but things to look forwards to include a huge cafe kitchen (as in, actual chefs on staff i believe), themed rooms like the treehouse library (although, the theme near me is apparently 'dunny and algae', not sure why...) plus having an actual desk next to the people I'm working with. Pictures of the surrounding area shall hopefully be added to this blog in the next few weeks.

Having said that, I have a feeling the next two weeks will be hurrendously busy for me due to some pending deadlines, so apologies if I am hard to contact. Preempting this, I decided to try something recommended by an American friend...pumpkin pie:
And after the amazing success, it's my new #1 thing to make (maybe I'll prepare one over Easter if I'm in Adelaide and have some victims to try it on) - so it appears vegetables can be used in desserts.

The last picture is just a small aside as to what happens when you try to copy Ikea and have instruction manuals with no words. You get cute little steps like this one, I'll let you decipher what step 4 does...

Merch!

Really short update, just to say something excellent arrived in the mail:

Pegasi merchandise! Not bad quality if I may say so myself :) Nothing else too interesting happening over here, more from me when it does. I hope all is well for the two or three people reading this :p

Another day at the office...

Ok, firstly:

• I was not responsible for Gmail going down worldwide
  
• I was also nowhere near Castlereagh street when it started falling apart

Just thought I'd clear those two up :)

Thanks to everyone who's emailed/chatted/sms'd/commented/facebooked etc. to me over the last few weeks! I apologise if I've been slow replying, things are still a bit busy around here but thankfully that's starting to ease.
So much so that I even made Jam scones and pancakes last sunday:
As you can see, unfortunately I only realised after making the batter that the frypan wasn't non-stick, so instead had to improvise a bit with a pan.

But the food here is certainly going well - lunch at Google monday to friday, and dinner around town or in my large kitchen. All I need now is some sort of exercise or I might come back from sydney a bit bigger :(

It must be said, the sydney-cbd lifestyle certainly does take a bit of adjusting too. If I had to sum it up in one word, I'd say: corporate. People in suits everywhere - some days I walk into work going down Martin Place, and it's amazing the number of office workers in suits that continually are commuting up and down there (I haven't yet stood outside the seven office and looked in to see Kochie just yet though...). To see the big head offices of so many large businesses is kinda cool - some are styled in a really old-fashioned way, probably because the buildings have been there for ages (it's amusing to see the old sandstone banks just like they appear in movies), but more impressive are the new ones - especially fashion places (e.g. Prada, Armani) and also Apple: Another thing I learned quickly was that Sydney drivers like using their horns (a LOT - I was honked at twice at an intersection while the light was red, simply because the driver behind me wanted to turn left on a green left-turn arrow while I was going straight...) and that pedestrian crossing lights are completely superfluous - the average commuter won't pay any attention to them at all, and simply cross when there's no cars close by (or even when they are close by, in some cases).

Finally, I have to say that I'm rather glad I'm working where I am. Despite the number of people who come to work at 11am and seem to not leave until 11pm or even 1am, it's amazing to come to work and feel like you're seeing the future of the internet - not only all these things about how the world is operating (e.g. search query statistics, how maps or gmail work) but also what it could be like in a few weeks or months time, chatting to people about future Google projects that haven't yet made it into the public, or in some cases, haven't even made it to more than one or two googlers yet. It's also nice to know that, if you do improve something, then based on the number of google users, whatever you do will (hopefully) be of some use - albeit also picked apart and commented about on blogs, but hey, hopefully they say nice stuff. Then there's also stuff like this:

The new place

Ok, so here goes, a brief pictorial overview of my situation in Sydney, starting with my new place (appearing mood-lit at night). My place is the window above the one with the light on:Next up is the view from the kitchen window. Just to the right of centre in the picture you can see Sydney's centrepoint tower, and between here and there is trees:
From the back balcony, you can see a local golf-course. There is also a nice view out my bedroom window...I'm not sure what town that is, but again, lots of green in the view:
Next up is where I'm working - the Google office I'm in is 11 floors up in this building, on the corner of Market st and Sussex st. Right now, I also sit at a desk right at the corner of the two side visible in this shot, so I get a pretty good view:
As it happens, just to the right of my screen, I can see pretty much this (just a bit smaller due to being 11 floors in the air...) - which happens to be the sydney aquarium to the right, the national maritime museum on the left, and some of its fancy boats in the middle, parked in Darling Harbour:
As I said, I'm on the corner of the office for now, so if I stand up and crane my neck a bit, I can look down to also see something like this - more of darling harbour:
I should add, on my first few days I was staying at a motel in Randwick, and as all the realestate agencies were closed on Australia day, I decided to take a walk - I think this one is Gordon's bay:
And this, of course, is Bondi! It was a bit overcast that day, but at least there were no sharks...:
That's it for the picture guide, but expect more info to come soon!

It's back!

After a long thesis-finishing hiatus, including a relocation to NSW, the codemonkey blog is back!

Now that I have net access, and am starting to settle down into the working-life routine, I hope to keep this updated with what's happening here in sydneyland. Stay tuned!

Ambidexterity

Recently, I've decided to upgrade my old Squier Strat for a 7-string Ibanez 7321. The strat is about 4 years old, so decided to give it a clean, which included a complete restring.

Now, a bit more background - I'm an avid Guitar Hero player, quite good, but can't really bring myself to play it often enough to be among the top league of players. Plus, it's not really very popular here in Aus, so while I've won beer and an IPod from T, I doubt i'd be able to earn much more. It's still fun though, so I figured I'd use the opportunity to learn a new skill - ambidexterity. You see, there's this option to play 'lefty-flipped' = everything reversed, where you strum with your left hand, and fret with your right.

I'd never noticed until I tried, how hard it was at first. You see, while it was easy to think what you should do, muscle memory inevitable took over. When playing normally, you always fret (left-hand) slightly before strumming (right-hand) so you're holding notes down before you hit them. Your left hand naturally learns to move a bit before right, so when you flip, suddently you're strumming before notes are held (= bad). Similarly, transitions between chords with the right hand, or simple strumming patterns with the left, would suddenly be much harder.

Which leads me to think that hand preference is more a thing of repeated action, than actually being better at one. You see, I began practicing in such a way that mistakes weren't tolerated (that is, starting by just finishing expert careers, but now aiming at 100% for expert songs, so far acheived on two of them! :D) and my progress isn't too dissimilar from playing normal-handed.

Now back to my original story - I decided to restring it flipped, with the strings in reversed order, to try to learn to play normal guitar flipped. I already know all the theory, tis just a matter of muscle coordination, so hopefully by next year I should have it at a reasonable stage :) At the moment, strumming still feels kinda odd, and my right hand feels strangely inflexible, but Wonderwall is starting to sound ok :) But yeah, in short - ambidexterity is a weird thing, it'd be nice to be able to use either side equally, and although it seems hard at first, practice does seem to help a lot...maybe it'll come in useful one day.

Note also that it can be quite odd - if you try to write left-handed, it's much easier writing the letters correctly than writing them as mirror imaged, I'm guessing in this case we remember the visuals more than the muscle movements. However, some things are easier to do wrong-handed when outright flipped.

In other cool news, my indoor soccer team won our grand final! That's two seasons in a row, especially good this season as we only just made it into the finals themselves, never expected to do that well, and it's also my last full season here in SA (...for a while, at least). Secondly, a Melbourne uni team of coders recently won our ACM regional - I was hoping these three would win, they've all been taught in the high-school program I help with, and what is more, check their team name! :)

Holidays on now, which means honours talk soon, and lots of thesis writing....fun....adios for now!

myTunes

So, happy September everyone! The following is the usage stats of my site for August, each bar representing how much data was downloaded from it per day by visitors:
The lowest horizontal (i.e. about day 1's total) is roughly 80Mb/day, which I used to be happy to hit - that translated into about 50-75 listens per day on mp3 sites. Then it kinda slowed down, and I thought I was in for a slow month...then August 24 happened, and BOOM. I mean, some rise was to be expected due to the end of the Olympics, especially as my listeners mostly seem to come via a chinese-language site, but still - almost 250Mb/day. Strangely, the # listens doesn't seem to gave grown much, people are just listening to songs for longer it seems. I've also had a number of odd referrers (= sites people get to mine from) include a few spam, one that looks like a ringtone site, and another apparently from ninemsn :S Maybe it was after the 20th = Pegasi's first gig, but either way, hopefully it'll keep up!

On the topic of music, and gigging, we received feedback on the performance. Most was good suggestions, stuff expected to be said about a band at their first gig after being formed for 3 weeks. However, a few things said - although not surprising comments - did kinda annoy me. They were - (1) The guitar playing was 'too complex', (2) Not enough hooks, (3) Stick to one genre, and (4) The song structures were too unusual.

Those who know my music tastes will know my #1 band to listen to, almost exclusively, is Dream Theater (with Fastball high up for their composing skills). Lets see some of the reasons I listen to DT and shun most other music:
(1) They're skillful - most parts are amazingly complex, yet still appealing to the ear (e.g Overture 1928)
(2) Most songs don't have catchy hooks, instead almost all notes and lyrics are important (e.g The Great Debate)
(3) Their range of songs is diverse, newer ones especially are not repetative (e.g. Constant Motion vs. Wait For Sleep vs. Endless Sacrifice vs. I Walk Beside You vs. Never Enough)
(4) Structures are rarely simple, with guitar/keyboard/drum fills and unusual time signatures added yet still sounding great (e.g. Honor Thy Father, Forsaken)

Not that I don't think the judges are bad for putting that feedback down, but it certainly is the way of the industry now to have repetative songs, whether inside the same song - i.e. lyrics repeated over and over again, the same riffs played CCVCCV, e.g. The Veronicas new 'hit' - or between songs by the same group [e.g. i have to say it - Dragonforce], or worse, songs that sound like songs already out there [*cough* I'm looking at you, Rogue Traders and Kid Rock].

And that's not to say that the artists themselves are to blame for this, it's just business. Instead, for me it's the consumer who wants 15 seconds of catchy song, either for their ringtone, or to appear on an ad, or simply because a four-minute song is too long to listen to...(*points at DT's Album/Song, Metropolis pt. 2*). So once you write your catchy, yet musically vacuous 15 seconds of hook, the next step is to play it over and over and over and OVER again, add some drum track, and dance around a bit. If you're already famous, you get some radio play, and because your hook is played 12 times per song, it'll get stuck in everyone's head! Meanwhile the musical intellect of the average listening is in a skydive.

Revolt against the dumbing down of our musical culture! It's time for a new style, where songs have over 1 minute of non-repeating sections, where lyrics and verses ACTUALLY MATTER, and where minor 7ths, suspended 4ths or added 13ths can roam free, safe from the threat of power chords!

Time's a curious thing

Ever look back on yourself five years ago and think how silly you were back then?
Whether it's a memory of screwing up a question at a quiz night, or finding a guitar song easy that I remember having trouble with, or looking back at old forum posts thinking "uhh...I actually said that? What a fool!", it's amazing to think of the changes over the last five years. And even more scary, wondering whether, five years (and probably 4 blog posts) from now, I'll think the same thing looking back '08. If so, I'll be one odd fellow in '13.

Anyhow, onto non-me topic: Time.

I'm not sure whether I've written it here before, but it is still my idea that, as we are all still here, if time travel were possible, it'd only be used by socities who can utilise it safely without any paradoxical activities. This also means that they don't travel to any societites for which this is not the case - including us. And as it seems to me we're a long way from maturing enough, it will be a long time before we can hope for time travel (if it is at all possible, maybe not), so don't hold your breath. I mention it now because I recently heard it was a theory that travel might be possible, but would require the correct technology at both ends of the trip, which has a strange parallel to my earlier idea.

And a second brief point:
Question 1: Do you think that time can go on forever? [e.g. there's no point where time will just stop]
If no: Q2) How will it stop, and what will cause it? { 'Time travel paradox' would be a cool answer :D }
If yes: Q2) Can time extend backwards forever?
My initial reaction to Q1 is "yes", and so now i'm thinking my reaction to Q2 is also "yes". It's often wondered how time began - Big Bang, Creation, etc... but it's not often considered *whether* time began. I can't think of any reason why it really needed to? Sure, if you keep going backwards, then entropy keeps decreasing, but it's easy to be bounded yet always decrease. Maybe there was no start of time. something to think about :)

Communication Breakdown

Kudos to anyone who got the Led Zeppelin reference in the title.
Anyway, this is a semi-rant over something that has started to bother me recently, but looking back I realise it's actually been happening for a while, just has increased over the last while so is more noticible.
You see, verbal communication (i.e. speaking) is great for getting whatever is in your head into someone else's, for sharing your thoughts with others. Thus it intrigues me whenever people say something vocally, yet then act in a way which completely contradicts their sentiments. As they say, actions speak louder than words, and I tend to trust body language/actions as how someone truly feels, moreso than what they're saying, for this exact reason. Is it truly that hard to say what you mean, to mean what you say?
The first question from this is: Is the contradiction intentional? Or are people just so unaware of themselves that they don't realise they don't agree with what they're saying? My guess would be the last one, just that if people really are that unaware of how they're feeling, and vocalise the opposite, then it truly is worrying. One thing that keeps a society functioning is accurate communication between people, so it'd be nice if you could trust what people said - while that is far off, it'd certainly be nice (and should be possible) to trust what people said about themselves...
Second question - Why is this happening? The first thing that comes to mind is the same cause as many problems nowadays: thought laziness. People are getting away with less and less deep thought, that reflecting on how you feel is apparently too hard, it's simpler to say the cliche that comes to mind first, which fits best, and others will be happy with, even when it's not true =(
The other reason which strikes me is egotism. Why? Well, verbal communication sends messages to others, and usually they act on these messages. If you actually worried about others reacting to what you say, then you'd try not to mislead (I would have thought...I guess I'm wrong). Instead, what happens is communication breakdown, people react but to the wrong thing, and that's when problems begin...
One final reason, which would be awesome, is that everyone is aware of what they feel, say and do, and the differences are to make things more interesting. Though based on how complex interaction is, I seriously doubt it.
Final question - Is it a problem, and if so, what can we do about it? My answer so far is: Yes, and I don't know. Personally, all I can do is try best to mean what I say, and try to get really good at body language :p
Mindless thoughts, thoughtless minds, to the heroes it's obvious, it's time to be leaving town...

On random non-sequiturs:
National Campus Bands Concert is on at Uni soon, maybe the first gig for the Pegasi?
And skiing (well, more snowboarding) was cold, expensive, but awesome!
Coming back was confusing however, when I found my supermarket had weird discounts:
-) 2L iced coffee cheaper than 2L plain milk
-) Packet of 20 chips cheaper than packet of 15
-) Softdrink cheaper per litre if bought in 1.25L than 2L bottles
Oh discordia...

This is not a blog post

Recently, an early painting by Monet was sold for $80 million, not bad for something that was bought in 1971 for $320,000 and hasn't been seen much since. The worth apparently comes from it being an example of what he'd later work on, so the moral of the story seems to be: If you think you're going to become famous, don't throw anything out...

Anyway, thinking about art and walking through uni, I noticed Magritte had come to Adelaide:
(for those who don't get the reference, check out The Treachery of Images)

Otherwise, no new music due to exams, and skiing for 2 weeks soon, but afterwards I'll start some predictions posts - and maybe, due to being very un-impressed with what is playing on the radio these days, actually do the song-in-a-day/week project to see what comes out of it.

More Beans

First up, I recently found out that my second-last blog entry 'Beans' did rather well in the contest it was written for, in fact coming in the top 10! So many thanks to Bodie for helping with the eloquence, and to all the folks running the NetBeans contest.
This is only a short entry to let readers know that I've managed to get myself a job at a little-known website company who have an office in Sydney. Which means moving at the start of next year, and making the most of Adelaide until then (hopefully I'll be able to come back on some weekends too).
Speaking of which, my band should soon have a name, and once a permanent drummer is found, the next step is finding gigs (probably some time after ski-trip in the mid-year break) so I'll keep you posted.
Oooh, and the most recent TCO just finished, congrats to the winners and JD on his 4th place (competing in style wearing sunglasses). Until next time, adios!

Black Parade

I'm starting to really love the walk home at night - so peaceful, so scenic, I'd strongly recommend it, you're welcome to come along some time but the most creativity comes from doing it alone while tuning out the rest of the world.
On the way home today, the result was this, influenced by My Chemical Romance's Black Parade:

To those who stand alone tonight -
beaten,
broken,
unseen by the eyes of others,
with unheard voice projected from unappreciated lips;
undervalued,
overlooked
yet still running the gauntlet -
Know that we're standing here with you,
beaten together,
broken together,
united by this humble existance.
We'll carry on.

In other news, due to 88Mb on the last day, plus new recordings, padster.gyronet.org managed to serve 1 Gb last month. As I write this, it is 3 hours into gyronet's March, and the old 'Final Goodbye' mp3 has had 39 hits already, and the new 'less ordinary' is on 17. Kinda makes me wish I could play full time once uni has finished, but this is unlikely.

Beans!

Amazing news in from Microsoft:
That's right, a P2P chat application with NO code written by the user at all. I was struck by two thoughts - (a) Is Microsoft just telling a big fib, and (b) is it a good thing that P2P apps can be written with no code? Having recently downloaded the NetBeans 6.1 Beta IDE to help with some Java GUI, I decided to test this out...so channeling the reviewing style of Jeremy Clarkson and simile generation of Zero Punctuation, welcome to my first ever IDE roadtest:

Can NetBeans create a code-less P2P app?

Armed with only NetBeans 6.1 Beta, a little plastic ball of mouse in my right hand I can start this java experiment ‐ while my left hand is free to go off and make itself some coffee, play golf with Donald Trump, or really do whatever it wants now that it's not required to write any code. I foresee it could soon become quite the socialite.

The first step is upgrading my old NetBeans 6.0 to the new 6.1 version. Unfortunately, 'upgrade' here is a euphemism for complete reinstall, or 105Mb download for the J2EE users. While this isn't a major problem, the long wait does put the new version under as much pressure to impress as a Rock band releasing their second album.

Anyhow, with the download over, install complete, it's time to start the coding drag-and-dropping for our chat program.

Step 1) Database
Needing somewhere to store our chat data, I decide to take the Schwarzenegger-Humvee approach and get out the big guns, creating a codeless database. Thankfully, this is pretty painless in NetBeans, it's all there under the "Services" tab. After starting the Apache Derby DB server, I can "Create Database...", then expanding the tree allows me to "Create Table..." to store my messages:
and with that, the table is created with as little effort as it takes to find a Starbucks in New York.

Step 2) GUI
Now, creating the actual app project goes something like:
File -> New Project -> Java Desktop Application -> rename to "P2P" and select "Database Application" -> Select the newly created database table -> Include the both columns -> Finish!
Step 2.5) Bling
I must admit, that was easy and quick - and so is a Concorde, but they're both kinda ugly at first, although this GUI isn't French. Thankfully, changing colours and rearranging forms is still a codeless, right-hand-only job, but as a programmer, I decided to bring the art to the code, and make something Piet Mondrian would be proud of:

Step 3) Running!
So, having reached this far only requiring the coding knowledge of the average Big Brother contestant (no Java, no SQL, and not really English required) it's time to test it out chatting to myself. It's the standard click-the-giant-green-triangle trick two bring up two versions of the app (both of which are happy to compile & run no problems). And Voila! - a functioning P2P java app, about as useable as credit-card-cutlery, but it involved writing no code at all.
The only thing that was missing was needing to manually refresh to see new messages - it'd be cool if you could drag a timer onto the form that you can set up to call an action every K milliseconds, however I still consider this mission successful! No picture here, see above for the running app.

Step 4) Line-of-Code metric
A few quick asides: programmers often get paid by lines-of-code. In this project, I wrote zero lines, but inside the project folder running: cat `find . -name "*.java"` wc --lines tells me this app is 804 lines long! That translates into an impresive 500 words-per-minute...
Actually, let's boost that a bit by generating the javadocs too. In NetBeans, that's as simple as Right-Click P2P -> Generate Javadoc and after some thought, it spits out a pretty website:
To find out how many lines of html are generated:cat `find . -name "*.html"` wc --lines gives 5720.
This little Worker Bee has generated 6524 LOC, which is more lines than even the Rolling Stones did in their peak. 267684 html and java characters in 30 minutes is a staggering 1750 wpm, time to brew some real java beans I think.

Step 5) Conclusion
So there we have it, a brief demonstration of the current state of code-free coding. I must admit, I'm more of a DIY coder who'd prefer setting up the butterfly effect to write my code, over having it fed to me one Java Bean at a time, but I'm also aware (and thankful) that not everyone feels the same way. With the learning curve for Java GUIs about as steep as petrol price rises before a long weekend, I guess it's kind nice to think that P2P applications can now be written with little programming experience. Which oddly reminds me of MSN messenger again...

Edit: font sizes fixed, apologies - hopefully blogger won't overwrite them again this time.

Quotes

Random update....
My indoor team The Blues (now Team Judas) just won our division indoor grand final, in sudden death extra time :)
Twas much fun, and now we have 570ml glass steins :)

Anyway, I shall have an update soon for the net-beans blogging contest, but until then, here's some awards:

Maths lecture quote of the week - split between:

"Let a and b be in A"
"F is algebraically closed if F is algebraically closed over F"
"It shouldn't surprise you that the number 2 features prominently in this, as there are circles happening"

F1 commentary quote of the week:

"You can see the tyre mark there on the top of the wing"

Randomly overheard quote of the week:

"So that's when I decided to never again wear a backless dress cut that low"

SMS of the week:

"Hey Pat, do you have Andrew's number? My phone fell into a toilet"

Reaction of the week:

"aaaaaaaahahahahahaaLOOKheheheheIT'S LEGShahahahahahahahaARE TINYaaahahahahahaha"

And that's it for now until the netbeans blog. There's also a Guitar Hero contest at uni soon (fingers crossed) and some of my songs now have bass parts and getting very close to recording, so stay tuned!
P.S. I shall be out of SA from 14th - 24th of april, but in sydney so should usually be in Email+Phone contact.

Creativity

First post for '08 - before rant, quick summary: Music / Reading = going well, Work/Coding = not so fun, but earning enough to take a long break soon :D Uni's looking like it'll be good.

Anyhow, I'm up to book VI in Stephen King's Dark Tower series, and just attended a (very awesome) Dream Theater concert, so enjoying the creativity in this world when I noticed something odd. At work, I was looking at how to add multi-language support into an installer (as you do), so googled "I18N Setup Project". Here's a summary of what I found:
1) A thread on a forum eggheadcafe by Norman Diamond: "My C# code is I18N'ed by appropriately naming and editing .resx files. At execution time, it works. ...(snip)", with a response by "Johannes Passing" and a final comment by Norman again.
2) A thread on google groups with the same question by Norman, answered on a different page
3) A thread on microsoft.com from a discussion in 'microsoft.public.dotnet.internationalization', with Norman's identical question, answered by Johannes and replied to by Norman.
4) A thread on thescripts.com with Norman's identical question, answered by Johannes and replied to by Norman.
5) A thread on developersdex.com with Norman's identical question, answered by Johannes and replied to by Norman.
6) A thread on techtalkz.com with Norman's identical question, answered by Johannes and replied to by Norman.
7) A thread at pcreview.co.uk with Norman's identical question, answered by Johannes and replied to by Norman.
etc...
If it only the question was identical, maybe it could be just Norman really wanting an answer quickly, but as the responses are identical too, they must come from the same source.
Sure, there are some other results, but as you can see above, it's by far mostly the same 3 posts.
The internet is a global community, with the potential to assist unknown creativity and collaboration, where search engines are making information easier to find, do we really need such blatant redundancy? What is worse is that most of the sites make it appear as though the information was posted on their site. grrrr.
Time to make up for it by reading a few creative webcomics and composing more, adios!

Plans

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 do it. Things on the the to-do list for next year (in no particular order):

1. Recording Asturias on my 12-string neck of the new guitar. It sounds awesome on 6 strings, but twice-as-fast on 12-string could be magnificent if played correctly. Much practice to do on that first though.
   
2. More composition, either writing new songs or improving (and, hopefully recording) the ones I currently have written. Might need to organise a band at some point...
   
3. Finishing reading the Dark Tower series. This is a great epic tale, which I have 2.5 books left to finish, so it could take a while but shall be worth it.
   
4. Come up with a music search engine algorithm. There isn't a good one yet, and there should be. Unfortunately, this is more the level of 3 years PhD study rather than 3 months working 'for fun' at night, but I'm sure it's doable, just with time...
   
5. Keep up designing / reviewing for TopCoder. This weekend I've had one design, two reviews, and one design-related project, so while the pay is good, it leaves very little time for anything else. Might have to slow down on this front :(
   
6. Go out more. Pretty self-explanatory really.
   
7. Upgrade some of the websites I've written. One in particular I have many ideas that will fix many design flaws and make it much more usable, though there's a lot of implementation behind it required.
   
8. Oh, and of course, do honours. Looks like something in Category Theory, though not really sure what yet, I'll find out next year.
   

So that's what's on my mind currently. I have this bad habit of doing waaay to much, and hoping my abilities can help me get it done well and quickly, and being disappointed if I don't get something done (because, I mean, I can, and some things not everyone can, so I'm letting myself or others down if I don't at least give it a shot....right? I believe that's my reasoning). Maybe I should try to fix that, or stress/work levels will build too high.
Looking at the list above, my guesses at what will happen is:

1. I'll try a bit but won't practice enough to get good, though hopefully will at least get it you-tube-able.
2. Nothing will happen on this front, as usual :(. Maybe a bit during pre-exam procrastination, but that's about it.
3. Definitely will happen, once uni goes back and I take buses
4. In line to get dropped first. It'd be awesome, I have many ideas, but the time commitment is just waaaay too big :(.
   
5. Might do some stuff for tournaments. Every time I think I've earned enough to take a break, another tournament comes up, so I might sit the next one out, although usually some good reason not to also comes up (this time they're inviting 12 rather than 8 people, the time after that is my last collegiate one, and could be my 5th onsite in a row...). Plus might need some more money for other reasons, see below
   
6. Hopefully this happens. Not too much, of course, I'm not a party person, but at least more than currently. If I plan on moving away from SA at the end of 2008, I want to enjoy my last year here.
   
7. It'd be cool if this happens sooner rather than later - I'm hoping to free some time up over the Xmas break and during the slower times at work for this, but it does require a lot of coding, so maybe will be pushed until honours starts, if at all.
   
8. This is definite, can't wait - as above, I'm really hoping I can find something new and useful to prove, as otherwise I'd kinda feel I could've been spending my time doing something else more useful.
   

The other news that affects a number of the things above is I might be moving out into a rental place with my sister early next year. Just figuring out the financials, logistics etc... but being able to have ppl over, not having parents who complain when I return after midnight, and being closer to uni & work would all be nice. So I'm still thinking about it, I should have decided by Xmas...
Other than that, current mood is contemplative and content :) Pat out.

Mr Thomspon's Problem

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 would have been excellent if all sum numbers were odd. Why? Well, if two numbers sum to an odd number, one must be odd and the other even. This means every edge in your graph is between an odd number and an even number, making it a bipartite graph. The maximum-matching algorithm for bipartite graphs is simpler and more known, so probably more appropriate for this level of contest.

Apologies that I don't have code for this one, as it's too much of a standard algorithm to re-write. If you're interested in an implementation, funnily enough it is inbuilt into the popular 'boost' C++ libraries [which you can't use in the ACM :p] - for details, see this which further illustrates how standard this algorithm is.

And that's all 9 problems, hope you enjoyed it!

A Fitting Advertisement

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's where problem 2 lies - Rather than removing zero-area rectangles from the input, so that contestants would only have to solve the problem they were given, it was for some reason decided that the problematic input would be kept, and instead the question changed, the changes then had to be broadcast to all contestants. weird :S

Oh, and to make it a bit worse, no limits were placed on how many rectangle queries there were. This does make a difference, as if there are many per histogram, it's best to pre-process the grid in O(400*1000) then solve each query in O(1). However, I'm guessing the number of queries is low, so instead, an algorithm that should work (though is as yet un-judged) is:
For each X-by-Y rectangle, see if it fits either normally or rotated as a Y-by-X rectangle

To check if an A-by-B rectangle fits under the histogram -
find the longest section with height >= A, and the longest section with height >= B in linear time.
If the former is >= B, or the latter is >= A, the rectangle fits.
This gives a complexity of O(#queries * width of histogram) and quite small to code - implementation can be found here.

Automatic Marking

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 less thinking and code.

Also, as the tree validation is given in the problem statement, the only new 'algorithm' that must be devised to solve this is how to parse the tree itself - as with many parsers, a good approach is similar to state-based, where the input is read as a stream (character-by-character). In this case, the 'interesting' characters are the brackets, between each pair you can parse a node and add it to a queue. Once the stream is finished, you work through the queue, linking up parent nodes with their required number of children. [Note that what they call 'level-order traversal' isn't really the nicest way of representing trees, pre- or post-order is much easier to parse, yet I guess it was used to make this harder]

Another gotcha with this question was how the children's values could be less-than-or-equal-to their upper bound, which makes things a bit more fiddly again.

Implementation of the idea described above can be found here.

Challenging "Butts"

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 extremely so if you're doing a contest where you don't get immediate feedback (like the IOI or TopCoder).

The proof itself is quite nice, and has the added benefit of making the code very short. It comes in two parts.
1) If the number of sectors is even:

Because it's even, you can add a checkerboard pattern to the zones as seen above, and always you will get a purple next to a pink at each border. Now, say we assign the highest values to the pink sections and the lowest to the purple, all of our border differences will look like |high_i - low_j| - i.e. adding the absolute difference will always result in a high number being added, and a low number subtracted. Because each zone is adjacent to 3 more, the overall affect is that each high number is added 3 times, and each lower is subtracted 3 times.
Two things about this configuration:

• Maybe surprisingly, it doesn't matter at all where you place the high or low numbers, so long as you alternate them! this means that most greedy solutions will work for these boards.
• This is THE best solution - anything else will result in at least one high - high and low - low border, which would be worse than that solution above. If there are 3N absolute differences, then 3N numbers must be added, and 3N must be subtracted, so you can do no better than adding the highest and subtracting the lowest.
  

This solves the even case optimally, we can use the observations to now solve it if:
2) The number of sectors is odd:

The interesting part happens now in the hilighted zones, where we are forced to have high-high and low-low. If you think how this changes our original answer, it means that the lower of the two highs has changed from being added, to being subtracted from the total, and the higher of the two lows is now being added.
That is, we've gone from (higha - lowa) + (highb - lowb) to (higha - highb) + (lowa - lowb), in other words, previousAnswer - 2 * highb + 2 * lowA. As this is the only difference, it's clear that the high value to 'demote' (i.e. highb) should be the lowest high value, and the low value being 'promoted' (i.e. lowa) is the highest low value.

Implementing this small fiddle then completes the formula for both even and odd sectors, and using some inbuilt C++ functions, we get an implementation that looks like this. If this question had a moral, it would be that it often pays to think more, allowing you to code less [which is why I liked it]

DNA Chopper

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 lowest number in the queue) - code that implements this can be read here, and is a reminder that even hard ACM questions can often be solved in very little code, even without obfuscation.

It seems this was not the most common way to solve the problem however, and judging by the input bounds of 15 numbers, it seems it was not the inteded solution either - I'd be interested to know if the problem writer knew of this approach.
Anyway, with 15 numbers, another method is to perform a DP solution, where your state is a bitmask with a 1 for numbers you can use, and a 0 for those you can't. cost(mask) is then the sum of the numbers you can use, plus the minimum value of cost(submask) + cost(mask - submask), where submask is a subset of the values you can use - e.g. submask | mask == mask.

If you memoize the values for each mask, you get a complexity of about O(2^15 states * time-per-state) where time-per-state is between 2^14 and 1, but on average small, and apparently with optimisations this passes (just) under the timelimit - although much slower compared to the O(n log n) queue solution.