TransWikia.com

Squaring Off (fit to smallest possible square)

Code Golf Asked by Adám on December 24, 2021

Intro

More complex than A square of text since this requires padding and input has unknown data type.

Every year, Dyalog Ltd. holds a student competition. The challenge there is to write good APL code. This is a language agnostic edition of this year’s tenth problem.

I have explicit permission to post this challenge here from the original author of the competition. Feel free to verify by following the provided link and contacting the author.

Problem

Write a program/function that will reshape a given string or numeric list into the smallest square that will contain all the elements of the input, padding with additional elements if necessary. The pad element should be the default fill element for the given data type, or any one element of your choice. The elements of the square should be in such order that flattening it will give the original order of input data (with trailing padding elements, if any).

Test cases

[1,2,3,4]

[[1,2],
 [3,4]]

[1,2,3,4,5]

[[1,2,3],
 [4,5,0],
 [0,0,0]]

"Dyalog APL"

[["Dyal"],       [["D","y","a","l"],
 ["og A"],   or   ["o","g"," ","A"],
 ["PL  "],        ["P","L"," "," "],
 ["    "]]        [" "," "," "," "]]

[100]

[[100]]

[]

your language’s closest equivalent to an empty matrix, e.g. [] or [[]]


11 Answers

J, 18 bytes

,~@>.@%:@#$]{.~#*#

Try it online!

Answered by Galen Ivanov on December 24, 2021

Dyalog APL, 20 19 bytes

{(,⍨⍴⍵↑⍨×⍨)⌈.5*⍨≢⍵}

-1 Byte thanks to @Adám!

Try it online!

Answered by Adalynn on December 24, 2021

Jelly, 13 bytes

L½Ċẋ€`
0ṁ;@ṁÇ

A monadic link taking a flat list and returning a list of lists.

Test suite at Try it online!

How?

Appends as many zeros (the padding element) as there are elements in the input and then reshapes to a square, dropping any zeros excess to requirements in the process.

L½Ċẋ€` - Link 1, create a square list of lists of the required size: list a
L      - length of a
 ½     - square root
  Ċ    - ceiling (the required side length, S)
     ` - repeat argument (S) for the dyadic operation:
   ẋ€  -   repeat list for €ach (implicit range [1,2,...,S] on both its left and right)
       -   note: if the input list has no length then an empty list is yielded here

0ṁ;@ṁÇ - Main link: list a (strings are lists of characters in Jelly)
0      - literal zero
 ṁ     - mould like a (makes a list of zeros of the same length as the flat list a)
  ;@   - concatenate a with that
     Ç - call the last link (1) as a monad with argument a
    ṁ  - mould the (possibly oversized) flat array with extra zeros like the square array

Answered by Jonathan Allan on December 24, 2021

Brachylog, 10 bytes

;Ac~c.l~l

Try it online!

Takes strings as lists of characters (the asker has confirmed that this is OK).

This is very inefficient on longer inputs, because it brute-forces all possible reshapings of the input, trying progressively more padding, until it finds one that happens to be square.

Explanation

;Ac~c.l~l
;Ac         Append {the shortest list possible}.
   ~c       Split into a list of lists
      l    such that it's rectangular, and the number of columns
     .  ~l  equals the number of rows

The padding elements used are Prolog's "any value" value _, which is normally rendered as _G plus some random digits on output (to make it possible for the Prolog engine to express relationships between those general-purpose values).

Incidentally, there was a bug fix to SWI-Prolog only a few days ago that makes this program possible (although it still appears to work on older, buggy versions); the "it's rectangular" constraint implied by was previously broken, but it got fixed in time for the challenge.

Answered by user62131 on December 24, 2021

R, 91 bytes

function(x){if(!is.double(x))x=strsplit(x,'')[[1]];matrix(x,r<-ceiling(sqrt(length(x))),r)}

By default, R pads matrices by recycling elements of the input vector and encodes matrices in column-major order. Will return a 0x0 matrix for an input of double(0) (an empty double array) or ''.

The first line (the if statement) splits a string into a vector of its constituent characters; if I can take that vector in instead, that line can be removed.

Try it online!

Answered by Giuseppe on December 24, 2021

PHP, 139 Bytes

Output string as 2D char array

works with [] as empty array

$r=[];for($z=ceil(sqrt($n=(($b=is_array($g=$_GET[0]))?count:strlen)($g)));$c<$z*$z;$c++)$r[$c/$z^0][]=$c<$n?$g[+$c]:($b?0:" ");print_r($r);

Try it online!

PHP, 143 Bytes

needs [[]] as empty array

Output string as 1D string array

$z=ceil(sqrt((($b=is_array($g=$_GET[0]))?count:strlen)($g)));print_r($b?array_chunk(array_pad($g,$z**2,0),$z):str_split(str_pad($g,$z**2),$z));

Try it online!

Answered by Jörg Hülsermann on December 24, 2021

Haskell, 87 bytes

import Data.Lists
f x|c:_<-[n|n<-[1..],n^2>=length x]=take c$chunksOf c$x++(error[]<$x)

Try it online!

The fill element is error[], the shortest value that is of any type (undefined is a little bit longer).

Notes on the TIO link:

  • you cannot print error, so I concatenate matrices with fill elements back to a list and print its length

  • TIO doesn't have Data.Lists, only Data.List.Split so it shows 5 more bytes.

How it works: calculate the length c of the c-by-c matrix. Take the first c elements of the list of chunks of length c of the input list followed by a list of fill elements which has the same length as the input list. E.g. :

[1,2,3,4,5]                                        -- Input 
[1,2,3,4,5,error,error,error,error,error]          -- fill elements appended
[[1,2,3],[4,5,error],[error,error,error],[error]]  -- chunks of length 3
[[1,2,3],[4,5,error],[error,error,error]]          -- take 3

Answered by nimi on December 24, 2021

Bash, 91 77 69 67 bytes

L=`dc -e${#1} 1-v1+p`
[ -z "$1"]||printf %-$[$L*$L]s "$1"|fold -$L

Try it online!

Formats text, pads with spaces. Outputs nothing to stdout on empty input.

Update: stole some tricks from answers here.

Answered by eush77 on December 24, 2021

JavaScript (ES7), 70 bytes

a=>[...Array((a.length-1)**.5+1|0)].map((_,$,b)=>b.map(_=>a[i++]),i=0)

Returns [] for an empty array/string. Uses undefined as the fill value. For ES6 replace (...)**.5 with Math.sqrt(...) (+5 bytes).

Answered by Neil on December 24, 2021

Python 2, 105 bytes

def f(a):b=len(a)and int((len(a)-1)**.5)+1;return[(a+[[0],' ']["'"in`a`]*b*b)[b*i:][:b]for i in range(b)]

Try it online!

Answered by Leaky Nun on December 24, 2021

MATL, 12 9 bytes

Saved three bytes thanks to Luis. he instead of UGwewe, but adding a t in the beginning.

tnX^Xkthe

Try it online!

This returns the results, but transposed compared to the result in OPs post (which is OK).

Explanation:

This works the same way for both numeric and string input, as MATL treats them the same way.

Assume the input is 'Dyalog APL'

                % Implicit: Take string or numeric array as input
                % Stack: 'Dyalog APL'
t               % Duplicate
                % Stack: 'Dyalog APL'
                %        'Dyalog APL'
 n              % Number of elements in last element. 
                % Stack: 'Dyalog APL'
                %        10
  X^            % Take the square root of the number of elements
                % Stack: 'Dyalog APL'
                % Stack: 3.16...
    Xk          % Ceil last number
                % Stack: 'Dyalog APL'
                %        4
      t         % Duplicate element
                % Stack: 'Dyalog APL'
                %        4
                %        4
       h        % Concatenate the last to elements horizontally
                % Stack: 'Dyalog APL'
                %        4  4
        e       % reshape into 4 rows, and 4 columns. Pads the input with zeros or spaces
                % if necessary.
                % Stack: (Note that there's a trailing column not shown below)
                %        DoP 
                %        ygL 
                %        a   
                %        lA  

This outputs nothing for empty input, which happens to be way MATL outputs empty matrices / strings.

Answered by Stewie Griffin on December 24, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP