teaching machines

CS 145 Lecture 22 – Loop-and-a-half

October 26, 2015 by Chris Johnson. Filed under cs145, fall 2015, lectures.

Agenda

• what ?s
• what does this do?
• looping patterns:
  • loop and a half
  • accumulation
  • selection

TODO

• Let’s not have lab tomorrow. This was anticipated! Quiz 4 is and has been scheduled for next week.
• For Wednesday, complete some loop questions on CodingBat, sections String-2 or String-3, or Practice-It!, section BJP3 Chapter 5.

Note

Loops add a motor to our code. They definitely open up the possibilities of what we can do in our programs, but things can also get out of hand very easily. Our best bet is to write and read many loops. Let’s read some in another installment of What Does This Do?! I’ll reveal the following code snippets one at a time. Read and absorb them for at least 30 seconds before saying what you think the code is doing.

1. /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 `
   '
   

2. /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 `
   '
   

3. /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 `
   '
   

4. /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 `
   '
   

We almost never write code from scratch. Even if we don’t call any helper methods, we still see similar patterns over and over again in our algorithms. Let’s example a few patterns through some examples.

We start with the loop and a half. This pattern emerges when we want to execute some portion of our repeated step more than another portion. We’ll look at an example of signing off a love note with “xoxoxoxoxox”, expressing lineage sentences like “A begat B begat C”, and generating a spherical triangle in Madeup. There’s not necessarily a clean way to solve this problem. We could condition that some portion of our code on the iteration count:

for i through bound
  do everytime stuff
  if i < bound (or perhaps i > 0)
    do inbetween stuff
  do everytime stuff
end

Or we could break out the portion before or after the loop:

do half step on item 0
for i in 1 .. bound
  do full step
end

for i in 0 to bound
  do full step
end
do half step on last item

Next we observe the accumulation pattern, where a loop iterates through a collection and accumulates values in some variable of larger scope. We’ll look at some examples of normalizing an image and calculating a linear approximation of a dataset.

Code

LoveLetter.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 `
'

Lineage.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