Help with algorithms

[mirado.kelly]

Im new to algorithms and am not haveing much luck on google, dont think im useing the right terms but here goes:

Im solveing a crackme, for fun. I've studied the code and determined the serial must add to 2F2 along with some other constraints. It is 6 chars long.

First I figured i could write a nested loop that counts from
1, 1, 1, 1, 1, 1 to 256, 256, 256, 256, 256, 256

That would take way too long, so I come up with an algorithm, it almost works except keeps returning to 256, were everything started. And thats where I need help.

It does not get much further then 255, 255, 127, 4, 1, 1

To descirbe my algorithm, I would first test for sum == target then,

if sum < target I would increase the current value by value = value + (max - value)/2
if sum > target I would reduce the curent value by value = value - (value - min)/2

max would equal 256, and min 0, but once sum < target, I set min equal to curent value since if the current value results in a sum less then what I want, reduceing it further makes no sence.

I think this is called divide and conquer but not sure. Where can I learn more about these type of algorithms?

[sec_ware]

Hi

A general note:

R. Sedgewick has written a book about Algorithms[1], which I still use frequently.
Also check the web for keywords like "backtracking[2]" and "dynamic programming[3]".
Have also a look at the webpage of the International Olympiad in Informatics[4] - an
excellent resource for algorithmic problems, often with documented solutions.

Note that it is a very crucial conceptual difference whether you need one solution
or all solutions - the right choice for the right algorithms is of utmost importance.



More specific about this kind of problems:

It seems not valid here, but in general, "serial-numbers" consist of letters A-Z (a-z) and
numbers 0-9. A nested loop (with jumps from 58 to 65 and 91 to 97) often is a reasonable
approach.

A boost in performance can be achieved by a clever way of doing the "checks": in the innermost
loop, to the computationally least intensiv checks first, and break after each check if not
successful.

If you have such a nice thing like a "additive checksum", you can do what you do: break
a loop as soon as the partial sum is larger than the intended checksum.



about this problem

You have the classic problem that you have to "reinitialise" a value. Backtracking comes
to my mind, but clearly is too much of an overhead here. Hence, you can do this "manually".
To illustrate this idea, here is a (in principle useless, and yes I know one could use For-Loops
as well ...) example just looking at 2 chars:

        A = 0
        B = 0
        sum = 240
        While (A <= 255)
            While (B <= Min(sum - A, 255))
                If (A + B = sum) Then
                    ...
                End If
                B += 1
            End While
            B = 0   ' <--
            A += 1
        End While

Certainly there are some more ways to decrease the space of possible "configurations", where
a configuration is defined as a 6-dimensional vector in the 6-dimensional discrete finite
space of your problem. However, you have to be very careful while reducing since often,
the dimensions are not permuteable, ie. you cannot exchange the chars A,B,C,D,E,F.

If the only condition to be satisfied is the "additive checksum" to be 754 (2F2) then you
can exchange the chars, hence you can demand that A <= B <= C <= D <= E <= F, which greatly
reduces the candidate configuration space. Furthermore, once you have found one "solution",
you have actually found 6!/(sim)=720/(sim) valid solutions (where sim is a factor coming
from repetitions in the solution, ie if you have 2x "250" but the other 4 values are unique,
this would be a factor 2. if you have 3x "250" and 2x "15" this number sim would be 3!*2! etc.).


Be careful when you increase a value by more than "1" as you do. If you are not careful
enough, you may miss a/the solution.

I may have misunderstood your current problem - if so, please paraphrase


Cheers

[1]
http://www.amazon.com/gp/product/020...956113?ie=UTF8
[2] http://en.wikipedia.org/wiki/Backtracking
[3] http://en.wikipedia.org/wiki/Dynamic_programming
[4] http://olympiads.win.tue.nl/ioi/

[steve.milner]

This may be stating the obvious, but you could cut down loop work by a dimension by calculating 'F'...

F == 754 - (A + B + C + D + E)

[mirado.kelly]

sec_ware That was extreamly helpfull, I am well on my way to solveing this problem now.

I am so greatfull for all this information I am adding it to my documentation, and notes. Your explanations are easy for me to understand compared to other sites I viewed.

PS Id give you more AP points but system refuses

[mirado.kelly]

I am glad to announce I have completed that chalenge. My final progie was able to calculate the corect answer in 2.12 minutes This was achived after realizeing the three conditons

A was determined by value of F, D by C, and E by B
I also noted they problably only used printable characters, reduceing my search futher.

Your secret of A<=B<=C<=D<=E<=F though didnt help this puzzel, I did try this technique of counting and it amazeingly reduces the range by half. Thanks for this great tip!

Your idea Min(sum - A, 255) realy helped me, I realize this meant B would never go larger then needed to develop target sum. So I calculated sum in inner loop, and checked for sum &gt; target

I cannot thank you enough.

[sec_ware]

Hi

Congratulation!

Your secret of A&lt;=B&lt;=C&lt;=D&lt;=E&lt;=F though didnt help this puzzel, I did try this technique of counting and it amazeingly reduces the range by half. Thanks for this great tip!

This was to be expected - the 6 chars are not interchangeable, which is a necessary
condition for this restriction to be valid.

I also noted they problably only used printable characters, reduceing my search futher.

As said, this makes perfectly sense - now you understand (However, I guess you already
know that) why people say use special characters in your passwords

Continue with the next challenge Have you seen these: crackits[1] by white_scorpion,
formerly known here as lepricaun (there is a thread about them[2]).


Cheers

[1] http://www.white-scorpion.nl/crackits/index.html
[2] http://www.antionline.com/showthread...hlight=secware

[mirado.kelly]

Thanks so much, I love these chalenges. Gona try them next.

I did notice, while trying the A&lt;=B trick, that I could use an algortihm next_predicate from the STL library, only after trying to code one my self. I noticed it was extramly fast with a set of 6.