Need help with the Water World level

[Ender]

I've already completed every level so far except for the Water World level, but I'm having a hard time figuring out what algorithm I'd need to use. I originally thought I could just add all the heights together and subtract that from the volume of the world, but There's the issue of the edges of the world not being valid places for water. I also thought about just finding the 2 edges and calculating from there, but that wouldn't work since you can have different heights for the water.

[Xandaros]

Yeah, this is for sure a tough one. The solution I came up with is very inefficient, but it does work.

I would suggest you have another think about it before revealing the spoiler, since I do think you can come up with the solution fairly easily. Again, though - it's very inefficient.

In Python-pseudocode:

result = 0
for x in range(16):
    left = find_left(x)
    right = find_right(x)
    smaller = min(left, right)
    result += smaller - data[x]

def find_left(x):
    result = data[x]
    while x >= 0:
        if data[x] > result:
            result = data[x]
    return result

# find_right basically the same, but going to the right instead

# Essentially, this works by find the highest walls to the left and right, taking the lower one and considering that the ceiling of the water. Then subtracting the land. Repeat for every slice. Very inefficient, as I said - but it works

[Ender]

Originally posted by Xandaros:

Yeah, this is for sure a tough one. The solution I came up with is very inefficient, but it does work.

I would suggest you have another think about it before revealing the spoiler, since I do think you can come up with the solution fairly easily. Again, though - it's very inefficient.

In Python-pseudocode:

result = 0
for x in range(16):
    left = find_left(x)
    right = find_right(x)
    smaller = min(left, right)
    result += smaller - data[x]

def find_left(x):
    result = data[x]
    while x >= 0:
        if data[x] > result:
            result = data[x]
    return result

# find_right basically the same, but going to the right instead

# Essentially, this works by find the highest walls to the left and right, taking the lower one and considering that the ceiling of the water. Then subtracting the land. Repeat for every slice. Very inefficient, as I said - but it works

Ok, that's kind of what I came up with when I thought about it. I haven't finished writing all the code for it yet though. I'm worried I'm not going to have enough memory for the code though. I might need to use multiple program blocks and change how the program counter works.

[Jumper]

Interesting approach.
I think that the games "hit ENTER to show water" solution preview is kind of misleading, because it is adding the volume in columns.
There is a (in my opinion) pretty clean solution hiding in plain sight - you just need to think in a different direction.
My first solution:
Determine the highest and lowest point (seems to always be 6/1, so I might as well could've turned that into a constant)
Iterate over the height data for each height between max (inclusive) and min (exclusive) and count the air between walls
That's it - no, really. Done in 5 list iterations.
Although, looking at the problem again... I'm pretty sure I can do it in one iteration as well.

[altrag]

After thinking about it way too much, I realized it can be done in two passes:
1- Moving from left to right:

if this_column > highest_left:
    highest_left = this_column
else
    total_water += (highest_left - this_column)

2- That overfills us a bit as it doesn't take the drop off on the right of the screen into account, so we take some away again. Moving from right to left:

if this_column >= highest_left:
    done
if this_column > highest_right:
    highest_right = this_column
total_water -= (highest_right - highest_left)

[wbradley]

A bit more than one pass, but generally less than two full passes:

- Scan the data to find the highest land, count total land squares while you're doing so
- Calculate total available spots for water (16 * high - total land squares)
- Count in from left edge until you hit a high point, removing squares where water would run off
- Repeat on right edge

Steps 3 and 4 are the interesting ones, as you throw out all the water that is higher than the highest land point you've seen so far as you traverse inwards.

[Arnavion]

This is a common interview question for programmer jobs :)

You only need one pass.


(pseudo-code)

let heights: u8[16] = ...; // Read from io
let max_height = ...; // Calculated at the same time as reading from io

let mut total_water = 0;

for (current_height = max_height - 1; current_height >= 0; current_height -= 1) {
    let mut found_first_wall = false;
    let mut current_water = 0;

    for (col = 0; col < 16; col += 1) {
        if current_height < heights[col] {
            if !found_first_wall {
                found_first_wall = true;
            }
            else {
                // This is a second or later wall, closing a region that contains water.
                // "Commit" the "uncommitted" water
                total_water += current_water;
                current_water = 0;
            }
        }
        else {
            if found_first_wall {
                // This is to the right of a previous wall, so it might contain water
                // in case there's another wall in the future
                current_water += 1;
            }
        }
}

The key is that the case of there being no right wall in the final region is automatically handled, since the "uncommitted" current_water remains "uncommitted" in that case.

[Ender]

Originally posted by Arnavion:

This is a common interview question for programmer jobs :)

You only need one pass.


(pseudo-code)

let heights: u8[16] = ...; // Read from io
let max_height = ...; // Calculated at the same time as reading from io

let mut total_water = 0;

for (current_height = max_height - 1; current_height >= 0; current_height -= 1) {
    let mut found_first_wall = false;
    let mut current_water = 0;

    for (col = 0; col < 16; col += 1) {
        if current_height < heights[col] {
            if !found_first_wall {
                found_first_wall = true;
            }
            else {
                // This is a second or later wall, closing a region that contains water.
                // "Commit" the "uncommitted" water
                total_water += current_water;
                current_water = 0;
            }
        }
        else {
            if found_first_wall {
                // This is to the right of a previous wall, so it might contain water
                // in case there's another wall in the future
                current_water += 1;
            }
        }
}

The key is that the case of there being no right wall in the final region is automatically handled, since the "uncommitted" current_water remains "uncommitted" in that case.

That's so much simpler than the code I came up with.

[altrag]

Originally posted by Arnavion:

You only need one pass.

That's not one pass. That's [max_height] passes.

[Arnavion]

Originally posted by altrag:

Originally posted by Arnavion:

You only need one pass.

That's not one pass. That's [max_height] passes.

Right. It's one pass per height level. I misread your suggestion in light of the previous comments and thought you were doing two passes per height level.

[mial.lohmann]

Interesting solutions :D I solved it slightly differently:

I am filling it not row by row, but basin by basin while I am reading the input.

This is done by pushing all falling edges (height and index) onto the stack and popping them when a rising edge comes and then having fun to decide if I need that last falling edge again :D
I think it is more complex (and probably a bit slower) than the other solutions, but for a real-world scenario it could have benefit that it can calculate the current volume on the fly and you can say "If I start here, let's just go into this direction until a certain condition is met (e.g. I want to have at least x amount of water)"

So it is roughly this as pseudo code:

volume = 0
current_height = column_input.next()

falling_edges = []

def calc_volume(high, low, start, end):
    return (high - low) * (end - start)

for i, new in enumerate(column_input):
    current_height = last_steps_height
    new = current_height
    if current_height == last_steps_height:
        continue
    if current_height < last_steps_height: # step down
        falling_edges.append((i, last_steps_height))
        continue

    # Yay! mixing assembly and some sort of python! :tada: (I am too lazy to think how to do this in python)
    # label step_up
    try:
        (last_falling_edge_index, last_falling_edge_height) = falling_edges.pop()
    except:
        # we didn't have a previous falling edge, so
        continue

    if (last_falling_edge_height > current_height):
        # we might need the edge again later
        falling_edges.append((last_falling_edge_index, last_falling_edge_height))
        volume += calc_volume(current_height, last_steps_height, last_falling_edge_index, i)
        continue

    volume += calc_volume(last_falling_edge_height, last_steps_height, last_falling_edge_index, i)
    if (last_falling_edge_height == current_height):
        continue
    # if we are here, the current rising edge closes several basins at once, so in assembly code terms:
    # jump step_up

Oh yeah - and because I could not come up with a way to solve this with 6 registers I sometimes have to carefully push/pop an additional value, so my stack is a bit of a mess, but it works :D

[manuelsuarez244]

I did it in O(n) where n is the number of colums (height values).
for each column i saved whats the highest wall to its right, denoted I_right
and the highest wall to its right, denoted I_left
if theres no biggest wall to the right or left, then its 0.

then the output for a given column with height i should be max ( min (I_left, I_right) , 0 )

you can get the highest wall to the right, by doing a full pass from right to left and giving each the maximum height you saw till now.

symmetric with highest from the left.

in total it takes 3 passes of the number of values, and 509 ticks on my first bad 4.1K gate computer

[fatboipete]

You can do it in one total pass.
Keep track of a left and right pointer that start at the beginning and end of the columns, and keep track of the maximum wall height on both sides. So left_pointer, left_max, right_pointer, right_max. Then just check which column, column[left] or column[right] is smaller. Increment/decrement the pointer of the smaller side, and check if the new column, column[left/right] is smaller than the previous max on that side, left_max/right_max. If it is, we can add that column of water to the total: sum += right_max/left_max - column[right/left]. If the new column is greater or equal to the previous max, reset the previous max to the current height. Continue until right_pointer <= left_pointer. With 6 registers (with the 6th being used as a RAM pointer, so really 5 usable registers), there are just enough to hold the pointers, previous max's, and sum. Although you will need to output the difference of the previous max height to current column height in the stack to then add it to the sum.

Code:

    def trap(height: List[int]) -> int:
        sum = 0
        l,r = 0, len(height) - 1
        left_max = right_max = 0

        while l < r:
            if height[l] < height[r]:
                left_max = max(left_max, height[l])
                sum += left_max - height[l]
                l += 1
            else:
                right_max = max(right_max, height[r])
                sum += right_max - height[r]
                r -= 1

        return sum

[TinySousage]

I've just solved the level. Here's my code:
It's javascript, but it's similar to what you might use for your CPU.
It searches for peaks and then calculate amount of water between the peaks.

// arr1 ... arr8 are examples of different levels (what you get from Input)
const arr1 = [4,6,1,4,6,5,1,4,1,2,6,5,6,1,4,2,0];
const arr2 = [2,5,1,5,1,2,1,5,1,2,2,4,5,5,4,1,0];
const arr3 = [6,1,1,1,2,1,1,1,1,1,3,1,1,1,1,6,0];
const arr4 = [1,2,3,4,5,6,6,6,6,6,6,5,4,3,2,1,0];
const arr5 = [5,1,1,6,1,1,5,1,1,4,1,1,3,1,1,2,0];
const arr6 = [1,5,3,1,2,1,1,1,1,1,1,1,1,1,1,1,0];
const arr7 = [1,1,1,1,1,1,1,1,1,1,1,1,3,1,4,6,0];
const arr8 = [3,3,1,3,4,4,3,4,2,6,1,6,6,3,5,5,0];
const arr = arr1;

// r0 - r11 are the registers
const RAM = []; for(let i=0;i<256;i++) {RAM = 0};
let r0=0,r1=0,r2=0,r3=0,r4=0,r5=0,r6=0,r7=0,r8=0,r9=0,r10=0,r11=0,r12=0,r13=0,r14=0,r15=0,r16=0;
let alu1=0,alu2=0,alu3=0,alu4=0;

/*
r9 - total amount of water
r10 - array start coord
r11 - amount of highs
r0 - index
r1 - array coord

r2 - up
r3 - left
r4 - right
r5 - high
r6 - loop high

r8 = number of current segment
r2 = a right
r3 = a high
r4 = b left
r5 = b high
r6 = loop high

r6 = column water
r7 = water level of a segment
*/

r0 = 1;
read();
scan();
if (r11 > 1) {
  next();
} else {
  r9 = 0;
}
console.log(r9);
// Functions:
function read() {
  RAM[r0] = arr[r0 - 1];
  r0++;
  if (r0 >= 17) return;
  read();
}
function scan() {
  r2 = 1;
  r0+=1;
  r1 = r0;
  r10 = r1;
  r3 = -1;
  r0 = 0;
  for(;;) {
    r6 = RAM[r0];
    if (!(r6 <= r5)) {
      r3 = r0; r3--;
      r5 = r6;
      r2 = 1;
    }
    if (!(r6 >= r5) && !(r2 === 0)) {
      r4 = r0;
      RAM[r1] = r3; r1++;
      RAM[r1] = r4; r1++;
      RAM[r1] = r5; r1++;
      r2 = 0;
      r11++;
    }
    r5 = r6;
    if (r0 > 18) break;
    r0++;
  }
}
function next() {
  if (r8 >= r11 - 1) return;
  r1 = r10 + r8 * 3;
  r2 = RAM[r1 + 1];
  r3 = RAM[r1 + 2];
  r4 = 0;
  r5 = 0;
  r0 = r8 + 1;
  for(;;) {
    r1 = r10 + r0 * 3;
    r6 = RAM[r1 + 2];
    if (r6 >= r3) {
      r4 = RAM[r1];
      r5 = r6;
      r8 = r0;
      break;
    }
    if (r6 > r5) {
      r4 = RAM[r1];
      r5 = r6;
      r8 = r0;
    }
    r0++;
    if (r0 >= r11) break;
  }
  water();
  next();
}
function water() {
  r7 = r3;
  if (r5 < r3) {
    r7 = r5;
  }
  r0 = r2;
  for(;;) {
    if (r0 > r4) break;
    alu1 = RAM[r0];
    r0++;
    if (alu1 >= r7) continue;
    r6 = r7 - alu1;
    r9 += r6;
  }
}