Tom Moertel's Blog

ABC
FED
GAI

Way  --Move---
     1   2   3

1:  *BC ABC *BC
    FED F*D FED
    GAI GAI GAI

2:  *BC ABC ABC
    FED F*D FED
    GAI GAI G*I

3:  ABC ABC *BC
    FED F*D FED
    G*I GAI GAI

4:  ABC ABC ABC
    FED F*D FED
    G*I GAI G*I

Way  --Move-------- 
     1   2   3   4 

1:  *BC A*C AB* ABC
    FED FED FED FE*
    GAI GAI GAI GAI

{-

Tom Moertel <tom@moertel.com>
2006-08-15

Haskell-based solution to the Google Code Jam problem "countPaths";
see http://www.cs.uic.edu/~hnagaraj/articles/code-jam/ for more.

-}

module Main (main) where

import Control.Monad
import Data.Array
import qualified Data.Map as M

main = do
    word:gridspec <- liftM words getContents
    print $ (countPaths word (toGridArray gridspec) :: Integer)

countPaths word@(p:_) gridArray =
    sum . M.elems $ foldl step state0 (zip word (tail word))
  where
    state0 = M.fromList [(cell, 1) | (cell, q) <- assocs gridArray, p == q]
    neighbors = toNeighborMap gridArray
    step state fromto = M.fromListWith (+) $ do
        steps <- M.lookup fromto neighbors
        (start, count) <- M.assocs state
        cells <- M.lookup start steps
        cell <- cells
        return (cell, count)

toGridArray gridspec@(l1:_) =
    listArray ((1,1), (length gridspec, length l1)) (concat gridspec)

toNeighborMap gridArray =
    M.fromListWith (M.unionWith (flip (++))) $ do
        (cell, p) <- assocs gridArray
        cell' <- neighbors8 cell
        guard $ inRange (bounds gridArray) cell'
        return ((p, gridArray!cell'), M.singleton cell [cell'])

neighbors8 (r,c) =
    [(r+h, c+v) | h <- [-1..1], v <- [-1..1], h /= 0 || v /= 0]

-- Local Variables:  ***
-- compile-command: "ghc -O2 -o wordpath --make WordPath.hs" ***
-- End: ***

$ ./wordpath
AAAAAAAAAAA

AAAAA
AAAAA
AAAAA
AAAAA
AAAAA
^D

2745564336

countPaths word gridArray =
    sum [counts ! (length word, cell) | cell <- cells]
  where
    counts = listArray ((1, (1, 1)), (length word, gridSize)) $
             [countFrom i cell | i <- [1..length word], cell <- cells]

    countFrom i cell
        | i == 1 && match = 1
        | match           = sum [counts!((i-1),n) | n <- neighbors!cell]
        | otherwise       = 0
      where
        match = rword ! i == gridArray ! cell

    neighbors = listArray (bounds gridArray) $
        [filter (inRange (bounds gridArray)) (neighbors8 cell)
            | cell <- cells ]

    rword    = listArray (1, length word) (reverse word)
    cells    = indices gridArray
    gridSize = snd (bounds gridArray)

{-

Tom Moertel <tom@moertel.com>
2006-08-15 (revised 2006-09-01)

Haskell-based solution to the Google Code Jam problem "countPaths" 
See http://www.cs.uic.edu/~hnagaraj/articles/code-jam/ for more.

This implementation is based on the dynamic-programming strategy
mentioned by reddit.com user "psykotic":
http://programming.reddit.com/info/dni1/comments/cdp59.

-}

module Main (main) where

import Control.Monad
import Data.Array

main = do
    word:gridspec <- liftM words getContents
    print $ (countPaths word (toGridArray gridspec) :: Integer)

countPaths word grid =
    sum . elems $ foldl move counts0 (tail (reverse word))
  where
    move counts c  = step c $ sum . map (counts!) . neighbors
    counts0        = step (last word) (const 1)
    step c f       = listArray (bounds grid) $ map (match c f) cells
    match c f cell = if c == grid!cell then f cell else 0
    neighbors cell = filter (inRange (bounds grid)) (neighbors8 cell)
    cells          = indices grid

toGridArray gridspec@(l1:_) =
    listArray ((1,1), (length gridspec, length l1)) (concat gridspec)

neighbors8 (r,c) =
    [(h, v) | h <- [r-1..r+1], v <- [c-1..c+1], h /= r || v /= c]

-- Local Variables:  ***
-- compile-command: "ghc -O2 -o wordpathdp --make WordPathDP.hs" ***
-- End: ***

Posted in programming, haskell, fun stuff
Tags code, countpaths, google, haskell, jam, puzzles, wordpaths
9 comments
no trackbacks
 

Comments

Leave a response

1. nukeedit
   Kartik Agaram said 16 days later:
   

   Hi, I didn’t quite solve the problem itself, but I’ve been trying to make sense of your solution with my incomplete haskell skills. I’ve documented my progress in a tiddlywiki

   It’s still incomplete; I’ve focussed so far on toNeighborMap which first caught my attention by being totally opaque ;)

   Two lessons I’ve learnt so far have been how easy a pure functional language is to refactor, and how to do blackbox probing in haskell. I refactored toNeighborMap into 2 new functions, and the description for one of them contains a nice IMO account of blackbox probing.

   I suspect as I go further I will eliminate toNeighborMap entirely and create a new name for the main do block in countPaths.

2. nukeedit
   Tom Moertel said 17 days later:
   

   Kartik, the function toNeighborMap in my original implementation converts the grid array into a “neighbor map” that serves as a look-up table to speed the main search. The neighbor map relates a given letter-transition pair to the set of all cells on the grid that participate in that transition. For example, if you looked up the transition ('A','B') in the neighbor map, the result would be the set of cells that contain 'A' and have 'B' cells as neighbors.

   If you look at my revised implementation in Update 2, however, you’ll see that the underlying dynamic-programming algorithm makes the neighbor map unnecessary.

   Further, even the Update-2 implementation can be improved. Access to the cache array counts proceeds in an orderly march, from small to large paths, that requires only two levels of the array at any given time. Thus we could replace counts with an array of lesser dimension that is folded through the path’s letters to result in the final maximum-path array, which is all that is needed to compute the result. If I have a spare moment, I’ll code it up.

3. nukeedit
   irieb@mac.com said 109 days later:
   

   here’s my java solution – I think it does the trick…

   import org.apache.commons.lang.time.StopWatch;
   
   import java.util.List;
   import java.util.ArrayList;
   
   public class Challange {
   
       private static char[][] _neighborhood;
       private static char[] _searchString;
   
       private static int _height;
       private static int _width;
   
       private static long foundCount;
   
       public long run(String[] grid, String searchString, boolean validate) {
           if (validate) {
               if (grid.length < 1) {
                   return -3;
               }
               if ((grid[0].length() == 0)) {
                   return -2;
               }
               String lastRow = null;
               for (String s : grid) {
                   if (lastRow != null) {
                       if (s.length() != lastRow.length()) {
                           return -4;
                       }
                   }
                   lastRow = s;
               }
           }
   
           init(grid, searchString);
           buildGrid(grid);
           //printGrid();
           try {
               findPaths();
           } catch (LimitExceededException e) {
               return -1;
           }
           return foundCount;
       }
   
       private void init(String[] grid, String searchString) {
           _height = grid.length;
           _width = grid[0].length();
           _neighborhood = new char[_height][_width];
           _searchString = searchString.toCharArray();
       }
   
       private void findPaths() throws LimitExceededException {
           for (int x = 0; x < _height; x++) {
               char[] chars = _neighborhood[x];
               for (int y = 0; y < _width; y++) {
                   char currentChar = _neighborhood[x][y];
                   if (currentChar == _searchString[0]) {
                       if (_searchString.length == 1) {
                           foundCount++;
                       } else {
                           Neighbor neighbor = new Neighbor(x, y, chars[y], 0);
                           findPath(neighbor);
                       }
                   }
               }
           }
       }
   
       private void findPath(Neighbor neighbor) throws LimitExceededException {
           List<Neighbor> friendlyNeighbors = getFriendlyNeighbors(neighbor);
           for (Neighbor foundNeighbor : friendlyNeighbors) {
               findPath(foundNeighbor);
           }
       }
   
       private String addPadding(int depth) {
           String pad = depth + ">";
           for (int x = 0; x < depth; x++) {
               pad += " ";
           }
           return pad;
       }
   
       private List<Neighbor> getFriendlyNeighbors(Neighbor neighbor) throws LimitExceededException {
           int depth = neighbor.depth + 1;
           char targetChar = _searchString[depth];
           List<Neighbor> frienlyNeighbors = new ArrayList<Neighbor>();
           int xPlace = neighbor.x - 1;
           for (int x = 0; x < 3; x++) {
               int yPlace = neighbor.y - 1;
               if (xPlace >= 0 && xPlace < _height) {
                   for (int y = 0; y < 3; y++) {
                       if (yPlace >= 0 && yPlace < _width) {
                           char currentChar = _neighborhood[xPlace][yPlace];
                           if (currentChar == targetChar) {
                               Neighbor friendlyNeighbor = new Neighbor(xPlace, yPlace, currentChar, depth);
                               if (!friendlyNeighbor.equals(neighbor)) {
                                   if (depth == _searchString.length - 1) {
                                       foundCount++;
                                       if (foundCount > 1000000) {
                                           throw new LimitExceededException();
                                       }
                                   } else {
                                       frienlyNeighbors.add(friendlyNeighbor);
                                   }
                               }
                           }
                       }
                       yPlace++;
                   }
               }
               xPlace++;
           }
           return frienlyNeighbors;
   
       }
   
       private void buildGrid(String[] grid) {
           for (int i = 0; i < _height; i++) {
               String line = grid[i];
               for (int ii = 0; ii < line.length(); ii++) {
                   _neighborhood[i][ii] = line.charAt(ii);
               }
           }
       }
   
       private static void printGrid() {
           StringBuilder sb = new StringBuilder();
           for (char[] aNeighborhood : _neighborhood) {
               for (char aChar : aNeighborhood) {
                   sb.append(aChar);
               }
               sb.append("\n");
           }
           System.out.println(sb.toString());
       }
   
       private class Neighbor {
           public int x;
           public int y;
           public char ch;
           public int depth;
   
           public Neighbor(int x, int y, char ch, int depth) {
               this.x = x;
               this.y = y;
               this.ch = ch;
               this.depth = depth;
           }
   
           public boolean equals(Object o) {
               if (this == o) return true;
               if (o == null || getClass() != o.getClass()) return false;
   
               final Neighbor neighbor = (Neighbor) o;
   
               if (x != neighbor.x) return false;
               if (y != neighbor.y) return false;
   
               return true;
           }
   
           public int hashCode() {
               int result;
               result = x;
               result = 29 * result + y;
               return result;
           }
   
           public String toString() {
               return "Neighbor{" +
                       "x=" + x +
                       ", y=" + y +
                       ", depth=" + depth +
                       ", ch=" + ch +
                       '}';
           }
       }
   
       private class LimitExceededException extends Exception {
       }
   
       public static void main(String[] args) {
   
           //2
           String searchString = "ABCDEA";
           String[] grid = {
                   "ABC",
                   "FED",
                   "GAI"};
   
           //1
           String searchString2 = "ABCDEFGHI";
           String[] grid2 = {
                   "ABC",
                   "FED",
                   "GHI"};
   
           //0
           String searchString3 = "ABCD";
           String[] grid3 = {
                   "ABC",
                   "DEF",
                   "GHI"};
   
           //108
           String searchString4 = "AAAA";
           String[] grid4 = {
                   "AA",
                   "AA"};
   
           //56448
           String searchString5 = "ABABABBA";
           String[] grid5 = {
                   "ABABA",
                   "BABAB",
                   "ABABA",
                   "BABAB",
                   "ABABA" 
           };
   
           //56448
           String searchString6 = "AAAAAAAAAAA";
           String[] grid6 = {
                   "AAAAA",
                   "AAAAA",
                   "AAAAA",
                   "AAAAA",
                   "AAAAA" 
           };
   
           String searchString7 = "A";
           String[] grid7 = {
                   "A" 
           };
   
           Challange challange = new Challange();
   
           StopWatch stopWatch = new StopWatch();
   
           long pathsFound;
           stopWatch.start();
           pathsFound = challange.run(grid5, searchString5, false);
           stopWatch.stop();
   
           System.out.println("foundPaths = " + pathsFound);
           System.out.println("completed in: " + stopWatch.getTime());
       }
   }
   

4. nukeedit
   irieb@mac.com said 109 days later:
   

   I tinkered with the problem again this morning and have come up with a mush better solution – it’s about 8 times faster now

   
   import org.apache.commons.lang.time.StopWatch;
   
   public class Challange {
   
       public static final long MAX_RESULTS = 1000000000;
   
       private static char[][] _neighborhood;
       private static char[] _searchString;
   
       private static int _height;
       private static int _width;
   
       private static long foundCount;
   
       public long run(String[] grid, String searchString, boolean validate) {
           if (validate) {
               if (grid.length < 1 || grid.length > 50) {
                   return -2;
               }
               if ((grid[0].length() == 0)) {
                   return -3;
               }
               String lastRow = null;
               for (String s : grid) {
                   String uppered = s.toUpperCase();
                   if (!uppered.equals(s)) {
                       return -5;
                   }
                   if (lastRow != null) {
                       if (s.length() != lastRow.length()) {
                           return -4;
                       }
                   }
                   lastRow = s;
               }
               if (searchString == null || searchString.length() < 1 || searchString.length() > 50) {
                   return -6;
               }
           }
   
           init(grid, searchString);
           buildGrid(grid);
           //printGrid();
           try {
               findPaths();
           } catch (LimitExceededException e) {
               return -1;
           }
           return foundCount;
       }
   
       private void init(String[] grid, String searchString) {
           _height = grid.length;
           _width = grid[0].length();
           _neighborhood = new char[_height][_width];
           _searchString = searchString.toCharArray();
       }
   
       private void findPaths() throws LimitExceededException {
           for (int x = 0; x < _height; x++) {
               for (int y = 0; y < _width; y++) {
                   char currentChar = _neighborhood[x][y];
                   if (currentChar == _searchString[0]) {
                       if (_searchString.length == 1) {
                           foundCount++;
                       } else {
                           findCurrentPaths(x, y, 0);
                       }
                   }
               }
           }
       }
   
       private void findCurrentPaths(int x, int y, int depth) throws LimitExceededException {
           depth++;
           char targetChar = _searchString[depth];
           int xPos = Math.max(0, x - 1);
           int i = Math.max(0, y - 1);
           while (xPos < _height && xPos <= x + 1) {
               int yPos = i;
               while (yPos < _width && yPos <= y + 1) {
                   char currentChar = _neighborhood[xPos][yPos];
                   if (currentChar == targetChar) {
                       if (!(xPos == x && yPos == y)) {
                           if (depth == _searchString.length - 1) {
                               foundCount++;
                               if (foundCount > MAX_RESULTS) {
                                   throw new LimitExceededException();
                               }
                           } else {
                               findCurrentPaths(xPos, yPos, depth);
                           }
                       }
                   }
                   yPos++;
               }
               xPos++;
           }
       }
   
       private void buildGrid(String[] grid) {
           for (int i = 0; i < _height; i++) {
               String line = grid[i];
               for (int ii = 0; ii < line.length(); ii++) {
                   _neighborhood[i][ii] = line.charAt(ii);
               }
           }
       }
   
       private static void printGrid() {
           StringBuilder sb = new StringBuilder();
           for (char[] aNeighborhood : _neighborhood) {
               for (char aChar : aNeighborhood) {
                   sb.append(aChar);
               }
               sb.append("\n");
           }
           System.out.println(sb.toString());
       }
   
       private class LimitExceededException extends Exception {
       }
   
       public static void main(String[] args) {
   
           //2
           String searchString = "ABCDEA";
           String[] grid = {
                   "ABC",
                   "FED",
                   "GAI"};
   
           //1
           String searchString2 = "ABCDEFGHI";
           String[] grid2 = {
                   "ABC",
                   "FED",
                   "GHI"};
   
           //0
           String searchString3 = "ABCD";
           String[] grid3 = {
                   "ABC",
                   "DEF",
                   "GHI"};
   
           //108
           String searchString4 = "AAAA";
           String[] grid4 = {
                   "AA",
                   "AA"};
   
           //56448
           String searchString5 = "ABABABBA";
           String[] grid5 = {
                   "ABABA",
                   "BABAB",
                   "ABABA",
                   "BABAB",
                   "ABABA" 
           };
   
           String searchString7 = "AC";
           String[] grid7 = {
                   "ABCDEFGHIJKLMNOPQRSTUVWZYZABCDEFGHIJKLMNOPQRSTUV",
                   "BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "CAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "DAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "EAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "FAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "GAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "HAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "IAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "JAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "KAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "LAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "MAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "NAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "OAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "PAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "QAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "RAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "SAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "TAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "UAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "VAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "WAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "XAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "WAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "ZAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "NAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "NAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
                   "NAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
   
           };
   
           //-1
           String searchString8 = "AAAAAAAAAAA";
           String[] grid8 = {
                   "AAAAA",
                   "AAAAA",
                   "AAAAA",
                   "AAAAA",
                   "AAAAA" 
           };
   
           Challange challange = new Challange();
           StopWatch stopWatch = new StopWatch();
           long pathsFound;
   
           stopWatch.start();
           long startTime = System.nanoTime();
           pathsFound = challange.run(grid3, searchString3, false);
           long endTime = System.nanoTime();
           stopWatch.stop();
   
           System.out.println("foundPaths = " + pathsFound);
           System.out.println("completed in: (nano: " + (endTime - startTime) + ", mill: " + stopWatch.getTime());
       }
   }
   

5. nukeedit
   Frank Cao said 185 days later:
   

   This C++ solution took me 2.5 hours, to hit the anser. Found 6 bugs in the code. Shame on me. If I don’t have the answers given in the problem statement, I probably can’t get it right. So, it is not easy to work in Google!

   //Found the problem in http://www.cs.uic.edu/~hnagaraj/articles/code-jam/
   //Wrote 1.5 hours, debug 1 hour. 6 bugs after compile
   
   #include <iostream>
   #include <string>
   #include <vector>
   #include <cstring>
   #include <cassert>
   #define ROW_MAX        50
   #define COL_MAX        50
   #define PATH_STR_MAX     (1<<10)
   #define INF        100000
   using namespace std;
   
   int FindStrCount(char  rgrgGrid[ROW_MAX][COL_MAX], int nRows, int nCols, char* rgString, int nStrLen)
   {
       int TempCharCounts1[ROW_MAX][COL_MAX];
       int TempCharCounts2[ROW_MAX][COL_MAX];
       int * pCharCounts = NULL;
       int * pNextCharCounts = NULL;
       int nTotalPaths=0;
       for ( int i =0; i<nRows; i++) 
       {
           for ( int j =0; j<nCols; j++) 
           {
               memset(TempCharCounts1, '\0', ROW_MAX*COL_MAX*sizeof(int)); //BUG used to be '0'
               memset(TempCharCounts2, '\0', ROW_MAX*COL_MAX*sizeof(int));
               if (rgrgGrid[i][j]==rgString[0])
               {
                   TempCharCounts1[i][j]=1;
                   bool bUseCount1 = true;
                   for ( int k =1; k<nStrLen; k++) //BUG used to be k=0
                   {
                       if (bUseCount1)
                       {
                           pCharCounts = (int *)TempCharCounts1; //BUG Did not know how to pass double arrays
                           pNextCharCounts = (int *)TempCharCounts2;
                       } else 
                       {
                           pCharCounts = (int *)TempCharCounts2;
                           pNextCharCounts = (int *)TempCharCounts1;
                       }
                       memset(pNextCharCounts, '\0', ROW_MAX*COL_MAX*sizeof(int)); //BUG: Missed this
                       for ( int l =0; l<nRows; l++) {
                           for ( int m =0; m<nCols; m++) {
                               if (0!=pCharCounts[l*COL_MAX+m])
                               {
                                   //update neighbors if the next char match
                                   for (int p=l-1; p<=l+1; p++)
                                   {
                                       if (p<0||p>=nRows) continue; //out of range
                                       for (int q=m-1; q<=m+1; q++) //BUG: for (int q=-1; q<=+1; q++)
                                       {
                                           if (p==l && q==m) continue; //did not move, ignore //BUG missed this
                                           if (q<0||q>=nCols) continue; //out of range
                                           if (rgString[k]==rgrgGrid[p][q])
                                           {
                                               pNextCharCounts[p*COL_MAX+q]+=pCharCounts[l*COL_MAX+m];
                                           }
                                       }
                                   }
                               }
                           }
                       }
                       bUseCount1 = !bUseCount1;
                   }
                   //add all numbers in the matrix of pCharCounts to nTotalPaths
                   for ( int x =0; x<nRows; x++) 
                   {
                       for ( int y =0; y<nCols; y++) 
                       {
                           nTotalPaths+=pNextCharCounts[x*COL_MAX+y]; //TODO watch for overflow
                           if (nTotalPaths>1000000000) return -1;
                       }
                   }
               }
               cout<<"Current count is: "<<nTotalPaths<< endl;
           }
       }
       return nTotalPaths;
   }
   
   main()
   {
       char path[PATH_STR_MAX];
       int rows, cols, path_sz;
   
       char grid[ROW_MAX][COL_MAX] = {
           {'A','B','A','B','A'},
           {'B','A','B','A','B'},
           {'A','B','A','B','A'},
           {'B','A','B','A','B'},
           {'A','B','A','B','A'}
       };
       strcpy(path, "ABABABBA");
       rows = 5;
       cols = 5;
   /*
       char grid[ROW_MAX][COL_MAX] = {
           {'A', 'A'},
           {'A', 'A'}
       };
       strcpy(path, "AAAA");
       rows = 2;
       cols = 2;
   */
       path_sz = (int) strlen(path);
   
       assert(rows < ROW_MAX);
       assert(cols < COL_MAX);
       assert(path_sz < PATH_STR_MAX);
   
       cout << FindStrCount(grid, rows, cols, path, path_sz) << endl;
   return;
   }
   

6. nukeedit
   hsisahens@yahoo.co.in said 298 days later:
   

   My C++ solution is generalised but for the fact that it follows the original specification of 50×50 grid and 50 character long word. It can count and display correctly any digited numbers being limited only by RAM availibility. However the major drawback is its preformance. Its damn slow.Guess recursion is taking its toll.

   the code ;

   #include <iostream.h>
   #include <conio.h>
   #include <string.h>
   #include <stdio.h>
   #include <stdlib.h>
   
   int WORDLEN;
   int MAX_ROW;
   int MAX_COL;
   char WORD[50];
   char GRID[50][50];
   struct NOW
   {
   int digit;
   NOW *lp;
   NOW *rp;
   };
   NOW* PTR=new NOW;
   NOW* CPTR=PTR;
   NOW* R=PTR;
   
   void search(char,int,int,int);
   void get_grid();
   void get_word();
   void display_result();
   void found_a_way();
   
   void main()
   {
   clrscr();
   get_grid();
   char ch='y';
   while(ch=='y' || ch=='Y')
   {
       PTR->digit=0;
       PTR->lp=NULL;
       PTR->rp=NULL;
       get_word();
       int level=1;
       search(WORD[level-1],-1,-1,level);
       display_result();
       cout<<"\nPress y for another word or any other key to quit";
       ch=getch();
   }
   
   }
   
   void search(char a,int row,int col,int level)
   {
   int row_ul=1,row_bl=MAX_ROW,col_rl=MAX_COL,col_ll=1;
   if (level!=1)
   {
       row_ul=row==1 ? 1 : row-1;
       row_bl=row==MAX_ROW ? MAX_ROW:row+1;
       col_rl=col==MAX_COL ? MAX_COL : col+1;
       col_ll=col==1 ? 1 : col-1;
   }
   for (int rowc=row_ul-1;rowc<row_bl;rowc++)
   {
       for (int colc=col_ll-1;colc<col_rl;colc++)
       {
           if(!(rowc==row-1 && colc==col-1))
           {
   
               if(GRID[rowc][colc]==a)
               {
   
                   if(level==WORDLEN)
                   {
   
                       found_a_way();
   
                   }
                   else
                   {
   
                       search(WORD[level],rowc+1,colc+1,level+1);
                   }
   
               }
           }
       }
   
   }
   level--;
   return;
   }
   
   void get_word()
   {
   cout<<"\n\nEnter the word to search for : ";
   gets(WORD);
   WORDLEN=strlen(WORD);
   return;
   }
   
   void get_grid()
   {
   cout<<"\nEnter no of rows : ";
   cin>>MAX_ROW;
   cout<<"\nEbter no of coloumns : ";
   cin>>MAX_COL;
   cout<<"\nEnter the alphabet grid : ";
   char c;
   for(int r=0;r<MAX_ROW;r++)
   {
       for(int c=0;c<MAX_COL;c++)
       {
           cin>>GRID[r][c];
   
       }
   }
   
   }
   
   void found_a_way()
   {
   
   while(CPTR->digit==9 && CPTR->lp)
   {
       CPTR->digit=0;
       CPTR=CPTR->lp;
   }
   if(CPTR->digit!=9)
   {
       CPTR->digit++;
   }
   else
   {
       if(! CPTR->lp)
       {
           CPTR->digit=0;
           R=new NOW;
           CPTR->lp=R;
           R->rp=CPTR;
           CPTR=R;
           CPTR->lp=NULL;
           CPTR->digit=1;
       }
   }
   CPTR=PTR;
   return;
   }
   
   void display_result()
   {
   CPTR=R;
   cout<<"The total no of ways in which the word can be spelled is : \n";
   do
   {
       cout<<CPTR->digit;
       CPTR=CPTR->rp;
   }
   while (CPTR);
   return;
   }
   

   output ;

   Enter no of rows : 5
   
   Ebter no of coloumns : 5
   
   Enter the alphabet grid : aaaaa
   aaaaa
   aaaaa
   aaaaa
   aaaaa
   
   Enter the word to search for : aa
   The total no of ways in which the word can be spelled is :
   144
   Press y for another word or any other key to quit
   
   Enter the word to search for : aaaaaaaaaaa
   The total no of ways in which the word can be spelled is :
   2745564335
   Press y for another word or any other key to quit
   
   Enter the word to search for : aaaaaa
   The total no of ways in which the word can be spelled is :
   243263
   Press y for another word or any other key to quit
   
   Enter the word to search for : aaaaaaaa
   The total no of ways in which the word can be spelled is :
   10164599
   Press y for another word or any other key to quit
   
   Enter the word to search for : aaaaaaaaa
   The total no of ways in which the word can be spelled is :
   65708927
   Press y for another word or any other key to quit
   

7. nukeedit
   hsisahens@yahoo.co.in said 336 days later:
   

   Here’s a different algo , a rather optimized one and i clocks less than a sec for the full 50×50 size of 50 words search.. !

   #include

   #include

   #include

   #include

   void main()

   {

   // defining variables

   register int i,j,r,c=0,wc,l,ROWMAX=50,COLMAX=50,WORDLEN,element,d,p,e;

   register char WORD[50],GRID50[50],a,b,ch;

   register long double sum,no_of_paths,RM2[2500];

   // accepting and displaying the grid and the word to serach for

   // setting the ROWMAX COLMAX and WORDLEN

   cout<<”\n Use test case for maximum length ? (y/n) : ” ;

   cin>>ch;

   if(!(ch==’y’ || ch==’Y’ ))

   {

   c=1;

   cout<<"\nEnter the no of rows : ";

   cin>>ROWMAX;

   cout<<"\nEnter the no. of coloumns : ";

   cin>>COLMAX;

   }

   l=0;

   while(l<=1)

   {

   if(l==1 && c==1)

   {

   cout<<"\nThe grid entered by you is : \n";

   }

   for(i=0;i

   {

   for(j=0;j

   {

   if(!l)

   {

   if(c==1) cin>>GRID[i][j];

   else GRID[i][j]='a';

   }

   else

   {

   if(c==1) cout<

   }

   }

   if(l==1 && c==1) cout<<"\n";

   }

   l++;

   }

   if(c==1)

   {cout<<”\nEnter the eord to search for : ”;

   gets(WORD);

   }

   else

   {

   for(i=0;i

   }

   WORDLEN=strlen(WORD);

   e=0;

   // The real calculation

   for (wc=WORDLEN-1;wc>=0;wc—)

   {

   e++;

   d=0;p=1;

   if(e%2==0) { d=1;p=0;}

   a=WORD[wc];

   element=-1;

   for(r=0;r

   {

   for(c=0;c

   {

   element++;

   b=GRID[r][c];

   if(wc==WORDLEN-1)

   {

   RM[d][element]= b==a ? 1 : 0;

   }

   else

   {

   if(b==a)

   {

   sum=0;

   for(i=-1;i<=1;i++)

   {

   if((r==0 && i==-1) || (r==ROWMAX-1 && i==1)) continue;

   for(j=-1;j<=1;j++)

   {

   l=0;

   if((c==0 && j==-1) || (c==COLMAX-1 && j==1)) continue;

   l=(r+i)ROWMAX+(c+j);

   if(!(l>ROWMAXCOLMAX-1 || l|| (r+i)/))

   {

   sum+=RM[p][l];

   }

   }

   }

   RM[d][element]=sum;

   }

   else

   {

   RM[d][element]=0;

   }

   }

   }

   }

   }

   no_of_paths=0;

   for(i=0;i<=element;i++)

   {

   no_of_paths+=RM[d][i];

   }

   cout<<”\nThe no of paths in which the word can be spelled is ”<

   getch();

   }

8. nukeedit
   Oeil_de_taupe said 692 days later:
   

   Here is my solution (I think it works). It takes 5 seconds for a grid composed of 1000×1000 “A” searching for “AAAAAAAAAAA”. (I use a Pentium3 0.7 Ghz).

   
   #include<stdbool.h>
   #include<stdlib.h>
   #include<stdio.h>
   typedef unsigned long long uint;
   #define TAILLE_GRILLE 1000
   
   void **mkSquareMatrix(uint size, size_t tailleCell);
   void freeSquareMatrix(void **matrix, uint size);
   uint sumElements(uint **matrix, uint size);
   inline void updatePaths(
       uint sizeM, 
       uint x, uint y,
       uint **before, uint **after);
   
   int main(void)
   {
       char grille[TAILLE_GRILLE][TAILLE_GRILLE];
       const char *path = "AAAAAAAAAAA";
   
       for(int line = 0; line < TAILLE_GRILLE; line++)
           for(int col = 0; col < TAILLE_GRILLE; col++)    
               grille[line][col] = 'A';
   
       uint **paths = (uint**)
           mkSquareMatrix(TAILLE_GRILLE, sizeof(uint));
   
       // cas trivial (path long de une seule lettre)
       for(int line = 0; line < TAILLE_GRILLE; line++)
           for(int col = 0; col < TAILLE_GRILLE; col++)
               if(grille[line][col] == *path)
                   paths[line][col] = 1;
   
       // pour chacune des composantes du path
       for(char c = *(++path); c; c = *(++path))
       {
           uint **pathsSuivants = (uint**)
             mkSquareMatrix(TAILLE_GRILLE, sizeof(uint));
   
           // pour chacune des cases de la grille
           for(int noCas = 0; noCas < TAILLE_GRILLE*TAILLE_GRILLE; noCas++)
               if(c==grille[noCas/TAILLE_GRILLE][noCas%TAILLE_GRILLE])
                   updatePaths(
                       TAILLE_GRILLE, 
                       noCas/TAILLE_GRILLE,
                       noCas%TAILLE_GRILLE,
                       paths, pathsSuivants);
   
           freeSquareMatrix((void**)paths, TAILLE_GRILLE);
           paths = pathsSuivants;
       }
   
       printf("%llu\n", sumElements(paths, TAILLE_GRILLE));
       freeSquareMatrix((void**)paths, TAILLE_GRILLE);
       return EXIT_SUCCESS;
   }
   
   void **mkSquareMatrix(uint size, size_t tailleCell)
   {
       void **matrix = malloc(size * sizeof(void*));
   
       for(uint line = 0; line < size; line++)
           matrix[line] = calloc(size, tailleCell);
       return matrix;
   }
   
   void freeSquareMatrix(void **matrix, uint size)
   {
       for(int line = 0; line < size; line++)
           free(matrix[line]);
       free(matrix);
   }
   
   uint sumElements(uint **matrix, uint size)
   {
       uint sum = 0;
       for(int line = 0; line < size; line++)
           for(int colonne = 0; colonne < size; colonne++)
               sum += matrix[line][colonne];
       return sum;
   }
   
   inline void updatePaths(
       uint sizeM, 
       uint x, uint y,
       uint **before, uint **after)
   {
       for(int line = -1; line <= 1; line++)
       {
           if(line == -1 && x == 0 ||
              line == 1 && x == sizeM-1)
               continue;
   
           for(int col = -1; col <= 1; col++)
           {
               if(line == 0 && col == 0 ||
                  col == -1 && y == 0 ||
                  col == 1 && y == sizeM-1)
                      continue;
               after[x][y] += before[x+line][y+col];
           }
       }
   }
   

   Sorry for my English…

9. nukeedit
   Busayo said 1301 days later:
   

   I just began programming and am i program using c#..... i am really interested in knowing algorithms, data structures and other stuffs… can someone please guide me through (any books, sites, blogs etc that can help)

   Keep up the good work on this blog, i really appreciate it..

Trackbacks

Use the following link to trackback from your own site:
http://blog.moertel.com/articles/trackback/154

RSS feed for this post trackback uri

Your name	(leave url/email »)
Your blog
Your email
Your message
Comment Markup Help Preview comment