Instead of using the Pomodoro method, I’ve been relying increasingly on my Clash of Clan method while working. Every 20 minute or so, I would check my phone in order to attack as my troops have been replenished.
Clash of Clans: Barracks Optimization
Hopefully this’ll be the first of a many part series to examine CoC in a more mathematical manner, and actually use some of the skills and technologies I have acquired over the years.
The first thing that raiders in CoC know is that time spent not raiding is wasted time. In order to minimize that wasted time, a critical thing to minimize is time spent building troops, spells and resting heroes. Spells and heroes has no build order to minimize, while troops has countless possibilities of building a set army.
The problem is fairly easy to define: given a certain army composition, use the given set of barracks and create that army in the shortest possible time.
Sounds easy right? Meh.
Scheduling Theory
My first impression is to use scheduling theory, and turn it into a simple library call to an approximation algorithm there. Unfortunately, there are several complications.
First of all, since there are multiple barracks, this is a multiple processor problem. Multiple processor problem are actually NP-hard, equivalent to the partitioning problem. Many heuristics exist for a standard problem of many processor, and many jobs for minimizing time. The standard is longest processing time first (LPT).
If one simply implements LPT on this problem, we have a weird problem. The heuristic was designed for processors of equal power, and barracks of different levels have different capacity. The second (more minor problem) is that we need to impose the constraint that a barrack can produce that particular troop (i.e. level 1 creating a P.E.K.K.A).
So in essence, this problem became much tougher using this approach. I guess I can read up on heterogenous processor research, but that’s for another day.
Integer programming
The next approach was to convert it to an integer programming problem.
Let us define our problem then. Let 
![](https://s0.wp.com/latex.php?latex=AC
<p>The unfortunate thing about this whole section is that there is no known general way to solve integer programing problems in polynomial time; it is also NP-hard. Many heuristics are available, and many sub-cases solved, but I’m not at that level yet. One technique which I suspect might do well is to simply relax the problem to a linear programming problem, and then round the result. Thing is, this LP relaxation method kind of sucks most of the time.</p>
<h5>Conclusion</h5>
<p>So do I have a final product? Nope.</p>
<p>Scheduling theory proves to have little Python implementations, while integer programming is only available from obscure libraries. The best thing to do might be to create my own little meta-heuristic.</p>
</div><!-- .entry-content -->
</article><!-- #post-714 -->
</main><!-- #main -->
</div><!-- #primary -->
<aside id="secondary" class="widget-area" aria-label="Blog Sidebar">
<section id="text-3" class="widget widget_text"><h2 class="widget-title">Currently “_______”</h2> <div class="textwidget"><p>Reading: New Yorker magazines…</p>
<p>Watching: Maniac</p>
<p>Playing: LoL</p>
</div>
</section>
<section id="recent-posts-2" class="widget widget_recent_entries">
<h2 class="widget-title">Recent Posts</h2><nav aria-label="Recent Posts">
<ul>
<li>
<a href="https://marshalljiang.com/tale-of-a-golden-corral/">Tale of a Golden Corral</a>
</li>
<li>
<a href="https://marshalljiang.com/my-not-so-successful-quest-to-conquer-the-nyt-connections-game-with-word2vec/">My (Not-So-Successful) Quest to Conquer the NYT Connections Game with Word2Vec</a>
</li>
<li>
<a href="https://marshalljiang.com/tapping-out/">Tapping Out</a>
</li>
<li>
<a href="https://marshalljiang.com/1928-2/">(no title)</a>
</li>
<li>
<a href="https://marshalljiang.com/a-terrible-philosophy/">A Terrible Philosophy</a>
</li>
</ul>
</nav></section><section id="search-2" class="widget widget_search">
<form role="search" method="get" class="search-form" action="https://marshalljiang.com/">
<label for="search-form-1">
<span class="screen-reader-text">Search for:</span>
</label>
<input type="search" id="search-form-1" class="search-field" placeholder="Search …" value="" name="s" />
<button type="submit" class="search-submit"><svg class="icon icon-search" aria-hidden="true" role="img"> <use href="#icon-search" xlink:href="#icon-search"></use> </svg><span class="screen-reader-text">Search</span></button>
</form>
</section><section id="archives-2" class="widget widget_archive"><h2 class="widget-title">Archives</h2> <label class="screen-reader-text" for="archives-dropdown-2">Archives</label>
<select id="archives-dropdown-2" name="archive-dropdown">
<option value="">Select Month</option>
<option value=)