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
0and1characters, 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: NAMEand 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
2 bar 0110 edges 1001 0.75 0.5 0.25 0.25 2 0.5
step 1: edges 0.8750 0.2500 0.1250 0.6250 step 2: edges 0.9375 0.1250 0.0625 0.8125 result: edges
2 dark 00 light 11 0.5 0.5 1 0.5
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])