5
\$\begingroup\$

Original Problem Statement


Problem Analysis

Task: Given a sentence, mangle each word and output the result.

Clarifications:

Mangling will be defined as a word with its characters in case-insensitive order. The case of the original character is preserved at the same location in the resulting mangled word (e.g., Oh becomes Ho). Punctuation location should be preserved.

A sentence is a collection of words separated by spaces (and only spaces). A word is a grouping of non-space symbols. Punctuation is any non-alphanumeric or space character.


Tests

Input 1:

This challenge doesn't seem so hard.

Output 1:

Hist aceeghlln denos't eems os adhr.

Input 2:

There are more things between heaven and earth, Horatio, than are dreamt of in your philosophy.

Output 2:

Eehrt aer emor ghinst beeentw aeehnv adn aehrt, Ahioort, ahnt aer ademrt fo in oruy hhilooppsy.


Solution Wandbox Live Demo

My approach was to sort the values using merge sort and in-place merge. Unfortunately, the STL doesn't provide a merge sort over two or more separated ranges (only adjacent ranges). The original input is not tokenized. Instead, I generate the range of all tokens and operate on those ranges.

Primary solution with simple driver:

#include "MyAlgorithms.h"

#include <cctype>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

template <typename Iterator, typename Comparator>
void inplace_mangle(Iterator first, Iterator last, Comparator comp) {
  const auto isupper_locations = my::collect_if(first, last, ::isupper);

  for (auto &loc : isupper_locations) {
    *loc = ::tolower(*loc);
  }

  const auto word_ranges = my::collect_ranges_if(first, last, ::isalnum);

  my::sort_ranges(word_ranges, comp);
  my::inplace_merge_ranges(word_ranges, comp);

  for (auto &loc : isupper_locations) {
    *loc = ::toupper(*loc);
  }
}

int main() {
  std::vector<std::string> sentences = {
    "This challenge doesn't seem so hard.",
    "There are more things between heaven and earth, Horatio, than are "
    "dreamt of in your philosophy.",
    "Eye of Newt, and Toe of Frog, Wool of Bat, and Tongue of Dog.",
    "Adder's fork, and Blind-worm's sting, Lizard's leg, and Howlet's wing.",
    "For a charm of powerful trouble, like a hell-broth boil and bubble." };

  const std::vector<std::string> solutions = {
    "Hist aceeghlln denos't eems os adhr.",
    "Eehrt aer emor ghinst beeentw aeehnv adn aehrt, Ahioort, ahnt aer "
    "ademrt fo in oruy hhilooppsy.",
    "Eey fo Entw, adn Eot fo Fgor, Loow fo Abt, adn Egnotu fo Dgo.",
    "Adder's fkor, adn Bdilm-nors'w ginst, Adilrs'z egl, adn Ehlost'w ginw.",
    "For a achmr fo eflopruw belortu, eikl a behh-llort bilo adn bbbelu." };

  for (auto &sentence : sentences) {
    const auto words =
      my::collect_ranges_if_not(sentence.begin(), sentence.end(), ::isspace);

    for (auto &word : words) {
      inplace_mangle(word.begin(), word.end(), std::less<char>());
    }
  }

  auto current_solution = solutions.begin();
  for (const auto &sentence : sentences) {
    std::cout << sentence << '\n';
    std::cout << "Passed? " << std::boolalpha << (sentence == *current_solution++)
              << "\n\n";
  }
}

<MyAlgorithms.h> Library (Applicable Functions)

#ifndef MY_ALGORITHMS_H_INCLUDED
#define MY_ALGORITHMS_H_INCLUDED

#include <algorithm>
#include <vector>

namespace my {
  template <typename Iterator> class BasicRangeIterator {
    Iterator first;
    Iterator last;

  public:
    explicit BasicRangeIterator(Iterator first, Iterator last)
      : first(first), last(last) {}
    Iterator begin() const { return first; };
    Iterator end() const { return last; };

    bool operator==(const BasicRangeIterator &rhs) const {
      return first == rhs.first && last == rhs.last;
    }

    bool operator!=(const BasicRangeIterator &rhs) const { 
      return *this != rhs; 
    }
  };

  template <typename InputIterator, typename UnaryPredicate,
            typename ResultType = std::vector<BasicRangeIterator<InputIterator>>>
  ResultType collect_ranges_if(InputIterator first, InputIterator last,
                               UnaryPredicate pred) {
    ResultType result;

    for (auto mid = first; true; ++mid) {
      first = std::find_if(mid, last, pred);
      mid = std::find_if_not(first, last, pred);
      result.emplace_back(first, mid);

      if (mid == last) {
        break;
      }
    }

    return result;
  }

  template <typename InputIterator, typename UnaryPredicate,
            typename ResultType = std::vector<BasicRangeIterator<InputIterator>>>
  ResultType collect_ranges_if_not(InputIterator first, InputIterator last,
                                   UnaryPredicate pred) {
    ResultType result;

    for (auto mid = first; true; ++mid) {
      first = std::find_if_not(mid, last, pred);
      mid = std::find_if(first, last, pred);
      result.emplace_back(first, mid);

      if (mid == last) {
        break;
      }
    }

    return result;
  }

  template <typename InputIterator, typename UnaryPredicate,
            typename ResultType = std::vector<InputIterator>>
  ResultType collect_if(InputIterator first, InputIterator last,
                        UnaryPredicate pred) {
    ResultType result;

    first = std::find_if(first, last, pred);

    while (first != last) {
      result.push_back(first);
      first = std::find_if(++first, last, pred);
    }

    return result;
  }

  template <typename BidirIterator, typename Comparator>
  void inplace_merge(BidirIterator lower_first, BidirIterator lower_last,
                     BidirIterator upper_first, BidirIterator upper_last,
                     Comparator comp) {
    for (; upper_first != upper_last; ++upper_first) {
      auto pivot = std::upper_bound(lower_first, lower_last, *upper_first, comp);

      if (pivot != lower_last) {
        std::rotate(pivot, std::prev(lower_last), lower_last);
        std::iter_swap(pivot, upper_first);
      }
    }
  }

  template <typename IteratorPairedRange, typename Comparator>
  void sort_ranges(const IteratorPairedRange &ranges, Comparator comp) {
    for (auto &range : ranges) {
      std::sort(std::begin(range), std::end(range), comp);
    }
  }

  template <typename BidirIteratorPairRange, typename Comparator>
  void inplace_merge_ranges(const BidirIteratorPairRange &range,
                            Comparator comp) {
    for (auto &upper : range) {
      for (auto &lower : range) {
        if (lower == upper) {
          break;
        }

        inplace_merge(std::begin(lower), std::end(lower), std::begin(upper),
          std::end(upper), comp);
      }
    }
  }
} // namespace my
#endif // MY_ALGORITHMS_H_INCLUDED
\$\endgroup\$
4
  • \$\begingroup\$ Rather than using make-shift tests in main(), you may wish to look into actual unit tests. \$\endgroup\$
    – user34073
    Jun 30, 2015 at 2:10
  • \$\begingroup\$ I kinda just wrote it on wandbox over a slow period right before and during my lunch break. The driver was just included to show that it does compile and does work. I had smaller tests for the individual components, but didn't include them. \$\endgroup\$
    – Snowhawk
    Jun 30, 2015 at 2:12
  • \$\begingroup\$ OK, just thought you might be interested. \$\endgroup\$
    – user34073
    Jun 30, 2015 at 2:14
  • \$\begingroup\$ For some reason, I didn't even think to use the Boost test library when writing it. Definitely should have. \$\endgroup\$
    – Snowhawk
    Jun 30, 2015 at 2:16

1 Answer 1

1
\$\begingroup\$
for (auto mid = first; true; ++mid) {
  ...
  if (mid == last) {
    break;
  }
}

looks strange. Why not

for (auto mid = first; mid != last; ++mid)

If you want to ensure that the body is executed at least once, use do ... while().

I am not sure I understand what do you mean by merge sort over two or more separated ranges. At least I don't see where the sorting separate ranges is called for. Mangling in-place each word (or range) independently seem to suffice.

\$\endgroup\$
4
  • \$\begingroup\$ I suppose I should have just made the for a while. The reason I pulled the conditional is you can't increment the iterator beyond end(). If I search a range and the last entry is mid == end(), the for will attempt to increment and be out of range. \$\endgroup\$
    – Snowhawk
    Jun 30, 2015 at 7:57
  • \$\begingroup\$ A for condition mid != end() is executed before mid is incremented, so you are safe. The only difference is that in your code a loop body is executed even if `first == end()1 at the very beginning. Is it intended? \$\endgroup\$
    – vnp
    Jun 30, 2015 at 8:19
  • \$\begingroup\$ Since I had the loop searching for both the start and end of the subranges at the same time, mid ends up updating in the loop and becoming last is a concern that had to be addressed as I didn't want to increment beyond last. I probably should have avoided trying to handle all the range cases (empty, single, many) and instead split out the special empty range by itself. Definitely a poor decision for readability. \$\endgroup\$
    – Snowhawk
    Jun 30, 2015 at 8:32
  • \$\begingroup\$ As for your second concern, the problem requires that the alphanumerics in a word be sorted. \$\endgroup\$
    – Snowhawk
    Jun 30, 2015 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.