Skip to content

Instantly share code, notes, and snippets.

@jin-x

jin-x/look-and-say-hugemem_slow.cpp

Last active June 6, 2021 09:50
Show Gist options
  • Save jin-x/bdf534cff7aff77ad47a00325638a6a1 to your computer and use it in GitHub Desktop.
Save jin-x/bdf534cff7aff77ad47a00325638a6a1 to your computer and use it in GitHub Desktop.
Download ZIP
@jinxonik / UniLecs #209
Raw
look-and-say-hugemem_slow.cpp
// Реализация алгоритма "Посмотри-и-скажи" (Look-and-Say).
// Вариант, итерационно формирующий результирующее значение (строку цифр). Цифры хранятся в виде 2-х битов на цифру.
// Самый медленный алгоритм, требующий наиболее значительного кол-ва памяти (119 Гб для N = 100, 8.4 Гб для N = 90).
// Хочу отметить, что дополнительные расчёты, связанные с хранением чисел в формате 2-х битов на цифру
// компенсируются меньшим кол-вом обращений к памяти, в результате чего скорость данного алгоритма почти не
// отличается от алгоритма, использующего 1 байт на цифру, однако он значительно менее требователен к памяти.
// Результат (в отличие от look-and-say.cpp) формируется лишь на последней итерации.
// В реализации используется один массив, работающий по принципу двунаправленного чтения и записи.
// Чередуются два способа чтения и записи: [<--r <==w] и [w==> r-->].
// Способ 1: чтение данных, располагающихся в начале массива, с конца (справа налево), запись - с конца массива
// (так же слева направо).
// Способ 2: чтение данных, располагающихся в конце массива, с начала (слева направо), запись - с начала массива
// (так же слева направо).
// Т.е. в обоих случаях чтение производится не с края, а из середины (условно) массива. Запись же производится с края.
// Т.к. записываемых данных больше, чем читаемых, в обоих случаях операция записи (позиция записи) является догоняющей
// по отношению к операции чтения (к позиции чтения). Окончательно запись догоняет чтение лишь на последней итерации,
// т.к. под массив изначально выделяется столько памяти, сколько нужно для формирования финальной последовательности.
#include <iostream>
#include <vector>
#include <string>
#include <chrono>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::vector;
using std::string;
using Clock = std::chrono::steady_clock;
static size_t STR_LENGTH[100] = {
1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78, 102, 134, 176, 226, 302, 408, 528, 678, 904,
1182, 1540, 2012, 2606, 3410, 4462, 5808, 7586, 9898, 12884, 16774, 21890, 28528, 37158, 48410,
63138, 82350, 107312, 139984, 182376, 237746, 310036, 403966, 526646, 686646, 894810, 1166642,
1520986, 1982710, 2584304, 3369156, 4391702, 5724486, 7462860, 9727930, 12680852, 16530884,
21549544, 28091184, 36619162, 47736936, 62226614, 81117366, 105745224, 137842560, 179691598,
234241786, 305351794, 398049970, 518891358, 676414798, 881752750, 1149440192, 1498380104,
1953245418, 2546222700, 3319186080, 4326816254, 5640348764, 7352630884, 9584715106, 12494412020,
16287462624, 21231903676, 27677468012, 36079732206, 47032657188, 61310766500, 79923316046,
104186199146, 135814773100, 177045063068, 230791944956, 300854953626, 392187941864, 511247092564
};
// Класс для работы с двунаправленным последовательным чтением и записью массива маленьких чисел размером L бит
template <unsigned char L>
class BiDirTinyUIntStream
{
private:
using ValueType = size_t;
const int val_in_elem = sizeof(ValueType) * CHAR_BIT / L;
const int hi_val_start_bit = (val_in_elem - 1) * L;
const ValueType value_mask = (1 << L) - 1;
vector<ValueType> data;
bool forward; // направление вперёд?
ValueType val_get, val_put; // последний прочитанный/записываемый элемент вектора (кэш)
size_t idx_get, idx_put; // индексы для чтения/записи следующего значения
int shift_get, shift_put; // сдвиг для чтения/записи следующего значения
// Перейти на следующую позицию для чтения
void move_get() {
if (forward) {
if (shift_get == hi_val_start_bit) {
++idx_get;
shift_get = 0;
} else {
shift_get += L;
}
} else {
if (shift_get == 0) {
--idx_get;
shift_get = hi_val_start_bit;
} else {
shift_get -= L;
}
}
}
// Перейти на следующую позицию для записи
void move_put() {
if (forward) {
if (shift_put == hi_val_start_bit) {
++idx_put;
shift_put = 0;
} else {
shift_put += L;
}
} else {
if (shift_put == 0) {
--idx_put;
shift_put = hi_val_start_bit;
} else {
shift_put -= L;
}
}
}
public:
BiDirTinyUIntStream(const size_t size) : forward(true), val_put(0), idx_get(0), idx_put(0), shift_get(0), shift_put(0) {
data.resize((size + val_in_elem - 1) / val_in_elem);
};
// Прочитать следующее значение
unsigned char get() {
int limit = forward ? 0 : hi_val_start_bit;
unsigned char n;
if (shift_get == limit) {
val_get = data[idx_get];
}
n = (val_get >> shift_get) & value_mask;
move_get();
return n;
}
// Записать следующее значение
void put(const unsigned char n) {
val_put = val_put | static_cast<ValueType>(n) << shift_put;
int limit = forward ? hi_val_start_bit : 0;
if (shift_put == limit) {
data[idx_put] = val_put;
val_put = 0;
}
move_put();
}
// Записать значение в массив при необходимости
void flush() {
int limit = forward ? 0 : hi_val_start_bit;
if (shift_put != limit) {
data[idx_put] = val_put;
}
}
// Следующая итерация чтения/записи (записанное становится читаемым)
void turn() {
flush();
forward = !forward;
val_get = val_put;
idx_get = idx_put;
shift_get = shift_put;
val_put = 0;
idx_put = forward ? 0 : data.size() - 1;
shift_put = forward ? 0 : hi_val_start_bit;
move_get();
}
// Направление чтения/записи вперёд?
bool get_forward() {
return forward;
}
// Перемотать в начало
void restart() {
flush();
forward = true;
idx_get = 0;
shift_get = 0;
val_put = 0;
idx_put = 0;
shift_put = 0;
}
}; // BiDirTinyUIntStream
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
string output_cache;
void output_flush()
{
cout << output_cache;
output_cache.clear();
}
void output(const char ch)
{
if (output_cache.length() == 65536) { output_flush(); }
output_cache.push_back(ch);
}
int main()
{
cerr << "N = 100 requires ~ 119 GiB of memory.\n"
"N = 95 requires ~ 31.6 GiB of memory.\n"
"N = 90 requires ~ 8.4 GiB of memory.\n"
"N = 85 requires ~ 2.23 GiB of memory.\n"
"N = 80 requires ~ 607 MiB of memory.\n"
"N = 75 requires ~ 161 MiB of memory.\n"
"N = 70 requires ~ 43 MiB of memory.\n\n"
"Please enter N (1..100): ";
int last_n;
cin >> last_n;
if (last_n < 1 || last_n > 100) {
cerr << "Wrong value is entered!" << endl;
return 1;
}
cerr << endl;
auto clock_start = Clock::now();
size_t str_length = STR_LENGTH[last_n-1];
BiDirTinyUIntStream<2> stream(str_length);
stream.put(1);
size_t length = 1;
for (int idx = 1; idx < last_n; ++idx) {
if (idx >= 10) {
cerr << "\rComputing: " << idx+1 << "...";
}
length = 0;
stream.turn();
unsigned char prev = stream.get();
unsigned char count = 1;
for (size_t i = 1, limit = STR_LENGTH[idx-1]; i < limit; ++i) {
unsigned char n = stream.get();
if (n != prev) {
if (stream.get_forward()) {
stream.put(count);
stream.put(prev);
} else {
stream.put(prev);
stream.put(count);
}
length += 2;
prev = n;
count = 0;
}
++count;
}
if (stream.get_forward()) {
stream.put(count);
stream.put(prev);
}
else {
stream.put(prev);
stream.put(count);
}
length += 2;
}
auto clock_end = Clock::now();
double elapsed_time = std::chrono::duration_cast<std::chrono::duration<double>>(clock_end - clock_start).count();
stream.turn();
if (!stream.get_forward()) { stream.restart(); }
cerr << '\r';
bool show_result = true;
if (length > 10000) {
string s;
cerr << "Result length is too large, output it (Y/N)? [N]: ";
cin.ignore();
getline(cin, s);
show_result = (tolower(s[0]) == 'y');
if (show_result) { cerr << endl; }
}
if (show_result) {
cerr << "Wait...\r";
for (size_t i = 0; i < length; ++i) {
output(stream.get()+'0');
}
output_flush();
if (length < 7) { cerr << " "; }
cerr << endl;
}
cerr << "\nLength: " << length;
if (length == str_length) {
cerr << " (OK";
} else {
cerr << " (WRONG, must be " << str_length;
}
cerr << "), elapsed time: " << std::fixed << elapsed_time << " sec" << endl;
return 0;
} // main
Raw
look-and-say-largemem.cpp
// Реализация алгоритма "Посмотри-и-скажи" (Look-and-Say) на основе данных, приведённых в статье по ссылке:
// http://www.nathanieljohnston.com/2010/10/a-derivation-of-conways-degree-71-look-and-say-polynomial/
// Вариант, формирующий массив кодов последовательностей seq_info.
// Самый быстрый алгоритм, но требующий значительного кол-ва памяти (47.6 Гб для N = 100, 3.36 Гб для N = 90).
// Результат (в отличие от look-and-say.cpp) формируется лишь на последней итерации.
// В реализации используется один массив, работающий по принципу двунаправленного чтения и записи.
// Чередуются два способа чтения и записи: [<--r <==w] и [w==> r-->].
// Способ 1: чтение данных, располагающихся в начале массива, с конца (справа налево), запись - с конца массива
// (так же слева направо).
// Способ 2: чтение данных, располагающихся в конце массива, с начала (слева направо), запись - с начала массива
// (так же слева направо).
// Т.е. в обоих случаях чтение производится не с края, а из середины (условно) массива. Запись же производится с края.
// Т.к. записываемых данных больше, чем читаемых, в обоих случаях операция записи (позиция записи) является догоняющей
// по отношению к операции чтения (к позиции чтения). Окончательно запись догоняет чтение лишь на последней итерации,
// т.к. под массив изначально выделяется столько памяти, сколько нужно для формирования финальной последовательности.
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <chrono>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::vector;
using std::string;
using Clock = std::chrono::steady_clock;
static size_t SEQ_LENGTH[99] = {
1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 5, 6, 9, 10, 18, 23, 34, 43, 52, 66, 96, 120, 153, 197, 256, 345, 449, 585, 757,
974, 1277, 1676, 2171, 2855, 3702, 4835, 6328, 8258, 10723, 14009, 18193, 23780, 30972, 40361, 52625, 68641, 89445,
116688, 152067, 198168, 258279, 336683, 439049, 572148, 745988, 972479, 1267684, 1652460, 2154678, 2807942, 3660684,
4771718, 6220421, 8108476, 10571095, 13779272, 17963034, 23415911, 30525289, 39790850, 51870815, 67617481, 88143015,
114902733, 149784977, 195256048, 254531241, 331804768, 432526861, 563838678, 735002239, 958133160, 1248994781,
1628172961, 2122434181, 2766772879, 3606695469, 4701614292, 6128903040, 7989519477, 10414938116, 13576672034,
17698246898, 23071036025, 30074852712, 39204928981, 51106669271
};
struct SeqInfo
{
string str;
vector<uint8_t> subseq;
};
const SeqInfo seq_info[99] = {
{"1", {1}},
{"11", {2}},
{"21", {3}},
{"1211", {4}},
{"111221", {5}},
{"312211", {6}},
{"13112221", {30, 45}},
{"1112", {69}},
{"1112133", {70, 68}},
{"111213322112", {71}},
{"111213322113", {72}},
{"1113", {74}},
{"11131", {75}},
{"111311222112", {90, 61}},
{"111312", {76}},
{"11131221", {77}},
{"1113122112", {82}},
{"1113122113", {83}},
{"11131221131112", {88}},
{"111312211312", {84}},
{"11131221131211", {85}},
{"111312211312113211", {86}},
{"111312211312113221133211322112211213322112", {87, 35, 97}},
{"111312211312113221133211322112211213322113", {87, 35, 96}},
{"11131221131211322113322112", {87, 36}},
{"11131221133112", {81, 35, 98}},
{"1113122113322113111221131221", {81, 38}},
{"11131221222112", {78}},
{"111312212221121123222112", {79}},
{"111312212221121123222113", {80}},
{"11132", {89}},
{"1113222", {92}},
{"1113222112", {93}},
{"1113222113", {94}},
{"11133112", {95, 98}},
{"12", {7}},
{"123222112", {9}},
{"123222113", {10}},
{"12322211331222113112211", {8, 67, 35, 91}},
{"13", {11}},
{"131112", {34}},
{"13112221133211322112211213322112", {30, 39, 67, 35, 97}},
{"13112221133211322112211213322113", {30, 39, 67, 35, 96}},
{"13122112", {13}},
{"132", {14}},
{"13211", {15}},
{"132112", {16}},
{"1321122112", {27}},
{"132112211213322112", {28}},
{"132112211213322113", {29}},
{"132113", {17}},
{"1321131112", {25}},
{"13211312", {18}},
{"1321132", {19}},
{"13211321", {20}},
{"132113212221", {21}},
{"13211321222113222112", {24}},
{"1321132122211322212221121123222112", {22}},
{"1321132122211322212221121123222113", {23}},
{"13211322211312113211", {26}},
{"1321133112", {12, 67, 35, 98}},
{"1322112", {32}},
{"1322113", {33}},
{"13221133112", {31, 35, 98}},
{"1322113312211", {31, 35, 73}},
{"132211331222113112211", {31, 35, 91}},
{"13221133122211332", {31, 35, 74, 67, 35, 95}},
{"22", {67}},
{"3", {39}},
{"3112", {46}},
{"3112112", {47}},
{"31121123222112", {48}},
{"31121123222113", {49}},
{"3112221", {44, 45}},
{"3113", {50}},
{"311311", {54}},
{"31131112", {60}},
{"3113112211", {55}},
{"3113112211322112", {56}},
{"3113112211322112211213322112", {57}},
{"3113112211322112211213322113", {58}},
{"311311222", {53, 44}},
{"311311222112", {53, 61}},
{"311311222113", {53, 62}},
{"3113112221131112", {53, 63}},
{"311311222113111221", {53, 64}},
{"311311222113111221131221", {53, 65}},
{"31131122211311122113222", {53, 66}},
{"3113112221133112", {53, 39, 67, 35, 98}},
{"311312", {51}},
{"31132", {52}},
{"311322113212221", {59}},
{"311332", {44, 35, 95}},
{"3113322112", {44, 36}},
{"3113322113", {44, 37}},
{"312", {40}},
{"312211322212221121123222113", {42}},
{"312211322212221121123222112", {41}},
{"32112", {43}}
};
string output_cache;
void output_flush()
{
cout << output_cache;
output_cache.clear();
}
void output(const string& s)
{
if (output_cache.length() + s.length() > 65536) { output_flush(); }
output_cache.append(s);
}
int main()
{
for (int i = 100; i >= 70; i -= 5) {
double mib = SEQ_LENGTH[i-2] / 1048576.0;
cerr << std::fixed << std::setprecision(2);
if (mib < 1024) {
cerr << "N = " << i << " requires ~ " << mib << " MiB of memory.\n";
} else {
cerr << "N = " << i << " requires ~ " << mib / 1024.0 << " GiB of memory.\n";
}
}
cerr << "\nPlease enter N (2..100): ";
int last_n;
cin >> last_n;
if (last_n < 2 || last_n > 100) {
cerr << "Wrong value is entered!" << endl;
return 1;
}
cerr << endl;
auto clock_start = Clock::now();
size_t seq_length = SEQ_LENGTH[last_n-2];
vector<uint8_t> seq(seq_length);
size_t length = 1;
size_t idx_from = 0;
size_t idx_to = seq_length - 1;
ssize_t dir = -1;
for (int n = 2; n < last_n; ++n) {
size_t count = length;
length = 0;
for (size_t i = 0; i < count; ++i) {
auto& subseq = seq_info[seq[idx_from]].subseq;
size_t size = subseq.size();
size_t idx = (dir > 0) ? 0 : size - 1;
for (size_t j = 0; j < size; ++j) {
seq[idx_to] = subseq[idx];
idx_to += dir;
idx += dir;
}
idx_from += dir;
length += size;
}
dir = - dir;
idx_from = idx_to + dir;
idx_to = (dir > 0) ? 0 : seq_length - 1;
if (n >= 9) {
cerr << "\rComputing: " << n + 1 << "...";
}
}
if (dir < 0) { idx_from -= length - 1; }
size_t str_len = 0;
for (size_t i = 0; i < length; ++i) {
auto& subseq = seq_info[seq[i]].subseq;
size_t count = subseq.size();
for (size_t j = 0; j < count; ++j) {
auto& str = seq_info[subseq[j]].str;
str_len += str.length();
}
}
auto clock_end = Clock::now();
double elapsed_time = std::chrono::duration_cast<std::chrono::duration<double>>(clock_end - clock_start).count();
cerr << '\r';
bool show_result = true;
if (length > 1000) {
string s;
cerr << "Result length is too large, output it (Y/N)? [N]: ";
cin.ignore();
getline(cin, s);
show_result = (tolower(s[0]) == 'y');
if (show_result) { cerr << endl; }
}
if (show_result) {
cerr << "Wait...\r";
for (size_t i = 0; i < length; ++i) {
auto& subseq = seq_info[seq[i]].subseq;
size_t count = subseq.size();
for (size_t j = 0; j < count; ++j) {
auto& str = seq_info[subseq[j]].str;
output(str);
}
}
output_flush();
if (length < 7) { cerr << " "; }
cerr << endl;
}
cerr << "\nLength: " << str_len;
if (length == seq_length) {
cerr << " (OK)";
} else {
cerr << " (WRONG)";
}
cerr << ", elapsed time: " << std::fixed << elapsed_time << " sec" << endl;
return 0;
} // main
Raw
look-and-say-regex.cpp
// Реализация алгоритма "Посмотри-и-скажи" (Look-and-Say) с помощью регулярных выражений (работает очень медленно).
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <regex>
#include <chrono>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::vector;
using std::string;
using Clock = std::chrono::steady_clock;
int main()
{
cerr << "\nPlease enter N (1..100): ";
int n;
cin >> n;
if (n < 1 || n > 100) {
cerr << "Wrong value is entered!" << endl;
return 1;
}
auto clock_start = Clock::now();
std::regex rx("(.)\\1*");
string prev_result;
string result = "1";
for (int i = 2; i <= n; ++i) {
prev_result = std::move(result);
for (auto it = std::sregex_iterator { prev_result.begin(), prev_result.end(), rx }, it_end = std::sregex_iterator {};
it != it_end;
++it)
{
auto s = it->str();
result.push_back('0' + s.length());
result.push_back(s[0]);
}
}
auto clock_end = Clock::now();
double elapsed_time = std::chrono::duration_cast<std::chrono::duration<double>>(clock_end - clock_start).count();
bool show_result = true;
if (result.length() > 100) {
string s;
cerr << "\nResult length is too large, output it (Y/N)? [N]: ";
cin.ignore();
getline(cin, s);
show_result = (tolower(s[0]) == 'y');
}
if (show_result) {
cerr << '\n';
cerr << result;
cerr << '\n';
}
cerr << "\nResult length: " << result.length() << ", elapsed time: " << std::fixed << elapsed_time << " sec" << endl;
return 0;
} // main
Raw
look-and-say-simple.cpp
// Реализация алгоритма "Посмотри-и-скажи" (Look-and-Say) простым алгоритмом: подсчётом кол-ва повторений в цикле.
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <chrono>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::vector;
using std::string;
using Clock = std::chrono::steady_clock;
int main()
{
cerr << "\nPlease enter N (1..100): ";
int n;
cin >> n;
if (n < 1 || n > 100) {
cerr << "Wrong value is entered!" << endl;
return 1;
}
auto clock_start = Clock::now();
string prev_result;
string result = "1";
for (int i = 2; i <= n; ++i) {
prev_result = std::move(result);
char prev_ch = prev_result[0];
char count = '1';
for (auto it = std::next(prev_result.begin()); it != std::next(prev_result.end()); ++it) {
char ch = *it;
if (ch != prev_ch) {
result.push_back(count);
result.push_back(prev_ch);
prev_ch = ch;
count = '0';
}
++count;
}
}
auto clock_end = Clock::now();
double elapsed_time = std::chrono::duration_cast<std::chrono::duration<double>>(clock_end - clock_start).count();
bool show_result = true;
if (result.length() > 100) {
string s;
cerr << "\nResult length is too large, output it (Y/N)? [N]: ";
cin.ignore();
getline(cin, s);
show_result = (tolower(s[0]) == 'y');
}
if (show_result) {
cerr << '\n';
cerr << result;
cerr << '\n';
}
cerr << "\nResult length: " << result.length() << ", elapsed time: " << std::fixed << elapsed_time << " sec" << endl;
return 0;
} // main
Raw
look-and-say.cpp
// Реализация алгоритма "Посмотри-и-скажи" (Look-and-Say) на основе данных, приведённых в статье по ссылке:
// http://www.nathanieljohnston.com/2010/10/a-derivation-of-conways-degree-71-look-and-say-polynomial/
// Рекурсивный вариант решения (немного более медленный, чем look-and-say-hugemem.cpp, но совершенно нетребовательный к памяти).
// Результат формируется постепенно, т.е. сначала готовы первые несколько цифр, затем ещё несколько и т.д.
// Расчёт результата для N = 100 (а это полтриллиона цифр) без вывода на экран на моём Intel Core i5-2500K занял чуть меньше 22 минут.
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <chrono>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::vector;
using std::string;
class LookAndSay
{
private:
struct SeqInfo
{
string str;
vector<uint8_t> subseq;
}; // SeqInfo
const SeqInfo seq_info[99] = {
{"1", {1}},
{"11", {2}},
{"21", {3}},
{"1211", {4}},
{"111221", {5}},
{"312211", {6}},
{"13112221", {30, 45}},
{"1112", {69}},
{"1112133", {70, 68}},
{"111213322112", {71}},
{"111213322113", {72}},
{"1113", {74}},
{"11131", {75}},
{"111311222112", {90, 61}},
{"111312", {76}},
{"11131221", {77}},
{"1113122112", {82}},
{"1113122113", {83}},
{"11131221131112", {88}},
{"111312211312", {84}},
{"11131221131211", {85}},
{"111312211312113211", {86}},
{"111312211312113221133211322112211213322112", {87, 35, 97}},
{"111312211312113221133211322112211213322113", {87, 35, 96}},
{"11131221131211322113322112", {87, 36}},
{"11131221133112", {81, 35, 98}},
{"1113122113322113111221131221", {81, 38}},
{"11131221222112", {78}},
{"111312212221121123222112", {79}},
{"111312212221121123222113", {80}},
{"11132", {89}},
{"1113222", {92}},
{"1113222112", {93}},
{"1113222113", {94}},
{"11133112", {95, 98}},
{"12", {7}},
{"123222112", {9}},
{"123222113", {10}},
{"12322211331222113112211", {8, 67, 35, 91}},
{"13", {11}},
{"131112", {34}},
{"13112221133211322112211213322112", {30, 39, 67, 35, 97}},
{"13112221133211322112211213322113", {30, 39, 67, 35, 96}},
{"13122112", {13}},
{"132", {14}},
{"13211", {15}},
{"132112", {16}},
{"1321122112", {27}},
{"132112211213322112", {28}},
{"132112211213322113", {29}},
{"132113", {17}},
{"1321131112", {25}},
{"13211312", {18}},
{"1321132", {19}},
{"13211321", {20}},
{"132113212221", {21}},
{"13211321222113222112", {24}},
{"1321132122211322212221121123222112", {22}},
{"1321132122211322212221121123222113", {23}},
{"13211322211312113211", {26}},
{"1321133112", {12, 67, 35, 98}},
{"1322112", {32}},
{"1322113", {33}},
{"13221133112", {31, 35, 98}},
{"1322113312211", {31, 35, 73}},
{"132211331222113112211", {31, 35, 91}},
{"13221133122211332", {31, 35, 74, 67, 35, 95}},
{"22", {67}},
{"3", {39}},
{"3112", {46}},
{"3112112", {47}},
{"31121123222112", {48}},
{"31121123222113", {49}},
{"3112221", {44, 45}},
{"3113", {50}},
{"311311", {54}},
{"31131112", {60}},
{"3113112211", {55}},
{"3113112211322112", {56}},
{"3113112211322112211213322112", {57}},
{"3113112211322112211213322113", {58}},
{"311311222", {53, 44}},
{"311311222112", {53, 61}},
{"311311222113", {53, 62}},
{"3113112221131112", {53, 63}},
{"311311222113111221", {53, 64}},
{"311311222113111221131221", {53, 65}},
{"31131122211311122113222", {53, 66}},
{"3113112221133112", {53, 39, 67, 35, 98}},
{"311312", {51}},
{"31132", {52}},
{"311322113212221", {59}},
{"311332", {44, 35, 95}},
{"3113322112", {44, 36}},
{"3113322113", {44, 37}},
{"312", {40}},
{"312211322212221121123222113", {42}},
{"312211322212221121123222112", {41}},
{"32112", {43}}
}; // seq_info
int level; // уровень рекурсии (обратная глубине, 0 - самый глубокий уровень)
size_t seq_length, str_length; // длина последовательностей seq_info и строки (кол-во цифр)
bool output_result; // выводить результат на консоль
size_t ok_str_length, percent_thres, percent_thres_step; // итоговое кол-во цифр результата
const size_t output_cache_size = 65536; // размер кэша для вывода строки
string output_cache; // кэш для вывода строки
// Вывести остаток кэша на консоль.
void output_flush() {
cout << output_cache;
output_cache.clear();
}
// Вывод результата на консоль с использованием кэша.
void output(const string& s) {
if (output_cache.length() + s.length() > output_cache_size) { output_flush(); }
output_cache.append(s);
}
// Основная функция вычисления.
void calc_recursive(const vector<uint8_t>& seq);
public:
// Запуск вычисления последовательности "посмотри-и-скажи".
// output_result - выводить результат в cout, ok_str_length - итоговое кол-во цифр результата для вывода процента
// выполнения в cerr (если output_result == false и ok_str_length != 0).
void calc(const int n, const bool output_result = true, const size_t ok_str_length = 0);
// Возвращает кол-во цифр (длину строки) результата.
size_t get_str_length() {
return str_length;
}
// Возвращает кол-во последовательностей (из списка seq_info) результата.
size_t get_seq_length() {
return seq_length;
}
}; // LookAndSay
void LookAndSay::calc(const int n, const bool output_result, const size_t ok_str_length)
{
seq_length = 0;
str_length = 0;
if (n < 1) { return; }
level = n;
this->output_result = output_result;
this->ok_str_length = ok_str_length;
percent_thres_step = ok_str_length <= (1000000-99) ? 1000000 : (ok_str_length + 99) / 100;
percent_thres = percent_thres_step;
calc_recursive({0}); // запуск с последовательностью, содержащей {0} (т.е. для строки "1")
if (output_result) { output_flush(); }
} // calc
void LookAndSay::calc_recursive(const vector<uint8_t>& seq)
{
--level;
for (auto it = seq.begin(); it != seq.end(); ++it) {
if (level == 0) {
++seq_length;
auto& str = seq_info[*it].str;
str_length += str.length();
if (output_result) {
output(str);
} else if (ok_str_length != 0 && str_length >= percent_thres) {
cerr << '\r' << str_length * 100 / ok_str_length << "%";
while (str_length >= percent_thres) {
percent_thres += percent_thres_step;
}
}
} else {
calc_recursive(seq_info[*it].subseq); // рекурсивный запуск для всех суб-последовательностей
}
}
++level;
} // calc_recursive
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
using Clock = std::chrono::steady_clock;
static size_t SEQ_LENGTH[100] = {
1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 5, 6, 9, 10, 18, 23, 34, 43, 52, 66, 96, 120, 153, 197, 256, 345, 449, 585, 757,
974, 1277, 1676, 2171, 2855, 3702, 4835, 6328, 8258, 10723, 14009, 18193, 23780, 30972, 40361, 52625, 68641, 89445,
116688, 152067, 198168, 258279, 336683, 439049, 572148, 745988, 972479, 1267684, 1652460, 2154678, 2807942, 3660684,
4771718, 6220421, 8108476, 10571095, 13779272, 17963034, 23415911, 30525289, 39790850, 51870815, 67617481, 88143015,
114902733, 149784977, 195256048, 254531241, 331804768, 432526861, 563838678, 735002239, 958133160, 1248994781,
1628172961, 2122434181, 2766772879, 3606695469, 4701614292, 6128903040, 7989519477, 10414938116, 13576672034,
17698246898, 23071036025, 30074852712, 39204928981, 51106669271, 66621435616
};
static size_t STR_LENGTH[] = {
1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78, 102, 134, 176, 226, 302, 408, 528, 678, 904,
1182, 1540, 2012, 2606, 3410, 4462, 5808, 7586, 9898, 12884, 16774, 21890, 28528, 37158, 48410,
63138, 82350, 107312, 139984, 182376, 237746, 310036, 403966, 526646, 686646, 894810, 1166642,
1520986, 1982710, 2584304, 3369156, 4391702, 5724486, 7462860, 9727930, 12680852, 16530884,
21549544, 28091184, 36619162, 47736936, 62226614, 81117366, 105745224, 137842560, 179691598,
234241786, 305351794, 398049970, 518891358, 676414798, 881752750, 1149440192, 1498380104,
1953245418, 2546222700, 3319186080, 4326816254, 5640348764, 7352630884, 9584715106, 12494412020,
16287462624, 21231903676, 27677468012, 36079732206, 47032657188, 61310766500, 79923316046,
104186199146, 135814773100, 177045063068, 230791944956, 300854953626, 392187941864, 511247092564
};
int main()
{
cerr << "\nPlease enter N (1..100): ";
int n;
cin >> n;
if (n < 1 || n > 100) {
cerr << "Wrong value is entered!" << endl;
return 1;
}
bool output_result;
{
string s;
cerr << "\nResult string length = " << STR_LENGTH[n-1] << " bytes, output it (Y/N)? [Y]: ";
cin.ignore();
getline(cin, s);
output_result = (tolower(s[0]) != 'n');
}
cerr << '\n';
if (output_result) {
cerr << "Wait...\r";
} else {
cerr << "0%";
}
size_t ok_len = STR_LENGTH[n-1];
auto clock_start = Clock::now();
LookAndSay las;
las.calc(n, output_result, ok_len);
auto clock_end = Clock::now();
double elapsed_time = std::chrono::duration_cast<std::chrono::duration<double>>(clock_end - clock_start).count();
if (output_result) {
if (las.get_str_length() < 7) { cerr << " "; }
} else {
cerr << "\r100%";
}
cerr << '\n';
cerr << "\nResult length: " << las.get_str_length();
if (las.get_str_length() == ok_len) {
cerr << " (OK";
} else {
cerr << " (WRONG, must be " << ok_len;
}
cerr << ") sequence length: " << las.get_seq_length();
ok_len = SEQ_LENGTH[n-1];
if (las.get_seq_length() == ok_len) {
cerr << " (OK)";
} else {
cerr << " (WRONG, must be " << ok_len;
}
cerr << ", elapsed time: " << std::fixed << elapsed_time << " sec" << endl;
return 0;
} // main
Raw
look-and-say.golf.rb
# https://tio.run/##KypNqvyfZ2ts8D/R1t7Q2kivtKAkXyNPszpRL724NElRQ19DTzPGUEtfs1pFTa84sypVryQ/vlhbxbC29n9BaUmxQuJ/AA
n=30
a=?1;2.upto(n){a.gsub!(/(.)\1*/){$&.size.to_s+$1}} #50 bytes
puts a
Raw
look-and-say.golf2.rb
# https://tio.run/##KypNqvyfZ2ts8D/R1t7Q2kivtKAkXyNPszpRL724NElRQ19DTzPGUEtfs1pJuVpFTa84syq1VklbxbC29n9BaUmxQuJ/AA
n=30
a=?1;2.upto(n){a.gsub!(/(.)\1*/){"#{$&.size}"+$1}} #50 bytes
puts a
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment