Как разбудить большинство людей в комнате? - PullRequest
Новая
       13

Как разбудить большинство людей в комнате?

0 голосов
/ 02 марта 2019

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

Когда вы будите человека, люди рядом с ним также просыпаются от сна, потому что расстояние близко.Например, в комнате спят три человека.Если вы разбудите человека посередине, то все три человека проснутся, то есть SSS станет ....

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

Проблема в том, что, учитывая комнату s, заполненную спящими людьми S и бодрствующими людьми ..После пробуждения k человек, какое максимальное количество бодрствующих людей в этой комнате.

Хитрый пример: s = S.SSSS и k = 2.

  1. бодрствующий человек s[4], тогда комната будет S.S...
  2. бодрствующий человек s[1], тогда комната будет ......

То есть, вы можете разбудить всех в этой комнате после пробуждения человека s[4] и человека s[1].Таким образом, ответом этого примера будет 6 человек вместо 5.

Я написал свое решение на python, перечислив все комбинации индекса людей, которых я мог разбудить.Разбудить их и подсчитать количество бодрствующих людей.

Работает только с короткими строками и небольшим количеством людей.

Думаю, мне нужны некоторые улучшения на алгоритмическом уровне.Любое предложение или подсказка будет принята с благодарностью.Заранее спасибо. 

import sys
import itertools

memo = {}

def wake(s, i):
    if i in memo: 
        return memo[i]
    s = list(s)
    for n in i:
        if n == 0:
            s[n], s[n+1] = '.', '.'
        elif n == len(s)-1:
            s[n-1], s[n] = '.', '.'
        else:
            s[n-1], s[n], s[n+1] = '.', '.', '.'
    memo[i] = s.count('.')
    return memo[i]

if __name__ == '__main__':
    with open(sys.argv[1]) as f:
        line = f.readline()
        n, k = map(int, list(line.rstrip().split(' ')))
        line = f.readline()
        s = line.rstrip()

    ans = 0
    for i in itertools.combinations(range(n), k):
        temp = wake(s, i)
        if temp > ans:
            ans = temp

    print(ans)

Для целей тестирования я поставлю несколько тестовых случаев и правильные ответы ниже.

Format:
n k
s
ans

5 3
.....
5

12 2
.SSSS.SS.SSS
9

7 1
..S.SS.
6

67 4
SS.S...S....SS..S..S.S.S...SS...SSS..SS.SS.SSSSS...S.S.S...S......S
48

29 2
.S.....SSSSS.SSSS...SS.SSS.SS
18

79 6
.S...SSS.SSS..SSSS.SSSSS.SS.S.SS.SS.SSSSSSS.SS...SS.S.SSS.SS.S.SS..S..S.SSS.SS.
47

41 9
.S.S...S.S.....S.SS.SS.SS.SS.S.SS.SS.....
41

91 67
...SS.SS....S...S.S.SS...SSS.SSSSSSS.....SS..S.S.SS...S..S..S.SS.......SSSSS.S.S...S.SS.S.S
91


7 97
SSSS.SS
7

276 23
SSSSSS.SSS..SSS.SS.S.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSS.S.SSS.SSSSSS.SSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSSS.S.SSSS.SSSSSSSSSSSS.SSSSSSSSSSSSSSSS.SSS.S.SS.SSSSSSS.SSSSSSSS.SSS.S.
100

Ответы [ 3 ]

0 голосов
/ 02 марта 2019

Вот мое решение. 

import pandas as pd


def count_all(text, string):
    pos = string.find(text)
    if len(string) == 0 or pos == -1:
        return 0
    return 1 + count_all(text, string[pos+len(text):])


def calculate_ans(input_str, k)->int:
    if 'check':
        if len(input_str) == 0 or \
                (input_str.find('S') == -1 and input_str.find('.') == -1):
            return 0

        if k <= 0 or pd.isna(k):
            return input_str.count('.')

    for cur_str in ['SSS', 'S.S', 'ST.TS', 'SS', 'S']:
        count_ns = min(count_all(cur_str, input_str), k)
        if count_ns > 0:
            if cur_str != 'S.S':
                input_str = input_str.replace(cur_str, len(cur_str) * '.', int(count_ns))
            else:
                input_str = input_str.replace(cur_str, 'T.T', int(count_ns))
            k -= count_ns
        if k == 0:
            break

    return input_str.count('.') + input_str.count('T')


def carson_demo():
    df = pd.read_csv('table.csv')
    for index, (input_str, k, answer) in df.iterrows():
        ans = 0 if pd.isna(input_str) else calculate_ans(input_str, k)
        df.at[index, 'answer'] = int(ans)  # update
    df['answer'] = df['answer'].astype(int, errors='ignore')
    df['k'] = df['k'].astype(int, errors='ignore')
    df.to_csv('table.csv', index=False)


if __name__ == '__main__':
    carson_demo()

table.csv (до) 

input_str,k,answer
.....,3,
.SSSS.SS.SSS,2,
..S.SS.,1,
SS.S...S....SS..S..S.S.S...SS...SSS..SS.SS.SSSSS...S.S.S...S......S,4,
.S.....SSSSS.SSSS...SS.SSS.SS,2,
.S...SSS.SSS..SSSS.SSSSS.SS.S.SS.SS.SSSSSSS.SS...SS.S.SSS.SS.S.SS..S..S.SSS.SS.,6,
.S.S...S.S.....S.SS.SS.SS.SS.S.SS.SS.....,9,
...SS.SS....S...S.S.SS...SSS.SSSSSSS.....SS..S.S.SS...S..S..S.SS.......SSSSS.S.S...S.SS.S.S,67,
SSSS.SS,97,
SSSSSS.SSS..SSS.SS.S.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSS.S.SSS.SSSSSS.SSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSSS.S.SSSS.SSSSSSSSSSSS.SSSSSSSSSSSSSSSS.SSS.S.SS.SSSSSSS.SSSSSSSS.SSS.S.,23,

table.csv (после) 

input_str,k,answer
.....,3,5
.SSSS.SS.SSS,2,9
..S.SS.,1,6
SS.S...S....SS..S..S.S.S...SS...SSS..SS.SS.SSSSS...S.S.S...S......S,4,48
.S.....SSSSS.SSSS...SS.SSS.SS,2,18
.S...SSS.SSS..SSSS.SSSSS.SS.S.SS.SS.SSSSSSS.SS...SS.S.SSS.SS.S.SS..S..S.SSS.SS.,6,47
.S.S...S.S.....S.SS.SS.SS.SS.S.SS.SS.....,9,41
...SS.SS....S...S.S.SS...SSS.SSSSSSS.....SS..S.S.SS...S..S..S.SS.......SSSSS.S.S...S.SS.S.S,67,91
SSSS.SS,97,7
SSSSSS.SSS..SSS.SS.S.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSS.S.SSS.SSSSSS.SSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSSS.S.SSSS.SSSSSSSSSSSS.SSSSSSSSSSSSSSSS.SSS.S.SS.SSSSSSS.SSSSSSSS.SSS.S.,23,100
0 голосов
/ 03 марта 2019

Исправление небольшой проблемы перекрытия в алгоритме Даниэля.

ans = 0

if n <= 3:
    if k > 0:
        ans = n
    else:
        ans = s.count('.')
else:
    dp = [[0 for x in range(k+1)] for y in range(n)]
    dp[0][1] = s[:2].count('S')
    dp[1][1] = s[:3].count('S')
    dp[2][1] = max(s[:3].count('S'), s[1:4].count('S'))
    for j in range(2,k+1):
        dp[0][j] = dp[0][1]
        dp[1][j] = dp[1][1]
        dp[2][j] = s[:4].count('S')

    for i in range(3,n-1):
        for j in range(1,k+1):
            dp[i][j] = max(dp[i-3][j-1] + s[i-1:i+2].count('S'),
                           dp[i-1][j])

    for j in range(k+1):
        dp[n-1][j] = dp[n-2][j]

    ans = dp[n-1][k]

    ans += s.count('.')

    print(ans)
0 голосов
/ 02 марта 2019

Пусть dp[n][k] будет числом 'S' людей, которых мы разбудили, если мы имеем дело с n первыми людьми и уже разбудили k людей.Для dp[n][k] я полагаю, что нет причины разбудить человека с номером n, потому что нет человека n+1, которого мы могли бы разбудить (потому что мы имеем дело только с n первыми людьми), так что лучше разбудите человека n-1, а также человек n проснулся.Эту логику я использую позже.

Тогда, если n <= 3, мы можем разбудить всех n людей, если у нас есть ходы, то есть k > 0.Если у нас нет движений, то ответ - это число уже пробужденных людей.

Если n > 3:

  • , если k = 0, то dp[n][k] = dp[n][0] = 0, потому чтомы никого не разбудили.
  • , если k > 0, то dp[n][k] = max(dp[n - 3][k - 1] + s[n - 3 : n].count('S'), dp[n - 1][k]).Здесь мы рассматриваем 2 случая: если мы разбудили человека n-1, то n-2, n-1, n -ого человека проснулись, и мы потеряли 1 ход, поэтому мы подсчитываем количество людей, которых мы только что разбудили (s[n - 3 : n].count('S')), и проверяем максимальное количестводля остальных n-3 человек и k-1 ходов: dp[n - 3][k - 1].Если мы никого не разбудили, то у нас есть n -й человек, если его начальное состояние и у нас все еще есть k ходов.Таким образом, ответ в этом случае dp[n - 1][k].

Ответ max(dp[n][k]) + s.count('.'): dp[n][k] относится только к числу спящих людей, но мы их разбудили.Итак, чтобы получить полный ответ, мы просто добавляем количество людей, которые уже не спали. 

ans = 0

if n <= 3:
    if k > 0:
        ans = n
    else:
        ans = s.count('.')
else:
    dp = [[0 for x in range(k + 1)] for y in range(n)]
    dp[2][1] = s[:3].count('S')
    for i in range(3, n):
        t = s[i - 3 : i].count('S')
        for j in range(1, k + 1):
            dp[i][j] = max(dp[i - 3][j - 1] + t, dp[i - 1][j])

    for i in range(2, n):
        ans = max(ans, dp[i][k])

    ans += s.count('.')

print(ans)
...