Problem #3

Problem: Design an algorithm that prints out all the prime numbers between 1 and the given number.

Example: input -> 10
2
3
4
5
7

Algorithm: In order to solve this problem I used dynamic programming to greatly reduce the number of prime checks I had to do. I formatted the code so that the parameter would be a command line input and thus the first portion of the main function is simple exception catching and error handling. Then because you want the primes between 1 and the given number as long as the number is not negative or 1 then 2 will always be on the prime list so I add it to an ArrayList of Integers. Then I used a for loop to go through all the numbers between 3 and the given number inclusive. To check if the current number is prime I used a step wise test:

Steps:

• Check is the number is even
• If it is then it cannot be prime
• Find the square root of the number
• Check all numbers from the prime list already built and the sort
• If it is evenly divisible by an of these numbers it is not prime
• If it passed the above test then it is prime

Full Code:

import java.util.*;

public class PrimeNumGen {

/* this class takes in 2 numbers for a range, it generates and prints

all the prime numbers in the range given */

public static boolean isPrime(int i, ArrayList<Integer> list){

// this function check if a number if prime

if (i % 2 == 0 && i != 2){

// if the num is divisible by two it is not prime

// unless the num is two

return false;

}

// check all numbers between the number and its sqrt

// if the num is divisble by any of these then it is not prime

int sqrt;

if (Math.sqrt(i) % 0 != 0){

sqrt = ((int) Math.sqrt(i)) + 1;

}

else{

sqrt = (int) Math.sqrt(i);

}

int index = 1;

while (index < list.size() && list.get(index) < sqrt){

if (i % list.get(index) == 0){

return false;

}

index++;

}

return true;

}

public static void main(String[] args) {

if (args.length != 1){

// exit if the command inputs are invalid

System.err.println("Invalid Arguments.");

return;

}

int n;

try{

// try to pull the range

n = Integer.parseInt(args[0]);

  }

catch (NumberFormatException e){

// if the given arguments are not ints print an error and exit

System.err.println("Arguments must be integers.");

return;

}

// if either number is negative print an error

if (n < 0){

System.err.println("Arguments cannot be negative.");

return;

}

ArrayList<Integer> primes = new ArrayList <Integer>();

primes.add(2);

// for each number in the range check if the number is a prime

for (int i = 3; i <= n; i++){

if (isPrime(i, primes)){

primes.add(i);

}

}

for (int j = 0; j < primes.size(); j++){

System.out.println(primes.get(j));

}

}

}

Game FFX HD Remaster

It's time to rehash and revisit the "old". For all of you Square Enix fans that means the HD remastering of possibly, in my opinion, the greatest of the Final Fantasies. This game is amazingt; it is literally my childhood. No, but actually, this game consumed something like 300 hours of my youth.

http://img2.wikia.nocookie.net/__cb20130322154006/finalfantasy/images/8/81/FFX_X-2_HD_Remaster_Logo.png

Look at that beauty, I know this game technically come out a couple months ago in March, but you know being in College has certain limitations. Plus, if I had my playstation 3 in my dorm, I would likely be failing out of school and have zero friends....yea I have problems. Regardless,  I have never been more excited for a game before. That is until I started to replay it. Ah all the great memories of small 5 pound birds somehow stunning a giant 300 pound Chocobo. For those of you how don't know a chocobo is basically a giant yellow chicken. Here a picture for reference:

Isn't he a cutie? Yea not so much when you need to spend over 5 hours trying to catch balloons and doge birds in order to get the main character's celestial/ultimate weapon. Lord, I hate this part of the game. To this day, I have been unable to complete this race. The overly sensitive controls and homing missile birds make this very difficult. Though I might be a masochist as I still try everyday. 

Okay so I might have been hyperbolizing when I said this game wasn't great, because it is, in fact, fantastic. It's a nice way for people to get acquainted with a great experience. It provides a level of nostalgia for those of us that played in the past and a whole level of entertainment for the new players. Though it should be stated that this game does take a long time depending on how much of a perfectionist you are. The average gamer might find it takes around 50-60 hours to see the ending of the game; however, super completionists can spend over 200+ hours trying to do everything. 

Okay, enough blabbing (for now) and time for a little overview of the game.

Plot:

The story is set place in the land of Spira, assumably named after the so called "spiral of death" that surrounds it. (Get it? Spira - spiral...yep it's super creative and puny...) 

Spira

The reason for all the death is a entity called Sin. What is sin you ask. Well, it's...um well it's a colossal whale like creature with hundreds of eyes and wings and it drops flowers. Basically Sin is the epitome of evil. It was said to be a result of the hedonistic life style of the past and will only disappear once Spira has repented for its sins. Until then Sin will continue to reck havoc on the lands. The only way to make Sin stop for a brief period of time is for a Summoner to defeat Sin through a ritual known as a the Final Summoning. This, however, does not get rid of Sin and after 10 years it returns. FFX revolves a band of guardians on a pilgrimage with a summoner, Yuna, on their way to defeat Sin. 

<To be continued in a later post.>

Problem #2

Problem: Write your own implementation of a queue data structure. The structure must support a constant time add and remove operations as well as a constant time concatenate. Note: a queue is runs under a first in first out (FIFO) algorithm.

Algorithm: The queue could be implemented in two ways: as a linked list or as an array. I choose to use the linked list approach. A linked list is a data structure that consists of a series of linked node classes. My node class consisted of 2 instance variables a string storing the item at the node and a pointer object to the next node in the sequence

Here is the code for my node class:

  class Node

  {

    String item;

    Node next;

  }

Pretty simple, no? I used this class to maintain a linked list.

http://www.cs.usfca.edu/~srollins/courses/cs112-f07/web/notes/linkedlists/ll2.gif

In order to make the linked list behave like a queue, I kept track of two pointer objects to the head and tail of the list. This way when calling the add function, the new item would be added to the tail of the list and then the tail would be update. If the remove function is called the item is removed from the head of the list and the head variable is updated. To add and remove simply involve pointer changes.

To handle the concat function in constant time, I took the lazy route...as we all know lazy is the best way to go. I simply set the next variable in the tail of the first queue to point to the head of the second queue. Then I updated the tail of the first queue to the second queue's tail. This effectively mashes the two queues together.

Full Code:

public class MyQueue

{

  // helper class for the queue

  class Node

  {

    String item;

    Node next;

  }

  

  private Node head = null;

  private Node tail = null;

  // keep track of the number of entries

  private int n = 0;

  

  // add the string to the end of the queue

  public void add(String s)

  {

    Node newNode = new Node();

    newNode.item = s;

    // if this is first entry set it to the head

    if (this.n == 0){

      this.head = newNode;

      this.tail = newNode;

    }

    else if (this.n == 1){

      this.head.next = newNode;

      this.tail = newNode;

    }

    else{

      // update the end of the queue

      this.tail.next = newNode;

      this.tail = newNode;

    }

    // update the number of items in the queue

    this.n++;

  }

  

  // remove and return the string at the head

  public String remove()

  {

    if (this.head == null)

      return null;

    String s = this.head.item;

    // update the head of the queue

    this.head = this.head.next;

    this.n--;

    // return the first string

    return s;

  }

  

  

  // concatenates another queue to this one

  public MyQueue concat(MyQueue other)

  {

    if (this.size() == 0){

      // if the queue is emtpy just set it equal to the other 

      this.tail = other.tail;

      this.head = other.head;

      this.n = other.n;

    }

    else{

      // connect the head of other to the tail of this

      this.tail.next = other.head;

      // update the size

      this.n =  this.n + other.size();

      // update the tail of this

      this.tail = other.tail;

    }

      // empty the other queue

      other.head = null;

      other.tail = null;

      return this;

  }

  

  

  // return the number of items in the queque

  public int size()

  {

    return this.n;

  }

}

Happy Coding!

Problem #1

Problem: Given a file name and a number, n, print out the n most frequnetly occurring words in the file. The algorithm should parse through the file and print the given number of words followed by the number of times the word occurs in the file.

Example: Here is an example of the output I got when I ran my program on the entire text of Jane Eyre (Charlotte Bronte) and an n of 10.

the : 7868
i : 6766
and : 6229
to : 5077
a : 4322
of : 4315
in : 2658
was : 2402
you : 2249
my : 2139

Exciting right? Though this does seem reasonable...I mean who uses the words "endeavoring" and "chiding" 8000 times each in a book? I have to admit that would certainly be interesting a read. 

Algorithm: In order to solve this problem I used a Priority Queue with my own comparable node class in order to draw out the word with the highest frequency.

The class looks like this:

private static class Node implements Comparable{

  String key;

  int freq;

  

  // used by the priority queue

  public int compareTo(Object other){

  Node n1 = (Node) this;

   Node n2 = (Node) other;

  if (n1.freq == n2.freq){

    return 0;

    }

  if (n1.freq > n2.freq){

    return -1;

   }

   return 1;

  }

  }

Note how the compareTo function's output seems a bit off, this is because you want to queue to return the largest frequency. The queue is implemented to pull the smallest item, the change reverses the order of the queue.

Now to find the words and to keep track of the frequencies when parsing through the file, I used a HashMap. The key of the map is the word and the value is the node. Each time you hit a word, you check if it is in the map already, if so you just increment the frequency of the node. If the word is not the map then make a new node and initialize frequency to 1. After parsing the whole file, I iterate through the keys in the map and add each node associated to the key to a priority queue. To finish off simply print n number of keys by pulling the top node from the queue. Happy coding!

Full Code:

import java.util.*;

import java.io.*;

public class PriorityParse {

 /* This class takes in a file name and the number of most freq occuring words

 the program should print. It parses through the file and then prints the given

 number of words followed by the number of times the word occurs in all the

 files. Only works with one file */

 // helper class node for the parsing

private static class Node implements Comparable{

  String key;

  int freq;

  

  // used by the priority queue

  public int compareTo(Object other){

  Node n1 = (Node) this;

   Node n2 = (Node) other;

  if (n1.freq == n2.freq){

    return 0;

    }

  if (n1.freq > n2.freq){

    return -1;

   }

   return 1;

  }

  }

  public static String removePuntc(String s){

  // takes in a word and removes the ending punction

  while(s.endsWith(".") || s.endsWith("!") || s.endsWith("?") || s.endsWith(",")){

   s = s.substring(0, s.length() - 2);

  }

  return s;

  }

  public static HashMap<String, Node> parseFile(Scanner s){

  // function parses a file and adds each word to a hashmap

  // the word is the key and the node with the freq is the value

  HashMap<String, Node> map = new HashMap<String, Node>();

  while (s.hasNextLine()){

   // disregard case when looking at a word

   String[] text = s.nextLine().toLowerCase().split("\\s+");

   // loop through the array and update the hashmap

for (int i = 0; i < text.length; i++){

String word = text[i];

word = removePuntc(word);

if (!word.equals("")){

// check if the word is in the hash map

if (map.containsKey(word)){

// if it is in the map update the freq of the node

Node temp = map.get(word);

temp.freq++;

}

else{

// if the word is not in the map add it

Node n = new Node();

n.key = word;

n.freq = 1;

map.put(word, n);

}

}

}

  } 

  return map;

  }

  // main takes in file names as arguments

public static void main(String[] args) {

  // print an error if not enough arguments are given

  if (args.length != 2){

   System.err.println("Invalid Arguments");

   return;

  }

  Scanner scan;

  int n;

  try{

    // try to open the file

   String filename = args[0];

   scan = new Scanner(new File(filename));

   // try to get the number

   n = Integer.parseInt(args[1]);

  }

  catch (FileNotFoundException e) {

   // if the file could not be opened print an error and quit

  System.err.println("Could not open file.");

  return;

  }

  catch (NumberFormatException ex){

   System.err.println("Argument 2 must be an integer.");

   return;

  }

  // parse the file using the helper function

  HashMap<String, Node> map = parseFile(scan);

// load the node in the map into a priority queue

PriorityQueue<Node> queue = new PriorityQueue<Node>();

Set<String> set = map.keySet(); 

for (String s: set){

queue.add(map.get(s));

}

//print the n most freq occuring words

for (int j = 0; j < n; j++){

Node word = queue.poll();

System.out.println(word.key + " : " + word.freq);

}

}

}

Details

Hello,

My name is Cindy or Cinthia (if you want to get formal). I'm just a normal person from Connecticut, the vestigial tail of New York. I attend the University of Toothpaste (aka Colgate). There I am a mathematical economics and computer science double major. I also do other things, but we won't get into the details. I'm starting this blog as a way to pass my employment-less summer! Woo go economy! Anywho, I just thought that I would share some "knowledge". By that I mean that I will mostly be posting coding problems and my solutions which if anyone wants to give criticism to is completely welcome. I, also, am an avid gamer; therefore you all might see some rants and updates for games I am currently playing/throwing my controller at the TV. All in all, I hope you all enjoy!