3
\$\begingroup\$

Input will be one or more space separated characters followed by a long string on STDIN or as an argument when called from the shell.

a C
WAtcIaElCpVqDRavOUejlgumcRCpfIWlaRFZpIoPYsWjsBSdlYfitfAPHpemiLpjaHheUGpFVQoZCnSCFgvpVzcoibdffoPRoJJwLIjVicPCdcvITXaQDjtMgrxQMZCkZNFmNqwGQYaSyPpdLOkAVHGVoVBiIksZCQHEaIxcRGwpIAmlChuhGEDajeJVXoCwFFuIvhEoqMuwrCDmZPcQxeaqJjynGWVjSaCCxWfupDbbEEFufDyealmbLxKfwlWCsSXwpPtuayxNVCodeEjeCIeHBYioeTogujuUFlWydOwInWGbsvlSwlwgfQaAmNTWPjsgqSCGzsJYfqGklpeLujFyrZJmNymUzpXLTkZcyPgPakAXTTfKlnnTCkjxxSZltwnLMOUCxlHOtLIUTqcbejXqyrwQgMaPUKcHBDZwMrCgwfVZUzxbdODBbBqEbpFLUOcPpVmsgLnfMXRWaddGnK
  • Your task is to line-wrap the string at a suitable length so that there is at least one column completely filled by each input character. All lines should be wrapped to the same length (except possibly the last one if it's shorter.)

In this case, the solution could be wrapping at 50 characters giving the output

WAtcIaElCpVqDRavOUejlgumcRCpfIWlaRFZpIoPYsWjsBSdlY
fitfAPHpemiLpjaHheUGpFVQoZCnSCFgvpVzcoibdffoPRoJJw
LIjVicPCdcvITXaQDjtMgrxQMZCkZNFmNqwGQYaSyPpdLOkAVH
GVoVBiIksZCQHEaIxcRGwpIAmlChuhGEDajeJVXoCwFFuIvhEo
qMuwrCDmZPcQxeaqJjynGWVjSaCCxWfupDbbEEFufDyealmbLx
KfwlWCsSXwpPtuayxNVCodeEjeCIeHBYioeTogujuUFlWydOwI
nWGbsvlSwlwgfQaAmNTWPjsgqSCGzsJYfqGklpeLujFyrZJmNy
mUzpXLTkZcyPgPakAXTTfKlnnTCkjxxSZltwnLMOUCxlHOtLIU
TqcbejXqyrwQgMaPUKcHBDZwMrCgwfVZUzxbdODBbBqEbpFLUO
cPpVmsgLnfMXRWaddGnK

The fifteenth (a) and twenty-seventh (C) all form a single column of the given input characters. The last line may or may not be complete.

  • There can be more than one solutions. Any one of them can be considered valid.

  • Returning the string as-is is NOT allowed. (For those claiming that it forms one-row columns). The columns of the input characters must have at least two rows. You may assume that the input string is longer than 10 characters.

  • If there is no possible solution, your program must indicate this in some way(return status, printing "no solution", etc.) which you must mention.

  • Input will only include [a-zA-Z]

This is


Here's the actual program(python) that I use to generate these strings.

import random

a = 10
b = 50

s = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
for i in xrange(a):
    c = ''
    for j in xrange(b):
        c += (random.choice(s))
    print c

I then rectangle-edit to get columns full of input characters and strip newlines, deleting random number of characters from the end of the last line.

\$\endgroup\$
  • \$\begingroup\$ Hummm... shouldn't you rather say: "at lease three rows"? Because the solution with 469 characters on the first line, a single character on the second line, has "at least two lines", and is valid according to your own example (see the C column in your own example, which is at the right of the end of the last line). \$\endgroup\$ – Thomas Baruchel Mar 12 '14 at 16:23
  • \$\begingroup\$ @ברוכאל Could you please elaborate what you are saying? abcdefghijklmnop newline azc is valid according to my criteria. The more than 1 input characters ensure that the algorithm is correct. That was just to prevent joke answers. By the way, WTF is wrong with your username? \$\endgroup\$ – user80551 Mar 12 '14 at 16:33
  • \$\begingroup\$ Precisely, joke answers are still available. Take your 470 example, format it as "WAtcI... newline K". It is valid, has at least two lines, and you can find many columns with either 'a' or 'C'. I precisely understood that you wanted to prevent joke answers, but they are still possible and it was why I told about "at least three lines". \$\endgroup\$ – Thomas Baruchel Mar 12 '14 at 16:39
  • \$\begingroup\$ My exact wording is The columns of the input characters must have at least two rows \$\endgroup\$ – user80551 Mar 12 '14 at 16:43
  • \$\begingroup\$ Out of curiosity, why do you import time for your generator program? \$\endgroup\$ – undergroundmonorail Mar 13 '14 at 7:11
2
\$\begingroup\$

GolfScript, 73 characters

n%(' '-:C;~:T,,1>{T/zip{.,1>*.&.,1=*}%''*C&C=},.{0=T/n*}{'no solution'}if

Breaks at the first position which is possible. The input must be given on STDIN in the format specified in the question.

Example (online):

X Y
abcdeXfYghijklmnXoYpqrstuvwXxYyzXYZ

abcdeXfYghi
jklmnXoYpqr
stuvwXxYyzX
YZ

Annotated code:

n%               # Split the input at newlines
(' '-:C;         # Extract the first line, remove all spaces
                 # and assign the resulting string to variable C
~:T              # Take the second line and assign this string
                 # to variable T
,,1>             # Makes an array [1 2 3 ... L-1] where L is the 
                 # length of T
{                # A filter block {...}, selects all possible 
                 # line wrap positions from this array
  T/             #   Test the current length by splitting T (input)
                 #   in pieces
  zip            #   Transpose the result (i.e. we now have a array
                 #   of strings representing the columns)
  {              #   For each column
    .,1>*        #     Is the length greater than one, then keep the column
                 #     else transforms it to the empty string (string * 0)
    .&           #     "and"s the string with itself, i.e. the result
                 #     is a string of the distinct characters in the column
    .,1=*        #     If the length is 1 (i.e. only one character) keep
                 #     the column, otherwise reduce it to the empty string
  }%
  ''*            #   Combine the resulting characters into a string again
  C&C=           #   Check if this string contails all characters from C
},
.{               # If the filter returns at least one possible wrap position
  0=             #   Take the first one
  T/n*           #   Split the string and join again with newlines
}{               # Else
  'no solution'  #   Return 'no solution'
}if              # Endif
\$\endgroup\$
  • \$\begingroup\$ My example takes ~5.3 secs on your website but I trust this works. \$\endgroup\$ – user80551 Mar 12 '14 at 16:14
  • \$\begingroup\$ Impressive ! Could we have an explanation, plz ? \$\endgroup\$ – guy777 Mar 13 '14 at 16:27
  • \$\begingroup\$ @guy777 Added some explanation to the answer. \$\endgroup\$ – Howard Mar 14 '14 at 7:18
0
\$\begingroup\$

APL (65)

⍞{1∊r←∧⌿↑∨/¨¨∧⌿¨¨↓⍵∘.=z←⍺∘{z⍵⍴⍺↑⍨⍵×z←⌈⍵÷⍨⊃⍴⍺}¨⍳¯1+⍴⍺:⊃r/z⋄0}⍞~' '

Example: (smaller one for legibility)

      ⍞{1∊r←∧⌿↑∨/¨¨∧⌿¨¨↓⍵∘.=z←⍺∘{z⍵⍴⍺↑⍨⍵×z←⌈⍵÷⍨⊃⍴⍺}¨⍳¯1+⍴⍺:⊃r/z⋄0}⍞~' '
r a b
abracadabra!
abracad
abra!  

Explanation:

  • ⍞{...}⍞~' ': Read two lines. Remove the spaces from the first line and pass it to the function as its right argument, pass the second line unaltered as the left argument.
    • ⍺∘{...}¨⍳¯1+⍴⍺: For each number 1..length ⍺-1, split into that many columns:
    • z←⌈⍵÷⍨⊃⍴⍺: calculate how many columns we'll need and store in z.
    • ⍺↑⍨⍵×z: extend with spaces to the length ⍵×z (fill the last line up with spaces if necessary)
    • z⍵⍴: reshape the result into z lines and columns
    • z←: store the array of matrices in z
    • ⍵∘.=z: for each character in (the input characters), see which elements in z match it
    • ∧⌿¨¨↓: take the logical and of each column of each matrix for each input character
    • ∨/¨¨: take the logical or of each element in the result (giving for each character and each matrix whether that character was matched in that matrix)
    • r←∧⌿↑: for each matrix, see whether or not all input characters were matched. Store a bitmask over the matrices in r.
    • 1∊r...:: If the bitmask contains a 1, there was a result, so:
    • ⊃r/z: Filter z by r and take the first element (displaying the result with the smallest amount of columns.)
    • ⋄0: otherwise, return '0'.
\$\endgroup\$
0
\$\begingroup\$

Ruby, 161

Why not use one clever regular expressions instead of "brute-forcing" and checking ;)

Online version

d,s=STDIN.read.split("\n")
l = s.size
puts s.scan(/.{,#{d.split.map{|c|(0..l-2).map{|n|n if /^.{,#{n}}(#{c+?.*n})*.{,#{n-1}}$/=~s}}.reduce(&:&).compact.min+1}}/)
\$\endgroup\$
  • \$\begingroup\$ It seems to be broken: try it on a C\n..C...a..C..a and it finds ..C...a\n..C..a which is not a solution. \$\endgroup\$ – Howard Mar 14 '14 at 7:21
0
\$\begingroup\$

Python (211 203)

This is my first codegolf so I expect many possible improvements. I have designed two version which use different systems to print out the solution.

The input is done via 2 input()s so you would have to put quotes before and after the strings.

Version 1 (211 203)

c=input().split();i=input();l=range(len(i)//2)
for k in c:l=[w for w in l if any(all(k==y for y in i[x::w])for x in range(w))]
print'\n'.join(len(l)and __import__('textwrap').wrap(i,l[0])or'No solution')

Explanation:

chars = input().split()
inp = input()
wrapAfter = range(len(inp)//2) # min 2 (full) lines
for char in chars:
    wrapAfter = [wrapped for wrapped in wrapAfter if any( # filter the possiblities left
        all(char == cAt for cAt in inp[columnNbr::wrapped]) # wrap the line and check that 
                                                            # cAt is char
            for columnNbr in range(wrapped))] # for all columns

# print a joined version of all strings that are returned
import textwrap
wrapped = wrapAfter[0]
print('\n'.join(textwrap.wrap(inp, wrapped) if len(wrapAfter) # if there are wrappingvalues left
                                                              # we wrap the string
                else 'No solution')) # else we print 'No solution'

Version 2 (245 236 219 208)

r=range;c=input().split();i=input();z=len(i);l=r(z//2)
for w in l:
 if set(s[0] for s in(i[x::w]for x in r(w))if len(set(s))==1)>=set(c):print'\n'.join(i[x:x+w]for x in r(0,z,w));break
else:print'No solution'

Explanation:

chars = input().split()
inp = input()
length = len(inp)
wrapAfter = range(length//2)
# we go through every possible wrapping
for wrap in wrapAfter:
    # if the set of all  character for that a colum exists that is purely made up of
    # this char is a superset of chars then we won
    if set(s[0] for s in
            # makes a generator that generates all columns
            (inp[x::wrap]for x in range(wrap)) 
            # if all characters in the column are equal
            if len(set(s))==1) >= set(chars):
        print('\n'.join(inp[x:x+wrap]for x in range(0,length,wrap))) # textwrap is 
                                                                   # slower as we
                                                                   # replace range
        break
# if the loop wasn't broken nothing was found
else:
    print('No solution')
\$\endgroup\$
  • \$\begingroup\$ You don't have to use print as a function, removing the parens can save one char \$\endgroup\$ – user80551 Mar 14 '14 at 2:59
  • \$\begingroup\$ Also, range() returns a list so you don't have to do list(range()) \$\endgroup\$ – user80551 Mar 14 '14 at 3:00
  • \$\begingroup\$ You could use a variable for len(i) as you use it twice \$\endgroup\$ – user80551 Mar 14 '14 at 3:02
  • \$\begingroup\$ that is Python 3 syntax. Don't ask me why I didn't use Python 2.7. Thanks for the input \$\endgroup\$ – WorldSEnder Mar 14 '14 at 6:44

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.