function runSolutionPuzzleOne(input) {
    let lastDepth = Infinity
    let increaseCnt = 0
    for (const depth of input) {
        if (lastDepth < depth) {
            increaseCnt++
        }
        lastDepth = depth
    }
    console.log(`Solution to first puzzle: ${increaseCnt}`)
}

function runSolutionPuzzleTwo(input) {
    let lastDepthSum = Infinity
    let increaseCnt = 0
    for (let i = 0; i + 2 < input.length; i++) {
        const depthSum = input[i] + input[i + 1] + input[i + 2]
        if (lastDepthSum < depthSum) {
            increaseCnt++
        }
        lastDepthSum = depthSum
    }
    console.log(`Solution to second puzzle: ${increaseCnt}`)
}

function runSolutionPuzzleOne(commandsList) {
    let horizontal = 0
    let depth = 0
    for (const { command, value }
        of commandsList) {
        if (command === 'forward') {
            horizontal += value
        } else if (command === 'down') {
            depth += value
        } else if (command === 'up') {
            depth -= value
        }
    }
    console.log(`Solution to first puzzle: ${horizontal * depth}`)
}

function runSolutionPuzzleTwo(commandsList) {
    let horizontal = 0
    let depth = 0
    let aim = 0
    for (const { command, value }
        of commandsList) {
        if (command === 'forward') {
            horizontal += value
            depth += aim * value
        } else if (command === 'down') {
            aim += value
        } else if (command === 'up') {
            aim -= value
        }
    }
    console.log(`Solution to second puzzle: ${horizontal * depth}`)
}

/**
 * @param {Array<string[]>} input
 */
function runSolutionPuzzleOne(input) {
    const gammaCommonBitArray = new Array(input[0].length).fill(0)
    for (const line of input) {
        for (const [i, bitChar] of line.entries()) {
            if (bitChar === '0') {
                gammaCommonBitArray[i] -= 1
            } else {
                gammaCommonBitArray[i] += 1
            }
        }
    }
    const gammaBinStr = gammaCommonBitArray.reduce((binString, value) => value < 0 ? binString + '0' : binString + '1', '')
    const epsilonBinStr = gammaCommonBitArray.reduce((binString, value) => value < 0 ? binString + '1' : binString + '0', '')
    const gamma = parseInt(gammaBinStr, 2)
    const epsilon = parseInt(epsilonBinStr, 2)
    console.log(`Solution to first puzzle: ${gamma * epsilon}`)
}

function getMostCommonValueForIndex(index, input) {
    let result = 0
    for (const line of input) {
        const bitChar = line[index]
        if (bitChar === '0') {
            result -= 1
        } else {
            result += 1
        }
    }
    return result >= 0 ? '1' : '0'
}

function filterInputByIndexValue(input, index, value) {
    return input.filter(line => line[index] === value)
}

function calculateRating(input, filterForMostCommon) {
    let currentInput = JSON.parse(JSON.stringify(input)) // Clone 2d Array. Slow but... ¯\_(ツ)_/¯
    for (let i = 0; i < input[0].length && currentInput.length > 1; i++) {
        let filterValue = getMostCommonValueForIndex(i, currentInput)
        if (!filterForMostCommon) {
            filterValue = filterValue === '1' ? '0' : '1'
        }
        currentInput = filterInputByIndexValue(currentInput, i, filterValue)
    }
    return parseInt(currentInput[0].join(''), 2)
}

function runSolutionPuzzleTwo(input) {
    const oxygen = calculateRating(input, true)
    const co2ScrubberRate = calculateRating(input, false)
    console.log(oxygen, co2ScrubberRate)
    console.log(`Solution to second puzzle: ${oxygen * co2ScrubberRate}`)
}

/**
 * @param {Array.<Array.<{value: number, marked: boolean}>>} board
 * @param {number} lastSetRowIndex
 * @param {number} lastSetColumnIndex
 * @returns boolean
 */
function checkIfBingo(board, lastSetRowIndex, lastSetColumnIndex) {
    const isRowCompleted = board[lastSetRowIndex]
        .map(boardEntry => boardEntry.marked)
        .reduce((previousValue, currentValue) => currentValue && previousValue, true)
    const isColumnCompleted = board
        .map(row => row[lastSetColumnIndex])
        .map(boardEntry => boardEntry.marked)
        .reduce((previousValue, currentValue) => currentValue && previousValue, true)
    return isRowCompleted || isColumnCompleted
}

/**
 * @param {number[]} numberList
 * @param {Array.<Array.<{value: number, marked: boolean}>>} board
 * @returns number
 */
function calculateNumberOfDrawsToWin(numberList, board) {
    let numberOfDraws = 0
    const numberToIndexMap = new Map()
    for ([rowIndex, row] of board.entries()) {
        for ([columnIndex, boardEntry] of row.entries()) {
            numberToIndexMap.set(boardEntry.value, [rowIndex, columnIndex])
        }
    }
    for (const number of numberList) {
        numberOfDraws++
        if (numberToIndexMap.has(number)) {
            const [rowIndex, columnIndex] = numberToIndexMap.get(number)
            board[rowIndex][columnIndex].marked = true
            if (checkIfBingo(board, rowIndex, columnIndex)) {
                return numberOfDraws
            }
        }
    }
    return null
}

/**
 * @param {Array.<Array.<{value: number, marked: boolean}>>} board
 * @returns number
 */
function calculateSumOfUnmarkedNumbers(board) {
    let result = 0
    for (const row of board) {
        for (const boardEntry of row) {
            if (!boardEntry.marked) {
                result += boardEntry.value
            }
        }
    }
    return result
}

/**
 * @param {number[]} numberList
 * @param {Array.<Array.<Array.<{value: number, marked: boolean}>>>} boardList
 * @returns {*}
 */
function calculateDrawsForEachBoard(numberList, boardList) {
    const resultList = []
    for (const board of boardList) {
        resultList.push({
            numberOfDraws: calculateNumberOfDrawsToWin(numberList, board),
            board
        })
    }
    return resultList
}

/**
 * @param {Array.<Array.<Array.<{value: number, marked: boolean}>>>} boardList
 * @param {number[]} numberList
 */
function runSolutionPuzzleOne(numberList, boardList) {
    const resultList = calculateDrawsForEachBoard(numberList, boardList)
    let winningBoard = null
    for (const item of resultList) {
        if (winningBoard === null || item.numberOfDraws < winningBoard.numberOfDraws) {
            winningBoard = item
        }
    }
    const score = calculateSumOfUnmarkedNumbers(winningBoard.board) * numberList[winningBoard.numberOfDraws - 1]
    console.log(`Solution to first puzzle: ${score}`)
}

/**
 * @param {Array.<Array.<Array.<{value: number, marked: boolean}>>>} boardList
 * @param {number[]} numberList
 */
function runSolutionPuzzleTwo(numberList, boardList) {
    const resultList = calculateDrawsForEachBoard(numberList, boardList)
    let winningBoard = null
    for (const item of resultList) {
        if (winningBoard === null || item.numberOfDraws > winningBoard.numberOfDraws) {
            winningBoard = item
        }
    }
    const score = calculateSumOfUnmarkedNumbers(winningBoard.board) * numberList[winningBoard.numberOfDraws - 1]
    console.log(`Solution to second puzzle: ${score}`)
}

/**
 * @param {Array.<{x1: number, y1: number, x2: number, y2: number}>} lineList
 * @returns {Map<string,number>}
 */
function rasterizeLines(lineList) {
    /** @type {Map<string,number>} */
    const rasterizeMap = new Map()
    for (const line of lineList) {
        let currentPos = { x: line.x1, y: line.y1 }
        const lineXLen = Math.abs(line.x2 - line.x1)
        const lineYLen = Math.abs(line.y2 - line.y1)
        const xStepDelta = line.x1 === line.x2 ? 0 : (line.x1 <= line.x2 ? 1 : -1)
        const yStepDelta = line.y1 === line.y2 ? 0 : (line.y1 <= line.y2 ? 1 : -1)
        while (Math.abs(currentPos.x - line.x1) <= lineXLen && Math.abs(currentPos.y - line.y1) <= lineYLen) {
            const pHash = `${currentPos.x},${currentPos.y}`
            const p = rasterizeMap.get(pHash)
            rasterizeMap.set(pHash, p !== undefined ? p + 1 : 1)
            currentPos.x += xStepDelta
            currentPos.y += yStepDelta
        }
    }
    return rasterizeMap
}

/**
 * @param {Array.<{x1: number, y1: number, x2: number, y2: number}>} lineList
 */
function runSolutionPuzzleOne(lineList) {
    const rasterizeMap = rasterizeLines(lineList.filter(p => p.x1 === p.x2 || p.y1 === p.y2))
    let overlapCnt = 0
    for (const value of rasterizeMap.values()) {
        if (value > 1) {
            overlapCnt++
        }
    }
    console.log(`Solution to first puzzle: ${overlapCnt}`)
}

/**
 * @param {Array.<{x1: number, y1: number, x2: number, y2: number}>} lineList
 */
function runSolutionPuzzleTwo(lineList) {
    const rasterizeMap = rasterizeLines(lineList)
    let overlapCnt = 0
    for (const value of rasterizeMap.values()) {
        if (value > 1) {
            overlapCnt++
        }
    }
    console.log(`Solution to second puzzle: ${overlapCnt}`)
}

/**
 * @param {number[]} fishDayList
 * @param {number} days
 * @returns {number} Total number of fishes
 */
function runSimulation(fishDayList, days) {
    let resetFishesCnt = 0
    for (let day = 1; day <= days; day++) {
        for (let [key, fishCnt] of fishDayList.entries()) {
            if (key === 0) {
                resetFishesCnt = fishCnt
                fishDayList[0] = 0
            } else {
                fishDayList[key - 1] = fishCnt
            }
        }
        fishDayList[8] = resetFishesCnt
        fishDayList[6] += resetFishesCnt
    }
    return fishDayList.reduce((pV, cV) => pV + cV, 0)
}

/**
 * @param {number[]} fishDayList
 */
function runSolutionPuzzleOne(fishDayList) {
    const result = runSimulation(fishDayList, 80)
    console.log(`Solution to first puzzle: ${result}`)
}

/**
 * @param {number[]} fishDayList
 */
function runSolutionPuzzleTwo(fishDayList) {
    const result = runSimulation(fishDayList, 256)
    console.log(`Solution to second puzzle: ${result}`)
}

/**
 * @param {number[]} crabList
 */
function runSolutionPuzzleOne(crabList) {
    const minPos = Math.min(...crabList)
    const maxPos = Math.max(...crabList)
    let minFuelConsumption = Infinity
    for (let pos = minPos; pos <= maxPos; pos++) {
        const fuelConsumption = crabList.reduce((pV, cV) => pV + Math.abs(cV - pos), 0)
        if (fuelConsumption < minFuelConsumption) {
            minFuelConsumption = fuelConsumption
        }
    }
    console.log(`Solution to first puzzle: ${minFuelConsumption}`)
}

/**
 * @param {number} fromPos
 * @param {number} toPos
 * @returns {number} Fuel consumption
 */
function calcFuelConsumption(fromPos, toPos) {
    let result = 0
    for (let i = 1; i <= Math.abs(toPos - fromPos); i++) {
        result += i
    }
    return result
}

/**
 * @param {number[]} crabList
 */
function runSolutionPuzzleTwo(crabList) {
    const minPos = Math.min(...crabList)
    const maxPos = Math.max(...crabList)
    let minFuelConsumption = Infinity
    for (let pos = minPos; pos <= maxPos; pos++) {
        const fuelConsumption = crabList.reduce((pV, cV) => pV + calcFuelConsumption(cV, pos), 0)
        if (fuelConsumption < minFuelConsumption) {
            minFuelConsumption = fuelConsumption
        }
    }
    console.log(`Solution to second puzzle: ${minFuelConsumption}`)
}

/**
 * @param {Array.<{usp: string[], output: string[]}>} entryList
 */
function runSolutionPuzzleOne(entryList) {
    let simpleDigitsCnt = 0
    for (let entry of entryList) {
        for (let digitSignalLineCnt of entry.output.map(v => v.length)) {
            if ([2, 4, 3, 7].includes(digitSignalLineCnt)) {
                simpleDigitsCnt++
            }
        }
    }
    console.log(`Solution to first puzzle: ${simpleDigitsCnt}`)
}

/**
 * @param {string[]} outputList
 * @returns {string[]} Initialized digit list containing simple digits only
 */
function initializeDigitList(outputList) {
    const digitList = new Array(10).fill(null)
    for (const [index, digitSignalLineCnt] of outputList.map(v => v.length).entries()) {
        if (digitSignalLineCnt === 2) {
            digitList[1] = outputList[index]
        } else if (digitSignalLineCnt === 4) {
            digitList[4] = outputList[index]
        } else if (digitSignalLineCnt === 3) {
            digitList[7] = outputList[index]
        } else if (digitSignalLineCnt === 7) {
            digitList[8] = outputList[index]
        }
    }
    return digitList
}

/**
 * @param {string} digitA
 * @param {string} digitB
 * @returns {string} Distinct signal
 */
function getDistinctSignals(digitA, digitB) {
    const digitACharList = digitA.split('')
    const digitBCharList = digitB.split('')
    let result = ''
    for (const d of digitACharList) {
        if (!digitBCharList.includes(d)) {
            result += d
        }
    }
    for (const d of digitBCharList) {
        if (!digitACharList.includes(d)) {
            result += d
        }
    }
    return result
}

/**
 * @param {Array.<{usp: string[], output: string[]}>} entryList
 */
function runSolutionPuzzleTwo(entryList) {
    let totalEntryValue = 0
    for (const entry of entryList) {
        // Initialize digit list with the simple digits
        const digitList = initializeDigitList(entry.usp)

        // Do a little deduction
        const aSignal = getDistinctSignals(digitList[1], digitList[7])
        const cfSignal = digitList[1]
        digitList[3] = entry.usp.filter(v => v.length === 5 && getDistinctSignals(cfSignal, v).length === 3)[0]
        const egSignal = getDistinctSignals(aSignal, getDistinctSignals(digitList[4], digitList[8]))
        digitList[9] = entry.usp.filter(v => v.length === 6 && getDistinctSignals(egSignal, v).length === 6)[0]
        const eSignal = getDistinctSignals(digitList[8], digitList[9])
        digitList[2] = entry.usp.filter(v => v.length === 5 && getDistinctSignals(eSignal, v).length === 4)[0]
        digitList[5] = entry.usp.filter(v => v.length === 5 && v !== digitList[2] && v !== digitList[3])[0]
        const dgSignal = getDistinctSignals(aSignal, getDistinctSignals(digitList[1], digitList[3]))
        digitList[6] = entry.usp.filter(v => v.length === 6 && getDistinctSignals(dgSignal, v).length === 4 && v !== digitList[9])[0]
        digitList[0] = entry.usp.filter(v => v.length === 6 && v !== digitList[6] && v !== digitList[9])[0]

        // Finally, convert output to number
        const digitCharMap = new Map()
        for (const [digit, chars] of digitList.entries()) {
            digitCharMap.set(chars, digit)
        }
        const entryValue = parseInt(entry.output.reduce((pV, cV) => `${pV}${digitCharMap.get(cV)}`, ''), 10)

        totalEntryValue += entryValue
    }
    console.log(`Solution to second puzzle: ${totalEntryValue}`)
}

/**
 * @param {Array.<Array.<number>>} heighMatrix
 * @param {number} xPos
 * @param {number} yPos
 * @returns {boolean} Is minimum
 */
function isMinimum(heighMatrix, xPos, yPos) {
    const currentHeight = heighMatrix[yPos][xPos]
    return heighMatrix[yPos][xPos - 1] > currentHeight &&
        heighMatrix[yPos][xPos + 1] > currentHeight &&
        heighMatrix[yPos + 1][xPos] > currentHeight &&
        heighMatrix[yPos - 1][xPos] > currentHeight
}

/**
 * @param {Array.<Array.<boolean>>} localMinimumMatrix
 * @param {number} xPos
 * @param {number} yPos
 */
function setLocalMinimum(localMinimumMatrix, xPos, yPos) {
    localMinimumMatrix[yPos][xPos] = true
    localMinimumMatrix[yPos][xPos - 1] = false
    localMinimumMatrix[yPos][xPos + 1] = false
    localMinimumMatrix[yPos - 1][xPos] = false
    localMinimumMatrix[yPos + 1][xPos] = false
}

/**
 * @param {Array.<Array.<number>>} heighMatrix
 * @returns {Array.<Array.<number>>} Local minimum matrix
 */
function generateLocalMinimumMatrix(heighMatrix) {
    const localMinimumMatrix = new Array(heighMatrix.length).fill(null).map(() => new Array(heighMatrix[0].length).fill(false))
    for (let xPos = 1; xPos < heighMatrix[0].length - 1; xPos++) {
        for (let yPos = 1; yPos < heighMatrix.length - 1; yPos++) {
            if (isMinimum(heighMatrix, xPos, yPos)) {
                setLocalMinimum(localMinimumMatrix, xPos, yPos)
            }
        }
    }
    return localMinimumMatrix
}

/**
 * @param {Array.<Array.<number>>} heighMatrix
 */
function runSolutionPuzzleOne(heighMatrix) {
    const localMinimumMatrix = generateLocalMinimumMatrix(heighMatrix)
    let totalRiskLevel = 0
    for (let xPos = 1; xPos < heighMatrix[0].length - 1; xPos++) {
        for (let yPos = 1; yPos < heighMatrix.length - 1; yPos++) {
            if (localMinimumMatrix[yPos][xPos]) {
                totalRiskLevel += heighMatrix[yPos][xPos] + 1
            }
        }
    }
    console.log(`Solution to first puzzle: ${totalRiskLevel}`)
}

/**
 * @param {Array.<Array.<number>>} heighMatrix
 * @param {number} xPos
 * @param {number} yPos
 * @returns {number} Size of basin
 */
function recurseBasin(heighMatrix, xPos, yPos) {
    if (heighMatrix[yPos][xPos] < 9) {
        heighMatrix[yPos][xPos] = 9 // Mark as visited
        let size = 1
        size += recurseBasin(heighMatrix, xPos - 1, yPos)
        size += recurseBasin(heighMatrix, xPos + 1, yPos)
        size += recurseBasin(heighMatrix, xPos, yPos - 1)
        size += recurseBasin(heighMatrix, xPos, yPos + 1)
        return size
    } else {
        return 0
    }
}

/**
 * @param {Array.<Array.<number>>} heighMatrix
 */
function runSolutionPuzzleTwo(heighMatrix) {
    const localMinimumMatrix = generateLocalMinimumMatrix(heighMatrix)
    const basinList = []
    for (let xPos = 1; xPos < heighMatrix[0].length - 1; xPos++) {
        for (let yPos = 1; yPos < heighMatrix.length - 1; yPos++) {
            if (localMinimumMatrix[yPos][xPos]) {
                basinList.push(recurseBasin(heighMatrix, xPos, yPos))
            }
        }
    }
    const result = basinList.sort((a, b) => b - a).slice(0, 3).reduce((pV, cV) => pV * cV)
    console.log(`Solution to second puzzle: ${result}`)
}

/** @type {Map<string,string>} */
const commandMap = new Map([
    ['(', ')'],
    ['[', ']'],
    ['{', '}'],
    ['<', '>']
])
const startCommandChars = [...commandMap.keys()]

/** @type {Map<string,number>} */
const corruptScoreMap = new Map([
    [')', 3],
    [']', 57],
    ['}', 1197],
    ['>', 25137]
])

/**
 * @param {string} line
 * @returns {string}
 */
function getFirstCorruptedChar(line) {
    const stack = []
    for (const c of line) {
        if (startCommandChars.includes(c)) {
            stack.push(c)
        } else {
            const cPrev = stack.pop()
            if (commandMap.get(cPrev) !== c) {
                return c
            }
        }
    }
    return null
}

/**
 * @param {Array.<string>} lineList
 */
function runSolutionPuzzleOne(lineList) {
    const corruptLineChars = new Map([
        [')', 0],
        [']', 0],
        ['}', 0],
        ['>', 0]
    ])
    for (const line of lineList) {
        const c = getFirstCorruptedChar(line)
        if (c !== null) {
            corruptLineChars.set(c, corruptLineChars.get(c) + 1)
        }
    }
    const points = [...corruptLineChars.entries()].reduce((pV, [c, count]) => pV + corruptScoreMap.get(c) * count, 0)
    console.log(`Solution to first puzzle: ${points}`)
}

/** @type {Map<string,number>} */
const incompleteScoreMap = new Map([
    [')', 1],
    [']', 2],
    ['}', 3],
    ['>', 4]
])

/**
 * @param {string} line
 * @returns {string}
 */
function generateCompletionString(line) {
    const stack = []
    for (const c of line) {
        startCommandChars.includes(c) ? stack.push(c) : stack.pop()
    }
    return stack.reverse().reduce((pV, c) => pV + commandMap.get(c), '')
}

/**
 * @param {string} value
 * @returns {number}
 */
function scoreCompletionString(value) {
    let score = 0
    for (const c of value) {
        score = score * 5 + incompleteScoreMap.get(c)
    }
    return score
}

/**
 * @param {Array.<string>} lineList
 */
function runSolutionPuzzleTwo(lineList) {
    const scoreList = []
    for (const line of lineList) {
        if (getFirstCorruptedChar(line) === null) {
            const completionString = generateCompletionString(line)
            scoreList.push(scoreCompletionString(completionString))
        }
    }
    const sortedScoreList = scoreList.sort((a, b) => a - b)
    const middleScore = sortedScoreList[Math.floor(sortedScoreList.length / 2)]
    console.log(`Solution to second puzzle: ${middleScore}`)
}

/**
 * @param {Array.<Array.<number>>} octopusMatrix
 * @param {number} x
 * @param {number} y
 */
function flashOctopus(octopusMatrix, x, y) {
    octopusMatrix[y][x] = 0
    for (let ty = Math.max(y - 1, 0); ty <= Math.min(y + 1, octopusMatrix.length - 1); ty++) {
        for (let tx = Math.max(x - 1, 0); tx <= Math.min(x + 1, octopusMatrix[0].length - 1); tx++) {
            if (!(ty === y && tx === x) && octopusMatrix[ty][tx] !== 0) {
                octopusMatrix[ty][tx] += 1
            }
        }
    }
}

/**
 * @param {Array.<Array.<number>>} octopusMatrix
 * @returns {number} Number of flashes ocurred in this step
 */
function executeStep(octopusMatrix) {
    for (let y = 0; y < octopusMatrix.length; y++) {
        for (let x = 0; x < octopusMatrix[0].length; x++) {
            octopusMatrix[y][x] += 1
        }
    }
    let didFlash = true
    let flashCnt = 0
    while (didFlash) {
        didFlash = false
        for (let y = 0; y < octopusMatrix.length; y++) {
            for (let x = 0; x < octopusMatrix[0].length; x++) {
                if (octopusMatrix[y][x] > 9) {
                    flashCnt++
                    didFlash = true
                    flashOctopus(octopusMatrix, x, y)
                }
            }
        }
    }
    return flashCnt
}

/**
 * @param {Array.<Array.<number>>} octopusMatrix
 */
function runSolutionPuzzleOne(octopusMatrix) {
    let flashCnt = 0
    for (let step = 1; step <= 100; step++) {
        flashCnt += executeStep(octopusMatrix)
    }
    console.log(`Solution to first puzzle: ${flashCnt}`)
}

/**
 * @param {Array.<Array.<number>>} octopusMatrix
 */
function runSolutionPuzzleTwo(octopusMatrix) {
    const maxFlashCnt = octopusMatrix.length * octopusMatrix[0].length
    let lastFlashCnt = 0
    let stepCnt = 0
    do {
        stepCnt++
        lastFlashCnt = executeStep(octopusMatrix)
    } while (lastFlashCnt !== maxFlashCnt)
    console.log(`Solution to second puzzle: ${stepCnt}`)
}

/**
 * @param {string} edge
 * @returns {boolean}
 */
function isSmallCave(edge) {
    return edge === edge.toLocaleLowerCase()
}

/**
 * @param {string[]} traversedPath
 * @returns {*}
 */
function simpleFilterGenerator(traversedPath) {
    return (edge) => {
        return !isSmallCave(edge) || !traversedPath.includes(edge)
    }
}

/**
 * @param {Map<string,Array.<string>>} edgeMap
 * @param {string[]} traversedPath
 * @param {*} edgeFilterGenerator
 * @returns {string[]}
 */
function findDistinctPaths(edgeMap, traversedPath, edgeFilterGenerator) {
    /** @type {string[]} */
    let result = []
    const lastEdge = traversedPath[traversedPath.length - 1]
    const edgeFilter = edgeFilterGenerator(traversedPath)
    const nextEdges = edgeMap.get(lastEdge).filter(edgeFilter)
    for (const edge of nextEdges) {
        if (edge === 'end') {
            result.push([...traversedPath, edge])
        } else {
            result = result.concat([...findDistinctPaths(edgeMap, [...traversedPath, edge], edgeFilterGenerator)])
        }
    }
    return result
}

/**
 * @param {Map<string,Array.<string>>} edgeMap
 */
function runSolutionPuzzleOne(edgeMap) {
    const paths = findDistinctPaths(edgeMap, ['start'], simpleFilterGenerator)
    console.log(`Solution to first puzzle: ${paths.length}`)
}

/**
 * @param {string[]} traversedPath
 * @returns {*}
 */
function complexFilterGenerator(traversedPath) {
    const maxSmallCaveVisitCount = Math.max(...traversedPath.filter(isSmallCave).map(v => traversedPath.filter(vv => vv === v).length))
    return (edge) => {
        return !isSmallCave(edge) || (maxSmallCaveVisitCount < 2 && isSmallCave(edge)) || !traversedPath.includes(edge)
    }
}

/**
 * @param {Map<string,string[]>} edgeMap
 */
function runSolutionPuzzleTwo(edgeMap) {
    const paths = findDistinctPaths(edgeMap, ['start'], complexFilterGenerator)
    console.log(`Solution to second puzzle: ${paths.length}`)
}

/**
 * @param {Map<string, [{x: number, y: number}]>} dotMap
 * @param {{axis: string, value: number}} instruction
 */
function fold(dotMap, instruction) {
    for (const [dotHash, dot] of dotMap.entries()) {
        if (instruction.value < dot[instruction.axis]) {
            const axisPos = instruction.value - (dot[instruction.axis] - instruction.value)
            const newDot = {...dot }
            newDot[instruction.axis] = axisPos
            if (!dotMap.has(`${newDot.x},${newDot.y}`)) {
                dotMap.set(`${newDot.x},${newDot.y}`, { x: newDot.x, y: newDot.y })
            }
            dotMap.delete(dotHash)
        }
    }
}

/**
 * @param {Map<string, [{x: number, y: number}]>} dotMap
 * @param {Array.<{axis: string, value: number}>} instructionList
 */
function runSolutionPuzzleOne(dotMap, instructionList) {
    fold(dotMap, instructionList[0])
    console.log(`Solution to first puzzle: ${dotMap.size}`)
}

/**
 * @param {Map<string, [{x: number, y: number}]>} dotMap
 */
function plotLetters(dotMap) {
    let xMax = 0
    let yMax = 0
    for (const dot of dotMap.values()) {
        xMax = Math.max(xMax, dot.x)
        yMax = Math.max(yMax, dot.y)
    }
    for (let y = 0; y < yMax + 1; y++) {
        let line = ''
        for (let x = 0; x < xMax + 1; x++) {
            line += dotMap.has(`${x},${y}`) ? '#' : '.'
        }
        console.log(line)
    }
}

/**
 * @param {Map<string, [{x: number, y: number}]>} dotMap
 * @param {Array.<{axis: string, value: number}>} instructionList
 */
function runSolutionPuzzleTwo(dotMap, instructionList) {
    for (const instruction of instructionList) {
        fold(dotMap, instruction)
    }
    console.log('Solution to second puzzle: (see plot)')
    plotLetters(dotMap)
}

/**
 * We just need to count the number of pairs and the numbers of single chars added.
 * The correct order of the pairs in the template string is irrelevant hence
 * we don't need to perform here any complex string modifications. This makes
 * the solution pretty simple :o)
 * @param {string} template
 * @param {number} steps
 * @param {Map<string, string>} rules
 * @returns {Map<string, number>}
 */
function getCharCountForTemplate(template, steps, rules) {
    const pairMap = initializePairMap(template)
    const charCountMap = countChars(template)
    for (let step = 1; step <= steps; step++) {
        const pairMapClone = new Map([...pairMap])
        for (const [pair, count] of pairMapClone.entries()) {
            // Add new pairs depending on the quantity of the current pair
            const insertChar = rules.get(pair)
            const leftPair = pair[0] + insertChar
            const rightPair = insertChar + pair[1]
            incrementMapValue(pairMap, leftPair, count)
            incrementMapValue(pairMap, rightPair, count)

            // Update char count
            incrementMapValue(charCountMap, insertChar, count)

            // Finally, remove current pairs as we've split them up into two new pairs
            decrementMapValue(pairMap, pair, count)
            if (pairMap.get(pair) === 0) {
                pairMap.delete(pair)
            }
        }
    }
    return charCountMap
}

/**
 * Map of pairs appearing in the template string and their count
 * @param {string} template
 * @returns {Map<string, Map<string, number>>}
 */
function initializePairMap(template) {
    /** @type {Map<string, number>} */
    const pairMap = new Map()
    for (let i = 0; i < template.length - 1; i++) {
        const pair = template[i] + template[i + 1]
        pairMap.set(pair, pairMap.has(pair) ? pairMap.get(pair) + 1 : 1)
    }
    return pairMap
}

/**
 * @param {string} template
 * @returns {Map<string, number>}
 */
function countChars(template) {
    const resultMap = new Map()
    for (const char of template) {
        incrementMapValue(resultMap, char, 1)
    }
    return resultMap
}

function incrementMapValue(map, key, value) {
    map.set(key, map.has(key) ? map.get(key) + value : value)
}

function decrementMapValue(map, key, value) {
    map.set(key, map.get(key) - value)
}

/**
 * @param {string} template
 * @param {Map<string, string>} rules
 */
function runSolutionPuzzleOne(template, rules) {
    const result = getCharCountForTemplate(template, 10, rules)
    const leastCommonCnt = Math.min(...result.values())
    const mostCommonCnt = Math.max(...result.values())
    console.log(`Solution to first puzzle: ${mostCommonCnt - leastCommonCnt}`)
}

/**
 * @param {string} template
 * @param {Map<string, string>} rules
 */
function runSolutionPuzzleTwo(template, rules) {
    const result = getCharCountForTemplate(template, 40, rules)
    const leastCommonCnt = Math.min(...result.values())
    const mostCommonCnt = Math.max(...result.values())
    console.log(`Solution to second puzzle: ${mostCommonCnt - leastCommonCnt}`)
}

/**
 * Dijkstra algorithm with optimized min heap
 * @param {Array.<Array.<number>>} riskMatrix
 * @returns {number}
 */
function getPathWithMinRisk(riskMatrix) {
    /** @type {Array.<Array.<{x: number, y: number, risk: number}>>} */
    const gridMatrix = new Array(riskMatrix.length)
        .fill(null)
        .map(_ => new Array(riskMatrix.length).fill(null))
    let minHeap = [{ x: 0, y: 0, risk: 0 }]
    gridMatrix[0][0] = minHeap[0]
    const tXY = riskMatrix.length - 1
    const adjacentGrids = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ]
    while (minHeap.length > 0) {
        const u = minHeap.shift()
        if (u.x === tXY && u.y === tXY) {
            return u.risk
        }
        for (const [dX, dY] of adjacentGrids) {
            const vX = u.x + dX
            const vY = u.y + dY
            if (0 <= vX && vX < riskMatrix.length && 0 <= vY && vY < riskMatrix.length) {
                const uvRisk = u.risk + riskMatrix[vY][vX]
                let v = gridMatrix[vY][vX]
                if (v === null) {
                    v = { x: vX, y: vY, risk: uvRisk }
                    minHeap.unshift(v)
                    gridMatrix[vY][vX] = v
                } else if (uvRisk < v.risk) {
                    v.risk = uvRisk
                }
            }
        }
        minHeap.sort((a, b) => a.risk - b.risk)
    }
}

/**
 * @param {Array.<Array.<number>>} riskMatrix
 */
function runSolutionPuzzleOne(riskMatrix) {
    const result = getPathWithMinRisk(riskMatrix)
    console.log(`Solution to first puzzle: ${result}`)
}

/**
 * @param {Array.<Array.<number>>} riskMatrix
 */
function runSolutionPuzzleTwo(riskMatrix) {
    const factor = 5
    const fullRiskMatrix = new Array(riskMatrix.length * factor)
        .fill(null)
        .map(_ => new Array(riskMatrix.length * factor).fill(null))
    for (n = 0; n < factor; n++) {
        for (m = 0; m < factor; m++) {
            const yOffset = n * riskMatrix.length
            for (let y = 0; y < riskMatrix.length; y++) {
                const xOffset = m * riskMatrix.length
                for (let x = 0; x < riskMatrix.length; x++) {
                    fullRiskMatrix[yOffset + y][xOffset + x] = ((riskMatrix[y][x] + n + m - 1) % 9) + 1
                }
            }
        }
    }
    const result = getPathWithMinRisk(fullRiskMatrix)
    console.log(`Solution to second puzzle: ${result}`)
}

const bitMasks = [
    0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF
]

/**
 * @param {Uint8Array[]} input
 * @param {number} startIndex
 * @param {number} endIndex
 * @returns {number}
 */
function getBits(input, startIndex, endIndex) {
    let result = 0
    let currentIndex = startIndex
    while (currentIndex < endIndex) {
        const byteIndex = Math.floor(currentIndex / 8)
        const bitI = currentIndex % 8
        const bitJ = (endIndex >= (byteIndex + 1) * 8) ? 8 : ((endIndex - 1) % 8 + 1)
        result = result << (bitJ - bitI)
        result |= ((input[byteIndex] >> (8 - bitJ)) & bitMasks[bitJ - bitI])
        currentIndex = (byteIndex + 1) * 8
    }
    return result
}

/**
 * @param {number[]} arr
 * @return {number}
 */
function convert4BitArrayToNumber(arr) {
    if (arr.length % 2 === 1) {
        arr.unshift(0)
    }
    const byteArr = new Uint8Array(arr.length / 2)
    for (let i = 0; i < arr.length; i += 2) {
        byteArr[i / 2] = arr[i] << 4 | arr[i + 1]
    }
    let buffer = Buffer.from(byteArr);
    return buffer.readUIntBE(0, byteArr.length);
}

/**
 * @param {Uint8Array[]} input
 * @param {number} offset
 * @returns {*}
 */
function processPacket(input, offset) {
    const headerOffset = offset + 3 + 3
    const pVersion = getBits(input, offset, offset + 3)
    const pType = getBits(input, offset + 3, offset + 3 + 3)
    if (pType === 4) {
        let groupIndex = -1
        let isLastGroup = false
        let literal4BitList = []
        while (!isLastGroup) {
            groupIndex++
            const groupStartIndex = headerOffset + groupIndex * 5
            const groupBits = getBits(input, groupStartIndex, groupStartIndex + 5)
            literal4BitList.push(groupBits & bitMasks[4])
            isLastGroup = groupBits >> 4 === 0
        }

        // JavaScript %$/§&$% when working with bit shift operators.
        // Shift works on signed 32-bit values but some values in the input are larger than.
        // As a result, we've suddenly minus values if we shift the value too much left.
        // Workaround: create an array of 4 bit values and convert it to a number...
        //       ¯\_(ツ)_/¯
        const literal = convert4BitArrayToNumber(literal4BitList)

        return {
            offset: headerOffset + groupIndex * 5 + 5,
            packet: {
                version: pVersion,
                type: pType,
                literal
            }
        }
    } else {
        const lengthTypeId = getBits(input, headerOffset, headerOffset + 1)
        if (lengthTypeId === 0) {
            const totalLength = getBits(input, headerOffset + 1, headerOffset + 1 + 15)
            let payloadOffset = headerOffset + 1 + 15
            let currentOffset = payloadOffset
            const packets = []
            while (currentOffset < payloadOffset + totalLength) {
                const { offset, packet } = processPacket(input, currentOffset)
                packets.push(packet)
                currentOffset = offset
            }
            return {
                offset: currentOffset,
                packet: {
                    version: pVersion,
                    type: pType,
                    packets
                }
            }
        } else {
            const numberOfSubPackets = getBits(input, headerOffset + 1, headerOffset + 1 + 11)
            let currentPackage = 1
            let payloadOffset = headerOffset + 1 + 11
            let currentOffset = payloadOffset
            const packets = []
            while (currentPackage <= numberOfSubPackets) {
                const { offset, packet } = processPacket(input, currentOffset)
                packets.push(packet)
                currentOffset = offset
                currentPackage++
            }
            return {
                offset: currentOffset,
                packet: {
                    version: pVersion,
                    type: pType,
                    packets
                }
            }
        }
    }
}

/**
 * @param {*} packets
 * @returns {number}
 */
function sumVersions(packets) {
    let versionSum = 0
    for (const packet of packets) {
        if (packet.type === 4) {
            versionSum += packet.version
        } else {
            versionSum += packet.version + sumVersions(packet.packets)
        }
    }
    return versionSum
}

/**
 * @param {Uint8Array[]} input
 */
function runSolutionPuzzleOne(input) {
    const { packet } = processPacket(input, 0)
    const versionSum = sumVersions([packet])
    console.log(`Solution to first puzzle: ${versionSum}`)
}

/**
 * @param {*} packet
 * @returns {number}
 */
function evaluatePacket(packet) {
    const valueList = packet.packets
        .map(p => p.type === 4 ? p.literal : evaluatePacket(p))
    if (packet.type === 0) {
        return valueList.reduce((sum, v) => sum + v, 0)
    } else if (packet.type === 1) {
        return valueList.reduce((sum, v) => sum * v, 1)
    } else if (packet.type === 2) {
        return Math.min(...valueList)
    } else if (packet.type === 3) {
        return Math.max(...valueList)
    } else if (packet.type === 5) {
        return valueList[0] > valueList[1] ? 1 : 0
    } else if (packet.type === 6) {
        return valueList[0] < valueList[1] ? 1 : 0
    } else if (packet.type === 7) {
        return valueList[0] === valueList[1] ? 1 : 0
    }
}

/**
 * @param {Uint8Array[]} input
 */
function runSolutionPuzzleTwo(input) {
    const { packet } = processPacket(input, 0)
    const result = evaluatePacket(packet)
    console.log(`Solution to second puzzle: ${result}`)
}