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