ジャンケン結果の中から間違ってるっぽいのを見つけ出すiPhoneアプリのサンプルコードを描いてみます。
#import “ViewController.h”
#include <algorithm>
#include <vector>
#include <memory>
using namespace::std;
typedef struct pattern {
// type:0 Tie game
// type:1 X win
int type, x, y;
} Pattern;
#define MMAX 100
//—————-
// UNION FIND
//—————-
class UnionFind {
public:
UnionFind();
int find(int);
void unite(int, int);
bool same(int, int);
private:
int parent[MMAX], rank[MMAX];
};
UnionFind::UnionFind() {
for (int i=0; i<MMAX; i++) { parent[i] = i, rank[i] = 0; }
}
int UnionFind::find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void UnionFind::unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (rank[x] > rank[y]) swap(x, y);
parent[x] = y;
if (rank[x] == rank[y]) rank[y]++;
}
bool UnionFind::same(int x, int y) {
return find(x) == find(y);
};
// ———————
// Rock-paper-scissors
// ———————
class RPSChecker {
public:
vector<int> solve(vector<Pattern>);
};
vector<int> RPSChecker::solve(vector<Pattern> patterns){
vector<int> diff;
int N = (int)patterns.size();
// n * 3 space. tie: input x = rock, y = rock (0..<N), x=paper, y=paper (N..<2N), …
UnionFind *uf = new UnionFind();
for (int i=0; i<patterns.size(); i++) {
Pattern pt = patterns[i];
if (pt.type == 0) {
// Tie game check
// rock space(0..<N), paper space(N..<2N), scissors space(2N..<3N)
if (uf->same(pt.x, pt.y + N) || uf->same(pt.x, pt.y + 2 * N)) {
diff.push_back(i);
} else {
uf->unite(pt.x, pt.y);
uf->unite(pt.x + N, pt.y + N);
uf->unite(pt.x + 2*N, pt.y + 2*N);
}
} else {
// x win
// x{0:N=rock N:2N=paper 2N:3N=scissors} win y :{ 0:N=scissors N:2N=rock 2N:3N=paper}
if (uf->same(pt.x, pt.y) || uf->same(pt.x, pt.y + 2*N)) {
diff.push_back(i);
} else {
uf->unite(pt.x, pt.y + N);
uf->unite(pt.x + N, pt.y + 2*N);
uf->unite(pt.x + 2*N, pt.y);
}
}
}
return diff;
}
@interface ViewController ()
@property (nonatomic) vector<Pattern> patt;
@end
@implementation ViewController
– (void)viewDidLoad {
[super viewDidLoad];
UILabel *title = [[UILabel alloc] init];
title.text = @”Spot the Difference??\nRock-paper-scissors”;
title.font = [UIFont systemFontOfSize:20];
title.textAlignment = NSTextAlignmentCenter;
title.numberOfLines = 0;
[title sizeToFit];
title.center = CGPointMake(CGRectGetMidX(self.view.bounds), 70);
[self.view addSubview:title];
vector<Pattern> v;
for (int i=0; i<30; i++) {
int t = arc4random() % 2;
int x = arc4random() % 15;
int y = (x + (arc4random() % 14)) % 15; // random 0~14 y != x
v.push_back({.type=t, .x=x, .y=y});
UILabel *q = [[UILabel alloc] initWithFrame:CGRectMake(100, i * 16 + 100, 200, 20)];
if (t == 1) {
q.text = [NSString stringWithFormat:@”x=%d, y=%d, x win!”, x, y];
} else {
q.text = [NSString stringWithFormat:@”x=%d, y=%d, tie game!”, x, y];
}
q.font = [UIFont systemFontOfSize:12];
[self.view addSubview:q];
}
self.patt = v;
}
– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event{
shared_ptr<RPSChecker> cppClass(new RPSChecker());
vector<int> difference = cppClass->solve(self.patt);
for (int i=0; i<difference.size(); i++) {
int no = difference[i];
UIView *redMarker = [[UIView alloc] initWithFrame:CGRectMake(100, no * 16 + 110, 200, 4)];
redMarker.transform = CGAffineTransformMakeTranslation(500, 0);
redMarker.backgroundColor = [[UIColor redColor] colorWithAlphaComponent:0.6];
[self.view addSubview:redMarker];
[UIView animateWithDuration:0.5 delay:0.5 * i options:0 animations:^{
redMarker.transform = CGAffineTransformIdentity;
} completion:nil];
}
}
@end