Codewars:一个鸡蛋引发的思考

在codewars上遇到这样一道题: Eulampy 有一筐鸡蛋, 有一天在一幢摩天大楼下, 他的朋友对他说, 如果你给我n个鸡蛋, 我保证可以告诉你, 在h层楼的范围内, 鸡蛋最多从第几次楼扔下来而不会被摔破. Eulampy说, "没问题, 但是我最多同意你扔m次, 看你扔的次数太多我会难过的.", 请设计一个函数, height(n, m), 求扔鸡蛋实验的总量程, 即 h. 需要说明的是, 我们假设每个鸡蛋的都是完全一样的, 当一个鸡蛋被扔下了而没破, 就可以再次使用. 原题地址:https://www.codewars.com/kata/faberge-easter-eggs-crush-test/train/python 重点来了, 这道题有三组测试, 分别是: 基础的(basic), 进阶的(advanced), 真格的(serious). test.it('basic tests') test.assert_equals(height(…

一个奇葩的Chrome插件:Flappy Octocat

前段时间看朋友写了个 Chrome 插件觉得特别酷,可以在 github 的 contributions board 上玩康威生命游戏。 大概是像这样的: 受朋友的启发,我也写了一个 Chrome 小插件,可以让我在 contributions board 上玩 flappy bird 一样的游戏,画面大概是这样的: 不过,到底是什么样的神经病才会在 github 的 contributions board 上玩游戏呢 🌚 如果喜欢的话,可以从 https://github.com/chxj1992/flappy-octocat 获得这个插件及其源码 或者,直接从 Chrome 的 Web Store 安装这个游戏…

Codewars:从逆波兰表达式到Three-Pass编译器(2)

在这里我想说的第二道题,我把它理解成一次对逆波兰表达式的运用和延伸。关于逆波兰表达式的相关知识,可以在前一篇博客中读到 : Codewars:从逆波兰表达式到Three-Pass编译器(1) 和前一题相比,这道题的题面就要复杂多了。 我们有一种如下的语法规则的编程语言: [ a b ] a*a + b*b 这里我们定义了一个函数,这个函数有两个参数(a 和 b),函数功能是计算 a 和 b 的平方和。 现在,请为该语言实现一个简单的语法编译器。编译过程可以拆分为三个步骤: 1.将函数解析为一个抽象语法树(AST ) AST有如下规则: { 'op': '+', 'a': a, 'b': b } // add subtree a to subtree b { 'op': '-', 'a': a,…

Codewars:从逆波兰表达式到Three-Pass编译器(1)

最近沉迷于在 codewars 上做题无法自拔,其中有两道题我感觉挺有意思,觉得值得记下来,故成此文。 第一道题的题面非常简单,实现一个包含 + - * / 四则运算的计算器,输入样例:1 + 2 * 3, 期望结果 7。 原题链接见下: https://www.codewars.com/kata/calculator 从小学数学的角度来思考这道题,答案是显而易见的:乘除法的优先级要高于加减法,所以我们可以把表达式中所有乘除法先提出来计算出结果并放回原来的位置,再依次计算加减法得到整个表达式的结果。依照这样的思路,我们可以有如下的代码实现(In Python): from operator import add, sub, mul, div FIRST = {'*' : mul, '/': div} SECOND = {'+': add,…

利用图像边缘检测算子破解滑动拼图验证码

在之前用神经网络的方法搞了一把前公司的验证码以后,前同事们也快速作出响应,迅速把普通验证码换成了滑动拼图验证码,然后还说: 我觉得我可能是和验证码杠上了。 滑动验证码拼图的定位问题只是破解过程中的一个环节,我的方案主要采用 opencv 提供的函数对图片进行处理后来实现定位,在这里只提供一个思路,抛砖引玉了。 最终的实现效果可以通过 这个Demo 简单感受一下。相比之前用神经网络训练来破解普通验证码,这次的实现方式可能更具通用性,因为不用再依赖训练数据。 关于滑动验证码 演示项目所用到的滑动验证码实现相对简单,整个交互过程主要包含以下步骤: 服务端将背景图片和拼图图片合并为一张图片,并记录下拼图在背景图中的x坐标,然后将拼好图片和单独的拼图图片返回给客户端 客户端实现单片拼图在背景图上拖动的动画效果,并在用户完成拖动动作后,将当前拼图所处位置的坐标数据加密后返回给服务端 服务端解密数据并比较客户端返回的x坐标数据并与之前保存的x坐标数据进行比较,允许小范围内的误差 实现原理 基于以上的验证码实现,本例子通过以下方式实现对验证码拼图在背景图中的定位(其他步骤较为简单,不做考虑): 利用opencv库中提供的边界查找函数(cv2.findContours)提取单片拼图边缘轨迹并构造成一个二维矩阵(算子),具体代码如下: shape = cv2.resize(cv2.imread('shape.png'), (shape_height, shape_width)…

用卷积神经网络识别普通验证码

最近在学习神经网络的相关知识,也谈谈自己目前对神经网络一些浅薄的认识。 实际生产生活中的很多问题都可以理解成如何建立从一个集合到另一个集合的映射关系的问题,也可以说成是,如何设计一个函数的问题。这个函数有一组权重参数,输入集合的数据经过权重参数的处理对应到不同的输出数据。而所谓的神经网络正是由一层一层这样的函数堆叠组成,所以神经网络也叫深度学习。深度学习中最重要一个环节就是通过大量的数据对各层函数的权重参数进行训练,所谓学习(训练)便是通过不断地修正,使权重参数慢慢趋于准确,尽量让所有训练数据的输入在经过权重参数的处理后都能映射到正确的输出,这样的学习(训练)过程往往需要将训练数据一轮一轮的输入我们设计的神经网络模型中,经过长时间反复拟合来实现。 神经网络中的 误差函数 即是一个能表示当前输入数据经过权重参数处理后得到的实际输出和预期输出之间误差大小的函数。我们的目的则可以表述为求取误差函数值最小时对应权重参数的值,当把误差函数用权重参数来表达时,这个问题又可以理解成求误差函数的极小值(一定区间内的最小值),即误差函数对于权重参数导数为0的那一个点。在计算机的数学优化方法中,一般采用梯度下降法来解决这个问题,而所谓梯度下降法,即从误差函数上的一点开始,沿着梯度(导数)下降的方向一点一点地逼近,最终得到一个近似的误差极小的点。梯度下降法是神经网络理论中最基础的知识。而其他如随机梯度下降、批量梯度下降和小批量梯度下降都是对上面提到的梯度下降法的优化,而其本质思想是相同的。而其他的一些相关知识也大都围绕着这一基本思想展开。如学习速度(learning rate)是对在梯度下降的过程中每一步移动大小的表述,而各种各样的优化器则是针对如何让程序自动地选取最合适的学习速率所设计的算法。 常见的神经网络模型大概分为:全连接神经网络、卷积神经网络、循环神经网络等几个大类。本文所提及的卷积神经网络借鉴了数字图像处理中使用算子对图片特征进行提取的方法,…