(Inspiriert beim Zeichnen auf einem trockenen Löschbrett)

Herausforderung:

Geben Sie bei einer Eingabezeichenfolge, die Zeichen enthält, die verschiedene Farben von Trockenlöschmarkierungen auf einer weißen Tafel darstellen, die Reihenfolge aus, in der sie vom ersten bis zum letzten Mal gezeichnet wurden.

Eingang:

Eine Zeichenfolge mit Farben für Trockenlöschmarkierungen, die durch alphabetische Buchstaben dargestellt werden (Großbuchstaben unterscheiden sich von Kleinbuchstaben. Sie können alle in meinen Beispielen verwendeten Zeichen ersetzen, sofern jede Farbe einen eigenen Buchstaben hat). Der Rest des Whiteboards ist weißer Raum. Es wird nur eine Linie von jeder Farbe pro Tafel geben. Es wird keine Eingabe geben, bei der sich alle Zeilen überlappen (siehe Testfall 4). Alle Linien sind gerade und entweder horizontal oder vertikal.

Ausgabe:

Die Reihenfolge, in der die Linien auf der Tafel gezeichnet wurden, von der ersten bis zur letzten. Wenn es für eine Eingabe mehrere Lösungen gibt, können Sie eine davon ausgeben. Die Ausgabe kann wie gewünscht formatiert werden: einzelne Zeichenfolgen oder durch Leerzeichen, Zeilenumbrüche usw. getrennt, sofern die verwendeten Zeichen mit den in Ihrer Eingabe verwendeten Zeichen übereinstimmen.

Testfälle:

Eingang 1:

  R
  R
BBRBB
  R

Ausgang 1:

BR

Eingang 2:

    GY
    GY
RRRRGYRRR
    GY
    GY
BBBBBBBB
    GY
    GY

Ausgang 2:

RGYB // or RYGB

Eingang 3:

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

Ausgang 3:

AGPR // or APGR

Eingang 4:

 O Y
RRRYR
 O Y
GOGGG
 O Y

Ausgang 4:

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

Eingang 5:

YYYB
   B
   B

Ausgang 5:

// YB or BY

Regeln:

Das ist Code-Golf , also gewinnt der kürzeste Code in 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

Laufen Sie mit -n0(2-Byte-Strafe).

Erläuterung:

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

Eine leichte Subtilität kommt hier mit Eingabe wie folgt:

   ABC
DDDDDDDDD
   ABC
   ABC
   ABC

Schauen Sie sich hier die vierte Zeile an. Wenn die Schreibreihenfolge BACBD wäre, könnte es tatsächlich eine horizontale Linie von Bs geben, ohne die Annahmen des Problems zu verletzen ( ansonsten gibt es von jeder Farbe nur eine Linie, die wir nicht überprüfen). Um dies zu umgehen, stellen wir im letzten regulären Ausdruck sicher, dass jede Zeile mit einem Buchstaben (oder einer Ziffer oder einem Unterstrich, die jedoch nicht möglich sind) beginnt , und verlassen uns darauf, dass parallele Zeilen von links nach rechts und von oben gefunden werden -to-bottom (weil der Regex die erste Übereinstimmung in der Zeichenfolge findet). Als solches wird das erste Zeichen jeder mehrdeutigen Zeile hier überschrieben, bevor die Zeile selbst als Übereinstimmung angesehen wird, und dies verhindert die Regex-Übereinstimmung.

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)

Das endete viel länger als ich ursprünglich gedacht hatte. Abgesehen davon rindexkonnte ich dies als ein sehr gutes Programm ansehen, um es in Pyth zu übersetzen.

Nimmt eine Liste von Zeilen auf und gibt eine Liste von Zeichen aus. Der Code generiert rekursiv Permutationen, wobei sichergestellt wird, dass keine der gezeichneten Linien über der aktuellen Linie liegen soll.

Der Code missbraucht viele Funktionen von Python, z. B. wdie Potenz eines Booleschen, das Prüfen auf leere Mengen durch Überprüfen von Teilmengen von {0}(da meine Mengen niemals Nicht-Zeichenfolgen enthalten) und von meinem Favoriten, um Listen von Listen zu unterscheiden, Noneindem überprüft wird, ob sie leer sind Darstellung ist größer als Z.

Erklärter Code

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