Find a criminal from his ear, finger, and head

Question

Prior to the discovery of fingerprints and DNA testing, the British police used an anthropometric system to identify repeat offenders. Certain parts of the bodies of criminals were measured and stored in records -- these parts of the body were assumed to not change in size after adulthood. This system was known as bertillonnage.

The diagram below shows a filing system used by the police to access these records quickly.

Diagram 1: A filing system with numbered drawers.
^{Note: if you cannot see the image, try the imgur mirror or compile it yourself.}

The filing cabinet consists of 81 numbered drawers. Each drawer contains cards, and each card has measurements of particular parts of a criminal's body:

• The length of their head (H)
• The breadth of their head (B)
• The width of their right ear (E)
• The length of their index finger (F)

Each measurement is classified as either small, medium or large.

For example, drawer 56 contains cards with the following characteristics: small H, large B, medium E, and small F. This can be notated using the letters S, M, and L in place of small, medium, and large:

SH,LB,ME,SF

Note that the size letter goes first, then what the measurement is. In addition, an exclamation point ! may be placed in front to cause a negative:

!SH,LB,!ME,SF

This indicates cards that have the following characteristics: not small H, large B, not medium E, and small F. There are four drawers that contain cards with these characteristics -- 58, 60, 61, and 63.

Your task is to write a program, that, when given a string notating some characteristics, outputs all of the drawers that contain cards with those characteristics. If there are no drawers that contain cards with the given characteristics, output 0.

Here are some sample inputs and outputs.

1. Input: SH,LB,ME,SF
   Output: 56
2. Input: !SH,LB,!ME,SF
   Output: 58,60,61,63
3. Input: SB,!MF,!LF
   Output: 1,2,3,4,5,6,7,8,9
4. Input: MH,!MH
   Output: 0

This is code golf, so the shortest entry wins. Ask questions in the comments if the specification is not clear.

Answer 1

GolfScript 95 (DEMO)

','/:r;81,{r{1$[[.9%3/\.3%\.27/\9/3%]{'SML'=}%'HEBF']zip{''+}%\.,3=\1${(;}*@?)!!=},!\;},{)}%0or

Answer 2

Ruby 1.9.3 - 173 157 143

x=(1..81).select{|j|$*[0].split(?,).all?{|y|i=j-1
z='SML'
[z[i%9/3]+?H,z[i%3]+?E,z[i/27]+?B,z[i/9%3]+?F].member?(y[-2,2])^y[?!]}}
p x==[]?[0]:x

Edit:

• applied Three If By Whiskey's tips.
• taken parameters from the command line to save some more chars

Online demo: http://ideone.com/lodTLt

Answer 3

Scala - 951

Definitely won't win this one, mainly due to the names of built in functions I think.

def m(a: List[Int]) = 0 to 8 flatMap (x => a map (_ + 9*x)) toSet
var SH = m(List(1,2,3))
var MH = m(List(4,5,6))
var LH = m(List(7,8,9))
var SE = m(List(1,4,7))
var ME = m(List(2,5,8))
var LE = m(List(3,6,9))
var SB = 1 to 27 toSet
var MB = 28 to 54 toSet
var LB = 55 to 81 toSet
def l(a: List[Int]) = 0 to 2 flatMap (x => a map (_+27*x)) toSet
var SF = l(1 to 9 toList)
var MF = l(10 to 18 toList)
var LF = l(19 to 27 toList)

var j = Map(("LH",LH),("MH",MH),("SH",SH),("LB",LB),("MB",MB),("SB",SB),("LF",LF),("MF",MF),("SF",SF),("LE",LE),("ME",ME),("SE",SE))

def f(x : String) = {
  def h(i : List[String], k : Set[Int]) : Set[Int] = {
      if(i isEmpty) k
      else if(i.head.startsWith("!")) h(i.tail, k filterNot (j(i.head.replace("!","")) contains _))
      else h(i.tail, k intersect j(i.head))
  }
  h(x split "," toList, 1 to 81 toSet) mkString ","
}

Argument is passed into the function f

f("SH,LB,ME,SF") = 56

Answer 4

T-SQL - 547 544

Not a winning entry, but suited to this type of problem.

Grid Table Setup - 254

SELECT ROW_NUMBER()OVER(ORDER BY (SELECT $))I,LEFT(Z,1)E,RIGHT(Z,1)H,LEFT(Y,1)F,RIGHT(Y,1)B INTO G FROM(VALUES('SS'),('MS'),('LS'),('SM'),('MM'),('LM'),('SL'),('ML'),('LL'))FB(Y),(VALUES('SS'),('MS'),('LS'),('SM'),('MM'),('LM'),('SL'),('ML'),('LL'))EH(Z)

Query - 293 290

DECLARE @S CHAR(400)='SELECT ISNULL(SUBSTRING(O,2,99),0)FROM (SELECT CONCAT('','',I)FROM G WHERE '+REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REVERSE(@i),',',' AND '),'S!','!S'),'M!','!M'),'L!','!L'),'S','=''S'''),'M','=''M'''),'L','=''L''')+' FOR XML PATH(''''))O(O)';EXEC(@S)

Input is done by declaring @i before the query

DECLARE @I VARCHAR(50) = 'SB,!MF,!LF';

I could save a further 89 characters if the output doesn't have to be comma delimited row

DECLARE @S CHAR(400)='SELECT I FROM G WHERE '+REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REVERSE(@i),',',' AND '),'S!','!S'),'M!','!M'),'L!','!L'),'S','=''S'''),'M','=''M'''),'L','=''L''')

Answer 5

Mathematica 191 235

Represents each cell number in base 3. Each digit position represents a bodily feature. The value of the digit, {0,1,2}, represents "Small","Medium","Large", respectively.

The features correspond to the digits as follows:

{"breadthOfHead", "IndexFingerLength", "LengthOfHead", "WidthOfRightEar"}

For example, the input,

{"SH","LB","ME","SF"}

signifies:

"LB" implies breadthOfHead = 2 (large)

"SF" implies IndexFingerLength = 0 (small)

"SH" implies LengthOfHead = 0 (small)

"ME" implies WidthOfRightEar = 1 (medium)

2001in base 3 is 55 in base 10.

We need to add one because we are counting cells from 1, not zero.

---

Code

c=Characters;t=Table[IntegerDigits[k,3,4],{k,0,80}];
f@i_:=1+FromDigits[#,3]&/@Intersection@@(Cases[t,#]&/@(ReplacePart[{_,_,_,_},{#}]&/@(c/@i
/.Thread[c@"BFHESML"-> {1,2,3,4,0,1,2}]/.{{"!",v_,n_}:> (n-> Except[v]),{v_Integer,n_}:> n-> v})))
/.{}:>0

---

Test Cases

f[{"SH","LB","ME","SF"}]

{56}

---

f[{"!SH","LB","!ME","SF"}]

{58, 60, 61, 63}

---

f[{"SB","!MF","!LF"}]

{1, 2, 3, 4, 5, 6, 7, 8, 9}

---

f[{"MH","!MH"}]

0

Answer 6

Python 3 - 192 - Try it!

from itertools import*
S=input().split(',')
print([i+1for i in range(81)if eval('*'.join('(list(product(*["SML"]*4))[i][%d]%s="%s")'%('BFHE'.find(s[-1]),'!='[s[0]>'!'],s[-2])for s in S))]or 0)

Answer 7

Python 2 - 194

from itertools import*
n=map(set,['012']*4)
for x in raw_input().split(','):n['BFHE'.find(x[-1])]&=set(`'SML'.find(x[-2])`)^set('012'*(x<'"'))
print[1+int(''.join(x),3)for x in product(*n)]or[0]

Output has brackets, and don't care about order of output
Some suggestions from Falko, and a couple from myself to take off 10 chars.