UVA - 10393 - The One-Handed Typist 

This article will explain my thought process to solve a problem called The One-Handed Typist (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Hash Table, Sorting

Objective 

Given:

  1. Total unusable fingers.

  2. List of unusable fingers.

  3. Total words.

  4. List of words.

We want to:

  1. Find the longest typeable words.

  2. Filter unique typeable words.

  3. Order typeable words alphabetically.

Glossary 

  1. Hash Table — A data structure used to insert, look up, and remove key-value pairs quickly.

  2. Sorting — Rearrangement of a given array or list of elements according to a comparison operator on the elements.

Observation 

Each finger is assigned with a list of letters. Since we are given a list of unusable fingers, we can exclude those fingers to retrieve the list of typeable letters. A word is typeable if it only consists of the typeable letters. After we know the typeable words, we can calculate the maximum length and retrieve every words with the same length as the maximum. After this, we just need to exclude the duplicate and order it alphabetically.

Algorithm 

The fingers-letters assignment and the typeable letters can be stored in a hash table for simplicity. The unique filter and alphabetical order can be handled by java’s built-in method.

The time complexity of this problem is O({total words} * log2({total words})) or O(10^4).

Implementation 

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

/**
 * 10393 - The One-Handed Typist
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1334
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        while (in.hasNextInt()) {
            final Input input = new Input();
            input.totalNonUsableFingers = in.nextInt();
            input.totalWords = in.nextInt();
            input.nonUsableFingers = new int[input.totalNonUsableFingers];
            for (int i = 0; i < input.nonUsableFingers.length; i++) {
                input.nonUsableFingers[i] = in.nextInt();
            }
            input.words = new String[input.totalWords];
            in.nextLine();
            for (int i = 0; i < input.words.length; i++) {
                input.words[i] = in.nextLine();
            }

            final Output output = process.process(input);
            out.println(output.totalLongestTypeableWords);
            for (final String word : output.longestTypeableWords) {
                out.println(word);
            }
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int totalNonUsableFingers;
    public int totalWords;
    public int[] nonUsableFingers;
    public String[] words;
}

class Output {
    public int totalLongestTypeableWords;
    public String[] longestTypeableWords;
}

class Process {
    private static final String[] lettersPerFingers = new String[]{
            "",
            "qaz",
            "wsx",
            "edc",
            "rfvtgb",
            " ",
            " ",
            "yhnujm",
            "ik",
            "ol.",
            "p;/"
    };

    public Output process(final Input input) {
        final Set<Integer> unusableFingers = new HashSet<>(10);
        for (final int finger : input.nonUsableFingers) {
            unusableFingers.add(finger);
        }

        final Set<Character> typeableLetters = new HashSet<>(32);
        for (int finger = 1; finger <= 10; finger++) {
            if (unusableFingers.contains(finger)) continue;

            for (final char letter : lettersPerFingers[finger].toCharArray()) {
                typeableLetters.add(letter);
            }
        }

        final List<String> typeableWords = new LinkedList<>();
        int maxLength = 0;
        for (final String word : input.words) {
            if (word.length() < maxLength) continue;
            if (!isTypeable(typeableLetters, word)) continue;

            if (word.length() > maxLength) {
                maxLength = word.length();
                typeableWords.clear();
                typeableWords.add(word);
            } else {
                typeableWords.add(word);
            }
        }

        final Output output = new Output();
        output.longestTypeableWords = typeableWords.stream().distinct().sorted().toArray(String[]::new);
        output.totalLongestTypeableWords = output.longestTypeableWords.length;
        return output;
    }

    private boolean isTypeable(final Set<Character> typeableLetters, final String word) {
        for (final char letter : word.toCharArray()) {
            if (!typeableLetters.contains(letter)) return false;
        }
        return true;
    }
}


Powered by Docmost