11
\$\begingroup\$

An entry for the August 2016 Community Challenge

I slightly modified the input and output to suit the snippet tool, and also because I really like the mapped output with the basins.

I have been golfing a lot recently, which always impacts my coding style. You will find a number of possibly too smart one-liners. I am looking for more gracious alternatives.

//1 liner helper functions
const $ = id => { return document.getElementById(id); },
      trim = s => { return s.trim(); },
      splitNumbersOnSpace = s => { return s.split(' ').map(Number); },
      join = a => { return a.join('') };

//DOM elements
const input = $('input'),
      output = $('output'),
      output2 = $('output2'),
      go = $('go');

go.addEventListener('click', () => {
  
  const depths = input.value.split('\n').map(trim).map(splitNumbersOnSpace),
        basins = Array(depths.length).fill().map(()=>{return [];}),
        basinDepths = new Map();
  let nextBasin = 1; 
  
  //compare a spot with the lowest neighbour thus far
  function compareNeighbour( lowestSpotSoFar, attemptRow, attemptCol ){
    try {
      if( depths[attemptRow][attemptCol] < lowestSpotSoFar.value ){
        lowestSpotSoFar.row = attemptRow;
        lowestSpotSoFar.col = attemptCol;
        lowestSpotSoFar.value = depths[attemptRow][attemptCol];
      }
    } catch (e) {
      //This is bound to happen due to out of bounds access requests            
    }    
  } 
  
  //For a given spot, try and find a lower neighbour
  function lowestNeighbour(spot){
    //Assume we are in a sink
    const lowest = {
      row: spot.row,
      col: spot.col,
      value: depths[spot.row][spot.col]
    }
    //Test the assumption
    compareNeighbour( lowest, spot.row + 1, spot.col );
    compareNeighbour( lowest, spot.row - 1, spot.col );
    compareNeighbour( lowest, spot.row, spot.col + 1 );
    compareNeighbour( lowest, spot.row, spot.col - 1 );
    return lowest;
  }
  
  //Mark a whole path as belong to a basin
  function markPath( path , basin ){
    basinDepths.set( basin , ( basinDepths.get( basin ) || 0 ) + path.length );    
    while(path.length){
      let spot  = path.shift();
      basins[spot.row][spot.col] = basin;
    }
  }

  //Recursively wander on the map towards a sink 
  function wander( path ){
    const spot = lowestNeighbour( path[0] );
    //We are on a sink
    if( spot.row == path[0].row && spot.col == path[0].col ){
      markPath( path , nextBasin++ );
    //We hit a known path to a sink  
    }else if ( basins[spot.row][spot.col] ){
      markPath( path , basins[spot.row][spot.col] );
    //Any other case, keep wandering  
    }else {
      path.unshift(spot);
      wander(path);
    }
  }
  
  //Analyze the depth map
  for( let row = 0 ; row < depths.length ; row++ ){
    for( let col = 0 ; col < depths[row].length ; col++ ){
      //We already know know the basin this spot belongs to
      if( basins[row][col] )
        continue;
      //We will now wander on a path to a sink
      wander( [{row,col}] );
    }
  }
  
  //Spit it out
  output.innerHTML = basins.map( join ).join( '<br>' );
  output2.innerHTML = 'Sizes: ' + Array.from( basinDepths.values() ).sort().join(' ');  
});
#output, #input {
  font-family: monospace;
}
<textarea id="input" rows="7">
    1 0 2 5 8 
    2 3 4 7 9 
    3 5 7 8 9 
    1 2 5 4 3 
    3 3 5 2 1</textarea>

  <button id="go">Analyze</button>
  <br><br>Output<br><br>
  <div id="output" ></div>
  <br><br>
  <div id="output2" ></div>

\$\endgroup\$
  • 1
    \$\begingroup\$ Are you trying to get a review from a code golf perspective? That IMO is not what happens here. For me this forum is more about professional code review, not how to minimize the number of lines of code you have, which is kind of antithetical in some ways to having clear, understandable code. \$\endgroup\$ – Mike Brant Aug 3 '16 at 15:58
  • 2
    \$\begingroup\$ Not at all. However, sometimes the more readable alternative is also the shorter one. If this were a golfed entry, it would look entirely different ;] \$\endgroup\$ – konijn Aug 3 '16 at 16:09
  • \$\begingroup\$ It seems that your code sorts the basin counts as strings, not as numbers, e.g. "1 11 2 22 3 4". \$\endgroup\$ – Martin R Aug 5 '16 at 19:37
5
\$\begingroup\$

I've been looking at this code for a good long while now, and I must admit I don't have much in terms of a review. It's all nicely done!

What few quibbles I have are minor:

  • output and output2 aren't really the best names, are they?

  • Also, basinDepths appears to actually hold basin sizes. The code already deals with "actual" depths, so the name's needlessly confusing.

  • Speaking of, "depth" is perhaps a slightly confusing term in this case. It's actually altitudes, and the rain flows from high to low. By calling it "depths", one would expect it to be the other way around: Water flowing to greater depth values.

  • The one-liners aren't all that useful. $ is fine (though maybe using document.querySelector would be nicer, as one might expect $ to behave jQuery-ish), but the rest are really only called once, as far as I can tell. So I would argue that this:

    const depths = input.value
      .split('\n')
      .map(line => line.trim().split(' ').map(Number));
    

    would be as clear as using extracted methods. Yes, it's nice to name and encapsulate the operations being performed, and the original line really reads quite well. Still... eh, just seems excessive when there's no re-use of said operations.
    Conversely, if you want to go all-in on English-like legibility, a lines function should perhaps take the place of split('\n')?

  • Your use of whitespace is... eclectic? I'm used to reproaching people for not using enough whitespace, but here it's the opposite. Maybe you're over-correcting after too much code golf? :)
    I just find it curious that a line like this:

    function markPath( path , basin ){
    

    has tons of space in the argument list, but nothing between ){ (esp. since you do use a space for x => { y } declarations... except in that place where you don't).
    Or that your else-if looks like this:

    }else if (...){
    

    when most would probably write:

    } else if(...) {
    

    instead. Indeed you do write if(...) { in other places.

    Again, it's not a disaster, but it is inconsistent and odd.

\$\endgroup\$
  • 3
    \$\begingroup\$ I noticed the same re:spacing but did not dare to update the question. Excellent point on the lack of re-use with one-liner functions, and basinSizes. \$\endgroup\$ – konijn Aug 4 '16 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.