Leonardo's Apprentice

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<char>(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<char>(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')
  )
} 

string patterns