Minimum Number From Increasing and Decreasing Digits

05 Dec 2020 - Hadron DaVinci

Problem

Given a string containing only I’s and D’s, where I’s represent an increase of 1 between adjacent digits
and D’s represent a decrease of 1 between adjacent digits, create a function named foo which determines
the minimum number formed by digits 1 through 9 that matches that pattern, given that no digits can repeat.

Examples

foo("I") = 12

foo("II") = 123

foo("ID") = 132

foo("IID") = 1243

foo("IIDD") = 12543

foo("IIDDD") = 126543

foo("D") = 21

foo("DD") = 321

foo("DI") = 213

foo("DDI") = 3214

foo("DDII") = 32145

foo("DDIDDIID") = 321654798

Truths

Based on the many examples from above, we can extract some insights.

Truth 1

The number of digits in number is one more than the length of string input
in input string.

For example, “I” (which has one character) produces 12, which has two digits

Similarly, “DDIDDIID” (which has eight characters) produces 321654798, which has nine digits

This is true for all the other examples

Truth 2

Since we can only use digits 1 - 9, and those digits are not allowed to repeat,
the maximum number of digits in number is nine

Truth 3

When string is All I’s, the digits simply increase.

Let i represent the number of I’s, then digits produced are: (1)…(i+1)
For example:

With i=1, “I”, this produces: 12
With i=2, “II”, this produces: 123

Truth 4

When string is All D’s, the digits simply decrease.

Let ( )r represent the reverse of some digits, so that (321)r equals 123

Let d represent the number of D’s, then digits produced are: ((1)…(d+1))r which equals (1)…(d+1)

For example:

With d=1, “D”, this produces: (12)r = 12
With d=2, “DD”, this produces: (123)r = 321

What’s important here is the order of digits is the same as All I’s but reversed

Truth 5

When the trend in string switches from D to I or from I to D,
we can combine the results using truths 3 and 4.

Note trends start with max digit in adjacent left trend

Note “I” trend loses digit shared with adjacent “D” trends

For example:

With “DI”, this produces: (12)r(23) = (21)(23) = 213

With “ID”, this produces: (12)(23)r = (12)(32) = 132

With “DDI”, this produces: (123)r(34) = (321)(34) = 3214

With “IID”, this produces: (123)(34)r = (123)(43) = 1243

With “DDII”, this produces: (123)r(345) = (321)(345) = 32145

With “IIDD”, this produces: (123)(345)r = (123)(543) = 12543

With “DDIDDIID”, this produces: (123)r(34)(456)r(678)(89)r = (321)(34)(654)(678)(98) = 321654798

Methods

Method 1

Time Complexity: n
Spatial Complexity: n

Method 1 Summary
This method shadows the by hand approach discussed in Truth 5 exactly.
Specifically, for each trend, do the following steps:

Find the current trend character

Count how many characters make up the current trend

Create a result only for current trend

this result is called a local_result

local_result starts incrementing at the highest number in previous trend

digit_index allows code to keep track of this information

Modify local_result if current trend character is ‘I’

when there is a ‘D’ trend to the right, remove right digit

when there is a ‘D’ trend to the left, remove left digit

Append local_result to result

Method 1 Solution

class Zoo:
    def __init__(self, _str):
        """
        :param _str: input string of I's and D's
        """
        self.input = _str
        self.digit_index = 1
        self.current_trend = None
        self.result = ''

    def main(self) -> int:
        """
        Runs main logic
        """
        i = 0
        while i < len(self.input):
            current_trend = self.input[i]
            trend_count = self.get_trend_count(current_trend, i)
            local_result = self.get_trend_result(current_trend, trend_count)
            local_result = self.modify_local_result(current_trend, trend_count, local_result, i)
            self.result += local_result
            i += trend_count
        return self.result

    def get_trend_count(self, trend: str, index: int) -> int:
        """
        Counts the number of trend characters which are the same
        in this part of input.
        For example:
            with 'DDDDII',  at i=0 (the trend that starts at beginning of input string), there are 4 D's
            with 'IIDDIII', at i=0 (the trend that starts at beginning of input string), there are 2 I's
        :param trend: current string being counted. Can be either an 'I' or a 'D'
        :param index: location where the trend starts in input string
        """
        start_index = index
        while self.input[index] == trend:
            index += 1
            if index == len(self.input):
                break
        return index - start_index

    def get_trend_result(self, trend: str, trend_count: int):
        """
        Uses information about the trend, trend_count, and digit index to calculate
        the trend result.
        For example,
            with 4 D's and a digit index of 1, this produces: 4321
            with 4 D's and a digit index of 2, this produces: 5432
            with 4 D's and a digit index of 3, this produces: 6543
            with 4 I's and a digit index of 1, this produces: 1234
            with 4 I's and a digit index of 2, this produces: 2345
            with 4 I's and a digit index of 3, this produces: 3456
        :param trend: current string being counted. Can be either an 'I' or a 'D'
        :param trend_count: number of characters in trend
        """
        range_end = self.digit_index + trend_count + 1
        local_result = ''
        index = self.digit_index
        for index in range(index, range_end):
            if trend == 'I':
                local_result = local_result + str(index)
            elif trend == 'D':
                local_result = str(index) + local_result
        self.digit_index = index
        return local_result

    def modify_local_result(self, trend: str, trend_count: int, local_result: str, index: int) -> str:
        """
        Modifies local_result when trend is 'I' by removing digits it shares with adjacent 'D' trends
        When (index + trend_count) < len(_input), this 'I' trend finishes before end of string which implies
        there is a D trend to the right
        When index != 0. this 'I' trend is not the first trend which implies
        there is a D trend to the left
        :param trend: the current string being counted. Can be either an 'I' or a 'D'
        :param trend_count: number of characters in trend
        :param local_result: string being modified
        :param index: location where the trend starts in input string
        """
        if trend == 'D':                                # don't modify if trend is D
            return local_result

        if (index + trend_count) < len(self.input):     # when there is a D trend to the right, remove right digit
            local_result = local_result[:-1]

        if index != 0:                                  # when there is a D trend to the left, remove left digit
            local_result = local_result[1:]

        return local_result

def foo(_input_str):
    f = Zoo(_input_str)
    result = f.main()
    print(f"{_input_str}:", result)
    return int(result)

# Try Code
if __name__ == "__main__":
    assert foo("I") == 12
    assert foo("II") == 123
    assert foo("ID") == 132
    assert foo("IID") == 1243
    assert foo("IIDD") == 12543
    assert foo("IIDDD") == 126543
    assert foo("D") == 21
    assert foo("DD") == 321
    assert foo("DI") == 213
    assert foo("DDI") == 3214
    assert foo("DDII") ==32145
    assert foo("DDIDDIID") == 321654798

Method 1 Result

I: 12
II: 123
ID: 132
IID: 1243
IIDD: 12543
IIDDD: 126543
D: 21
DD: 321
DI: 213
DDI: 3214
DDII: 32145
DDIDDIID: 321654798

Method 2

Time Complexity: n
Spatial Complexity: n

Method 2 Summary
This method is similar to Method 1 except it:

Stores information for each trend in a stack temporarily

Modifies the result directly

no need for a local_result

Doesn’t need to modify results for ‘I’ trends

In general, Method 2 is simpler. Having that said, it wasn’t as intuitive to me at first
but when I saw someone else explain this approach, it made sense to me. The key insight in Method 2:
is that we can use the properties of a stack to reverse the input. Specifically, given a sequence of
elements, we can reverse it by putting the entire sequence onto a stack and popping the stack
until it’s empty.

Note the reason why ‘I’ trends digits aren’t reversed in Method 2 is b/c each ‘I’ trend digit is popped off
the stack before the next ‘I’ trend digit is placed onto the stack. On the other hand, ‘D’ trend digits only
start getting popped off when an ‘I’ character is encountered or when the string ends.

For Method 2, for each index between 0 and (length of input_string) + 1
do the following steps:

Build stack

append (i + 1)

If current trend is ‘I’

process previous trend data

If no trends are remaining

process previous trend data

happens when input_string[i] produces an IndexError

Method 2 Solution

def process_trend_data(result: str, stack: list) -> (str, list):
    """
    Uses information about the trend contained in stack to append digits to result.
    :param result: resulting string of digits
    :param stack:
    """
    while len(stack):
        result = result + stack.pop()
    return result, stack

def foo(_str: str) -> int:
    """
    Contains the main logic
    :param _str: input string
    :return: number formed by digits
    """
    stack = []
    result = ""

    for i in range(len(_str) + 1):                              # must iterate to one more than trend
        try:
            current_trend = _str[i]
        except IndexError:
            current_trend = None

        stack.append(str(i + 1))                                # build stack for all trends, I and D

        if current_trend is None:                               # when no trends are remaining, process previous trend
            result, stack = process_trend_data(result, stack)

        elif current_trend == 'I':                              # when the trend is I, process previous trend
            result, stack = process_trend_data(result, stack)

    print(f"{_str}:", result)
    return int(result)

# Try Code
if __name__ == "__main__":
    assert foo("I") == 12
    assert foo("II") == 123
    assert foo("ID") == 132
    assert foo("IID") == 1243
    assert foo("IIDD") == 12543
    assert foo("IIDDD") == 126543
    assert foo("D") == 21
    assert foo("DD") == 321
    assert foo("DI") == 213
    assert foo("DDI") == 3214
    assert foo("DDII") ==32145
    assert foo("DDIDDIID") == 321654798

Method 2 Result

I: 12
II: 123
ID: 132
IID: 1243
IIDD: 12543
IIDDD: 126543
D: 21
DD: 321
DI: 213
DDI: 3214
DDII: 32145
DDIDDIID: 321654798

Files

method1.py
method2.py