Google CodeJam 2016 - Python Counting Sheep

Question

I decided to try some google codejam problems to get some more experience coding. The problem is at http://code.google.com/codejam/contest/6254486/dashboard, my solution is below. It gets the correct solution but would appreciate any tips on coding.

Problem

Bleatrix Trotter the sheep has devised a strategy that helps her fall asleep faster. First, she picks a number N. Then she starts naming N, 2 ×ばつ N, 3 ×ばつ N, and so on. Whenever she names a number, she thinks about all of the digits in that number. She keeps track of which digits (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) she has seen at least once so far as part of any number she has named. Once she has seen each of the ten digits at least once, she will fall asleep.

Bleatrix must start with N and must always name (i + 1) ×ばつ N directly after i ×ばつ N. For example, suppose that Bleatrix picks N = 1692. She would count as follows:

N = 1692. Now she has seen the digits 1, 2, 6, and 9. 2N = 3384. Now she has seen the digits 1, 2, 3, 4, 6, 8, and 9. 3N = 5076. Now she has seen all ten digits, and falls asleep. What is the last number that she will name before falling asleep? If she will count forever, print INSOMNIA instead.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a single integer N, the number Bleatrix has chosen.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the last number that Bleatrix will name before falling asleep, according to the rules described in the statement.

Code

import os
def getnumber(number,numberoftries):
 N = number
 digitlist = []
 print "new case number = " + str(number)
 for j in range(1,numberoftries):
 N = str(N)
 N.rstrip()
 digits = []
 for l in range(0,len(N)):
 if N[l] not in digits:
 digits.append(N[l])
 # print digits
 for l in range(0,len(digits)):
 k = digits[l]
 # Add digits to digitlist
 if k not in digitlist:
 digitlist.append(k)
 print digitlist
 # check if we have all digits
 count = 0
 for k in range (0,10):
 if str(k) in digitlist:
 count = count + 1
 if count == 10:
 print "count = 10"
 return str(N)
 else:
 N = number * (j+1)
 print "number = " + str(N)
 return "INSOMNIA"
numberoftries = 1000
path = '/home/username/GoogleCodeJam/'
inputfile = 'A-large-practice.in'
inputfilename = path + inputfile
outputfilename = path + 'largeoutput'
f = open(inputfilename, "r")
numberofcases = f.readline()
o = open(outputfilename,"w")
for i in range (1,int(numberofcases)+1):
 N = f.readline()
 N = int(N)
 result = getnumber(N,numberoftries)
 outputline = 'Case #' + str(i) + ': ' + str(result) + '\n'
 o.write(outputline)
o.close()

Answer 1

In general, it is difficult to follow the logic and the code is not readable.

First, here are some general things you can improve:

• N.rstrip() does not modify a string in place and returns a new string instead. Since you are not assigning the result to anything, it does nothing
• according to PEP8, you should put underscores between the words in variable and function names - number_of_tries vs numberoftries or digitlist vs digit_list, get_number() vs getnumber()
• following the previous note - N is not a good variable name
• remove unused import
• count = count + 1 can be rewritten as count += 1
• put the main logic of the program into if __name__ == '__main__':
• use print() function instead of a statement for Python 3.x compatibility
• use with context manager when opening file(s) - this will ensure it being properly and safely closed
• use os.path.join() to join the path components (okay, you now need to get your import os back :)
• define constants in upper case (PEP8 reference)
• use list comprehensions
• use .format() instead of string concatenation
• use built-in sum() function to for counting
• loop over the items directly instead of indexes

The code after applying the changes:

import os
NUMBER_OF_TRIES = 1000
BASE_DIRECTORY = '/home/username/GoogleCodeJam/'
INPUT_FILE_NAME = 'A-large-practice.in'
OUTPUT_FILE_NAME = 'largeoutput'
def get_number(number, number_of_tries):
 print("new case number = {number}".format(number=number))
 digit_list = []
 current_number = number
 for j in range(1, number_of_tries):
 number_as_string = str(current_number)
 digits = []
 for item in number_as_string:
 if item not in digits:
 digits.append(item)
 for digit in digits:
 if digit not in digit_list:
 digit_list.append(digit)
 count = sum(1 for k in range(0, 10) if str(k) in digit_list)
 if count == 10:
 print("count = 10")
 return number_as_string
 else:
 current_number = number * (j + 1)
 print("number = {number}".format(number=number))
 return "INSOMNIA"
if __name__ == '__main__':
 input_file_name = os.path.join(BASE_DIRECTORY, INPUT_FILE_NAME)
 output_file_name = os.path.join(BASE_DIRECTORY, OUTPUT_FILE_NAME)
 with open(input_file_name, "r") as input_file, open(output_file_name, "w") as output_file:
 number_of_cases = next(input_file)
 for case_number in range(1, int(number_of_cases) + 1):
 number = int(next(input_file))
 result = get_number(number, NUMBER_OF_TRIES)
 output_file.write('Case #{case_number}: {result}\n'.format(case_number=case_number, result=result))

---

Alternative Solution:

We can also improve on both the performance and readability if we would use sets - collecting the digits seen so far until the length of the set is 10 (collected all digits) or we reach the maximum number of tries:

def get_number(number, number_of_tries):
 digits = set([]) # keep track of all seen digits 
 current_number = number
 for j in range(1, number_of_tries):
 digits |= set(str(current_number)) # add new digits to the seen set
 if len(digits) == 10: # exit if collected all the digits
 return current_number 
 else:
 current_number = number * (j + 1)
 return "INSOMNIA"