The format of this competition, allowing us to run programs on our
own machines, brought up a very interesting issue for me: what
programming language should I be using? (I had had similar
considerations for IPSC 2013, but GCJ’s problems are closer to the
traditional ACM-ICPC style.)
The obvious choice is C++, the language I use for roughly every other
competition, but its safety (or lack thereof) is not very appealing. I
need speed, but not that much speed. Unfortunately I still
haven’t gotten around to learning any other friendlier mid-level
languages (on the list: D, Go, or Rust), so I have no close substitutes
for C++ right now.
Python is certainly available for a reliable arbitrary-length integer
type, if nothing else.
As for non-candidates, Java has BigInteger and memory
safety, but all in all I decided the benefits are too minor and it’s too
ugly without operator overloading. Scala is probably way too slow. So I
don’t expect to be writing either language.
The only difficult choice I have to make is, of course, Haskell —
which can be quite fast, even while it’s ridiculously type-safe and
expressive and referentially transparent and easy to reason about, once
you’ve:
figured out how to do the problem
scrapped step 1 and actually figured out how to do the
problem functionally
gotten the thing to compile
Even if I can handle step 1, step 2 is by no means a simple task, as
my struggle to implement a mere
Sieve of Eratosthenes
efficiently shows. That is fun, but not at all intuitive; I am doubtful
I can do this under contest conditions. It is extremely difficult to
transfer my skills in learning how to implement, say, a segment tree or
treap into this language.
But! Google links to the
programming language
breakdown for 2010 Qualification Round as an example, and much to my
surprise, Haskell ranks somewhere between sixth and tenth place in
popularity (depending on what you sort by), so there are functional
superprogrammers who can presumably do something like this.
As it happens, I ended up implementing all four solutions to the
qualification rounds in Haskell, because of the relaxed time limit and
lack of any involved algorithms and data structures. I think it was
worth it.
Random video! Although I feel that I’ve heard it earlier, my first
conscious memory of getting linked to it is from
this
post. At first I thought it would be the right background music for
this post, but upon further reflection I think it mainly suited me while
I was writing this post. Well, it’s topical if you mentally replace
“day” with “year”.
Anyway. Around this time a year ago, I paused my participation in big
high-school competitions, for a variety of reasons.
Firstly, I stopped attempting to make IMO both because I wouldn’t get
that much from the training and because other people ought to have the
opportunity. I was concerned that I might condition myself to only be
able to do math with the short-term motivation of contests. Better to
focus on college math and maybe some original research, I thought.
During the year, I did lots of the former and very little of the latter.
Meh.
As for the IOI, my obvious next target: I was tired of training and
going abroad while paranoid about whether my immune system would hold
up. I didn’t feel that the IOI was worth that. To some degree, I also
felt burned out about programming. Long story short, my treatment should
end soon, and learning Haskell completely resolved the burnout
problem.
But the most important reason, I think, was that “high school was too
short”. I started math competitions ridiculously early and didn’t spend
much time exploring other interests. I thought I knew myself well enough
that I could say I didn’t have many more interests at all, but I was
completely wrong (psych nerds will reflexively note this to be the
Dunning-Kruger
effect). I coded lots in weird languages — Haskell, as mentioned
previously, plus Scala, plus all manner of other magical command line
tools. I wrote my first math problem and submitted it officially, picked
up a new instrument, went to a debate competition, served as an
unimportant tech guy for MUN, discovered and became hooked on
Pentatonix, participated in three puzzle hunts in Australia and one in
Massachusetts, figured out my rough political stance, rode a boat, got
retweeted by @eevee and
@Kyrgyzstan_News, increased my
Neopets™ fortune by over 3400%, and lurked on FurAffinity a little too
much.
Funny, I go on a trip to Penghu followed by a four-day science camp
and also get dragged into drawing classes and some sort of movie
advising joint, and this is what I decide to blog about.
Since it’s summer, I went back to
Rankk and solved stuff. This is lots
of fun if you’re good with computers, plus a little math, cryptography,
and general puzzling. I’m still stuck on level 8… oh well. Since the
levels didn’t seem very indicative of difficulty to me, I decided to do
some analysis.
New challenges have been added to Rankk over time, so my metric of
difficulty is the number of solvers divided by the time from release to
now. Of course this is far from perfect; for example, a challenge’s
author doesn’t always seem consistently counted as a solver, problems
with lower numbers and problems that will help level up are more likely
to get checked out by new rankkers, and so on. But this is just for
fun.
“I have been told that any encryption becomes safer if the underlying
algorithm is maximally obscured, what is most conveniently done by
coding it in Haskell.” – rankk
Functional programming is terribly addicting! Partly I think the
completely different way of thinking makes it feel like learning
programming, and falling in love with it, all over again. Partly there’s
this evil sense of satisfaction from using $s (and later
<$>s and =<<s and
&&&s) to improve readability for initiated
Haskellers and worsen it for everybody else. Partly it’s because
Learn You a Haskell for Great
Good! is such a fun read — there are too many funny bits to list
but my favorite so far is when the author analyzes the first verse of
Avril Lavigne’s Girlfriend.
Although I think my code in Haskell tends to be more readable than in
other languages, code obfuscation in Haskell is almost natural: all you
have to do is refactor the wrong function to be “pointfree”, which means
that even though it’s a function that takes arguments, you define it
without parameters by manipulating and joining a bunch of other
functions. Example (plus a few other tiny obfuscations):
Okay, but seriously now. I wrote this about my journey to learn
functional programming in the
programming babble post half a
year ago:
The main obstacle I have is that it’s hard to optimize or get
asymptotics when computation is expensive (a big problem if you’re
trying to learn through Project Euler problems, particularly ones with
lots of primes).
because my title needs to mean something.
(note from the future: before late
2017, when I migrated to Hugo and
GitHub Pages, the blog was called “BetaWorldProblems”.)
Google just announced
it’s
shutting down Google Reader in three and a half months… I am
participating in the friendly Reddit DDoS-hug of all the alternatives
(list,
but scroll around in the thread for a few more). Darn.
So, what have I been doing with programming recently?
Scala is an amazing
multiparadigm programming language that runs on the Java Virtual Machine
and interoperates with Java. I learned about it last time reading random
articles on Twitter.
When I say “amazing” I mean “This is a language in which my code
gives me nerdgasms every time I read it.” Wheeee.
Okay, it’s not perfect. People say it’s too academic. It has a
notoriously complicated type system (which is
Turing-Complete
at compile time). Its documentation is a bit patchy too. For a
serious introduction, the Scala website has plenty of links under
documentation, and a tour
of features. Somebody wrote
another tour that
explains things a bit more. So here, instead of introducing it
seriously, I’m just going to screw with its features.
Example of freedom. Scala lets names consist of symbols, and treats
one-parameter methods and infix operators exactly the same. The full
tokenization rules are a bit detailed and I put them at the bottom of
this post for the interested. This lets you create classes with
arithmetic and domain-specific languages easily, but it also creates
some silly opportunities:
Yay?
Right now I feel about this a lot like I felt about getting Twitter. Nobody I know personally is there, but all the “famous” “technological” people are, and something like 90% of the open-source projects I bump into are too.
Just like Twitter, I barely know how to use Git either, but that’s okay. For version control I’m going all command-line now! Last time I tried to link stuff up with Eclipse everything exploded, but after I ran git init from the terminal this time, it’s highlighting things red and green everywhere like it’s suddenly begging me not to forsake it for the command line.
Okay I don’t actually know how this pointless rambling got so long. I
know the longer it is the more people will just tend to skim, because I
do that all the time. So I went back and refactored—er, rewrote all the
somewhat tangential bits (wow these puns are too easy) into footnotes.
Manually. Obviously if I have to do this again I’ll write a script for
it. But the post is still really long, and I bet nobody will read the
whole thing. Oh well.
Life updates: I got out of the hospital Friday two-and-a-half weeks
ago, went to the preliminaries of NPSC (a national team programming
contest) with classmates, threw up a lot, went back into the hospital,
and came out again. I wrote a lot of stuff about the experience and how
much it sucked (hint: a lot) when I started this draft around
that time, but now putting so much detail in this post feels weird. I’m
mostly good now.
Three years ago NPSC was the only programming contest I really knew
of; now I’ve participated in quite a few more, both online and locally,
but it’s still the only contest I’ve entered that gives you real-time
verdicts. I believe it inherits this from being modeled after ACM-ICPC,
but that’s for college people and I’m less clear on how it works. All
the other contests, namely
TopCoder,
CodeForces,
USACO, and the other local individual
competition (there doesn’t appear to be an English name so for the
purpose of this post I’ll just call it “Nameless Local”; there’s a
nation-wide competition in one-and-a-half weeks!), have system tests
after the contest that don’t allow you to resubmit afterwards.1 They all give pretests that you get
to know about right away, just to catch super-silly non-algorithmic
mistakes like failing to remove the debug statements or reading input
from the wrong place, but these contain weak test cases and don’t
guarantee that the solution will pass the system tests and get full
score.
Okay, I give up. Here it is: Gridderface is a (quoting the project description, which I wrote anyway so whatever) “keyboard inferface for marking grid-based puzzles in Java” that I’ve been working on for too long. It is open-source under the GPL v3.
Basically, it’s a thing you can paste logic puzzle images into to solve them in, like people do in Paint, when you can’t or don’t want to print them.