LMICSE: Lego Mindstorms in Computer Science Education

Prerequisite Knowledge

Knowledge of controlling the Turtle and using data structures in java.

Materials

Basic Turtle without sensors

Gridded area for testing. See printable example.

Comparable interface (not included in Lejos as of this printing) which can be found here.

Polymorphism

Polymorphism is a powerful tool to utilize in java. It allows for reference variables that can refer to different types of objects depending on the time it finds itself in the program. The way we will be utilizing polymorphism is via interfaces, specifically we will be using a comparable interface to redefine our storage array to allow it to be compared in our sorting algorithms. We will also need to create a compareTo() method in our object class.

Task One

In task one, we're going to modify our code from Lab 10 Task 3. Rather than store the list of locations in a two dimensional array of ints, you're going to create a new class called MyPoint which stores information about the locations the turtle is to visit. Your MyPoint class should implement the comparable interface meaning it should have a compareTo() method, along with a constructor, and accessor methods to look at the x and y values of each point. Now, back in your main method, you should modify your code so that you create an array of MyPoints. Your turtle should still visit each MyPoint in the array.

Task Two

Task two requires you to sort your MyPoints according to their x value. Assuming that you've properly implemented the comparable interface and your accessor methods work correctly, you should only need to make a few changes to the selection sort code given below.

public static void selectionSort(Comparable[] list){
	int min;
	Comparable temp;
	for (int index = 0; some comparison; index++){
		min = index;
		for(int scan = index + 1; 
some comparison
; scan++)
			if(item.compareTo(other item) ‹ 0)
				min = scan;
			
			//swap values
		
		}
	}

Task Three

Now you will implement your new sort method again, but this time you will redesign the goTo method to equate in for angles. To do this you will need a little math background.

Now that we've figured out which angle we need to turn to, all we have to do is figure out how far to turn from our current position. An extremely simple way to do this, is to just start turning 1° at a time, in one direction, and after each short turn, check to see if our current orientation is equal to our desired orientation, however this is not the most clean or accurate way to turn.

You will also need to check and see that once our orientation reaches 360°, it is reset to 0°.

Task Four

Now to add another sort method to our program. This time we will implement the insertion sorting algorithm. The algorithm is as follows with some little filling out:

public static void insertionSort (Comparable[] list){
	for(int index = 1; 
some comparison
; index++){
		Comparable key = list[index];
		int position = index;
		
		//Shift larger values to the right
		while(position › 0 && item.compareTo(other item) ‹ 0 ){
			list[position] = list[list[position-1];
			position--;
 		}
		
		list[position] = key;
 	}
  }
}

Redesign you code now to use the insertion sort instead of the selection sort and run the new program in your turtle.

Additional Problems

Redesign your compareTo methods now to do the following orders:

• right to left
• top to bottom
• bottom to top
• bottom-left to top-right
• top-right to bottom-left

Conclusion

In this lab, you learned the following:

• How to use the comparable interface
• How to use selection and insertion sorts