@jinxonik / UniLecs #272

restore_digits1a.cpp

/***********************************************************************************************************************

Задача UniLecs №272: https://telegra.ph/Anons-272-Vosstanovit-cifry-iz-peremeshannyh-bukv-06-04

Алгоритм №1A решения задачи на восстановление цифр из перемешанных букв.
Вариант работы со счётчиками букв.
________________________________________________________________________________________________________________________

Разберём запись числительных от 0 до 9 на английском языке и посчитаем кол-во букв в строке, содержащей их все. Получим
следующую статистику:
+---------------+---------+
|     буквы     | частота |
+---------------+---------+
| g, u, w, x, z |    1    |
| f, h, s, v    |    2    |
| r, t          |    3    |
| i, n, o       |    4    |
| e             |    9    |
+---------------+---------+

Очевидно, что кол-во букв g, u, w, x и z в исходной строке будет означать кол-во цифр, от которых образованы содержащие
эти буквы числительные. Самое забавное, что это чётные цифры: Zero(0), tWo(2), foUr(4), siX(6) и eiGht(8). Посчитаем
кол-во этих цифр и удалим такое же кол-во других букв, которые станут "уникальными" после такого удаления (точнее, их
оставшееся кол-во будет соответствовать кол-ву цифр, от которых образованы числительные, содержащие эти буквы). В словах
Four, Six и eigHt есть буквы, которые встречаются 2 раза (f, s и h), их мы и удалим. Это позволит нам найти числительные
и кол-во соответствующих цифр tHree(3), Five(5) и Seven(7). У нас остаются нераспознанными только цифры 1 и 9. Несложно
заметить, что числительные этих цифр различаются только двумя буквами: o (One) и i (nIne), но таких букв аж по 4! :-/
Чтобы найти эти цифры, нам нужно при работе с чётными цифрами и цифрами 3, 5, 7 удалить буквы o и i по 3 раза. В каких
словах это можно сделать? А вот в каких: zerO, twO, fOur, sIx, eIght и fIve. Т.о., по кол-ву букв o и i мы определим
кол-во цифр 1 и 9.

Чтобы алгоритм работал быстро, нам нужно избежать постоянную работу со строкой. Для этого в начале мы посчитаем кол-во
каждой из букв в строке и запишем результат в массив, с которым и будем работать дальше.

***********************************************************************************************************************/

#include <string>

std::string restore_digits(const std::string& s)
{
  size_t digits[10] {};  // counters for digits

  // Count number of each letter
  size_t letters[26] {};  // counters for letters
  for (const char ch : s) {
    if (ch >= 'a' && ch <= 'z') {
      ++letters[ch - 'a'];
    } else if (ch >= 'A' && ch <= 'Z') {
      ++letters[ch - 'A'];
    }
  } // for (ch:s)

  // Find digits with unique letters
  const char* unique_seq   = "zwuxghfsoi";  // Zero(0) tWo(2) foUr(4) siX(6) eiGht(8) tHree(3) Five(5) Seven(7) One(1), nIne(9)
  const char* decrease_seq = "qqfshqiqqq"   // (zero two) Four Six eigHt (three) fIve (seven one nine); "q" is a stub char for numerals in brackets
                             "oooiiqqqqq";  // zerO twO fOur sIx eIght (three five seven one nine)
  const uint8_t digit_order[10] = {0,2,4,6,8,3,5,7,1,9};  // order of digits
  for (size_t i = 0; i < 10; ++i) {
    const size_t let_idx = unique_seq[i] - 'a';
    size_t& count = letters[let_idx];
    digits[digit_order[i]] = count;
    // Remove some number of letters that present in found numerals to make them unique for other numerals
    for (size_t k = 0; k < 2; ++k) {
      letters[decrease_seq[i + k*10] - 'a'] -= count;  // remove letter
    }
    count = 0;  // letters[let] = 0
  } // for (i)

  // Generate result
  std::string result = "";
  for (size_t i = 0; i < 10; ++i) {
    result.insert(result.end(), digits[i], static_cast<char>(i+'0'));
  }
  return result;
} // restore_digits

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

using std::cout;
using std::endl;
using std::string;
using std::vector;

void generate_and_test(const size_t min, const size_t max, const bool show_result)
{
  if (!show_result) { cout << "Testing very long string"; }

  const char* const numerals[10] {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
  std::mt19937 rng{std::random_device{}()};
  std::uniform_int_distribution<size_t> random{min, max};
  string source, correct;
  for (size_t i = 0; i < 10; ++i) {
    const size_t n = random(rng);
    for (size_t j = 0; j < n; ++j) {
      source += numerals[i];
    }
    correct.insert(correct.end(), n, static_cast<char>(i+'0'));
  }
  std::shuffle(source.begin(), source.end(), rng);
  if (!show_result) { cout << " (" << source.length() << " letters / " << correct.length() << " digits)..."; }

  using Clock = std::conditional_t<std::chrono::high_resolution_clock::is_steady, std::chrono::high_resolution_clock, std::chrono::steady_clock>;
  auto start_time = Clock::now();
  const string result = restore_digits(source);
  auto stop_time = Clock::now();
  double duration = std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1>>>(stop_time - start_time).count();

  if (show_result) { cout << source << " --> " << result << " :"; }
  cout << " [" << std::fixed << duration << " sec] ";
  if (result == correct) {
    cout << "success! ;)";
  } else {
    cout << "EPIC FAIL! :`(";
  }
  cout << endl;
} // test

int main()
{
  string source = "owoztneoer", correct = "012";
  string result = restore_digits(source);
  cout << source << " --> " << result << " : " << (result == correct ? "" : "NOT " ) << "correct!" << endl;

  source = "fviefuro", correct = "45";
  result = restore_digits(source);
  cout << source << " --> " << result << " : " << (result == correct ? "" : "NOT " ) << "correct!" << endl;

  generate_and_test(0, 5, true);
  generate_and_test(1, 1000000, false);
} // main

restore_digits1a_faster.cpp

/***********************************************************************************************************************

Задача UniLecs №272: https://telegra.ph/Anons-272-Vosstanovit-cifry-iz-peremeshannyh-bukv-06-04

Алгоритм №1A решения задачи на восстановление цифр из перемешанных букв.
Вариант работы со счётчиками букв. Ускоренная модификация.
________________________________________________________________________________________________________________________

Разберём запись числительных от 0 до 9 на английском языке и посчитаем кол-во букв в строке, содержащей их все. Получим
следующую статистику:
+---------------+---------+
|     буквы     | частота |
+---------------+---------+
| g, u, w, x, z |    1    |
| f, h, s, v    |    2    |
| r, t          |    3    |
| i, n, o       |    4    |
| e             |    9    |
+---------------+---------+

Очевидно, что кол-во букв g, u, w, x и z в исходной строке будет означать кол-во цифр, от которых образованы содержащие
эти буквы числительные. Самое забавное, что это чётные цифры: Zero(0), tWo(2), foUr(4), siX(6) и eiGht(8). Посчитаем
кол-во этих цифр и удалим такое же кол-во других букв, которые станут "уникальными" после такого удаления (точнее, их
оставшееся кол-во будет соответствовать кол-ву цифр, от которых образованы числительные, содержащие эти буквы). В словах
Four, Six и eigHt есть буквы, которые встречаются 2 раза (f, s и h), их мы и удалим. Это позволит нам найти числительные
и кол-во соответствующих цифр tHree(3), Five(5) и Seven(7). У нас остаются нераспознанными только цифры 1 и 9. Несложно
заметить, что числительные этих цифр различаются только двумя буквами: o (One) и i (nIne), но таких букв аж по 4! :-/
Чтобы найти эти цифры, нам нужно при работе с чётными цифрами и цифрами 3, 5, 7 удалить буквы o и i по 3 раза. В каких
словах это можно сделать? А вот в каких: zerO, twO, fOur, sIx, eIght и fIve. Т.о., по кол-ву букв o и i мы определим
кол-во цифр 1 и 9.

Чтобы алгоритм работал быстро, нам нужно избежать постоянную работу со строкой. Для этого в начале мы посчитаем кол-во
каждой из букв в строке и запишем результат в массив, с которым и будем работать дальше.

***********************************************************************************************************************/

#include <string>

std::string restore_digits(const std::string& s)
{
  // Count number of each letter
  size_t letters[32] {};  // counters for letters
  for (const char ch : s) {
      ++letters[ch & 0x1F];
  } // for (ch:s)

  // Calculate digit counts
  size_t digits[10] {
    letters['z' & 0x1F],  // 0
    letters['o' & 0x1F],  // 1
    letters['w' & 0x1F],  // 2
    letters['h' & 0x1F],  // 3
    letters['u' & 0x1F],  // 4
    letters['f' & 0x1F],  // 5
    letters['x' & 0x1F],  // 6
    letters['s' & 0x1F],  // 7
    letters['g' & 0x1F],  // 8
    letters['i' & 0x1F]   // 9
  };
  digits[1] -= digits[0] + digits[2] + digits[4];
  digits[3] -= digits[8];
  digits[5] -= digits[4];
  digits[7] -= digits[6];
  digits[9] -= digits[5] + digits[6] + digits[8];

  // Generate result
  std::string result = "";
  for (size_t i = 0; i < 10; ++i) {
    result.insert(result.end(), digits[i], static_cast<char>(i+'0'));
  }
  return result;
} // restore_digits

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

using std::cout;
using std::endl;
using std::string;
using std::vector;

void generate_and_test(const size_t min, const size_t max, const bool show_result)
{
  if (!show_result) { cout << "Testing very long string"; }

  const char* const numerals[10] {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
  std::mt19937 rng{std::random_device{}()};
  std::uniform_int_distribution<size_t> random{min, max};
  string source, correct;
  for (size_t i = 0; i < 10; ++i) {
    const size_t n = random(rng);
    for (size_t j = 0; j < n; ++j) {
      source += numerals[i];
    }
    correct.insert(correct.end(), n, static_cast<char>(i+'0'));
  }
  std::shuffle(source.begin(), source.end(), rng);
  if (!show_result) { cout << " (" << source.length() << " letters / " << correct.length() << " digits)..."; }

  using Clock = std::conditional_t<std::chrono::high_resolution_clock::is_steady, std::chrono::high_resolution_clock, std::chrono::steady_clock>;
  auto start_time = Clock::now();
  const string result = restore_digits(source);
  auto stop_time = Clock::now();
  double duration = std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1>>>(stop_time - start_time).count();

  if (show_result) { cout << source << " --> " << result << " :"; }
  cout << " [" << std::fixed << duration << " sec] ";
  if (result == correct) {
    cout << "success! ;)";
  } else {
    cout << "EPIC FAIL! :`(";
  }
  cout << endl;
} // test

int main()
{
  string source = "owoztneoer", correct = "012";
  string result = restore_digits(source);
  cout << source << " --> " << result << " : " << (result == correct ? "" : "NOT " ) << "correct!" << endl;

  source = "fviefuro", correct = "45";
  result = restore_digits(source);
  cout << source << " --> " << result << " : " << (result == correct ? "" : "NOT " ) << "correct!" << endl;

  generate_and_test(0, 5, true);
  generate_and_test(1, 1000000, false);
} // main

restore_digits1a_fastest.cpp

/***********************************************************************************************************************

Задача UniLecs №272: https://telegra.ph/Anons-272-Vosstanovit-cifry-iz-peremeshannyh-bukv-06-04

Алгоритм №1A решения задачи на восстановление цифр из перемешанных букв.
Вариант работы со счётчиками букв. Самая быстрая модификация.
________________________________________________________________________________________________________________________

Разберём запись числительных от 0 до 9 на английском языке и посчитаем кол-во букв в строке, содержащей их все. Получим
следующую статистику:
+---------------+---------+
|     буквы     | частота |
+---------------+---------+
| g, u, w, x, z |    1    |
| f, h, s, v    |    2    |
| r, t          |    3    |
| i, n, o       |    4    |
| e             |    9    |
+---------------+---------+

Очевидно, что кол-во букв g, u, w, x и z в исходной строке будет означать кол-во цифр, от которых образованы содержащие
эти буквы числительные. Самое забавное, что это чётные цифры: Zero(0), tWo(2), foUr(4), siX(6) и eiGht(8). Посчитаем
кол-во этих цифр и удалим такое же кол-во других букв, которые станут "уникальными" после такого удаления (точнее, их
оставшееся кол-во будет соответствовать кол-ву цифр, от которых образованы числительные, содержащие эти буквы). В словах
Four, Six и eigHt есть буквы, которые встречаются 2 раза (f, s и h), их мы и удалим. Это позволит нам найти числительные
и кол-во соответствующих цифр tHree(3), Five(5) и Seven(7). У нас остаются нераспознанными только цифры 1 и 9. Несложно
заметить, что числительные этих цифр различаются только двумя буквами: o (One) и i (nIne), но таких букв аж по 4! :-/
Чтобы найти эти цифры, нам нужно при работе с чётными цифрами и цифрами 3, 5, 7 удалить буквы o и i по 3 раза. В каких
словах это можно сделать? А вот в каких: zerO, twO, fOur, sIx, eIght и fIve. Т.о., по кол-ву букв o и i мы определим
кол-во цифр 1 и 9.

Чтобы алгоритм работал быстро, нам нужно избежать постоянную работу со строкой. Для этого в начале мы посчитаем кол-во
каждой из букв в строке и запишем результат в массив, с которым и будем работать дальше.

***********************************************************************************************************************/

#include <string>

std::string restore_digits(const std::string& s)
{
  // Count number of each letter
  size_t letters[256] {};  // counters for letters
  for (const unsigned char ch : s) {
      ++letters[ch];
  } // for (ch:s)

  // Calculate digit counts
  size_t digits[10] {
    letters['z'],  // 0
    letters['o'],  // 1
    letters['w'],  // 2
    letters['h'],  // 3
    letters['u'],  // 4
    letters['f'],  // 5
    letters['x'],  // 6
    letters['s'],  // 7
    letters['g'],  // 8
    letters['i']   // 9
  };
  digits[1] -= digits[0] + digits[2] + digits[4];
  digits[3] -= digits[8];
  digits[5] -= digits[4];
  digits[7] -= digits[6];
  digits[9] -= digits[5] + digits[6] + digits[8];

  // Generate result
  std::string result = "";
  for (size_t i = 0; i < 10; ++i) {
    result.insert(result.end(), digits[i], static_cast<char>(i+'0'));
  }
  return result;
} // restore_digits

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

using std::cout;
using std::endl;
using std::string;
using std::vector;

void generate_and_test(const size_t min, const size_t max, const bool show_result)
{
  if (!show_result) { cout << "Testing very long string"; }

  const char* const numerals[10] {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
  std::mt19937 rng{std::random_device{}()};
  std::uniform_int_distribution<size_t> random{min, max};
  string source, correct;
  for (size_t i = 0; i < 10; ++i) {
    const size_t n = random(rng);
    for (size_t j = 0; j < n; ++j) {
      source += numerals[i];
    }
    correct.insert(correct.end(), n, static_cast<char>(i+'0'));
  }
  std::shuffle(source.begin(), source.end(), rng);
  if (!show_result) { cout << " (" << source.length() << " letters / " << correct.length() << " digits)..."; }

  using Clock = std::conditional_t<std::chrono::high_resolution_clock::is_steady, std::chrono::high_resolution_clock, std::chrono::steady_clock>;
  auto start_time = Clock::now();
  const string result = restore_digits(source);
  auto stop_time = Clock::now();
  double duration = std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1>>>(stop_time - start_time).count();

  if (show_result) { cout << source << " --> " << result << " :"; }
  cout << " [" << std::fixed << duration << " sec] ";
  if (result == correct) {
    cout << "success! ;)";
  } else {
    cout << "EPIC FAIL! :`(";
  }
  cout << endl;
} // test

int main()
{
  string source = "owoztneoer", correct = "012";
  string result = restore_digits(source);
  cout << source << " --> " << result << " : " << (result == correct ? "" : "NOT " ) << "correct!" << endl;

  source = "fviefuro", correct = "45";
  result = restore_digits(source);
  cout << source << " --> " << result << " : " << (result == correct ? "" : "NOT " ) << "correct!" << endl;

  generate_and_test(0, 5, true);
  generate_and_test(1, 1000000, false);
} // main

restore_digits1b.cpp

/***********************************************************************************************************************

Задача UniLecs №272: https://telegra.ph/Anons-272-Vosstanovit-cifry-iz-peremeshannyh-bukv-06-04

Алгоритм №1B решения задачи на восстановление цифр из перемешанных букв.
Вариант с редактированием исходной строки (медленный).
________________________________________________________________________________________________________________________

Разберём запись числительных от 0 до 9 на английском языке и посчитаем кол-во букв в строке, содержащей их все. Получим
следующую статистику:
+---------------+---------+
|     буквы     | частота |
+---------------+---------+
| g, u, w, x, z |    1    |
| f, h, s, v    |    2    |
| r, t          |    3    |
| i, n, o       |    4    |
| e             |    9    |
+---------------+---------+

Очевидно, что кол-во букв g, u, w, x и z в исходной строке будет означать кол-во цифр, от которых образованы содержащие
эти буквы числительные. Самое забавное, что это чётные цифры: Zero(0), tWo(2), foUr(4), siX(6) и eiGht(8). Посчитаем
кол-во этих цифр и удалим (заменим на пробелы) такое же кол-во других букв, которые станут "уникальными" после такого
удаления (точнее, их оставшееся кол-во будет соответствовать кол-ву цифр, от которых образованы числительные, содержащие
эти буквы). В словах Four, Six и eigHt есть буквы, которые встречаются два раза (f, s и h), их мы и удалим (заменим).
Это позволит нам на втором этапе найти числительные и кол-во соответствующих цифр tHree(3), Five(5) и Seven(7). У нас
остаются ненайденными только цифры 1 и 9. Несложно заметить, что числительные этих цифр различаются лишь двумя буквами:
o (One) и i (nIne), но таких букв аж по 4! :-/ Чтобы найти эти цифры, нам нужно при работе с чётными цифрами и цифрами
3, 5, 7 удалить буквы o и i уже по 3 раза. В каких словах это можно сделать? А вот в каких: zerO, twO, fOur, sIx, eIght
(первый этап) и fIve (второй этап). Т.о., на третьем этапе по кол-ву букв o и i мы определяем кол-во цифр 1 и 9.

P.S. Этот алгоритм можно ускорить, посчитав кол-во каждой из букв строки и работая с получившимся массивом, а не проходя
по строке несколько раз. Собственно, этим и отличается алгоритм 1А (который является оптимизацией данного алгоритма).

***********************************************************************************************************************/

#include <string>
#include <vector>

std::string restore_digits(std::string s)
{
  std::vector<size_t> digits(10);  // counters for every digit
  std::string unique_seq[3] = {"zwuxg", "hfs", "oi"};  // Zero(0) tWo(2) foUr(4) siX(6) eiGht(8) (i=0) | tHree(3) Five(5) Seven(7) (i=1) | One(1), nIne(9) (i=2)
  std::string replace_seq[2] = {"oifsh", "i"};  // zerO twO FOur SIx eIgHt (i=0) | fIve (i=1)
  size_t idx_mult[3] = {2, 2, 8}, idx_add[3] = {0, 3, 1};  // multipliers and addends of index

  // Find digits with unique letters
  for (size_t i = 0; i < 3; ++i) {
    for (char& ch : s) {
      const size_t pos = unique_seq[i].find(ch);
      if (pos != std::string::npos) {
        ++digits[pos*idx_mult[i] + idx_add[i]];  // 0,2,4,6,8 (i=0) | 3,5,7 (i=1) | 1,9 (i=2)
      }
    } // for (ch:s)
  
    if (i == 2) { break; }  // no more replaces

    // Remove (replace with space) some number of letters that present in found numerals to make them unique for other numerals
    // replace_count - number of letters in replace_seq which we must remove from string (replace with space)
    std::vector<size_t> replace_count;
    size_t total;
    if (i == 0) {
      replace_count = {digits[0]+digits[2]+digits[4], digits[6]+digits[8], digits[4], digits[6], digits[8]};
      total = digits[0]+digits[2]+digits[4]*2+digits[6]*2+digits[8]*2;  // total number of letters to remove (replace)
    } else {
      replace_count = {digits[5]};
      total = digits[5];
    }
    for (char& ch : s) {
      const size_t pos = replace_seq[i].find(ch);
      if (pos != std::string::npos) {
        if (replace_count[pos] > 0) {
          ch = ' ';  // replace
          --replace_count[pos];
          if (--total == 0) { break; }  // all letters are replaced
        }
      }
    } // for (ch:s)
  } // for (i)

  // Generate result
  s = "";
  for (size_t i = 0; i < 10; ++i) {
    s.insert(s.end(), digits[i], static_cast<char>(i+'0'));
  }
  return s;
} // restore_digits

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>

using std::cout;
using std::endl;
using std::string;
using std::vector;

void generate_and_test(const size_t min, const size_t max, const bool show_result)
{
  if (!show_result) { cout << "Testing very long string"; }

  const char* const numerals[10] {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
  std::mt19937 rng{std::random_device{}()};
  std::uniform_int_distribution<size_t> random{min, max};
  string source, correct;
  for (size_t i = 0; i < 10; ++i) {
    const size_t n = random(rng);
    for (size_t j = 0; j < n; ++j) {
      source += numerals[i];
    }
    correct.insert(correct.end(), n, static_cast<char>(i+'0'));
  }
  std::shuffle(source.begin(), source.end(), rng);
  if (!show_result) { cout << " (" << source.length() << " letters / " << correct.length() << " digits)..."; }

  using Clock = std::conditional_t<std::chrono::high_resolution_clock::is_steady, std::chrono::high_resolution_clock, std::chrono::steady_clock>;
  auto start_time = Clock::now();
  const string result = restore_digits(source);
  auto stop_time = Clock::now();
  double duration = std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1>>>(stop_time - start_time).count();

  if (show_result) { cout << source << " --> " << result << " :"; }
  cout << " [" << std::fixed << duration << " sec] ";
  if (result == correct) {
    cout << "success! ;)";
  } else {
    cout << "EPIC FAIL! :`(";
  }
  cout << endl;
} // test

int main()
{
  string source = "owoztneoer", correct = "012";
  string result = restore_digits(source);
  cout << source << " --> " << result << " : " << (result == correct ? "" : "NOT " ) << "correct!" << endl;

  source = "fviefuro", correct = "45";
  result = restore_digits(source);
  cout << source << " --> " << result << " : " << (result == correct ? "" : "NOT " ) << "correct!" << endl;

  generate_and_test(0, 5, true);
  generate_and_test(1, 1000000, false);
} // main

restore_digits2.cpp

/***********************************************************************************************************************

Задача UniLecs №272: https://telegra.ph/Anons-272-Vosstanovit-cifry-iz-peremeshannyh-bukv-06-04

Алгоритм №2 решения задачи на восстановление цифр из перемешанных букв.
________________________________________________________________________________________________________________________

Посчитаем кол-во каждой из букв в строке и запишем результат в массив letters. Далее пройдёмся по числительным (но не по
порядку, я расскажу об этом ниже) и запишем минимальное значение в letters для каждой из букв числительного в переменную
min_matches. Далее вычтем из letters для каждой из букв числительного это значение, как бы удаляя это кол-во каждой из
этих букв. Значение min_matches будет кол-вом цифр соответствующего числительного в результирующей строке.

Чтобы алгоритм сработал, необходимо перебирать числительные не по порядку. Сначала нужно пройтись по чётным цифрам, т.к.
каждая из них содержит уникальные буквы (z, w, u, x и g в Zero(0), tWo(2), foUr(4), siX(6) и eiGht(8)), а затем уже по
нечётным.

Этот алгоритм может показаться немного более простым и затратным в сравнении с алгоритмом 1А. Тем не менее, на практике
оба алгоритма работают примерно с одинаковой скоростью.

***********************************************************************************************************************/

#include <string>

std::string restore_digits(const std::string& s)
{
  size_t digits[10] {};   // counters for digits

  // Count number of each letter
  size_t letters[26] {};  // counters for letters
  for (const char ch : s) {
    if (ch >= 'a' && ch <= 'z') {
      ++letters[ch - 'a'];
    } else if (ch >= 'A' && ch <= 'Z') {
      ++letters[ch - 'A'];
    }
  } // for (ch:s)

  // Check numbers
  const char* const numerals[10] {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
  for (size_t k = 0; k < 2; ++k) {
    for (size_t i = k; i < 10; i += 2) {
      size_t min_matches = SIZE_MAX;
      for (const char* ch = numerals[i]; *ch; ++ch) {
        const size_t n = letters[*ch - 'a'];
        if (n < min_matches) { min_matches = n; }
      }
      // Remove some number of letters that present in found numerals to make them unique for other numerals
      for (const char* ch = numerals[i]; *ch; ++ch) {
        letters[*ch - 'a'] -= min_matches;
      }
      digits[i] = min_matches;
    }
  }

  // Generate result
  std::string result = "";
  for (size_t i = 0; i < 10; ++i) {
    result.insert(result.end(), digits[i], static_cast<char>(i+'0'));
  }
  return result;
} // restore_digits

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

using std::cout;
using std::endl;
using std::string;
using std::vector;

void generate_and_test(const size_t min, const size_t max, const bool show_result)
{
  if (!show_result) { cout << "Testing very long string"; }

  const char* const numerals[10] {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
  std::mt19937 rng{std::random_device{}()};
  std::uniform_int_distribution<size_t> random{min, max};
  string source, correct;
  for (size_t i = 0; i < 10; ++i) {
    const size_t n = random(rng);
    for (size_t j = 0; j < n; ++j) {
      source += numerals[i];
    }
    correct.insert(correct.end(), n, static_cast<char>(i+'0'));
  }
  std::shuffle(source.begin(), source.end(), rng);
  if (!show_result) { cout << " (" << source.length() << " letters / " << correct.length() << " digits)..."; }

  using Clock = std::conditional_t<std::chrono::high_resolution_clock::is_steady, std::chrono::high_resolution_clock, std::chrono::steady_clock>;
  auto start_time = Clock::now();
  const string result = restore_digits(source);
  auto stop_time = Clock::now();
  double duration = std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1>>>(stop_time - start_time).count();

  if (show_result) { cout << source << " --> " << result << " :"; }
  cout << " [" << std::fixed << duration << " sec] ";
  if (result == correct) {
    cout << "success! ;)";
  } else {
    cout << "EPIC FAIL! :`(";
  }
  cout << endl;
} // test

int main()
{
  string source = "owoztneoer", correct = "012";
  string result = restore_digits(source);
  cout << source << " --> " << result << " : " << (result == correct ? "" : "NOT " ) << "correct!" << endl;

  source = "fviefuro", correct = "45";
  result = restore_digits(source);
  cout << source << " --> " << result << " : " << (result == correct ? "" : "NOT " ) << "correct!" << endl;

  generate_and_test(0, 5, true);
  generate_and_test(1, 1000000, false);
} // main