How a 20-line program to solve sudokus came about

1 Apr 2014 | , ,
Share on:

I started using K, a predecessor language to q, in 1995. I had been hired by a large European bank to tune their databases. I found many performance and expressability problems that were forcing programmers to move analytics to C++, Java, or even Excel. Communication from one to the other often caused errors and always came with a performance penalty.

My client introduced me to Steve Apter and Arthur Whitney who showed me K, which I began to use for a project to detect unusual expenditures within one division of the company. I got hooked by the sheer power of working in a monolingual environment, the advantages of debugging in an interpretive environment, and the speed.

I’ve been using K or q ever since for prototypes for data analysis, finance, biology, and even puzzle design. One time my son, then 12, gave me a sudoku to solve when sudoku first was popular. I was on a train and staring at the paper gave me motion sickness. So I wrote a 20 line program in K to solve all sudokus. Later, I sent it to Arthur Whitney and he came back with an 80 character program. Too awesome, I know.

Over the years in conversations with Arthur, I extolled some of the benefits of relational algebra and SQL. Eventually he came out with KSQL, and then q, which is a clear semantic improvement over SQL, it subsumes SQL and includes order-dependent aggregates such as moving averages, as-of joins, and so on.

When I teach this, I refer to the model as “arrable” (for array-table). It’s a conceptually more powerful model than unordered tables and simplifies programming.

By Prof. Dennis Shasha
Department of Computer Science
Courant Institute of Mathematical Sciences
New York University

SUGGESTED ARTICLES

Python vs kdb+ for data analytics

A comparison of Python and q for data analysis

21 Aug 2018 | , , , ,

Guest blogger Ferenc Bodon illustrates using Python, SQL and kdb+ for data analytics in this blog. He takes an example that goes just one step beyond the simplest use cases by performing some aggregation based on multiple columns. Anybody who analyzes data tables will bump into this type of problem, probably on the third day.

Kx Insights: Machine learning subject matter experts in semiconductor manufacturing

9 Jul 2018 | , ,

Subject matter experts are needed for ML projects since generalist data scientists cannot be expected to be fully conversant with the context, details, and specifics of problems across all industries. The challenges are often domain-specific and require considerable industry background to fully contextualize and address. For that reason, successful projects are typically those that adopt a teamwork approach bringing together the strengths of data scientists and subject matter experts. Where data scientists bring generic analytics and coding capabilities, Subject matter experts provide specialized insights in three crucial areas: identifying the right problem, using the right data, and getting the right answers.