Personal computing discussed

Moderators: SecretSquirrel, just brew it!

 
IntelMole
Grand Gerbil Poohbah
Topic Author
Posts: 3505
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub
Contact:

Damn Cryptic Crosswords, and my stupid imagination

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
 
Yahoolian
Grand Gerbil Poohbah
Posts: 3577
Joined: Sun Feb 16, 2003 3:43 pm
Location: MD
Contact:

Wed Jun 23, 2004 10:56 am

but you can't incremement characters in java


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


Outputs c.

Nested loops should do the trick.
 
IntelMole
Grand Gerbil Poohbah
Topic Author
Posts: 3505
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub
Contact:

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
 
fc34
Minister of Gerbil Affairs
Posts: 2816
Joined: Wed May 08, 2002 8:39 am
Location: Somewhere

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
 
IntelMole
Grand Gerbil Poohbah
Topic Author
Posts: 3505
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub
Contact:

Mon Jul 26, 2004 7:58 pm

fc34, as in:

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
 
dalamar70
Gerbil First Class
Posts: 100
Joined: Thu Aug 29, 2002 3:23 pm

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....
 
IntelMole
Grand Gerbil Poohbah
Topic Author
Posts: 3505
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub
Contact:

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
 
dalamar70
Gerbil First Class
Posts: 100
Joined: Thu Aug 29, 2002 3:23 pm

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.
 
IntelMole
Grand Gerbil Poohbah
Topic Author
Posts: 3505
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub
Contact:

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
 
dalamar70
Gerbil First Class
Posts: 100
Joined: Thu Aug 29, 2002 3:23 pm

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:

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.

Who is online

Users browsing this forum: No registered users and 1 guest