View topic - Math Algorithm Problem (Other). Very Hard • AutoHotkey Community

View unanswered posts | View active topics

Board index » AutoHotkey » Support

All times are UTC [ DST ]

Math Algorithm Problem (Other). Very Hard

Page 1 of 1

[ 15 posts ]

Print view | E-mail friend

Previous topic | Next topic

Author

Message

NiJo

Post subject: Math Algorithm Problem (Other). Very Hard

Posted: February 22nd, 2007, 3:50 am

Joined: November 12th, 2005, 10:25 pm
Posts: 73

I need an algorithm (AHK code) that does the following:

I have 4 entrance values: a,b,c,d. (Desired)
I have 4 variables: k,l,m,n. (Maximuns)
I have another one, T. (Total Maximum)

I want the result to be 4 variables, w,x,y,z, has closest has possible to a,b,c,d, and close to each other too.

The wanted result has changed, see my next post.

Restraints:
w<k; x<l; y<m and d<n. (outputs smaller than Maximuns')
w+x+y+z<T. (Total output smaller than Total Maximum)
That's it...

You can think about this as with Money.
4 ppl want to withdraw money. their bank accounts contains the Maximuns. The Bank only has T (Total Maximum). How much should each of them get? (The bank shouldn't limit more one than the other, I mean, if A wants 100 and B 200, and they have money in Bank, can't give [33,66]: Should give [x;x] or [100;x€[100,200]]).

Example:
[100,200,500,1000]
[400,800,400,1000]
[800]
Result should be:
[100,200,250,250]

[200,200,200,200]
[0,100,1000,200]
[500]
Result should be:
[0,100,200,200]

Right now I have one aproximately correct:

Code:

    if (T<(a+b+c+d))
        Over:=(a+b+c+d)-T
    
    O1:=a-k
    if O1<0
        O1=0
    O2:=b-l
    if O2<0
        O2=0
    O3:=c-m
    if O3<0
        O3=0
    O4:=d-n
    if O4<0
        O4=0

    if (Over>O1+O2+O3+O4)
    {
        excessRatio:=Ceil((Over-(O1+O2+O3+O4))/4)
        O1+=excessRatio
        O2+=excessRatio
        O3+=excessRatio
        O4+=excessRatio
    }
    w:=a-O1
    x:=b-O2
    y:=c-O3
    z:=d-O4

    msgbox %w%,%x%,%y%,%z%

(This code gives negative numbers under certain situations...)
Examples:

Code:

[200,200,200,200]
[0,100,1000,200]
[500]
Result is:
[0,100,200,200]
CORRECT

[100,200,400,200]
[200,200,200,200]
[500]
Result is:
[50,150,150,150]
WRONG. Should be:
[100,133,133,133]

Last edited by NiJo on February 22nd, 2007, 3:47 pm, edited 3 times in total.

Top

toralf

Post subject:

Posted: February 22nd, 2007, 8:29 am

Joined: January 31st, 2005, 9:50 am
Posts: 3910
Location: Bremen, Germany

just a brain dump, not tested

Code:

s = wxyz

w := a < k ? a : k
x := b < l ? b : l
y := c < m ? c : m
z := d < n ? d : n

Loop {
    delta := T - (w + x + y + z)
    If (delta >= 0)
        Break
    delta *= -1
    i = 4
    Loop, Parse, s
        If (%A_LoopField% < T / 4){
            delta += T / 4 - %A_LoopField%
            i-- 
          }
    delta /= i  
    Loop, Parse, s
        %A_LoopField% -= %A_LoopField% > T / 4 ? delta : 0
    
  }

_________________
Ciao
toralf

Top

toralf

Post subject:

Posted: February 22nd, 2007, 9:08 am

Joined: January 31st, 2005, 9:50 am
Posts: 3910
Location: Bremen, Germany

tested:

Code:

msgbox, % func(100,200,500,1000,400,800,400,1000,800)
msgbox, % func(200,200,200,200,0,100,1000,200,500)
msgbox, % func(100,200,400,200,200,200,200,200,500)

func(a,b,c,d,k,l,m,n,T){
    s = wxyz
    
    w := a < k ? a : k
    x := b < l ? b : l
    y := c < m ? c : m
    z := d < n ? d : n
    
    delta := (w + x + y + z) - T
    If (delta <= 0)
        Return w " " x " " y " " z
    
    List =%w%`n%x%`n%y%`n%z%
    Sort, List, N R
    StringSplit, List, List, `n
    
    d1 := (delta > List1 - List2) ? List1 - List2 : delta
    
    If (d1 <> delta){
        d2 := ( delta - d1 > 2 * ( List2 - List3 ) ) ? List2 - List3 : ( delta - d1 ) / 2 
        d1 += d2 
      } 
    
    If (d1 + d2 <> delta){
        d3:= ( delta - d1 - d2 > 3 * ( List3 - List4 ) ) ? List3 - List4 : ( delta - d1 - d2 ) / 3 
        d2 += d3 
        d1 += d3 
      } 
    
    If (d1 + d2 + d3 <> delta){
        d4 := (delta - d1 - d2 - d3) / 4
        d3 += d4 
        d2 += d4 
        d1 += d4 
      }
    
    Loop, Parse, s
      {
        var := A_LoopField
        Loop, 4
            If (List%A_Index% = %var%){
                %var% -= d%A_Index%
                List%A_Index% = xxxxxxx
                break
              }
      }
    Return w " " x " " y " " z
  } 

_________________
Ciao
toralf

Top

polyethene

Post subject:

Posted: February 22nd, 2007, 12:47 pm

Joined: August 11th, 2004, 1:47 am
Posts: 5346
Location: UK

Here's a different algorithm:

Code:

MsgBox, % Sn(100, 200, 500, 1000, 400, 800, 400, 1000, 800)
MsgBox, % Sn(200, 200, 200, 200, 0, 100 ,1000, 200, 500)
MsgBox, % Sn(100, 200, 400, 200, 200, 200, 200, 200, 500) 

Sn(a1, a2, a3, a4, b1, b2, b3, b4, t, x = 0) {
   Loop, 4
      x++, t -= c%x% := a%x% - (b%x% > a%x% ? a%x% - b%x% : 0)
   t *= -1
   Loop, 4
      x := A_Index, i := c%x% - a%x%, c%x% -= j := (i > 0) ? i : 0, t -= j
   t //= 4, i := 0
   Loop
      If i = 4
         Return, c1 . "," . c2 . "," . c3 . "," . c4
      Else x := 4 - Mod(A_Index, 4), c%x% -= j := c%x% > t ? t : 0, i += j = t
}

I'm sure Laszlo will have 2^32 ways of optimizing that but it works as is

_________________
GitHub • Scripts • IronAHK • Contact by email not private message.

Top

NiJo

Post subject:

Posted: February 22nd, 2007, 1:33 pm

Joined: November 12th, 2005, 10:25 pm
Posts: 73

@Toralf.:
Cool...

Second one works nice. Thanks

Edited Twice: Yep, It's correct

@Titan:
I must be a real dumbass... I don't understand your code, and it doesn't work in your cases... msgbox 2 gives ppl money they don't have, and msgbox 3 isn't "close to each other"
Why is the "t -= c%x%" ?? Cs variables ain't got a value yet, do they?

Well, after thinking for some time... I'm not sure if this is the correct, lol... Wasn't it better if the bank Owed all the ppl the same amount at the end?
I mean:
[100,200,250,250]
[200,200,200,200]
[0,100,1000,200]
[500]
Result should be:
[37,87,187,187] So they are missing:
[63,63,63,63] (Missing to the requested, not to bank)

[100,200,500,1000]
[400,800,400,1000]
[800]
Result should be:
[0,0,150,650] So they are missing:
[100,200,350,350] This should be the returned value.

Can anyone write this algo?

I will change yours if it won't, but function needs to know w,x,y,z at a certain time, and needs to return the missing values.

I'll see if I can change Toralf's to do this

Thanks a lot guys

Last edited by NiJo on February 22nd, 2007, 3:47 pm, edited 1 time in total.

Top

nick (n-l-i)

Post subject:

Posted: February 22nd, 2007, 2:03 pm

just another variation:

Code:

MsgBox, % Calc("[100,200,500,1000]", "[400,800,400,1000]", "[800]")
MsgBox, % Calc("[200,200,200,200]", "[0,100,1000,200]" , "[500]")
MsgBox, % Calc("[100,200,400,200]", "[200,200,200,200]", "[500]")
Exit

Calc(a_in, m_in, t_in)
{
   t_in := RegexReplace(t_in, "[\[\]]")
   StringSplit, a, a_in, `,, []
   StringSplit, m, m_in, `,, []
   If ((a0 <> 4) Or (a0 <> m0)) {
      Return, "ERROR"
   }

   Loop, % a0
   {
      If (a%A_Index% > m%A_Index%) {
         a%A_Index% := m%A_Index%
      }
   }

   t := (a1 + a2 + a3 + a4) < t_in ? (a1 + a2 + a3 + a4) : t_in
   t /= a0

   i := a0
   l := a1 . "|" . a2 . "|" . a3 . "|" . a4
   Sort, l, D| N
   Loop, Parse, l, |
   {
      If (A_LoopField < t) {
         i--
         t += Round((t - A_LoopField) / i, 2)
      }
   }

   Loop, % a0
   {
      x%A_Index% := a%A_Index% < t ? a%A_Index% : Round(t)
   }

   Return % x1 . "," . x2 . "," . x3 . "," . x4
}

Top

nick (n-l-i)

Post subject:

Posted: February 22nd, 2007, 5:38 pm

Why not percentaged rates?

Code:

MsgBox, % Calc("[100,200,250,250]", "[100,200,200,250]", "[500]")
MsgBox, % Calc("[100,200,500,1000]", "[400,800,400,1000]", "[800]")
MsgBox, % Calc("[200,200,200,200]", "[0,100,1000,200]" , "[500]")
MsgBox, % Calc("[100,200,400,200]", "[200,200,200,200]", "[500]")
Exit

Calc(a_in, m_in, t_in)
{
   t := 0
   t_in := RegexReplace(t_in, "[\[\]]")
   StringSplit, a, a_in, `,, []
   StringSplit, m, m_in, `,, []
   If ((a0 <> 4) Or (a0 <> m0)) {
      Return, "ERROR"
   }
   ; limit to the personal maximum
   Loop, % a0
   {
      If (a%A_Index% > m%A_Index%) {
         a%A_Index% := m%A_Index%
      }
      t += a%A_Index%
   }
   ; if necessary, limit to total maximum (percentaged rates)
   If (t > t_in) {
      Loop, % a0
      {
         a%A_Index% := Round(a%A_Index% / t * t_in)
      }
   }
   
   Return % a1 . "," . a2 . "," . a3 . "," . a4
}

Top

polyethene

Post subject:

Posted: February 22nd, 2007, 5:49 pm

Joined: August 11th, 2004, 1:47 am
Posts: 5346
Location: UK

NiJo wrote:

msgbox 2 gives ppl money they don't have, and msgbox 3 isn't "close to each other"

I don't get it, #3 is all the same and the sum of #2 is lower than T.. but if toralfs version works I guess it don't matter. Thanks for trying anyway.

_________________
GitHub • Scripts • IronAHK • Contact by email not private message.

Top

NiJo

Post subject:

Posted: February 22nd, 2007, 5:50 pm

Joined: November 12th, 2005, 10:25 pm
Posts: 73

Percentaged rates is a possibility that I thought before.
Maybe to the Bank Related Problem it would make sense, but not for what I need.
It needs to have an "almost constant" "missing value"...

Last edited by NiJo on February 22nd, 2007, 5:57 pm, edited 1 time in total.

Top

NiJo

Post subject:

Posted: February 22nd, 2007, 5:55 pm

Joined: November 12th, 2005, 10:25 pm
Posts: 73

@Titan: Your msgbox #2, function(200, 200, 200, 200, 0, 100 ,1000, 200, 500) returns: 125,125,125,125. How's that possible if ppl #1 and #2 only have 0 and 100 in bank, respectively? and msgbox #3 returns 100,100,200,100, and not 100,133,133,133.

You'r right, Toralf's worked, but now I'm trying to do a diferent one. I explained in my 2nd Post. I want the Missing Values to be closer as possible, and not the Withdrawing Values.

Top

nick

Post subject:

Posted: February 23rd, 2007, 8:14 am

Joined: August 24th, 2005, 5:29 pm
Posts: 549
Location: Berlin / Germany

Something like this?

Code:

MsgBox, % Calc("[100,200,250,250]", "[200,200,200,200]", "[500]")
MsgBox, % Calc("[100,200,250,250]", "[200,200,200,250]", "[500]")
MsgBox, % Calc("[100,200,250,250]", "[0,200,200,250]", "[500]")
MsgBox, % Calc("[100,200,500,1000]", "[400,800,400,1000]", "[800]")
MsgBox, % Calc("[100,200,500,1000]", "[400,800,500,1000]", "[800]")
MsgBox, % Calc("[100,200,500,2000]", "[400,800,400,2000]", "[800]")
Exit

Calc(a_in, m_in, t_in)
{
   t_in := RegexReplace(t_in, "[\[\]]")
   StringSplit, a, a_in, `,, []
   StringSplit, m, m_in, `,, []
   If ((a0 <> 4) Or (a0 <> m0)) {
      Return, "ERROR"
   }

   ; limit to the personal maximum
   Loop, % a0
   {
      If (a%A_Index% > m%A_Index%) {
         a%A_Index% := m%A_Index%
      }
   }

   i := a0
   t := a1 + a2 + a3 + a4
   If (t > t_in) {
      Loop
      {
         b := True
         d := Round((t - t_in) / i)
         Loop, % a0
         {
            If ((a%A_Index% > 0) And (a%A_Index% <= d)) {
               t -= a%A_Index%
               a%A_Index% := 0
               i--
               b := False
            }
         }
         If ((b) Or (t <= t_in)) {
            Break
         }
      }
      d := Round((t - t_in) / i)
      Loop, % a0
      {
         If (a%A_Index% > 0) {
            a%A_Index% -= d
         }
      } 
   }

   Return % a1 . "," . a2 . "," . a3 . "," . a4
}

_________________
nick :wink:

Top

toralf

Post subject:

Posted: February 23rd, 2007, 9:03 am

Joined: January 31st, 2005, 9:50 am
Posts: 3910
Location: Bremen, Germany

NiJo wrote:

I want the Missing Values to be closer as possible, and not the Withdrawing Values.

What do you want to have close?
What difference of which entities should be as small as possible?

The withdraw from the desired amount? Or the withdraw from the maximum? Or the withdraw from the either the amount or the maximum (which ever is lower)?

Sorry, but you have to be very specific to solve this math. When done, it is pretty straight forward to code it.

_________________
Ciao
toralf

Top

toralf

Post subject:

Posted: February 23rd, 2007, 9:14 am

Joined: January 31st, 2005, 9:50 am
Posts: 3910
Location: Bremen, Germany

NiJo wrote:

Wasn't it better if the bank Owed all the ppl the same amount at the end?
I mean:
[100,200,250,250]
[200,200,200,200]
[0,100,1000,200]
[500]
Result should be:
[37,87,187,187] So they are missing:
[63,63,63,63] (Missing to the requested, not to bank)

I do not understand, in the beginning there are three arrays of 4 numbers (That is one too much)? Which is what?
If the last is the maximun, then the result is wrong, since the first person can't withdraw 37 coins, since its maximum is 0.

NiJo wrote:

[100,200,500,1000]
[400,800,400,1000]
[800]
Result should be:
[0,0,150,650] So they are missing:
[100,200,350,350] This should be the returned value.

This is in oposition to what you stated before: "if the bank Owed all the ppl the same amount". It is not even that the people will have nearly the same balance on their accounts at the end of the withdraw. So what exactly are you trying to calculate?

_________________
Ciao
toralf

Top

toralf

Post subject:

Posted: February 23rd, 2007, 9:24 am

Joined: January 31st, 2005, 9:50 am
Posts: 3910
Location: Bremen, Germany

Another question: I assume it is always lower then the maximum. But is it possible that the withdraw is higher then the desired amount? If so, the desired amount is obsolet, since the desired to have a low difference (of waht ever) is high then following the desired amount. Hence the desired amount values can be neglected.

_________________
Ciao
toralf

Top

NiJo

Post subject:

Posted: February 23rd, 2007, 5:19 pm

Joined: November 12th, 2005, 10:25 pm
Posts: 73

@Nick: Almost that, the only problem is the testing for a<m at the beginning. We need it, but it's changing the values before the calc

Well, I can live with that

Actually I'm using your RatioPercentage based algo.

@Toralf: My first example was mistyped... sorry to make you spend time with wrong presentations...
The correct was: (3rd 4-variables sequence shouldn't exist)

Code:

[100,200,250,250]
[200,200,200,200]
[500]
Result should be:
[37,87,187,187] So they are missing:
[63,63,63,63] ([b]Missing to the requested, not to bank[/b]) 

The Maximums aren't obsolete, they really are the maximums. But should only be considered "at the end"... I don't know how to explain better... The bank example isn't the right one to give. It would, if it was possible to ask for loans, but they are never accepted, lol. The "Missing" values are differences between the asked and the withdrawn... They should be closer to Each Other, the 4 ppl. The code is writable, but I needed one that was optimized.
And hey, I thought something like this would be enjoyably-done by some ppl

It is for me...
I'm using nicks#2 ratio based, and i think it's making the job

Thanks to all of you

Top

Page 1 of 1

[ 15 posts ]

Board index » AutoHotkey » Support

All times are UTC [ DST ]

Who is online

Users browsing this forum: 0x150||ISO, Alpha Bravo, KenC, Kgalv, Kirtman, kwfine, LazyMan, Yahoo [Bot] and 71 guests

You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum