Skip to content

Instantly share code, notes, and snippets.

@vjeranc

vjeranc/day12.py

Last active December 14, 2023 14:30
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save vjeranc/a24c49d3946a0a07d07f6618a888fca4 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save vjeranc/a24c49d3946a0a07d07f6618a888fca4 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. vjeranc revised this gist Dec 12, 2023. 1 changed file with 10 additions and 14 deletions.
    24 changes: 10 additions & 14 deletions day12.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,3 @@
    from functools import *

    ans = 0
    for l in open(0):
    P, G = l.split()
    @@ -9,16 +7,14 @@
    N, M = len(P), len(G)
    cdot = [P[i:].count('.') for i in range(N)]

    @cache
    def dp(i, j) -> int:
    if i>=N: return j==M and i==N
    ans = 0
    if P[i] in '.?': ans += dp(i+1, j)
    if j==M or i+G[j]>=N: return ans
    if P[i] in '#?' and cdot[i+G[j]]-cdot[i]==0 and P[i+G[j]]!='#':
    ans += dp(i+G[j]+1, j+1)
    return ans

    ans += dp(0, 0)
    dp = [[0]*(M+1) for _ in range(N+1)]
    dp[N][M] = 1
    for i in range(N-1, -1, -1):
    for j in range(M, -1, -1):
    if P[i] in '.?': dp[i][j] += dp[i+1][j]
    if j==M or i+G[j]>=N: continue
    if P[i] in '#?' and cdot[i+G[j]]-cdot[i]==0 and P[i+G[j]]!='#':
    dp[i][j] += dp[i+G[j]+1][j+1]
    ans += dp[0][0]

    print(ans)
    print(ans)
  2. vjeranc created this gist Dec 12, 2023.
    24 changes: 24 additions & 0 deletions day12.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,24 @@
    from functools import *

    ans = 0
    for l in open(0):
    P, G = l.split()
    G = tuple(map(int, G.split(',')))
    P, G = '?'.join([P]*5), G*5 # part 2
    P = P+'.'
    N, M = len(P), len(G)
    cdot = [P[i:].count('.') for i in range(N)]

    @cache
    def dp(i, j) -> int:
    if i>=N: return j==M and i==N
    ans = 0
    if P[i] in '.?': ans += dp(i+1, j)
    if j==M or i+G[j]>=N: return ans
    if P[i] in '#?' and cdot[i+G[j]]-cdot[i]==0 and P[i+G[j]]!='#':
    ans += dp(i+G[j]+1, j+1)
    return ans

    ans += dp(0, 0)

    print(ans)