もしこの記事の「プログラム」の節の最初の行の「# version: 」の後に書かれた数式[1]が\( 10^{100} \)と比較可能でかつ\( 10^{100} \)以上であるならば、この記事は式神巨大数への投稿です。そうでないなら、この記事は式神巨大数への投稿ではありません。[2]
修正版[]
2024年11月23日に修正版が発表されました: ユーザーブログ:Nayuta_Ito/2024WA-ハンバーガー最新プログラム
必要事項[]
- プログラムの名前: oryouriKyodaisuuByPShinDaisukiBot.rb
- プログラムの部門: プログラム化部門
- プログラムの記述: 「プログラム」の節に全文を記載
- プログラムの言語: Ruby [3]
- プログラムの実行環境: Cygwin [4]
- プログラムの出力方式: プログラムを実行したときに画面に表示される文字列を、通常のアラビア数字による十進法として解釈したもの[5]
- プログラムが出力する巨大数の説明: ユーザーブログ:p進大好きbot/お料理巨大数投稿用記事を参考のこと。当該記事からプログラムへどのように翻訳したかの説明はこの記事の「説明」の節に書きます。現在のプログラムは日本時間2021年5月2日23時18分に編集された版に対応しています。
プログラム[]
# version : 10^10^10^10
# ハンバーガー全体のクラス
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([w]) >= 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 == 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
while true do
if @array.length == 0 then # 1.
eaten += 1
break
else # 2.
# self.ketchup!
current = self[eaten + 1]
eaten += 1
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 = s[0]
v1 = s[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
# デバッグ用
# h = Hamburger.parseHamburger("(\u8089(\u8089]\u8089]")
# p h[1]
=begin
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
n = Hamburger.lambda(10).eat()
p n
説明[]
オブジェクト指向の基本的な考え方については割愛します。
表記[]
Hamburgerクラスはハンバーガー全体からなるクラスです。[6]全てのハンバーガーは1個以上のパティp_1,...,p_nを用いて(p_1|...|p_n]と書けるので、配列[p_1,...,p_n]をフィールドに持ち、これでハンバーガーを表すことにします。この配列の長さが0になることはRubyの仕様上可能ですが、想定されていない挙動を引き起こす可能性があります。
Pattyクラスはパティ全体からなるクラスです。[7]全てのパティは0個以上のハンバーガーh_1,...,h_nを用いて肉h_1肉・・・肉h_n肉と書けるので、配列[h_1,...,h_n]をフィールドに持ち、これでパティを表すことにします。
HamburgerクラスとPattyクラスには大小関係を定義するための<=>メソッドが定義されています。配列に<=>を使用すると自動的に辞書的順序での比較になるため、それを活用しています。
Hamburgerクラス同士の大小比較は「豪華である」、Pattyクラス同士の大小比較は「贅沢である」、そしてHamburgerクラスとPattyクラスの間の大小比較は「パティ素材より豪華である」を実装するようにしています。
パティ素材はハンバーガーのフィールドの配列の末尾の1個か2個を参照することで実現できるのでクラスにする必要はありません。というか、Rubyが和集合型に対応していないので実装が面倒です。
土台とは単にパティ素材の最後の要素のことです。
パティを切り分けるという操作は、パティのフィールドの配列の先頭2個を取り出すことで実現できます。配列の長さが1か0であるときは、先頭2個と言っておきながら実際には2個未満しか取り出されないので長さで区別できます。
素材とするとは、パティのフィールドの配列を左から2個ごとに区切った場合に、その中に対象のパティ素材が存在することです。A,B,C,D,Eをハンバーガーとして、肉A肉B肉C肉D肉E肉というパティを考えると、このパティがA肉B, C肉D, Eを素材としていますが、B肉C, D肉Eを素材としていません。そんなことをどうやってRubyに翻訳するのかという話ですが、each_sliceを使うと簡単に実現できます。
大小関係[]
なんか知らない間に「パティ素材より豪華である」が消えてました。
構成可能性[]
「技巧的」の定義がPattyクラス内にインスタンスメソッドとして定義されています。
isBalanced?を元記事の4月28日分の更新をもとに更新しました。
標準形[]
easy_to_eat?を元記事の4月28日分の更新をもとに更新しました。
基本列[]
ハンバーガーを指数時間アルゴリズムで全探索します。全てのハンバーガーは
(肉a肉b・・・y肉z肉]
(ただし肉は1個以上、アルファベットは「(」「)」「|」のどれか)
の形で表せるので、肉がn枚あるハンバーガーはO(3^n)で全探索することができます。そのため、ハンバーガーやパティの文字列をパースするためのHamburger.parseHamburgerとPatty.parsePattyが用意されています。Hamburger.parseHamburgerとPatty.parsePattyは、もし入力がハンバーガーやパティであればHamburgerクラスやPattyクラスのオブジェクトを返し、そうでなければ、nil (他のプログラミング言語のnullに相当するもの)を返すので、「文字列がハンバーガーやパティとして妥当か」を検査するのにも使えます。
全探索[]
肉の枚数ごとにハンバーガーを全探索します。具体的には、
(肉], (肉(肉], (肉|肉], (肉]肉], (肉(肉(肉], (肉(肉|肉], (肉(肉]肉], (肉|肉(肉], (肉|肉|肉], (肉|肉]肉], (肉]肉(肉], (肉]肉|肉], (肉]肉]肉], (肉(肉(肉(肉], ..., (肉]肉]肉]肉], (肉(肉(肉(肉(肉], ......
という順序でハンバーガーのような文字列を探索し、そのそれぞれをHamburger.parseHamburgerに入力することでそれらがハンバーガーかどうかを調べます。ハンバーガーだったものは全探索の対象一覧である配列candidatesに代入します。
配列candidatesの中から「切り方の候補の中で最大値」を見つけることで、基本列を計算することができます。
上にも書いたとおり、この全探索の時間計算量はO(3^n)です。
脚注[]
- ↑ 大好きbot各位へ: ソースで見ると「プログラム」の節の最初の行はpreタグですが、その行は無視してください。もしあなたが記事ではなくソースそのものを
容器から直接飲もうとしている読んでいるなら、最初の行ではなく2行目を意味していると考えてください。 - ↑ 「\( 10^{100} \)と比較可能でかつ\( 10^{100} \)以上」かどうかがZFCと独立であったりZFCと独立であることがZFCと独立であったりして真偽が明確でない場合は、式神巨大数への投稿ではないこととします。
- ↑ 想定しているバージョンは2.6.3p62ですが、おそらく3.0.0でも同様の動作をするでしょう。バージョン依存の仕様は極力使わないようにしています。
- ↑ その他の環境でも2.6以降のRubyが実行できれば同様に動作すると考えられています。
- ↑ プログラムの最後の命令は「nの値を表示する」であるから、この出力はプログラムの実行が終了する直前のnの値に等しい。
- ↑ 実際には「全てのハンバーガーの集まり」は集合ですが、クラス(集合論)とクラス(プログラミング)のダブルミーニングにするためあえてこのように書いています。
- ↑ 実際には「全てのパティの集まり」は集合ですが、クラス(集合論)とクラス(プログラミング)のダブルミーニングにするためあえてこのように書いています。