Создание алгоритма для решения проблемы в Python

Question

Цель алгоритма:

ссылка на фотографии, которые я сделал во время интервью амазонки:

[https://boards.wetransfer.com/board/shl7w5z1e62os7nwv20190618224258/latest][pictures]

Восемь домов, представленных клетками, расположены по прямой линии. Каждый день каждая клетка конкурирует со своими соседними клетками (соседями). Целочисленное значение 1 представляет активную ячейку, а значение 0 представляет неактивную ячейку. Если соседи по обе стороны ячейки активны или неактивны, ячейка становится неактивной на следующий день, в противном случае ячейка становится активной. Две ячейки на каждом конце имеют одну соседнюю ячейку, поэтому предположим, что незанятое пространство на противоположной стороне является неактивной ячейкой. Даже после обновления состояния ячейки учитывайте его предыдущее состояние при обновлении состояния других ячеек. Информация о состоянии всех ячеек должна обновляться одновременно.

Создать алгоритм для вывода состояния ячеек по истечении заданного количества дней.

Введите:

Входные данные для функции / метода состоят из двух аргументов: states, список целых чисел, представляющих текущее состояние ячеек, days, целое число, представляющее количество дней.

Выход:

Возвращает список целых чисел, представляющих состояние ячеек по истечении заданного количества дней

Примечание:

Элементы списка состояний содержат только 0 и 1

TestCase 1:

Ввод: [1,0,0,0,0,1,0,0] , 1

Ожидаемое возвращаемое значение: 0 1 0 0 1 0 1 0

TestCase 2:

Ввод: [1,1,1,0,1,1,1,1] , 2

Ожидаемое возвращаемое значение: 0 0 0 0 0 1 1 0

Что я пробовал:

def cellCompete(states, days):
    # WRITE YOUR CODE HERE
    il = 0; 
    tl = len(states);
    intialvalue = states
    results = []
    states = []
    for i in range(days):
      #first range
      if(intialvalue[il] != intialvalue[il+1]):
        print('value of index 0 is : ',reverse(intialvalue[il]))
        results.append(reverse(intialvalue[il]))
      else:
        print('value of index 0 is :', intialvalue[il])
        results.append(intialvalue[il])
      print("-------------------")  

      #range middle
      while il < tl-2:
        if(intialvalue[il] != intialvalue[il+1] or intialvalue[il+1] != intialvalue[il+2]):
          print('value of index',il+1,'is : ',reverse(intialvalue[il+1]))
          results.append(reverse(intialvalue[il+1]))
        else:
          print('value of index', il+1,'is :', intialvalue[il+1])
          results.append(intialvalue[il+1])
        print("-------------------") 
        il += 1

      #range last
      if(intialvalue[tl-2] != intialvalue[tl-1]):
        print('value of index',tl-1,'is : ',reverse(intialvalue[tl-1]))
        results.append(reverse(intialvalue[tl-1]))
      else:
        print('value of index',tl-1,'is :', intialvalue[tl-1])
        results.append(intialvalue[tl-1])
      print("-------------------")  

      print('Input: ',intialvalue)
      print('Results: ',results)
      initialvalue = results

def reverse(val):
    if(val == 0):
      return 1
    elif(val == 1):
      return 0
print("-------------------------Test case 1--------------------")
cellCompete([1,0,0,0,0,1,0,0],1)
print("-------------------------Test case 2--------------------")
cellCompete([1,1,1,0,1,1,1,1],2)

Я относительно новичок в python и не смог завершить этот алгоритм для второго случая на этом питоне

Answer 1

Вот гораздо более короткая процедура, которая решает вашу проблему.

def cellCompete(states, days):
    n = len(states)
    for day in range(days):
        houses = [0] + states + [0]
        states = [houses[i-1] ^ houses[i+1] for i in range(1, n+1)]
    return states

print(cellCompete([1,0,0,0,0,1,0,0] , 1))
print(cellCompete([1,1,1,0,1,1,1,1] , 2))

Распечатка того, что вы хотите (хотя и с включенными скобками списка):

[0, 1, 0, 0, 1, 0, 1, 0]
[0, 0, 0, 0, 0, 1, 1, 0]

Эта процедура добавляет нули часового в каждый конец списка состояний домов. Затем он использует понимание списка, чтобы найти новые состояния домов. Все это повторяется надлежащее количество раз, прежде чем возвращаются состояния домов.

Расчет состояния нового дома составляет houses[i-1] ^ houses[i+1]. Этот символ ^ является побитовым эксклюзивным или. Значение равно 1, если два значения различны, и 0, если два значения одинаковы. Это как раз то, что нужно в вашей проблеме.

Answer 2

Рекурсивная версия:

def cell_compete(states, days):
    s = [0] + states + [0]
    states = [i ^ j for i, j in zip(s[:-2], s[2:])]  # Thanks @RoyDaulton
    return cell_compete(states, days - 1) if days > 1 else states

Нерекурсивная версия, которая также избегает расширения списка путем добавления крайних [0] элементов:

def cell_compete(states, days):
    for _ in range(days):
        states = [states[1]] + [i ^ j for i, j in zip(states[:-2], states[2:])] + [states[-2]]
    return states

Answer 3

Пока все пытаются сделать самую простую из возможных версий, есть более сложная версия.Это очень похоже на предыдущие ответы, за исключением того, что вместо сохранения состояния в функции, это решение состоит из двух частей.Одна - это служебная функция, которую мы хотим вызывать, другая - генератор, который отслеживает состояния.

Основным отличием здесь является то, что генератор берет компаратор и исходное состояние, которое будет видоизменяться.Генератор также может быть отправлен в качестве параметра, так что генератор может помочь разделить логику того, сколько состояний вы хотите сгенерировать, и иметь возможность мутировать из фактического состояния на неопределенный срок.

def mutator(state, comparator):
    while True:
        states = [0] + state + [0]
        state = [
            comparator(states[cellid-1], states[cellid+1])
            for cellid in range(1, len(states)-1)
        ]
        yield state

def cellCompete(states, days):
    generator = mutator(states, lambda x, y: x ^ y)

    for idx, states in enumerate(generator):
        if idx+2 > days:
            break

    return states

print(cellCompete([1,0,0,0,0,1,0,0] , 1))
print(cellCompete([1,1,1,0,1,1,1,1] , 2))

Кроме того, я добавил компаратор, который позволяет нам выполнять некие неопределенные операции над обоими элементами.Это может позволить расширить код за пределы исходной спецификации.Это, очевидно, излишняя реализация, но, как уже упоминалось, это должен быть ответ на собеседование, и, насколько мне нравится, видеть прямой ответ, если кто-то может придумать гибкий ответ в то же время, то почему бы и нет.

Answer 4

Подобно тому, как Рори использует XOR, но без необходимости внутреннего понимания.Сдвиньте бит на 2 и обрежьте лишний бит слева, взяв модуль:

def process(state, r):
    n = int(''.join(map(str,state)), 2)
    for i in range(r):
        n = ((n ^ n << 2) >> 1) % 256

    return list(map(int,format(n, "08b")))

process([1,1,1,0,1,1,1,1], 2)
# [0, 0, 0, 0, 0, 1, 1, 0]

process([1,0,0,0,0,1,0,0] , 1)
# [0, 1, 0, 0, 1, 0, 1, 0]

Answer 5

Другая возможность:

def cellCompete(states,days):
    newstates = []
    added_states = [0] + states + [0]
    for counter,value in enumerate(states):
        newstates.append(int((added_states[counter] != added_states[counter+2])))

    if days > 1:
        return cellCompete(newstates,days-1)
    else:
        return newstates

print(cellCompete([1,1,1,0,1,1,1,1],2))