Newer posts are loading.
You are at the newest post.
Click here to check if anything new just came in.

July 22 2010

kaleb
11:21

Project Euler #9 with Python

While doing Project Euler exercise 9, I realized that python has no formal mechanism to break out of an outside loop. Here is my answer:

from itertools import count
p=False #to break or not to break
for b in count():
    for a in count():
        if a >= b: break
        c = (a**2 + b**2)**.5
        if a < b < c and a + b + c == 1000:
            p = True
            break
    if p:
        print a * b * c
        break
Tags: CS Python Project Euler
kaleb
02:20

Project Euler #8 with Python

For Project Euler #8, one must find the greatest product of five consecutive digits in a rediculously large number. Here's my go at it:

k = '73167176531330624919225119674426574742355349194934' \
    '96983520312774506326239578318016984801869478851843' \
    '85861560789112949495459501737958331952853208805511' \
    '12540698747158523863050715693290963295227443043557' \
    '66896648950445244523161731856403098711121722383113' \
    '62229893423380308135336276614282806444486645238749' \
    '30358907296290491560440772390713810515859307960866' \
    '70172427121883998797908792274921901699720888093776' \
    '65727333001053367881220235421809751254540594752243' \
    '52584907711670556013604839586446706324415722155397' \
    '53697817977846174064955149290862569321978468622482' \
    '83972241375657056057490261407972968652414535100474' \
    '82166370484403199890008895243450658541227588666881' \
    '16427171479924442928230863465674813919123162824586' \
    '17866458359124566529476545682848912883142607690042' \
    '24219022671055626321111109370544217506941658960408' \
    '07198403850962455444362981230987879927244284909188' \
    '84580156166097919133875499200524063689912560717606' \
    '05886116467109405077541002256983155200055935729725' \
    '71636269561882670428252483600823257530420752963450'

biggest = 0
for a,b in enumerate(k):
    m = 1
    for i in k[int(a):int(a)+5]:
        if i == '0': continue
        m*=int(i)
    if m > biggest:
        biggest = m
Tags: CS Python Project Euler

July 20 2010

kaleb
13:19

Project Euler #7 with Python: 10001st Prime Number

For this exercise, one must find the 10001st prime number. The following is my code:

def is_prime(n):
    #if n < 2: return False
    #if n == 2: return True
    #if n & 1: return False
    for i in range(3,int(n**.5)+1,2):
        if not n%i:
            return False
    return True
def prime_list(n):
    primes = [2,3,5,7,11,13]
    i = max(primes) + 2
    while len(primes) < n:
        if is_prime(i):
            primes.append(i)
        i+=2
    return primes
print max(prime_list(10001))

Notice that in the is_prime function, I have made it faster by removing tests that will not be necessary for the range it is working with. Un-comment those lines, and one will notice significant slow-downs.

I can comment out these lines in my primality test, because I am:
  1. not testing primality of numbers less than two
  2. not testing two at all
  3. not testing any even numbers
I just need to optimize and get rid of the doubly nested loops.

EDIT:

After doing some research, I found this awesome prime number generator:

def gen_primes():
    D = {}  
    q = 2  
    while True:
        if q not in D: 
            yield q        
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1

With this is play, here is my new answer:
def nth_prime(n):
    return (j for i,j in enumerate(gen_primes()) if i == n-1).next()
Tags: CS Python Project Euler

July 19 2010

kaleb
03:35

Project Euler Problem 4 with Python: Largest Palindrome

To find the largest palindromic number from multiplying two three digit numbers, I used the following python code:

def is_palindromic(n):
    return str(n) == str(n)[::-1]

print max(i*j for i in xrange(999,99,-1) for j in xrange(999,99,-1) if is_palindromic(i*j))
Tags: CS Python Project Euler
kaleb
03:12

Project Euler Problem 3 with Python: Greatest Prime Factor

This is not very efficient, but here is my solution to Project Euler Problem 3 using python.

from math import ceil
class Prime(object):
    primes = set([2])
    def is_prime(self,n):
        n = float(n)
        if n < 2:
            return False
        else:
            for i in xrange(2,int(ceil(n**.5))):
                f = n/i
                if not f%1:
                    return False
            else:
                return True
    def greatest_prime_factor(self,n):
        n = float(n)
        if self.is_prime(n): return n
        prime_factors = set()
        for i in xrange(2,int(ceil(n**.5))):
            f = n/i
            if not f%1:
                if self.is_prime(f):
                    prime_factors.add(f)
                if self.is_prime(i):
                    prime_factors.add(i)
        return max(prime_factors)
prime = Prime()
n = 600851475143
prime.greatest_prime_factor(n)
Edit:
After looking at some of the other answers, I made the following as translated from a fantastic c answer:
def greatest_prime_factor(n):
    divisor = 2
    while n > 1:
        print divisor
        if not n%divisor:
            n /= divisor
            divisor -= 1
        divisor += 1
    return divisor
Tags: CS Python Project Euler

March 13 2010

kaleb
02:04

Isograms

Another Python assignment from my programming languages class:
Write a program that will find isograms from user input.
dog is a 1 letter isogram.
TartAr is a 2 letter isogram.
Remove is not an isogram.
Aqwsssaqwaqwswqa is a 4 letter isogram.
Test-test has an illegal character
Here's my answer:

#!/usr/bin/python

def char_count(word):
    """Return a dictionary of character counts."""
    chars = {}                  # Should use py2.7's Counter class, not dict
    for char in word: chars[char] = chars.get(char,0) + 1
    return chars

def func(word):
    """If word is an isogram, return its degree, otherwise return 0."""
    if not word.isalpha(): raise Exception("Illegal character.")
    vals = char_count(word).values()
    return vals[0] if not any([cmp(vals[0],i) for i in vals]) else 0
Tags: CS Python

March 12 2010

kaleb
03:48

Project Euler 55

A few days ago, I made a post about palindromic numbers. After some thought, I realized that I should have done some things different. For one, there was no need for the partition function.

I also found out that a number which cannot become a palindrome through the process of reversing and addition is called a Lychrel number, and Project Euler has a problem concerning Lychrel numbers.

From Project Euler question #55:
If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

Here's my solution:

lychrel = 0
for i in xrange(10000):
    for k in xrange(50):
        r = int(str(i)[::-1])
        if i == r and k != 0: break
        else: i += r
    else: lychrel += 1
print lychrel

I've seen many solutions out there written in Python that were either un-pythonic or slow, and may of the times the former led to the latter. I am pretty sure that this is the fastest Python implementation.
Tags: Euler CS Python

March 09 2010

kaleb
03:45

Reduction ad Palindromo

My Programming Languages professor assigned the following as an assignment today:
It is claimed that all numbers, when reversed and added to their
reversal repeatedly, will eventually become palindromes.   Write a
program that allows a user to enter a number and then displays the
series of efforts to find its palindrome.  If the statement turns out
to be false, stop iteration of your program after some number of tries
to find the palindrome.
The following is my solution:

#!/usr/bin/python

def partition(obj):
    """Return a triple of the first half, middle (if it exists), and last half
    of an iterable object.
    """
    ctr, odd = divmod(len(obj), 2)
    fwd = obj[:ctr]
    if odd:
        mid = obj[ctr]
        aft = obj[ctr+1:]
    else:
        mid = None
        aft = obj[ctr:]
    return (fwd,mid,aft)

def palindromic(obj):
    """Return the palindromicity of an object."""
    if type(obj) == type(list()) or type(obj) == type(tuple()):
        pass
    else:
        obj = list(str(obj))
    front,mid,rear = partition(obj)
    return front == rear[::-1]


def reductio_ad_palindromo(num):
    """If a number is not palindromic, sum it and its reverse. Repeat until a
    a palindrome is found. Return a list of all attempts.
    """
    num = int(num)   # Make sure its an int.
    iterations = []
    def pal(n):
        iterations.append(n)
        if not palindromic(int(n)):
            pal(n + int(str(n)[::-1]))
    pal(num)
    return iterations

if __name__ == "__main__":
    """Since this most likely will be ran from `bash`, return the array in the
    form of a space delimited `bash` array."""

    from sys import argv

    print " ".join([str(i) for i in reductio_ad_palindromo(argv[1])])

I am not sure what she means by this antecedent, "if the statement turns out to be false," but Python's got the antecedent covered. Python will stop a recursion automatically after 1000 loops, that is unless it is told otherwise.
Tags: Python
Older posts are this way If this message doesn't go away, click anywhere on the page to continue loading posts.
Could not load more posts
Maybe Soup is currently being updated? I'll try again automatically in a few seconds...
Just a second, loading more posts...
You've reached the end.