Interesting puzzle:

Post all other topics which do not belong to any other category.
Post Reply
blazespinnaker
Long Handed Inserter
Long Handed Inserter
Posts: 85
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Interesting puzzle:

Post by blazespinnaker »

Let's say you start off on a world with no rocks, but you have 100 coal, 100 stone, 1 burner miner, and 1 furnace. Infinite ore is adjacent (coal / stone / copper / iron). Hand mining is disabled. Placement of all entities is immediate (zero time), as is feeding / grabbing of resources.. Everything is implicitly powered (don't need to power anything).

Feel free to further simplify if you run into a quandary.

What is the maximum number of miners you can build in 10 minutes?

Bonus points for algorithms / equations!

blazespinnaker
Long Handed Inserter
Long Handed Inserter
Posts: 85
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Interesting puzzle:

Post by blazespinnaker »

one approach is using genetic algorithms

GA is actually not that hard to do usually, though mapping factorio build order to code and mating them will be a bit of a task.

fitness evaluation in this case is just max # of miners.

the idea behind GA here is actually easy to explain. it's based on darwinism, a concept most people are familiar with.

a. create a random set of valid build orders as your first population
b. select the 'fittest' build orders from the population. keep a record of the most fit build order found so far
c. 'mate' many different random pairs of 'fit' build orders to generate new 'child' build orders. think of it as pairs of attractive parents having children who will be potentially attractive themselves
d. optionally mutate the new child build orders
e. using the children generated in c/d as your new population, loop back to b.

as mentioned, the fittest build orders would be the build orders with the most miners.

mating involves taking 'dna' or build sub-sequences from the parent build orders. this is done randomly. this could be a bit tricky with factorio as you want the children to be viable / valid

there are variations, but that's the basic idea.

There was a lot of hubbub about using GA with Starcraft build orders.

https://link.springer.com/article/10.10 ... 013-0263-2
http://lbrandy.com/blog/2010/11/using-g ... ld-orders/

I'm wondering if anyone has tried this with Factorio. I'm not a big fan of re-inventing wheels when it comes to coding (though it was fun with factorio blueprints :)

User avatar
DaveMcW
Smart Inserter
Smart Inserter
Posts: 3261
Joined: Tue May 13, 2014 11:06 am
Contact:

Re: Interesting puzzle:

Post by DaveMcW »

Since everything is implicitly powered, you don't need any coal. I am going to ignore the starting 100 stone, but also assume that growth is a continuous function. You can use the extra stone to accelerate the completion of buildings so their output matches the continuous function.

There are two phases:
1. Build burner mining drills and stone furnaces in the perfect ratio.
2. Upgrade all the stone furnaces into burner mining drills, giving the maximum number of burner mining drills at 10 minutes and a non-functioning factory.

Crafting time

The burner mining drill recipe has a crafting time, but the critical path goes through the last iron ore, the last iron plate, and the mining drill recipe. So we can account for the crafting time by doing nothing for the first 4 + 3.2 + 2 = 9.2 seconds of the 10 minutes.

Perfect ratio

The burner mining drill requires 9 iron ore, 9 iron plates, and 5 stone. Another stone furnace requires 5 stone. This means at a 1:1 ratio, we need (9+5+5)/0.25 = 76 seconds of mining and 9*3.2 = 28.8 seconds of smelting.

So the 1:1 ratio is wrong. We actually need a 76:28.8 ratio of burner mining drills to stone furnaces. This requires (9+5+5*(28.8/76))/0.25 = 63.6 seconds of mining and 28.8 seconds of smelting.

So the 76:28.8 ratio is wrong. We actually need a 63.6:28.8 ratio of burner mining drills to stone furnaces. This requires (9+5+5*(28.8/63.6))/0.25 = 65.1 seconds of mining and 28.8 seconds of smelting.

So the 63.6:28.8 ratio is wrong. We actually need a 65.1:28.8 ratio of burner mining drills to stone furnaces. This requires (9+5+5*(28.8/65.1))/0.25 = 64.8 seconds of mining and 28.8 seconds of smelting.

64.8:28.8 simplifies to a 9:4 ratio of burner mining drills to stone furnaces, which is our goal at the start of phase 1. By the end of phase 2, we should move all the stone miners to iron, and overbuild stone furnaces to smelt all that iron ore into plates. The ratio at the end of phase 2 is 3.2:(1/0.25) = 5:4 ratio of burner mining drills to stone furnaces.

We start at a 9:4 ratio, and end at a 5:4 ratio. This can be approximated by a 7:4 ratio of burner mining drills to stone furnaces over the entire 10 minutes.

Exponential growth

The formula for exponential growth is x = x0 * e^(k * t).

x0 = Starting population. Since we start with 1 burner mining drill and 1 stone furnace, this is (1+1)/(1+7/4) = 0.727 of our target ratio.
e = The base of the natural logarithm = 2.71828
k = The growth rate per second. At our target ratio, it takes 28.8 seconds to double the population, so the growth rate is 1/28.8 = 0.0347 per second.
t = Time. 10 minutes * 60 - 9.2 crafting time = 590.8 seconds.

So plugging everything into the formula:
x = (0.727) * (2.71828)^(0.0347 * 590.8)
x = 581962988

Remember that the units are a set of 2.75 burner mining drills and furnaces, all of which will be upgraded to burner mining drills. So we multiply x by 2.75.

The final answer is 1,600,000,000 burner mining drills.

Jap2.0
Smart Inserter
Smart Inserter
Posts: 2283
Joined: Tue Jun 20, 2017 12:02 am
Contact:

Re: Interesting puzzle:

Post by Jap2.0 »

Is hand crafting instant?

Does the prohibition on hand mining specifically refer to resources or everything?

Is it correct to assume that "miners" specifically refers to burner miners, and as a result there is no benefit from any production of coal (due to implicit power) and potentially copper (as with infinite space and insertion/extraction of resources the electric system is useless and the only research that could potentially be of use is assemblers (dependent on question 1 above))?
There are 10 types of people: those who get this joke and those who don't.

MassiveDynamic
Fast Inserter
Fast Inserter
Posts: 213
Joined: Sun Sep 16, 2018 10:44 pm
Contact:

Re: Interesting puzzle:

Post by MassiveDynamic »

“I am not a smart man”
- Forrest Gump
- me

blazespinnaker
Long Handed Inserter
Long Handed Inserter
Posts: 85
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Interesting puzzle:

Post by blazespinnaker »

here's the datastructure I'm going to use. i like it because it doesn't make assumptions about what has already been built, so I can pull the DNA from parents. there are some rules I'll need to enforce, but I don't think it should be that hard. i think this can be scaled up to larger builds with longer time between build actions. it does assume you'd spend more time on specific tasks though and certain micro/tactical things can't change the outcome that much.

note that it doesn't account for walking time as Nefrums pointed out. that is a serious issue I have some ideas on how to resolve, but the solution is a bit specific to the assumptions made about the map and where entities are placed.

let me know what you think

Let's say you start off on a world with no rocks, but you have 100 coal, 100 stone, 1 burner miner, and 1 furnace. Infinite ore is adjacent (coal / stone / copper / iron). Hand mining is disabled. Placement of all entities is immediate (zero time), as is feeding / grabbing of resources.. Everything is implicitly powered (don't need to power anything).

every X seconds. X = 60 / APM (actions per minute) of assumed player. . r X = 1s means that player can do something different every 1s. will craft only whole objects, not partial, so if whole object can not be completed in 10s, then it won't start. eg, crafting an assembler requires gears, plates, GC.


terminology

actions=['c', 'p', 'fz', 'fh', 'ff', 'g']
==
c = crafting
p = placing
fz = feeding with z drop
fh = feeding half ctrl right click
ff = feeding full ctrl left click
g = grabbing (assume left click)


entities=['im', 'if', 'imfp', 'sm', cm', 'cf', 'cmfp', 'gasm', fasm', 'masm', 'casm', 'asasm']
==

im = iron miner
if = iron furnace
imfp = iron miner furnace pair
sm = stone miner (ignore chests)
cm = copper miner
cf = copper furnace
cmfp = copper miner furnace pair
gasm = gear assembler
gsasm = green circuit assembler
fasm = furnace assembler
masm = miner assembler
casm = coal assembler
asasm = assembler assembler

resources=['g', 'gs', 'coi', 'coa', 'i', 'cop', 's']
==
g = gears
gs = green circuits
coi = coil

coa = coal
i = iron
cop = copper
s = stone

amount for crafting / feeding
==
amount will be random number generated % amount of available resources. rng will be multiples of 25% (25,50,75,100%). use available resources
eg, for green circuits, use lower of iron and copper. eg, if it's 50%, and there are 1000 iron but only 3 copper, than only 1 gs can be created. placing assumes all, but rate limited

eg build steps:
(c, im, 50) means craft iron miners using 50% of available resources.
(c, im, c) means feeding with zdrop iron miners coal
(ff, gasm, i) means feeding with left click iron into gear assemblers

a build order is just a list of build steps [(c, im, 50) , (c, im, c) , (ff, gasm, i) ..]


rate_limiting
==
there is a rate limit to all activities.
crafting = CRLPS (default 5 per second)
placing = PRLPS (default 5 entities per second)
feeding = FRLPS (default 5 entities per second)
grabbing = GRLPS (default 5 entities per second)


rules
==

Certain things can't occur in a build order until other things have occured, even during mating. if invalid, another random build order item is generated or dna is selected
- c_*asm can't occur until ASM_IMFPS miners are placed and ASM_CMFPS copper miner furnacer pairs are placed.
- feeds can't occur until the resource has been crafted and grabbed if crafted in a assembler
- you can't have more than 8 thousand resources in your inventory at any time

Certain things can't be placed,
- cm, im, *f, g, gs, i, coi, coa, cop, s
better might be what can be placed
- *mfp, *asm, sm
Last edited by blazespinnaker on Sun Nov 22, 2020 3:14 am, edited 3 times in total.

blazespinnaker
Long Handed Inserter
Long Handed Inserter
Posts: 85
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Interesting puzzle:

Post by blazespinnaker »

DaveMcW wrote:
Sat Nov 21, 2020 11:54 pm

The final answer is 1,600,000,000 burner mining drills.
Uhm, I think you simplified too much :)

but the answer might be ballpark right. the problem clearly is the instantaneous feeding / placing / grabbing resources which is not realistic. maybe also you assumed hand crafting was instant, which maybe is the over simplification

walking time is also an issue of course, but rather complicated to account for
Last edited by blazespinnaker on Sun Nov 22, 2020 2:34 am, edited 1 time in total.

blazespinnaker
Long Handed Inserter
Long Handed Inserter
Posts: 85
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Interesting puzzle:

Post by blazespinnaker »

Jap2.0 wrote:
Sun Nov 22, 2020 12:30 am
Is hand crafting instant?

Does the prohibition on hand mining specifically refer to resources or everything?

Is it correct to assume that "miners" specifically refers to burner miners, and as a result there is no benefit from any production of coal (due to implicit power) and potentially copper (as with infinite space and insertion/extraction of resources the electric system is useless and the only research that could potentially be of use is assemblers (dependent on question 1 above))?
I re-added some complexities back in for my answer. so hand crafting is not instant anymore, at least in my approach. everything except walking is rate limited.

Thinking about it some more, while Dave didn't account for assemblers and I guess he made hand crafting instant, I think if feeding/grabbing/placing is also instant, the number is still going to be insanely large if not quite what he arrived at. ie, if you can instantaneously place down assemblers and there are no limits to ore, then you're going to get a doubling. maybe not 28.8 seconds, but still some constant that will grow the function very quickly.

rate limiting feeding feeding,

and yes, i'm thinking burner miners, but really the question is just a instantiation of a particular archetype. it's the over all optimization problem that i've been thinking about for awhile and had hoped someone had already tackled it.
Last edited by blazespinnaker on Sun Nov 22, 2020 3:03 am, edited 1 time in total.

User avatar
DaveMcW
Smart Inserter
Smart Inserter
Posts: 3261
Joined: Tue May 13, 2014 11:06 am
Contact:

Re: Interesting puzzle:

Post by DaveMcW »

The basic concept is still exponential growth. The details are about how long it takes for the player (or CPU, or size of the universe) to become the bottleneck.

blazespinnaker
Long Handed Inserter
Long Handed Inserter
Posts: 85
Joined: Wed Sep 16, 2020 12:45 pm
Contact:

Re: Interesting puzzle:

Post by blazespinnaker »

Yeah with instant assembler placement and hand feeding/grabbing (without limit), agreed, it'd be exponential.

however, those are clearly not useful simplifications as I've discovered, and I'm sure everyone else already arrived at that point a long time ago.

I think a logistics curve makes more sense for what it actually will end up loooking like.
logisticgrowth.png
logisticgrowth.png (15.05 KiB) Viewed 292 times
of course, recursive blueprints are an entirely different thing :)

Post Reply

Return to “General discussion”

Who is online

Users browsing this forum: bormand, tobsn