8
\$\begingroup\$

The following problem is taken from the real world — but indubitably code-golf! In this puzzle, the programming language is fixed, and your job is to write the most efficient program in this fixed language. The language has no loops; a program is a straight-line sequence of instructions. Each instruction consists of exactly three characters — an opcode and two operands — and in fact there are only four possible opcodes:

  • <xy — Compare the value in register x to the value in register y; set flag = L if x < y; flag = G if x > y; and flag = Z otherwise.
  • mxy — Set the value in register x equal to the value in register y. (This is "move.")
  • lxy — If flag = L, then set the value in register x equal to the value in register y; otherwise do nothing. (This is "conditional move," or "cmov".)
  • gxy — If flag = G, then set the value in register x equal to the value in register y; otherwise do nothing. (This is "conditional move," or "cmov".)

For example, the program mca <ba lcb means "Set register c equal to the minimum of a and b."

The program mty <zy lyz lzt means "Stably sort the values in registers y and z." That is, it sets y to the minimum of y and z (breaking ties in favor of y) and sets z to the maximum of y and z (breaking ties in favor of z).

The following 16-instruction program stably sorts the values in registers x, y, z:

<zy mtz lzy lyt
max mby mcz
<yx lay lbx
<zx lcx lbz
mxa myb mzc

Your task is to find the shortest program that stably sorts four registers w, x, y, z.

A trivial Python implementation is available here if you want to test your solution before (or after) posting it.

\$\endgroup\$
13
  • \$\begingroup\$ You'll receive imaginary bonus points if you find a second (shortest) program that stably sorts five registers. \$\endgroup\$ Dec 19, 2023 at 3:00
  • \$\begingroup\$ This reminds me of Zachlike programming, specifically the programming in Shenzhen I/O. \$\endgroup\$
    – Tbw
    Dec 19, 2023 at 4:21
  • 3
    \$\begingroup\$ What does "stable" sorting mean when values that compare as equal are actually equal? \$\endgroup\$ Dec 19, 2023 at 6:06
  • 1
    \$\begingroup\$ I mean if "equal" truly means "equal" and not just "equivalent" then you cannot tell whether equal elements have been swapped or not. \$\endgroup\$ Dec 19, 2023 at 18:41
  • 1
    \$\begingroup\$ My point is neither deep not philosophical. Your wording ("cmov", "register") strongly suggests an assembly-like setting.The average reader will understand a register as carrying a simple value, a number, not something that would have "attributes that do not participate in equality". \$\endgroup\$ Dec 20, 2023 at 3:04

3 Answers 3

6
\$\begingroup\$

21 instr

  '<wx', 'gtw', 'gwx', 'gxt',
  '<xy', 'guy', 'gyx', 'gxu',
  '<yz', 'gtz', 'gzy', 'gyt',
  '<wx',        'gxw', 'gwu',
  '<xy',        'gyx', 'gxt',
  '<wx',        'gxw', 'gwt'

Try it online!


Neil suggests that reordering into this may get more clear:

<wx gtw gwx gxt
<xy gty gyx gxt
<wx     gxw gwt
<yz gtz gzy gyt
<xy     gyx gxt
<wx     gxw gwt

This looks more like insertion sort



For large enough amount of element, a \$\tilde {\mathrm O} \left(n\right)\$ sorting algorithm exist. Here I construct a \$\mathrm O \left(n \log^2 n\right)\$ one using a \$\mathrm O \left(n \log n\right)\$ sorting network, which seems reducible: (say the input is A[0..n-1]

  1. Set O to min(A) and I to max(A).

Notice that if O = I, then all elements are equal, and no swap would apply.

  1. Let B[i][j] = i & (1 << j) ? I : O for 0 <= j < log2(n).

  2. Do sorting network on A, each element A[i] together with B[i].

To do a multi-element compare:

T = O
if (P[0] < Q[0]) T = I
if (P[1] > Q[1]) T = O
if (P[1] < Q[1]) T = I
if (P[2] > Q[2]) T = O
if (P[2] < Q[2]) T = I
...
if (P[9] > Q[9]) T = O
if (P[9] < Q[9]) T = I
if (T > O) swap

This makes a swap in \$\mathrm O \left( \log n\right)\$

\$\endgroup\$
7
  • 2
    \$\begingroup\$ This also reduces the three-register sort from 16 to 12 instructions. \$\endgroup\$
    – Neil
    Dec 19, 2023 at 8:21
  • \$\begingroup\$ Very nice! But more boringly symmetric than I'd expected. ;) I mean, it's literally bubble sort — bubble max(w,x,y,z) up to z, then bubble max(w,x,y) up to y, etc. Do you think it's generally the case that stable-sorting n elements in this restricted language requires (n-1) + (n-2) + ... + 2 + 1 < instructions? \$\endgroup\$ Dec 19, 2023 at 16:40
  • 1
    \$\begingroup\$ @Quuxplusone I can sort n elements in \$\text O(n \log^3 n)\$ by finding two different elements to record position, and it should be far from optimal \$\endgroup\$
    – l4m2
    Dec 20, 2023 at 3:54
  • 1
    \$\begingroup\$ @Quuxplusone Pseudo-code \$\endgroup\$
    – l4m2
    Dec 20, 2023 at 15:28
  • 2
    \$\begingroup\$ <wx gtw gwx gxt <xy gty gyx gxt <wx gxw gwt <yz gtz gzy gyt <xy gyx gxt <wx gxw gwt shows more clearly what's going on, and also uses one fewer temporary to boot. The three-register sort is also now only 11 instructions: <xy gty gyx gxt <yz gtz gzy gyt <xy gyx gxt. \$\endgroup\$
    – Neil
    Dec 24, 2023 at 12:22
1
\$\begingroup\$

23 22 instructions

Here's a different approach from l4m2's bubble sort — we can use insertion sort. We start by sorting x, y, z. Then we insert w in its proper place by starting at the top and working downward: If w > z, insert it and bump out the old z into q. If w > y, insert q and bump out the old y into q. And so on. An "unoptimized" sequence of instructions that works for that second part is:

mpw mtx muy mvz
<vp mqp lqv lvp
mau <up luq lqa
<tp lpt ltq
mwp mxt myu mzv

I can optimize that and append it to l4m2's 12 Neil's 11-instruction sort3 to produce this 23 22-instruction sort4:

<zy lty lyz lzt
<yx ltx lxy lyt
<zy lyz lzt
mqw <zw lqz lzw
<yw lty lyq lqt
<xw lwx lxq

But I don't see how to shrink it further than that.

And it still uses 6 < instructions. Is it conceivably possible to use only 5? Here's a 20-instruction sort4 (based on this sorting network) that uses only 5 comparisons but is not stable, so it doesn't fulfill the challenge:

<wy gtw gwy gyt
<xz gtx gxz gzt
<wx gtw gwx gxt
<yz gty gyz gzt
<xy gtx gxy gyt

I'm also (finally) realizing that I should have given not only cmovl and cmovg but also cmovle and cmovge as primitives; I wonder if that would have helped at all.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Since sort3 is now down to 11 instructions, this can be reduced to 22: <xy gty gyx gxt <yz gtz gzy gyt <xy gyx gxt mqw <zw lqz lzw <yw lty lyq lqt <xw lwx lxq. \$\endgroup\$
    – Neil
    Dec 24, 2023 at 12:25
  • \$\begingroup\$ Oh, you have a tweaked sort3... I'm sure you can figure out what I meant... \$\endgroup\$
    – Neil
    Dec 24, 2023 at 12:27
0
\$\begingroup\$

32 instructions

Here's yet another approach: mergesort. This successfully minimizes the number of < operations to 5, but we pay for it with a lot more cmovs. We start by sorting the sublists {w, x} and {y, z}; then we merge those two lists. But "merge the two lists" is harder than it sounds. I wrote out the complete game tree; e.g. "First compare wy. If true, the next step will be to compare xy; otherwise, the next step will be to compare wz" and so on. Then rewrite as "If wy, set i,jx,y; otherwise, set i,jw,z. The next step is to compare ij" and so on. That gives an unoptimized program like this:

<wx gtw gwx gxt
<yz gty gyz gzt
maw mbx mcy mdz
<ac
  mwa mib mjc m1c m2d m3c m4d m5b m6d m7d m8b
  gwc gia gjd g1b g2d g3d g4b g5a g6b g7a g8b
<ij
  mxi
  gxj g15 g26 g37 g48
<bd
  my1 mz2
  gy3 gz4

My best-optimized version takes 32 instructions:

<wx gtw gwx gxt
<yz gty gyz gzt
m3y m4z m5x m6z m7z m8x
<wy g48 g5w g6x g7w gwy gx5 gy8 g3z
<x3 gx3 gy5 gz6 g37 g48
<8z gy3 gz4
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.