Instructions
Requirements and Specifications
Source Code
EXTENDED LETTER
import java.util.Objects;
public class ExtendedLetter extends Letter {
private static final int SINGLETON = -1;
private String content;
private int family;
private boolean related;
public ExtendedLetter(String s) {
this(s, SINGLETON);
}
public ExtendedLetter(String s, int fam) {
super('a');
content = s;
related = false;
family = fam;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
ExtendedLetter that = (ExtendedLetter) o;
if (that.family == family) {
related = true;
}
return content.equals(that.content);
}
@Override
public String toString() {
if (isUnused() && related) {
return "." + content + ".";
}
return decorator() + content + decorator();
}
public static Letter[] fromStrings(String[] content, int[] codes) {
Letter[] result = new Letter[content.length];
for (int i = 0; i
if (codes == null) {
result[i] = new ExtendedLetter(content[i]);
}
else {
result[i] = new ExtendedLetter(content[i], codes[i]);
}
}
return result;
}
}
LETTER
import java.util.Objects;
public class Letter {
private static final int UNSET = 0;
private static final int UNUSED = 1;
private static final int USED = 2;
private static final int CORRECT = 3;
private char letter;
private int label;
public Letter(char c) {
letter = c;
label = UNSET;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Letter letter1 = (Letter) o;
return letter == letter1.letter;
}
public String decorator() {
switch (label) {
case UNSET:
return " ";
case UNUSED:
return "-";
case USED:
return "+";
case CORRECT:
return "!";
default:
throw new IllegalStateException();
}
}
@Override
public String toString() {
return decorator() + letter + decorator();
}
public void setUnused() {
label = UNUSED;
}
public void setUsed() {
label = USED;
}
public void setCorrect() {
label = CORRECT;
}
public boolean isUnused() {
return label == UNUSED;
}
public static Letter[] fromString(String s) {
Letter[] result = new Letter[s.length()];
for (int i = 0; i
result[i] = new Letter(s.charAt(i));
}
return result;
}
}
WORD
public class Word {
private LinearNode firstNode;
public Word(Letter[] letters) {
for (int i = letters.length - 1; i>=0; i--) {
LinearNode newNode = new LinearNode<>(letters[i]);
newNode.setNext(firstNode);
firstNode = newNode;
}
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder("Word: ");
LinearNode current = firstNode;
while(current != null) {
builder.append(current.getElement().toString()).append(" ");
current = current.getNext();
}
return builder.toString();
}
// this is the only method, which is not described strictly in the paper,
// so it is the only one, which must be commented in details.
public boolean labelWord(Word mystery) {
// firstly we set used/unused for all letters in this word
// iterating through all letters in this word
LinearNode current = firstNode;
while(current != null) {
Letter l = current.getElement();
// trying to find current letter 'l' in this word
LinearNode mysteryCurr = mystery.firstNode;
// trying to find letter 'l' in word mystery
while (mysteryCurr != null) {
Letter mysteryL = mysteryCurr.getElement();
if (l.equals(mysteryL)) {
// letter 'l' was found in mystery, setting letter l as used
l.setUsed();
break;
}
mysteryCurr = mysteryCurr.getNext();
}
// if we walked through all the letters in mystery and did not find letter l, setting it as unused
if (mysteryCurr == null) {
l.setUnused();
}
// going to next letter of this word.
// maybe some letters in this word are the same, but we don't care - just making the same
current = current.getNext();
}
// now we need to set letters as 'correct' if they are in a correct place
// we start parallel iterations over both words
current = firstNode;
LinearNode mysteryCurr = mystery.firstNode;
// if there will be no matches, this variable will remain true
boolean equals = true;
// we will iterate until both words are not over
while(current != null && mysteryCurr != null) {
Letter l = current.getElement();
Letter mysteryL = mysteryCurr.getElement();
// comparing current letters for both words. If they match, setting 'correct'
if (l.equals(mysteryL)) {
l.setCorrect();
}
else {
equals = false;
}
// shifting to next letter
current = current.getNext();
mysteryCurr = mysteryCurr.getNext();
}
// if words had different length, setting equals var to false
if (current != null || mysteryCurr != null) {
equals = false;
}
return equals;
}
}
WORD LL
public class WordLL {
private Word mysteryWord;
private LinearNode history;
public WordLL(Word mystery) {
mysteryWord = mystery;
history = null;
}
public boolean tryWord(Word guess) {
// checking if word matches
boolean equals = guess.labelWord(mysteryWord);
// appending new guess to history
LinearNode newWord = new LinearNode<>(guess);
newWord.setNext(history);
history = newWord;
// returning comparing result
return equals;
}
@Override
public String toString() {
LinearNode current = history;
StringBuilder builder = new StringBuilder();
while(current != null) {
builder.append(current.getElement().toString()).append(System.lineSeparator());
current = current.getNext();
}
return builder.toString();
}
}Source Code
DJ SET
import java.util.*;
public class djset {
final public static int N = 10;
public int[] parent;
// this array will store set sizes: sizes[find(v)] is the size of set, contatining v
public int[] sizes;
// Creates a disjoint set of size n (0, 1, ..., n-1)
public djset(int n) {
parent = new int[n];
sizes = new int[n];
for (int i = 0; i < n; i++)
{
parent[i] = i;
sizes[i] = 1;
}
}
public int find(int v) {
// I am the club president!!! (root of the tree)
if (parent[v] == v) return v;
// Find my parent's root.
int res = find(parent[v]);
// Attach me directly to the root of my tree.
parent[v] = res;
return res;
}
public boolean union(int v1, int v2) {
// Find respective roots.
int rootv1 = find(v1);
int rootv2 = find(v2);
// No union done, v1, v2 already together.
if (rootv1 == rootv2) return false;
// Attach tree of v2 to tree of v1.
parent[rootv2] = rootv1;
// merging sizes of sets togethers
sizes[rootv1] += sizes[rootv2];
// clearing size of the second set
sizes[rootv2] = 0;
return true;
}
// method for calculating connectivity, according to task rules
public long connectivity() {
// we just beed to make sum of all squares
long sum = 0;
for (int i : sizes) {
long l = i;
sum += l*l;
}
return sum;
}
// For testing.
public void print() {
for (int i = 0; i < parent.length; i++)
System.out.print(parent[i] + " ");
System.out.println();
}
// Run a little test.
public static void main(String[] args) {
djset set = new djset(N);
Random r = new Random();
int numUnion = 0;
// Union N-1 times.
while (numUnion < N - 1) {
// Make v1 and v2 two distinct values.
int v1 = r.nextInt(N);
int v2 = v1;
while (v2 == v1) v2 = r.nextInt(N);
System.out.println("Union of " + v1 + " and " + v2);
boolean res = set.union(v1, v2);
// Already in the same tree/set.
if (!res)
System.out.println("Already together");
// Merge them.
else {
System.out.println("Merged the two trees.");
numUnion++;
}
// Let's look at the set.
set.print();
}
}
}
DESTROY
import java.io.File;
import java.io.IOException;
import java.util.*;
import java.util.stream.Collectors;
public class destroy {
public static void main(String[] args) throws IOException {
// reading input from console
try (Scanner scanner = new Scanner(new File("input.txt"))) {
// reading first line
String[] nmd = scanner.nextLine().split("\\s+");
// parsing n, m and d
int n = Integer.parseInt(nmd[0]);
int m = Integer.parseInt(nmd[1]);
int d = Integer.parseInt(nmd[2]);
// creating empty graph adjacency matrix
djset djset = new djset(n);
// creating an array of edges
int[][] edges = new int[m][2];
for (int i = 0; i < m; i++) {
// reading each edge from input
String[] parts = scanner.nextLine().split("\\s+");
int a = Integer.parseInt(parts[0]) - 1;
int b = Integer.parseInt(parts[1]) - 1;
// adding edge to edge array
edges[i][0] = a;
edges[i][1] = b;
}
// this linked list will contain all edges, which must be deleted in reversed order
LinkedList edgesToDelete = new LinkedList<>();
for (int i = 0; i < d; i++) {
// parsing index of edge destructed
int dest = Integer.parseInt(scanner.nextLine().trim()) - 1;
// adding next one to the beginning, to make list reversed
edgesToDelete.addFirst(dest);
}
// first of all, we create djset for graph without all edges for deletion
LinkedList result = new LinkedList<>();
for (int i = 0; i < m; i++) {
if (edgesToDelete.contains(i)) {
continue;
}
djset.union(edges[i][0], edges[i][1]);
}
// obtained set will have connectivity, which must be outputted last
// here we also reverse the list by adding next value to the beginning
result.addFirst(djset.connectivity());
// iterating over all edges to delete: we add last edge to delete to get previous configuration
for (int i : edgesToDelete) {
// linking connected sets
djset.union(edges[i][0], edges[i][1]);
// recalculating connectivity and pushing it
result.addFirst(djset.connectivity());
}
// outputting result list content, separated by new line character
System.out.println(result.stream().map(l -> Long.toString(l)).collect(Collectors.joining(System.lineSeparator())));
}
}
}