Skip to content

Instantly share code, notes, and snippets.

@Vyom-Yadav
Created December 24, 2023 17:49
Show Gist options
  • Save Vyom-Yadav/5601cdde60e49090cbc3344d85e1161a to your computer and use it in GitHub Desktop.
Save Vyom-Yadav/5601cdde60e49090cbc3344d85e1161a to your computer and use it in GitHub Desktop.
Edit Distance Visual Representor
package dynamic_programming;
import java.util.AbstractMap;
import java.util.HashMap;
import java.util.Map;
public class EditDistance {
public static void main(String[] args) {
if (args.length < 2) {
System.out.println("Please give proper args");
return;
}
String a = args[0];
String b = args[1];
boolean noSub = args.length > 2 && Boolean.parseBoolean(args[2]);
final int x = editDistance(a, b, noSub);
System.out.println("=========================");
System.out.println(x);
}
public static int editDistance(String a, String b, boolean noSub) {
if (a.equals(b)) {
return 0;
}
int aL = a.length();
int bL = b.length();
MinDist[][] minDist = new MinDist[aL + 1][bL + 1];
for (int i = 0; i <= aL; i++) {
for (int j = 0; j <= bL; j++) {
minDist[i][j] = new MinDist();
}
}
for (int i = 1; i <= aL; i++) {
minDist[i][0].setDist(1 + minDist[i - 1][0].getDist());
minDist[i][0].setParent(Operation.DELETION);
}
for (int i = 1; i <= bL; i++) {
minDist[0][i].setDist(1 + minDist[0][i - 1].getDist());
minDist[0][i].setParent(Operation.INSERTION);
}
Operation[] operationValues = Operation.values();
for (int i = 1; i <= aL; i++) {
for (int j = 1; j <= bL; j++) {
int[] operations = new int[operationValues.length];
operations[Operation.INSERTION.ordinal()] = 1 + minDist[i][j - 1].getDist();
operations[Operation.DELETION.ordinal()] = 1 + minDist[i - 1][j].getDist();
operations[Operation.SUBSTITUTION.ordinal()] = noSub ? Integer.MAX_VALUE : 1 + minDist[i - 1][j - 1].getDist();
if (a.charAt(i - 1) == b.charAt(j - 1)) {
operations[Operation.MATCH.ordinal()] = minDist[i - 1][j - 1].getDist();
minDist[i][j].setDist(operations[Operation.MATCH.ordinal()]);
minDist[i][j].setParent(Operation.MATCH);
continue;
}
operations[Operation.MATCH.ordinal()] = Integer.MAX_VALUE;
int shortest = operations[Operation.MATCH.ordinal()];
for (int k = 0; k < operations.length; k++) {
if (operations[k] < shortest) {
minDist[i][j].setDist(operations[k]);
minDist[i][j].setParent(operationValues[k]);
shortest = operations[k];
}
}
}
}
int parentI = -1;
int parentJ = -1;
Map<AbstractMap.SimpleEntry<Integer, Integer>, Operation> trail = new HashMap<>();
for (int i = aL; i >= 0; i--) {
for (int j = bL; j >= 0; j--) {
if (parentI == -1
|| i == parentI && j == parentJ) {
var entry = new AbstractMap.SimpleEntry<>(i, j);
if (i != 0 || j != 0) {
Operation parent = null;
switch (minDist[i][j].getParent()) {
case INSERTION -> {
parentI = i;
parentJ = j - 1;
parent = Operation.INSERTION;
}
case DELETION -> {
parentI = i - 1;
parentJ = j;
parent = Operation.DELETION;
}
case SUBSTITUTION -> {
parentI = i - 1;
parentJ = j - 1;
parent = Operation.SUBSTITUTION;
}
case MATCH -> {
parentI = i - 1;
parentJ = j - 1;
parent = Operation.MATCH;
}
}
trail.put(entry, parent);
}
}
}
}
int maxDist = 0;
for (MinDist[] min : minDist) {
for (var dist : min) {
maxDist = Math.max(maxDist, dist.dist);
}
}
int digits = (int) (StrictMath.log10(maxDist) + 1);
StringBuilder paddingBuilder = new StringBuilder(10);
while (digits > 1) {
paddingBuilder.append(" ");
digits--;
}
String padding = paddingBuilder.toString();
for (int i = -1; i <= aL; i++) {
for (int j = -1; j <= bL; j++) {
if (i == -1 && j == -1) {
System.out.print("| " + padding);
} else if (i == -1) {
if (j > 0) {
System.out.print("|" + ConsoleColors.PURPLE_BOLD + b.charAt(j - 1) + padding + ConsoleColors.RESET);
} else {
System.out.print("| " + padding);
}
if (j == bL) {
System.out.print("|");
}
} else if (j == -1) {
if (i > 0) {
System.out.print("|" + ConsoleColors.YELLOW_BOLD + a.charAt(i - 1) + padding + ConsoleColors.RESET);
} else {
System.out.print("| " + padding);
}
} else {
int dist = minDist[i][j].getDist();
var entry = new AbstractMap.SimpleEntry<>(i, j);
Operation operation = trail.get(entry);
int distDigits = (int) (StrictMath.log10(dist) + 1);
int paddingSub = padding.length();
while (distDigits > 1) {
paddingSub--;
distDigits--;
}
String paddingForDigits = padding.substring(0, paddingSub);
if (operation != null) {
final String color = getOperationColor(operation);
System.out.print("|" + color + dist + paddingForDigits + ConsoleColors.RESET);
} else {
System.out.print("|" + dist + paddingForDigits);
}
if (j == bL) {
System.out.print("|");
}
}
}
System.out.println();
}
return minDist[aL][bL].getDist();
}
private static String getOperationColor(Operation operation) {
String color = null;
switch (operation) {
case INSERTION -> color = ConsoleColors.BLUE_BOLD;
case DELETION -> color = ConsoleColors.RED_BOLD;
case SUBSTITUTION -> color = ConsoleColors.CYAN_BOLD;
case MATCH -> color = ConsoleColors.GREEN_BOLD;
}
return color;
}
static class MinDist {
private int dist;
private Operation parent;
public int getDist() {
return dist;
}
public void setDist(int dist) {
this.dist = dist;
}
public Operation getParent() {
return parent;
}
public void setParent(Operation parent) {
this.parent = parent;
}
}
enum Operation {
INSERTION,
DELETION,
SUBSTITUTION,
MATCH
}
public class ConsoleColors {
// Reset
public static final String RESET = "\033[0m"; // Text Reset
// Regular Colors
public static final String BLACK = "\033[0;30m"; // BLACK
public static final String RED = "\033[0;31m"; // RED
public static final String GREEN = "\033[0;32m"; // GREEN
public static final String YELLOW = "\033[0;33m"; // YELLOW
public static final String BLUE = "\033[0;34m"; // BLUE
public static final String PURPLE = "\033[0;35m"; // PURPLE
public static final String CYAN = "\033[0;36m"; // CYAN
public static final String WHITE = "\033[0;37m"; // WHITE
// Bold
public static final String BLACK_BOLD = "\033[1;30m"; // BLACK
public static final String RED_BOLD = "\033[1;31m"; // RED
public static final String GREEN_BOLD = "\033[1;32m"; // GREEN
public static final String YELLOW_BOLD = "\033[1;33m"; // YELLOW
public static final String BLUE_BOLD = "\033[1;34m"; // BLUE
public static final String PURPLE_BOLD = "\033[1;35m"; // PURPLE
public static final String CYAN_BOLD = "\033[1;36m"; // CYAN
public static final String WHITE_BOLD = "\033[1;37m"; // WHITE
// Underline
public static final String BLACK_UNDERLINED = "\033[4;30m"; // BLACK
public static final String RED_UNDERLINED = "\033[4;31m"; // RED
public static final String GREEN_UNDERLINED = "\033[4;32m"; // GREEN
public static final String YELLOW_UNDERLINED = "\033[4;33m"; // YELLOW
public static final String BLUE_UNDERLINED = "\033[4;34m"; // BLUE
public static final String PURPLE_UNDERLINED = "\033[4;35m"; // PURPLE
public static final String CYAN_UNDERLINED = "\033[4;36m"; // CYAN
public static final String WHITE_UNDERLINED = "\033[4;37m"; // WHITE
// Background
public static final String BLACK_BACKGROUND = "\033[40m"; // BLACK
public static final String RED_BACKGROUND = "\033[41m"; // RED
public static final String GREEN_BACKGROUND = "\033[42m"; // GREEN
public static final String YELLOW_BACKGROUND = "\033[43m"; // YELLOW
public static final String BLUE_BACKGROUND = "\033[44m"; // BLUE
public static final String PURPLE_BACKGROUND = "\033[45m"; // PURPLE
public static final String CYAN_BACKGROUND = "\033[46m"; // CYAN
public static final String WHITE_BACKGROUND = "\033[47m"; // WHITE
// High Intensity
public static final String BLACK_BRIGHT = "\033[0;90m"; // BLACK
public static final String RED_BRIGHT = "\033[0;91m"; // RED
public static final String GREEN_BRIGHT = "\033[0;92m"; // GREEN
public static final String YELLOW_BRIGHT = "\033[0;93m"; // YELLOW
public static final String BLUE_BRIGHT = "\033[0;94m"; // BLUE
public static final String PURPLE_BRIGHT = "\033[0;95m"; // PURPLE
public static final String CYAN_BRIGHT = "\033[0;96m"; // CYAN
public static final String WHITE_BRIGHT = "\033[0;97m"; // WHITE
// Bold High Intensity
public static final String BLACK_BOLD_BRIGHT = "\033[1;90m"; // BLACK
public static final String RED_BOLD_BRIGHT = "\033[1;91m"; // RED
public static final String GREEN_BOLD_BRIGHT = "\033[1;92m"; // GREEN
public static final String YELLOW_BOLD_BRIGHT = "\033[1;93m";// YELLOW
public static final String BLUE_BOLD_BRIGHT = "\033[1;94m"; // BLUE
public static final String PURPLE_BOLD_BRIGHT = "\033[1;95m";// PURPLE
public static final String CYAN_BOLD_BRIGHT = "\033[1;96m"; // CYAN
public static final String WHITE_BOLD_BRIGHT = "\033[1;97m"; // WHITE
// High Intensity backgrounds
public static final String BLACK_BACKGROUND_BRIGHT = "\033[0;100m";// BLACK
public static final String RED_BACKGROUND_BRIGHT = "\033[0;101m";// RED
public static final String GREEN_BACKGROUND_BRIGHT = "\033[0;102m";// GREEN
public static final String YELLOW_BACKGROUND_BRIGHT = "\033[0;103m";// YELLOW
public static final String BLUE_BACKGROUND_BRIGHT = "\033[0;104m";// BLUE
public static final String PURPLE_BACKGROUND_BRIGHT = "\033[0;105m"; // PURPLE
public static final String CYAN_BACKGROUND_BRIGHT = "\033[0;106m"; // CYAN
public static final String WHITE_BACKGROUND_BRIGHT = "\033[0;107m"; // WHITE
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment