32nd Diary

■ RejectKaigi @ RubyKaigi 2010

■ DevQuiz for Google Developers Day 2010 Japan

さて、Google Developers Day 2010 Japanに参加するためにはDevQuizの問題を解く必要があったわけですが、そのDevQuizの回答の締切りが今日でした。 ちゅうわけで、さっそくですが、感想戦。

今回のDevQuizはガチ開発者向け Super Hackers枠、Googleコミュニティ開発者向けTop Favorites枠、熱意のあるヤツ向けNext Generation枠というみっつの枠があった。

Super Hackers枠は純粋にプログラミングの勝負に近く、Top Favorites枠はGoogleのプロダクトに関する貢献などが特典に左右されるらしい。Next Generation枠では200文字の小論文というか、Twitterに毛が生えたような長さの文章で熱意を表現すると得点されるんだとか。

Googleに貢献してるかとか、よくわかんないスピリチュアルな文章で挑戦とかガラじゃないので、Super Hackers枠にて参戦。

■ ウォーアップ問題

もう何が出題されたのか忘れた。 簡単な三択とかでググったり、Webアプリケーション使ったら解けました。 おしまい。

■ ラウンド 1: HTML5 間違い探し

すみません、 "HTML5 validator" で検索してでてきたサイトでバリデーションチェックに引っかかったところをそのまんま入力しました。

仕様書とか読んでません。

■ ラウンド 2: 2-legged OAuth

選択問題。もうひとつは「ラウンド 2: Google Maps API」でした。問題文みた瞬間に「あー、これは難しい問題だけど、Maps API使うと解けるってやつか。」とオモイマシタガ、OAuthのほうがソースコードの提出とか必要ないみたいだし、ラクそうなので一撃でクリアーしました。

#!/usr/bin/env ruby

require 'net/http'
require 'digest/md5'
require 'openssl'
require 'uri'
http = Net::HTTP.new('gdd-2010-quiz-japan.appspot.com')

def base64(value)
	[ value ].pack('m').gsub(/\n/, '')
end

def digest_hmac_sha1(value)
	OpenSSL::HMAC.digest(OpenSSL::Digest::SHA1.new, secret(), value)
end
def secret
	"xxxxx" + '&' + ""
end

oauth_headers = {
	'oauth_consumer_key' => "xxxxx",
	'oauth_nonce' => "#{Digest::MD5.hexdigest(Time.now.to_f.to_s)}",
	'oauth_signature_method' => "HMAC-SHA1",
	'oauth_timestamp' => "#{Time.now.to_i}",
}
require 'cgi'
oauth_base = oauth_headers.sort.map do |key, value|
	"#{key}=#{value}"
end.join('&')


uri = URI.parse('http://gdd-2010-quiz-japan.appspot.com/oauth/xxxxx')
p signature = "POST&" + CGI.escape(uri.to_s) + "&" + CGI.escape('hello=world&'+ oauth_base)

oauth_headers['oauth_signature'] = base64(digest_hmac_sha1(signature))
headers = {
	'Authorization' => <<-EOA,
		OAuth realm="devquiz",
		oauth_consumer_key="#{oauth_headers['oauth_consumer_key']}",
		oauth_signature_method="#{oauth_headers['oauth_signature_method']}",
		oauth_signature="#{oauth_headers['oauth_signature']}",
		oauth_nonce="#{oauth_headers['oauth_nonce']}",
		oauth_timestamp="#{oauth_headers['oauth_timestamp']}"
	EOA
}
response = http.post(uri.path, 'hello=world', headers)
puts response.body

よく専用のライブラリも使わずに標準ライブラリで解く気になりましたね。 っていうか、ライブラリ探したけど使い方がよくわかんなくて 2-legged OAuth の仕様書読んだほうがはやく解決できました。

おしまい。

■ Super Hackers:Shiritori

Super Hackers枠ねらいの人は回答が必須の問題。 デタラメな英字列でしりとりをする。

レベルは三段階でだんだんとサーバの回答が定型的なハメでプレイヤーをやっつけるパターンになってくるカンジ。要するに特定の英字ではじまる単語を要求し続けることができるような辞書の組み合わせになっている。

辞書からこちらから発言するとハメパターンに陥る語の末尾候補を grep で抜き出して、単語単位で見る必要などないので cut, uniq してキケンなワードは目視で無視して、パターンに陥らないようにしていたら、サーバがハマるワードを回答したのでこっち側がハメパターン回答したら勝てた。

すべての勝利パターンを数え上げるソースコード書いたんだがな・・・レベル３ではメモリ2GBからスラッシング起こしはじめて使えず。まぁ、数え上げできてもわざわざ探すの面倒そうなのでコード書いた意味なかったよ。

#!/usr/bin/env ruby1.9

class Shiritori
	attr_reader :answers, :words
	def initialize(words, answers = [])
		@words = words
		@answers = answers
	end
	
	def followers(word)
		@words.map do |w|
			if word[-1..-1] == w[0..0] then
				w
			else
				nil
			end
		end.compact
	end

	def answer(word)
		Shiritori.new(@words - [word], @answers + [word])
	end
end

words = %w(qcazn nzmoc nfndmz nfxjqzfx ckajaeftuz crspflkyyx cmpqthtojp zlsmbux zbgssfqzp zupqplnq xyggruolxp xxowgiq xgripmcunm prkgvipfjq pjgdvfgwm pgiolvwbtfk qjnzgrm qcgbepdkrk qvygdtjfwu muodhdk mfolvctu mmsmjytqnbn kqurxiu kbxpdrnfun kebisc ujkjean ubafnsc ugqaljz nllvwh hvrymqjuuo hxuwevbmnj hfubde csvvdnr rkefyf rkxlzwi rwnlnb zjepxcs sqzqyxfdy spbmuuwg srrqszjhd xvcxh pyclr qyscs mysgh kuvtjr uwxsxzs olzvqgpejf odizhfy ovlkfj ombxpqei odistxbwbpg obijoe otwagogqib ohjcbd okdja omynhtyl osicrjxxkw fuxnpjhqio fkdcy fhoegbaij fwszai febcpqxjpyg fqpnaxoe fydmqosmb ftryiwrhfd ffdxna fewbl fufukxurw ykhippo ybtynsojvnf ydtmj yttohtbci yvxeg ytcme yowuvqkqgsb ygxsijjupd ytjvaala ypnnewwimil ywnffbjyhw jqvqzlo jxtjkqaaumf jhbsydy jedfeuti jnbeelalg jytwe jjpzbypmizb jtgnlad jlmnrca jvahmwl jojfnwasw iosgo iefwyowkcf ixihlcy iuyhqaj ibomxiqqng iybcgyhbe ipgbb iszid ifzba ixjgasssl inektww gkrgo gjmmbfuqvf gafocatxsy glfciweoivj gssji gkgsftpadye gwkernqb gvtvclgxkd gjhxa grttl ghsgdpoiaw eyniowomxho eeyuntf eoafry ejbpnfj eremnehi ehwkg edwdlxgcb ewaofd engra ebizruwzl ewizww bvjkzxuejo bzjbf beqiy bwkdmohqluj bhcmjuji bufsyzg bblke bphlfemcnsd bnhoea baxvwppppl bbsctaublww dbbnhyveboo duncwilf dgidhretxy deaeszcfj dgcuzfi duharynhog dsahqtergge dlfyydsrb dvyfjzjsaa dunvdavrxjl dreazshw arrfeo amxmodf aypeunsy ayrvhczj ahdpbjkni aimwvouazug abxvqgofe aqyib ahxpcabpd aegvvl aljmw llzsmeo lluscekzf luiwy lvrwfilgodj lrvci lpyvtlqgyg lkihxielive lmvylfdlb lxhvkikad lrmqdsohda llzcw wyruzto wijpf wvimevizdy whacj wlqscni wmqsbskg wubkeihe whhcb wbqglevyd wnana wcnjrnhl aghon axkzx atkhimqrm lzewc lynbsp logkfmqwk wjzeygwz wvktvyvyq wtdakfvphu)

answers = %w(qcazn)
s = Shiritori.new(words - answers, answers - [answers.last])

def solve(shiritori, word, win_patterns = [], lose_patterns = [])
	followers = shiritori.followers(word)
	if followers.empty? then
		if shiritori.answers.size.even? then
			win_patterns << shiritori
		else
			lose_patterns << shiritori
		end
	end
	followers.each do |w|
		solve(shiritori.answer(word), w, win_patterns, lose_patterns)
	end
	return win_patterns, lose_patterns
end

win_patterns, lose_patterns = solve(s, answers.last)
win_patterns.map do |win_pattern|
	lose_patterns.map do |lose_pattern|
		if win_pattern.answers.include?(lose_pattern.answers) then
			nil
		else
			win_pattern
		end
	end
end.flatten.uniq.each do |pattern|
	p pattern.answers
end

■ Super Hackers: PAC-MAN

どう考えても Super Hackers枠の本番ですね。 シミュレータを書いて手動で動かし、その結果を送信する形で得点・・・ が、敵数匹の動きがバグってるみたいで、微妙にしか動かなかったわ。 たぶん、途中でテストも書いてないのに豪快にリファクタリングしたのが原因ですね。 なんとか今までの得点を越えるくらいは得点できていたが。

てか、いま気づいたけど敵の一種類は実装がカラじゃねーの。ダメじゃねーか。 書いたソースコードはこんな感じ。 ヒアドキュメントできれいにマップを表現できた時点で8割くらい満足してしまった気がする。参考になる部分てそこらへんだけかもしれない。

あ。キレイで正常な動きにしてくれる diff 募集中・・・

#!/usr/bin/env ruby1.9


class Map
  attr_reader :dots, :player, :now
	def initialize(t, w, h, map)
		@time = t
    @now = 0
		@width = w
		@height = h
		@map = map.split("\n")
    @dots = []
    @enemies = []
    @inputs = []
    search_character
	end

  def search_character
    for x in 1..@width do
      for y in 1..@height do
        case get(x, y)
        when '@'
          @player = Player.new(self, x, y)
        when 'V'
          @enemies << EnemyV.new(self, x, y)
          @dots << Dot.new(self, x, y)
        when 'H'
          @enemies << EnemyH.new(self, x, y)
          @dots << Dot.new(self, x, y)
        when 'L'
          @enemies << EnemyL.new(self, x, y)
          @dots << Dot.new(self, x, y)
        when 'R'
          @enemies << EnemyR.new(self, x, y)
          @dots << Dot.new(self, x, y)
        when 'J'
          @enemies << EnemyJ.new(self, x, y)
          @dots << Dot.new(self, x, y)
        when '.'
          @dots << Dot.new(self, x, y)
        end
      end
    end
  end
  def dump
    puts @map
  end

  def get(x, y)
    @map[y - 1][x - 1]
  end

  def set(x, y, v = ' ')
    @map[y - 1][x - 1] = v
  end

  def available(target, direction)
    x = target.x
    y = target.y
    case direction
    when :down
      y += 1
    when :left
      x -= 1
    when :up
      y -= 1
    when :right
      x += 1
    end
    unless get(x, y) == '#' then
      true
    else
      false
    end
  end

  def input(ch)
    @inputs << ch
    player_pos = [@player.x, @player.y]
    case ch
    when 'h'
      @player.left
    when 'j'
      @player.down
    when 'k'
      @player.up
    when 'l'
      @player.right
    when '.'
    when 'q'
      game_end
    end
    @enemies.each do |enemy|
      if @now == 0 then
        enemy.first_move
      else
        enemy.move
      end
    end
    @dots.each do |dot|
      if dot.enable? and get(dot.x, dot.y) then
        dot.write
      end
    end
    @enemies.each do |enemy|
      enemy.write
      next unless enemy.x == @player.x
      next unless enemy.y == @player.y
      next unless enemy.swap?(@player)
      game_end
    end
    @player.write
    @now += 1
  end

  def game_end
    @inputs.delete('q')
    puts "answer: #{@inputs.join}"
    puts "time:   #{@inputs.join.size}"
    exit
  end
end

class Dot
  attr_reader :x, :y
  def initialize(map, x, y)
    @map = map
    @x = x
    @y = y
    @enable = true
  end

  def enable?
    @enable
  end

  def disable
    @enable = false
  end
  
  def write
    @map.set(@x, @y, '.')
  end
end

class Character
  def swap?(target)
    return false unless self.x  == target.xx
    return false unless self.yy == target.y
    return true
  end
end

class Player < Character
  attr_reader :x, :y, :xx, :yy
	def initialize(map, x, y)
    @map = map
    @xx = @x = x
    @yy = @y = y
	end

  def left
    pre_walk
    @xx = @x
    @x -= 1
    walk
  end

  def down
    pre_walk
    @yy = @y
    @y += 1
    walk
  end

  def up
    pre_walk
    @yy = @y
    @y -=1
    walk
  end

  def right
    pre_walk
    @xx = @x
    @x += 1
    walk
  end

  def pre_walk
    @map.set(@x, @y, ' ')
  end

  def walk
    @map.dots.each do |dot|
      if dot.x == @x and dot.y == @y then
        dot.disable
      end
    end
  end

  def write
    @map.set(@x, @y, '@')
  end
end

class Enemy < Character
  attr_reader :x, :y, :xx, :yy
	def initialize(map, x, y)
    @map = map
    @xx = @x = x
    @yy = @y = y
	end

  def down
    @direction = :down
    @yy = @y
    @y += 1
  end

  def left
    @direction = :left
    @xx = @x
    @x -= 1
  end

  def up
    @direction = :up
    @yy = @y
    @y -= 1
  end

  def right
    @direction = :right
    @xx = @x
    @x += 1
  end

  def first_move
    pre_move
    case true
    when @map.available(self, :down)
      down
      return true
    when @map.available(self, :left)
      left
      return true
    when @map.available(self, :up)
      up
      return true
    when @map.available(self, :down)
      down
      return true
    end
  end

  def pre_move
    @map.set(@x, @y, ' ')
  end

  def auto_move
    case ways
    when 1
      case @direction
      when :down
        up
      when :left
        right
      when :up
        down
      when :right
        left
      end
      return true
    when 2
      if @map.available(self, :down) and @y + 1 != @yy then
        down
        return true
      end
      if @map.available(self, :left) and @x - 1 != @xx then
        left
        return true
      end
      if @map.available(self, :up) and @y - 1 != @yy then
        up
        return true
      end
      if @map.available(self, :right) and @x + 1 != @xx then
        right
        return true
      end
    when 3
    when 4
    end
    return false
  end

  def ways
    ways = 0
    ways += 1 if @map.available(self, :down)
    ways += 1 if @map.available(self, :left)
    ways += 1 if @map.available(self, :up)
    ways += 1 if @map.available(self, :right)
    return ways
  end

  def move
    pre_move
  end
  
  def write
    @map.set(@x, @y, self.to_s)
  end

  def to_s
    "E"
  end
end


class EnemyV < Enemy
  def move
    pre_move
    return if auto_move
    return if d_move
    case true
    when @map.available(self, :down)
      down
      return true
    when @map.available(self, :left)
      left
      return true
    when @map.available(self, :up)
      up
      return true
    when @map.available(self, :right)
      right
      return true
    end
  end
  def d_move
    dx = @map.player.x - @x
    dy = @map.player.y - @y
    y = 0 < dy ? :down : :up
    x = 0 < dx ? :right : :left
    if dy != 0 and @map.available(self, y) then
      y == :down ? down : up
      return true
    end
    if dx != 0 and @map.available(self, x) then
      x == :right ? right : left
      return true
    end
    return false
  end
  def to_s
    "V"
  end
end

class EnemyH < EnemyV
  def d_move
    dx = @map.player.x - @x
    dy = @map.player.y - @y
    y = 0 < dy ? :down : :up
    x = 0 < dx ? :right : :left
    if dx != 0 and @map.available(self, x) then
      x == :right ? right : left
      return true
    end
    if dy != 0 and @map.available(self, y) then
      y == :down ? down : up
      return true
    end
    return false
  end
  def to_s
    "H"
  end
end

class EnemyL < Enemy
  def turn_left_and_go
    case @direction
    when :down
      if @map.available(self, :right) then
        right
        return true
      end
    when :left
      if @map.available(self, :down) then
        down
        return true
      end
    when :up
      if @map.available(self, :left) then
        left
        return true
      end
    when :right
      if @map.available(self, :up) then
        up
        return true
      end
    end
    return false
  end

  def turn_right_and_go
    case @direction
    when :down
      if @map.available(self, :left) then
        left
        return true
      end
    when :left
      if @map.available(self, :up) then
        up
        return true
      end
    when :up
      if @map.available(self, :right) then
        right
        return true
      end
    when :right
      if @map.available(self, :down) then
        down
        return true
      end
    end
    return false
  end

  def go_straight
    case @direction
    when :down
      if @map.available(self, :down) then
        down
        return true
      end
    when :left
      if @map.available(self, :left) then
        left
        return true
      end
    when :up
      if @map.available(self, :up) then
        up
        return true
      end
    when :right
      if @map.available(self, :right) then
        right
        return true
      end
    end
    return false
  end

  def move
    pre_move
    return if auto_move
    l_move
  end

  def l_move
    return if turn_left_and_go
    return if go_straight
    return if turn_right_and_go
  end

  def to_s
    "L"
  end
end

class EnemyR < EnemyL
  def move
    pre_move
    return if auto_move
    r_move
  end

  def r_move
    return if turn_right_and_go
    return if go_straight
    return if turn_left_and_go
  end
  def to_s
    "R"
  end
end

class EnemyJ < EnemyR
  def move
    pre_move
  end
  def to_s
    "J"
  end
end

map1 = Map.new(50, 11, 7, <<'EOM')
###########
#.V..#..H.#
#.##...##.#
#L#..#..R.#
#.#.###.#.#
#....@....#
###########
EOM

map2 = Map.new(300, 20, 17, <<'EOM')
####################
###.....L..........#
###.##.##.##L##.##.#
###.##.##.##.##.##.#
#.L................#
#.##.##.##.##.##.###
#.##.##L##.##.##.###
#.................L#
#.#.#.#J####J#.#.#.#
#L.................#
###.##.##.##.##.##.#
###.##.##R##.##.##.#
#................R.#
#.##.##.##.##R##.###
#.##.##.##.##.##.###
#@....R..........###
####################
EOM

map3 = Map.new(700, 58, 17, <<'EOM')
##########################################################
#........................................................#
#.###.#########.###############.########.###.#####.#####.#
#.###.#########.###############.########.###.#####.#####.#
#.....#########....J.............J.......###.............#
#####.###.......#######.#######.########.###.#######.#####
#####.###.#####J#######.#######.########.###.##   ##.#####
#####.###L#####.##   ##L##   ##.##    ##.###.##   ##.#####
#####.###..H###.##   ##.##   ##.########.###.#######J#####
#####.#########.##   ##L##   ##.########.###.###V....#####
#####.#########.#######.#######..........###.#######.#####
#####.#########.#######.#######.########.###.#######.#####
#.....................L.........########..........R......#
#L####.##########.##.##########....##....#########.#####.#
#.####.##########.##.##########.##.##.##.#########.#####.#
#.................##............##..@.##...............R.#
##########################################################
EOM

#map1.dump
#p map1.get(1, 1)
#p map1.set(1, 1)
#map1.dump

map1.dump
while input = gets do
  input.scan(/[hjkl.q]/).each do |ch|
    map1.input(ch)
    map1.dump
  end
end

インデントずれてるんだが、オレのシマの vim では正常に表示できていた。 デバッグすんのがくそめんどうだけど、設計レベルの崩壊はあんまなさそうなので、もっかいかけば正しいものが書けそう。 たぶん、もうやらんけどな。

■ USP友の会　第1回いたこ会　で話します

今月は8月の28日に開催される USP友の会の第1回いたこ会にて「シェルスクリプトで頭の体操」というテーマでお話させていただきます。

「有識者」「いたこ」とは恐縮です・・・

いたこ

イタコは、日本の東北地方などで口寄せ（神仙や死者・行方不明者の霊などを自身に乗り移らせてその言葉を語ること）を行う巫女で巫の一種。 シャーマニズムに基づく信仰習俗上の職である。

イタコには霊的な力を持つとされる人もいるが、実際の口寄せは心理カウンセラー的な面も大きい。死者あるいは音信不通者との縁を忘れられないでいる、あるいは時々思い出し供養に訪れる人々に対し、それらの気持ちを汲み取り、話を聞くことによってその心を和らげるのが、イタコとその信仰の本来の姿なのかも知れない。ただそうしてあげるためにはクライアントの心情を読み取る力（一種のコールドリーディング）は必須である。

出展：ウィキペディア日本語版

開催概要は以下のとおりです。よろしければどうぞご参加ください。 ＃ とはいっても、スラッシュドットにも掲載されていたので、すでに空きがあるのかよく把握できていません・・・

======================================================================
	USP友の会　第1回いたこ会 開催のお知らせ
======================================================================

USP友の会は、日本で唯一のシェルプログラミングコミュニティとして、
勉強会や飲み会などを定期的に行っています。
その活動の一環として、日本のLL界を盛り上げるため、
今回、外部の有識者をお招きしての講演 「いたこ会」 を企画しました。
さまざまな分野で活躍している人の楽しいトークと
シェルスクリプト技術の競演を、一緒に楽しみましょう！

記念すべき第1回目となる今回は
ゆーすけべーさん（株式会社ワディット代表取締役社長）の「PerlでCLIアプリ！」と、
takano32さん（グリー株式会社/日本UNIXユーザ会幹事）の
「シェルスクリプトで頭の体操」という2本立てでお送りします。

また、最後の15分でLT大会を予定！
誰でも参加可能です。シェルスクリプトに関するテーマから、
ライフハック、エンジニアライフ、OSS、コミュニティ活動、LL、勉強会等々…
1人あたり5分で、思いのたけを発表してください。
（発表希望の方は、申込フォームより申告してください。
発表希望者多数の場合は、抽選になります。
発表者の方には、後日主催者より連絡をいたします）

================================================================
■開催概要■
日　時：8月28日（土）15時～17時30分（開場14時30分）
会　費：500円
懇親会：18時30分～
懇親会会費：4000円（学生さん 1500円・受付時に申告してください）
================================================================
■アジェンダ■
14時30分　　　　　／開場
15時　　～15時15分／はじめに（全員自己紹介）
15時15分～16時　　／おはなし１「PerlでCLIアプリ！」ゆーすけべーさん
16時10分～16時55分／おはなし２「シェルスクリプトで頭の体操」takano32さん
17時　　～17時30分／大LT大会、おたのしみ抽選会
18時　　～　　　　／懇親会
================================================================

お申込希望の方は、告知ーずよりお願いします。
http://kokucheese.com/event/index/3951/

■ RubyKaigiの懇親会に参加するか考えてる

そんなこんなで、今年のRubyKaigiは三日目のみの参加になりそうです。 しかも、個人スポンサーなのに懇親会出れないかも・・・

どなたか二日目の夜につくばの床を貸してくださる方とかいらっしゃいましたらうれしいです。 同じふとんでキャッキャウフフするのもやぶさかでは・・・

という冗談はさておき、もしよろしければコメントとかくださいな。 いたこ会のあとに直行します。逆に懇親会のチケット買いあげてやんよ、というコメントも歓迎です。その場合はUSP友の会の方々とキャッキャウフフします。

ああー。そういえば、引越しやら転職やらでゴタゴタしておったりするわけで、Ruby周りの活動できてなくてすみません。 落ち着いたら早く ia64.s の "mov r8 = ar.bsp" のあたりが正しいのか調べたい・・・っていうか、軽く調べたらアプリケーションからはread-onlyとかでてきたのでこの領域にポインタセットして上書きしてるMEMCPYは爆発し・・・じゃなくて修正するべきっぽい。と思ったら、bspの値は書き換え不可でbspが示す先はいいのか。ややこしい！

"br.ret.sptk.many" の br って汎用レジスタの名前かと思ったら ブランチレジスタ のことだった！ けっこー、気合いりそうだな。