DEV Community

dev.to staff
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
Alt Text

The Bird-brain Calculations
Alt Text

Alt Text

Alt Text

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!

Top comments (4)

Collapse
 
willsmart profile image
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('')
    ]
Collapse
 
larisho profile image
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
Collapse
 
choroba profile image
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__

Some comments may only be visible to logged-in visitors. Sign in to view all comments.