Content-Length: 303874 | pFad | https://gist.github.com/yuizumi/547960ae83c9b3059b07

62 ShantenAnalysis.cs · GitHub
Skip to content

Instantly share code, notes, and snippets.

@yuizumi

yuizumi/ShantenAnalysis.cs Secret

Last active December 23, 2015 14:19
Show Gist options
  • Save yuizumi/547960ae83c9b3059b07 to your computer and use it in GitHub Desktop.
Save yuizumi/547960ae83c9b3059b07 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
ShantenAnalysis.cs
// https://github.com/ymatsux/MjaiClients
using System;
using System.Collections.Generic;
using System.IO;
public class MentsuUtil {
private const int NUM_MENTSU_ID = 55;
private const int MANZU_START = 0;
private const int PINZU_START = 9;
private const int SOZU_START = 18;
private const int MANZU_SHUNTSU_START = 0;
private const int PINZU_SHUNTSU_START = 7;
private const int SOZU_SHUNTSU_START = 14;
private const int KOTSU_START = 21;
private static readonly int[][] MENTSUS;
static MentsuUtil() {
MENTSUS = new int[NUM_MENTSU_ID][];
for (int i = MANZU_SHUNTSU_START; i < PINZU_SHUNTSU_START; i++) {
MENTSUS[i] = new int[3];
MENTSUS[i][0] = i - MANZU_SHUNTSU_START + MANZU_START;
MENTSUS[i][1] = i - MANZU_SHUNTSU_START + MANZU_START + 1;
MENTSUS[i][2] = i - MANZU_SHUNTSU_START + MANZU_START + 2;
}
for (int i = PINZU_SHUNTSU_START; i < SOZU_SHUNTSU_START; i++) {
MENTSUS[i] = new int[3];
MENTSUS[i][0] = i - PINZU_SHUNTSU_START + PINZU_START;
MENTSUS[i][1] = i - PINZU_SHUNTSU_START + PINZU_START + 1;
MENTSUS[i][2] = i - PINZU_SHUNTSU_START + PINZU_START + 2;
}
for (int i = SOZU_SHUNTSU_START; i < KOTSU_START; i++) {
MENTSUS[i] = new int[3];
MENTSUS[i][0] = i - SOZU_SHUNTSU_START + SOZU_START;
MENTSUS[i][1] = i - SOZU_SHUNTSU_START + SOZU_START + 1;
MENTSUS[i][2] = i - SOZU_SHUNTSU_START + SOZU_START + 2;
}
for (int i = KOTSU_START; i < NUM_MENTSU_ID; i++) {
MENTSUS[i] = new int[3];
MENTSUS[i][0] = MENTSUS[i][1] = MENTSUS[i][2] = i - KOTSU_START;
}
}
public static void addMentsu(int[] countVector, int mentsuIndex) {
countVector[MENTSUS[mentsuIndex][0]]++;
countVector[MENTSUS[mentsuIndex][1]]++;
countVector[MENTSUS[mentsuIndex][2]]++;
}
public static void removeMentsu(int[] countVector, int mentsuIndex) {
countVector[MENTSUS[mentsuIndex][0]]--;
countVector[MENTSUS[mentsuIndex][1]]--;
countVector[MENTSUS[mentsuIndex][2]]--;
}
public static int[] getMentsu(int mentsuIndex) {
return MENTSUS[mentsuIndex];
}
public static bool isYaochuhai(int mentsuId) {
return mentsuId == 21 || mentsuId == 29 ||
mentsuId == 30 || mentsuId == 38 ||
mentsuId == 39 || mentsuId == 47 ||
(48 <= mentsuId && mentsuId < 55);
}
public static bool isSangenpai(int mentsuId) {
return 52 <= mentsuId && mentsuId < 55;
}
public static bool hasYaochuhai(int mentsuId) {
return mentsuId == 0 || mentsuId == 6 ||
mentsuId == 7 || mentsuId == 13 ||
mentsuId == 14 || mentsuId == 20 ||
isYaochuhai(mentsuId);
}
private MentsuUtil() {
}
}
public class ShantensuUtil {
private const int NUM_HAI_ID = 34;
private const int NUM_MENTSU_ID = 55;
/*
public static int calculateShantensu(List<Hai> hais) {
int[] countVector = HaiUtil.haiListToCountVector(hais);
int chitoitsuShantensu = calculateChitoitsuShantensu(countVector);
// TODO: Handle Kokushimuso
return calculateShantensuInternal(
countVector, new int[NUM_HAI_ID], 4, 0, chitoitsuShantensu);
}
*/
public static int calculateShantensu(List<Int32> haiIds) {
int[] countVector = new int[NUM_HAI_ID];
for (int i = 0; i < haiIds.Count; i++) {
++countVector[haiIds[i]];
}
return calculateShantensuInternal(countVector, new int[NUM_HAI_ID], 4, 0, Int32.MaxValue);
}
private static int calculateChitoitsuShantensu(int[] currentVector) {
int numPairs = 0;
int numSingles = 0;
for (int haiId = 0; haiId < NUM_HAI_ID; haiId++) {
if (currentVector[haiId] >= 2) {
numPairs++;
} else if (currentVector[haiId] == 1) {
numSingles++;
}
}
int requiredPairs = 7 - numPairs;
if (numSingles >= requiredPairs) {
return requiredPairs - 1;
} else {
return numSingles + (requiredPairs - numSingles) * 2 - 1;
}
}
private static int calculateShantensuInternal(
int[] currentVector, int[] targetVector, int leftMentsu, int minMentsuId,
int foundMinShantensu) {
int minShantensu;
if (leftMentsu == 0) {
// Add janto.
minShantensu = foundMinShantensu;
for (int haiId = 0; haiId < NUM_HAI_ID; haiId++) {
targetVector[haiId] += 2;
if (isValidTargetVector(targetVector)) {
int shantensu = calculateShantensuLowerBound(currentVector, targetVector);
minShantensu = Math.Min(shantensu, minShantensu);
}
targetVector[haiId] -= 2;
}
return minShantensu;
}
minShantensu = foundMinShantensu;
for (int mentsuId = minMentsuId; mentsuId < NUM_MENTSU_ID; mentsuId++) {
MentsuUtil.addMentsu(targetVector, mentsuId);
int lowerBound = calculateShantensuLowerBound(currentVector, targetVector);
if (isValidTargetVector(targetVector) && lowerBound < foundMinShantensu) {
int shantensu = calculateShantensuInternal(
currentVector, targetVector, leftMentsu - 1, mentsuId, minShantensu);
minShantensu = Math.Min(shantensu, minShantensu);
}
MentsuUtil.removeMentsu(targetVector, mentsuId);
}
return minShantensu;
}
private static int calculateShantensuLowerBound(int[] currentVector, int[] targetVector) {
int count = 0;
for (int haiId = 0; haiId < NUM_HAI_ID; haiId++) {
if (targetVector[haiId] > currentVector[haiId]) {
count += targetVector[haiId] - currentVector[haiId];
}
}
return count - 1;
}
private static bool isValidTargetVector(int[] targetVector) {
for (int haiId = 0; haiId < NUM_HAI_ID; haiId++) {
if (targetVector[haiId] > 4) {
return false;
}
}
return true;
}
/*
public static int calculateShantensuWithinRemainingHais(List<Hai> hais, int[] remainingVector) {
int[] countVector = HaiUtil.haiListToCountVector(hais);
int chitoitsuShantensu = calculateChitoitsuShantensuWithinRemainingHais(
countVector, remainingVector);
// TODO: Handle Kokushimuso
return calculateShantensuWithinRemainingHaisInternal(
countVector, new int[NUM_HAI_ID], remainingVector, 4, 0, chitoitsuShantensu);
}
*/
private static int calculateChitoitsuShantensuWithinRemainingHais(
int[] currentVector, int[] remainingVector) {
int numPairs = 0;
int numEffectiveSingles = 0;
for (int haiId = 0; haiId < NUM_HAI_ID; haiId++) {
if (currentVector[haiId] >= 2) {
numPairs++;
} else if (currentVector[haiId] == 1 && remainingVector[haiId] >= 1) {
numEffectiveSingles++;
}
}
int requiredPairs = 7 - numPairs;
if (numEffectiveSingles >= requiredPairs) {
return requiredPairs - 1;
} else {
return numEffectiveSingles + (requiredPairs - numEffectiveSingles) * 2 - 1;
}
}
private static int calculateShantensuWithinRemainingHaisInternal(
int[] currentVector, int[] targetVector, int[] remainingVector, int leftMentsu,
int minMentsuId, int foundMinShantensu) {
int minShantensu;
if (leftMentsu == 0) {
// Add janto.
minShantensu = foundMinShantensu;
for (int haiId = 0; haiId < NUM_HAI_ID; haiId++) {
targetVector[haiId] += 2;
if (isValidTargetVectorWithinRemainingHais(
targetVector, currentVector, remainingVector)) {
int shantensu = calculateShantensuLowerBound(currentVector, targetVector);
minShantensu = Math.Min(shantensu, minShantensu);
}
targetVector[haiId] -= 2;
}
return minShantensu;
}
minShantensu = foundMinShantensu;
for (int mentsuId = minMentsuId; mentsuId < NUM_MENTSU_ID; mentsuId++) {
MentsuUtil.addMentsu(targetVector, mentsuId);
int lowerBound = calculateShantensuLowerBound(currentVector, targetVector);
if (isValidTargetVectorWithinRemainingHais(
targetVector, currentVector, remainingVector) &&
lowerBound < foundMinShantensu) {
int shantensu = calculateShantensuWithinRemainingHaisInternal(
currentVector, targetVector, remainingVector, leftMentsu - 1, mentsuId,
minShantensu);
minShantensu = Math.Min(shantensu, minShantensu);
}
MentsuUtil.removeMentsu(targetVector, mentsuId);
}
return minShantensu;
}
private static bool isValidTargetVectorWithinRemainingHais(
int[] targetVector, int[] currentVector, int[] remainingVector) {
for (int haiId = 0; haiId < NUM_HAI_ID; haiId++) {
if (targetVector[haiId] > 4) {
return false;
}
if (targetVector[haiId] - currentVector[haiId] > remainingVector[haiId]) {
return false;
}
}
return true;
}
private ShantensuUtil() {
}
}
public static class ShantenAnalysis
{
public static void Main()
{
using (StreamReader sr = new StreamReader("shanten_benchmark_data.num.txt")) {
while (true) {
string line = sr.ReadLine();
if (line == null) break;
string[] input = line.Split(' ');
List<Int32> haiIds = new List<Int32>();
for (int i = 0; i < input.Length - 1; i++) haiIds.Add(Int32.Parse(input[i]));
int expected = Int32.Parse(input[input.Length - 1]);
int actual = ShantensuUtil.calculateShantensu(haiIds);
if (actual != expected) throw new Exception(line + " --> " + actual);
}
}
}
}
Raw
ShantenAnalysis.java
import org.ymatsux.mjai.client.*;
import java.io.*;
import java.util.*;
import static org.ymatsux.mjai.client.CommonConsts.NUM_HAI_ID;
public class ShantenAnalysis {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(
new FileReader("shanten_benchmark_data.num.txt"));
while (true) {
String line = reader.readLine();
if (line == null) break;
String[] input = line.split(" ");
ArrayList<Hai> hais = new ArrayList<Hai>();
for (int i = 0; i < input.length - 1; i++) {
hais.add(Hai.ofId(Integer.parseInt(input[i])));
}
int expected = Integer.parseInt(input[input.length - 1]);
int actual = ShantensuUtil.calculateShantensu(hais);
if (actual != expected) throw new RuntimeException(line + " --> " + actual);
}
}
}
/*
--- a/src/org/ymatsux/mjai/client/ShantensuUtil.java
+++ b/src/org/ymatsux/mjai/client/ShantensuUtil.java
@@ -9,7 +9,7 @@
public static int calculateShantensu(List<Hai> hais) {
int[] countVector = HaiUtil.haiListToCountVector(hais);
- int chitoitsuShantensu = calculateChitoitsuShantensu(countVector);
+ int chitoitsuShantensu = Integer.MAX_VALUE;
// TODO: Handle Kokushimuso
return calculateShantensuInternal(
countVector, new int[NUM_HAI_ID], 4, 0, chitoitsuShantensu);
*/
Raw
ymatsux_shanten_analysis.py
NUM_PIDS = 34
class ShantenAnalyzer(object):
def __init__(self):
self.__mentsus = []
for pid in xrange(NUM_PIDS):
self.__mentsus.append((pid, pid, pid))
for t in xrange(3):
for n in xrange(7):
pid = t * 9 + n
self.__mentsus.append((pid, pid + 1, pid + 2))
def calculate_shantensu(self, pids):
return self.calculate_shantensu_internal(
self.pids_to_count_vector(pids), [0] * NUM_PIDS, 4, 0, 99)
def pids_to_count_vector(self, pids):
vector = [0] * NUM_PIDS
for pid in pids: vector[pid] += 1
return vector
def calculate_shantensu_internal(self, current_vector, target_vector,
left_mentsus, min_mentsu_id, found_min_shantensu):
min_shantensu = found_min_shantensu
if left_mentsus == 0:
for pid in xrange(NUM_PIDS):
target_vector[pid] += 2
if self.is_valid_target_vector(target_vector):
shantensu = self.calculate_shantensu_lowerbound(current_vector, target_vector)
min_shantensu = min(shantensu, min_shantensu)
target_vector[pid] -= 2
else:
for mentsu_id in xrange(min_mentsu_id, len(self.__mentsus)):
self.add_mentsu(target_vector, mentsu_id)
lowerbound = self.calculate_shantensu_lowerbound(current_vector, target_vector)
if self.is_valid_target_vector(target_vector) and lowerbound < found_min_shantensu:
shantensu = self.calculate_shantensu_internal(
current_vector, target_vector, left_mentsus - 1, mentsu_id, min_shantensu)
min_shantensu = min(shantensu, min_shantensu)
self.remove_mentsu(target_vector, mentsu_id)
return min_shantensu
def calculate_shantensu_lowerbound(self, current_vector, target_vector):
count = 0
for pid in xrange(NUM_PIDS):
if target_vector[pid] > current_vector[pid]:
count += target_vector[pid] - current_vector[pid]
return count - 1
def is_valid_target_vector(self, target_vector):
return all(count <= 4 for count in target_vector)
def add_mentsu(self, target_vector, mentsu_id):
for pid in self.__mentsus[mentsu_id]:
target_vector[pid] += 1
def remove_mentsu(self, target_vector, mentsu_id):
for pid in self.__mentsus[mentsu_id]:
target_vector[pid] -= 1
with open("shanten_benchmark_data.num.txt") as fp:
analyzer = ShantenAnalyzer()
for line in fp:
pids = [int(s) for s in line.split()]
expected_shantensu = pids.pop()
actual_shantensu = analyzer.calculate_shantensu(pids)
assert actual_shantensu == expected_shantensu
Raw
yuizumi_shanten_analysis.py
NUM_TILES = 34 # m, p, s, ESWNPFC
NUM_MELDS = 55
CHOW_PIDS = range(0, 7) + range(9, 16) + range(18, 25)
def compute_shantensu_i(melds_left, meld_id, hand_vec, temp_vec, accum, upper):
if melds_left == 0:
min_delta = 2
for pid in xrange(NUM_TILES):
if hand_vec[pid] >= temp_vec[pid] + 2:
min_delta = 0
break
elif hand_vec[pid] == temp_vec[pid] + 1:
min_delta = 1
accum += min_delta
return min(accum, upper)
else:
# Pungs.
while meld_id < NUM_TILES:
# temp_vec[meld_id] is always zero here. Note that no chows have
# been considered yet.
accum1 = accum if (hand_vec[meld_id] >= 3) else (accum + 3 - hand_vec[meld_id])
if accum1 < upper:
temp_vec[meld_id] = 3
upper = compute_shantensu_i(melds_left - 1, meld_id + 1, hand_vec, temp_vec,
accum1, upper)
temp_vec[meld_id] = 0
meld_id += 1
# Chows.
while meld_id < NUM_MELDS:
pid = CHOW_PIDS[meld_id - NUM_TILES]
if temp_vec[pid] < 4 and temp_vec[pid + 1] < 4 and temp_vec[pid + 2] < 4:
accum1 = accum
if hand_vec[pid ] <= temp_vec[pid ]: accum1 += 1
if hand_vec[pid + 1] <= temp_vec[pid + 1]: accum1 += 1
if hand_vec[pid + 2] <= temp_vec[pid + 2]: accum1 += 1
if accum1 < upper:
temp_vec[pid] += 1 ; temp_vec[pid + 1] += 1 ; temp_vec[pid + 2] += 1
upper = compute_shantensu_i(melds_left - 1, meld_id, hand_vec, temp_vec,
accum1, upper)
temp_vec[pid] -= 1 ; temp_vec[pid + 1] -= 1 ; temp_vec[pid + 2] -= 1
meld_id += 1
return upper
def compute_shantensu(pids):
hand_vec = [0] * NUM_TILES
for pid in pids: hand_vec[pid] += 1
return compute_shantensu_i(4, 0, hand_vec, [0] * NUM_TILES, -1, 99)
with open("shanten_benchmark_data.num.txt") as fp:
for line in fp:
pids = [int(s) for s in line.split()]
expected_shantensu = pids.pop()
actual_shantensu = compute_shantensu(pids)
assert actual_shantensu == expected_shantensu
Raw
yuizumi_shanten_analysis.rb
NUM_TILES = 34 # m, p, s, ESWNPFC
NUM_MELDS = 55
CHOW_PIDS = (0..6).to_a + (9..15).to_a + (18..24).to_a
def compute_shantensu_i(melds_left, meld_id, hand_vec, temp_vec, accum, upper)
if melds_left == 0
min_delta = 2
for pid in 0...NUM_TILES
if hand_vec[pid] >= temp_vec[pid] + 2
min_delta = 0
break
elsif hand_vec[pid] == temp_vec[pid] + 1
min_delta = 1
end
end
accum += min_delta
return accum < upper ? accum : upper
else
# Pungs.
while meld_id < NUM_TILES
# temp_vec[meld_id] is always zero here. Note that no chows have
# been considered yet.
accum1 = (hand_vec[meld_id] >= 3) ? accum : (accum + 3 - hand_vec[meld_id])
if accum1 < upper
temp_vec[meld_id] = 3
upper = compute_shantensu_i(melds_left - 1, meld_id + 1, hand_vec, temp_vec,
accum1, upper)
temp_vec[meld_id] = 0
end
meld_id += 1
end
# Chows.
while meld_id < NUM_MELDS
pid = CHOW_PIDS[meld_id - NUM_TILES]
if temp_vec[pid] < 4 && temp_vec[pid + 1] < 4 && temp_vec[pid + 2] < 4
accum1 = accum
accum1 += 1 if hand_vec[pid ] <= temp_vec[pid ]
accum1 += 1 if hand_vec[pid + 1] <= temp_vec[pid + 1]
accum1 += 1 if hand_vec[pid + 2] <= temp_vec[pid + 2]
if accum1 < upper
temp_vec[pid] += 1 ; temp_vec[pid + 1] += 1 ; temp_vec[pid + 2] += 1
upper = compute_shantensu_i(melds_left - 1, meld_id, hand_vec, temp_vec,
accum1, upper)
temp_vec[pid] -= 1 ; temp_vec[pid + 1] -= 1 ; temp_vec[pid + 2] -= 1
end
end
meld_id += 1
end
return upper
end
end
def compute_shantensu(pids)
hand_vec = [0] * NUM_TILES
pids.each { |pid| hand_vec[pid] += 1 }
return compute_shantensu_i(4, 0, hand_vec, [0] * NUM_TILES, -1, 99)
end
File.foreach("shanten_benchmark_data.num.txt") do |line|
line = line.chomp()
row = line.split(/ /)
expected_shanten = row[-1].to_i()
actual_shanten = compute_shantensu(row[0...-1].map { |s| s.to_i })
if expected_shanten != actual_shanten
raise("Shanten mismatch: %d != %d for %s" % [actual_shanten, expected_shanten, line])
end
end
Raw
YuizumiShantenAnalysis.cs
using System;
using System.Collections.Generic;
using System.IO;
public static class ShantenAnalysis
{
private const int NumTiles = 34; // m, p, s, ESWNPFC
private const int NumMelds = 55;
private static readonly int[] ChowPids = {
0, 1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 14, 15, 18, 19, 20, 21, 22, 23, 24
};
private static int ComputeShantensu(int meldsLeft, int meldId, int[] handVec, int[] tempVec,
int accum, int upperbound)
{
if (meldsLeft == 0) {
int delta = 2;
for (int pid = 0; pid < NumTiles; pid++) {
if (handVec[pid] >= tempVec[pid] + 2) {
delta = 0;
break;
} else if (handVec[pid] == tempVec[pid] + 1) {
delta = 1;
}
}
return Math.Min(accum + delta, upperbound);
} else {
// Pungs.
for (; meldId < NumTiles; meldId++) {
int accum1 = (handVec[meldId] >= 3) ? accum : (accum + 3 - handVec[meldId]);
if (accum1 < upperbound) {
tempVec[meldId] = 3;
upperbound = ComputeShantensu(meldsLeft - 1, meldId + 1, handVec, tempVec,
accum1, upperbound);
tempVec[meldId] = 0;
}
}
// Chows.
for (; meldId < NumMelds; meldId++) {
int pid = ChowPids[meldId - NumTiles];
if (tempVec[pid] == 4 || tempVec[pid + 1] == 4 || tempVec[pid + 2] == 4) {
continue;
}
int accum1 = accum;
if (handVec[pid ] <= tempVec[pid ]) ++accum1;
if (handVec[pid + 1] <= tempVec[pid + 1]) ++accum1;
if (handVec[pid + 2] <= tempVec[pid + 2]) ++accum1;
if (accum1 < upperbound) {
++tempVec[pid]; ++tempVec[pid + 1]; ++tempVec[pid + 2];
upperbound = ComputeShantensu(meldsLeft - 1, meldId, handVec, tempVec,
accum1, upperbound);
--tempVec[pid]; --tempVec[pid + 1]; --tempVec[pid + 2];
}
}
return upperbound;
}
}
private static int ComputeShantensu(List<Int32> pids)
{
int[] handVec = new int[NumTiles];
pids.ForEach(j => ++handVec[j]);
return ComputeShantensu(4, 0, handVec, new int[NumTiles], -1, Int32.MaxValue);
}
public static void Main()
{
using (StreamReader sr = new StreamReader("shanten_benchmark_data.num.txt")) {
while (true) {
string line = sr.ReadLine();
if (line == null) break;
string[] input = line.Split(' ');
List<Int32> pids = new List<Int32>();
for (int i = 0; i < input.Length - 1; i++) pids.Add(Int32.Parse(input[i]));
int expected = Int32.Parse(input[input.Length - 1]);
int actual = ComputeShantensu(pids);
if (actual != expected) throw new Exception(line + " --> " + actual);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment








ApplySandwichStrip

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


--- a PPN by Garber Painting Akron. With Image Size Reduction included!

Fetched URL: https://gist.github.com/yuizumi/547960ae83c9b3059b07

Alternative Proxies:

Alternative Proxy

pFad Proxy

pFad v3 Proxy

pFad v4 Proxy