2

I've reached what is to be the most simple part of my program but I am a bit lost, on how I can do this part and keep it efficient at the same time.

attacker= {3,10,14,15,17,18};
defender = {1,5,7,9,12,18};

So both of these are two arrays of same length, and also sorted. To put this in context the numbers in both arrays represent rolls entered in by the user.

Except in this risk the defender is allowed to rearrange his array so that he can win more battles. So he can pair 5 with 3, if he wanted.

I'm lost on how to do this without being incredibly inefficient or prone to much error.

gsamaras
  • 71,951
  • 46
  • 188
  • 305
Jude
  • 449
  • 1
  • 7
  • 17
  • Here you go: `defender = {5,12,18, 9, 1,7};` – Eugene Sh. Mar 04 '16 at 22:04
  • @Eugene sh I have two arrays, both are sorted from lowest to highest. The elements of both arrsys represent dice rolls. Then 2nd array is allowed to rearrange its self so that it will win more dicerolls than it would before – Jude Mar 04 '16 at 22:12

1 Answers1

4

I would propose this algorithm:

Merge the two arrays and mark the elements which are defender (d) or attacker (a):

d a d d d  a  d  a  a  a  d  a
1 3 5 7 9 10 12 14 15 17 18 18

(For two equal elements, place the defender first).

Then take the pairs where a d pattern is; these would be the battles defender wins:

d a d d d  a  d  a  a  a  d  a
1 3 5 7 9 10 12 14 15 17 18 18
  ^ ^      ^  ^        ^  ^

And just arrange the winning numbers first, and the losing ones last:

defender = {5, 12, 18, 1, 7, 9}
gsamaras
  • 71,951
  • 46
  • 188
  • 305
Eugene Sh.
  • 17,802
  • 8
  • 40
  • 61
  • Currently in my program we use mergesort, and I was thinking of merging the array by making a larger array (in this case size 12) and calling mergesort on that, but then I'd lose which roll is an attacker/defender. Any idea how I could get around that? – Jude Mar 05 '16 at 18:31
  • Work on two arrays in parallel. Or store the info in a `struct` – Eugene Sh. Mar 05 '16 at 20:52
  • +1 This is a very clever approach. I was starting thinking about complex AI stuff which would've been far less efficient, but thankfully came here before. (OP asked the same question again, this time with own brute force code) – Daniel Jour Mar 07 '16 at 01:40
  • An upvote from me too. I implemented the algorithm and it works: http://stackoverflow.com/a/35835138/2411320 – gsamaras Mar 07 '16 at 02:38