16
\$\begingroup\$

Inspired by this CR question (please don't kill me for browsing CR)

Spec

The probabilities of misspelling a word are:

  • 1/3 of the time don't change the output
  • 1/3 of the time remove a random character
  • 1/3 of the time duplicate a random character

The chance for removing/duplicating a given character in the input should be the same for all chars.

If two consecutive characters are the same (case-sensitive), the probability of one of them being modified should be the same as if they are one character. I.e. the outputs for AA (which are AA or A or AAA) should all have the same probability.


The input will only contain of letters for simplicity.

Examples

First line is input, following lines are all possible misspellings. Each line should have the same probability of being output, the input is excluded in the examples but it should still have a 1/3 probability of output.

foo

fo
oo
ffoo
fooo
PPCG

PPC
PPG
PCG
PPPCG
PPCCG
PPCGG
\$\endgroup\$
  • \$\begingroup\$ It's a nice challenge, but if each line has the same probability of being output, doesn't that mean that it isn't a 1/3 chance that the word stays the same? \$\endgroup\$ – Value Ink Aug 30 '16 at 0:45
  • \$\begingroup\$ @ValueInk okay that is a flaw with the examples. let me fix \$\endgroup\$ – Downgoat Aug 30 '16 at 0:47
  • 3
    \$\begingroup\$ Wait, if each line would have the same probability of being output, then wouldn't the distribution of characters not be uniform? Like, with foo: if you remove a character it could become (-f)oo, f(-o)o, and fo(-o). So fo should be twice as likely as oo, but you say every line has equal probability. \$\endgroup\$ – Deusovi Aug 30 '16 at 3:34
  • 2
    \$\begingroup\$ @Deusovi there is a whole paragraph explaing this, I'll copy that here just in case If two consecutive characters are the same (case-sensitive), the probability of one of them being modified should be the same as if they are one character. I.e. the outputs for AA (which are AA or A or AAA) should all have the same probability. \$\endgroup\$ – edc65 Aug 30 '16 at 8:24
  • 1
    \$\begingroup\$ @DJMcMayhem no, more than one characters are usually misspelt ;_; \$\endgroup\$ – Downgoat Aug 30 '16 at 18:08

11 Answers 11

5
\$\begingroup\$

Pip, 38 27 bytes

a@:`(.)\1*`YRR#aa@y@0X:RR3a

This was fun--got to use Pip's regex and mutable string capabilities, which I hadn't pulled out in a while. Takes input via command-line argument.

Explanation:

a@:`(.)\1*`                  Split a into runs of identical chars using regex match
           YRR#a             Yank randrange(len(a)) into y (randomly choosing one such run)
                a@y@0        Take the first character of that run
                     X:RR3   Modify in place, string-multiplying by randrange(3):
                               If RR3 is 0, character is deleted
                               If RR3 is 1, no change
                               If RR3 is 2, character is duplicated
                          a  Output the modified a

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Wow, congrats on having a terse golfing lang only with ASCII \$\endgroup\$ – Downgoat Aug 30 '16 at 1:02
3
\$\begingroup\$

Ruby, 64 55 + 1 (p flag) = 56 bytes

Input is a line of STDIN piped in without trailing newline.

a=[]
gsub(/(.)\1*/){a<<$&}
a.sample[-1]*=rand 3
$_=a*''
\$\endgroup\$
2
\$\begingroup\$

CJam (21 bytes)

re`_,mr_2$=3mr(a.+te~

Online demo

Dissection

r     e# Read a line of input from stdin
e`    e# Run-length encode it
_,mr  e# Select a random index in the RLE array
_     e# Hang on to a copy of that index
2$=   e# Copy the [run-length char] pair from that index
3mr(  e# Select a uniformly random integer from {-1, 0, 1}
a.+   e# Add it to the run-length
t     e# Replace the pair at that index
e~    e# Run-length decode
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 107

w=>(r=x=>Math.random()*x|0,a=w.match(/(.)\1*/g),a[p=r(a.length)]=[b=a[p],b+b[0],b.slice(1)][r(3)],a.join``)

Less golfed

w=>(
  a = w.match(/(.)\1*/g),
  r = x => Math.random()*x | 0,
  p = r(a.length),
  b = a[p],
  a[p] = [b, b+b[0], b.slice(1)][r(3)],
  a.join``
)

Test

f=w=>(r=x=>Math.random()*x|0,a=w.match(/(.)\1*/g),a[p=r(a.length)]=[b=a[p],b+b[0],b.slice(1)][r(3)],a.join``)

function update() { 
  O.innerHTML = Array(99)
  .fill(I.value)
  .map(x=>(
    r=f(x),
    r==x?r:r.length<x.length?'<b>'+r+'</b>':'<i>'+r+'</i>'
  
    )
  ).join` `
}

update()
#O { width:90%; overflow: auto; white-space: pre-wrap}
<input id=I oninput='update()' value='trolley'><pre id=O></pre>

\$\endgroup\$
2
\$\begingroup\$

Java 7, 189 180 178 bytes

import java.util.*;String c(String i){Random r=new Random();int x=r.nextInt(2),j=r.nextInt(i.length());return x<1?i:i.substring(0,j-(x%2^1))+(x<2?i.charAt(j):"")+i.substring(j);}

Ungolfed & test cases:

Try it here.

import java.util.*;
class M{
  static String c(String i){
    Random r = new Random();
    int x = r.nextInt(2),
        j = r.nextInt(i.length());
    return x < 1
            ? i
            : i.substring(0, j - (x%2 ^ 1)) + (x<2?i.charAt(j):"") + i.substring(j);
  }

  public static void main(String[] a){
    for(int i = 0; i < 5; i++){
      System.out.println(c("foo"));
    }
    System.out.println();
    for(int i = 0; i < 5; i++){
      System.out.println(c("PPCG"));
    }
  }
}

Possible output:

foo
fooo
foo
foo
ffoo

PPCCG
PPCG
PPCCG
PPPCG
PPCG
\$\endgroup\$
1
\$\begingroup\$

Python 2, 134 bytes

from random import*
def f(s):
 p=c=0;M,L=[],list(s)
 for t in L:
  if t!=p:M+=c,;p=t
  c+=1
 L[choice(M)]*=randint(0,2);return''.join(L)

White spaces in for loop are tabs.

Try it on Ideone

\$\endgroup\$
1
\$\begingroup\$

Pyth - 17 bytes

This one actually handles the special cases with consecutive char correctly.

 XZOKrz8Or_1 2r9K

Test Suite.

\$\endgroup\$
  • \$\begingroup\$ This is 16 bytes? Is the leading space correct? If not this is 15 bytes? \$\endgroup\$ – Downgoat Aug 31 '16 at 22:29
  • \$\begingroup\$ @Downgoat no, the leading space is correct. I'm pretty sure that its 17 bytes. \$\endgroup\$ – Maltysen Sep 1 '16 at 2:39
1
\$\begingroup\$

APL, 21

{⍵/⍨3|1+(?3)×(⍳=?)⍴⍵}

This starts by creating a vector of zeros with a 1 in random position. Then multiplies it by a random number between 1 and 3. +1 and mod 3 obtains a vector with all 1s and one random positioned 0,1 or 2.

Finally, ⍵/⍨ says that each letter should be written n times, where n are the numbers in the vector.

Try it on tryapl.org

\$\endgroup\$
0
\$\begingroup\$

Python 2, 123 bytes

from random import*
R=randint
s=input()
m=n=R(0,len(s)-1)
c=R(0,2)
m=[m,1+[-len(s),m][m>0]][c==1]
n+=c==2
print s[:m]+s[n:]
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 103

w=>{w=w.split(''),r=Math.random,x=r(),i=r()*w.length|0;w.splice(i,x<.6,x>.3?w[i]:'');alert(w.join(''))}
\$\endgroup\$
0
\$\begingroup\$

APL, 27 bytes

{⍵/⍨(?3)⌷1⍪2 0∘.|1+(⍳=?)⍴⍵}

Explanation:

                        ⍴⍵  ⍝ length of ⍵
                   (⍳=?)    ⍝ bit vector with one random bit on 
                 1+         ⍝ add one to each value (duplicate one character)
           2 0∘.|           ⍝ mod by 2 and 0 (remove instead of duplicate)
         1⍪                 ⍝ add a line of just ones (do nothing)
    (?3)⌷                   ⍝ select a random line from that matrix
 ⍵/⍨                        ⍝ replicate characters in ⍵

Test:

      {⍵/⍨(?3)⌷1⍪2 0∘.|1+(⍳=?)⍴⍵} ¨ 10/⊂'foo'
 fooo  foo  oo  foo  fo  fo  oo  fo  oo  fooo 
\$\endgroup\$

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.