# Question
Title: Rosetta Stone Challenge: Find the rule for a series
The goal of a Rosetta Stone Challenge is to write solutions in as many languages as possible. Show off your programming multilingualism!

# The Challenge

Your challenge is to implement a program that will input a list of numbers and output the rule used to generate each successive number in the series, *in as many programming languages as possible*. You are allowed to use any sort of standard library function that your language has, since this is mostly a language showcase.

## What is a "series?"

A series is an ordered list of integers. Each successive number in the series can be generated by applying a simple rule to the previous number in the series. In this challenge, the rule consists of multiplying the number by a constant, and then adding a second constant. Both of the constants can be any integer. The goal of this challenge is to output those two constants.

For the series `2 5 11`, the rule can be written as `2 1`. This means that each number is the previous number, times 2, plus 1. An important fact is that most series have exactly one rule. Some series have either an infinite number or none at all, but you will not have to deal with this.

## Input

Input will be a list of three different integers which are the numbers in the sequence. The numbers can be either space, comma, or newline delimited, but please specify which. I am going to be flexible on this limitation because certain languages may have input restrictions. Here are four examples of input:

```
0 7 14
2 5 11
2 0 -4
5 -19  77

```

## Output

Output will be two integers which represent the rule used to generate the series. The first number will be the multiplicative constant, while the second number will be the additive constant. The formatting of the output can be space, comma, or newline delimited. I am flexible on this limitation as well. Here are the corresponding examples of output:

```
1 7
2 1
2 -4
-4 1

```

# The Objective Winning Criterion

As for an objective winning criterion, here it is: Each language is a separate competition as to who can write the shortest entry, but the overall winner would be the person who wins the most of these sub-competitions. This means that a person who answers in many uncommon languages can gain an advantage. Code-golf is mostly a tiebreaker for when there is more than one solution in a language: the person with the shortest program gets credit for that language.

## Rules, Restrictions, and Notes

Your program can be written in any language that existed prior to April 9th, 2012. I will also have to rely on the community to validate some responses written in some of the more uncommon/esoteric languages, since I am unlikely to be able to test them.

---

# Current Leaderboard

This section will be periodically updated to show the number of languages and who is leading in each.

* AWK (32) - mellamokb
* bash (31) - Peter Taylor
* Befunge (29) - Howard
* bc (39) - kernigh
* brainfuck (174) - CMP
* C (78) - l0n3\_shArk
* C++ (96) - leftaroundabout
* Common Lisp (88) - kernigh
* Cray Chapel (59) - Kyle Kanos
* csh (86) - kernigh
* Cuda (301) - leftaroundabout
* dc (30) - kernigh
* DOS BATCH (54) - mellamokb
* Element (27) - Howard
* es (95) - kernigh
* Factor (138) - kernigh
* Felix (86) - kirbyfan64sos
* Fortran (44) - Kyle Kanos
* Go (101) - Howard
* GolfScript (16) - Howard
* Golflua (44) - Kyle Kanos
* Haskell (35) - leftaroundabout
* J (23) - Gareth
* Java (141) - Howard
* JavaScript (47) - mellamokb
* Julia (71) - M L
* Lua (51) - Howard
* Mercury (319) - leftaroundabout
* MoonScript (48) - kirbyfan64sos
* Nimrod (146) - leftaroundabout
* Owl (22) - r.e.s.
* Pascal (88) - leftaroundabout
* Perl (57) - Gareth
* PHP (61) - mellamokb
* PicoLisp (72) - kernigh
* Piet (56) - M L
* PostScript (61) - Howard
* Python (40) - Howard
* Q (36) - tmartin
* QBasic (34) - mellamokb
* R (50) - r.e.s.
* Ruby (44) - Howard
* Scala (102) - Gareth
* SQL (57) - Aman ZeeK Verma
* TI-83 BASIC (25) - mellamokb
* Unlimited Register Machine (285) - Paxinum
* VBA (57) - Gaffi
* Whitespace (123) - r.e.s.
* zsh (62) - kernigh

---

# Current User Rankings

Equal ranks are sorted alphabetically.

1. Howard (9): Befunge (29), Element (27), Go (101), GolfScript (16), Java (141), Lua (51), PostScript, (61) Python, (40) Ruby (44)
2. kernigh (8): bc (39), Common Lisp (88), csh (86), dc (30), es (95), Factor (138), PicoLisp (72), zsh (62)
3. leftroundabout (6): C++ (96), Cuda (301), Haskell (35), Mercury (319), Nimrod (146), Pascal (88)
4. mellamokb (6): AWK (32), DOS BATCH (54), JavaScript (47), PHP (61), QBasic (34), TI-83 BASIC (41)
5. Gareth (3): J (23), Perl (57), Scala (102)
6. Kyle Kanos (3): Cray Chapel (59), Fortran (44), Golflua (44)
7. r.e.s. (3): Owl (22), R (50), Whitespace (123)
8. kirbyfan64sos (2): Felix (86), MoonScript (48)
9. M L (2): Julia (71), Piet (56)
10. Aman Zeek verma (1): SQL (57)
11. CMP (1): brainfuck (174)
12. Gaffi (1): VBA (57)
13. l0n3\_shArk (1): C (78)
14. Paxinum (1): Unlimited Register Machine (285)
15. Peter Taylor (1): bash (31)
16. tmartin (1): Q (36)

# Answer
> 9 votes
### GolfScript, 16 characters

```
~1$- 1$3$-/.p@*-

```

Input is given as space-separated list.

### JavaScript, 56 characters

```
p=prompt;x=alert;a=p();b=p();x(m=(p()-b)/(b-a));x(b-a*m)

```

Input is given on prompt.

### Ruby, 44 characters

```
a,b,c=eval("[#{gets}]");m=c-b;p m/=b-a,b-m*a

```

Input is here given as comma-separated list.

### Python, 40 characters

```
a,b,c=input();m=c-b;m/=b-a;print m,b-m*a

```

Input is again comma-separated.

### Java, 141 characters

```
enum E{E;static int s(){return new java.util.Scanner(System.in).nextInt();}{int a=s(),b=s(),m=s()-b;m/=b-a;System.out.print(m+" "+(b-a*m));}}

```

Input separated by newline.

### Lua, 51 characters

```
r=io.read
a,b=r(),r()
m=(r()-b)/(b-a)
print(m,b-m*a)

```

Input separated by newline.

### Go, 101 characters

```
package main
import"fmt"
var a,b,c int
func main(){fmt.Scan(&a,&b,&c)
c-=b
c/=b-a
fmt.Print(c,b-a*c)}

```

Input separated by newline.

### Fortran, 90 characters

```
      PROGRAM X
      READ(*,*)I,J,K
      K=(K-J)/(J-I)
      WRITE(*,*)K,J-I*K
      END

```

Input separated by newline.

### Befunge, 29 characters

```
&01p&:11p:&-01g11g-/:.01g*-.@

```

### PostScript, 61 characters

```
2 5 14
1 index sub 1 index 3 index sub idiv dup = 3 2 roll mul sub =

```

### Owl, 23 characters

```
<%<%<$-1`4'-/%.32)2'*-.

```

Input separated by newline.

### Element, 27 characters

```
_-a;_3:'-_+"a~+/2:`a~*+\ ``

```

Input separated by newline.

# Answer
> 9 votes
## QBasic, 42

```
INPUT "",a,b,c
m=(c-b)/(b-a)
PRINT m;b-m*a

```

Requires input with commas, outputs with spaces (is this ok?)

---

## Mercury, 319

```
:-module r.
:-interface.
:-import_module io,list,int,char,string.
:-pred main(io::di,io::uo)is det.
:-implementation.
main(!IO):-io.read_line_as_string(J,!IO),(if J=ok(I),[A,B,C]=list.map(string.det_to_int,string.words_separator(char.is_whitespace,I)),M=(C-B)/(B-A)then io.format("%d %d",[i(M),i(B-M*A)],!IO)else true).

```

---

## Haskell, ~~85~~ 81

```
f[a,b,c]|m<-(c-b)`div`(b-a)=[m,b-m*a]
main=getLine>>=mapM_ print.f.map read.words

```

Now inputs with spaces, outputs with newlines.

---

## C, 80

```
main(a,b,c,m){scanf("%d %d %d",&a,&b,&c);m=(c-b)/(b-a);printf("%d %d",m,b-m*a);}

```

---

## C++, 96

```
#include<iostream>
main(){int a,b,c,m;std::cin>>a>>b>>c;m=(c-b)/(b-a);std::cout<<m<<' '<<b-m*a;}

```

---

## Nimrod, 146

```
import strutils
var
 q:array[0..3,int]
 b,m:int
for i in 0..2:q[i]=ParseInt(readLine(stdin))
b=q[1]
m=(q[2]-b)div(b-q[0])
echo($m,",",$(b-m*q[0]))

```

Input w/ newlines, output comma.

---

This one won't count, but I feel it still fits in in some way:

## Mathematical theorem, 713 characters of LaTeX

```
\documentclass{article}\usepackage{amsmath}\usepackage{amsthm}\begin{document}Theorem: for a sequence $(a_i)_i$ of integers with $a_2\neq a_1$ where $a_3-a_2$ is divisible by $a_2-a_1$, $m:=\frac{a_3-a_2}{a_2-a_1},\ p:=a_2-m\cdot a_1$ give rise to a sequence\[b_i:=\begin{cases}a_1&\text{for }i=1\\b_{i-1}\cdot m+p&\text{else}\end{cases}\] such that $b_i=a_i\ \forall i\leq 3$.

Proof: $i=1$ is trivial,\[\begin{aligned}b_2=&b_1\cdot m+p=a_1\frac{a_3-a_2}{a_2-a_1}+a_2-\frac{a_1a_3-a_1a_2}{a_2-a_1}=a_2,\\b_3=&b_2\cdot m+p=\frac{a_2a_3-a_2^2}{a_2-a_1}+a_2-\frac{a_1a_3-a_2^2}{a_2-a_1}\\=&\frac{a_2a_3-a_1a_3+(a_2-a_1)a_2-a_2^2+a_1a_2}{a_2-a_1}\\=&\frac{a_2-a_1a_3+0}{a_2-a_1}=a_3.\end{aligned}\]\qed\end{document}

```

---

While we're at writing `:=` definitions...

## Pascal, ~~90~~ 88

```
program r;var a,b,c:integer;begin;read(a,b,c);c-=b;c:=c div(b-a);write(c,' ',b-c*a);end.

```

---

## Cuda, 301

```
#include<stdio.h>
__global__ void r(int*q){if(!(blockIdx.x|threadIdx.x)){q[1]-=*q;q[1]/=(*q-q[2]);*q-=q[1]*q[2];}}
main(){int p[3],*q;scanf("%d%d%d",p+2,p,p+1);cudaMalloc(&q,24);cudaMemcpy(q,p,24,cudaMemcpyHostToDevice);r<<<1,1>>>(q);cudaMemcpy(p,q,24,cudaMemcpyDeviceToHost);printf("%d %d",p[1],*p);}

```

# Answer
> 8 votes
## Brainfuck - 174

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

```

## Piet - 82?

Not sure how to measure competitive golf here. I'm gonna go with total image size (in codels) Mine is 41x2:

## Befunge - 34

```
&00p&10p&10g-10g00g-/:.00g*10g\-.@

```

## English - 278

```
The multiplier is the quotient of the difference of the second
and third values and the second and first values.
To generate a new term, multiply the current term by the multiplier
and add the difference of the first value and the product of the
multiplier and the second value.

```

Not sure if this counts, but thought I'd give it a shot. It is remarkably difficult to describe even a simple algorithm accurately. Kinda wish English supported some kind of grouping symbol to establish precedence.

# Answer
> 7 votes
## AWK (32)

```
{m=$3-$2;print m/=$2-$1,$2-$1*m}

```

Demo: http://ideone.com/kp0Dj

---

## bash (38)

```
awk '{m=$3-$2;print m/=$2-$1,$2-$1*m}'

```

Demo: http://ideone.com/tzFi8

---

## DOS/BATCH (54 55)

```
set/a m=(%3-%2)/(%2-%1)&set/a n=%2-%m%*%1&echo %m% %n%

```

Takes parameters as space-separated list of arguments.

---

## Java (143 185)

> `enum R{R;{int a=0,b=0,c,i=2;for(;(c=new java.util.Scanner(System.in).nextInt()+b*--i)+i>=c;b=c)a+=c*i;c/=b-a;System.out.print(c+" "+(b-a*c));}}`

---

## JavaScript (48 61 67)

```
p=prompt;m=p(b=p(a=p()))-b;alert([m/=b-a,b-a*m])

```

 Demo: http://jsfiddle.net/BT8bB/6/

---

## PHP (61 77)

```
<?list(,$a,$b,$c)=$argv;$c-=$b;echo($c/=$b-$a).' '.$b-=$c*$a;

```

Demo: http://ideone.com/CEgke

---

## QBasic (34)

```
INPUT a,b,c
m=(c-b)/(b-a)
?m;b-m*a

```

---

## TI-83 Basic (25 ~~41~~)

```
:Prompt A,B,C
:(C-B)/(B-A
:Disp Ans,B-AAns

```

Yes, the missing right parenthesis is on purpose. It's a well-known optimization technique that closing the parentheses before a STO operation is not necessary in TI-83 Basic programming.

# Answer
> 7 votes
## AWK, 35 characters

```
{m=($3-$2)/($2-$1);print m,$2-$1*m}

```
* Input format: `2 0 -4`

## bc, 39 characters

```
define f(a,b,c){
m=(c-b)/(b-a)
m
b-a*m}

```
* Input format: `z=f(2, 0, -4)`
* The input is a `bc` expression. After `bc` reads the source file, it reads the standard input. This is why the input must look like a function call.
* I use OpenBSD `bc`, which requires a newline after the `{`.

## Common Lisp, 88 characters

```
(let*((a(read))(b(read))(c(read))(m(/(- c b)(- b a))))(format
t "~A ~A" m (- b(* a m))))

```
* Input format: `2 0 -4`

## csh, 86 characters

```
set i=(`cat`)
@ m=($i[3] - $i[2]) / ($i[2] - $i[1])
@ n=$i[2] - $i[1] * $m
echo $m $n

```
* Input format: `2 0 -4`
* The 86th character is newline at end of file. `csh` is the only language for which I count newline at end of file. This is because `csh` never runs the last command unless newline is there.
* `set i=($<)` does not work, because `$<` has no word splitting.

## dc, 30 characters

```
?scsbsalclb-lbla-/psmlblalm*-p

```
* Input format: `2 0 _4`, where `_` is the underscore.

## es, 95 characters

```
i=(`cat)
b=$i(2)
m=`{expr \( $i(3) - $b \) / \( $b - $i(1) \)}
echo $m `{expr $b - $i(1) \* $m}

```
* Input format: `2 0 -4`
* `es` is the *extensible shell* by Paul Haahr and Byron Rakitzis.

## Factor, 138 characters

```
USING: eval formatting io kernel locals math ;
contents eval( -- a b c ) [let :> ( a b c )
c b - b a - / dup a * b swap - "%d %d" printf ]

```
* Input format: `2 0 -4`

## PicoLisp, ~~74~~ 72 characters

```
(in()(let(r read a(r)b(r)c(r)m(/(- c b)(- b a)))(print
m (- b(* a m)))))

```
* Input format: `2 0 -4`
* EDIT: Lost 2 characters by changing `a(read)b(read)c(read)` to `r read a(r)b(r)c(r)`.

## TI-83 BASIC, ~~63~~ 61 characters

```
:Input A
:Input B
:Input C
:(C-B)/(B-A)→M
:Disp M
:Disp B-A*M

```
* Input format: `2` ENTER `0` ENTER `¯4` ENTER, where `¯` is the calculator's unary minus.
* I counted Unicode characters;  (the right arrow) counts as U+2192. For example, the calculator counts `Input A` as 2 characters, but I count `Input A` as 7 characters. I also count `:` as 1 character.
* EDIT: I miscounted: there are 61, not 63, characters.

## zsh, 62 characters

```
i=(`cat`)
((b=i[2],m=(i[3]-b)/(b-i[1]),n=b-i[1]*m))
echo $m $n

```
* Input format: `2 0 -4`

# Answer
> 6 votes
## Whitespace, 123

```

```

I/O is newline-separated. (To obtain the source code, enter edit mode and copy the whitespace between the preformat tags; or, see the online example at Ideone.)

Explanation, where S,T,L represents Space,Tab,Linefeed:

```
Pseudocode     Whitespace
----------     ----------
push 0         SS SSL
readn          TLTT
push 1         SS STL
readn          TLTT
push 2         SS STSL
dup            SLS
readn          TLTT
retr           TTT
push 1         SS STL
retr           TTT
-              TSST
push 1         SS STL
retr           TTT
push 0         SS SSL
retr           TTT
-              TSST
/              TSTS
dup            SLS
outn           TLST
push 10        SS STSTSL
outc           TLSS
push 0         SS SSL
retr           TTT
*              TSSL
push 1         SS STL
retr           TTT
swap           SLT
-              TSST
outn           TLST
exit           LLL

```

---

## R, 50

```
x=scan(n=3);y=diff(x);z=y[2]/y[1];c(z,x[2]-x[1]*z)

```

I/O is space-separated.

---

## Owl

**---22---**

```
< <%<-2`2`-/%.10)2'*-.

```

I/O is newline-separated.

**---19---** (if this version is allowed; but I think it's cheating, since the \ is executable code):

```
1`-1`3`-/%.32)2'*-.

```

I/O is space-separated. Command-line usage: `owl prog 5 19\ 77` (the \ acts as a postfix unary minus in Owl).

# Answer
> 5 votes
## J, 23 characters

```
(],1{x-0{x*])%~/2-/\x=:

```

Usage:

```
   (],1{x-0{x*])%~/2-/\x=: 5 _19 77
_4 1

```

Negative numbers are represented by underscores in J.

## PHP, 88 characters

```
<?php
list($x,$y,$z)=split(' ',fgets(STDIN));
$a=($z-$y)/($y-$x);
echo$a." ".($y-$a*$x);

```

## Scala, 102 characters

```
val x=readLine.split(" ").toList.map(_.toInt)
val a=(x(2)-x(1))/(x(1)-x(0))
print(a+" "+(x(1)-x(0)*a))

```

## Perl, 57 characters

```
s!(.+) (.+) (.+)!$a=($3-$2)/($2-$1);$a." ".($2-$1*$a)!e

```

Requires the '-p' option, for which I have added 2 characters. Assumes that the input is valid to save some characters.

All my answers take space separated numbers.

# Answer
> 4 votes
## PHP, 74,72,69

```
<?fscanf(STDIN,'%d%d%d',$a,$b,$c);echo($d=($c-$b)/($b-$a)).' '.($b-$d*$a);

```

When input is passed as arguments:

```
<?echo($d=($argv[3]-$argv[2])/($b=$argv[2]-$a=$argv[1])).' '.($b-$d*$a);

```

Now, as @mellamokb suggested, using $n=$argv:

```
<?$n=$argv;echo($d=($n[3]-$n[2])/($b=$n[2]-$a=$n[1])).' '.($b-$d*$a);

```

## C, 77,78

```
main(a,b,c,d){printf("%d %d",d=(c-b)/(b-a),b-d*a,scanf("%d%d%d",&a,&b,&c));}

```

^ doesn't work so, here's the stuff: \[thanks to @ugoren for bringing it to notice\]

```
main(a,b,c,d){printf("%d %d",d,b-a*(d=(c-b)/(b-a)),scanf("%d%d%d",&a,&b,&c));}

```

# Answer
> 3 votes
# DOS-BATCH, 98

```
@ECHO OFF&SET/P p=&SET/P q=&SET/P r=&SET/A m=(%r%-%q%)/(%q%-%p%)&SET/A n=%q%-%p%*%m%&ECHO %m% %n%

```

Input in separate lines

# Bash, 51

```
m=$((($3 - $2)/($2 - $1)))
echo $m $(($2 - $m*$1))

```

Example : `sh prog.sh 2 0 -4` (space separated arguments)

# Perl, 84

```
@s=split(/ /,<STDIN>);$m=($s[2]-$s[1])/($s[1]-$s[0]);print $m." ".($s[1]-$s[0]*$m);

```

# Java, 297

```
import java.util.*;public class A{public static void main(String a[]){StringTokenizer s=new StringTokenizer(new Scanner(System.in).nextLine());int i=4;int[] p=new int[i];while(i-->1)p[3-i]=Integer.parseInt(s.nextToken());p[3]=(p[2]-p[1])/(p[1]-p[0]);System.out.print(p[3]+" "+(p[1]-p[0]*p[3]));}}

```

Space separated input, space separated output.

# SQL, 57

```
select (&3-&2)/(&2-&1),&2-((&3-&2)/(&2-&1)*&1) from dual

```

This is a sad entry, but 'just' solves the purpose. The query binds input at runtime 1,2,3 are variables in order of input.

# Answer
> 3 votes
### bash (42 chars)

Pure bash:

```
((m=($3-$2)/($2-$1),c=$2-m*$1));echo $m $c

```

### bash (31 chars)

Shelling out to something else:

```
owl -p"<%<%<$-1`4'-/%.32)2'*-."

```

(Based on Howard's OWL implementation)

# Answer
> 3 votes
## VBA, 57 characters

```
Sub x(a,b,c)
y=(c-b)/(b-a)
MsgBox y & " " & b-a*y
End Sub

```

(*This is basically the same as the other 'BASIC' functions, but I didn't see any VBA submissions out there already.*)

# Answer
> 3 votes
This is (non-optimized) code for the unimited register machine, described here: http://www.proofwiki.org/wiki/Definition:Unlimited\_Register\_Machine

The input should be in register 1,2 and 3, and the output will be in register 1, 2 after the program is done. Non-negative and non-integer numbers are not handled, but inputs 0,7,14 and 2,5,11 are handled correctly.

`Zero[8]
Trans[2,11]
Jump[3,11,7]
Succ[11]
Succ[8]
Jump[11,11,3]
Zero[5]
Trans[1,12]
Jump[2,12,13]
Succ[12]
Succ[5]
Jump[12,12,9]
Zero[17]
Trans[8,13]
Jump[13,17,25]
Zero[16]
Trans[5,14]
Jump[13,14,22]
Succ[14]
Succ[16]
Jump[14,14,18]
Succ[9]
Trans[16,13]
Jump[17,17,15]
Zero[6]
Zero[20]
Jump[9,6,40]
Zero[7]
Trans[1,21]
Jump[20,7,36]
Succ[21]
Trans[21,19]
Trans[19,21]
Succ[7]
Jump[7,7,30]
Trans[21,18]
Trans[18,20]
Succ[6]
Jump[6,6,27]
Trans[20,4]
Zero[10]
Trans[4,15]
Jump[2,15,47]
Succ[15]
Succ[10]
Jump[15,15,43]
Trans[9,1]
Trans[10,2]`

EDIT: by removing brackes, and shortening instruction names:

**URM 285**

`Z8 T2,11 J3,11,7 S11 S8 J11,11,3 Z5 T1,12 J2,12,13 S12 S5 J12,12,9 Z17 T8,13 J13,17,25 Z16 T5,14 J13,14,22 S14 S16 J14,14,18 S9 T16,13 J17,17,15 Z6 Z20 J9,6,40 Z7 T1,21 J20,7,36 S21 T21,19 T19,21 S7 J7,7,30 T21,18 T18,20 S6 J6,6,27 T20,4 Z10 T4,15 J2,15,47 S15 S10 J15,15,43 T9,1 T10,2`

# Answer
> 2 votes
# Q, 36

```
{a,x[2]-x[1]*a:%[x[2]-x 1;x[1]-x 0]}

```

usage

```
q){a,x[2]-x[1]*a:%[x[2]-x 1;x[1]-x 0]}each(0 7 14;2 5 11;2 0 -4;5 -19 77)
1  7
2  1
2  -4
-4 1

```

# Answer
> 2 votes
## Fortran 44

```
read*,i,j,k;k=(k-j)/(j-i);print*,k,j-i*k;end

```

Input will be in a single line (comma or space separated)

## Cray Chapel 59

```
var i,j,k:int;read(i,j,k);k=(k-j)/(j-i);write(k," ",j-i*k);

```

Input will be on single line, no newline (add 2 chars for that by using `writeln` in place of `write`).

## Golflua 44

```
r=I.r;a,b=r(),r();m=(r()-b)/(b-a);w(m,b-m*a)

```

Newline delimited input, space delimited output

# Answer
> 2 votes
# Julia, 71 characters

Space delimited input and output.

`i,j,k=int(split(readline(STDIN)));println("$(l=div(k-j,j-i)) $(j-i*l)")`

Example input and output:

```
julia> i,j,k=int(split(readline(STDIN)));println("$(l=div(k-j,j-i)) $(j-i*l)")
5 -19 77
-4 1

```

# Piet, ~~86~~ ~~60~~ 56 codels (14x4), codel size 10 for better visibility

I could actually shrink down the amount of codels by a whopping 35%. I didn’t expect such a good outcome. Coding this program backwards was, as I expected, quite successful. I doubt it can be shorter than this, but I would be really interested if anyone could find a smaller solution.

The challenge does not state if the program has to stop after showing the result, so my smallest (56 codel) program should be valid. It just loops back to the beginning after showing the result, asking for a new triplet of integers. Due to the tight packing there is no place for the output of two newline characters, but that is no problem with the npiet interpreter, because it always prints a ‘?’ if it awaits input.

There are two possible sizes to build a looped version, but a version that runs only once is only possible in a program that’s at least 64 codels (16x4) big. The versions below show the reason. Maybe it’s also interesting for those who are familiar with Piet.

**The final, most tightly packed 56 codel version, with a loop**:

Second version (60 codels), with a loop

If the 56 codel version is against the rules, here is the **final 64 codel version, running only once**:

My first version (86 codels)

Input and output are newline delimited.

Example input and output:

```
D:\codegolf\npiet-1.3a-win32>npiet ml_series.png
? 5
? -19
? 77
-4
1

```

For looped versions, looking a bit uglier:

```
D:\codegolf\npiet-1.3a-win32>npiet ml_series_56_codels.png"
? 5
? -19
? 77
-4
1? 5
? -19
? 77
-4
1? 5
? -19
? 77
-4
1?

```

I chose newline as delimiter because coding ASCII 10 (\n) obviously needs only 7 codels, compared to ASCII 32 ( ) which needs 8 codels or even ASCII 40 (,) which needs 9 codels.

Coding backwards from the result to the first input is a great way to reduce the codel use for ROL operations. The stack order at the beginning and at the end are known, the rest is easily done by hand.

Here is a text version of the 64 codel program (with stack), in my made-up shorthand. The shorter programs just don’t terminate but loop back to the beginning.

```
NOP ADD DIV GRT DUP INC END
 0   +   /   >   =   c   ~
PSH SUB MOD PTR ROL OUN
 X   -   %   #   @   N
POP MUL NOT SWI INN OUC
 ?   *   !   $   n   C

                   1
        1    1   2 2     1                   a,b,c: input for series
      5 5  3 3 c c cb  3 3                       D: c-b
    b b bb b bbb b bcD D Da                      E: b-a
   bb b bb b baa a aaa a abE F                   F: D/E, (c-b)/(b-a), mul. const.
  bbb b ba a abb b bbb b bDDFFF    5             G: a*F, a(c-b)/(b-a)
 aaaa a aa a aaa a aaa a aaaaaaG  55 10          H: b-G, b-a*F, add. const.
aaaaa a ab b bbb b bbb b bbbbbbbH HH  H H
n=n==5X1X@3X1X@n2X1X@-3X1X@-/=N*-5X=  + CN~
| |            |     |     || |||\____/ ||
| |            |     |     || |||  |    |+———— output add. const.
| |            |     |     || |||  |    +————— output newline character
| |            |     |     || |||  +—————————— 5 DUP + =10, ASCII for \n
| |            |     |     || ||+————————————— H, add. const.
| |            |     |     || |+—————————————— G
| |            |     |     || +——————————————— output mul. const.
| |            |     |     |+————————————————— F, mul. const.
| |            |     |     +—————————————————— E
| |            |     +———————————————————————— D
| |            +—————————————————————————————— input c
| +——————————————————————————————————————————— input b
+————————————————————————————————————————————— input a

```

# Answer
> 1 votes
# MoonScript(48 chars, newline delimited input, space delimited output)

```
r=io.read
a,b=r!,r!
m=(r!-b)/(b-a)
print m,b-m*a

```

# Felix(86 chars, newline delimited input, comma delimited output)

```
gen r()=>int $ readln stdin;
var a,b=r(),r();
var m=(r()-b)/(b- a);
println(m,b- m*a);

```

# Julia(84 chars, space delimited input, space delimited output)

```
a,b,c=tuple(map(int,split(readline(STDIN)))...)
m=(c-b)/(b-a)
println("$m $(b-m*a)")

```

---
Tags: code-golf, math, rosetta-stone
---


# Question
Title: Calculate a probability exactly and quickly
\[This is a partner question to Calculate a probability exactly \]

This task is about writing code to compute a probability exactly *and quickly*. The output should be a precise probability written as a fraction in its most reduced form. That is it should never output `4/8` but rather `1/2`.

For some positive integer `n`, consider a uniformly random string of 1s and -1s of length `n` and call it A. Now concatenate to `A` its first value. That is `A[1] = A[n+1]` if indexing from 1. `A` now has length `n+1`. Now also consider a second random string of length `n` whose first `n` values are -1, 0, or 1 with probability 1/4,1/2, 1/4 each and call it B.

Now consider the inner product of `A[1,...,n]` and `B` and the inner product of `A[2,...,n+1]` and `B`.

For example, consider `n=3`. Possible values for `A` and `B` could be `A = [-1,1,1,-1]` and `B=[0,1,-1]`. In this case the two inner products are `0` and `2`.

Your code must output the probability that both inner products are zero.

Copying the table produced by Martin Büttner we have the following sample results.

```
n   P(n)
1   1/2
2   3/8
3   7/32
4   89/512
5   269/2048
6   903/8192
7   3035/32768
8   169801/2097152

```

**Languages and libraries**

You can use any freely available language and libraries you like. I must be able to run your code so please include a full explanation for how to run/compile your code in linux if at all possible.

**The task**

Your code must start with `n=1` and give the correct output for each increasing n on a separate line. It should stop after 10 seconds.

**The score**

The score is simply the highest `n` reached before your code stops after 10 seconds when run on my computer. If there is a tie, the winner be the one to get to the highest score quickest.

**Table of entries**

* `n = 64` in **Python**. Version 1 by Mitch Schwartz
* `n = 106` in **Python**. Version June 11 2015 by Mitch Schwartz
* `n = 151` in **C++**. Port of Mitch Schwartz's answer by kirbyfan64sos
* `n = 165` in **Python**. Version June 11 2015 the "pruning" version by Mitch Schwartz with `N_MAX = 165`.
* `n = 945` in **Python** by Min\_25 using an exact formula. Amazing!
* `n = 1228` in **Python** by Mitch Schwartz using another exact formula (based on Min\_25's previous answer).
* `n = 2761` in **Python** by Mitch Schwartz using a faster implementation of the same exact formula.
* `n = 3250` in **Python** using **Pypy** by Mitch Schwartz using the same implementation. This score needs `pypy MitchSchwartz-faster.py |tail` to avoid console scrolling overhead.

# Answer
> 24 votes
# Python

A closed-form formula of `p(n)` is

An exponential generating function of `p(n)` is

where `I_0(x)` is the modified Bessel function of the first kind.

**Edit on 2015-06-11:**
\- updated the Python code.

**Edit on 2015-06-13:**
\- added a proof of the above formula.
\- fixed the `time_limit`.
\- added a PARI/GP code.

**Python**

```
def solve():
  # straightforward implementation

  from time import time
  from itertools import count

  def binom(n, r):
    return facts[n] // (facts[r] * facts[n - r])

  def p(N):
    ans = 0
    for i in range(1 + N // 2):
      t = binom(2 * (N - 2 * i), N - 2 * i)
      t *= binom(N, 2 * i)
      t *= binom(4 * i, 2 * i)
      ans += t
    e = (ans & -ans).bit_length() - 1
    numer = ans >> e
    denom = 1 << (3 * N - 1 - e)
    return numer, denom

  facts = [1]
  time_limit = 10.0 + time()

  for i in count(1):
    facts.append(facts[-1] * (2 * i - 1))
    facts.append(facts[-1] * (2 * i))

    n, d = p(i)

    if time() > time_limit:
      break

    print("%d %d/%d" % (i, n, d))

solve()

```

**PARI/GP**

```
p(n) = polcoeff( (exp(x/2) + 1) * besseli(0, x/4) ^ 2, n) * n!;

```

**Proof:**
This problem is similar to a 2-dimensional (restricted) random walk problem.

If `A[i] = A[i+1]`, we can move from `(x, y)` to `(x+1, y+1)` \[1 way\], `(x, y)` \[2 ways\] or `(x-1, y-1)` \[1 way\].

If `A[i] != A[i+1]`, we can move from `(x, y)` to `(x-1, y+1)` \[1 way\], `(x, y)` \[2 ways\] or `(x+1, y-1)` \[1 way\].

Let `a(n, m) = [x^m]((x+1)^n + (x-1)^n)`, `b(n) = [x^n](1+x)^{2n}` and `c(n)` be the number of ways to move from `(0, 0)` to `(0, 0)` with `n` steps.

Then, `c(n) = \sum_{i=0}^n a(n, i) * b(i) * b(n-i).`

Since `p(n) = c(n) / 8^n`, we can get the above closed-form formula.

# Answer
> 9 votes
## Python

**Note:** Congratulations to Min\_25 for finding a closed-form solution!

Thanks for the interesting problem! It can be solved using DP, although I am not currently feeling very motivated to optimise for speed to get a higher score. It could be nice for golf.

The code reached `N=39` within 10 seconds on this old laptop running Python 2.7.5.

```
from time import*
from fractions import*
from collections import*

X={(1,0,0,0):1,(-1,0,0,0):1}

T=time()
N=0

while 1:
    Y=defaultdict(lambda:0)
    n=d=0
    for a,b,s,t in X:
        c=X[(a,b,s,t)]
        for A in ( (1,-1) if N else [a] ):
            for B in 1,0,0,-1:
                n+=c*(s+A*B==0==t+A*b+a*B)
                d+=c
                Y[(a,B,s+A*B,t+A*b)]+=c
    if time()>T+10: break
    N+=1
    print N,Fraction(n,d)
    X=Y

```

For tuple `(a,b,s,t)`: `a` is the first element of `A`, `b` is the last element of `B`, `s` is the inner product of `A[:-1]` and `B`, and `t` is the inner product of `A[1:-1]` and `B[:-1]`, using Python slice notation. My code does not store the arrays `A` or `B` anywhere, so I use those letters to refer to the next elements to be added to `A` and `B`, respectively. This variable naming choice makes the explanation a little awkward, but allows for a nice-looking `A*b+a*B` in the code itself. Note that the element being added to `A` is the penultimate one, since the last element is always the same as the first. I have used Martin Büttner's trick of including `0` twice in `B` candidates in order to get the proper probability distribution. The dictionary `X` (which is named `Y` for `N+1`) keeps track of the count of all possible arrays according to the value of the tuple. The variables `n` and `d` stand for numerator and denominator, which is why I renamed the `n` of the problem statement as `N`.

The key part of the logic is that you can update from `N` to `N+1` using just the values in the tuple. The two inner products specified in the question are given by `s+A*B` and `t+A*b+a*B`. This is clear if you examine the definitions a bit; note that `[A,a]` and `[b,B]` are the last two elements of arrays `A` and `B` respectively.

Note that `s` and `t` are small and bounded according to `N`, and for a fast implementation in a fast language we could avoid dictionaries in favor of arrays.

It may be possible to take advantage of symmetry considering values differing only in sign; I have not looked into that.

**Remark 1**: The size of the dictionary grows quadratically in `N`, where size means number of key-value pairs.

**Remark 2**: If we set an upper bound on `N`, then we can prune tuples for which `N_MAX - N <= |s|` and similarly for `t`. This could be done by specifying an absorbing state, or implicitly with a variable to hold the count of pruned states (which would need to be multiplied by 8 at each iteration).

**Update**: This version is faster:

```
from time import*
from fractions import*
from collections import*

N_MAX=115

def main():
    T=time()

    N=1
    Y={(1,0,0,0):1,(1,1,1,0):1}
    n=1
    thresh=N_MAX

    while time() <= T+10:
        print('%d %s'%(N,Fraction(n,8**N/4)))

        N+=1
        X=Y
        Y=defaultdict(lambda:0)
        n=0

        if thresh<2:
            print('reached MAX_N with %.2f seconds remaining'%(T+10-time()))
            return

        for a,b,s,t in X:
            if not abs(s)<thresh>=abs(t):
                continue

            c=X[(a,b,s,t)]

            # 1,1

            if not s+1 and not t+b+a: n+=c
            Y[(a,1,s+1,t+b)]+=c

            # -1,1

            if not s-1 and not t-b+a: n+=c
            Y[(a,1,s-1,t-b)]+=c

            # 1,-1

            if not s-1 and not t+b-a: n+=c
            Y[(a,-1,s-1,t+b)]+=c

            # -1,-1

            if not s+1 and not t-b-a: n+=c
            Y[(a,-1,s+1,t-b)]+=c

            # 1,0

            c+=c

            if not s and not t+b: n+=c
            Y[(a,0,s,t+b)]+=c

            # -1,0

            if not s and not t-b: n+=c
            Y[(a,0,s,t-b)]+=c

        thresh-=1

main()

```

Optimisations implemented:

* put everything into `main()` -- local variable access is faster than global
* handle `N=1` explicitly to avoid the check `(1,-1) if N else [a]` (which enforces that the first element in the tuple is consistent, when adding elements to `A` starting from the empty list)
* unroll the inner loops, which also eliminates multiplication
* double the count `c` for adding a `0` to `B` instead of doing those operations twice
* the denominator is always `8^N` so we do not need to keep track of it
* now taking symmetry into account: we can fix the first element of `A` as `1` and divide the denominator by `2`, since the valid pairs `(A,B)` with `A[1]=1` and those with `A[1]=-1` can be put into one-to-one correspondence by negating `A`. Similarly, we can fix the first element of `B` as non-negative.
* now with pruning. You would need to fiddle with `N_MAX` to see what score it can get on your machine. It could be rewritten to find an appropriate `N_MAX` automatically by binary search, but seems unnecessary? Note: We do not need to check the pruning condition until reaching around `N_MAX / 2`, so we could get a little speedup by iterating in two phases, but I decided not to for simplicity and code cleanliness.

# Answer
> 5 votes
## Python

Using Min\_25's idea of random walk, I was able to arrive at a different formula:

Here is a Python implementation based on Min\_25's:

```
from time import*
from itertools import*

def main():
    def binom(n, k):
        return facts[n]/(facts[k]*facts[n-k])

    def p(n):
        numer=0
        for i in range(n/2+1):
            t=binom(2*i,i)
            t*=t
            t*=binom(n,2*i)
            t<<=2*(n-2*i)
            numer+=t
        if not n&1:
            numer+=t
        e=(numer&-numer).bit_length()-1
        numer>>=e
        denom=1<<(3*n-e)
        return numer, denom

    facts=[1]
    time_limit=time()+10

    for i in count(1):
        facts.append(facts[-1]*i)

        n,d=p(i)

        if time()>time_limit:
            break

        print("%d %d/%d"%(i,n,d))

main()

```

**Explanation / proof:**

First we solve a related counting problem, where we allow `A[n+1] = -A[1]`; that is, the additional element concatenated to `A` can be `1` or `-1` regardless of the first element. So we do not need to keep track of how many times `A[i] = A[i+1]` occurs. We have the following random walk:

From `(x,y)` we can move to `(x+1,y+1)` \[1 way\], `(x+1,y-1)` \[1 way\], `(x-1,y+1)` \[1 way\], `(x-1,y-1)` \[1 way\], `(x,y)` \[4 ways\]

where `x` and `y` stand for the two dot products, and we are counting the number of ways to move from `(0,0)` to `(0,0)` in `n` steps. That count would then be multiplied by `2` to account for the fact that `A` can start with `1` or `-1`.

We refer to staying at `(x,y)` as a *zero move*.

We iterate over the number of non-zero moves `i`, which has to be even in order to get back to `(0,0)`. Horizontal and vertical movements make up two independent one-dimensional random walks, which can be counted by `C(i,i/2)^2`, where `C(n,k)` is binomial coefficient. (For a walk with `k` steps left and `k` steps right, there are `C(2k,k)` ways to choose the order of steps.) Additionally there are `C(n,i)` ways to place the moves, and `4^(n-i)` ways to choose the zero moves. So we get:

```
a(n) = 2 * sum_{i in (0,2,4,...,n)} C(i/2,i)^2 * C(n,i) * 4^(n-i)

```

Now, we need to turn back to the original problem. Define an allowable pair `(A,B)` to be *convertible* if `B` contains a zero. Define a pair `(A,B)` to be *almost allowable* if `A[n+1] = -A[1]` and the two dot products are both zero.

**Lemma:** For a given `n`, the almost allowable pairs are in one-to-one correspondence with the convertible pairs.

We can (reversibly) convert a convertible pair `(A,B)` into an almost allowable pair `(A',B')` by negating `A[m+1:]` and `B[m+1:]`, where `m` is the index of the last zero in `B`. The check for this is straightforward: If the last element of `B` is zero, we do not need to do anything. Otherwise, when we negate the last element of `A`, we can negate the last element of `B` in order to preserve the last term of the shifted dot product. But this negates the last value of the non-shifted dot product, so we fix this by negating the second-to-last element of `A`. But then this throws off the second-to-last value of the shifted product, so we negate the second-to-last element of `B`. And so on, until reaching a zero element in `B`.

Now, we just need to show that there are no almost allowable pairs for which `B` does not contain a zero. For a dot product to equal zero, we must have an equal number of `1` and `-1` terms to cancel out. Each `-1` term is composed of `(1,-1)` or `(-1,1)`. So the parity of the number of `-1` that occur is fixed according to `n`. If the first and last elements of `A` have different signs, we change the parity, so this is impossible.

So we get

```
c(n) = a(n)/2 if n is odd, else a(n)/2 + C(n,n/2)^2

p(n) = c(n) / 8^n

```

which gives the above formula (re-indexing with `i' = i/2`).

**Update:** Here is a faster version using the same formula:

```
from time import*
from itertools import*

def main():
    time_limit=time()+10

    binoms=[1]
    cb2s=[1]
    cb=1

    for n in count(1):
        if n&1:
            binoms=[a+b for a,b in zip([0]+binoms,binoms)]
        else:
            binoms=[a+b for a,b in zip([0]+binoms,binoms+[binoms[-1]])]
            cb=(cb<<2)-(cb+cb)/(n/2)
            cb2s.append(cb*cb)

        numer=0
        for i in xrange(n/2+1):
            t=cb2s[i]*binoms[min(2*i,n-2*i)]
            t<<=2*(n-2*i)
            numer+=t
        if not n&1:
            numer+=t
        e=(numer&-numer).bit_length()-1
        numer>>=e
        denom=1<<(3*n-e)

        if time()>time_limit:
            break

        print("%d %d/%d"%(n,numer,denom))

main()

```

Optimisations implemented:

* inline function `p(n)`
* use recurrence for binomial coefficients `C(n,k)` with `k <= n/2`
* use recurrence for central binomial coefficients

# Answer
> 3 votes
# Explication of Min\_25's formula

Min\_25 posted a great proof but it took a while to follow. This is a bit of explanation to fill in between the lines.

a(n, m) represents the number of ways to choose A such that A\[i\] = A\[i+1\] m times. The formula for a(n,m) is equivalent to a(n,m) = {2 * (n choose m) for n-m even; 0 for n-m odd.} Only one parity is allowed because A\[i\] != A\[i+1\] must occur an even number of times so that A\[0\] = A\[n\]. The factor of 2 is due to the initial choice A\[0\] = 1 or A\[0\] = -1.

Once the number of (A\[i\] != A\[i+1\]) is fixed to be q (named i in the c(n) formula), it separates into two 1D random walks of length q and n-q. b(m) is the number of ways to take a one-dimensional random walk of m steps that ends at the same place it started, and has 25% chance of moving left, 50% chance of staying still, and 25% chance of moving right. A more obvious way to state the generating function is \[x^m\](1 + 2x + x^2)^n, where 1, 2x and x^2 represent left, no move, and right respectively. But then 1+2x+x^2 = (x+1)^2.

# Answer
> 2 votes
# C++

Just a port of the (excellent) Python answer by Mitch Schwartz. The primary difference is that I used `2` to represent `-1` for the `a` variable and did something similar for `b`, which allowed me to use an array. Using Intel C++ with `-O3`, I got `N=141`! My first version got `N=140`.

This uses Boost. I tried a parallel version but ran into some trouble.

```
#include <boost/multiprecision/gmp.hpp>
#include <boost/typeof/typeof.hpp>
#include <boost/rational.hpp>
#include <boost/chrono.hpp>
#include <boost/array.hpp>
#include <iostream>
#include <utility>
#include <map>

typedef boost::multiprecision::mpz_int integer;
typedef boost::array<boost::array<std::map<int, std::map<int, integer> >, 3>, 2> array;
typedef boost::rational<integer> rational;

int main() {
    BOOST_AUTO(T, boost::chrono::high_resolution_clock::now());

    int N = 1;
    integer n = 1;
    array* Y = new array, *X = NULL;
    (*Y)[1][0][0][0] = 1;
    (*Y)[1][1][1][0] = 1;

    while (boost::chrono::high_resolution_clock::now() < T+boost::chrono::seconds(10)) {
        std::cout << N << " " << rational(n, boost::multiprecision::pow(integer(8), N)/4) << std::endl;
        ++N;
        delete X;
        X = Y;
        Y = new array;
        n = 0;

        for (int a=0; a<2; ++a)
            for (int b=0; b<3; ++b)
                for (BOOST_AUTO(s, (*X)[a][b].begin()); s != (*X)[a][b].end(); ++s)
                    for (BOOST_AUTO(t, s->second.begin()); t != s->second.end(); ++t) {
                        integer c = t->second;
                        int d = b&2 ? -1 : b, e = a == 0 ? -1 : a;

                        if (s->first == -1 && t->first+d+e == 0) n += c;
                        (*Y)[a][1][s->first+1][t->first+d] += c;

                        if (s->first == 1 && t->first-d+e == 0) n += c;
                        (*Y)[a][1][s->first-1][t->first-d] += c;

                        if (s->first == 1 && t->first+d-e == 0) n += c;
                        (*Y)[a][2][s->first-1][t->first+d] += c;

                        if (s->first == -1 && t->first-d-e == 0) n += c;
                        (*Y)[a][2][s->first+1][t->first-d] += c;

                        c *= 2;

                        if (s->first == 0 && t->first+d == 0) n += c;
                        (*Y)[a][0][s->first][t->first+d] += c;

                        if (s->first == 0 && t->first-d == 0) n += c;
                        (*Y)[a][0][s->first][t->first-d] += c;
                    }
    }

    delete X;
    delete Y;
}

```

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


title: Schrödinger's Laser

text:
# Question
Title: Schrödinger's Laser
Fed up with experimenting on tiny domestic animals, Nobel prize-winning Erwin Schrödinger has decided to find the nearest laser and shoot it at things instead. Because... science!

# Description

You will be given two points that the laser passes through and the size of a laser beam, and you must determine where the laser beam *must* have gone, *could* have gone, and *could not* have gone.

The laser beam can be horizontal, vertical, or diagonal. For a size 1 laser beam, they look like this respectively:

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

```

The diagonal laser beam can also be flipped. Size 2 laser beams look like this:

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

```

In general, to get a laser beam of size (n), simply take the laser beam of size (n-1) and add a laser beam of size (1) on both sides. As a final example, here are all possible laser beams of size 3, shown on the same "board":

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

```

This "board" will always have dimensions of 20x20 (in characters).

# Input

Your program will be given five integers as input. They are, in order, x1, y1, x2, y2, and the size of the laser beam. They must be taken exactly in that order. If you wish, you may take the ordered (x, y) pairs as an array, tuple, list, or other built-in data type that stores two values.

Both of the two points given as input will be within the board, and they are guaranteed to be distinct (i.e. the two points will never be the same). The size of the laser beam is bound to `1 ≤ size < 20`. There will always be at least one possible laser beam that passes through both of the points.

# Output

Your program must output a 20x20 grid of the following characters:

* `#` if every possible laser beam that passes through the two points also passes through this point.
* `.` if there is no laser beam that passes through the two points and this point.
* `?` if some, but not all, of the possible laser beams pass through this point.
* `X` if this is one of the two original input points (this overrides the `#`).

# Test cases

7, 7, 11, 3, 1

```
..............#.....
.............#......
............#.......
...........X........
..........#.........
.........#..........
........#...........
.......X............
......#.............
.....#..............
....#...............
...#................
..#.................
.#..................
#...................
....................
....................
....................
....................
....................

```

18, 18, 1, 1, 2

```
#??.................
?X??................
??#??...............
.??#??..............
..??#??.............
...??#??............
....??#??...........
.....??#??..........
......??#??.........
.......??#??........
........??#??.......
.........??#??......
..........??#??.....
...........??#??....
............??#??...
.............??#??..
..............??#??.
...............??#??
................??X?
.................??#

```

10, 10, 11, 10, 3

```
?????..????????..???
??????.????????.????
????????????????????
????????????????????
.???????????????????
..??????????????????
????????????????????
????????????????????
????????????????????
????????????????????
??????????XX????????
????????????????????
????????????????????
????????????????????
????????????????????
..??????????????????
.???????????????????
????????????????????
????????????????????
??????.????????.????

```

3, 3, 8, 10, 4

```
??????????..........
??????????..........
??????????..........
???X??????..........
???##?????..........
???###????..........
????###????.........
.????###????........
..????###????.......
..?????##?????......
..??????X??????.....
..??????????????....
..???????????????...
..????????????????..
..?????????????????.
..??????????????????
..??????????????????
..????????.?????????
..????????..????????
..????????...???????

```

The test cases were generated with the following Ruby script, located inside a Stack Snippet to conserve vertical space.

```
/*

#!/usr/bin/ruby

$w = $h = 20

class Point
    attr_reader :x, :y
    def initialize x, y
        @x = x
        @y = y
    end
    def inspect
        "(#{@x}, #{@y})"
    end
    def == p
        @x == p.x && @y == p.y
    end
    alias eql? ==
    def hash
        @x * $h + @y
    end
    def valid?
        @x >= 0 && @y >= 0 && @x < $w && @y < $h
    end
end

module Angle
    HORIZONTAL = Point.new(1, 0)
    VERTICAL = Point.new(0, 1)
    DIAG1 = Point.new(1, 1)
    DIAG2 = Point.new(1, -1)
end

def line_points point, angle, size
    points = [point]

    while points[-1].valid?
        points.push Point.new(points[-1].x + angle.x, points[-1].y + angle.y)
    end
    points.pop
    while points[0].valid?
        points.unshift Point.new(points[0].x - angle.x, points[0].y - angle.y)
    end
    points.shift

    if size == 1
        points
    elsif size > 1
        a2 = case angle
            when Angle::HORIZONTAL then Angle::VERTICAL
            when Angle::VERTICAL then Angle::HORIZONTAL
            else Angle::VERTICAL  # HORIZONTAL also works
        end
        (size-1).times do |n|
            np1 = Point.new(point.x + a2.x*(n+1), point.y + a2.y*(n+1))
            np2 = Point.new(point.x - a2.x*(n+1), point.y - a2.y*(n+1))
            points.concat line_points np1, angle, 1 if np1.valid?
            points.concat line_points np2, angle, 1 if np2.valid?
        end
        points
    else
        throw 'something is very wrong'
    end
end

def generate_grid x1, y1, x2, y2, size
    p1 = Point.new(x1, y1)
    p2 = Point.new(x2, y2)
    lasers = []
    points = [Point.new((p1.x + p2.x) / 2, (p1.y + p2.y) / 2)]  # midpoint
    while points.length > 0
        point = points.pop
        new_lasers = Angle.constants
            .map{|angle| line_points point, Angle.const_get(angle), size }
            .select {|laser| laser.include?(p1) && laser.include?(p2) } -
            lasers
        if new_lasers.length > 0
            lasers.concat new_lasers
            points.push Point.new(point.x+1, point.y) if point.x+1 < $w
            points.push Point.new(point.x, point.y+1) if point.y+1 < $h
            points.push Point.new(point.x-1, point.y) if point.x-1 > 0
            points.push Point.new(point.x, point.y-1) if point.y-1 > 0
        end
    end
    grid = Array.new($h) { ?. * $w }
    lasers.each do |laser|
        laser.each do |point|
            grid[point.y][point.x] = ??
        end
    end
    lasers.reduce(:&).each do |point|
        grid[point.y][point.x] = ?#
    end
    grid[p1.y][p1.x] = 'X'
    grid[p2.y][p2.x] = 'X'
    grid
end

testcases = [
    [7, 7, 11, 3, 1],
    [18, 18, 1, 1, 2],
    [10, 10, 11, 10, 3],
    [3, 3, 8, 10, 4]
]

testcases.each do |test|
    puts test * ', '
    puts
    puts generate_grid(*test).map{|line| '    ' + line }
    puts
end

*/
```

# Rules

* Your program must be able to solve each of the test cases in under 30 seconds (on a reasonable machine). This is more of a sanity check, as my test Ruby program solved all of the test cases near-instantaneously.
* This is , so the shortest solution wins.

# Answer
> 5 votes
# C, ~~291~~ ~~280~~ ~~277~~ 265 bytes

```
x,y,A,C,B,D,a,c,b,d,w,s,t;T(i){return abs(i)<2*w-1;}U(j,k){s+=T(j-k)*T(j)*T(k);t*=T(j-k)*j*k<1;}main(){for(scanf("%i%i%i%i%i",&a,&b,&c,&d,&w);y<20;y+=!x)s=0,t=1,U(A=a-x,C=c-x),U(B=b-y,D=d-y),U(A-B,C-D),U(A+B,C+D),putchar((x=++x%21)?".?#x"[!!s+t+(!A*!B+!C*!D)]:10);}

```

Can be compiled/run using:

*gcc laser.c -o laser && echo "10 10 11 10 3" | ./laser*

Below, the same code with whitespace and explanatory comments:

```
// Integers...
x,y,A,C,B,D,a,c,b,d,w,s,t;

// Is true if i is in range (of something)
T(i){return abs(i)<2*w-1;}

// Tests if lasers (horizontal, vertical, diagonal, etc) can/must exist at this point
// T(j-k) == 0 iff the laser of this direction can exist
// s += 1 iff this laser direction can pass through this point
// t *= 1 iff this laser direction must pass through this point
U(j,k){
    s+=T(j-k)*T(j)*T(k);
    t*=T(j-k)*j*k<1;
}

main(){
    // Read input; p0=(a,b), p1=(c,d)
    for(scanf("%i%i%i%i%i",&a,&b,&c,&d,&w); y<20; y+=!x)

        // A, B, C and D represent delta-x and delta-y for each points
        // e.g.: if we're processing (2,3), and p0=(4,5), A=4-2, B=5-3
        // s != 0 iff (x,y) can have some laser through it
        // t == 1 iff all lasers pass through (x,y)
        // (!A*!B+!C*!D) == 1 iff (x,y) is either p0 or p1
        s=0,t=1,U(A=a-x,C=c-x),U(B=b-y,D=d-y),U(A-B,C-D),U(A+B,C+D),
        putchar((x=++x%21)?".?#x"[!!s+t+(!A*!B+!C*!D)]:10);
}

```

# Answer
> 4 votes
# C, 302 bytes

```
b[400],x,y,s,t,w,d,e,g,k;f(u,v){d=u*x+v*y;e=u*s+v*t;if(e<d)k=e,e=d,d=k;for(k=0;k<400&d+w>e;++k)g=k%20*u+k/20*v,b[k]|=g>e-w&g<d+w|(g<d|g>e)*2;}main(){scanf("%d%d%d%d%d",&x,&y,&s,&t,&w);w=2*w-1;f(1,0);f(0,1);f(1,1);f(1,-1);b[y*20+x]=4;b[t*20+s]=4;for(k=0;k<400;)putchar(".#.?X"[b[k]]),++k%20?0:puts("");}

```

Input is taken from stdin, reading the 5 numbers in the defined order.

Before final size reduction step:

```
#include <stdio.h>
#include <stdlib.h>

int b[400], x, y, s, t, w, d, e, g, k;

void f(int u, int v) {
  d = u * x + v * y;
  e = u * s + v * t;
  if (e < d) k = e, e = d, d = k;
  if (d + w > e) {
    for (k = 0; k < 400; ++k) {
      g = u * (k % 20) + v * (k / 20);
      if (g > e - w && g < d + w) b[k] |= 1;
      if (g < d || g > e) b[k] |= 2;
    }
  }
}

int main() {
  scanf("%d%d%d%d%d", &x, &y, &s, &t, &w);
  w = 2 * w - 1;
  f(1, 0); f(0, 1); f(1, 1); f(1, -1);
  b[y * 20 + x] = 4;
  b[t * 20 + s] = 4;
  for (k = 0; k < 400; ) {
     putchar(".#.?X"[b[k]]);
     ++k % 20 ? 0 : puts("");
  }
}

```

Some explanation of key steps:

* Array `b` holds the state/result. Bit 0 will be set for all pixels that can be reached by a beam. Bit 1 will be set for all pixels that are **not** covered by all beams.
* Function `f` is called for all 4 directions (vertical, horizontal, both diagonals). Its arguments specify the normal vector of the direction.
* In function `f`:
    + The distance of both input points relative to the direction is calculated (`d` and `e`) as the dot product of the point with the normal vector passed in.
    + The distances are swapped if necessary so that `d` is always less than or equal to `e`.
    + If the difference between `d` and `e` is larger than the width of the beam, no beams are possible in this direction.
    + Otherwise, loop over all pixels. Set bit 0 if the pixel is reachable by any beam, and bit 1 if it is not covered by all beams.
* Mark the two input points with value 4. Since we used bits 0 and 1 to track the state, which results in values 0 to 3, this is the smallest unused value.
* Loop over the pixels in `b`, and convert the values in the range 0 to 4 to their corresponding character while printing them out.

---
Tags: code-golf
---


# Question
Title: Deciding if x-y is 0 or negative without using conditionals
So,

My friend has come up with this interestng question, that is, given two numbers `x` and `y` deciding whether their difference: `x-y`is 0 or less without using any conditionals. The code should return 0 if they are 0 or less, or the result of the subtraction otherwise.

My attempt (In Pseudo-Java):

```
try {
Math.log(x-y);
} catch(Math.Error e) {
return 0; }

return x-y;

```

However, I have a feeling that Java exception handling or log method may use conditionals at some point, which in a way would be cheating.

Thoughts? :D

# Answer
> 3 votes
Use something like this, assuming the integer type is signed and has 32 bits:

```
~((x-y) >> 31) & (x - y)

```

this shifts the sign bit of the difference right by 31 places, generating either 0 if x - y is positive or -1 if the result is negative. This inverted is anded with x - y to get 0 if x - y is negative, x - y otherwise.

# Answer
> 3 votes
There is a common misconception that comparison operators (e.g., `>` or `<`) somehow involve conditionals.

For most if not all architectures, this is not true. On x86, CMP sets the sign flag simply to most significant bit of the difference of `x` and `y`, so no conditionals are involved.

In C, Python and many other languages (but, notably, not Java), you can use

```
(x > y) * (x - y)

```

which will be **x - y = 1 * (x - y)** if **x \> y** and **0 = 0 * (x - y)** if **x ≤ y**.

---
Tags: math
---


title: Probabilities - how high can you go?

text:
# Question
Title: Probabilities - how high can you go?
I previously asked a question for how to compute a probability quickly and accurately. However, evidently it was too easy as a closed form solution was given! Here is a more difficult version.

This task is about writing code to compute a probability exactly *and quickly*. The output should be a precise probability written as a fraction in its most reduced form. That is it should never output `4/8` but rather `1/2`.

For some positive integer `n`, consider a uniformly random string of 1s and -1s of length `n` and call it A. Now concatenate to `A` a copy of itself. That is `A[1] = A[n+1]` if indexing from 1, `A[2] = A[n+2]` and so on. `A` now has length `2n`. Now also consider a second random string of length `n` whose first `n` values are -1, 0, or 1 with probability 1/4,1/2, 1/4 each and call it B.

Now consider the inner product of `B` with `A[1+j,...,n+j]` for different `j =0,1,2,...`.

For example, consider `n=3`. Possible values for `A` and `B` could be `A = [-1,1,1,-1,...]` and `B=[0,1,-1]`. In this case the first two inner products are `0` and `2`.

**Task**

For each `j`, starting with `j=1`, your code should output the probability that all the first `j+1` inner products are zero for every `n=j,...,50`.

Copying the table produced by Martin Büttner for `j=1` we have the following sample results.

```
n   P(n)
1   1/2
2   3/8
3   7/32
4   89/512
5   269/2048
6   903/8192
7   3035/32768
8   169801/2097152

```

**Score**

Your score is the largest `j` your code completes in 1 minute on my computer. To clarify a little, each `j` gets one minute. Note that the dynamic programming code in the previous linked question will do this easily for `j=1`.

**Tie breaker**

If two entries get the same `j` score then the winning entry will be the one that gets to the highest `n` in one minute on my machine for that `j`. If the two best entries are equal on this criterion too then the winner will be the answer submitted first.

**Languages and libraries**

You can use any freely available language and libraries you like. I must be able to run your code so please include a full explanation for how to run/compile your code in linux if at all possible.

**My Machine** The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code.

**Winning entries**

* `j=2` in **Python** by Mitch Schwartz.
* `j=2` in **Python** by feersum. Currently the fastest entry.

# Answer
> 3 votes
# Python 2, j=2

I tried to find a sort of 'closed form' for j=2. Perhaps I could make a MathJax image of it, although it would be really ugly with all the index fiddling. I wrote this unoptimized code only to test the formula. It takes about 1 second to complete. The results match with Mitch Schwartz's code.

```
ch = lambda n, k: n>=k>=0 and fac[n]/fac[k]/fac[n-k]
W = lambda l, d: ch(2*l, l+d)
P = lambda n, p: n==0 or ch(n-1, p-1)
ir = lambda a,b: xrange(a,b+1)

N = 50
fac = [1]
for i in ir(1,4*N): fac += [i * fac[-1]]

for n in ir(2, N):
    s = 0
    for i in ir(0,n+1):
     for j in ir(0,min(i,n+1-i)):
      for k in ir(0,n+i%2-i-j):
       t=(2-(k==0))*W(n+i%2-i-j,k)*W(i-(j+i%2),k)*W(j,k)**2*P(i,j+i%2)*P(n+1-i,j+1-i%2)
       s+=t
    denp = 3 * n - 1
    while denp and not s&1: denp -= 1; s>>=1
    print n, '%d/%d'%(s,1<<denp)

```

Consider a sequence where the ith member is `e` if A\[i\] == A\[i+1\] or `n` if A\[i\] != A\[i+1\]. `i` in the program is the number of `n`s. If `i` is even, the sequence must begin in and end with `e`. If `i` is odd, the sequence must begin and end with `n`. Sequences are further classified by the number of runs of consecutive `e`s or `n`s. There are `j` \+ 1 of one and `j` of the other.

When the random walk idea is extended to 3 dimensions, there is an unfortunate problem that there are 4 possible directions to walk in (one for each of `ee`,`en`,`ne`, or `nn`) which means they are not linearly dependent. So the `k` index sums over the number of steps taken in one of the directions (1, 1, 1). Then there will be an exact number of steps which must taken in the other 3 directions to cancel it.

P(n,p) gives the number of ordered partitions of n objects into p parts. W(l,d) gives the number of ways for a random walk of `l` steps to travel a distance of exactly `d`. As before there is 1 chance to move left, 1 chance to move right and 2 to stay put.

# Answer
> 3 votes
## Python, j=2

The dynamic programming approach for `j = 1` in my answer to the previous question does not need many modifications to work for higher `j`, but gets slow quickly. Table for reference:

```
n   p(n)

2   3/8
3   11/64
4   71/512
5   323/4096
6   501/8192
7   2927/65536
8   76519/2097152
9   490655/16777216
10  207313/8388608

```

And the code:

```
from time import*
from fractions import*
from collections import*

def main():
    N_MAX=50

    T=time()

    n=2
    Y=defaultdict(lambda:0)
    numer=0

    for a1 in [1]:
        for b1 in (1,0):
            for a2 in (1,-1):
                for b2 in (1,0,0,-1):
                    if not a1*b1+a2*b2 and not a2*b1+a1*b2:
                        numer+=1
                    Y[(a1,a2,b1,b2,a1*b1+a2*b2,a2*b1,0)]+=1

    thresh=N_MAX-1

    while time() <= T+60:
        print('%d %s'%(n,Fraction(numer,8**n/4)))

        if thresh<2:
            print('reached N_MAX with %.2f seconds remaining'%(T+60-time()))
            return

        n+=1
        X=Y
        Y=defaultdict(lambda:0)
        numer=0

        for a1,a2,b1,b2,s,t,u in X:
            if not ( abs(s)<thresh and abs(t)<thresh+1 and abs(u)<thresh+2 ):
                continue

            c=X[(a1,a2,b1,b2,s,t,u)]

            # 1,1

            if not s+1 and not t+b2+a1 and not u+b1+a1*b2+a2: numer+=c
            Y[(a1,a2,b2,1,s+1,t+b2,u+b1)]+=c

            # -1,1

            if not s-1 and not t-b2+a1 and not u-b1+a1*b2+a2: numer+=c
            Y[(a1,a2,b2,1,s-1,t-b2,u-b1)]+=c

            # 1,-1

            if not s-1 and not t+b2-a1 and not u+b1+a1*b2-a2: numer+=c
            Y[(a1,a2,b2,-1,s-1,t+b2,u+b1)]+=c

            # -1,-1

            if not s+1 and not t-b2-a1 and not u-b1+a1*b2-a2: numer+=c
            Y[(a1,a2,b2,-1,s+1,t-b2,u-b1)]+=c

            # 1,0

            c+=c

            if not s and not t+b2 and not u+b1+a1*b2: numer+=c
            Y[(a1,a2,b2,0,s,t+b2,u+b1)]+=c

            # -1,0

            if not s and not t-b2 and not u-b1+a1*b2: numer+=c
            Y[(a1,a2,b2,0,s,t-b2,u-b1)]+=c

        thresh-=1

main()

```

Here we are keeping track of the first two elements of `A`, the last two elements of `B` (where `b2` is the last element), and the inner products of `(A[:n], B)`, `(A[1:n], B[:-1])`, and `(A[2:n], B[:-2])`.

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


title: Compute the Join and Meet of Partitions

text:
# Question
Title: Compute the Join and Meet of Partitions
# Background

In this challenge, a *partition* of a set `S` means a collection of nonempty subsets of `S`, which are mutually disjoint and whose union is `S`. We say that a partition `p` is *finer* than another partition `q` (and `q` is *coarser* than `p`), if it can be obtained from `q` by splitting some of its sets into smaller pieces. The *join* (or *least upper bound*) of two partitions is the finest partition which is coarser than both of them, and their *meet* (or *greatest lower bound*) is the coarsest partition which is finer than both of them. See the Wikipedia pages on partitions and lattices for more information and nice pictures.

One way to compute the join and meet of two partitions `p` and `q` is the following. Form a graph whose vertex set is `S`, and add an edge `a - b` for each pair `a, b` that are in the same set in either `p` or `q`. Then the join of `p` and `q` contains the connected components of this graph. The meet of `p` and `q` consists of all nonempty intersections of a set in `p` with a set in `q`.

For example, consider the partitions `[[0,1],[2,3]]` and `[[0,1,2],[3]]` of `S = [0,1,2,3]`. The graph mentioned above is

```
0-1
|/
2-3

```

where the edge `2 - 3` comes from the first partition (`2` and `3` are in the same set), and the triangle comes from the second one (`0`, `1` and `2` are in the same set). This means that the join is `[[0,1,2,3]]`. The intersections of all the sets in the partitions are

```
[0,1] ∩ [0,1,2] = [0,1],
[0,1] ∩ [3]     = [],
[2,3] ∩ [0,1,2] = [2],
[2,3] ∩ [3]     = [3]

```

Removing the empty set, we have the meet `[[0,1],[2],[3]]`.

# Input

Two partitions of a finite set of integers, given as arrays of arrays.

# Output

The join and meet of the input partitions, in this order.

# Test Cases

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

```

# Detailed Rules

The order of the sets in the output partitions, and of the numbers in those sets, does not matter. You can assume that the inputs are correct, that is, they contain the same numbers, each exactly once, and no empty arrays. Note that the numbers do not necessarily form an interval (the third test case contains no `5`).

You can write either a full program or a function. You can also write two programs/functions in the same language, one of which computes the join and other the meet, but there's a bonus of **-10 bytes** if you don't choose this option. The shortest byte count wins, and standard loopholes are disallowed.

# Answer
> 7 votes
# CJam, 32 - 10 = 22

```
q_~{_{T&},:U-U:+a+}fTp~m*::&La-p

```

`::&` is newer than this question.

# CJam, 36 - 10 = 26

```
q_~{:T;_{T&},:U-U:+a+}/p~m*{~&}%La-p

```

Input:

```
[[0] [1] [2 3 4 7 6]]
[[2 3] [4 7] [6] [1 0]]

```

Output:

```
[[2 3 4 7 6] [0 1]]
[[0] [1] [2 3] [4 7] [6]]

```

### Explanation

```
q                 " Read the input. ";
_~                " Evaluate a copy. ";
{:T;              " For each list T in the second partition: ";
    _{T&},        " Select all lists in the first partition which share items with T. ";
    :U-           " Save to U and remove them from the first partition. ";
    U:+a+         " Append the union of U to the first partition. ";
}/
p                 " Print the meet. ";
~                 " Evaluate another copy. ";
m*                " Get the Cartesian product. ";
{~&}%             " Get the intersections of each pair of lists. ";
La-               " Remove empty lists. ";
p                 " Print. ";

```

# Answer
> 1 votes
## Java: 2014 (-10) = 2004 bytes

```
import java.util.*;public class A{static List<List<Set<Integer>>>b(Integer[][]c,Integer[][]d){Integer[][]e;Integer[][]f;if(c.length<=d.length){e=c;f=d;}else{e=d;f=c;}
Q g=h(e);List<List<Set<Integer>>>i=new ArrayList<>();i.add(j(f,g));i.add(k(f,g));System.out.println(i.toString());return i;}
static List<Set<Integer>>j(Integer[][]l,Q m){for(Integer[]o:l){if(o.length>1){n(m,o);}}
return p(m);}
static List<Set<Integer>>k(Integer[][]q,Q r){List<Set<Integer>>s=new ArrayList<>();for(Integer[]t:q){for(Set<Integer>u:v(r,t).values()){s.add(u);}}
return s;}
static Map<R,Set<Integer>>v(Q w,Integer[]x){Map<R,Set<Integer>>y=new HashMap<>();for(Integer z:x){R a=w.getSubset(z);if(!y.containsKey(a)){y.put(a,new HashSet<>());}
y.get(a).add(z);}
return y;}
static List<Set<Integer>>p(Q partition){partition.b();List<Set<Integer>>c=new ArrayList<>();for(R d:partition.y){Set<Integer>e=new HashSet<>();R f=d;while(f!=null&&!f.g){e.addAll(f.t);f.g=true;f=f.s;}
if(!e.isEmpty()){c.add(e);}}
return c;}
static void n(Q h,Integer[]i){for(int j:i){R k=h.getSubset(j);for(int l:i){R m=h.getSubset(l);if(k.s==null&&k!=m&&k!=m.s){k.s=m;}}}}
static Q h(Integer[][]n){List<R>o=new ArrayList<>();for(Integer[]p:n){o.add(new R(p));}
return new Q(o);}}
class R{R s;Set<Integer>t;boolean g=false;R(Integer[]u){this.t=Collections.unmodifiableSet(new HashSet<>(Arrays.asList(u)));}
R(Set<Integer>v){this.t=Collections.unmodifiableSet(v);}@Override
public int hashCode(){final int p=31;int r=1;r=p*r+((t==null)?0:t.hashCode());return r;}@Override
public boolean equals(Object x){if(this==x)
return true;if(x==null)
return false;if(getClass()!=x.getClass())
return false;R other=(R)x;if(t==null){if(other.t!=null)
return false;}else if(!t.equals(other.t))
return false;return true;}}
class Q{List<R>y;R getSubset(Integer z){for(R a:y){if(a.t.contains(z)){return a;}}
return null;}
Q(List<R>b){this.y=b;}
void b(){List<R>c=new ArrayList<>();for(int i=0;i<y.size();i++){if(y.get(i).s!=null){c.add(y.get(i));y.remove(i);}}
c.addAll(y);this.y=c;}}

```

Run by calling the b() function with two Integer\[\]\[\].

Using the given inputs, outputs are:

```
[[[1]], [[1]]]
[[[0, 1, 2, 3]], [[0, 1], [2], [3]]]
[[[0, 1], [2, 3, 4, 6, 7]], [[2, 3], [4, 7], [6], [1], [0]]]
[[[0, 1, 2, 3, 4, 5, 6]], [[3], [0], [6], [4], [2], [5], [1]]]

```

# Answer
> 0 votes
# Mathematica, 127 - 10 = 117

Not fully golfed.

```
{ConnectedComponents@Graph@Union@##,FindClique[Graph@Intersection@##,Infinity,All]}&@@(Union@@(Rule@@@Tuples[#,2]&/@#)&/@{##})&

```

---
Tags: code-golf, combinatorics, array, set-partitions
---


title: Print Input Sideways

text:
# Question
Title: Print Input Sideways
Your program must take an alpha/numeric input string and print it sideways (rotated 90 degrees clockwise). So for example, HI, would become:

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

#####

```

**Rules:**

The shortest code wins. For the sake of objectivity this will be the standard font. The input still only has to be alpha-numeric. Capitalization does not matter.

# Answer
## C 550 503

```
#define L putchar('\n');
c,b,i,j,m[]={0xe9d72e,0x10fd25,0x9ace29,0x556b5,0x4fd184,0x16ad6bd,0x156ae,0xc5e10,0x556aa,0x756a8,0,0,0,0,0,0,0,0xfa51e0,0xaad7e0,0x118c5c0,0xe8c7e0,0x15ad7e0,0x14a53e0,0x16ac5c0,0x1f213e0,0xf8000,0x1e08440,0x11513e0,0x1087e0,0x1f4111f,0x1f223e0,0xe8c62e,0x8a53e0,0xd9462e,0x5d29f,0x12ad6a9,0x1087e10,0xf043e,0x18304d8,0x1c1f07c,0xd909b,0xf14bd,0xcd6b3};main(){for(;;){c=getchar();c=c<48?11:c>90?c-80:c-48;b=0;for(i=0;i<5;i++){for(j=0;j<5;j++)putchar(m[c]&(1<<b++)?35:32);L}L}}

```

(Incorporated BrainSteel's tips and optimized a bit more)

Here's the non-obfuscated code:

```
#include <stdio.h>

int map[]
={
    // 0 - 9
    0xe9d72e, 0x10fd25, 0x9ace29, 0x556b5, 0x4fd184, 0x16ad6bd, 0x156ae,     0xc5e10, 0x556aa, 0x756a8,
    // Other stuff
    0,0,0,0,0,0,0,
    // A - Z
    0xfa51e0, 0xaad7e0, 0x118c5c0, 0xe8c7e0, 0x15ad7e0, 0x14a53e0, 0x16ac5c0, 0x1f213e0, 0xf8000, 0x1e08440, 0x11513e0, 0x1087e0, 0x1f4111f, 0x1f223e0, 0xe8c62e, 0x8a53e0, 0xd9462e, 0x5d29f, 0x12ad6a9, 0x1087e10, 0xf043e, 0x18304d8, 0x1c1f07c, 0xd909b, 0xf14bd, 0xcd6b3
};

int main()
{
    for(;;)
    {
        int c = getchar();
        c = c < '0' ? 11 : c > 'Z' ? c - ('0' + 'a' - 'A') : c - '0';
        int bit = 0;
        for(int i=0; i<5; i++)
        {
            for(int j=0; j<5; j++)
                putchar(map[c] & (1 << bit++) ? '#' : ' ');
            putchar('\n');
        }
        putchar('\n');
    }
}

```

I've encoded the characters the following way: I wrote a C "script" that takes a 5x5 area of characters from STDIN, changes "space" to 0 and anything else to 1, rotates the whole area by 90 degrees and finally puts every cell of the area in one bit of a 32-bit integer (the hex numbers in 'map'). That's how the "script" looks like:

```
#include <stdio.h>

int main()
{
    int array[5][5];
    for(int i=0; i<5; i++)
    {
        for(int j=0; j<5; j++)
            array[j][i] = (getchar() != ' ');
        getchar();
    }
    int res = 0;
    int bit = 0;
    for(int j=0; j<5; j++)
    {
        for(int i=0; i<5; i++)
            res = res | (array[j][4-i] << bit++);
    }
    printf("0x%x\n", res);
    return 0;
}

```

I am pretty sure there are FAR smaller programs possible (for example in Perl or Ruby), but this is the best I can come up with right know.
> 10 votes

# Answer
# Mathematica ~~120~~ 119

This should work.

```
g@t_:=GraphicsGrid[Transpose@Reverse@ImageData@Binarize@Rasterize@Style[t,{12,FontFamily->"Pixelette"}] /.{1 ->" ",0-> "#"}]

```

The function `g` takes the input text, converts to Pixelette font, rasterizes it, flips it (Reverse and Transpose), examines the array of `1`s and `0`s, and outputs the ASCII text (as text, not as an image or graphic). `GraphicsArray` conveniently displays the ASCII output in a table.

I used "HELLO" as the input because each letter in "HI" is horizontally and vertically symmetric, hence HI is a bad choice to use for testing.

```
g["HELLO"]

```
> 7 votes

# Answer
# Python 2, ~~376~~ ~~364~~ ~~361~~ 315

This is my first attempt at code golf.

The font is encoded as a single large integer in which each character takes up 25 bits - 5 columns of 5 pixels each. It reads its input from stdin as a Python string (including the quotes).

Updated three times to reduce size. The third update incorporates changes suggested by Sp3000.

```
for c in input().upper():
 c=ord(c)-48
 if c>9:c-=7
 s,l='',int('17vhur2t4cze6tuj2ja3e1i8luj1b1frxdf9pg8dxjw7ian4517nliqqn8tdogkck15rn5n6vz3l5zf1u10cv5trc4n49xtznzx7egrjllrn8e1nlgyjp3z481ffsqmiw3pj3a538wnhwydpp85o9j85kzqxfl3qop50sokgcvwfn2',36)>>25*c
 for i in range(25):
  s+=' #'[l&1];l/=2
  if i%5>3:print s;s=''

```
> 4 votes

# Answer
# C,335

Score excludes whitespace, which is unnecessary and only included for clarity.

In the absence of further info from the OP, I have assumed exactly one blank space is required between characters. If padding is required, backtick (ASCII 96) can be used (not sure how that character will display here.)

After converting to uppercase with `c-c/91*32`, I search the big string for the required character, and set a pointer to the character after it. This makes it easy to handle the variable width font. It also avoids the need to unite the ASCII ranges for letters and numbers.

The font data is contained, column by column, in the big string. As only 5 bits are required, only ASCII codes 95 and over are used. The next code below 90 signals the end of the character.

The program tends to segfault on characters outside the alphanumeric range.

```
char*p,s[99],c,i,j,k;
main(){
  for(scanf("%s",&s);c=s[i];i++){
    p=strchr("A~ee~B_uujCnqqqD_qqnE_uuF_eeGnqu}H_dd_I_JhppoK_djqL_ppM_bdb_N_bd_OnqqnP_eebQnqivR_emrSruuiTaa_aaUoppoVclplcWgxgxgX{dd{YwttoZyuus0nyusn1r_p2ryur3quuj4ljk_5wuum6nuuh7aa}c8juuj9buun",c-c/91*32)+1;
    for(;*p>90;p++)for(k=5;k--;k||puts(""))putchar(*p>>k&1?35:32);
    puts("");
  }
}

```
> 3 votes

# Answer
# Java 8 - 404

First time posting here. This program takes a single argument on the command line. Java 8 is required (Java 7 can be used at a cost of 3 additional characters).

```
class A{public static void main(String[]a){a[0].chars().forEach(c->{String o="";c-=c>57?c>90?87:55:48;for(char d:">AA>09O1009CE90AEE:06:BO0MEEF0>EE20@@GH0:EE:08EE>0?DD?0OEE:0>AAA0OAA>0OEE00ODD00>AEG0O44O0O0000211N0O4:A0O1100O848OO84O0>AA>0ODD80>AB=0ODF909EEB0@@O@@N11N0H616HL3L3LK44K0M55N0CEEI0".substring(c*=5, c+5).toCharArray()){for(d-=48;d>0;d/=2)o+=d%2==1?'#':32;o+="\n";}System.out.println(o);});}}

```

Unobfuscated version:

```
class A {
    public static void main(String[] a) {
        a[0].chars().forEach(
                c -> {
                    String o = "";
                    c -= c > 57 ? c > 90 ? 87 : 55 : 48;
                    for (char d: (">AA>09O1009CE90AEE:06:BO0MEEF0>EE20@@GH0:EE:08EE>0?DD?0"
                            + "OEE:0>AAA0OAA>0OEE00ODD00>AEG0O44O0O0000211N0O4:A0O1100O848O"
                            + "O84O0>AA>0ODD80>AB=0ODF909EEB0@@O@@N11N0H616HL3L3LK44K0M55N0"
                            + "CEEI0").substring(c *= 5, c + 5).toCharArray())
                    {
                        for (d -= 48; d > 0; d /= 2)
                            o += d % 2 == 1 ? ' ' : 32;
                        o += "\n";
                    }
                    System.out.println(o);
                }
        );
    }
}

```

Each row of pixels is encoded in the 5 least significant bits of a byte in the long string, and ASCII '0' is added to make the string contain only printable characters. The code simply translates each character in the input string to an index into the string, iterating through the 5 bytes representing the respective character, and decoding them using the reverse process. There are more compact encodings, but they would be more complex to decode and would probably inflate the code size too much to be worthwhile.
> 1 votes

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


title: Score a game of Kingdom Builder

text:
# Question
Title: Score a game of Kingdom Builder
*I want to try a new form of code golf here. Similar to bonuses, not all parts of the challenge have to be completed, but each answer has to implement a subset of certain size (and there is a core that every answer has to implement). So besides the golfing this challenge also involves choosing a set of features that go well together.*

## The Rules

Kingdom Builder is a board game, played on a (pointy-top) hex grid. The board is made up of four (randomised) quadrants, each of which has 10x10 hex cells (so a full board will be 20x20). For the purposes of this challenge, each hex cell contains either water (`W`), mountain (`M`) a town (`T`), a castle (`C`) or is empty (`.`). So a quadrant could look like

```
. . W . . . . . . .
 . M W W . . . . . .
. M . . W . . . T .
 M M . W . . . . . .
. . M . W W . . . .
 . . . . . W W W W W
. T . . . . . . . .
 . . W . . C . . . .
. . W W . . . . M .
 . . . . . . . M M .

```

The second row will always be offset to the right from the first row. Players `1` to `4` can place up to 40 settlements each on empty cells (following some rules which we will ignore for this challenge). A possible board at the end of the game is the following:

```
3 3 W . . . 4 . 4 . . 2 W . 4 . . 4 . 4
 3 M W W . 1 1 . . 4 2 W . 3 C 4 4 . . 4
3 M 2 2 W 1 1 1 T 3 2 W 4 3 . 1 4 . 4 .
 M M . W 2 2 . . . 2 2 W 3 . 1 1 1 . . .
. 4 M . W W 2 2 2 2 W W 3 . 1 4 . T . .
 . . . . . W W W W W . 3 C 1 . . 2 2 2 2
. T 1 1 1 1 . . 2 . . 4 . . . 2 2 M M M
 4 . W 4 . C 4 4 . . . . . . 2 M M M M M
. 4 W W . . . 4 M . . W . W . 2 2 2 M M
 . . . . . . . M M . . W W . . . . 2 M .
. . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 . 1
 M 3 3 . . . . . . . . 4 . T 2 . 2 4 1 .
M M . C . 4 . 4 . . . . . 1 2 4 2 1 1 .
 M . . 1 . 4 . . . . M M 1 2 . . 2 1 . .
. . . W 1 1 4 1 1 . . . 1 2 . . 2 W W W
 . . 1 1 W 1 T . 1 1 1 1 T . . 2 W . 4 .
. 1 1 W . 3 3 . . . . . . . . 2 W 4 C 3
 C 1 3 3 3 . 3 . 4 . 4 . 4 . . 2 W 1 1 M
4 3 3 4 . M 4 3 . . . . . . . 2 W . . .
 . . . 4 . M M 3 . . 4 4 . 4 . 2 W W . .

```

We'll label the quadrants like

```
1 2
3 4

```

Your task will be to score such a board. There is one core score which is always used, and 8 optional scores, **3** of which are chosen for each game. In the following, I'll describe all 9 scores and use the above setup as an example for how many points each player would get.

<sup>† There are 10 scores in the actual game, but I'll leave out two because no one wants to golf them.</sup>

**The core score.** A player gets **3 points** for each `C`astle they have a settlement next to. *Example scores:* 18, 0, 15, 12.

**The optional scores.**

1. A player gets **1 point** for each horizontal row on which they have at least one settlement.

*Example scores:* 14, 20, 12, 16.
2. For each player, find the horizontal row on which they most of their settlements (pick any in case of a tie). A player gets **2 points** for each settlement on that row.

*Example scores:* 14 (row 16), 8 (row 4, 5 or 6), 28 (row 11), 10 (row 1).
3. A player gets **1 point** for each settlement that is build next to `W`ater.

*Example scores:* 13, 21, 10, 5.
4. A player gets **1 point** for each settlement next to a `M`ountain.

*Example scores:* 4, 12, 8, 4.
5. Count the settlements of each player in each quadrant. Per quadrant, the players with the largest number of settlements get **12 points** each, the players with the second-largest number of settlements get **6 points** each.

*Example scores:* 18 (6 + 0 + 6 + 6), 36 (12 + 12 + 0 + 12), 12 (0 + 0 + 12 + 0), 18 (12 + 6 + 0 + 0).
6. For each player determine the quadrant in which they have the least number of settlements. A player gets **3 points** for each settlement in that quadrant.

*Example scores:* 18 (Quadrant 2), 0 (Quadrant 3), 15 (Quadrant 1 or 2), 27 (Quadrant 3).
7. A player gets **1 point** for each connected group of settlements.

*Example scores:* 7, 5, 6, 29.
8. A player gets **1 point** for every *2* settlements in the player's largest group of connected settlements.

*Example scores:* 4, 10, 8, 2.

## The Challenge

As in the game *you* will choose **3** of the optional scores, and score a given board based on the core score and those three scores. Your code should produce a list of 4 scores. There is one restriction on the choice though: I have grouped the scores into 3 groups, and you are to implement one of each group:

* Implement one of **1 and 2**.
* Implement one of **3, 4, 5 and 6**.
* Implement one of **7 and 8**.

You may write a program or function, taking input via STDIN, command-line argument, prompt or function parameter. You may return the result or print it to STDOUT.

You may choose any convenient 1D or 2D list/string format for the input. You may *not* use a graph with full adjacency information. Here is some good reading on hex grids if you need inspiration.

Your output may also be in any convenient, unambiguous list or string format.

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

## Further Assumptions

You may assume that ...

* ... each player has at least 1 settlement and there are no more than 40 settlements of each player.
* ... each quadrant contains either one town and two castles, or two towns and one castle.
* ... towns and castles are far enough apart, such that no settlement can be adjacent to two of them.

## Test Cases

Still using the above board, here are the individual scores for all possible choices of scoring mechanisms:

```
Chosen Scores      Total Player Scores
1 3 7              52 46 43 62
1 3 8              49 51 45 35
1 4 7              43 37 41 61
1 4 8              40 42 43 34
1 5 7              57 61 45 75
1 5 8              54 66 47 48
1 6 7              57 25 48 84
1 6 8              54 30 50 57
2 3 7              52 34 59 56
2 3 8              49 39 61 29
2 4 7              43 25 57 55
2 4 8              40 30 59 28
2 5 7              57 49 61 69
2 5 8              54 54 63 42
2 6 7              57 13 64 78
2 6 8              54 18 66 51

```

# Answer
> 5 votes
# Python 2, 367 bytes

```
T=range(20)
N=lambda r,c:{(a,b)for a,b in{(r+x/3-1,c+x%3-1+(x/3!=1)*r%2)for x in[0,1,3,5,6,7]}if-1<b<20>a>-1}
def S(B):
 def F(r,c):j=J[r][c]!=i;J[r][c]*=j;j or map(F,*zip(*N(r,c)));return j
 J=map(list,B);X=lambda r,c,x,y:x+y in{B[r][c]+B[a][b]for a,b in N(r,c)};return[sum((i in B[r])+20*(3*X(r,c,"C",i)-~X(r,c,i,"W")-F(r,c))for r in T for c in T)/20for i in"1234"]

```

The program uses scores 1, 3, 7. Input is a list of lists of chars representing each cell. To test the example board easily, we can do:

```
board = """
3 3 W . . . 4 . 4 . . 2 W . 4 . . 4 . 4
 3 M W W . 1 1 . . 4 2 W . 3 C 4 4 . . 4
3 M 2 2 W 1 1 1 T 3 2 W 4 3 . 1 4 . 4 .
 M M . W 2 2 . . . 2 2 W 3 . 1 1 1 . . .
. 4 M . W W 2 2 2 2 W W 3 . 1 4 . T . .
 . . . . . W W W W W . 3 C 1 . . 2 2 2 2
. T 1 1 1 1 . . 2 . . 4 . . . 2 2 M M M
 4 . W 4 . C 4 4 . . . . . . 2 M M M M M
. 4 W W . . . 4 M . . W . W . 2 2 2 M M
 . . . . . . . M M . . W W . . . . 2 M .
. . . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 . 1
 M 3 3 . . . . . . . . 4 . T 2 . 2 4 1 .
M M . C . 4 . 4 . . . . . 1 2 4 2 1 1 .
 M . . 1 . 4 . . . . M M 1 2 . . 2 1 . .
. . . W 1 1 4 1 1 . . . 1 2 . . 2 W W W
 . . 1 1 W 1 T . 1 1 1 1 T . . 2 W . 4 .
. 1 1 W . 3 3 . . . . . . . . 2 W 4 C 3
 C 1 3 3 3 . 3 . 4 . 4 . 4 . . 2 W 1 1 M
4 3 3 4 . M 4 3 . . . . . . . 2 W . . .
 . . . 4 . M M 3 . . 4 4 . 4 . 2 W W . .
"""

board = [row.split() for row in board.strip().split("\n")]
print S(board)

# [52, 46, 43, 62]

```

---

## Handling the hex grid

Since we are on a hex grid, we have to deal with neighbours a little differently. If we use a traditional 2D grid as our representation, then for `(1, 1)` we have:

```
. N N . .       . N N . .                (0, 1), (0, 2)            (-1, 0), (-1, 1)
 N X N . .  ->  N X N . .  -> Neighbours (1, 0), (1, 2) -> Offsets (0, -1), (0, 1)
. N N . .       . N N . .                (2, 1), (2, 2)            (1, 0), (1, 1)

```

On closer inspection, we realise that the offsets depend on the parity of the row you're on. The above example is for odd rows, but on even rows the offsets are

```
(-1, -1), (-1, 0), (0, -1), (0, 1), (1, -1), (1, 0)

```

The only thing that has changed is that the 1st, 2nd, 5th and 6th pairs have had their second coordinate decremented by 1.

The lambda function `N` takes a coordinate pair `(row, col)` and returns all neighbours of the cell within the grid. The inner comprehension generates the above offsets by extracting them from a simple base 3 encoding, incrementing the second coordinate if the row is odd and adds the offsets to the cell in question to give the neighbours. The outer comprehension then filters, leaving just the neighbours that are within the bounds of the grid.

## Ungolfed

```
def neighbours(row, col):
    neighbour_set = set()

    for dr, dc in {(-1,-1), (-1,0), (0,-1), (0,1), (1,-1), (1,0)}:
        neighbour_set.add((row + dr, col + dc + (1 if dr != 0 and row%2 == 1 else 0)))

    return {(r,c) for r,c in neighbour_set if 20>r>-1 and 20>c>-1}

def solve(board):
    def flood_fill(char, row, col):
        # Logic negated in golfed code to save a few bytes
        is_char = (dummy[row][col] == char)
        dummy[row][col] = "" if is_char else dummy[row][col]

        if is_char:
            for neighbour in neighbours(row, col):
                flood_fill(char, *neighbour)

        return is_char

    def neighbour_check(row, col, char1, char2):
        return board[row][col] == char1 and char2 in {board[r][c] for r,c in neighbours(row, col)}

    dummy = [row[:] for row in board] # Need to deep copy for the flood fill
    scores = [0]*4

    for i,char in enumerate("1234"):
        for row in range(20):
            for col in range(20):
                scores[i] += (char in board[row])                        # Score 1
                scores[i] += 20 * 3*neighbour_check(row, col, "C", char) # Core score
                scores[i] += 20 * neighbour_check(row, col, char, "W")   # Score 3
                scores[i] += 20 * flood_fill(char, row, col)             # Score 7

        # Overcounted everything 20 times, divide out
        scores[i] /= 20

    return scores

```

# Answer
> 2 votes
# Answer Set Programming, 629 bytes

```
d(X,Y):-b(X,Y,_).p(1;2;3;4).n(X,Y,(((X-2;X+2),Y);((X-1;X+1),(Y-1;Y+1)))):-d(X,Y).n(X,Y,I,J):-n(X,Y,(I,J));d(I,J).t(X,Y,P):-n(X,Y,I,J);b(I,J,P).s(c,P,S*3):-S={t(X,Y,P):b(X,Y,"C")};p(P).s(1,P,S*1):-S=#count{r(Y):b(_,Y,P)};p(P).s(3,P,S):-S={b(X,Y,P):t(X,Y,"W")};p(P).o(X,Y,Y+X*100):-d(X,Y).h(P,X,Y,I,J):-o(X,Y,O);o(I,J,Q);O<Q;n(X,Y,I,J);b(X,Y,P);b(I,J,P);p(P).h(P,X,Y,I,J):-o(X,Y,O);o(I,J,Q);O<Q;h(P,X,Y,K,L);n(K,L,I,J);b(I,J,P);p(P).c(P,X,Y):-h(P,X,Y,_,_);not h(P,_,_,X,Y).c(P,X,Y):-{h(P,X,Y,_,_);h(P,_,_,X,Y)}0;b(X,Y,P);p(P).s(7,P,S):-S=#count{c(P,X,Y):c(P,X,Y)};p(P).s(t,P,C+S+T+U):-s(c,P,C);s(1,P,S);s(3,P,T);s(7,P,U).#shows/3.

```

ASP belongs to the logic programming language family, here incarnated by the Potassco framework, in particular Clingo(grounder Gringo + solver Clasp). Because of the paradigm limitation, it can't take given board directly as an output, so a preprocessing of the data is necessary (here performed in python). This preprocessing in not counted in the total byte score.

Its my first code golf, and the objective is more to show a language i love that i never seen before in golf, than really win the game. Moreover, i'm far from an expert in ASP, so many optimizations of the code can certainly be perform for results in less bytes.

## knowledge representation

There is the python code that convert board in atoms :

```
def asp_str(v):
    return ('"' + str(v) + '"') if v not in '1234' else str(v)

with open('board.txt') as fd, open('board.lp', 'w') as fo:
        [fo.write('b('+ str(x) +','+ str(y) +','+ asp_str(v) +').\n')
         for y, line in enumerate(fd)
         for x, v in enumerate(line) if v not in ' .\n'
        ]

```

For example, atoms b (for \__b\__oard) given for the first line of example board are the followings :

```
b(0,0,3).
b(2,0,3).
b(4,0,"W").
b(12,0,4).
b(16,0,4).
b(22,0,2).
b(24,0,"W").
b(28,0,4).
b(34,0,4).
b(38,0,4).

```

Where b(0,0,3) is an atom that describes that player 3 has a settlement at coordinates (0;0).

## ASP solving

There is the ASP code, with many optional scores implemented :

```
% input : b(X,Y,V) with X,Y the coordinates of the V value

domain(X,Y):- b(X,Y,_).
player("1";"2";"3";"4").

% neighbors of X,Y
neighbors(X,Y,((X-2,Y);(X+2,Y);((X-1;X+1),(Y-1;Y+1)))) :- domain(X,Y).
neighbors(X,Y,I,J):- neighbors(X,Y,(I,J)) ; domain(I,J).

% Player is next to X,Y iff has a settlement next to.
next(X,Y,P):- neighbors(X,Y,I,J) ; b(I,J,P).

% SCORES

% Core score : 3 point for each Castle "C" with at least one settlement next to.
score(core,P,S*3):- S={next(X,Y,P): b(X,Y,"C")} ; player(P).

% opt1: 1 point per settled row
score(opt1,P,S*1):- S=#count{row(Y): b(_,Y,P)} ; player(P).

% opt2: 2 point per settlement on the most self-populated row
% first, defines how many settlements have a player on each row
rowcount(P,Y,H):- H=#count{col(X): b(X,Y,P)} ; domain(_,Y) ; player(P).
score(opt2,P,S*2):- S=#max{T: rowcount(P,Y,T)} ; player(P).

% opt3: 1 point for each settlements next to a Water "W".
score(opt3,P,S):- S={b(X,Y,P): next(X,Y,"W")} ; player(P).

% opt4: 1 point for each settlements next to a Mountain "M".
score(opt4,P,S):- S={b(X,Y,P): next(X,Y,"M")} ; player(P).

% opt5:
%later…

% opt6:
%later…

% opt7: 1 point for each connected component of settlement
% first we need each coord X,Y to be orderable.
% then is defined path/5, that is true iff exists a connected component of settlement of player P
%   that links X,Y to I,J
% then is defined the connected component atom that give the smaller coords in each connected component
% then computing the score.
order(X,Y,Y+X*100):- domain(X,Y).
path(P,X,Y,I,J):- order(X,Y,O1) ; order(I,J,O2) ; O1<O2 ; % order
                  neighbors(X,Y,I,J) ; b(X,Y,P) ; b(I,J,P) ; player(P). % path iff next to
path(P,X,Y,I,J):- order(X,Y,O1) ; order(I,J,O2) ; O1<O2 ; % order
                  path(P,X,Y,K,L) ; neighbors(K,L,I,J) ; % path if path to next to
                  b(I,J,P) ; player(P).
concomp(P,X,Y):- path(P,X,Y,_,_) ; not path(P,_,_,X,Y). % at least two settlements in the connected component
concomp(P,X,Y):- 0 { path(P,X,Y,_,_) ; path(P,_,_,X,Y) } 0 ; board(X,Y,P) ; player(P). % concomp of only one settlements
score(opt7,P,S):- S=#count{concomp(P,X,Y): concomp(P,X,Y)} ; player(P).

% opt8: 0.5 point for each settlement in the bigger connected component
%later…

% total score:
score(total,P,C+S1+S2+S3):- score(core,P,C) ; score(opt1,P,S1) ; score(opt3,P,S2) ; score(opt7,P,S3).

#show. # show nothing but the others show statements
#show total_score(P,S): score(total,P,S).
%#show score/3. % scores details

```

This program can be launched with the command:

```
clingo board.lp golf.lp

```

And will find only one solution (its a proof that there is only one way to distribute the points):

```
s(c,1,18) s(c,2,0) s(c,3,15) s(c,4,12) s(1,1,14) s(1,2,20) s(1,3,12) s(1,4,16) s(3,1,13) s(3,2,21) s(3,3,10) s(3,4,5) s(7,1,7) s(7,2,5) s(7,3,6) s(7,4,29) s(t,1,52) s(t,2,46) s(t,3,43) s(t,4,62)

```

Where s(7,3,6) says that player 3 gains 6 points with optional score 7, and s(t,4,62) says that player 4 gains 62 points in total (core + 1 + 3 + 7).

Easy to parse to have a fancy table !

---
Tags: code-golf, game, array, grid, hexagonal-grid
---