ユーザーブログ:Nayuta_Ito/2021HB-p進大好きbotさんの「お料理巨大数投稿用記事」をプログラミング言語に翻訳するにバグがあったので修正し、最新の定義を反映させました。
オリジナルの定義: ユーザーブログ:P進大好きbot/お料理巨大数投稿用記事
# version : 10→10→10
# require 'logger'
# ハンバーガー全体のクラス
class Hamburger
include Comparable
# arrayは1個以上のパティの列
def initialize(array)
@array = array
end
attr_reader :array
# to_sとinspect「表示」するための文字列を返す)
def to_s
str = "("
@array.each do |patty|
str += patty.to_s + "|"
end
# chopは文字列の最後の1文字を取り除く
# 最後が"\r\n"であればその2文字を取り除くが、ここではその仕様は考慮しなくてもよい
str = str.chop + "]"
return str
end
# inspectとはto_sのことである、と定義する
alias inspect to_s
# 大小関係
# self > other ならば +1
# self = other ならば 0
# self < other ならば -1
# Rubyの配列の仕様上これで実現できる
def <=>(other)
return @array <=> other.array
end
# 「パランスがよい」を判定する
# Rubyでは「is○○」の代わりに「○○?」を使う
def balanced?(y)
len = y.array.length
if len == 0 then # 1.
return false
else
w, v = y.odd_material # 2.
if @array.length == 1 then # 2.1.
x = @array[0]
if x.array.length == 0 then # 2.1.1.
return true
else # 2.1.2.
# 先生、スパゲティはハンバーガーの具材に入りますか！？
z, u = x.odd_material
cond1 = Hamburger.new([z]).balanced?(y)
cond2 = y.technical?(u) || Hamburger.new([y]) >= self
cond3 = u.length == 1
cond4 = u[0].balanced?(y)
cond5 = u.length >= 2 && u[0].balanced?(y) && u[1].balanced?(y) # こうしないとu[1]がnilになるのでエラーとなる
return cond1 && cond2 && (cond3 ? cond4 : cond5)
end
else # 2.2.
u = Hamburger.new(@array[0...-1])
x = @array[-1]
return u.balanced?(y) && Hamburger.new([x]).balanced?(y)
end
end
end
# 「食べやすい」を判定する
def easy_to_eat?
if @array.length == 1 then # 1.
x = @array[0]
len = x.array.length
if len == 0 then # 1.1.
return true
else # 1.2.
# 先生、スパゲティはハンバーガーの具材に入りますか！？
z, u = x.odd_material
cond1 = Hamburger.new([z]).easy_to_eat?
cond2 = u.length == 2 && z.array.length >= 2 && z.array.length % 2 == 0
cond3 = z.array.length >= 2 && z.array[-2] < u[0] # こうしないとz.array[-2]がnilになるのでエラーとなる
cond4 = u.length == 1
cond5 = u[0].easy_to_eat? && u[0].balanced?(x)
cond6 = u.length >= 2 && u[0].easy_to_eat? && u[1].easy_to_eat? && u[1].balanced?(x) # こうしないとu[1]がnilになるのでエラーとなる
return cond1 && (cond2 ? cond3 : true) && (cond4 ? cond5 : cond6)
end
elsif @array.length == 2 then # 2.
return Hamburger.new([@array[0]]).easy_to_eat? &&
Hamburger.new([@array[1]]).easy_to_eat? &&
Hamburger.new([@array[0]]) >= Hamburger.new([@array[1]])
else # 3.
return Hamburger.new(@array[0...-1]).easy_to_eat? && Hamburger.new(@array[-2..-1]).easy_to_eat?
end
end
# 基本列
# 指数時間アルゴリズム
# 後で実装する
def [](n)
num_meat = self.to_s.count("\u8089")
# 検索するハンバーガーの候補
candidates = []
for i in 1..(num_meat + n) do
if i == 1 then
candidates.push(Hamburger.parseHamburger("(\u8089]"))
else
# 全探索
for j in 0...(3 ** (i - 1)) do
str_num = j.to_s(3)
while str_num.length < i - 1 do
str_num = "0" + str_num
end
str_hamburger = "("
str_num.each_char do |digit|
str_hamburger += "\u8089"
case digit
when "0" then
str_hamburger += "("
when "1" then
str_hamburger += "|"
when "2" then
str_hamburger += "]"
end
end
str_hamburger += "\u8089]"
hamburger = Hamburger.parseHamburger(str_hamburger)
if !hamburger.nil? then
candidates.push(hamburger)
end
end
end
end
# 便宜上最小のハンバーガーを入れて開始
max = Hamburger.new([Patty.new([])])
for t in candidates do
if t.easy_to_eat? && t < self && t > max then
max = t
end
end
return max
end
# 急増加関数
# 記事には「再帰的」と書いてあるが、定義はループであり、
# 自分を呼び出している部分がどこにもないのである!
def eat()
eaten = 0
current = self
hamburger_atom = Hamburger.new([Patty.new([])])
# logger = Logger.new("refrigerator.log")
while true do
if current == hamburger_atom then # 1.
eaten += 1
break
else # 2.
# self.ketchup!
current = current[eaten + 1]
eaten += 1
# logger.info(current)
# logger.info(eaten)
end
end
return eaten
end
class << self
# Λ
# Hamburger.lambda(10)と呼び出すことを前提とする
def lambda(n)
if n == 0 then
return Hamburger.new([Patty.new([])])
else
return Hamburger.new([Patty.new([Hamburger.lambda(n - 1), Hamburger.lambda(n - 1)])])
end
end
# 文字列をハンバーガーとしてパースする
# パースできなければnilを返す
def parseHamburger(str)
unless str[0] == "(" && str[-1] == "]" then
return nil
else
# 文字列を|で分割するが、ネストされた部分では分割しない
tokens = [str[1]]
layer = 0
i = 2
pipe_on_base_layer = false
while i < str.length - 1 do
unless layer == 0 && str[i] == "|" then
if layer == 0 && str[i - 1] == "|" then
tokens.push(str[i])
else
tokens[-1].concat(str[i])
end
if str[i] == "(" then
layer += 1
elsif str[i] == "]" then
layer -= 1
end
end
i += 1
end
patties = tokens.map{|s| Patty.parsePatty(s)}
if patties.all? then
return Hamburger.new(patties)
else
return nil
end
end
end
end
end
# パティ全体のクラス
class Patty
include Comparable
# arrayは0個以上のハンバーガーの列
def initialize(array)
if array.nil? then
@array = []
else
@array = array
end
end
attr_reader :array
# to_sとinspect(「表示」するための文字列を返す)
def to_s
str = "\u8089" # うちのCygwinちゃんがコード中の全角文字を認識しないのでUnicodeで代用
@array.each do |hamburger|
str += hamburger.to_s + "\u8089"
end
return str
end
# inspectとはto_sのことである、と定義する
alias inspect to_s
# パティをオッドパティzとパティ素材sを用いてzs肉と表したときの[z, s]を返す
def odd_material
if @array.length == 0 then # 肉が入力された場合は便宜上無と無を返す
return [Patty.new([]), []]
else
oddlen = 0 # オッドパティの長さ
if @array.length % 2 == 0 then
oddlen = @array.length - 2
else
oddlen = @array.length - 1
end
z = Patty.new(@array[0...oddlen])
s = @array[oddlen..-1]
return [z, s]
end
end
# 大小関係
# self > other ならば +1
# self = other ならば 0
# self < other ならば -1
def <=>(other)
if other.array.length == 0 then # 1.
if @array.length == 0 then
return 0
else
return +1
end
elsif @array.length == 0 then # 2.
return -1
else # 3.
s = @array[0...2]
# @arrayが1項の場合はnilを返すが、initializeでnilチェックしているので問題ない
u = Patty.new(@array[2..-1])
t = other.array[0...2]
# other.arrayが1項の場合はnilを返すが、initializeでnilチェックしているので問題ない
v = Patty.new(other.array[2..-1])
if t.length == 1 then # 3.1.
if s.length == 1 && s[0] < t[0] then
return -1
elsif s.length > 1 || s[0] > t[0] then
return +1
else
return 0
end
end
if s.length == 1 && t.length != 1 then # 3.2.
return -1
end
# 3.3.
u0 = s[0]
u1 = s[1]
v0 = t[0]
v1 = t[1]
return [u0, u1, u] <=> [v0, v1, v]
end
end
# 技巧的
# 「uよりselfが技巧的である」を判定し、true/falseを返す
# uは1個か2個のハンバーガーからなる配列(パティ素材として使用)
def technical?(u)
if @array.length == 0 then # 1.
return false
else
w, v = self.odd_material # 2.
return (u[-1] < v[-1] || w.array.each_slice(2).to_a.index(u))
end
end
class << self
# 文字列をパティとしてパースする
# パースできなければnilを返す
def parsePatty(str)
unless str[0] == "\u8089" && str[-1] == "\u8089" then
return nil
else
# 肉だけのときは例外的にここで返す
if str == "\u8089" then
return Patty.new([])
end
# 文字列を肉で分割するが、ネストされた部分では分割しない
tokens = [str[1]]
layer = 1
i = 2
meat_on_base_layer = false
while i < str.length - 1 do
unless layer == 0 && str[i] == "\u8089" then
if layer == 0 && str[i - 1] == "\u8089" then
tokens.push(str[i])
else
tokens[-1].concat(str[i])
end
if str[i] == "(" then
layer += 1
elsif str[i] == "]" then
layer -= 1
end
end
i += 1
end
hamburgers = tokens.map{|s| Hamburger.parseHamburger(s)}
if hamburgers.all? then
return Patty.new(hamburgers)
else
return nil
end
end
end
end
end
=begin
# デバッグ用
h = Hamburger.parseHamburger("(\u8089(\u8089]\u8089]")
p h[1]
h = Hamburger.parseHamburger("(\u8089(\u8089]\u8089]")
p h.eat()
require 'benchmark'
nothingPatty = Patty.new([])
nothingBurger = Hamburger.new([nothingPatty])
layer2Patty = Patty.new([nothingBurger, nothingBurger])
layer2Burger = Hamburger.new([layer2Patty])
layer3Patty = Patty.new([layer2Burger])
layer3Burger = Hamburger.new([layer3Patty])
p layer3Burger
for i in 0..5 do
Benchmark.bm do |x|
x.report(i.to_s + ":") do
p layer3Burger[i]
end
end
end
# [5]の計算には筆者のコンピュータで37秒を要した
=end
# p Hamburger.new([Patty.new([])])
# n = Hamburger.lambda(10).eat()
# p n