2つのバケツ問題（Ruby）

反復深化/アルゴリズム講座
おもしろそうな問題を見つけました。

8リットルと5リットルのふたつのバケツを使って1リットルの水を最短手順で川からくみあげて下さい。

http://www.ic-net.or.jp/home/takaken/pz/index3.html

　
Ruby で解いてみました。それぞれのバケツには、空にするかいっぱいに水を入れるか、もう一方に移し替えるかの 3通りの場合があります。すべての手順に 0~5 の番号を振ります。

8リットル: 空(0), 入れる(1), 8→5に移す(2)
5リットル: 空(3), 入れる(4), 5→8に移す(5)

　
最短手順なので、幅優先探索を使います。
bucket_problem.rb

def move(mass, f, t)
  if (a = mass - t) >= f
    t += f
    f = 0
  else
    t = mass
    f -= a
  end
  [f, t]
end


procedures = [[[1], 0, 0], [[4], 0, 0]]
loop do
  pr = procedures.shift
  
  case pr[0][-1]
  when 1 then pr[1] = 8
  when 4 then pr[2] = 5
  when 0 then pr[1] = 0
  when 3 then pr[2] = 0
  when 2
    pr[1], pr[2] = move(5, pr[1], pr[2])
  when 5
    pr[2], pr[1] = move(8, pr[2], pr[1])
  end
  
  if pr[1] == 1 or pr[2] == 1
    p pr[0]
    exit
  end
  
  6.times do |i|
    a = pr[0].dup
    next if a[-1] == i    #高速化用
    a << i
    procedures.push([a, pr[1], pr[2]])
  end
end

実行してみます。

$ time ruby bucket_problem.rb
[1, 2, 3, 2, 1, 2, 3, 2]

real	0m0.384s
user	0m0.364s
sys	0m0.016s

　
上の手順は翻訳するとこうなります。

手順	8L	5L
8Lに入れる	8	0
8→5	3	5
5Lを空	3	0
8→5	0	3
8Lに入れる	8	3
8→5	6	5
5Lを空	6	0
8→5	1	5

これで確かに 8L のバケツに 1L 残りました！
　
ちなみに、意味ある最長手順は [4, 5, 4, 5, 0, 5, 4, 5, 4, 5, 0, 5, 4, 5] です。また、8リットルと5リットルのバケツで4リットルを作るのにも挑戦してみて下さい。

汎用性のあるバージョンに書き換えてみました。コードはこちらです。バケツの大きさと計る値を指定することができます。可能なすべての場合を出力し、無意味な解はできるだけ除きますが、一部冗長な解も出力してしまいますので注意して下さい。

飛車と角の利き（Ruby）

問題：

飛車と角を将棋盤（9×9）の上にひとつづつおきます。このとき、飛車か角によって（相手の）駒が取られる位置を、飛車と角の「利き」ということにします。
飛車の「利き」の上に角があるとき、その先の飛車の「利き」は（角にさえぎられて）ありません。角の場合も同様です。
飛車と角は重なりません。
飛車と角が採りうる位置をすべて採るとき、「利き」の総和は何個になるでしょうか。

　
Ruby で解いてみます。総当り法で、特に何のくふうもしていません。

class Field
  def clear
    a = Array.new(11, 1)
    @field = Array.new(9) {[1] + [0] * 9 + [1]}
    @field.unshift(a)
    @field.push(a)
  end
  
  def set(x, y, koma)
    @field[y][x] = koma
  end
  
  def get(x, y)
    @field[y][x]
  end
  
  def count
    counter = 0
    move_koma do |x, y|
      counter += 1 if get(x, y) == 4
    end
    counter
  end
  
  def set_kiki(x, y, dir)
    loop do
      x += dir[0]
      y += dir[1]
      a = get(x, y)
      return if a == 1 or a == 2 or a == 3
      set(x, y, 4)
    end
  end
end

def move_koma
  1.upto(9) do |y|
    1.upto(9) {|x| yield(x, y)}
  end
end


f = Field.new
counter = 0
move_koma do |xh, yh|
  move_koma do |xk, yk|
    next if xh == xk and yh == yk
    f.clear
    f.set(xh, yh, 2)
    f.set(xk, yk, 3)
    
    #飛車
    [[-1,  0], [1,  0], [0, -1], [0, 1]].each {|dir| f.set_kiki(xh, yh, dir)}
    #角
    [[-1, -1], [-1, 1], [1, -1], [1, 1]].each {|dir| f.set_kiki(xk, yk, dir)}
    
    counter += f.count
  end
end
puts counter    #=>149424

わざわざ（一部）オブジェクト指向プログラミングで解く必要はないのですが、この方が（自分に）見やすいかと思ってこうしました。

将棋盤（@field）の周囲には番兵を置いてあります。0 が空白、1 が番兵、2 が飛車、3 が角、4 が「利き」です。
　

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

　
　
よく似た問題に、チェスの「エイト・クイーン問題」というのがあります。過去記事で扱っているので、よろしければ御覧下さい。

Ruby で png 画像を自力生成（その2）

前回 png 画像を生成してみた続き。
　
こんなの。

コードはこんな感じ（画像データの生成部分のみ）。前回エントリを参照。

width, height = 400, 400

raw_data = []
height.times do |h|
  ob = []
  width.times {|w| ob << [0, 0, ((w - width / 2) ** 2 + (h - height / 2) ** 2) % 256]}
  raw_data << ob
end

　
またこんなのも。

双曲線を使う。

  width.times {|w| ob << [0, ((w - width / 2) ** 2 - (h - height / 2) ** 2) % 256, 0]}

Ruby で png 画像を自力生成できるらしいですよ

このところ脳みそが腐って全然プログラミングとかできないのだが、Ruby 愛はちっとも減じていないので、他人のブログをパクってエントリを書きます。「パクって」はいい言葉じゃないですね。とにかく唐突に「png ruby」でぐぐってみましたら、Ruby コミッタのまめさんのブログがヒットしました。
だいぶ昔の記事ですね。ほほう、Ruby で png 画像を生成するかあ。これはおもしろそうですね。png の生成は結構むずかしいらしいのですが、Ruby だとそんなにむずかしくないと。とりあえず、まめさんのコードをコピペ、実行してみます。赤色のグラデーションをもった画像を生成します。もともとは Ruby 1.9 用らしいですが、Ruby 2.3.3 でまったく修正なしに走りました。（Linux Mint 18.2）

コード（コピペほぼそのまま）。
gradation.rb

require "zlib"

width, height = 100, 20
depth, color_type = 8, 2

# グラデーションのベタデータ
line = (0...width).map {|x| [x * 255 / width, 0, 0] }
raw_data = [line] * height

# チャンクのバイト列生成関数
def chunk(type, data)
  [data.bytesize, type, data, Zlib.crc32(type + data)].pack("NA4A*N")
end

# ファイルシグニチャ
print "\x89PNG\r\n\x1a\n"

# ヘッダ
print chunk("IHDR", [width, height, depth, color_type, 0, 0, 0].pack("NNCCCCC"))

# 画像データ
img_data = raw_data.map {|line| ([0] + line.flatten).pack("C*") }.join
print chunk("IDAT", Zlib::Deflate.deflate(img_data))

# 終端
print chunk("IEND", "")

"zlib" ライブラリは標準添付ライブラリなので、Gem としてインストールする必要はありません。実行は

$ ruby gradation.rb > gradation.png

みたいな感じ。こうして生成された png 画像はこれだ！
　

　
小さいけれど、ちゃんと赤色のグラデーションとして生成されていますね。うーん、いいなあこれ。

ふつうのブログならこれを解説するわけだが、面倒なのでしない。というか、まめさんの説明がすごくわかりやすいので、自分のは不要なのである。といって、じつは自分はまめさんの記事を読んで密かにぐぐったので、それだけ書いておこう。

まず、標準添付ライブラリの "zlib" が話題になっているが、これって何か？　これはここを見るといいですね。つまり zlib とは、データを圧縮するアルゴリズムであるそうだ。Linux では gzip コマンドというので使われているらしいが、しかしよく Windows で使われている zip ってやつとは関係ないらしい。zlib は「可逆圧縮」、つまり解凍すると完全にもとのデータが復元できるということで、じつは png 画像ファイルの圧縮もこれであり、そう、png は劣化しないのですね。これは皆んな知っているだろう。ちなみに jpg は劣化するのですね。というわけで、png 画像を作るには、メインの画像データは zlib で圧縮すればよいというわけである。そのためのライブラリなのだった。

あとひとつ。まめさんの「臼NG はみんな見たことあるはず」がわからなかった。「臼NG」である。自分は見たことがない。これはわからないということでぐぐったら、ここがヒットした。ははあ、ファイルシグニチャ*1の「\x89P」が Shift_JIS で「臼」なわけね。納得。ただし、これを Linux の Ruby で実感してみようと思ったが、

require 'kconv'

puts "\x89PNG".tosjis.encode("UTF-8")     #=>臼NG

しかやり方がわからなかった。"kconv" を使うのは Ruby 2.3 っぽくないのだけれど*2。どうやるといいのかな。（つまりは、バイナリ→Shift_JIS→UTF-8 の変換を文字列ですること。これ、すごく時間をかけて調べたのだけれどわからなかった。もちろんマジックコメントを使えば簡単なのだが。）

自分も上のコードを少しだけ変えて、完全にランダムな色で打点した png 画像を作ってみた。コードは変更部分のみ。
random_color_png.rb

width, height = 100, 100

# グラデーションのベタデータ
raw_data = []
height.times do
  raw_data << width.times.with_object([]) do |i, ob|
    ob << [rand(256), rand(256), rand(256)]
  end
end

画像。
　


こんな具合ですね。

*1:png ファイルの先頭部分で、これは png ファイルですよという宣言。

*2:どうも最近の Ruby だと、エンコーディングをわざとまちがえて（笑）文字化けさせるということが想定されていないらしい。文字列が自分のエンコーディングの情報をもっています。で、バイナリから例えば UTF-8 へという無意味な変換ができないらしい。そういうことをやると Encoding::InvalidByteSequenceError が出ます。

paiza オンラインハッカソン vol.6 をやってみた

これも挑戦。使用言語は Ruby。どれも超簡単なので簡潔に。
　

六村リオ

問題。結果。

コード。

operations = []
gets.to_i.times {operations << gets.split.map(&:to_i)}

water = coffee = 0.0

operations.each do |op, q|
  case op
  when 1 then water  += q
  when 2 then coffee += q
  when 3
    r = 1 - q / (water + coffee)
    water  *= r
    coffee *= r
  end
end

puts (coffee * 100 / (water + coffee)).to_i

霧島京子

問題。結果。

コード。

n = gets.to_i
masu = gets.split.map(&:to_i)
deme = []
gets.to_i.times {deme << gets.to_i}

deme.each do |pos|
  memo = []
  loop do
    if pos == n - 1
      puts "Yes"
      break
    elsif memo.include?(pos) or pos < 0 or pos >= n or masu[pos].zero?
      puts "No"
      break
    else
      memo << pos
      pos += masu[pos]
    end
  end
end

緑川つばめ

問題。結果。

コード。

n = gets.to_i

puts n + n / 10 + n % 10

全体的に何だかどんどん簡単になっているような…。プログラミングを始めたばかりくらいの人向けかな？

paiza オンラインハッカソン vol.5 をやってみた

使用言語は Ruby です。画像クリックで詳細が出ます。
　

手紙の暗号を解読

簡単。

コード。

st = gets

result = ""
0.step(st.length - 1, 2) {|i| result += st[i]}
puts result

会社の入社試験

超簡単。こんな入社試験、ある筈がないですね。

コード。

num = gets.to_i
data = []
num.times {data << gets.to_i}

7.times do |day|
  sum = 0
  (num / 7).times {|i| sum += data[i * 7 + day]}
  puts sum
end

　
ここでレナちゃんか、ミナミちゃんのいずれかを選ばないといけない！

ミナミを選んでみる

問題はこれ。

これもやさしい。

コード。

x, y = gets.split.map(&:to_i)
field = []
y.times {field << gets.split.map(&:to_i)}

result = []
field.transpose.each do |line|
  ar = Array.new(y, 0)
  result << ar.fill(1, 0, line.count(1))
end
result.transpose.reverse_each {|x| puts x.join(' ')}

transpose, fill, count, reverse_each など、僕が普段あまり使わない Array の便利な組み込みメソッドを使って解きました。Ruby の表現力の高さが出ているのではないか知らん。
　

レナを選んでみる

問題はこれ。

うーん、大して工夫していないのに…。判定は条件分岐（if文など）を使わず、ビット演算でやったのが工夫したくらい。

コード。

x, y, num = gets.split.map(&:to_i)
table, area = [], []
y  .times {table << gets.split.map(&:to_i)}
num.times {area  << gets.split.map(&:to_i)}

MaskValue = 2 ** 10 - 1
@mask = Array.new(y) {Array.new(x, 0)}

def make_mask(x1, y1, x2, y2)
  y1.upto(y2) do |y|
    x1.upto(x2) {|x| @mask[y][x] |= MaskValue}
  end
end

area.each do |ar|
  make_mask(ar[0] - 1, ar[1] - 1, ar[2] - 1, ar[3] - 1)
end

y.times do |y1|
  x.times {|x1| table[y1][x1] &= @mask[y1][x1]}
end

puts table.flatten.inject(&:+)

　
今回も特にむずかしいことはなし。

paiza オンラインハッカソン vol.4 をやってみた

またまた挑戦してみました（ヒマ人^^;）。使用言語は Ruby です。画像クリックで詳細が出ます。
　

ミッション1

こりゃ簡単すぎるだろう。

コード。

data = []
gets.to_i.times {data << gets.to_i}

puts data.inject(&:+)

ミッション2

これも超簡単。

コード。

data = []
gets.to_i.times {data << gets.split.map(&:to_i)}

result = 0
data.each do |d|
  a = d[0] - d[1]
  result += a * d[2] if a > 0
end
puts result

ミッション3

簡単なのだけれど、たぶんもっといいアルゴリズムがあるでしょう。自分のコードに不満。

コード。

len, koma_size = gets.split.map(&:to_i)
koma = []
koma_size.times {koma << gets.to_i}

max = point = koma[0, len].inject(&:+)
(koma_size - len).times do |i|
  point = point - koma[i] + koma[i + len]
  max = point if point > max
end
puts max

コメントで60点とか言っている人は、ループを二重にしているのだと思う。
　
全体的にこれまでの paiza オンラインハッカソンに比べて極端に簡単。これでは差がつかないのではないか。