Optimize an Algorithm

  • 状态: Open
  • 奖金: $200
  • 参赛作品已收到: 4
  • 获胜者: gospodima

竞赛简介

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.

您还可能感兴趣的技能

公共说明面板

  • Rahulllkumarrr
    Rahulllkumarrr
    • 3 天 之前

    #guaranteed

    • 3 天 之前
  • monmohon
    monmohon
    • 1 周 之前

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

    • 1 周 之前
    1. scalig
      竞赛主办者
      • 1 周 之前

      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 周 之前
  • grammal
    grammal
    • 1 周 之前

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

    • 1 周 之前
    1. scalig
      竞赛主办者
      • 1 周 之前

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

      • 1 周 之前
    2. scalig
      竞赛主办者
      • 1 周 之前

      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 周 之前
  • mitikuyohannes
    mitikuyohannes
    • 1 周 之前

    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 周 之前
    1. scalig
      竞赛主办者
      • 1 周 之前

      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 周 之前

显示更多评论

如何以竞赛开始

  • 发布您的竞赛

    发起您的竞赛 快速简单

  • 获取众多参赛作品

    获取大量参赛作品 来自世界各地

  • 悬赏最佳参赛作品

    悬赏最佳参赛作品 下载文件-简单!

立即发布竞赛 或者立即加入我们!