-- 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
  -- [[ insert or remove space before [[ to switch impls
  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
  --]] table.sort(bytes)
  -- 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

for line in f:lines() do
  -- 'line' excludes the trailing '\n' (file guarantees every word ends with '\n')
  if #line == #key and sort_string(line) == sorted_key then
    io.stdout:write(line, "\n")
  end
end

f:close()