Coding Challenge
-
How should whitespace at the ends of the input string be treated - does " cat dog " match or only "cat dog"?
The challenge is to remove the strings that are provided. Nothing is said about removing (or, indeed, caring about, whitespace)
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
-
Randor wrote:
Tokenize the string using white space characters.
is that a valid assumption? dogcathorsefoodcat
-
// Well, this is my piece (C#): static void main(string[] args) { string Input = "doc cat monkey dog horse dog"; List listDeleteStart = new List(); List ListDeleteEnd = new List (); //Output = " monkey dog horse " string[] toTrim = new string[] {"dog", "cat"}; string[] InputStrip = Input.Split(new char[] {' '}); int iCounter = 0; //Going forwards foreach(string strSingle in InputString) { if(toTrim.Contains(strSingle)) ListDeleteStart.Add(iCounter); else break; iCounter++; } //Going backwards InputString = InputString.Reverse().ToArray(); iCounter = InputString.Length-1; foreach(string strSingleRev in InputString) { if(toTrim.Contains(strSingleRev)) ListDeleteStart.Add(iCounter); else break; iCounter--; } //Putting it back again for analysis InputString = InputString.Reverse().ToArray(); string Output = ""; iCounter = 0; foreach (string strResult in InputString) { if(!listDeleteStart.Contains(iCounter) && !listDeletedEnd.Contains(iCounter)) Output+= " " + strResult + " "; iCounter++; } Console.WriteLine(Output); Console.ReadKey(); }
-
Just out of fun as this is fun I created this in VB.NET
Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
Dim Input As String = "dog cat monkey dog horse dog"
Dim ToRemove As String() = New String() {"dog", "cat"}
Dim Start As Integer = 0
Dim EndPointer As Integer = 0For Each Value As String In ToRemove If Start < Input.IndexOf(Value) Then Start = Input.IndexOf(Value) + Value.Length If EndPointer < Input.LastIndexOf(Value) Then EndPointer = Input.LastIndexOf(Value) Next MessageBox.Show(Input.Substring(Start, (EndPointer - Start))) 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
-
Randor wrote:
I think the single pass algorithm could be implemented in a single lambda line of code.
The Not-So-KISS solution.
-
can we assume the input string is going to be tokenizable on ' ' ? or, should we expect things like "dogcatcotblahfoodog"
No consideration of whitespace is provided.
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
-
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
No whitespace treatment is specified in the spec so you can't assume tokenisation is possible
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
-
No whitespace treatment is specified in the spec so you can't assume tokenisation is possible
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
-
Just out of fun as this is fun I created this in VB.NET
Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
Dim Input As String = "dog cat monkey dog horse dog"
Dim ToRemove As String() = New String() {"dog", "cat"}
Dim Start As Integer = 0
Dim EndPointer As Integer = 0For Each Value As String In ToRemove If Start < Input.IndexOf(Value) Then Start = Input.IndexOf(Value) + Value.Length If EndPointer < Input.LastIndexOf(Value) Then EndPointer = Input.LastIndexOf(Value) Next MessageBox.Show(Input.Substring(Start, (EndPointer - Start))) 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
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
-
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
Too easy.
While DogsAndCatsAreStillInTheLine
LineEnd = "left"
GetRidOfCatsAndDogs(LineEnd)
LineEnd = "right"
GetRidOfCatsAndDogs(LineEnd)
WendGetRidOfCatsAndDogs {
OpenCanOfDogFood(ThisEnd)
OpenCanOfCatFood(ThisEnd)
}It's so simple that it's not even worth optimising it or using recursion. For future updates, though, it would be a good idea to use a set for the animals to remove, so that different ones could be included, another for the line ends (so that multiple lines could be serviced), and a third for the food types -- although getting bamboo shoots for pandas, eucalyptus leaves for koalas, and starlets for great whites might cause difficulties in implementation.
I wanna be a eunuchs developer! Pass me a bread knife!
-
I have discovered a truly marvellous solution of this, which the margin of this website is too narrow to contain.
Ideological Purity is no substitute for being able to stick your thumb down a pipe to stop the water
Thank you, Fermat.
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
-
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
My approach is to use substring to grab the current end and starting strings. Substring is also used to update the result. I am sure there are some faster ways, but this approach is very clean IMO.
public string Parse(string input, List remove)
{
string result = input.Trim();
bool startRemoved;
bool endRemoved;do { startRemoved = false; endRemoved = false; foreach (var match in remove) { //Determine if the remove string is fitable with in the remaining output bool inRange = result.Length >= match.Length; //Capture the beginning and ending characters string beginning = result.Substring(0, match.Length); string end = result.Substring(result.Length - match.Length, match.Length); if (inRange && beginning.Equals(match)) { //Update the result with the matched section removed result = result.Substring(match.Length, result.Length - match.Length).TrimStart(); startRemoved = true; } if (inRange && end.Equals(match)) { //Update the result with the matched section removed result = result.Substring(0, result.Length - match.Length).TrimEnd(); endRemoved = true; } } } while (startRemoved || endRemoved); return result;}
[Edit] Added a do while. The do while shuts down if nothing is removed. If anything is removed it must go back and check the removal collection. Optimization could be to track which is removed to then check up to that point. E.g. "dog" "cat" and "monkey" are to be removed (and collection is in that order). If "cat" is removed (start or end), then "monkey" will be checked on active foreach. "dog" and "cat" are the only ones that need be checked on the next do while iteration (unless one of them removes another character set) [Edit] Added Trimmers.
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.
-
No to be pedantic about things, bit if you're tokenizing based on "dog" and "cat", your final answer should be " monkey dog horse " (begins with 2 spaces) or "monkey dog horse " (begins with no space). Otherwise, the requirement on what to do with spaces is incomplete. :)
Who said anything about tokenising?
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
-
Too easy.
While DogsAndCatsAreStillInTheLine
LineEnd = "left"
GetRidOfCatsAndDogs(LineEnd)
LineEnd = "right"
GetRidOfCatsAndDogs(LineEnd)
WendGetRidOfCatsAndDogs {
OpenCanOfDogFood(ThisEnd)
OpenCanOfCatFood(ThisEnd)
}It's so simple that it's not even worth optimising it or using recursion. For future updates, though, it would be a good idea to use a set for the animals to remove, so that different ones could be included, another for the line ends (so that multiple lines could be serviced), and a third for the food types -- although getting bamboo shoots for pandas, eucalyptus leaves for koalas, and starlets for great whites might cause difficulties in implementation.
I wanna be a eunuchs developer! Pass me a bread knife!
For Dalek Dave's benefit, I dub this the Most Unique Solution.
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
-
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
No substrings [except for the end] or tokenizing in Java:
public static String trimStrings(String string, String\[\] trimmings) { if (trimmings == null || trimmings.length == 0) { return string.trim(); } int left = 0; int right = string.length()-1; boolean trimmed; do { while (left < right && string.charAt(left) == ' ') { left++; } while (left < right && string.charAt(right) == ' ') { right--; } trimmed = false; for (int trim = 0; trim < trimmings.length; trim++) { if (string.indexOf(trimmings\[trim\], left) == left) { left += trimmings\[trim\].length(); trimmed = true; } else if (string.lastIndexOf(trimmings\[trim\], right) == (right - trimmings\[trim\].length() + 1)) { right -= trimmings\[trim\].length(); trimmed = true; } } } while (trimmed); return string.substring(left, right+1); }
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
-
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
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 -
Who said anything about tokenising?
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
-
Failed: 1. No formatting 2. Language Dependent 3. Too verbose
Software Kinetics Wear a hard hat it's under construction
Metro RSSNorm .net wrote:
2. Language Dependent
Nothing stated you could not use a specific language. In fact part of the point it seemed was it can be done so many different ways with different languages...
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.
-
The challenge is to remove the strings that are provided. Nothing is said about removing (or, indeed, caring about, whitespace)
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
In that case, shouldn't "cat dog monkey..." end up as " monkey..." with two leading spaces? (It might just be the HTML rendering changing two to one in your OP.)
-
Norm .net wrote:
2. Language Dependent
Nothing stated you could not use a specific language. In fact part of the point it seemed was it can be done so many different ways with different languages...
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.
