Path of Survival

Catégorie: Misc Difficulté: hard Flag: HTB{i_h4v3_mY_w3ap0n_n0w_dIjKStr4!!!}

Challenge

Description

---

Far off in the distance, you hear a howl. Your blood runs cold as you realise the Kara'ka-ran have been released - vicious animals tortured beyond all recognition, starved to provide a natural savagery. They will chase you until the ends of the earth; your only chance of survival lies in a fight. Strong but not stupid, they will back off if they see you take down some of their number - briefly, anyway...

Ce challenge tourne sur un docker, disponible sur Github

Analyse et objectif

Toutes les règles sont énoncés sur le site et l’API est documentée. Il faut donc simplement les implémenter en local afin de tester tous les chemins possibles jusqu’à en trouver un qui respecte toutes les règles.

Pour une question de temps, il faut également optimiser un minimum cette recherche en évitant par exemple les chemins inutiles (comme faire des aller retour en 2 tuiles)

Script de résolution

import requests
from enum import Enum
from colorama import Fore, Style

class TileType(Enum):
    CLIFF = 'C'
    GEYSER = 'G'
    MOUNTAIN = 'M'
    PLAINS = 'P'
    RIVER = 'R'
    SAND = 'S'
    EMPTY = 'E'

class Tile:
    def __init__(self, raw):
        self.has_weapon = raw['has_weapon']
        self.type = TileType(raw['terrain'])

    def __str__(self):
        weapon = 'X' if self.has_weapon else ' '
        output = f"{self.type.value}[{weapon}]"
        return output

class Player:

    def __init__(self, x, y, time, game):
        self.x = x
        self.y = y
        self.time = time
        self.game: Game = game
        self.failed = False

    def copy(self):
        return Player(self.x, self.y, self.time, self.game)

    def move(self, direction):
        old_tile = self.game.get_tile(self.x, self.y)

        if direction == 'U':
            self.y -= 1
        elif direction == 'D':
            self.y += 1
        elif direction == 'L':
            self.x -= 1
        elif direction == 'R':
            self.x += 1

        # Illegal moves
        if not 0 <= self.x < self.game.width:
            raise ValueError('Illegal move: out of map')
        if not 0 <= self.y < self.game.height:
            raise ValueError('Illegal move: out of map')
        new_tile = self.game.get_tile(self.x, self.y)
        if new_tile.type == TileType.EMPTY:
            raise ValueError('Illegal move: fell off the world')
        if new_tile.type == TileType.CLIFF and direction in ['U', 'L']:
            raise ValueError('Illegal move: wrong side Cliff')
        if new_tile.type == TileType.GEYSER and direction in ['D', 'R']:
            raise ValueError('Illegal move: wrong side Geyser')

        # Time consumption
        if new_tile.type == old_tile.type:
            self.time -= 1

        if old_tile.type in [TileType.CLIFF, TileType.GEYSER]:
            self.time -= 1
        if new_tile.type in [TileType.CLIFF, TileType.GEYSER]:
            self.time -= 1

        if old_tile.type == TileType.PLAINS and new_tile.type == TileType.MOUNTAIN:
            self.time -= 5
        if old_tile.type == TileType.MOUNTAIN and new_tile.type == TileType.PLAINS:
            self.time -= 2

        if old_tile.type == TileType.PLAINS and new_tile.type == TileType.SAND:
            self.time -= 2
        if old_tile.type == TileType.SAND and new_tile.type == TileType.PLAINS:
            self.time -= 2

        if old_tile.type == TileType.PLAINS and new_tile.type == TileType.RIVER:
            self.time -= 5
        if old_tile.type == TileType.RIVER and new_tile.type == TileType.PLAINS:
            self.time -= 5

        if old_tile.type == TileType.MOUNTAIN and new_tile.type == TileType.SAND:
            self.time -= 5
        if old_tile.type == TileType.SAND and new_tile.type == TileType.MOUNTAIN:
            self.time -= 7

        if old_tile.type == TileType.MOUNTAIN and new_tile.type == TileType.RIVER:
            self.time -= 8
        if old_tile.type == TileType.RIVER and new_tile.type == TileType.MOUNTAIN:
            self.time -= 10

        if old_tile.type == TileType.SAND and new_tile.type == TileType.RIVER:
            self.time -= 8
        if old_tile.type == TileType.RIVER and new_tile.type == TileType.SAND:
            self.time -= 6

        if self.time < 0:
            raise ValueError('Too late')

        if self.time == 0 and not new_tile.has_weapon:
            raise ValueError('Too late')

        if new_tile.has_weapon:
            return True

        return False

    def __str__(self):
        output = f"[{self.x:0>2}, {self.y:0>2}] -> {self.time:0>3}"
        if self.failed:
            output = Style.DIM + Fore.RED + output + Style.RESET_ALL
        return output

class Game:
    def __init__(self, url):
        self.url = url
        data = requests.post(f"{url}/map").json()
        self.player = Player(data['player']['position'][0], data['player']['position'][1], data['player']['time'], self)
        self.width = data['width']
        self.height = data['height']
        self.map: list[list[Tile]] = []
        for y in range(self.height):
            self.map.append([])
            for x in range(self.width):
                self.map[y].append(Tile(data['tiles'][f"({x}, {y})"]))

    def get_tile(self, x, y) -> Tile:
        return self.map[y][x]

    @staticmethod
    def _solve_game(player: Player, path=None):
        path = path or []
        last_move = path[-1] if len(path) > 0 else None
        for move in ['U', 'R', 'D', 'L']:
            # Optimisation
            if move == 'U' and last_move == 'D':
                continue
            if move == 'D' and last_move == 'U':
                continue
            if move == 'R' and last_move == 'L':
                continue
            if move == 'L' and last_move == 'R':
                continue

            try:
                copy_player = player.copy()
                if copy_player.move(move):
                    return [*path, move]
                return Game._solve_game(copy_player, [*path, move])
            except ValueError:
                pass
        raise ValueError('No solution here')

    def solve(self):
        solution = Game._solve_game(self.player)
        for direction in solution:
            data = requests.post(f"{self.url}/update", json={"direction": direction}).json()
            if 'solved' in data:
                return data
        raise ValueError('Solve failed')

    def print_map(self):
        for y in range(self.height):
            items = []
            for x in range(self.width):
                tile = self.map[y][x]
                if self.player.x == x and self.player.y == y:
                    items.append(Style.DIM + Fore.CYAN + str(tile) + Style.RESET_ALL)
                elif tile.has_weapon:
                    items.append(Style.DIM + Fore.GREEN + str(tile) + Style.RESET_ALL)
                elif tile.type == TileType.EMPTY:
                    items.append(Style.DIM + Fore.RED + str(tile) + Style.RESET_ALL)
                else:
                    items.append(str(tile))
            print(' '.join(items))

def solve(url):
    assert requests.get(f"{url}/regenerate").status_code == 200
    for i in range(100):
        game = Game(url)
        print(f"Time left: {game.player.time}")
        game.print_map()
        print(game.solve())

if __name__ == '__main__':
    solve('http://83.136.250.103:30380')