Hello,
In Google Code Jam 2018 we are unable to run code locally and freely
use the compilers and programming languages of our choice anymore.
Instead we have to to pick one of the programming languages from the
following list: Bash, C, C++, C# (mono), Go, Haskell (ghc), Java 8,
Javascript (nodejs), Python 2, Python 3, PHP, and Ruby.
I'm happy that Ruby is still supported, because this is the programming
language which I'm using whenever I need to quickly prototype something.
However the current situation is far from perfect. For example, let's
take a look at the "Trouble Sort" problem from the Qualification round:
https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard/00000000000079cb
In the Limits section for the large input test, we can see that "Time
limit (for the entire test set): 20 seconds". In the previous years
we usually had up to 8 minutes (!) for this part of the test. But now
the time limit is only 20 seconds. I used the following Ruby program
to generate a large input data set according to the specified
constraints:
puts 100
100.times do
puts 100000
puts 100000.times.map { rand(1000000000) }.join(" ")
end
This script generated around ~100MB of data and when I tried to
feed it to my solution for this problem implemented in Ruby, it
took 13 seconds to process this data on my computer. Now I have no
idea whether the GCJ server is slower or faster than my computer,
but 13 seconds is dangerously close to the 20 seconds limit. And
the GCJ FAQ says:
"The same limits apply to all languages. Note that although we
attempt to make most problems solvable in the stated time limits
using most languages, it is not guaranteed that any problem can be
solved in any language; relaxing the limits to accommodate one
language might enable a suboptimal solution in another, etc. Part of
the contest is knowing which tool to use for which job, just as in
everyday software engineering."
Okay, the "knowing which tool to use for which job" part is perfectly
reasonable. So I would like to pick https://crystal-lang.org/ as my tool
for the job. Crystal is a statically typed language with a high
performance LLVM based compiler, which borrows the Ruby syntax.
In fact, my solution for the "Trouble Sort" problem can be very easily
adapted to a common subset of Ruby and Crystal (it happens to be a
valid Ruby and Crystal program at the same time!):
def trouble_sort!(arr)
e = arr.each.with_index.select {|(x, i)| i.even?}.map {|x| x[0]}.to_a.sort
o = arr.each.with_index.select {|(x, i)| i.odd?}.map {|x| x[0]}.to_a.sort
arr.size.times {|i| arr[i] = i.even? ? e[i / 2] : o[i / 2] }
end
def validate_trouble_sort(arr)
1.upto(arr.size - 1) { |i| return i - 1 if arr[i - 1] > arr[i] }
return "OK"
end
t = gets.to_s.to_i
1.upto(t) do |casenum|
n = gets.to_s.to_i
arr = gets.to_s.split.map {|x| x.to_i }
trouble_sort!(arr)
puts "Case ##{casenum}: #{validate_trouble_sort(arr)}\n"
end
$ crystal build --release trouble-sort.cr
$ time ./trouble-sort < large.in > large.out
real 0m2.108s
user 0m2.230s
sys 0m0.050s
It's already 5 or 6 times faster than Ruby code at least for this
particular program. Needless to say that this is not the best case
for Ruby vs. Crystal performance comparison because a lot of time is
spent in the sort function from the standard library. If we instead
look at a brute force code with a lot of number crunching in a tight
loop without any library function calls, then the performance may differ
up to a 100x factor (just like with C++ or any other natively compiled
programming language).
And of course it's a lot more convenient and fast to switch
between Ruby and Crystal than switching between Ruby and C++.
So my question is: would it be difficult to add a Crystal compiler
to the list of supported languages? It would be very useful for the
participants, who are currently using Ruby as their primary programming
language in Google Code Jam.
During the qualification round I still managed to somehow get a
perfect score with 100% Ruby code for all my solutions this time.
But I really don't want to be forced to use C++ where performance
matters.
By the way, the FAQ says that a "-pthread" option is used for
C/C++ compilers. Does it mean that it is allowed and beneficial
to use multithreaded code or maybe even OpenMP in C/C++ solutions?
--
Best regards,
Siarhei Siamashka aka 'ssvb'
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/20180409032222.116bd3f6%40i7.
For more options, visit https://groups.google.com/d/optout.
