# Thinking outside the box

You are trying to fit a sphere into a 5-sided box, but sometimes it does not fit completely. Write a function to calculate how much of the sphere is outside (above the rim of) the box.

There are 3 possible situations:

• The sphere fits completely in the box. The answer will be 0.
• The sphere sits on the rim of the box. The answer will be more than half of the total volume.
• The sphere sits on the bottom of the box.

You can see each situation here:

You must write a program or function to compute this value to at least 4 significant digits.

Input: 4 non-negative real numbers in whatever format is convenient* - width, length, depth of the box (interior measurements), and diameter of the sphere.

Output: 1 non-negative real number in a usable format* - the total volume (not the percentage) of the sphere outside the box.

* must be convertible to/from a decimal string

You are encouraged to limit your use of trigonometry as much as possible.

This is a popularity contest, so think outside the box!

• any example cases please? – mniip Jan 4 '14 at 22:21
• Can we assume either the walls of the box are infinitely thin or the dimensions given are interior dimensions? :) – Darren Stone Jan 4 '14 at 22:23
• What are the maximum values for the inputs? – Blender Jan 4 '14 at 22:30
• @DarrenStone I think that the walls thickness are uninportant. You could consider it infinite as well, so the box would be a rectangular hole in an infinte block. The result would be the same as any other value for the wall thickness. Except if you are intending to bend/cheat the rules by physically breaking, distorting or slicing either the box or the sphere, or do something really strange. – Victor Stafusa Jan 4 '14 at 22:31
• @DarrenStone The boxes only have thickness for the purposes of a nice picture. The problem deals with interior dimensions. – Kendall Frey Jan 4 '14 at 22:33

## Forth

Please find, below, a sphere outside the box.

The "sphere" is the volume-computing function f. The reference test cases compose the "box".

                     ( x y z d -- v )
: f { F: z F: d } d f2/
{ F: r } fmin { F: m } m f2/ {
F: b } d m f<= d z f<= and if 0e
else r r r f* b b f* f- fsqrt f-
{ F: t } d m f<= t z f> or if d
z f- else d t f- then r 3e f*
fover f- pi f* fover f*
f* 3e f/ then ;

1e                 1e
1e                 1e
f                  f.
cr       1e        1e       0e
1e       f         f.       cr
1e       1e 0.5e 1e f f. cr 1e
0.999e 1e          1e     f
f.  cr            0.1e 1e
1.000e 0.500e f f. cr


Output:

0.
0.523598775598299
0.261799387799149
0.279345334323962
0.0654299441440212


## Java - integer based

This program does not use pi and does not call any external function - not even sqrt. It only uses simple arithmetic - +, -, * and /. Furthermore, other than a scaling step, it works exclusively with integers. It basically divides the sphere into little cubes and counts the ones that are outside the box.

public class Box {
private static final int MIN = 10000;
private static final int MAX = MIN * 2;

private static final int[] SQ = new int[MAX * MAX + 1];

static {
int t = 1;
for (int i = 1; i <= MAX; ++i) {
while (t < i * i) SQ[t++] = i - 1;
}
SQ[MAX * MAX] = MAX;
}

public static long outsideInt(int r, int w, int z) {
int r2 = r * r;
int o = z - r + 1;
if (w < r * 2) {
int t = 1 - SQ[r2 - w * w / 4];
if (t < o) o = t;
}
long v = 0;
for (int i = o; i <= r; ++i) {
int d = r2 - i * i;
int j0 = SQ[d];
v += 1 + 3 * j0;
for (int j = 1; j <= j0; ++j)
v += 4 * SQ[d - j * j];
}
return v;
}

public static double outside(double x, double y, double z, double d) {
double f = 1;
double w = x < y ? x : y;
double r = d / 2;
while (r < MIN) {
f *= 8;
r *= 2;
w *= 2;
z *= 2;
}
while (r > MAX) {
f /= 8;
r /= 2;
w /= 2;
z /= 2;
}
return outsideInt((int) r, (int) w, (int) z) / f;
}

public static void main(final String... args) {
System.out.println(outside(1, 1, 1, 1));
System.out.println(outside(1, 1, 0, 1));
System.out.println(outside(1, 1, 0.5, 1));
System.out.println(outside(1, 0.999, 1, 1));
System.out.println(outside(0.1, 1, 1, 0.5));
}
}


Output:

0.0
0.5235867850933005
0.26178140856157484
0.27938608275528054
0.06542839088004015


In this form, the program requires more than 2GB memory (works with -Xmx2300m here) and is prettty slow. It uses the memory to precalculate a bunch of square roots (arithmetically); it's not really necessary, but without that it would be a LOT slower. To improve both memory needs and speed, reduce the value of the MIN constant (that will decrease the accuracy though).

# Python 2 (Array-based approach)

It creates an array of arrays with truth-values if a specific square in that grid is inside the circle or outside the circle. It should get more precise the bigger the circle is you draw. It then selects either an area below or above a certain row and counts the amount of squares that belongs to the circle and divides that by the amount of squares that are in the entire circle.

import math as magic
magic.more = magic.pow
magic.less = magic.sqrt

def a( width, length, depth, diameter ):
precision = 350 #Crank this up to higher values, such as 20000

circle = []
for x in xrange(-precision,precision):
row = []
for y in xrange(-precision,precision):
if magic.less(magic.more(x, 2.0)+magic.more(y, 2.0)) <= precision:
row.append(True)
else:
row.append(False)
circle.append(row)

if min(width,length,depth) >= diameter:
return 0
elif min(width,length) >= diameter:
row = precision*2-int(precision*2*float(depth)/float(diameter))
total = len([x for y in circle for x in y if x])
ammo = len([x for y in circle[:row] for x in y if x])
return float(ammo)/float(total)
else:
#Why try to fit a sphere in a box if you can try to fit a box on a sphere
maxwidth = int(float(precision*2)*float(min(width,length))/float(diameter))
for row in xrange(0,precision*2):
rowwidth = len([x for x in circle[row] if x])
if rowwidth > maxwidth:
total = len([x for y in circle for x in y if x])
ammo = len([x for y in circle[row:] for x in y if x])
return float(ammo)/float(total)


## Python 2.7, Spherical Cap Formula

This version will throw a runtime warning in some cases, but still outputs the correct answer.

import numpy as n
x,y,z,d=(float(i) for i in raw_input().split(' '))
r=d/2
V=4*n.pi*r**3/3
a=n.sqrt((d-z)*z)
b=min(x,y)/2
h=r-n.sqrt(r**2-b**2)
c=lambda A,H: (3*A**2+H**2)*n.pi*H/6
print(0 if d<=z and r<=b else c(a,d-z) if r<=b and z>r else V-c(a,z) if r<=b or z<h else V-c(b,h))


For 11 characters more, I can get rid of the warning.

import math as m
x,y,z,d=(float(i) for i in raw_input().split(' '))
r=d/2
V=4*m.pi*r**3/3
if d>z:
a=m.sqrt((d-z)*z)
b=min(x,y)/2
h=r-m.sqrt(r**2-b**2)
c=lambda A,H: (3*A**2+H**2)*m.pi*H/6
print(0 if d<=z and r<=b else c(a,d-z) if r<=b and z>r else V-c(a,z) if r<=b or z<h else V-c(b,h))


Here are the test cases run on version 1:

$python spherevolume.py 1 1 1 1 0$ python spherevolume.py
1 1 0 1
0.523598775598
$python spherevolume.py 1 1 .5 1 0.261799387799$ python spherevolume.py
1 .999 1 1
0.279345334324
\$ python spherevolume.py
.1 1 1 0.5
spherevolume.py:65: RuntimeWarning: invalid value encountered in sqrt
a=n.sqrt((d-z)*z) or b
0.065429944144

• Even though this isn't code golf, you can shorten import numpy as n to from numpy import* and take away all of the n. in your code. – Timtech Jan 5 '14 at 23:37
• @Timtech Thanks for the heads up and suggestion. – user2487951 Jan 6 '14 at 17:30

# Mathematica

Using numerical integration with proper limits.

f[width_, length_, height_, diam_] :=
With[{r = diam/2, size = Min[width, length]/2},
Re@NIntegrate[
Boole[x^2 + y^2 + z^2 < r^2], {x, -r, r}, {y, -r, r},
{z, -r, Max[-r, If[size >= r, r - height, Sqrt[r^2 - size^2]]]}]
]


## Reference Implementation - C#

using System;

namespace thinkoutsidethebox
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(OutsideTheBox(1, 1, 1, 1));
Console.WriteLine(OutsideTheBox(1, 1, 0, 1));
Console.WriteLine(OutsideTheBox(1, 1, 0.5, 1));
Console.WriteLine(OutsideTheBox(1, 0.999, 1, 1));
Console.WriteLine(OutsideTheBox(0.1, 1, 1, 0.5));
}

static double OutsideTheBox(double x, double y, double z, double d)
{
x = Math.Min(x, y);
double r = d / 2; // radius
double xr = x / 2; // box 'radius'
double inside = 0; // distance the sphere sits inside the box
if (d <= x && d <= z) // it fits
{
return 0;
}
else if (d <= x || r - Math.Sqrt(r * r - xr * xr) > z) // it sits on the bottom
{
inside = z;
}
else // it sits on the rim
{
inside = r - Math.Sqrt(r * r - xr * xr);
}
// now use the formula from Wikipedia
double h = d - inside;
return (Math.PI * h * h / 3) * (3 * r - h);
}
}
}


Output:

0
0.523598775598299
0.261799387799149
0.279345334323962
0.0654299441440212

• I do not understand these results. The first one is obviously 0. The second one has no height, so that one should be 1. The third one can house the ball, and exactly half of it is above it (answer should be 0.5). The box in case 4 is just a little to small, so it rests on top of the box. The answer should be a little bit more than 0.5. The answer for the last one should be >0.5, as the width/length is not sufficient to fit the ball inside. – Sumurai8 Jan 6 '14 at 19:17
• @Sumurai8 "Output: the total volume (not the percentage) of the sphere outside the box." – Kendall Frey Jan 6 '14 at 19:22

# Ruby

Let's see...
If the box is fully inside, then width>diameter; length>diameter and height>diameter.
That should be the 1st check to run.

If it's sitting at the bottom, then w>d ; l>d and h V=(pi*h^2 /3)*(3r-h) So in that case, We just get the height and run it through that.

If it's stuck, we use a similar formula (V=(pi*h/6)*(3a^2 + h^2)). In fact our earlier formula is based on this one! Essentially, we use that, and a is simply the smaller one of w and l. (hint, we can get height by doing h=r-a)

Now the code!

def TOTB(wi,le,hi,di)
if wi>=di and le>=di and hi>=di
res = 0
elsif wi>=di and le>=di
r = di/2
res = 3*r
res -= hi
res *= Math::PI
res *= hi*hi
res /= 3
else
r = di/2
if wi>le
a=le
else
a=wi
end #had issues with the Ternary operator on ruby 2.2dev
h = r-a
res = 3*a*a
res += h*h
res *= Math::PI
res *= h
res /= 6
end
res
end


Note** I didn't test it too much, so an error may have crept in, if anyone notices one, do tell!
The math is solid though.
Shorter version:

v1 = ->r,h{(3*r -h)*Math::PI*h*h/3}
v2 = ->r,a{h=r-a;((3*a*a)+(h*h))*h*Math::PI/6}
TOTB = ->wi,le,hi,di{(di<wi&&di<le&&di<hi)?0:((di<wi&&di<le)?v1[di/2,hi]:v2[di/2,((wi>le)?le:wi)])}


(Now I know for sure that getting h for v2 is done differently, but I'll fix it later.

• Nice. That code reads clearly. But are you sure about the following statement? "we can get height by doing h=r-a" I was just reading up on the spherical cap formulae, and the diagram doesn't suggest a relationship so simple. I'll give it another read. – Darren Stone Jan 5 '14 at 2:18
• @DarrenStone Now that I look back I'm not sure. I'm extraordinarily down/exhausted, but either way, it's very easy to patch! – user11485 Jan 5 '14 at 2:34
• I'm almost sure a = wi > le ? le : wi should work. Otherwise, you have a bug. – Konrad Borowski Jan 5 '14 at 9:05
• a = wi>le?le:wi did not work. I'm guessing it's because I'm running git ruby (2.2 developer), it might have said imbalance. – user11485 Jan 5 '14 at 20:27

c++

#define _USE_MATH_DEFINES   //so I can use M_PI
#include <math.h>           //so I can use sqrt()
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
double w;
double l;
double d;
double sd;
double min_wl;
double pdbd;
double sl;
cin >> w >> l >> d >> sd;

min_wl = min(w, l);
if(sd <= min_wl)
{
pdbd = 0.0;
} else
{
pdbd = (sqrt((((sd/2)*(sd/2))-((min_wl/2)*(min_wl/2)))) + (sd/2));
}
sl = sd - d;

if(sd <= min(min_wl, d))
{
cout << 0;
return 0;
} else if((sl < pdbd) && (pdbd > 0.0))    //sits on lip of box
{
cout << (M_PI * (((sd/2) * pdbd * pdbd) - ((pdbd * pdbd * pdbd)/(3))));
return 0;
} else                  //sits on bottom of box
{
cout << (M_PI * (((sd/2) * sl * sl)-((sl * sl * sl)/(3))));
return 0;
}
return 0;
}


My code finds the volume of the solid of rotation of the graph of some portion of a half-circle. pdbd holds the linear distance of the projection of a point on the surface of the sphere that touches the lip of the box to the diameter of the sphere that, if extended, would be normal to the bottom of the box. The two expressions that contain M_PI are basically the anti-derivative of the integral of pi * -(x^2)+2rx with respect to x (where x is a measure of the length along the above mentioned diameter through the sphere and where r is the radius of the sphere) evaluated at either pdbd or the difference of the sphere diameter and the box depth depending on the particular case that occurs with the different dimensions.