Geothmetic Meandian
April 13, 2021
In mathematics, the arithmetic geometric mean of two positive real numbers is computed by repeatedly taking half their sum and the square root of their product until the two numbers converge. For instance, the arithmetic geometric mean of 24 and 6 is 13.456171…, with the iterative steps computed as follows:
0 24 6 1 15 12 2 13.5 13.416407864998738175455042 3 13.458203932499369089227521 13.458139030990984877207090 4 13.458171481745176983217305 13.458171481706053858316334 5 13.458171481725615420766820 13.458171481725615420766806
The arithmetic geometric mean was invented by Lagrange and studied by Gauss, and is used today to compute various transcendental functions because it converges so quickly.
In the world of Randall Munroe, the geothmetic meandian of any set of positive numbers is computed by iterating three sequences — the arithmetic mean, the geometric mean, and the median — until they converge. For instance, the geothmetic meandian of the set (1,1,2,3,5) is 2.089, computed as follows:
1 2.4 1.9743504858348200 2 2 2.1247834952782734 2.1161924605448084 2 3 2.0803253186076938 2.0795368194795802 2.1161924605448084 4 2.0920181995440275 2.0919486049152223 2.0803253186076938 5 2.0880973743556477 2.0880901331209600 2.0919486049152223 6 2.0893787041306098 2.0893779142184865 2.0880973743556477 7 2.0889513309015815 2.0889512436159920 2.0893779142184865 8 2.0890934962453533 2.0890934865653277 2.0889513309015815 9 2.0890461045707540 2.0890461034958396 2.0890934865653277
[ I hate the damned new editor at WordPress; I struggle with it every time I post an exercise. I could not figure out how to embed the image from XKCD in this blog post. You can see it here. ]
Your task is to write programs that compute the arithmetic geometric mean and geothmetic meandian. 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.
Greedy Text Justification
March 30, 2021
Today’s exercise would make a good interview question, though I don’t know of anyone doing that; you should answer as if you are standing at a whiteboard explaining your code as you go:
Given a string and a line width, split the string into words (a maximal run of characters excluding spaces) and write the words onto successive lines with spaces added between the words so that each line is the requested width. Words should be added to lines greedily (as many words as will fit) and extra spaces should be assigned to the left of the output string. The last line should not have spaces added, so it may be shorter than the other lines.
For example, the string “This is an example of text justification” is written with a line width of 16 like this:
----+----+----+-
This is an
example of text
justification.
----+----+----+-
Your task is to write a program that greedily justifies text. 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.
Fizzbuzz
March 23, 2021
I’ve seen several recent posts on the beginning-programmer forums about how to solve the fizzbuzz problem, so let’s talk about that today:
Enumerate the numbers from 1 to N by writing “Fizz” if the number is divisible by 3, “Buzz” if the number is divisible by 5, “FizzBuzz” if the number is divisible by both, and the number itself if the number is divisible by neither. For instance, counting from 1 to 25 works like this: 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11. Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz.
FizzBuzz also appears as the first problem in Project Euler, where they characterize the problem like this:
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
Your task is to solve the two versions of the FizzBuzz problem, for all numbers up to N; you can use a simple method, but it is more fun to be a little bit clever. 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.
Bigger To The Right
March 9, 2021
Given a list of integers, calculate a list of integers that contains, at each item of the list, the count of integers in the original list that are greater than the item at the current position of the original list. For example, given the input list (10 12 8 17 3 24 19), the desired output is (4 3 3 2 2 0 0), because at the first item in list, 10, there are four items (12 17 24 19) greater than 10, at the second item in the list, 12, there are three items (17 24 19) greater than 12, at the third item in the list, 8, there are three items (17 24 19) greater than 8, at the fourth item in the list, 17, there are two items (24 19) greater than 17, at the fifth item in the list, 3, there are two items (24 19) greater than 3, at the sixth item in the list, 24, there are 0 items () greater than 24, and at the seventh item in the list, 19, there are 0 items greater than 19.
Your task is to write a program to calculate the list of counts of greater than the current item; is there an O(n) solution? When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Trailing Comments
February 23, 2021
Today’s exercise is based on a blog entry that Reddit pointed me to. Sean is trying to write a program that finds lines of code in his Python programs that have trailing comments at the ends of lines, which he considers bad style. His naive program improperly flagged a line as containing a trailing comment when the comment marker is embedded in a quoted string:
x = "# This is fine""This \# is fine too"x = "" # This is not
Sean gets a little bit sidetracked in his blog entry, and never quite solves the problem; I’m not convinced the code he writes is correct (though he seems to think it is), and I’m also not convinced that trailing comments are a bad thing. Nevertheless, the task makes an interesting exercise, especially when we also handle quoted escape sequences.
Your task is to write a program that identifies lines of code with trailing comments. 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.
Local Maxima
February 16, 2021
A local maximum of a list of integers is an element of the list at which the adjacent list elements are either less than or equal to the current element; for instance, in the input list (1 2 1 2 3 4 3 2 3 2 1) there are three local maxima, one at the first 2, one at the 4, and one and the last 3. The elements at either end of a list should be considered as greater than the boundary. Only one maximum should be reported for a plateau (consecutive equal maxima).
Your task is to write a program that finds the local maxima of a list of integers. 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.
Run Length Encoding
February 9, 2021
Alexey Grigorev says:
Most candidates cannot solve this interview problem:
Input: “aaaabbbcca”
Output: [(“a”,4), (“b”,3), (“c”,2), (“a”,1)]
Write a function that converts the input to the output. I ask it in the screening inverview and give it 25 minutes. How would you solve it?
Your task is to write the requested function. 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.
Tax Brackets
January 26, 2021
My W-2 form came in the mail a few days ago, so a task about taxes is appropriate. Given the following tax brackets:
income cap tax rate$ 10,000 0%$ 30,000 10%$100,000 25%more 40%
Calculate the amount of tax given an amount of income. The tax brackets work like this: If your income is less than $10,000, your tax is $0. If your income is between $10,000 and $30,000, your tax is 10% of your income in excess of $10,000. If your income is between $30,000 and $100,000, your tax is 10% of the $20,000 of income between $10,000 and $30,000 (or $2,000) plus 25% of your income over $30,000. If your income is over $100,000, your tax is 10% of the $20,000 of income between $10,000 and $30,000 (or $2,000), plus 25% of your income between $30,000 and $100,000 (or $17,500), plus 40% of your income over $100,000 (ouch!).
For example, if your income is $123,456, your tax is $2,000 plus $17,500 plus 40% of $23,456 (or $9,382.40), a total tax of $28,882.40, or 23.4% of your income.
Your task is to write a program that calculates the amount of tax due for a given amount of income. 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.
Stalin Sort
January 19, 2021
Stalin Sort is a single-pass sort that operates in O(1) space and O(n) time. Iterate down the list of elements checking if they are in order. Any element which is out of order is sent to the gulag (eliminated from the list). At the end you have a sorted list, though it may not be a permutation of the original list. As an example, the list (1 2 5 3 5 7) is Stalin-sorted as (1 2 5 5 7); the 3 is dropped because it is less than the 5 that it follows.
Your task is to write a program that implements Stalin sort. 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.
Animal.txt
January 12, 2021
Today’s task is from a beginning programmer, who starts with an input file called animal.txt:
There once was a Dog
Wednesday he ate Apples
Thursday he ate Apples
Friday he ate Apples
Saturday he ate carrots
There once was a Bear
Tuesday he ate carrots
Wednesday he ate carrots
Thursday he ate chicken
He wants to create this output:
Food: Apples Animals who ate it: 1
=======
Dog
Food: Carrots Animals who ate it: 2
========
Bear
Dog
Food: Chicken Animals who ate it: 1
========
Bear
He gave a complicated awk solution that didn’t work; it produced duplicate lines of output in those cases
where the same animal ate the same food on multiple days.
Your task is to write a program to produces the desired transformation form input to output. 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 