Denoise with a nearest-pattern denoiser

Generation in a diffusion model is a loop of guess and step. Here the network is replaced by a nearest-pattern guesser.

What to build

A program that denoises a noisy image towards the closest of some known patterns.

Requirements

  • Each pattern is a name and a string of 0 and 1 characters, one per pixel.
  • At each step find the pattern closest to the current image (smallest sum of squared differences, the first listed on a tie), then replace each pixel p by p + s * (b - p), where b is the pattern's pixel.
  • After each step print step T: NAME and the pixels with four decimal places.
  • After all steps print result: NAME, the closest pattern to the final image. With zero steps print only this line.

Input

Line 1: k. Then k lines name bits. Then the noisy pixels, the number of steps and the step size s.

Output

One line per step, then the result line.

Constraints

1 ≤ k ≤ 10; 0 ≤ steps ≤ 10; 1 to 20 pixels.

Example

Input:

2
bar 0110
edges 1001
0.75 0.5 0.25 0.25
2
0.5

Output:

step 1: edges 0.8750 0.2500 0.1250 0.6250
step 2: edges 0.9375 0.1250 0.0625 0.8125
result: edges

Why it works

Each step moves the image towards what the guesser believes is underneath the noise, so the distance to that pattern shrinks, which is the same loop a real diffusion model repeats with a trained network.

Examples

Example 1 · Input
2
bar 0110
edges 1001
0.75 0.5 0.25 0.25
2
0.5
Expected output
step 1: edges 0.8750 0.2500 0.1250 0.6250
step 2: edges 0.9375 0.1250 0.0625 0.8125
result: edges
Example 2 · Input
2
dark 00
light 11
0.5 0.5
1
0.5
Expected output
step 1: dark 0.2500 0.2500
result: dark

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Write a function that returns the pattern with the smallest sum of squared differences to the image; on a tie keep the first one listed.

Hint 2

At each step guess from the current image, then move every pixel `s` of the way towards the guessed pattern: `p + s * (b - p)`.

Hint 3

Print four decimal places. The final line is a guess made from the final image.

Solution

Show one correct solution (try it yourself first)
k = int(input())
patterns = []
for _ in range(k):
    name, bits = input().split()
    patterns.append((name, [int(c) for c in bits]))
img = list(map(float, input().split()))
steps = int(input())
s = float(input())


def guess(image):
    best, best_d = None, None
    for name, bits in patterns:
        d = sum((p - b) ** 2 for p, b in zip(image, bits))
        if best_d is None or d < best_d:
            best, best_d = (name, bits), d
    return best


for t in range(1, steps + 1):
    name, bits = guess(img)
    img = [p + s * (b - p) for p, b in zip(img, bits)]
    print(f"step {t}: {name} " + " ".join(f"{p:.4f}" for p in img))
print("result:", guess(img)[0])

Lesson: Image generation →