stamps

Discussion forum for all Windows batch related topics.

Moderator: DosItHelp

Message
Author
miskox
Posts: 553
Joined: 28 Jun 2010 03:46

Re: stamps

#16 Post by miskox » 25 Apr 2018 11:02

Wow!

Thank you all! Thanks Dave for finding that 'mistake'.

At first it looked like an easy task and it turned out to be a great exercise.

Thank you all.

Saso

dbenham
Expert
Posts: 2461
Joined: 12 Feb 2011 21:02
Location: United States (east coast)

Re: stamps

#17 Post by dbenham » 25 Apr 2018 12:22

I investigated the performance, and I'm pretty sure the maximum number of CALLs to :solve must be <=111 for any given number.

I tested all values from 1 to 4000, and the maximum number of CALLs was 55, and the vast majority required between 30 and 50 calls.

I looked at the results of running 1 to 4000, and I no longer believe there is a maximum value for which the optimum solution requires 2 x 0.02.

It would be tedious, but it shouldn't be too hard to modify my algorithm to be purely iterative, as one big set of nested FOR loops, without any need for SETLOCAL. I'm sure it would improve performance significantly. But I don't think it would be worth while given that 3905 requiring 55 CALLs takes just 0.4 seconds. Even if there is a value that requires 111 CALLs, it should still take less than 1 second.


Dave Benham

penpen
Expert
Posts: 1991
Joined: 23 Jun 2013 06:15
Location: Germany

Re: stamps

#18 Post by penpen » 25 Apr 2018 17:00

You must have missed one or more optimization steps; some examples:
260 requires 5 stamps:
----------------------------------
2 x D
1 x 0.05
1 x 0.02
1 x 0.01

An optimal solution requires 4 stamps:
2 x C
1 x A
1 x 0,20


288 requires 5 stamps:
----------------------------------
1 x D
1 x C
1 x A
1 x 0.20
1 x 0.02

An optimal solution requires 4 stamps:
2 x C
1 x B
1 x A


296 requires 5 stamps:
----------------------------------
2 x D
1 x A
2 x 0.02

An optimal solution requires 4 stamps:
2 x C
2 x B


penpen

dbenham
Expert
Posts: 2461
Joined: 12 Feb 2011 21:02
Location: United States (east coast)

Re: stamps

#19 Post by dbenham » 25 Apr 2018 22:20

Thanks penpen. The failure comes from my erroneous 2nd postulate where I only allow a count of n or n-1 for any given denomination. I had to change the algorithm to allow each denomination to test more than 2 counts.

It was surprisingly easy. I didn't spend much time trying to optimize the implementation of the modified algorithm. For example, it often performs a GOTO before it checks if the current count is positive - if I checked the count first then I could avoid a GOTO. The corrective change definitely slows everything down a bit, but it is still plenty fast :D

Code: Select all

@echo  off
setlocal enableDelayedExpansion

:: Define stamps
set /a n=0
for %%A in (D@126@0x7FFFFFFF C@100@2 B@48@4 A@40@2 0.20@20@1 0.10@10@1 0.05@5@1 0.02@2@2 0.01@1@1) do (
  for /f "delims=@ tokens=1-3" %%B in ("%%A") do (
    set /a n+=1
    set "stamp.!n!.label=%%B"
    set /a "stamp.!n!.value=%%C, stamp.!n!.max=%%D"
  )
)

call :solve %1 1 solution
echo(
if %solution.count% == 1 (echo %1 requires 1 stamp:) else echo %1 requires %solution.count% stamps:
echo ----------------------------------
for %%S in (%solution.list%) do for /f "delims=@ tokens=1,2" %%A in ("%%S") do echo %%A x !stamp.%%B.label!

exit /b

:solve  Target  StampIndex  ReturnVar
setlocal
set /a "count=%1/stamp.%2.value, remainder=%1%%stamp.%2.value, solution.count+=count, next=%2+1"
if %count% gtr !stamp.%2.max! exit /b 1
if %remainder% equ 0 (
  endlocal
  set /a %3.count=%count%
  set "%3.list=%count%@%2"
  exit /b 0
)
call :solve %remainder% %next% A || exit /b 1
set /a A.count+=count
if %count% gtr 0 set "A.list=%count%@%2 %A.list%"
:decrement
if %count% gtr 0 (
  set /a "count-=1, remainder+=stamp.%2.value"
  call :solve !remainder! %next% B && (
    set /a B.count+=count
    if !B.count! lss !A.count! (
      set /a A.count=B.count
      if !count! gtr 0 (set "A.list=!count!@%2 !B.list!") else set "A.list=!B.list!"
    )
    goto :decrement
  )
)
( endlocal
  set /a %3.count=%A.count%
  set "%3.list=%A.list%"
)
exit /b 0
Dave Benham

miskox
Posts: 553
Joined: 28 Jun 2010 03:46

Re: stamps

#20 Post by miskox » 26 Apr 2018 00:20

@Dave: Thanks! Great!

Your code is too complicated to understand. Could you please make a list of stamps (values/display) more user friendly so new stamps could be added or removed with ease.

One more thing: how can I use comma as a decimal point? If I replace '0.20' with '0,20' I get divide by zero. Also this message is displayed:

Code: Select all

******  B A T C H   R E C U R S I O N  exceeds STACK limits ******
Recursion Count=649, Stack Usage=90 percent
******       B A T C H   PROCESSING IS   A B O R T E D      ******
Thanks.
Saso

penpen
Expert
Posts: 1991
Joined: 23 Jun 2013 06:15
Location: Germany

Re: stamps

#21 Post by penpen » 26 Apr 2018 03:15

@Dave:
I've tested the values to 3000, and still found errors:
344 requires 6 stamps:
----------------------------------
2 x D
1 x B
1 x A
2 x 0.02

An optimal solution requires 5 stamps:
2 x C
3 x B

470 requires 7 stamps:
----------------------------------
3 x D
1 x B
1 x A
2 x 0.02

An optimal solution requires 6 stamps:
1 x D
2 x C
3 x B

If i see it right, then they all have the same structure, :
344+n*126 requires 6+n stamps:; n >= 0
----------------------------------
(2+n) x D
1 x B
1 x A
2 x 0.02

An optimal solution requires 5+n stamps:
n x D
2 x C
3 x B


penpen

dbenham
Expert
Posts: 2461
Joined: 12 Feb 2011 21:02
Location: United States (east coast)

Re: stamps

#22 Post by dbenham » 26 Apr 2018 15:14

miskox wrote:
26 Apr 2018 00:20
Your code is too complicated to understand. Could you please make a list of stamps (values/display) more user friendly so new stamps could be added or removed with ease.

One more thing: how can I use comma as a decimal point? If I replace '0.20' with '0,20' I get divide by zero.
My new code at the bottom of this post is a step in the direction of making it easy to modify the list of stamps. It now supports commas.

But the Max and Continue columns are pre-computed optimizations that enable my code to consistently come up with an optimal solution in under 1.5 seconds, no matter how large the target value. I don't have a simple way to derive those constants. Over the next few days I'll try to use a derivative of penpen's code to derive Max and Continue constants for each stamp denomination.
penpen wrote:
26 Apr 2018 03:15
I've tested the values to 3000, and still found errors:
344 requires 6 stamps:
----------------------------------
2 x D
1 x B
1 x A
2 x 0.02

An optimal solution requires 5 stamps:
2 x C
3 x B

470 requires 7 stamps:
----------------------------------
3 x D
1 x B
1 x A
2 x 0.02

An optimal solution requires 6 stamps:
1 x D
2 x C
3 x B

If i see it right, then they all have the same structure, :
344+n*126 requires 6+n stamps:; n >= 0
----------------------------------
(2+n) x D
1 x B
1 x A
2 x 0.02

An optimal solution requires 5+n stamps:
n x D
2 x C
3 x B
Thanks again. I see the source of my problem.

My stamp.n.max value represents the largest possible optimized count value for stamp n. I build a solution by starting with the largest denomination, and working toward the smallest. When I divide the target (remainder) by a denomination value, I quit (backtrack) if the count is greater than the max. But that strategy fails to take into account the fact that the sum of the optimized smaller denominations may exceed the denomination in question.

My new algorithm adds a second threshold called Continue that represents the largest acceptable initial count for that initial division. If the count exceeds the Continue threshold, then I backtrack. The Continue value is always >= the Max value. To compute Continue, I sum up Max * Value for all lesser denominations, and then divide by my current denomination value. I take this result and add it to the Max to get Continue. I'm pretty sure my computed Continue is sometimes larger than it needs to be, but that is OK. I want to be sure that my algorithm always gives a true optimized solution.

I'm feeling much more confident that I have finally reached the goal :roll: :D

Of course the changes slow things down a bit yet again. For "small" numbers my code is no faster than yours (penpen).

But my code has a maximum possible number of computations, regardless how big the target value gets. I have still yet to see any target value take longer than 1.5 seconds.

Code: Select all

@echo  off
setlocal enableDelayedExpansion

set /a "infinite=0x7FFFFFFF"

:: Define stamps
set /a n=0
for %%A in (
%= Label Value     Max       Continue =%
  "D       126  %infinite%  %infinite%"
  "C       100      2           5"
  "B        48      4           6"
  "A        40      2           2"
  "0,20     20      1           1"
  "0,10     10      1           1"
  "0,05      5      1           1"
  "0,02      2      2           2"
  "0,01      1      1           1"
) do (
  for /f "tokens=1-4 delims= " %%B in ("%%~A") do (
    set /a n+=1
    set "stamp.!n!.label=%%B"
    set /a "stamp.!n!.value=%%C, stamp.!n!.max=%%D, stamp.!n!.continue=%%E"
  )
)

call :solve %1 1 solution
echo(
if %solution.count% == 1 (echo %1 requires 1 stamp:) else echo %1 requires %solution.count% stamps:
echo ----------------------------------
for %%S in (%solution.list%) do for /f "delims=@ tokens=1,2" %%A in ("%%S") do echo %%A x !stamp.%%B.label!

exit /b

:solve  Target  StampIndex  ReturnVar
setlocal
set /a "count=%1/stamp.%2.value, remainder=%1%%stamp.%2.value, next=%2+1"
if %count% gtr !stamp.%2.continue! exit /b 1
if %count% gtr !stamp.%2.max! set /a "count=stamp.%2.max, remainder=%1-stamp.%2.value*count"
if %remainder% equ 0 (
  endlocal
  set /a %3.count=%count%
  set "%3.list=%count%@%2"
  exit /b 0
)
call :solve %remainder% %next% A || exit /b 1
set /a A.count+=count
if %count% gtr 0 set "A.list=%count%@%2 !A.list!"
:decrement
if %count% gtr 0 (
  set /a "count-=1, remainder+=stamp.%2.value"
  call :solve !remainder! %next% B && (
    set /a B.count+=count
    if !B.count! lss !A.count! (
      set /a A.count=B.count
      if !count! gtr 0 (set "A.list=!count!@%2 !B.list!") else set "A.list=!B.list!"
    )
    goto :decrement
  )
)
( endlocal
  set /a %3.count=%A.count%
  set "%3.list=%A.list%"
)
exit /b 0

Dave Benham

penpen
Expert
Posts: 1991
Joined: 23 Jun 2013 06:15
Location: Germany

Re: stamps

#23 Post by penpen » 27 Apr 2018 04:05

dbenham wrote:
26 Apr 2018 15:14
I'm feeling much more confident that I have finally reached the goal :roll: :D
I've tested your results up to least common multiple of the cost values (25200), and found no errors.


Because this computational problem is kind of cyclic (∀ n ∈ ℕ: Result(n+25200) == Result(n+25200)+"200 x D"), i think your algorithm is error free now.

@Aacini:
I've tested your algorithm, it gives suboptimal results:
108 requires 4 stamps:
----------------------------------
1 X C
1 X 0.05
1 X 0.02
1 X 0.01

An optimal solution requires3 stamps:
1 x B
1 x A
1 x 0,20

234 requires 5 stamps:
----------------------------------
1 X D
1 X C
1 X 0.05
1 X 0.02
1 X 0.01

An optimal solution requires 4 stamps:
1 x D
1 x B
1 x A
1 x 0,20

244 requires 5 stamps:
----------------------------------
1 X D
2 X B
1 X 0.20
1 X 0.02

An optimal solution requires 4 stamps:
1 x C
3 x B

Beside this the result for the value 1 is buggy.


penpen

dbenham
Expert
Posts: 2461
Joined: 12 Feb 2011 21:02
Location: United States (east coast)

Re: stamps

#24 Post by dbenham » 28 Apr 2018 20:59

As promised, here is a version that allows you to easily modify the list of available stamps. Instructions for how to modify the list are at the bottom of the code.

It is currently configured and optimized to quickly compute solutions for the original list of stamps. But the first time you run with a modified list it will use a modified version of penpen's code to compute the new optimizations and update the list accordingly - this takes significant time. Subsequent runs will then be fast.

Code: Select all

@echo  off
setlocal enableDelayedExpansion

:Load stamp definitions at bottom of file
set /a "big=0x7FFFFFFF"
for /f "tokens=1-5 delims=: " %%A in ('findstr /rc:"^::: " "%~f0" ^| findstr /n "^"') do (
  if "%%E" == "" goto :Compute 
  set "stamp.%%A.label=%%B"
  set /a "stamp.%%A.value=%%C, stamp.%%A.max=%%D, stamp.%%A.continue=%%E"
)

call :Solve %1 1 solution
echo(
if %solution.count% == 1 (echo %1 requires 1 stamp:) else echo %1 requires %solution.count% stamps:
echo ----------------------------------
for %%S in (%solution.list%) do for /f "delims=@ tokens=1,2" %%A in ("%%S") do (
  set "count=      %%A"
  echo !count:~-6! x !stamp.%%B.label!
)

exit /b

:Solve  Target  StampIndex  ReturnVar
setlocal
set /a "count=%1/stamp.%2.value, remainder=%1%%stamp.%2.value, next=%2+1"
if %count% gtr !stamp.%2.continue! exit /b 1
if %count% gtr !stamp.%2.max! set /a "count=stamp.%2.max, remainder=%1-stamp.%2.value*count"
if %remainder% equ 0 (
  endlocal
  set /a %3.count=%count%
  set "%3.list=%count%@%2"
  exit /b 0
)
call :Solve %remainder% %next% A || exit /b 1
set /a A.count+=count
if %count% gtr 0 set "A.list=%count%@%2 !A.list!"
:decrement
if %count% gtr 0 (
  set /a "count-=1, remainder+=stamp.%2.value"
  call :Solve !remainder! %next% B && (
    set /a B.count+=count
    if !B.count! lss !A.count! (
      set /a A.count=B.count
      if !count! gtr 0 (set "A.list=!count!@%2 !B.list!") else set "A.list=!B.list!"
    )
    goto :decrement
  )
)
( endlocal
  set /a %3.count=%A.count%
  set "%3.list=%A.list%"
)
exit /b 0

:Compute stamp optimizations
setlocal
echo Computing stamp optimizations...
set "o[init]="
set "prices="
for /f "tokens=1-3 delims=: " %%A in ('findstr /rc:"^::: " "%~f0" ^| findstr /n "^"') do (
  set "stamp.%%A.label=%%B"
  set /a "stamp.%%A.value=%%C, maxN=%%A"
  set "o[init]=!o[init]! 0"
  set "prices=!prices! %%C"
)
set /a "prev=0"
for /l %%N in (%maxN% -1 2) do (
  set /a "euro=value=stamp.%%N.value, max=1"
  call :Compute2 %%N
)

:: Write optimizations to file
set "stamp.1.max=^!big^!"
set "stamp.1.continue=^!big^!"
>"%~f0.new" (
  findstr /v /rc:"^::: " "%~f0"
  for /l %%N in (1 1 %maxN%) do (
    set    "label=!stamp.%%N.label!      "
    set    "value=      !stamp.%%N.value!"
    set      "max=      !stamp.%%N.max!"
    set "continue=      !stamp.%%N.continue!"
    echo ::: !label:~0,6! !value:~-6! !max:~-6! !continue:~-6!
  )
)
move /y "%~f0.new" "%~f0" >nul
endlocal
echo(
findstr /rc:"^::: " "%~f0"
echo Done
goto :Load

:Compute2  StampIndex
set /a "euro+=value, max+=1"
set "o[0]=!o[init]!"
echo %1:%max%:%euro%
for /l %%a in (1, 1, %euro%) do (
  set /a "priceIndex=-1, bestPriceIndex=-1, bestPrice=0"
  set /a "bestCount=euro+1"
  for %%b in (%prices%) do (
    set /a "priceIndex+=1, index=%%~a-%%~b"
    if 0 leq !index! (
      for %%c in ("!index!") do set /a "count=!o[%%~c]: =+!+1"
      if !count! LSS !bestCount! (
        set /a "bestCount=count, bestPrice=%%~b, bestPriceIndex=priceIndex"
      )
    )
  )
  set /a "index=%%~a-bestPrice, n=0"
  set "o[%%~a]="
  for %%c in ("!index!") do for %%A in (!o[%%~c]!) do (
    set /a "cnt=%%A + ^!(bestPriceIndex-n), n+=1"
    set "o[%%~a]=!o[%%~a]! !cnt!"
  )
  set /a "index=%%~a-stamp.1.value-1"
  set "o[!index!]="
)
set /a "N=0"
for %%C in (!o[%euro%]!) do (
  set /a "N+=1"
  if !N! == %%N if %%C == !max! (goto :Compute2) else goto :break
)
:break
set /a "stamp.%N%.max=(max-=1), stamp.%N%.continue=max+prev/stamp.%N%.value, prev+=stamp.%N%.value*max"
echo !stamp.%N%.label!  !stamp.%N%.value!  !stamp.%N%.max!  !stamp.%N%.continue!
exit /b


:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
::  STAMP DEFINITIONS:
::
::  When modifying the definitions, only the Label and Value should be populated.
::  The Max and Continue will be computed automatically. The rows must be sorted
::  by Value descending. The last row must have a value of 1. Each row must begin
::  with exactly three colons and a space.
::
::  Label   Value    Max Continue
::  ------ ------ ------ --------
::: D         126  !big!  !big!
::: C         100      2      5
::: B          48      4      6
::: A          40      2      3
::: 0,20       20      1      2
::: 0,10       10      1      2
::: 0,05        5      1      2
::: 0,02        2      2      2
::: 0,01        1      1      1

Dave Benham

miskox
Posts: 553
Joined: 28 Jun 2010 03:46

Re: stamps

#25 Post by miskox » 08 May 2018 07:15

Sorry for a short delay (I was offline for more than a week).

Dave! Great!

I just have another challenge:

can available quantity of stamps be added?

For example:

Maybe I don't have stamp 'C' (1.00 EUR) at hand so optimal solution for 0.60 EUR of C+0.20 cannot be used. So next best solution might work.

Thanks.
Saso

penpen
Expert
Posts: 1991
Joined: 23 Jun 2013 06:15
Location: Germany

Re: stamps

#26 Post by penpen » 16 May 2018 03:04

If you have limit stamps, then there is no guarantee, that a solution exists.
Dave's algorithm relies on the fact that the precomputed optimizations have solutions.

So i don't think that adding such limitations to his algorithm is an easy task if it is possible at all:
Limiting a NP-complete optimization problem (NP-cop) often results in an EXPTIME-complete optimization problem (EXPTIME-cop);
Although it actually isn't proven it is assumed by the majority of mathematicians that EXPTIME-cops are a real superset of NP-cops.

You might still use dynamic programming, and just add a test, if you have exceeded the stamp limit.

penpen

Post Reply