See link embedded in source

wabbits.py

#!/usr/bin/env python3

# https://www.reddit.com/r/riddles/comments/9sdy1y/a_hunter_and_a_rabbit_please_help_me_find_the/?utm_source=reddit-android

from bitstring import BitArray
import collections

class State(object):
    def __init__(self, n, data):
        self.data = data
        self.parents = []
        self.level = 0

    def __repr__(self):
        return self.data.bin

    @staticmethod
    def all_ones(n):
        return State(n, BitArray(uint=(1 << n) - 1, length=n))

    @staticmethod
    def all_zeros(n):
        return State(n, BitArray(uint=0, length=n))

    def final(self):
        return self.data.all(False)

    def dominates(self, other):
        return self.data | other.data == other.data

    def __eq__(self, other):
        return self.data == other.data

    def __hash__(self):
        return hash(self.data.uint)

    def is_palindrome(self):
        reverse = self.data[len(self.data)//2 + len(self.data)%2:]
        reverse.reverse()
        return self.data[:len(self.data)//2] == reverse

    def next_states(self):
        potential_rabbits = [i for i, include in enumerate(self.data) if include]

        # if palindromic, we need only consider the first half of the shot options
        shot_options = potential_rabbits if not self.is_palindrome() else potential_rabbits[:len(potential_rabbits) // 2 + len(potential_rabbits) % 2]

        for shot in shot_options:
            # it is only advantageous to shoot where a rabbit could be

            # compute new state by starting with a fresh state
            # and putting a potential rabbit everywhere a potential rabbit could jump
            new_state = State.all_zeros(len(self.data))
            new_state.level = self.level + 1

            for potential_rabbit in potential_rabbits:
                if potential_rabbit != shot:
                    # the potential rabbit we shot cannot jump
                    if potential_rabbit != 0:
                        # can't hop left if already at the zeroth position
                        new_state.data[potential_rabbit - 1] = 1
                    if potential_rabbit != len(self.data) - 1:
                        # can't hop right if already at the (n-1)th position
                        new_state.data[potential_rabbit + 1] = 1

            yield (shot, new_state)

def shortest_path(n):
    start_state = State.all_ones(n)
    start_state.parents = [(None, None)]
    all_states = set([start_state])
    states = collections.deque([start_state])
    while states:
        state = states.popleft()
        # print(f'trying {state}')

        if state.final():
            return state

        for (shot, next_state) in state.next_states():
            # print(f'arrived at {next_state}')
            if next_state not in all_states:
                if not any(state.dominates(next_state) for state in all_states):
                    next_state.parents.append((shot, state))
                    all_states.add(next_state)
                    states.append(next_state)

def print_state_path(state):
    while True:
        shot, state = state.parents[0]
        if state is None:
            break
        print(state)
        bufferf = list(' ' * len(state.data))
        bufferf[shot] = '^'
        print(''.join(bufferf))
    
# for i in range(20, 35):
#     state = shortest_path(i)
#     print(state.level == 2 * (i - 2))

while True:
    n = input()
    if n == 'q':
        break
    else:
        n = int(n)
        state = shortest_path(n)
        print_state_path(state)