Puzzle 15: reverse the order of words

[chrissie1]

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.

[Remou]

Oh well. VBA.

vbLine number Off | Show | Select all

1. Sub Puzzle15()
2. Dim TestCases(2, 1) As String
3.  
4. TestCases(0, 0) = "Chrissie goes to bed in the morning": TestCases(0, 1) = "Morning the in bed to goes chrissie"
5. TestCases(1, 0) = "Why is a plant always green, except if it's red": TestCases(1, 1) = "Red it's if except, green always plant a is why"
6. TestCases(2, 0) = "Plant a plant": TestCases(2, 1) = "Plant a plant"
7.  
8. For i = 0 To UBound(TestCases)
9.     s = split(TestCases(i, 0), " ")
10.     sr = ""
11.    
12.     sj = UBound(s)
13.     sr = sr & " " & StrConv(Replace(s(sj), ",", ""), vbProperCase)
14.    
15.    
16.     For j = sj - 1 To 1 Step -1
17.         sr = sr & " " & LCase(Replace(s(j), ",", ""))
18.    
19.         If Right(s(j - 1), 1) = "," Then
20.             sr = sr & ","
21.         End If
22.     Next
23.    
24.     sr = Trim(sr & " " & LCase(Replace(s(0), ",", "")))
25.  
26.     Debug.Print sr
27.     Debug.Print " Matches? "; sr = TestCases(i, 1)
28.     Debug.Print " Palindrome? "; Palindrome(sr)
29.     Debug.Print " Palindrome of words? "; PalindromeOfWords(sr)
30. Next
31. End Sub
32.  
33. Function Palindrome(ByVal s As String) As Boolean
34.     Set objRegEx = CreateObject("VBScript.RegExp")
35.     objRegEx.IgnoreCase = True
36.     objRegEx.Global = True
37.    
38.     Palindrome = False
39.    
40.     objRegEx.Pattern = "[^a-z0-9]"
41.     s = objRegEx.Replace(s, "")
42.    
43.     If s = StrReverse(s) Then Palindrome = True
44. End Function
45.  
46. Function PalindromeOfWords(ByVal s As Variant) As Boolean
47.     Set objRegEx = CreateObject("VBScript.RegExp")
48.     objRegEx.IgnoreCase = True
49.     objRegEx.Global = True
50.    
51.     PalindromeOfWords = True
52.    
53.     objRegEx.Pattern = "[^a-z0-9 ]"
54.     s = objRegEx.Replace(s, "")
55.    
56.     s = split(s, " ")
57.    
58.     For i = 0 To UBound(s) \ 2
59.         If s(i) <> s(UBound(s) - i) Then
60.             PalindromeOfWords = False
61.         End If
62.     Next
63. End Function

Code is hidden, SHOW

Edit: Result

textLine number Off | Show | Select all

1. Morning the in bed to goes chrissie
2.  Matches? True
3.  Palindrome? False
4.  Palindrome of words? False
5. Red it's if except, green always plant a is why
6.  Matches? True
7.  Palindrome? False
8.  Palindrome of words? False
9. Plant a plant
10.  Matches? True
11.  Palindrome? False
12.  Palindrome of words? True

Code is hidden, SHOW

[tarwn]

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

pythonLine number Off | Show | Select all

1. import re;
2.  
3. def RevSentence(sent):
4.     if type(sent) != type([]): return RevSentence(["You're supposed to give me an array - or in this case a list - not whatever junk you tried to give me, please try again later."])
5.     s = ''.join([str(i) for i in sent])
6.     s = re.compile("((?:[a-zA-Z0-9_']|(?:\-(?!\\n)))+)((?:[^a-zA-Z0-9_\-']+)|$|(?:-\\n))").findall(s)
7.     s = FlattenAndFlip(s)           #flatten and flip the resulting tuples
8.     s = s[1:] + [s[0]]          #flip the first entry to the end (final punctuation)
9.     s[0] = s[0][0].upper() + s[0][1:]   #recase the first word
10.     s[-2] = s[-2].lower()           #recase the last word
11.     return "".join(s)           #return it as a string
12.    
13. def FlattenAndFlip(li):
14.     if type(li) == type(()): li = list(li)
15.     if type(li) != type([]): return [li]
16.     if li == []: return li
17.     return FlattenAndFlip(li[-1]) + FlattenAndFlip(li[:-1])
18.  
19. # Example Code
20. s0 = ["T","h","e"," ","q","u","i","c","k"," ","b","r","o","w","n"," ","f","o","x"," ","d","o","-","e","s"," ","s","o","m","e","t","h","i","n","g"," ","o","r","-","\n","o","t","h","e","r"," ","a","n","d"," ","i","t",","," ","c","a","n","'","t"," ","h","e","l","p"," ","i","t","."]
21. #s0 = "a"
22. print s0
23. print RevSentence(s0)
24.  

Code is hidden, SHOW

[ZmrAbdulla]

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

vbnetLine number Off | Show | Select all

1.    Sub Reverse_Sentence(ByVal strInput As String)
2.         Dim strWords() As String
3.         strWords = strInput.Split(" ")
4.         Dim i As Integer
5.         Dim strOutPut As String = String.Empty
6.         For i = UBound(strWords) To 0 Step -1
7.             strOutPut &= strWords(i).ToString & " "
8.         Next
9.         Me.TextBox2.AppendText(strOutPut.TrimEnd)
10.         If strInput.ToLower = Me.TextBox2.Text.ToLower Then
11.             Me.TextBox2.AppendText(vbCrLf & vbCrLf & "This is a palindrom")
12.         End If
13.     End Sub

Code is hidden, SHOW

the result was

textLine number Off | Show | Select all

1. Chrissie goes to bed in the morning
2. morning the in bed to goes Chrissie
3.  
4. Why is a plant always green, except if it's red
5. red it's if except green, always plant a is Why
6.  
7. Plant a plant
8. plant a Plant
9.  
10. This is a palindrom

Code is hidden, SHOW

[chrissie1]

Zameer the result you got are not exactly the same as the testcases. You forgot punctuation and Capitals.

[ZmrAbdulla]

Capitalization is possible. But I don't have any idea how to deal with punctuation.

[tarwn]

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:

pythonLine number Off | Show | Select all

1. import re
2.  
3. def RevSentenceA(sentence):
4.     if type(sentence) != type([]): return RevSentence(["You're supposed to give me an array - or in this case a list - not whatever junk you tried to give me, please try again later."])
5.     s0 = ''.join([str(i) for i in sentence])
6.     s = re.compile("((?:[a-zA-Z0-9_']|(?:\-(?!\\n)))+)((?:[^a-zA-Z0-9_\-']+)|$|(?:-\\n))").findall(s0)
7.     s = FlattenAndFlip(s)           #flatten and flip the resulting tuples
8.     s = s[1:] + [s[0]]          #flip the first entry to the end (final punctuation)
9.     s[0] = s[0][0].upper() + s[0][1:]   #recase the first word
10.     s[-2] = s[-2].lower()           #recase the last word
11.     s = "".join(s)
12.     return [s,s0 == s]      #a string a boolean to indicate if it is a palindrome
13.    
14. def RevSentenceB(sentence):
15.     if type(sentence) != type(""): return RevSentence("You're supposed to give me a string not whatever junk you tried to give me, please try again later.")
16.     s0 = sentence   
17.     s = re.compile("((?:[a-zA-Z0-9_']|(?:\-(?!\\n)))+)((?:[^a-zA-Z0-9_\-']+)|$|(?:-\\n))").findall(s0)
18.     s = FlattenAndFlip(s)           #flatten and flip the resulting tuples
19.     s = s[1:] + [s[0]]          #flip the first entry to the end (final punctuation)
20.     s[0] = s[0][0].upper() + s[0][1:]   #recase the first word
21.     s[-2] = s[-2].lower()           #recase the last word
22.     s = "".join(s)
23.     return [s,s0 == s]      #a string a boolean to indicate if it is a palindrome
24.  
25. def FlattenAndFlip(li):
26.     if type(li) == type(()): li = list(li)
27.     if type(li) != type([]): return [li]
28.     if li == []: return li
29.     return FlattenAndFlip(li[-1]) + FlattenAndFlip(li[:-1])
30.  

Code is hidden, SHOW

And here is the test code for both functions:

pythonLine number Off | Show | Select all

1.  
2. # Example Code
3. import time
4. def PrintResults(orig,rev,isP,etime,numRuns):
5.     print "Original: " + orig
6.     print "Reversed Sentence: " + rev
7.     if isP == True: print "\tand it's a word-unit palindrome"
8.     print "Time Elapsed (" + str(numRuns) + " runs): " + str(etime * 1000) + "ms"
9.     print "Time Per Run: " + str(etime/numRuns * 1000) + "ms"
10.     print "-" * 5
11.  
12.  
13. n = 10000
14.  
15. # ----- Test with character list
16. print "=" * 15 + " Character List " + "=" * 15
17. sent = ["C","h","r","i","s","s","i","e"," ","g","o","e","s"," ","t","o"," ","b","e","d"," ","i","n"," ","t","h","e"," ","m","o","r","n","i","n","g"]
18.  
19. t0 = time.time()
20. for i in range(0,n):    sentN = RevSentenceA(sent)
21. t1 = time.time() - t0
22. PrintResults ("".join(sent), sentN[0], sentN[1], t1, n)
23.  
24. print "=" * 46
25. print ""
26.  
27. # ----- Test with strings
28. print "=" * 15 + " Strings " + "=" * 15
29. sent = ["Chrissie goes to bed in the morning",
30.     "Plant a plant",
31.     "Why is a plant always green, except if it's red"]
32.  
33. t2 = 0
34. for sent0 in sent:
35.     t0 = time.time()
36.     for i in range(0,n):    sentN = RevSentenceB(sent0)
37.     t1 = time.time() - t0
38.     t2 = t2 + t1
39.     PrintResults(sent0, sentN[0], sentN[1], t1, n)
40.  
41. print "_" * 5 + " Aggregate String Results " + "_" * 5
42. print "Total Time Elapsed (" + str(n * 3) + " runs): " + str(t2 * 1000) + "ms"
43. print "Time Per Run: " + str(t2/(n * 3) * 1000) + "ms"
44.  

Code is hidden, SHOW

And the results:

textLine number Off | Show | Select all

1. =============== Character List ===============
2. Original: Chrissie goes to bed in the morning
3. Reversed Sentence: Morning the in bed to goes chrissie
4. Time Elapsed (10000 runs): 3006.49619102ms
5. Time Per Run: 0.300649619102ms
6. -----
7. ==============================================
8.  
9. =============== Strings ===============
10. Original: Chrissie goes to bed in the morning
11. Reversed Sentence: Morning the in bed to goes chrissie
12. Time Elapsed (10000 runs): 2287.30010986ms
13. Time Per Run: 0.228730010986ms
14. -----
15. Original: Plant a plant
16. Reversed Sentence: Plant a plant
17.         and it's a word-unit palindrome
18. Time Elapsed (10000 runs): 1104.24399376ms
19. Time Per Run: 0.110424399376ms
20. -----
21. Original: Why is a plant always green, except if it's red
22. Reversed Sentence: Red it's if except, green always plant a is why
23. Time Elapsed (10000 runs): 3036.18192673ms
24. Time Per Run: 0.303618192673ms
25. -----
26. _____ Aggregate String Results _____
27. Total Time Elapsed (30000 runs): 6427.72603035ms
28. Time Per Run: 0.214257534345ms
29.  

Code is hidden, SHOW

[Remou]

Thanks for reminding me to show a result (by including a result, that is).

[ca8msm]

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

vbnetLine number Off | Show | Select all

1.        ' Test Values
2.         Dim Test1 As Array = "Chrissie goes to bed in the morning".ToLower.Split(" ")
3.         Dim Test2 As Array = "Why is a plant always green, except if it's red".ToLower.Split(" ")
4.         Dim Test3 As Array = "Plant a plant".ToLower.Split(" ")
5.  
6.         ' Reversals
7.         Array.Reverse(Test1)
8.         Array.Reverse(Test2)
9.         Array.Reverse(Test3)
10.  
11.         ' Reversed Strings
12.         Dim String1 As String = String.Join(" ", Test1)
13.         Dim String2 As String = String.Join(" ", Test2)
14.         Dim String3 As String = String.Join(" ", Test3)
15.  
16.         ' Results
17.         Response.Write(String1.Substring(0, 1).ToUpper & String1.Substring(1) & "<br />")
18.         Response.Write(String2.Substring(0, 1).ToUpper & String2.Substring(1) & "<br />")
19.         Response.Write(String3.Substring(0, 1).ToUpper & String3.Substring(1) & "<br />")
20.  

Code is hidden, SHOW

Results:

textLine number Off | Show | Select all

1. Morning the in bed to goes chrissie
2. Red it's if except green, always plant a is why
3. Plant a plant
4.  

Code is hidden, SHOW

[chrissie1]

Close but not close enough. I know what the result will be but could you post them anyway?

[ca8msm]

As yes, I see what you mean now (the comma's position).

[ca8msm]

Here's a modified version:

vbnetLine number Off | Show | Select all

1.        ' Test Values
2.         Dim Test1 As Array = "Chrissie goes to bed in the morning".ToLower.Replace(",", " ,").Split(" ")
3.         Dim Test2 As Array = "Why is a plant always green, except if it's red".ToLower.Replace(",", " ,").Split(" ")
4.         Dim Test3 As Array = "Plant a plant".ToLower.Replace(",", " ,").Split(" ")
5.  
6.         ' Reversals
7.         Array.Reverse(Test1)
8.         Array.Reverse(Test2)
9.         Array.Reverse(Test3)
10.  
11.         ' Reversed Strings
12.         Dim String1 As String = String.Join(" ", Test1)
13.         Dim String2 As String = String.Join(" ", Test2)
14.         Dim String3 As String = String.Join(" ", Test3)
15.  
16.         ' Results
17.         Response.Write(String1.Substring(0, 1).ToUpper & String1.Substring(1).Replace(" ,", ",") & "<br />")
18.         Response.Write(String2.Substring(0, 1).ToUpper & String2.Substring(1).Replace(" ,", ",") & "<br />")
19.         Response.Write(String3.Substring(0, 1).ToUpper & String3.Substring(1).Replace(" ,", ",") & "<br />")
20.  

Code is hidden, SHOW

Results:

textLine number Off | Show | Select all

1. Morning the in bed to goes chrissie
2. Red it's if except, green always plant a is why
3. Plant a plant
4.  

Code is hidden, SHOW

[ZmrAbdulla]

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?

[chrissie1]

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.

[ZmrAbdulla]

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.

[ca8msm]

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.

[shamsm]

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

javaLine number Off | Show | Select all

1. import java.util.ArrayList;
2. import java.util.Arrays;
3. import java.util.List;
4.  
5. public class Puzzle15 {
6.  
7.     final static char[] allowedSeparators;
8.     static {
9.         allowedSeparators = new char[] { ' ', ',', '(', ')', '[', ']', };
10.         Arrays.sort(allowedSeparators);
11.     }
12.  
13.     public static void main(String[] args) {
14.  
15.         final String[] pStrings = { "Chrissie goes to bed in the morning",
16.                 "Why is a Plant always green, except if it's red", "Plant a plant",
17.                 "reverse the order of the words (not characters) in it", };
18.         for (String loopString : pStrings) {
19.             reverseString(loopString);
20.         }
21.  
22.     }
23.  
24.     private static void reverseString(final String pInput) {
25.  
26.         final List<String> tokens = new ArrayList<String>();
27.         final List<Boolean> cases = new ArrayList<Boolean>();
28.         final List<Character> separators = new ArrayList<Character>();
29.  
30.         int lastEndIndex = -1;
31.         for (int i = 0; i < pInput.length(); i++) {
32.             char loopChar = pInput.charAt(i);
33.             boolean isSeparator = Arrays.binarySearch(allowedSeparators,
34.                     getReversedSeparator(loopChar)) >= 0;
35.             if (isSeparator) {
36.                 String token = pInput.substring(lastEndIndex + 1, i);
37.                 tokens.add(token);
38.                 if (token.length() > 0) {
39.                     cases.add(Character.isUpperCase(token.charAt(0)));
40.                 } else {
41.                     cases.add(Boolean.FALSE);
42.                 }
43.                 separators.add(getReversedSeparator(loopChar));
44.                 lastEndIndex = i;
45.             }
46.         }
47.         {
48.             // add the last string
49.             String token = pInput.substring(lastEndIndex + 1);
50.             tokens.add(token);
51.             if (token.length() > 0) {
52.                 cases.add(Character.isUpperCase(token.charAt(0)));
53.             } else {
54.                 cases.add(Boolean.FALSE);
55.             }
56.         }
57.  
58.         StringBuilder reversedStringBuilder = new StringBuilder();
59.         for (int i = tokens.size() - 1, j = 0; i > 0; i--, j++) {
60.             final String token = tokens.get(i);
61.             final Boolean respectiveCase = cases.get(j);
62.             reversedStringBuilder.append(respectiveCase ? startWithUpperCase(token)
63.                     : startWithLowerCase(token));
64.             char separator = getReversedSeparator(separators.get(i - 1));
65.             reversedStringBuilder.append(getReversedSeparator(separator));
66.         }
67.         {
68.             final String token = tokens.get(0);
69.             final Boolean respectiveCase = cases.get(tokens.size() - 1);
70.             reversedStringBuilder.append(respectiveCase ? startWithUpperCase(token)
71.                     : startWithLowerCase(token));
72.         }
73.         String reversedString = correctPunctuation(reversedStringBuilder.toString());
74.  
75.         System.out.println("Input: " + pInput);
76.         System.out.println("Result: " + reversedString);
77.         System.out.println("Palindrome: " + pInput.equals(reversedString));
78.         System.out.println();
79.  
80.     }
81.  
82.     private static char getReversedSeparator(char separator) {
83.  
84.         switch (separator) {
85.         case '(':
86.             return ')';
87.         case ')':
88.             return '(';
89.         case '[':
90.             return ']';
91.         case ']':
92.             return '[';
93.         }
94.         return separator;
95.     }
96.  
97.     private static String correctPunctuation(final String pInput) {
98.         String result = pInput;
99.  
100.         final char[] separatorsToFix = { ',', '?', '!', '.', };
101.         for (int i = 0; i < separatorsToFix.length; i++) {
102.             char loopSeparator = separatorsToFix[i];
103.             result = result.replace(" " + loopSeparator, loopSeparator + " ");
104.         }
105.  
106.         return result;
107.     }
108.  
109.     private static String startWithUpperCase(final String pInputString) {
110.         StringBuilder result = new StringBuilder();
111.         if (pInputString.length() > 0) {
112.             result.append(Character.toUpperCase(pInputString.charAt(0)));
113.             if (pInputString.length() > 1) {
114.                 result.append(pInputString.substring(1));
115.             }
116.         }
117.         return result.toString();
118.     }
119.  
120.     private static String startWithLowerCase(final String pInputString) {
121.         StringBuilder result = new StringBuilder();
122.         if (pInputString.length() > 0) {
123.             result.append(Character.toLowerCase(pInputString.charAt(0)));
124.             if (pInputString.length() > 1) {
125.                 result.append(pInputString.substring(1));
126.             }
127.         }
128.         return result.toString();
129.     }
130.  
131. }
132.  

Code is hidden, SHOW

And the output:

textLine number Off | Show | Select all

1. Input: Chrissie goes to bed in the morning
2. Result: Morning the in bed to goes chrissie
3. Palindrome: false
4.  
5. Input: Why is a Plant always green, except if it's red
6. Result: Red it's if Except, green always plant a is why
7. Palindrome: false
8.  
9. Input: Plant a plant
10. Result: Plant a plant
11. Palindrome: true
12.  
13. Input: reverse the order of the words (not characters) in it
14. Result: it in (characters not) words the of order the reverse
15. Palindrome: false
16.  
17.  

Code is hidden, SHOW

[Emtucifor]

shamsm,

why is "Except" capitalized in your output?

[shamsm]

why is "Except" capitalized in your output?

Since the corresponding fourth word in the actual input (Plant) is also capitalized

[Emtucifor]

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.

[shamsm]

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

[damber]

you get my vote, shamsm, for providing extra features free of charge