Coding Challenge
-
Marc Clifton wrote:
There's probably a regex solution, but that's gross.
Glad to be of service to you ;P
using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;namespace StripWords
{
static class Program
{
static void Main()
{
String input, replace;
input = replace = "dog cat monkey dog horse dog";
String stripThese = "dog cat";
String[] words = stripThese.Split(new Char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
String strRegEx = String.Empty;
foreach (String word in words)
{
strRegEx = strRegEx + String.Format(@"^\s*{0}\s*|\s*{0}\s*$|", word);
}
strRegEx = strRegEx.Trim(new char[] { '|' });
Regex trimRegExp = new Regex(strRegEx);bool replaceNeeded = false; do { if (replaceNeeded = trimRegExp.Match(replace).Length > 0) { replace = trimRegExp.Replace(replace, ""); } } while (replaceNeeded); Console.WriteLine("Trimming \\"{0}\\" from input \\"{1}\\" yields \\"{2}\\"!", stripThese, input, replace); Console.ReadLine(); } }}
Cheers! :)
"With sufficient thrust, pigs fly just fine."
Ross Callon, The Twelve Networking Truths, RFC1925
FAIL! ;) You're not preserving the leading and/or trailing space in the result after removing a token from the beginning or end. But cool none-the-less, and probably solvable, right? Marc
My Blog
An Agile walk on the wild side with Relationship Oriented Programming -
Back in the Days of Yore we had a couple of small coding challenges such as the Lean and Mean comp. I was thinking that there are a ton of small, well defined problems that can be tackled a zillion ways in a zillion languages and that it would be cool to see what you guys can come up with. I'd like to start the ball rolling with the following simple task: Problem: Given a string of text, trim from each end of the text each all occurrences of a given set of strings Sample input: Input string: "dog cat monkey dog horse dog" Strings that need to be trimmed from each end: { "dog", "cat" } Final output should be: " monkey dog horse" Final output should be " cat monkey dog horse " [Edit: My final sample output was incorrect, so to be fair I'll accept either answer] It's up to you whether you worry about case sensitivity. Let's see who can provide the smallest, neatest most elegant, most unique and/or fastest code. For those who feel like jumping on the "No Programming questions" bandwagon, please re-read the lounge guidelines. The point of this is to have fun, not to solve each other's programming issues.
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
Every sofware project starts with making a plan with strict schedules about deliverables and defining the architectural artefacts. We need to set up a scrum meeting about choosing the appropriate platform and team composition. We could do this sometimes next week, please send me your suggestions matching your schedules. Attached is the invoice for the 25% of the estimated project costs.
-
Dang, what are we, a bunch of whiners? It's a PROGRAMMING CHALLENGE! START YOUR CODING ENGINES!!! Do we need detail specs? Hell NO!!! There's probably a regex solution, but that's gross. Here's something I whipped together in about 15 minutes (took a bit of debugging, a few nuances to it) that I hope readable and somewhat reusable:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Stripper
{
public enum StringPoint
{
None,
Start,
End,
}
public static class StringHelpersExtensions
{
public static string RightOf(this String src, string s)
{
string ret = src;
int idx = src.IndexOf(s);
if (idx != -1)
{
ret = src.Substring(s.Length);
}
return ret;
}
public static string LeftOfRightmostOf(this String src, string s)
{
string ret = src;
int idx = src.LastIndexOf(s);
if (idx != -1)
{
ret = src.Substring(0, idx);
}
return ret;
}
public static bool StartsOrEndsWith(this String src, string[] items, out string match, out StringPoint whichEnd)
{
bool ret = false;
whichEnd = StringPoint.None;
match = String.Empty;
foreach (string item in items)
{
if (src.StartsWith(item))
{
match = item;
whichEnd = StringPoint.Start;
ret = true;
break;
}
if (src.EndsWith(item))
{
match = item;
whichEnd = StringPoint.End;
ret = true;
break;
}
}
return ret;
}
}
class Program
{
static void Main(string[] args)
{
string input = "dog cat monkey dog horse dog";
string[] stripOf = { "dog", "cat" };
string desiredOutput = " monkey dog horse ";
string result = Stripper(input, stripOf);
if (result == desiredOutput)
{
Console.WriteLine("Success");
}
else
{
Console.WriteLine("Fail! '" + result + "'");
}
}
static string Stripper(string input, string[] stripOf)
{
string ret = input;
string match;
StringPoint whichEnd;
string test = ret.Trim();
string leftPad = String.Empty;
string rightPad = String.Empty;
while (test.StartsOrEndsWith(stripOf, out match, out whichEnd))
{
switch (whichEnd)
{
case StringPoint.Start:
// The result always preserves the leading space separating the token, so add it back in.
leftPad = " ";
ret = leftPad + test.RightOf(match).Trim() + rightPad;
break;
case StringPoint.End:
// The result always preserves -
Hmmmm, 2 KISS algorithms A two pass algorithm might be: 1.) Tokenize the string using white space characters. 2.) Moving from left to right, push the string into a deque if the string is not in the excluded list. If we encounter a string that is included, all proceeding tags are pushed into the deque. 3.) Then do the same from right to left. A single pass algorithm might be: 1.) Tokenize the string using white space characters. 2.) Push all tags into a pair of string:index 3.) For each pair of string and index, if the string is excluded... if the index value of all other string:index pairs before me are also excluded... My index is the beginning of the string. 4.) For each pair of string and index, if the string is excluded... if the index value of all other string:index pairs after me are also excluded... My index is the end of the string. :) I'm too lazy to write the code. Btw, I think the single pass algorithm could be implemented in a single lambda line of code. Best Wishes, -David Delaune
Now remove "the cat" from the string.
-
Back in the Days of Yore we had a couple of small coding challenges such as the Lean and Mean comp. I was thinking that there are a ton of small, well defined problems that can be tackled a zillion ways in a zillion languages and that it would be cool to see what you guys can come up with. I'd like to start the ball rolling with the following simple task: Problem: Given a string of text, trim from each end of the text each all occurrences of a given set of strings Sample input: Input string: "dog cat monkey dog horse dog" Strings that need to be trimmed from each end: { "dog", "cat" } Final output should be: " monkey dog horse" Final output should be " cat monkey dog horse " [Edit: My final sample output was incorrect, so to be fair I'll accept either answer] It's up to you whether you worry about case sensitivity. Let's see who can provide the smallest, neatest most elegant, most unique and/or fastest code. For those who feel like jumping on the "No Programming questions" bandwagon, please re-read the lounge guidelines. The point of this is to have fun, not to solve each other's programming issues.
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
Here's my stab at a solution in C#: [Edit: Chris updated the guidance, and I changed the method accordingly.]
public static string CPtrimmer(string input, string[] trims, StringComparison compare = StringComparison.InvariantCultureIgnoreCase)
{
String Input = input;foreach (var trimWord in trims) { if (Input.StartsWith(trimWord, compare)) Input = Input.Remove(Input.IndexOf(trimWord, compare), trimWord.Length); if (Input.EndsWith(trimWord, compare)) Input = Input.Remove(Input.LastIndexOf(trimWord, compare), trimWord.Length); } if (Input != input) return CPtrimmer(Input, trims); else return Input;}
[modified] Given the exchange below, I am including the usage of this method as well (console C#):
static void Main(string[] args)
{
String input = "dog cat monkey dog horse dog";
String[] trims = new String[] { "dog", "cat" };String result = CPtrimmer(input, trims); // After CPtrimmer has returned, the result is " cat monkey dog horse "}
Be The Noise
-
Not "either alive and dead"? ;) In any case, the cat is itself an observer, so the waveform is always collapsed to a known state or "alive" or "dead", so it's a silly thought experiment (IMHO).
I am pretty sure the cat is both dead and alive, until viewed by a perceiver. That is the paradox of that thought experiment.
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.
-
Bassam Abdul-Baki wrote:
BTW, I assume those are CP's tab sizes and not spaces. One hamster needs to be shot for such wide tabs.
Yes, I just pasted to code directly without converting tabs to " ". Maybe that's why Chris needs this algorithm! Marc
My Blog
An Agile walk on the wild side with Relationship Oriented Programming -
Being a programmer, I cannot resist a coding challenge. Do not misconstrue this to be a general lifting of my personal CodeProject boycott. Usage:
string text = "dog cat dog doghorse monkey dog fishcat dog cat";
string[] removers = new string[] {"cat", "dog"};
do
{
} while (Challenge(ref text, removers));Method:
//-----------------------------------------------------------------------
private bool Challenge(ref string text, string[] removeThese)
{
bool changed = false;
for (int i = 0; i < removeThese.Length; i++)
{
string target = removeThese[i];
int start = -1;
int end = -1;
do
{
end = (text.StartsWith(target)) ? target.Length : -1;
if (end > -1)
{
text = text.Substring(end);
changed = true;
}
text = text.Trim();
} while (end > -1);
do
{
start = (text.EndsWith(target)) ? text.Length - target.Length : -1;
if (start > -1)
{
text = text.Substring(0, start);
changed = true;
}
text = text.Trim();
} while (start > -1);
}
return changed;
}You can also easily make this a recursive method.
".45 ACP - because shooting twice is just silly" - JSOP, 2010
-----
You can never have too much ammo - unless you're swimming, or on fire. - JSOP, 2010
-----
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass." - Dale Earnhardt, 1997That exile lasted long ... ;)
Panic, Chaos, Destruction. My work here is done. Drink. Get drunk. Fall over - P O'H OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
-
At least my version works. I know it can be done in much fewer lines, but the concept is there.
You should format it though (use the <pre> tags). It is very hard to read like that.
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.
-
Being a programmer, I cannot resist a coding challenge. Do not misconstrue this to be a general lifting of my personal CodeProject boycott. Usage:
string text = "dog cat dog doghorse monkey dog fishcat dog cat";
string[] removers = new string[] {"cat", "dog"};
do
{
} while (Challenge(ref text, removers));Method:
//-----------------------------------------------------------------------
private bool Challenge(ref string text, string[] removeThese)
{
bool changed = false;
for (int i = 0; i < removeThese.Length; i++)
{
string target = removeThese[i];
int start = -1;
int end = -1;
do
{
end = (text.StartsWith(target)) ? target.Length : -1;
if (end > -1)
{
text = text.Substring(end);
changed = true;
}
text = text.Trim();
} while (end > -1);
do
{
start = (text.EndsWith(target)) ? text.Length - target.Length : -1;
if (start > -1)
{
text = text.Substring(0, start);
changed = true;
}
text = text.Trim();
} while (start > -1);
}
return changed;
}You can also easily make this a recursive method.
".45 ACP - because shooting twice is just silly" - JSOP, 2010
-----
You can never have too much ammo - unless you're swimming, or on fire. - JSOP, 2010
-----
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass." - Dale Earnhardt, 1997 -
FAIL! ;) You're not preserving the leading and/or trailing space in the result after removing a token from the beginning or end. But cool none-the-less, and probably solvable, right? Marc
My Blog
An Agile walk on the wild side with Relationship Oriented ProgrammingMarc Clifton wrote:
You're not preserving the leading and/or trailing space in the result after removing a token from the beginning or end.
The removal of the white space along with the word was intentional. Did I miss this requirement somehow that the white space must be preserved? Regards, Manfred
"With sufficient thrust, pigs fly just fine."
Ross Callon, The Twelve Networking Truths, RFC1925
-
Collin Jasnoch wrote:
but this approach is very clean IMO.
But won't work, right? The desired result is " monkey dog horse " Did you notice the leading and trailing spaces? ;) Plus, your result calculation doesn't take into account that the result will have a leading or trailing space in it, just resulting in a failure for the next calculation of beginning and end. Marc
My Blog
An Agile walk on the wild side with Relationship Oriented ProgrammingNice catch:) OK, I can put some trims in. Not so hard to fixy. I placed one at the start and then TrimStart and TrimEnd in the Start/End matchers respectfully (more optimal this way) And I just noticed, there are not any leading and trailing spaces (formatting???). Either way, the trim at the start fixes it if the specs want that. The Trims in the algo are required by initial specs.
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.
-
Dang, what are we, a bunch of whiners? It's a PROGRAMMING CHALLENGE! START YOUR CODING ENGINES!!! Do we need detail specs? Hell NO!!! There's probably a regex solution, but that's gross. Here's something I whipped together in about 15 minutes (took a bit of debugging, a few nuances to it) that I hope readable and somewhat reusable:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Stripper
{
public enum StringPoint
{
None,
Start,
End,
}
public static class StringHelpersExtensions
{
public static string RightOf(this String src, string s)
{
string ret = src;
int idx = src.IndexOf(s);
if (idx != -1)
{
ret = src.Substring(s.Length);
}
return ret;
}
public static string LeftOfRightmostOf(this String src, string s)
{
string ret = src;
int idx = src.LastIndexOf(s);
if (idx != -1)
{
ret = src.Substring(0, idx);
}
return ret;
}
public static bool StartsOrEndsWith(this String src, string[] items, out string match, out StringPoint whichEnd)
{
bool ret = false;
whichEnd = StringPoint.None;
match = String.Empty;
foreach (string item in items)
{
if (src.StartsWith(item))
{
match = item;
whichEnd = StringPoint.Start;
ret = true;
break;
}
if (src.EndsWith(item))
{
match = item;
whichEnd = StringPoint.End;
ret = true;
break;
}
}
return ret;
}
}
class Program
{
static void Main(string[] args)
{
string input = "dog cat monkey dog horse dog";
string[] stripOf = { "dog", "cat" };
string desiredOutput = " monkey dog horse ";
string result = Stripper(input, stripOf);
if (result == desiredOutput)
{
Console.WriteLine("Success");
}
else
{
Console.WriteLine("Fail! '" + result + "'");
}
}
static string Stripper(string input, string[] stripOf)
{
string ret = input;
string match;
StringPoint whichEnd;
string test = ret.Trim();
string leftPad = String.Empty;
string rightPad = String.Empty;
while (test.StartsOrEndsWith(stripOf, out match, out whichEnd))
{
switch (whichEnd)
{
case StringPoint.Start:
// The result always preserves the leading space separating the token, so add it back in.
leftPad = " ";
ret = leftPad + test.RightOf(match).Trim() + rightPad;
break;
case StringPoint.End:
// The result always preservesMarc Clifton wrote:
Do we need detail specs? Hell NO!!!
I was about to invite you into my esteemed LinkIn network, but I'm not sure after reading that. :laugh:
Panic, Chaos, Destruction. My work here is done. Drink. Get drunk. Fall over - P O'H OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
-
Won't work if you have "dog dog text". It will only remove the first "dog"
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
Dim Input As String = "dog dog monkey dog horse cat cat dog"
Dim ToRemove As String() = New String() {"dog", "cat"}For Each Value As String In ToRemove While True If Input.StartsWith(Value) = True Then Input = Input.Substring(Value.Length + 1) ElseIf Input.EndsWith(Value) = True Then Input = Input.Substring(0, Input.LastIndexOf(Value) - 1) Else Exit While End If End While Next MessageBox.Show(Input) End SubLobster Thermidor aux crevettes with a Mornay sauce, served in a Provençale manner with shallots and aubergines, garnished with truffle pate, brandy and a fried egg on top and Spam - Monty Python Spam Sketch
-
I am pretty sure the cat is both dead and alive, until viewed by a perceiver. That is the paradox of that thought experiment.
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.
Collin Jasnoch wrote:
perceiver
Which is defined as what? The cat is inside the box, observing its own state, so no external observer is needed to collapse the waveform.
-
A dead cat knows it's dead? :confused:
:-D An alive cat knows it's alive so the waveform has already collapsed to "alive".
-
Back in the Days of Yore we had a couple of small coding challenges such as the Lean and Mean comp. I was thinking that there are a ton of small, well defined problems that can be tackled a zillion ways in a zillion languages and that it would be cool to see what you guys can come up with. I'd like to start the ball rolling with the following simple task: Problem: Given a string of text, trim from each end of the text each all occurrences of a given set of strings Sample input: Input string: "dog cat monkey dog horse dog" Strings that need to be trimmed from each end: { "dog", "cat" } Final output should be: " monkey dog horse" Final output should be " cat monkey dog horse " [Edit: My final sample output was incorrect, so to be fair I'll accept either answer] It's up to you whether you worry about case sensitivity. Let's see who can provide the smallest, neatest most elegant, most unique and/or fastest code. For those who feel like jumping on the "No Programming questions" bandwagon, please re-read the lounge guidelines. The point of this is to have fun, not to solve each other's programming issues.
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
If spaces aren't counted as special characters the output should be " cat monkey dog horse " because cat isn't at the end after removing dog.
Curvature of the Mind now with 3D
-
No consideration of whitespace is provided.
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
it ain't elegant, but it appears to work:
#include <string>
#include <vector>
#include <algorithm>using namespace std;
bool len (const string& s1, const string& s2)
{
return s1.length() > s2.length();
}string trim_right(const string &source , const string& t = " ")
{
string str = source;
return str.erase( str.find_last_not_of(t) + 1);
}bool findLeft(const char*p, size_t start, vector<string> &srch, size_t & foundLen)
{
foundLen = 0;
for (vector<string>::iterator it=srch.begin();it!=srch.end();it++)
{
if (strncmp(p + start, (*it).c_str(), (*it).length())==0)
{
foundLen = (*it).length();
return true;
}
}
return false;
}size_t findRight(const char*p, size_t start, vector<string> &srch, size_t & foundLen)
{
foundLen = 0;
for (vector<string>::iterator it=srch.begin();it!=srch.end();it++)
{
if (strncmp(p + start - (*it).length(), (*it).c_str(), (*it).length())==0)
{
foundLen = (*it).length();
return true;
}
}
return false;
}string stripper(string inp, vector<string> srch)
{
string ret="";const char *p = inp.c_str();
size_t left = 0;
size_t right = inp.length();
size_t foundLen = 0;// descending len sort. for greedy matching
std::sort(srch.begin(), srch.end(), len);// from left
bool matched=false;
do
{
matched=false;
if (findLeft(p, left, srch, foundLen))
{
matched = true;
left+=foundLen;
while (isspace(*(p + left)) && *(p+left)) left++;
}
} while (*(p+left) && matched);if (left==inp.length()) return ret;
// from right
do
{
matched=false;
if (findRight(p, right, srch, foundLen))
{
matched = true;
right-=foundLen;
while (isspace(*(p+right)) && right>=left) right--;
}
} while (right >= left && matched);ret = inp.substr(left, right - left);
ret = trim_right(ret); //?
return ret;
}int _tmain(int argc, _TCHAR* argv[])
{
vector<string> srch;
srch.push_back("doggie");
srch.push_back("dog");
srch.push_back("cat");stripper("doggiedog cathorse cat", srch);
}
-
Back in the Days of Yore we had a couple of small coding challenges such as the Lean and Mean comp. I was thinking that there are a ton of small, well defined problems that can be tackled a zillion ways in a zillion languages and that it would be cool to see what you guys can come up with. I'd like to start the ball rolling with the following simple task: Problem: Given a string of text, trim from each end of the text each all occurrences of a given set of strings Sample input: Input string: "dog cat monkey dog horse dog" Strings that need to be trimmed from each end: { "dog", "cat" } Final output should be: " monkey dog horse" Final output should be " cat monkey dog horse " [Edit: My final sample output was incorrect, so to be fair I'll accept either answer] It's up to you whether you worry about case sensitivity. Let's see who can provide the smallest, neatest most elegant, most unique and/or fastest code. For those who feel like jumping on the "No Programming questions" bandwagon, please re-read the lounge guidelines. The point of this is to have fun, not to solve each other's programming issues.
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
Can I used delegates? If so, I will delegate this to one of my co-workers. That should do it!
m.bergman
For Bruce Schneier, quanta only have one state : afraid.
To succeed in the world it is not enough to be stupid, you must also be well-mannered. -- Voltaire
Honesty is the best policy, but insanity is a better defense. -- Steve Landesberg
-
Here's my stab at a solution in C#: [Edit: Chris updated the guidance, and I changed the method accordingly.]
public static string CPtrimmer(string input, string[] trims, StringComparison compare = StringComparison.InvariantCultureIgnoreCase)
{
String Input = input;foreach (var trimWord in trims) { if (Input.StartsWith(trimWord, compare)) Input = Input.Remove(Input.IndexOf(trimWord, compare), trimWord.Length); if (Input.EndsWith(trimWord, compare)) Input = Input.Remove(Input.LastIndexOf(trimWord, compare), trimWord.Length); } if (Input != input) return CPtrimmer(Input, trims); else return Input;}
[modified] Given the exchange below, I am including the usage of this method as well (console C#):
static void Main(string[] args)
{
String input = "dog cat monkey dog horse dog";
String[] trims = new String[] { "dog", "cat" };String result = CPtrimmer(input, trims); // After CPtrimmer has returned, the result is " cat monkey dog horse "}
Be The Noise
This will not remove all of the strings. You will only remove the first instances of them if the string starts with it or ends with it. If your collection is {"dog", "cat"} But your string is "cat dog monkey" you will remove cat but not dog.
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.