package de.startat.aoc2023

import java.math.BigInteger
import kotlin.math.sqrt

class Day8 {
    data class WastelandMap(val map : Map<String,Pair<String,String>>) {
        operator fun get(currentNode: String): Pair<String, String> = map[currentNode]!!

    }

    private val mapLineRegex = Regex("(\\w*) = \\((\\w*), (\\w*)\\)")
    data class Instructions(val instructions : List<String>) {
        private var currentInstruction = 0
        fun next() : String {
            val instruction = instructions[currentInstruction]
            currentInstruction += 1
            currentInstruction %= instructions.size
            return instruction
        }
    }
    data class NavigationTools(val map : WastelandMap, val instructions : Instructions)

    class Journey(private val navigationTools: NavigationTools, private val startingNode: String = "AAA", private val targetNode: String = "ZZZ"){
        var currentNode = startingNode
        var destinationReached = false
        var stepCounter = 0
        fun step(){
            if(destinationReached) return

            val nextInstruction = navigationTools.instructions.next()
            val nextDecision = navigationTools.map[currentNode]
            val nextNode = when(nextInstruction){
                "L" -> nextDecision.first
                "R" -> nextDecision.second
                else -> throw RuntimeException("We're lost")
            }
            //println("Taking a step $nextInstruction from $currentNode to $nextNode")
            currentNode = nextNode
            stepCounter++
            if(currentNode == targetNode){
                println("$stepCounter from $startingNode to $targetNode")
                destinationReached = true
            }
        }
    }

    fun star1(){
        val tools : NavigationTools = parse(day8input)
        val journey = Journey(tools)
        while(!journey.destinationReached){
            journey.step()
        }
        println("The journey took ${journey.stepCounter} steps")

    }

    fun star2(){
        //step1()
        /* Result of step1
        12169 from SLA to LQZ
        12169 from LQZ to LQZ
        13301 from AAA to ZZZ
        13301 from ZZZ to ZZZ
        14999 from XJA to PDZ
        14999 from PDZ to PDZ
        16697 from JNA to PBZ
        16697 from PBZ to PBZ
        17263 from PTA to SNZ
        17263 from SNZ to SNZ
        18961 from BGA to LCZ
        18961 from LCZ to LCZ
        suspicious :D
        */

        val pathLengths = listOf(
        BigInteger.valueOf(12169),
        BigInteger.valueOf(13301),
        BigInteger.valueOf(14999),
        BigInteger.valueOf(16697),
        BigInteger.valueOf(17263),
        BigInteger.valueOf(18961))

        pathLengths.map { p -> Pair(p,primeFactors(p)) }.forEach{(p,primes) -> println("$p $primes") }
        /*
        12169 [43, 283]
        13301 [47, 283]
        14999 [53, 283]
        16697 [59, 283]
        17263 [61, 283]
        18961 [67, 283]
         */

        val kgv =
            BigInteger.valueOf(43) * BigInteger.valueOf(47) * BigInteger.valueOf(53) * BigInteger.valueOf(59) * BigInteger.valueOf(
                61
            ) * BigInteger.valueOf(67) * BigInteger.valueOf(283)
        println(kgv)



    }


    val two = BigInteger.valueOf(2)
    private fun primeFactors(number: BigInteger): ArrayList<BigInteger> {

        // Array that contains all the prime factors of given number.
        val arr: ArrayList<BigInteger> = arrayListOf()
        var n = number

        // At first check for divisibility by 2. add it in arr till it is divisible
        while (n.mod(two) == BigInteger.ZERO) {
            arr.add(two)
            n /= two
        }

        val squareRoot = sqrt(n.toDouble()).toInt()

        // Run loop from 3 to square root of n. Check for divisibility by i. Add i in arr till it is divisible by i.
        for (i in 3L..squareRoot step 2) {
            val bi = BigInteger.valueOf(i)
            while (n.mod(bi) == BigInteger.ZERO) {
                arr.add(bi)
                n /= bi
            }
        }

        // If n is a prime number greater than 2.
        if (n > two) {
            arr.add(n)
        }

        return arr
    }


    private fun step1() {
        val baseTools: NavigationTools = parse(day8input)
        val allStartingNodes = baseTools.map.map.keys.filter { it.endsWith("A") }.toList()
        val allTargetNodes = baseTools.map.map.keys.filter { it.endsWith("Z") }

        var allJourneys = mutableListOf<Journey>()
        for (start in allStartingNodes) {
            for (target in allTargetNodes) {
                allJourneys.add(
                    Journey(
                        NavigationTools(baseTools.map.copy(), baseTools.instructions.copy()),
                        start,
                        target
                    )
                )
            }
        }

        for (start in allTargetNodes) {
            for (target in allTargetNodes) {
                allJourneys.add(
                    Journey(
                        NavigationTools(baseTools.map.copy(), baseTools.instructions.copy()),
                        start,
                        target
                    )
                )
            }
        }

        while (allJourneys.any { j -> !j.destinationReached }) {
            allJourneys.forEach { j -> j.step() }
            allJourneys = allJourneys.filter { !it.destinationReached }.toMutableList()
        }
    }

    private fun parse(input: String): NavigationTools {
        val instructions = Instructions(input.lines()[0].split("").filter { it.isNotEmpty() }.toList())
        val mapEntries =
        input.lines().asSequence().drop(2).map { l -> mapLineRegex.find(l) }
            .associateBy({ it!!.groupValues[1] }, { Pair(it!!.groupValues[2], it.groupValues[3]) })
        val wastelandMap = WastelandMap(mapEntries)
        return NavigationTools(wastelandMap, instructions)
    }

    val day8testInput1 = """
        RL

        AAA = (BBB, CCC)
        BBB = (DDD, EEE)
        CCC = (ZZZ, GGG)
        DDD = (DDD, DDD)
        EEE = (EEE, EEE)
        GGG = (GGG, GGG)
        ZZZ = (ZZZ, ZZZ)
    """.trimIndent()

    val day8testInput2 = """
        LLR

        AAA = (BBB, BBB)
        BBB = (AAA, ZZZ)
        ZZZ = (ZZZ, ZZZ)
    """.trimIndent()

    val day8testInput3 = """
        LR

        11A = (11B, XXX)
        11B = (XXX, 11Z)
        11Z = (11B, XXX)
        22A = (22B, XXX)
        22B = (22C, 22C)
        22C = (22Z, 22Z)
        22Z = (22B, 22B)
        XXX = (XXX, XXX)
    """.trimIndent()

    val day8input = """
        LRRLRRRLRRLLLRLLRRLRRLLRRRLRRLLRLRRRLRLRRLRLRRRLRLRLRRLLRLRLRRLRRRLRRRLRRRLRLRRLLLLRLLRLLRRLRRRLLLRLRRRLRLRRRLRLRRLRRRLRRRLRLRLLRRRLLRLLRLRLRLRLLRRLRRLRRRLRRLRLRLRLRLRRLRRRLLRRRLLRLLLRRRLLRRRLRRRLRRLRLRRLRLLRRLLRRLRLRLRRLRLRRLLRRRLLRRRLLRLRRRLRLRRRLRLRRRLRRRLRRLRRLRRLLRRRLRRRLLLRRRR

        RGT = (HDG, QJV)
        QDM = (GPB, SXG)
        DJN = (TQD, BQN)
        QGG = (GGS, PTC)
        FJP = (MPB, HFP)
        KNB = (QHC, XBQ)
        RGR = (LSQ, LJV)
        HDP = (RLT, LRK)
        DBQ = (KTM, MPJ)
        QSG = (QVF, QVF)
        JKR = (XTK, RQB)
        BJH = (VKC, SML)
        LRF = (NPJ, HKK)
        JRD = (BQX, LGK)
        HVD = (CJP, TLM)
        VCG = (JMS, RJB)
        PCT = (KJC, RCQ)
        DRK = (PTR, FSH)
        BJN = (GVD, XXN)
        CXL = (FMB, NKM)
        TVM = (TTX, RCG)
        PTP = (KQQ, XLR)
        CKX = (VKR, RDH)
        TCP = (TPX, BSB)
        KSC = (JFL, CHL)
        DTF = (BTQ, TTQ)
        GFQ = (HKK, NPJ)
        BKD = (CXB, JSB)
        DJB = (TMG, DDQ)
        CQV = (SSX, DFT)
        BPC = (KNR, CGF)
        KLT = (BMF, XQC)
        NLB = (DBD, VCL)
        HJS = (FXK, FLB)
        PSL = (PBC, XFX)
        LVL = (JFD, RJD)
        JMX = (CGG, RRL)
        TTQ = (XVC, RCT)
        NLG = (FXK, FLB)
        LCD = (JSB, CXB)
        HVR = (CRV, HHM)
        HGV = (VCG, JDT)
        LND = (TTL, QCH)
        CSX = (DHS, JLB)
        BRJ = (BCT, XFS)
        XVN = (RDH, VKR)
        HQB = (BVD, GPC)
        PGP = (CFB, HQL)
        NFB = (BDX, JDK)
        HJK = (VVX, HTP)
        KKB = (NSF, GPP)
        JDV = (XJG, FDR)
        VGC = (HFV, JMT)
        BBG = (GTF, KTP)
        HTB = (BTC, KKC)
        KPL = (MXJ, MBN)
        NHD = (GCT, TGP)
        DMP = (KRH, SPM)
        LRB = (GNP, GGB)
        BGA = (MPB, HFP)
        PBZ = (KXQ, CKP)
        BQF = (LJC, VGC)
        KKC = (DJB, MCS)
        RRL = (QCK, RKN)
        PDZ = (RGF, BHL)
        SLA = (BCD, VJK)
        XRC = (SKL, VBP)
        HHM = (HSJ, NTR)
        BNP = (GPP, NSF)
        GHM = (HLC, KQK)
        LMV = (VTS, NFQ)
        QKF = (JNG, THN)
        PCG = (HSQ, DMP)
        CKG = (XSX, RDF)
        RMV = (FQL, HJL)
        LPG = (RJD, JFD)
        HFJ = (VQX, LQZ)
        QRF = (BCR, VSV)
        JSR = (BJJ, DVJ)
        TKS = (KTP, GTF)
        JNG = (DJD, XLM)
        XDG = (JKR, MRR)
        PFB = (QLT, PBD)
        NTR = (HBV, NRX)
        NMN = (BDX, JDK)
        MGP = (QMT, VLG)
        PTA = (LSP, TXX)
        CRK = (CJP, TLM)
        NVL = (STQ, QFH)
        VCL = (XFD, MGN)
        LJM = (VJH, NXV)
        GCJ = (RFS, QLN)
        NSF = (TKV, LKQ)
        PQN = (QHC, XBQ)
        GHK = (FNT, LCX)
        SFK = (FQL, HJL)
        FNX = (VXK, BJN)
        SSX = (MGK, KRX)
        FSH = (FNB, QFL)
        XFS = (BCK, CKG)
        VLQ = (XJV, HLM)
        JLB = (MMR, HMQ)
        GXX = (HLN, SGX)
        PKX = (QKF, SHQ)
        VND = (CDN, VVH)
        HJG = (FXR, VDR)
        GGR = (QRF, JMB)
        BQG = (CRV, HHM)
        RFS = (BHN, MNL)
        CSK = (DCX, VXG)
        RSL = (XCG, JGV)
        KRH = (CKX, XVN)
        VBP = (NLF, TVM)
        AAA = (MQQ, VHH)
        BVX = (LPG, LVL)
        QCG = (JKJ, CDR)
        JMQ = (HLR, GGT)
        NLF = (RCG, TTX)
        CXB = (NLG, HJS)
        VXG = (SDN, FCJ)
        XFT = (GNP, GGB)
        SST = (GGS, PTC)
        NNK = (PTD, HPF)
        RKN = (XVF, MMX)
        TGP = (SSN, MRT)
        TSR = (SFK, RMV)
        GBL = (NKQ, KVH)
        NKJ = (CGM, TCP)
        KVH = (VTK, GKV)
        VBB = (DXX, JVB)
        KGC = (HMK, TFL)
        PNL = (QLT, PBD)
        TNG = (QSG, TPL)
        HCV = (KVR, PKK)
        RBB = (TKG, CQK)
        BJJ = (GCN, PLQ)
        JRF = (DHC, XCQ)
        FLJ = (CKP, KXQ)
        KVR = (DJS, NKJ)
        HGT = (KVX, LTP)
        MGN = (JDS, LNS)
        FRC = (QLM, FHJ)
        MBN = (TRQ, MRD)
        TMG = (CTD, SFH)
        TNT = (JDG, HGV)
        DXP = (SSX, DFT)
        VVD = (JXJ, PGP)
        CHL = (XSL, SNZ)
        CGS = (GFQ, LRF)
        BHL = (FNQ, HFD)
        XHF = (NHD, PQC)
        PMH = (CNS, SVM)
        VKR = (TBT, TLT)
        LLK = (TQD, BQN)
        LVJ = (PDD, LML)
        JPB = (PRK, VCV)
        HSJ = (HBV, NRX)
        VJH = (DTL, BRL)
        SNJ = (DXP, CQV)
        HQL = (KDL, QFN)
        XHM = (HVG, ZZZ)
        RDX = (KTM, MPJ)
        MQQ = (LSC, DGG)
        TMM = (GMQ, RTL)
        JKP = (LRF, GFQ)
        TKG = (BDN, BDN)
        FBJ = (HLR, GGT)
        PTD = (LMV, QBR)
        FMB = (DQT, RRH)
        TTX = (LVJ, FXX)
        BXL = (BTQ, TTQ)
        QMV = (GND, FGG)
        HFD = (TBQ, VVD)
        NFQ = (PMH, DMM)
        RTH = (TPG, VDP)
        VHH = (DGG, LSC)
        HLN = (SPP, SPP)
        XQD = (PNL, PFB)
        GVD = (BPC, JJG)
        XRN = (DHJ, LBD)
        GNP = (NRC, NRC)
        JLC = (JHB, DRK)
        LGK = (BSK, BRV)
        BSB = (MBM, XHF)
        PBJ = (FRC, RFH)
        DRH = (VMR, XVK)
        RDF = (BHV, NGM)
        MMR = (HGD, PBJ)
        RGF = (HFD, FNQ)
        HTR = (RCQ, KJC)
        NGM = (FJP, LCZ)
        PJF = (QKF, SHQ)
        BCK = (XSX, XSX)
        PBD = (SXM, HTT)
        VCV = (GRD, VVT)
        TFL = (CCX, HQB)
        THT = (NXX, TSR)
        JMS = (RCF, XRC)
        FKG = (XRN, PHG)
        TBQ = (PGP, JXJ)
        SML = (TCH, DPF)
        RJB = (RCF, XRC)
        KJC = (LND, JNR)
        HPT = (DLM, MVH)
        NKM = (DQT, RRH)
        JSJ = (QFH, STQ)
        KJJ = (XXT, DBC)
        FGG = (HPT, GMM)
        RFH = (QLM, FHJ)
        TLM = (DKN, QGH)
        MJV = (QSG, TPL)
        DHG = (RGT, CVS)
        BVB = (QLJ, SNR)
        RMH = (JKR, MRR)
        XFX = (SNJ, QBD)
        LNS = (SFQ, GGR)
        QJV = (LRB, XFT)
        BHV = (FJP, FJP)
        JMT = (BJM, NPC)
        BDN = (JFL, JFL)
        CHC = (CXL, SXC)
        VBN = (VBB, CFM)
        SFQ = (QRF, JMB)
        XXN = (JJG, BPC)
        MCS = (TMG, DDQ)
        CFV = (DHG, NKS)
        FXK = (JSR, GLR)
        JMB = (VSV, BCR)
        VVT = (LST, GCJ)
        VRL = (DJN, LLK)
        XLB = (FGJ, PGB)
        JVC = (XXT, DBC)
        VQX = (BCD, VJK)
        DVJ = (GCN, PLQ)
        BTQ = (RCT, XVC)
        LCX = (JHK, KPL)
        FSD = (NNC, XLX)
        TSQ = (FKM, HFJ)
        HGD = (RFH, FRC)
        HJL = (JDV, LNV)
        FSB = (DBD, VCL)
        DCX = (SDN, FCJ)
        BHH = (JPK, GVQ)
        JHB = (PTR, FSH)
        THP = (SXC, CXL)
        LRK = (QCT, FPT)
        PTC = (LMF, DLF)
        DHS = (HMQ, MMR)
        GDK = (SNR, QLJ)
        CNJ = (JKJ, CDR)
        SBM = (BCT, XFS)
        GJP = (RJK, DDX)
        DFT = (KRX, MGK)
        XBQ = (BNP, KKB)
        FGJ = (VRL, CKV)
        QVF = (XTM, XTM)
        VJK = (BFB, CKT)
        VJX = (BKD, LCD)
        KQK = (GBL, HPK)
        KKX = (BDC, SKC)
        CRV = (HSJ, NTR)
        JNR = (QCH, TTL)
        HTG = (NQK, GJP)
        QLN = (MNL, BHN)
        GMB = (VVX, HTP)
        JDG = (JDT, VCG)
        QLT = (HTT, SXM)
        CLK = (VJB, SRH)
        GSX = (XKX, RSL)
        MQX = (RTH, LPL)
        ZZZ = (VHH, MQQ)
        PKK = (DJS, NKJ)
        MJT = (MQX, HTF)
        GLT = (TCD, HXV)
        PQX = (TGQ, JBF)
        VSX = (LTP, KVX)
        FSV = (FKG, NLC)
        FKR = (CQD, JPR)
        CKT = (RDX, DBQ)
        JFD = (TKS, BBG)
        CNM = (TBH, XRF)
        PBC = (SNJ, QBD)
        MRT = (QCG, CNJ)
        RCQ = (JNR, LND)
        JJG = (KNR, CGF)
        CFP = (JVT, GSX)
        BTG = (SBM, BRJ)
        BJM = (CRK, HVD)
        XVK = (CDS, BQF)
        BCT = (BCK, CKG)
        LST = (RFS, QLN)
        DNM = (VMR, XVK)
        GPB = (GNX, DJV)
        FDR = (FTG, LFQ)
        LCZ = (HFP, MPB)
        XJV = (FCP, JHV)
        HQC = (TRG, SCP)
        RMD = (QMV, NNH)
        SRH = (FLL, QKV)
        QBD = (CQV, DXP)
        RRH = (NCB, TSQ)
        XVF = (NFB, NMN)
        QMT = (GLT, NTS)
        GBX = (TKG, CQK)
        MFP = (TLH, QXD)
        XKG = (MHN, NLR)
        HQH = (HPF, PTD)
        LLR = (CNR, CRF)
        LSP = (SVQ, VJX)
        HSH = (LRK, RLT)
        TTL = (FKR, QMF)
        CFB = (KDL, QFN)
        SXG = (GNX, DJV)
        LTP = (KJJ, JVC)
        HSQ = (SPM, KRH)
        SHG = (DRH, DNM)
        DHJ = (QXR, GHK)
        GGK = (PRK, VCV)
        TRG = (PJN, CFV)
        TTF = (LJV, LSQ)
        VVH = (HSH, HDP)
        QXR = (FNT, LCX)
        DTL = (FSV, VQV)
        KVX = (JVC, KJJ)
        HLR = (BTG, MKN)
        XCG = (QTJ, HTQ)
        LML = (JMQ, FBJ)
        FMS = (XTM, VXJ)
        CTD = (JHQ, XLB)
        TCD = (CSK, GLS)
        MRR = (RQB, XTK)
        SSN = (CNJ, QCG)
        VLG = (NTS, GLT)
        JDT = (JMS, RJB)
        TPJ = (XFX, PBC)
        PDD = (FBJ, JMQ)
        QLJ = (NVL, JSJ)
        TVX = (JPB, GGK)
        QCT = (GBX, RBB)
        GMM = (DLM, MVH)
        RLT = (QCT, FPT)
        PFH = (HTG, DNF)
        DQN = (XCQ, DHC)
        XQC = (QJQ, JLC)
        QCH = (FKR, QMF)
        GMQ = (KPJ, RTF)
        HVJ = (QMV, NNH)
        VDP = (TVX, VFB)
        NXV = (DTL, BRL)
        JHK = (MXJ, MBN)
        JPK = (GQN, MFP)
        SSH = (KQK, HLC)
        FNB = (GPS, LLR)
        HTP = (SPG, CSX)
        HHN = (DNF, HTG)
        QJQ = (JHB, DRK)
        PFC = (KRJ, JLV)
        HFP = (JRD, MMT)
        HGC = (QCJ, CXG)
        KLG = (BVX, QSM)
        LHG = (HLM, XJV)
        CGG = (QCK, RKN)
        XVC = (CGS, JKP)
        FCJ = (TMM, MBL)
        KLC = (CDN, VVH)
        CRF = (LVG, FNX)
        PBP = (GSX, JVT)
        GLS = (DCX, VXG)
        DJD = (QGG, SST)
        BJV = (DMP, HSQ)
        MNL = (JSG, LNC)
        DNF = (NQK, GJP)
        NLR = (SSH, GHM)
        HSP = (JBF, TGQ)
        NRX = (DTX, CJK)
        VVX = (CSX, SPG)
        LSC = (DCL, QBB)
        VXJ = (FLJ, PBZ)
        CDR = (NXN, NMT)
        SGM = (NXV, VJH)
        XSX = (BHV, BHV)
        MGK = (FXG, XTG)
        VPC = (SKC, BDC)
        HBV = (CJK, DTX)
        RQB = (PCT, HTR)
        FXR = (HKP, LVP)
        BRL = (FSV, VQV)
        VXK = (GVD, XXN)
        SDN = (MBL, TMM)
        FCP = (HXD, SHG)
        XTG = (KLT, SPX)
        LBD = (GHK, QXR)
        JHQ = (FGJ, PGB)
        XXT = (KNB, PQN)
        VKC = (TCH, DPF)
        GQN = (QXD, TLH)
        HLM = (JHV, FCP)
        JDK = (TTF, RGR)
        VTS = (PMH, DMM)
        VMR = (CDS, BQF)
        XJA = (BHL, RGF)
        MMS = (NLR, MHN)
        DPF = (PQX, HSP)
        NNH = (FGG, GND)
        JSB = (NLG, HJS)
        XLR = (GMB, HJK)
        RCF = (VBP, SKL)
        JPD = (HTF, MQX)
        CJP = (DKN, QGH)
        BLC = (HGV, JDG)
        FTG = (PSL, TPJ)
        JDS = (SFQ, GGR)
        FQL = (JDV, LNV)
        JBF = (CHC, THP)
        HVG = (MQQ, VHH)
        LKQ = (NLX, HHX)
        KRX = (FXG, XTG)
        JNA = (CKP, KXQ)
        JPR = (CGD, BJH)
        CJK = (MSQ, HCV)
        QSM = (LVL, LPG)
        BQN = (PCG, BJV)
        SFH = (XLB, JHQ)
        XLD = (QNN, LVC)
        GTF = (HTB, RQV)
        BMF = (QJQ, JLC)
        THN = (XLM, DJD)
        VPB = (FXR, VDR)
        RQX = (XQD, JDL)
        LNV = (XJG, FDR)
        NXN = (DSS, KMF)
        QTJ = (DKR, KLG)
        VSV = (KHH, FSD)
        DBD = (MGN, XFD)
        DHC = (PHH, HQC)
        QGH = (VBN, DPJ)
        NTS = (TCD, HXV)
        BSK = (BQG, HVR)
        MRD = (VPB, HJG)
        BQX = (BSK, BRV)
        BRV = (BQG, HVR)
        SVM = (PKX, PJF)
        KRJ = (NMC, TBX)
        GTH = (HVG, HVG)
        SCP = (PJN, CFV)
        CGF = (VFD, GXX)
        SHQ = (THN, JNG)
        JVT = (XKX, RSL)
        RJK = (RVD, CLK)
        MKN = (SBM, BRJ)
        JHV = (HXD, SHG)
        TLT = (JRF, DQN)
        QBR = (NFQ, VTS)
        CNR = (FNX, LVG)
        LVG = (BJN, VXK)
        FCQ = (BHL, RGF)
        JXJ = (CFB, HQL)
        DJV = (BXL, DTF)
        DTX = (HCV, MSQ)
        JLV = (NMC, TBX)
        STQ = (RMH, XDG)
        NQK = (DDX, RJK)
        KTP = (RQV, HTB)
        RLP = (JDL, XQD)
        TQD = (PCG, BJV)
        GGT = (MKN, BTG)
        VJB = (FLL, QKV)
        JVB = (MJT, JPD)
        VQV = (FKG, NLC)
        FXG = (KLT, SPX)
        XFD = (LNS, JDS)
        NKS = (CVS, RGT)
        QFL = (GPS, LLR)
        CDN = (HSH, HDP)
        RTL = (RTF, KPJ)
        CCX = (GPC, BVD)
        CXG = (THT, VVN)
        GRC = (CGG, RRL)
        MXJ = (TRQ, MRD)
        SXM = (HQH, NNK)
        LJV = (SMP, VRJ)
        RJD = (TKS, BBG)
        HMQ = (PBJ, HGD)
        MSQ = (KVR, PKK)
        GPS = (CNR, CRF)
        FNT = (KPL, JHK)
        HDG = (LRB, XFT)
        LFQ = (PSL, TPJ)
        VFD = (HLN, SGX)
        SKC = (CFP, PBP)
        TKV = (HHX, NLX)
        GPP = (TKV, LKQ)
        JSG = (PFH, HHN)
        BCD = (CKT, BFB)
        MPJ = (HVJ, RMD)
        GCT = (MRT, SSN)
        XTM = (FLJ, FLJ)
        DKN = (DPJ, VBN)
        SVN = (VLG, QMT)
        LQZ = (VJK, BCD)
        PHS = (GPB, SXG)
        XCQ = (HQC, PHH)
        QNN = (FCQ, FCQ)
        DMM = (CNS, SVM)
        DBC = (PQN, KNB)
        JFL = (XSL, XSL)
        MBL = (RTL, GMQ)
        VTK = (MGP, SVN)
        SKL = (TVM, NLF)
        HXD = (DRH, DNM)
        GNX = (DTF, BXL)
        XLM = (SST, QGG)
        QMF = (CQD, JPR)
        HMK = (HQB, CCX)
        MMT = (BQX, LGK)
        PJN = (DHG, NKS)
        DGG = (DCL, QBB)
        SPX = (XQC, BMF)
        MHN = (SSH, GHM)
        RDH = (TLT, TBT)
        NMC = (KKX, VPC)
        GKV = (SVN, MGP)
        XSL = (LSP, TXX)
        TGQ = (THP, CHC)
        TRQ = (HJG, VPB)
        VHK = (KRJ, JLV)
        TPX = (MBM, XHF)
        QXD = (QDM, PHS)
        VRJ = (GDK, BVB)
        KXQ = (RLP, RQX)
        CNS = (PKX, PJF)
        TPG = (TVX, VFB)
        PTR = (QFL, FNB)
        QHC = (KKB, BNP)
        CDS = (VGC, LJC)
        BTC = (MCS, DJB)
        NLC = (PHG, XRN)
        BDC = (CFP, PBP)
        FPT = (GBX, RBB)
        CQD = (BJH, CGD)
        XKX = (JGV, XCG)
        TXX = (VJX, SVQ)
        SPP = (GTH, GTH)
        KTM = (HVJ, RMD)
        JGV = (HTQ, QTJ)
        HKP = (KLC, VND)
        GLR = (DVJ, BJJ)
        LMF = (LHG, VLQ)
        CLG = (TFL, HMK)
        KHH = (NNC, XLX)
        HTQ = (KLG, DKR)
        QFN = (CNM, TCT)
        FLL = (TNG, MJV)
        HFV = (NPC, BJM)
        NPC = (HVD, CRK)
        HKK = (KGC, CLG)
        XRF = (PFC, VHK)
        GGS = (DLF, LMF)
        LVC = (FCQ, PDZ)
        DXX = (MJT, JPD)
        DCL = (HGT, VSX)
        LNC = (HHN, PFH)
        TBT = (JRF, DQN)
        DKR = (QSM, BVX)
        KNL = (QCJ, CXG)
        TLH = (PHS, QDM)
        NMT = (DSS, KMF)
        HLC = (GBL, HPK)
        BDX = (TTF, RGR)
        HXV = (GLS, CSK)
        TBH = (VHK, PFC)
        QBB = (HGT, VSX)
        TCH = (PQX, HSP)
        QFH = (XDG, RMH)
        GND = (HPT, GMM)
        CVS = (QJV, HDG)
        FNQ = (VVD, TBQ)
        NCB = (FKM, FKM)
        FHJ = (MMS, XKG)
        VFB = (GGK, JPB)
        RQV = (KKC, BTC)
        NLX = (KNL, HGC)
        TCT = (XRF, TBH)
        GGB = (NRC, XLD)
        JKJ = (NXN, NMT)
        SPG = (DHS, JLB)
        LVP = (VND, KLC)
        NPJ = (KGC, CLG)
        RVD = (SRH, VJB)
        HTT = (NNK, HQH)
        PQC = (TGP, GCT)
        MPB = (MMT, JRD)
        BCR = (FSD, KHH)
        BHN = (LNC, JSG)
        SMP = (BVB, GDK)
        GPC = (NLB, FSB)
        NMD = (GTH, XHM)
        CGD = (SML, VKC)
        CKP = (RQX, RLP)
        DQT = (NCB, NCB)
        KDL = (CNM, TCT)
        CQK = (BDN, KSC)
        NXX = (SFK, RMV)
        RTF = (LJM, SGM)
        KQQ = (HJK, GMB)
        KMF = (BVK, BHH)
        HPK = (KVH, NKQ)
        PLQ = (MLH, PTP)
        RCG = (LVJ, FXX)
        HPF = (LMV, QBR)
        TBX = (VPC, KKX)
        NKQ = (VTK, GKV)
        PRK = (GRD, VVT)
        TPL = (QVF, FMS)
        CFM = (DXX, JVB)
        SGX = (SPP, NMD)
        MLH = (KQQ, XLR)
        NNC = (TNT, BLC)
        XLX = (TNT, BLC)
        MBM = (NHD, PQC)
        PHH = (TRG, SCP)
        QKV = (TNG, MJV)
        XJG = (FTG, LFQ)
        QCK = (XVF, MMX)
        SVQ = (LCD, BKD)
        SXC = (FMB, NKM)
        RCT = (CGS, JKP)
        KNR = (VFD, GXX)
        FKM = (VQX, VQX)
        CKV = (DJN, LLK)
        DDX = (CLK, RVD)
        GCN = (PTP, MLH)
        BFB = (DBQ, RDX)
        SNZ = (TXX, LSP)
        MVH = (JMX, GRC)
        HHX = (HGC, KNL)
        GRD = (GCJ, LST)
        SPM = (CKX, XVN)
        LPL = (VDP, TPG)
        CGM = (BSB, TPX)
        FXX = (LML, PDD)
        PGB = (CKV, VRL)
        MMX = (NMN, NFB)
        DJS = (TCP, CGM)
        HTF = (LPL, RTH)
        DSS = (BVK, BHH)
        KPJ = (SGM, LJM)
        DLM = (GRC, JMX)
        LSQ = (SMP, VRJ)
        SNR = (NVL, JSJ)
        DPJ = (CFM, VBB)
        DDQ = (SFH, CTD)
        VVN = (NXX, TSR)
        QLM = (XKG, MMS)
        QCJ = (VVN, THT)
        JDL = (PFB, PNL)
        DLF = (LHG, VLQ)
        LJC = (JMT, HFV)
        GVQ = (GQN, MFP)
        XTK = (HTR, PCT)
        NRC = (QNN, QNN)
        PHG = (DHJ, LBD)
        BVD = (NLB, FSB)
        VDR = (HKP, LVP)
        BVK = (GVQ, JPK)
        FLB = (JSR, GLR)
    """.trimIndent()
}
package de.startat.aoc2023

import java.math.BigInteger
import kotlin.math.sqrt

class Day8 {
    data class WastelandMap(val map : Map<String,Pair<String,String>>) {
        operator fun get(currentNode: String): Pair<String, String> = map[currentNode]!!

    }

    private val mapLineRegex = Regex("(\\w*) = \\((\\w*), (\\w*)\\)")
    data class Instructions(val instructions : List<String>) {
        private var currentInstruction = 0
        fun next() : String {
            val instruction = instructions[currentInstruction]
            currentInstruction += 1
            currentInstruction %= instructions.size
            return instruction
        }
    }
    data class NavigationTools(val map : WastelandMap, val instructions : Instructions)

    class Journey(private val navigationTools: NavigationTools, private val startingNode: String = "AAA", private val targetNode: String = "ZZZ"){
        var currentNode = startingNode
        var destinationReached = false
        var stepCounter = 0
        fun step(){
            if(destinationReached) return

            val nextInstruction = navigationTools.instructions.next()
            val nextDecision = navigationTools.map[currentNode]
            val nextNode = when(nextInstruction){
                "L" -> nextDecision.first
                "R" -> nextDecision.second
                else -> throw RuntimeException("We're lost")
            }
            //println("Taking a step $nextInstruction from $currentNode to $nextNode")
            currentNode = nextNode
            stepCounter++
            if(currentNode == targetNode){
                println("$stepCounter from $startingNode to $targetNode")
                destinationReached = true
            }
        }
    }

    fun star1(){
        val tools : NavigationTools = parse(day8input)
        val journey = Journey(tools)
        while(!journey.destinationReached){
            journey.step()
        }
        println("The journey took ${journey.stepCounter} steps")

    }

    fun star2(){
        //step1()
        /* Result of step1
        12169 from SLA to LQZ
        12169 from LQZ to LQZ
        13301 from AAA to ZZZ
        13301 from ZZZ to ZZZ
        14999 from XJA to PDZ
        14999 from PDZ to PDZ
        16697 from JNA to PBZ
        16697 from PBZ to PBZ
        17263 from PTA to SNZ
        17263 from SNZ to SNZ
        18961 from BGA to LCZ
        18961 from LCZ to LCZ
        suspicious :D
        */

        val pathLengths = listOf(
        BigInteger.valueOf(12169),
        BigInteger.valueOf(13301),
        BigInteger.valueOf(14999),
        BigInteger.valueOf(16697),
        BigInteger.valueOf(17263),
        BigInteger.valueOf(18961))

        pathLengths.map { p -> Pair(p,primeFactors(p)) }.forEach{(p,primes) -> println("$p $primes") }
        /*
        12169 [43, 283]
        13301 [47, 283]
        14999 [53, 283]
        16697 [59, 283]
        17263 [61, 283]
        18961 [67, 283]
         */

        val kgv =
            BigInteger.valueOf(43) * BigInteger.valueOf(47) * BigInteger.valueOf(53) * BigInteger.valueOf(59) * BigInteger.valueOf(
                61
            ) * BigInteger.valueOf(67) * BigInteger.valueOf(283)
        println(kgv)



    }


    val two = BigInteger.valueOf(2)
    private fun primeFactors(number: BigInteger): ArrayList<BigInteger> {

        // Array that contains all the prime factors of given number.
        val arr: ArrayList<BigInteger> = arrayListOf()
        var n = number

        // At first check for divisibility by 2. add it in arr till it is divisible
        while (n.mod(two) == BigInteger.ZERO) {
            arr.add(two)
            n /= two
        }

        val squareRoot = sqrt(n.toDouble()).toInt()

        // Run loop from 3 to square root of n. Check for divisibility by i. Add i in arr till it is divisible by i.
        for (i in 3L..squareRoot step 2) {
            val bi = BigInteger.valueOf(i)
            while (n.mod(bi) == BigInteger.ZERO) {
                arr.add(bi)
                n /= bi
            }
        }

        // If n is a prime number greater than 2.
        if (n > two) {
            arr.add(n)
        }

        return arr
    }


    private fun step1() {
        val baseTools: NavigationTools = parse(day8input)
        val allStartingNodes = baseTools.map.map.keys.filter { it.endsWith("A") }.toList()
        val allTargetNodes = baseTools.map.map.keys.filter { it.endsWith("Z") }

        var allJourneys = mutableListOf<Journey>()
        for (start in allStartingNodes) {
            for (target in allTargetNodes) {
                allJourneys.add(
                    Journey(
                        NavigationTools(baseTools.map.copy(), baseTools.instructions.copy()),
                        start,
                        target
                    )
                )
            }
        }

        for (start in allTargetNodes) {
            for (target in allTargetNodes) {
                allJourneys.add(
                    Journey(
                        NavigationTools(baseTools.map.copy(), baseTools.instructions.copy()),
                        start,
                        target
                    )
                )
            }
        }

        while (allJourneys.any { j -> !j.destinationReached }) {
            allJourneys.forEach { j -> j.step() }
            allJourneys = allJourneys.filter { !it.destinationReached }.toMutableList()
        }
    }

    private fun parse(input: String): NavigationTools {
        val instructions = Instructions(input.lines()[0].split("").filter { it.isNotEmpty() }.toList())
        val mapEntries =
        input.lines().asSequence().drop(2).map { l -> mapLineRegex.find(l) }
            .associateBy({ it!!.groupValues[1] }, { Pair(it!!.groupValues[2], it.groupValues[3]) })
        val wastelandMap = WastelandMap(mapEntries)
        return NavigationTools(wastelandMap, instructions)
    }

    val day8testInput1 = """
        RL

        AAA = (BBB, CCC)
        BBB = (DDD, EEE)
        CCC = (ZZZ, GGG)
        DDD = (DDD, DDD)
        EEE = (EEE, EEE)
        GGG = (GGG, GGG)
        ZZZ = (ZZZ, ZZZ)
    """.trimIndent()

    val day8testInput2 = """
        LLR

        AAA = (BBB, BBB)
        BBB = (AAA, ZZZ)
        ZZZ = (ZZZ, ZZZ)
    """.trimIndent()

    val day8testInput3 = """
        LR

        11A = (11B, XXX)
        11B = (XXX, 11Z)
        11Z = (11B, XXX)
        22A = (22B, XXX)
        22B = (22C, 22C)
        22C = (22Z, 22Z)
        22Z = (22B, 22B)
        XXX = (XXX, XXX)
    """.trimIndent()

    val day8input = """
        LRRLRRRLRRLLLRLLRRLRRLLRRRLRRLLRLRRRLRLRRLRLRRRLRLRLRRLLRLRLRRLRRRLRRRLRRRLRLRRLLLLRLLRLLRRLRRRLLLRLRRRLRLRRRLRLRRLRRRLRRRLRLRLLRRRLLRLLRLRLRLRLLRRLRRLRRRLRRLRLRLRLRLRRLRRRLLRRRLLRLLLRRRLLRRRLRRRLRRLRLRRLRLLRRLLRRLRLRLRRLRLRRLLRRRLLRRRLLRLRRRLRLRRRLRLRRRLRRRLRRLRRLRRLLRRRLRRRLLLRRRR

        RGT = (HDG, QJV)
        QDM = (GPB, SXG)
        DJN = (TQD, BQN)
        QGG = (GGS, PTC)
        FJP = (MPB, HFP)
        KNB = (QHC, XBQ)
        RGR = (LSQ, LJV)
        HDP = (RLT, LRK)
        DBQ = (KTM, MPJ)
        QSG = (QVF, QVF)
        JKR = (XTK, RQB)
        BJH = (VKC, SML)
        LRF = (NPJ, HKK)
        JRD = (BQX, LGK)
        HVD = (CJP, TLM)
        VCG = (JMS, RJB)
        PCT = (KJC, RCQ)
        DRK = (PTR, FSH)
        BJN = (GVD, XXN)
        CXL = (FMB, NKM)
        TVM = (TTX, RCG)
        PTP = (KQQ, XLR)
        CKX = (VKR, RDH)
        TCP = (TPX, BSB)
        KSC = (JFL, CHL)
        DTF = (BTQ, TTQ)
        GFQ = (HKK, NPJ)
        BKD = (CXB, JSB)
        DJB = (TMG, DDQ)
        CQV = (SSX, DFT)
        BPC = (KNR, CGF)
        KLT = (BMF, XQC)
        NLB = (DBD, VCL)
        HJS = (FXK, FLB)
        PSL = (PBC, XFX)
        LVL = (JFD, RJD)
        JMX = (CGG, RRL)
        TTQ = (XVC, RCT)
        NLG = (FXK, FLB)
        LCD = (JSB, CXB)
        HVR = (CRV, HHM)
        HGV = (VCG, JDT)
        LND = (TTL, QCH)
        CSX = (DHS, JLB)
        BRJ = (BCT, XFS)
        XVN = (RDH, VKR)
        HQB = (BVD, GPC)
        PGP = (CFB, HQL)
        NFB = (BDX, JDK)
        HJK = (VVX, HTP)
        KKB = (NSF, GPP)
        JDV = (XJG, FDR)
        VGC = (HFV, JMT)
        BBG = (GTF, KTP)
        HTB = (BTC, KKC)
        KPL = (MXJ, MBN)
        NHD = (GCT, TGP)
        DMP = (KRH, SPM)
        LRB = (GNP, GGB)
        BGA = (MPB, HFP)
        PBZ = (KXQ, CKP)
        BQF = (LJC, VGC)
        KKC = (DJB, MCS)
        RRL = (QCK, RKN)
        PDZ = (RGF, BHL)
        SLA = (BCD, VJK)
        XRC = (SKL, VBP)
        HHM = (HSJ, NTR)
        BNP = (GPP, NSF)
        GHM = (HLC, KQK)
        LMV = (VTS, NFQ)
        QKF = (JNG, THN)
        PCG = (HSQ, DMP)
        CKG = (XSX, RDF)
        RMV = (FQL, HJL)
        LPG = (RJD, JFD)
        HFJ = (VQX, LQZ)
        QRF = (BCR, VSV)
        JSR = (BJJ, DVJ)
        TKS = (KTP, GTF)
        JNG = (DJD, XLM)
        XDG = (JKR, MRR)
        PFB = (QLT, PBD)
        NTR = (HBV, NRX)
        NMN = (BDX, JDK)
        MGP = (QMT, VLG)
        PTA = (LSP, TXX)
        CRK = (CJP, TLM)
        NVL = (STQ, QFH)
        VCL = (XFD, MGN)
        LJM = (VJH, NXV)
        GCJ = (RFS, QLN)
        NSF = (TKV, LKQ)
        PQN = (QHC, XBQ)
        GHK = (FNT, LCX)
        SFK = (FQL, HJL)
        FNX = (VXK, BJN)
        SSX = (MGK, KRX)
        FSH = (FNB, QFL)
        XFS = (BCK, CKG)
        VLQ = (XJV, HLM)
        JLB = (MMR, HMQ)
        GXX = (HLN, SGX)
        PKX = (QKF, SHQ)
        VND = (CDN, VVH)
        HJG = (FXR, VDR)
        GGR = (QRF, JMB)
        BQG = (CRV, HHM)
        RFS = (BHN, MNL)
        CSK = (DCX, VXG)
        RSL = (XCG, JGV)
        KRH = (CKX, XVN)
        VBP = (NLF, TVM)
        AAA = (MQQ, VHH)
        BVX = (LPG, LVL)
        QCG = (JKJ, CDR)
        JMQ = (HLR, GGT)
        NLF = (RCG, TTX)
        CXB = (NLG, HJS)
        VXG = (SDN, FCJ)
        XFT = (GNP, GGB)
        SST = (GGS, PTC)
        NNK = (PTD, HPF)
        RKN = (XVF, MMX)
        TGP = (SSN, MRT)
        TSR = (SFK, RMV)
        GBL = (NKQ, KVH)
        NKJ = (CGM, TCP)
        KVH = (VTK, GKV)
        VBB = (DXX, JVB)
        KGC = (HMK, TFL)
        PNL = (QLT, PBD)
        TNG = (QSG, TPL)
        HCV = (KVR, PKK)
        RBB = (TKG, CQK)
        BJJ = (GCN, PLQ)
        JRF = (DHC, XCQ)
        FLJ = (CKP, KXQ)
        KVR = (DJS, NKJ)
        HGT = (KVX, LTP)
        MGN = (JDS, LNS)
        FRC = (QLM, FHJ)
        MBN = (TRQ, MRD)
        TMG = (CTD, SFH)
        TNT = (JDG, HGV)
        DXP = (SSX, DFT)
        VVD = (JXJ, PGP)
        CHL = (XSL, SNZ)
        CGS = (GFQ, LRF)
        BHL = (FNQ, HFD)
        XHF = (NHD, PQC)
        PMH = (CNS, SVM)
        VKR = (TBT, TLT)
        LLK = (TQD, BQN)
        LVJ = (PDD, LML)
        JPB = (PRK, VCV)
        HSJ = (HBV, NRX)
        VJH = (DTL, BRL)
        SNJ = (DXP, CQV)
        HQL = (KDL, QFN)
        XHM = (HVG, ZZZ)
        RDX = (KTM, MPJ)
        MQQ = (LSC, DGG)
        TMM = (GMQ, RTL)
        JKP = (LRF, GFQ)
        TKG = (BDN, BDN)
        FBJ = (HLR, GGT)
        PTD = (LMV, QBR)
        FMB = (DQT, RRH)
        TTX = (LVJ, FXX)
        BXL = (BTQ, TTQ)
        QMV = (GND, FGG)
        HFD = (TBQ, VVD)
        NFQ = (PMH, DMM)
        RTH = (TPG, VDP)
        VHH = (DGG, LSC)
        HLN = (SPP, SPP)
        XQD = (PNL, PFB)
        GVD = (BPC, JJG)
        XRN = (DHJ, LBD)
        GNP = (NRC, NRC)
        JLC = (JHB, DRK)
        LGK = (BSK, BRV)
        BSB = (MBM, XHF)
        PBJ = (FRC, RFH)
        DRH = (VMR, XVK)
        RDF = (BHV, NGM)
        MMR = (HGD, PBJ)
        RGF = (HFD, FNQ)
        HTR = (RCQ, KJC)
        NGM = (FJP, LCZ)
        PJF = (QKF, SHQ)
        BCK = (XSX, XSX)
        PBD = (SXM, HTT)
        VCV = (GRD, VVT)
        TFL = (CCX, HQB)
        THT = (NXX, TSR)
        JMS = (RCF, XRC)
        FKG = (XRN, PHG)
        TBQ = (PGP, JXJ)
        SML = (TCH, DPF)
        RJB = (RCF, XRC)
        KJC = (LND, JNR)
        HPT = (DLM, MVH)
        NKM = (DQT, RRH)
        JSJ = (QFH, STQ)
        KJJ = (XXT, DBC)
        FGG = (HPT, GMM)
        RFH = (QLM, FHJ)
        TLM = (DKN, QGH)
        MJV = (QSG, TPL)
        DHG = (RGT, CVS)
        BVB = (QLJ, SNR)
        RMH = (JKR, MRR)
        XFX = (SNJ, QBD)
        LNS = (SFQ, GGR)
        QJV = (LRB, XFT)
        BHV = (FJP, FJP)
        JMT = (BJM, NPC)
        BDN = (JFL, JFL)
        CHC = (CXL, SXC)
        VBN = (VBB, CFM)
        SFQ = (QRF, JMB)
        XXN = (JJG, BPC)
        MCS = (TMG, DDQ)
        CFV = (DHG, NKS)
        FXK = (JSR, GLR)
        JMB = (VSV, BCR)
        VVT = (LST, GCJ)
        VRL = (DJN, LLK)
        XLB = (FGJ, PGB)
        JVC = (XXT, DBC)
        VQX = (BCD, VJK)
        DVJ = (GCN, PLQ)
        BTQ = (RCT, XVC)
        LCX = (JHK, KPL)
        FSD = (NNC, XLX)
        TSQ = (FKM, HFJ)
        HGD = (RFH, FRC)
        HJL = (JDV, LNV)
        FSB = (DBD, VCL)
        DCX = (SDN, FCJ)
        BHH = (JPK, GVQ)
        JHB = (PTR, FSH)
        THP = (SXC, CXL)
        LRK = (QCT, FPT)
        PTC = (LMF, DLF)
        DHS = (HMQ, MMR)
        GDK = (SNR, QLJ)
        CNJ = (JKJ, CDR)
        SBM = (BCT, XFS)
        GJP = (RJK, DDX)
        DFT = (KRX, MGK)
        XBQ = (BNP, KKB)
        FGJ = (VRL, CKV)
        QVF = (XTM, XTM)
        VJK = (BFB, CKT)
        VJX = (BKD, LCD)
        KQK = (GBL, HPK)
        KKX = (BDC, SKC)
        CRV = (HSJ, NTR)
        JNR = (QCH, TTL)
        HTG = (NQK, GJP)
        QLN = (MNL, BHN)
        GMB = (VVX, HTP)
        JDG = (JDT, VCG)
        QLT = (HTT, SXM)
        CLK = (VJB, SRH)
        GSX = (XKX, RSL)
        MQX = (RTH, LPL)
        ZZZ = (VHH, MQQ)
        PKK = (DJS, NKJ)
        MJT = (MQX, HTF)
        GLT = (TCD, HXV)
        PQX = (TGQ, JBF)
        VSX = (LTP, KVX)
        FSV = (FKG, NLC)
        FKR = (CQD, JPR)
        CKT = (RDX, DBQ)
        JFD = (TKS, BBG)
        CNM = (TBH, XRF)
        PBC = (SNJ, QBD)
        MRT = (QCG, CNJ)
        RCQ = (JNR, LND)
        JJG = (KNR, CGF)
        CFP = (JVT, GSX)
        BTG = (SBM, BRJ)
        BJM = (CRK, HVD)
        XVK = (CDS, BQF)
        BCT = (BCK, CKG)
        LST = (RFS, QLN)
        DNM = (VMR, XVK)
        GPB = (GNX, DJV)
        FDR = (FTG, LFQ)
        LCZ = (HFP, MPB)
        XJV = (FCP, JHV)
        HQC = (TRG, SCP)
        RMD = (QMV, NNH)
        SRH = (FLL, QKV)
        QBD = (CQV, DXP)
        RRH = (NCB, TSQ)
        XVF = (NFB, NMN)
        QMT = (GLT, NTS)
        GBX = (TKG, CQK)
        MFP = (TLH, QXD)
        XKG = (MHN, NLR)
        HQH = (HPF, PTD)
        LLR = (CNR, CRF)
        LSP = (SVQ, VJX)
        HSH = (LRK, RLT)
        TTL = (FKR, QMF)
        CFB = (KDL, QFN)
        SXG = (GNX, DJV)
        LTP = (KJJ, JVC)
        HSQ = (SPM, KRH)
        SHG = (DRH, DNM)
        DHJ = (QXR, GHK)
        GGK = (PRK, VCV)
        TRG = (PJN, CFV)
        TTF = (LJV, LSQ)
        VVH = (HSH, HDP)
        QXR = (FNT, LCX)
        DTL = (FSV, VQV)
        KVX = (JVC, KJJ)
        HLR = (BTG, MKN)
        XCG = (QTJ, HTQ)
        LML = (JMQ, FBJ)
        FMS = (XTM, VXJ)
        CTD = (JHQ, XLB)
        TCD = (CSK, GLS)
        MRR = (RQB, XTK)
        SSN = (CNJ, QCG)
        VLG = (NTS, GLT)
        JDT = (JMS, RJB)
        TPJ = (XFX, PBC)
        PDD = (FBJ, JMQ)
        QLJ = (NVL, JSJ)
        TVX = (JPB, GGK)
        QCT = (GBX, RBB)
        GMM = (DLM, MVH)
        RLT = (QCT, FPT)
        PFH = (HTG, DNF)
        DQN = (XCQ, DHC)
        XQC = (QJQ, JLC)
        QCH = (FKR, QMF)
        GMQ = (KPJ, RTF)
        HVJ = (QMV, NNH)
        VDP = (TVX, VFB)
        NXV = (DTL, BRL)
        JHK = (MXJ, MBN)
        JPK = (GQN, MFP)
        SSH = (KQK, HLC)
        FNB = (GPS, LLR)
        HTP = (SPG, CSX)
        HHN = (DNF, HTG)
        QJQ = (JHB, DRK)
        PFC = (KRJ, JLV)
        HFP = (JRD, MMT)
        HGC = (QCJ, CXG)
        KLG = (BVX, QSM)
        LHG = (HLM, XJV)
        CGG = (QCK, RKN)
        XVC = (CGS, JKP)
        FCJ = (TMM, MBL)
        KLC = (CDN, VVH)
        CRF = (LVG, FNX)
        PBP = (GSX, JVT)
        GLS = (DCX, VXG)
        DJD = (QGG, SST)
        BJV = (DMP, HSQ)
        MNL = (JSG, LNC)
        DNF = (NQK, GJP)
        NLR = (SSH, GHM)
        HSP = (JBF, TGQ)
        NRX = (DTX, CJK)
        VVX = (CSX, SPG)
        LSC = (DCL, QBB)
        VXJ = (FLJ, PBZ)
        CDR = (NXN, NMT)
        SGM = (NXV, VJH)
        XSX = (BHV, BHV)
        MGK = (FXG, XTG)
        VPC = (SKC, BDC)
        HBV = (CJK, DTX)
        RQB = (PCT, HTR)
        FXR = (HKP, LVP)
        BRL = (FSV, VQV)
        VXK = (GVD, XXN)
        SDN = (MBL, TMM)
        FCP = (HXD, SHG)
        XTG = (KLT, SPX)
        LBD = (GHK, QXR)
        JHQ = (FGJ, PGB)
        XXT = (KNB, PQN)
        VKC = (TCH, DPF)
        GQN = (QXD, TLH)
        HLM = (JHV, FCP)
        JDK = (TTF, RGR)
        VTS = (PMH, DMM)
        VMR = (CDS, BQF)
        XJA = (BHL, RGF)
        MMS = (NLR, MHN)
        DPF = (PQX, HSP)
        NNH = (FGG, GND)
        JSB = (NLG, HJS)
        XLR = (GMB, HJK)
        RCF = (VBP, SKL)
        JPD = (HTF, MQX)
        CJP = (DKN, QGH)
        BLC = (HGV, JDG)
        FTG = (PSL, TPJ)
        JDS = (SFQ, GGR)
        FQL = (JDV, LNV)
        JBF = (CHC, THP)
        HVG = (MQQ, VHH)
        LKQ = (NLX, HHX)
        KRX = (FXG, XTG)
        JNA = (CKP, KXQ)
        JPR = (CGD, BJH)
        CJK = (MSQ, HCV)
        QSM = (LVL, LPG)
        BQN = (PCG, BJV)
        SFH = (XLB, JHQ)
        XLD = (QNN, LVC)
        GTF = (HTB, RQV)
        BMF = (QJQ, JLC)
        THN = (XLM, DJD)
        VPB = (FXR, VDR)
        RQX = (XQD, JDL)
        LNV = (XJG, FDR)
        NXN = (DSS, KMF)
        QTJ = (DKR, KLG)
        VSV = (KHH, FSD)
        DBD = (MGN, XFD)
        DHC = (PHH, HQC)
        QGH = (VBN, DPJ)
        NTS = (TCD, HXV)
        BSK = (BQG, HVR)
        MRD = (VPB, HJG)
        BQX = (BSK, BRV)
        BRV = (BQG, HVR)
        SVM = (PKX, PJF)
        KRJ = (NMC, TBX)
        GTH = (HVG, HVG)
        SCP = (PJN, CFV)
        CGF = (VFD, GXX)
        SHQ = (THN, JNG)
        JVT = (XKX, RSL)
        RJK = (RVD, CLK)
        MKN = (SBM, BRJ)
        JHV = (HXD, SHG)
        TLT = (JRF, DQN)
        QBR = (NFQ, VTS)
        CNR = (FNX, LVG)
        LVG = (BJN, VXK)
        FCQ = (BHL, RGF)
        JXJ = (CFB, HQL)
        DJV = (BXL, DTF)
        DTX = (HCV, MSQ)
        JLV = (NMC, TBX)
        STQ = (RMH, XDG)
        NQK = (DDX, RJK)
        KTP = (RQV, HTB)
        RLP = (JDL, XQD)
        TQD = (PCG, BJV)
        GGT = (MKN, BTG)
        VJB = (FLL, QKV)
        JVB = (MJT, JPD)
        VQV = (FKG, NLC)
        FXG = (KLT, SPX)
        XFD = (LNS, JDS)
        NKS = (CVS, RGT)
        QFL = (GPS, LLR)
        CDN = (HSH, HDP)
        RTL = (RTF, KPJ)
        CCX = (GPC, BVD)
        CXG = (THT, VVN)
        GRC = (CGG, RRL)
        MXJ = (TRQ, MRD)
        SXM = (HQH, NNK)
        LJV = (SMP, VRJ)
        RJD = (TKS, BBG)
        HMQ = (PBJ, HGD)
        MSQ = (KVR, PKK)
        GPS = (CNR, CRF)
        FNT = (KPL, JHK)
        HDG = (LRB, XFT)
        LFQ = (PSL, TPJ)
        VFD = (HLN, SGX)
        SKC = (CFP, PBP)
        TKV = (HHX, NLX)
        GPP = (TKV, LKQ)
        JSG = (PFH, HHN)
        BCD = (CKT, BFB)
        MPJ = (HVJ, RMD)
        GCT = (MRT, SSN)
        XTM = (FLJ, FLJ)
        DKN = (DPJ, VBN)
        SVN = (VLG, QMT)
        LQZ = (VJK, BCD)
        PHS = (GPB, SXG)
        XCQ = (HQC, PHH)
        QNN = (FCQ, FCQ)
        DMM = (CNS, SVM)
        DBC = (PQN, KNB)
        JFL = (XSL, XSL)
        MBL = (RTL, GMQ)
        VTK = (MGP, SVN)
        SKL = (TVM, NLF)
        HXD = (DRH, DNM)
        GNX = (DTF, BXL)
        XLM = (SST, QGG)
        QMF = (CQD, JPR)
        HMK = (HQB, CCX)
        MMT = (BQX, LGK)
        PJN = (DHG, NKS)
        DGG = (DCL, QBB)
        SPX = (XQC, BMF)
        MHN = (SSH, GHM)
        RDH = (TLT, TBT)
        NMC = (KKX, VPC)
        GKV = (SVN, MGP)
        XSL = (LSP, TXX)
        TGQ = (THP, CHC)
        TRQ = (HJG, VPB)
        VHK = (KRJ, JLV)
        TPX = (MBM, XHF)
        QXD = (QDM, PHS)
        VRJ = (GDK, BVB)
        KXQ = (RLP, RQX)
        CNS = (PKX, PJF)
        TPG = (TVX, VFB)
        PTR = (QFL, FNB)
        QHC = (KKB, BNP)
        CDS = (VGC, LJC)
        BTC = (MCS, DJB)
        NLC = (PHG, XRN)
        BDC = (CFP, PBP)
        FPT = (GBX, RBB)
        CQD = (BJH, CGD)
        XKX = (JGV, XCG)
        TXX = (VJX, SVQ)
        SPP = (GTH, GTH)
        KTM = (HVJ, RMD)
        JGV = (HTQ, QTJ)
        HKP = (KLC, VND)
        GLR = (DVJ, BJJ)
        LMF = (LHG, VLQ)
        CLG = (TFL, HMK)
        KHH = (NNC, XLX)
        HTQ = (KLG, DKR)
        QFN = (CNM, TCT)
        FLL = (TNG, MJV)
        HFV = (NPC, BJM)
        NPC = (HVD, CRK)
        HKK = (KGC, CLG)
        XRF = (PFC, VHK)
        GGS = (DLF, LMF)
        LVC = (FCQ, PDZ)
        DXX = (MJT, JPD)
        DCL = (HGT, VSX)
        LNC = (HHN, PFH)
        TBT = (JRF, DQN)
        DKR = (QSM, BVX)
        KNL = (QCJ, CXG)
        TLH = (PHS, QDM)
        NMT = (DSS, KMF)
        HLC = (GBL, HPK)
        BDX = (TTF, RGR)
        HXV = (GLS, CSK)
        TBH = (VHK, PFC)
        QBB = (HGT, VSX)
        TCH = (PQX, HSP)
        QFH = (XDG, RMH)
        GND = (HPT, GMM)
        CVS = (QJV, HDG)
        FNQ = (VVD, TBQ)
        NCB = (FKM, FKM)
        FHJ = (MMS, XKG)
        VFB = (GGK, JPB)
        RQV = (KKC, BTC)
        NLX = (KNL, HGC)
        TCT = (XRF, TBH)
        GGB = (NRC, XLD)
        JKJ = (NXN, NMT)
        SPG = (DHS, JLB)
        LVP = (VND, KLC)
        NPJ = (KGC, CLG)
        RVD = (SRH, VJB)
        HTT = (NNK, HQH)
        PQC = (TGP, GCT)
        MPB = (MMT, JRD)
        BCR = (FSD, KHH)
        BHN = (LNC, JSG)
        SMP = (BVB, GDK)
        GPC = (NLB, FSB)
        NMD = (GTH, XHM)
        CGD = (SML, VKC)
        CKP = (RQX, RLP)
        DQT = (NCB, NCB)
        KDL = (CNM, TCT)
        CQK = (BDN, KSC)
        NXX = (SFK, RMV)
        RTF = (LJM, SGM)
        KQQ = (HJK, GMB)
        KMF = (BVK, BHH)
        HPK = (KVH, NKQ)
        PLQ = (MLH, PTP)
        RCG = (LVJ, FXX)
        HPF = (LMV, QBR)
        TBX = (VPC, KKX)
        NKQ = (VTK, GKV)
        PRK = (GRD, VVT)
        TPL = (QVF, FMS)
        CFM = (DXX, JVB)
        SGX = (SPP, NMD)
        MLH = (KQQ, XLR)
        NNC = (TNT, BLC)
        XLX = (TNT, BLC)
        MBM = (NHD, PQC)
        PHH = (TRG, SCP)
        QKV = (TNG, MJV)
        XJG = (FTG, LFQ)
        QCK = (XVF, MMX)
        SVQ = (LCD, BKD)
        SXC = (FMB, NKM)
        RCT = (CGS, JKP)
        KNR = (VFD, GXX)
        FKM = (VQX, VQX)
        CKV = (DJN, LLK)
        DDX = (CLK, RVD)
        GCN = (PTP, MLH)
        BFB = (DBQ, RDX)
        SNZ = (TXX, LSP)
        MVH = (JMX, GRC)
        HHX = (HGC, KNL)
        GRD = (GCJ, LST)
        SPM = (CKX, XVN)
        LPL = (VDP, TPG)
        CGM = (BSB, TPX)
        FXX = (LML, PDD)
        PGB = (CKV, VRL)
        MMX = (NMN, NFB)
        DJS = (TCP, CGM)
        HTF = (LPL, RTH)
        DSS = (BVK, BHH)
        KPJ = (SGM, LJM)
        DLM = (GRC, JMX)
        LSQ = (SMP, VRJ)
        SNR = (NVL, JSJ)
        DPJ = (CFM, VBB)
        DDQ = (SFH, CTD)
        VVN = (NXX, TSR)
        QLM = (XKG, MMS)
        QCJ = (VVN, THT)
        JDL = (PFB, PNL)
        DLF = (LHG, VLQ)
        LJC = (JMT, HFV)
        GVQ = (GQN, MFP)
        XTK = (HTR, PCT)
        NRC = (QNN, QNN)
        PHG = (DHJ, LBD)
        BVD = (NLB, FSB)
        VDR = (HKP, LVP)
        BVK = (GVQ, JPK)
        FLB = (JSR, GLR)
    """.trimIndent()
}