Does Array Contain Numbers that Add up to Given Sum

Get help using Construct 2

Post » Sat May 31, 2014 8:18 pm

Hello - what is the correct procedure to find out if a given array of X size has a specific number in it or if the sum of any amount of the array numbers adds up to a specific number?

Say you have an array of [2, 6, 1, 4] and you want to find out if the number 6 is in the array or any sum of numbers adds up to 6.

So, both index 1 (which is a 6) is correct and index 0 + index 3 (which is 2 + 4) is correct.
B
33
S
7
G
8
Posts: 312
Reputation: 8,528

Post » Sat May 31, 2014 9:00 pm

Nevermind - I think I have it figured out by using nested For loops and testing the sum of array.at(index) for the various loops. Seems to be working.
B
33
S
7
G
8
Posts: 312
Reputation: 8,528

Post » Sat May 31, 2014 9:05 pm

I think you'd have to try every single combination to do this, which can add up a lot:

In you exemple [A, B, C, D] for a value Z, you have to compare I think 16 sums, there may be a way to do it (like excluding some of them if they cannot work, for exemple if the sum of all positives values cannot reach the number or above it, then no sum will be able to), but the basic concept is this I think. I hope there is an easier way

you could maybe try a repeat loop (16 times):

compare Z = A*((int(loopindex/8))%2) + B*((int(loopindex/4))%2) + C*((int(loopindex/2))%2) + D*(loopindex%2)

intested but this should try all the sums, (it will also compare Z to 0 the first time)

EDIT: glad you figured it out, I should have though of using not only one loop though.
Last edited by Aphrodite on Sat May 31, 2014 10:27 pm, edited 1 time in total.
Game design is all about decomposing the core of your game so it becomes simple instructions.
B
52
S
22
G
18
Posts: 2,122
Reputation: 17,093

Post » Sat May 31, 2014 9:17 pm

@Aphrodite - I think my "solution" is a work in progress, as it doesn't work 100% of time when I'm testing. I'm still trouble-shooting, so i appreciate anyone else's thoughts or solutions. Thanks.
B
33
S
7
G
8
Posts: 312
Reputation: 8,528

Post » Sat May 31, 2014 9:46 pm

Currently I have made a function that'll return the number of sum that give the wanted result (except if the value wanted is 0):

Image

of course now the thing is instead of returning number_of_sum, it should return a string corresponding to what we want, and to consider the 0, I'm working on that (also I think getbit makes it so you cannot make it work on an array > 32 in width, of course we can still use other techniques I think)
Game design is all about decomposing the core of your game so it becomes simple instructions.
B
52
S
22
G
18
Posts: 2,122
Reputation: 17,093

Post » Sun Jun 01, 2014 7:53 pm

@Aphrodite I like that algo you found there. Inspired I found a way to extend it beyond 32 elements. The idea is to use another array of 1's and 0's instead of just a number, and update the array with a simple function to add 1 in binary.
https://dl.dropboxusercontent.com/u/542 ... count.capx

It looks like counting sums of zero works, but it's also counting the case of none of the numbers added together. That case could be discarded by not using it when loopindex=0.

Edit:
Under further tests something seems broken with my capx.
Edit2:
Fixed
Last edited by R0J0hound on Sun Jun 01, 2014 9:39 pm, edited 1 time in total.
B
91
S
31
G
103
Posts: 5,234
Reputation: 67,754

Post » Sun Jun 01, 2014 8:59 pm

R0J0hound wrote:@Aphrodite I like that algo you found there. Inspired I found a way to extend it beyond 32 elements. The idea is to use another array of 1's and 0's instead of just a number, and update the array with a simple function to add 1 in binary.
https://dl.dropboxusercontent.com/u/542 ... count.capx

It looks like counting sums of zero works, but it's also counting the case of none of the numbers added together. That case could be discarded by not using it when loopindex=0.

Edit:
Under further tests something seems broken with my capx.



@R0J0hound

I didn't fully understood the capx (didn't had much time to look at it today), but instead of using an array of 0 and 1, why not taking int(Array.CurX/(2^loopindex))%2 instead of the getbit, I think it does the job over 32 elements(unless I got my math wrong).

Also by adding a condition "loopindex > 0" at your 11 event, it does not add the empty case for 0.

EDIT: Tried with 9, indeed not all solutions are found
Edit2: I begin to see the concept, your bits array help to choose the values to show it seems, I'm still strugling to understand why no all values are counted though
Game design is all about decomposing the core of your game so it becomes simple instructions.
B
52
S
22
G
18
Posts: 2,122
Reputation: 17,093

Post » Sun Jun 01, 2014 9:43 pm

Ok, found the issue. I was looping with width^2 instead of 2^width. Now it gives all results. The bits array works much like getbit but can use many more than just 32 bits. Other than that it works the same way as yours.

Edit:
While it's true that you can bypass the getbit expression to access some more bits you'll run into issues once you exceed the number of significant digits in floating point numbers.
B
91
S
31
G
103
Posts: 5,234
Reputation: 67,754


Return to How do I....?

Who is online

Users browsing this forum: No registered users and 15 guests