title: More cowbell...!

text:
# Question
Title: More cowbell...!
You are providing tech support to *the* Bruce Dickenson as he produces a Blue Öyster Cult recording session. When he asks for more cowbell, you can give it to him.

## Your task

Write a program or function that takes a string (or equivalent in your language) as input, and outputs a related string containing one more cowbell.

## How many cowbells does a string contain?

The number of cowbells a string contains equals the maximum number of distinct copies of "cowbell" that can be obtained by permuting the characters of the string. For example, `"bbbccceeellllllooowwwwwwwww"` contains 3 cowbells, while `"bbccceeellllllooowwwwwwwww"` and `"bbbccceeelllllooowwwwwwwww"` each contain 2 cowbells, and `"cowbel"` contains 0 cowbells.

## How should the output be related to the input?

The output should consist of the concatenation, in this order, of the input string and the shortest prefix of the input string needed to increase the number of cowbells.

For example, `"bbbccceeelllllooowwwwwwwww"` only needs one additional `"l"` to contain 3 cowbells instead of 2; the shortest prefix that contains that `"l"` is `"bbbccceeel"`. Therefore, if the input is `"bbbccceeelllllooowwwwwwwww"`, then the output should be `"bbbccceeelllllooowwwwwwwwwbbbccceeel"`.

## Technicalities

* You may assume that the input contains only printable ASCII characters. If there are one or two characters that are annoying for your language's string processing (such as newlines or `\`), you can assume that the input doesn't contain them—just mention this restriction.
* You may further assume that the alphabetic characters in the input are all lowercase, or all uppercase. If you choose not to assume one of these, count cowbells case-insensitively.
* You may further assume that the input contains at least one copy of each of the characters `b`, `c`, `e`, `l`, `o`, and `w`. This is equivalent to assuming that some prefix of the string can be concatenated to it to produce a string that contains more cowbell. (Note that the input string itself need not contain a cowbell.)
* If your language has a builtin that solves this problem ... then totally use it, seriously, how awesome is that.

## Gold-plated diapers

Since recording studio time is expensive, your code must be as short as possible. The entry with the fewest bytes is the winner!

## Test cases

(pastebin link for easier copy/pasting)

Test input #1: `"christopher walken begs for more cowbell!"`

Test output #1: `"christopher walken begs for more cowbell!christopher wal"`

Test input #2: `"the quick brown fox jumps over the lazy dog"`

Test output #2: `"the quick brown fox jumps over the lazy dogthe quick brown fox jumps over the l"`

Test input #3: `"cowbell"`

Test output #3: `"cowbellcowbell"`

Test input #4: `"cowbell cowbell cowbell"`

Test output #4: `"cowbell cowbell cowbellcowbell"`

Test input #5: `"cowbell cowbell cowbel"`

Test output #5: `"cowbell cowbell cowbelcowbel"`

Test input #6: `"bcelow"`

Test output #6: `"bcelowbcel"`

Test input #7: `"abcdefghijklmnopqrstuvwxyz"`

Test output #7: `"abcdefghijklmnopqrstuvwxyzabcdefghijkl"`

Test input #8: `"cccowwwwbbeeeeelllll"`

Test output #8: `"cccowwwwbbeeeeelllllccco"`

Test input #9: `"be well, programming puzzles & code golf"`

Test output #9: `"be well, programming puzzles & code golfbe well, programming puzzles & c"`

Test input #10: `"lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. wow!"`

Test output #10: `"lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. wow!lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut lab"`

Test input #11:

```
"c-c-b-c

i have a cow, i have a bell.
uh! bell-cow!
i have a cow, i have a cowbell.
uh! cowbell-cow!

bell-cow, cowbell-cow.
uh! cow-cowbell-bell-cow.
cow-cowbell-bell-cow!
"

```

Test output #11:

```
"c-c-b-c

i have a cow, i have a bell.
uh! bell-cow!
i have a cow, i have a cowbell.
uh! cowbell-cow!

bell-cow, cowbell-cow.
uh! cow-cowbell-bell-cow.
cow-cowbell-bell-cow!
c-c-b-c

i have a cow, i have a bell"

```

# Answer
> 13 votes
# Pip, ~~50~~ ~~42~~ 38 bytes

```
T$<(MN{_NaM"lcowbe"}//^2M[aYa@<i])++iy

```

Pass the string in as a command-line argument, quoted if necessary. Try it online!

### Explanation

I'm going to explain this in two parts: the cowbell function and the full program. First, here's the function that computes the amount of cowbell in a string:

```
MN{_NaM"lcowbe"}//^2

```

`{...}` defines a function. Many Pip operators, when applied to a function, return another function; for example, `-{a+1}` is the same as `{-(a+1)}`. So the above is equivalent to

```
{MN(_NaM"lcowbe")//^2}

```

which works as follows:

```
{                    }  Function, in which a is the 1st argument (the string)
    _Na                 Lambda fn: returns number of times its argument occurs in a
       M"lcowbe"        Map that function to the characters of "lcowbe"
                   ^2   A devious way to get [2]: split the scalar 2 into characters
   (            )//     Int-divide the list of character counts by [2]
                        Since the lists are not the same length, this divides the first
                          element (# of l's) by 2 and leaves the others alone
 MN                     Take the min of the resulting list

```

Now that we have that, here's the full program:

```
T$<(MN{_NaM"lcowbe"}//^2M[aYa@<i])++iy
                                        a is 1st cmdline arg, i is 0 (implicit)
T                                       Loop till condition is true:
                            a@<i        Slice leftmost i characters of a
                           Y            Yank that into y variable
                         [a     ]       List containing a and that value
                        M               To that list, map...
    MN{_NaM"lcowbe"}//^2                ... the cowbell function
                                        Result: a list containing the amount of cowbell
                                        in the original string and the amount in the slice
 $<(                             )      Fold on less-than: true if the first element is
                                        less than the second, otherwise false
                                  ++i   In the loop, increment i
                                     y  Once the loop exits, print y (the latest slice)

```

# Answer
> 6 votes
# C, ~~511~~ ~~488~~ ~~474~~ ~~470~~ ~~463~~ 454

```
void f(char*a){char*s;int i=-1,c,o,w,b,e=b=w=o=c=1,l=3,n,r,z=i;for(;s=a[++i];c+=s==67,o+=s==79,w+=s==87,b+=s==66,e+=s==69,l+=s==76);r=~-l/2;n=c<o?c:o;n=w<n?w:n;n=b<n?b:n;n=e<n?e:n;n=r<n?r:n;c=c==n;o=o==n;w=w==n;b=b==n;e=e==n;if(l=r==n?l:0)if(l%2)l=2;else l=1,c=o=w=b=e=0;else l+=l%2;n=c+o+w+b+e+l;for(printf("%s",a);s=n?a[++z]:0;s==67&&c?n--,c--:0,s==79&&o?n--,o--:0,s==87&&w?n--,w--:0,s==66&&b?n--,b--:0,s==69&&e?n--,e--:0,s==76&&l?n--,l--:0,putchar(s));}

```

**Try it online**

---

Readable format + explanation:

```
void f(char*a){
//a = input

    char*s;

    int i=-1,c,o,w,b,e=b=w=o=c=1,l=3,n,r,z=i;//c,o,w,b,e all start at 1; L starts at 3

    for(;s=a[++i];c+=s==67,o+=s==79,w+=s==87,b+=s==66,e+=s==69,l+=s==76);
    //loop to obtain number of times each character C,O,W,B,E,L is found in string (using the ASCII numeric values of each letter)

    //to get an extra cowbell we need to increment C,O,W,B,E by 1 and L by 2 (two Ls in cowbell); except we don't have to because we already did that by starting them at c=1, o=1, w=1, b=1, e=1, L=3 when we declared them.

    r=~-l/2;
    //r is half of (1 less the number of times L is in string (+ init value))

    n=c<o?c:o;n=w<n?w:n;n=b<n?b:n;n=e<n?e:n;n=r<n?r:n;
    //n is the number of times that the least occouring character appears in the string, (use R instead of L since cowbell has two L's in it and we just need ~-l/2)

    c=c==n;o=o==n;w=w==n;b=b==n;e=e==n;
    //convert c,o,w,b,e to BOOL of whether or not we need 1 more of that letter to create one more cowbell (logic for L handled below since it's trickier)

    if(l=r==n?l:0)//if L-1/2 is [or is tied for] least occurring character do below logic, else set l to 0 and skip to `else`
        if(l%2)//if l is divisible by 2 then we need 2 more Ls
            l=2;
        else //otherwise we just need 1 more l and no other letters
            l=1,c=o=w=b=e=0;
    else //add 1 to L if it's divisible by 2 (meaning just 1 more L is needed in addition to possibly other C,O,W,B,E letters) (*Note: L count started at 3, so a count of 4 would be divisible by 2 and there is only 1 L in the string)
        l+=l%2;

    n=c+o+w+b+e+l;
    //n = number of specific characters we need before we reach 1 more cowbell

    for(printf("%s",a);s=n?a[++z]:0;s==67&&c?n--,c--:0,s==79&&o?n--,o--:0,s==87&&w?n--,w--:0,s==66&&b?n--,b--:0,s==69&&e?n--,e--:0,s==76&&l?n--,l--:0,putchar(s));
    //loop starts by printing the original string, then starts printing it again one character at a time until the required number of C,O,W,B,E,L letters are reached, then break (s=n?a[++z]:0) will return 0 when n is 0. Each letter subtracts from n only when it still requires letters of its type (e.g. b?n--,b--:0)

}

```

---

Some Fun Tricks Used:

•When checking characters I type `'w'` for the char w which is 3 bytes, but for the characters `'c'` and `'b'` I can type their ASCII values 99 and 98 respectively to save a byte each time. *(Edit: Thanks to @Titus I know do this with all COWBELL letters by using uppercase input only which are all 2 bytes numeric ascii values)*

`r=~-l/2` is `r=(l-1)/2` using bitshifts

`a[++i]` I'm getting the character at index(i) and iterating the index all at the same time. I just start `i` at `i=-1` instead of `i=0` (I do the same with `z` and start it as `z=i` to save another byte)

# Answer
> 5 votes
## Python 2, ~~125~~ ~~113~~ 112 bytes

```
n=lambda s:min(s.count(c)>>(c=='l')for c in "cowbel")
def f(s,i=0):
 while n(s)==n(s+s[:i]):i+=1
 return s+s[:i]

```

---

`n` counts the number of cowbells

---

-12 bytes thanks to @Rod
-1 byte thanks to @Titus

# Answer
> 5 votes
# Perl 6, 91 bytes

```
{my &c={.comb.Bag.&{|.<c o w b e>,.<l>div 2}.min}
first *.&c>.&c,($_ X~[\,](.comb)».join)}

```

Assumes lower-case input.

### How it works

Inside the lambda, another lambda for counting the number of cowbells in a string is defined as such:

```
my &c={                                        }  # Lambda, assigned to a variable.
       .comb                                      # Split the string into characters.
            .Bag                                  # Create a Bag (maps items to counts).
                .&{                       }       # Transform it into:
                   |.<c o w b e>,                 #   The counts of those letters, and
                                 .<l>div 2        #   half the count of "l" rounded down.
                                           .min   # Take the minimum count.

```

The rest of the code uses this inner lambda `&c` to find the result, like this:

```
                     [\,](.comb)».join   # All prefixes of the input,
               ($_ X~                 )  # each appended to the input.
first         ,                          # Return the first one for which:
      *.&c>                              #   The cowbell count is greater than
           .&c                           #   the cowbell count of the input.

```

# Answer
> 5 votes
# MATL, ~~38~~ 37 bytes

*1 byte off thanks to @DLosc's idea of using the template string `lcowbe` instead of `cowbel`*

```
n`Gt@q:)hXK!'lcowbe'=s32BQ/kX<wy-Q]xK

```

Input characters are all lowercase. If the input contains newlines, the newline character needs to be entered as its ASCII code concatenated with the normal characters (see last input in the link with all test cases).

Try it online! Or verify all test cases.

# Answer
> 3 votes
# JavaScript (ES6), 106 ~~107 113 126 141~~

A porting to javascript of the Pip answer by @DLosc. I needed some time to fully understand it, and it's genius.

**Edit** -15 bytes following the hint by @Titus, directly appending chars to the input string `a` and avoiding early return (so no `for/if`)

**Edit 2** enumerating the 6 value for the Min function saves other 13 bytes

**Edit 3** changed c function again. I thought the verbose `length` and `split` would be too lengthy. I was wrong.

Assuming lowercase input

```
a=>[...a].some(z=>c(a+=z)>b,c=a=>Math.min(...[...'lcowbe'].map((c,i)=>~-a.split(c).length>>!i)),b=c(a))&&a

```

*Less golfed*

```
a=>{
  c=a=>{ // cowbell functions - count cowbells
    k = [... 'lcowbe'].map((c,i) =>
          (a.split(c).length - 1) // count occurrences of c in a
           / (!i + 1) // divide by 2 if first in list ('l')
    );
    return Math.min(...k);
  };
  b = c(a); // starting number of cowbells
  [...a].some(z => ( // iterate for all chars of a until true
    a += z,
    c(a) > b // exit when I have more cowbells
  ));
  return a;
}

```

**Test**

```
f=
a=>[...a].some(z=>c(a+=z)>b,c=a=>Math.min(...[...'lcowbe'].map((c,i)=>~-a.split(c).length>>!i)),b=c(a))&&a

;["christopher walken begs for more cowbell!"
,"the quick brown fox jumps over the lazy dog"
,"cowbell"
,"cowbell cowbell cowbell"
,"cowbell cowbell cowbel"
,"bcelow"
,"abcdefghijklmnopqrstuvwxyz"
,"cccowwwwbbeeeeelllll"
,"be well, programming puzzles & code golf"
,"lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. wow!"
,`c-c-b-c

i have a cow, i have a bell.
uh! bell-cow!
i have a cow, i have a cowbell.
uh! cowbell-cow!

bell-cow, cowbell-cow.
uh! cow-cowbell-bell-cow.
cow-cowbell-bell-cow!
`].forEach(x=>console.log(x+'\n\n'+f(x)))
```

# Answer
> 2 votes
# Bash \+ Unix utilities, 184 bytes

```
f()(tr -cd cowbel<<<"$1"|sed 's/\(.\)/\1\
/g'|sort|uniq -c|awk '{print int($1/(($2=="l")?2:1))}'|sort -n|head -1)
for((m=1;`f "$1${1:0:m}"`!=$[`f "$1"`+1];m++)){ :;}
echo "$1${1:0:$m}"

```

Try it online!

Thanks to @AlbertRenshaw for golfing 2 bytes off.

# Answer
> 2 votes
# Octave, ~~80~~ ~~87~~ 97 bytes

```
s=input('');k=1;do;until(x=@(A)min(fix(sum('cowbel'==A')./('111112'-48))))(b=[s s(1:++k)])>x(s);b

```

Try It Online!

# Answer
> 2 votes
# JavaScript (ES6), ~~124~~ 114 bytes

*Thanks to Neil for saving a few bytes*

```
a=>eval("for(c=0,d=a;(A=$=>Math.min([...'cowbel'].map(_=>($.split(_).length-1)>>(_=='l'))))(a)==A(d+=a[c++]););d")

```

Since this is quite different from the already existing JavaScript answer, and I put quite some time into this, I decided to create an answer myself.

## Usage

```
f=a=>eval("for(c=0,d=a;(A=$=>Math.min([...'cowbel'].map(_=>($.split(_).length-1)>>(_=='l'))))(a)==A(d+=a[c++]););d")
f("cowbell")

```

### Output

```
"cowbellcowbell"

```

# Answer
> 2 votes
# CJam, 37

```
q___S\+{+"cowbel"1$fe=)2/+:e<\}%()#)<

```

Try it online

If I can exclude the `"` and `\` characters, then…

## 35 bytes

```
q___`{+"cowbel"1$fe=)2/+:e<\}%()#)<

```

Try it online

**Explanation**

The code successively appends each character of the string to the initial string (going from original to doubled), determines the number of cowbells for each string (counting the number of occurrences of each character in "cowbel" and dividing the one for 'l' by 2, then taking the minimum), finds the position of the first string where the number of cowbells increases by 1, then takes the corresponding prefix of the input and puts it after the input string.

In order to include the original string too (with no character appended), the code prepends a neutral character to the string that's being iterated. The first version prepends a space, and the 2nd version uses the string representation, i.e. the string between double quotes.

```
q___          read input and make 3 more copies: one for output, one for prefix,
               one for appending and one for iterating
S\+           prepend a space to the iterating string
              or
`             get the string representation
{…}%          map each character of the string
  +           append the character to the previous string
  "cowbel"    push this string
  1$          copy the appended string
  fe=         get the number of occurrences of each "cowbel" character
  )2/+        take out the last number, divide by 2 and put it back
  :e<         find the minimum
  \           swap with the appended string
(             take out the first number (cowbells in the initial string)
)#            increment and find the index of this value in the array
)             increment the index (compensating for taking out one element before)
<             get the corresponding prefix
              another copy of the input is still on the stack
              and they are both printed at the end

```

# Answer
> 1 votes
# PHP, 133 bytes

a PHP port of @edc65´s JavaScript port of DLosc´s Pip answer.

```
function f($s){for(;$c=lcowbe[$i];)$a[$c]=substr_count($s,$c)>>!$i++;return min($a);}for($s=$argv[1];f($s)==f($s.=$s[$i++]););echo$s;

```

takes lower case input from command line argument. Run with `-nr`.

**breakdown**

```
// function to count the cowbells:
function f($s)
{
    for(;$c=lcowbe[$i];)            # loop through "cowbel" characters
        $a[$c]=substr_count($s,$c)  # count occurences in $s
            >>!$i++;                # divide by 2 if character is "l" (first position)
        return min($a);             # return minimum value
}
for($s=$argv[1];    # copy input to $s, loop:
    f($s)               # 1. count cowbells in $s
    ==                  # 3. keep looping while cowbell counts are equal
    f($s.=$s[$i++])     # 2. append $i-th character of $s to $s, count cowbells
;);
echo$s;             # print $s

```

---
Tags: code-golf, string
---


title: String truncation/summarization

text:
# Question
Title: String truncation/summarization
Not entirely sure if this one or a similar challenge has already been posted, but here it goes anyway.

Write a program that takes a `string` as input and writes its trucated/summarized `output` form such that a specific `sep` (separator) is placed in the middle, removing the necessary characters of the original `string` so that the length of `output` equals a given `width`.

# Rules

* Input is a `string`, a `width` and a `sep` (separator);
* `if len(string) <= width: output = string`, meaning that the output is the string itself unchanged;
* `if width <= len(sep): output = sep`, meaning that the output is the separator only;
* `len(output)` must be equal to `width`, with the exception of the previous case;
* The excess character in case of uneven number of remaining characters for each half of the string can be placed on the left or right halve;
* Standard code-golf challenge with the smallest program to win.

# Examples

Format: `"string" [length(string)] --> "output" [length(ouput) / width]` with `sep` equal to `_(...)_` (`_` are whitespaces).

```
"xtlgxbdwytxcjacu" [16] --> "x (...) " [8 / 8]
"upjptz" [6] --> " (...) " [7 / 3]
"h" [1] --> "h" [1 / 1]
"qsshkvmawcmf" [12] --> " (...) " [7 / 7]
"tvdknroxszhufgck" [16] --> "tv (...) k" [10 / 10]
"ag" [2] --> "ag" [2 / 5]
"vbgdegtgshnzjrudca" [18] --> "vbgd (...) udca" [15 / 15]
"bscwimjjhmgvcwp" [15] --> "bscwimjjhmgvcwp" [15 / 18]
"xwhgbaenornbzwirlp" [18] --> "xwhgbaenornbzwirlp" [18 / 18]
"tbqyrekkzyizc" [13] --> "t (...) " [8 / 8]
"oowdwbeezeh" [11] --> "o (...) h" [9 / 9]
"avlzfzpjazhjc" [13] --> "avlzfzpjazhjc" [13 / 15]
"dngxmebwenfrbidonses" [20] --> "dngxme (...) donses" [19 / 19]
"bqfxyffdemjghipk" [16] --> "bqfxyffdemjghipk" [16 / 16]
"sfwnlkreghzff" [13] --> " (...) " [7 / 5]
"dznlsyaojtferxh" [15] --> "dznlsyaojtferxh" [15 / 17]
"zwkhjdafkzjdgc" [14] --> "zwk (...) dgc" [13 / 13]
"kpzochngmwoulne" [15] --> "kpz (...) lne" [13 / 13]
"vluqvhpcxg" [10] --> "vluqvhpcxg" [10 / 10]
"wuc" [3] --> "wuc" [3 / 8]

```

# Answer
# Python 2, ~~93~~ ~~76~~ 72 bytes

```
s,w,p=input()
l=len(s)
if w<l:w=max(w-len(p),0);s[-~w/2:l-w/2]=p
print s

```

Try it online!

Input and output are a list of characters
> 3 votes

# Answer
## JavaScript (ES6), 78 bytes

```
(w,s,e,l=s.length,m=e.length)=>l>w?m<w?s.slice(0,w-m>>1)+e+s.slice(m-w>>1):e:s

```

I was pleasantly surprised to discover that `w-m>>w` and `m-w>>1` give the desired result.
> 2 votes

# Answer
# Python 2, 76 bytes

```
def f(s,p,w):t=len(s);q=len(p)-w;print[s,[p,s[:~q/2]+p+s[t+q/2:]][q<0]][t>w]

```

Tests are at **TryItOnline!**

*Note:* Places the extra character for odd splits on the right hand side
(question states that either is fine, although the examples show left only).
> 1 votes

# Answer
# JavaScript ES6, 103 99 bytes

```
(a,b,c,d=a.length,e=c.length,f=(b>e?b:e)-e,g=a.split(""),h=g.splice(-~f/2,d-f,c))=>b<d?g.join(""):a

```

```
f=(a,b,c,d=a.length,e=c.length,f=(b>e?b:e)-e,g=a.split(""),h=g.splice(-~f/2,d-f,c))=>b<d?g.join(""):a;

console.log(f("dngxmebwenfrbidonses", 19, " (...) "));
```
> 0 votes

# Answer
# Mathematica, 90 bytes

```
If[(l=Length)[i=#2]<=#,#2,If[#<=(s=l@#3),#3,Join[(t=i~Take~Floor[#/2]&)[#-s],#3,t[s-#]]]]&

```

Unnamed function taking an integer (the width) as its first argument and two lists of characters (the string and the separator) as its second/third arguments, and returning a list of characters.
> 0 votes

---
Tags: code-golf, string
---


title: Inverse Pi function

text:
# Question
Title: Inverse Pi function
The Pi function is an extension of the factorial over the reals (or even complex numbers). For integers *n*, *Π(n) = n!*, but to get a definition over the reals we define it using an integral:

In this challenge we will invert the *Π* function.

Given a real number *z ≥ 1*, find positive *x* such that *Π(x) = z*. Your answer must be accurate for at least 5 decimal digits.

---

Examples:

```
120 -> 5.0000
10 -> 3.39008
3.14 -> 2.44815
2017 -> 6.53847
1.5 -> 1.66277

```

# Answer
> 8 votes
# Mathematica, ~~17~~ ~~15~~ 27 bytes

```
FindInstance[#==x!&&x>0,x]&

```

Output looks like `{{x -> n}}`, where `n` is the solution, which may not be allowed.

# Answer
> 7 votes
# Pyth, 4 bytes

```
.I.!

```

A program that takes input of a number and prints the result.

Test suite

**How it works**

```
.I.!    Program. Input: Q
.I.!GQ  Implicit variable fill
.I      Find x such that:
  .!G    gamma(x+1)
     Q   == Q
        Implicitly print

```

# Answer
> 5 votes
# MATL, 13 bytes

```
1`1e-5+tQYgG<

```

This uses linear seach in steps of `1e-5` starting at `1`. So it is terribly slow, and times out in the online compiler.

To test it, the following link replaces the `1e-5` accuracy requirement by `1e-2`. Try it online!

### Explanation

```
1        % Push 1 (initial value)
`        % Do...while
  1e-5   %   Push 1e-5
  +      %   Add
  t      %   Duplicate
  QYg    %   Pi function (increase by 1, apply gamma function)
  G<     %   Is it less than the input? If so: next iteration
         % End (implicit)
         % Display (implicit)

```

# Answer
> 3 votes
# GeoGebra, 25 bytes

```
NSolve[Gamma(x+1)=A1,x=1]

```

Entered in the CAS input, and expects input of a number in spreadsheet cell `A1`. Returns a one-element array of the form `{x = <result>}`.

Here is a gif of the execution:

**How it works**

`N`umerically`Solve` the following equation: `Gamma(x+1)=A1`, with starting value `x=1`.

# Answer
> 2 votes
# MATLAB, 59 bytes

```
@(x)fminsearch(@(t)(gamma(t+1)-x)^2,1,optimset('TolF',eps))

```

This is an anonymous function that finds the minimizer of the squared difference betweeen the Pi function and its input, starting at `1`, with very small tolerance (given by `eps`) to achieve the desired precision.

Test cases (run on Matlab R2015b):

```
>> @(x)fminsearch(@(t)(gamma(t+1)-x)^2,1,optimset('TolF',eps))
ans =
    @(x)fminsearch(@(t)(gamma(t+1)-x)^2,1,optimset('TolF',eps))
>> f = ans; format long; f(120), f(10), f(3.14), f(2017)
ans =
   5.000000000000008
ans =
   3.390077650547032
ans =
   2.448151165246967
ans =
   6.538472664321318

```

You could try it online in Octave, but unfortunately some of the results lack the required precision.

# Answer
> 2 votes
# J, ~~86~~ 33 bytes

```
((]-(-~^.@!)%[:^.@!D.1])^:_>:)@^.

```

Uses Newton's method with log Pi to avoid overflow.

This is the previous version that computes log Gamma using Stirling's approximation. The step size (1e3) and number of terms in log Gamma (3) can be increased for possibly higher accuracy at the cost of performance.

```
3 :'(-(k-~g)%%&1e3(g=:((%~12 _360 1260 p.&:%*:)+-+^~-&^.%:@%&2p1)@>:)D:1])^:_>:k=:^.y'

```

Another version that computes the coefficient terms on the fly

```
3 :'(-((-^.y)+g)%%&1e3(g=:((%~(((%1-^@-)t:%]*<:)+:>:i.3)p.%@*:)+(*^.)-]+-:@^.@%&2p1)@>:)D:1])^:_>:^.y'

```

Try it online! and to see the terms converge.

## Explanation

```
((]-(-~^.@!)%[:^.@!D.1])^:_>:)@^.  Input: float y
(                            )@^.  Operate on log(y)
                           >:        Increment, the initial guess is log(y)+1
 (                     )^:_          Repeat until convergence starting with x = log(y)+1
                      ]                Get x
               ^.@!                    The log Pi verb
             [:    D.1                 Approximate its first derivative at x
       ^.@!                            Apply log Pi to x
     -~                                Subtract log(y) from it
            %                          Divide it by the derivative
  ]-                                   Subtract it from x and use as next value of x

```

# Answer
> 2 votes
# Mathematica, 21 bytes

```
FindRoot[#-x!,{x,1}]&

```

`FindRoot` applies Newton's method internally when there is an initial value.

The two methods below apply Newton's method directly.

### Alternative using FixedPoint 45 bytes

```
FixedPoint[#-(#!-y)/Gamma'[#+1]&,Log[y=#]+1]&

```

A more precise implementation of Newton's method for solving this since Mathematica can compute the derivative directly instead of approximating it.

Using rules to replace repeatedly would be shorter, but there is a limit (65536) to how many iterations it can perform that might be hit whereas `FixedPoint` does not have a limit.

### Alternative using rules, 38 bytes

```
Log[y=#]+1//.x_->x-(x!-y)/Gamma'[x+1]&

```

# Answer
> 1 votes
# Jelly, 34 bytes

```
Ḋ!Æl_®
ȷİ‘×;µ!ÆlI÷I÷@Ç_@ḊḢ
Æl©‘ÇÐĿ

```

Try it online! or View the intermediate values as they converge.

An implementation of J's combination of Newton's method and derivative approximation (secant method) to compute the inverse of *Π*(*n*).

It solves for the inverse of log(*Π*(*n*)) instead in order to avoid overflow.

It starts with an initial guess *x*0 = *y*+1 where *y* = log(*Π*(*n*)). Then it iterates until convergence using *x**n*+1 = *x**n* \- (log(*Π*(*x**n*)) - *y*) / (log((*Π*(1.001 * *x**n*)) - log(*Π*(*x**n*))) / (0.001 * *x**n*)).

# Answer
> 1 votes
## PARI/GP, 30 bytes

```
x->solve(t=1,x+1,gamma(t+1)-x)

```

Finds solution between `1` and`x+1`. Unfortunately, `x` is not big enough as upper bound for input like `1.5`.

# Answer
> 1 votes
## Mathematica, 26 Bytes

Yet another Mathematica solution!

Equation solving can always be turned into a minimization problem.

```
NArgMin[{(#-x!)^2,x>0},x]&

```

Finds the argument that minimizes the difference between the left and right sides of the equation.

Using NArgMin rather than NMinimize forces the output to just be the desired result rather than the usual verbose rule-based output (and it saves a byte!)

# Answer
> 0 votes
# C with libm, 111

**Update** \- fixed for input 1.5.

```
f(double *z){double u=2**z,l=0,g=u,p=0;for(;log(fabs(g-p))>-14;)p=g,g=(u+l)/2,u=tgamma(g+1)>*z?g:(l=g,u);*z=g;}

```

`gamma(x+1)` is a monotonically increasing function over the range in question, shis is just a binary search until the difference between successive values is small. The starting lower bound is `0` and the starting upper bound is `2*x`.

Input and output is via a pointer to a double passed to the function.

I'm pretty sure this can be golfed deeper - in particular I don't think I need 4 local doubles, but so far I'm not seeing an easy way to reduce this.

Try it online \- Builds (linking with libm) and runs in a bash script.

Mildly ungolfed:

```
f(double *z){
    double u=2**z,l=0,g=u,p=0;
    for(;log(fabs(g-p))>-14;){
        p=g;
        g=(u+l)/2;
        u=tgamma(g+1)>*z?g:(l=g,u);*z=g;
    }
}

```

---
Tags: code-golf, math
---


title: Detect Failing Castles

text:
# Question
Title: Detect Failing Castles
One of the interesting aspects of gravity is that, as far as I'm aware, you can't just have stuff floating in midair.

However, it seems not everyone at the Association of Random Castle Builders is aware of this fact, leading to castles such as this one:

                      #
                      #
    #  #      #  #   ###
    ####      ####   # #
    #### #  # ####   ###
    ##############   ###
    ######  ######   ###
    #####    #####   ###
                     ###
``````````````````````````````

and this one:

                                       # # #    # # #
                                       ##############
                                       ###  ####  ###
    #  #      #  #      #  #      #  # ###  ####  ### #  #      #  #      #  #      #  #
    ####      ####      ####      #### ############## ####      ####      ####      ####
    #### #  # #### #  # #### #  # #### ## ######## ## #### #  # #### #  # #### #  # ####
    ####################################################################################
    ######  ########  ########  ########  ########  ########  ########  ########  ######
    ###################################    ######    ###################################
    ###################################    ######    ###################################
                                       ##
                                         ##
                                           ##
                                             ##
                                               ##
````````````````````````````````````````````````````````````````````````````````````````````

and even this one:

       ##########
   ####   #      ###
#######################
            #
              #
                #
                  #
                    #  # # #
                  #   #  ###
                   #   # ###
                # # #  #  ##
                # # ##   ###
                 #  #  #####
                   #   #####
                  # #  #####
                       #####
                       ## ##
                       #####
                       #####
                       ## ##
                       ## ##
````````````````````````````````````````````

# Challenge

For a valid castle, all blocks will be connected to the ground either directly or indirectly. Your program or function will be given a castle such as the ones above as input, and your program must return a truthy or falsy value reflecting whether the castle is valid or not.

## Rules

* Input is given as a string.
* All valid castles rest on a surface, ``````````. (If the input string does *not* contain a surface, the castle is invalid.)
* You can assume all input will satisfy these criteria:
    + The surface will always be flat.
    + The surface will always be at least as wide as the castle, so there will be no blocks to the left or right of the ground.
    + The input will never have `#` below the surface.
    + Input will only contain characters given in this challenge. (`#`, ```, space or newline.)
    + You may assume the input will always contain at least one character.
* Blocks are connected if they are either horizontally or vertically adjacent. Diagonal does not count!
    + Connected:
    ```
    #	or	##
    #
    ```
    + Not connected:
    ```
    #      or	# #	or	 #
                      		#
    #
    ```
* Castles must exist to be valid. (In other words, inputs without any `#` must give a falsy value.)
* Input will only contain characters given in this challenge. (`#`, ```, space or newline.)
* You may assume the input will always contain at least one character.
* Standard I/O and loophole rules apply.

## Test cases

### Falsy

* All the examples given above.
* ```
#  #      #  #
####      ####
#### #  # ####
##############
######  ######
#####    #####
```
(No ground.)
* <pre><code>#
 ###      ####
#### #  # ####
##############
######  ######
#####    #####
``````````````</code></pre>
(Topmost block is not connected either horizontally or vertically.)
* <pre><code>
```

(No castle.)
*

                                     # # #    # # #
                                     ##############
                                     ##### ## #####
  #  #      #  #      #  #      #  # #### #  # #### #  #      #  #      #  #      #  #
  ####      ####      ####      ####  ##  ####  ##  ####      ####      ####      ####
  #### #  # #### #  # #### #  # #### #  # #### #  # #### #  # #### #  # #### #  # ####
  ####################################################################################
  ######  ########  ########  ########  ########  ########  ########  ########  ######
  ###################################    ######    ###################################
  ###################################    ######    ###################################
````````````````````````````````````````````````````````````````````````````````````````</code></pre>
(Central tower isn't connected to the rest of the castle because there are no horizontally or vertically adjacent blocks connecting it.)
* ```

```
(No castle.)
* ```

```
(No castle, just a single newline character.)
* <pre><code># #
#
```````</code></pre>
(Rightmost block is not connected either horizontally or vertically.)
* <pre><code>
```

(No castle.)

### Truthy

* ```
#
`
```
*
#  #      #  #
####      ####
#### #  # ####
##############
######  ######
#####    #####
``````````````

*
                      #
                      #
    #  #      #  #   ###
    ####      ####   # #
    #### #  # ####   ###
    ##############   ###
    ######  ######   ###
    #####    #####   ###
    #####    #####   ###
``````````````````````````````

*
                                       # # #    # # #
                                       ##############
                                       ###  ####  ###
    #  #      #  #      #  #      #  # ###  ####  ### #  #      #  #      #  #      #  #
    ####      ####      ####      #### ############## ####      ####      ####      ####
    #### #  # #### #  # #### #  # #### ## ######## ## #### #  # #### #  # #### #  # ####
    ####################################################################################
    ######  ########  ########  ########  ########  ########  ########  ########  ######
    ###################################    ######    ###################################
    ###################################    ######    ###################################
````````````````````````````````````````````````````````````````````````````````````````````

*
                      ####  ###
                      #  #### ###
                      #         ###
                      #           ##
                      #
                     ###
                    #####
                   #######
                  #########
                 ##### #####
                #####   #####
               ######   ######
              #################
              # ############# #
                #############
                #############
                #############
                ###### ######
                ###### ######
                #############
                #############
                #############
                #############
                ###### ######
                ###### ######
                #############
                #############
                #############
                #############
                ###### ######
                ###### ######
                #############
                #############
                #############
                #############
                #############
                #####   #####
                #####   #####
                #####   #####
            `````````````````````
                                    </code></pre>
* <pre><code>
                                          ####
                                         #####
                                        ######
                                         ####
                                         ####
                                        #####
                                       ########
                                      ##########
                                      ##########
                                     ###########
                                    ############
                                  ##############
   #####                       ################
  ###########                #################
  ###########################################
   ########################################
    #####################################
     ##################################
        ############################
            ###################
``````````````````````````````````````````````````</code></pre>

Good luck!

# Answer
## Snails, ~~21~~ 18 bytes

-3 bytes due to additional input constraints edited into challenge.

```
!{t=\#!(\#o`+\`}\#

```

Unfortunately the time complexity is factorial, so most of the inputs aren't runnable.

Outputs 0 for falsy cases, and the number of `#` for truthy cases.

```
                 ,,
!{ t             ,, Assert that nowhere in the grid,
    =\#          ,, there is a '#'
    !(           ,, such that there does not exist
        (\# o)+  ,, an orthogonally connected path of '#'
        \`       ,, ending at a '`'
    )            ,,
}                ,,
\#               ,, Match '#' at starting position

```
> 12 votes

# Answer
# Octave, ~~53~~ 51 bytes

```
@(s)([~,n]=bwlabel(s>32,4))|n==1&&nnz(diff(+s)==61)

```

Try It Online!

\*Since op dropped requirement to check for empty input answer reverted to my first edit.

Explanation:

```
nnz(s)                       check for empty input
([~,n]=bwlabel(s~=' ',4))    label nonempty regions and count number of labels

n==1                         check if number of labels is 1.

nnz(diff(+s)==61)            check if blocks connected to the surface

```
> 9 votes

# Answer
## Grime, 29 bytes

```
C=\`|\#&<0C>oX
e`\#&C!v#!&\##

```

Try it online! Most test cases time out on TIO. Replace the `<0C>` with `<0CoF>` to make it a little faster.

## Explanation

I'm checking that from every `#` there exists a path to a ```, and that there exists at least one `#`. I recently added rotation commands to Grime, which make this challenge much easier.

```
C=\`|\#&<0C>oX  First line:
C=               Define nonterminal C as
  \`             the literal `
    |            or
     \#          the literal #
       &<  >     which is contained in a larger rectangle
         0C      containing said literal adjacent to a match of C
            oX   rotated by any multiple of 90 degrees.
e`\#&C!v#!&\##  Second line:
e`               Match entire input against this pattern:
         !       does not
       v#        contain
  \#             the literal #
    &C!          which is not a match of C,
          &      and
             #   contains
           \#    the literal #.

```
> 7 votes

# Answer
## JavaScript (ES6), ~~197~~ 196 bytes

```
f=(s,l=Math.max(...s.split`\n`.map(t=>t.length)),t=s.replace(/^.*/g,t=>t+' '.repeat(l-t.length)),u=t.replace(eval('/(#|`)([^]{'+l+'})?(?!\\1)[#`]/g'),'`$2`'))=>t==u?/#/.test(s)>/#/.test(t):f(s,l,u)

```

Where `\n` represents the literal newline character. Tries to remove all `#`s one at a time by finding one adjacent to a ``` and changing it to a ```. Returns `true` if there was at least one `#` originally but there were all removed. Version that requires padded input for ~~118~~ 117 bytes:

```
f=(s,t=s,u=t.replace(eval('/(#|`)([^]{'+s.search`\n`+'})?(?!\\1)[#`]/'),'`$2`'))=>t==u?/#/.test(s)>/#/.test(t):f(s,u)

```
> 6 votes

# Answer
# Perl 6, 180 bytes

```
{?/\#/&&?all map ->\c{my \b=[map {[$^a.comb]},.lines];sub f(\y,\x){with b[y;x] ->$_ {b[y;x]=0;/\#/??f(y+(1|-1),x)|f(y,x+(1|-1))!!/\`/??1!!|()}}(|c)},map {|($++X ^$^a.comb)},.lines}

```

Checks if the input contains at least one `#`, and if every `#` can find a path to a ```.

Rather inefficient, because the pathfinding is brute-forced using a recursive function that always visits all other `#` of the same connected region (i.e. doesn't short-circuit).

Uses some unholy interaction between Junction operators and slipping, to ensure that the path test is skipped for space characters without requiring a separate check for that outside of the pathfinding function.
> 5 votes

# Answer
# Python 3, ~~214~~ 206 bytes

```
def f(s):
 C=s.split('\n');n=max(map(len,C));o=[''];C=[*''.join(t.ljust(n)for t in C+o)]
 while C>o:o=C;C=['`'if z>' 'and'`'in{C[i+y]for y in(1,-1,n,-n)}else z for i,z in enumerate(C)]
 return'#'in{*s}-{*C}

```

Try it online!

The first line here is devoted to padding all the lines to the same length: we split the string (`s.split('\n')` is one char shorter than `s.splitlines()`), find the maximum length of a line, and assign to C a flattened list of all the characters after padding each line. (The newlines are gone.)

Then we make a list where each non-space character adjacent to at least one backtick is replaced by a backtick, and continue until no change happened (when the old list `o` is equal to `C`. We can compare with `C>o` instead of `C!=o` because replacing # (ASCII 35) with \` (ASCII 96) can only increase the list's lexicographical ordering.)

If no # remains, and at least one was present initially, the castle is valid.

* Saved eight bytes checking for # in the set difference, rather than `'#'in s and'#'not in C`
> 5 votes

---
Tags: code-golf, ascii-art, decision-problem
---


# Question
Title: Automate your first grade counting exercise
# CodeGolf Challenge

PWSSHHHH! You wake up in a cryogenics lab in the year 3000. Upon being escorted to the assignment office to receive your career chip, presumably that of a delivery boy, a probe detects that you are from the year 2000. Because of this, and a few stereotypes, you are assumed stupid compared to *today's* modern human and are forced to repeat gradeschool.

You enter your first grade classroom and the teacher is giving an assignment. She will say or write a number up to 50. If she writes the number on the board (for example: 25) then you have to say the numbers up to that number "one, two, three, ..., twenty-five". If she says the number out loud (for example: "six") then, on your tablet, you have to write the numbers up to that number "1, 2, 3, 4, 5, 6"

This becomes very tedious and you decide you will automate the process with your still functioning, yet archaic, 21st century programming knowledge.

---

# Objective:

Your program should take an input. This input will either be a decimal number (`1 thru 50`) or a written-out number (`one thru fifty`).

•If the input is a decimal number, your output should count from one to said number, using written-out style. (e.g. *thirty-two*)

•If the input is a written-out number, your output should count from 1 to said number, using decimal style. (e.g. *32*)

---

# Rules:

Input and Output can be in any case of your choosing (so you can make a program that only accepts upper-case if desired).

Input decimal numbers do not have to be of a number type (e.g. int), they can be a input string containing numbers (25 vs "25"). Either are fine and you can chose which one you want your program to accept. (Your program does not need to accept both)

Written out style does NOT require a hyphen between compound words, but you can if desired.

Output values have to be separated in some form, any separator is fine `1,2,3` `1 2 3` `etc`

You can not add extra libraries like num2words (python) etc (However system libraries are fine)

Even though the back-story says you are from the year 2000, you can use languages created after that date (lol)

---

This is , so the program with the shortest bytecount wins!

# Answer
# Perl 6, ~~119~~ 113 bytes

```
{my \n=<① ⑳ ㉑ ㉟ ㊱ ㊿>.map:{|map *.uniname.words[2..*].join,$^a..$^b}
/\d/??n[^$_]!!1..1+first $_,n,:k}

```

Unicode database FTW!

Uses upper-case written-out numbers without hypen, e.g. `TWENTYTWO`.
Returns a list of strings, or a range of numbers. (Both use space as separator when printed with `put`.)
> 31 votes

# Answer
# Python3, ~~276~~ ~~271~~ ~~269~~ ~~243~~ ~~237~~ ~~235~~ ~~232~~ 217 bytes

Taking a cue from the @smls perl submission...

```
from unicodedata import*
o=[name(chr(k)).split(' ',2)[-1]for j in['①⑴','㉑㉠','㊱㋀']for k in range(ord(j[0]),ord(j[1]))]
i=input()
w=i in o
for i in range(w and o.index(i)+1or int(i)):print(w and i+1or o[i])

```

I suspect it might be golfed a little bit further.

It makes use of the system library `unicodedata` to look up names for numbers. It requires upper case number names (separated by space: `FORTY TWO`) or decimal integers as input.

(This is my first code golf submission.)

(I also just noticed I was miscounting the length (encoding), so it's a few bytes less than previously thought. I've only updated the most recent byte count, though. Oops.)
> 13 votes

# Answer
## Common Lisp, ~~297~~ ~~253~~ ~~243~~ ~~242~~ ~~144~~ 128

```
(lambda(s)(#1=dotimes(u(or(#1#(i 51)(if(equal(#2=format()"~R"i)s)(return i)))s))(#2#t"~[~:;, ~]~:[~R~;~D~]"u(stringp s)(1+ u))))

```

### Details

```
(lambda (s)
  (dotimes                         ; iterate...
      (u                           ; for u from zero below ...
       (or                         ; if s is a string, then
        (dotimes (i 51)            ;   parse s by iterating from 0 to 50
          (if (equal               ;   until we find a match between
               (format nil "~R" i) ;   the English word(s) for i
               s)                  ;   and the given s
              (return i)))         ;   (exit loop)
        s))                        ; otherwise, use s, which is a number
    (format t                      ; for each U, print to standard output
            "~[~:;, ~]~:[~R~;~D~]" ; (see below for details)
            u                      ; ...
            (stringp s)            ; ... arguments to format
            (1+ u))))              ; ...

```
* `~[ 0 ~; 1 ~; ... ~:; else ~]` is a switch, based on the next available argument's value, which jumps to the appropriate sub-control format. Here, I only have a case of "0" and for "else". This is used to insert a separator before each number except the first one, thanks to U starting from zero.
* `~:[ FALSE ~; TRUE ~]` is a conditional format; here we output things differently whether the input s is a string or not.
* `~R` write a number as a cardinal English number, whereas `~D` simply prints the number.

### Examples

```
CL-USER> (test "five")
1, 2, 3, 4, 5

CL-USER> (test 32)
one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen, twenty, twenty-one, twenty-two, twenty-three, twenty-four, twenty-five, twenty-six, twenty-seven, twenty-eight, twenty-nine, thirty, thirty-one, thirty-two

```
> 10 votes

# Answer
# JavaScript ES6, 559 526 381 368 364 358 332 327 315 bytes

```
a="one0two0three0four0five0six0seven0eight0nine0ten0eleven0twelve0thir10four10fif10six10seven10eigh10nine1".replace(/1/g,'teen').split(0),b="twenty0thirty0forty0fifty".split(0),c=(n,d=Array,e=b.forEach(i=>a=a.concat(i,a.slice(0,9).map(x=>i+x))))=>1/n?a.slice(0,n).join():d.from(d(a.indexOf(n)+1),(x,i)=>i+1).join();

```

Thanks to Kritixi Lithos for the idea of splitting the array and Arnauld for the 1/n trick.

```
a="one0two0three0four0five0six0seven0eight0nine0ten0eleven0twelve0thir10four10fif10six10seven10eigh10nine1".replace(/1/g,'teen').split(0),b="twenty0thirty0forty0fifty".split(0),c=(n,d=Array,e=b.forEach(i=>a=a.concat(i,a.slice(0,9).map(x=>i+x))))=>1/n?a.slice(0,n).join():d.from(d(a.indexOf(n)+1),(x,i)=>i+1).join();

console.log(c("twentyfive"));
console.log(c("fifty"));
console.log(c(50));
```
> 8 votes

# Answer
# PHP - ~~397~~ ~~372~~ ~~349~~ ~~344~~ 329 bytes

Inspired by TomDevs's JS solution

*Saved 25 bytes by replacing `$a=[...]` by `$a=explode(...)`*

*Saved another 23 bytes by switching back to an array without string delimiters and by storing `teen` in a variable, thanks to @user59178*

*Saved another 5 bytes by removing the `(int)` typecasting*

*Saved another 15 bytes by dropping `$b`, the `$i` in the `for` declarations, and the curly braces, thanks to @user59178 again*

```
$a=[one,two,three,four,five,six,seven,eight,nine,ten,eleven,twelve,thir.$t=teen,four.$t,fif.$t,six.$t,seven.$t,eigh.$t,nine.$t];foreach([twenty,thirty,forty,fifty] as$c){$a[]=$c;for($i=0;$i<9;)$a[]=$c.'-'.$a[$i++];}if($argv[1]!=0)for($i=0;$i<$argv[1];)echo$a[$i++].' ';else for($i=1;$i<=array_search($argv[1],$a)+1;)echo$i++.' ';

```

**Ungolfed :**

```
$a =[one,two,three,four,five,six,seven,eight,nine,ten,eleven,twelve,thir.$t=teen,four.$t,fif.$t,six.$t,seven.$t,eigh.$t,nine.$t];
foreach ([twenty,thirty,forty,fifty] as $c){
    $a[] = $c;
    for ($i=0;$i<9;)
        $a[] = $c . '-' . $a[$i++];
}
if( $argv[1] !=0 )
    for ($i=0;$i<$argv[1];)
        echo $a[$i++] . ' ';
else
    for ($i=1;$i<=array_search($argv[1], $a)+1;)
        echo $i++ . ' ';

```

Try it for an input string or for an input number
> 6 votes

# Answer
# Scheme, ~~161~~, ~~152~~, 149

```
(define (c x)(let((r(string->number x)))(let l((i 1))(let((n (format #f "~r" i)))(display(if r n i))(newline)(or(eq? r i)(equal? x n)(l (+ i 1)))))))

```

Uncompressed:

```
(define (count limit)
  (let ((numerical-limit (string->number limit)))
    (let l ((i 1))
      (let ((current-number (format #f "~r" i)))
        (display (if numerical-limit current-number i))
        (newline)
        (or (eq? numerical-limit i)
            (equal? limit current-number)
            (l (+ i 1)))))))

```
> 6 votes

# Answer
# Python 2, ~~503~~ ~~499~~ ~~494~~ ~~490~~ 479 bytes

-5 with thanks to @JonathanAllan

```
l='one two three four five six seven eight nine ten eleven twelve thir#four#fif#six#seven#eigh#nine#'.replace('#','teen ').split()
m='twenty','thirty','forty','fifty'
i,z,R=raw_input(),' ',range
try:n=int(i);p=(n/10)-2;o=(l+sum([[m[x]]+[m[x]+z+l[y]for y in R(9)]for x in R(p)],[])+[m[p]]+[m[p]+z+l[y]for y in R(n%10)],l[:n])[n<20]
except:j=i.split();o=map(str,R(1,(m.index(j[0])+2)*10+l.index(j[1])+2if z in i else l.index(i)+2if i in l else(m.index(i)+2)*10+1))
print','.join(o)

```

Try it online!

Input either a number or a space seperated spelling of a number.

Slightly less golfed and more readable version:

```
l='one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen'.split()
m='twenty','thirty','forty','fifty'
i=raw_input()
try:
 n=int(i)
 if n<20:
  o=l[0:n]
 else:
  o=l
  for x in range((n/10)-2):
   o+=[m[x]]+[m[x]+' '+l[y]for y in' '*9]
  p=m[(n/10)-2]
  o+=[p]+[p+' '+l[y]for y in' '*n%10]
except:
 if' 'in i:
  t=i.split()
  s=((m.index(t[0])+2)*10)+l.index(t[1])+2
 else:
  s=l.index(i)+2 if i in l else((m.index(i)+2)*10)+1
 r=range(1,s)
 o=map(str,r)
print','.join(o)

```
> 6 votes

# Answer
# Python 2, 262 bytes

```
x="one two three four five six seven eight nine ten eleven twelve thir#four#fif#six#seven#eigh#nine#".replace("#","teen ").split()
x+=[a+"ty"+b for a in"twen","thir","for","fif"for b in['']+x[:9]]
v=input()
for s in range(1,x.index(v)+2)if v>50else x[:v]:print s

```

**repl.it**

Input and output strings are lower case and concatenated\*, so to test a string input enter, for example, `"thirtyfive"` at the prompt.

Builds the list of all the words (plus `"fiftyone"` to `"fiftynine"`), `x`, then tests if `input` is a word with the proxy `v>50` (strings are greater than numbers in Python 2, and all the numbers in the valid input range from the specification are `<=50`) and `print`s the appropriate values by either slicing the list, `x[:v]`, or building a range of integers, `range(1,x.index(v)+2)`.

* Adding hyphenation on both costs 11 bytes, by replacing `a+"ty"b` with `a+"ty"+'-'*(b>'')+b`.
> 6 votes

# Answer
# JavaScript (ES6), 261 bytes

Note: the string assigned to z is encoded with `atob`. In the encoded string there are 11 bytes that I can not post to this site, even if they are valid characters in a javascript string. So I used an hex escape in the form \xHH. Each one of these escapes is counted as 1 byte.
The original uncompressed string is the *less golfed* version.

```
x=>(z=btoa('ö\x89ÞöÜ(öØkyï_¢êý~+ÞöÈ±öÇ¯z\x7f^\x8a\x08möx§{Û^\x9f×¥z÷§öÜ\x1e\x96÷½¶\x18«÷×â\x7fß}z(!÷Ûpz\x7f}~\x8aý').split(9),o=(0+z.map((v,i)=>i<20?i<13?v:(v||z[i-10])+'teen':z.slice(0,10).map(d=>(z[i]||z[i-8]||z[i-18])+'ty'+d))).split`,`,p=o.indexOf(x),o.slice(1,-~x+p+!~p).map((x,i)=>~p?i+1:x))

```

*Less golfed*

```
x => (
  z = '9one9two9three9four9five9six9seven9eight9nine9ten9eleven9twelve9thir99fif999eigh99twen99for9'
      .split(9),
  o = (0 + // 0 + array to build a comma separated string
       z.map( (v, i) =>
         i < 20
         ? i < 13
           ? v // 1 to 13 are 'as is'
           : (v||z[i-10])+'teen' // compose for 14 to 19
         : z.slice(0,10).map(d=>(v||z[i-8]||z[i-18])+'ty'+d)) // 20s, 30s, 40s, 50s
      ).split`,`, // from comma separated to array again
  // o contains strings from one to fiftynine
  p = o.indexOf(x), // look for input
  o.slice(1, -~x+p+!~p).map((x,i) => ~p?i+1:x)
)

```

**Test**

```
F=
x=>(z=btoa('ö\x89ÞöÜ(öØkyï_¢êý~+ÞöÈ±öÇ¯z\x7f^\x8a\x08möx§{Û^\x9f×¥z÷§öÜ\x1e\x96÷½¶\x18«÷×â\x7fß}z(!÷Ûpz\x7f}~\x8aý').split(9),o=(0+z.map((v,i)=>i<20?i<13?v:(v||z[i-10])+'teen':z.slice(0,10).map(d=>(v||z[i-8]||z[i-18])+'ty'+d))).split`,`,p=o.indexOf(x),o.slice(1,-~x+p+!~p).map((x,i)=>~p?i+1:x))

function update() {
  var i=I.value
  O.textContent = F(i)
}

update()
```

```
<input id=I value=25 oninput='update()'><pre id=O></pre>
```
> 5 votes

# Answer
## Python 2, ~~432 422 416~~ 403 bytes

I'm sure this can be improved on. At the very least if I can get away with hardcoding the value to be worked on and not needing a function I can save 20. It needs a space to separate words in text input. Saved 6 bytes thanks to JonathanAllan's comment on ElPedro's answer, 4 for rearranging maths.

```
def z(f):
 a,b,i,d="one two three four five six seven eight nine ten eleven twelve thir#four#fif#six#seven#eigh#nine#".replace("#","teen ").split()+[""],"twenty thirty forty fifty".split(),1,f>50
 if d:f=f.split();f=a.index(f[-1])+21+b.index(f[-2])*10 if len(f)>1 else b.index(f[-1])*10+20 if f[-1]in b else a.index(f[-1])+1
 while i<=f:s=i if d else a[i-1]if i<20 else b[i//10-2]+a[i%10-1];print s;i+=1

```

(NB: The actual version of this uses tabs to indent instead of spaces. QPaysTaxes added a single space because that wasn't rendering properly, to ensure that the given code compiles. It shouldn't change the byte count.)
> 5 votes

# Answer
# Python 3, ~~305~~ 303 bytes

Converted to Python 3 after advice from @nedla2004. Now also has no space between written numbers on input or output e.g. enter twentytwo

```
l='one two three four five six seven eight nine ten eleven twelve thir#four#fif#six#seven#eigh#nine#'.replace('#','teen ').split()
m='twenty','thirty','forty','fifty'
i,R=input(),range
l+=sum([[m[x]]+[m[x]+l[y]for y in R(9)]for x in R(3)],[])
for x in R(1,l.index(i)+2)if i in l else l[:int(i)]:print(x)

```

Try it online 3!

# Python 2, ~~327~~ ~~320~~ ~~313~~ 308 bytes

```
l='one two three four five six seven eight nine ten eleven twelve thir#four#fif#six#seven#eigh#nine#'.replace('#','teen ').split()
m='twenty','thirty','forty'
i,R=raw_input(),range
l+=sum([[m[x]]+[m[x]+l[y]for y in R(9)]for x in R(3)],[])+['fifty']
for x in R(1,l.index(i)+2)if i in l else l[:int(i)]:print x

```

Try it online 2!

~~163~~ ~~170~~ 177 bytes shorter than my original answer so I am posting it as an alternative. This uses `for` on the two lists to build up a complete list of all of the string representations of the numbers then identifies the right one in the list and prints everything up to it either by value or by index. Outputs a new line for each value.
> 5 votes

# Answer
# Wolfram Language, 92 bytes

```
If[NumberQ@#, Do[Print@IntegerName@i, {i, #}],
  Do[Print@i, {i, Interpreter["SemanticNumber"]@#}]] &

```

(I'm new to this, let me know if I did something wrong)
> 5 votes

# Answer
# C++11, ~~484~~ ~~480~~ 477 bytes

```
#import<iostream>
#import<cstdlib>
#import<vector>
using namespace std;f(){int j,i=2;string s="teen";vector<string>v={"","one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve"};for(;i++<9;)v.push_back(v[i]+s);v[13]="thir"+s;v[15]="fif"+s;v[18]="eigh"+s;for(i=19;i++<50;){string n[4]={"twenty","thirty","forty","fifty"};v.push_back(n[i/10-2]+v[i%10]);}cin>>s;if(i=atoi(s.c_str()))for(j=0;j++<i;)cout<<v[j]<<" ";else while(v[i++]!=s)cout<<i<<" ";}

```

Text input in lower-case without hyphens.
> 4 votes

# Answer
# PowerShell, 362 bytes

```
$z=0..50|%{("0twenty0thirty0forty0fifty"-split0)[+(($b="$_"[0])-gt49)*($_-gt19)*(+"$b"-1)]+($x=(("0one0two0three0four0five0six0seven0eight0nine0ten0eleven0twelve"-split0)+(-split'thir four fif six seven eigh nine'|%{$_+'teen'})))[($_%10)*($_-gt19)]+$x[$_*($_-le19)]}
if(($n=-split$args)[0][0]-in48..57){$z[$n[0]..$n[2]]}else{$z.IndexOf($n[0])..$z.IndexOf($n[2])}

```

Try it online! words input or numbers input

This is a right mess, and I'm not terribly happy with it, but here it is. Golfing suggestions welcome.

The first line sets `$z` to be an array of the full English words. You can see the `-split0` for numbers `1` to `12`, and the loop to construct all the `teen`s, and then there's a bunch of logic to put everything together right. Try it online!

The second line starts with some logic. We take the input `$args` (as a string), `-split` it on whitespace, store it into `$n` for use later, take the first `[0]` word, and the first `[0]` character of that, and check if it is `-in` a range `48..57` (i.e., ASCII `0` to `9`). So, we're checking if we have decimal input or English input. Try it online!

In the first case, we build a range based on the decimal inputs `$n[0]..$n[2]` and use that to index into `$z[...]`. In the other case, we find the `.indexOf()` the first word and the last word, and build just a numerical range from that. In either situation, we now have an array of objects on the pipeline (either strings or integers), and an implicit `Write-Output` at program completion gives us a newline between elements.
> 3 votes

# Answer
## Swift3, 402 bytes

```
let f=["one","two","three","four","five","six","seven","eight","nine"]
let g=["twenty","thirty","forty","fifty"]
let v=[f,["ten","eleven","twelve"],["thir","four","fif","six","seven","eigh","nine"].map{$0+"teen"},[g[0]],f.map{g[0]+$0},[g[1]],f.map{g[1]+$0},[g[2]],f.map{g[2]+$0},[g[3]]].flatMap{$0}
func c(s:String){if let i=Int(s){print(v.prefix(upTo:i))}else{for j in 1...v.index(of:s)!+1{print(j)}}}

```

Ungolfed:

```
let f = ["one","two","three","four","five","six","seven","eight","nine"]
let g = ["twenty","thirty","forty","fifty"]

let values = [f,["ten","eleven","twelve"],["thir","four","fif","six","seven","eigh","nine"].map{$0+"teen"},
              [g[0]], f.map{g[0]+$0},
              [g[1]], f.map{g[1]+$0},
              [g[2]], f.map{g[2]+$0},
              [g[3]]].flatMap{$0}

func count(s:String){
    if let i = Int(s) {
        print(values.prefix(upTo: i))
    } else {
        for j in 1...values.index(of: s)!+1{
            print(j)
        }
    }
}

count(s:"29")
count(s:"twentyeight")

```

Nothing special here, just using an array to back up the written-out numbers.

I originally thought this solution using this other way to calculate the `values` array:

```
let values = f + ["eleven","twelve"]
    + ["thir","four","fif","six","seven","eigh","nine"].map{$0+"teen"}
    + [g[0]] + f.map{g[0]+$0}
    + [g[1]] + f.map{g[1]+$0}
    + [g[2]] + f.map{g[2]+$0}
    + [g[3]]

```

Which could be golfed to:

```
let v=f+["eleven","twelve"]+["thir","four","fif","six","seven","eigh","nine"].map{$0+"teen"}+[g[0]]+f.map{g[0]+$0}+[g[1]]+f.map{g[1]+$0}+[g[2]]+.map{g[2]+$0}+[g[3]]

```

replacing the 3rd line in the golfed code

I could have scored 381 bytes, but, there is a compiler error that says: "expression was too complex to be solved in reasonable time", more info on the error can be found here
> 3 votes

# Answer
## R, ~~452~~ ~~430~~ 424 bytes

```
o=c("","one","two","three","four","five","six","seven","eight","nine")
t=gsub(0,"teen",c("ten","eleven","twelve","thir0","four0","fif0","six0","seven0","eigh0","nine0"))
s=c("twenty","thirty","forty")
p=""
for(i in s){for(j in o){p=paste0(p,i,j," ")}}
as.data.frame(t(d<-1:50))
names(d)=c(o[-1],t,as.vector(strsplit(p," ")[[1]]),"fifty")
f=function(x){if(is.numeric(x)){names(d)[1:x]}else{matrix(d[1:d[x]],dimnames=NULL)}}

#> f(5)
#[1] "one"   "two"   "three" "four"  "five"

#> f('five')
#     [,1]
#[1,]    1
#[2,]    2
#[3,]    3
#[4,]    4
#[5,]    5

```

Places the numbers in a data.frame with written-out numbers as column names, making the translation between the two (and subsequent printing) pretty easy.

Main attempt at golfing was in creating the written-out numbers for 20-49, probably much more to golf here.

I made an attempt with `as.matrix` to print the data.frame with just the numbers, but am still left with a matrix header. Hopefully that's ok.

Ungolfed:

```
ones <- c("","one","two","three","four","five","six","seven","eight","nine")
teens <- c("ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen")
tens <- c("twenty","thirty","forty")

p=""
for(i in tens){
  for(j in ones){
    p=paste0(p, i, j," ")
  }
}

nums <- 1:50
as.data.frame(t(nums))
names(nums) <- c(ones[-1], teens, as.vector(strsplit(p, " ")[[1]]), "fifty")
f <- function(x){
  if(is.numeric(x)){
    names(nums)[1:x]
  } else {
    matrix(nums[1:nums[x]], dimnames = NULL)
  }
}

```
> 3 votes

# Answer
# C, 342 331 bytes

```
char*x[]={"teen","one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thir","four","fif","twenty","thirty","fourty","fifty"};void main(int z,char**i){for(z=1;z<=atoi(i[3]);z++)printf("%s%s%s\n",z<16?x[z]:z<20?z^18?x[z-10]:"eigh":x[z/10+14],z>20&&z%10?"-":z>12&&z<20?*x:"",z>20&&z%10?x[z%10]:"");}

```

Try it online!
> 2 votes

# Answer
## SAS, 179

```
%macro c(n);%let f=words.;%if%length(&n)>2%then%do;%do c=1%to 50;%if%qsysfunc(putn(&c,&f))=&n%then%let n=&c;%end;%let f=2.;%end;%do i=1%to &n;%put%sysfunc(putn(&i,&f));%end;%mend;

```

Output is written to the log separated by newlines. SAS has a built-in format for converting digits to words, which is a major advantage for this challenge, but annoyingly it lacks an informat for doing the reverse.
> 1 votes

---
Tags: code-golf, string, math, natural-language, logic
---


title: Morse Decode Golf

text:
# Question
Title: Morse Decode Golf
I've become alarmed with the growing hatred of spaces and this answer has inspired me to make sure Morse code is safe from this insidious removal of whitespace.

So, your task will be to create a program that can successfully translate Morse code with all of the spaces removed.

**Rules:**

1. Input will be a string consisting only of dashes and dots (ASCII 2D and 2E). Output is undefined for input containing any other characters. Feel free to use any method convenient to your language of choice to receive the input (stdin, text file, prompt user, whatever). You can assume that the Morse code input only consists of the letters A-Z, and matching numbers or punctuation is not required.
2. Output should include only words contained in this dictionary file (again, feel free to use any convenient method to access the dictionary file). All valid decodings should be output to stdout, and all dots and dashes in the input must be used. Each matched word in the output should be separated by a space, and each possible decoding should separated by a newline. You can use upper case, lower case, or mixed case output as convenient.
3. All restrictions on standard loopholes apply with one exception as noted above, you may access the dictionary file referenced in requirement 2 via an internet connection if you really want to. URL shortening is acceptable, I believe that goo.gl/46I35Z is likely the shortest.
4. This is code golf, shortest code wins.

**Note:** Posting the dictionary file on Pastebin changed all of the line endings to Windows style 0A 0E sequences. Your program can assume line endings with 0A only, 0E only or 0A 0E.

**Test Cases:**

Input:

> ......-...-..---.-----.-..-..-..

Output must contain:

> hello world

Input:

> .--..-.-----..-..-----..-.--..--...---..--...-.......--.-..-.-.----...--.---.-....-.

Output must contain:

> programming puzzles and code golf

Input:

> -.....--.-..-..-.-.-.--....-.---.---...-.----..-.---..---.--....---...-..-.-......-...---..-.---..-----.

Output must contain:

> the quick brown fox jumps over the lazy dog

# Answer
> 6 votes
## Ruby, 210

```
(1..(g=gets).size).map{|x|puts IO.read(?d).split.repeated_permutation(x).select{|p|p.join.gsub(/./,Hash[(?a..?z).zip"(;=/%513':07*)29@-+&,4.<>?".bytes.map{|b|('%b'%(b-35))[1,7].tr'01','.-'}])==g}.map{|r|r*' '}}

```

If there exists such a practice as "over-golfing", I suspect I have partaken this time around. This solution generates an array of arrays of repeated permutations of *all of the dictionary words*, from length 1 up to the length of the input. Given that "a" is the shortest word in the dictionary file and its code is two characters long, it would have been sufficient to generate permutations of length up to half the size of the input, but adding `/2` is tantamount to verbosity in this domain, so I refrained.

Once the permutation array has been generated (*NB*: it is of length 45404104 in the case of the pangrammatic example input), each permutation array is concatenated, and its alphabetic characters are replaced with their Morse code equivalents via the rather convenient `(Regexp, Hash)` variant of the `#gsub` method; we've found a valid decoding if this string is equal to the input.

The dictionary is read (several times) from a file named "d", and the input must not contain a newline.

**Example run** (with a dictionary that'll give the program a fighting chance at ending before the heat death of the universe):

```
$ cat d
puzzles
and
code
dummy
golf
programming
$ echo -n .--..-.-----..-..-----..-.--..--...---..--...-.......--.-..-.-.----...--.---.-....-. | ruby morse.rb
programming puzzles and code golf
^C

```

# Answer
> 5 votes
## Haskell, 296 characters

* Dictionary file: must be a text file named "d"
* Input: stdin, may have a trailing newline but no internal whitespace

```
main=do f<-readFile"d";getLine>>=mapM(putStrLn.unwords).(words f&)
i!""=[i]
(i:j)!(p:q)|i==p=j!q
_!_=[]
_&""=[[]]
d&i=do
w<-d
j<-i!(w>>=((replicate 97"X"++words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")!!).fromEnum)
n<-d&j
[w:n]

```

Explanation of elements:

* `main` reads the dictionary, reads stdin, executes `&`, and formats the output of `&` with appropriate whitespace.
* `(replicate 97"X"++words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..")!!)` (an expression inside of the definition of `&`) is a list whose indices are character codes (97 is the code of `'a'`) and values are Morse sequences.
* `!` (a function named as an infix operator) matches a string against a prefix; if the prefix is present it returns the remainder in a one-element list (success in the list monad), otherwise the empty list (failure in the list monad)
* `&` uses the list monad for “nondeterministic” execution; it

1. picks an entry of `d` (a dictionary word),
    2. uses `!` to match the Morse form of that word (`w>>=((…)!!).fromEnum`, which is equivalent to `concatMap (((…)!!) . fromEnum) w`) against the input string `i`,
    3. calls itself (`d&j`) to match the rest of the string, and
    4. returns the possible result as a list of words `w:n`, in the list monad `[w:n]` (which is the shorter, concrete equivalent to `return (w:n)`).

Note that every line after line 6 is part of the `do` expression started on line 6; this takes exactly the same number of characters as using semicolons on a single line, but is more readable, though you can only do it once in a program.

This program is extremely slow. It can be made faster (and slightly longer) easily by storing the morsified words next to the originals in a list rather than recomputing them at each pattern match. The next thing to do would be to store the words in a binary tree keyed by Morse symbols (a 2-ary *trie*) so as to avoid trying unnecessary branches.

It could be made slightly shorter if the dictionary file did not contain unused symbols such as "-", allowing removal of `replicate 97"X"++` in favor of doing `.(-97+)` before the `!!`.

# Answer
> 3 votes
# Python - ~~363~~ 345

**Code:**

```
D,P='-.';U,N='-.-','.-.'
def s(b,i):
 if i=='':print b
 for w in open('d').read().split():
  C=''.join([dict(zip('abcdefghijklmnopqrstuvwxyz-\'23',[P+D,D+3*P,U+P,'-..',P,D+N,'--.',4*P,2*P,P+3*D,U,N+P,2*D,D+P,D*3,'.--.',D+U,N,P*3,D,'..-',3*P+D,'.--','-..-',U+D,'--..']+['']*4))[c]for c in w]);L=len(C)
  if i[:L]==C:s(b+' '+w,i[L:])
s('',input())

```

**Explanation:**

The dictionary must be stored as a plain text file named "d".

`D`, `P`, `U` and `N` are just some helper variables for a shorter definition of the morse lookup table.

`s(i)` is a recursive function that prints the previously translated message part `p` and each valid translation of the remaining code part `i`: If `i` is empty, we reached the end of the code an `b` contains the whole translation, thus we simply `print` it. Otherwise we check each word `w` in the dictionary `d`, translate it into morse code `C` and, if the remaining code `i` starts with `C`, we add the word `w` to the translated beginning `b` and call the function `s` recursively on the remainder.

**Note on efficiency:**

This is a pretty slow but golfed version. Especially loading the dictionary and constructing the morse lookup table (`dict(zip(...))`) in each iteration (to avoid more variables) costs a lot. And it would be more efficient to translate all words in the dictionary file once in advance and not in each recursion on demand. These ideas lead to the following version with 40 more characters but *significant* speed-up:

```
d=open('d').read().split()
D,P='-.';U,N='-.-','.-.'
M=dict(zip('abcdefghijklmnopqrstuvwxyz-\'23',[P+D,D+3*P,U+P,'-..',P,D+N,'--.',4*P,2*P,P+3*D,U,N+P,2*D,D+P,D*3,'.--.',D+U,N,P*3,D,'..-',3*P+D,'.--','-..-',U+D,'--..']+['']*4))
T=[''.join([M[c]for c in w])for w in d]
def s(b,i):
 if i=='':print b
 for j,w in enumerate(d):
  C=T[j];L=len(C)
  if i[:L]==C:s(b+' '+w,i[L:])
s('',input())

```

# Answer
> 2 votes
## Perl (5.10+), 293 characters

Dictionary file should be saved as "d" (and should be in unix format if you don't want CRs between words), morse input on stdin, with no trailing newline (use `echo -n`).

```
open D,d;chomp(@w=<D>);@m{a..z}=map{substr(sprintf("%b",-61+ord),1)=~y/01/.-/r}
'BUWI?OKMATJQDCLSZGE@FNHVXY'=~/./g;%w=map{$_,qr#^\Q@{[s/./$m{$&}/reg]}#}@w;
@a=[$i=<>];while(@a){say join$",@{$$_[1]}for grep!$$_[0],@a;
@a=map{$x=$_;map{$$x[0]=~$w{$_}?[substr($$x[0],$+[0]),[@{$$x[1]},$_]]:()}@w}@a}

```

(linebreaks only for formatting).

### Ungolfed code:

```
# Read the word list
open my $dictionary, '<', 'd';
chomp(my @words = <$dictionary>);

# Define morse characters
my %morse;
@morse{'a' .. 'z'} = map {
  $n = ord($_) - 61;
  $bits = sprintf "%b", $n;
  $bits =~ tr/01/.-/;
  substr $bits, 1;
} split //, 'BUWI?OKMATJQDCLSZGE@FNHVXY';

# Make a hash of words to regexes that match their morse representation
my %morse_words = map {
  my $morse_word = s/./$morse{$_}/reg;
  ($_ => qr/^\Q$morse_word/)
} @words;

# Read the input
my $input = <>;

# Initialize the state
my @candidates = ({ remaining => $input, words => [] });

while (@candidates) {
  # Print matches
  for my $solution (grep { $_->{remaining} eq '' } @candidates) {
    say join " ", @{ $solution->{words} };
  }
  # Generate new solutions
  @candidates = map {
    my $candidate = $_;
    map {
      $candidate->{remaining} =~ $morse_words{$_}
        ? {
          remaining => substr( $candidate->{remaining}, $+[0] ),
          words => [ @{ $candidate->{words} }, $_ ],
        }
        : ()
    } @words
  } @candidates;
}

```

### Modus Operandi:

Morse code symbols are stored by changing "." and "-" into binary digits 0 and 1, prepending a "1" (so that leading dots aren't gobbled up), converting the binary number into decimal, and then encoding the character with the value 61 higher (which gets me all printable chars and nothing that needs backslashing).

I thought of this as a kind of partitioning problem, and built a solution based on that. For each word in the dictionary, it constructs a regex object that will match (and capture) that word's spaceless morse representation at the beginning of a string. Then it begins a breadth-first search by creating a state that has matched no words and has the entire input as "remaining input". Then it expands each state by looking for words that match at the beginning of the remaining input, and creating new states that add the word to the matched words and remove the morse from the remaining input. States that have no remaining input are successful and have their list of words printed. States that can't match any words (including successful ones) generate no child states.

Note that in the ungolfed version the states are hashes for readability; in the golfed version they're arrays (for shorter code and less memory consumption); slot `[0]` is the remaining input and slot `[1]` is the matched words.

### Commentary

This is ungodly slow. I'm wondering if there's a solution that isn't. I tried to build one using Marpa (an Earley parser with the ability to give multiple parses for a single input string) but ran out of memory just constructing the grammar. Maybe if I used a lower-level API instead of the BNF input...

# Answer
> 2 votes
# Haskell - 418

This decoing problem can be solved efficiently by dynamic programming. I know this is a codegolf, but I love fast code.

Say we have the input string `s`, then we build an array `dp`, `dp[i]` is the list of all valid decoding results of substring `s[:i]`. For each word `w` in the dictionary, first we encoding it to `mw`, then we can compute part of `dp[i]` from `dp[i - length(mw)]` if `s[i - length(mw):i] == mw`. The time complexity of building `dp` is `O({count of words} {length of s} {max word length})`. Finally, `dp[length(s)]`, the last element, is what we need.

In fact, we don't need to store the whole decoding as the element of each `dp[i]`. What we need is the last decoded word. This make the implementation a lot faster. It cost less than 2 seconds to finished the "hello world" case on my i3 laptop. For other cases posted in the question, the program will not finish pratically since there are too many to output.

Using the dynamic programming technique, we can compute **the number of valid decodings**. You can find the code here. Results:

```
input: ......-...-..---.-----.-..-..-..
count: 403856

input: .--..-.-----..-..-----..-.--..--...---..--...-.......--.-..-.-.----...--.---.-....-.
count: 2889424682038128

input: -.....--.-..-..-.-.-.--....-.---.---...-.----..-.---..---.--....---...-..-.-......-...---..-.---..-----.
count: 4986181473975221635

```

## Ungolfed

```
import Control.Monad

morseTable :: [(Char, String)]
morseTable = zip ['a'..'z'] $ words ".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --.."

wordToMorse :: String -> Maybe String
wordToMorse xs = return . concat =<< mapM (`lookup` morseTable) xs

slice :: (Int, Int) -> [a] -> [a]
slice (start, end) = take (end - start) . drop start

decode :: String -> String -> IO ()
decode dict s = trace (length s) [] where
  dict' = [(w, maybe "x" id . wordToMorse $ w) | w <- lines dict]
  dp = flip map [0..length s] $ \i -> [(j, w) |
        (w, mw) <- dict', let j = i - length mw, j >= 0 && mw == slice (j, i) s]

  trace :: Int -> [String] -> IO ()
  trace 0 prefix = putStrLn . unwords $ prefix
  trace i prefix = sequence_ [trace j (w:prefix) | (j, w) <- dp !! i]

main :: IO ()
main = do
  ws <- readFile "wordlist.txt"
  decode ws =<< getLine

```

## Golfed

```
import Control.Monad
l=length
t=zip['a'..]$words".- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --.."
h s=return.concat=<<mapM(`lookup`t)s
f d s=g(l s)[]where g 0 p=putStrLn.unwords$p;g i p=sequence_[g j(w:p)|(j,w)<-map(\i->[(j,w)|(w,m)<-[(w,maybe"x"id.h$w)|w<-lines d],let j=i-l m,j>=0&&m==(take(i-j).drop j$s)])[0..l s]!!i]
main=do d<-readFile"d";f d=<<getLine

```

# Answer
> 2 votes
# PHP, ~~234~~ 226 bytes

```
function f($s,$r=""){$s?:print"$r
";foreach(file(d)as$w){for($i=+$m="";$p=@strpos(__etianmsurwdkgohvf_l_pjbxcyzq,$w[$i++]);)$m.=strtr(substr(decbin($p),1),10,"-.");0!==strpos($s,$m)?:g(substr($s,strlen($m)),$r.trim($w)." ");}}

```

recursive function, takes dictionary from a file named `d`.
Fails for every word in the dictionary containing a non-letter.

You can use any file name if you `define ("d","<filename>");` before calling the function.

Add 2 or 3 bytes for faster execution:
Remove `$s?:print"$r\n";`, insert `$s!=$m?` before `0!==` and `:print$r.$w` before `;}}`.

**breakdown**

```
function f($s,$r="")
{
    $s?:print"$r\n";            // if input is empty, print result
    foreach(file(d)as$w)        // loop through words
    {
        // translate to morse:
        for($i=+$m="";              // init morse to empty string, $i to 0
                                        // loop while character is in the string
            $p=@strpos(__etianmsurwdkgohvf_l_pjbxcyzq,$w[$i++])
        ;)
            $m.=                        // 4. append to word morse code
                strtr(
                    substr(
                        decbin($p)      // 1: convert position to base 2
                    ,1)                 // 2: substr: remove leading `1`
                ,10,"-.")               // 3. strtr: dot for 0, dash for 1
            ;
        0!==strpos($s,$m)           // if $s starts with $m
            ?:f(                        // recurse
                substr($s,strlen($m)),  // with rest of $s as input
                $r.trim($w)." "         // and $r + word + space as result
            )
        ;
    }
}

```

# Answer
> 1 votes
**Groovy ~~377~~ 337**

```
r=[:];t={x='',p=''->r[s[0]]=p+x;s=s.substring(1);if(p.size()<3){t('.',p+x);t('-',p+x)}};s='-eishvuf-arl-wpjtndbxkcymgzqo--';t()
m=('d'as File).readLines().groupBy{it.collect{r.get(it,0)}.join()}
f={it,h=[]->it.size().times{i->k=it[0..i]
if(k in m){m[k].each{j->f(it.substring(i+1),h+[j])}}}
if(it.empty){println h.join(' ')}}
f(args[0])

```

*Notes*

The dict must be a file named `d`. The morse string is passed by command line. e.g.:

```
% groovy morse.groovy ......-...-..---.-----.-..-..-.. | grep 'hello world'
hello world

```

For "morse code compression" I am using a binary tree

---
Tags: code-golf, morse
---


title: Tool-Assisted Code Golf

text:
# Question
Title: Tool-Assisted Code Golf
## TAS Golf

In the style of a tool-assisted speedrun with a code-golf twist, the goal of this challenge is to complete World 1-1 of the original *Super Mario Bros* game for the NES in your chosen programming language in as few bytes as possible, using only the in-game controller inputs in the format I'll describe below. Your program must output to `stdout` a list of lines in this format, created specifically for this challenge:

```
up down left right start select A B

```

Starting with the first frame, each newline represents the inputs for Controller 1 for a particular frame. The order of buttons per frame does not matter, and they can be separated by any amount of non-newline whitespace. All or none or some of the button names can be included per line. For example, a simple Python program that presses the D-pad right for 3 frames and then presses A might look like this:

```
for _ in range(3): print('right')
print('A')

```

And its output (which I would feed into my emulator to verify) would be:

```
right
right
right
A

```

Here, we define 'success' as reaching the flag at the end of World 1-1 pictured above. The score for this example Python submission, if it succeeded (which it doesn't), would be **44 bytes**, or the original length of the Python program.

For an example working input file I created based on the current fastest TAS, see this Github Gist: https://gist.github.com/anonymous/6f1a73cbff3cd46c9e1cf8d5c2ff58e1 Note that this file completes the entire game.

There is no way to enter subframe inputs. There is also no way to enter inputs in Player 2's controller, but that also shouldn't be necessary (or useful) for completing the level or game.

The version of SMB used will be the original USA / Japan iNES ROM (md5sum 811b027eaf99c2def7b933c5208636de -- the USA version is the exact same as the Japanese version so either will work, the ROM is commonly labeled `Super Mario Bros (JU) (PRG 0)` or similar).

To test the submissions, I will run the programs, pipe their `stdout` into an input.txt file, and load them into FCEUX using this Lua script `mario.lua` I wrote for this challenge:

```
for line in io.lines('input.txt') do
   local t = {}
   for w in line:gmatch("%S+") do
      t[w] = true;
   end;
   joypad.set(1, t);
   emu.frameadvance();
end;
while (true) do
   emu.frameadvance();
end;

```

The specific command I'll be using is `fceux mario.nes --loadlua mario.lua`. There is no time limit to the programs, though they must eventually terminate.

This is a little Bash one-liner I made to convert a FCEUX movie (.fm2) file to an input.txt for my script, if it helps:

```
cat movie.fm2 | cut -d'|' -f 3 | sed 's/\.//g' | sed 's/R/right /g' | sed 's/L/left /g' | sed 's/D/down /g' | sed 's/U/up /g' | sed 's/T/start /g' | sed 's/S/select /g' | sed 's/B/B /g' | sed 's/A/A /g' | tail -n +13 > input.txt

```

For reference, here is a full-resolution map of World 1-1 (open the image in a new tab for full resolution):
<sub>(source: mariouniverse.com)</sub>

Note: At first glance, this may seem like a Kolmogorov complexity challenge on my given input.txt file. However, in reality the challenge is more complex than that because (a) the input.txt I provided is definitely not the shortest possible and (b) there has never been an attempt to create the shortest possible set of keypresses for SMB in this format. The 'fewest buttons possible' known TAS is different because it allows for holding of buttons for a long time, which would add length to the desired output in this challenge.

# Answer
# Python 2, 69 48 46 44 bytes

```
print"start\n\n"*19+(27*"A right\n"+"\n")*99

```

See it in action on youtube!

Automatically found with (a modified version of) this hacky script:

```
start = 18
oncycle = 21
offcycle = 4

while true do
    emu.poweron()
    -- emu.speedmode("maximum")

    starting = 0
    i = 0
    frames = 0
    last_mario_x = -1

    emu.message(start .. " " .. oncycle .. " ".. offcycle)

    state = 0
    while state ~= 6 and state ~= 11 and frames < 4000 do
        if frames > 500 and frames % 100 == 0 then
            mario_x = memory.readbyte(0x6D) * 0x100 + memory.readbyte(0x86)
            if mario_x == last_mario_x then emu.message("stuck " .. mario_x .. " " .. last_mario_x); break end
            last_mario_x = mario_x
        end

        if starting < start then
            joypad.set(1, {start=1})
            emu.frameadvance(); frames = frames + 1;
            joypad.set(1, {})
            emu.frameadvance(); frames = frames + 1;
            starting = starting + 1
        else
            if i < oncycle then
                joypad.set(1, {A=1, B=1, right=1})
                i = i + 1
            else
                joypad.set(1, {})
                i = i +  1
                if i == oncycle + offcycle then
                    i = 0
                end
            end

            emu.frameadvance()
            frames = frames + 1
        end

        state = memory.readbyte(0x000E)
        if state == 4 then
            emu.message("success!")
            os.exit()
            break
        end

    end

    if start < 30 then
        start = start + 1
    elseif offcycle < 10 then
        start = 18
        offcycle = offcycle + 1
    else
        offcycle = 1
        oncycle = oncycle + 1
    end
end

```
> 20 votes

# Answer
# Python 2, 107 bytes

```
i=0
print'\n'*33+'start'
for c in'~~22 +  2 2? @  F        . \r0'+'@'*10:print'A B right\n'[i:]*ord(c);i^=2

```
> 5 votes

# Answer
# JavaScript (ES6), 59 characters

```
_=>`start

`[a="repeat"](19)+(`A right
`[a](27)+`
`)[a](99)

```

This outputs the same text as orlp's answer. I tried coming up with a better method myself, but the movies I converted to an `input.txt` file did not always play properly. Whenever I tried running the emulator from cmd, I got an error stating `"an unknown error occurred"`.
> 1 votes

---
Tags: code-golf, game
---


title: Copy a file - Windows style

text:
# Question
Title: Copy a file - Windows style
This challenge is inspired by xkcd:

## Challenge:

You'll simulate the copying a large file (1 Gigabyte). The transfer rate will vary between 10 kB/second to 100 MB/second. Your task is to output the time remaining of the file transfer. The output should look like:

```
Time remaining: 03:12    (meaning it's 3 minutes and 12 seconds left)
Time remaining: 123:12   (meaning it's 2 hours, 3 minutes and 12 seconds left)
Time remaining: 02:03:12 (optional output, meaning the same as above)

```

Leading zeros need not be displayed for minutes and hours (optional), but must be shown for seconds. Showing the time remaining using only seconds is not OK.

**The file transfer:**

* The transfer rate will start at 10 MB/second.
* Every second, there will be a 30% chance that the transfer rate will change
* The new transfer rate should be picked randomly (uniform distribution) in the range `[10 kB/s, 100 MB/s]`, in steps of 10 kB/s.

**Note: You don't need to actually copy a file.**

You may choose to use: `1 GB = 1000 MB, 1 MB = 1000 kB, 1 kB = 1000 B`, or `1 GB = 1024 MB, 1 MB = 1024 kB, 1 kB = 1024 B`.

**Output:**

* You start at `01:40`, not `01:39`.
* You display the time after the transfer rate changes, but before anything is transferred at that rate
* The seconds should be displayed as integers, not decimals. It's optional to round up/down/closest.
* You should clear the screen every second, unless that's impossible in your language.
* The output should be constant: `Time remaining: 00:00` when the file transfer is over.

**Example:**

I have rounded up all decimal seconds. Assume the lines below are shown with 1 second in between, and the screen is cleared between each one:

```
Time remaining: 01:40  (Transfer rate: 10 MB/s)
Time remaining: 01:39      1 GB - 10 MB
Time remaining: 01:38      1 GB - 2*10 MB
Time remaining: 01:37      1 GB - 3*10 MB
Time remaining: 01:28:54   1 GB - 4*10 MB  (TR: 180 kB/s)
Time remaining: 01:28:53   1 GB - 4*10 MB - 180 kB
Time remaining: 01:28:52   1 GB - 4*10 MB - 2*180 kB
Time remaining: 00:13      1 GB - 4*10 MB - 3*180 kB  (TR: 75 MB/s)
Time remaining: 00:12      1 GB - 4*10 MB - 3*180 kB - 75 MB
Time remaining: 00:11      1 GB - 4*10 MB - 3*180 kB - 2*75 MB
Time remaining: 00:10      1 GB - 4*10 MB - 3*180 kB - 3*75 MB
Time remaining: 00:09      1 GB - 4*10 MB - 3*180 kB - 4*75 MB
Time remaining: 00:08      1 GB - 4*10 MB - 3*180 kB - 5*75 MB
Time remaining: 14:09:06   1 GB - 4*10 MB - 3*180 kB - 6*75 MB  (TR: 10 kB/s)
Time remaining: 14:09:05   1 GB - 4*10 MB - 3*180 kB - 6*75 MB - 10 kB
Time remaining: 00:06      1 GB - 4*10 MB - 3*180 kB - 6*75 MB - 20 kB  (TR: 88.110 MB/s)
Time remaining: 00:05
Time remaining: 00:04
Time remaining: 00:03
Time remaining: 00:02
Time remaining: 00:01
Time remaining: 00:00     <- Transfer is finished. Display this.

```

# Answer
# Pyth - ~~70~~ 68 bytes

```
K^T5J^T3W>KZ%." r3úBTêî¢¤;¥
í".D/KJ60=J?<OT3O^T4J=-KJ.d1.

```

Try it online without sleeps.
> 9 votes

# Answer
# PowerShell, ~~190~~ ~~215~~ 187 bytes

```
($t="Time remaining: ")+"00:01:42";for($f,$r=1gb,10mb;$f-gt0;$f-=$r){if((Random 10)-lt3){$r=(Random -mi 1kb -ma (10mb+1))*10}$t+[Timespan]::FromSeconds([int]($f/$r));sleep 1}$t+"00:00:00"

```

Try it online! (TIO doesn't support clearing screen between lines)

Sets our initial `$f`ile size and our initial transfer `$r`ate to `1gb` and `10mb`/s, respectively. Then, so long as we still have `$f`ile remaining, we loop.

Inside the loop, the `if` selects a number from `0` to `9` inclusive, and if it's 0, 1, or 2 (i.e., 30% of the time), we change the rate. This picks a random integer between `1kb` and `10mb` then that's multiplied by `10` to get our step count.

We then leverage the `FromSeconds` static method from the `TimeSpan` .NET library to construct the time remaining. The output format of that call exactly matches the challenge requirements, so no need for additional formatting.

*(Saved a bunch thanks to @ConnorLSW)*
> 8 votes

# Answer
# MATL, 78 bytes

*Thanks to @Maltysen and @DigitalTrauma for corrections.*

```
1e5 1e3`XK10&XxyXIy/t0>*12L/'MM:SS'XO'Time remaining: 'whD-r.3<?1e4Yr}K]I0>]xx

```

Try it at MATL Online! (you may need to press "Run" several times if it doesn't initially work).

The online interpreter times out after 30 seconds. You may want to change `10` (pause time in tenths of second) to something smaller such as `3` in order to increase speed of display

### Explanation

```
1e5                  % Push 1e5: file size in 10-kB units
1e3                  % Push 1e3: initial rate in 10-kB/s units
`                    % Do...while
  XK                 %   Copy current rate into clipboard K (doesn't consume it)
  10&Xx              %   Wait 1 second and clear screen
  y                  %   Duplicate current file size onto the top of the stack
  XI                 %   Copy it to clipboard I (doesn't consume it)
  y                  %   Duplicate current rate onto the top of the stack
  /                  %   Divide. This gives the estimated remaining time in seconds
                     %   It may be negative in the last iteration, because the
                     %   "remaining" file size may have become negative
  t0>*               %   If negative, convert to 0
  12L/               %   Push 86400 and divide, to convert from seconds to days
  'MM:SS'XO          %   Format as a MM:SS string, rounding down
  'Time remaining: ' %   Push this string
  wh                 %   Swap, concatenate
  D                  %   Display
  -                  %   Subtract. This gives the new remaining file size
  r                  %   Push random number uniformly distributed in (0,1)
  .3<                %   Is it less than 0.3?
  ?                  %   If so
    1e4Yr            %     Random integer between 1 and 1e4. This is the new rate
                     %     in 10-kB/s units
  }                  %   Else
    K                %     Push rate that was copied into clipboard K
  ]                  %   End
  I                  %   Push previous remaining file size from clipboard I
  0>                 %   Is it positive?
]                    % End. If top of the stack is true: next iteration
xx                   % Delete the two numbers that are on the stack

```
> 5 votes

# Answer
# Ruby, ~~116~~ 110 bytes

Try it online, except repl.it reads `\r` as a newline and also can't use `$><<` so it's replaced with its 5-byte equivalent, `print`.

Shoutout to JonasWielicki for the initial idea of using `\r` to reset the line.

```
f=1e5;r=1e3;(k=f/r=rand<0.3?1+rand(1e4):r;$><<"\rTime remaining: %02d:%02d"%[k/60,k%60];f-=r;sleep 1)while f>0

```

This version is untested on Windows, but works on Unix.
> 5 votes

# Answer
# Bash + common utils, 117

Straightforward implementation. A few bytes saved by dividing out by 10000:

```
for((b=10**5,r=1000;b>0;r=RANDOM%10<3?RANDOM%10000+1:r,b-=r));{
clear
date -ud@$[b/r] "+Time remaining: %T"
sleep 1
}

```

Try it online. Using `sleep 0` on the TIO so you don't have to wait. `clear` doesn't work on TIO.
> 4 votes

# Answer
# JavaScript (ES6), 162 bytes

Shows minutes as is with padded seconds (floored)

E.g., `123:45`

```
t=1e5
s=1e3
setInterval(c=>c.log(`Time remaining: ${c.clear(d=t/s),d/60|0}:`+`0${t-=s>t?t:s,r=Math.random,s=r()<0.3?1+r()*1e4|0:s,d%60|0}`.slice(-2)),1e3,console)
```
> 3 votes

# Answer
# Python 3.6 (~~212~~ 203 bytes)

```
from random import*
import time,datetime
r=1e7
d=1e9
while 1:
 print(f"\x1b[KTime remaining: {datetime.timedelta(seconds=d//r)}",end="\r");d=max(0,d-r);time.sleep(1)
 if random()>.7:r=randint(1,1e4)*1e4

```

Pretty straightforward, I think. Erases the line using ANSI escape sequence and `K` command.
> 2 votes

# Answer
## C ~~184~~ ~~171~~ 155 bytes

```
f(){i,j=0,r=1e7;for(i=1e9;i>0;i-=r){j=i/r;printf("Time remaining: %02d:%02d:%02d\r",j/3600,(j/60)%60,j%60);sleep(1);if(rand()%10<3)r=(rand()%10000)*1e4;}}

```

I hope this qualifies.

Ungolfed version:

```
void f()
{
    int j=0;
    float rate=1e7;
    for(int size=1e9;i>0; size-=rate)
    {
       j=size/rate;
       printf("Time remaining: %02d:%02d:%02d\r",j/3600,(j/60)%60,j%60);
       sleep(1);

       if(rand()%10<3)
          rate=(rand()%10000)*1e4;

   }

}

```

Explanation: In the golfed version `i` corresponds to `size` in ungolfed version and `r` is `rate` in ungolfed version. `j` stores the time remaining in seconds.

* I have 10^9 bytes to copy. I start copying at the rate of 10 Megabytes/second,
* If the probablity is less than 30% , change the rate (from 10 kilobytes to 100 Megabytes per second)

@ValueInk Thanks for saving 13 bytes.

@nmjcman101 Thanks for saving 16 bytes.
> 1 votes

# Answer
## Batch, 193 bytes

```
@set/ap=10000,s=p*10,r=p/10
:l
@set/at=s/r,m=t/60,n=t%%60+100,s-=r
@cls
@echo Time remaining: %m%:%n:~1%
@timeout/t>nul 1
@if %random:~-1% lss 3 set/ar=%random%%%p+1
@if %t% gtr 0 goto l

```

Note: Slight bias towards rates of 27.68 MB/s or less.
> 1 votes

---
Tags: code-golf
---