12
\$\begingroup\$

This is the "Beautiful Binary String" problem at HackerRank:

Alice has a binary string. She thinks a binary string is beautiful if and only if it doesn't contain the substring 010.

In one step, Alice can change a 0 to a 1 or vice versa. Count and print the minimum number of steps needed to make Alice see the string as beautiful.

For example, if Alice's string is 010 she can change any one element and have a beautiful string.

This is my Python code:

def beautifulBinaryString(b):
    temp = list(b)
    count,i = 0,0
    if len(b) == 3 and b == "010": count += 1
    elif len(b) == 3 and b != "010": count = count
    else:
        while (i+3 <= len(temp)):
            if temp[i:i+3] == ['0','1','0']: 
                count += 1
                del temp[i:i+3]
            else: i += 1
    return count

It seems to me as having too many conditionals (though readable, I guess). Is there a more concise way to accomplish this?

Some test cases:

0101010 
01100

2
0
\$\endgroup\$
17
\$\begingroup\$

Style

  • Read the PEP8 style guide!

    1. Functions and variables should be snake_case
    2. Conditions should be on the next line if a: ... is bad style
    3. Conditions don't need parenthesis while (a) is the same as while a:
    4. Avoid temp variables

Algorithm

  • Your first 2 guard clauses seem very unnecessary

    When I remove them, the code still works.

  • Consider writing docstring/tests or both with the doctest module

Alternative Code

You could use re.findall(substring, string) for counting the occurrence,

OR string.count(substring) making this practically a one-line

import doctest

def beautiful_binary_string(b):
    """
    Returns the steps to make a binary string beautiful

    >>> beautiful_binary_string("0101010")
    2

    >>> beautiful_binary_string("01100")
    0

    >>> beautiful_binary_string("0100101010100010110100100110110100011100111110101001011001110111110000101011011111011001111100011101")
    10
    """
    return b.count("010")

if __name__ == '__main__':
    doctest.testmod()
\$\endgroup\$
  • 1
    \$\begingroup\$ @Tyberius: It seems to work fine because count doesn't count overlapping substrings. 'aaa'.count('aa') is just 1 \$\endgroup\$ – Eric Duminil Oct 2 '18 at 6:56
  • 2
    \$\begingroup\$ Now, that's some anticlimactic solution :D. \$\endgroup\$ – Eric Duminil Oct 2 '18 at 6:57
  • 1
    \$\begingroup\$ @EricDuminil Yes somehow this feels more like a hack then an actual solution :) \$\endgroup\$ – Ludisposed Oct 2 '18 at 8:05
  • 2
    \$\begingroup\$ Indeed, as you answer the question without doing the steps; A non-constructive solution is fine, but 1. you didn't show that doing a step to fix one occurrence doesn't create another one, 2. you didn't show that two overlapping occurrences can be fixed using a single step. \$\endgroup\$ – maaartinus Oct 2 '18 at 10:24
  • \$\begingroup\$ @Ludisposed Oh I overlooked that, guess I just assumed it had to be more complicated haha. Very clever solution +1. I'll clear my comments since maaartinus's suggestion addresses it \$\endgroup\$ – Tyberius Oct 2 '18 at 12:23
10
\$\begingroup\$

Is there a more concise way to accomplish this?

Certainly.

For a start, the special cases are unnecessary. (They make me think that the code has been refactored from a recursive version).

Secondly, the expensive del temp[i:i+3] could be replaced with i += 3, and since the processing is no longer destructive temp is unnecessary. This simplifies the code to

def beautifulBinaryString(b):
    count, i = 0, 0
    while (i+3 <= len(b)):
        if b[i:i+3] == "010":
            count, i = count+1, i+3
        else: i += 1
    return count
\$\endgroup\$
  • \$\begingroup\$ I have some very strong reservations about performing two assignments on a single line unnecessarily (and lack of PEP8 compliance). Apart from that, very nice answer. \$\endgroup\$ – Konrad Rudolph Oct 2 '18 at 12:42
  • 1
    \$\begingroup\$ @KonradRudolph, OP explicitly prioritised concision, and I don't think that a multiple assignment crosses the line into golfing. But I take your point that it's not uncontroversial. \$\endgroup\$ – Peter Taylor Oct 2 '18 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.