#ifndef LONGESTNONDECREASINGSUBSEQUENCE_H
#define LONGESTNONDECREASINGSUBSEQUENCE_H

#include<vector>

class Position {
  private:
    int number;
    int max_sub_sequence;
    Position *Parent;
    int index;
  public:
    void update_number(int temp) {number = temp;}
    void update_max(int temp) {max_sub_sequence = temp;}
    void update_parent(Position *temp) {Parent = temp;}
    void update_index(int temp) {index = temp;}
    int get_index() {return index;}
    Position * get_parent() { return Parent;}
    int get_max() {return max_sub_sequence;}
    int get_number() {return number;}
    Position(int temp_number);
    void display();
};

void getInput();
void computeMaxSub();
void displayResults();

std::vector<Position> sequence;

#endif

/*
 *  Andrew Donley 
 *  Dynamic Programming Problem:
 *  Longest NonDecreasing Subsequence
 *  June 18th, 2013
 */

#include "LongestNonDecreasingSubsequence.h"
#include<iostream>
#include<string>
#include<sstream>

using namespace std;

int main() {
  getInput();
  computeMaxSub();
  displayResults();
  return 0;
}

Position::Position(int temp_number) {
  number = temp_number;
  max_sub_sequence = 1;
}

void Position::display() {
  cout << endl << "Number: " << number << ", Index: " << index << ", Max: " << max_sub_sequence;
  return;
}

/*
 *  Gets the sequence from user input
 */
void getInput() {

  string input;
  int val, index = 0;
  Position *temp;

  cout << endl;
  cout << "Longest Non-Decreasing Subsequence" << endl;
  cout << "==================================" << endl;
  cout << "Please enter a sequence of numbers deliniated by spaces." << endl;
  cout << "Press 'return' to submit the sequence." << endl;
  getline(cin, input);

  istringstream iss(input);

  // Store the items
  while(iss >> val) {
    temp = new Position(val);
    temp->update_index(index);
    sequence.push_back(*temp);
    index++;
    delete temp;
  }

  return;
}

/*
 *  Computes the longest subsquence
 */
void computeMaxSub() {

  int largest_sub = 0;
  Position * temp_parent = NULL;

  for(vector<Position>::iterator i = sequence.begin(); i != sequence.end(); ++i) {
    for(int j = 0; j < i->get_index(); j++) {
      if(i->get_number() >= sequence.at(j).get_number() && sequence.at(j).get_max() > largest_sub) {
        largest_sub = sequence.at(j).get_max();
        temp_parent = &sequence.at(j);
      }
    }
    // Update the largest increasing subsequence
    i->update_parent(temp_parent);
    i->update_max(largest_sub+1);
    // Reset the values
    largest_sub = 0;
    temp_parent = NULL;

  }
  return;
}

/* 
 *  Outputs the longest subsequence to stdout
 */
void displayResults() {
  int largest = 0;
  Position * temp_position;
  vector<Position> output;

  for(vector<Position>::iterator i = sequence.begin(); i != sequence.end(); i++) {
    if(i->get_max() > largest) {
      largest = i->get_max();
      temp_position = &*i;
    }
  }

  while(temp_position != NULL) {
    output.push_back(*temp_position);
    temp_position = temp_position->get_parent();
  }

  cout << endl << "The longest subsequence had length: " << output.front().get_max() << endl << endl;

  while(!output.empty()) {
    cout << output.back().get_number();
    if(output.size() > 1)
      cout << " -> ";
    else
      cout << endl << endl;

    output.pop_back();
  }

  return;
}

/*
 * Interview Question at insideVault
 */

import java.lang.*;
import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;

public class CopyPasteProblem {
	
	public class KeyStroke {
		
		int numberOfA;
		int buffer; // Buffer value at a particular Keystroke
		int indexOfParent;  // To we can view the optimal solution
		
		public KeyStroke(int tempA, int tempBuff) {
			numberOfA = tempA;
			buffer = tempBuff;
			indexOfParent = 0;
		}
		
		public KeyStroke(int tempA, int tempBuff, int tempParent) {
			numberOfA = tempA;
			buffer = tempBuff;
			indexOfParent = tempParent;
		}	
	}
	
	ArrayList <KeyStroke>strokes;
	
	public CopyPasteProblem() {
		// Initialize the Strokes (ArrayList to be able to access
		//   an index very quickly)
		strokes = new ArrayList<KeyStroke>();
	}
	
	public void printStroke(KeyStroke key) {
		System.out.printf("A's = %8d, Buffer = %8d, Parent = %8d\n", key.numberOfA, key.buffer, key.indexOfParent);
	}
	
	public void printAllStrokes() {
		for(int i = 0; i < strokes.size(); i++) {
			System.out.print(i + ": ");
			printStroke(strokes.get(i));
		}
	}
	
	public void printResults() {
		System.out.printf("\nThe min number of keystrokes was %d and the final value of those keystrokes was %d. \n\n", strokes.size()-1, strokes.get(strokes.size() -1 ).numberOfA);
	}
	
	public void calculateOptomization(int numberToOptimize) {
		
		KeyStroke tempStroke = new KeyStroke(0,0);
		strokes.add(tempStroke);
		
		// strokes.get is constant because its an arraylist
		for(int i = 1; strokes.get(i-1).numberOfA <= numberToOptimize; i++ ) {
			
			// This has to do with the recurance. Nothing in the buffer until there is a select-all, copy, paste
			if(i - 6 >= 0) {
				// Have to find max at this stage. I'm keeping the values in terms of their object - list access form
				//   to accententuate the dynamic side of what's going on. Still constant access time because of ArrayList.
				
				// Case :If doing select all , copy, paste yields the max value for this many keystrokes
				if(strokes.get(i-6).numberOfA * 2 >= strokes.get(i-1).numberOfA + 1
						&& strokes.get(i-6).numberOfA * 2 >= strokes.get(i-2).numberOfA + strokes.get(i-2).buffer) {
					
					tempStroke = new KeyStroke(strokes.get(i-6).numberOfA * 2, strokes.get(i-6).numberOfA ,i-6);
					strokes.add(tempStroke);
					
				}
				// Case: If doing paste from the buffer yields the max value for this number of keystrokes 
				else if(strokes.get(i-2).numberOfA + strokes.get(i-2).buffer >= strokes.get(i-6).numberOfA * 2
						&& strokes.get(i-2).numberOfA + strokes.get(i-2).buffer >= strokes.get(i-1).numberOfA + 1) {
					
					tempStroke = new KeyStroke(strokes.get(i-2).numberOfA + strokes.get(i-2).buffer ,strokes.get(i-2).buffer ,i-2);
					strokes.add(tempStroke);
					
				}
				// Case: If pressing A to add one a yields the max number of 'a's for this number of keystrokes
				else {
					
					tempStroke = new KeyStroke(strokes.get(i-1).numberOfA + 1,strokes.get(i-1).buffer ,i-1);
					strokes.add(tempStroke);
					
				}
			}
			else { // There is nothing in the clip board until you select-all, copy, paste 
				tempStroke = new KeyStroke(strokes.get(i-1).numberOfA + 1,strokes.get(i-1).buffer ,i-1);
				strokes.add(tempStroke);
			}
		}
		
	}
	
	public void otherResults() {
		boolean quit = false;
		int val;
		
		do {
			System.out.println("-----------------------------------------");
			System.out.println("Press 1 to see the results path");
			System.out.println("Press 2 to print maxes at every keystroke");
			System.out.println("Press anything else to quit");
			System.out.println("-----------------------------------------");
			val = getInput();
			System.out.print("\n");
			switch(val) {
				case 1:
					printResultPath();
					break;
				case 2:
					printAllStrokes();
					break;
				default:
					quit = true;
					break;
			}
			
		} while (!quit);
	}
	
	public int getInput() {
		
		int val;
		Scanner in = new Scanner(System.in);
		val = in.nextInt();
		return val;
		
	}
	
	public void printResultPath() {
		
		boolean finished = false;
		int index = strokes.size()-1, distance;
		ArrayList <KeyStroke>path = new ArrayList<KeyStroke>();
		ArrayList <String>humanReadablePath = new ArrayList<String>();
		
		while(!finished) {
			path.add(strokes.get(index));
			distance = index - strokes.get(index).indexOfParent;
			
			if(distance > 2) {
				humanReadablePath.add(new String("Select-All, Copy, Paste"));
			}
			else if (distance == 2) {
				humanReadablePath.add(new String("Paste                  "));
			}
			else {
				humanReadablePath.add(new String("Press a                "));
			}
			index = strokes.get(index).indexOfParent;
			if(index == 0) {
				path.add(strokes.get(index));
				finished = true;
			}
		}
		
		for(int i = humanReadablePath.size()-1; i >= 0; i--) {
			System.out.printf("%s %10d 'a's\n", humanReadablePath.get(i),path.get(i).numberOfA);
		}
		
		// This was used to print out all info about the path.
		// Not useful information.
		/* for(int i = path.size()-1; i >= 0; i--) {
			printStroke(path.get(i));
		} */
		
		System.out.print("\n");
	}
	
	public static void main(String [] args) {
		
		CopyPasteProblem cpy = new CopyPasteProblem();
		
		System.out.println("\nHow many 'a's would you like to produce with the minimum amount of keystrokes?");
		
		int numberToOptimize = cpy.getInput();
		
		cpy.calculateOptomization(numberToOptimize);
		
		cpy.printResults();
		
		cpy.otherResults();
			
		return;
	}
		
}

$ gcc LinkedListLoopDetection.c -o LinkedListLoopDetection
$ ./LinkedListLoopDetection < nodes.txt

#include<stdio.h>
#include<stdlib.h>

// Functions
void listInitialize();
void detectLoop();

// List Node Struct
struct Node {

  struct Node * next;
  int info;

};

// Globals
struct Node * list;
int numberOfNodes;
int loopBegin; // This is the node where the loop starts in the list

int main() {

  listInitialize();
  detectLoop();

  return 0;
}

void detectLoop() {

  // Going to use two pointers to traverse the list.
  struct Node *iter1 = list, *iter2 = list;

  while(iter1->next != NULL) {

    iter1 = iter1->next;
    // If iter1 equals iter2 we know there is a loop
    // Also if iter1->next equals NULL we know there is no loop
    if(iter1 == iter2 || iter1->next == NULL)
      break;
    // Move iter a second time
    iter1 = iter1->next;

    // Check Equality Again
    if(iter1 == iter2)
      break;
    else
      // Move iter2 by one
      iter2 = iter2->next;

  }

  // If there is there is a NULL pointer we know we reached
  //   the end of the list
  if(iter1->next == NULL)
    printf("%s\n","There was no loop in this Linked List.");
  // Otherwise the while loop broke because it found a loop
  //   in the Linked List
  else
    printf("%s\n","There was a loop in the Linked List.");

  return;
}

/* 
 * Reads in file and initializes the list including a loop
 * if specified.
 */
void listInitialize () {
  char temp[256];
  int i;
  // This is to keep track of place in list
  struct Node *iter, *iter2;
  // Read in number of nodes
  fgets(temp,256,stdin);
  numberOfNodes = atoi(temp);
  // Read in loop beginning node
  fgets(temp,256,stdin);
  loopBegin = atoi(temp);

  for(i = 0; i < numberOfNodes; i++) {
    // Throw this guy on the heap
    if(i == 0) {
      iter = (struct Node *)malloc(sizeof(struct Node));
      list = iter;
    }
    iter->next = (struct Node *)malloc(sizeof(struct Node));
    fgets(temp,256,stdin);
    iter->info = atoi(temp);
    // Don't want to move to next on the last iteration
    if(i < numberOfNodes - 1) {
      iter = (*iter).next;
    }
    else
      // Get rid of unnecessary allocation
      free(iter->next);
  }


  // Negative Value means create no loop
  if(loopBegin >= 0) {
    // Initialize iter2 to head of the list
    iter2 = list;

    for(i = 0; i < loopBegin; i++) {
      // Get to the spot where we want to create the loop
      iter2 = iter2->next;
    }
    // Create the Loop
    iter->next = iter2;
  }
  else {
    // Create no Loop
    iter->next = NULL;
  }

  return;
}

import java.util.LinkedList;
import java.lang.Integer;
import java.io.*;

public class IntToList {

  private LinkedList<Integer> converted;
  private Integer toBeConverted;


  public static void main(String [] argv) {

	// Create a IntToList Object to use during conversion
	IntToList obj;
	
    // Create a buffered reader to read the integer
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    // To be used to get the input of a file
    String input;
    System.out.printf("%s: ","Please enter an integer to convert");

    try {
      // Read in the user input
      input = in.readLine();

      // Convert the string to an int using library functions
      obj = new IntToList(Integer.valueOf(input));

      obj.convertToList();
      obj.printList();

    } catch (NumberFormatException N) {  // Catch a non-integer input or too large input
  	  System.out.printf("%s\n","Please enter an integer.");
    } catch (Exception E) { // Everything else
      E.printStackTrace();
    }

    return;

  }

  public IntToList(Integer input) {
	  // Initializations
	  toBeConverted = input.intValue();
	  converted = new LinkedList<Integer>();
  }

  public void convertToList() {

    int temp = toBeConverted.intValue(), remainder;

    // Once the integer is equal to zero, there are no more single digits to extract
    while(temp > 0) {
    	
      // This remainder will be committed to the list of integers
      remainder = temp % 10;

      // This will add the integer to the front of the list
      converted.addFirst(new Integer(remainder));

      // This will remove a power of 10 from the read in integer, casted to not be a double
      temp = (int)Math.floor(temp / 10);
    }

  }

  public void printList() {
	
    System.out.print("Converted Integer to List: ");
	
    // Print out all the single digits in the list
    for (Integer i : converted) {
    	System.out.print(i);
    }

    System.out.print("\n");

  }

}