[Challenge] Reverse Words

Here is another attempt at the challenge! There should be a way to hack the original string using the results from re.search().groups() but I am finding it really hard to make it work. Therefore, I had to use a string array. Time cost is definitely O(n).

Two reg expressions are needed, one to split the text into bits, and one to hack the words out of those bits. The trick is to move the words but leave the punctuation in place.

#!/usr/bin/python3

import re

# example text
text = "A man, a plan, a canal: Panama!"

# split into words
words = re.split(r"\s+", text)

# loop through both ends at once; 
for i in range(words.__len__() // 2):

    # pick out an actual word, without the punctuation
    # from both ends at once
    b = re.match(r"\w*", words[i]).group()
    c = re.match(r"\w*", words[-i-1]).group()

    # swap the words round, but leave any trailing
    # punctuation marks behind
    words[i] = c + words[i][b.__len__():]
    words[-i-1] = b + words[-i-1][c.__len__():]

# simple output
print(" ".join(words))

Here is the link to a running code version on repl.it

Hope you like it!

Tim F

My previous entry modified to comply with, or at least approximate, the hard difficulty:

def rev_words_hard(text):
    import re

    text += '  '
    words = re.sub('[^A-Za-z]* ', ' ', text)
    wdnum = words.count(' ') - 1
    rtext = ''

    for i in re.findall(r'\W+', text):
        if i not in r'\'\-':
            rtext += ''.join(''.join(words).split()[wdnum]) + i
            wdnum -= 1
    print(rtext)

Not sure about the time, but this one uses just a couple of variables and no data structures. Rather than build the words & signs lists, re.sub is used to create a string where every word is separated by one whitespace. Then I iterate through a generator, building the output with words sliced off the end of the string and punctuation groups supplied by the regexp.

Line 4 adding 2 whitespaces to the input is a dirty fix to handle sentences without a trailing sign as well as a workaround to Python regexp not behaving like I’m expecting it to.

Known issues: won’t handle sentences featuring spanish interpunction (before first word) or signs not followed by space. It will however process correctly words-with-dash-in-them or apostroph’d ones:

>>> rev_words_hard("May the Fourth be with ya'll")
ya'll with be Fourth the May  
>>> rev_words_hard("First, second... Third, fourth?!  Fifth:     SIXTY-SEVENTH!!")
SIXTY-SEVENTH, Fifth... fourth, Third?!  second:     First!!

repl.it link

This solution is a rag-tag mix of several ideas I wasn’t able to implement fully, eg. one based on a function that would yield the segments to concatenate and one where the loop has a regexp grab the (n-i)th word and i-th sign group. It also feels like it could run on string splicing alone. Should be fun to have a go at it again in a few months :slight_smile:

Awesome code! Love it!

jsfiddle

Intermediate Difficulty:

function reverse_words2(str) {
    var i, k, words, center, lastChar1, lastChar2;
    var punctuations = [".", ",", ":", "!", "?"];
    //simple as that, split the given string to words
    words = str.split(' ');
    //reverse the words
    words = words.reverse();
    //calculate the index of middle word
    center = Math.floor(words.length / 2);
    //replaces the punctuation symbols
    for (i = 0; i < center; i += 1) {
        //calculate index of the word from the end
        k = words.length - 1 - i;
        //get last character
        lastChar1 = words[i].charAt(words[i].length - 1);
        lastChar2 = words[k].charAt(words[k].length - 1);
        //checks if both words have punctuation symbol or only one of them, and then swap their punctuations
        if (punctuations.indexOf(lastChar1) != -1 && punctuations.indexOf(lastChar2) != -1) {
            words[i] = words[i].substr(0, words[i].length - 1) + lastChar2;
            words[k] = words[k].substr(0, words[k].length - 1) + lastChar1;
        } else if (punctuations.indexOf(lastChar1) != -1) {
            words[k] = words[k] + lastChar1;
        } else if (punctuations.indexOf(lastChar2) != -1) {
            words[i] = words[i] + lastChar2;
        }
    }
    //create  reversed string from our array of words
    return words.join(' ');

}

Intermediate / Hard Difficulty:

function reverse_words1(str) {

    var i, k, j, temp, center, chars, wordLength;

    // create an array of chars from given string
    chars = str.split('')
    center = Math.floor(chars.length / 2);
    //reverse the chars array O(n)
    for (i = 0; i < center; i += 1) {
        k = chars.length - 1 - i;
        temp = chars[i];
        chars[i] = chars[k];
        chars[k] = temp;
    }
    i = wordLength = j = 0;
    //loop through the chars array and find all words O(n)
    while (i < chars.length) {
        //find a word O(n)
        while (i + wordLength < chars.length && chars[i + wordLength] != ' ') wordLength += 1;
        center = Math.floor(wordLength / 2);
        //reverse the word O(n)
        for (j = 0; j < center; j += 1) {
            k = i + wordLength - j - 1;
            temp = chars[i + j];
            chars[i + j] = chars[k];
            chars[k] = temp;
        }
        i = i + wordLength + 1;
        wordLength = 0;
    }
    return chars.join('');
}

1 Like

I did it in java using recursion. The substring until the first space is put at the end of the result, and a call to the mirror function is made for the rest of the string. Between the two strings, a space is added. When there are no more blank spaces the string is inserted as a whole.

https://repl.it/HpQQ/3

1 Like

Thank you everyone for your submissions! With particular thanks to @alexcraig and @factoradic, here are our favorites.

#The Winners

Winner: @gigawhiz30076, first person to respond with a fully correct solution for the hard level challenge, and has included an excellent description. Makes great use of anonymous functions and is the most efficient as it uses just one for loop.
See Oscar’s solution here

2nd Place: @brotherpeteniemeyerg, nice to see a Java submission, and nice that extra thought has been put in changing the case of letters. All done in-place, but slightly less efficient due to the number of while loops, and the fact that some are nested.
See Peter’s solution here

3rd Place: @javiervfa, nice use of defining a regular expression in a variable, case in third rather than second place due to the number of while loops. Very good to see that substrings have been used, as opposed to splitting the string into an array of words (so arguably this solution is the most “in-place”).
See Javier’s entry here.


###Feedback and honorable mentions:

@bradleybirchig - your solution is not done in-place, as it uses two separate arrays. However nice, efficient implementation and runs in constant time.

@datasolver52528 - Nicely implemented, uses many separate functions, which is clearer. However, it means that it does not complete the challenge in-place, and the code takes longer to run than shorter solutions. Putting capitals in the right place is a great addition though!

@lealik17 - Nice neat solution, quite a good way of doing it, since 3 arrays are used does not meet the in-place criteria, but still very good effort.

@oneilltp18gmail.com - nice solution using a dictionary, and good use of itertools and the lambda function. This also isn’t in place.

@stopthedeath - good use of a Hash, nice Ruby solution.

@foobarfoo - lovely solution making full use of java script’s inbuilt functions and mappings, however not done in place as two separate structures are used. Very efficient solution.

@tagrockstar79958 - very nice solution, again one that uses multiple arrays and a dictionary. All pulled together very nicely.

@devsurfer70303 - algorithm works nicely and efficiently, again uses multiple structures

@rd0122 - another nice solution in python using multiple structures

@digitalmaster25468 - very good JavaScript solution making use of ASCII values, nicely implemented and thought out, however it isn’t in-place.

@cloudsolver69633 - a similar solution to digitalmaster and foobarfoo, works nicely.

@ajaxblaster47797 - nice simple python solution

2 Likes

Hi @danieloduffy,
In the winners list I don’t see anyone who has used recursion. I hope it isn’t too much for me to ask your view regarding recursion in general and my solution in particular (please see #83 in the above).

Although it doesn’t address the punctuation, I think it qualifies as a solution to one of the hard difficulty problem statement, isn’t it?

Thanks for the honorable mention!

Much obliged,
David

1 Like

Hi @arcplayer88977, I helped look over everyone’s solutions.

Recursion is a really great tool that can help in many different situations, and I would normally recommend it whenever it can be used.
Your solution does look great because it’s recursive and it does solve the easy solution brilliantly.

However, I didn’t consider it appropriate for this hard challenge for a number of reasons:

  • We asked to do it “in place”. Using recursion gives recreates the string each time you use substring, so I don’t consider it to meet the criteria of in place.
  • Recursion also causes large overheads, every time you recurse temp variables have to be saved onto the stack so that they can be read off again as you come out of the recursion. This means a lot of space is wasted saving substrings of the initial string and could cause performance issues on larger inputs. i.e. a for or while loop will finish a lot quicker than a recursive solution.
  • Turning your recursive solution into one that solved the hard challenge will be quite challenging as it would be hard to keep track of the punctuation and add it back in again efficiently.

In general, recursion is a good tool to use and makes code much more streamlined, I just didn’t think it was appropriate for the Hard challenge in this case.
However, recursion could be very nicely used in this week’s challenge and is my preferred solution.

1 Like

Thank you @alexcraig. This is very helpful!

2 Likes

Hello @arcplayer88977! Usually, picking winners is a group effort. And I usually (not in this case) participate in this process, just like @alexcraig.

We always try to make sure that rating process is transparent as much as possible and for the sake of your future submissions (for which I am hoping for) I would like to present my view towards recursive solutions.

I simply love recursion, it’s elegant, neat, easy to read and easy to write. But when we deal with algorithmic problems, especially in technical interviews, it’s very important to be aware of pros and cons of programming techniques and of programming languages.

In imperative languages, recursion is strictly related to one of the most common problems - stack overflow. When you decide to use recursion you automatically add an artificial limit upon the size of input data. This leads to a situation where the same code written using loops works much faster and is more scalable. Recursion is simply a bad design choice.

Some imperative languages use tail-call optimisation. This allows us to write a special kind of recursive solutions that do not allocate new stack frames (because they do not have to). You submitted solution written in JavaScript. JavaScript is a funny language because its specification changes very dynamically and developers of engines are not keeping up with the changes. But, ES6 introduced tail-call optimisation. The problem is the fact that your code does not make use of it :slight_smile:

To summarise:

  1. In imperative languages, it’s always better to use iterative solutions because of the limited size of the stack and faster execution;
  2. If you have to use recursion make sure that it is tail-call optimised and that your language of choice supports this technique (JavaScript - yes, Python - nope);
  3. Recursion is a great way to prototype things (proofs of concepts);
  4. In functional languages (like Haskell), recursion is a first class citizen and you are most welcome to submit recursive solutions written in Haskell or Scheme.

If you would like to learn a bit more about tail-call optimisation I have found this article -> http://benignbemine.github.io/2015/07/19/es6-tail-calls/, it uses JavaScript in examples. I hope it will be easy to follow and informative :slight_smile:

2 Likes

Thank you for the mention! That’s pretty awesome!

Bradley :slight_smile:

Can I get some feedback on my second submission regarding how far it fell from meeting the hard difficulty requirements? In particular, if using a string is still a deal-killer because of its immutability in Python, how to work around it?

1 Like

Thanks a lot for this. I’m quite impressed, actually, with the quality of feedback I’m getting here… :slight_smile:

2 Likes

Before getting into your code, please note that I wasn’t a judge in this challenge and because of this I only present my own opinion that might be completely unrelated to the results of this challenge.


In particular, if using a string is still a deal-killer because of its immutability in Python, how to work around it?

That’s problematic. In a normal job interview, you can always ask a question or make some kind of remark. We are not able to reproduce this formula here, in the topic. Mainly because of our limited time resources.

While reading this challenge description it was clear for me that by string author meant list (or array) of characters that is mutable. Mainly because the task was to create in-place solution. So in the case of Python, where strings are immutable, I would assume that instead of Python string I can use a normal list of characters or a byte array.

When we talk about programming in general, not in the context of specific language, we usually use word string as a reference to the array of characters (mutable).

We are getting better at creating and managing these challenges, really. And I can assure you that from now on I will do my best to not make this mistake again :slight_smile:


Regarding your code. You are well aware that additional space complexity of your code is O(n), which does not qualify for the in-place, but this was the result of a misunderstanding.

Your code extensively uses regular expressions. Regular expressions are great and many novice programmers use them everywhere because they heard that regular expression only needs linear time to be executed (this is usually true). The thing is, the regular expression is an abstract syntax that is impossible for compiler/interpreter to use for matching a string. Before this happens, the regular expression needs to be compiled to the different form - finite state machine. And this, depending on the implementation and chosen method might take a lot of time.

Don’t get me wrong, sometimes it’s natural to use a regular expression. But take a look at this:

if i not in r'\'\-':

I know this is a simple and short expression. But it requires the interpreter to transform this expression into the finite state machine and then state engine will be evoked to match passed string (i, single character).

The alternative is quite simple, better looking (regular expressions are not known for their readability) and faster:

if i not in ["'", "-"]:

In summary, I really like your code. It’s a really well-thought solution. Space complexity was the main issue. I am sorry for the misunderstanding.


Here is the article that is well-known in the programmers’ world. It shows why regular expressions are usually viewed as slow (which is not always true) → Regular Expression Matching Can Be Simple And Fast.

2 Likes

Thanks for great feedback! I’ve long been using regular expressions for scripting and text processing and now that I’m learning real programming, they could become another bad habit I wouldn’t even be aware of otherwise. The if statement was a remainder from more complex, ugly routine meant to handle the problems I had mentioned - my failure to spot it in the tiny submitted code is another valuable lesson before I get to produce anything bigger, swamped with even more garbage :slight_smile: That being said, a good use of regexp still feels like key to solving this challenge in the most elegant manner that I’m hoping to figure out one day.

2 Likes

I worked on this challenge very late, just for practice. The basic version wasn’t much trouble, but the intermediate challenge took me a while. This is the first time I’ve used regular expressions, so I had to read a lot of documentation and do trial and error to figure it out. I also just got stuck for ideas, so I did skim some of the solutions already presented, and that’s where I took the idea of using left and right pointers. My solution is not the most efficient, I’m sure, but at least I finally got it to work:

Intermediate challenge:

function reverseWords(str) {

  // Split the string at its word boundaries to create an array:
  let arr = str.split(/\b/);

  // Set up pointers for the left and right to use as we go through the array from both directions:
  let left = 0;
  let right = arr.length - 1;

  // Create a regular expression to identify words (as opposed to punctuation):
  const regex = RegExp(/\w/);

  // The switch will continue until the two pointers meet or cross:
  while (left < right) {

    // Check if the string at the left pointer is a word:
    if (regex.test(arr[left])) {

      // Check if the string at the right pointer is a word. If not, go to the next string. Once we find a word, switch the strings at the left and right pointers:
      while (!regex.test(arr[right])) {
       right--;
      };
      let temp = arr[right];
      arr[right] = arr[left];
      arr[left] = temp;
    }

    // After the switch, move each pointer over one:
    left++;
    right--;
  }

  // Turn the array back into a string:
  let result = arr[0];
  for (let i = 1; i < arr.length; i++) {
    result += arr[i];
  }

  // Return the result:
  return result;
};

Repl.it: https://repl.it/@JessicaAHom/04reverseWords

1 Like

Hi @j_hom!

I’m on the same boat as you. I did the easy version in 5 minutes with a single line:

function reverseWordsNoPunc(str) {
    return str.split(" ").reverse().join(" ")
}

However, the intermediate version took my sleep away last night :rofl:

I eventually solved it and I used a very similar approach to yours. However I think mine is even a bit less efficient than yours because I actually create a new array and build it from scratch from the original.

Anyway good job us!! :beers:

Here’s my version:

function reverseWordsPunc(str) {
    // Split string by word boundaries, i.e. separates sequences of alphanumeric chars from sequences of non-alphanumeric chars
    // E.g. 'with you, be may!' becomes ['with', ' ', 'you', ', ', 'be', ' ', 'may', '!']
    let originalArray = str.split(/\b/)
    const arrayLength = originalArray.length

    // Create new empty array with same length as originalArray
    let newArray = new Array(arrayLength)

    // Loop through originalArray
    for (let i = 0; i < arrayLength; i++) {
        // If current element starts with a non-alphanumeric char
        if (originalArray[i].match(/\W/)) {
          // Puts the element in the newArray on the same position as it is on the originalArray  
          newArray[i] = originalArray[i]
          // Otherwise, i.e. if the current element is a word...
        } else {
            // Create a variable with the 'mirror' position, e.g. on an array with length 6: [5] mirrors [0], [4] mirrors [1] and [3] mirrors [2]
            let mirror = arrayLength - 1 - i
            // If the mirror position contains punctuation, i.e. non-alphanumeric chars, we can't touch it.
            // So we start going backwards on the originalArray until we find a word.
            while (originalArray[mirror].match(/\W/)) {
                mirror--
            }
            // Once we find a word on the originalArray we can put the current word on the new array on that position
            newArray[mirror] = originalArray[i]
        }
    }

// Return newArray joined back as string
    return newArray.join("")
}
def word_reverser(phrase): # Write your code here reverse = "" var = 0 for i in range(len(phrase)): if phrase[-i] == " ": for a in range(var-1): reverse += phrase[-i+a+1] reverse += " " var = 1 else: var += 1 if reverse == "": return phrase for letter in phrase: if letter == " ": return reverse reverse += letter print(word_reverser("May the Fourth be with you")) print(word_reverser('Codecademy rules'))

Basic Challenge:

def reverse_string(string):
return " “.join(string.split(” ")[::-1])
#i start with splitting the string into different component of a list ==> assess the list through calling [::-1] so the it goes backwack ==> then i join the list through join method with space in between