Math

Count number of heaps coding problem

Count number of heaps coding problem

Bruce Ediger

Another programming interview question from the Daily Coding Problem email list. I received it as #1608.

Daily Coding Problem: Problem #1608 [Medium]

This problem was asked by Microsoft.

Write a program to determine how many distinct ways there are to create a max heap from a list of N given integers.

For example, if N = 3, and our integers are [1, 2, 3], there are two ways, shown below.

  3      3
 / \    / \
1   2  2   1

Repo for my code.

Smullyan's clever solutions

Bruce Ediger

In my post about Raymond Smullyan’s Og and Bog puzzle, I wrote:

Smullyan has a clever solution in the back of Logical Labyrinths, but I’m going to whittle the puzzle down to a size I can hold in my head, because I like procedures to solve puzzles. Having a procedure keeps me from making mistakes, and developing the procedure helps me understand the underpinnings of all problems.

I thought of something that makes Smullyan smarter than I believed.

Raymond Smullyan's Knights and Knaves

Bruce Ediger

Raymond Smullyan, my favorite mathematician, posed a large number of questions involving the Isle of Knights and Knaves. Inhabitants are either knights, who always tell the truth, or knaves, who always tell falsehoods.

One of the best Knight and Knave problems is Og and Bog from Smullyan’s book Logical Labyrinths

Og and Bog are brothers living on the Isle of Knights and Knaves, and one of them is the chief.

  • Og says: Bog is the chief and he is a knave!
  • Bog says: Og is not the chief, but he is a knight.

Which one is the chief?

Base Seven

Bruce Ediger

An intelligent species (or confederation of species) might choose to use base 7 for their numeral system, no matter the exact number or nature of digits at the terminal end of their manipulative appendages.

Even entities with 8 terminal sub-appendages might use base 7.