Reverse String Ignoring Special Characters
October 30, 2015
Today’s exercise solves a homework problem for some lucky reader:
Given an input string that contains both alphabetic characters and non-alphabetic characters, reverse the alphabetic characters while leaving the non-alphabetic characters in place. For instance, given the input string
a!b3c, return the output stringc!b3a, where the non-alphabetic characters!and3are in their original positions.
Your task is to write a program that reverses a string while leaving non-alphabetic characters in place. 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.
Strangers On A Train
October 27, 2015
In Sloane’s Encyclopedia, sequence A247665 is defined as
a(1) = 2; thereafter a(n) is the smallest number not yet used which is compatible with the condition that a(n) is relatively prime to the next n terms. The sequence begins 2, 3, 4, 5, 7, 9, 8, 11, 13, 17, 19, 23, 15, 29, 14, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, …
The sequence was submitted by Amarnath Murthy and given to Neil Sloane as a birthday present. Sloane calls the sequence “Strangers on a Train” after the psychological thriller novel by Patricia Highsmith and subsequent film by Alfred Hitchcock, because the nth element of the sequence has no factors in common with the next n elements (they are “strangers”).
Your task is to write a program that generates the sequence. 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.
Two Swaps
October 23, 2015
Today we have one of those tricky interview questions that are easy once you know the answer:
You are given an array of three elements, in some random order. You must sort the array into increasing order, but may only use two swaps. How can you do it?
Your task is to write a program that sorts a three-element array with only two swaps. 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.
Longest Sequence Of Consecutive Odd Integers
October 20, 2015
Today’s exercise is to find the longest sequence of consecutive odd integers that add to a given sum. For instance, given the target 160701, the three consecutive odd integers 53565, 53567 and 53569 sum to 160701, but the 391 consecutive odd integers from 21 to 801 also sum to 160701, and are the longest sequence of consecutive odd integers to do so, so they are the correct answer.
Your task is to write a program to find the longest sequence of consecutive odd integers that add to a given sum. 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.
Largest Possible Remainder
October 16, 2015
The result of dividing a number n by a divisor d is a quotient q and a remainder r. Given a fixed n and a divisor d in the range 1 ≤ d < n, find the divisor that produces the largest possible remainder. For instance, given n = 20 and 1 ≤ d < 10, the largest remainder is 6 when the divisor d is 7.
Your task is to write a program that finds the largest possible remainder. 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.
Double Double Words
October 13, 2015
Today’s task is to write a program that reads a file and reports any instances of doubled words, which is a useful program for anyone that does a lot of writing, as I do in this blog.
Your task is to write a program to find doubled words. 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.
Searching For Hypotenuses
October 9, 2015
Hypotenusi?
Your task is to write a program that returns all the numbers less than some limit (think somewhere in the millions or tens of millions) that can be the hypotenuse of a right triangle with integer sides; strive for the minimum possible run time for your program. 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.
The Iron Bar
October 6, 2015
Three physicists recently published an article showing that an inert iron bar is capable of making decisions. They attach the bar between two slot machines, repeatedly play one of the machines, pull the bar toward the machine when it winds and push the bar away from the machine when it loses. After enough plays, the iron bar can decide whether to play one machine or the other in hopes of a better payoff. Then they say “The most important implication that we wish to claim is that the proposed scheme will provide a new perspective for understanding the information-processing principles of certain lower forms of life.” The physicists also claim the iron bar can determine the probabilities of winning on both slot machines even though it only plays one. I’m not sure I understand the article, though I will happily agree that an inert iron bar has more intelligence than the spammers that regularly bedevil my blog.
The iron bar recalls an old-time method for calculating the median of a stream; for instance, consider finding the median of a list of a thousand occurrences of the numbers 1 to 100. Initialize the median to the first number in the list. Then, at each subsequent number, increase the median by 1 if the number is higher than the current median and decrease the median by 1 if the number is lower than the current median. At the end of the list, the approximate median calculated in this way ought not to significantly differ from the actual median. This is essentially the same calculation as that of the iron bar.
Your task is to write a program that calculates approximate medians in the manner of an iron bar. 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.
The Hot Hand
October 2, 2015
A recent article in the Wall Street Journal discusses the “hot hand” paradox. Basketball players especially believe in the hot hand, when making a shot you can suddenly have a hot hand and make several more shots in a row. The Wall Street Journal proposes this experiment:
Toss a coin four times. Write down the percentage of heads on the flips coming immediately after heads. Repeat that process one million times. On average, what is that percentage?
The article claims that the correct percentage is 40%, not the 50% that you would expect from an unbiased coin, and that this is proof that the hot hand exists, even from such a random source as coin flips. If you’re interested, you can read the academic article that the Wall Street Journal account is based on, or see discussion of it at Hacker News.
Your task is to write a program to confirm the 40% figure. 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.
Programming Praxis 