Con una ventana similar a la que se muestra a continuación, se le proporciona una lista de cadenas, que desea poner en orden alfabético.

Como se muestra, tiene cinco operaciones:

• Mover hacia arriba [U]: mueve la cadena seleccionada hacia arriba un lugar
• Mover hacia abajo [D]: mueve la cadena seleccionada hacia abajo un lugar
• Mover primero [F]: mueve la cadena seleccionada al principio de la lista
• Mover último [L]: mueve la cadena seleccionada al final de la lista
• Invertir [R]: invierte el orden de la lista

Con STDIN, acepte un número (cuántas cadenas), seguido de la lista desordenada de cadenas. Cada cadena consta de 2-99 letras en inglés minúsculas. (El ejemplo anterior no sería una entrada válida).

Con STDOUT, imprima la forma de ordenar la lista. Primero, mencione un elemento para seleccionar, y luego las operaciones a realizar en él para poner la lista en orden alfabético.

Por ejemplo: February U December F May D D June D R D...

Explicación: Haga clic en febrero, muévalo hacia arriba 1. Seleccione Diciembre, muévalo hacia arriba. Mayo, muévelo hacia abajo dos veces. Junio, baja una vez, invierte la lista, baja otra vez ...

Como obviamente hay muchas soluciones válidas, debe elegir la más corta posible. Es decir, elija el método con el menor número de operaciones (7 en el ejemplo anterior).

Si hay un vínculo entre las salidas correctas con la entrada, resuélvalas en el siguiente orden.

1. Elija el que tenga menos selecciones de cadena (4 en el ejemplo anterior).

2. Elija el que tenga la menor cantidad de operaciones, contando operaciones idénticas consecutivas (en una cadena) como una (6 en el ejemplo anterior).

3. Elija el que tenga la salida más corta (menor número de caracteres totales, espacios de conteo).

4. Elija el que tiene la salida que viene primero alfabéticamente.

Este es el código de golf; gana el envío más corto que siempre produce el resultado correcto.

Ejemplos

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

Ejemplos adicionales (proporcionados por Scott Leadley, cualquier error es mío y no de ypnypn)

Algunos casos difíciles:

• 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
  • ( no el número mínimo de movimientos, que sería cc F bb F aa F)

Permutaciones de 4 elementos aa bb cc ddcon rutas de clasificación de longitud> 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

Variaciones sobre un tema, 4 elementos aaaaa bbbb ccc dddonde la longitud de la cadena marca la diferencia:

• 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

Python 2 - 593 521

Es una fuerza muy bruta con algunas eficiencias, por lo que en realidad terminaría. La lista de 6 elementos con los que estoy probando está tomando alrededor de 5 segundos en mi computadora portátil.

$ 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

Tenga en cuenta que estoy ignorando el número en la entrada. Lo encuentro inútil.

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, me acabo de dar cuenta de que no estoy manejando varias operaciones con el mismo valor correctamente. Trataré de arreglar eso.

Ruby 2.0

Con el operador configurado [U, D, F, L], el menor número de selecciones de cadena para ordenar la lista es el número de elementos en la lista menos la subsecuencia común más larga. Para agregar el operador R, simplemente invierta la cadena y aplique la misma regla. Desafortunadamente, minimizar las selecciones de cadenas no es lo mismo que minimizar el número de operaciones. Por ejemplo, para una entrada de 8 dd ww aa bb cc xx yy zz, la respuesta correcta es ww D D D dd D D D, pero sería la menor cantidad de operaciones (que cumpla con los otros criterios en la pregunta) cc F bb F aa F. Esto significa que es necesario explorar una porción mucho más grande del conjunto de posibles rutas de clasificación.

Esta solución utiliza una estrategia de búsqueda de profundidad y poda alfa-beta. Es importante bajar el valor alfa rápidamente para minimizar la profundidad de búsqueda, de lo contrario el árbol de búsqueda explota exponencialmente. Por ejemplo, para determinar la ruta de clasificación con el puntaje mínimo para el ejemplo introductorio de OP, clasificar los meses en orden de calendario en orden léxico, probablemente tomará algunas décadas con el método de puntuación actual de este programa. El programa encuentra el número mínimo de selecciones de cadena, 8, muy rápidamente. Desafortunadamente, eso todavía deja un árbol enorme por el que caminar.

Estoy usando gnome sort como mi función de puntuación porque:

1. es simple de entender y modificar
2. la puntuación generalmente converge al alfa óptimo rápidamente
3. esta implementación es más rápida que la implementación de mi función LCS
4. jugará mejor golf que la función LCS

El número 4 sería suficiente. Todo lo demás es un extra.

Para una búsqueda en profundidad, el orden en que se exploran las operaciones tiene un impacto significativo en el tiempo de búsqueda. Dado que cualquier conjunto no vacío de N elementos puede clasificarse con operaciones ≤ N-1 F (primero) o L (ast), esas operaciones se intentan primero.

# 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

Pasa este conjunto de pruebas TAP perl :

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;