Skeleton for report, small solver changes

diff --git a/LubbersReport.tex b/LubbersReport.tex
index b2a9422..abda695 100644 (file)
--- a/LubbersReport.tex
+++ b/LubbersReport.tex
@@ -1,11 +1,20 @@
 \documentclass{article}
 
+\usepackage{listings}
 \usepackage[dvipdfm]{hyperref}
 
+\lstset{
+       basicstyle=\footnotesize,
+       breaklines=true,
+       numbers=left,
+       numberstyle=\tiny,
+       tabsize=2
+}
+
 \author{
        Mart Lubbers\\
        s4109503\\
-       \url{mailto:mart@martlubbers.net}
+       \href{mailto:mart@martlubbers.net}{mart@martlubbers.net}
 }
 \title{Complexity Assignment}
 \date{\today}
@@ -13,9 +22,46 @@
 \begin{document}
 \maketitle
 \tableofcontents
-\section{Introduction}
+\newpage
+
+\section{Problem description}
+\begin{center}
+       \textit{
+               Every day children come to the zoo to take care of the pets. After an
+               introductory meeting with all the pets, the kids are given one pet to
+               exclusively take care of for the rest of the visit. However, certain pets
+               do not go on well with certain kids, and vice-versa. Pets are also not
+               immortal; and the groups vary in size from time to time. Because these pets
+               require very special attention, exactly one child can take care of a single
+               pet. This implies that sometimes a child does not have a pet to take care
+               for and sometimes a pet is left without a caretaker.
+       }
+\end{center}
+
+The assignment is to implement a \textit{\href{http://www.java.com}{Java}}
+program that optimizes the assignment of pets to children so that the sum of
+all the compatibility values between pets and children is the maximum possible.
 
 \section{Implementation}
+\subsection{Brute Force}
+The first approach was to implement a brute force algorithm which calculates
+every possible combination of pets and children and then takes the one with the
+highest value. This corresponds with the pseudocode specified in
+Listing~\ref{lst:brute_force}. The algorithm, due to calculating all the values
+has a minimal complexity of $n!$. This is because there are $n!$ permutations
+possible for $n$ children.
+\begin{lstlisting}[
+       caption={Brute Force approach},
+       label={lst:brute_force},
+       keywords={[3]loop,put,return}
+]
+n! - loop over all permutations
+c1 -   put compatibility in list
+c1 - return maximum compatibility rating from list
+\end{lstlisting}
+
+
+\subsection{Improvements}
 
 \section{Conclusion}
 

diff --git a/LubbersSolver.java b/LubbersSolver.java
index bdb4ded..571bb26 100755 (executable)
--- a/LubbersSolver.java
+++ b/LubbersSolver.java
@@ -77,27 +77,15 @@ public class LubbersSolver implements IPetproblemSolver {
                for(int i = 0; i<n; i++){
                        possibilities[i] = i>=m ? -1 : i;
                }
-               if(m<=n){
-                       System.out.println("Wierd shizzleeee");
-                       List<int[]> ps = new LinkedList<int[]>();
-                       permute(possibilities, 0, ps);
-                       for(int[] i : ps){
-                               System.out.println(computeCompatibility(compatibility, i) + ": " + Arrays.toString(i));
-                       }
-                       System.exit(0);
 
-                       return Collections.max(ps, new Comparator<int[]>(){
-                               @Override
-                               public int compare(int[] a, int[] b){
-                                       return computeCompatibility(compatibility, a) - computeCompatibility(compatibility, b);
-                               }
-                       });
-               }
-               else {
-                       System.out.println("not equal...");
-                       return new int[n];
-                       //return null;
-               }
-               
+               List<int[]> ps = new LinkedList<int[]>();
+               permute(possibilities, 0, ps);
+
+               return Collections.max(ps, new Comparator<int[]>(){
+                       @Override
+                       public int compare(int[] a, int[] b){
+                               return computeCompatibility(compatibility, a) - computeCompatibility(compatibility, b);
+                       }
+               });
        }
 }