yucatio@システムエンジニア

趣味で作ったものいろいろ

「5と8を使った和で表すことができない最大の整数を求めよ」を解いてみる

算数

小2が「5と8を使った和で表すことができない最大の整数を求めよ」という大学入試レベルの算数を教えてと聞いてきた

togetter.com

この問題が面白いなと思って自分なりに解いて見たので書いてみます。数学は専門ではないので厳密さに欠けることは先に記しておきます。

問題を書き直すと、

8x + 5y (xとyは0以上の整数) で表される数で、表現できない最大の数はいくつか

になります。

問題文から、ある程度大きい数字であれば5と8の和で表すことができるので、適当な数で確かめます。 49にでもしましょうか。

49から8を順に引いていきます。

f:id:yucatio:20190209142054p:plain
49から8を引いていく

さらに5で割った余りを下に書いていきます。

f:id:yucatio:20190209142142p:plain
5で割った余りを書く

25が5で割り切れますね。25までは49から3回8を引いていますので、

49 = 8 × 3 + 5 × 5

で表すことができます。別の数でもやってみましょう。8を引いていった数字と、それぞれ5で割った数字を書きます。

f:id:yucatio:20190209142813p:plain
48から8を引いていく

40が5で割り切れます。40まで1回8を引いているので、

48 = 8 × 1 + 5 × 8
(もちろん、48 = 8 × 6 でもよいです)

f:id:yucatio:20190209143221p:plain
47から8を引いていく

15が5で割り切れます。15まで4回8を引いているので、

47 = 8 × 4 + 5 × 3

長くなるので、たくさんのパターンは書けませんが、ある数から8を引いて、それを5で割った余りは、

f:id:yucatio:20190209151022p:plain
0 -> 2 -> 4 -> 1 -> 3 の繰り返し

この順番で現れることがわかります。もう少し大きい数でも確かめてみましょう。97でやってみます。

f:id:yucatio:20190209152509p:plain

なりますね。実際に定理になってると思うのですが、何の定理か忘れました。

ある数から8ずつ引いていくと、5回に1回は、5で割った余りが0になる(=5で割り切れる=5の倍数である)ということがわかりました。

ということは、ある数から4回以上8が引ければ、元の数と合わせて5個の数字が並び、その中の1つは5で割り切れます。4回以上8が引ける数の最小は33 (= 8 * 4 + 1 ) です。確かめてみると、

f:id:yucatio:20190209152956p:plain
33から8を引いていく

33 = 8 × 1 + 5 × 5

で表すことができます。

32のときは

f:id:yucatio:20190209154140p:plain
32から8を引いていく

5で割り切れる数は出てきませんが、8で割り切れるので、

32 = 8 × 4

です。1つずつみていきましょう。

31のときは、

f:id:yucatio:20190209154204p:plain
31から8を引いていく

31 = 8 × 2 + 5 × 3

30のときは、

f:id:yucatio:20190209154224p:plain
30から8を引いていく

30 = 5 × 6

29のときは、

f:id:yucatio:20190209154252p:plain
29から8を引いていく

29 = 8 × 3 + 5 × 1

28のときは、

f:id:yucatio:20190209154400p:plain
28から8を引いていく

28 = 8 × 1 + 5 × 4

27のときは、

f:id:yucatio:20190209154420p:plain
27から8を引いていく

27から8を引いていっても5の倍数にならないので、27が 8x + 5y で表すことのできない最大の数ということがわかります。

実は、32から1つずつみていかなくても、規則性を見ていけば計算で答えを求められます。

f:id:yucatio:20190209151022p:plain

32から25までは8が3回引けるので、元の数と合わせて4つの数が並びます。4つの場合、上の図で、2から始まると 2 → 4 → 1 → 3になり、0が出てこない(=5で割り切れない)ことが分かります。

5で割った余りが2になる33より小さい数は、32ですが、これは8の倍数(32 = 8*4)なので、次に大きい27(=32-5)が答えになります。

あとがき

小学校2年生まで習う知識ではとても解けなさそうでした。

ネット上に同じ解法が載っているかもしれませんが、見つけられませんでした。

この問題自体はフロベニウスの硬貨交換問題として知られているそうです。

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

面白くて眠れなくなる数学 （PHP文庫） [ 桜井進 ]
価格：691円（税込、送料無料) (2019/2/8時点)


RSpecでsubjectを使用して配列を検査時、配列の長さを取得する

RSpec

RSpecでsubjectを使用して、配列を

subject { user.errors[:name] }  # user.errors[:name] は配列

このように検査時、配列の長さを取得する方法が分からなかったので調べました。

結論

rspec-itsのitsを使用する。

its(:size) { is_expected.to eq 3 }

のように書くとsubjectの検査対象の配列の長さを取得できます。

経緯

モデルのテストを書きました。

modelのコード↓

class User < ApplicationRecord
  validates :nickname, presence: true, length: { maximum: 32 },
                       format: { with: /\A[-0-9a-zA-Z#$%&()._]*\z/,
                                 message: 'には半角英数字と#$%&()-._のみ使用できます。' }
end

テストは以下のようになります。(全て書くと長いので一部のみ抜粋)

require 'rails_helper'

RSpec.describe User, type: :model do
  describe '#nickname' do
    context '空白のとき'do
      it 'エラーが出ること' do
        user = User.new(nickname: '')
        user.valid?
        expect(user.errors[:nickname]).to include("can't be blank")
      end
    end

    context '許可される文字の場合' do
      context '英大文字小文字数字#$%&()-._' do
        it 'エラーが出ないこと' do
          user = User.new(nickname: 'ARZatz809(_#-$%.&)')
          user.valid?
          expect(user.errors[:nickname]).to be_blank
        end
      end
    end

    context '許可されない文字の場合' do
      context '許可されていない文字"?"が含まれている場合' do
        it 'エラーが出ること' do
          user = User.new(nickname: 'correct?')
          user.valid?
          expect(user.errors[:nickname]).to include('には半角英数字と#$%&()-._のみ使用できます。')
        end
      end
    end
  end
end

これを綺麗にすると以下のようになります。(参考: 使えるRSpec入門・その1「RSpecの基本的な構文や便利な機能を理解する」 - Qiita )

require 'rails_helper'

RSpec.describe User, type: :model do
  describe '#nickname' do
    subject { user.errors[:nickname] }

    let(:user) { User.new(params) }
    let(:params) { {nickname: nickname} }

    before do
      user.valid?
    end

    context '空白のとき'do
      let(:nickname) { '' }
      it { is_expected.to include("can't be blank") }
    end

    context '許可される文字の場合' do
      context '英大文字小文字数字#$%&()-._' do
        let(:nickname) { 'ARZatz809(_#-$%.&)' }
        it { is_expected.to be_blank }
      end
    end

    context '許可されない文字の場合' do
      context '許可されていない文字"?"が含まれている場合' do
        let(:nickname) { 'correct?' }
        it { is_expected.to include('には半角英数字と#$%&()-._のみ使用できます。') }
      end
    end
  end
end

繰り返しがなくなってすっきりしました。

ここでふと思いました。 このテストコード、対象のエラーが含まれることはチェックできるけど、想定外のエラーが(間違って)含まれることはテストできていないじゃん、と。

ここでの方針としては、

  • includeでなく配列同士の比較を行う
  • エラーの数をチェックする

などが思いつきます。今回は

  • エラーの数をチェックする

方法にします。この方法をとることで、

  • エラーの順番は問わず
  • 想定外のエラーが間違って入っていることを防ぐ

ことができます。

さて、テストの対象はsubjectに書かれています。これのサイズを取得したい。 これにはitsを使用します。

RSpec3からitsはgemに分離されているのでインストールします。

Gemfile

group :development, :test do
  # Call 'byebug' anywhere in the code to stop execution and get a debugger console
  gem 'byebug', platforms: [:mri, :mingw, :x64_mingw]
  gem 'rspec-rails'
  gem 'rspec-its'  # この行を追加
end

bundle installします。

テストを追加します。

its(:size) { is_expected.to eq 1 }のように書くとuser.errors[:nickname].sizeが1かどうかをテストすることができます。

RSpec.describe User, type: :model do
  describe '#nickname' do
    subject {user.errors[:nickname]}

    # 略

    context '空白のとき'do
      let(:nickname) { '' }
      it { is_expected.to include("can't be blank") }
      its(:size) { is_expected.to eq 1 }  # 追加
    end

    context '許可される文字の場合' do
      context '英大文字小文字数字#$%&()-._' do
        let(:nickname) {'ARZatz809(_#-$%.&)'}
        it { is_expected.to be_blank}
      end
    end

    context '許可されない文字の場合' do
      context '許可されていない文字"?"が含まれている場合' do
        let(:nickname) {'correct?'}
        it { is_expected.to include('には半角英数字と#$%&()-._のみ使用できます。')}
        its(:size) { is_expected.to eq 1 }  # 追加
      end
    end
  end
end

以上でsubjectに指定した配列のサイズ(長さ)をテストすることができました。

環境

参考


正規表現間違い探しクイズ　その3

正規表現 プログラミングクイズ

正規表現間違い探しクイズシリーズです。

正規表現は単体テストを書いている場合でもバグを発見しづらいものです。そのため、自身での検証が欠かせません。 今回は仕事中に見つけたものでなく、個人開発中にネットで見つけた間違いのうち印象的だったものを少し変えて紹介します。

問題編

仕様

  • 行頭及び行末の#記号を取り除くString#strip_hashを定義する
  • #記号は連続している可能性がある
  • #記号がない場合もある

動作イメージ

  • ###本文 → 本文
  • #大切# → 大切
  • 普通 → 普通

ソースコード

ソースコードです。 今回はRubyで実装します。

class String
  def strip_hash
    sub(/^#*([^#]+)#*$/, '\1')
  end
end

正規表現^#*([^#]+)#*$は、行頭に続き#の0回以上の繰り返し、続いて#以外の文字の繰り返し、#の0回以上の繰り返し、行末、を意味します。subメソッドを使用して、1つ目のグループ([^#]+)を抜き出しています。

f:id:yucatio:20190107194148p:plain

さて、この正規表現には明らかな間違いがあります。どのような間違いでしょうか。また、どのように修正するべきでしょうか。

テスト

以下のテストはパスしています。RSpecで書いています。

describe '#strip_hash' do
  subject { str.strip_hash }

  context '#が含まれているとき' do
    context '行頭に#がある場合' do
      let(:str) { '###文字列' }
      it { is_expected.to eq '文字列' }
    end

    context '行末に#がある場合' do
      let(:str) { '文字列###' }
      it { is_expected.to eq '文字列' }
    end

    context '行頭と行末に#がある場合' do
      let(:str) { '###文字列###' }
      it { is_expected.to eq '文字列' }
    end
  end

  context '#が含まれていないとき' do
    let(:str) { '文字列' }
    it { is_expected.to eq '文字列' }
  end
end

解答編

・

・

・

少し考えてから解答編を見てください

・

・

・

続きを読む

正規表現間違い探しクイズ　その2

正規表現 プログラミングクイズ

正規表現間違い探しクイズシリーズです。

正規表現は単体テストを書いている場合でもバグを発見しづらいものです。 そのためレビューの時には注意深く見るようにしています。そんな中見つけた間違いのうち印象的だったものを紹介します。

問題編

仕様

Linkモデルにはurlを持ちます。urlは以下の条件を満たします。

  • 入力必須
  • 長さは256文字以下
  • URLの形式を満たす必要がある
  • プロトコルはhttpまたはhttpsのみ許可される
  • ドメインはwww.example.comまたはblog.example.comのみ許可される

ソースコード

ソースコードです。 今回はRuby on Railsで実装します。

class Link < ApplicationRecord
  validates :url, presence: true, length: {maximum: 256}
  validate :valid_url

  private

  def valid_url
    return unless url

    if ! url?(url) then
      # URLの形式を満たしていない
      errors.add(:url, 'は有効なURLではありません。')
      return
    end

    if ! %r{\Ahttp(s)?://}.match?(url) then
      # httpまたはhttpsで始まっていない
      errors.add(:url, 'のプロトコルはhttpまたはhttpsのみ指定できます。')
    end

    if ! /((www)|(blog))\.example\.com/.match?(url) then
      # ドメインがwww.example.comまたはblog.example.comでない
      errors.add(:url, 'のドメインはwww.example.comまたはblog.example.comである必要があります。')
    end
  end

  def url?(url)
    # 今回の本題ではないので省略
  end
end

さて、上記ソースコードには明らかな間違いがあります。どのような間違いでしょうか。また、どのように修正するべきでしょうか。(ちなみに正規表現のはじめの\Aは文字列の先頭を指します。^と似ていますが、違いは参考のリンクを参照してください)

テスト

以下のテストはパスしています。

require 'rails_helper'

RSpec.describe Link, type: :model do
  describe '#url' do
    subject { link.errors[:url] }

    let(:link) { Link.new(params) }
    let(:params) { {url: url} }

    before do
      link.valid?
    end

    context '許可されるURLの場合' do
      context 'プロトコルがhttpの場合' do
        context 'ドメインがwww.example.comの場合' do
          let(:url) {'http://www.example.com/path/to/something'}
          it { is_expected.to be_blank}
        end
        context 'ドメインがblog.example.comの場合' do
          let(:url) {'http://blog.example.com/path/to/something'}
          it { is_expected.to be_blank}
        end
      end

      context 'プロトコルがhttpsの場合' do
        context 'ドメインがwww.example.comの場合' do
          let(:url) {'https://www.example.com/path/to/something'}
          it { is_expected.to be_blank}
        end
        context 'ドメインがblog.example.comの場合' do
          let(:url) {'https://blog.example.com/path/to/something'}
          it { is_expected.to be_blank}
        end
      end
    end

    context '許可されないURLの場合' do
      context '許可されないプロトコルの場合' do
        let(:url) {'ftp://www.example.com/path/to/something'}
        it { is_expected.to include('のプロトコルはhttpまたはhttpsのみ指定できます。')}
      end

      context '許可されないドメインの場合' do
        let(:url) {'http://www.hatenablog.com/path/to/something'}
        it { is_expected.to include('のドメインはwww.example.comまたはblog.example.comである必要があります。')}
      end
    end
  end
end

RSpec知らない人だと何書いてあるかわからないかと思いますが、重要な部分は、入力がhttp://www.example.com/path/to/somethingだとエラーが出なくて(be_blank)、入力がftp://www.example.com/path/to/somethingだとのプロトコルはhttpまたはhttpsのみ指定できます。というエラーが出るという部分です。

解答編

・

・

・

少し考えてから解答編を見てください

・

・

・

続きを読む

正規表現間違い探しクイズ　その1

正規表現 プログラミングクイズ

正規表現間違い探しクイズシリーズです。

正規表現のバグは単体テストを書いている場合でも発見しづらいものです。 そのためレビューの時には注意深く見るようにしています。そんな中見つけた間違いのうち印象的だったものを紹介します。

問題編

仕様

ユーザモデルはニックネームを持ちます。ニックネームは以下の条件を満たします。

  • 入力必須
  • 32文字以下
  • 使用できる文字列は半角英数字と#$%&()-._

ソースコード

ソースコードです。 今回はRuby on Railsで実装します。

class User < ApplicationRecord
  validates :nickname, presence: true, length: { maximum: 32 },
                       format: { with: /\A[0-9a-zA-Z#$%&()-._]*\z/,
                                 message: 'には半角英数字と#$%&()-._のみ使用できます。' }
end

さて、上記ソースコードの正規表現(\A[0-9a-zA-Z#$%&()-._]*\z)には明らかな間違いがあります。どのような間違いでしょうか。また、どのように修正するべきでしょうか。(ちなみに正規表現のはじめの\Aは文字列の先頭、\zは文字列の末尾を指します。それぞれ^と$と似ていますが、違いは参考のリンクを参照してください)

テスト

以下のテストはパスしています。

require 'rails_helper'

RSpec.describe User, type: :model do
  describe '#nickname' do
    subject { user.errors[:nickname] }

    let(:user) { User.new(params) }
    let(:params) { {nickname: nickname} }

    before do
      user.valid?
    end

    context '許可される文字の場合' do
      context '英大文字小文字数字#$%&()-._' do
        let(:nickname) { 'ARZatz809(_#-$%.&)' }
        it { is_expected.to be_blank }
      end
    end

    context '許可されない文字の場合' do
      context '許可されていない文字"?"と"""が含まれている場合' do
        let(:nickname) { '?baerg"' }
        it { is_expected.to include('には半角英数字と#$%&()-._のみ使用できます。') }
      end
    end
  end
end

RSpec知らない人だと何書いてあるかわからないかと思いますが、重要な部分は、入力がARZatz809(_#-$%.&)だとエラーが出なくて(be_blank)、入力が?baerg"だとには半角英数字と#$%&()-._のみ使用できます。というエラーが出るという部分です。

解答編

・

・

・

少し考えてから解答編を見てください

・

・

・

続きを読む

ソフトウェアのテストを書くのが嫌になる瞬間 第5位

ソフトウェアのテストを書くのが嫌になる瞬間

ソフトウェアのテストを書くのが嫌になる瞬間、今回は第5位です。

以下、単に”テスト”と書いた場合は、テストコードのことを指し、CIツールなどで自動実行されるものを指します。また、単に"コード"と書いた場合には、プロダクションコードを指します。 また、単体テストよりもエンドtoエンドのテストを厚く書く職場で働いています。

テストを書くのが嫌になる瞬間 第5位 : テストを書いたにも関わらずリリース後にバグが発見されたとき

辛い。

今回は漫画なしです。

テストを書くとバグが減ると思ってましたが、大して減りません。

バグが発生した原因としては、大きく分けると

  • 自動テストのケース漏れ
  • 手動でしか確認できない部分の漏れ(副作用系)

に分けられます。

リリース後に発見される(大抵はユーザ問い合わせで発覚する)バグで多いのは、"手動でしか確認できない部分の漏れ(副作用系)"です。このバグは自動テスト導入しても(当然ながら)一向に減ることはありません。

手動でしか確認できない部分の漏れ(副作用系)の具体的な内容としては、以下のようなものです。

  • ファイルの書き出しが正しくされていない
  • 他のAPIに通知されるはずが通知されていない
  • メールが送られるはずが送られていない
  • 親子関係のあるデータで、親を削除した時に子のデータも一緒に削除されるはずが、されていない

また、現在システムが複雑化していて、同じ機能を持ったアプリが複数ある状況で、片方で登録した内容がもう片方で正しく表示されない、などの問題もありました。

あとは、これはリリース前に気づいたことですが、運用ログが出力されていないということもありました。(参照する変数が間違っていて毎回ID:nullと出ていたり、文字列だけ組み立てて出力するコードを書き忘れていたり)。

個人的な感想ですが、自動テストを導入してそちらのテストに気を取られて手動でしか確認できないテストに手と気が回らなくなってる気がします。ツールの問題より人間の気力というのが難しいところです。

また、テストが通ること=バグがないこと、と思い、手動テストが必要だという意識がないメンバーもいて、頭を悩ませているところです。 テストを書くことによる恩恵も受けているので、テストを書かなくするという対応策も取れず。

第5位は以上です。その他のソフトウェアのテストを書くのが嫌になる瞬間は以下にまとめています。

yucatio.hatenablog.com

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

テスト駆動開発 [ Kent Beck ]
価格：3024円（税込、送料無料) (2018/12/31時点)


ソフトウェアのテストを書くのが嫌になる瞬間 第4位

ソフトウェアのテストを書くのが嫌になる瞬間

ソフトウェアのテストを書くのが嫌になる瞬間、今回は第4位です。

テストを書くのが嫌になる瞬間 第4位 : テストの文脈を見ないで落ちたテストのみ修正しているのをみたとき

今回は10コマ漫画でお送りします。

なお、以下単に”テスト”と書いた場合は、テストコードのことを指し、CIツールなどで自動実行されるものを指します。また、単に"コード"と書いた場合には、プロダクションコードを指します。 また、単体テストよりもエンドtoエンドのテストを厚く書く職場で働いています。

f:id:yucatio:20181230165209p:plain:w300

f:id:yucatio:20181230165731p:plain

f:id:yucatio:20181230164527p:plain:w300

大体こうなるよね。

とにかく落ちたテストしか見ないのです。落ちたテストが書いてあるファイルは見てほしいし、少なくとも前後のテストケースくらいは確認してもらいたいものですが、見ないのです。ちゃんと元のテストコードには

説明 値 期待値
最小値 - 1 2 エラーが出る
最小値 3 登録できる
最大値 10 登録できる
最大値 + 1 11 エラーが出る

のように説明も書いてあるんですよ(上記だと期待値が適当ですが実際はちゃんと書いてあります)。全然読まれてない。

念のため書いておくと、下記のように直すのが正しいです。

説明 値 期待値
最小値 - 1 2 エラーが出る
最小値 3 登録できる
最大値 20 登録できる
最大値 + 1 21 エラーが出る

上記漫画の重症例はソフトウェアのテストを書くのが嫌になる瞬間 第1位と同じメンタリティですね。とにかくテストが通ればよいという考えのようです。

誰ですかテストは仕様書だと言ったのは。修正漏れたままマージされてしまったら、

説明 値 期待値
最小値 - 1 2 エラーが出る
最小値 3 登録できる
最大値 10 登録できる
最大値 + 1 21 エラーが出る

もしくは

説明 値 期待値
最小値 - 1 2 エラーが出る
最小値 3 登録できる
最大値 10 登録できる
最大値 + 1 11 登録できる

になりますよ。これ、"仕様分からないからソース見なきゃわかんない"に陥るパターンではないですか。

仕様変更での修正漏れは、レビューでもうっかりすると見逃すパターンです。書き換えられた部分は差分に出てくるのですが、書き換え忘れた部分は差分として出てこないからです。

とにかく私の周りでこのパターン多すぎてレビュー来るたびにげんなりします。どうすればよいのですか。教えてえらいひと。

第4位は以上です。その他のソフトウェアのテストを書くのが嫌になる瞬間は以下にまとめています。

yucatio.hatenablog.com

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

テスト駆動開発 [ Kent Beck ]
価格：3024円（税込、送料無料) (2018/12/28時点)