[Problem Solving #4] Lego Mosaics

[wolfsinner]

Problem #4 - Lego Mosaics

 

So here's Problem #4 of the series. Again, I was really busy this week, so I didn't have time to come up with a problem. I used a problem from the Portuguese Inter-University Programming Marathon.

I recommend reading the original PDF or at the gateway, as the problem is better formatted there.
This one is either going to be really hard, or pretty accessible, depending on how comfortable you are with a certain Problem Solving method.

I won't be very active over the next few days, so I'm sorry if I can't help out as much as I'd like to. I'm sure the rest of the community will do their part.

 
Problem Description:
 
(This problem was a part of the 2011 edition of the Portuguese Inter-University Programming Marathon. You can download the original PDF file here.)
 
Building mosaics is an art dedicated to the construction of images by assembling small pieces of some material. Lego pieces are all about building things by assembling small pieces, and therefore they present the flexibility and versatility to create wonderful mosaics.
You have been commissioned to build a large lego mosaic. The basic idea is to use a lego plate and on the top of it attach some lego bricks. Each lego stud is like a pixel in the image. If we used text to represent a mosaic, with '.' representing a stud without a brick, 'R' for a red brick, 'Y' for a yellow brick and 'G' for a green brick, then the mosaic of the image below would be represented by:
 

For the construction of the mosaic you have available a very large set of 1xN bricks. In particular, for the purposes of the mosaic, you can assume you have an infinite number of 9 different types of bricks (in any needed color). These are 1x1, 1x2, 1x3, 1x4, 1x6, 1x8, 1x10, 1x12 and 1x16 bricks, and are depicted in the figure below.

 

For aesthetical reasons, you only want to use the bricks in the horizontal positions, that is, parallel to the bottom of the plate. This means that when seen from the top, as in the textual representation above, the width of the bricks is varible, but the height is always 1.
When you were starting the construction, you noticed that even with those constraints there were several different ways of building the mosaic. For example, the mosaic below has 16 different ways of using pieces to obtain the exact same image (with 'B' meaning a blue brick):
 

For a general case, can you tell in how many different ways you could build the desired mosaic?

Task
Given the description of a lego mosaic, your task is to compute in how many different ways you can build that mosaic assuming you have an infinite pool of 1x1, 1x2, 1x3, 1x4, 1x6, 1x8, 1x10, 1x12 and 1x16 lego bricks, in any color. The bricks must be positioned in horizontal positions.
 
Input:
 
(You can download the zip file containing all of the input files here.)
 
The first line of input contains two integers R and C, indicating respectively the number of rows and columns of the mosaic to be built.
The next R lines of input contain each exactly C characters detailing the mosaic to be built. Each character must either be '.' (representing a stud without any brick on top of it) or a capital letter (from 'A' to 'Z') representing a stud of a given color. Two bricks with the same letter representing it have the same color. You can assume that there is at least one brick in the mosaic.

Input example 1
4 4
....
YYBB
YBBB
....

Input example 2
3 6
GGRRRR
GYYRRR
GGRRRR
 
(All of the input data is too large to place here, so please use the zip file.)
 
Output:
The output should consist of a single integer W indicating the number of ways in which the mosaic can be build, given that you can only use bricks of type 1x1, 1x2, 1x3, 1x4, 1x6, 1x8, 1x10, 1x12 and 1x16 on horizontal positions. You can assume you always have enough bricks to build the mosaic using any combination of the bricks you need.
Your output must end with a line break.

Output example 1
16

Output example 2
2048

 
How to test your solution:
To submit your output solutions you need to run your code with each of the input files provided in the zip file, and place your output in the appropriate text box.
So your program's output with input from file "input1.txt" should be placed in the "Output 1" box.
 
I recommend downloading the zip file, and using command-line input redirection to send the file contents into the standard input stream of your program. In Windows, Linux or Mac OS, you would do something like:
[command to run your program] < inputN.txt
You can submit your output solutions through the problem solving gateway here.
 
Final notes:

• Create your account at the gateway with the same username as the one you use at the forums.
• Include your code in spoiler tags, so that the thread isn't cluttered with code.
• If you're having trouble solving the problem, ask the community for help! You may learn a lot from them.
• Don't worry too much about efficiency if you're starting out. Solve the problem first, we'll then tell you how to improve it.
• Please don't share the output solution if you've solved the problem.
• If the problem description isn't clear, please ask for further explanation!

[Ciccioo]

you know there's something wrong, when you write a recursive function with a dozen nested loops

[Ciccioo]

well nevermind

it's ugly, but it works

 

#include <stdio.h>#include <stdlib.h>size_t nextPiece(char* buf){    static char* cursor = NULL;    if(buf) cursor = buf;    while(*cursor == '.') cursor++;    if(*cursor == '\n') return 0;    char currentColor = *cursor;    size_t len = 1;    while(*(++cursor) == currentColor) len++;    return len;}size_t factorial(size_t n){    if(n<2) return 1;    size_t res = n;    while(--n)        res *= n;    return res;}size_t permutations(size_t a, size_t b, size_t c, size_t d, size_t e, size_t f, size_t g, size_t h, size_t i){    return factorial(a+b+c+d+e+f+g+h+i) / (        factorial(a) *        factorial(b) *        factorial(c) *        factorial(d) *        factorial(e) *        factorial(f) *        factorial(g) *        factorial(h) *        factorial(i)    );}size_t computeCombinations(size_t len, size_t* combinations){    if(combinations[len]) return combinations[len];    size_t a, b, c, d, e ,f, g, h;    for(a = 0; a * 16 <= len; a++)        for(b = 0; b * 12 + a * 16 <= len; b++)            for(c = 0; c * 10 + b * 12 + a * 16 <= len; c++)                for(d = 0; d * 8 + c * 10 + b * 12 + a * 16 <= len; d++)                    for(e = 0; e * 6 + d * 8 + c * 10 + b * 12 + a * 16 <= len; e++)                        for(f = 0; f * 4 + e * 6 + d * 8 + c * 10 + b * 12 + a * 16 <= len; f++)                            for(g = 0; g * 3 + f * 4 + e * 6 + d * 8 + c * 10 + b * 12 + a * 16 <= len; g++)                                for(h = 0; h * 2 + g * 3 + f * 4 + e * 6 + d * 8 + c * 10 + b * 12 + a * 16 <= len; h++){                                    size_t units = len - (h * 2 + g * 3 + f * 4 + e * 6 + d * 8 + c * 10 + b * 12 + a * 16);                                    combinations[len] += permutations(a, b, c, d, e, f, g, h, units);                                }    return combinations[len];}int main(){    size_t R, C, i;    scanf("%zu %zu\n", &R, &C);    C+=3; // i don't understand this one    char* lineBuffer = malloc(C * sizeof *lineBuffer);    size_t* combinations = calloc(C, sizeof *combinations);    size_t totalCombinations = 1;    for(i = 0; i < R; i++){        fgets(lineBuffer, C, stdin);        size_t newPiece = nextPiece(lineBuffer);        do            totalCombinations *= computeCombinations(newPiece, combinations);        while((newPiece = nextPiece(NULL)));    }    free(lineBuffer);    printf("%zu\n", totalCombinations);    return 0;}

 

TODO:

1. understand why i have to put that +3 in there. for now, i'm assuming it's for a "\n\r\0" (if i don't use that +3, the reading function goes terribly wrong)
2. replace the bagillion nested loops with a recursive function?
3. figure out if there is a method to make this work with long sequences of legos of the same color (right now it would need a BigInt or something)

appreciated the easter eggs

 

edit: i could post computeCombinations() in the "Bad, terrible or simply funny code examples" topic

[wolfsinner]

@Ciccioo, I can always count on you to write unexpected solutions.

Your solution is actually quite fast.

 

understand why i have to put that +3 in there. for now, i'm assuming it's for a "\n\r\0" (if i don't use that +3, the reading function goes terribly wrong)

 

It should be +2, because every line ends with a \r\n (I made the input files in Windows, my bad!).

 

 

replace the bagillion nested loops with a recursive function?

 

The optimal solution is written with Dynamic Programming. I wrote a dp iterative function with memoization. DP is awesome.

 

 

figure out if there is a method to make this work with long sequences of legos of the same color (right now it would need a BigInt or something)

 

This problem's solution values grow really fast even for small sequences. The only way to solve this for long sequences of legos is to use arbitrary-precision arithmetic (and even then it still grows too fast). It was really hard for me to find good test cases that could be represented by a signed integer (which can only represent up to 2³¹-1). You went ahead and stored it as an unsigned integer so I guess I could've gone with larger results.

 

I was wondering if you guys would notice the easter eggs haha

[fizzlesticks]

Eventually I'll solve one of these without making a stupid mistake when submitting.

 

I'm not a very mathy person so I went with a programming solution to get the number of combinations.

 

combinations = {1:1}def backtrack(l,ans,solutions):              blocks = [1,2,3,4,6,8,10,12,16]    numBlocks = len(blocks)    if l:        s = sum(l)        if s == ans:            solutions.append(list(l))            return True        elif s > ans:            return False    for i in range(0,numBlocks):        l.append(blocks[i])        backtrack(l,ans,solutions)        del l[-1]def getCombinations(x):    global combinations        n = combinations.get(x)    if n == None:        solutions = []        backtrack([],x,solutions)        n = len(solutions)        combinations[x] = n        return ndef main():    rows, cols = [int(x) for x in input().split()]    total = 1        for i in range(0,rows):        row = input()        if len(row) < 2:            continue                last = 0        cur = row[0]        for j in range(1,len(row)):            if cur == '.':                cur = row[j]                last = j                continue            elif row[j] != cur:                total *= getCombinations(j-last)                last = j                cur = row[j]        if cur != '.':            total *= getCombinations(len(row)-last)        print(total)if __name__ == "__main__":    from timeit import Timer    t = Timer(lambda: main())    print(t.timeit(number=1))

[wolfsinner]

Eventually I'll solve one of these without making a stupid mistake when submitting.

 

You submitted the first problem (Deletable Primes) with no mistakes.

 

EDIT: Yours is actually quite a good solution!

[Nuluvius]

The optimal solution is written with Dynamic Programming. I wrote a dp iterative function with memoization. DP is awesome.

 

That's what I've been spending my time (what little of it I have) reading through. Dynamic Programming, Memoization & Fibonacci number. Could have bruit forced it but knowing you it was only natural to assume that there would be a more eloquent methodology to be found.

[fizzlesticks]

You submitted the first problem (Deletable Primes) with no mistakes.

Ahh yes, I guess 1 for 4 isn't bad.

[Ciccioo]

@Ciccioo, I can always count on you to write unexpected solutions.

the plan is to write good ones, but unexpected are fine too

 

It should be +2, because every line ends with a \r\n (I made the input files in Windows, my bad!).

i tried with +2, it works with t0 but not with t1. it works with t1 if i replace \r\n with \n... go figure

 

 

The optimal solution is written with Dynamic Programming. I wrote a dp iterative function with memoization. DP is awesome.

 

This problem's solution values grow really fast even for small sequences. The only way to solve this for long sequences of legos is to use arbitrary-precision arithmetic (and even then it still grows too fast). It was really hard for me to find good test cases that could be represented by a signed integer (which can only represent up to 2³¹-1). You went ahead and stored it as an unsigned integer so I guess I could've gone with larger results.

time to dive into DP!

the solution does grow really fast, but my method goes to the moon even faster i think: it needs the factorial of N to compute the permutations of an N-pieces-long lego (as i write this, i begin to think that the solution may grow as a factorial too, but i won't investigate further)

[Ciccioo]

The optimal solution is written with Dynamic Programming. I wrote a dp iterative function with memoization. DP is awesome.

That's what I've been spending my time (what little of it I have) reading through. Dynamic Programming, Memoization & Fibonacci number.

i don't get it

 

i used memoization in my solution as much as i could, but i don't see how it can be used further. if i know the number of combinations that give me any piece of lenght <= N, how do i work out the combinations of a piece of lenght > N? i wanted to do that in the beginning, but i was sure that i would have double-counted a lot of solutions, so i changed path

 

also i can't see the line past which you're doing dynamic programming: i remember i looked into the definition some time ago, but just like this time i thought that it was just a strictly formal definition for a certain type of approach (wikipedia says "intelligent brute-force"). i certainly can't see how it could be an alternative to my uber-nested loops

[MrSuperb]

Not complete ... more just an idea:

(might be completely wrong)

List list;char[][] input;int n;int max;for(int r = 0; r < rows; r++){	char last = '';	for(int c = 0; c < columns ; c++){		if(input[c][r] == last && last != '.'){			n++;		} else {			list.add(n);			n=1;			last = input[c][r];		}	}}max = max(list);blocks = [1,2,3,4,6,8,10,12,16];int[] temp;for(int i = 1; i<=max;i++){	int t1=0;	for(int j=0;j<blocks.length;i++){		if(i-blocks[j]>0){			t1 += temp[i-blocks[j]];		} else {			if(i-blocks[j]==0)t1 ++;			break;		}	}	temp[i]=t1;	}result = 1;for(int num:list){	result *= temp[num];}

[wolfsinner]

i don't get it

 

i used memoization in my solution as much as i could, but i don't see how it can be used further. if i know the number of combinations that give me any piece of lenght <= N, how do i work out the combinations of a piece of lenght > N? i wanted to do that in the beginning, but i was sure that i would have double-counted a lot of solutions, so i changed path

 

also i can't see the line past which you're doing dynamic programming: i remember i looked into the definition some time ago, but just like this time i thought that it was just a strictly formal definition for a certain type of approach (wikipedia says "intelligent brute-force"). i certainly can't see how it could be an alternative to my uber-nested loops

 

Well, I can't really elaborate much on my solution because I'm a little tied up. I'll leave it here so that you can check it out. But I didn't take an equivalent path to yours when solving this, so that may be it.

[Ciccioo]

-snip-

-snip-

you guys are thinking of the same method, but i think i'll have to wait for foolproof explaination, with good big colorful drawings along with it to show how and why it works

[wolfsinner]

you guys are thinking of the same method, but i think i'll have to wait for

foolproof explaination, with good big colorful drawings along with it to show

how and why it works

 

The basis behind the solution is the following. I've prepared colorless drawings!

 

It can be easily proven that given any sequence of N equal bricks, and given an infinite set of 1x1, ..., 1xN building bricks, the solution for this sequence would be 2^n-1 for n > 0. We've only got 1x{1, 2, 3, 4, 6, 8, 10, 12, 16} bricks though. So we need to find an alternative method. Let's explore this anyway (n is the size of the sequence):

For:

• n = 0: Does not apply, but we know it's still 1 way.
• n = 1: 2⁰ = 1 way.
• n = 2: 2¹ = 2 different ways.
• n = 3: 2² = 4 different ways.
• n = 4: 2³ = 8 different ways.
• n = 5.. Well, we've come to a point where we don't have 1x5 bricks. Obviously we can't use this formula. How to solve this?

Enter Dynamic Programming. Let's assume that all of the first 5 cases ({0, 1, 2, 3, 4}) have been calculated. How do we calculate n = 5?

 

We can place a 1x1 brick at the end of the sequence and get the value for n = 4 (which we already know is 8), then a 1x2 brick at the end of the sequence and get  n = 3 (4), and continuously sum these values when possible with all bricks 1x{1, 2, 3, 4, 6, 8, 10, 12}.

This image illustrates what I'm talking about for n = 5:

 

We can generalize this as a recursive function. Let's call it W, it can be defined as:

 

So a sequence such as YYBBB would be calculated using W(2)xW(3). Now, knowing that differentWays in my code is W(n), you can look at the code and figure out what I'm doing pretty easily if you understand what I explained above.

Hope this helps!

[Ciccioo]

We can place a 1x1 brick at the end of the sequence and get the value for n = 4 (which we already know is 8), then a 1x2 brick at the end of the sequence and get  n = 3 (4), and continuously sum these values when possible with all bricks 1x{1, 2, 3, 4, 6, 8, 10, 12}.

This image illustrates what I'm talking about for n = 5:

i had to stare at the colorless drawing more time than i would like to admit

the part that left me thinking was why in the heaven would that procedure of "expanding the right brick" make any sense. i guess that was part of the demonstration for the general continous case, but it wasn't obvious for me

 

but it helped for sure, it's clear now, thank you!

[Maximation]

That's what I've been spending my time (what little of it I have) reading through. Dynamic Programming, Memoization & Fibonacci number. Could have bruit forced it but knowing you it was only natural to assume that there would be a more eloquent methodology to be found.

 

Thank you for sharing these articles, I would like to point out though that you mixed up the links for Memoization and Fibonacci number. They point to each other instead of themselves. No big deal though, I thought I would just share it with you. I am still reading up on this problem aswell, the problems certainly do not get easier

[Nuluvius]

Thank you for sharing these articles, I would like to point out though that you mixed up the links for Memoization and Fibonacci number. They point to each other instead of themselves. No big deal though, I thought I would just share it with you. I am still reading up on this problem aswell, the problems certainly do not get easier

 

Oh dear, sorry about that. I've fixed it now  :blush:

[Nuluvius]

I'm having trouble with the numbers/algebra again  :blush: I suspect I already know what the advice is going to be; that they are not really critical and that I should just clear them from my mind and try to conceptualize this another way? It's a little hard though as it looks like they are telling really important parts of the story... Sleep will help, I'm sure

 

Easter eggs were really awesome 

[wolfsinner]

I'm having trouble with the numbers/algebra again  :blush: I suspect I already know what the advice is going to be; that they are not really critical and that I should just clear them from my mind and try to conceptualize this another way? It's a little hard though as it looks like they are telling really important parts of the story... Sleep will help, I'm sure

 

Easter eggs were really awesome 

 

That's exactly my advice.

 

Are you talking about the problem itself or the DP solution I suggested? If it is the latter, then the W(n) function is nothing more than a formality. What it essentially does is start by defining a few base cases, where n is the size of the sequence (so a sequence n = 2 could be AA, BB, CC, etc):

 

w[0] = 1 //1 way to arrange for n = 0

w[1] = 1 //1 way to arrange for n = 1

 

What it does afterward is, using n = 2 as an example, it puts all of the available and possible 1xN bricks (where N is a value in {1, 2, 3, 4, 6, 8, 10, 12, 16}) at the end of the sequence, and recursively (or iteratively) reuses the previously computed values.

So placing a 1x1 brick at the end of a n = 2 sequence would leave a sequence of size 1 to its left.. We know how many possible combinations there are within this sequence of size 1 because we've already computed w[1].

We can also place a 1x2 brick at the end of the n = 2 sequence resulting in a sequence of size 0 to its left (we already computed w[0]).

We can't apply any more bricks because a 1x3 brick would result in a larger sequence than the original, so we stop there. Therefore w[2] = w[1] + w[0] = 2.

 

A few more examples:

1x1 brick at end leaves a sequence n = 2 to its left (w[2]).

1x2 brick at end leaves a sequence n = 1 (w[1]).

1x3 brick at end leaves a sequence n = 0 (w[0]).

1x4 brick at end makes the sequence larger so we stop here. 

Therefore w[3] = w[2] + w[1] + w[0] = 4.

 

1x1 brick at end leaves a sequence n = 3 to its left (w[3]).

1x2 brick at end leaves a sequence n = 2 (w[2]).

1x3 brick at end leaves a sequence n = 1 (w[1]).

1x4 brick at end leaves a sequence n = 0 (w[0]).

1x6 brick at end makes the sequence larger so we stop here.

Therefore w[4] = w[3] + w[2] + w[1] + w[0] = 8.

 

1x1 brick at end leaves a sequence n = 7 to its left (w[7]).

1x2 brick at end leaves a sequence n = 6 (w[6]).

1x3 brick at end leaves a sequence n = 5 (w[5]).

1x4 brick at end leaves a sequence n = 4 (w[4]).

1x6 brick at end leaves a sequence n = 2 (w[2]).

1x8 brick at end leaves a sequence n = 0 (w[0]).

1x10 brick at end makes the sequence larger so we stop here.

Therefore w[8] = w[7] + w[6] + w[5] + w[4] + w[2] + w[0].

 

And you repeatedly do this.

 

It is similar to something like this in code:

 

Hope that helps!

int [] w = new int[C+1];int [] bricks = {1, 2, 3, 4, 6, 8, 10, 12, 16};w[0] = 1;w[1] = 1;for(int i = 0 ; i <= C ; i++)    for(int j = 0 ; j < bricks.length && i-bricks[j] >= 0 ; j++)        w[i] += w[i-bricks[j]];//At the end of this w[] will have the results for any sequence (within the limits//of a 32-bit integer)/***A mosaic like:...AAAABBWW...XXA.....AAA...KKKKThe first line contains a sequence of 4 As, a sequence of 2 Bs, a sequence of 2 Ws, and a sequence of 2 Xs.The second line contains a sequence of 1 A, a sequence of 3 As, and a sequence of 4 Ks.The result can then be computed with w[4]*w[2]*w[2]*w[2]*w[1]*w[3]*w[4].***/

[Nuluvius]

-snip-

 

Thank you for the help, much appreciated I'll hopefully get time to work on this again tomorrow, today has been intense, haven't had any free time at all really.

[Nuluvius]

All done.

MainViewModel

MosaicWalker

Perhaps on the next one I'll swap out to a different language. I think you've done a good job with the problem gateway. When submitting it feels just like university did; all of the fear, dread and anxiety...

        private void ProcessFiles()        {            IsBusy = true;            _cs = new CancellationTokenSource();            UpdateCommands();            Task.Run(                () => Task.WaitAll(Directory.GetFiles(InputDirectory, "*.txt").Select(f => Task.Run(                    () =>                    {                                                var rawText = File.ReadAllText(f).Trim().Split(new[] { Environment.NewLine }, StringSplitOptions.None).ToList();                                                rawText.RemoveAt(0);                        var result = new Result { Index = f };                        var mosaicWalker = new MosaicWalker(rawText);                        _cs.Token.ThrowIfCancellationRequested();                        result.Total = mosaicWalker.ComputePermutations();                        AddResult(result);                    }, _cs.Token)).ToArray()), _cs.Token).ContinueWith(                        _ =>                        {                            IsBusy = false;                            UpdateCommands();                        });        }

    class MosaicWalker    {                private const char Empty = '.';        private readonly int[] _brickPool = { 1, 2, 3, 4, 6, 8, 10, 12, 16 };        private readonly int[] _permutations;        private readonly int[] _brickOccurrences;        private readonly IList<string> _grid;                private readonly int _columns;                public MosaicWalker(IList<string> grid)        {                        _grid = grid;            _columns = grid.First().Length;            _brickOccurrences = new int[_columns];            _permutations = new int[_columns + 1];        }        public int ComputePermutations()        {            Walk();            _permutations[0] = 1;            _permutations[1] = 1;            for (var i = 2; i <= _columns; i++)            {                for (var j = 0; j < _brickPool.Length && i - _brickPool[j] >= 0; j++)                {                    _permutations[i] += _permutations[i - _brickPool[j]];                }            }            var result = 1;            for (var i = 0; i < _columns; i++)            {                result *= (int)Math.Pow(_permutations[i + 1], _brickOccurrences[i]);            }            return result;        }        private void Walk()        {            foreach (var r in _grid)            {                var brickLength = 1;                for (var c = 0; c < _columns - 1; c++)                {                    var ch = r[c];                    if (ch == Empty)                    {                        continue;                    }                    if (ch == r[c + 1])                    {                        brickLength++;                    }                    else if (brickLength > 1)                    {                        CountBrick(brickLength);                        brickLength = 1;                    }                }                if (brickLength > 1)                {                    CountBrick(brickLength);                }            }                    }        private void CountBrick(int brickLength)        {            _brickOccurrences[brickLength - 1]++;        }    } 

[gauvinic]

Well, for better or worse, I have now finished all the ones that I had a clear idea how to tackle from the beginning.

Now I'm actually gonna have to take more time thinking about it than coding it, in all likelihood. This is gonna be a

great way to get back into programming before Data Structures this fall!

#include <vector>#include <string>#include <fstream>#include <iostream>#include <sstream>using namespace std;long long totalWays(int n);int main(void) {	vector<char> file;	vector<string> line;	vector<long long> repetitions;	int lines = 0;	int pos = 0;	int repeat = 0;	long long possibleWays = 1;	string temp;	string size;	string fileName = "";	cout << "Enter filename here (w/o ext): ";	cin >> fileName;	fileName += ".txt";	fstream in(fileName, fstream::in);	char ch;	while(in.get(ch) != "\n"){		if(ch != ' ') 			size += ch;		else			 break;	}	istringstream(size) >> lines;	while(in.get(ch) != "\n") {		if(ch == '\n')			break;	}	while(in.get(ch))		file.push_back(ch);	for(int i = 0; i < lines; i++) {		temp = "";		if(i > 0)			pos++;		for(int c = pos; c < file.size() && file[c] != '\n'; c++) {			temp += file[c];			pos++;		}		line.push_back(temp);	}	for(int i = 0; i < line.size(); i++) {				repeat = 1;		ch = '1';		for(int c = 0; c < line[i].size(); c++) {			if(ch != line[i][c]) {				if(repeat > 1 && ch != '.') 					repetitions.push_back(totalWays(repeat));				ch = line[i][c];				repeat = 1;			}			else 				repeat++;		}		if(repeat > 1 && ch != '.') {			repetitions.push_back(totalWays(repeat));		}	}	for(int i = 0; i < repetitions.size(); i++) 		possibleWays *= repetitions[i];	cout << possibleWays << endl;	system("pause");}long long totalWays(int n) {	int sum = 0;	int m = 0;	int arr[9] = {1, 2, 3, 4, 6, 8, 10, 12, 16};	if(n == 0)		return 1;	else if(n == 1)		return 1;	else {		while((n - arr[m]) >= 0) {			sum += totalWays(n - arr[m]);			m++;		}				return sum;	}}

[kingdorian]

I think I got the algorithm worked out (with a bit of help from the post with the nice gray pictures). Now let the coding begin, I might be able to finish it tonight.

[kingdorian]

Someone please help me D:

I had the algorithm figured out and written down but I can't figure out why it isn't working. It does not calculate the "fValues" correctly (Called W in the above example).

import java.io.BufferedReader;import java.io.FileReader;import java.io.IOException;import java.math.BigInteger;public class LEGO_Mosaics {	public static void main(String[] args) throws IOException{		String inputLocation = "C:/INPUT/t5.txt";		int[] bricks = {1, 2, 3, 4, 6, 8, 10, 12, 16};		BufferedReader input = new BufferedReader(new FileReader(inputLocation));		BigInteger possibilities = new BigInteger("1");		String[] firstLine = input.readLine().split(" ");		int R = Integer.parseInt(firstLine[0]);		int C = Integer.parseInt(firstLine[1]);		//To make sure we don't get ArrayIndexOutOfBoundExceptions		int[] fValues = new int[C+1];		//setting the values for f		fValues[0] = 1;		fValues[1] = 1;		for(int i = 0;i<= C;i++){			for(int x = 0; x<bricks.length && i-bricks[x]>= 0; x++){				fValues[i]+=fValues[i-bricks[x]];			}//			System.out.println(fValues[i]);		}		//calculating the possibility		for(int i = 0; i<R;i++){			char lastColor = 'F';			int chainLength = 1;			char[] curLine = input.readLine().toCharArray();			char curColor = curLine[0];			for(int x = 0;x<C;x++){				curColor = curLine[x];				if(Character.isLetter(curColor)){					if(curColor == lastColor){						chainLength++;					}else{						lastColor = curColor;						possibilities = possibilities.multiply(BigInteger.valueOf(fValues[chainLength]));						chainLength=1;					}				}			}			possibilities = possibilities.multiply(BigInteger.valueOf(fValues[chainLength]));		}		System.out.println(possibilities);	}}

edit: oops forgot spoilers

[Ciccioo]

		//setting the values for f		fValues[0] = 1;		fValues[1] = 1;		for(int i = 0;i<= C;i++){			for(int x = 0; x<bricks.length && i-bricks[x]>= 0; x++){				fValues[i]+=fValues[i-bricks[x]];			}//			System.out.println(fValues[i]);		}

the outer loop should start from 2, not from 0

fValues[0] is lucky, and doesn't get modified, but fValues[1] gets set to 2, and screws up all the next calculations

alternatively, you can set fValues[1] = 0 before the loop, it should work that way too

 

i couldn't test it, but that looks like the problem to me