package main

import (
	"os"
	"fmt"
	"io"
)

type TransducerOutput interface {
	build(Store) string
}

type TransducerReplacementRune rune
func (replacement TransducerReplacementRune) build(store Store) string {
	return string(replacement)
}

type TransducerReplacementLoad rune
func (replacement TransducerReplacementLoad) build(store Store) string {
	return store[rune(replacement)]
}

type Store map[rune]string
func (store Store) clone() Store {
	newStore := make(Store)
	for key, val := range store {
		newStore[key] = val
	}
	return newStore
}
func (store Store) withValue(key rune, value string) Store {
	newStore := store.clone()
	newStore[key] = value
	return newStore
}

func compileTransducer(transducerAst SubexAST) SubexState {
	return transducerAst.compileWith(SubexNoneState{})
}

type SubexBranch struct {
	store Store
	state SubexState
	output string
}
func (pair SubexBranch) eat(char rune) []SubexBranch {
	states := pair.state.eat(pair.store, char)
	for i := range states {
		states[i].output = pair.output + states[i].output
	}
	return states
}
func (pair SubexBranch) accepting() []string {
	return pair.state.accepting(pair.store)
}

func equalStates(left SubexBranch, right SubexBranch) bool {
	// Only care about if they are the same pointer
	return left.state == right.state
}

func pruneStates(states []SubexBranch) (newStates []SubexBranch) {
	outer: for _, state := range states {
		for _, newState := range newStates {
			if equalStates(state, newState) {
				continue outer
			}
		}
		newStates = append(newStates, state)
	}
	return newStates
}

func runTransducer(transducer SubexState, input string) (output string, err bool) {
	states := []SubexBranch{{
		state: transducer,
		output: "",
		store: make(Store),
	}}
	for _, char := range input {
		var newStates []SubexBranch
		for _, state := range states {
			newStates = append(newStates, state.eat(char)...)
		}
		states = pruneStates(newStates)
	}
	for _, state := range states {
		outputEnds := state.accepting()
		for _, outputEnd := range outputEnds {
			return state.output + outputEnd, false
		}
	}
	return "", true
}

func main() {
	if len(os.Args) != 2 {
		panic("Expected: program [subex]")
	}
	inputBytes, inputErr := io.ReadAll(os.Stdin)
	input := string(inputBytes)
	if inputErr != nil {
		fmt.Println("Error reading")
	}
	program := os.Args[1]
	ast := parse(program)
	transducer := compileTransducer(ast)
	output, err := runTransducer(transducer, input)
	if err {
		output = input
	}
	fmt.Print(output)
}