Sunday, November 25, 2012

I decided recently to start to tackle Gary Grigsby’s War in the East. So after playing the short tutorial I moved on to the first of a series of scenarios titled “The Road to …”. This first one is very short, requiring you to achieve your objectives in 3 turns.

Below is a map of the situation at the beginning of the game.

The objectives are to capture Minsk, and a set of points along the eastern border of the map. It doesn’t really leave you time to try and encircle the bulge of Soviet forces in the center of the line. Below I have included a map showing where the objectives are located (Red are Soviet, Blue are German).

My plan was for two main thrusts. One from the south, attacking through Brest-Litvosk, then skirting along the northern edge of the Pripyat marshes and heading for the Berezina river. In the north, there would be an attack along the Kaunas – Vilnuis axis, then a move towards Minsk with a secondary force heading for Vitebsk. Other forces, consisting mainly of slower infantry units, would try to pocket and shatter as many troops in the Soviet bulge on the main line as possible.

In the end I achieved a victory. I’m not sure I utilized my air power as well as I could have. My armor units did a great job keeping to the timetable needed to accomplish the scenario objectives, and I was able to keep them supported as they made their way to the eastern border and their objectives.

I didn’t move some of the units involved in shattering the bulge, or some units that were to push on to Minsk in the last turn since Minsk was already captured, and the scenario was ending.

Overall a fun game. They really have seemed to make it easy to play. I know there is a lot of stuff still to learn about air power, and force structure management, but they have made moving and attacking really easy to do in this game, and it was relatively quick to play through the scenario.

Monday, November 12, 2012

Gaming Update for the Fall

The fall has brought a lot of fun new games out. I haven't had much time to play, but here are some games I have spent time with recently:

• Crusader Kings II - I picked this up in a Steam sale. It is a fairly complex game simulating dynastic geopolitics of the middle ages. In my initial attempt while reading through an LP on somethingawful I quickly found myself in trouble. A region in my command soon revolted, and I had gone on the warpath against a neighbor that I didn't have the ability to defeat. You have to handle things with your family, managing the marriage of people, placing them into posts, dealing with threats from family members, and threats from outside your realm. Despite my disastrous initial attempt, this looks like it will be a game that will be entertaining for a long time.
• XCOM: Enemy Unknown - Firaxis did a superb job in their remake of this classic game. It is fun and the missions are short enough that you can pop in and do a quick one if you don't have a lot of time. My initial game is probably up in the air at this point, as I didn't get a good grasp on the strategic part of the game soon enough, but it is still fun to see how far I can go, and then I will try again. My team has suffered pretty high attrition the past couple of months, with a lot of veterans being lost. We have started to get some tech improvements though which should help, but we are also facing much tougher opposition now.
• Torchlight 2 - I have had some fun playing Torchlight 2 as well. It is a very nice ARPG, and runic has done a fine job with their sequel to their initial game. I have seen comments elsewhere that this is the true sequel to Diablo. I have never played the earlier Diablo games so I have no authority to comment on the veracity of that statement.
• The Operational Art of War - I have been spending time with Norm Koger's classic wargame lately as I have been in my military history mood. This is the Matrix edition that came out in 2006.
• Squad Battles: Falklands - A John Tiller title covering small unit actions in the Falklands campaign.

I've been doing a lot of reading lately, so here is an update of the books I have finished in the past couple of months.

• Tank Farm Dynamo - A sf short story by David Brin.
• Mind of War - A biography of John Boyd. This was a great book that covered a lot of what Col. Boyd had accomplished in his life, from setting up the AF fighter tactics school, designing the F-15 and F-16, and being a proponent of maneuver warfare and the OODA cycle.
• Cybermancy - Book #2 in Kelly McCullough's Webmage series.
• The Bitter Woods - John Eisenhower's wonderful operational history of the Ardennes campaign.
• Sherman Invades Georgia - Part history of Sherman's Atlanta campaign, and part workbook on the modern military decision making process and its use in the study of historical campaigns.
• Vortex - Larry Bond book about an attempt to turn back the clock as apartheid appears to be ending in South Africa. Larry Bond was a big part of Tom Clancy's early success and after the collaboration on Red Storm Rising he started to work on his own books.
• Red Phoenix - Another Larry Bond book, this one focusing on a 2nd war in Korea late in the Cold War.
• A Mathematician's Apology
• Guide to the Literature of Mathematics and Physics - a book I read about on the physicsforums site. The beginning of it talks about how to go about reading these books and self study, and then the bulk of it details good books on a variety of subjects as of the year 1958.
• Prime Obsession - John Derbyshire's book on the history of the Riemann Hypothesis.

I'm also at various stages of reading the following books:

• The Art of Wargaming - Peter Perla's book on the history of wargaming.
• Forward into Battle - Paddy Griffith's book on the evolution of battle from Napoleonic times to the 80s.
• The Generals - Tom Ricks' book on American Generalship from WWII to present day, and how changes over time in the policy of removing officers has impacted the military.
• The Signal and The Noise - Nate Silver's book pop sci book on statistical analysis.

Sunday, September 16, 2012

I have been doing a horrible job updating this blog. So here are some updates:

1. New job -- After 12 years I left my job in the UNIX sustaining group at Stratus and went to work for Oracle in their Linux Kernel and Virtualization group, working on the Unbreakable Enterprise Kernel team. I am working remotely from home which gives me the ability to see my daughter more than before. I have been working the new job for a month now. So far it seems to be going well.

2. Books that I have read recently -- Here are some books that I have read this year:

The World of Null-A by A.E. Van Vogt - old sf book that was entertaining to read.
Hackers & Painters by Paul Graham - Great collection of essays.
Black Swan by Bruce Sterling - okay sf short story
A Genius for War by Dupuy - Good book discussing the history of the German General Staff.
How to be a Programmer by Robert Read - pdf from online that was an okay read
The Google Resume by Gayle McDowell - Decent book on today's tech job market
Redshirts by John Scalzi - very entertaining sf book
The Cuckoo's Egg by Cliff Stoll - Always a great read
Makers by Cory Doctorow - ok book extrapolating the rise of the diy/maker culture
Why Good People Can't Get Jobs by Peter Cappelli - An interesting take on the jobs situation
Old Man's War by Scalzi - Another good sf book
WebMage by Kelly McCullough - A decent fantasy book that mixes cyber and magic
Team Geek by Ben Collins-Sussman and Brian Fitzpatrick - A great book about tech teams and being a team member
Griftopia by Matt Taibbi - Probably the best explanation of the causes of the financial crisis that there is

3. Games I have been playing -- I haven't spent much time on games this year, but here are some I have been playing lately:

FTL - A roguelike where you control a spaceship and crew. Very quick and entertaining.
Guild Wars 2 - Probably the 1st MMO that has really caught me outside of WoW.
Diablo 3 - Good mindless fun.

4. Games I am looking forward to in the future -- Here are some games coming out in the future that I am looking forward to:

X-Com: Enemy Unknown -- Finally it looks like someone is doing a good follow up to X-com.
Torchlight II - Should be an entertaining arpg.
Borderlands 2 - The first game was fun and had a lot of style, so hopefully they will hit all the right notes again with the sequel.
Planetary Annihilation - Just finished a kickstarter. Total Annihilation type rts on a galactic scale.
Wasteland 2 - Another kickstarter project, making a sequel to on of the great games of the 80s.
Clang - A kickstarter project by Neal Stephenson that is trying to make a sword fighting game.
Grim Dawn - A kickstarter project making an ARPG from the same guys that made Titan Quest.

Wednesday, April 4, 2012

So I grabbed a file with the 1st billion digits of pi to play with that as well. Using standard c types I ran into overflow issues when I got to around the 48 millionth digit. Luckily there is the GNU MP library. So converting things to using the mpz_t type I was able to scan the billion digits and get an answer. The call overhead for using mpz_t and its related functions only added 2 seconds of runtime.

The answer for 1000000000 digits is:

snits@cantor:~/proj/c/pi=>time ./nseqpi pi-1000000000.txt
sequence 1, 2, 3: 1000000000 166644616079693012548675 1323986657

real 0m18.796s
user 0m18.191s
sys 0m0.186s

Tuesday, April 3, 2012

An Improvement on Counting Subsequences in Pi

So I was thinking about this problem some more this evening while watching Dora the Explorer with my daughter, and I realized that I could use the same technique I was using to add up occurrences of the subsequence to track occurrences of the earlier portion of the subsequence and I would require only 3 counters and it would run in linear time. This solution should also work for subsequences of other lengths and remain O(n) bound.

Here is the solution:

1. While ! EOF, scan a digit
2. If it is the first digit in the subsequence, increment a counter.
3. If it is the second digit in the subsequence, increment second counter by current value of counter tracked in 2
4. If it is the third digit in the subsequence, increment occurrences counter by the current value of the counter tracked in 3.
5. goto 1

Here is the output from the old version:

sequence 1, 2, 3: 1000000 167568126814676 10031551523

real 0m41.618s
user 0m41.436s
sys 0m0.004s

Here is the output from the new version:

sequence 1, 2, 3: 1000000 167568126814676 1300014

real 0m0.019s
user 0m0.018s
sys 0m0.001s

As stated in the previous post on this, the first number is the number of digits scanned, the 2nd is the number of occurrences of the subsequence, and the 3rd is the number of logical operations.

Saturday, March 10, 2012

Counting subsequences in a stream of digits

While reading some posts on comp.lang.lisp the other day I came across an interesting problem that I have been trying to solve:

> Write a program that counts the number of times the subsequence "1, 2, 3"
> appears in the first 100,000 digits of pi. Note "subsequence" does not imply
> consecutive digits. For example, "1, 2, 3" appears in "3.141592653" twice.
> You may use Google or the link above to find the digits of pi. Please include
> the correct count when submitting your application.

We had a candidate submit a solution in Python which ran in O(n) time.
The algorithm was essentially correct, but unfortunately, he used a
numpy.array to hold some counters, and suffered integer overflow. Had
he used regular python lists, he would have been fine.

It is an interesting problem, but the most intriguing part is the assertion that the candidate turned in a algorithm which ran in O(n) time. That means the run time scales linearly at worst with the number of inputs. I guess maybe I need to go back and revisit some algorithm texts, dust the rust off my understanding of asymptotic notation, and brush up on my algorithms. The solution I have come up with so far is O(n^2) with a constant multiple (~ 1/100) that has it between O(n^2) and O(n log n) if I plot things out with gnuplot.

My solution is a pretty simple one. First I do one pass and determine the number of 1s (or whatever the first digit is that I tell it) so I can allocate storage for counters. I could skip this and just use a linked list, but this is linear time and not a big deal. Then I walk the digits again. When I scan a 1, I increment a counter, when I scan a 2 I walk a list of counters the size of the counter tracking ones incrementing each counter, and when I scan a 3 I walk the list same list of counters and add their values to the variable tracking the number of instances of the subsequence. It runs pretty quickly, going through 1000000 digits in about 34 seconds, and 3/10 of a second for the 100000 digits stated in the original problem. Output is given below:

snits@cantor:~/proj/c/pi=>time ./seqpi pi-1000000.txt 100000
sequence 1, 2, 3: 100000 168843528006 102081958

real 0m0.345s
user 0m0.342s
sys 0m0.001s

snits@cantor:~/proj/c/pi=>time ./seqpi pi-1000000.txt
sequence 1, 2, 3: 1000000 167568126814676 10031551523

real 0m33.897s
user 0m33.739s
sys 0m0.004s

The 1st number is the number of digits scanned, the 2nd is the number of occurrences of the subsequence, and the last number was a crude operation counter that counted things like scanning a digit, and incrementing a counter, or updating the tally,

It is very interesting stuff, and one thing that fascinates me about all this is the fact that a typical home computer has the power to these things this quickly. This program and the prime sieve program in earlier posts are single threaded applications so they don't even take advantage of all the cores on the system, but they still do a lot of work very quickly. I remember in the 5th grade, Dr. Van Huesen brought his vic-20 into class and had it run a basic program to count to 1 million I believe. It ran for over a day, sitting there spitting out the numbers on the screen. It is amazing how far technology has progressed in the past 25 years.

Friday, March 9, 2012

Sieve of Eratosthenes revisited

I recently revisited this after it coming up last year when my nephew was playing around with primes. This time I decided to implement a basic bit-array myself in c. Without the overhead of calls to the boost dynamic bitset in c++ the runtime dropped even more.

Back when I had initially run the c++ version this was the output for 40 billion:

snits@perelman:~/proj/cpp=>time ./se 40000000000
1711955433 primes between 2 and 40000000000. Greatest prime is 39999999979

real 90m48.631s
user 90m40.850s
sys 0m3.589s

Here is the output for running the c version with my own bitarray:

On my i7 system:

snits@cantor:~/proj/c=>time ./sieve 40000000000
1711955433 primes between 2 and 40000000000. Greatest prime is 39999999979

real 16m49.468s
user 16m23.482s
sys 0m6.471s

On my q6600 system:

snits@perelman:~/proj/c=>time ./sieve 40000000000
1711955433 primes between 2 and 40000000000. Greatest prime is 39999999979

real 24m57.106s
user 24m47.370s
sys 0m2.562s

That is a nice gain due to removing the overhead of calls to the dynamic bitset class in C++.

Friday, February 17, 2012

Euclid's Algorithm for finding the Greatest Common Denominator

Having some fun with Euclid's gcd algorithm this morning.

clojure: (defn gcd [a b] (if (= (mod a b) 0) b (gcd b (mod a b)))) scheme: (define (gcd a b) (if (= (modulo a b) 0) b (gcd b (modulo a b)))) lisp: (defun gcd (a b) (if (= (mod a b) 0) b (gcd b (mod a b)))) c: int gcd(int a, int b) { if ((a % b) == 0) return b; else return gcd(b, a % b); }