Damn Cryptic Crosswords, and my stupid imagination

From Visual Basic to GNU C, this is the place to talk programming.

Moderators: SecretSquirrel, just brew it!

Damn Cryptic Crosswords, and my stupid imagination

Postposted on Wed Jun 23, 2004 9:35 am

At Bath University last year, we used to get crosswords with every issue of the uni newspaper. The clues were usually pretty cryptic ("sport in rotten nissan" = tennis), and usually pretty vague. Half the time we'd fit a word to the clues rather than the other way round.

I got to thinking, what if the word was say, concentrate, and I could just give DOS a command line like "MakeWords con ent ate" and it would come up with every combination, legal or not.

I could then go through it with Word or something, and come up with a list of possible words.

Damn me and my stupid gob.

I figured this was a recursive sort of problem, since you're doing the same task each time, just with bigger or smaller segments of the word. I'd do it in java, but you can't incremement characters in java (Please read "Why oh why do Sun do this to me?" for more information :-D). So this looks to be something to do with C, or possible C++, but I have no knowledge of the latter and only a little of the former.

I've been trying to figure out the recursion (since I figured that would be the fastest way), and I'm more than a little stuck, to say the least.

Any ideas? :lol:,
-Mole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Wed Jun 23, 2004 10:56 am

but you can't incremement characters in java


Code: Select all
public static void main(String[] args)
  {
    char c = 'b';
    System.out.println( ++c );
  }


Outputs c.

Nested loops should do the trick.
Yahoolian
Grand Gerbil Poohbah
 
Posts: 3576
Joined: Sun Feb 16, 2003 3:43 pm
Location: MD

Postposted on Fri Jun 25, 2004 7:33 pm

That would be my solution Yahoolian, but that would require you to know how many input arguments there are for the whole thing, if I've understood what you're saying correctly (and it's 1:40am, so there's no guarentee of that :lol:)

But I was kinda hoping this would work for any number of word segments...

Which is where the recursion comes in.

Which is where it gets tricky in my imagination, without some obscene number of variables being used... :-D,
-Mole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Mon Jul 26, 2004 7:43 pm

How about using an array of characters?
Windows XP - The 64-bit wannabe with a 32-bit graphics interface for 16-bit extensions to a 8-bit patch on a 4-bit operating system designed to run on a 2-bit processor by a company that can't stand 1-bit of competition
fc34
Minister of Gerbil Affairs
 
Posts: 2816
Joined: Wed May 08, 2002 8:39 am
Location: Somewhere

Postposted on Mon Jul 26, 2004 7:58 pm

fc34, as in:

Code: Select all
charArray[0] = 'a';
charArray[1] = 'b';
...
...
charArray[25] = 'z';


???

That would work... it's also a kludge, but it's an interesting workaround to java's general Sun-ness :-D

I'm still no closer to the recursion logic though...
-Mole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Sun Aug 01, 2004 7:11 pm

I don't think you need recursion for this, although of course it should be possible. What you're trying to do is take a string like "con ent ate" and return a LIST of all possible strings from "conAentAate" to "conZentZate".

You can break your input up into three substrings: "con", "ent", "ate". The list of all possibilities (call it "lst") can be initialized with "con". For each additional substring,

1. expand lst by a factor of 26, by adding 'A'-'Z' onto each string in lst. For example, [ "con" ] becomes [ "conA", "conB", ..., "conZ" ]
2. append the next substring onto each element of lst. So your list becomes [ "conAent", "conBent", ..., "conZent" ]

Hope that makes some sense....
dalamar70
Gerbil First Class
 
Posts: 100
Joined: Thu Aug 29, 2002 3:23 pm

Postposted on Sun Aug 01, 2004 7:53 pm

Yeah, that's the kinda thing I was thinking of doing. Only I don't know how you'd go from step two onwards...

Anyway to make the number of dimensions in an array dynamic? I can't think of a way, other than that, to keep it all in some sort of order, without resorting to passing strings in some recursive fashion...

Maybe a combination of recursion and dalamar's method :-D

I'll see what happens :-D

Cheers guys, you all rock as always,
-Mole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Sun Aug 01, 2004 11:44 pm

You shouldn't need to do anything special after step 2. To continue that example, we go back to step 1, but now lst has [ "conAent", "conBent", ..., "conZent" ].

1. expand lst by a factor of 26, by adding 'A'-'Z' onto each string in lst. This gives [ "conAentA", "conAentB", ..., "conAentZ", "conBentA", "conBentB", ..., "conBentZ", ..., "conZentA", "conZentB", ..., "conZentZ" ]

2. append the next substring onto each element of lst. The next substring is "ate", so you end up with [ "conAentAate", "conAentBate", ..., "conAentZate", "conBentAate", "conBentBate", ..., "conBentZate", ..., "conZentAate", "conZentBate", ..., "conZentZate" ]

I am assuming the use of some kind of list structure, rather than only using arrays.
dalamar70
Gerbil First Class
 
Posts: 100
Joined: Thu Aug 29, 2002 3:23 pm

Postposted on Mon Aug 02, 2004 10:38 am

Ah, now it makes some kind of sense :-D

How do I go about "expanding lst," as you've put it? That's confusing me like hell :-D,
-Mole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Mon Aug 02, 2004 12:24 pm

Hmm, if there was a queue structure, then you could pull strings out of the queue one by one, and replace them with 26 new strings with 'a'-'z' appended. Something like:

Code: Select all
void expand(Queue q)
{
  int size = q.size();
  for (int i = 0; i < size; i++) {
    String str = (String) q.dequeue();
    for (char c = 'a'; c <= 'z'; c++) {
      q.enqueue(str + String.valueOf(c));    // append new letter onto old string
    }
  }
}


I guess Java doesn't have a queue structure. :( But you can probably still do something similar with lists.
dalamar70
Gerbil First Class
 
Posts: 100
Joined: Thu Aug 29, 2002 3:23 pm


Return to Developer's Den

Who is online

Users browsing this forum: No registered users and 3 guests