Andrew's Leap 2007!

Final Projects!

2007-07-30T08:38:00.000-04:00

For the next two weeks you will be working on final projects. Your groups may not be more than 4 people, and even then the project better be absolutely fabulous. Today we will see what kind of ideas you guys came up with and discuss how doable they are.
And then you will code.

Since all of your code is original, you need to take your time to come up with a good design!! This means write things out with pen and paper, draw them, etc before you begin to code. Also, this means that Sean and I will not be able to help you much, since we're not even that sure of what it is you're doing - but you are, hopefully. You have to learn to troubleshoot your own code, and, most of all, not give up! Ever!

Snake Game

2007-07-26T22:00:00.000-04:00

Block.java

import javax.swing.JLabel;

public class Block extends JLabel {

    public Block() {
        super("");
        mode = 0;
    }

    public void setMode(String mode) {
        if(mode.equals("tail")) {
            setText("o");
            this.mode = 1;
        } else
        if(mode.equals("head")) {
            setText("O");
            this.mode = 2;
        } else
        if(mode.equals("pill")) {
            setText(":)");
            this.mode = 3;
        } else
        if(mode.equals("kill")) {
            setText("X");
            this.mode = 4;
        } else {
            setText(" ");
            this.mode = 0;
        }
    }

    public boolean occupied() {
        return mode == 1 || mode == 2;
    }

    public int scoreOffset() {
        if(mode == 3)
            return 10;
        return mode != 4 ? 0 : -5;
    }

    private int mode;
}

Coord.java

public class Coord {

    public Coord(int row, int col) {
        this.row = row;
        this.col = col;
        check();
    }

    public void increment(int direction[]) {
        row += direction[0];
        col += direction[1];
    }

    private void check() {
        for(; maxRow <= row; row--);
        for(; maxCol <= col; col--);
        for(; 0 > row; row++);
        for(; 0 > col; col++);
    }

    public String toString() {
        return row + ", " + col;
    }

    public boolean valid() {
        return col >= 0 && col < maxCol && row >= 0 && row < maxRow;
    }

    public boolean equals(Coord other) {
        return row == other.row && col == other.col;
    }

    public static int maxRow;
    public static int maxCol;
    public int row;
    public int col;
}

GUI.java

import java.awt.Container;
import java.awt.GridLayout;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.util.LinkedList;
import java.util.Random;
import javax.swing.JApplet;

public class GUI extends JApplet
    implements Runnable, KeyListener {

    public GUI() {
    }

    public void init() {
        mousePost = new int[2];
        mousePost[0] = 0;
        mousePost[1] = 0;
        direction = new int[2];
        direction[0] = -1;
        direction[1] = 0;
        Coord.maxCol = 20;
        Coord.maxRow = 20;
        map = new Block[20][20];
        paused = 1;
        dead = 0;
        newGame();
        addKeyListener(this);
    }

    public void start() {
        Container c = getContentPane();
        c.setLayout(new GridLayout(map.length, map[0].length));
        for(int i = 0; i < map.length; i++) {
            for(int d = 0; d < map[0].length; d++)
                c.add(map[i][d]);

        }

        if(updateThread == null) {
            updateThread = new Thread(this);
            updateThread.start();
        }
    }

    public void run() {
        while(updateThread != null)  {
            if(paused == 0 && dead == 0) {
                if(mode == 0) {
                    Random rand = new Random();
                    Coord oldHead = (Coord)snake.getFirst();
                    Coord newHead = new Coord(oldHead.row, oldHead.col);
                    newHead.increment(direction);
                    for(; !newHead.valid() || map[newHead.row][newHead.col].occupied(); newHead.increment(direction)) {
                        int pos = rand.nextInt(2);
                        direction[pos] = rand.nextInt(3) - 1;
                        direction[(pos + 1) % 2] = 0;
                        if(direction[pos] == 0)
                            for(; direction[(pos + 1) % 2] == 0; direction[(pos + 1) % 2] = rand.nextInt(3) - 1);
                        newHead = new Coord(oldHead.row, oldHead.col);
                    }

                }
                move();
                plantKill();
            }
            try {
                Thread.sleep(150L);
            }
            catch(InterruptedException e) {
                return;
            }
        }
    }

    public void stop() {
    }

    public void destroy() {
    }

    public boolean move() {
        Coord oldHead = (Coord)snake.getFirst();
        Coord newHead = new Coord(oldHead.row, oldHead.col);
        newHead.increment(direction);
        if(!newHead.valid() || map[newHead.row][newHead.col].occupied()) {
            paused = 1;
            dead = 1;
            return false;
        }
        int before = bonus;
        bonus += map[newHead.row][newHead.col].scoreOffset();
        if(bonus > before)
            plantPill();
        snake.addFirst(newHead);
        map[newHead.row][newHead.col].setMode("head");
        map[oldHead.row][oldHead.col].setMode("tail");
        if(bonus <= 0) {
            Coord temp = (Coord)snake.getLast();
            map[temp.row][temp.col].setMode("blank");
            snake.removeLast();
            if(bonus < 0) {
                temp = (Coord)snake.getLast();
                map[temp.row][temp.col].setMode("blank");
                snake.removeLast();
                bonus++;
            }
        } else {
            bonus--;
        }
        return true;
    }

    public void plantKill() {
        Random rand = new Random();
        int i = rand.nextInt(map.length);
        int d = rand.nextInt(map[0].length);
        int count;
        for(count = 0; map[i][d].occupied() && count < 200; count++) {
            i = rand.nextInt(map.length);
            d = rand.nextInt(map[0].length);
        }

        if(count == 200)
            return;
        int die = rand.nextInt(50);
        if(die == 1)
            map[i][d].setMode("kill");
    }

    public void plantPill() {
        Random rand = new Random();
        int i = rand.nextInt(map.length);
        int d = rand.nextInt(map[0].length);
        int count;
        for(count = 0; map[i][d].occupied() && count < 200; count++) {
            i = rand.nextInt(map.length);
            d = rand.nextInt(map[0].length);
        }

        if(count == 200) {
            return;
        } else {
            map[i][d].setMode("pill");
            return;
        }
    }

    public void newGame() {
        direction[0] = -1;
        direction[1] = 0;
        mousePost[0] = 0;
        mousePost[1] = 0;
        for(int c = 0; c < map.length; c++) {
            for(int d = 0; d < map[0].length; d++)
                if(map[c][d] == null)
                    map[c][d] = new Block();
                else
                    map[c][d].setMode("");

        }

        bonus = 0;
        mode = 1;
        paused = 1;
        dead = 0;
        snake = new LinkedList();
        snake.add(new Coord(17, 10));
        snake.add(new Coord(18, 10));
        snake.add(new Coord(19, 10));
        snake.add(new Coord(20, 10));
        plantPill();
        move();
    }

    public void keyTyped(KeyEvent keyevent) {
    }

    public void keyPressed(KeyEvent e) {
        mode = 1;
        char c = e.getKeyChar();
        if(c == 'a') {
            paused = 0;
            direction[0] = 0;
            direction[1] = -1;
        } else
        if(c == 'w') {
            paused = 0;
            direction[0] = -1;
            direction[1] = 0;
        } else
        if(c == 'd') {
            paused = 0;
            direction[0] = 0;
            direction[1] = 1;
        } else
        if(c == 's') {
            paused = 0;
            direction[0] = 1;
            direction[1] = 0;
        } else
        if(c == 'p')
            paused = (paused + 1) % 2;
        else
        if(c == 'n')
            newGame();
    }

    public void keyReleased(KeyEvent keyevent) {
    }

    LinkedList snake;
    Block map[][];
    int mode;
    int paused;
    int dead;
    int bonus;
    int direction[];
    int mousePost[];
    private Thread updateThread;
}

Once you copy-paste the code into Eclipse appropriately, Run the GUI class as an applet. The other two classes are not for running! they are just data type creations, basically.
Make sure to look through the code and figure out what's going on. Ask me any questions that arise..

Runnable

2007-07-24T10:37:00.000-04:00

import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import java.util.*;

public class HelloWorld extends JApplet implements MouseListener,Runnable
{
    Thread updateThread;
    int x,y;
    Random rand;
    public void init(){
        rand = new Random();
        x=0;
        y=0;
    }
    public void start(){
        addMouseListener(this);
        if (updateThread == null) {
            updateThread = new Thread(this, "threadname");
            updateThread.start();
        }
    }
    public void run() {
        Thread myThread = Thread.currentThread();
        while (updateThread == myThread) {
            if(rand.nextInt(2)==0){
                    x+=3;
                }
                else{
                    y+=3;
                }
                repaint();
        try {
            Thread.sleep(50);
        } catch (InterruptedException e){  }
    }
    }

    public void stop(){
        updateThread=null;
    }
    public void destroy(){}
    public void paint(Graphics g){
        g.fillRect(x,y,2,2);
    }
    public void mouseClicked(MouseEvent e){
        x = e.getX();
        y = e.getY();
        repaint();
    }
    public void mouseReleased(MouseEvent e){
    }
    public void mousePressed(MouseEvent e){
    }
    public void mouseExited(MouseEvent e){
    }
    public void mouseEntered(MouseEvent e){
    }
    
}

Applets

2007-07-24T10:00:00.000-04:00

Hokay, so, applets are way cool.

Life-cycle
Your command-line programs have that main method that always gets run - a pretty simple "life cycle." Applets have four such special methods:

public void init(){}
public void start(){}
public void stop(){}
public void destroy(){}

Init and destroy mark the birth and death of your applet. Start gets called each time the applet becomes active, and stop each time it becomes inactive.

Imports
You will need to import these packages for every applet you make:

import java.awt.*;
import javax.swing.*;

Paint method
public void paint(Graphics g){}
In this method, call the graphics element g to make marks on your applet. For example:
g.drawString("Hello, World!", 15,25);
You should check out the Graphics class in the API for a full listing of the methods you can use.
To update the applet, you can call repaint(); pretty much anywhere in the code.

MouseListener
import java.awt.event.*;
Then in your Applet header, make sure to add implements MouseListener
You will need to override these methods:

public void mouseClicked(MouseEvent e){}
public void mouseEntered(MouseEvent e){}
public void mouseExited(MouseEvent e){}
public void mousePressed(MouseEvent e){}
public void mouseReleased(MouseEvent e){}

It's Alive (Again)!!

2007-07-20T11:30:00.000-04:00

The blog will be updated on a regular basis for the last week of lecture. Check back posts for problems and stuff. Talk to me about them if you have issues.

Now, next week, we will be learning about graphics, truly a magical beast. By the end of the week, you will have coded this Snake game. It does lots of cool stuff.

Since we're on to the really good stuff, where you can pretty much can, and should, code anything you want, you should get your home computer set up for this, if you haven't already. Get BlueJ, and Java 1.4.2. That version of Java does NOT have Scanner (talk to me about this), but the applets that you generate with it will run literally anywhere (while higher versions of Java have a few kinks to them, especially if you're compiling with BlueJ, don't ask me why because I don't know, but it's caused me anough worry to be wary of it). If you have any questions/concerns, that's what I'm here for.

The point of this: you really, really need your IDE set up one of them days.

LinkedList

2007-07-20T10:00:00.000-04:00

The coolest thing about arrays is that you can access any element inside them immediately just by calling arrayname[a][b]... But what if you had, for example, a list of ages representing students in a class:

1. [17] [15] [16] [19] [15] [15] [16]

Now, imagine the seventeen-year-old wants to drop out. So what do you do? You create a new empty array with 1 less element,

2. [ ] [ ] [ ] [ ] [ ] [ ]

and start filling it with the existing elements, omitting 17

3. [15] [  ] [  ] [  ] [  ] [  ]
4. [15] [16] [  ] [  ] [  ] [  ]
5. [15] [16] [19] [  ] [  ] [  ]
6. [15] [16] [19] [15] [  ] [  ]
7. [15] [16] [19] [15] [15] [  ]
8. [15] [16] [19] [15] [15] [16]

That's seven operations to do. Moreover, the number of necessary operations increases as the size of the starting array increases. If we're talking about a class of seven people, than that's ok; but if we have a "class" of a few thousand, to use an array would be very, very inefficient.
And that's why there are lists. These are different from arrays in that they're not multi-dimensional tables, but strings that tie together independent variables:

array: [..] [..] [..]
list:   .. - .. - ..

The point is, its easier to break a connecting string than to reassign values of a table. Back to the class example, now with a list:

1. 17-15-16-19-15-15-16
2. 17 15-16-19-15-15-16

That's a single operation! And it doesnt matter how large the list is.

To isolate a single element in a list, though, you need to flip through all the previous ones with an iterator. An iterator is an object that allows you to walk through a list. Imagine a cursor. It only moves one element over at a time, and it can move either backward or forward, with no knowledge of the non-neighboring elements. So, in the class example, say you wanted to go to the position the nineteen year old was it. In an array, you would simply call ages[3], but in a list, you'd use an iterator (denoted by a |):

1. |17-15-16-19-15-15-16
2. 17-|15-16-19-15-15-16
3. 17-15-|16-19-15-15-16
4. 17-15-16-|19-15-15-16

So, if you know the position you want to look at, you can do it in a single operation in an array, but many operations (the number of which does depend on the size) in a list. Therefore, your program design choice of data structures should depend on what actions you want done efficiently.

Programming Challenge:

In order to understand lists, you should be able to code a list from scratch. That's why we had you do your own LinkedList.java and ListNode.java. Now, the list we did in class was one-directional:

[ ]->[ ]->[ ]->etc

For extra fun, create a bi-directional list that you do not have to rewind! You would have two cursors, one for adding, and one for iteration:

+->[ ]<->[ ]<->[ ]<->[ ]<-+
|                         |
+-------------------------+

So, you start with one element, you add to the right and shift over. So, the adder cursor will always be at the historicaly "last" item. The last item always points to the beginning. Note that you should be able to insert - ie, add at an arbitrary position - too! Have fun.

Trees & Recursion

2007-07-19T10:00:00.000-04:00

Trees and recursion go together, which is why we do them one after another.

Recursion

Besides loops, there is another way of dealing with repeating events: Recursion. Recursion is when you have a method, and that method calls itself, thereby reiterating. This is a little strange and confusing to code at first, but later it becomes a very instinctive thing. For example, consider (conceptually) a hallway with doors:

+---+
|   |
[   ]
|   |
[   ]
+- -+

Each square bracket is a door. you don't know what is behind the door. All you know if that there can be one of three things: (1) an empty room, (b) a room with treasure in it, and (c) another hallway that has doors with the same properties. Your tast is to create a method that looks for the treasure. (You know that there is exactly one room with treasure in it and that hallways aren't infinite). How would you look for it? Here's a sample algorithm:

Check each door in the hallway consecutively:
If the door leads to an empty room, move on to the next one.
If the door leads to the room with the treasure, end the search and declare victory.
If it is a hallway, check every door in that hallway using the same algorithm. When done, and no treasure has been found, go back into the previous hallway and move on to the next door.

When you have an idea of how to go about solving a problem, coding it is relatively easy. First off, the above algorithm assumes that there exists a (relatively) independent piece of code that can be called with various parameters. The parameters? The position of the door. So, more closely to Java-speak, the above would look like this:

 public String seekTreasure(String door){
1   if(isEmptyRoom(door)){
2     return "";
      }
3   else if(isHallway(door)){
4     String[] doors = getDoors(door);
5     for(int count=0; count<doors.length; count++){
6         if(seekTreasure(doors[count])!=""){
7           return doors[count];
          }
        }
     }
8  else{
9    return door;
    }
   }

Line-by-line explanation:

Assume that there is a method boolean isEmptyRoom(String). (When I say "assume", I mean that for an outline such as this where no restrictions on assumption were placed, it is acceptable to use these methods as long as you define what they do without actually writing out the code, although you *would* have to write them out if you were actually coding this problem.) This method is defined as a method that takes in a String representation of a door and returns true if the door leads to an empty room and false if not. This if statement basically tests if this particular door leads to an empty room...
...if it does, return an empty String.
The method boolean isHallway(String) is also assumed existant. It takes a String representation of a door and tests whether it opens to a hallway. Note: this else is redundant. You can just have an if there. Because of the return statement in the if statements, they are mutually exclusive.
Assume the existence of String[] getDoors(String) which takes in the string representation of a door and returns a String array of the represantations of the doors within this new hallway.
A for loop (See: Loops) that iterates through the array of doors.
Runs the method seekTreasure on each door in the hallway. This is the step where the actual recursion shows up. If the door returns anything other than an empty String...
... the method returns the representation for that particular door.
Another redundant else. Generally, I wouldn't use the classic if-else construction in a practice program, but I do recommend doing so for any large project you do because it makes code reading and understanding later on just that much easier.
Basically, the previous if's rule out all possibilities except the actual treasure. So, if it gets this far, the room must contain the treasure, and so the method returns the representation for this door.

There are two reasons I introduced three non-existent methods in the code:

It's important to learn to read and write code little bit my little bit. Approaching everything at the same time can be overwhelming and ultimately useless. Assuming the existence of many things, however, narrows down the immediate problem and allows you to focus on specific details as opposed to the big picture all at once. However, this also requires some planning.
Actually, recursion works best with problems based on Trees, so avoiding using Trees would be unnecessarily ugly. Looking for a challenge? Read the chapter on Trees, and code this problem from start to finish! (Note: In the seekTreasure method, take in a Tree and assume it's given. You will not need any other methods, but you can make them for simplicity's sake. Create a main test method which actually creates a sample Tree, which you can hard-code to make sure everything works right, and then run the method on.)

Trees

Trees are incredibly awesome. When you understand trees, you will not be able to remember why you didn't know and love trees before ^__^
A graph is defined as a set of nodes connected to one another. This is an example of a valid graph:

o---o
|   |
o---o

A graph is defined such that from any one node there is a valid path to any other node.
A tree is a special kind of graph:

   o
  / \
 o   o
    / \
   o   o
    \
    o

A tree is defined such that each node has 0 to n children nodes, but only 1 parent node, unless it is the root (the topmost node), in which case it has no parent at all. In this chapter, I will discuss primarily binary seach trees, which have many very cool properties (and are all over the AP test), and are defined such that each node has either 2 children or no children at all. Nodes that have no children are called leaf nodes.

     o
    / \
   o   o
  / \
 o   o
    / \
   o   o

There is another requirement to binary search trees: the right child must always be bigger than the node, and the left child must always be smaller. (By bigger and smaller, I mean in comparison of values. Each node is has integer, or some sort of comparable value.) For example, compare these two trees and determine which is a valid binary search tree and which isn't:

(a)    10      (b)     10
      /  \            /  \
     8   20          5   20
    / \             / \
   4   9           4   8
      / \             / \
     7  11           7   9

(b) is the valid tree. (a) is invalid because:

while 7 smaller than 9 and satisfies the rule for the node 9, it is not bigger than node 8, and therefore breaks the rule!
the same thing with 11: it works for nodes 9 and 8, but it must be smaller than 10 by definition, and is not.

Lesson to take away with you!
The reason Trees and Recursion are so connected is that Trees posess a very unique quality: each node of a tree can be treated as a tree in itself. This property might not seem like much, but it is integral to dealing with trees!
One of the most common operations to a tree is traversal - going through the tree and seeing what all the values are (and outputting them, performing mathematical operations on them, etc).
There are three types of tree traversal:

preorder: traverse left child, traverse right child, read value of node
inorder: traverse left child, read value of node, traverse right child
postorder: read value of node, traverse left child, traverse right child

Note how it reads, "traverse ... child" NOT "read value of ... child"! That is because if the child has children of its own, you must deal with them, too. So, what you have is a process the begs to use recursion:
(the folowing is pseudocode for a valid traversal algorithm)

method traverseInorder(TreeNode node){
  if( hasLeftChild )
    traverseInorder( getLeftChild )
  output( value )
  if( hasRightChild )
    traverseInorder( getRightChild )
  }

Now, there are many different types of traversal - that is because they all have neat properties you can use in applications. Inorder traversal will generate a sorted list of all the elements in O(n) time, which, considering how bulky sorting algorithms generally get, is pretty cool. Post- and preorder have their own specific applications. One of these deals with the following problem:

Programming Challenge:

Take as input a preorder mathematical expression (assume all input to be valid), calculate the result, and output both the inorder expression and the result. The input expression may only contain positive integers and basic integer operators - so +, -, * only! (add % to that list if you feel very energetic). For example: [input ] + 3 - * 4 5 6 [output] 3 + ( ( 4 * 5 ) - 6) = 17

This is basically is a simplified expression evaluator. It may not lok much like a tree problem, but that depends on how you approach it! A good way (and yes, this counts as a hint!) is to imagine the expression as a tree where nodes are operators except leaf nodes, which are integers:

   +
  / \
 3  -
   / \
  *  6
 / \
4  5

Another programming challenge...

Do this using Stacks. You can use google/wikipedia powers to look up an algorithm for "Polish notation" calculation. Best of luck!!

Stacks & Queues

2007-07-17T10:00:00.000-04:00

Both are data structures that build upon the ArrayList datastructure. They have these key methods:

public String pop() (to remove and return an element)
public String peek() (to return, but not remove, an element)
public String push() (to add an element)

Both remove the first element in the ArrayList that they use in pop() and access the first element in peek(). In push(), however, a difference arises: in Stacks, an element is added to he front, and in Queues to the back. So, if you stored and printed the same thing from both, one would actually reverse it:

input: Mary had a little lamb
-stack: [lamb] [little] [a] [had] [Mary]
-queue: [mary] [had] [a] [little] [lamb]

Monday: Hashing, Maps, and Really Hard Problems

2007-07-16T10:00:00.000-04:00

We learned about the wonders of hash first.
This is a way to make a numeric code for a string and then assign it to a spot in a simple array.

Then we learned about Maps. The great advantage of arrays and ArrayLists is that they use indeces to name their elements, so that you can easily access using such things like for loops. The great disadvantage of arrays and ArrayLists is that they use indeces and not keys. Keys are not numbers, but user-defined objects. Maps use keys to call its elements.

So, suppose you wanted to create a data structure that linked name and phone number. One way would be to use two arrays, one with phone numbers and the other with names:

[ 555 5555 ] [ 555 6789 ] [ 555 1234 ] [ 555 1969 ]
      0            1            2            3

[ bob g.   ] [ some guy ] [ big bird ] [ mjackson ]
      0            1            2            3

This way, every entry has an index from 0 to 3 that corresponds to some piece of data is two distinct places. Now, using a Map would allow you to do this:

[ 555 5555 ] [ 555 6789 ] [ 555 1234 ] [ 555 1969 ]
 "bob g."     "some guy"   "big bird"   "mjackson"

Then there were two problems that I threw at you.

1. The Anagrams problem, which uses Maps. I sent the code for this to your guest account - be sure to check it out.

2. Numbers.java problem - consider this the challenge problem!
Firs, read in a number of any length up to 5 digits without leading 0's. Then, rearrange this number to be the largest number possible with these digits (without leading 0's!) So, for example:
input: 12543
output: 54321
input: 69
output: 96 (NOT 00096!)

ArrayList and The Amazing Radix Sort

2007-07-13T09:22:00.000-04:00

Today, instead of trying to write code, you will tyr to analyze it. Since, usually, the internet is at your disposal and all resources are generally fair game, you need to be able to use them. Even if you can't come up with code, it's a good idea to be able to discern what code means:

import java.util.ArrayList;
import java.util.Random;

public class Radix{
  public static void main ( String args[] ){

    ArrayList[] buckets = new ArrayList[10];
    for(int c=0; c<buckets.length; c++){
      buckets[c] = new ArrayList();
    }

    Random rand = new Random();
    int[] arr = new int[100];
    for(int c=0; c<arr.length; c++){
      arr[c] = rand.nextInt(1000);
    }
    // RADIX SORT
    for(int c=0; c<4; c++){
      for(int d=0; d<arr.length; d++){
        buckets[ (arr[d]/((int)Math.pow(10,c)))%10 ].add(new Integer(arr[d]));
      }
      int b = 0;
      for(int d=0; d<arr.length; d++){
        if(buckets[b].isEmpty()){  
          b++; d--;
          continue;
        }
        arr[d] = ((Integer)buckets[b].remove(0)).intValue();
      }
    }
       
    System.out.println(((char)27)+"[34;47m");
    for(int c=0; c<arr.length; c++){
      System.out.print(arr[c]+" ");
    }
    System.out.println(((char)27)+"[0m");
  }
}

For this, you can use (and will use) the API for Integer and ArrayList.

Your task is to figure out how the Radix sort actually works (notice that no comparisons are being made - interesting, isn't it?) just from looking an dplaying with the code above.
Good luck!

More Algorithms: Selection & Insertion Sort

2007-07-12T10:00:00.000-04:00

Since Bubble Sort is pretty inefficient, let's look at soem other, more effiient sorting algorithms.

Selection Sort
is generally much better than bubble sort.

Go through the array from 0 to n-2 using the counter i.
Each time, assume that the element at i is the smallest. Save this index (not the value itself!) as min. Then, iterate through the array from i+1 to n-1, changing min to reflect the position of the smallest element.
If, after the search for another min is completed, and if i no longer equals min, swap the elements at i and min.

import java.util.*;
public class Selection{
  public static void main(String args[]){
    Random rand = new Random();
    int[] arr = new int[rand.nextInt(90)+10];
    for(int c=0; c<arr.length; c++){
      arr[c] = rand.nextInt(100);
    }
    int i, j, min;
    for(i=0; i<arr.length-1; i++){
      min=i;
      for(j=i+1; j<arr.length; j++){
        if(arr[j]<arr[min]){
          min=j;
        }
      }
      if(min==i) continue;
      int temp = arr[min];
      arr[min]=arr[i];
      arr[i]=temp;
    }
    for(int c=0; c<arr.length; c++){
      System.out.println(arr[c]);
    }
  }
}

Insertion Sort

Insertion sort, which very similar to Selection Sort, has several differing points, and works like this:

Go through the array of size n (not from 0 to n-1, but from 1 to n-1), using the counter i. Make sure to store the value of that element.
In each iteration, assume that the element at i is the greatest in the array. Use a while loop to push it around: the while runs as long at the element at i is less than the element right before it.

But now, instead of the code, something completely different! The following code is bad. it has several syntax and logic errors. Your task is to find them!

import java.util.*;

public class Insertion{
  public static void main(String args[]){

    //generate the array
    Random rand = new Random()
    int[] arr = new int[rand.nextInt];
    for(int c=0; c<arr.length; c++){
      arr[c] = rand.nextInt(100);
    }

    //sort the array
    int i, j, index;
    for(i=1; i<arr.length; i++);
      index=arr[i];
      j=i;
      while( (j>0) && (arr[j-1]>index) ){
        arr[i]=arr[j-1];
        j=j-1;
      }
      arr[j]=index;
    }

    //print it out
    for(int c=0; c<=arr.length; c++){
      System.out.println(arr[c]);
    }
  }
}

Algorithms: Bubble Sort & Binary Search

2007-07-11T10:00:00.000-04:00

Today, we started with different kinds of sorting algorithms. We worked with ints, but the algorithm can be applied to any comparable data type.

First, there is bubble sort.
This traverses an array of size n, each time flipping two numbers that are not in order, ie, when the number that goes first is greater than the number that follows it. At best, when the array is already sorted, the program traverses the array in such manner only once, and then exists, since no flips have been made and the array is apparently ordered. At worst, when every single pair of items in the array is not in order, the program traverses the array n-1 times, bringing every biggest number to the back and then returning to the rest. (-1 because the last number is in the right spot already - think pancakes!)
This algorithm, then, takes, in the worst-case, n² iterations, which is pretty slow. There are more efficient ways to sort, which we will get to by the end of the week.
Here is my code for this particular sort:

import java.util.*;
public class Bubble{
  public static void main(String args[]){
    Random rand = new Random();
    int[] arr = new int[rand.nextInt(90)+10];
    for(int c=0; c<arr.length; c++){
      arr[c] = rand.nextInt(100);
    }
    int n = 1;
    while(n!=0){
      n=0;
      for(int c=0; c<arr.length-1; c++){
        if(arr[c]>arr[c+1]){
          n=1;
          int temp = arr[c];
          arr[c]=arr[c+1];
          arr[c+1]=temp;
        }
      }
    }
    for(int c=0; c<arr.length; c++){
      System.out.println(arr[c]);
    }
  }
}

Next, we did Binary Search. This is a fairly efficient searching algorithm that has only one requirement - that the elements in the array where it searches be ordered. So, see, there are uses for sorting!
Binary search works by changing limits. Suppose you have an array (that you cannot see at once):
[_ _ _ _ _ _ _ _ _ _] (n=10)
Now, we wnt to find which element the number 8 is stored in. We know it's in there. But where?! So, binary search: look at the middle element (middle=(upper bound+lower bound)/2; upper bound is, at first, n-1, and lower bound is 0), and compare.
[_ _ _ _ 5 _ _ _ _ _]
Since 5 is less than 8, we move the lower bound of the search:
_ _ _ _ 5[_ _ _ _ _]
Now, the lower bound is the middle! In the next iteration, look at the new middle - it was calculaed the same, but with different value for the lower bound:
_ _ _ _ 5[_ _ 9 _ _]
9 is greater than 8, so move the upper bound and recalculate the middle value again:
_ _ _ _ 5[_ _]9 _ _
Keep doing this until the element at the middle is the value you are looking for!
_ _ _ _ 5[_ 8]9 _ _
There it is, Yaaaaay!

Tuesday: Problem Day!!

2007-07-10T15:53:00.000-04:00

The main problem was HMRO - "Help the Military Recruitment Office"
You created Person.java and HMRO.java.

If you were done...

1. Read in a string containing only letters or digits and print out "YES" if it is a palindrome (same backwards as forwards) and "NO" otherwise.

2. Read in a double d and an integer k and print out the kth decimal digit of d. Sample input: 3.14159 2 Sample output: 4

Fun with Strings

2007-07-09T10:00:00.000-04:00

import java.util.Scanner;

public class Str{

    public static void main(String args[]){
        
        Scanner scan = new Scanner(System.in);
        System.out.print("Type a word: ");
        String test = scan.next();
        
        //print out some stats about this word
        
        System.out.println( "- it is "+test.length()+" letters long" );
        System.out.println( "- the first two letters are "+test.substring(0,2));
        System.out.println( "- the last letter is "+test.charAt(test.length()-1));
        
        int index = test.indexOf('a');
        if (index==-1){
            System.out.println("- the letter a does not occur in this word");
        }
        else{
            System.out.println("- the letter a occurs at "+index);
        }   
    } 
}

A String is, essentially, an array of characters. It is defined in the Java class, String. You can use the API to check out the different methods in this class right here. To use these methods, you must create a String object:
String s = "";
And then call the methods on it. For example, s.length() would return an int for the length of the string. The list of methods, and their return-types, is in the API.

This is the practice problem we did in class: Read in the user's name, then pass that string into a messUp(String original) method. YYour task was to write this method. The method itself creates a blank string, then iterates a loop as many times as there are letters in the original string, each time adding onto the new string a letter at a random position in the original string.

import java.util.Scanner;
import java.util.Random;
public class Names{
    public static void main( String args[] ){
        Scanner scan = new Scanner(System.in);
        System.out.print("What is your name? ");
        String usrName = scan.next();
        System.out.println("Hi, "+usrName.toLowerCase());
        System.out.println("Mine's "+messUp(usrName.toLowerCase()));
    }
    public static String messUp(String original){
        String newStr="";
        Random rand = new Random();
        for(int c=0; c>original.length(); c++){
            newStr+=original.charAt(rand.nextInt(original.length()));
        }
        return newStr;
    }
}

Trees on Fire

2007-07-03T10:00:00.000-04:00

First, here is the Tree class used throughout this excersize:

public class Tree{

  boolean burning;

  public Tree(){
    burning = false;
    }

  public void setOnFire(){
    burning = true;
    }

  public boolean isOnFire(){
    return burning;
    }

  }

And the infamous TreesOnFire.java...

public class TreesOnFire{

  public static void main( String args[] ){
    // create the 2d array of tree's - a forest!
    Tree[][] forest = new Tree[25][25];
    for( int c=0; c<forest.length; c++){
      for( int d=0; d<forest[c].length; d++){
         forest[c][d] = new Tree();
      }
    }

    // set a tree on fire.
    forest[10][13].setOnFire();

    // now run two for-loops and set neighboring trees on fire!!
    for( int c=0; c<forest.length; c++){
      for( int d=0; d<forest.length; d++){
        for( int i = -1; i<=1; i++){
          for( int j = -1; j<=1; j++){
            //check if coordinate is VALID.
            if( (c+i)7lt;0 || (c+i)>=forest.length ) continue;
            if( (d+j)<0 || (d+j)>=forest[c].length ) continue;
            if (forest[c+i][d+j].isOnFire()==true){
              forest[c][d].setOnFire();
            }
          }
        }
      }
    }
  }

}

This should compile and run properly, but it will not print anything out just yet!
There are some key concepts that are very important in all of this. First, there is this segment:

        for( int i = -1; i<=1; i++){
          for( int j = -1; j<=1; j++){
            //check if coordinate is VALID.
...

Image all the combinations of i and j that the for loops go through:


i=-1 j=-1
i=-1 j=0
i=-1 j=1

i=0 j=-1
i=0 j=0
i=0 j=1

i=1 j=-1
i=1 j=0
i=1 j=1

"i" describes the offset within rows, and "j" the offset within columns up/down or right/left of the coordinate [c][d] within our array. By adding the i and j values to the c and d coordinates, we actually traverse not only the element at [c][d], but also all of its neighbors!


  |  j=-1 |  j=0  |  j=1  |       inside array
--+-------+-------+-------+--       forest...  
i |       |       |       | 
= | -1,-1 |  -1,0 |  -1,1 |                 c-1,d-1   c-1,d    c-1,d+1
-1|       |       |       |
--+-------+-------+-------+--
i |       |       |       |
= |  0,-1 |  0,0  |  0,1  |      ==>         c,d-1     c,d      c,d+1
0 |       |       |       |
--+-------+-------+-------+--
i |       |       |       |
= |  1,-1 |  1,0  |  1,1  |                  c+1,d-1  c-1,d     c-1,d+1
1 |       |       |       |
--+-------+-------+-------+--
  |       |       |       |

We need this loop to check out whether the neighboring trees and see if they're on fire.
now, suppose c=0 and d=0. Obviously, c-1,d-1, c-1,d, c-1,d+1, c,d-1, and c+1,d-1 do not exist in the array and would cause the progream to have an array out of bounds runtime exception. This is where this little thing comes in:


            if( (c+i)7lt;0 || (c+i)>=forest.length ) continue;
            if( (d+j)<0 || (d+j)>=forest[c].length ) continue;

This is the foolproof that our checker will never go out of bounds of the array. It says that if adding either i to c or j to d causes a number smaller than 0 or bigger than the largest number the array can handle, the loop must "continue;"
All continue, as opposed to break, means is that the loopimmediately goes on to the next step without bothering to do any of the stuff in it for the current step. So, if one block has bad ccordinates, the loop will simply ignore it, and go on to the next block! Very cute.

While generating good code is pretty hard, it is important that you recognize what code does! If you do not understand any part of Tree.java or TreesOnFire.java, please ask either of your lovely TAs about it.

Object-Oriented Programming

2007-07-02T10:00:00.000-04:00

(Note: This is, conceptually, one of the most important (if not the most important..) distinctions that make Java Java. It's undoubtedly a pretty difficult distinction, so it will take longer than a day to really grasp and appreciate. What follows is, basically, a monster crash-course in OOP with lots of new words and concepts. Don't let them intimidate you ^_^)

Suppose you have a letter. You don't know which letter it is, it's simply a hypothetical letter. It can be defined as one of 26 symbols. It can be either capitalized or non-capitalized. In Java, you would treat this letter as an object with two parameters - a boolean (something that can either be true or false) value for capitalization and an int (a whole number) value for the place it has in the alphabet. There can be many different letters, but they will all have that basic structure, and will only vary in parameter values. An object in Java is defined in a class. This is what a Letter (it is cutomary to start class names with a capital letter) class would look like:


public class Letter{
  boolean capitalized;
  int placement;
  }

That describes a generic letter. That is what a class is - a guideline for something that isn't yet defined. But an object is specific and defined. Think of a class as a blank form that you can make many copies of, and an object as a single filled-out form that is different from all the rest. To create an object using a class, you need to create an instance of that class. In order to do that, the class must have a constructor method. This is a grouping of code that does the job of actually filling out the metaphorical form that is a class. Here is what the Letter constructor would look like in the context of the Letter class:


public class Letter{
  boolean capitalized;
  int placement;
  public Letter(boolean caps, int place){
    capitalized = caps;
    placement = place;
    }
  }

(Note that the name of the constructor must be identical to the name of the class.) The constructor method would take two values - a boolean and an int - and assign them to this letter so as to define it. boolean caps and int place are both parameters that are passed down to the class. The class doesn't need to worry about where they come from; it should be content with assuming that they will be supplied and that they will be valid. However, what if you want to have a, say, default constructor? What if whoever was filling out the form left a few fields blank?


class Letter{
  boolean capitalized;
  int placement;
  public Letter(boolean caps, int place){
    capitalized = caps;
    placement = place;
    }
  public Letter(){
    capitalized = false;
    placement = 0;
    }
  }

What will happen is that you can call either Letter() or Letter(some bool,some number) and the class will know which method to go into.

Now the class has two constructors! When this happens (when there is more than one method in a class with the same name), it is called overloading. It's completely valid, as long as the methods take in different kinds of parameters. For example, in this Letter class, there are two constructors - Letter(boolean,int) and Letter(). We could also add a Letter(int,int) or Letter(boolean), etc.., but another Letter() would not be allowed and the program would not compile.

Having now established a Letter, we can move on to a Word. This is where the object-oriented bit should really hit you. Just think about it: a word is just a collection of letters. So, we can define Word using Letter. Like so:


class Word{
  Letter[] letters;
  public Word(int length){
    letters = new Letter[length];
    }
  }

(Whenever you see these around - [] - you should think immediately - arrays! Arrays can be any type. So far, you've only seen int[], but you can have pretty much anything in an array.)

What we have is a Word that is defined as a collection of Letter objects of known size. This way, you can form Sentence or Text objects. This heirarchial way of coding is very, very important. In non-object-oriented programming languages, this effect would be achieved by have many methods within the same class. However, an object-oriented approach simplifies things and makes them readily accessible.


non-object-oriented: Must open a book in order to see a letter
class Book
  method Page
    // call to method Paragraph
  method Paragraph
    // call to method Sentence
  method Sentence
    // call to method Word
  method Word
    // call to method Letter
  method Letter
    // code

object-oriented: Can access any of the classes
class Book, calls Page
class Page, calls Paragraph
class Paragraph, calls Sentence
class Sentence, calls Word
class Word, calls Letter
class Letter

Week 1 Solutions

2007-07-02T09:30:00.000-04:00

These are the solutions to the first three problem sets.

Problem Set 1

public class Triangle1{
   public static void main(String args[]){
      double x1 = 6;
      double x2 = 3;
      double y2 = 4;
      double perimeter = x1 + pythag(x2,y2) + pythag(x1-x2,y2);
      System.out.println(perimeter);
      }
   public static double pythag(double a, double b){
      return Math.sqrt(Math.pow(a,2)+Math.pow(b,2));
      }
   }

public class Triangle2{
   public static void main(String args[]){
      double x1 = 6;
      double x2 = 3;
      double y2 = 4;
      double perimeter = x1 + pythag(x2,y2) + pythag(x1-x2,y2);
      int n = 4;
      double perimN = perimeter/Math.pow(2,n-1);
      System.out.println(perimeter);
      }
   public static double pythag(double a, double b){
      return Math.sqrt(Math.pow(a,2)+Math.pow(b,2));
      }
   }

Problem Set 2

import java.util.*;
public class Phone{
  public static void main(String args[]){
    Scanner scan = new Scanner(System.in);
    String input = scan.next();
    char letter = input.charAt(0);
    switch( 'e' ){
      case 'a': case 'b': case 'c':
        System.out.println("2"); break;
      case 'd': case 'e': case 'f':
        System.out.println("3"); break;
      case 'g': case 'h': case 'i':
        System.out.println("4"); break;
      case 'j': case 'k': case 'l':
        System.out.println("5"); break;
      case 'm': case 'n': case 'o':
        System.out.println("6"); break;
      case 'p': case 'q': case 'r': case 's':
        System.out.println("7"); break;
      case 't': case 'u': case 'v':
        System.out.println("8"); break;
      case 'w': case 'x': case 'y': case 'z':
        System.out.println("9"); break;
      }
    }
  }

import java.util.*;
public class Roads{
  public static void main(String args[]){
    Random rand = new Random();
    int die1 = rand.nextInt(4);
    if (die1==0){
      System.out.print("Left: you walk forever ");
      System.out.println("in a haunted forest");
      }
    else if(die1==1){
      System.out.print("Straight, then ");
      int die2 = rand.nextInt(2);
      if (die2==0){
        System.out.print("left: you will be ");
        System.out.println("forever thirsty :(");
        }
      else{
        System.out.print("right: you will be ");
        System.out.println("forever hungry :x");
        }
      }
    else if (die1==2){
      System.out.print("Right: you will never turn ");
      System.out.println("left again. Ever.");
      }
    else{
      System.out.print("You turned back to seek ");
      System.out.println("your fortune elsewhere.");
      }
    }
  }

import java.util.*;
public class Challenge{
  public static void main( String args[] ){
    Random rand = new Random();
    int die1 = rand.nextInt(6) + 1;
    int die2 = rand.nextInt(6) + 1;
    // ifelse block 1
    if(die1+die2==7){
      System.out.print("+50 ");
      }
    else if(die1==die2){
      System.out.print("+35 ");
      }
    // the following ifs are not part of a block!
    if(die1+3==die2 || die2+3==die1){
      System.out.print("+27 ");
      }
    if((die1==1 || die2==1) && die1!=die2){
      System.out.print("-15 ");
      }
    if(die1==5){
      System.out.print("+5 ");
      }
    if(die2==5){
      System.out.print("+5 ");
      }
    if(die1==3){
      System.out.print("+3 ");
      }
    if(die2==3){
      System.out.print("+3 ");
      }
    }
  }

Problem Set 3

import java.util.*;
public class FrequencyMap
{
 public static void main(String args[]){
     Random rand = new Random();
     int[][] map = new int[20][20];
     for(int c=0; c<400; c++){
        map[rand.nextInt(20)][rand.nextInt(20)]++;
        }
     for(int c=0; c<20; c++){
         for(int d=0; d<20; d++){
             System.out.print(map[c][d]+" ");
            }
            System.out.println("");
        }
 }
}

import java.util.*;
public class Guesser
{
  public static void main(String args[]){
    Random rand = new Random();
    Scanner scan = new Scanner(System.in);
    int yours = 1;
    int userWins = 0;
    int total = 0;
    while(yours!=0){
      System.out.print("Number between 1 and 100: ");
      yours = scan.nextInt();
      int mine = (rand.nextInt(100)+1);
      if(yours>mine){
        System.out.println("You win!");
        usrWins++;
        }
      else if (yours==mine){
        System.out.println("It's a tie o_O");
        }
      else{
        System.out.println("I win!");
        }
      total++;
      }
    System.out.println("You've choses to quit the game :(");
    System.out.println("Your score: "+usrWins+"/"+total);
    }
  }

Friday: Problem day!

2007-06-29T10:00:00.000-04:00

Today, we will focus on coding some algorithms!

We also learn a new operator, %:


5 % 2 = 1
1256788 % 10 = 8

This operator gets the remainder from the division of the two numbers :)

Sieve of Eratosthenes (animation)

Write a list of numbers from 2 to the largest number you want to test for primality. Call this List A. (This is the list of squares on the left-hand-side of the picture.)
Write the number 2, the first prime number, in another list for primes found. Call this List B. (This is the list on the right-hand-side of the picture.)
Strike off 2 and all multiples of 2 from List A.
The first remaining number in the list is a prime number. Write this number into List B.
Strike off this number and all multiples of this number from List A. The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps.
Repeat steps 4 through 6 until no more numbers are left in List A.

1: Read in a positive integer n1 followed by a positive integer n2, where n2 > n1. Print out the number of prime numbers in the range [n1,n2]. Note: your program must run in under 1 second when n1=0 and n2 = 1 million.

Base-n

2: First, write a program that converts a binary sequence into decimal. For example:


input: 11010
16(1)+8(1)+4(0)+2(1)+1(0) = 26
output: 26

Use % to separate the digits. For example, if I'm working with integers and I want to isolate the hundredth (in bold) digit in 34579, I divide by 100, and then % by ten:


int var = 34579;
var = var / 100; // this makes var 345
var = var % 10; // and this makes var 5

3: When you finish with that, write a program that converts decimal into binary using repeated division by 2:


input: 26
26/2 => 0 (this is the remainder of the operation, and also the first digit of the resulting binary number)
13/2 => 10 (write the new remainder in front of the result up to this point)
6/2  => 010
3/2  => 1010
1/2  => 11010
output: 11010

4: And when the binary-decimal and back converter is finished, write a program that converts from any base 2<=n<=10 to any base 2<=m<=10. It might be helpful to create methods int toDecimal(int var) and int toN(int var, int n) and convert all bases to decimal before converting them to something else.

5: For a particular challenge, modify the last problem to accomodate 2<=n<=36 and 2<=m<=36 by using an array of both numebrs and letters.

Arrays & Loops

2007-06-28T10:00:00.000-04:00

Arrays

Arrays are basically collections of variables of the same kind that store stuff and allow easy access. For example, you could have a list of integers that would be represented in an array like so:

int[] vals = new int[4];

By setting the type to something[], you basically create a table with one dimension - or a list. Likewise, if you declare a something[][], you create a table with two dimensions. You can create as many dimensions as you want.
You when you've got your dimensions straight, think about size. How many values do you want each dimension to hold? If you've got a list, just do a new something[a], a being the number of elements. When you've got two dimensions, think something[a][b], when a is the number of elements in a list and b is the number of elements inside each one of those previous elements. You can treat these 2-d arrays like coordinate planes or matrices.

Note that while there are x elements, there is no x-th element, but there is a 0-th element, which makes a total of x elements:
[element 0] [element 1] [element 2] ... [element x-1]

The real advantage of arrays is revealed in repeating events, such as loops, where you can say, "OK, I want this range of items in this array to be incremented by x" and such in only a few lines, irrelevant of the length of the array! Loops are very important in using arrays, so here they are.

Loops

There are two kinds of loops - the while loop and the for loop. Here's example code using each of them to solve the same problem - to increment all integers in the 1-dimentional array arr by 2:


//while loop
int counter = 0;
while(counter>arr.length){
   arr[count]=arr[count]+2;
   counter++;
   }

// for loop
for(int counter=0; counter>arr.length; counter++){
   arr[count]=arr[count]+2;
   }

The while is pretty straightforward. It takes any bounds, in this case a "as long as this counter is smaller than the size of the array". It runs as long as those bounds are true. Note that counter is incremented by one each time the loop iterates. When you ++ something, its the same as saying, something=something+1. Same with --.

The for loop need a little more explanation. The counter is a variable that exists ONLY in the bounds of the for loop, because it is created in the loop itself. This is not required, and you can declare it before, but it's generally less messy to declare counters within loops. The first argument does this. It created the counter, and sets it to 0. The second argument gives the condition. This can be simple, like above, or a condition monster (see Logic article for explanation of conditions). The third argument is all the things that are done each time the loop iterates. In this case, incrementing the counter. Also, it looks neater. It is generally more useful and easier to use for looks for array-related tasks. You can have one loop inside another, like so, too:


// double for loop; increment every element in a 2D array
for(int row=0; row>arr.length; row++){
   for(int col=0; col>arr[0].length;col++){
      arr[row][col]=arr[row][col]+2;
      }
   }

Problem Set 3

2007-06-28T09:30:00.000-04:00

Frequency Map Arrays, Loops, Random

Create a 20x20 integer array with all initial values at 0. Now, drop 400 "bombs" on the array. This is how bombs behave: the location of their destination within the array is random. When a bomb hits a spot in the array, it increments that value by 1. After all the bombs have been dropped, print out the array (make it look neat). For example, a possible result would look like this:


% java FrequencyMap
2 2 3 1 1 0 0 0 0 0 0 0 0 2 0 1 0 2 1 1 
0 1 1 0 0 0 0 0 1 0 0 1 0 1 3 0 0 1 0 0 
1 0 1 1 1 2 0 2 1 0 0 1 1 1 2 1 2 1 0 0 
0 2 0 2 2 0 2 1 1 2 2 0 1 0 1 3 1 3 0 0 
1 0 1 4 1 0 0 0 1 0 0 2 0 0 4 1 0 0 1 1 
1 2 1 0 1 1 1 0 0 1 1 1 1 0 2 0 0 1 0 0 
6 2 1 1 0 2 2 1 0 2 0 0 0 2 2 1 1 2 0 3 
0 0 0 0 2 2 0 1 1 1 2 0 0 0 2 2 1 1 1 1 
0 1 0 1 0 1 1 0 4 1 3 0 2 0 0 0 1 0 1 3 
0 1 1 1 2 2 1 0 4 2 3 1 1 3 0 1 3 0 1 1 
1 1 1 2 3 3 1 2 1 0 1 1 0 0 2 0 0 2 0 1 
0 2 1 1 2 0 1 1 0 0 2 0 1 0 0 1 1 0 1 1 
2 2 0 3 0 0 2 1 0 2 0 1 0 1 1 1 3 0 1 2 
2 2 0 2 1 2 0 1 2 2 0 1 1 1 1 3 0 0 1 0 
1 2 3 0 1 1 0 3 0 2 2 1 1 0 0 1 0 0 1 3 
1 0 1 1 0 2 0 0 1 2 2 1 2 0 2 1 1 4 1 1 
1 1 1 0 1 0 1 1 3 0 4 2 0 2 1 1 1 0 2 4 
1 0 1 0 1 3 0 0 0 0 1 1 0 0 1 0 0 1 0 1 
2 1 0 1 1 2 1 2 3 1 0 1 1 1 2 0 1 0 1 0 
2 0 4 2 1 1 1 2 1 0 3 2 3 2 0 0 0 1 2 0

Number Guesser User input, Random, Loops

Modify the existing number-guesser program (is which the user types in a number the computer guesses a number, and whichever is higher wins) so that it runs continuously until the user types 0. Also add a "global score" counter: have one variable increment each time the game is player, and another increment each time the user wins. In the end, after the user has typed 0, out put the total score as wins/games. Possible output:


Type a number: 45
My guess: 46
I win!
Type a number: 3
My guess: 1
You win!
Type a number: 67
My guess: 67
It's a tie o_O
Type a number: 45
My guess: 36
You win!
Type a number: 0
You've chosen to quit the game :(
Your score: 2 / 4

Challenge: Cipher User Input, If-else, Arrays, Loops

Prompt for 10 single-digit int inputs. Then, use a wraparound cipher to "encode" it. This means that every digit is incremented by one, unless that digit is 9, it which case it becomes 0. You will use two loops, one for getting+processing info, and another for printing it out in the end. You only need one integer array.
Sample program output:


% java Cipher
Please type in ONLY single digits!
0: 1
1: 2
2: 3
3: 4
4: 5
5: 3
6: 7
7: 8
8: 0
9: 9
Encoded number:
2345648910

After everyone will have at least attempted to solve the problems, I will post the answers.

Data: User Input & Random

2007-06-27T10:30:00.000-04:00

User Input


import java.util.Scanner;
public class HelloWorld{
   public static void main(String args[]){
      System.out.print("What is your name? ");
      Scanner scan = new Scanner(System.in);
      String name = scan.nextLine();
      System.out.println("Hello, "+name+"!");
   }
}

To get user input, we will be using Scanner, so you absolutely must import it, or the compiler won't recognize it and give lots of errors.
Scanner is a little buggy, though.

The .nextLine() immediately following a .nextInt() will return an empty string. Therefore, after you read in an integer and before you read in a string, just do a .nextLine() without assigning the result to anything.
If .nextInt() (or any other non-string-getter) is called and the user types in a non-integer, you get lots of exceptions. Try-catching them doesn't work. So, if you wanna foolproof your program, use the following method in your program instead of .nextInt():
public static int getInt(){ Scanner scan = new Scanner(System.in); while(true){ // run forever until the user types in a number try{ // try to parse the typed-in strign as an integer: return Integer.parseInt(scan.nextLine()); } catch( Exception e ){ // if fail, aks user again: System.out.println("Please type in a number."); } } }
Don't worry if you don't understand it yet: you will tomorrow. Just, whenever you need to get a number, do not do scan.nextInt(), instead, use getInt().

Random


import java.util.Random; // you need this line for all rpograms involving the Random object!
public class RandomTest{
   public static void main(String args[]){
      Random rand = new Random();
      System.out.println("Random number: "+rand.nextInt());
      System.out.println("Random number from 0 to 9: "+rand.nextInt(10));
      System.out.println("Random double: "+rand.nextDouble());
      System.out.println("Random double from 0 to 1: "+rand.nextDouble(1));
      }
   }

If & Switch

2007-06-27T10:00:00.001-04:00

If-Else

Most problems require handling some sort of conditions and doing different things in different cases. If-statements in Java do this:

if (condition){
   action A
   }
else{
   default action
   }

If there are more than two cases, you can use (as many as you need)

else if(another condition){
   action B
   }

between the original if and the ending else. Here's an example:

if (there is rain){
   use an umbrella
   }
else if (there is a trustworthy account of oncoming rain){
   bring an umbrella just in case
   }
else{
   leave the umbrella alone
   }

The action portion of the if statement can be any <working> piece of code.

The condition is a statement that is a boolean, ie, it is either true or false. If it is true, the action is performed. If not, the next condition is tested, or, if there are no more conditions, the default action is performed. It typically uses the following operators:

== Ex.: A==B "is A equal to B?"
!= Ex.: A!=B "is A NOT equal to B?"
> Ex.: A>B "is A larger than B?"
>= Ex.: A>=B "is A larger than or equal to B?"
< Ex.: A<B "is A smaller than B?"
<= Ex.: A<=B "is A smaller than or equal to B?"

For example, a valid piece of code would be:


//assume var is some random-generated integer between 0 and 9, inclusively
if(var<5){
   System.out.println("too small!");
   }
else{
   System.out.println("too BIG!");
   }

But what if you wanted to put in more constraints? Here's an example:


//assume var1 and var2 are two independent random-generated integers
//   between 0 and 9, inclusively
if(var1<5 && var2<5){
   //if both are less than 5:
   System.out.println("too small!");
   }
else if(var1<5 || var2<5){
   // both can't be less than 5, because if they were, the first if
   // would have been true; the order of the
   // if's really, really matters
   // basically if one is smaller than 5 and the other isn't.
   System.out.println("just right ^.^");
   }
else{
   System.out.println("too BIG!");
   }

the || is part of the operators that you can use to tie several constraints together into a single condition:

|| or (inexclusive - if at least one is true, it returns true)
&& and (returns true if both are ture)

So, you can have condition monsters such as:


((var1var2 && var3>var1) || var3==0))

In case you're wondering what that returns, here's the English version (note: it's just a random collection of conditions. it has no universal meaning. assume, for the purposes of this "demonstration," that var1 var2 and var3 are random integer variables.) This statement is true if:

var1 is smaller than var2 at the same time as var3 is anything other than 7, OR
var3 is equal to 0, OR
var3 is larger than both var1 and var2

Switch

Besides the if statement, you can have a switch. While in an if statement, you set certain bounds. Switches are different because they only analyze a single variable in the whole switch (while the if can set constraints or as many variables as you can type) and they don't set bounds, they set cases, such as:


switch(var1){
   case 1: action A; break;
   case 2: action B;
   case 3: action C; break;
   default: default action; break;
}

First off, the variable it analyzes is noted in the beginning of the switch. This variable can only be either int or char. Note the presence of "break;". This tells the switch to abort as soon as the action is complete. The case for 2, for example, is missing a break. This means that when var1=2, BOTH action B and action C is run because the switch doesn't abort until it sees the break; in case 3. Switches can be very neat in some cases, and just plain unusable in others.

Problem Set 2

2007-06-27T09:30:00.000-04:00

Topics: user input, random, if-else, switch

1: Write a program, using a switch, that takes as input a lowercase letter char and prints out the integer value of that character as it would be on a phone. So, 'a', 'b', and 'c' would yield 2, etc.

2: Write a program, using either if-else or switch, that uses random-generated integers as input. Basically, write this in Java:

you're standing before three roads.
if you go left, you will walk forever in some sort of haunted forest.
if you go straight ahead, you will encounter two more possible roads. of these, if you go left, you will always be thirsty, and, if you go right, you will always be hungry.
if you go right, you will never be able to make a left turn again. ever.
you can choose not to go by wither of the roads and turn back, seeking your fortune elsewhere.

You can use either two random-generated int's, one 0 to 3 and the other 0 to 1, OR one random-generated int that ranges from 0 to 4. Make sure to include (even if not exactly verbatim) every portion of the narration in proper places.

Challenge! Write a program, using if-else construction, that calculates the score in a specific game involving two 6-sided dice. The dice numbers should be randomly generated, then printed out along with the resulting score.

The rules of the game: (1) if the two dice add up to 7, you get 50 points; (2) if the two dice are both he same number, you get 35 points; (3) if one of the dice is exactly 3 bigger than the other (eg, 4 and 1) you get 27 points; (4) if exactly one if the dice is 1, you lose 15 points; (5) you get 5 points for every 5 that appears and 3 points for every 3.

This program is fairly challenging and will require several if-else blocks!
Note: the highest possible score is 50+27+5 and is the result of rolling 2 and 5. The lowest is -15 and is the result of rolling a 1 and anything that isn't 1 or 4. Use this as test input to check your program for errors.
Good luck :)!

Bash Shell

2007-06-26T11:00:00.000-04:00

Intro

You guys have been spoiled with pretty pictures and using a mouse to govern things. Well, for the first few weeks we will be working with the command line(as in we have to type everything). We will be working with the bash shell. A shell is a program that interprets what you type on the screen and tells the OS what you want to do. Different shells have different looks and "feels." The commands may also vary slightly in how you type them in and how they will display things. To return to the bash shell, or if you are unsure of what shell you are in, just type bash then strike the enter/return key.

The Screen

So the first thing we have to go over is what that text on the left hand side means... you should see your guest login and some symbols. Don't worry you haven't broken the computer...yet. All this tells you is that you are in your home directory. Your home directory is where all of your files are stored. This is important because you will probably need to refer to or copy code from previous lessons. This is also where you TYPE your commands.

Doin' Somtin' Useful

Making Directories (Folders)
Now lets start organizing our home folder. we can make a directory to put all of the code for our first program. Lets say first will be the name of the directory. The command for making a directory is mkdir or in more human words make directory. Now, to make our directory we type mkdir first. This can make any number of directories you want with whatever name you want.

Changing Directories (Folders)
So, now that we made the directory, how do we get into it? Well, traveling though directories in command line is nothing like looking at things in windows on your Windows or Mac computer. It is like walking through a garden while looking though a straw. You cannot see the whole thing at once, but instead you have to walk every path and get close to each flower, one at a time, in order to see them.... In command line, you can really only be working in one directory at a time. All the commands you enter are for that directory ONLY. To change to a new directory we use the command cd. So, to get into our new directory we type cd first.

What is in the directory?
To find out what is in the current directory you are in you type the command ls. That is it. It will list all the files and directories in that directory.

Making Files ( with pico )

There are a host of text editors to use in the command line. We will be using pico for the sheer fact that all the commands are listed on the bottom. To make a new file go to the directory you want your file in and then type pico first.java. This will make a file called, first.java in the directory. DON'T FORGET THE .java !!! Now, jump to Katie's post about your first program. Go to Compiling Java to learn how to make it do something.

Compiling Java

2007-06-26T10:30:00.000-04:00

Intro
Java is an interpreted language, which means that is does not directly execute on your computer's processor or use system specific methods. Though, you still have to compile the source code into java byte code.

Making Stuff Work( hopefully )

Compiling
Now, to compile your program we will use the javac command, short for java compiler. So to complile your first program you would type javac first.java. If all goes well, there should be no hoopla on your screen. If there is a problem, the compiler will tell you the line number and maybe what it is. Take all errors with a grain of salt, however, the compiler does not always get the right error. Occasionally, your error will be several lines above the error is lists. The only way you can lear to recognize this is by writing lots of programs...

Runing the Program
Now, that we have the program compiled, we have to invoke the java interpreter to read the .class file that the compiler made. To do this, we simply type java first. DO NOT ADD .class to the end of the class that is to be run. Again, the java interpreter will tell you if anything goes wrong during runtime.

Hello, World! Variables & Methods

2007-06-26T10:00:00.000-04:00

Welcome to the steaming-hot goodness of Java!!!

Sample Program


public class First{
   public static void main ( String args[] ) {
      System.out.println("Hello, world!");
      //some variables....
      int x = 42;
      double y = 3.14;
      char c = 'q';
      String str = "Hello, world!";
      //...that you can print out
      System.out.println( str+":"+c+" ~ "+smapleMethod(x,y) );
   }
   public static int sampleMethod( int a, int b) {
      //a method contains a collection of
      //procedures that constitute a single task.
      //for example, this method adds together two integers, a and b
      return a+b;
   }
}

Java Conventions

Every variable and method name starts with a lowercase letter. If it consists of more than one word, each word after the first is capitalised: variableOne, varOneOfMany, justVariable, etc
Every constant is written in ALL CAPS.
Class names follow the same rules and variable and method names, but start with a capital letter: ClassOne, MyFirstProgram, etc
Make sure to indent your code! See how neat the Sample program looks? Indenting makes code readable.
As you code, you should comment on what your code is and why it's that way. Otherwise, hours later, you'll have no idea why you did something and then spend the next n hours trying to figure it out. It's just not worth it to not comment. Use either // or /* stuff! */ to comment. // comments the line out, and /* */ comments out a block of text regardless of line breaks.

Problem Set 1 is now over here!

Problem Set 1

2007-06-26T09:30:00.001-04:00

Topics: the basics

Declare three doubles, x1, x2, and y2.
The doubles represent triangle T1 which has vertices at (0,0), (x1,0), and (x2,y2).
1: Calculate and print out the perimeter of T1.

Using the set up from the previous problem, try this one:
Declare an integer, n.
Now, suppose triangle T2 is formed by connecting the midpoints of the sides of triangle T1, and in general, triangle Tk+1 is formed by connecting the midpoints of the sides of triangle Tk.
2: Calculate and print out the perimeter of triangle Tn.