1.The CS5 Times
Eager Penguins Invade Computer Lab
Claremont (AP): The first-day offering of Harvey Mudd’s popular CS5 laboratory was disrupted when a large flock of penguins took every seat in the room. “They’re cute,” complained a distraught student, “but they smell like fish and there’s no room for us.”
Professors attempted to drive the penguins away by repeatedly shouting “Shark!”, but the penguins were unmoved.
Handouts (read them all!):
Today’s lecture notes
A preprinted blank "worksheet”
Light reading? ;^)
Prof. Geoff Kuenning, Olin 1255
http://www.cs.hmc.edu/~geoff/geoff-schedule.html
(Official course alien)
3.Programming Languages…
* A+
* A++
* A#
* A-0 programming language
* ABAP
* ABC
* ABC ALGOL
* ABLE
* ABSET
* ABSYS
* ACC
* Accent
* ACT-III
* ATOLL - Acceptance, Test Or Launch Language
* Action!
* ACS
* ActionScript
* Actor
* Ada
2000 languages omitted
* YAFL
* Yellow - Rejected prototype for Ada
* Yorick
* Y Language
* Z notation - A program specification language, like UML
* ZOPL.
* ZPL
* ZUG
* ZZT-oop
4.Python
Relatively “nice” syntax
Emerging as language of choice in many fields
Packages for graphics, audio, scientific computing, …
Befunge
class HelloWorld {
static public void main( String args[] ) {
System.out.println( "Hello World!" );
}
}
Java
print(“Hello World”)
Python
Prof. Geoff takes on Python…
5.Hello World…
#include
main()
{
cout << "Hello World!" << endl;
return 0;
}
C++
Ook
6.Some Things You’ll Do This Semester…
Sequence alignment
ATTATCG
ACATTC
Distance is 4
ATTAT-CG
A-CATTC-
ATTATCG ->
A TATCG ->
A CAT_CG ->
A CATTCG ->
A CATTC
Delete T
Change T to C
Insert T here
Delete G
7.Spel Cheking…
8.Huffman Data Compression
9.Connect 4 AI
10.The Alien's Life Advice
SMILE!
It makes people think you’re fun to be with.
11.Picobot
area already covered
area not covered (yet!)
walls
Goal: whole-environment coverage with only local sensing…
Picobot!
Murata Girl
Roomba
This language is not Turing-Complete. I guess that makes it “unreasonable”!
DEMO!
Reading: Chapter 1 in the book
(http://www.cs.hmc.edu/csforall/)
12.Environment in the NEWS!
Picobot can only sense things directly to the N, E, W, and S
For example, here its surroundings are
NxWx
N
E
W
S
N E W S
Surroundings are always in NEWS order.
13.How many distinct surroundings are there?
N
E
W
S
xxxx
Nxxx
xExx
xxWx
xxxS
NExx
NxWx
NxxS
xEWx
xExS
xxWS
NEWx
NExS
NxWS
xEWS
NEWS
(won’t happen)
== 16 possible …
24
Surroundings
14.State
Picobot's memory is a single number, called its state.
State is the internal context of computation.
State and surroundings represent everything the robot knows about the world
Picobot always starts in state 0.
I am in state 0.
My surroundings
are xxWS.
15.Rules
Picobot moves according to a set of rules:
state
surroundings
0
xxWS
0
N
direction
new state
If I'm in state 0 seeing xxWS,
Then I move North, and change to state 0.
Aha!
I should move N.
I should enter state 0.
A capital “X” here means “Don’t Move”
I am in state 0.
My surroundings
are xxWS.
16.Wildcards
Asterisks * are wild cards. They match walls or empty space:
0
x***
0
N
state
surroundings
direction
new state
and EWS may be wall or empty space
I am in state 0.
My surroundings
are xxWS.
Aha! This matches x***
N must be empty
17.What Will This Set of Rules Do to Picobot?
0
x***
0
N
0
N***
0
X
state
surroundings
direction
new state
Picobot checks its rules from the top each time.
Only one rule is allowed per state and surroundings.
When it finds a matching rule, that rule runs.
->
->
Add some code here to make Picobot go up and down in the same column forever!
A capital “X” here means “Don’t Move”
18.0
x***
0
N
0
N***
1
X
1
***x
1
S
1
***S
0
X
state
surroundings
direction
new state
Picobot checks its rules to find one that applies
Only one rule is allowed per state and surroundings.
When it finds a matching rule, that rule runs.
->
->
->
->
What Will This Set of Rules Do to Picobot?
19.This Week!
Write rules that will always cover these two rooms.
(separate sets of rules are encouraged…)
Lab Problem
Problem 2
our best: 4 states, 8 rules
our best: 3 states, 7 rules (but Cam Zhou had 6)
Your “program” can be slow but it should work for any starting location and for any wall-connected maze!
DEMO!
20. What’s the Point?
Simple syntax can support “powerful” computation: The picobot language syntax is very simple, yet it can control a robot in a complex environment.
Computer scientists examine limitations of languages:
Are there environments that the picobot language cannot navigate?
If so, what features could be added to give the language more “power”?
21.How About “General” Rooms?
Picobot has 100 states, but the “room” could be arbitrarily big and weird!
22.Python and the Command Line
Python makes it easy to experiment!
I goofed here
No worries, just try again
This way I don’t have to say math.pi
23.Python and the Command Line
Python makes it easy to experiment!
24.Defining Your Own Functions!
def dbl(x):
return 2 * x
dbl
x
2 * x
def dbl(myArgument):
myResult = 2 * myArgument
return myResult
Notice the indentation. This is done using “tab” and it’s absolutely necessary!
“Outdent” with shift-tab!
Sublime often indents for you!
25.def dbl(x):
”””This function takes a number x
and returns 2 * x”””
return 2 * x
Docstrings!
This is sort of like teaching your programs to talk to you!
26.# Doubling program
# Author: Ran Libeskind-Hadas
# Date: August 27, 2011
# Time Spent: 14 hours
def dbl(x):
”””This function takes a number x
and returns 2 * x”””
return 2 * x
Docstrings…and Comments
27.Composition of Functions
def quad(x):
return 4 * x
quad
x
4 * x
def quad(x):
return dbl(dbl(x))
Doubly cool!
28.# myFunc
# Author: Ran Libeskind-Hadas
# Date: August 27, 2011
def myFunc(x, y):
“””returns x + 42 * y“””
return x + 42 * y
Multiple Arguments...
myFunc
x, y
x + 42 * y
That’s a kind of a funky function!
30.from functools import reduce
def add(x, y):
"""returns x + y"""
return x + y
>>> reduce(add, [1, 2, 3, 4])
10
reduce-ing with Python...
add
add
add
31.Google’s “Secret”
This is what put Google on the map!
32.Try This…
Write a function called span that returns the difference
between the maximum and minimum numbers in a list…
>>> span([3, 1, 42, 7])
41
>>> span([42, 42, 42, 42])
0
min(x, y)
max(x, y)
These are built in to Python!
33.Try This...
Write a python function called gauss that accepts a positive integer N and returns the sum
1 + 2 + … + N
2. Write a python function called sumOfSquares that accepts a positive integer N and returns the sum
12 + 22 + 32 + … + N2
You can write extra “helper” functions too!