Solution works for sample data but online judge gives errors?

Question

This is the problem I am trying to solve:

B: The Foxen's Treasure

There are N (1 ≤ N ≤ 4) Foxen guarding a certain valuable treasure, which you'd love to get your hands on. The problem is, the Foxen certainly aren't about to allow that - at least, not while they're awake.

Fortunately, through careful observation, you've seen that each Fox has a regular sleep cycle. In particular, the ith Fox stays awake for Ai (1 ≤ Ai ≤ 23) hours, then sleeps for Si (1 ≤ Si ≤ 23) hours, repeating this pattern indefinitely (2 ≤ Ai + Si ≤ 24). At the start of your treasure-nabbing attempt, the ith Fox is exactly Oi (0 ≤ Oi < Ai + Si) hours into its cycle.

There are T (1 ≤ T ≤ 20) scenarios as described above. For each one, you'd like to determine how soon all of the Foxen will be simultaneously asleep, allowing you to grab their treasure, or if this will simply never happen.

Input

Line 1: 1 integer, T
For each scenario:
    Line 1: 1 integer, N
    Next N lines: 3 integers, Ai, Si, and Oi, for i = 1..N

Output

For each scenario:
    Line 1: 1 integer, the minimum number of hours after the start to 
     wait until all of the Foxen are asleep during the same hour. If this
     will never happen, output the string "Foxen are too powerful" (without
     quotes) instead.

Sample Input

2
2
2 1 2
2 2 1
3
1 1 0
1 1 0
1 1 1

Sample Output

6
Foxen are too powerful

My Solution works as expected when I input the given sample case and get expected output. But when I submit the code to online judge it gives clipped error. Now there is no detail of the error which makes it difficult to find what the problem is.

Here is the solution which I have worked so far:

# ai is awake hours
# si is sleep hours.
# ai + si <= 24.

# False == sleep. True == awake.

datasets = int(raw_input());
foxen = [];
number_of_foxen = 0;
foxes = [];

class fox:
    def __init__(self, a, s, i):
        self.awake = a;
        self.sleep = s;
        self.current = i;
    awake = 0;
    sleep = 0;
    current = 0;

    def next(self):
        if ( self.sleep + self.awake-1 > self.current ) :
            self.current = self.current+1;
        else:
            self.current = 0;
        return self.current;

    def check(self):
        if(self.current>=self.awake):
            return False;
        return True;

    def printdata(self):
        print "awake="+str(self.awake)+" sleep="+str(self.sleep)+" current="+str(self.current);
        #return "awake="+str(self.awake)+" sleep="+str(self.sleep)+" current="+str(self.current);


for i in range(0, datasets):
    number_of_foxen = int(raw_input());

    for j in range(0, number_of_foxen):
        foxen.append(raw_input());
        x = foxen[j].split();
        a = fox(int(x[0]), int(x[1]), int(x[2]));
        foxes.append(a);

    solution = False;
    for j in range(0, 48):
        #print "hour number = " + str(j);

        #for k in range(0, len(foxes)):
            #print "fox number="+ str(k)+" "+ foxes[k].printdata()+str(foxes[k].check());

        count = 0 ;
        for k in range(0, len(foxes)):
            if(foxes[k].check()==False):
                count+=1;
                #print "count = "+str(count);
                #print len(foxes);
            if( (int(count) == int(len(foxes))) and (solution == False)  ):
                #print "this runs now *************";
                solution = True;
                number = j;

        for k in range(0, len(foxes)):
            foxes[k].next();

    if(solution==True):
        print number;
    else:
        print "Foxen are too powerful";

    #print "Foxen are too powerful";
    foxen = [];
    number_of_foxen = 0;
    foxes = [];

Answer 1

The biggest problem with your code is that it is unreadable. Indeed, it looks like it was written with little concept of Python's strengths. Here is my suggestion:

#!/usr/bin/env python3

"""
The Foxen's Treasure puzzle from http://wcipeg.com/problem/acmtryouts1b
"""

from sys import stdin
from itertools import cycle

from euclid import lcm

debug = True  # set to False before submission to mechanical judge

class Fox:
    """A Fox cointains its defining integers and other derived
       bindings such as its cycle and schedule."""
    def __init__(self, trio):
        (self.awake_count, self.sleep_count, self.skip_count) = trio
        self.cycle = 'a' * self.awake_count + 's' * self.sleep_count
        self.schedule = cycle(self.cycle)
        if debug: print('<Fox: {}> cycle {}'.format(trio, self.cycle))

        # handle skips by discarding the first elements
        for _ in range(self.skip_count):
            next(self.schedule)     


def find_all_sleeping(foxes):
    """Return an hour number if all foxes are sleeping at that hour."""
    # only examine the LCM of all fox periods. If not there it will never be.
    lcm_period = 1
    for fox in foxes:
        lcm_period = lcm(lcm_period, len(fox.cycle))

    for hour in range(lcm_period):
        states = [next(fox.schedule) for fox in foxes]
        if debug: print('{:2d} {}'.format(hour, ' '.join(states)))
        if 'a' not in states:
            return hour
    return None


def read_trials(fp):
    """Reads the entire input at once. Returns a list of trials.
       Each trial is a list of Fox."""
    trials = list()
    trial_count = int(fp.readline())
    for trial in range(trial_count):
        if debug: print('--Read trial {}'.format(trial))
        foxes = list()
        fox_count = int(fp.readline())
        for _ in range(fox_count):
            fox = Fox([int(x) for x in fp.readline().split()])
            foxes.append(fox)
        trials.append(foxes)
    return trials


for trial, foxes in enumerate(read_trials(stdin)):
    if debug: print('--Run trial {}'.format(trial))
    hour = find_all_sleeping(foxes)
    if hour is None:
        print('Foxen are too powerful')
    else:
        print(hour)

I suspect that the first concern is that it looks much longer than the OP; that is true, but if you take out the debugging code which shows how things are happening, and the docstrings that explain why it is doing things, it's actually a few line shorter than the OP.

The main loop of the OP is too long to understand without significant study, and a whole bunch of bad variable names makes that even harder. In contrast, there are places here where a value is given a name only to make the code more explicit about what an input line means. You'll find a number of

for _ in range(trial)

to show that the loop value is not used. This is a frequent idiom when dealing with fixed format input.

The Fox representation keeps the inner workings in the problem space. As noted in the exercise page, it makes more sense to look at things as a concurrence between sequences:

--Read trial 0
<Fox: [2, 1, 2]> cycle aas
<Fox: [2, 2, 1]> cycle aass

the offsets skip_count are not shown here, but they are clear in the trial run.

The input from the datafile is all kept inside read_trials() instead of scattered through the code. This confines the mess to one place rather than distributing it through the code. We know from the puzzle instructions that the datafile will not be large enough to care about. read_trials(fp) also takes a file-like object which allows it to read from an actual file, a StringIO buffer, or the standard input.

Once the Fox schedule generator is initialized, itertools.cycle will give an unending supply of the next letter in the sequence; it does the wrap-around for you.

It is worth noting that the primary data structure trials is a plain old list because it doesn't need anything more than that.

I've gotten a little weary of bad code being answered with worse code. Sure, this could be considered way more than the needs of an electronic judge where only the output matters. Contrariwise, I'm still puzzled by bits like (solution == False), a main loop that is 42 lines long and split between the top and bottom of the file, variables like i and j which convey no intent, the memory burden of False == awake (or did I mix them up?), dead code, no-op code, `range(0, n) and a whole bunch of magic numbers throughout.

Sure, you can code like the code doesn't matter, but if you are teaching yourself to code it is good to practice good practice. Yeah, you might never look at this piece of code again, but if you ain't gonna learn it now, then when?

In case you feel it a cheat to have imported lcm() there's no reason to write it a second time, so I referenced a homebrew package of which the relevant lines are:

def gcd(a, b):
    """Return the Greatest Common Divisor of a and b."""
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Return the Least Common Multiple of a and b."""
    return abs(a * b) // gcd(a, b)

Answer 2

Jorge was correct in his comment, there doesn't appear to be any problem with your algorithm other than the arbitrary 48 hour cuttoff.

However:

1) your print statements do not use the correct syntax for Python 3+. For example, your final print statement print "Foxen are too powerful"; must be changed to work in Python 3, try print ('Foxen are too powerful') instead.

2) I'm seeing some odd C/MatLab-like syntax as well, lines being ended by a semicolon, and double brackets surrounding conditions in your if statements. This probably isn't a problem, but depending on how picky the system you are submitting the answer to is, you may want to clean it up a little.

3) Definitely increase the cutoff time for your search. I'd recommend a reasonably large value, on the order of 10,000 hours, just to be sure that it won't be a factor.

I've taken the liberty of making all of the above changes so I'm posting the resultant code now:

# ai is awake hours
# si is sleep hours.
# ai + si <= 24.

# False == sleep. True == awake.

datasets = int(raw_input())
foxen = []
number_of_foxen = 0
foxes = []

class fox:
    def __init__(self, a, s, i):
        self.awake = a
        self.sleep = s
        self.current = i
    awake = 0
    sleep = 0
    current = 0

    def next(self):
        if ( self.sleep + self.awake-1 > self.current ): 
            self.current = self.current+1
        else:
            self.current = 0
        return self.current

    def check(self):
        if(self.current>=self.awake):
            return False
        return True

    def printdata(self):
        print ("awake="+str(self.awake)+" sleep="+str(self.sleep)+"     current="+str(self.current))
        #return ("awake="+str(self.awake)+" sleep="+str(self.sleep)+" current="+str(self.current))


for i in range(0, datasets):
    number_of_foxen = int(raw_input())

    for j in range(0, number_of_foxen):
        foxen.append(raw_input())
        x = foxen[j].split()
        a = fox(int(x[0]), int(x[1]), int(x[2]))
        foxes.append(a)

    solution = False
    for j in range(0, 10000):
        #print ("hour number = " + str(j))

        #for k in range(0, len(foxes)):
            #print ("fox number="+ str(k)+" "+ foxes[k].printdata()+str(foxes[k].check()))

        count = 0 
        for k in range(0, len(foxes)):
            if(foxes[k].check()==False):
                count+=1
                #print ("count = "+str(count))
                #print (len(foxes))
            if (int(count) == int(len(foxes)) and (solution == False)):
                #print ("this runs now *************")
                solution = True
                number = j

        for k in range(0, len(foxes)):
            foxes[k].next()

    if(solution == True):
        print (number)
    else:
        print ("Foxen are too powerful")

    #print ("Foxen are too powerful")
    foxen = []
    number_of_foxen = 0
    foxes = []

Enjoy and Good Luck!

Answer 3

Interesting problem, here's my code:

import sys

# Globals
debugLevel = 0
fileMode = True # True if loading data from a file.

# Constants
AWAKE = 0
ASLEEP = -1


def gcd(a, b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while b:      
        a, b = b, a % b
    return a

def lcm(a, b):
    """Return lowest common multiple."""
    return a * b // gcd(a, b)


def readData(f):
    ''' Read in the problem data and store in data structures
    '''

    numTrials = int(f.readline().strip())
    if debugLevel >= 4:
        print("Num trials: ", numTrials)

    trialData = []

    for _ in range(numTrials):
        numFoxen = int(f.readline().strip())

        allFoxenHoursInfo = []
        for _ in range(numFoxen):
            aFoxHoursInfo = f.readline().split()
            aFoxHoursInfo = list(map(int, aFoxHoursInfo))
            allFoxenHoursInfo.append(aFoxHoursInfo)

        trialData.append((numFoxen, allFoxenHoursInfo))

    if debugLevel >= 8:
        print("Trial data\n", trialData)

    return numTrials, trialData


def runTrials(trialData):
    '''
    Go through each lot of foxen, and their sleep/awake schedules and 
    See if there's a time that all of them will be asleep.
    '''
    global debugLevel

    for trial in trialData:
        numFoxen, allFoxenHoursInfo = trial 

        # Create a table of the status of each fox in each hour
        row = [AWAKE] * (numFoxen+1)
        row[0] = 0
        hoursTable = [row]

        # Cycle length for each fox is the number of hours they spend awake then asleep.
        cycleLength = [0] * (numFoxen)
        # This is the number of hours into the cycle each fox is at the start
        startingPosInCycle= [0] * (numFoxen)


        # Initialise the first row
        for fox in range(numFoxen):
            cycleLength[fox] = allFoxenHoursInfo[fox][0] + allFoxenHoursInfo[fox][1] # Time awake plus time asleep
            startingPosInCycle[fox] = allFoxenHoursInfo[fox][2]  # % cycleLength[fox]
            if startingPosInCycle[fox] >= allFoxenHoursInfo[fox][0]:
                hoursTable[0][fox+1] = ASLEEP

        if debugLevel >= 4:
            print("Initial table: ", hoursTable)


        # lcm = lowest common multiple and it's implemented above.  
        # For this problem, we only need to look at the lcm of all the cycle lengths for the foxen.
        numIterations = 1
        for fox in range(numFoxen):
            numIterations = lcm(numIterations, cycleLength[fox])

        # Go around a loop adding a new row to the table for each new hour containing the updated
        # statuses of each fox.
        for hourNum in range(1, numIterations):

            allFoxesSleeping = False

            # Update our hours table by creating a new row and calculating the status of each fox
            newRow = [AWAKE]  * (numFoxen+1)
            newRow[0] = hourNum
            for fox in range(numFoxen):
                currentPosInCycle = (startingPosInCycle[fox] + hourNum) % cycleLength[fox]
                if currentPosInCycle >= allFoxenHoursInfo[fox][0]:
                    newRow[fox+1] = ASLEEP
            hoursTable.append(newRow)

            if debugLevel >= 4:
                print("Hours table\n", hoursTable)

            # See if all foxen are sleeping, if they are, success
            numFoxesSleeping  = hoursTable[hourNum].count(ASLEEP)
            if numFoxesSleeping == numFoxen:
                allFoxesSleeping = True
                print(hourNum)
                break


        if not allFoxesSleeping:
            print('Foxen are too powerful')


def main():
    '''Reads, runs, and outputs problem specific data.'''


    # Initialisation
    #strDir = ".\\"
#    if fileMode:
#        dataSource = open(strDir + "DataFile.txt", 'r')   
#    else: 
    dataSource = sys.stdin


    # Read in the input data.
    numTrials, trialData = readData(dataSource)

    # Run each trial, outputting the result of that trial
    runTrials(trialData)


    sys.stdout.flush()


    # Cleanup
#    if fileMode:
#        dataSource.close()



if __name__ == '__main__':
    main()

Unfortunately, it does not pass the judge either. I have no idea why. I get this output:

Test case #1: WA [0.178s, 3628K] (0/1) (Details)
Your Output (clipped)

6
Foxen are too powe


Final score: 0/1 

Interesting problem. I have emailed the author, because there is an inconsistency in the problem definition and the sample input data. He says this: Oi (0 ≤ Oi < Ai + Si) but then gives 1 1 1 on the last line of sample input data. And 1 is not strictly less than 1+1.

So who knows what other data the judge might be using...

The bit at the bottom that is commented out re files, lets me work with files and an IPython console rather than a Python console and pasting the data in, which I find slow and annoying.

Also, it's a little strange I reckon to not be able to see the data the judge is using. Surely seeing the data you are working against would enable the problem to be run and debugged offline, then when it's going, a new online submit could be done.