Search

Categories

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Send mail to the author(s) E-mail

# Wednesday, 01 May 2013

http://msdn.microsoft.com/en-us/library/ee256691.aspx – Using Cancellation tokens

using System;
using System.Threading;
using System.Threading.Tasks;

namespace ParallelCancel
{
    class Program
    {
        static void Main()
        {
            // want to break out of a parallel.for when a condition occurs
            var cts = new CancellationTokenSource();
            // Use ParallelOptions instance to store the CancellationToken
            var po = new ParallelOptions();
            po.CancellationToken = cts.Token;

            try
            {
                // could use syntax i => {
                Parallel.For(1, 100, po, delegate(int i)
                {
                    po.CancellationToken.ThrowIfCancellationRequested();
                    Console.WriteLine(i);
                    if (i == 50)
                    {
                        cts.Cancel();
                    }
                });
            }
            catch (OperationCanceledException e)
            {
                Console.WriteLine("Cancelled");
            }
        }
    }
}

Simple example of cancellation tokens
using System;
using System.Threading;
using System.Threading.Tasks;

namespace ParallelCancel
{
    class Program
    {
        static void Main()
        {
            // want to break out of a parallel.for when a condition occurs
            var cts = new CancellationTokenSource();
            // Use ParallelOptions instance to store the CancellationToken
            var po = new ParallelOptions();
            po.CancellationToken = cts.Token;

            long counterTotal = 0;

            try
            {
                // could use syntax i => {

                // want to have a sum of counts at the end
                Parallel.For<long>(1, 10000000, po, () => 0, delegate(int i, ParallelLoopState state, long counterSubtotal)
                    {
                        po.CancellationToken.ThrowIfCancellationRequested();
                        //CConsole.WriteLine(i);
                        counterSubtotal++;
                        if (i == 50000)
                        {
                            cts.Cancel();
                        }
                        //});
                        return counterSubtotal;
                    }, (x) => Interlocked.Add(ref counterTotal, x)
                    );
            }
            catch (OperationCanceledException e)
            {
                Console.WriteLine("Cancelled");
                Console.WriteLine("Total iterations across all threads {0}", counterTotal);
            }
        }
    }
}

Cancellation tokens with a ‘global state’ variable handled well.  ie the counter is summed up at the end.

this code works well (from http://stackoverflow.com/questions/16344736/parallelfor-not-cancelling-all-threads-immediately-if-condition-met)

static void Main()
        {
            // want to break out of a Parallel.For immediately when a condition occurs
            var cts = new CancellationTokenSource();
            var po = new ParallelOptions();
            po.CancellationToken = cts.Token;

            long counterTotal = 0;

            try
            {
                // want to have a sum of counts at the end
                // using type param here to make counterSubtotal a long
                Parallel.For<long>(1, 26, po, () => 0, delegate(int i, ParallelLoopState state, long counterSubtotal)
                        {
                            Console.WriteLine(i.ToString());
                            // 1 billion
                            for (int k = 0; k < 1000000000; k++)
                            {
                                //po.CancellationToken.ThrowIfCancellationRequested();
                                if (po.CancellationToken.IsCancellationRequested)
                                {
                                    return counterSubtotal;
                                }
                                counterSubtotal++;

                                if (i == 4 && k == 400000000)
                                {
                                    Console.WriteLine("Inner Cancelled");
                                    cts.Cancel();
                                }
                            }
                            return counterSubtotal;
                        }, (x) => Interlocked.Add(ref counterTotal, x)
                    );
            }
            catch (OperationCanceledException e)
            {
                Console.WriteLine("Cancelled");
                Console.WriteLine("Total iterations across all threads {0}", String.Format("{0:n0}", counterTotal));
                Console.ReadLine();
            }
        }

and here is the coding challenge using tokens:

To optimise this, I’d break up the chunks into smaller bits.  As a speed test, 750million comparisons per second is great.

image

    internal class Program
    {
        private static void Main()
        {
            var cts = new CancellationTokenSource();
            var po = new ParallelOptions();
            po.CancellationToken = cts.Token;

            long counterTotal = 0;
            var stopwatchOverall = new Stopwatch();
            stopwatchOverall.Start();
            try
            {
                Parallel.For<long>(97, 123, po, () => 0, (i, state, counterSubtotal) =>
                    {
                        Console.WriteLine("Starting " + i);

                        // array of bytes (can be 0 to 255) eg 100, 97, 118, 101, 100, 97, 118
                        byte[] secretBytes = Encoding.UTF8.GetBytes("aavedave");
                        // same size array that we'll populate many times to compare with
                        var comparisonBytes = new byte[8];

                        comparisonBytes[0] = (byte) i;
                        for (byte j = 97; j < 123; j++)
                        {
                            comparisonBytes[1] = j;
                            //loop 3
                            for (byte k = 97; k < 123; k++)
                            {
                                comparisonBytes[2] = k;
                                //loop4
                                for (byte l = 97; l < 123; l++)
                                {
                                    comparisonBytes[3] = l;
                                    //loop 5
                                    for (byte m = 97; m < 123; m++)
                                    {
                                        comparisonBytes[4] = m;
                                        //loop6
                                        for (byte n = 97; n < 123; n++)
                                        {
                                            comparisonBytes[5] = n;
                                            //loop7
                                            for (byte o = 97; o < 123; o++)
                                            {
                                                comparisonBytes[6] = o;
                                                //loop8
                                                for (byte p = 97; p < 123; p++)
                                                {
                                                    comparisonBytes[7] = p;

                                                    if (po.CancellationToken.IsCancellationRequested)
                                                    {
                                                        Console.WriteLine("Returning " + i.ToString());
                                                        return counterSubtotal;
                                                    }

                                                    counterSubtotal++;

                                                    bool found = true;
                                                    for (int a = 0; a < 8; a++)
                                                    {
                                                        if (comparisonBytes[a] != secretBytes[a])
                                                        {
                                                            found = false;
                                                            break;
                                                        }
                                                    }

                                                    if (found)
                                                    {
                                                        var comparisonString = Encoding.UTF8.GetString(comparisonBytes);
                                                        var secretString = Encoding.UTF8.GetString(secretBytes);
                                                        Console.WriteLine("Comparison is {0} and secret is {1} after {2} pattern matches on this thread",comparisonString, secretString,String.Format("{0:n0}", counterSubtotal));
                                                        Console.WriteLine("Inner cancelled");
                                                        cts.Cancel();
                                                    }
                                                } //end loop 8
                                            } //end loop 7
                                        } // end loop 6
                                    } // end loop 5
                                } //end loop 4
                            } // end loop 3
                        } // end loop 2
                        return counterSubtotal;
                    }, (x) => Interlocked.Add(ref counterTotal, x)
                    );
            }
            catch (OperationCanceledException e)
            {
                Console.WriteLine("Total counts on all threads is {0}", String.Format("{0:n0}", counterTotal));
                stopwatchOverall.Stop();
                TimeSpan ts = stopwatchOverall.Elapsed;
                Console.WriteLine("Timespan: {0}s", ts.TotalSeconds);

                long throughput = counterTotal/(long) ts.TotalSeconds;
                Console.WriteLine("Throughput across all cores: {0}comparisons/sec", String.Format("{0:n0}", throughput));
            }

            Console.WriteLine("End of program");
        }
    }
| | # 
# Tuesday, 30 April 2013

From around 12th Dec 2007: http://www.programgood.net/2010/10/12/CodeGuessingProgram.aspx

The Challenge

Whilst reading Simon Sing's - The Code Book (www.simonsingh.com)  I thought it would be fun to write a code guessing program.  My first try was in Visual Basic6, then I ported it over to C#.  Phil decided he'd have a go and wrote it in Python then Java.  Then Dan wrote it in C.  We were all intrigued as to how fast each language would be, and who would be the winner?

This program takes say x letters from lowercase a to z, in as a secretString (in all cases we used 'davedave' for 8, then 'davedav' for 7 etc..)  Then it tries to guess the secretString by starting at aaaaaaaa and finishing at zzzzzzzz (for the 8 length example).  It was not allowed guess each letter individually, it had to guess the entire string correctly.

Without further words... here are the current results, and below is the source code.  My machine runs an Athlon 1500+ processor with 3/4gig of RAM, and WinXPSP2.

--------

    Total Combinations (approx) PHP C Python Java C#      
                     
4 dave 52,278                
5 daved 1,380,000 9s     8        
6 daveda 36,000,000 221s 2 208 282        
7 davedav 936,416,178   25     23      
8 davedave     678 (11min)            

2007 times above.

2010 on Intel Core2 Dual 2.4GHz 9.5s (for #7)

2013 on i7 SandyBridge 2GHz  (4s for single thread  #7)…  ( 4s for multi thread  #8)

Here is the code (roughly the same):

using System;
using System.Diagnostics;
using System.Text;

namespace PasswordGuesserSingleThread
{
    class Program
    {
        static void Main()
        {
            var s = new Stopwatch();
            s.Start();

            long counter = 0;

            Console.WriteLine("Starting...");

            // array of bytes (can be 0 to 255) eg 100, 97, 118, 101, 100, 97, 118
            byte[] secretBytes = Encoding.UTF8.GetBytes("davedav");
            var comparisonBytes = new byte[secretBytes.Length];

            // loop 1
            for (byte i = 97; i < 123; i++)
            {
                comparisonBytes[0] = i;
                //loop2
                for (byte j = 97; j < 123; j++)
                {
                    comparisonBytes[1] = j;
                    //loop 3
                    for (byte k = 97; k < 123; k++)
                    {
                        comparisonBytes[2] = k;
                        //loop4
                        for (byte l = 97; l < 123; l++)
                        {
                            comparisonBytes[3] = l;
                            //loop 5
                            for (byte m = 97; m < 123; m++)
                            {
                                comparisonBytes[4] = m;
                                //loop6
                                for (byte n = 97; n < 123; n++)
                                {
                                    comparisonBytes[5] = n;
                                    //loop7
                                    for (byte o = 97; o < 123; o++)
                                    {
                                        comparisonBytes[6] = o;
                                        //loop8
                                        //for (byte p = 97; p < 123; p++)
                                        //{
                                        //   comparisonBytes[7] = p;

                                            counter++;

                                            // compare  to
                                            if (CompareByteArrays(comparisonBytes, secretBytes))
                                            {
                                                var comparisonString = Encoding.UTF8.GetString(comparisonBytes);
                                                Console.WriteLine("Found secret which is {0} after {1} pattern matches", comparisonString, String.Format("{0:n0}", counter));
                                                s.Stop();
                                                TimeSpan t = s.Elapsed;
                                                Console.WriteLine("Timespan: {0}s", t.TotalSeconds);

                                                long throughput = counter / (long)t.TotalSeconds;
                                                Console.WriteLine("Throughput: {0}comparisons/sec", String.Format("{0:n0}", throughput));

                                                goto End;
                                            }
                                        //} //end loop 8
                                    }//end loop 7
                                } // end loop 6
                            }// end loop 5
                        } //end loop 4
                    } // end loop 3
                }// end loop 2
            }//end 1
            Console.WriteLine("Got to end and didn't find");

        End:
            Console.ReadLine();
        }

        public static bool CompareByteArrays(byte[] comparison, byte[] secret)
        {
            // compare each byte
            for (int i = 0; i < 7; i++)
            {
                if (comparison[i] != secret[i]) return false;
            }

            return true;
        }
    }
}

image

image

See next post for multithreaded version which hits 750million comparisons per sec.

| | # 
# Sunday, 10 April 2011
keithDave

About a week ago Keith and I went on a ‘tramp’.. thats trekking.  We discussed Sudoku (apologies to Helen, Phil, Nora and others for starting the challenge without you..there was lots of time while walking to discuss strategy).

TDD

A single test project is VS2010.  Everything in one file (!) and static methods to make starting easier.

Coding strategy was to firstly:

    • find a way to check the sudoku was solved
      • Do all horizontal lines have only 1 to 9 used once
      • Do all vertical columns have 1 to 9 used once
      • Do all 3*3 squares have 1 to 9 used once

So I wanted a method to check if Array has only 1 instance of each number.

[TestClass]
public class UnitTest1
{
// Arrays are [row, col]
// 0,0 0,1 0,2
// 1,0 1,1 1,2

// SECTION 1 - tests are all about testing if the sudoku is solved
// Single Array
[TestMethod]
public void SingleArrayCheckerFailsWhenArrayTooShort()
{
int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8 };
bool result = DoesArrayHaveOnlyOneInstanceOfEachNumber(numbers);
Assert.AreEqual(false, result);
}

and the Method:

public static bool DoesArrayHaveOnlyOneInstanceOfEachNumber(int[] arrayOfNumbers)
{
if (arrayOfNumbers.Length != 9)
return false;

if (arrayOfNumbers.Contains(0))
throw new Exception("checking of a line array contains a 0");

int[] howManyInstancesOfEachNumber = new int[9] { 0, 0, 0, 0, 0, 0, 0, 0, 0 };

for (int i = 0; i < 9; i++)
{
int valueOfCurrentNumber = arrayOfNumbers[i];
howManyInstancesOfEachNumber[valueOfCurrentNumber - 1] += 1;
}

foreach (var result in howManyInstancesOfEachNumber)
{
if (result != 1)
return false;
}

return true;
}

An array is Enumerable.

then write the tests

[TestMethod]
public void AllHorizonalLinesPass()
{
int[,] sudokuArray = new int[9, 9]{ {1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9}
};

bool result = DoAllHorizontalRowsPass(sudokuArray);
Assert.AreEqual(true, result);
}

[TestMethod]
public void AllVerticalColsPass()
{
int[,] sudokuArray = new int[9, 9]{ {1,1,1,1,1,1,1,1,1},
{2,2,2,2,2,2,2,2,2},
{3,3,3,3,3,3,3,3,3},
{4,4,4,4,4,4,4,4,4},
{5,5,5,5,5,5,5,5,5},
{6,6,6,6,6,6,6,6,6},
{7,7,7,7,7,7,7,7,7},
{8,8,8,8,8,8,8,8,8},
{9,9,9,9,9,9,9,9,9}
};

bool result = DoAllVerticalColsPass(sudokuArray);
Assert.AreEqual(true, result);
}

[TestMethod]
public void AllSquaresPass()
{
int[,] sudokuArray = new int[9, 9]{ {1,2,3,1,2,3,1,2,3},
{4,5,6,4,5,6,4,5,6},
{7,8,9,7,8,9,7,8,9},
{7,8,9,7,8,9,7,8,9},
{4,5,6,4,5,6,4,5,6},
{1,2,3,1,2,3,1,2,3},
{4,5,6,4,5,6,4,5,6},
{1,2,3,1,2,3,1,2,3},
{7,8,9,7,8,9,7,8,9},
};

bool result = DoAllSquaresPass(sudokuArray);
Assert.AreEqual(true, result);
}

then make them pass:

public static bool DoAllHorizontalRowsPass(int[,] sudoku)
{
for (int row = 0; row < 9; row++) // go over each horizontal line
{
int[] horizonalLineArray = new int[9];
for (int col = 0; col < 9; col++) // get each number in that line and put into a new horizontalLineArray
horizonalLineArray[col] = sudoku[row, col];

if (!DoesArrayHaveOnlyOneInstanceOfEachNumber(horizonalLineArray))
return false;
}
return true;
}

public static bool DoAllVerticalColsPass(int[,] sudoku)
{
for (int col = 0; col < 9; col++) // go over each vertical line
{
int[] verticalLineArray = new int[9];

for (int row = 0; row < 9; row++) // get each number in that vertical line and put into a new verticalLineArray
verticalLineArray[row] = sudoku[row, col];

if (!DoesArrayHaveOnlyOneInstanceOfEachNumber(verticalLineArray))
return false;
}
return true;
}

public static bool DoAllSquaresPass(int[,] sudoku)
{
int rowStart = 0;
int rowEnd = 2;
int colStart = 0;
int colEnd = 2;

int squareCounter = 1;
while (squareCounter < 9) // take each 3*3 square and test it
{
int[] allNumbersInSquareArray = new int[9];
// go over first 3*3 square
int counter = 0;
for (int row = rowStart; row <= rowEnd; row++)
{
for (int col = colStart; col <= colEnd; col++)
{
allNumbersInSquareArray[counter] = sudoku[row, col];
counter++;
}
}

if (!DoesArrayHaveOnlyOneInstanceOfEachNumber(allNumbersInSquareArray))
return false;

// increment to the next 3*3 square going along horizontally first
if (colEnd != 8)
{
colStart += 3;
colEnd += 3;
}
else // go down to next 'row' of squares
{
colStart = 0;
colEnd = 2;
rowStart += 3;
rowEnd += 3;
}

squareCounter++;
}
return true;
}

Making a Solver

Strategy was to (For all the elements with 0 in them):

  • Get rid of numbers
    • LookAtOtherNumbersInRowAndTakeOutOnesWeDontNeedToCheck
    • LookAtOtherNumbersInColumnAndTakeOutOnesWeDontNeedToCheck
    • LookAtOtherNumbersInSquareAndTakeOutOnesWeDontNeed
    • Then select a random number from the ones left
    • check if sudoku is solved

I used TDD on each Method eg

[TestMethod]
public void LookAtOtherNumbersInRowAndTakeThoseOffTheListOfNumbersToTry()
{
int row = 2;
List<int> listOfNumbersToTry = new List<int>();
for (int i = 1; i < 10; i++)
listOfNumbersToTry.Add(i);

int[,] trySudokuArray = new int[9, 9]{ {1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,0,4,5,6,0,8,0}, // this one
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9}
};
LookAtOtherNumbersInRowAndTakeOutOnesWeDontNeedToCheck(trySudokuArray, row, listOfNumbersToTry);

Assert.AreEqual(3, listOfNumbersToTry.Count);
Assert.IsTrue(listOfNumbersToTry.Contains(3));
Assert.IsTrue(listOfNumbersToTry.Contains(7));
Assert.IsTrue(listOfNumbersToTry.Contains(9));
}

//level 1
public static int[,] solve(int[,] inputSudokuArray) {

// fill in numbers which are correct
//int[,] sudokuArrayAfterB = new int[9, 9];
//sudokuArrayAfterB = solveB(inputSudokuArray);

// semi random code
Random random = new Random();
bool isSolved = false;
int numberOfIterations = 0;

while (!isSolved)
{
int[,] trySudokuArray = (int[,])sudokuArrayAfterB.Clone();
for (int row = 0; row < 9; row++)
{
for (int col = 0; col < 9; col++)
{
if (trySudokuArray[row,col] == 0) // if it is blank
{
// setup numbers to try, then strategy is to take out of this list
List<int> listOfNumbersToTry = new List<int>();
for (int i = 1; i < 10; i++)
listOfNumbersToTry.Add(i);

LookAtOtherNumbersInRowAndTakeOutOnesWeDontNeedToCheck(trySudokuArray, row, listOfNumbersToTry);

LookAtOtherNumbersInColumnAndTakeOutOnesWeDontNeedToCheck(trySudokuArray, col, listOfNumbersToTry);

LookAtOtherNumbersInSquareAndTakeOutOnesWeDontNeed(trySudokuArray, row, col, listOfNumbersToTry);

// are there any possible numbers?
if (listOfNumbersToTry.Count > 0)
{
// pick a random number from listOfNumbersToTry
int indexOfListNumberToGet = random.Next(0, listOfNumbersToTry.Count());
trySudokuArray[row,col] = listOfNumbersToTry[indexOfListNumberToGet];
}
else
goto Foo;
}
}
}
isSolved = checkSudoku(trySudokuArray);

if (isSolved)
{
for (int row = 0; row < 9; row++)
{
for (int col = 0; col < 9; col++)
Debug.Write(trySudokuArray[row, col] + " ");
Debug.WriteLine("");
}
return trySudokuArray;
}
Foo:
if (numberOfIterations % 1000 == 0)
Debug.WriteLine("iterations: " + String.Format("{0:0,0}",numberOfIterations));
//Console.WriteLine("iterations: " + String.Format("{0:0,0}", numberOfIterations));
numberOfIterations++;
}
return null;
}

 

StrategyB – Make numbers definite if we know they are

  • For each 0 square see if there is only 1 possible number
    • ie look at LookAtOtherNumbersInRowAndTakeOutOnesWeDontNeedToCheck etc
    • put that number in the square
    • keep looping the whole board until nothing is changed
| | # 
# Wednesday, 13 October 2010

 

spectrum_800

Look at the G key :-)

/// <summary>
/// A rolling brute force attack on a secret password
/// The program knows the password is only lowercase letters, but doesn't know the length
///
/// Starting at: a
/// then b
/// then c
/// ...
/// then z
/// then aa
/// then ab
/// ...
/// then ba
/// then bb
/// ...
/// then ca
/// then cb
/// ...
///
/// try to find secret password of: davedave
/// </summary>

Here is some of the code I used.

public class PasswordGuesser
{
public string SecretPassword { get; set; }

public int CrackPassword()
{
int numberOfIterationsCrackingPassword = 0;

for (int i = 97; i < 123; i++) // 1 column
{
numberOfIterationsCrackingPassword++;
string letterToTest = ((char)i).ToString();
if (letterToTest == SecretPassword)
goto Foo;
}

for (int i = 97; i < 123; i++) // 2 columns
{
for (int j = 97; j < 123; j++)
{
numberOfIterationsCrackingPassword++;
string testingLetters = ((char)i).ToString() + ((char)j).ToString();
if (testingLetters == SecretPassword)
goto Foo;

}
}
yikes, left out the Foo bit.. here is a more recent example of the code:

image

pro

  • works
  • testable
  • easy to read

con

  • slow
  • inelegant

Version 4 – As Shown in ScreenCast

    Source (VS2010)

http://stackoverflow.com/questions/324831/breaking-out-of-a-nested-loop    - use an anonymous method would be another way

This came from a  fun project which a bunch of use tried a few years ago http://www.programgood.net/2010/10/12/CodeGuessingProgram.aspx 

Version 5 – Speedy (thanks to DaveMul)

I had to remember to run in release mode!  Intel Core2 Dual 2.4GHz.  Compiling in .NET4

davedav - 1,257,688,584...27.5 secs in debug.  45/6m iterations/sec
                        9.5 secs in release. 132m iterations.sec
zzzzzzz - 8,353,082,582...184secs in debug.  45m iterations/sec

davedave - 32,699,903,189iterations 245secs.. 4min 5secs. 133m iterations/sec
zzzzzzzz - 217,180,147,158iterations 1636secs.  133m iterations/sec   

This is significantly faster than 3 years ago. for davedav – took 23secs, and now takes 9.5 secs.

Source is here:

pro:

  • fast

con:

  • feels like there should be a better way

future:

  • use parallel library in .NET4 to use multiple cores
  • refactor so am not repeating code (DRY – Don’t Repeat Yourself, Don’t Rep…….)

 

Historial: Version 1


Here are some of the tests:

using CodeGuesserApplication;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System.Collections.Generic;

namespace Tests
{
[TestClass]
public class UnitTest1
{
[TestMethod]
public void Get_One_Column_List_Of_Strings_Check_First_Letter_Is_a()
{
PasswordGuesser codeGuesser = new PasswordGuesser();
List<string> listOfStrings = codeGuesser.Get_List_Of_Strings_a_to_z();
Assert.AreEqual(listOfStrings[0], "a");
}

[TestMethod]
public void Get_one_column_list_of_strings_check_last_letter_is_z()
{
PasswordGuesser codeGuesser = new PasswordGuesser();
List<string> listOfStrings = codeGuesser.Get_List_Of_Strings_a_to_z();
Assert.AreEqual(listOfStrings[25], "z");
}

[TestMethod]
public void Get_two_column_list_of_strings_check_first_is_aa()
{
PasswordGuesser codeGuesser = new PasswordGuesser();
List<string> listOfStrings = codeGuesser.Get_List_Of_Strings_aa_to_zz();
Assert.AreEqual(listOfStrings[0], "aa");
}
}
}

and some of the code so far:

public class PasswordGuesser
{
public string SecretPassword { get; set; }

public List<string> Get_List_Of_Strings_a_to_z()
{
List<string> listOfStrings = new List<string>();
for (int i = 97; i < 123; i++)
{
string thingToAdd = ((char)i).ToString();
listOfStrings.Add(thingToAdd);
}
return listOfStrings;
}

public List<string> Get_List_Of_Strings_aa_to_zz()
{
List<string> listOfStrings = new List<string>();
for (int i = 97; i < 123; i++)
{
for (int j = 97; j < 123; j++)
{
string thingToAdd = ((char)i).ToString() + ((char)j).ToString();
listOfStrings.Add(thingToAdd);
}
}
return listOfStrings;
}

public int CrackPassword()
{
int iterationCounter = 1;

List<string> firstColumnListOfStrings = Get_List_Of_Strings_a_to_z();
foreach (string characterToTest in firstColumnListOfStrings)
{
if ((characterToTest == SecretPassword))
{
return iterationCounter;
}
iterationCounter++;
}


List<string> secondColumnListOfStrings = Get_List_Of_Strings_aa_to_zz();
foreach (string stringOfLength2ToTest in secondColumnListOfStrings)
{
if ((stringOfLength2ToTest == SecretPassword))
{
return iterationCounter;
}
iterationCounter++;
}
return 0;
}
}

class Program
{
static void Main(string[] args)
{
PasswordGuesser codeGuesser = new PasswordGuesser();
codeGuesser.SecretPassword = "zz";
int numberOfIterations = codeGuesser.CrackPassword();
Console.WriteLine("Total iterations: " + numberOfIterations.ToString());
}
 
image

Pros
  • It works
  • I’m confident it is working well as the tests prove it
Cons:
  • It is slow
  • Lots of code
  • Not built out to handle 8 letters (many billions of iterations)
  • Wont scale well

Version 2

image

Pros
  • Becoming a bit more compact with the ‘blank’ character of 96
  • Testable
Cons
  • Has to generate a list before it can crack the password against it

Version 3

public class PasswordGuesser
{
public string SecretPassword { get; set; }

public int CrackPassword()
{
int numberOfIterationsCrackingPassword = 1;
StreamWriter file = new StreamWriter("c:\\passwordOutput.txt");
for (int i = 96; i < 123; i++) // treating 96 as a blank
{
for (int j = 96; j < 123; j++)
{
for (int k = 97; k < 123; k++)
{
string lines = ((char)i).ToString() + " " + ((char)j).ToString() + " " + ((char)k).ToString();
file.WriteLine(lines);

if ((i == 96) && (j == 96)) // 1 column
{
string letterToTest = ((char)k).ToString();
if (letterToTest == SecretPassword)
goto Foo;
}
else if ((i == 96) && (j != 96)) // 2 column
{
string testingLetters = ((char)j).ToString() + ((char)k).ToString();
if (testingLetters == SecretPassword)
goto Foo;
}
else // 3 column
{
string testingLetters = ((char)i).ToString() + ((char)j).ToString() + ((char)k).ToString();
if (testingLetters == SecretPassword)
goto Foo;
}
numberOfIterationsCrackingPassword++;
}
}
}
file.Close();
throw new Exception("Password not found");
Foo:
file.Close();
return numberOfIterationsCrackingPassword;
}
}

Unit test caught a bug in my logic.

image

Expected was 703, actual was 729.  What is going on? 

After dumping to a text file:

image

image

Ahh, so with 3 columns it is putting in a blank in the middle.  Interesting.

Pros

Cons

  • Can’t think of elegant way around this logic as I don’t want extra iterations eg a blank a is never valid

Go on to version 4 – make it simpler with multiple loops for each number of columns

Version 4

public class PasswordGuesser
{
public string SecretPassword { get; set; }
StreamWriter file = new StreamWriter("c:\\passwordOutput.txt");

public int CrackPassword()
{
int numberOfIterationsCrackingPassword = 1;

for (int i = 97; i < 123; i++) // 1 column
{
string letterToTest = ((char)i).ToString();
DoLoggingToTextFile(letterToTest);
if (letterToTest == SecretPassword)
goto Foo;
numberOfIterationsCrackingPassword++;
}

for (int i = 97; i < 123; i++) // 2 columns
{
for (int j = 97; j < 123; j++)
{
string testingLetters = ((char)i).ToString() + ((char)j).ToString();
DoLoggingToTextFile(testingLetters);
if (testingLetters == SecretPassword)
goto Foo;
numberOfIterationsCrackingPassword++;
}
}

for (int i = 97; i < 123; i++) // 3 columns
{
for (int j = 97; j < 123; j++)
{
for (int k = 97; k < 123; k++)
{
string testingLetters = ((char)i).ToString() + ((char)j).ToString() + ((char)k).ToString();
DoLoggingToTextFile(testingLetters);
if (testingLetters == SecretPassword)
goto Foo;
numberOfIterationsCrackingPassword++;
}
}
}

test code:

[TestMethod] // 132 seconds
public void Set_password_to_zzzzzz_and_check_it_takes_321million_iterations()
{
DateTime startTime = DateTime.Now;
Debug.Print("starting at: " + startTime);
PasswordGuesser passwordGuesser = new PasswordGuesser();
passwordGuesser.SecretPassword = "zzzzzz";
int numberOfIterations = passwordGuesser.CrackPassword();
Assert.AreEqual(321272406, numberOfIterations);
TimeSpan totalTime = DateTime.Now - startTime;
Debug.Print("total time in seconds for 6 cols zzzzzz: " + totalTime.TotalSeconds);
}

Slow - 132secs for zzzzzz 6 cols / 321million iterations.  Old code ran 23secs for 936million iterations

| | # 
# Tuesday, 12 October 2010

A Sudoku solver..Fun stuff..

MatLab (Chris)

This doesn’t solve harder puzzles


function X = sudoku(X)

[rows,cols] = size(X);
if rows~=9 | cols~=9
error('Invalid dimensions')
end
nmax = max(rows,cols);
siz = [rows,cols];
elements = rows*cols;
assn = find(X~=0);
unassn = find(X==0);

box = [1 2 3,[1 2 3]+rows,[1 2 3]+2*rows];
bnum = rows/3*cols/3;
bind = zeros(bnum,9);
for b = 1:bnum
bx = ceil(b/(cols/3));
by = b - (bx-1)*(cols/3);
bind(b,:) = box+(by-1)*3+(bx-1)*3*rows;
end
rind = zeros(rows,nmax);
for r = 1:rows
rind(r,:) = [1:rows:elements-rows+1] + r-1;
end
cind = zeros(cols,nmax);
for c = 1:cols
cind(c,:) = [1:rows] + (c-1)*rows;
end

%Initialise Y
Y = repmat([1:nmax],[elements,1]);
for i = assn'
Y(i,:) = 0;
Y(i,X(i)) = X(i);
end


%Calculate Y
while ~isempty(unassn)

for ind = unassn'

[i,j] = ind2sub(siz,ind);
%Check row
rowassn = find(X(rind(i,:))~=0);
Y(ind,X(rind(i,rowassn))) = 0;
%Check col
colassn = find(X(cind(j,:))~=0);
Y(ind,X(cind(j,colassn))) = 0;
%Check box
by = ceil(i/3);
bx = ceil(j/3);
b = by + 3*(bx-1);
boxassn = find(X(bind(b,:))~=0);
Y(ind,X(bind(b,boxassn))) = 0;
if sum(Y(ind,:)~=0)==1
X(ind) = Y(ind,find(Y(ind,:)~=0));
end
end

%Check row
for i = 1:rows
for n = 1:nmax
nind = find(Y(rind(i,:),n)==n);
if length(nind)==1
Y(rind(i,nind),:) = 0;
Y(rind(i,nind),n) = n;
X(rind(i,nind)) = n;
end
end
end

%Check col
for i = 1:cols
for n = 1:nmax
nind = find(Y(cind(i,:),n)==n);
if length(nind)==1
Y(cind(i,nind),:) = 0;
Y(cind(i,nind),n) = n;
X(cind(i,nind)) = n;
end
end
end

%Check box
for i = 1:bnum
for n = 1:nmax
nind = find(Y(bind(i,:),n)==n);
if length(nind)==1
Y(bind(i,nind),:) = 0;
Y(bind(i,nind),n) = n;
X(bind(i,nind)) = n;
end
end
end



unassn = find(X==0);
length(unassn)
pause

end

 

C++ (Michael)

So here is a c++ version that is intended to handle sudokus of various sizes(4x4,9x9,16x16...)
It was intended to be a short program, but it was a little trickier and longer than I thought. However it seems to be working for a couple of test puzzles.

#include <tchar.h>
#include <math.h>

#include <set>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>

#include <iostream>
#include <ostream>

#include <boost/smart_ptr.hpp>

//forward declarations
class Cell;
struct RowColumnBox;
class VectorMap;
class Grid;
class SolutionPoint;

// Convenient typedefs
typedef std::set<int> OptionsSet;
typedef std::map<int, Cell> GridMap;
typedef std::vector<int> GroupVector;
typedef std::map<int, GroupVector> GroupVectorCollection;
typedef std::map<int, RowColumnBox> CellLocationMap;
typedef std::pair<int,int> CellValuePair;
typedef std::queue<CellValuePair> SolvedQueue;

typedef boost::shared_ptr<VectorMap> VectorMapPtr;
typedef boost::shared_ptr<SolutionPoint> SolutionPointPtr;
typedef boost::shared_ptr<Grid> GridPtr;



// helper functions for determining important dimensions of the grid
inline int CellCount( int size ) { return static_cast<int>(pow( (double)size, 4)); }
inline int GridLength( int size ) { return size * size;}

// Just generates a sequence of numbers for filling in sequences into vectors etc
class SequenceGenerator {
int increment, current;
public:
SequenceGenerator(int inc, int start) : increment(inc), current(start - inc) {;}
int operator()() {
current += increment;
return current;
}
};

// Class holds all the available options for a cell
class Options {
OptionsSet options;
public:
Options(int size) {
std::generate_n( std::inserter(options, options.begin()), GridLength(size), SequenceGenerator(1, 1) );
}
Options(const Options& obj) : options(obj.options){
}
Options& operator=(const Options& obj ) {
options = obj.options;
//std::copy( obj.options.begin(), obj.options.end(), std::inserter( options, options.begin() ) );
}
// returns the value if there is only one possibility left else 0
int RemoveOption( int removeOption ) {
options.erase( removeOption );
return (options.size() == 1) ? *options.begin() : 0;
}
// returns a count of the available options for a cell
int GetCount() const { return static_cast<int>(options.size()); }
int GetGuessValue( int guessNumber ) const {
OptionsSet::const_iterator it = options.begin();
for( int i = 0; i < guessNumber; ++i, ++it );
return *it;
}
};

// One cell from the grid
class Cell {
int value;
Options options;
Cell& operator=(const Cell&); // at the moment don't need =
public:
Cell(int size) : options(size), value(0) {
}
Cell(const Cell& cell ) : value(cell.value), options(cell.options) {
}
// returns true if removing an option has solved the cell else false
int RemoveOption(int option) {
// if we have a value we no longer care about what we removing options
// but if it is already solved don't return the value
if( !value ) {
value = options.RemoveOption(option);
return value;
}
return 0;
}
// get/set for the value of the cell
void SetValue( int val ) { value = val; }
int GetValue() const { return value; }
// checks if the cell is solved
bool IsSolved() const { return (value != 0); }
//returns a count of the availble options for a cell
int GetOptionCount() const { return value ? 0 : options.GetCount(); }
// applies the guess number and returns the value guessed ( not equal to guessNumber )
int ApplyGuess( int guessNumber ) {
value = options.GetGuessValue( guessNumber );
return value;
}
};

// stores the row,column and box values for a cell
// 0 based so -1 means not set.
struct RowColumnBox {
int row;
int column;
int box;
RowColumnBox() : row(-1), column(-1), box(-1) {;}
};

// returns an iterator pointing to the location of the given cell
// if it cannot return a valid iterator an exception is thrown
CellLocationMap::iterator GetCellMapLocation( int cell, CellLocationMap& map ) {
CellLocationMap::iterator it = map.find( cell );
if( it == map.end() ) {
std::pair<CellLocationMap::iterator, bool> location
= map.insert( std::make_pair( cell, RowColumnBox() ) );
_ASSERT( location.second );
it = location.first;
}
return it;
}

// helper class for setting the row value
struct AddRowValueToCell{
AddRowValueToCell( CellLocationMap::iterator& it, int row ) {
it->second.row = row;
}
};
// helper class for setting the column value
struct AddColumnValueToCell{
AddColumnValueToCell( CellLocationMap::iterator& it, int column ) {
it->second.column = column;
}
};
// helper class for setting the box value
struct AddBoxValueToCell{
AddBoxValueToCell( CellLocationMap::iterator& it, int box ) {
it->second.box = box;
}
};

// adds all the items in the groupvector to the appropriate cell location map
// use one of the helper structs above for the template
template <typename T>
class AddCellToCellMap {
const int item;
CellLocationMap& map;
public:
AddCellToCellMap(int i, CellLocationMap& m) : item(i), map(m) {;}
void operator() ( const GroupVector::value_type& value ) {
CellLocationMap::iterator it = GetCellMapLocation( value, map );
T( it, item );
}
};

// add a vector of cells(either row/column/box) to the cell location map
// use one of the helper classes above for the template
template <typename T>
class AddCellsToMap {
CellLocationMap& map;
public:
AddCellsToMap( CellLocationMap& m ) : map(m) {;}
void operator() ( const GroupVectorCollection::value_type& val ) {
std::for_each( val.second.begin(), val.second.end(), AddCellToCellMap<T>( val.first, map ) );
}
};

// Contains maps for calculating row/column/box numbers from a given cell number
// and vice-versa
class VectorMap {
GroupVectorCollection rows;
GroupVectorCollection columns;
GroupVectorCollection boxes;
CellLocationMap cells;

static const int RowInc(int) { return 1; }
static const int ColumnInc( int size) { return GridLength( size ); }

// used for filling in the sequences for the rows/columns maps
void FillSequenceVector( GroupVectorCollection& col, int item, int inc, int start, int gridLength ) {
std::pair< GroupVectorCollection::iterator, bool>
insertPair = col.insert( std::make_pair( item, GroupVector() ));

std::generate_n( std::back_inserter( insertPair.first->second ),
gridLength, SequenceGenerator( inc, start ) );

}

// initialises the rows/columns/boxes maps
void InitCollectionMaps(int size) {
const int gridLength = GridLength(size);
for( int item = 0; item < gridLength; ++item ) {

int boxRow = item / size; int boxCol = item % size;
int box = boxCol + boxRow * size;
int boxStart = boxRow * GridLength(size) * size + boxCol * size;
int rowStart = item * GridLength(size); int colStart = item;

FillSequenceVector( rows, item, RowInc(size), rowStart, gridLength );
FillSequenceVector( columns, item, ColumnInc(size), colStart, gridLength );

// the box is a little more tricky so can't just call FillVector
std::pair< GroupVectorCollection::iterator, bool>
insertPair = boxes.insert( std::make_pair( item, GroupVector() ));
for( int i = 0; i < size; ++i ) {
std::generate_n( std::back_inserter(insertPair.first->second), size,
SequenceGenerator(RowInc(size), i * GridLength(size) + boxStart) );

}
}
}


// loops through the rows/columns/boxes and fills in the cell location map
void InitCellLocationMap(int size) {
std::for_each(rows.begin(), rows.end(), AddCellsToMap<AddRowValueToCell>(cells));
std::for_each(columns.begin(), columns.end(), AddCellsToMap<AddColumnValueToCell>(cells));
std::for_each(boxes.begin(), boxes.end(), AddCellsToMap<AddBoxValueToCell>(cells));
}

VectorMap(const VectorMap&);
VectorMap& operator=(const VectorMap&);
public:
VectorMap(int size)
{
InitCollectionMaps( size );
InitCellLocationMap(size );
}

// returns the row number for a given cell number
int GetRow( int cell ) const {
CellLocationMap::const_iterator it = cells.find(cell);
return it == cells.end() ? -1 : it->second.row;
}

// returns the column number for a given cell number
int GetColumn( int cell ) const {
CellLocationMap::const_iterator it = cells.find(cell);
return it == cells.end() ? -1 : it->second.column;
}

// returns the box number for a given cell number
int GetBox( int cell ) const {
CellLocationMap::const_iterator it = cells.find(cell);
return it == cells.end() ? -1 : it->second.box;
}

// need better error checking on these three accessors

const GroupVector& GetRowVector( int row ) const {
return rows.find( row )->second;
}

const GroupVector& GetColumnVector( int column ) const {
return columns.find( column )->second;
}

const GroupVector& GetBoxVector( int box ) const {
return boxes.find( box )->second;
}
};

// predicate for searching for cells with the right number of possibilities
struct CheckOptionCount
: public std::binary_function<GridMap::value_type, int, bool> {
bool operator()(const GridMap::value_type& value, const int& desiredOptionCount) const {
return (value.second.GetOptionCount() == desiredOptionCount);
}
};

class Grid {
const int gridSize;
int solvedCount;
GridMap grid;
VectorMapPtr map;
SolvedQueue solved;

Grid& operator=(const Grid&);
public:
// The initial grid is just 1d since we don't want to hard code in the 2d dimensions
Grid( int size, const int initialGrid[] ) : gridSize(size), map( new VectorMap(size)),
solvedCount(CellCount(size)) {
// generate a blank grid
std::generate_n( std::inserter( grid, grid.begin()), CellCount(size), CellInit(grid, gridSize));
//set the initial variables
const int gridLength = GridLength(size);
for(int row = 0; row < gridLength; ++ row ) {
for(int col = 0; col < gridLength; ++ col){
const int cell = row * gridLength + col;
if( initialGrid[cell] ) { // most cells are 0 at the start(ie. blank)
SetCellValue( cell, initialGrid[cell] );
}
}
}
SetSolvedQSolved();//start off solution
}

Grid( const Grid& obj ) : //copy constructor
gridSize(obj.gridSize),
map(obj.map),
solvedCount(obj.solvedCount),
solved(obj.solved),
grid(obj.grid){
}

// returns true if the grid is solved
bool IsGridSolved() const { return solvedCount == 0; }
int GetCellsToSolveCount() const { return solvedCount; }

VectorMapPtr GetMapPtr() const { return map; }

// returns true if there are items in the solved queue that need to be dealt to
bool IsSolvedQEmpty() const { return solved.empty(); }

// If we need to guess then returns the square with the least possible options
// i.e. searches first for cells that have only 2 possible values and then
// for cells with 3. (we want to find the cell with the best possible chance
// of picking the right cell
int GetBestGuessSquare() const {
if( IsGridSolved() ) {
return -1;
}
int result = -1;
const int maxCount = GridLength( gridSize ) + 1;
for(int desiredCount = 2; desiredCount < maxCount; ++ desiredCount ) {
GridMap::const_iterator it = std::find_if( grid.begin(), grid.end(), std::bind2nd( CheckOptionCount(), desiredCount ));
if( it != grid.end() ) {
result = it->first;
break;
}
}
return result;
}

void Guess(int cell, int guessNumber ) {
int value = grid.find(cell)->second.ApplyGuess( guessNumber );
_ASSERT( value );
AddCellToSolvedQueue( cell, value );
SetSolvedQSolved();
}

//check to see if the grid is in an invalid state ( useful after applying guesses )
bool IsGridValid() const {
GridMap::const_iterator it = std::find_if( grid.begin(), grid.end(), CheckGridValid(*this));
return it == grid.end();
}

// returns the current value of a given cell
int GetCellValue(int cell) const {
return grid.find(cell)->second.GetValue();
}

// returns a count of the available options
int GetOptionCount(int cell) const {
return grid.find(cell)->second.GetOptionCount();
}

// draws a grid to the ostream source -- the _T macro reduces readibility
void DisplayGrid( std::ostream& os ) const{
os << "\r\n";
const int gridLength = GridLength( gridSize );
for(int row = 0; row < gridLength; ++row ) {
for(int col = 0; col < gridLength; ++ col ) {
int cell = col + row * gridLength;
os << grid.find(cell)->second.GetValue() << " ";
}
os << "\r\n"; // new line
}
os << "\r\n";
}

private:

// helper class for initialising the blank grid
class CellInit {
int current;
const int size;
GridMap& map;
public:
CellInit(GridMap& m, int gridSize) : current(0), map(m),size(gridSize) {;}
GridMap::value_type operator()() {
return std::make_pair( current++, Cell(size));
}
};

// helper class for removing a value from a cell
class RemoveCellValue {
const int value;
Grid* grid;
public:
RemoveCellValue( int v , Grid* g ) :value(v), grid(g) {;}
void operator()( const GroupVector::value_type& cell ) {
// if there is notification of a forced select then add it to the
int solvedValue = grid->RemoveValue( cell, value );
if( solvedValue ) {
grid->AddCellToSolvedQueue( cell, solvedValue );
}
}
};

// searches to find if the grid is invalid - ie. true if invalid ( false if valid )
class CheckGridValid : public std::binary_function<GridMap::value_type, Grid, bool>
{
const Grid& grid;
public:
CheckGridValid(const Grid& g) : grid(g) {;}
bool operator()( const GridMap::value_type& value ) const {
const VectorMapPtr ptr = grid.GetMapPtr();
if(CheckVector( ptr->GetColumnVector( ptr->GetColumn( value.first )), value, grid ))
return true;
if(CheckVector( ptr->GetRowVector( ptr->GetRow( value.first )), value, grid ))
return true;
if(CheckVector( ptr->GetBoxVector( ptr->GetBox( value.first )), value, grid ))
return true;
return false;
}
private:
bool CheckVector( const GroupVector& vec, const GridMap::value_type& value, const Grid& grid ) const{
GroupVector::const_iterator it = std::find_if( vec.begin(), vec.end(), std::bind2nd( CheckCellValueExists(grid), value ) );
return it != vec.end();
}
};
// check that a cell matches the
class CheckCellValueExists : public std::binary_function<GroupVector::value_type, GridMap::value_type, bool>
{
const Grid& grid;
public:
CheckCellValueExists( const Grid& g ) : grid(g) {;}
bool operator()( const GroupVector::value_type& value, const GridMap::value_type& testValue ) const {
bool result = false;
if( testValue.second.GetValue() && value != testValue.first ) { //don't want to be comparing itself or checking zeros
result = ( grid.GetCellValue( value ) == testValue.second.GetValue() );
}
return result;
}
};

// sets a solved value
void SetCellValue( int cell, int value ) {
grid.find(cell)->second.SetValue( value );
RemoveSolvedValue( cell, value );
--solvedCount;
}

// removes a solved value from the other rows/columns/boxes
void RemoveSolvedValue( int cell, int value ) {
RemoveRowCellValue( map->GetRow( cell ), value );
RemoveColumnCellValue( map->GetColumn( cell ), value );
RemoveBoxCellValue( map->GetBox( cell ), value );
}

// removes a value from all the squares in a row
void RemoveRowCellValue( int row, int value ) {
std::for_each(map->GetRowVector(row).begin(), map->GetRowVector(row).end(), RemoveCellValue(value, this));
}
// removes a value from all the squares in a column
void RemoveColumnCellValue( int column, int value ) {
std::for_each(map->GetColumnVector(column).begin(), map->GetColumnVector(column).end(), RemoveCellValue(value, this));
}
// removes a value from all the squares in a box
void RemoveBoxCellValue( int box, int value ) {
std::for_each(map->GetBoxVector(box).begin(), map->GetBoxVector(box).end(), RemoveCellValue(value, this));
}
// removes a value from a cell
int RemoveValue( int cell, int value ) {
return grid.find(cell)->second.RemoveOption( value );
}

// adds a cell to the solved queue
void AddCellToSolvedQueue( int cell, int value ) {
solved.push( std::make_pair( cell, value) );
}

// loops throught the solved queue and removes the value from the rows/colums/boxes
void SetSolvedQSolved() {
while( !solved.empty() && solvedCount ) {
const CellValuePair pair = solved.front();
solved.pop();
RemoveSolvedValue( pair.first, pair.second );
--solvedCount;
}
}

};

// Stores a copy of the grid and the status of the guesses at a given point
class SolutionPoint {
GridPtr grid; // the grid before the guess
int guessCell; // the cell we are guessing
int guessNumber; // the guess number that we are going to try next(NOT THE VALUE OF THE GUESS )
int guessCount; // the number of possible guesses for that cell
public:
SolutionPoint( const Grid& g, int cell ) : grid( new Grid(g) ),
guessNumber(0), guessCell(cell) {
guessCount = g.GetOptionCount(cell);
}
bool TriedAllGuesses() const { return guessNumber == guessCount; }
// applies the next guess to a copy of the stored grid
// returns a pointer the the grid once it is solved
GridPtr ApplyNextGuess() {
_ASSERT( !TriedAllGuesses() );
GridPtr ptr = GridPtr( new Grid( *grid ) );
ptr->Guess( guessCell, guessNumber++ );
return ptr;
}
};

// Class that performs the solving of the grid
class GridSolver {
GridPtr mainGrid; // the grid on which all the working is performed
bool solved; // is the current mainGrid solved
GridSolver(const GridSolver&);
GridSolver& operator=(const GridSolver&);
public:
GridSolver( int size, const int initialGrid[] ) :
mainGrid( new Grid( size, initialGrid)) {
solved = mainGrid->IsGridSolved();
_ASSERT( mainGrid->IsGridValid()); // this will pick up bad initial grids ( at least in debug )
}

// call this to solve the grid
bool Solve() {
if( !solved )
RecursiveGuessLoop( CreateGuessPoint() );
_ASSERT( !solved || mainGrid->IsGridValid() );
return solved;
}

void DisplayGrid( std::ostream& os ) const {
mainGrid->DisplayGrid( os );
}
private:
// recursive function for applying guesses until we find a solution
// ( or run out of guesses )
void RecursiveGuessLoop( const SolutionPointPtr& ptr ) {
while(!solved && !ptr->TriedAllGuesses() ) {
mainGrid = ptr->ApplyNextGuess();
if( !mainGrid->IsGridSolved() ) {
RecursiveGuessLoop( CreateGuessPoint() ); // recursion
} else if( mainGrid->IsGridValid() ) {
solved = true;
break;
}
}
}

// just a convient function to help me type a long line -> I'm too lazy
inline SolutionPointPtr CreateGuessPoint() const{
return SolutionPointPtr( new SolutionPoint( *mainGrid, mainGrid->GetBestGuessSquare() ));
}
};


const int puzzle2[] = {
1,0,0,2,
0,2,0,0,
0,0,4,0,
0,3,0,0 };

const int puzzleTest[] = {
0,6,0,1,0,4,0,5,0,
0,0,8,3,0,5,6,0,0,
2,0,0,0,0,0,0,0,1,
8,0,0,4,0,7,0,0,6,
0,0,6,0,0,0,3,0,0,
7,0,0,9,0,1,0,0,4,
5,0,0,0,0,0,0,0,2,
0,0,7,2,0,6,9,0,0,
0,4,0,5,0,8,0,7,0 };

const int puzzlePress1[] = {
7,0,0,4,0,0,3,0,0,
0,0,0,0,0,1,7,0,0,
0,2,0,0,0,0,9,0,1,
0,0,1,0,4,0,2,0,0,
0,6,0,8,9,7,0,3,0,
0,0,8,0,2,0,5,0,0,
3,0,9,0,0,0,0,1,0,
0,0,7,9,0,0,0,0,0,
0,0,2,0,0,5,0,0,3 };

const int puzzleHard1[] = {
6,0,0,0,0,0,0,4,0,
0,0,5,0,0,2,0,0,7,
7,2,9,0,0,0,0,0,3,
0,9,0,0,4,0,0,0,1,
0,0,0,0,6,0,0,0,0,
4,0,0,0,8,0,0,7,0,
3,0,0,0,0,0,1,6,5,
2,0,0,4,0,0,8,0,0,
0,5,0,0,0,0,0,0,4 };

const int puzzleHard2[] = {
0,0,9,0,8,0,0,0,4,
0,6,0,0,0,0,0,0,8,
5,2,8,0,6,0,1,7,0,
2,0,0,7,0,0,0,0,5,
0,0,0,4,0,6,0,0,0,
9,0,0,0,0,1,0,0,6,
0,9,7,0,3,0,4,6,1,
6,0,0,0,0,0,0,3,0,
3,0,0,0,4,0,9,0,0 };


int _tmain(int argc, _TCHAR* argv[])
{
GridSolver solver(3, puzzleTest);
std::cout << "Solved = " << solver.Solve() << std::endl;
solver.DisplayGrid(std::cout);

GridSolver solver2(2, puzzle2);
std::cout << "Solved = " << solver2.Solve() << std::endl;
solver2.DisplayGrid(std::cout);

GridSolver solver3(3, puzzlePress1);
std::cout << "Solved = " << solver3.Solve() << std::endl;
solver3.DisplayGrid(std::cout);

GridSolver solver4(3, puzzleHard2);
std::cout << "Solved = " << solver4.Solve() << std::endl;
solver4.DisplayGrid(std::cout);

GridSolver solver5(3, puzzleHard1);
std::cout << "Solved = " << solver5.Solve() << std::endl;
solver5.DisplayGrid(std::cout);

return 0;
}

By some miracle it is looking pretty good - ( I managed to correct a bug in my recursive function which was causing some grief )
Here is a brief explanation of what I think I did ( any resemblance to actual code is purely coincidental )
Notes:
1) There are quite a few classes just used as predicates for stl algorithms
2) The grid dimensions are given as 2 for a 4x4, 3 for a 9x9, 4 for a 16x16 etc and the solver should be able to solve any of these...(the 2x2 test works well
3) The main classes:
Options holds a list of the possible values for a cell basically just a vector that starts of with all the possible numbers (1...9) and erases them as they are no longer a possibilty
Cell
A representation of a sudoku cell. Stores a value for the cell (0 if unassigned ) and a list of possible options for the cell.
Grid Contains a map of all the cells in the sudoku grid. Cells are number from 0 at the top left corner the the 1,2,3 moving along the row and finally 81 in the bottom right hand corner.
VectorMap Basically maps a cell number to a row number, column number, and box number. Also contains lists of all the cells each row/column/box.
SolutionPoint Keeps track of the current guess we are making.
GridSolver Implements the recursive solving mechanism.
All the other class/struct are just helpers for the stl functions i.e. std::find_if, std::for_each, etc
How it works:
1) In the grid constructor:
a) Creates a blank grid with each cell having all options available.
b) Starts adding the given numbers. This involves setting the value in the cell and removing that value as an option from the other cells in the same row/column/box.
note: as options are removed from a cell, that cell may reach the point where there is only one remaining value and hence is solved. In this case the cell is added to the solved queue.
c) Iterates through the solved queue and removes value of the solved cell from the option list in the same row/column/box
For easy/medium puzzles step c is usually self sustaining and when it is completed the puzzle is solved.
If this is not the case then we need some more advanced logic, or for the lazy, guessing. I went with guessing.
2) In the GridSolver.Solve Function
- check that the grid was not solved as described above. Then guess
a) find the first cell with the minimum of options ( so there is a good chance of guessing correctly ) ie. search for cells with 2 possibilties then 3..4..5 etc
b) Choose the next guess ( storing a copy of the current grid /which guess etc )
c) Iterates through the solved queue and removes value of the solved cell from the option list in the same row/column/box
d) Check if there is a solution -> (no) goto step a  (yes)continue
e) Check if the solution is valid -> (no) retreat to the last guess point and goto step b (yes) solved!!!!111!!!!one1!!!11eleven!!!!
steps a-d are implemented as a recursive function.
The solver should work

www.codeproject.com/csharp/sudoku.asp

| | # 

This was an older blog post from 2006, and I found the text from ‘The Wayback Machine’ ie web.archive.org, on davemateer.com

Whilst reading Simon Sing's - The Code Book (www.simonsingh.com)  I thought it would be fun to write a code guessing program.  My first try was in Visual Basic6, then I ported it over to C#.  Phil decided he'd have a go and wrote it in Python then Java.  Then Dan wrote it in C.  We were all intrigued as to how fast each language would be, and who would be the winner?


This program takes say x letters from lowercase a to z, in as a secretString (in all cases we used 'davedave' for 8, then 'davedav' for 7 etc..)  Then it tries to guess the secretString by starting at aaaaaaaa and finishing at zzzzzzzz (for the 8 length example).  It was not allowed guess each letter individually, it had to guess the entire string correctly.

My machine ran an Athlon 1500+ processor with 0.75gig of RAM, and WinXPSP2.

image

So Cv1.1 and C#v3 got pretty close.

C# v2 (thanks to Kelly)

namespace pattern_string_version2 

{

class Program

{

static void Main(string[] args)

{

string secretString = "davedave";

int counter = 0;



byte[] ts = new byte[8];



string timeStart;

string timeEnd;

timeStart = DateTime.Now.Hour.ToString() + ":" + DateTime.Now.Minute.ToString() + ":" + DateTime.Now.Second.ToString();

Console.WriteLine("time at start is {0}", timeStart);



//loop 1

for (byte i = 97; i < 123; i++)

{

//loop2

for (byte j = 97; j < 123; j++)

{

//loop3

for (byte k = 97; k < 123; k++)

{

//loop4

for (byte l = 97; l < 123; l++)

{

//loop5

for (byte m = 97; m < 123; m++)

{

//loop6

for (byte n = 97; n < 123; n++)

{

//loop7

for (byte o = 97; o < 123; o++)

{

//loop8

for (byte p = 97; p < 123; p++)

{

ts[0] = i;

ts[1] = j;

ts[2] = k;

ts[3] = l;

ts[4] = m;

ts[5] = n;

ts[6] = o;

ts[7] = p;



counter++;



string ts2 = System.Text.ASCIIEncoding.ASCII.GetString(ts, 0,8);



if (ts2.Equals(secretString))

{

Console.WriteLine("Found secret which is {0} after {1} pattern matches", ts, counter);

Console.WriteLine();

timeEnd = DateTime.Now.Hour.ToString() + ":" + DateTime.Now.Minute.ToString() + ":" + DateTime.Now.Second.ToString();

Console.WriteLine("time at end is {0}", timeEnd);

break;

}// End if

} //end loop 8

} // end loop 7

}// end loop 6

}//end loop5

}//end loop4

}//end loop3

}//end loop2

}//end loop1

}// End Main

}// End Program

}// End Namespace
 
 

C# V3 (thanks Dave Mulh, Phil, Darrin) – nested version

This may be the fastest C#?

using System;
using System.Text;

namespace pattern_string_version3
{
class PatternMatch
{
static void Main(string[] args)
{
byte[] SecretBytes = Encoding.UTF8.GetBytes("davedav");
//int counter = 0;
// A 64 bit type giving a large number
ulong counter = 0;
byte[] ComparisonBytes = new byte[7];
string timeStart;
string timeEnd;

timeStart = DateTime.Now.Hour.ToString() + ":" + DateTime.Now.Minute.ToString() + ":" + DateTime.Now.Second.ToString();

//loop 1
for (byte i = 97; i < 123; i++)
{
ComparisonBytes[0] = i;
//loop2
for (byte j = 97; j < 123; j++)
{
ComparisonBytes[1] = j;
//loop 3
for (byte k = 97; k < 123; k++)
{
ComparisonBytes[2] = k;
//loop4
for (byte l = 97; l < 123; l++)
{
ComparisonBytes[3] = l;
//loop 5
for (byte m = 97; m < 123; m++)
{
ComparisonBytes[4] = m;
//loop6
for (byte n = 97; n < 123; n++)
{
ComparisonBytes[5] = n;
//loop7
for (byte o = 97; o < 123; o++)
{
ComparisonBytes[6] = o;
//loop8
//for (byte p = 97; p < 123; p++)
//{
// ComparisonBytes[7] = p;

counter++;

//bool match = CompareByteArrays(ComparisonBytes,SecretBytes);
if (CompareByteArrays(ComparisonBytes, SecretBytes))
{
timeEnd = DateTime.Now.Hour.ToString() + ":" + DateTime.Now.Minute.ToString() + ":" + DateTime.Now.Second.ToString();
string matchedString = System.Text.ASCIIEncoding.ASCII.GetString(ComparisonBytes, 0, 7);
Console.WriteLine("Found secret which is {0} after {1} pattern matches", matchedString, "counter");
Console.WriteLine();
Console.WriteLine("time at start is {0}", timeStart);
Console.WriteLine("time at end is {0}", timeEnd);
Console.WriteLine("counter is {0}", counter);
break;
}// End
//} //end loop 8
}//end loop 7
} // end loop 6
}// end loop 5
} //end loop 4
} // end loop 3
}// end loop 2
}//end 1
//we failed, so output error
Console.WriteLine("Didn't Found secret which after {0} pattern matches", "counter");
Console.WriteLine("time at start is {0}", timeStart);
Console.WriteLine("time at end is {0}", DateTime.Now.Hour.ToString() + ":" + DateTime.Now.Minute.ToString() + ":" + DateTime.Now.Second.ToString());
Console.ReadLine();
}// End Main

public static bool CompareByteArrays(byte[] data1, byte[] data2)
{
for (int i = 0; i < 7; i++)
{
if (data1[i] != data2[i])
{
return false;
}
}
return true;
}
}// End Program
}// End Namespace


C# (Kelly’s Byte by Byte cheat!)

using System;
using System.Text;

namespace Proto

{

/// <summary>

/// Summary description for Class1.

/// </summary>

class Class1

{

/// <summary>

/// The main entry point for the application.

/// </summary>

[STAThread]

static void Main( string [] args)

{

byte [] SecretBytes = Encoding.UTF8.GetBytes("davedave");

byte [] ComparisonBytes = new byte [8] {97,97,97,97,97,97,97,97};

int index = 0;

string timeStart = String.Format("{0}:{1}:{2}", DateTime.Now.Hour.ToString(), DateTime.Now.Minute.ToString(), DateTime.Now.Second.ToString());

// Start Processing

while (SecretBytes.Length > index)

{

ComparisonBytes[index]++;

if (ComparisonBytes[index].Equals (SecretBytes[index]))

index++;

}

// End Processing

string timeEnd = String.Format("{0}:{1}:{2}", DateTime.Now.Hour.ToString(), DateTime.Now.Minute.ToString(), DateTime.Now.Second.ToString ());

string matchedString=System.Text.ASCIIEncoding .ASCII.GetString(ComparisonBytes, 0,8);

Console.WriteLine("Found secret which is {0} after {1} pattern matches",matchedString, "counter");

Console.WriteLine();

Console.WriteLine("time at start is {0}", timeStart);

Console.WriteLine("time at end is {0}", timeEnd);

Console.ReadLine();

}

}

}

PHP

PHP Code

Run from the command line eg php pattern.php

<?

$startTime = time();

echo "starting pattern match started <br \>";



$secretString = "daveda";

// loop1

for ($i = 97; $i < 123; $i ++)

{

$iChar = chr($i);

// loop2

for ($j = 97; $j < 123; $j++)

{

$jChar = chr($j);

// loop 3

for ($k = 97; $k < 123; $k++)

{

$kChar = chr($k);

// loop 4

for ($l = 97; $l < 123; $l++)

{

$lChar = chr($l);

// loop 5

for ($m = 97; $m < 123; $m++)

{

$mChar = chr($m);

// loop 6

for ($n = 97; $n < 123; $n++)

{

$nChar = chr($n);

$tryString = $iChar . $jChar . $kChar . $lChar . $mChar . $nChar;

if ($tryString == $secretString) {

echo "found secretString which is $tryString <br />" ;

$endTime = time();

$totalTime = $endTime - $startTime;

echo "Time taken in seconds is $totalTime <br />";

}// end if

} // end loop 6

} // end loop 5

} // end loop 4

} // end loop 3

}// end loop2

}// end loop1

?>

C (thanks to Dan)

Compiled with GCC, and run under Cygwin.
#include <stdio.h>
#include <time.h>

int main()
{
char * secretString = "davedave";
char tryString[10];
unsigned int counter = 0;
int i,j,k,l,m,n,o,p;
time_t start,end;

double dif;

unsigned int timeStart;
unsigned int timeEnd;

time (&start);

for (i = 'a'; i <= 'z'; i++)
{
for (j = 'a'; j <= 'z'; j++)
{
for (k = 'a'; k <= 'z'; k++)
{
for (l = 'a'; l <= 'z'; l++)
{
for(m = 'a'; m <= 'z'; m++)
{
for(n = 'a'; n <= 'z'; n++)
{
for(o = 'a'; o <= 'z'; o++)
{
for(p = 'a'; p <= 'z'; p++)
{
tryString[0] = (char)i;
tryString[1] = (char)j;
tryString[2] = (char)k;
tryString[3] = (char)l;
tryString[4] = (char)m;
tryString[5] = (char)n;
tryString[6] = (char)o;
tryString[7] = (char)p;
tryString[8] = '\0';

if ( strcmp( secretString, tryString ) == 0 )
{
time (&end);
dif = difftime (end, start);
printf( "\r\nSecretString is %s", tryString );
printf( "\r\nNumber combinations tried = %d", counter );
printf ("\r\nYou have taken %.2lf seconds to type your name.\n", dif );
return 1;
}
else
{
counter++;
}
}
}
}
}
}
}
}
}
printf("\r\nDid not find secret string %s after %d combinations", secretString, counter );
}
 

C v1.1 (thanks to Darrin)

This may be the fastest so far?

#include <stdio.h> 
#include <time.h>

int main()
{
char * secretString = "davedav";
char tryString[10];
unsigned int counter = 0;
int i,j,k,l,m,n,o,p;
time_t start,end;
double dif;

unsigned int timeStart;
unsigned int timeEnd;
time (&start);

for (i = 'a'; i <= 'z'; i++)
{
tryString[0] = i;
for (j = 'a'; j <= 'z'; j++)
{
tryString[1] = j;
for (k = 'a'; k <= 'z'; k++)
{
tryString[2] = k;
for (l = 'a'; l <= 'z'; l++)
{
tryString[3] = l;
for(m = 'a'; m <= 'z'; m++)
{
tryString[4] = m;
for(n = 'a'; n <= 'z'; n++)
{
tryString[5] = n;
for(o = 'a'; o <= 'z'; o++)
{
tryString[6] = o;
//for(p = 'a'; p <= 'z'; p++)
//{
//tryString[7] = p;
tryString[7] = '\0';
if ( strcmp( secretString, tryString ) == 0 )
{
time (&end);
dif = difftime (end, start);
printf( "\r\nSecretString is %s", tryString );
printf( "\r\nNumber combinations tried = %d", counter );
printf ("\r\nYou have taken %.2lf seconds to type your name.\n", dif );
return 1;
}
else
{
counter++;
}
//}
}
}
}
}
}
}
}
printf("\r\nDid not find secret string %s after %d combinations", secretString, counter );
}


C v2 (thanks to Dan) uses pointers

#include <stdio.h>
#include <time.h>

// This is the maximum length of the string we are trying to guess
#define MAX_SECRET_STRING_LENGTH 16

int
main( void )
{
char tryString[MAX_SECRET_STRING_LENGTH];
char *secretString = "davedav";
unsigned int numComparisons;
int strLen;
int i;
time_t start,end;
unsigned int timeStart;
unsigned int timeEnd;
double dif;

time (&start);

// Setting up start point of guesser
strLen = 0;
tryString[0] = 'a';
tryString[1] = '\0';
numComparisons = 0;
while ( 1 )
{
numComparisons++;
// Check if this is the string we're after
if ( !strcmp( tryString, secretString ) )
{
time (&end);
dif = difftime (end, start);
// We have found the string!
printf( "Secret string is: %s\r\n", tryString );
printf( "Number of comprisons: %d\r", numComparisons );
printf ("\r\nCode took %.2lf seconds to run.\n", dif );
return;
}

// String doesn't match so increment the most right hand character
tryString[strLen]++;

// Is most right hand character z?
if ( tryString[strLen] == 'z' )
{
// We need to roll one or more characters over to 'a'
// Count i backwards from strLen to 0
for ( i = strLen; i >= 0; i-- )
{
// Is the character at position i equal to z? It always will be on
// the first loop
if ( tryString[i] == 'z' )
{
// Have we reached position 0 ie the start of the string?
if ( i == 0 )
{
// We have just rolled over all the characters in our current try
// string and have not yet found a match. We must now try with
// a string 1 character longer.
strLen++;
tryString[0] = 'a';
tryString[strLen] = 'a';
// Delimit the string for the comparison
tryString[strLen + 1] = '\0';
break;
}
else
{
// We haven't reached the beginning of string, so set current character
// to a and previous character increment
tryString[i] = 'a';
tryString[i - 1]++;
}
}
else
{
// If we are not incrementing this character then we won't be
// incrementing any characters before it either. So break out of the for i loop
// and start incrementing the most right hand character again.
break;
}
} //for i...
} //if
} //while
}//main

C++ (thanks to Michael) Recursive Loop Simplified Version

Its performance is handicapped by its iterative deepening search method, oh well.

// MikesRecursivePattern.cpp : main project file.
#include "stdafx.h"
#include <iostream>
#include <string>
#include <time.h>

using std::string;

// what length of string will it search for before it gives up...
const int MAX_SEARCH_LENGTH = 8;
string secretString, guess;
int iterations = 0;

// checks to see it the string matches the secret string
bool CompareString() {
++iterations;
return !guess.compare( secretString );
}

// recursive function for scanning string
bool SearchString( string::iterator it )
{
bool result = false;
if( it != guess.end() ) {
for( int letter = 97; letter < 123 && !result; ++letter ) {
*it = (char)letter;
if( result = CompareString() )
break;
result = SearchString( it + 1 );
}
}
return result;
}

int main()
{
std::cout << "Enter string to search for -->";
std::getline( std::cin, secretString );
time_t start,end;
time( &start );

for(int tryLength = 0; tryLength < MAX_SEARCH_LENGTH; ++tryLength ){
guess += "a";
if( SearchString( guess.begin() ) )
break;
}
time( &end );

if( CompareString() ) {
std::cout << "secret string: " << guess.c_str() << "\n";
} else {
std::cout << "failed to find string. aaargh\n";
}

std::cout << "iterations: " << iterations << "\n";
std::cout << "time (secs): " << difftime (end, start) << "\n";
//stop the nasty app closing without showing results
std::getline( std::cin, secretString );
}

C++ (thanks to Michael) Full Version

1) will find any length string you enter
2) the letters aren't hardcoded and can be changed but adding/subtracting to the letters string.  ( if you replace this with the searching section from the c code then it ought to be equally speedy )
At the moment it is windows only, but that is only the timing code.

 

#ifdef _WIN32 
#define WINVER 0x0500
#define _WIN32_WINNT 0x0500
#define _WIN32_IE 0x0501

#include <windows.h>
#endif

#include <iostream>
#include <string>

// what length of string will it search for before it gives up...
const int MAX_SEARCH_LENGTH = 8;

// define the letters to search for ie. possible secret string letters/symbols etc
const std::string letters = "abcdefghijklmnopqrstuvwxyz";
// the letters string doesn't change
const std::string::const_iterator itLettersEnd = letters.end();

std::string secretString;


// counter
int iterations = 0;

// checks to see it the string matches the secret string
bool CompareString( const std::string& test ) {
++iterations;
return test.compare( secretString ) == 0;
}

// performs the search
class Search {
std::string test_;
// recursive function that searches the string
bool SearchString( std::string::iterator it ) {
bool result = false;
if( it != test_.end() ) {
// search all possible letters
for( std::string::const_iterator itLetter = letters.begin(); itLetter != itLettersEnd && !result; ++itLetter ) {
*it = *itLetter; if( CompareString( test_ ) ) {
result = true;
break;
}
// move to the next letter and call this function
result = SearchString( it + 1 ); } } return result;
}

public:
// constructor requires length of string to search
Search( int length ) : test_( length, 'a') {}

const char* GetString() const { return test_.c_str(); }
// call this to start the recursive search
bool SearchString() {
return SearchString( test_.begin() );
}
};


int main()
{
std::cout << "Enter string to search for -->";
std::getline( std::cin, secretString );
std::string result = "";
LARGE_INTEGER start;
QueryPerformanceCounter( &start );

for(int tryLength = 0; tryLength < MAX_SEARCH_LENGTH; ++tryLength ){
Search tryString(tryLength + 1);
if( tryString.SearchString() ) {
result = tryString.GetString();
break;
}
}


LARGE_INTEGER finish;
QueryPerformanceCounter( &finish );
LARGE_INTEGER freq;
QueryPerformanceFrequency( &freq );
double totalTime = (double)(finish.QuadPart - start.QuadPart) / freq.QuadPart;

if( !result.empty() ) {
std::cout << "secret string: " << result.c_str() << "\n";
} else {
std::cout << "failed to find string, aaargh\n"; }
std::cout << "iterations: " << iterations << "\n";
std::cout << "time (secs): " << totalTime << "\n";
//stop the nasty app closing immediately
std::getline( std::cin, secretString );
}
 

C++ Mininal Crazy Version (thanks to Michael)

I sacrificed speed somewhat for the sake of making it difficult to understand.
All the other programs on your site seemed to be taking it seriously! (it is only partially
obfuscated currently... just wait 'till I'm finished  ) As you will be able to tell it uses a
somewhat different approach from the other programs, although it still is a simple loop.
Anyway on my machine it runs about 80 seconds for 7 letters. This is handicapped by
searching the wrong direction: In reverse; vadevad takes only 10 secs.


davedave: -> 610 seconds
evadevad: -> 396 seconds


Maybe you need a palindrome? ( or maybe i should just reverse my algorithm ;-)   )
Anyway my code is pretty short (the algorithm is 6 lines) so here goes...

#include <iostream> 
#include <string>
#include <time.h>

typedef unsigned __int64 E;

int main()
{
std::cout << "Enter string to search for (12 letters max)...\n>> ";
char c, s[12]; std::cin >> s;
time_t b,f;
time( &b);

E y=0,e=0; int p, l = strlen( s ); for(p=0;p<l;e|=(E)p[s]-97<<p++*5);
for(;y!=e;++y); std::string O = "";
for(p=0;p<l;O+=97+((e>>p++*5)&31));
time( &f);
double t = difftime( f, b );
std::cout << "secret string: " << O.c_str() << std::endl;
std::cout << "iterations: " << y << std::endl;
std::cout << "time (secs): " << t << std::endl; }


Whew! There it goes This ought to work several compilers (with an appropriate substitution for the __int64 typedef for non-microsoft ones )

Also if you happen to have a 64bit machine lying I'm confident you could give this program a significant performance boost, since everything is, well, 64bit numbers.


Java (thanks to Phil)

import java.util.*;

public class RunMe {


public static void main(String[] args) {

int l1,l2,l3,l4,l5,l6,loop;
String a1,a2,a3,a4,a5,a6;
String secret,testword;
Date date;
long start,finish;
date = new Date();
start = date.getTime();
secret = "daveda";
loop=0;
for (l1=97;l1<=122;l1++){
for (l2=97;l2<=122;l2++){
for (l3=97;l3<=122;l3++){
for (l4=97;l4<=122;l4++){
for (l5=97;l5<=122;l5++){
for (l6=97;l6<=122;l6++){
byte[] bytes = new byte[1];
bytes[0] = (byte) l1;
a1 = new String(bytes);
bytes[0] = (byte) l2;
a2 = new String(bytes);
bytes[0] = (byte) l3;
a3 = new String(bytes);
bytes[0] = (byte) l4;
a4 = new String(bytes);
bytes[0] = (byte) l5;
a5 = new String(bytes);
bytes[0] = (byte) l6;
a6 = new String(bytes);

testword = a1 + a2 + a3 + a4 +a5 +a6;

loop = loop + 1;
if (testword.equals(secret)){
date = new Date();
finish = date.getTime();
System.out.println("Task completed in: (milliseconds) (loops):");
System.out.println(finish-start);
System.out.println (Integer.toString(loop));
}
}//loop 6
}//loop 5
}//loop 4
}//loop 3
}//loop 2
}//loop 1
}//end of method
} //end of class

Java Object Based Approach (thanks Phil)

public class Counter {
private String list;
private int x;

public Counter(){
x=0;
list = "abcdefghijklmnopqrstuvwxyz";
}

public int add(){
x=x+1;

if (x ==26) {
x=0;
return 1; //signifies a reset has occurred
}
return 0;

}

public String status(){
return list.substring(x,x+1);
}
public int length(){
return list.length ();
}

}// end of class

------------------------------------------
//OBJECT:Container.Java

import java.util.*;

public class Container {
Vector v;

public Container(){
v = new Vector();
}

public void addElement(Counter c){

//copy label ref to object... not actual copy of object!!
this.v.addElement(c);
}

public String reportAll(){

String out,working;
int t;
Enumeration e;
e=this.v.elements();
Counter c;

out = "";

//run thru all points and return as a single string
while (e.hasMoreElements()){
c=(Counter) e.nextElement();
out=out+(c.status());
}

//switch order - reverse
working = out;
out="";
for (t=working.length();t>0;t--){
out = out+ working.substring(t-1,t);
}
return out;
}

public int returnLength(){
return v.size();
}

public String returnLetter(int pos){
String l;
Counter lc;

lc=(Counter) v.elementAt(pos);
l = lc.status();

return l;

}

public int addOne(int pos){
Counter t;
int temp;
t = (Counter) v.elementAt (pos);
temp = t.add();
if (temp==1){
//counter reset need to add one to element left of current
return 1;
}
return 0;
}

}//end class

------------------------------------------

//MyDriver.Java

import java.util.Date;

// Java - Object based Brute Force PassWord Cracker
// Author - Phil Bartie - 1 Jan 2006

public class MyDriver {

public static void main(String[] args) {
String secret;
Counter c;
Container ct;
int temp,t;
long loop,start,finish;
Date date;
date = new Date();
start = date.getTime();
ct = new Container();
loop=0;
secret = "daveda";

//add basic unit
ct.addElement(new Counter());

while (ct.reportAll().compareTo(secret) !=0){
loop++;
//System.out.println(ct.reportAll());

temp = ct.returnLength(); // static value of length of vector

t=0;

while (ct.addOne(t)==1){
t++;

if (temp==t){ //character reached 'z' so need new counter object
ct.addElement(new Counter());
break;
}

}
}//end for loop

//report result and number of iterations required
System.out.println("MATCH for:"+ ct.reportAll()+" @ loop " + loop);
date = new Date();
finish = date.getTime();
System.out.println ("Task completed in: " + (finish-start)+" (milliseconds)");

}//end main method
}//end class

Python (Phil)

import time

# setup string to find by brute force
loopcounter =0
secret = "daveda"
starttime = time.strftime('%X')

print starttime

for l1 in range(97,122):
for l2 in range (97,122):
for l3 in range (97,122):
for l4 in range (97,122):
for l5 in range (97,122):
for l6 in range(97,122):
loopcounter=loopcounter+1
testword=chr(l1) + chr(l2) + chr(l3) + chr(l4)+chr(l5)+chr(l6)
if testword == secret:
print time.strftime('%X')
print testword + " found after"+str(loopcounter) +" iterations"
#terminate command needed here

Python (thanks Phil) Base 26 version

import string,time
alp = 'abcdefghijklmnopqrstuvwxyz'

def ntb(num, base):
stack = []
while num:
stack.append(alp[num % base])
num = num / base
stack.reverse()
return "".join(stack)

testword=""
secretword = "daved"
counter = 1L #long
starttime = time.clock()
print "Running..."
while (testword<>secretword):
testword=ntb(counter,26)
counter = counter+1
endtime = time.clock()
print "Secret word: " + testword + " found after " + str(counter) +" attempts"
print "Search took: " + str(round(endtime-starttime,3)) + " seconds"


VB.NET

Not sure if this compiles

Dim secretString As String = "da"

Dim tryString

MessageBox.Show("Starting crypto search.")



Dim i As Integer

For i = 97 To 122



Dim j As Integer

For j = 97 To 122

tryString = Chr(i) + Chr(j)

If tryString = secretString Then

MessageBox.Show("Found secretString which is " & tryString)

End If

Next ' Next j loop

Next ' Next i loop



MessageBox.Show("End crypto and last tryString is " & tryString)

| | #