title: Patch the Image

text:
# Question
Title: Patch the Image
In a popular image editing software there is a feature, that patches (The term used in image processing is *inpainting* as @mınxomaτ pointed out.) a selected area of an image, based on the information *outside* of that patch. And it does a quite good job, considering it is just a program. As a human, you can sometimes see that something is wrong, but if you squeeze your eyes or just take a short glance, the *patch* seems to fill in the *gap* quite well.

### Challenge

Given an image and a mask that specifies a rectangular area of the image should be patched (also as image, or any other preferred format), your program should try to fill the specified area with a patch that tries to blend in with the rest of the image. The program cannot use the information of the original image that was within the specified area.

You can assume that the patch always is at least it's width away from the sides, and it's height away from the top and the bottom of the image. That means the maximum area of a patch is 1/9 of the whole image.

Please add a brief description on how your algorithm works.

### Voting

Voters are asked to judge how well the algorithms perform and vote accordingly.

Some suggestions on how to judge: (Again, thanks @mınxomaτ for the some more criterions.)

* If you squint your eyes and the picture looks fine?
* Can you exactly tell where the patch is?
* How well are structures and textures from the image background and surrounding area continued?
* How much stray false color pixels does the edited area contain?
* Are there any uniformly colored blobs/blocks in the area that don't seem to belong there?
* Does the edited area have any drastic color / contrast or brightness shifts compared to the rest of the image?

### Validity criterion

In order for a submission to be valid, the output image must exactly match the input image outside of the specified area.

### Test case

On the left the source image, on the right the corresponding mask:

# Answer
## AutoIt, VB

### Introduction

This is an implementation of the *Object Removal by Exemplar-Based Inpainting* algorithm developed by A. Criminisi, P. Perez (Cambridge Microsoft Research Ltd.) and K. Toyama (Microsoft) \[X\]. This algorithm is targeted at high-information images (and video frames) and aims to be the balance between structural reconstruction and organic reconstruction. *Paragraphs of this answer contain full text quotes from the original paper (since it is no longer officially available) to make this answer more self-contained.*

### The Algorithm

**Goal**: Replace a selected (*masked*) area (preferably a visually separated foreground object) with visually plausible backgrounds.

In previous work, several researchers have considered texture synthesis as a way to fill large image regions with "pure" textures - repetitive two-dimensional textural patterns with moderate stochasticity. This is based on a large body of texture-synthesis research, which seeks to replicate texture *ad infinitum*, given a small source sample of pure texture \[1\] \[8\] \[9\] \[10\] \[11\] \[12\] \[14\] \[15\] \[16\] \[19\] \[22\].

As effective as these techniques are in replicating consistent texture, they have difficulty filling holes in photographs of real-world scenes, which often consist of linear structures and composite textures – multiple textures interacting spatially \[23\]. The main problem is that boundaries between image regions are a complex product of mutual influences between different textures. In contrast to the two-dimensional nature of pure textures, these boundaries form what might be considered more one-dimensional, or linear, image structures.

*Image inpainting* techniques fill holes in images by propagating linear structures (called *isophotes* in the *inpainting* literature) into the target region via diffusion. They are inspired by the partial differential equations of physical heat flow, and work convincingly as restoration algorithms. Their drawback is that the diffusion process introduces some blur, which is noticeable.

The region to be filled, i.e., the target region is indicated by Ω, and its contour is denoted δΩ. The contour evolves inward as the algorithm progresses, and so we also refer to it as the “fill front”. The source region, Φ, which remains fixed throughout the algorithm, provides samples used in the filling process. We now focus on a single iteration of the algorithm to show how structure and texture are adequately handled by exemplar-based synthesis. Suppose that the square template Ψp ∈ Ω centred at the point p (fig. 2b), is to be filled. The best-match sample from the source region comes from the patch Ψqˆ ∈ Φ, which is most similar to those parts that are already filled in Ψp. In the example in fig. 2b, we see that if Ψp lies on the continuation of an image edge, the most likely best matches will lie along the same (or a similarly coloured) edge (e.g., Ψq' and Ψq'' in fig. 2c). All that is required to propagate the isophote inwards is a simple transfer of the pattern from the best-match source patch (fig. 2d). Notice that isophote orientation is automatically preserved. In the figure, despite the fact that the original edge is not orthogonal to the target contour δΩ, the propagated structure has maintained the same orientation as in the source region.

### Implementation and Algorithm Details

The functionality of this implementation is encapsulated in an ActiveX COM DLL which is dropped from the host program as a binary and then invoked on the fly by calling the inpainter by IID. In this specific case, the API is written in VisualBasic and can be called from any COM-enabled language. The following section of the code drops the binary:

```
Func deflate($e=DllStructCreate,$f=@ScriptDir&"\inpaint.dll")
    If FileExists($f) Then Return
    !! BINARY CODE OMITTED FOR SIZE REASONS !!
    $a=$e("byte a[13015]")
    DllCall("Crypt32.dll","bool","CryptStringToBinaryA","str",$_,"int",0,"int",1,"struct*",$a,"int*",13015,"ptr",0,"ptr",0)
    $_=$a.a
    $b=$e('byte a[13015]')
    $b.a=$_
    $c=$e("byte a[14848]")
    DllCall("ntdll.dll","int","RtlDecompressBuffer","int",2,"struct*",$c,"int",14848,"struct*",$b,"int",13015,"int*",0)
    $d=FileOpen(@ScriptDir&"\inpaint.dll",18)
    FileWrite($d,Binary($c.a))
    FileClose($d)
EndFunc

```

The library is later instantiated using the CLSID and IID:

```
Local $hInpaintLib = DllOpen("inpaint.dll")
Local $oInpaintLib = ObjCreate("{3D0C8F8D-D246-41D6-BC18-3CF18F283429}", "{2B0D9752-15E8-4B52-9569-F64A0B12FFC5}", $hInpaintLib)

```

The library accepts a GDIOBJECT handle, specifically a DIBSection of any GDI/+ bitmap (files, streams etc.). The specified image file is loaded, and drawn onto an empty bitmap constructed from `Scan0` from the input image dimensions.

The input file for this implementation is any GDI/+ compatible file format containing masked image data. The *mask(s)* is one or more uniformly colored regions in the input image. The user supplies a RGB color value for the mask, only pixels with exactly that color value will be matched. The default masking color is green (0, 255, 0). All masked regions together represent the target region, Ω, to be removed and filled. The source region, Φ, is defined as the entire image minus the target region (Φ = I−Ω).

Next, as with all exemplar-based texture synthesis \[10\], the size of the template window Ψ (aka "*scan radius*") must be specified. This implementation provides a default window size of 6² pixels, but in practice require the user to set it to be slightly larger than the largest distinguishable texture element, or “texel”, in the source region. An additional modification to the original algorithm is the user-definable "*block size*" which determines the area of pixels to be replaced with a new uniform color. This increases speed and decreases quality. Block sizes geater than 1px are meant to be used with extremely uniform areas (water, sand, fur etc.), however, Ψ should be kept at max. .5x the block size (which can be impossible depending on the mask).

To not stall the algorithm on 1bit images, every time an image with less than 5 colors is received, the window size is amplified by 10x.

Once these parameters are determined, the remainder of the region-filling process is completely automatic. In our algorithm, each pixel maintains a colour value (or “empty”, if the pixel is unfilled) and a confidence value, which reflects our confidence in the pixel value, and which is frozen once a pixel has been filled. During the course of the algorithm, patches along the fill front are also given a temporary priority value, which determines the order in which they are filled. Then, our algorithm iterates the following three steps until all pixels have been filled.

**Step 1: Computing patch priorities**

Filling order is crucial to non-parametric texture synthesis \[1\] \[6\] \[10\] \[13\]. Thus far, the default favorite has been the “onion peel” method, where the target region is synthesized from the outside inward, in concentric layers. Our algorithm performs this task through a best-first filling algorithm that depends entirely on the priority values that are assigned to each patch on the fill front. The priority computation is biased toward those patches which are on the continuation of strong edges and which are surrounded by high-confidence pixels, these pixel are the boundary, marked by the value -2. The following code recalculates the priorities:

```
For j = m_top To m_bottom: Y = j * m_width: For i = m_left To m_right
    If m_mark(Y + i) = -2 Then m_pri(Y + i) = ComputeConfidence(i, j) * ComputeData(i, j)
Next i: Next j

```

Given a patch Ψp centered at the point p for some p ∈ δΩ (see fig. 3), its priority P(p) is defined as the product of the calculated confidence (`ComputeConfidence`, or *C(p)*) and the *data term* (`ComputeData`, or *D(p)*), where

(source: imgup.net)
, where

|Ψp| is the area of Ψp, α is a normalization factor (e.g., α = 255 for a typical grey-level image), and np is a unit vector orthogonal to the front δΩ in the point p. The priority is computed for every border patch, with distinct patches for each pixel on the boundary of the target region.

Implemented as

```
Private Function ComputeConfidence(ByVal i As Long, ByVal j As Long) As Double
    Dim confidence As Double
    Dim X, Y As Long

    For Y = IIf(j - Winsize > 0, j - Winsize, 0) To IIf(j + Winsize < m_height - 1, j + Winsize, m_height - 1): For X = IIf(i - Winsize > 0, i - Winsize, 0) To IIf(i + Winsize < m_width - 1, i + Winsize, m_width - 1)
        confidence = confidence + m_confid(Y * m_width + X)
    Next X: Next Y

    ComputeConfidence = confidence / ((Winsize * 2 + 1) * (Winsize * 2 + 1))
End Function

Private Function ComputeData(ByVal i As Long, ByVal j As Long) As Double
    Dim grad As CPOINT
    Dim temp As CPOINT
    Dim grad_T As CPOINT
    Dim result As Double
    Dim magnitude As Double
    Dim max As Double
    Dim X As Long
    Dim Y As Long
    Dim nn As CPOINT
    Dim Found As Boolean
    Dim Count, num As Long
    Dim neighbor_x(8) As Long
    Dim neighbor_y(8) As Long
    Dim record(8) As Long
    Dim n_x As Long
    Dim n_y As Long
    Dim tempL As Long
    Dim square As Double

    For Y = IIf(j - Winsize > 0, j - Winsize, 0) To IIf(j + Winsize < m_height - 1, j + Winsize, m_height - 1): For X = IIf(i - Winsize > 0, i - Winsize, 0) To IIf(i + Winsize < m_width - 1, i + Winsize, m_width - 1)
        If m_mark(Y * m_width + X) >= 0 Then
            Found = False
            Found = m_mark(Y * m_width + X + 1) < 0 Or m_mark(Y * m_width + X - 1) < 0 Or m_mark((Y + 1) * m_width + X) < 0 Or m_mark((Y - 1) * m_width + X) < 0
            If Found = False Then
                temp.X = IIf(X = 0, m_gray(Y * m_width + X + 1) - m_gray(Y * m_width + X), IIf(X = m_width - 1, m_gray(Y * m_width + X) - m_gray(Y * m_width + X - 1), (m_gray(Y * m_width + X + 1) - m_gray(Y * m_width + X - 1)) / 2#))
                temp.Y = IIf(Y = 0, m_gray((Y + 1) * m_width + X) - m_gray(Y * m_width + X), IIf(Y = m_height - 1, m_gray(Y * m_width + X) - m_gray((Y - 1) * m_width + X), (m_gray((Y + 1) * m_width + X) - m_gray((Y - 1) * m_width + X)) / 2#))
                magnitude = temp.X ^ 2 + temp.Y ^ 2
                If magnitude > max Then
                    grad.X = temp.X
                    grad.Y = temp.Y
                    max = magnitude
                End If
            End If
        End If
    Next X: Next Y

    grad_T.X = grad.Y
    grad_T.Y = -grad.X

    For Y = IIf(j - 1 > 0, j - 1, 0) To IIf(j + 1 < m_height - 1, j + 1, m_height - 1): For X = IIf(i - 1 > 0, i - 1, 0) To IIf(i + 1 < m_width - 1, i + 1, m_width - 1): Count = Count + 1
        If X <> i Or Y <> j Then
            If m_mark(Y * m_width + X) = -2 Then
                num = num + 1
                neighbor_x(num) = X
                neighbor_y(num) = Y
                record(num) = Count
            End If
        End If
    Next X: Next Y

    If num = 0 Or num = 1 Then
        ComputeData = Abs((0.6 * grad_T.X + 0.8 * grad_T.Y) / 255)
    Else
        n_x = neighbor_y(2) - neighbor_y(1)
        n_y = neighbor_x(2) - neighbor_x(1)
        square = CDbl(n_x ^ 2 + n_y ^ 2) ^ 0.5
        ComputeData = Abs((IIf(n_x = 0, 0, n_x / square) * grad_T.X + IIf(n_y = 0, 0, n_y / square) * grad_T.Y) / 255)
    End If
End Function

```

The confidence term C(p) may be thought of as a measure of the amount of reliable information surrounding the pixel p. The intention is to fill first those patches which have more of their pixels already filled, with additional preference given to pixels that were filled early on (or that were never part of the target region).

This automatically incorporates preference towards certain shapes along the fill front. For example, patches that include corners and thin tendrils of the target region will tend to be filled first, as they are surrounded by more pixels from the original image. These patches provide more reliable information against which to match. Conversely, patches at the tip of “peninsulas” of filled pixels jutting into the target region will tend to be set aside until more of the surrounding pixels are filled in. At a coarse level, the term C(p) of (1) approximately enforces the desirable concentric fill order.

As filling proceeds, pixels in the outer layers of the target region will tend to be characterized by greater confidence values, and therefore be filled earlier; pixels in the center of the target region will have lesser confidence values. The data term D(p) is a function of the strength of isophotes hitting the front δΩ at each iteration. This term boosts the priority of a patch that an isophote "flows" into. This factor is of fundamental importance in our algorithm because it encourages linear structures to be synthesized first, and, therefore propagated securely into the target region. Broken lines tend to connect, thus realizing the "Connectivity Principle" of vision psychology \[7\] \[17\].

The fill order is dependent on image properties, resulting in an organic synthesis process that eliminates the risk of “broken-structure” artifacts and also reduces blocky artifacts without an expensive patch-cutting step \[9\] or a blur-inducing blending step \[19\].

**Step 2: Propagating texture and structure information**

Once all priorities on the fill front (*boundary*) have been computed, the patch Ψpˆ with highest priority is found. We then fill it with data extracted from the source region Φ. We propagate image texture by direct sampling of the source region. Similar to \[10\], we search in the source region for that patch which is most similar to Ψpˆ. Formally,

(source: imgup.net)
, where

the distance d(Ψa, Ψb) between two generic patches Ψa and Ψb is simply defined as the sum of squared differences (SSD) of the already filled pixels in the two patches. No further analysis or manipulation (*especially no blurring*) is done in this step. This calculation runs in the main cycle loop and is implemented as follows:

Getting the maximum priority:

```
For j = m_top To m_bottom: Jidx = j * m_width: For i = m_left To m_right
    If m_mark(Jidx + i) = -2 And m_pri(Jidx + i) > max_pri Then
        pri_x = i
        pri_y = j
        max_pri = m_pri(Jidx + i)
    End If
Next i: Next j

```

Finding the most similar patch:

```
min = 99999999

For j = PatchT To PatchB: Jidx = j * m_width: For i = PatchL To PatchR
    If m_source(Jidx + i) Then
        sum = 0
        For iter_y = -Winsize To Winsize: target_y = pri_y + iter_y
            If target_y > 0 And target_y < m_height Then
                target_y = target_y * m_width: For iter_x = -Winsize To Winsize: target_x = pri_x + iter_x
                    If target_x > 0 And target_x < m_width Then
                        Tidx = target_y + target_x
                        If m_mark(Tidx) >= 0 Then
                            source_x = i + iter_x
                            source_y = j + iter_y
                            Sidx = source_y * m_width + source_x
                            temp_r = m_r(Tidx) - m_r(Sidx)
                            temp_g = m_g(Tidx) - m_g(Sidx)
                            temp_b = m_b(Tidx) - m_b(Sidx)
                            sum = sum + temp_r * temp_r + temp_g * temp_g + temp_b * temp_b
                        End If
                    End If
                Next iter_x
            End If
        Next iter_y

        If sum < min Then: min = sum: patch_x = i: patch_y = j
    End If
Next i: Next j

```

**Step 3: Updating confidence values**

After the patch Ψpˆ has been filled with new pixel values, the confidence C(p) is updated in the area delimited by Ψpˆ as follows:

(source: imgup.net)

This simple update rule allows us to measure the relative confidence of patches on the fill front, without image-specific parameters. As filling proceeds, confidence values decay, indicating that we are less sure of the color values of pixels near the center of the target region. Implemented here (along with all other necessary updates):

```
x0 = -Winsize
For iter_y = -Winsize To Winsize: For iter_x = -Winsize To Winsize
    x0 = patch_x + iter_x
    y0 = patch_y + iter_y
    x1 = pri_x + iter_x
    y1 = pri_y + iter_y
    X1idx = y1 * m_width + x1
    If m_mark(X1idx) < 0 Then
        X0idx = y0 * m_width + x0
        PicAr1(x1, y1) = m_color(X0idx)
        m_color(X1idx) = m_color(X0idx)
        m_r(X1idx) = m_r(X0idx)
        m_g(X1idx) = m_g(X0idx)
        m_b(X1idx) = m_b(X0idx)
        m_gray(X1idx) = CDbl((m_r(X0idx) * 3735 + m_g(X0idx) * 19267 + m_b(X0idx) * 9765) / 32767)
        m_confid(X1idx) = ComputeConfidence(pri_x, pri_y)
    End If
Next iter_x: Next iter_y

For Y = IIf(pri_y - Winsize - 2 > 0, pri_y - Winsize - 2, 0) To IIf(pri_y + Winsize + 2 < m_height - 1, pri_y + Winsize + 2, m_height - 1): Yidx = Y * m_width: For X = IIf(pri_x - Winsize - 2 > 0, pri_x - Winsize - 2, 0) To IIf(pri_x + Winsize + 2 < m_width - 1, pri_x + Winsize + 2, m_width - 1)
    m_mark(Yidx + X) = IIf(PicAr1(X, Y).rgbRed = MaskRed And PicAr1(X, Y).rgbgreen = MaskGreen And PicAr1(X, Y).rgbBlue = MaskBlue, -1, Source)
Next X: Next Y

For Y = IIf(pri_y - Winsize - 2 > 0, pri_y - Winsize - 2, 0) To IIf(pri_y + Winsize + 2 < m_height - 1, pri_y + Winsize + 2, m_height - 1): Yidx = Y * m_width: For X = IIf(pri_x - Winsize - 2 > 0, pri_x - Winsize - 2, 0) To IIf(pri_x + Winsize + 2 < m_width - 1, pri_x + Winsize + 2, m_width - 1)
    If m_mark(Yidx + X) = -1 Then
        Found = (Y = m_height - 1 Or Y = 0 Or X = 0 Or X = m_width - 1) Or m_mark(Yidx + X - 1) = Source Or m_mark(Yidx + X + 1) = Source Or m_mark((Y - 1) * m_width + X) = Source Or m_mark((Y + 1) * m_width + X) = Source
        If Found Then: Found = False: m_mark(Yidx + X) = -2
    End If
Next X: Next Y

For i = IIf(pri_y - Winsize - 3 > 0, pri_y - Winsize - 3, 0) To IIf(pri_y + Winsize + 3 < m_height - 1, pri_y + Winsize + 3, m_height - 1): Yidx = i * m_width: For j = IIf(pri_x - Winsize - 3 > 0, pri_x - Winsize - 3, 0) To IIf(pri_x + Winsize + 3 < m_width - 1, pri_x + Winsize + 3, m_width - 1)
    If m_mark(Yidx + j) = -2 Then m_pri(Yidx + j) = ComputeConfidence(j, i) * ComputeData(j, i)
Next j: Next i

```

### Complete Code

Here's the run-able code, complete with the libraries' source code as comments.

The code is invoked by

```
inpaint(infile, outfile, blocksize, windowsize, r, g, b)

```

Examples are included in the form of

```
;~ inpaint("gothic_in.png", "gothic_out.png")
;~ inpaint("starry_in.png", "starry_out.png")
;~ inpaint("scream_in.png", "scream_out.png")
;~ inpaint("mona_in.png", "mona_out.png")
;~ inpaint("maze_in.png", "maze_out.png")
;~ inpaint("checker_in.png", "checker_out.png")

```

just uncomment the example you want to run using `CTRL`+`Q`.

### Official Test Files

This algorithm is *made* to be adjusted for each image. Therefore, the default values (and also the default masks) are completely suboptimal. The default values are chosen so that every sample can be processed in a reasonable amount of time. I highly recommend to play with irregularly shaped masks and better window sizes. Click the images to enlarge!

**Checkerboard**

(source: imgup.net)
(source: imgup.net)

**American Gothic**

(source: imgup.net)
(source: imgup.net)

**Maze**

(source: imgup.net)
(source: imgup.net)

**Mona Lisa**

(source: imgup.net)
(source: imgup.net)

(terrible mask)

**Scream**

(source: imgup.net)
(source: imgup.net)

**Starry**

(source: imgup.net)
(source: imgup.net)

### Real-World Examples

These all use custom hand-drawn masks.

(source: imgup.net)

(source: imgup.net)

(source: imgup.net)

If you have other interesting images you'd like to see included, leave a comment.

### EBII Improvements

There are multiple variants of EBII out there, created by various researchers. AnkurKumar Patel caught my attention with his collection of papers \[24\] on various EBII improvements.

Specifically the paper "*Improved Robust Algorithm For Exemplar Based Image Inpainting*" \[25\] mentions two improvements on the weighing of the priority values.

**The improvement**

The effective modification is in Step 1 (see above) of the algorithm, and extends the *C(p)* and *D(p)* effect on the priority rating for this pixel using this:

In the formula for *C* and *D* given above, and are respectively the normalization factor (e.g., α = 255), the isophote vector, and the unit vector orthogonal to the front in the point p.

Further,

The priority function is defined as the weight sum of the regularized confidence term *C(p)* and the new data term *D(p)*. Where α is the adjustment coefficient, satisfying 0\<w\<1. Finally the robust priority function *Rp(p)* is defined follows:

Where α and β are respectively the component weights of the confidence and the data terms. Note that *α+β=1*.

**Objective scoring**

What is really interesting though is that this paper contains a proposed (and simple!) method for scoring the performance if EBII algorithms. Take this with a grain of salt though, as this is a method chosen by the paper authors themselves to verify the effectiveness of the proposed variance approach and the improvement on several images.

The result evaluation is performed by comparing the PSNR (the Peak Signal-to-Noise Ratio \[26\]) between the restored image and original image. Generally the higher the PSNR value the larger the similarity of the repaired image to the original. The equation to calculate the PSNR is as follows:

These are the staggering 2 (two!) real-world test images they used:

(source: imgup.net)

(source: imgup.net)

The conclusion is as disappointing as the quality of the paper itself. It shows very little improvement. The main thing here is a possible object scoring method for this kind of challenge (and other image-repair challenges):

```
+-------+---------------+----------+
| Image | EBII Original | Improved |
+-------+---------------+----------+
|     1 |       52.9556 |  53.7890 |
|     2 |       53.9098 |  53.8989 |
+-------+---------------+----------+

```

Meh.

### Research to be done

(Specific to EBII)

a) Pre-Processing

Everything comes down to the "Magic Erase" principle that the algorithm should "just work" for everything. My naive solution for this is a color-based amplification (see above), but there are better ways. I'm thinking of recognizing the geometric mean of all traceable texels to auto-adjust the window size and making the stamp size (also my improvement) dependent on texel- *and* whole-image resolution. Research has to be done here.

b) Post-Processing

The original authors already did a great job of debunking all post processing filters that come in mind. Today, I tried something else, inspired by the always uncanny Mona Lisa (thanks undergroundmonorail). If you take *just* the inpainted region and apply a new mask to all strange blocks of color and feed that into a despeckling algorithm, you're left with an almost perfect result. I may explore this some time in the future.

---

\[X\] — Object Removal by Exemplar-Based Inpainting by A. Criminisi, P. Perez, K. Toyama
\[1\] — M. Ashikhmin. Synthesizing natural textures. In Proc. ACM Symp. on Interactive 3D Graphics, pp. 217–226, Research Triangle Park, NC, Mar 2001.
\[5\] — M. Bertalmio, L. Vese, G. Sapiro, and S. Osher. Simultaneous structure and texture image inpainting. to appear, 2002
\[6\] — R. Bornard, E. Lecan, L. Laborelli, and J-H. Chenot. Missing data correction in still images and image sequences. In ACM Multimedia, France, Dec 2002.
\[7\] — T. F. Chan and J. Shen. Non-texture inpainting by curvature-driven diffusions (CDD). J. Visual Comm. Image Rep., 4(12), 2001.
\[8\] — J.S. de Bonet. Multiresolution sampling procedure for analysis and synthesis of texture images. In Proc. ACM Conf. Comp. Graphics (SIGGRAPH), volume 31, pp. 361–368, 1997.
\[9\] — A. Efros and W.T. Freeman. Image quilting for texture synthesis and transfer. In Proc. ACM Conf. Comp. Graphics (SIGGRAPH), pp. 341–346, Eugene Fiume, Aug 2001.
\[10\] — A. Efros and T. Leung. Texture synthesis by non-parametric sampling. In Proc. ICCV, pp. 1033–1038, Kerkyra, Greece, Sep 1999.
\[11\] — W.T. Freeman, E.C. Pasztor, and O.T. Carmichael. Learning low level vision. Int. J. Computer Vision, 40(1):25–47, 2000.
\[12\] — D. Garber. Computational Models for Texture Analysis and Texture Synthesis. PhD thesis, Univ. of Southern California, USA, 1981.
\[13\] — P. Harrison. A non-hierarchical procedure for re-synthesis of complex texture. In Proc. Int. Conf. Central Europe Comp. Graphics, Visua. and Comp. Vision, Plzen, Czech Republic, Feb 2001.
\[14\] — D.J. Heeger and J.R. Bergen. Pyramid-based texture analysis/synthesis. In Proc. ACM Conf. Comp. Graphics (SIGGRAPH), volume 29, pp. 229–233, Los Angeles, CA, 1995.
\[15\] — A. Hertzmann, C. Jacobs, N. Oliver, B. Curless, and D. Salesin. Image analogies. In Proc. ACM Conf. Comp. Graphics (SIGGRAPH), Eugene Fiume, Aug 2001.
\[16\] — H. Igehy and L. Pereira. Image replacement through texture synthesis. In Proc. Int. Conf. Image Processing, pp. III:186–190, 1997.
\[17\] — G. Kanizsa. Organization in Vision. Praeger, New York, 1979.
\[19\] — L. Liang, C. Liu, Y.-Q. Xu, B. Guo, and H.-Y. Shum. Real-time texture synthesis by patch-based sampling. In ACM Transactions on Graphics, 2001.
\[22\] — L.-W. Wey and M. Levoy. Fast texture synthesis using tree-structured vector quantization. In Proc. ACM Conf. Comp. Graphics (SIGGRAPH), 2000.
\[23\] — A. Zalesny, V. Ferrari, G. Caenen, and L. van Gool. Parallel composite texture synthesis. In Texture 2002 workshop - (in conjunction with ECCV02), Copenhagen, Denmark, Jun 2002.
\[24\] — AkurKumar Patel, Gujarat Technological University, Computer Science and Engineering
\[25\] — Improved Robust Algorithm For Exemplar Based Image Inpainting
\[26\] — Wikipedia, Peak-Signal-to-Noise-Ratio
> 147 votes

# Answer
# Matlab

This is a simple interpolation approach. The idea is first mirroring what is on each side of the patch. Then those mirror image pixels are interpolated by how close they are to the corresponding edge:

The tricky part was finding a nice interpolation weights. After some playing around I came up with a rational function that is zero on all edges except the one where we mirrored at. This is then transformed by a third degree polynomial for some smoothing:

This simple approach does surprisingly well on "natural" images, but as soon as you are confronted with sharp edges, the game is over. In the *american gothic* example the spikes of the hay fork line up nicely with the pixel grid, which makes it look quite nice, but it would have been much worse otherwise.

So here the results:

And finally, the code:

```
imgfile= 'filename.png';
maskfile = [imgfile(1:end-4),'_mask.png'];
img = double(imread(imgfile));
mask = rgb2gray(imread(maskfile));
%% read mask
xmin = find(sum(mask,1),1,'first');
xmax = find(sum(mask,1),1,'last');
ymin = find(sum(mask,2),1,'first');
ymax = find(sum(mask,2),1,'last');
%% weight transformation functiosn
third = @(x)-2* x.^3 + 3* x.^2;
f=@(x)third(x);
w=@(x,y)y.*(x-1).*(y-1)./( (x+y).*(x+1-y));

for x=xmin:xmax
    for y=ymin:ymax
        %Left Right Up Down;
        P = [img(y,xmin-(x-xmin)-1,:);img(y,xmax+(xmax-x)+1,:);img(ymin-(y-ymin)-1,x,:);img(ymax+(ymax-y)+1,x,:)];
        % normalize coordinates
        rx = (x-xmin)/(xmax-xmin);
        ry = (y-ymin)/(ymax-ymin);
        % calculate the weights
        W = [w(rx,ry),w(1-rx,ry),w(ry,rx),w(1-ry,rx)]';
        W = f(W);
        W(isnan(W))=1;
        img(y,x,:) = sum(bsxfun(@times,P,W),1)/sum(W);
    end
end
imshow(img/255);
imwrite(img/255,[imgfile(1:end-4),'_out.png']);

```
> 45 votes

# Answer
# Mathematica

This uses Mathematica's `Inpaint` function. Because Mathematica itself does all the heavy lifting, this is a community wiki.

`inPaint` (below) is a simple adaptation of `Inpaint`. For colored paintings/photos, it uses the default, "TextureSynthesis", setting. If it detects that the picture is black and white (because the image data of the picture is the same as the image data of the binary form of the picture), it then binarizes the image and applies the "TotalVariation" patch. The `If` clause either applies `Binarize` or `Identity` to the picture. (The `Identity` function returns its argument unchanged.)

```
inPaint[picture_, mask_] :=
 If[bw = ImageData@Rasterize[Binarize[picture]] == ImageData[picture], Binarize, Identity]@
  Inpaint[picture, mask, Method -> If[bw, "TotalVariation", "TextureSynthesis"]]

```

---

The image and mask are entered as arguments to `inPaint`. `Partition` and `Grid` are merely for formatting purposes.

The outputs have been patched. There was no retouching of the images after `inPaint`.
> 25 votes

# Answer
# Python 2 and PIL

This program blends copies of regions North, South, East, and West to create replacement pixels that use colours, textures, and shading from the local image region.

The example outputs:

The code first finds the bounding box for the patch. Then for each pixel to be generated, it computes the colour of each channel (RGB) based on the weighted sum of the 4 surrounding regions.

```
import sys
from PIL import Image

infile, maskfile, outfile = sys.argv[1:4]
imageobj = Image.open(infile)
maskobj = Image.open(maskfile)
image = imageobj.load()
mask = maskobj.load()

assert imageobj.size == maskobj.size
W, H = imageobj.size
pixels = [(x,y) for x in range(W) for y in range(H)]
whitepart = [xy for xy in pixels if sum(mask[xy]) > 230*3]
xmin = min(x for x,y in whitepart)
xmax = max(x for x,y in whitepart)
ymin = min(y for x,y in whitepart)
ymax = max(y for x,y in whitepart)
xspan = xmax - xmin + 1
yspan = ymax - ymin + 1

def mkcolor(channel):
    value = image[(xmin-dx, y)][channel] * 0.5*(xspan - dx)/xspan
    value += image[(xmax+1 + xspan - dx, y)][channel] * 0.5*dx/xspan
    value += image[(x, ymin-dy)][channel] * 0.5*(yspan - dy)/yspan
    value += image[(x, ymax+1 + yspan - dy)][channel] * 0.5*dy/yspan
    return int(value)

for dx in range(xspan):
    for dy in range(yspan):
        x = xmin + dx
        y = ymin + dy
        image[(x, y)] = (mkcolor(0), mkcolor(1), mkcolor(2))

imageobj.save(outfile)

```
> 20 votes

# Answer
## Python 3, PIL

This program uses the sobel operator, and draws lines onto the image based on that.

The sobel operator finds the angle of each edge, so any edges extruding into the unknown area should continue.

```
from PIL import Image, ImageFilter, ImageDraw
import time
im=Image.open('2.png')
im1=Image.open('2 map.png')
a=list(im.getdata())
b=list(im1.getdata())
size=list(im.size)
'''
def dist(a,b):
    d=0
    for x in range(0,3):
        d+=(a[x]-b[x])**2
    return(d**0.5)
#'''
C=[]
d=[]
y=[]
for x in range(0,len(a)):
    if(b[x][0]==255):
        C.append((0,0,0))
    else:
        y=(a[x][0],a[x][1],a[x][2])
        C.append(y)
im1.putdata(C)
k=(-1,0,1,-2,0,2,-1,0,1)
k1=(-1,-2,-1,0,0,0,1,2,1)
ix=im.filter(ImageFilter.Kernel((3,3),k,1,128))
iy=im.filter(ImageFilter.Kernel((3,3),k1,1,128))
ix1=list(ix.getdata())
iy1=list(iy.getdata())
d=[]
im2=Image.new('RGB',size)
draw=ImageDraw.Draw(im2)
c=list(C)
Length=0
for L in range(100,0,-10):
    for x in range(0,size[0]):
        for y in range(0,size[1]):
            n=x+(size[0]*y)
            if(c[n]!=(0,0,0)):
                w=(((iy1[n][0]+iy1[n][1]+iy1[n][2])//3)-128)
                z=(((ix1[n][0]+ix1[n][1]+ix1[n][2])//3)-128)
                Length=(w**2+z**2)**0.5
                if Length==0:
                    w+=1
                    z+=1
                Length=(w**2+z**2)**0.5
                w/=(Length/L)
                z/=(Length/L)
                w=int(w)
                z=int(z)
                draw.line(((x,y,w+x,z+y)),c[n])

d=list(im2.getdata())
S=[]
d1=[]
A=d[0]
for x in range(0,size[0]):
    for y in range(0,size[1]):
        n=y+(size[1]*x)
        nx=y+(size[1]*x)-1
        ny=y+(size[1]*x)-size[0]
        if d[n]==(0,0,0):
            S=[0,0,0]
            for z in range(0,3):
                S[z]=(d[nx][z]+d[ny][z])//2
            #print(S)
            d1.append(tuple(S))
        else:
            d1.append(tuple(d[n]))
d=list(d1)
im2.putdata(d)
#im2=im2.filter(ImageFilter.GaussianBlur(radius=0.5))
d=im2.getdata()
f=[]
#'''
for v in range(0,len(a)):
    if(b[v][0]*b[v][1]*b[v][2]!=0):
        f.append(d[v])
    else:
        f.append(C[v])
#'''
im1.putdata(f)
im1.save('pic.png')

```

Meanwhile, here are the sample images.

Mona Lisa Mona Lisa Ḿ͠oǹ̰͎̣a ̾̇Lisa Ḿ͠o̢̎̓̀ǹ̰͎̣aͧ̈ͤ ̣̖̠̮̘̹̠̾̇ͣLisa Ḿ̳̜͇͓͠o̢̎̓̀ǹ̰͎̣͙a̤̩̖̞̝ͧ̈ͤͤ ̣̖̠̮̘̹̠̾̇ͣL͉̻̭͌i̛̥͕̱͋͌ş̠͔̏̋̀ạ̫͕͎ͨͮͪ̐͡ͅ

The area in the above image is as smooth as a cactus

It is not very good with constant color.
> 14 votes

# Answer
# Python 2

Simple python script that creates patch using values from pixels just outside gap. It takes color values from end of pixels' row and column and calculates weighted average using distance from those pixels.

Output is not so pretty, but it's *art*.

And then, code:

```
IMGN = "6"

IMGFILE = "images/img%s.png" % (IMGN,)
MASKFILE = "images/img%s_mask.png" % (IMGN,)

BLUR = 5

def getp(img,pos):
    return img.get_at(pos)[:3]
def setp(img,pos,color):
    img.set_at(pos, map(int, color))

def pixelavg(L):
    return map(int, [sum([i[q] for i in L])/float(len(L)) for q in [0,1,2]])
def pixelavg_weighted(L, WL):   # note: "inverse" weights. More weight => less weight
    # colors [sum, max]
    color_data = [[0, 0], [0, 0], [0, 0]]
    for color,weight in zip(L, WL):
        for i in [0, 1, 2]: # r,g,b
            color_data[i][0] += inv_w_approx(weight) * color[i]
            color_data[i][1] += inv_w_approx(weight) * 255
    return [255*(float(s)/m) for s,m in color_data]
def inv_w_approx(x):
    return (1.0/(x+1e-10))

import pygame
image = pygame.image.load(IMGFILE)
mask = pygame.image.load(MASKFILE)

size = image.get_size()
assert(size == mask.get_size())

# get square from mask
min_pos = None
max_pos = [0, 0]
for x in range(size[0]):
    for y in range(size[1]):
        if getp(mask, [x, y]) == (255, 255, 255):
            if min_pos == None:
                min_pos = [x, y]
            max_pos = [x, y]
if not min_pos:
    exit("Error: no mask found.")
# patch area info
patch_position = min_pos[:]
patch_size = [max_pos[0]-min_pos[0], max_pos[1]-min_pos[1]]

# remove pixels from orginal image (fill black)
for dx in range(patch_size[0]):
    for dy in range(patch_size[1]):
        setp(image, [patch_position[0]+dx, patch_position[1]+dy], [0, 0, 0])

# create patch
patch = pygame.Surface(patch_size)

# take pixels around the patch
top = [getp(image, [patch_position[0]+dx, patch_position[1]-1]) for dx in range(patch_size[0])]
bottom = [getp(image, [patch_position[0]+dx, patch_position[1]+patch_size[1]+1]) for dx in range(patch_size[0])]
left = [getp(image, [patch_position[0]-1, patch_position[1]+dy]) for dy in range(patch_size[1])]
right = [getp(image, [patch_position[0]+patch_size[0]+1, patch_position[1]+dy]) for dy in range(patch_size[1])]

cpixels = top+left+right+bottom

# set area to average color around it
average = [sum([q[i] for q in cpixels])/float(len(cpixels)) for i in [0, 1, 2]]

for dx in range(patch_size[0]):
    for dy in range(patch_size[1]):
        setp(patch, [dx, dy], average)

# create new pixels
for dx in range(patch_size[0]):
    for dy in range(patch_size[1]):
        setp(patch, [dx, dy], pixelavg_weighted([top[dx], bottom[dx], left[dy], right[dy]], [dy, patch_size[1]-dy, dx, patch_size[0]-dx]))

# apply patch
for dx in range(patch_size[0]):
    for dy in range(patch_size[1]):
        setp(image, [patch_position[0]+dx, patch_position[1]+dy], getp(patch, [dx, dy]))

# blur patch?
for r in range(BLUR):
    for dx in range(patch_size[0]):
        for dy in range(patch_size[1]):
            around = []
            for ddx in [-1,0,1]:
                for ddy in [-1,0,1]:
                    around.append(getp(image, [patch_position[0]+dx+ddx, patch_position[1]+dy+ddy]))
            setp(patch, [dx, dy], pixelavg(around))

    # apply blurred patch
    for dx in range(patch_size[0]):
        for dy in range(patch_size[1]):
            setp(image, [patch_position[0]+dx, patch_position[1]+dy], getp(patch, [dx, dy]))

# save result
pygame.image.save(image, "result.png")

```
> 8 votes

# Answer
# Mathematica

```
Inpaint

```

It just so happens that *Mathematica* has a built-in function that performs exactly this task, and I mean **exactly**:

> `Inpaint[image, region]`
>
> * retouches parts of `image` that correspond to nonzero elements in `region`.

By default it uses a "best-fit texture synthesis method using random sampling" which produces good results on the paintings, but poor results for the maze and checkerboard:

Playing around with the settings didn't net me an increase in quality across all of the images, so I just used the defaults (to save bytes—this is `codegolf.se` after all!).
> 7 votes

# Answer
# Python3

This answer implements the idea in the paper "Deep Image Prior" by Ulyanov et al. (CVPR 2018) In this paper they explored the idea that the way well performing neural nets for image processing are designed closely reflects our idea of what a natural image should look like (the "prior" distribution).

They proposed a method that can be used for inpainting as well as noise and artifact removal that just uses the given image with no training on any other data. The actual concept is quite simple: The net is trained to output the desired image (for some fixed random noise as input) by penalizing only the erros outside some given mask. If you want to remove noise, you just don't need to mask anything, but just stop early in the training.

For inpainting you mask the part you want to inpaint and train until convergence. It is certainly not state-of-the-art, but I still wanted to post try it and post it here due to the simplicity of the idea and the still remarkable performance. In my experiments the inpainting of larger patches didn't turn out that well but for smaller segments the results can be a lot more convincing.

I implemented this using the popular U-Net architecture from jaxony on github. The code for training and processing the images can be found below.

### Training

This is a visualization of the training process. Every frame is the state ofter a certain number of iterations:

### Examples

### Code

Note that on a cpu this can take hours to run for just a single image, while a good cuda enabled gpu might take a lot less time.

```
import torch
import numpy as np
unet = __import__('unet-pytorch')
import PIL.ImageOps
#specify device (cpu/cuda)
device = "cpu"
#specify file and size
file = 'mona'
size = 512 #pad to this size (no smaller than original image), must be divisible by 2^5
img_pil = PIL.Image.open(file +'.png').convert('RGB')
mask_pil = PIL.Image.open(file +'-mask.png').convert('RGB')

net = unet.UNet(num_classes=3, in_channels=32, depth=6, start_filts=64).to(device)
h,w = img_pil.size
pad = (0, 0, size - h, size - w)
img = PIL.ImageOps.expand(img_pil, border=pad)
img = torch.Tensor(np.array(img).transpose([2, 0, 1])[None, :, :, :].astype(np.double)).to(device)
mask = PIL.ImageOps.expand(mask_pil, border=pad)
mask = torch.Tensor((np.array(mask)==0).transpose([2, 0, 1])[None, 0:3, :, :].astype(np.double)).to(device)
mean = img.mean()
std = img.std()
img = (img - mean)/std
optimizer = torch.optim.Adam(net.parameters(), lr=0.0001)
criterion = torch.nn.MSELoss()
input = torch.rand((1, 32, size, size)).to(device)
for it in range(5000):
    if it == 1000:
        optimizer.param_groups[0]['lr'] = 0.00003
    out = net(input)
    loss = criterion(out * mask, img * mask)
    optimizer.zero_grad()
    loss.backward()
    optimizer.step()
out = out.detach().cpu().numpy()[0].transpose([1,2,0])*std.item() + mean.item()
out = np.clip(out, 0, 255).astype(np.uint8)[0:w, 0:h, :]
mask_np = (np.array(mask_pil) > 0).astype(np.uint8)
img_np = np.array(img_pil)
inpaint = (img_np * (1-mask_np) + mask_np * out).astype(np.uint8)
PIL.Image.fromarray(inpaint).save('./{}_inpainted.png'.format(file))

```
> 5 votes

# Answer
# Python with OpenCV

OpenCV has a function called inpaint. There are two types of inpainting used, I will use the Fast Marching Method. According to the documentation, the algorithm works like this:

> Consider a region in the image to be inpainted. Algorithm starts from the boundary of this region and goes inside the region gradually filling everything in the boundary first. It takes a small neighbourhood around the pixel on the neigbourhood to be inpainted. This pixel is replaced by normalized weighted sum of all the known pixels in the neigbourhood. Selection of the weights is an important matter. More weightage is given to those pixels lying near to the point, near to the normal of the boundary and those lying on the boundary contours. Once a pixel is inpainted, it moves to next nearest pixel using Fast Marching Method. FMM ensures those pixels near the known pixels are inpainted first, so that it just works like a manual heuristic operation.

Here is the code\*:

```
import numpy as np
import cv2
from matplotlib import pyplot as plt
img = cv2.imread('gothic.jpg')
b,g,r = cv2.split(img)
img2 = cv2.merge([r,g,b])
mask = cv2.imread('mask.jpg',0)
dst = cv2.inpaint(img2,mask,3,cv2.INPAINT_TELEA)
(h, w) = dst.shape[:2]
center = (w / 2, h / 2)
# rotate the image by 180 degrees
M = cv2.getRotationMatrix2D(center, 180, 1.0)
rotated = cv2.warpAffine(dst, M, (w, h))
plt.imshow(rotated)

```

Note how I convert the BGR to RGB for plotting reasons. Also, I rotate it. Here are the results:

Mona Lisa returns!

As you can see, it i not the best with the two color ones.
> 4 votes

# Answer
# Java

A color averaging approach. Can probably be improved.

```
import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.Scanner;

import javax.imageio.ImageIO;

public class ImagePatcher{
    public static void main(String[]args) throws Exception{
        Scanner in=new Scanner(System.in);
        int white=Color.WHITE.getRGB();
        int black=Color.BLACK.getRGB();
        BufferedImage image=ImageIO.read(new File(in.nextLine())),mask=ImageIO.read(new File(in.nextLine()));
        assert(image.getWidth()==mask.getWidth()&&image.getHeight()==mask.getHeight());
        boolean bool=true;
        while(bool){
            bool=false;
        for(int x=0;x<image.getWidth();x+=2){
            for(int y=0;y<image.getHeight();y+=2){
                if(mask.getRGB(x,y)!=white)continue;
                int r=0,g=0,b=0,n=0;
                for(int dx=-1;dx<=1;dx++){
                    if(x+dx<0)continue;
                    if(x+dx>=image.getWidth())continue;
                    for(int dy=-1;dy<=1;dy++){
                        if(y+dy<0)continue;
                        if(y+dy>=image.getHeight())continue;
                        if(mask.getRGB(x+dx,y+dy)==white)continue;
                        Color c=new Color(image.getRGB(x+dx,y+dy));
                        r+=c.getRed();
                        g+=c.getGreen();
                        b+=c.getBlue();
                        n++;
                    }
                }
                if(n==0){bool=true;continue;}
                Color c=n>0?new Color(r/n,g/n,b/n):new Color(100,100,100);
                image.setRGB(x,y,c.getRGB());
                mask.setRGB(x, y, black);
            }
        }
        for(int x=0;x<image.getWidth();x+=2){
            for(int y=1;y<image.getHeight();y+=2){
                if(mask.getRGB(x,y)!=white)continue;
                int r=0,g=0,b=0,n=0;
                for(int dx=-1;dx<=1;dx++){
                    if(x+dx<0)continue;
                    if(x+dx>=image.getWidth())continue;
                    for(int dy=-1;dy<=1;dy++){
                        if(y+dy<0)continue;
                        if(y+dy>=image.getHeight())continue;
                        if(mask.getRGB(x+dx,y+dy)==white)continue;
                        Color c=new Color(image.getRGB(x+dx,y+dy));
                        r+=c.getRed();
                        g+=c.getGreen();
                        b+=c.getBlue();
                        n++;
                    }
                }
                if(n==0){bool=true;continue;}
                Color c=n>0?new Color(r/n,g/n,b/n):new Color(100,100,100);
                image.setRGB(x,y,c.getRGB());
                mask.setRGB(x, y, black);
            }
        }
        for(int x=1;x<image.getWidth();x+=2){
            for(int y=0;y<image.getHeight();y+=2){
                if(mask.getRGB(x,y)!=white)continue;
                int r=0,g=0,b=0,n=0;
                for(int dx=-1;dx<=1;dx++){
                    if(x+dx<0)continue;
                    if(x+dx>=image.getWidth())continue;
                    for(int dy=-1;dy<=1;dy++){
                        if(y+dy<0)continue;
                        if(y+dy>=image.getHeight())continue;
                        if(mask.getRGB(x+dx,y+dy)==white)continue;
                        Color c=new Color(image.getRGB(x+dx,y+dy));
                        r+=c.getRed();
                        g+=c.getGreen();
                        b+=c.getBlue();
                        n++;
                    }
                }
                if(n==0){bool=true;continue;}
                Color c=n>0?new Color(r/n,g/n,b/n):new Color(100,100,100);
                image.setRGB(x,y,c.getRGB());
                mask.setRGB(x, y, black);
            }
        }
        for(int x=1;x<image.getWidth();x+=2){
            for(int y=1;y<image.getHeight();y+=2){
                if(mask.getRGB(x,y)!=white)continue;
                int r=0,g=0,b=0,n=0;
                for(int dx=-1;dx<=1;dx++){
                    if(x+dx<0)continue;
                    if(x+dx>=image.getWidth())continue;
                    for(int dy=-1;dy<=1;dy++){
                        if(y+dy<0)continue;
                        if(y+dy>=image.getHeight())continue;
                        if(mask.getRGB(x+dx,y+dy)==white)continue;
                        Color c=new Color(image.getRGB(x+dx,y+dy));
                        r+=c.getRed();
                        g+=c.getGreen();
                        b+=c.getBlue();
                        n++;
                    }
                }
                if(n==0){bool=true;continue;}
                Color c=n>0?new Color(r/n,g/n,b/n):new Color(100,100,100);
                image.setRGB(x,y,c.getRGB());
                mask.setRGB(x, y, black);
            }
        }
        };
        ImageIO.write(image, "png", new File("output.png"));
    }
}

```

Results:
> 3 votes

---
Tags: popularity-contest, graphical-output, image-processing
---


title: Is this a submatrix?

text:
# Question
Title: Is this a submatrix?
*This is the 2-dimensional generalisation of this challenge.*

For our purposes, one matrix (or 2D array) *A* is considered a **submatrix** of another matrix *B*, if *A* can be obtained by completely removing a number of rows and columns from *B*. *(Note: some sources have different/more restrictive definitions.)*

Here's an example:

```
A = [1 4      B = [1 2 3 4 5 6
     2 1]          6 5 4 3 2 1
                   2 1 2 1 2 1
                   9 1 8 2 7 6]

```

We can delete columns 2, 3, 5, 6 and rows 2, 4 from *B* to obtain *A*:

```
B = [1 2 3 4 5 6         [1 _ _ 4 _ _         [1 4  = A
     6 5 4 3 2 1   -->    _ _ _ _ _ _   -->    2 1]
     2 1 2 1 2 1          2 _ _ 1 _ _
     9 1 8 2 7 6]         _ _ _ _ _ _]

```

Note that *A* is still a submatrix of *B* if all rows or all columns of *B* are retained (or in fact if *A = B*).

## The Challenge

You guessed it. Given two non-empty integer matrices *A* and *B*, determine if *A* is a submatrix of *B*.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be in any convenient format. The matrices can be given as nested lists, strings using two different separators, flat lists along with the dimensions of the matrix, etc, as long as the input is not pre-processed. You may choose to take *B* first and *A* second, as long as your choice is consistent. You may assume that the elements of the matrices are positive and less then 256.

Output should be truthy if *A* is a submatrix of *B* and falsy otherwise. The specific output value does not have to be consistent.

Standard rules apply.

## Test Cases

Each test case is on a separate line, `A, B`.

Truthy cases:

```
[[1]], [[1]]
[[149, 221]], [[177, 149, 44, 221]]
[[1, 1, 2], [1, 2, 2]], [[1, 1, 1, 2, 2, 2], [3, 1, 3, 2, 3, 2], [1, 1, 2, 2, 2, 2]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [4, 7, 6], [7, 8, 9], [1, 2, 3], [4, 5, 6], [7, 8, 9]]
[[228, 66], [58, 228]], [[228, 66], [58, 228]]
[[1, 2], [2, 1]], [[1, 2, 2], [2, 1, 2], [2, 2, 1]]
[[136, 196], [252, 136]], [[136, 252, 210, 196, 79, 222], [222, 79, 196, 210, 252, 136], [252, 136, 252, 136, 252, 136], [180, 136, 56, 252, 158, 222]]

```

Falsy cases:

```
[[1]], [[2]]
[[224, 15]], [[144, 15, 12, 224]]
[[41], [150]], [[20, 41, 197, 150]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [7, 8, 9], [4, 5, 6]]
[[1, 2, 2], [2, 1, 2], [2, 2, 1]], [[1, 2], [2, 1]]
[[1, 2, 2], [2, 1, 2]], [[1, 2], [2, 1], [2, 2]]
[[1, 2], [3, 4]], [[5, 3, 4, 5], [2, 5, 5, 1], [4, 5, 5, 3], [5, 1, 2, 5]]
[[158, 112], [211, 211]], [[158, 211, 189, 112, 73, 8], [8, 73, 112, 189, 211, 158], [211, 158, 211, 158, 211, 158], [21, 158, 199, 211, 212, 8]]

```

# Answer
# Pyth, 10 bytes

```
}CQsyMCMyE

```

Test suite

This is fairly straightforward. First, we consider B as a list of rows, and take all subsets using `yE`. Then, each of those matrices is transposed with `CM`, and all subsets are taken of their rows, with `yM`. Concatenating these sublists with `s` gives all possible transposed submatrices. So we transpose A with `CQ`, and check if it is present with `}`.
> 7 votes

# Answer
# Dyalog APL, ~~53~~ 43 bytes

```
(⊂A)∊⊃∘.{∧/∊2</¨⍺⍵:B[⍺;⍵]⋄⍬}/⍳¨(⍴A←⎕)/¨⍴B←⎕

```

`B←⎕`, `A←⎕`prompt for `B` and `A`
`⍴B`, `⍴A` dimensions of `B` and `A`
replicate each, e.g. `2 3/¨4 5``(4 4) (5 5 5)`
`⍳¨` all indices in each of the coordinate systems with those dimensions
`∘.{``}/` table of possible submatrices, where each submatrix is defined as the result of the anonymous function `{``}` applied between a pair of coordinates  and
`∧/∊2</¨:` if both  and  are (`∧/∊`) both (`¨`) increasing (`2</`), then...
`B[⍺;⍵]` return submatrix of `B` created from the intersections of rows  and columns
`⋄⍬` else, return an empty vector (something that A is not identical to)
`(⊂A)∊⊃` check if the whole of `A` (`⊂A`) is a member of  any of the submatrices ()

---

### Old 53-byte solution:

```
{(⊂⍺)∊v∘.⌿h/¨⊂⍵⊣v h←(⍴⍺){↓⍉⍺{⍵/⍨⍺=+⌿⍵}(⍵/2)⊤⍳⍵*2}¨⍴⍵}

```

`{``}` an anonymous inline function, where  is left argument and  is right argument
shape, e.g. 2 3 for a 2-by-3 matrix
`(⍴⍺){``}¨⍴⍵` for each pair of corresponding dimension-lengths, apply this anonymous function
`⍳⍵*2` indices of the square of, i.e. 2 → 1 2 3 4
`(⍵/2)⊤` convert to binary (number of bits is dimension-length squared)
`{⍵/⍨⍺=+⌿⍵}` of the binary table, select the columns (`⍵/⍨`) where the number of 1s (`+⌿⍵`) is equal to the the length of that dimension in the potential submatrix (`⍺=`)
`↓⍉` make table into list of columns
`v h←` store as `v`(ertical masks) and `h`(horizontal masks)
then
`h/¨⊂⍵` apply each horizontal mask to the right argument matrix
`v∘.⌿` apply each vertical mask each one of the horizontally masked versions of the large matrix
`(⊂⍺)∊` check if the left argument matrix is member thereof
> 6 votes

# Answer
## Jelly, ~~12~~ 10 bytes

*Thanks @Dennis for -2 bytes*

```
ZŒP
ÇÇ€;/i

```

Nearly the same algorithm as @isaacg, except we transpose the matrix before taking subsets.

```
ZŒP      Helper link. Input: z
Z          Transpose z
ZŒP        All subsets of columns of z.

ÇÇ€;/i   Main link. Input: B, A. B is a list of rows.
Ç          Call the helper link on B. This is the subsequences of columns of A.
 Ç€        Call the helper link on each column-subsequence.
           Now we have a list of lists of submatrices of B.
   ;/      Flatten that once. The list of submatrices of B.
     i     then get the 1-based index of A in that list.
           If A is not in the list, returns 0.

```

Try it here.
> 4 votes

# Answer
# Brachylog, 4 bytes

```
⊇z⊇z

```

Try it online!

Takes matrix B through the input variable and matrix A through the output variable, and outputs through success or failure. This is pretty much just the Pyth solution, except the input is more implicit and there's no explicit generation or membership checking for the powersets.

```
        B
⊇       has a sublist
 z      which transposed
  ⊇     has a sublist
   z    which transposed
        is A.

```
> 4 votes

# Answer
# Mathematica, 40 ~~65~~ bytes

```
!FreeQ[s[# ]&/@(s=Subsets)@#2,# ]&

```

Explanation: See one of the other answers -- it looks like they all did the same thing.
> 3 votes

# Answer
## Haskell, 66 bytes

```
import Data.List
t=transpose
s=subsequences
(.((s.t=<<).s)).elem.t

```

Usage example: `( (.((s.t=<<).s)).elem.t ) [[149, 221]] [[177, 149, 44, 221]]` -\> `True`.

A non-pointfree version is

```
f a b = elem(transpose a) $ (subsequences.transpose=<<) $ subsequences b

                      subsequences b     -- make all subsequences of b, i.e. all
                                         -- all combinations of rows removed
     (subsequences.transpose=<<)         -- transpose each such sub-matrix and
                                         -- remove rows again. Concatenate into a
                                         -- single list
elem(transpose a)                        -- check if the transposition of a is in
                                         -- the list

```
> 2 votes

# Answer
# Python + NumPy, ~~176~~ 173 bytes

```
from itertools import*
from numpy import*
def f(A,B):
 r,c=A.shape
 R,C=B.shape
 S=combinations
 print any([all(B[ix_(i,j)]==A)for i in S(range(R),r)for j in S(range(C),c)])

```
> 0 votes

---
Tags: code-golf, array, decision-problem, subsequence, matrix
---


title: Paradox of time travel

text:
# Question
Title: Paradox of time travel
A man has two devices.

* **A time machine** \- He can control this machine by thinking. It allows him to travel from any point in time to another point in time in the past or future (or even the present point in time) in no time at all. Note that if he travels to the past from B to A, then all normal events (time machines, alternators excluded) from A to B must repeat in the exact same way. Then from point B, he is taken back to point A. Thus, a single time travel creates an infinite loop.
* **Alternator** \- Realising this problem, he creates another machine. He notices that, even though all physical events get repeated in a loop, his thoughts may be different. Hence this machine was designed to be controllable by thought as well. The machine can be used at any time to provide an alternate future (but not past) with respect to the time he used it.

**Example**

I'll explain all the details using a lengthy example.

```
1000 T+250 250 T+0 500 T-200 100 T-50 125 A 225 T-400 500 A 100 T-200 150 T-25 100 T+100 50 A 25

```
* 1000 years pass. It is year 1000 now.
* He travels from 1000 to 1250.
* 250 years pass. It is year 1500 now.
* He travels from 1500 to 1500. This has no effect (and can be ignored).
* 500 years pass. It is now year 2000
* He travels from 2000 to 1800.
* 100 years pass. It is year 1900 now.
* He travels from 1900 to 1850.
* 125 years pass: However, this time, as he is in a loop, things are different. 50 years pass from 1850 to 1900. He loops back to 1850. Another 50 years pass from 1850 to 1900. He loops back again. 25 years pass and it is 1875, thus completing 125 years.
* He uses the alternator. Now there exists an alternate future to the year 1875, which he is now in. The past has not changed.
* 225 years pass. It is now year 2100.
* He travels from 2100 to 1700.
* 500 years pass: 175 years from 1700 to 1875 pass normally. No he encounters the alternator again, which means that now a *3rd* future has been created post-1875. 325 years pass normally, making it year 2200.
* Using an alternator now has no effect (and can be ignored) since there exists only one future to 2200 which has not yet been defined.
* 100 years pass. It is now 2300.
* He travels from 2300 to 2100.
* 150 years pass: 100 years from 2100 to 2200 pass normally. A second future gets created from 2200. 50 years pass and it is now year 2250.
* He is supposed to go from 2250 to 2225. However, there now exist two 2225s in two different timelines. Hence this leads to a paradox, since we cannot determine which point in time he will reach. (We will not assume that he goes to the more recent timeline) Hence this terminates our simulation.
* Anything further `100 T+100 50 A 25` is completely ignored since a paradox has occured and our simulation has stopped running.

*Hint:* If you are struggling to understand the example, imagine time to be like a path you are digging in the earth. If you are time travelling, you are creating a teleporter. If you are using the alternator, you are digging a new path into the wall of an existing path.

**Paradox**

Assume A, B and C are three points in time (one after another). A paradox is said to have occurred iff:

* you are at a point C, there exists an alternator at a point B, there exists more than one future to point B (and you are in one of them), and you attempt to access any point between B and C via time travel.
* you are at a point A, there exists an alternator at a point B, there exists more than one future to point B, and you try to access a point C (after B) via time travel.

**Input**

A series of events, similar to the example. (Format is flexible.)

**Output**

A truthy/falsey value, indicating whether a paradox has occured.

**Challenge**

Shortest code (in bytes) wins.

# Answer
> 4 votes
# Ruby, ~~510~~ 460 bytes

```
p=[0];w=[n=x=0]
i=gets.split.map{|s|
if x!=1
if s[0]=="A"
w<<n
else
if s[0..1]=="T+"
t=n
q=s[2..-1].to_i
if w[-1]==t||(w[-1]>t&&w[-1]<n+q)
w<<w[-1]
n+=q
else
n+=(t<p[-1]&&n+q>p[-1])?q%(p[-1]-n):q
end
elsif s[0..1]=="T-"
t=n
p<<n
n-=s[2..-1].to_i
x=(x==0&&w[-1]>0&&t>w[-1]&&n>w[-1])?1:0
else
t=n
q=s.to_i
if w[-1]==t||(w[-1]>t&&w[-1]<n+q)
w<<w[-1]
n+=q
else
n+=(t<p[-1]&&n+q>p[-1])?q%(p[-1]-n):q
end
end
end
else
break
end}
p x

```

**Input**

As per example

**Output**

0 = No Paradox, 1 = Paradox

**Sample**

The sample input provided: `1000 T+250 250 T+0 500 T-200 100 T-50 125 A 225 T-400 500 A 100 T-200 150 T-25 100 T+100 50 A 25` returns `1`, indicating a paradox occurred.

**Notes**

This is not only the first exercise I attempt, but it is also the first Ruby program I have written. Hence, it could probably be even shorter.

**Brief Explanation**

```
p: Infinite loops
w: Alternate timelines
n: Now (regardless of timeline)
x: Paradox

```

Infinite loops will only occur while traveling forward in time. I am happy for any feedback - especially if it is pointing out a better way to solve this.

# Answer
> 3 votes
# Java 10, ~~498~~ ~~485~~ 478 bytes

```
import java.util.*;s->{var a=new Stack<Long>();var m=new TreeMap<Long,Long>();long p=0,c=0,t,v,k;o:for(var S:s.split(" "))if((t=S.charAt(0))>65){var b=S.charAt(1)>44;v=new Long(S.substring(2));for(var A:a)p=A>c+(b?-v:v)|m.size()<1?p:1;if(v>0)m.put(c,b?c-v:c+v);c+=b?-v:v;}else if(t>64){a.add(c);m.clear();}else{t=new Long(S);e:for(var e:m.entrySet())if((k=e.getKey())>=c){for(v=c;v<=c+t;)if(a.contains(v++))break e;c=(v=e.getValue())+(c+t-v)%(k-v);continue o;}c+=t;}return p>0;}

```

Input is (for now) in the same format as in the challenge description.

-13 bytes thanks to *@BenjaminUrquhart*.
-7 bytes thanks to *@ceilingcat*.

Try it online or try it online with added debug-lines.

**Explanation:**

```
import java.util.*;            // Required import for the List and TreeMap
s->{                           // Method with String parameter and boolean return-type
  var a=new Stack<Long>();     //  Create a List for the alternators
  var m=new TreeMap<Long,Long>();
                               //  Create a sorted Map for the time-travels
  long p=0,                    //  Paradox-flag, initially 0
       c=0,                    //  Current year, initially 0
       t,v,k;                  //  Temp-values, uninitialized
  o:for(var S:s.split(" "))    //  Loop over the input substrings split by space:
    if((t=S.charAt(0))>65){    //   If the first character is a 'T':
      var b=S.charAt(1)>44;    //    Check if the second character is a '-'
      v=new Long(S.substring(2));
                               //    Convert the String-value to a number
      for(long A:a)            //    Loop over the alternators
        p=A>                   //     If an alternator is larger than:
            c+                 //      The current year, plus
              (b?              //      If we travel backwards in time:
                 -v            //       Subtract the value
                :              //      Else (we travel forward in time):
                 v)            //       Add the value
          |m.size()<1?         //     Or if no previous time-travels occurred:
           p                   //      Leave the paradox-flag the same
          :                    //     Else:
           1;                  //      Set the paradox-flag to 1
      if(v>0)                  //     If the value is not 0 (edge-case for "T+0")
        m.put(c,b?c-v:c+v);    //      Add the from-to time-travel to the Map
      c+=b?-v:v;}              //     Increase/decrease the year accordingly
    else if(t>64){             //   Else-if the character is an 'A':
      a.add(c);                //    Add the current year to the alternators-list
      m.clear();}              //    And empty the time-travel Map
    else{                      //   Else (it's a number)
      t=new Long(S);           //    Convert the String to a number
      e:for(var e:m.entrySet())//    Loop over the time-travels:
        if((k=e.getKey())      //     If the time-travel starting point is
                         >=c){ //     larger than or equal to the current year
          for(v=c;v<=c+t;)     //      Loop from the current year to the year+number:
            if(a.contains(v++))//       If the alternator-list contains any of these years
              break e;         //        Stop the time-travel loop
          c=                   //      Set the current year to:
             (v=e.getValue())  //       The time-travel destination
             +                 //       Plus:
              (c+t             //        The current year plus the number
                  -v)          //        minus the time-travel destination
                     %(k-v);   //        Modulo the time-travel from-to distance
          continue o;}         //      And then continue the outer input-loop
      c+=t;}                   //    Increase the current year by the number
  return p>0;}                 //  Return whether the paradox-flag is 1

```

# Answer
> 3 votes
# 05AB1E, ~~93~~ ~~92~~ ~~86~~ 82 bytes

```
ðU0V#vyAQiYˆðUëy.ïiYy+DX˜såàiXD€нY@Ïн©θ-®¥OÄ%®θY-YOVëVëYy¦+©¯@àXðÊ˜à*i1q}XY®Ÿª{U®V

```

Input is in the same format as in the challenge description, except that alternator `A` is `abcdefghijklmnopqrstuvwxyz` instead to save a byte.
Outputs `1` if a paradox occurred, or the input itself if not (only `1` is truthy in 05AB1E, everything else is falsey).

Loosely based on my Java 10 answer.

Try it online.

Or try it online with added debug-lines (*TODO: Create proper test suite with all test cases at once..*):
\- Test case with backward time-travel paradox: Try it online.
\- Test case with forward time-travel paradox: Try it online.
\- Test case without time-travel paradox: Try it online.

**Explanation:**

```
ðU                         # Set variable `X` (time-travels) to a space character " "
0V                         # Set variable `Y` (current year) to 0
#                          # Split the (implicit) input by spaces
 v                         # And loop over each event `y`:
  yAQi                     #  If the current event `y` is an alternator ("abcdefghijklmnopqrstuvwxyz"):
      Yˆ                   #   Add the current year `Y` to alternators-list `GB`
      ðU                   #   And reset variable `X` to " "
  ëy.ïi                    #  Else-if the current event `y` is an integer:
       Yy+                 #   Calculate the current year `Y` plus the integer `y`
          D                #   Duplicate `Y+y`
           X˜såài          #   If this `Y+y` is within any of the time-travel ranges:
                 X €н      #    Get the starting positions of each time-travel
                     Y@    #    Check for each starting position if the current year `Y` is >= it
                  D    Ï   #    And only leave the time-travel ranges for which this is truthy
                        н  #    Then pop and push the first one
                         © #    Store this time-travel range in variable `r` (without popping)
                 θ         #    Pop and only leave the time-travel destination
                  -        #    Subtract it from the `Y+y` we duplicated
                       %   #    And modulo it with:
                   ®¥OÄ    #     The absolute distance of the time-travel `r`
                 ®θ        #    Then push the time-travel destination again
                   Y-      #    And subtract the current year `Y`
                 YO        #    Then sum these two and the current year `Y` together
                   V       #    And pop and store it as new year `Y`
       ë                   #   Else (`Y+y` is not within any time-travel ranges)
        V                  #    Simply pop and store the duplicated `Y+y` as new year `Y`
  ë                        #  Else (the current event `y` is a time-travel)
    y¦                     #   Remove the leading "T"
   Y  +                    #   And add the value to the current year `Y`
       ©                   #   Store this value in variable `r`
        ¯@à                #   Check if any alternator in list `GB` is >= this value
           XðÊ˜à           #   Check if there are any time-travels
                *i  }      #   And if both are truhy:
                  1        #    Push a 1
                   q       #    Stop the program
                           #    (after which the top of the stack is output implicitly)
    Y®Ÿ                    #   Create a list in the range [current year `Y`, new year `r`]
   X   ª                   #   Append it to the time-travels `X`
        {                  #   And then sort these time-travels
         U                 #   After which we pop and store it as updated `X`
   ®V                      #   And then set `Y` to the new year `r`
                           # (if we haven't reached `q`, the (implicit) input is output instead)

```

---
Tags: code-golf
---


title: Break some standards!

text:
# Question
Title: Break some standards!
Everyone knows the phrase "Rules are made to be broken!", so here is your task:

Write some code in any language that breaks a standard. This can be anything, from putting 240 volts down a USB cable, to pinging your router (**NOT** somebody else's website!) with a 10mb packet! (Don't get any ideas, both of these will probably cause all sorts of doom!)

The most upvoted answer after 10 days (i.e the most serious violation) will win!

Rules:

1. The code must be explained.
2. The standard that you are breaking must be linked to, and you must explain what you are doing (implies 1) to break it. Otherwise answers will not be accepted.
3. Answers that just crash the interpreter, or make it stop working will not be accepted. I would like some creative answers, not just pasting something like  into IDLE (which crashes it)
4. Exploiting bugs are not allowed, unless they break a standard. Otherwise answers will not be accepted

Begin, and have fun!

# Answer
## Python

```
print 'Hello World'

```

---

Explanation:

The standard of the Programming Puzzles & Code Golf Stack Exchange is to

> Read the question carefully. What, specifically, is the question asking for? Make sure your answer provides that

This code is not answering the question, so it breaks the standard.
> 68 votes

# Answer
**C**
Here's a factorial program that compiles and runs succcessfully (with gcc4.6.3 on Ubuntu 12.04), but invokes as much undefined behaviour according to the C standard as I could cram in. Most are inspired from here. A lot of the remaining legal code is just bad.

```
int read(char** src, int into){
  int _r;                             //leading underscores reserved, and
  if (!--into) sscanf(*src,"%d",&into); //_r uninitalized
  *(*(--src)+into)=_r>>360;            //shifting more bits than we have
  while (into-->0) (*src)[into]='.'; //modifying const char argv
  printf(*src); // no return statement
}

main(int argc, const char** const argv){
  union  { int x; float y;} result;
  int f,minus1=0xFFFFFFFF,r,a[]={0};
  r=a[3]&2;                     //accessing past end of array
  result.x=read(&argv[r],--r);  //relying on order of arguments
  for(f=*(int*)&result.y;f;f+=minus1) //type punning/invalid union access,
    r*=f;                            //and unsigned overflow
  printf("%d\n",(&r+2)[-2]); //negative array indexes
}

```
> 24 votes

# Answer
# XHTML

```
<p>
   <div></div>
</p>

```

The W3C specification (http://www.w3.org/TR/html-markup/p.html#p):

> # p – paragraph
>
> The p element represents a paragraph.
>
> ## Permitted contents
>
> **Phrasing content**

Oh I feel dirty!

**Edit:** @xfix pointed out that the error I was displaying was actually XHTML. The HTML error this causes is cooler and less obvious such that:

`<p><div></div><p>` becomes `<p /><div></div></p>` because the `<div>` causes the `<p>` to self close. Thus resulting in an error because we are attempting to close a paragraph that doesn't exist.
> 17 votes

# Answer
HTTP/1.1: Response - Status Code and Reason Phrase

> The Status-Code element is a 3-digit...

Need I go any further? This status code isn't one of the codes defined in the standard. It doesn't even begin with one of the required category digits. It's not even 3 digits long.

My browser still manages to load the page fine.

In addition, this answer breaks one of this site's "standards" :)

Output (status line):

```
HTTP/1.1 0 :)

```

```
var http = require("http");
var server = http.createServer(onHttpRequest);
server.listen(80);

function onHttpRequest(request, response)
{
    response.writeHead(0, ":)", { "Content-Type": "text/plain" });
    response.write("Hello, World!");
    response.end();
}

```

## JavaScript (Node)
> 12 votes

# Answer
How many standards did I just break?

I did some awful programming indeed here.

# PHP

```
a: goto lol; begin();
b:
c: echo j; goto h;
d: echo u;
e: echo s;
f: echo t;
g:
h: echo k; goto o;
i: echo i; goto c;
j: echo l;
k: echo l;
l: echo e;
m: echo d;
n:
o: echo s;
p: echo t; goto u;
q: echo a; goto z;
r: echo n;
s: echo d;
t: echo a;
u: echo r; goto q;
v: echo D; goto i;
w: echo s;
x:
y:
z: die("!");
lol: goto v;

```

**Easter Egg:** The `echo`ed letters, if read vertically, will read `just killed standarDs!`.

**Sidenote:** Running this program will output the name of a guy who really loved `goto`s.
> 12 votes

# Answer
## C# - breaking Unicode

Simple algorithm to reverse a string:

```
public string Reverse(string s)
{
    StringBuilder builder = new StringBuilder();
    for (int i = s.Length - 1; i >= 0; i--)
    {
        builder.Append(s[i]);
    }
    return builder.ToString();
}

```

This breaks the Unicode standard, because it does not correctly keep surrogate pairs together, creating an invalid string. In .NET and many other platforms/programming languages, a `char` is not really a character, but a UTF-16 code unit.

NB: It also changes which letter is combined with subsequent combining marks (e.g. diacritics), which may or may not be intended.
> 9 votes

# Answer
# JavaScript

Run it in the console on this page.

```
var items = [], p = 1, finish = false, intr = setInterval(function() {
    if (p >= 10) finish = true
    $.get(unescape(escape('http://api.stackexchange.com/2.2/answers?page=' + (p++) + '&pagesize=100&order=desc&sort=votes&site=codegolf&filter=!*LVwAFZ.YnaK-KS*')), function(x) {
        items = items.concat(x.items)
        if (finish) {
            clearInterval(intr)
            onFinish()
        }
    })
}, 500)

function onFinish() {
    var item = items[Math.floor(Math.random() * items.length)]
    document.write(item.body)
}

```

Inspired by

> The majority of answers on this site violate at least one coding standard... – Comintern *1 hour ago*

What it does is output **a random answer out of the top 1000 voted from codegolf.SE** (i.e., solving the problem in a very meta fashion!), complete with formatting and all, on your page!

---

Unfortunately, this technically doesn't satisfy the rules, since the *output* is the code with the broken standards, so I did break a standard in this code - I used `document.write` (ewwww). I also have to provide a link, so here: Why is document.write considered a "bad practice"?

If that doesn't count as "breaking the standards," just in case, I wrapped my string in `unescape(escape())`, which is deprecated, as per MDN.

Note that I'm really just doing all this to get around the rules, and the main point of this answer is its output.

---

Sample run (click image to enlarge):
> 8 votes

# Answer
# XML

Not my "invention", I actually have to work with XML's like this that we get from a very secret place:

```
<?xml version="1.0"?>
<!DOCTYPE data [
  <!ELEMENT data (field2)>
  <!ELEMENT field2 (#PCDATA)>
]>
<data>
  <field1>Rock & Roll</field1>
</data>
<data>
  <field1>Something else</field1>
</data>

```

Doesn't validate against its own embedded DTD, contains multiple roots and unescaped ampersands. (There are also other higher level errors, ambiguous content model, etc., not demonstrated here.) Very sad.
> 6 votes

# Answer
Setting the netmask to non-contigous bitmasks was allowed but highly discouraged by RFC 950, but is now forbidden as of RFC 1219. Nevertheless, BSD-likes allow you to do this.

IPv4 netmasks are a combination of four bytes, just like an IP address. It is used to calculate, if two hosts with known IP addresses and netmasks are on the same network. In general an IP address consists of two parts: The network and the host part. Say your network at home is `192.168.1.1` \- `192.168.1.254`. The host part are the first three bytes of the IP, namely `192.168.1.x`. This means the netmask is `255.255.255.0`, meaning the first 24 bits are the network part. In binary the mask looks like `11111111.11111111.11111111.00000000`. The 1-bits are continous. In my example, the netmask would be `00010111.00000000.00000000.00101010`. So what would happen, if the netmask is non-continous? Instead of being at the right end, the host part is scattered over the whole IP address, making it really hard to read, just like my explanation here.

**DO NOT expect anything to work after this!**

```
root@Gotthold /v/root# ifconfig en0 inet 47.11.23.42 netmask 23.0.0.42
root@Gotthold /v/root# ifconfig en0 inet
en0: flags=8863<UP,BROADCAST,SMART,RUNNING,SIMPLEX,MULTICAST> mtu 8192
    options=b<RXCSUM,TXCSUM,VLAN_HWTAGGING>
    inet 47.11.23.42 netmask 0x1700002a broadcast 239.255.255.255

```
> 6 votes

# Answer
# C

How many errors can you find, which probably would cause most companies to reject your code (especially good ones). Most of these are probably style mistakes (that I hope nobody does), but some of these are undefined behavior.

```
    #define BEGIN {
    #define END }
    #define print printf
    void main(int argv, char* argc, char **args) BEGIN
print("hELLO,"); printf("WORLD");
    END

```

> 1. It defines macros that make C feel like another language (most codestyle guidelines).
> 2. The `main` function returns `void`, when it should return `int` (implementation-defined behavior).
> 3. `main` uses a form with three arguments, when it's not standard (undefined behavior).
> 4. Those arguments have incorrect names (most codestyle guidelines).
> 5. `argc` (should be `argv`) has incorrect type. It should be `char **`, but it's `char *` (undefined behavior).
> 6. Mixing C and C++ declaration styles, which differ in `*` position (most codelines guidelines want consistent code).
> 7. Strange coding style where the deeper code is deintended (most codestyle guidelines).
> 8. Using a function (`printf`) without importing correct header (undefined behavior, as it's a variadic function).
> 9. Using Caps Lock to write messages (most language guidelines).
> 10. No space after comma (most language guidelines).
> 11. Multiple statements on one line (most codestyle guidelines).
> 12. No new line printed at end, causing the prompt to be drawn on the end of program (implementation-defined behavior).
> 14. The return value is not defined (implementation-defined behavior).
> 6 votes

# Answer
# Go

```
package main

func main() {
    println(whereas "Standards are important")
    println("But sometimes it's fun to break them" despiteallobjections)
}

```

http://play.golang.org/p/DrDHF9EMgu

Explanation is here. The "whereas" and "despiteallobjections" rules don't appear in the spec, but the lexer just skips over them, as kind of an easter egg. I guess the linter is more standards-compliant because if you click "Format" on that Go Playground link, you get a parse error.
> 5 votes

# Answer
# JavaScript

```
standards:
while(1)
   break standards

```

## Explanation:

A while loop labeled "standards" is exited.

## Standards broken:

```
standards: <-- that one
while(1)
   break standards

```
> 4 votes

# Answer
**JavaScript**

```
var a = 1;
var b = a + 2;

```

It breaks a standard because it doesn't use enough jQuery
The proper way to write this code can be seen here
> 3 votes

# Answer
GML breaks a ton of standards. One being the beauty of not allowing for use of Ternary operators. Instead of using Ternary Operators, in GML I'd do this:

```
z = ( y * ( z > 0 ) ) + ( x * ( z <= 0 ) );

```

Where the Ternary equivalent is:

```
z = ( z > 0 ) ? y : x;

```

The first is pretty nasty especially when you start adding in other operations.
> 2 votes

# Answer
## Haskell

My program doesn't really break any standards, but just randomly selects one to use. It tries to be fair across the different standards. Here is my code.

```
import System.Random
import Control.Applicative
newlines=["\n", "\r\n", "\r"]
pick::[a]->IO a
pick lst=fmap (lst !!) $ randomRIO (0, length lst - 1)

fairUnlines::[String]->IO String
fairUnlines []         = pure ""
fairUnlines [str]      = pure str
fairUnlines (str:strs) = (\x y z->x++y++z) <$>
    pure str <*> pick newlines <*> fairUnlines strs

```

`fairUnlines` will take a list of Strings, and join them using random newline character standards. Also, it is the first time I have actually used the applicative style, on IO none the less.
> 1 votes

# Answer
# Bash

Taking from your example:

```
ping 192.168.0.1 -c 1 -s 10000

```

Assuming your router is at `192.168.0.1`

*Note: the max ping size is 65kb, so i did 10 kb in stead of 10 mb*
> 1 votes

# Answer
# Java

Oh dear, someone forgot the getter again...

```
import java.lang.reflect.*;

class Main {
    public static void main(String[] args) throws Exception {

        // Brian forgot to implement the getter again.
        // He's on vacation, so this will have to do.

        // TODO: figure out what he named the fields
        Field field = UsefulObject.class.getDeclaredFields()[1];
        Field objField = UsefulObject.class.getDeclaredFields()[0];

        field.setAccessible(true);
        objField.setAccessible(true);

        Object obj = objField.get(null);
        String s = (String) field.get(obj);

        System.out.println(s);
    }
}
class UsefulObject {

    private static UsefulObject Useful;
    private String usefulField;

    static {
        Useful = new UsefulObject("useful field");
    }
    private UsefulObject(String s) {
        this.usefulField = s;
    }

    public String getUsefulField() { return usefulField; }

    public static UsefulObject getUsefulObject() {
        throw new UnsupportedOperationException("TODO");
    }
}

```

The `Useful` field should be lowercase: `useful`

Not sure this is a standard: useless wildcard import (should just be `java.lang.reflect.Field` since that's all that's being used).
> 0 votes

---
Tags: popularity-contest
---