# Sequence Prediction using Java Assignment Solution

## Sequence Predictor

NUMITERATIONS NUMSPACES SEQUENCENUM...

Where

NUMITERATIONS is the amount of numbers to produce in the given sequence NUMSPACES is the number of spaces between numbers in the sequence

when printing out the sequences.

SEQUENCENUM... is the sequence of numbers that the program will produce more numbers for

For example: java Main 3 5 1 2 4 8 16 31 57 99 163

Produces Solution:

Main:

``` import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** * This program produces the next N numbers in a given sequence using * the method seen here: https://www.youtube.com/watch?v=4AuV93LOPcE * In doing this it prints out the all the steps it takes to produce * the next step. * * It takes in command line arguments as follows: * * NUMITERATIONS NUMSPACES SEQUENCENUM... * * Where * NUMITERATIONS is the amount of numbers to produce in the given sequence * NUMSPACES is the number of spaces between numbers in the sequence * when printing out the sequences. * SEQUENCENUM... is the sequence of numbers that the program will produce * more numbers for * * For example: java Main 3 5 1 2 4 8 16 31 57 99 163 * Produces: * * 1 2 4 8 16 31 57 99 163 * 1 2 4 8 15 26 42 64 * 1 2 4 7 11 16 22 * 1 2 3 4 5 6 * 1 1 1 1 1 * * 1 2 4 8 16 31 57 99 163 256 * 1 2 4 8 15 26 42 64 93 * 1 2 4 7 11 16 22 29 * 1 2 3 4 5 6 7 * 1 1 1 1 1 1 * * 1 2 4 8 16 31 57 99 163 256 386 * 1 2 4 8 15 26 42 64 93 130 * 1 2 4 7 11 16 22 29 37 * 1 2 3 4 5 6 7 8 * 1 1 1 1 1 1 1 * * 1 2 4 8 16 31 57 99 163 256 386 562 * 1 2 4 8 15 26 42 64 93 130 176 * 1 2 4 7 11 16 22 29 37 46 * 1 2 3 4 5 6 7 8 9 * 1 1 1 1 1 1 1 1 */ public class Main { public static void main(String[] args) { // TODO: Fill out the below functions or create your own solution // Get the count of numbers to be calculated int N = Integer.valueOf(args); // Get the spacing double spacing = Double.valueOf(args); // Get the numbers of the initial sequence // test sequence List ints_str = new ArrayList(); for(int i = 2; i < args.length; i++) ints_str.add(args[i]); // List of number sin Integer form List numbers = parseInput(ints_str); // Create sequence Sequence seq = new Sequence(numbers); List sequences = initializeGrid(seq); System.out.println(gridToString(spacing, sequences)); // Print the initial grid for(int i = 0; i < N; i++) { generateNextTerms(sequences); System.out.println(gridToString(spacing, sequences)); } } /** * Transforms a list of Strings into a list of Integers * @param args String list to be transformed * @return Integer list parsed from Strings */ private static List parseInput(List args) { List ints = new ArrayList(); for(String x: args) ints.add(Integer.valueOf(x)); return ints; } /** * Creates the initial "grid" of sequences by taking the initial * sequence and taking the difference iteratively until it reaches * a sequence where all the numbers in the sequence are the same. * @param sequence Seed sequence that dictates the other sequences * @return A list of sequences where each subsequent sequence is the difference of the previous one */ private static List initializeGrid(Sequence sequence) { // Create list of Sequence List sequences = new ArrayList(); Sequence currentSeq = sequence; sequences.add(currentSeq); while(!bottomOfGrid(currentSeq)) { // Calculate the diff Sequence diff_seq = sequenceDifference(currentSeq); // add this new sequence to the list of sequences sequences.add(diff_seq); // save into the currentSeq variable currentSeq = diff_seq; } return sequences; } /** * Tests if the given sequence contains all the same integers. * @param sequence input sequence * @return true if all integers in the sequence are the same, false otherwise */ private static boolean bottomOfGrid(Sequence sequence) { for(int i = 0; i < sequence.size(); i++) { if(sequence.get(i) != 1) return false; } return true; } /** * Takes the difference of the sequence. The resulting sequence is produced * as follows: * newSequence[i] = sequence[i+1] - sequence[i] * @param sequence input sequence * @return difference of input sequence */ private static Sequence sequenceDifference(Sequence sequence) { // First, create the List tht will store the result List new_numbers = new ArrayList(); // iterate through the pair of numbers in the sequence Iterable> res = sequence.pairWiseIterator(); Iterator> iter = res.iterator(); while(iter.hasNext()) { Pair thing = iter.next(); // Calculate difference int diff = thing.getSnd() - thing.getFst(); // Store in list new_numbers.add(diff); } // Now, create the new sequence return new Sequence(new_numbers); } /** * Prints out the given "grid" of sequences. The spacing parameter determines * the number of spaces between each integer in a sequence. The number of spaces * at the beginning of the line is determined by the following equation: * * ceil(spacing / 2) * lineNumber * * For example on line number 2 with a spacing of 5 the number of spaces at the * beginning of the line would be: * * ceil(5 / 2) * 2 = ceil(2.5) * 2 = 3 * 2 = 6 * * Line numbers start at 0. * @param spacing amount of space between elements of each sequence * @param sequences list of sequences to be printed * @return String that represents the visual representation of the given "grid" */ private static String gridToString(double spacing, List sequences) { int lineNumber = 0; String ret = ""; for(int i = 0; i < sequences.size(); i++) { Sequence sequence = sequences.get(i); // Calculate number of spaces double n = Math.ceil(spacing / 2.0) * lineNumber; // Now print if(n > 0) ret += String.format("%" + String.valueOf(n) + "s", ""); // print numbers for(int j = 0; j < sequence.size(); j++) { ret += String.format("%d", sequence.get(j)); if(j < sequence.size() -1) ret += String.format("%" + (int)spacing + "s", ""); } ret += "\n"; lineNumber++; } return ret; } /** * Generates the next term for each sequence in the given "grid" * @param sequences "grid" to produce the next term for */ private static void generateNextTerms(List sequences) { // To generate the terms we must go from the last sequence to the first for(int i = 0; i < sequences.size(); i++) { int idx = sequences.size()-i-1; Sequence sequence = sequences.get(idx); if(idx == sequences.size() -1) // we are in the last sequence, filled with ones. So the new term is just an additional one { sequence.add(1); } else { // Get the previous sequence Sequence prev = sequences.get(idx+1); // Get last term int term_prev = prev.get(prev.size()-1); // Now, get last term in the current sequence int term_curr = sequence.get(sequence.size()-1); // Add these terms int new_term = term_curr + term_prev; // Add this new term to the current sequence sequence.add(new_term); } } } } ```

Pair:

``` import java.util.Objects; /** * Generic pair that hold two pieces of data */ public class Pair { private final T fst; private final V snd; public Pair(T fst, V snd) { this.fst = fst; this.snd = snd; } public T getFst() { return fst; } public V getSnd() { return snd; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Pair pair = (Pair) o; return fst.equals(pair.fst) && snd.equals(pair.snd); } @Override public int hashCode() { return Objects.hash(fst, snd); } } ```

Sequence:

``` import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** * Represents a sequence of Integers. * Backed by a list of integers. * Defines two iterables, one that iterates over the * backing list normally, elementwise. * The other iterates over the list pairwise. */ public class Sequence { private final List sequence; public Sequence(List sequence) { this.sequence = sequence; } public void add(Integer i) { sequence.add(i); } public Integer get(int index) { return sequence.get(index); } public int size() { return sequence.size(); } public Iterable elementWiseIterator() { return new Iterable<>() { @Override public Iterator iterator() { return sequence.iterator(); } }; } /** * Defines a pairwise iterator for the sequence. * Pairwise iteration iterates over the list in pairs. * For example with the following sequence: [1,2,3] * Pairwise iteration would first return (1,2) then (2,3) * then stops. */ public Iterable> pairWiseIterator() { // TODO: Replace return null with your code // Create list of Pairs List> pairs = new ArrayList>(); for(int i = 0; i < sequence.size()-1; i++) { int x = sequence.get(i); int y = sequence.get(i+1); Pair pair = new Pair(x,y); pairs.add(pair); } Iterable> iterable = (Iterable>)pairs; return iterable; } @Override public String toString() { return sequence.toString(); } } ```