stamps

Message

miskox · #1 Post by **miskox** » 24 Apr 2018 01:55

Hello!

Below is a program that calculates what stamps I need for a specific value (value entered is in cents! - this might probably easiy be changed: maybe: append "00" to the entered value, get tokens 1 and 2, delimited by a comma and then first two digits of token 2).
So the result is optimized to use the least number of stamps available:

So calling it with 203 returns:

Code: Select all

>stamps 203

1 X D
1 X B
1 X 0,20
1 X 0,05
2 X 0,02

We see that I need one piece of stamps D, B, 0.20 EUR, 0.05 EUR and two pieces of 0.02 EUR.

I am sure you experts would optimize it. So that is why I am posting it.

Variable 'stamp' represents stamp value in cents
Variable 'stampd' represents stamp value displayed (because some stamps are marked with letters).
Stamp values are sorted min..max.
Number of stamps available can change so new variables can be added when new stamps are availalbe so the program determines how many variables are defined.

Somehow I just couldn't make it better. I know you know some C (?) shortcuts to get remainders...

Code: Select all

@echo off
REM                  value;display
REM value in EUR cents!
set  stamp[1]=1
set stampd[1]=0,01

set  stamp[2]=2
set stampd[2]=0,02

set  stamp[3]=5
set stampd[3]=0,05

set  stamp[4]=10
set stampd[4]=0,10

set  stamp[5]=20
set stampd[5]=0,20

set  stamp[6]=40
set stampd[6]=A

set  stamp[7]=48
set stampd[7]=B

set  stamp[8]=100
set stampd[8]=C

set  stamp[9]=126
set stampd[9]=D

REM value in cents

set reqval=%1
if "%1"=="" set /p reqval=Enter required stamp value in EUR cents:

if "%reqval%"=="" echo Enter numeric value^>0&goto :EOF

set /a reqval=reqval * 1

if %reqval% LEQ 0 echo Enter numeric value^>0&goto :EOF

REM get number of tokens

set /a cntmax=1

:00
if defined stamp[%cntmax%] set /a cntmax+=1&goto :00

set /a cntmax-=1

for /L %%L in (%cntmax%,-1,1) do call :11 %%L

goto :EOF

:11
set num=%1

call set stamp_display=%%stampd[%num%]%%

set /a div=reqval/stamp[%num%]
set /a remainder=reqval - stamp[%num%] * div

if not "%div%"=="0" echo %div% X %stamp_display%

set /a reqval=remainder
goto :EOF

Thanks.
Saso

#2 Post by **aGerman** » 24 Apr 2018 03:59

I think you're looking for something like that:

Code: Select all

REM ...

REM get number of array elements
set /a cntmax=0
for /f %%i in ('set stamp[') do set /a cntmax+=1

REM calculate
setlocal EnableDelayedExpansion
for /L %%L in (%cntmax%,-1,1) do (
  set /a "div=reqval/stamp[%%L], reqval %%= stamp[%%L]"
  if !div! neq 0 echo !div! X !stampd[%%L]!
)

No labels needed.
The operator for the calculation of the remainder is % (which you have to double in a batch script). Used in
set /a "div=reqval/stamp[%%L], reqval %%= stamp[%%L]"

Steffen

miskox · #3 Post by **miskox** » 24 Apr 2018 05:31

Well...wow. Thanks Steffen. I knew you experts can do it in a more efficient way.

Saso

#4 Post by **Aacini** » 24 Apr 2018 07:04

This is the way I would do it:

Code: Select all

@echo off
setlocal EnableDelayedExpansion

set stamps="D=126" "C=100" "B=48" "A=40" "0,20=20" "0,10=10" "0,05=5" "0,02=2" "0.01=1"

set "reqval=%1"
for %%a in (%stamps%) do for /F "tokens=1,2 delims==" %%m in (%%a) do (
   set /A "div=reqval/%%n, reqval%%=%%n"
   if !div! neq 0 echo !div! X %%m
)

Antonio

#5 Post by **dbenham** » 24 Apr 2018 11:31

All of the listed solutions give the following for 60:

1 X B
1 X 0,10
1 X 0,02

The correct answer should be :

1 X A
1 X 0,20

Dave Benham

#6 Post by **aGerman** » 24 Apr 2018 12:28

You are right Dave. The purpose was to use the lowest number of stamps. Is it an Extremum Problem? My last math lesson was 30 years ago

Steffen

#7 Post by **Aacini** » 24 Apr 2018 13:14

Ops! You are right! I missed "the result is optimized to use the least number of stamps available" requirement.

Code: Select all

@echo off
setlocal EnableDelayedExpansion

set "stamps=D@126 C@100 B@48 A@40 0.20@20 0.10@10 0.05@5 0.02@2 0.01@1 "

echo Possible solutions:
set /A i=0, sol=0, min=999999
:nextSol
set /A i+=1, num=0, reqval=%1
for %%a in (%stamps%) do for /F "tokens=1,2 delims=@" %%m in ("%%a") do (
   set /A "div=reqval/%%n, reqval%%=%%n"
   if !div! neq 0 (
      set "sol[%i%]=!sol[%i%]! !div!@%%m
      set /A num+=div
   )
)
echo %i%- !num! stamps = !sol[%i%]!
if %num% lss %min% set /A min=num, sol=i
set "stamps=%stamps:* =%"
if defined stamps goto nextSol
echo/
echo Best solution: #%sol% = %min% stamps
for %%a in (!sol[%sol%]!) do for /F "tokens=1,2 delims=@" %%m in ("%%a") do (
   echo %%m X %%n
)

Output example:

Code: Select all

C:\Users\Antonio\Tests> test.bat 60
Possible solutions:
1- 3 stamps =  1@B 1@0.10 1@0.02
2- 3 stamps =  1@B 1@0.10 1@0.02
3- 3 stamps =  1@B 1@0.10 1@0.02
4- 2 stamps =  1@A 1@0.20
5- 3 stamps =  3@0.20
6- 6 stamps =  6@0.10
7- 12 stamps =  12@0.05
8- 30 stamps =  30@0.02
9- 60 stamps =  60@0.01

Best solution: #4 = 2 stamps
1 X A
1 x 0.20

Antonio

#8 Post by **dbenham** » 24 Apr 2018 13:48

@Aacini - Nope

Your result for 160:

Possible solutions:
1- 5 stamps = 1@D 1@0.20 1@0.10 2@0.02
2- 4 stamps = 1@C 1@B 1@0.10 1@0.02
3- 6 stamps = 3@B 1@0.10 1@0.05 1@0.01
4- 4 stamps = 4@A
5- 8 stamps = 8@0.20
6- 16 stamps = 16@0.10
7- 32 stamps = 32@0.05
8- 80 stamps = 80@0.02
9- 160 stamps = 160@0.01

Best solution: #2 = 4 stamps
1 X C
1 X B
1 X 0.10
1 X 0.02

Actual best solution for 160:
1 X C
1 X A
1 X 0.20

Your result for 460:

Possible solutions:
1- 8 stamps = 3@D 1@B 1@0.20 1@0.10 2@0.02
2- 7 stamps = 4@C 1@B 1@0.10 1@0.02
3- 13 stamps = 9@B 1@0.20 1@0.05 1@0.02 1@0.01
4- 12 stamps = 11@A 1@0.20
5- 23 stamps = 23@0.20
6- 46 stamps = 46@0.10
7- 92 stamps = 92@0.05
8- 230 stamps = 230@0.02
9- 460 stamps = 460@0.01

Best solution: #2 = 7 stamps
4 X C
1 X B
1 X 0.10
1 X 0.02

Actual best solution for 460:

2 X D
2 X C
2 X 0.02

or

4 X C
1 X A
1 X 0.20

The problem is not trivial

#9 Post by **Squashman** » 24 Apr 2018 13:58

Someone likes playing Devils Advocate.

#10 Post by **dbenham** » 24 Apr 2018 14:25

It is a lot easier than coming up with a solution

I'm not sure how to translate this into a calculus multi-variable max/min problem (or even if it is possible). Like aGerman, it has been nearly 40 years. And I don't think I would want to do that in batch anyway

In lieu of that, this seems like a permutation problem, but we don't want to compute all possible permutations. We want to identify as soon as possible when a given path is pointless.

The best I can easily do is quickly arrive at a maximal stamp quantity that is guaranteed to be less than or equal to the optimal number of stamps required:
find the largest stamp value that is <= the total value, and divide that into the total value. If there is no remainder, then we have the answer. If there is a remainder, then the optimal stamp quantity must be >= the integral count + 1.

We could start with the original algorithm to arrive at one local minima. We then begin looking for other permutations that use fewer stamps, presumably by decrementing the count of one of the higher values from the current "best" solution, and then solving for the remainder. As we are exploring permutations, the moment we exceed the prior "best" solution, we can backtrack. But we don't necessarily have to wait that long to backtrack. For any given partial solution, we can compute the remainder that has to be solved. We can then apply my earlier rule about the minimum number of stamps required to reach that remainder value. If that number + the number from the current partial solution exceeds the current "best", then we can backtrack.

Sorry, this is hard to describe

This problem definitely seems to lend itself to recursion.

Dave Benham

#11 Post by **penpen** » 24 Apr 2018 14:59

If i don't miss anything, then It should be possible to solve this using dynamic programming:

Code: Select all

@echo off
setlocal enableExtensions enableDelayedExpansion
for /f "delims==" %%a in ('2^>nul set "o["') do set "%%~a="

set "stamps=  D   C  B  A 0,20 0,10 0,05 0,02 0.01"
set "prices=126 100 48 40   20   10    5    2    1"
set "o[0]=0 0 0 0 0 0 0 0 0"

set /P "input=EUR in cents: "
set /A "euro=input"

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"
	for %%c in ("!index!") do for /f "tokens=1-9" %%0 in ("!o[%%~c]!") do (
		set /a "count[0]=%%~0, count[1]=%%~1, count[2]=%%~2, count[3]=%%~3, count[4]=%%~4, count[5]=%%~5, count[6]=%%~6, count[7]=%%~7, count[8]=%%~8"
		set /a "count[!bestPriceIndex!]+=1"
		set "o[%%~a]=!count[0]! !count[1]! !count[2]! !count[3]! !count[4]! !count[5]! !count[6]! !count[7]! !count[8]!"
		set "o[%%~a]"
	)
	set /a "index=%%~a-127"
	set "o[!index!]="
)

for /f "tokens=1-9" %%A in ("!stamps!") do for /f "tokens=1-9" %%a in ("!o[%euro%]!") do (
	echo(
	echo(Result:
	if not %%~a == 0 echo(%%~a x %%~A
	if not %%~b == 0 echo(%%~b x %%~B
	if not %%~c == 0 echo(%%~c x %%~C
	if not %%~d == 0 echo(%%~d x %%~D
	if not %%~e == 0 echo(%%~e x %%~E
	if not %%~f == 0 echo(%%~f x %%~F
	if not %%~g == 0 echo(%%~g x %%~G
	if not %%~h == 0 echo(%%~h x %%~H
	if not %%~i == 0 echo(%%~i x %%~I
) 

pause
goto :eof

penpen

Edit: Corrected "price[" to "count[".

#12 Post by **dbenham** » 24 Apr 2018 15:54

Impressive

Now I have to see if I can figure out how your code works

#13 Post by **Aacini** » 24 Apr 2018 23:34

dbenham wrote: ↑
24 Apr 2018 13:48
@Aacini - Nope

Your result for 460:

Possible solutions:
1- 8 stamps = 3@D 1@B 1@0.20 1@0.10 2@0.02
2- 7 stamps = 4@C 1@B 1@0.10 1@0.02
3- 13 stamps = 9@B 1@0.20 1@0.05 1@0.02 1@0.01
4- 12 stamps = 11@A 1@0.20
5- 23 stamps = 23@0.20
6- 46 stamps = 46@0.10
7- 92 stamps = 92@0.05
8- 230 stamps = 230@0.02
9- 460 stamps = 460@0.01

Best solution: #2 = 7 stamps
4 X C
1 X B
1 X 0.10
1 X 0.02

Actual best solution for 460:

2 X D
2 X C
2 X 0.02

or

4 X C
1 X A
1 X 0.20

The problem is not trivial

Your first best solution is wrong. It gives 456, not 460...

Ok. This is my second attempt:

Code: Select all

@echo off
setlocal EnableDelayedExpansion

set "stamps=D@126 C@100 B@48 A@40 0.20@20 0.10@10 0.05@5 0.02@2 0.01@1 "

set "reqval=%1"
set "stampsA="
for %%a in (%stamps%) do for /F "tokens=1,2 delims=@" %%m in ("%%a") do (
   if %%n leq %reqval% set "stampsA=!stampsA!%%a "
)

echo Possible solutions:
set /A i=0, min=999999
set "prevSol="
for /F "tokens=1*" %%a in ("%stampsA%") do set "stamp1=%%a" & set "stampsB=%%b"

:nextSol
set /A i+=1, reqval=%1
for /F "tokens=1,2 delims=@" %%m in ("%stamp1%") do (
   set /A "num=reqval/%%n, reqval%%=%%n"
   set "sol[%i%]=!num!@%%m"
)
for %%a in (%stampsB%) do for /F "tokens=1,2 delims=@" %%m in ("%%a") do (
   set /A "div=reqval/%%n, reqval%%=%%n"
   if !div! neq 0 (
      set "sol[%i%]=!sol[%i%]! !div!@%%m
      set /A num+=div
   )
)
if "!sol[%i%]!" neq "%prevSol%" (
   set "prevSol=!sol[%i%]!"
   echo %i%- !num! stamps = !sol[%i%]!
   if %num% leq %min% (
      if %num% lss %min% (
         set /A min=num, sol=i
      ) else (
         set "sol=!sol! %i%
      )
   )
) else (
   set /A i-=1
)
set "stampsB=%stampsB:* =%"
if defined stampsB goto nextSol

set "stampsA=%stampsA:* =%"
if defined stampsA (
   for /F "tokens=1*" %%a in ("%stampsA%") do set "stamp1=%%a" & set "stampsB=%%b"
   if defined stampsB goto nextSol
)

echo/
echo Best solution(s) with %min% stamps
for %%i in (%sol%) do (
   echo/
   echo Number %%i:
   for %%a in (!sol[%%i]!) do for /F "tokens=1,2 delims=@" %%m in ("%%a") do (
      echo %%m X %%n
   )
)

Output example for 460:

Possible solutions:
1- 8 stamps = 3@D 1@B 1@0.20 1@0.10 2@0.02
2- 6 stamps = 3@D 2@A 1@0.02
3- 8 stamps = 3@D 4@0.20 1@0.02
4- 12 stamps = 3@D 8@0.10 1@0.02
5- 20 stamps = 3@D 16@0.05 1@0.02
6- 44 stamps = 3@D 41@0.02
7- 85 stamps = 3@D 82@0.01
8- 7 stamps = 4@C 1@B 1@0.10 1@0.02
9- 6 stamps = 4@C 1@A 1@0.20
10- 7 stamps = 4@C 3@0.20
11- 10 stamps = 4@C 6@0.10
12- 16 stamps = 4@C 12@0.05
13- 34 stamps = 4@C 30@0.02
14- 64 stamps = 4@C 60@0.01
15- 13 stamps = 9@B 1@0.20 1@0.05 1@0.02 1@0.01
16- 14 stamps = 9@B 2@0.10 1@0.05 1@0.02 1@0.01
17- 16 stamps = 9@B 5@0.05 1@0.02 1@0.01
18- 23 stamps = 9@B 14@0.02
19- 37 stamps = 9@B 28@0.01
20- 12 stamps = 11@A 1@0.20
21- 13 stamps = 11@A 2@0.10
22- 15 stamps = 11@A 4@0.05
23- 21 stamps = 11@A 10@0.02
24- 31 stamps = 11@A 20@0.01
25- 23 stamps = 23@0.20
26- 46 stamps = 46@0.10
27- 92 stamps = 92@0.05
28- 230 stamps = 230@0.02

Best solution(s) with 6 stamps

Number 2:
3 X D
2 X A
1 X 0.02

Number 9:
4 X C
1 X A
1 X 0.20

Antonio

#14 Post by **dbenham** » 25 Apr 2018 05:26

Aacini wrote: ↑
24 Apr 2018 23:34

dbenham wrote: ↑
24 Apr 2018 13:48
Actual best solution for 460:

2 X D
2 X C
2 X 0.02

or

4 X C
1 X A
1 X 0.20
Your first best solution is wrong. It gives 456, not 460...

Sorry, I was sloppy and used a value of D=128 instead of D=126

Aacini wrote: ↑
24 Apr 2018 23:34
Ok. This is my second attempt:

I did some comparisons with penpen's code, and your result for 3315 is sub-optimal:

Aacini 3315 solution:
Best solution(s) with 31 stamps

Number 1:
26 X D
1 X 0.20
1 X 0.10
1 X 0.05
2 X 0.02

penpen 3315 solution:
25 x D
1 x C
1 x A
1 x 0,20
1 x 0,05

I believe we can compute the maximum optimum number of each stamp for any arbitrary value:

1 x 0.01 because 2 will be replaced by 1 x 0.02
2 x 0.02 because 3 will be replaced by 1 x 0.05, 1 x 0.01
1 x 0.05 because 2 will be replaced by 1 x 0.10
1 x 0.10 because 2 will be replaced by 1 x 0.20
1 x 0.20 because 2 will be replaced by 1 x A
2 x A because 3 will be replaced by 1 x C, 1 x 0.20
4 x B because 5 will be replaced by 1 x C, 1 x A
2 x C because 3 can be replaced by 2 x D, 1 x B : or 12 x C because 13 will be replaced by 10 x D, 1 x A
infinite x D

I'm less sure about this statement - Based on some empirical probing using penpen's solution, there may be a maximum total value at which point the maximum number of optimal 0.02 is 1. If I am correct, then there is probably a similar threshold for A, and maybe B and C.

Dave Benham

#15 Post by **dbenham** » 25 Apr 2018 10:24

I believe I have an efficient solution that quickly computes an optimal solution for any positive integral value supported by SET /A.

Some values have multiple optimal solutions. My code finds the optimal solution with the highest possible number of D.

My code is dependent on one additional postulate - For any given current remainder, compute the highest denomination that is <= remainder. The optimal count for this denomination will either be remainder/denomination, or (remainder/denomination)-1. If I am wrong on this, then the algorithm will have to change. I was wrong - thanks penpen. Fixed at viewtopic.php?f=3&t=8517&start=15#p56532

Code: Select all

@echo  off
setlocal enableDelayedExpansion

set /a target=%1

:: 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 !target! 1 solution
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%"
  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!"
    )
  )
)
( endlocal
  set /a %3.count=%A.count%
  set "%3.list=%A.list%"
)
exit /b 0

In very limited testing, I always got the same value as penpen. However, my code is much faster

Dave Benham

DosTips.com

stamps

stamps

Re: stamps

Re: stamps

Re: stamps

Re: stamps

Re: stamps

Re: stamps

Re: stamps

Re: stamps

Re: stamps

Re: stamps

Re: stamps

Re: stamps

Re: stamps

Re: stamps