Conway’s Game of Life – Unlimited Edition(康威生命游戏-无限版)

最近也不知道在忙啥,反正好久没玩 codewars 了,上去看看的时候偶尔看到了一个很有意思的题目,稍微看了一下说明,感觉可以做出来,于是就开始了长达 2+2 个小时的解题过程。

下面是简单的题目说明:简单的来说,就是有一个二维数组,数组的每一个元素就是一个细胞,细胞有存活和死亡两种状态,每经过一代,细胞的状态都可以发生改变,有如下四个具体规则:

1、任何具有少于两个活邻居的活细胞都会死亡。
2、任何具有三个以上活邻居的活细胞都会死亡。
3、任何有两个或三个活邻居的活细胞都可以存活到下一代。
4、任何具有恰好三个活邻居的死细胞都将变为活细胞。

什么是邻居呢?就是围绕着该细胞的周围一圈,即八个细胞。

好了,在看完这些的时候,我的思路差不多就成型了。首先,我得获取到这个细胞周围细胞的状态,并且判断有几个活细胞,这样就能够根据规则判断各个细胞下一代的存活情况了。当我刷刷刷敲下代码,顺利地通过第一个测试的时候,我得意地提交了我的代码,结果出乎我的意料,在第三个测试之后陆续出现了问题。从此,我开始了长达半个小时的debug,但是仍然一无所获,只好绝望地看看讨论区的各位,结果,我发现了一点玄机!

首先,仔细点的朋友(不像我)就会发现,这道题的题目叫做 Conway’s Game of Life – Unlimited Edition,而我目前的思路,只是前半部分,并没有体现出Unlimited Edition(无限版)。发现了这个之后,我仔细地第无数次读题目,终于找到了一个关键信息,即这个区域是无限的,出了题目给的细胞之外,还有无数的死细胞,再通过第四条规则,死细胞是有机会变成活细胞的,即会对结果产生巨大的影响!

发现了这点之后,我开始意识到,这道题不像我原先现象的那么简单,以下这个动画图能够生动地说明这个问题。我们要关心的不只是这个小小的细胞区域,而是整个可能无限的区域。

接下来,正片开始!我的思路很简单,首先着眼于死细胞唯一的再生途径,即规则四,附近有恰好三个活细胞。把关注点放在这里之后,不难想到,这个区域不是无限大的了,而顶多只是比原先的区域大一圈而已,然后再根据每一代的存活情况,慢慢变大或者不变。思路理清楚了之后,实现起来就不难了,我把优化过的代码放在这里。虽然能够解决问题,但是感觉还是不够完美,看了好久别人的代码,感觉大体思想都差不多,只是把函数封装了一下,看起来舒服一点。如果大家有更好的想法,欢迎找我谈论!

function get_generation(array $cells, int $generations): array {
  $x = count($cells);
  $y = count($cells[0]);
  while($generations--) {
    //零数组,长度为
    $emptyX = array_fill(0,count($cells[0]),0);
    //如果第一行中活细胞数大于等于3,则有可能周围死细胞会再生,需要在其前方插入一行零数组
    if(array_sum($cells[0]) >= 3) array_unshift($cells,$emptyX);
    //如果最后一行中活细胞数大于等于3,则有可能周围死细胞会再生,需要在其后方插入一行零数组
    if(array_sum($cells[count($cells)-1]) >= 3) array_push($cells,$emptyX);
    //如果第一列中活细胞数大于等于3,则有可能周围死细胞会再生,需要在其前方插入一列零数组
    while($cells != [] && array_sum(array_column($cells,0)) >= 3) {
      foreach($cells as $key=>$item) {
        array_unshift($cells[$key],0);
      }
    }
    //如果最后一列中活细胞数大于等于3,则有可能周围死细胞会再生,需要在其后方插入一列零数组
    $i = count($cells[0])-1;
    while($cells != [] && array_sum(array_column($cells,$i)) >=3 ) {
      foreach($cells as $key=>$item) {
        array_push($cells[$key],0);
      }
      $i = count($cells[0])-1;
    }
    $x = count($cells);
    $y = count($cells[0]);
    $n = 0;
    $array = [];
    for($i=0;$i<$x;$i++) {
      for($j=0;$j<$y;$j++) {
        //每个细胞目前的存活情况
        $array['self'][$n] = $cells[$i][$j];
        for($k=($i-1>=0?$i-1:0);$k<=($i+1<$x-1?$i+1:$x-1);$k++) {
          for($l=($j-1>=0?$j-1:0);$l<=($j+1<$y-1?$j+1:$y-1);$l++) {
            //统计每个细胞周围的存活情况
            $array['around'][$n] += $cells[$k][$l];
          }
        }
        $n++;
      }
    }
    //通过规则,判断每个细胞下一代的存活情况
    for($i=0;$i<$x*$y;$i++) {
      $array['around'][$i] -= $array['self'][$i];
      if($array['around'][$i] < 2) {
        $array['self'][$i] = 0;
      } elseif ($array['around'][$i] > 3) {
        $array['self'][$i] = 0;
      } elseif ($array['around'][$i] == 3) {
        $array['self'][$i] = 1;
      }
    }
    $n = 0;
    //新的一代
    for($i=0;$i<$x;$i++) {
      for($j=0;$j<$y;$j++) {
        $cells[$i][$j] = $array['self'][$n];
        $n++;
      }
    }
  }
  //如果第一行为空行,则可以删除
  while($cells != [] && empty(array_sum($cells[0]))) {
    array_splice($cells, 0, 1);
  }
  //如果最后一行为空行,则可以删除
  while($cells != [] && empty(array_sum($cells[count($cells)-1]))) {
    array_splice($cells, count($cells)-1, 1);
  }
  //如果第一列为空列,则可以删除
  while($cells != [] && empty(array_sum(array_column($cells,0)))) {
    for($j=0;$j<count($cells);$j++) {
      array_splice($cells[$j], 0, 1);
    }
  }
  //如果最后一列为空列,则可以删除
  $i = count($cells[0])-1;
  while($cells != [] && empty(array_sum(array_column($cells,$i)))) {
    for($j=0;$j<count($cells);$j++) {
      array_splice($cells[$j], $i, 1);
    }
    $i = count($cells[0])-1;
  }
  //如果没有细胞存活,则返回二维的空数组
  $sum = 0;
  for($i=0;$i<$x;$i++) {
    for($j=0;$j<$y;$j++) {
      $sum += $cells[$i][$j];
    }
  }
  return $sum == 0 ? [[]] : $cells;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注