Damn Cryptic Crosswords, and my stupid imagination

[IntelMole]

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 ). 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? ,
-Mole

[Yahoolian]

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.

[IntelMole]

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 )

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... ,
-Mole

[fc34]

How about using an array of characters?

[IntelMole]

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

I'm still no closer to the recursion logic though...
-Mole

[dalamar70]

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]

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

I'll see what happens

Cheers guys, you all rock as always,
-Mole

[dalamar70]

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]

Ah, now it makes some kind of sense

How do I go about "expanding lst," as you've put it? That's confusing me like hell ,
-Mole

[dalamar70]

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.