Building a training set of tags for java

[iHiD]

Hello lovely maintainers :wave:

We've recently added "tags" to student's solutions. These express the constructs, paradigms and techniques that a solution uses. We are going to be using these tags for lots of things including filtering, pointing a student to alternative approaches, and much more.

In order to do this, we've built out a full AST-based tagger in C#, which has allowed us to do things like detect recursion or bit shifting. We've set things up so other tracks can do the same for their languages, but its a lot of work, and we've determined that actually it may be unnecessary. Instead we think that we can use machine learning to achieve tagging with good enough results. We've fine-tuned a model that can determine the correct tags for C# from the examples with a high success rate. It's also doing reasonably well in an untrained state for other languages. We think that with only a few examples per language, we can potentially get some quite good results, and that we can then refine things further as we go.

I released a new video on the Insiders page that talks through this in more detail.

We're going to be adding a fully-fledged UI in the coming weeks that allow maintainers and mentors to tag solutions and create training sets for the neural networks, but to start with, we're hoping you would be willing to manually tag 20 solutions for this track. In this post we'll add 20 comments, each with a student's solution, and the tags our model has generated. Your mission (should you choose to accept it) is to edit the tags on each issue, removing any incorrect ones, and add any that are missing. In order to build one model that performs well across languages, it's best if you stick as closely as possible to the C# tags as you can. Those are listed here. If you want to add extra tags, that's totally fine, but please don't arbitrarily reword existing tags, even if you don't like what Erik's chosen, as it'll just make it less likely that your language gets the correct tags assigned by the neural network.

---

To summarise - there are two paths forward for this issue:

1. You're up for helping: Add a comment saying you're up for helping. Update the tags some time in the next few days. Add a comment when you're done. We'll then add them to our training set and move forward.
2. You not up for helping: No problem! Just please add a comment letting us know :)

If you tell us you're not able/wanting to help or there's no comment added, we'll automatically crowd-source this in a week or so.

Finally, if you have questions or want to discuss things, it would be best done on the forum, so the knowledge can be shared across all maintainers in all tracks.

Thanks for your help! :blue_heart:

---

Note: Meta discussion on the forum

[iHiD]

Exercise: isbn-verifier

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

class IsbnVerifier {

    boolean isValid(String stringToVerify) {
        Pattern invalidCharacters = Pattern.compile("[A-Z&&[^X]]");
        Matcher invalidCharactersMatcher = invalidCharacters.matcher(stringToVerify);

        if (invalidCharactersMatcher.find()) {
            return false;
        }

        if(stringToVerify.substring(0, stringToVerify.length() - 2).contains("X")) {
            return false;
        }

        String[] isbnOnlyNumbersArr = stringToVerify
                .replaceAll("-", "")
                .split("");

        if (isbnOnlyNumbersArr[isbnOnlyNumbersArr.length - 1].equals("X")) {
            isbnOnlyNumbersArr[isbnOnlyNumbersArr.length - 1] = "10";
        }

        if (isbnOnlyNumbersArr.length != 10) {
            return false;
        }

        List<Integer> isbnOnlyNumbers = Arrays.stream(isbnOnlyNumbersArr)
                .map(Integer::parseInt)
                .collect(Collectors.toList());

        List<Integer> isbnNumbersMultiplied = new ArrayList<>();
        int multiplier = 10;
        for (Integer isbnOnlyNumber : isbnOnlyNumbers) {
            int newIsbnDigit = isbnOnlyNumber * multiplier;
            isbnNumbersMultiplied.add(newIsbnDigit);
            multiplier = multiplier - 1;
        }
        int isbnSum = isbnNumbersMultiplied
                .stream()
                .mapToInt(Integer::intValue)
                .sum();
        int i = isbnSum % 11;
        return i == 0;
    }

}

Tags:

construct:array
construct:assignment
construct:boolean
construct:class
construct:for-loop
construct:if
construct:import
construct:indexed-access
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:list
construct:method
construct:multiply
construct:number
construct:parameter
construct:return
construct:string
construct:subtract
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:higher-order-functions
technique:looping
technique:regular-expression
uses:ArrayList
uses:Matcher
uses:Pattern
uses:Stream

[iHiD]

Exercise: rotational-cipher

Code

import lombok.RequiredArgsConstructor;

import static java.lang.Character.isLowerCase;
import static java.lang.Character.isUpperCase;
import static java.util.stream.Collectors.joining;

@RequiredArgsConstructor
class RotationalCipher {
    private final int shift;

    String rotate(String text) {
        return text.chars()
                .mapToObj(chr -> String.valueOf((char) shiftCharacter(chr)))
                .collect(joining());
    }

    private int shiftCharacter(int chr) {
        if (isLowerCase(chr))
            return shiftForCharacter(chr, 'a');
        else if (isUpperCase(chr))
            return shiftForCharacter(chr, 'A');
        else
            return chr;
    }

    private int shiftForCharacter(int chr, char base) {
        return (chr - base + shift) % 26 + base;
    }
}

Tags:

construct:add
construct:annotation
construct:char
construct:class
construct:explicit-conversion
construct:field
construct:if
construct:import
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:method
construct:number
construct:parameter
construct:return
construct:short
construct:subtract
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:higher-order-functions
technique:type-conversion
uses:Character.isLowerCase
uses:Character.isUpperCase

[iHiD]

Exercise: saddle-points

Code

import java.util.*;

public class Matrix {
    private List<List<Integer>> matrix;

    Matrix(List<List<Integer>> matrix) {
        this.matrix = matrix;
    }

    public Set<MatrixCoordinate> getSaddlePoints() {
        final int columnSize = this.matrix.size(); // Column Size == Number of Rows
        if (columnSize == 0) {
            return Collections.emptySet();
        }

        final int rowSize = this.matrix.get(0).size(); // Vice-versa
        if (rowSize == 0) {
            return Collections.emptySet();
        }

        int[] rowMaxs = this.matrix
                .stream()
                .mapToInt(r -> Collections.max(r))
                .toArray();

        int[] colMins = new int[rowSize];
        for(int c = 0; c < rowSize; c++) {
            int curMin = this.matrix.get(0).get(c);
            for (int i = 1; i < columnSize; i++) {
                curMin = Math.min(curMin, this.matrix.get(i).get(c));
            }
            colMins[c] = curMin;
        }

        HashSet<MatrixCoordinate> result = new HashSet<>();
        for (int i = 0; i < columnSize; i++) {
            for (int j = 0; j < rowSize; j++) {
                int val = this.matrix.get(i).get(j);
                if (val >= rowMaxs[i] && val <= colMins[j]) {
                    result.add(new MatrixCoordinate(i,j));
                }
            }
        }
        return result;
    }
}

Tags:

construct:assignment
construct:boolean
construct:class
construct:comment
construct:constructor
construct:dictionary
construct:field
construct:for-loop
construct:if
construct:import
construct:indexed-access
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:list
construct:logical-and
construct:method
construct:number
construct:parameter
construct:return
construct:set
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:higher-order-functions
technique:looping
uses:HashSet
uses:Math.min
uses:Stream

[iHiD]

Exercise: run-length-encoding

Code

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class RunLengthEncoding {

    public RunLengthEncoding() {
        super();
    }

    public String encode(String source) {

        StringBuffer dest = new StringBuffer();
        for (int i = 0; i < source.length(); i++) {
            int runLength = 1;
            while (i + 1 < source.length()
                    && source.charAt(i) == source.charAt(i + 1)) {
                runLength++;
                i++;
            }
            if(runLength!=1) {
            dest.append(runLength);
            }
            dest.append(source.charAt(i));
        }
        return dest.toString();
    }

    public String decode(String source) {
        StringBuffer dest = new StringBuffer();
        Pattern pattern = Pattern.compile("[0-9]+|[a-zA-Z]");
        Matcher matcher = pattern.matcher(source);
        while (matcher.find()) {
            int number;
            number = Integer.parseInt(matcher.group());

            matcher.find();
            while (number-- != 0) {
                dest.append(matcher.group());
            }
        }
        return dest.toString();
    }

}

Tags:

construct:add
construct:assignment
construct:boolean
construct:char
construct:class
construct:constructor
construct:for-loop
construct:if
construct:import
construct:int
construct:integral-number
construct:invocation
construct:logical-and
construct:method
construct:number
construct:parameter
construct:return
construct:string
construct:subtract
construct:variable
construct:visibility-modifiers
construct:while-loop
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:looping
technique:regular-expression
uses:Matcher
uses:Pattern
uses:StringBuffer

[iHiD]

Exercise: pascals-triangle

Code

import java.util.Arrays;

public class PascalsTriangle {

    public static int[][] computeTriangle(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n should be positive value");
        }
        int result[][] = new int[n][];
        for (int i = 1; i <= n; i++) {
            int t[] = new int[i];
            t[0] = 1;
            t[i - 1] = 1;
            for (int j = 1; j < i - 1; j++) {
                t[j] = result[i - 2][j - 1] + result[i - 2][j];
            }
            result[i - 1] = t;
        }
        return result;
    }

    public static boolean isTriangle(int[][] input) {
        return Arrays.deepEquals(computeTriangle(input.length), input);
    }

    public static void main(String arg[]) {
        System.out.println(Arrays.deepToString(computeTriangle(6)));
    }

}

Tags:

construct:add
construct:assignment
construct:boolean
construct:class
construct:for-loop
construct:if
construct:import
construct:indexed-access
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:method
construct:number
construct:parameter
construct:return
construct:string
construct:subtract
construct:throw
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:exceptions
technique:higher-order-functions
technique:looping

[iHiD]

Exercise: minesweeper

Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static java.util.Objects.isNull;
import static java.util.stream.Collectors.toList;

public final class MinesweeperBoard {

    static final int BOARD_MIN = 0;

    static final char EMPTY = ' ';
    static final char BOMB = '*';

    final List<String> inputBoard;

    final int widthBound;
    final int heightMax;

    public MinesweeperBoard(List<String> inputBoard) {
        this.inputBoard = validateBoard(inputBoard);
        heightMax = inputBoard.size() - 1;
        widthBound = inputBoard.isEmpty() ? BOARD_MIN : inputBoard.get(0).length() - 1;
    }

    public List<String> getAnnotatedRepresentation() {
        List<StringBuilder> annotated = inputBoard.stream()
                                                  .map(StringBuilder::new)
                                                  .collect(toList());

        findBombs(inputBoard).entrySet()
                             .forEach(e -> e.getValue().forEach(x -> updateNeighbors(annotated, x, e.getKey())));

        return annotated.stream().map(StringBuilder::toString).collect(toList());
    }

    private static List<String> validateBoard(List<String> board) {
        if (isNull(board))
            throw new IllegalArgumentException("Input board may not be null.");

        validateRowLengths(board);
        board.forEach(MinesweeperBoard::validateRow);

        return board;
    }

    private static void validateRow(String row) {
        if (row.replaceAll("\\*", "").trim().length() > 0)
            throw new IllegalArgumentException("Input board can only contain the characters ' ' and '*'.");
    }

    private static void validateRowLengths(List<String> board) {
        if (board.stream().map(String::length).collect(Collectors.toSet()).size() > 1)
            throw new IllegalArgumentException("Input board rows must all have the same number of columns.");
    }

    private HashMap<Integer, List<Integer>> findBombs(List<String> board) {
        HashMap<Integer, List<Integer>> bombMap = new HashMap<>();
        for (int h = BOARD_MIN; h < board.size(); h++) {
            ArrayList<Integer> positions = new ArrayList<>();
            String row = board.get(h);
            int bomb = BOARD_MIN;
            while ((bomb = row.indexOf(BOMB, bomb)) >= BOARD_MIN) {
                positions.add(bomb);
                bomb++;
            }
            bombMap.put(h, positions);
        }
        return bombMap;
    }

    private void updateNeighbors(List<StringBuilder> board, int x, int y) {
        IntStream.rangeClosed(Math.max(BOARD_MIN, x - 1), Math.min(x + 1, widthBound))
                 .forEach(xPos ->
                         IntStream.rangeClosed(Math.max(BOARD_MIN, y - 1), Math.min(y + 1, heightMax))
                                  .forEach(yPos -> incrementPosition(board, xPos, yPos)));
    }

    private void incrementPosition(List<StringBuilder> board, int x, int y) {
        StringBuilder row = board.get(y);
        char spot = row.charAt(x);
        if (spot == EMPTY)
            row.setCharAt(x, '1');
        else if (spot != BOMB)
            row.setCharAt(x, (char) (spot + 1));
    }
}

Tags:

construct:add
construct:assignment
construct:char
construct:class
construct:constructor
construct:dictionary
construct:explicit-conversion
construct:field
construct:for-loop
construct:if
construct:import
construct:indexed-access
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:list
construct:method
construct:number
construct:parameter
construct:return
construct:set
construct:static-method
construct:subtract
construct:ternary
construct:throw
construct:throwable
construct:variable
construct:visibility-modifiers
construct:while-loop
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:exceptions
technique:higher-order-functions
technique:looping
technique:type-conversion
uses:ArrayList
uses:HashMap
uses:IntStream
uses:Math.max
uses:Math.min
uses:Stream
uses:StringBuilder

[iHiD]

Exercise: all-your-base

Code

final class BaseConverter {

    private static final int[] ZERO = new int[] { 0 };
    private final int valueBase10;

    public BaseConverter(int base, int[] digits) {
        if (base < 2) {
            throw new IllegalArgumentException("Bases must be at least 2.");
        }
        if (digits.length == 0) {
            throw new IllegalArgumentException("You must supply at least one digit.");
        }
        for (int digit : digits) {
            if (digit >= base) {
                throw new IllegalArgumentException("All digits must be strictly less than the base.");
            }
            if (digit < 0) {
                throw new IllegalArgumentException("Digits may not be negative.");
            }
        }

        int leadingZeroes = 0;
        int acc = 0;
        for (int i=0; i<digits.length; i++) {
            int pow = digits.length - i - 1;
            int digit = digits[i];
            acc += digit * Math.pow(base, pow);
            if (digit == 0 && acc == 0) {
                leadingZeroes++;
            }
        }

        if (leadingZeroes > 0 && digits.length > 1) {
            throw new IllegalArgumentException("Digits may not contain leading zeros.");
        }

        this.valueBase10 = acc;
    }

    public int[] convertToBase(int base) {
        if (base < 2) {
            throw new IllegalArgumentException("Bases must be at least 2.");
        }
        if (valueBase10 == 0) {
            return ZERO;
        }

        int length = (int) (Math.log(valueBase10) / Math.log(base)) + 1;
        int index = length - 1;
        int[] digits = new int[length];
        int copy = valueBase10;

        while (copy >= base) {
            int q = copy / base;
            int r = copy % base;
            digits[index] = r;
            index--;
            copy = q;
        }
        digits[index] = copy;

        return digits;
    }

}

Tags:

construct:add
construct:assignment
construct:boolean
construct:class
construct:constructor
construct:divide
construct:double
construct:explicit-conversion
construct:field
construct:for-loop
construct:if
construct:implicit-conversion
construct:indexed-access
construct:int
construct:integral-number
construct:logical-and
construct:method
construct:modulo
construct:multiply
construct:number
construct:parameter
construct:return
construct:string
construct:subtract
construct:throw
construct:variable
construct:visibility-modifiers
construct:while-loop
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:exceptions
technique:looping
technique:type-conversion
uses:Math.log
uses:Math.pow

[iHiD]

Exercise: word-search

Code

import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.Set;

import static java.util.stream.Collectors.toMap;

/**
 * Created by apop on 7/5/2017.
 */
public class WordSearcher {

  private static Map<String, Optional<WordLocation>> getWords(char[][] matrix, int row, int column, int wordLength) {
    Map<String, Optional<WordLocation>> result = new HashMap<>();

    if (column - wordLength + 1 >= 0) { // LEFT
      String tmp = "";
      int from = column - wordLength + 1;
      int to = column;
      for (int i = to; i >= from; i--) {
        tmp += matrix[row][i];
      }
      result.put(tmp, Optional.of(new WordLocation(new Pair(column + 1, row + 1), new Pair(column - wordLength + 1 + 1, row + 1))));
    }

    if (column + wordLength - 1 < matrix[row].length) { // RIGHT
      String tmp = "";
      int from = column;
      int to = column + wordLength;
      for (int i = from; i < to; i++) {
        tmp += matrix[row][i];
      }
      result.put(tmp, Optional.of(new WordLocation(new Pair(column + 1, row + 1), new Pair(column + wordLength - 1 + 1, row + 1))));
    }

    if (row - wordLength + 1 >= 0) { // TOP
      String tmp = "";
      int from = row - wordLength + 1;
      int to = row;
      for (int i = to; i >= from; i--) {
        tmp += matrix[i][column];
      }
      result.put(tmp, Optional.of(new WordLocation(new Pair(column + 1, row + 1), new Pair(column + 1, row - wordLength + 1 + 1))));
    }

    if (row + wordLength - 1 < matrix.length) { // BOTTOM
      String tmp = "";
      int from = row;
      int to = row + wordLength;
      for (int i = from; i < to; i++) {
        tmp += matrix[i][column];
      }
      result.put(tmp, Optional.of(new WordLocation(new Pair(column + 1, row + 1), new Pair(column + 1, row + wordLength - 1 + 1))));
    }

    return result;
  }

  public Map<String, Optional<WordLocation>> search(Set<String> searchWords, char[][] matrix) {
    Map<String, Optional<WordLocation>> result = new HashMap<>();

    for (int row = 0; row < matrix.length; row++) {
      for (int column = 0; column < matrix[row].length; column++) {
        char point = matrix[row][column];
        if (searchWords.stream().anyMatch(w -> w.charAt(0) == point)) {
          int crow = row;
          int ccolumn = column;

          Map<String, Optional<WordLocation>> combinations = searchWords.stream()
                  .map(s -> getWords(matrix, crow, ccolumn, s.length()))
                  .flatMap(m -> m.entrySet().stream())
                  .collect(toMap(Map.Entry::getKey, Map.Entry::getValue));

          result.putAll(combinations.entrySet().stream().filter(e -> searchWords.contains(e.getKey())).collect(toMap(Map.Entry::getKey, Map.Entry::getValue)));
        }
      }
    }
    result.entrySet().stream().forEach(e -> System.out.println(e.getKey() + "---" + e.getValue().get()));
    return result;
  }

}

Tags:

construct:add
construct:assignment
construct:char
construct:class
construct:constructor
construct:dictionary
construct:field
construct:for-loop
construct:if
construct:import
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:method
construct:number
construct:option
construct:parameter
construct:return
construct:set
construct:string
construct:subtract
construct:throw
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:exceptions
technique:higher-order-functions
technique:looping
uses:HashMap
uses:Stream

[iHiD]

Exercise: zipper

Code

import java.util.*;
import java.lang.*;

class Zipper
{
    public Zipper rightChild;
    public Zipper leftChild;
    public Zipper upperChild;
    public int data;

    public Zipper(int value)
    {
        this.data = value;
    }

    public BinaryTree toTree()
    {
        Zipper temp = this;
        while(temp.upperChild != null)
        {
            temp = temp.upperChild;
        }
        return new BinaryTree(temp);    
    }
}

Tags:

construct:assignment
construct:class
construct:constructor
construct:field
construct:import
construct:int
construct:integral-number
construct:method
construct:null
construct:nullability
construct:parameter
construct:return
construct:variable
construct:visibility-modifiers
construct:while-loop
paradigm:imperative
paradigm:object-oriented
technique:looping

[iHiD]

Exercise: go-counting

Code

import java.util.*;
import java.lang.*;

class GoCounting
{
    private char[][] board;

    public GoCounting(String input)
    {
        this.board = getBoard(board);
    }

    public Player getTerritoryOwner(int x, int y)
    {

    }

    public Set<Point> getTerritory(int x, int y)
    {

    }

    private char[][] getBoard(String board)
    {
        String[] rows = board.split("\\n");
        char[][] grid = new char[rows.length][rows[0].length()];

        for(int i = 0; i < grid.length; i++)
        {
            grid[i] = rows[i].toCharArray();
        }
        return grid;
    }
}

Tags:

construct:assignment
construct:char
construct:class
construct:constructor
construct:field
construct:for-loop
construct:import
construct:indexed-access
construct:int
construct:integral-number
construct:invocation
construct:method
construct:number
construct:parameter
construct:return
construct:set
construct:string
construct:throw
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:object-oriented
technique:exceptions
technique:looping

[iHiD]

Exercise: ocr-numbers

Code

import java.util.*;
import java.util.stream.Collectors;

public class OpticalCharacterReader {
    private static final Map<String, String> KNOWN = initializeEntries();

    private static Map<String, String> initializeEntries() {
        var initialLines = split(Arrays.asList(
                " _     _  _     _  _  _  _  _ ",
                "| |  | _| _||_||_ |_   ||_||_|",
                "|_|  ||_  _|  | _||_|  ||_| _|",
                "                              "
        ));
        var result = new HashMap<String, String>();
        for (int i = 0; i < initialLines.size(); i++) {
            result.put(initialLines.get(i), Integer.toString(i));
        }
        result.put(",", ",");
        return result;
    }

    public String parse(List<String> lines) {
        checkNumberOfRows(lines);
        return split(lines).stream()
                .map(d -> KNOWN.getOrDefault(d, "?"))
                .collect(Collectors.joining());
    }

    private void checkNumberOfRows(List<String> asList) {
        if (asList.size() % 4 != 0) {
            throw new IllegalArgumentException("\"Number of input rows must be a positive multiple of 4\"");
        }
    }

    private static List<String> split(List<String> lines) {
        try {
            var ocdDigits = new ArrayList<String>();
            int length = lines.get(0).length();
            for (int baseline = 0; baseline < lines.size(); baseline += 4) {
                for (int i = 0; i < length; i += 3) {
                    var digit = lines.get(baseline).substring(i, i + 3) +
                            lines.get(baseline + 1).substring(i, i + 3) +
                            lines.get(baseline + 2).substring(i, i + 3) +
                            lines.get(baseline + 3).substring(i, i + 3);
                    ocdDigits.add(digit);
                }
                ocdDigits.add(",");
            }
            ocdDigits.remove(ocdDigits.size() - 1);
            return ocdDigits;
        } catch (StringIndexOutOfBoundsException e) {
            throw new IllegalArgumentException("Number of input columns must be a positive multiple of 3");
        }
    }
}

Tags:

construct:add
construct:assignment
construct:catch
construct:class
construct:constructor
construct:dictionary
construct:field
construct:for-loop
construct:if
construct:import
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:list
construct:method
construct:number
construct:parameter
construct:return
construct:string
construct:subtract
construct:throw
construct:try
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:exceptions
technique:higher-order-functions
technique:looping
uses:ArrayList
uses:HashMap
uses:Stream

[iHiD]

Exercise: circular-buffer

Code

public class BufferIOException extends Exception {

    BufferIOException(String message) {
        super(message);
    }
}

class CircularBuffer<T> {
    T[] buffer;
    int headIndex;
    int tailIndex;
    int length;

    @SuppressWarnings("unchecked")
    CircularBuffer(int size) {
        buffer = (T[]) new Object[size];

        clear();
    }

    T read() throws BufferIOException {
        if (isEmpty()) {
            throw new BufferIOException("Tried to read from empty buffer");
        }

        T result = buffer[headIndex];
        headIndex = (headIndex + 1) % buffer.length;
        length--;
        return result;
    }

    void write(T element) throws BufferIOException {
        if (isFull()) {
            throw new BufferIOException("Tried to write to full buffer");
        }

        buffer[tailIndex] = element;
        tailIndex = (tailIndex + 1) % buffer.length;
        length++;
    }

    void overwrite(T element) throws BufferIOException {
        if (isFull()) {
            read();
        }
        write(element);
    }

    void clear() {
        headIndex = 0;
        tailIndex = 0;
        length = 0;
    }

    boolean isEmpty() {
        return length == 0;
    }

    boolean isFull() {
        return length > 0 && headIndex == tailIndex;
    }
}

Tags:

construct:add
construct:assignment
construct:boolean
construct:class
construct:constructor
construct:explicit-conversion
construct:field
construct:generic-type
construct:if
construct:indexed-access
construct:int
construct:integral-number
construct:logical-and
construct:method
construct:modulo
construct:number
construct:parameter
construct:return
construct:string
construct:throw
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:object-oriented
technique:exceptions
technique:inheritance
technique:boolean-logic

[iHiD]

Exercise: rectangles

Code

import javafx.util.Pair;

import java.awt.Point;
import java.util.*;

public class RectangleCounter {
    private Set<Pair<Point, Point>> rectangles;
    private String[] input;

    public int countRectangles(String[] input) {
        this.input = input;

        //find rectangles that are not made up of smaller rectangles & add to set
        findDistinctRectangles();

        //keep attempting to match rectangles until no more matches are found
        /*boolean foundOne;
        do {
            foundOne = false;

            for(Pair<Point, Point> p1 : rectangles){
                for(Pair<Point, Point> p2 : rectangles){
                    if(p1 == p2) continue;

                    if(hasCompositeRectangle(p1, p2)){
                        foundOne = rectangles.add(new Pair<>(p1.getKey(), p2.getValue()));
                    }
                }
            }

        } while(foundOne);*/

        return rectangles.size();
    }

    //Iterate over input, trying to find a rectangle for each + encountered
    private void findDistinctRectangles(){
        rectangles = new HashSet<>();

        for(int y = 0; y < input.length-1; y++){
            for(int x = 0; x < input[y].length()-1; x++){
                if(input[y].charAt(x) == '+') {
                    getDistinctRectangles(x, y, new Point(x, y), null, Direction.RIGHT);
                }
            }
        }
    }

    //runs along pipes and bars, turning at pluses, trying to get back to the start point
    //branches into a recursion if an intersection has two valid paths
    private void getDistinctRectangles(int x, int y, Point origin, Point opposite,
                                       Direction direction){
        if(input[y].charAt(x) != '+'){
            return;
        }

        while(true){
            x += direction.xChange;
            y += direction.yChange;
            if(y < 0 || y >= input.length || x < 0 || x >= input[y].length()){
                return;
            }

            //check intersections to see if we need to start the next direction
            if(input[y].charAt(x) == '+'){
                char angledView = input[y + direction.next().yChange].charAt(x + direction.next().xChange);
                switch(direction){
                    //looking for a bar at a right angle
                    case RIGHT:
                    case LEFT:
                        if(angledView == direction.next().validLine || angledView == '+'){
                            getDistinctRectangles(x, y, origin, opposite, direction.next());
                        }
                        break;
                    case DOWN:
                        if(angledView == direction.next().validLine || angledView == '+'){
                            opposite = new Point(x,y);
                            getDistinctRectangles(x, y, origin, opposite, direction.next());
                        }
                        break;
                    case UP:
                        if(x == origin.x && y == origin.y) {
                            rectangles.add(new Pair<>(origin, opposite));
                            return;
                        }
                        break;
                }
            }
            //if the character is not a valid line, rectangle not found
            else if(input[y].charAt(x) != direction.validLine){
                return;
            }
        }
    }

    //A composite rectangle exists if and only if two input rectangles share exactly two adjacent points
    private boolean hasCompositeRectangle(Pair<Point, Point> p1, Pair<Point, Point> p2){

        //skip if p2 is up or left of p1, since it will only need to be counted the other way
        if(p2.getKey().x < p1.getKey().x || p2.getKey().y < p1.getKey().y) return false;

        //rectangles share vertical boundary
        if(p1.getKey().x == p2.getKey().x //upper left corners align horizontally
                && p1.getValue().x == p2.getValue().x //lower right corners align horizontally
                && p1.getValue().y == p2.getKey().y){ //upper rectangle's lower corner and lower rectangle's upper corner align vertically
            return true;
        }

        //rectangles share horizontal boundary
        return p1.getKey().y == p2.getKey().y //upper left corners align vertically
                && p1.getValue().y == p2.getValue().y //lower right corners align vertically
                && p1.getValue().x == p2.getKey().x; //opposite corners align horizontally
    }
}

enum Direction{
    RIGHT(1,0, '-'), DOWN(0,1, '|'), LEFT(-1,0,'-'), UP(0,-1,'|');
    public final int xChange, yChange;
    public final char validLine;

    Direction(int x, int y, char c){
        xChange = x;
        yChange = y;
        validLine = c;
    }

    public Direction next(){
        return Direction.values()[((this.ordinal()+1) % Direction.values().length)];
    }
}

Tags:

construct:add
construct:assignment
construct:boolean
construct:break
construct:char
construct:class
construct:constructor
construct:continue
construct:do-while-loop
construct:enum
construct:field
construct:for-loop
construct:if
construct:import
construct:indexed-access
construct:int
construct:integral-number
construct:invocation
construct:logical-and
construct:logical-or
construct:method
construct:modulo
construct:null
construct:nullability
construct:number
construct:parameter
construct:return
construct:set
construct:string
construct:subtract
construct:switch
construct:variable
construct:visibility-modifiers
construct:while-loop
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:looping
uses:HashSet
uses:Pair

[iHiD]

Exercise: custom-set

Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CustomSet<T> {

    List<T> list;

    public CustomSet(List<T> list) {
        this.list = new ArrayList<T>(list);
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public boolean contains(int i) {
        return list.contains(i);
    }

    public boolean isSubset(CustomSet customSet) {
        boolean result = true;
        for (int i = 0; i < customSet.list.size(); i++) {
            if (!list.contains(customSet.list.get(i))) {
                result = false;
                break;
            }
        }
        return result;
    }

    public boolean isDisjoint(CustomSet customSet) {
        boolean result = true;
        for (int i = 0; i < customSet.list.size(); i++) {
            if (list.contains(customSet.list.get(i))) {
                result = false;
                break;
            }
        }
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        CustomSet other = (CustomSet) obj;
        if (list == null) {
            if (other.list != null)
                return false;
        } else {
            if (other.list.size() == 0 && list.size() == 0) {
                return true;
            } else if (isSubset(other) && !isDisjoint(other)) {
                return true;
            } else {
                return false;
            }
        }
        return true;
    }

    public void add(T element) {
        list.add(element);
    }

    public CustomSet<Integer> getDifference(CustomSet customSet) {
        CustomSet result = new CustomSet(Collections.EMPTY_LIST);
        List intersection = new ArrayList();
        for (int i = 0; i < list.size(); i++) {
            if (!customSet.list.contains(list.get(i))) {
                result.add(list.get(i));
            }
        }
        return result;
    }

    public CustomSet getIntersection(CustomSet customSet) {
        CustomSet result = new CustomSet(Collections.EMPTY_LIST);
        List intersection = new ArrayList();
        for (int i = 0; i < list.size(); i++) {
            if (customSet.list.contains(list.get(i))) {
                result.add(list.get(i));
            }
        }
        return result;
    }

    public CustomSet<Integer> getUnion(CustomSet customSet) {
        CustomSet result = new CustomSet(Collections.EMPTY_LIST);
        for (int i = 0; i < list.size(); i++) {
            result.add(list.get(i));
        }
        for (int i = 0; i < customSet.list.size(); i++) {
            result.add(customSet.list.get(i));
        }
        return result;
    }

}

Tags:

construct:assignment
construct:boolean
construct:break
construct:class
construct:constructor
construct:explicit-conversion
construct:field
construct:for-loop
construct:generic-type
construct:if
construct:import
construct:int
construct:integral-number
construct:invocation
construct:list
construct:logical-and
construct:method
construct:null
construct:nullability
construct:number
construct:parameter
construct:return
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:looping
technique:type-conversion
uses:ArrayList

[iHiD]

Exercise: affine-cipher

Code

package cipher;

import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toMap;

import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class AffineCipher {

  public String encode(String plaintext, int a, int b) {
    validateA(a);
    return plaintext.toLowerCase().replaceAll("\\W", "").chars()
        .map(c -> c - 'a')
        .map(c -> c < 0 ? c : ((c * a) + b) % 26)
        .mapToObj(c -> "" + (char) (c + 'a'))
        .collect(joining())
        .replaceAll(".{5}(?=.)", "$0 ");
  }

  public String decode(String ciphertext, int a, int b) {
    validateA(a);
    Map<Integer, Integer> aInverse = buildMultiplicativeInverseMap(a);
    return ciphertext.toLowerCase().replaceAll("\\W", "").chars()
        .map(c -> c - 'a')
        .map(c -> c < 0 ? c : aInverse.get(Math.floorMod(c - b, 26)))
        .mapToObj(c -> "" + (char) (c + 'a'))
        .collect(Collectors.joining());
  }

  private Map<Integer, Integer> buildMultiplicativeInverseMap(int a) {
    return IntStream.range(0, 26).boxed()
        .collect(toMap(i -> (i * a) % 26, i -> i));
  }

  private void validateA(int a) {
    if (a % 2 == 0 || a % 13 == 0) {
      throw new IllegalArgumentException("Error: keyA and alphabet size must be coprime.");
    }
  }
}

Tags:

construct:add
construct:boolean
construct:box
construct:char
construct:class
construct:constructor
construct:dictionary
construct:explicit-conversion
construct:if
construct:import
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:logical-or
construct:method
construct:modulo
construct:multiply
construct:number
construct:module
construct:parameter
construct:return
construct:string
construct:subtract
construct:ternary
construct:throw
construct:throwable
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:object-oriented
technique:boolean-logic
technique:exceptions
technique:higher-order-functions
technique:looping
technique:type-conversion
uses:IntStream

[sanderploegsma]

Definitely! 💯

[sanderploegsma]

@iHiD of the solutions you added, the following are invalid as they are not actually the solution files but the test files that were supposedly also submitted by students:

• difference-of-squares
• isogram
• queen-attack
• grade-school
• darts

[sanderploegsma]

@iHiD I went through all solutions and updated the tags to match the list of commonly used tags where appropriate, and adding/removing things where needed.

All exercises with 👍 have been updated, all exercises with 👎 I consider non-valid as I mentioned yesterday.

[iHiD]

Brilliant. Thank you!

[sanderploegsma]

@iHiD anything left to do here, or can we close it?

[iHiD]

We'll leave it open for Erik to get the data back out for now, and he'll close it when he's done. Thanks! :)

[ErikSchierboom]

This is an automated comment

Hello :wave: Next week we're going to start using the tagging work people are doing on these. If you've already completed the work, thank you! If you've not, but intend to this week, that's great! If you're not going to get round to doing it, and you've not yet posted a comment letting us know, could you please do so, so that we can find other people to do it. Thanks!

[ErikSchierboom]

Thanks for the help! We've updated the tags.