package main

import (
    "fmt"
    "os"
    "strings"
    "bufio"
    "sort"
)

type TeleportValue struct {
    node int
    steps int
}

type TeleportKey struct {
    startNode int
    startOrder int
}

type CurrentT struct {
    totalSteps int
    key TeleportKey
}

func main() {
    args := os.Args[1:]

    file, err := os.Open(args[0])
    if err != nil {
        panic(err)
    }
    defer file.Close()

    s := bufio.NewScanner(file)
    var inputs []string;
    for s.Scan() {
        line := s.Text()
        if line != "" {
            inputs = append(inputs, line)
        }
    }
    order := inputs[0]

    // Generate string -> int mappings for better search performance
    nextId := 1
    mappings := make(map[string]int)
    backMappings := make(map[int]string)
    for i := 1; i < len(inputs); i++ {
        line := inputs[i]
        splitted := strings.Split(line, "=")
        node := strings.TrimSpace(splitted[0])
        mappings[node] = nextId
        backMappings[nextId] = node
        nextId++
    }

    // Create initial graph
    T := make(map[string][]string)
    var currents []CurrentT
    for i := 1; i < len(inputs); i++ {
        line := inputs[i]
        splitted := strings.Split(line, "=")
        node := strings.TrimSpace(splitted[0])
        leftPath := line[7:10]
        rightPath := line[12:15]

        T[node] = make([]string, 2)
        T[node][0] = leftPath
        T[node][1] = rightPath

        if node[2] == 'A' {
            currents = append(currents, CurrentT{0, TeleportKey{mappings[node], 0}})
        }
    }

    // Generate distances to the closest __Z node
    teleports := make(map[TeleportKey]TeleportValue)
    done := 0
    maxStep := len(T) * len(order) // avoid inifnite loops
    for node := range T {
        done++
        for i := 0; i < len(order); i++ {
            currentNode := node
            totalSteps := 0
            idx := i
            for true {
                // try to use precalculated results first
                v, find := teleports[TeleportKey{mappings[currentNode], idx}]
                if find {
                    currentNode = backMappings[v.node]
                    if totalSteps != -1 {
                        totalSteps += v.steps
                    } else {
                        totalSteps = -1
                    }
                    break
                }

                if idx == len(order) {
                    idx = 0
                }

                paths, _ := T[currentNode]
                if order[idx] == 'L' {
                    currentNode = paths[0]
                }
                if order[idx] == 'R' {
                    currentNode = paths[1]
                }
                idx++
                totalSteps++
                if currentNode[2] == 'Z' {
                    break
                }

                // if we exceed maxStep it means we are in the infinite loop
                if totalSteps > maxStep {
                    totalSteps = -1
                    currentNode = ""
                    break
                }
            }
            teleports[TeleportKey{mappings[node], i}] = TeleportValue{mappings[currentNode], totalSteps}
        }
    }

    // Travers graph
    nextPrintStep := 100 * 1000 * 1000 * 1000
    nextPrint := 0
    maxSteps := 1
    expGoods := len(currents)
    good := 0
    run := true
    for run {
        if currents[0].totalSteps > nextPrint {
            fmt.Println(nextPrint / nextPrintStep, currents)
            nextPrint += nextPrintStep
        }

        for i := range currents {
            if currents[i].totalSteps >= maxSteps {
                continue
            }
            v, _ := teleports[currents[i].key]
            currents[i].totalSteps += v.steps
            currents[i].key.startNode = v.node
            currents[i].key.startOrder = (v.steps + currents[i].key.startOrder) % len(order)

            if maxSteps < currents[i].totalSteps {
                maxSteps = currents[i].totalSteps
                good = 1
            } else if maxSteps == currents[i].totalSteps {
                good++
                if good == expGoods {
                    run = false
                    break
                }
            }
        }

    }

    fmt.Println(currents, maxSteps)
}