diff options
| -rw-r--r-- | 2017-battleships/.gitignore | 3 | ||||
| -rw-r--r-- | 2017-battleships/Cargo.lock | 122 | ||||
| -rw-r--r-- | 2017-battleships/Cargo.toml | 11 | ||||
| -rw-r--r-- | 2017-battleships/bot.json | 8 | ||||
| -rw-r--r-- | 2017-battleships/notes.org | 1447 | ||||
| -rw-r--r-- | 2017-battleships/readme.txt | 20 | ||||
| -rw-r--r-- | 2017-battleships/src/actions.rs | 90 | ||||
| -rw-r--r-- | 2017-battleships/src/files.rs | 57 | ||||
| -rw-r--r-- | 2017-battleships/src/knowledge.rs | 504 | ||||
| -rw-r--r-- | 2017-battleships/src/lib.rs | 67 | ||||
| -rw-r--r-- | 2017-battleships/src/main.rs | 19 | ||||
| -rw-r--r-- | 2017-battleships/src/math.rs | 338 | ||||
| -rw-r--r-- | 2017-battleships/src/placement.rs | 23 | ||||
| -rw-r--r-- | 2017-battleships/src/ships.rs | 216 | ||||
| -rw-r--r-- | 2017-battleships/src/shooting.rs | 47 | ||||
| -rw-r--r-- | 2017-battleships/src/state.rs | 146 |
16 files changed, 3118 insertions, 0 deletions
diff --git a/2017-battleships/.gitignore b/2017-battleships/.gitignore new file mode 100644 index 0000000..a41bb2d --- /dev/null +++ b/2017-battleships/.gitignore @@ -0,0 +1,3 @@ +/target + +/knowledge-state.json diff --git a/2017-battleships/Cargo.lock b/2017-battleships/Cargo.lock new file mode 100644 index 0000000..96ea518 --- /dev/null +++ b/2017-battleships/Cargo.lock @@ -0,0 +1,122 @@ +[root] +name = "worthebot_battleships" +version = "0.1.0" +dependencies = [ + "json 0.11.6 (registry+https://github.com/rust-lang/crates.io-index)", + "rand 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)", + "serde 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)", + "serde_derive 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)", + "serde_json 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "dtoa" +version = "0.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "itoa" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "json" +version = "0.11.6" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "libc" +version = "0.2.22" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "num-traits" +version = "0.1.37" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "quote" +version = "0.3.15" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "rand" +version = "0.3.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "libc 0.2.22 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "serde" +version = "1.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "serde_derive" +version = "1.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "quote 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)", + "serde_derive_internals 0.15.0 (registry+https://github.com/rust-lang/crates.io-index)", + "syn 0.11.11 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "serde_derive_internals" +version = "0.15.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "syn 0.11.11 (registry+https://github.com/rust-lang/crates.io-index)", + "synom 0.11.3 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "serde_json" +version = "1.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "dtoa 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)", + "itoa 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", + "num-traits 0.1.37 (registry+https://github.com/rust-lang/crates.io-index)", + "serde 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "syn" +version = "0.11.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "quote 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)", + "synom 0.11.3 (registry+https://github.com/rust-lang/crates.io-index)", + "unicode-xid 0.0.4 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "synom" +version = "0.11.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "unicode-xid 0.0.4 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "unicode-xid" +version = "0.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[metadata] +"checksum dtoa 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "80c8b71fd71146990a9742fc06dcbbde19161a267e0ad4e572c35162f4578c90" +"checksum itoa 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "eb2f404fbc66fd9aac13e998248505e7ecb2ad8e44ab6388684c5fb11c6c251c" +"checksum json 0.11.6 (registry+https://github.com/rust-lang/crates.io-index)" = "27600e8bb3b71bcc6213fb36b66b8dce60adc17a624257687ef5d1d4facafba7" +"checksum libc 0.2.22 (registry+https://github.com/rust-lang/crates.io-index)" = "babb8281da88cba992fa1f4ddec7d63ed96280a1a53ec9b919fd37b53d71e502" +"checksum num-traits 0.1.37 (registry+https://github.com/rust-lang/crates.io-index)" = "e1cbfa3781f3fe73dc05321bed52a06d2d491eaa764c52335cf4399f046ece99" +"checksum quote 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)" = "7a6e920b65c65f10b2ae65c831a81a073a89edd28c7cce89475bff467ab4167a" +"checksum rand 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)" = "022e0636ec2519ddae48154b028864bdce4eaf7d35226ab8e65c611be97b189d" +"checksum serde 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "991ef6be409a3b7a46cb9ee701d86156ce851825c65dbee7f16dbd5c4e7e2d47" +"checksum serde_derive 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "9fd81eef9f0b4ec341b11095335b6a4b28ed85581b12dd27585dee1529df35e0" +"checksum serde_derive_internals 0.15.0 (registry+https://github.com/rust-lang/crates.io-index)" = "021c338d22c7e30f957a6ab7e388cb6098499dda9fd4ba1661ee074ca7a180d1" +"checksum serde_json 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "48b04779552e92037212c3615370f6bd57a40ebba7f20e554ff9f55e41a69a7b" +"checksum syn 0.11.11 (registry+https://github.com/rust-lang/crates.io-index)" = "d3b891b9015c88c576343b9b3e41c2c11a51c219ef067b264bd9c8aa9b441dad" +"checksum synom 0.11.3 (registry+https://github.com/rust-lang/crates.io-index)" = "a393066ed9010ebaed60b9eafa373d4b1baac186dd7e008555b0f702b51945b6" +"checksum unicode-xid 0.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "8c1f860d7d29cf02cb2f3f359fd35991af3d30bac52c57d265a3c461074cb4dc" diff --git a/2017-battleships/Cargo.toml b/2017-battleships/Cargo.toml new file mode 100644 index 0000000..cdebbe8 --- /dev/null +++ b/2017-battleships/Cargo.toml @@ -0,0 +1,11 @@ +[package] +name = "worthebot_battleships" +version = "0.1.0" +authors = ["Justin Worthe <justin.worthe@gmail.com>"] + +[dependencies] +rand = "0.3" +json = "0.11.6" +serde = "1.0.4" +serde_json = "1.0.2" +serde_derive = "1.0.4"
\ No newline at end of file diff --git a/2017-battleships/bot.json b/2017-battleships/bot.json new file mode 100644 index 0000000..6245b49 --- /dev/null +++ b/2017-battleships/bot.json @@ -0,0 +1,8 @@ +{ + "Author":"Justin Worthe", + "Email":"justin.worthe@gmail.com", + "NickName" :"Admiral Worthebot", + "BotType": 8, + "ProjectLocation" : "", + "RunFile" : "target\\release\\worthebot_battleships.exe" +} diff --git a/2017-battleships/notes.org b/2017-battleships/notes.org new file mode 100644 index 0000000..ff3e319 --- /dev/null +++ b/2017-battleships/notes.org @@ -0,0 +1,1447 @@ +* State.json + +#+BEGIN_EXAMPLE +State = {PlayerMap, OpponentMap, GameVersion=String, GameLevel=u16, Round=u16, MapDimension=u16, Phase=u16, Player1Map=null, Player2Map=null} + +PlayerMap = {Cells=[PlayerCell], Owner, MapWidth=u16, MapHeight=u16} + +PlayerCell = {Occupied=bool, Hit=bool, X=u16, Y=u16} + +Owner = {FailedFirstPhaseCommands=u16, Name=String, Ships=[PlayerShip], Points=u16, Killed=bool, IsWinner=bool, ShotsFired=u16, ShotsHit=u16, ShipsRemaining=u16, Key=String} + +PlayerShip = {Cells=[PlayerCell], Destroyed=bool, Placed=bool, ShipType=String, Weapons=[PlayerWeapon], } + +PlayerWeapon = {WeaponType=String} + +OpponentMap = {Ships=[OpponentShip], Alive=bool, Points=u16, Name=String, Cells=[OpponentCell]} + +OpponentShip = {Destroyed=bool, ShipType=String} + +OpponentCell = {Damaged=bool, Missed=bool, X=u16, Y=u16} + +#+END_EXAMPLE + +* State.json example + +#+BEGIN_SRC json +{ + "PlayerMap": { + "Cells": [ + { + "Occupied": false, + "Hit": true, + "X": 0, + "Y": 0 + }, + { + "Occupied": false, + "Hit": false, + "X": 0, + "Y": 1 + }, + { + "Occupied": true, + "Hit": false, + "X": 0, + "Y": 2 + }, + { + "Occupied": true, + "Hit": false, + "X": 0, + "Y": 3 + }, + { + "Occupied": true, + "Hit": false, + "X": 0, + "Y": 4 + }, + { + "Occupied": false, + "Hit": false, + "X": 0, + "Y": 5 + }, + { + "Occupied": true, + "Hit": true, + "X": 0, + "Y": 6 + }, + { + "Occupied": true, + "Hit": true, + + "X": 0, + "Y": 7 + }, + { + "Occupied": true, + "Hit": false, + "X": 0, + "Y": 8 + }, + { + "Occupied": false, + "Hit": true, + "X": 0, + "Y": 9 + }, + { + "Occupied": false, + "Hit": false, + "X": 1, + "Y": 0 + }, + { + "Occupied": false, + "Hit": false, + "X": 1, + "Y": 1 + }, + { + "Occupied": false, + "Hit": false, + "X": 1, + "Y": 2 + }, + { + "Occupied": false, + "Hit": true, + "X": 1, + "Y": 3 + }, + { + "Occupied": false, + "Hit": false, + "X": 1, + "Y": 4 + }, + { + "Occupied": false, + "Hit": false, + "X": 1, + "Y": 5 + }, + { + "Occupied": false, + "Hit": false, + "X": 1, + "Y": 6 + }, + { + "Occupied": false, + "Hit": false, + "X": 1, + "Y": 7 + }, + { + "Occupied": true, + "Hit": false, + "X": 1, + "Y": 8 + }, + { + "Occupied": false, + "Hit": true, + "X": 1, + "Y": 9 + }, + { + "Occupied": false, + "Hit": false, + "X": 2, + "Y": 0 + }, + { + "Occupied": false, + "Hit": false, + "X": 2, + "Y": 1 + }, + { + "Occupied": false, + "Hit": false, + "X": 2, + "Y": 2 + }, + { + "Occupied": false, + "Hit": false, + "X": 2, + "Y": 3 + }, + { + "Occupied": false, + "Hit": true, + "X": 2, + "Y": 4 + }, + { + "Occupied": false, + "Hit": true, + "X": 2, + "Y": 5 + }, + { + "Occupied": false, + "Hit": false, + "X": 2, + "Y": 6 + }, + { + "Occupied": false, + "Hit": false, + "X": 2, + "Y": 7 + }, + { + "Occupied": true, + "Hit": true, + "X": 2, + "Y": 8 + }, + { + "Occupied": false, + "Hit": false, + "X": 2, + "Y": 9 + }, + { + "Occupied": false, + "Hit": true, + "X": 3, + "Y": 0 + }, + { + "Occupied": false, + "Hit": true, + "X": 3, + "Y": 1 + }, + { + "Occupied": false, + "Hit": true, + "X": 3, + "Y": 2 + }, + { + "Occupied": false, + "Hit": false, + "X": 3, + "Y": 3 + }, + { + "Occupied": false, + "Hit": false, + "X": 3, + "Y": 4 + }, + { + "Occupied": false, + "Hit": false, + "X": 3, + "Y": 5 + }, + { + "Occupied": false, + "Hit": false, + "X": 3, + "Y": 6 + }, + { + "Occupied": false, + "Hit": false, + "X": 3, + "Y": 7 + }, + { + "Occupied": true, + "Hit": false, + "X": 3, + "Y": 8 + }, + { + "Occupied": false, + "Hit": false, + "X": 3, + "Y": 9 + }, + { + "Occupied": false, + "Hit": false, + "X": 4, + "Y": 0 + }, + { + "Occupied": false, + "Hit": true, + "X": 4, + "Y": 1 + }, + { + "Occupied": false, + "Hit": true, + "X": 4, + "Y": 2 + }, + { + "Occupied": false, + "Hit": false, + "X": 4, + "Y": 3 + }, + { + "Occupied": false, + "Hit": false, + "X": 4, + "Y": 4 + }, + { + "Occupied": false, + "Hit": false, + "X": 4, + "Y": 5 + }, + { + "Occupied": false, + "Hit": false, + "X": 4, + "Y": 6 + }, + { + "Occupied": false, + "Hit": true, + "X": 4, + "Y": 7 + }, + { + "Occupied": true, + "Hit": false, + "X": 4, + "Y": 8 + }, + { + "Occupied": false, + "Hit": true, + "X": 4, + "Y": 9 + }, + { + "Occupied": false, + "Hit": false, + "X": 5, + "Y": 0 + }, + { + "Occupied": true, + "Hit": true, + "X": 5, + "Y": 1 + }, + { + "Occupied": false, + "Hit": false, + "X": 5, + "Y": 2 + }, + { + "Occupied": false, + "Hit": false, + "X": 5, + "Y": 3 + }, + { + "Occupied": false, + "Hit": false, + "X": 5, + "Y": 4 + }, + { + "Occupied": false, + "Hit": false, + "X": 5, + "Y": 5 + }, + { + "Occupied": false, + "Hit": false, + "X": 5, + "Y": 6 + }, + { + "Occupied": false, + "Hit": false, + "X": 5, + "Y": 7 + }, + { + "Occupied": true, + "Hit": false, + "X": 5, + "Y": 8 + }, + { + "Occupied": false, + "Hit": false, + "X": 5, + "Y": 9 + }, + { + "Occupied": false, + "Hit": false, + "X": 6, + "Y": 0 + }, + { + "Occupied": true, + "Hit": false, + "X": 6, + "Y": 1 + }, + { + "Occupied": false, + "Hit": false, + "X": 6, + "Y": 2 + }, + { + "Occupied": false, + "Hit": true, + "X": 6, + "Y": 3 + }, + { + "Occupied": false, + "Hit": false, + "X": 6, + "Y": 4 + }, + { + "Occupied": false, + "Hit": true, + "X": 6, + "Y": 5 + }, + { + "Occupied": false, + "Hit": false, + "X": 6, + "Y": 6 + }, + { + "Occupied": false, + "Hit": false, + "X": 6, + "Y": 7 + }, + { + "Occupied": false, + "Hit": true, + "X": 6, + "Y": 8 + }, + { + "Occupied": false, + "Hit": false, + "X": 6, + "Y": 9 + }, + { + "Occupied": false, + "Hit": false, + "X": 7, + "Y": 0 + }, + { + "Occupied": true, + "Hit": true, + "X": 7, + "Y": 1 + }, + { + "Occupied": false, + "Hit": false, + "X": 7, + "Y": 2 + }, + { + "Occupied": false, + "Hit": false, + "X": 7, + "Y": 3 + }, + { + "Occupied": false, + "Hit": false, + "X": 7, + "Y": 4 + }, + { + "Occupied": true, + "Hit": false, + "X": 7, + "Y": 5 + }, + { + "Occupied": true, + "Hit": false, + "X": 7, + "Y": 6 + }, + { + "Occupied": false, + "Hit": false, + "X": 7, + "Y": 7 + }, + { + "Occupied": false, + "Hit": false, + "X": 7, + "Y": 8 + }, + { + "Occupied": false, + "Hit": false, + "X": 7, + "Y": 9 + }, + { + "Occupied": false, + "Hit": false, + "X": 8, + "Y": 0 + }, + { + "Occupied": true, + "Hit": false, + "X": 8, + "Y": 1 + }, + { + "Occupied": false, + "Hit": false, + "X": 8, + "Y": 2 + }, + { + "Occupied": false, + "Hit": true, + "X": 8, + "Y": 3 + }, + { + "Occupied": false, + "Hit": true, + "X": 8, + "Y": 4 + }, + { + "Occupied": false, + "Hit": false, + "X": 8, + "Y": 5 + }, + { + "Occupied": false, + "Hit": false, + "X": 8, + "Y": 6 + }, + { + "Occupied": false, + "Hit": false, + "X": 8, + "Y": 7 + }, + { + "Occupied": false, + "Hit": false, + "X": 8, + "Y": 8 + }, + { + "Occupied": false, + "Hit": true, + "X": 8, + "Y": 9 + }, + { + "Occupied": false, + "Hit": false, + "X": 9, + "Y": 0 + }, + { + "Occupied": false, + "Hit": false, + "X": 9, + "Y": 1 + }, + { + "Occupied": false, + "Hit": false, + "X": 9, + "Y": 2 + }, + { + "Occupied": false, + "Hit": false, + "X": 9, + "Y": 3 + }, + { + "Occupied": false, + "Hit": false, + "X": 9, + "Y": 4 + }, + { + "Occupied": false, + "Hit": false, + "X": 9, + "Y": 5 + }, + { + "Occupied": false, + "Hit": false, + "X": 9, + "Y": 6 + }, + { + "Occupied": false, + "Hit": false, + "X": 9, + "Y": 7 + }, + { + "Occupied": false, + "Hit": true, + "X": 9, + "Y": 8 + }, + { + "Occupied": false, + "Hit": false, + "X": 9, + "Y": 9 + } + ], + "Owner": { + "FailedFirstPhaseCommands": 0, + "Name": "Admiral Worthebot", + "Ships": [ + { + "Cells": [ + { + "Occupied": true, + "Hit": false, + "X": 0, + "Y": 2 + }, + { + "Occupied": true, + "Hit": false, + "X": 0, + "Y": 3 + }, + { + "Occupied": true, + "Hit": false, + "X": 0, + "Y": 4 + } + ], + "Destroyed": false, + "Placed": true, + "ShipType": "Submarine", + "Weapons": [ + { + "WeaponType": "SingleShot" + } + ] + }, + { + "Cells": [ + { + "Occupied": true, + "Hit": false, + "X": 7, + "Y": 6 + }, + { + "Occupied": true, + "Hit": false, + "X": 7, + "Y": 5 + } + ], + "Destroyed": false, + "Placed": true, + "ShipType": "Destroyer", + "Weapons": [ + { + "WeaponType": "SingleShot" + } + ] + }, + { + "Cells": [ + { + "Occupied": true, + "Hit": true, + "X": 5, + "Y": 1 + }, + { + "Occupied": true, + "Hit": false, + "X": 6, + "Y": 1 + }, + { + "Occupied": true, + "Hit": true, + "X": 7, + "Y": 1 + }, + { + "Occupied": true, + "Hit": false, + "X": 8, + "Y": 1 + } + ], + "Destroyed": false, + "Placed": true, + "ShipType": "Battleship", + "Weapons": [ + { + "WeaponType": "SingleShot" + } + ] + }, + { + "Cells": [ + { + "Occupied": true, + "Hit": false, + "X": 5, + "Y": 8 + }, + { + "Occupied": true, + "Hit": false, + "X": 4, + "Y": 8 + }, + { + "Occupied": true, + "Hit": false, + "X": 3, + "Y": 8 + }, + { + "Occupied": true, + "Hit": true, + "X": 2, + "Y": 8 + }, + { + "Occupied": true, + "Hit": false, + "X": 1, + "Y": 8 + } + ], + "Destroyed": false, + "Placed": true, + "ShipType": "Carrier", + "Weapons": [ + { + "WeaponType": "SingleShot" + } + ] + }, + { + "Cells": [ + { + "Occupied": true, + "Hit": true, + "X": 0, + "Y": 6 + }, + { + "Occupied": true, + "Hit": true, + "X": 0, + "Y": 7 + }, + { + "Occupied": true, + "Hit": false, + "X": 0, + "Y": 8 + } + ], + "Destroyed": false, + "Placed": true, + "ShipType": "Cruiser", + "Weapons": [ + { + "WeaponType": "SingleShot" + } + ] + } + ], + "Points": 280, + "Killed": false, + "IsWinner": false, + "ShotsFired": 86, + "ShotsHit": 16, + "ShipsRemaining": 5, + "Key": "B" + }, + "MapWidth": 10, + "MapHeight": 10 + }, + "OpponentMap": { + "Ships": [ + { + "Destroyed": false, + "ShipType": "Submarine" + }, + { + "Destroyed": true, + "ShipType": "Destroyer" + }, + { + "Destroyed": true, + "ShipType": "Battleship" + }, + { + "Destroyed": true, + "ShipType": "Carrier" + }, + { + "Destroyed": true, + "ShipType": "Cruiser" + } + ], + "Alive": true, + "Points": 50, + "Name": "John", + "Cells": [ + { + "Damaged": false, + "Missed": true, + "X": 0, + "Y": 0 + }, + { + "Damaged": false, + "Missed": true, + "X": 0, + "Y": 1 + }, + { + "Damaged": false, + "Missed": true, + "X": 0, + "Y": 2 + }, + { + "Damaged": false, + "Missed": true, + "X": 0, + "Y": 3 + }, + { + "Damaged": false, + "Missed": true, + "X": 0, + "Y": 4 + }, + { + "Damaged": false, + "Missed": false, + "X": 0, + "Y": 5 + }, + { + "Damaged": false, + "Missed": true, + "X": 0, + "Y": 6 + }, + { + "Damaged": false, + "Missed": true, + "X": 0, + "Y": 7 + }, + { + "Damaged": false, + "Missed": true, + "X": 0, + "Y": 8 + }, + { + "Damaged": false, + "Missed": true, + "X": 0, + "Y": 9 + }, + { + "Damaged": true, + "Missed": false, + "X": 1, + "Y": 0 + }, + { + "Damaged": true, + "Missed": false, + "X": 1, + "Y": 1 + }, + { + "Damaged": true, + "Missed": false, + "X": 1, + "Y": 2 + }, + { + "Damaged": true, + "Missed": false, + "X": 1, + "Y": 3 + }, + { + "Damaged": false, + "Missed": true, + "X": 1, + "Y": 4 + }, + { + "Damaged": false, + "Missed": true, + "X": 1, + "Y": 5 + }, + { + "Damaged": false, + "Missed": true, + "X": 1, + "Y": 6 + }, + { + "Damaged": false, + "Missed": true, + "X": 1, + "Y": 7 + }, + { + "Damaged": true, + "Missed": false, + "X": 1, + "Y": 8 + }, + { + "Damaged": false, + "Missed": true, + "X": 1, + "Y": 9 + }, + { + "Damaged": false, + "Missed": true, + "X": 2, + "Y": 0 + }, + { + "Damaged": false, + "Missed": true, + "X": 2, + "Y": 1 + }, + { + "Damaged": false, + "Missed": true, + "X": 2, + "Y": 2 + }, + { + "Damaged": false, + "Missed": false, + "X": 2, + "Y": 3 + }, + { + "Damaged": false, + "Missed": true, + "X": 2, + "Y": 4 + }, + { + "Damaged": false, + "Missed": true, + "X": 2, + "Y": 5 + }, + { + "Damaged": false, + "Missed": true, + "X": 2, + "Y": 6 + }, + { + "Damaged": false, + "Missed": true, + "X": 2, + "Y": 7 + }, + { + "Damaged": false, + "Missed": false, + "X": 2, + "Y": 8 + }, + { + "Damaged": false, + "Missed": true, + "X": 2, + "Y": 9 + }, + { + "Damaged": false, + "Missed": false, + "X": 3, + "Y": 0 + }, + { + "Damaged": true, + "Missed": false, + "X": 3, + "Y": 1 + }, + { + "Damaged": false, + "Missed": false, + "X": 3, + "Y": 2 + }, + { + "Damaged": false, + "Missed": false, + "X": 3, + "Y": 3 + }, + { + "Damaged": false, + "Missed": true, + "X": 3, + "Y": 4 + }, + { + "Damaged": false, + "Missed": true, + "X": 3, + "Y": 5 + }, + { + "Damaged": false, + "Missed": true, + "X": 3, + "Y": 6 + }, + { + "Damaged": false, + "Missed": true, + "X": 3, + "Y": 7 + }, + { + "Damaged": true, + "Missed": false, + "X": 3, + "Y": 8 + }, + { + "Damaged": false, + "Missed": false, + "X": 3, + "Y": 9 + }, + { + "Damaged": false, + "Missed": false, + "X": 4, + "Y": 0 + }, + { + "Damaged": true, + "Missed": false, + "X": 4, + "Y": 1 + }, + { + "Damaged": true, + "Missed": false, + "X": 4, + "Y": 2 + }, + { + "Damaged": true, + "Missed": false, + "X": 4, + "Y": 3 + }, + { + "Damaged": true, + "Missed": false, + "X": 4, + "Y": 4 + }, + { + "Damaged": false, + "Missed": true, + "X": 4, + "Y": 5 + }, + { + "Damaged": false, + "Missed": true, + "X": 4, + "Y": 6 + }, + { + "Damaged": false, + "Missed": false, + "X": 4, + "Y": 7 + }, + { + "Damaged": false, + "Missed": true, + "X": 4, + "Y": 8 + }, + { + "Damaged": false, + "Missed": true, + "X": 4, + "Y": 9 + }, + { + "Damaged": false, + "Missed": true, + "X": 5, + "Y": 0 + }, + { + "Damaged": true, + "Missed": false, + "X": 5, + "Y": 1 + }, + { + "Damaged": false, + "Missed": true, + "X": 5, + "Y": 2 + }, + { + "Damaged": false, + "Missed": true, + "X": 5, + "Y": 3 + }, + { + "Damaged": false, + "Missed": true, + "X": 5, + "Y": 4 + }, + { + "Damaged": false, + "Missed": true, + "X": 5, + "Y": 5 + }, + { + "Damaged": false, + "Missed": true, + "X": 5, + "Y": 6 + }, + { + "Damaged": false, + "Missed": true, + "X": 5, + "Y": 7 + }, + { + "Damaged": false, + "Missed": true, + "X": 5, + "Y": 8 + }, + { + "Damaged": false, + "Missed": false, + "X": 5, + "Y": 9 + }, + { + "Damaged": false, + "Missed": true, + "X": 6, + "Y": 0 + }, + { + "Damaged": true, + "Missed": false, + "X": 6, + "Y": 1 + }, + { + "Damaged": false, + "Missed": true, + "X": 6, + "Y": 2 + }, + { + "Damaged": false, + "Missed": true, + "X": 6, + "Y": 3 + }, + { + "Damaged": false, + "Missed": true, + "X": 6, + "Y": 4 + }, + { + "Damaged": false, + "Missed": true, + "X": 6, + "Y": 5 + }, + { + "Damaged": false, + "Missed": true, + "X": 6, + "Y": 6 + }, + { + "Damaged": false, + "Missed": true, + "X": 6, + "Y": 7 + }, + { + "Damaged": false, + "Missed": true, + "X": 6, + "Y": 8 + }, + { + "Damaged": false, + "Missed": false, + "X": 6, + "Y": 9 + }, + { + "Damaged": false, + "Missed": false, + "X": 7, + "Y": 0 + }, + { + "Damaged": true, + "Missed": false, + "X": 7, + "Y": 1 + }, + { + "Damaged": false, + "Missed": true, + "X": 7, + "Y": 2 + }, + { + "Damaged": true, + "Missed": false, + "X": 7, + "Y": 3 + }, + { + "Damaged": true, + "Missed": false, + "X": 7, + "Y": 4 + }, + { + "Damaged": false, + "Missed": true, + "X": 7, + "Y": 5 + }, + { + "Damaged": false, + "Missed": true, + "X": 7, + "Y": 6 + }, + { + "Damaged": false, + "Missed": true, + "X": 7, + "Y": 7 + }, + { + "Damaged": false, + "Missed": true, + "X": 7, + "Y": 8 + }, + { + "Damaged": false, + "Missed": true, + "X": 7, + "Y": 9 + }, + { + "Damaged": false, + "Missed": true, + "X": 8, + "Y": 0 + }, + { + "Damaged": false, + "Missed": true, + "X": 8, + "Y": 1 + }, + { + "Damaged": false, + "Missed": false, + "X": 8, + "Y": 2 + }, + { + "Damaged": false, + "Missed": true, + "X": 8, + "Y": 3 + }, + { + "Damaged": false, + "Missed": true, + "X": 8, + "Y": 4 + }, + { + "Damaged": false, + "Missed": true, + "X": 8, + "Y": 5 + }, + { + "Damaged": false, + "Missed": true, + "X": 8, + "Y": 6 + }, + { + "Damaged": false, + "Missed": true, + "X": 8, + "Y": 7 + }, + { + "Damaged": false, + "Missed": false, + "X": 8, + "Y": 8 + }, + { + "Damaged": false, + "Missed": true, + "X": 8, + "Y": 9 + }, + { + "Damaged": false, + "Missed": true, + "X": 9, + "Y": 0 + }, + { + "Damaged": false, + "Missed": true, + "X": 9, + "Y": 1 + }, + { + "Damaged": false, + "Missed": true, + "X": 9, + "Y": 2 + }, + { + "Damaged": false, + "Missed": true, + "X": 9, + "Y": 3 + }, + { + "Damaged": false, + "Missed": true, + "X": 9, + "Y": 4 + }, + { + "Damaged": false, + "Missed": true, + "X": 9, + "Y": 5 + }, + { + "Damaged": false, + "Missed": true, + "X": 9, + "Y": 6 + }, + { + "Damaged": false, + "Missed": true, + "X": 9, + "Y": 7 + }, + { + "Damaged": false, + "Missed": true, + "X": 9, + "Y": 8 + }, + { + "Damaged": false, + "Missed": true, + "X": 9, + "Y": 9 + } + ] + }, + "GameVersion": "1.0.0", + "GameLevel": 1, + "Round": 87, + "MapDimension": 10, + "Phase": 2, + "Player1Map": null, + "Player2Map": null +} +#+END_SRC diff --git a/2017-battleships/readme.txt b/2017-battleships/readme.txt new file mode 100644 index 0000000..ffffa2f --- /dev/null +++ b/2017-battleships/readme.txt @@ -0,0 +1,20 @@ +* Admiral Worthebot + +** Compilation Instructions + +As per the Rust sample bot. Install the Rust build toolchain from https://www.rust-lang.org/en-US/install.html, then from the root directory of the project run + +cargo build --release + +** Project Structure + +Cargo.toml - Cargo project config, including project dependencies +src/ - Soure code directory +src/main.rs - Command line entrypoint (main function) and command line argument parsing +src/lib.rs - Programs public interface (as used by main.rs and any integration tests) + +** Strategy + +- Track all possible ways that an opponent may have placed their ships +- After every move, deduce which possibilities are now impossible +- Shoot in an attempt to (possibly) eliminate as many possibilities as possible diff --git a/2017-battleships/src/actions.rs b/2017-battleships/src/actions.rs new file mode 100644 index 0000000..cf0059a --- /dev/null +++ b/2017-battleships/src/actions.rs @@ -0,0 +1,90 @@ +use math::*; +use ships::*; + +use std::fmt; + +use std::collections::HashSet; + +#[derive(Clone, PartialEq, Eq, Debug, Serialize, Deserialize)] +pub enum Action { + PlaceShips(Vec<ShipPlacement>), + Shoot(Weapon, Point) +} + +impl fmt::Display for Action { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &Action::Shoot(w, p) => writeln!(f, "{},{},{}", w, p.x, p.y), + &Action::PlaceShips(ref ships) => ships.iter().map(|ref ship| { + writeln!(f, "{} {} {} {}", ship.ship_type, ship.point.x, ship.point.y, ship.direction) + }).fold(Ok(()), |acc, next| acc.and(next)) + } + } +} + +#[derive(Clone, PartialEq, Eq, Debug, Serialize, Deserialize)] +pub struct ShipPlacement { + ship_type: Ship, + point: Point, + direction: Direction +} + +impl ShipPlacement { + pub fn new(ship_type: Ship, point: Point, direction: Direction) -> ShipPlacement { + ShipPlacement { + ship_type: ship_type, + point: point, + direction: direction + } + } + + pub fn valid(&self, map_size: u16) -> bool { + let start = self.point; + let end = start.move_point(self.direction, self.ship_type.length() as i32, map_size); + start.x < map_size && start.y < map_size && end.is_some() + } + pub fn valid_placements(placements: &Vec<ShipPlacement>, map_size: u16) -> bool { + let mut occupied = HashSet::new(); + + let individuals_valid = placements.iter().all(|p| p.valid(map_size)); + + let mut no_overlaps = true; + for placement in placements { + for i in 0..placement.ship_type.length() as i32 { + match placement.point.move_point(placement.direction, i, map_size) { + Some(block) => { + no_overlaps = no_overlaps && !occupied.contains(&block); + occupied.insert(block); + }, + None => { + //invalid case here is handled above + } + } + } + + //block out the area around the current ship to prevent adjacent ships + for i in 0..placement.ship_type.length() as i32 { + match placement.point.move_point(placement.direction, i, map_size) { + Some(current_block) => { + if let Some(p) = current_block.move_point(Direction::North, 1, map_size) { + occupied.insert(p); + } + if let Some(p) = current_block.move_point(Direction::South, 1, map_size) { + occupied.insert(p); + } + if let Some(p) = current_block.move_point(Direction::East, 1, map_size) { + occupied.insert(p); + } + if let Some(p) = current_block.move_point(Direction::West, 1, map_size) { + occupied.insert(p); + } + }, + None => { + //invalid case here is handled above + } + } + } + } + individuals_valid && no_overlaps + } +} diff --git a/2017-battleships/src/files.rs b/2017-battleships/src/files.rs new file mode 100644 index 0000000..0810a4e --- /dev/null +++ b/2017-battleships/src/files.rs @@ -0,0 +1,57 @@ +use json; +use serde_json; + +use std::io::prelude::*; +use std::fs::File; +use std::path::PathBuf; + +use actions::*; +use knowledge::*; + +const STATE_FILE: &'static str = "state.json"; + +const COMMAND_FILE: &'static str = "command.txt"; +const PLACE_FILE: &'static str = "place.txt"; + +const KNOWLEDGE_FILE: &'static str = "knowledge-state.json"; + + +pub fn read_file(working_dir: &PathBuf) -> Result<json::JsonValue, String> { + let state_path = working_dir.join(STATE_FILE); + let mut file = File::open(state_path.as_path()).map_err(|e| e.to_string())?; + let mut content = String::new(); + file.read_to_string(&mut content).map_err(|e| e.to_string())?; + json::parse(content.as_ref()).map_err(|e| e.to_string()) +} + +pub fn write_action(working_dir: &PathBuf, is_place_phase: bool, action: Action) -> Result<(), String> { + let filename = if is_place_phase { + PLACE_FILE + } + else { + COMMAND_FILE + }; + + let full_filename = working_dir.join(filename); + let mut file = File::create(full_filename.as_path()).map_err(|e| e.to_string())?; + write!(file, "{}", action).map_err(|e| e.to_string())?; + + println!("Making move: {}", action); + + Ok(()) +} + +pub fn read_knowledge() -> Result<Knowledge, String> { + let mut file = File::open(KNOWLEDGE_FILE).map_err(|e| e.to_string())?; + let mut content = String::new(); + file.read_to_string(&mut content).map_err(|e| e.to_string())?; + serde_json::from_str(content.as_ref()).map_err(|e| e.to_string()) +} + +pub fn write_knowledge(knowledge: &Knowledge) -> Result<(), String> { + let json = serde_json::to_string(knowledge).map_err(|e| e.to_string())?; + let mut file = File::create(KNOWLEDGE_FILE).map_err(|e| e.to_string())?; + write!(file, "{}", json).map_err(|e| e.to_string())?; + + Ok(()) +} diff --git a/2017-battleships/src/knowledge.rs b/2017-battleships/src/knowledge.rs new file mode 100644 index 0000000..4a66e8b --- /dev/null +++ b/2017-battleships/src/knowledge.rs @@ -0,0 +1,504 @@ +use actions::*; +use ships::*; +use state::*; +use math::*; + +use std::collections::HashMap; +use std::cmp::Ordering; + +#[derive(Serialize, Deserialize, Clone, Debug)] +pub struct Knowledge { + pub last_action: Action, + pub opponent_map: OpponentMapKnowledge, + pub map_size: u16, + pub available_weapons: Vec<Weapon>, + pub shootable_weapons: Vec<Weapon>, + pub charging_weapons: HashMap<Weapon, u16> +} + +impl Knowledge { + pub fn new(map_size: u16, action: Action) -> Knowledge { + Knowledge { + last_action: action, + opponent_map: OpponentMapKnowledge::new(map_size), + map_size: map_size, + available_weapons: Vec::new(), + shootable_weapons: Vec::new(), + charging_weapons: HashMap::new() + } + } + + pub fn with_action(&self, action: Action) -> Knowledge { + Knowledge { + last_action: action, + ..self.clone() + } + } + + pub fn resolve_last_action(&self, state: &State) -> Knowledge { + let mut new_knowledge = self.clone(); + + let energy = state.player_map.energy; + let mut available_weapons: Vec<_> = state.player_map.ships.iter() + .filter(|&(_, ship_data)| !ship_data.destroyed) + .flat_map(|(ship, _)| ship.weapons()) + .collect(); + + available_weapons.sort_by_key(|weapon| format!("{}",weapon)); + available_weapons.dedup(); + new_knowledge.available_weapons = available_weapons; + + new_knowledge.shootable_weapons = new_knowledge.available_weapons.iter() + .filter(|weapon| weapon.energy_cost(state.map_size) <= energy) + .cloned() + .collect(); + + new_knowledge.charging_weapons = new_knowledge.available_weapons.iter() + .filter(|weapon| weapon.energy_cost(state.map_size) > energy) + .map(|weapon| (weapon.clone(), weapon.single_shot_rounds_to_ready(energy, state.map_size))) + .collect(); + + let (hits, misses, _) = match self.last_action { + Action::PlaceShips(_) => { + (vec!(), vec!(), vec!()) + }, + Action::Shoot(Weapon::SeekerMissle, p) => { + Knowledge::seeker_hits_and_misses(p, &state) + } + + Action::Shoot(w, p) => { + Knowledge::to_hits_and_misses(w.affected_cells(p, state.map_size), &state) + } + }; + + let sunk_ships = new_knowledge.opponent_map.update_sunk_ships(&state); + + new_knowledge.opponent_map.update_from_shot(hits, misses, sunk_ships); + + new_knowledge + } + + fn to_hits_and_misses(points: Vec<Point>, state: &State) -> (Vec<Point>, Vec<Point>, Vec<Point>) { + let hits = points.iter().filter(|p| state.opponent_map.cells[p.x as usize][p.y as usize].damaged).cloned().collect(); + let misses = points.iter().filter(|p| state.opponent_map.cells[p.x as usize][p.y as usize].missed).cloned().collect(); + let unknown = points.iter().filter(|p| !state.opponent_map.cells[p.x as usize][p.y as usize].missed && !state.opponent_map.cells[p.x as usize][p.y as usize].damaged).cloned().collect(); + + (hits, misses, unknown) + } + + fn seeker_hits_and_misses(p: Point, state: &State) -> (Vec<Point>, Vec<Point>, Vec<Point>) { + let mut misses: Vec<Point> = Vec::new(); + let mut hits: Vec<Point> = Vec::new(); + + let rings = vec!( + vec!( + //0 + Some(p) + ), + vec!( + //1 + p.move_point(Direction::North, 1, state.map_size), + p.move_point(Direction::East, 1, state.map_size), + p.move_point(Direction::South, 1, state.map_size), + p.move_point(Direction::West, 1, state.map_size), + ), + vec!( + //1.44 + p.move_point(Direction::NorthEast, 1, state.map_size), + p.move_point(Direction::SouthEast, 1, state.map_size), + p.move_point(Direction::NorthWest, 1, state.map_size), + p.move_point(Direction::SouthWest, 1, state.map_size) + ), + vec!( + //2 + p.move_point(Direction::North, 2, state.map_size), + p.move_point(Direction::East, 2, state.map_size), + p.move_point(Direction::South, 2, state.map_size), + p.move_point(Direction::West, 2, state.map_size), + ) + ); + + //start in the center. Add rings, until I find a hit + //don't add more after a hit is found + for ring in rings { + if hits.is_empty() { + let (mut new_hits, mut new_misses, mut unknown) = Knowledge::to_hits_and_misses(ring.iter().filter_map(|&p| p).collect::<Vec<_>>(), &state); + misses.append(&mut new_misses); + if !new_hits.is_empty() { + hits.append(&mut new_hits); + } else { + misses.append(&mut unknown); + } + } + } + + (hits, misses, vec!()) + } + + pub fn has_unknown_hits(&self) -> bool { + self.opponent_map.cells.iter().fold(false, |acc, x| { + x.iter().fold(acc, |acc, y| acc || y.unknown_hit()) + }) + } + + pub fn get_best_adjacent_shots(&self) -> Vec<Point> { + let unknown_hits = self.opponent_map.cells_with_unknown_hits(); + let adjacent_cells = self.opponent_map.adjacent_unshot_cells(&unknown_hits); + + let possible_placements = self.opponent_map.possible_placements(); + + let mut max_score = 1; + let mut best_cells = Vec::new(); + + for placement in possible_placements { + for &cell in &adjacent_cells { + let score = placement.count_hit_cells(cell, &unknown_hits); + if score > max_score { + max_score = score; + best_cells = vec!(cell); + } + else if score == max_score { + best_cells.push(cell); + } + } + } + + best_cells + } + + pub fn get_best_seek_shots(&self) -> (Weapon, Vec<Point>) { + let possible_placements = self.opponent_map.possible_placements(); + // let lattice = self.lattice_size(); //TODO use the lattice still? + + let guaranteed_hits = self.get_points_that_touch_all_possibilities_on_unsunk_ship(); + if !guaranteed_hits.is_empty() { + return (Weapon::SingleShot, guaranteed_hits); + } + + let mut best_shots: HashMap<Weapon, (Vec<Point>, usize)> = HashMap::new(); + + for &weapon in self.available_weapons.iter() { + let mut current_best_score = 1; + let mut best_cells = Vec::new(); + + for target in self.opponent_map.flat_cell_position_list() { + let cells = if weapon == Weapon::SeekerMissle { + let full_range = weapon.affected_cells(target, self.map_size); + let has_hits = full_range.iter().any(|p| self.opponent_map.cells[p.x as usize][p.y as usize].hit); + if has_hits { + vec!() + } + else { + full_range + } + } + else { + weapon.affected_cells(target, self.map_size) + .iter() + .filter(|p| !self.opponent_map.cells[p.x as usize][p.y as usize].hit) + .cloned() + .collect() + }; + + let possibilities = possible_placements.iter() + .filter(|placement| placement.touches_any_point(&cells)) + .count(); + + if possibilities > current_best_score { + current_best_score = possibilities; + best_cells = vec!(target); + } + else if possibilities == current_best_score { + best_cells.push(target); + } + } + + best_shots.insert(weapon, (best_cells, current_best_score)); + } + + let best_single: Option<(Weapon, (Vec<Point>, usize))> = + best_shots.get(&Weapon::SingleShot).map(|x| (Weapon::SingleShot, x.clone())); + + let best: (Weapon, (Vec<Point>, usize)) = + best_shots.iter() + .max_by(|&(weapon_a, &(_, score_a)), &(weapon_b, &(_, score_b))| { + let score = score_a.cmp(&score_b); + let cost = weapon_a.energy_cost(self.map_size).cmp(&weapon_b.energy_cost(self.map_size)); + if score == Ordering::Equal { cost } else { score } + }) + .and_then(|(&weapon, x)| { + if self.shootable_weapons.contains(&weapon) { + Some((weapon, x.clone())) + } else { + best_single + } + }) + .unwrap_or((Weapon::SingleShot, (vec!(), 0))); + + + (best.0.clone(), (best.1).0) + } + + fn get_points_that_touch_all_possibilities_on_unsunk_ship(&self) -> Vec<Point> { + self.opponent_map.flat_cell_position_list().iter().cloned().filter(|&point| { + self.opponent_map.ships.values() + .any(|ref ship| !ship.destroyed && + ship.possible_placements.iter().all(|placement| { + placement.touches_point(point) + })) + }).collect() + } + + fn lattice_size(&self) -> u16 { + let any_long_ships = self.opponent_map.ships.iter() + .any(|(ship, knowledge)| ship.length() >= 4 && !knowledge.destroyed); + if any_long_ships { + 4 + } + else { + 2 + } + } +} + +#[derive(Serialize, Deserialize, Clone, Debug)] +pub struct OpponentMapKnowledge { + pub ships: HashMap<Ship, OpponentShipKnowledge>, + pub cells: Vec<Vec<KnowledgeCell>> +} + +impl OpponentMapKnowledge { + fn new(map_size: u16) -> OpponentMapKnowledge { + let mut cells = Vec::with_capacity(map_size as usize); + for x in 0..map_size { + cells.push(Vec::with_capacity(map_size as usize)); + for y in 0..map_size { + cells[x as usize].push(KnowledgeCell::new(x, y)); + } + } + + let ships = Ship::all_types().iter() + .map(|s| (s.clone(), OpponentShipKnowledge::new(s.clone(), map_size))) + .collect::<HashMap<_, _>>(); + + OpponentMapKnowledge { + ships: ships, + cells: cells + } + } + + fn update_sunk_ships(&mut self, state: &State) -> Vec<Ship> { + let sunk_ships = self.ships.iter() + .filter(|&(_, x)| !x.destroyed) + .filter(|&(s, _)| state.opponent_map.ships.get(s).map(|x| x.destroyed) == Some(true)) + .map(|(s, _)| s.clone()) + .collect(); + + for &ship in &sunk_ships { + self.ships.get_mut(&ship).map(|ref mut ship_knowledge| ship_knowledge.destroyed = true); + } + + sunk_ships + } + + fn update_from_shot(&mut self, hit_cells: Vec<Point>, missed_cells: Vec<Point>, sunk_ships: Vec<Ship>) { + for &missed in &missed_cells { + self.cells[missed.x as usize][missed.y as usize].missed = true; + } + for &hit in &hit_cells { + self.cells[hit.x as usize][hit.y as usize].hit = true; + } + + self.clear_sunk_ship_impossible_placements(&sunk_ships, &hit_cells); + + let mut more_changes = true; + while more_changes { + more_changes = self.derive_ship_positions() || self.clear_impossible_placements(); + } + } + + fn derive_ship_positions(&mut self) -> bool { + let mut any_changes = false; + for knowledge in self.ships.values() { + if knowledge.possible_placements.len() == 1 { + let ref true_placement = knowledge.possible_placements[0]; + for p in true_placement.points_on_ship() { + if self.cells[p.x as usize][p.y as usize].known_ship == None { + self.cells[p.x as usize][p.y as usize].known_ship = Some(true_placement.ship); + any_changes = true; + } + } + } + } + any_changes + } + + fn clear_impossible_placements(&mut self) -> bool { + let mut any_changes = false; + let ref cells = self.cells; + for knowledge in self.ships.values_mut() { + let before = knowledge.possible_placements.len(); + knowledge.possible_placements.retain(|x| x.all_could_be_hits(&cells)); + let after = knowledge.possible_placements.len(); + if before != after { + any_changes = true; + } + } + any_changes + } + + fn clear_sunk_ship_impossible_placements(&mut self, sunk_ships: &Vec<Ship>, must_touch_any: &Vec<Point>) { + let cells_copy = self.cells.clone(); + + for knowledge in self.ships.values_mut() { + knowledge.possible_placements.retain(|x| !sunk_ships.contains(&x.ship) || (x.touches_any_point(&must_touch_any) && x.all_are_hits(&cells_copy))); + } + } + + fn cells_with_unknown_hits(&self) -> Vec<Point> { + self.cells.iter().flat_map(|x| { + x.iter().filter(|y| y.unknown_hit()).map(|y| y.position) + }).collect() + } + + fn adjacent_unshot_cells(&self, cells: &Vec<Point>) -> Vec<Point> { + self.cells.iter().flat_map(|x| { + x.iter() + .filter(|y| !y.shot_attempted()) + .map(|y| y.position) + .filter(|&y| cells.iter().any(|z| z.is_adjacent(y))) + }).collect() + } + + fn flat_cell_position_list(&self) -> Vec<Point> { + self.cells.iter().flat_map(|x| { + x.iter().map(|y| y.position) + }).collect() + } + + fn cells_on_lattice(&self, lattice_size: u16) -> Vec<Point> { + self.cells.iter().flat_map(|x| { + x.iter() + .filter(|y| !y.shot_attempted() && y.position.is_on_lattice(lattice_size)) + .map(|y| y.position) + }).collect() + } + + fn possible_placements(&self) -> Vec<PossibleShipPlacement> { + self.ships + .values() + .flat_map(|knowledge| knowledge.possible_placements.clone()) + .collect() + } +} + +#[derive(Serialize, Deserialize, Clone, Debug)] +pub struct OpponentShipKnowledge { + pub ship: Ship, + pub destroyed: bool, + pub possible_placements: Vec<PossibleShipPlacement> +} + +impl OpponentShipKnowledge { + fn new(ship: Ship, map_size: u16) -> OpponentShipKnowledge { + OpponentShipKnowledge { + ship: ship, + destroyed: false, + possible_placements: PossibleShipPlacement::enumerate(ship, map_size) + } + } +} + +#[derive(Serialize, Deserialize, Clone, Debug)] +pub struct PossibleShipPlacement { + pub ship: Ship, + pub direction: Direction, + pub position: Point +} + +impl PossibleShipPlacement { + fn enumerate(ship: Ship, map_size: u16) -> Vec<PossibleShipPlacement> { + (0..(map_size-ship.length()+1)).flat_map(move |par| { + (0..map_size).flat_map(move |per| { + vec!( + PossibleShipPlacement { + ship: ship, + direction: Direction::East, + position: Point::new(par, per) + }, + PossibleShipPlacement { + ship: ship, + direction: Direction::North, + position: Point::new(per, par) + } + ) + }) + }).collect() + } + + pub fn touches_point(&self, p: Point) -> bool { + p.check_for_ship_collision(self.position, self.direction, self.ship.length()) + } + pub fn touches_any_point(&self, ps: &Vec<Point>) -> bool { + ps.iter().any(|&p| self.touches_point(p)) + } + + pub fn points_on_ship(&self) -> Vec<Point> { + (0..self.ship.length() as i32).map(|i| { + self.position.move_point_no_bounds_check(self.direction, i) + }).collect() + } + + fn all_are_hits(&self, cells: &Vec<Vec<KnowledgeCell>>) -> bool { + self.points_on_ship() + .iter() + .fold(true, |acc, p| acc && cells[p.x as usize][p.y as usize].hit) + } + + fn all_could_be_hits(&self, cells: &Vec<Vec<KnowledgeCell>>) -> bool { + self.points_on_ship() + .iter() + .all(|p| { + let ref cell = cells[p.x as usize][p.y as usize]; + !cell.missed && cell.known_ship.map(|ship| ship == self.ship).unwrap_or(true) + }) + } + + fn count_hit_cells(&self, required: Point, wanted: &Vec<Point>) -> u16 { + if !self.touches_point(required) { + return 0; + } + + wanted.iter().filter(|&&x| self.touches_point(x)).count() as u16 + } +} + +#[derive(Serialize, Deserialize, Clone, Debug)] +pub struct KnowledgeCell { + pub missed: bool, + pub hit: bool, + pub known_ship: Option<Ship>, + pub position: Point +} + +impl KnowledgeCell { + fn new(x: u16, y: u16) -> KnowledgeCell { + KnowledgeCell { + missed: false, + hit: false, + position: Point::new(x, y), + known_ship: None + } + } + + pub fn shot_attempted(&self) -> bool { + self.missed || self.hit + } + + pub fn unknown_hit(&self) -> bool { + self.hit && self.known_ship.is_none() + } + +} + + diff --git a/2017-battleships/src/lib.rs b/2017-battleships/src/lib.rs new file mode 100644 index 0000000..00eaf02 --- /dev/null +++ b/2017-battleships/src/lib.rs @@ -0,0 +1,67 @@ +extern crate json; +extern crate rand; +extern crate serde; +extern crate serde_json; +#[macro_use] +extern crate serde_derive; + +mod actions; +mod math; +mod files; +mod ships; +mod placement; +mod shooting; +mod state; +mod knowledge; + +use actions::*; +use math::*; +use files::*; +use ships::*; +use placement::*; +use shooting::*; +use state::*; +use knowledge::*; + +use std::path::PathBuf; + +pub fn write_move(working_dir: PathBuf) -> Result<(), String> { + let state_json = read_file(&working_dir)?; + + let is_place_phase = state_json["Phase"] == 1; + let map_size = State::map_size_from_json(&state_json)?; + + let (action, knowledge) = if is_place_phase { + placement(map_size) + } + else { + let state = State::new(&state_json)?; + shoot(&state)? + }; + + write_knowledge(&knowledge) + .map_err(|e| format!("Failed to write knowledge to file. Error: {}", e))?; + + write_action(&working_dir, is_place_phase, action) + .map_err(|e| format!("Failed to write action to file. Error: {}", e))?; + + println!("Knowledge:\n{}\n\n", serde_json::to_string(&knowledge).unwrap_or(String::from(""))); + + Ok(()) +} + +fn placement(map_size: u16) -> (Action, Knowledge) { + let action = place_ships_randomly(map_size); + let knowledge = Knowledge::new(map_size, action.clone()); + + (action, knowledge) +} + +fn shoot(state: &State) -> Result<(Action, Knowledge), String> { + let old_knowledge = read_knowledge()?; + let knowledge = old_knowledge.resolve_last_action(&state); + let action = shoot_smartly(&knowledge); + + Ok((action.clone(), knowledge.with_action(action))) +} + diff --git a/2017-battleships/src/main.rs b/2017-battleships/src/main.rs new file mode 100644 index 0000000..ee0ba59 --- /dev/null +++ b/2017-battleships/src/main.rs @@ -0,0 +1,19 @@ +extern crate worthebot_battleships; + +use worthebot_battleships as bot; +use std::env; +use std::path::PathBuf; + +fn main() { + let working_dir = env::args() + .nth(2) + .map(|x| PathBuf::from(x)) + .ok_or(String::from("Requires game state folder to be passed as the second parameter")); + + let result = working_dir.and_then(|working_dir| bot::write_move(working_dir)); + + match result { + Ok(()) => println!("Bot terminated successfully"), + Err(e) => println!("Error in bot execution: {}", e) + } +} diff --git a/2017-battleships/src/math.rs b/2017-battleships/src/math.rs new file mode 100644 index 0000000..3187829 --- /dev/null +++ b/2017-battleships/src/math.rs @@ -0,0 +1,338 @@ +use std::fmt; +use rand; +use rand::distributions::{IndependentSample, Range}; + +#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, Serialize, Deserialize)] +pub enum Direction { + North, + NorthEast, + East, + SouthEast, + South, + SouthWest, + West, + NorthWest +} + +use Direction::*; + +impl fmt::Display for Direction { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.write_str( + match self { + &North => "North", + &East => "East", + &South => "South", + &West => "West", + &NorthEast => "NorthEast", + &SouthEast => "SouthEast", + &NorthWest => "NorthWest", + &SouthWest => "SouthWest" + } + ) + } +} + +impl Direction { + pub fn random() -> Direction { + let mut rng = rand::thread_rng(); + let between = Range::new(0, 4); + let dir = between.ind_sample(&mut rng); + match dir { + 0 => North, + 1 => East, + 2 => South, + 3 => West, + _ => panic!("Invalid number generated by random number generator") + } + } +} + +#[cfg(test)] +mod direction_tests { + use super::*; + + #[test] + fn random_direction_does_not_panic() { + for _ in 0..10000 { + Direction::random(); + } + } +} + +#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, Serialize, Deserialize)] +pub struct Point { + pub x: u16, + pub y: u16 +} + +impl Point { + pub fn new(x: u16, y: u16) -> Point { + Point { + x: x, + y: y + } + } + + pub fn random(map_size: u16) -> Point { + let mut rng = rand::thread_rng(); + let between = Range::new(0, map_size); + let x = between.ind_sample(&mut rng); + let y = between.ind_sample(&mut rng); + Point::new(x, y) + } + + + pub fn move_point(&self, direction: Direction, distance: i32, map_size: u16) -> Option<Point> { + let x = self.x as i32 + match direction { + West|NorthWest|SouthWest => -distance, + East|NorthEast|SouthEast => distance, + _ => 0 + }; + let y = self.y as i32 + match direction { + South|SouthWest|SouthEast => -distance, + North|NorthWest|NorthEast => distance, + _ => 0 + }; + let max = map_size as i32; + + if x >= max || y >= max || x < 0 || y < 0 { + None + } + else { + Some(Point::new(x as u16, y as u16)) + } + } + + pub fn move_point_no_bounds_check(&self, direction: Direction, distance: i32) -> Point { + let x = self.x as i32 + match direction { + West => -distance, + East => distance, + _ => 0 + }; + let y = self.y as i32 + match direction { + South => -distance, + North => distance, + _ => 0 + }; + + Point::new(x as u16, y as u16) + } + + pub fn check_for_ship_collision(&self, ship_start: Point, direction: Direction, length: u16) -> bool { + let reverse = match direction { + West | South => true, + East | North => false, + _ => false //ships cannot go diagonally + }; + + let same_cross = match direction { + East | West => self.y == ship_start.y, + North | South => self.x == ship_start.x, + _ => false //ships cannot go diagonally + }; + + let (parr_self, parr_ship) = match direction { + East | West => (self.x, ship_start.x), + North | South => (self.y, ship_start.y), + _ => (self.x, self.y) //ships cannot go diagonally + }; + + let corrected_parr_ship = match reverse { + true => 1 + parr_ship - length, + false => parr_ship + }; + + same_cross && parr_self >= corrected_parr_ship && parr_self < corrected_parr_ship + length + } + + pub fn is_adjacent(&self, other: Point) -> bool { + let dx = if self.x > other.x {self.x - other.x} else {other.x - self.x}; + let dy = if self.y > other.y {self.y - other.y} else {other.y - self.y}; + + (dx == 0 && dy == 1) || + (dx == 1 && dy == 0) + + } + + pub fn is_on_lattice(&self, lattice_size: u16) -> bool { + (self.x + self.y) % lattice_size == 0 + } +} + + +#[cfg(test)] +mod point_tests { + use super::*; + + #[test] + fn random_point_is_in_correct_range() { + for _ in 0..10000 { + let point = Point::random(15); + assert!(point.x < 15); + assert!(point.y < 15); + } + } + + #[test] + fn move_point_works_north_west() { + assert_eq!(Some(Point::new(3,7)), Point::new(5,5).move_point(NorthWest, 2, 10)); + assert_eq!(Some(Point::new(7,3)), Point::new(5,5).move_point(NorthWest, -2, 10)); + assert_eq!(None, Point::new(5,5).move_point(NorthWest, 6, 10)); + assert_eq!(None, Point::new(5,5).move_point(NorthWest, -5, 10)); + } + + #[test] + fn move_point_works_west() { + assert_eq!(Some(Point::new(3,5)), Point::new(5,5).move_point(West, 2, 10)); + assert_eq!(Some(Point::new(7,5)), Point::new(5,5).move_point(West, -2, 10)); + assert_eq!(None, Point::new(5,5).move_point(West, 6, 10)); + assert_eq!(None, Point::new(5,5).move_point(West, -5, 10)); + } + + #[test] + fn move_point_works_east() { + assert_eq!(Some(Point::new(7,5)), Point::new(5,5).move_point(East, 2, 10)); + assert_eq!(Some(Point::new(3,5)), Point::new(5,5).move_point(East, -2, 10)); + assert_eq!(None, Point::new(5,5).move_point(East, 5, 10)); + assert_eq!(None, Point::new(5,5).move_point(East, -6, 10)); + } + + #[test] + fn move_point_works_south() { + assert_eq!(Some(Point::new(5,3)), Point::new(5,5).move_point(South, 2, 10)); + assert_eq!(Some(Point::new(5,7)), Point::new(5,5).move_point(South, -2, 10)); + assert_eq!(None, Point::new(5,5).move_point(South, 6, 10)); + assert_eq!(None, Point::new(5,5).move_point(South, -5, 10)); + } + + #[test] + fn move_point_works_north() { + assert_eq!(Some(Point::new(5,7)), Point::new(5,5).move_point(North, 2, 10)); + assert_eq!(Some(Point::new(5,3)), Point::new(5,5).move_point(North, -2, 10)); + assert_eq!(None, Point::new(5,5).move_point(North, 5, 10)); + assert_eq!(None, Point::new(5,5).move_point(North, -6, 10)); + } + + #[test] + fn unrestricted_move_point_works_west() { + assert_eq!(Point::new(3,5), Point::new(5,5).move_point_no_bounds_check(West, 2)); + assert_eq!(Point::new(7,5), Point::new(5,5).move_point_no_bounds_check(West, -2)); + } + + #[test] + fn unrestricted_move_point_works_east() { + assert_eq!(Point::new(7,5), Point::new(5,5).move_point_no_bounds_check(East, 2)); + assert_eq!(Point::new(3,5), Point::new(5,5).move_point_no_bounds_check(East, -2)); + } + + #[test] + fn unrestricted_move_point_works_south() { + assert_eq!(Point::new(5,3), Point::new(5,5).move_point_no_bounds_check(South, 2)); + assert_eq!(Point::new(5,7), Point::new(5,5).move_point_no_bounds_check(South, -2)); + } + + #[test] + fn unrestricted_move_point_works_north() { + assert_eq!(Point::new(5,7), Point::new(5,5).move_point_no_bounds_check(North, 2)); + assert_eq!(Point::new(5,3), Point::new(5,5).move_point_no_bounds_check(North, -2)); + } + + #[test] + fn ship_collision_check_works_west() { + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,5), West, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(6,5), West, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(7,5), West, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(8,5), West, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(9,5), West, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(10,5), West, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(4,5), West, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(6,4), West, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(6,6), West, 5)); + } + + #[test] + fn ship_collision_check_works_east() { + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,5), East, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(4,5), East, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(3,5), East, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(2,5), East, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(1,5), East, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(0,5), East, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(6,5), East, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(4,4), East, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(4,6), East, 5)); + } + + #[test] + fn ship_collision_check_works_north() { + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,5), North, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,4), North, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,3), North, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,2), North, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,1), North, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(5,0), North, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(5,6), North, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(4,4), North, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(6,4), North, 5)); + } + + #[test] + fn ship_collision_check_works_south() { + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,5), South, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,6), South, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,7), South, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,8), South, 5)); + assert_eq!(true, Point::new(5,5).check_for_ship_collision(Point::new(5,9), South, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(5,10), South, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(5,4), South, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(4,6), South, 5)); + assert_eq!(false, Point::new(5,5).check_for_ship_collision(Point::new(6,6), South, 5)); + } + + #[test] + fn adjacency_check_works() { + assert_eq!(true, Point::new(5,5).is_adjacent(Point::new(4,5))); + assert_eq!(true, Point::new(5,5).is_adjacent(Point::new(6,5))); + assert_eq!(true, Point::new(5,5).is_adjacent(Point::new(5,4))); + assert_eq!(true, Point::new(5,5).is_adjacent(Point::new(5,6))); + + assert_eq!(false, Point::new(5,5).is_adjacent(Point::new(4,4))); + assert_eq!(false, Point::new(5,5).is_adjacent(Point::new(6,6))); + assert_eq!(false, Point::new(5,5).is_adjacent(Point::new(6,4))); + assert_eq!(false, Point::new(5,5).is_adjacent(Point::new(4,6))); + assert_eq!(false, Point::new(5,5).is_adjacent(Point::new(5,5))); + + assert_eq!(false, Point::new(5,5).is_adjacent(Point::new(10,5))); + + } + + #[test] + fn point_on_4_lattice_works() { + assert_eq!(true, Point::new(0,0).is_on_lattice(4)); + assert_eq!(true, Point::new(4,0).is_on_lattice(4)); + assert_eq!(true, Point::new(0,4).is_on_lattice(4)); + assert_eq!(true, Point::new(4,4).is_on_lattice(4)); + assert_eq!(true, Point::new(1,3).is_on_lattice(4)); + assert_eq!(true, Point::new(3,1).is_on_lattice(4)); + + assert_eq!(false, Point::new(0,1).is_on_lattice(4)); + assert_eq!(false, Point::new(0,2).is_on_lattice(4)); + assert_eq!(false, Point::new(0,3).is_on_lattice(4)); + assert_eq!(false, Point::new(1,0).is_on_lattice(4)); + assert_eq!(false, Point::new(2,0).is_on_lattice(4)); + assert_eq!(false, Point::new(3,0).is_on_lattice(4)); + } + + #[test] + fn point_on_2_lattice_works() { + assert_eq!(true, Point::new(0,0).is_on_lattice(2)); + assert_eq!(true, Point::new(2,0).is_on_lattice(2)); + assert_eq!(true, Point::new(0,2).is_on_lattice(2)); + assert_eq!(true, Point::new(2,2).is_on_lattice(2)); + assert_eq!(true, Point::new(1,1).is_on_lattice(2)); + + assert_eq!(false, Point::new(0,1).is_on_lattice(2)); + assert_eq!(false, Point::new(1,0).is_on_lattice(2)); + } +} diff --git a/2017-battleships/src/placement.rs b/2017-battleships/src/placement.rs new file mode 100644 index 0000000..4740d76 --- /dev/null +++ b/2017-battleships/src/placement.rs @@ -0,0 +1,23 @@ +use actions::*; +use math::*; +use ships::*; + +pub fn place_ships_randomly(map_size: u16) -> Action { + let mut current_placement: Vec<ShipPlacement>; + + while { + current_placement = create_random_placement(map_size); + !ShipPlacement::valid_placements(¤t_placement, map_size) + } {} + Action::PlaceShips(current_placement) +} + +fn create_random_placement(map_size: u16) -> Vec<ShipPlacement> { + vec!( + ShipPlacement::new(Ship::Battleship, Point::random(map_size), Direction::random()), + ShipPlacement::new(Ship::Carrier, Point::random(map_size), Direction::random()), + ShipPlacement::new(Ship::Cruiser, Point::random(map_size), Direction::random()), + ShipPlacement::new(Ship::Destroyer, Point::random(map_size), Direction::random()), + ShipPlacement::new(Ship::Submarine, Point::random(map_size), Direction::random()) + ) +} diff --git a/2017-battleships/src/ships.rs b/2017-battleships/src/ships.rs new file mode 100644 index 0000000..422f24e --- /dev/null +++ b/2017-battleships/src/ships.rs @@ -0,0 +1,216 @@ +use std::fmt; +use std::str; + +use math::*; + +#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, Serialize, Deserialize)] +pub enum Weapon { + SingleShot, + DoubleShotVertical, + DoubleShotHorizontal, + CornerShot, + CrossShotDiagonal, + CrossShotHorizontal, + SeekerMissle +} + +impl fmt::Display for Weapon { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + use Weapon::*; + + f.write_str( + match self { + &SingleShot => "1", + &DoubleShotVertical => "2", + &DoubleShotHorizontal => "3", + &CornerShot => "4", + &CrossShotDiagonal => "5", + &CrossShotHorizontal => "6", + &SeekerMissle => "7" + } + ) + } +} + +impl Weapon { + pub fn energy_per_round(map_size: u16) -> u16 { + if map_size < 10 { + 2 + } + else if map_size < 14 { + 3 + } + else { + 4 + } + } + pub fn energy_cost(&self, map_size: u16) -> u16 { + use Weapon::*; + let epr = Weapon::energy_per_round(map_size); + match self { + &SingleShot => 1, + &DoubleShotVertical | &DoubleShotHorizontal => 8*epr, + &CornerShot => 10*epr, + &CrossShotDiagonal => 12*epr, + &CrossShotHorizontal => 14*epr, + &SeekerMissle => 10*epr + } + } + pub fn single_shot_rounds_to_ready(&self, current_energy: u16, map_size: u16) -> u16 { + let single_shot_cost = Weapon::SingleShot.energy_cost(map_size); + let energy_per_round = Weapon::energy_per_round(map_size) - single_shot_cost; + let required_energy = self.energy_cost(map_size) - current_energy; + //weird plus is to make the integer rounding up instead of down + (required_energy + energy_per_round - 1) / energy_per_round + } + + pub fn affected_cells(&self, target: Point, map_size: u16) -> Vec<Point> { + use Weapon::*; + + let p = target; + match self { + &SingleShot => { + vec!(Some(p)) + }, + &DoubleShotVertical => { + vec!( + p.move_point(Direction::North, 1, map_size), + p.move_point(Direction::South, 1, map_size) + ) + }, + &DoubleShotHorizontal => { + vec!( + p.move_point(Direction::East, 1, map_size), + p.move_point(Direction::West, 1, map_size) + ) + }, + &CornerShot => { + vec!( + p.move_point(Direction::NorthEast, 1, map_size), + p.move_point(Direction::SouthEast, 1, map_size), + p.move_point(Direction::NorthWest, 1, map_size), + p.move_point(Direction::SouthWest, 1, map_size), + ) + }, + &CrossShotDiagonal => { + vec!( + p.move_point(Direction::NorthEast, 1, map_size), + p.move_point(Direction::SouthEast, 1, map_size), + p.move_point(Direction::NorthWest, 1, map_size), + p.move_point(Direction::SouthWest, 1, map_size), + Some(p) + ) + }, + &CrossShotHorizontal => { + vec!( + p.move_point(Direction::North, 1, map_size), + p.move_point(Direction::East, 1, map_size), + p.move_point(Direction::South, 1, map_size), + p.move_point(Direction::West, 1, map_size), + Some(p) + ) + }, + &SeekerMissle => { + vec!( + Some(p), + + p.move_point(Direction::North, 1, map_size), + p.move_point(Direction::East, 1, map_size), + p.move_point(Direction::South, 1, map_size), + p.move_point(Direction::West, 1, map_size), + + p.move_point(Direction::NorthEast, 1, map_size), + p.move_point(Direction::SouthEast, 1, map_size), + p.move_point(Direction::NorthWest, 1, map_size), + p.move_point(Direction::SouthWest, 1, map_size), + + p.move_point(Direction::North, 2, map_size), + p.move_point(Direction::East, 2, map_size), + p.move_point(Direction::South, 2, map_size), + p.move_point(Direction::West, 2, map_size) + ) + } + }.iter().filter_map(|&p| p).collect::<Vec<_>>() + } +} + + +#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, Serialize, Deserialize)] +pub enum Ship { + Battleship, + Carrier, + Cruiser, + Destroyer, + Submarine +} + +impl fmt::Display for Ship { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + use Ship::*; + + f.write_str( + match self { + &Battleship => "Battleship", + &Carrier => "Carrier", + &Cruiser => "Cruiser", + &Destroyer => "Destroyer", + &Submarine => "Submarine" + } + ) + } +} + +impl str::FromStr for Ship { + type Err = String; + fn from_str(s: &str) -> Result<Self, Self::Err> { + use Ship::*; + + match s { + "Battleship" => Ok(Battleship), + "Carrier" => Ok(Carrier), + "Cruiser" => Ok(Cruiser), + "Destroyer" => Ok(Destroyer), + "Submarine" => Ok(Submarine), + _ => Err(String::from("ship type is not known")) + } + } +} + +impl Ship { + pub fn length(&self) -> u16 { + use Ship::*; + + match self { + &Battleship => 4, + &Carrier => 5, + &Cruiser => 3, + &Destroyer => 2, + &Submarine => 3 + } + } + + pub fn weapons(&self) -> Vec<Weapon> { + use Ship::*; + use Weapon::*; + + match self { + &Battleship => vec!(SingleShot, CrossShotDiagonal), + &Carrier => vec!(SingleShot, CornerShot), + &Cruiser => vec!(SingleShot, CrossShotHorizontal), + &Destroyer => vec!(SingleShot, DoubleShotVertical, DoubleShotHorizontal), + &Submarine => vec!(SingleShot, SeekerMissle) + } + } + + pub fn all_types() -> Vec<Ship> { + use Ship::*; + + vec!( + Battleship, + Carrier, + Cruiser, + Destroyer, + Submarine + ) + } +} diff --git a/2017-battleships/src/shooting.rs b/2017-battleships/src/shooting.rs new file mode 100644 index 0000000..e0358ee --- /dev/null +++ b/2017-battleships/src/shooting.rs @@ -0,0 +1,47 @@ +use rand; +use rand::distributions::{IndependentSample, Range}; + +use actions::*; +use math::*; +use knowledge::*; +use ships::*; + +pub fn shoot_smartly(knowledge: &Knowledge) -> Action { + let (weapon, target) = if knowledge.has_unknown_hits() { + destroy_shoot(&knowledge) + } + else { + seek_shoot(&knowledge) + }; + + Action::Shoot(weapon, target) +} + +fn seek_shoot(knowledge: &Knowledge) -> (Weapon, Point) { + let (weapon, possibilities) = knowledge.get_best_seek_shots(); + if possibilities.is_empty() { + println!("All possible shots on the current lattice have been tried!"); + (Weapon::SingleShot, Point::new(0,0)) + } + else { + let mut rng = rand::thread_rng(); + let between = Range::new(0, possibilities.len()); + let i = between.ind_sample(&mut rng); + + (weapon, possibilities[i as usize]) + } +} + +fn destroy_shoot(knowledge: &Knowledge) -> (Weapon, Point) { + let possibilities = knowledge.get_best_adjacent_shots(); + if possibilities.is_empty() { + seek_shoot(&knowledge) + } + else { + let mut rng = rand::thread_rng(); + let between = Range::new(0, possibilities.len()); + let i = between.ind_sample(&mut rng); + + (Weapon::SingleShot, possibilities[i as usize]) + } +} diff --git a/2017-battleships/src/state.rs b/2017-battleships/src/state.rs new file mode 100644 index 0000000..1756ad0 --- /dev/null +++ b/2017-battleships/src/state.rs @@ -0,0 +1,146 @@ +use json; +use std::collections::HashMap; +use ships::*; + +pub struct State { + pub map_size: u16, + pub player_map: PlayerMap, + pub opponent_map: OpponentMap +} + +impl State { + pub fn new(json: &json::JsonValue) -> Result<State, String> { + let map_size = State::map_size_from_json(&json)?; + + let ref player_map_json = json["PlayerMap"]; + let player_map = PlayerMap::new(&player_map_json)?; + + let ref opponent_map_json = json["OpponentMap"]; + let opponent_map = OpponentMap::new(&opponent_map_json, map_size)?; + + Ok(State { + map_size: map_size, + player_map: player_map, + opponent_map: opponent_map + }) + } + + pub fn map_size_from_json(json: &json::JsonValue) -> Result<u16, String> { + json["MapDimension"] + .as_u16() + .ok_or(String::from("Did not find the map dimension in the state json file")) + } +} + +pub struct OpponentMap { + pub cells: Vec<Vec<Cell>>, + pub ships: HashMap<Ship, OpponentShip>, +} + +impl OpponentMap { + fn new(json: &json::JsonValue, map_size: u16) -> Result<OpponentMap, String> { + let mut cells = Vec::with_capacity(map_size as usize); + for _ in 0..map_size { + let mut row = Vec::with_capacity(map_size as usize); + for _ in 0..map_size { + row.push(Cell::new()); + } + cells.push(row); + } + + for json_cell in json["Cells"].members() { + let x = json_cell["X"] + .as_u16() + .ok_or(String::from("Failed to read X value of opponent map cell in json file"))?; + let y = json_cell["Y"] + .as_u16() + .ok_or(String::from("Failed to read Y value of opponent map cell in json file"))?; + let damaged = json_cell["Damaged"] + .as_bool() + .ok_or(String::from("Failed to read Damaged value of opponent map cell in json file"))?; + let missed = json_cell["Missed"] + .as_bool() + .ok_or(String::from("Failed to read Missed value of opponent map cell in json file"))?; + + cells[x as usize][y as usize].damaged = damaged; + cells[x as usize][y as usize].missed = missed; + } + + let mut ships = HashMap::new(); + for json_ship in json["Ships"].members() { + let ship_type_string = json_ship["ShipType"] + .as_str() + .ok_or(String::from("Failed to read ShipType value of opponent map ship in json file"))?; + let ship_type = ship_type_string.parse::<Ship>()?; + + let destroyed = json_ship["Destroyed"] + .as_bool() + .ok_or(String::from("Failed to read Destroyed value of opponent map ship in json file"))?; + ships.insert(ship_type, OpponentShip { + destroyed: destroyed + }); + } + + + Ok(OpponentMap { + cells: cells, + ships: ships + }) + } +} + +pub struct OpponentShip { + pub destroyed: bool +} + +pub struct Cell { + pub damaged: bool, + pub missed: bool +} + +impl Cell { + fn new() -> Cell { + Cell { + damaged: false, + missed: false + } + } +} + +pub struct PlayerMap { + pub ships: HashMap<Ship, PlayerShip>, + pub energy: u16 +} + +impl PlayerMap { + fn new(json: &json::JsonValue) -> Result<PlayerMap, String> { + let mut ships = HashMap::new(); + for json_ship in json["Owner"]["Ships"].members() { + let ship_type_string = json_ship["ShipType"] + .as_str() + .ok_or(String::from("Failed to read ShipType value of player map ship in json file"))?; + let ship_type = ship_type_string.parse::<Ship>()?; + + let destroyed = json_ship["Destroyed"] + .as_bool() + .ok_or(String::from("Failed to read Destroyed value of player map ship in json file"))?; + ships.insert(ship_type, PlayerShip { + destroyed: destroyed + }); + } + + let energy = json["Owner"]["Energy"] + .as_u16() + .ok_or(String::from("Did not find the energy in the state json file"))?; + + Ok(PlayerMap { + ships: ships, + energy: energy + }) + } +} + + +pub struct PlayerShip { + pub destroyed: bool +} |