Tag: algorithms

Let’s learn algorithms!

Posted by – February 2, 2019

In Scala, of course… a new series of articles begins

Back in the day (circa 2011), I cut my teeth on Java participating in algorithm competitions on a site called TopCoder. There was a cool little applet you would download, and you used it to navigate problems, enter your code, run tests, check out other people’s solutions, etc. I wrote a parser for the problems in the form of a Swing application that would spit out fully formed Scala test scripts and code templates, which allowed me to tackle the problems in Scala as well, which was rather neat… if I say so myself. I wasn’t very highly rated, and by “participating”, I mean mainly tackling the problem sets post facto in my own sweet time, but it was good fun, somewhat addicitive, and a way to keep the coding skills sharp. I must have done hundreds of them.

Well, applets went out of fashion, and TopCoder went into terminal decline (they have their problems on a website now, but it er… doesn’t really work). Fortunately there are a bunch of similar sites that have sprung up in the meantime, one of the best of which is CodeForces. Its interface is a bit less friendly for JVM programmers (everything’s done in strings via the standard in and out, which requires a bit of rather tedious parsing and formatting kerfuffle, rather than filling the gaps in a method with a provided signature and return type), but it does support a wider range of languages including Scala, and some more “out-there” ones like Rust, Kotlin, and Node.js. So I’ve been playing around with those competitions lately instead.

Now I seem to do okay on the easier problems, like the ones tagged “brute force” or “implementation”, but I’ve been struggling a bit with the more advanced ones, for instance requiring use of data structures. One that had me scratching my head recently required the use of a “segment tree”. Since you don’t get to use any libraries beyond the standard one, you have to program it yourself during the course of answering the question (or, I guess, if you’ve done it before, cut-and-paste one from your bag of tricks). Lacking a formal computer science education, I’d never heard of a segment tree, which makes it kind of tricky. So far I’ve counted on pretty much working things out myself from first principles each time I see something new – but, given the limited time we have on this planet, and the time it would take to re-invent computer science in my own head, I thought maybe it would be an idea to knuckle down and learn algorithms properly.

“Introduction to Algorithms” (pictured), aka “CLRS” after its authors, is a highly regarded reference book. So I’ve got hold of my own copy, but at over 1200 densely packed pages it’s not something I’m going to fly through in a weekend. I will work through it; one interesting challenge will be to try to implement any exercises in functional style, i.e. without side-effects or mutable state. In the book, the examples are in a Python-esque pseudocode with variables and loops a-go-go.

Another reference for this blog series, will be cp-algorithms.com, which I’m going to call “CPA”, and as the name suggests is a guide to competetive programming algorithms. It is itself a translation of a Russian site (as everyone knows, the best competitors are mostly Russian – they love their C++ out there). There are a LOT of topics, which are listed in alphabetical order rather than from simplest to most complex, so I’ll use CLRS as a guide to learning order, and CPA for some juicy and pertinent examples to tackle in Scala.

There only seem to be a handful of people currently using Scala in these competitions, and their style is mostly imperative. Let’s see if we can take the world of algorithm competitions by storm writing idiomatic Scala. It will be a journey!