dev.to staff

Posted on

Daily Challenge #77 - Bird Mountain

A bird flying high above a mountain range is able to estimate the height of the highest peak.

Can you?

Example
The Birds Eye View

The Bird-brain Calculations

`Height=3`

This challenge comes from dinglemouse at CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

willsmart • Edited

A TypeScript version using reduces and maps to avoid too much mutation.
The main loop early exits if possible (if there are no hills left), otherwise it erodes the mountainscape by one hill. The `starPattern` array determines how this erosion happens, and it seems that the challenge uses up-down-left-right-dot.

``````const starPattern = [[0, 0], [-1, 0], [1, 0], [0, -1], [0, 1]];

const hillCount = (mountains: string[][]): number =>
mountains.reduce((acc, row) => acc + row.reduce((acc, dot) => acc + Number(dot === "^"), 0), 0);

const peakHeight = (mountains: string[][]): number =>
Array.from({
length: mountains.length,
}).findIndex(() => {
if (hillCount(mountains) === 0) return true;
mountains = mountains.map((row, rowIndex) =>
row.map((_, colIndex) =>
starPattern.reduce((acc, [x, y]) => acc && (mountains[rowIndex + y] || [])[colIndex + x] == "^", true)
? "^"
: " "
)
);
return false;
});
``````

Tested on Kata in its JS form.

Note that on there the mountains are defined using something like this:

``````const mountains = [
"^^^^^^        ".split(''),
" ^^^^^^^^     ".split(''),
"  ^^^^^^^     ".split(''),
"  ^^^^^       ".split(''),
"  ^^^^^^^^^^^ ".split(''),
"  ^^^^^^      ".split(''),
"  ^^^^        ".split('')
]
``````

Gab • Edited

Clojure solution:

``````;; These could be improved into a macro but want readability
(defn check-left [row col mountains]
"Checks the cell to the left"
(if (and (>= (- col 1) 0)
(.equals ((mountains row) (- col 1)) "^"))
true
false))
(defn check-up [row col mountains]
"Checks the cell above"
(if (and (>= (- row 1) 0)
(.equals ((mountains (- row 1)) col) "^"))
true
false))
(defn check-right [row col mountains]
"Checks the cell to the right"
(if (and (< (+ col 1) (count (mountains row)))
(.equals ((mountains row) (+ col 1)) "^"))
true
false))
(defn check-down [row col mountains]
"Checks the cell below"
(if (and (< (+ row 1) (count mountains))
(.equals ((mountains (+ row 1)) col) "^"))
true
false))

(defn will-erode? [row col mountains]
"Returns true if the current cell is not completely surrounded by mountains"
(not
(and (check-left row col mountains)
(check-up row col mountains)
(check-right row col mountains)
(check-down row col mountains))))

(defn erode-mountains [mountains errosion-symbol]
"Erodes the mountains once"
(into []
(map-indexed
(fn [row-index row]
(into []
(map-indexed
(fn [col-index col]
(if (and (.equals col "^")
(will-erode? row-index col-index mountains))
errosion-symbol
col))
row)))
mountains)))

(defn fully-eroded? [mountains]
(nil?
(first (filter #(.equals "^" %)
(flatten mountains)))))

(defn peak-height [mountains]
"Get the peak height (according to a fictional bird)"
(loop [times 0
mts mountains]
(if-not (fully-eroded? mts)
(recur (+ times 1) (erode-mountains mts times))
times)))

(def mountains [
[ "^" "^" "^" "^" "^" "^" " " " " " " " " " " " " " " " " ]
[ " " "^" "^" "^" "^" "^" "^" "^" "^" " " " " " " " " " " ]
[ " " " " "^" "^" "^" "^" "^" "^" "^" " " " " " " " " " " ]
[ " " " " "^" "^" "^" "^" "^" " " " " " " " " " " " " " " ]
[ " " " " "^" "^" "^" "^" "^" "^" "^" "^" "^" "^" "^" " " ]
[ " " " " "^" "^" "^" "^" "^" "^" " " " " " " " " " " " " ]
[ " " " " "^" "^" "^" "^" " " " " " " " " " " " " " " " " ]
])

(peak-height mountains)
;; 3
``````

E. Choroba • Edited

Not as elegant as I hoped. Debugging output included.

``````#!/usr/bin/perl
use warnings;
use strict;

use List::Util qw{ max };

sub populate {
my (\$view) = @_;
my @grid;
my \$y = 1;
my \$max_x = 0;
for my \$line (split /\n/, \$view) {
my \$x = 0;
for my \$char (split //, " \$line") {
\$grid[\$y][\$x++] = (0, undef)[\$char eq ' '];
\$max_x = \$x if \$x > \$max_x;
}
++\$y;
}
return \$max_x, @grid, []
}

sub height {
my (\$view) = @_;
my (\$max_x, @grid) = populate(\$view);
my @height = map [ map defined \$_ ? 0 : -1, @{ \$grid[\$_] }[0 .. \$max_x] ],
0 .. \$#grid;
my \$max_height = 0;
my \$change = 1;
while (\$change) {
undef \$change;
show(@height);
my @next = map [ @\$_ ], @height;
for my \$x (0 .. \$max_x) {
for my \$y (0 .. \$#grid) {
my @neighbours
= map \$height[ \$_->[1] ][ \$_->[0] ] // -1,
grep \$_->[1] >= 0 && \$_->[0] >= 0,
[\$x-1, \$y], [\$x+1, \$y], [\$x, \$y-1], [\$x, \$y+1];
if (\$height[\$y][\$x] == 0
&& grep \$_ == \$max_height - 1, @neighbours
) {
\$next[\$y][\$x] = 1 + max(@neighbours);
\$change = 1;
}
}
}
@height = @next;
++\$max_height unless \$max_height;
++\$max_height;
}
return \$max_height - 2
}

sub show {
for my \$line (@_) {
printf '%3s', \$_ for @\$line;
print "\n";
}
print "\n";
}

use Test::More tests => 4;

is height(<< '__INPUT__'), 2;
^^^
^^^
^^^
__INPUT__

is height(<< '__INPUT__'), 2;
^^^^^^^
^^^^^^^
^^^^^^^
^^^ ^^^
^^^^^^^
^^^^^^^
^^^^^^^
__INPUT__

is height(<< '__INPUT__'), 4;
^^^^^^^
^^^^^^^
^^^^^^^
^^^^^^^
^^^^^^^
^^^^^^^
^^^^^^^
__INPUT__

is height(<< '__INPUT__'), 3;
^^^^^^
^^^^^^^^
^^^^^^^
^^^^^
^^^^^^^^^^^^^
^^^^^^
^^^^
__INPUT__
``````