Kaleb's Grey Matter - posts tagged 'CS'

Palindromicity of Integers in C#

Wed, 25 Aug 2010 03:30:55 GMT

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;
    }
}

Project Euler #9 with Python

Thu, 22 Jul 2010 11:21:53 GMT

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

Project Euler #8 with Python

Thu, 22 Jul 2010 02:20:10 GMT

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

Project Euler #7 with Python: 10001st Prime Number

Tue, 20 Jul 2010 13:19:40 GMT

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:

not testing primality of numbers less than two
not testing two at all
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()

Project Euler Problem 4 with Python: Largest Palindrome

Mon, 19 Jul 2010 03:35:58 GMT

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))

Project Euler Problem 3 with Python: Greatest Prime Factor

Mon, 19 Jul 2010 03:12:55 GMT

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

Isograms

Sat, 13 Mar 2010 02:04:00 GMT

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

Project Euler 55

Fri, 12 Mar 2010 03:48:00 GMT

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.

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

Tue, 02 Feb 2010 15:48:00 GMT

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.