Implementing the Josephus Problem in Java

Problem:

This problem is based upon a report by the historian Joseph ben Matthias (Josephus) on the
outcome of a suicide pact that he had made between himself and 40 soldiers as they were
besieged by superior Roman forces in 67 A.D. Josephus proposed that each man slay his neighbor.
This scheme necessarily leaves one to kill himself. Josephus cleverly contrived to be that
one, thus surviving to tell the tale.

Output:

[A, B, C, D, E, F, G, H, I, J, K]
A killed B
C killed D
E killed F
G killed H
I killed J
K killed A
C killed E
G killed I
K killed C
G killed K
The lone survivor is G

Solution:

public class Josephus {
public static final int SOLDIERS = 8;
public static final String ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static void main(String[] args) {
Ring<String> ring = new Ring<String>();
for (int i=0; i<SOLDIERS; i++) {
ring.add(ALPHA.substring(i, i+1));
}
System.out.println(ring);
Iterator<String> it = ring.iterator();
String killer = it.next();
while (ring.size() > 1) {
String victim = it.next();
System.out.println(killer + " killed " + victim);
it.remove();
killer = it.next();
}
System.out.println("The lone survivor is " + it.next());
}
}

Read More

Implementing an ordered list using LinkedList and ListIterator in Java

Problem:

Implement an ordered list using LinkedList and ListIterator (the one in the book). You need to provide the following methods: AddSorted, Retrieve, Delete and Search.

Output:

Not available.

Solution:

/**------------------MyComparable.java---------------------*/
public interface MyComparable 
{
 public int MyCompareTo(Object O);
}

/**------------------OrderedList.java---------------------*/
import java.util.*;
public class OrderedList<E extends MyComparable>
{
 private LinkedList<E> linkedList = new LinkedList<E>();
 private ListIterator<E> listIterator;

 public void AddSorted(E entry)
 {
  listIterator = linkedList.listIterator();
  
  while(listIterator.hasNext())
  {
   if(entry.MyCompareTo(listIterator.next())>0)
   {
    listIterator.previous();
    listIterator.add(entry);
    return;
   }
  }
  
  listIterator.add(entry);
 }
 
 public void Delete(E entry)
 {
  listIterator=linkedList.listIterator();
  
  while(listIterator.hasNext())
  {
   if(entry.MyCompareTo(listIterator.next())==0)
   {
    listIterator.remove();
    
    System.out.println("Deleted");
    
    return;
   }    
  }
 }
 
 public E Retrieve(E entry)
 {
  listIterator = linkedList.listIterator();
  
  while(listIterator.hasNext())
  {
   if( entry.MyCompareTo(listIterator.next()) == 0)
   {
    return listIterator.previous();
   }    
  }
  
  throw new NoSuchElementException();
 }
 
 public void Search(E entry)
 {
  listIterator = linkedList.listIterator();
  
  while(listIterator.hasNext())
  {
   if(entry.MyCompareTo(listIterator.next())==0)
   {
    System.out.println("Found");
    return;
   }    
  }
  System.out.println("Not Found");
 }
 
}
/**----------------------Students.java-------------------------*/
public class Student implements MyComparable
{
 private String name;
 private int id;
 
 
 public Student(String name, int id) {
  this.name = name;
  this.id = id;
 }
 
 public String getName() {
  return name;
 }


 public void setName(String name) {
  this.name = name;
 }


 public int getId() {
  return id;
 }


 public void setId(int id) {
  this.id = id;
 }
 
 public int MyCompareTo(Object o)
    {
        Student student =(Student) o;
        
        if(id < student.getId())
            return -1;
        
        else if(id > student.getId())
            return 1;
        
        else
            return 0;
    }
 
 public String toString() {
  return "Student, " + name + "\n" + "Id, " + id;
 }
}
/**-------------------------Tester.java------------------------------*/
public class Tester
{
 public static void main(String[] args)
 {
  OrderedList<Student> student = new OrderedList<Student>();
  
   student.AddSorted(new Student("name1",1));
   student.AddSorted(new Student("name2",2));
   student.AddSorted(new Student("name3",3));
   student.AddSorted(new Student("name4",4));
   student.AddSorted(new Student("name5",5));

   System.out.println("Searching for \"name1\": ");
   //Searching based on id number not name
   student.Search(new Student("name1",1)); 
   System.out.println();
  
   System.out.println("Retrieving \"name1\": ");
   System.out.println(student.Retrieve(new Student("name1",1)));
   System.out.println();
  
   System.out.println("Deleting \"name1\": ");
   student.Delete(new Student("name1",1));
   System.out.println();
   
   System.out.println("Re-searching for  \"name1\": ");
   student.Search(new Student("name1",1));
   System.out.println();
  
 }
}

Read More

Creating a ListIterator Application in Java

Problem:

Game

-          title : String -          type : String -          released : Boolean -          price : int -         copiesSold : int

// Constructor(s)       // setters getters     + toString() : String

GameViewer

- games : LinkedList<game>

+ GameViewer() + addGame(game : Game) : void + deleteGanne(title : String) : void + getReleasedGames() : LinkedList<Game> + getMostSellingGame() : Game + getLeastSellingGame() : Game + getHighestPriceGame() : Game + getLowestPriceGame() : Game + getAllGames() : LinkedList<Game> + printGames() : void

You have to implement the previous two classes. The class Game has four private variables, a constructor, setters and getters, and a toString method. The class GameViewer has a LinkedList of games and a couple of methods that apply operations on the LinkedList.

- addGame(game : game): takes a game as parameter and adds it to games

- deleteGame(title : String): deletes a game from games with the specified title
- getReleasedGames(): returns a LinkedList<Game> that contains all the games that have been released (released = true)

- getMostSellingGame (): returns the game with the most copies sold

- getleastSellingGame(): returns the game with the least copies sold

- getHighestPriceGanne(): returns the game with the highest price

- getLowestPriceGame(): returns the game with the lowest price

- getAllGames(): returns the games linked list

- printGames(): prints the games linked list

In the tester class, you are required to create an object of type GameViewer and add to its list a number of games.

You should test all of the class' methods and print the output of each in a well formed manner.

You should only use ListIterator to loop over the linked list. Any other way is not acceptable.

Solution:

/**-----------------------Game.java----------------------*/
public class Game {

 private String title;
 private String type;
 private boolean released;
 private int price;
 private int copiesSold;
 
 public Game(String title, String type, boolean released,
                                       int price, int copiesSold) {
  this.title = title;
  this.type = type;
  this.released = released;
  this.price = price;
  this.copiesSold = copiesSold;
 }

 public String getTitle() {
  return title;
 }

 public void setTitle(String title) {
  this.title = title;
 }

 public String getType() {
  return type;
 }

 public void setType(String type) {
  this.type = type;
 }

 public boolean isReleased() {
  return released;
 }

 public void setReleased(boolean released) {
  this.released = released;
 }

 public int getPrice() {
  return price;
 }

 public void setPrice(int price) {
  this.price = price;
 }

 public int getCopiesSold() {
  return copiesSold;
 }

 public void setCopiesSold(int copiesSold) {
  this.copiesSold = copiesSold;
 }

 @Override
 public String toString() {
   return "[title=" + title + ", type=" + type + ", released=" 
               + released + ", price=" + price + 
               ", copiesSold=" + copiesSold + "]";
 }
}
/**-----------------------GameViewer.java----------------------*/
import java.util.LinkedList;
import java.util.ListIterator;

public class GameViewer {

 private LinkedList<Game> games;
 
 public GameViewer() {
  games = new LinkedList<Game>();
 }
 
 public void addGame(Game game) {
  games.add(game);
 }
 
 public void deleteGame(String title) {
  ListIterator<Game> itr = games.listIterator(0);
  
  while (itr.hasNext()) {
   Game game = itr.next();
   if (game.getTitle().equalsIgnoreCase(title)) {
    itr.remove();
    return;
   }
  }
 }
 
 public LinkedList<Game> getReleasedGames() {
  ListIterator<Game> itr = games.listIterator(0);
  LinkedList<Game> released = new LinkedList<Game>();
  
  while (itr.hasNext()) {
   Game game = itr.next();
   if (game.isReleased())
    released.add(game);
  }
  
  return released;
 }
 
 public Game getMostSellingGame() {
  ListIterator<Game> itr = games.listIterator(0);
  Game mostSelling = games.getFirst();
  
  while (itr.hasNext()) {
   Game game = itr.next();
   if (game.getCopiesSold() > mostSelling.getCopiesSold())
    mostSelling = game;
  }
  
  return mostSelling;
 }
 
 public Game getLeastSellingGame() {
  ListIterator<Game> itr = games.listIterator(0);
  Game leastSelling = games.getFirst();
  
  while (itr.hasNext()) {
   Game game = itr.next();
   if (game.getCopiesSold() < leastSelling.getCopiesSold())
    leastSelling = game;
  }
  
  return leastSelling;
 }
 
 public Game getHighestPriceGame() {
  ListIterator<Game> itr = games.listIterator(0);
  Game highestPrice = games.getFirst();
  
  while (itr.hasNext()) {
   Game game = itr.next();
   if (game.getPrice() > highestPrice.getPrice())
    highestPrice = game;
  }
  
  return highestPrice;
 }
 
 public Game getLowestPriceGame() {
  ListIterator<Game> itr = games.listIterator(0);
  Game lowestPrice = games.getFirst();
  
  while (itr.hasNext()) {
   Game game = itr.next();
   if (game.getPrice() < lowestPrice.getPrice())
    lowestPrice = game;
  }
  
  return lowestPrice;
 }
 
 public LinkedList<Game> getAllGames() {
  return games;
 }
 
 public void printGames() {
  System.out.println(games);
 }
}

Read More