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.
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.
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.
Four points, a square?) and comes originally from a Google Code Jam problem. The problem is stated simply enough
Accept three points as input, determine if they form a triangle, and, if they do, classify it at equilateral (all three sides the same), isoceles (two sides the same, the other different), or scalene (all three sides different), and also classify it as acute (all three angles less than 90 degrees), obtuse (one angle greater than 90 degrees) or right (one angle equal 90 degrees).
But once you start implementing it, that’s when things get more interesting. 😄
Yesterday’s post from Programming Praxis asks us to write a function that will read content formatted as comma-separated values and output the result as an HTML table. Their solution uses the text file database library that they posted about (which is a neat concept, you should check it out), but I think I’m going to work out the solution more directly.
Another post from Programming Praxis. This one was originally intended for Friday but they posted it early, so I figured I would go ahead and do the same. The problem is actually deceptively straight forward:
Given four points, do they form a square?