Number packing with C#

Hello,

I’d like to pack an array of integers (which I’m calling ‘children’) into another integer (the ‘host’). The integers can be repeated. The goal is to pack as few integers into the host as possible.

The desired output is:

  1. an array of numbers outputting the number of times each ‘child’ integer has been ‘packed’ into the ‘host’ - the packCount
  2. an array of numbers outputting the remainders (modulos) after each ‘best’ integer has been ‘packed’ - the remainders

I have posted some code below, and the results I’m getting now. Is there a better way to achieve this in C#? I know that this doesn’t appear to have a Rhino application at first glance, but this is the beginning of a panelization routine I’m working towards.

        protected override Result RunCommand(RhinoDoc doc, RunMode mode)
        {
        int host = 27;
        var children = new RhinoList<int> { 32, 28, 7, 2, 1 };

        RhinoApp.WriteLine("Host: {0}", host);
        RhinoApp.WriteLine("Children: [{0}]", string.Join(", ", children));

        int x = 0;
        int y = 0;

        int j = 0;
        int k = 0;

        var packCount = new RhinoList<int>();
        var remainder = new RhinoList<int>();

        //clear children greater than host and add to lists

        for (var i = 0; i < children.Count; i++)
        {
            if (host < children[i])
            {
                packCount.Add(0);
                remainder.Add(0);
            }

        }

        //remove bad children
        children.RemoveRange(0, packCount.Count);

        //pack first child into host and add to list
        x = host % children[0];
        remainder.Add(x);

        y = (host - x) / children[0];
        packCount.Add(y);

        //pack remaining children into remainders and add to list

        for (var i = 1; i < children.Count; i++)

        {
            j = remainder.Last % children[i];
            k = (remainder.Last - j) / children[i];

            remainder.Add(j);
            packCount.Add(k);

        }

        //output results

        RhinoApp.WriteLine("Pack counts: [{0}]", string.Join(", ", packCount));

        RhinoApp.WriteLine("Remainders: [{0}]", string.Join(", ", remainder));

   

        return Result.Success;

Result:

Host: 27
Children: [32, 28, 7, 2, 1]
Pack counts: [0, 0, 3, 3, 0]
Remainders: [0, 0, 6, 0, 0]

Hello,

This looks like a variation on the change making problem and the most efficient solution is likely to involve dynamic programming, particularly if you want to go on to look at multiple different panel combinations…?

Graham,

Oh my, this is exactly what I’m trying to do. I didn’t realize it was this complex. The link you sent is great, but it will take some time for me to digest the code on that page and attempt to re-implement in C#.

I most definitely want to look a multiple panel configurations in the future.

Thanks for putting your finger on the problem for me.

Dan

Hello,

I have made the following console application to try and work through the logic here. This is working:

    using System;
    using System.Collections.Concurrent;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

namespace numberPacker
{
    class Program
    {
        static void Main(string[] args)
        {

            var remainders = new List<int> { 52 };
            var host = remainders[0];
            var children = new List<int>() { 22, 6, 3 };
            var packCount = new List<int>();
            

          
            for (var i = 0; i < children.Count; i++)
            {
                var modulo = remainders.LastOrDefault() % children[i];
                remainders.Add(modulo);
            }

            for (var i = 0; i < children.Count; i++)
            {
                var pack = (remainders[i] - remainders[i + 1]) / children[i];
                packCount.Add(pack);

            }

            remainders.RemoveAt(0);


            Console.WriteLine(@"Host: {0}", host);
            Console.WriteLine(@"Children: " + string.Join(",", children));

            Console.WriteLine(@"Pack counts: " + string.Join(",", packCount));
            Console.WriteLine(@"Remainders: " + string.Join(",", remainders));


        }
    }
}

The result is:

Host: 52
Children: 22,6,3
Pack counts: 2,1,0
Remainders: 8,2,2

Now I’m trying to implement this into a GH plugin with this code:

namespace packingPlugin
{
    public class packingPluginComponent : GH_Component
    {
        /// <summary>
        /// Each implementation of GH_Component must provide a public 
        /// constructor without any arguments.
        /// Category represents the Tab in which the component will appear, 
        /// Subcategory the panel. If you use non-existing tab or panel names, 
        /// new tabs/panels will automatically be created.
        /// </summary>
        public packingPluginComponent()
          : base("packingPlugin", "packNumbers",
              "",
              "Math", "Util")
        {
        }

        /// <summary>
        /// Registers all the input parameters for this component.
        /// </summary>
        protected override void RegisterInputParams(GH_Component.GH_InputParamManager pManager)
        {
            // Use the pManager object to register your input parameters.
            // You can often supply default values when creating parameters.
            // All parameters must have the correct access type. If you want 
            // to import lists or trees of values, modify the ParamAccess flag.
            

            pManager.AddIntegerParameter("Host", "H", "Host number", GH_ParamAccess.item, 45);
            pManager.AddIntegerParameter("Children", "C", "Child numbers", GH_ParamAccess.list);

            // If you want to change properties of certain parameters, 
            // you can use the pManager instance to access them by index:
            //pManager[0].Optional = true;
        }

        /// <summary>
        /// Registers all the output parameters for this component.
        /// </summary>
        protected override void RegisterOutputParams(GH_Component.GH_OutputParamManager pManager)
        {
            // Use the pManager object to register your output parameters.
            // Output parameters do not have default values, but they too must have the correct access type.

            pManager.AddIntegerParameter("Remainders", "Rem", "what remains", GH_ParamAccess.list);
            pManager.AddIntegerParameter("Pack counts", "Packs", "what is packed", GH_ParamAccess.list);

            // Sometimes you want to hide a specific parameter from the Rhino preview.
            // You can use the HideParameter() method as a quick way:
            //pManager.HideParameter(0);
        }

        /// <summary>
        /// This is the method that actually does the work.
        /// </summary>
        /// <param name="DA">The DA object can be used to retrieve data from input parameters and 
        /// to store data in output parameters.</param>
        protected override void SolveInstance(IGH_DataAccess DA)
        {
            // First, we need to retrieve all data from the input parameters.
            // We'll start by declaring variables and assigning them starting values.
            

            List<int> remainders = new List<int>();
            var host = 0;
            List<int> children = new List<int>();
            List<int> packCount = new List<int>();

            // Then we need to access the input parameters individually. 
            // When data cannot be extracted from a parameter, we should abort this method.
            
            if (!DA.GetData(0, ref host)) return;
            if (!DA.GetDataList(1, children)) return;

            // We should now validate the data and warn the user if invalid data is supplied.
           
            if (host <= 0)
            {
                AddRuntimeMessage(GH_RuntimeMessageLevel.Error, "Host must be bigger than or equal to one");
                return;
            }

            //do the work of finding the modulos

            var modulo = 0;

            for (var i = 0; i < children.Count; i++)
            {
                modulo = remainders.LastOrDefault() % children[i];
                
            }

            remainders.Add(modulo);

            for (var i = 0; i < children.Count; i++)
            {
                var pack = (remainders[i] - remainders[i + 1]) / children[i];
                packCount.Add(pack);

            }

            remainders.RemoveAt(0);

            DA.SetDataList(0, remainders);
            DA.SetDataList(1, packCount);

        }

        /// <summary>
        /// The Exposure property controls where in the panel a component icon 
        /// will appear. There are seven possible locations (primary to septenary), 
        /// each of which can be combined with the GH_Exposure.obscure flag, which 
        /// ensures the component will only be visible on panel dropdowns.
        /// </summary>
        public override GH_Exposure Exposure
        {
            get { return GH_Exposure.primary; }
        }

        /// <summary>
        /// Provides an Icon for every component that will be visible in the User Interface.
        /// Icons need to be 24x24 pixels.
        /// </summary>
        protected override System.Drawing.Bitmap Icon
        {
            get
            {
                // You can add image files to your project resources and access them like this:
                //return Resources.IconForThisComponent;
                return null;
            }
        }

        /// <summary>
        /// Each component must have a unique Guid to identify it. 
        /// It is vital this Guid doesn't change otherwise old ghx files 
        /// that use the old ID will partially fail during loading.
        /// </summary>
        public override Guid ComponentGuid
        {
            get { return new Guid("98c532fe-f3ff-4560-af44-40b5d87c9bd0"); }
        }
    }
}

But I’m getting this error:

Is there something wrong with how I have registered inputs/outputs?

Help appreciated!

Dan

I don’t understand your problem but I see some error in SolveInstance().

        var modulo = 0;

        for (var i = 0; i < children.Count; i++)
        {
            modulo = remainders.LastOrDefault() % children[i]; // Why you reasign var modulo?
            
        }

        remainders.Add(modulo); // remainders.Count will always be 1.

        for (var i = 0; i < children.Count; i++) 
        {
            var pack = (remainders[i] - remainders[i + 1]) / children[i]; // remainders[1] out of range.
            packCount.Add(pack);

        }

Maybe you’ve forgotten

remainders.Add(modulo);

in the first loop?

Hello,

Thanks for the reply, that’s an error!

I’ve cleaned things up, but I’m still getting the same message in GH. @DavidRutten could you help with this one?

var host = 0;
            List<int> remainders = new List<int>(host);
            List<int> children = new List<int>();
            List<int> packCount = new List<int>();
            var modulo = 0;

            // Then we need to access the input parameters individually. 
            // When data cannot be extracted from a parameter, we should abort this method.

            if (!DA.GetData(0, ref host)) return;
            if (!DA.GetDataList(1, children)) return;

            // We should now validate the data and warn the user if invalid data is supplied.
           
            if (host <= 0)
            {
                AddRuntimeMessage(GH_RuntimeMessageLevel.Error, "Host must be bigger than or equal to one");
                return;
            }

            //do the work of finding the modulos

            for (var i = 0; i < children.Count; i++)
            {
                modulo = remainders.LastOrDefault() % children[i];
                remainders.Add(modulo);

            }

            

            for (var i = 0; i < children.Count; i++)
            {
                var pack = (remainders[i] - remainders[i + 1]) / children[i];
                packCount.Add(pack);

            }

            remainders.RemoveAt(0);

            DA.SetDataList(0, remainders);
            DA.SetDataList(1, packCount);

Your error is in

var host = 0;
List<int> remainders = new List<int>(host);

remainders is an empty list. Make sure you make a valid data assignment before you proceed with the rest of your code.

Ps: Its always good practice to use the debugger in VS to see were your error is.

The remainders[i+1] throw the error bc i+1 is out of range when i is the last of the loop. If children.Count and remainder.Count is for example 3, i can be 0, 1 and 2 to access its values, but that i+1 when i is 2 gives 3, and since index starts from 0, you are going out of range in remainders.

To fix it, you can wrap it doing (i+1)%remainders.Count (i+1 will be 0 en this case) but I don’t know if this have sense to your problem, or set a step less in the loop with i < children.Count-1. But for your case, add a first value properly in remainders, using this sintax: new List< int>() { host }.