Preorder Perusal

Pythonで書きたい欲求を抑え、Rubyで書く。
Rubyの構造体をとりあえず使ってみたが、別に使う必要はなかったかもしれない。

Tree=Struct.new("Tree",:left,:right)

def run
  t={}
  STDIN.gets.to_i.times do 
    l,r = STDIN.gets.rstrip.split(" ")
    if !t.has_key?(l)
      t[l]=Tree.new(r) #left
    else
      t[l].right=r
    end
  end  
  tr(t,t.keys[0])
end

def tr(t,k)
  puts k
  tree=t[k]

  if tree.nil?
    return
  end

  unless tree.left.nil?
    tr(t,tree.left)
    unless tree.right.nil?
      tr(t,tree.right)
    end
  end
end

STDIN.gets.to_i.times { run }

---

Given a binary tree, we want to perform a preorder traversal. A preorder traversal is defined as follows. Suppose the tree looks like this, where (left) and (right) are subtrees:

      Root
      /     \
 (left)   (right)

1. Print the root
2. Print the elements in (left), if any, using preorder traversal
3. Print the elements in (right), if any, using preorder traversal

The first line of the input will be an integer N (1 <= N <= 1000), indicating the number of test cases.

Each test case consists of one line containing an integer K (1 <= K <= 100), followed by K lines containing two space-separated strings A and B, representing that B is a child node of A. When A has two children, the left one will always be given first. Each test case is defined such that the tree has only one root.

For each test case, print out the node names in preorder, one per line. No blank line between test cases.

Sample Input/Output

1
6
A C
A F
C B
C D
F E
F G

A
C
B
D
F
E
G

Double Duplicates

GroupByとかメソッドチェーンとかRubyの出番かな？！と思ったが、そうは行かなかった。
けっきょくそんな集合演算するよりも、こんなかんじでガリガリ書いたほうがはやいのだ。ということでPython

import sys

def run():
  N=int(sys.stdin.readline(),10)
  arr=sys.stdin.readline().rstrip().split(" ")
  assert len(arr)==N+2

  target = sorted(int(s,10) for s in arr)
  for i in xrange(len(target)-1):
    if target[i]==target[i+1]:
      print target[i]

for i in range(int(sys.stdin.readline())):
  run()

ちなみにメモリくいつつAssertも省略な、馬鹿げた方法でよいなら、Rubyのほうがキレイには書ける。これRuby信者がよく言ってることね。
でもキレイなだけで、メモリ食ってるようじゃダメ。

def run
  STDIN.gets.to_i
  STDIN.gets.split(" ").map{ |s| s.to_i }.sort.group_by{|n| n}.select{|k,v| v.size==2}.each do |k,v|
    puts k
  end
end

STDIN.gets.to_i.times { run }

---

You've got a list of X+2 numbers containing the numbers 0 through X-1, but with two duplicates. We want to find those duplicates using as little memory as possible. (That's important.)

The first line of the input will be an integer N (1 <= N <= 100).

Each of the following N test cases consists of one line containing an integer X (1 <= X <= 1000), followed by X+2 space-separated integers on the next line.
 
For each test case, print out the two duplicate elements, separated by a newline, with the smaller one first. No blank line between test cases.

Sample Input/Output

1
5
1 2 3 4 0 4 2

2
4

Sublime String

これはRubyの得意分野か

def is_sublime(str1, str2)
  str1.each_char do |s|
    unless str2.include?(s)
      return false
    end
  end
  return true
end

def run
  str1,str2 = STDIN.gets.rstrip.split
  if is_sublime(str1,str2)
    puts "sublime"
  else
    puts "unsublime"
  end
end

STDIN.gets.to_i.times { run }

でもPythonのシンプルさには劣るな…

import sys

def isSublime(str1,str2):
  for c in str1:
    if not c in str2:
      return False
  return True

def run():
  str1,str2 = sys.stdin.readline().rstrip().split()
  if isSublime(str1, str2):
    print "sublime"
  else:
    print "unsublime"

for i in range(int(sys.stdin.readline())):
  run()

---

Two strings are "sublime" when all the characters in the first string appear in the same order in the second string. For example, "rat" and "rather" are sublime, "mat" and "moat" are sublime, but "can" and "cat" are not. We want to determine whether pairs of strings are sublime or not.

The first line of the input will be an integer N (1 <= N <= 100).

Each of the following N lines represents a single test case, containing a space-separated pair of strings A, B, each of which consists of only letters (no special characters).
 
For each test case, print 'sublime' if A is sublime to B, or 'unsublime' if not. No blank line between test cases.

Sample Input/Output

4
z izy
iy izy
ezy izy
c c

sublime
sublime
unsublime
sublime

Numerical Nirvana

Pythonなら、リスト内包のチカラで、すごく直感的に書けるのだが…。

import sys

def isHappy(n,closeset):
  if n==1:
    return True
  if n in closeset:
    return False
  closeset.add(n)
  n2=sum([int(x,10)**2 for x in str(n)])
  return isHappy(n2,closeset)

def run():
  n=int(sys.stdin.readline(),10)
  if isHappy(n,set()):
    print "Y"
  else:
    print "N"
  
for i in range(int(sys.stdin.readline())):
  run()

RubyだとMapとReduceを使うのかな…。ブロックを使うのかな…。

def is_happy(n,closeset)
  if n==1
    return true;
  end
  if closeset.include?(n)
    return false;
  end

  closeset << n
  #n2=n.to_s.map{ |x| x.to_i**2 }.reduce{ |i,j| i+j }
  n2=n.to_s.each_char.map{ |x| x.to_i**2 }.reduce{ |i,j| i+j }
  return is_happy(n2,closeset)
end

def run
  if is_happy(STDIN.gets.to_i,[])
    puts "Y"
  else
    puts "N"
  end
end

STDIN.gets.to_i.times { run }

コメントアウトしてあるけど、Ruby 1.8→1.9でStringがEnumerableじゃなくなったんだとか。なんでやねん。
Pythonが2→3で文字列をバイト列としているのと比較すると、なんかRubyはそれと逆行しているような感じがする。

• String#each_byte, each_char　→　PythonのStringに近い。1文字1文字のenumerable。冗長にbyteやらcharやらあるところがRubyらしくて嫌い。
• String#each_codepoint　→　Python3のbStringに近い。バイト列のenumerable

---

A happy number is defined by the following process: 

Given a number X, square each digit and sum the results. Repeat this procedure on the resulting sum until you either reach 1, or fall into a repeating cycle which does not include 1. When this process ends in 1, X is a happy number.

The first line of the input will be an integer N (1 <= N <= 100).

Each of the following N lines represents a single test case, containing an integer X (1 <= X <= 100000).
 
For each test case, print 'Y' if X is a happy number, and 'N' if not. No blank line between test cases.

Sample Input/Output

4
1
7
635
699

Y
Y
Y
N

Palindrom(回文)

putsとpの違いに騙された。
これだとダメっていわれた。

def is_palindrome(s)
  return s == s.reverse()
end

def run
  if is_palindrome(STDIN.gets.rstrip)
    p "Y"
  else
    p "N"
  end
end

STDIN.gets.to_i.times { run }

pだと"Y"ってかんじでダブルクオテーションがつけられてしまうらしい。どういうことかは知らんけど。
んで、これだといいらしい

def is_palindrome(s)
  return s == s.reverse()
end

def run
  if is_palindrome(STDIN.gets.rstrip)
    puts "Y"
  else
    puts "N"
  end
end

STDIN.gets.to_i.times { run }

とあるぺーじによると、こんな仕組みらしい。こういう意味不明に同じようなやり方が存在するっていうのが、私がRuby大嫌いな理由。pythonみたいにprintだけでコンマの有無で改行の有無が変わる、とかでいいじゃない。

• p
  引数のオブジェクトを人間に読みやすい形で出力。 文字列はダブル・クォーテーションで囲まれて表示されるので、 末尾にスペースが入っているかどうかも確認できる。 配列やハッシュ（連想配列）もそのままの形で表示する。
• puts
  引数のオブジェクトの値それぞれに改行をつけて出力。 配列の中身もそれぞれが改行される。 ハッシュ（連想配列）は繋がって表示される。
• putc
  １文字を出力。引数は１個だけＯＫ。 引数が数字なら、0 〜 255 の範囲の対応する文字を出力 引数が文字列なら、その先頭の１文字を出力。
• print
  引数を順に出力。 オブジェクト間に改行は自動的には入らないので、必要なら挿入してやる必要がある。
• printf
  C 言語の printf と同じように、format に従い引数を文字列に変換して出力

---

A palindrome is a string reads the same from left to right and from right to left. For example: 'abba' is a palindrome, as well as 'aba', but not 'bbaaa.' We want to determine whether strings are palindromes.

The first line of the input will be an integer N (1 <= N <= 10000).

Each of the following N lines represents a single test case, containing a string S (1 <= length of S <= 10000). The string will not contain any spaces or special characters.

*Note* each string will end with '\n' given each line has only one string(test case)
 
For each test case, print 'Y' if S is a palindrome and 'N' if not. No blank line between test cases.

Sample Input/Output

3
aba
bbaa
a

Y
N
Y

Fibonacci

こんなのがデフォルトで入ってる。

def run
  # Code here!
end

STDIN.gets.to_i.times { run }

↓サンプルは通ったけど、もっと良いアルゴリズム出さないと遅すぎて計算できんぞ、とRejectくらった。

def fib(n)
  if n<=1
    return n
  else
    return fib(n-1)+fib(n-2)
  end
end

def run
  # Code here!
  STDIN.gets.to_i.times { |n| p fib(n) }
end

↓うまくいった〜。

def fib_by(n)
  a=[0,1]
  
  n.times do |n|
    if n >= a.size
      a << a[-1] + a[-2]
    end
    p a[n]
  end
end

def run
  fib_by(STDIN.gets.to_i)
end

---

The Fibonacci sequence is a sequence in which each term is the sum of the two previous terms, like so:

F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
…

We want to write a function that prints the first X numbers of the sequence.

The first line of the input will be an integer N (1 <= N <= 100).

Each of the following N lines represents a single test case, containing an integer X (1 <= X <= 90).
 
For each test case, print the first X numbers of the Fibonacci sequence, one per line. No blank line between test cases.

Sample Input/Output

1
3

0
1
1