## Project Euler: Problem 8

The website has problem eight stated as such,“Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450”

Yeah, looks pretty intimadating to me too. ;) Lucky enough for both of us this really isn't all that hard to figure out.

Python

`#!/usr/bin/python3"""code solution for Euler Project #8"""import operatorfrom functools import reduce if __name__ == "__main__":  index = 0  high_score = 0  investigate_this = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450    digit_list = [int(x) for x in str(investigate_this)]  digit_list_length = len(digit_list)   while index < digit_list_length:    if index == 0:      temp_product = reduce(operator.mul, digit_list[index: index +5])    elif index == 1:      temp_product = reduce(operator.mul, digit_list[index - 1: index + 4])    elif index == digit_list_length - 1:      temp_product = reduce(operator.mul, digit_list[index - 4: index + 1])    elif index == digit_list_length - 2:      temp_product = reduce(operator.mul, digit_list[index - 3: index + 2])    else:      temp_product = reduce(operator.mul, digit_list[index -2 : index + 3])     if temp_product > high_score:        high_score = temp_product     index += 1   print(high_score)`

For my first attempt I took an approach of having a travelling index and checking both two digits before and two digits after the index. This worked out pretty well except that I needed to add four special use cases (the first two index points and the last two). Some people may say that it's not “pythonic” to use reduce, and in some ways I can agree with it. However, in this case my reduce fuctions really aren't very complicated and I think they look cleaner than using for loops in this instance. Does anyone out there have any opinions?

`module Main where import Data.Char investigate_this = map digitToInt \$ show 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450 investigate_length = length investigate_this productof5 index  | index >= investigate_length - 4 = []  | otherwise  = prod5 : productof5 (index + 1)  where prod5 = product [ investigate_this !! y | y <- [index..(index + 4)]] main :: IO()main = print . maximum \$ productof5 0`

In my next solution, I followed the same idea of using a traveling index, but this time I only paid attention to the index and the next four digits. The advantage to this was that I only needed to worry about one special case, and that was if the number of multipliers were less than five total. This did seem to simplify things.

Sorry to all my Perl & Java readers. Life is kind of chaotic at the moment and I only really had the energy to do these two languages. One day I hope to revisit this problem in those languages, and when I do I'll update this post with the new code additions.

I realize in the last few times I've posted project euler solution I haven't said anything so just to nail this thought home amongst the people reading this. I look forward to hearing any and all constructive comments regarding algorythms and code. Oh, and one more thing, I apologize in advance for the formatting of the rather large number.

## Code to lyrics

It's not everyday that one can turn song lyrics into code. I've been a big fan of the group One Minute Silence for a pretty long time (1998 if memory serves me correctly), but it wasn't until recently that I was listening to the song “I Can Change” that I noticed that the spoken word part that happens at both the beginning and the end of the song followed a pattern. Noticing this pattern I realized I could reproduce the lyrics in code:

`#!/usr/bin/python3 def print_lyrics(words):    if "I" in words:        print("If I can change " + words[0] + ", " + words[1] + " can change.")    else:        print("If I can change " + words[0] + ", I can change " + words[1] + ",") if __name__ == "__main__":    number = [ str(2 ** x) for x in range(0,4)]    number2 = number[1:]    number2.append('I')    for x in zip(number, number2):        print_lyrics(x)`

As a side note, I'm not sure if Yap intended to follow the powers of two, but it worked out really well when trying to generate the numerical output. And if you think your the kind of person that enjoys that hip-hop metal with anti-capitalist message, then you might want to give the song a try, and maybe the rest of their material if you like it.

Oh yeah, before I forget, Happy Friday everyone.

## Project Euler: Problem 7

Here is the seventh installment of this series. And just to keep things interesting I'm going to do something different this time around. I still performed the solutions for Haskell, Java, and Perl (if you want to view them check out my github repo), but instead of posting the code for all four languages, I'm going to be talking about the evolution of my Python solution, showing you all three revisions, and talking briefly about how or why things changed.

Python code:
Solution 1:

`#!/usr/bin/python3 import math def is_prime(divided):  divisor = 3  sqrt_divided = math.sqrt(divided)  while divisor <= sqrt_divided:    if divided % divisor == 0:      return False     divisor += 2  return True if __name__ == "__main__":  prime_list = [2]  count = 3   while len(prime_list) < 10001:    if is_prime(count) == True:      prime_list.append(count)     count += 2   print(prime_list[-1])`

Looking at this first solution, we see that it follows the Haskell solution quite closely. This is of course not an accident; I'm lazy. ;) And since I'm still learning Haskell, I find it easier to learn the basics of a language through translation. So this Python solution was my first solution, which I then translated to Haskell.

Solution 2:

`#!/usr/bin/python3 import math def is_prime(divided):  divisor = 3  sqrt_divided = math.sqrt(divided)  while divisor <= sqrt_divided:    if divided % divisor == 0:      return False     divisor += 2  return True  if __name__ == "__main__":  count = 1 #to substitute the prime number 2 in the example  last = 0  iterator = 3   while count < 10001:    if is_prime(iterator):      count += 1      last = iterator     iterator += 2   print(last)`

So in coming up with my Java solution, I didn't want to deal with trying to come up with a linked list-based solution for number storage. At which point I had the great thought: why not just hold the last number to be prime, and not all primes. Spending all this time with lists and arrays instead of just straight Ints has really played with my thought patterns. So after I wrote up the Java solution, I translated it to Python, to see if there would be a reduction in the execution time based on only using Ints instead of a list of Ints. Paint me a little surprised when I saw that the difference was minimal if non-existent most of the time.

Solution 3:

`#!/usr/bin/python3 import math def is_prime(divided):  divisor = 3  sqrt_divided = int(math.sqrt(divided))  while divisor <= sqrt_divided:    if divided % divisor == 0:      return False     divisor += 2  return True  if __name__ == "__main__":  # using a list to store each int value   data = [1,0,3]   while data[0] < 10001:    if is_prime(data[2]):      data[0] += 1      data[1] = data[2]     data[2] += 2   print(data[1])`

After digging into how Python does its memory management, like Lists being mutable while Ints are not, I modified the second solution so that the Ints are now in a list. This way the Python memory manager does not have to create a new variable to store each value. After these changes I got the speed difference I was expecting to see between the first and second revision.

Also, you might have noticed that in the is_prime function, I cast math.sqrt to an Int. As math.sqrt returns a float, every time that comparison happens for the while loop there has to be a conversion of divisor from its current state of int to a float. Math.sqrt returns a float, thus sqrt_divided is a float, and divisor is an int. So every time that while loop cycles again, there has to be a conversion of an int to a float. By casting that float to an int during the variable declaration, I save myself a few thousand cast operations and shave off a couple hundredths of a second from the total run time.

Language Run Times:
Python:
solution 1: .452s
solution 2: .433s
solution 3: .376
Perl : .333s
Java: .128s

I don't think there are enough words in the English language to express my surprise that Java actually had the lowest overall run time on this one. I reran the Java solution a couple of times to see if it was an error, but it's correct. This is something that I will have to dig into more deeply to find out why.

## And Now For Something Completely Different...

Or maybe not. I came across this programming challenge through means I'm not quite comfortable sharing on the interwebs. So disregard the origin of this challenge, and just put those spare brain cells toward the challenge and my answer.

The challenge:
```Write a program that assigns products to sites in a way that maximizes the scores over the set of customers. Each customer can only have one product and each product can only be offered to one customer. Your program should run on the command line and take as input two newline separated files, the first containing the names of the products and the second containing the names of the customers. The output should be the total SS and a matching between customers and products. You do not need to worry about malformed input, but you should certainly handle both upper and lower case names.```

```The algorithm for generating the number is as follows: • If the length of the product name is even, the base score is the number of vowels in the customer’s name multiplied by 1.5. • If the length of the product name is odd, the base score is the number of consonants in the customer’s name multiplied by 1. • If the length of the product name shares any common factors (besides 1) with the length of the customer’s name, the score is increased by 50% above the base score. ```

`#!/usr/bin/python import sysfrom optparse import OptionParser def build_list_from_file(filename):    """    builds a list from a newline delimited file.    INPUT: string object, the filename    OUTPUT: a list object with the lines of the file    """    temp_list = []    try:        with open(filename) as file:            for lines in file:                temp_list.append(lines.strip())    except IOError:        print "the file %s does not exist. Please look into it." % filename        sys.exit(1)     return temp_list def count_vowels(name):    """    counts the number of vowels in a string.    INPUT: string object, the string to be parsed    OUTPUT: int object, the number of vowels in the string    """    vowels = 0    for x in name.lower(): #setting all characters to lower case for comparison        for y in ['a', 'e', 'i', 'o', 'u']:            if x == y:                vowels += 1     return vowels  def count_consinants(name):    return len(name) - count_vowels(name)  def generate_ss(matrix_object):    """    The function to generate the SS score based on the product name    and customer name.    INPUT: tuple object, with the name in the first element and            the product name in the second    OUTPUT: a float object with the value after the computation    """    cust = matrix_object[0]    prod = matrix_object[1]    cust_factors = get_factors(cust)    prod_factors = get_factors(prod)    ss = 0.0     if len(prod) % 2 == 0:        ss = float(1.5 * count_vowels(cust))    else:        ss = float(count_consinants(cust)) # muliplicaton by 1 is implied.     # by using sets, we can now use itersection to see if there are any    # common factors between the two names    if len(cust_factors.intersection(prod_factors)) > 0:        ss *= 1.5     return ss  def get_factors(name):    """    Retrive the factors of a particular number.    INPUT: int object, number to gather factors of.    OUTPUT: set object, the factors of a particular number    """    # using a variable instead of calling len() twice, should be faster    top_num = len(name)    return set([x for x in range(2,top_num+1) if top_num % x  == 0])  if __name__ == "__main__":    """self explanitory... I hope."""    parser = OptionParser()    parser.add_option("-p", "--prod", dest="prod",                      help = "Path to the prodcts file.Which should be newline delimited file.")    parser.add_option("-c", "--cust", dest="cust",                      help = "Path to the customer file.Which should be newline delimited file.")     (options,args) = parser.parse_args()     if not (options.prod and options.cust):        print "A file for customers (-c) and one for products (-p) are needed."        sys.exit(1)     customer_list = build_list_from_file(options.cust)     prodcut_list = build_list_from_file(options.prod)    matrix = []    final_list = []     matrix = [(a,b) for a in customer_list for b in prodcut_list]     ss_list = map(generate_ss, matrix)     # since we're zipping things up, might as well sort it    # with largest SS value first    zipped_by_ss = list(reversed(sorted(zip( ss_list, matrix))))     # need to prime the list in order for this to work    final_list.append(zipped_by_ss[0])    del zipped_by_ss[0]     while 1 < len(zipped_by_ss):      j = 0      while j < len(zipped_by_ss):        if ( zipped_by_ss[j][1][0] is final_list[-1][1][0] or             zipped_by_ss[j][1][0] is final_list[-1][1][1] or             zipped_by_ss[j][1][1] is final_list[-1][1][0] or             zipped_by_ss[j][1][1] is final_list[-1][1][1]           ):           del zipped_by_ss[j]           continue        j += 1        final_list.append(zipped_by_ss[0])      del zipped_by_ss[0]     for item in final_list:        print "%s has item %s, with SS score of %s." % (item[1][0], item[1][1],item[0])`