「たけしのコマ大数学科」の問題を Ruby で解く

marginalia.hatenablog.comいまこちらの記事で挑戦中です。「たけしのコマ大数学科」については Wikipedia でどうぞ。


問題例です。

10人が円卓に座って1人ずつ握手をするとき、全員の手が交差しないように握手する仕方は全部で何通りあるか?

1~1000の数字が振られている1000個の電球がある。すべてOFFの状態から始めて、1回目の操作で1の倍数の電球のスイッチのON/OFFを切り替え、2回目の操作では2の倍数の電球のON/OFFを切り替える。
 このように、n回目の操作でnの倍数の電球のON/OFFを切り替える操作を、1000回目までおこなったとき、最後にONの状態の電球の数は何個か。

直径ABの円とAの地点に点Pがある。直径(線分)ABが円に沿って等速で一回転する間に点PもAからBへ等速で移動する。このときの点Pの軌跡を書きなさい。

連続数字をハイフンでつなぐ(Ruby)

既に更新はされていませんが、僕はブログ「hp12c」をよく読んでいます。Ruby 好きには楽しいですね。

そこで、「Rubyで連続数字をハイフンでつなぐよ」というエントリがありました。元ネタはここということです。やることは要するに、「スペース区切りの数字列を、数字が連続する場合にその箇所をハイフンにする」ということです。

"1 2 3" => "1-3."
"1 2 3 5 7 8" => "1-3, 5, 7-8."
"1 3 4 5 7" => "1, 3-5, 7."

こんな感じ。で、元ネタのも含めていろいろ Ruby の便利メソッドを使った華麗な回答がいくつもあるのですが、ふつうにというか、あんまり便利メソッドを使わない素直な回答を考えてみました。

こんな感じになりました。

def hyphenize(st)
  compress = ->(ar) {
    result = ar.first.to_s
    i = 0
    i += 1 while ar[i].succ == ar[i + 1]
    result += "-" + ar[i].to_s if i.nonzero?
    return result, ar.drop(i + 1)
  }
  ar = st.split.map(&:to_i)
  str = ""
  until ar.empty?
    s, ar = compress.(ar)
    str += s + ", "
  end
  str[0..-3] + "."
end

ちょっと長いし華麗でも何でもないですけれど、まあ素直だと思います。是非リンク先の凝った回答たちも見てみて下さい。


リンク先の回答例の中では、smileruby さんのこれが特に凝っていると思います。ただし、掲載されたコードは Ruby 2.5.1 では動かないので、多少変更しました。

def hyphenize(str)
  nums = str.scan(/\d+/).map(&:to_i).sort
  prev = nums.first
  nums.slice_before do |e|
    prev, prevprev = e, prev
    prevprev.succ != prev
  end.map {|e| e.minmax.uniq.join('-')}.join(', ') + '.'
end 

slice_before とか minmax.uniq.join('-') とか、凝っていますねえ。僕は思わずリファレンス・マニュアルを調べましたよ。
 

おまけ

上記事とは関係ないけれど、その smileruby さんのブログを読んでいたらすごい FizzBuzz を発見。これは今まで見た中の(Ruby での)最短じゃないか。

1.upto(100){|i|puts"#{[:Fizz][i%3]}#{[:Buzz][i%5]}"[/.+/]||i}

記事はこちら。わかるまでしばらく考えましたよ。

追記。さらに過去のブログ記事を読んでいたら、これよりも短いのも可能らしい(参照)。ひゃー、すごい世界だな。

Go言語でカレンダーを出力してみた

obelisk.hatenablog.comここの Ruby 版の移植です。

出力例。

$ go run calender.go
          2018/10
sun mon tue wed thu fri sat
     1   2   3   4   5   6  
 7   8   9  10  11  12  13  
14  15  16  17  18  19  20  
21  22  23  24  25  26  27  
28  29  30  31  

 
コード。
calender.go

package main
import "fmt"
import "strconv"
import "strings"

var month_table = [...]int{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}

//うるう年か?
func is_uruu(year int) bool {
    return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0
}

//西暦1年1月1日から何日目か(すべてグレゴリオ暦で計算)
func days(year, month, day int) int {
    uruu := func(y int) int {return y / 4 - y / 100 + y / 400}
    month_days := func() int {
        d := 0
        for i := 1; i < month; i++ { d += month_table[i] }
        if is_uruu(year) && month > 2 {d++}
        return d
    }
    y1 := year - 1
    return y1 * 365 + uruu(y1) + month_days() + day - 1
}

//曜日の計算(日曜日が0、月曜日が1, ...)
func week_number(year, month, day int) int {
    return (days(year, month, day) + 1) % 7
}

//カレンダーの出力
func calender(year, month int) {
    gen := func(from, to int) (st string) {
        for i := from; i <= to; i++ {st += fmt.Sprintf("%2d  ", i)}
        return
    }
    
    st := strconv.Itoa(year) + "/" + strconv.Itoa(month)
    fmt.Println(strings.Repeat(" ", (27 - len(st)) / 2) + st)
    fmt.Println("sun mon tue wed thu fri sat")
    
    w := week_number(year, month, 1)
    fmt.Println(strings.Repeat("    ", w) + gen(1, 7 - w))
    
    i := 8 - w
    last := month_table[month]
    if is_uruu(year) && month == 2 {last++}
    for i + 6 <= last {
        fmt.Println(gen(i, i + 6))
        i += 7
    }
    st = gen(i, last)
    if st != "" {fmt.Println(st)}
}

func main() {
    calender(2018, 10)
}

自然数を n 個に分割する & 重複組み合わせ(Ruby)

def divide(x, n)
  result = []
  return [] if n.zero?
  return [[0] * n] if x.zero?
  return [[x]] if n == 1
  0.upto(x) do |i|
    result += divide(x - i, n - 1).map {|a| [i] + a}
  end
  result
end

p divide(5, 3)

結果。5 を 3つに分割している。

[[0, 0, 5], [0, 1, 4], [0, 2, 3], [0, 3, 2], [0, 4, 1], [0, 5, 0], [1, 0, 4],
 [1, 1, 3], [1, 2, 2], [1, 3, 1], [1, 4, 0], [2, 0, 3], [2, 1, 2], [2, 2, 1],
 [2, 3, 0], [3, 0, 2], [3, 1, 1], [3, 2, 0], [4, 0, 1], [4, 1, 0], [5, 0, 0]]

これができれば重複組み合わせが簡単に実装できる。上の例だと、3つの中から重複を許して 5つ取る組み合わせを作ることができる。


実際に重複組み合わせを実装してみた。

def repeated_combination(ar, n)
  divide(n, ar.size).reverse.map do |a|
    result = []
    a.each_with_index {|n, i| n.times {result << ar[i]}}
    result
  end
end

p repeated_combination([:a, :b, :c], 3)

結果。

[[:a, :a, :a], [:a, :a, :b], [:a, :a, :c], [:a, :b, :b], [:a, :b, :c],
 [:a, :c, :c], [:b, :b, :b], [:b, :b, :c], [:b, :c, :c], [:c, :c, :c]]

なお、もちろん Ruby 本体に重複組み合わせを得るメソッドはあります。

Go言語でスライスの要素の順列、組み合わせを与える

これって組み込み関数がないのですかねえ...

順列。コード。
permutation.go

package main
import "fmt"

//スライスの 位置 i の要素を除いたスライスを返す(arを破壊しないようコピーしている)
func remove(ar []int, i int) []int {
    tmp := make([]int, len(ar))
    copy(tmp, ar)
    return append(tmp[0:i], tmp[i + 1:]...)
}

func permutation(ar []int) [][]int {
    var result [][]int
    if len(ar) == 1 {return append(result, ar)}
    for i, a := range ar {
        for _, b := range permutation(remove(ar, i)) {
            result = append(result, append([]int{a}, b...))
        }
    }
    return result
}

func main() {
    fmt.Println(permutation([]int{50, 2, 1, 9}))
}

結果。

[[50 2 1 9] [50 2 9 1] [50 1 2 9] [50 1 9 2] [50 9 2 1] [50 9 1 2] [2 50 1 9]
 [2 50 9 1] [2 1 50 9] [2 1 9 50] [2 9 50 1] [2 9 1 50] [1 50 2 9] [1 50 9 2]
 [1 2 50 9] [1 2 9 50] [1 9 50 2] [1 9 2 50] [9 50 2 1] [9 50 1 2] [9 2 50 1]
 [9 2 1 50] [9 1 50 2] [9 1 2 50]]

 

ちなみにこれは Ruby では

def permutation(ar)
  result = []
  return [ar] if ar.size == 1
  ar.each_with_index do |a, i|
    permutation(ar[0, i] + ar[i + 1..-1]).each do |b|
      result += [[a] + b]
    end
  end
  result
end

p permutation([50, 2, 1, 9])

で同等。あるいは組み込み関数を使って

p [50, 2, 1, 9].permutation.to_a

でおしまい。
 

素数を指定した順列、組み合わせ

package main
import "fmt"

func remove(ar []int, i int) []int {
    tmp := make([]int, len(ar))
    copy(tmp, ar)
    return append(tmp[0:i], tmp[i + 1:]...)
}

func permutation_full(ar []int) [][]int {
    var result [][]int
    if len(ar) == 1 {return append(result, ar)}
    for i, a := range ar {
        for _, b := range permutation_full(remove(ar, i)) {
            result = append(result, append([]int{a}, b...))
        }
    }
    return result
}

//順列
func permutation(ar []int, n int) (result [][]int) {
    for _, a := range combination(ar, n) {
        result = append(result, permutation_full(a)...)
    }
    return
}

//組み合わせ
func combination(ar []int, n int) (result [][]int) {
    if n <= 0 || len(ar) < n {return}
    if n == 1 {
        for _, a := range ar {
            result = append(result, []int{a})
        }
    } else if len(ar) == n {
        result = append(result, ar)
    } else {
        for _, a := range combination(ar[1:], n - 1) {
            result = append(result, append([]int{ar[0]}, a...))
        }
        result = append(result, combination(ar[1:], n)...)
    }
    return
}

func main() {
    fmt.Println(combination([]int{50, 2, 1, 9}, 3))
    fmt.Println(permutation([]int{50, 2, 1, 9}, 3))
}

組み合わせの場合が結構複雑になったのだけれど、もっといいやり方はないかな。
結果。

[[50 2 1] [50 2 9] [50 1 9] [2 1 9]]

[[50 2 1] [50 1 2] [2 50 1] [2 1 50] [1 50 2] [1 2 50] [50 2 9] [50 9 2]
 [2 50 9] [2 9 50] [9 50 2] [9 2 50] [50 1 9] [50 9 1] [1 50 9] [1 9 50]
 [9 50 1] [9 1 50] [2 1 9] [2 9 1] [1 2 9] [1 9 2] [9 2 1] [9 1 2]]

 
[]int はお好みの型でどうぞ。Go は [[]] という配列は作れないのだな。ああ、[]interface{}{[]int{}} とかはできるか。

しかしこれ、C でやったら大変そう。どうやってやるのだろう。

1時間以内に解けなければプログラマ失格?

blog.kazuhooku.comここで次のような問題を見つけました。

1,2,…,9の数をこの順序で、”+”、”-“、またはなにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる。

1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に | ソフトアンテナブログ

 
で、自力で解けばよいのですが、ついそこでの Cコードを読んでしまいました。これがとてもきれいなコードだったので、Ruby に移植してみました。自力ではたぶんこんなにうまく解けなかったと思います。まず結果から。

$ time ruby solve.rb
1+2+3-4+5+6+78+9 = 100
1+2+34-5+67-8+9 = 100
1+23-4+5+6+78-9 = 100
1+23-4+56+7+8+9 = 100
12+3+4+5-6-7+89 = 100
12+3-4+5+67+8+9 = 100
12-3-4+5-6+7+89 = 100
123+4-5+67-89 = 100
123+45-67+8-9 = 100
123-4-5-6-7+8-9 = 100
123-45-67+89 = 100

real	0m0.107s
user	0m0.064s
sys	0m0.008s

全部で 11とおりあるのですね。Ruby でも一瞬で解いています。

Ruby コード。でもあまり Ruby っぽくはないです。

MAX_POS = 9
EXPECTED = 100

def doit(pos, sum, st, sign)
  st += (sign == 1) ? "+" : "-"
  n = 0
  pos.upto(MAX_POS) do |i|
    st += i.to_s
    n += i
    s = sum + sign * n
    n *= 10
    if i == MAX_POS
      puts st[1..-1] + " = 100" if s == EXPECTED
    else
      doit(i + 1, s, st,  1)
      doit(i + 1, s, st, -1)
    end
  end
end

doit(1, 0, "", 1)

ほぼ Cコードと同じです。総当りなのだけれど、非常にきれいに再帰で書かれていますね。すばらしい。

なお、関数 doit() の呼び出しは 6561回で、なるほどこの程度なら一瞬の筈ですね。
 

問題4 もやってみた

大本の記事の問題4 もむずかしいというので、やってみました。

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。

1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に | ソフトアンテナブログ

 
これは以下でいいのかな。これだとRuby の恩恵で、全然むずかしくない。

def solve(given)
  max = 0
  given.permutation do |ar|
    n = ar.join.to_i
    max = n if n > max
  end
  max
end

p solve([50, 2, 1, 9])    #=>95012

ここで Go言語でもやってみました。
 

ついでに全部やってみた

問題1。

forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。

def sum1(given)
  result = 0
  for i in given
    result += i
  end
  result
end

def sum2(given)
  result = 0
  while (n = given.first)
    result += n
    given = given.drop(1)
  end
  result
end

def sum3(given, sum = 0)
  return sum if given.empty?
  sum3(given.drop(1), sum + given.first)
end

a = [4, 10, -9, 25, 1]
p sum1(a)
p sum2(a)
p sum3(a)

問題2。

交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。

def zip(a, b)
  a.zip(b).flatten
end

p zip([:a, :b, :c], [1, 2, 3])

#あるいは
def zip(a, b)
  result = []
  a.each_index do |i|
    result << a[i]
    result << b[i]
  end
  result
end

問題3。

最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。

def fib
  Enumerator.new do |y|
    a, b = 0, 1
    loop do
      y << a
      a, b = b, a + b
    end
  end
end

p fib.take(100)

GTK+ とソケットを使ってチャット通信(Ruby)

20180917214400
 
20180917214517

Ruby/GTK2 の使い方が少しづつわかってきたので、ソケットを使ってチャット通信ソフトを作ってみました。上の例では Linux Mint 18.3 と Ubuntu Budgie を使って実行しています。

まずはサーバ側を立ち上げます。これはふつうに

$ ruby oshaberi.rb

と実行するだけです。次にクライアント側では、localhost や サーバの IPアドレスを指定して

$ ruby oshaberi.rb 192.168.11.7

みたいな感じで立ち上げます。もちろんインターネットに出てはいけません。LAN 内で遊んで下さい。

次に名前を訊いてくるので入れて下さい。

あとは上のエントリーバーから文字を入力すると、自分と相手側のスクロール・ウィンドウに会話の文字が表示されます。というように、簡単でしょう?


コードです。
oshaberi.rb

require 'gtk2'
require 'socket'

module Oshaberi
  class MyWindow < Gtk::Window
    def initialize
      super("Oshaberi")
      set_resizable(true)
      set_size_request(500, 300)
      
      entry = Gtk::Entry.new
      entry.set_editable(true)
      entry.set_height_request(40)
      entry.modify_font(Pango::FontDescription.new("13"))
      
      tv = Gtk::TextView.new
      tv.modify_font(Pango::FontDescription.new("12"))
      tv.set_editable(false)
      tv.set_cursor_visible(false)
      buf = tv.buffer
      
      sock1, sock2 = ARGV[0] ? client(ARGV[0]) : server
      sock1.set_encoding('UTF-8')
      sock2.set_encoding('ASCII-8BIT')
      
      myname, hisname = get_names(sock1, sock2)
      
      entry.signal_connect('activate') do
        st = entry.text
        buf.insert_interactive(buf.end_iter, myname + ": " + st + "\n", true)
        tv.scroll_mark_onscreen(buf.create_mark(nil, buf.end_iter, true))
        entry.set_text("")
        sock2.puts st
      end
      
      sw = Gtk::ScrolledWindow.new
      sw.set_policy(Gtk::POLICY_AUTOMATIC, Gtk::POLICY_AUTOMATIC)
      sw.add(tv)
      
      box = Gtk::VBox.new
      add(box)
      box.pack_start(entry, false, true, 0)
      box.pack_start(sw   , true , true, 0)
      
      Thread.new(sock1, tv, buf, hisname) do |sock, tv, buf, name|
        ioc = GLib::IOChannel.new(sock)
        ioc.add_watch(GLib::IOChannel::IN) do |i|
          buf.insert_interactive(buf.end_iter, name + ": " + (i.gets || exit), true)
          tv.scroll_mark_onscreen(buf.create_mark(nil, buf.end_iter, true))
          true    #繰り返し
        end
      end
      
      signal_connect("destroy") {Gtk.main_quit}
      show_all
    end
    
    Port = 29753
    
    def server
      s = TCPServer.open(Port)
      
      puts "接続を待っています..."
      sock2 = s.accept
      sock1 = s.accept
      puts "接続しました"
      [sock1, sock2]
    end
    
    def client(host)
      [TCPSocket.open(host, Port), TCPSocket.open(host, Port)]
    end
    
    def get_names(sock1, sock2)
      print "名前を入力して下さい: "
      myname = STDIN.gets.chomp
      myname = "" if myname.empty?
      sock2.puts myname
      hisname = sock1.gets.chomp
      hisname = "相手" if hisname == ""
      puts "相手の名前は #{hisname} です。"
      [myname, hisname]
    end
  end
  
  def self.start
    MyWindow.new
    Gtk.main
  end
end

Oshaberi.start

 

Ruby/GTK2 については下も参考にしてみて下さい。
marginalia.hatenablog.com