Contest: String array concatenation

03-21-2007, 03:48 PM

I decided a new contest type.

In this one we focus on a real life Jass problem and find the best solution.

The current question is this:

Given an array of strings, join all the strings in a single one (mass concatenate)

When you concatenate 2 strings, you create a new one, and as you know, this string never gets cleaned... how would you join an array of strings by generating the least quantity of garbage?

Notice that the memory each string takes depends on its length. So reducing the length of the unnecessary strings might be a better way to generate less garbage memory than generating less strings If the strings are too big.

Solution prototype:

JASS:

globals
    string array udg_tojoin //0-based indexes, please
    integer udg_tojoinN     //count of elements in the array
endglobals

function ConcatenateArray takes nothing returns string //returns the concatenation of all the strings in the array

Deadline: Next thursday, 23:00 PM GMT.

Review: Places are chosen by estimated amount of memory used by the uncleanable strings created.

In case of a tie, the fastest algorithm takes priority (Minor speed differences are ignored and considered a tie in execution speed as well).

Only valid solutions are considered. A valid solution must be able to deal with all kinds of input generating a correct result and NOT crashing the thread; Always expect the array to be correctly initialized for the input size. Maximum array size would be 8191.

Prizes 15, 12 and 8 rep for 1st, 2nd and third place.

--
Example

JASS:

    string array udg_tojoin //0-based indexes, please
    integer udg_tojoinN     //count of elements in the array

    set udg_tojoin[0]="aaa"
    set udg_tojoin[1]="X#4"
    set udg_tojoin[2]="..."

    set udg_tojoinN=3

    call BJDebugMsg(ConcatenateArray()) // displays: aaaX#4...

03-21-2007, 05:22 PM	#2
Ammorth	Question, can we use the [ljass]string array udg_tojoin[/jass] during the function as in changing the values of it? And under what name should we submit our entries into the paste-bin?

03-21-2007, 05:23 PM	#3
Vexorian	possibly [joinstrings] hmmm forgot to mention how to submit stuff. hmm. It would be better if you didn't change the input array.

03-21-2007, 07:20 PM	#4
Daelin	I suppose there is no voodoo function which monitorizes memory? And if so, I wonder if task manager is the way you will judge the solutions. -Daelin

03-21-2007, 07:24 PM	#5
Vexorian	It is possible to predict how much extra strings will be generated, at least I hope so, can't monitor memory since we only want to avoid string memory, I've seen the memory increase sometimes there is some heavy processing or something like that.

03-21-2007, 07:37 PM	#6
PipeDream	We can rig something up in war3err.

03-22-2007, 03:05 AM	#7
wantok	What is the maximum length a string can be? I set up an array with 2000 strings to test my solution. If I make the strings equal to "-1", "-2", "-3" etc up to "-2000" the game freezes when i try and concatenate them. If i set all the strings to just "1" it concatenates fine. Am I hitting some limit on the string length in the first case? Or is my code just screwy?

03-22-2007, 03:18 AM	#8
Ammorth	The string length maximum is whatever vexorian decides when he tests them. Not sure if there is a string length, but I bet vexorian will be smart enough to not go that far. I think I have a decent script now, or at least a method. Won't submit it yet though, incase I think of something better than it.

03-22-2007, 10:54 AM

Toadcop

well it's relative ! because if you would parse any string by token it will create any token separate... hmmmm... any new cut create a new string so. if less cut so less new string... a new a method to get out of string integers and don't to make much garbage ! i will need only a parser by 1 token and find needed pointers and give whole string and this pointers to func and it will recreate needed integer or real and only use "0","1","2","3","4","5","6","7","8","9" string so only 10 string to get ANY integer ! and also "." for reals...
you task is to complicated... because i think you self don't sure for 100% which method is the best...

03-22-2007, 02:28 PM	#10
Ammorth	Keep in mind if, you hit the thread limit, its bye bye for your script!

03-22-2007, 02:32 PM	#11
Vexorian	Let's say each string is not bigger than 5 chars?

03-22-2007, 09:27 PM

#12

Toadcop

Quote:

Keep in mind if, you hit the thread limit, its bye bye for your script!

??? aha yes i call it 1000 times in same thread... and btw i use ExecuteFunc() so...

Code:

// it's a bit old
function GetIntBitwiseBR takes string STR,integer a,integer b returns integer
    local integer bc=b
    local integer m=1
    local integer t=0
    local string s=null
  loop
   exitwhen bc<=a
   set s=SubString(STR,bc-1,bc)
   set t=t+(S2I(s)*m)
if s=="-" then
   set t=t*(-1)
endif
   set m=m*10
   set bc=bc-1
  endloop
    return t
endfunction

function GetRealBitwiseBR takes string STR,integer a,integer b returns real
    local integer bc=b
    local real m=1.0
    local real t=0.0
    local real t2=0.0
    local string s=null
  loop
   exitwhen bc<=a
   set s=SubString(STR,bc-1,bc)
if s=="-" then
   set t=t*(-1.0)
   set t2=t2*(-1.0)
elseif s=="." then
   set t2=t/(m)
   set bc=bc-1
   set s=SubString(STR,bc-1,bc)
   set m=1.0
   set t=0.0
endif
   set t=t+(S2R(s)*m)
   set m=m*10.0
   set bc=bc-1
  endloop
    set t=t+t2
    return t
endfunction

Quote:

not bigger than 5 chars?

... ok it's 40 bits per string. ok i will think about this...