(Inspirado mientras dibuja en una pizarra)

Desafío:

Dada una cadena de entrada que contiene caracteres que representan diferentes colores de marcadores de borrado en seco en una pizarra blanca, genera el orden en el que fueron dibujados, del primero al último.

Entrada:

Una cadena que contiene colores de marcadores de borrado en seco que están representados por letras alfabéticas (las mayúsculas son diferentes a las minúsculas, puede sustituir cualquier carácter utilizado en mis ejemplos siempre que cada color tenga una letra distinta). El resto de la pizarra será espacio en blanco. Solo habrá una línea de cada color por tablero. No habrá entradas donde todas las líneas se superpongan entre sí (ver caso de prueba 4). Todas las líneas serán rectas y horizontales o verticales.

Salida:

El orden en que se dibujaron las líneas en el tablero, desde el primero hasta el último. Si hay varias soluciones para cualquier entrada, puede generar cualquiera de ellas. La salida se puede formatear de cualquier manera que prefiera: una sola cadena de caracteres o separada por espacios, nuevas líneas, etc. siempre que los caracteres utilizados coincidan con los utilizados en su entrada.

Casos de prueba:

Entrada 1:

  R
  R
BBRBB
  R

Salida 1:

BR

Entrada 2:

    GY
    GY
RRRRGYRRR
    GY
    GY
BBBBBBBB
    GY
    GY

Salida 2:

RGYB // or RYGB

Entrada 3:

    R    P
    R    P
AAAARAAAAPA
    R    P
    R    P
GGGGRGGG P
    R

Salida 3:

AGPR // or APGR

Entrada 4:

 O Y
RRRYR
 O Y
GOGGG
 O Y

Salida 4:

// Undefined, does not need to be handled by your program

Entrada 5:

YYYB
   B
   B

Salida 5:

// YB or BY

Reglas:

Este es el código de golf , por lo que gana el código más corto en bytes.

Perl, 103 + 2 = 105 bytes

s/$/$"x y===c/gem;$a=$_;$_.=$"while$a=~s/^./!($_.=$&)/gem;s/$1/-/g,$b="$&$b"while/\s(\w)(\1|-)+ /;say$b

Ejecutar con -n0(penalización de 2 bytes).

Explicación:

# -n0: read entire input into `$_` at start of program
# (technically speaking it reads to the first NUL byte, but there aren't any)

# We want to be able to extract columns from the input, so we need to add spaces
# to the ends of each line such that each column is complete. Adding too many
# space is OK, so to ensure we have enough, we add a number of spaces equal to the
# length of the input.
s/$/             # At the end of {something},
$" x             # append a number of spaces ($" is a space by default)
y===c            # obtained by counting the characters in $_
/gem;            # where {something} is each (g) line (m)

$a = $_;         # store a copy of the transformed input in $a

# The next step is to create a transposition of the input. To do that, we
# repeatedly extract the first column of $a and append it to $_. This will lead to
# a bunch of junk whitespace at the end of $_ (of varying lengths, because once a
# line is empty it's omitted from the extracted column), but we're OK with that.
# To transpose properly, we'd want to place newlines between the extracted
# columns; however, it happens that the rest of the program treats space the same
# way it would newline, and separating via spaces is shorter, so we do that.

while (          # keep looping as long as there are matches
  $a =~ s/^./    # replace the first character of {something related to $a}
  !(             # with the null string (NOT of something truthy)
    $_.=$&)      # but append that character ($&) to $_
  /gem) {        # {something} is each (g) line (m) of $a
  $_.=$"         # append a space ($", equivalent to newline here) to $_
}

# Finally, we repeatedly replace every character in the topmost line with the -
# character (treating a line as continuous through the - character but not through
# other characters), thus finding the lines from top to bottom. Because we
# appended the transpose of $_ to $_ above, each line appears twice: once
# horizontally, once vertically. We find only the horizontal copy, but replace
# both with hyphens.
# (Note: I rewrote the regex into a bit more readable of a form in this ungolfed
# version, because the original version wouldn't allow me room to write comments
# inside it. The two should be equivalent; I tested the golfed version.)
while (          # keep looping as long as there are matches
  /\s(\w)        # match a space or newline, $1 (a letter/digit/underscore),
    (\1|-)+      # any positive number of $1s and hyphens,
    \ /x) {      # and a space
  s/$1/-/g,      # changes all $1s to spaces; set $& to $1, $1 becomes invalid
  $b = "$&$b"    # prepend $& to $b
}

# We need to output the lines from first (i.e. bottom) to last (i.e. top).
# We found them in the opposite order, but reversed them via prepending
# (not appending) the partial results to $b.
say $b           # output $b

Una leve sutileza aquí viene con información como esta:

   A B C
DDDDDDDDD
   A B C
   A B C
   A B C

Mira la cuarta línea aquí. Si el orden de escritura fuera BACBD, realmente podría haber una línea horizontal de Bs a lo largo de allí sin violar ninguna de las suposiciones del problema (aparte de eso, solo hay una línea de cada color, algo que no verificamos). Para evitar esto, nos aseguramos en la última expresión regular de que cada línea comience con una letra (o dígito o guión bajo, pero eso es imposible), y confiamos en el hecho de que las líneas paralelas se encontrarán de izquierda a derecha y arriba -hasta abajo (porque la expresión regular encontrará la primera coincidencia dentro de la cadena). Como tal, el primer carácter de cada línea ambigua aquí se sobrescribe antes de que la línea misma se vea como una coincidencia, y eso evita la coincidencia de expresiones regulares.

Python 2, 199 bytes

l=input()
w=len(l[0])
j="".join(l)
c=set(j)-{" "}
def f(s):
 for h in s:
  i=j.index(h);I=j.rindex(h);o=f(s-{h})
  if{0}>c-s&set(j[i:I:w**(i+w<=I)])and`o`>"Z":return[h]+o
 if{0}>s:return[]
print f(c)

Esto terminó mucho más de lo que inicialmente pensé que sería. Aparte de esto rindex, podría ver esto como un muy buen programa para traducir a Pyth.

Toma una lista de líneas y genera una lista de caracteres. El código genera permutaciones de forma recursiva, asegurándose de que ninguna de las líneas dibujadas se dibuje encima de la línea actual.

El código abusa de muchas características de Python, por ejemplo, tomar wel poder de un booleano, probar conjuntos vacíos al verificar subconjuntos de {0}(ya que mis conjuntos nunca contienen no cadenas) y mi favorito, distinguir cualquier lista de Noneverificar si la representación es mayor queZ .

Código explicado

lines = input()
width = len(lines[0])
joined = "".join(lines)
characters = set(joined) - {" "} # find unique characters except space in input

def solve(chars_left): # returns a solution for the given set of lines
    for try_char in chars_left: # try all lines left

        start_index = joined.index(try_char) # find start position of this line
        end_index = joined.rindex(try_char) # and end position

        step = width ** (start_index + width <= end_index) # take every width'th character if start
                                                           # and end indices differ by at least width

        used_chars = characters - chars_left # find all drawn lines

        line_chars = set(joined[start_index:end_index:step]) # find the characters inside the current line
        missed_chars = used_chars & line_chars # find all lines that are already drawn but should be on
                                               # top of this line

        solution = solve(chars_left - {try_char}) # find solutions if this line was drawn now

        if {0} > missed_chars and `solution` > "Z": # there should be no missed lines and a solution
                                                    # should exist
            return [try_char] + solution # solution found, prepend current character and return

    if {0} > chars_left: # if no lines are left
        return [] # solution found

print solve(characters) # solve for all lines