Yahtzee. Есть ли ошибка в исходных данных

[IvanGrozniy]

Есть задача:

The game of Yahtzee involves five dice, which are thrown in 13 rounds. A score card
contains 13 categories. Each round may be scored in a category of the player’s choosing,
but each category may be scored only once in the game. The 13 categories are scored
as follows:
• ones - sum of all ones thrown
• twos - sum of all twos thrown
• threes - sum of all threes thrown
• fours - sum of all fours thrown
• fives - sum of all fives thrown
• sixes - sum of all sixes thrown
• chance - sum of all dice
• three of a kind - sum of all dice, provided at least three have same value
• four of a kind - sum of all dice, provided at least four have same value
• five of a kind - 50 points, provided all five dice have same value
• short straight - 25 points, provided four of the dice form a sequence (that is,
1,2,3,4 or 2,3,4,5 or 3,4,5,6)
• long straight - 35 points, provided all dice form a sequence (1,2,3,4,5 or 2,3,4,5,6)
• full house - 40 points, provided three of the dice are equal and the other two
dice are also equal. (for example, 2,2,5,5,5)
Each of the last six categories may be scored as 0 if the criteria are not met.
The score for the game is the sum of all 13 categories plus a bonus of 35 points if the
sum of the first six categories is 63 or greater.
Your job is to compute the best possible score for a sequence of rounds.
Input
Each line of input contains five integers between 1 and 6, indicating the values of the
five dice thrown in each round. There are 13 such lines for each game, and there may
be any number of games in the input data.
Output
Your output should consist of a single line for each game containing 15 numbers: the
score in each category (in the order given), the bonus score (0 or 35), and the total
score. If there is more than categorization that yields the same total score, any one will
do.

Серия исходных раундов такова:

1 1 1 1 1
6 6 6 6 6
6 6 6 1 1
1 1 1 2 2
1 1 1 2 3
1 2 3 4 5
1 2 3 4 6
6 1 2 6 6
1 4 5 5 5
5 5 5 5 6
4 4 4 5 6
3 1 3 6 3
2 2 2 4 6

Ответ должен получиться такой

3 6 9 12 15 30 21 20 26 50 25 35 40 35 327

Написал программу не получается такой ответ. Начинаю раскладывать каждый раунд на бумажке.
Первы раунд - 11111 - five of a kind, 50 очков
Второй раунд - 66666 - sixes, 30 очков
Третий раунд - 66611 - full house, 40 очков
Четвертый раунд - 11122 - по логике должно получиться chance и сумма всех чисел должна быть равна 7 (можно также three of a kind, что тоже не подходит). Но судя по ответу из задачи chance почему-то равен 21.
Никак не могу понять в чем проблема.

[venco]

Очевидно, выгоднее в chance записать 6 1 2 6 6.
А 11123 - в ones.

[IvanGrozniy]

Очевидно, выгоднее в chance записать 6 1 2 6 6.
А 11123 - в ones.

Я почему-то думал, что решение надо принимать в каждом раунде не знаю последующих раундов, как в игре. Вы думаете, что надо все варианты перебрать и искать максимум для учитывая все раунды?
Дело в том, что я как раз первый раз решил методом перебора всех вариантов для выбора максимума, но программа "зависла" - слишком много вариантов. Может как-то оптимизировать перебор можно?

[venco]

Я почему-то думал, что решение надо принимать в каждом раунде не знаю последующих раундов, как в игре. Вы думаете, что надо все варианты перебрать и искать максимум для учитывая все раунды?

Your job is to compute the best possible score for a sequence of rounds.

Дело в том, что я как раз первый раз решил методом перебора всех вариантов для выбора максимума, но программа "зависла" - слишком много вариантов. Может как-то оптимизировать перебор можно?

В этом и состоит задача - суметь перебрать за отведённое время.
Используйте метод Dynamic Programming.
Данная задача, если не ошибаюсь, решается за время порядка 13*2^13*64.

[IvanGrozniy]

Не могу понять в чём секрет Написал программку, которая просто максимум считает без бонуса и без вывода очков по каждой категории. Работает она долго, ждал несколько минут, затем зашел в режим отладки - считает в глубине 12-го элемента, то есть на 12-ом рекурсионном вызове.
Может кто подскажет, как побыстрей можно?

Code: Select all

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Collections.Specialized;
namespace __8_8
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] lines = File.ReadAllLines("input.txt");
            string[] input = new string[13];
            int i;
            for (i = 0; i <lines> 0))
                {
                    Calc(input);
                }
                input[i % 13] = lines[i];
            }
            if ((i % 13 == 0) && (i > 0))
            {
                Calc(input);
            }
            Console.ReadKey();
        }
        private static void Calc(string[] lines)
        {
            List<int> arrDigits = new List<int>();
            string[] arr;
            int[] digs = new int[5];
            for (int i = 0; i < lines.Length; i++)
            {
                digs = new int[5];
                arr = lines[i].Split(' ');
                for (int j = 0; j < 5; j++)
                    digs[j] = int.Parse(arr[j]);
                arrDigits.Add(digs);
            }
            string record = string.Empty;
            
            List<int> listCategories = new List<int>();
            for (int i = 0; i < 13; i++)
                listCategories.Add(i);
            string sequence = string.Empty;
            int score = GetMaxSum(arrDigits, listCategories, 0);
            /*
            int bonus = 0;
            int sum = 0;
            for (int i = 0; i < 13; i++)
            {
                if (i <6>= 63)
                bonus = 35;
            else
                bonus = 0;
            Console.WriteLine("{0} {1} {2}", record, bonus, sum);
             */
            Console.WriteLine("{0} {1}", sequence, score);
        }
        private static int GetMaxSum(List<int> arrDigits, List<int> categories, int sum)
        {
            if (arrDigits.Count == 0)
                return sum;
            int max = 0;
            List<int> maxs = new List<int>();
            for (int i = 0; i < arrDigits.Count; i++)
            {
                int[] digs = arrDigits[0];
                arrDigits.Remove(digs);
                for (int j = 0; j < categories.Count;  j++)
                {
                    int k = CalcLine(digs, categories[j]);
                    int currCat = categories[j];
                    //Don't count last six categories. Winning a big chunk of time here
                    if (((k == 0) && (categories[j] <7> 0))
                    {
                        categories.Remove(currCat);
                        k = GetMaxSum(arrDigits, categories, sum + k);
                        int[] maxArr = new int[2];
                        maxArr[0] = currCat;
                        maxArr[1] = k;
                        maxs.Add(maxArr);  //j - currCat. k - summ
                        categories.Insert(j, currCat);
                    }

                }
                arrDigits.Add(digs);
                for (int u = 0; u < maxs.Count; u++)
                {
                    if (max < maxs[u][1])
                    {
                        max = maxs[u][1];
                        //seq += " " + sequences[maxs[i][0]].ToString();
                    }
                }
            }

            return sum + max;
        }
        private static int CalcLine(int[] digs, int categoryNum)
        {
            int res = 0;
            switch (categoryNum)
            {
                case 0:
                case 1:
                case 2:
                case 3:
                case 4:
                case 5:
                    res = CalcN(digs, categoryNum + 1);
                    break;
                case 6:
                    res = CalcSum(digs);
                    break;
                case 7:
                    res = CalcNKind(digs, 3);
                    break;
                case 8:
                    res = CalcNKind(digs, 4);
                    break;
                case 9:
                    res = CalcNKind(digs, 5);
                    break;
                case 10:
                    res = CalcStraight(digs, 4);
                    break;
                case 11:
                    res = CalcStraight(digs, 5);
                    break;
                case 12:
                    res = CalcFullHouse(digs);
                    break;
            }
            return res;
        }
        private static int CalcN(int[] digs, int dig)
        {
            int sum = 0;
            for (int i = 0; i < 5; i++)
                if (digs[i] == dig)
                    sum += dig;
            return sum;
        }
        private static int CalcSum(int[] digs)
        {
            int sum = 0;
            for (int i = 0; i < 5; i++)
                sum += digs[i];
            return sum;
        }
        private static int CalcNKind(int[] digs, int kind)
        {
            int[] dices = new int[6];
            for (int i = 0; i < 6; i++)
                dices[i] = 0;
            for (int i = 0; i < 5; i++)
                dices[digs[i] - 1]++;
            for (int i = 0; i <6>= kind)
                {
                    if (kind < 5)
                        return CalcSum(digs);
                    else
                        return 50;

                }
            }
            return 0;
        }
        private static int CalcStraight(int[] digs, int howLong)
        {
            Array.Sort(digs);
            int count = 0;
            for (int i = 0; i < 2; i++)
            {
                count = 0;
                int start = digs[i];
                for (int j = i; j <5>= howLong) && (howLong == 4))
                    return 25;
                if (count == 5)
                    break;
            }
            if ((count == howLong) && (howLong == 5))
                return 35;
            if ((count >= howLong) && (howLong == 4))
                return 25;
            return 0;
        }
        private static int CalcFullHouse(int[] digs)
        {
            Dictionary<int> dic = new Dictionary<int>();
            for (int i = 0; i < 5; i++)
            {
                if (!dic.ContainsKey(digs[i]))
                    dic.Add(digs[i], 0);
                dic[digs[i]]++;
            }
            if (dic.Count == 2)
            {
                foreach (int i in dic.Keys)
                {
                    if ((dic[i] != 3) && (dic[i] != 2))
                        return 0;
                }
            }
            else
            {
                return 0;
            }
            return 40;
        }
    }
}

[venco]

Изучите метод Dynamic Programming.
Он очень часто нужен для решения подобных задач.
Например, вот так:

Code: Select all

#include <algorithm>
#include <iostream>
using namespace std;

struct Roll
{
    int dice[5];
    int sum_1_6;
    int score[13];

    void read();
};

Roll rolls[13];

void Roll::read()
{
    for ( int j = 0; j <5>> dice[j];
    sort(dice, dice+5);
    int sum = accumulate(dice, dice+5, 0);

    // init possible scores
    fill_n(score, 13, 0);
    sum_1_6 = 0;
    score[6] = sum; // Chance
    for ( int d = 1; d <6>= 3 ) { // Three of a kind
            score[7] = sum;
            if ( dice[0] != d && dice[1] == dice[0] ||
                 dice[4] != d && dice[3] == dice[4] ) // Full house
                score[12] = 40;
        }
        if ( c >= 4 ) // Four of a kind
            score[8] = sum;
        if ( c >= 5 ) // Five of a kind
            score[9] = 50;
    }
    // Straights
    int len = 0, last_d = 0;
    for ( int i = 0; i <5>= 4 ) // Short straight
                score[10] = 25;
            if ( len >= 5 ) // Long straight
                score[11] = 35;
        }
        else if ( dice[i] > last_d + 1 ) {
            last_d = dice[i];
            len = 1;
        }
    }
}

pair<int> dp_cache[14][1<<13][64];

const pair<int>& best_roll(int cat, int rxx, int sum_1_6)
{
    pair<int>& best = dp_cache[cat][rxx][sum_1_6];
    if ( best.first <0>= 63)? 35: 0;
        for ( int r = 0; r < 13; ++r ) {
            if ( rxx & (1<<r) ) continue;
            pair<int> score(rolls[r].score[cat], r);
            int new_sum_1_6 = min(63, sum_1_6+rolls[r].sum_1_6);
            score.first += best_roll(cat+1, rxx|(1<<r> best )
                best = score;
        }
    }
    return best;
}

void best_game()
{
    for ( int r = 0; r < 13; ++r ) {
        rolls[r].read();
    }
    memset(dp_cache, -1, sizeof(dp_cache));
    int rxx = 0, sum_1_6 = 0;
    for ( int cat = 0; cat < 13; ++cat ) {
        pair<int> best = best_roll(cat, rxx, sum_1_6);
        rxx |= 1<<best.second;
        sum_1_6 = min(63, sum_1_6+rolls[best.second].sum_1_6);
        cout << best.first-best_roll(cat+1, rxx, sum_1_6).first << ' ';
    }
    cout << best_roll(13, rxx, sum_1_6).first << ' '
         << best_roll(0, 0, 0).first << endl;
}

[IvanGrozniy]

Изучите метод Dynamic Programming.
Он очень часто нужен для решения подобных задач.
Например, вот так:

Спасибо за решение, буду разбираться.
По поводу Dynamic Programming: данная задачка из второй главы Data Sctuctures книги Programming Challenges. В этой же книги есть 11-ая глава, которая так и называется Dynamic Programming. Я ,конечно же, буду изучать данную главу, но вот как-то подозрительно, что решение требует Dynamic Programming из 11-ой главы.

[venco]

К сожалению, форум съел по нескольку символов перед почти каждым знаком > (больше), так что получился бред.

[IvanGrozniy]

К сожалению, форум съел по нескольку символов перед почти каждым знаком > (больше), так что получился бред.

Ничего страшного. Для меня главное идею понять.