1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/org/lpsolve.org	Sun Oct 16 06:57:42 2011 -0700
     1.3 @@ -0,0 +1,1387 @@
     1.4 +#+title: Discovering Effective Pokemon Types Using Linear Optimization
     1.5 +#+author: Robert McIntyre & Dylan Holmes
     1.6 +#+EMAIL:     rlm@mit.edu
     1.7 +#+MATHJAX: align:"left" mathml:t path:"../MathJax/MathJax.js"
     1.8 +#+STYLE: <link rel="stylesheet" type="text/css" href="../css/aurellem.css" />
     1.9 +#+OPTIONS:   H:3 num:t toc:t \n:nil @:t ::t |:t ^:t -:t f:t *:t <:t
    1.10 +#+SETUPFILE: ../templates/level-0.org
    1.11 +#+INCLUDE: ../templates/level-0.org
    1.12 +
    1.13 +
    1.14 +
    1.15 +* Introduction
    1.16 +In the [[./types.org][previous post]], we used the best-first search algorithm to
    1.17 +locate the most effective Pok\eacute{}mon type
    1.18 +combinations. Afterwards, we realized that we could transform this
    1.19 +search problem into a /linear optimization problem/.  This conversion
    1.20 +offered several advantages: first, search algorithms are comparatively
    1.21 +slow, whereas linear optimization algorithms are extremely fast;
    1.22 +second, it is difficult to determine whether a search problem has any
    1.23 +solution, whereas it is straightforward to determine whether a linear
    1.24 +optimization problem has any solution; finally, because systems of
    1.25 +linear equations are so common, many programming languages have linear
    1.26 +equation solvers written for them.
    1.27 +
    1.28 +In this article, we will 
    1.29 + - Solve a simple linear optimization problem in C :: We demonstrate
    1.30 +      how to use the linear programming C library, =lp_solve=, to
    1.31 +      solve a simple linear
    1.32 +      optimization problem.
    1.33 + - Incorporate a C library into Clojure :: We will show how we gave
    1.34 +      Clojure access to the linear programming C library, =lp_solve=.
    1.35 + - Find effective Pokemon types using linear programming :: Building
    1.36 +      on our earlier code, (...)
    1.37 +- Present our results :: (!)
    1.38 + 
    1.39 +#which can be represented and solved as a system of linear equations.
    1.40 +  
    1.41 +* COMMENT  
    1.42 +This post continues the [[./types.org][previous one]] about pok\eacute{}mon types. 
    1.43 +Pok\eacute{}mon is a game in which adorable creatures battle each
    1.44 +other using fantastic attacks.  It was made into a several gameboy
    1.45 +games that all share the same battle system.  Every pok\eacute{}mon in the
    1.46 +gameboy game has one or two /types/, such as Ground, Fire, Water,
    1.47 +etc. Every pok\eacute{}mon attack has exactly one type. Certain defending
    1.48 +types are weak or strong to other attacking types.  For example, Water
    1.49 +attacks are strong against Fire pok\eacute{}mon, while Electric attacks are
    1.50 +weak against Ground Pok\eacute{}mon.  In the games, attacks can be either
    1.51 +twice as effective as normal (Water vs. Fire), neutrally effective
    1.52 +(Normal vs. Normal), half as effective (Fire vs. Water), or not
    1.53 +effective at all (Electric vs. Ground).  Thus the range of defense
    1.54 +values for a particular type is the set 0, 1/2, 1, 2. These are
    1.55 +referred to in the game as being immune, resistant, neutral, and
    1.56 +weak, respectively. I call them the /susceptance/ of one type to another.
    1.57 +
    1.58 +If a pokemon has two types, then the strengths and weakness of each
    1.59 +type are /multiplied/ together.  Thus Electric (2x weak to Ground)
    1.60 +combined with Flying (immune to Ground (0x)) is immune to
    1.61 +Ground.  Fire (2x weak to Water) combined with Water (1/2x resistant
    1.62 +to Water) is neutral to Water. If both types are resistant to another
    1.63 +type, then the combination is doubly-resistant (1/4x) to that type. If
    1.64 +both types are weak to a certain type then the combination is
    1.65 +double-weak (4x) to that type.
    1.66 +
    1.67 +** Immortal Types
    1.68 +
    1.69 +In the game, pok\eacute{}mon can have either one type, or two types. If this
    1.70 +restriction is lifted, is there any combination of types that is
    1.71 +resistant to all types?  I call such a combination an /Immortal Type/,
    1.72 +since if that type's pattern was repeated over and over again towards
    1.73 +infinity, the resulting type would be immune to all attack types.
    1.74 +
    1.75 +* Linear Programming
    1.76 +
    1.77 +** Terminology
    1.78 +Linear programming is the process of finding an optimal solution to a
    1.79 +linear equation of several variables which are constrained by some linear
    1.80 +inequalities.
    1.81 +
    1.82 +In linear programming terminology, the function to be extremized is
    1.83 +the /objective function/.
    1.84 +
    1.85 +** COMMENT 
    1.86 +First, we'll give a small example of a linear optimization problem,
    1.87 +and show how it can be solved with Clojure and =lp_solve=.  Then,
    1.88 +we'll show how finding immortal pok\eacute{}mon types can be converted
    1.89 +into a linear problem suitable for solving in the same way.
    1.90 +
    1.91 +** The Farmer's Problem
    1.92 +
    1.93 +Let's solve the Farmer's Problem, a typical linear programming problem
    1.94 +borrowed from http://lpsolve.sourceforge.net/5.5/formulate.htm.
    1.95 +
    1.96 +
    1.97 +#+BEGIN_QUOTE 
    1.98 +*The Farmer's Problem:* Suppose a farmer has 75 acres on which to
    1.99 +plant two crops: wheat and barley. To produce these crops, it costs
   1.100 +the farmer (for seed, fertilizer, etc.)  $120 per acre for the wheat
   1.101 +and $210 per acre for the barley. The farmer has $15000 available for
   1.102 +expenses. But after the harvest, the farmer must store the crops while
   1.103 +awaiting favorable market conditions. The farmer has storage space
   1.104 +for 4000 bushels. Each acre yields an average of 110 bushels of wheat
   1.105 +or 30 bushels of barley.  If the net profit per bushel of wheat (after
   1.106 +all expenses have been subtracted) is $1.30 and for barley is $2.00,
   1.107 +how should the farmer plant the 75 acres to maximize profit?
   1.108 +#+END_QUOTE
   1.109 +
   1.110 +The Farmer's Problem is to maximize profit subject to constraints on
   1.111 +available farmland, funds for expenses, and storage space.
   1.112 +
   1.113 +|          | Wheat                | Barley              | Maximum total |
   1.114 +|----------+----------------------+---------------------+--------------|
   1.115 +| /        | <                    | >                   | <>           |
   1.116 +| Farmland | \(w\) acres          | \(b\) acres         | 75 acres     |
   1.117 +| Expense  | $120 per acre        | $210 per acre       | $15000       |
   1.118 +| Storage  | 110 bushels per acre | 30 bushels per acre | 4000 bushels |
   1.119 +|----------+----------------------+---------------------+--------------|
   1.120 +| Profit   | $1.30 per bushel     | $2.00 per bushel    |              |
   1.121 +
   1.122 +*** COMMENT
   1.123 +can be represented as a linear optimization
   1.124 + problem. In this form, it is a problem with two variables\mdash{}the number of
   1.125 + acres of wheat, \(w\), and the number of acres of barley, \(b\). The
   1.126 + aim is to maximize profit, which 
   1.127 +
   1.128 + subject to three constraints: the farmer can't spend more money
   1.129 +than he has, the farmer can't use more acres than he owns, and the harvest has
   1.130 +to fit in his storage space.
   1.131 +
   1.132 +We can express these constraints succinctly using matrix
   1.133 +notation. Denoting the number of acres of barley and wheat by \(b\) and \(w\),
   1.134 +we want to maximize the expression \(143 w + 60 b\) subject to 
   1.135 +
   1.136 +\(
   1.137 +\begin{cases}
   1.138 +120 w + 210 b & \leq & 1500\\
   1.139 +110 w + 30 b & \leq & 4000\\
   1.140 +1 w + 1 w & \leq & 75
   1.141 +\end{cases}
   1.142 +\)
   1.143 +
   1.144 +#\(\begin{bmatrix}120&210\\110&30\\1 &
   1.145 +#1\end{bmatrix}\;\begin{bmatrix}w\\b\end{bmatrix}
   1.146 +#\leq \begin{bmatrix}\$15000\\4000\text{ bushels}\\75\text{ acres}\end{bmatrix}\)
   1.147 +
   1.148 +
   1.149 +** Solution using LP Solve
   1.150 +#(LP solve is available at http://www.example.com.)
   1.151 +In a new file,  =farmer.lp=, we list the variables and constraints 
   1.152 +of our problem using LP Solve syntax.
   1.153 +
   1.154 +#+begin_src lpsolve :tangle farmer.lp
   1.155 +/* Maximize Total Profit */
   1.156 +max: +143 wheat +60 barley;
   1.157 +
   1.158 +
   1.159 +/* --------  Constraints  --------*/
   1.160 +
   1.161 +/* the farmer can't spend more money than he has */
   1.162 ++120 wheat +210 barley <= 15000;
   1.163 +
   1.164 +/* the harvest has to fit in his storage space */
   1.165 ++110 wheat +30 barley <= 4000;
   1.166 +
   1.167 +/* he can't use more acres than he owns */
   1.168 ++wheat +barley <= 75;
   1.169 +#+end_src
   1.170 +
   1.171 +
   1.172 +#This is a set of linear equations ideal for solving using a program like
   1.173 +#=lp_solve=. In Linear Algebra terms we are maximizing the linear function 
   1.174 +
   1.175 +#\(\text{profit} = 143\text{ wheat} + 60\text{ barley}\), subject to the constraints
   1.176 +
   1.177 +#Ax <= b,
   1.178 +
   1.179 +#where A is [120 210 110 30 1 1], x is [wheat barley] and b is [15000
   1.180 +#4000 75].
   1.181 +
   1.182 +Running the =lp_solve= program on =farmer.lp= yields the following output.
   1.183 +
   1.184 +#+begin_src sh :exports both :results scalar
   1.185 +~/roBin/lpsolve/lp_solve ~/aurellem/src/pokemon/farmer.lp
   1.186 +#+end_src
   1.187 +
   1.188 +#+results:
   1.189 +: 
   1.190 +: Value of objective function: 6315.62500000
   1.191 +: 
   1.192 +: Actual values of the variables:
   1.193 +: wheat                      21.875
   1.194 +: barley                     53.125
   1.195 +
   1.196 +This shows that the farmer can maximize his profit by planting 21.875
   1.197 +of the available acres with wheat and the remaining 53.125 acres with
   1.198 +barley; by doing so, he will make $6315.62(5) in profit.
   1.199 +
   1.200 +
   1.201 +#The farmer can make a profit of $6315.62 by planting 21.875 acres of
   1.202 +#his land with wheat and the other 53.125 acres of his land with barley.
   1.203 +
   1.204 +* Incorporating  =lp_solve= into Clojure 
   1.205 +
   1.206 +There is a Java API available which enables Java programs to use Lp
   1.207 +Solve. Although Clojure can use this Java API directly, the
   1.208 +interaction between Java, C, and Clojure is clumsy:
   1.209 +
   1.210 +
   1.211 +The Java API for LP Solve makes it possible to use Lp Solve algorithms
   1.212 +within Java. Although Clojure can use this  Java API directly, 
   1.213 +
   1.214 +
   1.215 +** The Farmer's Problem in Clojure
   1.216 +We are going to solve the same problem involving wheat and barley,
   1.217 +that we did above, but this time using clojure and the lpsolve API.
   1.218 +
   1.219 +#Because we ultimately intend to use Lp Solve to find optimal Pokemon type combinations.
   1.220 +# we want to solve linear optimization problems within Clojure, the language 
   1.221 +
   1.222 +** Setup
   1.223 +=lp_solve= is a crufty =C= program which already comes with a JNI
   1.224 +interface written by Juergen Ebert.  It's API is not
   1.225 +particularly friendly from a functional/immutable perspective, but
   1.226 +with a little work, we can build something that works great with
   1.227 +clojure.
   1.228 +
   1.229 +#+srcname: intro
   1.230 +#+begin_src clojure :results silent
   1.231 +(ns pokemon.lpsolve
   1.232 +  (:use rlm.ns-rlm))
   1.233 +(rlm.ns-rlm/ns-clone rlm.light-base)
   1.234 +(use 'clojure.set)
   1.235 +(import 'lpsolve.LpSolve)
   1.236 +(use '[clojure [pprint :only [pprint]]])
   1.237 +#+end_src
   1.238 +
   1.239 +The LpSolve Java interface is available from the same site as
   1.240 +=lp_solve= itself, http://lpsolve.sourceforge.net/ 
   1.241 +Using it is the same as many other =C=
   1.242 +programs. There are excellent instructions to get set
   1.243 +up.  The short version is that you must call Java with
   1.244 +=-Djava.library.path=/path/to/lpsolve/libraries= and also add the
   1.245 +libraries to your export =LD_LIBRARY_PATH= if you are using Linux. For
   1.246 +example, in my =.bashrc= file, I have the line
   1.247 +=LD_LIBRARY_PATH=$HOME/roBin/lpsolve:$LD_LIBRARY_PATH=.
   1.248 +If everything is set-up correctly, 
   1.249 +
   1.250 +#+srcname: body 
   1.251 +#+begin_src clojure :results verbatim :exports both
   1.252 +(import 'lpsolve.LpSolve)
   1.253 +#+end_src
   1.254 +
   1.255 +#+results: body
   1.256 +: lpsolve.LpSolve
   1.257 +
   1.258 +should run with no problems.
   1.259 +
   1.260 +** Making a DSL to talk with LpSolve
   1.261 +*** Problems
   1.262 +Since we are using a =C= wrapper, we have to deal with manual memory
   1.263 +management for the =C= structures which are wrapped by the =LpSolve=
   1.264 +object. Memory leaks in =LpSolve= instances can crash the JVM, so it's
   1.265 +very important to get it right.  Also, the Java wrapper follows the
   1.266 +=C= tradition closely and defines many =static final int= constants
   1.267 +for the different states of the =LpSolve= instance instead of using Java
   1.268 +enums.  The calling convention for adding rows and columns to
   1.269 +the constraint matrix is rather complicated and must be done column by
   1.270 +column or row by row, which can be error prone.  Finally, I'd like to
   1.271 +gather all the important output information from the =LpSolve= instance
   1.272 +into a final, immutable structure.
   1.273 +
   1.274 +In summary, the issues I'd like to address are:
   1.275 +
   1.276 +- reliable memory management
   1.277 +- functional interface to =LpSolve=
   1.278 +- intelligible, immutable output
   1.279 +
   1.280 +To deal with these issues I'll create four functions for interfacing
   1.281 +with =LpSolve=
   1.282 +
   1.283 +#+srcname: declares
   1.284 +#+begin_src clojure :results silent 
   1.285 +(in-ns 'pokemon.lpsolve)
   1.286 +
   1.287 +;; deal with automatic memory management for LpSolve instance.
   1.288 +(declare linear-program)
   1.289 +
   1.290 +;; functional interface to LpSolve
   1.291 +(declare lp-solve)
   1.292 +
   1.293 +;; immutable output from lp-solve
   1.294 +(declare solve get-results)
   1.295 +#+end_src
   1.296 +
   1.297 +*** Memory Management
   1.298 +
   1.299 +Every instance of =LpSolve= must be manually garbage collected via a
   1.300 +call to =deleteLP=. I use a non-hygienic macro similar to =with-open=
   1.301 +to ensure that =deleteLP= is always called.
   1.302 +
   1.303 +#+srcname: memory-management
   1.304 +#+begin_src clojure :results silent
   1.305 +(in-ns 'pokemon.lpsolve)
   1.306 +(defmacro linear-program
   1.307 +  "solve a linear programming problem using LpSolve syntax.
   1.308 +   within the macro, the variable =lps= is bound to the LpSolve instance."
   1.309 +  [& statements]
   1.310 +  (list 'let '[lps (LpSolve/makeLp 0 0)]
   1.311 +	(concat '(try)
   1.312 +		statements
   1.313 +		;; always free the =C= data structures.
   1.314 +		'((finally (.deleteLp lps))))))
   1.315 +#+end_src
   1.316 +
   1.317 +
   1.318 +The macro captures the variable =lps= within its body, providing for a
   1.319 +convenient way to access the object using any of the methods of the
   1.320 +=LpSolve= API without having to worry about when to call
   1.321 +=deleteLP=. 
   1.322 +
   1.323 +*** Sensible Results
   1.324 +The =linear-program= macro deletes the actual =lps= object once it is
   1.325 +done working, so it's important to collect the important results and
   1.326 +add return them in an immutable structure at the end.
   1.327 +
   1.328 +#+srcname: get-results
   1.329 +#+begin_src clojure :results silent
   1.330 +(in-ns 'pokemon.lpsolve)
   1.331 +
   1.332 +(defrecord LpSolution
   1.333 +  [objective-value
   1.334 +   optimal-values
   1.335 +   variable-names
   1.336 +   solution
   1.337 +   status
   1.338 +   model])
   1.339 +
   1.340 +(defn model
   1.341 +  "Returns a textual representation of the problem suitable for
   1.342 +  direct input to the =lp_solve= program (lps format)"
   1.343 +  [#^LpSolve lps]
   1.344 +  (let [target (java.io.File/createTempFile "lps" ".lp")]
   1.345 +    (.writeLp lps (.getPath target))
   1.346 +    (slurp target)))
   1.347 +
   1.348 +(defn results
   1.349 +  "given an LpSolve object, solves the object and returns a map of the
   1.350 +  essential values which compose the solution."
   1.351 +  [#^LpSolve lps]
   1.352 +  (locking lps
   1.353 +    (let [status (solve lps)
   1.354 +	  number-of-variables (.getNcolumns lps)
   1.355 +	  optimal-values (double-array number-of-variables)
   1.356 +	  optimal-values (do (.getVariables lps optimal-values)
   1.357 +			     (seq optimal-values))
   1.358 +	  variable-names
   1.359 +	  (doall ;; the doall is necessary since the lps object might
   1.360 +	   ;; soon be deleted
   1.361 +	   (map
   1.362 +	    #(.getColName lps (inc %))
   1.363 +	    (range number-of-variables)))
   1.364 +	  model (model lps)]
   1.365 +      (LpSolution.
   1.366 +       (.getObjective lps)
   1.367 +       optimal-values
   1.368 +       variable-names
   1.369 +       (zipmap variable-names optimal-values)
   1.370 +       status
   1.371 +       model))))
   1.372 +
   1.373 +#+end_src
   1.374 +
   1.375 +Here I've created an object called =LpSolution= which stores the
   1.376 +important results from a session with =lp_solve=.  Of note is the
   1.377 +=model= function which returns the problem in a form that can be
   1.378 +solved by other linear programming packages.
   1.379 +
   1.380 +*** Solution Status of an LpSolve Object
   1.381 +
   1.382 +#+srcname: solve
   1.383 +#+begin_src clojure :results silent       
   1.384 +(in-ns 'pokemon.lpsolve)
   1.385 +
   1.386 +(defn static-integer?
   1.387 +  "does the field represent a static integer constant?"
   1.388 +  [#^java.lang.reflect.Field field]
   1.389 +  (and (java.lang.reflect.Modifier/isStatic (.getModifiers field))
   1.390 +       (integer? (.get field nil))))
   1.391 +
   1.392 +(defn integer-constants [class]
   1.393 +  (filter static-integer? (.getFields class)))
   1.394 +
   1.395 +(defn-memo constant-map
   1.396 +  "Takes a class and creates a map of the static constant integer
   1.397 +  fields with their names.  This helps with C wrappers where they have
   1.398 +  just defined a bunch of integer constants instead of enums"
   1.399 +  [class]
   1.400 +     (let [integer-fields (integer-constants class)]
   1.401 +       (into (sorted-map)
   1.402 +	     (zipmap (map #(.get % nil) integer-fields)
   1.403 +		     (map #(.getName %) integer-fields)))))
   1.404 +	     
   1.405 +(defn solve
   1.406 +  "Solve an instance of LpSolve and return a string representing the
   1.407 +  status of the computation. Will only solve a particular LpSolve
   1.408 +  instance once."
   1.409 +  [#^LpSolve lps]
   1.410 +  ((constant-map LpSolve)
   1.411 +   (.solve lps)))
   1.412 +
   1.413 +#+end_src
   1.414 +
   1.415 +The =.solve= method of an =LpSolve= object only returns an integer code
   1.416 +to specify the status of the computation.  The =solve= method here
   1.417 +uses reflection to look up the actual name of the status code and
   1.418 +returns a more helpful status message that is also resistant to
   1.419 +changes in the meanings of the code numbers.
   1.420 +
   1.421 +*** The Farmer Example in Clojure, Pass 1
   1.422 +
   1.423 +Now we can implement a nicer version of the examples from the
   1.424 +[[http://lpsolve.sourceforge.net/][=lp\_solve= website]]. The following is a more or less
   1.425 +line-by-line translation of the Java code from that example.
   1.426 +
   1.427 +#+srcname: farmer-example
   1.428 +#+begin_src clojure :results silent
   1.429 +(in-ns 'pokemon.lpsolve)
   1.430 +(defn farmer-example []
   1.431 +  (linear-program
   1.432 +   (results
   1.433 +    (doto lps
   1.434 +      ;; name the columns
   1.435 +      (.setColName 1 "wheat")
   1.436 +      (.setColName 2 "barley")
   1.437 +      (.setAddRowmode true)
   1.438 +      ;; row 1 : 120x + 210y <= 15000
   1.439 +      (.addConstraintex 2
   1.440 +			(double-array [120 210])
   1.441 +			(int-array [1 2])
   1.442 +			LpSolve/LE
   1.443 +			15e3)
   1.444 +      ;; row 2 : 110x + 30y <= 4000
   1.445 +      (.addConstraintex 2
   1.446 +			(double-array [110 30])
   1.447 +			(int-array [1 2])
   1.448 +			LpSolve/LE
   1.449 +			4e3)
   1.450 +      ;; ;; row 3 : x + y <= 75
   1.451 +      (.addConstraintex 2
   1.452 +			(double-array [1 1])
   1.453 +			(int-array [1 2])
   1.454 +			LpSolve/LE
   1.455 +			75)
   1.456 +      (.setAddRowmode false)
   1.457 +
   1.458 +      ;; add constraints
   1.459 +      (.setObjFnex 2
   1.460 +		   (double-array [143 60])
   1.461 +		   (int-array [1 2]))
   1.462 +            
   1.463 +      ;; set this as a maximization problem
   1.464 +      (.setMaxim)))))
   1.465 +
   1.466 +#+end_src
   1.467 +
   1.468 +#+begin_src clojure :results output :exports both 
   1.469 +(clojure.pprint/pprint
   1.470 + (:solution (pokemon.lpsolve/farmer-example)))
   1.471 +#+end_src
   1.472 +
   1.473 +#+results:
   1.474 +: {"barley" 53.12499999999999, "wheat" 21.875}
   1.475 +
   1.476 +And it works as expected!
   1.477 +
   1.478 +*** The Farmer Example in Clojure, Pass 2
   1.479 +We don't have to worry about memory management anymore, and the farmer
   1.480 +example is about half as long as the example from the =LpSolve=
   1.481 +website, but we can still do better.  Solving linear problems is all
   1.482 +about the constraint matrix $A$ , the objective function $c$, and the
   1.483 +right-hand-side $b$, plus whatever other options one cares to set for
   1.484 +the particular instance of =lp_solve=.  Why not make a version of
   1.485 +=linear-program= that takes care of initialization?
   1.486 +
   1.487 +
   1.488 +
   1.489 +#+srcname: lp-solve
   1.490 +#+begin_src clojure :results silent       
   1.491 +(in-ns 'pokemon.lpsolve)
   1.492 +(defn initialize-lpsolve-row-oriented
   1.493 +  "fill in an lpsolve instance using a constraint matrix =A=, the
   1.494 +  objective function =c=, and the right-hand-side =b="
   1.495 +  [#^LpSolve lps A b c]
   1.496 +  ;; set the name of the last column to _something_
   1.497 +  ;; this appears to be necessary to ensure proper initialization.
   1.498 +  (.setColName lps (count c) (str "C" (count c)))
   1.499 +
   1.500 +  ;; This is the recommended way to "fill-in" an lps instance from the 
   1.501 +  ;; documentation. First, set row mode, then set the objective
   1.502 +  ;; function, then set each row of the problem, and then turn off row
   1.503 +  ;; mode. 
   1.504 +  (.setAddRowmode lps true)
   1.505 +  (.setObjFnex lps (count c)
   1.506 +	       (double-array c)
   1.507 +	       (int-array (range 1 (inc (count c)))))
   1.508 +  (dorun
   1.509 +   (for [n (range (count A))]
   1.510 +     (let [row (nth A n)
   1.511 +	   row-length (int (count row))]
   1.512 +       (.addConstraintex lps
   1.513 +			 row-length
   1.514 +			 (double-array row)
   1.515 +			 (int-array (range 1 (inc row-length)))
   1.516 +			 LpSolve/LE
   1.517 +			 (double (nth b n))))))
   1.518 +  (.setAddRowmode lps false)
   1.519 +  lps)
   1.520 +
   1.521 +
   1.522 +(defmacro lp-solve
   1.523 +  "by default:,
   1.524 +   minimize (* c x), subject to (<= (* A x) b),
   1.525 +   using continuous variables.  You may set any number of
   1.526 +   other options as in the LpSolve API." 
   1.527 +  [A b c & lp-solve-forms]
   1.528 +  ;; assume that A is a vector of vectors
   1.529 +  (concat
   1.530 +   (list 'linear-program
   1.531 +	 (list 'initialize-lpsolve-row-oriented 'lps A b c))
   1.532 +   `~lp-solve-forms))
   1.533 + #+end_src
   1.534 +
   1.535 +Now, we can use a much more functional approach to solving the
   1.536 +farmer's problem:
   1.537 +
   1.538 +#+srcname: better-farmer
   1.539 +#+begin_src clojure :results silent
   1.540 +(in-ns 'pokemon.lpsolve)
   1.541 +(defn better-farmer-example []
   1.542 +  (lp-solve  [[120 210]
   1.543 +	      [110 30]
   1.544 +	      [1 1]]
   1.545 +	     [15000
   1.546 +	      4000
   1.547 +	      75]
   1.548 +	     [143 60]
   1.549 +	     (.setColName lps 1 "wheat")
   1.550 +	     (.setColName lps 2 "barley")
   1.551 +	     (.setMaxim lps)
   1.552 +	     (results lps)))
   1.553 +#+end_src
   1.554 +
   1.555 +#+begin_src clojure  :exports both :results verbatim
   1.556 +(vec (:solution (pokemon.lpsolve/better-farmer-example)))
   1.557 +#+end_src
   1.558 +
   1.559 +#+results:
   1.560 +: [["barley" 53.12499999999999] ["wheat" 21.875]]
   1.561 +
   1.562 +Notice that both the inputs to =better-farmer-example= and the results
   1.563 +are immutable.
   1.564 +
   1.565 +* Using LpSolve to find Immortal Types
   1.566 +** Converting the Pokemon problem into a linear form
   1.567 +How can the original question about pok\eacute{}mon types be converted
   1.568 +into a linear problem? 
   1.569 +
   1.570 +Pokemon types can be considered to be vectors of numbers representing
   1.571 +their susceptances to various attacking types, so Water might look
   1.572 +something like this.
   1.573 +
   1.574 +#+begin_src clojure :results scalar :exports both
   1.575 +(:water (pokemon.types/defense-strengths))
   1.576 +#+end_src 
   1.577 +
   1.578 +#+results:
   1.579 +: [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5]
   1.580 +
   1.581 +Where the numbers represent the susceptibility of Water to the
   1.582 +attacking types in the following order:
   1.583 +
   1.584 +#+begin_src clojure :results output :exports both
   1.585 +(clojure.pprint/pprint
   1.586 + (pokemon.types/type-names))
   1.587 +#+end_src 
   1.588 +
   1.589 +#+results:
   1.590 +#+begin_example
   1.591 +[:normal
   1.592 + :fire
   1.593 + :water
   1.594 + :electric
   1.595 + :grass
   1.596 + :ice
   1.597 + :fighting
   1.598 + :poison
   1.599 + :ground
   1.600 + :flying
   1.601 + :psychic
   1.602 + :bug
   1.603 + :rock
   1.604 + :ghost
   1.605 + :dragon
   1.606 + :dark
   1.607 + :steel]
   1.608 +#+end_example
   1.609 +
   1.610 +
   1.611 +So, for example, Water is /resistant/ (x0.5) against Fire, which is
   1.612 +the second element in the list.
   1.613 +
   1.614 +To combine types, these sorts of vectors are multiplied together
   1.615 +pair-wise to yield the resulting combination.  
   1.616 +
   1.617 +Unfortunately, we need some way to add two type vectors together
   1.618 +instead of multiplying them if we want to solve the problem with
   1.619 +=lp_solve=.  Taking the log of the vector does just the trick.
   1.620 +
   1.621 +If we make a matrix with each column being the log (base 2) of the
   1.622 +susceptance of each type, then finding an immortal type corresponds to
   1.623 +setting each constraint (the $b$ vector) to -1 (since log_2(1/2) = -1)
   1.624 +and setting the constraint vector $c$ to all ones, which means that we
   1.625 +want to find the immortal type which uses the least amount of types.
   1.626 +
   1.627 +#+srcname: pokemon-lp
   1.628 +#+begin_src clojure :results silent
   1.629 +(in-ns 'pokemon.lpsolve)
   1.630 +
   1.631 +(require 'pokemon.types)
   1.632 +(require 'incanter.core)
   1.633 +
   1.634 +(defn log-clamp-matrix [matrix]
   1.635 +  ;; we have to clamp the Infinities to a more reasonable negative
   1.636 +  ;; value because lp_solve does not play well with infinities in its
   1.637 +  ;; constraint matrix.
   1.638 +  (map (fn [row] (map #(if (= Double/NEGATIVE_INFINITY %) -1e3 %) row))
   1.639 +       (incanter.core/log2
   1.640 +	(incanter.core/trans
   1.641 +	 matrix))))
   1.642 +
   1.643 +;; constraint matrices
   1.644 +(defn log-defense-matrix []
   1.645 +  (log-clamp-matrix
   1.646 +   (doall (map (pokemon.types/defense-strengths)
   1.647 +	       (pokemon.types/type-names)))))
   1.648 +
   1.649 +(defn log-attack-matrix []
   1.650 +  (incanter.core/trans (log-defense-matrix)))
   1.651 +
   1.652 +;; target vectors
   1.653 +(defn all-resistant []
   1.654 +  (doall (map (constantly -1) (pokemon.types/type-names))))
   1.655 +
   1.656 +(defn all-weak []
   1.657 +  (doall (map (constantly 1) (pokemon.types/type-names))))
   1.658 +
   1.659 +(defn all-neutral []
   1.660 +  (doall (map (constantly 0) (pokemon.types/type-names))))
   1.661 +
   1.662 +
   1.663 +;; objective functions
   1.664 +(defn number-of-types []
   1.665 +  (doall (map (constantly 1) (pokemon.types/type-names))))
   1.666 +
   1.667 +(defn set-constraints
   1.668 +  "sets all the constraints for an lpsolve instance to the given
   1.669 +  constraint. =constraint= here is one of the LpSolve constants such
   1.670 +  as LpSolve/EQ."
   1.671 +  [#^LpSolve lps constraint]
   1.672 +  (dorun (map (fn [index] (.setConstrType lps index constraint))
   1.673 +	      ;; ONE based indexing!!!
   1.674 +	      (range 1 (inc (.getNrows lps))))))
   1.675 +
   1.676 +
   1.677 +(defn set-discrete
   1.678 +  "sets every variable in an lps problem to be a discrete rather than
   1.679 +  continuous variable"
   1.680 +  [#^LpSolve lps]
   1.681 +  (dorun (map (fn [index] (.setInt lps index true))
   1.682 +	      ;; ONE based indexing!!!
   1.683 +	      (range 1 (inc (.getNcolumns lps))))))
   1.684 +
   1.685 +(defn set-variable-names
   1.686 +  "sets the variable names of the problem given a vector of names"
   1.687 +  [#^LpSolve lps names]
   1.688 +  (dorun
   1.689 +   (map (fn [[index name]]
   1.690 +	  (.setColName lps  (inc index) (str name)))
   1.691 +	;; ONE based indexing!!!
   1.692 +	(indexed names))))
   1.693 +
   1.694 +(defn poke-solve 
   1.695 +  ([poke-matrix target objective-function constraint min-num-types]
   1.696 +     ;; must have at least one type
   1.697 +     (let [poke-matrix
   1.698 +	   (concat poke-matrix
   1.699 +		   [(map (constantly 1)
   1.700 +			 (range (count (first poke-matrix))))])
   1.701 +	   target (concat target [min-num-types])]
   1.702 +       (lp-solve poke-matrix target objective-function
   1.703 +		 (set-constraints lps constraint)
   1.704 +		 ;; must have more than min-num-types
   1.705 +		 (.setConstrType lps (count target) LpSolve/GE)
   1.706 +		 (set-discrete lps)
   1.707 +		 (set-variable-names lps (pokemon.types/type-names))
   1.708 +		 (results lps))))
   1.709 +  ([poke-matrix target objective-function constraint]
   1.710 +     ;; at least one type
   1.711 +     (poke-solve poke-matrix target objective-function constraint 1)))
   1.712 +
   1.713 +(defn solution 
   1.714 +  "If the results of an lpsolve operation are feasible, returns the
   1.715 +  results. Otherwise, returns the error."
   1.716 +  [results]
   1.717 +  (if (not (= (:status results) "OPTIMAL"))
   1.718 +    (:status results)
   1.719 +    (:solution results)))
   1.720 +
   1.721 +#+end_src
   1.722 +
   1.723 +With this, we are finally able to get some results.
   1.724 +
   1.725 +** Results
   1.726 +#+srcname: results
   1.727 +#+begin_src clojure :results silent  
   1.728 +(in-ns 'pokemon.lpsolve)
   1.729 +
   1.730 +(defn best-defense-type
   1.731 +  "finds a type combination which is resistant to all attacks."
   1.732 +  []
   1.733 +  (poke-solve 
   1.734 +   (log-defense-matrix) (all-resistant) (number-of-types) LpSolve/LE))
   1.735 +
   1.736 +(defn worst-attack-type
   1.737 +  "finds the attack type which is not-very-effective against all pure
   1.738 +  defending types (each single defending type is resistant to this
   1.739 +  attack combination"
   1.740 +  []
   1.741 +  (poke-solve
   1.742 +   (log-attack-matrix)  (all-resistant) (number-of-types) LpSolve/LE))
   1.743 +
   1.744 +(defn worst-defense-type
   1.745 +  "finds a defending type that is weak to all single attacking types."
   1.746 +  []
   1.747 +  (poke-solve
   1.748 +   (log-defense-matrix) (all-weak) (number-of-types) LpSolve/GE))
   1.749 +
   1.750 +(defn best-attack-type
   1.751 +  "finds an attack type which is super effective against all single
   1.752 +defending types"
   1.753 +  []
   1.754 +  (poke-solve
   1.755 +   (log-attack-matrix) (all-weak) (number-of-types) LpSolve/GE))
   1.756 +
   1.757 +(defn solid-defense-type
   1.758 +  "finds a defense type which is either neutral or resistant to all
   1.759 +  single attacking types"
   1.760 +  []
   1.761 +  (poke-solve
   1.762 +   (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/LE))
   1.763 +
   1.764 +(defn solid-attack-type
   1.765 +  "finds an attack type which is either neutral or super-effective to
   1.766 +  all single attacking types."
   1.767 +  []
   1.768 +  (poke-solve
   1.769 +   (log-attack-matrix) (all-neutral) (number-of-types) LpSolve/GE))
   1.770 +
   1.771 +(defn weak-defense-type
   1.772 +  "finds a defense type which is either neutral or weak to all single
   1.773 +  attacking types"
   1.774 +  []
   1.775 +  (poke-solve
   1.776 +   (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/GE))
   1.777 +
   1.778 +(defn neutral-defense-type
   1.779 +  "finds a defense type which is perfectly neutral to all attacking
   1.780 +  types."
   1.781 +  []
   1.782 +  (poke-solve
   1.783 +   (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/EQ))
   1.784 +
   1.785 +#+end_src
   1.786 +
   1.787 +*** Strongest Attack/Defense Combinations
   1.788 +    
   1.789 +#+begin_src clojure :results output :exports both 
   1.790 +(clojure.pprint/pprint
   1.791 + (pokemon.lpsolve/solution (pokemon.lpsolve/best-defense-type)))
   1.792 +#+end_src
   1.793 +
   1.794 +#+results:
   1.795 +#+begin_example
   1.796 +{":normal" 0.0,
   1.797 + ":ground" 1.0,
   1.798 + ":poison" 2.0,
   1.799 + ":flying" 1.0,
   1.800 + ":fighting" 0.0,
   1.801 + ":dragon" 0.0,
   1.802 + ":fire" 0.0,
   1.803 + ":dark" 1.0,
   1.804 + ":ice" 0.0,
   1.805 + ":steel" 1.0,
   1.806 + ":ghost" 0.0,
   1.807 + ":electric" 0.0,
   1.808 + ":bug" 0.0,
   1.809 + ":psychic" 0.0,
   1.810 + ":grass" 0.0,
   1.811 + ":water" 2.0,
   1.812 + ":rock" 0.0}
   1.813 +#+end_example
   1.814 +
   1.815 +# #+results-old:
   1.816 +# : [[":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]]
   1.817 +
   1.818 +
   1.819 +This is the immortal type combination we've been looking for.  By
   1.820 +combining Steel, Water, Poison, and three types which each have complete
   1.821 +immunities to various other types, we've created a type that is resistant to
   1.822 +all attacking types.
   1.823 +
   1.824 +#+begin_src clojure :results output :exports both 
   1.825 +(clojure.pprint/pprint
   1.826 + (pokemon.types/susceptibility 
   1.827 +  [:poison :poison :water :water :steel :ground :flying :dark]))
   1.828 +#+end_src
   1.829 +
   1.830 +#+results:
   1.831 +#+begin_example
   1.832 +{:water 1/2,
   1.833 + :psychic 0,
   1.834 + :dragon 1/2,
   1.835 + :fire 1/2,
   1.836 + :ice 1/2,
   1.837 + :grass 1/2,
   1.838 + :ghost 1/4,
   1.839 + :poison 0,
   1.840 + :flying 1/2,
   1.841 + :normal 1/2,
   1.842 + :rock 1/2,
   1.843 + :electric 0,
   1.844 + :ground 0,
   1.845 + :fighting 1/2,
   1.846 + :dark 1/4,
   1.847 + :steel 1/8,
   1.848 + :bug 1/8}
   1.849 +#+end_example
   1.850 +
   1.851 +# #+results-old:
   1.852 +# : {: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}
   1.853 +
   1.854 +
   1.855 +Cool!
   1.856 +
   1.857 +#+begin_src clojure :results output :exports both
   1.858 +(clojure.pprint/pprint
   1.859 + (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type)))
   1.860 +#+end_src
   1.861 +
   1.862 +#+results:
   1.863 +#+begin_example
   1.864 +{":normal" 0.0,
   1.865 + ":ground" 0.0,
   1.866 + ":poison" 0.0,
   1.867 + ":flying" 0.0,
   1.868 + ":fighting" 0.0,
   1.869 + ":dragon" 0.0,
   1.870 + ":fire" 0.0,
   1.871 + ":dark" 1.0,
   1.872 + ":ice" 0.0,
   1.873 + ":steel" 0.0,
   1.874 + ":ghost" 1.0,
   1.875 + ":electric" 0.0,
   1.876 + ":bug" 0.0,
   1.877 + ":psychic" 0.0,
   1.878 + ":grass" 0.0,
   1.879 + ":water" 0.0,
   1.880 + ":rock" 0.0}
   1.881 +#+end_example
   1.882 +
   1.883 +Dark and Ghost are the best dual-type combo, and are resistant or
   1.884 +neutral to all types.
   1.885 +
   1.886 +#+begin_src clojure :results output :exports both
   1.887 +(clojure.pprint/pprint
   1.888 + (pokemon.types/old-school
   1.889 +  (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type))))
   1.890 +#+end_src
   1.891 +
   1.892 +#+results:
   1.893 +#+begin_example
   1.894 +{":normal" 0.0,
   1.895 + ":ground" 0.0,
   1.896 + ":poison" 0.0,
   1.897 + ":flying" 0.0,
   1.898 + ":fighting" 0.0,
   1.899 + ":dragon" 0.0,
   1.900 + ":fire" 0.0,
   1.901 + ":ice" 0.0,
   1.902 + ":ghost" 1.0,
   1.903 + ":electric" 0.0,
   1.904 + ":bug" 0.0,
   1.905 + ":psychic" 1.0,
   1.906 + ":grass" 0.0,
   1.907 + ":water" 0.0,
   1.908 + ":rock" 0.0}
   1.909 +#+end_example
   1.910 +
   1.911 +Ghost and Psychic are a powerful dual type combo in the original games,
   1.912 +due to a glitch which made Psychic immune to Ghost type attacks, even
   1.913 +though the game claims that Ghost is strong to Psychic.
   1.914 +
   1.915 +#+begin_src clojure :results verbatim :exports both
   1.916 +(pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type))
   1.917 +#+end_src
   1.918 +
   1.919 +#+results:
   1.920 +: INFEASIBLE
   1.921 +
   1.922 +#+begin_src clojure :results verbatim :exports both
   1.923 +(pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))
   1.924 +#+end_src
   1.925 +
   1.926 +#+results:
   1.927 +: INFEASIBLE
   1.928 +
   1.929 +
   1.930 +#+begin_src clojure :results verbatim :exports both
   1.931 +(pokemon.types/old-school
   1.932 + (pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type)))
   1.933 +#+end_src
   1.934 +
   1.935 +#+results:
   1.936 +: INFEASIBLE
   1.937 +
   1.938 +
   1.939 +#+begin_src clojure :results output :exports both
   1.940 +(clojure.pprint/pprint
   1.941 + (pokemon.types/old-school
   1.942 +  (pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))))
   1.943 +#+end_src
   1.944 +
   1.945 +#+results:
   1.946 +#+begin_example
   1.947 +{":normal" 0.0,
   1.948 + ":ground" 0.0,
   1.949 + ":poison" 0.0,
   1.950 + ":flying" 0.0,
   1.951 + ":fighting" 0.0,
   1.952 + ":dragon" 1.0,
   1.953 + ":fire" 0.0,
   1.954 + ":ice" 0.0,
   1.955 + ":ghost" 0.0,
   1.956 + ":electric" 0.0,
   1.957 + ":bug" 0.0,
   1.958 + ":psychic" 0.0,
   1.959 + ":grass" 0.0,
   1.960 + ":water" 0.0,
   1.961 + ":rock" 0.0}
   1.962 +#+end_example
   1.963 +
   1.964 +The best attacking type combination is strangely Dragon from the
   1.965 +original games.  It is neutral against all the original types except
   1.966 +for Dragon, which it is strong against.  There is no way to make an
   1.967 +attacking type that is strong against every type, or even one that is
   1.968 +strong or neutral against every type, in the new games.
   1.969 +
   1.970 +
   1.971 +*** Weakest Attack/Defense Combinations
   1.972 +
   1.973 +#+begin_src clojure :results output :exports both
   1.974 +(clojure.pprint/pprint
   1.975 + (pokemon.types/old-school
   1.976 +  (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type))))
   1.977 +#+end_src
   1.978 +
   1.979 +#+results:
   1.980 +#+begin_example
   1.981 +{":normal" 5.0,
   1.982 + ":ground" 0.0,
   1.983 + ":poison" 0.0,
   1.984 + ":flying" 0.0,
   1.985 + ":fighting" 0.0,
   1.986 + ":dragon" 0.0,
   1.987 + ":fire" 1.0,
   1.988 + ":ice" 2.0,
   1.989 + ":ghost" 1.0,
   1.990 + ":electric" 1.0,
   1.991 + ":bug" 1.0,
   1.992 + ":psychic" 0.0,
   1.993 + ":grass" 3.0,
   1.994 + ":water" 2.0,
   1.995 + ":rock" 0.0}
   1.996 +#+end_example
   1.997 +
   1.998 +# #+results-old:
   1.999 +# : [[":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]]
  1.1000 +
  1.1001 +#+begin_src clojure :results output :exports both
  1.1002 +(clojure.pprint/pprint
  1.1003 + (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type)))
  1.1004 +#+end_src
  1.1005 +
  1.1006 +#+results:
  1.1007 +#+begin_example
  1.1008 +{":normal" 4.0,
  1.1009 + ":ground" 1.0,
  1.1010 + ":poison" 1.0,
  1.1011 + ":flying" 0.0,
  1.1012 + ":fighting" 1.0,
  1.1013 + ":dragon" 0.0,
  1.1014 + ":fire" 0.0,
  1.1015 + ":dark" 0.0,
  1.1016 + ":ice" 4.0,
  1.1017 + ":steel" 0.0,
  1.1018 + ":ghost" 1.0,
  1.1019 + ":electric" 3.0,
  1.1020 + ":bug" 0.0,
  1.1021 + ":psychic" 1.0,
  1.1022 + ":grass" 1.0,
  1.1023 + ":water" 1.0,
  1.1024 + ":rock" 2.0}
  1.1025 +#+end_example
  1.1026 +
  1.1027 +# #+results-old:
  1.1028 +# : [[":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]]
  1.1029 +
  1.1030 +
  1.1031 +This is an extremely interesting type combination, in that it uses
  1.1032 +quite a few types.
  1.1033 +
  1.1034 +#+begin_src clojure :results verbatim :exports both
  1.1035 +(reduce + (vals (:solution (pokemon.lpsolve/worst-attack-type))))
  1.1036 +#+end_src
  1.1037 +
  1.1038 +#+results:
  1.1039 +: 20.0
  1.1040 +
  1.1041 +20 types is the /minimum/ number of types before the attacking
  1.1042 +combination is not-very-effective or worse against all defending
  1.1043 +types. This would probably have been impossible to discover using
  1.1044 +best-first search, since it involves such an intricate type
  1.1045 +combination.
  1.1046 +
  1.1047 +It's so interesting that it takes 20 types to make an attack type that
  1.1048 +is weak to all types that the combination merits further investigation.
  1.1049 +
  1.1050 +Unfortunately, all of the tools that we've written so far are focused
  1.1051 +on defense type combinations.  However, it is possible to make every
  1.1052 +tool attack-oriented via a simple macro.
  1.1053 +
  1.1054 +#+srcname: attack-oriented
  1.1055 +#+begin_src clojure :results silent
  1.1056 +(in-ns 'pokemon.lpsolve)
  1.1057 +
  1.1058 +(defmacro attack-mode [& forms]
  1.1059 +  `(let [attack-strengths# pokemon.types/attack-strengths
  1.1060 +	 defense-strengths# pokemon.types/defense-strengths]
  1.1061 +     (binding [pokemon.types/attack-strengths
  1.1062 +	       defense-strengths#
  1.1063 +	       pokemon.types/defense-strengths
  1.1064 +	       attack-strengths#]
  1.1065 +       ~@forms)))
  1.1066 +#+end_src
  1.1067 +
  1.1068 +Now all the tools from =pokemon.types= will work for attack
  1.1069 +combinations.
  1.1070 +
  1.1071 +#+begin_src clojure :results output :exports both
  1.1072 +(clojure.pprint/pprint
  1.1073 + (pokemon.types/susceptibility [:water]))
  1.1074 +#+end_src
  1.1075 +
  1.1076 +#+results:
  1.1077 +#+begin_example
  1.1078 +{:water 1/2,
  1.1079 + :psychic 1,
  1.1080 + :dragon 1,
  1.1081 + :fire 1/2,
  1.1082 + :ice 1/2,
  1.1083 + :grass 2,
  1.1084 + :ghost 1,
  1.1085 + :poison 1,
  1.1086 + :flying 1,
  1.1087 + :normal 1,
  1.1088 + :rock 1,
  1.1089 + :electric 2,
  1.1090 + :ground 1,
  1.1091 + :fighting 1,
  1.1092 + :dark 1,
  1.1093 + :steel 1/2,
  1.1094 + :bug 1}
  1.1095 +#+end_example
  1.1096 +
  1.1097 +
  1.1098 +#+begin_src clojure :results output :exports both
  1.1099 +(clojure.pprint/pprint
  1.1100 + (pokemon.lpsolve/attack-mode 
  1.1101 +  (pokemon.types/susceptibility [:water])))
  1.1102 +#+end_src
  1.1103 +
  1.1104 +#+results:
  1.1105 +#+begin_example
  1.1106 +{:water 1/2,
  1.1107 + :psychic 1,
  1.1108 + :dragon 1/2,
  1.1109 + :fire 2,
  1.1110 + :ice 1,
  1.1111 + :grass 1/2,
  1.1112 + :ghost 1,
  1.1113 + :poison 1,
  1.1114 + :flying 1,
  1.1115 + :normal 1,
  1.1116 + :rock 2,
  1.1117 + :electric 1,
  1.1118 + :ground 2,
  1.1119 + :fighting 1,
  1.1120 + :dark 1,
  1.1121 + :steel 1,
  1.1122 + :bug 1}
  1.1123 +#+end_example
  1.1124 +
  1.1125 +Now =pokemon.types/susceptibility= reports the /attack-type/
  1.1126 +combination's effectiveness against other types.
  1.1127 +
  1.1128 +The 20 type combo achieves its goal in a very clever way.
  1.1129 +
  1.1130 +First, it weakens its effectiveness to other types at the expense of
  1.1131 +making it very strong against flying.
  1.1132 +
  1.1133 +#+begin_src clojure :results output :exports both
  1.1134 +(clojure.pprint/pprint
  1.1135 + (pokemon.lpsolve/attack-mode
  1.1136 +  (pokemon.types/susceptibility
  1.1137 +   [:normal :normal :normal :normal
  1.1138 +    :ice :ice :ice :ice
  1.1139 +    :electric :electric :electric
  1.1140 +    :rock :rock])))
  1.1141 +#+end_src
  1.1142 +
  1.1143 +#+results:
  1.1144 +#+begin_example
  1.1145 +{:water 1/2,
  1.1146 + :psychic 1,
  1.1147 + :dragon 2,
  1.1148 + :fire 1/4,
  1.1149 + :ice 1/4,
  1.1150 + :grass 2,
  1.1151 + :ghost 0,
  1.1152 + :poison 1,
  1.1153 + :flying 512,
  1.1154 + :normal 1,
  1.1155 + :rock 1/16,
  1.1156 + :electric 1/8,
  1.1157 + :ground 0,
  1.1158 + :fighting 1/4,
  1.1159 + :dark 1,
  1.1160 + :steel 1/1024,
  1.1161 + :bug 4}
  1.1162 +#+end_example
  1.1163 +
  1.1164 +Then, it removes it's strengths against Flying, Normal, and Fighting
  1.1165 +by adding Ghost and Ground.
  1.1166 +
  1.1167 +#+begin_src clojure :results output :exports both
  1.1168 +(clojure.pprint/pprint
  1.1169 + (pokemon.lpsolve/attack-mode
  1.1170 +  (pokemon.types/susceptibility
  1.1171 +   [:normal :normal :normal :normal
  1.1172 +    :ice :ice :ice :ice
  1.1173 +    :electric :electric :electric
  1.1174 +    :rock :rock
  1.1175 +    ;; Spot resistances
  1.1176 +    :ghost :ground])))
  1.1177 +#+end_src
  1.1178 +
  1.1179 +#+results:
  1.1180 +#+begin_example
  1.1181 +{:water 1/2,
  1.1182 + :psychic 2,
  1.1183 + :dragon 2,
  1.1184 + :fire 1/2,
  1.1185 + :ice 1/4,
  1.1186 + :grass 1,
  1.1187 + :ghost 0,
  1.1188 + :poison 2,
  1.1189 + :flying 0,
  1.1190 + :normal 0,
  1.1191 + :rock 1/8,
  1.1192 + :electric 1/4,
  1.1193 + :ground 0,
  1.1194 + :fighting 1/4,
  1.1195 + :dark 1/2,
  1.1196 + :steel 1/1024,
  1.1197 + :bug 2}
  1.1198 +#+end_example
  1.1199 +
  1.1200 +Adding the pair Psychic and Fighting takes care of its strength
  1.1201 +against Psychic and makes it ineffective against Dark, which is immune
  1.1202 +to Psychic.
  1.1203 +
  1.1204 +Adding the pair Grass and Poison makes takes care of its strength
  1.1205 +against poison and makes it ineffective against Steel, which is immune
  1.1206 +to poison.
  1.1207 +
  1.1208 +#+begin_src clojure :results output :exports both
  1.1209 +(clojure.pprint/pprint
  1.1210 + (pokemon.lpsolve/attack-mode
  1.1211 +  (pokemon.types/susceptibility
  1.1212 +   [;; setup
  1.1213 +    :normal :normal :normal :normal
  1.1214 +    :ice :ice :ice :ice
  1.1215 +    :electric :electric :electric
  1.1216 +    :rock :rock
  1.1217 +    ;; Spot resistances
  1.1218 +    :ghost :ground
  1.1219 +    ;; Pair resistances
  1.1220 +    :psychic :fighting
  1.1221 +    :grass :poison])))
  1.1222 +#+end_src
  1.1223 +
  1.1224 +#+results:
  1.1225 +#+begin_example
  1.1226 +{:water 1,
  1.1227 + :psychic 1/2,
  1.1228 + :dragon 1,
  1.1229 + :fire 1/4,
  1.1230 + :ice 1/2,
  1.1231 + :grass 1,
  1.1232 + :ghost 0,
  1.1233 + :poison 1/2,
  1.1234 + :flying 0,
  1.1235 + :normal 0,
  1.1236 + :rock 1/4,
  1.1237 + :electric 1/4,
  1.1238 + :ground 0,
  1.1239 + :fighting 1/2,
  1.1240 + :dark 0,
  1.1241 + :steel 0,
  1.1242 + :bug 1/2}
  1.1243 +#+end_example
  1.1244 +
  1.1245 +Can you see the final step?
  1.1246 +
  1.1247 +It's adding the Water type, which is weak against Water and Dragon and
  1.1248 +strong against Rock and Fire.
  1.1249 +
  1.1250 +#+begin_src clojure :results output :exports both
  1.1251 +(clojure.pprint/pprint
  1.1252 + (pokemon.lpsolve/attack-mode
  1.1253 +  (pokemon.types/susceptibility
  1.1254 +   [;; setup
  1.1255 +    :normal :normal :normal :normal
  1.1256 +    :ice :ice :ice :ice
  1.1257 +    :electric :electric :electric
  1.1258 +    :rock :rock
  1.1259 +    ;; Spot resistances
  1.1260 +    :ghost :ground
  1.1261 +    ;; Pair resistances
  1.1262 +    :psychic :fighting
  1.1263 +    :grass :poison
  1.1264 +    ;; completion
  1.1265 +    :water])))
  1.1266 +#+end_src
  1.1267 +
  1.1268 +#+results:
  1.1269 +#+begin_example
  1.1270 +{:water 1/2,
  1.1271 + :psychic 1/2,
  1.1272 + :dragon 1/2,
  1.1273 + :fire 1/2,
  1.1274 + :ice 1/2,
  1.1275 + :grass 1/2,
  1.1276 + :ghost 0,
  1.1277 + :poison 1/2,
  1.1278 + :flying 0,
  1.1279 + :normal 0,
  1.1280 + :rock 1/2,
  1.1281 + :electric 1/4,
  1.1282 + :ground 0,
  1.1283 + :fighting 1/2,
  1.1284 + :dark 0,
  1.1285 + :steel 0,
  1.1286 + :bug 1/2}
  1.1287 +#+end_example
  1.1288 +
  1.1289 +Which makes a particularly beautiful combination which is ineffective
  1.1290 +against all defending types.
  1.1291 +
  1.1292 +
  1.1293 +# #+begin_src clojure :results scalar :exports both
  1.1294 +# (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])))))
  1.1295 +# #+end_src
  1.1296 +
  1.1297 +# #+results:
  1.1298 +# | [: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] |
  1.1299 +
  1.1300 +
  1.1301 +Is there anything else that's interesting?
  1.1302 +
  1.1303 +#+begin_src clojure :exports both
  1.1304 +(pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type))
  1.1305 +#+end_src
  1.1306 +
  1.1307 +#+results:
  1.1308 +: INFEASIBLE
  1.1309 +
  1.1310 +#+begin_src clojure :exports both
  1.1311 +(pokemon.types/old-school
  1.1312 + (pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type)))
  1.1313 +#+end_src
  1.1314 +
  1.1315 +#+results:
  1.1316 +: INFEASIBLE
  1.1317 +
  1.1318 +#+begin_src clojure :exports both
  1.1319 +(pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type))
  1.1320 +#+end_src
  1.1321 +
  1.1322 +#+results:
  1.1323 +: INFEASIBLE
  1.1324 +
  1.1325 +#+begin_src clojure :exports both
  1.1326 +(pokemon.types/old-school
  1.1327 + (pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type)))
  1.1328 +#+end_src
  1.1329 +
  1.1330 +#+results:
  1.1331 +: INFEASIBLE
  1.1332 +
  1.1333 +#+begin_src clojure :exports both
  1.1334 +(pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type))
  1.1335 +#+end_src
  1.1336 +
  1.1337 +#+results:
  1.1338 +: INFEASIBLE
  1.1339 +
  1.1340 +#+begin_src clojure :exports both
  1.1341 +(pokemon.types/old-school
  1.1342 + (pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type)))
  1.1343 +#+end_src
  1.1344 +
  1.1345 +#+results:
  1.1346 +: INFEASIBLE
  1.1347 +
  1.1348 +There is no way to produce a defense-type that is weak to all types.
  1.1349 +This is probably because there are many types that are completely
  1.1350 +immune to some types, such as Flying, which is immune to Ground. A
  1.1351 +perfectly weak type could not use any of these types.
  1.1352 +
  1.1353 +* Summary
  1.1354 +
  1.1355 +Overall, the pok\eacute{}mon type system is slanted more towards defense
  1.1356 +rather than offense.  While it is possible to create superior
  1.1357 +defensive types and exceptionally weak attack types, it is not possible to
  1.1358 +create exceptionally weak defensive types or very powerful attack
  1.1359 +types.
  1.1360 +
  1.1361 +Using the =lp_solve= library was more complicated than the best-first
  1.1362 +search, but yielded results quickly and efficiently. Expressing the
  1.1363 +problem in a linear form does have its drawbacks, however --- it's
  1.1364 +hard to ask questions such as "what is the best 3-type defensive combo
  1.1365 +in terms of susceptibility?", since susceptibility is not a linear
  1.1366 +function of a combo's types. It is also hard to get all the solutions
  1.1367 +to a particular problem, such as all the pokemon type combinations of
  1.1368 +length 8 which are immortal defense types.
  1.1369 +
  1.1370 +
  1.1371 +* COMMENT main-program
  1.1372 +#+begin_src clojure :tangle ../src/pokemon/lpsolve.clj :noweb yes :exports none
  1.1373 +<<intro>>
  1.1374 +<<body>>
  1.1375 +<<declares>>
  1.1376 +<<memory-management>>
  1.1377 +<<get-results>>
  1.1378 +<<solve>>
  1.1379 +<<farmer-example>>
  1.1380 +<<lp-solve>>
  1.1381 +<<better-farmer>>
  1.1382 +<<pokemon-lp>>
  1.1383 +<<results>>
  1.1384 +<<attack-oriented>>
  1.1385 +#+end_src
  1.1386 +
  1.1387 +
  1.1388 +* COMMENT Stuff to do.
  1.1389 +** TODO fix namespaces to not use rlm.light-base
  1.1390 +