wu :: forums « wu :: forums - Urgent Excel » Welcome, Guest. Please Login or Register. Feb 21st, 2024, 2:52pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: towr, ThudnBlunder, SMQ, Icarus, Grimbal, william wu, Eigenray)    Urgent Excel « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: Urgent Excel  (Read 4223 times)
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Urgent Excel   combos_2.zip « Reply #25 on: May 10th, 2017, 11:03am » Quote Modify

An alternative, more scalable solution. Using an extra column of integers as bitmask (skipping powers of 2) and a row of powers of two to check whether to include a value or not.
You can now simply extend the whole matrix in one go by copying columns/rows

NB, I had to use OpenOffice. I think excel actually has a BITAND, which would've made it a bit easier.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
fatball
Senior Riddler

Can anyone help me think outside the box please?

Gender:
Posts: 315
 Re: Urgent Excel   « Reply #26 on: May 10th, 2017, 12:53pm » Quote Modify

towr, your generalized model is very neat.  Can you elaborate on the rationale behind the formula inside the body of the table please?
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Urgent Excel   « Reply #27 on: May 10th, 2017, 10:35pm » Quote Modify

The basic rationale is, include value for column (top row) if the bit for its corresponding power of two (5th row) is set in the index bit-mask (column A)

For reference, the complete formula (in D7) is =IF(MOD(INT(\$A7/D\$5);2);D\$1;0)

\$A7 is the index bitmask in column A, row 7, \$A makes the column reference absolute, so copying will always refer to the first column when copied. The row will automatically change to the correct one when copied to another row.
D\$1 is the value we want to use in the combo (or not), it's always the number in the top row, but column can vary when copied elsewhere.
D\$5 is the bit we need to lookup in the bitmask to decide whether to include the value or not, it's always in the fifth row of the column.

Because I can't use BITAND (because openoffice sucks even more than excel), I'm using an alternative to check whether the bit is set or not.
BITAND(x; 2^y) == (x div 2^y) % 2 == MOD( INT(x/2^y); 2)
So, if the bit is set, include the value D\$1 in the combo, else leave it out and use 0 instead.
 « Last Edit: May 10th, 2017, 10:35pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
fatball
Senior Riddler

Can anyone help me think outside the box please?

Gender:
Posts: 315
 Re: Urgent Excel   « Reply #28 on: May 11th, 2017, 6:54am » Quote Modify

I am fully comfortable with all your Excel work including the absolute and relative referencing but guess I need to study more about the concept of bit and bitmask.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Urgent Excel   « Reply #29 on: May 11th, 2017, 1:02pm » Quote Modify

Well, bits and bitmasks is just a useful abstraction for me, it's not necessary, per se.

Basically every number can be written uniquely as a sum of distinct powers of two, e.g. 11 = 1 + 2 + 8. And what I'm doing is checking if a given power of two is part of the sum for a given number. In this case 4 isn't part of the sum (and also anything greater than 8), so we'd leave the third value (and anything after the 4th) out of the combination on the row with index 11.
 « Last Edit: May 11th, 2017, 1:03pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
fatball
Senior Riddler

Can anyone help me think outside the box please?

Gender:
Posts: 315
 Re: Urgent Excel   « Reply #30 on: May 11th, 2017, 3:57pm » Quote Modify

Thanks towr, so then why would this approach end up having the effect of a binary algorithm?  How do you reconcile the two concepts?
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Urgent Excel   « Reply #31 on: May 11th, 2017, 11:40pm » Quote Modify

The sum of powers of two representation is equivalent to the binary representation.
A binary representation 1011 means 1*8 + 0*4 + 1*2 + 1*1 = 8 + 2 + 1 = 11

And you might notice it's very much the same as what we're trying to do, except instead of powers of two we have a "random" set of numbers.
Say we have numbers a, b, c, d that we want to use in a combination. Then we can use the binary representation 1011 to mean 1*a + 0*b + 1*c + 1*d = a + c + d
We just replace the powers of two in the sum by the numbers we want combinations for.
By looping through all binary representations (up to 2^(# of values)), we loop through all combinations of our set of numbers.

Looping through all binary representations is also equivalent to a manual approach where each step you duplicate all the rows, but include the next power of two in the new rows:
0*1
1*1
=>
0*1
1*1
1*2 + 0*1
1*2 + 1*1

=>
0*1
1*1
1*2 + 0*1
1*2 + 1*1
1*4 + 0*1
1*4 + 1*1
1*4 + 1*2 + 0*1
1*4 + 1*2 + 1*1

The main difference with my manual version earlier is that my procedure was in some way reversed: I started with all 1s (in binary), and removed them from a column in each step, instead of starting with all zeroes and adding 1s in a column each step.

Comparison:

0000 vs 1111
=>
0000 - 1110
0001 - 1111
=>
0000 - 1100
0001 - 1101
0010 - 1110
0011 - 1111
=>
0000 - 1000
0001 - 1001
0010 - 1010
0011 - 1011
0100 - 1100
0101 - 1101
0110 - 1110
0111 - 1111
=>
0000 - 0000
0001 - 0001
0010 - 0010
0011 - 0011
0100 - 0100
0101 - 0101
0110 - 0110
0111 - 0111
1000 - 1000
1001 - 1001
1010 - 1010
1011 - 1011
1100 - 1100
1101 - 1101
1110 - 1110
1111 - 1111

You end up with exactly the same thing both ways.

A lot of problems are just figuring out how to map one thing you know (numbers 0 to 2^10) to another thing you want (sums of combination of up to 10 values). And there's multiple equivalent ways to do it.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
fatball
Senior Riddler

Can anyone help me think outside the box please?

Gender:
Posts: 315
 Re: Urgent Excel   « Reply #32 on: May 14th, 2017, 9:08am » Quote Modify

is it possible to automate the manual copying and pasting with a formula like this one: MOD( INT(x/2^y); 2) in order to list a full result of binary representation e.g. 1100, 1010, etc.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Urgent Excel   « Reply #33 on: May 14th, 2017, 1:10pm » Quote Modify

If you want the binary representations, you could just fill in 1 for all values in the last spreadsheet.
Though perhaps a better way is to use excels DEC2BIN function. (Which gives the binary representation as (probably a) string in one column, rather than as 0s and 1s spread over multiple columns.)
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
dudiobugtron
Uberpuzzler

Posts: 735
 Re: Urgent Excel   « Reply #34 on: May 14th, 2017, 1:33pm » Quote Modify

Afaict that only goes up to 512.  That's according to this page, anyway.

 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Urgent Excel   « Reply #35 on: May 14th, 2017, 10:18pm » Quote Modify

Huh, you're right. What a weird limitation. Who ever heard of ten bit numbers.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
fatball
Senior Riddler

Can anyone help me think outside the box please?

Gender:
Posts: 315
 Re: Urgent Excel   « Reply #36 on: May 16th, 2017, 10:23am » Quote Modify

Thank you all for help!
 IP Logged
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »