title: Lose at tic-tac-toe

text:
# Question
Title: Lose at tic-tac-toe
Write a program that a will play a game of Misère tic-tac-toe. That is, the goal is to force your opponent to take three in a row.

Accept on standard input either an 'X' or an 'O'(the letter, not zero), to determine which side the program will be playing as. Then output a single digit for your move on your turn, and read a single digit on your opponents turn until the game is over (X always goes first). Once a winner is decided, output X or O for who won, or D for a draw. For example, if O gets 3 in a row, X wins.

Assume the board is numbered like so:

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

```

Ideally a solution will be optimal and never lose. Like tic-tac-toe, perfect play should always result in a draw. If the above protocol is adhered to, I can test submissions automatically against a variety of possible strategies.

Winner is shortest code. bonus points if it picks randomly from equally good moves to make it a bit more unpredictable.

# Answer
## Python, 383 chars

```
M=[21,1344,86016,4161,16644,66576,65793,4368]
X=lambda B,k:any(m*k==B&m*3for m in M)
def S(B):
 if X(B,2):return 1,
 M=[i for i in range(0,18,2)if B>>i&3<2]
 return max((-S((B|3<<i)^87381)[0],i)for i in M)if M else(0,)
r='D'
c=ord(raw_input())&1
B=0
for i in range(9):
 if i&1==c:m=S(B^c*87381)[1];print m/2;B|=3-c<<m
 else:
  B|=2+c<<input()*2
  if X(B,2+c):r='XO'[c];break
print r

```

The board `B` is represented as an integer using two bits per square, with `00` and `01` representing empty, `10` representing O and `11` representing X. `M` is a set of bitmasks with `01` in the spots of a losing triple (`21` = `0b010101` = the top row etc.) `X` computes if any losing triple for `k` is present on a board. `S` does minimax search for an optimal move for X, returning a pair of the score (1=win, -1=lose, 0=draw) and a square index. `^87381` (=`^0b010101010101010101`) flips X and O while leaving empty squares unchanged.

The computer never loses, so I didn't need to include that check :) .

There is probably an easier/shorter rule-based algorithm out there, but this works.
> 11 votes

---
Tags: code-golf, tic-tac-toe
---


title: The Sleigh Packing problem

text:
# Question
Title: The Sleigh Packing problem
Santa's elves need help in determining if their current batch of presents will fit into santa's sleigh. Write the shortest program possible in the language of your choice to help them out.

## Constraints

* Santa's sleigh measures 6ft wide by 12ft long and is 4ft deep.
* Presents may be fragile, so they may not be stacked on top of each other.
* You can rotate and flip the presents as you wish, but Santa's quite an obsessive-compulsive chap so keep the rotations to multiples of 90 degrees.
* North Pole health and safety regulations stipulate that presents may not stick out more than 1ft above the top of a sleigh (therefore they may not be more than 5ft high).

## Input

Input will be on `STDIN` and will be one integer representing the number of presents in the batch followed by a list of the presents' dimensions - 1 present per line, 3 dimensions (in feet) separated by spaces.

Examples:

```
1
6 12 5

6
1 12 3
1 12 4
1 12 1
1 12 5
1 12 3
1 12 5

1
4 3 13

1
6 12 6

```

## Output

Output should just be the word 'YES' if the presents can be packed into the sleigh or 'NO' if they cannot.

Output for the above examples:

```
YES

YES

NO

NO

```

## Test scripts

As before, I've appropriated some test scripts written by Joey and Ventero to create some tests for this task:-

Usage: `./test [your program and its arguments]`

## Rewards

Each entry which I can verify that meets the spec, passes the tests and has obviously had some attempt at golfing will receive an upvote from me (so please provide usage instructions with your answer). The shortest solution by the end of the 2011 will be accepted as the winner.

# Answer
> 3 votes
## Haskell, 312 318 chars

```
import Data.List
s(ξ:υ:_,λ:σ:η:_)(x:y:_,l:w:_)=(ξ+λ<=x||ξ>=x+l||υ+σ<=y||υ>=y+w)&&ξ+λ<7&&υ+σ<13&&η<6
y p l=[(v,r):l|v<-[[x,y,0]|x<-[0..5],y<-[0..11]],r<-permutations p,all(s(v,r))l]
main=do
 n<-readLn
 p<-mapM(fmap(map read.words).const getLine)[1..n]
 putStr.r$foldr((=<<).y)[[([9,0],[0..])]]p
r[]="NO"
r _="YES"

```

For some reason that I don't fully understand at the moment, it doesn't finish your tests #9 and #16 in reasonable time. But you didn't say anything about performance, did you?

---

## 373 383 chars

This version runs *much* faster for the examples: it first checks if it's not impossible simply because the area is too small, and then it starts with the largest parcels rather then inserting them in the given order. Note that the area detection is not perfect: it doesn't consider rotations, so it may on some inputs give wrong results. But it does work with the test script.

```
import Data.List
s(ξ:υ:_,λ:σ:η:_)(x:y:_,l:w:_)=(ξ+λ<=x||ξ>=x+l||υ+σ<=y||υ>=y+w)&&ξ+λ<7&&υ+σ<13&&η<6
y p l=[(v,r):l|v<-[[x,y,0]|x<-[0..5],y<-[0..11]],r<-permutations p,all(s(v,r))l]
π=product
main=do
 n<-readLn
 p<-mapM(fmap(map read.words).const getLine)[1..n]
 putStr$if sum(map(π.init)p)>72||null(foldr((=<<).y)[[([9,0],[0..])]].sortBy((.π).compare.π)$p)then"NO"else"YES"

```

# Answer
> 2 votes
## Python, 461 chars

```
import sys
def L(P,z):
 if not P:return 1
 for w,h in[P[0],P[0][::-1]]:
  m=sum((2**w-1)<<i*6for i in range(h))
  for x in range(7-w):
   for y in range(13-h):
    n=m<<y*6+x
    if z&n==0and L(P[1:],z|n):return 1
 return 0
for G in sys.stdin.read().split('\n\n'):
 S=[(x,y)if z<6 else(x,z)if y<6 else(y,z)if x<6 else(9,9)for x,y,z in[sorted(eval(g.replace(' ',',')))for g in G.split('\n')[1:]if g]]
 print'YES\n'if sum(x*y for x,y in S)<73and L(S,0)else'NO\n'

```

`L` recursively checks if the rectangles in `P` can be put in the sleigh, where `z` is a bitmask of cells that are already occupied. The `S` assignment determines which way is up for each of the packages (largest dimension \<= 5 goes vertically).

The code is potentially exponential, but it is quick on all the test inputs.

# Answer
> 1 votes
## GolfScript, 130 characters

```
"NO":g;~](;3/127{128*64+}12*\{.,0>.!{"YES":g;}*{([{[~@]..[~\]\}3*;]{)6<{~[2\?(]*128base 83,{2\?1$*.4$&0={3$|2$f}*}%;}*}%;}*;;}:f~g

```

It took quite some time to get it running in GolfScript. Any attempt to golf it further broke some of the test cases.

Please be warned that this version may become incredibly slow if you run it with too many presents.

---
Tags: code-golf
---


title: Acrostic polyglot programming

text:
# Question
Title: Acrostic polyglot programming
The challenge is to write an acrostic piece of code.

When read normally (horizontally), the code should take an input string and remove all but the first character on each line. For example, the input:

```
float
or and
ord
 line
bool var
auto
real

```

Output:

```
foo bar

```

In addition to this, the code also must contain valid code when run vertically. Such that applying the horizontal code on itself yields a new piece of valid code in a different language.

**Rules/Restrictions:**

* Each horizontal line must contain at least 2 non-whitespace characters
* The vertical code cannot use newlines.
* The vertical code must be in a different language from the horizontal language, preferably something entirely different
* The code does not have to be a complete program (doesn't need main function, etc)

What the vertical code does is up to you, although the goal is to have it do something interesting. Having it do nothing is not interesting.

**Easy Mode:**

* You may use the same language both horizontally and vertically
* No restrictions on language choice

**Hard mode:**

* No comments
* Both codes should compile and run (main function, etc)
* Horizontal code contains exactly 1 word per line

# Answer
## Brainfuck -\> Ruby

```
e,
v[
a.
l>
"+
a[
=-<,----------
[>
i+
=<
0[-]
]>
*]
3,
e]
4[
;g
"4
+d
$)
<^
.%
b$
y@
ta
el
sD
.{
m[
a}
p]
{.
|d
bA
|:)
{y
?T
.K
,s
"+
pG
up
th
c}
 P
a$
[v
iF
]o
"d
,8
?t
,=
,h
"3
ay
[&
i*
]H
=s
gj
e9
t,
c<
"D
,d
?`
[q
,z
")
wT
hx
ie
lz
eW
 >
a$
[^
i!
];
>Y
0q
"#
,T
?X
]A
,b
"J
e$
n#
ds
"K
,$
?}
<?
,.
"e
iJ
-W
=k
1B
"&
,J
?g
>.
,>
"/
i@
+/
=s
1v
"E
,)
?.
+8
,v
"7
aS
[b
i$
]#
+5
=m
1w
"3
,*
?u
-f
,Z
"I
aW
[U
i%
]3
-v
=T
1E
":
}G
[;
b2
]@
};
*/
"+
;M
"B]

```

Horizontal is this little gem:

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

```

And Vertical is this:

```
eval"a=[i=0]*3e4;"+$<.bytes.map{|b|{?.,"putc a[i]",?,,"a[i]=getc",?[,"while a[i]>0",?],"end",?<,"i-=1",?>,"i+=1",?+,"a[i]+=1",?-,"a[i]-=1"}[b]}*";"

```

Which is a brainfuck interpreter stolen from this question. It qualifies for all of the hard mode criteria except the no comments bit, which I don't think is really fair to apply to brainfuck, or pretty much nothing but BF-\>BF would be possible.

Horizontal program runs till EOF(0) is read. Assumes newline at end of file.
> 4 votes

# Answer
## Befunge-93 (main program) -\> C (vertical program)

```
 >~:25*-v
m^>>>>v,_@
a^^...~
i^^...:
n^^...2
(^^...5
i^^...*
,^^...-
j^^<<<_$v
)^<<<<<<<
{|
f|
o|
r|
(|
i|
=|
0|
;|
i|
<|
6|
4|
;|
i|
+|
+|
)|
{|
f|
o|
r|
(|
j|
=|
0|
;|
j|
<|
6|
4|
;|
j|
+|
+|
)|
p|
u|
t|
c|
h|
a|
r|
(|
i|
&|
j|
?|
3|
2|
:|
4|
6|
)|
;|
p|
u|
t|
c|
h|
a|
r|
(|
1|
0|
)|
;|
}|
}|

```

The main program is a Befunge-93 code which does the task and ends by reading a blank line. The vertical program is in C which prints a Sierpinski triangle of depth 4 with '.' characters.

```
main(i,j){for(i=0;i<64;i++){for(j=0;j<64;j++)putchar(i&j?32:46);putchar(10);}}

```

I think I met all rules and restrictions and all items in hard mode. I'm not sure if I didn't use comments. Because comment definition in Befunge is not the same as other languages.

EDITED: added some pipe characters which are vertical condition command in befunge to meet first rule (2 non-whitespace characters in each line) as pointed out by @CMP
> 4 votes

# Answer
# Perl -\> HQ9+

Any verbose target language results in huge and unreadable code (IMHO), so in the interest of the reader I'll keep it short:

```
+print/(^.)/for<>

```
> 4 votes

---
Tags: code-challenge, polyglot
---


# Question
Title: Shortest Way of creating a basic Space Invaders Game in Python
Your challenge is to create a basic version of Space Invaders in Python

## Rules

* Program must be not written in Py3K
* All levels must be randomly generated
* There must be a HUD showing the players score

The winner would be the answer which uses the least amount of code

Some Questions

Q: *How detailed do the aliens and other elements have to be?*

A: **The aliens should be Block ASCII**

Q: *Can the bunkers be simplified to rectangles?*

A: **Yes, as long as they are filled**

Q: *How many enemies/bunkers do there have to be?*

A: **Number of Enemy's are chosen by random. 4 bunkers**

Q: *Do we need to implement the "mystery ship" that goes across the top of the screen?*

A: **No**

Q:*Do the symbols/characters that make up the laser cannon and the aliens need to be different?*

A: **Yes**

Q: *Do they need different shapes?*

A: **Yes**

Q: *Does it matter how fast the bullets/lasers travel?*

A: **No**

# Answer
## ~~3060~~ 3031 characters

OKAY, this was fun. But I very highly doubt that my code is short enough to compete, or if it's basic enough. I'm new to code golf but regardless, I had fun and that's what matters. I'm too used to object-oriented programming so a lot of my code is probably just too much objects... Game runs solely in the console, and I shortened most of the code with the `exec''''''.replace()` method. Complete with input of your name, random enemy firing, walls, aliens are randomly generated, worth 50 points each. each time you fire you lose one point so that you lose points if you just hold space in one spot to beat the level. Enemy speed increases each level, capped at every 0.2 seconds. Prints the level number, and game over at the bottom, your name,lives, and score at the top left. you have 3 lives. Ungolfed version is ~9500 characters, but I'll leave that out of here for now

instructions: fire with `space`, move with `a` and `d`, exit with `x`

let me know what think, if I can improve on anything

edit: forgot that msvcrt is Windows-Only. perhaps I can make a unix version too...

```
exec'''import threading as t
import msvcrt,Queue,time,random,os
u=raw_input('name:')
r=range
@Z:
$~(S):S.w=78;S.h=30;S.X();S.l='';S.Q=[];S.q=[];S.m=''
$J(S,x,y,c):S.q.append([x,y,c])
$X(S):S.s=[[' '^y in r(78)]^x in r(30)]
$V(S):
?s='';S.X()
?^x,y,z in S.q:S.s[y][x]=z
?S.q=[]
?^x in S.s:
? ^y in x:s+=y
? s+='\\n'
?s+=S.m.center(S.w)
?if s!=S.l:os.system('cls');S.l=s;print s
@E(Exception):pass
@C:
$~(S,g,c,p):S.g=g;S.c=c;S.p=p;S.s=[]
$M(S,a,d):
?if (a<0 and S.p[d]==0) or (a>0 and S.p[d]==(S.g.z.h if d else S.g.z.w)-1):raise E()
?S.p[d]+=a
$X(S):S.s.remove(S)
@A(C):
$~(S,g):C.~(S,g,'A',[39,28])
$M(S,a,d=0):
?try:C.M(S,a,d)
?except E:pass
@Y(A):
$~(S,g,p):C.~(S,g,'Y',p);S.s=g.a
@B(C):
$~(S,g,p,n):C.~(S,g,'|'if n<0 else'*',[p[0],p[1]+n]);S.s=g.b;S.d=n;S.a=0 if n<0 else 1
$M(S):
?try:C.M(S,S.d,1)
?except E:S.X()
$b(S):S.g.z.J(S.p[0],S.p[1],'X');S.g.z.V();S.X()
$co(S):
?^w in S.g.w:
? if S.p==w.p:S.b();w.X()
?if S.a:
? if S.p==S.g.p.p:S.b();S.g.d()
?else:
? ^a in S.g.a:
??if S.p==a.p:S.b();S.g.P(50);a.X()
@W(C):
$~(S,g,p):C.~(S,g,'#',p);S.s=g.w
@I(t.Thread):
$~(S,g):t.Thread.~(S);S.f=1;S.c={'a':g._g4,'d':g._g3,'x':g._X,' ':g._fi};S.start()
$run(S):
?while S.f:
? c=msvcrt.getch()
? if c in S.c:S.c[c]()
$X(S):S.f=0
@G:
$~(S):S.z=Z();S.x=3.0;S.c=0;S.b=[];S.Q=Queue.Queue();S.I=I(S);S.g2=0;S.g1=0;S.do=0;S.f=1;S.v=0;S.l=3;S.ti=[];S.G(1);S.O()
$O(S):
?while S.f:
? time.sleep(0.02)
? if not S.a:S.G(1)
? S.ch();S.B();S.u()
$u(S):
?S.z.X();S.P(0)
?s=u+' '+`S.l`
?^i in r(len(s)):S.z.J(i,0,s[i])
?^i in S.a+S.b+[S.p]+S.w:S.z.J(i.p[0],i.p[1],i.c)
?S.z.V()
$ch(S):
?try:
? while not S.Q.empty():S.Q.get_nowait()();S.Q.task_done()
?except Queue.Empty:pass
$cl(S):
?try:
? while not S.Q.empty():S.Q.get_nowait();S.Q.task_done()
?except Queue.Empty:pass
$_g4(S):
?if not S.g2:S.g2=1;S.Q.put(S.g4)
$g4(S):S.p.M(-1);S.g2=0
$_g3(S):
?if not S.g1:S.g1=1;S.Q.put(S.g3)
$g3(S):S.p.M(1);S.g1=0
$_X(S):S.I.X();S.Q.put(S.X)
$X(S):S.f=0;S.I.X();S.st()
$_fi(S):
?if not S.do:S.do=1;S.Q.put(S.fi)
$fi(S):S.b.append(B(S,S.p.p[:],-1));S.do=0;S.P(-1)
$_af(S):S.Q.put(S.af)
$af(S):c=random.choice(S.a);S.b.append(B(S,c.p[:],1));S.nt(random.uniform(0.1,2),S._af)
$nt(S,n,f):x=t.Timer(n,f);S.ti.append(x);x.start()
$st(S):
?^i in S.ti:i.cancel()
$G(S,n=0):
?S.st();S.cl();S.p=A(S);S.a=[];S.w=[];S.b=[]
?^x in[[i,o]^i in r(30)^o in r(3,10)]:
? if random.randint(0,99)%4==0:S.a.append(Y(S,x))
?S._m();S._af();f=[]
?^x in [6,27,46,65]:f+=[[z,y]^z in r(x,x+6)^y in r(23,26)]
?^i in f:S.w.append(W(S,i))
?S.v+=n;S.z.m='Level %s'%S.v;S.u()
?if S.x>0.2:S.x=1.6 - S.v*0.1
?S.m1=0;S.m2=0;S.k=1;time.sleep(3)
$_m(S):S.Q.put(S.m)
$m(S):
?x=0
?if S.m2:S.m2=0;S.m1=0;S.k=-S.k;x=1
?^i in S.a:i.M(*(abs(S.k),1)if x else(S.k,0))
?if S.m1==47:S.m2=1
?else:S.m1+=1
?S.nt(S.x,S._m)
$B(S):
?^i in S.b:i.M();i.co()
$d(S):
?S.l-=1
?if S.l==0:S.z.m='Game Over!';S.X();return
?S.G(0)
$P(S,n):
?S.c+=n if S.c+n>0 else 0;x=`S.c`
?^n in r(len(x)):S.z.J(n,1,x[n])
G()'''.replace('@','class ').replace('?','  ').replace('$',' def ').replace('^','for ').replace('~','__init__')

```

what the screen looks like:

```
Blazer 3
488            |

      YY  Y         YY  Y Y Y     Y
      YY  Y   YY  Y  Y           Y
      Y   Y    Y      Y    YY
                           Y   Y  Y
       YY Y   Y   Y Y             Y
           Y  YY YX Y Y
       Y       Y |                 Y

                   |

         *

                    |

      ####           |     ######             ######             ######
      ######               ######             ######             ######
      ######               ######             ######             ######

                     A

                                   Level 1

```

edit: managed to remove something I accidentally left in I wasn't using anymore
> 16 votes

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


title: Write a base X to base Y function

text:
# Question
Title: Write a base X to base Y function
## Create a function 'baseXtoY' which:

converts an integer or string `n`, which is a base `x` number (hexadecimal, binary, etc) into a base `y` number, reliably, including numbers like `10e50` or higher, using the least bytes possible, and using the following constraints:

* Provide built-in support for bases up to 64 using the following sequence: 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ=/
* Provide support for bases higher than 64 by allowing a different sequence to be used in the input
* Provide support for multi-byte sequences eg ('aa','bb','cc'...) in cases rally high value bases are needed (could also support unicode instead)
* You cannot have a base less than 2. Show an error
* You cannot use any built-in functions that convert base to base for you
* You need not worry about floating point

parameters should be:

* `n` \- any number, as a string
* `x` \- the base of `n`, integer
* `y` \- the base of the return value
* `s1` \- the sequence the given number's base uses
* `s2` \- the sequence the desired base uses
* `b` \- the bytesize of the digits in `s1`
* return value should be a string

example inputs: using '88888' base 10 to 2: `baseXtoY('88888',10,2) >>> '10101101100111000'`

base 2 to 5: `baseXtoY('10101101100111000',2,5) >>> '10321023'`

base 5 to 32: `baseXtoY('10321023',5,32) >>> '2mpo'`

base 32 to 10, using a new sequence, s=the above 64bit sequence, a=the alphabet: `baseXtoY('2mpo',32,10,s,a) >>> 'hhhhh'`

base 5 to 10, input base uses more than 1 byte per digit: `baseXtoY('bbaaddccbbaaccdd',5,10,('aa','bb','cc','dd','ee'),'0123456789',2))` \> '88888'\`

you do not have to inlude the character length of the testing or input code, just the function(s).

edit: I've given up trying to shorten my Python code lower than the answers, so I'll just show what I have. 585 characters python 2.7

```
r=range
def b1(n,x,s):
 if n==0:return s[0]
 if x<=1:raise
 l=[];p=n;i=0
 while 1:
  y=x**i;l.append(y)
  if y>p:break
  else:i+=1
 l.reverse();f=[]
 for p in l:h=int(n//p);f.append(h);n-=h*p
 while f[0]==0:f.pop(0)
 q=''
 for p in r(len(f)):q+=s[f[p]]
 return q
def b2(n,x,s,b):
 n=list(str(n));l=[]
 while n:
  a=''
  for p in r(b):a+=n.pop(0)
  l.append(a)
 m=0;q=0
 while l:c=s.index(l.pop());q+=c*(x**m);m+=1
 return q
s=''.join(map(chr,r(48,58)+r(97,123)+r(65,91)))+'=/'
def baseXtoY(n,x=10,y=2,s1=s,s2=s,b=1):return n if x==y else b2(n,x,s1,b)if y==10 else b1(b2(n,x,s1,b),y,s2)

```

test cases:

32 10 5 \>\>\> 112

112 5 2 \>\>\> 100000

100000 2 10 \>\>\> 32

88888 10 5 0123456789 ('aa', 'bb', 'cc', 'dd', 'ee') 1 \>\>\> bbaaddccbbaaccdd

bbaaddccbbaaccdd 5 10 ('aa', 'bb', 'cc', 'dd', 'ee') 0123456789 2 \>\>\> 88888

# Answer
> 3 votes
### GolfScript, 139 130 128 characters

```
~]{.,5<{[10,""*26,{[97+]}%""*.{32-}%"=/"+++]+}*}2*.,6<{1+}*~:B;.""?!{1/}*:T;.""?!{B/}*:S;:Y;:X;B/0\{S?\X*+}%;""\{.Y%T=@+\Y/.}do;

```

Most of the characters come from reading and converting parameters and adding the optional ones. The actual conversion is only few chars.

The example inputs are processed as expected:

```
'88888' 10 2                      # 10101101100111000
'10101101100111000' 2 5           # 10321023
'10321023' 5 32                   # 2mpo
'2mpo' 32 10                      # 88888
'88888' 10 5 '0123456789' ['aa' 'bb' 'cc' 'dd' 'ee'] 1
                                  # bbaaddccbbaaccdd
'bbaaddccbbaaccdd' 5 10 ['aa' 'bb' 'cc' 'dd' 'ee'] '0123456789' 2
                                  # 88888

```

*Edit 1:* some minor improvements, esp. coding the digits sequence.

*Edit 2:* this was an easy one: `0=` can be replaced by `!` two times in the conversion of the base parameters.

# Answer
> 1 votes
### scala: 399 365 chars:

```
type S=String
type I=Int
def t(l:List[I],b:I):I=l match{
case x::y=>(x%b)+b*t(y,b)
case Nil=>0}
def f(d:I,b:I):List[I]=if(d==0)List()else f(d/b,b):::List(d%b)
val c=(('0'to'9')++('a'to'z')++('A'to'Z')++Seq('=','/')).map(""+_)
def baseXtoY(a:S,g:I,r:I,i:Seq[S]=c,o:Seq[S]=c,w:I=1):S={
f(t(a.sliding(w,w).toList.map(i.indexOf(_)).reverse,g),r).map(o(_)).mkString("")}

```

testing code:

```
baseXtoY ("88888", 10, 2) //"10101101100111000"
baseXtoY ("10101101100111000", 2, 5) // "10321023"
baseXtoY ("10321023", 5, 32) // "2mpo"
baseXtoY ("2mpo", 32, 10) // "88888"
baseXtoY ("88888", 10, 5,"0123456789".map ("" + _).toSeq, "aabbccddee".sliding (2, 2).toSeq, 1) // "bbaaddccbbaaccdd"
baseXtoY ("bbaaddccbbaaccdd", 5, 10, "aabbccddee".sliding (2,2).toSeq, "0123456789".map ("" + _).toSeq, 2) // "88888"

```

result:

```
scala> baseXtoY ("88888", 10, 2) //"10101101100111000"
res218: S = 10101101100111000

scala> baseXtoY ("10101101100111000", 2, 5) // "10321023"
res219: S = 10321023

scala> baseXtoY ("10321023", 5, 32) // "2mpo"
res220: S = 2mpo

scala> baseXtoY ("2mpo", 32, 10) // "88888"
res221: S = 88888

scala> baseXtoY ("88888", 10, 5,"0123456789".map ("" + _).toSeq, "aabbccddee".sliding (2, 2).toSeq, 1) // "bbaaddccbbaaccdd"
res222: S = bbaaddccbbaaccdd

scala> baseXtoY ("bbaaddccbbaaccdd", 5, 10, "aabbccddee".sliding (2,2).toSeq, "0123456789".map ("" + _).toSeq, 2) // "88888"
res223: S = 88888

```

and ungolfed:

```
def todez (li: List[Int], base: Int): Int = li match {
  case x :: xs => (x % base) + base * todez (xs, base)
  case Nil => 0}
def fromdez (dez: Int, base: Int): List[Int] =
  if (dez == 0) List () else fromdez (dez /base, base) ::: List (dez % base)
def fromTo (li: List[Int], in: Int, out: Int) = fromdez (todez (li.reverse, in), out)

val coding=(('0'to'9')++('a'to'z')++('A'to'Z')++Seq('=','/')).map(""+ _)

def baseXtoY (in: String, f: Int, t: Int, inCoding: Seq[String] = coding, outCoding: Seq[String] = coding, width: Int=1): String = {
  val is = in.sliding (width, width).toList
  val li = is.map (inCoding.indexOf (_))
  val tmp = fromTo (li, f, t)
  tmp.map(outCoding(_)).mkString ("")
}

```

# Answer
> 0 votes
Scheme type conversions take care of this. The numerical tower too:

```
(define (f n b) (number->string n b))

```

Floating points, exceptions... Everything is taken care of. Just put a number and a base and it gets converted to whichever base.

---
Tags: code-golf
---


# Question
Title: Fastest C/C++ comparison function for an opaque field containing doubles
**Description:**

Write the fastest comparison function for an opaque field containing a double. Here is my example:

```
// Three-way comparison function:
//   if a < b: negative result
//   if a > b: positive result
//   else: zero result
inline int Compare(const unsigned char* a, const unsigned char* b) const
{
    if (*(double*)a < *(double*)b) return -1;
    if (*(double*)a > *(double*)b) return +1;
    return 0;
}

```

Size: 188 characters (excluding the comments)
Speed: N/A

**Background:**

Google's LevelDB stores keys as opaque fields (i.e. bytes) and it requires the use of a comparator when the keys cannot be compared as bytes, such as the case with doubles. You can read this article to see why Floating-Point binary comparison is tricky, so when LevelDB stores key-value pairs on disk it has to properly compare the opaque keys in order to achieve good data locality.

**Correct Submission:**

1. The submission must be written in C/C++.
2. The submission must correctly compare the opaque fields as doubles.
3. Given that 1 and 2 are satisfied, the winner should be selected based on the minimum CPU operations ticks (i.e. the fastest comparison).

If there is a tie, then the shortest correct submission will be awarded.

P.S. This is my first time posting, so please let me know if I should correct/improve something in the competition.

# Answer
> 5 votes
This function is written in MMIX assembly. It should perform the calculation in 2υ \+ 5μ. If you inline it, the call is no longer needed so you can save the `POP` instruction. This function should be compatible with gcc for MMIX. (Read TAOCP vol 1. fasc 1 for more information):

```
compareDoubles IS @  ; Declare symbol, @ is the current position
   LDOU $0,$0,0      ; Load first double  (LDOU: load octa unsigned), 1v
   LDOU $1,$1,0      ; Load second double, 1
   FCMP $0,$0,$1     ; Compare floating point values, 4µ
   POP  1,0          ; return, 1µ

```

If you assemble it, the code is 16 bytes long and may looks this:

```
8f 00 00 00  8f 01 01 00  01 00 00 01  f8 01 00 00

```

# Answer
> 1 votes
```
#define compare(X, Y) ((X)<(Y)?-1:((X)>(Y)?1:0))
// 48 characters

```

or want to pass a pointer you can define

```
#define compare(X, Y) (*((double*)X)<*((double*)Y)?-1:(*((double*)X)>*((double*)Y)?1:0))
// 88 characters

```

---
Tags: code-golf, math, fastest-code, c++, c
---


title: Shortest route through a one-way system

text:
# Question
Title: Shortest route through a one-way system
My home town, Rhyl, has a one-way traffic system which seems to have been designed to keep people away from their destination for as long as possible. Your task, should you choose to attempt it, is to produce a program to give the shortest route through such a traffic system.

## Input

Input will be on `STDIN`, and will be a list of start and end points followed by a blank line followed by a list of queries, as follows:

```
A B
B A
B C
C D
D C

A D
C A
B A

```

Each road can only be travelled in the direction(s) given, so, in the above example the road A - B is a two way street whereas B - C is a one-way street from B to C. Travelling from C to B is prohibited.

Start and end points will all be represented by a single upper-case letter.

## Output

Output should be the shortest route (measured by number of points visited) from the given start point to the given end point for each query received. If no such route exists, output a blank line. If more than one shortest route exists, output the first when sorting all shortest routes lexicographically.

For the above example the output would be:

```
A B C D

B A

```

## Test Scripts

As before I'm providing tests for this task based on scripts written by Joey and Ventero:-

and also tests and expected output for anyone who can't use the above scripts

Usage: `./test [your program and its arguments]`

## Rewards

All answers which have obviously had some attempt at golfing that meet the spec and pass all the tests will get my upvote. The shortest working answer by 26/01/2012 will be accepted.

# Answer
## Haskell, ~~223~~ 207 characters

```
main=interact$unlines.f.break null.map words.lines
s%[f,t]=[[f]]#t where[]#_="";x#t|y@(_:_)<-[z|z<-x,last z==t]=unwords$minimum y|1<3=s&x#t
s&z=[x++[b]|x<-z,[a,b]<-s,last x==a,notElem b x];f(s,_:q)=map(s%)q

```
> 3 votes

# Answer
## Python (2.x), 382 369 358 338 323 318 characters

All tips and comments welcome!

```
import os;u=str.split;l=u(os.read(0,1e9),'\n')
p,g,c=l.index(''),{},map;o=g.setdefault
def f(g,s,e,q=[]):q=q+[s];y=([],[q])[s==e];[c(y.append,f(g,n,e,q))for n in set(o(s,[]))-set(q)];return y
for k,v in c(u,l[:p]):o(k,[]);g[k]+=v
for w,e in c(u,l[p+1:]):h=sorted(f(g,w,e));print''if not h else' '.join(min(h,key=len))

```

Should pass the tests in this form. Feed input via stdin, e.g. `python shortestroute.py < test.txt`.
> 2 votes

# Answer
# C:450,437,404,390 characters

```
#include<stdio.h>
#include <string.h>
r[99][99],p[99],q[99],m[99],i,j,x,y,s;
char t[9],e[9999];
F(k)
{
    m[k]^s?r[p[k]=q[i]][k]?m[q[j++]=k]=s:0:0;
    if(++k<99)F(k);
}
f()
{
    F(0);
    if(++i^j)f();
}
P(o)
{
    if(p[o])P(p[o]);
    *t=m[o]^s?0:o;
    strcat(e,t);
}
w()
{
    gets(t);
    r[*t][t[2]]=*t?w():0;
}
W()
{
    gets(t);
    x=*t,x?y=t[j=2],s=x+y*99,m[q[t[2]=i=p[x]=0]=x]=s,f(),P(y),strcat(e,"\n"),W():0;
}
main()
{
    w();
    W();
    puts(e);
}

```
> 1 votes

---
Tags: code-golf, graph-theory
---


title: HangOver ACM problem!

text:
# Question
Title: HangOver ACM problem!
there is only one rule: get accept for this problem http://acm.ut.ac.ir/sc/problemset/view/1032!

to submit your code, you need to create an account(if you don't want to do so, just post your code here and I'll submit it). so far shortest code is written with C and has 85 character length.

winner will be the shortest C/C++ code submitted before 2012/02/01

note: to check shortest codes submitted you can click on "accepted runs" and then "code length"

as elssar suggested I've copied the question here :

How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We're assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 + ... + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). This is illustrated in the figure below.

figure http://acm.ut.ac.ir/sc/assets/problem\_images/1032\_50ac13c53158fd843d1884e8afa962dd.jpg

# Input

The input consists of one or more test cases, followed by a line containing the number 0.00 that signals the end of the input. Each test case is a single line containing a positive floating-point number c whose value is at least 0.01 and at most 5.20; c will contain exactly three digits.

# Output

For each test case, output the minimum number of cards necessary to achieve an overhang of at least c card lengths. Use the exact output format shown in the examples.

# Sample Input

1.00
3.71
0.04
5.19
0.00

# Sample Output

3 card(s)
61 card(s)
1 card(s)
273 card(s)

# Answer
## C, 149 89

Well, this was a noobish shot at it, but probably a decent starting point:

```
#include <cstdio>
float i;
int o(float a,int n=2){return a<0?n-2:o(a-1./n,n+1);}
main(){if (scanf("%f",&i),i==0) return 0;printf("%d card(s)\n",o(i));main();}

```

It reported as 145 characters.

---

With a push in the right direction, I got the solution down to 122 by changing the function to a for loop.

```
#include <cstdio>
float i;
main(){
if (scanf("%f",&i),i==0) return 0;
int n=2;for(;i>0;)i-=1./n++;
printf("%d card(s)\n",n-2);
main();}

```

---

On a roll!

```
#include <cstdio>
main()
{
    float i,n=2;
    for(scanf("%f",&i);i>0;i-=1/n++);
    if (n-=2) printf("%.0f card(s)\n",n), main();
}

```

Scooted `scanf`, for loop division doesn't need `1.` any more, adjusting `n` now done in conditional.

---

Switched over to C, got some good savings. Down to 89 characters.

```
main(n)
{
    float i;
    for(scanf("%f",&i);i>0;i-=1./++n);
    if (--n) printf("%d card(s)\n",n), main(1);
}

```
> 2 votes

# Answer
As I said so far there is an answer with 85 characters written in C99 (note that white spaces are not counted)

```
main(i){for(float x;i=scanf("%f",&x),x;printf("%d card(s)\n",--i))for(;x>0;x-=1./++i);}

```

that was the whole code, hope It gives you the idea how to optimize it!
> 0 votes

---
Tags: code-golf, c
---


# Question
Title: Which Numbers Would Crash this Function?
Which values of x and y will cause a crash with some C compilers?

```
int f(int x, int y) {
    return (y==0) ? 0 : (x/y);
}

```

# Answer
> 7 votes
-2147483648 (INT\_MIN) and -1

```
#include <stdio.h>
#include <limits.h>
int f(int x, int y) {
    return (y==0) ? 0 : (x/y);
}
int main() {
    int r = f(INT_MIN, -1);
    printf("%d\n", r);
    return 0;
}

```

$ gcc -Wall division.c && ./a.out # =\> zsh: floating point exception ./a.out

# Answer
> 3 votes
The right answer is already given, but I immediately thought about Microsoft Pex.

> Pex automatically generates test suites with high code coverage. Right from the Visual Studio code editor, Pex finds interesting input-output values of your methods, which you can save as a small test suite with high code coverage. Microsoft Pex is a Visual Studio add-in for testing .NET Framework applications

After adding your puzzle in the sandbox site, it finds the answer in a few seconds, the same as eregons answer. (click ask pex)

*Note: it does it in C#, but the language is not really relevant.*

* x: int.MinValue
* y: -1
* Exception: OverflowException
* Message: Arithmetic operation resulted in an overflow.

---
Tags: c, programming-puzzle, division
---


title: ASCII art 3D StreetView

text:
# Question
Title: ASCII art 3D StreetView
## Input:

1. You get a series of integers (fed via stdin or prompt).
2. Every pair of integers in this series represents a building's WIDTH \[valid range: 1..10\] and HEIGHT \[valid range: 0..10\]
3. Assume input to be well-formed.

*Sample input (the second line is for demonstration purposes only):*

```
1 2 1 1 1 0 2 4 1 3 1 2 2 1
W H W H W H W H W H W H W H

```

*Corresponding sample output:*

```

                 ______
               /______ /|
              |       | |__
              |       |/__ /|
     __       |       |   | |__
   /__ /|     |       |   |/__ /|
  |   | |__   |       |   |   | |______
  |   |/__ /| |       |   |   |/______ /|
  |   |   | |_|       |   |   |       | |
  |_o_|_o_|/__|_o_____|_o_|_o_|_o_____|/
  -------------------------------------
 -  -  -  -  -  -  -  -  -  -  -  -  -
-------------------------------------

```

## Rules:

**The buildings**

1. A basic building block looks like this (1 W, 1H)

```
   __
 /__ /| (base cube is borrowed from the one at this question:
|   | |  http://stackoverflow.com/questions/1609702/code-golf-playing-cubes)
|___|/

```
1. Our view is (ahum) ~3D so neighbouring buildings may hide parts of others. Buildings are 'logically' rendered from left to right.
2. The first building is preceded by two spaces to it's left.
3. You render every building by applying the WIDTH and HEIGHT to the dimensions of the base cube (do have a look at the sample output provided!). For reference: number of characters from the left to the right 'wall' (for a building with W \> 1): (W\*5)-(W-1).
4. Buildings with Height \> 0 have ONE door (which is depicted by the character `o` and is located at two characters from the 'left' wall on the 'bottom' row ).

**The road:**

1. The road consists of three parts which we'll call 'top', 'middle' and 'bottom'.
2. The 'top' part and 'bottom' part are identical apart from the fact that the 'top' part is preceded by two spaces.
3. The middle part is preceded by one space and consists of a repetition of the following pattern:
```
'-  '
```
4. Length is to be determined by the total width of the combined buildings: the most rightmost part of the road corresponds with the position of the 'right' wall of the 'last' building.

## Winners:

This is code-golf! The winner is the qualifying contestant with the shortest solution (by source code count). The source must consist solely of printable ASCII characters. Have fun!

Imaginary bonus points for (random) windows, cars or pedestrians.

Feel free to comment if the specifications are not clear!

# Answer
## Haskell, 396 characters

```
w&h=take h((3," /|"++(w-3)#'_'++"o_|"):c[(3,"| |"++(w-1)#s++"|")])++[(2,"|/ "++(w-2)#'_'++"/"),(0,"  "++(w-2)#'_')]++c[(0,w#s)]
p(w,h)=r.z take[sum w+k|k<-[1..]]$([c"-",s:c"-  ","  "++c"-"]++).map r.foldl(z(%))((2+maximum h)#(5#s))$z(&)w h
main=interact$unlines.p.q.map read.words;y%(d,x)=x++drop d y;q(x:y:z)=(4*x:a,2*y:b)where(a,b)=q z
q x=(x,x);(#)=replicate;c=cycle;r=reverse;z=zipWith;s=' '

```

**Example output:**

```
$ runghc Streetview.hs <<< "1 1 1 3 1 2 1 0 2 4 2 2 1 3 3 1"
                     ______
                   /______ /|
         __       |       | |        __
       /__ /|     |       | |      /__ /|
      |   | |__   |       | |_____|   | |
      |   |/__ /| |       |/______|   | |
     _|   |   | | |       |       |   | |__________
   /__|   |   | | |       |       |   |/__________ /|
  |   |   |   | |_|       |       |   |           | |
  |_o_|_o_|_o_|/__|_o_____|_o_____|_o_|_o_________|/
  -------------------------------------------------
 -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
-------------------------------------------------

```
> 10 votes

# Answer
## Python, 415 chars

```
I=eval(raw_input().replace(' ',','))
X=I[::2]
Y=I[1::2]
W=4*sum(X)+6
H=2*max(Y)+2
A=W*H*[' ']
p=W*H-W+2
for w,h in zip(X,Y):i=2*h;j=4*w;q=p-i*W;r=p+j;s=q+j;A[p+1:q+1:-W]=A[p+2:q+2:-W]=i*' ';A[p:q:-W]=A[r:s:-W]=A[r+2-W:s+2-W:-W]=i*'|';A[p+1:r]='_'*(j-1);A[q+2:s]=A[q+3-W:s+1-W]='_'*(j-2);A[q+1]=A[s+1]=A[r+1]='/';A[p+2]='_o'[h>0]; p+=j
A[W-1::W]='\n'*H
D=(W-5)*'-'
print''.join(A)+'  '+D+'\n'+(' - '*W)[:W-4]+'\n'+D

```

Uses slices to draw all the parts of the building.

```
$ echo "1 2 1 1 1 0 2 4 1 3 1 5 2 1" | ./streetview.py
                             __
                           /__ /|
                 ______   |   | |
               /______ /| |   | |
              |       | |_|   | |
              |       |/__|   | |
     __       |       |   |   | |
   /__ /|     |       |   |   | |
  |   | |__   |       |   |   | |______
  |   |/__ /| |       |   |   |/______ /|
  |   |   | |_|       |   |   |       | |
  |_o_|_o_|/__|_o_____|_o_|_o_|_o_____|/
  -------------------------------------
 -  -  -  -  -  -  -  -  -  -  -  -  -
-------------------------------------

```
> 8 votes

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


title: String manipulation

text:
# Question
Title: String manipulation
**The challenge is to manipulate strings using basic Vim-like commands**

**Input:**

* A string of text to be transformed. The input alphabet is \[a-z\].
* A string of legal commands

**Output:**

* The transformed string

---

There are a few ideas you should understand:

The cursor is represented as a location between 2 characters. `|` will be used to represent the cursor(s) in this explanation.

* `|foobar` \- The cursor at beginning of string
* `foo|bar` \- Cursor in the middle of the string
* `foobar|` \- Cursor at the end of the string

A selection is a a group of characters between 2 cursors.

* `|foobar|` \- The selection is `foobar`
* `|foo|bar` \- The selection is `foo`
* `foo|bar|` \- the selection is `bar`
* `|foobar` \- The selection is the empy string (both cursors at same location)

A selection is formed from the previous cursor position and the result of the current command.

Using the command `>` on `|foo` would make the selection `|f|oo`.

Commands can be described as functions. `C<selection>` is a command that has a selection parameter. The next command provides the selection.

* `D>` deletes the character to the right of the cursor. `f|oo` `->` `f|o`
* `DNa` deletes from the cursor to the next `a` character `f|oobar` `->` `f|ar`
* Etc.

As you can see, commands "associate to the right"

* `DNa` is parsed as `(D(Na))`
* `DDNa` is parsed as `(D(D(Na)))`
* Etc.

The insert mode command `I` extends until the next command.

* `DIbar>` is parsed as `(D(Ibar))(>)`.

**These are the commands:**

* `>` \- Move cursor right. `>` on `foo|bar` `->` `foob|ar`
* `<` \- Move cursor left. `<` on `foo|bar` `->` `fo|obar`
* `B` \- Move cursor to the beginning of the string
* `E` \- Move cursor to the end of the string
* `N<char>` \- Move cursor to place before next `<char>`. `Na` on `|foobar` `->` `foob|ar`
* `P<char>` \- Move cursor to place after previous `<char>`. `Po` on `foobar|` `->` `foo|bar`
* `I<string>` \- Enter/exit insert mode. Characters in `<string>` are inserted at the current cursor position. `<string>` extends until the next command. The cursor is moved to end of insertion `<string>`. `Iquz` on `foo|bar` `->` `fooquz|bar`
* `D<selection>` \- delete characters in `<selection>`. `f|ooba|r` `->` `f|r`. The output selection from this command is the empty string.

**Notes:**

* The cursor cannot move out of bounds. `B<<<` is the same as `B`. `Nx` is the same as `E` if no `x` can be found.
* The cursor location always starts at the beginning of the string
* The cursor should not be outputted
* Commands are always uppercase, characters are lowercase.

**Restrictions:**

* No text editor scripts like Vimscript

**Winning criteria:**

* It's code golf. Lowest character count wins.

---

**Examples:**

Input:

* `foobar`
* `>>><<>If`

Output:

* `fofobar`

---

Input:

* `foobar`
* `>>>DNEDPf`

Output:

* `f`

---

Input:

* `foobar`
* `>>>DDDDIbazD<Iquz>DPfDII`

Output:

* `far`

# Answer
## Haskell, 371 characters

```
z l b n i=p where
 p(a:c@ ~(q:u))|Just x<-a`lookup`zip"<>BEDNP"[l#c,m l#c,b#c,m b#c,z(d$k id)(\k _->k"")h(k f)c,m(n q)#u,n q#u]=x
 p('I':q:c)|q>'`'=i q c;p(_:c)=f c;p""=(++).r
d f k(q:x)=k x.f q;d f k""=k"";k&x=k"".(r x++);h q=(.snd.s q);n q k=(\(a,b)->k b.(r a++)).s q
x%c=f c""x;f=z(d(:))(&)n$ \q c->f('I':c).(q:);m f=flip.f.flip;k=const;r=reverse;(#)=(.f);s=span.(/=)

```

This defines a function `%` which returns the result of applying the string of commands to the original string.

**Example usage:**

```
> "foobar" % ">>>DNEDPf"
"f"
> "foobar" % ">>>DDDDIbazD<Iquz>DPfDII"
"far"

```
> 5 votes

---
Tags: code-golf, string
---


title: 400th Question Celebration/Challenge

text:
# Question
Title: 400th Question Celebration/Challenge
I just looked and saw that there are 399 questions on this wondrous "Programming Puzzles & Code Golf" site!!! That means that...**THIS IS THE 400th question!!!** To celebrate this momentous occasion, here are your goals:

1. Write a piece of code that is **EXACTLY 400 bits**.

* That's right...**BITS**!!!
    * For the risk of redundancy and the sake of clarity, that's 50 bytes!!!
2. Because this occasion is so extraordinarily meaningful, each bit and therefore each byte must also be meaningful!

* In other words: You can't just name a variable `aaaaa` because you needed 32 extra bits to get to 400. However, you can rename it to `party` as long as that is a meaningful name for that variable.
3. Your program must do something appropriate (not necessarily output something appropriate) to celebrate this grand occasion!

* For example: You could choose to make a program that outputs `400`. However, I must needs state that although submitting code that does only that would meet this requirement, it would also be like celebrating your birthday party at home by yourself sick in bed. At least you celebrated, but hey: **You can do better!!!**
4. The most creative code wins!!! In this case, creativity will be measured by votes.
5. This contest will last until **400** users have viewed this question. If there is a tie when the 400th user views this question, the contest will go into sudden-death overtime until there is a clear winner

Oh, and lest I forget...**HAPPY 400th QUESTION!!!**

# Answer
> 10 votes
### Python, FOUR HUNDRED bits

```
i=0
while 1:print" "*(i%8>3 and-i%4 or i%4),0;i+=1
```

At first I wanted to make a sine scroller, but there was no place for the import. Now you get a bugged triangle wave. ~~~party~~~

# Answer
> 8 votes
# Brainf\*ck

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

```

And the output will be: 400!

# Answer
> 7 votes
## Ruby

```
1.upto(side=gets.to_i){|i|puts (?**i).center side}

```

This creates a wobbling tree, like the following:

```
   *
  **
  ***
 ****
 *****
******
*******

```

# Answer
> 7 votes
### Scala gratulates with 400 Bits:

```
(1 to 400).map(x=>print("""
 ,
|_|
"""))

```

Sample:

```
 ,
|_|

 ,
|_|

 ,
|_|

 ,
|_|

```

... due to restrictions, I couldn't light bigger candles. I try to compensate with the scheer number.

# Answer
> 5 votes
### JavaScript, 400 bits

**Code**

```
for(i=0,a='';i<400;)a+='\n!'+i++;alert(a+"\n400!")

```

**Output**

```
!0
!1
!2
!3
..
..
!398
!399
400!

```

Or, how it is read in English: "not 0, not 1, not 2, not 3 .. not 398, not 399, 400!"

**Update**

Just realized I forgot to attach the Fiddle for this problem!

# Answer
> 2 votes
# HTML

(bad HTML!)

```
<marquee style="font-size:400px">~!400!~</marquee>

```

# Answer
> 1 votes
# Python

50 characters or 400 bits as metered by other submissions.

```
i,j=1,1
while len(str(i))<81:
 print i
 i,j=j,i+j

```

Simple fibonacci calculator, which terminates once the output no longer fits in a standard 80x60 terminal. Not especially festive I know, but the best I could come up with on short notice. More to follow!

# Answer
> 1 votes
**Here comes C#!**

```
class P{static void Main(){System.Console.Write("400!");}}

```

Ok, that is the smallest, running / valid, and remarkable thing i could squeeze out of .NET! But it fails by 13bytes! (code is 63bytes). Someone might suggest an improvement :D

Maybe using the roman numeral version might slash off an extra byte :-)

```
class P{static void Main(){System.Console.Write("CD!");}}

```

# Answer
> 1 votes
Bits of code, or bits compiled? Ah well, I see nobody has posted any x86 yet, so here goes...

## x86

```
4D 5A 90 00 03 00 00 00 40 00 00 0F FF F0 00 0B 80 00 00 00 00 00 00 04 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

```

IDK if this counts, it's the first 400 bits (in hex) of a Win32 PE executable

## VB.NET

```
Sub Main()
    Console.WriteLine("400 CodeGolf")
End Sub

```

# Answer
> 1 votes
## Yet another Python answer.

```
k=(1,)
while len(k)<400:k+=(sum(k[-2:]),)
print(k)

```

Print the first 400 Fibonacci numbers. I notice one of the other Python answers also does the Fibonacci sequence... Oh well. I came up with this method of calculating Fibonacci numbers while working on another code golf and I thought it was neat so I figured I'd answer anyway.

# Answer
> 0 votes
## Ada

```
with P;procedure C is begin P("400! Yay!");end C;

```

assuming there is a package *p*:

```
$ cat p.ads
procedure P(S:String);
$ cat p.adb
with Ada.Text_IO;
procedure P(S:String) is
begin
   Ada.Text_IO.Put_Line(S);
end P;

```

If I put `with Text_IO;` and `Text_IO.Put("")` into the source code I would already exceed the limit by 7 bytes, without outputting anything.. Ada is hard to golf.

# Answer
> 0 votes
**Shells with banner installed**

```
banner -w80 HAPPY  HAPPY  HAPPY  400th  QUESTION!

```

# Answer
> 0 votes
# Perl

```
$number_400=400;
$and_still_number_400=$still_number_400*4/4;
$when_is_the_500_post="In 100 posts!!";
print $number_400*400/400;

#      # ########## ##########
#      # #        # #        #
#      # #        # #        #
######## #        # #        #
       # #        # #        #
       # #        # #        #
       # #        # #        #
       # ########## ##########

```

# Answer
> 0 votes
Perl /\*Life:Eat,sleep,then die \*/

```
$rip=400;$pork="Pi";chop($pork);sleep($rip);die();

```

---
Tags: popularity-contest
---


# Question
Title: Conversion to palindrome with minimal points used
**Input**: a word (2-100 characters)

Convert this word to a palindrome:

* delete character - 13 points
* add character - 12 points
* increase character - 5 points ('d' \> 'e')
* decrease character - 4 points ('n' \> 'm')
* switch 2 characters - 7 points

What is the minimal points needed to make the word palindrome? (C++/C#)

**Output**: Minimal points needed to convert the word

**Winning criteria**: fastest algorithm

# Answer
> 2 votes
Spent about an hour and got a working solution that I believe should give an optimal result:

```
public class PalindromeFinder : IComparer<Tuple<int,string>>
    {
        public PalindromeFinder()
        {
            heap = new IntervalHeap<Tuple<int, string>>(this);
            handles = new Dictionary<string, IPriorityQueueHandle<Tuple<int, string>>>();
        }

        private readonly IntervalHeap<Tuple<int, string>> heap;
        private readonly Dictionary<string, IPriorityQueueHandle<Tuple<int, string>>>  handles;

        public int FindMinValue(string startingWord)
        {
            AddWord(startingWord,0);
            while(!heap.IsEmpty)
            {

                var item = heap.DeleteMin();
                var word = item.Item2;
                var value = item.Item1;
                handles.Remove(word);
                if(IsPalindrome(word))
                {
                    return value;
                }
                for(int i = 0; i<word.Length; i++)
                {
                    //decrease
                    var decreased = word.ToCharArray();
                    if (decreased[i] > 'a')
                    {
                        decreased[i]--;
                        AddWord(new string(decreased), value + 4);
                    }
                    //switch
                    for(int j = i+1; j<word.Length; j++)
                    {
                        if (word.Count(x => x == word[i]) >= 2 || word.Count(x => x == word[j]) >= 2)
                        {
                            var swap = word.ToCharArray();
                            var tmp = swap[i];
                            swap[i] = swap[j];
                            swap[j] = tmp;
                            AddWord(new string(swap), value + 7);
                        }
                    }
                    //add character before (only add characters already present)
                    foreach (char c in word.Distinct())
                    {
                        var added = word.Insert(i, c.ToString());
                        AddWord(added, value+12);
                    }
                }
                //add character at end of word
                foreach (char c in word.Distinct())
                {
                    var added = word + c.ToString();
                    AddWord(added, value + 12);
                }
            }
            return int.MaxValue;
        }

        private void AddWord(string word, int value)
        {
            var min = int.MaxValue;
            if(handles.ContainsKey(word))
            {
                var tuple = heap.Delete(handles[word]);
                min = tuple.Item1;
                handles.Remove(word);
            }
            IPriorityQueueHandle<Tuple<int, string>> handle = null;
            heap.Add(ref handle,new Tuple<int, string>(Math.Min(min, value), word));
            handles[word] = handle;
        }

        private bool IsPalindrome(string word)
        {
            int left = 0;
            int right = word.Length - 1;
            while(left<right)
            {
                if (word[left] != word[right]) return false;
                left++;
                right--;
            }
            return true;
        }

        public int Compare(Tuple<int, string> x, Tuple<int, string> y)
        {
            return x.Item1 - y.Item1;
        }
    }

```

Uses priority queue implementation from C5 collections. This is basically the brute force best-first search solution to the problem. It runs out of memory pretty fast, and is less efficient than is probably possible. I could fix that by implementing a better data structure like a DAWG, but out of time for now. Maybe later.It does work well for short words, and even for long ones that are within a few steps of a palindrome already.

### Edit:

Made some improvements on Peter's suggestion, but the complexity is still too high. On input: "superman", runs for about a minute until it runs out of memory with over 11 million items in heap and a max value of 42 reached. Still a bit off from being a viable general solution.

# Answer
> 0 votes
## C++

Made this under the assumption that simply changing the character costs the same as switching two characters(7 points) & that comparing costs 0 points. A pretty basic & dumb solution, but it works.

```
int main(int argc, char *argv[]) {
    int c, l, p;
    p = 0;
    if(argc != 2) {
        cout<<"Incorrect arguments\n";
        return 1;
    }
    else if(strlen(argv[1])<2 || strlen(argv[1])>100) {
        cout<<"Not a valid string(between 2 & 100 characters)\n";
        return 1;
    }
    l = strlen(argv[1]);
    c = l/2;
    for(int i=0;i<c;i++) {
        if(argv[1][i] != argv[1][l-i-1]) {
            argv[1][i] = argv[1][l-i-1];
            p+=7;
        }
    }
    cout<<argv[1]<<endl<<p<<endl;
    return 0;
}

```

---
Tags: string, palindrome, fastest-algorithm, c, c++
---


title: Sudoku board generator

text:
# Question
Title: Sudoku board generator
A program that randomly generates a Sudoku game board with varying degrees of difficulty (however you decide to measure difficulty). Sudoku requires that there is only one solution, so your program should too. Input and output can be any form or method of your choosing.

**Judging**

Fastest code. Tested on a quad-code Windows 7 machine with freely or easily available compiler. Provide link if necessary.

# Answer
# Scheme

Why should I be constrained on the platform used? Especially on such a developer-unfriendly platform as Windows! Anyways... doesn't matter since this code compiles on all Scheme implementations that provide the standard libraries srfi-1, srfi-27 and srfi-43 (that means almost all of them), on virtually (pun intended) every platform. The only non-portable-across-all-implementatons construct I use is "import", but I might as well have used "use" or "require" among others. This minor incompatibility between implementations will be fixed this year, don't worry.

Because of the holy wars pertaining to the Lisp family of languages on the matters of minimalism, the last standard in final status (R6RS) was rejected by most implementors, prefering instead to stick to R5RS until the steering comitee broke up. They came up with the idea to split the language in two, the first being a minimalistic core (assigned to working group 1). The second will be a superset of the first which will better suit daily usage. Both will form R7RS, which will be released this year. This will solve many incompatibilities between implementations.

```
;; Sudoku generator (v0.2)

;; list ops          randomness     vector ops
(import srfi-1) (import srfi-27) (import srfi-43)

(define rand (random-source-make-integers
                 default-random-source))

(define (shuffle! vec)
  (let swap! ([n (vector-length vec)])
    (let* ([i (rand n)] [n (- n 1)])
      (when (> n 1) (vector-swap! vec n i) (swap! n)))))

(define (make-row)
  (let ([row (vector-unfold (lambda (i) (+ i 1)) 9)])
    (shuffle! row) row))

(define (make-rows)
  (let f ([i 8] [r (make-row)])
    (cons r
      (if (zero? i) (list)
          (f (- i 1) (vector-copy r 1 10 (vector-ref r 0)))))))

(define (split-in ls n)
  (let ([n (quotient (length ls) n)])
    (let f ([ls ls])
      (if (null? ls) ls (cons (take ls n) (f (drop ls n)))))))

(define (make-grid)
  (let ([g (list->vector
              (map list->vector
              (zip (split-in (make-rows) 3))))])
    (shuffle! g) (vector-for-each shuffle! g)
    (vector-concatenate (vector->list g))))

```

Difficulty: none

I felt the code was too complicated so I rewrote it from scratch. For clue pruning, I am currently working on encoding the board in CNF notation. Since I have access to the original grid, testing for uniqueness is easier. Pruning is done by priority (we prefer to prune cells who maximize the number of possibilities in its surroundings).

So far, this only generates a valid complete grid using only a vector of numbers from 1 to 9 that swaps each index with a random index. This random row is used to derive the other rows by successive rotation. This works because there are only 8 other possible rows, given one sudoku row.

Thus, so far we have ensured there are no row or column conflicts possible. As a matter of fact, the sudoku is based on latin squares which are roman grids of size n\*n (a square) which must have unique numbers on every row and column in the range 1 to n. A sudoku is a latin square of size 9\*9, with an added constraint: regions.

The next step is to split the list of rows in 3, which now looks like this, given an initial row of (1 2 3 4 5 6 7 8 9):

```
;; this is a latin square
(((1 2 3 4 5 6 7 8 9)
  (2 3 4 5 6 7 8 9 1)
  (3 4 5 6 7 8 9 1 2))
 ((4 5 6 7 8 9 1 2 3)
  (5 6 7 8 9 1 2 3 4)
  (6 7 8 9 1 2 3 4 5))
 ((7 8 9 1 2 3 4 5 6)
  (8 9 1 2 3 4 5 6 7)
  (9 1 2 3 4 5 6 7 8)))

```

Given a grid like that, I can "zip" the lists (perform matrix transposition) so that it now looks like this:

```
;; this is now a sudoku
(((1 2 3 4 5 6 7 8 9)
  (4 5 6 7 8 9 1 2 3)
  (7 8 9 1 2 3 4 5 6))
 ((2 3 4 5 6 7 8 9 1)
  (5 6 7 8 9 1 2 3 4)
  (8 9 1 2 3 4 5 6 7))
 ((3 4 5 6 7 8 9 1 2)
  (6 7 8 9 1 2 3 4 5)
  (9 1 2 3 4 5 6 7 8)))

```

Magic! No row, column or region conflicts! What needs to be done next is to shuffle the three lists of rows, and the three rows within them. To do that, we convert all lists to vectors, then reuse the same shuffle procedure used with the first row. The last step is to collapse everything back to a grid of 9 rows.

I will post updates later. I am currently more advanced than this, but the rest is still in development (I promise you the cleverness and simplicity of my algorithms will surprise you). This was not done in one day, but with great amounts of research for optimal algorithms.
> 5 votes

---
Tags: game, fastest-code, board-game, sudoku
---


title: Hashiwokakero: Build bridges!

text:
# Question
Title: Hashiwokakero: Build bridges!
Hashiwokakero ("build bridges" in Japanese) is a puzzle where you are tasked with connecting a group of islands with bridges. The rules are:

1. Bridges must run either vertically or horizontally between two islands.
2. Bridges may not cross each other.
3. A pair of islands may be connected by at most two parallel bridges.
4. Each island is marked with a number between 1 and 8, inclusive. The number of bridges connected to an island must match the number on that island.
5. The bridges must connect the islands into a single connected group.

Your task is to write a program that will solve Hashiwokakero puzzles.

You may assume that any given puzzle is solvable and that there is only one solution.

The program should be reasonably efficient. For example, solving the 25x25 puzzle below shouldn't take more than 10 minutes on an average PC and it shouldn't use more than a gigabyte of memory. Solving smaller puzzles like the 7x7 one should take seconds.

**Input:**

The puzzle will be given as a 2D map of characters, with the digits `1` to `8` representing islands, and spaces representing water. The lines will be padded with spaces if necessary to make them all the same length.

Islands will always be separated horizontally and vertically by at least one square of water so that there is room to place the potential bridge between them. There will always be at least two islands in a puzzle.

Your program should preferably read the puzzle map from standard input, but you may specify an alternate input method if your programming language requires it.

**Output:**

The output should be like the input, except with spaces replaced by bridges as necessary. The bridges should be drawn using Unicode box drawing characters  (U+2500),  (U+2502),  (U+2550) and  (U+2551) to represent horizontal and vertical single and double bridges.

If Unicode characters are a problem, you may use the ASCII characters `-`, `|`, `=` and `H` instead.

**Winning criteria:**

This is code golf. The shortest correct and reasonably efficient solution wins.

**Examples:**

Puzzle (7x7):

```
2 2  1
 1  4 3
3  2
    4
 3 2  3
1
 3  4 2

```

Solution:

```
2─2──1
│1──4─3
3──2║ ║
│  │4 ║
│3─2║ 3
1║  ║ │
 3──4─2

```

Puzzle (25x25):

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

```

Solution:

```
2─2─2──2  1 1─2─2──2──2─2
│      │  │1─3═5══4══4─2│
2  2─4─5══5═4═2│2──1 │ │3
│ 2│ ║1│ 1─3═3─2│    │ 2║
│ ║3═4│4══4─4═5─4─3──2 │3
2 4═5─4│  │ │ ║ │ │2───3│
│2─1║ ║4─2│ 4─3 │ 1│ 1 │2
2│1─3 ║║ │1 ║1──6══4 │ 2│
│3─2──4║ 3══6─3 ║  │ │ │2
2│2═3 │3──2 │ ║ 5─2│ 4─3│
│2─1│ │   │ │ ║ ║ │1 ║ │2
│ 1─3─3─3─3─5═8═7═6──5═4│
2──3───1│1─2│ ║ │ ║    ││
 1 │ 1──5─1││ 4─5─6─3─1│2
1│ │1──2║  │2 │ ║ ║ │3═4│
│3─5═4 │4──3│ 3═8═7═5│1│2
2│ │ ║ 3│ 1│2──2║ │ ║1│1│
│2 │ ║ ║2 │2──2│5═7═6─3─3
3│ 3─6─3│ 5═3 │2│ ║2│2─3│
║2 │ ║  │ ║ │ 1│2─3║2│ ║2
3│ 4═6──4─5─5──3─3─5││1║│
│2 │ │1 │ │2║2──1│ ║1││3│
2│ │ 1│ │ 1║2│3══6═5─2││2
│2─3──4═4──4─2│  │    │1│
2─2──2─2──2─2─2  1  1─3─2

```

Additional puzzles can be found here.

# Answer
> 12 votes
## Haskell, 1074 characters

```
main=interact$unlines.(\f@(l:_)->let a=(length l,length f)in head.filter(網(0,0)a).計(0,0)a$f).lines
橋=結"─═"数;結=zip;網 置@(右,下) 域@(幅,高) 地|下>=高=實|右>=幅=網(0,下+1)域 地|目 置 地`含`島
 =折((&&).折((&&).not.(`含`島))實)實(潔 置 域 地)|實=網(右+1,下)域 地
導=[(種,動)|動<-[1,-1],種<-"─═│║"];潔 置 域 地=折(拡 置 域)(換 地 置 '0')導
拡 置 域(種,動)地|([地],置)<-続(行 置 種 動)域 種 動 種 地=潔 置 域 地|實=地
計 置@(右,下)域@(幅,高)地|下>=高=[地]|右>=幅=計(0,下+1)域 地|[価]<-目 置 地`価`島
 =見込(価-環 置 域 地)>>=折(\種->(fst.続(行 置 種 1)域 種 1' '=<<))[地]>>=計(右+1,下)域
 |實=計(右+1,下)域 地;見込 価|価<0=[]|価>4=[]|實=[[""],["─","│"],["─│","║","═"],["─║","═│"],["═║"]]!!価
続 置 域 種 動 空 地|存 置 域=建 置 域 種 動 空 地|實=([],置)
建 置 域 種 動 空 地|目 置 地`含`島=([地],置)|目 置 地==空=続(行 置 種 動)域 種 動 空(換 地 置 種)
 |實=([],置);存(右,下)(幅,高)|右>=0,幅>右,0<=下=高>下|實=not 實;環 置 域 地=折(環行 置 域 地)0導
環行 置 域 地(種,動)数|置<-行 置 種 動,存 置 域,事<-目 置 地,事==種,[価]<-事`価`(橋++桥)=数+価|實=数
行(右,下)種 数|種`含`橋=(右+数,下)|實=(右,下+数);目(右,下)地=地!!下!!右;島=結"12345678"数
換 地(右,下)事|(上に,線:下に)<-捌 下 地,(左,古:右)<-捌 右 線=上に++(左++(事:右)):下に
折=foldl.flip;捌 0覧=([],覧);捌 数(物:覧)|(一覧,他)<-捌(数-1)覧=(物:一覧,他);實=1>0;数=[1..]
価 _[]=[];価 事((物,数):覧)|事==物=[数]|實=価 事 覧;含 事 覧|[_]<-価 事 覧=實|實=1<0;桥=結"│║"数

```

---

Originally, I had it even more purely Japanese by also implementing the primitive functions in terms of simple pattern matching and list combinations:

## Haskell, 1192

```
main=interact$unlines.(\f@(l:_)->let a=(length l,length f)in head.filter(網(0,0)a).計(0,0)a$f).lines
橋=結合"─═"数;結合 []_=[];結合(事:覧)(物:一覧)=(事,物):結合 覧 一覧
網 置@(右,下) 域@(幅,高) 地|下>=高=實|右>=幅=網(0,下+1)域 地|目 置 地`含`島
 =折る((&&).折る((&&).反対.(`含`島))實)實(潔 置 域 地)|實=網(右+1,下)域 地
導=[(種,動)|動<-[1,-1],種<-"─═│║"];潔 置 域 地=折る(拡 置 域)(換 地 置 '0')導
拡 置 域(種,動)地|([地],置)<-続(行 置 種 動)域 種 動 種 地=潔 置 域 地|實=地
計 置@(右,下)域@(幅,高)地|下>=高=[地]|右>=幅=計(0,下+1)域 地|[価]<-目 置 地`価`島
 =見込(価-環 置 域 地)>>=折る(\種->(一.続(行 置 種 1)域 種 1' '=<<))[地]>>=計(右+1,下)域
 |實=計(右+1,下)域 地;見込 価|価<0=[]|価>4=[]|實=[[""],["─","│"],["─│","║","═"],["─║","═│"],["═║"]]!!価
続 置 域 種 動 空 地|存 置 域=建 置 域 種 動 空 地|實=([],置)
建 置 域 種 動 空 地|目 置 地`含`島=([地],置)|目 置 地==空=続(行 置 種 動)域 種 動 空(換 地 置 種)
 |實=([],置);存(右,下)(幅,高)|右>=0,幅>右,0<=下=高>下|實=反対 實;環 置 域 地=折る(環行 置 域 地)0導
環行 置 域 地(種,動)数|置<-行 置 種 動,存 置 域,事<-目 置 地,事==種,[価]<-事`価`結 橋 桥=数+価|實=数
行(右,下)種 数|種`含`橋=(右+数,下)|實=(右,下+数);一(第,第二)=第;目(右,下)地=地!!下!!右;島=結合"12345678"数
換 地(右,下)事|(上に,線:下に)<-捌 下 地,(左,古:右)<-捌 右 線=結 上に(結 左(事:右):下に);変 関[]=[]
変 関(物:覧)=関 物:変 関 覧;折る 関 物[]=物;折る 関 物(事:覧)=折る 関(関 事 物)覧;捌 0覧=([],覧)
捌 数(物:覧)|(一覧,他)<-捌(数-1)覧=(物:一覧,他);實=1>0;反対 真|真=1<0|實=實;数=[1..];結=(++)
価 _[]=[];価 事((物,数):覧)|事==物=[数]|實=価 事 覧;含 事 覧|[_]<-価 事 覧=實|實=1<0;桥=結合"│║"数

```

---

```
$ make ;   def0 +RTS -M1g < test-25x25.txt
ghc -o bin/def0 golfed0.hs -rtsopts -O2
[1 of 1] Compiling Main             ( golfed0.hs, golfed0.o )
Linking bin/def0 ...
2─2─2──2  1 1─2─2──2──2─2
│      │  │1─3═5══4══4─2│
2  2─4─5══5═4═2│2──1 │ │3
│ 2│ ║1│ 1─3═3─2│    │ 2║
│ ║3═4│4══4─4═5─4─3──2 │3
...

```

runs in ≈3 minutes on my *i5*.

---

Commented version:
```
type Board = [[Char]]
type Location = (Int,Int)
type BoardDimensions = (Int,Int)

main=interact$unlines.(\f@(l:_)
  ->let a=(length l,length f)  -- dimensions of the field from the input
     in head.filter(網(0,0)a)   --   ↙−   determine all possible ways to build bridges
  {-                ↑      -}   .計(0,0)a $ f                                         ).lines
     -- and use the first that is simply connected.

 --  islands,            bridges
島=結合"12345678"数;  橋=結合"─═"数;  桥=結合"│║"数;               数=[1..]
 -- each with the associated "value" from the natural numbers _↗

     -- plan & commit the building of bridges
計 :: Location -> BoardDimensions -> Board -> [Board]
計    置@(右,下)   域@(幅,高)          地
 |下>=高=[地]        -- Walk over the board until every location was visited.
 |右>=幅=計(0,下+1)域 地
 |[価]<-目 置 地`価`島      -- When there is an island, read it's "value" 価
    =見込(価-環 置 域 地)  -- substract the value of the already-built bridges; fetch the ways to build bridges with the remaining value
     >>=折る(\種->(一.続(行 置 種 1)域 種 1' '=<<))[地]  -- for each of these ways, try to build a bridge.
      >>=計(右+1,下)域    -- for every possibility where that was successful, go on with the resultant board.
 |實=計(右+1,下)域 地

  -- Ways to build bridges with value 価:
見込 :: Int -> [[Char]]
見込    価
 |価<0=[]   -- not possible to build bridges with negative value
 |価>4=[]   -- nor with value >4  (we're always building south- / eastwards)
 |實=[ [""]      -- value 0
     ,["─","│"]  -- value 1
     ,["─│","║","═"],["─║","═│"],["═║"]]!!価  -- ... and so on

 -- continue, if Location is on the board, with the building of a bridge of type 種
続 :: Location -> BoardDimensions -> Char -> Int -> Char -> Board -> ([Board],Location)
続    置          域                  種      動      空      地
 |存 置 域=建 置 域 種 動 空 地
 |實=([],置)

      -- build that bridge,
建 :: Location -> BoardDimensions -> Char -> Int -> Char -> Board -> ([Board],Location)
建    置          域                  種      動      空      地
 |目 置 地`含`島=([地],置)  -- but if we've reached an island we're done
 |目 置 地==空 -- if we're in water or what else (空, can also take on the value of 種 if we only want to check if the bridge is already there)
    =続(行 置 種 動)域 種 動 空(換 地 置 種) -- place (換) the bridge and go (行く) to the next location
 |實=([],置)  -- if we've reached something else (i.e. crossing bridges), return no result.

     -- number of connections present at location 置
環 :: Location -> BoardDimensions -> Board -> Int
環 置 域 地=折る(環行 置 域 地)0導  -- for all neighbouring positions
環行 置 域 地(種,動)数
 |置<-行 置 種 動,存 置 域   -- if they're on the board
 ,事<-目 置 地,事==種    --   and there's a bridge in the correct direction
 ,[価]<-事`価`結 橋 桥=数+価  -- check its value and sum it to the previous ones
 |實=数   -- if there's no bridge there, don't sum anything

導=[(種,動)|動<-[1,-1],種<-"─═│║"]     -- directions to go

--     --     --     --     --     --     --     --     --     --     --     --

     -- test for connectedness:
網 :: Location -> BoardDimensions -> Board -> Bool
網    置@(右,下)      域@(幅,高)         地      -- Walk over the board until an island is
 |下>=高=實                                    -- found. 潔 marks all islands connected to
 |右>=幅=網(0,下+1)域 地                        -- that island; then check if any unmarked
 |目 置 地`含`島=折る((&&).折る((&&).反対.(`含`島))實)實(潔 置 域 地)  -- islands are left in the
 |實=網(右+1,下)域 地                                                          -- result.

         -- mark islands connected to the one at 置:
潔 :: Location -> BoardDimensions -> Board -> Board
潔    置           域                 地    =折る(拡 置 域)(換 地 置 '0')[(種,動)|動<-[1,-1],種<-"─═│║"]
 -- mark the island at 置 with '0', then, for all the possible ways to go...
     -- Proceed with the marking in some direction
拡 :: Location -> BoardDimensions -> (Char,Int) -> Board -> [[Char]]
拡 置 域(種,動)地     -- if an island is found in the given direction, give control to 潔 there
 |([地],置)<-続(行 置 種 動)域 種 動 種 地=潔 置 域 地
 |實=地   -- if none is found (i.e. there was no bridge), just return the board without further marking

--     --     --     --     --     --     --     --     --     --     --     --
-- Primitives:

存 :: Location -> BoardDimensions -> Bool
存(右,下)(幅,高)|右>=0,幅>右,0<=下=高>下|實=反対 實  -- check if (右,下) is on the board

行 :: Location -> Char->Int -> Location
行(右,下)種 数|種`含`橋=(右+数,下)|實=(右,下+数)   -- go in some direction (determined by where 種 leads to)

目 :: Location -> Board -> Char
目(右,下)地=地!!下!!右          -- lookup what's at location (右,下)

   -- replace what's at (右,下) with 事
換 :: Board -> Location -> Char -> Board
換 地(右,下)事|(上に,線:下に)<-捌 下 地,(左,古:右)<-捌 右 線=結 上に(結 左(事:右):下に)

変 :: (a -> b) -> [a] -> [b]
変 関[]=[]                       -- Standard Haskell map function (just noticed I didn't actually use it at all)
変 関(物:覧)=関 物:変 関 覧

折る :: (b -> a -> a) -> a -> [b] -> a
折る 関 物[]=物                            -- equivalent 折る=foldl.flip
折る 関 物(事:覧)=折る 関(関 事 物)覧

捌 0覧=([],覧)
捌 数(物:覧)|(一覧,他)<-捌(数-1)覧=(物:一覧,他)   -- splitAt

實=1>0           --true

反対 真|真=1<0|實=實  -- not

結=(++)     -- list linking

一(第,第二)=第    -- fst

価 :: Eq a => a -> [(a,b)] -> [b]
価 _[]=[]                             -- lookup function
価 事((物,数):覧)|事==物=[数]|實=価 事 覧

含 :: Eq a => a -> [(a,b)] -> Bool
含 事 覧|[_]<-価 事 覧=實|實=1<0      -- equivalent 含 x = elem x . map fst

結合 []_=[]                          -- zip
結合(事:覧)(物:一覧)=(事,物):結合 覧 一覧

```

# Answer
> 6 votes
## Python, 1079 chars

```
import sys,re,copy
A=sys.stdin.read()
W=A.find('\n')+1
r=range
V={}
E=[]
for i in r(len(A)):
 if'0'<A[i]<'9':V[i]=int(A[i])
 for d in(1,W):m=re.match('[1-8]( +)[1-8]',A[i::d]);E+=[[i,i+len(m.group(1))*d+d,d,r(3)]]if m else[]
def S(E):
 q,t=0,1
 while q!=t:
  for e in E:
   if any(d[0]and e[3][0]==0and any(i in r(a+c,b,c)for i in r(e[0]+e[2],e[1],e[2]))for a,b,c,d in E):e[3]=[0]
  for i in V:
   m=sum(min(e[3])for e in E if i in e[:2]);n=sum(max(e[3])for e in E if i in e[:2])
   if m>V[i]or n<V[i]:return
   for e in E:
    if m+2>V[i]and i in e[:2]:e[3]=e[3][:V[i]-m+1]
    if n-2<V[i]and i in e[:2]:e[3]=e[3][V[i]-n-1:]
  t=q;q=sum(len(e[3])for e in E)
 Q=[min(V)]
 i=0
 while Q[i:]:
  x=Q[i];i+=1
  for e in E:
   if x in e[:2]:
    if sum(e[3]):
     for y in e[:2]:
      if y not in Q:Q+=[y]
 if len(Q)!=len(V):return
 U=[e for e in E if e[3][1:]]
 if U:
  for w in U[0][3]:U[0][3]=[w];S(copy.deepcopy(E))
 else:
  B=A
  for a,b,c,d in E:
   if d[0]:
    for i in r(a+c,b,c):B=B[:i]+[{1:'─',W:'│'},{1:'═',W:'║'}][d[0]-1][c]+B[i+1:]
  print(B)
  sys.exit(0)
S(E)

```

The code does a pretty straightforward exhaustive search in `S`, using some constraint propagation to make it run in a reasonable time. `E` represents the current set of edges, in the format *\[from,to,delta,possible weights\]*. *from* and *to* are island identifiers and *delta* is either 1 for horizontal edges or *W* (=width of lines) for vertical edges. *possible weights* is a sublist of *\[0,1,2\]* encoding the current known state of that edge (0=no bridge, 1 = single bridge, 2 = double bridge).

`S` does three things. First it propagates information, like if one edge no longer has a 0 weight as a possibility, then all edges that cross it are eliminated (their possible weights are set to \[0\]). Similarly, if the sum of the minimum weight for edges incident on an island equals the island's weight, then all of those edges are set to their minimum.

Second, `S` checks that the graph is still connected using non \[0\] edges (the `Q` computation).

Finally, `S` picks an edge that is still not fully determined and calls itself recursively, setting that edge to one of its remaining possibilities.

Takes about 2 minutes for the biggest example.

# Answer
> 3 votes
## C# - ~~6601~~ ~~5661~~ 2225

```
using System;using System.Collections.Generic;using Google.OrTools.ConstraintSolver;
using System.Linq;namespace A{class N{public int R,C,Q;public bool F;public N(int r,
int c,int q){R=r;C=c;Q=q;}}class E{private static int i;public N A,B;public int I;
public E(N a,N b){A=a;B=b;I=i++;}}class H{public void G(string i){var o=P(i);var g=
new List<E>();foreach(var m in o){var r=o.Where(x=>x.R==m.R&&x.C>m.C).OrderBy(x=>x.C)
.FirstOrDefault();if(r!=null){g.Add(new E(m,r));}var d=o.Where(x=>x.C==m.C&&x.R>m.R)
.OrderBy(x=>x.R).FirstOrDefault();if(d!=null){g.Add(new E(m,d));}}var s=new Solver("H")
;int n=g.Count;var k=s.MakeIntVarArray(n,0,2);foreach(var j in o){var w=j;var y=g.Where
(x=>x.A==w||x.B== w).Select(x=>k[x.I]).ToArray();s.Add(s.MakeSumEquality(y,j.Q));}
foreach(var u in g.Where(x=>x.A.R==x.B.R)){var e=u;var v=g.Where(x=>x.A.R<e.A.R&&x.B.R
>e.A.R&&x.A.C>e.A.C&&x.A.C< e.B.C);foreach (var f in v){s.Add(s.MakeEquality(k[e.I]*k[f.
I],0));}}if(o.Count>2){foreach(var e in g.Where(x=>x.A.Q==2&&x.B.Q==2)){s.Add(k[e.I]<=1)
;}foreach(var e in g.Where(x=>x.A.Q==1&&x.B.Q==1)){s.Add(k[e.I]==0);}}var z=s.MakePhase
(k,0,0);s.NewSearch(z);int c=0;while(s.
NextSolution()){if(C(k,o,g)){N(k,o,g);Console.WriteLine();c++;}}Console.WriteLine(c);}
bool C(IntVar[]t,List<N>d,List<E>g){var a=d[0];a.F=true;var s=new Stack<N>();s.Push(a);
while(s.Any()){var n=s.Pop();foreach(var e in g.Where(x=>x.A==n||x.B==n)){var o=e.A==n?
e.B:e.A;if(t[e.I].Value()>0&&!o.F){o.F=true;s.Push(o);}}}bool r=d.All(x=>x.F);foreach
(var n in d){n.F=false;}return r;}void N(IntVar[]t,IList<N>n,List<E>e){var l=new
List<char[]>();for(int i=0;i<=n.Max(x=>x.R);i++){l.Add(new string(' ',n.Max(x=>x.C)+1)
.ToCharArray());}foreach(var o in n){l[o.R][o.C]=o.Q.ToString()[0];N d=o;foreach(var
g in e.Where(x=>x.A==d)){var v=t[g.I].Value();if(v>0){char p;int c;if(g.B.R==o.R){p=v==1
?'─':'═';c=o.C+1;var r=l[o.R];while(c<g.B.C){r[c]=p;c++;}}else{p=v==1?'│':'║';c=o.R+1;
while(c<g.B.R){l[c][o.C]=p;c++;}}}}}foreach(var r in l){Console.WriteLine(new string(r))
;}}List<N>P(string s){var n=new List<N>();int r=0;foreach(var l in s.Split(new[]{'\r',
'\n'},StringSplitOptions.RemoveEmptyEntries)){for(int c=0;c<l.Length;c++){if(l[c]!=' '
){n.Add(new N(r,c,l[c]-'0'));}}r++;}return n;}}}

```

Not particularly well-golfed. Uses constraint programming library from google or-tools. Builds constraints for total edge counts and to eliminate crossing bridges, but it is a bit harder to define constrains to ensure they are all connected. I did add logic to prune 2=2 and 1-1 components, but I still have to go through the final list (39 on the large one) and eliminate those which are not fully connected. Works pretty fast. Takes only a couple seconds on largest example. Ungolfed:

```
using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;
using System.Linq;
namespace Hashi
{
    public class Node
    {
        public int Row, Col, Req;
        public bool Flag;

        public Node(int r, int c, int q)
        {
            Row = r;
            Col = c;
            Req = q;
        }
    }
    public class Edge
    {
        private static int idx = 0;
        public Node A, B;
        public int Index;
        public Edge(Node a, Node b)
        {
            A = a;
            B = b;
            Index = idx++;
        }
    }
    public class HashiSolver
    {
        public void Go(string input)
        {
            IList<Node> nodes = Parse(input);
            var edges = new List<Edge>();
            //add edges between nodes;
            foreach (var node in nodes)
            {
                var r = nodes.Where(x => x.Row == node.Row && x.Col > node.Col).OrderBy(x => x.Col).FirstOrDefault();
                if (r != null)
                {
                    edges.Add(new Edge(node, r));
                }
                var d = nodes.Where(x => x.Col == node.Col && x.Row > node.Row).OrderBy(x => x.Row).FirstOrDefault();
                if (d != null)
                {
                    edges.Add(new Edge(node, d));
                }
            }
            var solver = new Solver("Hashi");
            int n = edges.Count;
            var toSolve = solver.MakeIntVarArray(n, 0, 2);
            //add total node edge total constraints
            foreach (var node in nodes)
            {
                var node1 = node;
                var toConsider = edges.Where(x => x.A == node1 || x.B == node1).Select(x => toSolve[x.Index]).ToArray();
                solver.Add(solver.MakeSumEquality(toConsider, node.Req));
            }
            //add crossing edge constraints
            foreach (var ed in edges.Where(x => x.A.Row == x.B.Row))
            {
                var e = ed;
                var conflicts = edges.Where(x => x.A.Row < e.A.Row &&
                                                 x.B.Row > e.A.Row &&
                                                 x.A.Col > e.A.Col &&
                                                 x.A.Col < e.B.Col);
                foreach (var conflict in conflicts)
                {
                    solver.Add(solver.MakeEquality(toSolve[e.Index] * toSolve[conflict.Index], 0));
                }
            }
            if (nodes.Count > 2)
            {
                //remove 2=2 connections
                foreach (var e in edges.Where(x => x.A.Req == 2 && x.B.Req == 2))
                {
                    solver.Add(toSolve[e.Index] <= 1);
                }
                //remove 1-1 connections
                foreach (var e in edges.Where(x => x.A.Req == 1 && x.B.Req == 1))
                {
                    solver.Add(toSolve[e.Index] == 0);
                }
            }
            var db = solver.MakePhase(toSolve, Solver.INT_VAR_DEFAULT, Solver.INT_VALUE_DEFAULT);
            solver.NewSearch(db);
            int c = 0;
            while (solver.NextSolution())
            {
                if (AllConnected(toSolve, nodes, edges))
                {
                    Print(toSolve, nodes, edges);
                    Console.WriteLine();
                    c++;
                }
            }
            Console.WriteLine(c);
        }
        private bool AllConnected(IntVar[] toSolve, IList<Node> nodes, List<Edge> edges)
        {
            var start = nodes[0];
            start.Flag = true;
            var s = new Stack<Node>();
            s.Push(start);
            while (s.Any())
            {
                var n = s.Pop();
                foreach (var edge in edges.Where(x => x.A == n || x.B == n))
                {
                    var o = edge.A == n ? edge.B : edge.A;
                    if (toSolve[edge.Index].Value() > 0 && !o.Flag)
                    {
                        o.Flag = true;
                        s.Push(o);
                    }
                }
            }
            bool r = nodes.All(x => x.Flag);
            foreach (var n in nodes)
            {
                n.Flag = false;
            }
            return r;
        }
        private void Print(IntVar[] toSolve, IList<Node> nodes, List<Edge> edges)
        {
            var l = new List<char[]>();
            for (int i = 0; i <= nodes.Max(x => x.Row); i++)
            {
                l.Add(new string(' ', nodes.Max(x => x.Col) + 1).ToCharArray());
            }
            foreach (var node in nodes)
            {
                l[node.Row][node.Col] = node.Req.ToString()[0];
                Node node1 = node;
                foreach (var edge in edges.Where(x => x.A == node1))
                {
                    var v = toSolve[edge.Index].Value();
                    if (v > 0)
                    {
                        //horizontal
                        if (edge.B.Row == node.Row)
                        {
                            char repl = v == 1 ? '─' : '═';
                            int col = node.Col + 1;
                            var r = l[node.Row];
                            while (col < edge.B.Col)
                            {
                                r[col] = repl;
                                col++;
                            }
                        }
                        //vertical
                        else
                        {
                            char repl = v == 1 ? '│' : '║';
                            int row = node.Row + 1;
                            while (row < edge.B.Row)
                            {

                                l[row][node.Col] = repl;
                                row++;
                            }
                        }
                    }
                }
            }
            foreach (var r in l)
            {
                Console.WriteLine(new string(r));
            }
        }
        private IList<Node> Parse(string s)
        {
            var n = new List<Node>();
            int row = 0;
            foreach (var line in s.Split(new[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries))
            {
                for (int col = 0; col < line.Length; col++)
                {
                    if (line[col] != ' ')
                    {
                        n.Add(new Node(row, col, line[col] - '0'));
                    }
                }
                row++;
            }
            return n;
        }

    }
}

```

---
Tags: code-golf
---


title: Make something tasty!

text:
# Question
Title: Make something tasty!
Your challenge is to write a Chef program that works well as a recipe and also as a program. Its utility as a recipe is strictly required (I don't want a recipe for grapeleaves in chocolate-mustard sauce); its utility as a program is a looser requirement, so that it is enough to print something interesting (the first few integers, for example, or "just another chef", or "just another Chef hacker", or "hello world") or do some helpful calculation (printing the sum of two numbers, for example). Votes should take this into account, and the winner is the program with the most net upvotes after some time.

(Code length is not important here.)

# Answer
I wrote this program for another challenge, but I decided to try and make it a valid answer for this one too:

```
Shirred Eggs.

This recipe prints the number 2 and, in doing so, yields two delicious
shirred eggs.

Ingredients.
2 eggs

Cooking time: 12 minutes.

Pre-heat oven to 175 degrees Celsius.

Method.
Put eggs into mixing bowl. Pour contents of the mixing bowl into the
baking dish. Shirr the eggs. Bake the eggs until shirred.

Serves 1.

```

As I mentioned in the other answer, it seems pretty hard to write anything in Chef that involves something more complicated than mixing stuff in a bowl and baking it, and still have it work both as a program and as a recipe.

**Edit:** Changed the recipe from fried to shirred eggs — thanks to Blazer for the suggestion! The cooking time and temperature should be considered advisory only; I haven't actually tried the recipe yet myself, so I can't vouch for their accuracy.
> 6 votes

---
Tags: popularity-contest
---


# Question
Title: Play a valid chess move, given a board on stdin
The program plays white.

Example stdin:

```
8 ║♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜
7 ║♟ ♟ ♟ ♟ … ♟ ♟ ♟
6 ║… … … … … … … …
5 ║… … … … ♟ … … …
4 ║… … … … … … … …
3 ║… … ♘ … … … … …
2 ║♙ ♙ ♙ ♙ ♙ ♙ ♙ ♙
1 ║♖ … ♗ ♕ ♔ ♗ ♘ ♖
——╚═══════════════
—— a b c d e f g h

```

Example stdout:

```
8 ║♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜
7 ║♟ ♟ ♟ ♟ … ♟ ♟ ♟
6 ║… … … … … … … …
5 ║… … … … ♟ … … …
4 ║… … … … ♙ … … …
3 ║… … ♘ … … … … …
2 ║♙ ♙ ♙ ♙ … ♙ ♙ ♙
1 ║♖ … ♗ ♕ ♔ ♗ ♘ ♖
——╚═══════════════
—— a b c d e f g h

```

Any valid move is ok. "En passant" and castling are ignored. It is ok to show error messages or print nothing if there is no valid move.

The answer with the most votes wins.

# Answer
> 17 votes
*I'm not complaining about upvotes, but to be fair... my solution here isn't actually all that great. Ugoren's is better, apart from lacking unicode support. Be sure to look at all the answers before voting, if you've come across this question only now!*
Anyway.

# Haskell, 1074 bytes (without castling)

```
χ=w⋈b;w="♙♢♤♔♕♖♗♘";b="♟♦♠♚♛♜♝♞"
μ=t⤀ζ++((\(x,y)->(x,-y))⤀)⤀μ;q c|((_,m):_)<-((==c).fst)☂(χ⋎μ)=m
t(x:y:l)=(d x,d y):t l;t _=[];d c=fromEnum c-78
ζ=["NM","NL","MMOM","MMMNMONMNOOMONOO",σ⋈δ,σ,δ,"MLOLPMPOOPMPLOLM"]
σ=l>>=(\c->'N':c:c:"N");δ=[l⋎l,reverse l⋎l]>>=(>>=(\(l,r)->[l,r]))
l="GHIJKLMOPQRSTU"
α c|c∊"♢♤"='♙'|c∊"♦♠"='♟'|c∊χ=c;π('♙':_)=6;π _=1
(⋎)=zip;(⤀)=map;(∊)=elem;(✄)=splitAt;(☂)=filter;(⋈)=(++)
φ r@(x,y)p a
 |x>7=φ(0,y+1)p a
 |y>7=[]
 |c<-a✠r=(c⌥r)p a y⋈φ(x+1,y)p a
(c⌥r)p a y
 |c==p!!0=(a☈r)c χ++const(y==π p)☂(a☈r)(p!!1)χ++(a☈r)(p!!2)('…':w)
 |c∊p=(a☈r)c χ
 |True=[]
a✠(x,y)=a!!y!!(x*2);o(x,y)=x>=0&&x<8&&y>=0&&y<8
(n➴a)(x,y)|(u,m:d)<-y✄a,(l,_:r)<-(x*2)✄m=u⋈(l⋈(n:r):d)
(a☈r@(x,y))c b=(α c➴('…'➴a)r)⤀((\r->o r&&not((a✠r)∊b))☂((\(ξ,υ)->(x+ξ,y+υ))⤀q c))
main=interact$unlines.uncurry((⋈).zipWith((⋈).(:" ║"))['8','7'..]
 .head.((all(any('♔'∊)).φ(0,0)b)☂).φ(0,0)w.(drop 3⤀)).(8✄).lines

```

Try it online!

---

When you have GHC installed (for instance as part of the Haskell platform) you can do just

```
$ runhaskell def0.hs < examplechessboard.txt
8 ║♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜
7 ║♟ ♟ ♟ ♟ … ♟ ♟ ♟
6 ║… … … … … … … …
5 ║… ♘ … … ♟ … … …
4 ║… … … … … … … …
3 ║… … … … … … … …
2 ║♙ ♙ ♙ ♙ ♙ ♙ ♙ ♙
1 ║♖ … ♗ ♕ ♔ ♗ ♘ ♖
——╚═══════════════
—— a b c d e f g h

```

# Answer
> 11 votes
## C, 734 672 640 characters

Characters counted without removable whitespace.
The file format I used is not as requested, but simplified ASCII.
I need to add Unicode character support, it would cost some characets.

```
char*r=" kpnbrq  KPNBRQ $ ,&)$wxy()879()8(6:GI(",B[256],*b=B,i;
e(x,d,m,V,c,r,n,p){
    for(r=0,p=b[x];m/++r;){
        n=x+d*r;
        if(p==2+8*(d<0)||n&136||!(b[n]?r=8,8^p^b[n]^8&&c&65^64:c&65^65)
            ? r=m,0
            : V?v(n,x):b[n]==1)
            return b[x]=0,b[n]=p%8-2||n/16%7?p:p+4;
    }
    return d>0&&e(x,-d,m,V,c);
}
d(x,v,m,i)char*m;{
    return(i=*m-40)?e(x,i%64,b[x]%8-2?b[x]&4?7:1:(x/16-1)%5|i%2?1:2,v,i)||d(x,v,m+1):0;
}
v(t,f){
    bcopy(B,b+=128,128);
    b[t]=b[f];b[f]=0;
    i=a(1,63);
    b=B;
    return!i;
}
a(c,n){
    return b[i=n*2-n%8]&&b[i]/8==c&&d(i,!c,r+r[b[i]%8+15]-10)||n--&&a(c,n);
}
main(){
    for(;gets(b);b+=8)for(;*b;b++)*b=strchr(r,*b)-r;b=B;
    for(i=64*!a(0,63);i<64;i++%8-7||puts(""))putchar(r[b[i*2-i%8]]);
}

```

Input/output file format:
Must be exactly 8 lines of exactly 8 characters. `pnbrqk` are used for white pieces, `PNBRQK` for black pieces, spaces for spaces:

```
RNBQKBNR
PPPP PPP

 n  P

pppppppp
r bqkbnr

```

The logic is quite simple:
For each possible move of each white piece, try each possible move of each black piece.
If no black move captures the white king, the white move is valid.

The board is maintained as `char[256]`, treated as a 16x16 matrix, where only the top-left 8x8 is used. Positions and movement vectors are kept in 8-bit integers (`x:4,y:4`). The extra bit allows using simple arithmetic (`new_pos = old_pos + steps*direction`), with easy detection of the board edge (`&0x88` does the magic). `r[]` encodes three things:

1. The first 15 bytes map internal piece codes (K=1,P=2,N=3,B=4,R=5,Q=6) to letters.
2. The next 6 bytes map internal piece codes to offsets in the last part (K and Q are the same, B is their tail).
3. The last 16 bytes encode the movement of all pieces, as `'('+vector`.

Functions:

1. `main` reads the board, converts letters to internal code, calls `a` to find white moves, prints the board.
2. `a`recursively loops over the 64 squares. For each piece of the right color (parameter `c`), it finds the movement rule for the piece and calls `d`.
3. `d` recursively loops over the encoded movement rule, which is a list of vectors, calling `e` for each one. It gives `e` the original position, the vector and the range limit (7 for pieces above B, 2 for second rank pawns, 1 otherwise).
4. `e` tests all movements along a vector. If the move is possible (i.e. pawns move forward, within board, not blocked, pawn capture diagonally), checks one of two things. For white moves, runs `v` to validate the move. For black moves, checks if the white king is captured. If true, the move is played on the board.
5. `v` validates a white move. It copies the board aside, executes the move to test, and calls `a` again, to look for black moves.

# Answer
> 5 votes
## Python 2.6, 886 \- 1425 characters

My initial version (in the revisions) came in at 886 characters but did not satisfy the spec completely (it did not check for avoiding checkmate ; it didn't even consider the possible moves of the black pieces).

Now it does (and I've fixed several bugs in the original). Alas this comes with a cost in characters: 1425 for now, but there should still be little room for improvement. This version should be a lot more solid in handling edge cases then the previous one.

```
#-*-coding:utf8-*-
import sys;e=enumerate
B,W=["♟","♜","♞","♝","♛","♚"],["♙","♖","♘","♗","♕","♔"]
R={"♙":[11,42],"♖":[28],"♘":[31],"♗":[8],"♕":[8,28],"♔":[1,21]}
def F(w):return sum([[(i,j)for j,p in e(o)if p==w]for i,o in e(Z)],[])
def G(x,y):
 P=Z[x][y];D=P in W;L=[]
 for o in R[P]if D else R[unichr(ord(P.decode('utf8'))-6).encode('utf8')]:
  r,k="%02d"%o
  for g,h in[[(-1,-1),(1,1),(-1,1),(1,-1)],[[(1,-1),(1,1)],[(-1,-1),(-1,1)]][D],[(-1,0),(1,0),(0,-1),(0,1)],[(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)],[(-1,0)]][int(r)]:
   J=0
   for i in range(int(k)):
    T=x+(i+1)*g;U=y+(i+1)*h
    if T<0 or T>7 or U<0 or U>7:break
    M=Z[T][U]
    if not J:L.append((T,U,P,M))
    else:break
    if r in"02"and(M in W+B):
     J=1
     if not((D and M in B)or(not D and M in W)):L.pop()
    elif(r=="1"and not((D and M in B)or(not D and M in W)))or(r=="4"and((i==1 and x!=6)or M!="…")):L.pop()
 return L
Z=[[y for y in l[5:].split()]for l in sys.stdin.readlines()[:-2]]
Q=[]
for p in R:
 for i,j in F(p):
  for M,L,c,_ in G(i,j):
   O=Z[M][L];Z[i][j]="…";Z[M][L]=c;E=[];map(E.extend,map(F,B))
   if not any(any(1 for _,_,_,I in G(v,h)if I==["♔","♚"][c in B])for v,h in E):Q.append((i,j,M,L,c))
   Z[i][j]=c;Z[M][L]=O
(x,y,X,Y,p)=Q[0];Z[x][y]="…";Z[X][Y]=p
for i,h in e(Z):print`8-i`+' ║'+' '.join(h)
print"——╚"+"═"*16+"\n—— a b c d e f g h"

```

Example input and output:

```
# INPUT

8 ║♜ ♞ ♝ … ♚ ♝ ♞ ♜
7 ║♟ ♟ ♟ ♟ … ♟ ♟ ♟
6 ║… … … … … … … …
5 ║… … … … ♟ … … …
4 ║… … … … … … ♙ ♛
3 ║… … … … … ♙ … …
2 ║♙ ♙ ♙ ♙ ♙ … ♙ …
1 ║♖ ♘ ♗ ♕ ♔ ♗ ♘ ♖
——╚═══════════════
—— a b c d e f g h

```

```
# OUTPUT

8 ║♜ ♞ ♝ … ♚ ♝ ♞ ♜
7 ║♟ ♟ ♟ ♟ … ♟ ♟ ♟
6 ║… … … … … … … …
5 ║… … … … ♟ … … …
4 ║… … … … … … ♙ ♛
3 ║… … … … … ♙ ♙ …
2 ║♙ ♙ ♙ ♙ ♙ … … …
1 ║♖ ♘ ♗ ♕ ♔ ♗ ♘ ♖
——╚════════════════
—— a b c d e f g h

```

---
Tags: popularity-contest, chess
---


# Question
Title: Implement strategy for Jacks or Better Video
You are dealt five cards from a single deck. Implement a strategy for Jacks or Better Video Poker that has an expected revenue of *at least* 99.46%. Output the cards you want to hold.

The shortest code wins.

You are not required to implement the suggested strategy. Optimum play is also acceptable.

**Input** is read from standard input, **output** is written to standard output. Cards are identified as pairs of number (2,...,9,T,J,Q,K,A) and suit (S,H,D,C - spades, hearts, diamonds, clubs): 3C - three of clubs, QH - queen of hearts.

Examples:

```
$ ./jacks                               |
3C JC 5C QC 3H                          |<< input
3C 3H                                   |<< output
$ ./jacks                               |
3C 4C 5C 6C 7C                          |<< input
3C 4C 5C 6C 7C                          |<< output

```

# Answer
I did it!!!

```
import java.io.*;
// 427 lines 200
public class Base {

    static char suit (String tokens) {  return  tokens.charAt (1); }
    public static char num (String tokens) { return tokens.charAt (0);}

    public static void checkPair (String [] tokens)
    {
        for (int a = 0; a < 4; ++a)
        for (int b = a+1; b < 5; ++b)
            if (num (tokens [a]) == num (tokens [b]))
                System.out.print (tokens [a] + " " + tokens [b]);
    }

    public static void checkThreeKind (String [] tokens)
    {
        for (int a = 0; a < 3; ++a)
            if (num (tokens [a]) == num (tokens [a+1]))
                for (int b = 2; b < 5; ++b)
                    if (num (tokens [a]) == num (tokens [b]))
                        System.out.print (tokens [a] + " " + tokens [a+1] + " " + tokens [b]);
    }

    static void checkTwoPair (String [] tokens)
    {
        for (int i = 0; i < 5; i++)
        for (int j = 1; j < 5; j++)
            //First Increment is pair 1 2, followed by 1 3, 1 4, and 1, 5 then 2 3, 2 4, 2 5, then 3 4, 3 5 then 4 5
            if (num (tokens [i]) == num (tokens [j]))
                for (int y = 0; y <= 4; y++)
                    for (int x = 1; x <= 4; x++)
                        if ((i != y) && (j != x) && (y != x) && (i != j))
                            if (num (tokens [y]) == num (tokens [x]))
                                if ((tokens [i] != tokens [j]) && (tokens [i] != tokens [y]) && (tokens [j] != tokens [y]) &&
                                        (tokens [i] != tokens [x]) && (tokens [j] != tokens [x]) && (tokens [y] != tokens [x]))
                                    eblock (tokens);
    }

    static void checkHighFlush (String [] tokens)
    {
        if (suit (tokens [0]) == suit (tokens [1]) &&
            suit (tokens [0]) == suit (tokens [2]) &&
            suit (tokens [0]) == suit (tokens [3]) &&
            suit (tokens [0]) == suit (tokens [4]))
        {
            String outputString = "";
            for (int i = 0; i < tokens.length; i++)
                outputString  += tokens [i] + " ";
            System.out.println (outputString);
            System.exit (0);
        }
        for (int i = 0; i <= 4; i++)
            for (int j= 1; j<= 4; j++)
                //First Increment is pair 1 2, followed by 1 3, 1 4, and 1, 5 then 2 3, 2 4, 2 5, then 3 4, 3 5 then 4 5
                if (suit (tokens [i]) == suit (tokens [j]))
                    for (int y = 0; y <= 4; y++)
                        for (int x = 1; x <= 4; x++)
                            if ((i != y) && (j != x) && (y != x) && (i != j))
                            {
                                if (suit (tokens [i]) == suit (tokens [x]) &&
                                        suit (tokens [i]) == suit (tokens [y]))
                                {
                                    if ((tokens [i] != tokens [j]) && (tokens [i] != tokens [y]) && (tokens [j] != tokens [y]) &&
                                            (tokens [i] != tokens [x]) && (tokens [j] != tokens [x]) && (tokens [y] != tokens [x]))
                                        eblock (tokens);
                                }
                            }
    }

     static void checkFourKind (String [] tokens)
     {
        if (num (tokens [0]) == num (tokens [1]))
        {
            if (num (tokens [0]) == num (tokens [2]))
                if (num (tokens [0]) == num (tokens [3]) || num (tokens [0]) == num (tokens [4]))
                    eblock (tokens);
            if (num (tokens [0]) == num (tokens [3]))
                if (num (tokens [0]) == num (tokens [4]))
                    eblock (tokens);
        }
        if (num (tokens [1]) == num (tokens [2]))
            if (num (tokens [1]) == num (tokens [3]))
                if (num (tokens [1]) == num (tokens [4]))
                    eblock (tokens);
    }

    static void checkStraight (String [] tokens)
    {
        int [] ints = new int [5];
        for (int i = 0; i <= 4; i++)
        {
            switch (num (tokens [i]))        {
            case 'T': ints [i] = 10;
            case 'J': ints [i] = 11;
            case 'Q': ints [i] = 12;
            case 'K': ints [i] = 13;
            case 'A': ints [i] = 14;
            default:  ints [i] = num (tokens [i]) - '0';
        }
        }
        for (int i = 0; i <= 3; i++)
        for (int j= 1; j<= 4; j++)
            //First Increment is pair 1 2, followed by 1 3, 1 4, and 1, 5 then 2 3, 2 4, 2 5, then 3 4, 3 5 then 4 5
            if ((ints [i]+1) == ints [i+1])
                for (int y = 0; y <= 4; y++)
                    for (int x = 1; x <= 4; x++)
                        if ((i != y) && (j != x) && (y != x) && (i != j))
                        {
                            if (ints[i] + 2 == ints[y] && ints[i] + 3 == ints [x])
                            {
                                if ((tokens [i] != tokens [j]) && (tokens [i] != tokens [y]) && (tokens [j] != tokens [y]) &&
                                        (tokens [i] != tokens [x]) && (tokens [j] != tokens [x]) && (tokens [y] != tokens [x]))
                                {
                                    for (int a : new int[] {i, j, y, x})
                                        System.out.print (tokens [a] + " ");
                                    System.out.println ();
                                    System.exit (0);
                                }
                            }
                            java.util.Arrays.sort (ints);
                            if (( (ints [i]+1 == ints [j]) && (ints [i]+3 == ints [y]) && (ints [i]+4 == ints [x])))
                            {
                                for (int a : new int[] {i, j, y, x})
                                    System.out.print (tokens [a] + " ");
                                System.out.println ();
                                System.exit (0);
                            }
                        }
    }

    static void checkHighCard (String [] tokens)
    {
        int [] ints = new int [5];
        for (int i = 0; i <= 4; i++)
        {
            switch (num (tokens [i]))        {
            case 'T': ints [i] = 10;
            case 'J': ints [i] = 11;
            case 'Q': ints [i] = 12;
            case 'K': ints [i] = 13;
            case 'A': ints [i] = 14;
            default:  ints [i] = num (tokens [i]) - '0';
        }
        }
        int marker = 0;
        if (ints [0] > ints [1]) marker = 1;
        if (ints [1] > ints [2]) marker = 2;
        if (ints [2] > ints [3]) marker = 3;
        if (ints [3] > ints [4]) marker = 4;
        System.out.println (tokens [marker]);
    }

    static void eblock (String[] tokens)
    {
        for (int i = 0; i < 5; i++)
            System.out.print (tokens [i] + " ");
        System.out.println ();
        System.exit (0);
    }

    static void checkFullHouse (String [] tokens)
    {
        String [] test = new String [5];
        int counter = 0;
        int sum = 0;

        for (int i = 0; i <= 4; i++)
        test [i] = tokens [i];
        for (int i = 0; i <=4; i++)
        {
        for (int j = 1; j <= 4; j++)
        {
            if (num (test [i]) == num (tokens [j]))
                counter++;
        }
        if (counter > 1)
            sum++;
        counter = 0;
        }
        if (sum == 5) eblock (tokens);
    }

    public static void main (String [] args) throws IOException
    {
        String inputString = new BufferedReader (new InputStreamReader (System.in)).readLine ();
        String [] tokens = inputString.split (" ");
        java.util.Arrays.sort (tokens);
        checkFourKind (tokens);
        checkHighFlush (tokens);
        checkFullHouse (tokens);
        checkStraight (tokens);
        checkTwoPair (tokens);
        checkThreeKind (tokens);
        checkPair (tokens);
        checkHighCard (tokens);
    }
}

```
> 3 votes

---
Tags: code-golf
---