# Alice's First Code Review

Alice is an intern in a company that uses Brainfuck as a primary language for both client-side and server-side development. Alice just has written her first code and she's a bit nervous as she's getting ready for her first code review.

Alice wants to make her code properly formatted and look nice, but she has no time to read the 328-pages company code style guide, so she decided to format it as a perfect square. Alas, code length may be insufficient to form a square, so she decided to leave a rectangular gap in the middle. Gaps must be perfectly centered and as close to square as possible.

### Examples

++++++         +++++         +++++         +++++         +++++         +++++
++++++         +++++         +++++         +  ++         ++ ++         +++++
++++++         ++ ++         +   +         +  ++         +   +
++++++         +++++         +++++         +++++         ++ ++         +++++
++++++         +++++         +++++         +++++         +++++         +++++

Perfect         OK         Acceptable   Unacceptable    No way!        Nope.


Write a program or a function to help Alice. Given Alice's code as an input string, output properly formatted code as described below if possible. If formatting is impossible, output crying emoji :~(.

This is so answers are scored in bytes with fewer bytes being the aim.

### Constraints

1. Your program or function should take a single string as an input and output one or more lines of text (or return multi-line string or array of strings, if you implement a function).
2. Input string may contain any ASCII characters including whitespaces.
3. All whitespaces in input must be ignored. They shouldn't count for code length and they shouldn't be used in output.
4. Input string contains at least one non-whitespace character.
5. Formatted code must have the same non-whitespace characters in the same order as in input code.
6. Formatted code must be a perfect square, i.e. all lines should have same length, and number of lines should be equal to the lines' length.
7. Formatted code may contain a gap in the middle.
8. Only space characters (ASCII code 32) may be used in the gap.
9. Gap (if present) must be rectangular.
10. Every line of formatted code must contain at least one non-whitespace character, i.e. gap width must be strictly less than square width (gap 5x1 is unacceptable for 5x5 square).
11. Gap should be horizontal, i.e. gap width should be greater than or equal to gap height.
12. Gap must be perfectly centered.
13. Consequently gap width and height parity should be the same as square width parity (for example for 5x5 square gap may be 1x1, 3x1, or 3x3).
14. If possible, output square with no gap at all.
15. In case of multiple solutions, choose one with gap closest to square, i.e. difference between gap width and gap height is minimal (for example: gap 10x10 is more preferable than 8x6, and 8x6 is more preferable than 6x2).
16. If still there's a tie, choose solution with minimal gap area (for example gap 2x2 is more preferable than 4x4).
17. If it is impossible to format code at all, output :~(.
18. Newline after last line is optional.
19. [New] You may safely assume that any character with code below 33 is a white-space. I hope it will help you for golfing.

### Tests

Input           Output      Code length     Comment

+++++++++       +++                   9     Alice is lucky,
+++                         her code perfectly fits a square.
+++

++++++++        +++                   8     Though code length isn't enough for a square,
+ +                         a small gap fixes it.
+++

++++++          :~(                   6     No luck, code cannot be formatted.

Hello,          Hell                 12     Input may contain any ASCII characters,
World!          o  ,                        but whitespaces in input should be ignored.
W  o
rld!

+++++ + +++++   +++++                22     Gap is not required to be a square,
+++++ + +++++   +++++                       it can be a rectangle.
+   +
+++++
+++++

+++ + +++       ++++++++             28     There exists another solution:
+++ + +++       +      +                    6x6 square with 4x2 gap,
+++ + +++       +      +                    but in Alice's opinion square gap
+++ + +++       +      +                    makes code more readable.
+      +
+      +
+      +
++++++++


### Tricky tests

This must be    Thism                24     7x7 with 5x5 gap looks good,
5x5 with 1x1    ustbe                       but 5x5 with 1x1 gap is better,
gap.            5x 5w                       because gap area is smaller.
ith1x
1gap.

+++ +++ +++     :~(                  18     In case you tried 5x5 square
+++ +++ +++                                 with 7x1 gap ;)


### Resources

To save space you can find sample code and extra test cases on tio.run

[New] You may take a look at the table of accepted solutions for inputs upto 100 characters. I swapped width and height because it seems to look more intuituve.

Inspired by: A square of text

### Changes

• Added 2 tests, fixed bug in sample code.

• "If formatting is impossible, output crying emoji" - unnecessary fluff, allowing any output would be better IMO. – Jonathan Allan Jul 5 '19 at 21:46
• @JonathanAllan, even better would be guaranteeing that formatting is always possible. Boo-urns to input validation! – Shaggy Jul 5 '19 at 22:42
• @Jonathan Allan, any output is too broad and may be vulnerable to loopholes. I thought about letting to use any falsy values, but it would make output inconsistent between different languages. I also considered using empty string, but it would make running test cases less visual. I also thought about some other messages like "Error", but decided to make it even shorter to support Brainfuck developers all over the world. – Daniil Tutubalin Jul 6 '19 at 9:41
• @Shaggy, this is not just input validation. To find that there is no solution is important part of the puzzle: you need to find out when to stop searching. – Daniil Tutubalin Jul 6 '19 at 9:42
• @DaniilTutubalin it is very common to assure only certain inputs will be given here. Allowing any output on such "invalid" inputs is also a common approach, and avoids boilerplate code which has nothing to do with the core of the challenge. If you really want something unvarying as output in such cases I'd suggest the input itself. I am not suggesting you change it now though ...also this is a very nice challenge! – Jonathan Allan Jul 6 '19 at 15:41

# Stax, 80 bytes

ö╦Çc▀╕╡ëé╓]µiÖ9♪W|╣▐↑╖D┘↕♫╗╔äƒ■úφ■Uÿ⌠%é┴☼vAú)☺@Ä±◄¬¶¢(îÉ┼6⌠D~♀└lfæA.I@º╤∟òîü╦(


Run and debug it

How does it work?

• Consider all squares with rectangle cutouts.
• Filter out program shapes that aren't the right size.
• Filter out program shapes that don't have matching parity.
• Filter out program shapes where the cutout is too big for the square.
• If none are found, output failure and quit.
• Find the shape that minimizes "rectangularity" of cutout, then by cutout size.
• Replace each character in the program shape with the corresponding character in the program input.

Unpacked, ungolfed, and commented it looks like this.

                input e.g. "big socks"
L$j$            remove whitespace from input e.g. "bigsocks"
cr{~F           copy push each remaining character to input stack in reverse order
%c              get length L of flattened input and copy e.g. 8
^r3:$create triples [a,b,c] in range 0..n e.g. [[0,0,0], [0,0,1], ... [8,8,8]] {E*NsJ+n=f filter triples: require a*a-b*c=L e.g. [[3,1,1], [4,1,8], ...] {ET>f filter triples: a>b and a>c e.g. [[3,1,1]] {{2%m:u_0#+f filter triples: a%2=b%2=c%2 or b*c=0 e.g. [[3,1,1]] ":~("s|c if there are no triples, output ":~(" and terminate {D:s_D:*\oh sort by [abs(b-c),b*c]; keep the first e.g. [3,1,1] X store the chosen triple in the X register E explode onto stack e.g. 3, 1, 1 z)]* using last two values, make a rectangle of zeroes e.g. 3, [[0]] ~ this will be the cutout, push it to the input stack c'X*]* make a square of "X" e.g. ["XXX", "XXX", "XXX"] xEd-h given the dimensions in x register, calculate the centered cutout coordinates xEsd-h e.g. ["XXX", "XXX", "XXX"], 1, 1 ,|| embed the cutout grid at the specified coordinates e.g. ["XXX", "X X", "XXX"] m'X{,]}R for each line, regex replace "X" with a character from the input stack  Run this one • Could you please provide unpacked version as well? – Daniil Tutubalin Jul 7 '19 at 8:01 • @DaniilTutubalin I've added an explanation. – recursive Jul 7 '19 at 14:05 • Thank you! Well done! – Daniil Tutubalin Jul 7 '19 at 14:49 # C (gcc), 354 348 bytes -6 thanks to ceilingcat h,i,j,k,l,m;g,v,w,d;f(char*s){for(j=l=0;i=s[j];d=g=l+=!isspace(s[j++]));for(;i++<l;)if(h=i*i-l)for(j=0;j<i-++j;h>0&h%k<1&k<=m&m<i&m+~k&m-k<g|m==k+g&(d-2*v)*(d-2*w)>h?w=i-m>>1,v=j,g=m-k,d=i:0)k=i-2*j,m=h/k;else g=0,v=w=d=i;if(g-l)for(i=j=1;*s;j+=!i++,k=0,i%=~d)for(putchar(i?v>=j|j>d-v|w>=i|i>d-w?k=1,*s:32:10);k;k*=isspace(*++s));else puts(":~(");}  Try it online! • I think a tab is "white-space", although I asked for clarification on what exactly counts. – Jonathan Allan Jul 5 '19 at 22:03 • I have updated post. You may replace isspace(x) with x<33. – Daniil Tutubalin Jul 6 '19 at 10:16 # JavaScript (ES6), 284 ... 274 270 bytes Saved 4 bytes thanks to @Shaggy Returns an array of strings. s=>(s=s.replace(/\s/g,''),n=s.length,o=[':~('],W=d=g=(x,w=0,h=p=0)=>4*~-x>n?o:h>w?++w>x-2?g(-~x):g(x,w):g(x,w,h+1,o=n-x*x+w*h|(w^x|h^x)&!!(w|h)|w-h>d|w-h==d&w>W?o:[...Array(x)].map((_,Y,a)=>a.map((_,X)=>2*X>=x-w&2*X<x+w&2*Y>=x-h&2*Y<x+h?' ':s[p++]).join,d=w-h,W=w)))  Try it online! • Well done! Though try this test: This must be 5x5 with 1x1 gap. (24 characters) – Daniil Tutubalin Jul 5 '19 at 13:26 • @DaniilTutubalin That's why I deleted my initial post (and suggested such a test case), but this is now supported correctly. – Arnauld Jul 5 '19 at 13:28 • Can't [\s\n] just be \s? – Shaggy Jul 5 '19 at 22:33 • @Shaggy ++w>x-2 is actually w++>=x-2 (w++>=x would fail for $42$, for instance). But \s does save 4 bytes. Thanks. :) – Arnauld Jul 6 '19 at 6:14 # Charcoal, 120 bytes ≔Ｅ⮌⪫⪪Ｓ ωιθ≔⁰ηＦ⊕Ｌθ¿⁼Ｌθ×ιι«≔ιη≔ιζ≔ιε»Ｆ⊘ιＦ⊕κＦ∧⁼Ｌθ⁻×ιι×⁻ι⊗⊕κ⁻ι⊗⊕λ∨¬η›⁻ζε⁻κλ«≔ιη≔⊕κζ≔⊕λε»¿η«ＵＯη#ＪεζＦ›η⊗ζＵＯ⁻η⊗ε⁻η⊗ζψＵＭＫＡ⊟θ»:~(  Try it online! Link is to verbose version of code. Explanation: ≔Ｅ⮌⪫⪪Ｓ ωιθ  Strip the spaces from the input, then reverse it and split it into characters, so that we can loop over the characters more easily later. ≔⁰η  Start with a size of zero, indicating no result found (yet). Ｆ⊕Ｌθ  Check all side lengths up to the length of the string. (Throwing a division in would of course make the code faster.) ¿⁼Ｌθ×ιι«≔ιη≔ιζ≔ιε»  If the result turns out to be a perfect square then save the square size and also set that as the border size. Ｆ⊘ιＦ⊕κ  Loop over the possible border heights and widths (the border width is no greater than the border height, making the gap height no greater than the gap width.) Ｆ∧⁼Ｌθ⁻×ιι×⁻ι⊗⊕κ⁻ι⊗⊕λ∨¬η›⁻ζε⁻κλ«≔ιη≔⊕κζ≔⊕λε»  If the size of the border is the desired length and we don't have a solution yet or it's not as square as this solution then update the solution with this square and border sizes. ¿η«  If we have a solution... ＵＯη#  Draw a rectangle of an arbitrary character of the given square size. ＪεζＦ›η⊗ζＵＯ⁻η⊗ε⁻η⊗ζψ  If the border is small enough to leave a gap then erase the gap. (The drawing command will draw upwards and leftwards for negative values and doesn't like zero values at all.) ＵＭＫＡ⊟θ  Replace all (remaining) characters with characters from the input. »:~(  Otherwise output :~(. # Jelly, 91 85 bytes ÆDżU$<Ạa;ḂEɗʋƇṢƑƇ;€€
ḟ⁶ḟ⁷;©⁶L’²<¥Ðḟ²_ç;,Wɗ¹?⁸ʋ€\$Ẏạ/ÞḢµIH+""Rp"/ḟ@/ŒṬ€ĖP€Sị®Yµ“:~(”¹?


Try it online!

A monadic link that takes the input string as its argument and returns a string either with the formatted output or :~(.

# Python 2, 287281 279 bytes

c=list("".join(input().split()))
l=len(c)
p=[]
for q in range(l*l):x=q%l;y=q/l;s=(l+x*y)**.5;p+=[(abs(x-y)/2,int(s),-x)]*(s%1==0)*(x<s-1>y>=s%2==x%2==y%2or x<1)
if p:d,s,x=min(p);b=(s+x)/2;Y=0;exec"c[b:b]=' '*-x*(b+d<=Y<s-b-d);print''.join(c[:s]);c=c[s:];Y+=1;"*s
else:print':~('


Try it online!

Uses Python's lexicographic list comparison by using the same values for both choosing a solution and printing it. I'm pretty sure 10 4 2 or so bytes can still be shaved off.

### Explanation

c=list("".join(input().split()))
l=len(c)
p=[]


Remove whitespaces by splitting with whitespace and joining with "", then convert input to a list for later. Also initialize l to length of actual code and p to list of valid possibilities.

for q in range(l*l):x=q%l;y=q/l;s=(l+x*y)**.5;


Loop through all possibilities of gap sizes from 0*0 to l*l. Compute the edge length of the square with l code chars and x*y spaces as s.

p+=[(abs(x-y)/2,int(s),-x)]*(s%1==0)*(x<s-1>y>=s%2==x%2==y%2or x<1)


Check if the following conditions match:

• s % 1 == 0, i.e. a perfect square would be formed
• x < s-1 > y, i.e. x and y are at most s-2 and fit inside the square
• s % 2 == x % 2 == y % 2, i.e. both x and y match the edge's parity and can be centered
• but if x < 1, i.e. x == 0, ignore all but the perfect square requirement

If the conditions matched, add the following items in a tuple to p to find the optimal one:

• abs(x-y)/2; first find the minimal difference of x and y to get the most square gap. This is always even so we divide by 2.
• int(s); next find the minimal side length. Since s is an integer and increases as the gap area x*y, this sorts by gap area.
• -x; next find the maximal width to prefer horizontal gaps. This comes after the area due to how it was developed, but the area is the same for x*y and y*x so it works.
if p:d,s,x=min(p);b=(s+x)/2;Y=0


If we found any valid layouts, find the optimal one as described above. Compute the horizontal border b and initialize the line number Y to 0.

exec"c[b:b]=' '*-x*(b+d<=Y<s-b-d);print''.join(c[:s]);c=c[s:];Y+=1;"*s


If the line number Y is inside the gap (the vertical border is b+d, with d from the tuple), add the gap width's worth of spaces after the horizontal border in c. (The modification of c is why we need it to be a list.) Then print a line of the square and remove it from c. Repeat s times, incrementing the line number.

else:print':~('


If no layouts were found, fail.

• Well done! Alas, it doesn't work well with multiline input. Also it seems it doesn't support rectangular gaps (see test with length 22). – Daniil Tutubalin Jul 7 '19 at 8:13
• @DaniilTutubalin You need to supply input as a Python string, multiline would be literally "some\ntext" as delimiters. (input() evaluates a line of input as Python code.) If this isn't acceptable, please let me know. Length 22 also works for me. – PurkkaKoodari Jul 7 '19 at 12:22
• ouch, sorry. Probably I did something wrong with input. – Daniil Tutubalin Jul 8 '19 at 10:36

# Pyth, 99 98 bytes

#JscQ)=QshKh|oaFtNSf!|%hT1&eT|t{%R2TgeStThT+L@+lJ*Fd2^UJ2
":~("Am/-Qd2tKW=W}~hZrG-QGJj*eKdcJ]H<~>J


Try it online!

This uses the same algorithm as my Python answer, but many details are significantly changed to be shorter in Pyth.

Pyth shows its age here, since it hasn't been updated in ages and only uses the printable ASCII characters (for code, not data), wasting a lot of space.

Interestingly, if Pyth used the same kind of base-256 packing as Stax, this program could be ⌈98 log256 95⌉ = 81 bytes long, right next to Stax (80 bytes) and Jelly (85 bytes). I think this nicely shows how close golfing languages are even with their drastically different paradigms.

### Explanation (only slightly less unreadable than the code)

# wraps everything in a while True: that suppresses the message and quits on error.

JscQ) chops input (Q) at whitespace, sums the parts together and saves the result in J.

^UJ2 makes the list of indices (U) of J and takes its 2nd Cartesian power (^), resulting in all pairs [h,w] with 0<=h<len(J) and 0<=w<len(J).

+L@+lJ*Fd: for all (L) such pairs d, adds (+) the square root (@2) of (the length of J plus (+) the product (*F) of the pair d) to the left side of the pair, creating a triplet [side length, gap height, gap width].

f!|%hT1&eT|t{%R2TgeStThT: filter for triplets T where

• neither of (!|):
• side length (hT) modulo 1 (%1) is nonzero
• both of (&):
• gap height (eT) is nonzero
• either of (|):
• each number in the triplet (R) modulo 2 (%2), with duplicates ({) and the first unique (t) removed, is nonempty
• the larger (eS) of gap height and gap width (tT) is greater-or-equal than side length (hT)

S sorts the triplets lexicographically (by side length, then by gap height). oaFtN then orders the triplets by the absolute difference between gap height and gap width (tN).

At this point, if we have no valid solutions, | evaluates its second argument, \n":~(", which prints and returns :~(. h takes the optimal solution (or ":" if none) and it is saved in K. Then h takes its side length (or ":" if none), s casts it to integer (or fails and quits if none) and it is saved (=) in Q.

Each of (m) [gap height, gap width] (tK) is then subtracted (-) from side length (Q) and the result divided by 2 (/2). The results are Assigned to G and H.

Finally, we enter a While loop. Z starts at 0 and each iteration we increment it but use the old value (~hZ, think Z++ in C).

• If (W) the old value is in ({) the range G to (side length - G) (-QG), assign (=) to J the following: chop J at position (]) H and join the halves with gap width eK times (*) a space (d). If the value was not in the range, just return J. If this result is empty, stop the loop.
• Remove (>) the first Q characters from J and assign (~) the result to J. From the old value of J, take (<) the first Q characters and print them.

Finally, the # loop starts again, errors and quits because cQ) with Q containing a number is invalid.

• To be honest, I like printable code more. Though binary code takes less space, it looks much less apealing (and i would prefer to see it as hex dump) and usually comparison is done between solutions in the same language. So shorter packed Stax solution compared to another packed Stax solution, will still be shorter after unpacking both. Packing makes sense for overall Kolmogorov complexity only. – Daniil Tutubalin Jul 8 '19 at 12:10
• @DaniilTutubalin Regardless of how comparison is usually done, it's still nice to beat another golflang ;) – PurkkaKoodari Jul 8 '19 at 12:11

# 05AB1E, 95 89 bytes

…


A few bytes here and there can definitely be golfed.

The first three steps of the program are inspired by @recursive's Stax answer, so make sure to upvote him!

Explanation:

Step 1: Remove all white-spaces:

…
# Push string " \n\t"
м              # And remove those from the (implicit) input-string


Step 2: Create all possible triplets $$\[a,b,c]\$$, where $$\a\$$ is the dimension of the resulting $$\a×a\$$ square, and $$\b×c\$$ is the size of the gap. We do this by creating all possible triplets using integers in the range $$\[0,a]\$$. And then we filter these where all of the following is truthy for the triplet:

• $$\a^2-b×c=L\$$, where $$\L\$$ is the length of the string
• $$\(a\gt b)\text{ and }(a\gt c)\$$
• $$\(a\pmod2=b\pmod2=c\pmod2)\text{ or }(min(a,b)\neq0)\$$

For example: $$\L=28\$$ will result in the triplets [[6,2,4],[6,4,2],[8,6,6]].

Dg                 # Get the length of this string (without popping by duplicating first)
©                # Store this length in variable ® (without popping)
Ý               # Create a list in the range [0,®]
3ã             # Create all possible triplets by repeating the cartesian product 3 times
ʒ                  # Filter these triplets by:
ć                 #  Extract head; pop and push remainder-list and head to the stack
sP-             #  Take the product of the remainder, and subtract it from the squared head
®Q           #  And check if it's equal to the string length in variable ®
}ʒ                 # Filter the remaining triplets further by:
ć‹P              #  Where the first integer is larger than the other two
}ʒ      }          # And filter it a third time by:
ÈË               #  Where all three are either odd or even
~           #  Or
yß_            #  It does not contain any 0s


Step 3: Check if we still have any triplets left. If not, output ":~("; if we do, determine which one to use by sorting and only leaving the first. We do this by sorting the tuples $$\(abs(b-c),b×c)\$$.

For example: the triplets [[6,2,4],[6,4,2],[8,6,6]] will be sorted to [[8,6,6],[6,2,4],[6,4,2]], after which only [8,6,6] remains.

Dg_i               # If this completely filtered list is now empty:
…:~(           #  Push string ":~("
ë                  # Else:
Σ                 #  Sort the triplets by:
¦                #   Remove the first character
DÆÄ             #   Get the absolute difference between the remaining two integers
sP‚             #   And pair it with the product of the remaining two integers
}н           #  After we're done sorting: only leave the first triplet


Step 4: Create a list on how we should split the string to insert the spaces. This is done like this:

Given $$\[a,b,c]\$$, create a list with:

• As first item: $$\\frac{a-b}{2}×a + \frac{a-c}{2}\$$
• As middle $$\b-1\$$ items: $$\{a-c}\$$
• As last item: $$\a^2\$$

For example: triplet [7,3,5] will result in the list [15,2,2,35].

©                  #  Store this triplet in variable ® (without popping)
¤_i               #  If the last value is 0 (which means the string is a square without gap):
н              #   Simply keep the first value of the triplet
ë               #  Else:
¬U             #   Store the first value in variable X (without popping)
ć            #   Extract the first value; pop and push remainder-list and head to the stack
α           #   Get the absolute difference of this head with the other two values
¤          #   Push the last value (without popping the pair itself)
®Ås<и     #   And repeat it the middle element or ® minus 1 amount of times
s           #   Swap to get the difference pair again
;          #   Halve both values
R        #   Push them reversed to the stack
X*      #   Multiple the first value by X
+     #   And then add it to the second value
š    #   Prepend this in front of the repeated list
Xnª #   And also append the square of X


Step 5: And finally we split the string based on this list, join it back together with $$\c\$$ amount of spaces, split it into parts of size $$\c\$$, and join those together by newlines. For example:

String "Alongtesttoseeifitworksasintended." split according to list [15,2,2,35] will result in: ["Alongtesttoseei","fi","tw","orksasintended."]. This is then joined by $$\c=5\$$ amount of spaces to "Alongtesttoseei fi tw orksasintended.". And then split into parts of size $$\a=7\$$ to this: ["Alongte","sttosee","i f","i t","w o","rksasin","tended."]. Which is then joined by newlines to output.

    £              #   Then split the string into parts based on this list
®θð×          #   Push a string consisting of the last value of ® amount of spaces
ý         #   Join the list of substrings by this
X        #   Push variable X
}ô              #  After the if-else: split the string into parts of that size
»             #  And then join these by newlines
# (after which the top of the stack is output implicitly as result)
`