CHECKIO

Walkthrough of Fibonacci Golf

Jan 13, 2018
CHECKIO, PYTHON

题目需求 题目的原意可以总结为:以尽量简洁的方式,完成各种类Fibonacci计算。 提到的类型有: fibonacci: f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2) tribonacci: f(0)=0, f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2)+f(n-3) lucas: f(0)=2, f(1)=1, f(n)=f(n-1)+f(n-2) jacobsthal: f(0)=0, f(1)=1, f(n)=f(n-1)+2*f(n-2) pell: f(0)=0, f(1)=1, f(n)=2*f(n-1)+f(n-2) perrin: f(0)=3, f(1)=0, f(2)=2, f(n)=f(n-2)+f(n-3) padovan: f(0)=0, f(1)=1, f(2)=1, f(n)=f(n-2)+f(n-3) 题目的原始代码非常简单: def fibgolf(type, num): return 0 if __name__ == '__main__': assert fibgolf('fibonacci', 10) == 55 assert fibgolf('tribonacci', 10) == 149 assert fibgolf('lucas', 10) == 123 assert fibgolf('jacobsthal', 10) == 341 assert fibgolf('pell', 10) == 2378 assert fibgolf('perrin', 10) == 17 assert fibgolf('padovan', 10) == 9 思路 其实从题目给出的例子来看,各种数列在计算方式上都是高度类似的。我们只需要将计算方式和初始数值确定,就能确定各种f(n)的值。 ...

Walkthrough of Probably Dice

Jan 13, 2018
CHECKIO, PYTHON

题目需求 题目的原意可以总结为:求N个M面骰子(骰子点数为1-M)掷出X点数的概率。 其中,N,M,X依次为我们需要编写的函数的三个参数。返回值是0~1的一个数字,需要4舍5入保留四位小数。 这是题目的原始代码: def probability(dice_number, sides, target): return 0.0 if __name__ == '__main__': #These are only used for self-checking and are not necessary for auto-testing def almost_equal(checked, correct, significant_digits=4): precision = 0.1 ** significant_digits return correct - precision < checked < correct + precision assert(almost_equal(probability(2, 6, 3), 0.0556)), "Basic example" assert(almost_equal(probability(2, 6, 4), 0.0833)), "More points" assert(almost_equal(probability(2, 6, 7), 0.1667)), "Maximum for two 6-sided dice" assert(almost_equal(probability(2, 3, 5), 0. ...

Walkthrough of Text Holes Golf

Aug 30, 2014
CHECKIO, PYTHON

冲分的时候又到了!! 题目要求 题目要求一如既往的简单明了: 统计一段文字中,有多少空格满足周围都不是空格字符的数量 而原始代码嘛…… def golf(text): return 0 思路 我还是先用普通的方式来实现,然后再简化程序。 第一行、最后一行、第一列和最后一列不可能有满足条件的空格,所以在代码里面就直接忽略了。 def golf(t): c = 0 for r in range(1, len(t) - 1): for i in range(1, len(t[r]) - 1): try: if (t[r][i] == ' 'and t[r][i - 1] != ' 'and t[r][i + 1] != ' 'and t[r - 1][i] != ' 'and t[r + 1][i] != ' 'and t[r + 1][i+1] != ' 'and t[r-1][i-1] != ' 'and t[r + 1][i-1] ! ...

CheckIO - Snake

Sep 12, 2013
CHECKIO, PYTHON, Programming

http://www.checkio.org/mission/task/info/snake/python-27/ 呀〜贪吃蛇啊…… 和其他的task不同的是,这个是一次multicall。不过我其实完全可以不考虑这点,每次给出当前map,然后程序给出走法。而寻路的方式,我还是选用A*。虽然每次都会完整的计算一次完整路径,不过我到认为这是免得撞车的好方法。 首先还是需要实现puzzle,不过还是很简单啦。 class AnagramsPuzzle(AStar): """ description """ def __init__(self, goal): super(AnagramsPuzzle, self).__init__(goal) def heuristic(self, node): return abs(self.goal[0]-node.status[0]) + abs(self.goal[1]-node.status[1]) def get_result(self, node): #only care about the first step return node.comment 而且我们还只关心第一步,后面的都不用管,交给下个call来就行。现在到了node了。 class AnagramsPuzzleNode(AStarNode): """ description """ def __init__(self, status, G, parent): super(AnagramsPuzzleNode, self).__init__(status, G, parent) def possible_next_nodes(self): result = [] # get current position position_zero = divmod([j for i in self.status for j in i].index('0'), len(self.status[0])) position_one = divmod([j for i in self. ...

CheckIO - CheckSum

Sep 8, 2013
CHECKIO, PYTHON

题目的描述超级麻烦,不过逻辑很简单,没有什么特别注意的地方,全是非常基础的知识。 def checkio(data): sum_of_digits = 0 data = [i for i in data if ('0'<=i and i<='9') or ('A'<=i and i<='Z')] data.reverse() # even for i in xrange(0, len(data), 2): doubling = (ord(data[i]) - 48) * 2 if len(str(doubling)) > 1: map_point = reduce(lambda x, y: int(x)+int(y), [j for j in str(doubling)]) else: map_point = doubling sum_of_digits += map_point # odd for i in xrange(1, len(data), 2): sum_of_digits += ord(data[i]) - 48 if sum_of_digits == 10: return ['0', sum_of_digits] return [str(10-(sum_of_digits%10)), sum_of_digits] #These "asserts" using only for self-checking and not necessary for auto-testing if __name__ == '__main__': assert (checkio(u"799 273 9871") == ["3", 67]), "First Test" assert (checkio(u"139-MT") == ["8", 52]), "Second Test" assert (checkio(u"123") == ["0", 10]), "Test for zero" assert (checkio(u"999_999") == ["6", 54]), "Third Test" assert (checkio(u"+61 820 9231 55") == ["3", 37]), "Fourth Test" assert (checkio(u"VQ/WEWF/NY/8U") == ["9", 201]), "Fifth Test" print("OK, done! ...

CheckIO - Anagrams By Stacks

CHECKIO, PYTHON

http://www.checkio.org/mission/task/info/anagrams-by-stacks/python-27/这个任务是incinerator的最后一个任务(截至Sep. 13. 2013),题目的要求从配图来看一目了然:总结下来有这么几点:1,2两个stack是单词长度;0固定长度为1只能移动最后一个字母(这是废话,要不怎么用stack)我们当然可以设置三个stack,然后递归解决。不过我想了想,既然要求的是——最小步数,而非“成功的达成目标”。那么如果自己写递归还要比较各个方法的优劣的问题,太麻烦了〜如果把最小步数理解成最短路径,这不就变成寻路了吗!而且寻路算法,只要拿出A*就好了啊!至于A*,我以前题目里面用过的线程的代码可以拿出来:有了这个,我们只需要实现puzzle和node就可以了。而puzzle相当简单:class AnagramsPuzzle(AStar): """ description """ def __init__(self, goal): super(AnagramsPuzzle, self).__init__(goal) def Heuristic(self, Node): return 0 def getResult(self, Node): result = [] while Node.Parent: result.append(Node.Comment) Node = Node.Parent result.reverse() return ','.join(result)这里需要说到两点:Heuristic在不明确会不会对分析造成影响的前提下,建议直接返回0即可Node.Comment是每次移动对应的命令,在Node里面会看到。下面就是要实现node了。node最核心的地方就是每个节点可能有那些下一步,虽然重要,但是实现难度并不大。代码如下:class AnagramsPuzzleNode(AStarNode): """ description """ def __init__(self, Status, G, Parent): super(AnagramsPuzzleNode, self).__init__(Status, G, Parent) def PossibleNextNodes(self): Result = [] one_stack = self.Status[0] zero_stack = self.Status[1] two_stack = self.Status[2] if last_char(one_stack)[0] != '': # 10 if last_char(zero_stack)[1] != 0: new_one_stack = deepcopy(one_stack) new_zero_stack = deepcopy(zero_stack) new_zero_stack[0] = last_char(new_one_stack)[0] new_one_stack[last_char(new_one_stack)[1]] = '' temp = [new_one_stack, new_zero_stack, two_stack] new_node = AnagramsPuzzleNode(temp, self. ...

CheckIO - Area of a convex polygon

CHECKIO, PYTHON

http://www.checkio.org/mission/task/info/area-of-a-convex-polygon/python-27/一句话——求给出凸多边形的面积。请注意:1. 凸多边形,别去想什么凹多边形的例子了; 2. 没有说是正N变形,那个公式在这里是用不了的。多边形的面积,能想到的就只有三角形了——已知三角形的三条边长,可以得出三角形面积。那么我们可以考虑这样对任务进行分解:将多边形分成N个三角形;对N个三角形进行累加求和。我相信第二点是很容易的,参照百科的文档谁都能写。那么我们需要想想第一点怎么实现。我们选定一点作为基点,由于是凸多边形,那么其他所有的点都在这个点180度的范围内。为了方便计算,我们就用Y值最小的一个点就行,这样所有的点都在他上方(或者水平方向有一个点,且最多只能有一个!)。然后反余弦函数可以求出以基点为中心,与X轴正方向的夹角。按照夹角大小排序,之后每次顺序取出两个点和基点就可以组成N-2个没有重复的三角形了。代码如下:到此我相信已经可以返回结果了,但是现在才是纯粹数学之后的编程技巧。尝试测试一下assert checkio([[1, 1], [9, 9], [9, 1]]) == 32, "The half of the square"结果很意外吧,居然通不过!是的,就是通不过。那我们print出来看看,结果是32.0。呀〜原来是类型不对,现不管后面的测试,用int转换类型试试——31。你敢信!!!int(32.0) == 31别急,我们用as_integer_ratio这个浮点数内置方法来看看结果,结果是:(4503599627370495, 140737488355328)多么诡异的数值!别急,试试直接使用32.0来看看结果In [72]: a = 32.0In [73]: a.as_integer_ratio()Out[73]: (32, 1)In [74]: a = 35.5In [75]: a.as_integer_ratio()Out[75]: (71, 2)原来如此,我们print看到的32.0,是上面两个数相除得到的结果。我们计算的结果,虽然看起来是32.0,但是实际却不是!那么简单了 ,既然要求到0.1,我们先用进行四舍五入到小数点后面第一位。然后as_integer_ratio函数还解决了我们另外一个问题——何时返回整数,何时返回小数。把这里补完,就是上面贴的完整代码了。

CheckIO - Three Points Circle

CHECKIO, PYTHON

http://www.checkio.org/mission/task/info/three-points-circle/python-27/问题简化下来就是:给出三个点,求这三个点所在圆的方程说实话,这个问题看起来很简单的,全是初中数学知识。,求园的方程无非就是两点:圆心座标半径求圆心座标是很简单的事情:用这三个点做两条线段,做这两条线的中垂线,两条中垂线的交点就是圆心。在知道圆心座标后,半径自然就非常简单了。不过在过程中还是有些需要注意的地方:1. 两条线段的表示方式无非就是两种方式y=ax+c或者ax+by+c=0两种,但是考虑到线段所在的直线可能平行于X轴或者Y轴,第一种方式相对来说就有一些局限了——因为无法表示平行于Y轴的线段。当然除此之外,都是可以的。所以我除此之外都将b固定为-1,平行的时候设置为0。在确定了表示方法后,就是需要求出a和c两个常量,对应的方法很简单——先求斜率a,在求c2. 有了两条线段所在直线的方程后,求中垂线方程线段的中间点很简单,不需要任何技巧。而且对于已知斜率为k的直线,垂线斜率为-1/k。当然还是需要把平行于X轴和Y轴这两种情况单独拿出来,-1/k是不行的。3. 两条中垂线的交点与半径对于已知的两条直线,交点座标可以用百科上的方法来得到。在有了圆心座标后,半径也就很方便的可以得到了。4. 如何表示成要求的形式以前我一直都使用这样的方式格式化字符串:'x-%d' % 4.0这样的方式当浮点数后面全是0的时候,无法表示成整形的样子。也就是说,4.1要不只能4.1,要不只能4;4.0要不只能4.0,要不只能4而题目所需要的表示方式是,当小数点后面全是0的时候,表示成整数的形式,其他时候表示成两位小数。难道我还需要手动判断吗?恕我孤陋寡闻,在google以后才知道还有另外的方式表示'x-{:g}'.format(4.0)这种方式从文档中看更加灵活,而且有一个超方便的g参数,可以实现我们的要求。实在爽翻了!下面是代码