Skip to content

Instantly share code, notes, and snippets.

@Heliodex

Heliodex/miu.fsx

Created August 29, 2025 22:54
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Heliodex/799bb679b7e825b09c74ed47606ba717 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Heliodex/799bb679b7e825b09c74ed47606ba717 to your computer and use it in GitHub Desktop.
Download ZIP
Various programs for calculating the MU puzzle.
Raw
miu.fsx
type MIU =
| M
| I
| U
type String = MIU list
let str (s: String) : string =
s
|> List.map (function
| M -> "M"
| I -> "I"
| U -> "U")
|> String.concat ""
let printset (s: String Set) =
printfn "\nSet of size %d:" (Set.count s)
printfn "%b" (Set.contains [ M; I; I; I; U; U; I; U; I; I; I ] s)
printfn "%b" (Set.contains [ M; I; I; I; U; U; I; U; U ] s)
// s |> Set.map str |> String.concat " " |> printfn "%s"
s
type Collection = String Set
let collection = Set.ofList [ [ M; I ] ]
// Rule I: If you possess a string whose last letter is I, you can add on a U at the end.
let rule1 =
function
| x when List.last x = I -> Set.ofList [ x @ [ U ] ]
| _ -> Set.empty
// Rule II: Suppose you have Mx. Then you may add Mxx to your collection.
let rule2 =
function
| M :: x -> Set.ofList [ M :: x @ x ]
| _ -> Set.empty
// Rule III: If III occurs in one of the strings in your collection, you may make a new string with U in place of III.
let rule3 =
function
| x when List.windowed 3 x |> List.contains [ I; I; I ] ->
let windows = List.windowed 3 x
// get the index of every iii
let poss =
List.zip [ 0 .. List.length windows - 1 ] windows
|> List.filter ((=) [ I; I; I ] << snd)
|> List.map fst
let befores = List.map (fun p -> List.take p x) poss
let afters = List.map (fun p -> List.skip (p + 3) x) poss
List.zip befores afters |> List.map (fun (b, a) -> b @ [ U ] @ a) |> Set.ofList
| _ -> Set.empty
// Rule IV: If UU occurs inside one of your strings, you can drop it.
let rec remove =
function
| [] -> [ [] ]
| U :: U :: t ->
let withUU = List.map (fun r -> U :: U :: r) (remove t)
remove t @ withUU
| h :: t -> List.map (fun r -> h :: r) (remove t)
let rule4 =
function
| x when List.windowed 2 x |> List.contains [ U; U ] -> remove x |> Set.ofList
| _ -> Set.empty
let fns = [ rule1; rule2; rule3; rule4 ]
let apply (s: Collection) : Collection =
s
|> Set.map (fun x -> fns |> List.map ((|>) x) |> Set.unionMany)
|> Set.unionMany
|> Set.union s
let rec iterate n (s: Collection) : Collection =
if n <= 0 then
s
else if Set.contains [ M; U ] s then
printfn "MU found!"
s
else
iterate (n - 1) (s |> printset |> apply)
collection |> iterate 7 |> printset
Raw
miu.luau
type M = "M"
local m: M = "M"
type I = "I"
local i: I = "I"
type U = "U"
local u: U = "U"
type MIU = M | I | U
type String = { MIU }
local collection: { String } = {
{ m, i },
} :: { String }
local function equals(a: String, b: String): boolean
if #a ~= #b then return false end
for j = 1, #a do
if a[j] ~= b[j] then return false end
end
return true
end
local function has(c: { String }, s: String)
for _, v in collection do
if equals(v, s) then return true end
end
return false
end
local function add(s: String)
if not has(collection, s) then table.insert(collection, s) end
end
local function str(s: { String })
local ss = {}
for _, v in s do
table.insert(ss, table.concat(v))
end
print(table.concat(ss, "\n"))
end
local function check(c: { String })
for _, v in c do
if equals(v, { m, u }) then
error "Found MU!"
return
end
end
end
-- Rule I: If you possess a string whose last letter is I, you can add on a U at the end.
local function rule1(s: String): { String }
if s[#s] ~= i then return {} end
local copy = table.clone(s)
table.insert(copy, u)
return { copy }
end
-- Rule II: Suppose you have Mx. Then you may add Mxx to your collection.
local function rule2(s: String): { String }
if s[1] ~= m then return {} end
local copy = table.clone(s)
for j = 2, #s do
table.insert(copy, s[j])
end
return { copy }
end
-- Rule III: If III occurs in one of the strings in your collection, you may make a new string with U in place of III.
local function rule3(s: String): { String }
if #s < 3 then return {} end
local results = {}
for j = 1, #s - 2 do
if s[j] ~= i or s[j + 1] ~= i or s[j + 2] ~= i then continue end
local copy = table.clone(s)
copy[j] = u
table.remove(copy, j + 1)
table.remove(copy, j + 1)
table.insert(results, copy)
end
return results
end
-- Rule IV: If UU occurs inside one of your strings, you can drop it.
local function rule4(s: String): { String }
if #s < 2 then return {} end
local results = {}
for j = 1, #s - 1 do
if s[j] ~= u or s[j + 1] ~= u then continue end
local copy = table.clone(s)
table.remove(copy, j)
table.remove(copy, j)
table.insert(results, copy)
end
return results
end
local fns: { (String) -> { String } } = { rule1, rule2, rule3, rule4 }
local bug1 = { m, i, i, i, u, u, i, u, i, i, i }
local bug2 = { m, i, i, i, u, u, i, u, u }
-- There is a bug due to the order of the functions being applied I think (eg. it doesn't produce MIIIUUIUU at the right time) but I cba figuring it out atm
for idx = 1, 7 do
print(`\nCollection of {#collection}`)
print(has(collection, bug1))
print(has(collection, bug2))
-- str(collection)
check(collection)
print(`--- Iteration {idx} ---`)
local tcc = table.clone(collection)
for fni, fn in fns do
-- print(`\nRule {fni}`)
for _, v in tcc do
local strs = fn(v)
-- str(strs)
for _, s in strs do
add(s)
end
end
end
end
print(`\nCollection of {#collection}`)
print(has(collection, bug1))
print(has(collection, bug2))
-- str(collection)
check(collection)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment