17
\$\begingroup\$

(Inspired while drawing on a dry erase board)

Challenge:

Given an input string containing characters that represent different colors of dry erase markers on a white board, output the order in which they were drawn, from first to last.

Input:

A string which contains dry erase marker colors which are represented by alphabetical letters (upper ones are different than lowercase, you may substitute any characters used in my examples as long as each color has a distinct letter). The rest of the whiteboard will be white-space. There will only be one line of each color per board. There won't be inputs where all lines overlap each other (See test case 4). All lines will be straight and either horizontal or vertical.

Output:

The order in which the lines were drawn on the board, from the first one drawn to the last one. If there are multiple solutions for any input, you may output any one of them. The output can be formatted anyway you'd prefer: single string of characters or separated by spaces, newlines, etc. as long as the characters used match the ones used in your input.

Test Cases:

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

Output 4:

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

Input 5:

YYYB
   B
   B

Output 5:

// YB or BY

Rules:

This is , so shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ @StewieGriffin There can be as many as the printable ASCII characters (33-127). I used normal colors in my test cases, but since they are characters they don't actually correspond to the actual colors (Red, Green, Yellow, etc), they just represent unique colors (R is a different color from G and Y). \$\endgroup\$ – Yodle Nov 28 '16 at 18:45
  • 1
    \$\begingroup\$ Eh yeah good point, I'll just say alphabetical characters only (65-90 and 97-122). \$\endgroup\$ – Yodle Nov 28 '16 at 18:52
  • \$\begingroup\$ All the lines will be horizontal or vertical, right? You should probably specify that in the question. \$\endgroup\$ – user62131 Nov 28 '16 at 18:54
  • \$\begingroup\$ @ais523 Yes, edited it in. \$\endgroup\$ – Yodle Nov 28 '16 at 18:56
  • \$\begingroup\$ May we assume that the input is padded with spaces to a rectangle? \$\endgroup\$ – PurkkaKoodari Nov 29 '16 at 9:45
5
\$\begingroup\$

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

Run with -n0 (2 byte penalty).

Explanation:

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

One slight subtlety here comes with input like this:

   ABC
DDDDDDDDD
   ABC
   ABC
   ABC

Look at the fourth line here. If the order of writing were BACBD, there could genuinely be a horizontal line of Bs along there without violating any of the assumptions of the problem (other than that there's only one line of each colour, something that we don't check). In order to get around this, we ensure in the last regex that each line starts with a letter (or digit or underscore, but those are impossible), and rely on the fact that parallel lines will be found left-to-right and top-to-bottom (because the regex will find the first match within the string). As such, the first character of each ambiguous line here gets overwritten before the line itself is seen as a match, and that prevents the regex matching.

\$\endgroup\$
  • \$\begingroup\$ Very impressive... Well done! (I was at 161 bytes, with perl -n0E '/.*/;for$i(/(\S)(?=(?:(?:.{@{+}})?(?:\1| ))*(?!.*\1))/gs){/.*/;unless(/$i+[^$i\s]+$i/||/$i(.{@{+}}[^$i ])+.{@{+}}$i/s){$r="$i$r";s/$i/ /g;last}}/\S/?redo:say$r' (which requires the input lines to be right-padded with spaces to be all the same length) ) \$\endgroup\$ – Dada Nov 29 '16 at 19:32
2
\$\begingroup\$

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)

This ended up a lot longer than I initially thought it would. Apart from the rindex I could see this as a very good program to translate into Pyth.

Takes in a list of lines and outputs a list of characters. The code generates permutations recursively, making sure that none of the drawn lines are supposed to be drawn on top of the current line.

The code abuses a lot of Python's features, for example taking w to the power of a boolean, testing for empty sets by checking subsets of {0} (since my sets never contain non-strings), and my favorite, distinguishing any list from None by checking if its representation is greater than Z.

Explained 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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.