17
\$\begingroup\$

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.

Table 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.

\$\endgroup\$
  • \$\begingroup\$ As a historical note for accuracy, ​​​​​​​​​​​​​​​bertillonnage systems were actually much more complicated than this simplified version, using 9 measurements instead of 4, and thus using a more involved filing system than the one depicted here. \$\endgroup\$ – absinthe Sep 7 '14 at 4:57
  • 4
    \$\begingroup\$ Oh no! not ANOTHER Sudoku question ;-) \$\endgroup\$ – Level River St Sep 7 '14 at 12:25
  • 1
    \$\begingroup\$ @steveverrill I actually made the diagram from a sudoku template, so there's some truth in that :o \$\endgroup\$ – absinthe Sep 7 '14 at 12:27
1
\$\begingroup\$

GolfScript 95 (DEMO)

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

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ select is a shorter synonym for find_all. You could trim another two characters by replacing y[-2..-1] with y[-2,2], and three more still by using ==[] instead of .empty?. \$\endgroup\$ – Three If By Whiskey Sep 7 '14 at 12:22
  • \$\begingroup\$ @ThreeIfByWhiskey Great tips, thanks! I've edited my answer. \$\endgroup\$ – Cristian Lupascu Sep 7 '14 at 15:53
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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''')
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ ​​​​​​​​​​​​​​​Yes, it's okay to have the input wrapped in brackets. \$\endgroup\$ – absinthe Sep 8 '14 at 2:20
  • \$\begingroup\$ Do they need to be in order? \$\endgroup\$ – Bizangles Sep 8 '14 at 2:22
  • \$\begingroup\$ Good question. Actually, the output doesn't have to be in order - although I'm not sure how outputting them in a different order would save characters.​​​​​​​​​​​​​​​ \$\endgroup\$ – absinthe Sep 8 '14 at 2:23
  • \$\begingroup\$ I'm using python set()s, converting them back to lists, getting the product, converting to base 3 numbers back to ints. In all that, the order gets a little jumbled and I need to use sorted() if I want them back in the right order. \$\endgroup\$ – Bizangles Sep 8 '14 at 2:27
  • \$\begingroup\$ I see. Order isn't important so the sorted() may be removed. Nice solution. \$\endgroup\$ – absinthe Sep 8 '14 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.