ACSL Intermediate Scrabble Problem

This article discusses and contains the Python code solution for the American Computer Science League (ACSL) Intermediate Division 2013-2014 Contest 1 Programming Problem Scrabble.

ACSL Intermediate 2013-2014 Contest 1 Scrabble problem with solution

Scrabble

The ACSL Intermediate Scrabble problem was the programming problem in ACSL Intermediate Division 2013-2014 Contest 1.

First, read the Scrabble problem. Make sure you understand the problem description. Read it many times, if necessary. Then, write your algorithm on paper before coding anything. For your algorithm, you can write either pseudocode or a flowchart.

If you have worked on the Junior division version of Scrabble, this is different in that the counting process starts where the last letter ends. That makes it a little more tricky.

Algorithm

We will create separate lists of squares for double letters, triple letters, double words and triple words, while making sure that the previous list's letters are not included. We will also create a cumulative list of squares that are used.

After that, we will run through the letters of the word and count the score for each test case.

Now for a detailed algorithm.

Algorithm for main function

1. Create a list double_letters of all squares with every other multiple of 3, from 3 through 40.
2. Create a list used_nums which contains all the squares from the previous squares.
3. Create a list triple_letters of all squares with multiples of 5, from 5 through 40.
4. In this list triple_letters, remove all instances of used_nums.
5. Add the content of triple_letters to used_nums.
6. Create a list double_words of all squares with multiples of 7, from 7 through 40.
7. In this list double_words, remove all instances of used_nums.
8. Add the content of double_words to used_nums.
9. Create a list triple_words of all squares with multiples of 8, from 8 through 40.
10. In this list triple_words, remove all instances of used_nums.
11. Add the content of triple_words to used_nums.
12. Read the first line of input and split the letters of the 4-letter word.
13. Read the next 5 lines which are of the format POSITION, DIRECTION and pass each of those lines to the scrabble() function, along with the lists.

Algorithm for scrabble() function

1. This function accepts the 4-letter word, position, direction and the lists created earlier.
2. Create a 2D tuple consisting of (letter, position) depending on whether the direction is horizontal or vertical.
3. If the direction is horizontal, the position increases by 1 for the next letter.
4. If the direction if vertical, the square below is increased by 10 for the next letter.
5. Initialize score to 0. This is the overall value of the word score.
6. Loop through each letter in the word.
7. Create a variable times_word to track whether the word falls on a double word or triple word or not at all. It is set to 1.
8. Find the score of the current letter in the loop created 2 steps back.
9. If the letter falls in a double letter or triple letter square, multiply the value accordingly.
10. If the letter falls in a double word, change times_word to 2, and if the letter falls in a triple word, change times_word to 3.
11. Add the points to score.
12. Multiply score with times_word and the value will change depending on whether it landed on a double word or triple word square.
13. That's it.

Sample Input

You can save this as a file intermediate_scrabble_1.in

J, A, V, A
1, V
2, H
6, V
12, H
21, H

This file has one word and 5 test cases.

Sample Output

You can save this as a file intermediate_scrabble_1.out

18
17
42
30
66

There are 5 output lines, one for each test case.

My Python solution

This is my working Python solution:

'''
ACSL Intermediate 2013-2014 Contest 1 SCRABBLE
Blog Post: https://aruljohn.com/blog/acsl-intermediate-scrabble/
'''

def scrabble(letters, position, direction, 
             double_letters, triple_letters,
             double_words, triple_words):
    score = 0
    # 1. Loop through all letters of this 4-letter word and
    #    find position of each letter, either [H]orizontally or [V]ertically
    word = []
    for letter in letters:
        word.append((letter, position))
        if direction == 'H':
            position += 1
        else:
            position += 10

    # 2. Next, start scoring each letter
    times_word = 1 # for double word or triple word
    for letter, position in word: # letter, point
        point = 0
        if letter in ('A', 'E'):
            point = 1
        elif letter in ('D', 'R'):
            point = 2
        elif letter in ('B', 'M'):
            point = 3
        elif letter in ('V', 'Y'):
            point = 4
        elif letter in ('J', 'X'):
            point = 8
        if position in double_letters:
            point *= 2
        elif position in triple_letters:
            point *= 3
        if position in double_words:
            times_word = 2
        elif position in triple_words:
            times_word = 3
        score += point
    score *= times_word

    return score

'''
INPUT
=====
J, A, V, A
1, V
2, H
6, V
12, H
21, H

OUTPUT
======
18
17
42
30
66

Running the Program
===================
$ diff <(cat intermediate_scrabble_1.in | python intermediate_scrabble.py) <(cat intermediate_scrabble_1.out)
'''
# Main function here
if __name__ == '__main__':
    # Mark the squares with double letters
    double_letters = [x for x in range(1, 41) if x % 3 == 0]
    double_letters = [x for i, x in enumerate(double_letters) if i % 2 == 0]
    used_nums = set(double_letters)

    # Mark the squares with triple letters
    triple_letters = [x for x in range(1, 41) if x % 5 == 0]
    triple_letters = sorted(list(set(triple_letters) - used_nums))
    used_nums.update(triple_letters)

    # Mark the squares with double words
    double_words = [x for x in range(1, 41) if x % 7 == 0]
    double_words = sorted(list(set(double_words) - used_nums))
    used_nums.update(double_words)

    # Mark the squares with triple words
    triple_words = [x for x in range(1, 41) if x % 8 == 0]
    triple_words = sorted(list(set(triple_words) - used_nums))
    used_nums.update(triple_words)

    # Read 6 lines of input and parse accordingly
    letters = input().split(', ')
    for _ in range(5):
        position, direction = input().split(', ')
        print(scrabble(letters, int(position), direction, 
                       double_letters, triple_letters,
                       double_words, triple_words
        ))

Method 1: How to run the program the regular way

The regular way to run this program is:

python intermediate_scrabble.py

And copy/paste the input lines and press ENTER or return.

J, A, V, A
1, V
2, H
6, V
12, H
21, H

Screenshot

$ python intermediate_scrabble.py 
J, A, V, A
1, V
2, H
6, V
12, H
21, H
18
17
42
30
66

Method 2: How to run the program using cat on the input file

On my Mac, I personally prefer running cat on the input file and pipe the output to the Python program.

cat intermediate_scrabble_1.in | python intermediate_scrabble.py

Screenshot

$ cat intermediate_scrabble_1.in | python intermediate_scrabble.py 
18
17
42
30
66

Compare this output with the contents of intermediate_scrabble_1.out. They should be identical.

Method 3: How to run the program using cat and verifying using diff

You can combine cat on the input file, pipe to the Python program, run cat on the output file and compare using diff. All in one line.

diff <(cat intermediate_scrabble_1.in | python intermediate_scrabble.py) <(cat intermediate_scrabble_1.out)

Screenshot

$ diff <(cat intermediate_scrabble_1.in | python intermediate_scrabble.py) <(cat intermediate_scrabble_1.out)

If your program is successful, you should get nothing.

If your test cases do not pass, you will see the corresponding output line[s] in the output.

Decoding the program

In the main function, I created lists for double_letters, triple_letters, double_word and triple_word. These lists are passed into the scrabble() function everytime it is called.

Note that after creating double_letters, we check the presence of letters already in used_nums by using Set operation A - B. Yup, the same set operation in Discrete Math.

What is present in A, but not in B.

The set used_nums is updated everytime one of these 3 lists is created.

Next, loop through all the test cases, and call the scrabble() function.

In the scrabble() function, we create word, a list of tuples with each letter and its position, based on whether the direction is horizontal [H] or vertical [V].

We then loop through every letter of the list of tuples word, compare against the rules we have (letter => point), and calculate the points for each, based on double or triple letter.

We also keep track of whether a double or triple word is encountered, with the times_word variable.

After the iteration for the word is done, we multiply the score with times_word to get the final score for that test case.

Useful Python code snippets

There are many code snippets that can be used in competitive programming contests. These are a few. We will use the Python shell to test these individual snippets.

List comprehension

If you do not know about list comprehension, you really have to start learning about it. It reduces simple for-loops to one liners, but with high efficiency.

When to use Set vs List, and Set to List and List to Set operations

You use a Python List for regular array work.

You use a Python Set when you want unique values, and do not really care about the order.

List uses .append() or .extend() to add new lists to itself.

Set uses .update() to add new lists or sets to itself.

set(LIST) is used to convert a list to a set.

list(SET) is used to convert a set to a list.

Set A - Set B

If you have two lists A and B and want to find all items in A which are not in B, and store the result in list C:

C = list(set(A) - set(B))

Use in list keyword instead of comparing individually

If letter equals to A or E, point = 1, you can do it this way:

if letter == 'A' or letter = 'E':
    point = 1

You can do it more efficiently like this:

if letter in ('A', 'E'):
    point = 1

Why use a tuple instead of a list?

Tuples occupy lesser memory space and can be faster than lists.

So, wherever possible and you do not have to update the value in a list, we use a tuple instead of a list.

Use the Python shell

Feel free to test all the individual keywords and functions in the Python shell.

Combine common code and DRY

Wherever possible, see if you can combine common code that repeats itself. DRY stands for don't repeat yourself. You can either use repeating code in a function with appropriate parameters. If you don't have time, or it's too late to make a clean fix, just leave it as it is, as long as it is working properly.

Conclusion

If there is anything you would like me to add to this article, feel free to comment below or contact me. Thanks.

Related Posts

If you have any questions, please contact me at arulbOsutkNiqlzziyties@gNqmaizl.bkcom. You can also post questions in our Facebook group. Thank you.