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

August 25 2010

kaleb
03:30

Palindromicity of Integers in C#

In my software engineering course, we were assigned to create a function that will test for the palindromicity of a an integer. My first try is as follows:

static bool palindromicity(int n)
{
    return n.ToString() == new String(n.ToString().Reverse().ToArray()));
}

I know mine is not as efficient as could be, because I am reversing the entire number instead of just the final half. After examination by the professor, however, my function was incorrect and so were the code samples of the entire class. The defect was that a conversion to string was used, when the professor stated that we must use integers.

Here is my next try:

static bool palindromicity(int n)
{
    if (n < 0) return false;
    else if (n < 10) return true;
    else
    {
        int head;
        int tail;
        for (int m = Convert.ToInt32(Math.Pow(10, Math.Floor(Math.Log10(Convert.ToDouble(n))))); n > 10; m /= 100)
        {
            head = n / m;
            tail = n % 10;
            if (head != tail)
                return false;
            n -= m * head;
            n /= 10;
        }
        return true;
    }
}
Tags: CS C#

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

February 02 2010

kaleb
15:48

Yo Dawg, I heard You Like Perl: Writing a Perl interpreter with Perl

Finally, we were given our first assignment in my CSCI 3300 Programming Languages class. We have to write a basic Perl interpreter using Perl. I am not too thrilled about the assignment. I would probably appreciate it better if I could use Perl to write an interpreter of almost any other language.
Tags: CS
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.