previndexinfonext

code guessing, round #27 (completed)

started at ; stage 2 at ; ended at

specification

looks like rain. your challenge this round is to trap rainwater. submissions may be written in python, c, rust, or lua.

your input will be a list of non-negative integers representing an elevation map for a landscape viewed from the side, like so:

[0,1,0,2,1,0,1,3,2,1,2,1]
=>
       #
   #   ## #
 # ## ######

now imagine a long, 100-year downpour attacks the land. after the deluge is over, water will have collected:

       #
   #~~~##~#
 #~##~######

note that the ground is solid, but water falls out the sides, eventually streaming down and falling into the infinite abyss nearby.

in this example, a total of 6 units of rainwater were collected. your challenge, given an elevation map, is to return the amount of water left after the rain.

and now, the APIs:

results

  1. 👑 GNU Radio Shows +3 -0 = 3
    1. LyricLy
    2. moshikoi (was IFcoltransG)
    3. lynn (was razetime)
    4. IFcoltransG (was moshikoi)
    5. razetime (was lynn)
    6. umnikos
    7. olus2000
  2. IFcoltransG +2 -0 = 2
    1. umnikos (was LyricLy)
    2. moshikoi (was GNU Radio Shows)
    3. GNU Radio Shows (was razetime)
    4. LyricLy (was moshikoi)
    5. lynn
    6. razetime (was umnikos)
    7. olus2000
  3. razetime +1 -0 = 1
    1. IFcoltransG (was LyricLy)
    2. moshikoi (was GNU Radio Shows)
    3. umnikos (was IFcoltransG)
    4. LyricLy (was moshikoi)
    5. GNU Radio Shows (was lynn)
    6. lynn (was umnikos)
    7. olus2000
  4. moshikoi +1 -0 = 1
    1. GNU Radio Shows (was LyricLy)
    2. umnikos (was GNU Radio Shows)
    3. LyricLy (was IFcoltransG)
    4. IFcoltransG (was razetime)
    5. razetime (was lynn)
    6. lynn (was umnikos)
    7. olus2000
  5. LyricLy +1 -1 = 0
    1. moshikoi (was GNU Radio Shows)
    2. umnikos (was IFcoltransG)
    3. IFcoltransG (was razetime)
    4. razetime (was moshikoi)
    5. GNU Radio Shows (was lynn)
    6. lynn (was umnikos)
    7. olus2000
  6. umnikos +1 -1 = 0
    1. razetime (was LyricLy)
    2. moshikoi (was GNU Radio Shows)
    3. GNU Radio Shows (was IFcoltransG)
    4. IFcoltransG (was razetime)
    5. lynn (was moshikoi)
    6. LyricLy (was lynn)
    7. olus2000
  7. lynn +0 -1 = -1
    1. olus2000 +0 -6 = -6
      1. GNU Radio Shows (was LyricLy)
      2. umnikos (was GNU Radio Shows)
      3. moshikoi (was IFcoltransG)
      4. lynn (was razetime)
      5. LyricLy (was moshikoi)
      6. razetime (was lynn)
      7. IFcoltransG (was umnikos)

    entries

    you can download all the entries

    entry #1

    written by LyricLy
    submitted at
    2 likes

    guesses
    comments 0

    post a comment


    placeholder.rs ASCII text, with CRLF line terminators
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    fn find_min(heights: &[u32]) -> (usize, &u32) {
        heights.iter().enumerate().max_by_key(|(_, &x)| x).unwrap_or((0, &0))
    }
    
    ///                      #            #
    ///                                   #
    ///                      ##           ##
    ///                      #            ##
    ///                                   ##             #          ##  #
    ///       #              #            ##             #          ##  #
    ///   #   ## #   rotate  ###  extend  ###  truncate  ##   wall  ### #
    /// # ## ######    ->    ##     ->    ###     ->     ##    ->   ### #
    ///                      #            ###            ##         ### #
    ///                      ##           ###            ##         ### #
    ///                      #            ###
    ///
    fn rotate_right(heights: &[u32]) -> Vec<u32> {
        let mut new = Vec::new();
        let (min, &min_elem) = find_min(heights);
    
        'outer: for i in 0..min_elem {
            for (j, &height) in heights.iter().enumerate() {
                if height > i {
                    new.push((min - j) as u32);
                    continue 'outer;
                }
            }
        }
    
        // wall
        new.insert(0, min as u32);
        new.push(min as u32);
    
        new
    }
    
    ///                        #            #
    ///                       ##           ##
    ///                        #           ##
    ///                       ##           ##
    ///                      ###          ###
    ///       #                #          ###              #        #  ##
    ///   #   ## #   rotate       extend  ###  truncate   ##  wall  # ###
    /// # ## ######    ->      #    ->    ###     ->      ##   ->   # ###
    ///                       ##          ###             ##        # ###
    ///                                   ###
    ///                        #          ###
    ///
    fn rotate_left(heights: &[u32]) -> Vec<u32> {
        let mut new = Vec::new();
        let (min, &min_elem) = find_min(heights);
        let min = heights.len() - min - 1;
    
        'outer: for i in (0..min_elem).rev() {
            for (j, &height) in heights.iter().rev().enumerate() {
                if height > i {
                    new.push((min - j) as u32);
                    continue 'outer;
                }
            }
            break;
        }
    
        // wall
        new.insert(0, min as u32);
        new.push(min as u32);
    
        new
    }
    
    pub fn entry(height: &[u32]) -> u32 {
        if height.is_empty() || height.iter().all(|&x| x == height[0]) {
            return 0;
        }
        let s1 = entry(&rotate_right(height));
        let s2 = entry(&rotate_left(height));
        height.len() as u32 * height.iter().copied().max().unwrap_or(0) - height.iter().sum::<u32>() - s1 - s2
    }
    

    entry #2

    written by GNU Radio Shows
    submitted at
    1 like

    guesses
    comments 0

    post a comment


    terain.py ASCII text, with no line terminators
    1
    entry = lambda terrain: sum("".join(" #"[e > h] for e in terrain).strip().count(" ") for h in range(max(terrain)))
    

    entry #3

    written by IFcoltransG
    submitted at
    1 like

    guesses
    comments 0

    post a comment


    entry.rs ASCII text, with no line terminators
    1
    pub fn entry(t:&[u32])->u32{(0..t.len()).flat_map(|i|t[..i].iter().max().min(t[i..].iter().max())?.checked_sub(t[i])).sum()}
    

    entry #4

    written by razetime
    submitted at
    0 likes

    guesses
    comments 0

    post a comment


    subway.py ASCII text
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    import re
    def entry(terrain):
    	str = ''
    	for i in range(max(terrain)):
    		for j in range(len(terrain)):
    			if i < terrain[j]:
    				str += '#'
    			else:
    				str += ' '
    		str += '\n'
    	collected,_ = re.subn('# +#', lambda match: match.group(0).replace(' ','@'), str)
    	return collected.count('@')
    

    entry #5

    written by moshikoi
    submitted at
    0 likes

    guesses
    comments 0

    post a comment


    entry.c ASCII text
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    #include <inttypes.h>
    
    #define FLOOD for (size_t i = 0; i < w; ++i) {
    #define FILL for (size_t j = 0; j < h; ++j) {
    #define DRAIN }
    #define DOWNPOUR while (rain(m, w, h));
    #define M(i) m[(i)*h + j]
    
    enum { W, A, G };
    
    int rain(char *m, size_t w, size_t h) {
      int d = 0;
      FLOOD
      FILL int l = i > 0 && M(i - 1) != A;
      int r = i < w - 1 && M(i + 1) != A;
      if (M(i) == W && !(l && r)) { M(i) = A; d = 1; }
      DRAIN
      DRAIN
      return d;
    }
    
    unsigned entry(unsigned *const t, size_t w) {
      unsigned h = 0;
      FLOOD
      h ^= (h < t[i]) * (t[i] ^ h);
      DRAIN
      char m[w * h];
      FLOOD
      FILL M(i) = j < t[i] ? G : W;
      DRAIN
      DRAIN
      DOWNPOUR
      int c = 0;
      FLOOD
      FILL c += M(i) == W;
      DRAIN
      DRAIN
      return c;
    }
    
    #undef FLOOD
    #undef FILL
    #undef DRAIN
    #undef DOWNPOUR
    #undef M
    

    entry #6

    written by lynn
    submitted at
    1 like

    guesses
    comments 0

    post a comment


    cg27.py Unicode text, UTF-8 text, with CRLF line terminators
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    import itertools
    import functools
    import operator
    
    
    def vectorize(f):
        def g(*args):
            match args:
                case [*x], [*y]:
                    return [*map(f, x, y)]
                case [*x], y:
                    return [f(a, y) for a in x]
                case x, [*y]:
                    return [f(x, b) for b in y]
                case x, y:
                    return f(x, y)
    
        return g
    
    
    def evaluate(ast, input):
        if ast == "a":
            return input
        if callable(ast):
            return ast
        acc = evaluate(ast[-1], input)
        i = len(ast) - 2
        while i >= 0:
            assert callable(f := ast[i])
            if i > 0 and not callable(lhs := evaluate(ast[i - 1], input)):
                acc = f(lhs, acc)
                i -= 2
            else:
                acc = f(acc)
                i -= 1
        return acc
    
    
    builtins = {
        "+": vectorize(operator.add),
        "-": vectorize(operator.sub),
        "⌊": vectorize(min),
        "⌈": vectorize(max),
        "⌽": lambda x: list(reversed(x)),
    }
    
    
    def run(code, input):
        stack = [[]]
        for c in code:
            if c == "(":
                stack.append([])
            elif c == ")":
                top = stack.pop()
                stack[-1].append(top)
            elif c == "/":
                f = stack[-1].pop()
                stack[-1].append(lambda x, f=f: functools.reduce(f, x))
            elif c == "\\":
                f = stack[-1].pop()
                stack[-1].append(lambda x, f=f: list(itertools.accumulate(x, f)))
            else:
                stack[-1].append(builtins.get(c, c))
        return evaluate(stack.pop(), input)
    
    
    entry = functools.partial(run, r"+/((⌈\a)⌊⌽⌈\⌽a)-a")
    
    print(entry([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
    

    entry #7

    written by umnikos
    submitted at
    1 like

    guesses
    comments 0

    post a comment


    橄欖做到了.rs Unicode text, UTF-8 text
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    //! 香港就是中國!!!
    use rand::seq::SliceRandom;
    use rand::thread_rng;
    use std::process::Command;
    use std::thread::sleep_ms;
    
    pub fn entry(地形: &[u32]) -> u32 {
        let mut 水位 = Vec::from(地形);
    
        // 傾盆大雨!!!
        for 地點 in 0..地形.len() {
            水位[地點] = *地形.iter().max().unwrap();
        }
    
        // 和一千年的涓涓細流
        for  in 0..1000 {
            let 地點 =  % 地形.len();
            if 地點 == 0 || 地點 == 地形.len() - 1 {
                水位[0] = 地形[0];
                水位[地形.len() - 1] = 地形[地形.len() - 1];
                continue;
            }
    
            if 水位[地點] <= 地形[地點] {
                水位[地點] = 地形[地點];
                continue;
            }
    
            let 偏見 = ['左', '右'].choose(&mut thread_rng()).unwrap();
            match 偏見 {
                '左' => {
                    if 水位[地點 - 1] < 水位[地點] {
                        水位[地點 - 1] += 1;
                        水位[地點] -= 1;
                    }
                }
                '右' => {
                    if 水位[地點 + 1] < 水位[地點] {
                        水位[地點 + 1] += 1;
                        水位[地點] -= 1;
                    }
                }
                _ => unreachable!(),
            }
    
            Command::new("cls").status().unwrap();
            for  in (1..地形.iter().max().unwrap() + 3).rev() {
                for  in 0..地形.len() {
                    if 地形.iter().enumerate().max_by_key(|(_, )| *).unwrap() == (, &( - 1))
                    {
                        print!("屋");
                    } else if  > 水位[] {
                        print!("一");
                    } else if  > 地形[] {
                        print!("水");
                    } else {
                        print!("土");
                    }
                }
                print!("\n");
            }
            sleep_ms(20);
        }
    
        (0..地形.len()).map(|| 水位[] - 地形[]).sum()
    }
    
    fn main() {
        let 地形 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
        println!("{}", entry(&地形));
    }
    

    entry #8

    written by olus2000
    submitted at
    1 like

    guesses
    comments 2
    olus2000 *known at the time as [author of #8]

    it works for arrays of up to 16 elements but can be easily extended to 255


    razetime

    woah holy shit


    post a comment


    leg.lua ASCII text
      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    asm = [[
    # load values to memory
    label loadloop
    add+I 0 IO mem
    jle mem 1 not_max
    add+I 0 adr 0
    add+I 0 mem 1
    label not_max
    add+I 1 adr adr
    jne+I 16 adr loadloop
    
    # 0: max index (set while loading)
    # 1: max height
    # 2: water
    # stack: tmp
    # adr: adr
    # mem: heights
    
    # reset adr and max height
    add+I+J 0 255 adr
    add+I+J 0 0 1
    
    label first_loop
    add+I 1 adr adr
    jeq adr 0 second_part
    jgt mem 1 update_max_first
    sub 1 mem stack
    add 2 stack+pop 2
    jeq+I+J 0 0 first_loop
    
    label update_max_first
    add+I 0 mem 1
    jeq+I+J 0 0 first_loop
    
    label second_part
    add+I+J 0 16 adr
    add+I+J 0 0 1
    
    label second_loop
    sub+J adr 1 adr
    jeq adr 0 end
    jgt mem 1 update_max_second
    sub 1 mem stack
    add 2 stack+pop 2
    jeq+I+J 0 0 second_loop
    
    label update_max_second
    add+I 0 mem 1
    jeq+I+J 0 0 second_loop
    
    label end
    add+I 0 2 IO
    ]]
    
    
    codes = {
        
        jge = 0x25,
        jgt = 0x24,
        jle = 0x23,
        jlt = 0x22,
        jne = 0x21,
        jeq = 0x20,
    
        shl = 7,
        shr = 6,
        xor = 5,
        ["not"] = 4,
        ["or"]  = 3,
        ["and"] = 2,
        sub = 1,
        add = 0,
    
        I = 0x80,
        J = 0x40,
        jump = 0x20,
    
        stack = 3, pop = 8,
        adr   = 4,
        mem   = 5,
        IP    = 6,
        IO    = 7,
    
    }
    
    
    compile = function(asm)
        local no_coms = ""
        for l in asm:gmatch("[^\n]*") do
            if l:sub(1,1) ~= "#" then
                no_coms = no_coms .. " " .. l
            end
        end
        local iter = no_coms:gmatch("(%+?)([%w_]+)")
        local rom, labels, i = {}, {}, 0
    
        local plus, com = iter()
        while com do
            if com == "label" then
                plus, com = iter()
                labels[com] = labels[com] or {}
                labels[com].target = i
            else
                if plus ~= "+" then
                    rom[i] = 0
                    i = i + 1
                end
                if codes[com] then
                    rom[i - 1] = rom[i - 1] + codes[com]
                elseif tonumber(com) then
                    rom[i - 1] = rom[i - 1] + com
                else
                    labels[com] = labels[com] or {}
                    table.insert(labels[com], i - 1)
                end
            end
            plus, com = iter()
        end
        for k, v in pairs(labels) do
            for i = 1, #v do
                if v.target then
                    rom[v[i]] = rom[v[i]] + v.target
                else
                    print("A label without a target: "..k)
                end
            end
        end
        return rom
    end
    
    
    emulate = function(rom, input)
        local ram, stack, out = {}, {}, {}
        local ip, r0, r1, r2, adr = 0, 0, 0, 0, 0
        while rom[ip + 3] do
            local com, imm1, imm2, imm3 = rom[ip], rom[ip + 1], rom[ip + 2], rom[ip + 3]
            ip = ip + 4
            local regs = {[0] = r0, r1, r2, stack[#stack] or 0, adr, ram[adr] or 0, ip, input[1] or 0}
            local arg1, arg2, flag, ans
            if com & codes.I > 0 then
                arg1 = imm1
            else
                arg1 = regs[imm1 & 7]
            end
            if com & codes.J > 0 then
                arg2 = imm2
            else
                arg2 = regs[imm2 & 7]
            end
            if imm1 & 7 == 7 or imm2 & 7 == 7 and #input > 0
                then table.remove(input, 1) end
            if imm1 & 8 > 0 then table.remove(stack) end
            if com & codes.jump > 0 then
                if com & 7 == codes.jge & 7 then
                    flag = arg1 >= arg2
                elseif com & 7 == codes.jgt & 7 then
                    flag = arg1 > arg2
                elseif com & 7 == codes.jle & 7 then
                    flag = arg1 <= arg2
                elseif com & 7 == codes.jlt & 7 then
                    flag = arg1 < arg2
                elseif com & 7 == codes.jne & 7 then
                    flag = arg1 ~= arg2
                elseif com & 7 == codes.jeq & 7 then
                    flag = arg1 == arg2
                end
                if flag then ip = imm3 end
            else
                if com & 7 == codes.shl then
                    ans = arg1 << arg2
                elseif com & 7 == codes.shr then
                    ans = arg1 >> arg2
                elseif com & 7 == codes.xor then
                    ans = arg1 ~ arg2
                elseif com & 7 == codes["not"] then
                    ans = ~arg1
                elseif com & 7 == codes["or"] then
                    ans = arg1 | arg2
                elseif com & 7 == codes["and"] then
                    ans = arg1 & arg2
                elseif com & 7 == codes.sub then
                    ans = arg1 - arg2
                elseif com & 7 == codes.add then
                    ans = arg1 + arg2
                end
                ans = ans & 255
                if imm3 & 7 == 0 then r0 = ans
                elseif imm3 & 7 == 1 then r1 = ans
                elseif imm3 & 7 == 2 then r2 = ans
                elseif imm3 & 7 == 3 then table.insert(stack, ans)
                elseif imm3 & 7 == 4 then adr = ans
                elseif imm3 & 7 == 5 then ram[adr] = ans
                elseif imm3 & 7 == 6 then ip = ans
                elseif imm3 & 7 == 7 then table.insert(out, ans)
                end
            end
        end
        return out
    end
    
    
    entry = function(t) return emulate(compile(asm), t)[1] end