Page 3 of 3 FirstFirst 123
Results 21 to 22 of 22

Thread: How many different base layouts are there?

  1. #21
    Millennial Club megacrab's Avatar
    Join Date
    Mar 2017
    Evergreen Terrace
    I'm working on my own estimate. As I said, it's a very hard problem. Similar to bin packing or square tiling, some of the hardest problems in computing.

    For now I'll just pick apart Ravioli's estimate. It's a fine place to start, but has some problems.

    Quote Originally Posted by Raviolistan View Post
    There are about 100 structures (including mines). Assume each one is a 3x3 square. There are about 200 3x3 squares on a base.

    About 100 is pretty darn close. There are 65 non-proto buildings and 34 mines, for a total of 99 buildings. Not counting protos.

    Assume each is 3x3? Ok for the 65 real buildings - most are 3x3, a few are bigger. But the 34 mines? Easier to deal with those as 1x1. Assuming mines are 3x3 means you're vastly undercounting the number of possibilities.

    200 3x3 squares? You must mean non-overlapping. If we take a base to be a rectangle of 44 tiles by 45 (it's largest dimensions) then there are 210 non-overlapping sets of 3x3. Again, pretty darn close.

    However buildings can be placed on any tile, not just within your "lanes" of 3x3. I.e. you can move a cannon over 1 tile or 2 tiles, not just 3. There are actually (44-2)*(45-2) = 1806 different 3x3 squares on a 44x45 grid. In other words, there are 1806 unique positions for a cannon on a blank base - much more than the 200 you allow.

    Using all 1806 possibilities has a problem with building collisions whereas your 200 non-overlapping approach doesn't. But your non-overlapping approach severely undercounts the number of possibilities.

    Quote Originally Posted by Raviolistan View Post
    There are 200! permutations of the squares. The order of the 100 empty squares doesn't matter, so divide by 100!. Likewise, the order of structures of the same type doesn't matter, so for each structure with n instances (n > 1), divide by n!.

    Ok now we get to the fun stuff. Your math is quite frankly all wrong. I say that with affection because combinatorics is very very hard. It took a lot of thought to understand how it and why it was wrong.

    First, 200! counts all the ways to arrange your 200 non-overlapping squares. But that's just the base grid. We're not arranging those squares; we're putting buildings into those squares. 200! isn't counting anything useful.

    Likewise, dividing by 100! isn't doing anything either. The empty squares are not being chosen or arranged; they're being left alone. Counting the possible ways to arrange 100 empty squares is meaningless.

    Now the dividing by n! for structures makes some sense. The arrangement of buildings is a permutation with repetition. The formula with that is (number of items)! divided by (number of repeating items)!. You had good intuition on that one.

    Quote Originally Posted by Raviolistan View Post
    There are 5 boom cannons, 6 cannons, 3 rocket launchers, 2 shock launchers, 7 sniper towers, 4 flamethrowers, 4 mortars, 5 machine guns, 4 gold storages, 3 iron storages, 3 stone storages, 3 wood storages, 6 residences, 24 mines, 7 boom mines, and 3 shock mines.

    That gives us 200! / (100! * 24! * 7! * 7! * 6! * 6! * 5! * 5! * 4! * 4! * 4! * 3! * 3! * 3! * 3! * 3! * 2!) = 3.3*10^167

    That's wrong per the reasons above. What you should really be doing (under your simplified approach) is this: you have 200 non-overlapping 3x3 squares. You have 100 buildings. You're putting those 100 buildings into those 200 squares. How many ways can you do that? (200 choose 100) = 200! / (100! 100!) = 9.1 x 10^58.

    But that just counts position of buildings, not their layout. That's how many different ways you can choose 100 of your squares to put buildings in. For any given choice, there are still many ways to arrange those buildings. For instance, you could a cannon in the first spot, or a sniper, or a mortar, etc.

    For a given set of 100 building positions, how many ways can you arrange the 100 buildings within them? That's where the permutations with repetitions formula comes in. We have 100 buildings to arrange with repeats for certain types of buildings. That gives us 100! / (24! * 7! * 7! * 6! * 6! * 5! * 5! * 4! * 4! * 4! * 3! * 3! * 3! * 3! * 3! * 2!) = 3.7 * 10^108 possible ways to arrange the buildings after fixing which spots to put buildings in.

    Multiplying those two results - number of positions * number of layouts for each position - gives 3.3*10^167. Amazingly, the same as your original answer!

    Why is that? This is a case of your mistakes canceling out. Lucky 100 is half of 200. In the (200 choose 100) formula, the calculation is n! / r! (n-r)!. When n=200 and r=100, r is half of n so n-r also equals 100. That gives us two factors of 100! in the denominator. Then as luck would have it there's a 100! in the numerator of the other term. So two of the 100! terms cancelled out, leaving one in the denominator. Which ends up the same as your calculation. Even if you chose those numbers for the wrong reasons.

    As I said, this vastly underestimates the real answer. Here's a minor improvement using your method.

    Even if you use your 200 grid for the larger 3x3 buildings, there's no reason to do that with 1x1 mines. You should do two different calculations, one for mines and one for other buildings, then combine them:

    Buildings: (200 choose 65) building positions * 65! / (list of building repetitions)! = 3.5 e 65 * 6.1 e 69 = 2.2 e 123
    Mines: 1800 tiles - 65 * 9 used = 1215 open tiles
    (1215 choose 34) * 34! / (24! 7! 3!) = 1.6 e 66 * 1.6 e 10 = 2.5 e 76

    building choices * mine choices = 2.2 e 123 * 2.5 e 76 = 5.5 * 10^199

    Quote Originally Posted by Raviolistan View Post
    Obviously there's a lot I could've gotten wrong there, but this is about the number of atoms in the universe, squared.

    Agree. Even if your calculation is off by dozens of orders of magnitude, we can agree the result is HUGE. More than the number of atoms times the number of seconds the universe has existed.

    I'm working on my own estimate using a different approach. It's quite a long post so I'll add it later. Thanks for sharing this thread.
    Hasty Crab US #16 - Tribal Crab US #40
    main (retired) maxed - VP 1250 - 3 GB, 4 TD, 3 TH
    alt (crab smasher) maxed - VP 1000 - 3 GB, 3 PSC, 2 TD, 2 TH

  2. #22
    Centennial Club PDBismarck's Avatar
    Join Date
    Apr 2018
    I still say the answer is Pi.

    All kidding aside, there's been some impressive work done on this problem thus far in this thread. I like it.
    Bismarck - 1347 VP - Angry Volcano - 4 TD - 1 TH - 5 GBE // Trophies: 3 Diamond
    Rank: #20 in Canada - #9 on Tribal Crab - #43 on Hasty Crab

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts