Kdb+ Mastermind Challenge

Kdb+ Mastermind Challenge

4 Oct 2017 | , , , , ,
Share on:

By Nick Psaris

Nick Psaris is an expert kdb+/q programmer and the author of “Q-Tips: Fast, Scalable and Maintainable Kdb+” (available on Amazon). At the most recent Kx Community NYC Meetup (September 2017), Nick presented the results of his “Kdb+ Mastermind Challenge.” The rules for the challenge appear below, and more information is available on Nick’s GitHub.

Background

Mastermind is a popular code-breaking game introduced in 1975 that pits a “codemaker” against a “codebreaker.” The “code,” represented by four pegs chosen from a universe of 6 colors, is picked by the “codemaker.” The “codebreaker” continually makes 4-peg guesses and is told by the “codemaker” how many are the correct color in the correct position, and how many are the correct color in the wrong position.

The actual game uses black and white begs to denote these two cases. We will use a list of two values to represent the score. For example, if two pegs are correct and one peg is the right color but in the wrong position, the score would be: 2 1. The game continues until the “codebreaker” guess the correct code (with a score of 4 0).

There are 14 possible scores:

q)flip (where;raze til each)@\: 5 4 3 1 1
0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
2 0
2 1
2 2
3 0
4 0

Challenge

The challenge is to write a function that returns the score when provided a code and guess. For example, given the code of “1124” and the guess of “1412”, the score would be 1 3.

q)score["1124";"1412"]
1 3

Once a peg is used for a match it can not be used again. For example, given the code of “1234” and the guess of “1111”, the score would be 1 0, not 1 3.

q)score["1234";"1111"]
1 0

Scoring

There are are a total of 1296 possible codes:

q)count C:(cross/)4#enlist "123456"
1296

Your solution will be judged valid if it computes the proper md5:

q)md5 3 raze/ string C score\:/: C	
0x08dd3c8cfd42bda309c38b9bdab16a06

The fastest valid submission (measured in milliseconds) will be judged the winner.

q)\t C score\:/: C
5838

In the event of a tie, the submitter who provided the first valid submission (irrespective of performance) will be declared the winner.

Results

There were 14 submissions in the month before the Meetup, including an excellent C implementation which was ineligible for the prize. The top four solutions were notable by their completely different approaches.

First place went to this solution:

k)score:{[x;y;z;w]y@6/:x w,z}[@[&,55;"123456";:;!6];{(+/m;0+/&/g@\:!*g:(#:'=:)'(y n;x n:&~m:x=y))}.',/(,\:/:)/2#,,:'.q.cross/4#,"123456"]

Second place went to this solution:

score:{(4-c),$[f2~df:distinct f2:f where not (c:count w)=f:(x@:w)?y@:w:where not x=y;
  count df;
  count[df]+sum @[y;f?df;:;"_"] in @[x;df;:;" "]
  ]}

Third place went to this solution:

score:{n:0 0 0 0 0 0 0 0 0 0 0 0i;n[-49 -49 -49 -49 -43 -43 -43 -43i+"i"$x,y]+:1i;b,(sum(&). 0 6_n)-b:sum x=y}

Fourth place went to this solution:

score:{n,4-(n:sum x=y)+count{x _x?y}/[x;y]}

The winning solution was fast not just because it cached the mappings from guess to score, by creating a projection, but also because their caching mechanism was faster than a dictionary lookup.

First prize was a new Mastermind board game which now resides in the common room of our Meetup host, 1010data.

© 2017 Kx Systems
Kx® and kdb+ are registered trademarks of Kx Systems, Inc., a subsidiary of First Derivatives plc.

SUGGESTED ARTICLES

Kx collaborating with Fintech startup chartiq

Collaboration: The Dominant Trend in Finance

13 Dec 2017 | , , , ,

In December we are re-blogging some of our favorite content from Kx partners and affiliated companies, starting with this article on the ChartIQ blog. ChartIQ is an agile FinTech company that sells an advanced HTML5 charting library used in technical data analysis, trading configurations and for charting in the capital markets industry. Kx offers a ChartIQ integration as an addition to our Dashboards. In “Collaboration: The Dominant Trend in Finance,” ChartIQ’s Hanni Chehak writes about the rise of FinTech companies, and the role collaboration plays as FinTech companies are increasingly disrupting the traditional banking sector.

Water system workers with kdb+ historical database

Kdb+ Use Case: Machine Learning Water System Maintenance Application

6 Dec 2017 | , , , ,

Kdb+ is being used much more widely in machine learning applications today. Its ability to quickly ingest and process data, particularly large, fragmented datasets, is one way that developers are adding kdb+ to their technology stack of artificial intelligence and machine learning tools.
For Australian kdb+ developer Sherief Khorshid, who also develops machine learning systems, incorporating kdb+ into a predictive maintenance application gave him the edge in a hackathon win that landed him a cash prize and a contract with the Water Corporation of Western Australia.

kdb+ FFI

Kdb+ FFI: Access external libraries more easily from q

22 Nov 2017 | , , ,

Following on from the hugely popular Python library and interface embedPy and PyQ, Kx has released an FFI as part of the Fusion for kdb+ interfaces. As with embedPy and PyQ, this FFI is open-sourced under the Apache 2 license.
The kdb+ FFI is a foreign function interface library for loading and calling dynamic libraries from q code. It has been adapted and expanded upon from a library originally written by Alex Belopolsky of Enlightenment Research. With the kdb+ FFI you can now call your favorite C/C++ libraries directly from q without the overhead of having to compile shared objects and load into q using the 2: command.