Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

This question already has an answer here:

Unsolved puzzle:

Example puzzle

Solved Puzzle:

Example puzzle solved

Rules

  • Each circle with number must have as many lines from it as the number in the circle.
  • It is not allowed to have more than two lines between two circles.
  • The lines can not cross each other.
  • All the lines must either be horizontal or vertical. It is not allowed to draw lines diagonally.
  • All lines must be connected.

Program Description

Write a program to input a bridges puzzle from a text file and output the solution

Input file guidelines

The input file must display a number for the number of bridges connected and . for whitespace.

Example:

2.2.5.2.
.....1.3
6.3.....
.2..6.1.
3.1..2.6
.2......
1.3.5..3
.2.3..2.

Output guidelines

Replace periods with

  • - single horizontal line
  • = double horizontal line
  • | single vertical line
  • $ double vertical line

From the data file above, you should get this as output:

2 2-5=2 
$ | $1-3
6=3 $  $
$2--6-1$
3|1 $2=6
|2| $  $
1|3=5--3
 2-3==2 
share|improve this question
    
You marked this as code golf, but I assume this is instead a programming challenge? –  AardvarkSoup Feb 16 '13 at 21:03
    
The person with the smallest letter count wins, it is a codegolf challenge –  Will Sherwood Feb 16 '13 at 23:56
    
Is a unique solution guaranteed? –  Gordon Bailey Feb 17 '13 at 1:17
    
Yes, a unique solution is guaranteed –  Will Sherwood Feb 17 '13 at 2:14
4  
looks like an exact duplicate of codegolf.stackexchange.com/q/4790/367 –  Geoff Reedy Feb 21 '13 at 3:52
show 1 more comment

marked as duplicate by Peter Taylor, Hasturkun, primo, Geoff Reedy, grc Feb 23 '13 at 2:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3 Answers

Python: 1303 Characters

This is some super ugly code, and it isn't particularly efficient, but I believe it works:

import sys
from itertools import product,combinations
e=[]
p=[[[0,(c,r,o,[])][c!='.'] for o,c in enumerate(l.strip())] for r,l in enumerate(open(sys.argv[1]))]
r=range(len(p))
c=range(len(p[0]))
for i,j in combinations(product(r,c),2):
 if p[i[0]][i[1]] and p[j[0]][j[1]]:
  if i[0]==j[0] and abs(i[1]-j[1])>1:
    b=1
    g=range(min(i[1],j[1])+1,max(i[1],j[1]))
    for x in g:
     if p[i[0]][x]:b=0
    if b:e+=[(i,j,[i[0]],g,1)]
  if i[1]==j[1] and abs(i[0]-j[0])>1:
    b=1
    g=range(min(i[0],j[0])+1,max(i[0],j[0]))
    for x in g:
     if p[x][i[1]]:b=0
    if b:e+=[(i,j,g,[i[1]],0)]
def s(v,i,m):
 if i>=len(v):
  return None
 for j in [2,1,0]:
  v[i]=j
  q=dict(m)
  b=1
  for l in [0,1]:
   n=e[i][l]
   if not n in q:q[n]=0
   q[n]+=j
   y=int(p[n[0]][n[1]][0])
   if q[n]>y:b=0
  if not b:continue
  a=[d for b in range(i+1) for d in product(e[b][2],e[b][3]) if v[b]>0]
  if len(a)!=len(set(a)):continue
  if i==len(v)-1:
   g=1
   for l,z in product(r,c):
    n=p[l][z]
    if not n:continue
    if q[(n[1],n[2])]!=int(n[0]):g=0
   if g:return v
  u=s(v,i+1,q)
  if u:return u
for i,v in zip(e,s([None]*len(e),0,{})):
 if v>0:
  for j,k in product(i[2],i[3]):p[j][k]=[[['|','$'][v-1],['-','='][v-1]][i[4]]]
for l in p:
 for c in l:
  if not c:c=[' ']
  sys.stdout.write(c[0])
 print ""

Example:

$ cat problem
4.4.1
.....
4.6.2
.....
..1..
$ python bridges.py problem
4=4-1
$ |  
4=6=2
  |  
  1
share|improve this answer
    
why open(sys.argv[1])? sys.stdin save you some chars. –  Ray Feb 21 '13 at 0:19
    
The result in your example doesn't match the input. –  Ray Feb 21 '13 at 3:14
    
@Ray: I used open(sys.argv[1]) because the instructions specifically said to take input from a file. It's easy enough to change though. As for the example, thanks for catching my mistake: I edited the example to make it a bit more interesting, but I accidentally only copy/pasted the updated output. I'll fix that now. –  ESultanik Feb 21 '13 at 13:48
add comment

Ruby, 414 characters

h=->l,s,v{l[s.index(v)||s.size]}
c=->r,f{r[f].to_i-h[[1,2,0],'|$',r[f-N]]-h[[1,2,0],'-=',r[f-1]]-h[[1,2,0],'-=',r[f+1]]}
s=->r{(f=r=~/\./)&&(m=h[[2,4,25,25,25,31],w='|$-= ',a=r[f-N]]&h[[7,7,8,16,7,31],w,r[f-1]]
a=~/\d/&&m&=(0>d=c[r,f-N])?0:d<1?25:d<2?2:d<3?4:0
' |$-='.chars{|k|m&1>0&&(r[f]=k;s[r]);m=m>>1};r[f]='.')||r[-N..-1]=~/^ +$/&&$><<r[N..-N].tr("0",$/)}
N=1+((t=STDIN.read)=~/$/)
s[$/*N+t.tr($/,"0")+"."*N]

Example:

2.2.5.2.
.....1.3
6.3.....
.2..6.1.
3.1..2.6
.2......
1.3.5..3
.2.3..2.

2 2-5=2
$ | $1-3
6=3 $  $
$2--6-1$
3|1 $2=6
|2| $  $
1|3=5--3
 2-3==2
share|improve this answer
    
The program will output some incorrect answers. Try this case: 1.2. .... ..1. –  Ray Feb 21 '13 at 15:35
    
@Ray You are right. Such strange things didn't happen in my tests. Will have a look into it. –  Howard Feb 21 '13 at 17:03
    
@Ray It's with the trailing newline of the input. If you omit that it works fine. I'll try to fix that. –  Howard Feb 21 '13 at 17:09
add comment

Python 3/ 1780C

This problem can be converted to the exact cover problem. We can use Knuth's AlgorithmX to solve the exact cover problem.

I'll post the details about converting from input data to a 0-1 matrix later. It's very interesting.

Solving exact cover problem with AlgorithmX is very fast. On my machine, the example was solved within 0.09 second, in 310 iterations. And the program can output all solutions.

import sys
from itertools import product as I
a=sys.stdin.read().split()
V=list
L=len
Z=enumerate
W=range
P=V(I(W(L(a)),W(L(a[0]))))
E={p:[]for p in P}
Q={(i,j):int(a[i][j])for i,j in P if'.'!=a[i][j]}
J=Q.items()
F=[]
for p,c in J:
 for i,j in((0,1),(1,0)):
  q=p[0]+i,p[1]+j;e=[p,0]
  while q in P:
   E[q]+=[e]
   if q in Q:e[1]=q;E[p]+=[e];F+=[e];break
   q=q[0]+i,q[1]+j
E={x:[x for x in y if x[1]!=0]for x,y in E.items()}
C=[E[p] for p in P if p not in Q and L(E[p])>1]
m=[]
T=L(Q)+4*L(F)+L(C)
s=0
l={}
for p,c in J:
 e=E[p];u=L(e)*2
 for t in I(*((0,1,2)for x in e)):
  if sum(t)!=c:continue
  r=[0]*T;r[s+u]=1
  for i,x in Z(t):k=s+i*2;r[k:k+2]=((1,1),(0,1),(0,0))[x]
  m+=[r]
 l[p]=s;s+=u+1
z=L(m)
for e in F:
 p,q=e;r=[0]*T;c,d=l[p]+E[p].index(e)*2,l[q]+E[q].index(e)*2;t=r[:];r[c]=r[d]=1
 for i,u in Z(C):r[T-L(C)+i]=int(e in u)
 t[c+1]=t[d+1]=1;m+=[r,t]

def I(x,d):
 y=d[x]
 while y!=x:yield y;y=d[y]
def A(c):
 L[R[c]],R[L[c]]=L[c],R[c]
 for x in I(c,D):
  for y in I(x,R):U[D[y]],D[U[y]]=U[y],D[y]
def B(c):
 for x in I(c,U):
  for y in I(x,L):U[D[y]],D[U[y]]=y,y
 L[R[c]],R[L[c]]=c,c
def S():
 c=R[h]
 if c==h:yield[]
 A(c)
 for r in I(c,D):
  for x in I(r,R):A(C[x])
  for t in S():yield[r[0]]+t
  for x in I(r,L):B(C[x])
 B(c)
L,R,U,D,C={},{},{},{},{}
h=T
L[h]=R[h]=D[h]=U[h]=h
for c in W(T):
 R[L[h]],R[c],L[h],L[c]=c,h,c,L[h];U[c]=D[c]=c
for i,l in Z(m):
 s=0
 for c in I(h,R):
  if l[c]:
   r=i,c;D[U[c]],D[r],U[c],U[r],C[r]=r,c,r,U[c],c
   if s==0:L[r]=R[r]=s=r
   R[L[s]],R[r],L[s],L[r]=r,s,r,L[s]
for s in S(): 
 b=V(map(V,a))
 for e in s:
  if e<z:continue
  (i,j),(x,y)=F[(e-z)//2]
  if j==y:
   for r in W(i+1,x):b[r][j]='|H'[b[r][j]=='|']
  else:
   for r in W(j+1,y):b[i][r]='-='[b[i][r]=='-']
 print('\n'.join(''.join(l)for l in b).replace('.',' '))
share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.