Results 1 to 20 of 20

Thread: Math help or special calculator needed

  1. #1
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    925
    Thanks
    57
    Thanked 116 Times in 93 Posts

    Math help or special calculator needed

    MY wife is sitting with some math problems at work that i cant igive her an easy solutions for som im helping somebody here might know a fast way to caluclate this or could make a special calculator for it

    The issues is she gets the info of a full paid amount but not what it is covering.
    she have aprox 3 different prices to combine to get that full prices and have to figure out what it can be so she can put it in the system somehow correctly

    if I'm not mistaken this is kinda like the traveling salesman thingy. anyway here is an real life example

    Full paid price 30987
    Unit 1 price 4537
    Unit 2 price 5792
    Unit 3 (no unit 3)


    What combinations of units got sold to reach that price ?

    Side info in case there a multiple answers the ones with the fewest units will always be correct.

  2. #2
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    Depending on the input restrictions a dynamic programming approach can give an answer in reasonable time. The requirement is a reasonably small universe of possible prices. Eg if possible prices are from 0.00 to 999.99 then there are 100000 different possible prices if the accuracy is to second digit after the point.

    I don't see any correlation with TSP, though.

  3. #3
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    925
    Thanks
    57
    Thanked 116 Times in 93 Posts
    The solutions always need to be whole numbers as a unit cannot be divided so it can be 3.4 of unit1 and 2.2 of unit2 which kinda restrict it a bit

    TSP is probably a far stretch. in this case it just a number of values that you need to add together to make an exact value. I was seeing TSP and every path as different values that had to be added together to reach the minimum distance (instead of an exact value) but there is more difference then that.

    if possible prices are from 0.00 to 999.99 then there are 100000 different possible prices if the accuracy is to second digit after the point.
    I'm not sure i follow the prices are given in each task so its the number of units that needs to be found that's the actual problem

  4. #4
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,257
    Thanks
    307
    Thanked 797 Times in 489 Posts
    That's the subset sum problem, which is NP-complete. You can't do much better than a brute force search.

  5. #5
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    For me, the problem looks more like http://en.wikipedia.org/wiki/Knapsack_problem and it is solvable by dynamic programming.

    I've coded a solution: http://ideone.com/1AzRnU
    It does scale the prices by 100 and converts them to integers. It will fail if price isn't integral after scaling by 100.
    Complexity is like O(price * scale factor * number of units).

    Input:
    <sum>
    <unit1>
    <unit2>
    <unit3>

    If some unit is not used, enter 0.
    Last edited by Piotr Tarsa; 12th September 2014 at 02:50.

  6. Thanks:

    SvenBent (12th September 2014)

  7. #6
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 72 Times in 56 Posts
    The general case sounds like subset sum, but if it's always three prices, it can be something like O(n^2) I think.

    The connection to TSP would be that subset sum and TSP are both NP-hard.
    Last edited by nburns; 12th September 2014 at 02:25.

  8. #7
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    The general case sounds like subset sum, but if it's always three prices, it can be something like O(n^2) I think.
    O(n ^ 2) but what does 'n' mean here?

    The connection to TSP would be that subset sum and TSP are both NP-hard.
    Far fetched.

    Sven:
    More "real life" examples would be useful. My solution is here (ie in previous post) so testing it on another input is trivial.

  9. #8
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    925
    Thanks
    57
    Thanked 116 Times in 93 Posts
    Woot thank you Piotr. ehrm how do i make this into a program though?

    I don't have any real life info at this point but i will get more.

  10. #9
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    Well, it is a program, reading from standard input and writing to standard output (ie a command line program), written in Scala. Running Scala programs can be problematic so I can rewrite it in eg Java.

  11. #10
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    925
    Thanks
    57
    Thanked 116 Times in 93 Posts
    If you could you get my blessing that would be so awesome and remove a lot of work stress for my wife

    I tried downloading scala thing and use scalac. It just didnt do anything


    I dont know if this help but their actually might be a max per units

    see RL example it goes like this
    a hospital bills an insurance for 5 days i type 1, 4 days of type2 and 12 days of type3
    the insurance does not pay the full amount but only a certain but unknown numbers of days we do however know the amount paid
    my wife now has to combine the prices of the 3 day types to adjust the bill so its fits the amount paid by the insurance

    off cause the easiest solutions would be for the insurance to report what they did and did not pay for but yeah.. insurance companies

    the amounts of different units is different from case to case
    the pricing on the units is different from case to case
    and the amount paid is different from case to case

    The numbers of units bill'ed is different from case to case
    Last edited by SvenBent; 12th September 2014 at 13:05.

  12. #11
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    Try doing:
    Code:
    scalac Main.scala
    scala Main
    Rename file before executing that.
    It should then wait for the 4 numbers (1 for sum, 3 for units), separated by newlines.

    I'm at work so I can't spend time on translating the program to Java now.
    Last edited by Piotr Tarsa; 12th September 2014 at 15:51.

  13. #12
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    925
    Thanks
    57
    Thanked 116 Times in 93 Posts
    ''"java"'' is not recognized as an internal or external command, operable program or batch file.

    what i did was i went to "The Scala Programming Language" site www.scala-lang.org/
    downloaded scala 2.11.2
    installed the msi package
    renamed you .scala file
    scalac main.scala
    and
    scalac main

    But just got the java issues message

  14. #13
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,572
    Thanks
    780
    Thanked 687 Times in 372 Posts
    i think it's the Linear Diophantine equation

  15. #14
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    SvenBent:
    You need Java runtime to run Java-based programs (I recommend disabling support for Java applets after install) and Scala is based on Java. Then you need to run 'scalac' to compile and 'scala' to run compiled program as I've outlined in previous post.
    Last edited by Piotr Tarsa; 12th September 2014 at 18:21.

  16. #15
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    925
    Thanks
    57
    Thanked 116 Times in 93 Posts
    Ty again. I found out i needed to manually install java 8 and the batch file from scala "works" as in it start and does something,
    Just weird that the java site want me to go down to java 7 v67 that i had before. or is this now 2 compete different things.


    Code:
    C:\Users\Admin\Desktop\Solver>scalac main.scala
    warning: there were two deprecation warnings; re-run with -deprecation for detai
    ls
    one warning found
    
    C:\Users\Admin\Desktop\Solver>scalac main.scala -deprecation
    main.scala:4: warning: method readLine in class DeprecatedConsole is deprecated:
     Use the method in scala.io.StdIn
        val sum = BigDecimal(Console.readLine()).*(100).toIntExact
                                     ^
    main.scala:5: warning: method readLine in class DeprecatedConsole is deprecated:
     Use the method in scala.io.StdIn
        val unitPrices = (0 until 3).map(_ => BigDecimal(Console.readLine()).*(100).
    toIntExact).filter(_ != 0)
                                                                 ^
    two warnings found

  17. #16
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 72 Times in 56 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    This seems like the right way to look at it. In other words, the problem is to solve an equation such as

    Code:
    q_0*p_0 + q_1*p_1 + q_2*p_2 = P
    for item quantities q_i, prices p_i, and total price P, with the constraint that all q_i must be integers and >= 0.

    The wikipedia page has a lot of useful info on it. Knowing that Fermat's last theorem is somehow a relative of this problem doesn't exactly breed confidence.
    Last edited by nburns; 13th September 2014 at 00:32.

  18. #17
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 72 Times in 56 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    O(n ^ 2) but what does 'n' mean here?
    n would be the number of different prices that may individually be added or not to the total. That was based on a misreading of the problem, I think, because there seem to only be a small number of prices (e.g. n~3), but each can be added zero or more times. I was thinking it was similar to some other problem I had read about.

    Far fetched.
    The actual subset sum problem is NP-hard (look it up). This could degrade into subset sum, but then it would tend to not be worthwhile to solve.

    Sven:
    More "real life" examples would be useful. My solution is here (ie in previous post) so testing it on another input is trivial.
    If I understand this right, it's a very practical kind of problem. It's like when when you learn the score in the middle of an American football game and try to deduce what combinations of field goals (3 pts) and touchdowns (7 pts) could have produced that score.*

    *I simplified things here a bit.
    Last edited by nburns; 13th September 2014 at 00:37.

  19. #18
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    Sven:
    So, after all, it works or not? Deprecation warnings aren't particularly dangerous and they don't stop program from compiling (well, only errors stop). So you should be able to run the sequence I've posted in post #11.

    Java site shows Java 7 because it turned out that Java 8 can cause compatibility problems (i.e. there are some widely used programs which aren't written in portable ways, compliant with specification of Java). But if it works, it's good.

    Also, maybe pay attention to letter case. I don't know if it plays a significant role under Windows but it's better to be safe than sorry.
    Last edited by Piotr Tarsa; 13th September 2014 at 00:56.

  20. #19
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 72 Times in 56 Posts
    Stuff like this ought to be a good candidate for writing in JavaScript, since it hardly demands any resources and should be easy. I've made lots of runnable HTML files, but they can cause problems with IE. jsfiddle should work.

    It would be nifty if this board let you post runnable scripts. I've never seen that feature on a forum, probably because it seems like a security risk. It wouldn't be if done right.
    Last edited by nburns; 13th September 2014 at 01:33.

  21. #20
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,497
    Thanks
    26
    Thanked 132 Times in 102 Posts
    I've improved the code (hope no bugs introduced) so that it prompts user to enter numbers.

    Code:
    import scala.io.StdIn
    
    object Main {
    
      def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
    
      def main(args: Array[String]): Unit = {
        println("Enter sum (followed by newline)")
        val sum = BigDecimal(StdIn.readLine()).*(100).toIntExact
        println("Enter three units (each followed by newline; enter 0 for unused unit)")
        val unitPrices = (0 until 3).map(_ => BigDecimal(StdIn.readLine()).*(100).toIntExact).filter(_ != 0)
        val pricesGcd = if (unitPrices.isEmpty) 0 else unitPrices.reduce(gcd)
        val unitPricesReduced = unitPrices.map(_ / pricesGcd)
        val dynArray = Array.ofDim[Int](sum / pricesGcd + 1, unitPrices.length)
        dynArray.foreach(row => row.indices.foreach(row(_) = -1))
        dynArray(0) = Array.fill[Int](unitPrices.length)(0)
        for ((row, rowIndex) <- dynArray.zipWithIndex;
              elemIndex <- row.indices) {
          val unitPrice = unitPricesReduced(elemIndex)
          if (rowIndex >= unitPrice) {
            val upperElem = dynArray(rowIndex - unitPrice)(elemIndex)
            if (upperElem >= 0) {
              row(elemIndex) = upperElem + 1
            }
          }
          if (elemIndex > 0) {
            val leftElem = row(elemIndex - 1)
            if (row(elemIndex) < 0 || (leftElem >= 0 && leftElem <= row(elemIndex))) {
              row(elemIndex) = leftElem
            }
          }
        }
        val counts = (0 until unitPrices.length).map(_ => 0).toArray
        var col = unitPrices.length - 1
        var row = sum / pricesGcd
        while (row > 0 && dynArray(row)(col) >= 0) {
          val elem = dynArray(row)(col)
          if (col > 0 && elem == dynArray(row)(col - 1)) {
            col -= 1
          } else if (row >= unitPricesReduced(col) && elem == dynArray(row - unitPricesReduced(col))(col) + 1) {
            counts(col) += 1
            row -= unitPricesReduced(col)
          } else {
            throw new Error
          }
        }
        if (dynArray(row)(col) >= 0) {
          print(f"${sum / 100.0}%1.2f = ")
          println(counts.zipWithIndex.map {
            case (count, index) => f"$count%d * ${unitPrices(index) / 100.0}%1.2f"
          }.mkString(" + "))
          println(if (sum == counts.zip(unitPrices).map{case (a, b) => a * b}.sum) "sum correct" else "sum incorrect")
        } else {
          println("No solution")
        }
      }
    }
    Save at Main.scala and run as described in post #11.


    Sample output:
    Code:
    Enter sum (followed by newline)
    342.25
    Enter three units (each followed by newline; enter 0 for unused unit)
    32.01
    0.01
    64
    342,25 = 0 * 64,00 + 10 * 32,01 + 2215 * 0,01
    sum correct
    Code:
    Enter sum (followed by newline)
    35.23
    Enter three units (each followed by newline; enter 0 for unused unit)
    53.53
    3.53
    22.2
    No solution

Similar Threads

  1. command-line calculator for Windows?
    By Alexander Rhatushnyak in forum The Off-Topic Lounge
    Replies: 5
    Last Post: 29th January 2012, 23:40
  2. the latest rec math contest is just starting
    By willvarfar in forum The Off-Topic Lounge
    Replies: 0
    Last Post: 15th March 2010, 00:12
  3. Seeks special version of RZM
    By SvenBent in forum Data Compression
    Replies: 0
    Last Post: 13th July 2009, 10:03
  4. Precomp Help needed please
    By Rusty_v in forum Data Compression
    Replies: 2
    Last Post: 8th July 2009, 17:16
  5. Searching for special file generator
    By nimdamsk in forum Data Compression
    Replies: 5
    Last Post: 19th March 2009, 01:33

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •