(Zainspirowany podczas rysowania na suchej tablicy do wymazywania)

Wyzwanie:

Biorąc pod uwagę łańcuch wejściowy zawierający znaki reprezentujące różne kolory markerów wymazywania na sucho na białej tablicy, wypisz kolejność, w jakiej zostały narysowane, od pierwszego do ostatniego.

Wejście:

Łańcuch zawierający kolory znaczników wymazywania na sucho, które są reprezentowane przez litery alfabetu (górne są inne niż małe litery, możesz zastąpić dowolne znaki użyte w moich przykładach, o ile każdy kolor ma inną literę). Reszta tablicy będzie białą przestrzenią. Na planszy będzie tylko jedna linia każdego koloru. Nie będzie danych wejściowych, w których wszystkie linie nachodzą na siebie (patrz przypadek testowy 4). Wszystkie linie będą proste i albo poziome, albo pionowe.

Wynik:

Kolejność rysowania linii na planszy, od pierwszej do ostatniej. Jeśli istnieje wiele rozwiązań dla dowolnego wejścia, możesz wyprowadzić dowolne z nich. Dane wyjściowe można sformatować w dowolny sposób: pojedynczy ciąg znaków lub oddzielone spacjami, znakami nowego wiersza itp., O ile użyte znaki są zgodne z tymi, które zastosowano w danych wejściowych.

Przypadki testowe:

Wejście 1:

  R
  R
BBRBB
  R

Wyjście 1:

BR

Wejście 2:

    GY
    GY
RRRRGYRRR
    GY
    GY
BBBBBBBB
    GY
    GY

Wyjście 2:

RGYB // or RYGB

Wejście 3:

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

Wyjście 3:

AGPR // or APGR

Wejście 4:

 O Y
RRRYR
 O Y
GOGGG
 O Y

Wyjście 4:

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

Wejście 5:

YYYB
   B
   B

Wyjście 5:

// YB or BY

Zasady:

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.

Perl, 103 + 2 = 105 bajtów

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

Uruchom z -n0(kara 2 bajty).

Wyjaśnienie:

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

Jedna drobna subtelność tutaj zawiera takie dane wejściowe:

   ABC
DDDDDDDDD
   ABC
   ABC
   ABC

Spójrz na czwartą linię tutaj. Gdyby kolejność pisania była zgodna z BACBD, mogłaby istnieć pozioma linia Bs bez naruszania jakichkolwiek założeń problemu (poza tym, że istnieje tylko jedna linia każdego koloru, coś, czego nie sprawdzamy). Aby obejść ten problem, zapewniamy w ostatnim wyrażeniu regularnym, że każda linia zaczyna się od litery (lub cyfry lub podkreślnika, ale są one niemożliwe), i polegamy na tym, że linie równoległe będą znajdować się od lewej do prawej i od góry -to-bottom (ponieważ wyrażenie regularne znajdzie pierwsze dopasowanie w ciągu). W związku z tym pierwszy znak każdej niejednoznacznej linii jest nadpisywany, zanim sama linia zostanie uznana za dopasowanie, co zapobiega dopasowaniu wyrażenia regularnego.

Python 2, 199 bajtów

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)

Skończyło się to znacznie dłużej, niż początkowo myślałem. Poza tym rindexmogłem postrzegać to jako bardzo dobry program do tłumaczenia na język Pyth.

Pobiera listę wierszy i wyświetla listę znaków. Kod generuje permutacje rekurencyjnie, upewniając się, że żadna z narysowanych linii nie powinna być narysowana nad bieżącą linią.

Kod narusza wiele funkcji Pythona, na przykład przejmuje wmoc logiczną, testuje puste zestawy, sprawdzając podzbiory {0}(ponieważ moje zbiory nigdy nie zawierają ciągów znaków), i moją ulubioną, odróżniając dowolną listę od Nonesprawdzania, czy jej reprezentacja jest większa niż Z.

Wyjaśniony kod

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