逆FizzBuzz问题求最短序列

问题描述

FizzBuzz问题：一个大于0的自然数能整除3，将输出“Fizz”；能整除5，将输出“Buzz”；能整除3和5，将输出“FizzBuzz”；否则输出自己。

逆FizzBuzz问题最短序列：已知一个FizzBuzz问题的非数字输出序列，求能获得该序列的最短连续数字序列。如“Fizz”的最短序列是“3”，“Fizz Buzz”的最短序列是“9 10”，而不是“3 4 5”。

 

编程实现

  1 <?php
  2 
  3 /**
  4  * @author cenze
  5  *
  6  * 反FizzBuzz问题求最短序列
  7  * 
  8  * $inverseFizzBuzz = new InverseFizzBuzz([
  9  *   'fizz',
 10  *   'fizz',
 11  *   'buzz',
 12  * ]);
 13  * $inverseFizzBuzz->sequence():
 14  * Array ( [0] => 6 [1] => 7 [2] => 8 [3] => 9 [4] => 10 )
 15  */
 16 class InverseFizzBuzz
 17 {
 18     // FizzBuzz问题赋值
 19     const FizzBuzz = [
 20         'fizz' => 3,
 21         'buzz' => 5,
 22         'fizzbuzz' => 15
 23     ];
 24     
 25     // 预定义问题区间
 26     private $range = [
 27         1,
 28         100
 29     ];
 30     
 31     // 待求序列
 32     private $list = [];
 33     
 34     // 待求序列包含项数统计
 35     private $listItemsCount = 0;
 36 
 37     public function __construct($list = [], $range = [])
 38     {
 39         $this->init($list, $range);
 40     }
 41 
 42     /**
 43      * 待求序列、区间初始化
 44      *
 45      * @param array $list
 46      *            待求序列
 47      * @param array $range
 48      *            问题区间
 49      * @param bool $check
 50      *            是否检查属性已完成初始化
 51      *            
 52      * @return void
 53      */
 54     private function init($list = [], $range = [], $check = false)
 55     {
 56         if ($list) {
 57             $this->list = $this->inverseList($list);
 58             $this->listItemsCount = count($this->list);
 59             if (! $this->listItemsCount) {
 60                 exit('Invalid list.');
 61             }
 62         }
 63         
 64         if ($range) {
 65             $this->range = $range;
 66         }
 67         
 68         if ($check) {
 69             if (! $this->list) {
 70                 exit('Property list uninitialized.');
 71             }
 72         }
 73     }
 74 
 75     /**
 76      * 将待求解序列反转
 77      *
 78      * @param array $list
 79      *            待求解序列
 80      *            
 81      * @return mixed
 82      */
 83     private function inverseList($list)
 84     {
 85         $inverseList = [];
 86         foreach ($list as $item) {
 87             if (! array_key_exists($item, self::FizzBuzz)) {
 88                 return null;
 89             }
 90             $inverseList[] = self::FizzBuzz[
 91                 $item
 92             ];
 93         }
 94         
 95         return $inverseList;
 96     }
 97 
 98     /**
 99      * 搜索最短序列是否存在
100      *
101      * @param array $list
102      *            待求序列
103      * @param array $range
104      *            问题区间
105      *            
106      *            
107      * @return mixed
108      */
109     public function sequence($list = [], $range = [])
110     {
111         $this->init($list, $range, true);
112         
113         $sequences = $this->findSequences();
114         if (! $sequences) {
115             return 'Found no sequences.';
116         }
117         
118         $sequence = $this->shortestSequence($sequences);
119         // 将最短序列序列化后返回
120         return range($sequence[0], $sequence[$this->listItemsCount - 1]);
121     }
122 
123     /**
124      * 搜索最短序列(未序列化)
125      *
126      * @param array $sequences
127      *            序列集合，包含最短序列
128      *            
129      * @return array
130      */
131     private function shortestSequence($sequences)
132     {
133         // 默认第一条为最短
134         $shortestSequence = $sequences[0];
135         // 把每一个序列看做一条路径，都有对应的长度。记录最短的序列长度
136         $shortestSequenceLength = $sequences[0][$this->listItemsCount - 1] - $sequences[0][0];
137         // 为array_reduce()定义一个callback，用来搜索最短序列
138         $findShortestSequence = function ($shortestSequence, $currentSequence) use(&$shortestSequenceLength) {
139             $currentSequenceLength = $currentSequence[$this->listItemsCount - 1] - $currentSequence[0];
140             if ($currentSequenceLength < $shortestSequenceLength) {
141                 $shortestSequenceLength = $currentSequenceLength;
142                 return $currentSequence;
143             } else {
144                 return $shortestSequence;
145             }
146         };
147         
148         return array_reduce($sequences, $findShortestSequence, $shortestSequence);
149     }
150 
151     /**
152      * 从指定位置开始搜索指定项目的序列
153      *
154      * @param int $item
155      *            指定项目
156      * @param int $start
157      *            起始搜索位置
158      *            
159      * @return int
160      */
161     private function findItemSequenceFromPosition($item, $start)
162     {
163         if ($start % $item == 0) {
164             return $start;
165         }
166         
167         return $start + ($item - $start % $item);
168     }
169 
170     /**
171      * 从指定位置开始搜索首个序列
172      *
173      * @param int $start
174      *            起始搜索位置
175      *            
176      * @return mixed
177      */
178     private function findSequenceFromPosition($start)
179     {
180         $listSequence = [];
181         for ($i = 0; $i < $this->listItemsCount; $i ++) {
182             $itemSequence = $this->findItemSequenceFromPosition($this->list[$i], $start);
183             if ($itemSequence > $this->range[1]) {
184                 return null;
185             } else {
186                 $listSequence[] = $itemSequence;
187                 $start = $itemSequence + 1;
188             }
189         }
190         
191         return $listSequence;
192     }
193 
194     /**
195      * 找到多个序列，其中包括最短序列
196      *
197      * @return void
198      */
199     private function findSequences()
200     {
201         $sequences = [];
202         // 以第一个项为初始搜索位置在预定区间中搜索，且以第一个项为递增步长向后逐步搜索
203         for ($start = $this->list[0]; $start <= $this->range[1]; $start += $this->list[0]) {
204             // 只需找到指定位置开始的第一个序列即可
205             if ($sequence = $this->findSequenceFromPosition($start)) {
206                 $sequences[] = $sequence;
207             }
208         }
209         
210         return $sequences;
211     }
212 }