Coding Challenge

[Chris Maunder]

Quote:

There's probably a regex solution

result = Regex.Replace("dog cat monkey dog horse dog", "^(dog|cat)*(.*?)((dog|cat)*)$", "$2",
RegexOptions.IgnoreCase | RegexOptions.SingleLine);

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

[Luc Pattyn]

Assuming strings contain chars below Unicode 32000 only, and ignoring white space details:

string[] drops=new string[]{"cat","dog"};
string s="dog cat monkey dog horse dog";
string rep=" ";
char c=(char)32000;
foreach(string drop in drops) {s=s.Replace(drop,c.ToString()); rep+=c; c++;}
s=s.Trim(rep.ToCharArray());
c=(char)32000;
foreach(string drop in drops) {s=s.Replace(c.ToString(),drop); c++;}
log(s);

:zzz:

Luc Pattyn [My Articles] Nil Volentibus Arduum

[Chris Maunder]

:thumbsup: Neat, but lots and lots of new objects created.

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

[Karl Sanford]

Chris updated the guidance, and I have changed my solution accordingly.

Be The Noise

[BillWoodruff]

private string inS = "dog cat monkey dog horse dog";

private List<string> rmS = new List<string> {"dog", "cat"};

private string finalString = "";

private string resultString = " ";

private string removeVarious(string iStr, List<string> iListStr)
{
for (int i = 0; i < iListStr.Count; i++)
{
string str = iListStr[i];

    if (iStr.StartsWith(str))
    {
        iStr = iStr.Remove(0, str.Length + 1);
        finalString = iStr;
    }

    if (iStr.EndsWith(str))
    {
        iStr = iStr.Remove(iStr.Length - str.Length - 1, str.Length + 1);
        finalString = iStr;
    }

    if (iListStr.Count > 0)
    {
        iListStr.RemoveAt(0);
        // recursion here
        removeVarious(iStr, iListStr);
    }
    else
    {
        break;
    }
}

return resultString.Insert(1, finalString);

}

Note: this was written before Chris changed the accepted output to include the word "cat" at the beginning. Meow. best, Bill

"It is the mark of an educated mind to be able to entertain a thought without accepting it." Aristotle

[Slacker007]

my $trimWord = "dog";
my $string = "dog cat monkey dog horse dog";

$string =~ s/^($trimWord)+|($trimWord)+$//g;

print $string;

Just along for the ride. "the meat from that butcher is just the dogs danglies, absolutely amazing cuts of beef." - DaveAuld (2011)
"No, that is just the earthly manifestation of the Great God Retardon." - Nagy Vilmos (2011) "It is the celestial scrotum of good luck!" - Nagy Vilmos (2011)

[Slacker007]

You shat your eyes or your eyes are bleeding? :laugh: :-D :thumbsup:

Just along for the ride. "the meat from that butcher is just the dogs danglies, absolutely amazing cuts of beef." - DaveAuld (2011)
"No, that is just the earthly manifestation of the Great God Retardon." - Nagy Vilmos (2011) "It is the celestial scrotum of good luck!" - Nagy Vilmos (2011)

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

}