working on:

Images are sometimes not shown due to bandwidth/network limitations. Refreshing the page usually helps.

You are currently reading a thread in /sci/ - Science & Math

You are currently reading a thread in /sci/ - Science & Math

Thread images: 1

working on:

projecteuler.net/problem=544

Let F(r,c,n) be the number of ways to color a rectangular grid with r rows and c columns using at most n colors such that no two adjacent cells share the same color.

found a generalized formula for F(2, 2, n)

looking to extend this to F(r, c, n)

I have:

((n-1)*(n-1)*(n-2)+(n-1))*n

for 2x2 grids

because 1st cell has n choices, 2 cells adjacent will have n-1 choices followed by the last corner of (2n-3)

applying my logic to the 4*3 grid, i get something like 6*5^8*4*4*3 which is off by about 10 million.

any guidance?

>>

>>7813073

I have done a similar algorithm in the past.

I assigned a color for each digit (0,1,2,...,9)

(so it worked for up to 10 colors ...)

Tested all permutations (some optimization allowed to only test reasonable permutations).

In the case of a 2x2 matrix and 3 colors it worked like this

0000

Test: "fail, add one in base 3"

0001

Test "fail, add one in base 3"

0002

Test "fail, add one in base 3"

0010

Test "fail, add one in base 3"

....

2222

Test "fail"

end

I realized it would be much better if my test function would actually tell the algorithm what digit to increment.

0000

Test: "fail, at digit #2"

0100

Test "fail at digit #3"

0110

Test "win, increment count"

0111

...

There's probably better ways to do this (either with proper combinatorics or with a most efficient algorithm) but I was looking for a programming challenge for "beginners" at the time ...

Thread images: 1

Thread DB ID: 470378

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.

This is a 4chan archive - all of the shown content originated from that site. This means that 4Archive shows their content, archived. If you need information for a Poster - contact them.

If a post contains personal/copyrighted/illegal content, then use the post's