Programming puzzle

sort(list)
return 0

I just drained the swamp

Attached: trumpie-998x657.jpg (998x657, 86K)

pedantic autists, all of you

you get what he means, you're just being retarded

it's similar to the largest rectangle problem, get fucked you plebs.

not gonna do it though because I don't have time atm.

>What if i have [1,5,1,5,1,5,1] ?
Then the total would be 8

>Asume first number in array is the biggest number
Why?

Attached: 1501813110527.png (534x432, 17K)

>Real world
>People have poorly-formed problems
>Engineers are expected to give solutions to any given problem
>Can't do shit because muh lacking information
>Millenials

im not OP btw

This is not homework, this is a puzzle someone has posted on Jow Forums before.

Should be 8 according to the rules, see pic related

Attached: 1515151.jpg (401x395, 24K)

water = []
for x in mylist:
if x > mylist[0]:
break
water.append(mylist[0]-x)

>why

Because as long as the following numbers are lower, we can calculate the water volume. If not, then we dont need to calculate anything because the water would "spill out"

Nvm, this wouldn't work because i didn't take into account that water can spill out from the right.

Update possible solution

>Asume first number in array is the biggest number
>Initialize total as 0
>initialize subtotal as 0
>For each element in the array
>if number is bigger or equal than our biggest number, change biggest number to this number, then add subtotal to total and set subtotal to 0.
>if not, calculate biggest number - number, and add it up to subtotal
>if number is 0 or below, set subtotal to 0
>Discard subtotal when we end the array
>Total is the water volume

Do you happen to be indian? Just wondering.

something like this? Did I miss anything other than user input? #include "stdio.h"

int water(int graph[], int size){
int total = 0;
int temp = 0;
int curHeight = graph[0];
for(int i=1; i curVal){
temp += curHeight - graph[i];
}
else{
total += temp;
temp = 0;
curHeight = curVal;
}
}
return total;
}

int main(){
int graph[] = {3,2,1,2,1,4};
int size = 6;
int pool = water(graph,size);
printf("drink %d water blocks",pool);
return 0;
}

nope

oh i missed draining off the right side

reference solution

[3,2,1,2,1,4]
.reduce((a,e,i,o)=>[...a,{h:e, m: Math.max(...a.map(u=>u.m),e)}],[])
.reverse().
.reduce((a,e)=>{m = Math.max(a.m, e.h); return {m: m, s: a.s + Math.min(m, e.m) - e.h}},{m: 0, s: 0})
.s

out
6

further tests:
[1,2,3,0,0,0,10,0] => 9
[1,2,3,0,4,0,10,0] => 7
[0,10,0,4,0,3,2,1] => 7
[1,5,1,5,1,5,1] => 8

Attached: 1526050117532.jpg (540x720, 49K)

sorry should [1,2,3,0,0,0,10,0] not evaluate to zero? drains left, drains 0, drains right

tl;dr
[3,2,1,2,1,4]
.filter(e=>e)
.reduce((a,e,i,o)=>[...a,{h:e, m: Math.max(...a.map(u=>u.m),e)}],[])
.reverse().
.reduce((a,e)=>{m = Math.max(a.m, e.h); return {m: m, s: a.s + Math.min(m, e.m) - e.h}},{m: 0, s: 0})
.s

oh actually i didn't miss draining right; it only adds to total if the curValue is bigger than curHeight. My solution should be okay though not totally optimized.

0 should drain water

it's called an integral

tl;dr
[1,2,3,0,4,0,10,0]
.reduce((a,e,i,o)=>
[...a,{h:e, m: e && Math.max(...a.map(u=>u.m),e)}],[])
.reverse()
.reduce((a,e)=>
{m = e.h && Math.max(a.m, e.h);
return {m: m, s: a.s + Math.min(m, e.m) - e.h}},{m: 0, s: 0})
.s

>b-b-but muh speshul cases!!

no nevermind i still fucked up; i should have tested more hah it fails on something simple as 3,2,1,2. too sleepy for now

okay fuck it i did it anyway; going to bed. still misses some edge cases like only 1 bar whatever #include "stdio.h"

int water(int graph[], int size){
int total = 0;
int temp = 0;
int curHeight = graph[0];
int j = 0;
for(int i=1; i curVal){
j++;
temp += curHeight - graph[i];
}
else{
total += temp;
j = 0;
temp = 0;
curHeight = curVal;
}
}
//check right side drain
if(temp){
int rightGraph[j];
for(int i=size-1,k=0;i>=size-j;i--,k++){
rightGraph[k] = graph[i];
}
total += water(rightGraph,j);
}
return total;
}

int main(){
int graph[] = {3,2,1,2,3,2,1,2,1,2,1,2,1};
int size = 13;
int pool = water(graph,size);
printf("drink %d water blocks",pool);
return 0;
}

fuck you boomer

in javascript

var counter = 0;
function gay (barArr) {
counter = 0;
barArr.sort(function(a,b) {
return b - a;
}); //sorts the array from highest to lowest
console.log(barArr);
for (var i = 1; i < barArr.length; i++) {
counter += barArr[1] - barArr[i]; // as the second highest column is the one that will spill over, ie barArr[1]
}
console.log(counter);
}

gay([3,2,1,2,1,4]);

hope that helps, feel free to critique it

var counter = 0;
function gay (barArr) {

if (barArr[0] >= barArr[1] && barArr[barArr.length -1] >= barArr[barArr.length - 2]) {
counter = 0;
barArr.sort(function(a,b) {
return b - a;
}); //sorts the array from highest to lowest
console.log(barArr);
for (var i = 1; i < barArr.length; i++) {
counter += barArr[1] - barArr[i]; // as the second highest column is the one that will spill over, ie barArr[1]
}
console.log(counter);
} else if (barArr[0]

static int CalculateVolume(int[] array) {
int i, waterLevel, totalVolume;
i = waterLevel = totalVolume = 0;
;
while (i < array.Length) {
try {
int volume = 0;

while (array[i]

Can there be multiple pools of water or just one?

Thats not a special case. It says that in the description you just didnt pay attention to it

Multiple. OP put no limit on array length or specified how the number are generated.

that is true

and that is also probably the reason why I don't have a job.

I should probably just take the 100 bucks from the rap generator dude :/

static long WaterArea(List bar)
{
List water = new List(new uint[bar.Count]);

for (int i = 0; i < bar.Count - 1;) {
//Find a concave area between two bars
int tallest = i + 1;
for (int j = i + 1; j < bar.Count; j++) {
if (bar[j] == 0) {
tallest = i + 1;
break;
}
if (bar[j] >= bar[tallest]) {
tallest = j;
if (bar[j] >= bar[i]) {
break;
}
}
}

//Fill the area to match the height of the shorter bar
uint waterHeight = Math.Min(bar[i], bar[tallest]);
for (int k = i + 1; k < tallest; k++) {
if (bar[k] < waterHeight) {
water[k] = waterHeight - bar[k];
}
}

//Skip to the next segment
i = tallest;
}

return water.Sum(x => x);
}

Handles all cases that I've tried. This is an interesting challenge, since everyone here seems to solve it slightly differently.

when replying, please memequote the relevant part(s).

what's the runtime on that? n^2?

why do you check for indexoutofrange?

does [4,1,5,0,5,1,4] work?

>what's the runtime on that? n^2?
I'm hopeless with big O, but I think you're saying my solution is shit. Let's benchmark it.

{ 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4 }

My old code can run this a million times in 1000 ms. With some changes, I've gotten it down to 140 ms:

static long WaterArea(uint[] bar)
{
long water = 0;

for (int i = 0; i < bar.Length - 1;) {
//Find a concave area between two bars
int tallest = i + 1;
for (int j = i + 1; j < bar.Length; j++) {
if (bar[j] == 0) {
tallest = i + 1;
break;
}
if (bar[j] >= bar[tallest]) {
tallest = j;
if (bar[j] >= bar[i]) {
break;
}
}
}

//Fill the area to match the height of the shorter bar
uint waterHeight = Math.Min(bar[i], bar[tallest]);
for (int k = i + 1; k < tallest; k++) {
if (bar[k] < waterHeight) {
water += waterHeight - bar[k];
}
}

//Skip to the next segment
i = tallest;
}

return water;
}

is 250 times slower than my code. Pic related.

Attached: benchmark.png (69x35, 548)

this doesnt give the right answer

Use two pointers one on each end.

static int fill(int bars[])
{
const int NumBars = std::size(bars);
if (NumBars > 2)
{
int currentLeft = 0;
int ans = 0;
for (int i = 1; i < NumBars; i++)
{
if (bars[i] == 0)
{
currentLeft = i;
}
else
{
if (bars[i] > bars[currentLeft])
{
if (bars[currentLeft] != 0)
{
for (int e = currentLeft + 1; e < i; e++)
{
ans += bars[currentLeft] - bars[e];
}
}
currentLeft = i;
}
}
}
return ans;
}
return 0;
}

The solution was a lot simpler than I thought initially

I missed a case where the left-most bar is the tallest and none are taller.
static int fill(int bars[])
{
const int NumBars = std::size(bars);
if (NumBars > 2)
{
int currentLeft = 0;
int ans = 0;
for (int i = 1; i < NumBars; i++)
{
if (bars[i] == 0)
{
currentLeft = i;
}
else
{
if (bars[i] >= bars[currentLeft])
{
if (bars[currentLeft] != 0)
{
for (int e = currentLeft + 1; e < i; e++)
{
ans += bars[currentLeft] - bars[e];
}
}
currentLeft = i;
}
}
}
if (currentLeft == 0)
{
return fill(std::reverse(bars));
}
return ans;
}
return 0;
}

Not my favourite language -- literally the first time I ever try to use python, just decided to give it a shot this afternoon. Pls no bully.
Also, I have no idea how to benchmark it.

array = [3,2,1,2,1,4]
total = 0

Hi = [0, array[0]]

for i in range(1,len(array)):
if array[i] < 1:
Hi = [i, 0]
if array[i] > array[i-1]:
for j in range(Hi[0]+1,i):
fillAmount = min(Hi[1], array[i])-array[j]
array[j] = array[j] + fillAmount
total = total + fillAmount
if array[i] > Hi[1]:
Hi = [i, array[i]]

print('total filled ' + str(total))

Fug

array = [3,2,1,2,1,4]
total = 0

Hi = [0, array[0]]

for i in range(1,len(array)):
if array[i] < 1:
Hi = [i, 0]
if array[i] > array[i-1]:
for j in range(Hi[0]+1,i):
fillAmount = min(Hi[1], array[i])-array[j]
array[j] = array[j] + fillAmount
total = total + fillAmount
if array[i] > Hi[1]:
Hi = [i, array[i]]

print('total filled ' + str(total))

Attached: brainlet.jpg (702x800, 55K)

Nevermind, I figured it out.
Is that the right answer?

Attached: Selection_016.png (156x92, 4K)

Wow I'm impressed it can be the simple, I am such a brainlet as I started a Python script and it was pure #learntocode tier with lots of conditionals and still didn't work.
>tfw you will never be able to conceptualize problems and turn them into efficient code

>why do you check for indexoutofrange?
Because I have nested loops which do i++ therefore it could exceed array.length before the outer while loop catches it.

Basically, I was lazy.

>(You) is 250 times slower than my code. Pic related.
Fair point. I've reworked it so it is now contained in 1 loop, making it a lot simpler and a lot faster:
static int CalculateVolume2(int[] array) {
int level, volume, totalVolume;
level = volume = totalVolume = 0;

for (int i = 0; i < array.Length; i++) {
if (array[i] == 0) {
volume = 0;
level = 0;
}
else if (array[i] >= level) {
level = array[i];
totalVolume += volume;
volume = 0;
}
else if (array[i] < level) {
volume += level - array[i];
}
}

return totalVolume;
}

I used the same array as you:
{ 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4, 0, 3, 2, 1, 2, 1, 4 }

Giving answer: 48

And get the results:
Single Call: 0.186ms
Called in loop x1000000: 99.283ms

>all these cucks doing this faggot's homework

Attached: 1490596374299.png (242x242, 81K)

What are we expecting for input? Are we assuming the input is completely random ints in the list that can have a size as large as memory allows? Or do we know a bit about the data so we can optimize it, like the range is low, or there is a small or known cardinality? I think the problem is poorly defined desu.

C# Solution.
public static class WaterBars
{
private static T Id(T t) => t;
private static IReadOnlyList Append(IReadOnlyList l, T newItem) => l.Concat(new[] { newItem }).ToList();

public static int GetScore(IReadOnlyList vals)
{
var chunked = Chunk(vals, new List());
return chunked.Sum(ValueChunk);
}

private static int ValueChunk(IReadOnlyList chunk)
{
var ordered = chunk.OrderByDescending(Id).ToList();
var secondTop = ordered.ElementAt(1);
var topValue = ordered.ElementAt(0);
var mapped = TrimChunk(chunk, topValue, secondTop).Where(a => a < secondTop).Select(a => secondTop - a);
return mapped.Sum();
}

private static IReadOnlyList Chunk(IReadOnlyList vals, IReadOnlyList r)
{
var newChunk = vals.TakeWhile(a => a > 0).ToList();
var remainder = vals.SkipWhile(a => a > 0).SkipWhile(a => a == 0).ToList();
var newColl = Append(r, newChunk);
return remainder.Any() ? Chunk(remainder, newColl) : newColl;
}

private static IReadOnlyList TrimChunk(IReadOnlyList chunk, int topValue, int secondTopValue)
{
var l = chunk.ToList();
var endIndex = new[] {l.LastIndexOf(secondTopValue), l.LastIndexOf(topValue)}.Max();
var startIndex = new[] {l.IndexOf(secondTopValue), l.IndexOf(topValue)}.Min();
return chunk.Skip(startIndex - 1).Take(endIndex - startIndex).ToList();
}
}

8

This doesn't work
>321212
>Returns 0, expected 2

>all these thug solutions that wouldn’t work in general cases

I thought Jow Forums knew shit about shit?

Here you go. O(2n) = O(n):

v

Forgot pic.

Attached: Capture.png (642x418, 15K)

[4,4,4,4]

no gaps, no water, no area

this problem tries too hard

#YOLO
var r = a => a.reduce((ac, c) => ac + (Math.max(...a) - c), 0)

it dont work right, senpai

I just counted the squares of water instead of all the other bullshit. did I pass

this is why you are all neets, none of you even tried let alone succeeded with my algorithms challenge.

I solved it. I bet you didn’t even read through.

i did. no one posted a solution.

??

Meant to reply to you here.

not here, i made a thread with a different challenge, not programming. pure algorithms...

where is it

maybe you need to invest in a bigger marketing department

const waterBars = (arr) => {
let top = 0;
let count = 0;
arr.forEach((num,i)=>{
if(num>top) top=num
else if(num

This looks like some recurrency shit. Take first bar, move right, if next bar is same height increment counter of width, if higher add to width to final solution and treat increase height of all bars you went over by 1, if next bar is lower call the recurrent function for it.

Something like that?

Yeah, I realised the flaw in my logic soon after. I guess I actually need to find the pools and sum them rather just move left to right.

pastebin.com/4mbhSLzd

whoops. Now I ended up uploaded the uncommented version. Code should be pretty self explanatory anyways. Works in all cases.
Had to use visual c++ since I dont wanna swap to linux right now.

>

I'm gonna go with prefix scan for 500€, Jenna.