Daily Challenge #77 - Bird Mountain

#challenge

dev.to staff Sep 26, 2019 ・1 min read

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!

Discussion

willsmart • Sep 26 '19

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 • Sep 28 '19

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 • Sep 26 '19

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__

EarlWare • Sep 26 '19

Swift Solution:

import Foundation


//                 0    1    2    3    4    5    6    7    8    9   10   11   12   13
let mountain = [ ["^", "^", "^", "^", "^", "^", "^", " ", " ", " ", " ", " ", " ", " "],   // 0
                 [" ", "^", "^", "^", "^", "^", "^", "^", "^", "^", " ", " ", " ", " "],   // 1
                 [" ", " ", "^", "^", "^", "^", "^", "^", "^", "^", " ", " ", " ", " "],   // 2
                 [" ", " ", "^", "^", "^", "^", "^", "^", " ", " ", " ", " ", " ", " "],   // 3
                 [" ", " ", "^", "^", "^", "^", "^", "^", "^", "^", "^", "^", "^", "^"],   // 4
                 [" ", " ", "^", "^", "^", "^", "^", "^", "^", " ", " ", " ", " ", " "],   // 5
                 [" ", " ", "^", "^", "^", "^", "^", " ", " ", " ", " ", " ", " ", " "] ]  // 6

//  simple check to see if its the selected tile for mountains.
func isMountainTile(tile:String) -> Bool {
    return tile == "^"
}

//  simple helper to check if any mountain tiles remain in the tileset
func hasMountains(mount:[[String]]) -> Bool {
    for rows in mount {
        for col in rows {
            if isMountainTile(tile:col) {
                return true
            }
        }
    }
    return false
}

//  simple helper to print out tileset neatly
func printMountain(mount:[[String]]) {
    for row in mount {
        print(row)
    }
}

/*
isValid

@param mount  2d array
@param row    the row of the slot we are looking at
@param col    the column of the slot we are looing at

@return returns true if the row & col are within the valid range of the given 2d array.
*/
func isValid(mount:[[String]], row:Int, col:Int) -> Bool {
    return ((row >= 0 || row < mount.count) || (col >= 0 || col < mount[row].count))
}

/*
 edgeCase

 @param mount  2d array of single character strings of either mountain tiles '^' or something else
 @param row    the row of the slot we are looking at
 @param col    the column of the slot we are looing at

 @return returns true if the row/col is accessible from an edge(left/right/up/down)
 */
func isEdgeCase(mount:[[String]], row:Int, col:Int) -> Bool {
    if !isValid(mount: mount, row: row, col: col) {
        return false
    } else {
        if (row == 0 || row == (mount.count-1)) || (col == 0 || col == (mount[row].count-1)) {
            return true     // we are definitely on an edge!
        } else if (!isMountainTile(tile:mount[row][col+1]) ||
                   !isMountainTile(tile:mount[row][col-1])) {
            return true // non mountain is either in front or behind us
        } else if (!isMountainTile(tile:mount[row+1][col]) ||
                   !isMountainTile(tile:mount[row-1][col])) {
           return true // non mountain is either above or below us
        }
    }
    return false
}

/*
 Challenge function BirdMountain

 @param 2d array of single character strings, either white space ' '  or mountain  '^'

 @return returns an Int of the calculated 'Height' of the mountain passed in.
*/
func birdMountain(mount:[[String]]) -> Int {
    var mountTiles = mount
    var cachedTiles = mountTiles
    var passNum = 0

    repeat {
        cachedTiles = mountTiles
        passNum += 1
        for row in 0..<mount.count {
            for col in 0..<mount[row].count {
                //  check every tile to see if its a mountain tile, and if so compare to the cached version to see if its an edge case.
                if (isMountainTile(tile:mountTiles[row][col]) &&
                    isEdgeCase(mount: cachedTiles, row: row, col: col)) {

                    mountTiles[row][col] = String(passNum)
                }
            }
        }
        print("Pass   #", passNum)
        printMountain(mount: mountTiles)
    } while hasMountains(mount: mountTiles)

    return passNum
}


print("Initial Mountain:  ")
printMountain(mount: mountain)
print("\n")


print("Height of the mountain is:   ", birdMountain(mount: mountain), "\n\n")

Output:

Initial Mountain:  
["^", "^", "^", "^", "^", "^", "^", " ", " ", " ", " ", " ", " ", " "]
[" ", "^", "^", "^", "^", "^", "^", "^", "^", "^", " ", " ", " ", " "]
[" ", " ", "^", "^", "^", "^", "^", "^", "^", "^", " ", " ", " ", " "]
[" ", " ", "^", "^", "^", "^", "^", "^", " ", " ", " ", " ", " ", " "]
[" ", " ", "^", "^", "^", "^", "^", "^", "^", "^", "^", "^", "^", "^"]
[" ", " ", "^", "^", "^", "^", "^", "^", "^", " ", " ", " ", " ", " "]
[" ", " ", "^", "^", "^", "^", "^", " ", " ", " ", " ", " ", " ", " "]


Pass   # 1
["1", "1", "1", "1", "1", "1", "1", " ", " ", " ", " ", " ", " ", " "]
[" ", "1", "^", "^", "^", "^", "^", "1", "1", "1", " ", " ", " ", " "]
[" ", " ", "1", "^", "^", "^", "^", "^", "1", "1", " ", " ", " ", " "]
[" ", " ", "1", "^", "^", "^", "^", "1", " ", " ", " ", " ", " ", " "]
[" ", " ", "1", "^", "^", "^", "^", "^", "1", "1", "1", "1", "1", "1"]
[" ", " ", "1", "^", "^", "^", "^", "1", "1", " ", " ", " ", " ", " "]
[" ", " ", "1", "1", "1", "1", "1", " ", " ", " ", " ", " ", " ", " "]
Pass   # 2
["1", "1", "1", "1", "1", "1", "1", " ", " ", " ", " ", " ", " ", " "]
[" ", "1", "2", "2", "2", "2", "2", "1", "1", "1", " ", " ", " ", " "]
[" ", " ", "1", "2", "^", "^", "^", "2", "1", "1", " ", " ", " ", " "]
[" ", " ", "1", "2", "^", "^", "2", "1", " ", " ", " ", " ", " ", " "]
[" ", " ", "1", "2", "^", "^", "^", "2", "1", "1", "1", "1", "1", "1"]
[" ", " ", "1", "2", "2", "2", "2", "1", "1", " ", " ", " ", " ", " "]
[" ", " ", "1", "1", "1", "1", "1", " ", " ", " ", " ", " ", " ", " "]
Pass   # 3
["1", "1", "1", "1", "1", "1", "1", " ", " ", " ", " ", " ", " ", " "]
[" ", "1", "2", "2", "2", "2", "2", "1", "1", "1", " ", " ", " ", " "]
[" ", " ", "1", "2", "3", "3", "3", "2", "1", "1", " ", " ", " ", " "]
[" ", " ", "1", "2", "3", "3", "2", "1", " ", " ", " ", " ", " ", " "]
[" ", " ", "1", "2", "3", "3", "3", "2", "1", "1", "1", "1", "1", "1"]
[" ", " ", "1", "2", "2", "2", "2", "1", "1", " ", " ", " ", " ", " "]
[" ", " ", "1", "1", "1", "1", "1", " ", " ", " ", " ", " ", " ", " "]
Height of the mountain is:    3 


Program ended with exit code: 0

Definitely feel like I'm going a little heavy on the looping, but I was having a hard time visualizing how I could map the increasing elevations without keeping a reference copy of the array to make sure I wasn't just blowing through everything on each pass.... Any suggestions for improvements would be appreciated!

DEV Community

DEV Community is a community of 554,873 amazing developers

Daily Challenge #77 - Bird Mountain

Discussion

Read next

Project Euler #6 - Sum Square Difference

30 Days of AWS (Day 5)

Front-end Challenge: Prevent Clicks

Project Euler #4 - Largest Palindrome Product