Monday, May 5, 2014

12 days, Strata, and a fallen Marine

This is a post I wrote while on a plane in February. I'm just now getting around to posting it.

--

I spent last week at the Strata conference. It was a good time, saw some friends and soaked in some good presentations and discussions. James Burke gave a clever keynote on the last day. It was my favorite, here's a quote: "I'm an optimist, because to be a pessimist means to withdraw and not be involved. I like to be involved." I can relate to that, pessimism reeks of hopelessness and inaction. One of my previous Marine Corps commanders called me "disgustingly optimistic". 

Meanwhile, back in Virginia my very pregnant wife and her mother were digging out from under a foot of fresh snow. Despite that, I was optimistic about making it home on time and headed off to the airport early the next morning. At the airport the ticket attendant greeted me with a smile (she must be an optimist too ...or diligent service professional). The smile faded from her face when she looked down at her console. I knew before the words left her mouth that I wouldn't be getting home this day. Although every runway in the country was functional, the cancelled flights had a cascading effect and had knocked one of my connecting flights from the schedule. I cursed bad computer algorithms. For an hour I stared at the attendant while she made phone calls and typed on her computer, attempting to meddle with other people's schedules. She was able to determine that my choices were to spend another night in silicon valley or get to Denver and try my luck there. My disappointment in algorithms dissipated as I realized even the best flight scheduling system would fail with this amount of random intervention from empowered ticket attendants modifying it's solutions.

Denver is the home town of a fallen Marine I served with in Iraq. Walking through the airport, on the way to my flight, I was undecided if I should attempt to check in on his parents during my time in town. I wasn't sure how long I'd be there and it had been 5 years since I had visited them last. As though speaking directly to me the paging speakers in the airport kicked up and announced the name "Vandegrift". Apparently someone with this last name had missed a flight. They probably didn't hear the message. But I heard it; Matt Vandegrift was the fallen Marine I was thinking of and I was just knocked out of my fog of indecision. I was going to see the Vandegrifts. I sent his father an email from my smart phone in the jetway as I boarded my flight.

On the flight I popped open my trusty Dell XPS12. I had an interesting parsing problem on my work to-do list and some sample data to work with. After getting stuck and unable to access the Internet I ended up going through some of my old code looking for solutions I'd written previously. Unsuccessful, I started playing with one of my favorite pieces of code. twelve.c is 15 lines of c code that outputs all 64 lines of the 12 days of Christmas. I didn't write it, but I enjoy it; it's an old ioccc entry. I love pointing to this competition when people talk about static code analysis in the context of malicious developers. Good luck with that.

 #include <stdio.h>
 main(t,_,a) char *a; { return!0<t?t<3?main(-79,-13,a+main(-87,1-_,main(-86,0,a+1)+a)):
 1,t<_?main(t+1,_,a):3,main(-94,-27+t,a)&&t==2?_<13?
 main(2,_+1,"%s %d %d\n"):9:16:t<0?t<-72?main(_,t,
"@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l+,/n{n+,/+#n+,/#\
;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \
q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;#\
){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \
iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \
;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# \
}'+}##(!!/")
:t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
:0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a,
"!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a+1);
}



The 12 days of Christmas is pretty repetitive prose (see what i did there?). Repetitive text lends itself well to compression tricks. The 64 lines of the song are generated by the above 15 lines of code, about 75% compression, I should easily be able to write something that could beat that if I were just going for compression and not obfuscation. Doing it without the aid of the Internet made it fun enough of a game to burn some time. Here's what I came up with.

#!/bin/bash
b64="H4sICPFD/lIAA291dHB1dC50eHQA5ZXdcYQwDITfqWILuKSBPKaAq0HBAm\
viH8YyR+g+MtfAOZNkLpcXQGbX+lbAcE6onjFJ0QpHO/KEV19EayRF3FHLygj5w\
pjJDjUj8kBYqNQibmZIgpVMxaTMz8Nwvm6pPObkbt+zbhl1LTUwnN3Sgcx9S6Pq\
pfT08ebGVDiNHp6TnvDl1lM2l7+9d9NjpBAkzXgz7Nb8O3lk6sKRVufgUAxIX36\
cT+Wjh8/kmJmVQU+BdoM64feZ+cKpi7oZoBslNW7dJMZGfh9pWOaeLCb3FZHEtS\
xRwvuBfdcRk3Q9LpPbIjlhNVMaD+i/mLv2vaYmt7VyBAy8HDkeZhYcer/aqwOLL\
Fy0nQ7whx5S3Th0/S+awQpX1hjblI6La/x/NL1PBJqPqzMJAAA="
echo -n $b64 | base64 -d | gunzip | cat


The original code has 840 characters in it, my in-flight solution has 495.
The version of 12 days of Christmas that they both print out has 2355 characters. It would have been nice to fit the whole thing into some code I could tweet, 140 characters. Not possible with direct methods, but that would have been interesting. There are a few minor optimizations I could have done, but nothing dramatic. This is probably close to as tight as it gets. If this is interesting to you, check out this great Dr Dobbs article about a long standing challenge to compress the random numbers generated by Rand in the 1940s.

To find out just how much of the text I could theoretically tweet, I wrote a small program to chart how many characters my approach uses for the first n lines of the text. The program just grabbed the first N lines and then implemented the method and output how many characters it ended up being. The red line shows how the 64 lines of the song eventually add up to the whole 2355 characters. The blue line is my algorithm.



The lines cross down in the left corner of that chart. That's where the benefit from compression overcomes the overhead of the surrounding code. Here's a close up of that crossover.

Unfortunately the crossover takes place when we're already past 140 characters. Meaning that any code you could tweet with this algorithm would be longer than just tweeting the plain text. Not cool. I was bummed when I saw this. It seemed like such a clever idea a few moments ago. Before I was able to come up with a different approach, the attendant told me I had to power down my laptop.

When I powered on my phone a message was waiting from the Vandegrifts. They'd love to see me and that I should let them know when to pick me up from the Airport. The ticket counter informed me that I wouldn't be flying out until the next day so I ended up spending the night and eating dinner with the Vandegrifts and talking about their son. We also spoke about survivor guilt. Matt's father gave me a copy of Viktor Frankl's book "Man's Search For Meaning". I read it on my flight from Denver to DC. It chronicled Viktor himself and his survival through a series of Nazi death camps.

Viktor writes that the "best of us" died in the concentration camps. Those not immediately killed by chance sacrificed themselves by standing up to the guards or "Capos" (privileged inmates). The worst kind of prisoners prospered and survived. That stuck out in my mind, because it truly shows some of the weight that those that survived made. They were often plagued by the gnawing suspicion that they may have survived because they were willing to compromise their ethics; even if it's not true. Life in a Nazi death camp was different than imprisonment by the Japanese like Zamperini endured as chronicled in the recent book Unboken. I finished Unbroken a few weeks after it was released and highly recommend it. Both stories, Unbroken and Man's Search for Meaning are very moving tales.

In Unbroken, Zamperini discusses his life after freedom. It's best summarized in his letter to his most cruel tormentor while in prison camp. Here's a video of Zamprini reading it. And the text:

"To Mutsuhiro Watanabe,

As a result of my prisoner war experience under your unwarranted and unreasonable punishment, my post-war life became a nightmare. It was not so much due to the pain and suffering as it was the tension of stress and humiliation that caused me to hate with a vengeance.

Under your discipline, my rights, not only as a prisoner of war but also as a human being, were stripped from me. It was a struggle to maintain enough dignity and hope to live until the war's end.

The post-war nightmares caused my life to crumble, but thanks to a confrontation with God through the evangelist Billy Graham, I committed my life to Christ. Love has replaced the hate I had for you. Christ said, "Forgive your enemies and pray for them."

As you probably know, I returned to Japan in 1952 and was graciously allowed to address all the Japanese war criminals at Sugamo Prison… I asked then about you, and was told that you probably had committed Hara Kiri, which I was sad to hear. At that moment, like the others, I also forgave you and now would hope that you would also become a Christian.

Louis Zamperini"

Viktor takes on a similar sentiment. He wrote in "Man's Search for Meaning" that "first time in my life I saw the truth as it is set into song by so many poets, proclaimed as the final wisdom by so many thinkers. The truth – that love is the ultimate and the highest goal to which man can aspire. Then I grasped the meaning of the greatest secret that human poetry and human thought and belief have to impart: The salvation of man is through love and in love. I understood how a man who has nothing left in this world still may know bliss"

Those that have ever been present for the death of another, especially from trauma, are destined to relive the events. To wonder "what if" a million times over. What if we wrapped the bandages a different way. What if we missed something that could have cued us to what was about to happen. What if we took a different road. What if.

I don't have a good answer for any of the questions or the weight that comes after. But I do believe both Zamperini and Viktor's messages. Regardless of what you do, where you've been, what somebody else has done to you, or what you've done; the true measure of worth and what you accomplish is ultimately measured by how you treat and your attitude toward others. That's the most important thing you can work on and that's something you can do right now. Don't live in the past, and don't live in the future. You're called to action right now.

February passed, as did April 21st (the anniversary of Matt's death) before I got around to posting this. There are probably only a handful of people that can appreciate a data compression discussion and non-technical book reviews in the same article. But, hey, this is my blog and I can post things in whatever combination I feel like, this isn't a popularity contest. Stranger things have happened on the Internet. If 5 other people can appreciate this, then that's great. Pretty soon I'll get around to posting something else about welding and really narrow down to my key demography which is apparently... well I have no idea.  

Here are some articles about Matt.
http://www.vandegriftvoice.com/news/2012/04/30/valor-day-honors-school-namesake/
 http://projects.militarytimes.com/valor/marine-1st-lt-matthew-r-vandegrift/3495867
http://www.hillcountrynews.com/news/four_points/article_bea6ffac-cbe1-11df-91bc-001cc4c002e0.html
The first video posted to my youtube channel was a compilation of pictures and videos created by a Marine Gunnery Sergeant that I worked with. You'll see pictures of Matt and the rest of the team that I spent a year in Iraq with. Link here: https://www.youtube.com/watch?v=QArViiaU-U4&list=UUAFjD9wAsGMjhf_aHV36O9A