## The Trapped Knight

### February 19, 2019

Over at Numberphile, Neil Sloane discusses a knight moving on an infinite chessboard with squares numbered in a square spiral (note that, starting from 1, the squares on the southeast diagonal are successive squares of odd numbers 1² = 1, 3² = 9, 5² = 25, 7² = 49, and so on):

37 36 35 34 33 32 31 38 17 16 15 14 13 30 39 18 5 4 3 12 29 40 19 6 1 2 11 28 . 41 20 7 8 9 10 27 . 42 21 22 23 24 25 26 . 43 44 45 46 47 48 49 50

The knight starts from square 1 and always moves to the smallest-numbered square not previously visited. Thus, from 1, the knight can move to squares 10, 12, 14, 16, 18, 20, 22 or 24, of which the smallest unvisited square is 10. From 10, the knight can then move to squares 1, 3, 23, 29, 47, 49, 51 or 53; the smallest of those, 1, has already been visited, so the knight moves to square 3. And so on. The beginning of the knight’s tour visits squares 1, 10, 3, 6, 9, 4 and so on (A316667).

Your task is to write a program to determine if the knight’s tour is infinite or if the knight becomes trapped with no remaining unvisited squares; if the knight becomes trapped, determine the length of his tour and the square on which he remains. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Peaks

### February 15, 2019

Given an array of integers, a *peak* is a subarray of minimal length in which the integer values increase and then decrease. For instance, in the array [5,5,4,5,4] there is a peak [4,5,4] and in the array [6,5,4,4,4,4,4,5,6,7,7,7,7,7,6] there is a peak [6,7,7,7,7,7,6]. Note that [4,5,6,7,7,7,7,7,6] shows a pattern of increasing and decreasing values, but it is not minimal because the first two items can be removed and the remaining subarray remains a peak. The array [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8] has two peaks, [4,5,4] and [8,9,9,8].

Your task is to write a program that finds all of the peaks in an array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Consecutive Sums

### February 12, 2019

Given the positive integer 15, there are three ways to take consecutive positive integers that sum to 15: 1+2+3+4+5, 4+5+6 and 7+8.

Your task is to write a program that, given a positive integer, finds all the ways that consecutive positive integers can sum to the target integer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## String Data Type

### February 5, 2019

Different programming languages handle strings differently. In C, for instance, strings are null-terminated arrays of characters, so the \0 character is not permitted in strings; other langauges permit any character in a string. Some languages are limited to ascii, others admit unicode. Some languages allow strings to be mutated, while others make strings immutable. Some languages number the characters in a string starting from 0, others from 1. If you’re porting a program from one language to another, dealing with strings can be a headache. (You can probably guess accurately at the motivation for today’s exercise.)

Today’s exercise calls for you to write a portable string data type that can be easily moved language to another. You are free to define strings as you wish — not everyone will have the same needs. Whatever you decide, you should provide conversions to and from the strings in your native language, as well as some basic operations on strings: determine their length, find the character at a particular position, modify a character if you decide strings should be mutable, extract a substring, concatenate two strings, perhaps others. Make your data type as simple or as elaborate as you wish.

Your task is to write a portable string data type that can be easily moved from one language to another. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Alternating Lists

### February 1, 2019

Today’s exercise is a simple task in list manipulation:

Write a program that takes one or more lists and returns a single list containing the elements of the input lists, taken alternately from the lists. If the lists are of different lengths, continue taking items from the lists that remain.

For instance, given the inputs `(1 2 3 4 5)`

, `(a b c)`

and `(w x y z)`

, the desired output is `(1 a w 2 b x 3 c y 4 z 5)`

.

Your task is to write a program to take items alternately from multiple lists. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Marsaglia’s Mental RNG

### January 29, 2019

We saw an “in-your-head” random number generator in a previous exercise, but I found it hard to operate. Today’s exercise, due to George Marsaglia is a random number generator that even a dummy like me can work in his head:

Choose a two-digit number as a seed. Then form a new two-digit number by adding the ten’s digit and six times the unit digit. For instance, if you start from 23, the sequence is 23 → 20 → 02 → 12 → 13 → 19 → 55 → 35 …. Then the sequence of random digits is the unit digit of each two-digit number. This operation produces the numbers 1 through 58 as seeds; the ten digits each occur six times, except that nine and zero occur five times (because 59 and 60 are not part of the sequence).

Your task is to implement Marsaglia’s mental RNG, and experiment with it to determine its effectiveness. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## First Word

### January 25, 2019

We have a simple exercise today, inspired a co-worker. Where I work, we have a reporting tool that permits a “hook” to the underlying SQL in some places. My co-worker asked me how to write an SQL statement that extracts the first word (a maximal sequence of non-spaces) from the beginning of a string (assume there are no leading spaces). For instance, given the string “abcdefg hijklmnop qrs tuv wxyz” the first word is “abcdefg”. Here’s the SQL expression, wrapped in a `select`

statement, with `&&STR`

representing the string:

select substr('&&STR', 1, instr('&&STR', ' ') - 1) from dual

Your task is to write a program to extract the first word from a string. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Lunar Arithmetic

### January 22, 2019

Over at *Numberphile*, Neil Sloane (yes, *that* Neil Sloane), talks about lunar arithmetic, an “other-worldly” way of doing simple math:

Lunar addition and multiplication work digit by digit, the same as terrestrial addition and multiplication, except that the plus and times tables are unusual. Addition is done by taking the larger of the two digits, so 1 + 3 = 3 and 7 + 4 = 7. Multiplication is done by taking the smaller of the two digits, so 1 * 3 = 1 and 7 * 4 = 4. Thus:

3 5 7 3 5 7 + 6 4 * 6 4 ------- ------- 3 6 7 3 4 4 3 5 6 ------- 3 5 6 4There are no carries. There is no subtraction or division, since the results would not be unique.

Your task is to write programs that perform lunar addition and multiplication. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Extract Number From String

### January 18, 2019

We have another string-handling exercise today:

Given a string containing a number, extract the number from the string. For instance, the strings “-123”, “-123junk”, “junk-123”, “junk-123junk” and “junk-123junk456” should all evaluate to the number -123.

Your task is to write a program to extract a number from a string. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Find The Difference

### January 15, 2019

Today’s question comes from a programming student:

You are given two strings

sandtthat consist only of lower-case letters. Stringtwas created by adding one letter chosen at random to strings, then shuffling the resulting string. Find the letter that was added tot. For instance, the difference between the two strings “abcdef” and “bfxdeac” is the character “x”.

Your task is to write a program to find the random letter that was added to the string. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.