[Spoilers] Ichabod's spoiler thread

[thestick]

Ah, this takes me back to school... disclaimer, I don't really know anything about this. I just took the basic data structures course back in college. I think AutomatedTeller works in IT?

I have a stupid idea, using the hint that this is in the 'queue' section. Essentially this is a breadth first search. If we picture the various paths as branches of a tree, we start with the initial number Q at the root. We essentially search every possible 'path' down the tree, and terminate when we hit 1.

Initialize the queue as follows:
Back -1 Q Front

-1 is a marker that we've gone down one level in the tree.

Let i = number of steps = 1.

while (true):
   x = queue.remove()
      if (x == 1):
         return i
      if (x == -1):
         i++
        queue.add(-1)
      else:
         queue.add(x - 1)
         for (j from 2 to sqrt(x)):
            if (x % j == 0):
               queue.add(x / j)

Now time to see if this works...

[thestick]

Well, it works, but it guzzles memory and causes time out errors. There's probably a better way to find the factors... but I don't know enough math to figure it out.

I can try to explain this if you'd like.

[Ichabod]

Just to confirm that I choose Brazil. Would you guys be interested in a Civ overview?

I'll have more comments about the coding question later. Hopefully some of the mathematicians around can help us with the factoring problem.

[El Grillo]

Sure, a civ overview would be appreciated! I started a game of civ6 with a friend over the weekend and didn’t know what I was doing so I tried to remember what I had read in games here and went for Russia with Lavras into Choral Music and Stewardship with a Monumentality Golden Age and that worked really nicely even though I fumbled all the details, but I’d like to learn more and study other civ openings.

[Ichabod]

Interesting question Ichabod, let me take a stab at it.

The fact that we can only work through factorization makes me think that a greedy approach that tries to maximize each step down won't work, since it's easy to fall into traps. Also, these kinds of problems typically don't ask you to load in big dictionaries. The problem is categorized under queues in the linked website, but have you tried a list-based approach to see if that might be fast enough?

Ah, this takes me back to school... disclaimer, I don't really know anything about this. I just took the basic data structures course back in college. I think AutomatedTeller works in IT?

I have a stupid idea, using the hint that this is in the 'queue' section. Essentially this is a breadth first search. If we picture the various paths as branches of a tree, we start with the initial number Q at the root. We essentially search every possible 'path' down the tree, and terminate when we hit 1.

Initialize the queue as follows:
Back -1 Q Front

-1 is a marker that we've gone down one level in the tree.

Let i = number of steps = 1.

while (true):
   x = queue.remove()
      if (x == 1):
         return i
      if (x == -1):
         i++
        queue.add(-1)
      else:
         queue.add(x - 1)
         for (j from 2 to sqrt(x)):
            if (x % j == 0):
               queue.add(x / j)

Now time to see if this works...

I think you two were pointing in a similar direction, that my take on calculating Q(X) for every number until the target was not the best way to do it. That's why discussion is so nice. I spent a long time looking at this problem, and it never occurred to me that I could see this problem as a tree and use breadth first search in it. I’m confident that this solution is way better than my initial one. I’ll try implementing it soon, using a queue (not that there is much to change in thestick’s solution). 

So, I decided to focus on the second part of the problem, the part about finding the factors.

First, I wanted an algorithm to find the prime factorization on a number. I could start with a big list of prime numbers, which would make it trivial. But I wanted to make things harder (because why not).

So, here’s the algorithm. You take number N that you want to factor. You try “integer-dividing” it by 2 (the first prime is given). If you can do it, you add 2 to the factors list, divide N by 2, and try again. If you can’t, you add 1 to 2 and start the process again (so, this time, instead of trying to ivide by 2, you go with 3). This process ends when N reaches 1.

Perhaps the code will make things clearer:

Code:

def primeFactorization(target_number):

   prime = 2
   factors = []

   while True:
       
       while (target_number % prime == 0):
           factors += [prime]
           target_number = target_number / prime

       if target_number == 1:
           return factors

       prime += 1  

You’ll have to try every integer at a time, because you don’t know which ones are primes. But the algorithm doesn’t give false positives (it doesn’t add non-primes to the list).

After that, I started thinking about how to find the multiples of an integer, using the prime factorization of it. Here’s what I came up with:

You start with two lists, the prime factors list and an empty multiples list. You iterate over the prime factors list. For each of them, you multiply it by every integer in the multiples list and add this product to the multiples list, if it isn’t already on it. Finally, you add the prime factor to the multiples, if it isn’t already there.

Let’s try it with 30, which can be factored in [2, 3, 5].

First loop (prime = 2):

primes = [2, 3, 5] , multiples = []

No multiplications needed.

You add 2 to the list

Second loop (prime = 3):

primes = [2, 3, 5] , multiples = [2]

You add 6 to the list (2 . 3)

You add 3 to the list

Third loop (prime = 5):

primes = [2, 3, 5] , multiples = [2, 6, 3]

You add 10 to the list (2 . 5)

You add 30 to the list (6 . 5)

You add 15 to the list (3 . 5)

You add 5 to the list

Final multiple list = [2, 6, 3, 10, 30, 15, 5]

As far as I can tell, these are all the integer multiples of 30 (the only one missing is 1, which we don’t want anyway).

Here’s the code, in my terrible Python skills:

Code:

def multiples(prime_factors):

   all_multiples = []

   for prime_factor in prime_factors:
       
       iterator = len(all_multiples)
       
       for multiple in all_multiples[:iterator]:
           if prime_factor * multiple not in all_multiples:
               all_multiples += [prime_factor * multiple]

       if prime_factor not in all_multiples:
           all_multiples += [prime_factor]

   return sorted(all_multiples)

I think this algorithm looks promising enough for what we need, so I’ll try combining it with thestick’s solution when I have a bit more time. I haven’t tried to calculate the complexity of all of this, but I’m positive it’s better than my previous attempts (going through all the integers between 2 and the square root of N). The next step is to limit the multiples list to the ones I need (i.e. the highest ones, excluding N itself).

I’m sure there are better ways of doing all of this, but I find the exploring of options one of the coolest parts of these challenges. It’s really nice when you see a better solution to a problem you already solved, I think it makes you learn way more than just looking at the solution.

[Ichabod]

Sure, a civ overview would be appreciated! I started a game of civ6 with a friend over the weekend and didn’t know what I was doing so I tried to remember what I had read in games here and went for Russia with Lavras into Choral Music and Stewardship with a Monumentality Golden Age and that worked really nicely even though I fumbled all the details, but I’d like to learn more and study other civ openings.

I see that you brought the big guns early against your friend.  Lavras (and associated district discounts) + Choral Music is incredible. Monumentality alongside it, going into Cossacks, awesome. 

I don't think Brazil reaches this level of power, but I'll see what I can do. I think Brazil benefited from some changes in the expansions, so they are probably better than before.

[Chevalier Mal Fet]

I'm honestly surprised Brazil made the list of "garbage" civs, I think it's quite strong. It's featured in lots of games and the Rainforest appeal makes it pretty powerful. You lose out on chopping rainforest, but chopping was nerfed in GS so no worries!

[Ichabod]

I'm honestly surprised Brazil made the list of "garbage" civs, I think it's quite strong. It's featured in lots of games and the Rainforest appeal makes it pretty powerful. You lose out on chopping rainforest, but chopping was nerfed in GS so no worries!

I agree, Brazil is not bad, it's probably pretty good. I kinda feel bad now that my vote for Brazil wasn't that honest. In another topic, waht exactly were the chopping nerfs in GS? There was an overflow nerf as well (or are these the same thing), right? I know some things were changed in those departments, but I can't remember exactly and Civ 6 documentation is not the best. I have a hard time finding things online, let alone in the game.

[Ichabod]

Brazil is led by Pedro II, the second and last emperor from Brazil. Even though there are no living person today that lived during Brazil’s Monarchy years, a lot of people here claim that “those were the days” and “we could safely walk the streets during that time”. Some of those also argue that the time of the military dictatorship was better than today, so I guess we are living in pretty bad times (well, I can’t really argue with that). The current political situation in Brazil is so Kafkian that if you visit a rally in favor of president Bolsonaro you’ll see flags asking for the return of the Monarchy, of the military dictatorship and claiming that the Bolsonaro presidency is the most democratic period of Brazil’s history, all at the same time. How does this work? I don’t know, you tell me.

Despite all that, Firaxis was nice enough to give Brazil bonuses in the game, rather than penalties, as one could argue would be more appropriate. Let’s take a look at those bonuses.

The first bonus is Amazon, the civilization ability. As usual, foreigners think Brazil is just a big jungle and base the Civ ability on this preposterous claim… Well, I would complain about that, if it wasn’t for the fact that I have seen a monkey in the trees while taking a walk in the street just yesterday. By the way, I live as far from the Amazon as possible. Perhaps there is some truth to this jungle thing after all.

The ability reads: Rainforest tiles provide a +1 adjacency bonus for Campus, Commercial Hub, Holy Site, and Theater Square districts, and grant +1 Appeal to adjacent tiles, instead of the usual -1.

I would argue that adjacency bonuses are more important in GS than they were in vanilla, so the bonus is better now than before. Before, the policy cards that doubled the bonuses from district buildings far surpassed the ones that doubled adjacency bonuses, which used to make adjacency bonuses kind of meaningless after the early game. Now, the district buildings cards are tied to adjacency as well (50% of the bonus only work in districts with good adjacency), so it keeps its importance for longer. Some of the Golden Age bonuses also have bonuses tied to adjacency, so that’s also a plus. So, I think this bonus is no longer early game focused like it was in vanilla, but it keeps being useful as you get more advanced policy cards.

As a plus, jungles can get a lumbermill improvement in RS, so there's less of a penalty in leaving those tiles unchopped for the adjacency bonus. Chops are also not as good as they used to be.

The +1 adjacency is pretty good, especially for districts that have hard adjacency requirements, like the Theater Square. Notice that it doesn’t affect Industrial Zones and Harbors, though.

The appeal bonus also has its benefits, but I wonder how much they apply to MP games. Appeal is a very important factor in culture victories, which I don’t seen happening in MP. It gives bonuses to Neighborhood districts, which we also don’t see a lot in MP. Finally, you can use it to get a ton of faith with the Earth Goddess pantheon (which gives +2 in tiles with breathtaking appeal). I never did this in a test game, so I don’t know how good it can be. One problem is that the bonus only applies to rainforests inside Brazilian borders, while the rainforest tiles outsides still give the -1 appeal. For this reason, you are probably not getting that much high appeal tiles early on, when the faith boost would be more relevant. Well, it’s map dependent, so we need to wait to see if it will be relevant or not. Is there another Appeal bonus that I’m not seeing?



The leader ability is Magnanimous, which reads: Recruiting or patronizing a Great Person refunds 20% of their point cost. 

Is this good for MP? I can’t really tell before testing it. You get a benefit from it when you get the second GP of a certain type, before that, it didn’t help you at all. How likely are you to get 2 GP of a certain type? It can happen, but I guess it depends on how long the game lasts. I think it’ll be good if I’m already in a strong position, while it won’t help me getting to such a position. Those bonuses usually aren’t the best for MP, but it is what it is.

Uniques will be in a different post.

[Banzailizard]

I'm honestly surprised Brazil made the list of "garbage" civs, I think it's quite strong. It's featured in lots of games and the Rainforest appeal makes it pretty powerful. You lose out on chopping rainforest, but chopping was nerfed in GS so no worries!

I agree, Brazil is not bad, it's probably pretty good. I kinda feel bad now that my vote for Brazil wasn't that honest. In another topic, waht exactly were the chopping nerfs in GS? There was an overflow nerf as well (or are these the same thing), right? I know some things were changed in those departments, but I can't remember exactly and Civ 6 documentation is not the best. I have a hard time finding things online, let alone in the game.

They changed how overflow works.  It used to be you would say build a wall to within 1 turn of completion then slot in Limes (100% wall production) chop and the overflow would still be boosted 100%.  Not so now. Chopping is still good, but its no longer a necessity to juggle builds in the same way.  I think there is some weirdness about loosing the overflow entirely if you are partially done with the build.  I would check that out.  Production is the bottleneck in Civ6 and wasting chops is still bad.

Is this good for MP? I can’t really tell before testing it. You get a benefit from it when you get the second GP of a certain type, before that, it didn’t help you at all. How likely are you to get 2 GP of a certain type? It can happen, but I guess it depends on how long the game lasts. I think it’ll be good if I’m already in a strong position, while it won’t help me getting to such a position. Those bonuses usually aren’t the best for MP, but it is what it is.

I would say its good but not great in MP.  You can absolutely get more than one of a type of GP in a MP game.  Scientists are usually the hardest to get, you might grab a few per game.  Everyone builds campuses so everyone generates points.  Beyond that you can plan around what districts other people might build and try to either win a one on one race or start accruing points for GP no one else is.  I would say maybe great merchants might be a good choice given the adjacency bonus.  Upgrade costs scale now with techs so gold is also more important.