[SPOJ] Problem z zadaniem FLAMASTER

Question

https://pl.spoj.com/problems/FLAMASTE/
Moje rozwiązanie wydaje się być poprawne, lecz sędzia wypisuje "Błędna odpowiedź".
Sprawdzałem wiele razy i działa. Może coś z wyjściem?

std::string strReduce(const std::string& input){
	std::string str;
	int i = 0;
	int count = 0;
	while(i <= (input.length() - 1)){
		
			
		if((i != 0 && i != (input.length() - 1))
			&&
			(input[i] == input[i+1] && input[i]==input[i-1])) {
			
			for(;;count++){
				if(input[i+count] != input[i])
					break;
			}
			
			i += count;
			str.append(std::to_string(count+1));
			count = 0;
		}
		str += input[i];
		i++;
	}
	return str;
}

(Funkcja strReduce jest wywoływana w main)

Comments

(Funkcja strReduce jest wywoływana w main)

spoj lubi zaskakiwać, pokaż całość kodu :P

---

#include <iostream>
#include <string>
std::string strReduce(const std::string& input){
    std::string str;
    int i = 0;
    int count = 0;
    while(i <= (input.length() - 1)){
         
             
        if((i != 0 && i != (input.length() - 1))
            &&
            (input[i] == input[i+1] && input[i]==input[i-1])) {
             
            for(;;count++){
                if(input[i+count] != input[i])
                    break;
            }
             
            i += count;
            str.append(std::to_string(count+1));
            count = 0;
        }
        str += input[i];
        i++;
    }
    return str;
}


int main() {
	int C = 0;
    std::cin >> C;

    for(int = 0; i < C; i++) {
        std::string input;

        std::cin >> input;
        std::cout << strReduce(input) << std::endl;
    } 
	return 0;
}

 

Answer 1

Nieciekawy błąd. Pod koniec wypisujesz '\0', którego nie widać na konsoli, ale spojowi się nie zgadza wynik. Z takim quick-fixem zadziała:

if (i < input.size())
	str += input[i];

A co do kodu to jest brzydki i bliżej mu do C niż C++.

if ((i != 0 && i != (input.length() - 1))
			&&
			(input[i] == input[i + 1] && input[i] == input[i - 1]))

to jest po prostu brzydkie. Sprawdzanie w każdym obiegu pętli czy nie jesteśmy na początku lub końcu.

			for (;; count++) {
				if (input[i + count] != input[i])
					break;
			}

Korzystaj z gotowych algorytmów. Nie pisz wszystkiego samemu. To aż prosi się o wykorzystanie find_if lub input.find_first_not_of.

str.append(std::to_string(count + 1));

Lepiej użyć stringstream:

stringstream out;
...
out << count << input[i];
...
return out.str();

No i zwiększanie iteratora "i" w kilku miejscach sprawia, że bardzo ciężko się ten kod analizuje.

Tak widzę to ja:

std::string my_reduce2(const std::string& str) {
	std::stringstream out{};
	for (auto it = str.begin(); it != str.end();)
	{
		auto next_seq_start = std::find_if(it, str.end(), [it](char c) {return c != *it; });
		auto dist = std::distance(it, next_seq_start);
		if (dist > 2) {
			out << *it << dist;
		}
		else {
			out << std::string(dist, *it);
		}
		it = next_seq_start;
	}
	return out.str();
}

Answer 2

Jako ciekawostka można napisać całą transformacje w jednej linijce:

#include <iostream>
#include <string>
#include <regex>
#include <iterator>
using namespace std;

int main()
{
	std::regex sequence_pattern{ "(.)\\1*" };
	size_t tests{};
	cin >> tests;
	std::string input;
	for (size_t i = 0; i < tests; i++)
	{
		cin >> input;
		std::transform(
			std::sregex_iterator(input.begin(), input.end(), sequence_pattern),
			std::sregex_iterator(),
			std::ostream_iterator<std::string>(std::cout),
			[](auto&& match) -> std::string {
			return match.str().size() > 2 ? match.str()[0] + std::to_string(match.str().size()) : match.str();
		});
		std::cout << std::endl;
	}
}