teaching machines

CS 245 Lecture 18 – Snake

April 1, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• a snake game
• hashset and iterator
• different kinds of lists

TODO

• Homework 3 is posted. Due before April 16.
• Read sections 2.5-2.7 in Data Structures. 1/4 sheet.

Tasks for Snake?

• How do we manage eggs?
• Generate and draw eggs.
• Handle cursor events.
• How do we manage snake?
• Draw snake.
• How do we handle snake moving to a spot with an egg?
• How do we handle snake moving to a spot without an egg?
• How do we handle self-collision?
• How do we handle wall collision?

Think About This

1. Split into groups of three. Grand a handful of 10+ paperclips.
2. Make a chain of  your paperclips.
3. Join your chain up with another group’s into a 20+ sequence. Then form an 40+ sequence. Then 80+…
4. Add a new paperclip onto the end. How many operations did that take?
5. Remove the first paperclip. How many operations did that take?
6. Find the 37th paperclip. How many operations did that take?
7. Add a new paperclip after the 37th. How many operations did that take?
8. How many paperclips are in the chain? How many operations does that take?

Code

HashSet.java

package lecture18;

import java.util.ArrayList;

public class HashSet<T> {
  private ArrayList<T>[] items;
  
  public HashSet() {
    items = new ArrayList[5];
  }
  
  public void add(T item) {
    int i = Math.abs(item.hashCode()) % items.length;
    if (items[i] == null) {
      items[i] = new ArrayList<T>();
    }
    if (!items[i].contains(item)) {
      items[i].add(item);
    }
  }
  
  public void remove(T item) {
    int i = Math.abs(item.hashCode()) % items.length;
    if (items[i] != null) {
      items[i].remove(item);
    }
  }
  
  public boolean contains(T item) {
    int i = Math.abs(item.hashCode()) % items.length;
    return items[i] != null && items[i].contains(item);
  }
  
  public Iterator getIterator() {
    return new Iterator();
  }
  
  public class Iterator {
    private int hashIndexOfItemToRetrieve;
    private int listIndexOfItemToRetrieve;
    
    public Iterator() {
      hashIndexOfItemToRetrieve = 0;
      listIndexOfItemToRetrieve = -1;
      advanceToNextItemToRetrieve();
    }
    
    public boolean hasNext() {
      return hashIndexOfItemToRetrieve < items.length;
    }
    
    public T next() {
      T item = items[hashIndexOfItemToRetrieve].get(listIndexOfItemToRetrieve);
      advanceToNextItemToRetrieve();
      return item;
    }
    
    private void advanceToNextItemToRetrieve() {
      ++listIndexOfItemToRetrieve;
      
      while (hashIndexOfItemToRetrieve < items.length &&
             (items[hashIndexOfItemToRetrieve] == null ||
              listIndexOfItemToRetrieve >= items[hashIndexOfItemToRetrieve].size())) {
        listIndexOfItemToRetrieve = 0;
        ++hashIndexOfItemToRetrieve;
      }
    }
  }
  
  public static void main(String[] args) {
    HashSet<String> set = new HashSet<String>();
    set.add("a");
    System.out.println(set.contains("a"));
    set.remove("a");
    System.out.println(set.contains("a"));
    
    set.add("a");
    set.add("b");
    set.add("c");
    set.add("d");
    set.add("e");
    set.add("f");
    set.add("g");
    set.add("z");
    set.add("z");
    set.add("ifrim");
    set.add("racecar");
    
    System.out.println(set.contains("racecar"));
    System.out.println(set.contains("tacocat"));
    
    HashSet<String>.Iterator i = set.getIterator();
    while (i.hasNext()) {
      System.out.println(i.next());
    }
  }
}

Haiku