This code does exactly what I want it to do, but I wonder if there is a simpler solution to this problem. I'm also wondering if there is a different solution to this problem that I didn't catch.
The idea is to find all the values of n via n = 6a + 9b + 20c. I created an ascending list with no repeating values. The program runs pretty slow, but I guess that isn't too surprising since I am running 3 simultaneous loops, checking vs an if, creating a list, sorting the list, then minimizing the list.
Considering the problem set, I could use a smaller value than 150. I ran it with 50 as well, but it is still slow.
Code:
nList = []
for a in range(0,150):
for b in range(0,150):
for c in range(0,150):
n = 6*a + 9*b + 20*c
if n < 150:
nList.append(n)
nList.sort()
nList = list(set(nList))
print nList
edit to add:
ldo, math ftl?
Code:
nList = []
for a in range(0,10):
for b in range(0,6):
for c in range(0,3):
n = 6*a + 9*b + 20*c
if n < 50:
nList.append(n)
nList.sort()
nList = list(set(nList))
print nList
Last edited by daveT; 06-20-2011 at 08:05 PM.
Reason: now, it's lightening fast.
why are you sorting and uniq'ing during every iteration?
I have to check if n, n + 1,... n+5 is possible. According to the theorem, once I have that, then all n + (inf) is possible. I know that the highest possible number n that can't work is 37.
The plan (for now) is to check all numbers in the list against n, n + 1,... n+5 (which probably creates another for loop somewhere else), then print out 37.
that's all gobbledegook to me but even if you really, really need to call
Code:
nList = list(set(nList))
on every iteration, which I'm sure you don't, the expensive sort() operation in the previous line changes absolutely nothing because set() unsorts the list. But really what you should do is make nList a set from the start and call nlist.add(n) instead of your 3 lines.
that's all gobbledegook to me but even if you really, really need to call
Code:
nList = list(set(nList))
on every iteration, which I'm sure you don't, the expensive sort() operation in the previous line changes absolutely nothing because set() unsorts the list. But really what you should do is make nList a set from the start and call nlist.add(n) instead of your 3 lines.
How hard is it for me to highlight and format >> comment to see what happens without sort()?
I have to check if n, n + 1,... n+5 is possible. According to the theorem, once I have that, then all n + (inf) is possible. I know that the highest possible number n that can't work is 37.
The plan (for now) is to check all numbers in the list against n, n + 1,... n+5 (which probably creates another for loop somewhere else), then print out 37.
I'm currently working through the OCW Intro to Programming course too. I just did the McNugget problem last week. I'm obviously a Python n00b as well, so take my advice with a grain of salt, but what you're trying to do with lists seems needlessly complicated.
I solved this one pretty easily just brute-forcing the possible combinations and using if/else statements to set the appropriate flags and keep track of a counting variable until I found 6 valid combos in a row.
The code is in a spoiler below in case you don't want to see before you solve it for yourself :
Spoiler:
(43 is also the correct answer BTW, not 37)
Code:
# MIT OpenCourseWare problem 2-2
# Find the largest value of n such that 6a + 9b + 20c = n
# has no solution where a, b and c are all positive integers
n = 1
consecPasses = 0
validFound = False
while consecPasses < 6:
for a in range(0, 1 + n/6):
for b in range(0, 1 + n/9):
for c in range(0, 1 + n/20):
if n == 6*a + 9*b + 20*c:
print(str(n) + " = 6*" + str(a) + " + 9*" + str(b)
+ " + 20*" + str(c))
validFound = True
if validFound:
consecPasses += 1
else:
print("There is no valid solution for n = " + str(n))
consecPasses = 0
validFound = False
n += 1
print("Largest number of McNuggets that cannot be bought"
" in exact quantity: ") + str(n - 7)
I have a solution, though it probably isn't as correct as yours. This is something I threw together over about 4 hours (which is extremely fast for me). I got a little to married to the list idea, but I'll work on a different solution at a later date.
Spoiler:
Code:
nList = []
noValue = []
for a in range(12):
for b in range(9):
for c in range(4):
n = 6*a + 9*b + 20*c
if n < 70:
nList.append(n)
for checker in range(70):
noValue.append(checker)
list(set(nList))
list(set(noValue))
nextAnswer = list(set(noValue).difference(set(nList)))
print 'the most chicken mcNuggets you can buy is', nextAnswer[-1]
You should very, very rarely need to construct two data structures like this. You definitely shouldn't do it multiple times. In your case, why wouldn't you just make nList and noValue set's to start?
In fact: I think you can just leave them as sets and then call max(yourSet) to get the largest number.
Edit: The reason I'm pointing that out is that learning to use the right data structure and avoiding lots of unnecessary conversions between data structures is pretty important. Much more important than trying to get code down to a small size or to figure out the very best algorithm to use.
Been trying to learn python for a few months on and off in the free time that I have (very little). This week it finally paid off as I could write a script that eases some of the work I was doing.
Even though it is probably a horrible piece of code from a programmers' view, I was still kinda proud. It's 8 times a similar thing after each other, but each one is dependent on the step before it, so I split it into 8 codeblocks. Is there a way to do that easier?
Rough example: I have x, out of that comes x1 x2 and x3, then I do roughly the same with those and get y11 y12 y13, y21 y22 and y23, and y31/y32/y33.
Is that possible to do in one codeblock without using so many for and if blocks that I tab out of the right side of my screen?
Attached the script btw, some variable names might be weird but they make sense if you know what the subject is about. It basically gets the relevant information out of (in this case) 8 documents and pastes it exactly in the format I want in a new file.
Also, first time dabbling in regexes so it took me a while to figure out all those to get exactly what I wanted.
Spoiler:
Code:
#! /usr/local/bin/python
import re
import os
inputfile=''
path='C:\\blah\\blah\\'
filelisting=os.listdir(path)
for file in filelisting:
if file[-3:] == 'dot':
input=open(path+file)
inputfile=inputfile+input.read()
result=open("C:\\blah\\blah\\results.txt", "w")
result.write('digraph G {\n')
templinklistresult=open("C:\\blah\\blah\\tempresults.txt", "w")
rank1parents=[] #store all parents for later use
rank2parents=[]
rank3parents=[]
rank4parents=[]
rank5parents=[]
rank6parents=[]
rank7parents=[]
rank8parents=[]
ideal='000101101110101101' #first find ideotype
regex = r'([01]+)\s->\s('+str(ideal)+')(.+)' #make regex with ideotype
ideotypelinks=re.findall(regex,inputfile) #do the search
ideoparents=[]
for x in xrange(0,len(ideotypelinks)): #go through all found ideoparents
if ideotypelinks[x][0] not in ideoparents: #if-block to remove duplicates
ideoparents.append(ideotypelinks[x][0])
templinklistresult.write(ideotypelinks[x][0]+' -> '+ideotypelinks[x][1]+ideotypelinks[x][2]+'\n') #write links to file
rank1parents.append(ideotypelinks[x][0])
templinklistresult.write('\n2nd rank\n') #next generation (one up)
ideoparents1=[]
parents=[]
for x in xrange(0,len(ideoparents)):
searchword=r'([01]+)\s->\s('+ideoparents[x]+')(.+)' #make regex for each parent
linklist=re.findall(searchword,inputfile) #make the list of links/parent
tempparentslist=[]
for x in xrange(0,len(linklist)):
if linklist[x][0] not in parents: #if-block to store parents for
parents.append(linklist[x][0]) #next generation search start
if linklist[x][0] not in tempparentslist: #if-block to remove dups
tempparentslist.append(linklist[x][0])
templinklistresult.write(linklist[x][0]) #write all three parts of link
templinklistresult.write(' -> ') #to the file with a newline each
templinklistresult.write(linklist[x][1]) #time
templinklistresult.write(linklist[x][2]+'\n')
rank2parents.append(linklist[x][0])
templinklistresult.write('\n')
templinklistresult.write('3rd rank\n') #next generation (one up)
parentslist=[]
for x in xrange(0,len(parents)):
searchword=r'([01]+)\s->\s('+parents[x]+')(.+)' #make regex for each parent
linklist=re.findall(searchword,inputfile) #make the list of links/parent
tempparentslist=[]
for x in xrange(0,len(linklist)):
if linklist[x][0] not in parentslist: #if-block to store parents for
parentslist.append(linklist[x][0]) #next generation search start
if linklist[x][0] not in tempparentslist: #if-block to remove dups
tempparentslist.append(linklist[x][0])
templinklistresult.write(linklist[x][0]) #write all three parts of link
templinklistresult.write(' -> ') #to the file with a newline each
templinklistresult.write(linklist[x][1]) #time
templinklistresult.write(linklist[x][2]+'\n')
rank3parents.append(linklist[x][0])
templinklistresult.write('\n')
templinklistresult.write('4th rank\n') #next generation (one up)
parents=[]
for x in xrange(0,len(parentslist)):
searchword=r'([01]+)\s->\s('+parentslist[x]+')(.+)' #make regex for each parent
linklist=re.findall(searchword,inputfile) #make the list of links/parent
tempparentslist=[]
for x in xrange(0,len(linklist)):
if linklist[x][0] not in parents: #if-block to store parents for
parents.append(linklist[x][0]) #next generation search start
if linklist[x][0] not in tempparentslist: #if-block to remove dups
tempparentslist.append(linklist[x][0])
templinklistresult.write(linklist[x][0]) #write all three parts of link
templinklistresult.write(' -> ') #to the file with a newline each
templinklistresult.write(linklist[x][1]) #time
templinklistresult.write(linklist[x][2]+'\n')
rank4parents.append(linklist[x][0])
templinklistresult.write('\n')
templinklistresult.write('5th rank\n') #next generation (one up)
parentslist=[]
for x in xrange(0,len(parents)):
searchword=r'([01]+)\s->\s('+parents[x]+')(.+)' #make regex for each parent
linklist=re.findall(searchword,inputfile) #make the list of links/parent
tempparentslist=[]
for x in xrange(0,len(linklist)):
if linklist[x][0] not in parentslist: #if-block to store parents for
parentslist.append(linklist[x][0]) #next generation search start
if linklist[x][0] not in tempparentslist: #if-block to remove dups
tempparentslist.append(linklist[x][0])
templinklistresult.write(linklist[x][0]) #write all three parts of link
templinklistresult.write(' -> ') #to the file with a newline each
templinklistresult.write(linklist[x][1]) #time
templinklistresult.write(linklist[x][2]+'\n')
rank5parents.append(linklist[x][0])
templinklistresult.write('\n')
templinklistresult.write('6th rank\n') #next generation (one up)
parents=[]
for x in xrange(0,len(parentslist)):
searchword=r'([01]+)\s->\s('+parentslist[x]+')(.+)' #make regex for each parent
linklist=re.findall(searchword,inputfile) #make the list of links/parent
tempparentslist=[]
for x in xrange(0,len(linklist)):
if linklist[x][0] not in parents: #if-block to store parents for
parents.append(linklist[x][0]) #next generation search start
if linklist[x][0] not in tempparentslist: #if-block to remove dups
tempparentslist.append(linklist[x][0])
templinklistresult.write(linklist[x][0]) #write all three parts of link
templinklistresult.write(' -> ') #to the file with a newline each
templinklistresult.write(linklist[x][1]) #time
templinklistresult.write(linklist[x][2]+'\n')
rank6parents.append(linklist[x][0])
templinklistresult.write('\n')
templinklistresult.write('7th rank\n') #next generation (one up)
parentslist=[]
for x in xrange(0,len(parents)):
searchword=r'([01]+)\s->\s('+parents[x]+')(.+)' #make regex for each parent
linklist=re.findall(searchword,inputfile) #make the list of links/parent
tempparentslist=[]
for x in xrange(0,len(linklist)):
if linklist[x][0] not in parentslist: #if-block to store parents for
parentslist.append(linklist[x][0]) #next generation search start
if linklist[x][0] not in tempparentslist: #if-block to remove dups
tempparentslist.append(linklist[x][0])
templinklistresult.write(linklist[x][0]) #write all three parts of link
templinklistresult.write(' -> ') #to the file with a newline each
templinklistresult.write(linklist[x][1]) #time
templinklistresult.write(linklist[x][2]+'\n')
rank7parents.append(linklist[x][0])
templinklistresult.write('\n')
templinklistresult.write('8th rank\n') #next generation (one up)
parents=[]
for x in xrange(0,len(parentslist)):
searchword=r'([01]+)\s->\s('+parentslist[x]+')(.+)' #make regex for each parent
linklist=re.findall(searchword,inputfile) #make the list of links/parent
tempparentslist=[]
for x in xrange(0,len(linklist)):
if linklist[x][0] not in parents: #if-block to store parents for
parents.append(linklist[x][0]) #next generation search start
if linklist[x][0] not in tempparentslist: #if-block to remove dups
tempparentslist.append(linklist[x][0])
templinklistresult.write(linklist[x][0]) #write all three parts of link
templinklistresult.write(' -> ') #to the file with a newline each
templinklistresult.write(linklist[x][1]) #time
templinklistresult.write(linklist[x][2]+'\n')
rank8parents.append(linklist[x][0])
templinklistresult.write('\n')
allparentslist=[] #to not have any duplicates in parentlist
if len(rank8parents) != 0:
result.write('''{
rank = same;\n\t\t''')
for x in xrange(0,len(rank8parents)):
if rank8parents[x] not in allparentslist:
allparentslist.append(rank8parents[x])
searchword=rank8parents[x]+'[^;]*;' #everything up to final /table end
table=re.search(searchword, inputfile)
result.write(table.group()+'\n\t\t')
if len(rank8parents) != 0:
result.write('''}\n\t''')
if len(rank7parents) != 0:
result.write('''{
rank = same;\n\t\t''')
for x in xrange(0,len(rank7parents)):
if rank7parents[x] not in allparentslist:
allparentslist.append(rank7parents[x])
searchword=rank7parents[x]+'[^;]*;' #everything up to final /table end
table=re.search(searchword, inputfile)
result.write(table.group()+'\n\t\t')
result.write('''}
''')
if len(rank6parents) != 0:
result.write('''{
rank = same;\n\t\t''')
for x in xrange(0,len(rank6parents)):
if rank6parents[x] not in allparentslist:
allparentslist.append(rank6parents[x])
searchword=rank6parents[x]+'[^;]*;' #everything up to final /table end
table=re.search(searchword, inputfile)
result.write(table.group()+'\n\t\t')
result.write('''}
''')
if len(rank5parents) != 0:
result.write('''{
rank = same;\n\t\t''')
for x in xrange(0,len(rank5parents)):
if rank5parents[x] not in allparentslist:
allparentslist.append(rank5parents[x])
searchword=rank5parents[x]+'[^;]*;' #everything up to final /table end
table=re.search(searchword, inputfile)
result.write(table.group()+'\n\t\t')
result.write('''}
''')
if len(rank4parents) != 0:
result.write('''{
rank = same;\n\t\t''')
for x in xrange(0,len(rank4parents)):
if rank4parents[x] not in allparentslist:
allparentslist.append(rank4parents[x])
searchword=rank4parents[x]+'[^;]*;' #everything up to final /table end
table=re.search(searchword, inputfile)
result.write(table.group()+'\n\t\t')
result.write('''}
''')
if len(rank3parents) != 0:
result.write('''{
rank = same;\n\t\t''')
for x in xrange(0,len(rank3parents)):
if rank3parents[x] not in allparentslist:
allparentslist.append(rank3parents[x])
searchword=rank3parents[x]+'[^;]*;' #everything up to final /table end
table=re.search(searchword, inputfile)
result.write(table.group()+'\n\t\t')
result.write('''}
''')
if len(rank2parents) != 0:
result.write('''{
rank = same;\n\t\t''')
for x in xrange(0,len(rank2parents)):
if rank2parents[x] not in allparentslist:
allparentslist.append(rank2parents[x])
searchword=rank2parents[x]+'[^;]*;' #everything up to final /table end
table=re.search(searchword, inputfile)
result.write(table.group()+'\n\t\t')
result.write('''}
''')
if len(rank1parents) != 0:
result.write('''{
rank = same;\n\t\t''')
for x in xrange(0,len(rank1parents)):
if rank1parents[x] not in allparentslist:
allparentslist.append(rank1parents[x])
searchword=rank1parents[x]+'[^;]*;' #everything up to final /table end
table=re.search(searchword, inputfile)
result.write(table.group()+'\n\t\t')
result.write('''}
''')
result.write('''{
rank = same;\n\t\t''')
#paste ideotype table in there
searchword=ideal+'[^;]*;'
table=re.search(searchword, inputfile)
result.write(table.group()+'\n\t\t')
result.write('''Schedulename\n\t\t[shape=egg,fillcolor=gray20,fontcolor=white,fontsize=18,style=filled,label="all"];\n\t}''')
result.write('\n')
templinklistresult.close()
templinklistresult=open("C:\\blah\\blah\\tempresults.txt", "r")
for line in templinklistresult:
if len(line) >= 10:
result.write(line)
result.write("}")
You should very, very rarely need to construct two data structures like this. You definitely shouldn't do it multiple times. In your case, why wouldn't you just make nList and noValue set's to start?
In fact: I think you can just leave them as sets and then call max(yourSet) to get the largest number.
Edit: The reason I'm pointing that out is that learning to use the right data structure and avoiding lots of unnecessary conversions between data structures is pretty important. Much more important than trying to get code down to a small size or to figure out the very best algorithm to use.
Okay, I'll look all this up.
Slick Strawberry: The reason we were using spoilers is so we don't show off the answers to the homework we are doing.
I'm using a spoiler because a spoiler gets a scrollbar if the script is too long, don't want my posts to be extremely long and I don't really know a good other way to show off my code.
You can also use the php tag to get some syntax highlighting. It isn't perfect because it as it is geared towards php, but it does a decent job with any c-style language.
Two Plus Two
Linear Mode
