26
\$\begingroup\$

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

\$\endgroup\$
  • 11
    \$\begingroup\$ Well the google result for "carrying 5 shields" is Amazon.com : Best-selling Nipple Shield Carrying Case, Perfect... so I guess I'll never truly know. Did they actually carry 5 shields-- or was this to make the question work :P? \$\endgroup\$ – Magic Octopus Urn Aug 2 '18 at 20:25
  • 1
    \$\begingroup\$ @MagicOctopusUrn Im pretty sure you know the answer xD I don't think someone has the guts to go out in a fight with 5 shields \$\endgroup\$ – Luis felipe De jesus Munoz Aug 2 '18 at 20:32
  • 4
    \$\begingroup\$ I don't the general's math and calculations are right to conclude that repeatedly taking the largest square possible necessary minimizes shields. For example, 32 legionaries can split into two 4*4 squares for 64 total shields, rather than squares of 5*5 + 2*2 +1*1 + 1*1 + 1*1 for 72 total shields. \$\endgroup\$ – xnor Aug 3 '18 at 0:29
  • 6
    \$\begingroup\$ @xnor Maybe in general case the general was't right, but the general is the general (although we shouldn't generalize). \$\endgroup\$ – pajonk Aug 3 '18 at 5:04
  • 2
    \$\begingroup\$ @AJFaraday Asterix and the mercenary badgers? \$\endgroup\$ – Chris H Aug 3 '18 at 9:13

16 Answers 16

14
\$\begingroup\$

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

\$\endgroup\$
  • 8
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Luis felipe De jesus Munoz Aug 2 '18 at 20:24
  • 2
    \$\begingroup\$ I think n*n is shorter than n**2 to save you two bytes; more than that I can't say since I don't write python... \$\endgroup\$ – Giuseppe Aug 2 '18 at 20:32
  • 2
    \$\begingroup\$ 50 bytes. \$\endgroup\$ – Jonathan Frech Aug 2 '18 at 20:38
  • 2
    \$\begingroup\$ int(s**.5) can be shortened to s**.5//1. \$\endgroup\$ – ovs Aug 2 '18 at 22:21
  • 2
    \$\begingroup\$ @mypetlion It does. // is floor division in both Python 2 and 3. 3**.5//1 evaluates to 1.0 in both versions. \$\endgroup\$ – ovs Aug 3 '18 at 6:03
11
\$\begingroup\$

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\$.

\$\endgroup\$
  • \$\begingroup\$ You can simplify the explenation a lot: every roof square needs to be covered: \$y^2\$, and every side square needs to covered \$4\cdot y\$. Now it's obvious that it also works in the single-soldier case. \$\endgroup\$ – Todd Sewell Aug 2 '18 at 21:12
  • 1
    \$\begingroup\$ @ToddSewell sure, that's Arnauld's explanation, and it is far more elegant, but this is the way I approached it, so I'm sticking to it! Luckily, this is not a proof-golf question. \$\endgroup\$ – Giuseppe Aug 2 '18 at 21:14
10
\$\begingroup\$

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\$.

\$\endgroup\$
5
\$\begingroup\$

Jelly, 13 bytes

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

Try it online!

-1 thanks to Jonathan Allan.

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Another overcomplicated explanation for the shield count, see my comment on @Giuseppe's answer. \$\endgroup\$ – Todd Sewell Aug 2 '18 at 21:13
  • 2
    \$\begingroup\$ @ToddSewell Yeah, area + perimeter is a more elegant way to look at it. I didn't do it that way though, and similar to Giuseppe my intention is to describe my approach than to give the neatest proof of the formula. \$\endgroup\$ – sundar Aug 2 '18 at 21:23
4
\$\begingroup\$

Stax, 15 bytes

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

Run and debug it

\$\endgroup\$
3
\$\begingroup\$

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

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.

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

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.

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

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

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

Husk, 17 bytes

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

Try it online!

Alternative

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

Try it online!

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

APL (Dyalog Unicode), 31 30 bytes

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

Try it online!

-1 byte thanks to @jslip

\$\endgroup\$
  • \$\begingroup\$ 0.5 -> .5 for 1 byte \$\endgroup\$ – jslip Aug 9 '18 at 15:56
  • \$\begingroup\$ Wow, how did I miss that \$\endgroup\$ – Zacharý Aug 9 '18 at 15:57
1
\$\begingroup\$

Ruby, 45 bytes

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

Try it online!

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

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.

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

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

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
}
\$\endgroup\$

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.