java

Goal:

To demonstrate knowledge of both exhaustive search of a problem space and lookup search through the implementation of a password checker.

Background:

Let's assume that you work for a company that requires employee passwords to be 5 characters, 1-3 of which must be letters (lowercase "a"-"z", no capitals), 1-2 of which must be numbers, and 1-2 of which must be symbols (specifically "!", "@", "$", "%", "&", or "*"). You have been tasked with creating a program to check that employee passwords are "good" passwords within this space. A password is considered to be good if it does not contain any of the 500 most used English words (words from dictionary.txt), or any of these words with one or more numbers substituted for letters (i.e., "7" for "t", "4" for "a", "0" for "o", "3" for "e", "1" for "i", "1" for "l", or "5" for "s"). Your program will have two parts. First, it will enumerate all good passwords, second it will check if enetered passwords are good. If the entered password is not good, your program will recommend 10 alternative good passwords that share the longest possible prefix with the entered password.

Specifications:

· You must implement a De La Briandais (DLB) trie data structure (as described in lecture) to use throughout your project.

· Your main program should be called from the command line one of two ways, either without any command line arguments (e.g., "java pw_check"), or with a single command line argument "-g" (e.g., "java pw_check -g").

· When called with the "-g" argument, your program should generate the list of good passwords and terminate.

· You are provided a list of dictionary words to check in dictionary.txt. Use this file to populate a DLB trie with strings that cannot be contained within user passwords.

· You must also write the full list of words you add to this DLB trie to a text file called "my_dictionary.txt" when your program is run with the "-g" option.

· Use exhaustive search and pruning rules to find all good passwords. Be sure to carefully choose your pruning rules! Your search needs to be as efficient as you can make it.

· You must write the list of good words out to the text file "good_passwords.txt".

· When called without any command line arguments, your program should prompt the user to enter passwords until they wish to stop.

· You should use a DLB trie again to search through the good passwords.

· For each entered password, there are two options: it is either a good password, or it is not.

· If it is a good password, congratulate the user for their wise choice.

· If it is not a good password, find 10 good passwords that share the longest prefix with the entered password and present them to the user as alternatives.

Due: 11:59 PM Oct. 2, 2015

Submission Guidelines:

· DO NOT add "my_dictionary.txt" or "good_passwords.txt" to your git repository. These files must be generated by calling your program with the "-g" command line option.

· DO NOT SUBMIT any IDE package files.

· You must name your main program file pw_check.java.

· You must be able to compile your program by running "javac pw_check.java".

· You must be able to run your game by running "java pw_check [ -g ]".

· You must fill out info_sheet.txt.

· Be sure to remember to push the latest copy of your code back to your GitHub repository before the the assignment is due. At 12:00 AM Oct. 2, the repositories will automatically be copied for grading. Whatever is present in your GitHub repository at that time will be considered your submission for this assignment.

Additional Notes:

· Generating the list of good passwords may take several minutes. Be sure to give yourself plenty of time to debug your program with this in mind.

· The list of good passwords will be rather large, be sure to account for this in how you store it.

· To increase the efficiency of your search for good passwords, be sure not to perform unnecessary dictionary checks. If you can determine that the string you are checking is not a prefix to a dictionary word, then you will not need to check further strings built off of it.

· Also keep in mind that good passwords cannot contain dictionary words anywhere, e.g., "!5andu" is a bad password becuase it contains the word "and".

· You only need to keep in mind the number/letter replacements listed above when looking for dictionary words: "7" for "t", "4" for "a", "0" for "o", "3" for "e", "1" for "i", "1" for "l", and "5" for "s".

· Your DLB implementation must be all your own code, you cannot build the trie around Java builtin data structures such as the ArrayList or LinkedList classes.

Dictonary.txt

the
	be
	of
	and
	a
	to
	in
	he
	have
	it
	that
	for
	they
	I
	with
	as
	not
	on
	she
	at
	by
	this
	we
	you
	do
	but
	from
	or
	which
	one
	would
	all
	will
	there
	say
	who
	make
	when
	can
	more
	if
	no
	man
	out
	other
	so
	what
	time
	up
	go
	about
	than
	into
	could
	state
	only
	new
	year
	some
	take
	come
	these
	know
	see
	use
	get
	like
	then
	first
	any
	work
	now
	may
	such
	give
	over
	think
	most
	even
	find
	day
	also
	after
	way
	many
	must
	look
	before
	great
	back
	through
	long
	where
	much
	should
	well
	people
	down
	own
	just
	because
	good
	each
	those
	feel
	seem
	how
	high
	too
	place
	little
	world
	very
	still
	nation
	hand
	old
	life
	tell
	write
	become
	here
	show
	house
	both
	between
	need
	mean
	call
	develop
	under
	last
	right
	move
	thing
	general
	school
	never
	same
	another
	begin
	while
	number
	part
	turn
	real
	leave
	might
	want
	point
	form
	off
	child
	few
	small
	since
	against
	ask
	late
	home
	interest
	large
	person
	end
	open
	public
	follow
	during
	present
	without
	again
	hold
	govern
	around
	possible
	head
	consider
	word
	program
	problem
	however
	lead
	system
	set
	order
	eye
	plan
	run
	keep
	face
	fact
	group
	play
	stand
	increase
	early
	course
	change
	help
	line
	city
	put
	close
	case
	force
	meet
	once
	water
	upon
	war
	build
	hear
	light
	unite
	live
	every
	country
	bring
	center
	let
	side
	try
	provide
	continue
	name
	certain
	power
	pay
	result
	question
	study
	woman
	member
	until
	far
	night
	always
	service
	away
	report
	something
	company
	week
	church
	toward
	start
	social
	room
	figure
	nature
	though
	young
	less
	enough
	almost
	read
	include
	president
	nothing
	yet
	better
	big
	boy
	cost
	business
	value
	second
	why
	clear
	expect
	family
	complete
	act
	sense
	mind
	experience
	art
	next
	near
	direct
	car
	law
	industry
	important
	girl
	god
	several
	matter
	usual
	rather
	per
	often
	kind
	among
	white
	reason
	action
	return
	foot
	care
	simple
	within
	love
	human
	along
	appear
	doctor
	believe
	speak
	active
	student
	month
	drive
	concern
	best
	door
	hope
	example
	inform
	body
	ever
	least
	probable
	understand
	reach
	effect
	different
	idea
	whole
	control
	condition
	field
	pass
	fall
	note
	special
	talk
	particular
	today
	measure
	walk
	teach
	low
	hour
	type
	carry
	rate
	remain
	full
	street
	easy
	although
	record
	sit
	determine
	level
	local
	sure
	receive
	thus
	moment
	spirit
	train
	college
	religion
	perhaps
	music
	grow
	free
	cause
	serve
	age
	book
	board
	recent
	sound
	office
	cut
	step
	class
	true
	history
	position
	above
	strong
	friend
	necessary
	add
	court
	deal
	tax
	support
	party
	whether
	either
	land
	material
	happen
	education
	death
	agree
	arm
	mother
	across
	quite
	anything
	town
	past
	view
	society
	manage
	answer
	break
	organize
	half
	fire
	lose
	money
	stop
	actual
	already
	effort
	wait
	department
	able
	political
	learn
	voice
	air
	together
	shall
	cover
	common
	subject
	draw
	short
	wife
	treat
	limit
	road
	letter
	color
	behind
	produce
	send
	term
	total
	university
	rise
	century
	success
	minute
	remember
	purpose
	test
	fight
	watch
	situation
	south
	ago
	difference
	stage
	father
	table
	rest
	bear
	entire
	market
	prepare
	explain
	offer
	plant
	charge
	ground
	west
	picture
	hard
	front
	lie
	modern
	dark
	surface
	rule
	regard
	dance
	peace
	observe
	future
	wall
	farm
	claim
	firm
	operation
	further
	pressure
	property
	morning
	amount
	top
	outside