title: Generalized Cantor set segment lengths

text:
# Question
Title: Generalized Cantor set segment lengths
# Problem

Let's define a generalized Cantor set by iteratively deleting some rational length segments from the middle of all intervals that haven't yet been deleted, starting from a single continuous interval.

Given the relative lengths of segments to delete or not, and the number of iterations to do, the problem is to write a program or function that outputs the relative lengths of the segments that have or have not been deleted after `n` iterations.

Example: Iteratively delete the 4th and 6th eighth

# Input:

`n` – number of iterations, indexed starting from 0 or 1

`l` – list of segment lengths as positive integers with `gcd(l)=1` and odd length, representing the relative lengths of the parts that either stay as they are or get deleted, starting from a segment that doesn't get deleted. Since the list length is odd, the first and last segments never get deleted. For example for the regular Cantor set this would be \[1,1,1\] for one third that stays, one third that gets deleted and again one third that doesn't.

# Output:

Integer list `o`, `gcd(o)=1`, of relative segment lengths in the `n`th iteration when the segments that weren't deleted in the previous iteration are replaced by a scaled down copy of the list `l`. The first iteration is just `[1]`. You can use any unambiguous output method, even unary.

# Examples

```
n=0, l=[3,1,1,1,2] →                 [1]
n=1, l=[3,1,1,1,2] →     [3,    1,    1,    1,    2]
n=2, l=[3,1,1,1,2] → [9,3,3,3,6,8,3,1,1,1,2,8,6,2,2,2,4]

n=3, l=[5,2,3]     → [125,50,75,100,75,30,45,200,75,30,45,60,45,18,27]
n=3, l=[1,1,1]     → [1,1,1,3,1,1,1,9,1,1,1,3,1,1,1]

```

You can assume the input is valid. This is , so the shortest program measured in bytes wins.

# Answer
# Jelly,  ~~15 13~~  12 bytes

-2 thanks to Dennis (using a Link rather than a chain allows right to be used implicitly by `¡`; No need to wrap the `1` in a list due to the fact that Jelly prints lists of one item the same as the item)
-1 thanks to Erik the Outgolfer (use `Ɗ` to save the newline from using `Ç`)

```
1×€³§JḤ$¦ẎƊ¡

```

A full program printing a list in Jelly format (so `[1]` is printed as `1`)

**Try it online!**

### How?

```
1×€³§JḤ$¦ẎƊ¡ - Main link: segmentLengths; iterations
1            - literal 1 (start with a single segment of length 1)
           ¡ - repeat...
             - ...times: implicitly use chain's right argument, iterations
          Ɗ  - ...do: last 3 links as a monad (with 1 then the previous output):
   ³         - (1) program's 3rd argument = segmentLengths
 ×€          -  1  multiply €ach (e.g. [1,2,3] ×€ [1,2,1] = [[1,4,3],[2,4,2],[3,6,3]])
        ¦    -  2  sparse application...
       $     - (2) ...to: indices: last two links as a monad:
     J       - (2)          range of length = [1,2,3,...,numberOfLists]
      Ḥ      - (2)          double            [2,4,6,...] (note: out-of bounds are ignored by ¦)
    §        - (2) ...of: sum each (i.e. total the now split empty spaces)
         Ẏ   -  3  tighten (e.g. [[1,2,3],4,[5,6,7]] -> [1,2,3,4,5,6,7])
             - implicit print

```
> 6 votes

# Answer
# Python 2, ~~120~~ ~~107~~ ~~104~~ ~~103~~ ~~100~~ ~~99~~ 89 bytes

```
f=lambda n,l:n and[x*y for i,x in enumerate(l)for y in[f(n-1,l),[sum(l)**~-n]][i%2]]or[1]

```

Try it online!

---

Saved

* -10 bytes, thanks to Neil
> 4 votes

# Answer
# Haskell, ~~76~~ 58 bytes

```
l%0=[1]
l%n=do(x,m)<-l%(n-1)`zip`cycle[l,[sum l]];map(*x)m

```

Try it online!

The function `(%)` takes the list of line lengths `l` as first argument and the number of iterations `n` as second input.

*Thanks to Angs and Ørjan Johansen for -18 bytes!*
> 4 votes

# Answer
# , 94 bytes

```
f=function(n,a)"if"(n,unlist(Map(function(g,i)g(i),c(c,sum),split(m<-a%o%f(n-1,a),row(m)))),1)

```

Try it online!
> 4 votes

# Answer
## JavaScript (Firefox 42-57), 80 bytes

```
f=(n,l,i=0)=>n--?[for(x of l)for(y of(i^=1)?f(n,l):[eval(l.join`+`)**n])x*y]:[1]

```

Needs those specific versions because it uses both array comprehensions and exponentiation.
> 3 votes

# Answer
# JavaScript (Node.js), 71 bytes

```
l=>f=(n,c=1,e)=>n--?''+l.map(_=>(e=!e)?f(n,c*_):eval(l.join`+`)**n*c):c

```

Try it online!
> 3 votes

# Answer
# Java 10, 261 bytes

```
L->n->{if(n<1){L.clear();L.add(1);}else if(n>1){var C=new java.util.ArrayList<Integer>(L);for(int l=C.size(),i,x,t,s;n-->1;)for(i=x=0;i<L.size();){t=L.remove(i);if(i%2<1)for(;i%-~l<l;)L.add(i,C.get((i++-x)%l)*t);else{x++;s=0;for(int c:C)s+=c;L.add(i++,t*s);}}}}

```

Modifies the input-List instead of returning a new one to save bytes.

Try it online.

```
L->n->{                       // Method with List and integer parameters and no return-type
  if(n<1){                    //  If `n` is 0:
    L.clear();                //   Remove everything from the List
    L.add(1);}                //   And only add a single 1
                              //  Else-if `n` is 1: Leave the List as is
  else if(n>1){               //  Else-if `n` is 2 or larger:
    var C=new java.util.ArrayList<Integer>(L);
                              //   Create a copy of the input-List
    for(int l=C.size(),       //   Set `l` to the size of the input-List
        i,x,t,s;              //   Index and temp integers
        n-->1;)               //   Loop `n-1` times:
      for(i=x=0;              //    Reset `x` to 0
          i<L.size();){       //    Inner loop `i` over the input-List
        t=L.remove(i);        //     Remove the current item, saving its value in `t`
        if(i%2<1)             //     If the current iteration is even:
          for(;i%-~l<l;)      //      Loop over the copy-List
            L.add(i,C.get((i++-x)%l)*t);
                              //       And add the values multiplied by `t`
                              //       at index `i` to the List `L`
        else{                 //     Else (the current iteration is odd):
          x++;                //      Increase `x` by 1
          s=0;for(int c:C)s+=c;
                              //      Calculate the sum of the copy-List
          L.add(i++,t*s);}}}} //      Add this sum multiplied by `t`
                              //      at index `i` to the List `L`

```
> 2 votes

# Answer
# Jelly, 13 bytes

```
Ø1××S¥ƭ€³Ẏ$¡Ṗ

```

Try it online!

Full program. Outputs `1` instead of `[1]`. Annoyingly,  doesn't work like `×S¥` in this context, and `ƭ` doesn't work well with nilads. \>\_\<
> 2 votes

# Answer
# APL (Dyalog Classic), 20 bytes

```
{(∊⊢×⍵(+/⍵)⍴⍨≢)⍣⍺,1}

```

Try it online!
> 2 votes

# Answer
# K (ngn/k), 27 bytes

```
{x{,/y*(#y)#x}[(y;+/y)]/,1}

```

Try it online!

`{` `}` is a function with arguments `x` and `y`

`(y;+/y)` a pair of `y` and its sum

`{` `}[(y;+/y)]` projection (aka currying or partial application) of a dyadic function with one argument. `x` will be `(y;+/y)` and `y` will be the argument when applied.

`,1` singleton list containing 1

`x{` `}[` `]/` apply the projection `x` times

`(#y)#x` reshape to the length of the current result, i.e. alternate between the outer `y` and its sum

`y*` multiply each element of the above with the corresponding element of the current result

`,/` concatenate
> 2 votes

# Answer
# Ruby, 73 bytes

```
->a,l{r=[1];a.times{s=p;r=r.flat_map{|x|(s=!s)?l.map{|y|x*y}:x*l.sum}};r}

```

Try it online!
> 1 votes

# Answer
# Pyth, 20 bytes

```
us.e?%k2*bsQ*LbQGE]1

```

Input is segment array `l`, then iterations `n`. Try it online here, or verify all the test cases at once here.

```
us.e?%k2*bsQ*LbQGE]1   Implicit, Q=1st arg (segment array), E=2nd arg (iterations)
u                E     Execute E times, with current value G...
                  ]1   ... and initial value [1]:
  .e            G        Map G, with element b and index k:
        *bsQ               Multiply b and the sum of Q {A}
            *LbQ           Multiply each value of Q by b {B}
    ?%k2                   If k is odd, yield {A}, otherwise yield {B}
 s                       Flatten the resulting nested array

```
> 1 votes

---
Tags: code-golf, sequence, fractal, recursion
---


# Question
Title: Sometimes I need a Lossless Screenshot Resizer
Sometimes I need to write more documentation than just comments in code. And sometimes, those explanations need screenshots. Sometimes the conditions to get such a screenshot are so weird that I ask a developer to take a screenshot for me. Sometimes the screenshot does not fit my specifications and I have to resize it so that it looks nicely.

As you can see, the circumstances for a need for the magic "Lossless Screenshot Resizer" are very unlikely. Anyway, for me it seems I need it every day. But it doesn't exist yet.

I've seen you here on PCG solve awesome graphical puzzles before, so I guess this one is rather boring for you...

## Specification

* The program takes a screenshot of a single window as input
* The screenshot does not make use of glass effects or similar (so you don't need to deal with any background stuff that shines through)
* The input file format is PNG (or any other lossless format so that you don't have to deal with compression artifacts)
* The output file format is the same as the input file format
* The program creates a screenshot of different size as output. Minimum requirement is shrinking in size.
* The user shall specify the expected output size. If you can give hints about the minimum size your program can produce from the given input, that's helpful.
* **The output screenshot must not have less information if interpreted by a human.** You shall not remove text or image content, but you shall remove areas with background only. See examples below.
* If it is not possible to get the expected size, the program should indicate that and not simply crash or remove information without further notice.
* If the program indicates the areas which will be removed for verification reasons, that should increase its popularity.
* The program may need some other user input, e.g. to identify the starting point for optimization.

## Rules

This is a popularity contest. The answer with most votes on 2015-03-08 gets accepted.

## Examples

Windows XP screenshot. Original size: 1003x685 pixels.

Example areas (red: vertical, yellow: horizontal) that can be removed without losing any information (text or images). Note that the red bar isn't contiguous. This example doesn't indicate all possible pixels that could potentially be removed.

Losslessly resized: 783x424 pixels.

Windows 10 screenshot. Original size: 999x593 pixels.

Example areas which can be removed.

Losslessly resized screenshot: 689x320 pixels.

Note that it is ok that the title text ("Downloads") and "This folder is empty" are not centered any more. Of course, it would be nicer if it is centered, and if your solution provides that, it should become more popular.

# Answer
> 31 votes
# Python

the function `delrows` deletes all but one duplicate rows and returns the transposed image, applying it twice also deletes the columns and transposes it back. Additionally `threshold` controls how many pixels can differ for two lines to be still considered the same

```
from scipy import misc
from pylab import *

im7 = misc.imread('win7.png')
im8 = misc.imread('win8.png')

def delrows(im, threshold=0):
    d = diff(im, axis=0)
    mask = where(sum((d!=0), axis=(1,2))>threshold)
    return transpose(im[mask], (1,0,2))

imsave('crop7.png', delrows(delrows(im7)))
imsave('crop8.png', delrows(delrows(im8)))

```

Flipping the comparator in `mask` from `>` to `<=` will instead output the removed areas which are mostly blank space.

**golfed (because why not)**
Instead of comparing each pixel it only looks at the sum, as a side effect this also converts the screenshot to greyscale and has trouble with sum-preserving permutations, like the down-arrow in the address bar of the Win8 screenshot

```
from scipy import misc
from pylab import*
f=lambda M:M[where(diff(sum(M,1)))].T
imsave('out.png', f(f(misc.imread('in.png',1))),cmap='gray')

```

# Answer
> 15 votes
## Java: Try lossless and fallback to content-aware

*(Best lossless result so far!)*

When I first looked at this question I thought this is not a puzzle or challenge just someone desperately in need of a program and it's code ;) But it is in my nature to solve vision problems so I could not stop my self from trying this challenge!

I came up with the following approach and combination of algorithms.

**In pseudo-code it looks like this:**

```
function crop(image, desired) {
    int sizeChange = 1;
    while(sizeChange != 0 and image.width > desired){

        Look for a repeating and connected set of lines (top to bottom) with a minimum of x lines
        Remove all the lines except for one
        sizeChange = image.width - newImage.width
        image = newImage;
    }
    if(image.width > desired){
        while(image.width > 2 and image.width > desired){
           Create a "pixel energy" map of the image
           Find the path from the top of the image to the bottom which "costs" the least amount of "energy"
           Remove the lowest cost path from the image
           image = newImage;
        }
    }
}

int desiredWidth = ?
int desiredHeight = ?
Image image = input;

crop(image, desiredWidth);
rotate(image, 90);
crop(image, desiredWidth);
rotate(image, -90);

```

**Used techniques:**

* Intensity grayscale
* Dilation
* Equal column search and remove
* Seam-carving
* Sobel edge detection
* Thresholding

---

## The Program

The program can crop screenshots lossless but has an option to fallback to content-aware cropping which is not 100% lossless. The arguments of the program can be tweaked to achieve better results.

Note: The program can be improved in many ways (I don't have that much spare time!)

**Arguments**

```
File name = file
Desired width = number > 0
Desired height = number > 0
Min slice width = number > 1
Compare threshold = number > 0
Use content aware = boolean
Max content aware cycles = number >= 0

```

**Code**

```
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.awt.image.ColorModel;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;
import javax.swing.ImageIcon;
import javax.swing.JLabel;
import javax.swing.JOptionPane;

/**
 * @author Rolf Smit
 * Share and adapt as you like, but don't forget to credit the author!
 */
public class MagicWindowCropper {

    public static void main(String[] args) {
        if(args.length != 7){
            throw new IllegalArgumentException("At least 7 arguments are required: (file, desiredWidth, desiredHeight, minSliceSize, sliceThreshold, forceRemove, maxForceRemove)!");
        }

        File file = new File(args[0]);

        int minSliceSize = Integer.parseInt(args[3]); //4;
        int desiredWidth = Integer.parseInt(args[1]); //400;
        int desiredHeight = Integer.parseInt(args[2]); //400;

        boolean forceRemove = Boolean.parseBoolean(args[5]); //true
        int maxForceRemove = Integer.parseInt(args[6]); //40

        MagicWindowCropper.MATCH_THRESHOLD = Integer.parseInt(args[4]); //3;

        try {

            BufferedImage result = ImageIO.read(file);

            System.out.println("Horizontal cropping");

            //Horizontal crop
            result = doDuplicateColumnsMagic(result, minSliceSize, desiredWidth);
            if (result.getWidth() != desiredWidth && forceRemove) {
                result = doSeamCarvingMagic(result, maxForceRemove, desiredWidth);
            }

            result = getRotatedBufferedImage(result, false);

            System.out.println("Vertical cropping");

            //Vertical crop
            result = doDuplicateColumnsMagic(result, minSliceSize, desiredHeight);
            if (result.getWidth() != desiredHeight && forceRemove) {
                result = doSeamCarvingMagic(result, maxForceRemove, desiredHeight);
            }

            result = getRotatedBufferedImage(result, true);

            showBufferedImage("Result", result);

            ImageIO.write(result, "png", getNewFileName(file));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static BufferedImage doSeamCarvingMagic(BufferedImage inputImage, int max, int desired) {
        System.out.println("Seam Carving magic:");

        int maxChange = Math.min(inputImage.getWidth() - desired, max);

        BufferedImage last = inputImage;
        int total = 0, change;
        do {
            int[][] energy = getPixelEnergyImage(last);
            BufferedImage out = removeLowestSeam(energy, last);

            change = last.getWidth() - out.getWidth();
            total += change;
            System.out.println("Carves removed: " + total);
            last = out;
        } while (change != 0 && total < maxChange);

        return last;
    }

    private static BufferedImage doDuplicateColumnsMagic(BufferedImage inputImage, int minSliceWidth, int desired) {
        System.out.println("Duplicate columns magic:");

        int maxChange = inputImage.getWidth() - desired;

        BufferedImage last = inputImage;
        int total = 0, change;
        do {
            BufferedImage out = removeDuplicateColumn(last, minSliceWidth, desired);

            change = last.getWidth() - out.getWidth();
            total += change;
            System.out.println("Columns removed: " + total);
            last = out;
        } while (change != 0 && total < maxChange);
        return last;
    }

    /*
     * Duplicate column methods
     */

    private static BufferedImage removeDuplicateColumn(BufferedImage inputImage, int minSliceWidth, int desiredWidth) {
        if (inputImage.getWidth() <= minSliceWidth) {
            throw new IllegalStateException("The image width is smaller than the minSliceWidth! What on earth are you trying to do?!");
        }

        int[] stamp = null;
        int sliceStart = -1, sliceEnd = -1;
        for (int x = 0; x < inputImage.getWidth() - minSliceWidth + 1; x++) {
            stamp = getHorizontalSliceStamp(inputImage, x, minSliceWidth);
            if (stamp != null) {
                sliceStart = x;
                sliceEnd = x + minSliceWidth - 1;
                break;
            }
        }

        if (stamp == null) {
            return inputImage;
        }

        BufferedImage out = deepCopyImage(inputImage);

        for (int x = sliceEnd + 1; x < inputImage.getWidth(); x++) {
            int[] row = getHorizontalSliceStamp(inputImage, x, 1);
            if (equalsRows(stamp, row)) {
                sliceEnd = x;
            } else {
                break;
            }
        }

        //Remove policy
        int canRemove = sliceEnd - (sliceStart + 1) + 1;
        int mayRemove = inputImage.getWidth() - desiredWidth;

        int dif = mayRemove - canRemove;
        if (dif < 0) {
            sliceEnd += dif;
        }

        int mustRemove = sliceEnd - (sliceStart + 1) + 1;
        if (mustRemove <= 0) {
            return out;
        }

        out = removeHorizontalRegion(out, sliceStart + 1, sliceEnd);
        out = removeLeft(out, out.getWidth() - mustRemove);
        return out;
    }

    private static BufferedImage removeHorizontalRegion(BufferedImage image, int startX, int endX) {
        int width = endX - startX + 1;

        if (endX + 1 > image.getWidth()) {
            endX = image.getWidth() - 1;
        }
        if (endX < startX) {
            throw new IllegalStateException("Invalid removal parameters! Wow this error message is genius!");
        }

        BufferedImage out = deepCopyImage(image);

        for (int x = endX + 1; x < image.getWidth(); x++) {
            for (int y = 0; y < image.getHeight(); y++) {
                out.setRGB(x - width, y, image.getRGB(x, y));
                out.setRGB(x, y, 0xFF000000);
            }
        }
        return out;
    }

    private static int[] getHorizontalSliceStamp(BufferedImage inputImage, int startX, int sliceWidth) {
        int[] initial = new int[inputImage.getHeight()];
        for (int y = 0; y < inputImage.getHeight(); y++) {
            initial[y] = inputImage.getRGB(startX, y);
        }
        if (sliceWidth == 1) {
            return initial;
        }
        for (int s = 1; s < sliceWidth; s++) {
            int[] row = new int[inputImage.getHeight()];
            for (int y = 0; y < inputImage.getHeight(); y++) {
                row[y] = inputImage.getRGB(startX + s, y);
            }

            if (!equalsRows(initial, row)) {
                return null;
            }
        }
        return initial;
    }

    private static int MATCH_THRESHOLD = 3;

    private static boolean equalsRows(int[] left, int[] right) {
        for (int i = 0; i < left.length; i++) {

            int rl = (left[i]) & 0xFF;
            int gl = (left[i] >> 8) & 0xFF;
            int bl = (left[i] >> 16) & 0xFF;

            int rr = (right[i]) & 0xFF;
            int gr = (right[i] >> 8) & 0xFF;
            int br = (right[i] >> 16) & 0xFF;

            if (Math.abs(rl - rr) > MATCH_THRESHOLD
                    || Math.abs(gl - gr) > MATCH_THRESHOLD
                    || Math.abs(bl - br) > MATCH_THRESHOLD) {
                return false;
            }
        }
        return true;
    }

    /*
     * Seam carving methods
     */

    private static BufferedImage removeLowestSeam(int[][] input, BufferedImage image) {
        int lowestValue = Integer.MAX_VALUE; //Integer overflow possible when image height grows!
        int lowestValueX = -1;

        // Here be dragons
        for (int x = 1; x < input.length - 1; x++) {
            int seamX = x;
            int value = input[x][0];
            for (int y = 1; y < input[x].length; y++) {
                if (seamX < 1) {
                    int top = input[seamX][y];
                    int right = input[seamX + 1][y];
                    if (top <= right) {
                        value += top;
                    } else {
                        seamX++;
                        value += right;
                    }
                } else if (seamX > input.length - 2) {
                    int top = input[seamX][y];
                    int left = input[seamX - 1][y];
                    if (top <= left) {
                        value += top;
                    } else {
                        seamX--;
                        value += left;
                    }
                } else {
                    int left = input[seamX - 1][y];
                    int top = input[seamX][y];
                    int right = input[seamX + 1][y];

                    if (top <= left && top <= right) {
                        value += top;
                    } else if (left <= top && left <= right) {
                        seamX--;
                        value += left;
                    } else {
                        seamX++;
                        value += right;
                    }
                }
            }
            if (value < lowestValue) {
                lowestValue = value;
                lowestValueX = x;
            }
        }

        BufferedImage out = deepCopyImage(image);

        int seamX = lowestValueX;
        shiftRow(out, seamX, 0);
        for (int y = 1; y < input[seamX].length; y++) {
            if (seamX < 1) {
                int top = input[seamX][y];
                int right = input[seamX + 1][y];
                if (top <= right) {
                    shiftRow(out, seamX, y);
                } else {
                    seamX++;
                    shiftRow(out, seamX, y);
                }
            } else if (seamX > input.length - 2) {
                int top = input[seamX][y];
                int left = input[seamX - 1][y];
                if (top <= left) {
                    shiftRow(out, seamX, y);
                } else {
                    seamX--;
                    shiftRow(out, seamX, y);
                }
            } else {
                int left = input[seamX - 1][y];
                int top = input[seamX][y];
                int right = input[seamX + 1][y];

                if (top <= left && top <= right) {
                    shiftRow(out, seamX, y);
                } else if (left <= top && left <= right) {
                    seamX--;
                    shiftRow(out, seamX, y);
                } else {
                    seamX++;
                    shiftRow(out, seamX, y);
                }
            }
        }

        return removeLeft(out, out.getWidth() - 1);
    }

    private static void shiftRow(BufferedImage image, int startX, int y) {
        for (int x = startX; x < image.getWidth() - 1; x++) {
            image.setRGB(x, y, image.getRGB(x + 1, y));
        }
    }

    private static int[][] getPixelEnergyImage(BufferedImage image) {

        // Convert Image to gray scale using the luminosity method and add extra
        // edges for the Sobel filter
        int[][] grayScale = new int[image.getWidth() + 2][image.getHeight() + 2];
        for (int x = 0; x < image.getWidth(); x++) {
            for (int y = 0; y < image.getHeight(); y++) {
                int rgb = image.getRGB(x, y);
                int r = (rgb >> 16) & 0xFF;
                int g = (rgb >> 8) & 0xFF;
                int b = (rgb & 0xFF);
                int luminosity = (int) (0.21 * r + 0.72 * g + 0.07 * b);
                grayScale[x + 1][y + 1] = luminosity;
            }
        }

        // Sobel edge detection
        final double[] kernelHorizontalEdges = new double[] { 1, 2, 1, 0, 0, 0, -1, -2, -1 };
        final double[] kernelVerticalEdges = new double[] { 1, 0, -1, 2, 0, -2, 1, 0, -1 };

        int[][] energyImage = new int[image.getWidth()][image.getHeight()];

        for (int x = 1; x < image.getWidth() + 1; x++) {
            for (int y = 1; y < image.getHeight() + 1; y++) {

                int k = 0;
                double horizontal = 0;
                for (int ky = -1; ky < 2; ky++) {
                    for (int kx = -1; kx < 2; kx++) {
                        horizontal += ((double) grayScale[x + kx][y + ky] * kernelHorizontalEdges[k]);
                        k++;
                    }
                }
                double vertical = 0;
                k = 0;
                for (int ky = -1; ky < 2; ky++) {
                    for (int kx = -1; kx < 2; kx++) {
                        vertical += ((double) grayScale[x + kx][y + ky] * kernelVerticalEdges[k]);
                        k++;
                    }
                }

                if (Math.sqrt(horizontal * horizontal + vertical * vertical) > 127) {
                    energyImage[x - 1][y - 1] = 255;
                } else {
                    energyImage[x - 1][y - 1] = 0;
                }
            }
        }

        //Dilate the edge detected image a few times for better seaming results
        //Current value is just 1...
        for (int i = 0; i < 1; i++) {
            dilateImage(energyImage);
        }
        return energyImage;
    }

    private static void dilateImage(int[][] image) {
        for (int x = 0; x < image.length; x++) {
            for (int y = 0; y < image[x].length; y++) {
                if (image[x][y] == 255) {
                    if (x > 0 && image[x - 1][y] == 0) {
                        image[x - 1][y] = 2; //Note: 2 is just a placeholder value
                    }
                    if (y > 0 && image[x][y - 1] == 0) {
                        image[x][y - 1] = 2;
                    }
                    if (x + 1 < image.length && image[x + 1][y] == 0) {
                        image[x + 1][y] = 2;
                    }
                    if (y + 1 < image[x].length && image[x][y + 1] == 0) {
                        image[x][y + 1] = 2;
                    }
                }
            }
        }
        for (int x = 0; x < image.length; x++) {
            for (int y = 0; y < image[x].length; y++) {
                if (image[x][y] == 2) {
                    image[x][y] = 255;
                }
            }
        }
    }

    /*
     * Utilities
     */

    private static void showBufferedImage(String windowTitle, BufferedImage image) {
        JOptionPane.showMessageDialog(null, new JLabel(new ImageIcon(image)), windowTitle, JOptionPane.PLAIN_MESSAGE, null);
    }

    private static BufferedImage deepCopyImage(BufferedImage input) {
        ColorModel cm = input.getColorModel();
        return new BufferedImage(cm, input.copyData(null), cm.isAlphaPremultiplied(), null);
    }

    private static final BufferedImage getRotatedBufferedImage(BufferedImage img, boolean back) {
        double oldW = img.getWidth(), oldH = img.getHeight();
        double newW = img.getHeight(), newH = img.getWidth();

        BufferedImage out = new BufferedImage((int) newW, (int) newH, img.getType());
        Graphics2D g = out.createGraphics();
        g.translate((newW - oldW) / 2.0, (newH - oldH) / 2.0);
        g.rotate(Math.toRadians(back ? -90 : 90), oldW / 2.0, oldH / 2.0);
        g.drawRenderedImage(img, null);
        g.dispose();
        return out;
    }

    private static BufferedImage removeLeft(BufferedImage image, int startX) {
        int removeWidth = image.getWidth() - startX;

        BufferedImage out = new BufferedImage(image.getWidth() - removeWidth,
                image.getHeight(), image.getType());

        for (int x = 0; x < startX; x++) {
            for (int y = 0; y < out.getHeight(); y++) {
                out.setRGB(x, y, image.getRGB(x, y));
            }
        }
        return out;
    }

    private static File getNewFileName(File in) {
        String name = in.getName();
        int i = name.lastIndexOf(".");
        if (i != -1) {
            String ext = name.substring(i);
            String n = name.substring(0, i);
            return new File(in.getParentFile(), n + "-cropped" + ext);
        } else {
            return new File(in.getParentFile(), name + "-cropped");
        }
    }
}

```

---

## Results

---

## XP screenshot lossless without desired size (Max lossless compression)

**Arguments:** "image.png" 1 1 5 10 false 0

**Result:** 836 x 323

---

## XP screenshot to 800x600

**Arguments:** "image.png" 800 600 6 10 true 60

**Result:** 800 x 600

The lossless algorithm removes about 155 horizontal lines than the algorithm falls back to content-aware removal therefor some artifacts can be seen.

---

## Windows 10 screenshot to 700x300

**Arguments:** "image.png" 700 300 6 10 true 60

**Result:** 700 x 300

The lossless algorithm removes 270 horizontal lines than the algorithm falls back to content-aware removal which removes another 29. Vertical only the lossless algorithm is used.

---

## Windows 10 screenshot content-aware to 400x200 (test)

**Arguments:** "image.png" 400 200 5 10 true 600

**Result:** 400 x 200

This was a test to see how the resulting image would look after severe use of the content-aware feature. The result is heavily damaged but not unrecognizable.

---

# Answer
> 3 votes
## C#, algorithm like I would do it manually

This is my first image processing program and it took a while to implement with all that `LockBits` stuff etc. But I wanted it to be fast (using `Parallel.For`) to get an almost instant feedback.

Basically my algorithm is based on observations on how I remove pixels manually from a screenshot:

* I am starting from the right edge, because chances are higher that unused pixels are there.
* I define a threshold for edge detection in order to capture the system buttons correctly. For the Windows 10 screenshot, a threshold of 48 pixels works well.
* After the edge is detected (marked in red color below), I am looking for pixels of the same color. I take the minimum number of pixels found and apply it to all rows (marked violet).
* Then I start over again with edge detection (marked red), pixels of the same color (marked blue, then green, then yellow) and so forth

At the moment I do it horizontally only. The vertical result can use the same algorithm and operate on a 90° rotated image, so in theory it's possible.

## Results

This is a screenshot of my application with detected regions:

And this is the result for the Windows 10 screenshot and 48 pixels threshold. The output is 681 pixels wide. Unfortunately it's not perfect (see "Search Downloads" and some of the vertical column bars).

And another one with 64 pixels threshold (567 pixels wide). This looks even better.

Overall result applying rotation to crop from all bottom as well (567x304 pixels).

For Windows XP, I needed to change the code a bit since the pixels are not exactly equal. I am applying a similarity threshold of 8 (difference in RGB value). Note some artifacts in the columns.

## Code

Well, my first attempt on image processing. Doesn't look very good, does it? This only lists the core algorithm, not the UI and not the 90° rotation.

```
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Linq;
using System.Threading.Tasks;

namespace LosslessScreenshotResizer.BL
{
    internal class PixelAreaSearcher
    {
        private readonly Bitmap _originalImage;

        private readonly int _edgeThreshold;
        readonly Color _edgeColor = Color.FromArgb(128, 255, 0, 0);
        readonly Color[] _iterationIndicatorColors =
        {
            Color.FromArgb(128, 0, 0, 255),
            Color.FromArgb(128, 0, 255, 255),
            Color.FromArgb(128, 0, 255, 0),
            Color.FromArgb(128, 255, 255, 0)
        };

        public PixelAreaSearcher(Bitmap originalImage, int edgeThreshold)
        {
            _originalImage = originalImage;
            _edgeThreshold = edgeThreshold;

            // cache width and height. Also need to do that because of some GDI exceptions during LockBits
            _imageWidth = _originalImage.Width;
            _imageHeight = _originalImage.Height;
        }

        public Bitmap SearchHorizontal()
        {
            return Search();
        }

        /// <summary>
        /// Find areas of pixels to keep and to remove. You can get that information via <see cref="PixelAreas"/>.
        /// The result of this operation is a bitmap of the original picture with an overlay of the areas found.
        /// </summary>
        /// <returns></returns>
        private unsafe Bitmap Search()
        {
            // FastBitmap is a wrapper around Bitmap with LockBits enabled for fast operation.
            var input = new FastBitmap(_originalImage);
            // transparent overlay
            var overlay = new FastBitmap(_originalImage.Width, _originalImage.Height);

            _pixelAreas = new List<PixelArea>(); // save the raw data for later so that the image can be cropped
            int startCoordinate = _imageWidth - 1; // start at the right edge
            int iteration = 0; // remember the iteration to apply different colors
            int minimum;
            do
            {
                var indicatorColor = GetIterationColor(iteration);

                // Detect the edge which is not removable
                var edgeStartCoordinates = new PixelArea(_imageHeight) {AreaType = AreaType.Keep};
                Parallel.For(0, _imageHeight, y =>
                {
                    edgeStartCoordinates[y] = DetectEdge(input, y, overlay, _edgeColor, startCoordinate);
                }
                    );
                _pixelAreas.Add(edgeStartCoordinates);

                // Calculate how many pixels can theoretically be removed per line
                var removable = new PixelArea(_imageHeight) {AreaType = AreaType.Dummy};
                Parallel.For(0, _imageHeight, y =>
                {
                    removable[y] = CountRemovablePixels(input, y, edgeStartCoordinates[y]);
                }
                    );

                // Calculate the practical limit
                // We can only remove the same amount of pixels per line, otherwise we get a non-rectangular image
                minimum = removable.Minimum;
                Debug.WriteLine("Can remove {0} pixels", minimum);

                // Apply the practical limit: calculate the start coordinates of removable areas
                var removeStartCoordinates = new PixelArea(_imageHeight) { AreaType = AreaType.Remove };
                removeStartCoordinates.Width = minimum;
                for (int y = 0; y < _imageHeight; y++) removeStartCoordinates[y] = edgeStartCoordinates[y] - minimum;
                _pixelAreas.Add(removeStartCoordinates);

                // Paint the practical limit onto the overlay for demo purposes
                Parallel.For(0, _imageHeight, y =>
                {
                    PaintRemovableArea(y, overlay, indicatorColor, minimum, removeStartCoordinates[y]);
                }
                    );

                // Move the left edge before starting over
                startCoordinate = removeStartCoordinates.Minimum;
                var remaining = new PixelArea(_imageHeight) { AreaType = AreaType.Keep };
                for (int y = 0; y < _imageHeight; y++) remaining[y] = startCoordinate;
                _pixelAreas.Add(remaining);

                iteration++;
            } while (minimum > 1);

            input.GetBitmap(); // TODO HACK: release Lockbits on the original image
            return overlay.GetBitmap();
        }

        private Color GetIterationColor(int iteration)
        {
            return _iterationIndicatorColors[iteration%_iterationIndicatorColors.Count()];
        }

        /// <summary>
        /// Find a minimum number of contiguous pixels from the right side of the image. Everything behind that is an edge.
        /// </summary>
        /// <param name="input">Input image to get pixel data from</param>
        /// <param name="y">The row to be analyzed</param>
        /// <param name="output">Output overlay image to draw the edge on</param>
        /// <param name="edgeColor">Color for drawing the edge</param>
        /// <param name="startCoordinate">Start coordinate, defining the maximum X</param>
        /// <returns>X coordinate where the edge starts</returns>
        private int DetectEdge(FastBitmap input, int y, FastBitmap output, Color edgeColor, int startCoordinate)
        {
            var repeatCount = 0;
            var lastColor = Color.DodgerBlue;
            int x;

            for (x = startCoordinate; x >= 0; x--)
            {
                var currentColor = input.GetPixel(x, y);
                if (almostEquals(lastColor,currentColor))
                {
                    repeatCount++;
                }
                else
                {
                    lastColor = currentColor;
                    repeatCount = 0;
                    for (int i = x; i < startCoordinate; i++)
                    {
                        output.SetPixel(i,y,edgeColor);
                    }
                }

                if (repeatCount > _edgeThreshold)
                {
                    return x + _edgeThreshold;
                }
            }
            return repeatCount;
        }

        /// <summary>
        /// Counts the number of contiguous pixels in a row, starting on the right and going to the left
        /// </summary>
        /// <param name="input">Input image to get pixels from</param>
        /// <param name="y">The current row</param>
        /// <param name="startingCoordinate">X coordinate to start from</param>
        /// <returns>Number of equal pixels found</returns>
        private int CountRemovablePixels(FastBitmap input, int y, int startingCoordinate)
        {
            var lastColor = input.GetPixel(startingCoordinate, y);
            for (int x=startingCoordinate; x >= 0; x--)
            {
                var currentColor = input.GetPixel(x, y);
                if (!almostEquals(currentColor,lastColor))
                {
                    return startingCoordinate-x;
                }
            }
            return startingCoordinate;
        }

        /// <summary>
        /// Calculates color equality.
        /// Workaround for Windows XP screenshots which do not have 100% equal pixels.
        /// </summary>
        /// <returns>True if the RBG value is similar (maximum R+G+B difference is 8)</returns>
        private bool almostEquals(Color c1, Color c2)
        {
            int r = c1.R;
            int g = c1.G;
            int b = c1.B;
            int diff = (Math.Abs(r - c2.R) + Math.Abs(g - c2.G) + Math.Abs(b - c2.B));
            return (diff < 8) ;
        }

        /// <summary>
        /// Paint pixels that can be removed, starting at the X coordinate and painting to the right
        /// </summary>
        /// <param name="y">The current row</param>
        /// <param name="output">Overlay output image to draw on</param>
        /// <param name="removableColor">Color to use for drawing</param>
        /// <param name="width">Number of pixels that can be removed</param>
        /// <param name="start">Starting coordinate to begin drawing</param>
        private void PaintRemovableArea(int y, FastBitmap output, Color removableColor, int width, int start)
        {
            for(int i=start;i<start+width;i++)
            {
                output.SetPixel(i, y, removableColor);
            }
        }

        private readonly int _imageHeight;
        private readonly int _imageWidth;
        private List<PixelArea> _pixelAreas;

        public List<PixelArea> PixelAreas
        {
            get { return _pixelAreas; }
        }
    }
}

```

# Answer
> 1 votes
# Haskell, using naive removal of duplicate sequential lines

Unfortunately, this module only provides a function with the very generic type `Eq a => [[a]] -> [[a]]`, since I have no idea how to edit image files in Haskell, however, I'm certain it's possible to tranform a PNG image to a `[[Color]]` value and I'd imagine `instance Eq Color` to be easily definable.

The function in question is `resizeL`.

**Code:**

```
import Data.List

nubSequential []    = []
nubSequential (a:b) = a : g a b where
 g x (h:t)  | x == h =     g x t
            | x /= h = h : g h t
 g x []     = []

resizeL     = nubSequential . transpose . nubSequential . transpose

```

**Explanation:**

*Note:* `a : b` means *element* `a` prefixed to *list of type of `a`*, resulting in a list. This is the fundamental construction of lists. `[]` denotes the empty list.

*Note:* `a :: b` means `a` is of type `b`. For example, if `a :: k`, then `(a : []) :: [k]`, where `[x]` denotes a list containing things of type `x`.
This means that `(:)` itself, without any arguments, `:: a -> [a] -> [a]`. The `->` denotes a function from something to something.

The `import Data.List` simply gets some work some other people did for us and lets us use their functions without rewriting them.

First, define a function `nubSequential :: Eq a => [a] -> [a]`.
This function removes subsequent elements of a list that are identical.
So, `nubSequential [1, 2, 2, 3] === [1, 2, 3]`. **We will now abbreviate this function as `nS`.**

If `nS` is applied to an empty list, nothing can be done, and we simple return an empty list.

If `nS` is applied to a list with contents, then actual processing can be done. For this, we need a second function, here in a `where`-clause, to use recursion, as our `nS` doesn't keep track of an element to compare to.
We name this function `g`. It works by comparing its first argument to the head of the list it's been given, and discarding the head if they match and calling itself on the tail with the old first argument. If they don't, it appends the head onto the tail, passed through itself with the head as the new first argument.
To use `g`, we give it the head of the argument of `nS` and the tail as its two arguments.

`nS` is now of type `Eq a => [a] -> [a]`, taking a list and returning a list. It requires that we can check for equality between the elements as this is done in the function definition.

Then, we *compose* the functions `nS` and `transpose` using the `(.)` operator.
Composing functions means the following: `(f . g) x = f (g (x))`.

In our example, `transpose` rotates a table 90°, `nS` removes all sequential equal elements of the list, in this case other lists (that's what a table is), `transpose` rotates it back and `nS` again removes sequential equal elements. This is essentially removing subsequent duplicate rows an columns.

This is possible because if `a` is checkable for equality (`instance Eq a`), then `[a]` is, too.
In short: `instance Eq a => Eq [a]`

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


title: Print a Wavy String Line-by-Line

text:
# Question
Title: Print a Wavy String Line-by-Line
# Challenge

Write a program or function that takes in a string `s` and integer `n` as parameters. Your program should print (or return) the string when transformed as follows:

Starting in the top-left and moving down and to the right, write `s` as a wave of height `n`. Then, from top to bottom, combine each row as a string (without spaces).

# Example

Given the string "WATERMELON" and a height of 3:

The wave should look like this:

```
W   R   O
 A E M L N
  T   E

```

Then, combine the rows from top to bottom:

```
WRO
AEMLN
TE

```

So, your program should return the string "WROAEMLNTE"

Likewise, "WATERMELON" with height 4 should produce the following wave:

```
W     E
 A   M L
  T R   O
   E     N

```

Your program should then return the string "WEAMLTROEN"

# Rules

## Input

Input can be taken in any reasonable format. The string can be in any case you prefer. You may assume that `0 < n <= s.length`

## Output

Output should consist only of the transformed string (whether returned or printed to STDOUT), plus any trailing newlines.

## Scoring

This is , so shortest answer in bytes wins! Standard loopholes are not allowed.

# Test Cases

```
Input                        Output

programmingpuzzles, 5 ->     piermnlsomgzgapzru
codegolf, 3           ->     cgoeofdl
elephant, 4           ->     enlatehp
1234567, 3            ->     1524637
qwertyuiop, 1         ->     qwertyuiop

```

# Answer
# Husk, 6 bytes

```
δÖK…¢ḣ

```

Try it online!

Works for `n = 1` as well.

## Explanation

```
δÖK…¢ḣ  Implicit inputs, say n=4 and s="WATERMELON"
     ḣ  Range: [1,2,3,4]
    ¢   Cycle: [1,2,3,4,1,2,3,4,1,2,3,4..
   …    Rangify: [1,2,3,4,3,2,1,2,3,4,3,2..
δÖK     Sort s by this list: "WEAMLTROEN"
        Print implicitly.

```

The higher order function `δ` works like this under the hood. Suppose you have a higher order function that takes a unary function and a list, and returns a new list. For example, `Ö` takes a function and sorts a list using it as key. Then `δÖ` takes a binary function and two lists, zips the lists together, applies `Ö` to sort the pairs using the binary function as key, and finally projects the pairs to the second coordinate. We use `K` as the key function, which simply returns its first argument and ignores the second.
> 5 votes

# Answer
# MATL, 16 bytes

```
Zv3L)t?yn:)2$S}i

```

Try it online! Or verify all test cases.

### Explanation

Consider inputs `5`, `'programmingpuzzles'`.

```
Zv     % Input, implicit: number n. Symmetric range
       % STACK: [1 2 3 4 5 4 3 2 1]
3L     % Push [1 -1+1j]. When used as an index, this means 1:end-1
       % STACK: [1 2 3 4 5 4 3 2 1], [1 -1+1j]
)      % Index. Removes last element
       % STACK: [1 2 3 4 5 4 3 2]
t      % Duplicate
       % STACK: [1 2 3 4 5 4 3 2], [1 2 3 4 5 4 3 2]
?      %   If non-empty and non-zero
       %   STACK: [1 2 3 4 5 4 3 2]
  y    %   Implict input: string s. Duplicate from below
       %   STACK: 'programmingpuzzles', [1 2 3 4 5 4 3 2], 'programmingpuzzles'
  n    %   Number of elements
       %   STACK: 'programmingpuzzles', [1 2 3 4 5 4 3 2], 18
  :    %   Range
       %   STACK: 'programmingpuzzles', [1 2 3 4 5 4 3 2], [1 2 3 ··· 17 18]
  )    %   Index modularly
       %   STACK: 'programmingpuzzles', [1 2 3 4 5 4 3 2 1 2 3 4 5 4 3 2 1 2]
  2$S  %   Two-input sort: stably sorts first input as given by the second
       %   STACK: 'piermnlsomgzgapzru'
}      % Else. This branch is entered when n=1. The stack contains an empty array
       %   STACK: []
  i    %   Take input
       %   STACK: [], [], 'programmingpuzzles'
       % End, implicit
       % Display stack, implicit. Empty arrays are not displayed

```
> 6 votes

# Answer
# , 54, 29, 27 26 bytes

-1 byte thanks to hoosierEE

```
([\:#@[$[:}:|@i:@<:@]) ::[

```

Try it online!
> 5 votes

# Answer
# , 68 bytes

```
function(s,n)intToUtf8(unlist(split(utf8ToInt(s),-(n:(2.9-n)-1)^2)))

```

Try it online!

* -10 bytes thanks to @Giuseppe
* -17 bytes because I was silly
* -9 bytes and `n=1` case fixed thanks to @J.Doe
* -3 bytes thanks to @JayCe
> 5 votes

# Answer
# Haskell, 64 bytes

```
s#n=[c|m<-[0..n],(c,i)<-zip s.cycle$[0..n-1]++[n-2,n-3..1],i==m]

```

Try it online!
> 5 votes

# Answer
# Python 2, ~~119~~ ~~108~~ ~~98~~ ~~92~~ ~~91~~ ~~97~~ ~~93~~ ~~91~~ 90 bytes

```
lambda s,n:''.join(c*(j%(2*n-2or 1)in(i,2*n-i-2))for i in range(n)for j,c in enumerate(s))

```

Try it online!

<sub>-1 byte, thanks to Jonathan Frech</sub>
> 3 votes

# Answer
# 05AB1E (legacy), ~~11~~ 8 bytes

```
Σ²Lû¨¾è¼

```

Inspired by *@LuisMendo*'s MATL answer.
-3 bytes thanks to *@Adnan*

Try it online. (No test suite, because the legacy version of 05AB1E didn't had a reset for the `counter_variable`.)

**Explanation:**

```
Σ           # Sort the (implicit) input-string by:
 ²L         #  Create a list in the range [1, second input-integer]
            #   i.e. 5 → [1,2,3,4,5]
   û        #  Palindromize it
            #   i.e. [1,2,3,4,5] → [1,2,3,4,5,4,3,2,1]
    ¨       #  Remove the last item
            #   i.e. [1,2,3,4,5,4,3,2,1] → [1,2,3,4,5,4,3,2]
     ¾è     #  Index into it (with wraparound) using the counter_variable (default 0)
            #   i.e. counter_variable = 0 → 1
            #   i.e. counter_variable = 13 → 4
       ¼    #  And after every iteration, increase the counter_variable by 1

```

NOTE: The `counter_variable` is used, because in the Python Legacy version of 05AB1E, the `Σ` didn't had an index `N`, which it does have in the new Elixir rewrite version of 05AB1E. So why do I still use the Legacy version? Because in the Elixir rewrite it has a bug and doesn't sort for \\$n=1\\$, which would all result in an empty list `[]` after the indexing. All other test cases work as intended with `Σ²Lû¨Nè`: try it online, but the test case with \\$n=1\\$ times out without result, even with `--no-lazy` argument flag: try it online.
> 3 votes

# Answer
# Japt, 16 bytes

```
¬üÏu´VÑ aV°ÃÔc q

```

Test it online!

### Explanation

```
 ¬ üÏ   u´ VÑ  aV° Ã Ô c q
Uq üXY{Yu--V*2 aV++} w c q    Ungolfed
                               Implicit: U = input string, V = size of wave
Uq                             Split U into chars.
   üXY{            }           Group the items in U by the following key function:
       Y                         Take the index of the item.
        u--V*2                   Find its value modulo (V-1) * 2.
               aV++              Take the absolute difference between this and (V-1).
                                 This maps e.g. indices [0,1,2,3,4,5,6,7,...] with V=3 to
                                                        [2,1,0,1,2,1,0,1,...]
                                 The items are then grouped by these values, leading to
                                 [[2,6,...],[1,3,5,7,...],[0,4,...]].
                     w         Reverse the result, giving [[0,4,...],[1,3,5,7,...],[2,6,...]].
                       c       Flatten.
                         q     Join back into a single string.

```
> 2 votes

# Answer
# JavaScript (ES6), 75 bytes

*Shorter formula suggested by @MattH (-3 bytes)*

Takes input as `(string)(n)`.

```
s=>n=>--n?[...s].map((c,x)=>o[x=x/n&1?n-x%n:x%n]=[o[x]]+c,o=[])&&o.join``:s

```

Try it online!

---

# JavaScript (ES7), 78 bytes

*Saved 4 bytes thanks to @ETHproductions*

Takes input as `(string)(n)`.

```
s=>n=>--n?[...s].map((c,x)=>o[x=n*n-(x%(n*2)-n)**2]=[o[x]]+c,o=[])&&o.join``:s

```

Try it online!
> 2 votes

# Answer
# Jelly, 8 bytes

*6 byter fails for height 1; two bytes used to address it ...maybe a 7 can be found?*

```
ŒḄṖȯ1ṁỤị

```

A dyadic link accepting a positive integer and a list of characters which yields a list of characters.

**Try it online!**

### How?

```
ŒḄṖȯ1ṁỤị - Link: positive integer N; list of characters, T
ŒḄ       - bounce (implicit range of) N -> [1,2,3,...,N-1,N,N-1,...,3,2,1]
  Ṗ      - pop off the final entry         [1,2,3,...,N-1,N,N-1,...,3,2]
   ȯ1    - OR one                          if this is [] get 1 instead
     ṁ   - mould like T (trim or repeat to make this list the same length as T)
      Ụ  - grade-up (get indices ordered by value - e.g. [1,2,3,2,1,2] -> [1,5,2,4,6,3])
       ị - index into T

```
> 2 votes

# Answer
# K ( Kona ), 23 bytes

A translation of the J answer by Galen

```
{y@<(#y)#-1_(!x),|!x-1}

```
> 2 votes

# Answer
# MBASIC, ~~146~~ ~~159~~ 155 bytes

```
1 INPUT S$,N:DIM C$(N):P=1:D=1:FOR I=1 TO LEN(S$):C$(P)=C$(P)+MID$(S$,I,1)
2 IF N>1 THEN P=P+D
3 IF P=N OR P=1 THEN D=-D
4 NEXT:FOR I=1 TO N:PRINT C$(I);:NEXT

```

Updated to handle n=1

Output:

```
? programmingpuzzles, 5
piermnlsomgzgapzru

? codegolf, 3
cgoeofdl

? elephant, 4
enlatehp

? 1234567, 3
1524637

? WATERMELON, 4
WEAMLTROEN

? qwertyuiop, 1
qwertyuiop

```
> 1 votes

# Answer
# Perl 6, 49 bytes

```
->\n{*.comb.sort({-abs n-1-$++%(2*n-2||1)}).join}

```

Try it online!

Takes input as a curried function.

### Explanation:

```
->\n{*.comb.sort({-abs n-1-$++%(2*n-2||1)}).join}
->\n{                                           }  # Take an number
     *.comb        # Turn the string into a list of chars
           .sort({                       })   # And sort them by
                           $++    # The index of the char
                              %(2*n-2||1)  # Moduloed by 2*(n-1) or 1 if n is 0
                       n-1-       # Subtract that from n-1
                   abs            # get the absolute value
                  -               # And negate to reverse the list
                                          .join  # and join the characters

```

The sequence that it is sorted by looks like this (for `n=5`):

```
(-4 -3 -2 -1 0 -1 -2 -3 -4 -3 -2 -1 0 -1 -2 -3 -4 -3 -2 -1)

```
> 1 votes

# Answer
# , 24 bytes

```
4 :'x\:(#x)$}:|i:<:y'::[

```

Try it online!

Explicit dyadic verb. Run it like `'codegolf' f 3`.

### How it works

```
4 :'x\:(#x)$}:|i:<:y'::[    x: string, y: height
4 :                         Define a dyadic verb:
               i:<:y        Generate a range of -(y-1) .. y-1
            }:|             Take absolute value and remove last
       (#x)$             1) Repeat to match the string's length
    x\:                     Sort x by the decreasing order of above
                     ::[    If 1) causes `Length Error`, return the input string instead

```

Normally, explicit function takes additional 5 bytes in the form of `n :'...'`. But if error handling is added, the difference goes down to 2 bytes due to the parens and space in `(tacit)<space>::`.
> 1 votes

# Answer
# APL (Dyalog Classic), 23 bytes

```
{⍺[⍋(≢⍺)⍴(¯1↓⊢,1↓⌽)⍳⍵]}

```

Try it online!
> 1 votes

# Answer
# Powershell, ~~99~~ 95 bytes

```
param($s,$n)$r=,''*$n
$s|% t*y|%{$r[((1..$n+$n..1)*$s.Length|gu)[$i++*($n-gt1)]-1]+=$_}
-join$r

```

Test script:

```
$f = {

param($s,$n)$r=,''*$n
$s|% t*y|%{$r[((1..$n+$n..1)*$s.Length|gu)[$i++*($n-gt1)]-1]+=$_}
-join$r

}

@(
    ,("1234567", 3            ,     "1524637")
    ,("qwertyuiop", 1         ,     "qwertyuiop")
    ,("codegolf", 3           ,     "cgoeofdl")
    ,("elephant", 4           ,     "enlatehp")
    ,("programmingpuzzles", 5 ,     "piermnlsomgzgapzru")
) | % {
    $s,$n,$e = $_
    $r = &$f $s $n
    "$($r-eq$e): $r"
}

```

Output:

```
True: 1524637
True: qwertyuiop
True: cgoeofdl
True: enlatehp
True: piermnlsomgzgapzru

```

## Explanation

The script:

* creates an array of rows,
* fills rows with appropriate values,
* and returns the joined rows.

The expression `((1..$n+$n..1)*$s.Length|gu` generates a sequence like `1,2,3,3,2,1,1,2,3,3,2,1...` and removes adjacent duplicates. `gu` is alias for Get-Unique.

* For `$n=3` the deduplicated sequence is: `1,2,3,2,1,2,3,2,1...`
* For `$n=1` the deduplicated sequence is: `1`

The expression `$i++*($n-gt1)` returns an index in the deduplicated sequence. `=$i++` if `$n>1`, otherwise `=0`
> 1 votes

# Answer
# Ruby, ~~75~~ 65 bytes

```
->s,h{a=['']*h;x=-k=1;s.map{|c|a[x+=k=h-x<2?-1:x<1?1:k]+=c};a*''}

```

Try it online!

Takes input as an array of chars, returns string

How it wokrs:

* Create `h` strings
* For each character in the input string, decide which string to put it in based on its index (the index of the string to be modified goes up until `h` and then down until `0` and so on)
* Return all the strings joined together
> 1 votes

# Answer
# C, ~~142~~ 134 bytes

*8 bytes saved thanks to Jonathan Frech*

Code:

```
t;i;j;d;f(s,n)char*s;{for(t=strlen(s),i=0;i<n;i++)for(j=0;j+i<t;j=d+i+(n<2))d=j-i+2*~-n,putchar(s[i+j]),i>0&i<n-1&d<t&&putchar(s[d]);}

```

Explanation:

```
// C variable and function declaration magic
t;i;j;d;f(s,n)char*s;{
    // Iterate through each "row" of the string
    for(t=strlen(s),i=0;i<n;i++)
        // Iterate through each element on the row
        // Original index iterator here was j+=2*(n-1), which is a full "zig-zag" forward
        // The (n<2) is for the edge case of n==1, which will break the existing logic.
        for(j=0; j+i<t; j=d+i+(n<2))
            // If j+i is the "zig", d is the "zag": Original index was d=j+i+2*(n-i-1)
            // Two's complement swag here courtesy of Jonathan Frech
            d=j-i+2*~-n,
            putchar(s[i+j]),
            // Short circuit logic to write the "zag" character for the middle rows
            i>0 & i<n-1 & d<t && putchar(s[d]);
}

```

Try it online!
> 1 votes

# Answer
I have two solutions to the problem. The first solution I did first then I thought of another way to do it that I thought would save bytes but it didn't so I included it anyway.

---

# Solution 1

## PHP, ~~152~~ ~~144~~ 116 bytes

```
<?php
for($i=0;$i<$n=$argv[2];$i++)
    for($j=$i;$s=$argv[1][$j];$j+=$n<2|(($f=!$f|!$i)?$i<$n-1?$n+~$i:$i:$i)*2)
        echo $s;

```
* 8 bytes thanks to @JoKing
* 28 bytes thanks to @Shaggy

Try it online!

---

# Solution 2

## PHP, 162 bytes

```
<?php
$s=$argv[0];
$n=$argv[1];
$l=strlen($s);
for($i=0;$i<$l;){
    for($j=0;$j<$n&&$i<$l;)
        $a[$j++].=$s[$i++];
    for($j=$n-2;$j>0&&$i<$l;)
        $a[$j--].=$s[$i++];
}
echo join($a);

```

Try it online!
> 0 votes

# Answer
# Charcoal, 21 bytes

```
⭆ＮΦη¬⌊Ｅ²﹪⁺μ⎇νι±ι∨⊗⊖θ¹

```

Try it online! Link is to verbose version of code. Works by noting that indices \\$ m \\$ of the characters on line \\$ i \\$ satisfy the relation \\$ m \pm i = 0 \pmod {2n - 2} \\$. Explanation:

```
 Ｎ                      First input as a number
⭆                       Map over implicit range and join
   η                    Second input
  Φ                     Filter over characters
       ²                Literal 2
      Ｅ                 Map over implicit range
          μ             Character index
             ι ι        Outer index
              ±         Negate
            ν           Inner index
           ⎇            Ternary
         ⁺              Plus
                   θ    First input
                  ⊖     Decremented
                 ⊗      Doubled
                    ¹   Literal 1
                ∨       Logical Or
        ﹪               Modulo
     ⌊                  Minimum
    ¬                   Logical Not
                        Implicitly print

```
> 0 votes

# Answer
# SNOBOL4 (CSNOBOL4), 191 bytes

```
	S =INPUT
	N =INPUT
	A =ARRAY(N)
	A<1> =EQ(N,1) S	:S(O)
I	I =I + -1 ^ D
	S LEN(1) . X REM . S	:F(O)
	A<I> =A<I> X
	D =EQ(I,N) 1
	D =EQ(I * D,1)	:(I)
O	Y =Y + 1
	O =O A<Y>	:S(O)
	OUTPUT =O
END

```

Try it online!

Takes `S` then `N` on separate lines.

### Explanation:

```
	S =INPUT			;* read S
	N =INPUT			;* read N
	A =ARRAY(N)			;* create array of size N
	A<1> =EQ(N,1) S	:S(O)		;* if N = 1, set A<1> to S and jump to O
I	I =I + -1 ^ D			;* index into I by I + (-1)^D (D starts as '' == 0)
	S LEN(1) . X REM . S	:F(O)	;* extract the first character as X and set S to the
					;* remaining characters, jumping to O when S is empty
	A<I> =A<I> X			;* set A<I> to A<I> concatenated with X
	D =EQ(I,N) 1			;* if I == N, D=1
	D =EQ(I * D,1)	:(I)		;* if I == D == 1, D = 0. Goto I
O	Y =Y + 1			;* increment the counter
	O =O A<Y>	:S(O)		;* concatenate the array contents until last cell
	OUTPUT =O			;* and print
END

```
> 0 votes

# Answer
# Clean, ~~105~~ 84 bytes

```
import StdEnv,Data.List
$s n=[c\\l<-[1..n],c<-s&m<-cycle([1..n]++[n-1,n-2..2])|m==l]

```

Try it online!
> 0 votes

# Answer
# JavaScript (Node.js), 83 bytes

```
c=>g=(s,d=c*2-2,r=d,n=o='')=>s&&([...s].map((c,i)=>i%d%r?n+=c:o+=c),o)+g(n,r-1,r-2)

```

Try it online!
> 0 votes

# Answer
# Pyth, ~~22~~ 21 bytes

```
|seMhD,V*lz+PUQP_UQzz

```

Takes input as `n` followed by `s` on separate lines. Try it online here, or verify all the test cases at once here.

```
|seMhD,V*lz+PUQP_UQzz   Implicit: Q=eval(input()), z=remaining input

             UQ         Range [0-Q)
            P           All but last from the above
                         e.g. for Q=3, yields [0,1]
               P_UQ     All but last of reversed range
                         e.g. for Q=3, yields [2,1]
           +            Concatenate the previous two results
                          e.g. for Q=3, yields [0,1,2,1]
        *lz              Repeat len(z) times
      ,V           z    Vectorised pair the above with z, truncating longer to length of shorter
                          e.g. for Q=3, z=WATERMELON, yields:
                          [[0,'W'],[1,'A'],[2,'T'],[1,'E'],[0,'R'],[1,'M'],[2,'E'],[1,'L'],[0,'O'],[1,'N']]
    hD                  Sort the above by the first element
                          Note this is a stable sort, so relative ordering between equal keys is preserved
  eM                    Take the last element of each
 s                      Concatenate into string
                          Note that if n=1, the result of the above will be 0 (sum of empty array)
|                   z   If result of above is falsey, yield z instead

```

*Edit: saved a byte by moving the empty check to the end of processing. Previous version:* `seMhD,V*lz|+PUQP_UQ]0z`
> 0 votes

# Answer
# Red, 153 bytes

```
func[s n][i: v: m: 1 b: collect[foreach c s[keep/only reduce[v i c]v: v + m
if all[n > 1(i: i + 1)%(n - 1)= 1][m: -1 * m]]]foreach k sort b[prin last k]]

```

Try it online!

## Explanation:

```
f: func [ s n ] [                      ; s is the string, n is the height
    i: 1                               ; index of the current character in the string
    v: 1                               ; value of the "ladder"
    m: 1                               ; step (1 or -1)
    b: collect [                       ; collect the values in a block b
        foreach c s [                  ; foreach character in the string
            keep/only reduce [ v i c ] ; keep a block of the evaluated [value index char]
            i: i + 1                   ; increase the index
            v: v + m                   ; calculate the value
            if all [ n > 1             ; if height is greater than 1 and
                    i % (n - 1) = 1    ; we are at a pick/bottom of the ladder
                   ]
                [ m: -1 * m ]          ; reverse the step
        ]
    ]
    foreach k sort b [ prin last k ]   ; print the characters in the sorted block of blocks
]

```
> 0 votes

# Answer
# Ruby, 84 bytes

```
->s,n{r=['']*n;[*0...n,*(2-n)..-1].map{|x|r[x.abs]+=s.slice!(0)||''}while s[0];r*''}

```

Try it online!
> 0 votes

---
Tags: code-golf, string
---


title: Simplified Train Set

text:
# Question
Title: Simplified Train Set
Many different types of train set exist, ranging from wooden tracks like Brio, to fully digital control perfect tiny metal replicas of real trains, but they all require a track to be designed, ideally using as many of your pieces as possible.

So, your task is to determine whether, given input of the available pieces, it is possible to build a complete closed circuit using all of the elements, and if not, how many pieces will be left from the maximum possible circuit.

Since this is a simplified train set, there are only 3 elements: big curve, little curve, and straight. These are all based on a square grid:

* "Big Curve" is a 90 degree corner, covering 2 units in each dimension
* "Little Curve" is a 90 degree corner, covering one unit in each direction
* "Straight" is a straight element, 1 unit long

This means that the minimum circuit possible is formed of 4 little curves - it's a circle, of radius 1 unit. This can be extended by adding pairs of straight elements to form various ovals. There are other circuits possible by adding more curves, or by mixing the types of curve.

This train set doesn't include any junctions, or methods for tracks to cross, so it's not valid for two elements to connect to the same end of an other element (no Y formations) or to cross over one another (no X formations). Additionally, it's a train set, so any formation which doesn't allow a train to pass isn't valid: examples include straights meeting at 90 degree angles (there must always be a curve between perpendicular straights) and curves meeting at 90 degree angles (curves must flow).

You also want to use as many pieces as possible, ignoring what type they are, so you'll always opt for a circuit which has more bits in. Finally, you only have one train, so any solution which results in multiple circuits is unacceptable.

## Input

Either an array of three integers, all greater than or equal to 0, corresponding to the number of big curves, little curves, and straights available, or parameters passed to your program, in the same order.

## Output

A number corresponding to the number of pieces left over when the maximum possible circuit for the elements provided is constructed.

## Test data

```
Minimal circuit using big curves
Input: [4,0,0]
Output: 0

Slightly more complicated circuit
Input: [3,1,2]
Output: 0

Incomplete circuit - can't join
Input: [3,0,0]
Output: 3

Incomplete circuit - can't join
Input: [3,1,1]
Output: 5

Circuit where big curves share a centre
Input: [2,2,0]
Output: 0

Bigger circuit
Input: [2,6,4]
Output: 0

Circuit where both concave and convex curves required
Input: [8,0,0] or [0,8,0]
Output: 0

Circuit with left over bit
Input: [5,0,0] or [0,5,0]
Output: 1

```

## Notes

* 2 straights and a little curve are equivalent to a big curve, but use more pieces, so are preferred - should never be a situation where this combination is left, if there are any big curves in the circuit
* 4 little curves can usually be swapped for 4 straights, but not if this would cause the circuit to intersect itself
* The train set is also idealised - the track elements take up the widths shown, so it is valid for curves to pass through a single grid square without intersecting, in some cases. The grid just defines the element dimensions. In particular, two big curves can be placed so that the grid square at the top left of the example diagram would also be the bottom right square of another big curve running from left to top (with the diagram showing one running from right to bottom)
* A small curve can fit in the empty space under a big curve (bottom right grid square above). A second big curve could also use that space, shifted one across and one down from the first
* A small curve cannot fit on the same grid space as the outside of a big curve - mostly because there is no way to connect to it which doesn't intersect illegally

# Answer
# \[JavaScript (Node.js)\], 1220 bytes

```
f=r=>{var a=[{n:0,d:[[0,-1,"0000000101011"],[1,-1,"0011111111111"],[0,0,"0111101111111"],[1,0,"1100010000000"]],e:[2,-1,1]},{n:0,d:[[-1,-1,"1001111111111"],[0,-1,"0000010010110"],[-1,0,"0110000100000"],[0,0,"1101111011111"]],e:[-2,-1,3]},{n:1,d:[[0,0,"0011101111111"]],e:[1,0,1]},{n:1,d:[[0,0,"1001111011111"]],e:[-1,0,3]},{n:2,d:[[0,0,"1111101011111"]],e:[0,-1,0]}],e=r=>{var a=r.d,e=r.e,n=[];return a.forEach(r=>{var a=r[2];n.push([-r[1],r[0],""+a[10]+a[5]+a[0]+a[8]+a[3]+a[11]+a[6]+a[1]+a[9]+a[4]+a[12]+a[7]+a[2]])}),{d:n,e:[-e[1],e[0],e[2]]}};i=((r,a)=>{for(var n=0;n<r.d;n++,a=e(a));var p=!1;return a.d.forEach(a=>{var e=r[`${r.p.x+a[0]},${r.p.y+a[1]}`];void 0===e&&(e="00000000000000");for(var n="",d=0;d<13;d++)"1"===e[d]&&"1"===a[2][d]&&(p=!0),n+=e[d]===a[2][d]?e[d]:"1";r[`${r.p.x+a[0]},${r.p.y+a[1]}`]=n}),r.p.x+=a.e[0],r.p.y+=a.e[1],r.d=(r.d+a.e[2])%4,!p});var n=[],p=(r,e)=>{a.forEach(a=>{var d=Object.assign({},r);if(d.p=Object.assign({},r.p),!(e[a.n]<=0)&&i(d,a)){if(d.ps+=a.n,0==d.p.x&&0==d.p.y&&0==d.d)return void n.push(d);var s=Object.assign([],e);s[a.n]-=1,p(d,s)}})};p({p:{x:0,y:0},d:0,ps:""},Object.assign([],r));var d=0;n.forEach(r=>{r.ps.length>d&&(d=r.ps.length)}),console.log(r[0]+r[1]+r[2]-d)};

```

Try it online!

Note: The input is actually the variable q at the start. \[2,6,4\] will also take quite a bit of time as this is a brute force solution without optimizations.

I actually did this because it hasn't been answered in over a year and I was just kinda curious if it was possible.

---

Original Code:

```
var q = [4, 2, 4];
var t = [
    {
        n: 0,
        d: [
            [0, -1, "0000000101011"],
            [1, -1, "0011111111111"],
            [0, 0, "0111101111111"],
            [1, 0, "1100010000000"]
        ],
        e: [2, -1, 1],

    },
    {
        n: 0,
        d: [
            [-1, -1, "1001111111111"],
            [0, -1, "0000010010110"],
            [-1, 0, "0110000100000"],
            [0, 0, "1101111011111"]
        ],
        e: [-2, -1, 3]
    },
    {
        n: 1,
        d: [
            [0, 0, "0011101111111"]
        ],
        e: [1, 0, 1]
    },
    {
        n: 1,
        d: [
            [0, 0, "1001111011111"]
        ],
        e: [-1, 0, 3]
    },
    {
        n: 2,
        d: [
            [0, 0, "1111101011111"]
        ],
        e: [0, -1, 0]
    },
];

r = (p) => {
    var d = p.d; var e = p.e; var o = [];
    d.forEach(i => {
        var d = i[2];
        o.push([-i[1], i[0], "" + d[10] + d[5] + d[0] + d[8] + d[3] + d[11] + d[6] + d[1] + d[9] + d[4] + d[12] + d[7] + d[2]])
    });
    return { d: o, e: [-e[1], e[0], e[2]] };
};

i = (g, p) => {
    //console.log(g.p, g.d);
    for (var i = 0; i < g.d; i++ , p = r(p));
    var c = false;
    p.d.forEach(d => {
        var v = g[`${g.p.x + d[0]},${g.p.y + d[1]}`];
        if (v === undefined) v = "00000000000000";
        var o = "";
        for (var i = 0; i < 13; i++) {
            if (v[i] === '1' && d[2][i] === '1')
                c = true;
            o += (v[i] === d[2][i]) ? v[i] : '1';
        }
        //console.log(o);
        g[`${g.p.x + d[0]},${g.p.y + d[1]}`] = o;
    });
    g.p.x += p.e[0];
    g.p.y += p.e[1];
    g.d = (g.d + p.e[2]) % 4;
    return !c;
};

var l = [];
var re = (g, p) => {
    t.forEach(piece => {
        var gr = Object.assign({}, g);
        gr.p = Object.assign({}, g.p);
        if (p[piece.n] <= 0)
            return;
        if (i(gr, piece)) {
            gr.ps += piece.n;
            if (gr.p.x == 0 && gr.p.y == 0 && gr.d == 0) {
                l.push(gr);
                return;
            }
            var ti = Object.assign([], p);
            ti[piece.n] -= 1;
            re(gr, ti);
        }
    });
};
var gr = { p: { x: 0, y: 0 }, d: 0, ps: "" };
re(gr, Object.assign([], q));

var c = 0;
var lo = 0;
l.forEach(g => {
    if (g.ps.length > lo) {
        require("./draw.js")(g, `outs/out${c++}.png`)
        lo = g.ps.length;
    }
});

console.log(q[0] + q[1] + q[2] - lo);

```

first I should include a graphic of the tiles I used.

```
The sections of this tile were given a number and
used for comparison and overlap handling later.

So there first thing is the array t at the start.
This is a collection of track pieces that contain
    n[ame]: the index of the input array.
    d[ata]: the offset from the current tile and the Tile bit values.
    e[nd]: the relative offset and rotation that the piece provides.

function r[otate] ( p[iece] )
    this outputs a piece that is rotated by 90 degrees
    by rearranging the tile bits and the end offset

function i[nsert] ( g[rid], p[iece] )
    this modifies the passed in grid trying to place down each tile of the piece.
    if it hits a point where 2 tiles intersect it sets a flag c[ollision]
    it then adjusts the current p[osition] and and d[irection] stored in the grid.
    then it returns !c[ollision]

function re[peat] ( g[rid], p[eices] )
    this iterates across all nodes which
        creates a copy of the g[rid] as gr[id].
        checks if the piece is available if not continue
        if the peice is added without a collision
            add piece name to gr[id].ps[piece string];
            it checks if its back at the start
                add gr[id] to l[ist]
                return as no more pieces can be added without a collision.
            clone peices remove the used peice ti[nput]
            call re[peate] (gr[id], ti[nput])

call re[peate] with empty grid

search l[ist] for longest piece string
and output input added together minus the length of the longest string.

```

Sorry if the write up is hard to read I'm not used to explaining how my code works.

P.S. I actually also made a few functions for drawing the maps to a png but of course those were remove to save at least some space.
> 9 votes

---
Tags: code-golf
---


# Question
Title: Describe a 2D Bitmap Using Filled Rectangle Mapping
**Idea:**

Consider a 2-bit bitmap of arbitrary side-lengths overlaid on a coordinate grid and imaged with random data (1's represent an element of the image, 0's represent the "blank" canvas background):

```
y x—0 2 4 6 8 10  14  18
|
0   0000000000111100000000
    0000000011111110000000
2   0000111111111111000000
    0000011111111111000000
4   0000000000000000000000
    1111111000000000011111
6   1111111111100000000011
    1111111111111111000000

```

Next, consider how the rasterized image may be described using a series of drawn, solid rectangles. Example:

```
    0 2 4 6 8 101214161820

0   0000000000111100000000
    0000000011111110000000
2   0000111111111111000000
    0000011111111111000000
4   0000000000000000000000
    xxxxxxx000000000011111
6   xxxxxxx111100000000011
    xxxxxxx111111111000000

```

The x's describe a region of the bitmap that may be described using a solid rectangle. Finally, consider how that rectangular section of the image can be described under the X-Y coordinate system by two of its vertices in the format:

```
{x0,y0,x1,y1}

```

In this case,

```
{0,5,6,7}

```

describes the example rectangular section.

**Challenge:** Design a program which receives a 2D matrix containing bitmap data and outputs a concatenated list of rectangle coordinates.

**Restrictions:**

The output, when processed by remapping (plotting using 1's) the rectangles back onto a blank coordinate canvas (a canvas of all 0's) of the same side-length dimensions, should yield exactly the input matrix.

The output should be a concatenated list of all computed rectangles, no extraneous parsing characters or structures distinguishing one set of coordinates from another. The list will be read top-down, ordering will be inferred given that each rectangle requires only two coordinates to be described.

**Example I/O:**

(Do mind that this example in no way presents the ideal output, however, it is a valid output.)

Input 2D matrix:

```
0000000000111100000000
0000000011111110000000
0000111111111111000000
0000011111111111000000
0000000000000000000000
1111111000000000011111
1111111111100000000011
1111111111111111000000

```

Output concatenated list:

```
{10,0,13,3,8,1,9,3,5,2,7,3,4,2,4,2,14,1,14,3,15,2,15,3,0,5,6,7,7,6,10,7,11,7,15,7,17,5,21,5,20,6,21,6}

```

**Efficiency score:**

Programs will be ranked by their average-case efficiency using this resource (or one which functions identically) to generate pseudorandom, 2-bit, 20x20 matrices. Determine the average-case efficiency by calculating the arithmetic mean of the output lengths of at least 10 iterations (sum of the lengths divided by the number of iterations). The lesser the average length of the output, the greater the efficiency.

# Answer
> 1 votes
# Python 3 + Z3, optimal, 51.19 ± 0.10 rectangles

(Random 20×20 bitmaps with \\$\frac17\\$ probability of 0, average of 10000 cases, 95% confidence interval.)

```
import sys
import z3

bitmap = [list(map(int, line)) for line in sys.stdin.read().splitlines()]
height = len(bitmap)
width = len(bitmap[0])
rects = set()
for y0 in reversed(range(height)):
    for x0 in reversed(range(width)):
        x2 = width - 1
        for y1 in range(y0, height):
            if bitmap[y1][x0] != 1:
                break
            x1 = x0
            while x1 < x2 and bitmap[y1][x1 + 1] == 1:
                x1 += 1
            rects.discard((x0 + 1, y0, x1, y1))
            rects.discard((x0, y0 + 1, x1, y1))
            rects.discard((x0, y0, x1, y1 - 1))
            rects.add((x0, y0, x1, y1))
            x2 = x1
cover = {
    (x, y): [] for y in range(height) for x in range(width) if bitmap[y][x] == 1
}
use = {}
for x0, y0, x1, y1 in rects:
    u = use[x0, y0, x1, y1] = z3.Bool(f"use{x0}_{y0}_{x1}_{y1}")
    for y in range(y0, y1 + 1):
        for x in range(x0, x1 + 1):
            cover[x, y].append(u)
solver = z3.Optimize()
solver.add([z3.Or(c) for c in cover.values()])
solver.minimize(z3.Sum([z3.If(u, 1, 0) for u in use.values()]))
assert solver.check() != z3.unsat
model = solver.model()
print(sum((list(rect) for rect, u in use.items() if z3.is_true(model[u])), []))

```

# Answer
> 2 votes
# Rust

Try it online

Average case num rectangles: **57.9054** (10000 iterations of 20x20 matrices, with 1/7 probability of "0")

Solution to example input: `{10,0,13,3,8,1,14,3,4,2,15,2,5,3,15,3,0,5,6,7,17,5,21,5,0,6,10,7,20,6,21,6,0,7,15,7}`

The algorithm is pretty simple: for each horizontal line of 1s, use that as the top side of a rectangle, extend this rectangle down while possible, and if it covers some previously uncovered area, add it to the list. This assumes rectangles can overlap. I have not verified whether the output is always correct, but the example input looks ok. The output was verified against the input for 10000 iterations, and it looks correct.

The code includes a benchmark function to calculate the score, and a function to draw the result. The input can be changed in the main function.

```
extern crate rand;
use rand::{Rng, thread_rng};

#[derive(Copy, Clone, Debug)]
struct Rect {
    x0: usize,
    y0: usize,
    x1: usize,
    y1: usize
}

impl Rect {
    fn contains_xslice(&self, xa: usize, xb: usize) -> bool {
        self.x0 <= xa && xb <= self.x1
    }
    fn contains(&self, r: &Rect) -> bool {
        // r is completely inside of self
        self.x0 <= r.x0 && r.x1 <= self.x1 && self.y0 <= r.y0 && r.y1 <= self.y1
    }
}

fn display_rects(r: &[Rect]) -> String {
    let s = r.iter()
        .map(|z| format!("{},{},{},{}", z.x0, z.y0, z.x1, z.y1))
        .collect::<Vec<_>>()
        .join(",");

    // transform 1,1 into {1,1}
    format!("{{{}}}", s)
}

fn draw_rects(r: &[Rect], w: usize, h: usize) -> String {
    let mut s = format!("");
    for y in 0..h {
        for x in 0..w {
            let p = Rect { x0: x, x1: x, y0: y, y1: y };
            if r.iter().any(|a| a.contains(&p)) {
                s.push_str("1");
            } else {
                s.push_str("0");
            }
        }
        s.push_str("\n");
    }
    s
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct Matrix {
    v: Vec<u8>,
    size: (usize, usize),
}

impl Matrix {
    fn new(w: usize, h: usize) -> Self {
        Self {
            v: vec![0; w*h],
            size: (w, h),
        }
    }
    fn from_str(s: &str) -> Self {
        let mut v = vec![];
        let mut w = None;
        let mut h = 0;
        for l in s.lines() {
            h += 1;
            let mut tw = 0;
            for c in l.chars() {
                tw += 1;
                let x = match c {
                    '0' => 0,
                    '1' => 1,
                    a => panic!("Invalid input! {:?} at {},{}", a, tw, h),
                };
                v.push(x);
            }
            if let Some(ww) = w {
                if tw != ww {
                    panic!("All lines must have the same width! {} != {}", tw, ww);
                }
            } else {
                w = Some(tw);
            }
        }

        let w = w.unwrap_or(0);

        Matrix {
            v,
            size: (w, h),
        }
    }
    fn random(w: usize, h: usize) -> Self {
        let mut rng = thread_rng();
        let mut v = vec![];

        for _ in 0..w*h {
            let n = rng.gen_range(0, 6+1);
            let x = if n == 0 { 0 } else { 1 };
            v.push(x);
        }

        Matrix {
            v,
            size: (w, h),
        }
    }
    fn get(&self, x: usize, y: usize) -> u8 {
        self.v[y * self.size.0 + x]
    }
    fn hline(&self, y: usize) -> &[u8] {
        &self.v[y * self.size.0 .. (y + 1) * self.size.0]
    }
    fn hline_1_pieces(&self, y: usize) -> Vec<Rect> {
        let mut r = vec![];
        let line = self.hline(y);
        let xmax = self.size.0 - 1;
        let y0 = y;
        let y1 = y;
        let mut lineit = line.iter();
        let mut xoff = 0;
        while lineit.len() > 0 {
            // Find first non-zero pixel
            if let Some(x0) = lineit.position(|&x| x != 0) {
                let x0 = xoff + x0;
                // x0..x1 is a line of 11111
                let x1 = x0 + lineit.position(|&x| x == 0).unwrap_or(xmax - x0);
                r.push(Rect { x0, x1, y0, y1 });
                // Remember offset because the iterator is being consumed
                xoff = x1 + 2;
            }
        }

        r
    }
    fn rectangles(&self) -> Vec<Rect> {
        let mut r: Vec<Rect> = vec![];
        let ymax = self.size.1 - 1;
        // For each hline, add rectangles covering the maximum width possible
        let hpieces: Vec<Vec<Rect>> = (0..self.size.1).map(|i| self.hline_1_pieces(i)).collect();
        // Extend each rectangle down while possible
        for (y0, layer) in hpieces.iter().enumerate() {
            for rect in layer {
                let mut y = y0 + 1;
                while y <= ymax {
                    if hpieces[y].iter().any(|&r| r.contains_xslice(rect.x0, rect.x1)) {
                        y += 1;
                    } else {
                        break;
                    }
                }
                let y1 = y - 1;
                let rn = Rect { y1, ..*rect };
                if r.iter().any(|&r1| r1.contains(&rn)) {
                    // An equivalent rectangle is already in the vec
                } else {
                    // This rectangle covers some new area, push it
                    r.push(rn);
                }
            }
        }

        r
    }
}

fn benchmark(iterations: usize) -> f64 {
    let mut sum = 0;
    for _ in 0..iterations {
        let m = Matrix::random(20, 20);
        let r = m.rectangles();
        let output = draw_rects(&m.rectangles(), 20, 20);
        assert_eq!(m, Matrix::from_str(&output));
        sum += r.len();
    }
    sum as f64 / iterations as f64
}

fn main() {
    let input = "\
0000000000111100000000
0000000011111110000000
0000111111111111000000
0000011111111111000000
0000000000000000000000
1111111000000000011111
1111111111100000000011
1111111111111111000000
";
    let m = Matrix::from_str(input);
    assert_eq!(input, draw_rects(&m.rectangles(), 22, 8));
    println!("{}", display_rects(&m.rectangles()));
    println!("{}", benchmark(10000));
}

```

---
Tags: code-challenge, algorithm
---


title: One line Keyboard

text:
# Question
Title: One line Keyboard
**The Challenge**

The goal of this challenge is to determine whether a given String can be typed using only one line of a standard UK QWERTY keyboard.

This is `code golf`, so shortest solution in bytes wins!

---

**IO**

Input will be a single String of zero or more characters in the ASCII decimal range of 32-126 inclusive. You may assume for this challenge that an empty String requires no typing and thus can be typed using a single line.

You may take the input as a String, list of characters, or equivalent form for your language.

Output should be a truthy value for any String that can be typed using a single line, or falsey for one that cannot.

---

**Keyboard layout**

To clarify any ambiguity over what the standard keyboard layout is below is a list of keys available on each line, including alternate upper keys (accessed using shift).

* *Line 1*
    + Standard: ``1234567890-=`
* *Line 2*
    + Standard: `qwertyuiop[]`
* *Line 3*
    + Standard: `asdfghjkl;'#`
    + Uppercase: `ASDFGHJKL`
    + Special: Caps Lock
* *Line 4*
    + Standard: `\zxcvbnm,./`
    + Alternate: `|<>?`
    + Uppercase: `ZXCVBNM`
    + Special: Shift
* *Line 5*
    + Special: Space Bar

Alternate upper keys can only be pressed if Shift is also on the same line, and uppercase keys can only be accessed through Caps Lock or Shift. You really can only use one keyboard line!

---

**Test cases**
```
            -> true     (empty string)
45-2=43     -> true     (line 1)
qwerty      -> true     (line 2)
tryitout    -> true     (line 2)
Qwerty      -> false    (no shift or caps on line 2)
#sad        -> true     (line 3)
AsDf        -> true     (caps lock used)
@sDF        -> false    (no shift for alternate upper)
zxcvbn?     -> true     (line 4)
zxc vbn     -> false    (spacebar on separate line)
123abc      -> false    (multiple lines)
            -> true     (just space bar)
!!!         -> false    (exclamation marks cannot be printed by a single line)

```

# Answer
# Python 2, ~~130~~ ~~123~~ ~~121~~ 115 bytes

```
lambda s:any(set(s)<=set(l+l.lower())for l in["`1234567890-=","eqwrtyuiop[]","ASDFGHJKL;'#","ZXCVBNM\,./|<>?"," "])

```

Try it online!

---

# Python 3, 111 bytes

```
lambda s:any({*s}<={*l+l.lower()}for l in["`1234567890-=","eqwrtyuiop[]","ASDFGHJKL;'#","ZXCVBNM\,./|<>?"," "])

```

Try it online!

<sub>-4 bytes, thanks to nedla2004</sub>
> 12 votes

# Answer
# Retina 0.8.2, ~~72~~ 71 bytes

```
`^([-=\d`]+|[][eio-rtuwy]+|(?i)[adfghjkls;'#]+|[\\bcnmvxz,./|<>?]+| *)$

```

Try it online! Explanation: Each alternation matches a different row of the keyboard. The `(?i)` in the middle of the pattern causes the entire rest of the pattern to be matched case-insensitively. Edit: Saved 1 byte thanks to @KirillL.
> 9 votes

# Answer
# 05AB1E, ~~66~~ 47 bytes

```
žh…`-=«žS„[]«žTDu…;'#««žUDu"\,./|<>?"««ð)εISåP}O

```

Takes the input as a list of characters.

-19 bytes thanks to *@Emigna*. Completely forgot we had qwerty-keyboard constant builtins. :D

Try it online or verify all test cases.

**Explanation:**

```
žh                # Push "0123456789"
  …`-=            # Push "`-="
      «           # Merge them together
žS                # Push "qwertyuiop"
  „[]             # Push "[]"
     «            # Merge them togeter
žT                # Push "asdfghjkl"
  Du              # Duplicate, and toUppercase the copy
    …;'#          # Push ";'#"
        ««        # Merge all three together
žU                # Push "zxcvbnm"
  Du              # Duplicate, and toUppercase the copy
    "\,./|<>?"    # Push "\,./|<>?"
              ««  # Merge all three together
ð                 # Push a space
 )                # Wrap all string in an array
  ε   }           # Map each to:
   I              #  Take the input (list of characters)
    å             #  Check for each if it's in the current string of the map-iteration
     P            #  Take the product (1 if all are truthy, 0 otherwise)
       O          # Take the sum (either 1 or 0, so truthy/falsey), and output implicitly

```
> 8 votes

# Answer
# Perl 5 `-pl`, 76 bytes

```
$_=/^( *|[\d`=-]+|[][wetyuio-r]+|(?i)[asdfghjkl;'#]+|[\\\/zxcvbnm,.|<>?]+)$/

```

Try it online!

The obvious regex approach.
> 8 votes

# Answer
# Ruby `-n`, ~~86~~ 81 bytes

```
p /^( *|[\d`=-]+|[\]\[wetyuio-r]+|(?i)[asdfghjkl;'#]+|[\\\/zxcvbnm,.|<>?]+)$/?1:0

```

Try it online!
> 6 votes

# Answer
# JavaScript (Node.js), ~~99~~ ~~98~~ 95 bytes

```
x=>/^([-`=\d]+|[wetyuio-r[\]]+)$/.test(x)|/^([asdfghjkl;'#]+|[zxcvbnm,./<>?\\|]+| *)$/i.test(x)

```

Try it online!

-1 from the comment by @Kirill L. in the Retina answer.
-3 thanks @Ismael Miguel and @Arnauld for their combined effort.
> 5 votes

# Answer
# Perl 6, ~~102 101~~ 100 bytes

*-1 byte thanks to nwellnhof!*

```
->\a{max map {a.comb⊆comb $_~.lc:},|<eqwrtyuiop[] ASDFGHJKL;'# ZXCVBNM\,./|<>?>,' ',"`-="~[~] ^10}

```

Try it online!

Pretty standard implementation. There's probably a shorter regex based solution to this, but I don't know Perl 6's regex well enough to make an attempt.
> 5 votes

# Answer
# Java 10, ~~209~~ 208 bytes

```
s->{int l=0,t;for(var p:s){t=p.matches("[[0-9]`\\-=]")?1:"qwertyuiop[]".contains(p)?2:p.matches("(?i)[asdfghjkl;'#]")?3:"\\zxcvbnm,./|<>?ZXCVBNM".contains(p)?4:p.equals(" ")?5:9;l=l<1?t:l!=t?9:l;}return l<6;}

```

-1 byte thanks to *@TFeld*.

Try it online.

**Explanation:**

```
s->{                    // Method with String-array parameter and boolean return-type
  int l=0,              //  Line-integer, starting at 0
      t;                //  Temp integer
  for(var p:s){         //  Loop over the characters
    t=p.matches("[[0-9]`\\-=]")?
                        //   If it's a character from the first line:
       1                //    Set `t` to 1
      :"qwertyuiop[]".contains(p)?
                        //   Else-if it's a character from the second line:
       2                //    Set `t` to 2
      :p.matches("(?i)[asdfghjkl;'#]")?
                        //   Else-if it's a character from the third line
       3                //    Set `t` to 3
      :"\\zxcvbnm,./|<>?ZXCVBNM".contains(p)?
                        //   Else-if it's a character from the fourth line:
       4                //    Set `t` to 4
      :p.equals(" ")?   //   Else-if it's a space from the fifth line:
       5                //    Set `t` to 5
      :                 //   Else (invalid character):
       9;               //    Set `t` to 9
    l=l<1?              //   If `l` is still 0:
       t                //    Set it to `t`
      :l!=t?            //   Else-if `t` is a different line than `l`:
       9                //    Set `l` to 9 (non-existing line)
      :                 //   Else (`t` is the same line as `l`):
       l;}              //    Leave `l` the same
  return l<6;}          //  Return whether `l` is not 9

```
> 4 votes

# Answer
# Powershell, 87 bytes

*Port of Neil's Retina regex.*

```
"$args"-cmatch"^([-=\d``]+|[][eio-rtuwy]+|(?i)[adfghjkls;'#]+|[\\bcnmvxz,./|<>?]+| *)$"

```
> 4 votes

# Answer
# Jelly, 55 bytes

```
ØDW;Øq;Œu$€3,4¦;"“rɠ3“Ż²“¿µ|“aƲƘ0ÞḅzḂ»⁶ṭ
¢f€ẈṠSỊafƑ¢F¤$

```

Try it online!

The first line yields a list of the keyboard lines and the second one checks whether the program input is contained on a single (or zero) lines and that there are no characters that can't be typed (like `QWE!@#`).
> 4 votes

# Answer
# , 150 bytes

```
x;f(char*s){for(x=0;*s;x|="@               "[*s++-32]);return!(x&x-1);}

```

Try it online!

It won't win any prizes, but this is a fun approach: we map characters on the five rows of the keyboard to `4 8 16 32 64`, and every invalid character to `3`. We bitwise OR the value for each character in the string together, and check if the result satisfies `x&(x-1) == 0`, which is true when `x` is a power of 2 or zero, i.e. whenever `x` has at most one bit set.
> 3 votes

# Answer
# LUA, 282 262 259 270 bytes

```
s=io.read()l=0
t=0
for c in s:gmatch"."do
f=c.find
t=f(c,"[0-9%`-=]")or 0|(f(c,"[qwertyuiop%[%]]")or 0)*2|(f(c,"[aAsSdDfFgGhHjJkKlL:'@#~]")or 0)*4|(f(c,"[\\zxcvbnm,./|<>?ZXCVBNM]")or 0)*8|(f(c," ")or 0)*16
t=t==0 and 17or t
l=l<1 and t or l~=t and 17or l
end
print(l<17)

```

Try it online!
> 2 votes

# Answer
# PHP, 98 bytes

I´m a little sad that there´s nothing shorter than regex. It´s probably not the fastest solution.

```
<?=preg_match("%^([`\d=-]*|[wetyuio-r[\]]*|(?i)[asdfghjkl;'#]*|[\\\zxcvbnm,./|<>?]*| *)$%",$argn);

```

Run as pipe with `-F` or try it online.

---

Shortest non-regex solution I found (124 bytes; linebreak and tab for reading convenience):

```
foreach(["`1234567890-=","qwertyuiop[]","asdfghjkl;'#ASDFGHJKL","zxcvbnm,./\|<>?ZXCVBNM"," "]as$d)
    trim($argn,$d)>""||die(1);

```

exits with code `1` for truthy, `0` for falsy. Run as pipe with `-R`.
Requires PHP 5.4 or later; for older PHP, use `array(...)` instead of `[...]` (+5 bytes)
or use these 123 bytes with `-nR` in PHP \<7:

```
foreach(split(_,"`1234567890-=_qwertyuiop[]_asdfghjkl;'#ASDFGHJKL_zxcvbnm,./\|<>?ZXCVBNM_ ")as$d)
    trim($argn,$d)>""||die(1);

```
> 2 votes

# Answer
# AWK, ~~163~~ ~~119~~ 113 bytes

This is an AWK answer, returns a numeric 1 string for true, 0 string for false. (Written as AWK invoke as awk -f file for interactive use.)

```
{print/^[-`1234567890=]*$/||/^[]qwertyuiop\[]*$/||/^[asdfghjkl;'#ASDFGHJKL]*$/||/^[zxcvbnm,.\/\|<>?ZXCVBNM]*$/||/^ *$/}

```

Try it online!

However, does not handle TAB character as written (trivial extension) as not part of spec.
> 2 votes

# Answer
# Bash, 119 bytes

Includes an echo to provide "readable" output. If you put a suitable wrapper of shell (your choice) around it to include print/output, then you can save 8 bytes. My reading of the challenge suggests the solution should output a suitable output indication so I stick with 119 bytes.

```
[[ "$@" =~ ^[asdfghjklASDFGHJKL\;\'#]*$|^[-\`0-9=]+$|^[]qwertyuiop\[]*$|^[zxcvbnm,./\|\<\>\?ZXCVBNM]*$|^\ *$ ]];echo $?

```

Try it online!
> 1 votes

---
Tags: code-golf, string, decision-problem, keyboard
---