10
\$\begingroup\$

I am trying to solve apparatus problem, paraphrased below.

There is an apparatus with n on/off switches with a one-to-one correspondence to n lights (but with an unknown permutation). We have several different photographs of the apparatus showing different configurations of the switches and lights. Are these photos sufficient to fully describe the device?

Input

First line contains two integers: n (the number of switches, 1 ≤ n ≤ 1000) and m (the number of photographs, 0 ≤ m ≤ 1000).

Each subsequent pair of lines describes the switches and the lights as a string of 1 (on) and 0 (off).

Output

Write the number of possible different wirings, modulo 1000003.

I have a solution but it takes longer than 2 seconds which is the time limit. I've tried to optimize my code for speed but can't get it within the 2 second limit.

import sys
import math

for line in sys.stdin:

    line = line.strip("\n").split(" ")
    numSwitches = int(line[0])
    numPics = int(line[1])

    wiring = {}
    inValid = False
    for i in range(numPics):
        if (inValid):
            break
        x = sys.stdin.readline().strip("\n")
        f_x = sys.stdin.readline().strip("\n")

        x_ones = 0
        f_x_ones = 0

        digit = 0
        for i in range(numSwitches):
            if f_x[i]=='1':
                digit += 2**(numSwitches-i-1)
                f_x_ones += 1

        for switch in range(numSwitches):
            if (x[switch]=='1'):
                x_ones += 1
                if not (switch in wiring.keys()):
                    wiring[switch] = digit
                else:
                    wiring[switch] &= digit

        if x_ones != f_x_ones:
            inValid = True
            break

    if not inValid:
        for i in wiring.values():
            if i==0:
                inValid = True
                break

    for possibilities in set(wiring.values()):
        frequency = wiring.values().count(possibilities)
        if frequency>1:
            oneBits = 0
            while (possibilities>0):
                oneBits += (possibilities%2==1)
                possibilities /= 2
            if oneBits < frequency:
                inValid = True
                break

    if not inValid:
        print math.factorial(numSwitches-numPics)%1000003
    else:
        print 0

I'm looking for suggestions of ways I should have approached the problem or input on how I can optimize my current code.

Note: Consider the following test case:

3 2
110
011
011
011

My code finds that is invalid in the following manner. First, upon encountering the first photograph (110, 011). The wiring dictionary gets assigned the following keys and values:

wiring[0] = 011
wiring[1] = 011

This means that the first and second switch can light up either the second or third lights. Upon encountering the second photograph (011, 011). wiring is updated as follows:

wiring[1] = 011 & 011 = 011
wiring[2] = 011

Now observe that the state of wiring indicates that all three switches can light up either the second and third lights. This is an inconsistency since 3 switches have to light up three lights, here we have three switches lighting up 2 lights.

\$\endgroup\$
  • \$\begingroup\$ I'm probably reading this wrong, but does this work as intended? It's just that bold "inconsistency" to me reads as "doesn't run as intended". Otherwise welcome to CR, hope you get some nice answers! \$\endgroup\$ – Peilonrayz Nov 22 '15 at 23:16
  • \$\begingroup\$ Which version of Python do you use ? How do you call your script ? \$\endgroup\$ – SylvainD Nov 23 '15 at 15:03
  • \$\begingroup\$ @Ragnar Thanks for the additional explanation. This didn't work for me when I tried. I'll try again asap. \$\endgroup\$ – SylvainD Nov 23 '15 at 16:02
  • \$\begingroup\$ I don't know if it speeds up, but you can also test the opposite bitmask condition: the input 110 011 also means that light 3 is turned off by switch 1, so you can infer an input 001 100 to your logic. In this way (you should better test) you can probably cut off your inconsistency test. \$\endgroup\$ – N74 Nov 24 '15 at 9:23
  • 1
    \$\begingroup\$ (not sure that asking for solving a challenge is ontopic here, but well...). This problem doesn't seem clear (I have seen a different version much clearer; descriptions should be clear to allow focus on the implementation rather than on understanding what is expected). The main goal of this kind of programming challenges, where the speed matters, is not finding the right outputs, but doing it quickly enough. Iterating through all the cases is certainly not the right way through. You have to think carefully about the problem and come up with an algorithm minimising the number of iterations. \$\endgroup\$ – varocarbas Nov 25 '15 at 11:29
10
\$\begingroup\$

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 things 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 factorial(num_switches - num_photos) % 1000003


if __name__ == "__main__":
    print(wiring_possibilities())
\$\endgroup\$
  • \$\begingroup\$ @Ragnar As suggested since my first comment, a trying-everything approach is certainly not what this problem is expecting. Even in case that you would be able to notably improve the performance and meet the target time (very unlikely scenario if the problem was properly created; although well... after reading a so unclear description I don't trust too much in the creators), it would be somehow against what is expected and wouldn't help you to learn how to face this kind of situations (you will fail the next time because of the same reason). \$\endgroup\$ – varocarbas Nov 26 '15 at 8:29
  • \$\begingroup\$ Mathias, my message was addressed to the OP as a continuation of my comments above. You let very clear your position in the disclaimer you are mentioning (which I read and understood before writing my comment :)). \$\endgroup\$ – varocarbas Nov 26 '15 at 8:37
  • \$\begingroup\$ @varocarbas OK. Wanted to be extra clear, just in case. \$\endgroup\$ – Mathias Ettinger Nov 26 '15 at 8: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.