24 Poker Game 24点扑克游戏
cn
7 minutes read (About 1011 words)

24 Poker Game 24点扑克游戏


24 Poker Game is an easy and fun math games. 4 cards (exclude the kings) are randomly picked. And the player who solves the equation to 24 first wins. For example, if the 4 cards are 10, 10 and 5 5. The formula to 24 is: (5 5) - (10 / 10). 


I have made an online 24 Poker game and an API is provided using PHP.


The online 24 Poker Game:  https://helloacm.com/24/


You can find the source code below. The algorithm used is just bruteforce. 


API (Application Programming Interface) 


https://helloacm.com/api/24/?a=10&b=10&c=5&d=5

It will return JSON-encoded data:


{“errorCode”:0,”cnt”:1,”result”:[“(5  5) - (10 \/ 10)”]}

 If $_GET parameter s is not specified, this API will use the $_POST variable s instead.


curl -X POST https://helloacm.com/api/24/ -d “a=1” -d “b=1” -d “c=2” -d “d=3”

老小的时候就玩这个 24点扑克游戏. 说来很简单 就是随机抽取4张扑克牌(除掉大小王), 然后需要以最快的速度用这4张牌 加减乘除 来得到 24的一个算式. 这需要脑子运算快, 是个很好的脑力训练. 



 周末闲来无事, 刚好那天在电视上看到 花样少年 里明星也在玩. 于是就很快的写了这么一个程序. 当然提供免费 API 地址是 https://helloacm.com/api/24/  


原理和代码


代码在 英文网页上: https://helloacm.com/24/原理很简单, 就是暴力搜索. 才4个整数. 而且几种运算符而已. 注意加入了 pow 函数也就是可以有 a 的 b 次方. 整体来说4个数字只有两种方式. 就是 2个一组 即 (a, b), (c, d) 或者 ((a, b), c), d). 代码是用PHP实现的, 因为要提供API, 而且PHP里的数组很好用. 可以将值做为索引 (key). 这样就可以通过 array_key_exists(“=24”, $try1) 这样的方式来判断是否有结果为 24的算法. 


 最关键的可以通过 array_values(array_unique($rr)); 来去掉一些明显的重复. 关键代码如下:


// 返回 两数 A, B 可能的值数组 (value, how) 键值对.

  function tryA($a, $b, $aa, $bb) {

    $a = str_replace(“=”, “”, $a);

    $b = str_replace(“=”, “”, $b);

    $r = array();

    $r[“=” . ($a + $b)] = “$aa + $bb”; 

    $r[“=” . ($a - $b)] = “$aa - $bb”;

    $r[“=” . ($a  $b)] = “$aa  $bb”;

    $r[“=” . ($b - $a)] = “$bb - $aa”;

    $r[“=” . pow($a, $b)] = “pow($aa, $bb)”;

    $r[“=” . pow($b, $a)] = “pow($bb, $aa)”;

    if ($a != 0) $r[“=” . ($b / $a)] = “$bb / $aa”;

    if ($b != 0) $r[“=” . ($a / $b)] = “$aa / $bb”;

    return $r;    

  }

计算机最厉害的就是重复的工作. 这点搜索对计算来说是小 case. 而且能把几乎所有的可能搜索出来(不排除程序可能有漏掉的)


该功能集成到公众号里 (欢迎关注 公众号 justyyuk)



 Originally published at https://steemit.com Thank you for reading my post, feel free to FOLLOW and Upvote @justyy  which motivates me to create more quality posts.


原创首发于 https://steemit.com 非常感谢阅读, 欢迎FOLLOW和Upvote @justyy 能激励我创作更多更好的内容.   


  // 同步到我的中文博客和英文算法博客  



近期热贴 Recent Popular Posts 



This page is synchronized from the post: 24 Poker Game 24点扑克游戏

Software Engineer Interview Question - How Many Ways from A to C via B? 软件工程师面试技巧之 从A到B再到C有多少种方法?
cn
11 minutes read (About 1583 words)

Software Engineer Interview Question - How Many Ways from A to C via B? 软件工程师面试技巧之 从A到B再到C有多少种方法?


Let’s see this question: If @kenchung starts at A, and he can only travels one move at a time to the north or east, and he cannot go back. If he needs to travel through B, and finally reach C, how many ways are there for him to complete his journey? 


有这么一题, 如果 @kenchung 从A到C, 一定要经过B, 并且每次走一步向东或者向北, 不能回头, 问一共有多少不同的方法. 



 


BRUTE-FORCE?  暴力搜索(穷举)


In theory, you can write a program to count each possible path from A to C, then, only those paths through B are valid. This could take ages. For example, if A and B are separated by x steps horizontally and y steps vertically (x steps east and y steps north), the total number of paths is: 


理论上说, 你可以用暴力列举所有从A到C的走法 然后再一一比较是否经过B, 不过这种方法很低效因为需要列举出所有走法. 如果水平有X步垂直有Y步那么一共的方案有: 


  or  


This reads: the number of ways to choose x or y items from (x + y) items. In this case, the x=8 and y=9, which makes the bruteforce inefficient.


可以这么理解, 一共有 x+y 步 选其中 x 或者 y 步来往东或者往北走. 


PURE MATH SOLUTION 纯数学方法: 排列组合


A better way is to simplify the problem into two steps. First is to travel from A to B and the second step is to travel from B to C, thus, if we denote f(a, b) the number of paths from a to b, then the total number is: 


 细想一下, 我们只要分两个阶段即可: 第一个阶段计算由A到B的方法数, 第二个阶段计算由B到C的方法数, 然后这么一乘就是最后的方案数了. 



So, you know the answer easily from the above.  


 根据本题, 最终方案为  …. (我知道你懂的)


RECURSION  递归


Let’s write a function f(x, y) which returns the number of different paths for x steps east and y steps north. 


 假设我们定义了 f(x, y) 用于计算 水平x步, 垂直y步的方案数: 那么: 


function f($x, $y) {


  if (($x == 0) || ($y == 0)) {


    return 1;


  }


  return f($x - 1, $y) + f($x, $y - 1); // East of North, 1 step, two choices // 每次两种选择: 往东1步或者往北一步


}


 And the answer is just:     最终答案就是: 


echo f(3, 4) * f(5, 5);

 For each recursive call, there are two choices: 1 step north or 1 step east, so the answer is just to add these two (decompose into two smaller problems). The exiting conditions are when the offset is zero (step count is zero), this is when the answer should be returned as 1.


 这里的递归写法可以认动态规化的一种, 退出条件就是当任意方向步长为0, 这时候就只有一种方案. 


DYNAMIC PROGRAMMING (MEMORIZATION)  动态规化+记忆


The recursion is straightforward. However, it does not work well if the input is large, as a lot of intermediate results are computed again and again. You can memorize the intermediate results, which will speed up the computation (each f(x,y) is only computed once because next time the result will be fetched from memory): 


 递归的计算是很多冗余的, 因为很多中间计算在递归下去会被计算多次, 很低效. 这时候我们可以记录一下这些中间结果 这样速度就会快很多(每个 f(x,y) 值只会计算一次) 


$cache = array();


function f($x, $y) {


  global $cache;


  if (($x == 0) || ($y == 0)) {


    return 1;


  }


  $key = $x.’ ‘.$y; 


  if (isset($cache[$key])) { // has the result been computed?


    return $cache[$key];


  } 


  $sol = f($x - 1, $y) + f($x, $y - 1);


  $cache[$key] = $sol; // store the result


  return $sol;


}


The next improvement to improve this Dynamic Programming DP implementation is to use the iteration, which avoids the recursion. This is computed bottom-up direction. 


动态规化也不需要用递归来实现, 我们可以用更为高效的数组+迭代的方式, 从低往上计算. 


function f($x, $y) {


  $ans = array();


  for ($i = 0; $i <= $x; ++ $i) $ans[$i][0] = 1;


  for ($i = 0; $i <= $y; ++ $i) $ans[0][$i] = 1;


  for ($i = 1; $i <= $x; ++ $i) {


    for ($j = 1; $j <= $y; ++ $j) {


      $ans[$i][$j] = $ans[$i - 1][$j] + $ans[$i][$j - 1]; 


    }


  }


  return $ans[$x][$y];


}


 This runs at complexity O(xy) as well as the space complexity (need to declare a 2-dimensional array). 


 时间复杂度和空间复杂度都是 O(xy). 为嘛用PHP? 因为PHP是世界上最好的语言. 


Update: the next day, it comes to me that the space complexity can be further reduced to O(y): https://steemit.com/cn/@justyy/software-engineer-interview-question-how-to-improve-dynamic-programming-space-complexity 


更新：第二天 想到 空间复杂度可以降到 O(y)： https://steemit.com/cn/@justyy/software-engineer-interview-question-how-to-improve-dynamic-programming-space-complexity 




PS: Why PHP?  —  PHP is the best programming language in the world….



Originally published at https://steemit.com Thank you for reading my post, feel free to FOLLOW and Upvote @justyy which motivates me to create more quality posts.


原创首发于 https://steemit.com 非常感谢阅读, 欢迎FOLLOW和Upvote @justyy  能激励我创作更多更好的内容.   


 // 同步到我的中文博客和英文算法博客  



 近期热贴 Recent Popular Posts 



This page is synchronized from the post: Software Engineer Interview Question - How Many Ways from A to C via B? 软件工程师面试技巧之 从A到B再到C有多少种方法?

Software Engineer Interview Question - Dynamic Programming - Integer Break 软件工程师面试技巧之 动态规化 - 整数拆分
cn
9 minutes read (About 1388 words)

Software Engineer Interview Question - Dynamic Programming - Integer Break 软件工程师面试技巧之 动态规化 - 整数拆分


Dynamic Programming (DP)  is one of the very important algorithm in Computer Science. Here is the simplest example of demonstrating the concept of DP if you want to tell you 5-year-old son.



Give 5 matches to your son, and ask: “How many matches do you have?”


– The kid counts and says: Five.


Then, give one more match to your son and ask, how about now?


– The kid says Six because he knows Five + One More equals Six…  


The concept of DP is quite similar to this: breaking a problem into a smaller one + memorization of solutions to sub-problems.


 Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get. For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4). 

We can use Dynamic Programming (DP) to solve this problem. The puzzle does not ask you exactly how to break the integer. If we use f(n) to denote that the maximum product to break the integer n, then we have the following recurrence formula: 


  for  1 <= j < i <= n


If we break the integer i-j, the intermediate result is f(i-j) otherwise we have to check if we break i into i-j and j. The time complexity is O(n^2) and the space complexity is O(n). 


动态规化 (Dynamic Programming) 是个计算机领域里很重要的算法，我在高中参加过三次信息学奥林匹克竞赛 (ACM)，每年必有一题用动归(DP)来解答. 动态规化其实就是 把问题分解成子问题+记忆子问题求解的一个过程。


你如何教你的孩子DP是什么呢？


比如：你给你的孩子5根火柴，你的孩子数了数然后说有5根。然后你再给你的孩子1根火柴然后问一共有多少根，这时候你的孩子会马上说出6根，因为他知道已经有5根了，再加上1根就是6根。


原理就是：把问题分析成更小的问题，并分而求之，子问题的解会被保存下来这样在求解更大的问题的时候就不需要再重新把中间结果再算一遍了。


动态规化的解法经常是较优的一种解法，我们来看这么一道面试题：


给定一个正整数，将它拆分成至少两个正整数，求出这些正整数的最大乘积。比如 整数2，可以拆分成1+1， 乘积是1，当输入是10，需要分解成3+3+4，这样所得的最大乘积是36。


你会怎么解？暴力搜索？这种解法不好写，而且时间复杂度也大。可以用回溯+剪枝，但时间复杂度也相对较大，特别是当N较大的时候也会时间太久Time Exceeded.


动规解答这题就较为简单。这题并没有让你详细写出怎么拆分的方案，只需要解出最大的乘积即可。所以我们有以下的方案：


  其中 1 <= j < i <= n


我们用 f(n) 来表示整数N拆分后的最大乘积，那么我们当我们把整数 i 分解成两部分 i - j 和 j,  那么 最大乘积是 f(i - j) j 和 (i - j) j 的较大值。我们需要O(N^2)循环来寻求最优拆分法。


动规在计算 f(n) 的时候会需要取决于 f(i - j)的值，这时候每个f(m) 的值就会被保存起来以供之后迭代使用。这也是一个记忆的过程。以下实现就相对简单好理解。空间复杂度也是O(N^2)


If we break the integer i-j, the intermediate result is f(i-j) otherwise we have to check if we break i into i-j and j. The time complexity is O(n^2) and the space complexity is O(n). 


class Solution {


public:


    int integerBreak(int n) {


        vector<int> f(n + 1, 0);


        f[1] = 0;


        f[2] = 1;


        for (int i = 2; i < n + 1; i ++) {


            for (int j = 1; j < i; j ++) {


                f[i] = max(f[i], max(i - j, f[i - j]) * j);


            }


        }


        return f[n];


    }


};



Thank you for reading my post, feel free to FOLLOW and Upvote @justyy which motivates me to create more quality posts.


非常感谢阅读, 欢迎FOLLOW和Upvote @justyy 能激励我创作更多更好的内容.    


 // 同步到我的中文博客和英文算法博客  



 近期热贴 Recent Popular Posts 



This page is synchronized from the post: Software Engineer Interview Question - Dynamic Programming - Integer Break 软件工程师面试技巧之 动态规化 - 整数拆分

Planning Cards – Agile Poker Game! 敏捷开发扑克游戏
cn
5 minutes read (About 793 words)

Planning Cards – Agile Poker Game! 敏捷开发扑克游戏


At the beginning of each Agile sprints, the team members would sit down at a round table, planning tasks and breaking down each tasks into sub-tasks. The estimation of efforts will be the major outcome of this planning meeting. The following planning cards may be useful in this activity. 


A random (or in turn) team member gets to break down the task in advance. And for each sub-tasks, every developer picks a card and show it on the table at the same time. The point on the card represents the efforts required to accomplish the job. Of course, at beginning, a roughly-medium-size sub-tasks will be taken for the reference point (score = 1). 


敏捷开发 Agile Development 在每个短跑 Sprint 开始的时候都会有一个 圆桌会议. 开发小组成员会聚在一起 讨论需要开发的任务 并且会细分每个任务. 这时候我们就可以用到下面的扑克卡片. 预先需要有一个成员(可以是随机, 可以是轮流) 先把需要开发的任务汇总一下 并且把每个开发任务尽可能的细分成子任务. 这时候一开始会选一个难度适中的任务做为标准 (分数为1) 



 Agile Planing Cards


 “The deck of Planning Poker(R) cards is for youruse in estimating. The deck contains enough cards for four estimators to each hold cards with the following values: ?, 0, 1/2, 1, 2, 3, 5, 8, 13, 20, 40, 100 and infinity”. 


“每副卡片可供4人预估 分数为 ?, 0, 1/2, 1, 2, 3, 5, 8, 13, 20, 40, 100 和无穷大”. 



 Agile Planing Cards 



 Agile Planing Cards 



 Agile Planing Cards


Base on the points shown by everybody, opinions are required (and there might be discussions) for those who votes for the highest/lowest points. At the end of each estimation, the score will be averaged (or pick the medium) and recorded.This is called Agile poker game! 


每个人都想好每个任务的难度 并且同时的把卡片(对应难度系数) 亮在桌上. 这时候 出最高或者最低分数的人则需要 解释为什么 当然这时候就很可能会有激烈的讨论了. 最后统计分数的时候可以去掉一个最高分和最低分 剩下的取平均 并记录起来.这就是敏捷开发扑克游戏! 



Thank you for reading my post, feel free to FOLLOW and Upvote @justyy which motivates me to create more quality posts.


常感谢阅读, 欢迎FOLLOW和Upvote @justyy 能激励我创作更多更好的内容.     


// 同步到我的中文博客和英文算法博客   



 近期热贴 Recent Popular Posts 



This page is synchronized from the post: Planning Cards – Agile Poker Game! 敏捷开发扑克游戏

Software Engineer Interview Question - How to Check Valid Sudoku in C/C++? 软件工程师面试技巧之 如何检查数独的有效性
cn
11 minutes read (About 1611 words)

Software Engineer Interview Question - How to Check Valid Sudoku in C/C++? 软件工程师面试技巧之 如何检查数独的有效性


I’d like to continue the series of “Software Engineer Interview Questions or Tips” where I’d share you with some coding questions/tips from time to time. To share is the process of re-learning.



 Determine if a Sudoku is valid. The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’. A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated. 

 A valid Sudoku contains three conditions: (1) all rows should contain exactly 1 to 9. (2) all columns should contain exactly 1 to 9. (3) all sub grids (9 of them) should contain exactly 1 to 9. 


 The best data structure we can use is the STL:set, we need to clean the set before next validation (row, column or grid). 


前不久写的这个 软件工程师面试技巧 的系列，朋友很喜欢，所以我打算把我毕生所学（哈哈）整理整理分享于大家，望喜欢。另：我觉得：分享就是一种再学习的过程。



  1. 去年 Google 的面试题 - 打印消息

  2. 软件工程师面试技巧之 使用哈希表降复杂度


给定一个数独，我们要检查是否有效。一个有效的数独横的竖的都只出现1-9的数字各一次，并且9个小宫格里的数字也只出现1-9各一次。


你能快速的告诉我以下是否是个有效的数独么？



我们只需要检查给定的数独中已经填好的数字。最好的方法就是通过 C++中 STL 的 unordered_set (未排序的集合) 来保存已经出的数字。记得检查下一个9宫格或者行或列的时候清空集合便可。


class Solution {


public:


    bool isValidSudoku(vector<vector<char>>& board) {


        unordered_set<int> has;


        for (int i = 0; i < 9; i ++) {


            has.clear();


            // rows = 行


            for (int j = 0; j < 9; j ++) {


                if (board[i][j] != ‘.’) {


                    if (has.count(board[i][j])) {


                        return false;


                    }


                    has.insert(board[i][j]);


                }


            }


            has.clear();


            // columns = 列


            for (int j = 0; j < 9; j ++) {


                if (board[j][i] != ‘.’) {


                    if (has.count(board[j][i])) {


                        return false;


                    }


                    has.insert(board[j][i]);


                }


            }


        }


        for (int i = 0; i < 3; i ++) {


            for (int j = 0; j < 3; j ++) {


                // 9 sub grids - 每一个9宫格也要检查


                has.clear();


                for (int x = i 3; x < i 3 + 3; x ++) {


                    for (int y = j 3; y < j 3 + 3; y ++) {


                        if (board[x][y] != ‘.’) {


                            if (has.count(board[x][y])) {


                                return false;


                            }


                            has.insert(board[x][y]);


                        }


                    }


                }


            }


        }


        return true;


    }


};


这题并不难，意在考灵活使用数据类型（集合），面试的时候第一个需要思考的就是：这题是否可以用穷举（暴力）来解答？即使你的暴力不太现实（需要计算力太久，像比特币挖矿一样），但是对于考官来说，这也是解决方法的第一步，之后才会考虑是否可以有其它高效的方法来提速。



Originally Published in Steemit. Thank you for reading my post, feel free to FOLLOW and Upvote @justyy which motivates me to create more quality posts. 


原创首发 SteemIt, 非常感谢阅读, 欢迎FOLLOW和Upvote @justyy 能激励我创作更多更好的内容.     


// 同步到我的中文博客和英文算法博客 



广告一下微信群用于讨论各类编程技术：只要您对技术感兴趣都可以加群哈。



近期热贴 Recent Popular Posts 



This page is synchronized from the post: Software Engineer Interview Question - How to Check Valid Sudoku in C/C++? 软件工程师面试技巧之 如何检查数独的有效性

How to Claim BCC? BTC Hard-Fork via C program (Linux) 小白教程: 怎么领取 BCC (Bitcoin Cash) ?
cn
8 minutes read (About 1260 words)

How to Claim BCC? BTC Hard-Fork via C program (Linux) 小白教程: 怎么领取 BCC (Bitcoin Cash) ?


 这个月初比特币(8月1日)的硬分叉 (Hard Fork) 是互联网加密货币的一大新闻, 像我这等小白, 只关心钱包里的钱是否增值. 计算机中的 fork 意思就是进程自我复制一份 除了进程 pid 不一样, 执行的代码都一样, 这次比特币 (代码BTC) 进行了 fork 操作, 分出一孩子 也就是 BCC (Bitcoin Cash). 那么我用以下在LINUX下的C程序来演示一下这过程.  


#include <stdio.h>

#include <unistd.h>

#include <stdlib.h>

 

int main() {

        pid_t pid;

        switch (pid = fork()) { // 8月1号 hard fork

                case -1:

                        perror(“Hard Fork 失败”);

                        break;

                case 0: // 子进程 Bitcoin Cash (BCC)

                        printf (“%s\n“, “BCC 活了”);

                        break;

                default: // 父进程 BTC

                        printf (“%s\n“, “我是 BTC”);

                        break;

        }

        for (;;) ; // 一分为二 共存

}

BCC 和 BTC 从此各走一方, 但他们在8月一号前拥有一样的过去. 但之后你可以下载一个BCC钱包　然后里面就会有和BTC钱包等量的BCC. BCC (Bitcoin Cash)刚出生就从最高0.48 BTC一路逛跌, 当前1个BCC (Bitcoin Cash)值大概0.02BTC.


怎么领取 BCC (BITCOIN CASH)?


由于BCC和BTC共享密钥, 为了保险期间, 最好把原先BTC里的比特币给转移到另一个钱包, 或者卖了变现(我的做法). 有些在线比特币钱包比如 coinbase 还有其它一些交易所会在8月1号后自动给BCC钱包充等量的钱. 我用的是离线的Electrum钱包, 他们家做了一个BCC的钱包Electron Cash Wallet, 同样的团队做出的两个钱包也是相当的兼容. 


官方做法是把BTC钱包的密钥给导出保存然后打开BCC钱包再导入同样的密钥, 但实际上我在安装完BCC钱包后打开就有同等量的BCC货币了. 



 短期BCC情势并不明朗, 有专家预言长远来看1个BCC最多不超过100美元(而现在1个BTC值2000英镑), 不得不说人们还是比较信任BTC. 那BCC在我看来也如其它山寨币一样. 所以肯定也有很多像我一样的人不会长期看好而急抛, 这就导致了BCC价格不会太高.


It’s unlikely that BCH will survive at prices above $100 in the long term.

–Samson Mow, a video game developer and CEO of Pixelmatic

现在已经有较多的交易所 比如 bittrex, poloniex 都支持 BCC 交易, 而很多人也立马抛了BCC (Bitcoin Cash). 我是小户, 上个月换了一些比特币 在这次BTC分叉之前只存有不到0.18个BTC, 获得等量的 0.18 BCC, 这大概按现在的汇率能换 10几美元吧… 没卵用, 但有总比没有好, 这也是天上白掉下来的财富. 


BTC和BCC的关系即可以说是父子 也可以说是兄弟, 两种加密货币的技术架构都一样, 挖矿难度也类似, 但是BCC (Bitcoin Cash)现在普遍不被看好, 所以价钱和BTC差太多, 所以矿工更不想挖BCC (Bitcoin Cash), 是一种恶性循环 这并不有利于BCC的良性发展.


我呢, 这点小钱, 还是再等等. 



Originally published in Steemit. Thank you for reading my post, feel free to FOLLOW and Upvote @justyy which motivates me to create more quality posts.


Steemit 原创首发. 非常感谢阅读, 欢迎FOLLOW和Upvote @justyy 能激励我创作更多更好的内容.        


// 同步发表于我的中文博客和英文博客。  



近期热贴 Recent Popular Posts 



This page is synchronized from the post: How to Claim BCC? BTC Hard-Fork via C program (Linux) 小白教程: 怎么领取 BCC (Bitcoin Cash) ?

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×