Project Euler, problem 26

Problem is stated as following:

---

A unit fraction contains 1 in the numerator. The decimal representation of the unit 
fractions with denominators 2 to 10 are given:

    1/2  =  0.5
    1/3  =  0.(3)
    1/4  =  0.25
    1/5  =  0.2
    1/6  =  0.1(6)
    1/7  =  0.(142857)
    1/8  =  0.125
    1/9  =  0.(1)
    1/10 =  0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen
that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in 
its decimal fraction part.

---

Solution is based on idea that longest recurring cycle should have 1/p form, where p - prime number. After quick look at wikipedia about repeating decimals I thought that I should just search biggest prime, but at closer examination of wiki, I understood that not necessary biggest prime would result in biggest recurring cycle of 1/prime. So for the sake of mathematical integrity, I decided to implement 'correct' search of biggest recurring cycle, which is based on calculating multiplicative order of 10 modulo prime. Solution also is pretty fast - executes in about 130 ms. Below is solution code in language F#:

---

open System.Diagnostics

// http://en.wikipedia.org/wiki/Modular_exponentiation
let modular_exponent b e m =
    let rec modular_exponent0 b e e0 m c0 = 
        match () with
        | _ when e0 >= e -> c0
        | _  -> let e1 = e0 + 1 in
                let c1 = (c0 * b) % m in
                modular_exponent0 b e e1 m c1
    modular_exponent0 b e 0 m 1

// http://en.wikipedia.org/wiki/Multiplicative_order
let multiplicative_order a n =
    let rec multiplicative_order0 a n k0 = 
        let me = modular_exponent a k0 n in
            match me with
            | 1 -> k0
            | _ -> let k1 = k0 + 1 in
                   multiplicative_order0 a n k1
    multiplicative_order0 a n 1

// http://en.wikipedia.org/wiki/Repeating_decimal#Fractions_with_prime_denominators
let period_of_1divp p = multiplicative_order 10 p

// http://en.wikipedia.org/wiki/Prime_number#Verifying_primality
let is_prime x = 
    let rec is_prime0 x d0 = 
        match () with
        | _ when d0 > int (sqrt (float x)) -> true
        | _ when x % d0 = 0 -> false
        | _ -> let d1 = d0 + 1 in
               is_prime0 x d1
    is_prime0 x 2

let main = let stopwatch = new Stopwatch()
           stopwatch.Start()
           let prime,max_period = 
               [ for x in 6..999 do if is_prime x then yield x,period_of_1divp x ] |> 
               Seq.fold (fun (a,b) (x,y) -> if y > b then (x,y) else (a,b)) (0,0)
           stopwatch.Stop()
           printfn "Fraction with greatest period of %d is 1/%d, calculated in %d ms" 
                    max_period
                    prime
                    stopwatch.ElapsedMilliseconds

---

Have fun with Project Euler and F# !

Project Euler p83 and Dijkstra's algorithm

Problem definition:
-----------------------------------------------------------
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold and is equal to 2297.

131 673 234 103 18
201 96  342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37  331

Find the minimal path sum, in matrix.txt , a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.

-----------------------------------------------------------
Problem is solved with the help of Dijkstra's algorithm
Answer is calculated in a 2.5 seconds. Also it is not optimized,- computes distances to all nodes in network. To speed up - when we find target node - we can only check these nodes which distance is less than target node distance. Also this code suits equally well for solving project euler problem no 81 - only change shortestpath() function parameter "directions". And finally - this solution shows shortest path visually,- prints it to screen. Program code:

---

import time as t

def readmatrix(filename):
    f=open(filename, 'r')
    m=[map(lambda x: int(x),r.strip().split(",")) for r in f.readlines()]
    return m

def nextcell(dctresults):
    minw = 10000000
    mink = None
    for k in dctresults:
        if not dctresults[k][2]:
            if dctresults[k][1] < minw:
                minw = dctresults[k][1]
                mink = k
    return mink

def analyzecell(lstmat, tupcell, lstdirec, dctresults):
    i,j = tupcell
    for dr in lstdirec:
        di,dj = dr
        if (i+di) in range(len(lstmat)) and (j+dj) in range(len(lstmat)):
            if not dctresults.has_key((i+di,j+dj)):
                dctresults[(i+di,j+dj)] = [(i,j),dctresults[(i,j)][1]+lstmat[i+di][j+dj],False]
            else:
                oldw = dctresults[(i+di,j+dj)][1]
                neww = dctresults[(i,j)][1]+lstmat[i+di][j+dj]
                if neww < oldw:
                    dctresults[(i+di,j+dj)][0] = (i,j)
                    dctresults[(i+di,j+dj)][1] = neww
    dctresults[(i,j)][2] = True

def shortestpath(filename, directions):
    mat = readmatrix(filename)
    results = {}
    results[(0,0)] = [None,mat[0][0],False]
    cell = nextcell(results)
    while cell:
        analyzecell(mat,cell,directions,results)
        cell = nextcell(results)
    return results, results[(len(mat)-1,len(mat)-1)][1], mat

def showpath(res, inpmat):
    print ' '+'-'*len(inpmat)+' '
    pathcells = []
    curc = (len(inpmat)-1,len(inpmat)-1)
    while curc:
        pathcells += [curc]
        curc = res[curc][0]
    for i in range(len(inpmat)):
        s='|'
        for j in range(len(inpmat)):
            s+= '#' if (i,j) in pathcells else '.'
        print s+'|'
    print ' '+'-'*len(inpmat)+' '

t1 = t.time()*1000
resd, pathsum, mat = shortestpath('matrix.txt',[(-1,0),(+1,0),(0,-1),(0,+1)])
t2 = t.time()*1000
print 'Shortest path sum', pathsum, '; Calculation time is ', int(t2-t1), 'ms'
showpath(resd, mat)

---

Have fun with shortest path algorithms !!!

Project Euler p92

Problem description:
-------------------------------------------------------------------
A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 -> 32 -> 13 -> 10 -> 1 -> 1
85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?
-------------------------------------------------------------------
Semi-bruteforce algorithm based on idea that we don`t need to construct full number chains from starting number until 1 or 89. Instead we will save in memory each starting number final result (1 or 89). And at the next starting number we will construct number chain only until previous calculated number.
Well solution is slow, but fits in "one minute rule" :-). Here it is-

---

import time as t

def nextnum(number):
 n = number
 s = 0
 while n!=0:
  m = n%10
  n = n/10
  s += m*m
 return s

def untilknown(number):
    start = number
    res = []
    while start >= number and start not in (1,89):
        start = nextnum(start)
        res += [start]
    return res

def endswith89(limit):
    seq = {1:1,89:89}
    ret = 0
    for x in range(1,limit):
        if not seq.has_key(x):
            k = untilknown(x)
            if k:
                kk = k[-1]
            else:
                kk = x
            seq[x] = seq[kk]
            if len(k) > 1:
                for i in range(len(k)-1):
                    seq[k[i]] = seq[kk]
        if seq[x] == 89:
            ret += 1
    return ret

t1 = t.time()
ans = endswith89(10000000)
t2 = t.time()

print ans, int(t2-t1),'s'

---

Have fun !!

Project Euler p99

Project Euler problem 99 description:
------------------------------------------------------------------------
Comparing two numbers written in index form like 2^11 and 3^7 is not difficult, as any calculator would confirm that 2^11 = 2048 < 3^7 = 2187.

However, confirming that 632382^518061 > 519432^525806 would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.
------------------------------------------------------------------------
The trick of solution is not to compare whole numbers (because raising to power will be too much CPU time and memory consuming operation), instead we can compare logarithms of numbers. So actually we will compare LOG(number^power). Ok, but we still have to do power operation ? Well, no more ! By applying known logarithm formula: LOG(number^power) = power*LOG(number). So we are comparing power*LOG(number). This is very fast operation.
Problem solution is found in a 3.7 ms. Solution Python code:

---

import time as tm
import math as m

t1 = tm.time()*1000
f=open('base_exp.txt', 'r')
l=[i.strip().split(",")+[n+1] for (n,i) in enumerate(f.readlines())]
l = map(lambda i: (int(i[0]),int(i[1]), i[2]), l)
l = map(lambda (x,a,n): (a*m.log(x), n), l)
max = max(l)
t2 = tm.time()*1000

print max,t2-t1,'ms'

---

Have fun!

Project Euler p22

Problem description:
-----------------------------------------------------------
Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 * 53 = 49714.

What is the total of all the name scores in the file?
-----------------------------------------------------------
Solution in Python:

---

def ReadFile():
    """ Read data input file"""
    f = open('C:/ProjectEuler/names.txt','r')
    str = f.readlines()
    f.close()
    str[0] = str[0].replace('"','')
    ret = str[0].split(',')
    ret.sort()
    return ret

def AlphabeticalValue(string):
    alph = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
    values = map(lambda x: alph.index(x)+1, list(string))
    return sum(values)

def TotalScore():
    names = ReadFile()
    namsc = map(lambda (x,y): AlphabeticalValue(y)*(x+1), list(enumerate(names)))
    return sum(namsc)

if __name__ == '__main__':
    print TotalScore()

---

What is missing ? Of course - Have fun :-)

Project Euler p96 - solving sudoku

This is interesting one. Problem description:
-----------------------------------------------
Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.

0 0 3  0 2 0  6 0 0
9 0 0  3 0 5  0 0 1
0 0 1  8 0 6  4 0 0

0 0 8  1 0 2  9 0 0
7 0 0  0 0 0  0 0 8
0 0 6  7 0 8  2 0 0

0 0 2  6 0 9  5 0 0
8 0 0  2 0 3  0 0 9
0 0 5  0 1 0  3 0 0
===================
4 8 3  9 2 1  6 5 7
9 6 7  3 4 5  8 2 1
2 5 1  8 7 6  4 9 3

5 4 8  1 3 2  9 7 6
7 2 9  5 6 4  1 3 8
1 3 6  7 9 8  2 4 5

3 7 2  6 8 9  5 1 4
8 1 4  2 5 3  7 6 9
6 9 5  4 1 7  3 8 2

A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction.

The 6K text file, sudoku.txt (right click and 'Save Link/Target As...'), contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above).

By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.
-----------------------------------------------

Well, back to more understandable language like C# :-). Solution is done as semi brute-force, iterative method. Solution is quick enough - fifty puzzles are solved in just 122 ms. So this is it:

---

class Program
    {

        static int[][][] ReadSudoku(string file)
        {
            StreamReader sr = new StreamReader(file);
            int[][][] res = new int[50][][];
            int row = 0;
            int sud = -1;
            string line;

            while (!sr.EndOfStream)
            {
                line = sr.ReadLine();
                if (line.ToLower().IndexOf("grid") > -1)
                {
                    row = 0;
                    sud++;
                    res[sud] = new int[9][];
                }
                else
                {
                    res[sud][row] = Array.ConvertAll(line.ToCharArray(), c => 
                                    { return int.Parse(c.ToString()); });
                    row++;
                }
            }
            sr.Close();

            return res;
        }

        static void ShowSudoku(int[][] sud)
        {
            string o;
            o = sud.Aggregate("", (agg, next) =>
            {
                return agg +
                    ((agg == "") ? "":"\n") +
                    next.Aggregate("|", (agg2, next2) => { 
                        return agg2 + next2.ToString(); }) + "|";
            });
            o = "-----------\n" + o + "\n-----------";
            o = o.Replace("0", ".");
            Console.Write(o);
        }

        static bool ValueIsValid(int[][] grid, int val, int row, int col)
        {
            int regc, regr;
            int lc, lr;

            if (val == 0)
                return false;

            // checking row and column
            for (int i = 0; i < 9; i++)
                if ((grid[row][i] == val && i != col) || 
                    (grid[i][col] == val && i != row))
                    return false;
            
            // checking 3x3 region
            regr = 3*(row / 3);
            regc = 3*(col / 3);
            for (int i = 0; i < 3; i++)
            {
                lc = regc + i;
                for (int j = 0; j < 3; j++)
                {
                    lr = regr + j;
                    if (lc != col || lr != row)
                        if (grid[lr][lc] == val)
                            return false;
                }
            }

            return true;
        }

        static void CellWithMinValid(int[][] grid, 
                                    out int rowo, 
                                    out int colo)
        {
            int row = -1, col = -1;
            int minvalid = 9;
            int valcount;

            for (int i = 0; i < grid.Length; i++)
            {
                for (int j = 0; j < grid[i].Length; j++)
                {
                    if (grid[i][j] == 0)
                    {
                        valcount = 0;
                        for (int k = 1; k < 10; k++)
                            if (ValueIsValid(grid, k, i, j))
                                valcount++;
                        if (valcount < minvalid)
                        {
                            minvalid = valcount;
                            row = i;
                            col = j;
                        }
                    }
                    if (minvalid == 1) break;
                }
                if (minvalid == 1) break;
            }

            rowo = row;
            colo = col;
        }

        static void SolveSudoku(int[][] grid)
        {
            int row, col;
            int curval;
            int iter;
            bool force;
            int[,] steps = new int[81, 2];

            CellWithMinValid(grid, out row, out col);
            grid[row][col] = 1;
            steps[0, 0] = row;
            steps[0, 1] = col;
            force = false;
            iter = 0;

            while (row > -1)
            {
                curval = grid[steps[iter, 0]]
                             [steps[iter, 1]];
                if (ValueIsValid(grid, curval, 
                                steps[iter, 0], 
                                steps[iter, 1]) && !force)
                {
                    CellWithMinValid(grid, out row, out col);
                    if (row != -1)
                    {
                        force = false;
                        iter++;
                        grid[row][col] = 1;
                        steps[iter, 0] = row;
                        steps[iter, 1] = col;
                    }
                }
                else
                {
                    curval++;
                    if (curval < 10)
                    {
                        grid[steps[iter, 0]]
                            [steps[iter, 1]] = curval;
                        force = false;
                    }
                    else
                    {
                        grid[steps[iter, 0]]
                            [steps[iter, 1]] = 0;
                        force = true;
                        iter--;
                    }
                }
            }
        }

        static void SolveAll(string file)
        {
            int[][][] sud = ReadSudoku(file);
            int tot = 0;

            for (int i = 0; i < sud.Length; i++)
            {
                SolveSudoku(sud[i]);
                tot += (sud[i][0][0] * 100) + 
                    (sud[i][0][1] * 10) + 
                    (sud[i][0][2]);
            }

            Console.WriteLine("Answer to projectEuler {0}\nLast sudoku solution:\n",tot);
            ShowSudoku(sud[49]);
        }

        static void Main(string[] args)
        {
            System.Diagnostics.Stopwatch sw = 
                new System.Diagnostics.Stopwatch();
            sw.Start();
            SolveAll("C:\\ProjectEuler\\sudoku.txt");
            sw.Stop();
            Console.WriteLine("\n50-ty sudoku`s solved in {0} ms", 
                            sw.ElapsedMilliseconds);
            Console.ReadLine();
        }
    }

---

As always - have fun!.

J and Project Euler p35

Problem definition:
------------------------------------------
The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?
------------------------------------------

This time again solution in J language:

---

   rot =: |: ". (i.@:#) ((({:,}:) ^: )) (@: ":)
   ffac =: 0{|: @: q: @: rot
   circ =: ((+/@: (ffac = rot)) = (#@:":))
   tot =: +/ @: (circ"0) @: (2&+)
   tot i.999998

---

Learning J language - euler problem36

Project euler problem 36 definition:
--------------------------------------
The decimal number, 585 = 1001001001 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)
--------------------------------------

So, I has some interest in array programming language J. I try to learn it a bit. And as such, I tried to solve this euler problem with the help of J language. What I learned is that this J language is VERY powerful and also it`s programs is very short, but also it is very hard to learn this language and of course - hard to understand the code (if you don`t know the language). But as soon as you proceed - more things are showing up from the fog :-).

So this is the solution:

---

+/@:((0:`(0&+))@.((+/@:(=|.)=#)@:":*.(+/@:(=|.)=#)@:#:)"0)i.1000000

---

One shot - One Kill, oh sorry, I mean: One line - One Goal :-)

As you see this code is not much understandable, but I have a little bit more readable code, acctually code is the same- just with defined function names.
This is it:

---

equalbits=: +/@:(=|.)
decpalind =: (equalbits=#)@:":
binpalind =: (equalbits=#)@:#:
bothpalind =: (decpalind*.binpalind)"0
palindsum =: +/@:((0:`(0&+))@.bothpalind)
palindsum i.1000000

---

Also just 6 lines of code. And a bit more readable, but not more if you don`t know some J basics. This language is very powerfull - especially at data processing.
If you want to learn J some basics, I would recommend this online book (also comes for free as documentation in J installation pack). Note - J interpreter is also free. This book is very good introduction, without it I would not take a look at J.
So all in all J - powerfull,interesting,strange,hard language in the same time, IMHO.
Have fun !!

Project Euler p102 - finding origin

Problem description:
-----------------------------------------------------
Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.

Consider the following two triangles:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.

Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text file containing the co-ordinates of one thousand "random" triangles, find the number of triangles for which the interior contains the origin.

NOTE: The first two examples in the file represent the triangles in the example given above.
-----------------------------------------------------

I`ve exploited the idea that for origin to be in the triangle interior, triangle lines segments should cross x and y axis 2 times: x+ / x- and y+ / y-.
Basically it is enough to check does triangle cross y+ and y- axis parts, but I didn`t know that and checked both axis. This worked too :-)

Solution ( C# as always):

---

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace ConsoleApplication1
{
    class Program
    {
        static int[][] ReadTriangleCoordinates(string file)
        {
            int[][] res;
            StreamReader sr = new StreamReader(file);
            res = Array.ConvertAll(sr.ReadToEnd().TrimEnd().Split("\n".ToCharArray()), 
                  s => {return Array.ConvertAll(s.Split(",".ToCharArray()),
                                         n => { return int.Parse(n); }) ;});
            sr.Close();
            return res;
        }

        static void CrossesAxisAt(int x1, 
                                  int y1, 
                                  int x2, 
                                  int y2, 
                                  out double? xAt, 
                                  out double? yAt)
        {
            int dx = x2 - x1;
            int dy = y2 - y1;
            int xmin = Math.Min(x1, x2);
            int ymin = Math.Min(y1, y2);
            int xmax = Math.Max(x1, x2);
            int ymax = Math.Max(y1, y2);
            double? xcross;
            double? ycross;
            double a;
            double b;

            if (dx == 0)
            {
                xcross = x1;
                ycross = null;
            }
            else if (dy == 0)
            {
                xcross = null;
                ycross = y1;
            }
            else
            {
                a = (double)dy / (double)dx;
                b = y1 - (a * x1);
                xcross = -(b / a);
                ycross = b;
            }

            if (xcross != null)
            {
                if (xcross < xmin || xcross > xmax 
                                  || ymin > 0 || ymax < 0)
                    xcross = null;
            }

            if (ycross != null)
            {
                if (ycross < ymin || ycross > ymax 
                                  || xmin > 0 || xmax < 0)
                    ycross = null;
            }

            xAt = xcross;
            yAt = ycross;
        }

        static bool ContainsOrigin(int[] abc)
        {
            double? xc1, xc2, xc3;
            double? yc1, yc2, yc3;
            int xposc = 0, xnegc = 0, yposc = 0, ynegc = 0;
            bool res;

            CrossesAxisAt(abc[0], abc[1], abc[4], abc[5], out xc1, out yc1);
            CrossesAxisAt(abc[0], abc[1], abc[2], abc[3], out xc2, out yc2);
            CrossesAxisAt(abc[2], abc[3], abc[4], abc[5], out xc3, out yc3);

            xposc = ((xc1 > 0) ? 1 : 0) + ((xc2 > 0) ? 1 : 0) + ((xc3 > 0) ? 1 : 0);
            xnegc = ((xc1 < 0) ? 1 : 0) + ((xc2 < 0) ? 1 : 0) + ((xc3 < 0) ? 1 : 0);
            yposc = ((yc1 > 0) ? 1 : 0) + ((yc2 > 0) ? 1 : 0) + ((yc3 > 0) ? 1 : 0);
            ynegc = ((yc1 < 0) ? 1 : 0) + ((yc2 < 0) ? 1 : 0) + ((yc3 < 0) ? 1 : 0);

            if (xposc > 0 && xnegc > 0 && yposc > 0 && ynegc > 0)
                res = true;
            else
                res = false;

            return res;
        }

        static int TrianglesWithOrigin(string file)
        {
            int[][] tr = ReadTriangleCoordinates(file);
            int trcount = 0;

            for (int i = 0; i < tr.Length; i++)
            {
                if (ContainsOrigin(tr[i]))
                    trcount++;
            }

            return trcount;
        }

        static void Main(string[] args)
        {
            Console.WriteLine(TrianglesWithOrigin("C:\\ProjectEuler\\triangles.txt"));
            Console.ReadLine();
        }
    }
}

---

Project Euler p59 - breaking encryption

Problem definition:
------------------------------------------------
Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

Your task has been made easy, as the encryption key consists of three lower case characters. Using cipher1.txt (right click and 'Save Link/Target As...'), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.
------------------------------------------------

C# brute-force solution, running in 42 seconds:

---

        static byte[] ReadCipher(string file)
        {
            StreamReader sr = new StreamReader(file);
            string[] buf = sr.ReadToEnd().Trim().Split(",".ToCharArray());
            byte[] res = Array.ConvertAll(buf, s => { return byte.Parse(s); });
            sr.Close();

            return res;
        }

        static byte[] TryDecipher(byte[] cip, string key)
        {
            int ind = 0;
            byte[] dec = new byte[cip.Length];

            for (int i = 0; i < cip.Length; i++)
            {
                dec[i] = (byte)((int)cip[i] ^ (int)key[ind]);
                ind = (ind >= 2) ? 0 : ind + 1;
            }

            return dec;
        }

        static int KeywordsInText(string text, string[] keywords)
        {
            int kc = 0;

            for (int i = 0; i < keywords.Length; i++)
            {
                if (text.ToLower().IndexOf(" " + keywords[i] + " ") > -1) kc++;
            }

            return (kc*100) / keywords.Length;
        }

        static void Decipher(string file)
        {
            string[] keywords = new string[] {"the","be","is","are","was","to","of","and","a","in","into","that","have","has","had","I","it","for","not","on","with","he","as","you","do","did","done","at","this","but","his","by","from","they","we","say","her","she","or","an","will","shall","my","one","all","would","should","there","here","their","what","so","up","out","if","about","who","get","got","which","go","went","gone","me"};
            string passchars = "qwertyuioplkjhgfdsazxcvbnm";
            string curkey = "";
            byte[] cipher = ReadCipher(file);
            byte[] decoded = new byte[cipher.Length];
            string dectext;
            int keywordcount = 0;
            int maxkeywords = 0;
            string bestkey = "";
            byte[] bestbytes = new byte[cipher.Length];
            string besttext = "";
            long bytesum = 0;

            for (int i1 = 0; i1 < passchars.Length; i1++)
            {
                for (int i2 = 0; i2 < passchars.Length; i2++)
                {
                    for (int i3 = 0; i3 < passchars.Length; i3++)
                    {
                        curkey = passchars[i1].ToString() + passchars[i2].ToString() + passchars[i3].ToString();
                        decoded = TryDecipher(cipher, curkey);
                        dectext = ASCIIEncoding.ASCII.GetString(decoded);
                        keywordcount = KeywordsInText(dectext, keywords);
                        
                        if (keywordcount > maxkeywords)
                        {
                            maxkeywords = keywordcount;
                            bestkey = curkey;
                            bestbytes = decoded;
                            besttext = dectext;
                        }
                    }
                }
            }

            for (int i = 0; i < bestbytes.Length; i++)
            {
                bytesum += (long)bestbytes[i];
            }

            Console.WriteLine("Byte sum: {0}\nPassword: {1}\nDecoded message 50 chars: {2}\nMessage has {3}% common words",
                                      bytesum,bestkey,besttext.Substring(0,50),maxkeywords);
        }

        static void Main(string[] args)
        {
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            Decipher("C:\\ProjectEuler\\cipher1.txt");
            sw.Stop();
            Console.WriteLine("Decryption time: {0} seconds",sw.Elapsed.Seconds);
            Console.ReadLine();
        }

---

Project Euler p79 - cracking passcode

This one is very interesting. Problem description:
-------------------------------------------
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may asked for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.
-------------------------------------------

So solution in C# is this, not optimized, but works (in a 16 seconds):

---

        static int[] ReadKeyLog(string file)
        {
            int[] dig;
            string buf;
            string[] barr;
            StreamReader sr = new StreamReader(file);
            buf = sr.ReadToEnd().TrimEnd("\n".ToCharArray());
            barr = buf.Split("\n".ToCharArray());
            dig = Array.ConvertAll(barr, s => { return Int32.Parse(s); });
            sr.Close();
            return dig;
        }

        static bool KeyPartExists(long testnumber, int keypart)
        {
            int n1 = keypart / 100;
            int n2 = (keypart / 10) % 10;
            int n3 = keypart % 10;
            bool n1e = false;
            bool n2e = false;
            bool n3e = false;

            for (long i = testnumber; i > 0; i /= 10)
            {
                if (!n3e)
                    n3e = (i % 10) == n3;
                else
                    if (!n2e)
                        n2e = (i % 10) == n2;
                    else
                        if (!n1e)
                            n1e = (i % 10) == n1;
                        else
                            break;
            }
            if (n1e && n2e && n3e)
                return true;
            else
                return false;
        }

        static bool HasAllKeyParts(long testnum, int[] keylog)
        {
            bool res = true;

            for (int i = 0; i < keylog.Length; i++)
            {
                if (!KeyPartExists(testnum, keylog[i]))
                {
                    res = false;
                    break;
                }
            }
            return res;
        }

        static long FindPassCode(string file)
        {
            int[] keylog = ReadKeyLog(file);
            long num = 10000;
            
            while (true)
            {
                if (HasAllKeyParts(num, keylog))
                    return num;
                num++;
            }
        }

        static void Main(string[] args)
        {
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            Console.WriteLine("Bruteforced passcode is {0}",
                                FindPassCode("C:\\ProjectEuler\\keylog.txt")
            );
            sw.Stop();
            Console.WriteLine("Cracking time {0} seconds", sw.Elapsed.Seconds);
            Console.ReadLine();
        }

---

Project Euler Problem 17

Definition:
---------------------------------------------
If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

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

C# code solution:

---

static long LettersOfNumber(long num, long[,]bases)
{
  long count = 0;
  long tempnum;
  if (num > 1000 num < 1)
    count = -1;
  else if (num == 1000)
    count = 11;
  else
  {
    tempnum = num % 100;
    if (tempnum < 20)
      count += bases[tempnum, 0];
    else
      count += bases[num % 10, 0] + bases[(num / 10) % 10, 1];
    if (num > 99)
      count += bases[(num / 100), 0] + 7 + ((tempnum == 0) ? 0 : 3);
  }
  return count;
}
static long LettersUntilNumber(int num)
{
  long letcount = 0;
  long[,] bas = new long[20, 2] { {0, 0}, {3, 0}, {3, 6}, {5, 6}, {4, 5}, {4, 5}, {3, 5}, {5, 7}, 
                  {5, 6}, {4, 6}, {3, 0}, {6, 0}, {6, 0}, {8, 0}, {8, 0}, {7, 0},
                  {7, 0}, {9, 0}, {8, 0}, {8, 0} };
  for (int i = 1; i <= num; i++)
    letcount += LettersOfNumber(i, bas);
  return letcount;
}
static void Main(string[]args)
{
  Console.WriteLine(LettersUntilNumber(1000));
  Console.ReadLine();
}

---

Project Euler Problem 28

Problem definition-
--------------------------------------------------
Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
It can be verified that the sum of both diagonals is 101.
What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?
--------------------------------------------------
C# brute-force solution:

---

static long SpiralDiagonalsSum(long spiralsize)
{
  long sum = 1;
  long cursize = 3;
  long number = 1;
  while (cursize <= spiralsize)
  {
    for (int i = 0; i < 4; i++)
    {
      number += cursize - 1;
      sum += number;
    }
    cursize += 2;
  }
  return sum;
}
static void Main(string[]args)
{
  System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
  sw.Start();
  long diagsum = SpiralDiagonalsSum(1001);
  sw.Stop();
  Console.WriteLine("Spiral diagonals sum {0} calculated in {1} ms", diagsum, sw.Elapsed.TotalMilliseconds);
  Console.ReadLine();
}

---

Solution on core duo performs in a 0.2 ms.

Project Euler Problem 18

This time we will solve euler problem 18 by semi-bruteforce solution.
Problem description:
--------------------------------------------------------------------------------------
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3
7 5
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
----------------------------------------------------------------------------------------
Solution in C# is more or less short and fast (calculates answer in 1,1 ms):

---

using System;

class Program
{
    static long MaxTotalFromTriangle()
    {
        long[][] triangle = new long[15][];
        long max = 0;
        triangle[0] = new long[] { 75 };
        triangle[1] = new long[] { 95, 64 };
        triangle[2] = new long[] { 17, 47, 82 };
        triangle[3] = new long[] { 18, 35, 87, 10 };
        triangle[4] = new long[] { 20, 04, 82, 47, 65 };
        triangle[5] = new long[] { 19, 01, 23, 75, 03, 34 };
        triangle[6] = new long[] { 88, 02, 77, 73, 07, 63, 67 };
        triangle[7] = new long[] { 99, 65, 04, 28, 06, 16, 70, 92 };
        triangle[8] = new long[] { 41, 41, 26, 56, 83, 40, 80, 70, 33 };
        triangle[9] = new long[] { 41, 48, 72, 33, 47, 32, 37, 16, 94, 29 };
        triangle[10] = new long[] { 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14 };
        triangle[11] = new long[] { 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57 };
        triangle[12] = new long[] { 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48 };
        triangle[13] = new long[] { 63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31 };
        triangle[14] = new long[] { 04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23 };

        for (int i = 1; i < triangle.Length; i++)
        {
            for (int j = 0; j < triangle[i].Length; j++)
            {
                // Accumulating maximum total
                if (j == 0)
                {
                    triangle[i][j] += triangle[i - 1][j];
                }
                else if (j == triangle[i].Length - 1)
                {
                    triangle[i][j] += triangle[i - 1][triangle[i - 1].Length - 1];
                }
                else
                {
                    triangle[i][j] += Math.Max(triangle[i - 1][j], triangle[i - 1][j - 1]);
                }
                // Finding maximum from last row
                if (i == triangle.Length - 1)
                {
                    if (triangle[i][j] > max) max = triangle[i][j];
                }
            }
        }
        return max;
    }

    static void Main(string[] args)
    {
        System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
        sw.Start();
        long ans = MaxTotalFromTriangle();
        sw.Stop();
        Console.WriteLine("Total sum {0}; cpu time {1} ms", ans, sw.Elapsed.TotalMilliseconds);
        Console.ReadLine();
    } 
}

---

Also this solution is universal and can calculate bigger triangles (lets say 100 rows triangles and more) with a reasonable time.

Have fun!!

Project Euler Problem 21

Ok, this is it- problem description:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers. For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220. Evaluate the sum of all the amicable numbers under 10000.

Fun part,- C# solution:

---

using System;

class Program
{
    static long DivSum(long n)
    {
        long un = 1 + (long)Math.Sqrt(n);
        long sum = 1;

        for (int i = 2; i <= un; i++)
        {
            if (n % i == 0)
                sum += i + (n / i);
        } return sum;
    }

    static long AmicablePair(long n)
    {
        long ds = DivSum(n);
        long os = DivSum(ds);
        long ret;
        ret = (os == n && n != ds) ? ds : 0;
        return ret;
    }

    static long AmicableNumbersSum(long until)
    {
        bool[] amic = new bool[until];
        long nextAmic;
        long sum = 0;
        for (int i = 1; i < until; i++)
        {
            if (!amic[i])
            {
                nextAmic = AmicablePair(i);
                if (nextAmic > 0)
                {
                    if (nextAmic < until) amic[nextAmic] = true;
                    sum += i + nextAmic;
                }
            }
        }
        return sum;
    }

    static void Main(string[] args)
    {
        System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
        sw.Start();
        Console.WriteLine("Amicable numbers sum {0}", AmicableNumbersSum(10000));
        sw.Stop();
        Console.WriteLine("Calculation time {0} ms", sw.ElapsedMilliseconds);
        Console.ReadLine();
    } 
}

---

So solution is fast enough,- runs in about 20 ms. A little bit explanations of why this
solution is fast:

• We need not to search all divisors, but rather until SQRT limit of number.
  This is because if number, lets say x, have divisor d1 above SQRT(x), then,
  that number x MUST have also a divisor d2 = x/d1, below SQRT(x) limit.
• We need not to verify are all test numbers amicable, because if we find one
  amicable number, lets say x, then we know that there exists second amicable
  number y, which is sum of proper divisors of x. This rule is true, because
  we acctually searching amicable number pairs. So by applying this rule
  we can use memorization - mark second amicable number in bool array,
  and skip that number from test later.

Have fun!

Projecteuler.net problem 14 - Csharp vs Fsharp

Problem 14 stated as following:

The following iterative sequence is defined for the set of positive integers: n → n/2 (n is even) n → 3n + 1 (n is odd) Using the rule above and starting with 13, we generate the following sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain?

Ok, so here it is. Lets have fun with F#:

---

let seq_length n = n > Seq.unfold(fun x -> match x with
x when x = 0L -> None
x when x = 1L -> Some((1L,0L))
x when x%2L=0L -> Some((x,x/2L))
_ -> Some((x,3L*x + 1L))
) > Seq.length
[for i in 1L..1000000L -> (i, seq_length i)]
> List.fold1_left(fun (ai,al) (i,l) -> if l > al then (i,l) else (ai,al) )
> (fun (x,y) -> x ) > print_any

---

Elegant, slow version of solution-> ~20 lines; ~10 seconds.

Now lets try C#:

---

static long CountTerms(long x, ref long[] terms)
{
 long tc = 1;
 long k = x;

 while (k!=1)
 {
  tc++;
  k = (k % 2 == 0) ? k / 2 : 3 * k + 1;
  if (k <= x) 
  {
   if (terms[k] > 0)
   {
    terms[x] = terms[k] + tc;
    return terms[x];
   }
  }
 }
 terms[x] = tc;
 return terms[x] ;
}

static long LongestSeq()
{
 long max = 1000000;
 long[] termcount = new long[max+1];
 long tcmax = 0;
 long c = 0;
 long ix = 0;

 for (int i = 1; i <= max; i++) 
 {
  c = CountTerms(i, ref termcount);
  if ( c > tcmax)
  {
   tcmax = c;
   ix = i;
  }
 }
 return ix;
}

static void Main(string[] args)
{
 Console.WriteLine(LongestSeq());
 Console.ReadLine();
}

---

Ugly, fast version of solution -> ~0.18 second; ~60 lines.

Conclusion:

F# solutions can be done in more elegant/less code way, but in contrary it is slower that C#
counterpart. Also C# solutions can be written in fast way, but needs more code and attention.
F# solution was by factor 55 slower than C# solution, but also code was by factor of 3 shorter than C# counterpart. So if you want elegancy/generics power - take F#; and if you want only perfomance- take C#.
P.S. There is a way in F# to code (using mutable keyword) very very ugly like in C#, but i`ve not
suggest using it on F#,- why to code ugly in F# if you can grab C# instead ?? :-)