Sequence Predictor
Your program should read in command-line arguments with the following structure:
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[0]);
// Get the spacing
double spacing = Double.valueOf(args[1]);
// 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();
}
}