Tina Orooji

http://projecteuler.net/index.php?section=problems&id=6

# Project Euler - Problem 6 (http://projecteuler.net/index.php?section=problems&id=6)

# Generate the sum of squares and square of sums using summation formulas, then
# subtract.
def p6():
    n = 100
    squareOfSum = ((n*(n+1))/2)**2
    sumOfSquares = (n*(n+1)*(2*n+1))/6

    print squareOfSum - sumOfSquares

http://projecteuler.net/index.php?section=problems&id=13

This one was tricky until I Googled “java big integer” and found out about Java’s BigInteger, lol. It made the problem much simpler. After I got the answer I saw some posts on the forum saying that only the sum of the first 11-15 (it varied) digits were needed, but I’m not fully convinced of that yet. The other digits could lead to values being “carried over”, which will impact the total sum. So, I still stand by my solution… for now ) I’ll keep thinking about the other solution and see if I’m able to convince myself one way or the other.

	/* Project Euler - Problem 13 (http://projecteuler.net/index.php?section=problems&id=13)
	 *
	 * Saved the numbers to a file for neatness.  Then just read from the file and used
	 * Java's BigInteger.
	 */
	public static void p13(){
		String line = null;
		BigInteger sum = BigInteger.ZERO;

		try{
			BufferedReader input = new BufferedReader (new FileReader("numbers.txt"));

			while((line = input.readLine()) != null)
				sum = sum.add(new BigInteger(line));
		}
		catch(IOException e){e.printStackTrace();}

		System.out.println(sum.toString().substring(0,10));
	}

http://projecteuler.net/index.php?section=problems&id=1

I mentioned Project Euler to some of my co-workers and one of them, Daniel, is hooked. He came up with a better solution for Problem 1 than I had, but it was still an O(n) algorithm. We talked about it a little and our discussion lead to this constant time solution. Yay for teamwork!

	/* Project Euler - Problem 1 (http://projecteuler.net/index.php?section=problems&id=1)
	 *
	 * Using basic summations, get the sums of all multiples of 3, 5 and 3*5.  Add the
	 * summations for 3 and 5, then subtract the summation for 15.
	 */
	public static void p1(){
		double a = 3, b = 5, n = 999;
		double sum;

		sum = (a*summation(Math.floor(n/a))) + (b*summation(Math.floor(n/b))) - (a*b*summation(Math.floor(n/(a*b))));

		System.out.println((int)sum);
	}

	/* Basic summation function.  Returns the sum from 1 to n */
	public static double summation(double n){
		return n*(n+1)/2;
	}

http://projecteuler.net/index.php?section=problems&id=9

	/* Project Euler - Problem 9 (http://projecteuler.net/index.php?section=problems&id=9)
	 *
	 * Pretty simple brute force method.
	 */
	public static void p9(){
		double a = 0, b = 0, c = 0;

		for(a=0; a<1000; a++){
			for(b=a+1; b<1000; b++){
				c = Math.sqrt(Math.pow(a, 2) + Math.pow(b,2));
				if(b<c && a+b+c == 1000) break;
			}
			if(b<c && a+b+c == 1000) break;
		}

		System.out.println((int)(a*b*c));
	}

Note: After writing this I saw a mathematical solution on the forum. It utilizes stuff I vaguely remember so I’ll have to refresh my Geometry skills and redo this one soon )

http://projecteuler.net/index.php?section=problems&id=5

I’ll be honest, I solved this one on paper first and then figured out how to do it programatically. I don’t mean that I brainstormed a solution for a simpler case and then came up with an algorithm to get a solution for this problem… I mean I did the whole thing on paper and then once I had an answer I figured out how to write the program. Is that cheating? lol

Anyway, my first thought was that I may be able to find a subset of numbers from 1 to 20 whose product will be the solution.  For example, for the simpler solution of 1 to 10, 1*5*7*8*9 yields the solution.  (The 1 is included for completeness…  you’ll see.)  Eventually I realized that it wasn’t those actual values that caused their product to be the solution…  it was the prime factorization of those values.  Take the prime factorization for each number from 1 to 10:
1 = 1^1
2 = 1^1 * 2^1
3 = 1^1 * 3^1
4 = 1^1 * 2^2
5 = 1^1 * 5^1
6 = 1^1 * 2^1 * 3^1
7 = 1^1 * 7^1
8 = 1^1 * 2^3
9 = 1^1 * 3^3
10 = 1^1 * 2^1 * 5^1

The special thing about the values 5, 7, 8 and 9 is that the degrees for each prime number in their factorization are maximums of all other degrees for that prime. The highest degree of 1 is 1, the highest degree of 2 is 3, of 3 is 3, of 5 is 1, and of 7 is 1.

I then went through and figured out the prime factorization for 11 to 20:
11 = 1^1 * 11^1
12 = 1^1 * 2^2 * 3^1
13 = 1^1 * 13^1
14 = 1^1 * 2^1 * 7^1
15 = 1^1 * 3^1 * 5^1
16 = 1^1 * 2^4
17 = 1^1 * 17^1
18 = 1^1 * 2^1 * 9^1
19 = 1^1 * 19^1
20 = 1^1 * 2^2 * 5^1

Following the logic from before, my new set of highest degrees is:
1 – 1
2 – 4
3 – 2
5 – 1
7 – 1
11 – 1
13 – 1
17 – 1
19 – 1

So, this means that 1, 16, 9, 5, 7, 11, 13, 17 and 19 are the numbers that yield the maximum degree for each prime. Multiply them together, and you get the answer.

After I wrote a program to do what I’d done manually, I realized that it would be a lot cleaner to just loop through each number, check the factorization and see if one of the degrees produced is more than a previous degree.

I was a little concerned about the correctness because I need to make sure that if 1 is the highest degree for 5, the 5^1 from 5 is used… not, say, from 20. If I do somehow use the 5^1 from the 20, I want to make sure I don’t also use the 2^2 from 20, since another number had a higher degree for 2. I did a few test causes and I’m fairly confident that this won’t happen since I’m checking each prime individually.

	/* Project Euler - Problem 5 (http://projecteuler.net/index.php?section=problems&id=5)
	 *
	 * Finds the highest degree for each prime number in the prime factorization of
	 * all numbers from 1 to 20.  Each prime is then raised to it's highest degree and
	 * multiplied.
	 */
	public static void p5(){
		/* All primes from 1 to 20 */
		int degrees[][] = {{2,0}, {3,0}, {5,0}, {7,0}, {11,0}, {13,0}, {17,0}, {19,0}};
		int n=1;

		/* For each number, get the prime factorization.  If the degree is
		 * greater than the current degree for any given prime, replace it.
		 */
		for(int i=1; i<=20; i++)
			for(int j=0; j<degrees.length; j++)
				if(getDegree(i, degrees[j][0]) > degrees[j][1])
					degrees[j][1] = getDegree(i,degrees[j][0]);

		/* Get the product of each prime raised to it's highest degree */
		for(int i=0; i<degrees.length; i++)
			n = n * (int)Math.pow(degrees[i][0], degrees[i][1]);

		System.out.println(n);
	}

	public static int getDegree(int num, int prime){
		int count = 0;

		while(num % prime == 0){
			count++;
			num = num/prime;
		}

		return count;
	}

Note: After I wrote this I checked the forum on http://projecteuler.net and it looks like others solved it similarly, but without quite as much running around in circles )  Oops!

http://projecteuler.net/index.php?section=problems&id=4

	/* Project Euler - Problem 4 (http://projecteuler.net/index.php?section=problems&id=4)
	 *
	 * I was able to reduce some of the iterations by setting up the loops to not repeat
	 * computations (ie, don't do 998 x 912 and 912 * 998), but this is basically a
	 * brute force solution.
	 */
	public static void p4(){
		int pal = 0;

		for(int i=1; i<=999; i++)
			for(int j=1; j<=i; j++)
				if(i*j>pal && isPalindrome(Integer.toString(i*j)))
					pal = i*j;

		System.out.println(pal);
	}

	public static boolean isPalindrome(String str){
		int start = 0;
		int end = str.length() - 1;

		while(start < end){
			if(str.charAt(start) == str.charAt(end)){
				start++;
				end--;
			}
			else return false;
		}

		return true;
	}

http://projecteuler.net/index.php?section=problems&id=2

	/* Project Euler - Problem 2 (http://projecteuler.net/index.php?section=problems&id=2)
	 *
	 * I did realize that every 3rd Fibonacci number is even, but I haven't quite come
	 * up with a way to utilize that knowledge to simplify the loop.  I'll keep thinking
	 * about it and see if I come up with something better.
	 */
	public static void p2(){
		int sum = 0;
		int fib1 = 1;
		int fib2 = 1;
		int temp;

		do{
			temp = fib1 + fib2;
			fib1 = fib2;
			fib2 = temp;

			if(fib2 % 2 == 0) sum = sum+fib2;
		} while(fib2<4000000);

		System.out.println(sum);
	}

http://projecteuler.net/index.php?section=problems&id=1

	/* Project Euler - Problem 1 (http://projecteuler.net/index.php?section=problems&id=1)
	 *
	 * This problem is pretty straightforward, however, rather than going the brute-force
	 * route and checking each number from 1 to 999 to see if 3 or 5 is a divsor,
	 * I realized that I can break the numbers up in to groups of 15 (3*5) and find a
	 * pattern within the group.  It is still an O(n) runtime, but with some tweaking I should be able
	 * to get rid of the inner loop.
	 */
	public static void p1(){
		int n = 0;
		int sum = 0;
		int nums[] = {3, 2, 1, 3, 1, 2, 3}; /* Distances between 3, 5, 6, 9, 10, 12, 15 */

		do {
			for(int i=0;i<nums.length;i++){
				n=n+nums[i];
				if(n<1000) sum=sum+n;
				else break;
			}
		} while(n<1000);

		System.out.println(sum);
	}

Being married to one of those academic types is rough.  I can handle the 15-syllable words and the excited recaps of various studies, but amount of literature that one man can claim to read is amazing.  Ben has access to thousands of psychology journal articles and insists that he can not read them in electronic form, so he prints them out.  In addition to wreaking havoc on the environment this has turned his half of our home office in to a complete and utter mess.  We’ve done everything we can think of to help him organize his literature, but the problem is sometimes he just doesn’t have time to file away each article appropriately.  My unbelievably organized husband would rather dump new articles in an empty box and then move on to a new box once the current one gets full.  This is all great, until Ben needs an article that he is *sure* he read last year or the year before.  Insertion went fabulously, but searching is a whole other story.  Searching for a journal article about cognitive something or the other is an O(n) algorithm around here.

So, we need a solution.  I told a friend of mine about this dilemma a while back and he suggested using it as an opportunity to learn about Ruby on Rails, but I never really got around to it.  Since then I’ve had other opportunities to mess with Rails, but since the problem still exists I think it is high time I came up with a solution!

I hope to document my solution in hopes of not only learning more myself, but also to maybe create a super simple tutorial for someone else who may need it.  I’ll try to be as detailed as possible…  we’ll see how it goes )

Getting Started

First, Ben and I needed to come up with a reasonable way to store these articles.  I suggested having him enter information about each article as soon as he prints it out, but that led to divorce threats.  So, we decided that we’d foster his habit of just throwing articles into boxes, however, he’d also number each article and box.  That way, he can tell the app that articles 150 – 300 are in box 2.  Later, when he has the time and motivation, he can go back and tell the app little bit about articles 150 – 300.  He’ll want to tell it the name of the journal and issue number where the publication appeared, the author(s) and maybe some keywords.

In order to prevent me from constantly writing queries to answer questions like “Which boxes should I check if I want a lot of articles about forensic assessment of juveniles?”, I’ll probably add a reporting layer as well.  But, that’s getting ahead of myself )

Planning

So, now I need to plan out my entities.  Here’s a quick ERD of what I’m thinking:

And from that, here’s a relational model:

I think most of that should be self explanatory except for why I chose to have three separate attributes to make up the date in the issues relation.  Ben said that sometimes issues don’t have an exact date, they just have a month and a year.  Rather than hacking stuff up and setting the date to the first of the publication month or something, I figured the three separate attributes would be a good solution.

Create the application and start the webserver

C:\Users\Tina\workspace>rails articles
C:\Users\Tina\workspace>cd articles
C:\Users\Tina\workspace\Articles>ruby script\server

Start setting up Models, Views and Controllers

I’m going to use scaffolding to generate my entities that will need views…  Basically, it’s just the following syntax:

ruby script\generate scaffold <entity> <attribute1>:<datatype1> <attribute2>:<datatype2>

C:\Users\Tina\workspace\Articles>ruby script\generate scaffold journal name:string
C:\Users\Tina\workspace\Articles>ruby script\generate scaffold issue journal_id: integer month:integer day:integer year:integer
C:\Users\Tina\workspace\Articles>ruby script\generate scaffold article issue_id:integer box_id:integer name:string start_page:integer end_page:integer number:integer
C:\Users\Tina\workspace\Articles>ruby script\generate scaffold author first_name:string middle_initial:string last_name:string
C:\Users\Tina\workspace\Articles>ruby script\generate scaffold keyword word:string
C:\Users\Tina\workspace\Articles>ruby script\generate scaffold box number:integer

Migrate the database

Before doing any database migrations, sqlite needs to be installed with the ruby gem.  This is a good explanation of how to do so: http://wiki.rubyonrails.org/rails/pages/HowtoUseSQLite 
To install the gem I used the following:
C:\Users\Tina\workspace\Articles>gem install --version 1.2.3 sqlite3-ruby

To do the DB migration (create the DB and tables based on the scaffolding), just run the following command:
C:\Users\Tina\workspace\Articles>rake db:migrate 

Yay!!!
I can now enter journals, articles, etc.  Yippee!  However, this isn’t anywhere near usable.  None of my mapping tables are being populated and I highly doubt anyone wants to look up an issue’s id in order to enter a new article.  That’ll all be handled in Part 2! 

Since I pretty much have my earbuds in all day while I am at work, a colleague asked me for a list of podcasts that I regularly listen to.  I decided to post it here in case anyone else is interested!  Here’s an export of everything I listen to…  it’s a pretty eclectic mix of technical, news, science, financial and cooking related shows.  I should mention, however, that I can’t take credit for finding all of these.  Much of what I listen to was recommended to me by my friends Brian and Mario.

Enjoy!

Podcasts