[HackRank/Scala] Recursive Trees

程序员文章站 2022-05-18 20:26:27

...

Creating a Fractal Tree from Y-shaped branches

This challenge involves the construction of trees, in the form of ASCII Art. The restriction is, that you need to accomplish this with functional programming, and you cannot declare even local variables!

We have to deal with real world constraints, so we cannot keep repeating the pattern infinitely. So, we will provide you a number of iterations, and you need to generate the ASCII version of the Fractal Tree for only those many iterations (or, levels of recursion). A few samples are provided below.

Iteration #1
In the beginning, we simply create a Y. There are 63 rows and 100 columns in the grid below. The triangle is composed of underscores and ones as shown below. The vertical segment and the slanting segments are both 16 characters in length.

_____________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_________________________________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_________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________

Iteration #2

At the top of the left and right branches of the first Y, we now add a pair of Y-shapes, which are half the size of the original Y.

____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_________________________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_________________________________
_________________________________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_________________________________________
_________________________________________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__________________________________________________

Input Format
A single integer, N.

Constraints
N <= 5
And, you need to accomplish this without directly defining any local variables. For example, var and val have been blocked in Scala; def and defn are blocked in Clojure.

Output Format
The Nth iteration of the Fractal Tree, as shown above. It should be a matrix of 63 rows and 100 columns. (i.e. 6300 printable characters) It should be composed entirely of underscores and ones, in a manner similar to the examples provided. Do not include any extra leading or trailing spaces.

画板是固定大小的 => 只需要将所需要设为1的坐标计算出来就可以了。
树增长的规律是递归的
函数设计。我把每颗树看做是一个元素，那么树增加的过程是将一个元素映射成多个元素(一对多)。描述这样一个元素需要两个Int，用case class可以很简单的封装。这样做，我可以把问题看成了一个元素映射的过程。因为树的生长是递归的，每次减半。所以，可以递归调用。由于画板是固定的，我将树的转化和绘制分成两步。

这题的分类是在Functional and Fractals中（函数化和分形）。我的理解是遇到分形的问题，就看成是一对多的映射。只要实现映射函数，分形问题就解决了。也就是flatMap中所需要的函数。

object Solution {
  case class Point(x:Int, y:Int)
  case class Tree(peak:Point, height:Int)
  def getZero:List[List[String]] = List.fill(63, 100)("_")
  def getIter(n:Int, trees:List[Tree], iter:List[List[String]]):List[List[String]] = n match {
    case 0 => iter
    case _ => getIter(n-1, expand(trees), update(trees, iter))
  }

  def expand(trees: List[Tree]):List[Tree] = trees.flatMap(expandOne)
  def expandOne(tree: Tree):List[Tree] = {
      List(Tree(Point(tree.peak.x - 2* tree.height ,tree.peak.y - tree.height), tree.height /2),
           Tree(Point(tree.peak.x - 2* tree.height ,tree.peak.y + tree.height), tree.height /2))
  }
  def update(trees: List[Tree], iter:List[List[String]]):List[List[String]] = trees match {
    case Nil => iter
    case h::t => update(t, updateOne(h, iter))
  }
  def updateOne(tree: Tree, iter:List[List[String]]):List[List[String]]  = iter.zipWithIndex.map{
    case (row, i) if (tree.peak.x - tree.height + 1 to tree.peak.x).toList.contains(i) => row.zipWithIndex.map{
      case (x, j) if j == tree.peak.y => "1"
      case (x,_) => x
    }
    case (row, i) if(tree.peak.x - 2*tree.height + 1 until tree.peak.x).toList.contains(i) => row.zipWithIndex.map{
      case (x,j) if j == tree.peak.y - i + 1 + tree.peak.x - tree.height
                 || j == tree.peak.y + i - 1 - tree.peak.x + tree.height => "1"
      case (x,_) => x
    }
    case (row, _) => row
  }
  def main(args: Array[String]): Unit = {
    getIter(scala.io.StdIn.readInt, List(Tree(Point(62, 49), 16)), getZero)
    .map(x => x.mkString).foreach(println)
  }
}