The Coding Misfit

Starting to get back into studying basic algorithms again and thought I’d start with good ol Fibonacci. Most programmers already know how to the naive approach. This got me thinking, what are some other ways to solve this.

If you’ve forgotten the Fibonacci sequence can be defined as follows:

F(n) = {
0 if n = 0
1 if n = 1
F(n-1) + F(n-2) if n >= 2
}

Below are several implementations for generating the nth Fibonacci number. I’ve also include some timing characteristics to show how efficient the algorithm(s) is.

The first version (FibNaive) is the simplistic implementation and what many would probably call the “naive” approach. This is simply coding the recurrence formula above. This implementation runs in exponential time. This version performs the same calculation numerous times and is very inefficient.

The second version (FibCache) uses a cache to fix the problems in FibNaive. This version still uses the the problem with the recurrence above to calculate the nth fibonacci number. However, once a fibonacci number has been calculated it is stored in a cache so no re-calculation is done. The version now runs in O(n).

The third version (FibBottomUp) is similar to FibCache. It calculates the sequence from 2..n instead of n..2 like the previous two version. Each fibonacci number found is stored into a lookup table for subsequent searches. It also doesn’t use recursion to solve the problem. This version runs in O(n)

The fourth version (FibMatrix) is an attempt to see if the runtime can be better than O(n). This version does have a runtime of O(lg n). This version
uses the matrix form of the fibonacci sequence and its properties to allow the runtime to be better than O(n).

Because the implementations below use longs to store Fib(n) we can only calculate a max of Fib(92) before long overflows. Here are the timings
on a 2Ghz dual core.

Timings:
FibCache(92) = 7540113804746346429 took [0.333632]ms.
FibBottomUp(92) = 7540113804746346429 took [0.006355]ms.
FibMatrix(92) = 7540113804746346429 took [0.052101]ms.
(got tired of waiting)
FibNaive(53) = 53316291173 took [805.088976739]secs.

/*
 * Fib1.java
 *
 * Copyright (c) 2009 skaoth. All rights reserved.
 *
 * This software/library is free software; you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or version 3 of the
 * License.
 *
 * This software/library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE
 *
 * See the GNU Lesser General Public License for more details.
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html
 * http://www.gnu.org/licenses/lgpl.html
 */
package fib;

public class FibNaive {
    public long calculateFib(long n) {
        StopWatch sw = new StopWatch();
        sw.start();
        long answer = fib(n);
        sw.stop();

        System.out.println("FibNaive(" + n  +") = " + answer + " took [" + sw.timeInSeconds() + "]secs.");
        return answer;
    }

    private long fib(long n) {
        if(n == 0 || n == 1) { return n; }

        return fib(n - 1) + fib(n - 2);
    }
}

/*
 * FibCache.java
 *
 * Copyright (c) 2009 skaoth. All rights reserved.
 *
 * This software/library is free software; you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or version 3 of the
 * License.
 *
 * This software/library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE
 *
 * See the GNU Lesser General Public License for more details.
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html
 * http://www.gnu.org/licenses/lgpl.html
 */
package fib;

import java.util.HashMap;
import java.util.Map;

/**
 *
 * @author skaoth
 */
public class FibCache {

    private Map cache = new HashMap();

    public long calculateFib(long n) {
        StopWatch sw = new StopWatch();
        sw.start();
        long answer = fib(n);
        sw.stop();

        System.out.println("FibCache(" + n +") = " + answer + " took [" + sw.timeInMilliseconds() + "]ms.");
        return answer;
    }

    private long fib(long n) {
        if(n == 0 || n == 1) { return n; }

        // check cache;
        if(cache.containsKey(n)) {
            return cache.get(n);
        }

        long fib = fib(n - 1) + fib(n - 2);
        cache.put(n, fib);

        return fib;
    }
}

/*
 * BottomUpFib.java
 *
 * Copyright (c) 2009 skaoth. All rights reserved.
 *
 * This software/library is free software; you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or version 3 of the
 * License.
 *
 * This software/library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE
 *
 * See the GNU Lesser General Public License for more details.
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html
 * http://www.gnu.org/licenses/lgpl.html
 */
package fib;

public class FibBottomUp {
    private long[] lookup = null;

    public long calculateFib(int n) {
        if(n > Integer.MAX_VALUE || n < 2) {
            throw new IllegalArgumentException("Invalid value of n");
        }

        lookup = new long[n + 1];
        lookup[0] = 0;
        lookup[1] = 1;

        StopWatch sw = new StopWatch();
        sw.start();
        long answer = fib(n);
        sw.stop();

        System.out.println("FibBottomUp(" + n +") = " + answer + " took [" + sw.timeInMilliseconds() + "]ms.");
        return answer;
    }

    private long fib(long n) {
        for(int i = 2; i <= n; i++) {
            lookup[i] = lookup[i-1] + lookup[i-2];
        }

        return lookup[(int)n];
    }
}

/*
 * MatrixFib.java
 *
 * Copyright (c) 2009 skaoth. All rights reserved.
 *
 * This software/library is free software; you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or version 3 of the
 * License.
 *
 * This software/library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE
 *
 * See the GNU Lesser General Public License for more details.
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html
 * http://www.gnu.org/licenses/lgpl.html
 */

package fib;

/**
 * Description: The idea behind using the matrix form of the Fibonacci sequence
 * is to see if it can help in getting better than O(n) runtime. Indeed this is
 * true. The matrix form as shown on wikipedia allows the fibonacci sequence
 * to be solved in O(lg n).
 * Let A be the the matrix [1 1] ^n
 *                         [1 0]
 * With this representation the problem can be stated as:
 * Fib(n) =
 * {
 *  A^(n/2) * A(n/2)  if n is even
 *  A^((n-1/2) * (A(n-1/2) * A if n is odd
 * }
 *
 * @link http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
 * @author skaoth
 */
public class FibMatrix {
    private static long fibMatrix[][] = {{ 1, 1}, {1, 0}};
    private boolean even = false;

    public long calculateFib(int n) {
        if(n > Integer.MAX_VALUE || n < 2) {
            throw new IllegalArgumentException("Invalid value of n");
        }

        int m = n;
        even = isEven(n);
        if(even) {
            n /= 2;
        } else {
            n = (n - 1) / 2;
        }

        StopWatch sw = new StopWatch();
        sw.start();
        long matrix[][] = fib(n);
        sw.stop();

        System.out.println("FibMatrix(" + m +") = " + matrix[0][1] + " took [" + sw.timeInMilliseconds() + "]ms.");
        return matrix[0][1];
    }

    private long[][] fib(int n) {
        long matrix[][] = {{1, 1}, {1, 0}};  // starting matrix

        for(int i = n; i > 1; i--) {
            matrix = multiply(matrix, fibMatrix);
        }

        // Square
        matrix = multiply(matrix, matrix);
        if(!even) {
            matrix = multiply(matrix, fibMatrix);
        }

        return matrix;
    }

    private boolean isEven(int n) {
        return ((n & 0x1) == 0);
    }

    private long[][] multiply(long[][] m1, long[][] m2) {
        long[][] newMatrix = new long[2][2];
        newMatrix[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
        newMatrix[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
        newMatrix[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
        newMatrix[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];

        return newMatrix;
    }
}

Java, programming

I remember reading about this a while ago. Supposedly Cambridge research says that it doesn’t matter what order the letters of a word are in. The only thing that matters is that the first and last letter of the word stay in place.

I though I’d write a small little program to do just this and see what we get. Of course smaller words are going to be easier to read than really long words.

/*
 * This library is free software; you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or version 3 of the
 * License. This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE

 * See the GNU Lesser General Public License for more details.
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html
 * http://www.gnu.org/licenses/lgpl.html
 */

import java.util.*;
import java.util.Random;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 *
 * @author skaoth
 */
public class Scrambler {

    private String original = null;
    private String words[] = null;
    private Random r = new Random();

    public Scrambler(String msg) {
        original = msg;

        // Split the original message and mix it up
        words = original.split("\\s|\\n");
    }

    public void mix() {
        String ret = "";

        for(int i = 0; i < words.length; ++i) {

            // put the sentence(s) back together
            ret += scrambleWord(words[i]) + " ";
        }

        System.out.println("original: " + original);
        System.out.println("mixed: " + ret);

    }

    public String scrambleWord(String word) {

        // Pattern for isolating the first and last character
        Pattern re = Pattern.compile("^(\\w)(\\w+)(\\w)(.*)");
        Matcher m = re.matcher(word);
        String scrambled = word;
        if(m.find()) {
            scrambled = "";
            String toScramble = m.group(2);

            List letters = new ArrayList(toScramble.length());
            for(int i = 0; i < toScramble.length(); ++i) {
                letters.add(toScramble.charAt(i));
            }
            // scramble the letters
            Collections.shuffle(letters, r);

            for(Character t : letters) {
                scrambled += t;
            }

            // Re-assemble the word with the middle all scrambled up.
            scrambled = m.group(1) + scrambled + m.group(3) + m.group(4);
        }

        return scrambled;
    }
}

Output:

original: By three methods we may learn wisdom: First, by reflection, which is noblest; Second, by imitation, which is easiest; and third by experience, which is the bitterest.

mixed: By trehe mtdheos we may lraen wdoism: First, by recelifton, wchih is nsloebt; Second, by itimaotin, wihch is eessiat; and thrid by erixeepcne, whcih is the beeritstt.

original: Knowledge comes, but wisdom lingers.

mixed: Kdoenwgle coems, but wsdiom lerigns.

original: Do not dwell in the past, do not dream of the future, concentrate the mind on the present moment.

mixed: Do not dwell in the psat, do not draem of the frtuue, ctaetcrnnoe the mnid on the pnesret moment.

Java, Uncategorized, programming

his is code for solving the NQueens problem using tail recursion. Nothing fancy was done to optimize the solution. This is pure brute force. Therefore the runtime is very slow. This version supports a threaded capability to show that solving the puzzle with multiple threads does decrease the runtime.

Here is some stats on how long it took to run.

Solving NQueens Single Threaded
===========================
Solutions found: [2] Board Size: [4] Execution length: [0ms]
Solutions found: [10] Board Size: [5] Execution length: [0ms]
Solutions found: [4] Board Size: [6] Execution length: [15ms]
Solutions found: [40] Board Size: [7] Execution length: [0ms]
Solutions found: [92] Board Size: [8] Execution length: [16ms]
Solutions found: [352] Board Size: [9] Execution length: [78ms]
Solutions found: [724] Board Size: [10] Execution length: [500ms]
Solutions found: [2680] Board Size: [11] Execution length: [2719ms]
Solutions found: [14200] Board Size: [12] Execution length: [17203ms]
Solutions found: [73712] Board Size: [13] Execution length: [112250ms]
Solutions found: [365596] Board Size: [14] Execution length: [786766ms]

Solving NQueens Multi Threaded
===========================
Solutions found: [2] Board Size: [4] Execution length: [0ms]
Solutions found: [10] Board Size: [5] Execution length: [0ms]
Solutions found: [4] Board Size: [6] Execution length: [0ms]
Solutions found: [40] Board Size: [7] Execution length: [0ms]
Solutions found: [92] Board Size: [8] Execution length: [0ms]
Solutions found: [352] Board Size: [9] Execution length: [31ms]
Solutions found: [724] Board Size: [10] Execution length: [141ms]
Solutions found: [2680] Board Size: [11] Execution length: [718ms]
Solutions found: [14200] Board Size: [12] Execution length: [4328ms]
Solutions found: [73712] Board Size: [13] Execution length: [28641ms]
Solutions found: [365596] Board Size: [14] Execution length: [194609ms]

Note: I tried to attach syntax highlighting to the code, but the plugin puked on the xml comments and when using generics

C# Code

[NQueenSolver.cs]

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
using System.Threading;

namespace nqueens
{

    ///
    /// This class is meant to work in conjunction with the
    /// Chessboard class to help determine if a solution to
    /// the nqueens problem has been found
    ///
    public class NQueensSolver
    {
        private BitArray m_bitBoard = null;
        private BitArray m_mask = null;

        private ChessBoard m_board = null;
        private Solutions m_solutions = new Solutions();
        private int m_size;     // one dimension of the board

        public NQueensSolver(int boardSize)
        {
            m_size = boardSize;

            // Bitboard representation of the current chess board
            m_bitBoard = new BitArray(boardSize * boardSize);
            m_mask = new BitArray(boardSize * boardSize);

            // Current chessboard.
            m_board = new ChessBoard(boardSize);
        }

        public void SolveNqueens(bool bThreaded)
        {
            m_solutions.Clear();

            if (bThreaded)
                SolveThreaded();
            else
                SolveSingleThread();
        }

        private void SolveSingleThread()
        {
            int start, stop;
            start = System.Environment.TickCount;

            for (int i = 0; i < m_size; i++)
            {
                // Solve the nqueens for the ith rank
                DepthFirstRecursion(i, 0);
                m_board.ClearBoard();
            }

            stop = System.Environment.TickCount;

            Console.WriteLine("Solutions found: [" + m_solutions.Count + "] Board Size: [" + m_size + "] Execution length: [" + (stop - start) + "ms]");
        }

        private void SolveThreaded()
        {
            // Events used to determine whether a thread has completed
            ManualResetEvent[] evs = new ManualResetEvent[m_size];
            LinkedList list = new LinkedList();

            int start, stop;
            start = System.Environment.TickCount;

            // Create 'board size' threads
            for (int i = 0; i < m_size; i++)
            {
                evs[i] = new ManualResetEvent(false);
                NQueensSolver solver = new NQueensSolver(m_size);

                list.AddFirst(solver);
                // Put each ith rank into it's own thread
                ThreadPool.QueueUserWorkItem(solver.SolvePuzzle, new ThreadParam(evs[i], i));

            }
            WaitHandle.WaitAll(evs);

            foreach (NQueensSolver n in list)
                m_solutions.AddSolution(n.m_solutions);

            stop = System.Environment.TickCount;

            Console.WriteLine("Solutions found: [" + m_solutions.Count + "] Board Size: [" + m_size + "] Execution length: [" + (stop - start) + "ms]");
        }

        private void SolvePuzzle(object threadParam)
        {
            ThreadParam param = (ThreadParam)threadParam;

            // Perform recursion to solve nqueens
            DepthFirstRecursion(param.Rank, 0);

            // notify caller that thread is done
            param.Event.Set();
        }

        #region [private]

        ///
        /// Example of how to use tail-recursion to solve nqueens. This
        /// solution is NOT optimized it that it blindly checks every possible
        /// solution. I'm aware that there exists optimizations to this problem
        ///
        ///

        ///

        private void DepthFirstRecursion(int rank, int file)
        {
            if (file > m_size - 1 || rank >m_size - 1) return;

            // Recursively search for solution(s) to the nqueens problem
            CreateBitBoard(m_board.CurrentBoard);

            // Create Queen attack vector(s) mask
            CreateQueenAttackMask(rank, file);

            if (IsQueenMoveValid())
            {
                // Add the queen to the board
                m_board.AddQueen(rank, file);

                // Check if Solution
                if ((file == m_size - 1) && IsSolution(m_board.CurrentBoard))
                {
                    m_solutions.AddSolution(m_board.CurrentBoard);
                    return;
                }

                file++;

                // Add the next queen on the next file
                for (int i = 0; i < m_size; i++)
                {
                    DepthFirstRecursion(i, file);
                    m_board.CurrentBoard[file] = (int)PieceType.EmptyPiece;
                }
            }
        }

        private bool IsSolution(int[] board)
        {
            // If the index values of the board are unique then
            // we have a solution
            Dictionary test = new Dictionary();

            for(int i = 0; i < m_size; i++)
            {
                if (board[i] == (int)PieceType.EmptyPiece)
                    return false;

                if (test.ContainsKey(board[i]))
                    return false;
                else
                    test.Add(board[i], i);
            }
            return true;
        }

        private void PrintBitBoard(BitArray a)
        {
            // Print Mask
            for (int i = 0; i < a.Length; ++i)
            {
                if (i % m_size == 0) Console.WriteLine();
                if (a[i] == true) Console.Write("x");
                else Console.Write("-");
            }
            Console.WriteLine();
        }

        private bool IsQueenMoveValid()
        {
            BitArray validMove = m_mask.And(m_bitBoard);

            // Check to see if there is a conflict
            for (int i = 0; i < validMove.Length; ++i)
            {
                if (validMove[i])
                {
                    return false;
                }
            }

            return true;
        }

        ///
        /// Creates a bitboard out of the current chess board
        ///
        ///

        private void CreateBitBoard(int[] curBoard)
        {
            m_bitBoard.SetAll(false);
            // i == file position
            for (int i = 0; i < curBoard.Length && curBoard[i] != (int)PieceType.EmptyPiece; ++i)
            {
                int idx = BoardIndex(curBoard[i], i);

                if(idx >= 0)
                    m_bitBoard[idx] = true;
            }
        }

        ///
        /// Create a mask thte represents the 'next' queens attack vectors
        ///
        ///

        ///

        private void CreateQueenAttackMask(int rank, int file )
        {
            int r, f;
            // list of squares that the new queen can attack
            m_mask.SetAll(false);

            // Set the first horizontal index. The rest is in the loop
            m_mask[BoardIndex(rank, 0)] = true; 

            //Set Diagonal mask(s)
            int count = 1;
            while(true)
            {
                // Horizontal
                m_mask[BoardIndex(rank, count)] = true;

                // TopLeft Diagonal
                r = rank - count; f = file - count;
                if ((r < m_size) && (r > -1) && (f < m_size) && (f > -1))
                    m_mask[BoardIndex(r, f)] = true;

                // BottomLeft Diagonal
                r = rank + count; f = file - count;
                if ((r < m_size) && (r > -1) && (f < m_size) && (f > -1))
                    m_mask[BoardIndex(r, f)] = true;

                // TopRight Diagonal
                r = rank - count; f = file + count;
                if ((r < m_size) && (r > -1) && (f < m_size) && (f > -1))
                    m_mask[BoardIndex(r, f)] = true;

                // BottomRight Diagonal
                r = rank + count; f = file + count;
                if ((r < m_size) && (r > -1) && (f < m_size) && (f > -1))
                    m_mask[BoardIndex(r, f)] = true;

                ++count;

                if(count > (m_size - 1))
                  break;
            }
        }

        ///
        /// Returns a 1-d array index of a 2-d array representation
        /// of a queen position
        ///
        ///

        ///

        ///
        private int BoardIndex(int rank, int file)
        {
            int idx = 0;

            idx = (m_size * (rank)) + file;
            return idx;
        }

        #endregion

        #region [inner class]
        ///
        /// Used as a parameter to the threadproc when solving for
        /// the threaded version of nqueens
        ///
        protected struct ThreadParam
        {
            private ManualResetEvent m_ev;
            private int m_rank;

            public ThreadParam(ManualResetEvent ev, int rank)
            {
                m_ev = ev;
                m_rank = rank;
            }

            #region [properties]
            public ManualResetEvent Event
            {
                get { return m_ev; }
            }
            public int Rank
            {
                get { return m_rank;  }
            }
            #endregion
        }
        #endregion
    };
}

[ChessBoard.cs]

using System;
using System.Collections.Generic;
using System.Text;

namespace nqueens
{
    public enum PieceType
    {
        EmptyPiece = -1     // Represents an empty square on the board
    };

    public class ChessBoard
    {
        private int m_size;
        private int[] m_board;

        public ChessBoard(int size)
        {
            // Note: Chessboard is 0 based
            if (size < 4)
                m_size = 4;
            else
                m_size = size;

            m_board = new int[m_size];
            ClearBoard();
        }

        public void ClearBoard()
        {
            for (int i = 0; i < m_size; i++)
                m_board[i] = (int)PieceType.EmptyPiece;
        }

        public void AddQueen(int rank, int file)
        {
            if(rank < 0 || rank > m_size) throw new InvalidPosition();
            if(file < 0 || file > m_size) throw new InvalidPosition();

            // Add the queen to the board
            m_board[file] = rank;
        }

        public void RemoveQUeen(int rank, int file)
        {
            AddQueen(rank, (int)PieceType.EmptyPiece);
        }

        public int[] CurrentBoard
        {
            get { return m_board; }
        }
    };

    public class InvalidPosition : ApplicationException
    {
        public InvalidPosition() : base() {}
        public InvalidPosition(string s) : base(s) {}
        public InvalidPosition(string s, Exception innerException) : base(s, innerException){}
    }
}

[Solutions.cs]

using System;
using System.Collections.Generic;
using System.Text;

namespace nqueens
{
    public class Solutions
    {
        private List m_solutions = new List();
        private object m_lock = new object();
        public void AddSolution(int[] sol)
        {
            lock (m_lock)
            {
                m_solutions.Add(sol);
            }
        }

        public void AddSolution(Solutions s)
        {
            foreach(int[] board in s.m_solutions)
            {
                AddSolution(board);
            }
        }

        public int Count
        {
            get { return m_solutions.Count;}
        }

        public void Clear()
        {
            m_solutions.Clear();
        }
        #region [console print]
        public void print(int n)  // Print 0 to n solutions
        {

            for(int i = 0; i < m_solutions.Count && i < n; i++)
            {
                Console.WriteLine("[ {0} ]", m_solutions[i].ToString());
            }
        }
        #endregion
    }
}

[Program.cs]

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace nqueens
{
    class Program
    {
        static void Main(string[] args)
        {
            NQueensSolver ns = new NQueensSolver(boardSize);

            Console.WriteLine("Single Threaded: ");
            ns.SolveNqueens(true);

            Console.ReadLine();
        }
    }
}

Uncategorized programming

using System;
using System.Runtime.InteropServices;
using System.ComponentModel;
using System.Collections.Generic;
using System.Text;
namespace csharp.activex.sample
{
/// <summary>
/// A very simple interface to test ActiveX with.
/// </summary>
[
Guid( "E86A9038-368D-4e8f-B389-FDEF38935B2F"),
InterfaceType( ComInterfaceType.InterfaceIsDual),
ComVisible( true)
]
public interface IHello
{
    [DispId(1)]
    string Hello();
    [DispId(2)]
    int ShowDialog(string msg);
};

[
Guid("873355E1-2D0D-476f-9BEF-C7E645024C32"),
// This is basically the programmer friendly name
// for the guid above. We define this because it will
// be used to instantiate this class. I think this can be
// whatever you want. Generally it is
// [assemblyname].[classname]
ProgId("csharpAx.CHello"),
// No class interface is generated for this class and
// no interface is marked as the default.
// Users are expected to expose functionality through
// interfaces that will be explicitly exposed by the object
// This means the object can only expose interfaces we define
ClassInterface(ClassInterfaceType.None),
// Set the default COM interface that will be used for
// Automation. Languages like: C#, C++ and VB
// allow to query for interface's we're interested in
// but Automation only aware languages like javascript do
// not allow to query interface(s) and create only the
// default one
ComDefaultInterface(typeof(IHello)),
ComVisible(true)
]
public class CHello : IObjectSafetyImpl, IHello
{
    #region [IHello implementation]
    public string Hello()
    {
        return "Hello from CHello object";
    }

    public int ShowDialog(string msg)
    {
        System.Windows.Forms.MessageBox.Show(msg, "");
        return 0;
    }
    #endregion
};
}

public enum ComInterfaceType ()
{
InterfaceIsDual = 0,
InterfaceIsIUnknown = 1,
InterfaceIsIDispatch = 2,
}

<html xmlns="http://www.w3.org/1999/xhtml">
<head> <title>C# ActiveX Test</title> </head>
<h1>This is Our ActiveX Test Page h1>

The message from the ActiveX Control is [
<div id="axmsg"></div>
]
<script type="text/javascript">
function myload()
{

    var myAx = new ActiveXObject("csharpAx.CHello");
    if(myAx != null)
    {
        myAx.ShowDialog("hello from asp.net"); var d = document.getElementById("axmsg");
        var s = myAx.Hello();
        d.outerText = s;
    }
    else
        alert("NOOOO... we failed");
}

</script>
</body></html>

using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;
using System.ComponentModel;
using System.Text;
namespace csharp.activex.sample
{

    [
        Serializable,
        ComVisible(true)
    ]
    public enum ObjectSafetyOptions
    {
        INTERFACESAFE_FOR_UNTRUSTED_CALLER = 0x00000001,
        INTERFACESAFE_FOR_UNTRUSTED_DATA = 0x00000002,
        INTERFACE_USES_DISPEX = 0x00000004,
        INTERFACE_USES_SECURITY_MANAGER = 0x00000008
    };

    //
    // MS IObjectSafety Interface definition
    //
    [
    ComImport(),
    Guid("CB5BDC81-93C1-11CF-8F20-00805F2CD064"),
    InterfaceType(ComInterfaceType.InterfaceIsIUnknown)
    ]
    public interface IObjectSafety
    {
        [PreserveSig]
        long GetInterfaceSafetyOptions( ref Guid iid, out int pdwSupportedOptions, out int
pdwEnabledOptions);
        [PreserveSig]
        long SetInterfaceSafetyOptions( ref Guid iid, int dwOptionSetMask, int dwEnabledOptions);
    };

    //
    // Provides a default Implementation for
    // safe scripting.
    // This basically means IE won't complain about the
    // ActiveX object not being safe
    //
    public class IObjectSafetyImpl : IObjectSafety
    {
        private ObjectSafetyOptions m_options =
        ObjectSafetyOptions.INTERFACESAFE_FOR_UNTRUSTED_CALLER | OjectSafetyOptions.INTERFACESAFE_FOR_UNTRUSTED_DATA;

        #region [IObjectSafety implementation]
        public long GetInterfaceSafetyOptions( ref Guid iid, out int pdwSupportedOptions,
out int dwEnabledOptions)
        {
            pdwSupportedOptions = (int)m_options;
            pdwEnabledOptions = (int)m_options;
            return 0;
        }
        public long SetInterfaceSafetyOptions(ref Guid iid, int dwOptionSetMask, int dwEnabledOptions)
        {
            return 0;
        }
        #endregion
    };
}

public class CHello : IObjectSafetyImpl, IHello
{
…
};

interface IUnknown
{
    virtual HRESULT QueryInterface(REFIID riid, void **ppvObject) = 0;
    virtual ULONG AddRef(void) = 0;
    virtual ULONG Release(void) = 0;
};

interface IDispatch : public IUnknown
{
virtual ULONG GetTypeInfoCount(unsigned int FAR* pctinfo) = 0;
virtual HRESULT GetTypeInfo(unsigned int iTInfo, LCID lcid,   ITypeInfo FAR* FAR* ppTInfo ) = 0;
virtual ULONG GetIDsOfNames( REFIID riid,
OLECHAR FAR* FAR* rgszNames,
unsigned int cNames,
LCID lcid,
DISPID FAR* rgDispId) = 0;
};
virtual ULONG Invoke( DISPID dispIdMember,
REFIID riid,
LCID lcid,
WORD wFlags,
DISPPARAMS FAR* pDispParams,
VARIANT FAR* pVarResult,
EXCEPINFO FAR* pExcepInfo,
unsigned int FAR* puArgErr) = 0;
};

Uncategorized programming

I ran across a small programming puzzle which I thought was pretty neat.

The puzzle is fairly simple it is: Find the max integer of an array.
If this was all to it it wouldn’t be very good puzzle would it? So here are the modifications/requirements.
1) Find the max integer of an arbitrary sized array. The values of the array are in random order
2) Write the solution to this without using any “if” statements.
3) If your solution in (2) uses any looping constructs. Refactor your solution so that these other conditions are met

• No looping constructs (while, for)
• No use of the ternary operator
• No use of 3rd party functions (STL, etc) as those functions may use “if” or “looping” constructs

What seemed like a very easy find max puzzle got a little more interesting. This shouldn’t be a difficult problem. The heart of the problem is how can we mimic an “if” statement. This one keyword is used very heavily in all of programming. Anyways here is what I came up with. The thread that started this question and where I first answered can be found
at D.I.C.

int GetMax(int a, int b)
{
    int v[] = {a, b};

    // return the greater value
    return v[!(a > b)];
}

//
// Note: return value is a dummy field
//
bool CheckNext(int ary[], int size, int &curmax)
{
    curmax = GetMax(curmax, ary[size - 1]);

    // the condition is used to break out of the recursion
    return  (size > 1) && CheckNext(ary, size - 1, curmax);
}

int FindMax(int ary[], int size)
{
    int curmax = ary[size - 1];

    // Recursively check for the next max number and
    // assign it to curmax
    CheckNext(ary, size - 1, curmax);

    return curmax;
}

int main(int argc, char* argv[])
{
    int num[] = {100, 6, 9, 401, 121, 2, -23, 95, 344 };

    int size = sizeof(num) / sizeof(int);
    int val = FindMax(num, size);

    std::cout << "And the winner is: " << val << std::endl;
    int z;
    std::cin >> z;
}

programming puzzle

The problem can be stated as follows:

Your invited to a party. There are N people at the party.
In the party people may or may not know each other.
One celebrity was invited to the party. Everyone at
this party knows the celebrity. However, the celebrity
knows no one at the party!

You are allowed to ask one question to as many people
as you want. The question is:

“Person A do you know Person B?”

The answer can be “Yes” or “No”.

Using what you know about the party, write
an algorithm to find the celebrity. Most efficient
is best of course

programming puzzle

This one is thee must know link list question, and it goes a little something like this

Given a prototype: node* Reverse(node* head);

How would you reverse a link list?

Ans:

node* Reverse(node *head)
{
    node *pNext = NULL, *pPrev = NULL;
    while(head)
    {
        pNext = head->next;
        head->next = pPrev;
        pPrev = head;
        head = pNext;
    }
}

The way I remember this problem is to think of the problem as creating a new list.

programming programming