Put a list in order

Question

With a window similar to the one pictured below, you are given a list of strings, which you want to put in alphabetical order.

As shown, you have five operations:

• Move up [U] - moves the selected string up one place
• Move down [D] - moves the selected string down one place
• Move first [F] - moves the selected string to the top of the list
• Move last [L] - moves the selected string to the bottom of the list
• Reverse [R] - reverses the order of the list

Using STDIN, accept a number (how many strings), followed by the unordered list of strings. Each string consists of 2-99 lower case English letters. (The example above would not be a valid input.)

Using STDOUT, print the way to put the list in order. First, mention an item to select, and then the operations(s) to perform on it in order to put the list in alphabetical order.

For example: February U December F May D D June D R D...

Explanation: Click February, move it up 1. Select December, move it to top. May, move it down twice. June, move down once, reverse the list, move down again...

Since there are obviously many valid solutions, you must choose the shortest possible. That is, choose the method with the fewest number of operations (7 in the above example).

If there's a tie among correct outputs to the input, resolve it in the following order.

1. Choose the one with the fewest string selections (4 in the above example).

2. Choose the one with the fewest operations, counting consecutive identical operations (on one string) as one (6 in the above example).

3. Choose the one with shortest output (least number of total characters, counting spaces).

4. Choose the one with the output that comes first alphabetically.

This is code-golf; the shortest submission which always produces the correct output wins.

Examples

• IN 2 zz abc
  • OUT zz D
• IN 3 cc bb aa
  • OUT aa R
• IN 4 abc def cd ccc
  • OUT abc L R
• IN 6 rr mm nn oo qq pp
  • OUT pp U rr L

Additional examples (provided by Scott Leadley, any errors are mine and not ypnypn's)

Some difficult cases:

• IN => OUT
• 6 xx aa dd bb ee cc => dd L ee L xx L
• 7 aa bb ee cc dd ff gg => ee D D
• 8 dd ww aa bb cc xx yy zz => ww D D D dd D D D
  • (not the minimial number of moves, which would be cc F bb F aa F)

Permutations of 4 items aa bb cc dd with sort paths of length >1:

• IN => OUT
• 4 aa cc dd bb => bb F D
• 4 aa dd cc bb => aa L R
• 4 bb aa dd cc => aa F cc U
• 4 bb dd aa cc => aa F cc U
• 4 bb dd cc aa => bb D D R
• 4 cc aa bb dd => cc D D
• 4 cc aa dd bb => bb F aa F
• 4 cc bb aa dd => dd F R
• 4 cc bb dd aa => dd F R
• 4 cc dd aa bb => bb F aa F
• 4 cc dd bb aa => cc D R
• 4 dd aa cc bb => aa L R
• 4 dd bb aa cc => cc F D R
• 4 dd bb cc aa => bb D R
• 4 dd cc aa bb => aa D R

Variations on a theme, 4 items aaaaa bbbb ccc dd where string length makes a difference:

• IN => OUT
• 4 ccc dd aaaaa bbbb => ccc L dd L
• 4 bbbb aaaaa dd ccc => bbbb D dd D
• 4 bbbb dd aaaaa ccc => dd L bbbb D
• 4 ccc aaaaa dd bbbb => ccc L dd L
• 4 ccc dd bbbb aaaaa => dd F R
• 4 dd bbbb ccc aaaaa => ccc R D
• 4 dd ccc aaaaa bbbb => bbbb R D

Answer 1

Python 2 - 593 521

It's very brute-force with some efficiencies so it would actually finish. The 6-item list I'm testing with is taking around 5 seconds on my laptop.

$ time echo 5 xx aa dd bb ee cc | python order.py
dd L ee L xx L

real    0m4.444s
user    0m4.388s
sys 0m0.051s

Note that I'm ignoring the number in the input. I find it useless.

import sys
def d(l,s,o,f):
 p=len(o)
 tl=tuple(l)
 if tl in s and p>=len(s[tl]) or f and p>=len(f):
  return
 if l==sorted(l):
  return o if not f or p<len(f) else None
 s[tl]=o
 x=d(l[::-1],s,o+[l[-1]+' R'],f)or f
 for n,i in enumerate(l):
  for j,k in ([(l[:n]+[l[n+1],l[n]]+l[n+2:],'D'),(l[:n]+l[n+1:]+[l[n]],'L')]if(n!=len(l)-1)else[])+([(l[:n-1]+[l[n-1],l[n]]+l[n+1:],'U'),([l[n]]+l[:n]+l[n+1:],'F')]if(n!=0)else[]):
   x=d(j,s,(o+[i+' '+k]),x)or x
 return x
print ' '.join(d(sys.stdin.read().split()[1:],{},[],[]))

Ugh, I just realized I'm not handling multiple operations on the same value correctly. I'll try to fix that.

Answer 2

Ruby 2.0

With the operator set [U,D,F,L], the fewest number of string selects to sort the list is the number of items in the list minus the longest common subsequence. To add the R operator, just reverse the string and apply the same rule. Unfortunately, minimizing string selects is not the same as minimizing the number of operations. For example, for an input of 8 dd ww aa bb cc xx yy zz, the correct answer is ww D D D dd D D D, but the fewest number of operations (that meets the other criteria in the question) would be cc F bb F aa F. This means that a much larger portion of the set of possible sort paths needs to be explored.

This solution uses a depth-first search strategy and alpha-beta pruning. It's important to lower the alpha value rapidly to minimize the search depth, otherwise the search tree explodes exponential. E.g. to determine the sort path with the minimum score for OP's introductory example, sorting months in calendar order to lexical order, will probably take a few decades with this program's current scoring method. The program finds the minimum number of string selects, 8, very quickly. Unfortunately, that still leaves an enormous tree to walk through.

I'm using gnome sort as my scoring function because:

1. it's simple to understand and modify
2. the scoring usually converges to the optimal alpha quickly
3. this implementation is faster than my LCS function implementation
4. it will golf better than the LCS function

Number 4 would be sufficient. Everything else is a bonus.

For a depth-first search, the order in which operations are explored has a significant impact on the search time. Since any non-empty set of N items can be sorted with ≤ N-1 F(irst) or L(ast) operations, those operations are tried first.

# gnome sort
def gnomeSort(a)
    selects = 0
    previous = nil
    i = 1
    while i < a.size
        if a[i-1] <= a[i]
            # the array a[0..i] is sorted
            i += 1      # take another bite
        else
            if a[i] != previous
                previous = a[i]
                selects += 1
            end
            a[i], a[i-1] = a[i-1], a[i]
            if (i > 1)
                i -= 1
            end
        end
    end
    return selects
end
def score(a)
    return gnomeSort(a.dup)
end

# squeeze out unnecessary operands
def consolidate(a)
    # separate operands and operators
    x = []                      # operands
    f = []                      # operators
    a.each_slice(2) { |a,b|
        x << a
        f << b
    }
    n = x.size                  # number of (operand operator) pairs
    if n>=2
        # replace all R operands with the lexically lower operand
        #   from the right or left
        f.each_with_index{|v,i|
            if v=='R'
                leftOperand = x[i-1]
                rightOperand = x[i+1]
                # handle left & right edge cases
                leftOperand = rightOperand.succ  if i==0
                rightOperand = leftOperand.succ  if i>=n-1
                x[i] = [leftOperand, rightOperand].min
            end
        }

        # replace repeated operands with <nil>
        x = x.chunk{|e|e}.map{|v|v[1].fill(nil,1)}.flatten
    end
    return [x, f]
end

@solutions = []
@operation = []
@operation[3] = ->(a, i) {
        # swap a[i] and a[i-1]
        return nil  if i<1 || i>=a.size
        v = a[i]
        a[i-1], a[i] = a[i], a[i-1]
        return [ v, 'U' ]
    }
@operation[0] = ->(a, i) {
        # move a[i] after a.last
        return nil  if i+1>=a.size
        a.push(v=a.delete_at(i))
        return [ v, 'L' ]
    }
@operation[4] = ->(a, i) {
        # reverse the whole array
        v = a[i]
        a.reverse!
        return [ v, 'R' ]
    }
@operation[1] = ->(a, i) {
        # move a[i] before a.first
        return nil  if i<=0
        a.unshift(v=a.delete_at(i))
        return [ v, 'F' ]
    }
@operation[2] = ->(a, i) {
        # swap a[i] and a[i+1]
        return nil  if i<0 || i+1>=a.size
        v = a[i]
        a[i], a[i+1] = a[i+1], a[i]
        return [ v, 'D' ]
    }

def alphaSort(depth, a, selected, selects, sortPath)
  depth += 1
  return  if selects > @alpha
  return  if selects>@alpha || selects+depth>a.size+1
  if a.each_cons(2).all?{ |x, y| x <= y }
    # found a sort path
    @alpha = selects
    @solutions << sortPath.flatten.compact
  else
    selectsFromHere = score(a)
    if @alpha > selects+selectsFromHere
      @alpha = selects+selectsFromHere
    else
    end
    @operation.each do |op|
      a.each_index do |i|
        b = a.dup
        branch = sortPath.dup << op[b,i]
        alphaSort(depth, b, a[i], selects+(selected==a[i] ? 0 : 1), branch)
      end
    end
  end
end


#       input
a = ARGF.read.scan(/\w+/m)      # alternative, $*[0].scan(/\w+/m)
a.shift                         # ignore the item count

#       depth-first search of sort operations
@alpha = [a.size-1, score(a), score(a.reverse)+1].min + 1
alphaSort(0, a, nil, 0, [])

#       winnow the set of solutions
# determine the minimum number of string selects to solve
# short-circuit if selects to solve is 0 (already sorted)
@solutions.map!{|v|consolidate v}
minSelects = @solutions.map{|v|v[0].compact.size}.min
if !minSelects
    puts
    exit
end
# keep only solutions with the minimum number of string selects
@solutions.reject!{ |v| v[0].compact.size > minSelects }

# determine the minimum number of moves in the remaining solutions
minMoves = @solutions.map{|v|v[1].size}.min
# keep only solutions with the minimum number of moves
@solutions.reject!{ |v| v[1].size > minMoves }

#       beauty contest
# turn into strings
solutions = @solutions.map{|v|v[0].zip(v[1]).flatten.compact*' '}
# keep the shortest strings
minLength = solutions.map{|v|v.size}.min
solutions.reject!{ |v| v.size > minLength }
# print the string that "that comes first alphabetically"
puts solutions.sort.first

It passes this perl TAP test suite:

use strict;
use warnings;

use Test::More qw(no_plan);
#use Test::More tests => 61;

#       solution executable
my $solver = 'ruby2.0 sortshort.rb';
my $nonTrivial = 1;


#       "happy" path

#       examples from OP
is( `echo 2 zz abc | $solver 2>&1`, "zz D\n", 'OP example #1');
is( `echo 3 cc bb aa | $solver 2>&1`, "aa R\n", 'OP example #2');
is( `echo 4 abc def cd ccc | $solver 2>&1`, "abc L R\n", 'OP example #3');
is( `echo 6 rr mm nn oo qq pp | $solver 2>&1`, "pp U rr L\n", 'OP example #4');

# example from bizangles
is( `echo 6 xx aa dd bb ee cc | $solver 2>&1`, "dd L ee L xx L\n", 'wascally wabbit, challenges deep diver (from bizangles)');

SKIP: {
  skip('non-trivial tests', 2)  unless $nonTrivial;

  # 7 item example; bizangles' python solution (circa 2014-08-22) requires higher sys.setrecursionlimit() and takes about 5 minutes
  is( `echo 7 aa bb ee cc dd ff gg | $solver 2>&1`, "ee D D\n", 'shallow');

  # minimizing the number of selects scores better than minimizing moves
  # minimizing moves                =>  cc F bb F aa F
  # minimizing selects              =>  dd D D D D ww D D D D,  ww D D D dd D D D,  ww L U U U dd D D D,  etc.
  # minimizing selects, then moves  =>  ww D D D dd D D D
  is( `echo 8 dd ww aa bb cc xx yy zz | $solver 2>&1`, "ww D D D dd D D D\n", 'joker, minimize selects before moves');
}

#       exhaustive variations on a theme with 1 item ["aa"]
is( `echo 1 aa | $solver 2>&1`, "\n", 'permutations of 1, #1');

#       exhaustive variations on a theme with 2 items ["ab", "c"]
is( `echo 2 ab c | $solver 2>&1`, "\n", 'permutations of 2, #1');
# test OP's requirement that a string be selected before reverse operation
is( `echo 2 c ab | $solver 2>&1`, "c D\n", 'permutations of 2, #2');

#       exhaustive variations on a theme with 3 items ["five", "four", "three"]
is( `echo 3 five four three | $solver 2>&1`, "\n", 'permutations of 3, #1');
is( `echo 3 five three four | $solver 2>&1`, "four U\n", 'permutations of 3, #2');
is( `echo 3 four five three | $solver 2>&1`, "five F\n", 'permutations of 3, #3');
is( `echo 3 four three five | $solver 2>&1`, "five F\n", 'permutations of 3, #4');
is( `echo 3 three five four | $solver 2>&1`, "three L\n", 'permutations of 3, #5');
is( `echo 3 three four five | $solver 2>&1`, "five R\n", 'permutations of 3, #6');

#       selected variations on a theme with 5 items ["aa", "bb", "cc", "dd", "ee"]
is( `echo 5 aa bb cc dd ee | $solver 2>&1`, "\n", 'permutations of 5, #1, already sorted');
# two sort paths of length 1
is( `echo 5 aa bb cc ee dd | $solver 2>&1`, "dd U\n", 'permutations of 5, #2, single U or D');
is( `echo 5 aa bb ee cc dd | $solver 2>&1`, "ee L\n", 'permutations of 5, #4, single L');
is( `echo 5 bb cc aa dd ee | $solver 2>&1`, "aa F\n", 'permutations of 5, #31, single F');
is( `echo 5 ee dd cc bb aa | $solver 2>&1`, "aa R\n", 'permutations of 5, #120, reverse sorted');

#       exhaustive variations on a theme with 4 items ["aa", "bb", "cc", "dd"]
# sort paths of length 0
is( `echo 4 aa bb cc dd | $solver 2>&1`, "\n", 'permutations of 4, #1');
# sort paths of length 1
is( `echo 4 aa bb dd cc | $solver 2>&1`, "cc U\n", 'permutations of 4, #2');
is( `echo 4 aa cc bb dd | $solver 2>&1`, "bb U\n", 'permutations of 4, #3');
is( `echo 4 aa dd bb cc | $solver 2>&1`, "dd L\n", 'permutations of 4, #5');
is( `echo 4 bb aa cc dd | $solver 2>&1`, "aa F\n", 'permutations of 4, #7');
is( `echo 4 bb cc aa dd | $solver 2>&1`, "aa F\n", 'permutations of 4, #9');
is( `echo 4 bb cc dd aa | $solver 2>&1`, "aa F\n", 'permutations of 4, #10');
is( `echo 4 dd aa bb cc | $solver 2>&1`, "dd L\n", 'permutations of 4, #19');
is( `echo 4 dd cc bb aa | $solver 2>&1`, "aa R\n", 'permutations of 4, #24');

# sort paths of length 2
is( `echo 4 aa cc dd bb | $solver 2>&1`, "bb F D\n", 'permutations of 4, #4');
is( `echo 4 aa dd cc bb | $solver 2>&1`, "aa L R\n", 'permutations of 4, #6');
is( `echo 4 bb aa dd cc | $solver 2>&1`, "aa F cc U\n", 'permutations of 4, #8');
is( `echo 4 bb dd aa cc | $solver 2>&1`, "aa F cc U\n", 'permutations of 4, #11');
is( `echo 4 bb dd cc aa | $solver 2>&1`, "bb D D R\n", 'permutations of 4, #12');
is( `echo 4 cc aa bb dd | $solver 2>&1`, "cc D D\n", 'permutations of 4, #13');
is( `echo 4 cc aa dd bb | $solver 2>&1`, "bb F aa F\n", 'permutations of 4, #14');
is( `echo 4 cc bb aa dd | $solver 2>&1`, "dd F R\n", 'permutations of 4, #15');
is( `echo 4 cc bb dd aa | $solver 2>&1`, "dd F R\n", 'permutations of 4, #16');
is( `echo 4 cc dd aa bb | $solver 2>&1`, "bb F aa F\n", 'permutations of 4, #17');
is( `echo 4 cc dd bb aa | $solver 2>&1`, "cc D R\n", 'permutations of 4, #18');
is( `echo 4 dd aa cc bb | $solver 2>&1`, "aa L R\n", 'permutations of 4, #20');
is( `echo 4 dd bb aa cc | $solver 2>&1`, "cc F D R\n", 'permutations of 4, #21');
is( `echo 4 dd bb cc aa | $solver 2>&1`, "bb D R\n", 'permutations of 4, #22');
is( `echo 4 dd cc aa bb | $solver 2>&1`, "aa D R\n", 'permutations of 4, #23');

#       variations on a theme with 4 items ["aaaaa", "bbbb", "ccc", "dd"]
# force choice by string length
is( `echo 4 ccc dd aaaaa bbbb | $solver 2>&1`, "ccc L dd L\n", 'permutations of 4, #17');
is( `echo 4 dd bbbb aaaaa ccc | $solver 2>&1`, "ccc F D R\n", 'permutations of 4, #21');
is( `echo 4 bbbb aaaaa dd ccc | $solver 2>&1`, "bbbb D dd D\n", 'permutations of 4, #8');
is( `echo 4 bbbb dd aaaaa ccc | $solver 2>&1`, "dd L bbbb D\n", 'permutations of 4, #11');
is( `echo 4 ccc aaaaa dd bbbb | $solver 2>&1`, "ccc L dd L\n", 'permutations of 4, #14');
is( `echo 4 ccc dd bbbb aaaaa | $solver 2>&1`, "dd F R\n", 'permutations of 4, #18');
is( `echo 4 dd aaaaa ccc bbbb | $solver 2>&1`, "aaaaa L R\n", 'permutations of 4, #20');
is( `echo 4 dd bbbb ccc aaaaa | $solver 2>&1`, "ccc R D\n", 'permutations of 4, #22');
is( `echo 4 dd ccc aaaaa bbbb | $solver 2>&1`, "bbbb R D\n", 'permutations of 4, #23');

# identical items in list
is( `echo 2 aa aa | $solver 2>&1`, "\n", '1 repeat #1');
is( `echo 3 aa aa bb | $solver 2>&1`, "\n", '1 repeat #2');
is( `echo 3 aa bb aa | $solver 2>&1`, "aa F\n", '1 repeat #3');
is( `echo 3 bb aa aa | $solver 2>&1`, "aa R\n", '1 repeat #4');
is( `echo 4 aa cc bb aa| $solver 2>&1`, "aa L R\n", '1 repeat #5');
is( `echo 5 cc bb aa bb cc | $solver 2>&1`, "aa F cc L\n", '2 repeats');

#       "sad" path

# not explicitly excluded, so cover this case
#       exhaustive variations on a theme with 0 items []
is( `echo 0 | $solver 2>&1`, "\n", 'permutations of 0, #1');


#       "bad" path
# none!


exit 0;