XOR Riddle

t_n_k

Joined Mar 6, 2009
5,455
I figure that the answer would be, how many iterations does the LFSR have to go through in order to get to the start of the next verse of the West Side Story song, which would be "Oh", or 4F68 in hex, or 0100 1111 0110 1000 in binary.

It would take you a very long time to determine that answer by hand, as it will take you more than 33,000 iterations to arrive at the correct answer (very big hint).

There are three other possibilities with mixing of upper and lower case "O"s and "H"'s.
Thanks for that.

I've found those cases you mention. Of course it depends on which starting (seed) value you choose as to the particular iteration where the anticipated text first appears.

For instance if you enter the seed 1001 1110 1101 0000 = HEX 9ED0 the next iteration gives the ASCII equivalent "Oh"

Interestingly, you can find other two letter "words" [sequences] such as "OK" or "Hi" and "Pi". Usually you seem to get the four options ignoring any upper / lower case exclusions. Finding 3 letter words [as contiguous sequences] would be an interesting if not impossible [i.e. null result] challenge. I can't find "cat" for instance.
 

t_n_k

Joined Mar 6, 2009
5,455
Ah, well - here's what I came up with...
Rich (BB code):
"oh" was at iteration 14,975
"OH" "   "  "         33,689
"Oh" "   "  "         46,001
"oH" "   "  "         63,614
Believe it or not, I used an Excel spreadsheet.
I believe you - that's what I've been doing for the last hour or so.
 

blah2222

Joined May 3, 2010
582
Though I applaud your efforts at working on this problem, I think you guys are thinking too hard. I too spent time going through all the shifts but it is a riddle and they are meant to be clever not tedious.
 

SgtWookie

Joined Jul 17, 2007
22,230
As I expected, there were two cats;
"CA54" @ 22,503; chr$(54) is "T"
"CA74" @ 28,085; chr$(74) is "t"
It's kind of cheating, as the "C" and "A" are the hex representation of the first 8 bits; then the T's are ASCII lookups.

In the functions I was using in Excel, I only showed results where the resulting characters would be in the printable range, grouped around the letters.

@blah2222 - sure, but it's fun. ;) Did you know that there is no XOR() function in Excel? Sure, you could write a function in Visual Basic, but I wanted to stay away from that.

This is a workaround XOR:
=OR(AND(S1,NOT(Q1)),AND(Q1,NOT(S1)))
With that, I'm getting back a TRUE or FALSE depending on the contents of S1 and Q1.
There are two more XORs like that.
The conversion from binary to individual HEX characters is rather pedestrian:
=BIN2HEX((D2*1000)+(E2*100)+(F2*10)+G2,1)
Then I checked to see if the values were in a printable area of the ASCII table:
=IF(AND(AND(U1>"3",U1<"8"),AND(W1>"3",W1<"8")),"<=","")
And then convert the printable ones to text:
=IF(Y1="<=",CONCATENATE(CHAR(BIN2DEC(D1*10000000+E1*1000000+F1*100000+G1*10000+H1*1000+I1*100+J1*10+K1)),CHAR(BIN2DEC(L1*10000000+M1*1000000+N1*100000+O1*10000+P1*1000+Q1*100+R1*10+S1))),"")

It got to be a rather large spreadsheet; 70 megabytes. I hit the limit on rows. ;)
 
Last edited:

t_n_k

Joined Mar 6, 2009
5,455
Did you know that there is no XOR() function in Excel? Sure, you could write a function in Visual Basic, but I wanted to stay away from that.

This is a workaround XOR:
=OR(AND(S1,NOT(Q1)),AND(Q1,NOT(S1)))
With that, I'm getting back a TRUE or FALSE depending on the contents of S1 and Q1.
There are two more XORs like that.
;)
Nice work!

It's addictive.

Yes - it soon becomes obvious in the functions listing that there's no XOR.

I used XOR:=AND(NOT(AND(S1,Q1)),OR(S1,Q1))

- like you avoiding the VBA option.
 
@both SgtWookie and t_n_k
I don't use excel regularly. In-fact I haven't used excel in years. Your idea of using excel to solve such problems is quite interesting. So could you just upload the excel file that you used for this problem. Not the entire 70MB but just containing the formulas(I don't actually know how to use different cells in a formula:confused: I am a total noob at microsoft office). So your file will prove to be a prototype(or a starting point) with which I can develop my own ideas.
 
Since I didn't know much of excel I couldn't understand what you meant by U1, U2, W1, W2 and other terms. After going through the excel file I found out that they were actually specifying a value in a cell(U1 means column U and row 1). Thanks. Now I understand the entire logic.
 
Top