かけっこのパズル（Ruby）

qiita.com
　

問題

一郎、二郎、三郎の三人で駆けっこをして、その結果を次のように言っています。
　
一郎：「僕は一番じゃない」
二郎：「僕は一番だ」
三郎：「僕は二番だ」

三人のなかで一人だけウソをついています。それは誰でしょう？
　

Ruby で解いてみた

総当りで解いています。
0, 1, 2 でそれぞれ一郎、二郎、三郎を表しています。

names = %W(一郎 二郎 三郎)
(0..2).each do |usotsuki|    #嘘つきを選びます
  table = [-1, 1, 2]    #与えられた条件（否定は負にします）
  #嘘をつかせます
  table[usotsuki] = -table[usotsuki]
  #可能性のある順位を配列にします
  tmp = table.map { _1 < 0 ? [1, 2, 3] - [-_1] : [_1] }
  #順位を総当りでまわして判定します
  [1, 2, 3].permutation do |candidate|
    if candidate.zip(tmp).all? { |c, ary| ary.include?(c) }
      puts "嘘つきは#{names[usotsuki]}です。"
      str = names.zip(candidate).map { |n, c| "#{n}が#{c}位" }.join("、")
      puts "ちなみに順位は#{str}です。"
    end
  end
end

結果

嘘つきは三郎です。
ちなみに順位は一郎が2位、二郎が1位、三郎が3位です。

辞書順で何番目か（Ruby）

辞書順（lexicographical order）に並べて何番目か、あるはn番目のものは何か。

要素に重複がないとして考える。数列 (1, 2, .... , n) の並べ替えとして解こう。

数列 (a₁, .. , a_n) は辞書順で何番目か。

def number_in_lex_order(ary)
  n = ary.size
  return 1 if n <= 1
  idx = ary.sort.bsearch_index { _1 >= ary[0] }
  (1..n - 1).inject(:*) * idx + number_in_lex_order(ary[1..-1])
end

number_in_lex_order([2, 1, 5, 3, 4])    #=>29

ここでは、数列の左端の数字が、数列を昇順にソートした中で何番目に来るかがわからなければならない。それを i (=idx+1) とすると、そこまでで (n - 1)! * (i - 1) だけ既に（一桁少ない部分）数列が並んでいることになる（ただし n は ary の桁数）。
あとは左端の一桁を落として同じことを（再帰で）求め、すべての和をとってやれば求まる。

文字列などならば、ハッシュで数列に変換するテーブルを作ってやればよい。

str = "MATH"
h = "AHMT".each_char.with_index(1).to_h

number_in_lex_order(str.each_char.map { h[_1] })    #=>14

もっとも、文字列ならば Ruby の柔軟性（？）のおかげで、

number_in_lex_order("MATH".chars)    #=>14

で求まってしまうのだが。

これの逆、つまり辞書順でn番目の数列はどうなるか。この場合、数列の長さ（size）を与えることが必要である。

def nth_sequence_in_lex_order(n, size)
  i = 1
  table = (1..size - 1).map { i *= _1 }
  
  order = (1..size).to_a
  ans = []
  n -= 1
  size.pred.times do
    factorial = table.pop
    i = n / factorial
    n -= i * factorial
    ans << (a = order[i])
    order.delete(a)
    break if n <= 0
  end
  ans.concat(order)
end

やってみる。

nth_sequence_in_lex_order(29, 5)     #=>[2, 1, 5, 3, 4]

よさそうだ。

上と同様に、文字列でもやってみる。これも、ハッシュでテーブルを作り、Hash#invert する。

h = "AHMT".each_char.with_index(1).to_h.invert

nth_sequence_in_lex_order(14, 4).map { h[_1] }.join    #=>"MATH"

これもよさそうだ。

なお、いずれも不正入力には対応していない。

約数を求める（Ruby）

prime ライブラリを使う。結果は順不同。

require "prime"

def divisors(n)
  result = [1]
  
  doit = ->(pd, acc) {
    return if pd.empty?
    x, *xs = pd
    (0..x[1]).each do |i|
      e = acc * x[0] ** i
      result << e
      doit.(xs, e)
    end
  }
  doit.(n.prime_division, 1)
  
  result.uniq
end

p divisors(24)    #=>[1, 3, 2, 6, 4, 12, 8, 24]

numo-gnuplot sample

qiita.com

ウィンドウで表示する場合。Linux Mint 20.3。

require "numo/gnuplot"

Numo.gnuplot do
  set terminal: "wxt font 'Noto Sans CJK JP,12'"
  set title: "グラフのタイトル"
  set xrange: 0..6
  set yrange: 0..60
  set xlabel: "x軸のラベル"
  set ylabel: "y軸のラベル"
  
  x = [1, 2, 3]
  y1 = [11, 25, 32]
  y2 = [21, 35, 42]
  y3 = [31, 45, 52]
  
  plot x, y1, {title: "系列1"},
       x, y2, {w: :lines, title: "系列2(線のみ)"},
       x, y3, {w: :linespoints, title: "系3（点と線）"},
       "x * 10", {title: "y = x * 10"}
end

sleep

単調非減少と単調非増加で配列（Enumerator）を切断する

要するにこれです。
atcoder.jp

配列 A が与えられます。 A を何箇所かで切って、A の連続した部分であるようないくつかの数列に分けます。 この時、分けられたあとの数列は全て、単調非減少または単調非増加な列になっている必要があります。

コード

Enumerable にこんなメソッドupdown_cutを生やしてみました。

module Enumerable
  def updown_cut
    e = to_enum
    updown = 0
    
    calc = ->(compare) {
      case updown
      when 0 then [compare, false]
      when -1
        case compare
        when -1, 0 then [-1, false]
        else [0, true]
        end
      else
        case compare
        when 1, 0 then [1, false]
        else [0, true]
        end
      end
    }
    
    begin
      a = e.next
    rescue StopIteration
      return self
    end
    
    pool = [a]
    loop do
      b = e.next
      updown, f = calc.(a <=> b)
      a = b
      if f
        yield pool
        pool = [a]
      else
        pool << a
      end
    end
    yield pool
    self
  end
end

使い方

配列（あるいは Enumerator）を単調非減少、あるいは単調非増加な配列になるよう切ってくれます。切られた配列はブロック変数に入ります。

[1, 2, 3, 2, 2, 1].updown_cut { p _1 }
#=>
#[1, 2, 3]
#[2, 2, 1]

ary = ([*1..7] * 2).shuffle
#=>[3, 1, 2, 7, 6, 7, 6, 5, 1, 5, 4, 4, 3, 2]
ary.enum_for(:updown_cut).to_a
#=>[[3, 1], [2, 7], [6, 7], [6, 5, 1], [5, 4, 4, 3, 2]]

str = ("abcdef" * 4).chars.shuffle.join
#=>"ecfdedcfecbabbbadfadcaef"
str.each_char.enum_for(:updown_cut).map(&:join)
#=>["ec", "fd", "edc", "fecba", "bbba", "df", "ad", "ca", "ef"]

　
いやあ、苦労しました。

Ractor でフィボナッチ数列

まずは小手調べ

takeするまで待って、takeするたびに無限に同じオブジェクトを返してくれる Ractor は、「Pull型通信」を使ってこんな風に作れる。

r = Ractor.new do
  loop { Ractor.yield 1 }
end

Array.new(5) { r.take }    #=>[1, 1, 1, 1, 1]

わかりやすいですね。

では、例えば単調増加列も簡単に作れる。

r = Ractor.new do
  i = 1
  loop do
    Ractor.yield i
    i += 1
  end
end

Array.new(5) { r.take }    #=>[1, 2, 3, 4, 5]

フィボナッチ数列を Ractor で計算してみる

こんなコードを書いてみた。

def fibonacci
  fib = Array.new(N + 1)
  
  2.times do |i|
    fib[i] = Ractor.new(i) do |j|
      loop { Ractor.yield j }
    end
  end
  
  (2..N).each do |i|
    fib[i] = Ractor.new(fib[i - 1], fib[i - 2]) do |a, b|
      e = a.take + b.take
      loop { Ractor.yield e }
    end
  end
  
  fib[N].take
end

fib[n]はfib[n - 1]とfib[n - 2]が計算するまで待ち（これらすべて Ractor オブジェクト）、双方が計算を終了したらtakeされるのを待つ。それで、takeされるたび、計算結果を返し続ける。

ってまあ、ほとんど意味のないプログラムだが、計算と一種の「メモ化」ですね。おもしろいといえばおもしろい。パフォーマンスはどうかというと、N = 3000 としてわたしの環境で 3.4秒くらい。3001個の Ractor オブジェクトが生成されるわけだが、どうなのかな。

なお、fib[3000].takeの結果は、

4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125

という具合です。

パスカルの三角形（Elixir）

obelisk.hatenablog.com
ここで Ruby でやっていることを、Elixir でやってみました。
こういうのを表示します。

              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      

コード

pascal_triangle.exs

defmodule PascalTriangle do
  def draw(1), do: [1]
  def draw(2), do: [1, 1]

  def draw(n) do
    [1] ++ (draw(n - 1) |> contract) ++ [1]
  end

  defp contract([]), do: []
  defp contract([_]), do: []

  defp contract([a1 | [a2 | rest]]) do
    [a1 + a2 | contract([a2 | rest])]
  end
end

defmodule ExString do
  def center(str, n) do
    s = String.length(str)
    a = div(n - s, 2)
    (String.duplicate(" ", a) <> str) |> String.pad_trailing(n)
  end
end

result =
  for i <- 1..8 do
    PascalTriangle.draw(i) |> Enum.join(" ") |> ExString.center(30)
  end

Enum.join(result, "\n") |> IO.puts()