## 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.

## Two Simple Tasks

### January 5, 2021

Happy New Year! May 2021 be a better year than 2020.

We have two simple tasks today:

First: Write a program that prints the sequence 1, 5, 10, 50, 100, … up to a given limit.

Second: Write a program that finds all three-digit numbers

nsuch thatn/11 equals the sum of the squares of the three digits.

Your task is to write programs that solve the two tasks given above. 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.

## Rhyming Sort

### December 8, 2020

I recently found on the internet a delightful paper by Kenneth Ward Church called *Unix™ for Poets* that provides an introduction to the Unix command line utilities for text processing. The paper must be ancient, because it gives the author’s email address at research.att.com, but I’ve never seen it before. One of the examples in the paper is rhyming sort, in which words are sorted from the right rather than the left; the left column below is in normal alphabetical order, the right column is in rhyming order:

```
falsely freely
fly sorely
freely surely
sorely falsely
surely fly
```

Church says:

“freely” comes before “sorely” because “yleerf” (“freely” spelled backwards) comes before “yleros” (“sorely” spelled backwards) in lexicographic order. Rhyming dictionaries are often used to help poets (and linguists who are interested in morphology).

Church solved the problem with a `rev | sort | rev`

pipeline.

Your task is to sort a file containing one word per line into rhyming order. 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.