InfiniteSoup | Topcoder Archive

Problem Statement

Integer coordinates in a two-dimensional plane are assigned letters from a grid g as follows: point (x,y) is assigned g[y%R][x%C], where R and C are the number of rows and columns in g, respectively. The grid g is given as a String[], where each element is a single row, and g[i][j] is the jth character of the ith element (both 0-indexed).

Consider all rays that originate at (0,0) and move outward, crossing integer coordinates where both x and y are greater than or equal to zero. Each ray spells out an infinite sequence of letters - the letters assigned to each coordinate crossed by the ray, in the order they are crossed.

You are given a list of words. You must return the number of rays that contain each of the given words. A ray contains a word if the word is a substring of the infinite letter sequence spelled out by the ray. Only consider rays that intersect at least one integer coordinate (x,y) such that both 0<=x<=k and 0<=y<=k, where k is given as a parameter. In the int[] returned, the ith position represents the number of the described rays that contains ith word given in words.

Definition

Class:: InfiniteSoup
Method:: countRays
Parameters:: String[], String[], int
Returns:: int[]
Method signature:: int[] countRays(String[] g, String[] words, int k)
(be sure your method is public)

Constraints

g will contain between 1 and 35 elements, inclusive.
Each element of g will contain between 1 and 35 lowercase ('a'-'z') letters, inclusive.
All elements of g will contain the same number of characters.
words will contain between 1 and 25 elements, inclusive.
Each element of words will have between 1 and 50 lowercase ('a'-'z') letters, inclusive.
k will be between 1 and 200, inclusive.

Examples

```
{"abc","def","ghi"}
```
```
{"abc"}
```
```
2
```
```
Returns: {1 }
```
With k=2, the only five possible possible rays spell "abcabc...", "afhafh...", "aeiaei...", "ahfahf..." and "adgadg...".

{"abc","def","ghi"}

{"abc"}

Returns: {2 }

{"abc","def","ghi"}

{"abc"}

Returns: {3 }

{"ccbbc","baabc","ccbab","cbcaa","aacab"}

{"aaccbaaccbaacc","aabbcaabbcaabbc","babccbabccbabc","aaacaaaacaaaaca",
 "abbcaabbcaab","ccbbcccbbcccbbc","bbacabbacab","caacccaacccaac",
 "baaccbaaccbaac","caccbcaccbca"}

Returns: {0, 2, 0, 0, 2, 7, 5, 6, 0, 5 }

{"abb","bbb","bbb"}

{"aaa"}

Returns: {0 }

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.