COMP 210, Spring 2001
Homework 11 : palettes, zoos, passwords
Due Nov.21 (wed), at start of class
I encourage you to start these problems on your own, and then meet with your partner to discuss differing facets (large or small), and taking the best features of each, to turn in. This approach works (and is allowed) only if both of you work on the problem in advance, bringing it to a similar state of completion.
You are NOT required to show the template for your programs (woo-hoo!). Your functions should still follow the template, though. And of course, each function should still have a contract and purpose, and reasonable test cases.
Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks (in particular: staple and provide questions), and the Grading Guidelines.
(4pts) Colors can be decomposed into a red, green, and blue component; computer systems often represent colors as a triple of numbers: each component as an integer between 0 (black) and 255 (saturated), inclusive. (Note: these are additive colors.) Computer applications often let the user select a color by having them specify (say) the blue component with a slider, and then displaying a (say) palette of 10x10 color choices (each choice being a reasonably sized square).
Write a function which takes a value for the blue component, and draws a corresponding 10x10 palette. (each color a reasonable-sized square, and colors which reasonably cover the desired spectrum. Note: When the blue component is zero, any reasonable solution contains both pure red and pure black!)
Of course,
be sure to not have arbitrary (unnamed) constants occurring in your code.
You can use any suitable variation on lecture's fori=.
This problem uses the teachpack
color.ss
(located in /home/comp210/Homeworks/Hw11/).
This teachpack includes all the functions of the
draw teachpack
(like start and draw-solid-rect),
plus one more function:
;; make-color: num, num, num --> color ;; Takes in the red, green, and blue components of a color ;; (each in [0,256) ) and returns a color object suitable ;; for use with draw-solid-rect. ;; (define (make-color r g b) ...)To use the teachpack at home, you need to copy that file. color.ss.
;; An accumulator-version of "fori=":
;; Call body on each intgeter in [strt,stop).
;;
;; fori=: num, num, (num --> ANY) --> (void)
(define (fori= strt stop body!)
(cond [(>= strt stop) (void)]
[else (begin (body! strt)
(fori= (add1 strt) stop body!))]))
(define MAX_COLOR 255)
(define PALETTE_ROWS 10)
(define PALETTE_COLS PALETTE_ROWS)
;; Absolute palette dimensions & offset (nw corner), in pixels.
(define OFFSET_X 0)
(define OFFSET_Y OFFSET_X)
(define PALETTE_HEIGHT 200)
(define PALETTE_WIDTH PALETTE_HEIGHT)
;; Dimensions of an individual patch of the palette.
;;
(define patch-width (/ PALETTE_WIDTH PALETTE_COLS))
(define patch-height(/ PALETTE_HEIGHT PALETTE_ROWS))
;; draw-palette-row!: num, num --> (void)
;; Side-effect: Draw a row of the palette as described in hw.
;; row is the row-number; b is the blue-component of the palette.
;;
(define (draw-palette-row! row b)
(fori= 0 PALETTE_COLS
(lambda (col)
(draw-patch! col row b))))
;; draw-palette-cols!: num --> (void)
;; Side-effect: Draw (all columns of) the palette
;; as described in the hw.
;; b is the blue-component.
;;
(define (draw-palette-cols! b)
(fori= 0 PALETTE_ROWS
(lambda (r) (draw-palette-row! r b))))
; Same as draw-palette-cols!,
; but written as a nested loop.
; Fyi.
;
(define (draw-palette-nested! b)
(fori= 0 PALETTE_ROWS
(lambda (i) (fori= 0 PALETTE_COLS
(lambda (j) (draw-patch! j i b))))))
;; draw-patch!: num, num, num --> true
;; Draw a swatch at row r, column j of the pallette.
;; b is the blue component; the other components
;; are determined by row/columns spanning that plane of color space.
;;
(define (draw-patch! r c b)
(draw-solid-rect (patch-corner r c)
patch-width
patch-height
(patch-color r c b)))
;; patch-corner: natNum, natNum --> posn
;; patch-color: natNum, natNum, num --> color
;;
;; Return the nw corner and the color of the patch indexed (i,j),
;; for: i in [0,PALETTE_ROWS), j in [0,PALETTE_ROWS).
;; For patch-color, (i,j) determine the red & green components;
;; the third argument is the third color component.
;;
(define (patch-corner i j)
(make-posn (+ OFFSET_X (* i patch-width))
(+ OFFSET_Y (* j patch-height))))
(define (patch-color i j b)
(make-color ; col# proportional to red content:
(round (* (normalize-halfopen i PALETTE_COLS) MAX_COLOR))
; row# proportional to green content:
(round (* (normalize-halfopen j PALETTE_ROWS) MAX_COLOR))
(round b)))
;; normalize-halfopen natnum, natnum --> num
;; For k in the range [0,max), return what fraction
;; k is is through the range.
;;
;; (normalize-halfopen 0 5) = 0
;; (normalize-halfopen 4 5) = 1
;; (normalize-halfopen 2 5) = 1/2 ; 2 is halfway through the {0,1,2,3,4}.
;;
;; This is problematic for the case max=1.
;; If {0} is the only number in the range, and you're at 0,
;; how far are you through the range -- 0%? 50%? 100%?
;; We'll say to 0%.
;; (normalize-halfopen 0 1) = 0
;;
(define (normalize-halfopen k max)
(cond [(zero? max) (error 'normalize-halfopen "Empty range [0,0).~n")]
[(= max 1) 0]
[else (/ k (sub1 max))]))
; Open the canvas:
(start (+ OFFSET_X PALETTE_WIDTH)
(+ OFFSET_Y PALETTE_HEIGHT))
(draw-palette-cols! (* 0 MAX_COLOR)) ; black, reds, greens, orange.
(sleep 1)
(draw-palette-cols! (* 1/2 MAX_COLOR)) ; ..inbetween..
(sleep 1)
(draw-palette-cols! (* 1 MAX_COLOR)) ; blue, purples, yellows, white.
(draw-palette-nested! (* 1 MAX_COLOR)) ; blue, purples, yellows, white.
Why did we have our loops step by 1, rather than by the color's increment (MAX_COLOR/PALETTE_WIDTH) ? Because when drawing an individual patch, not just the color needs to vary, but also the nw corner of the patch. Reverse-engineering the color-increment to get back a number that can be scaled to find the nw corner is way gross; just pass around those original numbers, and compute the color and nw-corner from those.
Hmmm, if we have 10 columns in the palette,
we want the left-most to be 0% and the right-most to be 100%.
But ranging from 0/COLUMNS up through 10/COLUMNS is eleven values!
Solutions: either
This annoying off-by-one problem is similar to the fact that on exams w/ 100pts possible, there are 101 different possible scores. In particular, for a problem inherently paramterized by N, the program needs to cover N+1 values.
(3pts)
As needed, you can look up in help-desk, to see
for the difference between make-vector
and build-vector.
(define-struct animal (name type)) (define ZOO-SIZE 3) (define bobs-petting-zoo (make-vector ZOO-SIZE (make-animal 'dolly 'sheep))) (define san-diego-zoo (build-vector ZOO-SIZE (lambda (i) (make-animal 'dolly 'sheep))))
make-animal called, altogether?
make-animal is called 4 times
(once via make-vector, and ZOO-SIZE times via build-vector.)
bobs-petting-zoo ("bpz")
and
san-diego-zoo ("sdz"),
write (and evaluate) an expression which transmutes
the animal at index 1 into a llama.
(set-animal-type! (vector-ref bobs-petting-zoo 1) 'llama)
(set-animal-type! (vector-ref san-diego-zoo 1) 'llama)
; For fun, check out the contents: (not required)
;
(define (exhibit-animals zoo zoo-name)
(begin
(printf "Visiting ~a:~n" zoo-name)
(fori= 0 ZOO-SIZE
(lambda (cagenum)
(local [(define beastie (vector-ref zoo cagenum))]
(printf "Cage #~s: A ~s named ~s.~n"
cagenum
(animal-type beastie)
(animal-name beastie)))))
(newline)))
(exhibit-animals bobs-petting-zoo "bob's backyard")
(exhibit-animals san-diego-zoo "san diego")
bobs-petting-zoo
and
san-diego-zoo
don't look similar.)
We see that bob's petting zoo really has the same animal displayed three times, whereas san diego has three distinct animals.
animal: animal: animal: animal:
+==============+ +==============+ +==============+ +==============+
#name: 'dolly # #name: 'dolly # #name: 'dolly # #name: 'dolly #
# ~~~~~~~ # # ~~~~~~~ # # ~~~~~~~ # # ~~~~~~~ #
#type: 'llama # #type: 'sheep # #type: 'llama # #type: 'sheep #
# ~~~~~~~ # # ~~~~~~~ # # ~~~~~~~ # # ~~~~~~~ #
+==============+ +==============+ +==============+ +==============+
^ ^ ^ ^ ^ ^
| | \------------------\ | | |
| \--------------\ | | \---\ |
\---------\ | | \----------------\ | |
| | | | | |
+====|=======|======|====+ +====|======|=======|====+
# | | | # # | | | #
vector: # | | | # vector: # | | | #
# ~~~~~ ~~~~~ ~~~~~ # # ~~~~~ ~~~~~ ~~~~ #
# 0 1 2 # # 0 1 2 #
+========================+ +========================+
^ ^
| |
(define bobs-petting-zoo ---/ ) |
|
(define san-deigo-zoo -----)-----------------------/
Or, this same info in a text version:
(define animal1^ (make-animal 'dolly 'llama)) (define animal2^ (make-animal 'dolly 'sheep)) (define animal3^ (make-animal 'dolly 'llama)) (define animal4^ (make-animal 'dolly 'sheep)) (define bpz^ (vector animal1^ animal1^ animal1^)) (define sdz^ (vector animal2^ animal3^ animal4^)) (define bobs-petting-zoo bpz^) (define san-diego-zoo sdz^)
(5pts) In this problem we will create an entity which has its own password, and which checks for possible security breakins.
Write a function make-passwd-object that takes an initial password and returns a "password object". This password object is a function that takes two inputs, an action (a symbol) and a list.
There are two possible actions.
To prohibit repeated attempts to guess the current password, the object should keep track of failed attempts to check a password or update a password. If there are 4 or more consecutive failed attempts, the object should lock the password object, causing the action invoked via 'check-passwd or 'set-passwd to always fail. I should not be able to write a function which takes in the password object and circumvents this, even if I can look at your code.
Hint: Maintain the current password and
number of consecutive failed attempts as local variables.
(Lectures friday and monday will explore
some interaction between
set!,
local, and
lambda,
though you already have all the knowledge you need for this assignment.)
Example (which you can use as your entire test suite):
(define my-passwd (make-passwd-object 'secret-handshake))
(define your-passwd (make-passwd-object 'open-sesame))
(boolean=? (my-passwd 'check-passwd (list 'is-this-it?)) false)
(boolean=? (my-passwd 'check-passwd (list 'secret-handshake)) true)
(boolean=? (my-passwd 'set-passwd (list 'I-forgot 'treasure-map)) false)
(boolean=? (my-passwd 'check-passwd (list 'treasure-map)) false)
(boolean=? (my-passwd 'check-passwd (list 'secret-handshake)) true)
(boolean=? (my-passwd 'set-passwd (list 'secret-handshake 'pet-name)) true)
(boolean=? (my-passwd 'check-passwd (list 'pet-name)) true)
(boolean=? (my-passwd 'check-passwd (list 'clumsy-breakin-attempt)) false)
(boolean=? (my-passwd 'check-passwd (list 'clumsy-breakin-attempt)) false)
(boolean=? (my-passwd 'check-passwd (list 'pet-name)) true)
(boolean=? (my-passwd 'check-passwd (list 'another-clumsy-breakin-attempt))
false)
(boolean=? (my-passwd 'check-passwd (list 'if-at-first)) false)
(boolean=? (my-passwd 'check-passwd (list 'i-dont-succeed)) false)
(boolean=? (my-passwd 'check-passwd (list 'persistence-gets-me-arrested)) false)
(boolean=? (my-passwd 'check-passwd (list 'pet-name)) false)
(boolean=? (my-passwd 'set-passwd (list 'pet-name 'trojan-horse)) false)
(boolean=? (your-passwd 'check-passwd (list 'open-sesame)) true)
(define TOO_MANY_FAILURES 4)
;; make-passwd-object: symbol --> (symbol x list-of-symbol --> boolean)
;;
(define (make-passwd-object initial-password)
; These locals retain their values across calls to the returned object:
(local [(define passwd initial-passwd)
(define fails 0) ; Count of successive fails.
(define shutdown? false) ; Have we shut this object?
; verify: symbol --> boolean
; Is the presented password okay?
; Side-effect: update the count "fails" and
; set shutdown? if necessary.
;
(define (verify passwd-presented)
(if (symbol= passwd passwd-presented)
(begin (set! fails 0)
true)
(begin (set! fails (add1 fails))
(when (>= fails TOO_MANY_FAILURES)
(set shutdown? true)
;(email account-manager)
)
false)))
(define (set-p old-passwd new-passwd)
(cond [(verify old-passwd)
(begin (set! passwd new-passwd)
true)]
[else false]))]
;; Now, the body of the local:
;; we return the password object, which is a function:
(lambda (action args)
(cond [shutdown false] ; Don't even start.
[(eq? action 'check-passwd)
(verify (first args))]
; Boring (but important) code would be to verify that args
; really contains the right number of arguments.
; Not needed for this class.
[(eq? action 'set-passwd)
(set-p (first args) (second args))]
[else (error 'password-object "Unknown message ~s.~n" action)]))))
Be sure that to have a single point of control
for incrementing the failed count, and re-setting it to 0.
(Make sure that both types of actions can increment the failed-count --
if either of them doesn't check this, a hacker could repeatedly call
that function w/ every word in the dictionary,
which might break poor passwords.)
(How many words in a typical dictionary?
Is it feasible to try all pairs of words?
All words but with a digit placed inside?
Calculate some of these numbers, and assume
a program can try 106 passwords per second.
Note that some systems, instead of or in addition to locking
the account after a certain number of failures,
make sure the "verify" routine takes a long time to run -- e.g. 1/10 of
a second, so that trying a million passwords becomes intractible.
Note, however, that it should take this long regardless of
whether or not the attempt fails,
else timing information gives the answer, and the hacker
can try guessing a password through a different port (e.g. making
a new web connection, if this is a web-based passwrd).
Note that in this version, we centralize the check
for whether the object's been shut down in the main
dispatch function.
This is not necessary for this assignment;
it's okay to have this check in both the code which
processes 'check-passwd and 'set-passwd.
Why is it okay?
Because this design, while consolidating code,
also precludes doing anything with a password once it's
shutdown, but conceivably you might want to still do stuff.