Yesterday’s post from Programming Praxis asks us to solve a problem known as the Dutch National Flag problem (attributed to Edsgar Dijkstra): sort an array of red, white and blue symbols so that all reds come together, followed by all whites, followed finally by all blues.
On the island of Floup in the South Pacific ((not a real place)), one might find coins worth 1, 3, 7, 31, or 153 floupia each. In addition, they have a most curious custom. Whenever one makes a payment of any sort, it is considered rude not to minimize the total number of coins involved in the exchange. For example, if someone were to purchase a nice refreshing beverage for 17 floupia ((the floupia is currently performing rather well against the dollar)), one might pay with three 7f coins and receive a 1f and a 3f coin in exchange for a total of 5 coins. But that would be terrible, as a more efficient solutions exists: pay a single 31f coin and receive two 7f coins as change.
Yesterday’s puzzle from Programming Praxis asks us to solve a Sunday Puzzle from NPR:
Think of two familiar, unhyphenated, eight-letter words that contain the letters A, B, C, D, E and F, plus two others, in any order. What words are these?
It’s another in a long history of word games, my favorite sort of puzzle.
Yesterday’s post from Programming Praxis has us trying to find the predecessor and successor to a given value in a binary search tree. There are actually two general algorithms for doing this, depending on if you have parent pointers or not–but they’re asking for the algorithm without.
Today’s intermediate challenge on Reddit’s /r/dailyprogrammer intrigued me somewhat, so I decided to take a crack at it. The basic idea is if you are given a number, try converting it to all bases from 2 to 64 (with a special encoding). Print out any of those that are words.
For example, if you interpret the number 44,269 as a base 16 (Hexadecimal) number, you get the word “aced”. So just how many of these words are there out there?
Yesterday saw another puzzle from Programming Praxis, this one entitled The 147 Puzzle. The description is relatively straight forward. Find a set of k fractions each with numerator 1 such that the sum is equal to one.
For example, 1/5 + 1/5 + 1/5 + 1/5 + 1/5 = 1 is a trivial solution for k = 5. It turns out that there are 147 solutions when k = 5, thus the name of the puzzle.
Here is today’s /r/dailyprogramming challenge: Generate a simple substitution cipher such that the maximum number of words in a given dictionary of six letter words (there are 7,260 of them) are encoded as strings in alphabetical order.
It may be 1 uinal, 15 kin too late for the new baktun, but I’ve got some neat code to convert back and forth between the Gregorian calendar and the Mayan calendar. It’s based on a challenge on a post on the /r/dailyprogrammer subreddit. As one might expect, the goal is to be able to take a year, month, and day in the Gregorian calendar and return the equivalent Mayan Long Count corresponding to that date. As a bonus (which of course I had to do 😄), do the opposite and do it without using built in date functions.
I did say in yesterday’s comments that I would try re-implementing splay heaps using an imperative model with an array (Scheme’s vector) as the back end rather than a functional one with trees. Well, here is is.
Yesterday’s post from Programming Praxis gives a new (or at least different) vantage point on one of the most common problems in Computer Science: sorting. Today, we’re going to implement a data structure known as a splay heap and use that to perform a heapsort.