(Inspirado ao desenhar em uma placa de apagamento a seco)

Desafio:

Dada uma sequência de entrada contendo caracteres que representam cores diferentes de marcadores de apagamento a seco em um quadro branco, imprima a ordem em que foram desenhados, do primeiro ao último.

Entrada:

Uma sequência que contém cores de marcador de apagamento a seco, representadas por letras alfabéticas (as maiúsculas são diferentes das minúsculas, você pode substituir qualquer caractere usado nos meus exemplos, desde que cada cor tenha uma letra distinta). O restante do quadro branco terá espaço em branco. Haverá apenas uma linha de cada cor por cartão. Não haverá entradas nas quais todas as linhas se sobreponham (consulte o caso de teste 4). Todas as linhas serão retas e horizontais ou verticais.

Resultado:

A ordem em que as linhas foram desenhadas no quadro, desde a primeira até a última. Se houver várias soluções para qualquer entrada, você poderá produzir qualquer uma delas. A saída pode ser formatada da maneira que você preferir: sequência única de caracteres ou separada por espaços, novas linhas, etc., desde que os caracteres usados ​​correspondam aos usados ​​na sua entrada.

Casos de teste:

Entrada 1:

  R
  R
BBRBB
  R

Saída 1:

BR

Entrada 2:

    GY
    GY
RRRRGYRRR
    GY
    GY
BBBBBBBB
    GY
    GY

Saída 2:

RGYB // or RYGB

Entrada 3:

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

Saída 3:

AGPR // or APGR

Entrada 4:

 O Y
RRRYR
 O Y
GOGGG
 O Y

Saída 4:

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

Entrada 5:

YYYB
   B
   B

Saída 5:

// YB or BY

Regras:

Isso é código-golfe , então o código mais curto em bytes vence.

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

Corra com -n0(penalidade de 2 bytes).

Explicação:

# -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

Uma ligeira sutileza aqui vem com entradas como estas:

   abc
DDDDDDDDD
   abc
   abc
   abc

Veja a quarta linha aqui. Se a ordem de escrita fosse BACBD, realmente poderia haver uma linha horizontal de Bs por lá sem violar nenhuma das suposições do problema (exceto que só existe uma linha de cada cor, algo que não verificamos). Para contornar isso, garantimos no último regex que cada linha começa com uma letra (ou dígito ou sublinhado, mas são impossíveis) e confiamos no fato de que linhas paralelas serão encontradas da esquerda para a direita e superior -to-bottom (porque o regex encontrará a primeira correspondência dentro da string). Dessa forma, o primeiro caractere de cada linha ambígua aqui é sobrescrito antes que a própria linha seja vista como uma correspondência, e isso impede a correspondência da expressão regular.

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)

Isso acabou muito mais do que eu pensava inicialmente. Além do que rindexeu pude ver, esse é um programa muito bom para se traduzir em Pyth.

Pega uma lista de linhas e gera uma lista de caracteres. O código gera permutações recursivamente, certificando-se de que nenhuma das linhas desenhadas deva ser desenhada no topo da linha atual.

O código abusa de muitos recursos do Python, por exemplo, levando wao poder de um booleano, testando conjuntos vazios verificando subconjuntos de {0}(já que meus conjuntos nunca contêm não-strings) e o meu favorito, distinguindo qualquer lista Noneverificando se representação é maior que Z.

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