Optimize an Algorithm

  • Tình trạng: Closed
  • Giải thưởng: $200
  • Các bài thi đã nhận: 4
  • Người chiến thắng: gospodima

Tóm tắt cuộc thi

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.

Các kĩ năng yêu cầu

Những bài dự thi tốt nhất dự cuộc thi này

Xem thêm bài dự thi

Bảng thông báo công khai

  • Rahulllkumarrr
    Rahulllkumarrr
    • cách đây 1 tháng

    #guaranteed

    • cách đây 1 tháng
  • monmohon
    monmohon
    • cách đây 1 tháng

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

    • cách đây 1 tháng
    1. scalig
      Chủ cuộc thi
      • cách đây 1 tháng

      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.)

      • cách đây 1 tháng
  • grammal
    grammal
    • cách đây 1 tháng

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

    • cách đây 1 tháng
    1. scalig
      Chủ cuộc thi
      • cách đây 1 tháng

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

      • cách đây 1 tháng
    2. scalig
      Chủ cuộc thi
      • cách đây 1 tháng

      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

      • cách đây 1 tháng
  • mitikuyohannes
    mitikuyohannes
    • cách đây 1 tháng

    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?

    • cách đây 1 tháng
    1. scalig
      Chủ cuộc thi
      • cách đây 1 tháng

      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].

      • cách đây 1 tháng

Xem thêm bình luận

Làm thế nào để bắt đầu với cuộc thi

  • Đăng cuộc thi của bạn

    Đăng cuộc thi của bạn Nhanh chóng và dễ dàng

  • Nhận được vô số bài dự thi

    Nhận được vô số Bài dự thi Từ khắp nơi trên thế giới

  • Trao giải cho bài thi xuất sắc nhất

    Trao giải cho bài thi xuất sắc nhất Download File - Đơn giản!

Đăng cuộc thi ngay hoặc tham gia với chúng tôi ngay hôm nay!