Pascal's Square

Computer Science Level 4

On a Boggle grid, one can draw words by starting at a square, and then adding letters by tracing a path through the grid, going up, down, left, right, or diagonally, so long as no square is visited twice.

Consider the square grid above. How many ways can you spell 'COMBINATORICS' in it?


The answer is 4979777.

View wiki
Daniel Ploch by Daniel Ploch , 31, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Brian Riccardi
Sep 30, 2014

A simple solution via Dynamic Programming: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef long long ll;

char grid[15][15];
int mem[15][15];

ll solve(int i, int j)
{
        if( i<0 || i>12 || j<0 || j>12 ) return 0;
        if( mem[i][j]!=-1 ) return mem[i][j];
        if( j==12 ) return mem[i][j]=1;

        return solve(i-1,j+1)+solve(i,j+1)+solve(i+1,j+1);
}

int main()
{
        freopen("input.txt", "r", stdin);

        memset( mem, -1, sizeof(mem) );
        for(int i=0; i<13; i++) cin >> grid[i];

        ll ans=0;
        for(int i=0; i<13; i++) ans+=solve(i,0);

        cout << ans << endl;

        return 0;
}

1 Helpful 0 Interesting 0 Brilliant 0 Confused

To get a significant speed up why not:

for(int i=0; i<7; i++) ans+=solve(i,0); ans = ans*2+solve(7,0); cout << ans << endl;

Ed Sirett - 4 years, 7 months ago

Hi great solution, i have mad this program especialy to solve this problem, check it out https://www.youtube.com/watch?v=dZ1rOGeiviA

Elmokhtar Mohamed Moussa - 5 years, 8 months ago
Daniel Ploch
Jul 23, 2014

As is so subtly hinted in the problem title, the solution can be derived in much the same way as Pascal's Triangle can be generated: by taking the sum of adjacent elements in the previous row.

Here, the 'rows' are the columns of the grid. We define the function n ( x , y ) n(x, y) to be the number of ways to reach the cell at row y y , column x x while spelling out 'COMBINATORICS'. We specify n ( x , y ) = 0 n(x, y) = 0 anywhere it is not otherwise defined. Thus, we get:

n ( 0 , y ) = 1 ∀ y ∈ { 0...12 } n(0, y) = 1\;\forall y \in \{0...12\}

n ( x , y ) = n ( x − 1 , y − 1 ) + n ( x − 1 , y ) + n ( x − 1 , y + 1 ) ∀ x ∈ { 1...12 } and ∀ y ∈ { 0...12 } n(x, y) = n(x-1, y-1) + n(x-1, y) + n(x-1, y+1)\;\forall\:x \in \{1...12\}\;\text{and}\;\forall\:y \in \{0...12\}

By computing and caching the values of n ( x , y ) n(x, y) one column at a time, from left to right, we only need to do 13 ∗ 13 = 169 13 * 13 = 169 calculations. The answer is then:

∑ y = 0 12 n ( 12 , y ) = 4979777 \sum\limits_{y=0}^{12} n(12, y) = 4979777

1 Helpful 0 Interesting 0 Brilliant 0 Confused

http://oeis.org/A081113

Patrick Corn - 6 years, 10 months ago
Hunter Killer
Jan 15, 2015

Write down the path matrix Q= 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
    {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1}

The answer is the sum of all entry of Q 12 Q^{12}

( 15511 26324 29964 27016 20240 12804 6853 3080 1143 340 77 12 1 26324 45475 53340 50204 39820 27093 15884 7996 3420 1220 352 78 12 29964 53340 65715 66144 57057 42900 28236 16224 8073 3432 1221 352 77 27016 50204 66144 72568 69224 58200 43240 28313 16236 8074 3432 1220 340 20240 39820 57057 69224 73711 69564 58277 43252 28314 16236 8073 3420 1143 12804 27093 42900 58200 69564 73788 69576 58278 43252 28313 16224 7996 3080 6853 15884 28236 43240 58277 69576 73789 69576 58277 43240 28236 15884 6853 3080 7996 16224 28313 43252 58278 69576 73788 69564 58200 42900 27093 12804 1143 3420 8073 16236 28314 43252 58277 69564 73711 69224 57057 39820 20240 340 1220 3432 8074 16236 28313 43240 58200 69224 72568 66144 50204 27016 77 352 1221 3432 8073 16224 28236 42900 57057 66144 65715 53340 29964 12 78 352 1220 3420 7996 15884 27093 39820 50204 53340 45475 26324 1 12 77 340 1143 3080 6853 12804 20240 27016 29964 26324 15511 ) \left( \begin{array}{ccccccccccccc} 15511 & 26324 & 29964 & 27016 & 20240 & 12804 & 6853 & 3080 & 1143 & 340 & 77 & 12 & 1 \\ 26324 & 45475 & 53340 & 50204 & 39820 & 27093 & 15884 & 7996 & 3420 & 1220 & 352 & 78 & 12 \\ 29964 & 53340 & 65715 & 66144 & 57057 & 42900 & 28236 & 16224 & 8073 & 3432 & 1221 & 352 & 77 \\ 27016 & 50204 & 66144 & 72568 & 69224 & 58200 & 43240 & 28313 & 16236 & 8074 & 3432 & 1220 & 340 \\ 20240 & 39820 & 57057 & 69224 & 73711 & 69564 & 58277 & 43252 & 28314 & 16236 & 8073 & 3420 & 1143 \\ 12804 & 27093 & 42900 & 58200 & 69564 & 73788 & 69576 & 58278 & 43252 & 28313 & 16224 & 7996 & 3080 \\ 6853 & 15884 & 28236 & 43240 & 58277 & 69576 & 73789 & 69576 & 58277 & 43240 & 28236 & 15884 & 6853 \\ 3080 & 7996 & 16224 & 28313 & 43252 & 58278 & 69576 & 73788 & 69564 & 58200 & 42900 & 27093 & 12804 \\ 1143 & 3420 & 8073 & 16236 & 28314 & 43252 & 58277 & 69564 & 73711 & 69224 & 57057 & 39820 & 20240 \\ 340 & 1220 & 3432 & 8074 & 16236 & 28313 & 43240 & 58200 & 69224 & 72568 & 66144 & 50204 & 27016 \\ 77 & 352 & 1221 & 3432 & 8073 & 16224 & 28236 & 42900 & 57057 & 66144 & 65715 & 53340 & 29964 \\ 12 & 78 & 352 & 1220 & 3420 & 7996 & 15884 & 27093 & 39820 & 50204 & 53340 & 45475 & 26324 \\ 1 & 12 & 77 & 340 & 1143 & 3080 & 6853 & 12804 & 20240 & 27016 & 29964 & 26324 & 15511 \\ \end{array} \right)

My solution is purely mathematics, just use computer program to do matrix multiplication. It can be potentially extended to many class of counting problem,

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Yes, the problem title is a hint. I solved the problem with a simple spreadsheet. It is just summing up the number of legal ways from the last column. The following shows the last column first. The second column the sum of the legal ways of first column and so on. The answer is the sum of the last column data.

1 2 5 13 35 96 267 750 2123 6046 17303 49721 143365

1 3 8 22 61 171 483 1373 3923 11257 32418 93644 271218

1 3 9 26 75 216 623 1800 5211 15115 43923 127853 372735

1 3 9 27 80 236 694 2038 5981 17551 51512 151238 444211

1 3 9 27 81 242 721 2143 6359 18846 55803 165120 488331

1 3 9 27 81 243 728 2178 6506 19406 57805 171973 511068

1 3 9 27 81 243 729 2185 6541 19553 58365 173975 517921

1 3 9 27 81 243 728 2178 6506 19406 57805 171973 511068

1 3 9 27 81 242 721 2143 6359 18846 55803 165120 488331

1 3 9 27 80 236 694 2038 5981 17551 51512 151238 444211

1 3 9 26 75 216 623 1800 5211 15115 43923 127853 372735

1 3 8 22 61 171 483 1373 3923 11257 32418 93644 271218

1 2 5 13 35 96 267 750 2123 6046 17303 49721 143365 

                                            4979777
0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...