Moderators: gmalivuk, Prelates, Moderators General
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
class Ship(object):
""" where a ship is, its length and how its oriented."""
def __init__(self, x, y, length, orientation):
self.x = x
self.y = y
self.length = length
self.orientation = orientation
def occupies(self):
"""work out all the places the ship takes up"""
if self.orientation == 'h':
return set( [ (self.x + i, self.y) for i in range(self.length) ])
elif self.orientation == 'v':
return set( [ (self.x, self.y + i) for i in range(self.length) ])
class Board(object):
""" keeps track of vacant positions, and placed ships"""
def __init__(self):
self.vacant = set([ (x, y) for x in range(10) for y in range(10)])
self.ships = []
def possibleplacements(self, length):
"""Given a length, returns a set of all ships with that length that
can be placed."""
places = []
for (x, y) in self.vacant:
hship = Ship(x, y, length, 'h')
vship = Ship(x, y, length, 'v')
if hship.occupies() <= self.vacant:
places.append(hship)
if vship.occupies() <= self.vacant:
places.append(vship)
return set(places)
def placeship(self, ship):
"""places a ship and updates .vacant"""
self.ships.append(ship)
self.vacant.difference(ship.occupies())
def popship(self):
"""removes last placed ship and updates .vacant"""
ship = self.ships.pop()
self.vacant.union(ship.occupies())
def howmanysetups( shiplengths = [2, 3, 3, 4, 5], thisboard = Board() ):
"""how many ways can ships with shiplenghts be placed on thisboard"""
if len(shiplengths) == 1:
return len( thisboard.possibleplacements(shiplengths[0]) )
else:
thislength = shiplengths.pop()
setups = 0
for ship in thisboard.possibleplacements(thislength):
thisboard.placeship(ship)
setups += howmanysetups( shiplengths, thisboard )
thisboard.popship()
return setups
>>> battleship.howmanysetups()
103860
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
This is clearly way too low. For a trivial lower bound, consider just placements in which each ship is oriented horizontally in its own row. There are then 10!/5! choices of rows for the ships, and 6*7*8*8*9 ways to place the five ships in their rows, for a lower bound of 731566080. (Divide by 2 if the two length-3 ships are indistinguishable.)jestingrabbit wrote:
This is assuming that the two length 3 are different. If they're the same, then its half that. So, if you pick a setup, then I have a 1 in 103860 chance of picking the same setup. Its a 1/103860 chance for that to happen.
You'd have to play 71990 times for that it to be more likely than not that it happens. That's a lot of battleship.
Edit: the program logic looks good, but I'd appreciate some confirmation... pls? Seems quite a bit lower than I'd've guessed.
Edit2: if you think about it, a ship has four orientations (heading north, south, east or west), which would make the total number of placements
32 * 103860 = 3323520.
class Ship(object):
""" where a ship is, its length and how its oriented."""
def __init__(self, x, y, length, orientation):
self.x = x
self.y = y
self.length = length
self.orientation = orientation
def occupies(self):
"""work out all the places the ship takes up"""
if self.orientation == 'h':
return [ (self.x + i, self.y) for i in range(self.length) ]
elif self.orientation == 'v':
return [ (self.x, self.y + i) for i in range(self.length) ]
def otherend(self):
if self.orientation == 'h':
return ( self.x + self.length - 1 , self.y )
else:
return ( self.x , self.y + self.length - 1 )
def shipclash( tryship , placedship ):
if tryship.orientation == placedship.orientation:
orientation = tryship.orientation
if orientation == 'h' and tryship.y == placedship.y:
if tryship.otherend()[0] < placedship.x or \
placedship.otherend()[0] < tryship.x:
return False, tryship.x + 1
else:
return True, placedship.otherend()[0] + 1
elif orientation == 'v' and tryship.x == placedship.x:
if tryship.otherend()[1] < placedship.y or \
placedship.otherend()[1] < tryship.y:
return False, tryship.y + 1
else:
return True, placedship.otherend()[1] + 1
else:
if orientation == 'h':
return False, tryship.x + 1
else:
return False, tryship.y + 1
else:
tryorientation = tryship.orientation
if tryorientation == 'h':
if placedship.y <= tryship.y <= placedship.otherend()[1] and \
tryship.x <= placedship.x <= tryship.otherend()[0]:
return True, placedship.x + 1
else:
return False, tryship.x + 1
elif tryorientation == 'v':
if placedship.x <= tryship.x <= placedship.otherend()[0] and \
tryship.y <= placedship.y <= tryship.otherend()[1]:
return True, placedship.y + 1
else:
return False, tryship.y + 1
def howmanysetups( unplacedlengths = [5, 4, 3, 3, 2], placedships = [] ):
"""how many ways can ships with shiplenghts be placed on thisboard"""
if unplacedlengths == []:
return 1
elif placedships == [] and unplacedlengths[0] == 5:
length = unplacedlengths[0]
otherlengths = unplacedlengths[1:]
setups = 0
orientation = 'h'
for x in range(3):
for y in range(5):
ship = Ship(x, y, length, orientation)
setups += howmanysetups(otherlengths, [ship])
print setups
return setups
else:
length = unplacedlengths[0]
otherlengths = unplacedlengths[1:]
setups = 0
orientation = 'h'
y = 0
while y < 10:
x = 0
while x < 10 - length + 1:
ship = Ship(x, y, length, orientation)
newx = x + 1
flag = False
for s in placedships:
flag, newx = shipclash(ship, s)
if flag:
break
if not flag:
setups += howmanysetups(otherlengths, placedships+[ship])
x = newx
y += 1
orientation = 'v'
x = 0
while x < 10:
y = 0
while y < 10 - length + 1:
ship = Ship(x, y, length, orientation)
newy = y + 1
flag = False
for s in placedships:
flag, newy = shipclash(ship, s)
if flag:
break
if not flag:
setups += howmanysetups(otherlengths, placedships+[ship])
y = newy
x += 1
if len(placedships)< 3:
print setups
return setups
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
gmalivuk wrote:I would assume that the important sense of "same setup" is that the same grid squares are hits in both setups.
class Ship(object):
""" where a ship is, its length and how its oriented."""
def __init__(self, x, y, length, orientation):
self.x = x
self.y = y
self.length = length
self.orientation = orientation
def occupies(self):
"""work out all the places the ship takes up"""
if self.orientation == 'h':
return [ (self.x + i, self.y) for i in range(self.length) ]
elif self.orientation == 'v':
return [ (self.x, self.y + i) for i in range(self.length) ]
def otherend(self):
if self.orientation == 'h':
return ( self.x + self.length - 1 , self.y )
else:
return ( self.x , self.y + self.length - 1 )
def shipclash( tryship , placedship ):
if tryship.orientation == placedship.orientation:
orientation = tryship.orientation
if orientation == 'h' and tryship.y == placedship.y:
if tryship.otherend()[0] < placedship.x or \
placedship.otherend()[0] < tryship.x:
return False, tryship.x + 1
else:
return True, placedship.otherend()[0] + 1
elif orientation == 'v' and tryship.x == placedship.x:
if tryship.otherend()[1] < placedship.y or \
placedship.otherend()[1] < tryship.y:
return False, tryship.y + 1
else:
return True, placedship.otherend()[1] + 1
else:
if orientation == 'h':
return False, tryship.x + 1
else:
return False, tryship.y + 1
else:
tryorientation = tryship.orientation
if tryorientation == 'h':
if placedship.y <= tryship.y <= placedship.otherend()[1] and \
tryship.x <= placedship.x <= tryship.otherend()[0]:
return True, placedship.x + 1
else:
return False, tryship.x + 1
elif tryorientation == 'v':
if placedship.x <= tryship.x <= placedship.otherend()[0] and \
tryship.y <= placedship.y <= tryship.otherend()[1]:
return True, placedship.y + 1
else:
return False, tryship.y + 1
def howmanysetups( unplacedlengths = [5, 4, 3, 3, 2], placedships = [] ):
"""how many ways can ships with shiplenghts be placed on thisboard"""
if unplacedlengths == []:
return 1
elif placedships == []:
length = unplacedlengths[0]
otherlengths = unplacedlengths[1:]
setups = 0
orientation = 'h'
for x in range(3):
for y in range(5):
ship = Ship(x, y, length, orientation)
setups += howmanysetups(otherlengths, [ship])
print setups
return 8*setups
else:
length = unplacedlengths[0]
otherlengths = unplacedlengths[1:]
setups = 0
orientation = 'h'
y = 0
while y < 10:
x = 0
while x < 10 - length + 1:
ship = Ship(x, y, length, orientation)
newx = x + 1
flag = False
for s in placedships:
flag, newx = shipclash(ship, s)
if flag:
break
if not flag:
setups += howmanysetups(otherlengths, placedships+[ship])
x = newx
y += 1
orientation = 'v'
x = 0
while x < 10:
y = 0
while y < 10 - length + 1:
ship = Ship(x, y, length, orientation)
newy = y + 1
flag = False
for s in placedships:
flag, newy = shipclash(ship, s)
if flag:
break
if not flag:
setups += howmanysetups(otherlengths, placedships+[ship])
y = newy
x += 1
if len(placedships)< 3:
print setups
return setups
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Bei einem Spiel mit einem Schiff der Länge 5, zwei Schiffen der Länge 4, drei Schiffen der Länge 3 und vier Schiffen der Länge 2 gibt es genau 26.509.655.816.984 (also ungefähr 26,5 Billionen) Möglichkeiten, die Schiffe aufzustellen.
csiko wrote:For a game with 1 ship of length 5, 2 ships of length 4, 3 ships of length 3, 4 ships of lenth 2 there are exactly 26509655816984 different setups.
The probability for two setups to be exactly the same is then 1 : 702761851534953628502856256
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
jestingrabbit wrote:From the rather bizarrely existent battleship wikia,
http://battleship.wikia.com/wiki/Battle ... %29#Trivia
there's an unsourced claim that there are 1,925,751,392 different configurations, with indistinguishable length 3s. That seems low.
jaap wrote:jestingrabbit wrote:From the rather bizarrely existent battleship wikia,
http://battleship.wikia.com/wiki/Battle ... %29#Trivia
there's an unsourced claim that there are 1,925,751,392 different configurations, with indistinguishable length 3s. That seems low.
The source for that may be one of the answers to this mathoverflow post (which includes Haskell source code).
Further answers can be found in the table found here, which also has the (same?) Haskell source code.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
>>> battleships2.howmanysetups( [2, 2], [] )
<snip>
31252
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
jestingrabbit wrote:And my code just finished, and its given the answer as
30,093,975,536
for distinct 3s.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
jestingrabbit wrote:And I expect that yours took minutes to execute rather than hours :oops:
sweetadeleiiine wrote:Hello, numbers gods.
I need someone to calculate the odds of two people (in this scenario they are drunk, though I don't know that matters for the math) setting up -exactly- identical Battleship game boards with no foreknowledge of their opponent's tactics. And you know, obviously without cheating.
This really happened to me back in 2006. Once I figured it out I won, but the real winning can happen today with your help! Please explain your answer. I'd figure all this out myself if I a) had the game to go from and b) more than an elementary grasp of mathematics.
Please and thank you!
<3 Adeleine
P.S. Extra points for converting odds to probability. Cheers!
Ships : Patterns
2 3 4 5
-------
0 0 0 0 : 1
0 0 0 1 : 120
0 0 1 0 : 140
0 0 1 1 : 14400
0 1 0 0 : 160
0 1 0 1 : 17040
0 1 1 0 : 20336
0 1 1 1 : 1850736
0 2 0 0 : 11884
0 2 0 1 : 1119936
0 2 1 0 : 1367720
0 2 1 1 : 109786464
1 0 0 0 : 180
1 0 0 1 : 19840
1 0 1 0 : 23532
1 0 1 1 : 2216256
1 1 0 0 : 27336
1 1 0 1 : 2667272
1 1 1 0 : 3237624
1 1 1 1 : 269056552
1 2 0 0 : 1924020
1 2 0 1 : 165673320
1 2 1 0 : 205885084
1 2 1 1 : 15046987768
2 0 0 0 : 15626
2 0 0 1 : 1579056
2 0 1 0 : 1904748
2 0 1 1 : 163929000
2 1 0 0 : 2249848
2 1 0 1 : 200730096
2 1 1 0 : 247911400
2 1 1 1 : 18772683816
2 2 0 0 : 149875428
2 2 0 1 : 11767281448
2 2 1 0 : 14886380364
2 2 1 1 : 988321903552
>>> battleship.howmanysetups([2, 2], thisboard = battleship.Board(nodiagonaladjacency = True) )
27904
>>> 27904/2
13952.0
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
sweetadeleiiine wrote:So, what is the number based on this?
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
jestingrabbit wrote:sweetadeleiiine wrote:So, what is the number based on this?
That would be 30,093,975,536 and the probability is 1/30,093,975,536 for this event to occur.
Tirian wrote:jestingrabbit wrote:sweetadeleiiine wrote:So, what is the number based on this?
That would be 30,093,975,536 and the probability is 1/30,093,975,536 for this event to occur.
Errrm, that would be assuming that we choose Battleship setups uniformly, and I suspect we don't at all.
Dason wrote:Tirian wrote:jestingrabbit wrote:sweetadeleiiine wrote:So, what is the number based on this?
That would be 30,093,975,536 and the probability is 1/30,093,975,536 for this event to occur.
Errrm, that would be assuming that we choose Battleship setups uniformly, and I suspect we don't at all.
Sure but what other assumption are you going to make? Anything else would need to be based on data which we don't really have.
Dason wrote:Sure but what other assumption are you going to make? Anything else would need to be based on data which we don't really have.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
undecim wrote:I conjecture 1/30,093,975,536 is a lower bound on the probability. Humans tend to share specific tendencies when making "random" decisions. Even though we don't know what those specific tendencies are, I don't think it's at all a stretch to say that a human is more likely to set a board identical to one created by another human than to set a board identical to one of the 30 Billion possible board selected uniformly at random.
dudiobugtron wrote:undecim wrote:I conjecture 1/30,093,975,536 is a lower bound on the probability. Humans tend to share specific tendencies when making "random" decisions. Even though we don't know what those specific tendencies are, I don't think it's at all a stretch to say that a human is more likely to set a board identical to one created by another human than to set a board identical to one of the 30 Billion possible board selected uniformly at random.
Depending on the players, you could certainly get two people who had a lower chance than 1/30,093,975,536, if they were biased towards different types of setup. But overall you are likely right.
Except that it is also an officially trademarked game sold by a particular company along with a particular set of rules. This isn't changed by your ability to play pen-and-paper variants of the game.jestingrabbit wrote:Also, the game can be played with a few pieces of paper and some pens. So to speak of official rules is kinda crazy imo.
Users browsing this forum: No registered users and 8 guests