Re: minimum change digit factor computation

user923005 wrote:
Alexander Higgins wrote:
I am trying to write a computer program to do this, and math is not my
strong suit.

I am given a string of DIGITS from 0 to 50 characters long who values
when multiplied together are supposed to equal VALUE. I need to
calculate the minimum number of DIGITS that need to be changed to make
the equation true.

Example

DIGITS: 123
VALUE: 24

Answer: 1 (change the one to a six)

DIGITS:132456765434132524562
VALUE:0

Answer:1 - (change on digit to a zero)


The DIGITS can be up to 50 characters long.
Value can be an integer between 0 an 2^63-1 and contains no leading
zeros

If there is no solution I need to return -1 (ie 9^digits.length <
value)

I am trying solve the equation as follows:

I factor the the value in prime factors less than 10

while VALUE mod 2 =0
twos = twos +1
value = value/2

while VALUE mod 3 =0
threes = threes +1
value = value/3

while VALUE mod 5 =0
fives = fives +1
value = value/5

while value mod 7 =0
sevens = sevens +1
value = value /7

if twos and threes and fives and sevens = 0 or i > 0 then return -1

This gives me a string of factors ie for 12 - 223

I then go through the digits and get a string of factors
for example if digits is 145890 - > 0122222335

From here I cancel out the factors in each and come up with the number
of digits that need to be changed
in th above example
Digits 145890
Value: 12
Answer: 4
--1 does not have to be changed
--4 (22) matches 22 from our value factors, does not have to be changed
-5 needs to be changed to a 1
-8 needs to be changed to a 1
-9 needs to be changed to a 1
-0 need to be changed to 3 ( the last factor required in the value
factors to match)

I also sort the factors from highest to lowest before balancing out the
equation


Here is my problem:

If I am given
Digits:824 -->factors 222222
Value:8 -->factors 222

My equation will select the 8 (222) and mark the 2 and four as needed
to be changed.

This is on a smaller basis, but when dealing with larger numbers such
as
digits:123456789012345678901234567890
Value: 89373934605167493120

It starts to get confusing as whether to select an 8 (222) four (22) 2
(2) 6 (23) 9(33) or 3 (3)

Am I barking up the wrong tree with my approach here?? Is there an
algorithm or formula to figure this out??
Again, math is not my strong point so thanks in advance for any help.
It is appreciated.

One thing you can do to detect NO SOLUTION VALUEs is to factor out
multipliers of 2,3,5,7 from VALUE.
Because of the formulation of the problem, the answer must be composed
entirely of those prime factors (or equal zero). If you have removed
all factors of 2,3,5,7 and have something left greater than 9, it is NO
SOLUTION.

Once you have a list of factors from VALUE, then simply compute the
edit distance between your string of factors and the string you were
given.
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

You can sort both strings before the edit distance computation, because
multiplication is commutative.
If you have too many characters, you can change those which initially
do no match and are in excess to 1.

Not sure if it is optimal, but I guess it will be pretty hard to beat.

I should mention that 2*2, 2*3 and 3*3 can all be used to consume 2
factors at once if that is an advantage.
You could make a nested loop to consider all of those possibilities,
though it would chew into efficiency mightily.
You can probably make educated guesses, based on the length of the
input string and of the factor string to find out if combining is going
to improve the solution.

You could quickly figure out how many combination factors are possible
by doing mod with 4,6,9 to reduce the force needed to plow through the
loops.

.

Relevant Pages

  • Re: MAX-FLOAT-DIGITS
    ... a usable string when flag2=false ... ... There is no easy way to determine the maximum number of usable digits ... If u is greater than zero the character string shall consist ... consist of MAX-FLOAT-DIGITS graphic characters left-justified ...
    (comp.lang.forth)
  • MAX-FLOAT-DIGITS
    ... a usable string when flag2=false ... ... There is no easy way to determine the maximum number of usable digits ... If u is greater than zero the character string shall consist ... consist of MAX-FLOAT-DIGITS graphic characters left-justified ...
    (comp.lang.forth)
  • Re: How to convert extra long strings into their equivalent Hex Strings in VBA (Word 2K)
    ... numbers (upto 18 digits max) into its equivalent Hex String ... Public Function ExpressServiceCode(ByVal ServiceTag As String) As String ... 'the number dblTemp in the specified base, ... Dim lngTemp As Long ...
    (microsoft.public.vb.general.discussion)
  • Re: minimum change digit factor computation
    ... I am given a string of DIGITS from 0 to 50 characters long who values ... The DIGITS can be up to 50 characters long. ... multipliers of 2,3,5,7 from VALUE. ...
    (sci.math.num-analysis)
  • Re: BigNum -- Floating Point
    ... The 'N' is the number of decimal digits. ... The internal representation is really just a string of bits. ... the number of shifts for various multiples of ten: ... The 'exponent' is very closely related to ...
    (comp.programming)