Ruby でモナドの一例

Ruby

m-hiyama.hatenablog.comこれを Ruby でやってみる。
　
countup_monad.rb

class Countup
  def initialize(value, countup = 0)
    @value = value
    @countup = countup
  end
  attr_reader :value, :countup
  
  def fmap
    c = yield @value
    if c.instance_of?(Countup)
      Countup.new(Countup.new(c.value, @countup + c.countup))
    else
      Countup.new(c, @countup)
    end
  end
  
  def bind(&bk)
    fmap(&bk).join
  end
  
  def join
    value
  end
end


def sum_countup5(x, y)
  Countup.new(x + y, 5)
end

def length_countup(str)
  len = str.length
  Countup.new(len, len)
end

def countup(n)
  Countup.new(nil, n)
end

def minus_count8(n)
  Countup.new(-n, 8)
end

あるいは

class Countup
  def fmap(&bk)
    Countup.new(bind(&bk), @countup)
  end
  
  def bind
    c = yield @value
    if c.instance_of?(Countup)
      Countup.new(c.value, @countup + c.countup)
    else
      c
    end
  end
end

　
実行例。

$ irb
irb(main):001:0> require_relative "countup_monad"
=> true
irb(main):002:0> length_countup("Hello, world!").bind { |n| Countup.new(n) }
=> #<Countup:0x0000556c80efea88 @value=13, @countup=13>
irb(main):003:0> Countup.new("Hello, world!").bind { |n| length_countup(n) }
=> #<Countup:0x0000556c81244238 @value=13, @countup=13>
irb(main):004:0> l = length_countup("Hello, world!")
=> #<Countup:0x0000556c8116e020 @value=13, @countup=13>
irb(main):005:0> m = l.bind { |n| sum_countup5(n, 10) }
=> #<Countup:0x0000556c8100aa80 @value=23, @countup=18>
irb(main):006:0> m.bind { countup(2) }
=> #<Countup:0x0000556c8124c320 @value=nil, @countup=20>
irb(main):007:0> l.bind { |n| sum_countup5(n, 10).bind { countup(2)} }
=> #<Countup:0x0000556c81254e08 @value=nil, @countup=20>

第1例と第2例がそれぞれ右単位元、左単位元。残りが結合法則。

$ irb
irb(main):001:0> require_relative "countup_monad"
=> true
irb(main):002:0> a = Countup.new(-8)
=> #<Countup:0x0000560f814cebe0 @value=-8, @countup=0>
irb(main):003:0> b = a.bind(&method(:minus_count8))
=> #<Countup:0x0000560f8175a350 @value=8, @countup=8>
irb(main):004:0> b.fmap { |n| n ** 2 }
=> #<Countup:0x0000560f81722ae0 @value=64, @countup=8>

元記事のnoeffect乃至unitがCountup.newに、extがbindに対応している。（元記事の「モナド」の定義はじつはクライスリトリプルの定義だと思う。）
副作用@countupを隠蔽している。
　
qiita.comこれにはモナドの遅延評価が実装されている。
kentutorialbook.github.io

ここでの自己関手TはCountupクラス、圏Cは全オブジェクト、自然変換ηはCountup.new、自然変換μはjoinに対応する。

ただし、本当はメソッドはすべて「ファーストクラス化」しないといけないのだろうけれど。
　

Haskell の「関数型問題解決法」を Ruby で

Ruby

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

作者:Miran Lipovača
発売日: 2012/05/23
メディア: 単行本（ソフトカバー）

第10章。
　
ほぼ忠実な移植。

heathrow_to_London =
  [
    [50, 10, 30],
    [5, 90, 20],
    [40, 2, 25],
    [10, 8, 0]
  ]

make_section = ->(ary) {%i(A B C).zip(ary).to_h}
t_sum = ->(path) {path.sum {_1.values[0]}}

road_step = ->((path_a, path_b), sct) {
  time_a = t_sum.(path_a)
  time_b = t_sum.(path_b)
  foward_time_to_a = time_a + sct[:A]
  foward_time_to_b = time_b + sct[:B]
  cross_time_to_a = time_b + sct[:B] + sct[:C]
  cross_time_to_b = time_a + sct[:A] + sct[:C]
  new_path_to_a = if foward_time_to_a <= cross_time_to_a
                    path_a + [{A: sct[:A]}]
                  else
                    path_b + [{B: sct[:B]}, {C: sct[:C]}]
                  end
  new_path_to_b = if foward_time_to_b <= cross_time_to_b
                    path_b + [{B: sct[:B]}]
                  else
                    path_a + [{A: sct[:A]}, {C: sct[:C]}]
                  end
  [new_path_to_a, new_path_to_b]
}

optimal_path = ->(road_system) {
  best_path_a, best_path_b = road_system.inject([[], []], &road_step)
  t_sum.(best_path_a) <= t_sum.(best_path_b) ? best_path_a : best_path_b
}

path = optimal_path.(heathrow_to_London.map(&make_section))
path_string = path.map {_1.keys[0]}.join
path_time = t_sum.(path)

puts "The best path to take is: " + path_string
puts "Time taken: #{path_time}"

　
結果。

The best path to take is: BCACBBC
Time taken: 75

　
これを見ていると、ここでの関数型プログラミングというのはそれほど特別なものではないな。injectを使っているくらいか。Ruby でも充分に記述できる。ただ、Haskell の強力な型記述で（ある意味では）自然な書き方になっているのはそうかな。

ちなみに、

heathrow_to_London.map(&make_section)
#=>[{:A=>50, :B=>10, :C=>30}, {:A=>5, :B=>90, :C=>20}, {:A=>40, :B=>2, :C=>25}, {:A=>10, :B=>8, :C=>0}]

path
#=>[{:B=>10}, {:C=>30}, {:A=>5}, {:C=>20}, {:B=>2}, {:B=>8}, {:C=>0}]

である。Haskell のSectionを Hash で表している。
　

別解

深さ優先探索（DFS）で総当り。

heathrow_to_London =
  [
    [50, 10, 30],
    [5, 90, 20],
    [40, 2, 25],
    [10, 8, 0]
  ]

result = ["", Float::INFINITY]

go = ->(from, sections, path = "", time = 0) {
  if sections.empty?
    p_re, t_re = result
    result = [path, time] if t_re > time
  else
    (a, b, c), *rest = sections
    case from
    when "A"
      go.("A", rest, path + "A", time + a)
      go.("B", rest, path + "AC", time + a + c)
    when "B"
      go.("A", rest, path + "BC", time + b + c)
      go.("B", rest, path + "B", time + b)
    end
  end
}

go.("A", heathrow_to_London)
go.("B", heathrow_to_London)

puts "The best path to take is: " + result[0]
puts "Time taken: #{result[1]}"

2020-11-23

ABC184

AtCoder Ruby

https://atcoder.jp/contests/abc184
　

A: Determinant

a, b, c, d = readlines.join.split.map(&:to_i)
puts a * d - b * c

B: Quizzes

n, x = gets.split.map(&:to_i)
str = gets.chomp

str.each_char do |s|
  case s
  when "o"
    x += 1
  else
    x -= 1 if x.nonzero?
  end
end

puts x

2020-11-23

どう書く

Ruby

オフラインリアルタイムどう書くの会場や問題のリスト - 鍋あり谷あり
　

ポーカー

https://qiita.com/Nabetani/items/cbc3af152ee3f50a822f

Suit = %W(S H D C)
Rank = %W(2 3 4 5 6 7 8 9 10 J Q K A)

def cards
  Suit.flat_map {|s|
    Rank.map {|r| s + r}
  }.sample(5).join
end

t = Regexp.compile("[#{Suit.join}]")
counted = cards.chars.slice_before(t).map {|a, *b| b.join}
  .tally.values.sort.reverse

ans = if counted[0] == 4
        "4K"
      elsif counted[0] == 3 && counted[1] == 2
        "FH"
      elsif counted[0] == 3
        "3K"
      elsif counted[0] == 2 && counted[1] == 2
        "2P"
      elsif counted[0] == 2
        "1P"
      else
        "--"
      end
puts ans

別解。

Suit = %W(S H D C)
Rank = %W(2 3 4 5 6 7 8 9 10 J Q K A)

def cards
  Suit.flat_map {|s|
    Rank.map {|r| s + r}
  }.sample(5).join
end

t = Regexp.compile("[#{Suit.join}]")
counted = cards.chars.slice_before(t).map {|a, *b| b.join}
  .tally.values.sort.reverse.join

["4", "32", "3", "22", "2", "1"].zip(%W(4K FH 3K 2P 1P --)).each do |c, h|
  if counted.start_with?(c)
    puts h
    break
  end
end

Tick-Tack-Toe

http://nabetani.sakura.ne.jp/hena/1/

class TickTackToe
  WinPattern = %W(123 456 789 147 258 369 159 357)
  def initialize(input)
    @input = input.chars.map(&:to_i)
    @field = Array.new(10)
    @turn = 0    #o
    @ptns = WinPattern.map {|pt| pt.chars.map(&:to_i)}
  end

  def solve
    @input.each do |i|
      if @field[i]
        return "Foul : #{output_turn(false)} won."
      else
        @field[i] = @turn
        if settle?
          return "#{output_turn} won."
        elsif @field[1..9].all?
          return "Draw game."  
        else
          @turn = 1 - @turn
        end
      end
    end
  end

  def settle?
    @ptns.any? do |pt|
      a = pt.map {|i| @field[i]}.join
      a == "000" || a == "111"
    end
  end

  def output_turn(t = true)
    %W(o x)[t ? @turn : 1 - @turn]
  end

  def self.solve(input)
    new(input).solve
  end
end


if $0 == __FILE__
  data = [79538246, 35497162193, 61978543, 254961323121, 6134278187, 4319581,
   9625663381, 7975662, 2368799597, 18652368566, 965715, 38745796, 371929,
   758698769, 42683953, 618843927, 36535224, 882973, 653675681, 9729934662,
   972651483927, 5439126787, 142583697, 42198637563, 657391482]

  data.each do |d|
    puts TickTackToe.solve(d.to_s)
  end
end

二値画像の回転

https://qiita.com/Nabetani/items/9d80de41903775296ca6

class BinaryImageRotation
  def initialize(input)
    l, @binary = input.split(":")
    @l = l.to_i
  end
  
  def solve
    n = (@l ** 2 / 4.0).ceil * 4
    ans = @binary.chars.map {|c| c.to_i(16).to_s(2).rjust(4, "0")}
      .join[0, @l ** 2].chars.map(&:to_i).each_slice(@l)
      .to_a.reverse.transpose
      .join.ljust(n, "0").chars.each_slice(4)
      .map {|ary| ary.join.to_i(2).to_s(16)}.join
    "#{@l}:" + ans
  end
  
  def self.exec(input)
    new(input).solve
  end
end


if __FILE__ == $0
  require 'minitest/autorun'
  describe 'BinaryImageRotation' do
    [
      ["3:5b8", "3:de0"], ["1:8", "1:8"], ["2:8", "2:4"],
      ["2:4", "2:1"], ["2:1", "2:2"], ["3:5d0", "3:5d0"], ["4:1234", "4:0865"],
      ["5:22a2a20", "5:22a2a20"], ["5:1234567", "5:25b0540"],
      ["6:123456789", "6:09cc196a6"], ["7:123456789abcd", "7:f1a206734b258"],
      ["7:fffffffffffff", "7:ffffffffffff8"],
      ["7:fdfbf7efdfbf0", "7:ffffffffffc00"],
      ["8:123456789abcdef1", "8:f0ccaaff78665580"],
      ["9:112233445566778899aab", "9:b23da9011d22daf005d40"]
    ].each do |input, expect|
      it input do
        assert_equal BinaryImageRotation.exec(input), expect 
      end
    end
  end
end

Bit Tetris

http://nabetani.sakura.ne.jp/hena/ord2/

module BitTetris
  module_function
  
  def solve(input)    
    field = input.split("-").map { _1.to_i(16) }
    to_be_erased = to_a(field.inject(:&))
    field.map { "%02x" % erase(_1, to_be_erased) }.join("-")
  end
  
  def erase(i, to_be_erased)
    to_a(i).zip(to_be_erased).map { |s, t| t == "1" ? "" : s }.join.to_i(2)
  end
  
  def to_a(i)
    sprintf("%08b", i).chars
  end
end


if __FILE__ == $0
  require 'minitest/autorun'
  describe 'BitTetris' do
    [
      ["ff-2f-23-f3-77-7f-3b", "1f-03-00-1c-0d-0f-06"],
      ["01", "00"],
      ["00", "00"],
      ["7a-4e", "0c-02"],
      ["56-b6", "08-14"],
      ["12-12-12", "00-00-00"],
      ["de-ff-7b", "0a-0f-05"],
      ["95-be-d0", "05-1e-20"],
      ["7c-b0-bb", "1c-20-2b"],
      ["7a-b6-31-6a", "3a-56-11-2a"],
      ["32-0e-23-82", "18-06-11-40"],
      ["ff-7f-bf-df-ef", "0f-07-0b-0d-0e"],
      ["75-df-dc-6e-42", "35-5f-5c-2e-02"],
      ["62-51-ef-c7-f8", "22-11-6f-47-78"],
      ["0c-47-8e-dd-5d-17", "04-23-46-6d-2d-0b"],
      ["aa-58-5b-6d-9f-1f", "52-28-2b-35-4f-0f"],
      ["ff-55-d5-75-5d-57", "0f-00-08-04-02-01"],
      ["fe-fd-fb-f7-ef-df-bf", "7e-7d-7b-77-6f-5f-3f"],
      ["fd-fb-f7-ef-df-bf-7f", "7e-7d-7b-77-6f-5f-3f"],
      ["d9-15-b5-d7-1b-9f-de", "69-05-55-67-0b-4f-6e"],
      ["38-15-fd-50-10-96-ba", "18-05-7d-20-00-46-5a"],
      ["fe-fd-fb-f7-ef-df-bf-7f", "fe-fd-fb-f7-ef-df-bf-7f"]
    ].each do |input, expect|
      it input do
        assert_equal BitTetris.solve(input), expect 
      end
    end
  end
end

ボールカウント(野球)

https://qiita.com/Nabetani/items/ebd8a56b41711ba459f9

module BallCount
  def self.solve(input)
    out = strike = ball = 0
    sb_zero = ->{ strike = ball = 0 }
    
    input.each_char.map {|c|
      case c
      when "s"
        strike += 1
        if strike == 3
          sb_zero.()
          out += 1
        end
      when "b"
        ball += 1
        sb_zero.() if ball == 4
      when "h"
        sb_zero.()
      when "p"
        out += 1
        sb_zero.()
      when "f"
        strike += 1 if strike <= 1
      end
      
      out = strike = ball = 0 if out == 3
      
      "#{out}#{strike}#{ball}"
    }.join(",")
  end
end


if __FILE__ == $0
  require 'minitest/autorun'
  describe 'BallCount' do
    [
      ["s", "010"],
      ["sss", "010,020,100"],
      ["bbbb", "001,002,003,000"],
      ["ssbbbb", "010,020,021,022,023,000"],
      ["hsbhfhbh", "000,010,011,000,010,000,001,000"],
      ["psbpfpbp", "100,110,111,200,210,000,001,100"],
      ["ppp", "100,200,000"],
      ["ffffs", "010,020,020,020,100"],
      ["ssspfffs", "010,020,100,200,210,220,220,000"],
      ["bbbsfbppp", "001,002,003,013,023,000,100,200,000"],
      ["sssbbbbsbhsbppp", "010,020,100,101,102,103,100,110,111,100,110,111,200,000,100"],
      ["ssffpffssp", "010,020,020,020,100,110,120,200,210,000"]
    ].each do |input, expect|
      it input do
        assert_equal BallCount.solve(input), expect 
      end
    end
  end
end

Y字路巡り

http://nabetani.sakura.ne.jp/hena/ord3ynode/

module YshapedRoadTour
  Graph = {"A"=>"DCB", "B"=>"CEA", "C"=>"FBA",
           "D"=>"EFA", "E"=>"DBF", "F"=>"ECD"}
           
  def self.solve(input)
    input = input.each_char
    result = ""
    
    go = ->(s, e) {
      result << e
      idx = Graph[e].index(s)
      case input.next
      when "b"
        go.(e, s)
      when "r"
        i = (idx - 1) % 3
      when "l"
        i = (idx + 1) % 3
      end
      go.(e, Graph[e][i])
    }
    go.("B", "A")
  rescue StopIteration
    result
  end
end


if __FILE__ == $0
  require 'minitest/autorun'
  describe 'YshapedRoadTour' do
    [
      ["b", "AB"],
      ["l", "AD"],
      ["r", "AC"],
      ["bbb", "ABAB"],
      ["rrr", "ACBA"],
      ["blll", "ABCAB"],
      ["llll", "ADEBA"],
      ["rbrl", "ACADE"],
      ["brrrr", "ABEDAB"],
      ["llrrr", "ADEFDE"],
      ["lrlll", "ADFEDF"],
      ["lrrrr", "ADFCAD"],
      ["rllll", "ACFDAC"],
      ["blrrrr", "ABCFEBC"],
      ["brllll", "ABEFCBE"],
      ["bbbrrlrl", "ABABEDFCB"],
      ["rbllrrrr", "ACABCFEBC"],
      ["lbrlrrblr", "ADABCFEFCA"],
      ["rlbrrrrbl", "ACFCADFCFD"],
      ["bllrlrbrrb", "ABCADEFEBCB"],
      ["rllrllllbb", "ACFDEBADEDE"],
      ["blblrlrrlbr", "ABCBEDFCABAC"],
      ["lrlrrrrrbrb", "ADFEBCFEBEDE"],
      ["rblllrlrrlrr", "ACABCADEFDABE"],
      ["rbrrlrblrllb", "ACADFEBEFDACA"],
      ["lrrrlrllrrllr", "ADFCABEFCADEBC"],
      ["rrlblllrrlrrb", "ACBEBADEFDABEB"],
      ["brbllrrbbrlrll", "ABEBADFCFCABEFC"],
      ["rrrbbrlbrlblrb", "ACBABACFCABADFD"],
      ["lllllllllllblrr", "ADEBADEBADEBEFDE"],
      ["llllllrllrlbrrr", "ADEBADEFCBADABED"]
    ].each do |input, expect|
      it input do
        assert_equal YshapedRoadTour.solve(input), expect 
      end
    end
  end
end

フカシギの通行止め

https://qiita.com/Nabetani/items/9c514267214d3917edf2
　
ループによる実装。

module CountFukashigi
  n = 5
  Goal = n * n - 1
  Pathes = n.times.flat_map {|i|
    n.times.map {|j|
      a = i * n + j
      [a - 1, a - n, a + n, a + 1]
    }
  }
  Pathes[0...n].map! { _1.delete_at(1) }
  Pathes[-n..-1].map! { _1.delete_at(2) }
  0.step(by: n, to: Goal) { |i| Pathes[i].delete_at(0) }
  (n - 1).step(by: n, to: Goal) { |i| Pathes[i].delete_at(-1) }
  
  def self.solve(input)
    table = Pathes.map(&:dup)
    
    input.split.each do |str|
      a, b = str.bytes.map { _1 - 97 }
      table[a].delete(b)
      table[b].delete(a)
    end
    
    result = 0
    stack = [[0]]
    
    loop do
      road = stack.pop
      break result unless road
      table[road[-1]].each do |nxt|
        next if road.include?(nxt)
        if nxt == Goal
          result += 1
        else
          stack << road + [nxt]
        end
      end
    end
  end
end


if __FILE__ == $0
  require 'minitest/autorun'
  describe 'CountFukashigi' do
    [
      ["", 8512],
      ["af", 4256],
      ["xy", 4256],
      ["pq qr rs st di in ns sx", 184],
      ["af pq qr rs st di in ns sx", 92],
      ["bg ch di ij no st", 185],
      ["bc af ch di no kp mr ns ot pu rs", 16],
      ["ab af", 0],
      ["ty xy", 0],
      ["bg ch ej gh lm lq mr ot rs sx", 11],
      ["ty ch hi mn kp mr rs sx", 18],
      ["xy ch hi mn kp mr rs sx", 32],
      ["ch hi mn kp mr rs sx", 50],
      ["ab cd uv wx", 621],
      ["gh mn st lq qr", 685],
      ["fg gl lm mr rs", 171]
    ].each do |input, expect|
      it input do
        assert_equal CountFukashigi.solve(input), expect
      end
    end
  end
end

結果。

Finished in 0.332796s, 48.0774 runs/s, 48.0774 assertions/s.

16 runs, 16 assertions, 0 failures, 0 errors, 0 skips

　
別解。再帰を使う。

module CountFukashigi
  n = 5
  Goal = n * n - 1
  Pathes = n.times.flat_map {|i|
    n.times.map {|j|
      a = i * n + j
      [a - 1, a - n, a + n, a + 1]
    }
  }
  Pathes[0...n].map! { _1.delete_at(1) }
  Pathes[-n..-1].map! { _1.delete_at(2) }
  0.step(by: n, to: Goal) { |i| Pathes[i].delete_at(0) }
  (n - 1).step(by: n, to: Goal) { |i| Pathes[i].delete_at(-1) }
  
  def self.solve(input)
    table = Pathes.map(&:dup)
    
    input.split.each do |str|
      a, b = str.bytes.map { _1 - 97 }
      table[a].delete(b)
      table[b].delete(a)
    end
    
    result = 0
    field = Array.new(Goal + 1)
    field[0] = true
    
    go = ->(now) {
      table[now].each do |nxt|
        if nxt == Goal
          result += 1
        else
          next if field[nxt]
          field[nxt] = true
          go.(nxt)
          field[nxt] = nil
        end
      end
    }
    go.(0)
    
    result
  end
end

結果。ループよりこちらの方が速い。

Finished in 0.135252s, 118.2977 runs/s, 118.2977 assertions/s.

16 runs, 16 assertions, 0 failures, 0 errors, 0 skips

テトロミノ認識

http://nabetani.sakura.ne.jp/hena/ord4tetroid/

module FindTetromino
  t = [[:L, 4, ["111", "100"]],
       [:L, 4, ["111", "001"]],
       [:T, 4, ["111", "010"]],
       [:I, 2, ["1111"]],
       [:S, 2, ["110", "011"]],
       [:S, 2, ["011", "110"]],
       [:O, 1, ["11", "11"]]]
  Tetrominos = t.map {|s, n, pt|
    pt = pt.map { _1.chars.map(&:to_i) }
    a = n.times.map {
      tmp = pt
      pt = pt.reverse.transpose
      tmp
    }.map {|blk|
      blk.flat_map.with_index {|row, y|
        row.filter_map.with_index { |b, x| [x, y] if b == 1 }
      }
    }
    [s.to_s] + a
  }
  N = 10
  
  module_function
  
  def each_tetromino
    Tetrominos.each do |name, *pts|
      pts.each { |pt| yield(name, pt) }
    end
  end
  
  def do(input)
    field = Array.new(N) { Array.new(N) }
    input.split(",").each do |str|
      str.chars.map(&:to_i).tap { |x, y| field[y][x] = true }
    end
    
    answer = "-"
    
    N.times do |y|
      N.times do |x|
        each_tetromino do |name, pattern|
          f = pattern.all? {|dx, dy|
            x1 = x + dx
            y1 = y + dy
            next if x1 < 0 || x1 >= N
            next if y1 < 0 || y1 >= N
            field[y1][x1]
          }
          answer = name if f
        end
      end
    end
    
    answer
  end
end


if __FILE__ == $0
  require 'minitest/autorun'
  describe 'FindTetromino' do
    [
      ["55,55,55,55", "-"],
      ["39,28,27,29", "L"],
      ["63,62,43,53", "L"],
      ["32,42,43,44", "L"],
      ["81,72,91,71", "L"],
      ["62,64,72,63", "L"],
      ["45,25,35,24", "L"],
      ["12,20,22,21", "L"],
      ["66,46,67,56", "L"],
      ["44,46,45,43", "I"],
      ["04,24,14,34", "I"],
      ["43,42,41,40", "I"],
      ["48,38,58,68", "I"],
      ["31,20,22,21", "T"],
      ["69,79,78,89", "T"],
      ["42,33,44,43", "T"],
      ["16,25,05,15", "T"],
      ["27,37,28,38", "O"],
      ["13,24,23,14", "O"],
      ["63,72,62,73", "O"],
      ["73,63,62,74", "S"],
      ["56,57,47,66", "S"],
      ["88,99,98,87", "S"],
      ["62,43,52,53", "S"],
      ["86,95,87,96", "S"],
      ["84,83,73,94", "S"],
      ["32,33,41,42", "S"],
      ["86,85,75,96", "S"],
      ["97,76,96,77", "-"],
      ["53,55,45,43", "-"],
      ["73,93,94,84", "-"],
      ["31,33,41,42", "-"],
      ["21,32,11,12", "-"],
      ["73,75,65,64", "-"],
      ["64,65,45,54", "-"],
      ["12,00,01,10", "-"],
      ["94,85,75,74", "-"],
      ["87,86,77,75", "-"],
      ["56,56,56,56", "-"],
      ["41,42,41,52", "-"],
      ["61,60,63,61", "-"],
      ["03,13,33,13", "-"],
      ["92,96,94,93", "-"],
      ["15,25,55,45", "-"],
      ["17,14,16,13", "-"],
      ["72,83,83,92", "-"],
      ["40,40,42,51", "-"],
      ["81,80,93,82", "-"],
      ["51,61,30,41", "-"],
      ["17,37,35,15", "-"]
    ].each do |input, expect|
      it input do
        assert_equal FindTetromino.do(input), expect
      end
    end
  end
end

Rails on Tiles

http://nabetani.sakura.ne.jp/hena/ord5railsontiles/

module RailsOnTiles
  Tiles = [[2, 3, 0, 1], [1, 0, 3, 2], [3, 2, 1, 0]]
  Dirs = [[0, -1], [1, 0], [0, 1], [-1, 0]]
  module_function
  
  def go(input)
    field = input.chars.map(&:to_i).each_slice(3).to_a
    solve(field).map { |i| ("A".."I").to_a[i] }.join
  end
  
  def solve(field, x=1, y=-1, dir=2, route=[])
    dx, dy = Dirs[dir]
    x += dx
    y += dy
    return route if x < 0 || x > 2 || y < 0 || y > 2
    rev = Tiles[0][dir]
    nxt = Tiles[field[y][x]][rev]
    tile_num = y * 3 + x
    solve(field, x, y, nxt, route + [tile_num])
  end
end


if __FILE__ == $0
  require 'minitest/autorun'
  describe 'RailsOnTiles' do
    [
      ["101221102", "BEDGHIFEH"],
      ["000000000", "BEH"],
      ["111111111", "BCF"],
      ["222222222", "BAD"],
      ["000211112", "BEFIHEDGH"],
      ["221011102", "BADGHIFEBCF"],
      ["201100112", "BEHIFCBADEF"],
      ["000111222", "BEFIH"],
      ["012012012", "BC"],
      ["201120111", "BEDABCFI"],
      ["220111122", "BADEHGD"],
      ["221011022", "BADG"],
      ["111000112", "BCFIHEBA"],
      ["001211001", "BEFI"],
      ["111222012", "BCFEHIF"],
      ["220111211", "BADEHI"],
      ["211212212", "BCFEBAD"],
      ["002112210", "BEFC"],
      ["001010221", "BEF"],
      ["100211002", "BEFIHG"],
      ["201212121", "BEFCBAD"]
    ].each do |input, expect|
      it input do
        assert_equal RailsOnTiles.go(input), expect 
      end
    end
  end
end

大貧民

http://nabetani.sakura.ne.jp/hena/ord5dahimi/

class Card
  Rank = %W(3 4 5 6 7 8 9 T J Q K A 2)
  def initialize(str)
    @value = str
    @rank = (str == "Jo") ? 13 : Rank.index(str[1])
  end
  attr_reader :value, :rank
  
  alias to_s value
end

module Daihinmin
  module_function
  
  def play(input)
    table, hand = input.split(",")
    return "-" unless hand 
    hand = hand.scan(/../).map { |c| Card.new(c) }
    joker = hand.find {|c| c.value == "Jo"}    
    table = table.scan(/../).map { |c| Card.new(c) }
    t_rank = table.map(&:rank).min
    t_num = table.size
    
    cs = hand.group_by(&:rank).select { |k, v| k > t_rank }.values
    result = cs.select { |ary| ary.size >= t_num }
               .flat_map { |ary| ary.combination(t_num).to_a }
    if joker && t_num >= 2
      result +=
        cs.select { |ary| ary.size >= t_num - 1 && ary[0] != joker }
          .flat_map {|ary|
            ary.combination(t_num - 1).map { |cards| cards + [joker] }
          }
    end
    
    result.empty? ? "-" : result.map(&:join).join(",")
  end
end


if __FILE__ == $0
  def same?(input, expect)
    inputs = input.split(",")
    expects = expect.split(",")
    return false unless inputs.size == expects.size
    equal = ->(a, b) {
      a == b || a.scan(/../).sort == b.scan(/../).sort
    }
    is_found = ->(ans) {
      s = expects.find { |e| equal.(e, ans) }
      return false unless s
      expects.delete(s)
      true
    }
    
    inputs.all?(&is_found)
  end
  
  [
    ["DJ,", "-"],
    ["H7,HK", "HK"],
    ["S3,D4D2", "D4,D2"],
    ["S9,C8H4", "-"],
    ["S6,S7STCK", "CK,ST,S7"],
    ["H4,SAS8CKH6S4", "S8,CK,H6,SA"],
    ["ST,D6S8JoC7HQHAC2CK", "Jo,C2,CK,HA,HQ"],
    ["SA,HAD6S8S6D3C4H2C5D4CKHQS7D5", "H2"],
    ["S2,D8C9D6HQS7H4C6DTS5S6C7HAD4SQ", "-"],
    ["Jo,HAC8DJSJDTH2", "-"],
    ["S4Jo,CQS6C9DQH9S2D6S3", "DQCQ,D6S6,H9C9"],
    ["CTDT,S9C2D9D3JoC6DASJS4", "JoC2,SJJo,DAJo"],
    ["H3D3,DQS2D6H9HAHTD7S6S7Jo", "JoHA,JoD6,JoH9,D6S6,D7S7,JoS6,HTJo,JoDQ,S2Jo,JoD7,JoS7"],
    ["D5Jo,CQDAH8C6C9DQH7S2SJCKH5", "CQDQ"],
    ["C7H7,S7CTH8D5HACQS8JoD6SJS5H4", "HAJo,JoSJ,H8S8,H8Jo,CQJo,CTJo,JoS8"],
    ["SAHA,S7SKCTS3H9DJHJH7S5H2DKDQS4", "-"],
    ["JoC8,H6D7C5S9CQH9STDTCAD9S5DAS2CT", "CTDT,H9D9,S9D9,DACA,CTST,H9S9,DTST"],
    ["HTST,SJHJDJCJJoS3D2", "DJCJ,SJDJ,JoHJ,CJHJ,SJJo,HJSJ,DJJo,JoCJ,JoD2,SJCJ,DJHJ"],
    ["C7D7,S8D8JoCTDTD4CJ", "D8S8,JoS8,CTJo,DTJo,JoCJ,CTDT,D8Jo"],
    ["DJSJ,DTDKDQHQJoC2", "JoDK,HQDQ,DQJo,C2Jo,JoHQ"],
    ["C3H3D3,CKH2DTD5H6S4CJS5C6H5S9CA", "S5H5D5"],
    ["D8H8S8,CQHJCJJoHQ", "JoCQHQ,JoHJCJ"],
    ["H6D6S6,H8S8D8C8JoD2H2", "D2H2Jo,D8JoS8,D8S8C8,C8D8H8,JoC8S8,H8JoC8,S8H8C8,JoS8H8,C8JoD8,D8H8S8,D8JoH8"],
    ["JoD4H4,D3H3S3C3CADASAD2", "DACASA"],
    ["DJHJSJ,SQDQJoHQCQC2CA", "SQJoCQ,DQCQJo,JoSQHQ,SQCQHQ,DQHQSQ,HQDQCQ,HQDQJo,SQDQCQ,CQJoHQ,SQJoDQ"],
    ["H3D3Jo,D4SKH6CTS8SAS2CQH4HAC5DADKD9", "HASADA"],
    ["C3JoH3D3,S2S3H7HQCACTC2CKC6S7H5C7", "-"],
    ["H5C5S5D5,C7S6D6C3H7HAH6H4C6HQC9", "C6D6S6H6"],
    ["H7S7C7D7,S5SAH5HAD5DAC5CA", "SADACAHA"],
    ["D4H4S4C4,S6SAH6HAD6DAC6CAJo", "C6H6S6D6,SAJoDACA,S6H6C6Jo,SACAJoHA,HADASAJo,HADAJoCA,CADAHASA,D6C6JoH6,S6D6C6Jo,H6JoS6D6"],
    ["DTCTSTHT,S3SQH3HQD3DQC3CQJo", "HQSQJoDQ,SQCQDQJo,DQCQHQJo,SQHQJoCQ,CQDQHQSQ"],
    ["JoS8D8H8,S9DTH9CTD9STC9CAC2", "H9C9D9S9"],
  ].each do |input, expect|
    p same? Daihinmin.play(input), expect
  end
end

続柄

http://nabetani.sakura.ne.jp/hena/ord6kinship/

module Relationship
  module_function
  
  def solve(start, goal)
    tree = Hash.new { |h, k| h[k] = [] }
    (1..40).each do |i|
      tree[i] << (i + 1) / 3 if i != 1
      (i*3-1..i*3+1).each { |j| tree[i] << j } if i < 14
    end
    
    result = move(tree, start, goal)
    table = {""=>:me, "-"=>:mo, "+"=>:da, "-+"=>:si, "--+"=>:au,
             "-++"=>:ni, "--++"=>:co}
    table.default = :-
    table[result]
  end
  
  def move(tree, start, goal, before=0, route="")
    return route if start == goal
    (tree[start] - [before]).each do |nxt|
      next_route = route + (nxt < start ? "-" : "+")
      return next_route if nxt == goal
      a = move(tree, nxt, goal, start, next_route)
      return a if a
    end
    nil
  end
end


if __FILE__ == $0
  require 'minitest/autorun'
  describe 'Relationship' do
    [
      [[5, 2], :mo],
      [[28, 10], :au],
      [[1, 1], :me],
      [[40, 40], :me],
      [[27, 27], :me],
      [[7, 2], :mo],
      [[40, 13], :mo],
      [[9, 3], :mo],
      [[4, 1], :mo],
      [[1, 3], :da],
      [[12, 35], :da],
      [[3, 8], :da],
      [[6, 19], :da],
      [[38, 40], :si],
      [[9, 8], :si],
      [[4, 2], :si],
      [[15, 16], :si],
      [[40, 12], :au],
      [[10, 4], :au],
      [[21, 5], :au],
      [[8, 2], :au],
      [[3, 5], :ni],
      [[11, 39], :ni],
      [[2, 13], :ni],
      [[13, 32], :ni],
      [[14, 22], :co],
      [[40, 34], :co],
      [[5, 8], :co],
      [[12, 10], :co],
      [[1, 27], :-],
      [[8, 1], :-],
      [[12, 22], :-],
      [[2, 40], :-],
      [[32, 31], :-],
      [[13, 14], :-],
    ].each do |input, expect|
      it input do
        assert_equal Relationship.solve(*input), expect 
      end
    end
  end
end

2020-11-15

ABC179

AtCoder Ruby

https://atcoder.jp/contests/abc179
　

A: Plural Form

str = gets.chomp
puts str + (str[-1] == "s" ? "es" : "s")

B: Go to Jail

n = gets.to_i
dice = n.times.map {gets.split.map(&:to_i)}

f = dice.each_cons(3).any? {|d1, d2, d3|
  d1[0] == d1[1] && d2[0] == d2[1] && d3[0] == d3[1]
}

puts f ? "Yes" : "No"

C: A x B + C

提出していないけれど、これはたぶん TLE。

require "prime"

n = gets.to_i

puts (1..n - 1).sum {|c|
  (n - c).prime_division.inject(1) {|acc, (a, b)| acc * (b + 1)}
}

できた。484ms。
総当りで、仮に a ≦ b とすれば、a は高々 √n 個で済む。

n = gets.to_i

x = Integer.sqrt(n)
ans = 0

(1..x).each do |a|
  (a..n / a).each do |b|
    c = n - a * b
    next if c < 1
    if a == b
      ans += 1
    else
      ans += 2
    end
  end
end

puts ans

上を圧縮。466ms。

n = gets.to_i

ans = 0

(1..Integer.sqrt(n)).each do |a|
  (a..n / a).each do |b|
    next if n - a * b < 1
    ans += (a == b) ? 1 : 2
  end
end

puts ans

さらに改良。64ms。わーい、いまのところ Ruby で最速！
b のループをせずに計算で済ませている。

n = gets.to_i

x = Integer.sqrt(n)
ans = 0

(1..x).each do |a|
  bn = n / a - a
  bn -= 1 if (n % a).zero?
  ans += bn * 2 + 1
end
ans += 1 if x * x == n

puts ans

D: Leaping Tak

TLEまちがいなし。

n, k = gets.split.map(&:to_i)
lrs = k.times.map {gets.split.map(&:to_i)}

s = (1..n).select {|i|
  lrs.any? {|l, r| (l..r).cover?(i)}
}
count = 0

try = ->(x) {
  if x == n
    count += 1
  else
    s.each do |jump|
      nxt = x + jump
      break if nxt > n
      try.(nxt)
    end
  end
}
try.(1)

puts count % 998244353

TLEだが、悪くない。メモ化。でも、s をすべて求めているのがいけないのだな。

n, k = gets.split.map(&:to_i)
lrs = k.times.map {gets.split.map(&:to_i)}

s = (1..n).select {|i|
  lrs.any? {|l, r| (l..r).cover?(i)}
}
memo = {}

try = ->(x) {
  return memo[x] if memo[x]
  count = 0
  s.each do |i|
    a = x + i
    if a > n
      break
    elsif a == n
      count += 1
    else
      count += try.(a)
    end
  end
  memo[x] = count
}

puts try.(1) % 998244353

公式解説の解法。わからんぞ。

n, k = gets.split.map(&:to_i)
lrs = k.times.map {gets.split.map(&:to_i)}.sort

MOD = 998244353

dp = Array.new(n, 0)
ans, dp[0], dp[1] = 0, 1, -1

(0...n).each do |i|
  ans = (ans + dp[i]) % MOD
  lrs.each do |l, r|
    break unless i + l < n
    dp[i + l] = (dp[i + l] + ans) % MOD
    next unless i + r + 1 < n
    dp[i + r + 1] = (dp[i + r + 1] - ans) % MOD
  end
end

puts ans

2020-11-02

ABC181

AtCoder Ruby

https://atcoder.jp/contests/abc181
　

A: Heavy Rotation

n = gets.to_i
puts n.even? ? "White" : "Black"

B: Trapezoid Sum

n = gets.to_i
abs = n.times.map {gets.split.map(&:to_i)}

puts abs.map {|a, b| (b - a + 1) * (a + b) / 2}.sum

C: Collinearity

n = gets.to_i
xys = n.times.map {gets.split.map(&:to_i)}

f = xys.combination(3).any? {|p1, p2, p3|
  v1x = p2[0] - p1[0]
  v1y = p2[1] - p1[1]
  v2x = p3[0] - p1[0]
  v2y = p3[1] - p1[1]
  v1x * v2y == v1y * v2x
}
puts f ? "Yes" : "No"

D: Hachi

与えられた文字列strが 3桁以下の場合は、順列による総当り。
そうでない場合は、8で割り切れる数は下3桁で決まることを使う。但しここでは 0 を含んではいけないことに注意。そのような 3桁の数をすべて求め、使う数字の個数の一覧を登録しておく（変数table）。また、同様にstrで使う数字のそれぞれの個数も調べる（変数tmp）。あとは、tableに含まれるcntの中に、「条件」を満たすものがひとつでもあればよい。「条件」とは、tmpがうまくcntを「含んで」いること。

table = (100..999).map {|i|
  next if (i % 8).nonzero?
  ds = i.digits
  next if ds.include?(0)
  count = Array.new(9, 0)
  ds.each {|n| count[n - 1] += 1}
  count
}.compact

str = gets.chomp

if str.size <= 3
  f = str.chars.permutation.any? {|cs|
    (cs.join.to_i % 8).zero?
  }
else
  tmp = Array.new(9, 0)
  str.each_char {|c| tmp[c.to_i - 1] += 1}
  f = table.any? {|cnt|
    sum = 0
    cnt.zip(tmp).each {|a, b| sum += a if b >= a}
    sum == 3
  }
end

puts f ? "Yes" : "No"

E: Transformable Teacher

n, m = gets.split.map(&:to_i)
hs = gets.split.map(&:to_i).sort
ws = gets.split.map(&:to_i).sort

s = t = 0
dp1 = [0] + hs.each_slice(2).map {|a, b| s += (b || 0) - a}
dp2 = [0] + hs.reverse.each_slice(2).map {|a, b| t += a - (b || 0)}

j = 0
ans = (0..n / 2).map {|i|
  h = hs[2 * i]
  j += 1 while j + 1 < m && (ws[j + 1] - h).abs <= (ws[j] - h).abs
  dp1[i] + dp2[n / 2 - i] + (h - ws[j]).abs
}.min

puts ans

これはこの解答をパクった。いまひとつわからない。

2020-10-18

ABC180

AtCoder Ruby

https://atcoder.jp/contests/abc180
　

A: box

n, a, b = gets.split.map(&:to_i)
puts n - a + b

B: Various distances

gets
xs = gets.split.map(&:to_i)

puts xs.map {_1.abs}.sum
puts Math.sqrt(xs.map {_1 * _1}.sum)
puts xs.map {_1.abs}.max

C: Cream puff

require "prime"

n = gets.to_i

table = n.prime_division.map {|a, b| (b + 1).times.map {|i| a ** i} }
table = [[1]] if table.empty?
puts table[0].product(*table[1..-1]).map {|ary| ary.inject(:*)}.uniq.sort

D: Takahashi Unevolved

x, y, a, b = gets.split.map(&:to_i)

ex = 0

loop do
  if (tmp = x * a) > x + b
    ex += (y - 1 - x) / b
    break
  else
    x = tmp
  end
  break if x >= y
  ex += 1
end

puts ex

2020-08-21

ABC175

AtCoder Ruby

https://atcoder.jp/contests/abc175
過去問。
　

A: Rainy Season

puts gets.chomp.each_char.chunk {|e| e == "R"}
         .map {|b, ary| b ? ary.size : 0}.max

B: Making Triangle

n = gets.to_i
ls = gets.split.map(&:to_i)

puts ls.combination(3).count {|li, lj, lk|
  li != lj && lj != lk && lk != li &&
  li + lj > lk && lj + lk > li && lk + li > lj
}

C: Walking Takahashi

x, k, d = gets.split.map(&:to_i)
 
x = x.abs
 
result = if x < k * d
  if k.even?
    n = x / (2 * d)
    a = x - n * 2 * d
    b = a - 2 * d
    [a.abs, b.abs].min
  else
    if x <= d
      (x - d).abs
    else
      x -= d
      n = x / (2 * d)
      a = x - n * 2 * d
      b = a - 2 * d
      [a.abs, b.abs].min
    end
  end
else
  x - k * d
end
 
puts result

ひどいタイポをしていた。まちがったコードをここにコピペして気づいた。

2020-08-04

ABC174

AtCoder Ruby

https://atcoder.jp/contests/abc174
過去問。
　

A: Air Conditioner

x = gets.to_i
puts (x >= 30) ? "Yes" : "No"

B: Distance

n, d = gets.split.map(&:to_i)
coordinates = n.times.map {gets.split.map(&:to_i)}

puts coordinates.count {|x, y| x * x + y * y <= d * d}

2020-05-17

ABC167

AtCoder Ruby

https://atcoder.jp/contests/abc167
過去問。
　

A: Registration

s = gets.chomp
t = gets.chomp

puts (t[0..-2] == s) ? "Yes" : "No"

B: Easy Linear Programming

a, b, c, k = gets.split.map(&:to_i)

score = 0

if a <= k
  score += a
  k -= a
  if b <= k
    k -= b
    if c <= k
      score -= c
    else
      score -= k
    end
  end
else
  score += k
end

puts score

C: Skill Up

全探索なのだけれど、ちょっと自信がなかった。一発で通ってホッ。

n, m, x = gets.split.map(&:to_i)
books = n.times.map {gets.split.map(&:to_i)}

min = 1200001

(1..n).each do |i|
  books.combination(i) do |selected|
    cost = 0
    f = selected.map {|price, *up|
      cost += price
      up
    }.transpose.map(&:sum).all? {_1 >= x}
    if f
      min = cost if cost < min
    end
  end
end

puts (min == 1200001) ? -1 : min

D: Teleporter

これは考えた。エッジケースがむずかしかった。

n, k = gets.split.map(&:to_i)
destinations = gets.split.map(&:to_i)

teleport = [1]
visited = Array.new(200001)
visited[1] = true

now = 1
while true
  nxt = destinations[now - 1]
  teleport << nxt
  break if visited[nxt]
  visited[nxt] = true
  now = nxt
end

idx = teleport.index(nxt)
ts = teleport.size
ans = if k < ts
        teleport[k]
      else
        loop_size = ts - idx - 1
        teleport[(k - idx) % loop_size + idx]
      end

puts ans

IOモナド

別解

A: Determinant

B: Quizzes

ポーカー

Tick-Tack-Toe

二値画像の回転

Bit Tetris

ボールカウント(野球)

Y字路巡り

フカシギの通行止め

テトロミノ認識

Rails on Tiles

続柄

A: Plural Form

B: Go to Jail

C: A x B + C

D: Leaping Tak

A: Heavy Rotation

B: Trapezoid Sum

C: Collinearity

D: Hachi

E: Transformable Teacher

A: box

B: Various distances

C: Cream puff

D: Takahashi Unevolved

A: Rainy Season

B: Making Triangle

C: Walking Takahashi

A: Air Conditioner

B: Distance

A: Registration

B: Easy Linear Programming

C: Skill Up

D: Teleporter