coderrr

October 28, 2008

Ruby golf; generating random strings

Filed under: ruby — Tags: — coderrr @ 9:15 am

Update: See comments for all the latest/best solutions.

This post got me into some Ruby golfing a few days ago. The challenge is to see how few characters of Ruby code you need to generate a random string of length 4 or more consisting of only the following set of characters a-z, A-Z, 0-9.

The shortest solution posted on the blog entry was 59 chars. I came up with 50, can anyone beat this?

(0..9).map{0until(c=rand(?z).chr)=~/(?!_)\w/;c}*''

I’ll show an expanded version to help explain how it works

char_array = (0..9).map do
  until ( c = rand(?z).chr ) !~ /(?!_)\w/
    0
  end
  c
end
rand_string = char_array*''

(0..9).map just runs the block 10 times and stores the values in an array. *'' is a synonym for .join('') which turns the array into a string. The loop just keeps picking random characters with ascii values between 0 and ?z (122) until it matches one which is in the range we want. The actual body of the loop does nothing, but in the condition the variable c is set to the chosen random character. I used the while/until syntax form which allows you to put the body before the while condition. Using a number (0) as the body allowed me to not even have to use a space.

I described the range of characters with the regular expression /(?!_)\w/ which is equivalent to, but 1 character shorter than /[a-z\d]/i. /\w/ is the same as /[a-z\d_]/i so the problem is it will also match an underscore. I got around this with the negative lookahead (?!_) which means don’t match an underscore.

I think that’s about it. Can anyone beat 50?

Crap I just almost bested myself. This one returns a string ALMOST 100% of the time, but on some rare occasions it will return nil:

(0..9999).map{rand(?z).chr}.join[/[a-z\d]{9}/i]

47 chars, and if you change 9999 to 999 and {9} to {4}, you can get a 4 character string almost 100% of the time with only 46 chars.

Update: Wow Magnus comes in at 42… crazy:

(0..9).map{rand(?z).chr[/[^_\W]/]||redo}*''

props to nonsequitur for the regex /[^_\W]/
mme

30 Comments »

  1. /[^_\W]/ will let you strip another character. Birdie!

    Comment by nonsequitur — October 28, 2008 @ 12:44 pm

  2. 44: (0..9).map{0until(c=rand(?z).chr)[/\w/];c}*”

    Comment by Magnus Holm — October 28, 2008 @ 2:47 pm

  3. Crap. We need that (?!_) in there, so it’s only 49 :-(

    Comment by Magnus Holm — October 28, 2008 @ 2:50 pm

  4. 42: (0..9).map{rand(?z).chr[/[^_\W]/]||redo}*”

    Comment by Magnus Holm — October 28, 2008 @ 2:56 pm

  5. oh man… thats good… you win

    Comment by coderrr — October 28, 2008 @ 7:49 pm

  6. And if you don’t care about A-Z, you can do it 31:
    (0..9).map{rand(?#).to_s ?#}*”

    Comment by Magnus Holm — October 28, 2008 @ 9:21 pm

  7. lol base 35 man you’re fuckin insane…

    but you’d want to use base 36 instead right, ?$ ?

    Comment by coderrr — October 28, 2008 @ 9:25 pm

  8. Yeah, that’s right. I messed up with that :-)

    Comment by Magnus Holm — October 29, 2008 @ 8:36 am

  9. sepp2k came in w a super short one, 20 chars (only does a-z 0-9):

    rand(36**9).to_s(36)

    Comment by coderrr — November 14, 2008 @ 7:40 pm

  10. Nah. That’s cheating! The rand _might_ return very low values, so you’re not guaranteed to get it 9-chars long each time…

    Comment by Magnus Holm — November 25, 2008 @ 8:21 pm

  11. yea, good point

    Comment by coderrr — November 26, 2008 @ 5:07 am

  12. [...] Here is a Ruby golf riddle, which I have no idea how could be made this short (42 characters) without redo (via coderrr): [...]

    Pingback by Ruby, Rails, Web2.0 » Blog Archive » Ruby’s Most Underused Keyword — February 6, 2009 @ 9:41 pm

  13. This one, at 54, has the advantage of not using any ‘trial and error’.

    (A lot of you guys’ might not terminate if the random number generator gets stuck in a particular cycle, say)

    It also contains a smiley :-S

    ((0..9).map{(?0+rand(62)).chr}*”").tr(‘:-ST-m’,'A-Za-z’)

    Comment by Matthew — February 7, 2009 @ 12:52 pm

  14. Realised that can be trimmed to 52:

    ((0..9).map{(?0+rand(62)).chr}*””).tr’:-ST-m’,’A-Za-z’

    Comment by Matthew — February 7, 2009 @ 2:17 pm

  15. I don’t know how you guys will feel about this one, but I gotta share:

    rand.to_s.crypt($0).delete(‘/.’)[2,9]

    It’s only 37 characters, but does depend on $0 having a 2-character or longer string value (as it would in irb, for example). And the closing slice is there only to wax the two salt-provided characters.

    Comment by JeffMo — February 7, 2009 @ 9:11 pm

  16. Also, please correct me if I am wrong, but I think Magnus’s solution needs to have ?{ instead of ?z in the call to rand.

    Here is how I tested for the minor flaw I think I have perceived:

    (0..9999).any? { ((0..9).map{rand(?z).chr[/[^_\W]/]||redo}*”").include?(‘z’) }
    => false

    In English, that is “run 10000 trials of Magnus’s code, and see if any of those trials generate a string which includes ‘z’.”

    Making the change noted:

    (0..9999).any? { ((0..9).map{rand(?{).chr[/[^_\W]/]||redo}*”").include?(‘z’) }
    => true

    Comment by JeffMo — February 7, 2009 @ 9:35 pm

  17. JeffMo: Yes, you are absolutely correct; and the crypt is pretty sweet!

    Matthew: Yeah, I guess the trial and error is bad… You’ve managed to count wrong, though. Here’s a real 52: (0..9).map{(?0+rand(62)).chr.tr’:-ST-m’,'A-Za-z’}*”

    Comment by Magnus Holm — February 7, 2009 @ 11:33 pm

  18. Ah, yes my bad, i think the double quotes confused my attempt to run “(thecode)”.length. Yours works for 52 though.

    Here’s another nasty little trick that takes it down to 49:

    ENV.map{(?0+rand(62)).chr.tr’:-ST-m’,'A-Za-z’}*”

    and takes the winner down to 39:

    ENV.map{rand(?z).chr[/[^_\W]/]||redo}*”

    Works provided there’s at least 4 environment variables defined :) Which there invariably is unless it’s run as “env -i ruby” or something

    Comment by Matthew — February 7, 2009 @ 11:40 pm

  19. Woah, *that* was very nice! We need more golfing like this!

    Comment by Magnus Holm — February 7, 2009 @ 11:45 pm

  20. haha you guys are crazy!! i love it

    @jeffmo: the crypt one is awesome, except that it’s possible that crypt could produce a lot of . and / which would make the resulting string too short.

    38 :)
    $:.map{rand(?z).chr[/[^_\W]/]||redo}*”

    Comment by coderrr — February 8, 2009 @ 8:43 am

  21. @coderrr:

    I agree that is a theoretical drawback to the crypt solution I offered. However, it works pretty reliably in practice:

    irb(main):001:0> (1..10000000).map.any? { rand.to_s.crypt($0).delete(‘/.’)[2,9].size false

    Also, you’ll probably want to make the same correction to your “38″ solution that I suggested for Magnus’s solution earlier. (As it stands, it won’t generate any ‘z’ chars.)

    Comment by JeffMo — February 8, 2009 @ 6:21 pm

  22. LOL, that copied IRB session got hosed a bit. Trying again:

    irb(main):002:0> (1..10000000).map.any? { rand.to_s.crypt($0).delete(‘/.’)[2,9].size < 4 }
    => false

    Comment by JeffMo — February 8, 2009 @ 6:25 pm

  23. yea good pt thx

    $:.map{rand(?{).chr[/[^_\W]/]||redo}*”

    yea i agree in practice you probly wouldn’t run into it much, i wonder what the probability is.

    you could shave off one more char i think:

    rand.to_s.crypt($0).tr(‘./’,”)[2,9]

    or even shorter at the cost of losing all $0 chars and being under 4 more often:

    34
    rand.to_s.crypt($0).tr(“./#$0″,”)

    Comment by coderrr — February 8, 2009 @ 7:02 pm

  24. This is getting extreme!

    Collaborative golfing is so much funnier than competitive (aka codegolf.com)!

    Comment by Magnus Holm — February 8, 2009 @ 7:10 pm

  25. Jeffmo brought this to work, and then helped me with this one.

    36.

    (“%#{rand(2)>0?’x':’X'}”%srand)[9,4]

    I’m sure it can be improved upon…

    Comment by PeterFairfield — February 9, 2009 @ 8:20 pm

  26. rand>0.5 would make it one less, but I really need to get rid of the ternary altogether.

    Comment by PeterFairfield — February 9, 2009 @ 8:29 pm

  27. Here’s another vector, revolving around the fact that Integer#to_s accepts a base.

    This clocks in at 34 characters, and does not do upper case, but might inspire some:

    i=(x=36)**9;(rand(i*x-i)+i).to_s x

    Comment by Mina Naguib — February 10, 2009 @ 5:32 pm

  28. @coderr

    Hmm. True. I guess that essentially makes my version the same as sepp2k’s, but meeting the 10-character requirement.

    Comment by Mina Naguib — February 10, 2009 @ 6:54 pm

  29. yea good point mina, i missed that yours will always give 10

    Comment by coderrr — February 19, 2009 @ 8:13 pm


RSS feed for comments on this post. TrackBack URI

Leave a comment

Blog at WordPress.com.