October 30, 2015 9:00 AM
Let’s begin with the program to reverse a string in place, without considering the requirement to ignore special characters. The simple algorithm uses two pointers, one to the left end of the string and one to the right end of the string, swapping the two characters they point to, then moving the pointers one character closer to the other at each step until they meet:
(define (string-reverse! str)
(let loop ((lo 0) (hi (- (string-length str) 1)))
(cond ((<= hi lo) str)
(else (let ((t (string-ref str lo)))
(string-set! str lo (string-ref str hi))
(string-set! str hi t)
(loop (+ lo 1) (- hi 1)))))))
> (string-reverse! "a!b3c") "c3b!a"
Now it is obvious how to reverse a string while ignoring special characters; ensure that lo and hi never point to special characters:
(define (string-reverse! str)
(let loop ((lo 0) (hi (- (string-length str) 1)))
(cond ((<= hi lo) str)
((not (char-alphabetic? (string-ref str lo)))
(loop (+ lo 1) hi))
((not (char-alphabetic? (string-ref str hi)))
(loop lo (- hi 1)))
(else (let ((t (string-ref str lo)))
(string-set! str lo (string-ref str hi))
(string-set! str hi t)
(loop (+ lo 1) (- hi 1)))))))
> (string-reverse! "a!b3c") "c!b3a"
This function is identical to the previous function except that two clauses have been added to the cond expression, one checking that the lo character is alphabetic and one checking that the hi character is alphabetic.
You can run the program at http://ideone.com/Szld2K.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
Two solutions in scala.
The first works with the indexes -> complicated, slow
The second is a faster tail recursive solution
package programmingpraxis // https://programmingpraxis.com/2015/10/30/reverse-string-ignoring-special-characters/ object ReverseStringIgnoringSpecialCharacters { // Given an input string that contains both alphabetic characters and non-alphabetic characters, reverse the alphabetic characters while leaving the non-alphabetic characters in place. // For instance, given the input string a!b3c, return the output string c!b3a, where the non-alphabetic characters ! and 3 are in their original positions. val in = "a!b3c,d.abc" def rsisc(in: String): String = { val rev = in.filter(_.isLetter).reverse val is = in.zipWithIndex.filter(_._1.isLetter).zipWithIndex val revis = is.map(x => (rev(x._2), x._1._2)) val isall = revis ++ in.zipWithIndex.filter(!_._1.isLetter) isall.sortBy(_._2).unzip._1.mkString } rsisc(in) //> res0: String = c!b3a,d.cba def rsiscTailRec(in: String): String = { def rsiscTailRec(in: String, lettersReversed: String, agg: String = ""): String = { if (in.isEmpty()) agg else if (in.head.isLetter) rsiscTailRec(in.tail, lettersReversed.tail, agg + lettersReversed.head) else rsiscTailRec(in.tail, lettersReversed, agg + in.head) } rsiscTailRec(in, in.filter(_.isLetter).reverse) } rsiscTailRec(in) //> res1: String = c!b3a,d.cba }By FA on October 30, 2015 at 9:53 AM
Here’s some C++:
#include <stdio.h> #include <ctype.h> #include <string.h> #include <algorithm> template<typename T, typename P> void srev(T start, T end, P pred) { while(start < end) { if (!pred(*start)) start++; else if (!pred(*end)) end--; else std::swap(*start++,*end--); } } int main(int argc, char *argv[]) { char *s = argv[1]; srev(s, s+strlen(s)-1, isalpha); printf("%s\n", s); }And some Haskell:
By matthew on October 30, 2015 at 10:47 AM
Haskell:
strrev s = substAlpha s [ x | x<-(reverse s), isAlpha x ] where substAlpha s1 "" = s1 substAlpha (x:xs) s2@(y:ys) | isAlpha x = y : (substAlpha xs ys) | otherwise = x : (substAlpha xs s2)By wert310 on October 30, 2015 at 11:01 AM
In Python.
def swap_alpha(txt): alphas = reversed([t for t in txt if str.isalpha(t)]) return "".join(next(alphas) if str.isalpha(t) else t for t in txt)By Paul on October 30, 2015 at 11:10 AM
Standard ML solution.
(* reverseAlpha Works by comparing the supplied string s to reverse(s') where s' is only the alpha characters from s. Example: s ="a!b3c" s' ="cba" output | transitions -------------------- [] | a!b3c -> !b3c | cba ba c | !b3c -> b3c | ba ba c! | b3c -> 3c | ba a c!b | 3c -> c | a a c!b3 | c -> [] | a c!b3a *) fun reverseAlpha s = let val chars = (explode s) val alphachars = List.filter (fn c => Char.isAlpha c) chars fun reverseAlpha' [] [] acc = acc | reverseAlpha' [] (r::rs) acc = acc | reverseAlpha' (L as c::cs) [] acc = acc @ L | reverseAlpha' (L as c::cs) (R as r::rs) acc = if Char.isAlpha c then reverseAlpha' cs rs (acc @ [r]) else reverseAlpha' cs R (acc @ [c]) in reverseAlpha' chars (List.rev alphachars) [] endBy mcmillhj on October 30, 2015 at 4:06 PM
Here is a Common Lisp solution:
As you can see, it’s very simple. We just use a “generic” function that is not restricted to strings, or vectors, but that will work on any sequence (list, vectors, strings), and using any predicate to select the elements to be reversed.
We’ll use Common Lisp generic functions with methods to provide the variants for the various sequence subclasses (and since string is a subclass of vector, it’ll be included in the method for vector).
Also, we provide two versions of the generic function, one destructive and one non-destructive. nreverse-elements-such will reverse the sequence in place, while reverse-elements-such will create a new sequence. Of course, we will reuse the former to implement the later.
(defgeneric nreverse-elements-such (predicate sequence) (:method (predicate (sequence list)) (replace sequence (nreverse-elements-such predicate (coerce sequence 'vector)))) (:method (predicate (sequence vector)) (loop :with i := 0 :with j := (1- (length sequence)) :while (< i j) :do (cond ((not (funcall predicate (aref sequence i))) (incf i)) ((not (funcall predicate (aref sequence j))) (decf j)) (t (rotatef (aref sequence i) (aref sequence j)) (incf i) (decf j)))) sequence)) (defgeneric reverse-elements-such (predicate sequence) (:method (predicate (sequence list)) (coerce (nreverse-elements-such predicate (coerce sequence 'vector)) 'list)) (:method (predicate (sequence vector)) (nreverse-elements-such predicate (copy-seq sequence)))) (defun test/reverse-elements-such () (let ((tests '(((1 2 3 4 5 6 7 8) oddp (7 2 5 4 3 6 1 8)) ((2 4 6 8 1 3 5 7) oddp (2 4 6 8 7 5 3 1)) ((1 3 5 7 2 4 6 8) oddp (7 5 3 1 2 4 6 8)) ((1 2 3 4 5 6 7 8) oddp (7 2 5 4 3 6 1 8)) ((1 3 5 2 4 6 7 8) oddp (7 5 3 2 4 6 1 8)) ((2 4 6 8 1 3 5) oddp (2 4 6 8 5 3 1)) ((1 3 5 2 4 6 8) oddp (5 3 1 2 4 6 8)) ((1 3 5 2 4 6 8) oddp (5 3 1 2 4 6 8)) ((2 4 6 8) oddp (2 4 6 8)) ((1 3 5 7) oddp (7 5 3 1)) ((1) oddp (1)) ((2) oddp (2)) (() oddp ())))) (loop :for (sequence predicate expected) :in tests :do (let ((input (copy-seq sequence))) (let ((output (nreverse-elements-such predicate input))) (assert (eql input output)) (assert (equalp output expected)))) (let ((input (coerce sequence 'vector))) (let ((output (nreverse-elements-such predicate input))) (assert (eql input output)) (assert (equalp output (coerce expected 'vector))))) (let ((input (copy-seq sequence))) (let ((output (reverse-elements-such predicate input))) (assert (or (null output) (not (eql input output)))) (assert (equalp input sequence)) (assert (equalp output expected)))) (let ((input (coerce sequence 'vector))) (let ((output (reverse-elements-such predicate input))) (assert (not (eql input output))) (assert (equalp input (coerce sequence 'vector))) (assert (equalp output (coerce expected 'vector))))))) :success) (test/reverse-elements-such) ;; --> :success (defun reverse-string-leaving-non-alphabetic-in-place (string) (reverse-elements-such (function alpha-char-p) string)) (defun test/reverse-string-leaving-non-alphabetic-in-place () (assert (string= (reverse-string-leaving-non-alphabetic-in-place "reverse-string-leaving-non-alphabetic-in-place") "ecalpni-citeba-hplanon-gni-vaelgnirts-es-rever")) (assert (string= (reverse-string-leaving-non-alphabetic-in-place "a!b3c") "c!b3a")) :success) (test/reverse-string-leaving-non-alphabetic-in-place) ;; --> :successBy Informatimago on October 30, 2015 at 9:46 PM
I’m learning Julia, at v0.4.0 now. Strings are stored as UTF-8, character length in a string varies, in-place mutation makes no sense. A vector of valid indices is neatly reversed using a bit vector to mark the positions of the alphabetic indices. The resulting index gives the result.
"""Reverses alphabetically, leaving rest as is.""" function ralph(s::AbstractString) x = collect(eachindex(s)) v = falses(length(x)) v[find(k -> isalpha(s[k]), x)] = true x[v] = reverse(x[v]) s[x] end let s = "Tämä! on testi. Väli-merkein!?" println(s) println(ralph(s)) end # printlns: # Tämä! on testi. Väli-merkein!? # niek! re miläV. itse-tnoämäT!? let s = "c!b3a" println(s) println(ralph(s)) end # printlns: # c!b3a # a!b3cBy Jussi Piitulainen on October 31, 2015 at 8:26 PM
Another Haskell solution. Similar to the Lisp version, we write a reversal function that takes a predicate indicating which elements to reverse and which to leave in their original positions. We then use it to define functions to reverse letters of a string and odd numbers in a list of numbers. (Arguably, the revPred function suffers from a round of code golf. It’s a sickness… :-)
By Globules on November 1, 2015 at 1:37 AM
//https://programmingpraxis.com/2015/10/30/reverse-string-ignoring-special-characters/ // This solution is verbose, but solves the problem in an interesting way. // // We create a Sort_proxy object that stores a pointer to the original // elements. We create a swap member function that swaps the original values // in-place. Then we create a global override for swap that calls our member // function, because that's what std::reverse will use. // // We create a std::vector of these Swap_proxy objects. We initialize it with // proxies to the alpha characters in the target string. // // Now, when we reverse the vector, rather than sorting the proxy objects // themselves, it sorts the alpha charaters in the original string. // // Requires C++11. #include <string> #include <vector> #include <algorithm> #include <cctype> #include <iostream> template<typename T> class Sort_proxy { public: Sort_proxy(T* tp = nullptr): p(tp) {} void swap(Sort_proxy& that) { T t = *(that.p); *(that.p) = *p; *p = t; } private: T* p; }; template<typename T> void swap(Sort_proxy<T>& lhs, Sort_proxy<T>& rhs) { lhs.swap(rhs); } int main() { std::string s("a!b3c"); std::vector<Sort_proxy<char>> v; for (auto& c: s) if (isalpha(c)) v.push_back(Sort_proxy<char>(&c)); std::reverse(v.begin(), v.end()); std::cout << s << '\n'; }By fisherro on November 1, 2015 at 1:42 PM
Another, more straight-forward solution…
//https://programmingpraxis.com/2015/10/30/reverse-string-ignoring-special-characters/ #include <string> #include <algorithm> #include <iterator> #include <cctype> #include <iostream> int main() { std::string s1("a!b3c"); //Copy just the alpha characters into a second string. std::string s2; std::copy_if(s1.begin(), s1.end(), std::back_inserter(s2), ::isalpha); //Reverse the alpha characters. std::reverse(s2.begin(), s2.end()); //Substitute the alpha characters back into the original string. std::transform(s1.begin(), s1.end(), s1.begin(), [&s2, i = 0UL](char c) mutable { return isalpha(c)? s2[i++]: c; }); std::cout << s1 << '\n'; }By fisherro on November 1, 2015 at 1:44 PM
@fisherro: Nice ingenious solution. We can extend your proxy idea to an outer container of iterators over the inner container, with a suitable iterator class that acts as a proxy for the inner elements. Now we can eg. sort all digits as well as reversing just the alphabetic characters:
#include <vector> #include <string> #include <cctype> #include <iterator> #include <algorithm> #include <iostream> template<template <class...> class InnerCont, template <class...> class OuterCont, typename T> class ProxyCont { private: typedef InnerCont<T> Inner; typedef typename Inner::iterator InnerIter; typedef OuterCont<InnerIter> Outer; typedef typename Outer::iterator OuterIter; typedef typename OuterIter::iterator_category OuterIterCat; typedef typename OuterIter::difference_type OuterIterDiff; public: typedef T value_type; class iterator: public std::iterator<OuterIterCat, char> { public: iterator(OuterIter it_) : it(it_) {} value_type &operator*() { return **it; } iterator operator--() { return iterator(--it); } iterator operator++() { return iterator(++it); } friend iterator operator+(iterator it, int n) { return iterator(it.it + n); } friend iterator operator-(iterator it, int n) { return iterator(it.it - n); } friend OuterIterDiff operator-(iterator it1, iterator it2) { return it1.it - it2.it; } friend bool operator==(iterator it1, iterator it2) { return it1.it == it2.it; } friend bool operator!=(iterator it1, iterator it2) { return it1.it != it2.it; } friend bool operator<(iterator it1, iterator it2) { return it1.it < it2.it; } private: OuterIter it; }; iterator begin() { return iterator(a.begin()); } iterator end() { return iterator(a.end()); } void push_back(InnerIter it) { a.push_back(it); } private: Outer a; }; int main(int argc, char *argv[]) { for (int i = 1; i < argc; i++) { std::string s(argv[i]); ProxyCont<std::basic_string,std::vector,char> alphas; ProxyCont<std::basic_string,std::vector,char> nums; for (auto it = s.begin(); it != s.end(); it++) { if (std::isalpha(*it)) alphas.push_back(it); else if (std::isdigit(*it)) nums.push_back(it); } std::reverse(alphas.begin(), alphas.end()); std::sort(nums.begin(), nums.end()); std::cout << s << '\n'; } }By matthew on November 2, 2015 at 6:50 PM
@matthew Very nice!
I’m not sure if it is ever practical, but I like the fact that you could use this to std::sort a std::list in-place by proxying through a std::vector.
By fisherro on November 2, 2015 at 9:51 PM
It occurs to me that my second solution is not guaranteed to work. Because std::transform does not guarantees the order in which it transforms the elements. It should use std::for_each instead.
By fisherro on November 2, 2015 at 9:59 PM
package reversestring;
public class ReverseString {
static String input = “a!b3c”;
public static void main(String[] args) {
int stringLength = input.length();
int currentAlphaindex = 0;
char currentChar = ‘a’;
String letters = “”;
String output = “”;
int replacementCount = 0;
char[] alpha = new char[stringLength];
int[] alphaIndex = new int[stringLength];
char[] fullText = new char[stringLength];
for (int i = 0; i = 0; i–){
letters = letters + alpha[i];
letters = letters.trim();
}
for(int i = 0; i = 0)){
fullText[alphaIndex[i]] = letters.charAt(replacementCount);
replacementCount++;
}
output = output + fullText[i];
}
System.out.println(“input: ” + input + “\noutput: ” + output);
}
}
By Davo on November 3, 2015 at 7:21 AM
Sorry guys, I stuffed the indentation on that one.
By Davo on November 3, 2015 at 7:27 AM
attempt number 2
package reversestring; public class ReverseString { static String input = "a!b3c"; public static void main(String[] args) { int stringLength = input.length(); int currentAlphaindex = 0; char currentChar = 'a'; String letters = ""; String output = ""; int replacementCount = 0; char[] alpha = new char[stringLength]; int[] alphaIndex = new int[stringLength]; char[] fullText = new char[stringLength]; for (int i = 0; i < stringLength; i++){ currentChar = input.charAt(i); fullText[i] = currentChar; alphaIndex[i] = -1; if(Character.isLetter(currentChar)){ alpha[currentAlphaindex] = currentChar; alphaIndex[currentAlphaindex] = i; currentAlphaindex++; } } for (int i = (stringLength - 1); i >= 0; i--){ letters = letters + alpha[i]; letters = letters.trim(); } for(int i = 0; i < stringLength; i++){ if((alphaIndex[i] >= 0)){ fullText[alphaIndex[i]] = letters.charAt(replacementCount); replacementCount++; } output = output + fullText[i]; } System.out.println("input: " + input + "\noutput: " + output); } }By Davo on November 3, 2015 at 7:38 AM
@fisherro: Thanks. I liked that possible use too. Incidentally, I think my iterator operator++ and operator– should return a *this reference rather than a new iterator (and I don’t think the template template parameter is necessary for the inner container).
I wonder if we could define an inner container that iterates over the contents of a UTF-8 string.
By matthew on November 3, 2015 at 11:35 AM
Reblogged this on anutech.
By spencerwilliams1988 on November 3, 2015 at 12:41 PM
@matthew
A UTF-8 iterator might be tricky. My first instinct is to use std::string as the value_type. But the specification wants an iterator’s operator* to return a reference. (And operator-> requires returning a pointer.) Maybe it could be faked with a proxy object?
I think using char32_t has the same issue.
A string_view might work, though. It can point directly to the original bytes.
By fisherro on November 3, 2015 at 3:25 PM
@matthew
Here’s a rough first pass of an iterator adapter for walking the characters in a UTF-8 string. It would be better as a container adapter. Well…probably a lot about it could be better. ^_^
http://codepad.org/qNmEkqgy
By fisherro on November 5, 2015 at 3:27 AM
Yes, looks tricky wrapping up UTF-8 in an iterable class. I was musing on the idea of dealing with UTF-8 in-place, and came up with this. It uses the well-known trick for reversing a sequence of blocks in memory by reversing each block individually, then the whole sequence. Seems a waste of electrons to do the full reverse when the outer blocks are the same size so we deal with that specially:
#include <string.h> #include <wchar.h> #include <wctype.h> #include <locale.h> #include <iostream> #include <vector> #include <algorithm> // Reverse from p to q, inclusive of q. void reverse(char *p, char *q) { while(p < q) std::swap(*p++,*q--); } // Swap p-q with r-s, excluding q and s void swap2(char *p, char *q, char *r, char *s) { // q-p == s-r while(p < q) std::swap(*p++,*r++); } // Same, when blocks are different sizes void swap3(char *p, char *q, char *r, char *s) { // q-p != s-r reverse(p,q-1); reverse(q,r-1); reverse(r,s-1); reverse(p,s-1); } int main(int argc, char *argv[]) { setlocale(LC_CTYPE, ""); char *s = argv[1]; std::vector<char*> chars; std::vector<int> alphas; mbstate_t mbstate = mbstate_t(); int len = strlen(s)+1; while (true) { chars.push_back(s); wchar_t wc; ssize_t nbytes = mbrtowc(&wc, s, len, &mbstate); if (nbytes <= 0) break; // No error check! alphas.push_back(iswalpha(wc)); s += nbytes; len -= nbytes; } int p = 0, q = alphas.size()-1; while (p < q) { if (!alphas[p]) p++; else if (!alphas[q]) q--; else { int diff = (chars[q+1]-chars[q])-(chars[p+1]-chars[p]); if (diff == 0) { swap2(chars[p],chars[p+1],chars[q],chars[q+1]); } else { swap3(chars[p],chars[p+1],chars[q],chars[q+1]); for (int i = p+1; i <= q; i++) chars[i] += diff; } std::cout << argv[1] << "\n"; p++; q--; } } }The output is quite pretty:
By matthew on November 5, 2015 at 11:01 PM
Probably doesn’t deal with combining characters properly though…
By matthew on November 5, 2015 at 11:08 PM