New Coders Survey 2016

Brief analysis of the dataset from the Free Code Camp's New Coders Survey 2016:

https://github.com/tkuriyama/notebooks/blob/master/ipython/New_Coders_Survey_2016.ipynb

TLDR; coding schools / bootcamps yield mixed results, but there are lots of folks interested in coding and lots of resources available beyond Udacity and Coursera.

SICP

I've decided to work through SICP. So far, its reputation as a classic text that has withstood the test of time seems well deserved. I've been targeting one sub-chapter a week, so factoring in an extra 50% for distractions and presumed difficulty of later chapters, it will take me the remainder of the year to finish.

This post was incredibly useful in terms of setting up a good vim / tmux working environment with Racket as the language of choice: http://crash.net.nz/posts/2014/08/configuring-vim-for-sicp/. It seems like emacs may have better indentation support, but learning a new editor still escapes me.

Python Sudoku Solver

Inspired by Richard Bird's sudoku solution in Pearls of Functional Algorithm Design, I wrote a Python solver.

Since the rules of Sudoku involve row, column, and box-wise operations, it makes sense to have a solution for iterating over each of the three ways of dividing up a board. One possible solution is to write functions that all have custom logic for row, column, and box-wise operations (perhaps based on indexing or dictionary lookups, depending on the board implementation). Another, more functional solution is to write helper functions that transform the board, such that all functions can iterate over the board in the same way, regardless of whether it is a row, column, or box-wise operation. Ideally, the transformation functions are involutions, such that it is easy to return the board to its original arrangement (e.g. cols(cols(board)) == board). The latter is adopted in this solver:

http://nbviewer.jupyter.org/url/tarokuriyama.com/notebooks/sudoku.ipynb

Explicit Type Annotations

In languages with good type inference, it's often quick and easy to omit type annotations. As a student prone to typos, I've found that this can lead to pernicious bugs when the function parameters are not obvious.

In this example ported to F# from Richard Bird's book, glue is supposed to take a digit and a tuple of (Expression, Values) and return a list of (Expression, Values) tuples. But there is a syntactic bug that cannot be inferred without more context (n.b. the list delimiter in F# is a semi-colon rather than comma):

type Digit = int
type Factor = Digit list
type Term = Factor list
type Expression = Term list
type Values = (Digit * Digit * Digit * Digit)

let glue x ((xs :: xss) :: xsss, (k, f, t, e)) =
        [(((x :: xs) :: xss) :: xsss, (10 * k, k * x + f, t, e)),
         (([x] :: xs :: xss) :: xsss, (10, x, f * t, e)),
         ([[x]] :: (xs :: xss) :: xsss, (10, x, 1, f * t + e))]

In an IDE, the type checker makes the error obvious once annotations are added. Editing for the correct list delimiters, glue is defined as:

let glue' (x: Digit) (ev: Expression * Values) : (Expression * Values) list =
    match x, ev with
    | x, ((xs :: xss) :: xsss, (k, f, t, e)) ->
        [(((x :: xs) :: xss) :: xsss, (10 * k, k * x + f, t, e));
         (([x] :: xs :: xss) :: xsss, (10, x, f * t, e));
         ([[x]] :: (xs :: xss) :: xsss, (10, x, 1, f * t + e))]


Just another reminder that "explicit is better than implicit".

F# and Functional Pearls

After encountering the language last year, I've finally gotten around to studying F# from Expert F#. So far, the language has proven much friendlier than Haskell (though it's not really a fair comparison since I'm now more aware of functional constructs).

As practice, I've started implementing some Project Euler problems in F#. I've also been working on porting some Haskell "functional pearls" from Richard Bird's excellent book Pearls of Functional Algorithm Design. The going is slow but rewarding, as it's turning out to be a great way to practice F# while also learning more about functional programming in general.

One chapter that I've worked on is the "countdown" problem, in which the goal is to use some numbers from a given list to generate an arithmetic expression that evaluates to a value as close to target as possible. For example, given a list of numbers [1, 3, 7, 10, 25, 50] and a target of 831, the solution is: 

> display(countdown1 831 [1;3;7;10;25;50]);;

(7+((1+10)*(25+50))) = 832

https://github.com/tkuriyama/functional-pearls/tree/master/countdown

Longest Subpalindrome in Linear Time

I've finally rewritten the linear time algorithm for finding the longest palindromic substring ("subpalindrome") within a given string. I originally came across this problem in Peter Norvig's class on Udacity and have worked on it quite a bit since then.

I'm not altogether satisfied with the clarity of the code -- it is quite imperative and stateful, with many indexing variables -- but I don't see a way to meaningfully refactor without changing the fundamental structure, so I'll leave that for another day.


Algorithm Description and Visualization
http://tarokuriyama.com/projects/palindrome2.php

Code
https://github.com/tkuriyama/palindrome

Blacksmith Puzzle Solved

The blacksmith puzzle from a previous blog post is now solved!

I experimented with a number of heuristics, but I wasn't able to come up with a very good way to rank next moves.

In the end, the combinatorial solution works fine -- it's just that the solution space was unnecessarily polluted by permutations of the same visited states. Modifying the hash of visited states to use sorting ensures uniqueness, and the solution now runs in a few seconds. Interestingly, the magic number of 13 chain links appears to be necessary, as the solver didn't find a solution when fed 12 chain links as a starting state.

https://gist.github.com/tkuriyama/8de2711675350645349d