Look And Say or Count And Say Sequence

$\mathtt{REFERENCE}$ @ LeetCode

This is a LeetCode Problem. You can find it HERE

Problem Definition

This problem is actually generation of $look-and-say\ sequence$. DESCRIPTION

The count-and-say sequence is the sequence of integers with the first five terms as following:

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221
 
 1 is read off as "one 1" or 11.
 11 is read off as "two 1s" or 21.
 21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.
  

Solution

Then $nth$ sequence is generated using $(n-1)th$ sequence. So the obvious solution would to go on generating sequences starting from $n=1$ for which the $sequence = 1$.

Algorithm to generate a sequence from previous sequence is simple.

1. Traverse through previous sequence character by character.
1. Maintian the count of repeated character.
2. When a new character is encountered, append to result the $count$ and the $character$.
2. Return result.

We will have to repeat this algorithm until the required sequence is generated.

P.S. When I was tyring to solve this problem, I was looking for more efficient solution. More specifially I was looking for a pattern so that I could directly generate the $nth$ sequence without computing the intermediate sequences. As it turns out, there is no such solution. So the process described above is the actual solution to this problem.

Implementation

Following is the implementation in $GoLang$.

Important thing to keep in mind during the implementation is the generation of intermediate strings. Be careful to generate intermediate and final sequence in $\cal{O(n)}$ time.

	func countAndSay(n int) string {
	prev := "1"
	if n == 1 {
	return prev
	}
	for i := 2; i <= n; i++ {
	prev = compute(prev)
	}
	return prev
	}
	func compute(term string) string {
	var sb strings.Builder
	prev := rune(term[0])
	var count int = 0
	for _, v := range term {
	if v == prev {
	count++
	} else {
	fmt.Fprintf(&sb, "%d", count)
	sb.WriteRune(prev)
	prev = v
	count = 1
	}
	}
	fmt.Fprintf(&sb, "%d", count)
	sb.WriteRune(prev)
	return sb.String()
	}

view raw look-and-say.go hosted with ❤ by GitHub

Complexity

Method countAndSay() runs for $\cal{O(n)}$ time $n$ being the $nth$ sequence number.

Method compute() which computes current sequence using previous sequence, runs for $\cal{O(m)}$ time where $m$ is number of characters in previous sequence.

Assuming $m=n$, The Time Complexity of this solution will be $\cal{O(n^2)}$.

---

---

---

String in GoLang

$\mathtt{REFERENCE}$ @ Blog.GoLang.Org

• The BLOG explains how slices work in Go
• This post is more or less summary of Go string
• Efficient use of string requires understanding not only how they work, but also
  1. the difference between a byte, a character and a rune
  2. the difference between Unicode and UTF-8
  3. the difference between a string and a string literal
  4. and other even more subtle distinctions

"When I index a Go string at position n, why don't I get the nth character?" As you'll see, this question leads us to many details about how text works in the modern world."

An excellent introduction to some of these issues, independent of Go, is Joel Spolsky's famous blog post, The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!).

What is string?

1. In Go, a string is in effect a read-only slice of bytes.
2. It's important to state right up front that a string holds arbitrary bytes. It not required to hold Unicode text, UTF-8 text or any other predefined format. As far as the content of a string is concerned, it is exactly equivalent to a slice of bytes

Code Points, Characters and Runes

1. As mentioned above, a string holds bytes.
2. The idea of $Character$ is a little hard to define. The Unicode standard uses the term $Code Point$ to refer to the item represented by a single value. The code point U+2318, with the hexadecimal value 2318, represents the symbol ⌘. The concept of $Character$ in computing is ambiguous or at least confusing.
3. $Code Point$ is a bit of a mouthful, so Go introduces a shorter term for the concept: $rune$. It means exactly the same as $Code Point$ with one interesting addition. The Go language defines the word rune as an alias for the type int32, so programs can be clear when an integer value represents a code point. Moreover, what you might think of as a character constant is called a rune constant in Go. The type and value of the expression '⌘' is rune with integer value 0x2318.

Range Loops

1. With a regular $for$ loop, we get bytes of the string
2. A $for\ range$ loop, by contrast, decodes one UTF-8-encoded $rune$ on each iteration. Each time around the loop is the starting position of the current rune, measured in bytes and the $Code\ Point$ is its value.

---

---

---

Print given String in ZigZag Fashion

Problem Definition

Given a string and a number of lines $k$, print the string in zigzag form.

In zigzag, characters are printed out diagonally from top left to bottom right until reaching the $kth$ line, then back up to top right, and so on.

For example, given the sentence "thisisazigzag" and k = 4, you should print:

t     a     g
 h   s z   a
  i i   i z
   s     g

Solution

The solution to this problem would be to construct $k$ lines and print them.

Key Problem

Construction of each of the line is the key part of this problem. Each line would consist necessary characters from the $input\ string$ separated by required number of $spaces$. To construct each line we need to identify characters belonging to the line and number of spaces to be inserted after/before each of the characters.

Basic Algorithm

To construct each line,

1. Insert necessary number of spaces in the beginning of the line
2. Identify next character that belongs to this line and append to it
3. Append necessary number of spaces
4. Go to step 2, if there are more characters that belong to this line, otherwise print the line and move on to next line

Identify Size of spaces and Next Belonging Character

Assuming $0\ index$ based line numbers.

1. For $ith\ line$, number of spaces that starts the line $=\ i$
2. Index (say $index$) of first character that belong to $ith\ line = i$
3. Number of spaces that follows after a character depends upon whether we are moving $up\ or\ down$. For simplicity we can assume that at character on first line $i = 0$, we are always moving $down$, while for the last line $i = k-1$, we are always moving $up$. For other lines we will be alternatively moving $up$ and $down$ starting from moving down because initially we are moving down.

             If we are moving up,
                gapSize = 2 * i - 1
   
             Else if we are moving down,
                j = k - i - 1
                gapSize = 2 * j - 1
           

   
4. Index of next character will be $index = index + gapSize + 1$

Implementation

Following is the implementation as described above.

	import java.util.Scanner;
	public class ZigZag {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String input = "I am Lord Voldemort. Lord Voldemort is my past, my present and my future!!!"; //sc.next();
	System.out.print("Enter value of K: ");
	int K = sc.nextInt();
	System.out.println();
	for (int i = 0; i < K; i++) {
	StringBuilder sb = new StringBuilder();
	sb.append(new String(new char[i]).replace('\0', ' ')); // logic may be changed to create string of spaces
	int index = i;
	boolean up = i == K - 1; // for all lines except last, we start by moving down
	while(index < input.length()) {
	sb.append(input.charAt(index)); // append char
	int gapSize; // compute and append spaces
	if (up) {
	gapSize = 2 * i - 1;
	} else {
	int j = K - i - 1;
	gapSize = 2 * j - 1;
	}
	sb.append(new String(new char[gapSize]).replace('\0', ' ')); // logic may be changed to create string of spaces
	index += gapSize + 1; // index of next char for current line
	// set direction for next character
	if (i == 0) { // for top line always consider we are moving down
	up = false;
	} else if (i == K - 1) { // for last line always consider we are moving up
	up = true;
	} else { // for middle lines we alaternatively move down and up
	up = !up;
	}
	}
	System.out.println(sb.toString());
	}
	}
	}

view raw ZigZag.java hosted with ❤ by GitHub

Complexity

Ignoring the time complexity to construct string of empty spaces, the time complexity of this implementation is $O(n)$ because we go through each of the characters in the input string only once.

---

---

---