単調非減少と単調非増加で配列(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()

Hit&Blow を Ruby で

qiita.comおもしろそうなので、自分でも書いてみた。
 

ルール

コンピュータの決めた、各桁に重複のない3桁の数を当てるゲーム。
当たらなかった場合、

  • 入力と桁の合っている数字の数を、ヒット
  • 入力と桁は合っていないが重複はしている数字の数を、ブロウ

として教えてくる。
 

実行例

各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 135
ヒット:1, ブロウ:0
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 315
ヒット:0, ブロウ:1
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 351
ヒット:0, ブロウ:1
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 124
ヒット:1, ブロウ:0
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 106
ヒット:1, ブロウ:1
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 160
ヒット:2, ブロウ:0
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 170
ヒット:2, ブロウ:0
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 180
ヒット:2, ブロウ:0
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 190
正解です! 9回で当てました!

 

コード

hit_and_blow.rb

module Hit_and_Blow
  module_function
  
  N = 3
  
  def input
    expl = (0...N).to_a.join
    loop do
      print "各桁のそれぞれちがう、#{N}桁の数を入力して下さい(例:#{expl}): "
      s = gets.chomp.chars
      if s.size != N || s.uniq.size != N || s.any?(/\D/)
        puts "不正な入力です。"
      else
        return s
      end
    end
  end
  
  def judge(target, number)
    overlap = (target & number).size
    hit = target.zip(number).count { |a, b| a == b }
    [hit, overlap - hit]
  end
  
  def play
    target = [*"0".."9"].sample(N)
    (1..).each do |n|
      number = input
      
      if target == number
        puts "正解です! #{n}回で当てました!"
        break
      else
        hit, blow = judge(target, number)
        puts "ヒット:#{hit}, ブロウ:#{blow}"
      end
    end
  end
end

Hit_and_Blow.play

N = 3だと簡単ですが、N = 4にすると結構手ごわいです。

Enumerator#rest みたいなのが欲しい

Ruby の Enumerator で、列挙はひとつずつしかできない。まとめていくつか列挙できるメソッドが欲しい。

こんな感じ。

class Enumerator
  def rest(n=nil)
    ary = []
    case n
    in nil
      loop { ary << self.next }
    in Integer => a
      a.times { ary << self.next }
    end
    ary
  end
end


a = [*1..10].to_enum

a.next    #=>1
a.next    #=>2
a.rest(4) #=>[3, 4, 5, 6]
a.next    #=>7
a.rest    #=>[8, 9, 10]

ダメですかねえ…。

Ruby の slice が便利になった

Python

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10][1:10:3]    #=>[2, 5, 8]

って便利ですよね。Ruby でこれをやろうとすると、ちょっと工夫が必要でした。

例えばこんな感じに。

1.step(9, 3).map { [*1..10][_1] }    #=>[2, 5, 8]

 
しかし、これはいまではこんな風に書けるようです。

s = (1...10).step(3)
s.class    #=>Enumerator::ArithmeticSequence
[*1..10].slice(s)    #=>[2, 5, 8]

 
これの応用で、さらに短く書けます。

[*1..10].slice((1...10) % 3)   #=>[2, 5, 8]
[*1..10][(1...10) % 3]   #=>[2, 5, 8]

便利ですね。

Ruby でコラッツの問題

ja.wikipedia.org
「コラッツの問題」というのは、自然数 n を取り、

  • n が偶数なら2で割る
  • n が奇数なら、3倍して1を足す

という操作を繰り返したところ、どうなるかという問題。じつはこれは難問で、いまだに解決されていない。いまのところ、初期値が268あたりまで、1に帰結することが知られているそうである。

Ruby で計算してみる。初期値が10万までの範囲での、1に至るステップ数の最大値を求めるコードを、再帰で実装する。

def collatz(n, co = 0)
  return co if n == 1
  n.even? ? collatz(n / 2, co + 1) : collatz(3 * n + 1, co + 1)
end

puts (1..10_0000).map(&method(:collatz)).max    #=>350

最大値は350ステップとわかる。実行時間は、僕の環境で0.94秒ほどでした。


350ステップかかるときの初期値を求めてみる。コードの後半をこう書き直す。

max = 0
max_idx = 1
(1..10_0000).each do |i|
  step = collatz(i)
  if step > max
    max = step
    max_idx = i
  end
end
p [max_idx, max]    #=>[77031, 350]

初期値が77031のとき350ステップかかることがわかる。
 

追記

メモ化できるよう、コードを修正してみる。

$memo = {}

def collatz(n)
  return $memo[n] if $memo[n]
  return 0 if n == 1
  sum = n.even? ? collatz(n / 2) : collatz(3 * n + 1)
  $memo[n] = sum + 1
end

puts (1..10_0000).map(&method(:collatz)).max    #=>350

これだと0.12秒で済む。100_0000回までやっても1.5秒ほど、ちなみに初期値が837799のとき、最大値524ステップを取る。もう一桁上げて、1000_0000回までやると、初期値8400511のとき、最大値685ステップ。