(Вдохновленный во время рисования на сухой доске стирания)

Вызов:

При наличии входной строки, содержащей символы, которые представляют разные цвета маркеров сухого стирания на белой доске, выведите порядок, в котором они были нарисованы, от первого до последнего.

Входные данные:

Строка, содержащая цвета маркера сухого стирания, которые представлены буквенными буквами (верхние отличаются от строчных, вы можете заменить любые символы, используемые в моих примерах, если каждый цвет имеет отдельную букву). Остальная часть доски будет пустым пространством. Там будет только одна линия каждого цвета на доске. Не будет входов, где все строки перекрывают друг друга (см. Контрольный пример 4). Все линии будут прямыми и горизонтальными или вертикальными.

Выход:

Порядок, в котором линии были нарисованы на доске, от первого до последнего. Если для любого входа есть несколько решений, вы можете вывести любое из них. Вывод может быть отформатирован так, как вы пожелаете: одна строка символов или разделенные пробелами, символами новой строки и т. Д., Если используемые символы совпадают с теми, которые использовались при вводе.

Тестовые случаи:

Вход 1:

  R
  R
BBRBB
  R

Выход 1:

BR

Вход 2:

    GY
    GY
RRRRGYRRR
    GY
    GY
BBBBBBBB
    GY
    GY

Выход 2:

RGYB // or RYGB

Вход 3:

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

Выход 3:

AGPR // or APGR

Вход 4:

 O Y
RRRYR
 O Y
GOGGG
 O Y

Выход 4:

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

Вход 5:

YYYB
   B
   B

Выход 5:

// YB or BY

Правила:

Это код-гольф , поэтому выигрывает самый короткий код в байтах.

Perl 103 + 2 = 105 байт

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

Запуск с -n0(штраф 2 байта).

Объяснение:

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

Здесь есть небольшая тонкость:

   азбука
DDDDDDDDD
   азбука
   азбука
   азбука

Посмотрите на четвертую строку здесь. Если бы порядок записи был BACBD, то там действительно могла бы быть горизонтальная линия Bs, не нарушая ни одного из предположений проблемы (кроме того, что есть только одна линия каждого цвета, что мы не проверяем). Чтобы обойти это, в последнем регулярном выражении мы гарантируем, что каждая строка начинается с буквы (или цифры, или подчеркивания, но это невозможно), и полагаемся на тот факт, что параллельные линии будут найдены слева направо и сверху -вниз (потому что регулярное выражение найдет первое совпадение в строке). Таким образом, первый символ каждой неоднозначной строки здесь перезаписывается до того, как сама строка рассматривается как совпадение, и это предотвращает сопоставление с регулярным выражением.

Python 2, 199 байт

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)

Это закончилось намного дольше, чем я изначально думал. Кроме того, rindexя мог видеть это как очень хорошую программу для перевода на Pyth.

Берет список строк и выводит список символов. Код рекурсивно генерирует перестановки, следя за тем, чтобы ни одна из нарисованных линий не рисовалась поверх текущей линии.

Код злоупотребляет многими функциями Python, например, использует wмощь логического значения, тестирует пустые наборы, проверяя подмножества {0}(поскольку мои наборы никогда не содержат нестроковых значений ), и мой любимый, отличая любой список от Noneпроверки, если его Представление больше, чем Z.

Объясненный код

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