title: Caesar-Cypher-Mania

text:
# Question
Title: Caesar-Cypher-Mania
The Caesar Cypher is a very simple substitution cypher where each letter is shifted by a fixed offset (looping around Z to A). Similarly, we can also a Caesar cypher for the set of printable ASCII characters. These are the 95 characters from code points 0x20 to 0x7E. For a given offset `d`, we map the code point `C` to

```
(C - 32 + d) % 95 + 32

```

which shifts all characters by a `d` and loops around from `~` to space. Characters outside this range (control characters like newlines, tabs, and characters outside the ASCII range) are unaffected.

You're to write two programs or functions (potentially in different languages), which take an offset `d` and a string. The first program should return or print the Caesar cypher of the input. The second program should return or print the *inverse* Caesar cypher (i.e. using offset `-d`). You may take input via STDIN, command-line argument or function argument.

To make things more interesting, the second program must be a Caesar cypher of the first program. That is, if you pass the source code of the first program to itself, for some non-zero offset `d`, the output has to be the second program.

Both programs, as well as the input strings, must contain only printable ASCII characters, newlines and tabs. Neither program may contain any comments or read its own source code, file name or process ID directly or indirectly.

This is code golf, so the shortest answer (in bytes) wins. Since both programs must have the same size, you only need to count it once.

# Answer
> 13 votes
# Cjam, ~~40 38~~ 37 bytes

Forward Cypher:

```
 q~'~),32>_@m<er "o|%|'*10<]>k<cpZ"_-

```

Inverse Cypher:

```
"s!)!+.54@aBo>gt"$q~'~),32>_@m>er\$a/

```

and the second program is the cypher of first one with difference of `2`

---

**How it works**

I came up with this answer on pure luck while testing things out.

First, the Cypher parts:

```
q~'~),32>_@m<er
q~                 "Take the input and evaluate it";
  `~)              "Get the next character after the printable ASCII range";
     ,32>          "Get all printable ASCII characters":
         _@        "Copy the printable ASCII string and bring the cypher difference"
                   "on top of stack";
           m<      "Forward rotate the copy of printable ASCII string by difference";
                   "In case of inverse Cypher, this is m> to reverse rotate the string";
             er    "Transliterate to complete the forward/inverse Cypher";

```

Now comes the explanation of the tricky part.

Key transformations are

```
<space> -> "     // Empty space to string conversion
Z -> \           // Character Z in an useless string to swap operation
_ -> a           // Copy operation to wrapping in an array
- -> /           // Set subtraction to string splitting

```

So the first program is

```
 q~'~),32>_@m<er "o|%|'*10<]>k<cpZ"_-
 q~'~),32>_@m<er                          "no-op space, Forward cypher, no-op space";
                 "o|%|'*10<]>k<cpZ"       "Useless String (Actually not)";
                                   _      "Copy it and ..."
                                    -     "remove all alphabets of copy from original";

```

And the second program is

```
"s!)!+.54@aBo>gt"$q~'~),32>_@m>er\$a/
"s!)!+.54@aBo>gt"                       "Cypher of first part of first program"
                                        "with difference of 2";
                 $q~'~),32>_@m>er\$a/   "Cypher of the useless string of first program";
                                        "with difference 2";
                 $                      "Sort the first program's main part's cypher";
                  q~'~),32>_@m>er       "Program to reverse cypher";
                                 \$     "Swap the cypher to the top of stack and sort it";
                                   a    "Wrap it in array";
                                    /   "Split the output string on an array, which";
                                        "always returns the output in an array as there";
                                        "are no occurrences of an array in a string";

```

---

Input is like `"<escaped string to be cyphered>" <difference>`

For example:

```
"abcd" 4

```

and output of the first program is

```
efgh

```

and of the second program is

```
]^_`

```

Try it online here

# Answer
> 7 votes
# Python 2, 147

Clearly I didn't think too hard about this one, as it would be futile in Python. There are simply two seperate programs, with the unused one encased in a string.

The offset between the two programs is 39.

## Forward

Defines the function Z accepting a Unicode string and an offset.

```
Z=lambda s,d:s.translate({i+32:(i+d)%95+32for i in range(95)})or u''and Z
"uE:F;=:XLd=rLfMK:GLE:M>`TBckjr`Be=a]qmckj?HKXBXBGXK:G@>`qmaVaHKXN__:G=X"

```

## Inverse

Defines the function I accepting a Unicode string and an offset.

```
"d4)5*,)G;S,a;U<:)6;4)<-OC1RZYaO1R,PL`\RZY.7:G1G16G:)6/-O`\PEP7:G=NN)6,G"
I=lambda s,d:s.translate({i+32:(i-d)%95+32for i in range(95)})or u''and I

```

# Answer
> 5 votes
# Ruby, ~~131~~ 125 bytes

Here is my own submission (which I had written earlier as a proof of concept, but I managed to violate my own rules somehow). I'm not reusing any code between the two submissions (I want you guys to beat this, after all), but instead it consists of two lines, one of which is turned into a string with gibberish.

**Forward cypher:**

```
Y=->d,s{s.chars{|c|x=c.ord;$><<(x<32?x:(x-32+d)%95+32).chr}};Y
"tdu<cKSKe;@9JKST;TPt;eGJ<r[uss_PsjivPq_Pdjid<`\plbji`e;@JUUr"

```

**Inverse cypher:**

```
"eUf-T<D<V,1*;<DE,EAe,V8;-cLfddPAd[ZgAbPAU[ZS-QMa]S[ZQV,1;FFc"
J=->d,s{s.chars{|c|x=c.ord;$><<(x<32?x:(x-32-d)%95+32).chr}};J

```

Both snippets define a function (called `Y` in the first one, and `J` in the second one), which takes an integer and a string and prints the transformed string to STDOUT. The offset between the two pieces of code is `40`.

# Answer
> 5 votes
# Python 3 - 248 bytes

My goal was to do this as a Python one-liner. Goal success, but now I can't be bothered golfing.

Encrypt:

```
r=q="".__doc__[2];eval("p"+q+"int(''.join([c,ch"+q+"((o"+q+"d(c)-32+d)%95+32)][31<o"+q+"d(c)<127]fo"+q+" d in[int(input())]fo"+q+" c in input()))")or'\^UZ`smmyV[UZsGOwOT^ss[^PsOtx~}xPtp%!v~}tIG~|([^PsOt(|}$IR[^kPkUZGUZ`sUZ\a`sttIR[^kOkUZkUZ\a`sttt'

```

Decrypt:

```
'Q&Q66Bssx$wssoFqOy+u!<6%6?&?6}#)<;;B~$}#<ow@w|6?&?6<<$6?&?6x<w=AGF?x=9MI?GF=qoGEP$6?&?6x<w=PEFKqz$6?&?64x4}#o}#)<}#%*)<==qz$6?&?64w4}#4}#%*)<===6=$';print("".join([c,chr((ord(c)-32-d)%95+32)][31<ord(c)<127]for d in[int(input())]for c in input()));

```

*Edit: Fixed to not affect chars outside the printable ASCII range*

Offset from encrypt to decrypt is 20. Use by inputting the offset first, then the string, e.g.

```
5
hello

```

## Explanation

The following transformations are the key:

```
r -> '
' -> ;

```

The first allows the use of `or`, while the second ignores a string by semicolons.

Note that `"".__doc__[2]` returns the string `r` (taken from `str`). This is necessary to prevent the single quoted string in the decryption program from having stray quotes in the middle.

# Answer
> 4 votes
# oOo CODE, 750 744 bytes, all code used in both programs

Too long but it's probably the right tool doing that...

Encrypt:

```
CcCcccccccccCcYcccCCCccCcCcCccccccCcCcccccCcCcccCcCccCccCcCCccccCcCccccCCcCccccCCccCccCcCCcccCCCcCccccCcCCcCCcCCcCcCcCccccCCccCccCccCccCccCccCccCccccccCCCcCccCccCCcCcCcccCCcCcccCcCCcCCcCcCCccCCcCCcCCcCCcCCcCCcCCcCCcCCcCCcCcccccccCccccCccccCCccccCCcCccCCcccCccccccccccCcCccCccCccCccCcCCccCCcccCcCcCccCCcccCCCcCcccccccccccccCCccCccCcCcCcccCCccccccccccCcCccccccCcCccccCCcCccCccCCcCccccccccccCCccCcCcCcccccCcCccCcCCCcCccCccCCcCccCccCccCcCcccccCcCcccCCCcCcCccccCcCccCCcCCcCCcCcCCcccCcCCcCCcCCcCCcCCcCCcCCcCCcCCcCcCcccCccCCcccccCcCcccCcccccCcccCcccCccCccCCcCcccccccccccccCCCcccCcCcCcccCcccCCCcCccCccCccCcCCccCccCcCCCcCccccCcCccccccccCcCccCccCcCCccccccCccccccccCcccCCccCccCccCCcCCcCCcCCcCcCcCcccccCcCCcCCcCCcCCcCCcCCcCCcCccCcCCcccCCccCcCcccCCcccCCCcCC

```

Decrypt:

```
SsSsssssssssSsisssSSSssSsSsSssssssSsSsssssSsSsssSsSssSssSsSSssssSsSssssSSsSssssSSssSssSsSSsssSSSsSssssSsSSsSSsSSsSsSsSssssSSssSssSssSssSssSssSssSssssssSSSsSssSssSSsSsSsssSSsSsssSsSSsSSsSsSSssSSsSSsSSsSSsSSsSSsSSsSSsSSsSSsSsssssssSssssSssssSSssssSSsSssSSsssSssssssssssSsSssSssSssSssSsSSssSSsssSsSsSssSSsssSSSsSsssssssssssssSSssSssSsSsSsssSSssssssssssSsSssssssSsSssssSSsSssSssSSsSssssssssssSSssSsSsSsssssSsSssSsSSSsSssSssSSsSssSssSssSsSsssssSsSsssSSSsSsSssssSsSssSSsSSsSSsSsSSsssSsSSsSSsSSsSSsSSsSSsSSsSSsSSsSsSsssSssSSsssssSsSsssSsssssSsssSsssSssSssSSsSsssssssssssssSSSsssSsSsSsssSsssSSSsSssSssSssSsSSssSssSsSSSsSssssSsSssssssssSsSssSssSsSSssssssSssssssssSsssSSssSssSssSSsSSsSSsSSsSsSsSsssssSsSSsSSsSSsSSsSSsSSsSSsSssSsSSsssSSssSsSsssSSsssSSSsSS

```

Brainfuck translations:

```
+>>>+>,<[->[->+>+<<]>[-<+>]<<]>,[>++++[-<-------->]+<<+[<+>+++]<++++++++++>>[>-<-<+<-[>>>+<<<<]<-[+<-]+>>>>]<<[-]>>>[->[-<+<<+>>>]<[->+<]+<<+<<<[>[-]+[>+<+++]>++++++++++[<<->+>->-[<<<+>>>>]-[+>-]+<<<]<<]+>[->>+<<]>>->>-]<<<++++[->++++++++<]>.[-]>,]
+>>>->,<[->[->+>+<<]>[-<+>]<<]>,[>++++[-<-------->]+<<+[<+>+++]<++++++++++>>[>-<-<+<-[>>>+<<<<]<-[+<-]+>>>>]<<[-]>>>[->[-<+<<+>>>]<[->+<]+<<+<<<[>[-]+[>+<+++]>++++++++++[<<->+>->-[<<<+>>>>]-[+>-]+<<<]<<]+>[->>+<<]>>->>-]<<<++++[->++++++++<]>.[-]>,]

```

oOo CODE is a Brainfuck variant where only the case of letters matters.

It take the first byte and use its character code as `d` (so a newline means d=10). The rest of input is the string. EOF is 0.

# Answer
> 4 votes
# GolfScript, 95 64 bytes, all code used in both programs

Encrypt:

```
0 0z{ 1)'[}??)9t:z21,--/; [84;%zt*84*84$|)21*|$Z!!\~'---|}`{)}%~

```

Decrypt:

```
1!1{|!2*(\~@@*:u;{32-..0<!\95<&{u+95+95%}*32+}%[""] (...}~a|*~&

```

Input format:

```
1 "0 0z{ 1)'[}??)9t:z21,--/; [84;%zt*84*84$|)21*|$Z!!\~'---|}`{)}%~"

```

### Explanation

Decrypt:

```
1!1                            # Push 0 1.
{                              # Define a block and evaluate it.
    |                          # Or.
    !2*(                       # Get 1 for encryption, or -1 for decryption.
    \~                         # Evaluate the input string.
    @@*:u;                     # u = d for encryption, or -d for decryption.
    {                          # For each character:
        32-                    # Subtract 32.
        ..0<!\95<&             # Test if it is in the printable range.
        {u+95+95%}*            # If so, add u (mod 95).
        32+                    # Add 32 back.
    }%
    [""] (...                  # Push an empty array and 4 empty strings.
}~
a                              # No-op.
|*~                            # Evaluate ""*(""|"") which does nothing.
&                              # Calculate []&"" which is empty.

```

Encrypt:

```
0 0                            # Push 0 0.
z                              # No-op.
{                              # Define a block and get its string representation.
    ...                        # See decryption code.
    |                          # This will be decoded into a }. The string will be truncated here when evaluated.
}`                             # Only the closing } will be truncated, but it is still used as the end of the block.
{)}%                           # Increment each character. Note that the braces before and after the block will also be incremented.
~                              # Evaluate the string.

```

# Answer
> 3 votes
# Javascript (ES7 Draft) - 167 165 bytes

Borrowing from @feersum 's use of strings and @MartinButtner 's use of semicolon ;)

**Encrypt:**

```
J=(s,d)=>s.replace(/[ -~]/g,x=>String.fromCharCode((x.charCodeAt()-32+d)%95+32));J
"eP<T-Qef<V;.95*,.PW$HUG&W0TAef{=;270V/;86k1*;k8-.PPAV,1*;k8-.i=PQS^[U-QMa]S[ZQQc"

```

**Decrypt:**

```
"t_Kc<`tuKeJ=HD9;=_f3WdV5f?cPtu+LJAF?e>JGEz@9JzG<=__Pe;@9JzG<=xL_`djib<`\plbji``r"
Y=(s,d)=>s.replace(/[ -~]/g,x=>String.fromCharCode((x.charCodeAt()+63-d)%95+32));Y

```

**Offset to use:** 55

# Answer
> 2 votes
# \>\<\> (Fish), 467 bytes

Encrypt:

```
ffii{{~~__:0a('0'*!.0a('0'*22(!'(~$~_:}-}$-a*}+{{if~~:i:0({}?;__:{}84{}*__({}?\__:{} _{}70{}g_{})_{}?\4__{}8*-_{}+{}80{}g_%4_{}8*{}+\\sl||||||||||||||||||||||||||||9||||||||||||||9||||||||||||||||||||||||||||||||||||||||||||||||||||9
                                                                              >                      >                              >!;7f7-_{}!%_{}!<872-d_{}!&_{}!<[755(7(%~~_{}!<[55(7(_{}!*!*23a(_{}!'_{}!"55(7((~~_{}~~~o__'4'0.{{{o,

```

Decrypt:

```
iill~~""bb=3d+*3*-$13d+*3*-55+$*+"'"b=!0!'0d-!.~~li""=l=3+~!B>bb=~!;7~!-bb+~!B_bb=~!#b~!:3~!jb~!,b~!B_7bb~!;-0b~!.~!;3~!jb(7b~!;-~!.__vo                            <              <                                                    <
##############################################################################A######################A##############################A$>:i:0b~!$(b~!$?;:50gb~!$)b~!$?^:88+:+(""b~!$?^88+:+b~!$-$-56d+b~!$*b~!$%88+:++""b~!"""rbb*7*31~~~r/

```

The two programs are offset by 3, and they take input of the form:

```
<2-digit offset> <text>

```

The offset *must* be 2 digits, so an offset of 5 needs to be entered as `05`.

This is a long submission, but **nearly all non-filler chars are used by both programs**. There's a lot of whitespace that can definitely be golfed out, but I thought the program would be more interesting this way.

This image highlights the chars used by both programs.

## Explanation

The main construct that makes this possible is `_{} -> b~!`, which allows arbitrary skipping of chars in the decryption program. How?

```
Encrypt:
  _ : Mirror, but is a no-op if the program flow is horizontal
  { : Shift stack left
  } : Shift stack right

Decrypt:
  b : Push 11 to stack
  ~ : Pop top of stack
  ! : Skip the next instruction

```

All in all, the encryption program does nothing, but the decryption program skips the next instruction. This can then be extended to `_{}! -> b~!$`, which allows arbitrary skipping of chars in the *encryption* program instead.

Aside from this, most of the rest of the program is pushing numbers, performing operations on those numbers then finding ways to pop them. For example, one useful construct is `~~ -> ""`, which pops two values for the encryption program, but pushes nothing in the decryption program.

---

# \>\<\>, 149 bytes

Here's the less interesting version, which uses the fact that instructions not passed through are effectively comments in 2D languages.

Encrypt:

```
i68*:@-a*i@@-+i~v
4:v?)g31:;?(0:i:/8
(?v48*-+03g%48*+\*
_~\of0.   .1+1fo/
j*+:zq<6B99A6=qz6g
53Ji?C58/8;?r0?C5:
C?EiJ4r?<EFJ3;EtEg
:tAC5EK8l5tKK86t*i

```

Decrypt:

```
^+-~/5"V~^55" ^sk
)/k4}\(&/04|%/^/$-
|4k)-~" %(\y)-~ Q~
TsQd[%#ttt#& &[d$
_~ /of1+7..6+2fo+\
*(?^48*-$-04g%48*/
84:^?)g41:;?(0:i:\
/i68*:@-a*i@@-+i~^

```

The two programs are offset by 84, and take input the same way as above. The first instruction decides which half of the program to execute, with `i` (input) maintaining program flow rightward in the encryption program, and `^` redirecting program flow upward (looping around and coming back from the bottom) in the decryption program.

## Explanation

For the relevant half of the encryption program (decryption program is similar):

```
i                       read first input digit as char
68*:@-a*                subtract 48 (ASCII "0") and multiply by 10, keeping another 48 on the stack
i                       read second input digit as char
@@-+                    subtract 48 and add to 10*(first digit), giving the offset
i~                      read in space and discard it

--- LOOP ---
:                       copy the offset
i:                      read input char
:0)?;                   check if less than 0 (i.e. EOF) and terminate if so
:13g)?v                 check if greater than ~ in cell (1,3) and drop down if so
48*(?v                  check if less than 32 and drop down if so
48*-+03g%48*+           calculate Caesar shift of the char, fetching 95 from (0,3)

of1+1.                  repeat loop
of0.                    repeat loop

```

---

## Coding tool

*This isn't related to the rest of the post above, but I thought I'd post this because I need to use it :P*

```
for(var i=0;i<95;++i){var option=document.createElement("option");option.text=i;document.getElementById("offset").add(option)};function update(m){if(m==1)var code=document.getElementById("in").value;else var code=document.getElementById("out").value;var offset=parseInt(document.getElementById("offset").value);var output="";for(var i=0;i<code.length;i++){var n=code[i].charCodeAt(0);if(n<32||n>127)output+=code[i];else{var c=(n-32+offset*m)%95;output+=String.fromCharCode(c<0?c+95+32:c+32)}}if(m==1)document.getElementById("out").value=output;else document.getElementById("in").value=output};
```

```
<html><body><textarea id="in" onkeyup="update(1)" rows=5 style="width:100%"></textarea><textarea id="out" rows=5 style="width:100%" onkeyup="update(-1)"></textarea><select id="offset" onchange="update(1)"></select></body></html>
```

# Answer
> 1 votes
# Perl - 131

It takes input from command line args.

```
We;{for(split//,$ARGV[1]){print chr(((ord$_)-32+$ARGV[0])%95+32)}};q!LUXmYVROZttqi'8-<AvCnaVXOTZeINXmmmUXJiEnrxwri'8-<AuCnj~zpxwnc!

```

Shifting it by 26 gives the other one:

```
q U6!*-B.+'$/IIF>[lapuKwC6+-$)/:}#-BBB*-~>yCGMLE>[lapuJwC?SOEMLC88U,;for(split//,$ARGV[1]){print chr(((ord$_)-32-$ARGV[0])%95+32)};

```

---
Tags: code-golf, string, source-layout
---


# Question
Title: Recover the mutated source code (for robbers)
**This is the companion thread to the main Recover the mutated source code (link) challenge.** If you have successfully cracked a cop's answer, post your solution as an answer to this question.

As a reminder, here are the robber rules from the main challenge again:

> The robber will attempt to change the cop's program (which completes Task #1) into a program that completes Task #2 (not necessarily the original program written by the cop) in the edit distance specified by the cop.
>
> An already-cracked submission cannot be cracked again (only the first robber who cracks a submission gets credit).
>
> After cracking a submission, please do the following:
>
> * **Post an answer** to this challenge's accompanying question (link), providing the language, your solution, and a link to the original answer.
> * **Leave a comment** with the text "Cracked" that links to your posted answer.
> * **Edit the cop's answer** if you have edit privileges (if you do not, either wait until someone else with the required privileges does so for you or suggest an edit).

And scoring:

> If a robber successfully cracks a cop's submission, the robber's score goes up by the edit distance of that submission. For example, a robber that cracks a submission with an edit distance of 3 and one with a distance of 5 earns 8 points. The robber with the highest score wins. In the event of a tie, the robber who earned the score first wins.

# Leaderboard

There are no cracked submissions yet.

# Answer
> 3 votes
# Python 2, FryAmTheEggman

```
x=n=1;j=input();
while j>2:
    x,n=n,x+n;j-=1;
    ##while~-all(n%i for i in range(2,n)):n+=1;
print n

```

Used 12 edits. Put in an extra `#` to make it 13.

# Answer
> 3 votes
# Python 2, Sp3000

```
from fractions import*
n=input()
k,=P=[1]
while n>len(P):k+=1;z=reduce(lambda x,y:x+y,P[~1:]);P+=[z]#*(gcd(z,k)<2)
print P[-1]

```

# Answer
> 3 votes
# J, grc

```
   f=:3 :'{.+/(!|.)i.y'

   f 45
1134903170

```

# Answer
> 2 votes
# Python 3, Sp3000

```
x=n= int(input())       # 3
P = [1,1]               #+2 = 5
k = 2
while n >=len(P):       #+1 = 6
 k += 1
 for x in P:
  if k%x ==~0: break    #+1 = 7
 else: P += [P[-2]+x]   #+7 = 14
print(x)

```

# Answer
> 1 votes
# Python 3, matsjoyce

```
a,c,n=1,1,int(input())
while n-1:
 #c+=1
 ##########list(map(c.__mod__,range(2,46))).count(0):
 a,c=a+c,a
 n-=1
print(c)

```

The Fibonacci program was strangely already in there...only needed 5 edits to get it.

# Answer
> 1 votes
# JAGL, globby

```
T~2]d]2C{cSdc+c]}wSP

```

It might not be the most efficient approach, it it is almost definitely not the Cop's code, but it works, and its 12 away.

# Answer
> 1 votes
# CJam by Martin Büttner

```
T1l~({_2$+}*p];

```

Takes input `n` from STDIN

# Answer
> 1 votes
# Python 2, Pietu1998

```
f=lambda p,i:p if p[45:]else f(p+[i]#f all(i%q for q in p[1:])else
,p[-1]+i)
print f([1,1,1],2)[input('!')]

```

I used 9 edits to get a Fibonacci program.

# Answer
> 1 votes
# Ruby, histocrat

```
p [x=1,y=1,*(1..200).map{|i|z=y;y+=(y*x**(i-1)+x%2).divmod(i)[2-1]?x:1;x=z;y}].-([x-1])[gets.to_i-1]

```

---
Tags: code-challenge, primes, cops-and-robbers, fibonacci, edit-distance
---


title: Draw A Snowflake

text:
# Question
Title: Draw A Snowflake
Joe lives at the Bahamas. It is winter. His children are disappointed that there is no snow. Joe needs to make snow for his children. Fortunately, he has a 3-d printer. He plans to make snowflakes with it. Unfortunately he has no idea how a snowflake would look like. In fact, he has never seen a snowflake! Let us help him by creating a program that automatically generates a 2d-image of a snowflake for him.

# Input

The diameter of the image(in pixels), the percentage of the image that is actually a snowflake.

# Output

An image of a snowflake with the required diameter. It can be saved to a file or displayed to the user.

# Specifications

Create a wedge that has a 30 degree angle. Create a Brownian Tree with initial seed at the point of the wedge. Reflect the wedge around the center of the image 12 times to generate the rest of the image. The snowflake has the color White. The background has the color Black.

# Scoring

Due to the fact there are different ways to generate a Brownian Tree, the score is 10 * number of upvotes - golf score.

Golf score is defined as the number of bytes in the program with the following bonuses:

-20% Can arbitrarily specify the symmetry of the snowflake.

-50% Can specify the shape of the snowflake. (By being able to specify the ratio of the lengths of the sides of the wedge.)

Highest score wins.

Here is a picture what the shape of the wedge would be with the ratio approximately 2:

Scoreboard:

Martin Buttner: 10 * 14 - 409 = -269

Nimi: 10 * 1 - 733 * .5 = -356.5

Optimizer: 10 * 5 - 648 = -598

The winner is Martin with score -269!

# Answer
> 16 votes
# Mathematica, 409 bytes

```
{n,p}=Input[];m=999;Clear@f;_~f~_=0;0~f~0=1;r=RandomInteger;For[i=0,i<m,++i,For[x=m;y=0,f[x+1,y]+f[x-1,y]+f[x,y+1]+f[x,y-1]<1,a=b=-m;While[x+a<0||y+b<0||(y+b)/(x+a)>Tan[Pi/6],a=-r@1;b=r@2-1];x+=a;y+=b];x~f~y=1];Graphics[{White,g=Point/@Join@@{c=Cases[Join@@Table[{i,j}-1,{i,m},{j,m}],{i_,j_}/;i~f~j>0],c.{{1,0},{0,-1}}},Array[Rotate[g,Pi#/3,{0,0}]&,6]},Background->Black,ImageSize->n*p,ImageMargins->n(1-p)/2]

```

Ungolfed:

```
{n,p}=Input[];
m = 999;
ClearAll@f;
_~f~_ = 0;
0~f~0 = 1;
r = RandomInteger;
For[i = 0, i < m, ++i,
  For[x = m; y = 0,
   f[x + 1, y] + f[x - 1, y] + f[x, y + 1] + f[x, y - 1] < 1,
   a = b = -m;
   While[x + a < 0 || y + b < 0 || (y + b)/(x + a) > Tan[Pi/6],
    a = -r@1;
    b = r@2 - 1
    ];
   x += a;
   y += b
   ];
  x~f~y = 1
  ];
Graphics[
 {White, g =
   Point /@
    Join @@ {c =
       Cases[Join @@ Table[{i, j} - 1, {i, m}, {j, m}], {i_, j_} /;
          i~f~j > 0], c.{{1, 0}, {0, -1}}},
  Array[Rotate[g, Pi #/3, {0, 0}] &, 6]},
 Background -> Black,
 ImageSize -> n*p,
 ImageMargins -> n (1 - p)/2
 ]

```

This expects input the form `{n,p}` where `n` is the image size in pixels, and `p` is the percentage of the image to be covered by the snowflake.

It takes something like half a minute to generate a snowflake with the given parameters. You can speed it up by changing the value of `m` from `999` to `99`, but then the result looks a bit sparse. Likewise, you can crank up the quality by using larger numbers, but then it'll take very long.

I'm forming the Brownian tree on an integer lattice, placing new particles at `{999, 0}`, and moving the randomly to the left and up or down (not to the right), until they hit the existing particles. I'm also constraining the motion to the wedge between 0 and 30 degrees. Finally, I reflect that wedge on the x-axis, and display it with its 5 rotations.

Here are some results (click for larger version):

And here are two animations of the Brownian tree growing (10 particles per wedge per frame):

# Answer
> 6 votes
# JavaScript, ES6, ~~799 740 695 658~~ 648

*I am only counting the two canvas tags and the function `f` from the snippet below as part of the byte count.* Rest of the stuff is for live demo

To watch it in action, just run the snippet below in a latest Firefox giving the size and ratio via the input boxes

*Note that you will have to hide the result then show again before a consecutive snowflake*

```
f=(N,P)=>{E.width=E.height=D.width=D.height=N
E.style.background="#000"
C=D.getContext("2d"),F=E.getContext("2d")
C.strokeStyle='#fff'
M=Math,r=M.random,I=0,n=N/2
C.beginPath()
C.rect(n,n,2,2)
C.fill()
B=_=>{x=n*P/100,y=0,w=[]
do{w.push([x,y])
do{X=2*((r()*2)|0)
Y=2*(((r()*3)|0)-1)
}while(x-X<0||y-Y<0||(y-Y)/(x-X)>.577)
x-=X,y-=Y}while(!C.isPointInPath(n+x,n+y))
I++
w=w.slice(-4)
x=w[0]
C.moveTo(x[0]+n,x[1]+n)
w.map(x=>C.lineTo(n+x[0],n+x[1]))
C.stroke()
E.width=E.height=N
for(i=0;i<12;i++){F.translate(n,n)
i||F.rotate(M.PI/6)
i-6?F.rotate(M.PI/3):F.scale(1,-1)
F.translate(-n,-n)
F.drawImage(D,0,0)}
I<(n*n*P*.22/100)&&setTimeout(B,15)}
B()}
```

```
<input placeholder="Input N" id=X /><input placeholder="Input percentage" id=Y /><button onclick="f(~~X.value,~~Y.value)">Create snowflake</button><br>
<canvas id=E><canvas id=D>
```

Here are a few example renders with different size and percentages. The best one is called **SkullFlake** (first in the list). Click the images to see them in full resolution.

A lot of help and input from Martin and githubphagocyte.

# Answer
> 1 votes
# Haskell, 781 733 Bytes

The program features the „specify the ratio of the lengths of the sides of the wedge“ option, so you have to call it with three command line arguments:

```
./sf 150 50 40

```

Argument #1 is the size of the image, #2 the % of pixels in the wedge and #3 the length (in %) of the shorter side of the wedge. The image is saved in a file called „o.png“.

150-50-40:

My program produces snowflakes with cut-off spikes, because new pixels start on the middle axis of the wedge (green dot, see below) and tend to stay there, because they move equally random to the left, up or down. As pixels outside the wedge are discarded, straight lines appear on the boundary of the wedge (green arrow). I was too lazy to try out other paths for the pixels.

150-50-40:

When the wedge is big enough (3rd argument 100) the spikes on the middle axis can grow and then there are 12 of them.

150-40-100:

Few pixels make round shapes (left: 150-5-20; right 150-20-90).

The program:

```
import System.Environment;import System.Random;import Graphics.GD
d=round;e=fromIntegral;h=concatMap;q=0.2588
j a(x,y)=[(x,y),(d$c*e x-s*e y,d$s*e x+c*e y)] where c=cos$pi/a;s=sin$pi/a
go s f w p@(x,y)((m,n):o)|x<1=go s f w(s,0)o|abs(e$y+n)>q*e x=go s f w p o|elem(x-m,y+n)f&&(v*z-z)*(b-q*z)-(-v*q*z-q*z)*(a-z)<0=p:go s(p:f)w(s,0)o|1<2=go s f w(x-m,y+n)o where z=e s;a=e x;b=e y;v=e w/100
main = do
 k<-getArgs;g<-getStdGen;let(s:p:w:_)=map read k
 i<-newImage(2*s,2*s);let t=h(j 3)$h(\(x,y)->[(x,y),(d$0.866*e x+0.5*e y,d$0.5*e x-0.866*e y)])$take(s*d(q*e s)*p`div`100)$go s[(0,0)]w(s,0)$map(\r->((1+r)`mod`2,r))(randomRs(-1,1)g)
 mapM(\(x,y)->setPixel(x+s,y+s)(rgb 255 255 255)i)((h(j(-3/2))t)++(h(j(3/2))t));savePngFile "o.png" i

```

# Answer
> 0 votes
# Processing 2 - 575 characters

Takes in a file f whose first line is the image size and the second is the flakes radius. Every time a new point is placed it is rotated around the center 12 times. This creates a very similar effect as a rotated wedge, but not exactly the same.

```
  int d,w,h,k,l,o,p,x,y;
  String n[] = loadStrings("f.txt");
  d=Integer.parseInt(n[0]);
  h=Integer.parseInt(n[1]);
  size(d,d);
  w=d/2;
  k=l=(int)random(d);
  background(0);
  loadPixels();
  o=p=0;
  pixels[w*w*2+w]=color(255);
  while(true)
  {
    o=k+(int)random(-2,2);
    p=l+(int)random(-2,2);
    if(p*d+o>d*d-1 || p*d+o<0 || o<0 || o>d){
      k=l=(int)random(d);
    }
    else
    {
      if(pixels[p*d+o]==color(255))
      {
        p=l-w;
        o=k-w;
        if(o*o+p*p>h*h){break;}
        float s,c;
        for(int j=0;j<12;j++)
        {
          s=sin(PI*j/6);
          c=cos(PI*j/6);
          x=(int)((o*c)-(p*s));
          y=(int)(((p*c)+(o*s)));
          pixels[(int)(d*y+x+w+(w*d))]=color(255);
        }
        k=l=(int)random(d);
      }
      else
      {
        k=o;
        l=p;
      }
    }
  }
  updatePixels();

```

you can get processing here

---
Tags: code-challenge, graphical-output, geometry
---


title: Magnetic Sculptures

text:
# Question
Title: Magnetic Sculptures
This is a loose continuation of my earlier challenge on constructing graphs.

# Background

An eccentric artist has hired you to estimate the structural integrity of his sculptures. He creates his works of art by taking a bunch of cube-shaped magnets, and dropping them one by one into a huge pile. To better analyze his method, we use the following two-dimensional model. We start with an empty floor, and drop a magnet `#` at any integer coordinate, say `0`:

```
       |
       v
       #
===============
       0

```

If another magnet is dropped at `0`, it ends up on top of the previous one:

```
       |
       v
       #
       #
===============
       0

```

Now, let us drop one more magnet at `0`, and then one at `1`:

```
        |
       #v
       ##
       #
===============
       0

```

As seen above, a falling magnet sticks to the *second* magnet it passes (the first one merely slows it down). The second magnet need not be directly below the first one, and a magnet on both sides still counts as one magnet:

```
      #   #
      ##|##
      # v #
      ### #
      #   #
===============
       0

```

The artists wants you to calculate the maximal vertical gap in the final sculpture, that is, the maximum number of empty spaces between two magnets on the same column, or a magnet and the ground below it. In the above picture, this number would be 3 (on column `2`).

# Input

A list of integers, representing the coordinates where the artist drops his magnets, read from left to right. You may assume that the coordinates satisfy `-1024 <= i < 1024` and that the length of the list is at most `1024`, if that helps.

# Output

The maximal vertical gap in the final sculpture. The empty sculpture has gap `-1`, and this case has to be included, since our sculptor is a dadaist.

# Additional rules

You may give a function or a full program. The shortest byte count wins, and standard loopholes are disallowed. Code with explanations is preferred.

# Test cases

```
[] -> -1
[0,2,1] -> 0
[0,0,0,0,0,1,-1] -> 3
[0,0,0,0,0,1,1,1,2] -> 4
[1,1,2,2,2,2,2,2,1] -> 2
[1,1,2,2,2,2,2,2,1,0,1,0] -> 2
[1,2,1,2,1,2,1,2,2,2,2,1,0] -> 3
[-1,-1,-1,1,1,1,0] -> 1
[-1,-1,-1,-1,2,2,1,1,2,2,2,1,0] -> 2
[-2,-2,-2,-1,-1,-1,0,0,0,1,1,1,2,2,2,3,3,4,4,5,5,5,6] -> 6

```

# Answer
# Dyalog APL, ~~73~~ 70 characters

~~`{y←⍬⋄⌈/¯1,,¯1-2-/0,x⊢⌸{y,←⌈/(1+y/⍨0=⍵),Y⊃⍨2⊃⍒Y←1 1,∪y/⍨1=⍵}¨|x-¯1↓¨,\x←⍵}`~~

`{y←⍬⋄¯1⌈⌈/,¯1-2-/¯1,⍵⊢⌸{y,←⌈/(1+y/⍨0=⍵),⊃1↓{⍵[⍒⍵]}∪y/⍨1=⍵}¨|⍵-¯1↓¨,\⍵}`

```
First statement:
       y←⍬  initialize semi-global variable y with an empty vector
Second statement, from right to left:
         ⍵  the vector of x coordinates
       ,\⍵  concat-scan: all prefixes of ⍵ of length 1, 2, ..., ≢⍵
   ¯1↓¨,\⍵  drop the last element of each prefix, lengths are 0, 1, ..., (≢⍵)-1
|⍵-¯1↓¨,\⍵  for each x: magnitudes of differences between x and its predecessors
 {...}¨...  execute the code in parens for each item of the argument
         ⍵  is now a single vector of differences from those described above
       1=⍵  boolean mask, where are our neighbouring xs?
    y/⍨1=⍵  select the ys corresponding to our neighbouring xs
   ∪y/⍨1=⍵  unique ys
   {⍵[⍒⍵]}  sort descending
       ⊃1↓  first of one-drop, i.e. get the second element if it exists, otherwise 0
       0=⍵  which previous xs are the same as our x?
  1+y/⍨0=⍵  select the corresponding ys and add 1 to them
        ⌈/  maximum of all the ys described so far
       y,←  append to the semi-global y
            the result from {} will be identical to y
  ⍵⊢⌸{...}  a matrix of ys, grouped in rows by x (which is now in ⍵) and zero-padded
       ¯1,  prepend ¯1 to the left of each row
       2-/  differences between consecutive horizontal elements, result is a matrix
       ¯1-  negative one minus each element of the matrix
         ,  ravel the matrix (linearize it to a vector)
        ⌈/  maximum; if the vector is empty, return ¯1.8e308, a very small number
     ¯1⌈⌈/  greater of ¯1 and the ⌈/  to avoid the very small number

```
> 1 votes

# Answer
# Haskell - 217 185 182 Bytes

```
import Data.List
r g n m|m==n=max(head(g m)+1)((reverse.(0:).nub.sort$g(m-1)++g(m+1))!!1):g m|1<3=g m
j x=(-1)-minimum(0:(map(foldl r(\_->[0])x)[-1024..1024]>>=(tail>>=zipWith(-))))

```

Usage:

```
j [1,2,1,2,1,2,1,2,2,2,2,1,0]

```

This function builds up another function that returns a list of magnet y-positions for a given x-position. With it, it calculates the gaps for all x-positions -1024 .. 1024 and takes the maximum (Edit: now I'm taking the minimum, because gaps are negative: the lower the number the larger the gap).
> 4 votes

# Answer
# Javascript, 201 193

```
F=P=>{m=[];for(p of P){s=2;c=m[p]=m[p]||[];for(i=1e4;~i&&s;i--){if((m[p-1]||[])[i]||(m[p+1]||[])[i])s--;if(c[i-1]) s=0}c[++i]=1}g=-1;m.map(c=>{ d=0;for(i in c){g=i-d>g?i-d:g;d=++i} });return g}

```

> F(\[1,1,2,2,2,2,2,2,1\]) === 2

Or readable version

```
F=P=>{
  m=[];  // magnet positions
  for(p of P){ // every dropped magnet
    s=2; // initial speed
    c=m[p]=m[p]||[]; // column where magnet is dropping
    for(i=1e4;~i&&s;i--){ // continue until at floor or zero speed
      if((m[p-1]||[])[i]||(m[p+1]||[])[i])s--;  // magnet on either side, decrease speed
      if(c[i-1]) s=0; // magnet is directly below
    }
    c[++i]=1;
  }
  g=-1; // maximum gap
  m.map(c=>{
          d=0;for(i in c){g=i-d>g?i-d:g;d=++i;}
       });
  return g;
};

```
> 3 votes

# Answer
## Python 2.7, 327

```
from itertools import *
s=input()
if s:m=min(s);l=[[] for _ in range(max(s)-m+3)]
for t in s:
    i=t-m+1;r=l[i];c=[x or y for x,y in izip_longest(l[i-1],l[i+1])][::-1][1:];j=len(c)-c.index(1)-1-len(r) if any(c) else 0;l[i]=r+[0]*j+[1]
print -1 if not s else max([len(list(q)) if b==0 else 0 for k in l for b,q in groupby(k)])

```

Before white space golfing, it looks like this:

```
from itertools import *
s=input()
if s:
    m=min(s)
    l=[[] for _ in range(max(s)-m+3)]
for t in s:
    i=t-m+1;r=l[i]
    c=[x or y for x,y in izip_longest(l[i-1],l[i+1])][::-1][1:]
    j=len(c)-c.index(1)-1-len(r) if any(c) else 0
    l[i]=r+[0]*j+[1]
print -1 if not s else max([len(list(q)) if b==0 else 0 for k in l for b,q in groupby(k)])

```

Here's an explanation of the more complex lines, mostly for my own benefit.

```
l=[[] for _ in range(max(s)-m+3)]

```

This constructs an array of empty lists of length max(drops)-min(drops)+1 plus a placeholder on either side. I always want to write \[ \[ \] \]\*K to construct an array of empty lists, but that makes K pointers to the same empty list.

```
c=[x or y for x,y in izip_longest(l[i-1],l[i+1])][::-1][1:]

```

The function izip\_longest from itertools is like zip, but infills the shorter list with None in order to zip the lists together. The slicing \[::-1\] reverses the list of 0's and 1's from the "or" comparison. The list is reversed in order to use the index method in the next line, which finds the first instance of an element. Since the last element of a nonempty column must be 1, this is the first element in the reversed list and is ignored via the slice \[1:\].

```
j=len(c)-c.index(1)-1-len(r) if any(c) else 0
l[i]=r+[0]*j+[1]

```

First calculate the difference between the length of column i and the position of the second 1 in the adjacent columns. If the difference is positive, add that many zeros to column i before adding a 1. Any nonpositive number times \[0\] is the empty list.

```
max([len(list(q)) if b==0 else 0 for k in l for b,q in groupby(k)])

```

The function groupby from itertools splits a list into subsequences of consecutive elements. This line finds the max of the lengths of all the subsequences of zeros in all of the columns. It's necessary to cast each subsequence q to a list, because groupby returns a generator (like all the itertools functions) which naturally doesn't support a len method.
> 2 votes

# Answer
# Java - 281 bytes

Pretty straight forward.

First it constructs the sculpture in an array

Then it finds the greatest gap.

```
int a(int[]b){
        int[][]d=new int[9999][9999];
        int g,r,t,y=-1;
        for(int c:b){
            c+=5000;
            g=0;
            for(r=9998;r>=0;r--){
                if(r==0||d[c][r-1]==1){d[c][r]=1;break;}
                if((d[c-1][r]==1||d[c+1][r]==1)&&++g==2){d[c][r]=1;break;}
            }
        }
        for(int[] k:d){
            t=0;
            for(int i:k){
                if(i==0)t++;
                else{if(t>y)y=t;t=0;}
            }
        }
        return y;
    }

```

small -

```
int a(int[]b){int[][]d=new int[9999][9999];int g,r,t,y=-1;for(int c:b){c+=5000;g=0;for(r=9998;r>=0;r--){if(r==0||d[c][r-1]==1){d[c][r]=1;break;}if((d[c-1][r]==1||d[c+1][r]==1)&&++g==2){d[c][r]=1;break;}}}for(int[] k:d){t=0;for(int i:k){if(i==0)t++;else{if(t>y)y=t;t=0;}}}return y;}

```
> 1 votes

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


title: Recover the mutated source code

text:
# Question
Title: Recover the mutated source code
In a very unusual accident involving a small sample of radium, an electrocuted whale, and three gummy bears, some of The Management™'s source code has been mutated. Little does The Management™'s boss know, it was actually the Cops© who had been responsible, in an attempt to thwart The Management™'s "evil" plans. So the Robbers® have been hired in an attempt to retrieve the original code, because who doesn't like being evil sometimes?

*note: This challenge was heavily inspired by Unscramble the Source Code.*

# Description

This is a challenge.

* The **cops** will write a program (the mutated code) that performs Task #1 (and also write a program that performs Task #2, but is kept secret).
* The **robbers** will attempt to reverse the "mutation" and change this original code into code that performs Task #2.

In this challenge, Task #1 will be to **output the `n`th prime number**, and Task #2 will be to **output the `n`th Fibonacci number** (which is somehow evil, according to the Cops© anyway). The Fibonacci sequence is defined as (`n=1``1`; `n=2``1`; `n=3``2`; ...), and the prime numbers are defined as (`n=1``2`; `n=2``3`; `n=3``5`; ...).

The cops' goal is to minimize the difference between the programs that complete Task #1 and Task #2, while preventing the robbers from recreating the code that completes Task #2.

# Cop Rules

The cops will write two programs (one that completes Task #1, and one that completes Task #2), and make the following information public:

* The **first program** (that outputs the `n`th prime number)
* The **Levenshtein edit distance** between the first program and the second program
* The **programming language** that both programs are written in (must be the same language for both programs)

The following restrictions apply to both programs:

* They must be 128 characters in length or less.
* They must only use printable ASCII (plus newlines, which are also allowed).
* They must take less than 10 seconds to run for `n=45`, and they are not required to produce the correct output for any `n>45`.
* They must not use any hashing or cryptographic functions.

# Robber Rules

The robber will attempt to change the cop's program (which completes Task #1) into a program that completes Task #2 (not necessarily the original program written by the cop) in the edit distance specified by the cop.

An already-cracked submission cannot be cracked again (only the first robber who cracks a submission gets credit).

After cracking a submission, please do the following:

* **Post an answer** to this challenge's accompanying question (link), providing the language, your solution, and a link to the original answer.
* **Leave a comment** with the text "Cracked" that links to your posted answer.
* **Edit the cop's answer** if you have edit privileges (if you do not, either wait until someone else with the required privileges does so for you or suggest an edit).

# Scoring

If a cop's program remains uncracked for 1 week, the cop can post the original code that completes Task #2 (in the specified edit distance), and the submission is from then on considered "safe." The safe submission that has the smallest edit distance will win. In the event of a tie, the shortest program (the original that completes Task #1) wins. If two submissions are still tied, the one posted earlier wins.

If a robber successfully cracks a cop's submission, the robber's score goes up by the edit distance of that submission. For example, a robber that cracks a submission with an edit distance of 3 and one with a distance of 5 earns 8 points. The robber with the highest score wins. In the event of a tie, the robber who earned the score first wins.

# Leaderboard

1. Ruby, 6 (histocrat)

# A small tool to compute the Levenshtein distance

```
var f=document.getElementById("f"),g=document.getElementById("s"); function h(){var a=f.value,e=g.value;if(128<a.length)a="<span style='color:red'>First program is too long!</span>";else if(128<e.length)a="<span style='color:red'>Second program is too long!</span>";else{if(0===a.length)a=e.length;else if(0===e.length)a=a.length;else{var d=[],b;for(b=0;b<=e.length;b++)d[b]=[b];var c;for(c=0;c<=a.length;c++)d[0][c]=c;for(b=1;b<=e.length;b++)for(c=1;c<=a.length;c++)d[b][c]=e.charAt(b-1)===a.charAt(c-1)?d[b-1][c-1]:Math.min(d[b-1][c-1]+1,Math.min(d[b][c-1]+1,d[b-1][c]+ 1));a=d[e.length][a.length]}a="Distance = <strong>"+a+"</strong>"}document.getElementById("d").innerHTML=a}f.onkeyup=h;g.onkeyup=h;
```

```
<h3 id=ft>First program</h3>
<textarea id=f rows=7 cols=80 style="width:100%"></textarea>
<h3 id=st>Second program</h3>
<textarea id=s rows=7 cols=80 style="width:100%"></textarea>
<p id=d></p>
```

# Answer
# Python 2, distance = 8 \[cracked\]

```
from fractions import*
n=input()
k,=P=[2]
while n>len(P):k+=1;z=reduce(lambda x,y:x*y,P,1);P+=[k]*(gcd(z,k)<2)
print P[-1]

```

Finally got this one under the char limit. Shouldn't be too hard, but I thought the idea was interesting.

---

**Intended solution:**

> `from fractions import*
>  n=input()
>  k,=P=[1]
>  while n>len(P):k+=1;z=reduce(lambda x,y:x+y,P[:-1],1);P+=[z]*(gcd(z,k)<2)
>  print P[-1]`

The idea was to use that `F(n+2) = 1 + (sum over F(k) from k = 1 to n)`, and the fact that consecutive Fibonacci numbers are coprime. The `1` in the reduce argument was supposed to provide the `+1`.

Looks like feersum found a different line of attack!
> 6 votes

# Answer
## J, distance = 5 \[Cracked\]

```
f=:3 :'{.p:|.i.y'

```

Usage:

```
> f 45
197

```
> 5 votes

# Answer
# Ruby, distance 6 \[safe\]

```
require'prime';p Prime.take(n=gets.to_i)[-1]
#p (((807462154311276410)**n/(5**0.5)).round)

```

Coming up with pairs of formulas with short edit distances is fun, but it seems like this approach might be more effective/annoying. You may understand exactly what I did, but that doesn't mean you can reverse it.

Solution:

> `require'prime';p=Prime.take(n=gets.to_i)[-1]
>  p (((0742154311276/4e10)**n/(5**0.5)).round)`

Explanation:

> The code generates the Golden Ratio to 11 decimal places and uses it to directly calculate the Fibbonaci sequence. It's just enough precision to get the required number of terms right. That part wasn't obfuscated at all, if you happen to know the formula. To make it harder to brute-force reverse my mutations and recover the constant, I used octal notation (the leading 0) and scientific notation (4e10). Dividing by 4e10 rather than 1e11 makes it look more like I'm dividing by something `.0` to force float division, when actually anything in scientific notation is for some reason always a Float in Ruby, even when a Bignum might seem to make more sense. I thought I was being clever with the `p=` stuff, but the way I wrote it you can just delete the `p`. I could've reduced the distance by 1 and forced the `p=` solution by using `p&&` instead of `#` on the second line, but I didn't think of it.
> 4 votes

# Answer
## Python 2 - LD = 13 Cracked

```
n=1;j=input();
while j>0:
    n+=1;j-=1;
    while~-all(n%i for i in range(2,n)):n+=1;
print n

```

A nice, easy (hopefully not *too* easy) one to start things off :)

Looks like it was too easy ;) I feel rather silly that I forgot you could use comments :/
> 3 votes

# Answer
# Haskell, distance = 13

```
import Data.List
x=id=<<snd(mapAccumL(\m n->(,)=<<(++m)$[n|and[n`mod`m1/=0|m1<-m]])[1+1][3..])
main=print.(!!)(0:2:x)=<<readLn

```

This could be more readable, but the `import` ate too many bytes, so I had to golf it a bit.
> 3 votes

# Answer
# Ruby, distance 14 (Cracked)

```
p [x=2,y=1,*(1..200).map{|i|y==(y*x**(i-1)+x%2).divmod(i)[x-1]?i:1}].-([x-1])[gets.to_i-1]

```
> 2 votes

# Answer
# CJam, distance 10 (Cracked)

```
1l~{{)_mp!}g}*

```

Just put `n` on STDIN. Test it here.

For reference, the original solution used the rare `j`.

**Original:**

> `T1]l~\{(_j\(j+}j`
> 2 votes

# Answer
# J, distance = 4 \[safe\]

```
f =: 3 :  '{. (p:) (+) / 0 , y - 1x'

```

Solution:

> f =: 3 : '{. 2(x:) (+%) / 0 , y $ 1x'

Method:

> Denominator `{. 2(x:)` of the continued fraction `(+%)` 1+1/(...(1+1/(1+1/(1+1/(1))))).
> 2 votes

# Answer
# Python 3, distance = 14 \[cracked\]

```
n = int(input())
P = [2]
k = 2
while n > len(P):
 k += 1
 for x in P:
  if k%x == 0: break
 else: P += [k]
print(k)

```

I had some spare chars so I put some whitespace in for clarity :)
> 1 votes

# Answer
# JAGL Alpha 1.2 - Distance = 16 \[Cracked\]

```
T~2S]{]S1{D[dmn}wDS}wSP

```

Shouldn't be too hard, We will see what happens...
> 1 votes

# Answer
# TI-BASIC, distance 38

```
Input N:{2>L1:For(A,3,E99:If min(1=gcd(A,seq(A,A,2,$(A:A>L1(1+dim(L1:End:L1(N

```

`>` represents the `STO→` key and `$` represents the square root symbol.
> 1 votes

# Answer
# Python 2 – distance = 12 \[Cracked\]

I'm kinda happy with how this turned out.

```
f=lambda p,i:p if p[45:]else f(p+[i]if all(i%q for q in p[1:])else p,-~i)
print f([1,2,3],2)[input()]

```

Let's see how long it takes... I assume it'll still be cracked.

**Edit:** shortened code a tiny bit, no effect on operation/distance.

## Intended solution

I tried to go for no comments or newline changes.

> `f=lambda p,i:p if p[45:]else f(p+[p[i]+p[-2]]if all(i|q for q in p[1:])else p,-~i)
>  print f([1,1,1],2)[input()]`
> 1 votes

# Answer
# Python 3 - Distance = 14 \[Cracked\]

---

```
a,c,n=1,2,int(input())
while n-1:
 c+=1
 while 1!=list(map(c.__mod__,range(2,46))).count(0):
  c,a=a+c,a
 n-=1
print(c)

```

We'll see how long this lasts...
> 0 votes

---
Tags: code-challenge, primes, cops-and-robbers, fibonacci, edit-distance
---


# Question
Title: Write a mathematical function whose result is "hello world"
Write a mathematical function that results in an integer representation of "hello world"

For example "hello world" in hex is `68656c6c6f20776f726c64` so the goal will be to write a mathematical program that results in a number representing "hello world".

Here is a example of a possible solution using python:

```
print(2*2*3*59*61*97*416510539*72330832279)==int("68656c6c6f20776f726c64", 16)

```

Any type of mathematical equations could be used, such as: powers, series, factorials, and other mathematical operations.

**The rules:**

* You may select your own way to encode/represent "hello world" as an integer. Hash functions are also allowed
* Mathematical libraries (e.g. numpy, GMP) are allowed.
* The intention is to focus on the mathematics part

# Answer
> 14 votes
**Python 2.7**

Some abuse of the random number generator, works on Python 2.7 but not Python 3.x since the generator seems to have changed the seeding algorithm;

```
>>> import random
>>> n=[(15,30,15,25,15,0,-15,-25,-15,-30,-15),(107,35,34,26,22,0,71,188,94,64,81)]
>>> random.seed(4711)
>>> m = zip("MERRY CHRISTMAS",*n)
>>> print(''.join(map(lambda x:chr(ord(x[0])+random.randint(x[1],x[2])),m)))

hello world

```

# Answer
> 23 votes
I'll do better than just printing it, I'll print it infinitely many times!

The rational number

```
1767707668033969 / 3656158440062975

```

returns the following base-36 expansion:

```
0.helloworldhelloworldhelloworldhelloworldhelloworld...

```

Try it out! (Wolfram Alpha)

Or, if you want a more subliminal message, try:

```
2399843759207982499621172523113947162810942763812298565948669
/ 1357602166130257152481187563160405662935023615

```

Which returns (again in base 36):

```
helloworld.helpimtrappedinanumberfactoryhelpimtrappedinanumberfactoryhelpimtrappedinanumberfactory...

```

If your program worked with only integers, you'd never see the fractional part.

# Answer
> 12 votes
# Python ~~(not finished... yet!)~~ finished! :D

```
number = ((sum(b'This text will end up converting to the text "hello world" by a bunch of math.') *
sum(b'For example, multiplication will be used to increase the number so that it may reach the required result.') *
sum(b'Wow, double multiplication! The required result number is extremely big so I have to use lots of math to get there.') *
sum(b'TRIPLE multiplication?!?!?! Wow!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Did I put too many exclamation points?') *
sum(b'I think maybe I might have put too many exclamation points, oops. :(') *
sum(b'This is taking a long time...') *
sum(b'A very, very, very long time...')) // 2)

number -= (sum(b'Okay, the number is a bit too high. Blah. This is extremely hard.') *
sum(b'I need to reduce it. I will just keep multiplying again! Yay! That seems effective!') *
sum(b'I don\'t know what to write now... I used up all my creativity in the previous number.') *
sum(b'So. Uhhh, how has your day been? Was it good? I wonder how many people are still reading.') *
sum(b'Gah! There is nothing to type about anymore! I will just type randomness then.') *
sum(b'Do you like pie? I like pie. Refrigerator. The chicken ate the potato. Llamas are not tasty.'))

number -= (sum(b'Blah, I am still a tiny bit too high!') *
sum(b'This is very frustrating!') * sum(b'Argh!!!!!!!') *
sum(b'I have even less creative ideas now since I have written two paragraphs already.') *
sum(b'Well, I suppose they\'re not paragraphs. They\'re just blocks of code.') *
sum(b'The only reason I made that remark was to increase this number to subtract, so that I reach my target.'))

number -= (sum(b'I am an extremely miniscule amount over the target!!!') *
sum(b'I am so close!!! So close!!') *
sum(b'I must make it!!! I will!!!') *
sum(b'I shall NEVER give up!!!') *
sum(b'Okay, ummm... maybe not exactly "never"...') *
sum(b'I mean, this is REALLY hard...'))

number -= (sum(b'I am so close. This is just ridiculous.') *
sum(b'Just ridiculous. And that\'s awesome :D') *
sum(b'Why am I doing this?!?') *
sum(b'The answer\'s probably "becase I can."') *
sum(b'Notice how most of the text in this program is meaningless.'))

number -= (sum(b'How have I been above my target this whole time? That is very odd.') *
sum(b'I wonder how much time I could have saved if I removed a few characters in the first block.') *
sum(b'I wish I did that. That would have made it so much easier.... But oh well.') *
sum(b'Well, I am really really really really really really close now!'))

number -= (sum(b'I am so close!') *
sum(b'I will never give up now! Not after all this!') *
sum(b'I wonder if I will ever get exactly on the target. What if I do, and then discover a typo? :O') *
sum(b'So close!'))

number -= (sum(b'Wow; this is the eighth block. That\'s a lot of blocks!') *
sum(b'I only have a little more to go! I must finish! I will!') *
sum(b'It is starting to get harder thinking of things to type than it is getting to the target...'))

number -= (sum(b'These strings are short') *
sum(b'So the number to subtract is less') *
sum(b'Hi'))

number += (sum(b'Finally adding') *
sum(b'That\'s new') *
sum(b':D'))

number -= (sum(b'I am back to subtraction, and also longer strings.') *
sum(b'But this time I only get two strings!'))

number -= (sum(b'I have switched over to adding the strings, not multiplying them!') +
sum(b'I am really really close! So close that I can\'t even multiply two strings to subtract anymore!') +
sum(b'This is very exciting; I\'ve nearly made it! Only a few more strings to add...') +
sum(b'I ran out of ideas for what to type again... I will just type exactly what I am thinking, which is what I am doing now actually.') +
sum(b'But now the only thing I am thinking about is getting to the target, and there is not much about that to type...') +
sum(b'I am only a few thousand away!!!!!!!!!!!!'))

number += 8 # NOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

print(number)

```

Outputs `126207244316550804821666916` (equivalent to your example, `0x68656c6c6f20776f726c64`)

# Answer
> 8 votes
> You may select your own way to encode/represent "hello world" as an integer.

Well, then...

## PHP

```
<?=1?>

```

where 1 represents "hello world" because I said so.

# Answer
> 7 votes
# Calculator Font / FreePascal

I may get into trouble for posting this, but I'll do it anyway :-)

1. Calculate 7734/100000. Change the leading zero to blue, and the other digits to calculator font. Turn it upside down. The blue O represents the world:

If that's too lazy, how about this:

```
uses graph;
var gd, gm : integer;
var n,m:integer;

begin
  gd := D4bit;
  gm := m640x480;
  initgraph(gd,gm,'');
  setcolor(black);

  For n:=0 to 5  do for m:=0 to 3 do begin;
    setfillstyle(solidfill,(abs(n*2-1)));

    if(($967EEF shr (20-n*4+m)) and 1) = 1
      then sector(50+n*80,100,90*m,90*(m+1),40,60);

    if(($EDF7E9 shr (20-n*4+m)) and 1) = 1
      then sector(50+n*80,300,90*m,90*(m+1),40,60);
    end;

  readln;
  closegraph;
end.

```

circles numbered 0-5, colour determined by abs(2n-1). One hex digit per circle, quadrants coloured from most significant bit downwards, clockwise from bottom right. By the mystic constants 967EEF and EDF7E9 hex.

Special thanks to the following primitive, and to Borland for putting it in TurboPascal so that FreePascal could clone it.

*procedure Sector( x: SmallInt; y: SmallInt; StAngle: Word; EndAngle: Word; XRadius: Word; YRadius: Word ); Sector draws and fills a sector of an ellipse with center (X,Y) and radii XRadius and YRadius, starting at angle Start and ending at angle Stop.*

# Answer
> 3 votes
## Ruby & Python

Using base 36 math, we arrive at an integer representation quite easily in Ruby & Python:

---

**Ruby**

```
%w(hello world).map{|n|n.to_i(36)}

```

result:

```
[29234652, 54903217]

```

or, expressed as a general function:

```
def f(words); words.split.map{|n|n.to_i(36)}; end

```

example:

```
f("hello world")
=> [29234652, 54903217]

```

---

**Python**

```
def f(words): return map(lambda n: int(n,36), words.split())

```

example:

```
>>> f("hello world")
[29234652, 54903217]

```

# Answer
> 3 votes
Some carefully crafted PHP:

```
$x=18306744;
$w=($z=($y=30)/3)/2;
echo base_convert($x, $z, $y+$z/$w),chr($y+$z/$w).base_convert($x*($y/$z)-$w*41*83,$z,$y+$y/$w);

```

# Answer
> 1 votes
# R6RS Scheme

```
#!r6rs
(import (rnrs))
(define (hello-world)
  (bitwise-xor (fold-left (lambda (acc d)
                        (+ (* acc 256)
                           (+ (bitwise-and 255 acc) d)))
                      104
                      '(-3 7 0 3 8 0 -8 3 -6 -8))
               (bitwise-arithmetic-shift 87 40)))

```

Outputs #x68656c6c6f20776f726c64 (in decemal):

```
126207244316550804821666916

```

My original implementation was:

# Racket (Scheme dialect)

```
(define (hello-world)
  (bitwise-xor (foldl (lambda (d acc)
                        (+ (* acc 256)
                           (+ (bitwise-and 255 acc) d)))
                      104
                      '(-3 7 0 3 8 0 -8 3 -6 -8))
               (arithmetic-shift 87 40)))

```

# Answer
> 1 votes
# JavaScript

```
function stringTheory(theory) {
  var proof = 0;
  var principles = theory.split(/[ ,.'-]/);
  for (var i = 0; i < principles.length; i++) {
      var formula = '';
      for (var j = 0; j < principles[i].length; j++) {
        formula += principles[i].charCodeAt(j).toString(10);
      }
      proof += +formula;
  }
  return proof;
}

console.log(
/* \2 and \3 are start of text and end of text characters */
stringTheory('\2 Yo it\'s 4327 - Go to space, look back, and see the dot of a small blue rock you once sat on amid the vast empty void - KA-BOOM - you are in awe of it. "Ah" - so tiny in this vast space yet you are even more so. A mere atom in an ocean of stars, the earth a speck of dust to the sun\'s ping-pong ball. One day you shall go back and as your toes touch the soft soil once more, the cool wind in your hair as you cast your gaze upon the moon, a mere rock just like this one, and bask in it\'s warm glow - Ah. Only then can you know the scale of it all, what luck you have to call this place home.  And with this new ken, a love you\'ve kept for all of time but had not seen - for it is clear to you now. You lay open your arms and fill the air with your song - (aah) ~o Good-bye space and ... o? \3') + 42
);

```

### What is going on?

We take this string and apply a little `stringTheory()` (it is actually a transmission from the future):

`'\2 Yo it\'s 4327 - Go to space, look back, and see the dot of a small blue rock you once sat on amid the vast empty void - KA-BOOM - you are in awe of it. "Ah" - so tiny in this vast space yet you are even more so. A mere atom in an ocean of stars, the earth a speck of dust to the sun\'s ping-pong ball. One day you shall go back and as your toes touch the soft soil once more, the cool wind in your hair as you cast your gaze upon the moon, a mere rock just like this one, and bask in it\'s warm glow - Ah. Only then can you know the scale of it all, what luck you have to call this place home. And with this new ken, a love you\'ve kept for all of time but had not seen - for it is clear to you now. You lay open your arms and fill the air with your song - (aah) ~o Good-bye space and ... o? \3'`

First we split it at its punctuation to form words. We then create a set of numbers by converting the characters to their decimal ASCII code. Adjoined letters become adjoined numbers (e.g. `aa` becomes `9797`).

The numbers are then summed. What we get back is `191212222216169` an utterly useless number, it has no meaning, much like the quadrillions of rocks that float idly in space. What makes this world special? Why it is life. So by giving this number the meaning of life `+=42` then we get `191212222216211`;

### But why?

What does this mean? Why it means `stringTheory("Hello world")` of course.

# Answer
> 1 votes
# Python

```
from math import fsum
c=[104.,-4412.705557362921,12008.518259002305,-13041.051140948179,7566.060243625142,-2619.91695720304,567.427662301322,-77.52280096313,6.48776455347,-0.303552138602,0.006079144624]
def f(x):
    return fsum([c[i]*x**i for i in range(len(c))])
s=""
for i in range(11):
    s+=chr(int(round(f(i))))
print s

```

# Answer
> 0 votes
## Ruby

Any string is mapped to an integer.

```
# encode string to integer
def str_to_int(s)
  i = 0
  s.chars.each do |c|
    i = i << 7 | c.ord
  end
  i
end

```

The inverse function:

```
# decode integer to string
def int_to_str(i)
  s = ''
  while i > 0 do
    s = (i & 0x7f).chr + s
    i = i >> 7
  end
  s
end

```

Examples:

```
str_to_int("ABC")
=> 1073475
int_to_str(1073475)
=> "ABC"

str_to_int("hello world")
=> 123720932638399026476644
int_to_str(123720932638399026476644)
=> "hello world"

```

# Answer
> 0 votes
**C#**

A method to convert any string (hello world or something else) to hexadecimal string

```
string Encode(string text)
{
   string hexValue = String.Empty;
   foreach(char c in text)
      hexValue += String.Format("{0:X}", (int)c);
   return hexValue;
}

```

A method to convert hexadecimal string to string

```
string Decode(string hexValue)
{
   string text = String.Empty;
   for (int i = 0; i < hexValue.Length; i += 2)
   {
     int value = Convert.ToInt32(hexValue.Substring(i, 2), 16);
     text += (char)value;
   }
   return text;
}

```

Here goes the complete C# program

```
using System;

namespace ConsoleApplication1
{
    class Program
    {

        static string Encode(string text)
        {
            string hexValue = String.Empty;
            foreach(char c in text)
                hexValue += String.Format("{0:X}", (int)c);
            return hexValue;
        }

        static string Decode(string hexValue)
        {
            string text = String.Empty;

            for (int i = 0; i < hexValue.Length; i += 2)
            {
                int value = Convert.ToInt32(hexValue.Substring(i, 2), 16);
                text += (char)value;
            }

            return text;
        }

        static void Main(string[] args)
        {
            string Text1 = "Hello World!";
            Console.WriteLine("Before Encoding: " + Text1 + "\n");

            string Hex = Encode(Text1);
            Console.WriteLine("After endoding: " + Hex + "\n");

            string Text2 = Decode(Hex);
            Console.WriteLine("After decoding: " + Text2 + "\n");
        }
    }
}

```

And here is the output.

# Answer
> 0 votes
## Python

```
def D(A):
    try:
        return sum(D(x)**2 for x in A)
    except TypeError:
        return A
print hex(D([[[[33,22,3,1],[20,13,2],5],[[31,19,1],[11,5,3],1]],[[[26,13],[18,14,6,4],1],[[12,10],[10,3,1],2],4],28]))

```

Recursively decomposes the target number into sums at most four squares. My base case is \<100. I used http://www.alpertron.com.ar/FSQUARES.HTM to calculate the decompositions.

(Maybe a base case of \<=1 would have been interesting...)

# Answer
> 0 votes
## Python

```
def church(i):
    if i > 0:
        return 'f(' + church(i-1) + ')'
    else:
        return 'x'

def church_string(bs):
    import base64
    return church(int(base64.b16encode(bs), 16))

print(church_string(b'hello world'))

```

The result really is a number, I swear!

# Answer
> 0 votes
Just a little C fun with numbers, nothing special.

```
int main()
{
    int a , b, c;
    double i = 0, f = 0;

    for (; i < 1; i += .00000012785666)
        f += cos(i);
    c = f;
    a = f * 276.393089;
    b = a + f * 7.4358109;

    printf("%.4s%.4s%.4s\n", &a, &b, &c);
}

```

demo

# Answer
> -2 votes
```
(+ 110145154154157040127157162154144 0)

```

---
Tags: math, popularity-contest
---


title: Bad News, Someone

text:
# Question
Title: Bad News, Someone
In the Futurama episode The Prisoner of Benda members of the crew swap bodies with each other, with the catch that no pair of *bodies* can have their minds swapped more than once.

### Challenge

Write a program or function that accepts a valid collection of mind-body swaps that have already occurred, and outputs a legal set of swaps that will return each mind to its original body. The identifiers for these mind-body collections must be strings which will not contain newlines. You may add up to two (distinctly named) people who have had no prior swaps to the input group. (Proof that you only need at most 2 additional bodies) However, you must add the minimum number of people required to solve the problem.

The input and output may take any clear form, however, no additional information can be stored in either. You may assume it is always valid. This is code golf, so the winner is the submission with the fewest bytes.

### Examples

```
[('A','B'),('C','D')] -> [('A','C'),('B','D'),('A','D'),('B','C')]

['A','B'] -> ['C','D','A','C','B','D','A','D','B','C']

[('A','B'),('C','D'),('A','C'),('A','D')] -> [('B', 'E'), ('A', 'E'), ('C', 'B'), ('C', 'E')]

"A\nB\nC\nD\n" -> "A\nC\nB\nD\nA\nD\nB\nC\n"

```

The one from the show:

```
[("Amy","Hubert"),("Bender","Amy"),("Hubert","Turanga"),("Amy","Wash Bucket"),("Wash Bucket","Nikolai"),("Phillip","John"),("Hermes","Turanga")]

```

The show's solution, given below is invalid:

```
[("Clyde","Phillip"),("Ethan","John"),("Clyde","John"),("Ethan",Phillip"),("Clyde","Hubert"),("Ethan","Wash Bucket"),("Clyde","Leela"),("Ethan","Nikolai"),("Clyde","Hermes"),("Ethan","Bender"),("Clyde","Amy"),("Ethan","Hubert"),("Clyde","Wash Bucket")]

```

This is invalid because Ethan, and Clyde are unnecessary because of how little ~~Fry~~ Phillip, ~~Zoidberg~~ John and ~~Hermes~~ Hermes used the machine. A valid solution for this case is provided below:

```
[("Philip","Hubert"),("John","Wash Bucket"),("Philip","Turanga"),("John","Nikolai"),("Philip","Hermes"),("John","Bender"),("Philip","Amy"),("John","Hubert"),("Philip","Wash Bucket")]

```

Note that there are clearly many possible answers for any valid input. Any is valid.

# Answer
# Python 3: 328 character (slow), 470 character (fast)

Probably a bit too long for a serious answer.

## Slow and short code:

```
from itertools import*
def d(u,s):i,j=map(u.index,s);u[i],u[j]=u[j],u[i]
def f(Q):
 n=set()
 for s in Q:n|=set(s)
 n=list(n)
 while 1:
  for t in permutations(i for i in combinations(n,2)if not set((i,i[::-1]))&set(Q)):
   u=n[:];j=0
   for s in Q:d(u,s)
   for s in t:
    j+=1;d(u,s)
    if n==u:return t[:j]
  n+=[''.join(n)]

```

`d(u,s)` applies a swap `s` to `u`. In the main method `f(Q)`, I first generate the list of all persons `n` using set operations and converting the result back to a list. The `while 1`-loop is of course not a infinity loop. In it, I try too solve the problem using the persons I have in `n`. If it is not successful, I add another person by combining all names `n+=[''.join(n)]`. Therefore the `while 1`-loop is executed at most 3 times (see proof in the question).

The solving of the problem is done bruteforce. I generate all swaps that are legal and try all permutations `for t in permutations(i for i in combinations(n,2)if not set((i,i[::-1]))&set(Q))`. If each person is in it's own body, I return the sequence of swaps.

**Usage:**

```
print(f([('A','B'),('C','D')]))
print(f([('A','B')]))
print(f([('A','B'),('C','D'),('A','C'),('A','D')]))

```

The example from futurama takes way too long. There are 9 persons, so there are 36 possible swaps and 28 of them are legal. So there are 26! legal permutations.

## Faster code

```
def w(u,s):i,j=map(u.index,s);u[i],u[j]=u[j],u[i]
def f(Q):
 n=set()
 for s in Q:n|=set(s)
 while 1:
  n=list(n);u=n[:];l=len(n)
  for s in Q:w(u,s)
  for d in range((l*l-l)//2-len(Q)+1):r(n,u,Q,[],d)
  n+=[''.join(n)]
def r(n,u,Q,t,d):
 m=0;v=u[:];l=len(u)
 for i in range(l):
  if n[i]!=v[i]:m+=1;w(v,(n[i],v[i]))
 if m<1:print(t);exit()
 for i in range(l*l):
  s=n[i//l],n[i%l]
  if m<=d and i//l<i%l and not set([s,s[::-1]])&set(Q+t):v=u[:];w(v,s);r(n,v,Q,t+[s],d-1)

```

The function `f(Q)` has an iterative deepening approach. It first tries depth=0, then depth=1, until depth=(l\*l-l)//2-len(Q), which is the maximal number of legal moves. Like the slower code it then adds another person and tries again.

The recursive function `r(n,u,Q,t,d)` tries to solve the current position `u` with `d` swaps. `n` is the solved position, `Q` the input moves and `t` the moves already done. It first calculates an lower bound of swaps `m` needed (by solving the state with legal and illegal swaps). If `m` == 0, all persons are in the correct body, so it prints the solution `t`. Otherwise it tries all possible swaps `s`, if `m<d` (pruning), `d>1` (which is already included in `m<d`, `i//l<i%l` (don't allow swaps like `('A','A')` or `('A','B')` and `('B','A')`) and `not set([s,s[::-1]])&set(Q+t)` (`s` hasn't been performed yet).

**Usage:**

```
f([("Amy","Hubert"),("Bender","Amy"),("Hubert","Turanga"),("Amy","Wash Bucket"),("Wash Bucket","Nikolai"),("Philip","John"),("Hermes","Turanga")])

```

It finds the optimal swaps for the futurama problem in about 17 seconds on my laptop using pypy and about 2 minutes without pypy. Notice that both algorithms outputs different solutions, when calling it with the same parameter. This is because of the hashing algorithm of a python-`set`. `n` stores the person each time in a different order. Therefore the algorithm may be faster or slower each run.

Edit: The original futurama test case was wrong, the corrected test case has an optimal solution of 9 instead of 10, and is therefore faster. 2 seconds with pypy, 7 seconds without.
> 3 votes

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


# Question
Title: Print a specific value in this generated binary matrix
Suppose we define an infinite matrix `M`, on `N^2 -> {0, 1}` (where `N` starts from `1` instead of `0`) in this manner:

* `M(1, 1)` = `0`.
* For every `x > 1`, `M(x, 1)` = `1` if `x` is prime, and `0` otherwise.
* For every `y > 1`, `M(1, y)` = the `y`th term in the `Thue-Morse sequence`.
* For every `x, y > 1`, `M(x, y)` = `M(x, y-1) + M(x-1, y) mod 2`.

The top-left `16x16` section of this matrix looks like (with `x` being rows and `y` being columns):

```
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1
1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0
0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1
1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1
0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1
1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1
0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1
0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1
0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0
1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1
0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1
1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0
0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1
0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1
0 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1

```

Your task is to build a program that will evaluate the value of an arbitrary entry in this matrix as accurately as possible.

Your program will take two integers `x` and `y` as input, in any form you choose, and return `M(x, y)`, which will be either `0` or `1`.

Your code may be written in any language, but must not exceed 64 kilobytes (65,536 bytes) of source code size or 2 MB (2,097,152 bytes) of total memory usage. Your program must start with empty memory (i.e. it cannot load data from somewhere else) and run independently for each input (that is, it may not store common data for multiple runs). Your program must also be able to evaluate all the entries in the top-left `8192x8192` square in a reasonable amount of time.

The program that evaluates the most entries correctly in the top-left `8192 x 8192` square will be the winner, with shorter code acting as a tie-breaker.

# Answer
> 9 votes
# J - ~~42~~ 38 char

Pretty fast, 100% accurate, and well within the memory constraints.

```
([{+2&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<:

```

The strategy is as follows: we will calculate successive antidiagonals of this matrix, performing a pairwise XOR to move along and adding the current Thue-Morse and prime bits to the ends. We then pull the required digit out of the antidiagonal when we get there.

Explanation by explosion:

```
(                                 )&<:  NB. decrement each of x and y
     &(                        )        NB. apply the following function...
   +                                    NB. ... (x-1)+(y-1) times...
                                0:      NB. ... starting with a zero:
    2             ~:/\                  NB.   pairwise XOR on the argument
                      ,(p:>:)&#         NB.   append prime bit (is 1+length prime?)
       ~:/@#:@#@],                      NB.   prepend TM bit (XOR of binary)
 [{                                     NB. take the x-th bit (at index x-1)

```

Usage of this verb is `x m y` for M(x, y) as specified in the question, where `m` is the verb.

```
   5 ([{+2&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<: 8
0
   m =: ([{+2&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<:
   1+i.16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
   m/~ 1+i.16
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1
1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0
0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1
1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1
0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1
1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1
0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1
0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1
0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0
1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1
0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1
1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0
0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1
0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1
0 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1

```

To save keystrokes we don't try to tell if we still need more prime or Thue-Morse bits, so we compute the entire antidiagonal to get the bit we want. However, `8192 m 8192` still runs in less than 0.07 s and about 100 KiB on my modest laptop.

# Answer
> 6 votes
## Mathematica – 100% accuracy, ~~223~~ ~~193~~ 189 bytes

```
f=(r=Array[0&,Max@##];For[s=2,s<=#+#2,++s,For[i=Max[1,s-#2],i<=Min[s-1,#],++i,j=s-i;r[[j]]=Which[i==1,PrimeQ@j,j==1,OddQ@Total@IntegerDigits[i-1,2],0<1,Xor@@r[[j-1;;j]]]]];If[r[[#2]],1,0])&

```

Here is a legible version:

```
f[x_,y_] := (
   r = Array[0 &, Max[x,y]];
   For[s = 2, s <= x + y, ++s,
    For[
     i = Max[1, s - y],
     i <= Min[s - 1, x],
     ++i,

     j = s - i;
     r[[j]] = Which[
       i == 1,
       PrimeQ@j,
       j == 1,
       OddQ@Total@IntegerDigits[i - 1, 2],
       0 < 1,
       r[[j - 1]]~Xor~r[[j]]
       ]
     ]
    ];
   If[r[[y]], 1, 0]
   );

```

I basically precompute along diagonals of constant `x+y`.

Features:

* It's accurate.
* It runs in `O(x*y)`.
* `f[8192,8192]` takes about 400 seconds. I suppose there is room for improvement (maybe `RotateLeft` could replace the inner loop).
* It only uses one array of up to `max(x,y)` intermediate results in memory. So there is no necessity to use more than about 32k (assuming 32-bit integers) for the algorithm itself (plus, whatever Mathematica uses). In fact, Mathematica uses 31M by itself on my system, but this works without an issue:

```
MemoryConstrained[f[8192, 8192], 2^21]

```

# Answer
> 2 votes
# Python, 192 characters

100% accuracy, calculates M(8192,8192) in ~10 seconds on my machine.

```
R=range
def M(X,Y):
 X+=1;c=[1]*X;r=[0]
 while len(r)<Y:r+=[i^1 for i in r]
 for i in R(2,X):
  if c[i]:
   for j in R(i+i,X,i):c[j]=0
  r[0]=c[i]
  for i in R(1,Y):r[i]^=r[i-1]
 return r[Y-1]

```

# Answer
> 0 votes
## Perl, 137

Not to 'win' :-), but since there's no Perl here yet and code was written anyway, here it is.

```
sub f{($n,$m)=@_;@a=0;@a=(@a,map{0+!$_}@a)while@a<$n;for$k(2..$m){$p=0;O:{$k%$_?1:last O for 2..sqrt$k;$p=1}$p=$a[$_]^=$p for 1..$n-1}$p}

```

Takes several seconds if called `print f(8192,8192)`, stores single line of matrix in memory (array of 8192 integers (scalars)), about 3.5 Mb whole Perl process. I tried to do it with string instead of array (either with regexps or accessing with substr), takes less memory and can be golfed further, but runs much slower.

Indented:

```
sub f{
    ($n,$m)=@_;
    @a=0;                                  # @a will be current line.
    @a=(@a,map{0+!$_}@a)while@a<$n;        # Fill it with Thue-Morse sequence.
    for$k(2..$m){                          # Repeat until required line number.
        $p=0;                              # Find out if current line number
        O:{                                # is a prime.
            $k%$_?1:last O for 2..sqrt$k;
            $p=1                           # Store result (0 or 1) in $p.
        }
        $p=$a[$_]^=$p for 1..$n-1          # XOR previous value in current position
    }                                      # with $p and store in $p.
    $p                                     # Return $p.
}

```

# Answer
> 0 votes
# Haskell, 223

```
g n=div(filter(>=n)(iterate(*2)1)!!0)2
1%1=0>1
1%n=not$1%(n-g n)
n%1=and[rem n x>0|x<-[2..n-1]]
a%b=g[0<1]where g s|foldr seq(0>1)s=0<1|n==a+b=s!!(b-1)|0<1=g$n%1:zipWith x s(tail s)++[1%n]where n=length s+1
x p|p=not|0<1=id

```

this has fast runtime (5.7 seconds with `-O3`). memory wasn't checked yet, though it should be linear.

this uses the diagonal algorithm seen here before.

as far as speed is concerned, the only things that matter are the diagonal algorithm, `-O3` , and the `|foldr seq(0>1)s=0<1` guard, which makes the list strict. everything else is implemented rather inefficiently - prime checking is done by checking all the lesser numbers for division, the Morse sequence's elements are recomputed constantly. but it is still fast enough :-).

---
Tags: code-challenge, restricted-time, binary-matrix, restricted-memory
---


title: Time Travelling Stock Trader

text:
# Question
Title: Time Travelling Stock Trader
**Story**
Long time ago Bobby created a Bitcoin wallet with 1 Satoshi (1e-8 BTC, smallest currency unit) and forgot about it. Like many others he later though "Damn, if only I invested more back then...".
Not stopping at daydreaming, he dedicates all of his time and money to building a time machine. He spends most of his time in his garage, unaware of worldly affairs and rumors circulating about him. He completes the prototype a day before his electricity is about to be turned off due to missed payments. Looking up from his workbench he sees a police van pulling up to his house, looks like the nosy neighbours thought he is running a meth lab in his garage and called the cops.
With no time to run tests he grabs a USB-stick with the exchange rate data of the past years, connects the Flux Capacitor to the Quantum Discombobulator and finds himself transported back to the day when he created his wallet

**Task**
Given the exchange rate data, find out how much money Bobby can make. He follows a very simple rule: "Buy low - sell high" and since he starts out with an infinitesimally small capital, we assume that his actions will have no impact on the exchange rates from the future.

**Input**
A list of floats \> 0, either as a string separated by a single character (newline, tab, space, semicolon, whatever you prefer) passed as command line argument to the program, read from a textfile or STDIN or passed as a parameter to a function. You can use numerical datatypes or arrays instead of a string because its basically just a string with brackets.

**Output**
The factor by which Bobbys capital multiplied by the end of trading.

**Example**

```
Input:  0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41

```

Exchange rate: 0.48 $/BTC, since it is about to drop we sell all Bitcoins for 4.8 nanodollar. Factor = 1 Exchange rate: 0.4, do nothing
Exchange rate: 0.24 $/BTC and rising: convert all $ to 2 Satoshis. Factor = 1 (the dollar value is still unchanged)
Exchange rate: 0.39 - 2.1 $/BTC: do nothing
Exchange rate: 2.24 $/BTC: sell everything before the drop. 44.8 nanodollar, factor = 9.33
Exchange rate: 2.07 $/BTC: buy 2.164 Satoshis, factor = 9.33
Exchange rate: 2.41 $/BTC: buy 52.15 nanodollar, factor = **10.86**

```
Output: 10.86

```

**Additional Details**
You may ignore weird edge cases such as constant input, zero- or negative values, only one input number, etc.
Feel free to generate your own random numbers for testing or using actual stock charts. Here is a longer input for testing (Expected output approx. 321903884.638)
Briefly explain what your code does
Graphs are appreciated but not necessary

# Answer
> 10 votes
# APL, 16 chars

```
{×/1⌈÷/⊃⍵,¨¯1⌽⍵}

```

This version uses **@Frxstrem**'s simpler algorithm and **@xnor**'s `max(r,1)` idea.

It also assumes that the series is overall rising, that is, the first bitcoin value is smaller than the last one. This is consistent with the problem description. To get a more general formula, the first couple of rates must be dropped, adding 2 chars: `{×/1⌈÷/⊃1↓⍵,¨¯1⌽⍵}`

**Example:**

```
    {×/1⌈÷/⊃⍵,¨¯1⌽⍵}  0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41
10.86634461
    {×/1⌈÷/⊃⍵,¨¯1⌽⍵}  (the 1000 array from pastebin)
321903884.6

```

**Explanation:**

Start with the exchange rate data:

```
    A←0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41

```

Pair each number with the preceding one (the first will be paired with the last) and put them into a matrix:

```
    ⎕←M←⊃A,¨¯1⌽A
0.48 2.41
0.4  0.48
0.24 0.4
0.39 0.24
0.74 0.39
1.31 0.74
1.71 1.31
2.1  1.71
2.24 2.1
2.07 2.24
2.41 2.07

```

Reduce each row by division, keep those with ratio \> 1, and combine the ratios by multiplication. This will eliminate any repeating factors in a row of successive rising rates, as well as the spurious ratio between the first and last exchange rates:

```
    ×/1⌈÷/M
10.86634461

```

# Answer
> 6 votes
## Python, 47

```
f=lambda t:2>len(t)or max(t[1]/t[0],1)*f(t[1:])

```

Example run on the test case.

Take a list of floats. Recursively multiplies on the profit factor from the first two elements until fewer than two elements remains. For the base case, gives `True` which equals `1`.

Using `pop` gives the same number of chars.

```
f=lambda t:2>len(t)or max(t[1]/t.pop(0),1)*f(t)

```

So does going from the end of the list.

```
f=lambda t:2>len(t)or max(t.pop()/t[-1],1)*f(t)

```

For comparison, my iterative code in Python 2 is 49 chars, 2 chars longer

```
p=c=-1
for x in input():p*=max(x/c,1);c=x
print-p

```

Starting with `c=-1` is a hack to make the imaginary first "move" never show a profit. Starting the product at `-1` rather than `1` lets us assign both elements together, and we negative it back for free before printing.

# Answer
> 3 votes
# Python, ~~79~~ ~~81~~ ~~76~~ 77 bytes

```
f=lambda x:reduce(float.__mul__,(a/b for a,b in zip(x[1:],x[:-1]) if a>b),1.)

```

`x` is the input encoded as a list. The function returns the factor.

# Answer
> 2 votes
# CJam, 33 bytes

```
q~{X1$3$-:X*0>{\;}*}*](g\2/{~//}/

```

This can be golfed further.

Takes input from STDIN, like

```
[0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41]

```

and outputs the factor to STDOUT, like

```
10.866344605475046

```

Try it online here

# Answer
> 1 votes
# Pyth, 18

```
u*GeS,1ceHhHC,QtQ1

```

Explanation:

```
u                 reduce, G is accumulator, H iterates over sequence
 *G               multiply G by
   eS             max(
     ,1               1,
       ceHhH            H[1]/H[0])
 C                H iterates over zip(
  ,QtQ                                Q,Q[1:])
 1                G is initialized to 1

```

`max(H[1]/H[0],1)` idea thanks to @xnor

# Answer
> 1 votes
## C#, 333, 313

My first attempt. Could probably optimize it more but like I said first attempt so will get the hang of it!.

```
double a(double [] b){var c=0.0;var d=1;for(int i=0;i<b.Count();i++){c=(d==1)?(((i+1)<b.Count()&&b[i+1]<=b[i]&&d==1)?((c==0)?b[i]:b[i]*c):((i+1)>=b.Count()?(c*b[i])/b[0]:c)):((i+1)<b.Count()&&b[i+1]>b[i]&&d==0)?c/b[i]:c;d=((i+1)<b.Count()&&b[i+1]<b[i]&&d==1)?0:((i+1)<b.Count()&&b[i+1]>b[i]&&d==0)?1:d;}return c;}

```

Input

```
0.48, 0.4, 0.24, 0.39, 0.74, 1.31, 1.71, 2.1, 2.24, 2.07, 2.41

```

Output

```
10.86

```

Edit: Thanks to DenDenDo for suggesting not using math.floor to round and using int instead of bool to cut chars. Will remember that for future puzzles!

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


title: 10, 10, 10... I hope?

text:
# Question
Title: 10, 10, 10... I hope?
## Preface

As I was shooting an archery 900 round earlier today (10 ends at 6 arrows an end, and 10 ends at 3 arrows an end, for a total of 90 arrows and a maximum score of 900), I thought of this challenge.

In archery (assuming that you are shooting on a FITA supplied *target face* \[the piece of paper that you shoot at\]), for each arrow you can claim a maximum score of 10. The target face contains 10 or 11 rings of decreasing diameter, nested inside one another. From the inner ring outward, these are counted from 10 points, to one point (and in the case of 11 rings, there is a secondary innermost ring that counts as 'X', which scores as 10 but is used in tie breaking cases as the higher value). Observe:

Of course, I am referring to the FITA Metric scoring, as seen in the above illustration. If you look closely, you may observe the innermost ring, which is a faded dotted line, whose score is not marked. That is the 'X' that I was referring to, but you will not have to pay heed to that unless competing for the bonus.

## Challenge

Create a function (or full program, if the language doesn't support functions), that receives a perfectly square image as input (or image filename, if need be), containing some number of green (HEX #00FF00, RGB(0, 255, 0)) dots of some size, and returns the score. **The image may contain data other than the green dots**, but the green will always be the exact same shade.

You may imagine that the square image represents the target face, with the outermost ring touching at 4 points (top center, bottom center, right center, left center). The represented target face will always be of the same proportion, with all of the rings having a width of exactly 1/20th of the input target image's width. As an example, given an input image of input dimensions 400px by 400px, you may assume that each ring has an inner width of 20px, as illustrated below:

## Clarifications

* If touching two seperate rings, the higher of the two rings is counted
* You do not have to automatically account for misses or the 'x' case, unless trying for the bonus
* You may assume that no green circles are overlapping
* You may also assume that no other pixels of that shade of green are in the image
* The image will either be in a PNG, JPEG or PPM format (your choice)
* External image processing libraries are allowed, if authored before the posting of this question
* You may assume that all green circles on one target will have the same diameter
* If shooting (hah) for the overlapping circles bonus, you may assume that at least one circle in the image does not have another overlapping
* Standard loopholes are disallowed

## Test cases

The following two cases should each score ***52*** (or in the case of bonuses, 52 with 1 'x' and 1 miss):

And this last test case should score ***25***:

## Bonus

* -25 bytes if you also return the number of misses (outside any of the rings) as well
* -30 bytes if you also return the amount of Xs (assume that the innermost x is 3/100ths of the width of the image, and 10 is then 2/100ths of the width of the image. The 1-9 proportions remain unchanged)
* -35% byte count if you account for overlapping circles

This is code golf, so the least bytes wins. Have fun!

# Answer
# Processing 2, 448-25=423 bytes

```
int x,y,w,b,v,c,m;color g;PImage i;void setup(){i=loadImage("f.png");w=i.width;size(w,w);g=#00ff00;image(i,0,0);b=v=x=y=c=m=0;loadPixels();while(y*w+x<w*w){if(pixels[y*w+x]==g){f(y,x);if(v>=0)c+=v;else m++;}v=-1;x++;if(x==w){x=0;y++;}}println(c+" "+m);}void f(int k,int l){pixels[k*w+l]=color(0);if(pixels[(k+1)*w+l]==g)f(k+1,l);if(pixels[k*w+l+1]==g)f(k,l+1);if(pixels[k*w+l-1]==g)f(k,l-1);k-=w/2;l-=w/2;b=10-(int)(sqrt(k*k+l*l)/(w/20));if(b>v)v=b;}

```

Reads in an image file f loops through the pixels until it finds green then flood fills the circle determining the point that is closest to the center. Then adds that score to a total. if the score is negative, it is added to a miss counter.

The program will output 2 numbers, the first is the score and the second is the number of misses.

```
  int x,y,w,b,v,c,m;
  color g;
  PImage i;
void setup()
{
  i=loadImage("f.png");
  w=i.width;
  size(w,w);
  g=#00ff00;
  image(i,0,0);
  b=v=x=y=c=m=0;
  loadPixels();
  while(y*w+x<w*w)
  {
    if(pixels[y*w+x]==g)
    {
      f(y,x);
      if(v>=0)c+=v;
      else m++;
    }
    v=-1;
    x++;
    if(x==w){x=0;y++;}
  }
  print(c+" "+m);
}

void f(int k,int l)
{
  pixels[k*w+l]=color(0);
 if(pixels[(k+1)*w+l]==g)f(k+1,l);
 if(pixels[k*w+l+1]==g)f(k,l+1);
 if(pixels[k*w+l-1]==g)f(k,l-1);
 k-=w/2;
 l-=w/2;
 b=10-(int)(sqrt(k*k+l*l)/(w/20));
 if(b>v)v=b;
}

```

you can get processing here
> 4 votes

# Answer
# Perl 5 + GD: 225 - 25 = 200

Edit: Found the reason for the incorrect pixel reading in indexed PNGs and applied a workaround. For some reason with the GD library the green pixel values are read as (4,254,4). I am not sure if this is specific to the PNG files included in the question. Line breaks can be removed in the code below.

```
use GD;$k=newFromPng GD::Image'-',1;
sub v{/ /;10-int((($'-@x/2)**2+($`-@x/2)**2)**.5/@x*20)}
map{v>0?($r+=v):$%++,fill$k @c,0if 65280==getPixel$k @c=split
}sort{v($_=$b)- v$_=$a}map{//;map"$_ $'",@x}@x=0..width$k-1;
print"$r $%"

```

Takes a PNG image on the input and prints 2 values: Number of points and misses. For example:

```
perl arch.pl <arch52.png
52 1

```

### Last minute change:

In true color mode that I needed anyway the color indexes used by `getPixel` and `fill` are simply integer encoded RGB values, so no need to use `rgb` and `colorAllocate` to convert to and from those indexes.

### Explanation:

* Generate list of all pixel coordinates (as space separated pairs of integers).
* Sort by potential score (using `sub v` which takes parameter through `$_` instead of standard parameters as it is shorter).
* For each pixel starting from the highest scoring ones if it is green add to the result and flood fill its location black.
> 4 votes

# Answer
# Haskell - 579-25 = 554 603-25-30 576-25-30 = 521 Bytes

Strategy:

* Make a list of (d,x,y) triples for all pixels (d is distance to center)
* sort the list by distance
* beginning with the greatest distance: if the pixel the only green pixel in a small neighborhood, keep it's distance in a list L, else blacken it
* calculate score from the distance list L

Output ist a triple (score,misses,Xs), e.g. `(52,1,1)` for the test image.

The program may fail if the pixel of a circle closest to the center is within 3 pixels of another circle.

```
import Data.List
import Codec.Picture
import Codec.Picture.RGBA8
import Codec.Picture.Canvas
z=fromIntegral
f(e,x,y)(v,h)|and$j x y:[not$j a b|a<-[x-3..x+3],b<-[y-3..y+3],not(a==x&&b==y)]=(v,e:h)|1<2=(setColor x y(PixelRGBA8 0 0 0 0)v,h)
 where j n m|PixelRGBA8 0 255 0 _<-getColor n m v=0<1|0<1=0>1
d k r(h,i,j)|r>10*k=(h,i+1,j)|r<k*3/5=(h+10,i,j+1)|1<2=(10-(floor$r/k)+h,i,j)
main=do
 i<-readImageRGBA8 "p.png"
 let(Right c)=imageToCanvas i;s=canvasWidth c;q=[3..s-4];(_,g)=foldr f(c,[])$sort[(sqrt$(z x-z s/2)^2+(z y-z s/2)^2,x,y)|x<-q,y<-q]
 print$foldr(d$z s/20)(0,0,0)g

```
> 3 votes

# Answer
# Mathematica - ~~371~~ 386 - 25 = 361

A more optimal solution. Computes the answer much faster than my Python solution.

```
i=IntegerPart;c=i/@((NestList[#+.01&,.1,10]~Prepend~1)*100);g[m_]:=Last@@c~Position~#-1&/@(i@Round@Last@#&/@(#*100&/@Riffle[RGBColor/@NestList[#+.01&,{.1,.1,.1},10],Table[Disk[{0,0},n],{n,1,.1,-.1}]]~Graphics~{ImageSize->ImageDimensions[m],PlotRangePadding->None}~ImageMultiply~ChanVeseBinarize[m,"TargetColor"->Green]~ComponentMeasurements~"Max"/.Rule[a_,b_]:>b))//{Total@#,#~Count~0}&

```

# Python with PIL - A trivial and non-optimal solution, 961 bytes

**This is simply to try to demonstrate a silly approach at solving the problem.** It takes ~2 minutes to run the first two test cases, and ~20 minutes to run the third on my system because of the quickly made up, terribly resource intensive, and repulsively algorithmically complex circle detector. Despite this, it does meet requirements, though it is certainly not optimally golfed. The more green there is on the image, the longer it takes to run.

```
from PIL import Image,ImageDraw
a=lambda x,y,w,h:filter(lambda x:0<=x[0]<w and 0<=x[1]<h,[(x-1,y-1),(x,y-1),(x+1,y-    1),(x-1,y),(x,y),(x+1,y),(x-1,y+1),(x,y+1),(x+1,y+1)])
def b(c):
 d=0,255,0;e,f=c.size;g=c.load();h,i=[],[];j=Image.new("RGB",(e,f));k=ImageDraw.Draw(j)
 for l in range(e):
  for m in range(e):
   n=g[l,m][:-1]
   if n==d and(l,m)not in i:
    o=[(l,m)];p=[];q=1
    while q:
     q=0;r=o[:]
     for s in o:
      t=filter(lambda x:g[x[0],x[1]][:-1]==d and(x[0],x[1]) not in r,a(s[0],s[1],e,f))
      if t:
       r+=t
       if len(t)<8:
        p+=[s]
       q=1
     o=r
    h+=[p]
    for u in o:
     i+=[u]
   i+=[(l,m)]
 p=map(lambda x:"#"+str(x)*6,'123456789ab');v=0;k.rectangle((0,0,e,f),fill=p[0])
 for n in p[1:]:
  w=e/20*v;x=e-w;k.ellipse((w,w,x,x),fill=n);v+=1
 y=j.load();z=0
 for l in h:
  v=[]
  for m in l:
   s=y[m[0],m[1]]
   if s not in v:
    v+=[s]
  v=max(v);z+=p.index("#"+''.join(map(lambda x:hex(x)[2:],v)))
 return z

```

Takes a PIL image object, and returns the score.

## Steps it takes:

1. Isolate green circles (inefficiently)
    * Find all neighbours of some pixel `n`, if any are green pixels then add them to the circle
    * Determine rough outline by filtering out pixels that have 8 neighbours
2. Draw a target representation
    * Create a blank canvas
    * Draw a unique colored background (easy to implement misses)
    * Draw nested ellipses with unique colors
3. Determine which scoring zones each circle is in by determining the color(s) of the target which would be underneath the circle
4. Choose the higher of the scoring zones (if multiple) and add the score to the total
5. Return the total
> 2 votes

---
Tags: code-golf, image-processing
---