#! /usr/bin/env python

from collections import namedtuple
from operator import itemgetter
from typing import List
import random

import numpy as np


Voxel = namedtuple('Voxel', 'x y z')


class Voxels:
    """Turns text input into a list of Voxels."""

    def __init__(self, text: str):
        depth = 1 + int(max(text))
        lines = text.splitlines()
        height = len(lines)
        width = max(map(len, lines))
        self.model = np.zeros((width, height, depth), int)
        voxels = []
        for j, line in enumerate(lines):
            y = len(lines) - j  # Origin is at lower left.
            for x, ch in enumerate(line):
                if ch.isnumeric():  # We ignore ocean pixels.
                    assert ch > '0', (ch, line)
                    for z in range(1, int(ch) + 1):
                        voxel = Voxel(x, y, z)
                        self.model[voxel] = True
                        voxels.append(voxel)
        random.shuffle(voxels)
        self.voxels = voxels

    def render(self) -> str:
        for voxel in self.voxels:
            assert self.model[voxel], voxel
        width, height, depth = self.model.shape
        return '\n'.join(self._raster(height - 1 - y)  # origin LL
                         for y in range(height))

    def _raster(self, y) -> str:
        width = self.model.shape[0]
        return ''.join(self._depth_val(x, y)
                       for x in range(width))

    def _depth_val(self, x, y) -> str:
        """Returns blank for ocean, or 1..3 for coast..mountain."""
        depth = self.model.shape[2]
        val = ' '  # Ocean, by default.
        for z in range(depth):
            if self.model[(x, y, z)]:
                val = str(z)
        return val


def three_d_print(voxels: List[Voxel]) -> str:
    assert len(voxels)
    width = max(map(itemgetter(0), voxels))
    height = max(map(itemgetter(1), voxels))
    depth = max(map(itemgetter(2), voxels))
    out = np.zeros((width, height, depth), int)
    cur = voxels[0]  # 3-D print head position
    elapsed = 0  # Zero cost to move print head to initial voxel.
    for x, y, z in voxels:
        _verify_feasible(out, x, y, z)
        out[(x, y, z)] = True

def _verify_feasible(out, x, y, z):
    """Ensure there is a foundation to print a mountain top upon."""
    for z1 in range(1, z):
        assert out[(x, y, z1)], (x, y, z)


islands = Voxels("""
                  1
    111          1121
 1112211       11223211
1112233211      112321
  122211          13
    1211    1      1                         11
     1     1211                             12321
          1123211                            121
           1121                               1
            11
""")
print(three_d_print(islands.voxels))

# volcanic voxels
#
# Some volcanic islands are depicted below.
# A 3-D printer will create a model of them.
# The input of (x, y, z) voxels is now in a randomly permuted order.
# Write a function that puts the voxels in "better than naïve" order.

@@ -1810,32 +1810,36 @@
 els)%0A    width =
+ 1 +
  max(map(itemget
@@ -1867,16 +1867,20 @@
 height =
+ 1 +
  max(map
@@ -1911,24 +1911,28 @@
 %0A    depth =
+ 1 +
  max(map(ite
@@ -2121,23 +2121,21 @@
     for 
-x, y, z
+voxel
  in voxe
@@ -2168,23 +2168,22 @@
 le(out, 
-x, y, z
+*voxel
 )%0A      
@@ -2192,25 +2192,237 @@
 out%5B
-(x, y, z)%5D = True
+voxel%5D = True%0A        elapsed += _manhattan_distance(cur, voxel)%0A    return elapsed, out%0A%0A%0Adef _manhattan_distance(a: Voxel, b: Voxel) -%3E int:%0A    return (abs(a.x - b.x)%0A            + abs(a.y - b.y)%0A            + abs(a.z - b.z))%0A
 %0A%0Ade
@@ -2961,16 +2961,23 @@
 d_print(
+sorted(
 islands.
@@ -2984,16 +2984,20 @@
 voxels))
+%5B0%5D)
 %0A%0A# volc
@@ -3051,13 +3051,13 @@
 ted 
-below
+above
 .%0A# 

Add manhattan_distance