August Challenge of the Month Discussion

[Jack in the UK]

Re readin the question set by Bill im more preplexed, i can now even see the issue receivable / sales ledger / credit control, will or should eat this alive, 52or54 is not that many if on one user account, the account package will be able to run tally this and so will be easy enough. The debtor should be able to send a remitance advice or call them direct to say, oh explain this one.

If sales ledger in Excel than is not an accounting pacage as discribed. And thats not a real questin as they conflict.

Saying that 54 invoices on one account in 30 day or say 120 max is fine but after that would be legasy debts never paid in full so impossible to program.

Im not blunting the question as i know code will do as you want, but all im saying is its not workable so dont rely on it, nothing will or can substute for keen staff with sharp eyes.

Im preplex and who the 54 are obtained as if not pasteable in excel i can see the saving!!!

 

[Jay Petrulis]

Chris,

The brute force method is the only way this is going to be "solved" but you can use all sorts of techniques to narrow the scope a bit.

The systems designed to solve these problems use genetic algorithms where the program tries to learn from its "mistakes" and focus on only the possible successful outcomes. They also use simulated annealing (kicking the program out of a node that is going nowhere), and branch and bound techniques. The details are way beyond me.

Your code from the "longest macro" thread can be used to do this. One thing to speed it a bit -- since we are dealing with combinations instead of permutations, you can use the following

<pre>For i = 1 To n - 2
For j = i + 1 To n - 1
For k = j + 1 To n
'do stuff
Next k
Next j
Next i</pre>

rather than

<pre>For i = 1 To n
For j = 1 To n
For k = 1 To n
' eliminate duplicates and do stuff
Next k
Next j
Next i</pre>

as you go further up the levels, significant savings will start to show.

Jack,

Don't get hung up on the specifics. Consider another situation. I work at a trust bank where there is a need to reconcile pension fund statements. When the accounts do not balance, it is up to the analyst to find the discrepancy. Usually, it is one entry that is causing the problem, as it is not mapping through all the investment schedules correctly. In no way will the analyst be able to know this ahead of time (nor will the client or money manager have any details about this). There are no legal rules that must be followed. The out-of-balance must be found and corrected. Any systematic procedure would help. Of course, there are other guides used to spot the problems, but sometimes you just have to pour through the data and find the number(s).

 

[Mark W.]

On 2002-08-03 01:01, Chris Davison wrote:
how many answers are there ?

I got one set in about 3 mins running time if it's any help...

680.23
98.40
444.98
324.84
978.53
911.45
409.17
718.32

just a very basic brute-force but random method.... I'll keep tinkering
This message was edited by Chris Davison on 2002-08-03 01:04

I'm guessing that 98.4 is a typo meant to be 89.4.

 

[Mark W.]

Here's another solution set...

77.74
116.14
192.65
194.58
222.52
538.64
680.23
691.83
1842.59

 

[Mark W.]

...And another...

77.74
89.40
116.14
185.58
192.65
194.58
228.31
230.72
324.84
329.97
346.35
365.43
456.68
507.08
911.45

 

[Ian Mac]

I sat and did about 5 or 6 brute force solutions at work, I didn't post them as I didn't think THAT was that problem set. Forgive me but we're not going to get anywhere quoting what's right in the numbers set (next week it may be 67 and whole different set of numbers).

Did nobody read Jays:

This problem won't be "solved" with an algorithm, at least not by anyone using Excel by August 31. This challenge is a "Holy Grail" of computer science. However, that doesn't mean the exercise is of no use. In fact, I think it is highly instructive about using Excel and has a lot of practical use for smaller data sets. So I wouldn't worry too much about how truly applicable this is for the specific problem description.


I came into this Excel thingy from a Graphic design background, but fully understand the need to try and stretch to the challenge.

BUT, Jay, why arn't you interested in the CD?? I worked on 100 of the files and there's some great stuff on it.

That's all I have to say, rant rant rant

Regards,

Don't argue why the wealth is there, why we need the wealth anyway, or who has it, just SHARE IT!!.

 

[Mark W.]

Here are the 1st 30 rows of the Solver model that is producing my results. The model parameters are saved (and reloadable) from cells F1:F5.

Book2.xls
	A	B	C	D	E	F	G
1	77.74	1		0.00		0.00
2	83.06	1				54.00
3	89.40	1				FALSE
4	116.14	0				TRUE
5	126.69	0				100.00
6	144.77	1
7	160.62	1
8	185.58	0
9	192.65	1
10	194.58	0
11	219.10	0
12	222.52	0
13	228.31	1
14	230.72	0
15	244.22	1
16	280.71	0
17	324.84	0
18	329.17	1
19	329.97	0
20	346.35	0
21	365.43	0
22	409.17	0
23	440.93	1
24	441.43	0
25	444.98	0
26	456.68	0
27	507.08	0
28	515.11	0
29	538.64	0
30	542.12	0
Sheet1

As of this point in time this model has produced the following solution sets...

77.74, 116.14, 192.65, 194.58, 222.52, 538.64, 680.23, 691.83, 1842.59

77.74, 89.40, 116.14, 185.58, 192.65, 194.58, 228.31, 230.72, 324.84, 329.97, 346.35, 365.43, 456.68, 507.08, 911.45

77.74, 83.06, 89.40, 144.77, 160.62, 192.65, 228.31, 244.22, 329.17, 440.93, 978.53, 1587.52
This message was edited by Mark W. on 2002-08-03 17:49

 

[Chris Davison]

in terms of processor speed, is it any quicker to check if 1002, 2003, 3004 etc add up to 5,007 (ie whole numbers) than it is to check whether 10.02, 20.03, 30.04 etc add up to 50.07 (ie decimals) ?

 

[PaddyD]

Following some prompting from Jay, and as it's only slightly tangential to the main challenge:

This problem won't be "solved" with an algorithm, at least not by anyone using Excel by August 31. This challenge is a "Holy Grail" of computer science...

To the extent that this problem relates to the P=NP? question, it might be worth pointing out that a full solution could earn you both the Mr Excel CD and $1 million. I am agnostic about which prize would be more valuable.

In Chris' thread, I think PaddyD responded about this being a P=NP (complete or hard???) problem, like the travelling salesman and the knapsack problem...

BTW, the travelling salesman problem has been solved...

That's not strictly true. The solution of a particular version of the travelling salesman (TS), while interesting to salesman & those concerned with the general issue of algorithmic optimisation, doesn't really bare on the general reason why TS is famous - i.e. does P=NP?

As this is a Microsoft Excel forum, is seems appropriate to point to a link that (a) explains the P=NP? issue in some detail, and (b) relates it to Minesweeper:

http://www.claymath.org/prizeproblems/milliondollarminesweeper.htm

Paddy
This message was edited by PaddyD on 2002-08-04 19:18

 

[Sharad Kothari]

The outline of code is as follows:

1. First, all the values is stored in an Array in Ascending Order. This is been done by putting all the values in a Range in Excel, Sorting it and loading it in Array.
2. A recursive routine is used to find out the Target Total.
3. This recursive routine works in the reverse order from the last (and highest point of array).
4. The last point is extracted and checked against the Target Sum. If this last point is higher than the Target Sum, then routine moves to the next highest point.
5. If it is less than Target sum, then this point is Stacked. A recursive call is made, whereby the target is reduced by this point and the list is curtailed, immediately preceding this point.
6. If the at any point the target sum can be found out, the entire stack can be extracted, which in the given code is extracted on the spreadsheet. The code keeps on working on the remainder value.
7. If in a particular recursive call, the target is not found, the last value from the Stack is removed.


' Code

Option Base 1
Private Stack() As Double
Private CurRow As Integer

Sub temp()
' Subroutine to do the preliminary work

Dim aList() As Double
Dim iListCount As Integer
Dim dTarget As Double
CurRow = 5
ReDim Stack(1)

' "rngList" is sorted in Ascending order
iListCount = Application.Range("rngList").Rows.Count
ReDim aList(iListCount)

dTarget = Range("rngTarget")

For n = 1 To UBound(aList, 1)
aList = Range("rngList").Cells(n, 1)
Next

SearchTarget dTarget, aList

End Sub

' Main Recursive Routine
Sub SearchTarget(dTarget As Double, aTargetList() As Double)
Dim aRevisedList() As Double, dRevisedTarget As Double

For n = UBound(aTargetList, 1) To 1 Step -1

Select Case aTargetList
Case Is = dTarget
For m = 1 To UBound(Stack, 1)
Cells(CurRow, m + 4) = Stack(m)
Next
'MsgBox ("Found!")
Cells(CurRow, m + 4) = dTarget 'the last value which is not Stacked
CurRow = CurRow + 1

Case Is< dTarget And n > 1
aRevisedList() = aTargetList
ReDim Preserve aRevisedList(n - 1)
dRevisedTarget = dTarget - aTargetList
ReDim Preserve Stack(UBound(Stack, 1) + 1)
Stack(UBound(Stack, 1)) = aTargetList
SearchTarget dRevisedTarget, aRevisedList
ReDim Preserve Stack(UBound(Stack, 1) - 1)
End Select
Next


End Sub

EDIT: I have posted revised and updated code on 25th August. - Sharad Kothari
This message was edited by Sharad Kothari on 2002-08-25 02:59