String balls
Statement
Goal
Note: You can find the second part of this puzzle, made by @Timinator, at:Statement:
Let's name the string
d("b", "d") = d("d", "b") = 2
d("f", "f") = 0
d("a", "z") = 25
We can extend d to strings of equal length as follows: given two strings sa, sb of equal length len, d(sa, sb) is the sum of the pairwise d(sa[i], sb[i]) for all index values (i) from 0 to len-1. For example:
d("fb", "fd") = d("f", "f") + d("b", "d") = 0 + 2 = 2
d("ab", "ac") = d("ac", "ab") = 1
d("ac", "bb") = 2
We can now define a (closed) ball of center a given string and of (integer) radius. A point p (i.e. a string with letters in the alphabet and of same length as the center) is inside the ball if d(center, p) <= radius.
Find the number of points contained in the ball of center center and radius radius.
Example (Test 4):
2
ab
The points at distance less or equal to
- at distance 0: ab
- at distance 1: bb, aa, ac
- at distance 2: cb, ad, bc, ba
For a total of 8 points contained in the (closed) ball of center
NB: Tests 1-7 cover simple cases and should help you debug your program. Tests 8-11 check the performance.
Input
Line 1: An integer radius, the radius of the ball.
Line 2: A string center, the center of the ball.
Line 2: A string center, the center of the ball.
Output
The number of points inside the ball of center center and radius radius.
Constraints
0 < radius <= 100
0 < length(center) < 20
0 <= answer <= 1e6
The string center contains only lowercase English letters.
0 < length(center) < 20
0 <= answer <= 1e6
The string center contains only lowercase English letters.
Example
Input
1 a
Output
2
Tags
Geometry, Strings
Difficulty
Medium
Test cases
1. r=1, edge=yes, char=1 Test
Input
1
a
Output
2
1. r=1, edge=yes, char=1 val Validator
Input
1
z
Output
2
2. r=1, edge=no, char=1 Test
Input
1
j
Output
3
2. r=1, edge=no, char=1 val Validator
Input
1
k
Output
3
3. r>1, edge=no, char=1 Test
Input
4
g
Output
9
3. r>1, edge=no, char=1 val Validator
Input
7
l
Output
15
4. r>1, edge=yes, char>1 Test
Input
2
ab
Output
8
4. r>1, edge=yes, char>1 val Validator
Input
3
yz
Output
13
5. r>1, edge=no, char>1 Test
Input
3
pen
Output
63
5. r>1, edge=no, char>1 val Validator
Input
3
pin
Output
63
6. Small test 1 Test
Input
4
ball
Output
199
6. Small test 1 val Validator
Input
5
kappa
Output
819
7. Big radius Test
Input
100
bye
Output
17576
7. Big radius val Validator
Input
50
coc
Output
17272
8. Medium 1 (>100k) Test
Input
11
greece
Output
181477
8. Medium 1 (>100k) val Validator
Input
9
souvlaki
Output
408319
9. Medium 2 Test
Input
10
rafarafa
Output
244669
9. Medium 2 val Validator
Input
14
paella
Output
295804
10. Big ( > 500k) Test
Input
10
portugal
Output
841635
10. Big ( > 500k) val Validator
Input
12
finland
Output
819559
11. Big 2 Test
Input
9
codingame
Output
968896
11. Big 2 val Validator
Input
12
ripchat
Output
775177
Solution language
Solution
Stub generator input