Google Code Jam

  昨天在 Solidot.org 上看到 Google 要专程在中国举行一次 Code Jam 大赛,由于对 Google 举办的编程比赛会出什么题目比较感兴趣就去注册了一把。比赛平台用的是 TopCoder 开发的一个专门用于程序竞赛的 Java 程序,默认界面是黑色的,看起来比较 Cool!

  进入练习后的解题界面分上下两部分,上面是用英文描述的题目,下面是代码输入窗口,写好代码后可以点击下面的编译按钮进行编译,还可以用系统提供的测试用例测试程序。解题时有 4 种语言可选:Java、C++、C# 和 VB。从看到题目开始计时,到提交了编译通过的代码后计时停止。如果再次提交代码会减分,代码被别人的测试用例挑战成功也要减分(别人加分)。

  由于 12 月 12 号才开始第一轮选拔赛,所以现在只能看到 3 个练习题,都比较简单,想必正式的比赛是不会出这么简单的题目吧?!尤其是后几轮。最近都在抽时间看 Ruby,正好可以拿这个练练手:-)就用那个 250 分的题开刀吧,题目是这样的:给定一个 20×20 的字符矩阵,左上角坐标为 (0,0),初始方向向下。开始时矩阵中每个点的值都是“.”,输入数据是若干条指令,指令只有两种,“LEFT”和“FORWARD n”,“n”是步长。程序要按照给定的一系列指令在矩阵中 walk,最终的输出就是按照指令 walk 后留下的轨迹,走过的地方用“X”标记,测试用例可以保证不会走出这个矩阵的范围。我用 Ruby 写的程序如下:

  1. class DrawLines
  2.    def execute( commands )
  3.      direction = x = y = 0
  4.      result = []
  5.      for i in 0 ... 20
  6.        result.push( '.' * 20 )
  7.      end
  8.      commands.each{ | command |
  9.        if( "LEFT" == command )
  10.          direction = ( direction + 1 ) % 4
  11.        else
  12.          steps = command.split( ' ' )[1]
  13.          result[y][x] = 'X'
  14.          for i in 0 ... steps.to_i
  15.            case direction
  16.              when 0 then y += 1  # Down
  17.              when 1 then x += 1  # Right
  18.              when 2 then y -= 1  # Up
  19.              when 3 then x -= 1  # Left
  20.            end
  21.            result[y][x] = 'X'
  22.          end
  23.        end
  24.      }
  25.      return result
  26.    end
  27.  end

  这个比我用 C++ 写的代码短多了,Ruby 的 iterater 起了很大的作用!不过由于对 Ruby 还不太熟,很多方法还是要中间查文档才知道的:-)想要测试这段代码可以这样:

  1. ( (DrawLines.new).execute( [ "FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19" ] ) ).each{ |item| print "#{item}\n" }

Leave a Reply