ACSL: "A rock implements every finite-state automaton"; just need to find the right one…

all_stars_2009–10_7.py

#!/usr/bin/env python3

__author__ = 'Yatharth Agarwal <[email protected]>'

from collections import defaultdict
import itertools


START_STATE = 0
FINAL_STATE = -1


def visualize_consumer(consumer):
    output = consumer('1')
    if output == 1:
        return '1'
    elif output is None:
        return '0'
    elif output == 0:
        return '∂'
    else:
        raise ValueError("invalid consumer")

def visualize_fsm(fsm):
    output = []
    for from_state, state_cons_dict in fsm.items():
        for to_state, consumers in state_cons_dict.items():
            output.append("{} -> {}: [{}]".format(from_state, to_state,
                    ", ".join(map(visualize_consumer, consumers))))
    output.append("")
    return output


def next_state_number(states):
    return 1 + max(itertools.chain(
                states.keys(),
                (to_state for from_state, state_cons_dict in states.items() for to_state in state_cons_dict)
            ), default=0)


def make_consumer(char=None):
    return lambda x: 0 if char is None else 1 if x == char else None


def make_fsm(regex, pos=0):
    states = defaultdict(lambda: defaultdict(list))
    curr_state = START_STATE

    assert regex[pos] == '(', ValueError("regex doesn't begin with an open parenthesis")
    pos += 1

    while pos < len(regex):

        if regex[pos] in ('0', '1'):
            to_state = next_state_number(states)
            consumer = make_consumer(regex[pos])

            if regex[pos + 1] == '*':
                states[curr_state][to_state].append(make_consumer())
                curr_state = to_state
                pos += 1

            states[curr_state][to_state].append(consumer)
            curr_state = to_state

        elif regex[pos] == 'U':
            states[curr_state][FINAL_STATE].append(make_consumer())
            curr_state = START_STATE

        elif regex[pos] == '(':
            # if curr_state == 0:
            #     to_state = next_state_number(states)
            #     states[curr_state][to_state].append(make_consumer())
            #     curr_state = to_state

            other_states, pos = make_fsm(regex, pos)
            kleene = regex[pos + 1] == '*'

            if kleene:
                to_state = next_state_number(states)
                states[curr_state][to_state].append(make_consumer())
                curr_state = to_state
                pos += 1

            padding_state = next_state_number(states)
            for from_state, state_consumer_dict in other_states.items():
                for other_to_state, consumers in state_consumer_dict.items():
                    if other_to_state != FINAL_STATE:
                        states \
                            [padding_state + from_state if from_state != START_STATE else curr_state] \
                            [padding_state + other_to_state if to_state != START_STATE else curr_state]\
                                .extend(consumers)

            to_state = curr_state if kleene else next_state_number(states)
            for from_state, state_consumer_dict in other_states.items():
                for other_to_state, consumers in state_consumer_dict.items():
                    if other_to_state == FINAL_STATE:
                        states[padding_state + from_state][to_state].extend(consumers)

            curr_state = to_state

        elif regex[pos] == ')':
            states[curr_state][FINAL_STATE].append(make_consumer())
            return states, pos

        else:
            raise ValueError("invalid character '{}'".format(regex[pos]))

        pos += 1

    raise ValueError("regex continued after final close parenthesis")


def find_max(fsm, string, pos, from_state=START_STATE):

    if pos == len(string):
        return pos
    elif pos > len(string):
        raise ValueError("position greater than length of string")

    max_consumed = pos

    for to_state, consumers in fsm[from_state].items():
        for consumer in consumers:

            consumed = consumer(string[pos])
            if consumed is not None:

                other_consumed = find_max(fsm, string, pos + consumed, to_state)
                max_consumed = max(max_consumed, other_consumed)

    return max_consumed


def main():
    TEST = [
        "1*110*, 10110",
        "(10)*1*, 1010100",
        "(01)*U(1*0), 0101110",
        "(0(1U0)*)*U(1*0), 010011"
    ]

    regex, string = map(str.strip, TEST[3].split(','))
    fsm, _ = make_fsm("({})".format(regex))
    out = find_max(fsm, string, 0)

    if out == len(string):
        print("yes")
    elif out < len(string):
        print("No, {}".format(out))
    else:
        raise AssertionError("consumed more characters than were there")

if __name__ == '__main__':
    for i in range(10):
        try:
            main()
        except:
            raise