6 ms·

I also come to the conclusion that Ruby-like languages are just not the right tool for this kind of problem, but it should be pointed out that you would have be

• bvdbijl 13y ago
  Yep, in a competition you want a language that had as little magic as possible. Languages like Ruby (not necessarily dynamic languages!) are just not really suitable for it
  • nossralf 13y ago
    Wouldn't you want to use a language that is familiar in a competition? If Ruby is your forte, surely you should use it? I fail to see how "magic" properties of a language matter if you've got reasonable algorithmic chops and focus on solving the problems rather than trying to be clever.
    • trailfox 13y ago
      > Wouldn't you want to use a language that is familiar in a competition? If Ruby is your forte, surely you should use it? If you're familiar with knives why not bring a knife to a gun fight? If knives are your forte, surely you should use it?
      • nossralf 13y ago
        If the goal of the competition is to slice apples, then a knife is pretty good compared to a gun. Or if the competition takes place under water. Or if you're Steven Seagal and the ship where you work is taken over by a splendidly over-acting Tommy Lee Jones and his gun-wielding minions. Execution speed is nice, I don't disagree. But it's not always the be-all and end-all deciding factor for what tool to use to solve a problem in a specific context. Competitions can be stressful, and choosing a tool that feels like an extension of yourself (be that Ruby, COBOL or whatever) is, to me, the better route. Compared to something that executes faster on your computer but not in your head.
        • georgemcbay 13y ago
          I don't think the parent post (which I totally agree with) was saying that you must always decide by picking an inherently fast language, but rather if you decide to pick one whose execution time is not inherently fast to enter a competition where execution time is factored you will start with a major disadvantage. That doesn't mean you'll lose (ala your Steven Seagal analogy), maybe you're so much better than everyone else that you can overcome the disadvantage, but you'll surely be starting in a bad position compared to someone holding a 'gun' even if he or she is somewhat less skilled at using the gun than you are at using the knife.
          • nossralf 13y ago
            Well sure, adding "where execution time is factored" makes it hard to disagree with you. (And ultimately, it usually becomes a factor sooner or later.) That wasn't the context in which I was writing my original reply, however. I was responding to a post that mentioned "magic" as a reason to disregard Ruby for competitions, which I didn't agree with. (The Ruby solution in the submission was slow even using a while loop, which is far from magic.) If you're able to solve problems in the same amount of time using a fast and a not so fast language, of course you pick the faster one in a competition. I'm not arguing against that.
          • entropy_ 13y ago
            My experience with GCJ has been that raw execution speed almost never matters as long as you have the right algorithm. In the case of the OP, for example a trivial optimization(the kind you do without even thinking in these competitions) would've brought his execution time down 10000x. Basically, you are asked about the number of "fair and square" numbers in a certain range, over and over again, in 10000 different cases. He could have just taken his solution, pre-generated all those numbers once and then ran all those test cases by counting in that pregenerated list, instead of generating it for every single test case(all 10^5 of them). It turns out, that in the whole span of 1->10^14 there is only 39 such numbers and it would've taken his program probably less than a minute to generate all of them(I'm being generous here, since it ran 10^5 test cases in 53min). In fact, if you read the problem analysis later provided by google you will see that in fact you were expected to make this optimization to solve the problem. The fact that C-small had 100 test cases, C-large-1 had 10^5 and C-large-2 had 100 should've been a strong hint that C-large-1 required some pre-caching across test cases.
    • bvdbijl 13y ago
      Yeah sure. It's just that for performance reasons some languages really are better than others.
      • nossralf 13y ago
        Agreed. If performance is the main (or an important) criteria for the competition then the choice of language is rather more significant.
        • bvdbijl 13y ago
          It's why IOI (http://www.ioi2012.org/competition/rules/ http://www.ioi2012.org/competition/rules/) doesn't allow interpreted languages, because they are (or at least when the competition was first held were) just too slow. If you have only 1-5 seconds of computations time you're going to choose for a compiled language every time
          • Radim 13y ago
            I thought rules were there to discourage unfair advantage, not disadvantage? Why would you need a rule for that? In any case, I see both python and ruby on the page you linked to, so perhaps I'm missing something.
            • bvdbijl 13y ago
              Well it's just that to support another language they need to make solutions for every problem in that language to test that it's actually possible and they don't want to do that. and on that page it says: Each submitted source program must be written in C, C++ or Pascal, it must be smaller than 100 KB, the evaluation server must be able to compile it in less than 10 seconds and at most 256 MB of memory. No other extensions different than the ones listed above will be run. They put Python and Ruby on the machines so you can write a script to generate testcases, you can't submit programs written in those languages
  • chc 13y ago
    This seems like such a vague, insubstantial piece of advice. I've seen it before, but never in a more concrete form. I don't see any "magic" in Ruby. How do I determine if a language is magic? Usually, the best I can figure is that they're either confusing syntax with semantics or they're actually thinking of some library like ActiveRecord rather than Ruby. Really, for pretty much anything I could conceivably think of to call "magic" in Ruby (e.g. method_missing), there's equivalent "magic" in Python (e.g. __get_attr__). And yet PyPy is pretty darned fast.
    • evolve2k 13y ago
      I think the misunderstanding comes from people confusing Rails with Ruby.
    • robryan 13y ago
      I think people are referring to language features that are very powerful and concise but have horrible performance when you get large data sets like this. Something like the inject method, at least in my limited use of ruby with these kind of Google Code questions, seemed problematic.
  • deleted 13y ago
    [deleted]
  • JeanPierre 13y ago
    I partially disagree, partially agree. In these competitions, it's about implementing a solution as fast as possible, while still get it working under the time limit (5/8 minutes). It's mostly about having the right idea and implement it. In very many cases, you would like to be able to manipulate and play with algorithms and have efficient mutable data structures. For this, Java/C++ (Essentially C with data structures) is very suitable. However, in some cases, you'd like to perform advanced simulations, mathematical calculations or manipulations where immutable data structures are more suitable. In those cases, you would LIKE to have magic: Arbitrary numbers, ratios, (efficient) immutable data structures and a more functional style would not only eliminate work, but also reduce the amount of errors you're likely to do. The important part is that the implementation uses the right idea, not that the implementation is fast. Usually it's handy with a lower-level language to implement the algorithm right, but at times, a higher level (functional) language is better when it comes to implementation speed.
    • bvdbijl 13y ago
      Different ways for different people, I'm just talking about my own experience
  • entropy_ 13y ago
    I've been taking part in GCG since ~2008 now. I have only once encountered a problem where my solution in python was too slow but an equivalent one in C would've been fast enough. Though just barely(my python solution ran in ~10min, the C one I wrote later ran in 5min, the time limit was 8min). In that particular case, there was a more efficient algorithm which we were expected to find to solve the problem(ie, my brute force-ish solution was not anticipated and it would've been "cheating" if it had actually worked) and I didn't find it. In general, I'd much rather be able to implement my solutions as quickly as possible as the challenge is usually in 1) finding the correct algorithm and 2) implementing it correctly and fast. If you can do that, choice of language usually doesn't matter unless in some of the problems you might get in the finals(I've never gotten that far, I usually rank somewhere in the top 2000). Also, for me, the ease with which I get things like arbitrary-size integers, sets and dictionaries far outweighs any speed gains from something like C++.
  • nfm 13y ago
    When you say "magic", what you really mean is "abstraction", which is a more suitable and neutral word to describe the pros and cons of using a higher level language. Not that I disagree with your premise - if you need to write highly performant code, lower level languages will pretty much always be faster. But abstraction is extremely beneficial in many other circumstances.
  • lmm 13y ago
    On the contrary, the biggest downside of magic comes in maintainability. So languages with more magic are more appropriate for competitions than for regular code.
• jeffwass 13y ago
  I learned python about a month ago and was able to solve all three parts of this problem correctly (part C was the most difficult). My code was poorly optimized, but with some careful forethought, python's bottlenecks were not too problematic. The first two parts were very easy with only brute force by working thru the square root of the full range once, caching the numbers, and using that cache. I don't see why people (including the auhor) recalculated the numbers for each goven range, especially in part B which required 10k such ranges. That said, my python code, as a relative newbie, took 10s to cache all fair and square numbers from 1 to 10^14. I ran thru from 1 to 10^7, checked if palindromic using strings, and if good checked the square. (there were only 39 such numbers in total). I then ran all 10k answers in seconds. Part C was MUCH more tricky, until I discovered the same trick most others found, that only some of the square root palindromes are valid with digits 0, 1, and 2. That said, as a python n00b, my code took 40 mins to run the range from 1 to 10^100. I asked the google staff if pre-caching is allowed, and they said yes, as long as my code to generate the pre-cache is provided wih my submission. Properly optimizing my python would probably give similar performance. But the point is that with a bit of forethought, even poorly-optimized python code by a newbie was sufficient to solve all three parts of this question.
  • entropy_ 13y ago
    I also solved in python, however, my code to pre-generate all "fair and square" numbers in the range 1->10^100 only took 6s to run. Didn't even need optimization. I simply constructed the numbers outright, ie, there was no iteration in my code and trying to see if something fit. I just figured out a rule that would generate all those palindromes with no checking. I think that was what they were looking for in that submission. If anyone is curious, the rule is as follows. Any palindrome where the sum of the squares of the digits add up to strictly less than 10(9 or less) will be the square root of a "fair and square number". From there, I constructed them using a recursive method which finds the first half of numbers fitting that description and mirrors them to get the palindrome. I ended up getting an incorrect solution on C-large-2 but that was because I failed to realize that I would lose precision when finding the square roots of the bounds of the range. While integers in python can grow indefinitely math.sqrt() will give you a 32bit floating point number which will represent square roots of 10^14 numbers accurately but not square roots of 10^100 numbers. The diff which turns my program into one that gives correct answers has literally 3 changes lines(to use decimal.Decimal instead of the math library for doing square roots).