今日解いた問題

Ruby アルゴリズム

分割数はいまいちわかっていない

最長増加部分列問題

自分(i)より小さい部分問題を解いていけばできる

N = 5
A = [4, 2, 3, 1, 5].freeze

$dp = Array.new(N, 1)

def solve
  N.times do |i|
    i.times do |j|
      $dp[i] = [$dp[j] + 1, $dp[i]].max if A[i] > A[j]
    end
  end

  $dp.max
end

p solve # => 3

分割数

NをM個以下に分割する総数

N=4,M=3の場合 dp(3,4)=dp(3,1)+dp(2,4)になる．
dp(2,4)は総数なので2個以下で分割するときの総数($dp[i-1][j])
dp(3,1)は3分割したもののそれぞれから1引いてそれを分割する総数($dp[i][j-1] この場合 j < iなので0)
3分割したものから1引くとは4=1+1+2となるのでそれぞれから１引いて0+0+1=1

N = 4
M = 3

$dp = Array.new(M + 1).map { Array.new(N + 1, 0) }

def solve
  $dp[0][0] = 1

  (1..M).each do |i|
    (0..N).each do |j|
      a = j - i >= 0 ? $dp[i][j-i] : 0
      $dp[i][j] =  $dp[i-1][j] + a
    end
  end

  $dp[M][N]
end

p solve # => 4

ナップザック問題

Ruby アルゴリズム

久しぶりにナップザック問題書いてみたら思いの外時間がかかって辛かった

N = 4
W = 5
ITEMS = [[2, 3], [1, 2], [3, 4], [2, 2]].freeze # [重さ, 価値]
INF = 10000000

# 全探索
def dfs(i, w)
  return 0 if i == N
  b = dfs(i + 1, w)
  a = w - ITEMS[i][0] >= 0 ? dfs(i + 1, w - ITEMS[i][0]) + ITEMS[i][1] : 0
  [a, b].max
end
p dfs(0, W) # => 7 


# memo化
$memo = Array.new(N).map { Array.new(N, INF) }
def dfs_memo(i, w)
  return 0 if i == N

  b = dfs_memo(i + 1, w)
  a = w - ITEMS[i][0] >= 0 ? dfs_memo(i + 1, w - ITEMS[i][0]) + ITEMS[i][1] : 0
  $memo[i][w] = [a, b].max
end
p dfs_memo(0, W) # => 7 



# dp
$dp = Array.new(N + 1).map { Array.new(W + 1, 0) }
def solver
  (1..N).each do |i|
    (1..W).each do |j|
      a = $dp[i-1][j]
      b = j >= ITEMS[i-1][0] ? $dp[i-1][j-ITEMS[i-1][0]] + ITEMS[i - 1][1] : 0
      $dp[i][j] = [a, b].max
    end
  end
end

solver
p $dp[N][W] # => 7

rspec3で標準入力と標準出力のテスト

Ruby RSpec

rspecで標準入力からユーザの入力を受け取って標準出力に出力する方法の覚書 rspec2とrspec3がまざっててややこしかった

プロダクションコード

solver.rb

getでユーザの入力を受け取ってprintで標準出力に答え(文字列)を出力するのクラス

class Solver
  attr_reader :n

  def get
    @n = gets
  end

  def print
    puts 'answer is foo'
  end
end

テストコード

solver_spec.rb

標準入力ではallow(ARGF).to receive(:gets) { 1000 }とするといいらしい． 1000の部分を入力したい値に変更すればいい．

標準出力はoutput("answer is foo\n").to_stdoutとするといいらしい． "answer is foo\n"の部分を出力したい値に変更すればいい．

require 'solver'

describe Solver do
  let(:solver) { described_class.new }

  describe 'solver#getは標準入力を受け取って@nにセットする' do
    before do
      allow(ARGF).to receive(:gets) { 1000 }
      solver.get
    end

    it { expect(solver.n).to eq 1000 }
  end

  describe 'solver#printは標準出力に答えを出力する' do
    it { expect { solver.print }.to output("answer is foo\n").to_stdout }
  end
end

参考

rubyで簡単なテストを書く

Ruby

スクリプト程度のちょっとしたテスト書きたい時に便利でした

以下を書いてあとはassertとかでテスト

require 'minitest/unit'
extend MiniTest::Assertions

例

require 'minitest/unit'
extend MiniTest::Assertions

a = [1, 2, 3]
b = a.dup

assert_equal a.object_id, b.object_id, "Yo"

実行結果

$ ruby assert.rb
/Users/ganma/.rbenv/versions/2.1.1/lib/ruby/2.1.0/minitest/unit.rb:202:in `assert': Yo. (MiniTest::Assertion)
Expected: 70124833148220
  Actual: 70124833148200
  from /Users/ganma/.rbenv/versions/2.1.1/lib/ruby/2.1.0/minitest/unit.rb:230:in `assert_equal'
   from 0724-230559.rb:41:in `<main>'

参考

module MiniTest::Assertions

masterブランチにpushさせないようにするフック

git

git push -f origin masterをして「masterブランチがあああああ、あっあっあっ」とならないために(今日なった)

$HOME/.git_template/hooksというディレクトリをつくる

$ mkdir -p ~/.git_template/hooks

作成したディレクトリにpre-pushというファイルを作る

$ emacs ~/.git_template/hooks/pre-push

pre-push

#!/bin/sh

# if the branch is master, then fail.

branch="$(git symbolic-ref HEAD 2>/dev/null)" || \
       "$(git describe --contains --all HEAD)"

if [ "${branch##refs/heads/}" = "master" ]; then
  echo "Do not push on the master branch!"
  exit 1
fi

作ったあとは実行権限を与えます

$ chmod +x ~/.git_template/hooks

.gitconfigに設定を追加する

$ git config --global init.templatedir ~/.git_template/

以上で次からクローンしてくるリポジトリにはgit push origin masterができなくなります

今既に存在しているリポジトリでもマスターへのプッシュを禁止したいときはレポジトリの.git/hooksディレクトリに追加するといいです

$ cd repo
$ cp ~/.git_template/hooks/pre-push ./git/hook/pre-push

参考に書いてあることをそのままコピーしただけなので参考を見てください

参考

masterのpushを常に禁止する

railsを使わないrspecの使い方

Ruby RSpec

パス

  • ./lib/以下にプロダクションコードをおく
  • ./spec/以下にテストコードを置く

名前

例えば./lib/test.rbを作ったとする。このときのspecの名前はspec/test_spec.rbとする

コードのひな形

プロダクションコード(./lib/test.rb)

class Hoge
  def hello
    'hello world'
  end
end

テストコード(./spec/test_spec.rb)

require 'hoge'

describe Hoge do

  let(:hoge) { Hoge.new }

  it 'hogeはhello worldと出力' do
    expect(hoge.hello).to eq 'hello world'
  end
end

実行方法

./にいる状態で$ rspecとするだけでよい