title: Patch the Paragraph

text:
# Question
Title: Patch the Paragraph
*In the spirit of Patch the Image, here's a similar challenge but with text.*

## Challenge

Bit rot has afflicted your precious text! Given a paragraph composed of ASCII characters, with a rectangular hole somewhere in it, your program should try to fill in the hole with appropriate text, so that the paragraph blends as best as possible.

## Further definitions

* The hole will always be rectangular, and it may span multiple lines.
* There will only ever be one hole.
* Note that the hole does not necessarily fall on word boundaries (in fact, it usually won't).
* The hole will be at most 25% of the input paragraph, but may overlap or extend past the "end" of the "normal" text (see the Euclid or Badger examples below).
* Since finding the hole is not the main point of this challenge, it will be composed solely of hash marks `#` to allow for easy identification.
* No other location in the input paragraph will have a hash mark.
* Your code cannot use the "normal" text in the examples below - it will only receive and process the text with the hole in it.
* The input can be as a single multi-line string, as an array of strings (one element per line), as a file, etc. -- your choice of what is most convenient for your language.
* If desired, an optional additional input detailing the coordinates of the hole can be taken (e.g., a tuple of coordinates or the like).
* Please describe your algorithm in your submission.

## Voting

Voters are asked to judge the entries based on how well the algorithm fills in the text hole. Some suggestions include the following:

* Does the filled in area match the approximate distribution of spaces and punctuation as the rest of the paragraph?
* Does the filled in area introduce faulty syntax? (e.g., two spaces in a row, a period followed by a question mark, an erroneous sequence like `, ,`, etc.)
* If you squint your eyes (so you're not actually reading the text), can you see where the hole used to be?
* If there aren't any CamelCase words outside the hole, does the hole contain any? If there aren't any Capitalized Letters outside the hole, does the hole contain any? If There Are A Lot Of Capitalized Letters Outside The Hole, does the hole contain a proportionate amount?

## Validity Criterion

In order for a submission to be considered valid, it must not alter any text of the paragraph outside of the hole (including trailing spaces). A single trailing newline at the very end is optional.

## Test Cases

Format is original paragraph in a code block, followed by the same paragraph with a hole. The paragraphs with the hole will be used for input.

1 (Patch the Image)

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

In a popular image editing software there is a feature, that patches (The term
used in image processing is inpainting as @minxomat pointed out.) a selected
area of an image, #############information outside of that patch. And it does a
quite good job, co#############is just a program. As a human, you can sometimes
see that something#############t if you squeeze your eyes or just take a short
glance, the patch seems to fill in the gap quite well.

```

2 (Gettysburg Address)

```
But, in a larger sense, we can not dedicate, we can not consecrate, we can not
hallow this ground. The brave men, living and dead, who struggled here, have
consecrated it, far above our poor power to add or detract. The world will
little note, nor long remember what we say here, but it can never forget what
they did here. It is for us the living, rather, to be dedicated here to the
unfinished work which they who fought here have thus far so nobly advanced. It
is rather for us to be here dedicated to the great task remaining before us-
that from these honored dead we take increased devotion to that cause for which
they gave the last full measure of devotion-that we here highly resolve that
these dead shall not have died in vain-that this nation, under God, shall have
a new birth of freedom-and that government of the people, by the people, for
the people, shall not perish from the earth.

But, in a larger sense, we can not dedicate, we can not consecrate, we can not
hallow this ground. The brave men, living and dead, who struggled here, have
consecrated it, far above our poor power to add or detract. The world will
little note, nor long remember what we say here, but it can never forget what
they did here. It is for us the living, rather, to be dedicated here to the
unfinished work which they who fought here h######################advanced. It
is rather for us to be here dedicated to the######################before us-
that from these honored dead we take increas######################use for which
they gave the last full measure of devotion-######################solve that
these dead shall not have died in vain-that ######################, shall have
a new birth of freedom-and that government of the people, by the people, for
the people, shall not perish from the earth.

```

3 (Lorem Ipsum)

```
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit
in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur
sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt
mollit anim id est laborum.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo conse################irure dolor in reprehenderit
in voluptate velit esse cil################giat nulla pariatur. Excepteur
sint occaecat cupidatat non################in culpa qui officia deserunt
mollit anim id est laborum.

```

4 (Jabberwocky)

```
'Twas brillig, and the slithy toves
Did gyre and gimble in the wabe;
All mimsy were the borogoves,
And the mome raths outgrabe.

'Twas brillig, and the slithy toves
Did gyre a######### in the wabe;
All mimsy #########borogoves,
And the mome raths outgrabe.

```

5 (Euclid's proof of the Pythagorean Theorem)

```
1.Let ACB be a right-angled triangle with right angle CAB.
2.On each of the sides BC, AB, and CA, squares are drawn,
CBDE, BAGF, and ACIH, in that order. The construction of
squares requires the immediately preceding theorems in Euclid,
and depends upon the parallel postulate. [footnote 14]
3.From A, draw a line parallel to BD and CE. It will
perpendicularly intersect BC and DE at K and L, respectively.
4.Join CF and AD, to form the triangles BCF and BDA.
5.Angles CAB and BAG are both right angles; therefore C, A,
and G are collinear. Similarly for B, A, and H.
6.Angles CBD and FBA are both right angles; therefore angle ABD
equals angle FBC, since both are the sum of a right angle and angle ABC.
7.Since AB is equal to FB and BD is equal to BC, triangle ABD
must be congruent to triangle FBC.
8.Since A-K-L is a straight line, parallel to BD, then rectangle
BDLK has twice the area of triangle ABD because they share the base
BD and have the same altitude BK, i.e., a line normal to their common
base, connecting the parallel lines BD and AL. (lemma 2)
9.Since C is collinear with A and G, square BAGF must be twice in area
to triangle FBC.
10.Therefore, rectangle BDLK must have the same area as square BAGF = AB^2.
11.Similarly, it can be shown that rectangle CKLE must have the same
area as square ACIH = AC^2.
12.Adding these two results, AB^2 + AC^2 = BD × BK + KL × KC
13.Since BD = KL, BD × BK + KL × KC = BD(BK + KC) = BD × BC
14.Therefore, AB^2 + AC^2 = BC^2, since CBDE is a square.

1.Let ACB be a right-angled triangle with right angle CAB.
2.On each of the sides BC, AB, and CA, squares are drawn,
CBDE, BAGF, and ACIH, in that order. The construction of
squares requires the immediately preceding theorems in Euclid,
and depends upon the parallel postulate. [footnote 14]
3.From A, draw a line parallel to BD and CE. It will
perpendicularly intersect BC and DE at K and L, respectively.
4.Join CF and AD, to form the triangles BCF and BDA.
5.Angles CAB and BAG are both right angles; therefore C, A,
and G are #############milarly for B, A, and H.
6.Angles C#############e both right angles; therefore angle ABD
equals ang############# both are the sum of a right angle and angle ABC.
7.Since AB#############FB and BD is equal to BC, triangle ABD
must be co#############iangle FBC.
8.Since A-#############ight line, parallel to BD, then rectangle
BDLK has t############# of triangle ABD because they share the base
BD and hav#############titude BK, i.e., a line normal to their common
base, conn#############rallel lines BD and AL. (lemma 2)
9.Since C #############with A and G, square BAGF must be twice in area
to triangl#############
10.Therefo############# BDLK must have the same area as square BAGF = AB^2.
11.Similar############# shown that rectangle CKLE must have the same
area as square ACIH = AC^2.
12.Adding these two results, AB^2 + AC^2 = BD × BK + KL × KC
13.Since BD = KL, BD × BK + KL × KC = BD(BK + KC) = BD × BC
14.Therefore, AB^2 + AC^2 = BC^2, since CBDE is a square.

```

6 (Badger, Badger, Badger by weebl)

```
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!

Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger##################badger, badger,
badger##################badger, badger
Mushro##################
Badger##################badger, badger,
badger##################badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!

```

# Answer
# Python 2

I know that @atlasologist already posted a solution in Python 2, but the way my works is a bit different. This works by going through all holes, from top to bottom, left to right, looking 5 characters back and at the character above, and finding a character where these matches. If multiple characters are found, it picks the most common one. In case there are no characters found, it removes the above-character restriction. If there are still no characters found, it decreases the amount of characters it looks back, and repeats.

```
def fix(paragraph, holeChar = "#"):
    lines = paragraph.split("\n")
    maxLineWidth = max(map(len, lines))
    lines = [list(line + " " * (maxLineWidth - len(line))) for line in lines]
    holes = filter(lambda pos: lines[pos[0]][pos[1]] == holeChar, [[y, x] for x in range(maxLineWidth) for y in range(len(lines))])

    n = 0
    for hole in holes:
        for i in range(min(hole[1], 5), 0, -1):
            currCh = lines[hole[0]][hole[1]]
            over = lines[hole[0] - 1][hole[1]]
            left = lines[hole[0]][hole[1] - i : hole[1]]

            same = []
            almost = []
            for y, line in enumerate(lines):
                for x, ch in enumerate(line):
                    if ch == holeChar:
                        continue
                    if ch == left[-1] == " ":
                        continue
                    chOver = lines[y - 1][x]
                    chLeft = lines[y][x - i : x]
                    if chOver == over and chLeft == left:
                        same.append(ch)
                    if chLeft == left:
                        almost.append(ch)
            sortFunc = lambda x, lst: lst.count(x) / (paragraph.count(x) + 10) + lst.count(x)
            if same:
                newCh = sorted(same, key=lambda x: sortFunc(x, same))[-1]
            elif almost:
                newCh = sorted(almost, key=lambda x: sortFunc(x, almost))[-1]
            else:
                continue
            lines[hole[0]][hole[1]] = newCh
            break

    return "\n".join(map("".join, lines))

```

Here's the result of Badger, Badger, Badger:

```
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a- b
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!

```

Here's the result from the proof:

```
1.Let ACB be a right-angled triangle with right angle CAB.
2.On each of the sides BC, AB, and CA, squares are drawn,
CBDE, BAGF, and ACIH, in that order. The construction of
squares requires the immediately preceding theorems in Euclid,
and depends upon the parallel postulate. [footnote 14]
3.From A, draw a line parallel to BD and CE. It will
perpendicularly intersect BC and DE at K and L, respectively.
4.Join CF and AD, to form the triangles BCF and BDA.
5.Angles CAB and BAG are both right angles; therefore C, A,
and G are the same areamilarly for B, A, and H.
6.Angles CAB and CA, sqe both right angles; therefore angle ABD
equals angle ABD becaus both are the sum of a right angle and angle ABC.
7.Since ABD because theFB and BD is equal to BC, triangle ABD
must be construction ofiangle FBC.
8.Since A-angle ABD becight line, parallel to BD, then rectangle
BDLK has the same area  of triangle ABD because they share the base
BD and have the base thtitude BK, i.e., a line normal to their common
base, conngle and G, sqrallel lines BD and AL. (lemma 2)
9.Since C = BD × BK + with A and G, square BAGF must be twice in area
to triangle FBC. (lemma
10.Therefore angle and  BDLK must have the same area as square BAGF = AB^2.
11.Similarly for B, A,  shown that rectangle CKLE must have the same
area as square ACIH = AC^2.
12.Adding these two results, AB^2 + AC^2 = BD × BK + KL × KC
13.Since BD = KL, BD × BK + KL × KC = BD(BK + KC) = BD × BC
14.Therefore, AB^2 + AC^2 = BC^2, since CBDE is a square.

```

And the result of Jabberwocky:

```
'Twas brillig, and the slithy toves
Did gyre and the mo in the wabe;
All mimsy toves, anborogoves,
And the mome raths outgrabe.

```
> 15 votes

# Answer
## Python 2

This is a pretty straight-forward solution. It creates a sample string composed of words that are between average word length `A`-(`A`/2) and `A`+(`A`/2), then it applies leading and trailing space trimmed chunks from the sample to the patch area. It doesn't handle capitalization, and I'm sure there's a curveball test case out there that would break it, but it does okay on the examples. See the link below to run all the tests.

I also put a patch in the code for good measure.

```
def patch(paragraph):
    sample = [x.split() for x in paragraph if x.count('#') < 1]
    length = max([x.count('#') for x in paragraph if x.find('#')])
    s = sum(####################
    sample,[####################
    ])      ####################
    avg=sum(####################
    len(w)  ####################
    for w in####################
    s)//len(s)
    avg_range = range(avg-(avg//2),avg+(avg//2))
    sample = filter(lambda x:len(x) in avg_range, s)
    height=0
    for line in paragraph:
        if line.find('#'):height+=1
        print line.replace('#'*length,' '.join(sample)[(height-1)*length:height*length].strip())
    print '\n'

```

Lorem Ipsum, original then patched:

```
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit
in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur
sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt
mollit anim id est laborum.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo conseore dolore magnairure dolor in reprehenderit
in voluptate velit esse cilenim minim quisgiat nulla pariatur. Excepteur
sint occaecat cupidatat nonnisi mollit aniin culpa qui officia deserunt
mollit anim id est laborum.

```

Try it
> 5 votes

# Answer
# Java Shakespeare

Who needs a grasp of standard english conventions? Just make your own! Just like the bard was allowed to make up his own words. This bot doesn't worry to much about correcting the cut off words, he really just inserts random words. The result is some beautiful Poetry. As a bonus feature the bard is of a higher caliber and can handle multiple holes provided they are the same size!

---

Sample Input
```
 From fairest creatures we desire increase,
  That thereby beauty's rose might never die,
  But as the riper should by time decease,
  His tender############bear his memory:
  But thou c############ thine own bright eyes,
  Feed'st th############ame with self-substantial fuel,
  Making a famine where abundance lies,
  Thy self thy foe, to thy sweet self too cruel:
  Thou that art now the world's fresh ornament,
  And only herald to the gaudy spring,
  Within thine own bud buriest thy content,
  And tender churl mak'st was############ding:
    Pity the world, or else t############be,
    To eat the world's due, b############and thee.

                     2
  When forty winters shall besiege thy brow,
  And dig deep trenches in thy beauty's field,
  Thy youth's proud livery so gazed on now,
  Will be a tattered weed of small worth held:
  Then being asked, where all thy beauty lies,
  Where all the treasure of thy lusty days;
  To say within thine own deep sunken eyes,
  Were an all-eating shame, and thriftless praise.
  How much more praise deserved thy beauty's use,
  If thou couldst answer 'This fair child of mine
  Shall sum my count, and make my old excuse'
  Proving his beauty by succession thine.
    This were to be new made when thou art old,
    And see thy blood warm when thou feel'st it cold.

                     3
  Look in thy glass and tell the face thou viewest,
  Now is the time that face should form another,
  Whose fresh repair if now thou not renewest,
  Thou dost beguile the world, unbless some mother.
  For where is she so fair whose uneared womb
  Disdains the tillage of thy husbandry?
  Or who is he so fond will be the tomb,
  Of his self-love to stop posterity?
  Thou art thy mother's glass and she in thee
  Calls back the lovely April of her prime,
  So thou through windows of thine age shalt see,
  Despite of ############s thy golden time.
    But if th############mbered not to be,
    Die singl############image dies with thee.

```

Beautiful output

```
 From fairest creatures we desire increase,
  That thereby beauty's rose might never die,
  But as the riper should by time decease,
  His tender should of bear his memory:
  But thou c all mbered  thine own bright eyes,
  Feed'st th Proving Or ame with self-substantial fuel,
  Making a famine where abundance lies,
  Thy self thy foe, to thy sweet self too cruel:
  Thou that art now the world's fresh ornament,
  And only herald to the gaudy spring,
  Within thine own bud buriest thy content,
  And tender churl mak'st was he Thou my ding:
    Pity the world, or else t So the the be,
    To eat the world's due, b t thine so and thee.

                     2
  When forty winters shall besiege thy brow,
  And dig deep trenches in thy beauty's field,
  Thy youth's proud livery so gazed on now,
  Will be a tattered weed of small worth held:
  Then being asked, where all thy beauty lies,
  Where all the treasure of thy lusty days;
  To say within thine own deep sunken eyes,
  Were an all-eating shame, and thriftless praise.
  How much more praise deserved thy beauty's use,
  If thou couldst answer 'This fair child of mine
  Shall sum my count, and make my old excuse'
  Proving his beauty by succession thine.
    This were to be new made when thou art old,
    And see thy blood warm when thou feel'st it cold.

                     3
  Look in thy glass and tell the face thou viewest,
  Now is the time that face should form another,
  Whose fresh repair if now thou not renewest,
  Thou dost beguile the world, unbless some mother.
  For where is she so fair whose uneared womb
  Disdains the tillage of thy husbandry?
  Or who is he so fond will be the tomb,
  Of his self-love to stop posterity?
  Thou art thy mother's glass and she in thee
  Calls back the lovely April of her prime,
  So thou through windows of thine age shalt see,
  Despite of  Look gazed s thy golden time.
    But if th When be, mbered not to be,
    Die singl repair the image dies with thee.

```

The last couple lines are deeply poetic if I do say so myself. It performs suprisingly well on the gettysburg address as well.

```
But, in a larger sense, we can not dedicate, we can not consecrate, we can not
hallow this ground. The brave men, living and dead, who struggled here, have
consecrated it, far above our poor power to add or detract. The world will
little note, nor long remember what we say here, but it can never forget what
they did here. It is for us the living, rather, to be dedicated here to the
unfinished work which they who fought here h to of rather us of advanced. It
is rather for us to be here dedicated to the who be it, vain who before us
that from these honored dead we take increas be dead the the what use for which
they gave the last full measure of devotion  dead government The solve that
these dead shall not have died in vain that  the take nor world , shall have
a new birth of freedom and that government of the people, by the people, for
the people, shall not perish from the earth.

```

---

Lets see what makes Shakespeare tick. Here is the code. Essentially he strives to build a vocabulary base from the input. He then uses these words and randomly places them in the hole (ensuring that it fits nicely). He is deterministic as he uses a fixed seed for randomness.
```
package stuff;

import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;

/**
 *
 * @author rohan
 */
public class PatchTheParagraph {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("File Name :");
        String[] text = getWordsFromFile(in.nextLine());
System.out.println("==ORIGINAL==");
        for(String s:text){
    System.out.println(s);
}
                    int lengthOfHole= 0;
        int rows = 0;
            for(String s: text){
                s = s.replaceAll("[^#]", "");

//      System.out.println(s);
                if(s.length()>0){
                    lengthOfHole = s.length();
                rows++;
                }
            }
            ArrayList<String> words = new ArrayList<>();
            words.add("I");
            for(String s:text){
                String[] w = s.replaceAll("#", " ").split(" ");
for(String a :w){
    words.add(a);
            }

            }
                        Iterator<String> j = words.iterator();
            while(j.hasNext()){
                String o;
                if((o = j.next()).equals("")){
                    j.remove();
                }
            }
            System.out.println(words);
            Stack<String> out = new Stack<>();
            String hashRow = "";
            for(int i = 0;i<lengthOfHole;i++){
                hashRow+="#";
            }

        for(int i = 0;i<rows;i++){
            int length = lengthOfHole-1;
            String outPut = " ";
            while(length>2){
String wordAttempt = words.get(getRandom(words.size()-1));
while(wordAttempt.length()>length-1){
 wordAttempt = words.get(getRandom(words.size()-1));
}
length -= wordAttempt.length()+1;
            outPut+=wordAttempt;
                outPut+=" ";
            }
        out.push(outPut);
    }
System.out.println("==PATCHED==");
        for(String s : text){
            if(s.contains(hashRow)){
                System.out.println(s.replaceAll(hashRow,out.pop()));
            }else{
                System.out.println(s);
            }
        }
                                    }
public static final Random r = new Random(42);
    public static int getRandom(int max){
    return (int) (max*r.nextDouble());
}
    /**
     *
     * @param fileName is the path to the file or just the name if it is local
     * @return the number of lines in fileName
     */
    public static int getLengthOfFile(String fileName) {
        int length = 0;
        try {
            File textFile = new File(fileName);
            Scanner sc = new Scanner(textFile);
            while (sc.hasNextLine()) {
                sc.nextLine();
                length++;
            }
        } catch (Exception e) {
System.err.println(e);
        }
        return length;
    }

    /**
     *
     * @param fileName is the path to the file or just the name if it is local
     * @return an array of Strings where each string is one line from the file
     * fileName.
     */
    public static String[] getWordsFromFile(String fileName) {
        int lengthOfFile = getLengthOfFile(fileName);
        String[] wordBank = new String[lengthOfFile];
        int i = 0;
        try {
            File textFile = new File(fileName);
            Scanner sc = new Scanner(textFile);
            for (i = 0; i < lengthOfFile; i++) {
                wordBank[i] = sc.nextLine();
            }
            return wordBank;
        } catch (Exception e) {
            System.err.println(e);
            System.exit(55);
        }
        return null;
    }
}

```

---

Most of Shakespeare's poetry is public domain.
> 4 votes

# Answer
## Python 2.7

Another Python solution with a different approach. My program sees the text as a Markov chain, where each letter is followed by another letter with a certain probability. So the first step is to build the table of probabilities. The next step is to apply that probabilities to the patch.

Full code, including one sample text is below. Because one example used unicode characters, I included an explicit codepage (utf-8) for compatibility with that example.

```
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict
import numpy

texts = [
"""'Twas brillig, and the slithy toves
Did gyre a######### in the wabe;
All mimsy #########borogoves,
And the mome raths outgrabe."""
]

class Patcher:
    def __init__(self):
        self.mapper = defaultdict(lambda: defaultdict(int))

    def add_mapping(self, from_value, to_value):
        self.mapper[from_value][to_value] += 1

    def get_patch(self, from_value):
        if from_value in self.mapper:
            sum_freq = sum(self.mapper[from_value].values())
            return numpy.random.choice(
                self.mapper[from_value].keys(),
                p = numpy.array(
                    self.mapper[from_value].values(),dtype=numpy.float64) / sum_freq)
        else:
            return None

def add_text_mappings(text_string, patcher = Patcher(), ignore_characters = ''):
    previous_letter = text_string[0]
    for letter in text_string[1:]:
        if not letter in ignore_characters:
            patcher.add_mapping(previous_letter, letter)
            previous_letter = letter
    patcher.add_mapping(text_string[-1], '\n')

def patch_text(text_string, patcher, patch_characters = '#'):
    result = previous_letter = text_string[0]
    for letter in text_string[1:]:
        if letter in patch_characters:
            result += patcher.get_patch(previous_letter)
        else:
            result += letter
        previous_letter = result[-1]
    return result

def main():
    for text in texts:
        patcher = Patcher()
        add_text_mappings(text, patcher, '#')
        print patch_text(text, patcher, '#')
        print "\n"

if __name__ == '__main__':
    main()

```

Sample output for the Lorem Ipsum:

```
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo conse Exe eut ccadamairure dolor in reprehenderit
in voluptate velit esse cilore indipserexepgiat nulla pariatur. Excepteur
sint occaecat cupidatat non upir alostat adin culpa qui officia deserunt
mollit anim id est laborum.

```

An extra poetic line in the Jabberwocky:

```
'Twas brillig, and the slithy toves
Did gyre and me the in the wabe;
All mimsy was
An inborogoves,
And the mome raths outgrabe.

```
> 3 votes

# Answer
# C# 5 *massive as ever*

I threw this together, it's a bit of a mess, but it produces some OK results some of the time. It a mostly-deterministic algorithm, but with some (fixed-seed) randomness added to avoid it producing the same string for similar gaps. It goes to some effort to try to avoid just having columns of spaces either side of the gaps.

It works by tokenizing the input into words and punctuation (punctuation comes from a manually entered list, because I can't be bothered to work out if Unicode can do this for me), so that it can put spaces before words, and not before punctuation, because this is fairly typical. It splits on typical whitespace. In the vein of markov chains (I think), it counts how often each token follows each other token, and then *doesn't* compute probabilities for this (I figure that because the documents are so tiny, we would do better to bias toward things we see a lot where we can). Then we perform a breadth-first search, filling the space left by the hashes and the 'partial' words either side, with the cost being computed as `-fabness(last, cur) * len(cur_with_space)`, where `fabness` returns the number of times `cur` has followed `last` for each appended token in the generated string. Naturally, we try to minimise the cost. Because we can't always fill the gap with words and punctuation found in the document, it also considers a number of 'special' tokens from certain states, including the partial strings on either side, which we bias against with arbitrarily increased costs.

If the BFS fails to find a solution, then we naively try to pick a random adverb, or just insert spaces to fill the space.

## Results

All 6 can be found here: https://gist.github.com/anonymous/5277db726d3f9bdd950b173b19fec82a

The Euclid test-case did not go very well...

Patch the Image

```
In a popular image editing software there is a feature, that patches (The term
used in image processing is inpainting as @minxomat pointed out.) a selected
area of an image, that patches information outside of that patch. And it does a
quite good job, co the patch a is just a program. As a human, you can sometimes
see that something In a short it if you squeeze your eyes or just take a short
glance, the patch seems to fill in the gap quite well.

```

Jabberwocky

```
'Twas brillig, and the slithy toves
Did gyre and the in in the wabe;
All mimsy the mome borogoves,
And the mome raths outgrabe.

```

Badger

```
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, badger, badger
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!

```

\_I'm glad with how this one turned out... it's fortuate that "badger, badger," fits, or this one would not have done so well

## Code

Run it with

```
csc ParaPatch.cs
ParaPatch.exe infile outfile

```

There is quite a lot of it. The only remotely interesting bit is the `Fill` method. I include the heap implementation, because .NET doesn't have one (WHY MS WHY?!).

```
using System;
using System.Collections.Generic;
using System.Linq;

namespace ParaPatch
{
    class Program
    {
        private static string[] Filler = new string[] { "may", "will", "maybe", "rather", "perhaps", "reliably", "nineword?", "definitely", "elevenword?", "inexplicably" }; // adverbs
        private static char[] Breaking = new char[] { ' ', '\n', '\r', '\t' };
        private static char[] Punctuation = new char[] { ',', '.', '{', '}', '(', ')', '/', '?', ':', ';', '\'', '\\', '"', ',', '!', '-', '+', '[', ']', '£', '$', '%', '^', '—' };

        private static IEnumerable<string> TokenizeStream(System.IO.StreamReader reader)
        {
            System.Text.StringBuilder sb = new System.Text.StringBuilder();

            HashSet<char> breaking = new HashSet<char>(Breaking);
            HashSet<char> punctuation = new HashSet<char>(Punctuation);

            while (!reader.EndOfStream)
            {
                int ci = reader.Read();
                if (ci == -1) // sanity
                    break;

                char c = (char)ci;

                if (breaking.Contains(c))
                {
                    if (sb.Length > 0)
                        yield return sb.ToString();
                    sb.Clear();
                }
                else if (punctuation.Contains(c))
                {
                    if (sb.Length > 0)
                        yield return sb.ToString();
                    yield return ""+c;
                    sb.Clear();
                }
                else
                {

                    sb.Append(c);
                }
            }

            if (sb.Length > 0)
                yield return sb.ToString();
        }

        private enum DocTokenTypes
        {
            Known,
            LeftPartial,
            RightPartial,
            Unknown,
        }

        private class DocToken
        {
            public DocTokenTypes TokenType { get; private set; }
            public string StringPart { get; private set; }
            public int Length { get; private set; }

            public DocToken(DocTokenTypes tokenType, string stringPart, int length)
            {
                TokenType = tokenType;
                StringPart = stringPart;
                Length = length;
            }
        }

        private static IEnumerable<DocToken> DocumentTokens(IEnumerable<string> tokens)
        {
            foreach (string token in tokens)
            {
                if (token.Contains("#"))
                {
                    int l = token.IndexOf("#");
                    int r = token.LastIndexOf("#");

                    if (l > 0)
                        yield return new DocToken(DocTokenTypes.LeftPartial, token.Substring(0, l), l);

                    yield return new DocToken(DocTokenTypes.Unknown, null, r - l + 1);

                    if (r < token.Length - 1)
                        yield return new DocToken(DocTokenTypes.RightPartial, token.Substring(r + 1), token.Length - r - 1);
                }
                else
                    yield return new DocToken(DocTokenTypes.Known, token, token.Length);
            }
        }

        private class State : IComparable<State>
        {
            // missing readonly params already... maybe C#6 isn't so bad
            public int Remaining { get; private set; }
            public int Position { get; private set; }
            public State Prev { get; private set; }
            public string Token { get; private set; }
            public double H { get; private set; }
            public double Fabness { get; private set; }
            public string FullFilling { get; private set; }

            public State(int remaining, int position, Program.State prev, double fabness, double h, string token, string toAdd)
            {
                Remaining = remaining;
                Position = position;
                Prev = prev;
                H = h;
                Fabness = fabness;
                Token = token;

                FullFilling = prev != null ? prev.FullFilling + toAdd : toAdd;
            }

            public int CompareTo(State other)
            {
                return H.CompareTo(other.H);
            }
        }

        public static void Main(string[] args)
        {
            if (args.Length < 2)
                args = new string[] { "test.txt", "testout.txt" };

            List<DocToken> document;
            using (System.IO.StreamReader reader = new System.IO.StreamReader(args[0], System.Text.Encoding.UTF8))
            {
                document = DocumentTokens(TokenizeStream(reader)).ToList();
            }

            foreach (DocToken cur in document)
            {
                Console.WriteLine(cur.StringPart + " " + cur.TokenType);
            }

            // these are small docs, don't bother with more than 1 ply
            Dictionary<string, Dictionary<string, int>> FollowCounts = new Dictionary<string, Dictionary<string, int>>();
            Dictionary<string, Dictionary<string, int>> PreceedCounts = new Dictionary<string, Dictionary<string, int>>(); // mirror (might be useful)

            HashSet<string> knowns = new HashSet<string>(); // useful to have lying around

            // build counts
            DocToken last = null;
            foreach (DocToken cur in document)
            {
                if (cur.TokenType == DocTokenTypes.Known)
                {
                    knowns.Add(cur.StringPart);
                }

                if (last != null && last.TokenType == DocTokenTypes.Known && cur.TokenType == DocTokenTypes.Known)
                {
                    {
                        Dictionary<string, int> ltable;
                        if (!FollowCounts.TryGetValue(last.StringPart, out ltable))
                        {
                            FollowCounts.Add(last.StringPart, ltable = new Dictionary<string, int>());
                        }

                        int count;
                        if (!ltable.TryGetValue(cur.StringPart, out count))
                        {
                            count = 0;
                        }
                        ltable[cur.StringPart] = count + 1;
                    }

                    {
                        Dictionary<string, int> ctable;
                        if (!PreceedCounts.TryGetValue(cur.StringPart, out ctable))
                        {
                            PreceedCounts.Add(cur.StringPart, ctable = new Dictionary<string, int>());
                        }

                        int count;
                        if (!ctable.TryGetValue(last.StringPart, out count))
                        {
                            count = 0;
                        }
                        ctable[last.StringPart] = count + 1;
                    }
                }

                last = cur;
            }

            // build probability grid (none of this efficient table filling dynamic programming nonsense, A* all the way!)
            // hmm... can't be bothered
            Dictionary<string, Dictionary<string, double>> fabTable = new Dictionary<string, Dictionary<string, double>>();
            foreach (var k in FollowCounts)
            {
                Dictionary<string, double> t = new Dictionary<string, double>();

                // very naive
                foreach (var k2 in k.Value)
                {
                    t.Add(k2.Key, (double)k2.Value);
                }

                fabTable.Add(k.Key, t);
            }

            string[] knarr = knowns.ToArray();
            Random rnd = new Random("ParaPatch".GetHashCode());

            List<string> fillings = new List<string>();
            for (int i = 0; i < document.Count; i++)
            {
                if (document[i].TokenType == DocTokenTypes.Unknown)
                {
                    // shuffle knarr
                    for (int j = 0; j < knarr.Length; j++)
                    {
                        string t = knarr[j];
                        int o = rnd.Next(knarr.Length);
                        knarr[j] = knarr[o];
                        knarr[o] = t;
                    }

                    fillings.Add(Fill(document, fabTable, knarr, i));
                    Console.WriteLine(fillings.Last());
                }
            }

            string filling = string.Join("", fillings);

            int fi = 0;

            using (System.IO.StreamWriter writer = new System.IO.StreamWriter(args[1]))
            using (System.IO.StreamReader reader = new System.IO.StreamReader(args[0]))
            {
                while (!reader.EndOfStream)
                {
                    int ci = reader.Read();
                    if (ci == -1)
                        break;

                    char c = (char)ci;
                    c = c == '#' ? filling[fi++] : c;

                    writer.Write(c);
                    Console.Write(c);
                }
            }

//            using (System.IO.StreamWriter writer = new System.IO.StreamWriter(args[1], false, System.Text.Encoding.UTF8))
//            using (System.IO.StreamReader reader = new System.IO.StreamReader(args[0]))
//            {
//                foreach (char cc in reader.ReadToEnd())
//                {
//                    char c = cc;
//                    c = c == '#' ? filling[fi++] : c;
//
//                    writer.Write(c);
//                    Console.Write(c);
//                }
//            }

            if (args[0] == "test.txt")
                Console.ReadKey(true);
        }

        private static string Fill(List<DocToken> document, Dictionary<string, Dictionary<string, double>> fabTable, string[] knowns, int unknownIndex)
        {
            HashSet<char> breaking = new HashSet<char>(Breaking);
            HashSet<char> punctuation = new HashSet<char>(Punctuation);

            Heap<State> due = new Heap<Program.State>(knowns.Length);

            Func<string, string, double> fabness = (prev, next) =>
            {
                Dictionary<string, double> table;
                if (!fabTable.TryGetValue(prev, out table))
                    return 0; // not fab
                double fab;
                if (!table.TryGetValue(next, out fab))
                    return 0; // not fab
                return fab; // yes fab
            };

            DocToken mostLeft = unknownIndex > 2 ? document[unknownIndex - 2] : null;
            DocToken left = unknownIndex > 1 ? document[unknownIndex - 1] : null;
            DocToken unknown = document[unknownIndex];
            DocToken right = unknownIndex < document.Count - 2 ? document[unknownIndex + 1] : null;
            DocToken mostRight = unknownIndex < document.Count - 3 ? document[unknownIndex + 2] : null;

            // sum of empty space and partials' lengths
            int spaceSize = document[unknownIndex].Length
                + (left != null && left.TokenType == DocTokenTypes.LeftPartial ? left.Length : 0)
                + (right != null && right.TokenType == DocTokenTypes.RightPartial ? right.Length : 0);

            int l = left != null && left.TokenType == DocTokenTypes.LeftPartial ? left.Length : 0;
            int r = l + unknown.Length;

            string defaultPrev =
                left != null && left.TokenType == DocTokenTypes.Known ? left.StringPart :
                mostLeft != null && mostLeft.TokenType == DocTokenTypes.Known ? mostLeft.StringPart :
                "";

            string defaultLast =
                right != null && right.TokenType == DocTokenTypes.Known ? right.StringPart :
                mostRight != null && mostRight.TokenType == DocTokenTypes.Known ? mostRight.StringPart :
                "";

            Func<string, string> topAndTail = str =>
            {
                return str.Substring(l, r - l);
            };

            Func<State, string, double, bool> tryMove = (State prev, string token, double specialFabness) =>
            {
                bool isPunctionuation = token.Length == 1 && punctuation.Contains(token[0]);
                string addStr = isPunctionuation || prev == null ? token : " " + token;
                int addLen = addStr.Length;

                int newRemaining = prev != null ? prev.Remaining - addLen : spaceSize - addLen;
                int oldPosition = prev != null ? prev.Position : 0;
                int newPosition = oldPosition + addLen;

                // check length
                if (newRemaining < 0)
                    return false;

                // check start
                if (oldPosition < l) // implies left is LeftPartial
                {
                    int s = oldPosition;
                    int e = newPosition > l ? l : newPosition;
                    int len = e - s;
                    if (addStr.Substring(0, len) != left.StringPart.Substring(s, len))
                        return false; // doesn't match LeftPartial
                }

                // check end
                if (newPosition > r) // implies right is RightPartial
                {
                    int s = oldPosition > r ? oldPosition : r;
                    int e = newPosition;
                    int len = e - s;
                    if (addStr.Substring(s - oldPosition, len) != right.StringPart.Substring(s - r, len))
                        return false; // doesn't match RightPartial
                }

                if (newRemaining == 0)
                {
                    // could try to do something here (need to change H)
                }

                string prevToken = prev != null ? prev.Token : defaultPrev;
                bool isLastunctionuation = prevToken.Length == 1 && punctuation.Contains(prevToken[0]);

                if (isLastunctionuation && isPunctionuation) // I hate this check, it's too aggresive to be realistic
                    specialFabness -= 50;

                double fab = fabness(prevToken, token);

                if (fab < 1 && (token == prevToken))
                    fab = -1; // bias against unrecognised repeats

                double newFabness = (prev != null ? prev.Fabness : 0.0)
                    - specialFabness // ... whatever this is
                    - fab * addLen; // how probabilistic

                double h = newFabness; // no h for now

                State newState = new Program.State(newRemaining, newPosition, prev, newFabness, h, token, addStr);

//                Console.WriteLine((prev != null ? prev.Fabness : 0) + "\t" + specialFabness);
//                Console.WriteLine(newFabness + "\t" + h + "\t" + due.Count + "\t" + fab + "*" + addLen + "\t" + newState.FullFilling);

                due.Add(newState);
                return true;
            };

            // just try everything everything
            foreach (string t in knowns)
                tryMove(null, t, 0);

            if (left != null && left.TokenType == DocTokenTypes.LeftPartial)
                tryMove(null, left.StringPart, -1);

            while (!due.Empty)
            {
                State next = due.RemoveMin();

                if (next.Remaining == 0)
                {
                    // we have a winner!!
                    return topAndTail(next.FullFilling);
                }

                // just try everything
                foreach (string t in knowns)
                    tryMove(next, t, 0);
                if (right != null && right.TokenType == DocTokenTypes.RightPartial)
                    tryMove(next, right.StringPart, -5); // big bias
            }

            // make this a tad less stupid, non?
            return Filler.FirstOrDefault(f => f.Length == unknown.Length) ?? new String(' ', unknown.Length); // oh dear...
        }
    }

    //
    // Ultilities
    //

    public class Heap<T> : System.Collections.IEnumerable where T : IComparable<T>
    {
        // arr is treated as offset by 1, all idxes stored need to be -1'd to get index in arr
        private T[] arr;
        private int end = 0;

        private void s(int idx, T val)
        {
            arr[idx - 1] = val;
        }

        private T g(int idx)
        {
            return arr[idx - 1];
        }

        public Heap(int isize)
        {
            if (isize < 1)
                throw new ArgumentException("Cannot be less than 1", "isize");

            arr = new T[isize];
        }

        private int up(int idx)
        {
            return idx / 2;
        }

        private int downLeft(int idx)
        {
            return idx * 2;
        }

        private int downRight(int idx)
        {
            return idx * 2 + 1;
        }

        private void swap(int a, int b)
        {
            T t = g(a);
            s(a, g(b));
            s(b, t);
        }

        private void moveUp(int idx, T t)
        {
        again:
            if (idx == 1)
            {
                s(1, t);
                return; // at end
            }

            int nextUp = up(idx);
            T n = g(nextUp);
            if (n.CompareTo(t) > 0)
            {
                s(idx, n);
                idx = nextUp;
                goto again;
            }
            else
            {
                s(idx, t);
            }
        }

        private void moveDown(int idx, T t)
        {
        again:
            int nextLeft = downLeft(idx);
            int nextRight = downRight(idx);

            if (nextLeft > end)
            {
                s(idx, t);
                return; // at end
            }
            else if (nextLeft == end)
            { // only need to check left
                T l = g(nextLeft);

                if (l.CompareTo(t) < 0)
                {
                    s(idx, l);
                    idx = nextLeft;
                    goto again;
                }
                else
                {
                    s(idx, t);
                }
            }
            else
            { // check both
                T l = g(nextLeft);
                T r = g(nextRight);

                if (l.CompareTo(r) < 0)
                { // left smaller (favour going right if we can)
                    if (l.CompareTo(t) < 0)
                    {
                        s(idx, l);
                        idx = nextLeft;
                        goto again;
                    }
                    else
                    {
                        s(idx, t);
                    }
                }
                else
                { // right smaller or same
                    if (r.CompareTo(t) < 0)
                    {
                        s(idx, r);
                        idx = nextRight;
                        goto again;
                    }
                    else
                    {
                        s(idx, t);
                    }
                }
            }
        }

        public void Clear()
        {
            end = 0;
        }

        public void Trim()
        {
            if (end == 0)
                arr = new T[1]; // don't /ever/ make arr len 0
            else
            {
                T[] narr = new T[end];
                for (int i = 0; i < end; i++)
                    narr[i] = arr[i];
                arr = narr;
            }
        }

        private void doubleSize()
        {
            T[] narr = new T[arr.Length * 2];
            for (int i = 0; i < end; i++)
                narr[i] = arr[i];
            arr = narr;
        }

        public void Add(T item)
        {
            if (end == arr.Length)
            {
                // resize
                doubleSize();
            }

            end++;
            moveUp(end, item);
        }

        public T RemoveMin()
        {
            if (end < 1)
                throw new Exception("No items, mate.");

            T min = g(1);

            end--;
            if (end > 0)
                moveDown(1, g(end + 1));

            return min;
        }

        public bool Empty
        {
            get
            {
                return end == 0;
            }
        }

        public int Count
        {
            get
            {
                return end;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public IEnumerator<T> GetEnumerator()
        {
            return (IEnumerator<T>)arr.GetEnumerator();
        }
    }
}

```
> 3 votes

---
Tags: string, popularity-contest, natural-language
---


# Question
Title: Is there a way of shortening fat-arrow functions?
From what I've seen throughout my time here on PPCG, most JavaScript entries involving fat arrow functions tend to be one of two camps:

1. The simple ones that are capable of running as a single statement and returning an answer, straight off the bat, like `x=(a,b)=>a*a+b`
2. The more complex ones that usually have curly braces because of the use of loops, and as a result require the use of a `return` statement.. like `p=b=>{m=b;for(a=1;~-m;)--m,a*=m*m;return a%b}`

Taking the above example from category 2 with the curly braces concept as proof-of-concept... Would there be a way to re-golf this code (or similar) like this so as to eliminate the curly braces as well as the `return`? I'm only asking this as this could *potentially* (not saying this will happen all the time) eliminate 8 bytes from a JS golfer's code. Are there any techniques that one could use in this instance? I've tried recursion, but the `m=b` statement has proven to be a bit of a bugbear, as I can't seem to shake it.

For the above code, how would one golf that further so as to eliminate the `return` statement, regardless of whether it golfs shorter or not?

# Answer
> 18 votes
## Use Recursion

I've found that recursion is (almost) always shorter than `eval`+`for`. The general way to convert from for to eval is:

```
for(a=n;b;c);d
(f=a=>b?f(c):d)(n)

```

So let's see your example:

```
b=>{m=b;for(a=1;~-m;)--m,a*=m*m;return a%b}

```

We can first simplify it to:

```
for(m=b,a=1;~-m;--m,a*=m*m)a%b;

```

What did we do here? Well we simply moved everything inside the `for` statement, this helps us reduce the amount of semicolons which is not directly better but almost always leads to some golf.

---

Let's put this in eval and compare it to the recursion version:

```
b=>{m=b;for(a=1;~-m;)--m,a*=m*m;return a%b}
b=>eval('for(m=b,a=1;~-m;--m,a*=m*m)a%b')
b=>(f=a=>~-m?(--m,f(a*=m*m)):a%b)(1,m=b)

```

The first part of the for loop (`a=n`), we can start that off by passing those variables in as arguments. The condition is simply: `b?(c,f(a)):d` where `d` is the return value. Usually `c` just modifies `a` so it can be merged into it. So we can golf it even more using what I've mentioned:

```
b=>(f=a=>~-m?(--m,f(a*=m*m)):a%b)(1,m=b)
b=>(f=a=>~-m?f(a*=--m*m):a%b)(1,m=b) // --m moved into a*=
b=>(f=a=>--m?f(a*=m*m):a%b)(1,m=b) // --m moved to condition

```

That said, as noted by @Niel is simplifying your algorithm. An algorithm golfy in one language may not be golfy in another so make sure to try different algoriths and compare them.

# Answer
> 11 votes
# Abuse eval.

It's simple. Instead of:

```
f=n=>{for(i=c=0;i<n;i++)c+=n;return c}

```

Use

```
f=n=>eval("for(i=c=0;i<n;i++)c+=n;c")

```

Eval returns the last evaluated statement. In this case, since the last evaluated statement would be `c+=n`, we would be left with `c` anyhow, saving two bytes.

```
f=n=>eval("for(i=c=0;i<n;i++)c+=n")

```

In general:

```
f=n=>eval("code;x")

```

is shorter than this, by a byte:

```
f=n=>{code;return x}

```

---

As a note, using graves to call eval to possibly save bytes doesn't work, since:

```
eval`string`

```

is equivalent to

```
["string"]

```

Helpful for obfuscation! Not so much for code golf.

---
Tags: code-golf, tips, javascript, recursion
---


# Question
Title: Change to conventional algebra notations
**The Challenge**

Given an algebraic expression (eg `2ab`, change it so it follows standard convention rules.

**The Rules**

* Letters should be in alphabetical order. ie `2ab` is allowed but not `2ba`.
* Numbers should always go first. ie `2ab` is allowed but `ab2` is not.
* Exponentiation will be given as `a^b` to mean `a` to the power of `b`.
* These rules must be applied to every sub-expression. ie `2ab + ba3` becomes `2ab + 3ab`, `2vd * vd5` becomes `2dv * 5dv`. **This must work for at least addition, subtraction, multiplication, division, modulus and exponentiation.**
* Exponentiation is assumed to belong to the variable immediately preceding it and must stay with the variable it is assigned to. ie `2ba^2` becomes `2a^2b`. This means that all variables to the right of `^` are part of the exponentiation.

**Sample Input/Output**

Input can be given with any amount of white space, which must be ignored. Output can use either one space or none. For example, `2ab +3ba` could become `2ab + 3ab` or `2ab+3ab`

```
Input -> Output
2ba -> 2ab
4gb + 5vh * gh7 -> 4bg + 5hv * 7gh
2ba^2 -> 2a^2b
5xk^2ba -> 5k^2abx

```

(The last couple of outputs don't make sense mathematically because of order of operations, but you don't have to worry about that.)

**Scoring**

Standard code golf, shortest answer in bytes wins. Answer can be a program which takes input, or a function (can be anonymous).

# Answer
# Ruby, 112 + 1 (`p` flag) = 113 bytes

Run as `ruby -pe` with the code surrounded by single quotes. Full program, even if it looks like just a recursive function at the beginning.

```
f=->s{s.scan(/(\w)(\^.+)?/).map{|a,b|[a,b&&?^,b&&f[b]]}.sort_by &:first};gsub(/[\w^]+/){f[$&]*""};gsub(/\s+/,"")

```
> 0 votes

---
Tags: code-golf
---


title: A Fractional Year

text:
# Question
Title: A Fractional Year
***My PPCG holiday is over :D***

## Intro

Fractional time is `the year + (the value (minute of year) / number of minutes in the year)`.

## Example calculation

*You should assume that February always has 28 days and the year is always 365 days long.*

Let's say we want to convert the time: `17:34 3rd March 2013` to fractional time. Firstly, you find how many minutes were in 2013: 525600 minutes. Let's call this `x`.

Next, you want to find out how many minutes there have been since the start of 2013. A few quick calculations will tell you that the answer is 88894 minutes:

There have been 61 days since the start of the year, which times 1440 (number of minutes in a day) equals 87840 minutes. In 17 hours are 1020 minutes (17\*60). Now, we can add 87840, 1020 and 34 minutes to equal 88894 minutes.

Let's call this `y`.

Finally, you divide `y` by `x` and add the year, resulting in `2013.16912` (to 5 decimal places).

## Input

The date and time will be given as a single string. The string will be in the following format:

```
YYYY-MM-DD hh:mm

```

The time will always be in 24 hour format and the year will always be in the range 1900-2050 inclusive.

## Examples

```
Input:  2016-08-06 23:48
Output: 2016.59723

Input:  2013-03-03 17:34
Output: 2013.16912

Input:  1914-11-11 11:11
Output: 1914.86155

```

If you are going for the bounty, either ping me in the comments or in The Nineteenth Byte.

## Challenge

Calculate the given date and time as a fractional year.

Give all output to five decimal places (you may round in anyway you wish: flooring, ceiling, or true rounding). Shortest code wins.

## Bounty

**I am offering a 100 rep bounty** for the shortest program which *also* accepts the date in fractional year format and returns the time in `YYYY-MM-DD hh:mm` format. In essence, your program (or function) has to act in the following way:

```
f('1914-11-11 11:11') => 1914.86155
f('1914.86155')       => 1914-11-11 11:11

```
1. t-clausen.dk - 154 bytes
2. Neil - 183 bytes

## Leaderboard

```
var QUESTION_ID=88924,OVERRIDE_USER=30525;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
# TSQL, 63 bytes

This is a shorter version than my original answer, because my initial answer included calculation for leap year.

```
DECLARE @ VARCHAR(16) ='1914-11-11 11:11'

PRINT LEFT(YEAR(@)+DATEDIFF(mi,0,STUFF(@,1,4,1900))/525600.,10)

```

**Fiddle**

The following sql can handle both input types

# TSQL, 154 bytes

```
DECLARE @ VARCHAR(16) ='1914-11-11 11:11'--can be replaced with '1914.86155'

PRINT IIF(isdate(@)=1,LEFT(YEAR(@)+DATEDIFF(mi,0,STUFF(@,1,4,1900))/525600.,10),LEFT(@,4)+RIGHT(CONVERT(CHAR(16),DATEADD(mi,1*RIGHT(@,5)*5.256,0),20),12))

```

**Combined Fiddle 1**

**Combined Fiddle 2**
> 1 votes

# Answer
## JavaScript (ES6), 84 bytes

```
f=
s=>(Date.parse(1970+s.slice(4).replace(/ /,'T')+'Z')/31536e6+parseInt(s)).toFixed(5)
;
```

```
<input placeholder=Input oninput=o.value=f(this.value)><input placeholder=Output id=o>
```

Assuming no leap years or DST are required, I replace the year with 1970 which makes `Date.parse` directly return the time offset in milliseconds, of which there were `31536000000` in 1970 (or indeed any other non-leap year). All I need do then is to add back the year and round to 5 decimal places. Edit: Bidirectional conversion in ~~183~~ 178 bytes:

```
f=
s=>/:/.test(s,m=31536e6)?(Date.parse(1970+s.slice(4).replace(/ /,'T')+'Z')/m+parseInt(s)).toFixed(5):s.slice(0,4)+new Date(s.slice(4)*m+3e4).toJSON().slice(4,16).replace(/T/,' ')
;
```

```
<input placeholder=Input oninput=o.value=f(this.value)><input placeholder=Output id=o>
```

Assumes strings containing a `:` are time format, handled as above, otherwise strips off the year, converts to milliseconds, adds half a minute for rounding purposes, converts to a date in 1970, extracts the month, day, hour and minute, and prefixes the original year.
> 5 votes

# Answer
## Matlab, ~~132~~ 115 bytes

```
 d=input('');m=cumsum([-1 '# #"#"##"#"'-4]);year(d)+fix((((m(month(d))+day(d))*24+hour(d))*60+minute(d))/5.256)/10^5

```

*Rounds towards 0.*

Hmmm... That's quite long.
That's using some builtins, but not the really helpful ones - because of leap years.

Parsing the string directly gives 2 more byte solution:

```
d=sscanf(input(''),'%d%[- :]');m=cumsum([-1 '# #"#"##"#"'-4]);d(1)+fix((((m(d(3))+d(5))*24+d(7))*60+d(9))/5.256)/10^5

```

Newer Matlab versions probably have some better split function, but I'm running on 2012a.

*Some bytes saved thanks to @Luis Mendo*
> 2 votes

# Answer
## PowerShell v3+, 131 bytes

```
$t=date $args[0];$a=1440*!!(date "2-29-$($t.year)");"{0:F5}"-f((($t.DayOfYear-1)*1440+$t.TimeOfDay.TotalMinutes-$a)/525600+$t.Year)

```

Takes input `$args[0]` and converts it with `Get-Date` to store into .NET `[datetime]` format, stores into `$t`. Calculates whether February 29th exists, and sets `$a` so we subtract out that date's worth of minutes (if present).

Then we use the `-f`ormat operator with a fixed-string specification of 5 decimal digits to run through the calculation. Uses built-ins to calculate the `.DayOfYear` and the `.TotalMinutes` of the given input, subtract `$a` if it's a leap year, divide by `525600` minutes total, and add on the input `.Year`.

Will complain (verbosely) to STDERR if February 29th doesn't exist (see examples below), but since STDERR is ignored by default, we don't worry about that. Also, note that PowerShell does banker's rounding by default.

### Examples

```
PS C:\Tools\Scripts\golfing> .\fractional-year.ps1 '2016-08-06 23:48'
2016.59724

PS C:\Tools\Scripts\golfing> .\fractional-year.ps1 '2013-03-03 17:34'
Get-Date : Cannot bind parameter 'Date'. Cannot convert value "2-29-2013" to type "System.DateTime". Error: "String was not recognized as a valid DateTime."
At C:\Tools\Scripts\golfing\fractional-year.ps1:7 char:36
+   $t=date $args[0];$a=1440*!!(date "2-29-$($t.year)");"{0:F5}"-f((($t.DayOfYear- ...
+                                    ~~~~~~~~~~~~~~~~~
    + CategoryInfo          : InvalidArgument: (:) [Get-Date], ParameterBindingException
    + FullyQualifiedErrorId : CannotConvertArgumentNoMessage,Microsoft.PowerShell.Commands.GetDateCommand

2013.16913

PS C:\Tools\Scripts\golfing> .\fractional-year.ps1 '1914-11-11 11:11'
Get-Date : Cannot bind parameter 'Date'. Cannot convert value "2-29-1914" to type "System.DateTime". Error: "String was not recognized as a valid DateTime."
At C:\Tools\Scripts\golfing\fractional-year.ps1:7 char:36
+   $t=date $args[0];$a=1440*!!(date "2-29-$($t.year)");"{0:F5}"-f((($t.DayOfYear- ...
+                                    ~~~~~~~~~~~~~~~~~
    + CategoryInfo          : InvalidArgument: (:) [Get-Date], ParameterBindingException
    + FullyQualifiedErrorId : CannotConvertArgumentNoMessage,Microsoft.PowerShell.Commands.GetDateCommand

1914.86155

```

---

### Alternately, with leap years, 119 bytes

```
"{0:F5}"-f((($t=date $args[0]).DayOfYear-1+$t.TimeOfDay.TotalMinutes/1440)/(date "12-31-$($t.year)").DayOfYear+$t.Year)

```

If we follow calendar settings, we can shave off a dozen bytes because we won't need to account for `$a` in the original code above. This allows us to move `$t` into the expression itself, and we'll explicitly calculate the `.DayOfYear` for December 31st. Otherwise, follows the same methodology.
> 1 votes

# Answer
# Python 3, ~~163~~ 173 bytes

more bytes because of output format

doesn't use any date builtins, like the java answer.

```
def s(x):z=x[5:10].split("-");v=x[10:].split(":");return int(x[:4])+(sum(([-1,31,28]+[31,30,31,30,31]*2)[:int(z[0])],int(z[1]))*1440+int(v[0])*60+int(v[1]))/525600

```

slightly more readable

```
def s(x):
    date=x[5:10].split("-");time=x[10:].split(":")
    return int(x[:4])+(sum(([-1,31,28]+[31,30,31,30,31]*2)[:int(date[0])],int(date[1]))*1440+int(time[0])*60+int(time[1]))/525600

```
> 0 votes

# Answer
# Perl 6,  ~~107 105~~  102 bytes

```
~~{$/=.comb(/\d+/);($0+(sum(|flat(-1,31,28,(31,30,31,30,31)xx 2)[^$1],$2)*1440+$3*60+$4)/525600).fmt: '%.5f'}
{$/=.comb(/\d+/);fmt $0+(sum(|flat(-1,31,28,(31,30,31,30,31)xx 2)[^$1],$2)*1440+$3*60+$4)/525600: '%.5f'}~~

{$/=.comb(/\d+/);fmt $0+(flat($2-1,31,28,(31,30,31,30,31)xx 2)[^$1].sum*1440+$3*60+$4)/525600: '%.5f'}
{$/=.comb(/\d+/);round $0+(flat($2-1,31,28,(31,30,31,30,31)xx 2)[^$1].sum*1440+$3*60+$4)/525600,.1⁵}

```

### Explanation:

```
{
  $/ = .comb(/\d+/); # grab a list of only the digits
  # ｢$0｣ is short for ｢$/[0]｣

  fmt

    $0 # year
    +
    (
      flat(
        $2 -1,                     #    days
        31,28,(31,30,31,30,31)xx 2 # -+ months
      )[^$1].sum * 1440            # /
      + $3 * 60                    #    hours
      + $4                         #    minutes
    )
    /
    525600

  : '%.5f' # the ｢:｣ is used here as ｢fmt｣ is a method not a subroutine
}

```

### Test:

```
#! /usr/bin/env perl6
use v6.c;
use Test;

# returns Str
my &fractional-year-a = {$/=.comb(/\d+/);fmt $0+(sum(flat($2-1,31,28,(31,30,31,30,31)xx 2)[^$1])*1440+$3*60+$4)/525600: '%.5f'}
# returns Rat
my &fractional-year-b = {$/=.comb(/\d+/);round $0+(sum(flat($2-1,31,28,(31,30,31,30,31)xx 2)[^$1])*1440+$3*60+$4)/525600,.1⁵}

my @tests = (
  '2016-08-06 23:48' => 2016.59723,
  '2013-03-03 17:34' => 2013.16912,
  '1914-11-11 11:11' => 1914.86155,
);

plan +@tests * 2;

for @tests -> $_ ( :key($input), :value($expected) ) {
  is-approx +fractional-year-a($input), +$expected, 1e-5, "a $input => $expected";
  is-approx +fractional-year-b($input), +$expected, 1e-5, "b $input => $expected";
}

```

```
1..6
ok 1 - a 2016-08-06 23:48 => 2016.59723
ok 2 - b 2016-08-06 23:48 => 2016.59723
ok 3 - a 2013-03-03 17:34 => 2013.16912
ok 4 - b 2013-03-03 17:34 => 2013.16912
ok 5 - a 1914-11-11 11:11 => 1914.86155
ok 6 - b 1914-11-11 11:11 => 1914.86155

```
> 0 votes

---
Tags: code-golf, date
---


title: METAscii Code Golf

text:
# Question
Title: METAscii Code Golf
**Introduction**

Here at code colf SE, we appear to love meta-problems. Here, I've tried to compose a meta-problem that's an interesting, not-straightforward challenge.

**Challenge**

The answer code is allowed to read its own source code, but not allowed to use external resources.

All characters should be 5-lines tall. Characters used in the ascii representation are also not important, though they must be visible. Each visible character in the output will count as one byte, regardless of cheaty byte-values. Spaces used in the code are necessary, and may be only one byte wide if desired.

Lowest Byte Count ***of the output*** wins. Output must exist and include at least 1 visible byte.

Example Input and Output

**Input:**

For an example code:

```
print theanswer

```

One possible answer is:

**Output:**

```
PPPP  RRRR  III N   N TTTTTT  TTTTTT H  H EEEE   AA  N   N  SSS  W     W EEEE RRRR
P   P R   R  I  NN  N   TT      TT   H  H E     A  A NN  N S     W     W E    R   R
PPPP  RRRR   I  N N N   TT      TT   HHHH EEE   AAAA N N N  SSS  W  W  W EEE  RRRR
P     R R    I  N  NN   TT      TT   H  H E     A  A N  NN     S  W W W  E    R R
P     R  RR III N   N   TT      TT   H  H EEEE  A  A N   N SSSS    W W   EEEE R  RR

```

The alphabet used should consist of the following ***patterns***, the characters used are not important: :

```
 AA  BBBB   CCC DDD  EEEE FFFF  GGG  H  H III     J K  K L    M   M N   N  OOO  PPPP   QQQ   RRRR   SSS  TTTTTT U   U V     V W     W X   X Y   Y ZZZZZ
A  A B   B C    D  D E    F    G     H  H  I      J K K  L    MM MM NN  N O   O P   P Q   Q  R   R S       TT   U   U V     V W     W  X X   Y Y     Z
AAAA BBBB  C    D  D EEE  FFF  G  GG HHHH  I      J KK   L    M M M N N N O   O PPPP  Q   Q  RRRR   SSS    TT   U   U  V   V  W  W  W   X     Y     Z
A  A B   B C    D  D E    F    G   G H  H  I  J   J K K  L    M   M N  NN O   O P     Q  Q   R R       S   TT   U   U   V V    W W W   X X    Y    Z
A  A BBBB   CCC DDD  EEEE F     GGG  H  H III  JJJ  K  K LLLL M   M N   N  OOO  P      QQ Q  R  RR SSSS    TT    UUU     V      W W   X   X   Y   ZZZZZ

 11   22  333  4  4 5555   6   77777  888   9999  000       //!!!  @@@   # #  %   %%  ^^   &&    ((  ))
111  2  2    3 4  4 5     6       7  8   8 9   9 0  00     // !!! @   @ #####    %%  ^  ^ &  &  ((    ))
 11    2   33  4444 555  6666    7    888   9999 0 0 0    //  !!! @  @@  # #    %%         &&& &((    ))
 11   2      3    4    5 6   6   7   8   8    9  00  0   //       @     #####  %%         & & & ((    ))
11l1 2222 333     4 555   666    7    888    9    000   //    !!!  @@@   # #  %%   %       &&&&  ((  ))   ____

```

For other characters, the equivalent produced by this generator using the 'Alphabet' font will be acceptable. If the output generated by the tool is more than 5 characters tall, use the central 5 characters for output.

**Edit -** I've allowed the program to read its own source code to possibly open this question up to interesting answers.

# Answer
> 3 votes
# Python 2, 2142 bytes

Should work, it's pretty confusing to read the output.

```
n=["","","","",""]
t=["EEEE","E  E","EEE ","E   "," EE "," E "," EEE ","E   E","E    ","  EE  ","EEEE "," EEEE","   ","EEE","     ","EE EE","    "]
e=[[t[4],t[1],t[0],t[1],t[1]],[t[2],t[1],t[1],t[1],t[2]],[t[0],t[3],t[2],t[3],t[0]],[t[0],t[3],t[2],t[3],t[3]],[t[6],t[8],"E  EE",t[7],t[6]],["EEE",t[5],t[5],t[5],"EEE"],[t[3],t[3],t[3],t[3],t[0]],[t[7],"EE  E","E E E","E  EE",t[7]],[t[6],t[7],t[7],t[7],t[6]],[t[10],t[7],t[10],t[8],t[8]],[t[10],t[7],t[10],"E E  ","E  EE"],[t[6],"E    ",t[6],"    E",t[6]],["E"*6,t[9],t[9],t[9],t[9]],[t[4],t[2],t[4],t[4],t[0]],[t[4],t[1],"  E "," E  ",t[0]],[t[2],"   E",t[4],"   E",t[2]],[t[1],t[1],t[0],"   E","   E"],[t[0],t[3],t[2],"   E",t[2]],["  E  "," E   ",t[10],t[7],t[6]],["EEEEE","   E ","  E  ","  E  ","  E  "],[t[6],t[7],t[6],t[7],t[6]],[t[11],t[7],t[11],"   E ","  E  "],[t[6],"E  EE","E E E","EE  E",t[6]],["EE    "," EE   ","  EE  ","   EE ","    EE"],[t[12],t[13],t[12],t[13],t[12]],[t[0],"EE  ","EE  ","EE  ",t[0]],[t[0],"  EE","  EE","  EE",t[0]],[t[15],t[15],t[14],t[14],t[14]],["  ","  ","  ","  ","EE"],[" EE","EE ","EE ","EE "," EE"],["EE "," EE"," EE"," EE","EE "],[t[12],t[5],t[13],t[5],t[12]],[t[16],t[16],t[16],t[16],t[0]],["  ","EE","  ","EE","  "],["  ","EE","  ","EE"," E"]]
def s(i):
 if i==" ":r()
 if i=="a":g(e[0])
 if i=="d":g(e[1])
 if i=="e"or i=="E":g(e[2])
 if i=="f":g(e[3])
 if i=="g":g(e[4])
 if i=="i":g(e[5])
 if i=="l":g(e[6])
 if i=="n":g(e[7])
 if i=="o":g(e[8])
 if i=="p":g(e[9])
 if i=="r":g(e[10])
 if i=="s":g(e[11])
 if i=="t":g(e[12])
 if i=="1":g(e[13])
 if i=="2":g(e[14])
 if i=="3":g(e[15])
 if i=="4":g(e[16])
 if i=="5":g(e[17])
 if i=="6":g(e[18])
 if i=="7":g(e[19])
 if i=="8":g(e[20])
 if i=="9":g(e[21])
 if i=="0":g(e[22])
 if i=="\\":g(e[23])
 if i=="=":g(e[24])
 if i=="[":g(e[25])
 if i=="]":g(e[26])
 if i=="\"":g(e[27])
 if i==",":g(e[28])
 if i=="(":g(e[29])
 if i==")":g(e[30])
 if i=="+":g(e[31])
 if i=="_":g(e[32])
 if i==":":g(e[33])
 if i==";":g(e[34])
 r()
def g(p):
 for i in range(5):n[i]+=p[i]
def r():g([" "," "," "," "," "])
for l in open(__file__).read().split("\n"):
 for i in l:s(i)
 print"\n".join(n);n=["","","","",""]

```

Output is 47965 bytes.

Can probably be golfed a lot more.

The code above uses half of the alphabet, all numbers and some symbols/special characters. I used the letter `E` for the output.

The characters are a list of five strings, each for one line. Also, to save a few bytes, there's a list with common lines (`"EEEE"`, `"E E"`, etc.)

The `,` has two lines, and one of them is below most characters, so I only included the upper one (same for underscore).

# Answer
> 3 votes
## Perl 5, 266

**34721 bytes code, 177815 total bytes of output, 266 bytes of which are non-whitespace.**

```
eval'                                                                                '=~s' +\t'chr length$&'ger
```

Based on the scoring confirmed by @Thomas Cleberg, something like this is likely optimal, but feels a little cheaty. This encodes a program that prints the desired output as space and tab characters, which are replaced with the result of running `ord` on the length of each run (spaces, terminated by a tab). To cater for this in the output, each tab is represented with two spaces (over the five lines) and all spaces are shown as described above.

TIO limits the output to 128KiB so you can't see it all there, but if you run this program locally, it should work as expected. Something like:

```
perl -M5.010 metascii-code-golf.pl > metascii-code-golf.txt

```

and view `metascii-code-golf.txt` in a text editor with word-wrap disabled.

Try it online!

---
Tags: code-golf, ascii-art, quine
---


title: Write a VIC cipher decoder

text:
# Question
Title: Write a VIC cipher decoder
You've received a coded message from your ally that you know is encoded with the VIC cipher. As you know that the VIC cipher is notoriously convoluted, you want to write a program that will decode the VIC cipher but is small enough to hide from the enemy if you are captured, and thus uses as few bytes as possible.

Your instructions are as follows:

**The information you have**

* The encoded message. For this example, we'll use the message we encrypted in the "VIC cipher encoder" challenge: `71431 14842 71192 58619 04185 22614 14745 49924 32826 13348 02189 38641 70140 40252 44820 64522 43982 47921 71283 22694 94443 80642 14521`
* A keyword with the most common letters of your chosen alphabet.
* A key phrase, such a quote or song lyric
* A date (or another number that is six digits or more)
* A personal agent number

In practice, these last four should be agreed upon beforehand by the sender and the recipient, including whether the agent number of the sender or the recipient is used in encoding.

What you and your ally agreed to use in your encoding is the following: the keyword `SENATORI`, the key phrase "The first principle is that you must not fool yourself — and you are the easiest person to fool.", and the date `3172016`, and the recipient's agent number, `9`.

**Summary of steps**

1. Derive the intermediate keys for use in the following steps and extract the message identifier from the encoded message.
2. Construct and apply the second (disrupted) transposition table in reverse.
3. Construct and apply the first transposition table in reverse.
4. Construct and apply the straddling checkerboard in reverse.
5. Finalize the decoding removing nulls and by starting the message at the "message begin" mark.

**Submechanisms**

Two more things to explain before we get into the meat of the matter: the processes of chain addition and sequentializing.

Chain addition, also known as a lagged Fibonacci generator, works by taking a starting digit sequence, adding the first two digits without adding and appending the result to the end. For example:

```
79081
7 + 9 = 6

790816
9 + 0 = 9

7908169
0 + 8 = 8

79081698
8 + 1 = 9

790816989
1 + 6 = 7

7908169897
... and so on

```

Sequentializing is essentially taking a sequence of letters or digits and labeling them by their alphabetical/numerical order. Duplicates are labelled left to right. For example:

```
E X A M P L E
    0         A
1   0       2 Es
1   0     3 2 L
1   0 4   3 2 M
1   0 4 5 3 2 P
1 6 0 4 5 3 2 X

3  3  0  5  8  4  2  0  4  7  5  4  8  1
      1              2                    0s
      1              2                 3  1
      1           4  2                 3  2
5  6  1           4  2                 3  3s
5  6  1        7  4  2  8        9     3  4s
5  6  1 10     7  4  2  8    11  9     3  5s
5  6  1 10     7  4  2  8 12 11  9     3  7
5  6  1 10 12  7  4  2  8 12 11  9 14  3  8s

```

I use zero-indexing here, but index however you like.

**1. Intermediate Keys**

Firstly, you need to retrieve the message identifier `M` from the message. The last digit of the date `3172016` is `6`, so you know that the message identifier was placed sixth from the last in the message.

```
The encoded message =
  71431 14842 71192 58619 04185 22614 14745 49924 32826 13348 02189 38641
  70140 40252 44820 64522 43982 47921 71283 22694 94443 80642 14521
Message id = 47921

```

Split the first 20 letters of the key phrase into two groups of 10 and sequentialize each individually, which we will call `S1` and `S2`.

```
    THEFIRSTPR
S1: 8201357946

    INCIPLEIST
S2: 2603751489

```

Subtract, without borrowing, the first five digits of the key date `3172016` from `M`:

```
M      47921
date - 31720
     = 16201

```

Chain add the result until you have ten digits:

```
1620178218

```

Add these digits to `S1`, without carrying, to obtain `G`:

```
     1620178218
S1 + 8201357946
G  = 9821425154

```

Above `S2`, write the sequence 0123456789. Locate each digit of `G` in the sequence 0123456789 and replace it with the digit directly below it in `S2`. The result is `T`.

```
   0123456789
S2 2603751489

G  9821425154
T  9806705657

```

Use chain addition to expand `T` by 50 digits. These digits, in five rows of ten, form the `U` block.

```
T  9806705657
U  7863751124
   5490262369
   9392885958
   2210634430
   4316978734

```

The last two non-equal digits of the `U` block are individually added to the agent's personal number to give the widths of the two transpositions, `p` and `q`.

```
9 + 3 = 12  (p, first transposition width)
9 + 4 = 13  (q, second transposition width)

```

Sequentialize `T` and use this sequence to copy off the columns of the `U` block, from top to bottom, into a new row of digits, `V`.

```
T     9806705657
seqT  9804612537

U     7863751124
      5490262369
      9392885958
      2210634430
      4316978734

V     69911 56837 12548 26533 30206 13947 72869 49804 84323 75924

```

Sequentialize the first `p` digits to get the key for the first transposition `K1`, and the following `q` digits for the key for the second `K2`.

```
First 12  6  9  9  1  1  5  6  8  3  7  1  2
K1        6 10 11  0  1  5  7  9  4  8  2  3

Next 13   5  4  8  2  6  5  3  3  3  0  2  0  6
K2        8  7 12  2 10  9  4  5  6  0  3  1 11

```

Finally, sequentialize the final row of the `U` block to get `C`, the column headers for the straddling checkerboard:

```
U5  4316978734
C   3105968724

```

**2. Reverse the Second Transposition**

We fill a transposition table with the message by columns in order of the column headings, `K2`. The message has 110 digits in 13 columns, leaves 8 full rows and six digits in a final row.

```
71431 14842 71192 58619 04185 22614 14745 49924 32826 13348 02189 38641
70140 40252 44820 64522 43982 47921 71283 22694 94443 80642 14521

starts off with

K2   8  7 12  2 10  9  4  5  6  0  3  1 11

              8                 7     4
              6                 1     2
              1                 4     7
              9                 3     1
              0                 1     1
              4                 1     9
              1                 4     2
              8                 8     5
              5

resulting in

K2   8  7 12  2 10  9  4  5  6  0  3  1 11

     0  6  0  8  2  6  4  2  8  7  2  4  9
     2  4  6  6  7  4  5  8  0  1  2  2  4
     5  1  4  1  1  5  4  2  2  4  6  7  9
     2  7  2  9  2  2  9  6  1  3  1  1  4
     4  0  1  0  8  2  9  1  8  1  4  1  4
     4  1  4  4  3  4  2  3  9  1  1  9  4
     8  4  5  1  2  3  4  3  3  4  4  2  3
     2  0  2  8  2  9  3  4  8  8  7  5  8
     0  4  1  5  6  8

```

Taking the rows one at a time, and stopping at the disrupted parts

```
K2   8  7 12  2 10  9  4  5  6  0  3  1 11

                                7  2  4  9  stop at 0
                                   2  2  4
                                      7  9
                                         4
                                            go all the way down until you run out of row
     4  1  4  4  3  4  2  3  9  1  1  9  4
     8  4  5  1  2  3  4  3  3  4  4  2  3
     2  0  2  8  2  9  3  4  8  8  7  5  8
     0  4  1  5  6  8

Result so far: 060826428 2466745801 51411542246 272922961311 4010829181414

```

The continue to avoid disrupted bits until the end...

```
K2   8  7 12  2 10  9  4  5  6  0  3  1 11

                                7  2  4  9  stop at 0
                                   2  2  4
                                      7  9
                                         4
                                            go all the way down until you run out of row
                                      9  4  restart until 1
                                         3

              5  6  8                       restart until 2

Result so far: 060826428 2466745801 51411542246 272922961311 4010829181414
41443423911 845123433442 2028293488758 041

```

Then grab the rest:

```
Result: 060826428 2466745801 51411542246 272922961311 4010829181414
41443423911 845123433442 2028293488758 041 7249 224 79 4 94 3 568

```

**3. Reverse the First Transposition**

As before, create the transposition table by filling in columns in order of the column headings, `K1`. With 110 digits and 12 columns, we have 9 full rows and 2 digits in a final row.

```
K1   6 10 11  0  1  5  7  9  4  8  2  3

              0
              6
              0
              8
              2
              6
              2
              4
              8

resulting in

K1   6 10 11  0  1  5  7  9  4  8  2  3

     4  0  7  0  2  0  1  2  9  3  1  2
     4  4  9  6  4  8  1  9  6  3  5  4
     1  1  4  0  6  2  8  3  1  4  1  6
     4  7  9  8  6  9  4  4  3  4  4  2
     4  2  4  2  7  1  5  8  1  2  1  7
     3  4  3  6  4  8  1  8  1  2  1  2
     4  9  5  4  5  1  2  7  4  0  5  9
     2  2  6  2  8  4  3  5  0  2  4  2
     3  2  8  8  0  1  4  8  1  8  2  2
     9  4

```

Reading of the rows in order, with no disruptions this time, we obtain:

```
407020129312 449648196354 114062831416 479869443442 424271581217
343648181212 495451274059 226284350242 328801481822 94

```

**4. Reversing the Straddling Checkerboard**

The heading for the checkerboard is `C = 3105968724`. We fill in the first row with the keyword `SENATORI` and the rest of the alphabet is filled in as follows:

```
  3 1 0 5 9 6 8 7 2 4
  S E N A T O R I
2 B D G J L P U W Y .
4 C F H K M Q V X Z #

```

To decode we simply look up the each number in the checkerboard as we read them. First, `4` must be a row heading, so we move to `40` which is H. `7` is I. `0` is N. `2` is a row heading, so we move to `20` which is G. Continuing in this way, we reveal the original message:

```
HINGELSE.MOVETOSAFEHOUSEFOXTROT#3#..
WEAREDISCOVERED.TAKEWHATYOUCAN.BURNEVERYT?

```

The question mark at the end is from the final `4`. As this is a row heading, there should be another number after this, but this is end of the message. Thus, we conclude that this is a null, and discard it.

```
HINGELSE.MOVETOSAFEHOUSEFOXTROT#3#..
WEAREDISCOVERED.TAKEWHATYOUCAN.BURNEVERYT

```

**5. Finalize the Decryption**

The program does not need to reinsert spaces and punctuation, but if there is a set convention for where the message originally began (here we used `..`), cycle through the message until the message beginning is at the beginning.

The final decrypted message is:

```
WEAREDISCOVERED.TAKEWHATYOUCAN.
BURNEVERYTHINGELSE.MOVETOSAFEHOUSEFOXTROT#3#..

```

Notes for this challenge:

* You are given a minimum of five inputs: the message, the letter keyword, the key phrase, the date, and a personal number.
* You may assume all inputs are valid, with the correct number of digits and letters (5-digit message identifier, at least 20 digits for the key phrase, and so on). You may assume that the keyword and key phrase have already had all punctuation and spaces removed except for those that you allow in your version, and that numbers are denoted with number signs correctly.
* The encoded message should be either a string of space-separated five-digit groups, a list of five-digit integers, one long string without spaces, or something similar.
* I used zero-indexing and `0123456789` in my example. You may use 1-indexing and `1234567890`, or some other system in your answer, as long as you specify what you used.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

# Answer
# Python 3, 1446 bytes

This is even longer than my encoder. Golfing suggestions very welcome.

As this is a counter to my encoder, this also uses the uppercase Latin alphabet with additional characters `.` and `#`. The decoder also uses 0-indexing and `0123456789` when converting `g` to `t`.

```
I=int;L=list;E=len;R=range;B=str;J=''.join
def H(s,e):
 for i in R(e-E(s)):s+=chr(48+(ord(s[i])+ord(s[i+1]))%32%10)
 return s
def Q(s):
 r=[0]*E(s);s=L(s);a=R(E(s))
 for z in a:b=min(a,key=lambda i:s[i]);r[b]=z;s[b]="~"
 return r
def T(x,k):
 u=E(x);v=E(k);g=R(v);c=[x[i::v]for i in g];s=[0]*v
 for f in g:s[k[f]]=c[f]
 return J(s)
def U(x,k,d=0):
 c=[];w=[];u=E(x);v=E(k);g=R(v);n=u//v+1;l=u%v or v;e=0
 for j in g:c+=[[]]
 for j in g:i=k.index(j);c[i]+=L(x[e:e+n-(i>=l)]);e+=n-(i>=l)
 for z in R(n):
  w+=[[]]
  for j in c:w[z]+=j[z:z+1]
 if d:
  u=[];r=y=0;i=k.index(y)
  while r<n:
   u+=w[r][:i];w[r]=w[r][i:];i+=1;r+=1
   if i>v:y=(y+1)%v;i=k.index(y)
  for j in w:u+=j
  return J(u)
 else:return J(J(i)for i in w)
def C(m,s,w):
 t={s[-2:]:".",s[-1]*2:"#"};x=64;r='';j=z=n=0;e=-1;h=''
 while x<90:
  x+=1;v=chr(x)
  if v in w:t[s[w.index(v)]]=v
  else:t[s[z-2]+s[j]]=v;j+=z;z=(z+1)%2
 for j in R(E(m)):
  if(e>=0)*(j<e+2):continue
  else:e=-1
  if n:e=m.index(s[-1]*2,j+1);r+=m[j:e]+"#";n=0
  else:
   k=m[j]
   if h:r+=t[h+k];n=t[h+k]=="#";h=''
   elif k in s[:-2]:r+=t[k]
   else:h=k
 b=r.index("..")+2
 return r[b:]+r[:b]
def D(m,w,P,d,A):j=-I(d[-1]);m=m.split();M=m[j];m=J(m[:j]+m[j+1:]);t=J(B(Q(P[10:20])[I(J(B((I(H(J(B((I(M[i])-I(d[i]))%10)for i in R(5)),10)[i])+Q(P[:10])[i])%10)for i in R(10))[i])])for i in R(10));u=H(t,60)[10:];p=A+I(u[-2]);v=T(u,Q(t));return C(U(U(m,Q(v[p:p+A+I(u[-1])]),1),Q(v[:p])),J(B(i)for i in Q(u[40:])),w)

```

**Ungolfing:**

```
def chain_add(seq, end):
    for i in range(end - len(seq)):
        seq += chr(48+(ord(seq[i])+ord(seq[i+1]))%32%10)
    return seq

def sequent(seq):
    res = [0]*len(seq);seq=list(seq)
    for z in range(len(seq)):
        b = min(range(len(seq)),key=lambda i:seq[i])
        res[b] = z
        seq[b] = "~"
    return res

def transpose(text, keys):
    columns = ['']*len(keys)
    for t in range(len(text)):
        columns[t%len(keys)] += text[t]
    res = [0]*len(keys)
    for index in range(len(keys)):
        res[keys[index]] = columns[index]
    return''.join(res)

def untranspose(text, keys, disrupt=False):
    columns = []
    for j in range(len(keys)):
        columns += [[]]
    num_rows, len_last = divmod(len(text),len(keys))
    num_rows += 1
    if len_last == 0:
        len_last = len(keys)
    text_index = 0
    for j in range(len(keys)):
        ind = keys.index(j)
        columns[ind] += list(text[text_index:text_index+num_rows-(ind>=len_last)])
        text_index += num_rows-(ind>=len_last)
    rows = []
    for k in range(num_rows):
        rows += [[]]
        for j in columns:
            rows[k] += j[k:k+1]
    if disrupt:
        undisrupt = []
        current_row = 0
        stop_key = 0
        stop_index = keys.index(stop_key)
        while current_row < num_rows:
            undisrupt += rows[current_row][:stop_index]
            rows[current_row] = rows[current_row][stop_index:]
            stop_index += 1
            current_row += 1
            if stop_index > len(keys):
                stop_key = (stop_key + 1) % len(keys)
                stop_index = keys.index(stop_key)
        for i in rows:
            undisrupt += i
        return ''.join(undisrupt)
    else:
        return ''.join(''.join(i) for i in rows)

def uncheckerboard(message, seq, word):
    trans = {seq[-2:]:".", seq[-1]*2:"#"};x=64;res='';j=z=0
    while x<90:
        x += 1
        v = chr(x)
        if v in word:
            trans[seq[word.index(v)]] = v
        else:
            trans[seq[z-2] + seq[j]] = v
            j += z
            z = (z+1) % 2
    num = False
    end = -1
    h = ''
    for j in range(len(message)):
        if end>=0 and j<end+2:
            continue
        else:
            end = -1
        if num:
            end = message.index(seq[-1]*2,j+1)
            res += message[j:end]+"#"
            num = 0
        else:
            k = message[j]
            if h:
                res += trans[h+k]
                if trans[h+k] == "#":
                    num = 1
                h = ''
            elif k in seq[:-2]:
                res += trans[k]
            else:
                h = k
    begin = res.index("..") + 2
    return res[begin:] + res[:begin]

def decode(message, keyword, phrase, date, agent):
    mkey = -int(date[-1])
    message = message.split()
    m_id = message[mkey]
    message = ''.join(message[:mkey] + message[mkey+1:])

    s1 = sequent(phrase[:10])
    s2 = sequent(phrase[10:20])
    b = ''.join(str((int(m_id[i])-int(date[i]))%10) for i in range(5))
    a = chain_add(b, 10)
    g = ''.join(str((int(a[i])+int(s1[i]))%10) for i in range(10))
    t = ''.join(str(s2[int(g[i])]) for i in range(10))
    u = chain_add(t,60)[10:]
    p = agent+int(u[-2])
    q = agent+int(u[-1])
    seqT = sequent(t)
    v = transpose(u,seqT)
    k1 = sequent(v[:p])
    k2 = sequent(v[p:p+q])
    c = ''.join(str(i)for i in sequent(u[40:]))
    z = untranspose(message,k2,1)
    y = untranspose(z,k1)
    x = uncheckerboard(y,c,keyword)
    return x

```
> 3 votes

---
Tags: code-golf, cryptography
---