Problem 23

For questions about problems on the Project Euler web site. No spoilers. Please include the question number in the subject line of your post.

Problem 23

Postby themightydud » Mon May 12, 2014 2:20 am

I looked up the answer because I thought i was close, and it turns out that my number [redacted by micseydel] greater than the answer. I can't figure out why.
Here is my code:
Code: Select all
from time import sleep
from time import clock
import math


def getDivisors(x):
    divList = []
    y = 1
    while y <= math.sqrt(x):
        if x % y == 0:
            divList.append(y)
            if x/y != y:
            divList.append(int(x / y))
        y += 1
    divList.remove(x)
    return divList

def sumDiv(num):
   div = getDivisors(num)
   add = 0
   for x in div:
      add+=x
   return add

start = clock()
abundantNums = []
for x in range(1,28123):
   if sumDiv(x) > x:
      print x,sumDiv(x)
      sleep(0)
      abundantNums.append(x)
print "abundant nums created",len(abundantNums)

all_sums = set()
last = False
for y in range(len(abundantNums)):
   for z in range(y+1,len(abundantNums)):
      temp = abundantNums[y]+abundantNums[z]
      if temp < 28123 and temp not in all_sums:
         all_sums.add(temp)
   percent = int((float(y)/(len(abundantNums)-1)*100))
   if percent%10 != 0: last = True
   if percent%10 == 0 and last is True:
      print str(percent)+"%"
      last = False

not_sum = 0

lstart = 0
all_nums = [x for x in range(1,28123)]

for z in all_sums:
   all_nums.remove(z)


print "ANSWER: "+str(sum(all_nums))
print clock()-start

#ANSWER:
#TIME:
Last edited by micseydel on Tue May 13, 2014 5:40 am, edited 2 times in total.
Reason: First post lock.
themightydud
 
Posts: 1
Joined: Mon May 12, 2014 2:18 am

Re: Problem 23

Postby micseydel » Tue May 13, 2014 5:39 am

Hello and welcome to the forum!

So first off, that code is unnecessarily messy. When you post code and ask others to read it, you should post the most absolutely polished code you can come up with. You have variables that don't do anything, and all that percentage output is just noise. I can appreciate it during development, when things are too slow, but yeah, less is more here.

Here is about 95% way through cleaning up your code so that I could read it more comfortably
Code: Select all
import math

BOUND 
= 28123

def getDivisors
(x):
    divList = []
    y = 1
    while y 
<= math.sqrt(x):
        if x % y == 0:
            divList.append(y)
            if x / y != y:
              divList.append(int(/ y))
        y += 1
    divList
.remove(x)
    return divList

def getAbundantNums
(bound):
    return [x for x in range(1, bound) if sum(getDivisors(x)) > x]

def main():
    abundantNums = getAbundantNums(BOUND)

    all_sums = set()
    for y in range(len(abundantNums)):
        for z in range(+ 1, len(abundantNums)):
            two_sum = abundantNums[y] + abundantNums[z]
            if two_sum < BOUND and two_sum not in all_sums:
                all_sums.add(two_sum)

    answer = sum(x for x in xrange(BOUND) if x not in all_sums)
    print "answer: ", answer

if __name__ 
== "__main__":
  main()

Doing this accidentally made it faster, which was neat, but not too important.

I took one more step, which accidentally (again) solved the problem. I re-wrote the nested for loops to use enumerate on the outside, and islice on the inside. In doing so, I eliminated an off-by-one error.

Kudos though on a generally good solution, even though it could have been tightened up. It was substantially faster than my problem 23 solution I wrote many years ago. On my machine, my solution takes 37 seconds whereas yours, as I've posted, takes just over 5. Very cool.

Note: we don't want spoilers here, which yours isn't, but please don't post the solution once you get it. In fact, I'm going to edit your post to remove the exact number you mention it being off by :)
Join the #python-forum IRC channel on irc.freenode.net!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1490
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA


Return to Project Euler

Who is online

Users browsing this forum: No registered users and 2 guests

cron