アルゴ式をRubyで解く。【プログラミングに慣れ親しむ】

AC (Accepted)：提出したプログラムが正解であることを意味します (AC 以外のメッセージは不正解です)
WA (Wrong Answer)：提出したプログラムの出力が正しくありません
TLE (Time Limit Exceeded)：問題で指定された実行制限時間以内にプログラムが終了しませんでした
MLE (Memory Limit Exceeded)：使用メモリ量が問題で使用制限メモリ量を超えました
CE (Compile Error)：提出したプログラムのコンパイルに失敗しました
RE (Runtime Error)：配列外参照、ゼロ除算などの原因により、プログラムの実行中にエラーが発生しました
IE (Internal Error)：内部のエラー、つまりジャッジシステムのエラーです

ハガユウキ

String#chomp

self の末尾から rs で指定する改行コードを取り除いた文字列を生成して返します。

ハガユウキ

四捨五入したいなら、round
切り上げしたいなら、ceil
切り捨てしたいなら、floor

ハガユウキ

rubyの$について

String#splitはデフォルトで、半角空白文字でセパレートする

ハガユウキ

Array#sumは要素の合計を返す。すげえ

ハガユウキ

Array#minで、要素の最小値を取得できる。すげえ

ハガユウキ

Array#maxは、最大の要素、もしくは最大の n 要素が降順に入った配列を返す
すご

ハガユウキ

rubyのreduceも地味に使える

ハガユウキ

reduceでデフォルト値を指定しなかったと、1回目のループで第一要素がresultに、第二要素がnumberに入っていた。。

  minimum_number = numbers.reduce do |result, number|
    p result
    p number
    number % 10 < result % 10 && result = number
    result
  end

ハガユウキ

整数の一の位はその数を 10 で割った余りと等しいです。
たとえば 17 の一の位は 7 ですが、これは 17 を 10 で割った余りと一致します。

なんとなくイメージはできる

ハガユウキ

n要素で考えた時でも成功するようなコードを書かないとなあ
その場しのぎ的なコードを書かない。n要素の方がどんな仕様変更が来ても、対応しやすい。

ハガユウキ

「A が B の倍数である」ことは、「A が B で割りきれる」ことと等しいです。

ハガユウキ

rubyで0かどうかを判定したいなら、Numeric#zero?を使う。

ハガユウキ

rubyで平均値的なメソッドはないのか。

ハガユウキ

解答結果
平均値を求めるメソッドは、モジュールとして切っても良いかもな。

begin
  numbers = gets.chomp.split.map(&:to_i)
  average_number = numbers.sum / numbers.length
  puts average_number
rescue StandardError => e
  p "raise: error", e
end

ハガユウキ

複数行を標準入力として受け取りたいなら、readlinesを使う。
ctrl + dを押すことで、readlinesの実行を終了できる。

ハガユウキ

Array#sumで文字列の結合はできるけど、Array#joinを使った方が高速

begin
  words = readlines.map(&:chomp).reverse
  puts words.join
rescue StandardError => e
  p "raise: error", e
end

ハガユウキ

多重代入してます。

begin
  words = readlines.map(&:chomp)
  word = words[0]
  indexes = words[1].split.map(&:to_i)
  word[indexes[0]], word[indexes[1]] = word[indexes[1]], word[indexes[0]]
  puts word
rescue StandardError => e
  p "raise: error", e
end

ハガユウキ

配列の要素同士の掛け算に関しての便利メソッドはなさそう。ループさせるしかないか

ハガユウキ

一の位はone_placeと呼ぶ

ハガユウキ

rubyのfilterはjsのfilterとやっていること一緒やな。

ハガユウキ

変数に * をつけると、残り全部を配列として受け取れる

ハガユウキ

多重代入でインデックス1以降の要素を配列として受け取りたい時

begin
  lines = readlines.map(&:chomp)
  # インデックス1以降の要素をまとめて配列として取得する
  _, *words = lines
  joined_word = words.join
  puts joined_word.length
rescue StandardError => e
  p "raise: error", e
end

実行結果

ruby src/become_familiar_with_programming/receive_input/many_stdin/practice_8.rb
3
hello
algo
method
15

ハガユウキ

S = readlines.map(&:chomp)

lft = S.count "left"
rgt = S.count "right"

puts lft > rgt ? "left" : lft == rgt ? "same" : "right"

上のコードでもできなくないけど、topやdown等の方向が増えたときに、集計ロジックを変えないといけない。

begin
  lines = readlines.map(&:chomp)
  # インデックス1以降の要素をまとめて配列として取得する
  _, *directions = lines
  direction_counter = Hash.new(0)
  directions.each { |direction| direction_counter[direction] += 1 }
  if direction_counter["left"] > direction_counter["right"]
    puts "left"
  elsif direction_counter["left"] < direction_counter["right"]
    puts "right"
  elsif direction_counter["left"] == direction_counter["right"]
    puts "same"
  end
rescue StandardError => e
  p "raise: error", e
end

こっちのコードだったら、集計ロジックを書き換える必要はない。
(どちらのコードでも、if文は書き換える必要は出てくるけど)

ハガユウキ

「アルゴリズム入門: 全探索」やっていこう

ハガユウキ

rubyのmapでインデックスも取得したい場合、with_indexを使えば良いそう。

[:a, :b, :c].map.with_index do |data, index|
  # indexは 0, 1, 2というカウンタ
end

末尾から改行コードを取りたいなら、chompを使う

ハガユウキ

いらない括弧を使わない

Class: RuboCop::Cop::Lint::ShadowedArgumentって何やろう。いまだによくわからん

ハガユウキ

全探索とは

全探索は考えられる可能性を全て調べ上げる方法のことです。

線形探索法

このように、「一つ一つのデータを順に調べていく」方法のことを線形探索法と言います。この考え方は一見シンプルですが、探索アルゴリズムの原点となる大切なものです。

ハガユウキ

全探索の一つとして線形探索法があるって感じか

ハガユウキ

Array#include?で配列の中に特定の要素が入っているかをチェックできる

ハガユウキ

Array#countで、countに引数を渡すと、配列の要素 == 引数がtrueになるような要素の個数を数えてくれる。

ハガユウキ

ブロックを指定した場合は、ブロックを評価して真になった要素の個数をカウントして返します。
これで正の整数の個数も数えられる。

ハガユウキ

Numeric#positive?で正の整数かどうかを判定できる。
すげえ

ハガユウキ

最初に初期値 init と self の最初の要素を引数にブロックを実行します。 2 回目以降のループでは、前のブロックの実行結果と self の次の要素を引数に順次ブロックを実行します。そうして最後の要素まで繰り返し、最後のブロックの実行結果を返します。

reduceのresultにははじめのループでは第一要素、２回目以降のループはblockの実行結果が入るのか

ハガユウキ

<は英語でless than
最も右はfar right

ハガユウキ

reduceをindex付きでやりたいなら、each_with_indexを先に書く。with_indexじゃできないそう。

  numbers.each_with_index.reduce do |result, (element, index)|
    if result[0] < element
      maximum_number_index = index
      result = [element, index]
    end
    result
  end

ハガユウキ

ハッシュロケットを使えば、ハッシュのキーに文字列、シンボル以外に数値を指定できる

ハガユウキ

このコードのデメリットは、number_counterが増えると辛い

begin
  lines = readlines.map(&:chomp)
  numbers = lines[1].split.map(&:to_i)
  number_counter = {
    1 => 0,
    2 => 0,
    3 => 0,
    4 => 0,
    5 => 0,
    6 => 0,
    7 => 0,
    8 => 0,
    9 => 0
  }

  numbers.each { |number| number_counter[number] += 1 }

  number_counter.each do |_, value|
    puts value
  end
rescue StandardError => e
  p "raise: error", e
end

ただ、配列のインデックスもだいぶトラップな気がする。

ハガユウキ

Hash#valuesで、ハッシュの全valueを要素とする配列を取得できる。

ハッシュにもeachはある。Hash#each

Hash#keyで、valueに対応するキーを返す

begin
  lines = readlines.map(&:chomp)
  numbers = lines[1].split.map(&:to_i)
  number_counter = Hash.new(0)
  numbers.each { |number| number_counter[number] += 1 }
  maximum_count = number_counter.values.max
  most_appear_number = number_counter.key(maximum_count)
  puts most_appear_number
rescue StandardError => e
  p "raise: error", e
end

ハガユウキ

hashでもreduceは使える

ハガユウキ

数値の全探索

「配列の全探索」では、配列の要素を調べあげる練習をしました。
この章では、特定の範囲の数をすべて調べ上げる「数字の全探索」を取り扱います。

ハガユウキ

for文とグローバル変数countを使うことで、特定の範囲の数を全て調べられるのか。

ハガユウキ

N の約数とは「 N を割り切ることのできる 1 以上の整数」のことです。

ハガユウキ

そうか、約数の最大値ってその数自身か。

ハガユウキ

Range#each

Rangeにもeachあったのか。

(10..15).each {|n| print n, ' ' }
# prints: 10 11 12 13 14 15

(2.5..5).each {|n| print n, ' ' }
# raises: TypeError: can't iterate from Float

ハガユウキ

次の条件を満たすとき「 N は素数である」と言います。
N は 2 以上の整数である
N を割り切ることのできる 1 より大きい整数は N のみである

ハガユウキ

与えられた数が素数かどうかを判定する

素数判定のアルゴリズム
もっちょい綺麗に描きたい

def prime_number?(target_number)
  return false if target_number < 2
  return true if target_number == 2

  (2..target_number - 1).each do |number|
    return false if (target_number % number).zero?
  end

  true
end

begin
  target_number = gets.chomp.to_i
  if prime_number?(target_number)
    puts "Yes"
  else
    puts "No"
  end
rescue StandardError => e
  p "raise: error", e
end

ハガユウキ

最大公約する

ただし次の条件を満たすとき「 X は A と B の最大公約数である」と言います。
条件：X は A も B も割り切る 1 以上の整数の中で最大のものである

ハガユウキ

あまりが0になった時に割った数が最大公約数

ハガユウキ

こんな感じ

begin
  a, b = gets.chomp.split.map(&:to_i)

  loop do
    remainder_number = b % a
    break if remainder_number.zero?

    b = a
    a = remainder_number
  end

  puts a
rescue StandardError => e
  p "raise: error", e
end

rubyで配列の要素を別の2つの変数に入れるとかできたんやね。すごい

# aに1, bに2が代入される
a, b = [1, 2]

ハガユウキ

Numeric#negative?は、selfが0未満の場合にtrueを返す
Numeric#positive?は、selfが0より大きい場合に、trueを返す。つまり、0.1とかはtrueになる。

ハガユウキ

Rubyの流儀
「!」がついているメソッドは大元のオブジェクトを書き換えるメソッド
「?」がつくメソッドは真偽値を返すメソッド

ハガユウキ

前の数と後の数を比較する際に、Array#reduceは使えるな。

ハガユウキ

String#splitはデフォルトで空白文字をセパレータとして、区切っていく。

ハガユウキ

String#include?で文字列中に部分文字列が含まれてたらtrueを返す

ハガユウキ

1文字はletterか
複数文字ならlettersにすれば良いか。

https://eow.alc.co.jp/search?q=letter

ハガユウキ

どんな数だろうと、最初の約数は「1」となります。素数の定義とややこしいな。

ハガユウキ

rangeにもreduceあった

ハガユウキ

ある要素以降の配列が欲しいなら、a[n..]を指定すれば良い

  words_count, words = lines[0].to_i, lines[1..]

ハガユウキ

ループさせる配列が 3 つになってくると、流石にこのロジック計算量大丈夫かってなるな。

begin
  lines = readlines.map(&:chomp)
  x, y, z = lines[0].split.map(&:to_i)
  numbers = lines[1].split.map(&:to_i)
  other_numbers = lines[2].split.map(&:to_i)
  another_numbers = lines[3].split.map(&:to_i)
  equal_count = 0

  (0..x - 1).each do |i|
    (0..y - 1).each do |j|
      (0..z - 1).each do |k|
        numbers[i] + other_numbers[j] == another_numbers[k] && equal_count += 1
      end
    end
  end

  puts equal_count
rescue StandardError => e
  p "raise: error", e
end

ハガユウキ

≧: "greater than or equal to"
≦: "less than or equal to
＞: "greater than"
＜: "less than"

ハガユウキ

ペアの全探索

この章では、1 つの配列に対して過不足なく (同じ添字を 2 回調べることなく) ループを回す方法を学び練習します。

組みを取り出す場合、順列とは異なるから、

i は 0 から N−1 までの範囲を動く。
j は i+1 から N−1 までの範囲を動く。

と考えた方が、(i, j)の組みが重複することはない

ハガユウキ

図をイメージする。

ハガユウキ

2重ループの場合、内側のループではiは固定される。そのiより大きい ~ 最大の範囲でjが動けば、iとjは絶対被らない。iが固定されていてjがiより大きい範囲とiの最大値の間で動いている図をイメージする。

ハガユウキ

選び方って言われたら、順列とは違う。位置まで関心がない。組み合わせにしか関心がない

ハガユウキ

maxの書き方思いつかなかった。確かに、ループが増えると条件文がめっちゃ長くなるから、maxのが良いか

before

begin
  lines = readlines.map(&:chomp)
  numbers_count = lines[0].to_i
  numbers = lines[1].split.map(&:to_i)
  middle_maximum_number_count = 0

  (0..numbers_count - 1).each do |i|
    (i + 1..numbers_count - 1).each do |j|
      (j + 1..numbers_count - 1).each do |k|
        numbers[j] >= numbers[i] && numbers[j] >= numbers[k] && middle_maximum_number_count += 1
      end
    end
  end

  puts middle_maximum_number_count
rescue StandardError => e
  p "raise: error", e
end

after

begin
  lines = readlines.map(&:chomp)
  numbers_count = lines[0].to_i
  numbers = lines[1].split.map(&:to_i)
  middle_maximum_number_count = 0

  (0..numbers_count - 1).each do |i|
    (i + 1..numbers_count - 1).each do |j|
      (j + 1..numbers_count - 1).each do |k|
        numbers[j] == [numbers[i], numbers[j], numbers[k]].max && middle_maximum_number_count += 1
      end
    end
  end

  puts middle_maximum_number_count
rescue StandardError => e
  p "raise: error", e
end

ハガユウキ

1の位を求めたいなら、10で割ったあまりを求めればよい

irb
irb(main):001:0> 123 % 10
=> 3
irb(main):002:0> 123 % 100
=> 23
irb(main):003:0>

z = ab + cの形を想像すれば簡単か。