Programming Forums > Application Development > C++

andro · Jul 27th, 2006, 4:28 PM

Quote:

Originally Posted by Narue

>That's exactly what I can't have happen.
*sigh* Did you completely miss the rest of my post by latching onto that comment? The only difference between what you were trying to do and what set_intersection does, is set_intersection uses temporary storage (the result container). This is a good thing. Unless your checkCollisions function is very trivial, you'll want to know where the collisions are so that they can be dealt with in a user-friendly way. If you simply return true or false after finding a collision, what are you going to do? Throw an error?

Throw out the candidate.

andro · Jul 27th, 2006, 4:38 PM

I guess I ought to explain this a bit. I'm writing a program that solves the Crypto Quotes (Cryptograms) in the newspaper. Here is how it works:

- Take every word of the cryptogram (CipherWord) and "patternize" it.

hello -> abccd
banana -> abcbcb

- For each CipherWord, iterate through an English language dictionary and find all words whos pattern also matches the CipherWords pattern.

- From each of these possible matches in each CipherWord, a corresponding keymap can be deduced.

- Take the CipherWord with the least pattern matches and create a MasterKeyList. At this point, you are now guaranteed that ONE of these keymaps is correct.

- Moving on to the next CipherWord (from least pattern matches to most), check each key in the MasterKeyList with each candidate keymap in the CipherWord. If there are collisions, the candidate must be thrown out.

- Combine all non-collision MasterKeyList keymaps and CipherWord keymaps, combine the 2 keymaps.

- Update the MasterKeyList to contain the new combined keymaps, removing the previous shorter keymaps.

- Continue until you've used all CipherWords.

- At the end, you will be left with best case scenario 1 possible keymap, and usually worst case scenario you get 2-4, usually from things like [p]ot vs [h]ot where neither p nor h is used elsewhere in the puzzle, so theres no way to be sure.

- Apply the keymaps to the cryptoquote.

Narue · Jul 27th, 2006, 4:46 PM

>Throw out the candidate.
Okay, then you can ignore my suggestion. It would be faster to manually search and break out of the algorithm on the first collision:

(Toggle Plain Text)

bool collisions (
  const keymap& master, const keymap& candidate )
{
  keymap::const_iterator mit = master.begin();

  while ( mit != master.end() ) {
    keymap::const_iterator match
      = candidate.find ( mit->first );

    if ( match != candidate.end() {
      if ( match->second == mit->second )
        return false;
    }

    ++mit;
  }

  return true;
}

andro · Jul 27th, 2006, 5:02 PM

Quote:

Originally Posted by Narue

>Throw out the candidate.
Okay, then you can ignore my suggestion. It would be faster to manually search and break out of the algorithm on the first collision:

(Toggle Plain Text)

bool collisions (
  const keymap& master, const keymap& candidate )
{
  keymap::const_iterator mit = master.begin();

  while ( mit != master.end() ) {
    keymap::const_iterator match
      = candidate.find ( mit->first );

    if ( match != candidate.end() {
      if ( match->second == mit->second )
        return false;
    }

    ++mit;
  }

  return true;
}

Thanks

Jul 27th, 2006, 4:46 PM	#13
Narue Professional Programmer Join Date: Sep 2005 Posts: 419 Rep Power: 4	>Throw out the candidate. Okay, then you can ignore my suggestion. It would be faster to manually search and break out of the algorithm on the first collision: (Toggle Plain Text) bool collisions ( const keymap& master, const keymap& candidate ) { keymap::const_iterator mit = master.begin(); while ( mit != master.end() ) { keymap::const_iterator match = candidate.find ( mit->first ); if ( match != candidate.end() { if ( match->second == mit->second ) return false; } ++mit; } return true; } bool collisions ( const keymap& master, const keymap& candidate ) { keymap::const_iterator mit = master.begin(); while ( mit != master.end() ) { keymap::const_iterator match = candidate.find ( mit->first ); if ( match != candidate.end() { if ( match->second == mit->second ) return false; } ++mit; } return true; } __________________ Even if the voices aren't real, they have some pretty good ideas.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Combining languages	titaniumdecoy	Other Programming Languages	12	Jul 13th, 2006 2:03 PM
Compiling Maverik 6.2 (from C)	megamind5005	C	16	May 3rd, 2006 5:41 PM
libraries	matko	C	1	Jan 22nd, 2006 2:12 PM
Jackpot game	zorin	Visual Basic	3	Jun 10th, 2005 1:19 PM
airport Log program using 3D linked List : problem reading from file	gemini_shooter	C++	0	Mar 2nd, 2005 4:12 PM

Jul 27th, 2006, 4:38 PM	#12
andro Professional Programmer Join Date: Oct 2005 Location: California Posts: 311 Rep Power: 3	I guess I ought to explain this a bit. I'm writing a program that solves the Crypto Quotes (Cryptograms) in the newspaper. Here is how it works: - Take every word of the cryptogram (CipherWord) and "patternize" it. hello -> abccd banana -> abcbcb - For each CipherWord, iterate through an English language dictionary and find all words whos pattern also matches the CipherWords pattern. - From each of these possible matches in each CipherWord, a corresponding keymap can be deduced. - Take the CipherWord with the least pattern matches and create a MasterKeyList. At this point, you are now guaranteed that ONE of these keymaps is correct. - Moving on to the next CipherWord (from least pattern matches to most), check each key in the MasterKeyList with each candidate keymap in the CipherWord. If there are collisions, the candidate must be thrown out. - Combine all non-collision MasterKeyList keymaps and CipherWord keymaps, combine the 2 keymaps. - Update the MasterKeyList to contain the new combined keymaps, removing the previous shorter keymaps. - Continue until you've used all CipherWords. - At the end, you will be left with best case scenario 1 possible keymap, and usually worst case scenario you get 2-4, usually from things like [p]ot vs [h]ot where neither p nor h is used elsewhere in the puzzle, so theres no way to be sure. - Apply the keymaps to the cryptoquote.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

checkCollisions() function