lok3rs

visible_mountains.py

def visible_mountains(heights: List[int], verbose=True):
    mstack = []
    answer = 0
    maxnum = -1
    """What is the maximum number"""
    maxcount = 0
    """How many equally maximum height mountains are there"""
    idxfirstmax = -1
    """index of first occurrence of max number"""
    idxlastmax = -1
    """index of last occurrence of max number"""
    secondhighestnum = -1
    """What is the second highest number"""

    # loop forward through indices 0 to N up to two times
    # this part accounts for lower mountains seeing higher mountains
    # and similar height mountains seeing each other
    # only in the forward direction.
    visiblePairsTilFirstHighest = 0
    """
    Keeps track of the number of visible pairs from the start of the list to the first highest
    mountain.
    This value is subtracted from the forward pass as these visible pairs would have been double counted
    in the second pass.
    """
    for idx in range(0, len(heights) * 2):
        ringIdx = idx % len(heights)
        curr = heights[ringIdx]

        if idx < len(heights):
            if curr > maxnum:
                secondhighestnum = maxnum
                maxnum = curr
                idxfirstmax = idx
                idxlastmax = idx
                maxcount = 1
            elif curr == maxnum:
                idxlastmax = idx
                maxcount += 1
            elif curr > secondhighestnum:
                secondhighestnum = curr
        elif idx - len(heights) > idxfirstmax:
            # stop after the first maximum value has been processed in the second loop forward
            if verbose:
                print(f'stopped after index {idxfirstmax} (idxfirstmax) on the second pass.')
            break

        if len(mstack) == 0:
            mstack.append(curr)
            continue

        lastpopped = -1
        numIdenticalPopped = 1
        """
        How many identical elements were popped in a row (always at least 1).
        Used to calculate pairs of same-height mountains seeing each other.
        """
        while len(mstack) > 0 and mstack[-1] < curr:
            # We pop these off to maintain the monotonicity of the stack.
            popped = mstack.pop()
            answer += 1
            if verbose:
                print(f'count {answer}: {popped} (prior) sees {curr} (curr)')

            if popped == lastpopped:
                numIdenticalPopped += 1
                answer += numIdenticalPopped - 1
                if verbose:
                    print(f'count {answer}: another {numIdenticalPopped - 1} mountain(s) of identical height {popped} '
                          f'see each other')
            else:
                lastpopped = popped
                numIdenticalPopped = 1

        if idx == idxfirstmax:
            # if this is the first highest mountain so far, keep track of the visible pair count to
            # subtract later on
            if verbose:
                print(f'storing {answer} forward pairs till first highest mountain at idx {idx}')
            visiblePairsTilFirstHighest = answer

        mstack.append(curr)

    answer -= visiblePairsTilFirstHighest
    answer += triangle_number(maxcount - 1)
    if verbose:
        print(f'Forward pass yielded {answer} visible pairs after subtracting {visiblePairsTilFirstHighest} double counts '
              f'and accounting for {triangle_number(maxcount - 1)} pair(s) of the {maxcount} highest mountain(s) '
              f'being able to see each other')

    if secondhighestnum == -1:
        print(f'Exiting early, all the numbers are the same, solving using triangle numbers instead.\n'
              f'\nAnswer: {triangle_number(len(heights) - 1)}')
        return

    # second loop only checks for mountains seeing higher mountains in backwards direction
    # (mountains of equivalent height seeing each other are already accounted for in forwards loop)
    # this traverses the CDLL from idx 0 backwards to the index of the last maximum.

    # If there is only a single highest mountain, this part also doesn't count second-highest mountains
    # seeing the highest mountain, as it would have already been accounted for in the forward pass.

    mstack = []

    backwardsPairs = 0
    visibleBackwardsPairsTillLastHighest = 0
    """
        Keeps track of the number of visible pairs from the start of the list to the last highest
        mountain during first pass of the backwards traversal.
        This value is subtracted from the backwards pass as these visible pairs would have been double counted
        in the second pass.
        """
    for idx in range(2 * len(heights), 0, -1):
        ringIdx = idx % len(heights)
        curr = heights[ringIdx]

        if idx < idxlastmax:
            if verbose:
                print(f'stopped after index {idxlastmax} (idxlastmax) on backwards second pass')
            break

        if len(mstack) == 0:
            mstack.append(curr)
            continue

        while len(mstack) > 0 and mstack[-1] < curr:
            # We pop these off to maintain the monotonicity of the stack.
            popped = mstack.pop()

            # If there is only a single highest mountain, this part also doesn't count second-highest mountains
            # seeing the highest mountain, as it would have already been accounted for in the forward pass.
            if idxlastmax == idxfirstmax and popped == secondhighestnum and curr == maxnum:
                if verbose:
                    print(f'skipped duplicate: {popped} does not see {curr} backwards as this pair was already accounted '
                          f'for in the forwards pass.')
            else:
                answer += 1
                backwardsPairs += 1
                if verbose:
                    print(f'count {answer}: {popped} (prior) sees {curr} (curr) backwards')

            # in backwards passes, no need to account for same-height mountains seeing each other.

        if idx == idxlastmax + len(heights):
            # if this is the last most highest mountain in the backwards pass, store the number
            # of backwards pairs
            if verbose:
                print(f'storing {backwardsPairs} backwards pairs till last highest mountain at index {idx} ({idxlastmax})')
            visibleBackwardsPairsTillLastHighest = backwardsPairs

        mstack.append(curr)

    answer -= visibleBackwardsPairsTillLastHighest
    print(f'Backwards pass yielded {backwardsPairs} visibility pairs. After subtracting '
          f'{visibleBackwardsPairsTillLastHighest} double-counts,\n\nFinal answer is: {answer}')

def test_visible(l):
    print(f'Testing mountains: {l}\n')
    visible_mountains(l, False)
    print()

if __name__ == '__main__':
    test_visible([1,1,1,1])
    test_visible([1,2,3,4])
    test_visible([4,3,2,1])
    test_visible([1,2,3,2])
    test_visible([1,2,3,4,5])
    test_visible([3,1,1,2,4])
    test_visible([5,4,4,4,3,2,1,5,1])