title: Toggle, Print, Repeat

text:
# Question
Title: Toggle, Print, Repeat
*This challenge is loosely inspired by the unimplemented esolang Pada.*

Consider an array of 8 bits, all initialised to zero. We'll introduce a very minimalistic instruction set to print arbitrary strings. There are two instructions, both of which take a parameter `N` which is the index of a bit:

* `t N` for **t**oggle: This changes the value of bit `N`.
* `p N` for **p**rint: This interprets all 8 bits as a byte, *starting from bit `N` and wrapping around the end*. The character corresponding to this byte is printed to STDOUT.

Let's look an example. We want to print `:=`. Naively we achieve this as follows (0-based bit indices):

```
t 2    [0 0 1 0 0 0 0 0]
t 3    [0 0 1 1 0 0 0 0]
t 4    [0 0 1 1 1 0 0 0]
t 6    [0 0 1 1 1 0 1 0]
p 0    [0 0 1 1 1 0 1 0] == 58 == ':'
t 5    [0 0 1 1 1 1 1 0]
t 6    [0 0 1 1 1 1 0 0]
t 7    [0 0 1 1 1 1 0 1]
p 0    [0 0 1 1 1 1 0 1] == 61 == '='

```

But instead, we can make use of the cyclic feature of `p` and save two instructions:

```
t 2    [0 0 1 0 0 0 0 0]
t 3    [0 0 1 1 0 0 0 0]
t 4    [0 0 1 1 1 0 0 0]
t 6    [0 0 1 1 1 0 1 0]
p 0    [0 0 1 1 1 0 1 0] == 58 == ':'
t 1    [0 1 1 1 1 0 1 0]
p 7    [0 1 1 1 1 0 1 0] == [0 0 1 1 1 1 0 1] == 61 == '='
                      ^

```

So `p 7` simply starts reading the byte value from the last bit instead of the first.

## The Challenge

Given a non-empty string of printable ASCII characters (0x20 to 0x7E, inclusive), produce an optimal list of instructions (one line per instruction) to print that string with the above system. If there are multiple optimal solutions (which will almost always be the case), generate only one of them.

You may choose between 0-based and 1-based indexing for the bits, but please state your choice.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter. If you don't print the result to STDOUT, it should still be a single newline-separated string.

This is code golf, so the shortest answer (in bytes) wins.

## Test Cases

Each test case is a single line containing the input string, followed by the optimal number of instructions, followed by one possible solution.

You should *not* output the instruction count in your solution - this is only included here so you can check the correctness of your code if it prints a different instruction list.

```
?
7 instructions
t 2
t 3
t 4
t 5
t 6
t 7
p 0

:=
7 instructions
t 2
t 3
t 4
t 6
p 0
t 1
p 7

0123456789
26 instructions
t 2
t 3
p 0
t 7
p 0
t 6
t 7
p 0
t 7
p 0
t 5
t 6
t 7
p 0
t 7
p 0
t 6
t 7
p 0
t 7
p 0
t 2
t 3
p 3
t 2
p 3

9876543210
28 instructions
t 2
t 3
t 4
t 7
p 0
t 7
p 0
t 0
t 7
p 5
t 4
p 5
t 0
t 5
p 0
t 7
p 0
t 5
t 6
t 7
p 0
t 7
p 0
t 6
t 7
p 0
t 7
p 0

Hello, World!
39 instructions
t 1
t 4
p 0
t 3
t 7
p 2
t 1
t 6
p 2
p 2
t 0
t 1
p 2
t 0
t 1
t 3
p 2
t 6
t 7
p 2
t 0
t 2
t 6
t 7
p 1
t 0
t 1
t 5
p 0
t 2
t 7
p 3
t 2
t 6
p 0
t 4
p 0
t 1
p 3

The quick brown fox jumps over the lazy dog.
150 instructions
t 1
t 3
t 5
p 0
t 1
t 2
p 1
t 1
t 3
t 7
p 0
t 1
t 5
t 7
p 0
t 1
t 3
t 7
p 0
t 5
p 0
t 3
t 4
t 5
p 0
t 4
t 6
p 0
t 4
p 0
t 1
t 4
t 6
t 7
p 0
t 1
t 6
p 0
t 3
p 0
t 0
t 5
p 4
t 0
t 7
p 0
t 1
p 1
t 3
t 5
t 6
t 7
p 0
t 1
t 5
t 6
p 0
t 4
t 7
p 0
t 1
t 2
p 3
t 5
t 6
t 7
p 2
t 1
t 2
t 6
p 0
t 0
p 7
t 0
t 7
p 5
t 3
t 4
t 6
t 7
p 0
t 6
t 7
p 0
t 1
t 3
t 6
t 7
p 0
t 1
t 4
t 5
t 6
t 7
p 0
t 4
p 4
t 6
p 0
t 1
t 6
p 4
t 5
t 6
t 7
p 0
t 1
t 3
t 5
p 0
t 1
p 1
t 1
t 3
t 7
p 0
t 1
t 5
t 7
p 0
t 1
t 4
t 5
p 0
t 1
p 3
t 3
t 7
p 1
t 1
t 5
p 0
t 1
t 3
t 4
t 7
p 0
t 1
t 5
p 0
t 4
t 6
t 7
p 0
t 4
p 0
t 1
t 4
t 7
p 0

```

The test cases were generated with this CJam reference implementation.

# Answer
> 3 votes
# CJam, 67 bytes

```
U]8*l{i2b8Ue[8,{1$m>2$.^:+}$0=_@m>@1$.^ee{~{"t "op}{;}?}/"p "o\p}/;

```

Try it online

Explanation:

```
U]8*    Build start bit array [0 0 0 0 0 0 0 0].
l       Get input.
{       Start loop over input characters.
  i       Convert character to integer.
  2b      Convert to binary array.
  8Ue[    Pad to 8 entries with leading 0.
  8,      Generate list of possible rotation amounts.
  {       Start of sort function block.
    1$      Get bit array of character.
    m>      Rotate by rotation amount.
    2$      Get previous bit array.
    .^      Element-wise xor to get different bits.
    :+      Add elements in result to get count of different bits.
  }$      Sort possible rotations by count of different bits.
  0=      Get first rotation amount in sorted list, which is the one with the
          one that results in the smallest count of different bits.
  _       Copy count. Will use original for "p" output later.
  @       Get the character bit array to top of stack.
  m>      Rotate it, to get optimal rotated bit array.
  @       Get previous bit array to top of stack.
  1$      Copy rotated bit array, will need the original as starting point
          for next character.
  .^      Element-wise xor to get different bits.
  ee      Enumerate array to get pairs of index and bit value.
  {       Loop over bits.
    ~       Unpack index bit pair.
    {       Start of if block for bit value.
      "t "o   Output "t ".
      p  Output index and newline.
    }       End of if block.
    {       Start of else block.
      ;       Pop the index value.
    }?      End of ternary if.
  }/      End loop over bits.
  "p "o   Output "p ".
  \       Swap rotation amount to top.
  p       Print rotation amount and newline.
}/      End loop over input characters.
;       Ppp current bit array off stack to prevent extra output.

```

# Answer
> 5 votes
# Ruby, 171

```
->w{s=[0]*8
w.chars.flat_map{|c|z=0..7
*m,i=z.map{|j|z.select{|k|s[k]!=z.map{|i|c.ord[i]}.rotate(j)[k]}<<j}.min_by &:size
m.map{|m|s[m]=1-s[m];"t #{7-m}"}+["p #{i}"]}*?\n}

```

A Ruby function that's *only* double the size of the reference implementation. :)

Try it online: http://ideone.com/ysYyFP

The program is pretty straighforward: it starts off with the 8 bits set to 0 and iterates through the characters. At each step, it takes the shortest route from the current state to a state that would allow printing the character. It returns a string in the specified format.

The initial (less golfed) version of the program is available here.

# Answer
> 4 votes
# CJam, ~~81~~ 76 bytes

Still a lot to golf.

```
0]8*q{i2b8Te[8,\fm>:X\_@\f.=::+_$W=#:YX=_@.{=M['tSUN]?U):U;}o0:U;['pSYN]o}/;

```

Try it online.

---
Tags: code-golf, string, path-finding, binary
---


title: Puzzle: Factor these 256-bit semiprimes

text:
# Question
Title: Puzzle: Factor these 256-bit semiprimes
## Challenge

Write a program to factor this set of 10 numbers:

```
15683499351193564659087946928346254200387478295674004601169717908835380854917
24336606644769176324903078146386725856136578588745270315310278603961263491677
39755798612593330363515033768510977798534810965257249856505320177501370210341
45956007409701555500308213076326847244392474672803754232123628738514180025797
56750561765380426511927268981399041209973784855914649851851872005717216649851
64305356095578257847945249846113079683233332281480076038577811506478735772917
72232745851737657087578202276146803955517234009862217795158516719268257918161
80396068174823246821470041884501608488208032185938027007215075377038829809859
93898867938957957723894669598282066663807700699724611406694487559911505370789
99944277286356423266080003813695961952369626021807452112627990138859887645249

```

Each of these:

* Is a 77-digit number less than 2^256.
* Is a semiprime (e.g., the product of exactly 2 primes).
* Has something in common with at least one other number in the set.

Thus, this challenge is not about general factoring of 256-bit semiprimes, but about factoring *these* semiprimes. It is a puzzle. There is a trick. The trick is fun.

It is possible to factor each of these numbers with surprising efficiency. Therefore, the algorithm you choose will make a much bigger difference than the hardware you use.

## Rules

1. This is , so the shortest answer wins.
2. You may use any method of factoring. (But don't precompute the answers and just print them. You program should do actual work.)
3. You may use any programming language (or combination of languages), and any libraries they provide or you have installed. However, you probably won't need anything fancy.

# Answer
> 4 votes
# Pyth, 12 bytes

```
V.Q--iRN.Q1N

```

Try it here: Demonstration

### Explanation:

```
               implicit: .Q is the list of the input numbers
V.Q            for N in .Q:
     iRN.Q        compute the gcd of N with each number in .Q
    -     1       remove 1s
   -       N      remove the number N and print

```

# Answer
> 3 votes
# Julia

```
f=l->(A=map(big,[gcd(l[i],l[j]) for i=1:length(l),j=1:length(l)]);A-=eye(A).*(l-1);for i=1:length(l) println(l[i]," = ",join(unique(A[i,:])," × "))end);

```

Running it:

```
julia> tic();f(l);toc()
15683499351193564659087946928346254200387478295674004601169717908835380854917 = 1 × 123830525223423718982054269884856893727 × 126652934104061135988638942588043498971
24336606644769176324903078146386725856136578588745270315310278603961263491677 = 123830525223423718982054269884856893727 × 1 × 196531562802139162910711939551924590851
39755798612593330363515033768510977798534810965257249856505320177501370210341 = 126652934104061135988638942588043498971 × 1 × 313895598975456800331958744266933545471
45956007409701555500308213076326847244392474672803754232123628738514180025797 = 1 × 196531562802139162910711939551924590851 × 233835251470362519313085185758275325847
56750561765380426511927268981399041209973784855914649851851872005717216649851 = 1 × 218051709768607497734800854124975705007 × 260261943488556401874345256435550440693
64305356095578257847945249846113079683233332281480076038577811506478735772917 = 1 × 218051709768607497734800854124975705007 × 294908745103709254641398276907437631131
72232745851737657087578202276146803955517234009862217795158516719268257918161 = 1 × 233835251470362519313085185758275325847 × 308904433345854212511531098349325333463
80396068174823246821470041884501608488208032185938027007215075377038829809859 = 1 × 260261943488556401874345256435550440693 × 308904433345854212511531098349325333463
93898867938957957723894669598282066663807700699724611406694487559911505370789 = 1 × 294908745103709254641398276907437631131 × 318399740590727338211743341325021840319
99944277286356423266080003813695961952369626021807452112627990138859887645249 = 1 × 313895598975456800331958744266933545471 × 318399740590727338211743341325021840319
elapsed time: 0.002534739 seconds

```

Note: Because of how Julia operates, you might want to run it twice - the first time you run it, the tic/toc will include the time required to "compile" it. The second time, it will have already compiled it.

# Answer
> 3 votes
# CJam, 32 bytes

```
q~]__ff{{_@\%}h}:|1-_m*_::*\er:p

```

Try it online: permalink for Chrome | permalink for Firefox

# Answer
> 2 votes
## CJam, 38 bytes

```
q~]_2m*{~{_@\%}h;}%_2$-&2m*f{_::*@#=p}

```

Try it here.

This answer is shorter than any of the factors in the output.

# Answer
> 2 votes
## J, 2 bytes

This is now, so I assume efficiency doesn't actually matter, which means:

```
q:

```

(J's "factor prime" function) will return the right answer (in the form of a neatly formatted `2x10` array!) if you pass it an array of bignums give it a couple of hours/days to factor the semiprimes.

# Answer
> 1 votes
# Pyth, 15 13 12 bytes

```
jbmS{iLd.Q.Q

```

Expects the list of primes seperated by newlines on stdin. Outputs in the following format:

```
[1, 123830525223423718982054269884856893727, 126652934104061135988638942588043498971, 15683499351193564659087946928346254200387478295674004601169717908835380854917]
[1, 123830525223423718982054269884856893727, 196531562802139162910711939551924590851, 24336606644769176324903078146386725856136578588745270315310278603961263491677]
[1, 126652934104061135988638942588043498971, 313895598975456800331958744266933545471, 39755798612593330363515033768510977798534810965257249856505320177501370210341]
[1, 196531562802139162910711939551924590851, 233835251470362519313085185758275325847, 45956007409701555500308213076326847244392474672803754232123628738514180025797]
[1, 218051709768607497734800854124975705007, 260261943488556401874345256435550440693, 56750561765380426511927268981399041209973784855914649851851872005717216649851]
[1, 218051709768607497734800854124975705007, 294908745103709254641398276907437631131, 64305356095578257847945249846113079683233332281480076038577811506478735772917]
[1, 233835251470362519313085185758275325847, 308904433345854212511531098349325333463, 72232745851737657087578202276146803955517234009862217795158516719268257918161]
[1, 260261943488556401874345256435550440693, 308904433345854212511531098349325333463, 80396068174823246821470041884501608488208032185938027007215075377038829809859]
[1, 294908745103709254641398276907437631131, 318399740590727338211743341325021840319, 93898867938957957723894669598282066663807700699724611406694487559911505370789]
[1, 313895598975456800331958744266933545471, 318399740590727338211743341325021840319, 99944277286356423266080003813695961952369626021807452112627990138859887645249]

```

# Answer
> 1 votes
# Pyth, 4 bytes

Since we don't have to abuse the common divisors we can simply use the factorization function and map it to the input:

```
PM.Q

```

Yay loopholes!

---
Tags: code-golf, primes, number-theory, puzzle-solver
---


title: Zig-zag strings

text:
# Question
Title: Zig-zag strings
# Zig-zag strings

Given a string and a positive integer, output the string in a zig-zag wave pattern with a peak amplitude and character spacing equal to the integer.

This is similar to this question but also includes character spacing.

## Input

Input can be read from STDIN or taken as function arguments. Input is a string without newlines and a positive integer.

## Output

Expected output is the string transformed into a zig-zag wave pattern -- starting upwards -- with the first character on the base line. The wave patter must have an amplitude and **character spacing** equal to the integer.

## Examples

*Input*

```
Programming Puzzles & Code Golf
2

```

*Output*

```
    o               g                s
  r   g           n                e               e   G
P       r       i       P        l       &       d       o
          a   m           u    z               o           l
            m                z               C               f

```

*Input*

```
Programming Puzzles & Code Golf
1

```

*Output*

```
 r   a   n   u   e       e   l
P o r m i g P z l s & C d   o f
   g   m       z       o   G

```

This is code golf -- shortest program wins.

# Answer
> 4 votes
# Javascript (ES6), ~~133~~ ~~132~~ ~~136~~ 134 bytes

```
(s,n,o=Array(2*n+1).fill``)=>[...s].map((v,i)=>o=o.map((w,a)=>w+(a-((j=(i+3*n)%(4*n))>2*n?4*n-j:j)?" ":v)+" ".repeat(n-1)))&&o.join`
`

```

Defines an anonymous function. To call it, add `f=` to the beginning to call the function `f`. Then, it can be tested with `console.log(f("Programming Puzzles & Code Golf", 2))`

Thanks to @vihan and @edc65 for helping save some bytes! :)

@kvill: The code has been modified to address the variable character spacing requirement in the spec. Didn't notice that at first!

# Answer
> 0 votes
# Python 2, 151

Here is my answer using Python 2:

```
s,n=input()
a=2*n+1
l,j,o=['',]*a,n,1
for c in s:
 for k in range(a):l[k]+=c+(n-1)*' ' if j==k else' '*n
 j-=o
 if j in [0,2*n]:o=-o
print'\n'.join(l)

```

Sample output:

```
         t                                   e                                   h                                   t                                   e
      s     i                             v     ,                             t     e                             s     i                             v
   e           n                       a                                                                       e           n                       a
t                 g                 w                 t                 g                 w                 t                 g                 w
                                                         e           n                       a
                        t     e                             s     i                             v     ,                             t     e
                           h                                   t                                   e                                   h

```

and

```
 r   a   n   u   e       e   l
P o r m i g P z l s & C d   o f
   g   m       z       o   G

```

# Answer
> 0 votes
# J, 75 bytes

```
f=:4 :0
|:((]*>:@i.@#)((+:<:b)|i.#y){x|.}:(],}.@|.)|.=/~i.b=.>:+:x){' ',y
)

```

Here is function in use

```
   7 f'code golf is awesome and I like it'

       l
      o f
     g                           t
          i                     i
   e       s
  d                           e
 o           a               k
c             w             i
               e           l
                s
                 o       I
                  m
                   e   d
                      n
                     a

```

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


title: ASCII Game of Pong

text:
# Question
Title: ASCII Game of Pong
# Ascii Pong

The challenge is to recreate the classic game "pong" in ASCII characters in the shortest code possible.

**Requirements/specifications**

* The "screen" should be 45x25 characters.
* White space should actually be white space.
* The paddles should be 9 equals signs: `=========` and should be on the top-most and bottom-most rows (I know the original is played side-to-side instead of top-to-bottom, but I think this works better for ascii pong).
* The ball can be a lower or upper case `o` or a zero.
* Two input buttons of any kind (it is fine if the user presses a key that makes a letter show up in the input, that is fine, too) to move the player's paddle left and right one or two character at a time.
* The ball needs to ricochet at the appropriate angle upon hitting a paddle or a wall (hint: negate the x or y difference value).
* The score should be displayed somewhere in the output. The score is how many times the player successfully hits the ball.
* If the ball misses the player's paddle, terminate the program.
* There should be *some* sort of AI (even if the AI's paddle just matches the ball's x value).
* The ball can't travel in a straight line vertically or horizontally.

The start screen/first frame should look something like this:

```
                  =========

                      o

                  =========
score: 0

```

**Scoring** This is , so the shortest code wins ... however, there are some bonuses to decrease your character count:

* -30 characters: Change trajectory of ball depending on where it hits on the paddle
* -10 characters: Make the game speed up over time
* -20 characters: Make the AI beatable
* -20 characters: Avoid any situation where the player stays still and the game goes on forever without winning or losing (caused by certain trajectories and AI patterns)
* -20 characters: Make the ball start moving at a (semi-)random trajectory
* -25 characters: Add a reset option

Here is an un-golfed example with no bonuses in JavaScript:

```
//init
var x = 22,
    y = 12,
    xd = Math.random() < 0.5 ? -1 : 1,
    yd = 1,
    player = opponent = 18,
    score = 0,

//interval that runs 10x per second (minus the runtimeof one cycle)
interval = setInterval(function() {
  //move ball
  x += xd;
  y += yd;

  //move opponent
  opponent = x - 4;

  //collision with walls
  if(x <= 0 || x >= 44) xd = -xd;

  //collision with paddles
  if(y == 1) {
    if(x >= opponent && x < opponent + 9) yd = -yd;
    else {
      //you win
      clearInterval(interval);
      document.body.innerHTML = "You win!<br>Your score was: " + score;
      return;
    }
  }
  else if(y == 23) {
    if(x >= player && x < player + 9) {
      yd = -yd;
      score++;
    }
    else {
      //you lose
      clearInterval(interval);
      document.body.innerHTML = "You lose!<br>Your score was: " + score;
      return;
    }
  }

  draw();
}, 100);

function draw() {
  var body = document.body;
  body.innerHTML = "";
  for(var i = 0; i < 25; i++) {
    for(var j = 0; j < 45; j++) {
      //white space is default
      var char = " ";

      //ball
      if(j == x && i == y) char = "o";

      //paddles
      if(i === 0) {
        if(j >= opponent && j < opponent + 9) char = "=";
      }
      else if(i == 24) {
        if(j >= player && j < player + 9) char = "=";
      }

      body.innerHTML += char;
    }
    body.innerHTML += "<br>";
  }
  body.innerHTML += "score: " + score;
}

//key press listener for left and right movement
window.onkeydown = function() {
  if (window.event.keyCode == 37) player -= 2;
  else if(window.event.keyCode == 39) player += 2;
};
```

```
<body style="font-family: monospace; white-space: pre">

</body>
```

Let the games begin!

# Answer
> 4 votes
# Perl, ~~760 611 592 535~~ 515 (640-30-10-20-20-20-25)

A console solution with all the bonus stuff.
It should work on any terminal that understands the ANSI escape codes (\e\[...). Tested on cygwin.

Keyboard controls:
Left: 4
Right : 6
Reset : 8

```
use Term::ReadKey;ReadMode 4;END{ReadMode 0}$|++;$a=$d=45;$b=25;$h=1;$j=$l=17;$p='='x9;sub P{print"\e[@_"}sub L{$%=$l+pop;if($%>0&$%+7<$a){P"25H\e[K\e[25;$%H$p ";$l=$%}}sub U{$%=$j+pop;if($%>0&$%+7<$a){P"1H\e[K\e[1;$%H$p ";$j=$%}}sub I{$}=int rand 42;$g=8;$i=1;P"2J\ec";L}I;while(1){if($c>0){$c--}else{$c=98;$d-=$d>6}if($c%9==0){U -1if$}<$j+4;U 1if$}>$j+6};if($c%$d==0){$m=$}+$h;$n=$g+$i;$h*=-1if$m<1||$m>$a;if($n>24&$}>=$l&$}<$l+9){$i*=-1;$h=-1if$m<$l+5;$h=1if$m>$l+5;$s++}if($n<2&$}>=$j&$}<$j+9){$i*=-1}P"$g;1H\e[K";$}+=$h;$g+=$i;P"$g;$}HO"}if($k=ReadKey -1){I,if$k>6;L$k<=>5}P"26;0Hscore:$s";exit,if$g>=$b;select($\,$\,$\,0.01);I,if$g<2}

```

# Answer
> 1 votes
# JavaScript, 618 bytes + HTML, 99 bytes

Well here is my golfed JavaScript answer even if it isn't feasible in other languages:

```
var x,y,xd,yd,p,o,s,n,i,j,c,k;function a(){x=22;y=12;xd=Math.random()<.5?-1:1;yd=1;p=o=18;s=0;n=setInterval(function(){x+=xd;y+=yd;o=x-4;if(x<=0||x>=44)xd=-xd;if(y==1){if(x>=o&&x<o+9)yd=-yd;else{clearInterval(n);b.innerHTML="You Win!<br>Score: "+s;return}}else if(y==23){if(x>=p&&x<p+9){yd=-yd;s++;}else{clearInterval(n);b.innerHTML="You Lose!<br>Score: "+s;return}}d();},100);}function d(){b.innerHTML="";for(i=0;i<25;i++){for(j=0;j<45;j++){c=" ";if(j==x&&i==y)c="o"; if(i==0&&j>=o&&j<o+9)c="=";if(i==24&&j>=p&&j<p+9)c="=";b.innerHTML+=c;} b.innerHTML+="<br>";}b.innerHTML+="score: "+s;}onkeydown=function(){ k=window.event.keyCode;if(k==37)p-=2;if(k==39)p+=2;};
```

```
<button onclick="a()">start</button><div id="b"style="font-family:monospace;white-space:pre"></div>
```

-20 and -25 for bonuses

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


title: ASCII Art Chessboard

text:
# Question
Title: ASCII Art Chessboard
In this challenge, you are to draw the chessboard below, and allow for moves to be made.

**1. Drawing**

Each white square has 5x9 spaces.

Each black square has 5x9 colons.

The board is surrounded by a border of colons.

The pieces are 5 characters wide and sit on the bottom row of the square in the centre.

The pawns are 4 characters wide. They sit slightly off centre to the right, with 3 blank squares on the left and 2 blank squares on the right. They sit one line above the bottom of the square.

There shall be no whitespace outside the area of the board, with the exception of an optional trailing newline.

The board and the chessmen shall be drawn exactly as shown, except that:

1. You may subsitute the `:` in the black squares and border for a different symbol, and you may substitute the `@` in the black pieces for a different symbol (but not the same one used for the black squares.)
2. You may move the pawns one character to the left if you wish.

.

```
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:         :::::::::         :::www:::   _+_   :::::::::         ::::::::::
:  |_|_|  :: _,,:::   (/)   :::)@(:::   )@(   :::(/):::   _,,   ::|_|_|:::
:   |@|   ::"- \~::   |@|   :::|@|:::   |@|   :::|@|:::  "- \~  :::|@|::::
:   |@|   :::|@|:::   |@|   :::|@|:::   |@|   :::|@|:::   |@|   :::|@|::::
:  /@@@\  ::/@@@\::  /@@@\  ::/@@@\::  /@@@\  ::/@@@\::  /@@@\  ::/@@@\:::
::::::::::         :::::::::         :::::::::         :::::::::         :
:::::():::    ()   ::::():::    ()   ::::():::    ()   ::::():::    ()   :
:::::)(:::    )(   ::::)(:::    )(   ::::)(:::    )(   ::::)(:::    )(   :
::::/@@\::   /@@\  :::/@@\::   /@@\  :::/@@\::   /@@\  :::/@@\::   /@@\  :
::::::::::         :::::::::         :::::::::         :::::::::         :
:         :::::::::         :::::::::         :::::::::         ::::::::::
:         :::::::::         :::::::::         :::::::::         ::::::::::
:         :::::::::         :::::::::         :::::::::         ::::::::::
:         :::::::::         :::::::::         :::::::::         ::::::::::
:         :::::::::         :::::::::         :::::::::         ::::::::::
::::::::::         :::::::::         :::::::::         :::::::::         :
::::::::::         :::::::::         :::::::::         :::::::::         :
::::::::::         :::::::::         :::::::::         :::::::::         :
::::::::::         :::::::::         :::::::::         :::::::::         :
::::::::::         :::::::::         :::::::::         :::::::::         :
:         :::::::::         :::::::::         :::::::::         ::::::::::
:         :::::::::         :::::::::         :::::::::         ::::::::::
:         :::::::::         :::::::::         :::::::::         ::::::::::
:         :::::::::         :::::::::         :::::::::         ::::::::::
:         :::::::::         :::::::::         :::::::::         ::::::::::
::::::::::         :::::::::         :::::::::         :::::::::         :
::::::::::         :::::::::         :::::::::         :::::::::         :
::::::::::         :::::::::         :::::::::         :::::::::         :
::::::::::         :::::::::         :::::::::         :::::::::         :
::::::::::         :::::::::         :::::::::         :::::::::         :
:         :::::::::         :::::::::         :::::::::         ::::::::::
:    ()   ::::():::    ()   ::::():::    ()   ::::():::    ()   ::::()::::
:    )(   ::::)(:::    )(   ::::)(:::    )(   ::::)(:::    )(   ::::)(::::
:   /__\  :::/__\::   /__\  :::/__\::   /__\  :::/__\::   /__\  :::/__\:::
:         :::::::::         :::::::::         :::::::::         ::::::::::
::::::::::         :::::::::   www   :::_+_:::         :::::::::         :
:::|_|_|::   _,,   :::(/):::   ) (   :::) (:::   (/)   :::_,,:::  |_|_|  :
::::| |:::  "- \~  :::| |:::   | |   :::| |:::   | |   ::"- \~::   | |   :
::::| |:::   | |   :::| |:::   | |   :::| |:::   | |   :::| |:::   | |   :
:::/___\::  /___\  ::/___\::  /___\  ::/___\::  /___\  ::/___\::  /___\  :
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

```

**2. Moving**

The columns are labelled A-H from left to right and 1 to 8 from bottom to top. The user shall be able to enter a move in the following form:

```
<start column><start row><space><destination column><destination row>

```

For example `B1 C3` means move the knight to the square in front of the bishop's pawn (assuming the game has just started).

Alternatively the ICCF system can be used, in which the columns are labelled 1 to 8 instead of A to H. So the knight move mentioned above becomes `21 33`.

The following image (source) clarifies both systems:

The move shall be executed and the new board displayed. Any resulting capture shall occur with the moving chessman removing the chessman on the destination square from the board.

There is no need to check for a legal chess move, as that has been covered in other challenges: Smallest chess program and The smallest Chess arbiter If the user tries to move from an empty square, your program or function should ignore the move. If the user tries to capture a friendly piece, you can either ignore the move or allow the stationary piece to be captured.

There is no need to support en passant or castling.

You may assume the input will be well formed, i.e. always in the format described above. Letters will always be in the same case, you can decide what case that is.

**3. Scoring and Bonuses**

This is code golf. Shortest code wins.

-10% bonus if your program or function allows for promotion. The user enters a third input, this time one of the following letters: Q B R N. This should only be allowed if the move ends with a pawn on the last row. The pawn is exchanged for the named piece. QBRN.

-10% bonus if your program or function implements a special "undo" move for reversal of moves (as far back as the beginning of the game if required.) Obviously it is possible for amateur players to make illegal moves, and they may wish to undo them. You may define the input the user must give for this "undo" move (it must always be the same.) Behaviour is undefined if the user tries to undo beyond the beginning of the game.

Bonuses sum, i.e. if you go for both bonuses you get -20%.

# Answer
# Octave, 776 688 bytes

**688:**

* functions inlined into main loop (both were used only once),
* used cell notation `{'foo','bar'}{i}` in place of slightly longer `['foo';'bar'](i,:)`

Still none of bonuses implemented.

---

Uses ICCF system.

There may be no leading spaces in the move description and the source and destination field must be separated by a single whitespace, so `42 44` is correct, while  `42 44` and `42 44` are not.

```
R=@repmat;s=[t='BFJbRJFB';R(('@    A')',1,8);t+1]';while 1q=' ';c=R(':',42,74);m=R([m=R(q,5,9) l=m+26;l m],4,4);c(2:41,2:73)=m;for i=1:8 for j=1:8 f=s(i,j);z=@(c)bitand(+f,c);if z(64)b=z(1)+1;W={') (',')@('}{b};U=43-5*j;Z=9*i-2;T=Z-2:Z;Q=Z-3:Z+1;if z(2)c(U+3,Q)={'/___\','/@@@\'}{b};a=c(U+2,T)={'| |','|@|'}{b};if z(4)c(U+1,Q)='"- \~';c(U,Z-3:Z)=' _,,';else c(U+1,T)=a;if z(8)c(U,T)='(/)';elseif z(16)||z(32)c(U,T)=W;c(U-1,T)={'_+_','www'}{1+z(32)/32};else c(U,Q)='|_|_|';end
end
else c(U+2,Z-2:Z+1)={'/__\','/@@\'}{b};c(U:U+1,Z-1:Z)=['()';')('];end;end;end;end;c
m=input(q,'s')-'0';x=m(1);y=m(2);X=m(4);Y=m(5);if s(x,y)~=q&&(s(X,Y)==q||mod(s(x,y)-s(X,Y),2))s(X,Y)=s(x,y);s(x,y)=q;end
end

```

Somewhat ungolfed version:

```
# draw an empty chessboard
function n=cb
R=@repmat;
n=R(':',42,74);
m=R([m=R(' ',5,9) m+26;m+26 m],4,4);
n(2:41,2:73)=m;
end

# function n=put(n,f,c,r) :
#
# put a chessman f on column c and row r of chessboard n,
# returning new chessboard
# chessman is described by single character defined following way
# (please excuse naming bits by value rather than position):
# bit valued  127 -     unused
# bit valued  64  -     0 = field empty, 64 = field occupied.
# bits valued 32,16,8 - 0 = rook, 8 = bishop, 16 = king, 32 = queen
# bit valued  4 -       0 = not knight 4 = knight (only checked if "other piece" bit is set)
# bit valued  2 -       0 = pawn       2 = other piece
# bit valued  1 -       0 = white      1 = black

# this gives the following chars:

# pawns   - 64      (+1)  => @ , A
# knights - 64+4+2  (+1)  => F , G
# rooks   - 64+2    (+1)  => B , C
# bishops - 64+8+2  (+1)  => J , K
# kings   - 64+16+2 (+1)  => R , S
# queens  - 64+32+2 (+1) =>  b , a
# empty space - any character with bit valued 64 unset (space char does)

function n=put(n,f,c,r)
z=@(n)bitand(f-0,n);
if z(64)
    b=z(1);
    W=') ()@('(1+3*b:3+3*b);
    R=5*r;C=9*c;
    if z(2)
            n(46-R,C-5:C-1)='/___\/@@@\'(1+5*b:5+5*b);
            a=n(45-R,C-4:C-2)='| ||@|'(1+3*b:3+3*b);
            if z(4) # knight
                    n(44-R,C-5:C-1)='"- \~';
                    n(43-R,C-5:C-2)=' _,,';
            else
                    n(44-R,C-4:C-2)=a;
                    if z(8) # bishop
                            n(43-R,C-4:C-2)='(/)';
                    elseif z(16) # king
                            n(43-R,C-4:C-2)=W;
                            n(42-R,C-4:C-2)='_+_';
                    elseif z(32) # queen
                            n(43-R,C-4:C-2)=W;
                            n(42-R,C-4:C-2)='www';
                    else  # rook
                            n(43-R,C-5:C-1)='|_|_|';
                    end
            end
    else
            n(45-R,C-4:C-1)='/  \/@@\'(1+4*b:4+4*b);
            n(43-R:44-R,C-3:C-2)=['()';')('];
    end
end
end

# here we can easily define the chessboard.
s=['BFJbRJFB';repmat(('@    A')',1,8);'CGKcSKGC']';
c=cb;for i=1:8 for j=1:8 c=put(c,s(i,j),i,j);end;end
c

# We scan five characters. They must be positions in ICCF without leading spaces separated by single space.
while m=input('','s')-'0'
x=m(1)
y=m(2)
X=m(4)
Y=m(5)
# if the move is not allowed (capture piece of the same color or the start field is blank,
# do nothing
if s(x,y)==' ' || (s(X,Y) ~=' ' && mod(s(x,y)-s(X,Y),2)==0) continue; end;
# make the move
s(X,Y)=s(x,y);
s(x,y)=' ';
# redraw the board
c=cb;for i=1:8 for j=1:8 c=put(c,s(i,j),i,j);
end end
c
end

```
> 4 votes

# Answer
# Ruby, ~~715~~ ~~696~~ ~~693~~ 683 bytes

This is a fairly messy solution but I don't have the patience to clean it up further at the moment.

Neither of the bonuses done.

Uses ICCF system.

```
a,b,c=->f,x,y,p{p.map{|ln|ln.gsub(/\d/){|z|f*(z.to_i)}.tr('AB',x+y)}},Array.new(64){|i|((i%56<8?[4,2,3,5,6,3,2,4][i%56]:(i-8)%40<8?1:0)<<2)+(i<16?2:0)},':'*74
loop{puts c
b.each_slice(8).with_index{|r,y|d,*e=r.map.with_index{|v,x|a[*([[' '],[':']][(x+y)%2]+[[' ','_'],['@','@']][v&2==2?1:0]+[('9@9@9@9@9;9@4()3@4)(3@3/BB\2@9;9@3_,,3@2"- \~2@3|A|3@2/BBB\2;9@3(/)3@3|A|3@3|A|3@2/BBB\2;9@2|_|_|2@3|A|3@3|A|3@2/BBB\2;3www3@3)A(3@3|A|3@3|A|3@2/BBB\2;3_+_3@3)A(3@3|A|3@3|A|3@2/BBB\2'.split(';').map{|s|s.split '@'})[v>>2]])]}
d.zip(*e).each{|r|puts ":#{r.join}:"}}
puts c
gets.scan(/(.)(.) (.)(.)/){|f,g,h,i|j,k=63+(f.to_i)-(g.to_i)*8,63+(h.to_i)-(i.to_i)*8
b[k],b[j]=b[j]>0?b[j]: b[k],0}}

```
> 5 votes

# Answer
## Python, 1136 890 753 bytes

Apologies for the partial answer but I'm a newbie and I really enjoyed this challenge. I know it's probably really verbose but here's my rough draft:

```
y=':'*9
z=' '*9
b='::/___\::'
c=':::|@|:::'
d=':::)@(:::'

ps = {'r': [y,'::|*|*|::', c, c,b],'n': [y,':::,,::::', '::"- \~::', c,b],'b': [y,':::(/):::',c,c,b],'k': [':::www:::',d,c,c,b],'q': [':::*+*:::',d,c,c,b],'p': [y, '::::():::','::::)(:::',':::/__\::',y]}

def cell(p,c):
  if p == '!':
    return ([z]*5,[y]*5)[c]
  s = []
  for l in ps[p.lower()]:
    l = (l.replace('@', ' '), l.replace('_', '@'))[p.islower()]
    l = (l.replace(':', ' '), l)[c].replace('*', '_')
    s.append(l)
  return s

b = {8:'rnbkqbnr',7:'p'*8,2:'P'*8}
b[1] = b[8].upper()
for i in range(3,7):
  b[i] = '!'*8

o=[y*8]
c=0
for r in b:
  l=['']*5
  for p in b[r]:
    cc=cell(p,c)
    for i in range(0,5):
      l[i]+=cc[i]
    c=not c
  o.extend(l)
  c=not c
o.append(o[0])
for l in o:
  print ':'+l+':'

```
> 3 votes

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


title: Computationally Calculate Core Count

text:
# Question
Title: Computationally Calculate Core Count
Almost all operating systems allow you to run multiple programs at the same time. If your system does not have enough processors to run all the programs you want to run, it starts to give each program just a tiny slice of time on the processor it runs on. This is normally not noticeable but can lead to strange artefacts that you might not expect.

Your task is to write a program that tries to find out how many cores your computer has without asking the operating system. This is a popularity contest, the most upvoted solution wins. Here are the constraints:

* While you cannot expect that your submission is the only thing that runs, you may expect that all other programs on the system are idling and wake up only sporadically.
* You may not ask the operating system how many cores your computer has. Neither may you look up this number from any configuration file or similar. You may also not invoke a utility that provides you with that information.
* For the sake of this challenge, the number of cores your computer has is the number of processes your computer can run at the same time. For instance, if you have an Intel processor with 2 cores and hyper threading, that would count as 4 cores.
* Your solution needs not to be precise. It should not be terribly wrong all the time though.

# Answer
# C++11

Simply compares single core performance with threaded performance until there is not a linear speedup anymore. It's important that you do not have any other CPU intensive process running at the same time.

Compile with `-O2 -m64 -march=native -std=c++11`. You might have to pass `-lpthread`.

```
#include <chrono>
#include <cstdint>
#include <future>
#include <iostream>
#include <vector>

double f() {
    double cnt = 0;
    std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
    start = std::chrono::system_clock::now();

    while (true) {
        end = std::chrono::system_clock::now();
        std::chrono::duration<double> elapsed = end - start;
        if (elapsed.count() > 1.) break;
        cnt++;
    }

    return cnt;
}

int main(int argc, char** argv) {
    double one_core = f();

    int n = 1;
    while (true) {
        std::vector<std::future<double>> futures;
        for (int i = 0; i < n; ++i) {
            futures.push_back(std::async(std::launch::async, f));
        }

        double tot = 0;
        for (int i = 0; i < n; ++i) tot += futures[i].get();
        if (int(tot / one_core + 0.5) != n) {
            std::cout << n - 1 << " core(s)\n";
            return 0;
        }

        ++n;
    }
}

```
> 10 votes

# Answer
# C

Here's a new, imprecise approach:

```
/* ncpu.c */

#include <stdio.h>
#include <pthread.h>
#include <signal.h>

pthread_mutex_t count_mutex = PTHREAD_MUTEX_INITIALIZER;
int count = 1;  /* start at 1 for the main() thread */

static void *inc_thread (void *arg) {
    /* Woohoo - now we're no longer languishing on the ready queue -
     * We're actually running on a real core.  Atomically bump the counter. */
    pthread_mutex_lock(&count_mutex); {
        count++;
    } pthread_mutex_unlock(&count_mutex);

    /* keep this core spinning so another thread doesn't get it */
    while (1);
    return NULL;
}

#define MAX_CORE 64
int main (int argc, char **argv) {
    pthread_t tid_array[MAX_CORE];
    int i;

    /* create a bunch of threads */
    for (i = 0; i < MAX_CORE; i++) {
        pthread_create(&tid_array[i], NULL, inc_thread, NULL);
    }
    /* cancel all those threads, regardless of whether they ran or not */
    for (i = 0; i < MAX_CORE; i++) {
        pthread_cancel(tid_array[i]);
    }

    printf("Your core count is approximately %d\n", count);
}

```

Build with `LDFLAGS=-pthread make ncpu`.

This works some of the time on Ubuntu 14.04. I have tested with 1, 2 and 4 virtual cores in a VM.

This kicks off 64 threads, and then (almost) immediately cancels all those threads. `pthread_create()` will put the new thread in a ready queue, but won't necessarily jump into the thread start routine immediately. When the threads get to run depends on core availability at that time.

For example if there are 4 cores, then 3 of the threads can potentially start running immediately. Each thread atomically increments a counter then spins for a bit until it is cancelled. Beyond the third thread, the rest of the threads will still be sitting in the ready queue when the main thread cancels them, and so they won't get to increment the counter.

This is certainly not very precise, but its only *terribly* wrong some of the time. Here are some runs with 1, 2 and 4 virtual cores:

### 1 core:

```
$ for i in {1..10}; do ./ncpu; done
Your core count is approximately 65
Your core count is approximately 1
Your core count is approximately 1
Your core count is approximately 15
Your core count is approximately 1
Your core count is approximately 19
Your core count is approximately 1
Your core count is approximately 1
Your core count is approximately 42
Your core count is approximately 1
$

```

### 2 cores:

```
$ for i in {1..10}; do ./ncpu; done
Your core count is approximately 2
Your core count is approximately 2
Your core count is approximately 2
Your core count is approximately 2
Your core count is approximately 2
Your core count is approximately 2
Your core count is approximately 3
Your core count is approximately 3
Your core count is approximately 2
Your core count is approximately 2
$

```

### 4 cores:

```
$ for i in {1..10}; do ./ncpu; done
Your core count is approximately 4
Your core count is approximately 5
Your core count is approximately 4
Your core count is approximately 4
Your core count is approximately 4
Your core count is approximately 4
Your core count is approximately 4
Your core count is approximately 4
Your core count is approximately 4
Your core count is approximately 4
$

```

---

My previous answer:

Here's a start, though it only distinguishes between exactly one core and more than one core:

```
/* 1cpu.c */

#include <stdio.h>
#include <pthread.h>

int c = 0;

static void *inc_thread (void *arg) {
    int i;
    for (i = 0; i < 10000000; i++) c++;
    return NULL;
}

static void *dec_thread (void *arg) {
    int i;
    for (i = 0; i < 10000000; i++) c--;
    return NULL;
}

int main (int argc, char **argv) {
    pthread_t inc_tid, dec_tid;

    pthread_create(&inc_tid, NULL, inc_thread, NULL);
    pthread_create(&dec_tid, NULL, dec_thread, NULL);

    pthread_join(inc_tid, NULL);
    pthread_join(dec_tid, NULL);

    if (c) {
        printf("c=%d, More than one CPU\n", c);
    } else {
        printf("c=%d, Only one CPU\n", c);
    }
}

```

Build with `LDFLAGS=-pthread make 1cpu`.

This is a nice demonstration of how normal `++` and `--` are **not** atomic operations. In the single-core situation, `inc_thread()` and `dec_thread()` can never run concurrently, so the global counter `c` will always be incremented and decremented exactly 10 million times and thus end up as 0. However with more than one core, these two threads will likely end up on different cores, and thus colliding with their operations on the global counter. As we know, these operations have to load, \[in|de\]crement, then save each time, so threads can end up operating on stale data as they go through these operations. Therefore over 10 million runs we will likely end up with a different number of effective increment vs decrement operations and the counter will end up non-zero.

This method seems to be fairly accurate, and works on OSX as well as Linux.
> 7 votes

# Answer
# Python 2

```
import decimal
from timeit import Timer

elapsed = decimal.Decimal(Timer("""1 and 1""").timeit())
speed = 1/elapsed
cores = speed/decimal.Decimal(3.6)

cores = round(cores)

print cores

```

I kind of lost what I was doing halfway through but this works fairly well for me.

## Edit

I guess modern computer cores have a greater speed. The program should now be more accurate (hopefully).
> 0 votes

---
Tags: popularity-contest, concurrency
---


# Question
Title: Find the area of the largest convex polygon
Given a list of integer coordinates, find the area of the biggest convex polygon you can construct from the list such that -

* every vertex is in the list
* no element of the list is contained within the polygon.

Example:

> (0, 0) (8, 0) (0, 1) (3, 1) (7, 1) (1, 2) (5, 2) (9, 2) (2, 3) (5, 3) (7, 3) (3, 4) (5, 5) (11, 5)

Visualized:

```
o       o
o  o   o
 o   o   o
  o  o o
   o
     o     o

```

The biggest convex polygon you can make from this is this:

```
o
o  o
 o   o
  o  o
   o
     o

```

With an area of 12.

---

You may take the list of coordinates in any reasonable format, and should output (in an appropriate way for your language of choice) the area of the largest convex polygon, rounded to no less than 2 digits after the decimal point.

Additionally, you must employ some sort of algorithm, and not simply brute force all subsets of the points. To enforce this, your program must solve a list of 50 vertices in under a minute on a modern PC.

**Shortest code in bytes wins.**

# Answer
> 12 votes
# Javascript ES6, 738 bytes

```
((V,C,L,r,k,n,A,G,F,e,i,j,q)=>p=>{p=p.map((p,i)=>({i:i,x:p[0],y:p[1]}));A=(f,p,a,b,v,i)=>{for(i=p[n],v=V(a,b);i--;)if(f(v,V(a,p[i])))return 1};G=(p,i,a)=>{for(i=p[n]-1,a=C(p[i],p[0]);i--;)a+=C(p[i],p[i+1]);if((a/=2)>r)r=a};F=(p,s,l,f,a,b,v)=>(l=s[n],f=s[0],a=s[l-2],b=s[l-1],e[a.i][b.i]||A((a,b)=>C(a,b)?0:a.x<0==b.x<0&&a.y<0==b.y<0&&L(a)>L(b),p,a,b)?0:(p=(v=V(a,b),p[k](x=>C(v,V(a,x))>=0)),A((a,b)=>C(a,b)>0,p,b,f)?0:(p.map(q=>F(p[k](r=>q!==r),[...s,q])),s[2]&&!p[n]&&!e[b.i][f.i]?G(s):0)));e=p.map(x=>p.map(y=>x===y));for(i=p[n];i--;){for(j=i;j--;){q=p[k]((p,x)=>x-i&&x-j);F(q,[p[i],p[j]]);F(q,[p[j],p[i]]);e[i][j]=e[j][i]=1}}console.log(r)})((a,b)=>({x:b.x-a.x,y:b.y-a.y}),(a,b)=>a.x*b.y-a.y*b.x,v=>v.x*v.x+v.y*v.y,0,'filter','length')

```

Here's an ES5 or less version that should work in most browsers and node without tweaking: **827 bytes**

```
eval("(%V,C,L,r,k,n,A,G,F,e,i,j,q){@%p){p=p.map(%p,i){@{i:i,x:p[0],y:p[1]}});A=%f,p,a,b,v,i){for(i=p[n],v=V(a,b);i--;)if(f(v,V(a,p[i])))@1};G=%p,i,a){for(i=p[n]-1,a=C(p[i],p[0]);i--;)a+=C(p[i],p[i+1]);if((a/=2)>r)r=a};F=%p,s,l,f,a,b,v){@(l=s[n],f=s[0],a=s[l-2],b=s[l-1],e[a.i][b.i]||A(%a,b){@C(a,b)!=0?0:a.x<0==b.x<0&&a.y<0==b.y<0&&L(a)>L(b)},p,a,b)?0:(p=(v=V(a,b),p[k](%x){@C(v,V(a,x))>=0})),A(%a,b){@C(a,b)>0},p,b,f)?0:(p.forEach(%q){@F(p[k](%r){@q!==r}),s.concat([q]))}),s[2]&&p[n]==0&&!e[b.i][f.i]?G(s):0)))};e=p.map(%x,i){@p.map(%y,j){@i==j})});for(i=p[n];i--;){for(j=i;j--;){q=p[k](%p,x){@x!=i&&x!=j});F(q,[p[i],p[j]]);F(q,[p[j],p[i]]);e[i][j]=e[j][i]=1}}console.log(r)}})(%a,b){@{x:b.x-a.x,y:b.y-a.y}},%a,b){@a.x*b.y-a.y*b.x},%v){@v.x*v.x+v.y*v.y},0,'filter','length')".replace(/%/g,'function(').replace(/@/g,'return '))

```

Code returns an anonymous function. As a parameter, it takes an array of points, like `[[0,1],[2,3],[4,5]]`. To use it you can place `var f=` before it, or if you want to use it from the command line, add `(process.argv[2].replace(/ /g,'').slice(1,-1).split(')(').map((x)=>x.split(',')))` to the end, and call it like `node convpol.js '(1,2)(3,4)(5,6)'`

Thanks for the challenge! As there is no reference implementation, I can't prove this is correct, but it is consistent at least for permutations of the point list. I almost didn't think this was going to work, as versions with debugging code, even disabled, were way too slow with exponential time increase. I decided to golf it anyway, and was pleased to see that it dropped down to under 2 seconds for 50 points on my machine. It can calculate approximately 130 points in 1 minute.

The algorithm is similar to the Graham scan, except that it has to search for empty convex hulls everywhere.

### Explanation

Here's a high-level overview of how the algorithm works. The meat of this algorithm is just searching for counter-clockwise convex loops that don't enclose a point. The procedure is something like this:

1. Start with a pair of points, and a list of all other points.
2. If the current pair of points goes exactly through any point in the list, stop.
3. Filter out all points clockwise of the current pair, since they would make the polygon concave.
4. For all points left, do the following:
    1. If a line from this point to the first point of the chain goes through or encloses any points counter-clockwise, skip this point, since any polygons would enclose the point.
    2. Add this point to the chain, recurse from step 1 with the current chain and list of points.
5. If there were no points left, and the chain has at least 3 points, this is a valid convex polygon. Remember the largest area of these polygons.

Also, as an optimization, we record the initial pair of the chain as checked, so any searches afterwards upon seeing this pair anywhere in the chain can immediately stop searching, since the largest polygon with this pair has already been found.

This algorithm should never find a polygon twice, and I've experimentally verified this.

---
Tags: code-golf, geometry, restricted-time
---


title: Approximate Square Formation

text:
# Question
Title: Approximate Square Formation
# Background

I have a bunch of square-shaped boxes of equal size, and since I'm a neat person, I want to arrange them all into a square formation. However, their number is not necessarily a perfect square, so I may have to approximate the square shape. I want you to find me the most aesthetically pleasing arrangement -- programmatically, of course.

# Input

Your input is a single positive integer `k`, representing the number of boxes.

# Output

Your program shall choose two positive integers `m, n` such that `m*(n-1) < k ≤ m*n` holds. They represent the width and height of the large square-like shape we are arranging. Since we are looking for aestethically pleasing shapes, the quantity `(m - n)<sup>2</sup> + (m*n - k)<sup>2</sup>` shall be minimal, so that the shape is close to a square, and its area is close to `k`. If there are still several candidates for the pair `(m, n)`, choose the one where the width `m` is maximal.

Now, your actual output shall *not* be the numbers `m` and `n`. Instead, you shall print the arrangement of boxes, using the character `#` to represent a box. More specifically, you shall print `n-1` rows, each of which consists of `m` characters `#`, and then one row of `k - m*(n-1)` characters `#`. Note that the output contains exactly `k` characters `#`.

# Rules and Scoring

There shall not be any leading or trailing whitespace in the output, except that the last row may be padded with trailing spaces to be of length `m`, if desired. There may be one trailing newline, but no preceding newlines. You may use any printable ASCII character in place of `#`, if desired.

You may write a full program, or return a string from a function. The lowest byte count wins, and standard loopholes are disallowed.

# Test Cases

Here are the correct outputs for a few input values.

```
1
#
2
##
3
##
#
4
##
##
8
###
###
##
13
#####
#####
###
17
######
######
#####
18
#####
#####
#####
###
20
#####
#####
#####
#####
21
######
######
######
###
22
######
######
######
####
23
#####
#####
#####
#####
###

```

# Answer
> 6 votes
# Pyth, 28 bytes

```
jbc*\#Qho.a,,N*NJ_/_QN,JQ_SQ

```

Try it online.

The crux is that I sort potential m on the following property:

```
(m - ceil(k/m))^2 + (m*ceil(k/m) - k)^2

```

Note the total absence of `n`. The total shape is defined merely by `m`. Then I transform the above property once more, and my final sorting weight is defined as the Euclidean distance between the following two points:

```
(m, m*ceil(k/m)) and (ceil(k/m), k)

```

This changes the weight values, but not their ordering.

# Answer
> 3 votes
# Python 3, 202 bytes

I know that its longer than the CJam or Pyth solutions, but nevertheless, here is a way of solving this problem in Python:

```
k=int(input())
r,d,s=range(k+1),{},'#'*k
for n in r:
 for m in r:
  if m*n>=k:
   d[m,n]=(m-n)**2+(m*n-k)**2
x,y=max(i for i in d.keys()if d[i]==min(d.values()))
[print(s[i*x:(i*x+x])for i in range(y+1)]

```

The basic principle is that we know m and n are both less than k. Also, m\*n \>= k . That means that we can simply find the minimum of the expression given in the challenge for all m,n \< k, excluding values whose product is greater than k.

# Answer
> 2 votes
## CJam (44 42 bytes)

```
qi_,{)_2$d\/m]_2$-_*@@*2$-_*+~}$W=)'#@*/N*

```

Online demo

I was rather expecting there to be a simpler solution involving square roots, but it's not at all that simple. E.g. for input `31` the row width is two greater than the ceiling of the square root; for `273` (square root just over 16.5) the best approximate square is a perfect 21x13 rectangle.

# Answer
> 1 votes
# CJam, 42 bytes

```
li:K_,f-{:XdK\/m]:YX-_*XY*K-_*+}$0='#K*/N*

```

Try it online

Explanation:

```
li    Get and interpret input.
:K    Store in variable K for later use.
_     Copy.
,     Build sequence [0 .. K-1].
f-    Subtract from K, to get sequence [K .. 1]. Larger values have to come
      first so that they are ahead in ties when we sort later.
{     Begin block for calculation of target function for sort.
  :X    Store width in variable X.
  d     Convert to double.
  K\/   Calculate K/X.
  m]    Ceiling.
  :Y    Store height in variable Y.
  X-    Calculate Y-X.
  _*    Square it.
  XY*   Calculate X*Y...
  K-    ... and X*Y-K
  _*    Square it.
  +     Add the two squares.
}$    Sort by target function value.
0=    Get first element, this is the best width.
'#K*  Build string of K '# characters.
/     Split using width.
N*    Join with newlines.

```

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


title: Solve a game of Accordion

text:
# Question
Title: Solve a game of Accordion
Accordion is a solitaire card game I recently came across where nearly every layout is solvable, but incredibly hard. You can play it here.

## Rules

52 face cards are placed face-up in a random order. **Each turn, you replace a card with a later card, where the two cards**:

* **Share a suit or number** and
* **Are at a distance of 1** (adjacent) **or 3** (two cards in between).

**The game is won when there is only 1 card remaining**. You can assume that each input is solvable. The replaced card must always precede the replacing card.

## Example

As an example, consider the following layout:

```
2H,2S,1S,2D  (H: Hearts, S: Spades, D: Diamonds)

```

There are 3 possible moves here:

1. Replace the `2H` with the adjacent `2S`, so we end up with `2S,1S,2D`
2. Replace the `2S` with the adjacent `1S`, so we end up with `2H,1S,2D`
3. Replace the `2H` with the `2D` (at a distance of 3), so we end up with `2D,2S,1S`

Of those 3 moves, only the last one has the possibility of winning (You win by replacing `2D <- 2S`, then `2S <- 1S`).

## Input/Output

**Your job is to write an Accordion solver**. You are passed a list of cards, and you need to return a list of moves to solve the game.

You are passed a list of cards as a comma-delimited string, where each card is passed as an integer representing their numeric value, then a character representing their suit.

You must return a list of replacements as a comma-delimited string, where each replacement is in the format `Card <- Card` (following the card format described above). The first card in each pair is the card being replaced.

Test cases:

```
5H,1C,12S,9C,9H,2C,12C,11H,10C,13S,3D,8H,1H,12H,4S,1D,7H,1S,13D,13C,7D,12D,6H,10H,4H,8S,3H,5D,2D,11C,10S,7S,4C,2H,3C,11S,13H,3S,6C,6S,4D,11D,8D,8C,6D,5C,7C,5S,9D,10D,2S,9S
5H,9C,11H,7S,7D,12D,6H,10S,3H,4D,12C,2S,3C,5C,7H,6S,1H,8S,2H,11S,4C,10D,12H,9H,2D,4H,6C,13H,11C,2C,10H,8C,1S,11D,3S,12S,7C,5D,13S,8D,4S,6D,13C,3D,8H,13D,1D,9D,9S,1C,5S,10C
7H,11C,8C,7S,10D,13H,4S,10C,4D,2C,4H,13D,3C,2H,12C,6C,9H,4C,12H,11H,9S,5H,8S,13S,8H,6D,2S,5D,11D,10S,1H,2D,5C,1C,1S,5S,3H,6S,7C,11S,9C,6H,8D,12S,1D,13C,9D,12D,3D,7D,10H,3S

```

While this competition is a , I am particularly interested in time-efficient solutions, and am likely to reward ingenious solutions with bounties. That said, solutions that take astronomical amounts of time are still acceptable (I'd recommend testing with a smaller deck, such as a 16-card, 4 suit deck).

# Answer
# Python 3, ~~274~~ ~~272~~ 271 bytes

*2 bytes saved thanks to @orlp.*

```
def g(p):
 q=lambda a:[[i,a]for i in range(len(p)-a)if p[i][:-1]==p[i+a][:-1]or p[i][-1]in p[i+a]]
 for n in q(1)+q(3):
  s=sum(n);c=p[:s]+p[s+1:];c[n[0]]=p[s]
  if g(c):return p[n[0]]+' <- '+p[s]+','+g(c)
 return' 'if len(p)<2else[]
print(g(input().split(','))[:-2]or'')

```

This is extremely slow. However, you can try it with a memoize. This has a few extra `list`-`tuple` conversions, but is otherwise equivalent.

```
import functools
@functools.lru_cache(maxsize=None)
def g(p):
 q=lambda a:[[i,a]for i in range(len(p)-a)if p[i][:-1]==p[i+a][:-1]or p[i][-1]in p[i+a]]
 for n in q(1)+q(3):
  s=sum(n);c=list(p[:s]+p[s+1:]);c[n[0]]=p[s]
  if g(tuple(c)):return p[n[0]]+' <- '+p[s]+','+g(tuple(c))
 return' 'if len(p)<2else[]
print(g(tuple(input().split(',')))[:-2]or'')

```

Even this one is astronomically slow with certain inputs.

The code uses strings, not numbers, so it also supports notation like `KH` instead of `13H`.

Example:

```
$ python accordion.py
5H,9C,11H,7S,7D,12D,6H,10S,3H,4D,12C,2S,3C,5C,7H,6S,1H,8S,2H,11S,4C,10D,12H,9H,2D,4H,6C,13H,11C,2C,10H,8C,1S,11D,3S,12S,7C,5D,13S,8D,4S,6D,13C,3D,8H,13D,1D,9D,9S,1C,5S,10C
7S <- 7D,7D <- 12D,3C <- 5C,12H <- 9H,11C <- 2C,3S <- 12S,13D <- 1D,1D <- 9D,9D <- 9S,2S <- 6S,7H <- 1H,6S <- 8S,1H <- 2H,8S <- 11S,2H <- 9H,10D <- 2D,9H <- 4H,4H <- 4C,5C <- 4C,4D <- 4C,4C <- 12C,10S <- 11S,11H <- 11S,6H <- 3H,12D <- 2D,12C <- 2C,2C <- 6C,6C <- 8C,12S <- 13S,5D <- 6D,6D <- 8D,8D <- 3D,4S <- 9S,13S <- 9S,11D <- 3D,7C <- 1C,1S <- 1C,1C <- 13C,8C <- 13C,13C <- 13H,13H <- 10H,2D <- 3D,3D <- 3H,3H <- 8H,8H <- 10H,11S <- 5S,5H <- 10H,5S <- 9S,10H <- 10C,10C <- 9C,9C <- 9S

```
> 5 votes

---
Tags: code-golf, card-games
---


title: Shapeshifting boxes

text:
# Question
Title: Shapeshifting boxes
I define four box styles:

```
+-----+   ooooooo    ^^^^^   *******
|  1  |   o  2  o   <  3  >  *  4  *
|     |   o     o   <     >  *     *
+-----+   ooooooo    vvvvv   *******

```

Write a program or function that given an integer and a string will find one of the above boxes inside the string and change its style into the box style requested by the user. For example:

```
1
This is a test document.
It ********* has
no *purpose* other than
dem*onstrat*ion.
   *********

```

Becomes:

```
This is a test document.
It +-------+ has
no |purpose| other than
dem|onstrat|ion.
   +-------+

```

You may assume that the input contains exactly one valid box that's at least 3x3. Your code must ignore incomplete/incorrect boxes:

```
ooooooooooooooooooooooooooooooooo
o This is not a box. o This is. o
ooooooooooo ooooo ooooooooooooooo

      ^^^^     ######
     <NOPE>    #NOPE#
      vVVv     ######

```

---

Shortest code in bytes wins.

# Answer
> 5 votes
# Julia, ~~995~~ ~~818~~ ~~713~~ 613 bytes

```
g=(s,n)->(w=map;f=t->(t[z=end];for i=1:z-2,j=eachmatch(r"([*o]|(\+)|(\ ))(?(2)-|(?(3)\^|\1))+\1",t[i],1>0),k=i+2:z N=j.match;N[M=end];p=N[1];J=j.offset;u=w(i->i[[J:J+M-1]∩[1:end]],t);try p%3<1?for l=matchall(r"^([*o])\1+\1",u[k]),q=3:endof(l) w(r->r[[1,q]],u[i:k])⊆["$p$p"]&&return(i,k,J,J+q-1)end:u[k]==replace(N,"^","v")&&w(r->r[[1,M]],u[i+1:k-1])⊆[p<33?"<>":"||"]&&return(i,k,J,M+J-1)end;end);o=ones(5)';T=split(s,'\n');(i,j,k,l)=f(T);u=w(collect,T);(a,u[i][r=k+1:l-1],u[j][r],b,c)=41+[2 4 4 83 83;70o;-9 53 77 19 21;o][n,:];u[i][I]=u[j][I=[k,l]]=a;w(e->(e[k]=b;e[l]=c),u[i+1:j-1]);join(w(join,u),'\n'));

```

Ungolfed with explanation:

```
function g(s,n)
  # First, we define function f(t), which finds the box
  function f(t)
    # determine the number of rows of text
    z=length(t)
    # Get an iterator of all of the matches to iterate over
    # Regex handles all four box styles
    temp=i->eachmatch(r"([*o]|(\+)|(\ ))(?(2)-|(?(3)\^|\1))+\1",t[i],1>0)
    # Iterate over rows up to third-last one (i)...
    # and over any possible box-tops on each of those rows (j)...
    # and all possible box-bottom rows for each possible box-top (k)
    for i=1:z-2,j=temp(i),k=i+2:z
      # N holds the matched box-top
      N=j.match
      # M stores the length of the match
      M=length(N)
      # p holds the first letter of the match, the corner character.
      p=N[1]
      # J holds the position of the first character of the match in row i
      J=j.offset
      # The intersection here allows truncation of each row to only those
      # parts that lie within the valid range of the box-top
      u=map(i->i[[J:J+M-1]∩[1:end]],t)
      # A try block is being used to skip if a BoundsError is encountered
      # this BoundsError will occur if a box cannot be formed due to
      # a row not being long enough to form both sides or to form bottom
      try
        # This distinguishes between simple boxes (types 2 and 4)
        # from fancy boxes (types 1 and 3), as code differs between them
        if p%3<1 # "then" for simple boxes
          # loop over l either doesn't run (if bottom won't form a match
          # from position 1 within u) or holds the unique match
          # then loop over q looks at all possible bottom-lengths
          for l=matchall(r"^([*o])\1+\1",u[k]),q=3:endof(l)
            # If box sides are found to match top and bottom...
            if map(r->r[[1,q]],u[i:k])⊆["$p$p"]
              # return the coordinates of the box
              return(i,k,J,J+q-1)
            end
          end
        else # "else" for fancy boxes
          # If the bottom matches the top (replace fixes for type 3)...
          if u[k]==replace(N,"^","v")
            # ... and the edges are also there...
            if map(r->r[[1,M]],u[i+1:k-1])⊆[p<33?"<>":"||"]
              # return the coordinates
              return(i,k,J,M+J-1)
            end
          end
        end
      end
    end
  end
  # That defines function f(t), now for the replacement part of the code
  # Input s is a single string with newlines, split into separate strings
  T=split(s,'\n')
  # Find the coordinates of the box using f(T)
  (i,j,k,l)=f(T)
  # u holds the same strings, but stored as char arrays
  u=map(collect,T)
  # Here, we have the appropriate replacement characters for each type
  # with n determining which character from each array is taken
  # Variable names are used here to make it clearer
  corners =  ['+';'o';' ';'*'][n]
  topedge =  ['-';'o';'^';'*'][n]
  bottomedge=['-';'o';'v';'*'][n]
  leftedge = ['|';'o';'<';'*'][n]
  rightedge= ['|';'o';'>';'*'][n]
  # Assign the appropriate characters in the appropriate places
  u[i][[k,l]]=corners
  u[j][[k,l]]=corners
  u[i][k+1:l-1]=topedge
  u[j][k+1:l-1]=bottomedge
  # Iteration is required here because it's an array of arrays
  for e=i+1:j-1
    u[e][k]=leftedge
    u[e][l]=rightedge
  end
  # All that's left to do is recombine to form a single string again
  # we join each internal char array into single-line strings...
  # then join the strings together with a newline delimiter, and return
  return join(map(join,u),'\n')
end

```

Contrary to how I first approached it, this code will only work correctly for "valid" type numbers - 1, 2, 3, or 4. It is split into two parts - a box-finder, and a box-replacer. The box-finder code, function `f(t)`, uses regex to locate tops and, for the simpler boxes (types 2 and 4), bottoms.

The first regex is the simplest way I could find to find the box-tops. Here's the logic of it:

```
r"([*o]|(\+)|(\ ))(?(2)-|(?(3)\^|\1))+\1"
  ([*o]|(\+)|(\ ))                        < This finds the first corner
        ( 2) ( 3)                         . if a + or space, conditionals
  (    1         )                        . kick in, so they're captured
                                          . separately
                  (?(2)-|           )     < If a +, top edge must be
                                          . at least one -
                         (?(3)\^|\1)      < Otherwise, if a space, top
                                          . edge must be at least one ^,
                                          . otherwise, repeat the corner
                                     +    < Allows more than one top-edge
                                          . character
                                      \1  < finish with the same corner
                                          . char found at the start

```

The code is used like this:

```
julia> s="""This is a test document.
       It************* has
       no *purpose* other than
       dem*onstrat*ion.
        ************o""";

julia> print(s)
This is a test document.
It************* has
no *purpose* other than
dem*onstrat*ion.
 ************o
julia> print(g(s,1))
This is a test document.
It*+-------+*** has
no |purpose| other than
dem|onstrat|ion.
 **+-------+*o

```

Printing is not included in the function, as the output format isn't specified - I just return the string, you can print it afterwards as seen above.

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