Coding Challenge

[CPallini]

The function:

-- function
require("lpeg")
d = lpeg.P"dog" + lpeg.P"cat"
g = d^0 * lpeg.C((1-d)^1 * (d^0 * (1-d))^0) * d^0
function trm(s) return lpeg.match(g, s) or "" end

the test:

-- test
t = {
"dog cat monkey dog horse dog",
"dogcatmonkeycatcatcat",
"dog",
"doghorsedogdog dog",
"monkey",
"catcatdogcathorse sheep dog cat pig horse sheepcatmonkeydogcat"
}

for i,v in ipairs(t) do
print ("'" .. v .. "'" .. " -> " .. "'" .. trm(v) .. "'")
end

the output:

'dog cat monkey dog horse dog' -> ' cat monkey dog horse '
'dogcatmonkeycatcatcat' -> 'monkey'
'dog' -> ''
'doghorsedogdog dog' -> 'horsedogdog '
'monkey' -> 'monkey'
'catcatdogcathorse sheep dog cat pig horse sheepcatmonkeydogcat' -> 'horse sheep dog cat pig horse sheepcatmonkey'

If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]

[Lost User]

I bet that's the last programming challenge you try!

MVVM# - See how I did MVVM my way ___________________________________________ Man, you're a god. - walterhevedeich 26/05/2011 .\\axxx (That's an 'M')

[Lost User]

Chris Maunder wrote:

Given a string of text, trim from each end of the text each all occurrences of a given set of strings

Assuming (from your sample) you only want to remove a single item from each end (hence the leading 'cat' remains), then the below would seem to provide the requisite output and I feel earn bonus points for its simplicity, elegance and the fact that it's the first opportunity I've had to do c# for nearly a year!

private string CodingChallenge(string source, string[] removals)
{
string delimiter = " ";
bool leftDone = false;
bool rightDone = false;

        foreach (string s in removals)
        {
            if (!leftDone && source.Substring(0, s.Length) == s && source.Substring(s.Length, 1) == delimiter)
            {
                source = source.Substring(s.Length);
                leftDone = true;
            }

            if (!rightDone && source.Substring(source.Length - s.Length) == s && source.Substring(source.Length - s.Length - 1, 1) == delimiter)
            {
                source = source.Substring(0, source.Length - s.Length);
                rightDone = true;
            }
        }

        return source;
    }

MVVM# - See how I did MVVM my way ___________________________________________ Man, you're a god. - walterhevedeich 26/05/2011 .\\axxx (That's an 'M')

[ErnestoNet]

Need to check this with other strings, debug some more, improve comments and string handling in main(), etc. But still....here it goes:

#include "stdafx.h"

const wchar_t whitechar = ' ';
const bool IncludeWhiteSpace = true;
const wchar_t* wordstoremove[] = {L"dog", L"cat"};

const wchar_t* strtoparse = L"dog cat monkey dog horse dog"; //Len 28
int ltoparse;
const int numwords = 2;

int wordlen[numwords];

//Positions in the original string to rip
int pos_orig_from;
int pos_orig_to;

//Len of left and right copies
int left_len;
int right_len;

//Gets hoy many bytes per char
void ProcessLeft(wchar_t* strresult)
{
bool bContinue = true;

pos\_orig\_from = left\_len = 0;

while (bContinue)
{
	//Check for whitespaces. If there are, copy them
	if (strtoparse\[pos\_orig\_from\] == whitechar)
	{
		pos\_orig\_from ++;
		if (IncludeWhiteSpace)
		{
			strresult\[left\_len\] = whitechar;
			left\_len ++;
		}
	}
	else
	{
		bContinue = false;
		for (int i = 0; i < numwords; i++)
		{
			//Compare strings
			wchar\_t\* strcompare = (wchar\_t\*)strtoparse + pos\_orig\_from;
			if (wcsncmp(strcompare, wordstoremove\[i\], wordlen\[i\]) == 0)
			{
				pos\_orig\_from += wordlen\[i\];
				bContinue = true;
				break;
			}
		}
	}
}

}
void ProcessRight(wchar_t* strresult)
{
bool bContinue = true;

pos\_orig\_to = right\_len = ltoparse - 1;

while (bContinue)
{
	//Check for whitespaces. If there are, copy them
	if (strtoparse\[pos\_orig\_to\] == whitechar && IncludeWhiteSpace)
	{
		pos\_orig\_to -= 1;
		if (IncludeWhiteSpace)
		{
			strresult\[right\_len\] = whitechar;
			right\_len -= 1;
		}
	}
	else
	{
		bContinue = false;
		for (int i = 0; i < numwords; i++)
		{
			//Compare strings
			//To check right, start from end and substract string to compare len
			wchar\_t\* strcompare = (wchar\_t\*)strtoparse + pos\_orig\_to - wordlen\[i\] + 1;
			if (wcsncmp(strcompare, wordstoremove\[i\], wordlen\[i\]) == 0)
			{
				pos\_orig\_to -= wordlen\[i\];
				bContinue = true;
				break;
			}
		}
	}
}

}

int _tmain(int argc, _TCHAR* argv[])
{

//Load len of words to avoid rechecking
for (int i=0; i

[Pete OHanlon]

Your former client base is showing mate - calling a method Stripper.

Forgive your enemies - it messes with their heads

"Mind bleach! Send me mind bleach!" - Nagy Vilmos

My blog | My articles | MoXAML PowerToys | Mole 2010 - debugging made easier - my favourite utility

[AnthonyN1974]

I was fed up, so here it is in c#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CodeChallenge
{
class Program
{
private static List<string> wordsToRemove = new List<string>() { "dog", "cat" };

static void Main(string\[\] args)
{
  string text = "dog cat monkey dog horse dog";

  string\[\] words = text.Split(' ');
  string\[\] output;
  int start = 0;
  int end = 0;

  // test the start
  if (wordsToRemove.Contains(words\[0\]) && words.Length > 0)
    start = 1;

  // test the end
  if (wordsToRemove.Contains(words\[words.Length - 1\]) && words.Length != start)
    end = (words.Length - 1) - start;
  else
    end = words.Length - start;

  //build
  output = new string\[end\];
  Array.Copy(words, start, output, 0, end);

  //output
  Console.WriteLine(string.Join(" ",output));
}

}
}

[mrchief_2000]

Probably not the most efficient, but in C#, this works:

using System.Text.RegularExpressions;

var source = "dog cat dog horses monkeys dog";
var stringsToTrim = new[] { "dog", "cat" };
var trimmedString = Regex.Replace(source, string.Format("^({0})|({0})$", string.Join("|", stringsToTrim )), "");
Console.WriteLine(trimmedString);

Live demo: http://rextester.com/GTLWO64640[^] Making above shorter:

using System.Text.RegularExpressions;

Console.WriteLine(Regex.Replace("dog cat dog horses monkeys dog", string.Format("^({0})|({0})$", string.Join("|", "dog", "cat")), ""));

[Clumpco]

Here's a solution in APL V←'dog cat monkey dog horse dog' Q←'dog' V←(((V≠Q)⍳1)-⎕IO)↓V V←(⎕IO-(Q≠⌽V)⍳1)↓V Q←'cat' V←(((V≠Q)⍳1)-⎕IO)↓V V←(⎕IO-(Q≠⌽V)⍳1)↓V No doubt a true APL programmer could do it in one line.

[Marc Clifton]

Chris Maunder wrote:

result = Regex.Replace

That's sweet. And amazingly simple. Marc

My Blog
An Agile walk on the wild side with Relationship Oriented Programming

[Marc Clifton]

Pete O'Hanlon wrote:

Your former client base is showing mate - calling a method Stripper.

I am scarred for life! ;P Marc

My Blog
An Agile walk on the wild side with Relationship Oriented Programming

[DariusLegion]

What the hell is the matter with you guys...? :sigh:

[jsc42]

5th Jan: But you said there was nothing in the spec about whitespace, so only removing the first dog is permissible. FWIW: Here is my solution in JavaScript (not the fastest, but still quite short a) Only removing the first dog (if there are multiple dogs)

alert(/^(dog|cat)*(.*?)(dog|cat)*$/.exec("dog cat monkey dog horse dog")[2])

b) Allowing removal of packs of dogs and cats optionally separated by whitespace chars:

alert(/^(\s*(dog|cat))*(.*?)((dog|cat)\s*)*$/.exec("dog cat monkey dog horse dog")[3])

6th Jan: Modified Clarifications in other responses suggest that whitespace is to be preserved and is not significant when looking for leading / trailing texts and that a general solution is required rather than looking only for dogs and cats bracketing "dog cat monkey dog horse dog". So, today's JavaScript version is ...

function strim(str, texts)
{
return str.replace(
new RegExp(
'^((\\s*)(' + // $2 = leading whitespace
texts.join('|') +
'))*(.*?)((' + // $4 = middle portion
texts.join('|') +
')(\\s*)?)*$', // $7 = trailing whitespace
'ig'
),
'$2$4$7'
);
}

alert(strim('dog cat monkey dog horse dog', [ 'dog', 'cat' ]));
alert(strim('dog dog text', [ 'dog', 'cat' ]));

To see the spaces, change the alerts to

alert(strim('dog cat monkey dog horse dog', [ 'dog', 'cat' ]).replace(/ /g, '~')); // ~~monkey~dog~horse~
alert(strim('dog dog text', [ 'dog', 'cat' ]).replace(/ /g, '~')); // ~~text

Note: This will not work if the texts for testing at the start and end include any special RegExp chars, e.g.

. * + ? {

or }.

[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...