Skip to main content
Commonmark migration
Source Link

#Reading data from standard input

Reading data from standard input

#Converting back and forth between integers and their binary representation

Converting back and forth between integers and their binary representation

#Use functions

Use functions

#collections

collections

#PEP8

PEP8

#EAFP

EAFP

#Putting it all together

Putting it all together

#Reading data from standard input

#Converting back and forth between integers and their binary representation

#Use functions

#collections

#PEP8

#EAFP

#Putting it all together

Reading data from standard input

Converting back and forth between integers and their binary representation

Use functions

collections

PEP8

EAFP

Putting it all together

deleted 98 characters in body
Source Link

I had trouble running your script from both IDLE and windows command prompt. Neither of them were good at handling sys.stdin as a file. But we can improve thingthings by using the builtin input (raw_input in Python 2) since we just want to read lines one by one.

            if not (switch in wiring.keys()):
                wiring[switch] = digit
            else:
                wiring[switch] &= digit
            if switch in wiring:
                wiring[switch] &= digit
            else:
                wiring[switch] = digit
            try:
                wiring[switch] &= digit
            except KeyError:
                wiring[switch] = digit
from math import factorial
from collections import Counter


def parse_photo(wiring):
    switches = input()
    lights = input()

    if switches.count('1') != lights.count(1):
        return False # invalid data

    # Convert binary value to integer
    lights_value = int(lights, 2)

    for switch, switch_value in enumerate(switches):
        if switch_value == "1":
            try:
                wiring[switch] &= lights_value
            except KeyError:
                wiring[switch] = lights_value

    return True


def wiring_possibilities():
    wiring = {}
    num_switches, num_photos = map(int, input().split())

    for _ in range(num_photos):
        if not parse_photo(wiring):
            return 0

    frequencies = Counter(wiring.values())
    if 0 in frequencies:
        # Same as if 0 in wiring.values()
        return 0

    for possibility, frequency in frequencies.items():
        switched_on_bits = bin(possibility).count('1')
        if switched_on_bits < frequency:
            return 0

    return math.factorial(num_switches - num_photos)%1000003 % 1000003


if __name__ == "__main__":
    print(wiring_possibilities())

I had trouble running your script from both IDLE and windows command prompt. Neither of them were good at handling sys.stdin as a file. But we can improve thing by using the builtin input (raw_input in Python 2) since we just want to read lines one by one.

            if not (switch in wiring.keys()):
                wiring[switch] = digit
            else:
                wiring[switch] &= digit
            if switch in wiring:
                wiring[switch] &= digit
            else:
                wiring[switch] = digit
            try:
                wiring[switch] &= digit
            except KeyError:
                wiring[switch] = digit
from math import factorial
from collections import Counter


def parse_photo(wiring):
    switches = input()
    lights = input()

    if switches.count('1') != lights.count(1):
        return False # invalid data

    # Convert binary value to integer
    lights_value = int(lights, 2)

    for switch, switch_value in enumerate(switches):
        if switch_value == "1":
            try:
                wiring[switch] &= lights_value
            except KeyError:
                wiring[switch] = lights_value

    return True


def wiring_possibilities():
    wiring = {}
    num_switches, num_photos = map(int, input().split())

    for _ in range(num_photos):
        if not parse_photo(wiring):
            return 0

    frequencies = Counter(wiring.values())
    if 0 in frequencies:
        # Same as if 0 in wiring.values()
        return 0

    for possibility, frequency in frequencies.items():
        switched_on_bits = bin(possibility).count('1')
        if switched_on_bits < frequency:
            return 0

    return math.factorial(num_switches - num_photos)%1000003


if __name__ == "__main__":
    print(wiring_possibilities())

I had trouble running your script from both IDLE and windows command prompt. Neither of them were good at handling sys.stdin as a file. But we can improve things by using the builtin input (raw_input in Python 2) since we just want to read lines one by one.

    if not (switch in wiring.keys()):
        wiring[switch] = digit
    else:
        wiring[switch] &= digit
    if switch in wiring:
        wiring[switch] &= digit
    else:
        wiring[switch] = digit
    try:
        wiring[switch] &= digit
    except KeyError:
        wiring[switch] = digit
from math import factorial
from collections import Counter


def parse_photo(wiring):
    switches = input()
    lights = input()

    if switches.count('1') != lights.count(1):
        return False # invalid data

    # Convert binary value to integer
    lights_value = int(lights, 2)

    for switch, switch_value in enumerate(switches):
        if switch_value == "1":
            try:
                wiring[switch] &= lights_value
            except KeyError:
                wiring[switch] = lights_value

    return True


def wiring_possibilities():
    wiring = {}
    num_switches, num_photos = map(int, input().split())

    for _ in range(num_photos):
        if not parse_photo(wiring):
            return 0

    frequencies = Counter(wiring.values())
    if 0 in frequencies:
        # Same as if 0 in wiring.values()
        return 0

    for possibility, frequency in frequencies.items():
        switched_on_bits = bin(possibility).count('1')
        if switched_on_bits < frequency:
            return 0

    return factorial(num_switches - num_photos) % 1000003


if __name__ == "__main__":
    print(wiring_possibilities())
Source Link

Disclaimer: I won't try and provide a different algorithm to improve the time complexity of the approach. Instead I’ll rather focus on introducing python constructs that will cleanup the code and may help gain speed a bit.

#Reading data from standard input

I had trouble running your script from both IDLE and windows command prompt. Neither of them were good at handling sys.stdin as a file. But we can improve thing by using the builtin input (raw_input in Python 2) since we just want to read lines one by one.

#Converting back and forth between integers and their binary representation

One of the way to improve your computation of oneBite would be to use the divmod builtin. But it is even more easier when using bin and counting the number of '1' in the returned string.

Same when computing digit: the int builtin accept a second argument which is the base in which the number is represented.

#Use functions

You could make the code easier to read and understand by using functions: one to parse two lines (one photo) and one to iterate over the whole set of photos and interpret the results.

Functions will also allow you to import your file into an interactive session and test things more easily. If you want to have code at the top-level to be run when invoking your script from the command line, it is recommended to put it under an if __name__ == "__main__" clause.

#collections

The last part of your code count the frequency for a certain possibility in a bizarre way. Time for you to learn about collections.Counter.

#PEP8

  • Use snake_case instead of camelCase for your variable names.
  • Use spaces around most of your operators (frequency > 1, possibilities%2 == 1, possibilities > 0…)
  • Remove parenthesis around your tests

#EAFP

While

            if not (switch in wiring.keys()):
                wiring[switch] = digit
            else:
                wiring[switch] &= digit

is correct, I would first write it

            if switch in wiring:
                wiring[switch] &= digit
            else:
                wiring[switch] = digit

for readability (and less computation) but then change it to

            try:
                wiring[switch] &= digit
            except KeyError:
                wiring[switch] = digit

It is not necessarily faster in this case (it is when failures are much less than success) but I find it clearer.

#Putting it all together

In Python 2 use raw_input, xrange and itervalues instead of input, range and values.

from math import factorial
from collections import Counter


def parse_photo(wiring):
    switches = input()
    lights = input()

    if switches.count('1') != lights.count(1):
        return False # invalid data

    # Convert binary value to integer
    lights_value = int(lights, 2)

    for switch, switch_value in enumerate(switches):
        if switch_value == "1":
            try:
                wiring[switch] &= lights_value
            except KeyError:
                wiring[switch] = lights_value

    return True


def wiring_possibilities():
    wiring = {}
    num_switches, num_photos = map(int, input().split())

    for _ in range(num_photos):
        if not parse_photo(wiring):
            return 0

    frequencies = Counter(wiring.values())
    if 0 in frequencies:
        # Same as if 0 in wiring.values()
        return 0

    for possibility, frequency in frequencies.items():
        switched_on_bits = bin(possibility).count('1')
        if switched_on_bits < frequency:
            return 0

    return math.factorial(num_switches - num_photos)%1000003


if __name__ == "__main__":
    print(wiring_possibilities())