Efficient Sorting Algorithm

 Here is a problem that I came across today. Here is the link.

Place each of the numbers from 1 to 15 into the spaces provided so that the sum of any two consecutive spaces is a square number. The following clue was provided: the number 8 must be placed on one end and the number 9 must be placed on the other end.

Without the clue, there are a staggering 1,307,674,368,000 possible permutations (that's over one trillion) but with the clue this reduces to 6,227,020,800 or a little over six billion. However, the clue is very helpful because we know that next to 8 we can only place a 1 and next to the 9 we can only place a 7. So we have:$$9, 7, x, x, x, x, x, x, x, x, x, x, x, 1, 8$$Now next to the 7 we can only place a 2 and next to the 1 we can only place a 15, so we now have:$$9, 7, 2, x, x, x, x, x, x, x, x, x, 15, 1, 8$$Next to the 2 we can only place 14 and next to the 15 we can only place a 10. This gives$$9, 7, 2, 14, x, x, x, x, x, x, x, 10, 15, 1, 8$$Continuing this process, we find 14 can only be paired with 11 and 10 with 6. We now have:$$9, 7, 2, 14, 11, x, x, x, x, x, 6, 10, 15, 1, 8$$We then quickly reach our solution:

The key to solving the problem is to begin and end the sequence of numbers with 8 and 9 or vice versa because these two initial choices determine all the remaining numbers. I asked Gemini to write a Python program to solve the problem but without giving it any clues. I also asked it to explain its thinking. Figure 1 is what it came up with, in about 67 lines of code.

Figure 1: Gemini Link

Here is how Gemini described its thinking:

\( \textbf{Reasoning and Strategies:}\)

is_square(n) \( \textbf{Function} \):

• This function efficiently checks if a number is a perfect square. It calculates the integer square root and compares its square to the original number. 

find_next(current_sequence, remaining_numbers) \( \textbf{Function (Recursive Backtracking:)} \)

• This function uses recursion to explore possible sequences.
• It checks if the current sequence is complete (no remaining numbers).
• For each remaining number, it checks if it forms a square sum with the last number in the current sequence.
• If a square sum is found, it adds the number to the sequence and recursively calls itself with the updated sequence and remaining numbers.
• If no valid next number is found, it backtracks. 

\( \textbf{Optimization} \) 

\( \textbf{Precompute Possible Pairs (Graph Representation): }  \)

• Instead of repeatedly checking for square sums, we precompute all possible pairs of numbers that add to a square.
• This is stored in the possible_pairs dictionary, which represents a graph where numbers are nodes, and edges exist between numbers that form a square sum.
• This optimization significantly reduces the number of square sum calculations. 

\( \textbf{Optimization} \) 

\( \textbf{Start with Numbers with Fewer Possible Pairs:} \)

• The sorted_numbers list is created by sorting the numbers based on the number of possible pairs they have.
• Starting the search with numbers that have fewer possible pairs reduces the branching factor in the recursive search. This means the algorithm explores fewer potential paths, leading to faster results.
• This is a heuristic that helps avoid exploring large portions of the search space that are unlikely to lead to a solution. 

\( \textbf{Backtracking Efficiency}: \)

• The recursive backtracking algorithm is designed to efficiently explore the search space. When a dead end is encountered (no valid next number), the algorithm immediately backtracks to the previous decision point, avoiding unnecessary exploration of other paths.
• By combining the precomputation of possible pairs and the heuristic of starting with numbers with fewer options, the backtracking algorithm becomes much more efficient than a naive brute-force approach.

The algorithm (permalink) is easily adapted for longer runs of numbers. For example, let's say we want to arrange the number from 1 to 35. Here is one configuration (generated almost instantly):

[18, 7, 2, 14, 11, 5, 31, 33, 3, 22, 27, 9, 16, 20, 29, 35, 1, 8, 28, 21, 4, 32, 17, 19, 6, 30, 34, 15, 10, 26, 23, 13, 12, 24, 25] ... permalink

Radix Economy

In a coffee shop this afternoon, I was reading an interesting article in Quanta Magazine titled How Base 3 Computing Beats Binary. I like the graphic also that began the article and which I've reproduced in Figure 1.

Figure 1: source

The article introduces the notion of "radix economy" that is explained as follows:

The hallmark feature of ternary notation is that it’s ruthlessly efficient. With two binary bits, you can represent four numbers. Two “trits” — each with three different states — allow you to represent nine different numbers. A number that requires 42 bits would need only 27 trits.

If a three-state system is so efficient, you might imagine that a four-state or five-state system would be even more so. But the more digits you require, the more space you’ll need. It turns out that ternary is the most economical of all possible integer bases for representing big numbers.

To see why, consider an important metric that tallies up how much room a system will need to store data. You start with the base of the number system, which is called the radix, and multiply it by the number of digits needed to represent some large number in that radix. For example, the number 100,000 in base 10 requires six digits. Its “radix economy” is therefore 10 × 6 = 60. In base 2, the same number requires 17 digits, so its radix economy is 2 × 17 = 34. And in base 3, it requires 11 digits, so its radix economy is 3 × 11 = 33. For large numbers, base 3 has a lower radix economy than any other integer base.

This Wikipedia article explains it in more formal terms for a number \(N\):$$ \text{radix economy of } N =b \lfloor \log_b(N)+1 \rfloor $$For large \(N\) we can thus write:$$ \begin{align} \text{radix economy of } N &\approx b \log_b(N) \\ &= \frac{b}{ln \,(b)} ln \,(N) \end{align}$$Using the number 123456789 as an example, the radix efficiency for integer bases from 3 to 16 is shown in Figure 2.

Figure 2: base 3 is best

The Quanta article goes on to say that:

In addition to its numerical efficiency, base 3 offers computational advantages. It suggests a way to reduce the number of queries needed to answer questions with more than two possible answers. A binary logic system can only answer “yes” or “no.” So if you’re comparing two numbers, x and y, to find out which is larger, you might first ask the computer “Is x less than y?” If the answer is no, you need a second query: “Is x equal to y?” If the answer is yes, then they’re equal; if the answer is no, then y is less than x. A system using ternary logic can give one of three answers. Because of this, it requires only one query: “Is x less than, equal to, or greater than y?”

And finally, also quoting from the article:

Surprisingly, if you allow a base to be any real number, and not just an integer, then the most efficient computational base is the irrational number e.

The table in Figure 2 looks as shown in Figure 3 when we add "e" to the list of bases.

Figure 3: e is best

Representing numbers using "e" as the number base is the stuff of a future post perhaps but here is a link to how to go about it. 

Measuring Dartsmanship

Recently I've taken to recording how many throws it takes me to complete a game of Round the World in darts. The game is quite simple: you must score a 1 before moving on to the 2, once the 2 is completed you can move on 3 and so on around the board before finishing on the red bullseye or the green ring around it. The minimum number of throws required for this feat is 21.

I decided to measure the efficiency of my score by dividing it into 21 and expressing this as a fraction. Thus: $$ \text{efficiency }=\frac{21}{\text{score}} \times 100$$Figure 1 shows a graph of the resultant efficiencies for scores ranging from 105 to 21.

Figure 1: permalink

Figure 2 shows a table of selected scores and their associated efficiencies (rounded to the nearest whole number).

Figure 2: permalink

As can be seen, it becomes increasingly difficult to achieve an efficiency close to 100%. For example, 22 scores 95% and 21 scores 91% but all other scores are under 90%. I'm recording these results in a newly created AirTable database. See Figure 3.

Figure 3

I'm keeping track of the number of throws using a counter on my iPhone. See Figure 4.

Figure 4

There is a defect of sorts in this way of measuring efficiency because it supposes that 21 steps required to finish are all equal. Indeed from 1 to 20 they are but the final bullseye and green ring have a combined area that is considerably smaller than the numbered sectors. One might complete steps 1 to 20 with 20 throws and then spend ten more throws before hitting the central area of the dartboard. The final score of 30 with result efficiency of 70% doesn't fully reward the extraordinary skill required to progress from 1 to 20 in only 20 throws.

The bull's-eye has an outerbull area (also know as the single bull, which scores 25) and an inner bull (also known as a double bull's-eye, which scores 50). The circular scoring area of the standard dartboard has a diameter of 34" and the bull's-eye has a diameter of 3". So this means that each numbered sector has an area of 45.04 square inches and the bull's-eye has an area of 7.069 square inches which is thus more than six times smaller. Hitting the bull's-eye in a single throw ought to be rewarded more than hitting one of the numbered sectors in a single throw.

Hitting the bull's-eye is equivalent to hitting six numbered sectors in succession. The numbers should range from 1 --> 20 and then from 21 --> 26 but 26 is difficult to work with. Let's go with 21 --> 25 so that the numbered sectors count for 80% and the bull's-eye 20%. If somebody hits the numbers 1 to 20 in twenty throws, they are assured of an 80% score. A formula then involves two statistics, \(x\) and \(y\) where the former represents the throws taken to traverse 1 to 20 and the latter represents the throws needed to hit the bull's-eye. The formula thus becomes:$$\text{efficiency }=\frac{20}{x} \times 80 + \frac{1}{y} \times 20$$This is a fairer estimate of efficiency that doesn't unduly penalise somebody for having difficulty hitting the bull's-eye. I've changed my AirTable database to reflect these changes.

ADDENDUM: March 6th 2024

There's a major problem with this final efficiency formula that I came up with and I only noticed it today. Recently, on February 26th, I achieved an efficiency of 62% after scoring 41 in the 1 to 20 section and 1 in the bull's-eye:$$ \text{efficiency } =\frac{20}{40} \times 80 + \frac{1}{1} \times 20  \approx 62.0 \%$$Today I needed 41 for the 1 to 20 section but needed two throws to get the bull's-eye. However, I was shocked to see that my efficiency was 10% less as the result of the calculation:$$ \text{efficiency } =\frac{20}{41} \times 80 + \frac{1}{2} \times 20  \approx 52.0 \%$$This is clearly not reasonable but the problem only emerged as the consistency of my dart throwing improved.

For the time being, I'll revert to my original formula:$$ \text{efficiency }=\frac{21}{\text{score}} \times 100$$This then produces more reasonable results:$$ \text{efficiency }=\frac{21}{41} \times 100 \approx 51.2 \%$$$$ \text{efficiency }=\frac{21}{43} \times 100 \approx 48.8 \%$$This formula is far from perfect but it will have to do for the time being until I come up with something better.