CS:2820, Machine Problem 4, Spring 2020

The reference solution, when run with the above input, produced the following output on one run:

Person@42a57993 homemaker home Place@75b84c92
Person@6bc7c054 homemaker home Place@75b84c92
Person@232204a1 homemaker home Place@75b84c92
Person@4aa298b7 worker home Place@75b84c92 work Place@7d4991ad
Person@28d93b30 worker home Place@1b6d3586 work Place@4554617c
Person@74a14482 worker home Place@1b6d3586 work Place@4554617c
Person@1540e19d worker home Place@1b6d3586 work Place@4554617c
Person@677327b6 student home Place@1b6d3586 school Place@14ae5a5
Person@7f31245a student home Place@6d6f6e28 school Place@135fbaa4
Person@45ee12a7 student home Place@6d6f6e28 school Place@330bedb4

Person@42a57993 homemaker home Place@75b84c92
Person@6bc7c054 homemaker home Place@75b84c92
Person@232204a1 homemaker home Place@75b84c92
Person@4aa298b7 worker home Place@75b84c92 work Place@7d4991ad
Person@28d93b30 worker home Place@1b6d3586 work Place@7d4991ad
Person@4554617c worker home Place@1b6d3586 work Place@74a14482
Person@1540e19d worker home Place@1b6d3586 work Place@74a14482
Person@677327b6 student home Place@1b6d3586 school Place@14ae5a5
Person@7f31245a student home Place@6d6f6e28 school Place@135fbaa4
Person@45ee12a7 student home Place@6d6f6e28 school Place@330bedb4

Notice that people are always listed in exactly the same order they were created, and people were "poured" into places in exactly the same order, so all the homemakers end up in the same home, along with the first worker, and the next 3 workers plus one student end up in the second home. The only real difference between the to runs lies in the number of workers assigned to each workplace. That difference is because the input file had a nonzero scatter for workplace size but the scatters for the other are zero.

This is not realistic! In the real world, households usually contain people with different roles, not all the same role, and if two members of the household both have the same role, they have a high likelihood of having different places. There may be two students in the household, but they are likely to go to different schools, and if there are two workers, they probably work at different places.

What we ought to do is assign people to places more or less at random within the constraints of their list of roles. Solving this problem should not change the number of places created from each class of place, and for each person, they should be connected to exactly the same number of places as before.

Also, there is still likely to be lots of code duplication. Certainly, the reference solution repeats big blocks of code over and over for things like making sure numbers are positive and other sanity constraints. This is a typical result of rushed deadline-driven development. Since this assignment does not involve any change to the input format for the program, it might be a good idea to use this opportunity to clean things up by finding repetitive patterns in the code and dealing with them.

Assignment

Hint, the Java Collections framework offers two static methods called Shuffle that can be used to shuffle the items in a list. If you shuffle the right list or lists at the right point, you can break the correlations you are required to break for this assignment. Be careful to use only one random number stream!

Breaking the correlation can be done with a remarkably small amount of code if you take the time to understand the problem carefully before writing any code. Far larger and more difficult solutions will typically result from brute-force solutions.

Submission

On or before the end of Monday, Mar. 1, you must submit your program using the following shell command on the fastx machine:

~dwjones/submit xxxx Epidemic.java

Substitute your section number for xxxx above, but do not alter the text dwjones.

The program will confirm that you successfully submitted your solution with the message "submiter: succesfull submission of xxxx/HawkID" with xxxx replaced with your section number and HawkID replaced with your HawkID.

You may submit as many times as you want. The last successful submission is the one that will count. As such, it is a good idea to submit as soon as you have code that sort-of works, submit again when you have code that works the way you like, and perhaps submit again when you bring your code up to the highest standard of readability.

Grading

Code that executes correctly is worth half credit (2.5 out of 5 points). Expect demerits for the usual style issues in addition to the "on inspection" criteria given above:

Student Questions

A student asked: There are two shuffle methods. Does it matter which I use?

Collections.shuffle( myList );
This version allocates its own random stream, initializing it however it wants, and then does the shuffle. You have no control of how it randomizes, and each time a shuffle is done, it uses a new random stream.
Collections.shuffle( myList, myStream );
With this version, you take control of how the shuffle gets random numbers. You are in control of what stream of randomness it uses, when that stream is created, and what seed it uses.

The seed is the initial value that is used to generate the stream of random numbers. The stream is generated by updating the seed using a deterministic function that, if you didn't know the function, would appear to be random. In the case of class Random, you have two choices:

Random myStream = new Random();
You let the Java library pick the seed. It makes an honest try at picking a seed using physical randomness by mixing things like the time of day to the nearest microsecond with other stuff outside your control. This is useful in production use because if something is supposed to be random, it shouldn't always happen the same way in different runs of the program.
Random myStream = new Random( n );
With this version, you take control of the seed, providing some integer n as a starting value. This is useful for debugging becaue it means that each time you run your program, you'll get the exact same sequence of values, so if you find a bug, you can try to fix it and then run the program again with the same input and know that the only difference in behavior is due to your change and not to a different seed being used.

Aside from this, you never need to worry about the seed. Note that the Java library documentation is quite open about the exact algorithm Java uses. It gives the multiplier, addend and modulus used to update the seed, and it gives the exact algorithm used to construct the pseudo-random numbers returned from the stream using the sequence of seed values.

A student asked: My solution breaks the correlation, but the output no-longer groups people by role. Is this a problem?

As I said in lecture, the order of output of the people is not an issue. Even in a solution to MP3, it would have been perfectly acceptable to output the population in any order.

First note, because you are unlikely to use the same seed I used, your output will not be the same as mine, and it will be different each time you run the program unless you take control of the seed for the pseudo-random number generator. Here is one run of my first solution to the problem, using the same input as suggested for MP3:

Person@42a57993 worker home Place@75b84c92 work Place@6bc7c054
Person@232204a1 homemaker home Place@75b84c92
Person@4aa298b7 student home Place@75b84c92 school Place@7d4991ad
Person@28d93b30 worker home Place@75b84c92 work Place@6bc7c054
Person@1b6d3586 worker home Place@4554617c work Place@6bc7c054
Person@74a14482 worker home Place@4554617c work Place@1540e19d
Person@677327b6 student home Place@4554617c school Place@14ae5a5
Person@7f31245a homemaker home Place@4554617c
Person@6d6f6e28 student home Place@135fbaa4 school Place@45ee12a7
Person@330bedb4 homemaker home Place@135fbaa4

Here is the output from a second run with the same input but a different seed:

Person@42a57993 student home Place@75b84c92 school Place@6bc7c054
Person@232204a1 worker home Place@75b84c92 work Place@4aa298b7
Person@7d4991ad homemaker home Place@75b84c92
Person@28d93b30 homemaker home Place@75b84c92
Person@1b6d3586 worker home Place@4554617c work Place@4aa298b7
Person@74a14482 student home Place@4554617c school Place@1540e19d
Person@677327b6 student home Place@4554617c school Place@14ae5a5
Person@7f31245a worker home Place@4554617c work Place@4aa298b7
Person@6d6f6e28 homemaker home Place@135fbaa4
Person@45ee12a7 worker home Place@135fbaa4 work Place@330bedb4

This solution is defective! The problem is, it successfully broke the correlation between roles and places, but it left a correlation between places. So, while the residents of a home are unlikely to have the same role, if two workers do live in the same home, they are highly likely to have the same workplace.

When I fixed the above problem, throwing out code that shuffled things at the wrong point, the solution I came up with output the people in the same order as my solution for MP3. The order in which the people are output is irrelevant. What matters is that this solution did a good job of shuffling all the places:

Person@42a57993 homemaker home Place@75b84c92
Person@6bc7c054 homemaker home Place@232204a1
Person@4aa298b7 homemaker home Place@7d4991ad
Person@28d93b30 worker home Place@7d4991ad work Place@1b6d3586
Person@4554617c worker home Place@75b84c92 work Place@74a14482
Person@1540e19d worker home Place@7d4991ad work Place@1b6d3586
Person@677327b6 worker home Place@7d4991ad work Place@74a14482
Person@14ae5a5 student home Place@75b84c92 school Place@7f31245a
Person@6d6f6e28 student home Place@232204a1 school Place@135fbaa4
Person@45ee12a7 student home Place@75b84c92 school Place@330bedb4

There are quite a few bricks of code that look like this in my posted solution to MP3:

// force the median to be positive
if (median <= 0) {
    Error.warn(
	"place " + name + " " + median + " " + scatter +
	": non-positive median?"
    );
    median = 1.0F;
}

There are several ways go go about compacting them that would make the code more readable by moving one or another part of this code into a helper method somewhere. If you merely create one helper method for each of these code bricks, you would not do much good, but if you can find common subexpressions or common control structgures that are used more than a few times and move them into helper methods, you can significantly improve the readability of the code.

Some people call this "factoring the code," because it is akin to what you do when you rewrite an algebraic expression. Consider this expression:

(a + b)(c + d) + (e + f)(c + d) + (g + h)(c + d)

We can find the common factor and rewrite the expression as:

(c + d)(a + b + e + f + g + h)

The result is much more readable. So, the challenge is, can you find something to factor out of the code in order to make it easier to read?

Machine Problem 4

Due Mar 1, on line

Background

Assignment

Submission

Grading

Student Questions