(Terinspirasi saat menggambar di papan menghapus kering)

Tantangan:

Diberikan string input yang berisi karakter yang mewakili warna berbeda dari spidol kering pada papan tulis, menampilkan urutan penggambarannya, dari awal hingga akhir.

Memasukkan:

String yang berisi warna marker penghapus kering yang diwakili oleh huruf alfabet (huruf atas berbeda dari huruf kecil, Anda dapat mengganti karakter apa pun yang digunakan dalam contoh saya selama setiap warna memiliki huruf yang berbeda). Sisa papan tulis akan menjadi ruang putih. Hanya akan ada satu garis dari setiap warna per papan. Tidak akan ada input di mana semua baris saling tumpang tindih (Lihat test case 4). Semua garis akan lurus dan horizontal atau vertikal.

Keluaran:

Urutan garis digambar di papan tulis, dari yang pertama ditarik hingga yang terakhir. Jika ada beberapa solusi untuk input apa pun, Anda dapat mengeluarkan salah satu dari mereka. Outputnya dapat diformat lagi yang Anda inginkan: string karakter tunggal atau dipisahkan oleh spasi, baris baru, dll. Selama karakter yang digunakan cocok dengan yang digunakan dalam input Anda.

Kasus uji:

Input 1:

  R
  R
BBRBB
  R

Output 1:

BR

Input 2:

    GY
    GY
RRRRGYRRR
    GY
    GY
BBBBBBBB
    GY
    GY

Output 2:

RGYB // or RYGB

Input 3:

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

Output 3:

AGPR // or APGR

Input 4:

 O Y
RRRYR
 O Y
GOGGG
 O Y

Keluaran 4:

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

Input 5:

YYYB
   B
   B

Output 5:

// YB or BY

Aturan:

Ini adalah kode-golf , jadi kode terpendek dalam byte menang.

Perl, 103 + 2 = 105 byte

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

Jalankan dengan -n0(penalti 2 byte).

Penjelasan:

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

Satu sedikit kehalusan di sini datang dengan input seperti ini:

   ABC
DDDDDDDDD
   ABC
   ABC
   ABC

Lihatlah baris keempat di sini. Jika urutan penulisan adalah BACBD, mungkin akan ada garis horizontalB di sana tanpa melanggar asumsi masalah (selain itu hanya ada satu baris dari setiap warna, sesuatu yang tidak kami periksa). Untuk mengatasi ini, kami memastikan di regex terakhir bahwa setiap baris dimulai dengan huruf (atau digit atau garis bawah, tetapi itu tidak mungkin), dan bergantung pada kenyataan bahwa garis paralel akan ditemukan dari kiri ke kanan dan atas -to-bottom (karena regex akan menemukan kecocokan pertama dalam string). Dengan demikian, karakter pertama dari setiap baris yang ambigu di sini akan ditimpa sebelum garis itu sendiri dilihat sebagai pertandingan, dan yang mencegah pencocokan regex.

Python 2, 199 byte

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)

Ini berakhir jauh lebih lama daripada yang saya pikir awalnya. Terlepas dari rindexsaya bisa melihat ini sebagai program yang sangat bagus untuk diterjemahkan ke dalam Pyth.

Mengambil daftar garis dan menampilkan daftar karakter. Kode menghasilkan permutasi secara rekursif, memastikan bahwa tidak ada garis yang ditarik yang seharusnya ditarik di atas garis saat ini.

Kode ini menyalahgunakan banyak fitur Python, misalnya mengambil wkekuatan boolean, menguji set kosong dengan memeriksa subset dari {0}(karena set saya tidak pernah mengandung non-string), dan favorit saya, membedakan daftar dariNone dengan memeriksa apakah itu representasi lebih besar dari Z.

Kode yang dijelaskan

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