Way to make this faster?

[czardas]

I would love to work on an ArrayPermuteUnique() function because I think i's very interesting. Unfortunately I have a lot on my plate right now, so I wouldn't be able to give it enough attention. I would like to know how much it is possible to circumvent memory limitations by removing duplicates as you go along. I think it's a worthy challenge for anyone with time on their hands. It's the only missing element from the code I

Edited February 28, 2012 by czardas

[kylomas]

jb09,

"a1,b1,c1,a2,b2,c2,a3,b3,c3" is ok

"b1,a1,b2,c1,a2,a3,c2,b3,c3" is ok

"b1,c1,a2,c2,c3,b3,a1,b2,a3" is not ok

Why is "c1" ok in line #2???

kylomas

[kylomas]

@czardas,

I clearly do not understand the problem yet. Can you answer my question from post #22?

kylomas

[czardas]

@czardas,

I clearly do not understand the problem yet. Can you answer my question from post #22?

It is the first occurence of 'c' in the string. See this

[jb09]

jb09,

Why is "c1" ok in line #2???

kylomas

"c1" is ok because it is the first occurence of the letter "c". I'm not sure how else to explain the "rules" as to what I'm looking for.

@czardas,

I'll give it a try on making the arraypermuteunique(), but quite frankly I feel like I'm finally getting in over my head. I'll try to learn the SQLite stuff first. Much apprecitiated on the help and guidance.

Edit:

An idea just hit me. To use arraypermute we have to stay under 16 million elements, which would be 10 elements being entered into the function have some 3 million elements. Using your code, then finds all duplicates and removes the extras. Now, for my purposes, instead of starting with 10 I start with 9, three of each letter. This would give me only the possible combinations of a1-a3, b1-b3, and c1-c3, just without the numbers added. Now, lets call this array "Permuted1". What if......

We don't had the numbers to this array....instead first use arraypermute again, only with 7 elements from Permuted1? Of course doing so a few times if and probably are more than 7 elements in Permuted1. (I'm currently running this setup of 9 original elements to find out, as I write this arrayunique is running removing duplicates. ) Now lets call the array, from our second arraypermute series into one, "Permuted2". And call the function arrayunique on Permuted2. Last but not least add the numbers to Permuted2. Would this be quicker? Plus, considering the final information I'm after from this list of combinations, I know I won't be worried about having more than three of the same letter in a row. It could be possible that having only 4 a's in a row the very first thing in the combination which would be my final answer for the script after this. But I doubt it. If so it should be easy to get the combinations with 4 a's first. So in the end I'm also eliminating some data which I won't need.

Comments?

I should be fine coding this setup, just wanting input before I do.

Edited February 29, 2012 by jb09

[czardas]

It's a pleasure for me to try to figure things out. This task is a bit confusing and I started out trying to solve it the wrong way: so I have learned by my attempts. I can envisage there being lots of potential use for this type of processing. It's an interesting queueing system: in fact it's a mulltiple integrated queue (there's probably a technical term for it).

[kylomas]

jb09, czardas,

This has turned into one of those problems where, once you see it you go, "holy shit, of course!!". However, the light has not come on yet.

Are you generating a list or working with a pre-existing list?

The list seems to be the range of a1 - d20, is this correct?

Based on previous responses it seems like you want an ordered list (not premutation) of unique values ordered by numeric within alpha? Is this correct? If so, how many symbols pre element (line)?

I'm probably so far out in left field that I'm wasting your time, if so, just tell me to "fuck off" and I'll just watch for an eventual solution.

kylomas

[czardas]

kylomas if the system only has the following four values - a1, a2, b1, b2 - then there are exactly six legitimate arrangements:

a1,a2,b1,b2

a1,b1,a2,b2

a1,b1,b2,a2

b1,a1,a2,b2

b1,a1,b2,a2

b1,b2,a1,a2

In all the above patterns a1 always preceeds a2 (and b1 always preceeds b2). Is that any clearer?

[jb09]

kylomas, I think you are starting to understand what I'm after.

I want to be clear on what you mean be "a1-d20". I'm after my list to have "a1-a20","b1-b20", and "c1-20". Not using any letter besides "a", "b", and "c". Also I'm after creating a list, no pre-existing for this problem.

Try running the code czardas posted on the first page, look at final result don't mind first two arraydisplays. Should give you an idea of what I want, only his is showing "a1-a2", "b1-b2", and "c1-c2".

You two posted while I was writing my edit. lol

[kylomas]

jb09, czardas,

Thanks, you are both very patient.

Spitball suggestion: Turn the alpha into a number then add the number prefix to it to produce a unique numeric equivalent. Create a 2X array of ordinal premutations and transpose back to alpha's for output.

Ohhh...it hurt my head to even type that so, going to have a beer and watch a basketball game.

Good Luck,

kylomas

[jb09]

Can someone translate that to English?

[czardas]

An idea just hit me. To use arraypermute we have to stay under 16 million elements, which would be 10 elements being entered into the function have some 3 million elements. Using your code, then finds all duplicates and removes the extras. Now, for my purposes, instead of starting with 10 I start with 9, three of each letter. This would give me only the possible combinations of a1-a3, b1-b3, and c1-c3, just without the numbers added. Now, lets call this array "Permuted1". What if......

We don't had the numbers to this array....instead first use arraypermute again, only with 7 elements from Permuted1? Of course doing so a few times if and probably are more than 7 elements in Permuted1. (I'm currently running this setup of 9 original elements to find out, as I write this arrayunique is running removing duplicates. ) Now lets call the array, from our second arraypermute series into one, "Permuted2". And call the function arrayunique on Permuted2. Last but not least add the numbers to Permuted2. Would this be quicker? Plus, considering the final information I'm after from this list of combinations, I know I won't be worried about having more than three of the same letter in a row. It could be possible that having only 4 a's in a row the very first thing in the combination which would be my final answer for the script after this. But I doubt it. If so it should be easy to get the combinations with 4 a's first. So in the end I'm also eliminating some data which I won't need.

Comments?

I should be fine coding this setup, just wanting input before I do.

I'm not sure I understand this. I think you will still miss many combinations. You should try things like this out on smaller sets first, and try to proove you have suceeded in creating all the permutations on a small scale. Scale it up and run further checks to make sure your results are consistant. Then go for the big one. However I'm not sure if you will have enough space on your hard drive. Maybe you could compress the results. (JOKE)

Why does it need to be so big?

Edit

BTW, since you are using single letters for the permutations, during this process you could discard the reverse patterns. They can be created on the fly when needed (watch out for palindromes). It is also unecessary to add the numbers since they can also be added on the fly as shown in my code. The only thing you need are the unique permutations. You should probably get rid of the delimeters too.

Edited February 29, 2012 by czardas

[jb09]

OK. Ill first check my idea on a small amount of data.

As for why so big, I'm wanting to run a simulation as to the best build order for a game. No, this is not to automate the game where I'm not playing but a bot is. Only I will be interacting with the game, which is called "ogame". In about 10 hours I will be back home and have access to a computer, where it is much easier to show the links to the game along with links to provided formulas for the simulation. Currently at work writing this from phone.

[czardas]

Well since we have only been discussing mathematical permutations, and there has been no mention of game play automation, I feel a bit on the fence right now. If this is to give you an advantage over other players in a multiplayer enviroment, I won't help any further. From a programming perspective, I find the challenge to solve the problems we have discussed intriguing, but I won't ignore the policies of the forum.

Edited February 29, 2012 by czardas

[jb09]

OK, yes this is for a game. But not in any shape, form, or fashion to control it. http://ogame.us, is the game which has a forum with lots of data about the game. Such as formulas used for the game, for those who make programs about the game. http://board.ogame.org/board684-ogame-org/board82-tools-scripts-and-sims/ or http://board.ogame.us/board178-ogame-us/board29-help-questions/board49-tools-scripts-and-sims/ to see many tools, scripts, and simulators used. The formulas are somewhat scattered, but have managed to find everything I'd need for my purposes on two topics. http://board.ogame.org/board703-miscellaneous/board156-archive-version-2-0/board705-help-questions-archive/board631-faq-s-guides/576831-formula-thread-v3/ and http://board.ogame.org/board703-miscellaneous/board156-archive-version-2-0/board705-help-questions-archive/board631-faq-s-guides/89308-all-buildings-researches-fleets-and-defences/.

As far as the code I've been working on the simulate the building process and find the best build order is not complete. But this is what I have so far.

expandcollapse popup

; testing to see what build is best
;cost per lvl formula - INT((Base Cost)*(Cost Increase Factor)^(lvl-1))
;cost cumulative formula - INT((Base Cost)*(1-(Cost Increase Factor)^lvl)/(1-(Cost Increase Factor)))
;cost increase factors -
; metal mine : 1.5
; crystal mine : 1.6
; deuterium synthesizer : 1.5
; solar plant : 1.5
; astrophysics : 1.75
; fusion reactor : 1.8
; graviton technology : 3
; all other buildings and researchs : 2
; metal mine base cost - 60 metal, 15 crystal, 0 deuterium
; metal mine production/hr - INT(30*lvl*1.1^lvl)
#include <Array.au3>
$maxtemperature = 80
$metalminelvl = 0
$crystalminelvl = 0
$dueteriumsynthesizerlvl = 0
$solarplantlvl = 0
$fusionreactorlvl = 0
$solarsatellite = 0
$metalstorage = 0
$crystalstorage = 0
$dueteriumstorage = 0
$metalden = 0
$crystalden = 0
$dueteriumden = 0
$roboticfactorylvl = 0
$shipyardlvl = 0
$researchlablvl = 0
$alliancedepotlvl = 0
$misslesilolvl = 0
$ninatefactorylvl = 0
$terraformerlvl = 0
$energytechnologylvl = 0
$lasertechnologylvl = 0
$iontechnologylvl = 0
$hyperspacetechnologylvl = 0
$plasmatechnologylvl = 0
$combustiondrivelvl = 0
$impulsedrivelvl = 0
$hyperspacedrivelvl = 0
$espionagetechnologylvl = 0
$computertechnologylvl = 0
$astrophysicslvl = 0
$intergalacticresearchnetworklvl = 0
$gravitontechnologylvl = 0
$weaponstechnologylvl = 0
$shieldingtechnologylvl = 0
$armortechnologylvl = 0
$lighfighter = 0
$heavyfighter = 0
$cruiser = 0
$battleship = 0
$smallcargo = 0
$heavycargo = 0
$colonyship = 0
$battlecruiser = 0
$bomber = 0
$destroyer = 0
$deathstar = 0
$recycler = 0
$espionageprobe = 0
$rocketlancher = 0
$lightlaser = 0
$heavylaser = 0
$gausscannon = 0
$ioncannon = 0
$plasmaturret = 0
$smallshielddome = 0
$largeshielddome = 0
$antiballisticmissiles = 0
$interplanetarymissiles = 0
Dim $metalminepoduction[30]
$x = 0
While $x < 30
$metalminepoduction[$x] = Int(30 * $x * 1.1 ^ $x)
$x = $x + 1
WEnd
Dim $metalminecost[30][3]
$x = 0
While $x < 30
If $x = 0 Then
  $metalminecost[$x][0] = 0
  $metalminecost[$x][1] = 0
  $metalminecost[$x][2] = 0
Else
  $metalminecost[$x][0] = Int(60 * 1.5 ^ ($x - 1))
  $metalminecost[$x][1] = Int(15 * 1.5 ^ ($x - 1))
  $metalminecost[$x][2] = 0
EndIf
$x = $x + 1
WEnd
Dim $metalmineconstrustiontime[30]
$x = 0
While $x < 30
If $x = 0 Then
  $metalmineconstrustiontime[$x] = 0
Else
  $metalmineconstrustiontime[$x] = Int((($metalminecost[$x][0] + $metalminecost[$x][1]) / 2500) * (1 / ($roboticfactorylvl + 1)) * (0.5 ^ $ninatefactorylvl))
EndIf
$x = $x + 1
WEnd
Dim $metalmineconsumption[30]
$x = 0
While $x < 30
$metalmineconsumption[$x] = Int(10 * $x * 1.1 ^ $x)
$x = $x + 1
WEnd
Dim $crystalmineproduction[30]
$x = 0
While $x < 30
$crystalmineproduction[$x] = Int(30 * $x * 1.1 ^ $x)
$x = $x + 1
WEnd
Dim $crystalminecost[30][3]
$x = 0
While $x < 30
If $x = 0 Then
  $crystalminecost[$x][0] = 0
  $crystalminecost[$x][1] = 0
  $crystalminecost[$x][2] = 0
Else
  $crystalminecost[$x][0] = Int(20 * 1.5 ^ ($x - 1))
  $crystalminecost[$x][1] = Int(10 * 1.5 ^ ($x - 1))
  $crystalminecost[$x][2] = 0
EndIf
$x = $x + 1
WEnd
Dim $crystalmineconstructiontime[30]
$x = 0
While $x < 30
If $x = 0 Then
  $crystalmineconstructiontime[$x] = 0
Else
  $crystalmineconstructiontime[$x] = Int((($crystalminecost[$x][0] + $crystalminecost[$x][1]) / 2500) * (1 / ($roboticfactorylvl + 1)) * (0.5 ^ $ninatefactorylvl))
EndIf
$x = $x + 1
WEnd
Dim $crystalmineconsumption[30]
$x = 0
While $x < 30
$crystalmineconsumption[$x] = Int(10 * $x * 1.1 ^ $x)
$x = $x + 1
WEnd
Dim $dueteriumsynthesizerproduction[30]
$x = 0
While $x < 30
$dueteriumsynthesizerproduction[$x] = Int(10 * $x * 1.1 ^ $x * (1.44 - 0.004 * $maxtemperature))
$x = $x + 1
WEnd
Dim $dueteriumsynthesizercost[30][3]
$x = 0
While $x < 30
If $x = 0 Then
  $dueteriumsynthesizercost[$x][0] = 0
  $dueteriumsynthesizercost[$x][1] = 0
  $dueteriumsynthesizercost[$x][2] = 0
Else
  $dueteriumsynthesizercost[$x][0] = Int(225 * 1.5 ^ ($x - 1))
  $dueteriumsynthesizercost[$x][1] = Int(75 * 1.5 ^ ($x - 1))
  $dueteriumsynthesizercost[$x][2] = 0
EndIf
$x = $x + 1
WEnd
Dim $dueteriumsynthesizerconstructiontime[30]
$x = 0
While $x < 30
If $x = 0 Then
  $dueteriumsynthesizerconstructiontime[$x] = 0
Else
  $dueteriumsynthesizerconstructiontime[$x] = Int((($dueteriumsynthesizercost[$x][0] + $dueteriumsynthesizercost[$x][1]) / 2500) * (1 / ($roboticfactorylvl + 1)) * (0.5 ^ $ninatefactorylvl))
EndIf
$x = $x + 1
WEnd
Dim $dueteriumsynthesizerconsumption[30]
$x = 0
While $x < 30
$dueteriumsynthesizerconsumption[$x] = Int(20 * $x * 1.1 ^ $x)
$x = $x + 1
WEnd
Dim $solarplantproduction[30]
$x = 0
While $x < 30
$solarplantproduction[$x] = Int(20 * $x * 1.1 ^ $x)
$x = $x + 1
WEnd
Dim $solarplantcost[30][3]
$x = 0
While $x < 30
If $x = 0 Then
  $solarplantcost[$x][0] = 0
  $solarplantcost[$x][1] = 0
  $solarplantcost[$x][2] = 0
Else
  $solarplantcost[$x][0] = Int(75 * 1.5 ^ ($x - 1))
  $solarplantcost[$x][1] = Int(30 * 1.5 ^ ($x - 1))
  $solarplantcost[$x][2] = 0
EndIf
$x = $x + 1
WEnd
Dim $solarplantconstructiontime[30]
$x = 0
While $x < 30
If $x = 0 Then
  $solarplantconstructiontime = 0
Else
  $solarplantconstructiontime = Int((($solarplantcost[$x][0] + $solarplantcost[$x][1]) / 2500) * (1 / ($roboticfactorylvl + 1)) * (0.5 ^ $ninatefactorylvl))
EndIf
$x = $x + 1
WEnd
Dim $roboticfactorycost[11][3]
$x = 0
While $x < 11
If $x = 0 Then
  $roboticfactorycost[$x][0] = 0
  $roboticfactorycost[$x][1] = 0
  $roboticfactorycost[$x][2] = 0
Else
  $roboticfactorycost[$x][0] = Int(400 * 2 ^ ($x - 1))
  $roboticfactorycost[$x][1] = Int(120 * 2 ^ ($x - 1))
  $roboticfactorycost[$x][2] = Int(200 * 2 ^ ($x - 1))
EndIf
$x = $x + 1
WEnd
Dim $roboticfactoryconstructiontime[11]
$x = 0
While $x < 11
If $x = 0 Then
  $roboticfactoryconstructiontime = 0
Else
  $roboticfactoryconstructiontime = Int((($roboticfactorycost[$x][0] + $roboticfactorycost[$x][1]) / 2500) * (1 / ($roboticfactorylvl + 1)) * (0.5 ^ $ninatefactorylvl))
EndIf
$x = $x + 1
WEnd
Dim $nanitefactorycost[11][3]
$x = 0
While $x < 11
If $x = 0 Then
  $nanitefactorycost[$x][0] = 0
  $nanitefactorycost[$x][1] = 0
  $nanitefactorycost[$x][2] = 0
Else
  $nanitefactorycost[$x][0] = Int(1000000 * 2 ^ ($x - 1))
  $nanitefactorycost[$x][1] = Int(500000 * 2 ^ ($x - 1))
  $nanitefactorycost[$x][2] = Int(100000 * 2 ^ ($x - 1))
EndIf
$x = $x + 1
WEnd
Dim $nanitefactoryconstructiontime[11]
$x = 0
While $x < 11
If $x = 0 Then
  $nanitefactoryconstructiontime = 0
Else
  $nanitefactoryconstructiontime = Int((($nanitefactorycost[$x][0] + $nanitefactorycost[$x][1]) / 2500) * (1 / ($roboticfactorylvl + 1)) * (0.5 ^ $ninatefactorylvl))
EndIf
$x = $x + 1
WEnd
Dim $shipyardcost[11][3]
$x = 0
While $x < 11
If $x = 0 Then
  $shipyardcost[$x][0] = 0
  $shipyardcost[$x][1] = 0
  $shipyardcost[$x][2] = 0
Else
  $shipyardcost[$x][0] = Int(1000000 * 2 ^ ($x - 1))
  $shipyardcost[$x][1] = Int(500000 * 2 ^ ($x - 1))
  $shipyardcost[$x][2] = Int(100000 * 2 ^ ($x - 1))
EndIf
$x = $x + 1
WEnd
Dim $shipyardconstructiontime[11]
$x = 0
While $x < 11
If $x = 0 Then
  $shipyardconstructiontime = 0
Else
  $shipyardconstructiontime = Int((($shipyardcost[$x][0] + $shipyardcost[$x][1]) / 2500) * (1 / ($roboticfactorylvl + 1)) * (0.5 ^ $ninatefactorylvl))
EndIf
$x = $x + 1
WEnd
Dim $researchlabcost[15][3]
$x = 0
While $x < 15
If $x = 0 Then
  $researchlabcost[$x][0] = 0
  $researchlabcost[$x][1] = 0
  $researchlabcost[$x][2] = 0
Else
  $researchlabcost[$x][0] = Int(200 * 2 ^ ($x - 1))
  $researchlabcost[$x][1] = Int(400 * 2 ^ ($x - 1))
  $researchlabcost[$x][2] = Int(200 * 2 ^ ($x - 1))
EndIf
$x = $x + 1
WEnd
Dim $researchlabconstructiontime[11]
$x = 0
While $x < 11
If $x = 0 Then
  $researchlabconstructiontime = 0
Else
  $researchlabconstructiontime = Int((($researchlabcost[$x][0] + $researchlabcost[$x][1]) / 2500) * (1 / ($roboticfactorylvl + 1)) * (0.5 ^ $ninatefactorylvl))
EndIf
$x = $x + 1
WEnd

Where am I interacting with the game server? If the mods see this as against the forum rules, then please close.

[Valik]

I'm going to allow this thread for several reasons:

• The user himself brought it to my attention and seems prepared to accept my judgement either way.
• So far this thread has been purely mathematical in nature. The fact that it is related to data for a game is almost tangential but I can see how viewing the formulas and how things interact will benefit understanding in solving the problem.
• I can not see how this tool grants an advantage or alters the game. An optimized build order is useful but no plan survives first contact with the enemy. A good player can counter someone using a perfect build order.
• This is far above the common rabble. I don't see the usual gamer type being able to abuse this. I don't see them really understanding, implementing and adapting an optimized build order.

So, the conclusion: Yes, this technically violates the game rule. However, I'm waving the rule for this specific instance due to the above reasons. Carry on.

[czardas]

I took a quick look at the links you posted jb09, and it seems quite educational. I'll read more about it later. I'm glad Valik has allowed this thread to continue. I'm also quite impressed by your actions.

Edited March 1, 2012 by czardas

[jb09]

Thank you czardas. And yes the link are very educational, u might even find the topic about a program I created for the game, used visual basic for that though.

Anyway, before I continue to post, I'm waiting on a clear understanding from Valik. Which I appreciate allowing this thread to continue.

[czardas]

Valik has already said it was okay. Let's just stick to the maths.

[jb09]

Right.

I'm about to play with my idea which you didn't understand with small sets of data. And post the code so maybe then you understand what I was trying to say.