Coding Challenge

[klasbj]

Hi, I have gotten the CodeProject newsletters for several years and used the site, but this it the first time I have posted, but this topic was so fun I just had to! :) I found the task was not clear on one topic, namely which resulting string should be the answer if several are possible? It can happen if the matches at the beginning and end overlap, if my assumption that the patterns you remove can not overlap is correct? Anyway, I solved it with the assumption that what is wanted is the shortest possible resulting string, why else would you trim a string :laugh:

#include <cstdio>
#include <vector>

#include "ahocorasick.h"

using namespace std;
using namespace ac;

// arbitraty length limits
#define MAX_TEXT 1000000
#define MAX_PATTERN 1000000

struct interval {
int begin,end;

interval(int b, int e) : begin(b), end(e) { }

// reverse the interval given the total length is n
interval reverse(int n) const {
    return interval(n - end, n - begin);
}

};

interval trim(int len, vector<interval> & intervals);

int main() {
char * patternbuf;
char ** patterns;
char text[MAX_TEXT];
int npatterns;

scanf("%d", &npatterns); getchar();
patterns = new char\*\[npatterns\];
patternbuf = new char\[npatterns \* MAX\_PATTERN\];
for (int i = 0; i < npatterns; ++i) {
    patterns\[i\] = &patternbuf\[i\*MAX\_PATTERN\];
    gets(patterns\[i\]);  // is dangerous and should not be used!
}
gets(text);

// match the patterns to find all the possible places to trim the string
aho\_corasick matcher(npatterns, patterns);
vector<int> \* matches = matcher.get\_matches(text);

// build a list of intervals of the matches
vector<interval> intervals;
for (int i = 0; i < npatterns; ++i) {
    int len = matcher.get\_pattern\_size(i);
    for (vector<int>::iterator it = matches\[i\].begin();
            it != matches\[i\].end(); ++it)
        intervals.push\_back(interval(\*it, \*it+len));
}

// trim the string as much as possible, i.e. find the shortest interval of
// the original string that can result from trimming
interval result = trim(strlen(text), intervals);

// print the result
text\[result.end\] = '\\0';
printf("\\"%s\\"\\n", &text\[result.begin\]);


// clean up
delete \[\] patternbuf;
delete \[\] patterns;

return 0;

}

[darkDercane]

where i can send my solution?? :P

[Rizean]

I'm sorry but this is not a challenge. If you want a real challenge go to ProjectEuler.com. There you will find over 350 easy to difficult challenges. I have learned a ton from the site and have only completed 45 problems so far. Wish I had more time to work the problems. Regards

[Chris Maunder]

I'm sorry but I think you missed the point of this entire thread. Alternatively you could post your own challenge. I'd love to see everyone else throwing their challenges into the ring.

cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP

[User 7888059]

Hmm, i read here since more than one, year but never posted something, but this sounds not to difficult. euphoria 4.0.x include std/text.e include std/console.e puts(1,trim("dog cat monkey dog horse dog","dogcat",0)&"\n") any_key() this should produce your final output Andreas

[PIEBALDconsult]

OK, this is simpler than what I was concocting yesterday and it's not fully tested, but it works with your sample strings. I started by writing a simple Spell Check Tree class (in C# it's much simpler than it was with C back in college):

namespace PIEBALD.Types
{
public sealed class SpellCheckTree
{
public enum SearchState
{
NotFound = -1
,
Inconclusive = 0
,
Found = 1
}

private sealed class TreeNode : System.Collections.Generic.Dictionary<char,TreeNode> {}

private readonly TreeNode tree ;

private TreeNode current ;

public SpellCheckTree
(
)
{
  this.current = this.tree = new TreeNode() ;

  return ;
}

public void
Reset
(
)
{
  this.current = this.tree ;

  return ;
}

public void
Add
(
  System.Collections.Generic.IEnumerable<char> String
)
{
  TreeNode temp = this.tree ;

  foreach ( char c in String )
  {
    if ( !temp.ContainsKey ( c ) )
    {
      temp \[ c \] = new TreeNode() ;
    }                                        
                                             
    temp = temp \[ c \] ;    
  }

  temp \[ System.Char.MaxValue \] = new TreeNode() ;

  return ;
}

public SearchState
Find
(
  char C
)
{
  SearchState result = SearchState.Inconclusive ;

  if ( !this.current.ContainsKey ( C ) )
  {
    result = SearchState.NotFound ;
  }
  else
  {
    this.current = this.current \[ C \] ;

    if ( this.current.ContainsKey ( System.Char.MaxValue ) )
    {
      result = SearchState.Found ;
    }
  }

  return ( result ) ;
}

}
}

Then I wrote a Trim method to use it:

namespace PIEBALD.Lib
{
using System.Linq ; /* Laziness/expedience */

public enum TrimFrom
{
Left = 1
,
Right = 2
,
Both = 3
}

namespace LibExt.Trim
{
public static partial class LibExt
{
public static string
Trim
(
this string Subject
,
TrimFrom TrimFrom
,
params string[] Strings
)
{
System.Text.StringBuilder result = new System.Text.StringBuilder ( Subject ) ;
in

[PIEBALDconsult]

I read it as, "if you want to trim whitespace, then supply them as a 'string to be removed'".

[IAbstract]

You would be correct. Until you look in the box - the cat is neither dead nor alive. Quantum theory can be crudely demonstrated with this example. Anyway ...back to the topic...

[brian oslick]

Chris Maunder... without having to think too much (and thus stress my feeble brain)

include 'win32a.inc'
format PE console 4.0
entry start
;*********************************************
section '.data' data readable writeable

_s db '%s',13,0

i_string db 'dog cat monkey dog horse dog'
o_string db 21 dup(0)

;*********************************************
section '.text' code readable executable
;*********************************************
start: ;fasm_dogcat.fasm

mov ebx,3
xor ecx,ecx
above:
mov eax,dword[i_string+ebx+ecx*4]
mov dword[o_string+ecx*4],eax
inc ecx
cmp ecx,5
jnz above
mov ax,word[i_string+ebx+ecx*4]
mov word[o_string+ecx*4],ax

cinvoke printf,_s,o_string

; >"C:\_sys\temp\shell.exe"
;$20,'cat monkey dog horse',$20,0
; >Exit code: 0
;*********************************************
invoke ExitProcess,0
;***********************************************
section '.idata' data import readable writeable
library kernel32,'kernel32.dll',\
user32,'user32.dll',\
msvcrt,'msvcrt.dll'
include 'api\kernel32.inc'
include 'api\user32.inc'
import msvcrt,\
printf,'printf'
;***********************************************

brianO

[Chris Maunder]

You get serious Man Points for that. :beer:

cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP

[Lost User]

Here is my kick at the cat … er, dog … er, dog and cat. This c# solution is generic enough to handle any number of search words (when using parameters). Note the use of a space as a search word.

using System;
using System.Text;

namespace ConsoleApplication1 {
class Program {
static void Main( string[] args ) {

     string phrase = "dog cat monkey dog horse dog";
     string\[\] words = { " ", "dog", "cat" };    // Note: added space.
     StringBuilder sb1 = new StringBuilder();  // Leading spaces.
     StringBuilder sb2 = new StringBuilder();  // Trailing spaces.
     bool found;

     // Trim start.
     do {
        found = false;
        foreach ( string w in words ) {
           if ( phrase.StartsWith( w ) ) {
              found = true;
              phrase = phrase.Substring( w.Length );
              if ( string.IsNullOrWhiteSpace( w ) ) sb1.Append( w );
           }
        }
     } while ( phrase.Length > 0 && found );

     // Trim end.
     do {
        found = false;
        foreach ( string w in words ) {
           if ( phrase.EndsWith( w ) ) {
              found = true;
              phrase = phrase.Substring( 0, phrase.Length - w.Length );
              if ( string.IsNullOrWhiteSpace( w ) ) sb2.Append( w );
           }
        }
     } while ( phrase.Length > 0 && found );

     Console.WriteLine( "\[" + sb1.ToString() + phrase + sb2.ToString() + "\]" );
  }

}
}

[PIEBALDconsult]

But then you haven't removed the whitespace as specified by the parameters.

[User 4520523]

The paradox is that the cat can't be alive and dead at the same time. The thought experiment was designed to pick holes in the Coppenhagen interpretation of quantum mechanics. He never believed that an unseen cat could be both dead & alive at the same time.

[Lost User]

Member 4523790 wrote:

The paradox is that the cat can't be alive and dead at the same time.

By no definition (of paradox) is that a paradox. Thats like saying my computer can't be on and off at the same time is a paradox. If I could somehow claim my computer is both on and off then that is a paradox. A paradox is something that holds true yet contradicts. "The only certainty is there is no certainty" is a pardoxial (word?) statement because even if it is true then there exists a certainty, thus making it not true. The paradox is that both truths (the cat is dead and the cat is alive) are true until you open the box.

Computers have been intelligent for a long time now. It just so happens that the program writers are about as effective as a room full of monkeys trying to crank out a copy of Hamlet.

[Lost User]

:confused: As per Chris: "The specs say nothing of trimming whitespace ..." (8:07 4 Jan '12)

[User 4520523]

I'll go by the wikipedia definition of paradox: a paradox is a logical statement or group of statements that lead to a contradiction or a situation which (if true) defies logic or reason it defies logic that the cat can be both alive and dead. If you read http://en.wikipedia.org/wiki/Schrödinger's\_cat (scroll to The thought experiment) you'll see that Schrödinger thought it was a "ridiculous case". Albert Einstein wrote: "Nobody really doubts that the presence or absence of the cat is something independent of the act of observation" Niels Bohr (one of the main scientists associated with the Copenhagen interpretation) "never had in mind the observer-induced collapse of the wave function, so that Schrödinger's Cat did not pose any riddle to him. The cat would be either dead or alive long before the box is opened by a conscious observer.[6] Analysis of an actual experiment found that measurement alone (for example by a Geiger counter) is sufficient to collapse a quantum wave function before there is any conscious observation of the measurement" So basically nobody involved thinks the cat is both alive and dead, I don't know why so many people don't get it. Everything is "an observer", there is no special flag in the universe on humans, cats, geiger counters etc.

[Lost User]

Member 4523790 wrote:

a paradox is a logical statement or group of statements that lead to a contradiction or a situation which (if true) defies logic or reason

Using this definition,

Member 4523790 wrote:

The paradox is that the cat can't be alive and dead at the same time.

is definately not a paradox. That is the 'fact' that it can't be both dead and alive at the same time. NOT the paradox. To quote Wiki:

Wikipedia says:

According to Schrödinger, the Copenhagen interpretation implies that the cat remains both alive and dead (to the universe outside the box) until the box is opened. Schrödinger did not wish to promote the idea of dead-and-alive cats as a serious possibility; quite the reverse, the paradox is a classic reductio ad absurdum.

Again, that is the paradox. Back to what I said earlier "The only certainty is there are no certainties". These are Reductio ad absurdum[^] Wether or not an individual 'believes' the cat is alive and dead at the same time, is irrelevant. The paradox is proof against its logic (thats why it is a paradox). It does not change the pardox or make the actual pardox itself false. Its funny that you say

Member 4523790 wrote:

I don't know why so many people don't get it.

when you clearly also don't get it.

Computers have been intelligent for a long time now. It just so happens that the program writers are about as effective as a room full of monkeys trying to crank out a copy of Hamlet.

[Lost User]

Actually it is dead 'and' alive. That is why it is a paradox. Saying it is either dead 'or' alive is not a paradox (and would not have concluded anything under the thought experiment). That is simply a statement, "It is raining or it is not". Meaningless.

Computers have been intelligent for a long time now. It just so happens that the program writers are about as effective as a room full of monkeys trying to crank out a copy of Hamlet.

[PIEBALDconsult]

Yes, but your parameters { " ", "dog", "cat" } specify removing them, yet you didn't.

[Lost User]

I made a point of noting that "spaces" were receiving special handling. I could have hard-coded (more) "space" logic; adding it to the word list made things "simpler". I thought it was obvious, but assume that the "space" is added to the word list / array at run time; e.g. List words = new List () {"dog", "cat"}; .. words.Add( " " ); etc. It's a "black box"; assume {"dog", "cat"} get passed in; a space is added to simplify the logic. That was the point. And the "spec" did not say that a "space" (or any other special character) might be passed, just "words". We could keep going around that a "complete" implementation would also need to validate the "words"; etc. ... but that was not the point of the challenge. (Granted: my "words" list should have been called "wordsWithASpaceAddedToSimplifyLogic" ... ;P )