# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
 [quote="LordKinbote"][quote="Zag"]Also, it sounds as if this is a pretty beginning class, but if its more than first year, or perhaps just with your best students, you might want to talk a little about algorithms. For instance, finding the words with at least two other anagrams will require a little cleverness in approach, if you want the process to finish in a reasonable amount of time. Testing every word against every other word is not a good idea. You could ask them to brainstorm different approaches that will be more efficient than that.[/quote] It is a beginner's course, but we have discussed that there are solutions to problems that work significantly quicker than others. Tomorrow will be the first time in class we will have worked with data of any substantial size though. Part of what I want them to do is *try* inefficient solutions so that I can say "Okay, that will work...but might take a few hours or more RAM than you have." Off the top of my head, I'm thinking the easiest way to find anagrams is to walk through the wordlist, sort the letters in each word alphabetically, and then put them into a dictionary that looks like {alphabetical_word:[word1,word2,etc.], ...} then return all the words that have a list two elements or greater? This seems like it should work a hell of a lot better than, say, checking every permutation of a word against the word list. Edit: Yeah, that worked really really quickly...CATER/CRATE/CARET/REACT/TRACE is the winner, by my wordlist. Edit: Actually, my current wordlist has no inflections. I found a couple of sixes if I use my wordlist that includes inflections.[/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
Jack_Ian
Posted: Thu Feb 21, 2013 7:54 pm    Post subject: 1

Perhaps getting them to create a simple Stream Cipher would be a good introduction into both random numbers and cryptography.

Essentially you use a pseudo random number generator to encrypt a file.

Seed the Random Number generator with a known key (or with one to be hidden within the cyphered text).
repeat
Get Next Random Number
Get the next character
XOr the random number with the character
Store the result
until source file is empty
Nsof
Posted: Thu Feb 21, 2013 3:57 pm    Post subject: 0

Elethiomel wrote:
(The BMP suggestion comes closest to an actual I/O problem.)
I think the search engine is also io intensive (from teaching and program execution perspective).
The BMP requires binary access while the search engine would depend on implementation. Not sure this is covered in the class.
LordKinbote
Posted: Thu Feb 21, 2013 2:38 am    Post subject: -1

Amb wrote:
I second this suggestion:

"Find the highest scoring 7 letter scrabble word. Or better, find the 10 highest scoring 7 letter scrabble words. "

But no word may have an impossible combination such as PIZZAZZ

I gave them the first version of this question, though I like the second version of this question...too late it to assign it to the kids, but I wrote an answer for myself, and it's a good use of using a dictionary to keep track of many values at once (just create a dictionary to act as the tile bag and pull letters out of the bag as you use them, and use the blank tiles if necessary).
Amb
Posted: Thu Feb 21, 2013 12:51 am    Post subject: -2

I second this suggestion:

"Find the highest scoring 7 letter scrabble word. Or better, find the 10 highest scoring 7 letter scrabble words. "

But no word may have an impossible combination such as PIZZAZZ
LordKinbote
Posted: Thu Feb 21, 2013 12:03 am    Post subject: -3

Elethiomel wrote:
Sounds like there's really just one I/O problem in this thread: Read the word list into memory. If you really want to teach them more about I/O (I'm guessing you don't), then you should be talking about stuff like random access (seeking) and memory mapping of files.

(The BMP suggestion comes closest to an actual I/O problem.)

No, I do, and you're right, it's less about dealing with a large amount of data than it is doing a whole bunch of I/O commands. Basically, I taught them the following things so far:

Opening and closing a file
file.seek(num)
How file types can be iterated.

For what we've learned thus far, there is only so much interesting stuff that you can do that is purely file i/o (especially since I've only covered the i, not the o). Tomorrow (or, as tomorrow is likely a snow day, Friday), we'll cover the other side and we'll talk how one can write to a file, or read a file, make changes, and then output. Sorry if I was misleading about my goals.

Their final project will have to have some sort of file i/o component, so they will continue to get practice with it.
Elethiomel
Posted: Wed Feb 20, 2013 11:31 pm    Post subject: -4

Sounds like there's really just one I/O problem in this thread: Read the word list into memory. If you really want to teach them more about I/O (I'm guessing you don't), then you should be talking about stuff like random access (seeking) and memory mapping of files.

(The BMP suggestion comes closest to an actual I/O problem.)
Amb
Posted: Wed Feb 20, 2013 11:15 pm    Post subject: -5

If you did the palindrome idea: Then you could find:

1. All words that, when 1 letter is removed - becomes a palindrome.
2. All words that, when 1 letter is added - becomes a palindrome.
3. All words that when 1 letter is changed to any one specific other letter becomes a palindrome.
4. All words that when 1 letter is changed to any other letter - it becomes a palindrome regardless of what that letter is. (ie the centre letter)

Finally: From the lists above, only keep combinations that were words before the transformation and words AFTER the transformation as well.
extropalopakettle
Posted: Wed Feb 20, 2013 12:07 am    Post subject: -6

Hmmm ... just off the top of my head, and this one sounds devilish: Arrange all the words like as in a completed crossword puzzle (or scrabble arrangement) of minimal height times width. This would assume that all the words can in fact be arranged into a connected crossword puzzle (though then again, you could remove the requirement of connectedness).

Yes, way too much for an intro course - but fun to get them thinking at least.
Jack_Ian
Posted: Tue Feb 19, 2013 4:30 pm    Post subject: -7

Compare 2 paragraphs and report on which words were inserted/deleted. (Trickier than you might think)
Nsof
Posted: Tue Feb 19, 2013 2:38 pm    Post subject: -8

1. Have them read a bitmap file and change the image somehow.
2. Build a text search index of an input file (or a whole directory) and a search functionality.
3. Something about redirecting io streams. file, memory, sockets, screen.
4. Video transcoding (if python has good utilities for this)

Make sure the balance between io and algorithms is right (or they might thing io is fun )
Thok
Posted: Tue Feb 19, 2013 11:52 am    Post subject: -9

Find the highest scoring 7 letter scrabble word. Or better, find the 10 highest scoring 7 letter scrabble words.

Give them a short list of animal types, and have them find all words that have one of the animals as a substring. (So, for example, CrATe would contain cat.) There's nothing special about animal types here.

Find all words that can be made using straight line letters (AEFHIKLMNTVWXYZ)
extropalopakettle
Posted: Tue Feb 19, 2013 3:33 am    Post subject: -10

LordKinbote wrote:
Off the top of my head, I'm thinking the easiest way to find anagrams is to walk through the wordlist, sort the letters in each word alphabetically, and then put them into a dictionary that looks like {alphabetical_word:[word1,word2,etc.], ...} then return all the words that have a list two elements or greater?

I was asked to (and did) solve that problem during a job interview many years ago.
Amb
Posted: Tue Feb 19, 2013 3:27 am    Post subject: -11

Find words that are one letter incorrect of being a palindrome.

eg:
Banana & Estate & Bomb (Drop the B, Drop the S, Drop the M respectively)
Erase (Erase, because 1 off Esase and/or Erare)
Signs (Signs, because 1 off Sigis and/or Sngns)
( - Or better RENDER / REDDER - both are words)
Shah (Add an S to the end to make SHAHS)
LordKinbote
Posted: Tue Feb 19, 2013 2:25 am    Post subject: -12

For the code-curious:

Code:
def find_anagrams():
d = {}
for word in wordset:
sorted_word = "".join(sorted(word))
if sorted_word in d:
d[sorted_word].append(word)
else:
d[sorted_word] = [word]
return d

wordset is a global set (not list) that I load the wordlist file into.
Amb
Posted: Tue Feb 19, 2013 2:13 am    Post subject: -13

I have a wordlist that I loaded into SQL, and I wrote anag routines, word splitters etc - entirely in T-SQL functions.

For anagramming, I sort word letters into order and store those.

PEACH = ACEHP
CHEAP = ACEHP
LordKinbote
Posted: Tue Feb 19, 2013 1:50 am    Post subject: -14

Zag wrote:
Also, it sounds as if this is a pretty beginning class, but if its more than first year, or perhaps just with your best students, you might want to talk a little about algorithms. For instance, finding the words with at least two other anagrams will require a little cleverness in approach, if you want the process to finish in a reasonable amount of time. Testing every word against every other word is not a good idea. You could ask them to brainstorm different approaches that will be more efficient than that.

It is a beginner's course, but we have discussed that there are solutions to problems that work significantly quicker than others. Tomorrow will be the first time in class we will have worked with data of any substantial size though. Part of what I want them to do is *try* inefficient solutions so that I can say "Okay, that will work...but might take a few hours or more RAM than you have."

Off the top of my head, I'm thinking the easiest way to find anagrams is to walk through the wordlist, sort the letters in each word alphabetically, and then put them into a dictionary that looks like {alphabetical_word:[word1,word2,etc.], ...} then return all the words that have a list two elements or greater?

This seems like it should work a hell of a lot better than, say, checking every permutation of a word against the word list.

Edit: Yeah, that worked really really quickly...CATER/CRATE/CARET/REACT/TRACE is the winner, by my wordlist.

Edit: Actually, my current wordlist has no inflections. I found a couple of sixes if I use my wordlist that includes inflections.
Zag
Posted: Tue Feb 19, 2013 1:26 am    Post subject: -15

Also, it sounds as if this is a pretty beginning class, but if its more than first year, or perhaps just with your best students, you might want to talk a little about algorithms. For instance, finding the words with at least two other anagrams will require a little cleverness in approach, if you want the process to finish in a reasonable amount of time. Testing every word against every other word is not a good idea. You could ask them to brainstorm different approaches that will be more efficient than that.
Zag
Posted: Tue Feb 19, 2013 1:21 am    Post subject: -16

Find words that are caesar shifts of each other.

List all the words with Q but no U.

(This is handy for Scrabble players) From all the two-letter words, make a chart like this:

Code:

ABFHLMPT    A    ABDEGHLMNPRSTWXY
A           B    AEIOY
C
AEIO        D    AO
.
.
.

In the first row, the ABFHLMPT are there to show that each of those letters make a two letter word with A following -- i.e. AA, BA, FA, HA, etc. Similarly, the ABDEGHLMNPRSTWXY are all the letters that make a two-letter word if you put A before each of them: AA, AB, AD, AE, AG, etc.

In the next row, we see that there is only one two-letter word that ends with B, and five that start with B. There are no two-letter words with C in either position. etc.

BTW, I'm not positive I have those first 4 rows correct, and it will depend on the word list you use, of course.
LordKinbote
Posted: Tue Feb 19, 2013 1:05 am    Post subject: -17

I teach a high school programming class using the language Python. Today I taught the basics of File I/O (basically by giving them a file of Best Picture winners and years and having them pull that data out and make it easily accessible).

Tomorrow, I want them to practice this new skill, and I thought because I'm a lover of all things puzzl-ey that I would give them a large wordlist and then have them go on a Word Scavenger Hunt to find words that exhibit certain properties that require writing some sort of program. (No Googling allowed).

For example:

Find three words that make smaller words when the odd letters and the even letters are written down seperately (like CALLIOPE = CLIP and ALOE). The NPL calls this an alternade.

Find a word that has two anagrams.

Find a word with three or more z's. (PIZZAZZ fits the bill in the wordlist that I have, as well as RAZZLE-DAZZLE).

Find three words that can become different words by switching the places of two letters. The NPL calls this a metathesis.

Can anyone help me brainstorm some more of these?