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);
            }
        }
    }
}

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);
*/

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

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

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

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);
            }
        }
    }
}