Skip to main content

Featured Post

Ed Scheidts Mayan Symbols - Can we solve the puzzle?

In this post I want to talk about a thing from the Kryptos universe that are not directly related to the statue. But i think it may be an indirect hint to some Kryptos related methods. The Mayan Symbols in Ed Scheidts driveway I think everyone who knows Kryptos knows Ed Scheidt. The former Chairman of the Cryptographic Center at the CIA and founder of the cryptosystems used around the Kryptos statue. As already shown in Part 4 of my Kryptos series, in the driveway of Ed Scheidts house, there are two symbols: Figure 1 - Garage driveway of Ed Scheidt We denote the left symbol set with $S_1$ and the right one with $S_2$. It took me a while to find his house on Google Maps - Street View. To save you some time, here is the link with a view on the driveway. I you go back in time in Streetview, you can see that the symbols were already there in 2012. But it is impossible to say when they were built. $S_1$ is clearly visible from the street, $S_2$ is hidden in the view. But you can u...
12 comments

Gravity-Sort, sorting in $\mathcal{O}(1)$

Sorting integers and the corresponding algorithms is one of the first basic topics one learns in computer science. Bubble-Sort, Insertion-Sort, Merge-Sort, Quick-Sort, Radix-Sort and even many more are discussed during the first classes. For a general purpose sorting algorithm, that is one that is based on comparison operations, it is known that one can not do better than $\mathcal{O}(n\log n)$. 
Radix-Sort for example, which is not a general purpose algorithm, since it works only for integers, has a running time for $k$-digit integers of $\mathcal{O}(kn)$.

The sorting algorithm which i want to discuss today is Gravity-Sort (Although Wikipedia calls it Bead-Sort.) It is based on a funny little idea to let gravity make the work for you. It has a theoretical runtime (assuming gravity is for free) of $\mathcal{O}(1)$. Implementing this on a normal pc would actually destroy this runtime because the gravity has to be programmed somehow.


However, it works as follows: Assume we have a list of integers $3,6,3,1,4$. Little beads, that are lined up on a stick vertically, are forming these integers horizontally. An abacus would, for example, be a perfect tool for this kind of sorting.

\begin{array}{l | c c c c c c}
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
6&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet\\
&|&|&|&|&|&|\\
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
1&\huge\bullet&|&|&|&|&|\\
&|&|&|&|&|&|\\
4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
\hline\\
\end{array}
Let the gravity begin.
\begin{array}{l | c c c c c c}
1&\huge\bullet&|&|&|&|&|\\
&|&|&|&|&|&|\\
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
&|&|&|&|&|&|\\
6&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet\\
\hline\\
\end{array}
The beads fall until they are all stacked up on the last row. The sorted list of integers can then be extracted row by row.

Lemma. Assuming that gravity is an $\mathcal{O}(1)$ operation, and neglecting input and output operations, Bead-Sort sorts a given list in $\mathcal{O}(1)$.

Informal proof. You can view Bead-Sort as Simultaneous Bubble-Sort. Bubble-Sort takes an integer, say the one at the bottom, and moves the integer via comparison upwards (like it bubbles towards the surface) until it reaches a larger number. There it stops. It does so for every integer one after another. Here, it is similar, but all this bubbling happens more or less concurrently and from the top to the bottom.
To see this, look what happens if we drop the rows one after another instead of concurrently:
\begin{array}{l | c c c c c c}
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
6&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet\\
&|&|&|&|&|&|\\
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
1&\huge\bullet&|&|&|&|&|\\
&|&|&|&|&|&|\\
4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
\hline\\
\end{array}
The bottom line can not drop any further, so we let the second to last row drop onto the last row.
\begin{array}{c l | c c c c c c}
&3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&&|&|&|&|&|&|\\
&6&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet\\
&&|&|&|&|&|&|\\
&3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&&|&|&|&|&|&|\\
\rightarrow&1&\huge\bullet&|&|&|&|&|\\
&&|&|&|&|&|&|\\
\rightarrow&4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
\hline\\
\end{array}
Nothing happens. Now, we let the let third to the last row drop. First, it drops onto the second to the last row.
\begin{array}{c l | c c c c c c}
&3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&&|&|&|&|&|&|\\
&6&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet\\
&&|&|&|&|&|&|\\
\rightarrow&3-2=1&\color{red}{\huge\bullet}&|&|&|&|&|\\
&&|&|&|&|&|&|\\
\rightarrow&1+2=3&\huge\bullet&\color{red}{\huge\bullet}&\color{red}{\huge\bullet}&|&|&|\\
&&|&|&|&|&|&|\\
&4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
\hline\\
\end{array}
Since, the dropping row has two beads more, these additional beads drop onto the row below, indicated by the red-colored beads. This "operation" is equal to a swap operation, i.e., the two rows exchange their length.
Hence, whenever a larger row drops onto a smaller row, they exchange their length, i.e., the number of beads in that rows. Consequently, a larger row drops down and swaps its length, until it reaches a larger row.
The next step would be to let the second row (now colored orange) drop onto the new third row:

\begin{array}{c l | c c c c c c}
&3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&&|&|&|&|&|&|\\
\rightarrow&6-5=1&\color{orange}{\huge\bullet}&|&|&|&|&|\\
&&|&|&|&|&|&|\\
\rightarrow&1+5=6&\color{red}{\huge\bullet}&\color{orange}{\huge\bullet}&\color{orange}{\huge\bullet}&\color{orange}{\huge\bullet}&\color{orange}{\huge\bullet}&\color{orange}{\huge\bullet}\\
&&|&|&|&|&|&|\\
&3&\huge\bullet&\color{red}{\huge\bullet}&\color{red}{\huge\bullet}&|&|&|\\
&&|&|&|&|&|&|\\
&4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
\hline\\
\end{array}
They exchange their length and the large row will drop in the same manner until it reaches it final position.
Executing this simultaneously is Bead-Sort and hence yields a sorted list of integers.
Q.e.d.

        # Practical Implications #

Has Bead-Sort any practical implications? There exists an implementation on special purpose hardware, which allows a runtime of around $\mathcal{O}(n)$. With standard mechanism it is hard to believe that it can be implemented in such a way, that is becomes more efficient than that. 
Note one has not to use gravity, but also any other mechanism that pulls the beads at one column downwards. For example some electric or magnetic forces could be used to manipulate a given certain arranged input list.

Given an matrix like object of size $n\times n$, initialize the rows with the unsorted integer list.

\begin{array}{c || c | c | c | c | c | c |}
\hline
\rightarrow&\bullet&\bullet&...&\bullet & & \\
\hline
\rightarrow&\bullet&\bullet&...& & & \\
\hline
...&...&...&...& & & \\
\hline
\rightarrow&\bullet&\bullet&...&\bullet&\bullet&\bullet\\
\hline
\rightarrow&\bullet&\bullet&...&\bullet&\bullet&\\
\hline
\end{array}
Apply some kind of pulling force to each column that makes each "bead" move downwards.
\begin{array}{c | c | c | c | c | c | c |}
\hline 
&\bullet&\bullet&...&\bullet & & \\
\hline 
&\bullet&\bullet&...& & & \\
\hline 
&...&...&...& & & \\
\hline 
&\bullet&\bullet&...&\bullet&\bullet&\\
\hline 
&\bullet&\bullet&...&\bullet&\bullet&\bullet\\
\hline
&\color{red}{\downarrow}&\color{red}{\downarrow}& \color{red}{\downarrow}&\color{red}{\downarrow}&\color{red}{\downarrow}&\color{red}{\downarrow}
\end{array}
 Readout the sorted integer list from each row.
 \begin{array}{c | c | c | c | c | c | c |}
\hline
\leftarrow&\bullet&\bullet&...&\bullet & & \\
\hline
\leftarrow&\bullet&\bullet&...& & & \\
\hline
...&...&...&...& & & \\
\hline
\leftarrow&\bullet&\bullet&...&\bullet&\bullet&\\
\hline
\leftarrow&\bullet&\bullet&...&\bullet&\bullet&\bullet\\
\hline
\end{array}
Is it possible and does this yield a non-negligible advantage?
Labels:

Comments

Post a Comment

Popular posts from this blog

Kryptos - The Cipher (Part 4) - Correctly positioned decryption of the word BERLIN

EASTNORTHEAST - This is not exactly the hint Jim Sanborn (JS) gave for K4 on the 29th of January this year. He only gave NORTHEAST - which refers to the positions 26-34 of K4's plaintext.  Beside BERLIN and CLOCK it is the third revealed plaintext word of K4. However, also this hint does not seem to help much.  However, it just so happened, that a member in the yahoo kryptos group had a conversation with Jim Sanborn due to a submitted solution. Sandborn's answer to the question contained again the last clue which surprisingly was EASTNORTHEAST at position 22-34. Jim Sanborns compass rose at CIA There is disagreement if Jim revealed this on purpose or he did it accidentially, but the new extended clue seem to be serious and valid.Interestingly, EASTNORTHEAST is exactly the direction which is illustrated on the compass rose on one of the stones around kryptos, also created by Jim Sanborn. Actually, i dont really kn...
116 comments
Read more

Kryptos - The Cipher (Part 1) - Introduction

Introduction. Since I think that KRYPTOS does not need any introduction, I will only give you a brief description of one of the most famous and only partially solved ciphers known today: KRYPTOS - Von Jim Sanborn - Jim Sanborn, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=8253447 KRYPTOS was constructed in Nov. 1990 on the ground of the CIA Headquarter in Langley, Virginia by Jim Sanborn It contains 4 ciphers (K1,K2,K3,K4) on its left side and some kind of Vigenère-Table on its right side K1, K2 and K3 were solved by James Gillogly in 1999. Afterwards, the CIA and later the NSA claimed that they had a solution to the first three ciphers at an earlier point in time Ed Scheidt, a cryptoanalyst and former director of the CIA, gave Sanborn the input of possible cryptographic techniques to use K1 is a variant of the Vigenère-Cipher (Quagmire 3) with the codewords KRYPTOS and PALIMPSES...
7 comments
Read more

Kryptos - The Cipher (Part 3)

This post is about is more or less a collection of several approaches and facts that has been said as well as some speculations. B-ary integer representation According to [1] during a Question and Answer round, Jim Sanborn was asked again about the hint BERLIN. The question was if N decodes to B, Y decodes to E, etc, etc. and Jim confirmed it does. Emphatically . It is written, that Jim Sanborn rattled through the entire crib: \begin{align}   \texttt{N} &\stackrel{\text{decode}}{\rightarrow} \texttt{B} \\   \texttt{Y} &\stackrel{\text{decode}}{\rightarrow}  \texttt{E} \\   \texttt{P} &\stackrel{\text{decode}}{\rightarrow}  \texttt{R} \\   \texttt{V} &\stackrel{\text{decode}}{\rightarrow}  \texttt{L} \\   \texttt{T} &\stackrel{\text{decode}}{\rightarrow}  \texttt{I} \\   \texttt{T} &\stackrel{\text{decode}}{\rightarrow}  \texttt{N} \end{align} When the same q...
1 comment
Read more