A return the number of trees in a map

user_8425613 0
Viewed 55

Let's say I have a map written in ASCII. This map represents the gardens of some people. I have to write a program that, given the map returns how many trees there are in each garden. A mockup map:

+-----------+------------------------------------+
|           |    B  A                            |
|  A A A A  |     A       (Jennifer)             |
|           |                                    |
|     C     +--------------+---------------------+
|       B        C         |                     |
|   B       C              |                B B  |
|     B       C            |    (Marta)          |
|         B                |                     |
+--------------+           |                     |
|              |           |                     |
| (Peter) B    |           |             A       |
|   C          |  (Maria)  |                     |
|     A        |           |                     |
+--------------+           +---------------------+
|              |           |                     |
|              |           |                     |
|              |           |                     |
| (Elsa)       +           |      (Joe)          |
|             /            |        C            |
|   C  A     /      A      +      C   A    A     |
|    B      /     A   B     \     A   B          |
|     B A  /        C        \           B       |
+---------+----+---------- +--+------------------+

the output should be something like:

Jennifer B:1 A:1 C:0
Marta    B:2 A:1 C:0
Peter    A:1 B:1 C:1
...
Joe      A:3 B:2 C:2

Is there any package in python or any algorithm that I can study to understand how to perform this task?

ascii-art ascii algorithm python
2 Answers

I would start creating a matrix of chars from that ascii.

Then I would find all the (i,j) of the '('.

Found that indexes you can create a dictionary with the name of the people as key and another dictionary as value. Each one of the inner dictionaries will have the tree name as key and a integer as value.

Knowing (i,j) of the '(' i would read the names and initilize the dictionary.

Now, foreach (i,j) pointing at a '(' do: (let name be the name related to the '('

  • che if at the left of '(' there is a letter. if you find a letter x let dict[name][x]++ (stop if you find any of ('|','','/','+')
  • do the same for the right
  • start going upwards, for each line check left and right
  • do the same while going downwards

you just have to play a bit to understand how to recognize correctly the wall between maria and jennifer.

user_34159930

Here is an example in JavaScript that should be fairly easy to translate to Python. It scans left to right, relying on a determination of the current labeled area. Hopefully the function names and comments make clear what it happening. If you have questions, please ask.

function f(map){
  const m = map.split('\n')
    .filter(x => x)
    .map(x => x.trim());
    
  const [h, w] = [m.length, m[0].length];
  
  const borders = ['+', '-', '|', '/', '\\'];
  const trees = ['A', 'B', 'C'];
  
  const labelToName = {};
  const result = {};
  
  let prevLabels = new Array(w).fill(0);
  let currLabels = new Array(w).fill(0);
  let label = 1;
  
  function getLabel(y, x){
    // A label is the same as
    // a non-border to the left,
    // above, or northeast.
    if (!borders.includes(m[y][x-1]))
      return currLabels[x-1];
    else if (!borders.includes(m[y-1][x]))
      return prevLabels[x];
    else if (!borders.includes(m[y-1][x+1]))
      return prevLabels[x+1];
    else
      return label++;
  }
  
  function update(label, tree){
    if (!result[label])
      result[label] = {[tree]: 1};
    else if (result[label][tree])
      result[label][tree]++;
    else
      result[label][tree] = 1;
  }
  
  for (let y=1; y<h-1; y++){
    for (let x=1; x<w-1; x++){
      const tile = m[y][x];
      
      if (borders.includes(tile))
        continue;
        
      const currLabel = getLabel(y, x);
      currLabels[x] = currLabel;
      
      if (tile == '('){
        let name = '';
        while (m[y][++x] != ')'){
          name += m[y][x];
          currLabels[x] = currLabel;
        }
        currLabels[x] = currLabel;
        labelToName[currLabel] = name;
      
      } else if (trees.includes(tile)){
        update(currLabel, tile);
      }
    }
    
    prevLabels = currLabels;
    currLabels = new Array(w).fill(0);
  }
  
  return [result, labelToName];
}

var map = `
    +-----------+------------------------------------+
    |           |    B  A                            |
    |  A A A A  |     A       (Jennifer)             |
    |           |                                    |
    |     C     +--------------+---------------------+
    |       B        C         |                     |
    |   B       C              |                B B  |
    |     B       C            |    (Marta)          |
    |         B                |                     |
    +--------------+           |                     |
    |              |           |                     |
    | (Peter) B    |           |             A       |
    |   C          |  (Maria)  |                     |
    |     A        |           |                     |
    +--------------+           +---------------------+
    |              |           |                     |
    |              |           |                     |
    |              |           |                     |
    | (Elsa)       +           |      (Joe)          |
    |             /            |        C            |
    |   C  A     /      A      +      C   A    A     |
    |    B      /     A   B     \\     A   B          |
    |     B A  /        C        \\           B       |
    +---------+----+---------- +--+------------------+
`;

var [result, labelToName] = f(map);
for (let label in result)
  console.log(`${ labelToName[label] }: ${ JSON.stringify(result[label]) }`)

user_20347870
Related