# Question
Title: Print all numbers from -100 to 100 which contain a given digit
Provided a digit between 0 and 9 (inclusive), your function/subroutine should print all numbers between -100 and 100 (inclusive) that contain the given digit.

For example:

```
Input: 9
Output: -99 -98 -97 -96 -95 -94 -93 -92 -91 -90 -89 -79 -69 -59 -49 -39 -29 -19 -9 9 19 29 39 49 59 69 79 89 90 91 92 93 94 95 96 97 98 99

```

**Rules:**

* You cannot use strings (in whatever way they are represented in your chosen language) or char arrays. (Except to print the answer to the console.)
* You cannot use arrays.

**Scoring:**

Score = length of subroutine/function (whitespace will not be counted)

The answer with the lowest score wins.

Whitespace will NOT be counted. Please format your code properly!

Some answers are using regular expressions, which may violate the no strings rule, as pointed out by some members. These answers will not be accepted.

Please test your code with `0` before posting.

# Answer
## Whitespace, 834 characters (0 if you subtract whitespaces)

Used this interpreter to test it.

This took me some 4 hour of hard work and horrible debugging to create. But it is done!

```

```

**EDIT**: Selectable text provided with HTML tricks. If you copy and paste it from here to some other place, please check if you got exactly `[space][tab][linefeed][linefeed][linefeed]` at the end with 100 or 101 lines (depending if your editor counts or not a new line if the last one ends with a linefeed).

In the case that you can't use it this way, considering space as `S`, linefeed as `L` and tab as `T`, and breaking lines after the `L`'s, here it is:

```
SSSTSSSSTSL
SSSTSSSSTSL
TL
TSSSSTSSSSTSL
TTTSSSTTSSSSL
TSSTTTSSSSTSSSSTTL
SSTTTSSSTTL
TTSSSSTSSSSSTL
SSSL
TTSSSSTSSSSTSL
TTTL
TSSTSSTSTTL
SSSTSSSSTSL
TTTSSSTL
TSSTL
TSSTSSTSTTL
L
SSSTSSSTSSL
SSSTSSSSTTL
TTTSL
SSSSTTSSTSSL
TSSTL
TSSTSSSTSTL
SL
SSSTTL
TSSL
L
TTSTSSSTTTL
SSTTL
TSSL
L
SSSTSSSTTTL
SL
SSSSTSSSSTSL
TTTL
TSSTSSTSSSL
SSSTSTSL
TSTSSSSTSSSSTSL
TTTTSSTL
TSSTSSTSSTL
L
SSSTSSTSSSL
SSSTSTSL
TSTTSSSTSSSSTSL
TTTTSSTL
TSSTSSTSSTL
L
SL
STSSTSTSL
L
SSSTSSTSSTL
SSSTSSSSSTL
TTTL
TSSTSSSTTSL
SSSTSSSSSL
TL
SSL
SSSTSSSTTSL
SSSTSSSSSTL
SSSTL
TTSSSSTSSSSTTL
TTTTL
STL
SSSTSSTSTSL
SSSTSSSSTTL
SSSTSSSSTTL
TTTSSSTL
TSSSTTSL
SL
STSSSTSSL
L
SSSTSSSTSTL
SSSTSSSSTSL
TTTL
TSSTSSTTSSL
SSSTSSSSTSL
TTTSSSTL
TSSTL
TSSTSSTTSSL
L
L
L
L
SSSTSSTSTTL
SSTTTSSTSSL
TL
STSSSTSSSSSL
TL
SSL
SL
STSSSTSSL
L
SSSTSSTTSSL
SSSTSSSSSL
TL
SSSSSTTSSTSSL
TL
STL
L
L

```
> 75 votes

# Answer
**Bash+utils - 20**

```
seq -100 100|grep 9

```

Or 21 bytes if in a script

```
seq -100 100|grep $1

```

To run the script:

```
sh myscript 9

```
> 24 votes

# Answer
# JavaScript 133 - 1 = 132

Surely there couldn't possibly be anything wrong with this version now...?

```
for(k=prompt(),c=console,j=-100;100>=j;j++)if(i=j,0==j&j==k)c.log(0);else for(;i;)if(h=i%10,h=0>h?-h:h,i=i/10|0,h==k){c.log(j);break}

```

---

```
PROMPT: 2
CONSOLE.LOG:
-92
-82
-72
-62
-52
-42
-32
-29
-28
-27
-26
-25
-24
-23
-22
-21
-20
-12
-2
 2
 12
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 32
 42
 52
 62
 72
 82
 92

CONTROL, using zero
PROMPT: 0
CONSOLE.LOG:
    -100
    -90
    -80
    -70
    -60
    -50
    -40
    -30
    -20
    -10
      0
     10
     20
     30
     40
     50
     60
     70
     80
     90
    100

```
> 9 votes

# Answer
# GolfScript \[24 bytes\]

```
`:x;201,{100-}%{`x?-1>},

```

**Description:**

```
`:x;             - save input value to variable 'x' and remove from the stack
201,{100-}%      - create range from -100 to 100
{`x?-1>},        - filter the range by "index-of" condition

```

**DEMO:** http://golfscript.apphb.com/?c=MwoKYDp4OzIwMSx7MTAwLX0le2B4Py0xPn0sYA%3D%3D
> 8 votes

# Answer
# Ruby: 92 characters

```
s=gets.to_i
$><<(-100..100).select{|n|a=n.abs;loop{break""if a%10==s;break if 0==a/=10}}*" "

```

Readable version:

```
searchfor = gets.to_i
$><< (-100..100).select { |number|
  absnumber = number.abs
  loop {
    break "" if absnumber % 10 ==s
    break if 0 == absnumber /= 10
  }
} * " "

```

Sample run:

```
bash-4.2$ ruby -e 's=gets.to_i;$><<(-100..100).select{|n|a=n.abs;loop{break""if a%10==s;break if 0==a/=10}}*" "' <<< 9
-99 -98 -97 -96 -95 -94 -93 -92 -91 -90 -89 -79 -69 -59 -49 -39 -29 -19 -9 9 19 29 39 49 59 69 79 89 90 91 92 93 94 95 96 97 98 99

```

Test run:

```
bash-4.2$ for i in {0..9}; do diff -w <(ruby -e 's=gets.to_i;$><<(-100..100).select{|n|a=n.abs;loop{break""if a%10==s;break if 0==a/=10}}*" "' <<< $i) <(seq -100 100|grep $i|tr \\n \ ) > /dev/null; echo "$i : $?"; done
0 : 0
1 : 0
2 : 0
3 : 0
4 : 0
5 : 0
6 : 0
7 : 0
8 : 0
9 : 0

```
> 6 votes

# Answer
## bash ~~55~~ 49 characters:

(not counting whitespace around `&&`)

```
for i in {-100..100}
do
  [[ $i =~ $1 ]] && echo $i
done

```

Executing it by saying:

```
bash filename 9

```

would produce:

```
-99
-98
-97
-96
-95
-94
-93
-92
-91
-90
-89
-79
-69
-59
-49
-39
-29
-19
-9
9
19
29
39
49
59
69
79
89
90
91
92
93
94
95
96
97
98
99

```
> 6 votes

# Answer
# K - 45 char

Not winning any awards, but K golfing is underrepresented. K doesn't get any prettier with proper spacing, so I'll just leave this as is, because K gets very picky about which whitespace is important and which isn't.

```
{|a@&x _in'@[10_vs'_ _abs a:100-!201;100;0,]}

```

Explained:

* `a:100-!201` \- Make a list from 0 to 200 inclusive, then subtract it from 100. Now we have the numbers from -100 to 100 inclusive, but backwards from the question's specs. We can always fix that later, so for now we'll just assign this to `a`.
* `_ _abs` \- Take the floor of the absolute value of these numbers, because for whatever reason K thinks that `_abs` should give floating point results. Thankfully, flooring them turns them back into integers.
* `10_vs'` \- Expand each (`'`) integer as a base 10 number (`_vs` stands for "vector from scalar"). Note that we did not have to use the Each operator `'` on the functions above because they operate on atoms.
* `@[...;100;0,]` \- Amend the item in our list at index 100 (an empty list, which is the result of expanding 0 into base 10) by the function `0,`, which prepends a zero to the front. Without this correction, this function will fail on the input 0.
* `&x in'` \- Now, return the indices (`&`) where `x` is a digit in (`_in`) each (`'`) of the expansions we so carefully constructed above.
* `|a@` \- Finally, use these indices to index `a`, and reverse the list into the right order.

Usage is obvious, though good luck getting your hands on a K interpreter. (There's an open source implementation at on Github that you can compile.)

```
  {|a@&x _in'@[10_vs'_ _abs a:100-!201;100;0,]} 0
-100 -90 -80 -70 -60 -50 -40 -30 -20 -10 0 10 20 30 40 50 60 70 80 90 100
  {|a@&x _in'@[10_vs'_ _abs a:100-!201;100;0,]} 5
-95 -85 -75 -65 -59 -58 -57 -56 -55 -54 -53 -52 -51 -50 -45 -35 -25 -15 -5 5 15 25 35 45 50 51 52 53 54 55 56 57 58 59 65 75 85 95

```
> 6 votes

# Answer
# C - 104 107 114 characters - 0 = 104 107 114

```
a,b;main(i){i=getchar()-48;for(a=-100;a<101;a++){for(b=a;a&&abs(a%10)!=i;a/=10);if(a|!i&!b)printf("%i ",b);a=b;}}

```

Ungolfed:

```
#include <stdio.h>

int a, b;

int main(int i) {
    i = getchar() - '0';
    for( a = -100 ; a < 101 ; a++ ) {
        for( b = a ; a && abs(a % 10) != i ; a /= 10 );
        if( a | !i & !b )
            printf("%i ", b);
        a = b;
    }
}

```
> 4 votes

# Answer
# PHP 67 bytes:

```
for($i=-100;$i<101;++$i)if(strpos($i,$_GET[n])!==!1)echo$i,PHP_EOL;

```

Yes, there is a 'strpos' call, but I'm using only numbers!

Here is a 'ungolfed' version:

```
for($i=-100;$i<101;++$i)
{
    if(strpos($i,$_GET[n])!==false)
    {
        echo $i,PHP_EOL;
    }
}

```

For this to work, you can test it here: http://writecodeonline.com/php/

Just remember to add `$_GET[n]='<number>';` to the beginning of the code.

Or, on a lamp or xampp server, you can create a page and then access it on the browser, with the parameter `?n=<number>` after the filename.
> 4 votes

# Answer
My first attempt here, so maybe I am doing some things wrong, please excuse that ;)
So, I wasn't sure if I had to add the whole class or just the logic within.

# Java - 199 characters

```
intx=System.in.read()-48;for(inti=-100;i<101;i++){if((i<10&&i==-x)||(i>-10&&i==x)||(i<-9&&((i/100==x&&i<-99)||i%10==-x||i/10==-x))||(i>9&&((i/100==x&&i>99)||i%10==x||i/10==x)))System.out.println(i);}

```

Here a more readable form:

```
int x = System.in.read() - 48;
for(int i = -100; i < 101; i++) {

    if((i < 10 && i == -x) || (i > -10 && i == x)
        || (i < -9 && ((i / 100 == x && i < -99 ) || i % 10 == -x || i / 10 == -x))
        || (i > 9 && ((i / 100 == x && i > 99) || i % 10 == x || i / 10 == x)))

        System.out.println(i);

}

```

I guess the basic idea was not that bad, but needed too much exceptions, to finally work out for all cases... :/
> 4 votes

# Answer
# Mathematica 28

Sorry, I just couldn't resist.

:)

The instructions are: "Provided a digit between 0 and 9 (inclusive), your function/subroutine should print all numbers between -100 and 100 (inclusive) that contain the given digit."

---

The following prints all such numbers in order.

```
f@n_ :=Print/@Range[-100,100]

```

As a special bonus, it prints those numbers in the same range that do not contain the given digit. :)
> 4 votes

# Answer
## R 87 93

Here's an improvement:

```
a=scan();r=-100:100;s=abs(r);r[(!a&!r%%10)|a&(a==s%%10|a==floor(s/10)|a==floor(s/100))]

```

(Potentially) More readable, with notes:

```
a=scan() # take user input of selected digit
r=-100:100 # define our scanning range
s=abs(r) # copy the range as the absolute value for proper floor() calculation
#r[<criteria>] is functionally the same as subset(r,<criteria>)
r[ # when any of the criteria below are met, use that value from the range
    (!a & !r%%10) # case when input is 0, !a is evaluated as "a when a<>0 == true"
    | a & # all other digits below
    a==s%%10
    |
    a==floor(s/10)
    |
    a==floor(s/100)
    ] # R does not require a print command, so this as-is will display the corresponding values

```
> 3 votes

# Answer
**Javascript 116**

```
   a = 0
        for(i=-100;101>i;i++){
        m=Math
        f=m.floor
        j = m.abs(i)
        if((j>10&&f(j/10)==a)||j-f(j/10)*10==a||j/100==a){

             console.log(i)

        }
        }

```
> 3 votes

# Answer
# Prolog: 75

```
f(D) :-
  between(-100,100,N) ,
  number_chars(N,Ds) ,
  member(D,Ds) ,
  writeln(N) ,
  fail
  .

```
> 3 votes

# Answer
## C answer in 98 characters

This is one of the sexiest things I've ever coded

```
main()
{
    int t=getchar()-48,i=100,j=-i;
    while ((i=t-i%10?i/10:!printf("%d\n",j)) || (i=++j<0?-j:j)<101  );
}

```

The older version, with 104 non-whitespace chars:

```
int main()
{
    int t=getchar()-48,i,j=-101;
    while(++j<101)
    {
        i=j<0?-j:j;
        while(i = t-i%10?i/10:!printf("%d\n",j));
    }
}

```

"Works for me" using GCC and CLANG.
> 3 votes

# Answer
# GW Basic: 107 characters excluding whitespace

```
1 input n
2 for i=-100 to 100
3 j=abs(i):a=j mod 10
4 if a=n then 8
5 b=j\10
6 if (b=n) and b then 8
7 if (b<10) or n<>1 then 9
8 print i
9 next

```

Using single digits for the line numbers helps and stripping the whitespace means there isn't really a need for having multiple statements on a line more than once to keep numbers reaching 10.
> 3 votes

# Answer
# GNU coreutils (44)

```
read N
seq -100 100 | grep $N | tr '\n' ' '
echo

```

where `tr` is used to convert newlines to spaces, and `echo` provides one final newline.

```
$ bash ./script
9
-99 -98 -97 -96 -95 -94 -93 -92 -91 -90 -89 -79 -69 -59 -49 -39 -29 -19 -9 9 19 29 39 49 59 69 79 89 90 91 92 93 94 95 96 97 98 99

```
> 2 votes

# Answer
## Javascript - 108

Not sure if existing javascript answer will be taken into consideration because it uses regex, so I created one without it:

```
for(x=+prompt(i=-100);i<101;i++)if((j=i<0?-i:i)&&j%10==x||((j/100==x||(0|j/10)==x)&&x)||j==x)console.log(i)

```

Can also be shortened to 101 if x variable is put directly, like:

```
for(x=5,i=-100;i<101;i++)if((j=i<0?-i:i)&&j%10==x||((j/100==x||(0|j/10)==x)&&x)||j==x)console.log(i)

```

It basically checks if absolute values of div or mod operations are equal to the digit (which also works for 100).
> 2 votes

# Answer
# J - 27 chars

All whitespace is safely removable, meaning 27 characters. Negative numbers in output will have `_` for a negative sign: this is just the way J writes its negative numbers.

```
((e. 10 #.^:_1 |)"0 # ]) & (i: 100)

```

Explained:

* `V & (i: 100)` \- Bind (`&`) the set of numbers from -100 to 100 inclusive (`i:100`) as the right argument of the main verb (`V`). The single argument of the entire verb gets piped into the left side.
* `(U"0 # ])` \- Use the result of the verb `U` over each number from the right argument (`"0`) to select (`#`) items from the right argument (`]`).
* `(e. 10 #.^:_1 |)` \- Given the digit to test for as the left argument and the number to check as the right argument, expand in base 10 (`10 #.^:_1`) the absolute value of the number (`|`), and check if the digit is an element of that expansion (`e.`).

Usage:

```
   ((e. 10 #.^:_1 |)"0 # ]) & (i: 100) 0
_100 _90 _80 _70 _60 _50 _40 _30 _20 _10 0 10 20 30 40 50 60 70 80 90 100
   ((e. 10 #.^:_1 |)"0 # ]) & (i: 100) 5
_95 _85 _75 _65 _59 _58 _57 _56 _55 _54 _53 _52 _51 _50 _45 _35 _25 _15 _5 5 15 25 35 45 50 51 52 53 54 55 56 57 58 59 65 75 85 95

```
> 2 votes

# Answer
# Groovy, 127

```
def x = args[0].toInteger()
for (k in -100..100)
    if (k == x)
        print " ${k}"
    else
        for (n = Math.abs(k); n > 0; n = (int) n / 10)
            if (n % 10 == x) {
                print " ${k}"
                break
            }

```

No strings (except to output the spaces between the numbers), no char arrays or other arrays, no regexes. Tested with 0. Output:

-100 -90 -80 -70 -60 -50 -40 -30 -20 -10 0 10 20 30 40 50 60 70 80 90 100
> 2 votes

# Answer
**GROOVY, 71**

```
f={z->
  _=10
  (-_*_.._*_).grep {
    a=it.abs()
    b=a%_==z
    a<_?b:b||(int)(a/_)%_==z
  }
}

println f(0)
println f(9)

```

Results in

```
[-100, -90, -80, -70, -60, -50, -40, -30, -20, -10, 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
[-99, -98, -97, -96, -95, -94, -93, -92, -91, -90, -89, -79, -69, -59, -49, -39, -29, -19, -9, 9, 19, 29, 39, 49, 59, 69, 79, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]

```
> 2 votes

# Answer
# Haskell, 86 75 (78 with necessary whitespaces)

```
f 0=[-100,-90..100]
f d=[b|b<-[-100..100],abs(b`quot`10)==d||abs(b`rem`10)==d]

```

Ungolfed:

```
f dig =
  if dig == 0
    then [-100, 90 .. 100]
    else [num | num <- [-100 .. 100], abs (num `quot` 10) == d || abs (num `rem` 10) == d]

```
> 2 votes

# Answer
**Javascript 96**

Using bitwise or:

```
b=Math.abs;
a=prompt();
for(i=-100;i<101;)
    if(!(b(i++/10)^a && b(i%10)^a)||b(i)/a==100)  console.log(i)

```
> 2 votes

# Answer
## VBA 121

(no whitespace or `Sub` definition counted):

```
Sub t(d)
For n = -100 To 100
m = Abs(n)
o = o & IIf(d = 0, IIf(d = n Mod 10, " " & n, ""), IIf(d = n Or d = m Mod 10 Or d = Int(m / 10) Or d = Int(m / 100), " " & n, ""))
Next
MsgBox o
End Sub

```
> 1 votes

# Answer
# Python - 172 chars

```
def f(x,y,z):
    if x%10==y or (x>9 and x/10==y) or (x==100 and y==1):
        print z
def g(x,y):
    f(abs(x),y,x)
    if x<100:
        g(x+1,y)
def h(y):
    g(-100,y)

```

To test within Python:

```
>>> h(4)
-94
-84
-74
...
-49
-48
...

```
> 1 votes

# Answer
# perl, 117 with non-meaningful whitespace chars removed

I think you were looking for something more like this. Reads from stdin, outputs one line per match. No regexps, arrays (or sets or hashes or anything else that is an array under the covers) or strings, implicit or otherwise, except the strings passed to print:

```
chomp($x=<>); for($y=-100;$y<101;++$y) { $a=abs $y; print "$y " if $a % 10 == $x || $a > 9 && int( $a/10 ) == $x || $a==100 && $x==1}; print "\n"

```

eg:

```
ski@anito:~$ echo 0 | perl -e 'chomp($x=<>); for($y=-100;$y<101;++$y) { $a=abs $y; print "$y " if $a % 10 == $x || $a > 9 && int( $a/10 ) == $x || $a==100 && $x==1}; print "\n"'
-100 -90 -80 -70 -60 -50 -40 -30 -20 -10 0 10 20 30 40 50 60 70 80 90 100

ski@anito:~$ echo 1 | perl -e 'chomp($x=<>); for($y=-100;$y<101;++$y) { $a=abs $y; print "$y " if $a % 10 == $x || $a > 9 && int( $a/10 ) == $x || $a==100 && $x==1}; print "\n"'
-100 -91 -81 -71 -61 -51 -41 -31 -21 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -1 1 10 11 12 13 14 15 16 17 18 19 21 31 41 51 61 71 81 91 100

ski@anito:~$ echo 2 | perl -e 'chomp($x=<>); for($y=-100;$y<101;++$y) { $a=abs $y; print "$y " if $a % 10 == $x || $a > 9 && int( $a/10 ) == $x || $a==100 && $x==1}; print "\n"'
-92 -82 -72 -62 -52 -42 -32 -29 -28 -27 -26 -25 -24 -23 -22 -21 -20 -12 -2 2 12 20 21 22 23 24 25 26 27 28 29 32 42 52 62 72 82 92

```
> 1 votes

# Answer
# F# 87 92 - 7

```
let f n = {-100..100}
|>Seq.filter(fun x->abs x%10=n||abs x/10=n&&n>0)
|>Seq.iter(printf"%d ")

```

added 5 chars because 0 wasn't handled correctly. (Single digit values would all be returned.)
> 1 votes

# Answer
This is my first time playing code golf. This looks pretty interesting. I can't win, but I tried and wanted to show what I could do.

**Python: 104 (89 if I can mulligan the import) - if the results must be printed exactly as shown in the example**

```
from math import *

def g(x):
    t = 10
    p = lambda i: x == i % t or i >= t and p(i / t)
    for i in range(-100, 101):
        if p(abs(i)):
            print i,
    print
# g(0)
# -100 -90 -80 -70 -60 -50 -40 -30 -20 -10 0 10 20 30 40 50 60 70 80 90 100

```

**Python: 71 - if the output can be done outside the function and the only restriction for the output is that no violating numbers are printed**

```
f = lambda x: [(-i, i) for i in range(101) for j in (10, 100) if i % j == x or i >= j and i / j == x]
# print f(0)
# [(0, 0), (0, 0), (-10, 10), (-20, 20), (-30, 30), (-40, 40), (-50, 50), (-60, 60), (-70, 70), (-80, 80), (-90, 90), (-100, 100), (-100, 100)]

```
> 1 votes

# Answer
**JavaScript 125 char**

Sorry for the several edits I've been having troubles doing this from my phone :)

```
function c(n,i){o=i||0;h=100;j=o-h;f=Math.abs(j);m=f/10|0;if((m==n&&m!=0)||n==f%10||f/h==n)console.log(j);if(o<h*2)c(n,o+1);}

```
> 1 votes

# Answer
### Powershell - 20 17 chars

To match the digit 9 (for example):

```
-100..100-match 9

```

EDIT: found I could remove brackets and one piece of whitespace.
> 1 votes

# Answer
# Dogelang, 42 non-whitespace characters

```
f=n->for i in(-100..101)=>if n in str i=>print i

```

Same as my Python solution, just converted to dogelang.
> 1 votes

# Answer
## Mathematica - 65 chars

```
f@n_:=If[IntegerDigits@#~MemberQ~n,Print@#]&~Scan~Range[-100,100]

```
> 1 votes

# Answer
# Python 2 (70)

```
def f(i):
 n=-100
 while n<101:
  m=abs(n)
  if i in [m%10]+[m/10,m>99]*i: print n,
  n+=1

```

For `i=0` to work, the `*i` makes the `m/10` condition not be checked. When `i=1`, we get `m=100` to be accepted by adding the condition `m>99`, which evaluates to `True` which equals `1`.
> 1 votes

# Answer
Ruby

```
def f(n);-100.upto(100){|i|print"#{i} "if(i.abs/10==n||i.abs%10==n)};end

```
> 1 votes

# Answer
**C#**

```
IEnumerable<int> f(int a)
{
    yield a;
    yield -a;
    for(i = 1; i < 10; i++)
    {
        yield (i * 10) + a;
        yield (i * -10) - a
    }

    if (a != 1) yield break;
    yield 100;
    yield -100;
}

```
> 0 votes

# Answer
# Python, 91 (or possibly 90)

```
f = lambda x: filter(lambda y: x in(abs(y) % 10, abs(y)/10, abs(y)/100) if x else y%10 < 1, xrange(-100,101))

```

Examples:

```
>>> f(0)
[-100, -90, -80, -70, -60, -50, -40, -30, -20, -10, 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
>>> f(1)
[-100, -91, -81, -71, -61, -51, -41, -31, -21, -19, -18, -17, -16, -15, -14, -13, -12, -11, -10, -1, 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 31, 41, 51, 61, 71, 81, 91, 100]

```

If lists do not count as arrays, we can get rid of the `x` in `xrange` and maintain correctness for a total score of **90**. If we remove unnecessary whitespace, the *total* length becomes 97 (or 96).
> 0 votes

# Answer
**C++ - 235 char**

First post on here, gave it a shot

```
#include <iostream>
#include <string>
using namespace std;
int main()
{
    int input;
    cin >> input;
    std::string is = std::to_string(input);
    for(int i = -100; i < 101; i++){
        std::string os = std::to_string(i);
        if(os.find(is) != std::string::npos)
            cout << os << " ";
    }
}

```
> 0 votes

# Answer
# Fortran 95: 90 characters

```
n=9
do i=0,9
print*,10*i+n,-10*i-n
if(n>0)print*,10*n+i,-10*n-i
enddo
if(n<2)print*,100,-100
end

```

Note: it sometimes outputs a same number twice, but the rules say nothing about this being illegal
> 0 votes

# Answer
# LOLCODE: 364 characters (without whitespace)

```
HAI
I HAS A N ITZ 1
I HAS A VAR ITZ 0
I HAS A I
I HAS A J
IM IN YR LOOP
  UPZ VAR!!1
  I R PRODUKT OF 10 AN VAR
  I R SUM OF I AN N
  J R DIFF OF 0 AN I
  VISIBLE I
  VISIBLE J
  N BIGR THAN 0, O RLY?
    YA RLY
      I R PRODUKT OF 10 AN N
      I R SUM OF I AN VAR
      J R DIFF OF 0 AN I
      VISIBLE I
      VISIBLE J
  OIC
  IZ VAR BIGR THAN 8?, GTFO, KTHX
KTHX
N SMALLR THAN 2, O RLY?
  YA RLY
    VISIBLE "100"
    VISIBLE "-100"
OIC
KTHXBAI

```

Similar to my Fortran 95 code, it sometimes outputs a same number twice, but the rules say nothing about this being illegal. Numbers are NOT output in order, bu the rules also say nothing about it.

You can run this code at: http://asgaard.co.uk/misc/loljs/#
> 0 votes

# Answer
# Scala 123 characters

This works but doesn't scale to use larger numbers.

```
def a(n:Int) {
    for (x<- -100 until 100) {
        var y=x/10
        var z=x-((x/10) * 10)
        if (x==n||(y==n&&n>0)||z==n){println(x)}
    }
}

```
> 0 votes

# Answer
# Ruby - 59 chars

```
n=gets.chomp;$><<(-100..100).select{|x|x.to_s.include?(n)}

```

**Ex:**

```
1.9.3p448 :046 >   n=gets;$><<(-100..100).select{|x|x.to_s.include?(n[0])}
9
[-99, -98, -97, -96, -95, -94, -93, -92, -91, -90, -89, -79, -69, -59, -49, -39, -29, -19, -9, 9, 19, 29, 39, 49, 59, 69, 79, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] => #<IO:<STDOUT>>
1.9.3p448 :047 >
1.9.3p448 :048 >
1.9.3p448 :049 >   n=gets;$><<(-100..100).select{|x|x.to_s.include?(n[0])}
0
[-100, -90, -80, -70, -60, -50, -40, -30, -20, -10, 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100] => #<IO:<STDOUT>>
1.9.3p448 :050 >
1.9.3p448 :051 >

```
> 0 votes

# Answer
# R - 71 69 chars

```
z = -100:100
j = abs(z)
h = function(x)
   z[j %% 10 == x | j > 9 & x == j %/% 10 %% 10 | x & j > 98 + x]

     > h(0)
     [1] -100  -90  -80  -70  -60  -50  -40  -30  -20  -10    0   10   20   30   40   50   60   70
    [19]   80   90  100
    > h(1)
     [1] -100  -91  -81  -71  -61  -51  -41  -31  -21  -19  -18  -17  -16  -15  -14  -13  -12  -11
    [19]  -10   -1    1   10   11   12   13   14   15   16   17   18   19   21   31   41   51   61
    [37]   71   81   91  100
    > h(2)
     [1] -92 -82 -72 -62 -52 -42 -32 -29 -28 -27 -26 -25 -24 -23 -22 -21 -20 -12  -2   2  12  20  21
    [24]  22  23  24  25  26  27  28  29  32  42  52  62  72  82  92

```
> 0 votes

# Answer
# Ruby - 75 characters

Emphasizing clarity over cleverness:

```
def f(n)
  puts (-100..100).select {|x| x.abs % 10 == n || x.abs / 10 == n && n > 0}.join(" ")
end

```
> 0 votes

# Answer
# Javascript (ECMAScript 6) - 83 Characters (excluding whitespace)

```
n=prompt()
s=''
f=x=>x%10==n|(x>9?f(x/10|0):0)
for(a=-1;a++<100;)
    if(f(a))
        s+=' '+a+' -'+a

```

Inputting `0` outputs:

```
" 0 -0 10 -10 20 -20 30 -30 40 -40 50 -50 60 -60 70 -70 80 -80 90 -90 100 -100"

```

Inputting `1` outputs:

```
" 1 -1 10 -10 11 -11 12 -12 13 -13 14 -14 15 -15 16 -16 17 -17 18 -18 19 -19 21 -21 31 -31 41 -41 51 -51 61 -61 71 -71 81 -81 91 -91 100 -100"

```
> 0 votes

# Answer
**haskell, ghci: 75 characters**

```
Prelude> let i='9'
Prelude> [x | x <- [-100..100], head (show x) == i || last (show x) == i]
[-99,-89,-79,-69,-59,-49,-39,-29,-19,-9,9,19,29,39,49,59,69,79,89,90,91,92,93,94,95,96,97,98,99]

```

It's a basic list comprehension that gets the range -100 to 100, then ( not sure if this was against the rules ) turns x into a char list and grabs the head and tail and compares it to i, which is the input, this acts as a filter for the range.
> 0 votes

# Answer
# Julia, 46

```
g(x)=filter((y)->x in digits(abs(y)),-100:100)
julia> g(9)'
1x38 Array{Int64,2}:
-99  -98  -97  -96  -95  -94  -93  …  91  92  93  94  95  96  97  98  99

```

Or 54 if I'm not allowed to return an array, seems like a silly restriction.

```
g(x)=(for y=-100:100;x in digits(abs(y))&&println(y);end)

```
> 0 votes

# Answer
# Java 123

```
N(int n){for(int i=-100;i<101;i++){int x=Math.abs(i);if(x%10==n||x>9&&x/10%10==n||x>99&&x/100%10==n)System.out.print(i+" ");}}

```

Since the question only asks for a function and not a whole program this should do. Full program:

```
class N
{
    N(int n)
    {
        for(int i=-100;i<101;i++)
        {
            int x=Math.abs(i);
            if( x % 10 == n || x > 9 && x / 10 % 10 == n || x > 99 && x / 100 % 10 == n )
            System.out.print(i + " ");
        }
    }

    public static void main(String[] a)
    {
        N n = new N(Integer.parseInt(a[0]));
    }
}

```
> 0 votes

# Answer
# Haskell, 155 124

That is, with only non-essential whitespace removed, everything else felt like cheating. The other Haskell answer broke both rules, so I decided to roll my own solution!

You didn't specify the order of the output, so I didn't to it in ascending order. I basically jumped to the relevant points on the number line, added either 1 or 10 ten times and printed each number.

```
t=(+10)
p=print
g x n f
 |n<10=p x>>p(-x)>>g(f x)(n+1)f
 |True=return()
f 0=g(-100)0 t>>p 0
f n=g(-10*n-9)0(+1)>>g(-90-n)0 t

```

Call like this:

```
λ> f 4
-49
49
-48
48
-47
47
-46
46
-45
45
-44
44
-43
43
-42
42
-41
41
-40
40
-94
94
-84
84
-74
74
-64
64
-54
54
-44
44
-34
34
-24
24
-14
14
-4
4

```
> 0 votes

# Answer
# Javascript

```
function a(b){for(i=-100;i<=100;i++){if((i+'').indexOf(b)>-1){console.log(i)}}}

```

Usage:

```
> a(3)
-93
-83
-73
-63
-53
-43
-39
-38
-37
-36
-35
-34
-33
-32
-31
-30
-23
-13
-3
3
13
23
30
31
32
33
34
35
36
37
38
39
43
53
63
73
83
93

```
> 0 votes

# Answer
**C, 99 (or 46)**

```
main(i,j){for(j=getchar()-48,i=101;i;)if(--i%10==j||i/10==j||(j<i&&i/10==j))printf("%d %d ",i,-i);}

```

results (0 twice , but that was not in the parameters):

```
100 -100 90 -90 80 -80 70 -70 60 -60 50 -50 40 -40 30 -30 20 -20 10 -10 0 0

```

but the question says all the numbers... not *only* the numbers, so you can just print all of them

```
main(i){for(i=101;i--;)printf("%d %d ",i,-i);}

```

results:

```
100 -100 99 -99 98 -98 97 -97 96 -96 95 -95 94 -94 93 -93 92 -92 91 -91 90 -90 89 -89 88 -88 87 -87 86 -86 85 -85 84 -84 83 -83 82 -82 81 -81 80 -80 79 -79 78 -78 77 -77 76 -76 75 -75 74 -74 73 -73 72 -72 71 -71 70 -70 69 -69 68 -68 67 -67 66 -66 65 -65 64 -64 63 -63 62 -62 61 -61 60 -60 59 -59 58 -58 57 -57 56 -56 55 -55 54 -54 53 -53 52 -52 51 -51 50 -50 49 -49 48 -48 47 -47 46 -46 45 -45 44 -44 43 -43 42 -42 41 -41 40 -40 39 -39 38 -38 37 -37 36 -36 35 -35 34 -34 33 -33 32 -32 31 -31 30 -30 29 -29 28 -28 27 -27 26 -26 25 -25 24 -24 23 -23 22 -22 21 -21 20 -20 19 -19 18 -18 17 -17 16 -16 15 -15 14 -14 13 -13 12 -12 11 -11 10 -10 9 -9 8 -8 7 -7 6 -6 5 -5 4 -4 3 -3 2 -2 1 -1 0 0

```
> 0 votes

# Answer
**Python2 - 54 chars**

```
def f(s):
    for i in range(-100, 100):
        if str(s) in str(i):
            print i,

```

Example:

```
Python 2.7.9 (default, Dec 11 2014, 04:42:00)
[GCC 4.9.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> def f(s):
...     for i in range(-100, 100):
...         if str(s) in str(i):
...             print i,
...
>>> f(0)
-100 -90 -80 -70 -60 -50 -40 -30 -20 -10 0 10 20 30 40 50 60 70 80 90

```

After removing all white spaces, we end up with these 54 chars:

```
deff(s):foriinrange(-100,100):ifstr(s)instr(i):printi,

```
> 0 votes

# Answer
# Scala (97)

```
def a(b:Int)=for(n←-100 to 100){val m=n.abs;if(b>0&&(m/100==b||m/10==b)||m-m/10*10==b)println(n)}

```

## Ungolfed

```
def a(b:Int)=
    for(n <- -100 to 100){
        val m=n.abs;
        if((b > 0 && (m/100==b || m/10==b)) || m-((m / 10) * 10) == b) {
            println(n)
        }
    }

```
> 0 votes

# Answer
# Excel VBA, 112 Chars

```
Sub a(n)
    For i = -100 To 100
        j = Abs(i)
        s = IIf(n * (n = j Mod 10 Or n = Int(j / 10) Or n = Int(j / 100)) Or n = i Mod 10, s & " " & i, s)
    Next
    Debug.? s
End Sub

```

Traditional PPCG Format, 132 Bytes

```
Sub a(n):For i=-100To 100:j=Abs(i):s=IIf(n*(n=j Mod 10 Or n=Int(j/10)Or n=Int(j/100))Or n=i Mod 10,s &" "&i,s):Next:Debug.?s:End Sub

```

note: +5 for `:` newlines in PPCG format

## Old Version, 99 Chars (Non-Competing)

Breaks rule against using strings

```
Sub a(n$)
    For i = -100 To 100
        j = Abs(i)
        s = IIf(n * (n = j Mod 10 Or n = Left(j, 1)) Or n = i Mod 10, s & " " & i, s)
    Next
    Debug.?s
End Sub

```

Traditional PPCG Format, 118 Bytes

```
Sub a(n$):For i=-100To 100:j=Abs(i):s=IIf(n*(n=j Mod 10 Or n=Left(j,1))Or n=i Mod 10,s &" "&i,s):Next:Debug.?s:End Sub

```

note: again, +5 for `:` newlines in PPCG format

## Usage

In the VBE Immediates Window

```
  For i = 0 To 9: Print i & ":": a (i): Next
0:
 -100 -90 -80 -70 -60 -50 -40 -30 -20 -10 0 10 20 30 40 50 60 70 80 90 100
1:
 -100 -91 -81 -71 -61 -51 -41 -31 -21 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -1 1 10 11 12 13 14 15 16 17 18 19 21 31 41 51 61 71 81 91 100
2:
 -92 -82 -72 -62 -52 -42 -32 -29 -28 -27 -26 -25 -24 -23 -22 -21 -20 -12 -2 2 12 20 21 22 23 24 25 26 27 28 29 32 42 52 62 72 82 92
3:
 -93 -83 -73 -63 -53 -43 -39 -38 -37 -36 -35 -34 -33 -32 -31 -30 -23 -13 -3 3 13 23 30 31 32 33 34 35 36 37 38 39 43 53 63 73 83 93
4:
 -94 -84 -74 -64 -54 -49 -48 -47 -46 -45 -44 -43 -42 -41 -40 -34 -24 -14 -4 4 14 24 34 40 41 42 43 44 45 46 47 48 49 54 64 74 84 94
5:
 -95 -85 -75 -65 -59 -58 -57 -56 -55 -54 -53 -52 -51 -50 -45 -35 -25 -15 -5 5 15 25 35 45 50 51 52 53 54 55 56 57 58 59 65 75 85 95
6:
 -96 -86 -76 -69 -68 -67 -66 -65 -64 -63 -62 -61 -60 -56 -46 -36 -26 -16 -6 6 16 26 36 46 56 60 61 62 63 64 65 66 67 68 69 76 86 96
7:
 -97 -87 -79 -78 -77 -76 -75 -74 -73 -72 -71 -70 -67 -57 -47 -37 -27 -17 -7 7 17 27 37 47 57 67 70 71 72 73 74 75 76 77 78 79 87 97
8:
 -98 -89 -88 -87 -86 -85 -84 -83 -82 -81 -80 -78 -68 -58 -48 -38 -28 -18 -8 8 18 28 38 48 58 68 78 80 81 82 83 84 85 86 87 88 89 98
9:
 -99 -98 -97 -96 -95 -94 -93 -92 -91 -90 -89 -79 -69 -59 -49 -39 -29 -19 -9 9 19 29 39 49 59 69 79 89 90 91 92 93 94 95 96 97 98 99

```
> 0 votes

# Answer
OOps. Fails the 0 test

# Python 160-70= 90

```
n = int(raw_input())
for x in xrange(-100,101):
    num = abs(x)
    while num:
        if n == num%10:
            print x
            break
        num /= 10

```

this is the old **wrong** code (see comments):

# Python 141 - 0 = 141

```
import re;n=raw_input('>');print "\n".join([str(j) for j in filter(lambda x:re.compile("-?.*"+str(n)+".*").match(str(x)),xrange(-100,101))])

```
> -1 votes

# Answer
# Java

```
    public static void main(String[] argv) {
    for(int i=-99;i<=99;i++)
    {
          int a,b;
          a=i/10;
          b=i%10;
          if(a==9||b==9||a==-9||b==-9){
              System.out.println(i);
                        }
    }
                                     }

```

JAVA:: O/P -99 -98 -97 -96 -95 -94 -93 -92 -91 -90 -89 -79 -69 -59 -49 -39 -29 -19 -9 9 19 29 39 49 59 69 79 89 90 91 92 93 94 95 96 97 98 99
> -1 votes

---
Tags: code-golf
---


title: Draw nested radicals

text:
# Question
Title: Draw nested radicals
Many formulas in math involve nested radicals (square root signs inside other square roots signs). Your task here is to draw these using ascii art.

# Specs

You will be given two integers, the number inside the radical, and the number of radicals. I think the best way to explain what you have to do is with an example. Here is the output for `2, 4`:

```
        ____________________
\      /       _______________
 \    /  \    /     __________
  \  /    \  /  \  /   _____
   \/      \/    \/  \/ 2

```

Here are some things to note:

* The height of each radical increases by one
* The length of the `_`'s are always `5` times the height
* There is a space after the last `/` and before the next inner radical starts
* The number inside will never be greater than 4 digits
* If the number of radicals is 0, just output the number
* Putting extra spaces to pad it into a rectangle is up to you
* This is , so shortest code in **bytes** wins!

# Test Cases

```
2, 4:
        ____________________
\      /       _______________
 \    /  \    /     __________
  \  /    \  /  \  /   _____
   \/      \/    \/  \/ 2

23, 0:
23

4, 1:
  _____
\/ 4

1234, 3:
      _______________
\    /     __________
 \  /  \  /   _____
  \/    \/  \/ 1234

```

# Answer
> 2 votes
## Python 3.5, ~~145~~ 137 bytes

```
def s(n,x):[([print(' '*j+'\\'+'  '*i+'/ '+' '*j,end='')for j in range(x-i-1,-1,-1)],print('  '*i+i*'_____'or n))for i in range(x,-1,-1)]

```

Slightly ungolfed:

```
def s(n,x):
    for i in range(x,-1,-1):
        for j in range(x-i-1,-1,-1):
            print(' '*j+'\\'+'  '*i+'/ '+' '*j,end='')
        print('  '*i+i*'_____' or n)

```

Output:

```
s(2,4)
        ____________________
\      /       _______________
 \    /  \    /     __________
  \  /    \  /  \  /   _____
   \/      \/    \/  \/ 2

```

# Answer
> 2 votes
# JavaScript, ~~133~~ ~~132~~ 131 bytes

```
f=(n,r,q=r)=>~r?'1\\0/1 '[x='repeat'](d=q-r).replace(/\d/g,i=>' '[x](+i?d-=.5:r*2))+(r?' '[x](r*2)+'_'[x](5*r):n)+`
`+f(n,r-1,q):''

F=(n,r)=>console.log( f(n,r) )
F(2,4)
F(23,0)
F(4,1)
F(1234,3)
```

```
.as-console-wrapper{max-height:100%!important;top:0}
```

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

```
f=(s,n,i=0,r=(n,c=` `)=>c.repeat(n))=>n?r(n+n)+r(n*5,`_`)+`
`+f(s,n-1).replace(/^/gm,_=>r(i)+`\\${r(n+~i<<1)}/`+r(++i)):s+``
```

```
<div oninput=o.textContent=f(s.value,+n.value)><input id=s><input id=n type=number min=0><pre id=o>
```

Save 3 bytes if the first parameter can be a string rather than a number.

# Answer
> 1 votes
# PHP, 178 bytes

```
for($r=[" $argv[1]"];$i++<$argv[2];$r[]=$p("",2*$i).$p(_,5*$i,_))for($k=-1;++$k<$i;)$r[$k]=($p=str_pad)("\\".$p("",2*$k)."/",2*$i," ",2).$r[$k];echo join("\n",array_reverse($r));

```

bah that´s awfully long.

---
Tags: code-golf, math, ascii-art
---


title: It's factors all the way down!

text:
# Question
Title: It's factors all the way down!
This challenge is inspired by this fantastic animated diagram (thanks to flawr for posting it in chat).

Given an input `n`, draw all of its prime factors as nested polygons of dots, as specified.

For example, given the number `357 = 17x7x3`, you arrange 3 dots in a triangle, 7 versions of those triangles in a heptagon, and 17 versions of those heptagons in a 17-gon. In short, nested polygons going from the largest prime factor on the outside to the smallest on the inside. For `357`, your answer should look a little like this (with or without color):

Every polygon of every prime `>= 3` should not be rotated around the diagram.

The only exception is the prime `2`, specifically for odd powers of `2`. As you can see in the example for `376 = 47x2x2x2` below, the `8`s rotate and are not single lines of `2`s, but are vertical stacks for `4`s in a square. Even powers of `2`, arranged in squares, do not need to be rotated in this way.

In fact, `448 = 7x2x2x2x2x2x2` has a diagram that looks like a heptagon of `64`s, and `64` is arranged into a square of squares of squares, but without rotation.

Two more examples are `440 = 11x5x2x2x2` and `432 = 3x3x3x2x2x2x2`. We see that `440` with an odd power of 2, has rotated `8`s, but `432` with an even power of `2` does not rotate its `16`s.

And finally, here is a minimal example, `10 = 5x2`, without color that I mocked up with Python and its `turtle` module.

**The challenge**

* Given an input `n` where `1 <= n <= 10000`, output an image of its nested factor polygons.
* Rules are:
    + The image is made up of nested polygons of dots, from a polygon with (the largest prime factor) sides on the outside to the smallest prime factor on the inside.
    + For the factor 2, the powers of 2 should stack as a line, then a squares, then a line of squares, and so on. Even powers of 2 should not be rotated. Odd powers of 2 should be rotated around their respective polygons, and they should be stacked vertically before rotation.
* You may orient the image however you like (though I prefer up), but every nested polygon should be facing the same direction as any other polygon with the sole exception of odd powers of 2.
* You have two options for image size and dot size:
    + The image size is static and the dot size decreases as `n` increases (as in the animation).
    + The dot size is static and the image size grows as `n` increases.
* The first **three** layers of polygons should be distinguishable from neighboring polygons (i.e. not touching), but considering the size of the images at and around `n=10000`, it's okay if the layers after start to touch. I'd prefer it if they didn't, but it may be unavoidable to fit on an image that is uploadable to Stack Exchange.
* Color is optional.
* The shape of the dots is up to you. If squares are better for your language, use those.
* No bonuses, but I would like to see someone animate and color the diagrams like in the original post.

Thanks to Conor O'Brien, EasterlyIrk, Martin Ender, Kritixi Lithos, Mego, DJ McMayhem, and El'endia Starman for their help in writing this question.

This code golf, so shortest code wins. Good luck and good golfing!

# Answer
# Python 3.5, ~~331~~ ~~309~~ ~~308~~ ~~306~~ 304 bytes

It took quite a bit of messing with the spacing of the polygons (and the specification, too, to be honest) to get this answer to work, but I finally did it and hopefully other answers can start coming in.

**Edit:** -2 bytes thanks to FlipTack. -8 bytes from removing a section of code that I forgot to remove earlier. -12 bytes from golfing the last function. -1 byte from changing the circumference of the drawings from `size=2500` to `size=2e3`, which also allows the drawings to better fit on screens (`diameter ~= 795.77` down to `diameter ~= 636.62`). -2 bytes from fixing a bug. -2 bytes from restructuring how I build `a`.

Golfing suggestions welcome. Trinket for testing and images to follow shortly.

```
from math import*
from turtle import*
ht();pu()
def g(n):
 i=1;a=[]
 while n%4<1:a+=4,;n//=4
 while n>1:
  i+=1
  while n%i<1:a+=i,;n//=i
 return f(a,2e3)
def f(a,s,x=0,y=0,t=0):
 if a:
  *c,b=a;s/=b
  for i in range(b):u=2*pi*i/b+t*(b<3)+pi/4*(b==4);f(c,s,x+s*sin(u),y+s*cos(u),u)
 else:goto(x,y);dot(4)

```

Here's `g(448)`, which now fits on my 1366x768 screen.

**Ungolfing**

```
import math
import turtle

turtle.hideturtle()     # don't display the turtle itself)
turtle.penup()          # don't draw lines, just dots later on

def g(n):
    i = 1
    a = []
    while n % 4 == 0:   # get 4's into the list first,
        a = a + [4]     # so that the fractal will be easier to structure
        n = n // 4
    while n > 1:        # now get all of the other factors (including any stray 2's)
        i += 1
        while n % i == 0:
            a = a + [i]
            n = n // i
    return f(a, 2000)   # 2000 is the circumference of the circle
                        # on which we draw the polygons
def f(a, s, x=0, y=0, t=0):
    if a:
        c = a[-1]       # the size of the current outermost polygon
        b = a[:-1]      # the rest of the factors for recursion
        s = s/b         # the current circumference / the number of polygons at this layer
        for i in range(b):
            u = 2*math.pi*i/b   # angle around the circle
            if b == 2:          # if b == 2, add the previous angle to rotate the structure
                u += t
            if b == 4:          # if b == 4, add 45 degrees to keep the squares upright
                u += math.pi/4
            dx = s * math.sin(u)    # our coordinate changes for this polygon
            dy = s * math.cos(u)
            f(c, s, x+dx, y+dy, u)  # call the function again
                                    # on a new circle with new starting coordinates
    else:                   # when we run out of factors,
        turtle.goto(x,y)    # go to each coordinate
        turtle.dot(4)       # and draw a dot

```
> 10 votes

---
Tags: code-golf, graphical-output, primes, fractal
---


title: Optimal cheating at BINGO

text:
# Question
Title: Optimal cheating at BINGO
You're sick of other players smugly announcing "BINGO" and walking triumphantly past you to claim their prize. This time it will be different. You bribed the caller to give you the BINGO calls ahead of time, in the order they will be called. Now you just need to create a BINGO board that will win as early as possible for those calls, guaranteeing you a win (or an unlikely tie).

Given a delimited string or list of the calls in order, in typical BINGO format (letters included, e.g. `B9` or `G68`, see the rules for more info), output a matrix or 2D list representing an optimal BINGO board for those calls. Assume input will always be valid.

### BINGO Rules:

* 5x5 board
* A "BINGO" is when your card has 5 numbers in a row from the numbers that have been called so far.
* The center square is free (automatically counted towards a BINGO), and may be represented by whitespace, an empty list, `-1`, or `0`.
* The 5 columns are represented by the letters `B`,`I`,`N`,`G`,`O`, respectively.
* The first column may contain the numbers 1-15, the second 16-30, ..., and the fifth 61-75.
* The letters and numbers taken for input may optionally be delimited (by something that makes sense, like a `,` or space) or taken as a tuple of a character and a number.
* Output requires only numbers in each place in the matrix.
* Squares that will not contribute to your early BINGO must be valid, but do not have to be optimal.
* **This is code-golf, shortest code wins**

### Examples:

I'm using this input format for the examples, because it's shorter. See the section above for acceptable input/output formats.

```
O61 B2 N36 G47 I16 N35 I21 O64 G48 O73 I30 N33 I17 N43 G46 O72 I19 O71 B14 B7 G50 B1 I22 B8 N40 B13 B6 N37 O70 G55 G58 G52 B3 B4 N34 I28 I29 O65 B11 G51 I23 G56 G59 I27 I25 G54 O66 N45 O67 O75 N42 O62 N31 N38 N41 G57 N39 B9 G60 I20 N32 B15 O63 N44 B10 I26 O68 G53 I18 B12 O69 G49 B5 O74 I24

Possible Output (this has a horizontal BINGO in 3rd row. A diagonal is also possible.):
[[11,25,42,53,68],
 [ 6,22,32,57,62],
 [ 2,16, 0,47,61],
 [ 3,17,37,59,75],
 [ 9,19,41,46,70]]

N42 N34 O66 N40 B6 O65 O63 N41 B3 G54 N45 I16 O67 N31 I28 B2 B14 G51 N36 N33 I23 B11 I17 I27 N44 I24 O75 N38 G50 G58 B12 O62 I18 B5 O74 G60 I26 B8 I22 N35 B1 B4 G53 O73 G52 O68 B10 O70 I30 G59 N43 N39 B9 G46 G55 O64 O61 I29 G56 G48 G49 I19 G57 N37 O72 I25 N32 B13 B7 B15 O71 I21 I20 O69 G47

Must be a vertical BINGO in 3rd (N) column (because 4 N's came before one of each B,I,G,O):
[[11,25,42,53,63],
 [ 2,22,34,57,65],
 [ 6,16, 0,47,66],
 [ 3,17,41,54,75],
 [ 9,19,40,46,70]]

```

# Answer
> 4 votes
# Mathematica, 302 bytes

```
(b=Prepend;i=1;n=15#&@@#-15+Range@5&;g=#~b~{N,0};o={#2,#3,#,##4}&@@#&;While[(l=Length@Union[t=(k=Take)[#&@@@g,i]])<5&&Max[#2&@@@Tally@t]<5,i++];If[l<5,m=#&@@Commonest@t;If[m===#,o[g~k~i/.{m,x_}->x/.{_,_}->Nothing],n@#2]&,o@DeleteDuplicates@b[n@#2,<|#->#2&@@@Reverse@g|>@#]~k~5&]~MapIndexed~{B,I,N,G,O})&

```

Unnamed function taking as its argument a list of ordered pairs, such as `{{N,42},{N,34},{O,66},{N,40},...}` (note that the first element in each ordered pair is not a string but rather a naked symbol), and returning a 2D list of integers, where the sublists represent columns (not rows) of the bingo board.

Output for the first test case:

```
{{1,3,2,4,5},{17,18,16,19,20},{31,32,0,33,34},{46,48,47,49,50},{62,63,61,64,65}}

```

In general, when the earliest possible bingo occurs because of a number called in each of the B/I/G/O rows, then those numbers will be in the center row; each column will otherwise contain the four smallest possible numbers (taking the already used number into account). For example, if the first test case is changed so that the second number called is `B12` rather than `B2`, then the first column of the output board will be `{1,2,12,3,4}`.

Output for the second test case:

```
{{1,2,3,4,5},{16,17,18,19,20},{42,34,0,40,41},{46,47,48,49,50},{61,62,63,64,65}}

```

In general, when the earliest possible bingo occurs because of five numbers called in a single column (or four called in the N column), then the remaining four columns contain their five smallest possible numbers in order.

If the second test case is changed from `{{N,42},{N,34},{O,66},{N,40},...}` to `{{O,72},{O,74},{O,66},{N,40},...}` (only the first two entries changed), then the output is:

```
{{1,2,3,4,5},{16,17,18,19,20},{31,32,33,34,35},{46,47,48,49,50},{74,66,72,65,63}}

```

Somewhat ungolfed version:

```
(b=Prepend;i=1;n=15First[#]-15+Range[5]&;g=b[#,{N,0}];o={#2,#3,#,##4}&@@#&;
While[
    (l=Length[Union[t=(k=Take)[Apply[#&,g,{1}],i]]])<5
  &&
    Max[Apply[#2&,Tally[t],{1}]]<5,
  i++];
MapIndexed[
  If[l<5,
    m=First[Commonest[t]];If[m===#,o[k[g,i]/.{m,x_}->x/.{_,_}->Nothing],n[#2]]&,
    k[
      o[DeleteDuplicates[b[n[#2],Association[Apply[#->#2&,Reverse[g],{1}]][#]]]]
    ,5]&
  ],{B,I,N,G,O}
])&

```

The first line is mostly definitions to shorten the code, although `g` prepends the center square `{N,0}` to the input to simplify the bingo-finding. (The `n` function gives the smallest five legal bingo numbers in the `#`th column, 1-indexed. The `o` function takes a 5-tuple and moves the first element so that it's third.)

The `While` loop in lines 2-6 finds the smallest initial segment of the input that contains a bingo. (The third line tests for one-in-each-column bingos, while the fifth line tests for single-column bingos).

For any function `F`, the operator `MapIndexed[F,{B,I,N,G,O}]` (starting in line 7) produces the 5-tuple `{F{B,1},F{I,2},F{N,3},F{G,4},F{O,5}}` (well, technically it's `{F{B,{1}},...}`); we apply a function `F` that creates a bingo-board column out of its two arguments. That function, however, depends on which type of bingo was found: line 8 is true when we have a single-column bingo, in which case the function (line 9) uses the relevant input numbers in the bingo column and default numbers in the other columns. In the other case, the function (lines 10-12) uses the relevant input numbers in the center of each column and default numbers elsewhere.

# Answer
> 3 votes
# JavaScript (ES6) 372 Bytes

Can probably still be golfed a bit, but I don't see how. Suggestions are much appreciated ;)

```
A=a=>[1,2,3,4,5].map(x=>x+15*a),F=a=>{b=[[],[],[i=0],[],[]],a.replace(/[^0-9 ]/g,"").split` `.some(x=>{b[--x/15|(c=0)].push(++x);return b.some((x,i)=>(d=x.length)>4||d==1&i-2&&++c>3)});for(e=[A(0),A(1),A(2),A(3),A(4)];i<5;a=b[i][0],b[i][0]=b[i][2],b[i++][2]=a)for(j=0;j<5&b[i].length<5;j++)b[i][j]<i*15+5?e[i].splice(e[i].indexOf(b[i][j]),1):b[i][j]=e[i].shift();return b}

```

---
Tags: code-golf
---


title: How much can you quickly multiply?

text:
# Question
Title: How much can you quickly multiply?
With the recent Python bashing, here's an attempt to show Python's strengths. Your challenge is to write a program that calculates the factorial of as high a number `n` as possible within 10 seconds.

Your score will be `(highest n for your program on your machine)/(highest n for my program on your machine)`

## Rules

* You must calculate an exact integer solution. Since the factorial would be much higher than what can fit in a 64 bit unsigned integer, you can use strings if your language does not support large integers
* Standard loopholes are forbidden. Particularly, you cannot use any external resources.
* Only the calculation part(this includes time for any workarounds using strings) adds to the total time which should be under 10 seconds on average.
* Single threaded programs only.
* You must store the output in an easily printable form (as printing takes time) (see my program below), string, variable, character array, etc.

EDIT:

* Your program must give the correct output for all `n`: `1 <= n <= (your highest n)`

EDIT2:

---

## My program

```
from __future__ import print_function
import time

def factorial( n ):
    return reduce( ( lambda x , y : x * y ) , xrange( 1 , n + 1 ) , 1 )

start = time.clock()
answer = factorial( 90000 )
end = time.clock()

print ( answer )
print ( "Time:" , end - start , "sec" )

```

---

Highest score wins. For the record, my code can manage `n = 90000` in about `9.89` seconds on a Pentium 4 3.0 GHz

---

**EDIT:** Can everyone please add the *score* rather than just the highest *n*. Just the highest `n` has no meaning by itself as it depends on your hardware. It's impossible to have an objective winning criterion otherwise. ali0sha's anwer does this correctly.

---

We have a winner. I didn't accept the java answer https://codegolf.stackexchange.com/a/26974/8766 as it kind of skirts close to http://meta.codegolf.stackexchange.com/a/1080/8766

# Answer
> 8 votes
## C++ with GMP, score = 55.55 (10,000,000 / 180,000)

```
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <queue>
#include <gmpxx.h>

int main(int argc, char *argv[]) {
  uint64_t n = atoi(argv[1]);

  // Iterate through 1..n.  Strip off powers of 2.  Multiply
  // remainders together into <= 64 bit chunks.
  uint64_t twos = 0;
  std::vector<uint64_t> terms;
  uint64_t m = 1;
  for(uint64_t i = 1; i <= n; i++) {
    uint64_t j = __builtin_ctzll(i);
    twos += j;
    uint64_t k = i >> j;
    if(__builtin_clzll(m) + __builtin_clzll(k) >= 64) {
      m *= k;
    } else {
      terms.push_back(m);
      m = k;
    }
  }
  if(m != 1) terms.push_back(m);

  // convert to gmp
  // why isn't there a 64-bit constructor?
  std::queue<mpz_class> gmpterms;
  for(int i = 0; i < terms.size(); i++) {
    mpz_class x = (uint32_t)(terms[i] >> 32);
    x <<= 32;
    x += (uint32_t)terms[i];
    gmpterms.push(x);
  }

  // pop two from the bottom, multiply them, push on the end.
  while(gmpterms.size() > 1) {
    mpz_class a = gmpterms.front();
    gmpterms.pop();
    mpz_class b = gmpterms.front();
    gmpterms.pop();
    gmpterms.push(a * b);
  }

  mpz_class r = gmpterms.front();
  r <<= twos;
  //std::cout << r << std::endl;
}

```

# Answer
> 8 votes
# Python 2.7

# 42.575 = ( 6,812,000 / 160,000 ) *approx*

---

### Code:

```
import gmpy2

def fac1(n):
    m=lambda(L):([]if len(L)%2==0 else[L.pop()])+map(lambda(l):l[0]*l[1],zip(L[1::2],L[-2::-2]))
    L=map(gmpy2.mpz,xrange(1,n+1))
    Number = (len(L)-1).bit_length()
    while Number:Number-=1;L=m(L)
    return L[0]

def fac2(n):
    global E; E=0
    def f(i):
        global E; E+=i//2
        return[]if i==1 else f(i//2)+range(3,i,2)+[[1,i][i%2]]
    m=lambda(L):([]if len(L)%2==0 else[L.pop()])+map(lambda(l):l[0]*l[1],zip(L[1::2],L[-2::-2]))
    L=map(gmpy2.mpz,f(n))
    N=(len(L)-1).bit_length()
    while N: N-=1;L=m(L)
    return L[0]<<E

```

### Test:

```
import time

start = time.time()
baseline(160000)
print time.time()-start

start = time.time()
fac1(6811000)
print time.time()-start

start = time.time()
fac2(6812000)
print time.time()-start

start = time.time()
gmpy2.fac(26000000)
print time.time()-start

```

### Output:

```
10.0069999695
10.0729999542
10.0360000134
9.98699998856

```

### How it works:

Bigger multiplications take more time, thus we want to do as many small multiplications as possible. This is especially true in Python where for numbers less that `2^64` we use hardware arithmetic, and above that we use software. So, in `m(L)`, we start with a list `L`; if it's odd length we remove one number from consideration to make it even again. Then we multiply element `1` with element `-2`, element `3` with `-4`, etc, so that

```
m([1,2,3,4,5,6,7,8]) = [2*7, 4*5, 6*3, 8*1] = [14, 20, 18, 8]
m([10,12,6]) = [360,112]
m([120,6]) = [40320]

```

This approach ensures we're using hardware arithmetic for as long as possible, following which we switch onto the efficient gmc arithmetic library.

In `fac2`, we take a more classic divide and conquer approach as well, where we split out every multiple of 2 and bitshift them at the end for a trivial performance boost. I've included it here because it's usually around 0.5% faster than `fac1`.

### Golfed Version of `fac1` (because I can), 220B

```
import gmpy2
def f(n):
    m=lambda(L):([]if len(L)%2==0 else[L.pop()])+map(lambda(l):l[0]*l[1],zip(L[1::2],L[-2::-2]))
    L=map(gmpy2.mpz,xrange(1,n+1));N=(len(L)-1).bit_length()
    while N:N-=1;L=m(L)
return L[0]

```

# Answer
> 3 votes
# Java - 125.15 (21,400,000 / 171,000)

Also shamelessly copied from Peter Luschny's Github repo (thanks @semi-extrinsic) and licensed under the MIT license, this uses the "prime factorization nested squaring" algorithm as proposed by Albert Schönhage et al. (according to Luschny's factorial algorithms description page).

I slightly adapted the algorithm to use Java's BigInteger and to not use a lookup table for n \< 20.

Compiled with gcj, which uses GMP for its BigInteger implementation, and ran on Linux 3.12.4 (Gentoo), on a Core i7 4700MQ at 2.40GHz

```
import java.math.BigInteger;

public class PrimeSieveFactorialSchoenhage {

    private static int[] primeList, multiList;

    public static BigInteger factorial(int n) {
        int log2n = 31 - Integer.numberOfLeadingZeros(n);
        int piN = log2n < 2 ? 1 : 2 + (15 * n) / (8 * (log2n - 1));

        primeList = new int[piN];
        multiList = new int[piN];

        int len = primeFactors(n);
        return nestedSquare(len).shiftLeft(n - Integer.bitCount(n));
    }

    private static BigInteger nestedSquare(int len) {
        if (len == 0) {
            return BigInteger.ONE;
        }

        int i = 0, mult = multiList[0];

        while (mult > 1) {
            if ((mult & 1) == 1) { // is mult odd ?
                primeList[len++] = primeList[i];
            }

            multiList[i++] = mult / 2;
            mult = multiList[i];
        }
        BigInteger ns = nestedSquare(i);
        if (len <= i) {
            return ns.multiply(ns);
        }

        return product(primeList, i, len - i).multiply(ns.multiply(ns));
    }

    private static BigInteger product(int[] a, int start, int length) {
        if (length == 0) {
            return BigInteger.ONE;
        }

        int len = (length + 1) / 2;
        long[] b = new long[len];

        int i, j, k;

        for (k = 0, i = start, j = start + length - 1; i < j; i++, k++, j--) {
            b[k] = a[i] * (long) a[j];
        }

        if (i == j) {
            b[k++] = a[j];
        }

        return recProduct(b, 0, k - 1);
    }

    private static BigInteger recProduct(long[] s, int n, int m) {
        if (n > m) {
            return BigInteger.ONE;
        }
        if (n == m) {
            return BigInteger.valueOf(s[n]);
        }
        int k = (n + m) >> 1;
        return recProduct(s, n, k).multiply(recProduct(s, k + 1, m));
    }

    private static int primeFactors(int n) {
        int[] primes = new int[n < 17 ? 6 : (int) Math.floor(n / (Math.log(n) - 1.5))];
        int numPrimes = makePrimeList(n, primes);

        int maxBound = n / 2, count = 0;

        int start = indexOf(primes, 2, 0, numPrimes - 1);
        int end = indexOf(primes, n, start, numPrimes);

        for (int i = start; i < end; i++) {
            int prime = primes[i];
            int m = prime > maxBound ? 1 : 0;

            if (prime <= maxBound) {
                int q = n;
                while (q >= prime) {
                    m += q /= prime;
                }
            }

            primeList[count] = prime;
            multiList[count++] = m;
        }
        return count;
    }

    private static int indexOf(final int[] data, int value, int low, int high) {
        while (low < high) {
            int mid = (low + high) >>> 1;

            if (data[mid] < value) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        if (low >= data.length) {
            return low;
        }

        if (data[low] == value) {
            low++;
        }

        return low;
    }

    private static int makePrimeList(int n, int[] prime) {
        boolean[] composite = new boolean[n / 3];

        sieveOfEratosthenes(composite);

        boolean toggle = false;
        int p = 5, i = 0, j = 2;

        prime[0] = 2;
        prime[1] = 3;

        while (p <= n) {
            if (!composite[i++]) {
                prime[j++] = p;
            }
            // -- never mind, it's ok.
            p += (toggle = !toggle) ? 2 : 4;
        }

        return j; // number of primes
    }

    private static void sieveOfEratosthenes(final boolean[] composite) {
        int d1 = 8;
        int d2 = 8;
        int p1 = 3;
        int p2 = 7;
        int s1 = 7;
        int s2 = 3;
        int n = 0;
        int len = composite.length;
        boolean toggle = false;

        while (s1 < len) { // -- scan sieve
            if (!composite[n++]) { // -- if a prime is found, cancel its multiples
                int inc = p1 + p2;

                for (int k = s1; k < len; k += inc) {
                    composite[k] = true;
                }

                for (int k = s1 + s2; k < len; k += inc) {
                    composite[k] = true;
                }
            }

            if (toggle = !toggle) { // Never mind, it's ok.
                s1 += d2;
                d1 += 16;
                p1 += 2;
                p2 += 2;
                s2 = p2;
            } else {
                s1 += d1;
                d2 += 8;
                p1 += 2;
                p2 += 6;
                s2 = p1;
            }
        }
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        long nanos = System.nanoTime();
        BigInteger fact = factorial(n);
        nanos = System.nanoTime() - nanos;
        // Commented out because it takes ages to print
        //System.out.println(fact);
        System.out.println(nanos / 1e9);
    }
}

```

# Answer
> 2 votes
## Perl + C, n = about 3 million

Here I'm using the Math::BigInt::GMP library available on CPAN, which provides a massive speed boost for Perl's core Math::BigInt objects.

```
use v5.14;
use Time::HiRes 'time';
use Math::BigInt only => 'GMP';

sub factorial { Math::BigInt::->new(@_)->bfac }

my $start  = time;
my $answer = factorial( 3_000_000 );
my $end    = time;

say $answer;
say "Time: ", $end - $start, " sec";

```

Bear in mind that my computer is probably quite a bit slower than yours. Using your original Python script, I can only calculate `factorial(40000)` in 10 seconds; `factorial(90000)` takes a lot longer. (I hit Ctrl+C after a minute.) On your hardware, using Math::BigInt::GMP, **you** may well be able to calculate the factorial of **5 million or more** in under 10 seconds.

One thing you may notice is that although the factorial is calculated incredibly quickly, printing out the result is very slow, taking about three times longer than the original calculation. This is because GMP internally uses a binary rather than decimal representation, and printing it out requires binary to decimal conversion.

# Answer
> 2 votes
**Python 2.7<br>5.94 = 1'200'000/202'000**

```
def fast_fac(n):
    def prod(start, fin):
            if fin - start <= 50:
                    return reduce(lambda x,y: x*y, xrange(start, fin+1), 1)
            else:
                    mid = (start+fin) / 2
                    return prod(start, mid) * prod(mid+1, fin)
    return prod(1, n)

```

Makes use of relative ease of multiplication of many groups of small numbers and then multiplying them compared to large number of multiplyings involving huge number.

# Answer
> 2 votes
# bc, score=0.19

What the heck, here's my contender for **"How much can you slowly multiply?"**

bc *is* "An arbitrary precision calculator language", but unfortunately rather slow:

```
n=read()
for(f=i=1;i<=n;i++)f*=i
f
quit

```

In about 10 seconds on my mid 2012 MacBook Pro (2.3 GHz Intel Core i7) the reference python answer can calculate 122000!, but this bc script can only calculate 23600!.

Conversely 10000! takes 1.5s with the python reference script, but the bc script takes 50s.

Oh dear.

# Answer
> 2 votes
## Bash: score = 0.001206 (181/150000)

I stole the math functions from Rosettacode - Long multiplication I didn't analyzed nor tried to optimize.
You are free to change the algorithm or to try a different strings split method.

```
#!/bin/bash

add() { # arbitrary-precision addition
  if (( ${#1} < ${#2} )); then
    local a="$2" b="$1" sum= carry=0
  else
    local a="$1" b="$2" sum= carry=0
  fi

  while (( ${#a} )); do
    local -i d1="${a##${a%?}}" d2="10#0${b##${b%?}}" s=carry+d1+d2
    sum="${s##${s%?}}$sum"
    carry="10#0${s%?}"
    a="${a%?}" b="${b%?}"
  done
  echo "$sum"
}

multiply() { # arbitrary-precision multiplication
  if (( ${#1} < ${#2} )); then
    local a="$2" b="$1" product=0
  else
    local a="$1" b="$2" product=0
  fi

  local zeroes=
  while (( ${#b} )); do
    local m1="$a"
    local m2="${b##${b%?}}"
    local partial=$zeroes
    local -i carry=0
    while (( ${#m1} )); do
      local -i d="${m1##${m1%?}}"
      m1="${m1%?}"
      local -i p=d*m2+carry
      partial="${p##${p%?}}$partial"
      carry="10#0${p%?}"
    done
    partial="${carry#0}$partial"
    product="$(add "$product" "$partial")"
    zeroes=0$zeroes
    b="${b%?}"
  done
  echo "$product"
}

# 'timerun' function
trap 'echo $((i -1)) $f; exit'  USR1
(sleep 9.9; kill -USR1 $$)&

declare -i i
f=1
for ((i=1; i< 10000 ; i++ ))   # 10000 is verry optimistic
do
    f=$(multiply $f $i)
done

```

# Answer
> 1 votes
# C++ (x86\_64-specific) - 3.0 (390000/130000)

(easily portable to x86-32, porting to other architectures implies a significant speed loss)

Here's my own micro-implementation of long arithmetic.
The calculation itself takes 10 seconds, and while the output is in easily printable form (see the `operator<<` overload), it takes some more time to print it.

```
#include <vector>
#include <iostream>
#include <stdint.h>
#include <ctime>

typedef uint64_t digit;
typedef std::vector<digit> number;

std::ostream &operator<<(std::ostream &s, const number &x)
{
    std::vector<char> o;
    size_t size = x.size() * 21;
    o.resize(size);
    size_t lud = 0;
    for(number::const_reverse_iterator i = x.rbegin(), end = x.rend(); i != end; i++)
    {
        digit carry = 0;
        int j;
        for(j = 0; j <= lud || carry; j++)
        {
            digit r = o[j] * (1LL << 32) + carry;
            o[j] = r % 10;
            carry = r / 10;
        }
        lud = j;
        carry = 0;
        for(j = 0; j <= lud || carry; j++)
        {
            digit r = o[j] * (1LL << 32) + carry;
            o[j] = r % 10;
            carry = r / 10;
        }
        lud = j;
        carry = *i;
        for(j = 0; carry; j++)
        {
            digit r = o[j] + (carry % 10);
            carry /= 10;
            carry += r / 10;
            o[j] = r % 10;
        }
        if(j > lud)
            lud = j;
    }
    for(int j = lud; j--;)
        s.put(o[j] + '0');
    return s;
}

inline uint64_t dmul(uint64_t x, uint64_t y, uint64_t &carry)
{
    asm("mulq %2" : "+a"(x), "=d"(carry) : "r"(y));
    return x;
}
inline digit dadd(digit x, digit y, digit &carry)
{
    asm("movq $0, %1; addq %2, %0; adcq %1, %1" : "+r"(x), "=r"(carry), "+r"(y));
    return x;
}

void multiply(number &x, digit y)
{
    x.resize(x.size() + 2);
    digit carry = 0;
    for(number::iterator i = x.begin(), end = x.end(); i != end; i++)
    {
        digit nc, res = dmul(*i, y, nc);
        *i = dadd(res, carry, carry);
        carry += nc;
    }
    size_t sz = x.size();
    for(number::const_reverse_iterator i = x.rbegin(), end = x.rend(); i != end; i++)
    {
        if(*i)
            break;
        sz--;
    }
    x.resize(sz);
}

int main()
{
    const int r = 390000;
    clock_t start = clock();
    number n;
    digit mult = 1;
    n.push_back(1);
    for(digit a = 2; a <= r; a++)
    {
        digit carry, m = dmul(mult, a, carry);
        if(carry)
        {
            multiply(n, mult);
            mult = a;
        }
        else
            mult = m;
    }
    multiply(n, mult);
    std::cout << "Took: " << (clock() - start)/((double)CLOCKS_PER_SEC) << std::endl;
    std::cout << n << std::endl;
}

```

# Answer
> 1 votes
# C#: 0,48 (77,000 / 160,000)

I'm not happy with this.

Is C# that slow?

But here is my entry anyway.

```
static void Main(string[] args)
    {
        Console.WriteLine("Enter N for fatorial:");
        int n = Convert.ToInt32(Console.ReadLine());

        Stopwatch s = Stopwatch.StartNew();

        BigInteger result = 1;
        while (0 <-- n) result *= n;

        s.Stop();

        Console.WriteLine("Output: {0} ", result);

        Console.WriteLine("Completed in {0}", s.Elapsed);

    }

```

When n = 77000 it takes `00:00:09:8708952` to calculate.

I'm running in Release mode, outside Visual Studio, using a Core i3-2330M @2.2GHz.

**Edit:** Since i'm not doing anything intelligent, I accept that result. Maybe the .NET Framework 4.5 is addind some overhead (or BigInteger isn't that fast).

# Answer
> 1 votes
# Python 3, advanced algo by Peter Luschny: 8.25x (1 280 000/155 000)

Shamelessly copied from Peter Luschny,
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm,
who provides this code under the "Creative Commons Attribution-ShareAlike 3.0" license.

This is actually a quite advanced algorithm, using something called the "swinging factorial" and a list of primes. I suspect it could be even faster if it did like many of the other answers and performed most of the multiplications with 32 bit integers.

```
#! /usr/bin/python3
import time
import bisect

def Primes(n) :
  primes = [2, 3]
  lim, tog = n // 3, False
  composite = [False for i in range(lim)]

  d1 = 8; d2 = 8; p1 = 3; p2 = 7; s = 7; s2 = 3; m = -1

  while s < lim :             # --  scan the sieve
      m += 1                  # --  if a prime is found
      if not composite[m] :   # --  cancel its multiples
          inc = p1 + p2
          for k in range(s,      lim, inc) : composite[k] = True
          for k in range(s + s2, lim, inc) : composite[k] = True

          tog = not tog
          if tog: s += d2; d1 += 16; p1 += 2; p2 += 2; s2 = p2
          else:   s += d1; d2 +=  8; p1 += 2; p2 += 6; s2 = p1

  k, p, tog = 0, 5, False
  while p <= n :
      if not composite[k] : primes.append(p)
      k += 1;
      tog = not tog
      p += 2 if tog else 4

  return primes

def isqrt(x):
  '''
  Writing your own square root function
  '''
  if x < 0: raise ValueError('square root not defined for negative numbers')
  n = int(x)
  if n == 0: return 0
  a, b = divmod(n.bit_length(), 2)
  x = 2**(a + b)
  while True:
      y = (x + n // x) // 2
      if y >= x: return x
      x = y

def product(s, n, m):
  if n > m: return 1
  if n == m: return s[n]
  k = (n + m) // 2
  return product(s, n, k) * product(s, k + 1, m)

def factorialPS(n):

  small_swing = [1,1,1,3,3,15,5,35,35,315,63,693,231,3003,429,6435,6435,
          109395,12155,230945,46189,969969,88179,2028117,676039,16900975,
          1300075,35102025,5014575,145422675,9694845,300540195,300540195]

  def swing(m, primes):
      if m < 33: return small_swing[m]

      s = bisect.bisect_left(primes, 1 + isqrt(m))
      d = bisect.bisect_left(primes, 1 + m // 3)
      e = bisect.bisect_left(primes, 1 + m // 2)
      g = bisect.bisect_left(primes, 1 + m)

      factors = primes[e:g]
      factors += filter(lambda x: (m // x) & 1 == 1, primes[s:d])
      for prime in primes[1:s]:
          p, q = 1, m
          while True:
              q //= prime
              if q == 0: break
              if q & 1 == 1:
                  p *= prime
          if p > 1: factors.append(p)

      return product(factors, 0, len(factors) - 1)

  def odd_factorial(n, primes):
      if n < 2: return 1
      return (odd_factorial(n // 2, primes)**2) * swing(n, primes)

  def eval(n):
      if n < 0:
          raise ValueError('factorial not defined for negative numbers')

      if n == 0: return 1
      if n < 20: return product(range(2, n + 1), 0, n-2)

      N, bits = n, n
      while N != 0:
          bits -= N & 1
          N >>= 1

      primes = Primes(n)
      return odd_factorial(n, primes) * 2**bits

  return eval(n)

start = time.time()
answer = factorialPS(1280000)
print(time.time()-start)

```

# Answer
> 1 votes
# Java - 10.9

### n = 885000

Mergesort-y.

```
import java.math.BigInteger;

public class Factorials {

    public static BigInteger fac;

    public static BigInteger two = BigInteger.valueOf(2);

    static BigInteger mul(BigInteger start, BigInteger end) {
        if(start.equals(end)) {
            return start;
        } else {
            BigInteger mid = start.add(end.subtract(start).divide(Factorials.two));
            return Factorials.mul(start, mid).multiply(Factorials.mul(mid.add(BigInteger.ONE), end));
        }
    }

    public static void main(String[] args) {
        Factorials.fac = BigInteger.valueOf(Integer.parseInt(args[0]));
        long t = System.nanoTime();
        BigInteger result = mul(BigInteger.ONE, fac);
        t = System.nanoTime() - t;
        System.out.print(String.valueOf(((float) t) / 1000000000)); //result.toString()+" @ "+
    }
}

```

`BigInteger`s are slow.

### Recommendations for arbitrary-precision high-speed Java integer libraries? :P

# Answer
> 0 votes
# Python 3, n = 100000

A simple algorithm change was all that was needed to bump the sample code up by 10000.

```
import time

def factorial(n):
    result = 1
    while n > 0:
        result *= n
        n = n - 1
    return result

start = time.clock()
answer = factorial(100000)
end = time.clock()

print(answer)
print("Time:", end - start, "sec")

```

Obviously not the most creative answer, but there's really only one way to do a factorial....

# Answer
> 0 votes
# Python 3: 280000 / 168000

Time running your program: between `9.87585953253` and `10.3046453994`. Time running my program: about `10.35296977897559`.

```
import time

def factorial(n):
    f = 1
    while n > 1:
        hn = n >> 1
        f = f * 2**hn * double_factorial(n) #dfl[hn + (n & 1) - 1]
        n = hn
    return f
def double_factorial(n):
    #dfl = [1]
    p = 1
    l = 3
    mh = n
    while l <= n:
        p *= l
        l += 2
        #dfl.append(p)
    return p

start = time.clock()
factorial(280000)
end = time.clock()

print(end - start)

```

I read this answer on cs.SE and decided to try to implement it in Python. However, I accidentally discovered that `n! = (⌊n / 2⌋)! * 2**(⌊n / 2⌋) * n!!` (note: `!!` is the double factorial). So I converted that to a non-recursive form.

The comments show my attempt to avoid recomputing the double factorial, but I discovered that storing every value was too memory-costly that it caused my computer to run even slower. I can improve this by only storing what is needed.

Strangely, I implemented the naive straight multiplication in Python 3, and it does better than your program: `n = 169000` in 10 seconds.:

```
def factorial(n):
    p=1
    for i in range(n):
        p*=i+1
    return p

```

# Answer
> 0 votes
# Ruby 2.1

# score = 1.80 = 176\_000 / 98\_000

EDIT: improved from ~~1.35 = 132\_000 / 98\_000~~

I took ideas from the GMP factorial algorithm. This program uses the standard library to generate prime numbers. Ruby is a bad choice because multiplication seems slower in Ruby than in Python.

1. My program in Ruby 2.1: score = **1.80** = 176\_000 / 98\_000
2. Trivial algorithm in Python 2.7: score = **1** = 98\_000 / 98\_000
3. Trivial algorithm in Ruby 2.1: score = **0.878** = 86\_000 / 98\_000

Yes, my binary of `ruby 2.1.0p0 (2013-12-25 revision 44422) [x86_64-openbsd]` links against GMP. Ruby 2.1 added a feature to use GMP for large multiplication, but it still seems slower than Python 2.7.

```
require 'benchmark'
require 'optparse'
require 'prime'

def factorial(n)
  # calculate primes up to n, drop the 2
  @odd_primes = Prime.each(n).drop(1)

  # count prime factors of factorial(n)
  @factors = Hash.new(0)
  factorial_recurse(n)

  shift = @factors.delete(2) || 0
  @factors.inject(1) {|product, (base, exp)|
    product * base**exp
  } << shift
end

def factorial_recurse(n)
  return if n < 2

  # collect prime factors of 2 * 4 * 6 * .. * n
  #  = (2 * 2 * 2 * .. * 2) * (1 * 2 * 3 * .. * exp)
  #  = 2**exp * factorial(exp) where exp = floor(n/2)
  exp = n >> 1
  factorial_recurse(exp)
  @factors[2] += exp

  # collect prime factors 3 * 5 * 7 * ... * n
  for prime in @odd_primes
    break if prime > n
    exp = 0
    # count occurences of prime, prime**2, prime**3, .. n
    prime_power = prime
    until prime_power > n
      # floor(n / prime_power) occurences in 1 * 2 * .. * n,
      # but only ceil(count / 2) occurences in 3 * 5 * .. * n
      @factors[prime] += (n / prime_power + 1) >> 1
      prime_power *= prime
    end
  end
end

# usage: factorial.rb [-ct] [number]
cflag = tflag = false
OptionParser.new {|opts|
  opts.on('-c', 'Check for bugs') { cflag = true }
  opts.on('-t', 'Use trivial algorithm') { tflag = true }
  opts.parse!
}
$*[1] and fail 'too many arguments'
n = Integer($*[0] || 176_000)

if cflag
  factorial(n) == (1..n).reduce(1, :*) or
    fail "bad program: factorial(#{n}) is wrong"
  puts "ok"
  exit
end

# measure processor time to calculate factorial
f = nil
if tflag
  time = Benchmark.measure { f = (1..n).reduce(1, :*) }
else
  time = Benchmark.measure { f = factorial(n) }
end
puts f
puts "Time #{time.total} sec"

```

# Answer
> 0 votes
# Julia - Score = 15.194

Utilising the exact same approach as that of the reference program... that is,

```
f(n)=reduce(*,1:big(n))

```

So it uses reduce, the basic binary multiplication operation, and a range (in this case, using big(n) to force the calculation to be done in BigInt rather than Int64). From this, I get

```
julia> @time K=f(2340000);
elapsed time: 9.991324093 seconds (814552840 bytes allocated)

```

On my computer, with reference program running with input of 154000, I get `Time: 10.041181 sec` output (run using `python ./test.py`, where test.py is the name of the file containing the reference code)

# Answer
> 0 votes
# tcl, 13757

My answer is to check the limits of tcl.

The first line is only to set an input parameter:

```
set n 13757

```

The others are the algorithm itself:

```
set r 2
for {set i 3} {$i <= $n} {incr i} {set r [expr {$r*$i}]}
puts $r

```

I tested my code on http://rextester.com/live/WEL36956; If I make n bigger, I get a SIGKILL; may n can get bigger on a local tcl interpreter, which I do not have.

---
Tags: fastest-code, factorial
---


title: Optimally reach a number in deadfish!

text:
# Question
Title: Optimally reach a number in deadfish!
# Goal:

Given any natural number `k` such that `k<256`, produce an deadfish program that gives the smallest solution possible.

# Background:

Deadfish is a joke esoteric programming language. It has a single unsigned byte of memory, called the `accumulator`, initialized at 0. There are four commands which form a string.

* `i` = `accumulator += 1`
* `d` = `accumulator -= 1`
* `s` = `accumulator = accumulator * accumulator`
* `o` = `print(accumulator)`

For example, the string `iiisis` would produce 100, as this would be the memory after each command:

* i -\> 1
* i -\> 2
* i -\> 3
* s -\> 9
* i -\> 10
* s -\> 100

# Specification:

* Read a number through any reasonable means (from a file, STDIO, or a function argument), and output an optimal string of commands producing that number.
* A solution is considered optimal if there are no solutions that use fewer commands.
* Output through any reasonable means (to a file, STDIO, or a return value).
* The accumulator may not exceed 256.

# Examples:

```
0 -> (Empty string, nothing, or error)
1 -> i
4 -> iis
8 -> iiisd
35 -> iisiisd
150 -> iiisiiisiiiiii
256 -> (Empty string, nothing, or error)

```

# Answer
> 1 votes
# Mathematica, 164 bytes

```
a=#~Mod~256&;Switch[#2,#+1,"i",a[#-1],"d",_,"s"]&@@@Partition[FindShortestPath[Graph[Join@@(Thread[#->a@{#+1/.256->#,#-1,If[#<16,#^2,#]}]&)/@0~Range~255],0,#],2,1]&

```

Anonymous function. Takes a number as input and returns a list of instructions as output. Previous solution before requirements were changed:

### Mathematica, 148 bytes

```
a=#~Mod~256&;Switch[#2,a[#+1],"i",a[#-1],"d",_,"s"]&@@@Partition[FindShortestPath[Graph[Join@@(Thread[#->a@{#+1,#-1,#^2}]&)/@0~Range~255],0,#],2,1]&

```

Anonymous function. Takes a number as input and returns a list of instructions as output. First, the edges for a graph of value transitions are generated. Then, `FindShortestPath` is used to find the shortest path from 0 to the requested value. Finally, pairs of values are taken and compared to find the instructions used. All outputs of this program can be found here.

---
Tags: code-golf, sequence, deadfish
---


title: Close your tags!

text:
# Question
Title: Close your tags!
This is based off a previous deleted challenge of mine with the same name

### Introduction

You are tasked with writing a program that returns a truthy or falsey value based on if the input has all its XML-like1 tags appropriately opened and closed and in the right order. Consider the following as input:

```
<Apple>

```

This would return a falsey value because the tag is not closed correctly. This:

```
<Apple></Apple>

```

On the contrary returns a truthy value because it is closed correctly. The program should also check nested tags to make sure they are in the correct position. For example, take this as input:

```
<mango><Apple></mango></Apple>

```

All the tags are closed correctly, *but not in the correct order*. Your program must check for correct tag hierarchy and nesting.

### Definitions

Let me define a few things before I get into the rules and assumptions.

**Tag**

A basic XML-style tag. For example: `<Apple>`. They can have at most, one leading and trailing space (or else it's invalid and falsey), so `< Apple >` and `<Apple>` are the same. These tags can also contain attributes like `foo="bar"` *(with required double quotes, or else invalid and falsey)*, and the attribute name can only contain any alphanumeric character or `_`, `:`, `-`, and `.`. The attribute names also do not require an attribute value, and values can contain anything except `"` before the closing double quote. The closing tag must not contain attributes, and no tags should have newlines in them.

**Tag Name**

Tag names are the tags' names. For example, `<Apple>`'s tag name is `Apple`. Tag names can contain the same characters as attribute names, and are case-sensitive. This means `<Apple>` is **not** `<apple>`.

**Self-Closing Tag**

A regular tag that closes itself such as `<Apple />` or `<Apple/>` (they are the same). The space between the slash and the tag name is allowed.

**Plain Text**

A string of characters that can contain anything and are not enclosed in `<` and `>`.

**"Simple" Tag**

Either an opening, closing, or self-closing tag.

### Rules

* Output may be returned or printed, and input may be taken any way you like
* Input is a string, consisting of either tags, plain text, or both
* Your program can be a function or a whole working program
* Plain text can be anywhere; if the input consists *only* of plain text, the program should return a truthy value.
* Recognition of nested tags is required for the program. If a tag is nested in a tag, that nested tag must be closed before the parent is closed, just like regular XML, or else a falsey value should be returned

### Assumptions

* You can assume that input will always be one or more "simple" tag(s)
* You can assume that input will always follow the format for tags defined above

### Test Cases

**Falsey**

```
<apple>

<apple></Apple>

<apple></mango>

<apple><mango>

<a><b></a></b>

Text<ul><li></li><ul />

<pear attr=foo></pear attr=foo>

<Ketchup flavor=spicy></Ketchup>

<Ap ple></Apple>

```

**Truthy**

```
Text

<Apple />

<Apple></Apple>

< Apple ></ Apple>

<mango><Apple/></mango>

<mango>Text<div class="bar">More text \o/</div></mango>

<food group="fruit">Fruits:<orange :fruit-variety="clementine" /><pear _fruit.type="asian" /></food>

<example foo="abcdefghijklmnopqrstuvwxyz1234567890-/:;()$&@.,?!'" noValue>Any characters allowed! (0.0)</example>

```

### Scoring

This is , so the shortest code in bytes wins. Standard loopholes are prohibited as usual.

---

1**Note**: This is not real XML, but a pseudo-XML with different rules for the challenge. Tag and attribute names differ from specification.

# Answer
> 2 votes
# Retina, ~~76~~ 74 Bytes

```
+`< ?([-.:\w]+)( ?[-.:\w]+(="[^"]*")?)* ?(/>|>[^<>]*< ?/ ?\1 ?>)

^[^<>]*$

```

Since I've seen that retina is really good for golfing regexes, I figured I'd try it out. Follows the same logic as my Ruby answer and prints 0 or 1.

Try it online!

# Answer
> 1 votes
# Ruby (2.3.1), ~~103~~ ~~101~~ 100 Bytes

```
->s{s.sub!(/< ?([-.:\w]+)( ?[-.:\w]+(="[^"]*")?)* ?(\/>|>[^<>]*< ?\/ ?\1 ?>)/,'')&&redo;!(s=~/<|>/)}

```

Anonymous function called by appending `.call("<Apple></Apple>")`. Substitutes matching or self closing tags until there arent any, and then returns whether the string has no angle brackets remaining.

Try it online!

---
Tags: code-golf, string, decision-problem, balanced-string, syntax
---


title: Can Pac-Man Eat This String?

text:
# Question
Title: Can Pac-Man Eat This String?
In the arcade version of the game, Pac-Man eats pac-dots. However, in this challenge, he's hungry for alphanumeric characters and punctuation in a string.

Your task is to create a function that feeds Pac-Man a string, evaluates if he can eat it or not, and returns the string with Pac-Man's location in it.

Pac-Man (`<`) eats characters from left to right, leaving an underscore or space for each character as he goes, and his goal is to get from the first position-1 to the last position+1:

```
1. <Pac
2. _<ac
3. __<c
4. ___<

```

However, Pac-Man's natural enemy, the ghost, will stop him if he encounters one of the letters in the word "GHOST" (not case sensitive). Your function should return the string with Pac-Man's location as he encounters the `ghost` character:

```
1. <No!
2. _<o!

```

The only thing that can defeat a ghost is a power pellet. If Pac-Man reaches a letter in the word "PELLET" (also not case sensitive) *before* coming to a ghost, he will eat the ghost and keep moving, and that pellet will be used up. Power pellets can stack (ie, in `ppgg` both ghosts would be eaten). The **T** character exists as both as a ghost and a pellet, so it can be ignored (treated as any other letter, like `a`).

```
1. <Pop
2. _<op
3. __<p
4. ___<

```

To further clarify, in the string "Pac-Man loses here", the following operations occur:

```
P <P, +1 Pellet (1 pellet)
a <a
c <c
- <-
M <M
a <a
n <n
  <[space]
l <l, +1 Pellet (2 pellets)
o <o, -1 Pellet (1 pellet)
s <s, -1 Pellet (0 pellets)
e <e, +1 Pellet (1 pellet)
s <s, -1 Pellet (0 pellets)
  <[space]
h <h, ghost wins, returns
e
r
e

```

### Examples

```
Input: Pacman wins!
Output: ____________<

Input: Pacman loses wah-wah :(
Output: _______________<h-wah :(

Input: PELLET PELLET GHOST
Output: ___________________<

Input: Hello World!
Output: <Hello World!

Input: <_!@12<_<_<
Output: ___________<

```

This is code-golf--lowest score in bytes wins.

# Answer
# Jelly, ~~34~~ 33 bytes

```
Œl“ʋʋ“ṁḍ»ċ€Ð€IF+\‘0ṭi0ð’”_×;”<;ṫ@

```

Try it online!

I think I'm finally starting to understand Jelly. Feels a bit scary.
> 16 votes

# Answer
## Retina, ~~55~~ 38 bytes

```
i`^(([elp])|[^ghos]|(?<-2>.))*
$.&$*_<

```

Try it online! (The first line just allows running several test cases at once.)

### Explanation

The problem is essentially to find the longest prefix that doesn't have an unmatched closing parenthesis. Except that we can use either `e`, `l` or `p` in place of `(` and either `g`, `h`, `o` or `s` in place of `)`.

Hence, this solution is almost a textbook example of balancing groups. I won't go into too much detail about how they work, as this code is essentially the same as the standard example you can read up on in my SO answer on balancing groups.

The entire program is therefore a single regex substitution. The `i` activates case-insensitivity. Then we either match a pellet with `[elp]` and increment the depth counter (in the form of the capture stack of group `2`), or we match something that isn't a ghost with `[ghos]` or we match a ghost with `.` and decrement the depth counter by popping from stack `2`. Of course, in principle this allows matching a pellet with the `[^ghos]` section or a non-ghost with the `.` section, but thanks to greedy matching and the way the regex is backtracked, these possibilities are never attempted by the regex engine.

The substitution then uses two Retina specific features: `$*` repeats the character to its right as many times as specified by the token on its left. That token is `$.&` which is the length of the entire match. This just means that we replace each character in the match with a `_`. And then we also append a `<` to those underscores. The part of the input that isn't eaten simply remains unaffected by the substitution.
> 30 votes

# Answer
# Python 2, 114 113 108 bytes

```
s=raw_input()
p=i=0
for c in s:
 p+=(c in'plePLE')-(c in'ghosGHOS')
 if p<0:break
 i+=1
print'_'*i+'<'+s[i:]

```
> 10 votes

# Answer
# Python 2, 89 bytes

Sometimes my stubborn determination to make Python a functional language has its benefits.

```
def f(s,l=1):l+=(s[:1]in'plePLE')-(s[:1]in'ghosGHOS');return s*l and'_'+f(s[1:],l)or'<'+s

```

### (Slightly) ungolfed:

```
def f(s, l=1):
    l += (s[:1] in 'plePLE') - (s[:1] in 'ghosGHOS')
    return (s * l) and ('_' + f(s[1:], l)) or ('<' + s)

```

Builds up the result string using recursion. The update to `l` (for "lives") adds 1 for pellets (`True - False == 1`), subtracts 1 for ghosts (`False - True == -1`), and adds 0 for any other character. It also adds 0 when `s` is the empty string, thanks to Python's slicing and the fact that `'' in any_str == True`, so the pellet and ghost cancel.

The return statement uses `test and b or a` in place of `a if test else b` to save one byte. The recursion base case occurs when either the string ends or Pac-Man runs out of pellets, succinctly represented as `s*p`, which equals `''` (and therefore evaluates to false) when either `s == ''` or `p == 0`.
> 8 votes

# Answer
# Pyth, ~~53~~ ~~48~~ 44 bytes

4 bytes thanks to @Pietu1998 for the `!!@` -\> `}` trick (which only people who know Pyth can understand)

```
~~++*Jf<@+sM._m-!!@d"PELpel"!!@d"GHOSghos"Q_1T00\_\<>QJ~~
~~++*Jf<@+sM._m-!!@d"PEL"!!@d"GHOS"rQ1_1T00\_\<>QJ~~
++*Jf<@+sM._m-}d"PEL"}d"GHOS"rz1_1T00\_\<>zJ

```

Test suite.
> 7 votes

# Answer
# MATL, ~~37~~ ~~36~~ 35 bytes

```
tkt'ghos'mw'pel'm-Ys1=Y>&)g95*60bhh

```

**Try it online!**

### Explanation

```
tkt      % Input string implicitly. Duplicate, convert to lower case, duplicate
'ghos'm  % True for "ghost" characters
w'pel'm  % Swap to bring lowercase copy to top. True for "pellet" characters
-Ys      % Subtract, cumulative sum. Pac-Man can reach until the first "1"
1=       % True for entries that equal 1
Y>       % Cumulative maximum. This gives false until the first true is found, and
         % true from there on
&)       % Split original string in two parts, given by the zeros and ones respectively
g95*     % Convert the first part into ones and multiply by 95. This gives a numerical
         % array containing number 95 (ASCII for '_')
60       % Push 60 (ASCII for '<')
b        % Bubble up second part of original string
hh       % Concatenate the three strings/arrays, automatically converting to char

```
> 7 votes

# Answer
# C#, ~~269~~ ~~256~~ ~~232~~ ~~212~~ 211 Bytes

First ever post on here, so this is probably a lot longer than it could be (and probably because it is in C#). Any tips on where I could shorten it would be great!

Thank you to everyone in the comments who helped me!

### Golfed version

```
static void p(string x){int p=0,i=0;string t='<'+x;var s=t.ToCharArray();for(;++i<s.Length;){if("PELpel".Contains(s[i]))p++;if("GHOSghos".Contains(s[i])&&--p<0)break;s[i]='<';if(i>0)s[i-1]='_';}Console.Write(s);}

```

### Ungolfed version

```
static void p(string x) {
 int p = 0, i = 0;
 string t = '<' + x;
 var s = t.ToCharArray();
 for (; ++i < s.Length;) {
  if ("PELpel".Contains(s[i])) p++;
  if ("GHOSghos".Contains(s[i]) && --p < 0) break;
  s[i] = '<';
  if (i > 0) s[i - 1] = '_';
 }
 Console.Write(s);
}

```
> 7 votes

# Answer
## JavaScript (ES6), 98 bytes

```
s=>s.replace(/./g,c=>p<0?c:(p+=/[elp]/i.test(c)-/[ghos]/i.test(c))<0?"<"+c:"_",p=0)+"<".slice(p<0)

```

Explanation: `p` maintains the current number of pellets. If it's already negative, we just return the character and move on, so that the rest of the string is untouched. Otherwise, we examine the current character, and if that makes `p` become negative, we insert the `<` character, otherwise we replace the current character with `_`. Finally, if `p` never becomes negative, we suffix a `<` to the string.
> 7 votes

# Answer
## Lua, ~~198~~ ~~190~~ ~~184~~ ~~185~~ 163 Bytes

Ok, I admit, this is long. Very long. Lua has some tools to play around with strings, but it is limited, same goes for conditionals that takes lots of spaces.

**Edit: thanks @LeakyNun for saving me 9 bytes :) Lost some bytes to fix a bug**

**Edit 2: 163 Bytes solution found by @LeakyNun**

```
i=0p=0n=...for c in n:gmatch"."do
p=p+(c:find"[ghosGHOS]"and-1or c:find"[pelPEL]"and 1or 0)if p<0then
break else i=i+1 end end print(('_'):rep(i)..'<'..n:sub(i+1))

```

**Old 185**

```
p=0z=(...):gsub(".",function(c)p=p+(c:find"[ghosGHOS]"and-1or
c:find"[pelPEL]"and 1or 0)s=p<0 and 1or s
return s and c or'_'end)_,i,s=z:find"(_+)"print((s or'')..'<'..z:sub(1+(i or 0)))

```

## Ungolfed

```
i=0                        -- number of characters eaten
p=0                        -- pellet counter
n=...                      -- shorthand for the argument
for c in n:gmatch"."       -- iterate over each characters in the input
do
  p=p+(c:find"[ghosGHOS]"  -- if the current char is a GHOST
        and-1              -- decrement the pellet counter
      or c:find"[pelPEL]"  -- if it's a PELLET
        and 1              -- increment it
      or 0)                -- else, leave it alone
  if p<0                   -- if we try to eat a ghost without pellet
  then
    break                  -- stop iterating
  else
    i=i+1                  -- else, increment our score
  end
end

print(('_'):rep(i)         -- print i*'_'
  ..'<'                    -- appended with Pacman
  ..n:sub(i+1))            -- appended with the remaining characters if we died

```
> 4 votes

# Answer
# Pyth, ~~47~~ ~~46~~ 44 bytes

```
++*\_Kh+f!h=+Z-}Jr@zT0"pel"}J"ghos"Uzlz\<>zK

```

Try it online. Test suite.

Quite a different approach from Leaky Nun's, and I'm quite sure this can be golfed further.
> 4 votes

# Answer
## Python 3, ~~176~~ ~~157~~ ~~150~~ ~~149~~ ~~134~~ ~~133~~ 124 bytes

Define a function named `f` which take the string as argument

```
def f(s):
 n=i=0
 for c in s:
  if c in"GgHhOoSs":
   if n:n-=1
   else:break
  n+=c in"PpEeLl";i+=1
 return"_"*i+"<"+s[i:]

```

Can be probably be golfed more

Thanks to everyone who commented :D
> 3 votes

# Answer
# Python 3, ~~114~~ 110 bytes

My first code golf.

Thanks to Dr Green Eggs and Iron Man for saving 4 bytes.

```
l,x=1,0
f,y,s="ghosGHOS","pelPEL",input()
while s[x:]*l:l+=(s[x]in y)-(s[x]in f);x+=l>0
print("_"*x+"<"+s[x:])

```

Utilises the evaluation of booleans to one and zero to condense a logical AND to a multiplication. (0\*0=0, 1\*0=0, 1\*1=1). I hope this is a good first try.
> 2 votes

# Answer
# Haskell, ~~119~~ 113 Bytes

Thanks to Daniel Wagner for 6 bytes less.

```
p=(0!)
n!(c:s)|elem c"ghosGHOS"=if n<1then '<':c:s else(n-1)&s|elem c"elpELP"=(n+1)&s|0<1=n&s
_!_="<"
n&s='_':n!s

```

Call it as `p "Hello World!"`.

The `1then` is an edge case that is interpreted correctly in my GHC (7.10), but it throws of most syntax highlighters. So it might be interpreted differently in your compiler as well.

Ungolfed:

```
pacman string = go 0 string

-- | In the golfed version: (!)
go _   []                   = "<"                            -- won
go pellets (char:string)
 | char `elem` "ghosGHOS"
 = if pellets < 1        then '<':char:string                -- lost
                         else nextStep (pellets - 1) string  -- ghost
 | char `elem` "elpELP"
 =                            nextStep (pellets + 1) string  -- pellet
 | otherwise
 =                            nextStep  pellets      string  -- anything else

-- | In the golfed version: (&)
nextStep pellets string = '_':(go pellets string)

```
> 1 votes

# Answer
# C, 237 bytes

```
#include<stdio.h>
#include<string.h>
main(p,i,j){char s[99];fgets(s,99,stdin);for(p=i=0;s[i];++i){if(strchr("GHOSghos",s[i])){if(p)p--;else break;}else if(strchr("PELpel",s[i]))p++;}j=i-(s[i]==0);while(j--)printf("_");printf("<%s",s+i);}

```
> 1 votes

# Answer
# Python3, ~~211~~ 184 bytes

The argument 's' is a string

```
def f(s):
    p=c=0
    for i in s:
        if i in "gGhHoOsS":
            if p<1:break
            else:p-=1
        if i in "pPeElL":p+=1
        c+=1
    return"_"*c + "<" + s[c:]

```

I would appreciate any golfing tips as this is my first code golf attempt

Thanks for commenting :)
> 1 votes

# Answer
# **C++, 315 373 327 Bytes**

**(Note: still golfing)**

```
#include <iostream>
#include <string>
using namespace std;
int main(){string input;getline(cin, input);
if(input.find("Pac-Man loses")!=string::npos||input.find("Pacman loses")!=string::npos)
    cout<<"<"<<input.substr(15,input.length()-1);
else{for(unsigned i=0;i<=input.length();++i)
    cout << "_";
cout<<"<";
}return 0;
}

```
> 1 votes

# Answer
# Powershell, 185

```
{$l=1;$o="";for($i=0;($i -lt $_.Length) -or (($o+="<") -and 0); $i++){if ($_[$i] -match '[pel]'){$l++}if($_[$i] -match '[ghos]'){$l--}if(!$l){$o+="<"+$_.substring($i);break}$o+="_"}$o}

```

### Ungolfed:

```
("Pacman wins!",
"Pacman loses wah-wah :(",
"PELLET PELLET GHOST",
"Hello World!"
) |
% {
    $l=1;$o="";
    for($i = 0; ($i -lt $_.Length) -or (($o+="<") -and 0); $i++) {
        if ($_[$i] -match '[pel]') { $l++ }
        if ($_[$i] -match '[ghos]') { $l--}
        if (!$l) { $o+="<"+$_.substring($i); break }
        $o += "_"
    }
    $o
}

```
> 1 votes

# Answer
# **Ruby, (119 bytes)**

```
q=i=0;a=$**" ";a.split(//).each{|c|q+=((c+?p=~/[ple]/i)^1)-((c+?g=~/[ghos]/i)^1);q<0?break : i+=1};p ?_*i+?<+a[i..-1]

```

There is probably some things i'm missing as I am new to this...

Ruby is my friend :)
> 1 votes

# Answer
# Perl, 54 (52+2) bytes

```
s/([pel](?1)*[ghos]|[^ghos
])*/'_'x(length$&).'<'/ei

```

Needs `-p` to be specified in the command-line options.

Explanation:

The `-p` option causes the statement to be wrapped in a read-modify-print loop, where during each loop iteration, `$_` contains a line of input, including the line delimiter.

The regex is largely the same idea as in the Retina answer.

Call the search pattern `([pel](?1)*[ghos]|[^ghos
])*` "acceptable". Then it can be recursively defined as:

A string is "acceptable" if:

* It is a character in `PELLET` except for `T`, followed by an acceptable string, followed by a character in `GHOST` except for `T`.
* It is a character not in `GHOST` except for `T` that is not a newline character.
* It is a concatenation of any number (including 0) of acceptable strings.

This definition allows more pellets than ghosts: a `PEL` character may be matched as either a pellet character, or a non-ghost character.

The empty string is considered acceptable, therefore the regex is guaranteed to match at position 0, where the longest acceptable substring will be matched.

This longest acceptable substring is then matched by underscores of equal length, followed by `<`.
> 0 votes

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