Skip to content

Instantly share code, notes, and snippets.

@Tener
Created September 18, 2011 22:09
Show Gist options
  • Save Tener/1225609 to your computer and use it in GitHub Desktop.
Save Tener/1225609 to your computer and use it in GitHub Desktop.
Look and say in C++, reimplementation of algorithm first written in Haskell
/*
g++ -O3 -mtune=native -march=native -fomit-frame-pointer lookandsay.cpp -o lookandsay.out
time ./lookandsay.out > /dev/null
./lookandsay.out > /dev/null 2,88s user 0,05s system 99% cpu 2,948 total
*/
#include <vector>
#include <iostream>
using namespace std;
inline void render(int i, vector< int > & vec)
{
vector< int >::iterator it;
int sum = 0;
for(it = vec.begin(); *it > 0; it++)
{
cout << *it;
sum += *it;
}
cout << endl;
cerr << "(" << i+1 << "," << sum << ")" << endl;
cout << vec.size() << endl;
}
int main()
{
vector< int > v1;
vector< int > v2;
vector< int >::iterator it;
v1.push_back(1);
v2.push_back(-1);
v2.push_back(-1);
int i;
for(i = 0; i < 59; i++)
{
render(i, v1);
it = v1.begin();
v2.clear();
while(*it > 0)
{
if (*it == *(it+1))
{
if (*(it+1) == *(it+2))
{
v2.push_back(3);
v2.push_back(*it);
it+=3;
}
else
{
v2.push_back(2);
v2.push_back(*it);
it+=2;
}
}
else
{
v2.push_back(1);
v2.push_back(*it);
it+=1;
}
}
v2.push_back(-1);
v2.push_back(-1);
v1.clear();
v1 = v2;
}
render(i, v1);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment