# Ghosts and Pumpkins

Here's an ASCII pumpkin carved into a Jack-o-Lantern. Isn't it cute?

((^v^))


Here's an ASCII ghost. Look how spooky it is!

\{O.O}/


Obviously, the pumpkins have to be on the ground, with a space between them so they don't rot.

Ghosts, however, like to stand on top of pumpkins, so they're even spookier. However, they have to stand on two pumpkins, else their ghostly weight will crush the pumpkin beneath them. But, due to how their ghostly magic works, multiple ghosts can stack and share pumpkins, provided that the ghosts are either split evenly on the lower pumpkins or the lower ghosts. In other words, forming a shape like a human pyramid. Note that ghosts can't stack on ghosts unless there's a pumpkin underneath (that's how the magic works).

Given two non-negative integers, g and p, representing the number of ghosts and pumpkins, output the most-compact left-most formation possible, following the above pyramid stacking rules. Leftover pumpkins and ghosts (that is, those not forming the pyramid) go on the ground to the right.

For clarification, these formations are OK (blank newline separated), and serve as example I/O:

0p 1g
\{O.O}/

1p 0g
((^v^))

1p 1g
((^v^)) \{O.O}/

2p 1g
\{O.O}/
((^v^)) ((^v^))

2p 2g
\{O.O}/
((^v^)) ((^v^)) \{O.O}/

3p 1g
\{O.O}/
((^v^)) ((^v^)) ((^v^))

3p 2g
\{O.O}/ \{O.O}/
((^v^)) ((^v^)) ((^v^))

3p 3g
\{O.O}/
\{O.O}/ \{O.O}/
((^v^)) ((^v^)) ((^v^))

0p 4g
\{O.O}/ \{O.O}/ \{O.O}/ \{O.O}/

3p 0g
((^v^)) ((^v^)) ((^v^))

7p 6g
\{O.O}/
\{O.O}/ \{O.O}/
\{O.O}/ \{O.O}/ \{O.O}/
((^v^)) ((^v^)) ((^v^)) ((^v^)) ((^v^)) ((^v^)) ((^v^))


These formations are Not OK

\{O.O}/
((^v^))

\{O.O}/
((^v^))

((^v^)) ((^v^)) \{O.O}/

\{O.O}/
\{O.O}/
((^v^)) ((^v^))

\{O.O}/
\{O.O}/ ((^v^)) ((^v^))

((^v^))
((^v^)) ((^v^))

\{O.O}/
((^v^)) ((^v^))


### Input

Two non-negative integers in any convenient format. At least one of the numbers will be non-zero. You can take the inputs in either order (i.e., in the examples I had pumpkins first) -- please specify how you take input in your answer.

### Output

An ASCII-art representation of the ghosts and pumpkins, following the above rules. Leading/trailing newlines or other whitespace are optional, provided that the ghosts and pumpkins line up appropriately.

### Rules

• Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
• Standard loopholes are forbidden.
• This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
• What's the correct formation for 7 pumpkins and 6 ghosts? – Neil Oct 28 '16 at 16:09
• @Neil Since the rules ask for the most-compact left-most output, that would be a pyramid of 6 ghosts on top of 4 pumpkins, with an additional 3 pumpkins to the right. I'll add it as an example. – AdmBorkBork Oct 28 '16 at 16:13
• Well, your use of compact confused me - I could put all the ghosts on the same row, so that's more compact vertically! – Neil Oct 28 '16 at 16:29
• Will pumpkins always be provided before ghosts? – Gabriel Benamy Oct 28 '16 at 19:03
• I like that the ghosts and pumpkins are making a human pyramid – MayorMonty Oct 28 '16 at 19:40

## JavaScript (ES7), 166164 159 bytes

Saved 5 bytes thanks to Neil

f=(p,g,j=(g*2)**.5+.5|0,G=j>p-1?p?p-1:0:j,P=
,i=~j?g-G*++G/2:G,n=i>0?i>g?g:i:0)=>p|g?f(0,g-n,-1,G-1,P+'    ')+P+'((^v^)) '.repeat(p)+'\\{O.O}/ '.repeat(n):''


### Formatted and commented

f = (                                    // given:
p,                                     // - p = number of pumpkins
g,                                     // - g = number of ghosts
j = (g * 2) ** .5 + .5 | 0,            // - j = ceil(triangular root of g)
G = j > p - 1 ? p ? p - 1 : 0 : j,     // - G = max(0, min(p - 1, j))
P = '\n',                              // - P = padding string (+ line-break)
i = ~j ?                               // - i =
g - G * ++G / 2                      //   first iteration: g - G * (G + 1) / 2
: G,                                   //   next iterations: G
n = i > 0 ? i > g ? g : i : 0          // - n = max(0, min(i, g)) = number of
) =>                                     //   ghosts to print at this iteration
p | g ?                                  // if there's still something to print:
f(                                     //   do a recursive call with:
0,                                   //   - no pumpkin anymore
g - n,                               //   - the updated number of ghosts
-1,                                  //   - j = -1 (so that ~j == 0)
G - 1,                               //   - one less ghost on the pyramid row
P + '    '                           //   - updated padding string
) +                                    //
P +                                    //   append padding string
'((^v^)) '.repeat(p) +                 //   append pumpkins
'\\{O.O}/ '.repeat(n)                  //   append ghosts
: ''                                     // else: stop


### Underlying math

The tricky part is to find out the optimal width G of the ghost pyramid.

The number of ghosts g in such a pyramid is given by:

g = 1 + 2 + 3 + ... + G = G(G + 1) / 2


Reciprocally, the width of a pyramid containing g ghosts is the real root of the resulting quadratic equation:

G² + G - 2g = 0

Δ = 1² - 4(-2g)
Δ = 8g + 1

G = (-1 ± √Δ) / 2


Which leads to the following real root (also known as the triangular root):

G = (√(8g + 1) - 1) / 2


However, the width of the pyramid is also limited by the number of pumpkins: we can have no more than p-1 ghosts over p pumpkins. Hence the final formula used in the code:

j = ⌈(√(8g + 1) - 1) / 2⌉
G = max(0, min(p - 1, j))


### ES6 version, 173171 166 bytes

f=(p,g,j=Math.pow(g*2,.5)+.5|0,G=j>p-1?p?p-1:0:j,P=
,i=~j?g-G*++G/2:G,n=i>0?i>g?g:i:0)=>p|g?f(0,g-n,-1,G-1,P+'    ')+P+'((^v^)) '.repeat(p)+'\\{O.O}/ '.repeat(n):''


### Test cases (ES6)

f=(p,g,j=Math.pow(g*2,.5)+.5|0,G=j>p-1?p?p-1:0:j,P=
,i=~j?g-G*++G/2:G,n=i>0?i>g?g:i:0)=>p|g?f(0,g-n,-1,G-1,P+'    ')+P+'((^v^)) '.repeat(p)+'\\{O.O}/ '.repeat(n):''

console.log(f(0, 1));
console.log(f(1, 0));
console.log(f(1, 1));
console.log(f(2, 1));
console.log(f(2, 2));
console.log(f(3, 1));
console.log(f(3, 2));
console.log(f(3, 3));
console.log(f(0, 4));
console.log(f(3, 0));
console.log(f(7, 6));

• I think j=(g+g)**.5+.5|0 should work. – Neil Oct 29 '16 at 15:57
• Nice explanation! – AdmBorkBork Oct 29 '16 at 16:28
• @Neil This is shorter and more reliable. (My method had some invalid values, starting at g = 5051.) Thanks. – Arnauld Oct 30 '16 at 12:59

# Perl, 246 bytes (newlines are not part of the code and are provided solely for readability)

($c,$d)=<>=~/(\d+)/g;
$p="((^v^)) ";$g="\\{O.O}/ ";
for($f[0]=$c;$d>0;$d--){$f[$b+1]+1<$f[$b]?$f[++$b]++:$f[$b]++;$f[0]+=$d,$d=0 if$b==$c-1;$f[$b]==1?$b=0:1}
$h[0]=($p x$c).$g x($f[0]-$c);$h[$_].=$"x(4*$_).$g x$f[$_]for(1..$#f);
say join\$/,reverse@h;


Accepts two numbers: pumpkins first, followed by ghosts. Sample input:

5 20


Sample output:

                \{O.O}/
\{O.O}/ \{O.O}/
\{O.O}/ \{O.O}/ \{O.O}/
\{O.O}/ \{O.O}/ \{O.O}/ \{O.O}/
((^v^)) ((^v^)) ((^v^)) ((^v^)) ((^v^)) \{O.O}/ \{O.O}/ \{O.O}/ \{O.O}/ \{O.O}/ \{O.O}/ \{O.O}/ \{O.O}/ \{O.O}/ \{O.O}/ \{O.O}/

• Oh, you read my wording a little different than how I was intending -- Ghosts can only stack on top of ghosts if there's a pumpkin underneath, otherwise they need to go to the right single-file. That's why the 0p 4g test case has all the ghosts in a line, rather than stacked. – AdmBorkBork Oct 28 '16 at 19:46
• @TimmyD Alright, I fixed it now. I'll need to do a bit of golfing to reduce it though. – Gabriel Benamy Oct 28 '16 at 19:54