Jon.Koehmstedt
BAN USERimport java.util.ArrayList;
import java.util.Arrays;
public class main{
public static String findPath(String absolutePath, String relativePath) {
ArrayList<String> absolutePaths = new ArrayList<String>(Arrays.asList(absolutePath.split("/")));
String[] relativePaths = relativePath.split("/");
int lastIndex = absolutePaths.size()-1;
System.out.println(absolutePaths);
for (int i=0; i<relativePaths.length; i++) {
if (relativePaths[i].equals("..") && lastIndex>=0) {
absolutePaths.remove(lastIndex);
lastIndex--;
System.out.println("REMOVED "+absolutePaths);
} else {
absolutePaths.add(relativePaths[i]);
lastIndex++;
System.out.println("ADDED "+absolutePaths);
}
}
StringBuilder sb = new StringBuilder();
for (String s : absolutePaths)
{
sb.append(s);
sb.append("/");
}
return sb.toString();
}
public static void main(String []args){
System.out.println(findPath("/usr/bin/mail", "../../../etc/xyz/../abc"));
}
}
This sorts the numbers from highest to smallest, and then starts with the highest number, adding it to the next consecutively until it reaches the target or higher. In the case it's higher, it skips that number and moves on. Doing this for every possible set starting with the highest number. If it can't find a solution with the highest number, it then moves to the next highest and repeats. By starting with the highest number, often the answer if found fairly quickly.
Sort of like making change for a purchase - you start with quarters if possible and then move to dimes, nickles, pennies, etc.
Downside: I made my own LinkedList which may not have been necessary but it works.
import java.util.ArrayList;
import java.util.Scanner;
//take a set of numbers and check if the later portion can add up to the first number in a unique way
public class AddChecker{
private int target;
private LinkedList nums;
private static Scanner keyboard = new Scanner(System.in);
private ArrayList<Integer> answers;
public AddChecker(int target, LinkedList nums){
this.target = target;
this.nums = nums;
}
public void findUniqueSum() {
System.out.println("Target number is: "+target);
if (nums.sum>=target){ // If the sum of all numbers entered is less than target, return false
int sum = 0;
Node list = nums.front;
while (list != null){
answers = new ArrayList<Integer>();
sum = findUniqueSum(list, sum);
if (sum==target) { // Solution Found
System.out.print("A unique solution is: ");
System.out.print(answers.toString());
return;
}
else { //Solution not found, move to next highest number and try that.
answers = new ArrayList<Integer>();
sum=0;
list = list.next;
}
}
}
System.out.println("No Solution");
}
private int findUniqueSum(Node node, int sum){
if (node == null) return sum;
if (sum+node.data<=target) {
sum+=node.data;
answers.add(node.data);
if (sum==target) return sum; // Found solution, break recursion
}
sum = findUniqueSum(node.next, sum);
return sum;
}
private static class Node {
public int data;
public Node next;
public Node(int data){
this.data = data;
}
public String toString(){
StringBuffer print = new StringBuffer(""+data);
Node temp = next;
while (temp!=null){
print.append(", "+temp.data);
temp=temp.next;
}
return print.toString();
}
}
private static class LinkedList {
public Node front, current;
public int sum;
public void sortedAdd(int data){
sum+=data;
Node insert = new Node(data);
if (front == null || front.data<data){
insert.next = front;
front = insert;
} else {
current = front;
while (current.next!=null){
if (current.next.data<data){
insert.next = current.next;
current.next = insert;
return;
}
current = current.next;
}
current.next = insert;
}
}
public String toString(){
if (front==null) return "";
StringBuffer print = new StringBuffer(""+front.data);
current = front.next;
while (current!=null){
print.append(", "+current.data);
current = current.next;
}
return print.toString();
}
}
public static void main(String[] args){
System.out.println("please enter a set of numbers separated by spaces (end line with 'x')");
LinkedList nums = new LinkedList();
int sum = keyboard.nextInt();
while(keyboard.hasNextInt()){
int nextInt = keyboard.nextInt();
nums.sortedAdd(nextInt);
}
AddChecker checkThis = new AddChecker(sum, nums);
checkThis.findUniqueSum();
}
}
Sorry, I didn't see that criteria of only printing up to 80, I updated the code to have a "max" value that each line is then divided by and multiplied by 80, to give a relative histogram.
- Jon.Koehmstedt March 24, 2014