TopcoderArchiveVisit Topcoder
Archive
Archive
Algorithm problem

TouchScreenDialing

Problem statement, definition, constraints, and public examples.

Problem Statement

Your company is marketing a phone that allows input via a touch screen. The pressure sensitive screen sends coordinates to the processing device, which then determines which numbers have been input. In this problem, you are writing the code for the processing device. You will be given int[]s rows and cols specifying where the screen has been pressed. More precisely, the ith press occurred at row rows[i] and column cols[i] (both 0-indexed). You are also given a String[] screen containing the image the user sees as they dial. Each element of screen is a row of the image, and each character of a single row is in a different column. screen will be divided up into numerous regions. Two points of the screen are in the same region if you can get from one to the other using only horizontal or vertical steps that never cross an X character. For each of the numerals '0'-'9', there will be a region containing that numeral. A press that occurs anywhere in a region containing a numeral results in that number being dialed. A press that occurs in a region containing no numeral, or directly on an X character results in no dialing. Other than numerals and Xs, screen will also contain (quotes for clarity) '.' characters as fillers. Your method will return a String containing the numbers dialed by the user (see example 1 for further clarification).

Definition

Class:
TouchScreenDialing
Method:
getNumber
Parameters:
String[], int[], int[]
Returns:
String
Method signature:
String getNumber(String[] screen, int[] rows, int[] cols)
(be sure your method is public)

Constraints

  • screen will contain between 1 and 50 elements inclusive.
  • Each element of screen will contain between 1 and 50 characters inclusive.
  • Each element of screen will contain the same number of characters.
  • The characters in screen will all come from the following string (quotes for clarity): "0123456789.X".
  • Each digit (0-9) will occur exactly once in screen.
  • Each digit will be the only digit in its region.
  • rows will contain between 1 and 50 elements inclusive.
  • cols will contain the same number of elements as rows.
  • Each element of rows will be between 0 and N-1 inclusive, where N is the number of elements in screen.
  • Each element of cols will be between 0 and M-1 inclusive, where M is the number of characters in each element of screen.

Examples

  1. {"1X2X3",
 "XXXXX",
 "4X5X6",
 "XXXXX",
 "7X8X9",
 "XXXXX",
 "XX0XX"}
    {0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,
 3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,6,6,6}
    {0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
 0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4}
    Returns: "1234567890"
    As a test, the user has hit every spot on the screen beginning with the upper left corner, proceeding one row at a time.
  2. {"1........",
 "XXXXXXXX.",
 ".........",
 ".XXXXXXXX",
 ".........",
 ".........",
 "XXXXXXXXX",
 "2X3X4X5X6",
 "X7X8X9X0X"}
    {0,0,1,2,3,4,5,6,7,8}
    {0,8,8,8,8,8,8,8,8,8}
    Returns: "1111116"
    The 1 button is quite windy.
  3. {"1.....X.....2",
 "XXXXXX.XXXXXX",
 "3.....X.....4",
 "XXXXXX.XXXXXX",
 "5.....X.....6",
 "XXXXXX.XXXXXX",
 "7.....X.....8",
 "XXXXXX.XXXXXX",
 "9.....X.....0"}
    {0,1,2,3,4,5,6,7,8,8,7,6,5,4,3,2,1,0}
    {5,5,5,5,5,5,5,5,5,7,7,7,7,7,7,7,7,7}
    Returns: "1357908642"
  4. {"...................",
 ".XXXXX.XXXXX.XXXXX.",
 ".X...X.X...X.X...X.",
 ".X.1.X.X.2.X.X.3.X.",
 ".X...X.X...X.X...X.",
 ".XXXXX.XXXXX.XXXXX.",
 "...................",
 ".XXXXX.XXXXX.XXXXX.",
 ".X...X.X...X.X...X.",
 ".X.4.X.X.5.X.X.6.X.",
 ".X...X.X...X.X...X.",
 ".XXXXX.XXXXX.XXXXX.",
 "...................",
 ".XXXXX.XXXXX.XXXXX.",
 ".X...X.X...X.X...X.",
 ".X.7.X.X.8.X.X.9.X.",
 ".X...X.X...X.X...X.",
 ".XXXXX.XXXXX.XXXXX.",
 "...................",
 ".......XXXXX.......",
 ".......X...X.......",
 ".......X.0.X.......",
 ".......X...X.......",
 ".......XXXXX.......",
 "..................."}
    {0,1,2,3,3,3,10,10,10,16,16,16,22}
    {4,0,6,2,8,14,2,8,14,2,8,14,8}
    Returns: "1234567890"
    More normal looking phone.
  5. {"1X2X3X4X5X6X7X8X9X0"}
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}
    Returns: "1234567890"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.

Back to all problems