Login or Sign Up to become a member!
LessThanDot Site Logo

LessThanDot

A Technical Community for IT Professionals

Less Than Dot is a community of passionate IT professionals and enthusiasts dedicated to sharing technical knowledge, experience, and assistance. Inside you will find reference materials, interesting technical discussions, and expert tips and commentary. Once you register for an account you will have immediate access to the forums and all past articles and commentaries.

LTD Social Sitings

Lessthandot twitter Lessthandot Linkedin Lessthandot facebook Lessthandot rss

Note: Watch for social icons on posts by your favorite authors to follow their postings on these and other social sites.

Highly Rated Users

Forum
No Posts Rated

Top 50
Given
Received

Forum Statistics

Users
Members:
1566
Members Online:
2
Guests Online:
5

Total Post History
Posts:
80459
Topics:
18410

7-Day Post History
New Posts:
27
New Topics:
9
Active Topics:
13

Our newest member
watson45

Other

FAQ
All times are UTC [ DST ]

Google Ads

Puzzle 15: reverse the order of words

Mind Boggling Puzzles, to keep that grey matter in shape...
Forum rules
Always post answers in a "Hidecode" tag, so that others have a chance to answer the question too.
Please wait...

Puzzle 15: reverse the order of words

Postby chrissie1 on Fri Sep 12, 2008 10:01 am

Given an array of characters that form a sentence, give an efficient algorithm to reverse the order of the words (not characters) in it.

Testcases
"Chrissie goes to bed in the morning" = "Morning the in bed to goes chrissie"
"Why is a plant always green, except if it's red" = "Red it's if except, green always plant a is why"
"Plant a plant" = "Plant a plant"

Look at punctuation and capitalization. Extra points if you can determine if it's a palindrome but only for this case. A more difficult palindrome puzzle will follow in the next few weeks.

If you want, you can time it, which is usually a good indication of how good your algorithm is.

Taken and improved from http://halcyon.usc.edu/~kiran/msqs.html#programming.
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: Puzzle 15: reverse the order of words

Postby Remou on Fri Sep 12, 2008 9:28 pm

Oh well. VBA.

Code is hidden, SHOW


Edit: Result
Code is hidden, SHOW
Stop quoting laws to us. We carry swords.
User avatar
Remou
LTD Admin
LTD Admin
LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948
LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948
LTD Gold - Rating: 948
 
Posts: 5293
Joined: Sun Oct 14, 2007 11:26 am
Unrated

Re: Puzzle 15: reverse the order of words

Postby tarwn on Sat Sep 13, 2008 2:10 am

Python and regex goodness. Can't handle parans or brackets, maybe I will add those later when I time it :P

Code is hidden, SHOW

Um, yeah...I'm going to need you to come in on Saturday -- Bill Lumbergh, Office Space
User avatar
tarwn
LTD Admin
LTD Admin
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813
 
Posts: 3660
Joined: Fri Oct 12, 2007 11:10 am
Location: Raleigh, NC, USA
Unrated

Re: Puzzle 15: reverse the order of words

Postby ZmrAbdulla on Sat Sep 13, 2008 7:52 am

I don't know if this is answer but it works
In vb.net
Code is hidden, SHOW


the result was
Code is hidden, SHOW
Zameer Abdulla
User avatar
ZmrAbdulla
LTD Senior Moderator
LTD Senior Moderator
LTD Bronze - Rating: 54LTD Bronze - Rating: 54
 
Posts: 225
Joined: Thu Oct 18, 2007 7:43 am
Location: United Arab Emirates
Unrated

Re: Puzzle 15: reverse the order of words

Postby chrissie1 on Sat Sep 13, 2008 8:15 am

Zameer the result you got are not exactly the same as the testcases. You forgot punctuation and Capitals.
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: Puzzle 15: reverse the order of words

Postby ZmrAbdulla on Sat Sep 13, 2008 9:01 am

Capitalization is possible. But I don't have any idea how to deal with punctuation.
Zameer Abdulla
User avatar
ZmrAbdulla
LTD Senior Moderator
LTD Senior Moderator
LTD Bronze - Rating: 54LTD Bronze - Rating: 54
 
Posts: 225
Joined: Thu Oct 18, 2007 7:43 am
Location: United Arab Emirates
Unrated

Re: Puzzle 15: reverse the order of words

Postby tarwn on Sat Sep 13, 2008 1:26 pm

Slightly newer version that has a function for a list of characters and a second function for raw strings. Both now return the reversed sentence and an indication of whether the sentence is a word palindrome:

Code is hidden, SHOW


And here is the test code for both functions:
Code is hidden, SHOW


And the results:
Code is hidden, SHOW

Um, yeah...I'm going to need you to come in on Saturday -- Bill Lumbergh, Office Space
User avatar
tarwn
LTD Admin
LTD Admin
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813LTD Gold - Rating: 813
LTD Gold - Rating: 813
 
Posts: 3660
Joined: Fri Oct 12, 2007 11:10 am
Location: Raleigh, NC, USA
Unrated

Re: Puzzle 15: reverse the order of words

Postby Remou on Sat Sep 13, 2008 1:41 pm

Thanks for reminding me to show a result (by including a result, that is).
Stop quoting laws to us. We carry swords.
User avatar
Remou
LTD Admin
LTD Admin
LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948
LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948LTD Gold - Rating: 948
LTD Gold - Rating: 948
 
Posts: 5293
Joined: Sun Oct 14, 2007 11:26 am
Unrated

Re: Puzzle 15: reverse the order of words

Postby ca8msm on Mon Sep 15, 2008 9:22 am

Here's a .NET based one. It could have been a one-liner if the .NET reversal method I used returned a value...
Code is hidden, SHOW

Results:
Code is hidden, SHOW
User avatar
ca8msm
LTD Admin
LTD Admin
LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687
LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687
 
Posts: 2492
Joined: Wed Oct 10, 2007 6:49 pm
Location: North East England
Unrated

Re: Puzzle 15: reverse the order of words

Postby chrissie1 on Mon Sep 15, 2008 9:30 am

Close but not close enough. I know what the result will be but could you post them anyway?
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: Puzzle 15: reverse the order of words

Postby ca8msm on Mon Sep 15, 2008 10:09 am

As yes, I see what you mean now (the comma's position).
User avatar
ca8msm
LTD Admin
LTD Admin
LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687
LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687
 
Posts: 2492
Joined: Wed Oct 10, 2007 6:49 pm
Location: North East England
Unrated

Re: Puzzle 15: reverse the order of words

Postby ca8msm on Mon Sep 15, 2008 10:17 am

Here's a modified version:
Code is hidden, SHOW

Results:
Code is hidden, SHOW
User avatar
ca8msm
LTD Admin
LTD Admin
LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687
LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687
 
Posts: 2492
Joined: Wed Oct 10, 2007 6:49 pm
Location: North East England
Unrated

Re: Puzzle 15: reverse the order of words

Postby ZmrAbdulla on Mon Sep 15, 2008 10:50 am

Sorry Mark,
I can't agree with this.. I am sure you can do better.
1) What if the string didn't start with Capital letter?
2) What if there is any other punctuation marks in the string?
3) What if any other word started in capital letter?
Zameer Abdulla
User avatar
ZmrAbdulla
LTD Senior Moderator
LTD Senior Moderator
LTD Bronze - Rating: 54LTD Bronze - Rating: 54
 
Posts: 225
Joined: Thu Oct 18, 2007 7:43 am
Location: United Arab Emirates
Unrated

Re: Puzzle 15: reverse the order of words

Postby chrissie1 on Mon Sep 15, 2008 10:57 am

The code should work for the testcases given. Weather or not it is good code is up to you. Mark's code works for the given testcases so it isa perfectly valid solution.
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: Puzzle 15: reverse the order of words

Postby ZmrAbdulla on Mon Sep 15, 2008 11:17 am

Then it is my mistake I didn't post a valid solution more similar to this earlier.
I was thinking need to check any string.
Zameer Abdulla
User avatar
ZmrAbdulla
LTD Senior Moderator
LTD Senior Moderator
LTD Bronze - Rating: 54LTD Bronze - Rating: 54
 
Posts: 225
Joined: Thu Oct 18, 2007 7:43 am
Location: United Arab Emirates
Unrated

Re: Puzzle 15: reverse the order of words

Postby ca8msm on Mon Sep 15, 2008 12:31 pm

ZmrAbdulla wrote:Sorry Mark,
I can't agree with this.. I am sure you can do better.
1) What if the string didn't start with Capital letter?
2) What if there is any other punctuation marks in the string?
3) What if any other word started in capital letter?


1) I didn't think that mattered. All of the test case results have a starting capital letter as though they were part of a sentence so I assumed all results should have the first letter capitalised.

2) I just used the given test cases, I would have probably used a regular expression to deal with other punctuation characters had there been others.

3) Again I just followed the test cases. If there was a capital in any other word, I simply wouldn't have used the ToLower method in the first declarations.

These puzzles are just about seeing what different methods can be used to achieve the same result. Even if someone posts a solution that doesn't generate the correct results, I find them just as interesting to see what their thought process was when tackling the problem.
User avatar
ca8msm
LTD Admin
LTD Admin
LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687
LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687LTD Silver - Rating: 687
 
Posts: 2492
Joined: Wed Oct 10, 2007 6:49 pm
Location: North East England
Unrated

Re: Puzzle 15: reverse the order of words

Postby shamsm on Wed Sep 24, 2008 11:24 pm

Here is my solution, in java as usual.

Features:
- custom string tokenizer that doesn't use regular expressions
- Handles parenthesis, check the sample output
- Handles cases for not only the first word, but any word in the middle
- checks for palindromes

Code is hidden, SHOW


And the output:

Code is hidden, SHOW
shamsm
Apprentice
Apprentice
LTD Bronze - Rating: 47
 
Posts: 12
Joined: Wed Jul 30, 2008 10:09 am

Re: Puzzle 15: reverse the order of words

Postby Emtucifor on Thu Sep 25, 2008 12:33 am

shamsm,

why is "Except" capitalized in your output?
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA
Unrated

Re: Puzzle 15: reverse the order of words

Postby shamsm on Thu Sep 25, 2008 4:30 pm

Emtucifor wrote:why is "Except" capitalized in your output?


Since the corresponding fourth word in the actual input (Plant) is also capitalized
shamsm
Apprentice
Apprentice
LTD Bronze - Rating: 47
 
Posts: 12
Joined: Wed Jul 30, 2008 10:09 am
Unrated

Re: Puzzle 15: reverse the order of words

Postby Emtucifor on Thu Sep 25, 2008 5:35 pm

Seems an unusual rule, to me, since the only capitalization rule based on position that I'm aware of is the first word. All other words should remain capitalized in the output if they are capitalized in the input. There are problems with recognizing doubly-capitalized words like a proper noun as the first word in the sentence, but otherwise the rules seem clear.

He gave John a piece of his mind.
--> Mind his of piece a John gave he.
not --> Mind his Of piece a john gave he.
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA
Unrated

Re: Puzzle 15: reverse the order of words

Postby shamsm on Fri Sep 26, 2008 4:51 am

ya it is, just wanted to point it out as a feature I have implemented ;)
In this whole rule of reversing words won't help remembering most of the grammar rules :)
shamsm
Apprentice
Apprentice
LTD Bronze - Rating: 47
 
Posts: 12
Joined: Wed Jul 30, 2008 10:09 am

Re: Puzzle 15: reverse the order of words

Postby damber on Wed Oct 01, 2008 5:38 pm

you get my vote, shamsm, for providing extra features free of charge :-)
a smile is worth a thousand kind words, so smile, it's easy! :-)


CODE: $5
WORKING CODE: $500
PROPERLY DESIGNED & WORKING CODE: Priceless
User avatar
damber
LTD Admin
LTD Admin
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
 
Posts: 3134
Joined: Tue Oct 09, 2007 1:48 pm
Location: North Wales, UK
Unrated