-- bagmatch.lua
-- Usage: luajit bagmatch.lua <key> <dictfile>
-- Prints dictionary words whose multiset of ASCII single-byte letters
-- equals that of <key>.
--
-- Approach:
-- 1. Sort letters of the key with an insertion sort into canonical order.
-- 2. For each line (word) in the file (each terminated by '\n'), strip the '\n',
--    sort its letters with the same insertion sort, compare strings; on match print.
-- Implementation favors explicit loops and string operations for LuaJIT speed.

local arg = assert(arg, "no args") -- keep code concise; will error if missing

local key = arg[1]
local fname = arg[2]

-- canonical sort: insertion sort on ASCII bytes of the given string
-- returns a new string with characters sorted ascending by byte
local function sort_string(s)
  local n = #s
  if n <= 1 then return s end
  -- build array of bytes (1-based)
  local bytes = {}
  for i = 1, n do
    bytes[i] = string.byte(s, i)
  end
  -- insertion sort over bytes
  for i = 2, n do
    local v = bytes[i]
    local j = i - 1
    while j >= 1 and bytes[j] > v do
      bytes[j+1] = bytes[j]
      j = j - 1
    end
    bytes[j+1] = v
  end
  -- convert back to string
  return string.char(unpack(bytes))
end

-- Precompute sorted key
local sorted_key = sort_string(key)

-- Open file for reading in binary mode to ensure exact single-byte handling
local f, err = io.open(fname, "rb")
if not f then
  io.stderr:write("error opening file: ", err, "\n")
  os.exit(1)
end

-- Read file in reasonably large chunks and process line by line.
-- Simpler approach: read full file into memory if it's expected to fit.
-- For speed and simplicity here, read in blocks and handle line buffering.
local chunk_size = 65536
local buffer = ""
local out = io.stdout

while true do
  local chunk = f:read(chunk_size)
  if not chunk then
    -- process remaining buffer only if it ends with '\n' assumption? Problem states each word is followed by '\n' including last, so buffer contains final line with '\n'.
    -- still process if buffer non-empty
    if buffer ~= "" then
      -- process any remaining lines (should be one, ending with '\n')
      -- split by '\n'
      local start = 1
      while true do
        local s, e = buffer:find("\n", start, true)
        if not s then break end
        local word = buffer:sub(start, s-1)
        if #word == #key then
          if sort_string(word) == sorted_key then
            out:write(word, "\n")
          end
        end
        start = e + 1
      end
    end
    break
  end

  buffer = buffer .. chunk

  -- extract complete lines
  local start = 1
  while true do
    local s, e = buffer:find("\n", start, true)
    if not s then
      -- keep remainder in buffer
      buffer = buffer:sub(start)
      break
    end
    local word = buffer:sub(start, s-1)
    -- quick length check before sorting
    if #word == #key then
      if sort_string(word) == sorted_key then
        out:write(word, "\n")
      end
    end
    start = e + 1
    -- if we've consumed whole buffer, clear it
    if start > #buffer then
      buffer = ""
      break
    end
  end
end

f:close()