Carve a square from a string

Question

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 code-golf, fewest bytes wins!

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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!

Answer 5

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`));

Answer 6

Brachylog, 16 bytes

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

Try it online!

Answer 7

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.

Answer 8

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

Answer 9

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!

Answer 10

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.

Answer 11

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

Answer 12

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)

Answer 13

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!

Answer 14

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!

Answer 15

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.

Answer 16

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!

Answer 17

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!}

Answer 18

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!)

Answer 19

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!

Answer 20

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.

Answer 21

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!

Answer 22

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.