A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you are requested to be thoughtful in not posting anything that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
I've got a nice algorithm all written out for problem 158, but it appears one of my assumptions about the nature of lexographical sorting is incorrect. The example says that of strings of length 3, there are 10400 which have only 1 character greater than its left neighbor.
Yet, running this naive brute force on 3 letters, I get a result of 11700.
total=0;
for a in range(ord("a"),ord("z")+1):
for b in range(ord("a"),ord("z")+1):
for c in range(ord("a"),ord("z")+1):
t=0;
if(b>a): t+=1;
if(c>b): t+=1;
if(t==1): total+=1;
#st=chr(a)+chr(b)+chr(c);
print "Total: %d"%total;
You've simply overlooked the word 'different' in the problem text. Or maybe not, it's not in that sentence, so technically we have a mistake in the example It's in the more important sentences, though
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
Just a clarification to help people who might struggle with this problem, like I did, in order to save them some frustration: as the problem is worded, it is ambiguous and redundant. First off, of course a string of n characters that are all different will be of length n. So, saying p(n) counts strings with n characters of length n sounds like it's adding an extra requirement, some kind of diagonalisation requirement, which is confusing.
The ambiguity is that it's unclear whether we are considering alphabets with n <= 26 characters, or whether we are choosing n <= 26 characters from the standard alphabet. It turns out that the correct answer requires you to assume the latter. But the wording "We now consider" implies that we're doing something that puts a twist on what was stated in the first paragraph, whereas it's actually exactly the same as the example in the first paragraph. Also, the redundancy in specifying the string length contributes to interpretation that what was being specified was the size of the alphabet, rather than the number of characters chosen from it, which does not need to be specified. Hope this helps someone.
I'm trying to get 10400 for n=3, but I'm getting 9800. Am I missing any cases by thinking like this, or am I just calculating it wrong?
Get all possible strings where the first two letters are not lexicographically ordered, and append a lexicographically ordered character to the end, i.e. zx.y, zw.(x+y), ..., za.(b+...+y), yw.(x+z), yv.(w+x+z), ..., ca.(b+d+e+...+z).
Then get all possible strings where the first two letters are lexicographically ordered, and append a non-lexicographically correct character, i.e. yz.(a+...+x), xz.(a+...+w+y), ..., ac.b.
PurpleBlu3s wrote:I'm trying to get 10400 for n=3, but I'm getting 9800. Am I missing any cases by thinking like this, or am I just calculating it wrong?
That should give the right answer for the 3 letter example. Note that there are the same number of each type (so 5200 each). Can you see why?
PurpleBlu3s wrote:I'm trying to get 10400 for n=3, but I'm getting 9800. Am I missing any cases by thinking like this, or am I just calculating it wrong?
That should give the right answer for the 3 letter example. Note that there are the same number of each type (so 5200 each). Can you see why?
It's in the more important sentences, though 
