title: Place a Carcassonne tile

text:
# Question
Title: Place a Carcassonne tile
**The board game**

In the board game "Carcassonne" players place tiles by matching their edges and earn the highest scores through creating large contiguous areas of terrain. The following are (roughly) the types and quantities of tiles included in the game:

`#01` `x4` `#02` `x5` `#03` `x8` `#04` `x2`

`#05` `x9` `#06` `x4` `#07` `x1` `#08` `x3`

`#09` `x3` `#10` `x3` `#11` `x4` `#12` `x5`

`#13` `x3` `#14` `x3` `#15` `x2` `#16` `x5`

`#17` `x5` `#18` `x2` `#19` `x3` `#20` `x1`

`#21` `x5` `#22` `x2` `#23` `x1` `#24` `x1`

`#25` `x1`

**The Task**

You must place a tile by matching edges, while trying to maintain the largest possible contiguous areas of terrain.

**Placement**

* Tiles can only be placed in one of the (up to 4) blank spaces adjacent to any existing tile (or tiles) in the play area.
* Tiles can be rotated 90, 180 or 270 degrees.

**Edge-matching**

* Edges of a placed tile must match the touching edges of the (up to 4) neighbouring tiles, i.e. touching pixels are the same colour.

**Contiguous terrain**

* "Closing an area of terrain" refers to placing a tile such that any contiguous area of colour could not then be continued with further tile placements.
* If an alternative placement is possible, it must be chosen over any tile placement that would close an area of terrain.
* If you have to choose between a number of closing placements, choose any. If you have to choose between a number of non-closing placements, choose any.
* Disregard #ff00ff (the corner pixels) when calculating contiguous areas. Also disregard buildings, i.e. areas of colour already fully enclosed within a tile.

**Input**

* Input is two images:

1. The play area.

    + The initial play area consists of tile `#11` (a single tile).
        + The augmented play area created as output must also be supported as input.
    2. The tile to be placed.

    + All of the example tiles must be supported as input.
* Determine matching edges/contiguous terrain using this image data alone. No hardcoding.

**Output**

* Output is an image showing the resultant play area after placing the tile.
* The image must be compatible with your own program, i.e. it can be used as play area input.
* If it's impossible to place a tile, return an error.

**You can assume that**

* Tiles are always 55 px by 55 px
* Tiles will only ever feature the colours currently used in the example tiles.

**Notes**

* Your answer must feature example output after at least 2 passes (more is encouraged).
* This is a partial and inaccurate rendering of the original board game, you don't need to apply any of the rules or tactics not mentioned here.

**Score**

* Your score is your submission's byte count.
* Image data isn't included in your score.
* Lowest score wins.

---

***Playing a full game** You may wish to write a script that uses your submissison to play a full game, which might consist of:<br>* Placing a tile chosen pseudorandomly from the full set of 85.
* Returning the tile to the set if it can't be placed.
* Repeating until every tile has been placed - or until two tiles in a row can't be placed.*

*It won't be included in your byte count, or improve your score, but I'll likely offer a bounty to this kind of answer.*

# Answer
# Perl 5 with PerlMagick: 875 789 763

I did not count the line starting with `sub w`, which is used to sort positions on the distance to the center to prefer compact solutions (now working properly). In this version closing is avoided like requested but I find the opposite more interesting and true to the game. To achieve that change the line `$s=$t if!grep...` to `$s=$t if grep...`.

```
use Image::Magick;
sub p{/x/;@o=$r->GetPixel(y=>$'+pop,x,$`+pop);"@o"}
sub o{$w=&p;"0 0 0"eq$w?3:&p eq$w}
sub f{$r->FloodfillPaint(y=>$J+$',x,$I+$&,channel,All,fill,@_)}
($i=Image::Magick->new)->Read(@ARGV);$r=$b=$i->[0];
$h=$b->Get(rows)+112;$:=$b->Get(width)+112;
$b->Extent(geometry,"$:x$h-56-56",background,none);
@v=grep p()eq"0 0 0",map{map-54+55*$_.x.($'*55-54),//..$:/55}1..$h/55;
sub w{$_=pop;/x/;abs($:-2*$`)+abs($h-2*$')}@v=sort{w($b)<=>w($a)}@v;
map{map{/x/;$I=$`;$J=$';$r=$b->Clone();
($t=$r)->Composite(image,$i->[1],x,$I,y=>$J);
if((o(27,0,27,-1)&o(0,27,-1,27)&o(27,54,27,55)&o(54,27,55,27))==1){
$s=$t if!grep{/../;$r=$t->Clone();f(none);f(red);
!grep{p()eq"1 0 0"}@v}
map{/..$/;($_,$&.$`)}map{($_.-1,$_.55)}10,27,45;
$o=$r=$t;}$i->[1]->Rotate(degrees,90)}($_)x4}@v;
$s||=$o or exit 1;$s->Trim();$s->Write("car.png")

```

Usage: `perl car.pl board.png tile.png`. Result stored in `car.png`. Exit status is 1 if the tile could not be placed.

Script to run a complete game. It assumes the code above is in the file `car.pl` and the tiles are stored in `tiles` directory named `01.png` to `25.png`.

```
use List::Util shuffle;$x='00';
@t=shuffle map{($x++)x$_}split'',a4582941333353325523152111;
`cp tiles/11.png car.png`;
$i++,`perl car.pl car.png tiles/$_.png`,print"placed $i\n"for@t

```

This runs quite slowly now. 8-12 minutes on my machine. With closing preferred: With closing avoided (note nothing is closed).
> 9 votes

# Answer
# Common Lisp, 2650 2221 1992 1186 1111 bytes

*Update:* "Easy" golfing now done, further gains will require bigger changes.

*Update 2:* With the competition getting fiercer, the new version no longer favors positions inside the current playing field rectangle (that would be 57 bytes extra). This option, as well as a simple speed optimization, is by enabled by default in the downloadable version with the simulator, but not in the official answer below.

*Update 3:* Minor interface changes for major byte count gains.

I created a simple Web UI as well. The full package (a single LISP file and the tile images) can be downloaded here. To try it, install `hunchentoot`, `zpng` and `png-read` with quiclisp, load in `carcassonne.lisp`, and connect to `localhost:8080`. The code has been tested on CCL/Windows and SBCL/Linux. The above mentioned libraries are only needed for the UI/simulator part; the solution itself is plain ANSI Common Lisp.

```
(defun c(f p &aux b a s z(c 55))
  (macrolet((d(v l &body b)`(dotimes(,v,l),@b))
            (b(b c)`(d i c(d j c(setf,b,c))))
            (r(&rest p)`(aref,@p))
            (n(u v i j)`(and(setf l(*(f,u,v)l))
                            (find(r f(+,u,i)(+,v,j))`(0,(r f,u,v))))))
    (labels((p(p w)(d y(ceiling w 2)(d x(- w y y)(rotatef(r p y #6=(+ x y))(r p #6##7=(- w y))(r p #7##8=(- w x y))(r p #8#y)))))
            (a(y x)(or(if(= 0(r f y x))1 #4=(and(= 1(incf(r s y x)))(=(r f y x)z)(push`(,y,x)a)0))0))
            (f(y x)(setf z(r f y x))(if #4#(loop for((y x))= a while(pop a)maximize(+(a(1- y)x)(a y(1- x))(a(1+ y)x)(a y(1+ x))))1)))
      (d i 8(when(d x #1=(array-dimension f 0)(or(= 0(r f(- #1#52 i)x))(return t)))(setf f(adjust-array f`(#2=,(+ #1#c)#2#))))(p f(1- #1#)))
      (d i 4(d u #9=(/ #1#c)(d v #9#
        (let((y(* u c))(x(* v c))(l 9e9))
          (when(= 0(r f y x))
            (b #10=(r f(+ y i)(+ x j))(r p i j))
            (setf s(make-array`(,#1#,#1#))a())
            (ignore-errors(if(> #11=(*(loop for d from 1 to 53
                                            sum(+(n y #3=(+ x d)-1 0)(n #5=(+ y d)(+ 54 x)0 1)(n(+ 54 y)#3#1 0)(n #5#x 0 -1)))
                                      (1+ l))
                                (or(car b)0))
                             (setf b`(,#11#,i,y,x))))
            (b #10#0)))))
         (p p 54))
      (when b(d j(cadr b)(p p 54))(b(r f(+(third b)i)(+(nth 3 b)j))(r p i j)))
      `(,f,b))))

```

All line feeds and line-starting spacing are for cosmetics only, to ensure legibility, and not counted into the total sum.

You should call the function `c` with two arguments: The current play field, and the tile to place. Both should be 2D arrays; the tile 55x55 and the field a multiple of that. Additionally, the field array must be adjustable. The function returns a two-element list with the new field as its first argument. The second element is `NIL` if the tile cannot be placed, or otherwise a list containing the top-left coordinates and rotation of the latest tile on that array and the score for that tile. This information can be used for visualization purposes.

Note that in further calls, you must use the new field returned by `c` even if the second list element is `NIL` (the original array may have been `adjust-array`ed and thus invalidated).

The code is now a bit on the slow side, byte count optimization resulting in redundant calculations. The example below completed in about three minutes on my system.

Example run for all 85 tiles:

Web UI screenshot:
> 16 votes

# Answer
# DarkBASIC Pro: ~~2078~~ ~~1932~~ 1744 bytes

UPDATE: Just more golfing effort

UPDATE: Now fully meets the spec, including preferring non-closing choices.

I chose DarkBASIC because while it's rather verbose, it provides an extremely straightforward and simple command set for manipulating images.

I uploaded an EXE for people who don't have the DarkBASIC compiler (Windows).

```
#constant m memblock
#constant f function
#constant k endfunction
#constant z exitfunction
#constant i image
#constant e endif
#constant t then
#constant o or
#constant s paste image
#constant n next
#constant r for
set i colorkey 0,20,0:load i "map.png",1:f$="next.png"
if file exist(f$)=0 t f$=str$(rnd(24)+1)+".png"
load i f$,2:make m from i 1,1:make m from i 2,2
global ts,h,j,u,v,td
ts=i width(2):h=i width(1):j=i height(1):u=h/ts:v=j/ts:td=ts*2
create bitmap 2,h+td+1,j+td+1:r b=1 to 4:r xx=0 to u+1:r yy=0 to v+1:x=xx*ts-1:y=yy*ts-1
cls 5120:s 1,ts,ts,1:if (a(x+1,y) o a(x,y+1) o a(x-ts,y) o a(x,y-ts)) and a(x,y)=0
x1=ts*xx:y1=ts*yy:make i from m 2,2:s 2,x1,y1,1
cl=0:r fd=0 to 1:r x2=1 to ts-2:r yt=0 to 1:y2=yt*ts-yt:y3=yt*ts+yt-1
aa=x2:ab=x2:ba=y2:bb=y3:t2=y1:r t3=0 to 1:p=point(x1+aa,y1+ba):q=point(x1+ab,y1+bb)
if p<>q and rgbg(q)<>20 and t2+b>0 t goto fa
if fd and p<>0xFF0000
if l(x1+aa,y1+ba,p)=0 t cl=1
e
aa=y2:ba=x2:bb=x2:ab=y3:t2=x1:n t3:n yt:n x2:n fd:dn=1:c=xx-1:g=yy-1:make i from m 3,2:if cl=0 t goto dm
e
fa:
n y:n x
d=ts/2:r x=0 to d:r y=0 to d-1:vx=ts-1-x:vy=ts-1-y:t1=rd(x,y):t2=rd(vy,x):wr(vy,x,t1):t1=rd(vx,vy):wr(vx,vy,t2):t2=rd(y,vx):wr(y,vx,t1):wr(x,y,t2):n x:n y:n b
dm:
if dn=0 t report error "Not placed"
p=c<0:q=g<0:t1=h+ts*(p o c>=u):t2=j+ts*(q o g>=v):cls 5120:p=ts*p:q=ts*q:s 1,p,q,1:s 3,c*ts+p,g*ts+q,1:get i 1,0,0,t1,t2,1:save i "map.png",1
end
f l(x,y,w)
if x<0 o y<0 o x>=h+td o y>=j+td t z 1
p=point(x,y)
if rgbg(p)=20 t z 1
if p<>w t z 0
dot x,y,0xFF0000:rt=l(x+1,y,p) o l(x-1,y,p) o l(x,y+1,p) o l(x,y-1,p)
k rt
f rd(x,y)
w=m dword(2,0):b=m dword(2,12+(y*w+x)*4)
k b
f wr(x,y,d)
w=m dword(2,0):write m dword 2,12+(y*w+x)*4,d
k
f a(x,y)
if x<0 o y<0 o x>=h o y>=j t z 0
b=m byte(1,15+(y*h+x)*4)
k b

```
> 10 votes

---
Tags: code-golf, graphical-output, game
---


# Question
Title: Calculate the Delacorte Number of a square
### Challenge: implement calculation of a Delacorte Number in any language. Shortest code wins.

For a given square matrix of distinct integers *1..n²* (possible side length *n* at least between 3 and 27), its Delacorte Number is the sum of the products *gcd(a, b) × distance²(a, b)* for each distinct pair of integers {a, b}.

The following example shows a 3×3 square with a Delacorte Number of 160.

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

```

In this square we have 36 distinct pairs to calculate, for example the pair 4 and 6: *gcd(4, 6) × distance²(4, 6) = 4*

Another example square for testing - this has a Delacorte Number of 5957:

```
10  8 11 14 12
21  4 19  7  9
 5 13 23  1 16
18  3 17  2 15
24 22 25  6 20

```

Delacorte Numbers are taken from this programming contest \- see there for further details... The contest ended in January 2015. It was great fun!

### Rules:

Necessary line breaks count as 1 char. You may post your golfed solution with line breaks, but they are only counted if necessary in that language.

You can choose how to handle input and output and you don't have to count the **necessary** framework of your language, like standard-includes or main function headers. Only the actual code counts (including shortcut/alias definitions), like in this C# example:

```
namespace System
{
    using Collections.Generic;
    using I=Int32; //this complete line counts
    class Delacorte
    {
        static I l(I[]a){return a.Length;} //of course this complete line counts

        static void CalculateSquare(int[] a, out int r)
        {
            r=0;for(I i=l(a);i-->0;)r+=a[i]; //here only this line counts
        }

        static void Main()
        {
            int result;
            CalculateSquare(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, out result);
            Console.Write(result); //should output 140 for the example
            Console.ReadKey();
        }
    }
}

```

You may also input the square as 2-dimensional array or from a prompt or as string or some standard collection type. A 2-dimensional array is the only way not having to calculate the side length of the square yourself.
A sub-function for the actual work is not required, you could also put the code directly within Main().

Even more preparation is allowed for free, like here:

```
using System;
unsafe class Delacorte
{
    static void CalculateSquare(int* a, out int r)
    {
        r=0;while(*a>0)r+=*a++; //only this line counts
    }

    static void Main()
    {
        var input = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; //adding a terminator
        int result;
        fixed (int* a = &input[0]) //necessary in C#
            CalculateSquare(a, out result);
        Console.Write(result);
        Console.ReadKey();
    }
}

```

If you are unsure whether your lengthy preparation is in the spirit of these rules or could be called cheating, just ask :)

# Answer
> 6 votes
## APL (38)

```
{.5×+/∊∘.{(∨/Z[⍺⍵])×+/⊃×⍨⍺-⍵}⍨⊂¨⍳⍴Z←⍵}

```

This is a function that takes a matrix as its right argument, like so:

```
      sq5←↑(10 8 11 14 12)(21 4 19 7 9)(5 13 23 1 16)(18 3 17 2 15)(24 22 25 6 20)
      sq5
10  8 11 14 12
21  4 19  7  9
 5 13 23  1 16
18  3 17  2 15
24 22 25  6 20
      {.5×+/∊∘.{(∨/Z[⍺⍵])×+/⊃×⍨⍺-⍵}⍨⊂¨⍳⍴Z←⍵}sq5
5957

```

Explanation:

* `⊂¨⍳⍴Z←⍵`: store the matrix in `Z`. Make a list of each possible pair of coordinates in `Z`.
* `∘.{`...`}⍨`: for each pair of coordinates, combined with each pair of coordinates:
    + `+/⊃×⍨⍺-⍵`: calculate `distance^2`: subtract the first pair of coordinates from the second, multiply both by themselves and sum the result
    + `∨/Z[⍺⍵]`: get the number in `Z` for both pairs of coordinates, and find the GCD
    + `×`: multiply them by each other
* `+/∊`: sum the elements of the result of that
* `.5×`: multiply by 0.5 (because we counted each nonzero pair twice earlier)

# Answer
> 5 votes
# Python - ~~128 112 90 89~~ 88

Preparation:

```
import pylab as pl
from fractions import gcd
from numpy.linalg import norm
from itertools import product

A = pl.array([
    [10,  8, 11, 14, 12],
    [21,  4, 19,  7,  9],
    [ 5, 13, 23,  1, 16],
    [18,  3, 17,  2, 15],
    [24, 22, 25,  6, 20]])

```

Computing the Delacorte Number (the line that counts):

```
D=sum(gcd(A[i,j],A[m,n])*norm([m-i,n-j])**2for j,n,i,m in product(*[range(len(A))]*4))/2

```

Output:

```
print D

```

Result:

```
5957

```

# Answer
> 5 votes
# Mathematica (~~83~~ ~~82~~ ~~79~~ ~~69~~ ~~67~~ 66)

Preparation

```
a={{10,8,11,14,12},{21,4,19,7,9},{5,13,23,1,16},{18,3,17,2,15},{24,22,25,6,20}}

```

Code

```
#/2&@@Tr[ArrayRules@a~Tuples~2/.{t_->u_,v_->w_}->u~GCD~w#.#&[t-v]]

```

If we count using Unicode characters: **62**:

```
Tr[ArrayRules@a~Tuples~2/.{t_u_,v_w_}u~GCD~w#.#&[t-v]]〚1〛/2

```

# Answer
> 3 votes
## Pyth 43

This answer could almost certainly be golfed further; I particularly don't like the distance calculation.

```
K^lJ.5VJFdUN~Z*i@JN@Jd+^-/dK/NK2^-%dK%NK2;Z

```

To set this up, store the linear-ized array in the variable J. You can do this by writing:

```
J[3 2 9 4 1 8 5 6 7)

```

Try it online.

Outputs a float. I think this is legitimate, please tell me if I've broken a rule :)

Explanation:

```
                                             : Z=0 (implicit)
K^lJ.5                                       : K=sqrt(len(J))
      VJ                                     : for N in range(len(J))
        FdUN                                 : for d in range(N)
            ~Z*                              : Z+= the product of
               i@JN@Jd                       : GCD(J[N],J[d])
                      +^-/dK/NK2^-%dK%NK2    : (d/K-N/K)^2 + (d%K-N%K)^2 (distance)
                                         ;Z  : end all loops, and print Z

```

# Answer
> 2 votes
# CJam, 55

```
q~:Q__,mqi:L;m*{_~{_@\%}h;\[Qf#_Lf/\Lf%]{~-_*}/+*}%:+2/

```

Takes the matrix as STDIN in the following format:

```
[10  8 11 14 12
 21  4 19  7  9
  5 13 23  1 16
 18  3 17  2 15
 24 22 25  6 20]

```

Try it online here

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


title: The Fatal Error Challenge

text:
# Question
Title: The Fatal Error Challenge
## Objective

Write a routine that accepts a string of printable ASCII characters, *s*, and returns a string containing the same characters as *s*, reordered so that no two-character substring appears more than once. The program must process all benchmark strings (see below) in under one minute each on a modern computer. I will also award a special bonus of **50 rep** to the lowest scoring answer that processes *any* valid 30-character string in under one minute.

For example, given the input `Mississippi`, a valid output would be `issiMspiips` (no two-character substrings appear twice), while an invalid output would be `ipMsispiiss` (since the substring `is` appears twice).

The routine may take the form of:

* a complete program reading from `stdin` (or equivalent) or the command line, and outputting to `stdout` (or equivalent)
* a function accepting a single string argument and returning a string

You may assume that the input string always admits at least one valid output.

## The Challenge

Your routine must comprise 5 or more lines of code separated by newlines. Empty lines (which includes lines containing only whitespace) are ignored in all contexts and do not count towards total line count.

Swapping any two lines in your source code **must** produce a fatal error. By "fatal error", we refer to any of the following conditions:

* the source code fails to compile, with the compiler/interpreter declaring a fatal error
* the routine aborts with a runtime fatal error or an unhandled runtime exception
* the routine is forced into an abrupt, abnormal program termination that produces no output of any kind except for a possible error message and/or stack dump

**Alternatively**, contiguous blocks of code containing no newline characters may be used in place of lines. These blocks should each be displayed on their own line in the source file, with the understanding that newlines are stripped out before the source code is compiled/interpreted.

For example, the code

```
aaaa
bbbb
cccc

```

would condense to

```
aaaabbbbcccc

```

before being evaluated.

In this mode, the fatal error condition applies to swapping any two code blocks (and thus to swapping lines in the source code before newlines are stripped out). Hence in the above example the routines `aaaaccccbbbb`, `bbbbaaaacccc`, and `ccccbbbbaaaa` must all produce fatal errors, either at compiletime or runtime.

Submissions using this alternative mode should declare its use.

## Scoring

Let *n* be the number of non-empty textlines in your source file, with *n* ≥ 5. Let *c* be the number of bytes comprised by the **longest textline** (by byte length) in your source file, not counting any trailing newline.

A submission's score is given by *c*(*n* \+ 10).

The submission with the lowest score is the winner.

Best of luck. ;)

## Benchmark Strings

```
Abracadabra Alacazam
Is Miss. Mississauga Missing?
Ask Alaska's Alaskans
GGGGAAAATTTTCCCCgggaaatttccc
A Man A Plan A Canal Panama

```

# Answer
> 6 votes
# PHP, score = 289 (17×(7+10))

PHP's built-in functions make it quite easy to do this badly. The following code just shuffles the string until a valid result is obtained:

```
function f($s){
while(preg_match(
'/(..).*?\1/',$s)
+preg_match('/(.'
.')\1\1/',$s))$s=
str_shuffle(
$s);return $s;}

```

---

## Benchmarks

Average and maximum execution times calculated using the following code:

```
$s = 'Mississippi';
$t_total = 0;
$t_max = 0;
for ($i=0; $i<10; $i++) {
  $t0 = microtime(true);
  echo f($s);
  $t = microtime(true) - $t0;
  printf("  %10.7f\n",$t);
  $t_total += $t;
  if ($t > $t_max) $t_max = $t;
}
printf("Avg: %10.7f secs; Max: %10.7f secs\n",$t_total/$i, $t_max);

```

**Results:**

* Mississippi: Avg: 0.0002460 secs; Max: 0.0005491 secs
* Anticonstitutionnellement: Avg: 0.0001470 secs; Max: 0.0002971 secs
* Pneumonoultramicroscopicsilicovolcanoconiosis: Avg: 0.0587177 secs; Max: 0.1668079 secs
* Donaudampfschiffahrtselektrizitatenhauptbetriebswerkbauunterbeamtengesellschaft*: Avg: 9.5642390 secs; Max: 34.9904099 secs
* baaacadaeafbbcbdbebfccdcecfdde: Avg: 5.0858626 secs; Max: 9.8927171 secs

* I changed `ä` to `a` to avoid multi-byte issues
† This was the hardest 30-character string I could come up with. It's actually the first 30 characters of the De Bruijn sequence for *k*='abcdef' and *n*=2, with the first 'b' moved to avoid an instant match.

# Answer
> 5 votes
## Dyalog APL (11(5+10)=165)

```
f←{a←{⍴⍵}
b←a⌸2,/⍵
c←b⊢⍵[?⍨a⍵]
1∨.≠b:∇c⋄⍵
}

```

Proof:

* Lines 1 and 5 bound the function. Swapping any line for those would result in  occurring outside of a function, which is a `SYNTAX ERROR`.
* Line 2 defines `b`, so it cannot be swapped for lines `3` or `4`, which depend on `b`. There would be a `VALUE ERROR`. (And it obviously can't be swapped with `1` or `5` either.)
* Line 3 defines `c`, so it cannot be swapped for line `4`, which depends on `c`. (And we've already proven no other line can be swapped with line `3`.)
* Line 4 depends on the variables from lines 2 and 3 and must therefore be last.

# Answer
> 4 votes
## APL(Dyalog), 6(5+10) = 90

```
{1∧.=
+/∘.≡⍨
2,/⍵:⍵
⋄∇⍵[
?⍨⍴⍵]}

```

I'm using the alternative, so:

```
{1∧.=+/∘.≡⍨2,/⍵:⍵⋄∇⍵[?⍨⍴⍵]}

```

This is the same old algorithm.

---

**Explanation**
`2,/⍵` gives an array of character pairs in the input string
`+/∘.≡⍨` generates a numerical array of how many pairs does each pair equal (including itself)
`1∧.=` checks if each element of that array equals 1, and logical AND the results together

`:⍵` If that is true (`1`), return the input string

`∇⍵[?⍨⍴⍵]` else scramble the input string and do a recursive call

---

**Swapping**

If line 1 is swapped with line 2, then you end up with `+/∘.≡⍨{...}` which is just a mess of functions and operators that gives `SYNTAX ERROR`.
If line 1 is swapped with line 3 or 4, then you have  outside of a function definition, and that's a `SYNTAX ERROR`.
If line 1 is swapped with line 5, unbalanced braces alone would cause `SYNTAX ERROR`, so don't worry about the other 4 syntax errors.

If line 5 is swapped with line 2/3/4, again you have  outside of a function definition.(`SYNTAX ERROR`)

If line 2 is swapped with line 3, you end up with `1∧.=2,/⍵:⍵`. This syntax is called a guard (think of it as a conditional). The guard condition must evaluate to `0` or `1` or a 1-element array of `0` or `1`. Here, it evaluates to something more complex than that (a scalar containing a 2-element array). So this is a `DOMAIN ERROR`.
If line 2 is swapped with line 4, you get the statement `1∧.=`, which attempts to apply the function `∧.=` without the required left argument. (`SYNTAX ERROR`).

If line 3 is swapped with line 4, again you get a mess of functions and operators (`1∧.=+/∘.≡⍨`) so you get `SYNTAX ERROR`.

---

**Benchmarks**
(numbers in milliseconds)

```
Abracadabra Alacazam
11 1 3 5 2
Avg: 4.4

Is Miss. Mississauga Missing?
1260 2000 222 117 111
Avg: 742

Ask Alaska's Alaskans
7 2 3 3 4
Avg: 3.8

GGGGAAAATTTTCCCCgggaaatttccc
31 15 24 13 11
Avg: 18.8

A Man A Plan A Canal Panama
377 2562 23 301 49
Avg: 662.4

```

---

I am still thinking about different splittings. Also I have a deterministic, systematic way of doing the task. I just can't make it into an algorithm (take away the creative part of "making the numbers right") and can't make sure it works every time.

# Answer
> 0 votes
# Haskell, 129 = 3x(33 + 10)

this uses the alternative mode.

```
imp
ort
 Da
ta.
Lis
t;a
%[]
=[[
]];
a%s
=[x
:j|
x<-
s,n
ot$
isI
nfi
xOf
[la
st
a,x
]a,
j<-
(a+
+[x
])%
(s\
\[x
])]
;g
s=[
]%s
!!0

```

or in a readable form:

```
import Data.List
a%[]=[[]]
a%s=[x:j|x<-s,not$isInfixOf[last a,x]a,j<-(a++[x])%(s\\[x])]
g s=[]%s!!0

```

Haskell is a very strict language. for example, the `import` must come first; the definitions of `s` must come together; all the types must agree and there is no way to cast between them, and so forth. this leads to having a non-fatal error almost impossible. in fact, having a runtime fatal error is too almost near impossible.

note that if `g` is a valid function but has an the wrong type (any type different then `[a]->[a]` or `String -> String` and the like) than this is a fatal error because it's impossible to apply `g` to the inputs.

outputs:

```
Abracadabar Alaazcma
Is Miss. iMsiasusgsa sMniig?s
Ask Alasak's lAaankss
GGAGTGCAATACTTCCggagtaacttcc
A Man AP la nAC  aalnnaPama

```

---
Tags: code-challenge, restricted-source, source-layout, restricted-time
---


title: Evaluate CDF of Student-t distribution

text:
# Question
Title: Evaluate CDF of Student-t distribution
The goal of this codegolf is evaluating the cumulative distribution function of the student-t probability distribution. This is not trivial since there is no closed form and the function is dependent of two variables `v` and `x`. The distribution function is

For getting the CDF you could integrate this function from `-inf` to `x`. As you can see the evaluation of this function relies much on integration as you'd also have to evaluate nontrivial values of the gamma function.

## Details

You can can write a program or function that accepts a two numbers `x`and `v` as input, where `x` is the position (must at least accept floats from -10 upto 10) at which the CDF is evaluated and `v` is the number of degrees of freedom. `v` is a positive integer (range `1` upto `1450`) but it must be possible to set it to *infinity* (for `v=inf` the student-t distribution is equal to the normal distribution). But you can specify that e.g. `v = -1` should denote infinity. The output consists must be a number between 0 and 1 and must have an accuracy of at least *4 decimal places*. If your language does not support runtime inputs or arguments on program call you may assume that both arguments are stored in variables (or another 'memory unit')

## Restrictions

You may not use special functions like the gamma function or probability distribution functions as well as numerical integration functions or libraries (as long as you do not include their source in your code which counts for the score) etc. The idea is using only basic math functions. I tried to make a list of what I consider as 'basic' but there might be others I forgot - if so please comment.

Explicitly ***allowed*** are

```
+ - / *
% (modulo)
! (factorial for integers only)
&& || xor != e.t.c. (logical operators)
<< >> ^ e.t.c. (bitshift and bitwise operators)
** pow (powerfunction for floats like a^b including sqrt or and other roots)
sin cos tan arcsin arccos arctan arctan2
ln lb log(a,b)
rand() (generating pseudorandom numbers of UNIFORM distribution)

```

## Scoring

Lowest number of bytes wins.

## Entry

Please explain how your code works. Please show the output of your program for at least 5 different arguments. Among those should be the following three. For your own values please also provide 'exact' values (like from wolframalpha or what ever you prefer).

```
x = 0      v= (any)  (should return 0.5000)
x = 3.078  v= 1      (should return 0.9000
x = 2.5    v= 23     (should return 0.9900)

```

If possible, it would be great if you could provide some fancy plots of the values calculated with your program (the code for plotting does not count for the score).

(from Wikipedia):

# Answer
# BBC BASIC, 155 ASCII characters, tokenised filesize 140

Download emulator at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

```
  a=1s=.000003INPUTx,v
  IFv<1v=9999
  FORw=1TOv-1a=w/a
  NEXTb=SGN(x)*s*a/SQR(v)IFv MOD2b=b/PI ELSEb=b/2
  f=.5FORz=0TOABS(x)STEPs
  f+=b/(1+z*z/v)^(v/2+.5)NEXTPRINTf

```

The code is in two parts. The first calculates the coefficient that is independent of x. and stores it in `b`. The algorithm is a bit like a continued fraction, but a mathematician would probably call it a simple quotient of two products. It's based on a formula from the Wikipedia page in the question, which is similar to a factorial but has the product `(v-1)(v-3)...` divided by the product `(v-2)(v-4)...` This is possible because we are only interested in half-integral values of the gamma function (arbitrary values of the gamma function would be a lot harder.) Using this formula we never have to calculate either gamma function, so we avoid large numbers. The largest intermediate value is approximately the square root of `v`.

The second is a straightforward integration from 0 to x by summation. It is known that f(0) is 0.5 so we start from there and work outwards. the sign and magnitude of `b` are modified before the loop, in order to be able to give the final answer directly.

**Pretty version, ungolfed**

This contains a few extra lines to add colour and to plot the data. The range x=0 to endpoint, and f(x)=0.5 to 1 is shown. Also `v` is modified to `2^v` to be able to show the full range of v values without exceeding the limits on colour. In order to speed the drawing up, there are two less digits in `s` than in the golfed version. Even so, there is only one discrepancy when compared with http://www.wolframalpha.com/input/?i=student+t-distribution+probability: `0.8130575` rounds up to 0.8131. The golfed version give the correct answer `(0.8130)` for this and all the other cases below.

```
  a=1                              :REM accumulator for gamma series
  s=.0001                          :REM step size for x integration
  INPUTx,v
  IFv<1 v=9999                     :REM if v<1, set v to a value that gives results indistinguishable from infinity
  GCOLv                            :REM pick a colour
  v=2^v                            :REM for the pretty version, modify v to 2^v
  FORw=1TOv-1
    a=w/a                          :REM calculate series as per Wikipedia
  NEXT
  b=a/SQR(v)                       :REM divide a by the necessary values...
  IFv MOD2 b=b/PI ELSE b=b/2       :REM to give the coefficient, per Wikipedia

  b*=SGN(x)*s                      :REM modify according to sign and step size
  f=.5                             :REM initialise f(x)=.5 at x=0
  FORz=0TO ABS(x) STEPs
    f+=b/(1+z*z/v)^(v/2+.5)        :REM perform integration as simple "barchart" sum
    PLOT69,z*100+200,(f-.5)*1600   :REM plot a point
  NEXT
  PRINT f

```
> 5 votes

---
Tags: code-golf, math, probability-theory, calculus
---


# Question
Title: Decompose a number with bit-xor without the digits 0, 3, 7
## Challenge

Write a function or program which takes a positive decimal number, call it *A*, and output two positive numbers, *B* and *C*, such that:

* *A* == *B* bitxor *C*
* *B* and *C* must not contain any of the digits 0, 3 or 7 in its decimal representation.

## Examples

```
>>> decompose(3)
1, 2
>>> decompose(7)
1, 6
>>> decompose(718)
121, 695
>>> decompose(99997)
2, 99999
>>> decompose(4294967296)
4294968218, 922
>>> decompose(5296080632396965608312971217160142474083606142654386510789497504098664630388377556711796340247136376)
6291484486961499292662848846261496489294168969458648464915998254691295448225881546425551225669515922,
1191982455588299219648819556299554251659915414942295896926425126251962564256469862862114191986258666

```

Since the decomposition is not unique, your function/program does not need to output the exact same results as these provided examples.

## Very detailed rules

1. Submissions should be in the form of a **complete function or program**. `import` statements *do* count towards the final score.
2. You may assume the input *A* always contains at least a digit of 0, 3 or 7.
3. You may assume a decomposition always exist.
4. You may use BigInt if they are part of the standard libraries of the language, or can be installed through the language's *de jure* package manager.
5. The function should be fast. It should take no more than **20 seconds** to run on reasonably modern computer when fed a 100-digit number, and no more than 2 seconds when fed a 10-digit number.
6. The function/program should support input up to at least **100 digits**.

* If the function/program can only support integers up to N\<100 digits, there will be a **penalty** of +10×(100/N - 1) bytes to the final score. This is to encourage golfers to support a wider range of numbers even if importing may be verbose.
7. There is **no restriction on the presentation** of input/outputs as long as they are clearly in decimal representation.

* The function may input and output strings/BigInts if the built-in integer types are not sufficient.
    * The input may come from the function parameter, command line argument or STDIN.
    * The function may return the result, or just print the result directly to STDOUT.
    * However, signed overflow in the input/outputs are not allowed.
    * Approximate answers are not tolerated, the input/outputs must be exact.

## Scoring

This is a . Shortest solution in bytes win.

There is a penalty if the program can only support numbers less than 100 digits:

* 64-bit integers (19 digits) = +42 bytes
* 63-bit integers (18 digits) = +45 bytes
* 53-bit integers (15 digits) = +56 bytes
* 31/32-bit integers (9 digits) = +101 bytes

# Answer
> 2 votes
# CJam, 70 bytes

```
ri:Q{;Qmr_Q^`1$`+730`&}g_Q^p

```

Try it online.

Randomly selects integers until it finds a match. This barely complies with the 20 second limit for 64-bit integers (using the Java interpreter), so I've added 42 to the actual byte count.

### Example run

```
$ cjam t <<< 7777777777; echo
2695665494
6161166119

```

# Answer
> 10 votes
# Common Lisp, 240 224 183 173 169 bytes

Common Lisp is a bit verbose for golfing. However, this decomposes 100-digit numbers in under a second, and 200-digit integers in less than ten seconds, so no need for penalties. The algorithm is deterministic.

```
(defun s(z)(and #1=(some(lambda(q)(position q(format()"~a"z)))"037")(+ z(floor z(expt 10 #1#)))))
(defun d(x)(do((y x(or(s y)(s #3=(logxor x y))(return`(,y,#3#)))))(())))

```

The line feed between the functions is for typographic purposes only. Test run with the 100-digit reference input:

```
(time (d 5296080632396965608312971217160142474083606142654386510789497504098664630388377556711796340247136376))
took 677,000 microseconds (0.677000 seconds) to run.
      20,989 microseconds (0.020989 seconds, 3.10%) of which was spent in GC.
During that period, and with 8 available CPU cores,
     671,875 microseconds (0.671875 seconds) were spent in user mode
           0 microseconds (0.000000 seconds) were spent in system mode
 54,221,104 bytes of memory allocated.
(1864921261592819619661568919418981552559955289196969112566252282429216186594265918444566258544614425
 5891958562486995519825158818455999516899524658151445485616155916296966645869599949958954491929662561)

```

As a bonus, I'm including a version of the code that incrementally builds the solution top-down. It can manage a 1000-digit number in less than ten seconds, but cannot compete in golf due to the additional code.

```
(defun decompose (x)
  (flet ((s (z)
           (mapcan #'(lambda (c) (and #1=(position c #2=(format () "~a" z))
                                 (list (- (length #2#) #1# 1))))
                   '(#\0 #\3 #\7))))
    (do ((y x (let ((p (nconc (s y) (s #3=(logxor x y)))))
                (or p (return`(,y,#3#)))
                (+ y (expt 10 (apply #'max p))))))
        (nil))))

* (time (decompose (parse-integer (make-string 1000 :initial-element #\7))))
took 9,226,000 microseconds (9.226000 seconds) to run.
        90,966 microseconds (0.090966 seconds, 0.99%) of which was spent in GC.
During that period, and with 8 available CPU cores,
     9,234,375 microseconds (9.234375 seconds) were spent in user mode
             0 microseconds (0.000000 seconds) were spent in system mode
 487,434,560 bytes of memory allocated.
(8889898889152488921298888992819221914229899249999918899888899888888889999989141219898898888988988898888888888899142442899924898918898898988988895189988898888924192198992454114198911989191888889898888918888988988998888891421118891899122898888998989898888898988898888999988918888898889189918889888888899888989219188898998888988892119889198888988888894888912188898989952999888888888898899998988898889228918998949999998898898991141888898999988912121292118899889998989899999892889941898888911888898889118998898888911889889888891452888998889288921141888888942189888899988891918889118888888888989892198899199914111188988889421111188889118888918989988912989999998989891119888898888888892621229888988888999619888952462219889189899998899888889989898891118989218888888898962988891188899888888888999888888888888888888888891269188921288888888998898899214191188888888898992188998898889919888889989889899988892115549998888898889218899988998911898989199918898918988898888891889888989119899888889888998918889112189998
 4184469818464841952189561886965821566229261221619858498284264289194458622668559698924621446851546256444641488616184155821914881485164244662156846141894655485889656891849662551896595944656451462198891289692696856414192264846811616261884188919426294584158925218559295881946496911489245664261126565546419851585441144861859822815144162828551969425529258169849412525611662488849586554989254181228254465226521648916188265491499166186964881248156451994924294646681548996645996894665198811511522424996844864211629888924642289925565591484541149414914699289441561496451494562955652129199261462268846144518142486845251946444998812988291119592418684842524648484689261441456645518518812265495165189812912919529151991611962525419626921619824496626511954895189658691229655648659252448158451924925658586522262194585891859285841914968868466462442488528641466655911199816288496111884591648442984864269495264612518852292965985888414945855422266658614684922884216851481646226111486498155591649619266595911992489425412191)
* (apply #'logxor *)
7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777

```

# Answer
> 2 votes
# Python 2, 103 + 42 = 145 bytes

Python natively supports bigints, but this program far exceeds 20 seconds for a 100-digit number. However, it decomposes 64-bit integers in around 2 seconds.

```
from random import *
def d(a):
 b=c=0
 while set(`b`+`c`)&set('037'):
    b=randint(1,a);c=a^b
 return b,c

```

# Answer
> 1 votes
# Python 3 (132 bytes)

(This is just to stimulate better solutions. This is my solution when solving the original problem in ASCII movie.)

```
def d(a):
 l=len(str(a));s=int('1'*l);u=10**(l-1)
 while u:
  while set(str(s)+str((a^s)//u))&set('037'):s+=u
  u//=10
 print(s,a^s)

```

Although the behavior of bitwise xor in decimal system is pretty complicated, there is one major observation: *modifying the low digits will not affect the high digits*. Therefore, we can work top-down: try to make the top digits free of 0, 3, 7, and then work on the next digit, until the whole number is worked out. This allows us to run in linear time, then processing a thousand-digit number can complete under 1 second. (The Common Lisp solution is also using the same technique I believe.)

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


title: Group the Numbers With the Same Sum

text:
# Question
Title: Group the Numbers With the Same Sum
Your task is, given a square grid of digits (`0-9`), output one of the ways that the digits can be grouped such that:

1. Each digit is part of exactly one group
2. All groups have the same number of digits
3. All groups are bounded by one polygon-like shape (this means that every digit in the group is next to \[left, right, up, down\] at least one other digit of the same group, unless each group has 1 element).
4. All groups have the same sum

The input grid will always be a square: You may choose any input method you would like (including supplying arguments to a function or method). In addition, the input will supply the number of groups that your program should group the digits into.

Example input:

Suppose your input format is `stringOfDigits numberOfGroups`.

An example input would be:

```
156790809 3

```

which would translate to (a grid of `sqrt(9) * sqrt(9)`)

```
1 5 6
7 9 0
8 0 9

```

which you would have to divide into 3 groups, each of which should have `9 / 3 = 3` elements with the same sum.

Output: Output should be the string of digits, with optional spaces and newlines for formatting, with each digit followed by a letter `a-z` indicating its group. There should be exactly `numberOfTotalDigits / numberOfGroups` elements in each group. You will never have to divide something into more than 26 groups.

Example output:

```
1a 5a 6b
7c 9a 0b
8c 0c 9b

```

Note that replacing all `a`s with `b`s and `b`s with `a`s is equally valid. As long as each group is denoted by a distinct letter, the output is valid.

In addition, I expect most programs to output something along the lines of this, because newlines/spaces are optional:

```
1a5a6b7c9a0b8c0c9b

```

In this case, adding all digits of group `a`, `b`, or `c` makes 15. In addition, all groups are bound by some polygon.

Invalid outputs:

```
1a 5a 6b
7c 9a 0c
8c 0b 9b

```

because the groups do not form polygons (specifically, the `6b` is isolated and `0c` is also lonely).

```
1a 5a 6b
7c 9a 0b
8c 0b 9b

```

because the group `b` has 4 elements while `c` only has 2.

Etc.

If there is no valid solution, your program may do anything (i.e. stop, crash, run forever) but if your program prints `None` when there is no valid solution, `-15` to your score.

If there is more than one solution, you only have to print one, but `-20` if your program prints all of them separated by some delimiter.

This is code golf, so shortest code (with bonuses) wins!

# Answer
# Pyth, 122 - 20 - 15 = 87

```
=Z/lzQ=ks^lz.5Jm]dUzL[-bk+bk?tb%bkb?hb%hbkb)FNJIgNZB~Jm+NksmybN;|jbS{msm+@zk@S*Z<GQxsdkUzfqSsTUz^fqsmv@*ZzbY/smvdzQJQ"None

```

Changes:

* 130 -\> 120: Switched to newline separated input.
* 120 -\> 134: Fixed a bug involving groups not of size equal to the side length of the matrix.
* 134 -\> 120: Prints all solutions, including ones equivalent under group renaming.
* 120 -\> 122: Fixed a bug where only paths would be generated, instead of all legal groups.

Test run:

```
pyth programs/sum_group.pyth <<< '156790809
3'
1a5a6b7c9a0b8c0c9b
1a5a6c7b9a0c8b0b9c
1b5b6a7c9b0a8c0c9a
1b5b6c7a9b0c8a0a9c
1c5c6a7b9c0a8b0b9a
1c5c6b7a9c0b8a0a9b

pyth programs/sum_group.pyth <<< '156790808
3'
None

pyth programs/sum_group.pyth <<< '1111
2'
1a1a1b1b
1a1b1a1b
1b1a1b1a
1b1b1a1a

```

Explanation:

```
Pyth code           (Pseudo)-Python code              Comments

(implicit)          z = input()                       z is the digit string
(implicit)          Q = eval(input())                 S is the number of groups
(implicit)          G = 'abcdefghijklmnopqrstuvwxyz'
=Z/lzQ              Z = len(z)/Q                      Z is the size of each group.
=ks^lz.5            k = int(len(z) ** .5)             k is the side length of the matrix.
Jm]dUz              J = map(lambda d:[d], range(len(z))) Locations are encoded as numbers.
L                   def y(b): return                  y will be the transition function.
 [-bQ                         [b-k,                   Move up - the row above is k less.
  +bQ                          b+k,                   Move down - the row below is k more.
  ?tb%bkb                      b-1 if b%k else b      Move left, unless at the left edge.
  ?hb%hbkb)                    b+1 if (b+1)%k else b] Move right, unless at right edge.
FNJ                 for N in J:                       This constructs the list of all
   IgNZB                       if N[Z-1]: break       Z-length connected groups.
   ~Jm+Nk                      J+=map(lambda k: N+[k],  Append to J the group of N +
      smybN                          sum(map(lambda b:  anything reachable from
                                     y(b),N)))        anywhere in N.
   ;                (end for)
|                   or                                Print first truthy thing between
 S{                 sorted(set(                       Unique elements in sorted order of
   ms               map(lambda b:sum(                 Map+sum over allowable combinations
     m+@zd          map(lambda d:z[d]+                Character in original digit string
       @S*Z<GQ      sorted(G[:Q]*Z)[                  Repeated and sorted early alphabet
        xsbd        sum(b).index(d)],                 At index of number in sum of groups
      Uz                range(len(z)))                Over possible indexes.
   f                filter(lambda T:                  To generate allowable combinations,
                                                      we will filter all groups of Q paths.
    qSsTUz          sorted(sum(T)) == range(len(z))   Ensure all locations are visited.
    ^                                                 Combinations of
     f              filter(lambda Y:                  Filter over connected Z-length groups
      qsm           equal(sum(map(lambda k:           Sum of the values of the group
         v@*ZzkY    eval((z*Z)[k]),Y)                 In the original digit string
       /smvbzQ      sum(map(lambda b:eval(b),z))/Q    must equal the sum of all values in z
                                                      divided by the number of groups.
      J             J                                 Filter over connected Z-length groups
     Q              Q                                 Combinations of length Q
 "None              "None"                            If the above was empty, print "None"

```
> 10 votes

# Answer
# JavaScript (ES6) 361 (376-15) ~~372~~

(Maybe can still be golfed a little more)

As a function, first param is the string of digits and second param is the number of groups.
It's a naive recursive search, stopping at first solution found (no -20 bonus).
Need some more test cases to verify performance on some bigger input.

```
F=(g,n,l=g.length,i=w=Math.sqrt(l),o=s=h='',
  R=(g,p,k,j=l/n,t=s/n,v=0,h=String.fromCharCode(97+k))=>(
    t-=g[p],!(t<0)&&(
      g=[...g],g[p]=h,
      S=f=>g.some((c,p)=>c<':'&&f(p)),
      --j?S(p=>(g[p+1]==h|g[p-1]==h|g[p+w+1]==h|g[p-w-1]==h)?v=R(g,p,k,j,t):0)
      :t?0:k?S(p=>v=R(g,p,k-1)):v=g
    ),v
  )
)=>([for(c of g)(s-=-c,h+=--i?c:(i=w,c+':'))],h=R(g=h,-1,n,1))?h.map((c,p)=>o+=c!=':'?g[p]+c:'')&&o:'None'

```

**Ungolfed & Explained**

```
F=(g,n)=>
{
  var l = g.length, // string size, group size is l/n
      w = Math.sqrt(l), // width of grid
      s,i,h,o;

  // Build a new string in h, adding rows delimiters that will act as boundary markers
  // At the same time calculate the total sum of all digits
  h='',  // Init string
  s = 0, // Init sum
  i = w, // Init running counter for delimiters
  [for(c of g)(
    s -= -c, // compute sum using minus to avoid string concatenation
    h += --i ? c : (i=w, c+':') // add current char + delimiter when needed
  )];

  // Recursive search
  // Paramaters:
  // g : current grid array, during search used digits are replaced with group letters
  // p : current position
  // k : current group id (start at n, decreaseing)
  // j : current group size, start at l/n decreasing, at 0 goto next group id
  // t : current group sum value, start at s/n decreasing

  var R=(g,p,k,j,t)=>
  {
    var v = 0, // init value to return is 0
        h = String.fromCharCode(97+k); // group letter from group

    t-=g[p]; // subtract current digit

    if (t<0) // exceed the sum value, return 0 to stop search and backtrak
      return 0;

    g=[...g]; // build a new array from orginal parameter
    g[p] = h; // mark current position

    // Utility function  to scan grid array
    // call worker function  f only for digit elements
    //   skipping group markers, row delimieters and out of grid values (that are undefined)
    // Using .some will return ealry if f returns truthy
    var S=f=>g.some((c,p)=>c<':'&&f(p));

    if (--j) // decrement current group size, if 0 then group completed
    { // if not 0
      // Scan grid to find cells adiacent to current group and call R for each
      S( p => {
        if (g[p+1]==h|g[p-1]==h|g[p+w+1]==h|g[p-w-1]==h) // check if adiacent to a mark valued h
        {
          return v=R(g,p,k,j,t) // set v value and returns it
        }
      })
      // here v could be 0 or a full grid
    }
    else
    {
      // special case: at first call, t is be NaN because p -1 (outside the grid)
      // to start a full grid serach
      if (t) // check if current reached 0
        return 0; // if not, return 0 to stop search and backtrak

      if (k) // check if current group completed
      {
        // if not at last group, recursive call to R to check next group
        S( p => {
          // exec the call for each valid cell still in grid
          // params j and t start again at init values
          return v=R(g,p,k-1,l/n,s/n) // set value v and returns it
        })
        // here v could be 0 or a full grid
      }
      else
      {
        return g; // all groups checked, search OK, return grid with all groups marked
      }
    }
    return v
  };
  g = h; // set g = h, so g has the row boundaries and all the digits

  h=R(h,-1,n,1); // first call with position -1 to and group size 1 to start a full grid search

  if (h) // h is the grid with group marked if search ok, else h is 0
  {
    o = ''; // init output string
    // build output string merging the group marks in h and the original digits in g
    h.map( (c,p) => o += c>':' ? g[p]+c: '') // cut delimiter ':'
    return o;
  }
  return 'None';
}

```

**Test** In FireFox/FireBug console

`F("156790809",3)` output `1c5c6b7a9c0b8a0a9b`

`F("156790819",3)` output `None`
> 4 votes

---
Tags: code-golf
---


title: Michael Crichton's Mousetrap

text:
# Question
Title: Michael Crichton's Mousetrap
In 1984, Michael Crichton wrote a security program in BASIC that was published in Creative Computing magazine. The program would ask the user to type a phrase of their choice, record the intervals between the keystrokes, then ask them to retype the phrase. If the timings differed by too much, the program would identify the user as an imposter.

Your assignment: create a version of Crichton's program in the language of your choice.

Rules:

1. Phrases for communicating with the user ("Please type the key phrase," "Please type the key phrase again," etc.) count as one byte each regardless of actual length. This is for user communication only, do not try to hide program code in the strings.
2. The pass/fail test should be based on the average absolute value of the percentage variances from the original intervals. If the strings don't match, either return fail or allow the user to try again, at your discretion.
3. The key phrase should not allow a null string. In the event the key phrase is too long for your string datatype, either truncate or disallow and start over, at your discretion.
4. The sensitivity of the test (the threshold for the pass/fail test) should be adjustable in the source code.
5. I originally provided a bonus of 20% of total byte count if your source code can be formatted to recognizably resemble a dinosaur. It has been pointed out that this is highly subjective and perhaps more appropriate for a popularity contest, so I have removed this bonus. *However* I still heartily encourage dinosaur formatting, and if you format your code to look like a dinosaur, you can deduct any purely cosmetic comments, linebreak or whitespace characters from your byte total.
6. Shortest byte count wins, subject to string-length and dinosaur formatting adjustments.

Note that my specification above does not exactly match the operation of Crichton's code, copies of which may be found online. Follow the spec, don't try to clone the original.

# Answer
# Ruby, ~~171 167~~ 157 bytes

```
require'io/console';t=Time;f=->a{loop{x=t.now;STDIN.getch==?\r?break: a<<t.now-x};a};p"Please type the key phrase";f[r=[]];p"Please type the key phrase again";p r.zip(f[[]]).map{|x,y|(1-x/y).abs}.reduce(:+)/r.size>0.2

```

Outputs `true` if average variance is above 20%, otherwise outputs `false`.

Dinosaur ASCII art attempt:

```
(_=/\
  \ \
   \ \
    \ \              _...---..__
     \ \          .∕` #{t=Time} `\._
      \ \      .∕ #{z='io/console'} `\.
       \ \.__.∕  #{require z;s=STDIN} `\.
        \ #{p'1:';f=->a{loop{x=t.now;#   \.
         s.getch==?\r?break: a<<t.now-x;# `\.
          };a};f[r=[]];p'2:';p r.zip(f[[]])#\
           .map{|x,y|(1-x/y).abs}.reduce(:+)#|
            .fdiv(r.size)>0.2}###########\   \
            `-._    ,___...----...__,   ,__\  \
                |   |_|           |_|   |    \ \
                |___|               |___|      \\/)

```

Ungolfed:

```
require 'io/console' # so we can read one char at a time

t = Time

f = ->(a) {
  loop {
    x = t.now # record start time
    break if STDIN.getch == ?\r
    a << t.now - x # push (start time - end time) into array
  }
  a
}

puts "Please type the key phrase"
f[r = []]

puts "Please type the key phrase again"

# interweave timing arrays, compute variances, sum elements
# then divide by array length. Check to see if average
# is greater than threshold (0.2)
p r.zip(f[[]]).map { |x,y| (1-x/y).abs }.reduce(:+) / r.size > 0.2

```

`require 'io/console'` could be removed when run in some Ruby REPLs, as the library is already loaded.
> 9 votes

# Answer
# Java 768 bytes

*what? Java? for code golf?*

This is probably the worst thing to do, but I tried it anyway.

It displays any messages in the console window, but the actual typing occurs in the JTextField. Not exactly nice looking. Oh, and to save 5 bytes, you have to resize the JFrame yourself. Also, it doesn't check for string correctness the second time. Not sure if that is against the specs.

To Use:

Type your key in the textfield.

Don't press enter, go to the console and type something. It will display another message

Type the same thing in the textfield (which should now be cleared).

Go to the console and press something again. It will display whether you are an intruder or not.

ungolfed:

```
import java.util.*;
import javax.swing.*;
import javax.swing.event.*;

public class CrichtonsMousetrap {
    public static void main(String[]a){
        new CrichtonsMousetrap();
    }
    long start;
    List<Long>elapsed = new ArrayList<>();
    List<Long>e2;
    public CrichtonsMousetrap(){
        JFrame f = new JFrame();
        f.setSize(199,70);
        f.setVisible(true);
        JTextField t = new JTextField();
        System.out.println("please type in the key phrase.");
        f.add(t);
        t.getDocument().addDocumentListener(new DocumentListener(){
            @Override
            public void changedUpdate(DocumentEvent e) {}
            @Override
            public void insertUpdate(DocumentEvent e) {
                long r = System.nanoTime();
                if(start!=0){elapsed.add(r-start);}
                start=r;}
            @Override
            public void removeUpdate(DocumentEvent e) {}
        });
        Scanner s = new Scanner(System.in);
        s.next();
        System.out.println("please type that again!");
        e2=elapsed;
        elapsed=new ArrayList<>();
        start=0;
        t.setText("");
        s.next();
        double sum=0;
        for(int i=0;i<e2.size();i++){
            sum+=Math.abs(1-elapsed.get(i)/(double)e2.get(i));
        }
        System.out.println("your average percent error was " + sum/e2.size());
        double okLimit = .2;
        System.out.println(sum/e2.size() < okLimit ? "you're ok":"INTRUDER!");
    }
}

```

golfed:

```
import java.util.*;import javax.swing.*;import javax.swing.event.*;class q{static long p;static List<Long>y=new ArrayList<>(),o;public static void main(String[]a){JFrame f=new JFrame();f.setSize(0,0);f.setVisible(true);JTextField t=new JTextField();System.out.println("please type in the key phrase.");f.add(t);t.getDocument().addDocumentListener(new DocumentListener(){public void changedUpdate(DocumentEvent e){}public void insertUpdate(DocumentEvent e){long r=System.nanoTime();if(p!=0){y.add(r-p);}p=r;}public void removeUpdate(DocumentEvent e){}});Scanner s = new Scanner(System.in);s.next();System.out.println("please type that again!");o=y;y=new ArrayList<>();p=0;t.setText("");s.next();double b=0;for(int i=0;i<o.size();b+=Math.abs(1-y.get(i)/(double)o.get(i++)));System.out.print(b/o.size() < .25 ? "you're ok":"INTRUDER!");}}

```
> 4 votes

# Answer
# C, 154 (86+68 for flags)

```
d[99],i,a,b;main(x,y){P"Please type the key phrase"W(E-13)U,x=y;U;P"Please type
the key phrase again"W(a<i)E,b+=abs(Y-Z)*99/Z,++a,x=y;b<a*9||P"No cake for imposters");}

```

Compile with `-DY=(y=clock())-x`, `-DZ=a[d]`, `-DE=getch()`, `-DW=);while`, `-DU=i++[d]=Y` and `-DP=puts(`. Newlines added for presentation purposes and may be removed (byte count given is without).

Ungolfed+comments:

```
d[99],i,a,b;
main(x,y,z){
    puts("Please type the key phrase");
    do
        z = getch(),
        i++[d] = (y = clock()) - x, // save amount of time from last key. first value is garbage.
        x = y;
    while((z = getch())-13); // read until carriage return.
    for(;a < i && getch(); ++a) // don't check for validity, just get a char
        b += abs((y = clock())- x - d[a])*99/d[a], // (y=clock())-x is time from last key.
                                                     // subtract from original time, *99, divide by new
                                                     // then get sum of these
        x = y;
    b < i*9  // check that the average difference is less than 9/99
    || puts("No cake for imposters"); // identify as imposter if greater/equal
    // don't output anything if not an imposter
}

```

This does not check that the retyped phrase is identical, nor does it output anything if the user is not identified as an imposter.

This also does not consider the time taken after prompting before the first keystroke.
> 3 votes

# Answer
# HTML, JavaScript (ES6), 328

Total bytes count of the code is 402 bytes and the messages to interact with the user:

```
"Valid User"
"Imposter alert!!"
"Please Enter the Key again"
Please Enter the Key

```

are total 78 bytes, so total score =\> 402 - 78 + 4 = 328

Run the snippet below in a **latest Firefox** and type the key in the input box followed by Enter key.

The code checks that both the entered and re-entered keys are same, (prompts for re-entering again if not), calculates the average absolute difference percentage and checks if it is less than the the value of the variable `V`

```
<a id=t >Please Enter the Key</a><input id=f /><script>V=.3,a=[],i=0,s=b="",q=0
c=_=>(j=0,_.slice(1).map(v=>j+=Math.abs(v)/i),alert(j<V?"Valid User":"Imposter alert!!"))
r=_=>(a=[],i=0,t.textContent="Please Enter the Key again",f.value="")
f.onkeyup=_=>_.keyCode==13?q++?s==f.value?(A=a,B=b,A=a.map((v,i)=>v-A[i-1]),c(b.map((v,i)=>(v-B[i-1]-A[i])/A[i]))):r():r(b=a,s=f.value):a[i++]=Date.now()</script>
```
> 3 votes

# Answer
## Scala REPL 233

```
def l:Stream[(Int,Long)]=(Console.in.read,System.nanoTime)#::l
def m={
    println("Enter");
    l.takeWhile(_._1!=13).map(_._2).toList.sliding(2).map(a=>a(1)-a(0))
}
val k=m.zip(m)
k.map(a=>Math.abs(a._2-a._1)/(a._1.toDouble*k.length)).sum<0.2

```

With all the spacing removed, you have:

```
def l:Stream[(Int,Long)]=(Console.in.read,System.nanoTime)#::l;def m={println("Enter");l.takeWhile(_._1!=13).map(_._2).toList.sliding(2).map(a=>a(1)-a(0))};val k=m.zip(m);k.map(a=>Math.abs(a._2-a._1)/(a._1.toDouble*k.length)).sum<0.2

```

Which I'm sure somebody more talented than I am could make into a dinosaur!

Brief explanation:

The `l` method read characters and keeps tract of the `nanoTime` of when each character was typed.

The `m` method prints `"Enter"`, breaks the `l` method upon hitting enter (character 13), then maps it to just the `nanoTimes`, and then gets the time intervals between each character.

The next 2 lines reads in 2 strings, zips them, then finds the average absolute value of the percentage difference between the second intervals and the first, and finally prints whether or not this average was less than `0.2`.
> 2 votes

# Answer
# Common Lisp : 660

```
(ql:quickload'(cl-charms alexandria))(defun m(&key(ok 0.2))(labels((^(s)(fresh-line)(princ s)(return-from m))(d(a b)(abs(/ (- b a) b)))($(x)(princ x)(force-output))(?(m)(charms:with-curses()($ m)(clear-input)(charms:enable-raw-input)(loop for c = (read-char)for n = (get-internal-real-time)for x = nil then (/(- n b)internal-time-units-per-second)for b = n when (eql c #\Esc)do (^"QUIT")when x collect x into % until (eql c #\Newline) collect c into ! finally(progn(terpri)(return(cons(coerce !'string)%)))))))(let*((ip(?"INIT PASSWORD: "))(ps(car ip))(sp(if(equal""ps)(^"NO EMPTY PASSWORD ALLOWED")(?"ENTER PASSWORD: ")))(r(if(equal ps(car sp))(alexandria:mean(mapcar #'d(cdr sp)(cdr ip)))(^"YOU DIDN'T SAY THE MAGIC WORD!"))))(if(> r ok)($"YOU ARE A FAKE!")($"IDENTITY CONFIRMED")))))(m)

```

# Ungolfed

```
(ql:quickload'(cl-charms alexandria))
(defun m(&key(ok 0.2))
  (labels
      ((^(s)(fresh-line)(princ s)(return-from m))
       (d(a b)(abs(/ (- b a) b)))
       ($(x)(princ x)(force-output))
       (?(m)(charms:with-curses()
              (clear-input)
              ($ m)
              (charms:enable-raw-input)
              (loop for c = (read-char)
                    for n = (get-internal-real-time)
                    for x = nil then (/ (- n b)
                                        internal-time-units-per-second)
                    for b = n
                    when (eql c #\Esc)
                      do (^"QUIT")
                    when x
                      collect x into %
                    until (eql c #\Newline)
                    collect c into !
                    finally (progn
                              (terpri)
                              (return
                                (cons (coerce !'string) %)))))))
    (let* ((ip (?"INIT PASSWORD: "))
           (ps (car ip))
           (sp (if (equal "" ps)
                 (^"NO EMPTY PASSWORD ALLOWED")
                 (?"ENTER PASSWORD: ")))
           (r (if (equal ps (car sp))
                (alexandria:mean(mapcar #'d(cdr sp)(cdr ip)))
                (^"YOU DIDN'T SAY THE MAGIC WORD!"))))
      (if (> r ok)
        ($"YOU ARE A FAKE!")
        ($"IDENTITY CONFIRMED")))))

(m) ;; call function

```

# Additional remarks

* Complies with all rules
* When user first gives an empty password, the program aborts cleanly
* When typing `Escape`, the program aborts cleanly.
* Tested on recent SBCL and CCL implementations
* Requires cl-charms, which is a wrapper around Ncurses. This is the easiest way to capture raw input.
* This is inspired by (but not copied from) the original version found by squeamish-ossifrage

# Dinosaur bonus

I should have a bonus because everybody knows that "Common Lisp is a moribund dinosaur".
> 1 votes

---
Tags: code-golf
---


title: Predict the Falling Rocks

text:
# Question
Title: Predict the Falling Rocks
In this challenge, you are given a map of a two-dimensional terrain, viewed from the side. Unfortunately, some parts of the terrain are floating in the air, which means they'll come crashing down. Your job is to predict where they land.

# The Input

Your input is one or more newline-separated strings of equal lengths, containing only the characters `#` (a number sign, signifying a rock) or `.` (a period, signifying empty space).

# The Output

Your output has the same format as the input, but with the following modification. Let us view the input string as a two-dimensional grid of rocks. Every rock in the input which is connected to the bottom of the grid by a path of adjacent rocks is *firm*; other rocks are *loose*. Diagonally adjacent rocks are not considered to be adjacent. All the loose rocks will fall straight down, and end up as a stack on top of either a firm rock or the bottom row. The loose rocks are not attached to each other, so they fall individually, not as big formations. The output is the resulting grid.

# Examples

* The input

```
..###.
.##.#.
.#....
.##.#.

```

contains no loose rocks, so the output is identical to it.
* The input

```
...#..
.#..#.
.#..##
.#...#
.#####
.#...#

```

contains one loose rock at the top, which falls down on the firm rock under it. The output is

```
......
.#..#.
.#..##
.#.#.#
.#####
.#...#

```
* The input

```
.#####....
.#....####
###.###..#
#.#...##..
.####..#.#
......###.
..#...#..#
..#...#..#

```

has a large group of loose rocks on the left. The group breaks down as the rocks fall, so the output is

```
..........
....######
..#.###..#
. #...##..
.##....#..
.##...####
####..#..#
#####.#..#

```

# Clarifications

* You can either take the input from STDIN and output to STDOUT, or write a function.
* This is code-golf, so shortest program (in bytes) is the winner.
* Standard loopholes are disallowed.

# Answer
> 12 votes
# CJam, ~~180 ... 133 101 ... 94 90~~ 87 bytes

```
qN/~'#/S*_,):L;]N*_,_,*{:A1$='#={[W1LL~)]Af+{W>},1$f=S&,{ASct}*}*}/N/z{S/{$W%}%'#*}%zN*

```

~~There is definitely lots of golfing possible, but I wanted to post it first after getting it to work completely.~~

> Look ma! No scrollbars!

Takes the rocks grid (made up of `.` and `#` without a trailing newline) from STDIN and prints the output to STDOUT

*UPDATE* : Using an inefficient but shorter partial flood fill to figure out firm rocks.

*UPDATE 2*: Changed the algorithm for making the rocks fall down. Much shorter now!

*UPDATE 3*: Did several small optimizations and in the end I was able to bring down the byte count to half of the original code!

**How it works**:

```
qN/~'#/S*_,):L;]N*             "Preparations";
qN/~                           "Read the input, split by new line and expand the array";
    '#/S*                      "In the last row, replace # by space";
         _,):L                 "Copy the last row and store length + 1 in L";
              ;]N*             "Pop the length, wrap everything in array and join by \n";

_,_,*{ ... }/                  "Flood fill";
_,                             "Copy the array and calculate its length";
  _,                           "Copy the length and calculate [0 - length] array";
    *                          "Repeat the above array, length times";
     { ... }/                  "Run the code block on each element of the array";

:A1$='#={ ... }*               "Process only #";
:A1$                           "Store the number in A and copy the input array to stack";
    =                          "Get Ath index element from input array";
     '#={ ... }*               "Run the code block if Ath element equals #";

[W1LL~)]Af+{W>},1$f=S&,{ASct}* "Flood fill spaces";
[W1LL~)]Af+                    "Get the indexes of the 4 elements on the cross formed by"
                               "the Ath index";
           {W>},               "Filter out the negative values";
                1$f=           "For each of the index, get the char from input string";
                    S&,        "Check if space is one of the 4 chars from above step";
                       {    }* "Run the code block if space is present";
                        ASct   "Make the Ath character of input string as space";

N/z{S/{$W%}%'#*}%zN*           "Let the rocks fall";
N/z                            "Split the resultant string by newlines and"
                               "transpose the matrix";
   {           }%              "Run the code block for each row (column of original)";
    S/{   }%                   "Split by space and run the code block for each part";
       $W%                     "Sort and reverse. This makes # come down and . to go up";
            '#*                "Join by 3, effectively replacing back spaces with #";
                 zN*           "Transpose to get back final matrix and join by newline";

```

For the floodfill, we iterate through the whole grid length(grid) times. In each iteration, we are guaranteed to convert at least 1 `#` which is directly touching a space to  (space). Space here represents a firm rock group. Thus at the end of length(grid) iterations, we are guaranteed to have all firm rocks represented by spaces.

Try it online here

# Answer
> 15 votes
# Perl 5: 98

98 including 2 command line flags.

```
#!perl -p0
1while/
/,($x="($`)")=~y!#!.!,s/#(.*
$)/%$1/+s/#$x?%|%$x?#/%$1$2%/s;1while s/#$x\./.$1#/s;y!%!#!

```

Explanation:

```
#!perl -p0 #read entire input to $_ and print at the end
/\n/;($x="($`)")=~y!#!.!; #calculate pattern matching space
                          #between two characters in the same column
                          #looks like "(......)"
1 while s/#(.*\n$)/%$1/+s/#$x?%|%$x?#/%$1$2%/s;
                          #flood fill solid rock with %
1 while s/#$x\./.$1#/s;   #drop loose rock
y!%!#!                    #change % back to #

```

# Answer
> 5 votes
# JavaScript (ES6) 232

```
s=>{for(s=[...s+'1'.repeat(r=1+s.search('\n'))];s=s.map((c,p)=>c=='#'&(s[p+1]|s[p-1]|s[p-r]|s[p+r])?f=1:c,f=0),f;);for(;s.map((c,p)=>c=='#'&s[p+r]=='.'&&(s[p]='.',f=s[p+r]=c),f=0),f;);return s.join('').replace(/1/g,rok).slice(0,-r)}

```

As a function with a string parameter and returning a string.

At first, add a bottom row of '1' to identify the ground line.
The first loop search for the fixed rocks (that are near a '1') and marks them as '1' as well.The search is repeated until no more firm rocks are found.
The second loop move the remaining '#' characters towards the bottom row. Again, this is repeated until no rock can be moved.
At last, replace the '1' with '#' again and cut the bottom row.

*Less golfed*

```
s=>{
  r = 1+s.search('\n');
  s = [...s+'1'.repeat(r)];
  for (; s = s.map((c,p) => c=='#' & (s[p+1]|s[p-1]|s[p-r]|s[p+r])?f=1:c,f=0),f; );
  for (; s.map((c,p) => c=='#' & s[p+r]=='.'&& (s[p] ='.', s[p+r]=c, f=1),f=0),f; );
  return s.join('')
    .replace(/1/g,'#')
    .slice(0,-r)
}

```

**Test** (You can have evidence of what rocks are firm and what have fallen)

```
F=
s=>{for(s=[...s+'1'.repeat(r=1+s.search('\n'))];s=s.map((c,p)=>c=='#'&(s[p+1]|s[p-1]|s[p-r]|s[p+r])?f=1:c,f=0),f;);for(;s.map((c,p)=>c=='#'&s[p+r]=='.'&&(s[p]='.',f=s[p+r]=c),f=0),f;);return s.join('').replace(/1/g,rok).slice(0,-r)}

var rok // using rok that is 3 chars like '#'

function update() {
  rok = C.checked ? '@' : '#';
  O.textContent=F(I.textContent)
}

update()
```

```
td { padding: 5px }
pre { border: 1px solid #000; margin:0 }
```

```
<table><tr><td>Input</td><td>Output</td></tr>
<tr><td><pre id=I>.#####....
.#....####
###.###..#
#.#...##..
.####..#.#
......###.
..#...#..#
..#...#..#</pre></td>
<td><pre id=O></pre>
</td></tr></table>
<input type='checkbox' id=C oninput='update()'>Show firm rocks
```

# Answer
> 3 votes
## APL, ~~130~~ 119

```
'.##'[1+⊖1↓⍉↑↑{,/{⍵[⍒⍵]}¨x⊂⍨2=x←2,⍵}¨↓ ⍉⊃⌈/(1,¨⍳⍴⊃↓x){x←⍵⋄(⍺⌷x)∧←2⋄x≡⍵:x⋄⊃⌈/((⊂⍴⍵)⌊¨1⌈(,∘-⍨↓∘.=⍨⍳2)+⊂⍺)∇¨⊂x}¨⊂⊖'#'=x←⎕]

```

Since it is not possible (as far as I know) to enter newlines when input is prompted, this program takes a character matrix as input.

The algorithm used is first converting to a binary matrix (`0` is air and `1` is rock) then flood filling from the bottom row to mark firm rocks as `2`. Then partition each column into "spaces between firm rocks" and sort each partition to make the loose rock "fall through" the air.

Edit1: Golfed some using a different flood fill algorithm

---

## Test runs

**Run 1**

Define a character matrix `A` and prints it:

```
      A←↑('.#####....') ('.#....####') ('###.###..#') ('#.#...##..') ('.####..#.#') ('......###.') ('..#...#..#') ('..#...#..#')
      A
.#####....
.#....####
###.###..#
#.#...##..
.####..#.#
......###.
..#...#..#
..#...#..#

```

Then feed `A` into the program:

```
      '.##'[1+⊖1↓⍉↑↑{,/{⍵[⍒⍵]}¨x⊂⍨2=x←2,⍵}¨↓⍉(1,¨⍳⊃⌽⍴x){⍵≡y←⊃⌈/x←⍺{x←⍵⋄(⍺⌷x)∧←2⋄x}¨⊂⍵:y⋄((⊂⍴⍵)⌊¨1⌈,(,∘-⍨↓∘.=⍨⍳2)∘.+⍺/⍨x≢¨⊂⍵)∇y}⊖'#'=x←⎕]
⎕:
      A
..........
....######
..#.###..#
..#...##..
.##....#..
.##...####
####..#..#
#####.#..#

```

**Run 2**

```
      A←↑('#######')('#.....#')('#.#.#.#')('#.....#')('#######')
      A
#######
#.....#
#.#.#.#
#.....#
#######
      '.##'[1+⊖1↓⍉↑↑{,/{⍵[⍒⍵]}¨x⊂⍨2=x←2,⍵}¨↓⍉(1,¨⍳⊃⌽⍴x){⍵≡y←⊃⌈/x←⍺{x←⍵⋄(⍺⌷x)∧←2⋄x}¨⊂⍵:y⋄((⊂⍴⍵)⌊¨1⌈,(,∘-⍨↓∘.=⍨⍳2)∘.+⍺/⍨x≢¨⊂⍵)∇y}⊖'#'=x←⎕]
⎕:
      A
#######
#.....#
#.....#
#.#.#.#
#######

```

# Answer
> 2 votes
# JS - 443 bytes

```
function g(b){function f(b,c,e){return b.substr(0,c)+e+b.substr(c+1)}function e(d,c){"#"==b[c][d]&&(b[c]=f(b[c],d,"F"),1<d&&e(d-1,c),d<w-1&&e(d+1,c),1<c&&e(d,c-1),c<h-1&&e(d,c+1))}b=b.split("\n");w=b[0].length;h=b.length;for(i=0;i<w;i++)"#"==b[h-1][i]&&e(i,h-1);for(j=h-2;-1<j;j--)for(i=0;i<w;i++)if(k=j+1,"#"==b[j][i]){for(;k<h&&"F"!=b[k][i]&&"#"!=b[k][i];)k++;k--;b[j]=f(b[j],i,".");b[k]=f(b[k],i,"#")}return b.join("\n").replace(/F/g,"#")};

```

Flood fills rocks from the bottom, then brings un-flood-filled rocks down. Uses a lot of recursion with the flood fill so it may lag your browser for a bit.

It's a function - call it with `g("input")`

JSFiddle: http://jsfiddle.net/mh66xge6/1/

Ungolfed JSFiddle: http://jsfiddle.net/mh66xge6/

# Answer
> 1 votes
# Python 3, 364 bytes

I'm sure more could be squeezed out of this... but it's never going to compete with CJam and Perl anyway.

```
z="%";R=range
def F(r,c,g):
 if z>g[r][c]:g[r][c]=z;[F(r+d%2*(d-2),c+(d%2-1)*(d-1),g)for d in R(4)]
def P(s):
 t=s.split()[::-1];w=len(t[0]);g=[list(r+".")for r in t+["."*w]];[F(0,c,g)for c in R(w)]
 for c in R(w):
  for r in R(len(g)):
   while g[r][c]<z<g[r-1][c]and r:g[r][c],g[r-1][c]=".#";r-=1
 return"\n".join(''.join(r[:w])for r in g[-2::-1]).replace(z,"#")

```

Similar to other answers. One quirk is that it turns the grid upside down first (to make the loop indices more convenient) and adds an extra row & column of `.` (to avoid problems with wrapping `-1` indices). Run by calling `P(string)`.

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


title: Let's Judge Some Books By Their Covers

text:
# Question
Title: Let's Judge Some Books By Their Covers
Everyone knows that the content makes the question. But a good title helps too, and that's the first thing we see. It's time to turn that first impression into a program, and figure out what kinds of titles get more upvotes.

You are hereby challenged to write a program or function that takes the title of a PPCG question as input, and returns a prediction of its score.

For instance, you might receive `Counting Grains of Rice` as an input, and you would be trying to return something close to the score, `59` in this case. Non-integer guesses are fine, but guesses at or below `-20` are not.

Here is the data, for testing and scoring:

http://data.stackexchange.com/codegolf/query/244871/names-and-upvotes

**Scoring:** Your program will be run on every question in this site's (PPCG) history, not counting closed questions. The function `ln(score + 20)` will then be applied to each score, and to each guess. The root-mean-squared-error between the two resultant sets of values is your score. Lower is better.

For instance, a program that guessed 0 every time would score 0.577, while one that guessed 11 every time would score 0.362.

Please calculate your score and include it in the title of your answer. Please also include your program's prediction for how many upvotes this question will get.

**Restrictions:**

* To prevent excessive hard-coding, no more than 1000 characters.
* Must run on the entire data set above in under a minute on a reasonable machine.
* Standard Loopholes are closed.

---

Here is a tester written in Python, for your use and/or to clear up ambiguities:

```
import sys
import math
import csv

scores_dict = {}

with open(sys.argv[1], 'r') as csv_file:
    score_reader = csv.reader(csv_file)
    for score, title in score_reader:
        if score == 'Score':
            continue
        scores_dict[title] = int(score)

def rate_guesses(guesser):
    def transform(score):
        return math.log(score + 20) if score > -20 else 0
    off_by_total = 0
    lines_count = 0
    for title in scores_dict:
        guessed_score = guesser(title)
        real_score = scores_dict[title]
        off_by_total += (transform(real_score) - transform(guessed_score)) ** 2
    return (off_by_total/len(scores_dict)) ** .5

def constant11(title):
    return 11

print(rate_guesses(constant11))

```

# Answer
> 9 votes
# Python 2, 991 chars, score 0.221854834221, predict 11

```
import base64
e={}
d=base64.decodestring('vgAcRAEVDAIsqgQYalYaggcjQKwVXAoZWAsYQg0Ckg4VlWEX9hEDRhMe0hckCBkeuhsW3CAWQiEm\nSiMZMiwgTDAZZjIcSLMZfDQDnjwCe2AVaEQCYWEBIEgnDEoXzk0e3lQb5FYVKlkVZlwB+F0XwmI/\nGmRcuGUXWmYdVGkbzmwafG8eaHMdInkggHonRn5sKoMXgIkpbowVOI4cNJAubpQdYpcydJgVypkA\nZpweMp8ZsqEcRKMghKQYkKVPPXEWMqkWHKwbjrEdzLIBNLMf1LQivrYC99UV9rxNRsABNMEiPzob\npc0ActAhn3gcrNUZYNcWYNov/t8VgOEXAuMYqOUWsqUiCPIefPWNbvtKevwWvP0Cl9UsjQMdWwQb\nfQdpJQgWYwkCZRLBjxMWWdkqHRkWNxwB6x8p2SEZyyICSyYcgysaOS0CUy8hezAaGeEVpTRQ3zUz\nZzkZRzohizwwST4c8UAdF0OqG9AXIuEYYRN6208nU1AktVEVJ1IVWeMkIVQXdY4D2VYYD/cYb1om\nG1xA0zoY3uUaRWAhWpBSHWUXQTxGe+cad20CO3AZX3EBw3IiMXcef3gecXsVGXwhw30VbX4W24BD\n6qyQ45YaYYgZ4YobbYwauY4bMY82HZEdO5YmQ5cV35sVxaMbY6gYNas576ws+bADO7QpN7hdLJ8B\n4Eoks8EYX8VU68cYWfcar82QOdAaxdEfQ9UiW/kXL9k2ddwCW90m694enqUCkeEBE+IYWvsfA1FC\nJ+spMVIjhe4WEP0fAfYax/c3MfgbgfkqP/0DLf4V\n')
for i in range(0,600,3):
 e[ord(d[i])*256+ord(d[i+1])]=ord(d[i+2])*2-8
def p(t):
 return e.get(hash(t)%256**2,11)

```

# Explanation:

This is shameless hardcoding, but trying to do it efficiently.

## Preprocessing:

In a separate code, I hashed each title to a value between 0 and 256^2-1. Let's call these values bins. For each bin, I calculated the average score. (Average is needed because for a tiny fraction of the bins, there are collisions - more than 1 title hashes to the same bin. But for the vast majority each title maps to a bin of its own).

The idea behind the 2-byte code for each title is that 1 byte is not enough - we get too many collisions, so we don't really know what score to assign to each 1-byte bin. But with 2-byte bins, there are almost no collisions, and we effectively get a 2 byte representation of each title.

Then **rank** the bins - compute the gain in score if we assign this bin its computed value, instead of just guessing 11. Take the top N bins, and code them into a string (which is d in the actual code).

The encoding: the key of the bin is coded as 2 bytes. the value is encoded using 1 byte. I found values between -8 and 300+something, so had to squeeze a bit to get it into 1 byte: x -\> (x+8)/2.

## Actual code:

read d as byte triplets, decoding the encoding explained above. When a title is given, compute its hash (modulo 256^2), and if that key is found in the dict, return the value it maps to. Otherwise, return 11.

# Answer
> 15 votes
# Javascript ES6

## Score: 0.245663
Length: 1000 bytes
Predicts: 5

(I guess the question is due for an unexpected avalanche of downvotes. :P)

### Minified

```
E="ABCDEFGHIJKLMNOPQRSTUVWXYZ";E=E+E.toLowerCase()+"0123456789!@#$%;*()";P="RCRHIFMGPGIDQKHMJLLRMLFJGKHEqHPOgJNKGPCHPJNUPOSGJQKKKMELMIJHLKIKNcKDOfSJLFHDILGKIOUKLMLLKMKIHGHJGIIJDGJKIHIIFIGMTIHFJMIKDJGQJKGMKJHPRJPLMGIOPIIIIPBYFMGLEIKIMMRUKFLFGJFKFTHPFODEQTGTHKIJDHNJGDGiHKNYLHHDLJHGILOEViKNEKGQZfHJMIISIJFRHKLJMLPIFJILKKKJKKJESHNLLIKIGKGJJJHKJRGULLSLRONJNEeLKIQGGPQIHPLEIHHIDXjQHNBKOGWWIENRbYoHINHNMKTNKHTGMIPXFJLLMLIHPPLDJJKFUMIQMOKJLJJKIJKNLHRILJIAIbJEZOGIELGHGLOINDPJMJeJWRIIJHSOZDOsOFRRIOIOTIJSGGJKFUIDOINGOcLQEJFEITLMNIIGIGIMG7LPSNLKVOKIFGHJITGOFUJIIRN";K={};"99r1501vz076mip077myv0733it280exx081gt9118i1g279dyx102uho203ejd07433z087uje097kdg1567ft2088rk275dmu1203ez106lih1763ei126f6q101aax084owh088aid161i9y179gvn236ptn3338vf132i55080fke101l4z3789ai281ulm081blm124euz074o5m07513z14117l095qdn092gl30757n5153".replace(/(...)(...)/g,(_,a,b)=>K[a]=1*b);D=40655;N=479;H=(s,T)=>(h=7,[...s].map(c=>h=~~(h*T+c.charCodeAt(0))),h);S=s=>(y=H(s,31),K[((y%D+D)%D).toString(36)]||E.indexOf(P[(H(s,48)%N+N)%N]));

```

### Expanded

```
E = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
E = E + E.toLowerCase() + "0123456789!@#$%;*()";
K = {};
P = "RCRHIFMGPGIDQKHMJLLRMLFJGKHEqHPOgJNKGPCHPJNUPOSGJQKKKMELMIJHLKIKNcKDOfSJL" +
    "FHDILGKIOUKLMLLKMKIHGHJGIIJDGJKIHIIFIGMTIHFJMIKDJGQJKGMKJHPRJPLMGIOPIIIIP" +
    "BYFMGLEIKIMMRUKFLFGJFKFTHPFODEQTGTHKIJDHNJGDGiHKNYLHHDLJHGILOEViKNEKGQZfH" +
    "JMIISIJFRHKLJMLPIFJILKKKJKKJESHNLLIKIGKGJJJHKJRGULLSLRONJNEeLKIQGGPQIHPLE" +
    "IHHIDXjQHNBKOGWWIENRbYoHINHNMKTNKHTGMIPXFJLLMLIHPPLDJJKFUMIQMOKJLJJKIJKNL" +
    "HRILJIAIbJEZOGIELGHGLOINDPJMJeJWRIIJHSOZDOsOFRRIOIOTIJSGGJKFUIDOINGOcLQEJ" +
    "FEITLMNIIGIGIMG7LPSNLKVOKIFGHJITGOFUJIIRN";

   ("99r1501vz076mip077myv0733it280exx081gt9118i1g279dyx102uho203ejd07433z087u" +
    "je097kdg1567ft2088rk275dmu1203ez106lih1763ei126f6q101aax084owh088aid161i9" +
    "y179gvn236ptn3338vf132i55080fke101l4z3789ai281ulm081blm124euz074o5m07513z" +
    "14117l095qdn092gl30757n5153").
        replace( /(...)(...)/g, (_,a,b) => K[a] = 1*b );

D = 40655;
N = 479;
H = (s,T) => (
    h = 7,
    [...s].map( c => h = ~~(h*T + c.charCodeAt(0)) ),
    h
);

S = s => (
    y = H( s, 31 ),
    K[((y%D + D)%D).toString( 36 )] || E.indexOf( P[(H( s, 48 )%N + N)%N] )
);

```

The function `S` accepts a string (title) and returns its score.

Notes on Behaviour:

* ≤ 70 vote titles are handled separately from \> 70 vote titles
* ≤ 70 vote titles are sorted into bins using a highly sophisticated holonomic keyword tracking potential optimization algorithm that in no way resembles a string hash function
* after a bit of happy calculus it turns out that the optimal guess for each bin is simply the geometric average of the (votes + 20)'s for all titles in the bin, minus 20
* the optimal guesses for all 479 bins are then encoded as a 479-character base-70 string
* for \> 70 vote titles, the titles are assigned unique 3-digit base-36 codes generated using a state-of-the-art hashing technique that guarantees no collisions with other \> 70 vote titles and no false detections of ≤ 70 vote titles. This state-of-the-art technique in no way resembles trying random bin counts until one produces no collisions.
* the \> 70 vote title codes and their vote counts are encoded in a string (6 bytes per title), which is converted to a simple lookup table. The routine therefore has zero error for all \> 70 vote titles.

# Answer
> 10 votes
## Python 2, Score = 0.335027, 999 chars, Predict 11.34828 for this question

Just to get the ball rolling. This is nowhere optimal.

The fancy SVM thing is just my random idea and I felt like implementing it, so here it is. It does improve the baseline by 0.02 points, so I'm happy enough with that. But to show that hard-coding the input is where the majority of the improvement comes from, I'm hard coding some answer also.

Without the hard-coding the score is 0.360 (and actually all the predictions are around 11, haha)

I'm using scikit-learn and nltk

```
import sys
import math
import csv
from sklearn.feature_extraction.text import TfidfVectorizer as TV
from sklearn.svm import SVR
from nltk.stem.porter import PorterStemmer as PS
sd = {}
lr = None
tv = None
with open(sys.argv[1], 'r') as cf:
    sr = csv.reader(cf)
    for sc, t in sr:
        if sc == 'Score':
            continue
        sd[t] = int(sc)
ts,scs = zip(*sd.items())
s = PS()
def analyzer(st):
    r = []
    for word in st.split():
        if word.isdigit():
            r.append('<NUM>')
        elif not word.isalnum():
            r.append('<PUNCT>')
        else:
            r.append(s.stem(word.lower()))
    return r
tv = TV(min_df=25, stop_words='english', analyzer=analyzer)
ti = tv.fit_transform(ts)
lr = SVR()
lr.fit(ti, scs)
d={'4 w':378,'y 42':333,'eeta':280,'an Got':279,'s 2 ':275,"e I'":208,'r CP':203,'? No':179,'B.O':156}
def c(t):
    for s in d.keys():
        if s in t:
            return d[s]
    t = tv.transform([t])
    r = lr.predict(t)[0]+1.5
    return r

```

# Answer
> 4 votes
# Python 2, 986 chars, score 0.3480188, predict 12

```
M,S=14.29,23.02
D=lambda x:[ord(y)-32 for y in x]
w='fiLoNoNuMiNoTiMoShOnLoGoLeThRantexgensuBaSqUnInPeReGaMuLinprOuThInThEvEnClOpExPyThADdiSoLiSiMaTrEqUsImAsCoManstARrePoWoReawhapoLandradeTyPaLOsoReCreprediVeReSpebeTiPrImPladaTrihelmakwhicolpaReValpaTrafoROsoumovfinfunpuzyoufaSeQuiwhecoDeChagivcouchehanpoStrdiGraconjavwricalfrowitbinbrafrabuipoi'
for i in range(26):w=w.replace(chr(65+i),chr(97+i)*2)
w=[w[i:i+3]for i in range(0,372,3)]
m=D("(+),+)+=*...+..++'(*)5)/2)*43++16+0,+33*4*/(0.'+>-)+13+(2?8+6;,3;43+4(+.('(,.*.*+56+6)0((++(B,))+E0,-7/)/*++),+***)2+(3(.*)'")
s=D("))'B)'*j+:51(*3+0')+)^'/<-+MG,-1=),-0:A+T&J&K1%,O*()4Y-%:_A.=A*C]MJ-N%)5(%%-0+).*3Q(M&0'%(+$p*)()a8:-T?%5(-*'/.'+)+@,'J&1'&&")
def G(x,m,s):s=s or 1e-9;return(.4/s)*(2.78**(-(x-m)**2./(2*s*s)))
d={w[i]:(m[i],s[i])for i in range(124)}
def Z(t,c):
 p=1
 for W in t.split():
  if len(W)>3:
   W=W[:3].lower()
   if W in d:p*=G(c,*d[W])
 return p*G(c,M,S)
def J(t):return max([(Z(t,r),r)for r in range(-9,99)])[1]

```

The relevant function is `J`.

The program is essentially Naive Bayes using title words as features, but it's extremely restricted thanks to the char limit. How restricted? Well...

* For each title we convert to lower case and only look at words at least 4 letters long. Then we take the **first three letters** of each of those words as features. We skip stripping punctuation to save on chars.
* We choose only letter triplets which are at the start of **at least 19** words (these are stored in `w` above). Compression is done by rearranging the triplets so that as many doubled letters are present as possible, and these pairs are replaced with their corresponding ASCII uppercase (e.g. fiLoNoN... → fil, lon, non, ...)
* For each triplet, we look at the scores of the titles in which it appears and calculate the mean and standard deviation of the scores. Then we **convert those to integers** and store them in `m`, `s` above, by using the fact that the mean/sd are at most 90 (allowing a direct ASCII encoding, since there are 95 printable ASCII)
* `G` is the normal distribution function - we round e to 2dp and the inverse square root of 2 pi to 1 dp to save on chars.

Altogether the extreme char limit made this one of the worst ideas I've ever come up with, but I'm pretty happy with how much I managed to cram in (even though it doesn't work very well). If anyone has better ideas for compression, please let me know :)

(Thanks to KennyTM for pointing out my pointless compression)

# Answer
> 4 votes
# Python 2, 535 chars, score 0.330910, predicts 11.35

Average the score for titles containing each word, then use the top and bottom 50 words to possibly modify the BASE score in the `guess(title)` function.

Python code:

```
BASE = 11.35
word={}
for sc,ti in csv.reader(open(sys.argv[1])):
    if sc == 'Score': continue
    parts = re.findall(r"[-a-zA-Z']+", ti.lower())
    for p in parts:
        a, c = word.get(p, (0.0,0))
        word[p] = (a+int(sc), c+1)

rank = sorted([(sc/ct,wd) for wd,(sc,ct) in word.items() if ct > 2])
adjust = rank[:50] + rank[-50:]

def guess(title):
    score = BASE
    parts = re.findall(r"[-a-zA-Z']+", title.lower())
    for sc,wd in adjust:
        if wd in parts:
            score *= 0.7 + 0.3*sc/BASE
    return score

```

# Answer
> 2 votes
# C

## Score: Unknown
Length: 5 bytes
Predicts: 5

## Golfed:

```
int s(char *p){return 5;}

```

## Ungolfed:

```
int s(char *p)
{
   return 5;
}

```

A query of the scores gives an average score of 5.

I've not got the ability to test it at the moment, others are welcome to run/edit.

---
Tags: code-challenge
---