prev • index • info • next

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. 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
  6. 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
  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