понедельник, 28 октября 2013 г.

codingame contest: "Scrabble" task

Task
When playing Scrabble©, each player draws 7 letters and must find a word that scores the most points using these letters.

A player doesn't necessarily have to make a 7-letter word; the word can be shorter. The only constraint is that the word must be made using the 7 letters which the player has drawn.

For example, with the letters  etaenhs, some possible words are: ethanehates,saneant.

LETTER SCORING:
In Scrabble©, each letter is weighted with a score depending on how difficult it is to place that letter in a word. You will see below a table showing the points corresponding to each letter:
LettersPoints
      e, a, i, o, n, r, t, l, s, u   1
      d, g   2
      b, c, m, p   3
      f, h, v, w, y   4
      k   5
      j, x   8
      q, z   10
The word banjo earns 3 + 1 + 1 + 8 + 1 = 14 points.

A dictionary of authorized words is provided as input for the program. The program must find the word in the dictionary which wins the most points for the seven given letters. If two words win the same number of points, then the word which appears first in the order of the given dictionary should be chosen.
All words will only be composed of alphabetical characters in lower case. There will always be at least one possible word.
INPUT:
Line 1: The number N of words in the dictionary
N following lines: The words in the dictionary. One word per line.
Last line: The 7 letters available.
OUTPUT:
The word that scores the most points using the available letters (1 to 7 letters). The word must belong to the dictionnary. There is always a solution.
CONSTRAINTS:
0 < N < 100000
Words in the dictionary have a maximum length of 30 characters.
EXAMPLE:
Input
5
because
first
these
could
which
hicquwh
Output
which



   class Task1
    {
        public int N { get; set; }
        List board = new List();
        public string Letters { get; set; }

        public void Run()
        {
            using (new ConsoleManager("Test_1_input.txt", "Test_1_outputMy.txt"))
            {
                GetData();
                var filtered = board.Where(w => FromLetters(w, Letters.ToCharArray())).ToList();
                var scores = filtered.Select(w => Score(w)).ToList();
                var max = scores.Max();
                var index = scores.FindIndex(score=>score==max);
                if (index >= 0)
                {
                    var word = filtered[index];
                    Console.WriteLine(word);
                }
            }
        }

        bool FromLetters(string word, char[] letters)
        {
            bool yes = true;
            var list = letters.ToList();
            for (int i = 0; i < word.Length; i++)
            {
                var index = list.FindIndex(w=>w==word[i]);
                if (index < 0) { yes = false; break; }
                list.RemoveAt(index);
            }

            
            return yes;
        }

        int Score(string word)
        {
            int score = 0;
            var arr = new String(word.ToCharArray().Distinct().ToArray());
            for (int i = 0; i < arr.Length; i++)
            {
                if ("eaionrtlsu".Contains(word[i])) score++;
                else if ("dg".Contains(word[i])) score+=2;
                else if ("bcmp".Contains(word[i])) score += 3;
                else if ("fhvwy".Contains(word[i])) score += 4;
                else if ("k".Contains(word[i])) score += 5;
                else if ("jx".Contains(word[i])) score += 8;
                else if ("qz".Contains(word[i])) score += 10; 
                 
            }
            return score;
        }

        void GetData()
        {
            string line = Console.ReadLine();
            N = Convert.ToInt32(line);
            for (int i = 0; i < N; i++)
            {
                line = Console.ReadLine();
                board.Add(line);
            }
            Letters = Console.ReadLine();
            Debug.Print("N =" + N + "; " + board.Print());
            Debug.Print("Letters =" + N + "; " + Letters);
        }
    }


Комментариев нет :

Отправить комментарий