Problem 059

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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Slock
Posts: 4
Joined: Wed Feb 27, 2008 12:20 pm

Problem 059

Post by Slock »

So I am trying to write the brute force cipher program. I thought I had everything right, example, when I encode my own message, it comes back out correctly. But when I deal with the cipher1.txt file I get gibberish constantly. For example, the first character when XOR'd with a-z it always produces a symbol. But this is supposed to be all english words.

So I did:

Code: Select all

for(int i=97; i<=122;i++)
		{
			int currVal = XOR(79,i);
			char c=new Character((char) currVal);
			PrintShop.print(""+c+PrintShop.nl());
		}

and that produces for the first letter:
Expand
.
-
,
+
*
)
(
'
&
%
$
#
"
!

?
>
=
<
;
:
9
8
7
6
5
If the password has to be 3 lower case letters, then it has to be one of a-z deciphering the first character.XOR(79,i)works fine, I've double checked it with the examples they give with answers in the problem text.

65 XOR 42 = 107, then 107 XOR 42 = 65. That works fine. Am I misunderstanding what lower case character is? is that more then just a-z (26 characters).

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 59

Post by daniel.is.fischer »

Well, english text can contain some special symbols, e.g. some books begin with a quotation mark, an apostrophe or a digit.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

User avatar
hk
Administrator
Posts: 10660
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 59

Post by hk »

The encrypted text does not only contain lower case letters, but also uppercase letters and other characters.
Image

Slock
Posts: 4
Joined: Wed Feb 27, 2008 12:20 pm

Re: Problem 59

Post by Slock »

Oh, I got ya. That was my mistake then. I'll keep at it, Thank you.

Eureka
Posts: 6
Joined: Sun Jun 22, 2008 5:44 pm

Re: Problem 59

Post by Eureka »

I don't think I quite understand this problem.
Is there just one technically correct answer or many technically correct answers but only one that we have to pick out by reading the most linguistically or grammatically correct one?

For example, even when I correctly encrypt my own code and then try to decrypt it, I come up with many different possible answers that contain only ASCII printable characters. Then I have to scan through them and find the decryption that makes sense (ie, readable English words). Is that how it's suppose to be done?

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 59

Post by daniel.is.fischer »

More or less. There are some characteristics plain english text has. Let your programme look for some of these, once you've found four or five, you have the key.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

Eureka
Posts: 6
Joined: Sun Jun 22, 2008 5:44 pm

Re: Problem 59

Post by Eureka »

I have generated 540 possible solutions for cypher1.txt containing ASCII printables but none of them reads remotely like English.
Should I post my code?

Thanks!

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 59

Post by daniel.is.fischer »

Don't post the code, PM it if it's a readable language.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 59

Post by daniel.is.fischer »

One of them reads like english. To find out which, you should let your code scan for characteristics of such text, there's more to it than that it only consists of printable characters.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

Eureka
Posts: 6
Joined: Sun Jun 22, 2008 5:44 pm

Re: Problem 59

Post by Eureka »

Oy, found it! Thanks a lot. Much appreciated. :D

tiny
Posts: 10
Joined: Tue Aug 05, 2008 9:51 am

Problem 59

Post by tiny »

Hello

I found the key and unscrambled the text.
But...
When I add all the ascii values, the answer appears to be wrong.

Where can I look for?
Whitespace (asc 32)?
Newlines \n

Ikcelaks
Posts: 28
Joined: Wed Oct 15, 2008 8:08 pm

Re: Problem 59

Post by Ikcelaks »

That's the right value for space. Most languages have a function from characters to their ascii byte value (usually "ord"). Are you applying that function to each character in the decrypted string and summing the result?

One possible thing to look for (depending on the language) is that you're summing integers rather than bytes, which would quickly overflow. However, it would probably be pretty obvious if you were getting a result less than 256.

tiny
Posts: 10
Joined: Tue Aug 05, 2008 9:51 am

Re: Problem 59

Post by tiny »

I'am summing up exactly 1200 characters.

For this problem I use python.
The ord() function is part of this language.

Ikcelaks
Posts: 28
Joined: Wed Oct 15, 2008 8:08 pm

Re: Problem 59

Post by Ikcelaks »

I'am summing up exactly 1200 characters.
That might be the problem. I count 1201 characters.

User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Re: Problem 59

Post by elendiastarman »

Yeah, you might have to increase the end limit of your Python loop by 1 (It is rather annoying to me sometimes... :P).
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

Ikcelaks
Posts: 28
Joined: Wed Oct 15, 2008 8:08 pm

Re: Problem 59

Post by Ikcelaks »

Isn't the "foreach" construct a hallmark of Python programming? Maps, folds, and foreach like patterns are the way to go these days. Almost every language supports some kind of automated iteration over data structures.

sigh
Posts: 5
Joined: Wed Nov 19, 2008 11:46 pm

Re: Problem 59

Post by sigh »

Ikcelaks wrote:Isn't the "foreach" construct a hallmark of Python programming? Maps, folds, and foreach like patterns are the way to go these days. Almost every language supports some kind of automated iteration over data structures.
Indeed. Whenever possible iterate over the elements in the object, rather than the indexes. If you need the indexes, then use enumerate.

Simple example:

Code: Select all

for i, c in enumerate(string_object):
    print "Character in position %d is %s" %(i,c)
Most of the time you don't need the indexes so `for c in string_object` would suffice. This will help greatly reduce off-by-one errors :).

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: Problem 59

Post by quilan »

Ikcelaks wrote:Isn't the "foreach" construct a hallmark of Python programming? Maps, folds, and foreach like patterns are the way to go these days. Almost every language supports some kind of automated iteration over data structures.
Technically, the 'for' is a 'foreach' all the time I believe. Just use enumerate to make cleaner code.
ex ~100%'er... until the gf came along.
Image

tiny
Posts: 10
Joined: Tue Aug 05, 2008 9:51 am

Re: Problem 59

Post by tiny »

Hello

All the loops did what they had to do, but the problem was the absence of a comma at the end of the file.

My program genrated a character after reading a comma, so the last character was forgotten.

whakamaru
Posts: 47
Joined: Thu May 06, 2010 10:08 pm

Re: Problem 059

Post by whakamaru »

Do the words of the question "common English words" imply an element of human judgement?
If so, may I use human judgement to guess that common English words will be seperated by common English spaces?
That gave me the key, so I wrote the code that does the XOR and adds up the ASCII. And get the wrong answer.!
Oh dear, so sad, too bad. Perhaps there is another valid key? I will persist, mainly coz I want to see how the 'experts' did it. Watch this space... next year.

Post Reply