パスカルの三角形（Haskell）

「パスカルの三角形」というのはこういうやつですね。

              1               
             1 1              
            1 2 1             
           1 3 3 1            
          1 4 6 4 1           
        1 5 10 10 5 1         
       1 6 15 20 15 6 1       
     1 7 21 35 35 21 7 1      

この出力を目標に、Haskell で書いてみます。

以前に Ruby で書いてみました。そのコードを再掲しましょう。

pascal = ->(n) {
  each_cons = ->(ar) {
    (ar.size < 2) ? [] : [ar[0] + ar[1]] + each_cons[ar.drop(1)]
  }
  n.zero? ? [1] : [1] + each_cons[pascal[n - 1]] + [1]
}

n = 8
n.times {|i| puts pascal[i].join(" ").center(30)}

簡潔ですね。これを手本にしてみます。

こんな感じでしょうか。

main :: IO ()
main = putStr $ unlines $ map (centering 30 . toString) (map pascal [0..7])

centering :: Int -> String -> String
centering n str = (replicate i ' ') ++ str ++ (replicate j ' ')
    where l = length str
          i = div (n - l) 2
          j = n - l - i

toString :: [Int] -> String
toString xs = tail $ concat $ map f xs
    where f x = ' ': show x

pascal :: Int -> [Int]
pascal 0 = [1]
pascal n = [1] ++ eachCons (pascal (n - 1)) ++ [1]
       
eachCons :: [Int] -> [Int]
eachCons xs = if length xs < 2
              then []
              else (head xs + (head . tail) xs): (eachCons . tail) xs

いやー、これだけでも悩みましたよ。
関数 pascal と eachCons は Ruby の動作とまったく同じです。あとは関数 toString と centering で結果を成形された文字列にしています。

ちなみに、

• unlines 関数：[String]を改行を入れて結合する。[String] -> String。
• concat 関数：リストの平坦化。
• div 関数：整数/整数をして整数で返す。

です。

初心者が気づいたこと。

• Haskell で繰り返しをするのはまず map を使うとラク　でなければ再帰
• show 関数を使えばとりあえず String になる
• Ruby でのメソッドチェーンみたいなことができる

すごいHaskellたのしく学ぼう!

和暦 (明治 大正 昭和 平成) と西暦の変換をおこなう（Ruby）

簡単な遊びのプログラムが作りたかったのでやってみました。Date クラスは使っていません。

こんな感じです。コマンドライン引数を指定します。

#西暦から和暦
$ ruby gengou.rb 2018
平成30年
$ ruby gengou.rb 1945
昭和20年
$ ruby gengou.rb 1912
明治45年
大正元年

#和暦から西暦
$ ruby gengou.rb m1
西暦1868年
$ ruby gengou.rb h30
西暦2018年

明治はm、大正はt、昭和はs、平成はh で指定します。

コード。
gengou.rb

years_table = [[1868, 1912], [1912, 1926], [1926, 1989], [1989, 2019]]
period_names = %W(明治 大正 昭和 平成)
period_initials = %W(m t s h)

#西暦から和暦へ
year_to_period = ->(year) {
  year1 = 0
  years_table.each_with_index do |y, i|
    if y[0] <= year and year <= y[1]
      year1 = year - y[0] + 1
      year1 = "元" if year1 == 1
      puts period_names[i] + "#{year1}年"
    end
  end
  puts "その西暦はサポートしていません" if year1 == 0
}

#和暦から西暦へ
period_to_year = ->(period, year) {
  period.downcase!
  period_initials.each_with_index do |p_ini, i|
    if period == p_ini
      year1 = years_table[i][0] + year - 1
      st = if year1 > years_table[i][1]
        "#{period_names[i]}に#{year}年はありません"
      else
        "西暦#{year1}年"
      end
      puts st
    end
  end
}

if (m = /^(\d+)$/.match(ARGV[0]))
  year_to_period.(m[1].to_i)
elsif (m = /^([a-zA-Z])(\d+)$/.match(ARGV[0]))
  period_to_year.(m[1], m[2].to_i)
else
  puts "許されない入力です"
end

データを増やせばすべての元号に対応させることも可能です。ただ、頭文字の重複があるでしょうから、漢字で指定するようにしないといけませんね。

遊びですけれど、こういうのを書くには Ruby 最強じゃないですか？　書いていてチョー気持ちいいです。
かんたんな遊びのプログラミングいいですね。もっと題材を探したいです。

こんなのもどうぞ。
obelisk.hatenablog.com

Ruby でイケてないコードを→「いいね」→「スゲーいいね」にリファクタリング？

qiita.com
自分が「Ruby + リファクタリング」でぐぐると上のサイトがいちばん最初にヒットする。内容は題名どおり。添削者はすごい上級者プログラマらしい。添削された人には気の毒なのだけれど、勝手に引用してみる。まず「イケてない」コード。（ごめんなさい）

class OrdersReport
  def initialize(orders, start_date, end_date)
    @orders = orders
    @start_date = start_date
    @end_date = end_date
  end

  def total_sales_within_date_range
    orders_within_range = []
    @orders.each do |order|
      if order.placed_at >= @start_date && order.placed_at <= @end_date
        orders_within_range << order
      end
    end

    sum = 0
    orders_within_range.each do |order|
      sum += order.amount
    end
    sum
  end
end

class Order < OpenStruct
end

うーん、確かに読みにくいかなあ。でもわかるけれど。
RSpec テストコード。

require 'spec_helper'

describe OrdersReport do
  describe '#total_sales_within_date_range' do
    it 'returns total sales in range' do
      order_within_range1 = Order.new(amount:  5, placed_at: Date.new(2016, 10, 10))
      order_within_range2 = Order.new(amount: 10, placed_at: Date.new(2016, 10, 15))
      order_out_of_range  = Order.new(amount:  6, placed_at: Date.new(2016,  1,  1))
      orders = [order_within_range1, order_within_range2, order_out_of_range]

      start_date = Date.new(2016, 10,  1)
      end_date   = Date.new(2016, 10, 31)

      expect(OrdersReport.new(orders, start_date, end_date)
         .total_sales_within_date_range).to eq(15)
    end
  end
end

　
リファクタリング後。「スゲーいいね」のコード。

class OrdersReport
  def initialize(orders, date_range)
    @orders = orders
    @date_range = date_range
  end

  def total_sales_within_date_range
    total_sales(orders_within_range)
  end

  private

  def total_sales(orders)
    orders.map(&:amount).inject(0, :+)
  end

  def orders_within_range
    @orders.select { |order| order.placed_between?(@date_range) }
  end
end

class DateRange < Struct.new(:start_date, :end_date)
  def include?(date)
    (start_date..end_date).cover? date
  end
end

class Order < OpenStruct
  def placed_between?(date_range)
    date_range.include?(placed_at)
  end
end

添削者の言葉。

もう最初のコードと比べると可読性、単一責任、再利用性、疎結合、と全ての要素が満たされて格段に良くなっているのが分かる。ほとんどのメソッド内の行数が１行。（２行なのはinitializeのみ）気持ちいいぐらいに読みやすい。

https://qiita.com/jabba/items/e169adb2f33532c119cf

　
へー、プロの上級者はこんな風にリファクタリングするのだな。でも、自分みたいな初心者素人には謎すぎる。凝りすぎてキモい感じ。「気持ちいいぐらいに読みやすい」ともあまり思えない。まったく自分はセンスがないのだな。「可読性、単一責任、再利用性、疎結合」。確かに、ですな。

初心者素人ならこんな風に書くかも。マネしないように。

class OrdersReport
  def initialize(orders, start_date, end_date)
    @orders = orders
    @start_date = start_date
    @end_date   = end_date
  end

  def total_sales_within_date_range
    @orders.select {|od| @start_date <= od.placed_at and od.placed_at <= @end_date}
       .map(&:amount).inject(:+)
  end
end

class Order < OpenStruct
end

実質一行。あと、レシーバーが @orders で中身がわかるのに、ブロック変数まで order にするのは長くて自分には見にくい感じ。od で充分に思える。あとは select したら足すだけじゃね？

もちろん DateRange クラスを作ってもいいのだけれど、それは DRY 的に必要になってからでいいと思う。元をシンプルにしておけば改変もラク（select を置き換えればよいのが明白）。「不必要に将来の拡張性を考えない。それが必要になることはたぶんない。」「コードが短くなったら great ! といおう。」

自分に「スゲーいいね」のコードが見にくく感じるのは、置き換えるべき select が一般的な Enumerable なので、（ここでモンキーパッチはダメなので）そのためにいろいろいじらなくてはならないからである。そのために新たにクラスをひとつ追加し、メソッドも大幅に増やしている。これほどのことをするくらいなら、select のままではいけないのだろうか？　プロってのはむずかしいな。

プログラミングにおいてデータ構造は決定的なファクタのひとつだが、この「スゲーいいね」では DateRange クラスというデータ構造を思いついたためにこうなった。結局、この決定がよいかどうかということなのではないか。

※追記（4/2）

自分ならどうするかというとこういう感じかな。要するに条件に合う注文を足し算したいだけなので、条件に合う注文を足し算しようよ、という。https://t.co/HEhsO5q2nr

— Rui Ueyama (@rui314) 2016年7月17日

植山類さんのこれで充分（そしてそちらの方がたぶんずっと速い）。じつは本文記事は植山さんの「教え」（？）みたいなのが頭にあったのですが、既に本人がお書きになっていました(^^;　自分の場合は Ruby の便利メソッドを使ってメソッドチェーンにしただけで、考え方は植山さんのコードとまったく同じ。植山さんのなら Ruby 以外でもだいたい似たように書けると思う。あと、もしこれだけというのなら OrdersReport クラスがいらないというのもそのとおりですね。

Go言語と Ruby で 8 queens 問題

Go で「8 queens 問題」を解いてみました。実際は n queens が解けます。

すべての解を出力します。num = 8 の場合、解は 92通りあります。こんな感じ。

------------------
n = 1
@.......
....@...
.......@
.....@..
..@.....
......@.
.@......
...@....
------------------
n = 2
@.......
.....@..
.......@
..@.....
......@.
...@....
.@......
....@...
------------------
（以下略）

　
コードはこんな感じです。
eight_queen.go

package main
import "fmt"
import "strings"

const num = 8
var count = 0

//出力
func putout(field []int) {
    count++
    fmt.Println("------------------")
    fmt.Printf("n = %d\n", count)
    st := strings.Repeat(".", num - 1)
    for _, queen := range field {
        fmt.Println(st[0: queen] + "@" + st[0: num - queen - 1])
    }
}

//ここまでの field で女王の置けるマス（空白）を探す（1なら置けない）
func get_space(field []int) [num]int {
    result := [num]int{}
    l := len(field)
    for i, queen := range field {
        result[queen] = 1
        dst := l - i
        if a := queen - dst; a >= 0  {result[a] = 1}
        if a := queen + dst; a < num {result[a] = 1}
    }
    return result
}

//メインの深さ優先探索
func solve(field []int) {
    if len(field) == num {
        putout(field)
    } else {
        for i, space := range get_space(field) {
            if space == 0 { solve(append(field, i)) }
        }
    }
}

func main () {
    solve([]int{})
}

実質的に solve() と get_space() の 2つのメソッドだけでシンプルに書けました。putout() は出力用です。たぶん、これはたいていの言語にそのまま移植できると思います。
　
結構うまく書けたのではないでしょうか。再帰的に深さ優先探索で解いています。

実行時間は num = 8 の場合ほぼ一瞬（0.01秒くらい）です。num = 15 の場合、最終的な解の個数だけ出力するように改変して（コード）実行すると

$ time ./eight_queen
2279184

real	0m17.135s
user	0m17.332s
sys	0m0.040s

となります。num = 17 で

$ time ./eight_queen
95815104

real	13m38.920s
user	13m42.884s
sys	0m1.228s

くらいが限界でしょうか。

Go で書くのは好きですね。コードの見た目がいいです。

※参考
これまでの試み。今回は以前とはだいぶちがったロジックで求めています。
エイト・クイーン（8 queen）問題を Ruby で解いてみる - Camera Obscura
ふたたび Ruby で 8 queen（関数型プログラミングっぽく） - Camera Obscura
Swift で 8queen 問題を解く - Camera Obscura
　

ちなみに Ruby だとこんな風に移植できますか。
eight_queen_another.rb

#ここまでの field で女王の置けるマス（空白）を探す（falseなら置けない）
def get_space(field)
  result = Array.new(N, true)
  l = field.size
  field.each_with_index do |queen, i|
    result[queen] = false
    dst = l - i
    result[queen - dst] = false if queen - dst >= 0
    result[queen + dst] = false if queen + dst <  N
  end
  result
end

#メインの深さ優先探索および出力
def solve(field)
  if field.size == N
    @count += 1
    puts "------------------"
    puts "n = #{@count}"
    field.each {|queen| puts ("." * (N - 1)).insert(queen, "@")}
  else
    get_space(field).each_with_index {|space, i| solve(field + [i]) if space}
  end
end

N = 8
@count = 0
solve([])

「あなたのセッションは10秒以上続きませんでした」

Linux Mint 18.3 を起動しようとしたところ、以下のような表示が出て立ち上がらない。

あなたのセッションは10秒以上続きませんでした。もしあなた自身がログアウトしていない場合、インストールに問題があるか、ディスクの空き容量が足りないかもしれません。フェイルセーフなセッションからログインし、この問題を解決できるかどうか確認してください。

ちなみにこれはここからコピペしたものである。~/.xsession-errors ファイルの内容はリンク先とはちがい、fcitx 関係（追記：これはたぶんまちがい。正しくは initctl だったらしい）のものだった。原因がまったくわからなかったので、[Ctrl] + [Alt] + [F1] で tty に入り、timeshift を実行。

$ sudo timeshift --list
$ sudo timeshift --restore

画面の指示にしたがってリカバリーする。途中の GRUB2 の再インストールは実行するのが recommend だったのにしなかったので、たぶんそのせいで「reboot..」が出てもまったくリブートしない。これは失敗。リカバリーの途中では絶対に中断してはいけないが、どうも終了しているようだったので、いつもの [Alt] + [PrtSc] + [R], [S], [E], [I], [U], [B] で初期化したところ何とか再起動、うまく立ち上がった（ホッ）。

timeshift で救われたのは既に 2回目である。僕のメインマシンは Linux とあまり相性がよくないので、Mint 18.3 から導入された timeshift は簡単にリカバリーできて初心者にはすごく助かる。マシンとの相性がよくない方で、実力充分どんな不具合でも welcome とはいかない方は是非導入をお勧めする。Ubuntu 系統なら導入できる筈。

ちなみに原因はまったく不明。直前のセッションは端末から poweroff で終了したのだが、これはこれまで何度もやっていておかしいとはあまり思えない。あるとすれば直前のシステムのアップデートだが、それだったのか。とりあえずシステム更新は時間をおいてみることにする。

※追記
これを書いたところ検索で来られる方が少なくない。どうも自分の PC だけではないと思う。システムの更新後また不具合が再発したので、まず確実に apt で更新したパッケージがおかしい。はっきりとは言えないけれど、たぶん「tiff」があやしい（バージョンは 4.0.6.1ubuntu4）。まだ不具合が出ていない方は、apt でのアップデートは控えた方がよいかもしれない。具体的な解決策を提示できなくて、わざわざ来られた方には申し訳ないです。

追加。検索していておかしいパッケージがわかりました。virtualbox でバージョンは 5.1.34-dfsg-0ubuntu1.16.04.2 です。これをインストールするとおかしくなるようです。問題はここで議論されています。
https://forums.linuxmint.com/viewtopic.php?f=47&t=266431
とりあえず

$ sudo apt-get remove virtualbox*

あるいは

$ sudo apt-get remove virtualbox-guest*

で関連パッケージを削除するといいみたいな回答があがっていますが、未確認なので保証できません。実行は自己責任でお願いします。

不具合が出るのはいまのところ Linux Mint でしか確認していません。

追加。いちおう下が最新の解決策のようです（3/27 AM10:56）。自分では確認していないので実行は自己責任でお願いします。
https://forums.linuxmint.com/viewtopic.php?f=47&t=266431&start=40#p1449369
必要部分だけ抜き出しておきます。

• [Ctrl] + [Alt] + [F1] でコンソールに入る
• テキストモードでログインする
• 下のコマンドで virtualbox guest を取り除く

sudo apt-get purge virtualbox-guest-dkms virtualbox-guest-utils virtualbox-guest-x11

• PC を再起動する

https://forums.linuxmint.com/viewtopic.php?f=47&t=266431&start=40#p1449369

追記。問題が認識されたようで、いま virtualbox はアップデートマネージャのアップデートの対象から外れているようです。上の英語版 Linux Mint フォーラムではまだ議論が続いているようなので、参考にされる方はよくお確かめ下さい。（3/27 PM06:08）

追記。修正されたようです。自分の環境では新たなアップデートは問題ありませんでした。（3/28 PM00:12）

Ruby でカレンダーを出力してみた

特定の年と月を指定して、カレンダーを出力するプログラムを書いてみました。

標準添付ライブラリの Date クラスを使ってはつまらないので、自力で計算しました。
calender.rb

month_table = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

#うるう年か？
is_uruu = ->(year) {
  (year % 4 == 0 && year % 100 != 0) || year % 400 == 0
}

#西暦1年1月1日から何日目か（すべてグレゴリオ暦で計算）
days = ->(year, month, day) {
  uruu = ->(y) {
    y / 4 - y / 100 + y / 400
  }
  month_days = ->{
    month_table[0, month].inject(&:+) + (is_uruu.(year) && month > 2 ? 1 : 0)
  }
  y1 = year - 1
  y1 * 365 + uruu.(y1) + month_days.() + day - 1
}

#曜日の計算
week_number = ->(year, month, day) {
  (days.(year, month, day) + 1) % 7
}

#カレンダーの出力
Calender = ->(year, month) {
  gen = ->(from, to) {
    (from..to).map {|i| sprintf("%2d  ", i)}.join
  }
  putout = ->(i) {
    last = month_table[month]
    last += 1 if is_uruu.(year) && month == 2
    while i + 6 <= last
      puts gen.(i, i + 6)
      i += 7
    end
    st = gen.(i, last)
    puts st unless st.empty?
  }
  puts "#{year}/#{month}".center(27)
  puts "sun mon tue wed thu fri sat"
  w = week_number.(year, month, 1)
  puts "    " * w + gen.(1, 7 - w)
  putout.(8 - w)
}

実行例。

$ pry
[1] pry(main)> require "./calender"
=> true
[2] pry(main)> Calender[2018, 3]
          2018/3           
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  
=> nil
[3] pry(main)> Calender[1989, 1]
          1989/1           
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  
=> nil
[4] pry(main)> Calender[1968, 7]
          1968/7           
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  
=> nil
[5] pry(main)> Calender[2018, 2]
          2018/2           
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  
=> nil

　
なお、days.() 関数は西暦1年1月1日から何日目かを計算しますが、すべてグレゴリオ暦で計算しています。Ruby の Date クラスでは、それ以前のユリウス暦の期間を補正しているらしいので、こことはちがった値を出力します。なので厳密にいえば、このカレンダーはグレゴリオ暦に切り替わって以降の分しか正しい出力ではないことになります。なお、未来のカレンダーとしては正しいものを出力する筈です。

week_number.(year, month, day) はその日の曜日を出力します。日曜日は 0、月曜日は 1, ..土曜日は 6 という具合です。ソースの最後に

if __FILE__ == $0
  week_table = %W(日 月 火 水 木 金 土)
  puts week_table[week_number.(*ARGV.map(&:to_i))] + "曜日"
end

を加えると、

$ ruby calender.rb 2018 3 27
火曜日

という風にその日の曜日を出力することができます。

こんなのもどうぞ。
obelisk.hatenablog.com

素因数分解（Ruby）

素因数分解は結局素数で順に割っていくしかないのだけれど、素数をわざわざ求めてというのは却って大変ですね。

うまいやり方としては、2 および 3 以上の奇数で割るという方法があります。これは多少のムダは出るけど、全部の数で割るより効率的ですね。さらにうまいやり方があって、2, 3 以上は 5, 7, 11, 13, 17, 19, 23, 25, 29 .... と、ステップ幅を 2 と 4 の交代にして割っていくという方法があります。かしこいですね。これは例えば Ruby でこんなふうに書けます。
prime_factorize.rb

def prime_factorize(n)
  if n <= 1 or !n.class.ancestors.include?(Integer)
    raise ArgumentError, "#{n} incorrect."
  end
  result = {}
  divide = ->(i) {
    while (n % i).zero?
      result[i] = result.has_key?(i) ? result[i] + 1 : 1
      n /= i
    end
  }
  divide[2]
  divide[3]
  k, step = 5, 2
  guard = Math.sqrt(n).to_i
  while n != 1
    divide[k]
    k += step
    return result if k > guard    #高速化
    step = 6 - step
  end
  result
end

if __FILE__ == $0
  p prime_factorize(15141523320)    #=>{2=>3, 3=>3, 5=>1, 7=>2, 11=>1, 19=>1, 37=>2}
end

結果はハッシュで返ります。

なお、素因数分解は Ruby では標準添付ライブラリにあるので、実際はそれを使えばよいですね。ちなみに例えば 69316536495422 の素因数分解をやると、上のプログラムではフリーズしますが（笑）、ライブラリのメソッドだと苦もなく瞬時に素因数分解します。
（※追記：2行付け加えただけで劇的に高速化しました。これだと 69316536495422 の素因数分解でも一瞬です。（4/29））

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)