# Drilling For Oil

## Congratulations!

You have just been hired by a Fortune 499 company specializing in oil drilling. Your job is to write a program to determine the optimum placement of OilRUs' drill (represented by a single alphabetical character of your choice, I use a capital "O" in the examples), given a length of piping, and a two-dimensional Ground Composition Analysis(Henceforth, "GCA") of the area.

However, due to the limited amounts of fossil fuels in the region, copious amounts of bureaucracy, and a recent influx of environmentalists, you must write your program in the fewest bytes possible.

Your program is expected to return the GCA with an Oil drill and piping in the optimal position, as defined below.

### Rules:

1. Input will be composed of an integer, followed by a new-line-separated GCA.
2. The GCA will be composed exclusively of the following characters, representing the surface, dirt, and oil respectively:
• =
• .
• ~
3. The first line of the GCA will always contain exclusively surface tiles, and all layers below that will contain a mixture exclusively of dirt and oil.
4. The GCA will be at least 4 lines of 3 characters, but will not exceed 64 lines of 256 characters each. Every input will contain at least one oil tile.
5. Multiple, adjacent oil tiles on the same row create a 'pool', where all tiles are collected if a pipe tile replaces any of them.
6. Every GCA will have at least one valid solution. See Clarification section for examples.
• For GCAs with multiple equivalent solutions, the solution closest to the surface wins.
• For GCAs with multiple equivalent solutions at the same depth, the one closest to the left-hand side wins.
• A single, larger pool with the same volume as multiple smaller ones are viewed as equivalent. For example, two pools of four tiles are equivalent to a single pool of eight tiles.
• Volume of oil retrieved outweighs the above three points. If a superior solution exists at a deeper level, or further rightward, that solution is to be the one returned by the program.
7. You may not use any purpose-created built-ins for finding oil reserves, whether they're supplied by OilRUs, WeDrill4U, or any third parties.
8. Your program must complete its execution within a reasonable time frame (~30 minutes or less).
9. Standard Loopholes apply.

### Clarification:

• The integer portion of the input represents the maximum number of pipes available. They do not all need to be used.

• Optimum position is defined in this challenge as the first valid place the drill can be set that intersects the largest amount of oil tiles/pools.

• Oil tiles replaced by pipe tiles are still collected, even though they don't show up in the output.

Rule 6 Examples:

   Equal (assuming you were given 3+ pipes)
=====  =====
..~..  .....
..~..  .....
..~..  ..~~~


But:

Loses  Wins
=====  =====
.....  .....
.....  .~~~. ** Solution closer to the surface. (Rule 6.1)
.~...  .....
.~...  .....
.~...  .....


Also:

 Wins     Loses
=====     =====
.....     .....
..~~.     ...~~ ** Solutions are at the same depth,
..~~.     ...~~ ** but one is further left. (Rule 6.2)
.....     .....


### Test Cases

Note: The text shown (denoted by the preceding two asterisks and continuing to the end of that line) in some of the test case outputs below is there for illustrative purposes only. Your program is not expected to print anything apart from OilRUs' drill, pipe, and the GCA.

Input:

4
===============================
..~~....~~.....................
~~........~~~...~~~~~~.........
.....~~~~.....~~~..~~..........
..............~~~...~...~~~..~.
..~~~..~~...~~.....~~....~~~...
.........~~..~...~~..........~.
.......~~...~......~~~.........
..~..........~...........~.....
.........~~.............~......
...~.........~~~~.........~....
...........~..........~........


Output:

================O==============
..~~....~~......|..............
~~........~~~...|~~~~~.........
.....~~~~.....~~|..~~..........
..............~~|...~...~~~..~.
..~~~..~~...~~.....~~....~~~...
.........~~..~...~~..........~.
.......~~...~......~~~.........
..~..........~...........~.....
.........~~.............~......
...~.........~~~~.........~....
...........~..........~........


Input:

2
===============
..~~~.~~.......
..~.....~~~~~~.
.~~~.....~~~...
..~~~..~~..~~~.
.~~...~~~....~.


Output:

========O======
..~~~.~~|......
..~.....|~~~~~.
.~~~.....~~~... ** Leftmost tile in pool (Rule 6.2)
..~~~..~~..~~~.
.~~...~~~....~.


Input:

5
===
~.~
...
~.~


Output:

O==
|.~
|.. ** Leftmost solution wins (Rule 6.2)
|.~


Input:

55
============
............
............
...~.~~..~..
..~~......~.
.....~~~....
..~~~...~~..
...~~~~~~~..


Output:

===O========
...|........
...|........
...|.~~..~..
..~|......~.
...|.~~~....
..~|~...~~..
...|~~~~~~..


Input:

6
============
............
............
..~~........
...~..~~~~..
............
...~........


Output:

======O=====
......|.....
......|.....
..~~..|.....
...~..|~~~.. ** Even though there is a solution closer to the left,
............ ** the solution highlighted here takes priority because it is
...~........ ** closer to the surface. (Rule 6.1)


• So what should be returned if all solutions are equivalent? – R. Kap May 2 '16 at 3:13
• @r.kap: The solution furthest left, and nearest to the surface. Rule 6. – Gabe Evans May 2 '16 at 3:16

# Java, 287 bytes

void a(int d,char[][]a){int b=a.length-1,c=0,e=d=b>d?d:b,f=0,i=0,j,k,g,h,l,m=a[0].length;for(;i<m;i++){g=0;h=0;for(j=1;j<=d;j++){l=0;for(k=0;k<m;k++)if(a[j][k]!=46)l++;else if(k<i)l=0;else break;g+=k==i?0:l;h=l>0?j:h;}if(g>c||g==c&&h<e){c=g;e=h;f=i;}}for(j=0;j<=e;a[j][f]=j++>0?'|':79);}


### Ungolfed

void gcaAnalysis(int pipes, char[][] soil) {
int soilDepth = soil.length - 1, bestCount = 0, bestDepth = pipes = soilDepth > pipes ? pipes : soilDepth, bestX = 0, x = 0, y, k, curCount, curDepth, curLayerCount, width = soil[0].length;
for (; x < width; x++) {
curCount = 0;
curDepth = 0;
for (y = 1; y <= pipes; y++) {
curLayerCount = 0;
for (k = 0; k < width; k++)
if (soil[y][k] != 46) curLayerCount++;
else if (k < x) curLayerCount = 0;
else break;
curCount += k == x ? 0 : curLayerCount;
curDepth = curLayerCount > 0 ? y : curDepth;
}
if (curCount > bestCount || curCount == bestCount && curDepth < bestDepth) {
bestCount = curCount;
bestDepth = curDepth;
bestX = x;
}
}
for (y = 0; y <= bestDepth; soil[y][bestX] = y++ > 0 ? '|' : 79);
}


### Note

• Well... this took half an alphabet of variable names, but it works i guess...

• Results are written back into a (aka soil in the ungolfed code).

### Output

================O==============
..~~....~~......|..............
~~........~~~...|~~~~~.........
.....~~~~.....~~|..~~..........
..............~~|...~...~~~..~.
..~~~..~~...~~.....~~....~~~...
.........~~..~...~~..........~.
.......~~...~......~~~.........
..~..........~...........~.....
.........~~.............~......
...~.........~~~~.........~....
...........~..........~........

========O======
..~~~.~~|......
..~.....|~~~~~.
.~~~.....~~~...
..~~~..~~..~~~.
.~~...~~~....~.

O==
|.~
|..
|.~

===O========
...|........
...|........
...|.~~..~..
..~|......~.
...|.~~~....
..~|~...~~..
...|~~~~~~..

======O=====
......|.....
......|.....
..~~..|.....
...~..|~~~..
............
...~........