36. Abelian Sandpile
The door opened without knocking. This meant Johann.
He entered carrying something under his arm— a flat wooden box, shallow and slotted, its compartments divided by thin strips of birch. Sand dusted his sleeve and the front of his coat.
„Before you say anything,“ Johann announced, setting the box on Mihkel's desk with ceremony, „this is not a toy. It is a philosophical instrument.“
Mihkel looked at the box. It was, unmistakably, a toy.
„A Livonian peddler sold it to me,“ Johann continued, pulling a chair close and sitting down uninvited. „He said Cistercian monks used these to teach patience. You heap the sand high in one cell, and then—“
He scooped a pinch of fine sand from a pouch and piled it into the centre compartment until the tiny mound trembled and slid sideways, grains tumbling left and right over the birch dividers into the neighbouring slots.
„You see?“ Johann said, delighted. „It topples. And then sometimes those topple. And then those. It goes on and on until everything is low and calm.“
Mihkel watched the last few grains settle. The arrangement was different now— lower, broader, quieter.
„Empires in miniature,“ Johann said, leaning back with satisfaction. „You heap power in one place, and eventually it spreads until no one has enough to fall.“
„Or until everyone has just enough to stay,“ Mihkel replied, still watching the box.
Johann waved a hand. „Same thing, different poetry. But here is my question, Herr Logiker—“
He reset the box with a gentle shake, smoothing the sand into uneven heaps.
„If I tell you how high each pile is at the start, can you tell me where the sand will rest without watching it fall?“
Mihkel raised an eyebrow.
„A bet,“ Johann added, grinning the way he always did when he believed he had cornered something. „One mug of good Dorpat beer says you cannot predict the final state faster than the sand itself settles.“
Mihkel looked at the heaps. Three compartments. Two grains, three grains, two grains. The centre one already trembling.
„By tomorrow evening?“ Mihkel asked.
„By tomorrow evening,“ Johann confirmed. He stood, brushed sand from his trousers, and paused at the door.
„The monks said the lesson was humility. That no matter how high you build, the sand always finds its own level.“
He smiled. „I think the lesson is patience. But I suspect you'll try to prove them both wrong.“
The door closed. Sand glittered faintly on the desk.
On the input tape, you’ll get sandpile heights in unary format, separated by commas. Your task is to simulate a 1D Abelian sandpile until it becomes stable.
Stability rule:
- If a pile has fewer than 3 grains, it is stable.
- If a pile has 3 or more grains, it topples.
When a pile topples:
- It loses 2 grains.
- 1 grain moves to the left neighbor (or is lost if there is no left neighbor).
- 1 grain moves to the right neighbor (or is lost if there is no right neighbor).
Keep applying topples until every pile is stable. Although intermediate steps may differ, the final stable state does not depend on the order of toppling. Then output the final pile heights, again in unary and separated by commas.
Example:
- Start:
||,|||,|| - 2nd pile topples:
||,|||,||→|||,|,||| - 3rd pile topples:
|||,|,|||→|||,||,| - 1st pile topples:
|||,||,|→|,|||,| - 2nd pile topples:
|,|||,|→||,|,||(now stable)