Advent of Code 2018: Day 2

Part 1

Part 1 is a trivial checksum calculation where we need to loop through each ID - and count the number of IDs which have at least one character repeated exactly twice - and separately count the number of IDs which have at least one character repeated exactly three times. Then multiple these numbers together.

I haven't posted this code separated as it's quite simple - it's included in the part 2 code.

Part 2

Part 2 is interesting. We have to find a pair of ids which differ on only one character. The naive solution is to loop through each pair and check if they differ by exactly one. If we call the number of boxes N, and the length of the ID L, this would be O(N²) time and constant space.

My solution is to generate L hashes per box (by replacing each character with a character that does not appear in any id), insert them into a map, and then find any collections which contain exactly two. This is O(LN) time and space. In this challenge L is a fixed number so it's effectively O(N).

class BoxId {
    private final String id;
    private final boolean hasTwoSameLetter;
    private final boolean hasThreeSameLetter;

    BoxId(String id) {
        this.id = id;
        Collection<Long> counts = calculateCharacterCounts(id);
        hasTwoSameLetter = counts.contains(2L);
        hasThreeSameLetter = counts.contains(3L);
    }

    /**
     * @return A collection of the character counts from this string.
     *         e.g. "test" would return { 2, 1, 1 } (2 t, 1 e, 1 s)
     */
    private static Collection<Long> calculateCharacterCounts(String id) {
        return id.chars().boxed()
                .collect(Collectors.groupingBy(c -> c, Collectors.counting()))
                .values();
    }

    String id() {
        return id;
    }

    boolean hasTwoSameLetter() {
        return hasTwoSameLetter;
    }

    boolean hasThreeSameLetter() {
        return hasThreeSameLetter;
    }

    /**
     * Generate the ID with each character replaced with an underscore.
     * For example, if the ID is "abcdefg" then the result will be:
     *    {"_bcdefg", "a_cdefg", "ab_defg", "abc_efg", "abcde_g", "abcdef_"}
     */
    Collection<String> generateStringsOfIdWithEachCharacterReplacedWithUnderscore() {
        List<String> strings = new ArrayList<>();
        StringBuilder builder = new StringBuilder(id);

        for (int i = 0; i < id.length(); i++) {
            builder.replace(i, i + 1, "_");

            strings.add(builder.toString());

            builder.replace(i, i + 1, String.valueOf(id.charAt(i)));
        }

        return strings;
    }
}

class BoxCollection {
    private final List<BoxId> boxIds;
    private final int checksum;

    BoxCollection(List<BoxId> boxIds) {
        this.boxIds = boxIds;
        checksum = calculateChecksum();
    }

    private int calculateChecksum() {
        int twoCount = 0;
        int threeCount = 0;

        for (BoxId boxId: boxIds) {
            if (boxId.hasThreeSameLetter()) {
                threeCount++;
            }
            if (boxId.hasTwoSameLetter()) {
                twoCount++;
            }
        }

        return twoCount * threeCount;
    }

    /**
     * Calculate the checksum according to the task.
     *
     * This counts the number of boxIds containing exactly two of any letter and then separately counting those
     * with exactly three of any letter. These two counts are multiplied together to produce the checksum.
     */
    int checksum() {
        return checksum;
    }

    /**
     * Find every set of two boxIds which differ in only one character.
     */
    Collection<CorrectBoxSet> findCorrectBoxIds() {
        // The algorithm here is that for each of the N boxIds, we generate L hashes (where L is the length of the
        // id). Each of these is used as the key in a map, so that IDs which are one different from each other
        // will be together. We then loop through each value in the map and find any which contain exactly two ids
        // these will be returned.
        Collection<CorrectBoxSet> correctBoxSets = new HashSet<>();
        Map<String, Collection<BoxId>> boxIdHashes = new HashMap<>();

        for (BoxId boxId : boxIds) {
            for (String hash : boxId.generateStringsOfIdWithEachCharacterReplacedWithUnderscore()) {
                addToCollection(boxIdHashes, hash, boxId);
            }
        }

        for (Collection<BoxId> set : boxIdHashes.values()) {
            if (set.size() == 2) {
                BoxId[] setArray = set.toArray(new BoxId[2]);
                correctBoxSets.add(new CorrectBoxSet(setArray[0], setArray[1]));
            }
        }
        return correctBoxSets;
    }

    private void addToCollection(Map<String, Collection<BoxId>> boxIdHashes, String hash, BoxId boxId) {
        if (!boxIdHashes.containsKey(hash)) {
            boxIdHashes.put(hash, new HashSet<>());
        }
        boxIdHashes.get(hash).add(boxId);
    }
}

class CorrectBoxSet {
    private BoxId boxId1;
    private BoxId boxId2;

    CorrectBoxSet(BoxId boxId1, BoxId boxId2) {
        this.boxId1 = boxId1;
        this.boxId2 = boxId2;
    }

    String calculateOverlap() {
        StringBuilder overlap = new StringBuilder();

        int ptr = 0;
        while (ptr < boxId1.id().length() && ptr < boxId2.id().length()) {
            if (boxId1.id().charAt(ptr) == boxId2.id().charAt(ptr)) {
                overlap.append(boxId1.id().charAt(ptr));
            }
            ptr++;
        }

        return overlap.toString();
    }
}

public class BoxScanner {
    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Error: First argument must be box IDs string");
            System.exit(1);
        }

        String[] boxIdStrings = args[0].split("[ \n]");

        List<BoxId> boxIds = Stream.of(boxIdStrings).map(BoxId::new).collect(Collectors.toList());

        BoxCollection boxCollection = new BoxCollection(boxIds);

        System.out.println(String.format("The checksum is %s", boxCollection.checksum()));

        Collection<CorrectBoxSet> correctBoxSets = boxCollection.findCorrectBoxIds();

        for (CorrectBoxSet correctBoxSet : correctBoxSets) {
            System.out.println(String.format("Common letters in correct box: %s", correctBoxSet.calculateOverlap()));
        }
    }
}

Advent Of Code runs until December 25. You should get involved!

Show Comments

Get the latest posts delivered right to your inbox.