{"id":531,"date":"2009-10-25T23:58:59","date_gmt":"2009-10-25T15:58:59","guid":{"rendered":"http:\/\/blog.lolyco.com\/sean\/?p=531"},"modified":"2009-10-26T00:21:36","modified_gmt":"2009-10-25T16:21:36","slug":"code-golf-at-stackoverflow-byte-array-substring-searching","status":"publish","type":"post","link":"https:\/\/blog.lolyco.com\/sean\/2009\/10\/25\/code-golf-at-stackoverflow-byte-array-substring-searching\/","title":{"rendered":"Code golf at Stackoverflow. Byte array substring searching."},"content":{"rendered":"

I don’t know what<\/em> I was searching for when I found this ‘code golf’ challenge at Stack Overflow<\/a>. The challenge was to find a substring of bytes in a byte array, returning the start position. It cost me half an hour or so, so I thought I’d post my attempt up for posterity. Many of the answers were aiming at presenting the code in the fewest characters possible, so that’s what I did too.<\/p>\n

I didn’t do an in-depth survey, but it looked like a lot of the contributions were na\u00efve string search, as is mine. Better search algorithms exist<\/a>, so be warned! Here’s my 116 characters of Java:<\/p>\n

int m(byte[]a,int i,int y,byte[]b,int j,int z)\r\n{return i<y?j<z?a[i]==b[j++]?m(a,++i,y,b,j,z)\r\n:m(a,0,y,b,j,z):-1:j-y;}\r\n<\/code><\/pre>\n
Not<\/em> pretty! I have to confess to writing it with whitespace and if-else first, before stripping out the whitespace and converting if-else to (boolean expression)?statement-if-true:statement-if-false. One thing I noticed in an early attempt is that you can remove the whitespace between the ‘return’ statement and ‘-1’. Should you ever need to do that, you know who to thank!<\/p>\n
Before you complain about the missing javadoc markup, the first byte array is the string to search for<\/strong>. The second byte array is the string to search in<\/strong>. The two ints following each byte array are the start index in each (typically zero – it saves me having to write another method to do that, and hence, precious characters in my golf!) and the length of the byte array – to save me using the lengthy ‘.length’ property! The method returns, as per spec, the position of the first matching substring or -1 if a match is not found.<\/p>\n
Some of the really short contributions are from alleged programing languages with built in substring handling. You’ll forgive me if I sneer at those attempts and say they’re not really<\/em> programming languages, they’re applications with complicated interfaces.<\/p>\n","protected":false},"excerpt":{"rendered":"
I don’t know what I was searching for when I found this ‘code golf’ challenge at Stack Overflow. The challenge was to find a substring of bytes in a byte array, returning the start position. It cost me half an hour or so, so I thought I’d post my attempt up for posterity. Many of […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[30,20,51,3],"tags":[109,32,33,9,105,57],"class_list":["post-531","post","type-post","status-publish","format-standard","hentry","category-breaktime","category-fixed","category-philosophy","category-software","tag-fixed","tag-haha","tag-java","tag-open-source","tag-software","tag-web"],"_links":{"self":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/531","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/comments?post=531"}],"version-history":[{"count":9,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/531\/revisions"}],"predecessor-version":[{"id":536,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/posts\/531\/revisions\/536"}],"wp:attachment":[{"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/media?parent=531"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/categories?post=531"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.lolyco.com\/sean\/wp-json\/wp\/v2\/tags?post=531"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}