teaching machines

CS 145 Lecture 31 – Decksercise

November 16, 2015 by Chris Johnson. Filed under cs145, fall 2015, lectures.

Agenda

• what ?s
• working with a deck of cards
• for-each loop
• Monte Carlo simulations

TODO

• For a participation point, write a question or two to share before the quiz in tomorrow’s lab. New topics we’ve covered since the last quiz include arrays and ArrayLists.

Note

The theme for the day is cards. We’re going to explore some algorithm ideas and looping mechanics by looking at some exercises for manipulating decks of cards. Let’s start with a Program This:

Write a method generateDeck that generates a deck of cards. The deck will need to allow cards to removed and shuffled around.

I’d start with these two arrays:

/usr/lib/ruby/2.7.0/rubygems/dependency.rb:311:in `to_specs': Could not find 'coderay' (>= 0) among 56 total gem(s) (Gem::MissingSpecError)
Checked in 'GEM_PATH=/.gem/ruby/2.7.0:/var/lib/gems/2.7.0:/usr/lib/ruby/gems/2.7.0:/usr/share/rubygems-integration/2.7.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/2.7.0:/home/johnch/.gems', execute `gem env` for more information
	from /usr/lib/ruby/2.7.0/rubygems/dependency.rb:323:in `to_spec'
	from /usr/lib/ruby/2.7.0/rubygems/core_ext/kernel_gem.rb:62:in `gem'
	from ./coderay:24:in `
'

Some of you may have used regular for loops. Notice that the indices don’t really matter. They only serve as a bridge to the element in the array. What if we could bypass the indices altogether? We can! We’ll use the for-each loop.

Now, let’s complete a few problems:

1. Shuffle the cards.
2. A well-dressed man approaches you with two decks of cards in hand. He says, “Let us play a game. You give me $5. Here’s your deck. Here is mine. We turn over our cards one at a time. If any match, I win and keep your $5. If none match, you win and I give you $10.” Should you play this game?
3. Deal 7 cards to 4 players.
4. Determine if a player’s hand is short-suited.

We’ll solve number 2 through a Monte Carlo simulation. Such a simulation can be summarized as follows: simulate a phenomenon n times and compute your expected value of some measure of interest as the average across all runs. Here’s an interesting historical note about the first formal description to the Monte Carlo

The first thoughts and attempts I made to practice [the Monte Carlo Method] were suggested by a question which occurred to me in 1946 as I was convalescing from an illness and playing solitaires. The question was what are the chances that a Canfield solitaire laid out with 52 cards will come out successfully? After spending a lot of time trying to estimate them by pure combinatorial calculations, I wondered whether a more practical method than “abstract thinking” might not be to lay it out say one hundred times and simply observe and count the number of successful plays. This was already possible to envisage with the beginning of the new era of fast computers, and I immediately thought of problems of neutron diffusion and other questions of mathematical physics, and more generally how to change processes described by certain differential equations into an equivalent form interpretable as a succession of random operations. Later [in 1946], I described the idea to John von Neumann, and we began to plan actual calculations.

Code

Deck.java

/usr/lib/ruby/2.7.0/rubygems/dependency.rb:311:in `to_specs': Could not find 'coderay' (>= 0) among 56 total gem(s) (Gem::MissingSpecError)
Checked in 'GEM_PATH=/.gem/ruby/2.7.0:/var/lib/gems/2.7.0:/usr/lib/ruby/gems/2.7.0:/usr/share/rubygems-integration/2.7.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/2.7.0:/home/johnch/.gems', execute `gem env` for more information
	from /usr/lib/ruby/2.7.0/rubygems/dependency.rb:323:in `to_spec'
	from /usr/lib/ruby/2.7.0/rubygems/core_ext/kernel_gem.rb:62:in `gem'
	from ./coderay:24:in `
'

Haiku