Background
1. Goals of this assignment
Question 1: PositiveInteger.java
Question 2: Buffon Needle Experiment
Question 3: Simulation of Derangements Experiment
Submission

Background

Now that you have learned how to repeatedly perform the same actions over and over again via loops, you are in a position to use your computer to do something that computers have been used for since the very early days: simulations. In this assignment, you will warm up your new loop skills by programming three number theory concepts. Then, you’ll perform a Monte Carlo simulation and then simulate the Buffon Needle problem.

This is a long assignment, so you’ll have two weeks to complete it. Take it step by step!

Goals of this assignment

Use iteration to check complex properties of data
Generate large numbers of random data points for analysis
Compute probabilities based on results from repeated experiments

Question 1: PositiveInteger.java

In this part of the assignment, you will write 3 methods to study some simple number theory concepts. To get started, create a file PositiveInteger.java that houses the class PositiveInteger. This class has one single instance variable of type int called num. We have provided you with the skeleton here, including a constructor as well as stubs for the methods you’ll need to fill out. Just type it out in your code. DO NOT change the method signatures in this class!

public class PositiveInteger {

    private int num;

    public PositiveInteger(int number){
        num = number;
    }

    public boolean isPerfect() {
        return false;
    }

    public boolean isAbundant() {
        return false;
    }

    public boolean isNarcissistic() {
        return false;
    }

}

Study the constructor, and note how it creates a new PositiveInteger by storing its single int input in the field num. This means that the methods that check the properties of this number don’t take any inputs, and that you perform these checks on the field num.

isPerfect() Autograded

A positive integer is said to be perfect if it is equal to the sum of all its unique factors, excluding from the list of factors the number itself. For example:

6 is a perfect number because its factors 1, 2, 3 all sum together to 6.
28 is a perfect number: its factors are 1, 2, 4, 7, 14, which sum to 28.
10 is not a perfect number. Its factors are 1, 2, 5, which sum together to 8.
1 is not a perfect number since it has no factors other than itself.

isAbundant() Autograded

A positive integer is said to be abundant if the sum of its unique factors (aside from the number itself) is greater than the number itself. For example:

12 is abundant since 1+2+3+4+6 = 16 > 12.
15 is not abundant since 1+3+5 = 9 < 15.
1 is not abundant since it has no factors other than itself.

isNarcissistic() Autograded

A positive integer is said to be narcissistic if it is equal to the sum of its own digits each raised to the power of n, where n is the total number of digits. For example:

153 is narcissistic because 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153.
by definition, all single digit numbers are narcissistic (1^1 = 1, 2^1 = 2 etc).
14 is not narcissistic because 1^2 + 4^2 = 1 + 16 = 17 != 14.

What to Submit for Question 1

PositiveNumber.java, with the three specified methods completed. isPerfect(), isAbundant(), and isNarcissistic() will all be graded.

General Notes for Question 1

You can write a helper method if you like in order to simplify your code.
Make sure to come up with some test cases for your code! We’ll test all sorts of different inputs for these methods. This would be a good opportunity to collaborate with your classmates.
You can write a main method in this class if you’d like to use it to test your own code, but we’ll ignore it when grading. Nothing important should go here.
All three of these methods will be graded automatically. Therefore, you must not change the names, parameter lists, or return types of any of these provided methods.

Question 2: Buffon Needle Experiment

This assignment idea is borrowed heavily from Big Java by Cay S. Horstmann. This question will have you implement a simulation as an exercise. Our goal is to estimate the value of pi by modeling the process of randomly dropping needles on a lined piece of paper.

Background on the Experiment

This experiment was devised by Comte Georges Louis Leclerc de Buffon (1707–1788), a French naturalist.

A needle of length 1 inch is dropped onto paper that is ruled with lines 2 inches apart many, many times. When the needle drops onto a line, we count it as a hit; otherwise, it’s a miss.

By counting the number of times the dropped needle crosses a line (i.e. the number of hits), as well as the total number of times the needle is dropped, we can calculate the quotient totalDrops / hits. Surprisingly, the result actually approximates pi given enough experiment trials. You can watch a video on this experiment here and read more about it here.

Conducting the Experiment

Here’s how you can simulate a random individual needle drop. Since the needle has a fixed length of one inch, its position can be defined by two numbers: the y-coordinate of the low end of the needle, as well as the angle between the needle and the x-axis. We’ll call the low y-coordinate y_low and the angle alpha.

needle diagram

For each drop, you’ll need to generate a random value for y_low between 0 and 2 inches. You’ll also need to generate a random value for alpha between 0 and 180 degrees. Based on y_low and alpha, you will calculate y_high as follows:

y_high = y_low + sin(alpha)

We say that the needle crosses the line (i.e. we have a hit) when y_high is at least 2.

runExperiment() Autograded Manually Checked

To estimate pi, we’ll need to keep track of the number of hits as well as the number of times we drop the needle (totalDrops).

To help you write this experiment, we provide here a class called Needle. Needle has exactly one method (aside from the constructor) called runExperiment(int totalDrops). In this method, we simulate dropping the needle totalDrops times and return the resulting quotient of totalDrops/hits. The skeleton for this class also has a Random instance variable you should utilize. Refresh your memory on the Random documentation here.. No additional instance variables and methods are needed. Do not change the signature of runExperiment().

import java.util.*;

public class Needle {
	
	private Random generator;
	public Needle() {
		generator = new Random();
	}
	
	public double runExperiment(int totalDrops) {
		// implement 
	}
}

What to Submit for Question 2

Needle.java, with the specified method runExperiment() completed. Your solution for runExperiment() will be automatically graded, although we will verify that you are actually running the experiment and that you aren’t just explicitly returning the literal 3.14159....

General Notes for Question 2

You can write a helper method if you like in order to simplify your code.
You can use Math.sin() to compute the sin of an angle. Note that Math.sin() expects an input in radians, not degrees! Make sure to convert if needed.
Test runExperiment with many different inputs values. Which inputs make the result come closer to 3.14159...?
You can write a main method in this class if you’d like to use it to test your own code, but we’ll ignore it when grading. Nothing important should go here.

Question 3: Simulation of Derangements Experiment

Now you will simulate a famous derangements problem, which can be phrased as follows:

There are n people. Each of these people has a coat. They go to a bar to party. The bar asks them to leave their coats in a checking room. They go and get drunk and when they come back to pick up their coats it is hard for them to recognize theirs, so they just pick up a random coat.

There are two interesting probability questions we can ask about this situation.

What is the probability of 0 people getting their coats?
What is the average number (expected value) of people who get their coats back?

We won’t use combinatorial reasoning to solve this problem–that kind of thing is for boring courses like CIT 592. I’m kidding! Mostly. Instead, we’ll follow our strategy from the needle problem and run many virtual experiments to gather data.

What Does a Single Trial Look Like?

In our simulation, we assume that the people are numbered from 1 to n and the coats are also correspondingly numbered from 1 to n. A random arrangement of numbers from 1 to n then simulates a virtual “experiment”, where n people picked up n coats in a random manner.

For example, if we have 10 people and the random arrangement is [1, 8, 5, 6, 3, 4, 7, 10, 9, 2] then this means that person 1 got coat 1, person 2 got coat 8, and so on. In this individual experiment, we see that three people got their own coats back (person 1, person 7, and person 9).

If we want to answer our first question, we can generate many random arrangements and count the total number of trials where zero people got their own coats. To answer the second question, we can see how many coats are returned in each trial and take the average over all of those values from each trial.

The Provided Framework

For this section of the homework, you will complete the implementation of the class CoatExperimentSimulator. We have also provided a prewritten class called RandomOrderGenerator whose methods you will use.

Random Order Generator

RandomOrderGenerator has a method called getRandomOrder(int n) that returns a random ordering (permutation) of the numbers from 1 to n (inclusive). In our simulation, this random arrangement of numbers indicates which person picked up which coat. In RandomOrderGenerator we also provide a main method that shows you how getRandomOrder() is used.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class RandomOrderGenerator {

	public static int[] getRandomOrder(int outputLength) {
		List<Integer> range = new ArrayList<>();
		for (int i = 1; i <= outputLength; i++) {
			range.add(i);
		}
		Collections.shuffle(range);
		int[] outputArray = new int[outputLength];
		for (int i = 0; i < outputLength; i++) {
			outputArray[i] = range.get(i);
		}
		return outputArray;
	}

	public static void main(String[] args) {
		// Print the results of RandomOrderGenerator.getRandomOrder(10);
		// ten different times.

		for (int i = 0; i < 10; i++) {
			int[] randomOrder = RandomOrderGenerator.getRandomOrder(10);
			System.out.print("order " + (i + 1) + ": [ ");
			for (int j = 0; j < 10; j++) {
				System.out.print(randomOrder[j] + " ");
			}
			System.out.println("]");
		}
	}
}

For example, the following would produce a random ordering of the numbers from 1 to 10:

int[] randomArrangement = RandomOrderGenerator.getRandomOrder(10);

Do not change anything in this file. Just use the getRandomOrder method in it. You can place this file directly into your Java project.

Coat Experiment Simulator

You have to write one class in the same project in order to do this HW question. It should be called CoatExperimentSimulator.java. It should have one single instance variable called numberOfPeople (please make sure your instance variable is called exactly this). The class must have a simple constructor, which is provided to you.

public class CoatExperimentSimulator {

    private int numberOfPeople;

    public CoatExperimentSimulator(int numPpl) {
        numberOfPeople = numPpl;
    }

    public int numPplWhoGotTheirCoat(int[] permutation) {
        return 0;
    }

    public int[] simulateCoatExperiment(int iterations) {
        return null;
    } 

    public double answerToQuestionOne(int[] results) {
        return 0.0;
    }

    public double answerToQuestionTwo(int[] results) {
        return 0.0;
    }
}

numPplWhoGotTheirCoat() Autograded

This method determines the number of people who got their coat back given an array that represents a randomly generated arrangement. This permutation array will have the same length as the number of people in the experiment.

simulateCoatExperiment() Autograded

This method simulates the coat experiment multiple times and counts the number of people who got their coats back in each experiment. These counts should be stored in an array, which is returned by the method. The returned array should have its length be equal to the number of experiments run. The value at position i in the returned array should represent the number of coats correctly returned in trial i.

The input argument iterations is likely to be a large number so that we have enough data to get a reliable result. Don’t get confused between what iterations and what the field numberOfPeople represent!

answerToQuestionOne() Autograded

Given the results of some number of iterations of the coats experiment, this computes the probability of 0 people getting their coats back by taking the number of times 0 people got their coats back and dividing that number by the total number of iterations run (i.e. the length of the input array).

answerToQuestionTwo() Autograded

Given the results of n iterations of the coats experiment, this computes the average number of people who get their coats back across all experiments. For example, if we run two trials, we might get the output {1, 6}, in which case the average number of coats returned per trial is 3.5.

Optional: What Are the Answers?

You can write yourself a main method and print out the results of your previous work! It is imperative, however, that your other methods should not print anything out at all.

What to Submit for Question 3

CoatExperimentSimulator.java, with the specified methods numPplWhoGotTheirCoat(), simulateCoatExperiment(), answerToQuestionOne(), answerToQuestionTwo(). All of this will be automatically graded. Do not change any of the method signatures. It is imperative that none of these default methods have any print statements! The autograder will break.

General Notes for Question 3

You can write a helper method if you like in order to simplify your code.
Start small! Take this work one method at a time.
Check with your classmates: do your probabilities & averages look about the same?

Submission

Submit PositiveNumber.java, Needle.java, and CoatExperimentSimulator.java. Ensure that your files do not have a package header! Specifically, the first lines of your file should not read package xyz or similar.

Please find these files locally on your file system. By default, they will be found in a folder called eclipse_workspace, often in your user’s directory. You should select each of the files and upload them as files (not as a directory, and preferably not as a .zip either). If you need help, please reach out on Piazza or in Office Hours.