電波ビーチ

☆（ゝω・）v

AOJ ALDS1_6_C Quick Sort

AOJ Algorithm ruby

ソートアルゴリズムの実装自体やったことないぜ！！！！！！！！！メリークリスマスイヴ！！！！！！！！！

n 枚のカードの列を整列します。１枚のカードは絵柄(S, H, C, またはD)と数字のペアで構成されています。これらを以下の疑似コードに基づくクイックソートで数字に関して昇順に整列するプログラムを作成してください。partition は ALDS1_6_B の疑似コードに基づくものとします。

また、与えられた入力に対して安定な出力を行っているかを報告してください。ここでは、同じ数字を持つカードが複数ある場合、それらが入力で与えられた順序であらわれる出力を「安定な出力」とします。

安定な出力かどうか とは

クイックソートは与えられた配列の要素同士を交換するので安定でない配列ということらしい。安定な出力をするソートにはマージソートがある。

クイックソートとマージソートを実装してそれぞれに配列を投げて得られた結果が同じならば安定、異なれば非安定ということにする。

マージソート

分割統治してソートする感じ。半分ずつに分割する部分とそれを統合（merge）する部分がある

  • 半分ずつに分ける
  • 分けたうちの左側と右側を比較
    • 先頭から比較していって小さい方を選択
  • 比較してできた結果からさらに大きい単位で比較

ソート済のLとRをみたときにそれぞれ上の処理をやるとできた結果Aは全体でソートされている。これを小さい単位（2数の比較）から大きくしていく感じ

def merge(a, l, m, r)
  l_arr = a[l, m-l] << 10000000000000000000
  l_i = 0
  r_arr = a[m, r-m] << 10000000000000000000
  r_i = 0

  (l...r).each do |idx|
    # 小さい方から入れていく
    if l_arr[l_i] <= r_arr[r_i]
      a[idx] = l_arr[l_i]
      l_i+=1
    else
      a[idx] = r_arr[r_i]
      r_i+=1
    end
  end
end

def merge_sort(a, left, right)
  if 1 < right-left
    mid = (right+left)/2
    merge_sort(a, left, mid)
    merge_sort(a, mid, right)
    merge(a, left, mid, right)
  end
end

これのmergeメソッドのとこが統合に当たる。あるいは配列ごと作ってぶちこむ手もある。LLならこっちのが簡単そう*1。どっちもやってるこたぁおんなじ

def merge(left, right)
  ret = []
  loop do
    break if left.size.zero? && right.size.zero?
    # 先頭の小さい方から入れていく
    if left.empty? || (!right.empty? && right.first <= left.first)
      ret << right.shift
    elsif right.empty? || (!left.empty? && left.first < right.first)
      ret << left.shift
    else
      p "fuck"
      exit
    end
  end 
  ret
end

def merge_sort(a)
  return a if a.size == 1
  mid = a.size/2
  left = a[0, mid]
  right = a[mid, mid+1]
  left = merge_sort(left)
  right = merge_sort(right)
  return merge(left, right)
end

クイックソート

これも分割統治。配列から適当なpivotを決めて、pivotより左側に「pivotより小さい要素」、右側に「pivotより大きい要素」がくるようにする。この操作をpartitionと呼ばうらしい。partitionによって配列の更新と、更新後のpivotのインデックスを返すようにすれば、pivotより小さい部分の配列と大きい部分の配列に分割できるのでそれらに対して同じように処理していくのだ。partitionの部分はなんか説明しにくいので見てくれ

def partition(a, l, r)
  pivot = a[r-1]
  j = l-1
  (l...r).each do |i|
    if a[i] <= pivot
      j+=1
      a[j], a[i] = a[i], a[j]
    end
  end
  return j
end

def quick_sort(a, l, r)
  if 1 < r-l
    q = partition(a, l, r)
    quick_sort(a, l, q)
    quick_sort(a, q+1, r)
  end
end

だいたいの言語のsort関数なんかはサイズが小さいときはマージソートで大きいときはクイックソート使うらしいみたいなのを聞いたことがある。知らんけど

実装

入力される要素に合わせて上で書いたやつを書き換えたりなんかしたり

def partition(a, l, r)
  pivot = a[r-1][1]
  j = l-1
  (l...r).each do |i|
    if a[i][1] <= pivot
      j+=1
      a[j], a[i] = a[i], a[j]
    end
  end
  return j
end

def quick_sort(a, l, r)
  if 1 < r-l
    q = partition(a, l, r)
    quick_sort(a, l, q)
    quick_sort(a, q+1, r)
  end
end


def merge(a, l, m, r)
  l_arr = a[l, m-l] << ['死', 10000000000000000000]
  l_i = 0
  r_arr = a[m, r-m] << ['死', 10000000000000000000]
  r_i = 0
  
  (l...r).each do |idx|
    # 小さい方から入れていく
    if l_arr[l_i][1] <= r_arr[r_i][1]
      a[idx] = l_arr[l_i]
      l_i+=1
    else
      a[idx] = r_arr[r_i]
      r_i+=1
    end
  end
end

def merge_sort(a, left, right)
  if 1 < right-left
    mid = (right+left)/2
    merge_sort(a, left, mid)
    merge_sort(a, mid, right)
    merge(a, left, mid, right)
  end
end

n = gets.to_i
a = []
n.times do
  a << gets.chomp.split.map{|x| x.match?(/\d/) ? x.to_i : x}
end
b = a.clone
quick_sort(a, 0, n)
merge_sort(b, 0, n)

puts a == b ? "Stable" : "Not stable"
a.each do |av|
  puts "#{av[0]} #{av[1]}"
end

はい よくできました えらいね。クリスマスプレゼントは職がいいです

*1:LLなら軽率に配列を作ったりぶっ壊すのが楽という雑魚認識

【ruby】連番をキーとし配列を値にしてるハッシュ

ruby 
irb(main):016:0> n = 4
=> 4
irb(main):017:0> table = (1..n).to_a.zip(Array.new(n, Array.new)).to_h
=> {1=>[], 2=>[], 3=>[], 4=>[]}
irb(main):018:0> table[1] << 1
=> [1]
irb(main):019:0> table
=> {1=>[1], 2=>[1], 3=>[1], 4=>[1]}

👿

irb(main):030:0> table = (1..n).to_a.map{|i| [i, Array.new]}.to_h
=> {1=>[], 2=>[], 3=>[], 4=>[]}
irb(main):031:0> table[1] << "あばばばばば"
=> ["あばばばばば"]
irb(main):032:0> table
=> {1=>["あばばばばば"], 2=>[], 3=>[], 4=>[]}

👼

Ruby オブジェクト -> hash -> json

ruby

アロー演算子じゃないです。

インスタンス変数: 値 みたいな感じで

require 'json'
require 'time'

class Hito
  attr_accessor :age, :name, :id
  def initialize(age, name)
    @age = age
    @name = name
    @id = Time.new.iso8601(6)
  end
end

human = Hash.new

a = Hito.new(392, "dare")
b = Hito.new(49, "kimi")
c = Hito.new(113, "watashi")

# ただハッシュにぶちこんだだけのオブジェクトをjsonizeする
def jsonize(dict)
  ret = Hash.new{|h,k| h[k] = {}}
  dict.map{|k, v|
    ret[k] = v.instance_variables.map{|var| [var, v.instance_variable_get(var)]}.to_h
  }.to_json
  open("hoge.json", 'w') do |io|
    JSON.dump(ret, io)
  end
end

human[a.id] = a
human[b.id] = b
human[c.id] = c

jsonize(human)

ハッシュ内ハッシュ Hash.new{|h,k| h[k] = {}}はこれ

qiita.com

インスタンス変数: 値はこれ

qiita.com

特異メソッドにしたいだけ、ならばmodule_functionは要らない

ruby

module_functionを使うと確かに特異メソッドが作れる。が、それで作られるメソッドは、同時にプライベートメソッドでもある。（ 参考：伊藤淳一「プロを目指すためのRuby入門 言語仕様からテスト駆動開発・デバッグ技法まで」kindle版 , 技術評論社, 位置 7425 ）

hoge.rb

module Hoge
  module_function
  def hoge(n)
     "ほげ"*n
  end
end

main.rb

require_relative 'hoge'

def yobu
  puts Hoge.hoge(3)
end
    
yobu

結果

ほげほげほげ

Hogeには外部から呼び出すためのメソッドだけおいておけばいい、という場合に、プライベートメソッドは不要である。むしろ上記の場合だとmain.rbから呼ぶ際にレシーバを指定する方法がそもそも無いのでプライベートメソッドは必要ない。（ここんとこ理解および日本語があやしいかもしれないので間違ってたらそっと教えてください）

解決法

特異クラスにしてやればよい。

hoge.rb

module Hoge
  # module_function <- プライベートメソッドは必要ない
  class << self
    def hoge(n)
       "ほげ"*n
    end
  end
end

参考

qiita.com

rubyの便利コマンドラインパーサoptparseのdescriptionがsummaryなので見やすくしたい

ruby

なにをいってるかわからねータイトルですが。

rubyにはoptparseっていうコマンドラインパーサが標準ライブラリ*1があり、使う機会があった

github.com

-hでヘルプを表示できるのだが、たとえばこんなやつ

require "optparse"

OptionParser.new do |opt|
  begin
      # バージョンを追加
      opt.version = "0.0.1"
      # リリース日を追加
      opt.release = "2018-11-12"
      # 名前を追加
      opt.program_name = ""
      # Usageで最初に表示されるやつ
      opt.banner = "Usage: #{opt.program_name} [options] [directory]"
      # helpとかUsageで表示されるときのサマリーが始まるまでの行頭からの幅
      summary_width = 32
      opt.summary_width = summary_width
      # 同じくコマンドのインデント
      summary_indent = 4
      opt.summary_indent = ' ' * summary_indent
      # summaryの幅を改行時にも揃えたい。長文で折り返した際も同じようにインデントするようにしたい
      # opt.onでオプションとそのdescを追加
      opt.on("-x", "所詮サマリーなのでそもそも長文を書くものではないんだけど、それにしてもターミナル幅が短いとめちゃくちゃ読みにくいしつらい。\n改行なんてしようもんならもっとひどいことになる。とても読めたものではない"){ |v|
          options[:a] = v
      }
      opt.separator("")
      opt.on("-h", "--help", "show help."){
          puts opt.help
          exit
      }
      opt.on("-v", "--version", "show version."){
          puts opt.ver
          exit
      }
      opt.parse!(ARGV)
  rescue OptionParser::InvalidOption => e
      puts e.message
      return
  end
end

を、ヘルプオプションで表示しようとすると、ターミナル幅が70とかだとこんな感じになっちゃう f:id:or3:20181112101242p:plain

これがストレスなのでちゃんとインデント付きで折り返してくれるようなヘルパー関数を作ってあげた

github.com

（中見ればわかりますが力ずくでよろしくやっているだけ...）

*1:rubyの文化知らんのだが組み込みgem?でいいのかな

【AOJ】Rubyで2次元配列を連番で初期化 && Rubyでpythonのisdigitっぽいやつ

ruby AOJ 競プロ

AOJ ITP1_6_B

タイトルのやつでおいしい書き方ができずに少しハマった。

２次元配列を連番で初期化

map内での宣言で要素を初期化できる。範囲オブジェクトをto_aで配列にしてぶちこんだ。

cards = Array.new(4).map { Array.new((1..13).to_a) }
=> [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]]

isdigitっぽいやつ

pythonだとよくある感じの書き方で、文字列のリストの要素の中で数値に変換できるやつは変換してしまう、というやつはisnumericを使う。

target = list(map(lambda a: int(a) if a.isnumeric() else a, input().split()))

べつにisdigitでもいいんだけど、なんかのやつでなぜか漢数字を変換しなくちゃいけない場面があって以来isnumeric万能ってなったので使っている。

kk6.hateblo.jp

Rubyにはそんな便利なメソッドは無いらしい。調べると正規表現でやっているのをよく見かけるので真似した。

konbu13.hatenablog.com

こちらのをパクらせていただきました。ありがとうございます。

今回はfloatにも対応するようにしてみた。三項演算子を入れ子にしたのだが、いちいちmatchを判断しているところが冗長で遅そう。正規表現力が圧倒的に足りない。

arr = ["unk0", "321", "0.00220", "y00011", "321.32xx334" "127.0.0.1"]
arr.map { |t| t.match? (/^\d+\.?\d+$/) ? (t.match? (/\./) ? t.to_f : t.to_i) : t }
=> ["unk0", 321, 0.0022, "y00011", "321.32xx334", "127.0.0.1"]