Iterators – look and say sequence algorithm

Look and say sequence is fun little exercise.. here is the code

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

std::string looknsay(int num){
  // initialize vector with vector of ints.
  // add default seed value to it [1].
  std::vector<std::vector<int>> look_n_say_seq{{1}};
  // iterate over until the number n is reached.
  for(int n = 0; n <= num; n++){
    auto latest_sequence = look_n_say_seq.back();
    std::vector<int> next_sequence;
   // keep a pair of iterators to move across the latest sequence from vector.
    auto i = latest_sequence.begin();
    auto j = latest_sequence.begin();
    while(i < latest_sequence.end()){
      for(;*i==*j && j < latest_sequence.end();++j){}
      // distance will give the count
      next_sequence.push_back(std::distance(i, j));
      // *i will give the actual number to iterate on
      next_sequence.push_back(*i);
      i = j;
    }
    // insert newly created sequence into the vector.
    look_n_say_seq.push_back(next_sequence);
  }
  auto latest_sequence = look_n_say_seq.back();
 // accumulate - join vector of ints to make string and return
  return std::accumulate(std::next(latest_sequence.begin()), 
                         latest_sequence.end(),
                          std::to_string(*latest_sequence.begin()),
                          [](std::string s, int i){return s += std::to_string(i);});
}
int main(){
  std::cout << looknsay(0) << '\n';
  std::cout << looknsay(1) << '\n'; // 11
  std::cout << looknsay(2) << '\n'; // 21
  std::cout << looknsay(3) << '\n'; // 1211
  std::cout << looknsay(4) << '\n'; // 111221
  std::cout << looknsay(5) << '\n'; // 312211
}

Author: Saurabh Purnaye

Sr. Developer @NYSE @ICE_Markets. Low Latency Trading, Linux, C++, Python, Ruby. pursuing certificate in #QuantFinance and Passed CFA L1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s