rlm@0: #+title: Discovering Effective Pokemon Types Using Linear Optimization
rlm@0: #+author: Robert McIntyre & Dylan Holmes
rlm@0: #+EMAIL:     rlm@mit.edu
rlm@0: #+MATHJAX: align:"left" mathml:t path:"../MathJax/MathJax.js"
rlm@0: #+STYLE: <link rel="stylesheet" type="text/css" href="../css/aurellem.css" />
rlm@0: #+OPTIONS:   H:3 num:t toc:t \n:nil @:t ::t |:t ^:t -:t f:t *:t <:t
rlm@2: #+SETUPFILE: ../../aurellem/org/level-0.org
rlm@2: #+INCLUDE: ../../aurellem/org/level-0.org
rlm@2: #+BABEL: :mkdirp yes
rlm@0: 
rlm@0: 
rlm@0: * Introduction
rlm@0: In the [[./types.org][previous post]], we used the best-first search algorithm to
rlm@0: locate the most effective Pok\eacute{}mon type
rlm@0: combinations. Afterwards, we realized that we could transform this
rlm@0: search problem into a /linear optimization problem/.  This conversion
rlm@0: offered several advantages: first, search algorithms are comparatively
rlm@0: slow, whereas linear optimization algorithms are extremely fast;
rlm@0: second, it is difficult to determine whether a search problem has any
rlm@0: solution, whereas it is straightforward to determine whether a linear
rlm@0: optimization problem has any solution; finally, because systems of
rlm@0: linear equations are so common, many programming languages have linear
rlm@0: equation solvers written for them.
rlm@0: 
rlm@0: In this article, we will 
rlm@0:  - Solve a simple linear optimization problem in C :: We demonstrate
rlm@0:       how to use the linear programming C library, =lp_solve=, to
rlm@0:       solve a simple linear
rlm@0:       optimization problem.
rlm@0:  - Incorporate a C library into Clojure :: We will show how we gave
rlm@0:       Clojure access to the linear programming C library, =lp_solve=.
rlm@0:  - Find effective Pokemon types using linear programming :: Building
rlm@0:       on our earlier code, (...)
rlm@0: - Present our results :: (!)
rlm@0:  
rlm@0: #which can be represented and solved as a system of linear equations.
rlm@0:   
rlm@0: * COMMENT  
rlm@0: This post continues the [[./types.org][previous one]] about pok\eacute{}mon types. 
rlm@0: Pok\eacute{}mon is a game in which adorable creatures battle each
rlm@0: other using fantastic attacks.  It was made into a several gameboy
rlm@0: games that all share the same battle system.  Every pok\eacute{}mon in the
rlm@0: gameboy game has one or two /types/, such as Ground, Fire, Water,
rlm@0: etc. Every pok\eacute{}mon attack has exactly one type. Certain defending
rlm@0: types are weak or strong to other attacking types.  For example, Water
rlm@0: attacks are strong against Fire pok\eacute{}mon, while Electric attacks are
rlm@0: weak against Ground Pok\eacute{}mon.  In the games, attacks can be either
rlm@0: twice as effective as normal (Water vs. Fire), neutrally effective
rlm@0: (Normal vs. Normal), half as effective (Fire vs. Water), or not
rlm@0: effective at all (Electric vs. Ground).  Thus the range of defense
rlm@0: values for a particular type is the set 0, 1/2, 1, 2. These are
rlm@0: referred to in the game as being immune, resistant, neutral, and
rlm@0: weak, respectively. I call them the /susceptance/ of one type to another.
rlm@0: 
rlm@0: If a pokemon has two types, then the strengths and weakness of each
rlm@0: type are /multiplied/ together.  Thus Electric (2x weak to Ground)
rlm@0: combined with Flying (immune to Ground (0x)) is immune to
rlm@0: Ground.  Fire (2x weak to Water) combined with Water (1/2x resistant
rlm@0: to Water) is neutral to Water. If both types are resistant to another
rlm@0: type, then the combination is doubly-resistant (1/4x) to that type. If
rlm@0: both types are weak to a certain type then the combination is
rlm@0: double-weak (4x) to that type.
rlm@0: 
rlm@0: ** Immortal Types
rlm@0: 
rlm@0: In the game, pok\eacute{}mon can have either one type, or two types. If this
rlm@0: restriction is lifted, is there any combination of types that is
rlm@0: resistant to all types?  I call such a combination an /Immortal Type/,
rlm@0: since if that type's pattern was repeated over and over again towards
rlm@0: infinity, the resulting type would be immune to all attack types.
rlm@0: 
rlm@0: * Linear Programming
rlm@0: 
rlm@0: ** Terminology
rlm@0: Linear programming is the process of finding an optimal solution to a
rlm@0: linear equation of several variables which are constrained by some linear
rlm@0: inequalities.
rlm@0: 
rlm@0: In linear programming terminology, the function to be extremized is
rlm@0: the /objective function/.
rlm@0: 
rlm@0: ** COMMENT 
rlm@0: First, we'll give a small example of a linear optimization problem,
rlm@0: and show how it can be solved with Clojure and =lp_solve=.  Then,
rlm@0: we'll show how finding immortal pok\eacute{}mon types can be converted
rlm@0: into a linear problem suitable for solving in the same way.
rlm@0: 
rlm@0: ** The Farmer's Problem
rlm@0: 
rlm@0: Let's solve the Farmer's Problem, a typical linear programming problem
rlm@0: borrowed from http://lpsolve.sourceforge.net/5.5/formulate.htm.
rlm@0: 
rlm@0: 
rlm@0: #+BEGIN_QUOTE 
rlm@0: *The Farmer's Problem:* Suppose a farmer has 75 acres on which to
rlm@0: plant two crops: wheat and barley. To produce these crops, it costs
rlm@0: the farmer (for seed, fertilizer, etc.)  $120 per acre for the wheat
rlm@0: and $210 per acre for the barley. The farmer has $15000 available for
rlm@0: expenses. But after the harvest, the farmer must store the crops while
rlm@0: awaiting favorable market conditions. The farmer has storage space
rlm@0: for 4000 bushels. Each acre yields an average of 110 bushels of wheat
rlm@0: or 30 bushels of barley.  If the net profit per bushel of wheat (after
rlm@0: all expenses have been subtracted) is $1.30 and for barley is $2.00,
rlm@0: how should the farmer plant the 75 acres to maximize profit?
rlm@0: #+END_QUOTE
rlm@0: 
rlm@0: The Farmer's Problem is to maximize profit subject to constraints on
rlm@0: available farmland, funds for expenses, and storage space.
rlm@0: 
rlm@0: |          | Wheat                | Barley              | Maximum total |
rlm@0: |----------+----------------------+---------------------+--------------|
rlm@0: | /        | <                    | >                   | <>           |
rlm@0: | Farmland | \(w\) acres          | \(b\) acres         | 75 acres     |
rlm@0: | Expense  | $120 per acre        | $210 per acre       | $15000       |
rlm@0: | Storage  | 110 bushels per acre | 30 bushels per acre | 4000 bushels |
rlm@0: |----------+----------------------+---------------------+--------------|
rlm@0: | Profit   | $1.30 per bushel     | $2.00 per bushel    |              |
rlm@0: 
rlm@0: *** COMMENT
rlm@0: can be represented as a linear optimization
rlm@0:  problem. In this form, it is a problem with two variables\mdash{}the number of
rlm@0:  acres of wheat, \(w\), and the number of acres of barley, \(b\). The
rlm@0:  aim is to maximize profit, which 
rlm@0: 
rlm@0:  subject to three constraints: the farmer can't spend more money
rlm@0: than he has, the farmer can't use more acres than he owns, and the harvest has
rlm@0: to fit in his storage space.
rlm@0: 
rlm@0: We can express these constraints succinctly using matrix
rlm@0: notation. Denoting the number of acres of barley and wheat by \(b\) and \(w\),
rlm@0: we want to maximize the expression \(143 w + 60 b\) subject to 
rlm@0: 
rlm@0: \(
rlm@0: \begin{cases}
rlm@0: 120 w + 210 b & \leq & 1500\\
rlm@0: 110 w + 30 b & \leq & 4000\\
rlm@0: 1 w + 1 w & \leq & 75
rlm@0: \end{cases}
rlm@0: \)
rlm@0: 
rlm@0: #\(\begin{bmatrix}120&210\\110&30\\1 &
rlm@0: #1\end{bmatrix}\;\begin{bmatrix}w\\b\end{bmatrix}
rlm@0: #\leq \begin{bmatrix}\$15000\\4000\text{ bushels}\\75\text{ acres}\end{bmatrix}\)
rlm@0: 
rlm@0: 
rlm@0: ** Solution using LP Solve
rlm@0: #(LP solve is available at http://www.example.com.)
rlm@0: In a new file,  =farmer.lp=, we list the variables and constraints 
rlm@0: of our problem using LP Solve syntax.
rlm@0: 
rlm@0: #+begin_src lpsolve :tangle farmer.lp
rlm@0: /* Maximize Total Profit */
rlm@0: max: +143 wheat +60 barley;
rlm@0: 
rlm@0: 
rlm@0: /* --------  Constraints  --------*/
rlm@0: 
rlm@0: /* the farmer can't spend more money than he has */
rlm@0: +120 wheat +210 barley <= 15000;
rlm@0: 
rlm@0: /* the harvest has to fit in his storage space */
rlm@0: +110 wheat +30 barley <= 4000;
rlm@0: 
rlm@0: /* he can't use more acres than he owns */
rlm@0: +wheat +barley <= 75;
rlm@0: #+end_src
rlm@0: 
rlm@0: 
rlm@0: #This is a set of linear equations ideal for solving using a program like
rlm@0: #=lp_solve=. In Linear Algebra terms we are maximizing the linear function 
rlm@0: 
rlm@0: #\(\text{profit} = 143\text{ wheat} + 60\text{ barley}\), subject to the constraints
rlm@0: 
rlm@0: #Ax <= b,
rlm@0: 
rlm@0: #where A is [120 210 110 30 1 1], x is [wheat barley] and b is [15000
rlm@0: #4000 75].
rlm@0: 
rlm@0: Running the =lp_solve= program on =farmer.lp= yields the following output.
rlm@0: 
rlm@0: #+begin_src sh :exports both :results scalar
rlm@0: ~/roBin/lpsolve/lp_solve ~/aurellem/src/pokemon/farmer.lp
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : 
rlm@0: : Value of objective function: 6315.62500000
rlm@0: : 
rlm@0: : Actual values of the variables:
rlm@0: : wheat                      21.875
rlm@0: : barley                     53.125
rlm@0: 
rlm@0: This shows that the farmer can maximize his profit by planting 21.875
rlm@0: of the available acres with wheat and the remaining 53.125 acres with
rlm@0: barley; by doing so, he will make $6315.62(5) in profit.
rlm@0: 
rlm@0: 
rlm@0: #The farmer can make a profit of $6315.62 by planting 21.875 acres of
rlm@0: #his land with wheat and the other 53.125 acres of his land with barley.
rlm@0: 
rlm@0: * Incorporating  =lp_solve= into Clojure 
rlm@0: 
rlm@0: There is a Java API available which enables Java programs to use Lp
rlm@0: Solve. Although Clojure can use this Java API directly, the
rlm@0: interaction between Java, C, and Clojure is clumsy:
rlm@0: 
rlm@0: 
rlm@0: The Java API for LP Solve makes it possible to use Lp Solve algorithms
rlm@0: within Java. Although Clojure can use this  Java API directly, 
rlm@0: 
rlm@0: 
rlm@0: ** The Farmer's Problem in Clojure
rlm@0: We are going to solve the same problem involving wheat and barley,
rlm@0: that we did above, but this time using clojure and the lpsolve API.
rlm@0: 
rlm@0: #Because we ultimately intend to use Lp Solve to find optimal Pokemon type combinations.
rlm@0: # we want to solve linear optimization problems within Clojure, the language 
rlm@0: 
rlm@0: ** Setup
rlm@0: =lp_solve= is a crufty =C= program which already comes with a JNI
rlm@0: interface written by Juergen Ebert.  It's API is not
rlm@0: particularly friendly from a functional/immutable perspective, but
rlm@0: with a little work, we can build something that works great with
rlm@0: clojure.
rlm@0: 
rlm@0: #+srcname: intro
rlm@0: #+begin_src clojure :results silent
rlm@0: (ns pokemon.lpsolve
rlm@0:   (:use rlm.ns-rlm))
rlm@0: (rlm.ns-rlm/ns-clone rlm.light-base)
rlm@0: (use 'clojure.set)
rlm@0: (import 'lpsolve.LpSolve)
rlm@0: (use '[clojure [pprint :only [pprint]]])
rlm@0: #+end_src
rlm@0: 
rlm@0: The LpSolve Java interface is available from the same site as
rlm@0: =lp_solve= itself, http://lpsolve.sourceforge.net/ 
rlm@0: Using it is the same as many other =C=
rlm@0: programs. There are excellent instructions to get set
rlm@0: up.  The short version is that you must call Java with
rlm@0: =-Djava.library.path=/path/to/lpsolve/libraries= and also add the
rlm@0: libraries to your export =LD_LIBRARY_PATH= if you are using Linux. For
rlm@0: example, in my =.bashrc= file, I have the line
rlm@0: =LD_LIBRARY_PATH=$HOME/roBin/lpsolve:$LD_LIBRARY_PATH=.
rlm@0: If everything is set-up correctly, 
rlm@0: 
rlm@0: #+srcname: body 
rlm@0: #+begin_src clojure :results verbatim :exports both
rlm@0: (import 'lpsolve.LpSolve)
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results: body
rlm@0: : lpsolve.LpSolve
rlm@0: 
rlm@0: should run with no problems.
rlm@0: 
rlm@0: ** Making a DSL to talk with LpSolve
rlm@0: *** Problems
rlm@0: Since we are using a =C= wrapper, we have to deal with manual memory
rlm@0: management for the =C= structures which are wrapped by the =LpSolve=
rlm@0: object. Memory leaks in =LpSolve= instances can crash the JVM, so it's
rlm@0: very important to get it right.  Also, the Java wrapper follows the
rlm@0: =C= tradition closely and defines many =static final int= constants
rlm@0: for the different states of the =LpSolve= instance instead of using Java
rlm@0: enums.  The calling convention for adding rows and columns to
rlm@0: the constraint matrix is rather complicated and must be done column by
rlm@0: column or row by row, which can be error prone.  Finally, I'd like to
rlm@0: gather all the important output information from the =LpSolve= instance
rlm@0: into a final, immutable structure.
rlm@0: 
rlm@0: In summary, the issues I'd like to address are:
rlm@0: 
rlm@0: - reliable memory management
rlm@0: - functional interface to =LpSolve=
rlm@0: - intelligible, immutable output
rlm@0: 
rlm@0: To deal with these issues I'll create four functions for interfacing
rlm@0: with =LpSolve=
rlm@0: 
rlm@0: #+srcname: declares
rlm@0: #+begin_src clojure :results silent 
rlm@0: (in-ns 'pokemon.lpsolve)
rlm@0: 
rlm@0: ;; deal with automatic memory management for LpSolve instance.
rlm@0: (declare linear-program)
rlm@0: 
rlm@0: ;; functional interface to LpSolve
rlm@0: (declare lp-solve)
rlm@0: 
rlm@0: ;; immutable output from lp-solve
rlm@0: (declare solve get-results)
rlm@0: #+end_src
rlm@0: 
rlm@0: *** Memory Management
rlm@0: 
rlm@0: Every instance of =LpSolve= must be manually garbage collected via a
rlm@0: call to =deleteLP=. I use a non-hygienic macro similar to =with-open=
rlm@0: to ensure that =deleteLP= is always called.
rlm@0: 
rlm@0: #+srcname: memory-management
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.lpsolve)
rlm@0: (defmacro linear-program
rlm@0:   "solve a linear programming problem using LpSolve syntax.
rlm@0:    within the macro, the variable =lps= is bound to the LpSolve instance."
rlm@0:   [& statements]
rlm@0:   (list 'let '[lps (LpSolve/makeLp 0 0)]
rlm@0: 	(concat '(try)
rlm@0: 		statements
rlm@0: 		;; always free the =C= data structures.
rlm@0: 		'((finally (.deleteLp lps))))))
rlm@0: #+end_src
rlm@0: 
rlm@0: 
rlm@0: The macro captures the variable =lps= within its body, providing for a
rlm@0: convenient way to access the object using any of the methods of the
rlm@0: =LpSolve= API without having to worry about when to call
rlm@0: =deleteLP=. 
rlm@0: 
rlm@0: *** Sensible Results
rlm@0: The =linear-program= macro deletes the actual =lps= object once it is
rlm@0: done working, so it's important to collect the important results and
rlm@0: add return them in an immutable structure at the end.
rlm@0: 
rlm@0: #+srcname: get-results
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.lpsolve)
rlm@0: 
rlm@0: (defrecord LpSolution
rlm@0:   [objective-value
rlm@0:    optimal-values
rlm@0:    variable-names
rlm@0:    solution
rlm@0:    status
rlm@0:    model])
rlm@0: 
rlm@0: (defn model
rlm@0:   "Returns a textual representation of the problem suitable for
rlm@0:   direct input to the =lp_solve= program (lps format)"
rlm@0:   [#^LpSolve lps]
rlm@0:   (let [target (java.io.File/createTempFile "lps" ".lp")]
rlm@0:     (.writeLp lps (.getPath target))
rlm@0:     (slurp target)))
rlm@0: 
rlm@0: (defn results
rlm@0:   "given an LpSolve object, solves the object and returns a map of the
rlm@0:   essential values which compose the solution."
rlm@0:   [#^LpSolve lps]
rlm@0:   (locking lps
rlm@0:     (let [status (solve lps)
rlm@0: 	  number-of-variables (.getNcolumns lps)
rlm@0: 	  optimal-values (double-array number-of-variables)
rlm@0: 	  optimal-values (do (.getVariables lps optimal-values)
rlm@0: 			     (seq optimal-values))
rlm@0: 	  variable-names
rlm@0: 	  (doall ;; the doall is necessary since the lps object might
rlm@0: 	   ;; soon be deleted
rlm@0: 	   (map
rlm@0: 	    #(.getColName lps (inc %))
rlm@0: 	    (range number-of-variables)))
rlm@0: 	  model (model lps)]
rlm@0:       (LpSolution.
rlm@0:        (.getObjective lps)
rlm@0:        optimal-values
rlm@0:        variable-names
rlm@0:        (zipmap variable-names optimal-values)
rlm@0:        status
rlm@0:        model))))
rlm@0: 
rlm@0: #+end_src
rlm@0: 
rlm@0: Here I've created an object called =LpSolution= which stores the
rlm@0: important results from a session with =lp_solve=.  Of note is the
rlm@0: =model= function which returns the problem in a form that can be
rlm@0: solved by other linear programming packages.
rlm@0: 
rlm@0: *** Solution Status of an LpSolve Object
rlm@0: 
rlm@0: #+srcname: solve
rlm@0: #+begin_src clojure :results silent       
rlm@0: (in-ns 'pokemon.lpsolve)
rlm@0: 
rlm@0: (defn static-integer?
rlm@0:   "does the field represent a static integer constant?"
rlm@0:   [#^java.lang.reflect.Field field]
rlm@0:   (and (java.lang.reflect.Modifier/isStatic (.getModifiers field))
rlm@0:        (integer? (.get field nil))))
rlm@0: 
rlm@0: (defn integer-constants [class]
rlm@0:   (filter static-integer? (.getFields class)))
rlm@0: 
rlm@0: (defn-memo constant-map
rlm@0:   "Takes a class and creates a map of the static constant integer
rlm@0:   fields with their names.  This helps with C wrappers where they have
rlm@0:   just defined a bunch of integer constants instead of enums"
rlm@0:   [class]
rlm@0:      (let [integer-fields (integer-constants class)]
rlm@0:        (into (sorted-map)
rlm@0: 	     (zipmap (map #(.get % nil) integer-fields)
rlm@0: 		     (map #(.getName %) integer-fields)))))
rlm@0: 	     
rlm@0: (defn solve
rlm@0:   "Solve an instance of LpSolve and return a string representing the
rlm@0:   status of the computation. Will only solve a particular LpSolve
rlm@0:   instance once."
rlm@0:   [#^LpSolve lps]
rlm@0:   ((constant-map LpSolve)
rlm@0:    (.solve lps)))
rlm@0: 
rlm@0: #+end_src
rlm@0: 
rlm@0: The =.solve= method of an =LpSolve= object only returns an integer code
rlm@0: to specify the status of the computation.  The =solve= method here
rlm@0: uses reflection to look up the actual name of the status code and
rlm@0: returns a more helpful status message that is also resistant to
rlm@0: changes in the meanings of the code numbers.
rlm@0: 
rlm@0: *** The Farmer Example in Clojure, Pass 1
rlm@0: 
rlm@0: Now we can implement a nicer version of the examples from the
rlm@0: [[http://lpsolve.sourceforge.net/][=lp\_solve= website]]. The following is a more or less
rlm@0: line-by-line translation of the Java code from that example.
rlm@0: 
rlm@0: #+srcname: farmer-example
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.lpsolve)
rlm@0: (defn farmer-example []
rlm@0:   (linear-program
rlm@0:    (results
rlm@0:     (doto lps
rlm@0:       ;; name the columns
rlm@0:       (.setColName 1 "wheat")
rlm@0:       (.setColName 2 "barley")
rlm@0:       (.setAddRowmode true)
rlm@0:       ;; row 1 : 120x + 210y <= 15000
rlm@0:       (.addConstraintex 2
rlm@0: 			(double-array [120 210])
rlm@0: 			(int-array [1 2])
rlm@0: 			LpSolve/LE
rlm@0: 			15e3)
rlm@0:       ;; row 2 : 110x + 30y <= 4000
rlm@0:       (.addConstraintex 2
rlm@0: 			(double-array [110 30])
rlm@0: 			(int-array [1 2])
rlm@0: 			LpSolve/LE
rlm@0: 			4e3)
rlm@0:       ;; ;; row 3 : x + y <= 75
rlm@0:       (.addConstraintex 2
rlm@0: 			(double-array [1 1])
rlm@0: 			(int-array [1 2])
rlm@0: 			LpSolve/LE
rlm@0: 			75)
rlm@0:       (.setAddRowmode false)
rlm@0: 
rlm@0:       ;; add constraints
rlm@0:       (.setObjFnex 2
rlm@0: 		   (double-array [143 60])
rlm@0: 		   (int-array [1 2]))
rlm@0:             
rlm@0:       ;; set this as a maximization problem
rlm@0:       (.setMaxim)))))
rlm@0: 
rlm@0: #+end_src
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both 
rlm@0: (clojure.pprint/pprint
rlm@0:  (:solution (pokemon.lpsolve/farmer-example)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : {"barley" 53.12499999999999, "wheat" 21.875}
rlm@0: 
rlm@0: And it works as expected!
rlm@0: 
rlm@0: *** The Farmer Example in Clojure, Pass 2
rlm@0: We don't have to worry about memory management anymore, and the farmer
rlm@0: example is about half as long as the example from the =LpSolve=
rlm@0: website, but we can still do better.  Solving linear problems is all
rlm@0: about the constraint matrix $A$ , the objective function $c$, and the
rlm@0: right-hand-side $b$, plus whatever other options one cares to set for
rlm@0: the particular instance of =lp_solve=.  Why not make a version of
rlm@0: =linear-program= that takes care of initialization?
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: #+srcname: lp-solve
rlm@0: #+begin_src clojure :results silent       
rlm@0: (in-ns 'pokemon.lpsolve)
rlm@0: (defn initialize-lpsolve-row-oriented
rlm@0:   "fill in an lpsolve instance using a constraint matrix =A=, the
rlm@0:   objective function =c=, and the right-hand-side =b="
rlm@0:   [#^LpSolve lps A b c]
rlm@0:   ;; set the name of the last column to _something_
rlm@0:   ;; this appears to be necessary to ensure proper initialization.
rlm@0:   (.setColName lps (count c) (str "C" (count c)))
rlm@0: 
rlm@0:   ;; This is the recommended way to "fill-in" an lps instance from the 
rlm@0:   ;; documentation. First, set row mode, then set the objective
rlm@0:   ;; function, then set each row of the problem, and then turn off row
rlm@0:   ;; mode. 
rlm@0:   (.setAddRowmode lps true)
rlm@0:   (.setObjFnex lps (count c)
rlm@0: 	       (double-array c)
rlm@0: 	       (int-array (range 1 (inc (count c)))))
rlm@0:   (dorun
rlm@0:    (for [n (range (count A))]
rlm@0:      (let [row (nth A n)
rlm@0: 	   row-length (int (count row))]
rlm@0:        (.addConstraintex lps
rlm@0: 			 row-length
rlm@0: 			 (double-array row)
rlm@0: 			 (int-array (range 1 (inc row-length)))
rlm@0: 			 LpSolve/LE
rlm@0: 			 (double (nth b n))))))
rlm@0:   (.setAddRowmode lps false)
rlm@0:   lps)
rlm@0: 
rlm@0: 
rlm@0: (defmacro lp-solve
rlm@0:   "by default:,
rlm@0:    minimize (* c x), subject to (<= (* A x) b),
rlm@0:    using continuous variables.  You may set any number of
rlm@0:    other options as in the LpSolve API." 
rlm@0:   [A b c & lp-solve-forms]
rlm@0:   ;; assume that A is a vector of vectors
rlm@0:   (concat
rlm@0:    (list 'linear-program
rlm@0: 	 (list 'initialize-lpsolve-row-oriented 'lps A b c))
rlm@0:    `~lp-solve-forms))
rlm@0:  #+end_src
rlm@0: 
rlm@0: Now, we can use a much more functional approach to solving the
rlm@0: farmer's problem:
rlm@0: 
rlm@0: #+srcname: better-farmer
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.lpsolve)
rlm@0: (defn better-farmer-example []
rlm@0:   (lp-solve  [[120 210]
rlm@0: 	      [110 30]
rlm@0: 	      [1 1]]
rlm@0: 	     [15000
rlm@0: 	      4000
rlm@0: 	      75]
rlm@0: 	     [143 60]
rlm@0: 	     (.setColName lps 1 "wheat")
rlm@0: 	     (.setColName lps 2 "barley")
rlm@0: 	     (.setMaxim lps)
rlm@0: 	     (results lps)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+begin_src clojure  :exports both :results verbatim
rlm@0: (vec (:solution (pokemon.lpsolve/better-farmer-example)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : [["barley" 53.12499999999999] ["wheat" 21.875]]
rlm@0: 
rlm@0: Notice that both the inputs to =better-farmer-example= and the results
rlm@0: are immutable.
rlm@0: 
rlm@0: * Using LpSolve to find Immortal Types
rlm@0: ** Converting the Pokemon problem into a linear form
rlm@0: How can the original question about pok\eacute{}mon types be converted
rlm@0: into a linear problem? 
rlm@0: 
rlm@0: Pokemon types can be considered to be vectors of numbers representing
rlm@0: their susceptances to various attacking types, so Water might look
rlm@0: something like this.
rlm@0: 
rlm@0: #+begin_src clojure :results scalar :exports both
rlm@0: (:water (pokemon.types/defense-strengths))
rlm@0: #+end_src 
rlm@0: 
rlm@0: #+results:
rlm@0: : [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5]
rlm@0: 
rlm@0: Where the numbers represent the susceptibility of Water to the
rlm@0: attacking types in the following order:
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.types/type-names))
rlm@0: #+end_src 
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: [:normal
rlm@0:  :fire
rlm@0:  :water
rlm@0:  :electric
rlm@0:  :grass
rlm@0:  :ice
rlm@0:  :fighting
rlm@0:  :poison
rlm@0:  :ground
rlm@0:  :flying
rlm@0:  :psychic
rlm@0:  :bug
rlm@0:  :rock
rlm@0:  :ghost
rlm@0:  :dragon
rlm@0:  :dark
rlm@0:  :steel]
rlm@0: #+end_example
rlm@0: 
rlm@0: 
rlm@0: So, for example, Water is /resistant/ (x0.5) against Fire, which is
rlm@0: the second element in the list.
rlm@0: 
rlm@0: To combine types, these sorts of vectors are multiplied together
rlm@0: pair-wise to yield the resulting combination.  
rlm@0: 
rlm@0: Unfortunately, we need some way to add two type vectors together
rlm@0: instead of multiplying them if we want to solve the problem with
rlm@0: =lp_solve=.  Taking the log of the vector does just the trick.
rlm@0: 
rlm@0: If we make a matrix with each column being the log (base 2) of the
rlm@0: susceptance of each type, then finding an immortal type corresponds to
rlm@0: setting each constraint (the $b$ vector) to -1 (since log_2(1/2) = -1)
rlm@0: and setting the constraint vector $c$ to all ones, which means that we
rlm@0: want to find the immortal type which uses the least amount of types.
rlm@0: 
rlm@0: #+srcname: pokemon-lp
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.lpsolve)
rlm@0: 
rlm@0: (require 'pokemon.types)
rlm@0: (require 'incanter.core)
rlm@0: 
rlm@0: (defn log-clamp-matrix [matrix]
rlm@0:   ;; we have to clamp the Infinities to a more reasonable negative
rlm@0:   ;; value because lp_solve does not play well with infinities in its
rlm@0:   ;; constraint matrix.
rlm@0:   (map (fn [row] (map #(if (= Double/NEGATIVE_INFINITY %) -1e3 %) row))
rlm@0:        (incanter.core/log2
rlm@0: 	(incanter.core/trans
rlm@0: 	 matrix))))
rlm@0: 
rlm@0: ;; constraint matrices
rlm@0: (defn log-defense-matrix []
rlm@0:   (log-clamp-matrix
rlm@0:    (doall (map (pokemon.types/defense-strengths)
rlm@0: 	       (pokemon.types/type-names)))))
rlm@0: 
rlm@0: (defn log-attack-matrix []
rlm@0:   (incanter.core/trans (log-defense-matrix)))
rlm@0: 
rlm@0: ;; target vectors
rlm@0: (defn all-resistant []
rlm@0:   (doall (map (constantly -1) (pokemon.types/type-names))))
rlm@0: 
rlm@0: (defn all-weak []
rlm@0:   (doall (map (constantly 1) (pokemon.types/type-names))))
rlm@0: 
rlm@0: (defn all-neutral []
rlm@0:   (doall (map (constantly 0) (pokemon.types/type-names))))
rlm@0: 
rlm@0: 
rlm@0: ;; objective functions
rlm@0: (defn number-of-types []
rlm@0:   (doall (map (constantly 1) (pokemon.types/type-names))))
rlm@0: 
rlm@0: (defn set-constraints
rlm@0:   "sets all the constraints for an lpsolve instance to the given
rlm@0:   constraint. =constraint= here is one of the LpSolve constants such
rlm@0:   as LpSolve/EQ."
rlm@0:   [#^LpSolve lps constraint]
rlm@0:   (dorun (map (fn [index] (.setConstrType lps index constraint))
rlm@0: 	      ;; ONE based indexing!!!
rlm@0: 	      (range 1 (inc (.getNrows lps))))))
rlm@0: 
rlm@0: 
rlm@0: (defn set-discrete
rlm@0:   "sets every variable in an lps problem to be a discrete rather than
rlm@0:   continuous variable"
rlm@0:   [#^LpSolve lps]
rlm@0:   (dorun (map (fn [index] (.setInt lps index true))
rlm@0: 	      ;; ONE based indexing!!!
rlm@0: 	      (range 1 (inc (.getNcolumns lps))))))
rlm@0: 
rlm@0: (defn set-variable-names
rlm@0:   "sets the variable names of the problem given a vector of names"
rlm@0:   [#^LpSolve lps names]
rlm@0:   (dorun
rlm@0:    (map (fn [[index name]]
rlm@0: 	  (.setColName lps  (inc index) (str name)))
rlm@0: 	;; ONE based indexing!!!
rlm@0: 	(indexed names))))
rlm@0: 
rlm@0: (defn poke-solve 
rlm@0:   ([poke-matrix target objective-function constraint min-num-types]
rlm@0:      ;; must have at least one type
rlm@0:      (let [poke-matrix
rlm@0: 	   (concat poke-matrix
rlm@0: 		   [(map (constantly 1)
rlm@0: 			 (range (count (first poke-matrix))))])
rlm@0: 	   target (concat target [min-num-types])]
rlm@0:        (lp-solve poke-matrix target objective-function
rlm@0: 		 (set-constraints lps constraint)
rlm@0: 		 ;; must have more than min-num-types
rlm@0: 		 (.setConstrType lps (count target) LpSolve/GE)
rlm@0: 		 (set-discrete lps)
rlm@0: 		 (set-variable-names lps (pokemon.types/type-names))
rlm@0: 		 (results lps))))
rlm@0:   ([poke-matrix target objective-function constraint]
rlm@0:      ;; at least one type
rlm@0:      (poke-solve poke-matrix target objective-function constraint 1)))
rlm@0: 
rlm@0: (defn solution 
rlm@0:   "If the results of an lpsolve operation are feasible, returns the
rlm@0:   results. Otherwise, returns the error."
rlm@0:   [results]
rlm@0:   (if (not (= (:status results) "OPTIMAL"))
rlm@0:     (:status results)
rlm@0:     (:solution results)))
rlm@0: 
rlm@0: #+end_src
rlm@0: 
rlm@0: With this, we are finally able to get some results.
rlm@0: 
rlm@0: ** Results
rlm@0: #+srcname: results
rlm@0: #+begin_src clojure :results silent  
rlm@0: (in-ns 'pokemon.lpsolve)
rlm@0: 
rlm@0: (defn best-defense-type
rlm@0:   "finds a type combination which is resistant to all attacks."
rlm@0:   []
rlm@0:   (poke-solve 
rlm@0:    (log-defense-matrix) (all-resistant) (number-of-types) LpSolve/LE))
rlm@0: 
rlm@0: (defn worst-attack-type
rlm@0:   "finds the attack type which is not-very-effective against all pure
rlm@0:   defending types (each single defending type is resistant to this
rlm@0:   attack combination"
rlm@0:   []
rlm@0:   (poke-solve
rlm@0:    (log-attack-matrix)  (all-resistant) (number-of-types) LpSolve/LE))
rlm@0: 
rlm@0: (defn worst-defense-type
rlm@0:   "finds a defending type that is weak to all single attacking types."
rlm@0:   []
rlm@0:   (poke-solve
rlm@0:    (log-defense-matrix) (all-weak) (number-of-types) LpSolve/GE))
rlm@0: 
rlm@0: (defn best-attack-type
rlm@0:   "finds an attack type which is super effective against all single
rlm@0: defending types"
rlm@0:   []
rlm@0:   (poke-solve
rlm@0:    (log-attack-matrix) (all-weak) (number-of-types) LpSolve/GE))
rlm@0: 
rlm@0: (defn solid-defense-type
rlm@0:   "finds a defense type which is either neutral or resistant to all
rlm@0:   single attacking types"
rlm@0:   []
rlm@0:   (poke-solve
rlm@0:    (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/LE))
rlm@0: 
rlm@0: (defn solid-attack-type
rlm@0:   "finds an attack type which is either neutral or super-effective to
rlm@0:   all single attacking types."
rlm@0:   []
rlm@0:   (poke-solve
rlm@0:    (log-attack-matrix) (all-neutral) (number-of-types) LpSolve/GE))
rlm@0: 
rlm@0: (defn weak-defense-type
rlm@0:   "finds a defense type which is either neutral or weak to all single
rlm@0:   attacking types"
rlm@0:   []
rlm@0:   (poke-solve
rlm@0:    (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/GE))
rlm@0: 
rlm@0: (defn neutral-defense-type
rlm@0:   "finds a defense type which is perfectly neutral to all attacking
rlm@0:   types."
rlm@0:   []
rlm@0:   (poke-solve
rlm@0:    (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/EQ))
rlm@0: 
rlm@0: #+end_src
rlm@0: 
rlm@0: *** Strongest Attack/Defense Combinations
rlm@0:     
rlm@0: #+begin_src clojure :results output :exports both 
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.lpsolve/solution (pokemon.lpsolve/best-defense-type)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {":normal" 0.0,
rlm@0:  ":ground" 1.0,
rlm@0:  ":poison" 2.0,
rlm@0:  ":flying" 1.0,
rlm@0:  ":fighting" 0.0,
rlm@0:  ":dragon" 0.0,
rlm@0:  ":fire" 0.0,
rlm@0:  ":dark" 1.0,
rlm@0:  ":ice" 0.0,
rlm@0:  ":steel" 1.0,
rlm@0:  ":ghost" 0.0,
rlm@0:  ":electric" 0.0,
rlm@0:  ":bug" 0.0,
rlm@0:  ":psychic" 0.0,
rlm@0:  ":grass" 0.0,
rlm@0:  ":water" 2.0,
rlm@0:  ":rock" 0.0}
rlm@0: #+end_example
rlm@0: 
rlm@0: # #+results-old:
rlm@0: # : [[":normal" 0.0] [":ground" 1.0] [":poison" 0.0] [":flying" 1.0] [":fighting" 0.0] [":dragon" 1.0] [":fire" 0.0] [":dark" 0.0] [":ice" 0.0] [":steel" 2.0] [":ghost" 1.0] [":electric" 0.0] [":bug" 0.0] [":psychic" 0.0] [":grass" 0.0] [":water" 2.0] [":rock" 0.0]]
rlm@0: 
rlm@0: 
rlm@0: This is the immortal type combination we've been looking for.  By
rlm@0: combining Steel, Water, Poison, and three types which each have complete
rlm@0: immunities to various other types, we've created a type that is resistant to
rlm@0: all attacking types.
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both 
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.types/susceptibility 
rlm@0:   [:poison :poison :water :water :steel :ground :flying :dark]))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {:water 1/2,
rlm@0:  :psychic 0,
rlm@0:  :dragon 1/2,
rlm@0:  :fire 1/2,
rlm@0:  :ice 1/2,
rlm@0:  :grass 1/2,
rlm@0:  :ghost 1/4,
rlm@0:  :poison 0,
rlm@0:  :flying 1/2,
rlm@0:  :normal 1/2,
rlm@0:  :rock 1/2,
rlm@0:  :electric 0,
rlm@0:  :ground 0,
rlm@0:  :fighting 1/2,
rlm@0:  :dark 1/4,
rlm@0:  :steel 1/8,
rlm@0:  :bug 1/8}
rlm@0: #+end_example
rlm@0: 
rlm@0: # #+results-old:
rlm@0: # : {:water 1/4, :psychic 1/4, :dragon 1/2, :fire 1/2, :ice 1/2, :grass 1/2, :ghost 1/2, :poison 0, :flying 1/4, :normal 0, :rock 1/4, :electric 0, :ground 0, :fighting 0, :dark 1/2, :steel 1/16, :bug 1/16}
rlm@0: 
rlm@0: 
rlm@0: Cool!
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {":normal" 0.0,
rlm@0:  ":ground" 0.0,
rlm@0:  ":poison" 0.0,
rlm@0:  ":flying" 0.0,
rlm@0:  ":fighting" 0.0,
rlm@0:  ":dragon" 0.0,
rlm@0:  ":fire" 0.0,
rlm@0:  ":dark" 1.0,
rlm@0:  ":ice" 0.0,
rlm@0:  ":steel" 0.0,
rlm@0:  ":ghost" 1.0,
rlm@0:  ":electric" 0.0,
rlm@0:  ":bug" 0.0,
rlm@0:  ":psychic" 0.0,
rlm@0:  ":grass" 0.0,
rlm@0:  ":water" 0.0,
rlm@0:  ":rock" 0.0}
rlm@0: #+end_example
rlm@0: 
rlm@0: Dark and Ghost are the best dual-type combo, and are resistant or
rlm@0: neutral to all types.
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.types/old-school
rlm@0:   (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type))))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {":normal" 0.0,
rlm@0:  ":ground" 0.0,
rlm@0:  ":poison" 0.0,
rlm@0:  ":flying" 0.0,
rlm@0:  ":fighting" 0.0,
rlm@0:  ":dragon" 0.0,
rlm@0:  ":fire" 0.0,
rlm@0:  ":ice" 0.0,
rlm@0:  ":ghost" 1.0,
rlm@0:  ":electric" 0.0,
rlm@0:  ":bug" 0.0,
rlm@0:  ":psychic" 1.0,
rlm@0:  ":grass" 0.0,
rlm@0:  ":water" 0.0,
rlm@0:  ":rock" 0.0}
rlm@0: #+end_example
rlm@0: 
rlm@0: Ghost and Psychic are a powerful dual type combo in the original games,
rlm@0: due to a glitch which made Psychic immune to Ghost type attacks, even
rlm@0: though the game claims that Ghost is strong to Psychic.
rlm@0: 
rlm@0: #+begin_src clojure :results verbatim :exports both
rlm@0: (pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : INFEASIBLE
rlm@0: 
rlm@0: #+begin_src clojure :results verbatim :exports both
rlm@0: (pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : INFEASIBLE
rlm@0: 
rlm@0: 
rlm@0: #+begin_src clojure :results verbatim :exports both
rlm@0: (pokemon.types/old-school
rlm@0:  (pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : INFEASIBLE
rlm@0: 
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.types/old-school
rlm@0:   (pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {":normal" 0.0,
rlm@0:  ":ground" 0.0,
rlm@0:  ":poison" 0.0,
rlm@0:  ":flying" 0.0,
rlm@0:  ":fighting" 0.0,
rlm@0:  ":dragon" 1.0,
rlm@0:  ":fire" 0.0,
rlm@0:  ":ice" 0.0,
rlm@0:  ":ghost" 0.0,
rlm@0:  ":electric" 0.0,
rlm@0:  ":bug" 0.0,
rlm@0:  ":psychic" 0.0,
rlm@0:  ":grass" 0.0,
rlm@0:  ":water" 0.0,
rlm@0:  ":rock" 0.0}
rlm@0: #+end_example
rlm@0: 
rlm@0: The best attacking type combination is strangely Dragon from the
rlm@0: original games.  It is neutral against all the original types except
rlm@0: for Dragon, which it is strong against.  There is no way to make an
rlm@0: attacking type that is strong against every type, or even one that is
rlm@0: strong or neutral against every type, in the new games.
rlm@0: 
rlm@0: 
rlm@0: *** Weakest Attack/Defense Combinations
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.types/old-school
rlm@0:   (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type))))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {":normal" 5.0,
rlm@0:  ":ground" 0.0,
rlm@0:  ":poison" 0.0,
rlm@0:  ":flying" 0.0,
rlm@0:  ":fighting" 0.0,
rlm@0:  ":dragon" 0.0,
rlm@0:  ":fire" 1.0,
rlm@0:  ":ice" 2.0,
rlm@0:  ":ghost" 1.0,
rlm@0:  ":electric" 1.0,
rlm@0:  ":bug" 1.0,
rlm@0:  ":psychic" 0.0,
rlm@0:  ":grass" 3.0,
rlm@0:  ":water" 2.0,
rlm@0:  ":rock" 0.0}
rlm@0: #+end_example
rlm@0: 
rlm@0: # #+results-old:
rlm@0: # : [[":normal" 5.0] [":ground" 1.0] [":poison" 0.0] [":flying" 0.0] [":fighting" 2.0] [":dragon" 0.0] [":fire" 0.0] [":ice" 4.0] [":ghost" 1.0] [":electric" 4.0] [":bug" 0.0] [":psychic" 0.0] [":grass" 0.0] [":water" 1.0] [":rock" 1.0]]
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {":normal" 4.0,
rlm@0:  ":ground" 1.0,
rlm@0:  ":poison" 1.0,
rlm@0:  ":flying" 0.0,
rlm@0:  ":fighting" 1.0,
rlm@0:  ":dragon" 0.0,
rlm@0:  ":fire" 0.0,
rlm@0:  ":dark" 0.0,
rlm@0:  ":ice" 4.0,
rlm@0:  ":steel" 0.0,
rlm@0:  ":ghost" 1.0,
rlm@0:  ":electric" 3.0,
rlm@0:  ":bug" 0.0,
rlm@0:  ":psychic" 1.0,
rlm@0:  ":grass" 1.0,
rlm@0:  ":water" 1.0,
rlm@0:  ":rock" 2.0}
rlm@0: #+end_example
rlm@0: 
rlm@0: # #+results-old:
rlm@0: # : [[":normal" 4.0] [":ground" 1.0] [":poison" 1.0] [":flying" 0.0] [":fighting" 2.0] [":dragon" 0.0] [":fire" 0.0] [":dark" 0.0] [":ice" 5.0] [":steel" 0.0] [":ghost" 1.0] [":electric" 5.0] [":bug" 0.0] [":psychic" 1.0] [":grass" 0.0] [":water" 1.0] [":rock" 2.0]]
rlm@0: 
rlm@0: 
rlm@0: This is an extremely interesting type combination, in that it uses
rlm@0: quite a few types.
rlm@0: 
rlm@0: #+begin_src clojure :results verbatim :exports both
rlm@0: (reduce + (vals (:solution (pokemon.lpsolve/worst-attack-type))))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : 20.0
rlm@0: 
rlm@0: 20 types is the /minimum/ number of types before the attacking
rlm@0: combination is not-very-effective or worse against all defending
rlm@0: types. This would probably have been impossible to discover using
rlm@0: best-first search, since it involves such an intricate type
rlm@0: combination.
rlm@0: 
rlm@0: It's so interesting that it takes 20 types to make an attack type that
rlm@0: is weak to all types that the combination merits further investigation.
rlm@0: 
rlm@0: Unfortunately, all of the tools that we've written so far are focused
rlm@0: on defense type combinations.  However, it is possible to make every
rlm@0: tool attack-oriented via a simple macro.
rlm@0: 
rlm@0: #+srcname: attack-oriented
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.lpsolve)
rlm@0: 
rlm@0: (defmacro attack-mode [& forms]
rlm@0:   `(let [attack-strengths# pokemon.types/attack-strengths
rlm@0: 	 defense-strengths# pokemon.types/defense-strengths]
rlm@0:      (binding [pokemon.types/attack-strengths
rlm@0: 	       defense-strengths#
rlm@0: 	       pokemon.types/defense-strengths
rlm@0: 	       attack-strengths#]
rlm@0:        ~@forms)))
rlm@0: #+end_src
rlm@0: 
rlm@0: Now all the tools from =pokemon.types= will work for attack
rlm@0: combinations.
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.types/susceptibility [:water]))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {:water 1/2,
rlm@0:  :psychic 1,
rlm@0:  :dragon 1,
rlm@0:  :fire 1/2,
rlm@0:  :ice 1/2,
rlm@0:  :grass 2,
rlm@0:  :ghost 1,
rlm@0:  :poison 1,
rlm@0:  :flying 1,
rlm@0:  :normal 1,
rlm@0:  :rock 1,
rlm@0:  :electric 2,
rlm@0:  :ground 1,
rlm@0:  :fighting 1,
rlm@0:  :dark 1,
rlm@0:  :steel 1/2,
rlm@0:  :bug 1}
rlm@0: #+end_example
rlm@0: 
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.lpsolve/attack-mode 
rlm@0:   (pokemon.types/susceptibility [:water])))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {:water 1/2,
rlm@0:  :psychic 1,
rlm@0:  :dragon 1/2,
rlm@0:  :fire 2,
rlm@0:  :ice 1,
rlm@0:  :grass 1/2,
rlm@0:  :ghost 1,
rlm@0:  :poison 1,
rlm@0:  :flying 1,
rlm@0:  :normal 1,
rlm@0:  :rock 2,
rlm@0:  :electric 1,
rlm@0:  :ground 2,
rlm@0:  :fighting 1,
rlm@0:  :dark 1,
rlm@0:  :steel 1,
rlm@0:  :bug 1}
rlm@0: #+end_example
rlm@0: 
rlm@0: Now =pokemon.types/susceptibility= reports the /attack-type/
rlm@0: combination's effectiveness against other types.
rlm@0: 
rlm@0: The 20 type combo achieves its goal in a very clever way.
rlm@0: 
rlm@0: First, it weakens its effectiveness to other types at the expense of
rlm@0: making it very strong against flying.
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.lpsolve/attack-mode
rlm@0:   (pokemon.types/susceptibility
rlm@0:    [:normal :normal :normal :normal
rlm@0:     :ice :ice :ice :ice
rlm@0:     :electric :electric :electric
rlm@0:     :rock :rock])))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {:water 1/2,
rlm@0:  :psychic 1,
rlm@0:  :dragon 2,
rlm@0:  :fire 1/4,
rlm@0:  :ice 1/4,
rlm@0:  :grass 2,
rlm@0:  :ghost 0,
rlm@0:  :poison 1,
rlm@0:  :flying 512,
rlm@0:  :normal 1,
rlm@0:  :rock 1/16,
rlm@0:  :electric 1/8,
rlm@0:  :ground 0,
rlm@0:  :fighting 1/4,
rlm@0:  :dark 1,
rlm@0:  :steel 1/1024,
rlm@0:  :bug 4}
rlm@0: #+end_example
rlm@0: 
rlm@0: Then, it removes it's strengths against Flying, Normal, and Fighting
rlm@0: by adding Ghost and Ground.
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.lpsolve/attack-mode
rlm@0:   (pokemon.types/susceptibility
rlm@0:    [:normal :normal :normal :normal
rlm@0:     :ice :ice :ice :ice
rlm@0:     :electric :electric :electric
rlm@0:     :rock :rock
rlm@0:     ;; Spot resistances
rlm@0:     :ghost :ground])))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {:water 1/2,
rlm@0:  :psychic 2,
rlm@0:  :dragon 2,
rlm@0:  :fire 1/2,
rlm@0:  :ice 1/4,
rlm@0:  :grass 1,
rlm@0:  :ghost 0,
rlm@0:  :poison 2,
rlm@0:  :flying 0,
rlm@0:  :normal 0,
rlm@0:  :rock 1/8,
rlm@0:  :electric 1/4,
rlm@0:  :ground 0,
rlm@0:  :fighting 1/4,
rlm@0:  :dark 1/2,
rlm@0:  :steel 1/1024,
rlm@0:  :bug 2}
rlm@0: #+end_example
rlm@0: 
rlm@0: Adding the pair Psychic and Fighting takes care of its strength
rlm@0: against Psychic and makes it ineffective against Dark, which is immune
rlm@0: to Psychic.
rlm@0: 
rlm@0: Adding the pair Grass and Poison makes takes care of its strength
rlm@0: against poison and makes it ineffective against Steel, which is immune
rlm@0: to poison.
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.lpsolve/attack-mode
rlm@0:   (pokemon.types/susceptibility
rlm@0:    [;; setup
rlm@0:     :normal :normal :normal :normal
rlm@0:     :ice :ice :ice :ice
rlm@0:     :electric :electric :electric
rlm@0:     :rock :rock
rlm@0:     ;; Spot resistances
rlm@0:     :ghost :ground
rlm@0:     ;; Pair resistances
rlm@0:     :psychic :fighting
rlm@0:     :grass :poison])))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {:water 1,
rlm@0:  :psychic 1/2,
rlm@0:  :dragon 1,
rlm@0:  :fire 1/4,
rlm@0:  :ice 1/2,
rlm@0:  :grass 1,
rlm@0:  :ghost 0,
rlm@0:  :poison 1/2,
rlm@0:  :flying 0,
rlm@0:  :normal 0,
rlm@0:  :rock 1/4,
rlm@0:  :electric 1/4,
rlm@0:  :ground 0,
rlm@0:  :fighting 1/2,
rlm@0:  :dark 0,
rlm@0:  :steel 0,
rlm@0:  :bug 1/2}
rlm@0: #+end_example
rlm@0: 
rlm@0: Can you see the final step?
rlm@0: 
rlm@0: It's adding the Water type, which is weak against Water and Dragon and
rlm@0: strong against Rock and Fire.
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.lpsolve/attack-mode
rlm@0:   (pokemon.types/susceptibility
rlm@0:    [;; setup
rlm@0:     :normal :normal :normal :normal
rlm@0:     :ice :ice :ice :ice
rlm@0:     :electric :electric :electric
rlm@0:     :rock :rock
rlm@0:     ;; Spot resistances
rlm@0:     :ghost :ground
rlm@0:     ;; Pair resistances
rlm@0:     :psychic :fighting
rlm@0:     :grass :poison
rlm@0:     ;; completion
rlm@0:     :water])))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {:water 1/2,
rlm@0:  :psychic 1/2,
rlm@0:  :dragon 1/2,
rlm@0:  :fire 1/2,
rlm@0:  :ice 1/2,
rlm@0:  :grass 1/2,
rlm@0:  :ghost 0,
rlm@0:  :poison 1/2,
rlm@0:  :flying 0,
rlm@0:  :normal 0,
rlm@0:  :rock 1/2,
rlm@0:  :electric 1/4,
rlm@0:  :ground 0,
rlm@0:  :fighting 1/2,
rlm@0:  :dark 0,
rlm@0:  :steel 0,
rlm@0:  :bug 1/2}
rlm@0: #+end_example
rlm@0: 
rlm@0: Which makes a particularly beautiful combination which is ineffective
rlm@0: against all defending types.
rlm@0: 
rlm@0: 
rlm@0: # #+begin_src clojure :results scalar :exports both
rlm@0: # (with-out-str (clojure.contrib.pprint/pprint (seq (attack-mode (pokemon.types/susceptibility [:normal :normal :normal :normal :ice :ice :ice :ice :electric :electric :electric :rock :rock  :ground :ghost :psychic :fighting :grass :poison])))))
rlm@0: # #+end_src
rlm@0: 
rlm@0: # #+results:
rlm@0: # | [:water 1] | [:psychic 1/2] | [:dragon 1] | [:fire 1/4] | [:ice 1/2] | [:grass 1] | [:ghost 0] | [:poison 1/2] | [:flying 0] | [:normal 0] | [:rock 1/4] | [:electric 1/4] | [:ground 0] | [:fighting 1/2] | [:dark 0] | [:steel 0] | [:bug 1/2] |
rlm@0: 
rlm@0: 
rlm@0: Is there anything else that's interesting?
rlm@0: 
rlm@0: #+begin_src clojure :exports both
rlm@0: (pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : INFEASIBLE
rlm@0: 
rlm@0: #+begin_src clojure :exports both
rlm@0: (pokemon.types/old-school
rlm@0:  (pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : INFEASIBLE
rlm@0: 
rlm@0: #+begin_src clojure :exports both
rlm@0: (pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : INFEASIBLE
rlm@0: 
rlm@0: #+begin_src clojure :exports both
rlm@0: (pokemon.types/old-school
rlm@0:  (pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : INFEASIBLE
rlm@0: 
rlm@0: #+begin_src clojure :exports both
rlm@0: (pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : INFEASIBLE
rlm@0: 
rlm@0: #+begin_src clojure :exports both
rlm@0: (pokemon.types/old-school
rlm@0:  (pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : INFEASIBLE
rlm@0: 
rlm@0: There is no way to produce a defense-type that is weak to all types.
rlm@0: This is probably because there are many types that are completely
rlm@0: immune to some types, such as Flying, which is immune to Ground. A
rlm@0: perfectly weak type could not use any of these types.
rlm@0: 
rlm@0: * Summary
rlm@0: 
rlm@0: Overall, the pok\eacute{}mon type system is slanted more towards defense
rlm@0: rather than offense.  While it is possible to create superior
rlm@0: defensive types and exceptionally weak attack types, it is not possible to
rlm@0: create exceptionally weak defensive types or very powerful attack
rlm@0: types.
rlm@0: 
rlm@0: Using the =lp_solve= library was more complicated than the best-first
rlm@0: search, but yielded results quickly and efficiently. Expressing the
rlm@0: problem in a linear form does have its drawbacks, however --- it's
rlm@0: hard to ask questions such as "what is the best 3-type defensive combo
rlm@0: in terms of susceptibility?", since susceptibility is not a linear
rlm@0: function of a combo's types. It is also hard to get all the solutions
rlm@0: to a particular problem, such as all the pokemon type combinations of
rlm@0: length 8 which are immortal defense types.
rlm@0: 
rlm@0: 
rlm@0: * COMMENT main-program
rlm@0: #+begin_src clojure :tangle ../src/pokemon/lpsolve.clj :noweb yes :exports none
rlm@0: <<intro>>
rlm@0: <<body>>
rlm@0: <<declares>>
rlm@0: <<memory-management>>
rlm@0: <<get-results>>
rlm@0: <<solve>>
rlm@0: <<farmer-example>>
rlm@0: <<lp-solve>>
rlm@0: <<better-farmer>>
rlm@0: <<pokemon-lp>>
rlm@0: <<results>>
rlm@0: <<attack-oriented>>
rlm@0: #+end_src
rlm@0: 
rlm@0: 
rlm@0: * COMMENT Stuff to do.
rlm@0: ** TODO fix namespaces to not use rlm.light-base
rlm@0: