Lab 00: Word Puzzles
Small Group, Due: 2025 Dec 2, 11:59pm
In this lab challenge, you will work on a word puzzle generator. You are required to submit at least one word puzzle that fits the appropriate requirements.
You may work in a group of no more than three, but each group member must submit a unique puzzle.
Crossword
Write a program that generates a Crossword puzzle. Specifically, generate a crossword puzzle from a given list of words each with an associated hint.
The example below...
__
__ |1_|
__|2_|____________________ |__|
|3_|__|__|4_|__|__|__|__|__| |__|
|__| |__|_________________|__|__
|__| |5_|__|__|__|__|6_|__|__|__|
|__| |__| |__| |__|
______________|__|________ |__|
|7_|__|__|__|__|__|__|__|__| |__|
|__| |__|
________|__|_______________
|8_|__|__|__|__|__|__|__|__|
|__|
Down:
1. having two
2. FIFO
4. interface for comparing
6. LIFO
Across:
3. sorts in ~N lg N time, guaranteed!... probably
5. stable sorts in ~N lg N time, guaranteed!... but requires extra memory
7. neg -> less, pos -> greater, zero -> equal
8. sorts in subquadratic time... but with unknown average case
The words may go down or across. All words must be connected via a crossing with every other word in the crossword puzzle (in other words, only one connected component).
Your submission is a crossword puzzle that contains at least 10 words that relate to COS265, each with a clever definition.
Tricky:
- How to ensure no two down or across words are adjacent unless it forms a word?
- How to handle a cycle of crossing words, not just a tree?
Note: You do not need to draw fancy crossword puzzle. It is completely acceptable to simply write the words out as if it were a finished crossword puzzle.
Down: B
1. having two Q I
2. FIFO Q U I C K S O R T N
4. interface for comparing E O A
6. LIFO U M E R G E S O R T
E P T Y
Across: A A
3. sorts in ~N lg N time, guaranteed!... probably C O M P A R E T O C
5. stable sorts in ~N lg N time, guaranteed!... A K
but requires extra memory B
7. neg -> less, pos -> greate, zero -> equal S H E L L S O R T
8. sorts in subquadratic time... but w/ unknown avg case E
Word Find
Write a program that generates a Word Find puzzle. Specifically, given a width, a height, and a set of words, print out a width×height block of characters where each of the given words is hidden at least one time (best if it is exactly once) among a bunch of random other characters.
The example below contains the 7 words listed at the bottom in a 40×20 block.
R U E T T I I B R S T N O R T R O S G R E M T E R S R O S E L B B U B M R M E I I B N C R X S O O S O S C O S B R T B U O L R T R N O B T R O S M I T O R S N R N B S E O S S T E G N R R O S N O I T R E S N I O G T G I T T T S T S I I E T O S L S L S O S L E O O S T N T R O S O G O B C M T I S S O S R R O N I N O L L S E E E E T R E L I T Q S S K R A D I X S O R E D I E M O O B R E O N O I T E B N R S O S U C N T B U S T O O E E R N T K I R O S X I D A R O M I S M Q Q T C R O T O R S T E R O C T R B S R B T T R I C G B N D S S T R S T T E R U U T S T O I I R B I O E G K R O R E N N T S T O M S E R N E O I N X T C R T C C R B S I S T O N O I S O S O S S L O B R L O T I O N T L S Q R T I R E T S K K O T U U O X R N N R N S O S O O B T S S U R S D R A X U O E S K D O L I N S S S T B B O N I E S K I O R G G M B O R Q E K B A T R S R O T R S A S E O O O O E A R N B I S D S O X R T R O M U I R O T U O C B D T Q R N I I R K S N I R R L O R I I L E T A N R T S E B E B O S T S E T I S U L I I E B I T C E S T T T B S Q I O R E E T R I S R M M R B R R S R G M R X C B Q E X T N I U B O C S T B R E B U L T S I O S D A R T G E T R B L E R U E E T K O T S S T Q O R E I R U M U I N E C R O S X I D T S S X M R B E R O E I D S O T S G S O O T T L I R B O R I R R I B K R T T S T E O B S M E G S S K M E T T I N N O O E R R E I R U R O S N O I T R E S N I O B R R R N O R R S I T R O S K C U Q E R S M S T T S O B I B S E L E C T I O N S K S A M O L A E G O S T R O S O G O B O T O R S R O S N O I T R E S N I O I R B T S B B I X D C S E R O S B R T M S T R I I R M R O S E L B B U B U I U X N T T BUBBLESORT INSERTIONSORT MERGESORT QUICKSORT RADIXSORT TIMSORT SELECTIONSORT
The words may appear horizontally or vertically (or diagonally... or the reverse of these). Words may cross. In the case above, a word might even wrap around the edge of the block... See if you can find them all!
Your submission is a 50×20 word find puzzle that contains all of the following words:
data |
enqueue |
queue |
mergesort |
|
structures |
dequeue |
stack |
insertionsort |
|
algorithms |
push |
array |
selectionsort |
|
java |
pop |
linkedlist |
quicksort |
|
programming |
insert |
graph |
shellsort |
Interesting question: how small can the puzzle be such that all the words still fit?
Below is a very difficult word find puzzle. Good luck!
T L E I R E E R A R O M E K R T D I O O R S A A E T T S Q R D U I S M O E M A D
E A R A R T R L V T I A S M T R A N I S P O I U I R S C P A T N M I K S O A T R
T T M I S O R R L M S E R E A O T S T L E R M E U O G O E S O R M P R C R E E R
Q S K C I U Q O I S S L M S H S A A C E S T O U A S N M D I Q E A P L S C S T R
C O M P A R T O S K O R A M T K C E E H G G R E R N D P S P E G R I A R N T O U
C A T G O A C R I N U R S C S C B O L S L Q M Q R O L A A S E R G R A I C I A H
L R T H U S E I I R O R T Q K I T E E T U S B K A I M R M T O E O O U C M M L L
I S T R T T G M H E C I A R R U A S S E T A E M Y T S A D A G S R L I N K E D L
E T L E E S L T T M O O T S R Q A R U P A C T H T C E B E C S H P I R T E A T E
K N I L E D R S U E M U N R A T A E R I V S T T A E R L Q K R U O B T S I L B E
L A B I S Q S M R R P R S S E I T S T Y A J U I R L U Q U P T S S M H T I R O G
H A M I S S I K C G A S K E S S I R R G J M G R I E T L E G N I M A R G O R P E
R M L N D A T U M E R T M I U R N I Q R R E O O I S C G S E P U T C U R T S A A
O E O M S A B G J S E N T U O S C I S T R R T G M E U H B S A P G U P G T O C A
A I N R Q H S P V O T C I T C T T J N R R G U L A R R U E Q R U N T A O C O P R
COMPARETO COMPARABLE ALGORITHMS SELECTIONSORT DATA STRUCTURES
PROGRAMMING SHELLSORT JAVA STACK QUEUE QUICKSORT LINKEDLIST
ARRAY MERGESORT INSERTIONSORT
Requirements
Choose one of the word puzzles above, and submit a puzzle that fits the respective requirements. Your puzzle will need to be in a Markdeep file.
Note: you can simply copy-paste the output of your program into a Markdeep file. Your code does not need to generate the Markdeep file directly.
Note: place triple backticks (```) at the top and bottom of your puzzle, Markdeep will treat the puzzle as plaintext or code and respect your spaces and newlines.
The backticks are called code fences.
You will receive extra credit by submitting up to 3 additional puzzles (4 in total) that your code generates.
Submission
| Submission | |
| 3pts | Markdown file containing puzzle |
| 3pts | Source code to generate puzzle |
| Extra Credit | |
| +3pts | Extra Credit: Up to 3 additional puzzles |
| +3pts | Extra Credit: Exceptionally well done |
| +3pts | Extra Credit: Submission contains both puzzles |