Roman Army Shields

Question

^{Sandbox post (deleted)}

The old roman army formations are very famous around the world. In these formations roman legionaries grouped in a geometric shape (usually a rectangle) protecting the flanks and the superior part of it using their shields. The legionaries at interior positions covered the superior part placing their shield above their heads, the legionaries at the flanks carried 2 or more shields: one for protecting the superior part, and one or more shields for protecting the flanks (if someone was in the corner he had 3 shields, if someone was alone in a formation he had 5 shields ^{Yes, I know it is impossible for a human to carry 5 shields, but somehow they did it}). Using this formation all roman legionaries protected themselves and were the hardest opponent at the time.

The history tells there was a roman general who stated that the best formation shape was the square (same number of legionaries in rows and columns). The problem was figuring out how many formations (and the size) he should split his army in order to:

• Do not left any legionary out of a formation (although he admitted single legionary formation)
• Reduce the amount of required shields

The general, after doing some math and calculations, he figured out that the best way to accomplish this 2 conditions is to start with the biggest square possible, and then repeat until no legionaries left.

---

Example:

If 35 legionaries in his army, the formation consisted in

• A 5x5 legionaries square (This is the biggest square possible).

With the remaining legionaries (10)

• A 3x3 square

With the remaining legionaries (1)

• A 1x1 square.

At the end it will look something like this:

   5x5      
* * * * *        3x3            
* * * * *       * * *      1x1  
* * * * *       * * *       *
* * * * *       * * *       
* * * * *               

The legionaries at interior positions covered the superior part placing their shield above their heads. They only needed 1 shield.

* * * * *                   
* 1 1 1 *       * * *       
* 1 1 1 *       * 1 *       *
* 1 1 1 *       * * *       
* * * * *               

The legionaries at the flanks carried 2

* 2 2 2 *                   
2 1 1 1 2       * 2 *       
2 1 1 1 2       2 1 2       *
2 1 1 1 2       * 2 *       
* 2 2 2 *               

If someone was in the corner he had 3 shields

3 2 2 2 3               
2 1 1 1 2       3 2 3       
2 1 1 1 2       2 1 2       *
2 1 1 1 2       3 2 3       
3 2 2 2 3               

If someone was alone in a formation he had 5 shields

3 2 2 2 3               
2 1 1 1 2       3 2 3       
2 1 1 1 2       2 1 2       5
2 1 1 1 2       3 2 3       
3 2 2 2 3               

This formation required a total of 71 shields.

---

Challenge

• Calculate the amount of shields that are needed for a X amount of legionaries

Input

• Amount of legionaries in the army

Output

• Amount of shields needed.

Test Cases

35 => 71
20 => 44
10 => 26
32 => 72

---

• Standard code-golf rules apply

Answer 1

Python 2, 60 50 48 bytes

def f(s):n=s**.5//1;return s and(n+4)*n+f(s-n*n)

Try it online!

New to code golf, but giving it my best swing!

Method:

Sum n^2 + 4n where n is each of the largest square numbers that sum to the input.

Edit 1

Reduced to 50 bytes thanks to @Jonathan Frech!

Edit 2

Switched int(s**.5) to s**.5//1 to save 2 bytes thanks to @ovs

Answer 2

R, 51 50 bytes

f=function(x,y=x^.5%/%1)"if"(x,y^2+4*y+f(x-y^2),0)

Try it online!

A square of side length \$y\$ must have exactly \$y^2+4y\$ shields. We reduce by the largest square less than or equal to \$x\$ until \$x\$ is zero, accumulating the number of shields as we go.

Proof:

Given a perfect square of side length \$y\$, we need precisely 1 shield for each member of the square. Next, for each member on the edge, we need an additional shield. There are \$(y-2)^2\$ members not on the edges, so there are \$y^2-(y-2)^2\$ members on the edges. Finally, for each corner, we need an additional shield. Apart from the case where \$y=1\$, we can thus add 4. This simplifies to \$y^2+4y\$ which fortunately also yields the correct value of \$5\$ when \$y=1\$, allowing us to use it for all \$y\$.

Answer 3

JavaScript (ES7), 34 bytes

f=n=>n&&(w=n**.5|0)*w+w*4+f(n-w*w)

Try it online!

How?

At each iteration, we compute the width \$w = \lfloor\sqrt{n}\rfloor\$ of the largest possible square. The number of shields \$s_w\$ for this square is given by:

$$s_w = w^2+4w$$

For instance, for \$w=3\$:

$$\begin{align}&\pmatrix{3 & 2 & 3\\2 & 1 & 2\\3 & 2 & 3}=&(s_3=21)\\&\pmatrix{1 & 1 & 1\\1 & 1 & 1\\1 & 1 & 1}+&(3^²=9)\\&\pmatrix{1 & 1 & 1\\0 & 0 & 0\\0 & 0 & 0}+\pmatrix{0 & 0 & 1\\0 & 0 & 1\\0 & 0 & 1}+\pmatrix{0 & 0 & 0\\0 & 0 & 0\\1 & 1 & 1}+\pmatrix{1 & 0 & 0\\1 & 0 & 0\\1 & 0 & 0}&(4\times3=12)\end{align}$$

The formula holds for \$w=1\$, as \$s_1=5\$.

Answer 4

Jelly, 13 bytes

ƽ²ạƊƬ_Ɲ½ẋ4S+

Try it online!

-1 thanks to Jonathan Allan.

Answer 5

Julia 0.6, 36 bytes

!n=(s=isqrt(n))*s+4s+(n>0&&!(n-s*s))

Try it online!

Uses the same \$ n^2 + 4n \$ method as @Giuseppe's R answer, though my method to arrive there involved less meaningful thinking and more just visual inspection: the inner square of 1s has dimensions \$ (n - 2) \$ by \$ (n - 2) \$, so that has \$ (n - 2)^2 \$ shields. Surrounding that, there are 4 walls of \$ n - 2 \$ soldiers each, each with 2 shields - so that adds \$ 4*(n - 2)*2 \$ shields. Finally, there are four 3s in the four corners, so that adds 12 shields.

$$ (n-2)^2 + 4*(n-2)*2 + 4*3 = n^2 + 4 - 4n + 8n - 16 + 12 = n^2 + 4n $$

Ungolfed:

!n = begin       # Assign to ! operator to save bytes on function parantheses
  s = isqrt(n)   # Integer square root: the largest integer m such that m*m <= n
  s * s +
    4 * s +
      (n > 0 &&  # evaluates to false = 0 when n = 0, otherwise recurses
        !(n - s * s))
end

(This can also be done it in 35 bytes with n>0?(s=isqrt(n))*s+4s+f(n-s*s):0, but I wrote this for Julia 0.7 wanted to avoid the new deprecation warnings (requiring spaces are ? and :).)

Answer 6

Stax, 15 bytes

ëñ|^○╖?║<l╛P╝z√

Run and debug it

Answer 7

Brachylog, 26 bytes

0|⟧^₂ᵐ∋N&;N-ℕ↰R∧N√ȧ×₄;N,R+

Try it online!

0           % The output is 0 if input is 0
|           % Otherwise,
⟧           % Form decreasing range from input I to 0
^₂ᵐ         % Get the squares of each of those numbers
∋N          % There is a number N in that list
&;N-ℕ       % With I - N being a natural number >= 0 i.e. N <= I
            % Since we formed a decreasing range, this will find the largest such number
↰           % Call this predicate recursively with that difference I - N as the input
R           % Let the result of that be R
∧N√ȧ        % Get the positive square root of N
×₄          % Multiply by 4
;N,R+       % Add N and R to that
            % The result is the (implicit) output

Answer 8

Retina 0.8.2, 28 bytes

.+
$*
(\G1|11\1)+
$&11$1$1
.

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to decimal.

(\G1|11\1)+

Match odd numbers. The first pass through the group, \1 doesn't exist yet, so only \G1 can match, which matches 1. Subsequent matches can't match \G1 since \G only matches at the beginning of the match, so instead we have to match the 11\1 which is 2 more than the previous match. We match as many odd numbers as we can, and the total match is therefore a square number, while the last capture is one less than twice its side.

$&11$1$1

Add the side shields to each match. $& is \$n^2\$ and $1 is \$2n-1\$ while we need \$n^2+4n=n^2+2+2(2n-1)\$.

.

Sum and convert to decimal.

Answer 9

05AB1E, 17 bytes

[Ð_#tïÐns4*+Šn-}O

Try it online or verify all test cases.

Work-around because ΔDtïÐns4*+Šn-}O (15 bytes) doesn't seem to work.. Try it online in debug-mode to see what I mean. I would expect it to go from [45,'35',25] to [45,10] after the - and next iteration of Δ, but apparently it clears the stack except for the last value and becomes [10], resulting in 0 at the very end.. Not sure if this is intended behavior or a bug.. (EDIT: It's intended, see bottom.)

Explanation:

Also uses \$w^2+4w\$ where \$w\$ is the width in a loop like most other answers.

[        }     # Start an infinite loop:
 Ð             #  Triplicate the value at the top of the stack
  _#           #  If the top is 0: break the infinite loop
 t             #  Take the square-root of the value
               #   i.e. 35 → 5.916...
  ï            #  Remove any digits by casting it to an integer, so we have our width
               #   i.e. 5.916... → 5
   Ð           #  Triplicate that width
    n          #  Take the square of it
               #   i.e. 5 → 25
     s         #  Swap so the width is at the top again
      4*       #  Multiply the width by 4
               #   i.e. 5 → 20
        +      #  And sum them together
               #   i.e. 25 + 20 → 45
 Š             #  Triple-swap so the calculated value for the current width
               #  is now at the back of the stack
               #   i.e. [35,5,45] → [45,35,5]
  n            #  Take the square of the width again
               #   5 → 25
   -           #  Subtract the square of the width from the value for the next iteration
               #   i.e. 35 - 25 → 10
          O    # Take the sum of the stack
               #   i.e. [45,21,5,0,0] → 71

---

EDIT: Apparently the behavior I described above for Δ is intended. Here two 17-bytes alternatives provided by @Mr.Xcoder that do use Δ by putting values in the global_array (with ^) and retrieving them again afterwards (with ¯):

ΔЈtïnα}¯¥ÄDt··+O

Try it online or verify all test cases.

ΔЈtïnα}¯¥ÄtD4+*O

Try it online or verify all test cases.

Answer 10

dc, 25 bytes

d[dvddSa*-d0<MLa+]dsMx4*+

Try it online!

Calculates the shields as sum(n^2) (the original number) plus 4*sum(n) by pushing a copy of each square side length into stack register a as it goes, then adding all the values from register a as the recursion "unrolls".

Answer 11

Husk, 17 bytes

ṁS+o*4√Ẋ≠U¡S≠(□⌊√

Try it online!

Alternative

ṁS*+4m√Ẋ≠U¡S≠(□⌊√

Try it online!

Answer 12

APL (Dyalog Unicode), 31 30 bytes

{⍵<2:⍵×5⋄(S×S+4)+∇⍵-×⍨S←⌊⍵*.5}

Try it online!

-1 byte thanks to @jslip

Answer 13

Ruby, 45 bytes

->n{n+(1..n).sum{n-=(z=(n**0.5).to_i)*z;z*4}}

Try it online!

Answer 14

PHP, 67 bytes

<?for($n=$argv[1];$w=(int)sqrt($n);$n-=$w**2)$a+=$w**2+$w*4;echo$a;

To run it:

php -n <filename> <n>

Example:

php -n roman_army_shields.php 35

Or Try it online!

---

Using -R option, this version is 60 bytes:

for(;$w=(int)sqrt($argn);$argn-=$w**2)$a+=$w**2+$w*4;echo$a;

Example:

echo 35 | php -nR "for(;$w=(int)sqrt($argn);$argn-=$w**2)$a+=$w**2+$w*4;echo$a;"

(on Linux, replace " with ')

---

Note: This is using Arnauld's answer great formula, I was not able to find anything shorter than that.

Answer 15

Pyth, 19 bytes

A recursive function, which should be called using y (see the link).

L&b+*Ks@b2+4Ky-b^K2

Try it here!

Pyth, 21 bytes

The revision history is quite funny, but make sure to visit it if you want a much faster version :)

sm*d+4deeDsI#I#@RL2./

Try it here!

Explanation

sm*d+4deeDsI#I#@RL2./     Full program, let's call the input Q.
                   ./     Integer partitions of Q. Yields all combinations of positive
                          integers that add up to Q.
               @RL2       Take the square root of all integers of each partition.
             I#           Keep only those partitions that are invariant under:
          sI#             Discarding all non-integers. This basically only keeps the
                          partitions that are formed fully of perfect squares, but
                          instead of having the squares themselves, we have their roots.
       eeD                Get the partition (say P) with the highest maximum.
 m                        For each d in P ...
  *d+4d                   ... Yield d*(d+4)=d^2+4d, the formula used in all answers.
s                         Sum the results of this mapping and implicitly output.

Answer 16

Swift 4, 111 99 84 78 bytes

func f(_ x:Int)->Int{var y=x;while y*y>x{y-=1};return x>0 ?(y+4)*y+f(x-y*y):0}

Try it online!

That feel when implementing integer square root manually is far shorter than the built-in...

Ungolfed and Explained

// Define a function f that takes an integer, x, and returns another integer
// "_" is used here to make the parameter anonymous (f(x:...) -> f(...))
func f(_ x: Int) -> Int {

    // Assign a variable y to the value of x

    var y = x

    // While y squared is higher than x, decrement y.

    while y * y > x {
        y -= 1
    }

    // If x > 0, return (y + 4) * y + f(x - y * y), else 0.

    return x > 0 ? (y + 4) * y + f(x - y * y) : 0
}