#!/usr/bin/env python3

"""miu.py 0.2

Usage: miu.py [initial-words] [-g goal]

Play the MIU-game from Hofstaedter's "Goedel, Escher, Bach". This is a
simple string substitution game, applying the rules below to a set of
starting words (originally "MI"), trying to derive a particular goal
(orginally, MU).

xI    -> xIU
xIIIy -> xUy
xUUy  -> xy
Mx    -> Mxx

The programm will derive new strings "forever" unless it derives the
(optional) goal. It will print derivations (chains of intermediate
words, starting with the inially given words) for short words. 

Options:

-h Print this help.
-g Give the goal to derive
-s Expand shortest words first (default it to expand them in the order
   they were generated in.
-l Short word limit (derivations are only printed for words up tp this
   length. Default is 6.

Examples: 

  Generate all words, expanding the shortest ones first
  > ./miu.py -s
  MI []
  MIU ['MI']
  MII ['MI']
  MIIU ['MII', 'MI']
  ...

  Generate words until MIIIII has been derived.   
  > ./miu.py -g MIIIII
  MI []
  MIU ['MI']
  MII ['MI']
  ...
  MIIIII ['MIIIIIUU', 'MIIIIIIIIU', 'MIIIIIIII', 'MIIII', 'MII', 'MI']
  Success


Copyright 2014, 2021 Stephan Schulz, schulz@eprover.org

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program ; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston,
MA  02111-1307 USA 

The original copyright holder can be contacted as

Stephan Schulz
DHBW Stuttgart
Informatik
Postfach 10 05 63
D-70004 Stuttgart
Germany
schulz@eprover.org.

"""

import sys
import getopt

goal = "MU"
"""
If this word is derived, stop. Since MU is not derivable, the default
is to go on deriving words forever.
"""

words = ["MI"]
"""
Default is to play the version from the book.
"""

shortest = False
"""
Default is to do FIFO.
"""

limit = 6
"""
Length of the longest word to be printed with derivation. 
"""


def rule1(word):
    if word[-1] == "I":
        return [word+"U"]
    return []

def rule2(word):
    result = []
    for i in range(len(word)-2):
        if word[i:i+3] == "III":
            new = word[:i]+"U"+word[i+3:]
            result.append(new)
    return result
    
def rule3(word):
    result = []
    for i in range(len(word)-1):
        if word[i:i+2] == "UU":
            new = word[:i]+word[i+2:]
            result.append(new)
    return result

def rule4(word):
    if word[0] == "M":
        return [word+word[1:]]
    return []

def popShortest(words):
    if words:
        result = words[0]
        minl   = len(result)
        for word in words[1:]:
            if len(word) < minl:
                result = word
                minl = len(result)
        words.remove(result)
        return result
    return None

def derivation(known, word):
    deriv = []
    while known[word]:
        word = known[word]
        deriv.append(word)
    return deriv


if __name__ == '__main__':
    opts, args = getopt.gnu_getopt(sys.argv[1:], "hg:sl:",
                                   ["help", "goal=", "shortest-first",
                                    "limit="])

    for option, optarg in opts:
        if option == "-h" or option == "--help":
            print(__doc__)
            sys.exit()
        elif option == "-g" or option == "--goal":
            goal = optarg
        elif option == "-s" or option == "--shortest-first":
            shortest = True;
        elif option == "-l" or option == "--limit":
            limit = int(optarg)
        else:
            sys.exit("Unknown option "+ option)

    if args:
        words = args

known = {}
for word  in words:
    known[word] = False


while words:
    if shortest:
        given = popShortest(words)
    else:
        given = words.pop(0)
    d = derivation(known, given)
    if len(given) <= limit:
        print(given, d)
    else:
        print(given)

    if given == goal:
        print("Success")
        sys.exit()
    for rule in [rule1, rule2, rule3, rule4]:
        new = rule(given)
        for word in new:
            if not word in known:
                words.append(word)
                known[word] = given