Category Archives: Homework

Arrays 2D: Minesweeper

Write a program Minesweeper_YI.java that takes 3 input arguments m, n, and p and produces an m-by-n boolean array where each entry is occupied with probability p. In the minesweeper game, occupied cells represent bombs and empty cells represent safe cells. Print the array using an asterisk for bombs and a period for safe cells. Then, replace each safe square with the number of neighboring bombs (above, below, left, right, or diagonal) and print the solution.

HS-TEACHER-17464:Array2D gracielaelia$ java Minesweeper 3 3 0.2
. . . 
. . . 
* . . 

0 0 0 
1 1 0 
* 1 0

Try to write your code so that you have as few special cases as possible to deal with, by using an (m+2)-by-(n+2) boolean array.

HS-TEACHER-17464:Array2D gracielaelia$ java Minesweeper 3 3 0.3
. . * 
. . * 
. . * 

0 2 * 
0 3 * 
0 2 * 
HS-TEACHER-17464:Array2D gracielaelia$ java Minesweeper 3 3 0.4
. . . 
* . . 
. . . 

1 1 0 
* 1 0 
1 1 0 
HS-TEACHER-17464:Array2D gracielaelia$ java Minesweeper 3 3 0.5
* * * 
. * * 
* . * 

* * * 
4 * * 
* 4 * 
HS-TEACHER-17464:Array2D gracielaelia$ java Minesweeper 3 3 0.6
* * * 
. . * 
* * * 

* * * 
4 7 * 
* * * 
HS-TEACHER-17464:Array2D gracielaelia$ java Minesweeper 3 3 0.7
. * * 
* * * 
* . * 

3 * * 
* * * 
* 5 * 
HS-TEACHER-17464:Array2D gracielaelia$ java Minesweeper 3 3 0.8
* . * 
* * . 
* * * 

* 4 * 
* * 4 
* * * 
HS-TEACHER-17464:Array2D gracielaelia$ java Minesweeper 3 3 0.9
* * * 
* * . 
* * * 

* * * 
* * 5 
* * *

Required Submission:

Copy and paste the program (with the output as a paragraph comment at the end of your program) to the Text entry tab.
Submit the file with the ‘”java” extension.

3. Make sure you document code snippets that have a particular purpose!

4. Testing: Have multiple boards with different board sizes and different probabilities. The minimum should be 3 boards.

Arrays: Game of Life

Game Of Life:

If you have successfully completed the random block program and written the draft for the algorithm in pseudocode, you should be able to get started with the game of life assignment.

Start small. Hardcode the seed for the glider:

Requirements:
1. Take as input the size of the grid.
2. Show the live cells in color other than black.

Challenges:
1. Take as input the coordinates for the seed. You must include in your documentation the coordinates for the glider seed.
2. Change the color of the dead cells to a faded color for at least one generation after dying.
3. Take as input the option to speed or slow down the simulation.

Arrays – Connect Four

Classwork/Homework:
(Game: connect four) Connect four is a two-player board game in which the players alternately drop colored disks into a seven-column, six-row vertically suspended grid, as shown below.

connectfour

The objective of the game is to connect four same-colored disks in a row, a column, or a diagonal before your opponent can do likewise. The program prompts two players to drop a red or yellow disk alternately. In the preceding figure, the red disk is shown in a dark color and the yellow in a light color. Whenever a disk is dropped, the program redisplays the board on the console and determines the status of the game (win, draw, or continue). Here is a sample run:

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
———————————————

Drop a red disk at column (0–6): 0
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
|R| | | | | | |
———————————————

Drop a yellow disk at column (0–6): 4

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
|R| | | |Y| | |
.
.
.
.

Drop a yellow disk at column (0–6): 6 

| | | | | | | |
| | | | | | | |
| | | | |Y| | |
| | | |Y|Y|Y|R|
| | |Y|R|R|Y|Y|
|R|Y|R|Y|R|R|R|
———————————————
The yellow player won
Do you want to play again?

Write the two-player program, YI_Connect4.java. Display at a every move the board as shown in the example above. Include a prompt to continue playing.

Your program should include:
1. Good documentation
2. An introduction message
3. Functions (Optional)
4. An end of game message
5. Input/output

What is good documentation?
Answer:

Header with author’s name, assignment description, date and python version.
Comments in each function. A short sentence will be sufficient.
Comments for code snippets written for specific handling. An example might be checking if there are 3 in a row, or 4 in a row.
Comments to indicate unusual or rare situations that don’t follow a pattern or repetition.

Arrays: Preparing for assessments

Preparing for assessments

Your notes should include:

All loops syntax: while, do while, and for.
The Scanner class: how to create an object of it and use it’s methods.
The Math.random() function.
Typical array-processing code highlights:
- 1D and 2D arrays: how to declare and initialize them.
- Code snippets to print all the elements, to add columns, rows.
- Programs designed to create frequency arrays.
- The code needed to swap elements of an array, to find the max and the min.
- A short program to simulate rolling dice.
StdIn, StdOut and StdDraw short API’s with few examples.
The rules to print formatted output, printf.
Simple drawings programs.

Arrays: Test Review Arrays

Arrays Test Review

One Dimensional arrays:
1. Create arrays and initialize them with a loop.
2. Initialize an array when created.
3. Find the number of elements in an array.
4. Check an array’s bounds.
5. Swapping elements of an array – permutations (sampling without replacement)
6. Given an array of N elements, write the code to shuffle them using the random feature.
7. Find the max – min of the elements.
8. Reverse the elements.
9. Find the average of the elements.
10. Print each element.
11. Sieve of Erasthostenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
12. Arrays as frequency or counters.
13. What types must be used as indices for arrays?

Midterm Review Part 1

Content for some questions:

Overflow

From

The int data type is a 32-bit signed two’s complement integer. It has a minimum value of -2,147,483,648 (0x80000000) and a maximum value of 2,147,483,647 (0x7FFFFFFF) (inclusive)

So when you add one to an integer’s max value:

0x7FFFFFFF + 0x00000001 = 0x80000000 (-2,147,483,648)

Arrays: Intro

Typical array-processing code.
Programming with arrays.
- Zero-based indexing
- Array length
- Memory representation
- Bounds checking
- Setting array values at compile time
- Setting array values at run time
Shuffling and sampling
- Exchange
- Shuffling
- Hardwired constants
- Sampling without replacement

classwork:
Write a program, ArrayBasics_YI.java to do the following:

Create an array a[] size 10. Assign a random number between 1 and 30 to each element.
a. Display the first element of the array.
b. Display the last element of the array assuming you do not know the size of the array.
c. Display the messages given when you try to access an element with a negative index and with an index beyond the size of the array.
Create two arrays, suit[] and face_value[].
a. The suit[] array contains the 4 different suits as elements.
b. The face_value array contains “2”, “3”,…,”Jack”,…,”Ace” elements.
c. Use the random function to select five cards and display them.
Create two arrays x[] and y[] with N number of elements both. Prompt the user for N. Assign random integers to each element. Then have another loop to find the product of each element wit the same index and add them all together. This operation is called the “dot product”.

Assignments:
ClosestPair_YI.java
Write a program to create an array of 100 random integers between the values of 1 and 1000 and find the two consecutive integers with the smallest difference between the two of them.

MaxInArray_YI.java
Write a program to create an array of 100 random integers between the values of 1 and 1000 and find the largest value.

AverageArray_YI.java
Write a program to create an array of 100 random integers between the values of 1 and 1000 and find the average of all the elements of the array.

PrintArray_YI.java
Write a program to create an array of 100 random integers between the values of 1 and 1000 and print them separated by 3 spaces. Note: Use printf to keep all your numbers tab properly.
A printf format reference page (cheat sheet)

Pop Quiz Array 1
Pop Quiz 1: Fix the problem

Arrays: Duplicate

Classwork/Homework:
Write a program, Duplicate_YI.java to find a duplicate. Given an array of N elements with each element between 1 and N, write an algorithm to determine whether there are any duplicates. You do not need to preserve the contents of the given array, but do not use an extra array.

Create an array with 50 random integer numbers between 1 and 50 inclusive.
Print the array in 10 rows by 5 columns. Use “printf” to keep the columns aligned.
Print all the duplicate values and their index. Format: value, index 1, index 2 … per line.
Print the total number of duplicates as the last message in your output.

Arrays: At Least One of Each

Classwork/Homework:
Suppose that you have a shuffled deck of cards and you turn them face up, one by one. How many cards do you need to turn up before you have seen one of each suit?
OneOfEach1_YI.java: this program will allow the user to pick as many cards as needed until all the different values in any deck of cards come up. Your program should generate the number of cards needed to find all the suits. The input should be M, the number of suits.

In general, suppose that a trading card company issues trading cards with M different possible cards: how many do you have to collect before you have all M possibilities, assuming that each possibility is equally likely for each card that you collect and that there is an infinite number of cards?

A good example would be “Collect all ranks in a random sequence of cards (M = 13).” Look at page 23 on the pdf above.

Card collector simulation
• Generate random int values between 0 and M-1

• Count number used to generate each value at least once.

Key to the implementation
• Create a boolean array of length M (Initially all false by default.)
• When r generated, check the rth value in the array.
• If true, ignore it (not new).
• If false, count it as new (and set rth entry to true)

How many cards do you need to turn up before you have seen one of each suit? Sample test runs:

How many different cards in your deck? 13
After randomly drawing 46 cards, the full collection was acquired.

How many different cards in your deck? 13
After randomly drawing 22 cards, the full collection was acquired.

How many different cards in your deck? 13
After randomly drawing 49 cards, the full collection was acquired.

How many different cards in your deck? 13
After randomly drawing 30 cards, the full collection was acquired.

OneOfEach2_YI.java: implement this program to allow the user an additional input, the specific number of trials. Each trial will calculate how many cards (no_of_cards) were drawn until all different (face) value cards were drawn. End the program by displaying the average number of cards needed for all the M cards to come up. Again, assuming there is an infinite number of cards.

A large number of trials will give you a better approximation to the solution to the problem. The idea is to keep track of how many cards were drawn to get all the (face) values at each trial and find the average. The more trials, the closer you get to the actual number. You will also see that as the number of trials keeps on growing the average does not change much. To help you find a pattern, then you increase the number of suits, and repeatedly increase the number of trials.

Show these predicted values by running the program with a high number of trials, from 1000 to 1000000.

Sample runs:

% java OneOfEach2_YI 4 1000000
8
% java OneOfEach2_YI 13 1000000
41
% java OneOfEach2_YI 52 100000
236
% java OneOfEach2_YI 1200 10000
9176
% java OneOfEach2_YI 12534 1000
125920

In theory:
Given n different suits, how many cards do you expect you need to draw with replacement (or in this case, an infinite number of cards of all different suits) before having drawn each suit at least once? The mathematical analysis of the problem reveals that the expected number of trials needed approximates n(log(n)).
For example, when n = 50 it takes about 225 trials to collect all 50 suits.

Screen Shot 2015-12-13 at 8.01.43 AM

From Lawerence Chen
Screen Shot 2015-12-13 at 7.56.00 AM

Input/Output: Graphics: Simple Bar Graph

Looking at the printf method
A printf format reference page (cheat sheet)

// This class shows how to initialize an array 
// How to use the printf output formatting method
public class InitPrintfArray 
{
   public static void main( String[] args )
   {
      // initializing the array when it is created
      int[] arrayA = { 87,56,78,99,102 };

      System.out.printf( "%s%7s\n", "Index", "Value" ); // column headings
   
      // output each array element's value 
      for ( int i = 0; i < arrayA.length; i++ )
         System.out.printf( "%5d%5d\n", i, arrayA[ i ] );
   } // end main
} // end class InitPrintfArray

A "simplified" version of a bar chart by using the elements of an array as counters

// Bar graph printing program.

public class BarGraph 
{
   public static void main( String[] args )
   {
      int[] arrayA = { 0, 0, 0, 0, 0, 0, 1, 2, 4, 2, 1 };

      System.out.println( "Grade distribution:" ); 

      // for each array element, output a bar of the chart
      for ( int i = 0; i < arrayA.length; i++ ) 
      {
         // output bar label ( "00-09: ", ..., "90-99: ", "100: " )
         if ( i == 10 )
            System.out.printf( "%5d: ", 100 ); 
         else
            System.out.printf( "%02d-%02d: ", 
               i * 10, i * 10 + 9  ); 
 
         // print bar of asterisks
         for ( int stars = 0; stars < arrayA[ i ]; stars++ )
            System.out.print( "*" );

         System.out.println(); // start a new line of output
      } // end outer for
   } // end main
} // end class BarGraph

Grade distribution:
00-09:
10-19:
20-29:
30-39:
40-49:
50-59:
60-69: *
70-79: **
80-89: ****
90-99: **
100: *
Claswork/Homework:
Tracing 101: Trace the i, arrayA[i], and the output as the inner and outer loops traverse arrayA.

Mrs. Elias's Intro to Computers (Acc)

Class Website at PHS