title: Golfing Flower of Life

text:
# Question
Title: Golfing Flower of Life
The challenge here is to accurately depict the flower of life (which is a sacred geometrical figure according to some) in the language of your choice.

The design consists an arrangement of circles and partial circles of radius 1 as shown whose centres arranged on a triangular grid of pitch 1, plus one larger circle of radius 3 surrounding them.

The design can be scaled as you like, but a max error of 2% from mathematically correct is permitted. If using raster graphics, this effectively limits the diameter of the small circles to at least about 100 pixels.

Since this is code-golf, shortest code (bytes) wins.

# Answer
## Mathematica, ~~177~~ ~~173~~ ~~128~~ ~~124~~ 120 bytes

```
c=Circle;Graphics@{{0,0}~c~3,Rotate[Table[If[-3<x-y<4,c[{√3x,-x+2y}/2,1,Pi/{6,2}]],{x,-3,2},{y,-4,2}],Pi/3#]&~Array~6}

```

The main idea is to compose the result from six rotated versions of this:

This in turn is a rectangular table of identical circle arcs with two corners cut off. If we remove the shearing and represent each circle center with a `#`, we basically want to distribute the circles in this pattern:

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

```

These edges are cut off by imposing the condition `-3 < x-y < 4` on the 2D indices (since the value of `x-y` is constant along diagonals) and the shearing comes from multiplying these `x` and `y` by non-orthogonal basis vectors which span the grid we're looking for.

This particular orientation of the unrotated arcs turns out to be the shortest since both ends of the arc evenly divide `Pi` so that the arc can be expressed as `Pi/{6,2}` (all other arcs would either require and additional minus sign or integers in the numerator).
> 24 votes

# Answer
# OpenSCAD, 228 bytes

```
$fn=99;module o(a=9){difference(){circle(a);circle(a-1);}}function x(n)=9*[sin(n*60),cos(n*60)];module q(g){for(i=[1:6])if(g>0){translate(x(i))union(){o();q(g-1);}}else{intersection(){translate(x(i))o();circle(9);}}}q(2);o(27);

```

The below is a version allowing someone to set parameters r (radius) and w (width of rings).

```
r=1;w=.1;$fn=99;module o(n){difference(){circle(n);circle(n-w);}}function x(n)=(r-w/2)*[sin(n*60),cos(n*60)];module q(g){for(i=[1:6])if(g>0){translate(x(i))union(){o(r);q(g-1);}}else{intersection(){translate(x(i))o(r);circle(r);}}}q(2);o(3*r-w);

```

This version is xactly 246 characters.
Some of this code is technically unnecessary but makes it look more like the picture.
> 9 votes

# Answer
# Mathematica, 263 bytes

Not really competitive with @MartinEnder's submission but I had fun with this nonetheless. I let the petals do a random walk! The petal walks by rotating 60 degrees randomly about one of the endpoints which is also randomly chosen. I test to see if the rotating end of the petal falls outside the large disk, and if so, the rotation goes the other way.

```
c=Circle;a=√3;v={e=0{,},{0,2}};f=RandomChoice;Graphics@{e~c~6,Table[q=f@{1,2};t=f@{p=Pi/3,-p};r=RotationTransform[#,v[[q]]]&;v=r[If[r[t]@v[[-q]]∈e~Disk~6,t,-t]]@v;Translate[Rotate[{c[{1,a},2,p{4,5}],c[{1,-a},2,p{1,2}]},ArcTan@@(#-#2)&@@v,e],v[[2]]],{5^5}]}

```

Here is the subsequent code I used for the animation.

```
Export[NotebookDirectory[]<>"flower.gif", Table[Graphics[Join[{c[e,6]},(List@@%)[[1,2,1;;n-1]],{Thick,Red,(List@@%)[[1,2,n]]}]],{n,1,3^4,1}]]

```

I read somewhere that 2-dimensional random walks must eventually return to the origin. It seems like a few thousand steps guarantee filling the large disk.
> 6 votes

# Answer
## JavaScript (ES6)/SVG, 299 bytes

```
with(document){write(`<svg height=250 width=250><circle${b=` fill=none stroke=black `}cx=125 cy=125 r=120 />`);for(i=0;i<24;i++)write(`<path${b}d=M5,125${`${a=`a60,60,0,0,1,`}40,0`.repeat(i%4+3)+`${a}-40,0`.repeat(i%4+3)} transform=${`rotate(60,125,125)`.repeat(i>>2)}rotate(-60,${i%4*4}5,125) />`)}
```

Works by generating multiple arc pairs of various lengths then rotating them into place.
> 4 votes

---
Tags: code-golf, ascii-art, graphical-output
---


title: Japanese Mahjong Score Calculator

text:
# Question
Title: Japanese Mahjong Score Calculator
I'm new to Japanese Mahjong and have trouble calculating the scores. Please help me write a program to calculate it.

# Introduction

(aka you can skip this boring part)

Mahjong is a popular tile game in Asia. Different rules have evolved and systematically established in various regions. Japan, being an isolated island state, have its own mahjong variant including rules and scoring.

In Japanese Mahjong, 4 players participate in the game at the same time. They take turn to draw a tile from wall and discard a tile from hand. Occasionally then can take other's discarded tiles for use. Each round 1 of the 4 players will be the dealer. Independent of that, each round may have a winner if he/she can assemble a winning hand. There could be no winners in a round but we don't care about that in this challenge.

When a player become the winner of that round, the change in score is calculated depending on 4 things: (1) `Han` and (2) `fu` depends on the winning hand, (3) whether the winner is also a dealer, and (4) whether he win by self-draw or from other's discard. The winner get his points by taking the points from the losers. So points lost by all losers added should equal to points gained by winner. Moreover, sometimes only one loser lose his points while the other two don't lose any, and sometimes one of the three losers lose more points. (See below)

# Objective

Write a program or function that accepts the 4 parameters mentioned above, and return (1) how many points the winner will gain, and (2-4) how many points each of the three losers will lose.

## Details of inputs

`Han`: An integer from 1 to 13 inclusive.
`Fu`: An integer that is either 25, or an *even* number from 20 to 130 inclusive. If `han` is 1 or 2, `fu` is further capped at 110.
`dealer or not`: A truthy/falsy value. Though if you are a mahjong lover you can instead accept the winner's seat-wind :-)
`self-draw or discard`: A two-state value. Truthy/falsy value will suffice but other reasonable values are acceptable.

## Steps of calculating the points gained/lost:

**1. Calculate the base score**

The base score is calculated based on 2 cases.

*1a) `Han` ≤ 4*

If `fu` is 25, then keep it as-is. Otherwise round it *up* to nearest 10.

Then base score is calculated by
base\_score = fu×2han+2
And it's capped at 2000 points.

*1b) `Han` ≥ 5*

`Fu` is *not* used here. The base score is obtained by direct lookup of `han` in the following table:

```
Han    Base score
5      2000
6-7    3000
8-10   4000
11-12  6000
13     8000

```

**2. Calculate the points lost by losers**

*2a) Dealer wins by self-draw*
Each loser pays an amount equal to double of the base score, then rounded *up* to nearest 100.

*2b) Dealer wins by discard*
The discarding loser pays an amount equal to 6x the base score, then rounded *up* to nearest 100. Other two losers don't pay.

*2c) Non-dealer wins by self-draw*
Dealer (one of the loser) pays an amount equal to double of the base score, then rounded *up* to nearest 100. The other two losers each pays an amount equal to base score, also rounded up to 100.

*2d) Non-dealer wins by discard*
The discarding loser pays an amount equal to 4x the base score, then rounded up to 100. Other two losers don't need to pay. Scoring isn't affected by whether the discarding loser is dealer or not.

**3. Calculate the points gained by winner**

Winner gains the total points lost by the three losers. Not a point less and not a point more.

# Example

(Some examples are shamelessly taken/modified from Japanese Wikipedia page of calculating mahjong score)

**4 `han` 24 `fu`, dealer win by self-draw**

24 `fu` rounded up to 30 `fu`
Base score = 30 × 2 4+2 = 1920
Each loser pays 1920×2 = 3840 =\> 3900 (rounded)
Winner takes 3900×3 = 11700 points
Output: +11700/-3900/-3900/-3900

**3 `han` 25 `fu`, dealer win by discard**

25 `fu` no need to round up
Base score = 25 × 2 3+2 = 800
Discarding loser pays 800×6 = 4800
Non-discarding loser pays 0 points
Winner takes 4800 points
Output: +4800/-4800/0/0

**4 `han` 40 `fu`, non-dealer win by self-draw**

40 `fu` no need to round up
Base score = 40 × 2 4+2 = 2560 =\> 2000 (capped)
Dealer pays 2000×2 = 4000
Non-dealer pays 2000
Winner takes 4000+2000×2 = 8000 points
Output: +8000/-4000/-2000/-2000

**9 `han` 50 `fu`, non-dealer win by discard**

`Fu` not used to calculate score
Base score = 4000 (table lookup)
Discarding loser pays 4000×4 = 16000
Non-discarding loser pays 0 points
Winner takes 16000 points
Output: +16000/-16000/0/0

## Output

Output 4 numbers: The point that the winner is gaining (as positive number), and the points that each of the three losers is losing (as negative number).
You may output the numbers as 4 individual numerical values in your language's native format, an array/list of numbers, 4 separate strings (or array/list of characters), or a string contatining the numbers that are properly delimited. If you use string, the positive sign is optional but negative sign is mandatory.
The order of the numbers doesn't matter, since they can be inferred from sign and magnitude of the numbers. e.g. 0/-16000/+16000/0 is acceptable.

## Format

* Full program or function
* Any reasonable input/output format
* Default rules apply. Standard loopholes forbidden. so fewest bytes wins.

# Notes

* All outputs are guaranteed to be integers, more specifically multiples of 100 in the range \[-48000,+48000\]
* Rounding is applied only to (1) `fu` and (2) loser's points. It is *not* applied to base score.
* Theoretically winning by self-draw or discard should gain the same points (6x or 4x base points). However due to rounding, this may not be true at low `han`. (See 1st and 2nd test cases)

# Test cases

(Also see example)

```
Inputs                         Outputs
Han    Fu     Dealer  Self     Winner   Loser1    Loser2    Loser3
1      22     N       Y        +1100    -500      -300      -300
1      22     N       N        +1000    -1000     0         0
3      106    Y       N        +12000   -12000    0         0
4      20     N       Y        +5200    -2600     -1300     -1300
4      25     Y       N        +9600    -9600     0         0
5      88     Y       Y        +12000   -4000     -4000     -4000
7      25     Y       Y        +18000   -6000     -6000     -6000
12     64     N       N        +24000   -24000    0         0
13     130    Y       N        +48000   -48000    0         0

```

# Answer
> 3 votes
# 05AB1E, 79 bytes

05AB1E uses CP-1252 encoding.

**Input order:**

```
Han
Fu
Dealer = 1, Non-dealer = 0
Self = 2, Discard = 0

```

**Code:**

```
3‹i6b‚ï{0è}¹5‹iÐT/îT*‚sÈè¹Ìo*3°·‚{0èë\•j¤È°•¹è3°*}U•é2TˆÞ•S3ôŠ+èX*Tn/îTn*(DOÄ¸ì

```

Try it online!

Explanation to come.

# Answer
> 3 votes
## Python 2, 128 bytes

```
def m(h,f,o,t):C=100;b=[24/(50/h)*1000,min(2000,[-f/10*~9,f][f%2]<<h+2)][h<5];x=(o|2-t)*-2*b/C*C;y=~o*t*b/C*C;return-x-y-y,x,y,y

```

`h` is han, `f` is fu, `o` is dealer (1/0), `t` is self-draw (1/0). Outputs in the same order as the test cases. ideone link.

Expanded slightly:

```
def m(h,f,o,t):
  C = 100

  # Base score
  b = [24/(50/h)*1000, min(2000,[-f/10*~9,f][f%2]<<h+2)][h<5]

  # Player scores - uses the -x/100*-100 approach to round up
  x = (o|2-t)*-2*b/C*C
  y = ~o*t*b/C*C

  return -x-y-y, x, y, y

```

Indirect thanks to @MartinEnder.

# Answer
> 0 votes
## C#6, 211 bytes

```
using static System.Math;(h,f,x,y)=>{int b=h>5?24/(50/h)*100:Min(f%2<1?(int)Ceiling(f*.1)<<h+2:10<<h,200),c=-(int)Ceiling(b*.1*(y?2:x?6:4))*100,d=-(int)Ceiling(b*.1*(y?x?2:1:0))*100;return new[]{-c-d*2,c,d,d};};

```

Contains an idea shamelessly stolen from @Sp3000.

Assign to `Func<int,int,bool,bool,int[]>`
h=han
f=fu
x=true if dealer wins, false if non-dealer wins
y=true if self draw, false if discard
returns int\[\], \[0\]=winner, \[1\]-\[3\]:loser
repl.it demo

Ungolfed + explanations

```
// b is base score / 10
int b=h>5
    // han is [6,13], use Sp3000's idea
    ?24/(50/h)*100
    // han <= 5, calculate base score (/ 10) from formula...
    // Yes this formula works for han==5 also
    :Min(
        f%2<1
            // round up to 10, then times 2^(h+2)
            ?(int)Ceiling(f*.1)<<h+2
            // b=2.5*2^(h+2)=10*2^h=10<<h
            :10<<h
        // Cap at 200, thus base score is capped at 2000
        ,200),
// Multiply 0.1b by 2/4/6 according to input, then multiply by 100 to get actual score
c=-(int)Ceiling(b*.1*(y?2:x?6:4))*100,
d=-(int)Ceiling(b*.1*(y?x?2:1:0))*100;
// Array type implied from arguments
return new[]{-c-d*2,c,d,d};

```

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


# Question
Title: The Golfer Adventure - Chapter 1 : The vase
# The Golfer Adventure

This is the first challenge ! There will be more challenges later that will require data from the previous challenge :)

## Chapter 1 : The Vase

Let's imagine a minute.. You are a powerful God, your powers are limitless but require one thing : Souls. Each soul is here represented by a byte, each byte you use does sacrifice a soul. So the goal is obviously to save the biggest amount of people while sacrificing the least amount of souls.

Your first challenge is to save a little village, the devil is willing not to destroy the entire village if you resolve his challenge.

### The Challenge :

You have a vertical vase which can contain exactly 10 things (Air included). If you put a thing in that vase, gravity will make that thing fall to the bottom. If the vase is already full (and it's always full if you consider it as "full of air"), the input will replace the element at the top of the vase.

Here is the set of allowed things :

* Air `0 /`
* A Rock `1 / -`
* A Leaf `2 / ~`
* A Bomb `3 / x`

If there is a rock or a leaf on top of "A Bomb", it will explode and destroy the thing on the top of it.

The input is the list of the things you'll put in the vase every turn.

**Example :** 11231 : You'll put 2 rocks, then a leaf, then a bomb and finally a last rock.

When the vase is static, you can begin to count with the following rule :

* Rock adds 1 unit to the accumulator
* Leaf multiplies the accumulator by 2
* Bomb decrement the accumulator by 1
* Air does nothing

(You need to start counting from the top of the vase)

Here is the simulation we get using "11231" as input :

```
|-|  |-|  |~|  |x|  |-|  | |  | |  | |  | |  | |  | |
| |  |-|  |-|  |~|  |x|  |-|  | |  | |  | |  | |  | |
| |  | |  |-|  |-|  |~|  |x|  |-|  | |  | |  | |  | |
| |  | |  | |  |-|  |-|  |~|  |x|  |-|  | |  | |  | |
| |  | |  | |  | |  |-|  |-|  |~|  |x|  |-|  | |  | |
| |  | |  | |  | |  | |  |-|  |-|  |~|  |x|  |-|  | |
| |  | |  | |  | |  | |  | |  |-|  |-|  |~|  |x|  | |
| |  | |  | |  | |  | |  | |  | |  |-|  |-|  |~|  |~|
| |  | |  | |  | |  | |  | |  | |  | |  |-|  |-|  |-|
| |  | |  | |  | |  | |  | |  | |  | |  | |  |-|  |-|

```

And the output will be 2 (calculated as `((0 x 2) + 1) + 1`) No need to print all the states of the vase !

### The base program (Python3)

You can execute it to understand how it works.

```
def printVase(vase):
  for i in vase:
    if i == 1:
      print("|-|")
    elif i == 2:
      print("|~|")
    elif i == 3:
      print("|x|")
    else:
      print("| |")

def updateVase(vase):
  changed = False
  for i in range(len(vase), -1, -1):
    if i < len(vase) - 1:
      if vase[i+1] == 3 and vase[i] in [1,2]:
        vase[i], vase[i+1] = 0, 0
        changed = True
      if not vase[i+1] and vase[i] in [1, 2, 3]:
        vase[i], vase[i+1] = vase[i+1], vase[i]
        changed = True
  return changed

userInput = input("Vase : ")
vase = [0 for i in range(0, 10)]
oldVase = vase
while updateVase(vase) or userInput != "":
  if userInput != "":
    vase[0] = int(userInput[0])
  userInput = userInput[1::]
  printVase(vase)
  input()

accumulator = 0
for i in vase:
  if i == 1:
    accumulator += 1
  if i == 2:
    accumulator *= 2
  if i == 3:
    accumulator -= 1
print(accumulator)

```

### Golfed version (Python3, no Vase Display) : 360 bytes = 360 points

```
def u(v):
  c=0
  for i in range(len(v),-1,-1):
    if i<len(v)-1:
      if v[i+1]==3 and v[i]in[1,2]:v[i],v[i+1],c=0,0,1
      if not v[i+1]and v[i]in[1,2,3]:v[i],v[i+1],c=v[i+1],v[i],1
  return c
l,v=input(),[0 for i in range(0, 10)]
while u(v)or l!="":
  if l!="":v[0],l=int(l[0]),l[1::]
a=0
for i in v:
  if i==1:a+=1
  if i==2:a*=2
  if i==3:a-=1
print(a)

```

**If you want to test if your program works correctly, you can test this input : 12122111131**

**Correct answer is 43** :) (Thanks Emigna)

### Now for the points :

* (x) points where : x is the amount of bytes needed to write your program. If you answer after the next challenge is posted, points for this challenge won't be added to your total amount of points.

The goal is to keep a minimum amount of points during the whole challenge :) If you skip one of the part of the challenge, you'll have (wx + 1) points by default for the skipped part (where wx is the worst score for that challenge).

### Data that will be required for the next challenge :

Output when input = 10100000200310310113030200221013111213110130332101

### Current Champion : Emigna

Good luck everyone !

# Answer
> 5 votes
# Python 2 - ~~208~~ ~~191 185 180 172 164~~ 156 bytes

```
t=filter(bool,map(int,input()))
i=a=0
n=len(t)
while 0<n-1>i<11:
 if(t[i]>=3>t[i+1]):del t[i:i+2];i,n=0,n-2
 i+=1
for x in t[9::-1]:a+=a+x%2*(2-x-a)
print a

```

The breakdown is it removes air and the bombs if it is on the stack then counts.

EDIT : I swapped to Python 2 to save a byte, but now the input should be put in braces like '3312123'

EDIT2 : Im also kinda proud of the accumulator count

EDIT3 : Thanks for all your suggestions I would never have thought I could get it so low

# Answer
> 4 votes
# 05AB1E, ~~28~~ 36 bytes

05AB1E uses CP-1252 encoding.

```
Î0KDvT¹g‚£`sTØõ:žwõ:ì}ÁT£ÀRS"<>·"è.V

```

Try it online!

# Answer
> 4 votes
## Retina, ~~58~~ 56 bytes

```
1+`0|(?<=.{9}).\B|3[12]

+-1=`2
$'
+`13

*\(1`3
-
)T`d
.

```

Try it online!

# Answer
> 3 votes
## Python 2, ~~150~~ 146 bytes

```
v=[]
s=0
for c in input():
 v=v[:9]
 if'0'==c:1
 elif 3 in v[-1:]and c in'21':v=v[:-1]
 else:v+=[int(c)]
for x in v[::-1]:s+=s+x%2*(2-x-s)
print s

```

Thanks to Pâris Douady for the points formula, and for saving 4 bytes.

# Answer
> 2 votes
## Javascript, ~~267~~ ~~264~~ 249 souls sacrificed

```
r='replace'
f=t=>{t=t[r](/0/g,'');while(/3[12]/.test(t.substring(0,10)))t=t[r](/3[12]/,'');
a=t.length-1;x=(t.substring(0,9)+(a>8?t[a]:'')).split('').reverse().join('');
c='c=0'+x[r](/1/g,'+1')[r](/2/g,';c*=2;c=c')[r](/3/g,'-1');eval(c);return c}

```

Edited version, because the previous one was incorrect for larger inputs. Golfed it a little further by making `string.prototype.replace()` into an array-accessed function call. Explanation:

```
f=t=>{                                  Function declaration, input t
t=t.replace(/0/g,'');                   Remove air
while(/3[12]/.test(t.substring(0,10)))  Look for bombs; not double bombs, and only in the first 10 chars
    t=t.replace(/3[12]/,'');            Detonate bombs. If this makes a new bomb fall into the vase, or
                                        a double bomb is now a single bomb, it'll detonate that bomb too.
x=(t.substring(0,9)+                    Fill the vase, take the first 9 items
    (t.length>9?t[t.length-1]:''))      If we have more than 9 items, then add the last one
    .split('').reverse().join('');      Flip the instruction string.
c='c=0'+x.replace(/1/g,'+1')            Replace each item with the proper instruction to the ACC
         .replace(/2/g,';c*=2;c=c')
         .replace(/3/g,'-1');
eval(c);return c}                       Eval to get the value of ACC and return it.

```

`f('11231');` returns `2`. Try it online

# Answer
> 1 votes
# Haskell, ~~221 202 181 177~~ 166 ~~souls~~ bytes

```
g(0:r)=r++[0]
g(3:x:r)|0<x,x<3=0:0:g r|1<3=3:g(x:r)
g(x:r)=x:g r
g r=r
v%(x:r)=g(init v++[x])%r
v%[]|v==g v=foldr([id,(+)1,(*)2,(-)1]!!)0v|1<3=g v%[]
(([0..9]>>[0])%)

```

Try it on ideone. Takes items as integer list.

### Usage:

```
*Prelude> (([0..9]>>[0])%) [1,2,1,2,2,1,1,1,1,3,1]
43

```

### (Edit: Old) Explanation:

```
g [] = []                             -- g simulates gravity in the vase
g ('0':r) = r ++ "0"                  -- the first 0 from the bottom is removed
g ('3':x:r) | elem x "12" = "00"++g r -- if a 1 or 2 is on a bomb, explode
            | True = '3' : g(x:r)     -- else continue
g (x:r) = x : g r                     -- no air and no bomb, so check next item

c x = [id,(+)1,(*)2,(-)1]!!(read[x])  -- map 0, 1, 2, 3 to their score functions

f v w (x:r) =                         -- v is the current vase state, w the previous one
               init v++[x]            -- replace last vase element with input
             g(init v++[x])           -- simulate one gravity step
           f(g(init v++[x]))v r       -- repeat, w becomes v
f v w[] | v==w =                      -- if the input is empty and vase reached a fixpoint
                 foldr c 0 v          -- then compute score
        | True = f (g v) v []         -- else simulate another gravity step

vase input = f "0000000000" "" input  -- call f with empty vase, previous vase state and
                                      -- the input as string of numbers

```

---
Tags: code-golf
---


title: Help Me Count to Ten!

text:
# Question
Title: Help Me Count to Ten!
You will write a simple program that prints *exactly* `1 2 3 4 5 6 7 8 9 10` to STDOUT, Console, or your language's closest output method. No other visible output should be seen. Any other code executed must be back-end only.

This is , so the catch is that you **must include the previous answer's source code in your code** ("included code"), comments and all. I have started the first answer down below.

Included code must be an exact replica of the previous code, unchanged and whole. To keep this challenge fair, the included code must not be in a comment. No language may be used twice. You may use languages created after this contest, but it must not be made for this challenge specifically. Please do not use any libraries or frameworks made for this challenge specifically, either.

This is a , so most vote score wins! Please vote on creativeness of code inclusion, which means that if someone who puts included code in a string and throws it away should not score very high. To make sure everyone gets a chance, discourage answers that do not follow the rules. Also, if you give an answer, please do not downvote other answers if they do not deserve it.

Please use the following draft for your answer:

```
#Answer Number: (your number in the chain)
##Language: (programming language used, hyperlinked to official website of language or hyperlink to download compiler)

**Previous Answer:**
(prev answer language)
(link to prev answer)

code

Any additional info. Try it on web and an explanation are highly encouraged.

Bytes Added: (optional, just for my musings. how many bytes you added to previous person's code)

```

# Answer
> 2 votes
# Answer Number: 4

# Language: CSS

Previous answer

```
body:before{content:"0 1 2 3 4 5 6 7 8 9 10";}TLðý?0i<?php echo implode(" ",range(1,10)); die;?>
var textToPrint = '';
for (var i = 1; i < 11; i++) {
  textToPrint += i;
  if (i != 10)
    textToPrint += " ";
}
console.log(textToPrint);

```

https://jsfiddle.net/3tLpp4r2/

# Answer
> 0 votes
# Answer Number: 1

## Language: Javascript

**Previous Answer:**

First Answer, NA

```
var textToPrint = '';
for (var i = 1; i < 11; i++) {
  textToPrint += i;
  if (i != 10)
    textToPrint += " ";
}
console.log(textToPrint);
```

Bytes Added: 139

# Answer
> -1 votes
# Answer Number: 2

## Language: PHP

**Previous answer:** https://codegolf.stackexchange.com/a/101123/38505

```
<?php echo implode(" ",range(1,10)); die;?>
var textToPrint = '';
for (var i = 1; i < 11; i++) {
  textToPrint += i;
  if (i != 10)
    textToPrint += " ";
}
console.log(textToPrint);

```

https://eval.in/685567

I'm unsure if I'm doing this right for the tag .

Prints the desired output, then dies.

# Answer
> -1 votes
# Answer Number: 3

# Language 05AB1E

Previous answer

```
TLðý?0i<?php echo implode(" ",range(1,10)); die;?>
var textToPrint = '';
for (var i = 1; i < 11; i++) {
  textToPrint += i;
  if (i != 10)
    textToPrint += " ";
}
console.log(textToPrint);

```

Try it online!

---
Tags: popularity-contest, answer-chaining
---


title: How to Draw Melting Icicles

text:
# Question
Title: How to Draw Melting Icicles
A sculptor is tasked to creating icicle sculptures for the new museum in Greenland. He has been given specifications by his boss, which consists of two numbers: \[s, m\] or size and melt. Size *must* be an odd number. He was given some photos of real icicles:

```
vvvvv [5, 0]
 vvv
  v

vvvvvvv [7, 0]
 vvvvv
  vvv
   v

vvvvvvv [7, 2]
 vvvvv

vvvvvvv [7, 3]

vvv [3, 1]

```

He needs a program to help draw. Any language allowed. The program needs to take in S and M, any method of input acceptable. You must then print out an ascii art representation of it.

S is how many `v`s are on the first layer. M is how many layers are cut out from the bottom.

This is , so as usual this competition is **byte based**. White space does count for byte counting. Least bytes wins.

*Edit:* You will never get a set of numbers that draws nothing, for example \[5, 3\]. Checking code is *not* required however.

# Answer
> 8 votes
# 05AB1E, 11 bytes

```
;-Ý·¹+'v×.c

;-          Compute x = Input[1]-Input[0]/2  (e.g. 7,2 -> -1.5)
  Ý         Push [0, ..., x]                 (e.g. 7,2 -> [0, -1])
   ·        Multiply each value by 2         (e.g. 7,2 -> [0, -2])
    ¹+      Add Input[0] to each value       (e.g. 7,2 -> [7, 5])
      'v×   String multiply by 'v'
         .c Center all strings and implicitly display them

```

Try it online!

# Answer
> 16 votes
# , 15 bytes

```
Àévò^lYp2x>òÀñd

```

Try it online!

Fairly straightforward.

```
À               " Arg1 times:
 év             "   Insert a 'v'
   ò       ò    " Recursively:
    ^l          "   Break if there is only one character on this line
      Y         "   Yank this line
       p        "   Paste it below us
        2x      "   Delete two characters
          >     "   Indent this line
            À   " Arg2 times:
             ñd "   Delete a line

```

# Answer
> 9 votes
# 05AB1E, 12 bytes

Code:

```
ÅÉ'v×R²F¨}.c

```

Explanation:

```
ÅÉ             # List of uneven numbers: [1, 3, 5, ..., input]
  'v×          # String multiply by 'v', giving ['v', 'vvv', 'vvvvv', ...]
     R         # Reverse the array
      ²F }     # Second input times, do...
        ¨      #   Remove the first element of the array
          .c   # Centralize the array

```

Uses the **CP-1252** encoding. Try it online!

# Answer
> 7 votes
# MATL, 22 bytes

```
'v'itQ2/i-wX"R2&PRZ{Zv

```

Try it online!

### Explanation

```
'v'   % Push character 'v'
it    % Input first number. Duplicate
Q2/   % Add 1 and divide by 2
i-    % Input second number. Subtract
w     % Swap
X"    % Char matrix of 'v' repeated those many times along each dim
R     % Upper triangular part
2&P   % Flip horizontally
R     % Upper triangular part
Z{    % Split char matrix along first dimension into a cell array of strings
Zv    % Remove trailing spaces from each string. Implicitly display

```

# Answer
> 6 votes
# Jelly, 19 bytes

```
Rm-2”vẋµLḶ⁶ẋżðḣL_¥Y

```

**TryItOnline!**

### How?

```
Rm-2”vẋµLḶ⁶ẋżðḣL_¥Y - Main link: s, m
       µ            - monadic chain separation
R                   - range(s)  [1,2,3,...s]
 m-2                - mod -2    [s,s-2,s-4,...,1]
    ”v              - 'v'
      ẋ             - repeat    ['v'*s,...,'vvv','v']  (call this y)
             ð      - dyadic chain separation
        L           - length, effectively (s+1)/2
         Ḷ          - lowered range [0,1,2,...length-1]
          ⁶         - ' '
           ẋ        - repeat ['', ' ', ... ' '*(length-1)]
            ż       - zip with y
                 ¥  - last two links as a dyad
               L    -     length
                _   -     subtract m
              ḣ     - head
                  Y - join with line feeds
                    - implicit print

```

# Answer
> 5 votes
# Ruby, ~~46~~ 44 bytes

```
->s,m{0.upto(s/2-m){|i|puts' '*i+?v*s;s-=2}}

```

2 bytes saved thanks to G B

# Answer
> 5 votes
## Batch, 142 bytes

```
@set/ah=%1-%2-%2
@set s=v
@for /l %%i in (3,2,%1)do @call set s=%%s%%vv
@for /l %%i in (1,2,%h%)do @call echo %%s%%&call set s= %%s:~0,-2%%

```

# Answer
> 4 votes
# Python, ~~76~~ 73 bytes

```
def f(s,m):print"\n".join([' '*(s/2-i/2)+'V'*i for i in range(s,m*2,-2)])

```

**Edit:** Saved 3 bytes thanks to @TuukkaX and @Challenger5 (Thanks!)

# Answer
> 3 votes
## JavaScript (ES6), 57 bytes

```
f=(s,m,p=``)=>s<m+m?``:p+`v`.repeat(s)+`
`+f(s-2,m,p+` `)

```

Outputs a trailing newline. If a leading newline is acceptable, then for 54 bytes:

```
f=(s,m,p=`
`)=>s<m+m?``:p+`v`.repeat(s)+f(s-2,m,p+` `)

```

# Answer
> 3 votes
## Python 2, 63 bytes

```
lambda s,m:'\n'.join((s-x)/2*' '+x*'v'for x in range(s,m*2,-2))

```

# Answer
> 3 votes
# Turtlèd, 53 bytes

```
@v?,:l[v,l][ [ l]rr[ d,ur]ld' l]?<:d[ [ u]d[ ' d]luu]

```

### Try it online!

## Explanation:

```
@v,           set char var to v, write it to cell

   ?:l        take positive int input, move that many character right, move 1 left

      [v,l]   move left back to the v, writing v on all the cells it goes on

           [                   ]                      until the current cell is a space

             [ l]    move left until finding a space
                 rr  move two right

                   [     ]  until cell is a space
                     d,ur   move down, write v, move up and right

                          ld' l    move left, down, write space

                                [end of big loop]

                                  [that part made the "icicle", the next melts some]

                                ?<:
           Take integer input again,
           rotate counterclockwise, move that number right (now up the icicle)

                                    d      move down
                                     [               ] until cell is space
                                       [ u]d   up until space is found, down 1
                                            [ ' d]  until space is found, write space to cell and move down
                                                  luu    move left, up, up
                                                   [end loop]

```

# Answer
> 2 votes
## Java, ~~138~~ 137 bytes

```
void m(int l,int r){int f=l;do{String v="";for(int i=0;i++<l;v+="v");if(l/2<r)break;System.out.printf("%"+f--+"s%n",v);l-=2;}while(l>0);}

```

Ungolfed:

```
void m(int l, int r) {
    int f = l;
    do {
        String v = "";
        for (int i = 0; i++ < l; v += "v");
        if (l / 2 < r) break;
        System.out.printf("%" + f-- + "s%n", v);
        l -= 2;
    } while (l > 0);
}

```

Update: One byte and loop body gone thanks to @ClaytonRamsey.

# Answer
> 1 votes
# C, 83 bytes

```
i,j;f(s,m){for(i=-1;i++<s/2-m;)for(j=-1;++j<=s;)putchar(j<s?j>=i&&s-j>i?86:32:10);}

```

Ungolfed and usage:

```
i,j;
f(s,m){
  for(i=-1;i++<s/2-m;)
    for(j=-1;++j<=s;)
      putchar(j<s ?
                j>=i&&s-j>i ? 86 : 32
                : 10);
}

main() {

  f(5,0);
  f(7,0);
  f(7,2);
  f(7,3);
  f(3,1);

}

```

# Answer
> 1 votes
# Pyth, 21 bytes

```
j<E.e+*kd*hyb\v_Uh/Q2

```

A program that takes input of `S` followed by `M`, newline-separated, and prints the result.

Test suite

**How it works**

```
j<E.e+*kd*hyb\v_Uh/Q2  Program. Inputs: Q, E
                  /Q2  Yield Q // 2
                 h      + 1
                U      Yield [0, 1, 2, ..., Q //2 +1]
               _       Reverse
   .e                  Map over with elements as b and zero-indexed indices as k:
           yb           2 * b
          h              + 1
         *   \v          "v" characters
     +                  prepended with
       k                k
      * d                spaces
 <E                    All but the last E elements
j                      Join on newlines
                       Implicitly print

```

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


title: Koalas, Crabs, and Commapillars

text:
# Question
Title: Koalas, Crabs, and Commapillars
Given two positive integers X and Y, output any combination of the following three ASCII-art animals such that the output contains exactly X commas (`,`) and Y periods (`.`), if it is possible.

1. **Koala:** 1 comma, 2 periods

```
<.,.>

```
2. **Crab:** 2 commas, 2 periods

```
,<..>,

```
3. **Commapillar:** 3 or more commas, 1 period

```
<,,,.>

```

or `<,,,,.>` or `<,,,,,.>` or `<,,,,,,.>` or `<,,,,,,,.>` etc.

If no combination of these animals can produce exactly X commas and Y periods, output a single commaleon who will camouflage the failure:

```
~<.,,>~~

```

The output animals can be in any amounts and any order. They may be in a string, space or newline separated, or else in a list where each animal is one element.

For example, for X = 7, Y = 5, these would all be valid outputs (separated by empty lines):

```
<.,.> <.,.> <,,,,,.>

<.,.>
<,,,,,.>
<.,.>

,<..>, <.,.> <,,,,.>

<,,,,.>
,<..>,
<.,.>

,<..>, <,,,.> ,<..>,

[",<..>,", ",<..>,", "<,,,.>"] (list syntax depends on language)

```

Note that (at least in this example) there are multiple sets of animals than can work. But remember you only need to output any *one* valid solution, if one exists. The number of animals or number of distinct animals does not matter.

For inputs such as X = 3, Y = 3 or X = 1, Y = 5 where there is no solution, the output will always be

```
~<.,,>~~

```

perhaps in a single-element list.

**The shortest code in bytes wins.**

# Answer
> 5 votes
# Ruby, 139 bytes

Lambda function, takes x and y as arguments and returns a string

```
->x,y{c=y-2*n=y-(x>y ?1:0)>>1
x+=-c/2*s=[x-n,c*3].max
x<n||x>n*2?'~<.,,>~~':',<..>, '*(x-n)+'<.,.> '*(2*n-x)+"<%s.> "*c%[?,*s-=c/2*3,?,*3]}

```

If a solution exists, it can be done with all koalas+commapillars or all koalas+crabs.

The principle is to use a minimum of commapillars. If the number is odd, we use 1 commapillar. if even we use 0 commapillars, unless there are more commas than periods, in which case we use 2.

The number of periods used in noncommapillars (crabs + koalas) is necessarily even, and the number of noncommapillars is half `(number of periods)-(number of commapillars)`. If there are insufficient commas for all koalas, or too many for all crabs, no solution is possible. Otherwise, we return a solution.

**Commented in test program**

uses "fail" instead of chameleon for clarity

```
f=->x,y{c=y-2*n=y-(x>y ?1:0)>>1
#n=noncommapillars=y>>1 as they have 2 periods. c=commapillars=y-2*n, 1 for odd y, 0 for even y.
#if x>y there are too many commas to have 0 commapillars for even y. noncommapillars= y-1 >> 1, so 2 commapillars

x+=-c/2*s=[x-n,c*3].max
# s=number of commas allocated to commapillars. x-n to allow all noncommapillars to be koalas, but at least 3 per commapillar.
#-c/2 == -1 if there are commapillars, 0 if not (Ruby truncates toward -inf). Subtract commas for commapillars from x if necessary

x<n||x>n*2?'fail':',<..>, '*(x-n)+'<.,.> '*(2*n-x)+"<%s.> "*c%[?,*s-=c/2*3,?,*3]}
#if x<n (insufficient commas for all koalas) or x>n*2 (too many for all crabs) return fail. Else...
#return string off crabs, koalas, and (using % operator like sprintf) c commapillars (0..2), the second with 3 commas (if present) and the first with the rest.

10.times{|j|10.times{|i|puts "%-20s %s"%[?.*j+?,*i,f[i,j]]}}
#all x,y from 0..9

```

**Output**

```
,                    fail
,,                   fail
,,,                  fail
,,,,                 fail
,,,,,                fail
,,,,,,               fail
,,,,,,,              fail
,,,,,,,,             fail
,,,,,,,,,            fail
.                    fail
.,                   fail
.,,                  fail
.,,,                 <,,,.>
.,,,,                <,,,,.>
.,,,,,               <,,,,,.>
.,,,,,,              <,,,,,,.>
.,,,,,,,             <,,,,,,,.>
.,,,,,,,,            <,,,,,,,,.>
.,,,,,,,,,           <,,,,,,,,,.>
..                   fail
..,                  <.,.>
..,,                 ,<..>,
..,,,                fail
..,,,,               fail
..,,,,,              fail
..,,,,,,             <,,,.> <,,,.>
..,,,,,,,            <,,,,.> <,,,.>
..,,,,,,,,           <,,,,,.> <,,,.>
..,,,,,,,,,          <,,,,,,.> <,,,.>
...                  fail
...,                 fail
...,,                fail
...,,,               fail
...,,,,              <.,.> <,,,.>
...,,,,,             <.,.> <,,,,.>
...,,,,,,            <.,.> <,,,,,.>
...,,,,,,,           <.,.> <,,,,,,.>
...,,,,,,,,          <.,.> <,,,,,,,.>
...,,,,,,,,,         <.,.> <,,,,,,,,.>
....                 fail
....,                fail
....,,               <.,.> <.,.>
....,,,              ,<..>, <.,.>
....,,,,             ,<..>, ,<..>,
....,,,,,            fail
....,,,,,,           fail
....,,,,,,,          <.,.> <,,,.> <,,,.>
....,,,,,,,,         <.,.> <,,,,.> <,,,.>
....,,,,,,,,,        <.,.> <,,,,,.> <,,,.>
.....                fail
.....,               fail
.....,,              fail
.....,,,             fail
.....,,,,            fail
.....,,,,,           <.,.> <.,.> <,,,.>
.....,,,,,,          <.,.> <.,.> <,,,,.>
.....,,,,,,,         <.,.> <.,.> <,,,,,.>
.....,,,,,,,,        <.,.> <.,.> <,,,,,,.>
.....,,,,,,,,,       <.,.> <.,.> <,,,,,,,.>
......               fail
......,              fail
......,,             fail
......,,,            <.,.> <.,.> <.,.>
......,,,,           ,<..>, <.,.> <.,.>
......,,,,,          ,<..>, ,<..>, <.,.>
......,,,,,,         ,<..>, ,<..>, ,<..>,
......,,,,,,,        fail
......,,,,,,,,       <.,.> <.,.> <,,,.> <,,,.>
......,,,,,,,,,      <.,.> <.,.> <,,,,.> <,,,.>
.......              fail
.......,             fail
.......,,            fail
.......,,,           fail
.......,,,,          fail
.......,,,,,         fail
.......,,,,,,        <.,.> <.,.> <.,.> <,,,.>
.......,,,,,,,       <.,.> <.,.> <.,.> <,,,,.>
.......,,,,,,,,      <.,.> <.,.> <.,.> <,,,,,.>
.......,,,,,,,,,     <.,.> <.,.> <.,.> <,,,,,,.>
........             fail
........,            fail
........,,           fail
........,,,          fail
........,,,,         <.,.> <.,.> <.,.> <.,.>
........,,,,,        ,<..>, <.,.> <.,.> <.,.>
........,,,,,,       ,<..>, ,<..>, <.,.> <.,.>
........,,,,,,,      ,<..>, ,<..>, ,<..>, <.,.>
........,,,,,,,,     ,<..>, ,<..>, ,<..>, ,<..>,
........,,,,,,,,,    <.,.> <.,.> <.,.> <,,,.> <,,,.>
.........            fail
.........,           fail
.........,,          fail
.........,,,         fail
.........,,,,        fail
.........,,,,,       fail
.........,,,,,,      fail
.........,,,,,,,     <.,.> <.,.> <.,.> <.,.> <,,,.>
.........,,,,,,,,    <.,.> <.,.> <.,.> <.,.> <,,,,.>
.........,,,,,,,,,   <.,.> <.,.> <.,.> <.,.> <,,,,,.>

```

# Answer
> 4 votes
## Befunge, ~~249~~ 218 bytes

```
&::00p&::00g\`-2/:20p2*-3*:30p\20g-`:!00g20g-*\30g*+:30g-v>:#,_@
"~<.,,>~~"0_v#\g03+`g050`\0:-g02\p05:-\*2g02:-*/6+3g03p04<^
$"<">:#,_40p>:!#|_3-0" >.,,"40g3>3g#<\#-:#1_
0" ,>..<,">:#,_$>:!#|_1-
#@_1-0" >.,.<">:#,_$>:!

```

Try it online!

This is now based on the algorithm in the Ruby answer by Level River St, which provided greater scope for golfing and a significant reduction in size compared to my original solution.

# Answer
> 2 votes
## C#6, ~~321~~ 303 bytes

```
using System.Linq;string F(int x,int y)=>S(x,y)??"~<.,,>~~";string S(int x,int y)=>x<0|y<0?null:y<1?x<1?"":null:y*3>x?S(x-1,y-2)!=null?S(x-1,y-2)+"<.,.> ":S(x-2,y-2)!=null?S(x-2,y-2)+",<..>, ":null:string.Concat(new int[y].Select((_,k)=>k<1?C(x-y*3+3):C(3)));string C(int x)=>$"<{new string(',',x)}.> ";

```

Call `F()`. The other two functions are helpers. repl.it demo

```
// Coalesce failed combinations with commaleon
string F(int x,int y)=>S(x,y)??"~<.,,>~~";
// Get successful combination or null
string S(int x,int y)=>
    x<0|y<0
        // Fail: Out of range
        ?null
        :y<1
            ?x<1
                // Successful: All commas and periods accounted for
                ?""
                // Fail: Not enough periods for commas
                :null
            :y*3>x
                // Not all commapillars
                ?S(x-1,y-2)!=null
                    // Try koala
                    ?S(x-1,y-2)+"<.,.> "
                    // Try crab
                    :S(x-2,y-2)!=null
                        ?S(x-2,y-2)+",<..>, "
                        // Epic fail
                        :null
                // All commapillars
                :string.Concat(new int[y].Select((_,k)=>k<1
                    // This commapillar takes most of commas
                    ?C(x-y*3+3)
                    // The rest each takes 3
                    :C(3)));
// Generate single commapillar
string C(int x)=>$"<{new string(',',x)}.> ";

```

---
Tags: code-golf, ascii-art, kolmogorov-complexity
---


title: Evaluate the B-spline basis

text:
# Question
Title: Evaluate the B-spline basis
B-splines are defined using a set of "knots", "control points", and degree. For the purposes of this challenge, the control points are not needed.

The knots are simply a list of strictly increasing real values (note that real B-splines may have repeated knots, for the purposes of this challenge assume knots are all unique). The degree is a non-negative integer.

The set of polynomial basis functions are recursively defined as (image credit):

where `i` is the `i-th` basis function, and `p` is the degree of the basis function. `u` is the curve parameterization, and `u_j` is the `j'th` knot.

The goal of this challenge is to evaluate all the basis functions for a curve of degree `m` at location `u`.

# Input

Your program/function should take as input 3 parameters:

1. A real value for the location `u`
2. A non-negative integer for the curve degree `m`
3. A list of strictly increasing real values for the knots vector `u_j`

You may take these parameters in any order desired and may mutate the inputs as long as no additional information is added (for example, you may take the knots vector to be a combination of a real pointer and integer length).

The input may come from any source desired (stdio, function parameter, etc.).

You may assume the input describes a valid B-spline and that `u` is in the range of the knots vector.

# Output

Your program/function should output a list of real numbers describing what the basis functions evaluate to. That is, you should output  for all `0 <= i <= n-1-m`, where `n` is the number of knots (For 1-based indexing, then `1 <= i <= n - m`). The output must be accurate to within `1%` or 1000 ULP of the true value, whichever is greater. The output may be to any sink desired (stdout, return value, etc.)

# Examples

All examples are formatted as such:

```
u
m
u_0 u_1 u_2 ...
N_{0,m}(u) N_{1,m}(u) N_{2,m}(u) ...

```

case 1:

```
.5
0
0 0.5 1
0 1

```

case 2:

```
.5
1
-1 0 1 2
0.5 0.5

```

case 3:

```
 0.9
 1
 -1 0 1 2 3
 0.1 0.9 0

```

case 4:

```
 1.1
 1
 -1 0 1 2 3
 0 0.9 0.1

```

case 7:

```
 3
 3
 -1 0 1 2 3 8 10 12 15 20
 0 0.5952381 0.38392857 0.02083333 0 0

```

# Hints

Notice that `N_{p}` depends only on `N_{p-1}`. That means rather than recursing from the top-down, you could start at the base case and work up. While this is faster execution-wise, I'm not sure if this will necessarily produce the shortest code.

Here's a reference implementation using Python3+NumPy for the bottom-up approach:

```
from numpy import *

def basis(knots, m, u):
    # base case
    Ns = 1.*logical_and(knots[:-1] <= u, u < knots[1:])
    # work backwards, starting at the base case up to p=m
    for p in range(1,m+1):
        Ns = (u - knots[:-1-p]) * Ns[:-1] / (knots[p:-1] - knots[:-p-1]) \
             + (knots[p+1:] - u) * Ns[1:] / (knots[p+1:]- knots[1:-p])
    return Ns

```

# Scoring

This is code golf; shortest answer in bytes wins. Standard loopholes are prohibited. You are welcome to use any built-ins desired.

# Answer
# Pyth - ~~83~~ 82 bytes

Jesus, this is long, probably a few redundancies, but the formulas are long. This is a recursive solution that just implements the formulas given. The reference solution seems to be doing something else, but I don't know what. Maybe if I knew more about what all of this does...

```
KEM?H+.x*c-KJ@QG-@Q+GHJgGtHZ.x*c-=T@Qh+GHK-T@QhGghGtHZ&|>K@QGqK@QG<K@QhGgRvzt-lQvz

```

Test Suite.
> 1 votes

# Answer
# Python 2, ~~192~~ 185 bytes

```
D,E,Q=input();J=0;exec"F=lambda u,m,j,i:+(j[i]<=u<j[-~i])if m<1else(u-j[i])/(j[i+m]-j[i])*F(u,~-m,j,i)+(j[-~i+m]-u)/(j[-~i+m]-j[-~i])*F(u,~-m,j,-~i);print F(D,E,Q,J);J+=1;"*(~-len(Q)-E)

```

A direct implementation of the formula given with recursion in the lambda *and* iteration using `exec`. Prompts for input through the command line upon invocation as `u,m,[u_0,u_1,u_2...]` with `u` *always* input as a float (e.g. if `u=1`, then u would still be input as `1.0`) and outputs each of the `len([u_0,u_1,u_2...])-1-u` values on a separate line.

Try it Online! (Ideone)
> 1 votes

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


# Question
Title: Add the Fibonnaci Sequence to the Lucas Sequence
**Background of Lucas Numbers**

The French mathematician, Edouard Lucas (1842-1891), who gave the name to the Fibonacci Numbers, found a similar series occurs often when he was investigating Fibonacci number patterns.

The Fibonacci rule of adding the latest two to get the next is kept, but here we start from 2 and 1 (in this order) instead of 0 and 1 for the (ordinary) Fibonacci numbers. The series, called the Lucas Numbers after him, is defined as follows: where we write its members as Ln, for Lucas:

**Challenge**

**Input**

0 \< x \< ∞
The input will be a positive integer starting at 0.

**Output**

The output must be a positive integer.

**What to do?**

Add the Fibonacci numbers to the Lucas numbers.
You will input the index.
The output will be the addition of the Lucas and Fibonacci numbers.

**Fibonnaci formula:**

> F(0) = 0,
> F(1) = 1,
> F(n) = F(n-1) + F(n-2)

**Lucas formula:**

> L(0) = 2,
> L(1) = 1,
> L(n) = L(n-1) + L(n-2)

**Who wins?**

Standard Code-Golf rules apply, so the shortest answer in bytes wins.

**Test-cases**

> A(0) = 2
> A(1) = 2
> A(5) = 16
> A(10) = 178
> A(19) = 13,530
> A(25) = 242,786

# Answer
# C, 33 bytes

```
A(n){return n<2?2:A(n-1)+A(n-2);}

```
> 1 votes

---
Tags: code-golf, math, sequence, fibonacci, subsequence
---


title: Uniquely separated pixels

text:
# Question
Title: Uniquely separated pixels
For an ***N*** by ***N*** image, find a set of pixels such that no separation distance is present more than once. That is, if two pixels are separated by a distance ***d***, then they are the only two pixels that are separated by exactly ***d*** (using Euclidean distance). *Note that **d** need not be integer.*

The challenge is to find a larger such set than anyone else.

### Specification

No input is required - for this contest ***N*** will be fixed at 619.

<sub>*(Since people keep asking - there's nothing special about the number 619. It was chosen to be large enough to make an optimal solution unlikely, and small enough to let an N by N image be displayed without Stack Exchange automatically shrinking it. Images can be displayed full size up to 630 by 630, and I decided to go with the largest prime that doesn't exceed that.)*</sub>

The output is a space separated list of integers.

Each integer in the output represents one of the pixels, numbered in English reading order from 0. For example for ***N*** = 3, the locations would be numbered in this order:

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

```

You may output progress information during running if you wish, as long as the final scoring output is easily available. You may output to STDOUT or to a file or whatever is easiest for pasting into the Stack Snippet Judge below.

### Example

***N*** = 3

Chosen coordinates:

```
(0,0)
(1,0)
(2,1)

```

Output:

```
0 1 5

```

### Winning

The score is the number of locations in the output. Of those valid answers which have the highest score, the earliest to post output with that score wins.

Your code does not need to be deterministic. You may post your best output.

---

### Related areas for research

*(Thanks to **Abulafia** for the Golomb links)*

While neither of these is the same as this problem, they are both similar in concept and may give you ideas on how to approach this:

Note that the points required for this question are not subject to the same requirements as a Golomb rectangle. A Golomb rectangle extends from the 1 dimensional case by requiring that the ***vector*** from each point to each other be unique. This means that there can be two points separated by a distance of 2 horizontally, and also two points separated by a distance of 2 vertically.

For this question, it is the ***scalar*** distance that must be unique, so there cannot be both a horizontal and a vertical separation of 2. Every solution to this question will be a Golomb rectangle, but not every Golomb rectangle will be a valid solution to this question.

---

### Upper bounds

**Dennis** helpfully pointed out in chat that 487 is an upper bound on the score, and gave a proof:

> According to my CJam code (`619,2m*{2f#:+}%_&,`), there are 118800 unique numbers that can be written as the sum of the squares of two integers between 0 and 618 (both inclusive). n pixels require n(n-1)/2 unique distances between each other. For n = 488, that gives 118828.

So there are 118,800 possible different lengths between all the potential pixels in the image, and placing 488 black pixels would result in 118,828 lengths, which makes it impossible for them all to be unique.

I'd be very interested to hear if anyone has a proof of a lower upper bound than this.

---

### Leaderboard

*(Best answer by each user)*

---

# Stack Snippet Judge

```
canvas=document.getElementById('canvas');ctx=canvas.getContext('2d');information=document.getElementById('information');problemList=document.getElementById('problemList');width=canvas.width;height=canvas.height;area=width*height;function verify(){stop();checkPoints();}function checkPoints(){valid=true;numbers=[];points=[];lengths=[];lengthDetails=[];duplicatedLengths=[];clearCanvas();rawData=pointData.value;splitData=rawData.split(' ');for(i=0;i<splitData.length;i++){datum=splitData[i];if(datum!==''){n=parseInt(datum);if(n>=area||n<0){valid=false;information.innerHTML='Out of range:'+n;break;}if(numbers.indexOf(n)>-1){valid=false;information.innerHTML='Duplicated value:'+n;break;}numbers.push(n);x=n%width;y=Math.floor(n/width);points.push([x,y]);}}if(valid){ctx.fillStyle='black';for(i=0;i<points.length-1;i++){p1=points[i];x1=p1[0];y1=p1[1];drawPoint(x1,y1);for(j=i+1;j<points.length;j++){p2=points[j];x2=p2[0];y2=p2[1];d=distance(x1,y1,x2,y2);duplicate=lengths.indexOf(d);if(duplicate>-1){duplicatedLengths.push(lengthDetails[duplicate]);duplicatedLengths.push([d,[numbers[i],numbers[j]],[x1,y1,x2,y2]]);}lengths.push(d);lengthDetails.push([d,[numbers[i],numbers[j]],[x1,y1,x2,y2]]);}}p=points[points.length-1];x=p[0];y=p[1];drawPoint(x,y);if(duplicatedLengths.length>0){ctx.strokeStyle='red';information.innerHTML='Duplicate lengths shown in red';problemTextList=[];for(i=0;i<duplicatedLengths.length;i++){data=duplicatedLengths[i];length=data[0];numberPair=data[1];coords=data[2];line(coords);specificLineText='<b>'+length+': '+numberPair[0]+' to '+numberPair[1]+'</b> [('+coords[0]+', '+coords[1]+') to ('+coords[2]+', '+coords[3]+')]';if(problemTextList.indexOf(specificLineText)===-1){problemTextList.push(specificLineText);}}problemText=problemTextList.join('<br>');problemList.innerHTML=problemText;}else{information.innerHTML='Valid: '+points.length+' points';}}}function clearCanvas(){ctx.fillStyle='white';ctx.fillRect(0,0,width,height);}function line(coords){x1=coords[0];y1=coords[1];x2=coords[2];y2=coords[3];ctx.beginPath();ctx.moveTo(x1+0.5,y1+0.5);ctx.lineTo(x2+0.5,y2+0.5);ctx.stroke();}function stop(){information.innerHTML='';problemList.innerHTML='';}function distance(x1,y1,x2,y2){xd=x2-x1;yd=y2-y1;return Math.sqrt(xd*xd+yd*yd);}function drawPoint(x,y){ctx.fillRect(x,y,1,1);}
```

```
<input id='pointData' placeholder='Paste data here' onblur='verify()'></input><button>Verify data</button><p id='information'></p><p id='problemList'></p><canvas id='canvas' width='619' height='619'></canvas>
```

# Answer
> 13 votes
# Python 3, ~~135~~ ~~136~~ 137

```
10 6830 20470 47750 370770 148190 306910 373250 267230 354030 30390 361470 118430 58910 197790 348450 381336 21710 183530 305050 2430 1810 365832 99038 381324 39598 262270 365886 341662 15478 9822 365950 44526 58862 24142 381150 31662 237614 118830 380846 7182 113598 306750 11950 373774 111326 272358 64310 43990 200278 381014 165310 254454 12394 382534 87894 6142 750 382478 15982 298326 70142 186478 152126 367166 1162 23426 341074 7306 76210 140770 163410 211106 207962 35282 165266 300178 120106 336110 30958 158 362758 382894 308754 88434 336918 244502 43502 54990 279910 175966 234054 196910 287284 288468 119040 275084 321268 17968 2332 86064 340044 244604 262436 111188 291868 367695 362739 370781 375723 360261 377565 383109 328689 347879 2415 319421 55707 352897 313831 302079 19051 346775 361293 328481 35445 113997 108547 309243 19439 199037 216463 62273 174471 207197 167695 296927

```

Found using a greedy algorithm which, at each stage, chooses the valid pixel whose set of distances to the chosen pixels overlaps the least with that of other pixels.

Specifically, the scoring is

```
score(P) = sum(number of pixels with D in its distance set
               for each D in P's distance set)

```

and the pixel with the lowest score is chosen.

The search is kicked off with the point `10` (i.e. `(0, 10)`). This part is adjustable, so beginning with different pixels may lead to better or worse results.

It's quite a slow algorithm, so I'm trying to add optimisations/heuristics, and maybe some backtracking. PyPy is recommended for speed.

Anyone trying to come up with an algorithm should test on `N = 10`, for which I've got 9 (but this took a *lot* of tweaking and trying different initial points):

## Code

```
from collections import Counter, defaultdict
import sys
import time

N = 619

start_time = time.time()

def norm(p1, p2):
    return (p1//N - p2//N)**2 + (p1%N - p2%N)**2

selected = [10]
selected_dists = {norm(p1, p2) for p1 in selected for p2 in selected if p1 != p2}
pix2dist = {} # {candidate pixel: {distances to chosen}}
dist2pix = defaultdict(set)

for pixel in range(N*N):
    if pixel in selected:
        continue

    dist_list = [norm(pixel, p) for p in selected]
    dist_set = set(dist_list)

    if len(dist_set) != len(dist_list) or dist_set & selected_dists:
        continue

    pix2dist[pixel] = dist_set

    for dist in dist_set:
        dist2pix[dist].add(pixel)

while pix2dist:
    best_score = None
    best_pixel = None

    for pixel in sorted(pix2dist): # Sorting for determinism
        score = sum(len(dist2pix[d]) for d in pix2dist[pixel])

        if best_score is None or score < best_score:
            best_score = score
            best_pixel = pixel

    added_dists = pix2dist[best_pixel]
    selected_dists |= added_dists
    del pix2dist[best_pixel]
    selected.append(best_pixel)

    for d in added_dists:
        dist2pix[d].remove(best_pixel)

    to_remove = set()
    for pixel in pix2dist:
        new_dist = norm(pixel, best_pixel)

        if (new_dist in selected_dists or new_dist in pix2dist[pixel]
                or added_dists & pix2dist[pixel]):
            to_remove.add(pixel)
            continue

        pix2dist[pixel].add(new_dist)
        dist2pix[new_dist].add(pixel)

    for pixel in to_remove:
        for d in pix2dist[pixel]:
            dist2pix[d].remove(pixel)

        del pix2dist[pixel]

    print("Selected: {}, Remaining: {}, Chosen: ({}, {})".format(len(selected), len(pix2dist),
                                                                 best_pixel//N, best_pixel%N))
    sys.stdout.flush()

print(*selected)
print("Time taken:", time.time() - start_time)

```

# Answer
> 5 votes
# SWI-Prolog, score 131

Barely better than the initial answer, but I guess this will get things started a bit more. The algorithm is the same as the Python answer except for the fact that it tries pixels in an alternate way, starting with the top left pixel (pixel 0), then the bottom right pixel (pixel 383160), then pixel 1, then pixel 383159, etc.

```
a(Z) :-
    N = 619,
    build_list(N,Z).

build_list(N,R) :-
    M is N*N,
    get_list([M,-1],[],L),
    reverse(L,O),
    build_list(N,O,[],[],R).

get_list([A,B|C],R,Z) :-
    X is A - 1,
    Y is B + 1,
    (X =< Y,
    Z = R
    ;
    get_list([X,Y,A,B|C],[X,Y|R],Z)).

build_list(_,[],R,_,R) :- !.
build_list(N,[A|T],R,W,Z) :-
    separated_pixel(N,A,R,W,S),
    is_set(S),
    flatten([W|S],V),!,
    build_list(N,T,[A|R],V,Z)
    ;build_list(N,T,R,W,Z).

separated_pixel(N,A,L,W,R) :-
    separated_pixel(N,A,L,[],W,R).

separated_pixel(N,A,[A|T],R,W,S) :-
        separated_pixel(N,A,T,R,W,S).

separated_pixel(N,A,[B|T],R,W,S) :-
    X is (A mod N - B mod N)*(A mod N - B mod N),
    Y is (A//N - B//N)*(A//N - B//N),
    Z is X + Y,
    \+member(Z,W),
    separated_pixel(N,A,T,[Z|R],W,S).

separated_pixel(_,_,[],R,_,R).

```

### Input:

`a(A).`

### Output:

```
Z = [202089, 180052, 170398, 166825, 235399, 138306, 126354, 261759, 119490, 117393, 281623, 95521, 290446, 299681, 304310, 78491, 314776, 63618, 321423, 60433, 323679, 52092, 331836, 335753, 46989, 40402, 343753, 345805, 36352, 350309, 32701, 32470, 352329, 30256, 28089, 357859, 23290, 360097, 22534, 362132, 20985, 364217, 365098, 17311, 365995, 15965, 15156, 368487, 370980, 371251, 11713, 372078, 372337, 10316, 373699, 8893, 374417, 8313, 7849, 7586, 7289, 6922, 376588, 6121, 5831, 377399, 377639, 4941, 378494, 4490, 379179, 3848, 379453, 3521, 3420, 379963, 380033, 3017, 380409, 2579, 380636, 2450, 2221, 2006, 381235, 1875, 381369, 381442, 381682, 1422, 381784, 1268, 381918, 1087, 382144, 382260, 833, 382399, 697, 382520, 622, 382584, 382647, 382772, 384, 382806, 319, 286, 382915, 382939, 190, 172, 383005, 128, 383050, 93, 383076, 68, 383099, 52, 40, 383131, 21, 383145, 10, 383153, 4, 383158, 1, 383160, 0]

```

### Image from Stack Snippet

# Answer
> 4 votes
# Haskell—~~115~~ ~~130~~ ~~131~~ ~~135~~ 136

My inspiration was the Sieve of Eratosthenes and in particular The Genuine Sieve of Eratosthenes, a paper by Melissa E. O'Neill of Harvey Mudd College. My original version (which considered points in index order) sieved points *extremely* quickly, for some reason I can't recall I decided to shuffle the points before “sieving” them in this version (I think solely to make generating different answers easier by using a new seed in the random generator). Because the points are no longer in any sort of order there's not really any sieving going on anymore, and as a result it takes a couple minutes just to produce this single 115 point answer. A knockout `Vector` would probably be a better choice now.

So with this version as a checkpoint I see two branches, returning to the “Genuine Sieve” algorithm and leveraging the List monad for choice, or swapping out the `Set` operations for equivalents on `Vector`.

**Edit:** So for working version two I veered back toward the sieve algorithm, improved the generation of “multiples” (knocking indices out by finding points at integer coordinates on circles with radius equal to the distance between any two points, akin to generating prime multiples) and making a few constant time improvements by avoiding some needless recalculation.

For some reason I can't recompile with profiling turned on, but I believe that the major bottleneck now is backtracking. I think exploring a bit of parallelism and concurrency will produce linear speedups, but memory exhaustion will probably cap me at a 2x improvement.

**Edit:** Version 3 meandered a bit, I first experimented with a heuristic in taking the next 𝐧 indices (after sieving from earlier choices) and choosing the one that produced the next minimum knockout set. This ended up being far too slow, so I went back to a whole-searchspace brute force method. An idea to order the points by distance from some origin came to me, and led to an improvement by one single point (in the time my patience lasted). This version picks index 0 as the origin, it may be worth trying the center point of the plane.

**Edit:** I picked up 4 points by re-ordering the search space to prioritize the most distant points from the center. If you're testing my code, ~~135~~ 136 is actually the ~~second~~ third solution found. *Fast edit:* This version seems the most likely to keep being productive if left running. I suspect I may tie at 137, then run out of patience waiting for 138.

One thing I noticed (that may be of help to someone) is that if you set the point ordering from the center of the plane (i.e., remove `(d*d -)` from `originDistance`) the image formed looks a bit like a sparse prime spiral.

```
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE BangPatterns #-}

module Main where

import Data.Function (on)
import Data.List     (tails, sortBy)
import Data.Maybe    (fromJust)
import Data.Ratio
import Data.Set      (fromList, toList, union, difference, member)

import System.IO

sideLength :: Int
sideLength = 619

data Point = Point {  x :: !Int,  y :: !Int } deriving (Ord, Eq)
data Delta = Delta { da :: !Int, db :: !Int }

euclidean :: Delta -> Int
euclidean Delta{..} = da*da + db*db

instance Eq Delta where
  (==) = (==) `on` euclidean

instance Ord Delta where
  compare = compare `on` euclidean

delta :: Point -> Point -> Delta
delta a b = Delta (min dx dy) (max dx dy)
  where
    dx = abs (x a - x b)
    dy = abs (y a - y b)

equidistant :: Dimension -> Point -> Point -> [Point]
equidistant d a b =
  let
    (dx, dy) = (x a - x b, y a - y b)
    m = if dx == 0 then Nothing else Just (dy % dx)                    -- Slope
    w = if dy == 0 then Nothing else Just $ maybe 0 (negate . recip) m -- Negative reciprocal
    justW = fromJust w -- Moral bankruptcy
    (px, py) = ((x a + x b) % 2, (y a + y b) % 2)                      -- Midpoint
    b0 = py - (justW * px)                                             -- Y-intercept
    f q = justW * q + b0                                               -- Perpendicular bisector
  in
   maybe (if denominator px == 1 then map (Point (numerator px)) [0..d - 1] else [])
         ( map (\q -> Point q (numerator . f . fromIntegral $ q))
         . filter ((== 1) . denominator . f . fromIntegral)
         )
         (w >> return [0..d - 1])

circle :: Dimension -> Point -> Delta -> [Point]
circle d p delta' =
  let
    square = (^(2 :: Int))
    hypoteneuse = euclidean delta'
    candidates = takeWhile ((<= hypoteneuse) . square) [0..d - 1]
    candidatesSet = fromList $ map square [0..d - 1]
    legs = filter ((`member` candidatesSet) . (hypoteneuse -) . square) candidates
    pythagoreans = zipWith Delta legs
                 $ map (\l -> floor . sqrt . (fromIntegral :: Int -> Double) $ hypoteneuse - square l) legs
  in
    toList . fromList $ concatMap (knight p) pythagoreans

knight :: Point -> Delta -> [Point]
knight Point{..} Delta{..} =
    [ Point (x + da) (y - db), Point (x + da) (y + db)
    , Point (x + db) (y - da), Point (x + db) (y + da)
    , Point (x - da) (y - db), Point (x - da) (y + db)
    , Point (x - db) (y - da), Point (x - db) (y + da)
    ]

type Dimension = Int
type Index = Int

index :: Dimension -> Point -> Index
index d Point{..} = y * d + x

point :: Dimension -> Index -> Point
point d i = Point (i `rem` d) (i `div` d)

valid :: Dimension -> Point -> Bool
valid d Point{..} = 0 <= x && x < d
                 && 0 <= y && y < d

isLT :: Ordering -> Bool
isLT LT = True
isLT _  = False

sieve :: Dimension -> [[Point]]
sieve d = [i0 : sieve' is0 [i0] [] | (i0:is0) <- tails . sortBy originDistance . map (point d) $ [0..d*d - 1]]
  where
    originDistance :: Point -> Point -> Ordering
    originDistance = compare `on` ((d*d -) . euclidean . delta (point d (d*d `div` 2)))

    sieve' :: [Point] -> [Point] -> [Delta] -> [Point]
    sieve' []     _  _ = []
    sieve' (i:is) ps ds = i : sieve' is' (i:ps) ds'
      where
        ds' = map (delta i) ps ++ ds
        knockouts = fromList [k | d' <- ds
                                , k  <- circle d i d'
                                , valid d k
                                , not . isLT $ k `originDistance` i
                                ]
            `union` fromList [k | q  <- i : ps
                                , d' <- map (delta i) ps
                                , k  <- circle d q d'
                                , valid d k
                                , not . isLT $ k `originDistance` i
                                ]
            `union` fromList [e | q <- ps
                                , e <- equidistant d i q
                                , valid d e
                                , not . isLT $ e `originDistance` i
                                ]
        is' = sortBy originDistance . toList $ fromList is `difference` knockouts

main :: IO ()
main = do let answers = strictlyIncreasingLength . map (map (index sideLength)) $ sieve sideLength
          hSetBuffering stdout LineBuffering
          mapM_ (putStrLn . unwords . map show) $ answers
  where
    strictlyIncreasingLength :: [[a]] -> [[a]]
    strictlyIncreasingLength = go 0
      where
        go _ []     = []
        go n (x:xs) = if n < length x then x : go (length x) xs else go n xs

```

## Output

```
1237 381923 382543 382541 1238 1857 380066 5 380687 378828 611 5571 382553 377587 375113 3705 8664 376356 602 1253 381942 370161 12376 15475 7413 383131 367691 380092 376373 362114 36 4921 368291 19180 382503 26617 3052 359029 353451 29716 382596 372674 352203 8091 25395 12959 382479 381987 35894 346031 1166 371346 336118 48276 2555 332400 46433 29675 380597 13066 382019 1138 339859 368230 29142 58174 315070 326847 56345 337940 2590 382663 320627 70553 19278 7309 82942 84804 64399 5707 461 286598 363864 292161 89126 371267 377122 270502 109556 263694 43864 382957 824 303886 248218 18417 347372 282290 144227 354820 382909 380301 382808 334361 375341 2197 260623 222212 196214 231526 177637 29884 251280 366739 39442 143568 132420 334718 160894 353132 78125 306866 140600 297272 54150 240054 98840 219257 189278 94968 226987 265881 180959 142006 218763 214475

```

# Answer
> 3 votes
# Python 3, score 129

This is an example answer to get things started.

Just a naive approach going through the pixels in order and choosing the first pixel that doesn't cause a duplicate separation distance, until the pixels run out.

### Code

```
width = 619
height = 619
area = width * height
currentAttempt = 0

temporaryLengths = []
lengths = []
points = []
pixels = []
for i in range(area):
    pixels.append(0)

def generate_points():
    global lengths
    while True:
        candidate = vacantPixel()
        if isUnique(candidate):
            lengths += temporaryLengths
            pixels[candidate] = 1
            points.append(candidate)
            print(candidate)
        if currentAttempt == area:
            break
    filename = 'uniquely-separated-points.txt'
    with open(filename, 'w') as file:
        file.write(' '.join(points))

def isUnique(n):
    x = n % width
    y = int(n / width)
    temporaryLengths[:] = []
    for i in range(len(points)):
        point = points[i]
        a = point % width
        b = int(point / width)
        d = distance(x, y, a, b)
        if d in lengths or d in temporaryLengths:
            return False
        temporaryLengths.append(d)
    return True

def distance(x1, y1, x2, y2):
    xd = x2 - x1
    yd = y2 - y1
    return (xd*xd + yd*yd) ** 0.5

def vacantPixel():
    global currentAttempt
    while True:
        n = currentAttempt
        currentAttempt += 1
        if pixels[n] == 0:
            break
    return n

generate_points()

```

### Output

```
0 1 3 7 12 20 30 44 65 80 96 122 147 181 203 251 289 360 400 474 564 592 627 660 747 890 1002 1155 1289 1417 1701 1789 1895 2101 2162 2560 2609 3085 3121 3331 3607 4009 4084 4242 4495 5374 5695 6424 6762 6808 7250 8026 8356 9001 9694 10098 11625 12881 13730 14778 15321 16091 16498 18507 19744 20163 20895 23179 25336 27397 31366 32512 33415 33949 39242 41075 46730 47394 48377 59911 61256 66285 69786 73684 79197 89530 95447 102317 107717 111751 116167 123198 126807 130541 149163 149885 154285 159655 163397 173667 173872 176305 189079 195987 206740 209329 214653 220911 230561 240814 249310 269071 274262 276855 285295 305962 306385 306515 312310 314505 324368 328071 348061 350671 351971 354092 361387 369933 376153

```

### Image from Stack Snippet

# Answer
> 3 votes
# Python, 134 132

Here's a simple one that randomly culls some of the search space to cover a greater area. It iterates the points in distance from an origin order. It skips points that are same distance from origin, and early-outs if it cannot improve on the best. It runs indefinitely.

```
from random import *
from bisect import *

W = H = 619
pts = []
deepest = 0
lengths = set()

def place(x, y):
    global lengths
    pos = (x, y)
    for px, py in pts:
        dist = (x-px)*(x-px) + (y-py)*(y-py)
        if dist in lengths:
            return False
    dists = set((x-px)*(x-px) + (y-py)*(y-py) for px, py in pts)
    if len(dists) != len(pts):
        return False
    lengths |= dists
    pts.append(pos)
    return True

def unplace():
    x, y = pos = pts.pop()
    for px, py in pts:
        dist = (x-px)*(x-px) + (y-py)*(y-py)
        lengths.remove(dist)

def walk(i):
    global deepest, backtrack
    depth = len(pts)
    while i < W*H:
        d, x, y, rem = order[i]
        if rem+depth <= deepest: # early out if remaining unique distances mean we can't improve
            return
        i += 1
        if place(x, y):
            j = i
            while j < W*H and order[j][0] == d: # skip those the same distance from origin
                j += 1
            walk(j)
            unplace()
            if backtrack <= depth:
                break
            if not randint(0, 5): # time to give up and explore elsewhere?
                backtrack = randint(0, len(pts))
                break
            backtrack = W*H # remove restriction
    if depth >= deepest:
        deepest = depth
        print (ox, oy), depth, "=", " ".join(str(y*W+x) for x, y in pts)

try:
    primes = (0,1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97)
    while True:
        backtrack = W*H
        ox, oy = choice(primes), choice(primes) # random origin coordinates
        order = sorted((float((ox-x)**2+(oy-y)**2)+random(), x, y) for x in xrange(W) for y in xrange(H))
        rem = sorted(set(int(o[0]) for o in order)) # ordered list of unique distances
        rem = {r: len(rem)-bisect_right(rem, r) for r in rem} # for each unique distance, how many remain?
        order = tuple((int(d), x, y, rem[int(d)]) for i, (d, x, y) in enumerate(order))
        walk(0)
except KeyboardInterrupt:
    print

```

It quickly finds solutions with 134 points:

3097 3098 2477 4333 3101 5576 1247 9 8666 8058 12381 1257 6209 15488 6837 21674 19212 26000 24783 1281 29728 33436 6863 37767 26665 14297 4402 43363 50144 52624 18651 9996 58840 42792 6295 69950 48985 34153 10644 72481 83576 63850 29233 94735 74997 60173 43477 101533 102175 24935 113313 88637 122569 11956 36098 79401 61471 135610 31796 4570 150418 57797 4581 125201 151128 115936 165898 127697 162290 33091 20098 189414 187620 186440 91290 206766 35619 69033 351 186511 129058 228458 69065 226046 210035 235925 164324 18967 254416 130970 17753 248978 57376 276798 456 283541 293423 257747 204626 298427 249115 21544 95185 231226 54354 104483 280665 518 147181 318363 1793 248609 82260 52568 365227 361603 346849 331462 69310 90988 341446 229599 277828 382837 339014 323612 365040 269883 307597 374347 316282 354625 339821 372016

For the curious, here are some brute-forced small N:

```
3  =  0  2  3
4  =  0  2  4  7
5  =  0  2  5 17 23
6  =  0 12 21 28 29 30
7  =  4  6 11 14 27 36 42
8  =  0  2  8 11 42 55 56
9  =  0  2  9 12 26 50 63 71
10 =  0  2  7 10 35 75 86 89  93
11 =  0 23 31 65 66 75 77 95 114 117

```

# Answer
> 3 votes
# Python 3, 130

For comparison, here's a recursive backtracker implementation:

```
N = 619

def norm(p1, p2):
    return (p1//N - p2//N)**2 + (p1%N - p2%N)**2

def solve(selected, dists):
    global best

    if len(selected) > best:
        print(len(selected), "|", *selected)
        best = len(selected)

    for pixel in (range(selected[-1]+1, N*N) if selected else range((N+1)//2+1)):
        # By symmetry, place first pixel in first half of top row
        added_dists = [norm(pixel, p) for p in selected]
        added_set = set(added_dists)

        if len(added_set) != len(added_dists) or added_set & dists:
            continue

        selected.append(pixel)
        dists |= added_set

        solve(selected, dists)

        selected.pop()
        dists -= added_set

print("N =", N)
best = 0
selected = []
dists = set()
solve(selected, dists)

```

It finds the following 130 pixel solution quickly before it starts choking:

```
0 1 3 7 12 20 30 44 65 80 96 122 147 181 203 251 289 360 400 474 564 592 627 660 747 890 1002 1155 1289 1417 1701 1789 1895 2101 2162 2560 2609 3085 3121 3331 3607 4009 4084 4242 4495 5374 5695 6424 6762 6808 7250 8026 8356 9001 9694 10098 11625 12881 13730 14778 15321 16091 16498 18507 19744 20163 20895 23179 25336 27397 31366 32512 33415 33949 39242 41075 46730 47394 48377 59911 61256 66285 69786 73684 79197 89530 95447 102317 107717 111751 116167 123198 126807 130541 149163 149885 154285 159655 163397 173667 173872 176305 189079 195987 206740 209329 214653 220911 230561 240814 249310 269071 274262 276855 285295 305962 306385 306515 312310 314505 324368 328071 348061 350671 351971 354092 361387 371800 376153 378169

```

More importantly, I'm using it to check solutions for small cases. For `N <= 8`, the optimal are:

```
1: 1 (0)
2: 2 (0 1)
3: 3 (0 1 5)
4: 4 (0 1 6 12)
5: 5 (0 1 4 11 23)
6: 6 (0 1 9 23 32 35)
7: 7 (0 2 9 20 21 40 48)
8: 7 (0 1 3 12 22 56 61)
9: 8 (0 1 3 8 15 37 62 77)
10: 9 (0 1 7 12 30 53 69 80 89)

```

Listed in brackets are the first lexicographical optimals.

Unconfirmed:

```
11: 10 (0 2 3 7 21 59 66 95 107 120)
12: 10 (0 1 3 7 33 44 78 121 130 140)

```

# Answer
> 3 votes
# Scala, 132

Scans left-to-right and top-to-bottom like the naive solution, but tries starting at different pixel locations.

```
import math.pow
import math.sqrt

val height, width = 619
val area = height * width

case class Point(x: Int, y: Int)

def generate(n: Int): Set[Point] = {

  def distance(p: Point, q: Point) = {
    def square(x: Int) = x * x
    sqrt(square(q.x - p.x) + square(q.y - p.y))
  }

  def hasDuplicates(s: Seq[_]) = s.toSet.size != s.size

  def rotate(s: Vector[Point]): Vector[Point] = s.drop(n) ++ s.take(n)

  val remaining: Vector[Point] =
    rotate((for (y <- 0 until height; x <- 0 until width) yield { Point(x, y) }).toVector)
  var unique = Set.empty[Point]
  var distances = Set.empty[Double]
  for (candidate <- remaining) {
    if (!unique.exists(p => distances.contains(distance(candidate, p)))) {
      val candidateDistances = unique.toSeq.map(p => distance(candidate, p))
      if (!hasDuplicates(candidateDistances)) {
        unique = unique + candidate
        distances = distances ++ candidateDistances
      }
    }
  }
  unique
}

def print(s: Set[Point]) = {
  def toRowMajor(p: Point) = p.y*height + p.x
  println(bestPixels.map(toRowMajor).toSeq.sorted.mkString(" "))
}

var bestPixels = Set.empty[Point]
for (n <- 0 until area) {
  val pixels = generate(n)
  if (pixels.size > bestPixels.size) bestPixels = pixels
}
print(bestPixels)

```

# Output

```
302 303 305 309 314 322 332 346 367 382 398 424 449 483 505 553 591 619 647 680 719 813 862 945 1014 1247 1459 1700 1740 1811 1861 1979 2301 2511 2681 2913 3114 3262 3368 4253 4483 4608 4753 5202 5522 5760 6246 6474 6579 6795 7498 8062 8573 8664 9903 10023 10567 10790 11136 12000 14153 15908 17314 17507 19331 20563 20941 22339 25131 26454 28475 31656 38328 39226 40214 50838 53240 56316 60690 61745 62374 68522 71208 78598 80204 86005 89218 93388 101623 112924 115702 118324 123874 132852 136186 139775 144948 154274 159730 182200 193642 203150 203616 213145 214149 218519 219744 226729 240795 243327 261196 262036 271094 278680 282306 289651 303297 311298 315371 318124 321962 330614 336472 343091 346698 354881 359476 361983 366972 369552 380486 382491

```

# Answer
> 2 votes
## Fantom 96

I used an evolution algorithm, basically add k random points at a time, do that for j different random sets, then pick the best one and repeat. Pretty terrible answer right now, but that's running it with only 2 children per generation for the sake of speed, which is nearly just random. Gonna play with the parameters a bit to see how it goes, and I probably need a better scoring function than number of free spots left.

```
class Pixel
{
  static const Int n := 619
  static const Int stepSize := 20
  static const Int generationSize := 5
  static const |Int, Int -> Int| d := |Int x, Int y -> Int| {
      d1 := x%n - y%n
      d2 := x/n - y/n
      return d1.pow(2) + d2.pow(2)
    }

  public static Void main(){

    //Initialize

    [Int: Int[][]] disMap := [:]
    Int[] freeSpots := (0..<n*n).toList
    Int[] pixels := [,]
    Int[] distances := [,]

    genNum := 0
    children := [,]
    while(freeSpots.size > 0){
      echo("Generation: ${genNum++} \t Spots Left: ${freeSpots.size} \t Pixels added: $pixels.size \t Distances used: $distances.size uniqueDistances: $distances.unique.size" )
      echo(distances)
      echo("Pixels: " + pixels.join(" "))
      //echo("Distances: $distances")
      //Generate children
      children = [,]
      generationSize.times{
        //echo("\tStarting child $it")
        i := Int.random(0..<freeSpots.size)
        childFreeSpots := freeSpots.dup
        childPixels := pixels.dup
        childDistances := distances.dup

        for(Int step := 0; step < stepSize; step++){

          if( i < childFreeSpots.size){
            //Choose a pixel
            pixel := childFreeSpots.removeAt(i)
            //echo("\t\tAdding pixel $pixel")

            //Remove neighbors that are the new distances away
            ///Find distances
            newDis := [,]
            childPixels.each {
              newDis.add(d(pixel, it))
            }

            //Check that there are no equal distances
            if(newDis.size != newDis.unique.size) continue

            //Remove neighbors
            childPixels.each | Int childPixel|{
              newDis.each |Int dis|{
                neighbors := getNeighbors(childPixel, dis, disMap)
                neighbors.each| Int n |{
                  index := childFreeSpots.binarySearch(n)
                  if(index >= 0) childFreeSpots.removeAt(index)
                }
              }
            }
            //echo("Removed neighbors: $test")
            //Remove all the neighbors of new pixel
            childDistances.addAll(newDis)
            childDistances.each|Int dis| {
              neighbors := getNeighbors(pixel, dis, disMap)
              childFreeSpots.removeAll(neighbors)
            }

            //Add new pixel
            childPixels.add(pixel)
          }
        }
        children.add([childPixels.dup, childDistances.dup, childFreeSpots.dup])
        echo("\tChild $it: pixels: $childPixels.size \t distances: $childDistances.size \t freeSpots: $childFreeSpots.size")
      }

      //Score children and keep best one as new parent
      Obj?[][] parent := children.max |Int[][] a, Int[][] b -> Int| { return (a.last.size  + a.first.size*10000) <=> (b.last.size + b.first.size*10000)  }
      pixels = parent.first
      distances = parent[1]
      freeSpots = parent.last

    }//End while

    //Return result
    echo("Size: " + pixels.size)
    echo(pixels.join(" "))

  }

  private static Bool checkValid(Int[] pixels){
    distances := [,]
    pixels[0..-2].each|Int p, Int i|{
      for(Int j := i + 1; j < pixels.size; j++){
        distances.add(d(p, pixels[j]))
      }
    }
    if(distances.size > distances.unique.size){
      echo("Duplicate distance found!!!!")
      echo("Pixel $pixels.last is not valid")
      return false
    }
    return true
  }

  public static Int[] getNeighbors(Int spot, Int distance, [Int : Int[][]] disMap ){
    result := [,]
    //Check hash map
    pairs := disMap.get(distance, null)

    //Find possible int pairs if not already in the map
    if(pairs == null){
      for(Int i := 0; i*i <= distance; i++ ){
        for(Int j := i; j*j + i*i <= distance; j++){
          if(i.pow(2) + j.pow(2) == distance){
            pairs.add([i, j])
          }
        }
      }
      disMap.add(distance, pairs)
    }

    pairs.each|Int[] pair|{
      //Find neighbors with pair
      x := pair.first
      y := pair.last
      2.times{
        //Positive x
        result.add(spot + x + y*n)
        result.add(spot + x - y*n)

        //negative x
        result.add(spot - x + y*n)
        result.add(spot - x - y*n)

        //Swap x and y and repeat
        temp := x
        x = y
        y = temp
      }
    }

    return result.findAll |Int i -> Bool| { i >= 0 }.unique
  }

}

```

Output

```
17595 17596 17601 17627 17670 17726 17778 17861 17956 18117 18324 18733 19145 19597 20244 21139 21857 22742 24078 25343 28577 30152 32027 34406 37008 39864 42313 44820 48049 52193 55496 59707 64551 69976 74152 79758 84392 91782 98996 104625 150212 158877 169579 178660 189201 201343 213643 225998 238177 251012 263553 276797 290790 304915 319247 332702 347266 359665 373683 125899 144678 170677 195503 220092 244336 269861 289473 308633 326736 343756 358781 374280 131880 172485 212011 245015 277131 302055 321747 347911 363717 379166 249798 284200 313870 331913 360712 378024 9704 141872 249686 293656 357038 357596 370392 381963

```

# Answer
> 1 votes
# Python 3, 119

I no longer remember why I named this function `mc_usp`, though I suspect it had something to do with Markov chains. Here I publish my code that I ran with PyPy for about 7 hours. The program tries to build up 100 different sets of pixels by randomly picking pixels until it has checked every pixel in the image, and returning one of the best sets.

On another note, at some point, we should really attempt to find an upper bound for `N=619` that's better than 488, because judging from the answers on here, that number is way too high. Rowan Blush's comment about how every new point `n+1` can potentially remove `6*n` points with optimal choice seemed like a good idea. Unfortunately, upon inspection of the formula `a(1) = 1; a(n+1) = a(n) + 6*n + 1`, where `a(n)` is the number of points removed after adding `n` points to our set, this idea may not be the best fit. Checking when `a(n)` is greater than `N**2`, `a(200)` being larger than `619**2` seems promising, but the `a(n)` larger than `10**2` is `a(7)` and we've proved that 9 is the actual upper bound for `N=10`. I'll keep you posted as I try to look a better upper bound, but any suggestions are welcome.

Onto my answer. First, my set of 119 pixels.

```
15092 27213 294010 340676 353925 187345 127347 21039 28187 4607 23476 324112 375223 174798 246025 185935 186668 138651 273347 318338 175447 316166 158342 97442 361309 251283 29986 98029 339602 292202 304041 353401 236737 324696 42096 102574 357602 66845 40159 57866 3291 24583 254208 357748 304592 86863 19270 228963 87315 355845 55101 282039 83682 55643 292167 268632 118162 48494 378303 128634 117583 841 178939 20941 161231 247142 110205 211040 90946 170124 362592 327093 336321 291050 29880 279825 212675 138043 344012 187576 168354 28193 331713 329875 321927 129452 163450 1949 186448 50734 14422 3761 322400 318075 77824 36391 31016 33491 360713 352240 45316 79905 376004 310778 382640 383077 359178 14245 275451 362125 268047 23437 239772 299047 294065 46335 112345 382617 79986

```

Second, my code, which randomly picks a starting point from an octant of the 619x619 square (since the starting point is otherwise equal under rotation and reflection) and then every other point from the rest of the square.

```
import random
import time

start_time = time.time()
print(start_time)

def mc_usp_v3(N, z, k=100, m=1.0):
    """
    At m=1.0, it keeps randomly picking points until we've checked every point. Oh dear.
    """
    ceil = -(-N//2)
    a=random.randint(0,ceil)
    b=random.randint(a,ceil)
    r=[a*N+b]

    best_overall = r[:]
    all_best = []
    best_in_shuffle = r[:]
    num_shuffles = 0
    num_missteps = 0
    len_best = 1

    while num_shuffles < k and len(best_overall) < z:
        dist = []
        missteps = []
        points_left = list(range(N*N))
        points_left.remove(r[0])

        while len_best + num_missteps < m*N*N and len(points_left):
            index = random.randint(0, len(points_left)-1)
            point = points_left[index]
            points_left.pop(index)
            dist, better = euclid(r, point, dist, N)

            if better and len(r) + 1 > len_best:
                r.append(point)
                best_in_shuffle = r[:]
                len_best += 1
            else:
                missteps.append(point)
                num_missteps += 1

        else:
            print(num_shuffles, len(best_overall), len_best, num_missteps, time.time() - start_time)

            num_shuffles += 1
            num_missteps = 0
            missteps = []

            if len(best_in_shuffle) == len(best_overall):
                all_best.append(best_in_shuffle)
                print(best_in_shuffle)

            if len(best_in_shuffle) > len(best_overall):
                best_overall = best_in_shuffle[:]
                all_best = [best_overall]
                print(best_overall)
            a=random.randint(0,ceil)
            b=random.randint(a,ceil)
            r=[a*N+b]
            best_in_shuffle = r[:]
            len_best = 1
    return len(best_overall), all_best

def euclid(point_set, new_point, dist, N):
    new_dist = []
    unique = True
    a,b=divmod(new_point, N)
    for point in point_set:
        c,d=divmod(point, N)
        current_dist = (a-c)**2+(b-d)**2
        if current_dist in dist or current_dist in new_dist:
            unique = False
            break
        new_dist.append(current_dist)
    if unique:
        dist += new_dist
    return dist, unique

def mcusp_format(mcusp_results):
    length, all_best = mcusp_results
    return " ".join(str(i) for i in all_best[0])

print(mcusp_format(mc_usp_v3(10, 20, 100, 1.0)))
print(mcusp_format(mc_usp_v3(619, 488, 100, 1.0)))
print(time.time()-start_time)

```

---
Tags: code-challenge, grid, optimization
---