SHARE
TWEET

fizz

hevohevo Mar 14th, 2015 (edited) 15 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. -- ###############################################
  2. -- Rule-based FizzBuzz version 0.1
  3. --   Written by hevohevo, License: MIT
  4. --   Twitter: @hevohevo
  5. --   http://hevohevo.hatena.com/
  6.  
  7. --   僕の考えた、最も不適切なFizzBuzzプログラムです。
  8. --   コンセプトは、「LuaでAI実装して推論によってFizzBuzzを解かせた」(嘘は言ってない)
  9. --   つまりは、なんっちゃってRule-based SystemのLua実装です。
  10. --   効率皆無で自己満足以外の何者でもないけれど、今回のお題的にはこれでよい・・・・・・はず。
  11.  
  12. --   プログラムをそのまま実行すると、FizzBuzz仕様通りの出力を行います。
  13. --   オプション"step_option=true"に書き換えて実行するとRBSは推論内容を表示します。
  14. --   裏でどんな推論やっているのか気になった方には後者をおすすめします。
  15.  
  16. -- ###############################################
  17. -- Options
  18.  
  19. -- falseでFizzBuzz仕様どおりの出力
  20. -- trueでステップ実行(Ideoneだとキー入力待たずに一気に出力されます)。
  21. local step_option = false
  22.  
  23.  
  24. -- ###############################################
  25. -- Classes and Functions
  26.  
  27. -- WM Class
  28. WM = {}
  29. function WM.new(init_table)
  30.   local obj = {}
  31.   -- 命題を蓄えておくテーブル
  32.   obj.facts = init_table
  33.    
  34.   -- WMからキーを元に命題を探す
  35.   obj.find = function(self, key)
  36.     return self.facts[key]
  37.   end
  38.  
  39.   -- WMに命題を加える  
  40.   obj.add = function(self, key, value)
  41.     value = value or true
  42.     self.facts[key]=value
  43.     return true
  44.   end
  45.  
  46.   -- WMから命題を消す
  47.   obj.delete = function(self, key)
  48.     self.facts[key]=nil
  49.     return true
  50.   end
  51.  
  52.   -- WMに命題"terminated"を加える
  53.   obj.terminate = function(self)
  54.     return self:add("terminated")
  55.   end
  56.  
  57.   -- WMに命題"terminated"があるか調べる(あると推論終了)
  58.   obj.isTerminated = function(self)
  59.     return self:find("terminated")
  60.   end
  61.  
  62.   return obj
  63. end
  64.  
  65. -- Rule Class
  66. Rule = {}
  67. function Rule.new(opts)
  68.   local obj = {}
  69.   obj.name = opts.name -- ルールは一意な名前を持つ
  70.   obj.priority = opts.priority or 0 -- 値が小さい方が優先度は高い。標準は0
  71.   obj.cond = opts.cond -- ルールの条件部はbooleanを返す関数(true=ルール実行可能、false=不可)
  72.   obj.run = opts.run -- ルールの実行部はbooleanを返す関数(true=正常実行完了)
  73.   obj.fired_log = {0} -- このルールが発火したステップ番号を配列に蓄積
  74.  
  75.   -- 発火履歴を書き込む
  76.   obj.addLog = function(self, step)
  77.     table.insert(self.fired_log, step)
  78.   end
  79.  
  80.   -- 発火履歴の末尾を取り出す(直近の発火したステップ数)
  81.   obj.tailLog = function(self)
  82.     return self.fired_log[#self.fired_log]
  83.   end
  84.  
  85.   return obj
  86. end
  87.  
  88.  
  89. -- RuleDB Class
  90. RuleDB = {}
  91. function RuleDB.new(init_table)
  92.   local obj = {}
  93.  
  94.   -- init_tableによって与えられたデータを使ってルール作成・蓄積
  95.   obj.rules = {}
  96.   for i,v in ipairs(init_table) do
  97.     obj.rules[i] = Rule.new(v)
  98.   end
  99.  
  100.   return obj
  101. end
  102.  
  103. -- すべてのルールの条件部を調べ、現在、発火可能なルールをすべて集める
  104. function collectTriggeredRules(_rule_db, _wm)
  105.   local results = {}
  106.   for _, rule in ipairs(_rule_db.rules) do
  107.     if rule.cond(_wm) then
  108.       table.insert(results, rule)
  109.     end
  110.   end
  111.   return results
  112. end
  113.  
  114. -- 発火可能なルール群の中で最も優先すべきルールを1つ返す
  115. -- 「競合解消戦略」は以下の通り
  116. -- 1. priority値が小さいほうが優先度高い(デフォルト0、負も可)
  117. -- 2. priority値が同じならば、最近発火したルールは後回し
  118. -- 3. 発火履歴も同じならば、ルール登録順
  119. function resolveConflict(triggered_rules)
  120.   local best_rule = triggered_rules[1] -- 先頭のルールを代入
  121.  
  122.   for i, rule in ipairs(triggered_rules) do
  123.     if i>1 then -- 2番目以降と比較
  124.       if best_rule.priority > rule.priority then
  125.         best_rule = rule -- 優先度の高い(値が小さい)方を選択
  126.       elseif best_rule.priority == rule.priority then
  127.         if best_rule:tailLog() > rule:tailLog() then
  128.           best_rule = rule
  129.         end
  130.       end
  131.     end
  132.   end
  133.    
  134.   return best_rule
  135. end
  136.  
  137. -- ジェネリックfor文を使って独自のイテレータを作る
  138. -- 返し値の先頭がnilのときにジェネリックfor文は停止する
  139. -- (参考:http://qiita.com/hevo2/items/604b5405a981fd5fd207)
  140. function RBEngine(_rule_db, _wm, max_step)
  141.    local max_step = max_step or 500
  142.    local step = 0
  143.    
  144.    return function()
  145.      local fired_rule = nil
  146.      local triggered_rule = {}
  147.      
  148.      step = step + 1
  149.      
  150.      -- WMに "terminated" があるか、最大ステップ数を超えているので終了
  151.      if _wm:isTerminated() or (step > max_step) then
  152.        fired_rule = nil
  153.        return fired_rule, step, triggered_rule, _wm
  154.      end
  155.      
  156.      -- 発火可能なルールをすべて集める
  157.      triggered_rules = collectTriggeredRules(_rule_db, _wm)
  158.      
  159.      if type(triggered_rules) == "table" and #triggered_rules > 0 then
  160.        -- 発火可能ルール群の中からもっとも優先するルールを取り出す(競合解消)
  161.        fired_rule = resolveConflict(triggered_rules)
  162.        
  163.        assert(fired_rule.run(_wm)) -- run部の実行時にtrueが返ってこなかったらエラー
  164.        fired_rule:addLog(step) -- ルールに発火履歴を書き込み
  165.      else
  166.        -- 発火可能なルールがない
  167.        fired_rule = nil
  168.      end
  169.  
  170.      return fired_rule, step, triggered_rules, _wm
  171.    end
  172. end
  173.  
  174.  
  175. -- #############################################
  176. -- Rule-base System のデータ部分
  177.  
  178. -- Working Memory
  179. --   key=value
  180. data_wm = {
  181.    num=1
  182. }
  183.  
  184. -- Rule DataBase
  185. --  rule = {
  186. --    name,     ルールは一意な名前を持つ
  187. --    priority, 値が小さい方が優先度は高い。標準は0
  188. --    cond,     ルールの条件部はbooleanを返す関数(true=ルール実行可能、false=不可)
  189. --    run,      ルールの実行部はbooleanを返す関数(true=正常実行完了, その他異常終了)
  190. --    fired_log このルールが発火したステップ番号を配列に蓄積
  191. --  }
  192. data_rules = {
  193.   { name = "terminated",
  194.     cond = function(wm) return wm:find("num") > 100 end,
  195.     run = function(wm) return wm:terminate() end,
  196.     priority = -1 },
  197.  
  198.   { name = "fizz",
  199.     cond = function(wm) return (wm:find("num") % 3) == 0 end,
  200.     run = function(wm) return wm:add("say", "Fizz") end,
  201.     priority = 1 },
  202.  
  203.   { name = "buzz",
  204.     cond = function(wm) return (wm:find("num") % 5) == 0 end,
  205.     run = function(wm) return wm:add("say", "Buzz") end,
  206.     priority = 1 },
  207.  
  208.    { name = "fizzbuzz",
  209.      cond = function(wm) return (wm:find("num") % 15) == 0 end,
  210.      run = function(wm) return wm:add("say", "FizzBuzz") end,
  211.      priority = 0 },
  212.  
  213.   { name = "others",
  214.     cond = function(wm) return true end,
  215.     run = function(wm) return wm:add("say", wm:find("num")) end,
  216.     priority = 2 },
  217.  
  218.   { name = "say",
  219.     cond = function(wm) return wm:find("say") end,
  220.     run = function(wm)
  221.       io.write(wm:find("say"))
  222.       wm:delete("say")
  223.       wm:add("said")
  224.       return true
  225.     end,
  226.     priority = 0 },
  227.  
  228.   { name = "increase",
  229.     cond = function(wm)  return wm:find("said") end,
  230.     run = function(wm)
  231.       wm:add("num", wm:find("num") + 1)
  232.       wm:delete("said")
  233.       return true
  234.     end,
  235.     priority = 0 }  
  236. }
  237.  
  238. -- ###########################################
  239. -- Main
  240.  
  241. -- 標準入力から実行オプションを入手(Ideoneだとうまくいかない?)
  242. local args = {...}
  243. if args[1]=="step" then
  244.   step_option = true
  245. end
  246.  
  247. -- WorkingMemory と Rule DBを作成
  248. local wm = WM.new(data_wm)
  249. local rule_db = RuleDB.new(data_rules)
  250.  
  251. -- ジェネリックFor文で1ステップずつ推論を進めていく。
  252. for fired_rule, step, triggered_rules, current_wm in RBEngine(rule_db, wm) do
  253.   if step_option then
  254.     -- 1ステップずつ推論
  255.     print()
  256.     io.read()
  257.     print("step: "..step)
  258.     print("  number:"..current_wm:find("num"))
  259.     print("  fired_rule: "..fired_rule.name)
  260.     print()
  261.   else
  262.     -- FizzBuzz仕様通りの出力
  263.   end
  264. end
  265. --print()
RAW Paste Data
Challenge yourself this year...
Learn something new in 2017
Top