Problems & Puzzles: Puzzles

Puzzle 896. Optimal packing of a set of integers

Here we ask for an algorithm that produces an optimal answer. The original problem goes back up to 1979 (See Ref 3). But in this puzzle I use a numerical version of it.

Problem. "Given a set of decimal integers, what is the shortest string S of L decimal digits that contains all the integers as subsequences in the asked string." 

Example:

Set of integers: {123, 451, 46733}
Optimal string:  S = 46751233, L = 8.
Usually there are several distinct strings S with the same L minimal value.

Regarding the asked algorithm remember that we ask here for the optimal solution, that is to say, the minimal L for the S asked solution.

There are some other very simple algorithm & solutions, but these are not the optimal asked ones:

a) The worst solution LWS, is just to concatenate all the integers of the set. For this solution L is the sum of the lengths of all the integers.

b) A better solution LBS is to sum the counts of the distinct digits in each position of the integers. In this case, L is the sum of all the counts.

But none of these algorithms produce the optimal solution LOS, as you soon will discover.

Going back to the example shown above, LWS = 3+3+5 = 11, LBS = 2+3+3+1+1 = 10 but LOS = 8.

OK. Hands to work! Let's define three sets:

Set A: {4242064951, 5519385407, 6886477529, 3816749731, 4700006089, 9650560979, 4371455527, 5419320281, 8761823531, 3454277693}

Set B: {Prime numbers from 2 to 97}

Set C: {Prime numbers from 2 to 997}

Q1. Develop and send your algorithm description.

Q2. Send your best string S solutions for Sets A, B & C, respectively, as produced by your algorithm. [Starting point: my best solutions are L=45, 11, 21 for sets A, B & C, respectively]

References:

  1. PLANET PACKING by A. ROSS ECKLER (2001)
  2. PLANET PACKING REVISITED by DANA RICHARDS (2001)
  3. Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael Garey and David S. Johnson. Appendix A4.2, SR8, Shortest Common Super sequence.
 



 


Records   |  Conjectures  |  Problems  |  Puzzles