6
In this question Tom learned that, in general, there are many motivations to choose to include case sensitivity in his programming language, because the possible combinations for a variable name are much more than what's possible with a case insensitive programming language for a name of the same length.
But, as a more meticulous person than him pointed out, even with case sensitivity, many combinations like A_18__cDfG are wasted anyway because no one will ever use them, so Tom decided to be an even more meticulous person and to redo the calculation of the difference of possibilities of variable names between a case sensitive programming language and a case insensitive programming language only counting the variable names that are likely to be used.
The Challenge
Write a function (or a full program if your language doesn't support them) that takes an input n and returns (or outputs) the difference between the number of possible, valid combinations for a variable name of length n with case sensitivity and a variable name of the same length without case sensitivity.
Valid names
You must only count names in which:
The first character is either an alphabet letter or an underscore, but never a digit;
If there are digits, they must appear at the end of the name, so that
x1andarraysize12are valid butiam6feettallisn't;If underscores are present, they must appear at the beginning of the name, like in
__privateand_VERSIONbut unlike in__init__orsome_variable;For case sensitive names, variables like
HeLlObOySaren't counted. A name must be either all uppercase (HELLOBOYS) or all lowercase (helloboys);There must be at least one alphabetic character. This means
_________a9999999999is valid but__or_4arent't.
Rules
Regexs are, of course, allowed;
Blame Tom's meticulousness.
Testcases
Input (lenght of the varable name) -> Output (differences in valid combinations)
0 -> 0 (no combinations for both cases: 0 - 0 = 0)
1 -> 26
2 -> 962
3 -> 27898
4 -> 754234
5 -> 19898970
6 -> 520262106
Scoring
It's again code golf. Shortes program in bytes wins.
Reference, non-competing Lua implementation
Since the test cases may be wrong, I've been asked to include it, so here it is:
local case = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_0123456789"
local function isvalid(s) --checks if a string s is valid AND only suitable for case sensitive
if s:upper() == s then --if the string is all uppercase, it's also valid for case unsensitive
return false
end
return (s:match"^_*[%w]+[%d]*$" --checks if it matchs the underscore-character-digit sequence
and s:lower() == s) --checks if it's all lowercase
and true --trasforms to boolean value
end
local function each(s, n) --recursive function called for character at position 2..n
if n == 0 then
if isvalid(s) then
return 1
end
return 0
else
local total = 0
for i = 1, #case do
total = total + each(s..case:sub(i, i), n - 1)
end
return total
end
end
local function diff(n) --the actual function
local total = 0
if n > 0 then
for s = 1, #case - 10 do --loops for character at position 1, which can't be a digit
total = total + each(case:sub(s, s), n - 1)
end
end
print(string.format("%.0f", total)) --prints the result in non-scientific notation
end
user6245072
Posted 2016-07-14T09:08:27.150
Reputation: 775
@Zeta Tom's programming language's naming conventions don't allow that :-p it's to keep the challenge not too complicated. – user6245072 – 2016-07-14T09:43:39.733
I'm not sure whether the difference for
2is correct. Valid names are either_<character>,<character><digit>or<character><character>. Without case sensitivity, we have26 + 26 * 10 + 26 * 26 = 962combinations. With case sensitivity, we have52 + 2 * 26 * 26 + 52 * 10 = 1924combinations. The difference is962, but you state926. Typo? – Zeta – 2016-07-14T10:04:45.050@Zeta actually, yes. Thanks for correcting me. – user6245072 – 2016-07-14T10:10:16.097
It's computationally impossible to have the execution time stay less than 2^n minutes as n increases, since each character adds more than double the previous number of names. – PurkkaKoodari – 2016-07-14T10:17:21.893
@Pietu1998 I'm removing the limit – user6245072 – 2016-07-14T10:30:18.507
@user6245072: I'm still not sure about your test cases. There are 27898 valid case-insensitive combinations for
n = 3, and 55796 for case-sensitive ones. See answer below. Perhaps you want to add your own solution as reference? – Zeta – 2016-07-14T11:12:01.6331
%wmatches alphanumerics, so your pattern allows for e.g.iam6feettall. Use%afor letters. – PurkkaKoodari – 2016-07-14T12:15:06.657@Pietu1998 * facepalm * – user6245072 – 2016-07-14T12:27:51.117
@Pietu1998 That fixed everything. Thanks. – user6245072 – 2016-07-14T12:30:54.107
@Pietu1998: Err, it's easily possible to have the execution time less than 2^n minutes. Well, unless you start to create every valid string… – Zeta – 2016-07-14T16:56:35.913
@Zeta well, now that I think of it, does seem simple with the mathematical approach. – PurkkaKoodari – 2016-07-14T16:58:10.780