Coding Challenge
-
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
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 -
An example is not a specification... the spec says:
Quote:
Given a string of text, trim from each end of the text each all occurrences of a given set of strings
Which says nothing about removing spaces (which Chris has already mentioned in a few replies on the thread), therefore, all spaces are left alone. Examples are guidance, specifications are rules... I followed the rules*. *I do agree that 'technically', once you remove the first occurance of "dog", cat is NOT at the begining of the string, and should actually result in " cat monkey dog horse ". Though in looking at the guidance, since cat is removed, I assumed that spaces should be ignored and left alone. Although if you really wanted to get convoluted, and have the EXACT match of a single leading space, that would fundamentally change the given specification... hence my design choice. Taking an occams razor approach, is it more likely that the spec is wrong and we should have a convoluted solution to have a single leading space? Or more likely that it was a typo and Chris ment to have two leading spaces?
Be The Noise
I read it as, "if you want to trim whitespace, then supply them as a 'string to be removed'".
-
It thought it was both alive and dead until you had a look in the box at which point it became alive or dead. A bit late but still; Erwin Schrödinger has sent us a Christmas present. The kids are going to be delighted or distraught on Christmas Day.
Every man can tell how many goats or sheep he possesses, but not how many friends.
-
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
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.fasmmov 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],axcinvoke 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... 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.fasmmov 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],axcinvoke 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
You get serious Man Points for that. :beer:
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
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() + "\]" ); }}
} -
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() + "\]" ); }}
}But then you haven't removed the whitespace as specified by the parameters.
-
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.
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.
-
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.
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.
-
But then you haven't removed the whitespace as specified by the parameters.
-
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.
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.
-
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.
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.
-
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...
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.
-
:confused: As per Chris: "The specs say nothing of trimming whitespace ..." (8:07 4 Jan '12)
Yes, but your parameters
{ " ", "dog", "cat" }specify removing them, yet you didn't. -
Yes, but your parameters
{ " ", "dog", "cat" }specify removing them, yet you didn't.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 )
-
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 )
But what if the caller does specify
" "or"dog cat"as a word (sequence of characters) to remove? You have to remove what you were asked to remove. Edit: I just realized that mine won't handle{ "dog" , "dog cat" }properly. :sigh: -
But what if the caller does specify
" "or"dog cat"as a word (sequence of characters) to remove? You have to remove what you were asked to remove. Edit: I just realized that mine won't handle{ "dog" , "dog cat" }properly. :sigh:The fact is: we have all done the design based on the "sample data" (and spec) and how we interpreted it. I think it is a leap to go from {"dog", "cat"} to {" ", " dog cat ", " dogca", etc.} though. Anyway, development is supposed to be an iterative process; with feedback from the "user". (And yes, even the order of elements matters if "strings" are made up of one versus 1-n words).
-
The fact is: we have all done the design based on the "sample data" (and spec) and how we interpreted it. I think it is a leap to go from {"dog", "cat"} to {" ", " dog cat ", " dogca", etc.} though. Anyway, development is supposed to be an iterative process; with feedback from the "user". (And yes, even the order of elements matters if "strings" are made up of one versus 1-n words).
Gerry Schmitz wrote:
I think it is a leap
Absolutely not; you need to look at the bigger, more general, picture; never focus narrowly on the provided specifics or you'll find yourself constantly rewriting. "A stitch in time saves nine."
Gerry Schmitz wrote:
feedback from the "user"
Some of that can be predicted, and when you do and deliver a more flexible solution than specified you earn respect. If you deliver an inflexible solution that doesn't show any imagination on your part, you don't. It was clear from the post that the sample output was incorrect (at least with a high probability) in two ways and no coding should have taken place until it was cleared up. "Haste makes waste."
-
Gerry Schmitz wrote:
I think it is a leap
Absolutely not; you need to look at the bigger, more general, picture; never focus narrowly on the provided specifics or you'll find yourself constantly rewriting. "A stitch in time saves nine."
Gerry Schmitz wrote:
feedback from the "user"
Some of that can be predicted, and when you do and deliver a more flexible solution than specified you earn respect. If you deliver an inflexible solution that doesn't show any imagination on your part, you don't. It was clear from the post that the sample output was incorrect (at least with a high probability) in two ways and no coding should have taken place until it was cleared up. "Haste makes waste."
I think we’re confusing "flexibility" with (unneeded) functionality. The idea of handling every type of string … which also equates to more “complexity” and more development time … might be totally contrary to what the user had in mind. I don't have the source(s) handy, but there is something to be said about adding in functionality that was not asked for (before it is asked for, if ever). I’m of the belief that you get “something” in the hands of users as soon as possible in order to keep up their level of interest and start a feedback loop as soon as possible (it's worked so far). The alternative is delivering something that was not asked for because “we knew better” (shades of the waterfall). I’m all for flexibility / extensibility; I do little of any type of “rewriting”. Unasked for functionality is another matter. (And I will argue that my solution is quite “extensible” without necessitating a “rewrite” … and also easier to understand, and therefore to maintain / update).
-
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.
Collin Jasnoch wrote:
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.
The point I was making was that he put the thought experiment up as a strawman argument, it wasn't supposed to be taken seriously.
<blockquote class="FQ"><div class="FQA">Collin Jasnoch wrote:</div>Again, that is the paradox. Back to what I said earlier<BR>"The only certainty
is there are no certainties". These are <A href="http://en.wikipedia.org/wiki/Reductio\_ad\_absurdum">Reductio
ad absurdum</A>[<A title="New Window" href="http://en.wikipedia.org/wiki/Reductio\_ad\_absurdum"
target="_blank">^</A>]<BR> <BR>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.<BR></blockquote>It disproves the proposition. "Reductio ad absurdum (Latin: "reduction to the absurd") is a form of argument in which a proposition is disproven by following its implications logically to an absurd consequence.[1]" I doubt he wished to kickstart the multiple universe theory movement.
Collin Jasnoch wrote:
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.
Back at you.