8
\$\begingroup\$

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 [[]]


\$\endgroup\$
  • \$\begingroup\$ Do we have to be able to handle both strings and arrays as input or only one? Can output be a string containing newlines? Should the output for [100] not be [[1,0],[0,0]]? If not, is [[100,1],[2,0]] the expected output for input [100,1,2]? \$\endgroup\$ – Shaggy May 15 '17 at 7:41
  • \$\begingroup\$ @Shaggy Yes, numeric lists and strings/lists of characters (whatever your language uses). Output per default rules. "100" gives [["1",0"],["0"," "]] (or whatever the fill element is. Yes, [100,1,2] → [[100,1],[2,0]]. \$\endgroup\$ – Adám May 15 '17 at 7:43
  • \$\begingroup\$ Hi Adám, I have three questions... 1. What does "The pad element should be the default fill element for the given data type, or any one element of your choice." mean, - is it restricted or free (it seems contradictory or redundant)? 2. What should the output be for an input like [1,2,3,4,'O'], or is it guaranteed not to occur? 3. Is the required order after flattening requirement ignoring the pad elements (e.g. could an input of [1,2,3,4,5] yield [[0,0,0],[0,1,2],[3,4,5]] or even [[0,1,0],[2,0,3],[0,4,5]])? \$\endgroup\$ – Jonathan Allan May 15 '17 at 14:00
  • 1
    \$\begingroup\$ @JonathanAllan 1. Some languages will automatically pad. Whatever they pad with is fine. If your's don't, choose an element. 2. string or numeric list. 3. The padding elements must be trailing. \$\endgroup\$ – Adám May 15 '17 at 14:04

10 Answers 10

4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What does it output for empty input? \$\endgroup\$ – Adám May 15 '17 at 6:46
  • \$\begingroup\$ This outputs nothing for empty input, which happens to be way MATL outputs empty matrices / strings. \$\endgroup\$ – Stewie Griffin May 15 '17 at 6:52
  • 1
    \$\begingroup\$ I think tnX^Xkt3$e does the job too \$\endgroup\$ – Luis Mendo May 15 '17 at 10:16
  • 1
    \$\begingroup\$ Or, better, tnX^Xkthe \$\endgroup\$ – Luis Mendo May 15 '17 at 10:34
  • 1
    \$\begingroup\$ @LuisMendo I looked for a way to pass three inputs to reshape and didn't notice the very obvious: $: Specified inputs. And I didn't know you could pass the dimensions as a vector. I knew there had to be a way without having to go through two reshapes. Thanks! :) \$\endgroup\$ – Stewie Griffin May 15 '17 at 11:23
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

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

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!

\$\endgroup\$
  • \$\begingroup\$ What does it output for empty input? \$\endgroup\$ – Adám May 15 '17 at 6:47
  • 4
    \$\begingroup\$ @Adám The correct answer. \$\endgroup\$ – Leaky Nun May 15 '17 at 6:52
  • \$\begingroup\$ You can now simplify by using just one fill element. \$\endgroup\$ – Adám May 15 '17 at 7:09
1
\$\begingroup\$

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!

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

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ @JonathanAllan thank you, fixed. \$\endgroup\$ – Giuseppe May 16 '17 at 14:06
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

Dyalog APL, 20 19 bytes

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

-1 Byte thanks to @Adám!

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Save one: {(,⍨⍴⍵↑⍨×⍨)⌈.5*⍨≢⍵} \$\endgroup\$ – Adám Aug 15 '17 at 8:44
  • \$\begingroup\$ This was my answer for the student competition, it was naturally golfy so I put it here, and thanks for the byte! \$\endgroup\$ – Zacharý Aug 15 '17 at 20:37

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.