Wednesday, November 4, 2015

A Sudoku Solver and Thoughts on Automating Life

Introduction

While on a recent flight, I turned to the back of the inflight magazine to look for the crossword puzzle.  This was something my wife and I could do to pass the time while we also tried our best to entertain our infant son, who was sitting on our laps.  So we would take turns, one of us holding the magazine and reading the clues with pen in hand, the other, offering suggestions with baby on lap.  We quickly dispatched that and, needing something else to fill up the time, I turned my attention to the other inflight magazine puzzle offerings: Sudoku.
 
I had done my fair share of Sudoku puzzles, but it had been a while since I really attempted to work through a puzzle.  But as there was little else to do that would work as entertainment in the cramped space with a squirmy child, I decided to give it a shot.  I chose the easy puzzle and started to work.  I had an hour to complete my task.
 
I never finished.  Maybe it was the lack of focus to be had under such conditions.  Or maybe I was just out of practice.  Or maybe "easy" was harder than I thought it would be and I simply overestimated my abilities.  Whatever the reason was, the fact remained, and I had to put the unfinished puzzle back into the seat pouch as we arrived at our destination.
 
Frustrated by my inability to complete an "easy" Sudoku puzzle, what did I do?  Did I decide to practice, doing puzzle after puzzle to hone my skills?  Nope.  My goal was to complete Sudoku puzzles, so naturally, I thought of the best way to accomplish this goal: write a program to do it for me.
 

The Program

I chose my favorite language of late, R, to write the program in.  Perhaps not the most elegant language or most efficient for my task, but it would suffice.  The process for solving the puzzle is as follows (feel free to skip if you don't care):
  1. Load the puzzle to be solved into a matrix
  2. Create a work table with a row for each puzzle cell containing:
    • Row number
    • Column number
    • Square number (i.e., which 3x3 square block)
    • Possible values remaining
  3. Apply rules for eliminating values from possible values remaining
    1. If a row already contains a decided value, remove that value from the possible values list for every other cell in that row.
    2. If a column already contains a decided value, remove that value from the possible values list for every other cell in that column.
    3. If a square block already contains a decided value, remove that value from the possible values list for every other cell in that square block.
  4. Repeat step 3 until no more changes are made (i.e., no more possible values are removed).
  5. Check if solved (i.e., only one possible value remains for each cell).
    • If solved, verify results.  If verified, print solved puzzle.
    • If not solved or not verified, proceed to 6.
  6. Choose a remaining possible value for a cell and hold that fixed.  Then repeat steps 3-5. 
    • If no solution is found, hold the next remaining possible value for a cell fixed.  Then repeat steps 3-5. 
    • Do this for all cells until a solution is found and verified.
  7. Print solved puzzle solution.
Instead of taking an hour, it takes less than a second to solve a puzzle.  Hooray?
 

Missing the Point

Creating the program to solve the puzzle was like solving the puzzle itself.  I experienced frustration when my attempts didn't work, excitement when I had a breakthrough or revelation, and satisfaction when I had finally solved the puzzle (i.e., the code worked and solved the puzzles for me).  But I don't experience that same satisfaction now whenever I feed in a new puzzle to solve.  Wouldn't that be nice?  If I could experience each time the satisfaction of solving a puzzle with my code in the same way that I would experience it in solving it on my own?  But I don't.
 
This experience highlights a typical difference in the way people experience life: as a journey vs. a destination.  Is life, and its constituent parts (like solving a Sudoku), to be treated like a destination or a journey?  Whether any part should be treated like a journey or like a destination probably depends on our criteria for success.  At least in the case of solving a Sudoku puzzle, the criteria would seem to be something to do with its ability to produce fun, enjoyment, and satisfaction.
 
In treating the object of a Sudoku puzzle to be merely the destination (i.e., solving it), I missed its primary method of providing satisfaction, which is the experience of solving it, not actually solving it.  Sure, the actual solving is a part of the satisfaction, but it is only a small part of the experience, and hence, a small part of the satisfaction which comes from actually having worked through the solution myself to the final result.  That is, the journey is the most enjoyable part, not the destination alone.
 
I am reminded of the hedonistic paradox: if you aim at happiness as your only goal, you will miss it; if you aim at other things, you will find happiness as well.  In my attempt to automate Sudoku solving, I was aiming for the happiness of solving the puzzle, and I missed it.
 

So What?

This isn't really about Sudoku, but about life in general.  I love automation and greater efficiency, but certainly it seems that some things should not and cannot be automated if we are to benefit from them in desirable ways.  Particularly, if something comes too easily, we do not enjoy it nearly as much as we would have if it had come though challenges and obstacles.  We like working at things to a certain degree.  Projects, games, exercise, and other activities all have to be somewhat difficult, but not too difficult, to be worthwhile and worth doing for our own satisfaction and enjoyment.
 
An article in the Atlantic titled "A World Without Work" highlights the fact that we, to a certain degree, enjoy our work.  And we are more miserable if we aren't working. It seems that the only thing worse than having a job is not having a job.  Ask any retiree who has not transitioned to doing something else after retirement.  We need to have some challenge, some goal, some project in our life if we are to find meaning in it.
 
So what am I saying?  I suppose, automation and efficiency have their place and are important, but they may not be the most important consideration in designing and implementing a solution to a problem.  It just depends on the goal.  Many unpleasant tasks can, should, and will be automated most of the time.  But those tasks we enjoy and find satisfaction in doing ourselves, shouldn't always be.  I bet most things fall somewhere in the middle.  Like work, many tasks are enjoyable sometimes and not so enjoyable other times.  For example, driving is a chore a lot of the time, but occasionally (on backroads) it is fun. 
 

Automating Life Appropriately

A simple and obvious solution is to use automation and efficiency when we want to (e.g., driving the morning commute) and not when we don't want (e.g., driving country backroads).  As long as we have the option and can decide how and when we do things automatically instead of manually, we can have the best of both worlds.  When I want to wash the car, I can pull out the hose and scrub away.  When I don't, I can use the drive through.  When I want get my hands dirty and use my muscles, I can dig away in the garden and mow the lawn.  When I don't, I can get yard service.  In this way, we can have the advantages of automation and efficiency without being forced to give up the satisfaction of doing it ourselves.
 
My Sudoku solver works great, but I think I'll do it by hand and brain the next time around.  It won't be nearly as fast, but it will be fun.  And isn't that the point after all?
 
 

Thursday, October 29, 2015

2015 NFL Game Predictions: Week 8

Welcome!  I intend this to be an ongoing project of predicting NFL game outcomes, point spreads, and final scores.  My hope is that my models will improve over time as they become more sophisticated and use better data.  I will try to regularly publish predictions to keep myself accountable, and will make observations along the way about what is working and what isn't.  See below for latest updates.  Enjoy!
Previous predictions
_____________________________________________________________________________________
Recap of Week 8:
My most recent attempt wasn’t great.  My predictions went 8-6.  Let’s look at what happened:
·         49ers vs. Rams
o   Predicted: 49ers 64% likely to win, but they lost.
o   Other sites predicted a Ram’s victory.  I should have agreed.  49ers have been struggling and had the worst of the two records going into the game.  Kaepernick is getting benched and Vernon Davis has been traded, so things are looking really grim for the 49ers going forward.  No real injuries I see, so my prediction was just bad.  Especially since the 49ers got trounced.
·         Packers vs. Broncos
o   Predicted: 64% Packers likely to win, but they lost.
o   Other sites also favored the Packers.  Packers didn’t have any new major injuries.  Again, it looks like another missed prediction, although this time I was on the side of other predictions.  Unfortunately, the game wasn’t even close.
·         Falcons vs. Buccaneers
o   Predicted: 65% Falcons likely to win, but they lost.
o   This game went into overtime, and other sites thought the Falcons would win too, so I don’t feel too bad.  Falcons had a much stronger record and were playing at home.  I’ll call this one unlucky.
·         Lions vs. Chiefs
o   Predicted: 55% Lions likely to beat Chiefs, but they lost.
o   Other sites favored the Chiefs, but not by much.  Both teams had pretty bad records, but the Lions were worse.  Lions got destroyed 45 to 10.  Lions were a bit healthier than in previous games.  Another bad prediction on my part.
·         Jets vs. Raiders
o   Predicted: Jets 53% likely to win, but they lost.
o   Other sites favored the Jets, and they had a slightly better record going into the game.  Jets have a lot of injuries on their offense, including their QB.  Raiders look comparatively healthy, so perhaps this can help explain some of the error in prediction (my model does not yet account for injuries/starters).
·         Titans vs. Texans
o   Predicted: Titans 56% likely to win, but they lose.
o   Texans were favored to win by other sites and they had a slightly better record going into the game.  Texans look more injured than Titans.  So again, another bad call on my part.
I was in agreement with other sites on 3 of these 6 games.  It looks like injuries are partly making a difference, but not by much.  I think in the end, I need better data and a more accurate model as some of my predictions weren’t even close.  We’ll try again soon.
Week 8: Second Published Predictions (Win/Lose)
Below is the next round of predictions I was able to make.  I've been working on cleaning up the code, automating data pulls, creating new features, and making sure I wasn't using any information that was not known prior to the game in building my model.  Here are the predictions for week 8:
Week
Date
Team
HomeAway
Opponent
ProbabilityWin
PredictedTeamWin
ActualTeamWin
8
10/29/2015
Dolphins
@
Patriots
0.28
0
0
8
10/29/2015
Patriots
Dolphins
0.72
1
1
8
11/1/2015
49ers
@
Rams
0.64
1
0
8
11/1/2015
Bears
Vikings
0.31
0
0
8
11/1/2015
Bengals
@
Steelers
0.62
1
1
8
11/1/2015
Broncos
Packers
0.36
0
1
8
11/1/2015
Browns
Cardinals
0.34
0
0
8
11/1/2015
Buccaneers
@
Falcons
0.35
0
1
8
11/1/2015
Cardinals
@
Browns
0.66
1
1
8
11/1/2015
Chargers
@
Ravens
0.38
0
0
8
11/1/2015
Chiefs
Lions
0.45
0
1
8
11/1/2015
Cowboys
Seahawks
0.44
0
0
8
11/1/2015
Falcons
Buccaneers
0.65
1
0
8
11/1/2015
Giants
@
Saints
0.41
0
0
8
11/1/2015
Jets
@
Raiders
0.53
1
0
8
11/1/2015
Lions
@
Chiefs
0.55
1
0
8
11/1/2015
Packers
@
Broncos
0.64
1
0
8
11/1/2015
Raiders
Jets
0.47
0
1
8
11/1/2015
Rams
49ers
0.37
0
1
8
11/1/2015
Ravens
Chargers
0.62
1
1
8
11/1/2015
Saints
Giants
0.59
1
1
8
11/1/2015
Seahawks
@
Cowboys
0.56
1
1
8
11/1/2015
Steelers
Bengals
0.37
0
0
8
11/1/2015
Texans
Titans
0.44
0
1
8
11/1/2015
Titans
@
Texans
0.56
1
0
8
11/1/2015
Vikings
@
Bears
0.69
1
1
8
11/2/2015
Colts
@
Panthers
0.34
0
0
8
11/2/2015
Panthers
Colts
0.66
1
1
_____________________________________________________________________________________

Friday, October 16, 2015

Take You Out, Coach: Why NFL Coaches Get Sacked

Introduction

While I am continuing to gather more data for predicting NFL game outcomes, I am exploring the data I gather for insights and interesting facts.  My most recent exploration comes from looking at yearly team data with the coach included for each year.  From that I can determine how long a coach has been on that same team, if there was a coaching change, and what impact a coaching change has.  I can also gain some insight as to why a coach is fired.  Here are some things I discovered.

Random Facts about Coaches

  • Most years coaching for a single team in a row?
    • 29 years by Landry of the Dallas Cowboys, 1960 -1988 and Lambeau for the Packers 1921-1949.  Others: Shula (26, Dolphins), Owen (23, Giants), and Noll (23, Steelers)
    • Current coaches: Belichick (16, Patriots), Lewis (13, Bengals), and Coughlin (12, Giants)
  • Most years coaching for a single team:
    • 39 years for Halas for the Bears.  From 1920-1929, 1933-1941, 1946-1955,1958-1967
  • Average years of coaching for a single team: 4 years (median of 3)



    • Most coaches only get 2 years, but 1 year is closely behind
  • Most wins: Shula (346), Halas (313), Landry (250)
  • Most losses: Shula (202), Landry (162), Reeves (155)
  • Highest overall win ratio by a retired coach over more than a single season: Madden (.72)
    • Current coach over more than one season: Arians (.70), McCarthy(.68), and Belichick (.67)
  • Most teams coached for (depends on how you count it, but...):
    •  Phillips (5), Edwards, Johnson, Mora, Parcells, Ryan, Saban, Schottenheimer, Turner (4)
  • Most playoff appearances:
    • Shula (19), Landry (18), Brown (15), Belichick (13), Schottenheimer (13)
  • Most years since playoffs with the same coach:
    • Halas (8), Lambeau (7), Parker (7), Wilson (7), Starr (6)
  • Most years since playoffs by any team:
    • The Cardinals were out of the playoffs for 25 years straight from 1949-1973.  The Redskins were also out for 25 years from 1946-1970.
    • Current: Bills (16), Browns (13), and Raiders (13)

Coaching Changes and Win Ratio

Does a coaching change make a difference in the following year?  If we look at the Win Ratio (wins/(wins+losses+ties)), the win ratio in years where there is no coach change (i.e., the same coach as previous year) is higher on average than years where there is a coach change (i.e., a different coach from previous year).  No coach change years have an average win ratio of .53 while coach change years have an average of .40.  The graph of the distribution is below.




But perhaps it is lower because the previous coach was doing such a poor job, and so the new coach has a bad team to start with and needs time to rebuild.  We can compare the win ratio of coaches on their last year with those in their first year (i.e., a coach change), and we find out that they are virtually the same.  Coaches in their last year have a slightly lower win ratio (.38), but the distribution looks basically the same:
In fact, if we look at coaches who are not in their first year or in their last year, these coaches have an average win ratio of .57.  The distribution is below:
So what we might expect is that a coach will do fairly poorly his first year as he rebuilds a broken team, he will do better in his middle years, but as his win ratio declines, he is headed for his last year as a coach for the particular team.  That is, after a grace period, a coach's continued employment depends on the win ratio.  This seems reasonable.  But here is what that journey looks like, plotting the win ratio for every coach/team combo over the duration of that coach's time with the team (duration is calculated by year of coaching for the team divided by total years of coaching for the team):
There is no pattern here.  In fact, win ratio appears to have nothing to do with a coach's duration.  But perhaps the average win ratio for each duration follows the pattern we would expect.  In fact, there is a broad trend of rising and then falling of the average win ratio through the tenure of all coaches as a group:

However, for any given individual coach, this trend may not be followed perfectly.  Here are some examples:

Some coaches finish their last year coaching with a decent win ratio, and as we have seen there is a lot of variation.  So while it is an important part of the reason why a coach may be let go, it is not the only reason. 

Why Do Coaches Get Fired (or Retire or ...)

Most coaches do not get fired (or retire) each year.  Over the history of the NFL, a coach has been in his last continuous year of coaching for the same team about 27% of all year/team/coach combinations.  If trying to predict if a coach will be coaching his last year, one could simply predict for all year/team/coach combinations that he will not be coaching his last year, and one would be correct 73% of the time.  Obviously, this is not helpful if we are trying to predict when a coach will be fired/retired, since all of these predictions will be wrong.  So the success of model in this instance is how well it predicts the firing/retiring of a coach specifically.
Coaches are likely fired/retired for many reasons not directly observable to the public: administrative conflicts, new opportunities, actual retirement, family reasons...  Such things are not readily known and as a result cannot be included in a model.  What is known (and what I will be focusing on) is each coach's football stats with his team prior to his firing/retiring.  In particular:
  • Wins, Losses, Ties, Win Ratio Previous years win ratio comparison
  • Made Playoffs that year, Years since playoffs with that coach
  • Team ranks (offensive, defensive, overall)
  • Years Coaching
These factors are easily measurable, publicly measurable, and intuitively important in whether a coach is fired/retired.  According to my models, here are the important factors and some comments on them:
  • Win Ratio:
    • Having a 0.50+ win ratio strongly indicates that the coach will NOT be fired/retired, although it is not perfect.
  • Point Difference (points for - points against)
    • A negative point difference likely means the coach will be fired/retired, unless he has better than average points for.  If that is the case, then what seems to matter is the current win ratio compared to previous years. 
    • If the coach does not have better than average points for and has a negative point difference, the coach will likely be fired/retired.
  • Win Ratio Differences
    • If  there has been a 30% drop in win ratio over the past three years, then the coach will most likely be fired/retired.
    • If not,  and the coach has appeared to have peaked already in win ratio, then its a toss up whether the coach will keep his job or not.
    • Drops in win ratio from two years prior and also the previous year indicate the coach is likely to be fired/retired.
  • Wins
    • Having more than 10 wins suggests the coach will NOT be fired/retired, although it is not perfect.
  • Years Coaching
    • If a coach has a win ratio less than 0.50, and has only coached one year, he is more likely to be fired/retired than not, but only slightly.  Surviving at least two years greatly improves his changes of not being fired.  In fact, the more years you coach, the less likely you are to be fired/retired.
  • Offensive Rank
    • With a losing record in the season, a coach can still keep his job if his team's offensive rank by points is in the top 6 (i.e., 1-6).  In one model, each decrease (e.g., 7 to 8) in offensive rank increased the coach's chances of firing by 3%.
  • Years Since Playoffs with Same Coach
    • In some models, this really mattered.  In one, for every year not going to the playoffs, the coach's chances of being fired/retired increased by about 15%.  The longer the coach is out of the playoffs with his team, the more likely he will be fired.
    • Although a bit unfair, a team's being out of the playoffs for a long time increases a coach's chances of being fired, even when that coach was not responsible for the long drought that preceded him.


In summary, a coach will likely be fired/retired if some combination of the following factors is present in any given year: a win ratio of less than 50%, a declining win ratio from previous years, a low scoring offense, more points against than for, fewer years coaching for the team, and several years since a playoff appearance.

Who Has to Worry in 2015?

Based on the above considerations and modeling, who should be most worried in 2015 with the way things are at present?  I would have said Philbin of the Dolphins, but he already got fired.  After him, I believe Payton and Tomsula have the most to be worried about:
  • Payton (Saints)
    • The Saints had a bad year last year and this year doesn't look any better, although the recent win against the Falcons may bring hope.  Nevertheless, the best seems to be in the past for Payton, at least as far as his time with the Saints is concerned.  I rate him as 75% likely to be fired/retired.
  • Tomsula (49ers)
    • The 49ers are off to a really bad start.  They didn't make the playoffs last year, and this year is not looking good either.  While it is Tomsula's first year, that may make it harder to keep his job if he can't turn things around soon.  I rate him as 75% likely to be fired/retired.
Others that may have reason to worry: Harbaugh (Ravens), Garrett (Cowboys), Caldwell (Lions), and McCoy (Chargers).


Conclusion

 It is not surprising that coaches are largely fired because they have started losing and are not going to the playoffs.  What is slightly surprising is that the longer a coach is coaching, the more likely he is to continue coaching.  I suppose that past success can help sustain a coach into the future, at least for a while.  Also a bit surprising initially but not after reflection, is the fact that, even though the team has a losing record, as long as the team is putting up lots of points, the coach will likely be retained.  After all, what do fans want to see?  Wins, playoffs, and lots of points being scored by their team.  A great defense is necessary to win championships, but it is not as glamourous or as fun to watch as a great offense.

Good luck in week 6!