Puzzles

Below are various puzzles and games.

Number Puzzles
1. Primality Test
Array Puzzles
1. Rain Trapping
String Puzzles

Number Puzzles

Primality Test

Given a positive integer ${n,}$ write an algorithm that returns true if ${n}$ is prime, and false otherwise.

A naive solution is to iterate up to ${n.}$ This would get the job done, but it runs on ${\bigTheta{n}}$ time. We can bring that down to ${\bigTheta{\sqrt{n}}}$ time by relying on the fact that the largest divisor of an integer ${n}$ (say some integer ${d}$ ), will always be ${d^2.}$ In other words, we only need to check for divisors up to ${\sqrt{n}.}$

primality-test

Input: An integer ${n.}$
Output: ${1}$ if ${n \in \primes,}$ ${0}$ otherwise.

if ${n \lt 2}$ return ${0}$
else
1. init ${\let{i}{2}}$
2. while ${i^2 \le n}$ do
  1. if ${n \rem i = 0}$ return ${0}$
  2. else ${\df{increment } i}$
  3. goto ${\line{3}}$
return ${1}$

Note that we use the square of the divisor rather than ${\sqrt{n}.}$ Square roots are fairly nasty objects — both in real analysis and on computers — causing problems on the comparison operators because of floating point arithmetic.

Array Puzzles

Rain Trapping

Given ${n}$ non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

function f(height:number[]) {
	const L = height.length;
	let left = 0;
	let right = L-1;
	let leftmax = height[left];
	let rightmax = height[right];
	let result = 0;
	while (left < right) {
		if (leftmax < rightmax) {
			left++;
			leftmax = leftmax > height[left] ? leftmax : height[left];
			result += leftmax-height[left]
		} else {
			right--;
			rightmax = rightmax > height[right] ? rightmax : height[right];
			result += rightmax - height[right];
		}
	}
	return result;
}

String Puzzles

For the string puzzles, unless otherwise stated, characters are mapped to ASCII.

Decompress

Given a string of the form ${nS,}$ where ${n}$ is an integer and ${S}$ is a string, write an algorithm that returns the decompressed form of the string — the string ${S}$ repeated ${n}$ times. For example, the string ${2c}$ results in ${cc.}$ The string ${4a2b}$ results in ${aaaabb.}$ We assume the strings are well-formed.

The algorithm below is one possible approach. The idea is to have one pointer ${i}$ behind another pointer ${j.}$ We use ${j}$ to move through the string ${S.}$ If the character ${S\ix{j}}$ is a numeral (represented by the ${\df{is-digit}}$ function below), we we increment ${j.}$ Otherwise, we enter an innerloop that concatenates the string from ${i}$ to ${j.}$

decompress

Input: A string ${S.}$
Output: An uncompressed string ${S.}$

${\let{i}{0}}$
${\let{j}{0}}$
${\let{result}{\df{new empty string}}}$
while ${j \lt \len S}$
1. if ${\df{is-digit}(S \ix{j})}$ then ${\df{increment }j}$
2. else
  1. ${\let{n}{\df{cast int}}~S.\df{slice}(i,j)}$
  2. ${\let{k}{0}}$
  3. while ${k \lt n}$
    1. ${result \inc S \ix{j}}$
  4. ${\df{increment~}j}$
  5. ${\let{i}{j}}$
return ${result}$

For example, suppose the string is ${2a3b11a.}$ Initially, both ${i}$ and ${j}$ are on the first character:

\begin{array}{c:c:c:c:c:c:c} j & ~ & ~ & ~ & ~ & ~ & ~ \\ \hdashline 2 & a & 3 & b & 1 & 1 & a \\ \hdashline i & ~ & ~ & ~ & ~ & ~ & ~ \\ \end{array} ~~~~~~ j = 0

This is a numeral, so ${j}$ moves forward:

\begin{array}{c:c:c:c:c:c:c} ~ & j & ~ & ~ & ~ & ~ & ~ \\ \hdashline 2 & a & 3 & b & 1 & 1 & a \\ \hdashline i & ~ & ~ & ~ & ~ & ~ & ~ \\ \end{array} ~~~~~~ j = 1

In doing so, ${j}$ is no longer on a numeral, so we take the slice from ${i}$ to ${j.}$ That's the numeral ${2,}$ so we cast it to an integer, then loop up to that cast. At each iteration, we concatenate the the character ${j}$ is currently pointing to. At the end of that loop, we increment ${j}$ and update ${i}$ to ${j.}$

\begin{array}{c:c:c:c:c:c:c} ~ & j & ~ & ~ & ~ & ~ & ~ \\ \hdashline 2 & a & 3 & b & 1 & 1 & a \\ \hdashline ~ & i & ~ & ~ & ~ & ~ & ~ \\ \end{array} ~~~~~~ j = 2 ~~~~~~ aa

At the next iteration, we have ${j}$ on another numeral:

\begin{array}{c:c:c:c:c:c:c} ~ & ~ & j & ~ & ~ & ~ & ~ \\ \hdashline 2 & a & 3 & b & 1 & 1 & a \\ \hdashline ~ & i & ~ & ~ & ~ & ~ & ~ \\ \end{array} ~~~~~~ j = 2 ~~~~~~ aa

The previous process repeats:

\begin{array}{c:c:c:c:c:c:c} ~ & ~ & ~ & j & ~ & ~ & ~ \\ \hdashline 2 & a & 3 & b & 1 & 1 & a \\ \hdashline ~ & ~ & i & ~ & ~ & ~ & ~ \\ \end{array} ~~~~~~ j = 3 ~~~~~~ aabbb

resulting in the state:

\begin{array}{c:c:c:c:c:c:c} ~ & ~ & ~ & j & ~ & ~ & ~ \\ \hdashline 2 & a & 3 & b & 1 & 1 & a \\ \hdashline ~ & ~ & ~ & i & ~ & ~ & ~ \\ \end{array} ~~~~~~ j = 3 ~~~~~~ aabbb

Now, when ${j}$ encounters another numeral followed by another numeral, we simply keep incrementing:

\begin{array}{c:c:c:c:c:c:c} ~ & ~ & ~ & ~ & ~ & j & ~ \\ \hdashline 2 & a & 3 & b & 1 & 1 & a \\ \hdashline ~ & ~ & ~ & i & ~ & ~ & ~ \\ \end{array} ~~~~~~ j = 5 ~~~~~~ aabbb

Leaving us with:

\begin{array}{c:c:c:c:c:c:c} ~ & ~ & ~ & ~ & ~ & ~ & j \\ \hdashline 2 & a & 3 & b & 1 & 1 & a \\ \hdashline ~ & ~ & ~ & ~ & i & ~ & ~ \\ \end{array} ~~~~~~ j = 6 ~~~~~~ aabbbaaaaaaaaaaa

In the worst case, this algorithm runs on ${\bigO{n \by m},}$ where ${n}$ is the length of the string, and ${m}$ is the length of an expansion. The time complexity may be worse, however, depending on how the ${\df{slice}}$ and ${\inc}$ (concatenation) functions are implemented. In a language like JavaScript, those operations run on ${\bigO{n}.}$ These bottlenecks can be avoided by pushing the characters to the array, then joining all of the array elements after the loops. This problem is not encountered in languages like C++.

Compress

Given a string ${S,}$ write an algorithm that replaces 2 or more consecutive terms of the same character into the number of occurrences followed by the character. For example, ${aaab \to 3ab.}$

This implementation uses the same approach as the uncompress problem. Note the use of the do-while loop. Unlike the uncompress algorithm, this approach takes ${\bigTheta{n}.}$ There's an inner-while loop, but that loop is purely there to make the code more concise. The ${j}$ pointer increments so long as ${j}$ and ${i}$ point to terms of the same character.

compress

Input: A string ${S.}$
Output: A compressed string, ${result.}$

${\let{L}{\len S}}$
${\let{i}{0},}$ ${\let{j}{0}}$
${\let{result}{\df{new empty string}}}$
while ${(j \lt L)}$
1. do ${\let{j}{j+1}}$
  1. while ${S\ix{i} = S\ix{j}}$
2. if ${j-i \gt 1}$ then
  1. ${result \df{ concat } S \ix{i}}$
return ${result}$

Anagrams

Given two strings ${S_1}$ and ${S_2,}$ write an algorithm that returns true (or 1) if ${S_1}$ and ${S_2}$ are anagrams, and false (or 0) otherwise. Anagrams are strings that contain the same characters, disregarding order.

an incorrect, tempting solution would be to iterate over the first string, accumulating the sum of each element's character code. Then iterate over the second string, subtracting each element's character code from the sum. If two strings have the same set of characters (an anagram), the result should be 0, so we return 1, otherwise we return 0. Before any of these operations occur, we immediately return if the two strings do not have the same length (strings of unequal lengths are not anagrams by definition):

anagram

Input: a string ${s_1}$ and a string ${s_2.}$
Output: Boolean.

if ${\len s_1 \neq \len s_2}$ return ${\df{false}}$
init
1. ${\let{sum}{0}}$
2. ${\let{i}{0}}$
if ${i \lt \len s_1}$ start loop body
1. ${\let{sum}{sum + (\df{cast int})s_1\ix{i}}}$
2. ${\let{sum}{sum - (\df{cast int})s_2\ix{i}}}$
3. ${\let{i}{i+1}}$
goto ${\line{4}}$ end loop body
return ${sum=0}$

The temptation here is strong: We have a linear time complexity and constant memory complexity. Except there's a case it doesn't cover: ${ac}$ and ${bb.}$ If the characters were encoded via ASCII, we would have ${97+99=196}$ and ${98+98=196.}$ This yields ${196-196=0,}$ in which case we return true. Clearly, however, the two strings are not anagrams.

A correct approach would be to use a hash table:

anagram

Input: a string ${s_1}$ and a string ${s_2.}$
Output: Boolean.

if ${\len s_1 \neq \len s_2}$ return ${\df{false}}$
init
1. ${\let{H}{\df{new hash-table}}}$
2. ${\let{i}{0}}$
if ${i \lt \len{s_1}}$ start loop 1 body
1. if ${s_1 \ix{i} \in H}$ then ${H \push (s_1 \ix{i}, 0)}$
2. ${{\df{increment}}~{H \ix{s_1 \ix{0}}}}$
3. ${\df{increment}~i}$
goto ${\line{4}}$ end loop 1 body
${\let{i}{0}}$
if ${i \lt \len{s_2}}$ start loop 2 body
1. if ${(H \ix{s_2 \ix{i}} = \nil)}$ then return ${\df{false}}$
2. else ${\df{decrement} ~ H \ix{s_2 \ix{i}}}$
3. ${\df{increment}~i}$
goto ${\line{10}}$ end loop 2 body
for each ${x \in H}$ do start loop 3 body
1. if ${x \neq 0}$ return ${\df{false}}$
return ${\df{true}}$ end loop 3 body

Here, we have a linear time complexity, ${\bigO{n + m},}$ where ${n}$ is the length of either string, and ${m}$ is the number of entries in the hash table. This comes at the cost of ${\bigO{n}}$ memory complexity. The time complexity also depends on the hash table implementation.

Most Frequent Character

Given a string ${S,}$ write an algorithm that returns the most frequent character of the string. If there are ties, return the earliest character.

A hash table would work here.

most frequent character

Input: a string ${S.}$
Output: a string ${result,}$ the most frequent character.

init
1. ${\let{L}{\len{S}}}$
2. ${\let{H}{\df{new hash-table}}}$
3. ${\let{i}{0}}$
4. ${\let{result}{S \ix{0}}}$
if ${i \lt L}$ then begin loop body
1. if ${S \ix{i} \in H}$ then
  1. ${\df{increment }H \ix{S \ix{i}}}$
2. else ${H \push (S \ix{i}, 1)}$
goto ${\line{5}}$ end loop body
init ${\let{max}{0}}$
for each ${(key,value) \in H}$ do
1. if ${value \gt max}$ then
  1. ${\let{max}{value}}$
  2. ${\let{result}{key}}$
return ${result}$

This algorithm has a running time of ${\bigO{n+m},}$ where ${n}$ is the length of the string and ${m}$ is the number of entries in the hash table. Given that ${m \le n,}$ we have ${\bigO{n}.}$ Like other hash table solutions, a complete time complexity analysis requires an examining the hash table's implementation. The memory complexity here is ${\bigO{m},}$ where ${m}$ is the size of the hash table.

Roman Numeral Conversion

Write an algorithm that converts a given Roman numeral into its Hindu-arabic equivalent.

romnum

Let ${S}$ be a finite, non-empty string of length ${n}$ over the alphabet ${\Sigma = \set{\tx{I}, \tx{V}, \tx{X}, \tx{L}, \tx{C}, \tx{D}, \tx{M}}.}$ Further, let ${M}$ be a mapping from ${\Sigma \to z \in \uint^+,}$ defined as

M = \lset{ \eqs{ & (\tx{I},1),(\tx{IV},4),(\tx{V},5) \\ & (\tx{IX},9),(\tx{X},10),(\tx{XL},40) \\ & (\tx{L},50),(\tx{XC},90),(\tx{C},100) \\ & (\tx{CD},400),(\tx{D},500),(\tx{CM},900) \\ & (\tx{M},1000) } }.

For each character ${s_i \in S = (s_0, s_1, \ldots, s_{n-1})}$ with ${n \in \NN}$ , the function ${\df{romnum}}$ returns the sum

\dsum{i=0}{n-1} M(s_i).

${\var ~ \let{out}{0}}$
${\var ~ \let{i}{\len (S) - 1}}$
while ${i \ge 0}$ do
1. ${\df{switch} ~~ \df{true}}$
  1. ${\df{case} ~~ S \ix{i} = {\tx{M}}}$
    1. ${\if ~ S \ix{i-1} = {\tx{C}} ~ \nc}$ ${\let{i'}{i - 1},~~\let{out'}{out + 900}}$
    2. ${\else ~ \let{out'}{out + 1000}}$
  2. ${\df{case} ~~ S\ix{i} = {\tx{D}}}$
    1. ${\if ~ S \ix{i-1} = {\tx{C}} ~ \nc}$ ${\let{i'}{i - 1},~~\let{out'}{out + 400}}$
    2. ${\else ~ \let{out'}{out + 500}}$
  3. ${\df{case} ~~ S\ix{i} = {\tx{C}}}$
    1. ${\if ~ S \ix{i-1} = {\tx{X}} ~ \nc}$ ${\let{i'}{i - 1},~~\let{out'}{out + 90}}$
    2. ${\else ~ \let{out'}{out + 100}}$
  4. ${\df{case} ~~ S \ix{i} = {\tx{L}}}$
    1. ${\if ~ S \ix{i-1} = {\tx{X}} ~ \nc}$ ${\let{i'}{i - 1},~~\let{out'}{out + 40}}$
    2. ${\else ~ \let{out'}{out + 50}}$
  5. ${\df{case} ~~ S \ix{i} = \st{\tx{X}}}$
    1. ${\if ~ S \ix{i-1} = {\tx{I}} ~ \nc}$ ${\let{i'}{i - 1},~~\let{out'}{out + 9}}$
    2. ${\else ~ \let{out'}{out + 10}}$
  6. ${\df{case} ~~ S \ix{i - 1} = {\tx{V}}}$
    1. ${\if ~ S \ix{i-1} = {\tx{I}} ~ \nc}$ ${\let{i'}{i - 1},~~\let{out'}{out + 4}}$
    2. ${\else ~ \let{out'}{out + 5}}$
  7. ${\df{default} ~ \let{out'}{out + 1}}$
return ${out}$

\ax{ \set{3} & \to & \set{7} & \to & \set{1} & \to & \set{4} \\ \uarr & ~ & ~ & ~ & ~ & ~ & \darr \\ \set{2} & ~ & ~ & ~ & ~ & ~ & \set{43} \\ \uarr & ~ & ~ & ~ & ~ & ~ & \darr \\ \set{5} & \gets & \set{8} & \gets & \set{19} & \gets & \set{21} \\ }