Optimize an Algorithm

• Status: Closed
• Præmier: \$200
• Modtagne indlæg: 4
• Vinder: gospodima

Konkurrence Instruktioner

Edit:
Support functions may be included, but please ensure there is a function which takes the test case array as the only argument and returns an object in the format:
{ i: [0, 0, 0], weight: 0 }
wherein the x = i[] values map to test[n].b[x] (with -1 for "ignore") and match the order of the test array (like in the linked jsfiddles below.) I am adding the tester to be utilized for comparing submissions to this contest as [login to view URL] - the count specified on line 202 will be >127 and n=16. Submissions will be entered similarly to line 114. Added [login to view URL] with computed best weights.

I've been wracking my brain against this problem for a day and it seems like there might be a solution in the realm of a random walker algorithm or by caching partial results or some combination thereof, but thus far haven't been able to figure it out and am curious if anyone might know a solution.

In short: I'm trying to merge objects based on a best-fit for order-agnostic arrays in a collision-free manner.

The pre-processing which takes place prior to where this algorithm fits in can easily produce something like:

let test = [
{ a: 1, b: [2,3,4], weight: 3},
{ a: 2, b: [3,9,15], weight: 6},
...
];

Wherein the test array contains a set of elements broken down as:

* a: the left-side array index
* b: an array of possible right-side array indexes which match
* i: output in range -1 - n where n = maximum element of array, -1 signifies "ignore this match"
* weight: the weight produced if a is matched with any of the b[] entries

The goal is to produce the highest sum of weights for i values >= 0 without using any b[] entry twice.

**WARNING** the following link will take 3-5 minutes before your browser tab unfreezes if you open it, though your browser may present a prompt to allow you to stop it early.

I have a working version of this [available in this fiddle]([login to view URL]) but it is slow. I'd like to get this down to under 2 seconds at most for the test case included.

Any thoughts on how this might be achieved or does anyone know of an extant algorithm for doing this?

If you don't want to wait for the linked fiddle to run, this is the truncated result (best combined score = 98)

98 98 98 0,2,2,1,0,2,2,0,0,0,1,2,-1,2,0,2

A more in-depth test mechanism is [available here]([login to view URL]) with several test case prepared (also attached) - the truncated output of those tests is below:

99 2,2,2,2,0,2,0,0,2,0,2,1,2,2,0,-1
=====================================
99 2,2,2,2,0,2,0,0,2,0,2,1,2,2,0,-1
=====================================
99 3,1,2,2,0,3,0,0,2,0,3,2,2,2,0,-1
=====================================
101 3,1,2,2,0,3,0,0,2,0,3,1,2,2,0,2

Note: to win the contest any test composed of 16 elements with up to 8 elements in the b[] array of each must return within under 2 seconds with an accurate result equivalent to the brute forced output above. The result need not match the result produced by a brute force via the linked algorithms, but it must be a valid combination (check function is provided) and have the same weight as the best brute-forced combination. If no solutions meet this criteria I may at my discretion choose the closest matching entry as determined via benchmarks, but this is not a guaranteed contest because if nothing comes close no entry will be selected. Additional randomly-generated test cases will be a part of the final evaluation of submissions.

Winner

Offentlig Præciserings Opslagstavle

• Rahulllkumarrr
• 1 måned siden

#guaranteed

• 1 måned siden
• monmohon
• 1 måned siden

hi , contest holder image is ok
but for this contest demo url required for testing

• 1 måned siden
1. Konkurrenceafholder
• 1 måned siden

I believe the site only allows pdf submissions, but you should be able to provide a link to a jsfiddle within the pdf (unfortunately it doesn't allow me to copy+paste directly from the pdf, so while you should submit the code in a pdf file please include a jsfiddle link at the top so I can test it.)

• 1 måned siden
• grammal
• 1 måned siden

Please make a text (research) contest, not a design (image) contest.

• 1 måned siden
1. Konkurrenceafholder
• 1 måned siden

I don't see an option for that but will ask freelancer.com support

• 1 måned siden
2. Konkurrenceafholder
• 1 måned siden

after speaking with freelancer.com technical support they have stated the contest supports .txt and .js file entries - failing that it should accept .pdf - you can just link a jsfiddle entry in a pdf if you prefer

• 1 måned siden
• mitikuyohannes
• 1 måned siden

Could you make it more clear?
E.g { a: 18, b: [2,8,18], weight: 4}, this is the last element from the array you posted, what is `a` `b` and `weight` here? Where did this data came?

• 1 måned siden
1. Konkurrenceafholder
• 1 måned siden

a and b are indices to the two arrays being matched. The line you pasted essentially translates to a[18] may be matched with b[2], b[8], or b[18] - with a weight of 4 applied to the sum if it can be matched to any of them. The b side doesn't correspond to the a side otherwise (e.g. they are indices to two different arrays) however both any item in a and any item in b may only be matched to at most 1 item in the alternate array. That is to say a[18] may not be matched to both b[2] and b[8] and if a[18] is matched to b[2] then no other item within a may be matched to b[2].

• 1 måned siden

Sådan kommer du i gang med konkurrencer

• Opret din konkurrence Hurtigt og nemt

• Få tonsvis af indlæg Fra hele verden