#Language : Java #Score : 555 533

Language : Java

Score : 555 533

#Language : Java #Score : 555

import java.awt.Color;
import java.awt.Graphics;
import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import javax.imageio.ImageIO;

public class Packer {
    public static void main(String[] args) throws Exception {
        long t1 = System.currentTimeMillis();

        int width = Integer.valueOf(args[0]);
        List<Item> itemList = new ArrayList<Item>();
        for (int i = 1; i < args.length; i++) {
            itemList.addAll(getItems(ImageIO.read(new File(args[i]))));
        }

        File outputFile = new File("output.png");
        if (outputFile.exists()) {
            outputFile.delete();
        }
        outputFile.createNewFile();

        ImageIO.write(pack(itemList, width), "PNG", outputFile);
        long t2 = System.currentTimeMillis();
        System.out.println("Finished in " + (t2 - t1) + "ms");
    }

    private static BufferedImage pack(List<Item> itemList, int width) {
        System.out.println("Packing " + itemList.size() + " items");
        Collections.sort(itemList, new Comparator<Item>() {

            @Override
            public int compare(Item o1, Item o2) {
                return o1.area < o2.area ? 1 : (o1.area > o2.area ? -1
                        : (o1.perimiter < o2.perimiter ? 1
                                : (o1.perimiter > o2.perimiter ? -1 : 0)));
            }
        });
        Packing packing = new Packing(width);
        PackedItem.Rotation[] widthRots = { PackedItem.Rotation.ZERO,
                PackedItem.Rotation.ONE_EIGHTY };
        PackedItem.Rotation[] heightRots = { PackedItem.Rotation.NINETY,
                PackedItem.Rotation.TWO_SEVENTY };
        int count = 0;
        for (Item item : itemList) {
            count++;
            int minSize = Math.min(item.width, item.height);
            int maxSize = Math.max(item.width, item.height);
            int x = 0;
            int y = minSize;
            int rot = 0;
            PackedItem.Rotation[] rots = widthRots;
            if (item.width > item.height) {
                rots = heightRots;
            }
            boolean rotsSwitched = false;

            PackedItem packedItem = new PackedItem(item, rots[rot], x, y);
            System.out.format("Packing item %d which is %d by %d\n", count,
                    item.width, item.height);
            while (!packing.isValidWith(packedItem)) {
                if (rot == 0) {
                    rot = 1;
                } else {
                    rot = 0;
                    if (x + minSize >= width) {
                        x = 0;
                        y++;
                        if (!rotsSwitched
                                && y + maxSize > packing.height + minSize) {
                            rotsSwitched = true;
                            if (item.width > item.height) {
                                rots = widthRots;
                            } else {
                                rots = heightRots;
                            }
                            y = minSize;
                        }
                    } else {
                        x++;
                    }
                }
                packedItem.set(x, y, rots[rot]);
            }
            packing.addItem(packedItem);
            System.out.format("Packed item %d\n", count);
        }
        return packing.getDrawing();
    }

    private static List<Item> getItems(BufferedImage image) {
        List<Item> itemList = new ArrayList<Item>();
        boolean[][] pointsProcessed = new boolean[image.getWidth()][image
                .getHeight()];

        for (int i = 0; i < image.getWidth(); i++) {
            for (int j = 0; j < image.getHeight(); j++) {
                if (pointsProcessed[i][j]) {
                    continue;
                }
                ImagePoint point = ImagePoint.getPoint(i, j, image);
                if (point.getColor().equals(Color.WHITE)) {
                    pointsProcessed[point.x][point.y] = true;
                    continue;
                }
                Collection<ImagePoint> itemPoints = new ArrayList<ImagePoint>();
                Queue<ImagePoint> pointsToProcess = new LinkedList<ImagePoint>();
                pointsToProcess.add(point);
                while (!pointsToProcess.isEmpty()) {
                    point = pointsToProcess.poll();
                    if (pointsProcessed[point.x][point.y]) {
                        continue;
                    }
                    pointsProcessed[point.x][point.y] = true;
                    if (point.getColor().equals(Color.WHITE)) {
                        continue;
                    }
                    itemPoints.add(point);
                    pointsToProcess.addAll(point.getNeighbors());
                }
                itemList.add(new Item(itemPoints));
            }
        }

        return itemList;
    }

    private interface Point {
        int getX();

        int getY();

        Color getColor();
    }

    private static final class ImagePoint implements Point {
        private static final Map<BufferedImage, Map<Integer, Map<Integer, ImagePoint>>> POINT_CACHE = new HashMap<BufferedImage, Map<Integer, Map<Integer, ImagePoint>>>();
        private final int x;
        private final int y;
        private final Color color;
        private final BufferedImage image;
        private Collection<ImagePoint> neighbors;

        private ImagePoint(int x, int y, BufferedImage image) {
            this.x = x;
            this.y = y;
            this.image = image;
            this.color = new Color(image.getRGB(x, y));
        }

        static ImagePoint getPoint(int x, int y, BufferedImage image) {
            Map<Integer, Map<Integer, ImagePoint>> imageCache = POINT_CACHE
                    .get(image);
            if (imageCache == null) {
                imageCache = new HashMap<Integer, Map<Integer, ImagePoint>>();
                POINT_CACHE.put(image, imageCache);
            }
            Map<Integer, ImagePoint> xCache = imageCache.get(x);
            if (xCache == null) {
                xCache = new HashMap<Integer, Packer.ImagePoint>();
                imageCache.put(x, xCache);
            }
            ImagePoint point = xCache.get(y);
            if (point == null) {
                point = new ImagePoint(x, y, image);
                xCache.put(y, point);
            }
            return point;
        }

        Collection<ImagePoint> getNeighbors() {
            if (neighbors == null) {
                neighbors = new ArrayList<ImagePoint>();
                for (int i = -1; i <= 1; i++) {
                    if (x + i < 0 || x + i >= image.getWidth()) {
                        continue;
                    }
                    for (int j = -1; j <= 1; j++) {
                        if ((i == j && i == 0) || y + j < 0
                                || y + j >= image.getHeight()) {
                            continue;
                        }
                        neighbors.add(getPoint(x + i, y + j, image));
                    }
                }
            }
            return neighbors;
        }

        @Override
        public int getX() {
            return y;
        }

        @Override
        public int getY() {
            return x;
        }

        @Override
        public Color getColor() {
            return color;
        }
    }

    private static final class Item {
        private final Collection<ItemPoint> points;
        private final int width;
        private final int height;
        private final int perimiter;
        private final int area;

        Item(Collection<ImagePoint> points) {
            int maxX = Integer.MIN_VALUE;
            int minX = Integer.MAX_VALUE;
            int maxY = Integer.MIN_VALUE;
            int minY = Integer.MAX_VALUE;
            for (ImagePoint point : points) {
                maxX = Math.max(maxX, point.x);
                minX = Math.min(minX, point.x);
                maxY = Math.max(maxY, point.y);
                minY = Math.min(minY, point.y);
            }
            this.width = maxX - minX;
            this.height = maxY - minY;
            this.perimiter = this.width * 2 + this.height * 2;
            this.area = this.width * this.height;
            this.points = new ArrayList<ItemPoint>(points.size());
            for (ImagePoint point : points) {
                this.points.add(new ItemPoint(point.x - minX, point.y - minY,
                        point.getColor()));
            }
        }

        private static final class ItemPoint implements Point {
            private final int x;
            private final int y;
            private final Color color;

            public ItemPoint(int x, int y, Color color) {
                this.x = x;
                this.y = y;
                this.color = color;
            }

            @Override
            public int getX() {
                return x;
            }

            @Override
            public int getY() {
                return y;
            }

            @Override
            public Color getColor() {
                return color;
            }
        }
    }

    private static final class PackedItem {
        private final Collection<PackedPoint> points;
        private Rotation rotation;
        private int x;
        private int y;
        private AffineTransform transform;
        private int modCount;

        PackedItem(Item item, Rotation rotation, int x, int y) {
            this.set(x, y, rotation);
            this.points = new ArrayList<PackedPoint>();
            for (Point point : item.points) {
                this.points.add(new PackedPoint(point));
            }
        }

        void set(int newX, int newY, Rotation newRotation) {
            modCount++;
            x = newX;
            y = newY;
            rotation = newRotation;
            transform = new AffineTransform();
            transform.translate(x, y);
            transform.rotate(this.rotation.getDegrees());
        }

        void draw(Graphics g) {
            Color oldColor = g.getColor();
            for (Point point : points) {
                g.setColor(point.getColor());
                g.drawLine(point.getX(), point.getY(), point.getX(),
                        point.getY());
            }
            g.setColor(oldColor);
        }

        private enum Rotation {
            ZERO(0), NINETY(Math.PI / 2), ONE_EIGHTY(Math.PI), TWO_SEVENTY(
                    3 * Math.PI / 2);

            private final double degrees;

            Rotation(double degrees) {
                this.degrees = degrees;
            }

            double getDegrees() {
                return degrees;
            }
        }

        private final class PackedPoint implements Point {
            private final Point point;
            private final Point2D point2D;
            private int x;
            private int y;
            private int modCount;

            public PackedPoint(Point point) {
                this.point = point;
                this.point2D = new Point2D.Float(point.getX(), point.getY());
            }

            @Override
            public int getX() {
                update();
                return x;
            }

            @Override
            public int getY() {
                update();
                return y;
            }

            private void update() {
                if (this.modCount != PackedItem.this.modCount) {
                    this.modCount = PackedItem.this.modCount;
                    Point2D destPoint = new Point2D.Float();
                    transform.transform(point2D, destPoint);
                    x = (int) destPoint.getX();
                    y = (int) destPoint.getY();
                }
            }

            @Override
            public Color getColor() {
                return point.getColor();
            }
        }
    }

    private static final class Packing {
        private final Set<PackedItem> packedItems = new HashSet<PackedItem>();

        private final Set<PointWrapper> wrappedPoints = new HashSet<PointWrapper>();

        private final int maxWidth;

        private int height;

        Packing(int maxWidth) {
            this.maxWidth = maxWidth;
        }

        void addItem(PackedItem item) {
            packedItems.add(item);
            for (Point point : item.points) {
                height = Math.max(height, point.getY());
                wrappedPoints.add(new PointWrapper(point));
            }
        }

        BufferedImage getDrawing() {
            BufferedImage image = new BufferedImage(maxWidth, height,
                    BufferedImage.TYPE_INT_ARGB);
            Graphics g = image.getGraphics();
            g.setColor(Color.WHITE);
            g.drawRect(0, 0, maxWidth, height);
            for (PackedItem item : packedItems) {
                item.draw(g);
            }
            return image;
        }

        boolean isValidWith(PackedItem item) {
            for (Point point : item.points) {
                if (point.getY() < 0 || point.getX() < 0
                        || point.getX() >= maxWidth) {
                    return false;
                } else if (wrappedPoints.contains(new PointWrapper(point))) {
                    return false;
                }
            }
            return true;
        }

        private static final class PointWrapper {
            private final Point point;

            public PointWrapper(Point point) {
                this.point = point;
            }

            @Override
            public int hashCode() {
                final int prime = 31;
                int result = 1;
                result = prime * result + point.getX();
                result = prime * result + point.getY();
                return result;
            }

            @Override
            public boolean equals(Object obj) {
                if (this == obj) {
                    return true;
                }
                if (obj == null) {
                    return false;
                }
                if (!(obj instanceof PointWrapper)) {
                    return false;
                }
                PointWrapper other = (PointWrapper) obj;
                if (point.getX() != other.point.getX()) {
                    return false;
                }
                if (point.getY() != other.point.getY()) {
                    return false;
                }
                return true;
            }

        }
    }
}

The solution this produces (takes about 4 minutes on my machine) is:

Looking at this picture it seems like the result can be improved by iterating over all of the shapes post packing and trying to move them all up a bit. I might try doing that later.

#Language : Java #Score : 555 533

import java.awt.Color;
import java.awt.Graphics;
import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import javax.imageio.ImageIO;

public class Packer {
    public static void main(String[] args) throws Exception {
        long t1 = System.currentTimeMillis();

        int width = Integer.valueOf(args[0]);
        List<Item> itemList = new ArrayList<Item>();
        for (int i = 1; i < args.length; i++) {
            itemList.addAll(getItems(ImageIO.read(new File(args[i]))));
        }

        File outputFile = new File("output.png");
        if (outputFile.exists()) {
            outputFile.delete();
        }
        outputFile.createNewFile();

        ImageIO.write(pack(itemList, width), "PNG", outputFile);
        long t2 = System.currentTimeMillis();
        System.out.println("Finished in " + (t2 - t1) + "ms");
    }

    private static BufferedImage pack(List<Item> itemList, int width) {
        System.out.println("Packing " + itemList.size() + " items");
        Collections.sort(itemList, new Comparator<Item>() {

            @Override
            public int compare(Item o1, Item o2) {
                return o1.area < o2.area ? 1 : (o1.area > o2.area ? -1
                        : (o1.perimiter < o2.perimiter ? 1
                                : (o1.perimiter > o2.perimiter ? -1 : 0)));
            }
        });
        Packing packing = new Packing(width);
        PackedItem.Rotation[] widthRots = { PackedItem.Rotation.ZERO,
                PackedItem.Rotation.ONE_EIGHTY };
        PackedItem.Rotation[] heightRots = { PackedItem.Rotation.NINETY,
                PackedItem.Rotation.TWO_SEVENTY };
        int count = 0;
        for (Item item : itemList) {
            count++;
            int minSize = Math.min(item.width, item.height);
            int maxSize = Math.max(item.width, item.height);
            int x = 0;
            int y = 0;
            int rot = 0;
            PackedItem.Rotation[] rots = widthRots;
            if (item.width > item.height) {
                rots = heightRots;
            }
            boolean rotsSwitched = false;

            PackedItem packedItem = new PackedItem(item, rots[rot], x, y);
            System.out.format("Packing item %d which is %d by %d\n", count,
                    item.width, item.height);
            while (!packing.isValidWith(packedItem)) {
                if (rot == 0) {
                    rot = 1;
                } else {
                    rot = 0;
                    if (x + minSize >= width) {
                        x = 0;
                        y++;
                        if (!rotsSwitched
                                && y + maxSize > packing.height) {
                            rotsSwitched = true;
                            if (item.width > item.height) {
                                rots = widthRots;
                            } else {
                                rots = heightRots;
                            }
                            y = 0;
                        }
                    } else {
                        x++;
                    }
                }
                packedItem.set(x, y, rots[rot]);
            }
            packing.addItem(packedItem);
            System.out.format("Packed item %d\n", count);
        }
        return packing.getDrawing();
    }

    private static List<Item> getItems(BufferedImage image) {
        List<Item> itemList = new ArrayList<Item>();
        boolean[][] pointsProcessed = new boolean[image.getWidth()][image
                .getHeight()];

        for (int i = 0; i < image.getWidth(); i++) {
            for (int j = 0; j < image.getHeight(); j++) {
                if (pointsProcessed[i][j]) {
                    continue;
                }
                ImagePoint point = ImagePoint.getPoint(i, j, image);
                if (point.getColor().equals(Color.WHITE)) {
                    pointsProcessed[point.x][point.y] = true;
                    continue;
                }
                Collection<ImagePoint> itemPoints = new ArrayList<ImagePoint>();
                Queue<ImagePoint> pointsToProcess = new LinkedList<ImagePoint>();
                pointsToProcess.add(point);
                while (!pointsToProcess.isEmpty()) {
                    point = pointsToProcess.poll();
                    if (pointsProcessed[point.x][point.y]) {
                        continue;
                    }
                    pointsProcessed[point.x][point.y] = true;
                    if (point.getColor().equals(Color.WHITE)) {
                        continue;
                    }
                    itemPoints.add(point);
                    pointsToProcess.addAll(point.getNeighbors());
                }
                itemList.add(new Item(itemPoints));
            }
        }

        return itemList;
    }

    private interface Point {
        int getX();

        int getY();

        Color getColor();
    }

    private static final class ImagePoint implements Point {
        private static final Map<BufferedImage, Map<Integer, Map<Integer, ImagePoint>>> POINT_CACHE = new HashMap<BufferedImage, Map<Integer, Map<Integer, ImagePoint>>>();
        private final int x;
        private final int y;
        private final Color color;
        private final BufferedImage image;
        private Collection<ImagePoint> neighbors;

        private ImagePoint(int x, int y, BufferedImage image) {
            this.x = x;
            this.y = y;
            this.image = image;
            this.color = new Color(image.getRGB(x, y));
        }

        static ImagePoint getPoint(int x, int y, BufferedImage image) {
            Map<Integer, Map<Integer, ImagePoint>> imageCache = POINT_CACHE
                    .get(image);
            if (imageCache == null) {
                imageCache = new HashMap<Integer, Map<Integer, ImagePoint>>();
                POINT_CACHE.put(image, imageCache);
            }
            Map<Integer, ImagePoint> xCache = imageCache.get(x);
            if (xCache == null) {
                xCache = new HashMap<Integer, Packer.ImagePoint>();
                imageCache.put(x, xCache);
            }
            ImagePoint point = xCache.get(y);
            if (point == null) {
                point = new ImagePoint(x, y, image);
                xCache.put(y, point);
            }
            return point;
        }

        Collection<ImagePoint> getNeighbors() {
            if (neighbors == null) {
                neighbors = new ArrayList<ImagePoint>();
                for (int i = -1; i <= 1; i++) {
                    if (x + i < 0 || x + i >= image.getWidth()) {
                        continue;
                    }
                    for (int j = -1; j <= 1; j++) {
                        if ((i == j && i == 0) || y + j < 0
                                || y + j >= image.getHeight()) {
                            continue;
                        }
                        neighbors.add(getPoint(x + i, y + j, image));
                    }
                }
            }
            return neighbors;
        }

        @Override
        public int getX() {
            return y;
        }

        @Override
        public int getY() {
            return x;
        }

        @Override
        public Color getColor() {
            return color;
        }
    }

    private static final class Item {
        private final Collection<ItemPoint> points;
        private final int width;
        private final int height;
        private final int perimiter;
        private final int area;

        Item(Collection<ImagePoint> points) {
            int maxX = Integer.MIN_VALUE;
            int minX = Integer.MAX_VALUE;
            int maxY = Integer.MIN_VALUE;
            int minY = Integer.MAX_VALUE;
            for (ImagePoint point : points) {
                maxX = Math.max(maxX, point.x);
                minX = Math.min(minX, point.x);
                maxY = Math.max(maxY, point.y);
                minY = Math.min(minY, point.y);
            }
            this.width = maxX - minX;
            this.height = maxY - minY;
            this.perimiter = this.width * 2 + this.height * 2;
            this.area = this.width * this.height;
            this.points = new ArrayList<ItemPoint>(points.size());
            for (ImagePoint point : points) {
                this.points.add(new ItemPoint(point.x - minX, point.y - minY,
                        point.getColor()));
            }
        }

        private static final class ItemPoint implements Point {
            private final int x;
            private final int y;
            private final Color color;

            public ItemPoint(int x, int y, Color color) {
                this.x = x;
                this.y = y;
                this.color = color;
            }

            @Override
            public int getX() {
                return x;
            }

            @Override
            public int getY() {
                return y;
            }

            @Override
            public Color getColor() {
                return color;
            }
        }
    }

    private static final class PackedItem {
        private final Collection<PackedPoint> points;
        private Rotation rotation;
        private int x;
        private int y;
        private AffineTransform transform;
        private int modCount;

        PackedItem(Item item, Rotation rotation, int x, int y) {
            this.set(x, y, rotation);
            this.points = new ArrayList<PackedPoint>();
            for (Point point : item.points) {
                this.points.add(new PackedPoint(point));
            }
        }

        void set(int newX, int newY, Rotation newRotation) {
            modCount++;
            x = newX;
            y = newY;
            rotation = newRotation;
            transform = new AffineTransform();
            transform.translate(x, y);
            transform.rotate(this.rotation.getDegrees());
        }

        void draw(Graphics g) {
            Color oldColor = g.getColor();
            for (Point point : points) {
                g.setColor(point.getColor());
                g.drawLine(point.getX(), point.getY(), point.getX(),
                        point.getY());
            }
            g.setColor(oldColor);
        }

        private enum Rotation {
            ZERO(0), NINETY(Math.PI / 2), ONE_EIGHTY(Math.PI), TWO_SEVENTY(
                    3 * Math.PI / 2);

            private final double degrees;

            Rotation(double degrees) {
                this.degrees = degrees;
            }

            double getDegrees() {
                return degrees;
            }
        }

        private final class PackedPoint implements Point {
            private final Point point;
            private final Point2D point2D;
            private int x;
            private int y;
            private int modCount;

            public PackedPoint(Point point) {
                this.point = point;
                this.point2D = new Point2D.Float(point.getX(), point.getY());
            }

            @Override
            public int getX() {
                update();
                return x;
            }

            @Override
            public int getY() {
                update();
                return y;
            }

            private void update() {
                if (this.modCount != PackedItem.this.modCount) {
                    this.modCount = PackedItem.this.modCount;
                    Point2D destPoint = new Point2D.Float();
                    transform.transform(point2D, destPoint);
                    x = (int) destPoint.getX();
                    y = (int) destPoint.getY();
                }
            }

            @Override
            public Color getColor() {
                return point.getColor();
            }
        }
    }

    private static final class Packing {
        private final Set<PackedItem> packedItems = new HashSet<PackedItem>();
        private final int maxWidth;
        private boolean[][] pointsFilled;
        private int height;

        Packing(int maxWidth) {
            this.maxWidth = maxWidth;
            this.pointsFilled = new boolean[maxWidth][0];
        }

        void addItem(PackedItem item) {
            packedItems.add(item);
            for (Point point : item.points) {
                height = Math.max(height, point.getY() + 1);
                if (pointsFilled[point.getX()].length < point.getY() + 1) {
                    pointsFilled[point.getX()] = Arrays.copyOf(
                            pointsFilled[point.getX()], point.getY() + 1);
                }
                pointsFilled[point.getX()][point.getY()] = true;
            }
        }

        BufferedImage getDrawing() {
            BufferedImage image = new BufferedImage(maxWidth, height,
                    BufferedImage.TYPE_INT_ARGB);
            Graphics g = image.getGraphics();
            g.setColor(Color.WHITE);
            g.drawRect(0, 0, maxWidth, height);
            for (PackedItem item : packedItems) {
                item.draw(g);
            }
            return image;
        }

        boolean isValidWith(PackedItem item) {
            for (Point point : item.points) {
                int x = point.getX();
                int y = point.getY();
                if (y < 0 || x < 0 || x >= maxWidth) {
                    return false;
                }
                boolean[] column = pointsFilled[x];
                if (y < column.length && column[y]) {
                    return false;
                }
            }
            return true;
        }
    }
}

The solution this produces (takes about 4 minutes 30 seconds on my machine) is:

Looking at this picture it seems like the result can be improved by iterating over all of the shapes post packing and trying to move them all up a bit. I might try doing that later.

Looking at this picture it seems like the result can be improved by iterating over all of the shapes post packing and trying to move them all up a bit. I might try doing that later.