# Question
Title: Write a program that always prints N when it is shifted N times up the ASCII alphabet
Write a program using only printable ASCII characters that takes no input. For reference, here are the 95 printable ASCII characters in order:

```
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

```

When your program is run it should print `0` (plus an optional trailing newline) to stdout, then terminate normally.

When each character in your program is replaced by the character N spaces to its right in printable ASCII, looping around from `~` to space, the resulting printable ASCII string will *ideally* be a program runnable in the same language that takes no input and outputs N (plus an optional trailing newline) to stdout, then terminates normally, for N = 1 to 94.

For example, if your original program was

```
@Cat~(88 !)

```

running it should output `0` and shifting all the characters up the printable ASCII scale by one

```
ADbu )99!"*

```

should result in another program that outputs `1`. Doing so again will ideally result in another program that outputs `2`

```
BEcv!*::"#+

```

and so on with 3 and 4, etc. up to the point of shifting 94 times

```
?B`s}'77~ (

```

which ideally is a program that outputs `94`.

The relief is that this is only the ideal behavior. Your program and its 94 derivatives do not all need to work, but the more that consecutively do from the start the better. (Programs that do not work may have any behavior whatsoever.)

# Scoring

Your score is the number of *consecutive* programs starting from the original (the one that outputs `0`) that do work, i.e. correctly output their corresponding N. The answer with the highest score (a maximum of 95) wins. If there's a tie then the program with the shortest length in bytes wins.

For example, if `@Cat~(88 !)` output `0` and `ADbu )99!"*` output `1` but `BEcv!*::"#+` errored, then your score would be 2. It's 2 even if `?B`s}'77~ (` accurately outputs `94` and even if all the programs for N = 30 to 40 worked. Only the *consecutive* number of working programs, starting at zero, are counted.

# Notes

* To combat potential contention and loopholes, competing answers must output their numbers in decimal with no leading zeroes or signs or decimal points (i.e. plain `0` `1` `2` ... `94`).
* Languages that use different bases or number formats are allowed but are not eligible to win.
* The presence of an optional trailing newline does not need to be consistent across programs.
* Functions and REPL commands are not allowed, only full programs.

# Answer
> 30 votes
## Ook!, 95 programs, ~~19992~~ 14066 bytes

```
Ook!Ook!Ook!Ook?Ook.Ook?Ook.Ook.Ook?Ook.Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook?Ook!Ook.Ook?Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook.NJ_.NJ_.NJ_.NJ}.NJl.NJ}.NJl.NJl.NJ}.NJl.NJ_.NJ_.NJ_.NJ_.NJ_.NJ_.NJ_.NJ_.NJ_.NJ_.NJ}.NJ_.NJl.NJ}.NJ_.NJl.NJ_.NJl-)>l-)>l-)>l-)\l-)Kl-)\l-)Kl-)Kl-)\l-)Kl-)>l-)>l-)>l-)>l-)>l-)>l-)>l-)>l-)>l-)>l-)\l-)>l-)Kl-)\l-)Kl-)Kl-)Kl-)Kl-)Kl-)Kl-)>l-)Kl-)>l-)Kkg|Kkg|Kkg|Kkg;Kkg*Kkg;Kkg*Kkg*Kkg;Kkg*Kkg|Kkg|Kkg|Kkg|Kkg|Kkg|Kkg|Kkg|Kkg|Kkg|Kkg;Kkg|Kkg*Kkg;Kkg*Kkg*Kkg|Kkg*JF[*JF[*JF[*JFy*JFh*JFy*JFh*JFh*JFy*JFh*JF[*JF[*JF[*JF[*JF[*JF[*JF[*JF[*JF[*JF[*JFy*JF[*JFh*JFy*JF[*JFh*JFh*JFh*JFh*JFh*JFh*JFh*JFh*JFh*JF[*JFh)%Gh)%Xh)%:h)%:h)%:h)%Xh)%Gh)%Gh)%Gh)%Gh)%Gh)%Xh)%Gh)%Gh)%:h)%Xh)%Gh)%Gh)%Xh)%Gh)%Xh)%:h)%Gh)%Xh)%Xh)%:h)%Gh)%Xh)%:h)%:h)%:h)%Gh)%:h)%:h)%:h)%:h)%:h)%:h)%:h)%:h)%:h)%:h)%:h)%:h)%:h)%:h)%:h)%Ggc&Ggc7GgcxGgcxGgcxGgc7Ggc&Ggc&Ggc&Ggc&Ggc&Ggc7Ggc&Ggc&GgcxGgc7Ggc&Ggc&Ggc7Ggc&Ggc7GgcxGgc&Ggc7Ggc7GgcxGgc&Ggc7GgcxGgc&FBW&FBW&FBW&FBu&FBd&FBu&FBd&FBd&FBu&FBd&FBW&FBW&FBW&FBW&FBW&FBW&FBW&FBW&FBW&FBW&FBu&FBW&FBd&FBu&FBd&FBd&FBW&FBd&FBW&FBW&FBW&FBW&FBW&FBW&FBW&FBd%!Cd%!Td%!6d%!6d%!6d%!Td%!Cd%!Cd%!Cd%!Cd%!Cd%!Td%!Cd%!Cd%!6d%!Td%!Cd%!Cd%!Td%!Cd%!Td%!6d%!Cd%!Td%!Td%!6d%!Cd%!Td%!6d%!6d%!6d%!Cd%!6d%!6d%!6d%!6d%!6d%!6d%!6d%!Cc_tCc_tCc_tCc_3Cc_"Cc_3Cc_"Cc_"Cc_3Cc_"Cc_tCc_tCc_tCc_tCc_tCc_tCc_tCc_tCc_tCc_tCc_3Cc_tCc_"Cc_3Cc_tCc_tCc_tCc_tCc_tCc_"Cc_"Cc_"Cc_tCc_"B>S"B>S"B>S"B>q"B>`"B>q"B>`"B>`"B>q"B>`"B>S"B>S"B>S"B>S"B>S"B>S"B>S"B>S"B>S"B>S"B>q"B>S"B>`"B>q"B>`"B>`"B>S"B>`"B>`"B>`"B>S"B>`!|?`!|P`!|2`!|2`!|2`!|P`!|?`!|?`!|?`!|?`!|?`!|P`!|?`!|?`!|2`!|P`!|?`!|?`!|P`!|?`!|P`!|2`!|?`!|P`!|P`!|2`!|?`!|P`!|2`!|2`!|2`!|?`!|?`!|?`!|2`!|?_[p?_[p?_[p?_[/?_[}?_[/?_[}?_[}?_[/?_[}?_[p?_[p?_[p?_[p?_[p?_[p?_[p?_[p?_[p?_[p?_[/?_[p?_[}?_[/?_[p?_[p?_[p?_[p?_[p?_[}?_[}?_[}?_[}?_[}?_[}?_[}?_[}?_[}?_[}?_[}?_[p?_[}>:O}>:O}>:O}>:m}>:\}>:m}>:\}>:\}>:m}>:\}>:O}>:O}>:O}>:O}>:O}>:O}>:O}>:O}>:O}>:O}>:m}>:O}>:\}>:m}>:\}>:\}>:O}>:\}>:\}>:\}>:\}>:\}>:\}>:\}>:\}>:\}>:\}>:\}>:O}>:\|x;\|xL\|x.\|x.\|x.\|xL\|x;\|x;\|x;\|x;\|x;\|xL\|x;\|x;\|x.\|xL\|x;\|x;\|xL\|x;\|xL\|x.\|x;\|xL\|xL\|x.\|x;\|xL\|x.\|x;\|x.\|x.\|x.\|x.\|x.\|x.\|x.\|x.\|x.\|x.\|x.\|x.\|x.\|x;[Wl;[Wl;[Wl;[W+;[Wy;[W+;[Wy;[Wy;[W+;[Wy;[Wl;[Wl;[Wl;[Wl;[Wl;[Wl;[Wl;[Wl;[Wl;[Wl;[W+;[Wl;[Wy;[W+;[Wl;[Wl;[Wl;[Wy;[Wl;[Wl;[Wl;[Wl;[Wl;[Wy:6Ky:6Ky:6Ky:6iy:6Xy:6iy:6Xy:6Xy:6iy:6Xy:6Ky:6Ky:6Ky:6Ky:6Ky:6Ky:6Ky:6Ky:6Ky:6Ky:6iy:6Ky:6Xy:6iy:6Xy:6Xy:6Xy:6Xy:6Ky:6Xy:6Ky:6Ky:6Ky:6Ky:6Ky:6Xxt7XxtHXxt*Xxt*Xxt*XxtHXxt7Xxt7Xxt7Xxt7Xxt7XxtHXxt7Xxt7Xxt*XxtHXxt7Xxt7XxtHXxt7XxtHXxt*Xxt7XxtHXxtHXxt*Xxt7XxtHXxt*Xxt7Xxt*Xxt*Xxt*Xxt*Xxt*Xxt7WSh7WSh7WSh7WS'7WSu7WS'7WSu7WSu7WS'7WSu7WSh7WSh7WSh7WSh7WSh7WSh7WSh7WSh7WSh7WSh7WS'7WSh7WSu7WS'7WSh7WSh7WSh7WSu7WSu7WSu7WSu7WSu7WSh7WSu62Gu62Gu62Gu62eu62Tu62eu62Tu62Tu62eu62Tu62Gu62Gu62Gu62Gu62Gu62Gu62Gu62Gu62Gu62Gu62eu62Gu62Tu62eu62Tu62Tu62Tu62Tu62Gu62Tu62Tu62Tu62Tu62Tu62Gu62Ttp3TtpDTtp&Ttp&Ttp&TtpDTtp3Ttp3Ttp3Ttp3Ttp3TtpDTtp3Ttp3Ttp&TtpDTtp3Ttp3TtpDTtp3TtpDTtp&Ttp3TtpDTtpDTtp&Ttp3TtpDTtp3Ttp3Ttp&Ttp3Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp&Ttp3SOd3SOd3SOd3SO#3SOq3SO#3SOq3SOq3SO#3SOq3SOd3SOd3SOd3SOd3SOd3SOd3SOd3SOd3SOd3SOd3SO#3SOd3SOq3SO#3SOd3SOd3SOd3SOq3SOq3SOq3SOq3SOq3SOq3SOq3SOq3SOq3SOq3SOq3SOq3SOq3SOd3SOq2.Cq2.Cq2.Cq2.aq2.Pq2.aq2.Pq2.Pq2.aq2.Pq2.Cq2.Cq2.Cq2.Cq2.Cq2.Cq2.Cq2.Cq2.Cq2.Cq2.aq2.Cq2.Pq2.aq2.Pq2.Pq2.Pq2.Pq2.Pq2.Pq2.Cq2.Pq2.Cq2.Cq2.Cq2.Cq2.Cq2.Cq2.Cq2.Cq2.Cq2.Cq2.Cq2.Ppl/Ppl@Ppl"Ppl"Ppl"Ppl@Ppl/Ppl/Ppl/Ppl/Ppl/Ppl@Ppl/Ppl/Ppl"Ppl@Ppl/Ppl/Ppl@Ppl/Ppl@Ppl"Ppl/Ppl@Ppl@Ppl"Ppl/Ppl@Ppl/Ppl/Ppl"Ppl/Ppl"Ppl"Ppl"Ppl"Ppl"Ppl"Ppl"Ppl"Ppl"Ppl"Ppl"Ppl/OK`/OK`/OK`/OK~/OKm/OK~/OKm/OKm/OK~/OKm/OK`/OK`/OK`/OK`/OK`/OK`/OK`/OK`/OK`/OK`/OK~/OK`/OKm/OK~/OK`/OKm/OK`/OK`/OK`/OKm.*?m.*?m.*?m.*]m.*Lm.*]m.*Lm.*Lm.*]m.*Lm.*?m.*?m.*?m.*?m.*?m.*?m.*?m.*?m.*?m.*?m.*]m.*?m.*Lm.*]m.*Lm.*Lm.*Lm.*Lm.*Lm.*Lm.*?m.*Lm.*?m.*?m.*?m.*Llh}Llh}Llh}Llh<Llh+Llh<Llh+Llh+Llh<Llh+Llh}Llh}Llh}Llh}Llh}Llh}Llh}Llh}Llh}Llh}Llh<Llh}Llh+Llh<Llh}Llh+KG\+KG\+KG\+KGz+KGi+KGz+KGi+KGi+KGz+KGi+KG\+KG\+KG\+KG\+KG\+KG\+KG\+KG\+KG\+KG\+KGz+KG\+KGi+KGz+KG\+KGi+KGi+KGi+KGi+KGi+KGi+KGi+KG\+KGi*&;i*&;i*&;i*&Yi*&Hi*&Yi*&Hi*&Hi*&Yi*&Hi*&;i*&;i*&;i*&;i*&;i*&;i*&;i*&;i*&;i*&;i*&Yi*&;i*&Hi*&Yi*&Hi*&Hi*&Hi*&Hi*&Hi*&Hi*&;i*&Hi*&Hi*&Hi*&Hi*&Hi*&Hi*&Hi*&;i*&Hhd'Hhd8HhdyHhdyHhdyHhd8Hhd'Hhd'Hhd'Hhd'Hhd'Hhd8Hhd'Hhd'HhdyHhd8Hhd'Hhd'Hhd8Hhd'Hhd8HhdyHhd'Hhd8Hhd8HhdyHhd'Hhd8HhdyHhdyHhdyHhd'GCX'GCX'GCX'GCv'GCe'GCv'GCe'GCe'GCv'GCe'GCX'GCX'GCX'GCX'GCX'GCX'GCX'GCX'GCX'GCX'GCv'GCX'GCe'GCv'GCe'GCe'GCX'GCe'GCX'GCX'GCX'GCX'GCX'GCX'GCX'GCX'GCX'GCe&"De&"Ue&"7e&"7e&"7e&"Ue&"De&"De&"De&"De&"De&"Ue&"De&"De&"7e&"Ue&"De&"De&"Ue&"De&"Ue&"7e&"De&"Ue&"Ue&"7e&"De&"Ue&"7e&"7e&"7e&"De&"7e&"7e&"7e&"7e&"7e&"7e&"7e&"7e&"7e&"Dd`uDd`uDd`uDd`4Dd`#Dd`4Dd`#Dd`#Dd`4Dd`#Dd`uDd`uDd`uDd`uDd`uDd`uDd`uDd`uDd`uDd`uDd`4Dd`uDd`#Dd`4Dd`uDd`uDd`uDd`uDd`uDd`#Dd`uDd`#C?T#C?T#C?T#C?r#C?a#C?r#C?a#C?a#C?r#C?a#C?T#C?T#C?T#C?T#C?T#C?T#C?T#C?T#C?T#C?T#C?r#C?T#C?a#C?r#C?a#C?a#C?T#C?a#C?T#C?a"}@a"}Qa"}3a"}3a"}3a"}Qa"}@a"}@a"}@a"}@a"}@a"}Qa"}@a"}@a"}3a"}Qa"}@a"}@a"}Qa"}@a"}Qa"}3a"}@a"}Qa"}Qa"}3a"}@a"}Qa"}3a"}3a"}3a"}@a"}3a"}@`\q@`\q@`\q@`\0@`\~@`\0@`\~@`\~@`\0@`\~@`\q@`\q@`\q@`\q@`\q@`\q@`\q@`\q@`\q@`\q@`\0@`\q@`\~@`\0@`\q@`\q@`\q@`\q@`\q@`\~@`\~@`\~@`\~@`\~@`\~@`\~@`\~@`\~@`\q@`\~?;P~?;P~?;P~?;n~?;]~?;n~?;]~?;]~?;n~?;]~?;P~?;P~?;P~?;P~?;P~?;P~?;P~?;P~?;P~?;P~?;n~?;P~?;]~?;n~?;]~?;]~?;P~?;]~?;]~?;]~?;]~?;]~?;]~?;]~?;]~?;]~?;P~?;]}y<]}yM]}y/]}y/]}y/]}yM]}y<]}y<]}y<]}y<]}y<]}yM]}y<]}y<]}y/]}yM]}y<]}y<]}yM]}y<]}yM]}y/]}y<]}yM]}yM]}y/]}y<]}yM]}y/]}y<]}y/]}y/]}y/]}y/]}y/]}y/]}y/]}y/]}y/]}y/]}y/]}y/]}y/]}y/]}y/]}y<\Xm<\Xm<\Xm<\X,<\Xz<\X,<\Xz<\Xz<\X,<\Xz<\Xm<\Xm<\Xm<\Xm<\Xm<\Xm<\Xm<\Xm<\Xm<\Xm<\X,<\Xm<\Xz<\X,<\Xm<\Xm<\Xm<\Xm<\Xm<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xz<\Xm<\Xz;7Lz;7Lz;7Lz;7jz;7Yz;7jz;7Yz;7Yz;7jz;7Yz;7Lz;7Lz;7Lz;7Lz;7Lz;7Lz;7Lz;7Lz;7Lz;7Lz;7jz;7Lz;7Yz;7jz;7Yz;7Yz;7Yz;7Yz;7Lz;7Yz;7Lz;7Lz;7Lz;7Lz;7Lz;7Lz;7Lz;7Yyu8YyuIYyu+Yyu+Yyu+YyuIYyu8Yyu8Yyu8Yyu8Yyu8YyuIYyu8Yyu8Yyu+YyuIYyu8Yyu8YyuIYyu8YyuIYyu+Yyu8YyuIYyuIYyu+Yyu8YyuIYyu+Yyu8Yyu+Yyu+Yyu+Yyu+Yyu+Yyu+Yyu+Yyu8XTi8XTi8XTi8XT(8XTv8XT(8XTv8XTv8XT(8XTv8XTi8XTi8XTi8XTi8XTi8XTi8XTi8XTi8XTi8XTi8XT(8XTi8XTv8XT(8XTi8XTi8XTi8XTv8XTv8XTv8XTi8XTv73Hv73Hv73Hv73fv73Uv73fv73Uv73Uv73fv73Uv73Hv73Hv73Hv73Hv73Hv73Hv73Hv73Hv73Hv73Hv73fv73Hv73Uv73fv73Uv73Uv73Uv73Uv73Hv73Uv73Uv73Uv73Hv73Uuq4UuqEUuq'Uuq'Uuq'UuqEUuq4Uuq4Uuq4Uuq4Uuq4UuqEUuq4Uuq4Uuq'UuqEUuq4Uuq4UuqEUuq4UuqEUuq'Uuq4UuqEUuqEUuq'Uuq4UuqEUuq'Uuq4Uuq4Uuq4Uuq'Uuq4TPe4TPe4TPe4TP$4TPr4TP$4TPr4TPr4TP$4TPr4TPe4TPe4TPe4TPe4TPe4TPe4TPe4TPe4TPe4TPe4TP$4TPe4TPr4TP$4TPe4TPe4TPe4TPr4TPr4TPr4TPr4TPr4TPr4TPr4TPr4TPr4TPr4TPr4TPe4TPr3/Dr3/Dr3/Dr3/br3/Qr3/br3/Qr3/Qr3/br3/Qr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/br3/Dr3/Qr3/br3/Qr3/Qr3/Qr3/Qr3/Qr3/Qr3/Dr3/Qr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Dr3/Qqm0QqmAQqm#Qqm#Qqm#QqmAQqm0Qqm0Qqm0Qqm0Qqm0QqmAQqm0Qqm0Qqm#QqmAQqm0Qqm0QqmAQqm0QqmAQqm#Qqm0QqmAQqmAQqm#Qqm0QqmAQqm0Qqm0Qqm#Qqm0Qqm#Qqm#Qqm#Qqm#Qqm#Qqm#Qqm#Qqm#Qqm#Qqm#Qqm#Qqm#Qqm#Qqm0PLa0PLa0PLa0PL 0PLn0PL 0PLn0PLn0PL 0PLn0PLa0PLa0PLa0PLa0PLa0PLa0PLa0PLa0PLa0PLa0PL 0PLa0PLn0PL 0PLa0PLn0PLa0PLa0PLa0PLa0PLa0PLn/+@n/+@n/+@n/+^n/+Mn/+^n/+Mn/+Mn/+^n/+Mn/+@n/+@n/+@n/+@n/+@n/+@n/+@n/+@n/+@n/+@n/+^n/+@n/+Mn/+^n/+Mn/+Mn/+Mn/+Mn/+Mn/+Mn/+@n/+Mn/+@n/+@n/+@n/+@n/+@n/+Mmi~Mmi~Mmi~Mmi=Mmi,Mmi=Mmi,Mmi,Mmi=Mmi,Mmi~Mmi~Mmi~Mmi~Mmi~Mmi~Mmi~Mmi~Mmi~Mmi~Mmi=Mmi~Mmi,Mmi=Mmi~Mmi~Mmi~Mmi,LH],LH],LH],LH{,LHj,LH{,LHj,LHj,LH{,LHj,LH],LH],LH],LH],LH],LH],LH],LH],LH],LH],LH{,LH],LHj,LH{,LH],LHj,LHj,LHj,LHj,LHj,LH],LHj+'<j+'<j+'<j+'Zj+'Ij+'Zj+'Ij+'Ij+'Zj+'Ij+'<j+'<j+'<j+'<j+'<j+'<j+'<j+'<j+'<j+'<j+'Zj+'<j+'Ij+'Zj+'Ij+'Ij+'Ij+'Ij+'Ij+'Ij+'<j+'Ij+'Ij+'Ij+'Ij+'Ij+'<j+'IiezIiezIiezIie9Iie(Iie9Iie(Iie(Iie9Iie(IiezIiezIiezIiezIiezIiezIiezIiezIiezIiezIie9IiezIie(Iie9Iie(Iie(Iie(Iie(Iie(Iie(IiezIie(HDY(HDY(HDY(HDw(HDf(HDw(HDf(HDf(HDw(HDf(HDY(HDY(HDY(HDY(HDY(HDY(HDY(HDY(HDY(HDY(HDw(HDY(HDf(HDw(HDY(HDf(HDf(HDf(HDf(HDf(HDf(HDf(HDf(HDf(HDf(HDf(HDf(HDf(HDY(HDf'#Ef'#Vf'#8f'#8f'#8f'#Vf'#Ef'#Ef'#Ef'#Ef'#Ef'#Vf'#Ef'#Ef'#8f'#Vf'#Ef'#Ef'#Vf'#Ef'#Vf'#8f'#Ef'#Vf'#Vf'#8f'#Ef'#Vf'#8f'#8f'#8f'#Ef'#8f'#8f'#8f'#8f'#8f'#8f'#8f'#8f'#8f'#8f'#8f'#EeavEeavEeavEea5Eea$Eea5Eea$Eea$Eea5Eea$EeavEeavEeavEeavEeavEeavEeavEeavEeavEeavEea5EeavEea$Eea5EeavEeavEeavEeavEeavEea$EeavEeavEeavEea$D@U$D@U$D@U$D@s$D@b$D@s$D@b$D@b$D@s$D@b$D@U$D@U$D@U$D@U$D@U$D@U$D@U$D@U$D@U$D@U$D@s$D@U$D@b$D@s$D@b$D@b$D@U$D@b$D@U$D@U$D@U$D@b#~Ab#~Rb#~4b#~4b#~4b#~Rb#~Ab#~Ab#~Ab#~Ab#~Ab#~Rb#~Ab#~Ab#~4b#~Rb#~Ab#~Ab#~Rb#~Ab#~Rb#~4b#~Ab#~Rb#~Rb#~4b#~Ab#~Rb#~4b#~4b#~4b#~Ab#~4b#~4b#~4b#~Aa]rAa]rAa]rAa]1Aa] Aa]1Aa] Aa] Aa]1Aa] Aa]rAa]rAa]rAa]rAa]rAa]rAa]rAa]rAa]rAa]rAa]1Aa]rAa] Aa]1Aa]rAa]rAa]rAa]rAa]rAa] Aa] Aa] Aa] Aa] Aa] Aa] Aa]rAa] @<Q @<Q @<Q @<o @<^ @<o @<^ @<^ @<o @<^ @<Q @<Q @<Q @<Q @<Q @<Q @<Q @<Q @<Q @<Q @<o @<Q @<^ @<o @<^ @<^ @<Q @<^ @<^ @<^ @<^ @<^ @<^ @<^ @<Q @<^~z=^~zN^~z0^~z0^~z0^~zN^~z=^~z=^~z=^~z=^~z=^~zN^~z=^~z=^~z0^~zN^~z=^~z=^~zN^~z=^~zN^~z0^~z=^~zN^~zN^~z0^~z=^~zN^~z0^~z=^~z0^~z0^~z0^~z0^~z0^~z0^~z0^~z0^~z0^~z0^~z0^~z0^~z0^~z0^~z0^~z0^~z0^~z=]Yn=]Yn=]Yn=]Y-=]Y{=]Y-=]Y{=]Y{=]Y-=]Y{=]Yn=]Yn=]Yn=]Yn=]Yn=]Yn=]Yn=]Yn=]Yn=]Yn=]Y-=]Yn=]Y{=]Y-=]Yn=]Yn=]Yn=]Yn=]Yn=]Y{=]Y{=]Y{=]Y{=]Y{=]Y{=]Y{=]Y{=]Y{=]Y{=]Y{=]Y{=]Y{=]Y{=]Y{=]Yn=]Y{<8M{<8M{<8M{<8k{<8Z{<8k{<8Z{<8Z{<8k{<8Z{<8M{<8M{<8M{<8M{<8M{<8M{<8M{<8M{<8M{<8M{<8k{<8M{<8Z{<8k{<8Z{<8Z{<8Z{<8Z{<8M{<8Z{<8M{<8M{<8M{<8M{<8M{<8M{<8M{<8M{<8M{<8Zzv9ZzvJZzv,Zzv,Zzv,ZzvJZzv9Zzv9Zzv9Zzv9Zzv9ZzvJZzv9Zzv9Zzv,ZzvJZzv9Zzv9ZzvJZzv9ZzvJZzv,Zzv9ZzvJZzvJZzv,Zzv9ZzvJZzv,Zzv9Zzv,Zzv,Zzv,Zzv,Zzv,Zzv,Zzv,Zzv,Zzv,Zzv9YUj9YUj9YUj9YU)9YUw9YU)9YUw9YUw9YU)9YUw9YUj9YUj9YUj9YUj9YUj9YUj9YUj9YUj9YUj9YUj9YU)9YUj9YUw9YU)9YUj9YUj9YUj9YUw9YUj9YUw84Iw84Iw84Iw84gw84Vw84gw84Vw84Vw84gw84Vw84Iw84Iw84Iw84Iw84Iw84Iw84Iw84Iw84Iw84Iw84gw84Iw84Vw84gw84Vw84Vw84Vw84Vw84Iw84Vw84Iw84Vvr5VvrFVvr(Vvr(Vvr(VvrFVvr5Vvr5Vvr5Vvr5Vvr5VvrFVvr5Vvr5Vvr(VvrFVvr5Vvr5VvrFVvr5VvrFVvr(Vvr5VvrFVvrFVvr(Vvr5VvrFVvr(Vvr5Vvr(Vvr5UQf5UQf5UQf5UQ%5UQs5UQ%5UQs5UQs5UQ%5UQs5UQf5UQf5UQf5UQf5UQf5UQf5UQf5UQf5UQf5UQf5UQ%5UQf5UQs5UQ%5UQf5UQf5UQf5UQs5UQs5UQs5UQs5UQs5UQs5UQs5UQs5UQs5UQf5UQs40Es40Es40Es40cs40Rs40cs40Rs40Rs40cs40Rs40Es40Es40Es40Es40Es40Es40Es40Es40Es40Es40cs40Es40Rs40cs40Rs40Rs40Rs40Rs40Es40Rs40Rs40Rs40Rs40Rs40Rs40Rs40Rs40Rs40Es40Rrn1RrnBRrn$Rrn$Rrn$RrnBRrn1Rrn1Rrn1Rrn1Rrn1RrnBRrn1Rrn1Rrn$RrnBRrn1Rrn1RrnBRrn1RrnBRrn$Rrn1RrnBRrnBRrn$Rrn1RrnBRrn1Rrn1Rrn$Rrn1Rrn$Rrn$Rrn$Rrn$Rrn$Rrn$Rrn$Rrn$Rrn$Rrn$Rrn$Rrn$Rrn$Rrn$Rrn$Rrn1QMb1QMb1QMb1QM!1QMo1QM!1QMo1QMo1QM!1QMo1QMb1QMb1QMb1QMb1QMb1QMb1QMb1QMb1QMb1QMb1QM!1QMb1QMo1QM!1QMb1QMo1QMb1QMb1QMb1QMb1QMb1QMb1QMb1QMo0,Ao0,Ao0,Ao0,_o0,No0,_o0,No0,No0,_o0,No0,Ao0,Ao0,Ao0,Ao0,Ao0,Ao0,Ao0,Ao0,Ao0,Ao0,_o0,Ao0,No0,_o0,No0,No0,No0,No0,No0,No0,Ao0,No0,Ao0,Ao0,Ao0,Ao0,Ao0,Ao0,Ao0,Nnj Nnj Nnj Nnj>Nnj-Nnj>Nnj-Nnj-Nnj>Nnj-Nnj Nnj Nnj Nnj Nnj Nnj Nnj Nnj Nnj Nnj Nnj>Nnj Nnj-Nnj>Nnj Nnj Nnj Nnj Nnj Nnj-MI^-MI^-MI^-MI|-MIk-MI|-MIk-MIk-MI|-MIk-MI^-MI^-MI^-MI^-MI^-MI^-MI^-MI^-MI^-MI^-MI|-MI^-MIk-MI|-MI^-MIk-MIk-MIk-MI^-MIk,(=k,(=k,(=k,([k,(Jk,([k,(Jk,(Jk,([k,(Jk,(=k,(=k,(=k,(=k,(=k,(=k,(=k,(=k,(=k,(=k,([k,(=k,(Jk,([k,(Jk,(Jk,(Jk,(Jk,(Jk,(Jk,(=k,(Jk,(Jk,(Jk,(=k,(Jjf{Jjf{Jjf{Jjf:Jjf)Jjf:Jjf)Jjf)Jjf:Jjf)Jjf{Jjf{Jjf{Jjf{Jjf{Jjf{Jjf{Jjf{Jjf{Jjf{Jjf:Jjf{Jjf)Jjf:Jjf)Jjf)Jjf)Jjf)Jjf{Jjf)IEZ)IEZ)IEZ)IEx)IEg)IEx)IEg)IEg)IEx)IEg)IEZ)IEZ)IEZ)IEZ)IEZ)IEZ)IEZ)IEZ)IEZ)IEZ)IEx)IEZ)IEg)IEx)IEZ)IEg)IEg)IEg)IEg)IEg)IEg)IEg)IEg)IEg)IEg)IEg)IEZ)IEg($Fg($Wg($9g($9g($9g($Wg($Fg($Fg($Fg($Fg($Fg($Wg($Fg($Fg($9g($Wg($Fg($Fg($Wg($Fg($Wg($9g($Fg($Wg($Wg($9g($Fg($Wg($9g($9g($9g($Fg($9g($9g($9g($9g($9g($9g($9g($9g($9g($9g($9g($9g($9g($Ffb%Ffb6FfbwFfbwFfbwFfb6Ffb%Ffb%Ffb%Ffb%Ffb%Ffb6Ffb%Ffb%FfbwFfb6Ffb%Ffb%Ffb6Ffb%Ffb6FfbwFfb%Ffb6Ffb6FfbwFfb%Ffb6Ffb%Ffb%FfbwFfb%EAV%EAV%EAV%EAt%EAc%EAt%EAc%EAc%EAt%EAc%EAV%EAV%EAV%EAV%EAV%EAV%EAV%EAV%EAV%EAV%EAt%EAV%EAc%EAt%EAc%EAc%EAV%EAc%EAV%EAV%EAV%EAV%EAV%EAc$ Bc$ Sc$ 5c$ 5c$ 5c$ Sc$ Bc$ Bc$ Bc$ Bc$ Bc$ Sc$ Bc$ Bc$ 5c$ Sc$ Bc$ Bc$ Sc$ Bc$ Sc$ 5c$ Bc$ Sc$ Sc$ 5c$ Bc$ Sc$ 5c$ 5c$ 5c$ Bc$ 5c$ 5c$ 5c$ 5c$ 5c$ Bb^sBb^sBb^sBb^2Bb^!Bb^2Bb^!Bb^!Bb^2Bb^!Bb^sBb^sBb^sBb^sBb^sBb^sBb^sBb^sBb^sBb^sBb^2Bb^sBb^!Bb^2Bb^sBb^sBb^sBb^sBb^sBb^!Bb^!Bb^!Bb^!Bb^!Bb^sBb^!A=R!A=R!A=R!A=p!A=_!A=p!A=_!A=_!A=p!A=_!A=R!A=R!A=R!A=R!A=R!A=R!A=R!A=R!A=R!A=R!A=p!A=R!A=_!A=p!A=_!A=_!A=R!A=_!A=_!A=_!A=_!A=_!A=R!A=_ {>_ {O_ {1_ {1_ {1_ {O_ {>_ {>_ {>_ {>_ {>_ {O_ {>_ {>_ {1_ {O_ {>_ {>_ {O_ {>_ {O_ {1_ {>_ {O_ {O_ {1_ {>_ {O_ {1_ {1_ {1_ {>_ {>_ {>_ {>_ {>_ {1_ {>^Zo>^Zo>^Zo>^Z.>^Z|>^Z.>^Z|>^Z|>^Z.>^Z|>^Zo>^Zo>^Zo>^Zo>^Zo>^Zo>^Zo>^Zo>^Zo>^Zo>^Z.>^Zo>^Z|>^Z.>^Zo>^Zo>^Zo>^Zo>^Zo>^Z|>^Z|>^Z|>^Z|>^Z|>^Z|>^Z|>^Z|>^Z|>^Z|>^Z|>^Z|>^Z|>^Zo>^Z|=9N|=9N|=9N|=9l|=9[|=9l|=9[|=9[|=9l|=9[|=9N|=9N|=9N|=9N|=9N|=9N|=9N|=9N|=9N|=9N|=9l|=9N|=9[|=9l|=9[|=9[|=9[|=9[|=9N|=9[|=9N|=9N|=9N|=9N|=9N|=9N|=9N|=9N|=9N|=9N|=9N|=9[{w:[{wK[{w-[{w-[{w-[{wK[{w:[{w:[{w:[{w:[{w:[{wK[{w:[{w:[{w-[{wK[{w:[{w:[{wK[{w:[{wK[{w-[{w:[{wK[{wK[{w-[{w:[{wK[{w-[{w:[{w-[{w-[{w-[{w-[{w-[{w-[{w-[{w-[{w-[{w-[{w-[{w:ZVk:ZVk:ZVk:ZV*:ZVx:ZV*:ZVx:ZVx:ZV*:ZVx:ZVk:ZVk:ZVk:ZVk:ZVk:ZVk:ZVk:ZVk:ZVk:ZVk:ZV*:ZVk:ZVx:ZV*:ZVk:ZVk:ZVk:ZVx:ZVk:ZVk:ZVk:ZVx95Jx95Jx95Jx95hx95Wx95hx95Wx95Wx95hx95Wx95Jx95Jx95Jx95Jx95Jx95Jx95Jx95Jx95Jx95Jx95hx95Jx95Wx95hx95Wx95Wx95Wx95Wx95Jx95Wx95Jx95Jx95Jx95Wws6WwsGWws)Wws)Wws)WwsGWws6Wws6Wws6Wws6Wws6WwsGWws6Wws6Wws)WwsGWws6Wws6WwsGWws6WwsGWws)Wws6WwsGWwsGWws)Wws6WwsGWws)Wws6Wws)Wws)Wws)Wws6VRg6VRg6VRg6VR&6VRt6VR&6VRt6VRt6VR&6VRt6VRg6VRg6VRg6VRg6VRg6VRg6VRg6VRg6VRg6VRg6VR&6VRg6VRt6VR&6VRg6VRg6VRg6VRt6VRt6VRt6VRt6VRt6VRt6VRt6VRg6VRt51Ft51Ft51Ft51dt51St51dt51St51St51dt51St51Ft51Ft51Ft51Ft51Ft51Ft51Ft51Ft51Ft51Ft51dt51Ft51St51dt51St51St51St51St51Ft51St51St51St51St51St51St51St51Ft51Sso2SsoCSso%Sso%Sso%SsoCSso2Sso2Sso2Sso2Sso2SsoCSso2Sso2Sso%SsoCSso2Sso2SsoCSso2SsoCSso%Sso2SsoCSsoCSso%Sso2SsoCSso2Sso2Sso%Sso2Sso%Sso%Sso%Sso%Sso%Sso%Sso%Sso%Sso%Sso%Sso%Sso%Sso%Sso%Sso%Sso%Sso%Sso2RNc2RNc2RNc2RN"2RNp2RN"2RNp2RNp2RN"2RNp2RNc2RNc2RNc2RNc2RNc2RNc2RNc2RNc2RNc2RNc2RN"2RNc2RNp2RN"2RNc2RNc2RNc2RNp2RNp2RNp2RNp2RNp2RNp2RNp2RNp2RNp2RNp2RNp2RNp2RNp2RNp2RNp2RNc2RNp1-Bp1-Bp1-Bp1-`p1-Op1-`p1-Op1-Op1-`p1-Op1-Bp1-Bp1-Bp1-Bp1-Bp1-Bp1-Bp1-Bp1-Bp1-Bp1-`p1-Bp1-Op1-`p1-Op1-Op1-Op1-Op1-Op1-Op1-Bp1-Op1-Bp1-Bp1-Bp1-Bp1-Bp1-Bp1-Bp1-Bp1-Bp1-O

```

The easy way to do this challenge is with a tokenised language which doesn't need newlines and ignores invalid tokens.

Tested using this interpreter\*. Assumes 8-bit cells for extra golfiness. Programs are also overlapped slightly to save some bytes.

<sup>\*This interpreter has a strange quirk whereby the last token needs a char after it to be registered, which affects `n = 62`. There's offline 8-bit interpreters without this quirk, but this was the best online one I could find.</sup>

# Answer
> 6 votes
# PHP, 95 programs, ~~2439~~ 2063 bytes

```
<?=0;die?>;></*na^bkd`m'(:chd>=:=;/)m`]ajc_l&'9bgc=<9<:/(l_\`ib^k%&8afb<;8;9/'k^[_ha]j$%7`ea;:7:8/&j]Z^g`\i#$6_d`:9697/%i\Y]f_[h"#5^c_98586/$h[X\e^Zg!"4]b^87475/#gZW[d]Yf !3\a]76364/"fYVZc\Xe~ 2[`\65253/!eXUYb[Wd}~1Z_[54142&% dWTXaZVc|}0Y^Z43031%%~cVSW`YUb{|/X]Y32/20$%}bURV_XTaz{.W\X21.1/#%|aTQU^WS`yz-V[W10-0."'}`SPT]VR_xy,UZV0/,/-!%z_ROS\UQ^wx+TYU/.+., %y^QNR[TP]vw*SXT.-*-+~%x]PMQZSO\uv)RWS-,),*}%w\OLPYRN[tu(QVR,+(+)|%v[NKOXQMZst'PUQ+*'*(|zuZMJNWPLYrs&OTP*)&)'{ztYLIMVOKXqr%NSO)(%(&zzsXKHLUNJWpq$MRN('$'%yzrWJGKTMIVop#LQM'&#&$xzqVIFJSLHUno"KPL&%"%#w|rUHEIRKGTmn!JOK%$!$"vzoTGDHQJFSlm INJ$# #!uznSFCGPIERkl~HMI#"~" tzmREBFOHDQjk}GLH"!}!~szlQDAENGCPij|FKG! | }spkPC@DMFBOhi{EJF ~{~|rpjOB?CLEANghzDIE~}z}{qpiNA>BKD@MfgyCHD}|y|zpphM@=AJC?LefxBGC|{x{yopgL?<@IB>KdewAFB{zwzxnpfK>;?HA=Jcdv@EAzyvywmrgJ=:>G@<Ibcu?D@yxuxvlpdI<9=F?;Habt>C?xwtwukpcH;8<E>:G`as=B>wvsvtjpbG:7;D=9F_`r<A=vurusjfaF96:C<8E^_q;@<utqtrif`E859B;7D]^p:?;tspsqhf_D748A:6C\]o9>:srorpgf^C637@95B[\n8=9rqnqoff]B526?84AZ[m7<8qpmpnef\A415>73@YZl6;7polomdf[@304=62?XYk5:6onknlch\?2/3<51>WXj495nmjmkbfY>1.2;40=VWi384mliljafX=0-1:3/<UVh273lkhkia\W</,092.;TUg162kjgjh`\V;.+/81-:STf051jifig_\U:-*.70,9RSe/40ihehf^\T9,)-6/+8QRd.3/hgdge]\S8+(,5.*7PQc-2.gfcfd\\R7*'+4-)6OPb,1-febec[\Q6)&*3,(5NOa+0,edadbZ\P5(%)2+'4MN`*/+dc`caZTQ4'$(1*&3LM_).*cb_b`X\N3&#'0)%2KL^(-)ba^a_XRM2%"&/($1JK]',(a`]`^WRL1$!%.'#0IJ\&+'`_\_]VRK0# $-&"/HI[%*&_^[^\URJ/"~#,%!.GHZ$)%^]Z][TRI.!}"+$ -FGY#($]\Y\ZSRH- |!*#~,EFX"'#\[X[YRRG,~{ )"}+DEW!&"[ZWZXQRF+}z~(!|*CDV %!ZYVYWPRE*|y}' {)BCU~$ YXUXVPJF){x|&~z(ABT}#~XWTWUOHC(zw{%}y'@AS|"}WVSVTNHB'yvz$|x&?@R{!|VURUSMHA&xuy#{w%>?Qz {UTQTRLH@%wtx"zv$=>Py~zTSPSQKH?$vsw!yu#<=Ox}ySRORPJH>#urv xt";<Nw|xRQNQOIH="tqu~ws!:;Mv{wQPMPNHH<!spt}vr 9:LuzvPOLOMGH; ros|uq~89KtyuONKNLFH:~qnr{tp}78JsxtNMJMKF>9}pmqzso|67IrwsMLILJE>8|olpyrn{56HqvrLKHKID>7{nkoxqmz45GpuqKJGJHC>6zmjnwply34FotpJIFIGB>5ylimvokx23EnsoIHEHFA>4xkhlunjw12DmrnHGDGE@>3wjgktmiv01ClqmGFCFD?>2vifjslhu/0BkplFEBEC>>1uheirkgt./AjokEDADB=>0tgdhqjfs-.@injDC@CA=4/sfcgpier,-?hmiCB?B@<4.rebfohdq+,>glhBA>A?;4-qdaengcp*+=fkgA@=@>:4,pc`dmfbo)*<

```

Requires the option output\_buffering to be On or some values such as 4096. It defaults to 4096 for the web service (but not CLI) at least for my installation.

The doc says `ob_clean` doesn't return anything. But it returned true nevertheless.

Shifted programs look like these:

```
9:  ...dmfbo)*<ejf@?<?=8+ob_clean();die?>;><8*na^bkd`m(:chd>=:=;/.)...
15: ...dmfbo)*<ejf@?<?=16-ob_clean();die?>;><04*na^bkd`m'(:chd>=:=;...
94: ...dmfbo)*<ejf@?<?=93+ob_clean();

```

Generated using this CJam program:

```
"<?=0;die?>"95,(;{["<?="1$(_Ab:--3={))'-}'+?"ob_clean();die?>"]sf{i\- 95+ 32- 95% ' +}}%s-5<

```

# Answer
> 5 votes
# CJam, 10 programs, 1 byte

I thought I'd better add this right off the bat before someone else gets cheeky and does it :P

```
0

```

A CJam program with just a plain number outputs that number, so this is an easy way to get 10 programs that work, namely:

`0`, `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, and `9`.

The next program `:` unsurprisingly does not output `10` but gives an "unfinished operator" error.

This undoubtedly works in many languages.

---
Tags: code-challenge, number, source-layout, printable-ascii
---


# Question
Title: Check if a pattern appears in a DNA sequence
In a project I am working on, I am checking to see if certain DNA sequences appear in certain genes in E. coli. I have written a program in Java that performs the below features. However, since I wrote my program in Java, the universe needs to be corrected and rid of verbosity by having you write your code in as few bytes as possible.

My program took a DNA sequences and a regex as input (for this challenge, order doesn't matter). The DNA sequence contains only the letters `A`, `C`, `G`, and `T`. It will be determined if the DNA sequence contains any subsequences that follow the regex, and the output of the program will be the one-indexed location(s) of the first character of each matching subsequence in the DNA sequence in your choice of format. If there is no such location, you may output any reasonable indicator of this.

The regex I used had the following specifications.

* `A`, `C`, `G`, and `T` match to themselves.
* `N` matches to any of `A`, `C`, `G`, and `T`
* `(X/Y)` means that at the current location in the sequence, the next character(s) in the sequence match `X` or `Y` (note that `X` and `Y` can be multiple characters long, and that there can be multiple slashes; for example, `(AA/AG/GA)` matches to `AA`, `AG` or `GG`; however, `X` and `Y` must have the same length)

You may assume that the DNA sequence is longer than any sequence that follows the specifications of the regex, and that both the DNA and the regex are valid.

---

## Test cases

Here, the DNA sequence is first, and the regex is second.

```
AAAAAAAAAA
AAA
==> 1 2 3 4 5 6 7 8

ACGTAATGAA
A(A/C)(T/G/A)
==> 1 5

GGGGCAGCAGCTGACTA
C(NA/AN)
==> 5 8 15

ACGTTAGTTAGCGTGATCGTG
CGTNA
==> 2 12

```

---

This is . The shortest answer in bytes wins. Standard rules apply.

# Answer
# Python 3, 125 bytes

```
import re,sys
a=sys.argv
s=re.sub
print([i+1 for i in range(len(a[1]))if re.match(s('N','[ACGT]',s('/','|',a[2])),a[1][i:])])

```
> 1 votes

# Answer
# Pyth, 28 bytes

```
fT*VSlQ_:RX+\^z"/N.|")0_M.__

```

Simple regex matching.

I hope there had a function which returns the position of each match, but there is not.

Test suite.
> 0 votes

---
Tags: code-golf, regular-expression, chemistry
---


title: Who's gonna win the football game?

text:
# Question
Title: Who's gonna win the football game?
The American football championship, Super Bowl 50, is happening today at 11:30pm UTC (and you can watch it live online). This challenge was made to celebrate it.

---

In an American football game, two teams compete to get the most points and there are six ways to score these points. We'll give each an abbreviation:

Write a program or function that takes in a single line string containing only these six abbreviations, in both uppercase and lowercase.

This string represents all the scoring events in a game (or portion of a game) of football, with the uppercase terms belonging to one team and the lowercase belonging to the other.

Your job is to report the final scores of the game and indicate who won with output of the form

```
[score 1] [to] [score 2]

```

where:

* `[score 1]` is always the larger of the two scores (if not equal), regardless of if uppercase or lowercase won.
* `[score 2]` is the smaller of the two scores (if not equal).
* `[to]` is `TO` if the uppercase team won, `to` if the lowercase team won, and `To` if it's a tie.

> **Example:** All the scoring events in Super Bowl XLIX could be summarized by the string
>
> ```
> TDXPtdxpTDXPtdxpfgtdxpTDXPTDXP
>
> ```
>
> where uppercase is the New England Patriots and lowercase is the Seattle Seahawks. The Patriots scored 28 and the Hawks 24, so the output would be:
>
> ```
> 28 TO 24
>
> ```

# Notes

* Your program/function must support any arbitrary input, including the empty string.
* `XP` and `XD` will only occur right after `TD`. `xp` and `xd` will only occur right after `td`.
* You may not assume the input string starts or ends in a certain case.
* A single trailing newline is optionally allowed in both the input and output

# Scoring

**The shortest code in bytes wins.** Answers that are posted before the kickoff (**too late now!**) of Super Bowl 50 may predict the winning team (either Panthers or Broncos), and if they are correct, get a -10% byte bonus!

(I will check revision history to ensure predictions have not changed and really were made before kickoff.)

# Test Cases

```
[empty string] -> 0 To 0
TDXPtdxpTDXPtdxpfgtdxpTDXPTDXP -> 28 TO 24
FG -> 3 TO 0
fg -> 3 to 0
TD -> 6 TO 0
td -> 6 to 0
TDXP -> 7 TO 0
tdxp -> 7 to 0
TDXD -> 8 TO 0
tdxd -> 8 to 0
S -> 2 TO 0
s -> 2 to 0
FCK -> 3 TO 0
fck -> 3 to 0
TDTDXDSssFCKfgfckFGtd -> 22 TO 16
fcksFCKS -> 5 To 5
tdtdtdtdxp -> 25 to 0
SSSSSSSTD -> 20 TO 0
fgSfckFGfgtdxptdxdTDs -> 26 to 11
FGTDXPtdxdtdsStdxpfgTDfckTDXDFCK -> 29 To 29

```

# Answer
> 3 votes
# Pyth, ~~49~~ ~~46~~ ~~43~~ 42 bytes (37.8 bytes with bonus)

```
jr" to "xh._-FJmsmhx"PSFT"kXd\D\S,rz2z2_SJ

```

*Thanks to @Maltysen for helping me save 4 bytes!*

Try it in the Pyth Compiler.

I like covering all bases, so I'll bet on the Broncos.

### How it works

```
jr" to "xh._-FJmsmhx"PSFT"kXd\D\S,rz2z2_SJ Input: z

                                  rz2      Swap the case of z.
                                 ,   z     Pair the result with z.
               m                           Map; for each d in the pair:
                           Xd\D\S            Replace each D with an S.
                 m                           Map; for each character k:
                   x"PSFT"k                    Compute k's first index on "PSFT".
                  h                            Increment the index.
                s                            Compute the sum of the incr. indices.
                                               "FG"  -> [3, 0]     -> 3
                                               "TD"  -> [4, 2]     -> 6
                                               "XP"  -> [0, 1]     -> 1
                                               "XD"  -> [0, 2]     -> 2
                                               "S"   -> [2]        -> 2
                                               "FCK" -> [3, 0, 0]  -> 3
                                               (lowercase letters) -> 0
              J                            Save the resulting list of scores in J.
            -F                             Reduce J by subtraction.
          ._                               Compute the sign of the difference.
         h                                 Add 1.
        x                             2    XOR the result with 2.
 r" to "                                   Pick‡ a function and apply it to " to ".
                                       _SJ Sort and reverse the list of scores.
j                                          Join, separating by the modified string.

```

`r` is a family of functions that operate on strings.

* If the first score in `J` (corresponding to swapped case `z`, i.e., the original lowercase letters) is lower than the second score, the sign function will return `-1`, `(-1 + 1) ^ 2 == 2` and `r" to "2` is `swapcase`, so it returns `" TO "`.
* If the first score is higher than the second score, the sign function will return `1`, `(1 + 1) ^ 2 == 0` and `r" to "0` is `lowercase`, so it returns `" to "`.
* If the scores are equal, the sign function will return `0`, `(0 + 1) ^ 2 == 3` and `r" to "3` is `title`, so it returns `" To "`.

# Answer
> 4 votes
# MATL, 51\*0.9 = 45.9 ~~54~~ ~~57~~ ~~58~~ ~~63~~ bytes

*Thanks to Dennis for removing 3 bytes!*

```
'%i To %i'j0h!3'PDFTS'tkXc=s4:Hh*sSPYD3MdXK?kK0<?Xk

```

An empty input string is represented in the online compiler as a single newline character.

*EDIT (June 8, 2016): The link below includes a modification as per release 18.1.0 of the language (move he first `3` right before `Xc`)*

**Try it online!**

I bet on the Broncos.

### Explanation

The scores are detected using a single letter, either upper or lowercase (uppercase is shown in the following):

* `P` for XP (1 point)
* `D` for XD (2 points)
* `F` for FG (3 points) and for FCK (3 points)
* `T` for TD (6 points)
* `S` for S (2 points)

Each of these five letters corresponds uniquely to a score event except that

* `F` is reused for `FG` and `FCK`, which have the same score. *Thanks to @Dennis for this*!
* `D` will detect both TD and XD. So `T` will be assigned 4 points instead of 6 to compensate.

The ordering `PDFTS`, saves a few bytes when defining the number array that specifies the points: `[1,2,3,4,2]`.

Each event is detected by the presence of one of the above letters in uppercase or lowercase. The comparison is done in three dimensions: input string length (*N*) × number of teams (2) × number of detected score events (5). Extensive use is made of broadcasting, which is the automatic expansion of an array along a singleton dimension to match the size of a larger array.

```
'%i To %i'  % string with format specifiers for two integers
j0h         % input string. Attach 0 so it's never empty. Gives string of length N>0
!           % transpose into char array of size N×1
3           % number literal
'PDFTS'     % characters to detect the five combined types of score
tk          % duplicate and convert to lowercase
Xc          % concatenate along the third dimension to produce a 1×5×2 array
=           % test for equality with broadcast. Gives N×5×2 array
s           % sum along 1st dim. Gives 1×5×2 array
4:Hh        % array [1,2,3,4,2] to compute the total score. Size 1×5(×1)
*           % multiply with broadcast. Gives 1×5×2 array
s           % sum along 2nd dim. Gives 1×1×2 array with the two scores
SP          % sort in reverse order along 3rd dim
YD          % sprintf. Gives output string with "To"
3M          % push array with the two scores again
dXK         % difference along 3rd dim. Gives a number. Copy to clipboard K
?           % is it non-zero? If so we need to make either lowercase or uppercase
  k         %   make (tentatively) lowercase
  K0<       %   did the uppercase team win?
  ?         %   if so...
    Xk      %     make uppercase
            % implicitly end the two if's and display string

```

# Answer
> 3 votes
# CJam, ~~57~~ ~~55~~ ~~54~~ ~~53~~ ~~50~~ 49 bytes

```
q_32f^]{"PSFTD"f#:)5Yer1b}%_$(@:-g"ToTOto"2/=\]S*

```

Try it online!

I have no idea what a Bronco is, so I'll bet on the Panthers.

### How it works

```
q                              Read all input from STDIN.
 _                             Push a copy.
  32f^                         XOR all characters with 32. This swaps case.
      ]                        Wrap both strings in an array.
       {                 }%    Map; push the string S, then:
        "PSFTD"                    Push that string (T).
               f#                  Compute the index of each character of S in T.
                 :)                Increment each index.
                   5Yer            Replace 5's with 2's.
                       1b          Add the resulting integers.
                                       "FG"  -> [3 0]      -> 3
                                       "TD"  -> [4 2]      -> 6
                                       "XP"  -> [0 1]      -> 1
                                       "XD"  -> [0 2]      -> 2
                                       "S"   -> [2]        -> 2
                                       "FCK" -> [3 0 0]    -> 3
                                       (lowercase letters) -> 0

                               We've now computed the scores of the first (input)
                               and second (swapped case) team.

_$                             Push a copy of the array of scores and sort it.
  (                            Shift out the first (lower) score.
   @                           Rotate the array of scores on top.
    :-                         Reduce it by subtraction.
      g                        Compute the sign (1, 0 or -1) of the difference.
       "ToTOto"2/              Push ["To" "TO" "to"].
                 =             Select the string that corresponds to the sign.
                  \            Swap it with the lower score.
                   ]           Wrap the entire stack in an array.
                    S*         Join the resulting array, separating by spaces.

```

# Answer
> 3 votes
# JavaScript (ES6), 128 ~~130~~ bytes

**Edit** 2 bytes saved applying @Neil's tip

```
s=>(l=u=0,s.replace(/fck|s|../gi,x=>(z=+' 231  362'[parseInt(x,36)%10],x>'a'?l+=z:u+=z)),l>u?l+' to '+u:u+(u>l?' TO ':' To ')+l

```

**TEST**

```
f=s=>(
  l=u=0,
  s.replace(/fck|s|../gi,x=>(
    z=+' 231  362'[parseInt(x,36)%10],
    x>'a'?l+=z:u+=z
  )),
  l>u?l+' to '+u:u+(u>l?' TO ':' To ')+l
)

//TEST
console.log=x=>O.textContent+=x+'\n'

;[
["","0 To 0"],
["TDXPtdxpTDXPtdxpfgtdxpTDXPTDXP", "28 TO 24"],
["FG", "3 TO 0"],
["fg", "3 to 0"],
["TD", "6 TO 0"],
["td", "6 to 0"],
["TDXP", "7 TO 0"],
["tdxp", "7 to 0"],
["TDXD", "8 TO 0"],
["tdxd", "8 to 0"],
["S", "2 TO 0"],
["s", "2 to 0"],
["FCK", "3 TO 0"],
["fck", "3 to 0"],
["TDTDXDSssFCKfgfckFGtd", "22 TO 16"],
["fcksFCKS", "5 To 5"],
["tdtdtdtdxp", "25 to 0"],
["SSSSSSSTD", "20 TO 0"],
["fgSfckFGfgtdxptdxdTDs", "26 to 11"],
["FGTDXPtdxdtdsStdxpfgTDfckTDXDFCK", "29 To 29"]
].forEach(t=>{
  var i=t[0],x=t[1],r=f(i)
  console.log(i+' -> '+r+(r==x?' OK':' FAIL expected '+x))
})
```

```
<pre id=O></pre>
```

# Answer
> 2 votes
### Perl, ~~144~~ 140 + 2 = 142 bytes

```
%a=qw(fg 3 td 6 xp 1 xd 2 s 2 fck 3);@a=(0,0);$^=lc,$a[$^eq$_]+=$a{$^}for/fck|s|../gi;$,=$".(To,TO,to)[$a[1]-$a[0]<=>0].$";say sort{$b-$a}@a

```

Requires the `-n` flag and `-E`:

```
$ echo "
TDXPtdxpTDXPtdxpfgtdxpTDXPTDXP
FG
fg
SSSSSSSTD
FGTDXPtdxdtdsStdxpfgTDfckTDXDFCK" | \
perl -nE'%a=qw(fg 3 td 6 xp 1 xd 2 s 2 fck 3);@a=(0,0);$^=lc,$a[$^eq$_]+=$a{$^}for/fck|s|../gi;$,=$".(To,TO,to)[$a[1]-$a[0]<=>0].$";say sort{$b-$a}@a'
0 To 0
28 TO 24
3 TO 0
3 to 0
20 TO 0
29 To 29

```

Edit: Forgot to support `to`, `To` and `TO`.

# Answer
> 2 votes
# JavaScript (ES6), ~~165~~ ~~156~~ ~~151~~ 149 bytes

```
s=>(a=b=0,s.match(/S|FCK|../gi)||[]).map(m=>(u=m.toUpperCase(),p=u>"XO"?1:u=="TD"?6:u>"R"?2:3,u<m?a+=p:b+=p))&&a>b?a+" to "+b:b+(b>a?" TO ":" To ")+a

```

*9 bytes saved thanks to @dev-null, 5 thanks to @Not that Charles and 2 thanks to @Neil!*

## Explanation

```
var solution =

s=>(
    a=b=0,                // scores for teams A and B
    s.match(/S|FCK|../gi) // get an array of each abbreviation
      ||[]                // if it returns null, default to an empty array
  ).map(m=>(              // for each abbreviation m
    u=m.toUpperCase(),    // u = abbreviation in upper-case
    p=                    // p = number of points for the abbreviation
      u>"XO"?1            // case "XP"
      :u=="TD"?6          // case "TD"
      :u>"R"?2            // case "XD" or "S"
      :3,                 // case "FG" or "FCK"
    u<m?a+=p:b+=p         // add the points to the appropriate team
  ))

  // Output the scores
  &&a>b?a+" to "+b
  :b+(b>a?" TO ":" To ")+a
```

```
<input type="text" id="input" value="FGTDXPtdxdtdsStdxpfgTDfckTDXDFCK" />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>
```

# Answer
> 1 votes
# Lua, ~~231~~ 200 Bytes

It was a lot of fun, even if I don't really know the rules of american football (We have Rugby here :)). I had to test a lot of things to make it as short as possible, I don't think there's a lot of things to improve, maybe there isn't.

**Edit: I'm a total retard. The first solution I've worked on revolved around using array expansion, then I changed it and the array containing the scores for both the lowercase and the uppercase team wasn't useful anymore. Removing it and using plain variable makes a beautiful -31 bytes.**

```
a={F=3,D=2,T=4,P=1,S=2}l,u=0,0 io.read():gsub(".",function(c)x=a[c:upper()]if a[c]then u=u+a[c]elseif x then l=l+x end end)w=l>u and" to "or l<u and" TO "or" To "print(math.max(l,u)..w..math.min(l,u))

```

### Ungolfed and explanations

```
a={F=3,D=2,T=4,P=1,S=2}        -- define the table a with our scoring values
l,u=0,0                        -- scores for the upper and lowercase teams
io.read():gsub(".",function(c) -- iterate over each character in the input
  x=a[c:upper()]               -- x contains the score for a lowercase character
  if a[c]                      -- if a contains c (would evaluate to nil otherwise)
  then
    u=u+a[c]                   -- increment the score of the uppercase team
  elseif x                     -- if x isn't nil
  then                         -- same as "a contains c:upper()"
    l=l+x                      -- increment the score of the lowercase team
  end
end)                           -- exit the anonyme function
w=l>u and" to "               -- nested ternary, lower > upper, we will use "to"
    or l<u and" TO "       -- lower < uppercase, use "TO"
    or" To "                   -- else (draw), use "To"
print(math.max(l,u)        -- output the concatenated string using
      ..b.w..math.min(l,u))-- min/max to put the winner in the first position

```

# Answer
> 0 votes
# Python, 167 bytes

The superb owl is long past, but since there isn't a Python solution yet:

```
def f(s):g=lambda s:0if s==""else{68:1,70:3,83:2,84:5,88:1}.get(ord(s[0]),0)+g(s[1:]);a=g(s);b=g(s.upper())-a;return"%i %s %i"%((a,("To","TO")[a>b],b),(b,"to",a))[a<b]

```

Works in Python 2 or 3.

---
Tags: code-golf, string, arithmetic, game
---


title: Generalized Birthday Problem

text:
# Question
Title: Generalized Birthday Problem
Tonight, my fiancée took me out to dinner to celebrate my birthday. While we were out, I heard *Happy Birthday* sung to 5 different guests (including myself), in a restaurant full of 50 people. This got me wondering - the original birthday problem (finding the probability that 2 people in a room of `N` people share the same birthday) is very simple and straightforward. But what about calculating the probability that at least `k` people out of `N` people share the same birthday?

In case you're wondering, the probability of at least 5 people out of 50 total people sharing the same birthday is about 1/10000.

## The Challenge

Given two integers `N` and `k`, where `N >= k > 0`, output the probability that at least `k` people in a group of `N` people share the same birthday. To keep things simple, assume that there are always 365 possible birthdays, and that all days are equally likely.

For `k = 2`, this boils down to the original birthday problem, and the probability is `1 - P(365, N)/(365)**N` (where `P(n,k)` is the number of k-length permutations formed from n elements). For larger values of `k`, this Wolfram MathWorld article may prove useful.

## Rules

* Output must be deterministic, and as accurate as possible for your chosen language. This means no Monte Carlo estimation or Poisson approximation.
* `N` and `k` will be no larger than the largest representable integer in your chosen language. If your chosen language has no hard maximum on integers (aside from memory constraints), then `N` and `k` may be arbitrarily large.
* Accuracy errors stemming from floating-point inaccuracies may be ignored - your solution should assume perfectly-accurate, infinite-precision floats.

## Test Cases

Format: `k, N -> exact fraction (float approximation)`

```
2, 4 -> 795341/48627125 (0.016355912466550306)
2, 10 -> 2689423743942044098153/22996713557917153515625 (0.11694817771107766)
2, 23 -> 38093904702297390785243708291056390518886454060947061/75091883268515350125426207425223147563269805908203125 (0.5072972343239854)
3, 3 -> 1/133225 (7.5060987051979735e-06)
3, 15 -> 99202120236895898424238531990273/29796146005797507000413918212890625 (0.0033293607910766013)
3, 23 -> 4770369978858741874704938828021312421544898229270601/375459416342576750627131037126115737816349029541015625 (0.01270542106874784)
3, 88 -> 121972658600365952270507870814168157581992420315979376776734831989281511796047744560525362056937843069780281314799508374037334481686749665057776557164805212647907376598926392555810192414444095707428833039241/238663638085694198987526661236008945231785263891283516149752738222327030518604865144748956653519802030443538582564040039437134064787503711547079611163210009542953054552383296282869196147657930850982666015625 (0.5110651106247305)
4, 5 -> 1821/17748900625 (1.0259790386313012e-07)
4, 25 -> 2485259613640935164402771922618780423376797142403469821/10004116148447957520459906484225353834116619892120361328125 (0.0002484237064787077)
5, 50 -> 786993779912104445948839077141385547220875807924661029087862889286553262259306606691973696493529913926889614561937/7306010813549515310358093277059651246342214174497508156711617142094873581852472030624097938198246993124485015869140625 (0.00010771867165219201)
10, 11 -> 801/8393800448639761033203125 (9.542757239717371e-23)
10, 20 -> 7563066516919731020375145315161/4825745614492126958810682272575693836212158203125 (1.5672327389589693e-18)
10, 100 -> 122483733913713880468912433840827432571103991156207938550769934255186675421169322116627610793923974214844245486313555179552213623490113886544747626665059355613885669915058701717890707367972476863138223808168550175885417452745887418265215709/1018100624231385241853189999481940942382873878399046008966742039665259133127558338726075853312698838815389196105495212915667272376736512436519973194623721779480597820765897548554160854805712082157001360774761962446621765820964355953037738800048828125 (1.2030611807765361e-10)
10, 200 -> 46037609834855282194444796809612644889409465037669687935667461523743071657580101605348193810323944369492022110911489191609021322290505098856358912879677731966113966723477854912238177976801306968267513131490721538703324306724303400725590188016199359187262098021797557231190080930654308244474302621083905460764730976861073112110503993354926967673128790398832479866320227003479651999296010679699346931041199162583292649095888379961533947862695990956213767291953359129132526574405705744727693754517/378333041587022747413582050553902956219347236460887942751654696440740074897712544982385679244606727641966213694207954095750881417642309033313110718881314425431789802709136766451022222829015561216923212248085160525409958950556460005591372098706995468877542448525403291516015085653857006548005361106043070914396018461580475651719152455730181412523297836008507156692430467118523245584181582255037664477857149762078637248959905010608686740872875726844702607085395469621591502118462813086807727813720703125 (1.21685406174776e-07)

```

# Answer
# Jelly, ~~17~~ 16 bytes

```
ĠZL
365ṗÇ€<¬µS÷L

```

Extremely inefficient. Try it online! (but keep **N** below **3**)

### How it works

```
365ṗÇ€<¬µS÷L  Main link. Left argument: N. Right argument: K

365ṗ          Cartesian product; generate all lists of length N that consist of
              elements of [1, ..., 365].
    Ç€        Map the helper link over all generated lists. It returns the highest
              amount of people that share a single birthday.
      <       Compare each result with K.
       ¬      Negate.
        µS÷L  Take the mean by dividing the sum by the length.

ĠZL           Helper link. Argument: A (list of integers)

Ġ             Group the indices have identical values in A.
 Z            Zip; transpose rows with columns.
  L           Take the length of the result, thus counting columns.

```
> 2 votes

# Answer
# MATL, 16 bytes

```
365:Z^!tXM=s>~Ym

```

First input is `N`, second is `k`.

**Try it online!**

This is an enumeration-based approach, like Dennis' Jelly answer, so input numbers should be kept small due to memory limitations.

```
365:   % Vector [1 2 ... 365]
Z^     % Take N implicitly. Cartesian power. Gives a 2D array with each
       % "combination" on a row
!      % Transpose
t      % Duplicate
XM     % Mode (most frequent element) of each column
=      % Test for equality, element-wise with broadcast. For each column, gives
       % true for elements equal to that column's mode, false for the rest
s      % Sum of each column. Gives a row vector
>~     % Take k implicitly. True for elements equal or greater than k
Ym     % Mean of each column. Implicitly display

```
> 4 votes

# Answer
# J, ~~41~~ 36 bytes

```
(+/%#)@(<:365&(#~>./@(#/.~)@#:i.@^))

```

Straight-forward approach similar to the others. Runs into memory issues at **n \> 3**.

## Usage

Takes the value of `k` on the LHS and `n` on the RHS.

```
   f =: (+/%#)@(<:365&(#~>./@(#/.~)@#:i.@^))
   0 f 0
0
   0 f 1
1
   1 f 1
1
   0 f 2
1
   1 f 2
1
   2 f 2
0.00273973
   0 f 3
1
   1 f 3
1
   2 f 3
0.00820417
   3 f 3
7.5061e_6

```

On my pc, using an i7-4770k and the timer foreign `6!:2`, computing for **n = 3** requires about 25 seconds.

```
   timer =: 6!:2
   timer '2 f 3'
24.7893
   timer '3 f 3'
24.896

```

## Explanation

```
(+/%#)@(<:365&(#~>./@(#/.~)@#:i.@^)) Input: k on LHS, n on RHS
          365&                       The number 365
               #~                    Create n copies of 365
                                 ^   Calculate 365^n
                              i.@    The range [0, 1, ..., 365^n-1]
                            #:       Convert each value in the range to base-n and pad
                                     with zeroes to the right so that each has n digits
                     (#/.~)@         Find the size of each set of identical values
                 >./@                Find the max size of each
        <:                           Test each if greater than or equal to k
(+/%#)@                              Apply to the previous result
 +/                                  Find the sum of the values
    #                                Count the number of values
   %                                 Divide the sum by the count and return

```
> 0 votes

---
Tags: code-golf, combinatorics, probability-theory
---


title: Super speedy totient function

text:
# Question
Title: Super speedy totient function
The goal is simple: **calculate the totient function** for as many numbers as you can in **10 seconds** and **sum the numbers.**

You must print your result at the end and you must actually calculate it. No automated totient function is allowed, but bignum libraries are. **You have to start at 1 and count up all the integers consecutively. You are *not* allowed to skip numbers.**

Your score is **how many numbers your program can calculate on your machine / how many my program can calculate on your machine**. My code is a simple program in C++ (optimizations off), hopefully you can run it.

Important properties you could use!

* if `gcd(m,n) = 1, phi(mn) = phi(m) * phi(n)`
* if `p` is prime, `phi(p) = p - 1` (for `p < 10^20`)
* if `n` is even, `phi(2n) = 2 phi(n)`
* others listed in first link

My code

```
#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    while (b != 0)
    {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int phi(int n)
{
    int x = 0;
    for (int i=1; i<=n; i++)
    {
        if (gcd(n, i) == 1)
            x++;
    }
    return x;
}

int main()
{
    unsigned int sum = 0;
    for (int i=1; i<19000; i++) // Change this so it runs in 10 seconds
    {
        sum += phi(i);
    }
        cout << sum << endl;
        return 0;
}

```

# Answer
> 14 votes
# Nimrod: ~38,667 (580,000,000/15,000)

This answer uses a pretty simple approach. The code employs a simple prime number sieve that stores the prime of the smallest prime power in each slot for composite numbers (zero for primes), then uses dynamic programming to construct the totient function over the same range, then sums the results. The program spends virtually all its time constructing the sieve, then calculates the totient function in a fraction of the time. It looks like it comes down to constructing an efficient sieve (with the slight twist that one also has to be able to extract a prime factor for composite numbers from the result and has to keep memory usage at a reasonable level).

Update: Improved performance by reducing memory footprint and improving cache behavior. It's possible to squeeze out 5%-10% more performance, but the increase in code complexity is not worth it. Ultimately, this algorithm primarily exercises a CPU's von Neumann bottleneck, and there are very few algorithmic tweaks that can get around that.

Also updated the performance divisor since the C++ code wasn't meant to be compiled with all optimizations on and nobody else did it. :)

Update 2: Optimized sieve operation for improved memory access. Now handling small primes in bulk via memcpy() (~5% speedup) and skipping multiples of 2, 3, and 5 when sieving bigger primes (~10% speedup).

C++ code: 9.9 seconds (with g++ 4.9)

Nimrod code: 9.9 seconds (with -d:release, gcc 4.9 backend)

```
proc handleSmallPrimes(sieve: var openarray[int32], m: int) =
  # Small primes are handled as a special case through what is ideally
  # the system's highly optimized memcpy() routine.
  let k = 2*3*5*7*11*13*17
  var sp = newSeq[int32](k div 2)
  for i in [3,5,7,11,13,17]:
    for j in countup(i, k, 2*i):
      sp[j div 2] = int32(i)
  for i in countup(0, sieve.high, len(sp)):
    if i + len(sp) <= len(sieve):
      copyMem(addr(sieve[i]), addr(sp[0]), sizeof(int32)*len(sp))
    else:
      copyMem(addr(sieve[i]), addr(sp[0]), sizeof(int32)*(len(sieve)-i))
  # Fixing up the numbers for values that are actually prime.
  for i in [3,5,7,11,13,17]:
    sieve[i div 2] = 0

proc constructSieve(m: int): seq[int32] =
  result = newSeq[int32](m div 2 + 1)
  handleSmallPrimes(result, m)
  var i = 19
  # Having handled small primes, we only consider candidates for
  # composite numbers that are relatively prime with 31. This cuts
  # their number almost in half.
  let steps = [ 1, 7, 11, 13, 17, 19, 23, 29, 31 ]
  var isteps: array[8, int]
  while i * i <= m:
    if result[i div 2] == 0:
      for j in 0..7: isteps[j] = i*(steps[j+1]-steps[j])
      var k = 1 # second entry in "steps mod 30" list.
      var j = 7*i
      while j <= m:
        result[j div 2] = int32(i)
        j += isteps[k]
        k = (k + 1) and 7 # "mod 30" list has eight elements.
    i += 2

proc calculateAndSumTotients(sieve: var openarray[int32], n: int): int =
  result = 1
  for i in 2'i32..int32(n):
    var tot: int32
    if (i and 1) == 0:
      var m = i div 2
      var pp: int32 = 2
      while (m and 1) == 0:
        pp *= 2
        m = m div 2
      if m == 1:
        tot = pp div 2
      else:
        tot = (pp div 2) * sieve[m div 2]
    elif sieve[i div 2] == 0: # prime?
      tot = i - 1
      sieve[i div 2] = tot
    else:
      # find and extract the first prime power pp.
      # It's relatively prime with i/pp.
      var p = sieve[i div 2]
      var m = i div p
      var pp = p
      while m mod p == 0 and m != p:
        pp *= p
        m = m div p
      if m == p: # is i a prime power?
        tot = pp*(p-1)
      else:
        tot = sieve[pp div 2] * sieve[m div 2]
      sieve[i div 2] = tot
    result += tot

proc main(n: int) =
  var sieve = constructSieve(n)
  let totSum = calculateAndSumTotients(sieve, n)
  echo totSum

main(580_000_000)

```

# Answer
> 9 votes
### Java, score ~24,000 (360,000,000 / 15,000)

The java code below does calculation of the totient function and the prime sieve together. Note that depending on your machine you have to increase the initial/maximum heap size (on my rather slow laptop I had to go up to `-Xmx3g -Xms3g`).

```
public class Totient {

    final static int size = 360000000;
    final static int[] phi = new int[size];

    public static void main(String[] args) {
        long time = System.currentTimeMillis();
        long sum = 0;

        phi[1] = 1;
        for (int i = 2; i < size; i++) {
            if (phi[i] == 0) {
                phi[i] = i - 1;
                for (int j = 2; i * j < size; j++) {
                    if (phi[j] == 0)
                        continue;

                    int q = j;
                    int f = i - 1;
                    while (q % i == 0) {
                        f *= i;
                        q /= i;
                    }
                    phi[i * j] = f * phi[q];
                }
            }
            sum += phi[i];
        }
        System.out.println(System.currentTimeMillis() - time);
        System.out.println(sum);
    }
}

```

# Answer
> 9 votes
# Nimrod: ~2,333,333 (42,000,000,000/18,000)

This uses an entirely different approach from my previous answer. See comments for details. The `longint` module can be found here.

```
import longint

const max = 500_000_000

var ts_mem: array[1..max, int]

# ts(n, d) is defined as the number of pairs (a,b)
# such that 1 <= a <= b <= n and gcd(a,b) = d.
#
# The following equations hold:
#
# ts(n, d) = ts(n div d, 1)
# sum for i in 1..n of ts(n, i) = n*(n+1)/2
#
# This leads to the recurrence:
# ts(n, 1) = n*(n+1)/2 - sum for i in 2..n of ts(n, i)
#
# or, where ts(n) = ts(n, 1):
# ts(n) = n*(n+1)/2 - sum for i in 2..n of ts(n div i)
#
# Note that the large numbers that we deal with can
# overflow 64-bit integers.

proc ts(n, gcd: int): int =
  if n == 0:
    result = 0
  elif n == 1 and gcd == 1:
    result = 1
  elif gcd == 1:
    result = n*(n+1) div 2
    for i in 2..n:
      result -= ts(n, i)
  else:
    result = ts(n div gcd, 1)

# Below is the optimized version of the same algorithm.

proc ts(n: int): int =
  if n == 0:
    result = 0
  elif n == 1:
    result = 1
  else:
    if n <= max and ts_mem[n] > 0:
      return ts_mem[n]
    result = n*(n+1) div 2
    var p = n
    var k = 2
    while k < n div k:
      let pold = p
      p = n div k
      k += 1
      let t = ts(n div pold)
      result -= t * (pold-p)
    while p >= 2:
      result -= ts(n div p)
      p -= 1
    if n <= max:
      ts_mem[n] = result

proc ts(n: int128): int128 =
  if n <= 2_000_000_000:
    result = ts(n.toInt)
  else:
    result = n*(n+1) div 2
    var p = n
    var k = 2
    while k < n div k:
      let pold = p
      p = n div k
      k += 1
      let t = ts(n div pold)
      result = result - t * (pold-p)
    while p >= 2:
      result = result - ts(n div p)
      p = p - 1

echo ts(42_000_000_000.toInt128)

```

# Answer
> 7 votes
**C#: 49,000 (980,000,000 / 20,000)**

https://codegolf.stackexchange.com/a/26800 "Howard's code".
But modified, phi values are computed for odd integers.

```
using System;
using sw = System.Diagnostics.Stopwatch;
class Program
{
    static void Main()
    {
        sw sw = sw.StartNew();
        Console.Write(sumPhi(980000000) + " " + sw.Elapsed);
        sw.Stop(); Console.Read();
    }

    static long sumPhi(int n)  // sum phi[i] , 1 <= i <= n
    {
        long s = 0; int[] phi;
        if (n < 1) return 0; phi = buildPhi(n + 1);
        for (int i = 1; i <= n; i++) s += getPhi(i, phi);
        return s;
    }

    static int getPhi(int i, int[] phi)
    {
        if ((i & 1) > 0) return phi[i >> 1];
        if ((i & 3) > 0) return phi[i >> 2];
        int z = ntz(i); return phi[i >> z >> 1] << z - 1;
    }

    static int[] buildPhi(int n)  // phi[i >> 1] , i odd , i < n
    {
        int i, j, y, x, q, r, f; int[] phi;
        if (n < 2) return new int[] { 0 };
        phi = new int[n / 2]; phi[0] = 1;
        for (j = 2, i = 3; i < n; i *= 3, j *= 3) phi[i >> 1] = j;
        for (x = 4, i = 5; i <= n >> 1; i += x ^= 6)
        {
            if (phi[i >> 1] > 0) continue; phi[i >> 1] = i ^ 1;
            for (j = 3, y = 3 * i; y < n; y += i << 1, j += 2)
            {
                if (phi[j >> 1] == 0) continue; q = j; f = i ^ 1;
                while ((r = q) == i * (q /= i)) f *= i;
                phi[y >> 1] = f * phi[r >> 1];
            }
        }
        for (; i < n; i += x ^= 6)  // primes > n / 2
            if (phi[i >> 1] == 0)
                phi[i >> 1] = i ^ 1;
        return phi;
    }

    static int ntz(int i)  // number of trailing zeros
    {
        int z = 1;
        if ((i & 0xffff) == 0) { z += 16; i >>= 16; }
        if ((i & 0x00ff) == 0) { z += 08; i >>= 08; }
        if ((i & 0x000f) == 0) { z += 04; i >>= 04; }
        if ((i & 0x0003) == 0) { z += 02; i >>= 02; }
        return z - (i & 1);
    }
}

```

New score: **61,000** (1,220,000,000 / 20,000)
In "App.config" I had to add "gcAllowVeryLargeObjects enabled=true".

```
    static long sumPhi(int n)
    {
        int i1, i2, i3, i4, z; long s1, s2, s3, s4; int[] phi;
        if (n < 1) return 0; phi = buildPhi(n + 1); n -= 4; z = 2;
        i1 = 1; i2 = 2; i3 = 3; i4 = 4; s1 = s2 = s3 = s4 = 0;
        if (n > 0)
            for (; ; )
            {
                s1 += phi[i1 >> 1];
                s2 += phi[i2 >> 2];
                s3 += phi[i3 >> 1];
                s4 += phi[i4 >> z >> 1] << z - 1;
                i1 += 4; i2 += 4; i3 += 4; i4 += 4;
                n -= 4; if (n < 0) break;
                if (z == 2)
                {
                    z = 3; i4 >>= 3;
                    while ((i4 & 3) == 0) { i4 >>= 2; z += 2; }
                    z += i4 & 1 ^ 1;
                    i4 = i3 + 1;
                }
                else z = 2;
            }
        if (n > -4) s1 += phi[i1 >> 1];
        if (n > -3) s2 += phi[i2 >> 2];
        if (n > -2) s3 += phi[i3 >> 1];
        if (n > -1) s4 += phi[i4 >> z >> 1] << z - 1;
        return s1 + s2 + s3 + s4;
    }

    static int[] buildPhi(int n)
    {
        int i, j, y, x, q0, q1, f; int[] phi;
        if (n < 2) return new int[] { 0 };
        phi = new int[n / 2]; phi[0] = 1;
        for (uint u = 2, v = 3; v < n; v *= 3, u *= 3) phi[v >> 1] = (int)u;
        for (x = 4, i = 5; i <= n >> 1; i += x ^= 6)
        {
            if (phi[i >> 1] > 0) continue; phi[i >> 1] = i ^ 1;
            for (j = 3, y = 3 * i; y < n; y += i << 1, j += 2)
            {
                if (phi[j >> 1] == 0) continue; q0 = j; f = i ^ 1;
                while ((q1 = q0) == i * (q0 /= i)) f *= i;
                phi[y >> 1] = f * phi[q1 >> 1];
            }
        }
        for (; i < n; i += x ^= 6)
            if (phi[i >> 1] == 0)
                phi[i >> 1] = i ^ 1;
        return phi;
    }

```

# Answer
> 4 votes
# Python 3: ~24000 (335,000,000 / 14,000)

My version is a Python port of Howard's algorithm. My original function was a modification of an algorithm introduced in this blogpost.

I'm using Numpy and Numba modules to speed up the execution time. Note that normally you don't need to declare the types of the local variables (when using Numba), but in this case I wanted to squeeze the execution time as much as possible.

Edit: combined constructsieve and summarum functions into a single function.

C++: 9.99s (n = 14,000); Python 3: 9.94s (n = 335,000,000)

```
import numba as nb
import numpy as np
import time

n = 335000000

@nb.njit("i8(i4[:])", locals=dict(
    n=nb.int32, s=nb.int64, i=nb.int32,
    j=nb.int32, q=nb.int32, f=nb.int32))

def summarum(phi):
    s = 0

    phi[1] = 1

    i = 2
    while i < n:
        if phi[i] == 0:
            phi[i] = i - 1

            j = 2

            while j * i < n:
                if phi[j] != 0:
                    q = j
                    f = i - 1

                    while q % i == 0:
                        f *= i
                        q //= i

                    phi[i * j] = f * phi[q]
                j += 1
        s += phi[i]
        i += 1
    return s

if __name__ == "__main__":
    s1 = time.time()
    a = summarum(np.zeros(n, np.int32))
    s2 = time.time()

    print(a)
    print("{}s".format(s2 - s1))

```

# Answer
> 3 votes
Here is my Python implementation that seems to be able to crank out ~60000 numbers in 10seconds. I am factorizing numbers using the pollard rho algorithm and using the Rabin miller primality test.

```
from Queue import Queue
import random

def gcd ( a , b ):
    while b != 0: a, b = b, a % b
    return a

def rabin_miller(p):
    if(p<2): return False
    if(p!=2 and p%2==0): return False
    s=p-1
    while(s%2==0): s>>=1
    for _ in xrange(10):
        a=random.randrange(p-1)+1
        temp=s
        mod=pow(a,temp,p)
        while(temp!=p-1 and mod!=1 and mod!=p-1):
            mod=(mod*mod)%p
            temp=temp*2
        if(mod!=p-1 and temp%2==0): return False
    return True

def pollard_rho(n):
    if(n%2==0): return 2;
    x=random.randrange(2,1000000)
    c=random.randrange(2,1000000)
    y=x
    d=1
    while(d==1):
        x=(x*x+c)%n
        y=(y*y+c)%n
        y=(y*y+c)%n
        d=gcd(x-y,n)
        if(d==n): break;
    return d;

def primeFactorization(n):
    if n <= 0: raise ValueError("Fucked up input, n <= 0")
    elif n == 1: return []
    queue = Queue()
    factors=[]
    queue.put(n)
    while(not queue.empty()):
        l=queue.get()
        if(rabin_miller(l)):
            factors.append(l)
            continue
        d=pollard_rho(l)
        if(d==l):queue.put(l)
        else:
            queue.put(d)
            queue.put(l/d)
    return factors

def phi(n):

    if rabin_miller(n): return n-1
    phi = n
    for p in set(primeFactorization(n)):
        phi -= (phi/p)
    return phi

if __name__ == '__main__':

  n = 1
  s = 0

  while n < 60000:
    n += 1
    s += phi(n)
  print(s)

```

# Answer
> 2 votes
# Matlab: 1464 = 26355867/ 18000

I can't test your code so I divided by 18000 as it represents the fastest computer of those who tested. I came to the score using this property:

* if p is prime, phi(p) = p - 1 (for p \< 10^20)

I mostly like that it is a one liner:

```
sum(primes(500000000)-1)

```

# Answer
> 2 votes
φ(2n) = 2n − 1
Σ φ(2i) = 2i − 1 for i from 1 to n

First, something to find times:

```
import os
from time import perf_counter

SEARCH_LOWER = -1
SEARCH_HIGHER = 1

def integer_binary_search(start, lower=None, upper=None, big_jump=1):
    if lower is not None and lower == upper:
        raise StopIteration # ?

    result = yield start

    if result == SEARCH_LOWER:
        if lower is None:
            yield from integer_binary_search(
                start=start - big_jump,
                lower=None,
                upper=start - 1,
                big_jump=big_jump * 2)
        else:
            yield from integer_binary_search(
                start=(lower + start) // 2,
                lower=lower,
                upper=start - 1)
    elif result == SEARCH_HIGHER:
        if upper is None:
            yield from integer_binary_search(
                start=start + big_jump,
                lower=start + 1,
                upper=None,
                big_jump=big_jump * 2)
        else:
            yield from integer_binary_search(
                start=(start + upper) // 2,
                lower=start + 1,
                upper=upper)
    else:
        raise ValueError('Expected SEARCH_LOWER or SEARCH_HIGHER.')

search = integer_binary_search(start=1000, lower=1, upper=None, big_jump=2500)
n = search.send(None)

while True:
    print('Trying with %d iterations.' % (n,))

    os.spawnlp(
        os.P_WAIT,
        'g++', 'g++', '-Wall', '-Wextra', '-pedantic', '-O0', '-o', 'reference',
        '-DITERATIONS=%d' % (n,),
        'reference.cpp')

    start = perf_counter()
    os.spawnl(os.P_WAIT, './reference', './reference')
    end = perf_counter()
    t = end - start

    if t >= 10.1:
        n = search.send(SEARCH_LOWER)
    elif t <= 9.9:
        n = search.send(SEARCH_HIGHER)
    else:
        print('%d iterations in %f seconds!' % (n, t))
        break

```

For the reference code, for me, that’s:

> Trying with 14593 iterations.
> 64724364
> 14593 iterations in 9.987747 seconds!

Now, Haskell:

```
import System.Environment (getArgs)

phiSum :: Integer -> Integer
phiSum n = 2 ^ n - 1

main :: IO ()
main = getArgs >>= print . phiSum . (2^) . read . head

```

It makes something with 2525224 digits in 0.718 seconds. And now I’m just noticing @Howard’s comment.

# Answer
> 1 votes
# Python 2.7: 10.999 (165975/15090)

# Pypy 2.3.1: 28.496 (430000/15090)

Some interesting methods I use:

**Rabin-Miller Strong Pseudoprime Test** \- A primality test that provides an efficient probabilistic algorithm for determining if a given number is prime

**Euler's product formula** \- The product is over the distinct prime numbers dividing n

**Code:**

```
import math
import random

#perform a Modular exponentiation
def modular_pow(base, exponent, modulus):
    result=1
    while exponent>0:
        if exponent%2==1:
           result=(result * base)%modulus
        exponent=exponent>>1
        base=(base * base)%modulus
    return result

#Miller-Rabin primality test
def checkMillerRabin(n,k):
    if n==2: return True
    if n==1 or n%2==0: return False

    #find s and d, with d odd
    s=0
    d=n-1
    while(d%2==0):
        d/=2
        s+=1
    assert (2**s*d==n-1)

    #witness loop
    composite=1
    for i in xrange(k):
        a=random.randint(2,n-1)
        x=modular_pow(a,d,n)
        if x==1 or x==n-1: continue
        for j in xrange(s-1):
            composite=1
            x=modular_pow(x,2,n)
            if x==1: return False #is composite
            if x==n-1:
                composite=0
                break
        if composite==1:
            return False        #is composite
    return True                 #is probably prime

def findPrimes(n):              #generate a list of primes, using the sieve of eratosthenes

    primes=(n+2)*[True]

    for i in range(2,int(math.sqrt(n))+1):
        if primes[i]==True:
            for j in range(i**2,n+1,i):
                primes[j]=False

    primes=[i for i in range(2,len(primes)-1) if primes[i]==True]
    return primes

def primeFactorization(n,primes):   #find the factors of a number

    factors=[]

    i=0
    while(n!=1):
        if(n%primes[i]==0):
            factors.append(primes[i])
            n/=primes[i]
        else:
            i+=1

    return factors

def phi(n,primes):
    #some useful properties
    if (checkMillerRabin(n,10)==True):      #fast prime check
        return n-1

    factors=primeFactorization(n,primes)    #prime factors
    distinctive_prime_factors=set(factors)

    totient=n
    for f in distinctive_prime_factors:     #phi = n * sum (1 - 1/p), p is a distinctive prime factor
        totient*=(1-1.0/f);

    return totient

if __name__ == '__main__':

    s=0
    N=165975
    # N=430000
    primes=findPrimes(N)    #upper bound for the number of primes
    for i in xrange(1,N):
        s+=phi(i,primes)

    print "Sum =",s

```

---
Tags: math, number-theory, fastest-code
---


title: Solve Einstein's riddle

text:
# Question
Title: Solve Einstein's riddle
Einstein wrote a riddle. He said that 98% of the world could not solve it.

I solved this riddle in about 25 minutes while on the train to work. It's basically just deduction.

# The riddle

> There are 5 houses in 5 different colors in a row.
> In each house lives a person with a different nationality.
> The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet.
> No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.
> **Question:** *Who owns the fish?*

To solve this riddle Einstein provides 15 hints:

1. The Brit lives in the red house.
2. The Swede keeps dogs as pets.
3. The Dane drinks tea.
4. The green house is on the immediate left of the white house.
5. The green house's owner drinks coffee.
6. The owner who smokes Pall Mall rears birds.
7. The owner of the yellow house smokes Dunhill.
8. The owner living in the center house drinks milk.
9. The Norwegian lives in the first house.
10. The owner who smokes Blends lives next to the one who keeps cats.
11. The owner who keeps the horse lives next to the one who smokes Dunhill.
12. The owner who smokes Bluemasters drinks beer.
13. The German smokes Prince.
14. The Norwegian lives next to the blue house.
15. The owner who smokes Blends lives next to the one who drinks water.

With these hints you can come to a solution.

Your task: Make a program that will solve this riddle for you. Hard coding the solution isn't allowed (duh)

It is allowed to hardcode the hints in any format.
**Example format:**

```
//Hints in order
(Nationality:Brit)==(Color:Red)
(Nationality:Swede)==(Pet:Dogs)
(Nationality:Dane)==(Drink: Tea)
(Color:Green)/(Color:White)
(Color:Green)==(Drink:Coffee)
(Smoke:PallMall)==(Pet:Birds)
(Color:Yellow)==(Smoke:Dunhill)
(House:3)==(Drink:Milk)
(Nationality:Norwegian)==(House:1)
(Smoke:Blend)/\(Pet:Cats)

```

> == means equals to
> / means on left side of
> \ means on right side of
> /\ means left or right of

Like I said its allowed to either hardcode hints or have them as input.

Output: Output should be in the following format (With the correct values, just saying for the trolls ;) )

```
 _____________    _____________    _____________    _____________    _____________
|   Number    |  |   Number    |  |   Number    |  |   Number    |  |   Number    |
| Nationality |  | Nationality |  | Nationality |  | Nationality |  | Nationality |
|    Color    |  |    Color    |  |    Color    |  |    Color    |  |    Color    |
|    Drink    |  |    Drink    |  |    Drink    |  |    Drink    |  |    Drink    |
|    Smoke    |  |    Smoke    |  |    Smoke    |  |    Smoke    |  |    Smoke    |
|     Pet     |  |     Pet     |  |     Pet     |  |     Pet     |  |     Pet     |
---------------  ---------------  ---------------  ---------------  ---------------

The <Nationality> in the <Color> house owns the fish!

```

Ascii art boxes can be changed by you, as long as they are boxes, doesn't matter what symbols you use.

Any knowledge on this riddle and solution can *not* be used in the program. It should use pure logic and deduction to solve the riddle.

Tagged this as a codegolf but might be a code challenge, not sure. Any thoughts on winning criteria for a code challenge feel free to share :)

For now this is code-golf so the program with the lowest bytecount wins.

Good luck and Happy coding :)

# Answer
# Prolog - 954 Characters

```
m(A,Z):-member(A,Z).
e:-e(Z),w(Z).
e(Z):-Z=[[1,A,F,K,P,U],[2,B,G,L,Q,V],[3,C,H,M,R,W],[4,D,I,N,S,X],[5,E,J,O,T,Y]],m([_,b,r,_,_,_],Z),m([_,s,_,d,_,_],Z),m([_,d,_,_,t,_],Z),m([WH,_,w,_,_,_],Z),m([GH,_,g,_,_,_],Z),GH=:=WH-1,m([_,_,g,_,c,_],Z),m([_,_,_,b,_,p],Z),m([_,_,y,_,_,d],Z),m([3,_,_,_,m,_],Z),m([1,n,_,_,_,_],Z),m([BH,_,_,_,_,b],Z),m([CH,_,_,c,_,_],Z),(BH=:=CH+1;BH=:=CH-1),m([DH,_,_,_,_,d],Z),m([HH,_,_,h,_,_],Z),(HH=:=DH+1;HH=:=DH-1),m([_,_,_,_,b,l],Z),m([_,g,_,_,_,r],Z),m([NH,n,_,_,_,_],Z),m([YH,_,b,_,_,_],Z),(NH=:=YH+1;NH=:=YH-1),m([SH,_,_,_,_,b],Z),m([XH,_,_,_,w,_],Z),(SH=:=XH+1;SH=:=XH-1),p([n,d,b,g,s],[A,B,C,D,E]),p([y,b,r,g,w],[F,G,H,I,J]),p([c,h,b,f,d],[K,L,M,N,O]),p([w,t,m,c,b],[P,Q,R,S,T]),p([d,b,p,r,l],[U,V,W,X,Y]).
t(X,[X|R],R).
t(X,[F|R],[F|S]):-t(X,R,S).
p([W|X],Y):-p(X,V),t(W,Y,V).
p([],[]).
b:-write('+--+--+--+--+--+--+'),nl.
z(A):-writef('|%2L|%2L|%2L|%2L|%2L|%2L|',A),nl.
w([A,B,C,D,E]):-b,z(A),z(B),z(C),z(D),z(E),b.

```

**Output**

```
+--+--+--+--+--+--+
|1 |n |y |c |w |d |
|2 |d |b |h |t |b |
|3 |b |r |b |m |p |
|4 |g |g |f |c |r |
|5 |s |w |d |b |l |
+--+--+--+--+--+--+

```

Key:

* First column is house number;
* Second column is nationality;
* Third column is favorite color;
* Fourth column is pet;
* Fifth column is drink; and
* Sixth column is cigarette (r = prince, l = bluemaster).
> 24 votes

# Answer
# Ruby 322 + input 442

**Brute force** search of nearly **25 billion** possible answers.
My computer would take about **75 days** to run this program.
I never verified if this program prints a correct answer!

Run as `ruby riddle.rb < riddle.in`

*riddle.rb* (332 bytes)

```
g=readlines
v=g.shift(5).map &:split
c,*d=v.map{|a|[*a.permutation]}
c.product(*d){|a|(f=eval a.map{|b|b.each_with_index.map{|s,i|"#{s}=#{i}\n"}.join}.join+'g.map{|h|eval h}.all?&&fish')&&(r=['-----------']*5
puts [r,[*0..4],*a,r].map{|s|s.map{|t|'|%11s|'%t}.join},"The #{a[0][f]} in the #{a[1][f]} house owns the fish!")}

```

*riddle.in* (442 bytes)

```
brit dane german norwegian swede
blue green red white yellow
beer coffee milk tea water
blends bluemasters dunhill pall_mall prince
birds cats dogs fish horse
brit==red
swede==dogs
dane==tea
green==white-1
green==coffee
pall_mall==birds
yellow==dunhill
2==milk
norwegian==0
blends==cats-1||blends==cats+1
horse==dunhill-1||horse==dunhill+1
bluemasters==beer
german==prince
norwegian==blue-1||norwegian==blue+1
blends==water-1||blends==water+1

```

The input file must contain 5 lines of names, followed by lines of logical expressions. House numbers are 0 to 4. There must be a `fish`.

The program calls `Array#permutation` five times to find all ways to order the arrays of nationalities, colors, drinks, smokes and pets. The long loop is `c.product(*d){|a|...}`, calling `Array#product` to iterate nearly 25 billion possible answers. The loop body has the form `(f=eval ...)&&(...)`. The `eval ...` part evaluates the logical expressions. If all are true, then `f` is the house number of the fish and the `&&(...)` part prints the answer. House number 0 is true in Ruby.

Code golf means not adding code for speed! But I lack **75 days** to run the program!
> 5 votes

# Answer
## Prolog, 653 characters

```
a([],L,L).
a([H|T],L2,[H|L3]):-a(T,L2,L3).
m(X,L):-a(_,[X|_],L).
r(X,Y,L):-a(_,[X,Y|_],L).
n(X,Y,L):-r(X,Y,L);r(Y,X,L).
s:-s(S),w(S).
s(S):-length(S,5),m([b,r,_,_,_],S),m([s,_,_,_,d],S),m([d,_,t,_,_],S),r([_,g,_,_,_],[_,w,_,_,_],S),m([_,g,c,_,_],S),m([_,_,_,p,b],S),m([_,y,_,d,_],S),S=[_,_,[_,_,m,_,_],_,_],S=[[n,_,_,_,_],_,_,_,_],n([_,_,_,b,_],[_,_,_,_,c],S),n([_,_,_,d,_],[_,_,_,_,h],S),m([_,_,b,l,_],S),m([g,_,_,r,_],S),n([n,_,_,_,_],[_,b,_,_,_],S),n([_,_,_,b,_],[_,_,w,_,_],S),m([_,_,_,_,f],S).
b:-write('----------------+'),nl.
z(Y,A):-write(Y),writef('|%2L|%2L|%2L|%2L|%2L|',A),nl.
w([S1,S2,S3,S4,S5]):-b,z(1,S1),z(2,S2),z(3,S3),z(4,S4),z(5,S5),b.

```
> 4 votes

# Answer
# Smalltalk 1332 chars

**Using plain Smalltalk:**

```
|n c v g p t r|n:=#(Brit Swede Dane Norwegian German
Red Green White Yellow Blue
Tea Coffee Milk Beer Water
PallMall Dunhill Blends Bluemasters Prince
Dogs Birds Cats Horses Fish).
v:=Dictionary new.n do:[:n|v at:n put:nil].g:=n splitForSize:5.
c:={{[:b :r|b==r].#Brit.#Red}.{[:s :d|s==d].#Swede.#Dogs}.{[:d :t|d==t].#Dane.#Tea}.
{[:g :w|g==(w-1)].#Green.#White}.{[:g :c|g==c].#Green.#Coffee}.
{[:p :b|p==b].#PallMall.#Birds}.{[:y :d|y==d].#Yellow.#Dunhill}.
{[:m|m==3].#Milk}.{[:n|n==1].#Norwegian}.{[:b :c|(b-c)abs==1].#Blends.#Cats}.
{[:h :d|(h-d)abs==1].#Horses.#Dunhill}.{[:m :b|m==b].#Bluemasters.#Beer}.
{[:g :p|g==p].#German.#Prince}.{[:n :b|(n-b)abs==1].#Norwegian.#Blue}.
{[:b :w|(b-w)abs==1].#Blends.#Water}}.
t:=[:c|x:=(c from:2collect:[:n|v at:n]).(x includes:nil)or:[c first valueWithArguments:x]].
p:=[|f|(((''-'',* 16),'' ''),*5)printCR.g do:[:n||w|w:=n collect:[:n|v at:n].w sortWith:n.
n do:[:n|''|''print.(n centerPaddedTo:14)print.''| ''print].''''printCR.].(((''-'',* 16),'' ''),*5)printCR.
f:=v at:#Fish.(''The %1 in the %2 house owns the fish''bindWith:(g first detect:[:n|(v at:n)==f])with:((g at:2) detect:[:n|(v at:n)==f]))printCR].
r:=[:gi|gi==0ifTrue:p ifFalse:[#(1 2 3 4 5)permutationsDo:[:perm|v declareAll:(g at:gi)from:perm.
(c conform:t)ifTrue:[r value:gi-1]].v declareAll:(g at:gi)from:#(nil),*5]].
r value:g size.

```

Output:

```
---------------- ---------------- ---------------- ---------------- ----------------
|  Norwegian   | |     Dane     | |     Brit     | |    German    | |    Swede     |
|    Yellow    | |     Blue     | |     Red      | |    Green     | |    White     |
|    Water     | |     Tea      | |     Milk     | |    Coffee    | |     Beer     |
|   Dunhill    | |    Blends    | |   PallMall   | |    Prince    | | Bluemasters  |
|     Cats     | |    Horses    | |    Birds     | |     Fish     | |     Dogs     |
---------------- ---------------- ---------------- ---------------- ----------------
The German in the Green house owns the fish

```

As the golfed version is almost unreadable, here is the developer's code with proper names, indentation and spaces for readability:

```
|names constraints foundSolution v groups printSolution testC test try|

names := #(Brit Swede Dane Norwegian German
 Red Green White Yellow Blue
 Tea Coffee Milk Beer Water
 PallMall Dunhill Blends Bluemasters Prince
 Dogs Birds Cats Horses Fish).

v := Dictionary new.
names do:[:n | v at:n put:nil].
groups := names splitForSize:5.

constraints := {
        {[:b :r | b==r] . #Brit . #Red   }.          "/ The Brit lives in the red house.
        {[:s :d | s==d] . #Swede . #Dogs }.          "/ The Swede keeps dogs as pets.
        {[:d :t | d==t] . #Dane . #Tea   }.          "/ The Dane drinks tea.
        {[:g :w | g==(w-1)] . #Green . #White }.     "/ The green house is on the immediate left of the white house.
        {[:g :c | g==c] . #Green . #Coffee}.         "/ The green house's owner drinks coffee.
        {[:p :b | p==b] . #PallMall . #Birds}.       "/ The owner who smokes Pall Mall rears birds.
        {[:y :d | y==d] . #Yellow . #Dunhill}.       "/ The owner of the yellow house smokes Dunhill.
        {[:m | m==3] . #Milk}.                       "/ The owner living in the center house drinks milk.
        {[:n | n==1] . #Norwegian }.                 "/ The Norwegian lives in the first house.
        {[:b :c | (b-c)abs==1] . #Blends . #Cats}.   "/ The owner who smokes Blends lives next to the one who keeps cats.
        {[:h :d | (h-d)abs==1] . #Horses . #Dunhill}."/ The owner who keeps the horse lives next to the one who smokes Dunhill.
        {[:m :b | m==b] . #Bluemasters . #Beer}.     "/ The owner who smokes Bluemasters drinks beer.
        {[:g :p | g==p] . #German . #Prince}.        "/ The German smokes Prince.
        {[:n :b | (n-b)abs==1] . #Norwegian . #Blue}."/ The Norwegian lives next to the blue house.
        {[:b :w | (b-w)abs==1] . #Blends . #Water}.  "/ The owner who smokes Blends lives next to the one who drinks water.
}.
testC := [:c | vi:=((c from:2) collect:[:n|v at:n]). (vi includes:nil) or:[c first valueWithArguments:vi]].
test := [constraints conform:testC].

printSolution :=
 [  |f|
    ((('-',* 16),' '),*5) printCR.
    groups do:[:names|
         |values|
         values := names collect:[:nm|v at:nm].
         values sortWith:names.
         names do:[:n| '|'print. (n centerPaddedTo:14)print.'| ' print].
         '' printCR.
    ].
    ((('-',* 16),' '),*5) printCR.
    f := v at:#Fish.
    ('The %1 in the %2 house owns the fish'
        bindWith:((groups at:1) detect:[:n|(v at:n)==f])
        with:((groups at:2) detect:[:n|(v at:n)==f]))printCR
 ].

try := [:gi |
    gi == 0
     ifTrue: printSolution
     ifFalse:[
        (1 to:5) asArray permutationsDo:[:perm |
            v declareAll:(groups at:gi) from:perm.
            test value ifTrue:[
                try value:(gi-1).
            ].
        ].
        v declareAll:(groups at:gi) from:#(nil nil nil nil nil).
    ].
].
try value:groups size.

```

**Using a constraint solver library:**

Using a constraint solver library, which is very similar to the one described in the OZ/Mozart manual. As I expect you will complain this being not valid for the contest ;-), it is added for your amusement and inspiration only (look for a contraint package in your language), ungolfed, and not counting chars.

```
|solution|

solution := Solver
    anySolutionFor:[
        |Brit Swede Dane Norwegian German
         Red Green White Yellow Blue
         PallMall Dunhill Prince Blends Bluemasters
         Tea Coffee Water Beer Milk
         Dogs Birds Cats Horses Fish|

        Brit        := (1 %% 5) name:#Brit.
        Swede       := (1 %% 5) name:#Swede.
        Dane        := (1 %% 5) name:#Dane.
        Norwegian   := (1 %% 5) name:#Norwegian.
        German      := (1 %% 5) name:#German.

        Red     := (1 %% 5) name:#Red.
        Green   := (1 %% 5) name:#Green.
        White   := (1 %% 5) name:#White.
        Yellow  := (1 %% 5) name:#Yellow.
        Blue    := (1 %% 5) name:#Blue.

        PallMall     := (1 %% 5) name:#PallMall.
        Dunhill      := (1 %% 5) name:#Dunhill.
        Prince       := (1 %% 5) name:#Prince.
        Blends       := (1 %% 5) name:#Blends.
        Bluemasters  := (1 %% 5) name:#Bluemasters.

        Tea    := (1 %% 5) name:#Tea.
        Coffee := (1 %% 5) name:#Coffee.
        Milk   := (1 %% 5) name:#Milk.
        Water  := (1 %% 5) name:#Water.
        Beer   := (1 %% 5) name:#Beer.

        Dogs         := (1 %% 5) name:#Dogs.
        Birds        := (1 %% 5) name:#Birds.
        Cats         := (1 %% 5) name:#Cats.
        Horses       := (1 %% 5) name:#Horses.
        Fish         := (1 %% 5) name:#Fish.

        Solver allDistinct:{ Brit . Swede . Dane . Norwegian . German. }.
        Solver allDistinct:{ Red. Green. White. Yellow. Blue. }.
        Solver allDistinct:{ PallMall. Dunhill. Prince. Blends. Bluemasters. }.
        Solver allDistinct:{ Tea. Coffee. Milk. Water. Beer }.
        Solver allDistinct:{ Dogs. Birds. Cats. Horses. Fish. }.

        Brit       =: Red.           "/ The Brit lives in the red house.
        Swede      =: Dogs.          "/ The Swede keeps dogs as pets.
        Dane       =: Tea.           "/ The Dane drinks tea.
        Green =: (White - 1).        "/ The green house is on the immediate left of the white house.
        Green =: Coffee.             "/ The green house's owner drinks coffee.
        PallMall   =: Birds.         "/ The owner who smokes Pall Mall rears birds.
        Yellow =: Dunhill.           "/ The owner of the yellow house smokes Dunhill.
        Milk =: 3.                   "/ The owner living in the center house drinks milk.
        Norwegian =: 1.              "/ The Norwegian lives in the first house.
        (Blends - Cats) abs =: 1.    "/ The owner who smokes Blends lives next to the one who keeps cats.
        (Horses - Dunhill) abs =: 1. "/ The owner who keeps the horse lives next to the one who smokes Dunhill.
        Bluemasters =: Beer.         "/ The owner who smokes Bluemasters drinks beer.
        German =: Prince.            "/ The German smokes Prince.
        (Norwegian - Blue) abs =: 1. "/ The Norwegian lives next to the blue house.
        (Blends - Water) abs =: 1.   "/ The owner who smokes Blends lives next to the one who drinks water.
    ].

solution printCR.

```

Notice the "=:" operator, which means "unify with". The solver uses a backtracking algorithm on the set of constraints defined in the problem block. The remaining code prints the solution into boxes:

```
    |pLine pSorted f |

    pLine := [
        (1 to:5) do:[:i | ('-' ,* 15) print] separatedBy:[' ' print].
        '' printCR.
    ].
    pSorted := [:keys |
        |items t|

        items := keys collect:[:k| solution at:k].
        t := keys copy. items values sortWith:t.
        pLine value:(t collect:[:x | '| ',(x centerPaddedTo:11),' |']).
    ].

    pLine value.
    pSorted value:#( Brit Swede Dane Norwegian German ).
    pSorted value:#( Red Green White Yellow Blue ).
    pSorted value:#( Tea Coffee Milk Water Beer ).
    pSorted value:#( PallMall Dunhill Prince Blends Bluemasters ).
    pSorted value:#( Dogs Birds Cats Horses Fish ).
    pLine value.

    f := solution at:'Fish'.
    ('The %1 in the %2 house owns the fish!'
        bindWith:(#( Brit Swede Dane Norwegian German ) detect:[:n| (solution at:n) == f])
        with:(#( Red Green White Yellow Blue ) detect:[:n| (solution at:n) == f])
            ) printCR.

```

Output:

```
Solution(Brit->3 Swede->5 Dane->2 Norwegian->1 German->4 Red->3 Green->4
 White->5 Yellow->1 Blue->2 PallMall->3 Dunhill->1 Prince->4 Blends->2
 Bluemasters->5 Tea->2 Coffee->4 Milk->3 Water->1 Beer->5 Dogs->5 Birds->3
 Cats->1 Horses->2 Fish->4)
--------------- --------------- --------------- --------------- ---------------
|  Norwegian  | |    Dane     | |    Brit     | |   German    | |    Swede    |
|   Yellow    | |    Blue     | |     Red     | |    Green    | |    White    |
|    Water    | |     Tea     | |    Milk     | |   Coffee    | |    Beer     |
|   Dunhill   | |   Blends    | |  PallMall   | |   Prince    | | Bluemasters |
|    Cats     | |   Horses    | |    Birds    | |    Fish     | |    Dogs     |
--------------- --------------- --------------- --------------- ---------------
The German in the Green house owns the fish!

```

Edit: oops - I forgot to print the "who owns the fish" line in the plain version.
> 3 votes

# Answer
# Ruby 1166 characters

*Edit: Updated for correct output format*

Runs consistently in under 0.2 seconds on a MBP i5.

**Source: View On Github**

One-liner:

```
def q(a);a.permutation;end;def z(a,b,c,d);l(a,b,c,d)||l(c,d,a,b);end;def l(a,b,c,d);(0..4).any?{|i|a[i]==b&&c[i+1]==d};end;def i(a,b,c,d);(0..4).any?{|i|a[i]==b&&c[i]==d};end;def t(i);['White','Yellow','Blue','Red','Green','German','Swede','Brit','Norwegian','Dane','Birds','Cats','Horses','Fish','Dogs','Beer','Water','Tea','Milk','Coffee','Blends','PallMall','Prince','Bluemasters','Dunhill'][i];end;def y(s);l=13-s.length;'|'+' '*(l/2.0).floor+s+' '*(l/2.0).ceil+'|';end;def d(s);b=[' '+(0..4).map{'_'*13}.join(' '*4)];u='  ';b<<[1,2,3,4,5].map{|i|y(i.to_s)}.join(u);s.each{|i|b<<i.map{|j|y(t(j))}.join(u)};b<<(0..4).map{'-'*15}.join(u);b<<'';z=s[4].index(13);b<<"The #{t s[0][z]} in the #{t s[1][z]} house owns the fish!";b.join "\n";end;q([0,1,2,3,4]).each{|c|l(c,4,c,0)||next;q([5,6,7,8,9]).each{|n|i(n,7,c,3)||next;n[0]==8||next;z(n,8,c,2)||next;q([10,11,12,13,14]).each{|a|i(n,6,a,14)||next;q([15,16,17,18,19]).each{|d|d[2]==18||next;i(c,4,d,19)||next;i(n,9,d,17)||next;q([20,21,22,23,24]).each{|s|z(a,12,s,24)||next;i(s,21,a,10)||next;z(s,20,d,16)||next;z(s,20,a,11)||next;i(n,5,s,22)||next;i(c,1,s,24)||next;i(s,23,d,15)||next;puts d([n,c,d,s,a]);exit}}}}}

```

Padded with newlines to fit the page:

```
def q(a);a.permutation;end;def z(a,b,c,d);l(a,b,c,d)||l(c,d,a,b);end
def l(a,b,c,d);(0..4).any?{|i|a[i]==b&&c[i+1]==d};end;def i(a,b,c,d);
(0..4).any?{|i|a[i]==b&&c[i]==d};end;def t(i);['White','Yellow','Blue',
'Red','Green','German','Swede','Brit','Norwegian','Dane','Birds',
'Cats','Horses','Fish','Dogs','Beer','Water','Tea','Milk','Coffee',
'Blends','PallMall','Prince','Bluemasters','Dunhill'][i];end;def y(s);
l=13-s.length;'|'+' '*(l/2.0).floor+s+' '*(l/2.0).ceil+'|';end;
def d(s);b=[' '+(0..4).map{'_'*13}.join(' '*4)];u='  ';
b<<[1,2,3,4,5].map{|i|y(i.to_s)}.join(u);s.each{|i|b<<i.map{|j|
y(t(j))}.join(u)};b<<(0..4).map{'-'*15}.join(u);b<<'';
z=s[4].index(13);
b<<"The #{t s[0][z]} in the #{t s[1][z]} house owns the fish!";
b.join "\n";end;q([0,1,2,3,4]).each{|c|l(c,4,c,0)||next;
q([5,6,7,8,9]).each{|n|i(n,7,c,3)||next;n[0]==8||next;z(n,8,c,2)||next;
q([10,11,12,13,14]).each{|a|i(n,6,a,14)||next;
q([15,16,17,18,19]).each{|d|d[2]==18||next;i(c,4,d,19)||next;
i(n,9,d,17)||next;q([20,21,22,23,24]).each{|s|z(a,12,s,24)||next;
i(s,21,a,10)||next;z(s,20,d,16)||next;z(s,20,a,11)||next;i(n,5,s,22)||next;
i(c,1,s,24)||next;i(s,23,d,15)||next;puts d([n,c,d,s,a]);exit}}}}}

```

Outputs:

```
 _____________    _____________    _____________    _____________    _____________
|      1      |  |      2      |  |      3      |  |      4      |  |      5      |
|  Norwegian  |  |    Dane     |  |    Brit     |  |   German    |  |    Swede    |
|   Yellow    |  |    Blue     |  |     Red     |  |    Green    |  |    White    |
|    Water    |  |     Tea     |  |    Milk     |  |   Coffee    |  |    Beer     |
|   Dunhill   |  |   Blends    |  |  PallMall   |  |   Prince    |  | Bluemasters |
|    Cats     |  |   Horses    |  |    Birds    |  |    Fish     |  |    Dogs     |
---------------  ---------------  ---------------  ---------------  ---------------

The German in the Green house owns the fish!

```

## Ungolfed Code

```
@colors        = [:white, :yellow, :blue, :red, :green].shuffle.permutation
@cigars        = [:blends, :pall_mall, :prince, :bluemasters, :dunhill].shuffle.permutation
@nationalities = [:german, :swedish, :british, :norwegian, :danish,].shuffle.permutation
@drinks        = [:beer, :water, :tea, :milk, :coffee].shuffle.permutation
@pets          = [:birds, :cats, :horses, :fish, :dogs].shuffle.permutation

def next_to?(set_a, val_a, set_b, val_b)
  left_of?(set_a, val_a, set_b, val_b) ||
  left_of?(set_b, val_b, set_a, val_a)
end

def left_of?(set_a, val_a, set_b, val_b)
  (0..4).any? do |i|
    set_a[i]   == val_a &&
    set_b[i+1] == val_b
  end
end

def implies?(set_a, val_a, set_b, val_b)
  (0..4).any? do |i|
    set_a[i] == val_a &&
    set_b[i] == val_b
  end
end

def solve
  i = 0
  @colors.each do |colors|
    i += 1
    next unless left_of?(colors, :green, colors, :white)
    @nationalities.each do |nationalities|
      i += 1
      next unless implies?(nationalities, :british, colors, :red)
      next unless nationalities[0] == :norwegian
      next unless next_to?(nationalities, :norwegian, colors, :blue)
      @pets.each do |pets|
        i += 1
        next unless implies?(nationalities, :swedish, pets, :dogs)
        @drinks.each do |drinks|
          i += 1
          next unless drinks[2] == :milk
          next unless implies?(colors, :green, drinks, :coffee)
          next unless implies?(nationalities, :danish, drinks, :tea)
          @cigars.each do |cigars|
            i += 1
            next unless next_to?(pets, :horses, cigars, :dunhill)
            next unless implies?(cigars, :pall_mall, pets, :birds)
            next unless next_to?(cigars, :blends, drinks, :water)
            next unless next_to?(cigars, :blends, pets, :cats)
            next unless implies?(nationalities , :german, cigars, :prince)
            next unless implies?(colors, :yellow, cigars, :dunhill)
            next unless implies?(cigars, :bluemasters,  drinks, :beer)
            return [colors, nationalities, pets, drinks, cigars], i
          end
        end
      end
    end
  end
end

class Symbol
  def humanize
    result = self.to_s
    result.gsub!('_', ' ')
    result.split(' ').collect{|part| part.capitalize }.join(' ')
  end
end

solution, attempts = solve

puts "\nSolved in #{attempts} attempts.\n\n"

for i in (0..4)
  number, color, nationality, cigar, drink, pet = i+1, solution[0][i], solution[1][i].humanize, solution[4][i].humanize, solution[3][i], solution[2][i]
  puts "House #{number} is #{color}. The owner is #{nationality}, smokes #{cigar}, drinks #{drink}, and keeps #{pet}."
end

puts "\n"

```

Outputs:

```
Solved in 37663 attempts.

House 1 is yellow. The owner is Norwegian, smokes Dunhill, drinks water, and keeps cats.
House 2 is blue. The owner is Danish, smokes Blends, drinks tea, and keeps horses.
House 3 is red. The owner is British, smokes Pall Mall, drinks milk, and keeps birds.
House 4 is green. The owner is German, smokes Prince, drinks coffee, and keeps fish.
House 5 is white. The owner is Swedish, smokes Bluemasters, drinks beer, and keeps dogs.

```

The use of `shuffle` in the initial setup ensures unique solution paths every time. You can see this by the number of attempts altering between runs. This mitigates the need to feed in the input separately, though altering the code to do so would be trivial.
> 3 votes

---
Tags: code-golf
---


title: Detect Duplicate Questions

text:
# Question
Title: Detect Duplicate Questions
# Detect Duplicate Questions

Once upon a time, there was a golfing site. It had a problem: people would post similar or identical questions again and again. You have been ~~chosen selected forced conscripted blackmailed~~ requested to automate the process of deciding whether a question is a duplicate of an existing one, by whatever means necessary (see Rules).

## Input

Your program must accept a single URL as input. It may assume that this leads to a question on codegolf.stackexchange.com.

## Output

Search the site for similar questions. If you think that the input question is a duplicate of an existing question (or vice versa), output the other question's URL. You may output multiple URLs, separated by new lines. At the end of your output, output `end` (on a separate line).

## Scoring

* If a question that you output was indeed marked as a duplicate of the input question (or vice versa), you score 4 points. This is a "correct guess".
* For each false positive (aka "incorrect guess"), you lose 2 points.
* For each question that was actually a duplicate but does not appear in your output (aka "missing guess"), lose 1 point.

The highest score after handling 32 input questions wins. These 32 questions are a "round". At the beginning of each round, the scores will be reset to 0. One round will be run every few days, and the leaderboard updated after each round.

## Rules

* If questions A and C are both closed as duplicates of B, A will count as a duplicate of C and vice versa.
* At the start of each round, your program may not possess any data about any questions (i.e. **no hardcoding**), except on how to parse the website.
* However, you may keep data in external files during a round.
* No data may be kept between rounds.
* Your output must have a trailing new line.
* **You may not use any data from the website except search results and the URL, title, tags and text of a question**, with or without formatting. For example, you may not use the text "marked as duplicate by foo, bar..." that appears on duplicate questions.
* You may retrieve this data directly from the site, via data.SE or via the API.
* **Each submission must have a name.**
* Each submission must have clear version numbering.
* **If a submission does not produce output after a time limit (to be decided; please state how long your submission takes) it will be killed and lose 8 points.**

# Answer
> 4 votes
# Python 3

I am giving this entry the name `The Differ`.

Code:

```
import urllib.request, gzip, re, json, difflib, sys
API_URL = "https://api.stackexchange.com/"
qurl = input()
qid = int(re.search("\d+",qurl).group(0))
def request(url,wrapper=False,**params):
    params.setdefault("filter","withbody")
    params.setdefault("site","codegolf")
    url = API_URL + url + "?"+"&".join([str(k)+"="+str(v) for k,v in params.items()])
    compressed_response = urllib.request.urlopen(url)
    response = gzip.decompress(compressed_response.read()).decode("utf8")
    response_object = json.loads(response)
    if wrapper:
        return response_object
    else:
        return response_object["items"]
question = request("questions/%s"%qurl)[0]
tags = ";".join(question["tags"])
title = question["title"]
escaped = title.replace(" ","%20")
related = request("similar",title=escaped,pagesize=100)
hasmore = False
length = sys.maxsize
for tag in question["tags"]:
    result = request("search",tagged=tag,
                     wrapper=True,
                     filter="!-*f(6rc.cI8O",
                     pagesize=100)
    if result["total"] < length:
        length = result["total"]
        related.extend(result["items"])
        hasmore = result["has_more"]
        besttag = tag
related.extend(best)
if length < 1500:
    for page in itertools.count(2):
        if not hasmore:
            break
        response = request("search",
                           tagged=besttag,
                           page=page,
                           pagesize=100,
                           filter="!-*f(6rc.cI8O",
                           wrapper=True)
        hasmore = response["has_more"]
        related.extend(result["items"])
matcher = difflib.SequenceMatcher(None, question["body"], None)
titlematcher = difflib.SequenceMatcher(None, question["title"], None)
seen = set()
seen.add(question["question_id"])
for possible in related:
    matcher.set_seq2(possible["body"])
    titlematcher.set_seq2(possible["title"])
    score = matcher.ratio()+titlematcher.ratio()
    qid = possible["question_id"]
    if score > .85 and qid not in seen:
        print(qid)
        seen.add(qid)
print("end")

```

The filter `"!-*f(6rc.cI8O"` included the `total` parameter on the global wrapper object and the `body` parameter on questions.

This entry makes two API requests plus one per tag on the question plus one per hundred questions in its least used tag. If it hits an api throttle (which it doesn't check for), it will raise an `urllib.error.HTTPError: HTTP Error 400: Bad Request`

---
Tags: code-challenge, natural-language, stack-exchange-api
---