21
\$\begingroup\$

Your challenge today is to take a multiline string, and output the biggest square contained within the string that includes the top left corner.

A square string is one where:

  • Each line has the same number of characters
  • The number of characters on each line is equal to the number of lines.

Consider the following possible input string:

abcde
fgh
asdf
foobar

The largest square you can take from it that includes the first character (the a in the topleft corner) is this:

abc
fgh
asd

There can't be a square of side-length 4, because the second line isn't long enough. Now consider this potential input:

a
bcd
edf
ghi

The biggest square here is just a. The 3x3 square formed in the bottom doesn't contain the very first character, and doesn't count.

Here's a few more test cases:

a

a

abc
def
gh

ab
de

ab
cd

ab
cd

abcde
fghij
klm
no

abc
fgh
klm

a
b

a

You may require input to be delimited by your choice of LF, CR, or CRLF.

The newline character(s) are not considered part of the line's length.

You may require there to be or to not be a trailing newline in input, which doesn't count as an additional line.

Input is a string or 1D char array; it is not a list of strings.

You may assume input is non-empty and all lines are non-empty, and that it only contains printable ASCII, including spaces and newlines (for the line delimiter) but not tabs.

This is , fewest bytes wins!

\$\endgroup\$
  • \$\begingroup\$ related \$\endgroup\$ – Pavel Nov 8 '17 at 18:17
  • 5
    \$\begingroup\$ +1 for an interesting challenge, -1 for strict I/O \$\endgroup\$ – Dennis Nov 8 '17 at 21:10
  • \$\begingroup\$ @Dennis not every solution needs to use .split('\n') so I don't see why some should get it for free. \$\endgroup\$ – Pavel Nov 8 '17 at 22:06
  • 2
    \$\begingroup\$ It's not (just) about having to add bytes for boring boilerplate. Some approaches (e.g., recursive functions) become completely impractical if there's pre- or postprocessing. \$\endgroup\$ – Dennis Nov 8 '17 at 22:16
  • \$\begingroup\$ @Dennis I hadn't thought about it like that. Do you think I should change it now, or is it too late? \$\endgroup\$ – Pavel Nov 8 '17 at 22:19

22 Answers 22

5
\$\begingroup\$

Brachylog, 11 bytes

ṇ⊇ᵐẹa₀ṁcᵐ~ṇ

Try it online!

Explanation

ṇ             Split on linebreaks
 ⊇ᵐ           Take a subset of each line
   ẹ          Split the lines into list of chars
    a₀        Take a prefix of this list of lists of chars
      ṁ       It is a square matrix
       cᵐ     Concatenate the list of chars back into strings
         ~ṇ   Join the strings with linebreaks
\$\endgroup\$
7
\$\begingroup\$

Husk, 13 bytes

►oΛ≈S+TzṀ↑Nḣ¶

Try it online!

Explanation

►oΛ≈S+TzṀ↑Nḣ¶  Implicit input, say "ab\nc".
            ¶  Split at newlines: ["ab","c"]
           ḣ   Take prefixes: [["ab"],["ab","c"]]
       z  N    Zip with [1,2,3..
        Ṁ↑     by taking that many characters from each row: [["a"],["ab","c"]]
►o             Find rightmost element that satisfies this:
  Λ            all strings in
    S+T        the list concatenated to its transpose
   ≈           have the same length: ["a"]
               Implicitly print separated by newlines.
\$\endgroup\$
  • 1
    \$\begingroup\$ How is this even a programming language - you've just pasted some obscure unicode characters! ;) \$\endgroup\$ – turnip Nov 9 '17 at 11:00
  • 1
    \$\begingroup\$ @Petar Welcome to the world of golfing languages, which are designed specifically to use as few bytes as possible to do a certain task. Part of this is to have a custom code page, so that there is a character for each possible byte, instead of the usual 95 printable ASCII. But don't worry, there are also much more legible golfing languages; for example my MATL entry [/shameless self-promotion] \$\endgroup\$ – Sanchises Nov 9 '17 at 11:39
5
\$\begingroup\$

GNU sed, 106 + 1 94 + 2 = 96 bytes

+2 bytes for -rz flags. Uses unprintable characters NUL and BEL, shown as @ and # here. See below for an xxd dump.

Thanks to @seshoumara for sending me down the path to -z.

s/^/@/gm
s/.*/#&\n/
:B
s/@(.)/\1@/mg
s/#(.+\n)/\1#/m
/#.*@./M!b
/@\n.*#/!bB
:
s/@[^\n]*|#.*//g

Try it online!

Explanation

This works by inserting two cursors into the text—one to step over lines and one to step over columns. The cursors are represented by NUL (0x00) and BEL (0x07), respectively, but in the below examples I'll use @ and #. Suppose we have this input:

abcde
fgh
asdf
foobar

The BEL cursor is inserted before the 0th column and the BEL cursor before the 0th line (here I've kept the columns aligned for legibility; but in actuality there is no left padding):

#@abcde
 @fgh
 @asdf
 @foobar

In a loop, the cursors are moved one character to the right and one line down, respectively:

 a@bcde
#f@gh
 a@sdf
 f@oobar
 ab@cde
 fg@h
#as@df
 fo@obar
 abc@de
 fgh@
 asd@f
#foo@bar

After each iteration, it checks two conditions:

  1. On the line with the line cursor, is there a column cursor and can the column cursor move to the right?
  2. On the lines before the line cursor, can every column cursor move to the right?

If either condition is false, the loop ends. The script finishes by deleting everything after @ on each line and everything after # in the pattern space.

xxd dump

00000000: 732f 5e2f 002f 676d 0a73 2f2e 2a2f 0726  s/^/./gm.s/.*/.&
00000010: 5c6e 2f0a 3a42 0a73 2f00 282e 292f 5c31  \n/.:B.s/.(.)/\1
00000020: 002f 6d67 0a73 2f07 282e 2b5c 6e29 2f5c  ./mg.s/.(.+\n)/\
00000030: 3107 2f6d 0a2f 072e 2a00 2e2f 4d21 620a  1./m./..*../M!b.
00000040: 2f00 5c6e 2e2a 072f 2162 420a 3a0a 732f  /.\n.*./!bB.:.s/
00000050: 005b 5e5c 6e5d 2a7c 072e 2a2f 2f67       .[^\n]*|..*//g
\$\endgroup\$
  • \$\begingroup\$ You can remove the first loop, A, because the statement says you have to read the input as a string, so you can receive "line1\nline2\nline3" etc. Other answers did this too. That should get the count below 100 :) \$\endgroup\$ – seshoumara Nov 8 '17 at 22:37
  • \$\begingroup\$ @seshoumara Other answers do line1\nline2\nline3 where \n is \x5C\x6E? Which? \$\endgroup\$ – Jordan Nov 8 '17 at 22:40
  • \$\begingroup\$ Can you give me a link? (Click on "share" at the bottom of any answer.) Or show me in a TiO what you mean? In all of the Python and PHP answers I see \n is interpreted as a newline character (\x0A, not \x5C\x6E) and I can't find a way to make sed take input with newline characters as a single line. \$\endgroup\$ – Jordan Nov 8 '17 at 23:04
  • \$\begingroup\$ @seshoumara Hah, nevermind, I just remembered the -z flag. Thanks! \$\endgroup\$ – Jordan Nov 8 '17 at 23:09
4
\$\begingroup\$

Python 2, 81 bytes

l=input().split('\n')
i=0
while zip(*l[:i+1])[i:]:i+=1
for x in l[:i]:print x[:i]

Try it online!


An interesting method, but 2 bytes longer.

Python 2, 83 bytes

l=input().split('\n')
while len(zip(*l))<len(l):l.pop()
for x in l:print x[:len(l)]

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Doesn't input only read one line? \$\endgroup\$ – Pavel Nov 9 '17 at 15:14
  • \$\begingroup\$ @Pavel, if you look at the online example, you can see it is using explicit newline characters to keep the input a one-line string. Probably opting for this method because raw_input() would add more bytes. \$\endgroup\$ – Xavier Dass Nov 10 '17 at 0:46
4
\$\begingroup\$

JavaScript (ES6), 77 bytes

f=(s,i=1,m=s.match(`^${`(.{${i}}).*
`.repeat(i)}`))=>m?f(s,i+1)||m.slice(1):0

Recursively uses a regular expression to search for a larger and larger square until none is found.

The regular expression would be this for a 3x3 square:

^(.{3}).*
(.{3}).*
(.{3}).*

Input is expected to end with a newline, and output is a list.

Explanation:

f = (s,                                            //input
     i = 1,                                        //start searching for a 1x1 square
     m = s.match(`^${`(.{${i}}).*\n`.repeat(i)}`)  //match on the regex
    )=>
    m ? f(s, i+1)                   //if there's a match, recurse on the next-sized square
        || m.slice(1) :             //if there's not a next-sized square, return the match
        0                           //no match for this square, so stop recursing

Snippet:

f=(s,i=1,m=s.match(`^${`(.{${i}}).*
`.repeat(i)}`))=>m?f(s,i+1)||m.slice(1):0

console.log(f(`abcde\nfgh\nasdf\nfoobar`));
console.log(f(`a\nbcd\nedf\nghi\n`));
console.log(f(`a\n`));
console.log(f(`abc\ndef\ngh\n`));
console.log(f(`ab\ncd\n`));
console.log(f('abcde\nfghij\nklm\nno'));
console.log(f(`a\nb\n`));

\$\endgroup\$
3
\$\begingroup\$

Brachylog, 16 bytes

ṇ{ẹa₀ᵐa₀ṁ}ᶠtcᵐ~ṇ

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Explanation, please? \$\endgroup\$ – Pavel Nov 8 '17 at 20:24
3
\$\begingroup\$

Perl 5, 84 bytes

chomp(@a=<>);map$.&&=y///c>$i,@a[0..$i]while$.&&$i++<$#a;say/(.{$i})/ for@a[0..$i-1]

Try it online!

Fulfills the "abcde\nfghij\nklm\nno" test case.

\$\endgroup\$
  • \$\begingroup\$ you could use chop instead of chomp and ++$i<@a instead of $i++<$#a \$\endgroup\$ – Nahuel Fouilleul Nov 9 '17 at 11:05
3
\$\begingroup\$

R, 84 83 81 76 bytes

-5 bytes porting Dennis' approach with sum

cat(substr(x<-readLines(),1,m<-sum(cummin(nchar(x))>=seq(x)))[1:m],sep='\n')

Try it online!

reads from stdin, prints to stdout without a trailing newline.

Slightly ungolfed:

x <- readLines()                    # read in input one line at a time;
                                    # saved as a vector of strings
minChar <- cummin(nchar(x))         # rolling minimum of all line lengths
lineNum <- seq(x)                   # line number
mins <- minChar>=lineNum            # the min between the line number and the line lengths
m <- sum(mins)                      # the sum of those is the size of the square
cat(substr(x,1,m)[1:m],sep='\n')    # print the first m characters of the first m lines,
                                    # and join with newlines

\$\endgroup\$
3
\$\begingroup\$

C (gcc), 162 159 151 147 144 142 137 bytes

There must be some strokes to golf away here...

i,l=9;char*p,s[9][8];main(t){for(p=s;~(*p=getchar());)p=*p<32?*p=0,l=(t=strlen(s+i))<l?t:l,s[++i]:p+1;for(i=0;i<l;puts(s+i++))s[i][l]=0;}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Can !=-1 be >-1 or does getchar() output values smaller than minus one? Could it even be +1? \$\endgroup\$ – Jonathan Frech Nov 8 '17 at 19:27
  • \$\begingroup\$ Potential 158 bytes. \$\endgroup\$ – Jonathan Frech Nov 8 '17 at 19:30
  • \$\begingroup\$ @JonathanFrech I can use ~ to detect minus one. \$\endgroup\$ – cleblanc Nov 8 '17 at 19:54
  • 1
    \$\begingroup\$ @RickHitchcock Seems to work in the latest golf version. \$\endgroup\$ – cleblanc Nov 8 '17 at 20:19
2
\$\begingroup\$

Jelly, 15 bytes

L€«\‘>Jx@Z
ỴÇÇY

Try it online!

How it works

ỴÇÇY        Main link. Argument: s (string)

Ỵ           Split s at linefeeds, yielding a string array.
 Ç          Apply the helper link.
  Ç         Apply the helper link again.
   Y        Join, separating by linefeeds.


L€«\‘>Jx@Z  Helper link. Argument: A (string array/2D character array)

L€          Compute the length of each row/line.
  «\        Take the cumulative minimum.
    ‘       Increment each minimum.
      J     Indices; yield [1, ..., len(A)].
     >      Perform elementwise comparison. If the output should have n lines, this
            yields an array of n ones and len(A)-n zeroes.
         Z  Zip/transpose A.
       x@   For each string t in the result to the right, repeat its characters as
            many times as indicated in the result to the left, discarding all but
            the first n characters.
\$\endgroup\$
2
\$\begingroup\$

Java 8, 150 bytes

s->{String q[]=s.split("\n"),r="";int l=q[0].length(),i=0,t;for(;i<l;l=t<l?t:l)t=q[i++].length();for(i=0;i<l;)r+=q[i++].substring(0,l)+"\n";return r;}

Explanation:

Try it here.

s->{                          // Method with String as both parameter and return-type 
  String q[]=s.split("\n"),   //  Split the input on new-lines, and put it in an array
         r="";                //  Result-String, starting empty
  int l=q[0].length(),        //  Length of the lines, starting at the length of line 1
      i=0,                    //  Index-integer, starting at 0
      t;                      //  Temp integer
  for(;i<l;                   //  Loop (1) from 0 to `l` (exclusive)
      l=t<l?                  //    After every iteration: if `t` is smaller than `l`:
         t                    //     Change `l` to `t`
        :                     //    Else:
         l)                   //     Leave `l` the same
    t=q[i++].length();        //   Set `t` to the length of the current line
                              //  End of loop (1) (implicit / single-line body)
  for(i=0;i<l;                //  Loop (2) from 0 to `l` (the determined square dimension)
    r+=                       //   Append the result-String with:
       q[i++].substring(0,l)  //    The current row chopped at `l-1`
       +"\n"                  //    + a new-line
  );                          //  End of loop (2)
  return r;                   //  Return the result-String
}                             // End of method
\$\endgroup\$
2
\$\begingroup\$

MATL, 33 bytes

10-~ft1)wdhqY<tn:vX<X>:GYbowt3$)c

Try it online!

My spidey sense tells me that there's probably a shorter way (I'm thinking something with Ybo right from the start)... Requires a newline at the end. (Note: I over-engineered this a bit, as this will handle empty lines as well, which is not required. I'll see if I can reduce the bytecount, because in code golf, it's not a feature, but a bug)

\$\endgroup\$
  • 1
    \$\begingroup\$ @Pavel Guiseppe was referring to another version, which I rolled back because it indeed had a bug. \$\endgroup\$ – Sanchises Nov 9 '17 at 19:02
1
\$\begingroup\$

Python 2, 132 bytes

def f(s):s=s.split("\n");return["\n".join([l[:j+1]for l in s[:j+1]])for j,v in enumerate(s[0])if all(len(l)>j for l in s[:j+1])][-1]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 2, 103 bytes

def f(i):
 i=i.split('\n');x=0
 while all(v[x:]for v in i[:x+1])*i[x:]:x+=1
 for v in i[:x]:print v[:x]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 95 bytes

f=
s=>(g=s=>s.slice(0,a.findIndex((e,i)=>a.some((s,j)=>j<=i&!s[i]))))(a=s.split`
`).map(g).join`
`
<textarea oninput=o.textContent=f(this.value+`\n`)></textarea><pre id=o>

Requires a trailing newline in input.

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 81 bytes

Column[For[i=1,d=c;MatrixQ[c=StringExtract[#,"\n"->;;i,""->2;;i+1]],i++];Row/@d]&

Try it online!

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog), 25 bytes*

Tacit prefix function. Returns a matrix.

(↑↑⍨2⍴(⌊/≢,≢¨))⎕AV[3]∘≠⊆⊢

Try it online!

It is really an atop of two independent functions, namely ⎕AV[3]∘≠⊆⊢ which deals with the awkward input format and ↑↑⍨2⍴(⌊/≢,≢¨) which does the actual interesting work.

⎕AV[3]∘≠ difference from LF (the third element of the Atomic Vector – the character set)

 partitions (substrings beginning at values larger than their predecessor and drop at 0s)

 the argument

() apply the following tacit function:

2⍴() reshape the following to length 2:

  ⌊/ the minimum of

   the number of strings

  , followed by

  ≢¨ the number of characters in each string

↑⍨ take that many rows and columns from

 the strings mixed together to form a matrix (padding with spaces)


* In Classic with ⎕ML (Migration Level) 3 (default on many systems) and substituting for and for the leftmost . Tio!

\$\endgroup\$
  • \$\begingroup\$ If it's the same length in Dyalog Classic you might as well say it's Dyalog Classic and not use the footnote. \$\endgroup\$ – Pavel Nov 9 '17 at 0:31
  • \$\begingroup\$ @Pavel Both Classic and ⎕ML←3 are deprecated, so I'd rather show the language as it would normally appear. In fact, almost all my Dyalog APL solutions assume Classic just because we count bytes instead of characters, though even the Unicode version assigns meaning to less than 256 characters. \$\endgroup\$ – Adám Nov 9 '17 at 0:51
1
\$\begingroup\$

PHP, 123 bytes

for(;preg_match("#^(\S{".++$i."}.*
){"."$i}#",$s="$argv[1]
"););while($k<$i-1)echo substr(split("
",$s)[+$k++],0,$i-1),"
";

requires PHP 5.4, 5.5 or 5.6. Replace split with explode for later PHP.

Run with php -nr '<code> '<string>'
or try it online. (Make sure you select a suiting PHP version!)

\$\endgroup\$
1
\$\begingroup\$

Haskell, 92 88 bytes

unlines.f.lines
f s|let t=take$until(all.(.l).(<=)<*>(`take`s))pred$l s=t<$>t s
l=length

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 60 +5 (-0777p) bytes

$.++while/^(.{$.}.*
){$.}/;$_=join"
",(/.{$.}/gm)[0..--$.-1]

Try it online

  • The last line of input must end with a newline in case it belongs to output.
  • In case of two consecutive newlines -00 may option be changed by -0777.
\$\endgroup\$
  • \$\begingroup\$ Two consecutive newlines is possible, so you'll need -0777. What do -00 and -0777 do, anyway. \$\endgroup\$ – Pavel Nov 9 '17 at 15:09
  • \$\begingroup\$ -0 is to specify the record separator in octal format 777 is a special value to indicate no separator so the whole file is read, 0 is another special value to indicate "paragraph mode", separator is more than 1 consecutive newlines \$\endgroup\$ – Nahuel Fouilleul Nov 9 '17 at 15:36
1
\$\begingroup\$

Perl 6, 158 140 bytes

my$c;for ^(my@b=lines).elems {any(@b.head(++$c).map({.substr(0,$c).chars <$c}))&&$c--&&last;};say @b.head($c).map({.substr(0,$c)}).join("
")

Try it online!

Hooray for my first Perl 6 answer. I'll play around with some command line options to see if I can golf this a bit more. All help saving bytes is welcome!

\$\endgroup\$
1
\$\begingroup\$

Scala, 201 bytes

type S=String
def c(s:S):S={val? =s split "\n"
var(z,q:Seq[S])=(Seq(?size,?(0).size).min,Nil)
while(1<2){?map(i=>{if(i.size>=z)q=q:+i.take(z)
if(q.size==z)return q mkString "\n"})
q=Nil;z-=1}
return""}

Try it online!

First time golfing in this language, so maybe not the greatest.

\$\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.