Story of a simple task

There was this on-line challange where you were supposed to calculate the cargo that could fit into your cargo space. Task, itself, was not complicated, however my ideas about solving it, were jumping from technology to technology. From purely functional, via object based to ancient, structural based, approach.

At first, I though – “Why not use Scala or something? All this new functional fuss. It will be super cool”. I have created all possible lists of cargo with toSet and subsets, ordered lists by cargo size and price. Then, I have thrown away cargo that doesn’t fit, and taken head. At this point, I could have easily refer to List of tuples that define the best match. Nice!

def foldTuples(l: List[List[(Int,Int)]]): List[(Int,Int,Int)] = {
  def _foldTuples(res: List[(Int,Int,Int)], rem: List[List[(Int,Int)]], idx: Int):
  List[(Int,Int,Int)] = rem match {
    case Nil => res
    case (h:List[(Int, Int)])::tail => _foldTuples(
      res:+h.foldLeft(
        (0,0,idx)){(acc,iter) => (acc._1 + iter._1, acc._2 + iter._2, idx)}, 
      tail, 
      idx+1)
  }
  _foldTuples(List.empty[(Int,Int, Int)], l, 0)
}

var a = List((2,26),(6,30),(4,28),(4,36),(3,30)).
  toSet[(Int,Int)].subsets.map(_.toList).toList;
a(foldTuples(a).filter(_._1 <= 12).sortWith(_._2 > _._2).head._3)

But hey! Maybe OO based approach would be better here? I could have created Ship with a Cargo bay. Cargo bay could hold different kinds of Cargo represented by yet another class. This way, process of calculating cargo size would be hidden. It could be delegated to Cargo bay itself. In case like this, all I need to do to get my stuff packed is to ask the Ship: “-Hey, Falcon, here is the cargo. Will it fit in?”

import java.util.ArrayList;

public class Ship {

  public Ship(int cargoSize) {
    bay = new CargoBay(cargoSize);
  }

  public void fillCargoBay(ArrayList<Cargo> cargo) {
    bay.fill(cargo);
  }

  public void printCargo() {
    bay.printCargo();
  }

  public static void main(String[] arg) {
    ArrayList<Cargo> boxes = new ArrayList<>();
    boxes.add(new Cargo(2, 26));
    boxes.add(new Cargo(6, 30));
    boxes.add(new Cargo(4, 28));
    boxes.add(new Cargo(4, 36));
    boxes.add(new Cargo(3, 30));

    Ship millenniumFalcon = new Ship(12);
    millenniumFalcon.fillCargoBay(boxes);
    millenniumFalcon.printCargo();
  }

  private CargoBay bay;
}

class CargoBay {
  public CargoBay(int maxCapacity) {
    this.maxCapacity = maxCapacity;
  }

  public void fill(ArrayList<Cargo> cargo) {
    ArrayList<ArrayList> allSubSets = generateAllSubSets(cargo);

    Cargo currentMax = calculateCapacityOfCargo(this.cargo);

    for(ArrayList list : allSubSets) {
      Cargo nextCargo = calculateCapacityOfCargo(list);
      if(nextCargo.size <= maxCapacity && nextCargo.price > currentMax.price) {
        this.cargo = list;
        currentMax = nextCargo;
      }
    }
  }

  public void printCargo() {
    for(Cargo c : this.cargo) {
      System.out.println("size: " + c.size + " price: " + c.price);
    }
  }

  private Cargo calculateCapacityOfCargo(ArrayList<Cargo> cargo) {
    Cargo result = new Cargo(0, 0);
    for (Cargo c : cargo) {
      result.size += c.size;
      result.price += c.price;
    }
    return result;
  }

  private ArrayList<ArrayList> generateAllSubSets(ArrayList<Cargo> cargo) {

    ArrayList<ArrayList> cargoLists = new ArrayList<>();

    int n = cargo.size();

    for (int i = 0; i < (1 << n); i++) {
      ArrayList<Cargo> newCargo = new ArrayList<>();
      for (int j = 0; j < n; j++) {
        if ((i & (1 << j)) > 0) {
          newCargo.add(cargo.get(j));
        }
      }
      cargoLists.add(newCargo);
    }
    return cargoLists;
  }

  private ArrayList<Cargo> cargo = new ArrayList<Cargo>();
  private int maxCapacity = 0;
}

class Cargo {
  public Cargo(int size, int price) {
    this.price = price;
    this.size = size;
  }

  public int size;
  public int price;
}

Nah, man. OO based result is way too long. But, wait! Maybe there is a different way? Maybe I can do it nasty, structural, way? Is it possible to create something that will fit inside one Tweet? Yes it is. Here comes the code. Simple, small, and very elegant ;) It has recursion, have you noticed? Thus, it must be a sophisticated one ;)

crg[]={2,26,6,30,4,28,4,36,3,30,12},mp,mm;
int l(i,c,p,m){return (i<5)
?(l(i+1,c,p,m)&&l(i+1,c+(i*2)[crg],p+(i*2+1)[crg],m|=(1<<i)))
:((p>mp && c<=10[crg])?((mp=p)&&(mm=m)):1);}
int main(){l(0,0,0,0);
for(int i=0;i<5;i++)mm&(1<<i)
?printf("%d,%d\n",(i*2)[crg],(i*2+1)[crg])
:0;}

And it fits in a one Tweet ;)