Posts Tagged ‘elf’

Typical – I’m late

May 30, 2009

Here are my solutions from the last set that I never got around to posting:

Problem 3 – I guess I just printed the list and then took the biggest here.


def divisors(n):
  divs = set([1])

  for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
      divs.add(i)
      divs.add(n/i)

  return divs

def isPrime(n):
  return len(divisors(n)) == 1

divs = list(divisors(600851475143))
divs.sort()
divs.reverse()

for div in divs:
  if isPrime(div):
    print div

Problem 4 –

def isPalidrome(num):
    numstr = str(num)
    for i in range(len(numstr)):
	if numstr[i] != numstr[-i-1]:
	    return False
    return True

i = 999
j = 999
prod = i * j
biggest = 0
big_i = 0
big_j = 0

while prod > biggest:
    while prod > biggest:
	if isPalidrome(prod):
	    biggest = prod
	    big_i = i
	    big_j = j
	    break
	j -= 1
	prod = i * j
    i -= 1
    j = i
    prod = i * j

print "Biggest is: ", big_i, " x ", big_j, " = ", biggest

Problem 5 – Okay, this one is cheap, but Carolyn and I figured out that it was super easy to just count which divisors you needed, so there wasn’t really much coding to do. 🙂

print 20*19*9*17*4*7*13*11

Problem 6 – Hmm. Don’t see where I put the source to this one, so maybe I skipped it. I’ll post it with the solutions to next (i.e. this) week’s problems.

Cheers.

Advertisements

Problem 1 Rehash

May 15, 2009

Well Nick mentioned earlier today in the office that he had thought of a quicker way to accomplish the first problem.  I’m not sure if this is what he meant, but what I came up with is roughly this: you don’t need to run past all the multiples of each number (3 and 5 in our case) since you can run over the lcm instead.  There will be a fixed amount added each time you pass a multiple of the lcm.

So for example with the numbers 3 and 5 chosen as the divisors we’re interested in we could organize the multiples into a list as follows:

  • 3 + 5 + 6 + 9 + 10 + 12 +15 = 60
  • 18 + 20 + 21 + 24 + 25 + 27 + 30 = 165
  • 33 + 35 + 36 + 39 + 40 + 42 + 45 = 270
  • . . .

You’ll notice that the difference between each sum here is 105 = 7 * 15 which is the number of divisible numbers below the lcm times the lcm.  Well, you probably get the idea now . . . the only snag is the fudge factor: since 15*66 = 990 we need to pick up the last couple multiples above this guy before we get to 1000 (namely 993,996,999).

It seemed like a good idea to allow as many different dividing factors as you like at the same time, so I rewrote both mine and Nick’s solution to take an arbitrary list of numbers as an argument.  For low values like 1000, the lcm idea doesn’t add much.  But for higher maximum values and more factors, it’s a considerable speedup.

Here are some timing results for 3 and 5:

  • Max = 1000, Lcm = .00083, All = .00081
  • Max = 100000 Lcm = .12, All = .12
  • Max = 10000000 Lcm = 3.1, All = 6.3

Now for 3,5 and 7:

  • Max = 1000, Lcm = .00014, All = .001
  • Max = 100000, Lcm = .012, All = .14
  • Max = 10000000, Lcm = .51, All = 9.5

You can see that the Lcm method actually improves with more factors since we’re skipping ahead faster.  Here’s the (kind of messy) code:

def solution2(divisors = [3,5,7], m_val = max_val):
   nums_lcm = lcm(divisors)

   base_set = set([nums_lcm])

   for j in range(len(divisors)):
     cur_div = divisors[j]
     base_set |= set( cur_div * i for i in range(1, nums_lcm / cur_div) )

   # sum of all numbers below least common multiple
   base_sum = sum(base_set)

   # of summands in the previous example
   num_summands = len(base_set)

   reps = max_val//nums_lcm
   scale = num_summands * nums_lcm

   big_skip = nums_lcm * reps
   fudge_set = set( i + big_skip for i in base_set if i + big_skip < max_val )    fudge = sum(fudge_set)    t = time()    my_set = set( base_sum + (i*scale) for i in xrange(0,reps))    print_answer(sum(my_set) + fudge, time()-t) [/sourcecode] Note that I don't start the clock until after doing the setup calculations since technically this information would be given to us as part of specifying which factors to use. Finally, here is some number magic: the answers for higher maximum values in the case of the factors 3 and 5 are as follows:

  • 1000 => 233168
  • 10000 => 23331668
  • 100000 => 2333316668
  • 1000000 => 233333166668

Holy shit, no?

Assignments

May 14, 2009

So I noticed that two solutions used code like this to generate the Fibbonaci numbers:


a,b=0,1

...

a, b = b, a+b

Being used to older languages like C, these multiple assignments would not have been allowed.  But beyond that, it raises the question of the order in which the assignments are made.  For example, I would have thought they would be processed just as they are written, in which case the second assignment would be adding “b” to itself instead of the old “a” (which is why I used an extra temporary variable in my solution.) Since this code gets the right answer, this is apparently not the case.

All Python data types are objects, so what if the multiple assignment had more complicated side effects?  Do all the objects involved get copied in memory as an assignment like this takes place to save their state? This is probably all wrapped up in the reference system.  Maybe someone could clarify the assignment process for me.  (And save my lazy ass the trouble of looking it up.)

A Word of Warning

May 13, 2009

Well, I learned one thing from my first post: Python is really strict about indentation, since that’s how it determines loops and conditionals and such (no braces!).  I think this is a great thing, and most editors which are made for programming will help you out with this.  But I did notice that copying and pasting my code lost a couple of the tabs (though it should be fixed now), and this might make the interpreter give errors to anyone who tried it.  So I guess we gotta be a bit careful about the formatting as we post these things . . .

Out of the gates in a hurry!

May 13, 2009

Well, I had already tried a bunch of these guys, and I want to try out this posting deal, so here’s my solutions to the first two.


#
#  problem1.py
#

nums = set(i for i in range(1,1000) if ((i%3 == 0) or (i%5 == 0)))

print sum(nums)

#
#  problem2.py
#

fib_last = 1
fib_cur = 1

ev_sum = 0

def isEven(num):
return (num % 2 == 0)

while fib_cur <= 4000000: if isEven(fib_cur): ev_sum += fib_cur temp = fib_cur fib_cur += fib_last fib_last = temp print ev_sum [/sourcecode]