title: Nth K-Ugly Number

text:
# Question
Title: Nth K-Ugly Number
Write the shortest code in any language of your choice to find the \\$N\\$th \\$K\\$-ugly number.

A \\$K\\$-ugly number is a number whose only prime factors are the prime numbers \\$\le K\\$. \\$K\\$-ugly number's are popularly known as \\$K\\$-smooth numbers.

Constraints:

* \\$0 \< N \< 1000\\$
* \\$0 \< K \< 25\\$

Input:

* `N K` (separated by a single space)

Output:

* `-1` (if no such number exists)
*or*
* \\$M\\$ (if \\$N\\$th \\$K\\$-ugly number is \\$M\\$)

# Answer
> 4 votes
# Mathematica ~~82 72~~ 70

```
n_~u~k_:=(c=m=1;While[m <= n,If[FactorInteger[c][[-1,1]]<=k,m++];c++];c-1)

```

**Usage**

```
u[1, 5]
u[5, 2]
u[20, 3]
u[57, 5]
u[66, 13]
u[100, 5]
u[1000, 25]

```

> 1
> 16
> 96
> 324
> 110
> 1536
> 5474

---

Prime factors and their powers are in the center column.

```
Table[{t, FactorInteger[t], u[t, 5]}, {t, 15}] // Grid

```

# Answer
> 4 votes
## Python 2 - 63 bytes

```
i=t=1
n,k=input()
while~-n:i+=1;t*=i>k or i**n;n-=t%i<1
print i

```

Input is taken from stdin, comma separated.

Sample usage:

```
$ echo 1, 5 | python nth-k-smooth.py
1

$ echo 5, 2 | python nth-k-smooth.py
16

$ echo 20, 3 | python nth-k-smooth.py
96

$ echo 57, 5 | python nth-k-smooth.py
324

$ echo 66, 13 | python nth-k-smooth.py
110

$ echo 100, 5 | python nth-k-smooth.py
1536

$ echo 1000, 25 | python nth-k-smooth.py
5474

```

---

At *N = 1000*, the script has a reasonable execution time for all values *K ≥ 7*. For the input *N = 1000, K = 2* the correct answer is *2999 ≈ 5.357543300·10300*. Using an "increase by one" approach, as David Carraher's answer also does, it would take longer than the age of the universe to reach this value (considerably longer!).

# Answer
> 3 votes
## APL(Dyalog), 38

```
{⍵≡1:¯1⋄⊃⌽⍺{0~⍨⍺↑y[⍋y←∪,⍵∘.×⍵]}⍣≡⍳⍵}/⎕

```

Finally, for once, APL has beaten GS!!

---

**Sample**

```
⎕:
      5 3
6

⎕:
      20 5
36

⎕:
      500 20
2028

⎕:
      50 1
¯1

```

---

**Explanation**

`/⎕` Takes evaluated input (space-seperated numbers are interpreted as numerical array) and insert a function in between (reduce).

`⍵≡1:` If right argument (k) is 1
`¯1` return -1 (`¯` is the high-minus, APL's way of representing negative numbers)
Statement seperator used as `else`.

`⍳⍵` Generate a numerical array from 1 to k
`⍺{...}⍣≡` Recursively apply function until output of an iteration is the same as that of the last iteration (fixpoint), passing the left argument of outer function (N) as the left each iteration.

`⍵∘.×⍵` Outer product of the left argument with itself (generating a multiplication table)
`,` Unravel the matrix to numerical array
Remove duplicates
`y[⍋y←...]` Sort
`⍺↑` Get the first N values (fills 0s if shorter than N)
`0~⍨` Remove 0s
**In short, `⍺{0~⍨⍺↑y[⍋y←∪,⍵∘.×⍵]}⍣≡⍳⍵` generates the first N k-smooth numbers**

`⊃⌽` get last value

# Answer
> 2 votes
## R 133 characters

```
a=scan(n=2)
k=1:a[2]
i=m=0
while(m<a[1]){i=i+1;if(all(sfsmisc::factorize(i)[[1]][,1]%in%k[rowSums(!outer(k,k,`%%`))<3]))m=m+1}
cat(i)

```

Explanation:

`k[rowSums(!outer(k,k,`%%`))<3]`: k being here the sequence from 1 to K, this piece of code outputs the list of primes smaller or equal to K.
`all(sfsmisc::factorize(i)[[1]][,1]%in%k[rowSums(!outer(k,k,`%%`))<3])`: this checks that all of the primes used to factorize a number belong to the previous list. It uses a function from package `sfsmisc` that performs the prime factorization.

# Answer
> 2 votes
### GolfScript, 42 characters

```
~),2>{:s,2>{s\%!},!},:^1+1+{$({*}+^%|}@*0=

```

Unfortunately, I had to insert several correction terms to get the indexing correct.

Examples:

```
> 5 2
16

> 20 3
96

> 66 13
110

> 1000 25
5474

```

# Answer
> 1 votes
## Mathematica, 96 characters

```
{n,k}=%~Read~{Number,Number};If[n>k==1,-1,While[p<n,m++;If[Max@FactorInteger[m][[All,1]]<=k,p++]];m]

```

Ungolfed:

```
{n, k} = % ~Read~ {Number, Number};
If[n > k == 1,
  -1,
  While[p < n,
    m++;
    If[Max@FactorInteger[m][[All, 1]] <= k, p++]
  ]; m
]

```

I did manage to find a shorter solution, more in the spirit of Mathematica's functional programming style by avoiding the while-loop, but it runs out of memory without an upper bound on *M*. It also cheats on the space-seperated input, but I thought it was elegant (60 characters):

```
Select[Range@999,Max@FactorInteger[#][[All,1]]<=k&][[n]]~Check~-1

```

# Answer
> 1 votes
# Ruby 1.9+, 101 chars

Sort of verbose but nice and functional:

```
require'Prime'
n,k=gets.split.map &:to_i
p (1..5474).select{|i|i.prime_division.all?{|j,l|j<=k}}[n-1]

```
edit:

The number constant `5474` represents the highest value the program will ever output (upper bound), and is the answer to *N = 1000, K = 2*. As Primo points out, this may be a little low.

If you for some reason would like to run this program, the upper bound can be changed to whatever you want. Increasing it by a few digits will however increase execution time dramatically, even for small outputs.

A feature I find quite neat is that the program cleanly outputs `nil` if the output would exceed the upper bound.

---
Tags: code-golf, math, primes, number-theory
---


# Question
Title: Bitonic Program to find the maximum of two numbers
A bitonic program is a program every string of which is bitonic.

A bitonic string is a string S with S\[0\]\<= . . . \<=S\[k\]\>= . . . \>=S\[n-1\] for some k, 0\<=k\< n. (n is the length of the string)

**Examples of Bitonic strings:**

* abcd
* dcba
* vyzcba
* adgf

The goal is to write the shortest bitonic program to find the maximum of two numbers.

**Note:**

* Two group of characters separated by one or more spaces(' '), tabs('\t'), backspaces or line-break('\n') are considered as two different strings.
* Comments in the code are not allowed.
* Other than tabs, spaces, backspaces or line-breaks, the code must contain at least 3 other characters.

**EDIT:**

* Inbuilt function not allowed.
* Conditional statements not allowed.
* \<(less than) and \>(greater than) signs not allowed

# Answer
## APL, 3

```
⎕⌈⎕

```

Can this be beaten?
> 2 votes

---
Tags: code-golf
---


title: Just Another Perl Hacker

text:
# Question
Title: Just Another Perl Hacker
Classic code golf challenge. Write the most obscure Perl program to print "Just another Perl hacker". Here's the Wikipedia article on it. Bonus points if it fits in 3 lines / 70 characters each.

# Answer
```
@H=@h=(176,138,140,17,87,54,126,182,217,223,136,130,136,117,73,52,154,
134,161,36,33,92,60,51);for(;$j<24;$j++){$x=0;for($k=0;$k<24;$k++){$x
+=@h[$k]<<($j*$k%24);$x%=241;}@H[$j]=$x;}print pack('c*',@H)
```

I'm not sure whether a newline at the end is required: if so, the addition of `."\n"` still doesn't take me up to the limit of 3 lines * 70 chars/line.

If it weren't for encoding issues the initialisation could be much smaller and extracted with unpack, so I expect someone can improve on this. I'm thinking about making a more efficient version - this is O(n^2), and O(n lg n) decoding is possible.
> 10 votes

# Answer
```
eval eval '"'.

                                      ('['^"\+").(
           ('[')^                   ')').('`'|')').
        ('`'|'.').                ('['^'/').('{'^'['
 ).'\\'.'"'  .('`'^              '*').('['^'.').('['^
'(').('['^'/').('{'^            '[').('`'|'!').(('`')|
'.').('`'|'/').("\["^          '/').('`'|'(').('`'|'%'
  ).('['^')').(('{')^        '[').('{'^'+').('`'|'%').(
       '['^')').('`'|      ',').('{'^'[').('`'|'(').('`'
      |'!').('`'|'#'     ).('`'|'+').('`'|'%').('['^')').
     '\\'.'"'.("\!"^   '+').'"';$:='.'^'~';$~='@'|"\(";$^=
    ')'^'[';$/='`'|   '.';$,='('^'}';$\='`'|'!';$:=')'^"\}";
    $~='*'|"\`";$^=  '+'^'_';$/='&'|'@';$,='['&'~';$\=','^'|'
    ;$:='.'^'~';$~  ='@'|'(';$^=')'^'[';$/='`'|'.';$,='('^'}'
    ;$\='`'|'!';$:  =')'^'}';$~='*'|'`';$^='+'^'_';$/='&'|'@';
    $,='['&'~';$\=','^'|';$:='.'^'~';$~='@'|'(';$^=')'^'[';$/=
    '`'|'.';$,='('^'}';$\='`'|'!';$:=')'^'}';$~='*'|'`';$^='+'^
     '_';$/='&'|'@';$,='['&'~';$\=','^'|';$:='.'^'~';$~='@'|'('
     ;$^=')'^'[';$/='`'|'.';$,='('^'}';$\='`'|'!';$:=')'^'}';$~=
      '*'|'`';$^='+'^'_';$/='&'|'@';$,='['&'~';$\=','^'|';$:='.'^
       '~';$~='@'|'(';$^=')'^'[';$/='`'|'.';$,='('^'}';$\='`'|'!'
        ;$:=')'^'}';$~='*'|'`';$^='+'^'_';$/='&'|'@';$,="\["& '~'
         ;$\=','^'|';$:='.'^'~';$~='@'|'(';$^=')'^'[';$/='`'  |((
          '.'));$,='('^'}';$\='`'|'!';$:=')'^'}';$~ ='*'|'`'  ;$^
            ='+'^'_';$/='&'|'@';$,='['&'~';$\=','^  '|';$:=   '.'
             ^'~'; $~='@'|'(';$^=')'^'[';$/="\`"|   '.';$,=   '('
                   ^'}';$\='`'|'!';$:=')'^'}';$~    =('*')|   '`'
                   ;$^='+'^    '_';$/='&' |"\@";     $,='['   &+
                   '~';$\=     ','^'|';   $:='.'     ^"\~";  $~
                   =('@')|     "\(";$^=   "\)"^       "\[";  (
                   ($/))=      '`'|'.';   ($,)         ='('
                   ^"\}";     $\=('`')|   '!';         ($:)
                    =')'^     "\}";$~=    '*'|         '`';
                    ($^)=     '+'^'_'     ;$/=         '&'|
                    '@';     $,='['       &'~'         ;$\=
                    ','^     '|'          ;$:=         '.'^
                    '~';      $~=         '@'          |((
                    '('        ));       $^=           ')'
                    ^((         '['     ));            $/=
                    '`'          |((   '.'              ))
                    ;(             ($,))=               ((
                    ((              '('))               ))
                    ^+             "\}";$\=             ((
                   '`'            ))|+ "\!";            $:
                  =((           ')'))^  '}';           $~=
                 '*'|         "\`";$^=   '+'          ^'_'
               ;($/)=                                ('&')|
             "\@";$,=                               '['&'~'

```
> 34 votes

# Answer
```
use Time'HiRes"usleep";$|=@q=(a..z,' ');@w=('just another perl hacker'
=~/./g);while("@w"ne"@e"){$e[$_]eq$w[$_]or$e[$_]=$q[rand@q]for+0..$#w;
print"\r@e";usleep+1e5}

```

animated version :)
> 5 votes

# Answer
### Less than 70 character on 3 lines:

```
$_=unpack("H21","9Ø
HvÂláµöÂ");s/(.)/" "x(hex$1<3).substr
"AHPJocehtunarslk",hex$1,1/eg;say

```

Care: It's **ISO-8859-1** encoded.

```
perl -E '$_=unpack("H21","9Ø
HvÂláµöÂ");s/(.)/" "x(hex$1<3).substr
"AHPJocehtunarslk",hex$1,1/eg;say'

Just Another Perl Hacker

```

More than 70 chars at all, but less than **100!**

```
wc -clL <<< '$_=unpack("H21","9Ø
HvÂláµöÂ");s/(.)/" "x(hex$1<3).substr
"AHPJocehtunarslk",hex$1,1/eg;say'

  3 92  37

```

And a little *obfuscated*!

### A little away?!

There is a *\<1'000* perl script with a full help and some features:

(It's **ISO-8859-1** encoded too ;)

```
#!/usr/bin/perl -s
$;=$/;$_=q=sub'O{un=."\144e".q[f}sub'l{$#_==-1?leng].q[th:leng].'t'.q[h&a}sub'u{($.=
q;?02:;)=~y+0-@+a-q+;$. =~s/^/&a?"un].q[":""/mxe;$..=' "b';$..=do{$.].q[=~m+^u+?&a:1
}<<3;$..='","';$..=do{$.].q[=~m+^u+?"\44_":&a};eval $.."\42"}s].q[ub'a{pop}sub'b{$.=
"Hauri Félix, ";$v?do{$_=$.;y+?-^+_-~+;].q[s/\s.*/.ch/mgx;$_=do{$0=~m-j\w+-?$&.q.@.:
(q.w.x3).q,.,}.q qf-q].q[.$_;$..$_}:sub].q[str("lockpents ".$.,&a,1)}sub'p{pr]."in".
q<t do{$#_+1?&a."\n":do{/\n/?$_:$_.".\n"}}};sub'x{e>.pack("v",27000).q<t}sub't{sel>.
"ec".q<t O,&O,O,&a};$v&&{p $0." \251".(30*67)." ".b}&&x;$j&&do{$_="Îx¹\26§ÕIÕ\220º".
"2Õ";$_=>.q<u 12,1;s/.{4}/b ord u O,"$&",O/meg;tr+@-[+`-{+;s/./($.=$&)=~y.^-{.?-\\>.
q<\\.;$./xe;p;$c&&do{$c!=1&&do{$_=$c." ";p};fo>."reac".q<h$=(1..2*l){s/.//m;$_.=$&;p
"\33[A\r".$_;t.1}};x};$/=O;o>.chr(0x38*2).q-en$_,$0;$_=<$_>;$k&&p&&x||$p&&do{p;op-.q
len$p,$p;p<$p>;x};$h&&do{$_="Usal.q lge: ".$0." [ -v | -h | -j [-c[=string]] | -k |l
.q+ -p=file.pl ]";p;x};1+;eval||die+No.$;;

```

There are some features:

```
./japh.pl -h
Usage: ./japh.pl [ -v | -h | -j [-c[=string]] | -k | -p=file.pl ].

```

Where:

* `-v` signature
* `-h` help string
* `-j` prompt *Just another perl hacker.*
* `-c` animate the *japh* string or a submited string if any
* `-k` dump the script himself
* `-p` polute another script

So:

```
./japh.pl -j
Just another perl hacker.

./japh.pl -k | wc -lcL
     14     998      84

./japh.pl -p=$(which perldoc) >japhedPerldoc
chmod +x japhedPerldoc

./japhedPerldoc perl | head
PERL(1)               User Contributed Perl Documentation              PERL(1)

NAME
   perl - The Perl 5 language interpreter

SYNOPSIS
       perl [ -sTtuUWX ]      [ -hv ] [ -V[:configvar] ]
            [ -cw ] [ -d[t][:debugger] ] [ -D[number/list] ]

./japhedPerldoc -j -c
Just another perl hacker.

```

(The last string is animated:)

### Trying to *de-obfucate*

There is a nice B::Deparse module available on CPAN:

```
perl -MO=Deparse japh.pl
$; = $/;
$_ = qq[sub'O{undef}sub'l{\$#_==-1?length:length&a}sub'u{(\$.=\nq;?02:;)=~y+0-\@+a-q+;\$. =~s/^/&a?"un":""/mxe;\$..=' "b';\$..=do{\$.=~m+^u+?&a:1\n}<<3;\$..='","';\$..=do{\$.=~m+^u+?"\\44_":&a};eval\$.."\\42"}sub'a{pop}sub'b{\$.=\n"Hauri F\351lix, ";\$v?do{\$_=\$.;y+?-^+_-~+;s/\\s.*/.ch/mgx;\$_=do{\$0=~m-j\\w+-?\$&.q.\@.:\n(q.w.x3).q,.,}.q qf-q.\$_;\$..\$_}:substr("lockpents ".\$.,&a,1)}sub'p{print do{\$#_+1?&a."\\n":do{/\\n/?\$_:\$_.".\\n"}}};sub'x{e] . pack('v', 27000) . q[t}sub't{sel] . 'ec' . qq[t O,&O,O,&a};\$v&&{p \$0." \\251".(30*67)." ".b}&&x;\$j&&do{\$_="\316x\271\\26\247\325I\325\\220\272".\n"2\325";\$_=] . 'u 12,1;s/.{4}/b ord u O,"$&",O/meg;tr+@-[+`-{+;s/./($.=$&)=~y.^-{.?-\\' . '\\.;$./xe;p;$c&&do{$c!=1&&do{$_=$c." ";p};fo' . 'reac' . qq(h\$=(1..2*l){s/.//m;\$_.=\$&;p\n"\\33[A\\r".\$_;t.1}};x};\$/=O;o) . 'p' . 'en$_,$0;$_=<$_>;$k&&p&&x||$p&&do{p;op' . 'en$p,$p;p<$p>;x};$h&&do{$_="Usa' . 'ge: ".$0." [ -v | -h | -j [-c[=string]] | -k |' . ' -p=file.pl ]";p;x};1';
die 'No' . $; unless eval $_;
japh.pl syntax OK

```

Well, this is *more* readable, but...

Ok, there is a `pack('v', 27000)`, what it mean:

```
perl -E "say pack('v', 27000)";
xi

```

Hmm. so we could try to simplify deparser's work:

```
perl -MO=Deparse <(sed -e <japh.pl 's/pack("v",27000)/"xi"/')
$; = $/;
$_ = qq(sub'O{undef}sub'l{\$#_==-1?length:length&a}sub'u{(\$.=\nq;?02:;)=~y+0-\@+a-q+;\$. =~s/^/&a?"un":""/mxe;\$..=' "b';\$..=do{\$.=~m+^u+?&a:1\n}<<3;\$..='","';\$..=do{\$.=~m+^u+?"\\44_":&a};eval \$.."\\42"}sub'a{pop}sub'b{\$.=\n"Hauri F\351lix, ";\$v?do{\$_=\$.;y+?-^+_-~+;s/\\s.*/.ch/mgx;\$_=do{\$0=~m-j\\w+-?\$&.q.\@.:\n(q.w.x3).q,.,}.q qf-q.\$_;\$..\$_}:substr("lockpents ".\$.,&a,1)}sub'p{print do{\$#_+1?&a."\\n":do{/\\n/?\$_:\$_.".\\n"}}};sub'x{exit}sub't{select O,&O,O,&a};\$v&&{p \$0." \\251".(30*67)." ".b}&&x;\$j&&do{\$_="\316x\271\\26\247\325I\325\\220\272".\n"2\325";\$_=u 12,1;s/.{4}/b ord u O,"\$&",O/meg;tr+\@-[+`-{+;s/./(\$.=\$&)=~y.^-{.?-\\\\.;\$./xe;p;\$c&&do{\$c!=1&&do{\$_=\$c." ";p};foreach\$=(1..2*l){s/.//m;\$_.=\$&;p\n"\\33[A\\r".\$_;t.1}};x};\$/=O;open\$_,\$0;\$_=<\$_>;\$k&&p&&x||\$p&&do{p;open\$p,\$p;p<\$p>;x};\$h&&do{\$_="Usage: ".\$0." [ -v | -h | -j [-c[=string]] | -k | -p=file.pl ]";p;x};1);
die 'No' . $; unless eval $_;
/dev/fd/63 syntax OK

```

Well, now it is clear that whole script is contained in `qq(...)` on line 2 and have to be submited to `eval`. We could now:

```
perl -MO=Deparse <(sed -e <japh.pl 's/pack("v",27000)/"xi"/') |
    sed -ne 's/$_ = \(qq(.*)\);/print \1/p' |
    perl
/dev/fd/63 syntax OK
sub'O{undef}sub'l{$#_==-1?length:length&a}sub'u{($.=
q;?02:;)=~y+0-@+a-q+;$. =~s/^/&a?"un":""/mxe;$..=' "b';$..=do{$.=~m+^u+?&a:1
}<<3;$..='","';$..=do{$.=~m+^u+?"\44_":&a};eval $.."\42"}sub'a{pop}sub'b{$.=
"Hauri Félix, ";$v?do{$_=$.;y+?-^+_-~+;s/\s.*/.ch/mgx;$_=do{$0=~m-j\w+-?$&.q.@.:
(q.w.x3).q,.,}.q qf-q.$_;$..$_}:substr("lockpents ".$.,&a,1)}sub'p{print do{$#_+1?&a."\n":do{/\n/?$_:$_.".\n"}}};sub'x{exit}sub't{select O,&O,O,&a};$v&&{p $0." \251".(30*67)." ".b}&&x;$j&&do{$_="Îx¹\26§ÕIÕ\220º".
"2Õ";$_=u 12,1;s/.{4}/b ord u O,"$&",O/meg;tr+@-[+`-{+;s/./($.=$&)=~y.^-{.?-\\.;$./xe;p;$c&&do{$c!=1&&do{$_=$c." ";p};foreach$=(1..2*l){s/.//m;$_.=$&;p
"\33[A\r".$_;t.1}};x};$/=O;open$_,$0;$_=<$_>;$k&&p&&x||$p&&do{p;open$p,$p;p<$p>;x};$h&&do{$_="Usage: ".$0." [ -v | -h | -j [-c[=string]] | -k | -p=file.pl ]";p;x};1

```

In the hope *deparser* could better understand, now:

```
perl -MO=Deparse <(sed -e <japh.pl 's/pack("v",27000)/"xi"/') |
    sed -ne 's/$_ = \(qq(.*)\);/print \1/p' |
    perl |
    perl -MO=Deparse
/dev/fd/63 syntax OK
sub O {
    undef;
}
sub l {
    $#_ == -1 ? length $_ : length &a;
}
sub u {
    ($. = '?02:') =~ tr/0-@/a-q/;
    $. =~ s/^/&a ? 'un' : '';/emx;
    $. .= ' "b';
    $. .= do {
        $. =~ /^u/ ? &a : 1
    } << 3;
    $. .= '","';
    $. .= do {
        $. =~ /^u/ ? '$_' : &a
    };
    eval $. . '"';
}
sub a {
    pop();
}
sub b {
    $. = "Hauri F\351lix, ";
    $v ? do {
        $_ = $.;
        tr/?-^/_-~/;
        s/\s.*/.ch/gmx;
        $_ = do {
            $0 =~ /j\w+/ ? $& . '@' : 'w' x 3 . '.'
        } . 'f-' . $_;
        $. . $_
    } : substr('lockpents ' . $., &a, 1);
}
sub p {
    print do {
        $#_ + 1 ? &a . "\n" : do {
            /\n/ ? $_ : $_ . ".\n"
        }
    };
}
sub x {
    exit;
}
sub t {
    select O(), &O, O(), &a;
}
x  if $v and {p($0 . " \251" . 2010 . ' ' . b())};
if ($j) {
    $_ = "\316x\271\cV\247\325I\325\220\2722\325";
    $_ = u(12, 1);
    s/.{4}/b ord u(O(), "$&", O());/egm;
    tr/@-[/`-{/;
    s[.][($. = $&) =~ tr/^-{/?-\\/;
    $.;]ex;
    p ;
    if ($c) {
        if ($c != 1) {
            $_ = $c . ' ';
            p ;
        }
        foreach $= (1 .. 2 * l()) {
            s/.//m;
            $_ .= $&;
            p "\e[A\r" . $_;
            t 0.1;
        }
    }
    x ;
}
$/ = O();
open $_, $0;
$_ = <$_>;
$p and do {
    p ;
    open $p, $p;
    p <$p>;
    x
} unless $k and p  and x ;
if ($h) {
    $_ = 'Usage: ' . $0 . ' [ -v | -h | -j [-c[=string]] | -k | -p=file.pl ]';
    p ;
    x ;
}
'???';
- syntax OK

```

Well! We got something near readable, now. Do this alway give same result?

```
perl -MO=Deparse <(sed -e <japh.pl 's/pack("v",27000)/"xi"/') |
    sed -ne 's/$_ = \(qq(.*)\);/print \1/p' |
    perl |
    perl -MO=Deparse |
    perl -s /dev/stdin -j -c="That's all folks"
/dev/fd/63 syntax OK
- syntax OK
Just another perl hacker.
That's all folks .

```

(And the last line is animated:)
> 4 votes

# Answer
```
use strict;*1=*CORE'die,*!=*=,@=='hacker',s??'&1(@!,$/)'?ee;s;;%ENV=~m
,..$,,$&+10;e,@!=(chr.'ust',~~reverse('rehtona'),'Perl',$@);&1("@{=}")

```

It works with strictures enabled. Although it does not work on all machines/perls, because of `CORE'die` and `~~%ENV`.

```
$ perl
use strict;*1=*CORE'die,*!=*=,@=='hacker',s??'&1(@!,$/)'?ee;s;;%ENV=~m
,..$,,$&+10;e,@!=(chr.'ust',~~reverse('rehtona'),'Perl',$@);&1("@{=}")
^Z
Just another Perl hacker

```
> 1 votes

---
Tags: popularity-contest, obfuscation, perl
---


title: Code-Golf: Lights Off!

text:
# Question
Title: Code-Golf: Lights Off!
*The shortest code to pass all possibilities wins*

Many grid based games have been made that start off with a grid of lights that are switched on. Pressing any of the lights causes that light and the four lights adjacent to it to be toggled. When a light is toggled, it is turned off or turned on, depending on if it was intially turned on or off. The goal is to hit the lights in a sequence that results in all of the lights being turned off at the end.

"X" represents lights that are turned on. "O" represents lights that are turned off. "P" represents that square that is pressed.

```
XOO          XOO      XOX      XOX      XXX
XOX          XOP  ->  XXO  ->  OPO  ->  XOX
OOX          OOX      POO      XXO      XOO

Intial Grid  Press 1  Press 2  Press 3  Ending Grid

```

Input can be taken directly from a file passed as an argument, or as standard input. The first line of input will contain *x* (1 \<= *x* \<= 20), the size of the grid of lights, meaning *x* by *x*. The second line will contain *y* (0 \<= *y* \<= (*x* * 3)2), the number of lights initially lit up. The next *y* lines contain coordinates of lit up lights on the grid, in the format of "row column". Lights that are already switched on (have been toggled previously) should be toggled off again. The next line will contain *z*, the number of lights pressed. The final *z* lines contain coordinates of the pressed lights, in the order that they were pressed, in the format of "row column".

No input will be incorrect. All numbers will be within the given boundaries of the grid.

The output will be the final grid after all lights have been toggled. It should be an *n* by *n* grid. For each area that has a light which is on, the uppercase character "X" should be used. For each area that has a light which is off, the uppercase character "O" should be used.

Lights that are affected that are off the grid should be ignored. Toggling a light on the edge of a grid should only affect the lights that are on the grid itself.

## Test Cases

---

**Input**

```
4
5
2 3
2 4
3 1
3 4
4 3
7
3 3
4 4
3 4
4 2
4 1
2 2
3 2

```

**Output**

```
OXOO
XOXO
XOXO
OXOO

```

---

**Input**

```
1
3
1 1
1 1
1 1
2
1 1
1 1

```

**Output**

```
X

```

# Answer
# J, 132

```
'x f'=:0 2{,i=:".;._2(1!:1)3
echo u:79+9*}:"1}."1}.}:2|+/(1:`[`]}&(0$~,~x+2))"0<"1(f{.2}.i),;([:<[,[:|:(2 4$0 0,,~1 _1)+])"1(3+f)}.i

```

Probably can be golfed a lot further.

* Console only, stdin-\>stdout. Tested on j602 on Linux.
* Passes both tests given.
* Assumes sane upper limit on X (no extended precision)

Original ungolfed version:

```
NB. Whole input as two column grid
i=:".;._2(1!:1)3

NB. x is x, f is number of initial toggles
'x f'=:0 2{,i

NB. z is 1..x
z =: >:i.x

NB. Take a boxed pair of indices, generate 'cross' indices (boxed)
f2=:3 :'y,,<"1(>y)+"1>0 1;1 0;0 _1;_1 0'

NB. List of initial toggles, individually boxed
init=: <"1 f {. 2 }. i

NB. List of Ps, individually boxed
toggle=: <"1 (3 + f) }. i

NB. Grid of 0s padded on all sides
g =:0$~(x+2),(x+2)

NB. For each initial toggle, make a grid with a 1 in that position. Sum each 'position'.
grid =: +/ (1:`[`]}&g)"0 init

NB. For each position in the cross (f2) of each press, make a grid with a 1 in that position.
NB. Sum each 'position', add to 'grid', take mod 2, and select inner rows/columns.
gfinal =: z {"1 z { 2|grid + +/ (1:`([:f2[)`]}&g)"0 toggle

NB. Translate 0/1 to O/X through ascii and print
echo u:79+9*gfinal

```
> 4 votes

# Answer
## Python, 209 203 199 characters

```
I=input
x=I()+1
s=0
C=lambda:eval(raw_input().replace(' ','*%d+'%x))
exec's^=1<<C();'*I()
exec's^=1+(7<<x)/2+(1<<x<<x)<<(C()-x);'*I()
R=range(1,x)
for r in R:print''.join('OX'[s>>r*x+c&1]for c in R)

```

The state of the lights is kept in a single (big) integer variable, `s`. XORs with bitmasks are used to toggle the lights. I keep an extra bit per row to prevent wraparound.
> 6 votes

# Answer
## Ruby 1.9, 167 characters

```
n=gets.to_i
y=z=[*[1]*n,0]*n
$<.map{|i|a,b=i.split.map &:to_i;b ?[*y&&[b>1&&-1,b<n&&1,a>1&&~n,a<n&&n+1],0].map{|f|f&&z[n*a+a-n-2+b+f]*=-1}:y=!y}
z.map{|a|putc"
OX"[a]}

```

Edits:

* (198 -\> 191) Removed some unnecessary stuff
* (191 -\> 180) Simplified the way the input is parsed
* (180 -\> 172) Removed parentheses, use `z[u]*=-1` instead of `z[u]=-z[u]`, remove unused variable
* (172 -\> 169) Some simplifications
* (169 -\> 167) Simplified a conditional
> 5 votes

# Answer
# Perl, 139 chars

```
@s=1..<>;<>=~/ /,$f{$`,$'+0}=1for 1..<>;<>=~/ /,map$f{$`+$_*($_&1),$'+int$_/2}^=1,-2..2for 1..<>;$\=$/;for$x(@s){print map$f{$x,$_}?X:O,@s}

```

### Explanation:

```
# Read size and generate an array of integers from 1 to the size.
# We’ll need to iterate over this array often, but otherwise we don’t need the size
@s = 1..<>;

# Read number of prelit lights
for (1..<>) {
    # Find the space; sets $` and $' to row and column, respectively
    <> =~ / /;
    # Set the relevant light; need +0 because $' includes the newline
    $f{$`, $'+0} = 1;
}

# Read number of light switchings
for (1..<>) {
    # As above
    <> =~ / /;
    # Some nice formulas that flip the 5 relevant lights,
    # including the ones “off the board”, but we don’t care about those
    map {
        $f{ $`+$_*($_&1), $'+int$_/2 } ^= 1
    }, (-2..2);
}

# Cause each subsequent print statement to print a newline after it
$\ = $/;

# For each row...
for $x (@s) {
    # Print X’s and O’s as required
    print map { $f{$x,$_} ? X : O }, @s;
}

```
> 3 votes

# Answer
## APL (71)

```
'OX'[1+⊃{⍵≠(⍳⍴⍵)∊(⊂⍺)+K,⌽¨K←(0 1)(0 0)(0 ¯1)}/({⎕}¨⍳⎕),⊂({⎕}¨⍳⎕)∊⍨⍳2/⎕]

```
> 2 votes

---
Tags: code-golf, grid, simulation
---


# Question
Title: Just one note - musical instrument synthesizing
## Statement

The task is to synthesize sound (one note played) of some musical instrument (of your choice) using function in some general purpose programming language (of your choice).

There are two goals:

* Quality of the resulting sound. It should resemble the real instrument as fine as possible;
* Minimality. Keeping the code under 1500 bytes is adviced (less if there's only basic sound generation).

Only generation function need to be provided, boilerplate is not counted for the score.

Unfortunately no score can be calculated for the sound fidelity, so there can't be strict rules.

Rules:

* No dependance on sample libraries, specialized music generation things;
* No downloading from network or trying to use microphone or audio card's MIDI or something too external like this;
* The code size measure unit is bytes. File can get created in current directory. Pre-existing files (coefficient tables, etc) may exist, but their content is added to the score + they must by opened by name.
* The boilerplate code (not counted to score) receives array (list) of signed integers and only deals with outputting them.
* Output format is signed little endian 16-bit words, 44100 samples per seconds, with optional WAV header. No trying to output compressed audio instead of plain wav;
* Please choose different instruments for synthesizing (or other quality vs code size category for the instrument); but don't initially tell what are you simulating - let other users to guess in comments;
* Electronic instruments are discouraged;
* Drum is an instrument. Human voice is an instrument.

## Boilerplates

Here are boilerplates for some languages. You can write similar boiler plate for your language as well. Commented out "g" function is just for a demo (1 second 440 Hz sine tone).

C:

```
//#!/usr/bin/tcc -run
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

/*
void g(signed short *array, int* length) {
    *length = 44100;
    int i;
    for(i=0; i<44100; ++i) array[i]=10000*sin(i*2.0*3.14159265358979323*440.0/44100.0);
}
*/

// define your g here

signed short array[44100*100];
int main(int argc, char* argv[]) {
    int size=0;
    memset(array,0,sizeof array);
    // i(array); // you may uncomment and implement some initialization
    g(array, &size);
    fwrite("RIFFH\x00\x00\x00WAVEfmt\x20\x12\x00\x00\x00\x01\x00\x01\x00\x44\xac\x00\x00\x88X\x01\x00\x02\x00\x10\x00\x00\x00LIST\x1a\x00\x00\x00INFOISFT\x0e\x00\x00\x00GolfNote\0\0\0\0\0\0data\x00\xff\xff\xff", 1, 80, stdout);
    fwrite(array, 1, size*sizeof(signed short), stdout);
    return 0;
}

```

Python 2:

```
#!/usr/bin/env python
import os
import re
import sys
import math
import struct
import array

#def g():
#    return [int(10000*math.sin(1.0*i*2*3.141592654*440.0/44100.0)) for i in xrange(0,44100)]

# define your g here

sys.stdout.write("RIFFH\x00\x00\x00WAVEfmt\x20\x12\x00\x00\x00\x01\x00\x01\x00\x44\xac\x00\x00\x88X\x01\x00\x02\x00\x10\x00\x00\x00LIST\x1a\x00\x00\x00INFOISFT\x0e\x00\x00\x00GolfNotePy\0\0\0\0data\x00\xff\xff\xff");
array.array("h", g()).tofile(sys.stdout);

```

Perl 5:

```
#!/usr/bin/perl

#sub g() {
#    return (map 10000*sin($_*3.14159265358979*2*440.0/44100.0), 0..(44100-1))
#}

# define you g here

my @a = g();
print "RIFFH\x00\x00\x00WAVEfmt\x20\x12\x00\x00\x00\x01\x00\x01\x00\x44\xac\x00\x00\x88X\x01\x00\x02\x00\x10\x00\x00\x00LIST\x1a\x00\x00\x00INFOISFT\x0e\x00\x00\x00GolfNotePl\0\0\0\0data\x00\xff\xff\xff";
print join("",map(pack("s", $_), @a));

```

Haskell:

```
#!/usr/bin/runhaskell

import qualified Data.Serialize.Put as P
import qualified Data.ByteString as B
import qualified Data.ByteString.Char8 as C8
import Data.Word
import Control.Monad

-- g :: [Word16]
-- g = map (\t->floor $ 10000 * sin(t*2*3.14159265358979*440/44100)) [0..44100-1]
-- insert your g here

main = do
    B.putStr $ C8.pack $ "RIFFH\x00\x00\x00WAVEfmt\x20\x12\x00\x00\x00\x01\x00\x01\x00\x44\xac\x00\x00\x88X\x01\x00\x02\x00\x10\x00\x00\x00LIST\x1a\x00\x00\0INFOISFT\x0e\x00\x00\x00GolfNote\0\0\0\0\0\0data\x00\xff\xff\xff"
    B.putStr $ P.runPut $ sequence_ $ map P.putWord16le g

```

## Example

Here's ungolfed C version modeled after piano sound:

```
void g(signed short *array, int* length) {
    *length = 44100*5;
    int i;

    double overtones[]={4, 1, 0.5, 0.25, 0.125};

    double freq[]   = {393, 416, 376, 355, 339, 451, 555};
    double freq_k[] = {40,  0.8,  1,  0.8,   0.7,  0.4, 0.25};
    double corrector = 1/44100.0*2*3.14159265358979323;

    double volumes_begin[] ={0,     0.025, 0.05,   0.4};
    double volumes_end  [] ={0.025, 0.05,  0.4,    5};

    double volumes_kbegin[]={0,     1.8,   1,      0.4};
    double volumes_kend [] ={1.8,     1,   0.4,    0};

    for(i=0; i<44100*5; ++i) {
        int j;
        double volume = 0;

        for(j=0; j<sizeof volumes_begin/sizeof(*volumes_begin); ++j) {
            double t = i/44100.0;
            if(t>=volumes_begin[j] && t<volumes_end[j]) {
                volume += volumes_kbegin[j]*(volumes_end[j]-t  )/(volumes_end[j]-volumes_begin[j]);
                volume += volumes_kend[j]  *(t-volumes_begin[j])/(volumes_end[j]-volumes_begin[j]);
            }
        }

        int u;
        for(u=0; u<sizeof freq/sizeof(*freq); ++u) {
            for(j=0; j<sizeof overtones/sizeof(*overtones); ++j) {
                double f = freq[u]*(j+1);
                array[i] += freq_k[u]*volume*10000.0/(f)/1*overtones[j]*sin(1.0*i*corrector*f);
            }
        }
    }
}

```

It scores approximately 1330 bytes and provides poor/mediocre quality.

# Answer
> 2 votes
## Java

My boilerplate plays the sound. I could golf `g()` a bit more, but it's currently at 273 chars which is well under 1500. I originally wrote this for 16kHz for a 4kB game and had to tweak the constants a bit to get the right tonal qualities at 44.1kHz playback, but I'm reasonably happy with it.

```
import java.io.*;
import javax.sound.sampled.*;

public class codegolf13003 {
    byte[]g(){byte[]d=new byte[88000];int r=1,R=1103515247,b[]=new int[650],i,o,s,y;for(i=0;i<b.length;r*=R)b[i++]=0x4000+((r>>16)&0x3fff);for(i=o=0;i<d.length;o=s){s=(o+1)%b.length;y=(b[o]+b[s])/2*((r&0x10000)<1?-1:1);r*=R;d[i++]=(byte)(b[o]=y);d[i++]=(byte)(y>>8);}return d;}

    public static void main(String[] args) throws Exception {
        byte[] data = new codegolf13003().g();
        ByteArrayInputStream bais = new ByteArrayInputStream(data);
        AudioFormat format = new AudioFormat(AudioFormat.Encoding.PCM_SIGNED, 44100, 16, 1, 2, 44100, false/*LE*/);
        AudioInputStream stream = new AudioInputStream(bais, format, data.length / 2);
        new Previewer().preview(stream);
    }

    static class Previewer implements LineListener {
        Clip clip;

        public void preview(AudioInputStream ais) throws Exception {
            AudioFormat audioFormat = ais.getFormat();
            DataLine.Info info = new DataLine.Info(Clip.class, audioFormat);

            clip = (Clip)AudioSystem.getLine(info);
            clip.addLineListener(this);

            clip.open(ais);
            clip.start();
            while (true) Thread.sleep(50); // Avoid early exit of program
        }

        public void update(LineEvent le) {
            LineEvent.Type type = le.getType();
            if (type == LineEvent.Type.CLOSE) {
                System.exit(0);
            }
            else if (type == LineEvent.Type.STOP) {
                clip.close();
            }
        }
    }
}

```

Further reading: Karplus-Strong synthesis.

# Answer
> 2 votes
## C

Here's the `g()` function, without the boilerplate.

```
void g(signed short *array, int* length)
{
    short r[337];
    int c, i;

    *length = 44100 * 6;
    for (i = 0 ; i < 337 ; ++i)
        r[i] = rand();
    *array = *r;
    for (i = c = 1 ; i < *length ; ++i) {
        array[i] = r[c];
        r[c] = (r[c] + array[i - 1]) * 32555 / 65536;
        c = (c + 1) % 337;
    }
}

```

An interesting experiment is to play with the first loop that initializes a beginning sequence of random values. Replacing the call to `rand()` with `i*i` changes the character of the sound in a plausible way (that is, it sounds like the synthesis is imitating a different member of the same instrument family). `i*i*i` and `i*i*i*i` give other sound qualities, though each one gets closer to sounding like `rand()`. A value like `i*327584` or `i*571`, on the other hand, sounds quite different (and less like an imitation of something real).

---

Another minor variation of the same function comes even closer to another instrument, or at least it does to my ear.

```
void g(signed short *array, int* length)
{
    int i;

    *length = 44100 * 6;
    for (i = 0 ; i < 337 ; ++i)
        array[i] = rand();
    for ( ; i < *length ; ++i)
        array[i] = (array[i - 337] + array[i - 1]) * 32555 / 65536;
}

```

**Edited to Add:** I hadn't been treating this as a code golf question, since it's not flagged as such (beyond the 1500-char limit), but since it's been brought up in the comments, here's a golfed version of the above (96 characters):

```
g(short*a,int*n){int i=0;for(*n=1<<18;i<*n;++i)
a[i]=i>336?32555*(a[i-337]+a[i-1])/65536:rand();}

```

(I could get it down below 80 characters if I could change the function interface to use global variables.)

---
Tags: music, popularity-contest, audio
---


# Question
Title: How many times is rectangular array A embedded in rectangular array B?
Given two rectangular arrays, A and B, let's say that A is *embedded* in B if A can be obtained from B by deleting some (or none) of the rows and columns of B.

Write a program with the following I/O:

**Input**: two arbitrary rectangular arrays of letters (a-z), as a string from stdin.

**Output**: the number of embeddings of the first array in the second array, followed by a "text picture" of each embedding (showing deleted elements replaced by dots).

(This is a two dimensional generalization of my old question Is string X a subsequence of string Y?)

**Example:**

input:

```
abb
aba

ababb
aabba
babab
abbaa

```

output (if I haven't missed any):

```
5

a..bb
a..ba
.....
.....

ab.b.
.....
.....
ab.a.

ab..b
.....
.....
ab..a

.....
a.bb.
.....
a.ba.

.....
.abb.
.aba.
.....

```

The winner is the shortest such program (least number of characters).

# Answer
## APL (160)

```
{∆,⍨⍴∆←⍵∘{(⍴⍵)⍴(,⍵){⍺:⍵⋄'.'}¨,⍺}¨⊃¨∘.∧/¨∆/⍨⍺∘≡¨⍵∘{(⊃⍵)⌿⍺/⍨⊃⌽⍵}¨∆←,⊃∘.,/⊂¨¨K{⍵=0:⊂⍺/1⋄~(⍳⍺)∘∊¨⍵{⍺=1:(⍳⍵)⋄∆/⍨{∧/</¨2,/⍵}¨∆←,⍳⍺/⍵}⍺}¨(K←⍴⍵)-⍴⍺}/{×⍴K←⍞:∇⍵,⊂K⋄↑⍵}¨⍬⍬

```

Output:

```
      {∆,⍨⍴∆←⍵∘{(⍴⍵)⍴(,⍵){⍺:⍵⋄'.'}¨,⍺}¨⊃¨∘.∧/¨∆/⍨⍺∘≡¨⍵∘{(⊃⍵)⌿⍺/⍨⊃⌽⍵}¨∆←,⊃∘.,/⊂¨¨K{⍵=0:⊂⍺/1⋄~(⍳⍺)∘∊¨⍵{⍺=1:(⍳⍵)⋄∆/⍨{∧/</¨2,/⍵}¨∆←,⍳⍺/⍵}⍺}¨(K←⍴⍵)-⍴⍺}/{×⍴K←⍞:∇⍵,⊂K⋄↑⍵}¨⍬⍬
abb
aba

ababb
aabba
babab
abbaa

 5  .....  .....  ab..b  ab.b.  a..bb
    a.bb.  .abb.  .....  .....  a..ba
    .....  .aba.  .....  .....  .....
    a.ba.  .....  ab..a  ab.a.  .....

```

Explanation:

* `{`...`}/{×⍴K←⍞:∇⍵,⊂K⋄↑⍵}¨⍬⍬`: read the two arrays from the keyboard, and return them as two matrices. Reduce the following function over the list of the two matrices.
* `∆{`...`}¨(∆←⍴⍵)-⍴⍺`: get the height and width of each of the matrices. In both the width and the height, get a list of possible lines to drop.

+ `⍵=0:⊂⍺/1`: if the matrices are the same length in a dimension, never drop any lines from that dimension. Otherwise:
    + `⍺=1:(⍳⍵)⋄`: If the difference is one, try to drop each line
    + `∆/⍨{∧/</¨2,/⍵}¨∆←,⍳⍺/⍵`: otherwise, drop each possible combination of  lines.
* `∆←,⊃∘.,/⊂¨¨`: combine each height mask with each width mask, giving all possible combinations to make the second list the size of the first.
* `⍵∘{(⊃⍵)⌿⍺/⍨⊃⌽⍵}¨∆`: for each possible combination, remove those lines from the second matrix.
* `∆/⍨⍺∘≡¨`: drop all the ones that are not equal to the first matrix, giving the solutions.
* `⊃¨∘.∧/¨`: for each of the possible solutions, make a matrix with `0` where a dot should go and `1` where the corresponding character from the first matrix should go.
* `⍵∘{(⍴⍵)⍴(,⍵){⍺:⍵⋄'.'}¨,⍺}¨`: for each of these, flatten both the second matrix (`,⍵`) and the matrix of dots (`,⍺), and take either the character or a dot for each position (`{⍺:⍵⋄'.'}¨). Then reshape it to the shape it had before (`(⍴⍵)⍴`).
* `∆,⍨⍴∆`: give the amount of solution, and each solution.
> 7 votes

# Answer
# Mathematica, 186 chars

```
{a,b}=Characters/@StringSplit@InputString[]&~Array~2;{Length@#,Grid/@#}&[ReplacePart[b,Except[$|##&@@Tuples@#,{_,_}]->"."]&/@Select[Tuples[Subsets/@Range/@Dimensions@b],b[[##]]&@@#==a&]]

```

### Example:

```
In[1]:= {a,b}=Characters/@StringSplit@InputString[]&~Array~2;{Length@#,Grid/@#}&[ReplacePart[b,Except[$|##&@@Tuples@#,{_,_}]->"."]&/@Select[Tuples[Subsets/@Range/@Dimensions@b],b[[##]]&@@#==a&]]
? abb aba
? ababb aabba babab abbaa

Out[1]= {5, {a . . b b, a b . b ., a b . . b, . . . . ., . . . . .}}
             a . . b a  . . . . .  . . . . .  . a b b .  a . b b .
             . . . . .  . . . . .  . . . . .  . a b a .  . . . . .
             . . . . .  a b . a .  a b . . a  . . . . .  a . b a .

```
> 6 votes

# Answer
# Python 2 with Numpy, 342 chars

```
from numpy import*
from itertools import*
import sys
S=str.split
C=combinations
R=range
a,b=[mat(map(list,S(x)))for x in S(sys.stdin.read(),'\n\n')]
n,m=b.shape
o,p=a.shape
z=[]
for i in product(C(R(n),o),C(R(m),p)):
 i=ix_(*i);e=b[i]
 if all(a==e):f=copy(b);f[:]='.';f[i]=e;z+=[f]
print len(z)
for x in z:print'\n'.join(map(''.join,x))+'\n'

```

## Output Example

```
5
a..bb
a..ba
.....
.....

ab.b.
.....
.....
ab.a.

ab..b
.....
.....
ab..a

.....
.abb.
.aba.
.....

.....
a.bb.
.....
a.ba.

```
> 3 votes

# Answer
# Haskell, 364 chars

```
m=map
l=length
u=unlines
v=reverse
z=zip[0..]
q s=p(lines s)[]
e i a=[a!!j|j<-i]
main=g.w.q=<<getContents
g x=(print.l)x>>(putStr.u.m u)x
c 0=[[]];c n=let x=m(m(1+))$c(n-1)in x++m(0:)x
p(c:x) a|c==""=(v a,fst$p x[])|1<2=p x(c:a);p[]a=(v a,[])
w(a,b)=[m(\(p,r)->m(\(q,x)->if(elem p i&&elem q j)then(b!!p!!q)else '.')$z r)$z b|i<-c.l$b,j<-c.l$b!!0,a==(m(e j).e i)b]

```

## Ungolfed Version, 716 chars

```
parse (c:x) a | c == "" = (reverse a, fst$parse x [])
              | otherwise = parse x (c:a)
parse [] a = (reverse a, [])
readMat s = parse (lines s) []

choose 0 = [[]]
choose n = let
  x = map (map (1+))$choose (n-1)
  in x ++ map (0:) x

select ix a = [a!!i | i<-ix]

for = flip map
make b (ix, jx) =
  for (zip [0..] b) (\(i,r) ->
    for (zip [0..] r) (\(j,x) ->
      if elem i ix && elem j jx
      then b!!i!!j
      else '.'
    )
  )

main = do
  s <- getContents
  let (a, b) = readMat s
      (n, m) = (length b, length.head$ b)
  let ans = [make b (ix, jx) | ix <- choose n, jx <- choose n,
              a == (map (select jx).select ix$ b)]
  print$ length ans
  putStrLn$unlines.map unlines$ ans

```
> 1 votes

# Answer
Ruby 448

```
class Array
alias t transpose
alias z size
alias e each
alias s select
end

def x
v=[]
while(w=gets.chop).size>0 do
v<<w.split('')
end
v
end

def w(i,j)(0...i).to_a.combination(i-j).to_a end

a=x
n=a.z
a=a.t
o=a.z
b=x
q=b.z
r=b[0].z
w=['.']
y=w*r
z=w*q
f=[]
w(q,n).e{|u|w(r,o).e{|v|
h=b.dup
u.e{|i|h[i]=y}
h=h.t
v.e{|j|h[j]=z}
h=h.t
f<<h if(h.s{|i|i!=y}.t.s{|i|i!=w*n})==a}}
p f.z
puts
f.e{|b|b.e{|i|k='';i.e{|j|(k<<' ')if k.size>0;k<<j}
puts k}
puts}

```
> 1 votes

---
Tags: code-golf, array
---


# Question
Title: Download all google results for given Query
### The Task

Write a program to take a query from STDIN and then download the first 20 search results of that query from google and save them in a folder named `Search` as `html` files. Or if google points to a non-html file (like PDF), save whatever it is. Type of results may depend on the programmer, but the first 20 results should be matched. Ads etc. can also be counted as results.

### Scoring

This is ; shortest code wins.

# Answer
> 3 votes
# Ruby, ~~260~~ 256 characters

```
require'net/http';require'nokogiri';i=0;`mkdir Search`;`cd Search`;N=Net::HTTP
Nokogiri::HTML.parse(N.get"www.google.cz","/search?"+URI.encode_www_form(q:gets,num:20)).css(".r a").each{|e|File.open("#{i+=1}",?w)<<N.get(URI e['href'][/q=(.*?)&/,1])rescue 0}

```

Note: when testing this multiple times, be sure to add ``cd ..`` between each test to reset the current working directory lest you end up with `whatever/Search/Search/Search/Search...`

If we are allowed to fail on first unsuccessful result, we can drop `rescue 0` at the end of the second line and save 8 characters.

if we may assume input is alphanumeric and a single word, we can skip encoding and shave off some more characters. (**235 chars** with error recovery, **227** without)

```
require'net/http';require'nokogiri';i=0;`mkdir Search`;`cd Search`;N=Net::HTTP
Nokogiri::HTML.parse(N.get"www.google.cz","/search?num=20&q="+gets).css(".r a").each{|e|File.open("#{i+=1}",?w)<<N.get(URI e['href'][/q=(.*?)&/,1])}

```

# Answer
> 2 votes
## Bash

```
mkdir Search;cd Search;wget -U msie -rl 1 -e robots=off -d http://www.google.com http://www.google.com/search?q=`cat`&num=20

```

Because `wget` is the right way to do that.

---
Tags: code-golf
---


title: Find prime factors

text:
# Question
Title: Find prime factors
A whole program to find the prime factors of a given number. The number will be given on standard input.

# Answer
> 6 votes
## Bash Shell

**6 Chars**

`factor`

If `rot13` can be allowed, i don't see why this one is an issue...I'm sorry but this is very trivial.

# Answer
> 6 votes
## J - 2 characters

```
q:

```

Example:

```
   q: 31415
5 61 103

```

# Answer
> 5 votes
## dc, 48 chars

```
[ldp0<x]sp?2sd[[dsrld~0=p]dsxxcld1+sdlrd1<y]dsyx

```

# Answer
> 4 votes
# Ruby - 50 49 47 44 42 chars

```
2.upto(n=gets.to_i){|i|n/=p i while n%i<1}

```

# Answer
> 3 votes
## Python: 58

```
n=input()
for i in range(2,n+1):
 while n%i<1:print i;n/=i

```

# Answer
> 3 votes
## Perl, 42 chars

```
map{$n/=$_,print$_,$/until$n%$_}2..($n=<>)

```

# Answer
> 3 votes
## Windows PowerShell, 46

Naïve solution.

```
2..($x=+"$input")|%{for(;!($x%$_)){$_;$x/=$_}}

```

# Answer
> 2 votes
## Python (55)

based on marcog

```
n=input()
i=1
while~-n:
 i+=1
 while n%i<1:print i;n/=i

```

# Answer
> 2 votes
## Pure Bash Solution (60 characters)

Based on F.Hauri's solution (thanks to him):

```
read p;for((i=2;p-1;));do((p%i++||(p/=--i)*0))||echo $i;done

```

# Answer
> 1 votes
## Javascript (54)

```
n=prompt()*1;for(i=2;n>1;n/=n%i?(++i,1):(alert(i),i));

```

# Answer
> 1 votes
## C (68)

Not the shortest, but I was curious to see how a C solution could compare.

```
d=2;main(n){scanf("%d",&n);for(;n>1;)n%d?++d:printf("%d\n",d,n/=d);}

```

# Answer
> 1 votes
## 100% Pure : 72 chars

```
read p;for((i=1;p>i++;));do while((p%i<1));do echo $i;((p/=i));done;done

```

or

```
read p;i=1;while((p>i++));do while((p%i<1));do o+=$i\ ;((p/=i));done;done ;echo $o

```

This seem longer, but in replacing `for` by `while`, I could make an overall loop and using `alias` to reduce then code:

```
alias D=done W=while
prime() { W read p;do i=1 o=;W((p>i++));do W((p%i<1));do o+=$i\ ;((p/=i));D;D;echo $o;D;}
unalias D W

```

This way, my (written) code **whith** the loop is 77 char length.

Anyway, the function is memorized with full command names:

```
declare -f prime
prime ()
{
    while read p; do
        i=1 o=;
        while ((p>i++)); do
            while ((p%i<1)); do
                o+=$i\ ;
                ((p/=i));
            done;
        done;
        echo $o;
    done
}

```

# Answer
> 1 votes
# Mathematica, 26 chars

```
#&@@@FactorInteger@Input[]

```

# Answer
> 1 votes
## R, 72 characters

Just for the kicks, an attempt without using any preexisting function to prime-factorize:

```
n=scan(n=1);m=1:n;M=m[!n%%m&!m%in%c(1,n)];M[rowSums(!outer(M,M,`%%`))<2]

```

Ungolfed with explanations:

```
n <- scan(n=1) #Take one number from stdin
m <- 1:n
#Of which of the integers from 1 to n is n a multiple (excluding 1 and himself):
M <- m[!n%%m & !m%in%c(1,n)]
#Trim that list by excluding integers that are multiples of others in the list:
M[rowSums(!outer(M,M,`%%`))<2]

```

NB: Instead of checking if `n%%m==0`, use the fact the `0` coerce as `FALSE` when using `!`.

# Answer
> 0 votes
# Scala, 111 bytes:

```
def f(i:Int,c:Int=2):List[Int]=if(i==c)List(i)else
if(i%c==0)c::f(i/c,c)else f(i,c+1)
f(readInt).mkString(" ")

```

# Answer
> 0 votes
## perl5.10: 36 chars

```
map{$p/=$_,say until$p%$_}2..($p=<>)

```

# Answer
> 0 votes
# Haskell 74 chars

```
s n=f((==0).mod n)[2..n]
main=readLn>>=print.f((==1).length.s).s
f=filter

```

## Example

```
12 -> [2,3]
128 -> [2]
60 -> [2,3,5]

```

# Answer
> 0 votes
# Octave, 17 chars

```
factor(input(''))

```

---
Tags: code-golf, primes
---


title: A simple logic gate calculator

text:
# Question
Title: A simple logic gate calculator
Your mission, if you choose to accept it, is to construct a simple truth evaluator for the following logical operators:

```
----------------------------------------------------------------------------------
  Logical Name          |  Gate Name   |  Symbol  |  Symbol Name  |  Truth Table
----------------------------------------------------------------------------------
  Identity              |  is          |          |  (none)       |  10
  Negation              |  not         |    ~     |  tilde        |  01
  Conjunction           |  and         |    &     |  ampersand    |  1000
  Disjunction           |  or          |    |     |  pipe         |  1110
  Negative Conjunction  |  nand        |    ^     |  caret        |  0111
  Joint Denial          |  nor         |    v     |  "vee"        |  0001
  Exclusive Disjunction |  xor         |    x     |  "ecks"       |  0110
  Equivalence           |  equals/xnor |    =     |  equals       |  1001
  Implication           |  implies     |    >     |  greater than |  1011

```

Truth tables are in the following order:

1. 1 1
2. 1 0
3. 0 1
4. 0 0

Input will come as a simple string of 0, 1, and the symbol. You can either accept input as a parameter or read it from the user on stdin. Here are some sample input/output pairs:

```
Input: 1
Output: 1

Input: ~1
Output: 0

Input: 0|1
Output: 1

Input: 1>0
Output: 0

```

The unary operator (negation) will always appear before the boolean value, while the binary operators will always appear between the two boolean values. You can assume that all input will be valid. Strings are regular ASCII strings.

If you prefer, you can use T and F rather than 1 and 0. **-6** to your character count if you support both.

This is : shortest code in any language wins!

# Answer
> 6 votes
## APL (45 - 6 = 39)

```
⍎(1+9≠L)⌷¨↓⍉Z⍪⍉⍪'10∧∨⍲⍱≠≤*'[L←'TF&|^vx>'⍳Z←⍞]

```

Supports `T` and `F` as input but will always output `0` or `1`.

Explanation:

* `Z←⍞`: read a line and store it in `Z`
* `L←'TF&|^vx>'⍳Z`: get the index in `'TF&|^vx>'` for each character in `Z`, giving `9` if the character is not in `'TF&|^vx>'`.
* `'10∧∨⍲⍱≠≤*'[`...`]`: find the corresponding character in `'10∧∨⍲⍱≠≤*'`. (So characters that weren't in the first list become `*`).
* `↓⍉Z⍪⍉⍪`: make this into a matrix, put the original (`Z`) on top of it, and split it into a list of strings, where the first character is the original and the second character is its translation, if any.
* `(1+9≠L)⌷¨`: for each of these strings, get the first character if there was no translation (if `L=9` in that place) and the second character if there was.
* Example: if the input had been `T|0`, we would have `1∨0` by now which is the corresponding APL expression
* : eval

Note: `~` and `=` already do the right thing so they don't need to be replaced by anything.

# Answer
> 8 votes
## C - ~~165~~ 127

That was fun! Plain lookup table relying on a fixed offset for the lookup.

```
main(){
  char*s="100011001110110v& x = |^> /~",
       t[6]="0/xxx",
      *u= strchr((gets(t+2),t),0)-3;
  putchar(strchr(s,u[1])[*u*2+u[2]-159]);
}

```

For some reason `gets` doesn't get implicitly declared, so when I removed the include I had to change `gets(t+2)` to `(gets(t+2),t)` (or similarly elsewhere, costing as much).

---

### Explanation

First of all, since the truth tables for the operators have plenty of overlapping characters we wish to store the lookup tables in a way so that we allow overlap. Here's how I chose to store them:

```
v    &    x    =    |    ^    >       ~     (operation)
1000 0001 0110 1001 0111 1110 1101 01 10    (truth table [order 00,01,10,11])
0    1    3    5    7    8    9    B  D     (offset in LUT below)

0123456789ABCDE   (offsets)
100011001110110   (values)

```

Next, we want to map operator symbols to these offsets. We do this by storing the operator symbols in the same string at a fixed offset from the LUT data (namely, 16 characters later, i.e. directly after the LUT data). The lookup process is "find operator in `s`, subtract `16`, add `left*2+right` (left/right operand). For the lookup of the empty "identity operation", due to how the input is fetched the operator in this case will resolve to whatever `t[1]` is initialised to--in our case `/`. Thus, we use `/` as the lookup table key to represent the identity operation. When we process the unary `~` operation "`left`" (for the lookup calculation mentioned earlier) is always this same `/` . `/` happens to be one less than `0` ASCII-wise, meaning when we compensate for ASCII digits `\` will represent `-1`. The slash in the lookup table key area (second-to-last character in `s`, that is) is positioned to compensate for this.

Next up, input handling. The input has dynamic length, but it'd be easier if we have specific static names for the left operand, operator and right operand, regardless of input. If we pretend that we could read the input right-to-left, this would basically happen automagically--the right operand is always the rightmost character, the operator (if present) is second-to-rightmost, the left operand (if present) is third-to-rightmost. In order to be able to index the string like this, we use `strchr` in order to locate the `\0` terminator (`- 3` to simplify indexing). This shows why `t[0]` and `t[1]` become the left operand/operator respectively when the input is 1 or 2 characters.

Putting it together, the output would be `putchar(strchr(s,u[1])[(u[0] - '0')*2 + (u[2] - '0') - 15])`, but some refactoring and constant folding instead gets us the shorter `putchar(strchr(s,u[1])[u[0]*2+u[2]-159])`.

# Answer
> 4 votes
## Tcl, ~~212~~ 208-6 = 202

```
proc o n\ e {proc $n a\ b expr\ $e}
o > {$a<=$b}
o v {!($a|$b)}
o x {$a^$b}
o ^ {!($a&$b)}
namespace pat tcl::mathop
lmap o\ b [lassign [split [string map {~0 1 ~1 0} $argv] {}] a] {set a [$o $a $b]}
puts $a

```

Ungolfed:

```
# Defines an operator
proc operator {name expression} {
    proc $name {a b} "expr $expression"
}
operator > {$a<=$b}
operator v {!($a|$b)}
operator x {$a^$b}
operator ^ {!($a&$b)}
# Call the commands in ::tcl::mathop if the command is not in the global namespace
namespace path tcl::mathop
# lmap instead foreach
# assume that we only got 1 argument.
foreach {op b} [lassign [string map {{~ 0} 1 {~ 1} 0} [split $argv {}]] a] {
   set a [$op $a $b]
}
puts $a

```

I think the foreach line needs some explanation:

* `split $argv {}` splits the input string (it is actually a list, but code-golf) into it's characters.
* `string map {{~ 0} 1 {~ 1} 0} ...` takes a string and replaces `~ 0` with `1` and `~ 1` with `0`
* `lassign ... a` takes the first element of the list and assigns it to the variable a, returns the rest.
* `foreach {op b} ... {code}` walks over the list and takes 2 elements each time: `op` and `b`
* `set a [$op $a $b]` executes the command in the variable `op`, stores the result in `a`

# Answer
> 3 votes
## JavaScript - ~~107~~ 105 characters

```
alert((x=eval(prompt().replace(/v/,'|~').replace(/\^/,'&~').replace(/x/,'^').replace(/=/,'==')))!=-1?x:0)

```

# Answer
> 3 votes
### Befunge-98 - ~~104 101 98-6~~ 72

...because every task needs an esolang solution.. translation of my C implementation, but processing characters one at a time instead.

```
#v~
2_vp5a00+*2%2\p10\%
0:<+1_v#-g5\g1
1_|#:\</2\-
.@>2%
 v   ~x^&=.>  |

```

~~Fun fact: change the `@` to `a,$` and you get a fancy neverending REPL instead (though, if you do this you'll notice that identity is actually "repeat last command with lhs=0 and rhs=input", which just happens to default to identity).~~ The REPL is no more.

Ungolfed (earlier version):

```
v10001100111011v& x = |^>~
  $       1111111111222222
 1234567890123456789012345

 [read input]
> ~ :a- #v_   $ 21g " "- + 0g , @

v p11:   <
   ↑save chr

0 ←lup   [traverse LUT]
> 1+  :11g  \0g -! #v_
 v                  <
    lup chr acc
v>  :3` #v_  $"0"-\2*+

               v>   . , a,
 v       <
v> 9+9+ 21p $

```

**Edit:** inspired by @jpjacobs' solution, I now rely on the position of characters in the LUT to represent truth tables. E.g., `|` is on position 11102 = 14 because this corresponds to the truth table for `|`.

# Answer
> 2 votes
# J - 6567-6=61

No more the b. Adverb. Without counting the assignment of the function: 67 characters for the TF version, 63 for the non-TF version:

```
lgcTF =:".@({&('*+-+-<*01',.3 6#'.:')"1@n^:(9>n=:'&|~xv>^FT'&i.)@{.&.>&.;:)
lgc   =:".@({&('*+-+-<*',.3 4#'.:')"1@n^:(7>n=:'&|~xv>^'&i.)@{.&.>&.;:)

```

LgcTF handles both 0 and 1 as well as T and F.

Supports all of J's syntax in terms of trains, parenthesis, and evaluates strictly right to left (no other precedence rules).

All characters not in the operator list + Z can not be used, others will act as in standard J (including variables).

Usage:

```
NB.Assign TF anyhow
T=:1 [ F=: 0
lgc 'T & F'
0
lgc ' T ~@& F' NB. negation after and = nand
NB. make a truth table
d=: 0 1
lgc 'd ~@|/ d'
1 0
0 0
NB. and so on...

```

# Answer
> 1 votes
# Postscript 263

Firefly's idea translated to Postscript.

```
{(0/xxx)dup 2 3 getinterval(%lineedit)(r)file exch
readstring pop length 1 sub 3
getinterval(100011001110110v& x = |^> /~)dup
2 index 1 1 getinterval search pop exch pop exch pop
length 3 2 roll{}forall exch pop exch 2 mul add 159 sub add
1 getinterval =}loop

```

Indented:

```
%!

{
    (0/xxx) dup 2 3 getinterval
    (%lineedit)(r)file exch % (0/xxx) file (xxx)
    readstring pop
    length % (0/xxx) len(x|xx|xxx)
    1 sub 3 getinterval % (0/x)|(/xx)|(xxx)
    (100011001110110v& x = |^> /~) dup
    2 index 1 1 getinterval search pop % (0/x)|(/xx)|(xxx) s post match pre
    exch pop exch pop % (xxx) s pre
    length
    3 2 roll {} forall exch pop % s len(pre) u_0 u_2
    exch 2 mul add 159 sub add % s ind
    1 getinterval
    = flush
} loop

```

# Answer
> 1 votes
# Befunge-93, 86 characters

Works by hashing the second symbol of the input (finding a function that was both compact and avoided collisions was some work) for a y coordinate, and taking the first and third symbols each modulo 2 as the two least significant bits of the x coordinate, then retrieving whatever value is at the indicated position. A better hash function or more compact method of storing/addressing the truth tables are just two possible ways one could cut down on the length.

```
~~~\:8/\5%:++00p2%\2%2*+00gg,@
0 1

1001
0001
1101
1

0
0110

1110
1000

0111

```

---
Tags: code-golf, logic-gates
---


# Question
Title: Shortest code - Finding the kth good cipher
**Challenge:** A cipher (which is a positive integer) which has any substring not divisible by 2, or has a substring divisible by 11 (other than 0), is defined as 'bad'. All other ciphers are defined as 'good'. Find the kth cipher, in ascending order, which is 'good'.

**Input format**

The first line of input has a single integer T, the total number of test cases. The next T lines each have an integer k on them.

**Output Format**

The output should contain T integers on T different lines, the kth good cipher.

**Sample Input**

2
1
136

**Sample Output**

2
4008

# Answer
## Perl, ~~75~~ 74 characters

```
map{map{1while++$n=~/[13579]|(.+)(?(?{$^N<1|$^N%11})!)/}1..<>;$n=say$n}1..<>

```

I should point out that the character count is taking advantage of Perl's bizarre feature of allowing a special variable of the form `$^X` to be spelled with a literal ctrl-*X* character.

The regex extensions being utilized are also terrifying, but boy do they come in handy.
> 2 votes

# Answer
## Haskell, 187

```
import Data.List
d=drop 1
e=[]:d e>>=(\z->map(\y->z++[y])"02468")
f=filter
g=f(all((>0).(`rem`11)).f(>0).map(read.('0':)).(>>=inits).tails)e
main=interact$unlines.map((g!!).read).d.lines

```

Could save 4 characters by inlining `g`, but then the code wouldn't be quite as nice.

If the input wasn't preceded by a test case count (like in the Ruby submission), then could save 6 more characters.

```
& runhaskell 13166-Cipher.hs
2
1
2
136
4008

```
> 2 votes

# Answer
## APL (70)

```
⍪{⎕{⍺⍺<Z←⍺+∧/{~2|⍵,0=11|⍵~0}⍎¨⊃,/{↑∘⍵¨⍳⍴⍵}¨↓∘Z¨0,⍳⍴Z←⍕⍵:⍵⋄Z∇⍵+1}⍨0}¨⍳⎕

```
> 2 votes

# Answer
## Ruby, ~~231~~ ~~227~~ 219

```
gets
s=[]
l=[]
while(g=gets.to_i)>0
s.push g
end
z=2
until l.size>=s.max
a=z.to_s.split''
l.push z if(1..a.size).flat_map{|n|a.each_cons(n).map{|x|x.join.to_i}}.all?{|x|x<1||x%11>0&&x%2<1}
z+=1
end
puts s.map{|x|l[x-1]}

```

Input is terminated with an empty line.

If the input was just a list of indeces without the length, I could save 5 characters.

Sample run:

```
c:\a\ruby>goodc
2
1
136

2
4008

c:\a\ruby>

```
> 1 votes

# Answer
## Sage Notebook, ~~167~~ 166

```
for k in list(file(DATA+'i'))[1:]:
 j=n=0
 while j<int(k):n+=1;j+=not[t for t in[int(`n`[i:j])for i in[0..len(`n`)]for j in[i+1..len(`n`)]]if(t%11==0)*t+t%2]
 print n

```

Sample run ...

**Input** (in data file named 'i'):

```
2
1
136

```

**Output**:

```
2
4008

```

## Python 2, ~~180~~ 179

```
for k in[input()for i in[0]*input()]:
 j=n=0
 while j<int(k):n+=1;j+=not[t for t in[int(`n`[i:j])for i in range(len(`n`))for j in range(i+1,len(`n`)+1)]if(t%11==0)*t+t%2]
 print n

```

Sample run ...

```
>>> 2
>>> 1
>>> 136
2
4008

```
> 1 votes

---
Tags: code-golf
---


title: So... what is your StackOverflow score?

text:
# Question
Title: So... what is your StackOverflow score?
This is a simple one. Given the input of a number, return the name and reputation score of the Stack Overflow user with that **given ID**. Your program can assume that it is always given a valid and existent user ID.

For example: given the input `764357` (which is my userID on StackOverflow) the program would return `LegoStormtroopr 3,088` (approximately) it might change.

You get the URL: "https://stackoverflow.com/users/" or "http://api.stackexchange.com/2.1/users/" for free, so your score is `length of your program - 31 or 39`, **depending on which URL you use - but declare which it is**. This prevents people from abusing URL shorteners.

edit: And no calling a custom made API that query Stack Overflow, and returns just the name and score. ~~But if you know of an offical API, then that is totally legitimate.~~

edit2: If you need an example input: I've given my ID below, feel free to add your own ID, username and score below to help others out. Note again, this is for the main Stack Overflow site.

```
764357   returns   LegoStormtroopr 3,088

```

# Answer
# Shell script: ~~64~~ 51 characters

```
curl -sL http://stackoverflow.com/users/`cat`|grep -oPm2 'n">\K[0-9,]+|e">\K[^<]+'

```

Sample run:

```
bash-4.1$ curl -sL http://stackoverflow.com/users/`cat`|grep -oPm2 'n">\K[0-9,]+|e">\K[^<]+'
662504
manatwork
834

bash-4.1$ curl -sL http://stackoverflow.com/users/`cat`|grep -oPm2 'n">\K[0-9,]+|e">\K[^<]+'
764357
Lego Stormtroopr
3,087

```

(Note that you have to press `^D` after typing in the input interactively. Or just pipe it to the command.)
> 15 votes

# Answer
# Ruby: ~~84~~ 70 characters

```
s=open("http://stackoverflow.com/users/"+gets).read
puts s[/me">(.+)</,1],s[/n">([\d,]+)/,1]

```

Sample run:

```
bash-4.1$ ruby -ropen-uri -e 's=open("http://stackoverflow.com/users/"+gets).read;puts s[/me">(.+)</,1],s[/n">([\d,]+)/,1]' <<< '662504'
manatwork
834

bash-4.1$ ruby -ropen-uri -e 's=open("http://stackoverflow.com/users/"+gets).read;puts s[/me">(.+)</,1],s[/n">([\d,]+)/,1]' <<< '764357'
Lego Stormtroopr
3,087

```
> 8 votes

# Answer
# Python 2.7 - 119

### (150 - 31)

Without regex:

```
from urllib import*
s=urlopen("http://stackoverflow.com/users/%d"%input()).read()
p=str.split
print p(p(s,'r ')[1],' -')[0],p(p(s,'ore">')[1],'<')[0]

```
> 6 votes

# Answer
# Python 3, 117

`117 = 148 - 31`

I don't think searching in plain HTML source code will lead to strong solution. For example, some weird stuff in one's profile may break your solutions. So I'd like to search using CSS selectors.

```
from lxml.html import*
C=parse('http://stackoverflow.com/users/'+input()).getroot().cssselect
print(C('[id^=u]')[0].text,C('[class$=ore]')[0].text)

```
> 6 votes

# Answer
# Javascript 217

Heres a ungolfed Javascript Version using the official api with JSONP, to start with . Using the url would require XHR, which sould be quite verbose, if i find some time i'll try a more golfed version though.

```
d=document;function f(a){y=a.items[0];alert(y.display_name+" "+y.reputation)}x=d.createElement("script");x.src="https://api.stackexchange.com/2.1/users/"+prompt()+"?site=stackoverflow&callback=f";d.body.appendChild(x)

```
> 5 votes

# Answer
## Perl 5 (with Mojolicious), 87 - 31 = 56 bytes

```
say/h1.*>(.*)</,$/,/core">(.*?)</ for g("http://stackoverflow.com/users/".pop)->dom

```

Sample run:

```
$ perl -Mojo -E 'say/h1.*>(.*)</,$/,/core">(.*?)</ for g("http://stackoverflow.com/users/".pop)->dom' 764357
Lego Stormtroopr
3,103

```

Readable & clean: 128 - 31 = 97 bytes

```
say $_->at("#user-displayname")->text, ": ", $_->at(".reputation a")->text for g("http://stackoverflow.com/users/".pop)->dom

```

Sample run:

```
$ perl -Mojo -E 'say $_->at("#user-displayname")->text, ": ", $_->at(".reputation a")->text for g("http://stackoverflow.com/users/$ARGV[0]")->dom' 764357
Lego Stormtroopr: 3,103

```
> 5 votes

# Answer
## R: 150-31=119

```
f=function(i){S=function(x)strsplit(grep(x,scan(paste0("http://stackoverflow.com/users/",i),"",sep="\n"),v=T)[1],">|<")[[1]][3];cat(S("h1"),S("=re"))}

```

Quite simply picks the first lines containing `h1` (for the name) and `=re` (for the score) using `grep` with argument `value=TRUE` (here `v=T`) and then split the string (using `strsplit` at characters `>` and `<`. Inconveniently it queries the page twice (hence the two "Read n items" warnings) but that was shorter.

```
>f(1451109)
Read 917 items
Read 917 items
plannapus 6,566

```
> 4 votes

# Answer
## Tcl, (231 - 39) 192

not the shortest way, but using the official API

```
package r http
package r json
set d [lindex [dict get [json::json2dict [http::data [http::geturl http://api.stackexchange.com/2.1/users/$argv?site=stackoverflow]]] items] 0]
puts [dict get $d display_name]\ [dict get $d reputation]

```

And in spirit of the **original** question:

```
package r http
package r json
set c [dict get [json::json2dict [http::data [http::geturl http://api.stackexchange.com/2.1/users/?order=desc&sort=reputation&site=stackoverflow&min=$argv&max=$argv]]] items]
foreach d $c {puts "[dict get $d display_name] [dict get $d reputation]"}

```

Finds users with that reputation
> 4 votes

# Answer
# Shorter CoffeeScript: 143 characters (182 - 39)

This relies on the API always returning the object keys in the same order, but shaves off 7 characters.

```
f=(r)->u=Object.keys(items[0]);alert u[3]+' '+u[5]
d=document
j=d.createElement('script')
j.src="//api.stackexchange.com/2.1/users/"+prompt()+'?site=diy&jsonp=f'
d.body.appendChild j

```

# CoffeeScript: 150 characters (189 - 39)

```
f=(r)->u=r.items[0];alert u.display_name+' '+u.reputation
d=document
j=d.createElement('script')
j.src="//api.stackexchange.com/2.1/users/"+prompt()+'?site=diy&jsonp=f'
d.body.appendChild j

```

(Note that the program prompts you for "undefined" -- it's asking for the User ID.)
> 3 votes

# Answer
## R - 84

84 = 115 - 31

```
sub(".*\\/(.*)\\?.*>(.*)<.*","\\1 \\2",grep("b=r",scan(paste0("http://stackoverflow.com/users/",scan(n=1)),""),v=T)[1])

```

Simulation:

```
> sub(".*\\/(.*)\\?.*>(.*)<.*","\\1 \\2",grep("b=r",scan(paste0("http://stackoverflow.com/users/",scan(n=1)),""),v=T)[1])
1: 1201032
Read 1 item
Read 2976 items
[1] "flodel 31,093"

```
> 3 votes

# Answer
## 101 100 - CoffeeScript with jQuery

```
$.getJSON "http://api.stackexchange.com/2.1/users/#{prompt()}?site=stackoverflow",(d)->alert [d.items[0].reputation,d.items[0].display_name]

```

Here's a fiddle; just know that it prompts you when you first open the page, so have a ID ready, or press Run again.

Or we can be super hacky to save a whole character!

```
$.getJSON "http://api.stackexchange.com/2.1/users/#{prompt()}?site=stackoverflow",(d)->`with(d.items[0])alert([reputation,display_name])`;1

```
> 3 votes

# Answer
# Python 2.7 - 112

### 112 = 143 - 31

A newer, short version that uses some of the ideas from Steven Rumbalski answer, while still using Regex.

```
import urllib,re
r=re.findall('r (.*?) -|re">(.*?)<',urllib.urlopen("http://stackoverflow.com/users/%d"%input()).read())
print r[0][0],r[2][1]

```

### 133 = 164 - 31

Here is a base version for people to work from, but I'm sure people can get even shorter.

```
import urllib,re
u=input()
s=urllib.urlopen("http://stackoverflow.com/users/%d"%u).read()
r=re.findall('name.*?>(.*?)</h1|tion.?>(.*?)</a',s)
print r[0][0],r[1][1]

```
> 2 votes

# Answer
# GNU Awk: 217 characters

Just because GNU `awk` supports TCP natively: no module/library/external tool.

```
{RS="\r"
print h("/users/"$0,$0,"/",4),h($2,$2"\\?","<|>",3)}function h(p,m,r,f){d="stackoverflow.com"
g="/inet/tcp/0/"d"/80"
print"GET "p" HTTP/1.1\nHost:"d"\n"|&g
close(g,"to")
while(g|&getline)if($0~m){close(g,"from")
split($0,a,r)
return a[f]}}

```

Sample run:

```
bash-4.1$ awk '{RS="\r";print h("/users/"$0,$0,"/",4),h($2,$2"\\?","<|>",3)}function h(p,m,r,f){d="stackoverflow.com";g="/inet/tcp/0/"d"/80";print"GET "p" HTTP/1.1\nHost:"d"\n"|&g;close(g,"to");while(g|&getline)if($0~m){close(g,"from");split($0,a,r);return a[f]}}' <<< 662504
manatwork 854

bash-4.1$ awk '{RS="\r";print h("/users/"$0,$0,"/",4),h($2,$2"\\?","<|>",3)}function h(p,m,r,f){d="stackoverflow.com";g="/inet/tcp/0/"d"/80";print"GET "p" HTTP/1.1\nHost:"d"\n"|&g;close(g,"to");while(g|&getline)if($0~m){close(g,"from");split($0,a,r);return a[f]}}' <<< 764357
lego-stormtroopr 3,947

```
> 2 votes

---
Tags: code-golf, stack-exchange-api
---


# Question
Title: Find the optimal set of weights to add to a certain set of weights
In this challenge, you will recieve a comma-separated list of weights as input, such as

```
1,3,4,7,8,11

```

And you must output the smallest amount of weights that can add to that set. For example, the output for this set would be

```
1,3,7

```

Because you could represent all of those weights with just those three:

```
1     = 1
3     = 3
1+3   = 4
7     = 7
1+7   = 8
1+3+7 = 11

```

There may be more than one solution. For example, your solution for the input `1,2` could be `1,1` or `1,2`. As long as it finds the minimum amount of weights that can represent the input set, it is a valid solution.

Weights may not be used more than once. If you need to use one twice, you must output it twice. For example, `2,3` is not a valid solution for `2,3,5,7` because you can't use the `2` twice for `2+2+3=7`.

Input is guaranteed not to have duplicated numbers.

This is so shortest code by character count wins.

Network access is forbidden (so none of your "clever" `wget` solutions @JohannesKuhn *cough* *cough*) `;)`

Simpleest cases:

```
1,5,6,9,10,14,15               => 1,5,9
7,14,15,21,22,29               => 7,14,15
4,5,6,7,9,10,11,12,13,15,16,18 => 4,5,6,7
2,3,5,7                        => 2,2,3 or 2,3,7

```

And some trickier ones:

```
10,16,19,23,26,27,30,37,41,43,44,46,50,53,57,60,61,64,68,71,77,80,84,87
  => 3,7,16,27,34
20,30,36,50,56,63,66,73,79,86
  => 7,13,23,43
27,35,44,46,51,53,55,60,63,64,68,69,72,77,79,81,86,88,90,95,97,105,106,114,123,132
  => 9,18,26,37,42

```

# Answer
# Mathematica ~~80~~ 75

Update: See at bottom an update on Doorknob's challenging last test, added on Nov.5

---

This passes all but the last test. However, it does **not** attempt to use a digit more than once. And it only searches from solutions that are subsets of the larger data set.

The function generates all of the subsets of the input data set and then tests which subsets can be used to construct the complete set. After the viable subsets are found, it chooses the smallest sets.

```
s=Subsets
f@i_:=GatherBy[Select[s@i,Complement[i, Total /@ s@#]=={}&],Length]〚1〛

```

**Tests**

```
f[{1, 3, 4, 7, 8, 11}]

```

> {{1, 3, 7}}

---

```
f[{1, 5, 6, 9, 10, 14, 15}]

```

> {{1, 5, 9}}

---

```
f[{7, 14, 15, 21, 22, 29}]

```

> {{7, 14, 15}}

---

```
f[{4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 18}]

```

> {{4, 5, 6, 7}}

---

```
f[{2, 3, 5, 7}]

```

> {{2, 3, 5}, {2, 3, 7}}

---

## Update

Below I'll provide an initial analysis that may help get started toward a solution.

The data:

```
data = {10, 16, 19, 23, 26, 27, 30, 37, 41, 43, 44, 46, 50, 53, 57, 60, 61, 64, 68, 71, 77, 80, 84, 87};

```

Differently from the earlier approach, we want to consider, in the solution set, numbers that do NOT appear in the data set.

The approach makes use of absolute differences between pairs of numbers in the data set.

```
g[d_] := DeleteCases[Reverse@SortBy[Tally[Union[Sort /@ Tuples[d, {2}]] /. {a_, b_} :> Abs[a - b]], Last], {0, _}]

```

Let's look at the number of times each difference appears; we'll only grab the first 8 cases, starting from the most common difference\].

```
g[data][[1;;8]]

```

> {{7, 14}, {27, 13}, {34, 12}, {3, 11}, {20, 10}, {16, 10}, {4, 10}, {11, 9}}

14 pairs differed by 7; 13 pairs differed by 27, and so on.

Now let's test subsets starting with {difference1},{difference1, difference2}, and so on, until we can hopefully account for all the original elements in the data set.

`h` reveals those numbers from the original set that cannot be constructed by composing sums from the subset.

```
h[t_] := Complement[data, Total /@ Subsets@t]

```

By the fifth try, there are still 10 elements that cannot be formed from {7, 27, 34, 3, 20}:

```
h[{7, 27, 34, 3, 20}]

```

> {16, 19, 26, 43, 46, 53, 60, 77, 80, 87}

But on the next try, all numbers of the data set are accounted for:

```
h[{7, 27, 34, 3, 20, 16}]

```

> {}

This is still not as economical as {3,7,16,27,34}, but it's close.

---

There are still some additional things to take into account.

1. If 1 is in the data set, it will be required in the solution set.
2. There may well be some "loners" in the original set that cannot be composed from the most common differences. These would need to be included apart from the difference tests.

These are more issues than I can handle at the moment. But I hope it sheds some light on this very interesting challenge.
> 3 votes

# Answer
Ruby 289

This is a straight enumeration, so it will obtain minimal solutions, but it may take years--possibly light years--to solve some problems. All the "simplest cases" solve in at most a few seconds (though I got 7,8,14 and 1,2,4 for the 3rd and 5th cases, respectively). Tricky #2 solved in about 3 hours, but the other two are just too big for enumeration, at least for the way I've gone about it.

An array of size `n` that generates the given array by summing subsets of its elements is of minimal size if it can be shown that there is no array of size `< n` that does that. I can see no other way to prove optimality, so I start the enumeration with subsets of size `m`, where `m` is a known lower bound, and then increase the size to `m+1` after having enumerated subsets of size `m` and shown they none of those "span" the given array, and so on, until I find an optimum. Of course, if I have enumerated all subsets up to size n, I could use a heuristic for size n+1, so that if I found a spanning array of that size, I would know it is optimal. Can anyone suggest an alternative way to prove a solution is optimal in the general case?

I've included a few optional checks to eliminate some combinations early on. Removing those checks would save 87 characters. They are as follows (`a` is the given array):

* an array of size `n` can generate at most `2^n-1` distinct positive numbers; hence, `2^n-1 >= a.size`, or `n >= log2(a.size).ceil` (the "lower bound" I referred to above).
* a candidate generating array `b` of size `n` can be ruled out if:
    + `b.min > a.min`
    + `sum of elements of b < a.max` or
    + `b.max < v`, where `v = a.max.to_f/n+(n-1).to_f/2.ceil` (`to_f` being conversion to float).

The last of these, which is checked first, implements

```
sum of elements of b <= sum(b.max-n+1..b.max) < a.max

```

Note `v` is constant for all generator arrays of size `n`.

I've also made use of @cardboard\_box's very helful observation that there is no need to consider duplicates in the generating array.

In my code,

```
(1..a.max).to_a.combination(n)

```

generates all combinations of the numbers 1 to `a.max`, taken `n` at a time (where `a.max = a.last = a[-1]`). For each combination `b`:

```
(1...2**n).each{|j|h[b.zip(j.to_s(2).rjust(n,?0).split('')).reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0}

```

fills a hash `h` with all numbers that are sums over non-empty subsets of `b`. The hash keys are those numbers; the values are arbitrary. (I chose to set the latter to zero.)

```
a.all?{|e|h[e]}}

```

checks whether every element of the given array `a` is a key in the hash (`h[e] != nil`, or just `h[e]`).

Suppose

```
n = 3 and b=[2,5,7].

```

Then we iterate over the range:

```
(1...2**8) = (1...8) # 1,2,..,7

```

The binary representation of each number in this range is used to stab out the elements of `b` to sum. For `j = 3` (`j` being the range index),

```
3.to_s(2)                  # =>  "11"
"11".rjust(3,?0)           # => "011"
"011".split('')            # => ["0","1","1"]
[2,5,7].zip(["1","0","1"]) # => [[2,"0"],[5,"1"],[7,"1"]]
[[2,"0"],[5,"1"],[7,"1"]].reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0 # => t = 0+5+7 = 12

```

The code:

```
x=a[-1]
n=Math.log2(a.size).ceil
loop do
v=(1.0*x/n+(n-1)/2.0).ceil
(1..x).to_a.combination(n).each{|b|
next if b[-1]<v||b[0]>a[0]||b.reduce(&:+)<x
h={}
(1...2**n).each{|j|h[b.zip(j.to_s(2).rjust(n,?0).split('')).reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0}
(p b;exit)if a.all?{|e|h[e]}}
n+=1
end

```
> 0 votes

---
Tags: code-golf
---


# Question
Title: Enumerate the primes using only unary arithmetic
Write a program which prints the sequence of prime numbers. The shortest solution wins!

All numbers must have a unary representation (not just in the output, but throughout the entire program). This could be a string of 1s, a list of 1s, Peano-style objects, etc.

No particular output format is required, as long as numbers are recognizable. `111`, `[1, 1, 1]`, and `S(S(S(0)))` are all acceptable representations of `3`, for example.

Examples of permissible operations:

* Appending or prepending a constant value to a string/list
* Deleting a constant number of elements from a string/list
* Comparing something with a constant, such as `"11"`
* Calling `is_empty` on a string/list

Examples of what's not allowed:

* Any operations on non-unary integers or floats, such as `+`, `%`, `==` or `<`
* Built-in functions which operate on multiple strings/lists, like `+` or `==`
* Importing or downloading a library which does unary arithmetic ;-)

Sample programs

# Answer
> 4 votes
## Haskell, 212 135 130 111 104 characters

```
x⊡[1]=print x>>p x
x⊡s@(_:r)=s∇x where[]∇[]=p x;_∇[]=x⊡r;[]∇y=s∇y;(_:t)∇(_:y)=t∇y
p x=(1:x)⊡x
main=p[1]

```

The sieve was fun to implement, but simple exhaustive remainder checking is smaller. Strictly adheres to the terms. Unary numbers are represented as lists of 1.

First ten primes:

```
& runhaskell 13159-UnaryPrimes.hs | head
[1,1]
[1,1,1]
[1,1,1,1,1]
[1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

```

No library functions are used at all in the computation. In fact, the only library function used is `print`, which you can't get away from since you need some library function to output.

# Answer
> 4 votes
## C, 220 chars

```
o(void**n){putchar(n?33:10);n&&o(*n);}
d(void**a,void**b,void**c){return a?d(*a,b,c?*c:*b):c;}
q(void**a,void**b){return a?q(*a,*b):b;}
p(a,s){return!q(&s,a)||d(a,&s,0)&&p(a,&s);}
z;
e(n){p(&n,&z)&&o(&n);e(&n);}
main(){e(&z);}

```

Explanations:

1. Numbers are represented as linked lists. `NULL` is 0, a pointer to `N` is `N+1`.
2. `e` enumerates numbers by calling itself with `&n`, i.e. with `n+1`. It uses `p` to test for primality and `o` to print.
3. `p(a,s)` tests if `a` is prime, checking divisors starting from `s`.
4. `q(a,b)` returns false if the numbers are equal. It only works for `a<=b`.
5. `d(a,b,0)` returns false if `b` divides `a`. The 3rd parameter is for recursion.
6. `o(n)` prints `n` exclamation marks, followed by a newline.

# Answer
> 3 votes
## Perl 39 bytes

```
$_.=1while/^(11+)\1+$/||print$_||=11,$/

```

Interestingly enough, a well-known Perl primality test actually *relies* on unary logic.

# Answer
> 2 votes
# Mathematica, 81 chars

```
a=s@s@0;b={};While[1<2,Print@a;b~AppendTo~a;While[Or@@((a//.#:>0)==0&/@b),a=s@a]]

```

### Output:

> s\[s\[0\]\]
> s\[s\[s\[0\]\]\]
> s\[s\[s\[s\[s\[0\]\]\]\]\]
> s\[s\[s\[s\[s\[s\[s\[0\]\]\]\]\]\]\]
> s\[s\[s\[s\[s\[s\[s\[s\[s\[s\[s\[0\]\]\]\]\]\]\]\]\]\]\]
> ......

### Explanation:

Numbers are represented as Peano numbers. For example, `s[s[0]]` means `2`. I use suffix notation in my code. `s@s@0` is just short for `s[s[0]]`.

`a//.#:>0` repeatedly replace the pattern `#` in `a` with `0`. Both `a` and `#` in this expression are Peano numbers. In fact, it is equivalent to `a mod #`. For example, `s[s[s[0]]]]]//.s[s[0]]:>0` returns `s[0]`. So `(a//.#:>0)==0` if and only if `a` is divisible by `#`.

# Answer
> -1 votes
## Action Script 3 | Many bytes

```
var endOfTheWorld:Object = new Object();
var timeToEndOfTheWorld:Number = 1;

while(!endOfTheWorld){
    var busted:boolean = false;
    timeToEndOfTheWorld++;

    for (var k:Object in endOfTheWorld) {
        if(timeToEndOfTheWorld % Number(k) == 0){
            busted = true;
            break;
        }
    }
    if(busted){
        continue;
    }

    timeToEndOfTheWorld[timeToEndOfTheWorld] = timeToEndOfTheWorld;
    trace(timeToEndOfTheWorld);
}

```

**P.S** *If you think I got wrong with the time to end of the world, then prove it ;)*

---
Tags: code-golf, primes
---


title: Code Golf Bingo!

text:
# Question
Title: Code Golf Bingo!
You are given a Bingo board and a list of calls. You must print BINGO! as soon as your board wins the game.

Bingo boards look like this:

They will be specified like this:

```
14 29 38 52 74
4 18 33 46 62
7 16 * 60 71
9 27 44 51 67
12 23 35 47 73

```

Immediately following the board will be calls, like this:

```
B7
I29
G60
G51
O71
I23
I16
N38

```

You must echo the calls out to standard output until just after the call that makes you win (get a row, column, or 5-long diagonal all filled), then print `BINGO!`.

For the above example, print:

```
B7
I29
G60
G51
O71
I23
I16
BINGO!

```

**Rules**

Standard code-golf rules, shortest code wins.

**Details**

There will always be enough calls to guarantee you a Bingo. There will be no duplicate numbers on the board, and no duplicate calls. Boards will always have correctly matched numbers and letters (the `B` column contains only 1-15, the `I` column contains only 16-30, and so on), as will calls. The one and only free space will always be in the middle, marked with `*` instead of a number. Consuming and discarding calls from standard input after the winning call is allowed, but not required.

Make your own test cases!

# Answer
## Perl, 122 120 char

```
$b=join'. .
',map~~<>,0..4;while(<>){/(\d+)/;$b=~s/\b$1\b/*/;print;
$b=~/(\*\s(\S+\s){$_}){4}\*/&&die"BINGO!
"for 0..7}

```

Build the card in `$b` with two additional junky columns. Replace the numbers that are called on the card with `*` and print the called number. Then the last regular expression will evaluate to true when there are 5 regularly spaced `*`s on the board.
> 3 votes

# Answer
## Ruby 1.9 (194, 130)

This probably isn't the most sensible way to check for empty columns, but it was the first thing I thought to try! In particular, that `#transpose` costs a lot.

Either a blank line between the board and the numbers or fixed width fields when declaring the board would save a lot of characters. I couldn't think of a really nice way to read exactly 5 lines.

```
b=(R=0..4).map{gets}.join.scan /\d+|\*/
loop{gets
puts$_
~/\d+/
(e=b.index$&)&&b[e]=?*
R.map{|y|$><<:BINGO!&&exit if R.map{|x|[b[5*x+y],b[5*y+x],b[y<1?x*6:4*x+4]]}.transpose.any?{|a|a==[?*]*5}}}

```

**EDIT:** 130 character solution using the regular expression technique from mob's perl answer:

```
b=(0..4).map{gets}*'~ ~ '
loop{gets
puts$_
~/\d+/
b[/\b#$&\b/]=?*
7.times{|i|$><<:BINGO!&&exit if b=~/(\*\s(\S+\s){#{i}}){4}\*/m}}

```
> 4 votes

# Answer
## C# – 536

(OK, this is probably not the most suitable language for that, but anyway…)

```
using System;using System.Collections.Generic;using System.Linq;class C{static void Main(){var s=Enumerable.Range(1,12).Select(_=>new HashSet<string>()).ToList();var b=Enumerable.Range(1,5).Select(_=>Console.ReadLine().Split(' ')).ToList();int i;for(i=0;i<5;++i){for(int j=0;j<5;++j){s[i].Add(b[i][j]);s[i+5].Add(b[j][i]);}s[10].Add(b[i][i]);s[11].Add(b[4-i][i]);}while(i>0){var l=Console.ReadLine();Console.WriteLine(l);l=l.Substring(1);foreach(var x in s){x.Remove("*");x.Remove(l);if(x.Count==0){Console.WriteLine("BINGO!");i=0;}}}}}

```

Formatted and commented:

```
using System;
using System.Collections.Generic;
using System.Linq;

class C
{
    static void Main()
    {
        // all possible winnable five-item sets – any one of them need to be emptied to win
        var s = Enumerable.Range(1, 12).Select(_ => new HashSet<string>()).ToList();
        // read the board from input to a list of arrays of numbers
        var b = Enumerable.Range(1, 5).Select(_ => Console.ReadLine().Split(' ')).ToList();
        int i;
        // split the board into the winnable sets
        for (i = 0; i < 5; ++i)
        {
            for (int j = 0; j < 5; ++j)
            {
                // sets 0–4 represent rows
                s[i].Add(b[i][j]);
                // sets 5–9 represent columns
                s[i + 5].Add(b[j][i]);
            }
            // set 10 represent one diagonal
            s[10].Add(b[i][i]);
            // set 11 represent the other diagonal
            s[11].Add(b[4 - i][i]);
        }
        while (i > 0)
        {
            // read and echo another input
            var l = Console.ReadLine();
            Console.WriteLine(l);
            // ignore the initial letter – we are guaranteed it is correct, anyway
            l = l.Substring(1);
            // remove the number from all sets
            foreach (var x in s)
            {
                x.Remove(l);
                // also remove the center * (inside the loop just to shave off a few characters)
                x.Remove("*");
                // if any set became empty, we won!
                if (x.Count == 0)
                {
                    Console.WriteLine("BINGO!");
                    // ensure the loop will stop (might not be necessary per the rules, but anyway)
                    i = 0;
                }
            }
        }
    }
}

```
> 4 votes

# Answer
*Given the long, long, long overdue announcement of Rebol's impending release as open source software, I returned to my pet dialect to solve this Bingo problem. I may soon be able to distribute Rebmu as its own, teensy GPL package. :)*

---

## Rebmu 88 characters

In the compact notation:

```
rtZ5[GisGpcRaZisGaAPgPCaSB6zAPv'*]l5[AgL5[apGfAsk+A5]]hd+Gu[raGin-NTrM'*fisGv5]p"BINGO!"

```

The dialect uses a trick I call *mushing* which is explained on the Rebmu page. It's "legit" in the sense that it doesn't cheat the parser; this is valid Rebol...and can actually can be freely intermingled with ordinary code as well as (ahem) "long-form" Rebmu...which BTW would be 141 characters:

`[rt z 5 [g: is g pc r a z is g a ap g pc a sb 6 z ap v '*] l 5 [a: g l 5 [ap g f a sk+ a 5]] hd+ g u [ra g in- nt r m '* fis g v 5] p "BINGO!"]`

*(Given that I claim the compression is a trick that one can do without the help of automation or compilation, I actually develop the code in the mushed form. It's not difficult.)*

It's actually quite simple, nothing special--I'm sure other Rebol programmers could shave things off. Some commented source is on GitHub, but the main trick I use is to build all the possible solutions in a long series ("list", "array", what-have-you). I build the diagonal solutions during the input loop, as it takes five insertions at the head and five appends at the tail to make them...and there's already a five-iteration loop in progress.

The whole thing easily maps to Rebol code, and I haven't yet thrown any "matrix libraries" into Rebmu with transposition or other gimmicks that seem to come up often. Someday I will do that but for now I'm just trying to work relatively close to the medium of Rebol itself. Cryptic-looking things like:

```
 [g: is g pc r a z is g a ap g pc a sb 6 z ap v '*]

```

...are rather simple:

```
 [
     ; assign the series pointer "g" to the result of inserting
     ; the z'th element picked out of reading in some series
     ; from input that was stored in "a"...this pokes an element
     ; for the forward diagonal near the front of g
     g: insert g (pick (readin-mu a) z)

     ; insert the read-in series "a" from above into "g" as well,
     ; but *after* the forward diagonal elements we've added...
     insert g a

     ; for the reverse diagonal, subtract z from 6 and pick that
     ; (one-based) element out of the input that was stored in "a"
     ; so an element for the reverse diagonal is at the tail
     append g (pick a (subtract 6 z))

     ; so long as we are counting to 5 anyway, go ahead and add an
     ; asterisk to a series we will use called "v" to search for
     ; a fulfilled solution later
     append v '*
 ]

```

*Note: Parentheses added above for clarity. But Rebol programmers (like English speakers) generally eschew the application of extra structural callouts for indicating the grammar in communication...rather save them for other applications...*

Just as an added bonus to show how interesting this actually is, I'll throw in some mix of normal code to sum the board. The programming styles are actually...compatible:

```
rtZ5[GisGpcRaZisGaAPgPCaSB6zAPv'*]
temp-series: g
sum: 0
loop 5 * 5 [
    square: first temp-series
    if integer! == type? square [
        sum: sum + square
    ]
    temp-series: next temp-series
]
print ["Hey grandma, the board sum is" sum]
l5[AgL5[apGfAsk+A5]]hd+Gu[raGin-NTrM'*fisGv5]p"BINGO!"

```

That's valid Rebmu as well, and it will give you a nice board sum before playing Bingo with you. In the example given, it says `Hey grandma, the board sum is 912`. Which is probably right. But you get the point. :)
> 4 votes

# Answer
# Mathematica 250

Disclosure: I assumed that the input was given in lists which are far more natural to use for Mathematica. So,with `b` representing the board and `c` representing the calls,

```
b//Grid
c//Column

```

If the input were to be in strings, the code would grow by about 30 characters. (I'll later include that variation.)

**Code**

```
y = ReplacePart[ConstantArray[0, {5, 5}], {3, 3} -> 1]; d = Diagonal;
t := Tr[BitAnd @@@ Join[y, Transpose@y, {d@y}, {d[Reverse /@ y]}]] > 0;
r@i_ :=(y = ReplacePart[y, Position[x, ToExpression@StringDrop[i, 1]][[1]] -> 1];
Print@If[t, Column[{i, "BINGO!"}], i])
n = 1; While[! t, r@c[[n]]; n++]

```

> B7
>
> I29
>
> G60
>
> G51
>
> O71
>
> I23
>
> I16
>
> BINGO!
> 2 votes

# Answer
# Python 249

```
R=raw_input;F=B=[[[x,0][x=='*']for x in row]for row in[R().split()for i in'11111']];A=any
while all([all(map(A,B)),all(map(A,zip(*B))),A(F[::6]),A(F[4:24:4])]):c=R();print c;C=c[1:];B=[[[x,0][x==C]for x in row]for row in B];F=sum(B,[])
print'BINGO!'

```

### Usage:

```
$ ./bingo.py < bingo.txt
B7
I29
G60
G51
O71
I23
I16
BINGO!

```
> 2 votes

# Answer
## APL (82)

```
{(D≡(⍵∨⌽⍵)∧D←=/¨⍳⍴⍵)∨∨/(∧⌿⍵)∨∧/⍵:'BINGO!'⋄∇⍵∨B=⍎1↓⎕←⍞}0=B←↑{⍎(K,K)[⍞⍳⍨K←11↑⎕D]}¨⍳5

```
* `{`...`}¨⍳5`: do 5 times:
* `⍎(K,K)[⍞⍳⍨K←11↑⎕D]`: read a line () and map all characters that aren't digits or space to `0`, then evaluate the line.
* `B←↑`: turn it into a matrix (5x5 if the input was correct), and store in B.
* `{`...`}0=B`: the starting board has a 1 in the free space (0) and 0 in the other spaces.
* `(D≡(⍵∨⌽⍵)∧D←=/¨⍳⍴⍵)∨∨/(∧⌿⍵)∨∧/⍵`: if a line, a column, or a diagonal is filled:
* `'BINGO!'`: then output `BINGO`
* `∇⍵∨B=⍎1↓⎕←⍞`: otherwise, read a line (), echo it (`⎕←`), drop the first character (`1↓`), evaluate it to get a number (), see where it occurs on the board (`B=`), mark it (`⍵∨`), and try again ().
> 2 votes

# Answer
# K, 114

Given the board `b` and the calls `c`

```
b{-1@y;a:(5*!5)_@[,/x;&(,/x)~\:1_y;:;"*"];$[max{max@min'"*"=,/'x}@/:(a;a ./:/:+:'(r;)'(r;|:r:!5));'"BINGO!";];a}/c

```

.

```
k)b
"14" "29" "38" "52" "74"
,"4" "18" "33" "46" "62"
,"7" "16" ,"*" "60" "71"
,"9" "27" "44" "51" "67"
"12" "23" "35" "47" "73"
k)c
"B7"
"I29"
"G60"
"G51"
"O71"
"I23"
"I16"
"N38"
k)b{-1@y;a:(5*!5)_@[,/x;&(,/x)~\:1_y;:;"*"];$[max{max@min'"*"=,/'x}@/:(a;a ./:/:+:'(r;)'(r;|:r:!5));'"BINGO!";];a}/c
B7
I29
G60
G51
O71
I23
I16
'BINGO

```
> 0 votes

---
Tags: code-golf
---


title: Find the joker in deck of cards

text:
# Question
Title: Find the joker in deck of cards
You have a French deck of cards that **sorted** like this: 2 - 10, Princes, Queens, Kings, Aces.

The deck represented with array of numbers from 1 to 52(included)

Now the dealer is shuffling the deck 3 times and inserting a Joker in a random position of the deck.

The joker represented with the number 0

The idea of shuffling is slicing the array in random position and moving it to the front like in the next examples:

* 1,2,3,4,5,6,7,8,9,10 -\> 6,7,8,9,10,1,2,3,4,5 // Sliced at 6
* 1,2,3,4,5,6,7,8,9,10 -\> 8,9,10,1,2,3,4,5,6,7 // Sliced at 8

Find the joker position in the array. The challenge is doing this without iterating over the entire deck.

**Winning priority:**

* Best time performance
* Shortest code

# Answer
> 6 votes
# polyglot, constant time, 8 characters

```
52-a[52]

```

The trick is to realise what actually happens when you shuffle the array. Imagine the array as circular. Let us render the array starting at zero with the actual start/end signified with a bar:

```
0 1 2 3 4 5 6 7 8 9 |

```

Now, what actually happens when you shuffle the top three cards to the bottom and re-render:

```
7 8 9 0 1 2 3 4 5 6 |
0 1 2 3 4 5 6 | 7 8 9

```

Let's shuffle three more cards:

```
0 1 2 3 | 4 5 6 7 8 9

```

The only thing shuffles do is that they rotate the whole array, but don't change the ordering up to rotation.

So, if the array ends with a zero, we want to output the last index. The array has 53 elements, so the last index is 52.

If the array starts with a zero, it ends with its largest value. We want to output zero in this case.

Similarly, if the zero is `n` positions from the end, the last element of the array is `n`. Thus, the position of zero is the last position in the array, minus the value at the last position.

---
Tags: code-golf
---


# Question
Title: Convert 1 into any positive integer using only the operations *3 and /2
Any positive integer can be obtained by starting with **1** and applying a sequence of operations, each of which is either **"multiply by 3"** or **"divide by 2, discarding any remainder"**.

**Examples** (writing f for \*3 and g for /2):

`4 = 1 *3 *3 /2 = 1 ffg`
`6 = 1 ffggf = 1 fffgg`
`21 = 1 fffgfgfgggf`

Write a program with the following behavior:

**Input**: any positive integer, via stdin or hard-coded. (If hard-coded, the input numeral will be excluded from the program length.)
**Output**: a string of f's and g's such that `<input> = 1 <string>` (as in the examples). Such a string in reverse order is also acceptable. NB: The output contains only f's and g's, or is empty.

The winner is the entry with the fewest bytes of *program-plus-output* when 41 is the input.

# Answer
> 3 votes
### GolfScript, score 64 (43-2+23)

```
0{)1.$2base:s{{3*}{2/}if}/41=!}do;s{103^}%+

```

(41 is hardcoded, therefore -2 characters for the score). The output is

```
fffgffggffggffgggffgggg

```

which is 23 characters (without newline). By construction the code guarantees that it always returns (one of) the shortest representations.

# Answer
> 3 votes
We're getting dirty, friends!

**JAVA ~~210 207~~ 199 characters**

```
public class C{public static void main(String[] a){int i=41;String s="";while(i>1){if(i%3<1){s+="f";i/=3;}else if(i%3<2){s+="g";i+=i+1;}else{s+="g";i+=i+(Math.random()+0.5);}}System.out.println(s);}}

```

non-golfed:

```
public class C {

    public static void main(String[] a) {

        int i = 41;
        String s = "";
        while (i > 1) {
            if (i % 3 == 0) {
                s += "f";
                i /= 3;
            } else {
                if (i % 3 == 1) {
                    s += "g";
                    i += i + 1;
                } else {
                    s += "g";
                    i += i + (Math.random() + 0.5);
                }
            }
        }
        System.out.println(s);
    }
}

```

output : depending on the faith of the old gods, the shortest i had was 30. Note that the output must be read from the right.

**234**

```
1 ggfgfgfgfggfggfgffgfggggfgffgfggfgfggggfgffgfggfgfggfgfggfgfgggggfffgfggfgfggfgfgggffgggggfffgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggfgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggggggggggggfgfgfggggfgfgfggfffgfgfggffgfgfggfgfggggffgfgfffff

```

**108**

```
1 gggffgfgfggggggfggggfgffggggfgfgfgfgfgffgggfgggggfggfffggfgfffffgggffggfgfgggffggfgfgggffggggggfgfgffgfgfff

```

*edit* **45**

```
1 ggfgfgfgfgggfggfffgfggfgfgggggggffgffgfgfff

```

**points : ~~318~~ 199+30 = 229**

**edit1** (2\*i+1)%3==0 --\> (2\*i) % 3 ==1

Nota Bene if you use Java 6 and not Java 7 while golfing, you can use

```
public class NoMain {
    static {
        //some code
        System.exit(1);
    }
}

```

39 characters structure instead of a standard structure which is 53 characters long.

# Answer
> 3 votes
## Python, score 124 (90-2+36)

```
x=41;m=f=g=0
while(3**f!=x)*(m!=x):
 f+=1;m=3**f;g=0
 while m>x:m/=2;g+=1
print'f'*f+'g'*g

```

90 chars of code (newlines as 1 each) - 2 for hard-coded input numeral + 36 chars of output

Output:

```
ffffffffffffffffgggggggggggggggggggg

```

# Answer
> 3 votes
## Python, score 121 (87 - 2 + 36)

```
t=bin(41)
l,n,f=len(t),1,0
while bin(n)[:l]!=t:f+=1;n*=3
print(len(bin(n))-l)*'g'+f*'f'

```

# Answer
> 1 votes
## Perl, score 89 (63 - 2 + 28)

```
$_=41;$_=${$g=$_%3||$_==21?g:f}?$_*2+$_%3%2:$_/3while$_>print$g

```

***Conjecture:*** If the naive approach described in my original solution below ever reaches a cycle, that cycle will be *\[21, 7, 15, 5, 10, 21, ...\]*. As there are no counter-examples for *1 ≤ n ≤ 106*, this seems likely to be true. To prove this, it would suffice to show that this is the only cycle which *can* exist, which I may or may not do at a later point in time.

The above solution avoids the cycle immediately, instead of guessing (wrongly), and avoiding it the second time through.

Output (28 bytes):

```
ggfgfgfgfggfggfgfgfggfgfgfff

```

---

## Perl, score 100 (69 - 2 + 33)

```
$_=41;1while$_>print$s{$_=$$g?$_*2+$_%3%2:$_/3}=$g=$_%3||$s{$_/3}?g:f

```

Using a guess-and-check approach. The string is constructed using inverse operations (converting the value to *1*, instead of the other way around), and the string becomes mirrored accordingly, which is allowed by the problem specification.

Whenever a non-multiple of three is encountered, it will be multiplied by two, adding one if the result would then be a multiple of three. When a multiple of three is encountered, it will be divided by three... unless this value has previously been encountered, indicating a cycle, hence guess-and-check.

Output (33 bytes):

```
ggfgfgfgfggfggfgffgfgggfggfgfgfff

```

# Answer
> 1 votes
# J, score 103 (82-2+23)

\*Note: I named my verbs `f` and `g`, not to be confused with output strings `f` and `g`.

Hard-coded:

```
f=:3 :'s=.1 for_a.y do.s=.((<.&-:)`(*&3)@.a)s end.'
'gf'{~#:(>:^:(41&~:@f@#:)^:_)1

```

General functions:

```
f=:3 :'s=.1 for_a.y do.s=.((<.&-:)`(*&3)@.a)s end.'
g=:3 :'''gf''{~#:(>:^:(y&~:@f@#:)^:_)1'

```

Did away with operating on blocks of binary numbers, which was the most important change as far as compacting `g`. Renamed variables and removed some whitespace for the heck of it, but everything's still functionally the same. (Usage: `g 41`)

### J, score 197 (174+23)

```
f =: 3 : 0
acc =. 1
for_a. y do. acc =. ((*&3)`(<.&-:)@.a) acc end.
)

g =: 3 : 0
f2 =: f"1 f.
l =. 0$0
i =. 1
while. 0=$(l=.(#~(y&=@:f2))#:i.2^i) do. i=.>:i end.
'fg'{~{.l
)

```

Output: `ffffffffggggggggfgffggg`

`f` converts a list of booleans into number, using 0s as `*3` and 1s as `/2` (and `floor`). `#:i.2^i` creates a rank 2 array containing all the rank 1 boolean arrays of length `i`.

---
Tags: code-challenge, math
---