专栏名称: 申龙斌的程序人生
分享可繁殖的知识与技能:GTD时间管理、读书心得、个人成长、财富自由之路
分享
今天看啥  ›  专栏  ›  申龙斌的程序人生

通过欧拉计划学Rust编程(第54题)

申龙斌的程序人生  · 公众号  · 程序员  · 2020-02-15 08:43

由于研究Libra等数字货币编程技术的需要,学习了一段时间的Rust编程,一不小心刷题上瘾。

刷完欧拉计划中的63道基础题,能学会Rust编程吗?

“欧拉计划”的网址: https://projecteuler.net

英文如果不过关,可以到中文翻译的网站: http://pe-cn.github.io/

这个网站提供了几百道由易到难的数学问题,你可以用任何办法去解决它,当然主要还得靠编程,编程语言不限,论坛里已经有Java、C#、Python、Lisp、Haskell等各种解法,当然如果你直接用google搜索答案就没任何乐趣了。

这次解答的是第54题: https://projecteuler.net/problem=54



题目描述:

扑克手牌

在扑克游戏中,玩家的手牌由五张牌组成,其等级由低到高分别为:

  • 单牌:牌面最大的一张牌。

  • 对子:两张牌面一样的牌。

  • 两对:两个不同的对子。

  • 三条:三张牌面一样的牌。

  • 顺子:五张牌的牌面是连续的。

  • 同花:五张牌是同一花色。

  • 葫芦:三条带一个对子。

  • 四条:四张牌面一样的牌。

  • 同花顺:五张牌的牌面是连续的且为同一花色。

  • 同花大顺:同一花色的10、J、Q、K、A。

牌面由小到大的顺序是:2、3、4、5、6、7、8、9、10、J、Q、K、A。

如果两名玩家的手牌处于同一等级,那么牌面较大的一方获胜;例如,一对8胜过一对5(参见例1);如果牌面相同,例如双方各有一对Q,那么就比较玩家剩余的牌中最大的牌(参见例4);如果最大的牌相同,则比较次大的牌,依此类推。

S代表黑桃(Spade),H表示红桃(Heart),D表示方块(Diamond),C表示梅花(Club),T表示10(Ten),考虑以下五局游戏中双方的手牌:

手牌玩家1玩家2胜者
15H 5C 6S 7S KD2C 3S 8S 8D TD玩家2

一对5一对8
25D 8C 9S JS AC2C 5C 7D 8S QH玩家1

单牌A单牌Q
32D 9C AS AH AC3D 6D 7D TD QD玩家2

三条A同花方片
44D 6S 9H QH QC3D 6D 7H QD QS玩家1

一对Q一对Q

最大单牌9最大单牌7
52H 2D 4C 4D 4S3C 3D 3S 9S 9D

葫芦葫芦

(三条4)(三条3)

在poker.txt文本文件中,包含有两名玩家一千局的手牌。每一行包含有10张牌(均用一个空格隔开):前5张牌属于玩家1,后5张牌属于玩家2。你可以假定所有的手牌都是有效的(没有无效的字符或是重复的牌),每个玩家的手牌不一定按顺序排列,且每一局都有确定的赢家。

其中有多少局玩家1获胜?




解题过程:

遇到一个复杂的问题,可以尝试将问题分解,变为一个个简单的情况,然后慢慢逼近最终的问题。

第一步: 先读文件,将玩家1和玩家2的牌分开。

第22题里已经学会了读文件,并且将字符串分隔成向量,再利用切片功能将前5个赋给玩家1,后5个赋给玩家2。

let data = std::fs::read_to_string("poker.txt").expect("打开文件出错");
let data2 = data.replace("\r\n", "\n");
let lines = data2.trim().split('\n');
for line in lines {
let hand1 = &line[..14];
let hand2 = &line[15..];
println!("{:?} {:?}", hand1, hand2);
}


第二步: 多文件管理

这个项目涉及到手牌、牌张、花色等概念,适合用面向对象的编程思路。Rust项目对多源文件的功能支持也相当不错,main.rs放主程序,poker.rs放扑克相关的模块。

一手牌Hand由多张牌Card组成,一个Card由牌点(用8位整数表示)和花色Suit构成,花色只有4种,适合用枚举表示。Rust里的枚举看上去与C/C#/Java等语言的枚举很像,但实际上它的功能远远不是一个简单的枚举。

// 文件poker.rs
pub enum Suit {
Spade, // 黑桃
Heart, // 红桃
Diamond, // 方块
Club, // 梅花
}

pub struct Card {
value: u8, // 214表示2, 3, ..., 10, J, Q, K, A
suit: Suit,
}

pub struct Hand {
cards: Vec,
}

main.rs需要加一行语句,告诉主程序要使用poker.rs中定义的模块。

mod poker;

这个时候,程序可以编译,会给出几个警告,提示Hand,Card和Suit这些类型从来没用过。


第三步: 构建一张牌Card

我们的任务要通过一个字符串构建出一个Card对象。比如,"8C"构建出梅花8,"TS"构建也黑桃10,"KC"为梅花K,"9H"为红桃9,"4S"为黑桃4。

这个时候要先学会Rust中的Trait概念,Trait这个东西很像Java/C#里的接口,但又不是。Rust内置不支持构造函数,下面这段代码相当于给Card定义了一个静态方法new(),相当于其它语言里的构造函数。

impl Card {
pub fn new(str_card: &str) -> Card {
let first_char = str_card.chars().next().unwrap();
let card_value = "..23456789TJQKA"
.chars()
.position(|c| c == first_char)
.unwrap() as u8;
let second_char = str_card.chars().nth(1).unwrap();
let card_suit = if second_char == 'S' {
Suit::Spade
} else if second_char == 'H' {
Suit::Heart
} else if second_char == 'D' {
Suit::Diamond
} else {
Suit::Club
};
Card {
value: card_value,
suit: card_suit,
}
}
}

主程序里可以构造一个card(这里用梅花8),尝试打印出来。

let card = poker::Card::new("8C");
println!("{:?}", card);

编译时Rust会给出相当清楚的错误信息,还给出了修改建议

error[E0277]: `poker::Card` doesn't implement `std::fmt::Debug`
--> src\main.rs:14:22
|
14 | println!("{:?}", card);
| ^^^^ `poker::Card` cannot be formatted using `{:?}`
|
= help: the trait `std::fmt::Debug` is not implemented for `poker::Card`
= note: add `#[derive(Debug)]` or manually implement `std::fmt::Debug`
= note: required by `std::fmt::Debug::fmt`

我们声明了一个新类型Card,但系统并不知道如何把它转换成字符串显示出来。按照提示,我们在Card和Suit前面各加上一行语句,让系统帮我们自动实现一个输出格式。

#[derive(Debug)]
pub enum Suit {
Spade, // 黑桃
Heart, // 红桃
Diamond, // 方块
Club, // 梅花
}

#[derive(Debug)]
pub struct Card {
value: u8, // 214表示2, 3, ..., 10, J, Q, K, A
suit: Suit,
}

此时程序可以顺利编译,运行可以得到如下结果:

Card { value: 8, suit: Club }

输出得虽然有点复杂,但容易理解。如果我们就想输出"8C"这样的字符串,则需要实现Display这个trait里的fmt()函数。注意write!语句后面千万别习惯性地加个分号,否则出现的编译错误让人好困惑!

use std::fmt::{Display, Error, Formatter};
impl Display for Suit {
// 只用一个字母表示: S,H,D,C
fn fmt(&self, f: &mut Formatter) -> Result {
let name = format!("{:?}", self);
write!(f, "{}", &name[..1])
}
}

impl Display for Card {
fn fmt(&self, f: &mut Formatter) -> Result {
let first_char = "..23456789TJQKA".chars().nth(self.value as usize).unwrap();
write!(f, "{}{}", first_char, self.suit)
}
}

现在构建5张牌,输出出来。

let card1 = poker::Card::new("8C");
let card2 = poker::Card::new("TS");
let card3 = poker::Card::new("KC");
let card4 = poker::Card::new("9H");
let card5 = poker::Card::new("4S");
println!("{} {} {} {} {}", card1, card2, card3, card4, card5);


第四步: 构建一手牌Hand

对于Hand,也要实现fmt()函数,还要实现一个构造函数new()。

use itertools::Itertools;
impl Display for Hand {
fn fmt(&self, f: &mut Formatter) -> Result {
let str_cards = self.cards.iter().map(|x| x.to_string()).join(" ");
write!(f, "{}", str_cards)
}
}

impl Hand {
pub fn new(str_cards: &str) -> Hand {
let mut v = vec![];
for s in str_cards.split(' ') {
v.push(Card::new(s));
}
Hand { cards: v }
}
}

主程序这样写:

let hand = poker::Hand::new("8C TS KC 9H 4S");
println!("{}", hand);


第五步: 比较两个对象的大小

现在我们想比较两手牌的大小,主程序写成这样。

let hand1 = poker::Hand::new("8C TS KC 9H 4S");
let hand2 = poker::Hand::new("7D 2S 5D 3S AC");
if hand1 > hand2 {
println!("player1 wins" );
}

想让两个对象能够相互比较大小,需要实现四个trait(Ord、PartialOrd、Eq和PartialEq)中的几个函数。

use std::cmp::{Ord, Ordering};
impl Ord for Hand {
fn cmp(&self, other: &Self) -> Ordering {
self.to_string().cmp(&other.to_string())
}
}

impl PartialOrd for Hand {
fn partial_cmp(&self, other: &Self) -> Option {
Some(self.cmp(other))
}
}

impl Eq for Hand {}

impl PartialEq for Hand {
fn eq(&self, other: &Self) -> bool {
self.to_string().eq(&other.to_string())
}
}

现在,这里的比较逻辑还没有实现,暂时用字符串的比较代替。有几点要留意: 1)Ord里的cmp()函数,PartialOrd里的partial_cmp()函数,一个是表示全序,一个表示偏序。 2)cmp()和partial_cmp()两个函数的返回值有点区别,后面的多Option<> 3)Eq里的内容是空的,但必须要写 4)PartialEq里的函数名是eq() 5)实现了这些trait后,程序会自动理解“”、“==”这些比较运算符。

第六步: 比较两手牌的大小

这时需要细心了,判断同花、顺子、四条、三条、对子等情况,为了后面的比较,我声明了一个枚举enum,用来区分各种牌型,从这里可以领略Rust里枚举的强大。

pub enum HandType {
HighCard(u8, u8, u8, u8, u8), // 单牌
//对子
OnePair {
value_pair: u8,
max_remain: u8, // 除了对子之外,剩下最大的牌点
},
//两对
TwoPairs {
high_pair: u8, // 最大的一对
low_pair: u8, // 最小的一对
max_remain: u8, // 除了两对之外,剩下最大的牌点
},
KindThree(u8), // 三条
Straight(u8), // 顺子
Flush(u8), // 同花
//葫芦,即三条带一个对子
FullHouse {
value_kind_three: u8,
value_pair: u8,
},
KindFour(u8), // 四条
StraightFlush(u8), // 同花顺
RoyalFlush, // 同花大顺
}

再声明两个函数ranking1()和ranking2(),两次比较后能够区分大小。

impl HandType {
pub fn ranking1(&self) -> u8 {
match self {
HighCard(_, _, _, _, _) => 0,
OnePair { .. } => 1,
TwoPairs { .. } => 2,
KindThree(_) => 3,
Straight(_) => 4,
Flush(_) => 5,
FullHouse { .. } => 6,
KindFour(_) => 7,
StraightFlush(_) => 8,
RoyalFlush => 9,
}
}

pub fn ranking2(&self) -> u64 {
// ...
}

这里有一个".."的语法点,忽略结构体里的内容。

FullHouse { .. } => 6,

相当于:

FullHouse {
value_kind_three: _,
value_pair: _,
} => 6,

Ord里的cmp()和PartialEq里的eq()的逻辑也要相应修改一下。

impl Ord for HandType {
fn cmp(&self, other: &Self) -> Ordering {
self.ranking1()
.cmp(&other.ranking1())
.then(self.ranking2().cmp(&other.ranking2()))
}
}
impl PartialEq for HandType {
fn eq(&self, other: &Self) -> bool {
self.ranking1() == other.ranking1() && self.ranking2() == other.ranking2()
}
}

剩下就是依次判断各种情况,需要足够的耐心和测试。

use itertools::Itertools;
impl Hand {
//是否五张牌同一个花色。
fn is_flush(&self) -> bool {
self.cards.iter().map(|card| card.suit).all_equal()
}

//判断五张牌是否连号,先将牌面数值从小到大排序,两两之差为1就是顺子。
fn is_straight(&self) -> bool {
let mut v: Vec<u8> = self.cards.iter().map(|x| x.value).collect();
v.sort();
(0..4).all(|i| v[i + 1] - v[i] == 1) //两两之差都为1
}


第七步: 将相关类整理到一个文件夹下

源文件较多时,可以放在一个文件夹下,模块里还可以有子模块。比如这样组织文件:

src/
+---main.rs
+---poker/
+---card.rs
+---hand.rs
+---hand_type.rs
+---mod.rs
+---suit.rs

poker文件夹可以自动识别为一个mod,需要mod.rs文件的配合,这里声明用到的子模块,编译器可以自动找到相应的源文件。

pub mod card;
pub mod hand;
pub mod hand_type;
pub mod suit;

hand.rs文件里使用其它模块的内容时,需要用use语句。

use super::card::*;
use super::hand_type::*;

--- END ---


我把解题的过程记录了下来,写成了一本《用欧拉计划学 Rust 编程》PDF电子书,请随意下载。

链接:https://pan.baidu.com/s/1NRfTwAcUFH-QS8jMwo6pqw

提取码:qfha

该PDF文件将来会不定期更新,可以在公众号后台回复“rust”,得到最新的下载链接。


历史文章:

学会10多种语言是种什么样的体验?

刷完欧拉计划中的63道基础题,能学会Rust编程吗?



今天看啥 -
本文地址:http://www.jintiankansha.me/t/V0m5KLnipq