Look and Say sequence problem [reviewed]

Problem

Implement the pattern function producing the following pattern:

  0: 1
  1: 11
  2: 21
  3: 1211
  4: 111221
  5: 312211

 Your function should generate the string sequences shown above, given the input as a integer.

  For example, input = 4, output should be 111221

We first need to understand what "Look and Say sequence" to solve this problem.

Starting with 1, your algorithm "11", which is read "one one".
The first "1" is the number of "1" shown.
"11" produce "21", equivalent to "two one".

Now, you need to write the algorithm counting the occurrence of the same number while traversing from the left to right and store the result as "count integer" in a separate string.

We just need to perform the step above as many as the given input until returning the result.

Here is the algorithm running in O(NM), where N is the given input, M is the longest look-and-say string processed.

#include <iostream>
#include <string>
using namespace std;
string look_and_say(int count)
{
string result = "1";
int lap = 0;
while (lap < count)
{
int count;
string value="";
char cur;
for (int i = 0; i < result.length(); i++)
{
if (i == 0)
{
cur = result[i];
count = 1;
}
else if (result[i] == cur)
{
count++;
}
else {
value += string(to_string(count));
value.push_back(cur);
cur = result[i];
count = 1;
}
if (i == result.length() - 1)
{
value += string(to_string(count));
value.push_back(cur);
}
}
cout << value << endl;
result = value;
lap++;
}
return result;
}
int main()
{
int count = 6;
cout << " look and say for 6 " << look_and_say(6) << endl;
return 1;
}


Practice statistics

14:12 min to write up the code with logical flaw
2:18 min to fix up the typo
9:53: to debug the logical flaws through compilation.


UPDATE(2019-07-26): Solve the problem again in python.
Was able to finish the code in 17 mins. No typos this time !!

Here is a solution in python.

class LookAndSay:
def find_sequence(self, target):
current = '1'
for i in range(0, target):
next = self.look_and_say(current)
current = next
return current
def look_and_say(self, input):
result =''
prev = None
count = 0
for i in input:
if prev == None:
prev = i
count = 1
elif prev != i:
result += ("{}{}".format(count, prev))
prev = i
count = 1
else:
count += 1
if prev != None:
result += ("{}{}".format(count, prev))
return result
l = LookAndSay()
input = 4
print("input = {} output = {}".format(input, l.find_sequence(input)))
input = 5
print("input = {} output = {}".format(input, l.find_sequence(input)))


Practice statistics
10:00: to come up with algorithm for look and say and write the code half way

7:00: to write the code. (No bug !! Good job !!)


Comments

Popular posts from this blog

Planting flowers with no adjacent flower plots

Find the shorted path from the vertex 0 for given list of vertices.