# Leonardo's Apprentice

See the original problem on HackerRank.

## Solutions

A simple solution that makes use of extra space consists in simply copying words backwards to a temporary array starting from the last one.

However, an classical in-place solution exists and works in two steps: first reverse the string blindly and then reverse every single word individually.

Note that the input of this puzzle contains multiple lines and empty ones must be preserved.

Here is a C++ solution:

  1 2 3 4 5 6 7 8 9 10 11 12  std::string s{std::istreambuf_iterator(std::cin), {}}; // read full input into memory, preserving newlines and spaces std::reverse(begin(s), end(s)); // reverse the string blindly auto head = begin(s); while (head != end(s)) { auto where = std::find_if_not(head, end(s), [=](auto i) { return isalnum(*head) == isalnum(i); }); std::reverse(head, where); // reverse each word individually head = where; } std::cout << s; 

To be super strict, the lambda should be rewritten this way:

 1 2 3  [=](unsigned char i) { return !isalnum(*head) == !isalnum(i); } 

Since isalnum returns non-zero value if the character is an alphanumeric character, 0 otherwise. Also, to use this function safely, the argument should first be converted to unsigned char.

This is linear in time and constant in space (assuming s is constant).

A possible open question is: how can you solve this problem when the input does not fit the main memory?

### Patterns

The solution above can be rewritten in terms of a few functional patterns.

The idea is still to first reverse the string blindly, then to “group” letters together to form words we can use a pattern that in C++ is called chunk_by that simply groups together all contiguous elements of a range satisfying a certain condition. The condition here is something like “same category of letter” that is either a special character or an alphanumeric character.

Here is a next-generation C++ solution making use of ranges:

 1 2 3 4 5 6  std::string s{std::istreambuf_iterator(std::cin), {}}; auto output = views::reverse(s) | views::group_by([](unsigned char c1, unsigned char c2) { return !isalnum(c1) == !isalnum(c2); }) // [['g', 'n', 'i', 'r', 't', 's'], [' '], ['s', 'i', 'h', 't'], ...] | views::for_each(views::reverse_fn{}); // ['s', 't', 'r', 'i', 'n', 'g', ' ', ...] 

Then printing output gives the desired result. This solution works lazily.

A variation of this solution that changes in-place on the input string can be found here below:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  // reverse blindly (and eagerly) reverse(s); // find words (lazily) auto groups = s | views::group_by([](unsigned char c1, unsigned char c2) { return !isalnum(c1) == !isalnum(c2); }); // get sizes of each words (lazily) auto lengths = groups | views::transform([](auto g) { return size(g); }); // indexes of each words auto intervals = views::zip( lengths | views::exclusive_scan(0), lengths | views::partial_sum); // reverse each word individually for (auto [lb, ub] : intervals) actions::reverse(views::slice(s, lb, ub)); std::cout << s; 

The complete discussions about these patterns for C++ aficionados can be found here.

Another slick solution in Python by umuril_lyerood:

 1  print("\n".join(' '.join(list(reversed(line.split()))) for line in reversed(list(sys.stdin)))) 

Here is a functional one in Javascript by Francesco Osti and Simone Busoli:

  1 2 3 4 5 6 7 8 9 10 11 12  function processData(input) { console.log( input.split('\n') .map(line => line.split(' ') .reverse() .join(' ') ) .reverse() .join('\n') ) } 
We've worked on this challenge in these gyms: modena