Pandoc：「サイゼリヤで1000円あれば最大何kcal摂れるのか」を解くLuaフィルタ

menu.csv

saizeriya.lua

-- saizeriya.lua
-- 「サイゼリヤで1000円あれば最大何kcal摂れるのか」
-- を求めるPandcoフィルタ (えっ)
--
-- @copyright 2019 Takayuki YATO (aka. "ZR")
--   GitHub:   https://github.com/zr-tex8r
--   Twitter:  @zr_tex8r
--   This program is distributed under the MIT License.
--
local filter_name = 'saizeriya'
---------------------------------------- 準備

--local utils = require 'pandoc.utils'
--local list = require 'pandoc.List'
--for name, fun in pairs(require 'text') do
--  string['uc_'..name] = fun
--end

local insert, unpack = table.insert, table.unpack

---------------------------------------- 設定

--- デバッグログを出すか
local show_log = false
--- 一覧出力用のリンク要素クラス
local class_list = 'saizeriya-list'
--- 計算結果出力用のリンク要素クラス
local class_solve = 'saizeriya-solve'
-- ※異常の2つのリンク要素を"特殊リンク要素"と呼ぶ.
--- 予算値用の属性キー
local attr_badget = 'badget'
--- 予算値の既定値
local attr_badget_default = 1000

---------------------------------------- general helpers

--- デバッグログを出力する.
local function log(fmt, ...)
  if not show_log then return end
  io.stderr:write(filter_name..': '..fmt:format(...).."\n")
end

-- 列に対して関数をマップする.
local function map(func, list)
  local res = {}
  for i = 1, #list do
    res[i] = func(list[i])
  end
  return res
end

---------------------------------------- load data file

--- メニューのデータファイルを読み込む.
-- ファイルはCSV形式(ヘッダ無し)でカラム定義は"名称,カロリー,価格".
-- @param fmenu ファイル名
-- @return メニュー(メニューアイテムの列)
local function load_menu_file(fmenu)
  local menu = {}
  local hm = assert(io.open(fmenu, 'r'))
  for line in hm:lines('l') do
    -- 各行を解析する
    local name, calo, cost = line:match('^(.-),(%d+),(%d+)$')
    assert(name, ("syntax error in data file (line %s)"):format(#menu + 1))
    insert(menu, {
      name = name, calorie = tonumber(calo), cost = tonumber(cost)
    })
  end
  hm:close()
  return menu
end

--- サイゼリヤ問題を動的計画法を用いて解く.
-- @param menu メニュー
-- @param badget 予算値
-- @return 選んだアイテムの添字の列
function solve_maximize(menu, badget)
  -- mcalo[k]は予算値kに対する最大カロリー値
  -- item[k]は最適解で最後に追加したアイテム(添字).
  local mcalo, item = {}, {}
  -- 初期化
  for k = 0, badget do
    mcalo[k], item[k] = 0, 0
  end
  -- アイテムごとのループ
  for i = 1, #menu do
    local calo, cost = menu[i].calorie, menu[i].cost
    for k = badget, cost, -1 do -- 重複禁止の場合
--    for k = cost, badget do -- 重複許容の場合
      local nmcalo = mcalo[k - cost] + calo
      if nmcalo > mcalo[k] then -- 最適解更新
        mcalo[k], item[k] = nmcalo, i
      end
    end
  end
  -- 最適解のアイテムのリストを求める
  local k, choice = badget, {}
  while item[k] > 0 do
    insert(choice, item[k]); k = k - menu[item[k]].cost
  end
  table.sort(choice, function(i, j) -- カロリーの降順でソート
    return menu[i].calorie > menu[j].calorie
  end)
  return choice
end

---------------------------------------- filter helpers

--- 要素が"空白"であるか.
local function is_space(el)
  return (el.t == 'Space' or el.t == 'LineBreak' or el.t == 'SoftBreak')
end

--- 単一文字列をPlainブロック列に変換する.
local function plain(str)
  return {pandoc.Plain({pandoc.Str(tostring(str))})}
end

--- 単一文字列を重要付でPlainブロック列に変換する.
local function plain_strong(str)
  return {pandoc.Plain({pandoc.Strong({pandoc.Str(tostring(str))})})}
end

--- 要素が特殊リンクである場合にその情報を返す.
-- @return 要素クラス名(saizeriya-XXX), 特殊でない場合はnil
-- @return メニューファイルのパス名(文法上はリンク先パス名)
-- @return 計算用の場合は予算値; 一覧用の場合はnil
local function saizeriya_link_info(el)
  if el.t ~= "Link" then return nil end
  if el.classes:includes(class_list) then -- 一覧出力要素
    return class_list, el.target
  elseif el.classes:includes(class_solve) then -- 計算結果出力要素
    local badget = tonumber(el.attributes['badget']) or attr_badget_default
    return class_solve, el.target, badget
  end
end

--- 段落を特定の位置で分割する.
-- 段落要素elの子のリストを"idxより前", "idx自体", "idxより後"(idxは添字)
-- の3つに分割し, 各々の部分を段落に変換してそれらの段落の列を返す.
-- ただし空になる部分についてはその段落は結果の列から省く.
-- @return 分割後の段落の列
-- @return "idx自体"の段落の位置(添字, 1または2)
local function split_paragraph(el, idx)
  local c, ib, ia = el.content, idx - 1, idx + 1
  -- 分割される位置にある"空白"の要素は削除する
  while ib > 0 do
    if not is_space(c[ib]) then break end
    ib = ib - 1
  end
  while ia <= #c do
    if not is_space(c[ia]) then break end
    ia = ia + 1
  end
  local res, ridx = {pandoc.Para({c[idx]})}, 1
  if ib > 0 then -- "前"がある
    insert(res, 1, pandoc.Para({unpack(c, 1, ib)}))
    ridx = 2
  end
  if ia <= #c then -- "後"がある
    insert(res, pandoc.Para({unpack(c, ia, #c)}))
  end
  return res, ridx
end

---------------------------------------- "precheck"フェーズ
-- 特殊リンク要素の配置には制限がある:
-- - 段落内にしか置けない. (例えば見出しに含めるのはダメ)
--   ※ブロック要素に置き換わるため.
-- - 1つの段落に高々1つしか置けない.
-- その条件が守られている("正当"と呼ぶ)かを検証する.
-- ※このフェーズでは要素の更新は起こらない.

--- 特殊リンク要素の個数 / 正当な要素の個数
local s_link, s_ok_link = 0, 0

--- precheckでのLink要素の処理.
-- 特殊リンクである場合はs_linkを計上する.
local function precheck_Link(el)
  local class = saizeriya_link_info(el)
  if not class then return end
  log("found link '%s'", class)
  s_link = s_link + 1
end

--- precheckでのPara要素の処理.
-- その要素の(直接の)子である特殊リンクをs_ok_linkに計上する.
local function precheck_Para(el)
  local count = 0 -- この要素内の特殊リンク個数
  for _, cel in ipairs(el.content) do -- 各子要素について
    local class, target = saizeriya_link_info(cel)
    if class then -- 特殊リンクである
      log("found valid link '%s' (%s)", class, target)
      s_ok_link, count = s_ok_link + 1, count + 1
    end
  end
  if count > 1 then -- 複数配置はダメ
    error("Multiple saizeriya links in a paragraph")
  end
end

--- precheckでのPandoc要素の処理.
-- 特殊リンク要素が全て正当であるかを検証する.
-- ※特定の処理を1度実行したいからPandoc要素をフックしているのであり,
-- 実際には要素は見ていない.
local function precheck_Pandoc()
  log("link count: all=%s, valid=%s", s_link, s_ok_link)
  if s_link ~= s_ok_link then -- 非正当なのがあるのでダメ
    error("Found saizeriya link outside paragraphs")
  end
end

---------------------------------------- "inject"フェーズ

--- 一覧出力のブロックを生成する.
-- メニューの一覧を記した箇条書き.
-- @param target メニューファイルのパス名
-- @param 生成したBulletList要素
local function saizeriya_list_block(target)
  local menu = load_menu_file(target)
  local items = {}
  for _, e in ipairs(menu) do
    local s = ("%s：%skcal，%s円"):format(e.name, e.calorie, e.cost)
    insert(items, plain(s))
  end
  return pandoc.BulletList(items)
end

--- 計算結果出力のブロックを生成する.
-- 最適解のアイテムの情報を記した表組.
-- @param target メニューファイルのパス名
-- @param badget 予算値
-- @param 生成したTable要素
local function saizeriya_solve_block(target, badget)
  -- 問題を解く
  local menu = load_menu_file(target)
  local choice = solve_maximize(menu, badget)
  -- 合計
  local tcalo, tcost = 0, 0
  for _, i in ipairs(choice) do
    tcalo, tcost = tcalo + menu[i].calorie, tcost + menu[i].cost
  end

  -- 表を生成する
  local align = {pandoc.AlignLeft, pandoc.AlignRight, pandoc.AlignRight}
  local header = map(plain, {
    "名称", "カロリー／kcal", "価格／円"
  })
  local body = map(function(i)
    local me = menu[i]
    return map(plain, {me.name, me.calorie, me.cost})
  end, choice)
  insert(body, map(plain_strong, {
    "合計", tcalo, tcost
  }))
  return pandoc.Table({}, align, {}, header, body)
end

--- injectでのPara要素の処理.
-- その要素の子要素である特殊リンク要素を所望のブロック要素(一覧用は
-- BulletList、計算用はTable)に変換して置き換える.
-- ※インライン要素をブロック要素に置き換えるため, 事前に段落を分割する.
-- @return 更新後の子要素列(更新しないならnil)
local function inject_Para(el)
  -- 子要素の中から特殊リンク要素を探す
  local cls, target, badget, idx
  for i, cel in ipairs(el.content) do
    cls, target, badget = saizeriya_link_info(cel)
    if cls then
      idx = i; break
    end
  end
  -- 特殊リンクがないなら更新しない
  if not idx then return nil end

  -- 段落を分割する
  local out, oidx = split_paragraph(el, idx)
  -- 特殊リンク要素を変換する
  if cls == class_list then
    out[oidx] = saizeriya_list_block(target)
  elseif cls == class_solve then
    out[oidx] = saizeriya_solve_block(target, badget)
  end

  return out
end

---------------------------------------- フィルタ定義
return {
  -- precheckフェーズは2回に分ける(順序を保証するため)
  { -- precheck前半
    Link = precheck_Link;
    Para = precheck_Para;
  };
  { -- precheck後半
    Pandoc = precheck_Pandoc;
  };
  { -- injectフェーズ
    Para = inject_Para;
  }
}
---------------------------------------- おしまい

sample.md

問題

予算1000円以内で，サイゼリヤで最大カロリーを摂取するような注文の仕方を求めよ。ただしサイゼリヤの料理のメニューは以下の通りとする。

一覧{.saizeriya-list}

解答

以下の通り。

解答{.saizeriya-solve badget=1000}

参照：「サイゼリヤで1000円あれば最大何kcal摂れるのか」をPandocで解いてみた