19

Python 3, 33 bytes lambda a:sum(sorted(a)[-2::-2])/2 Try it online! This is my first answer :D


10

Score: 8066 8065 walls I found an 8066 wall solution using dynamic programming over solutions that can be recursively decomposed by splitting on a row or column consisting entirely of floors or entirely of walls. The implementation of this apparently simple idea was rather more complicated than its description, since there are 17 different types of ...


9

APL (Dyalog Extended), 11 10 bytes −1 thanks to Jonah. Anonymous tacit prefix function. ⌊∨+.÷∞2⍴⍨≢ Try it online! ≢ the tally of item prices …⍴⍨ use that to reshape…  0∞ the list [0,infinity] …+.÷ sum the division of the following by that:  ∨ the item prices sorted into descending order ⌊ floor (because the infinity is actually just the largest ...


7

R, 81 79 bytes -2 bytes thanks to pajonk function(n,`!`=function(x)outer(x,x,`+`),x=which(n==!!(0:n)^2,T)[1,]-1)x[x>0]^2 Try it online! (For large inputs, TIO will run into time-out/out-of-memory problems.) By Lagrange's four-square theorem, the output is always of length at most 4. This constructs all the sums of 4 squares from \$0^2\$ to \$n^2\$ in a ...


7

Python 3.8 with Numpy using Lagrange's four-square theorem, 92 bytes A Numpy version with Lagrange's four-square theorem as exploited by others. 3 bytes shaved thanks to @ovs using the r_ trick, literally called index_tricks in Numpy. i.e. the Lagrange's four-square theorem together with Numpy save you 44 byte comparing to pure Python. from numpy import* ...


6

05AB1E, 6 bytes {RιθO; Try it online! Sort, Reverse, split into even and odd indices, get second part, sum and take half.


5

Score: 8127 (validation) -11 thanks to Anders Kaseorg .....#.....#....#................##........#.##...........#...........#........#..................#.................#........... .#.#...#.#...#.##.#.#.#.#.#.#.##..#.#.#.#.##..#.##.#.#.#.##.#.#.#.#.#...#.#.#.##.#.#.#.#.#.#.#.#.##.#.#.#.##.#.#.#.##.#.#.#.#.#. .#.#.#.#.#.#.#..#.#.#.#.#.#.#..#.##.#.#.#..#.##.....


5

Perl 5, 49 44 43 bytes sub f{@_=sort$a-$b,@_;pop;pop()/2+(@_&&&f)} Try it online! -6 thanx to @kjetil-s; previous.


5

Wolfram Language (Mathematica), 46 bytes # #&@@PowersRepresentations[#,4,2]/. 0->Set@$& Try it online! Relies on the four-square theorem, then removes zeroes. Built-in does most of the work.


4

Vyxal s, 4 bytes sṘy½ Try it Online! 5 bytes without the flag. Port of ovs's answer but with two key differences: y, uninterleave, pushes both halves separately on the stack, so we don't need to get the second half We have the s flag, so we don't need to sum the list in the code. s # Sort Ṙ # Reverse y # Interleave ½ # Take half (vectorised)


4

Perl 5, 66 64 bytes use List::Util pairmap,sum;sub f{sum+pairmap{$b/2}sort{$b-$a}@_} Try it online!


4

Scala, 222..187 180 bytes -7 bytes thanks to user! x=>y=>{var(a,b,r)=(x,y,Set[Any]()) while(a.sum>0){var?,m=a.max min b.max var p,q= -1 while(p<0|q<0){if(p<0)p=a indexOf? if(q<0)q=b indexOf? ? +=1} a(p)-=m b(q)-=m r+=Seq(p,q,m)} r} Try it online!


4

Jelly, 7 bytes ṢU0Hƭ€S Try it online! Based on Adám's method, so go upvote that as well How it works ṢU0Hƭ€S - Main link. Takes a list L on the left ṢU - Sort L in descending order ƭ€ - Tie the previous 2 atoms, and alternate between the two for each element: 0 - At odd-indexed elements: Replace the element with 0 H - At even-...


3

C (gcc), 100 78 73 bytes r;f(a,l)int*a;{qsort(a,l,4,L"\x72b068bǃ");for(r=0;l--;++a)r+=*++a/2;r=r;} Try it online! Saved a whopping 22 bytes thanks to ceilingcat!!!


3

05AB1E, 10 bytes ÅœéʒŲP}нR Try it online! will be ridiculously slow for larger inputs integer partitions sort by length filter square? (implicit map) product (implicit truthy) end filter head reverse


3

Charcoal, 23 bytes W⁻θυF№ι⌊ι⊞υ⌊ιI⊘ΣEυ×ι﹪κ² Try it online! Link is to verbose version of code. Explanation: W⁻θυF№ι⌊ι⊞υ⌊ι Sort the input in descending order. I⊘ΣEυ×ι﹪κ² Multiply each value by its index modulo 2, then take half the sum.


3

JavaScript (ES6), 137 bytes a=>g=(b,k=O=0,o=[],n,c)=>O=O&&!O[k]||a.map((p,i)=>b.map((q,j)=>b[a[i]-=n=p<q?p:q,b[j]-=n,n&&g(b,k+1,[...o,[i,j,c=n]]),a[i]=p,j]=q))|c?O:o Try it online! Commented a => // outer function taking the 1st list a[] g = ( // inner function taking: b,...


3

JavaScript (ES6), 49 bytes f=a=>1/a.sort((a,b)=>a-b)?0:a.pop(a.pop())/2+f(a) Try it online! How? Because sort() operates in lexicographical order by default, we unfortunately need the explicit callback function (a, b) => a - b, although all test cases would pass without it. We can stop as soon as the array is empty or only one element remains. ...


3

Wolfram Language (Mathematica), 25 bytes -Tr@Sort[-#/2][[2;;;;2]]& Try it online!


3

R, 35 bytes Thanks to att for spotting a bug. function(p).5*p%*%!rank(-p,,"f")%%2 Try it online! Takes the dot-product (%*%) of p/2 and a vector of 0s and 1s, with the 1s at the positions corresponding to even ranks in the sorted version of -p. We need to use .5*p instead of p/2 because of operator precedence. The "f" is needed to ...


3

R, 36 bytes function(p)sum(-sort(-c(p,0))*0:1)/2 Try it online! Assumes the price of each item in the order is non-negative.


3

JavaScript (ES6), 110 81 71 bytes -7 thanks to Mayube, -6 thanks to emanresu A, and -2 thanks to Arnauld f=(x,i=x**.5|0,r=i?[i*i,...f(x-i*i)]:[])=>s=i>1&&r[f(x,i-1).length]?s:r Recursive solution. Lots of golfs along the way :p Try it online!


3

J, 36 bytes ((i.~+/&>){])[:*:&.>@,4{\@$[:<1+i.@- Try it online! Brute force. Relies on 4-square theorem, which I learned about from Robin Ryder's answer.


3

Python 2, 77 76 bytes f=lambda n,i=1:min(`f`*(~i*~i>n)or f(n,i+1),n and[i*i]+f(n-i*i)or[],key=len) Try it online! f=lambda n,i=1 # recursive function with input n and initial side length 1 n and ... or [] # If n is 0, return the empty list. min(..., key=len) # Otherwise return the shortest of `f`*(~i*~i>n) # - '<...


2

Husk, 7 bytes ṁ½Ċ2Θ↔O Try it online! O # sort in ascending order ↔ # reverse Θ # prepend a zero Ċ2 # get every 2nd element, starting at the first ṁ½ # halve each of these, and then sum the results


2

Jelly, 9 bytes ŒṗƲẠ$ƇṪU Try it online! ŒṗfƑƇ²€ṪU Try it online! Times out for test cases larger than 50. How they work ŒṗƲẠ$ƇṪU - Main link. Takes n on the left Œṗ - Integer partitions of n; Ways to sum positive integers to n $Ƈ - Keep those partitions P for which the following is true: Ạ - All elements are: Ʋ - Square ...


2

Retina 0.8.2, 201 92 91 bytes .+ $* ^((^1|11\2)*?)((1(?(4)1\4))*?)((1(?(6)1\6))*?)((1(?(8)1\8))+)$ $.7 $.5 $.3 $.1 +` 0$ Try it online! Link includes test cases. Explanation: .+ $* Convert to unary. ^((^1|11\2)*?)((1(?(4)1\4))*?)((1(?(6)1\6))*?)((1(?(8)1\8))+)$ Try to match 3 squares lazily, plus a 4th square (greedily, since that's golfier). This is ...


2

Charcoal, 37 bytes NθF⊕θF⊕ιF⊕κFE⊕λX⟦μλκι⟧²F⁼θΣμ⊞υμI⮌Φ⌊υι Try it online! Link is to verbose version of code. Very slow. Explanation: Nθ Input n. F⊕θF⊕ιF⊕κFE⊕λX⟦μλκι⟧² Generate all sets of four squares in ascending order with the largest square not exceeding n². F⁼θΣμ⊞υμ If the squares sum to n then save the set. I⮌Φ⌊υι Print the set with the most zeros, ...


2

JavaScript (ES6), 79 bytes f=(n,i=o=1,l=[])=>(n?i>n||f(n-i*i,i,[i*i,...l])|f(n,i+1,l):l[o.length]?o:o=l,o) Try it online!


2

Pari/GP, 54 bytes n->forpart(p=n,prod(i=1,#p,issquare(p[i]))&&return(p)) Try it online! Port of wasif's 05AB1E answer. PARI/GP has a built-in to iterate over integer partitions, sorted by length.


Only top voted, non community-wiki answers of a minimum length are eligible