XYZ - XYZ
type: channel
link: https://xyzshare.xyz/index.php/author/1/
description: XYZ
items: 戏说清朝十二帝
items: 网络协议的趣谈
items: 怀旧老题：滑动窗口中位数
items: 尝一尝深度学习的“樱桃”强化学习
items: 狐狸、兔子和蘑菇
items: 图像的手绘效果
items: 俄罗斯方块：“富贵险中求”算法
items: 极客挑战赛-笔记二
items: 极客挑战赛-笔记一
items: 小学二年级数学题，震惊了～

戏说清朝十二帝
type: item
date: 2024-09-14T07:26:00+00:00
description: 引言清朝，作为中国历史上最后一个封建王朝，从1616年努尔哈赤建立后金政权开始，到1912年末代皇帝宣统帝退位，历经近300年的风雨。从一统天下的辉煌到内忧外患的衰落，清朝的兴衰历程不仅是中国历史的重要篇章，也是世界历史中一段波澜壮阔的经历。清朝的建立与发展，无疑是中国封建王朝历史中的一个重要转折点。努尔哈赤和他之后的皇帝们通过军事征服、政治谋略和文化融合，成功地将一个起初弱小的女真部落发展为一个横跨东北、华北、华中以及西北广大地区的庞大帝国。清朝在康熙、雍正、乾隆三位帝王的治理下，达到顶峰，创造了中国历史上著名的“康乾盛世”。然而，随着统治时间的推移，清朝也逐渐暴露出其自身的弱点和问题。自道光帝时期开始，内忧外患接踵而至。鸦片战争、太平天国运动、以及列强的干涉，使得清朝政府疲于应对，国家财政状况恶化，社会矛盾也日益尖锐。清末的改革尝试，如光绪帝的“百日维新”，也因保守势力的强大阻力而未能成功。清朝的十二位皇帝，每一位都在这个历史的舞台上留下了自己的印迹。他们或开创基业，或励精图治，或力挽狂澜，或无奈收场。通过他们的治国策略、政策措施以及个人性格，我们可以更全面地理解清朝这个封建王朝的全貌，以及其从辉煌走向衰落的必然性。本文将以清朝十二位皇帝为线索，深入探讨他们的生平及其治国理念，揭示他们在清朝历史中的重要性和影响力。希望通过这段历史的回顾，能够为读者提供一些有益的启示，帮助我们更好地理解历史，并从中汲取经验教训。一、清太祖努尔哈赤：开疆拓土的奠基者清朝的开创者努尔哈赤（1559-1626），其出身于建州女真部落，祖籍为今辽宁省新宾县赫图阿拉村。他的家族世代为建州女真部落的领袖，在一个相对分散、纷争不断的环境中成长。努尔哈赤幼时丧父，家庭背景并不显赫，但他凭借卓越的军事才能和政治智慧，逐步崛起为女真各部的领袖。努尔哈赤早年即展示出卓越的军事和政治才能。他通过征战、联姻和外交手段，逐步统一了建州女真。在1583年，努尔哈赤发动一系列攻势，击败了邻近的女真部落以及汉族军队，不断扩大其统治范围。努尔哈赤在1593年的九部联军之战中，以少胜多，彻底巩固了自己在女真各部中的霸主地位。努尔哈赤于1616年建立后金，定都赫图阿拉，正式称汗。这标志着女真部落从一个松散的联盟逐渐转变为一个中央集权的国家。为了进一步巩固其统治，努尔哈赤进行了多项改革。他实行八旗制度，将女真各部编入八个军事单位中，八旗不仅是军事组织，也是行政管理单位，有效提高了军事和行政效率。此外，他还注重发展农业和手工业，鼓励开垦荒地，增加粮食生产，以支持日益扩张的军事需求。在外交方面，努尔哈赤积极与明朝、大明周边的蒙古各部和朝鲜进行互动，既有征战，也有联姻和贸易。他的战略目标不仅限于统一女真各部，更是要与明朝争夺东北的统治权。1618年，努尔哈赤发布“七大恨”檄文，正式对明朝宣战，开启了长达数十年的明清战争。在努尔哈赤的领导下，后金军队屡次在战场上击败明军，逐步控制了辽东大片地区，为后来的入关奠定了基础。努尔哈赤的历史功绩不仅在于他建立了后金，统一了女真各部，更在于他为大清帝国的建立和发展奠定了坚实基础。他所创立的八旗制度、军事战略和行政管理模式，被其后继者保留并发扬光大，对清朝的巩固和扩张起到了至关重要的作用。努尔哈赤去世后，其子皇太极继位，继续推动后金向大清帝国的转变，最终完成了对中原的统一。努尔哈赤的一生充满了战斗与智慧，他那不屈不挠的精神和卓越的领导才能，使他成为一位名副其实的开疆拓土的奠基者，为清朝的辉煌奠定了基石。二、清太宗皇太极：缔造大清帝国的基础皇太极，原名爱新觉罗·皇太极，是清朝的第二位皇帝，也是清朝的奠基者之一。作为努尔哈赤的第八子，皇太极在其父去世后继位，继续推进满洲的统一和扩张。他在位期间，不仅从后金转变为大清，更是在经济、军事和文化方面进行了一系列的改革，为大清帝国的稳固和发展奠定了坚实的基础。从后金到大清在努尔哈赤去世后，皇太极继位于1626年。当时的后金虽然已经占据了辽东大部分地区，但内部仍需进一步整合，外部也面临明朝的强大压力。皇太极深知，要想建立一个持久稳固的政权，仅靠武力是不够的，还需要在制度和文化上进行深远的变革。1636年，皇太极正式改国号为“大清”，并自称“皇帝”，宣告了一个全新帝国的诞生。这一举措不仅增强了后金统治集团的凝聚力，还为未来的入关和统一全国做好了准备。经济改革为了增强国家的经济实力，皇太极推行了一系列重大改革。首先，他倡导农业生产，鼓励满洲人学习汉族的农业技术，提高粮食产量，以解决军粮供应问题。其次，他重视商业发展，尤其是东北地区的皮毛、药材等特产贸易，通过与蒙古、西伯利亚等地的互市，增加了清朝的经济收入。此外，皇太极还注重财政管理，通过严格的税收制度，确保了国家财政的稳定。军事改革在军事方面，皇太极延续了努尔哈赤的八旗…

网络协议的趣谈
type: item
date: 2024-09-13T11:21:00+00:00
description: 引子：网络协议究竟是什么？我们每天通过互联网进行各种活动：购物、聊天、刷视频，但你是否想过这些数据是如何传输的？在这一章，我们将揭开网络协议的神秘面纱，用通俗易懂的语言解释其基本概念和重要性。首先，想象一下你在现实生活中给朋友打电话。你需要知道对方的电话号码，拨号，然后等待接通。这个过程中有很多规则：比如你要先拿起电话，听到拨号音后再拨号码，接通后要等对方接听才能开始对话。这一系列规则确保了你能顺利找到对方并进行交流。网络协议就像这些规则一样，是计算机网络中进行信息交换的标准和规范。它们定义了数据如何在网络上进行发送、接收和解释。没有这些协议，就像没有电话通话的规则，我们的计算机将无法相互理解和通信。你可能会问，为什么需要这么多协议？想象一下我们日常的网络活动：发送邮件、浏览网页、观看视频、在线购物……每一种活动都涉及不同类型的数据和不同的传输要求。为了满足这些多样化的需求，互联网发展出了多种网络协议，每种协议负责特定类型的通信。例如，浏览网页时最常用的协议是HTTP（超文本传输协议），它定义了浏览器和服务器之间交换网页内容的方式。发送和接收电子邮件则主要依靠SMTP（简单邮件传输协议）和POP3/IMAP（邮局协议/互联网消息访问协议）。这些协议各有其特定的功能和工作原理，但共同确保了数据在互联网中可以可靠地传输和接收。网络协议的重要性不言而喻，它们是互联网的基石，使得不同设备、不同平台之间能够互相通信，构建出一个全球性的网络。在接下来的章节中，我们将深入探讨一些关键的网络协议，用生动的例子和通俗的语言帮你理解这些看似复杂但实际上非常有趣的技术细节。准备好了吗？让我们一起踏上这段网络协议的探索之旅吧！第一章：TCP/IP - 守护互联网的隐形英雄在互联网的世界里，TCP/IP协议就像是交通规则，指引着数据包的正确方向。你可以把它们想象成邮局的工作人员，负责把信件（数据包）从一个地点送到另一个地点。尽管这些信件要经过错综复杂的路线，但TCP/IP协议确保它们最终能够准确无误地到达目的地。TCP：可靠的传输保障首先，让我们认识一下TCP（Transmission Control Protocol），它是保证数据可靠传输的关键人物。可以把TCP想象成一辆运送贵重包裹的快递车，它不仅要保证包裹送达，还要确保包裹的完整性。三次握手：确保连接稳固TCP最著名的特性之一是“三次握手”机制。想象一下你在打电话，第一次拨号就是请求连接，对方接听并回应表示可以接通，这就是第一次握手；你确认收到回应，并再次确认连接状态，这就是第二次握手；对方收到你的确认并最终确认连接成功，这就是第三次握手。通过这三次握手，TCP确保双方都准备好进行数据传输。分段和重传：确保数据完整TCP还负责将数据分成小片发送，并在接收端重新组装这些数据片。如果有任何数据片在传输过程中丢失，TCP会自动重传。好比邮局会分批次运送你的包裹，并在丢失时重新发送。IP：寻找最佳路径有了TCP的可靠传输保障，还需要IP（Internet Protocol）来负责找路。IP就像是地图导航系统，它决定数据包通过哪条路线才能最快最安全地到达目的地。IP地址：互联网的门牌号每一台连接到互联网的设备都有一个独一无二的IP地址，就像每个房子都有一个门牌号。IP地址分为IPv4和IPv6两种，IPv4是由四组数字组成的，例如192.168.1.1，而IPv6则是为了应对互联网设备数量爆发式增长而设计的，它由八组16进制数字组成，如2001:0db8:85a3:0000:0000:8a2e:0370:7334。路由选择：智能导航IP协议不仅负责地址管理，还要选择最佳路径。每个数据包在传输过程中会经过多个路由器，这些路由器就像是高速公路上的每个路口，决定数据包的下一跳。如果一个路口堵车了，IP协议会智能地选择其他可行路径，确保数据包能顺利到达。小故事：快递小哥的冒险假设你要给远方的朋友寄一份生日礼物，过程中你会先把礼物交给快递公司（就像数据由应用层交给传输层），快递公司会把大件礼物拆成多个小包裹（数据分段），并用快递单号（序列号）标记。每个小包裹会通过不同的路线送往朋友家（路由选择），快递公司会确保每一个包裹都安全送达。如果某个包裹丢失，快递公司会重新发送（重传机制）。最终，朋友会收到所有包裹并把它们重新组装成一份完整的礼物（数据重组）。通过这个小故事，你应该对TCP/IP协议有了更直观的理解。它们是互联网数据传输的无名英雄，确保我们每天都能顺畅地上网、通讯和获取信息。在接下来的章节中，我们将继续探索更多有趣且重要的网络协议，敬请期待！第二章：HTTP和HTTPS - 网站通信的语言在互联网世界中，HTTP和HTTPS就像是网站之间的语言翻译官，帮助我们与远程服务器进行有效的沟通。那么，这两位“翻译官”…

怀旧老题：滑动窗口中位数
type: item
date: 2024-02-05T09:50:00+00:00
description: 前言个人认为，这是一道非常经典的 LeetCode Hard 题目，第一次碰到时，感觉觉得如此之精妙，想破脑袋也不会想到使用什么样合适的数据结构去解决这道问题。时隔快5年，在2024年农历新年最后一个工作日，重温下这道经典的题目。题目描述中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。例如：[2,3,4]，中位数是 3[2,3]，中位数是 (2 + 3) / 2 = 2.5给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。示例：给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。窗口位置 中位数--------------- -----[1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6 因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。提示：你可以假设 k 始终有效，即：k 始终小于等于输入的非空数组的元素个数。与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。原题快速门说句题外话，以现在卷的程度，是不是很多校招生必会解此题呢，想当年，这样的题目，是不太可能出现在现场笔试题目中的。^.^解题思路首先，拿到一道题目后，要分析输入规模，那其实老的题目这点是不太规范的，往往没有给你输入规模的描述，也就少了一些提示。我理解这道题目的输入规模应该如下：n = len(nums)1 <= k <= n <= 10^5那么如果是这样的数据规模，所有O(n^2)的算法可以直接劝退，不用费脑子和精力去想了。接下来，要仔细想下题目的考点是哪一个，或者哪几个组合。显然这道题目非常贴心的告诉你一个考点，滑动窗口，什么是滑动窗口，题目的示例解释的非常清楚了，k表示滑动窗口的长度，窗口往右滑动时，前面的数出窗口，后面的数进入窗口，就是这么个过程。其次，要求窗口内数据的中位数，如果每次暴力的重新计算，那么需要排序，取中间值，显然这个方案的复杂度，最坏情况下会变成O(n^2logn)，应该是过不了testcase，那么这里就要引入数据结构，以O(1)时间计算中位数，如果滑动窗口内的数字保存在一个有序数组，那么计算中位数的复杂度为O(1)就很轻松了，但是删除和添加一个元素到有序数组，操作是O(N)的，那什么数据结构删除和添加一个元素是O(logn)以下的复杂度呢？啊，想到了，类似堆或者红黑树的数据结构。那怎样使用有序的这些数据结构，实现滑动窗口中位数呢？最巧妙的设计在于，使用两个堆或者有序树的实例，一个维护前半段，一个维护后半段，那么中位数和前半段的最大值和后半段的最小值相关。如果是堆的话，前面半段使用最大堆，后面半段使用最小堆。如下图所示：这里还有一个细节点，如果k是偶数，那么前半段和后半段的数字数量相等，否则前半段多维护一个数，所以前半段维护数字的数量是 k+1 除以 2 下取整，后半段维护数字的数量是 k 除以 2 下取整。所以当 k 为奇数时，前半段堆最大值就是中位数，否则，需要将两个堆顶的数字取平均。代码实现通过上面的分析，思路有了，我实际实现时，使用了Python3，以及SortedList这个有序List（底层实现采用了二分查找和分块算法。在插入元素时，它会将列表分块，并在每个块内部使用二分查找来维护有序性。这样可以在保证列表有序的同时，提高插入和查找元素的效率），效果和堆是类似的，就是优化插入和删除元素的时间复杂度。代码如下：from sortedcontainers import SortedList class Solution: def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]: n = len(nums) l = (k+1) // 2 r = k // 2 L = SortedList(nums[:k]) R = SortedList() def L2R(): x = L.pop() R.add(x) def R2L(): x = R.pop(0) L.add(x) while len(L) > l: L2R() ans = [] if l > r: ans.append(L[-1]) else: ans.append((L[-1] + R[0]) / 2) for i in ran…

尝一尝深度学习的“樱桃”强化学习
type: item
date: 2024-01-20T06:41:00+00:00
description: 引言强化学习是蛋糕顶上缀着的一颗樱桃，这不是我说的，而是深度学习领域Yann LeCun教授在CoRL 2017大会上做的演讲时提及的。他著名的“蛋糕”理论。“真正的”强化学习好比蛋糕上的樱桃，监督学习好比蛋糕上的糖衣，而蛋糕本身是非监督学习（预测学习）。这里LeCun也表示，这一比喻对做强化学习的兄弟可能不太友好。认识下“樱桃”什么是强化学习呢？举个通俗的例子，强化学习就好比一个女猎手（为啥是女猎手，因为我下面用了阿塔兰忒的图像，哈哈）进入了一个迷雾森林，里面充满了各种挑战和奖励。她得自己摸索，判断哪个方向更有“糖果”，哪个方向有“陷阱”。在这个过程中，她会慢慢学会，哦，原来这样做能得到糖果，那样做会掉进陷阱。不过，这个魔法森林可不是那么容易走的。有时候，她会走错路，掉进陷阱，或者绕着同一个地方转圈圈。这时候，就需要神出手啦，给她点提示，让她知道哪个方向可能更有糖果。这就是我们常说的“智能体（agent）”和“环境（evironment）”之间的互动。通过这样的摸索和学习，阿塔兰忒最终会走出迷雾森林，这就是强化学习的魅力所在啦！小姐姐好看吧，也是我用AIGC生成的，嘿嘿。其实上面简单通俗的语言，就已经把强化学习的原理展露出来了，强化学习（Reinforcement Learning，RL）是一种通过试错来学习的方法。在深度学习中，强化学习用于训练智能体（agent）在环境（evironment）中采取行动，以最大化累积奖励。与监督学习不同，强化学习没有明确的输入输出对，智能体需要通过与环境的交互来学习最佳策略。深度学习中的强化学习原理涉及到状态（state）、动作（action）、奖励（reward）等核心概念。状态是指环境的当前状态，动作是智能体可以执行的操作，奖励是智能体采取某个动作后获得的正面或负面反馈。智能体在环境中不断尝试不同的动作，根据奖励信号来调整策略，以期获得最大的累积奖励。深度强化学习在许多应用领域取得了显著的成果，例如自动驾驶、游戏AI、机器人控制等。在实际应用中，智能体需要与环境进行大量的交互来学习最佳策略，这通常需要大量的计算资源和时间。实践环节当然只知道上面的原理是不够的，实践出真知，这块怎么去实验呢？我想起了2017年，Deepmind公司发表在nature科学杂志上的AlphaGoZero论文，当时也是通过在围棋比赛上战胜人类冠军而出圈，零人类经验，其自我训练的时间仅为3天，自我对弈的棋局数量为490万盘。但它以100:0的战绩击败前辈。围棋显然我没法找到足够算力支持，但是找个简单的游戏，还是可行的，那么我想到了一个简单好玩的小游戏《flappy bird》，我首先做了一个通过玩家控制的版本：是不是很熟悉，画面不够精致，但是也够用了，小白球作为小鸟，需要往前飞，又不能碰到白色障碍物。我自己来控制，还是比较难掌控的，很快就会死了。那么怎么实现AI控制小鸟，就是我要完成的事情。首先上面说的环境（evironment）在这个游戏中就是这个游戏本身，智能体（agent）就是这个小鸟的大脑，控制小鸟的行动。关于环境（evironment），如何抽象状态（state）是关键，我想到有好几种方法：整个游戏画面作为state，画面的每个像素点就是state，智能体（agent）需要自己理解这个画面意味着什么，障碍物的距离，小鸟的位置等等；计算某一帧时环境变量，最近的障碍物顶部占据画面高度的比例，小鸟离最近障碍物的距离占画面宽度的比例，小鸟的垂直方向的位置，小鸟的速度等等；显然不管环境（evironment）如何抽象，智能体（agent）都应该可以学会如何应对某一个具体的state，我在这篇文章中，先尝试了2这个方法，定义了5个变量：environment[0] = closest.x / (WIN_WIDTH - bird.x) # 最近的障碍物的横坐标 = closest.x，小鸟的横坐标 = bird.x，屏幕的宽度 = WIN_WIDTH environment[1] = closest.top / WIN_HEIGHT # 最近的障碍物上半部分下沿 = closest.top，屏幕的高度 = WIN_HEIGHT environment[2] = closest.bottom / WIN_HEIGHT # 最近的障碍物下半部分上沿 = closest.bottom，屏幕的高度 = WIN_HEIGHT environment[3] = bird.y / WIN_HEIGHT # 小鸟的纵坐标 = bird.y，屏幕的高度 = WIN_HEIGHT environment[4] = bird.velocity / 10 # 小鸟的往前的速度 = bird.velocity 智能体（agent）简单定义为一…

狐狸、兔子和蘑菇
type: item
date: 2023-06-08T14:00:00+00:00
description: 导语好久没更新，从去年十月份来，工作突然很忙，平时剩下的时间用来学习、健身，给到总结写作，没剩下时间。加上人每隔一段时间，都会产生懈怠，就停更个人技术博客近半年。想想去年因为疫情在家办公期间，某种程度上来看，还是很幸福的，上班不用来回坐车，节省下来的时间，可以花在自己感兴趣的事情上，产生一些输出。OK，言归正传，今天闲来无事，我翻出了女儿去年玩过的小游戏，她妈妈给她买的这类智力小游戏有不少，很偶尔会瞧见她们娘俩一起玩，估计是不太感兴趣。今天这款游戏，我小时候没见过，是一个新的小游戏，我就起一个应景的名字，《兔兔大战小狐狸》，今年是兔年，兔子要逃脱小狐狸的围追堵截，逃到安全的小土坑里，躲起来。游戏介绍游戏棋盘是一个5*5的方盘，左上、右上、左下、右下以及正中间有5个小土坑，如果棋盘上所有的兔子，都在土坑待着，就完成了任务。具体规则，我不码字，看如下说明：如上面所说，游戏内置了60个关卡（因为随便摆放，是不一定能完成任务的），也有最少步骤的解答，我自己尝试玩了几个简单关卡（最少10步以内可以完成的），貌似还挺简单的。然后，我翻到了关卡的最后4个关卡，哇，一下子震惊了，好难，最后一关官方解答，需要87步完成任务。一些疑问小朋友如果自己完成前面简单、中等题目，已经很不容易了。至于困难、专家级别的题目，如果能完成，小脑瓜不是一般聪明，非常了不起。但我想了下，官方说最后一题87步是最少步骤，这个怎么证明官方没错呢？或者有更少步骤的解法？我心想，是不是写个算法求解，看看是否是对的。求解过程首先是需要有个建模过程，棋盘规格是5*5方盘，上面有25个位置，5个位置是土坑。可以放置的角色是小狐狸、兔兔和蘑菇。兔兔和蘑菇都只占用一个格子，狐狸占用两个格子，还有头和尾巴，但我仔细想了下，狐狸头和尾巴，其实在算法中不需要区分，只需要区分狐狸是竖着还是横着放置的，你可以理解为狐狸的头总是在左边或者上方，尾巴在右边或者下方。这样对算法实现更简单。比如60题，我会使用5个字符串表示5行，"...X." "FF.R." "..X.R" "X...." "...R." 字符X表示蘑菇，F表示小狐狸（头或者尾），R表示小兔兔，最后.表示空位。算法显然就是搜索算法，DFS还是BFS呢？我先用DFS实现了半天，会TLE，根本算不出最少步骤的解法。我后来想了下，最少步骤的解法确实不太适合DFS，因为DFS可能需要搜索完所有的解法空间（也可能我剪枝还不够），所以无法算出最少步骤。在DFS上，我其实花了不少时间优化，这个题目比刷题难，因为是自己出给自己的，也没有什么参考答案，都只能自己去想，如何建模和实现搜索算法，总之，自己试了半天，也不work。OK，那么我就来试下BFS搜索，大概的逻辑步骤如下：1. 建立一个队列，将游戏初始棋盘局面放到队列中； 2. 一一取出当前局面，评估可能变为的下一个局面； 3. 评估当前局面可能可以行动的小兔兔、小狐狸坐标； 4. 一一取出小兔兔、小狐狸，评估她们可能的移动到的位置； 5. 通过改变小兔兔、小狐狸位置，得到下一个局面； 6. 将2～5变化的到的局面插入队列（下一轮）； 7. 遍历完上一轮队列，步骤+1； 8. 把下一轮队列变为需要遍历的当前队列，重复2～7步骤； 代码实现：int smartGame(vector<string> board) { int n = board.size(); // 判断游戏是否结束 set<vector<int>> finish_pos = {{0, 0}, {0, n-1}, {n-1, 0}, {n-1, n-1}, {n/2, n/2}}; function<bool(vector<vector<int>>)> isFinished = [&](vector<vector<int>> ani_pos) -> bool { int n = ani_pos.size(); for (int i = 0; i < n; ++i) { if (ani_pos[i][2] != -1) continue; vector<int> pos = {ani_pos[i][0], ani_pos[i][1]}; if (finish_pos.find(pos) == finish_pos.end()) return false; } return true; }; // 分析棋盘局面，哪些可能移动的小兔兔、小狐狸所在位置 function<void(vector<string>, vector<vector<int>>&)> analyzeBoard = [&](vector<string> board, vector<vector<int>>& ani_pos) { for (int i = 0; i < n…

图像的手绘效果
type: item
date: 2023-02-03T03:10:00+00:00
description: 导语最近在学python数据处理的几个常用库，分别是numpy、matplotlib和pandas。这几个库应该是python数据处理的第三方神器库，学了一招图像手绘风格处理，非常有意思，记录下来。图像手绘风格手绘风格示例：第二幅就是有手绘的感觉，当然是基于第一章图片处理得到的。手绘风格可以总结为以下几点：黑白灰色边界线条较重相邻的像素，如果是相同或者相近色彩趋于白色略有光源效果具体如何通过程序实现呢？接下来就来逐一介绍下。梯度的重构利用像素之间的梯度值和虚拟深度值对图像进行重构，根据灰度变换来模拟人类视觉的明暗程度。代码如下：import numpy as np from PIL import Image a = np.asarray(Image.open('xxx.jpeg').convert('L')).astype('float') depth = 10. grad = np.gradient(a) grad_x, grad_y = grad grad_x = grad_x*depth/100. grad_y = grad_y*depth/100. 下面这行代码是通过pillow库读取原先图像，RGB值转为灰度值。a = np.asarray(Image.open('xxx.jpeg').convert('L')).astype('float') 这几行代码是计算灰度图像的像素间梯度，并且根据虚拟深度重构梯度值，depth初始化为10，depth取值0～100。depth = 10. grad = np.gradient(a) grad_x, grad_y = grad grad_x = grad_x*depth/100. grad_y = grad_y*depth/100. 光源效果根据灰度变化来模拟人类视觉的远近程度。设计一个位于图像斜上方的虚拟光源光源相对于图像的俯视角为Elevation，方位角为Azimuth建立光源对各个点梯度值的影响函数运算各个点的新像素值代码如下：vec_el = np.pi/2.2 # 光源的俯视角度，弧度值 vec_az = np.pi/4. # 光源的方位角度，弧度值 dx = np.cos(vec_el)*np.cos(vec_az) # 光源对x轴的影响 dy = np.cos(vec_el)*np.sin(vec_az) # 光源对y轴的影响 dz = np.sin(vec_el) # 光源对z轴的影响 A = np.sqrt(grad_x**2 + grad_y**2 + 1.) # 光源归一化 uni_x = grad_x/A uni_y = grad_y/A uni_z = 1./A b = 255*(dx*uni_x+dy*uni_y+dz*uni_z) 最后，对像素值进行裁剪至0～255，防止越界。b = b.clip(0, 255) im = Image.fromarray(b.astype('uint8')) im.save('xxxHD.jpeg') 最后程序虽然小，效果还是比较有意思的，我给女儿看了，她说你画画不是很丑的吗，为啥画的这么好？哈哈，我和她说，这是计算机处理的，不是我手画的，小小的年纪充满大大的问号。其实，这里最重要的是对图像灰度值计算梯度，这是Computer Vision里面传统图像处理的关键，CV相关的技术，由于可以可视化，实现之后，还是比较有意思的。

俄罗斯方块：“富贵险中求”算法
type: item
date: 2022-07-12T10:22:00+00:00
description: 导语作为80后，小时候一定玩过一款经典游戏，俄罗斯方块，英文名称Tetris。玩的画面在脑海中已是“上古”时期的事情，但也并不陌生，因为刷视频时，偶尔还能看到顶尖世界高手对决，他们玩的俄罗斯方块难度极大，游戏模式是对决，比谁的分数高，有些比赛到最后不仅自己消砖块得分，而且还可以通过得分不停给对手制造麻烦。看到鹅厂组织的一次极客挑战赛，主题就是俄罗斯方块游戏，当然游戏名称叫“鹅”罗斯方块，蛮鹅厂风格的，可可爱爱。我比较感兴趣，当时也报名参加了，最后是在2000+入场选手排名在9位，比赛结束后，我又花了点时间调试了自己的算法参数，最终比赛分数可以刷进TOP3。谨以此文，记录自己的所思所想。如何活着第一步想到的是，如何“活着”，就和当前经济形势下，各行各业都得考虑先“活着”，能不能得到高分其次，先得“不死”。我自己写了一个俄罗斯方块的游戏界面，和传统俄罗斯方块游戏一样，如何拼搭这些小图形，让高度不超过游戏规定的高度，满行就会消除，消除的行数有4种情况1行、2行、3行和4行。针对如何活着的俄罗斯方块AI算法比较多了，全网比较有名的是Pierre Dellacherie算法。我这里搜索到一篇El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm，大家可以参考下。首先，分析下俄罗斯方块中方块的种类，一共有7种图形：上面图中有7种不同的形状，我在代码里面的表示为坐标法，以(0, 0)为原点，标示周围那几个点对应图形需要占用。BrickShapes = [ # I [[[-2, 0], [-1, 0], [0, 0], [1, 0]], [[0, -1], [0, 0], [0, 1], [0, 2]]], # L [[[-2, 0], [-1, 0], [0, 0], [0, 1]], [[0, 0], [0, 1], [0, 2], [1, 0]], [[0, -1], [0, 0], [1, 0], [2, 0]], [[-1, 0], [0, -2], [0, -1], [0, 0]]], # J [[[-2, 0], [-1, 0], [0, -1], [0, 0]], [[-1, 0], [0, 0], [0, 1], [0, 2]], [[0, 0], [0, 1], [1, 0], [2, 0]], [[0, -2], [0, -1], [0, 0], [1, 0]]], # T [[[0, -1], [0, 0], [0, 1], [1, 0]], [[-1, 0], [0, -1], [0, 0], [1, 0]], [[-1, 0], [0, -1], [0, 0], [0, 1]], [[-1, 0], [0, 0], [0, 1], [1, 0]]], # O [[[-1, 0], [-1, 1], [0, 0], [0, 1]]], # S [[[-1, 0], [-1, 1], [0, -1], [0, 0]], [[-1, -1], [0, -1], [0, 0], [1, 0]]], # Z [[[-1, -1], [-1, 0], [0, 0], [0, 1]], [[-1, 0], [0, -1], [0, 0], [1, -1]]] ]比如竖棍“I”的图形，有两种rotation，所以有两组坐标的标示方式，其他图形类似，只不过rotation数量不同： # I, two rotations [[[-2, 0], [-1, 0], [0, 0], [1, 0]], [[0, -1], [0, 0], [0, 1], [0, 2]]], El-Tetris算法是传统AI人工智能，不要因为人工智能，就觉得很复杂，其实不论传统的AI算法还是目前深度学习的人工算法，一般都不会很复杂，深度学习AI算法不在此文讨论范围。基本上传统AI算法就是列举所有的可能性，通过计算预先建模的公式，评估最优秀的一个局面，做出选择，一直循环往复，直到游戏结束。我们看下El-Tetris算法的公式：f(x) = b0x0+b1x1+b2x2...bnxn其中x0,x1,x2...xn都是一些特征，b0,b1,b2...bn是一些系数（通过数学方法或者机器学习方法等手段推算出的经验值），对应特征和系数相乘相加之后，得到的就是当前局面+此选择的局面评估分数，是不是很简单，看上去是一个线性公式，但是效果出奇的好，原因还是在于每一个特征x的合理性以及系数b的合理性。系数b不需要我们实现，就是一组常数字，作者说是通过particle swarm optimization寻找到的，具体怎么找，我也不太清楚，先拿来用吧。另外要提一下，算法可以通常可以考虑当前图形+下一个图形，也可以只考…

极客挑战赛-笔记二
type: item
date: 2022-06-25T09:02:00+00:00
description: 导语上周记录了极客挑战赛的情况，其中一道非常有趣的题，本周继续，本周题目也是游戏，大概的游戏形式是横版闯关类的：还是借用网上游戏的图片说明下大概的意思，玩家一个英雄，进入一个场景（横版的），会有一个（每个场景仅一个）怪物与玩家英雄对抗，玩家有血条，有蓝量，6个技能（其中1个技能是升级其他5个技能），然后需要做的就是打到场景中的怪物，冲往下一个关卡。摸索有了之前游戏的经验之后，我知道了，上来就是一顿摸索，其实和上周说的游戏类似，客户端是个状态机，英雄有血量和蓝量，每次和怪物对抗之后，客户端会上传一堆指令到服务端，服务端重放这一堆指令，看最终的英雄状态和怪物状态是否合法，是不是英雄还活着，怪物已经死亡，然后就可以进行到下一关。一共是有9个怪物，一旦进入游戏，可以得到所有怪物的属性：bosses = [ { "Name": "小壶守卫", "Model": "Boss_ball", "Hp": 396, "Skill1_harm": 63, "Skill2_harm": 71, "Award_hp": 133, "Award_mp": 1695, "New_star": 0 }, { "Name": "苇名二心", "Model": "Boss_sword", "Hp": 532, "Skill1_harm": 59, "Skill2_harm": 89, "Award_hp": 157, "Award_mp": 1678, "New_star": 0 }, { "Name": "古达", "Model": "Boss_guda", "Hp": 643, "Skill1_harm": 57, "Skill2_harm": 97, "Award_hp": 142, "Award_mp": 1362, "New_star": 1 }, { "Name": "中壶守卫", "Model": "Boss_ball", "Hp": 668, "Skill1_harm": 59, "Skill2_harm": 67, "Award_hp": 178, "Award_mp": 1458, "New_star": 0 }, { "Name": "苇名三心", "Model": "Boss_sword", "Hp": 687, "Skill1_harm": 31, "Skill2_harm": 101, "Award_hp": 212, "Award_mp": 2659, "New_star": 0 }, { "Name": "黑古达", "Model": "Boss_guda", "Hp": 852, "Skill1_harm": 77, "Skill2_harm": 91, "Award_hp": 132, "Award_mp": 4157, "New_star": 2 }, { "Name": "大壶守卫", "Model": "Boss_ball", "Hp": 1502, "Skill1_harm": 71, "Skill2_harm": 105, "Award_hp": 154, "Award_mp": 3089, "New_star": 0 }, { "Name": "苇名零心", "Model": "Boss_sword", "Hp": 1611, "Skill1_harm": 97, "Skill2_harm": 127, "Award_hp": 189, "Award_mp": 6493, "New_star": 0 }, { "Name": "超黑古达", "Model": "Boss_guda", "Hp": 2988, "Skill1_harm": 101, "Skill2_harm": 153, "Award_hp": 0, "Award_mp": 0, "New_star": 3 } ]简单讲一下“Award_hp”和“Award_mp”这两个值，就是你击败怪物后，得到的奖励，可以分别增加对应的hp和mp，其他字段就是对应意思了。hero = { "Hp": 520, "Mp": 1806, "Power": { "Cost_mp": 233, "Attack_increase": [ { "skill_i": 1, "skill_j": 1, "skill_k": 1, "skill_l": 1, "skill_u": 1 }, { "skill_i": 6, "skill_j": 1, "skill_k": 2, "skill_l": 3, "skill_u": 5 }, { "skill_i": 6, "skill_j": 2, "skill_k": 2, "skill_l": 3, "skill_u": 4 },…

极客挑战赛-笔记一
type: item
date: 2022-06-18T09:41:00+00:00
description: 最近参加了一场极客挑战赛，挺有意思的，准备简单写下笔记。整个比赛是以游戏形式让大家参与的，一共四个，一开始的时候，我以为真的可以靠纯手打，去进行通关，后来发现，想得太天真了。四个游戏，都是需要通过一些编程去解决的，我过了大部分关卡，不过有些是靠的运气，看完官方的题解后，又有了新的认知。第一个游戏是类似回合制RPG游戏，类似：画面没这么好哈，版权原因不能用游戏原图，总之有一个行动条，到了时间就可以行动，英雄（就1个）和怪物（一场战斗也就1个）互相攻击，主角在一个地下城堡，总共24层，一层一层往下冲关，每层会有一个宝箱，每次进入下一层，地图都是随机选择的，地图模式有简单、困难和BOSS，每经过8层，地图中怪兽会升级。英雄是有技能池的，选择什么技能攻击怪兽，是可以进行策略选择的。英雄的数据：hero = { "Attack": 30, "Hp": 200, "Mp": 200, "Skills": { "skill_0": { "Cost_mp": 0, "Power": 1 }, "skill_1": { "Cost_mp": 10, "Power": 1.5 }, "skill_2": { "Cost_mp": 20, "Power": 2 }, "skill_3": { "Cost_mp": 30, "Power": 2.5 } }, "Speed": 30 }典型的怪物数据："Monsters":[ { "Attack":30, "Hp":40, "Speed":25 }, { "Attack":20, "Hp":50, "Speed":20 } ]上面的Monsters数据是简单地图的，字段都还比较好理解哈，不多做解释了。游戏还有一个设定，如果是非8、16、24层，每层都有一个宝箱，这个宝箱是随机开出来奖励或者惩罚，一共有4种情况：empty_box，空箱子；add_hp_mp，加血又加魔法值，Hp+10且Mp+50；del_hp，扣10血；升级属性，可以选择Attack+10，Speed+1，Hp+100，Mp+200；是不是感觉这些写出来变量都有点多了，而且都是靠自己抓包，分析出来的，其实玩的时候，真的需要一点点琢磨。然后我通过手打1～8层，发现了一些规律：如果英雄和怪兽Speed一样，英雄是占先的，也就是速度这块，玩家是占点便宜的；通过抓包发现，整个游戏和后端交互的协议就三条吧，new_level（重开游戏），next_layer（进入下一层），和open_box（开宝箱）；new_level请求和回包：{token: "YOUR_TOKEN"} {"code":0,"data":{"hero":{"Attack":30,"Hp":200,"Mp":200,"Skills":{"skill_0":{"Cost_mp":0,"Power":1},"skill_1":{"Cost_mp":10,"Power":1.5},"skill_2":{"Cost_mp":20,"Power":2},"skill_3":{"Cost_mp":30,"Power":2.5}},"Speed":30},"star_num":3},"message":""} open_box请求和回包：{"Layer_idx":1,"token":"YOUR_TOKEN"} {"code":0,"data":{"box":{"BoxType":"add_hp_mp","Value":[30,50]}},"message":""} next_layer请求和回包：{"Layer_idx":1,"Choice":"left","Layer_ops":[["start_battle",0],["battle_op",170,200,[["Hero","skill_0"],["Monster","skill_0"],["Hero","skill_0"]]],["start_battle",1],["battle_op",150,190,[["Hero","skill_1"],["Monster","skill_0"],["Hero","skill_0"]]],["open_box"]],"token":"06xyzzou0074CFBD948B14E238FB24BC"} {"code":0,"data":{"layer":{"Layer_idx":2,"Map_mode":"boss_map","Monsters":[{"Attack":30,"Hp":100,"Speed":40}]}},"message":""} 在客户端清理了一层的怪物后，可以选择去下一层的两扇门（left or right），这时候客户端会发送后端，玩家在这一层执行的所有动作序列（看上…

小学二年级数学题，震惊了～
type: item
date: 2022-06-17T14:07:00+00:00
description: 上海疫情封在家中有三个月，辅导了小孩子功课，每每小孩遇到不会做的题目，比她更着急。有时也会想起自己学生时代的样子，遇到难题，心中升起必须克服难题的决心，现在自己娃，怎么没有我当年的风采了。哈哈，扯远了，这两天网上看到一道小学二年级的题目，其实我之前做过类似的题目，但是当下还是震惊了，怎么现在小学二年级题目有这么难？题目是这样的：配合网友的回复，我马上想到了之前类似的问题，说是25匹马，5个赛道，至少比几场保证找出最快的2匹马。赛马这题答案我记得很清楚7场比赛，先分组进行小组赛：首先一个虚线框就是一场比赛，上来25匹马，分5组，进行5场预赛。5组比赛会得到组内的名次，比如A组，A1->A2->A3->A4->A5，每组第一名就是A1，B1，C1，D1和E1，然后第一名之间安排一场决赛：假设结果就是A1->B1->C1->D1->E1(真正结果不重要，不管怎么样，总能推理出最后的结论)，这时候我们就通过4场比赛，知道了第一名是A1，那第二名是谁呢，是不是B1，不一定哦，有可能是在小组赛中被A1淘汰的A2，所以安排场附加赛吧，A2 vs B1：附加赛之后，就能知道前两名了。话说回小学二年级赛车这道题目，其实思路一模一样，就是通过小组赛->决赛->附加赛，完成前两名的确认，也就是说赛车的话，通过至少5场比赛，保证找出前两名的赛车。作为小学二年级的题目很变态了吧，但是出题的人还多问了一句，怎么证明这件事情呢，为什么通过4场比赛一定不能保证找出前两名呢？这个证明难倒我了，抓耳挠腮半天，没想出来。然后我就看了下出题老师的分析，茅塞顿开，原来还可以使用图论+反正法来证明。大致的过程如下：首先把每一辆赛车想象成点，那么我们一共有9辆赛车，一共9个点，每场比赛，只能进行3辆赛车的比拼，每次比拼完，我们会有一个名次，紧挨着的前后两名之间，使用一条有向边连接，这个我文字讲得有点绕口，一图解千愁：圆圈表示赛车，1号比2号快，2号比3号快，所以每次比赛，我们仅仅能得到2条有向边，如果进行4场比赛，那么总共的有向边数量是4*2 = 8条，而赛车的数量是9，也就是节点数量是9，8条边，9个点，如果要保证所有边都连接到一张图中，不能出现环，否则边的数量不够。出现环就意味着9个点形成了若干个分开的子图，上面图中9个节点，分为了两个子图，那么就会有一个问题，第一名都不知道是谁，为什么？因为在1～8节点所在的图中，1号赛车最快，9号赛车单独成子图，9号赛车和谁都没有比过，那么到底9号和1号赛车谁快呢？不知道。所以8条边，安排的比赛结果，划分为多个子图，这样是无法确认前两名的。那我们4场比赛的结果，如何是可以前两名的图形呢，如下：左边就是分3场比赛（1、4、7，2、5、8和3、6、9分别比赛），得到结果后，4、2、3比一次，结果是4->2->3，转化这张单图，得到右侧的结果，其实就是一个树形的图，那么前两名就是1、4号赛车。这样我们很容易举出反例，你不是就8条边么，我最后4、2、3的结果是2->4->3，图就变成非树形图，如下：这样又回到之前多个子图的问题，我们是没法确认1号赛车和2号赛车谁快的，也就没法真正确认前两名是哪两辆赛车。OK，至少5场比赛，而非4场比赛保证找出最快的2辆赛车得证。是不是挺难的，至少我是没有想出来，通过图论+反证法证明这个数据结论，由衷发出感慨，活学活用好难啊，能做到的大佬，真的太强了。