Thomas Nilsen

Tushar Goel wrote:Just wondering the requirement in this case. Inorder generally performed on binary search tree. After performing swap, tree is no more abide the
pre-condition(left child is less than root and right child is greater than the root).

I just did inorder to get a look at the output, to see if my function worked.

I'm trying to write a function that performs a swap on all the children of nodes at a given depth.

Say we have a tree like this:

1 / \ 2 3

And an array containing the depth of nodes I want to perform a swap on.

If the array contains 1 then we swap all the childs of nodes at that depth. The tree would then look like this:

1 / \ 3 2

My function looks like this:

public void swap(TreeNode node, int[] swaps, int i, int arraySize, int depth) { if(arraySize == 0) return; if(depth < swaps[i]) { swap(node.left, swaps, i+1, arraySize-1, depth+1); } if(depth == swaps[i]) { TreeNode temp = node.left; node.right = temp; node.left = node.right; } if(depth != swaps[i]) { swap(node.right, swaps, i+1, arraySize-1, depth+1); } if(depth == swaps[i]) { TreeNode temp2 = node.left; node.right = temp2; node.left = node.right; } }

When I run this method on the example tree, and perform a inorder traversal of the tree, it gives me 2 1 2

I came across an interesting programming challenge, which I'm trying to solve.

In my mind Dijkstras algorithm is the best solution, since what they're essentially asking is to find the shortest path in a un-directed graph.

Here is my solution, but I don't get the correct answer, so I'd like some feedback on my code. Maybe my mistake is obvious.

Any help on the would truly be appreciated!

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class Solution { public static void main(String[] args) { //Read first line of input Scanner s = new Scanner(System.in); String[] constants = s.nextLine().split(" "); //CONSTANTS final int N = Integer.parseInt(constants[0]); final int H = Integer.parseInt(constants[1]); final int V = Integer.parseInt(constants[2]); //Datastructures List<Coordinate> junctions = new ArrayList<>(); List<Coordinate> paths = new ArrayList<>(); List<Vertex> vertices = new ArrayList<>(); //Read N junctions for(int i = 0; i < N; i++) { junctions.add(Coordinate.readInput(s)); } // Read N-1 paths between junctions for(int i = 0; i < N-1; i++) { paths.add(Coordinate.readInput(s)); } for(int i = 0; i < N; i++){ vertices.add(new Vertex(i+1, junctions.get(i))); } for(int i = 0; i < N - 1; i++){ int x = junctions.get(paths.get(i).getX() - 1).getX(); int x1 = junctions.get(paths.get(i).getY() - 1).getX(); int y = junctions.get(paths.get(i).getX() - 1).getY(); int y1 = junctions.get(paths.get(i).getY() - 1).getY(); Vertex vertex1 = vertices.get(paths.get(i).getX() - 1); Vertex vertex2 = vertices.get(paths.get(i).getY() - 1); double distance = Math.sqrt(Math.pow(x - x1, 2) + Math.pow(y - y1, 2)); vertex1.addNeighbour(new Edge(distance, vertex2)); vertex2.addNeighbour(new Edge(distance, vertex1)); } int h = 0; int v = 0; int unorderedPairs = 0; Algorithm a = new Algorithm(); for(int i = 0; i < N-1; i++) { a.shortestPath(vertices.get(paths.get(i).getX()-1)); for(Vertex vertex : a.getShortestPathTo(vertices.get(paths.get(i).getY()-1))) { h += Math.abs(h - vertex.getPoint().getX()); v += Math.abs(v - vertex.getPoint().getY()); } if (h > H || v > V) { unorderedPairs++; h = v = 0; } for(Vertex vtx : a.getShortestPathTo(vertices.get(paths.get(i).getY()-1))){ vtx.setMinDistance(0); vtx.setPreviousVertex(null); } } System.out.println(unorderedPairs); } } class Vertex implements Comparable<Vertex> { private int id; private List<Edge> adjacencyList; private Vertex previousVertex; private double minDistance = Double.POSITIVE_INFINITY; private Coordinate point; public Vertex(int id, Coordinate point) { this.id = id; this.point = point; this.adjacencyList = new ArrayList<>(); } public int getID() { return this.id; } public Coordinate getPoint() { return this.point; } public List<Edge> getAdjacencyList() { return this.adjacencyList; } public void addNeighbour(Edge edge) { this.adjacencyList.add(edge); } public Vertex getPreviousVertex() { return this.previousVertex; } public void setPreviousVertex(Vertex previousVertex) { this.previousVertex = previousVertex; } public double getMinDistance() { return this.minDistance; } public void setMinDistance(double minDistance) { this.minDistance = minDistance; } public int compareTo(Vertex other) { return Double.compare(this.minDistance, other.minDistance); } } class Edge { private double weight; private Vertex targetVertex; public Edge(double weight, Vertex targetVertex) { this.weight = weight; this.targetVertex = targetVertex; } public double getWeight() { return this.weight; } public void setWeight(double weight) { this.weight = weight; } public Vertex getTargetVertex() { return this.targetVertex; } public void setTargetVertex(Vertex targetVertex) { this.targetVertex = targetVertex; } } class Algorithm { public void shortestPath(Vertex startVertex) { startVertex.setMinDistance(0); PriorityQueue<Vertex> queue = new PriorityQueue<>(); queue.add(startVertex); while (!queue.isEmpty()) { Vertex actualVertex = queue.poll(); for (Edge edge : actualVertex.getAdjacencyList()) { Vertex v = edge.getTargetVertex(); double weight = edge.getWeight(); double currentDistance = actualVertex.getMinDistance() + weight; if (currentDistance < v.getMinDistance()) { queue.remove(v); v.setMinDistance(currentDistance); v.setPreviousVertex(actualVertex); queue.add(v); } } } } public List<Vertex> getShortestPathTo(Vertex targetVertex){ List<Vertex> path = new ArrayList<>(); for (Vertex vertex = targetVertex; vertex != null; vertex = vertex.getPreviousVertex()){ path.add(vertex); } Collections.reverse(path); return path; } } class Coordinate { private int x; private int y; Coordinate(int x, int y) { this.x = x; this.y = y; } public int getX() { return this.x; } public int getY() { return this.y; } public static Coordinate readInput(Scanner in) { String[] temp = in.nextLine().split(" "); return new Coordinate(Integer.parseInt(temp[0]), Integer.parseInt(temp[1])); } }

Tony Docherty wrote:

Do you have any specific date formats in mind?

How about 2 Mar 15 or 1/4/15 or dd-mm-(yy)yy (traditional Danish) or yyyy年m月d日 (Chinese)

Months as actual text which cannot be parsed to ints is a problem...

dd-mm-yyyy will work, but not with dd-mm-yy.

But, when you write year with only yy, how will one know if i mean 2020 or 1920 for example?

Knute Snortum wrote:I don't think it will validate mmddyy with or without separators. This is because the constructor always assumes day, month, year.

Not mmddyy, because I assume year is 4 digits. see my answer above for what date version it accepts right now..

Junilu Lacar wrote:But what happens when someone wants to validate a date that's not formatted in a way that you have defined in one of these enums? Seems like this design violates the Open-Closed Principle

Do you have any specific date formats in mind?

Right now it accepts:
DDMMYYYY
MMDDYYYY
YYYYMMDD

DD.MM.YYYY
MM.DD.YYYY
YYYY.MM.DD

DD-MM-YYYY
MM-DD-YYYY
YYYY-MM-DD

DD/MM/YYYY
MM/DD/YYYY
YYYY/MM/DD

Only thing I can think would be if one would set a 2 digit year (YY)?

Junilu Lacar wrote:Your choice of using an enum for this seems a little strange to me. It doesn't fit my mental model of an enum.

I actually worked "backwards".

I started out by asking myself - How do I want to call the validation method, and set the date format at the same time? Enum seemed like the most logical choice to me.
You could do so much more with enum in java as opposed to other languages.

I'm fairly new to java, and is just building small programs to get the feel for the language. Any tips on how I can improve this code would be greatly appreciated.


import java.util.Set; import java.util.HashSet; import java.util.Arrays; import java.util.regex.Matcher; import java.util.regex.Pattern; enum DateValidator { DDMMYYYY(0, 2, 4), MMDDYYYY(2, 0, 4), YYYYMMDD(6, 4, 0); private final int dayIndex; private final int monthIndex; private final int yearIndex; private DateValidator(int dayIndex, int monthIndex, int yearIndex) { this.dayIndex = dayIndex; this.monthIndex = monthIndex; this.yearIndex = yearIndex; } private int getDay(String date){ return Integer.parseInt(date.substring(dayIndex, dayIndex + 2)); } private int getMonth(String date){ return Integer.parseInt(date.substring(monthIndex, monthIndex + 2)); } private int getYear(String date){ return Integer.parseInt(date.substring(yearIndex, yearIndex + 4)); } private static boolean isLeapYear(int y) { return (y % 4 == 0) && ((y % 100 != 0) || (y % 400 == 0)); } private boolean isDateLegal(String date) { final int day = getDay(date); final int month = getMonth(date); final int year = getYear(date); boolean isValid = false; final Set<Integer> values = new HashSet<Integer>(Arrays.asList(1, 3, 5, 7, 8, 10, 12)); final int daysInFebruary = (month == 2 && isLeapYear(year)) ? 29 : 28; if (values.contains(month)) { isValid = day <= 31; } else if (month > 0 && month < 13 && month != 2) { isValid = day <= 30; } else if (month == 2) isValid = day <= daysInFebruary; return isValid; } private static boolean isDateFormatValid(String date) { final String DATE_PATTERN = "^([0-9]{2}\\.[0-9]{2}\\.[1-2][0-9]{3}|[0-9]{2}" + "\\-[0-9]{2}\\-[1-2][0-9]{3}|[0-9]{2}\\/[0-9]{2}" + "\\/[1-2][0-9]{3}|[0-9]{2}[0-9]{2}[1-2][0-9]{3}|[1-2][0-9]{3}" + "\\.[0-9]{2}\\.[0-9]{2}|[1-2][0-9]{3}\\-[0-9]{2}" + "\\-[0-9]{2}|[1-2][0-9]{3}\\/[0-9]{2}\\/[0-9]{2})$"; Pattern pattern = Pattern.compile(DATE_PATTERN); Matcher matcher = pattern.matcher(date); return matcher.matches(); } public boolean validate(String date) { return isDateLegal(date.replaceAll("[\\.\\-\\/]", "")) && isDateFormatValid(date); } } class Main { public static void main(String[] args) { System.out.print(DateValidator.DDMMYYYY.validate("16.10.1990") ? "Date is valid" : "Date is NOT valid"); } }