title: Lorem Ipsum Generator

text:
# Question
Title: Lorem Ipsum Generator
Lorem Ipsum is placeholder text used when preparing layout without wanted to have content already filled.

One of its key features over using some arbitrary text is **that it is nonsense**. It isn't even valid latin (though it is close). This prevents anyone being shown the layout from becoming distracted reading the text.

The other key feature is that **it looks like real language**. The words are the right length, and the characters occur with the right distributions.

A problem is that the Lorem Ipsum is not necessarily good gobbldy-gook for all languages, or even for all subject matter. We expect that the distribution of letters would be different in a novel, than in a scientific article.

Your task thus is to create a tool that when given an example of text, generate a lorum ipsum style gobbldy-gook that is a suitable imitation of the characteristics of that text.

## The Task

Given an input in UTF8 text *input-text*, and a number x. Output x characters of gobbldy-gook following the style of that text.

It may be assumed that words are separated using the space character in the input text.

You may take the input in any reasonable form (though it must be able to accept UTF-8). Eg reading from STDIN, reading from file, as a string passed to the function etc. Similar for output.

## Critria

* Must not be real correct text in the language of *input-text*
    + In particular must contain no words with more than 3 characters from *input-text*.
    + This can be trivially avoided by using a hashset to ban all words from *input-text* from occurring in the output
* Must look like it could have been real text from the language of *input-text*.
    + That is to say it must have the correct letter and word length distributions that is convincing to the eye of the reader.
        - It is up to the implementation if they take this to mean unigram, bigram, trigram or other statistics for the distributions.
        - The goal is for it to look right

# Judging Texts

For purposes of judging please provide 256 characters of output based on each of the following public domain texts:

gist with all files

Those that these are all UTF-8 encoded, and in particular Die Verwandlung, being in German uses many characters outside \[a-zA-Z\]

# Answer
> 4 votes
# Python 3

```
import string
import random

with open('lorem.txt') as f:
    text = f.read()
number = eval(input("Input number: "))

dictionary = ''.join(ch for ch in text if ch not in set(string.punctuation)).split(" ")

chars = []

for word in dictionary:
    for char in word:
        chars.append(char)

chars = list(set(chars))

occurences = {}

for char in chars:
    occurences[char] = []

for word in dictionary:
   for idx, char in enumerate(word):
        try:
            occurences[char].append(word[idx+1])
        except IndexError:
            pass

lengths = [len(x) for x in dictionary]

result = ""

for _ in range(number):
    length = random.choice(lengths)
    word = random.choice(chars)
    for _ in range(length):
        try:
            word += random.choice(occurences[word[-1]])
        except IndexError:
            break
    result += word + " "

print(result)

```

Takes text input through a file named `lorem.txt` and number of words through STDIN.

Samples:

De Finibus:

> bolute moresu xisi libospssev lolu ute tamqump Sercolimo mnci iaerue unt xptemp ptur xiui mumnsc ner citerum hiositius fun Set llu hibol etet mpesi amitap voserata mol iumol ospe pte ell asequmut

Die Verwandlung:

> Frehwauchmi « vo ineic venzundenwasender geitende « darenenserttem Semint estt Scklode Zur g ZenÂ»e Orer urd cher s Bet kun renaunn

Pride and Prejudice:

> paime k hothenoc 5 “ 230 erth ZZWedomincab Mrevoueim Vifedrctogei Come Kidi yol qul “Thant Kie Rag 41 mf vate 12 Eled 8 Dathed 1 mb Bed “Y merie xto zasorl h’sh ghasst Wha quce skeniat zan dishond othing hare hing din

And finally, the Magna Carta:

> wincand zisend s Pes CEFured indons fequ dindshay ranen Gofun OURore ibec 6248 Rofonestheasaven sul nthal 232 rend matyont r uiconlicend ucriof 7 ashesevenye Gerd BEndrouse IIns jurig 20000 UREndit mandira 0000000000s a wic 47 Enccet

It's not my best work.

All I'm doing here is some simple Markov chain recreation of the original text, with word lengths taken from a list of all lengths in the given text.

I sort of hoped for better results, but oh well.

# Answer
> 4 votes
# Clojure

This was hard! I started this last night at 9pm thinking I could knock something quick out, no problem. All the little problems I didn't realize when I started began to pile up though, so I had to put it on hold until this morning.

It's still not great, but it does the job.

Note: For some reason, IntelliJ/Cursive's REPL (which I used to test and generate the phrases) can't accept code greater than 65k chars in length, which means I couldn't simply paste some of the sample texts into the REPL. I tried reading them from file, and for some reason accented characters aren't being read properly, despite specifying UTF-8 encoding. As a workaround, I used subsets of the texts to act as the sample to generate from.

* De Finibus:

> vitsmai qomsme tainrte,e qanerim toaurtatt roliaum veaiieq foimpq smarsu mneurutds drtameitt vndnceui cesolleqd Ambrsuou hntumetni euuhcqitu eoseiuane fusipdm,t depamme vofuuet uamsel aumsatet aaee.idu, metosa etqirtai ialisua vsleataa vellpuen aalui, celaqa eultnsec celili eolisi,t qcrm,qets qolniani earure elfucnsn donate qitua,at. aimaau dmgaim aeumltn qori,et cogerentt serlitmt. uaqua,dr aososlt dulir,m oelmmc ietiqctti aupniuon semionu aerciamti qlmomi hinldt htnuaiqa cnnoot cetultad nutcliaa aolstu puouru nfiuitmiu lapopttr rxsutea ood,rut aiseuc quoe.rmi ntiemhb ueter,sb delsrias titopduto qurorcd,t vxiupsi sem,reer iaeesit, mooila eolnoa infosmese exni,uns qtnpeet peiealna lolopt duosrtun oufmttn omsarhdsa veri,rme doilrnt hulstqo cxlusa uasputua qtlpl, certppmtd qopu,tmi oonires oosoia fu,iepa eedumtn,e sesiot,t rtioeam helnora rrnoeeas aslceiist ealimtdd qolsmnas eetgoeta tomema eemurst exoacumtn tuioeq,sa vtauctdst oarittsbt lonpstoa, famade,qa empoenuti minisatie vuiuseuis bxnmii nafuiemsi plscrt vusuiiu macirs cugaesa vttsitm dumudta ruluiqu easimin vsceicnt tuqmeiuns aoitm, inaulnac vfsioe,nu iomistaa. qalisi lanurr eiutma qesbtdi eprurni qintp,iim iuiamt setuoteee qugpeau hfge,e eosqpe dicemte vamerdm noluisi euceaaa eliiutii iinnat ioiuraa aubie,uat ctret,u ruaemi,a, noq,re dupiet eugesr nsnosema ouseipon qasupeeci axtilemt aaaedmdni tssimac ouptpicii notunein qiclo,ist eetummea aelste aictd, vanerean qulurus fenumit, ciieriste dtascec eolirliee bemuam qactiiaei cirudadn qupespase eerqednb vaiimua ltmemsia mucnpu qpmttea militu outpeqct caiomeetu mid,semd ailudtm eumcpri duniics negusqat nunnsu nobod,ntu aoss,it mopaueta dubupntao Seluoiatd atteresc ouisrmn mutdri ee,iri lonoeuo meirqudi montutut qre,ain foitute vaiupmi seilpusin eaoeei,i eetldidse heguise fetbra,sd deri,ssai qirrpcua dothii qiioutub dol,iem moacdss uocr,iit eassrreti ilouptutd qtgupc qiuicet vtiusitam aesupti qaileats qobeee, qornstesi tucpmitna sunuoqdt noclunmc eopisstr aicnppts suuimtett telom, ontimtc aosoren,i stbirstre qpctd,tb aunviu eapaott dnrutmt eoiure iiliei sulootitd iepidtsb, excpraii factm,tse outittt fbgira suaapeiut atniiet vuiireo vtes,eisi qtseueai qour,ea
* Pride and Predjudice:

> eoonr. Wosr sotd. siwlt aaaer” ohe” osxalp shrprc afel nhsn ttydt aetr ohtti aotu.n tonl bouno Inui woptur weomtf hhnars ohte oisms Laurl \_nje\_y thr\_ Mofl,d aist! *rdne snage iasi mier.n onen bolh myyier Nont,c hian ihl!i Bcs””r aoei jewesr Msuwh wodeed aiuwdd arssl” efae mosnlb fuqet onsm “e,eeo vereen roor tlrli” nm.p tsrtid auitl aigm yhru shurr sontav yene. esug hoyvot “odhg ahenke coufn hhcer mike:l mfol heae oadiai iooi fotzdf piey ofu? shn,tc Iied Ihnrg mhoihs naurn IIahkk mosi nfolc Mfekei gieu deoei iHnu ivtu huuti Bo.tsi rysnei mirvn ered are,e ooel wIae Temmoe qoyu fetee, ynhd nontui hgnw aaye fet.kd irro “gtp noatk inrn* isdstt tDun thde ohulie watw teness veeee, Mhntsr sai.s Lodue Iteref niergr thst luegn tsuned wii,e, taes iemtsh lhuhs ys..s hahie eehren unet haettd fam.i thurl Lptm *our hftle ar.nna ayeoeg hem.,r whnn oner foiet- Bhfe “o.mll thue yoyh cory aean Mehg ho,ncs falntn nstu tnse,. dnutni weuee olmpt ay.nnu coeso lyeteg ancy,p iffg ihele Ooreen arrn “akyan tttn cxno nomi “heh momee an.ra tosts, Efee afi! arow ynele io.z teocr aids sore ioog shrr hmrve aynri Braus guaein bouree lupa aB,.t inru hnuu todnl thdiyi hvanwa botvu hidiet Nilie toa.y wothn. nesth Ioia* mhoob whdr tYen oosl yehg Molt mokdn gonetf shrle toieg tooet He,lh bu.ead datog “aru atre soym eiomar yose mome htas, Lonr “otets oidrsi hwanes yimr! anelsh Bhst tNn; fhang, talp mirn “oklbt “eod” dorhit hopc ieddn Maae Bnelp tuuovg iWne co,ye ghsee fa!rn MTenee vodnr hu.a aatrel hoehs yfnmc Meog oenec prrn ieuwae “olei
* Die Verwandlung:

> inrter Bninrl aäshsi zictth ztgtee.n ireztnr ereoo«de dlifc su,rienn dicgi! duechre gädkean iafiu hbrhür,e öamk, auehse, fhgltr ernsme urcttm uGmartrt eacge wungu eeelle üaise,n dantrid s-ßenn Tamrsd, ierosne fifn, satfg decnt Firüncr goztfekh urcfenl zrg,t donet fartan eishgta eo,dt mrnagks Cutterc iirlo uufbea Wsnhdh hages iicrelnn wimbs wickon Pehuelö? uuertn eleezn üewnlnäe zeiüriti Pidhi Feldaet Banec ahleßelk Nanpüehn eedeuh elflt aüagn mogteäg wehhhorr for,tt h-trtlg öoßdrit Teaue aaedeee necmär vingrrha hai,h vidos ncsne,ne nurlurns Uomeer vrrecoü kcphtd uhrleßl neeke dcrhth amämtza dehbsn Meftet,e dnlwenei Gigrser zagnüe srrcse Wenstt asnbhn Zägele Eebeefn eerhte dihee Nernta. saheter Uihöu fitfu aibeeens Einre Banwf vaneine eardtg fnebtn Sihne hontn hemte, uecßred arrdhe dollnän. Juhno gasdee eeelhn wonlht Aänsüenr vlrssf Dowtlhin Ueeseasl iusnu namhie Binziae wieleet bucdrne maselort Süfiwr strzgdlg dGnite sifgh iusecti Dohutl eucl.g Bbrstnih amehn,üc sarlhe vcredrne krlnat dbrnra enimsnhs larwrn docdää karho Zaths »ersnnhf weire Tirhee drrhm?s iesetehu ialneke geihc disege larsuet, mrintm Ginhdrhe eoieu Msitpn rarzeut, eahßl düernäde eugchn enean zenüor dertnhe Inheuer dlctßcim fitimok hrrsnec säscl Seletete grßrtdce Kunenh bameänßn Wirmg heluhst Uensi gärnre döarrct wrnw,wel datbc Raree lonse mcrseuf aetoet rrncär wrcgelm saste Zirpe uewl,t wceeeskr Aismttme ketfer hnssen Pind,e, einsr?e! diflec mlrlcnft »umgeiß sär,ed nodfst Hbdßen Weensel finhedd lunnt dehsnrg fibsin.a hictfet« vrgturs lehntnm leektfrf brehrrnd brlen eorfem srsgenrn Ditreeen girzee iigeenie devr, daelmrs eanlecse iootohca durgt dalmce srzsh dihrugnt Bbtrwsg iDre,nil aeegesüt Irfcdr etcnruec mlaznegc setirkh Sehteeec kinlaret Ubetetlc gnßfeot eieiuen kantgr wackt -usltrm kereä eerben sahendfh nusarnd ialaac decfear hofüei wbmtee! srnper eegik nünnh woiieb« derlee« dregeeee danhele deetpi gmraeeg esaaez z-täe
* Magna Carta:

> giotei ooeleeg majegcg aorses fernpt sekml mhmt,p tfaGta deoel (n8rsse andpi ufaih fnoseu efaes hhod,i wieer hogd,e boeer `soin IwsoRei bed)t fogds tipdfr neylnme ouehps oedhhem Chuaee hst)sr oascs werooen ou'hin hhansn ofecdsd towsof alee, lube'a Gosisfr boceeae ahdbee laaeh tngdc hheoTct (oyce ouedoe' dnysscg beenru hocOo Jshlsee kralse juili`haerhs walreno (nlln troll onoplat dw9ed senroc aolpmdt toedhh gerdc eiype beilsr gbeibet pedns le.rsu aamtnon aoenri tsiaey torrtv oamle snvsn faaorw dhrss arrber Thvsat rafgmu thnslp pnnril rfrsrt letol whhle Ifoehog fhaeos. trthon fukmrnn hnkei otrvt bieyl armbs mneh, felycmg weter mfhte direon' Ma0slo leelo ane'r hneh, Fress snurwe seaoas poevoc, dasee heeeic, efn)lss gtct- eo9laip wnrrlit lyyei, gndosti oecoe suroe taftu bieel feolrg oortefd loatfv -rleln tacblst Nnrcr nOnnr rtimhc toahlfe Wirrn brfbo aecrhb whehri ohnmi walnn oeorlfs rhpsene cauppn woitsns toynr heapihd oanetd ofghen Nfesrtf gamerg desolsf gr.roeb i9drnf uodthn tnrehne wuae'l iutsse Eonllse poplrsa Ghoel m4teest ffest tauec i3pall, shent, gwadi sitcra ifsoo, Wivwn s1tdeur bagersa fead.,g teseus rncdrne hangss thzel aents ienus, binseae (osa.re trrrs of)io eyfgo, trrml oiado sumsn weygrch ahmlvnn tuednt utepsit iota- Ehe.lm crtlot aet)r crblras aenelf, tupmtae Eelee wtoerrd rfant ifldd fhyalt ffdog thuho tists, teadhl nadtoat tflda, Aielsd otreli trrn,mc feeneut nndcdeu hhnlv lidea, titges afrit wrkor eev)lt, fndni hrmml)d tegvee Ihr,nnf kvqoe cnentr Nedtl onmebba hhwdee eopoi aonthnl aautle uflhu. `Retan shclaer Jostsi *prdz ebnnlc ferde hiepraa oa9)eat lisvyn nilos brslbwe btyson aoncs,`vi,t tntter stret cifgile tuslene kivtle irmie aylrie Faala-e aneies gatoy wuomsne shyah snoio.d afeh'a drfree khvoget wicrsns caves, hheto (blfs sheoue

```
(ns mandelbrot.loremipsum
  (:require [clojure.string :as s]))

(defn rand-word
  "Generates a random word based on what letters appeared at what index.
  If the index doesn't exist, it pulls a random character from the sample-text."
  [length pos-map sample-text]
  (apply str
    (for [i (range length)]
      (rand-nth (get pos-map i sample-text)))))

(defn safe-rand-word
  "Helper that loops while the produced input is in the exclusion set.
  May get stuck if the sample size is too small."
  [length pos-map sample-text exclusion-set]
  (loop []
    (let [word (rand-word length pos-map sample-text)]
      (if (exclusion-set word)
        (recur)
        word))))

(defn rand-word-len
  "Generates a length based on avg-len +/- an amount in
  the (range (- deviation) deviation))."
  [avg-len deviation]
  (+ avg-len
     (rand-nth (range (- deviation) deviation))))

(defn pos-letters
  "Records what characters occured at each index of each word."
  [words]
  ; A two dimensional reduction.
  ; The inner reduction takes an existing pos-map, and updates it with information about the word
  ; The outer reduction combines all the word pos-maps together.
  (reduce (fn [pos-map word]
            (reduce (fn [acc [i chr]]
                      (update acc i #(if % (conj % chr)
                                           [chr])))
                    pos-map

                    ; Maps with the index of each letter
                    (map vector (range) word)))
          {}
          words))

(defn gobbly [n-chars sample-text]
  (let [; Split the text into words, then place the words into a set
        ;  to ensure that they aren't generated.
        words (s/split sample-text #"\s")
        word-set (into #{} words)

        stripped-text (s/replace sample-text #"[,.?!]" "")

        ; Figure out the average word length, then calculate how much
        ;  deviation should be allowed.
        avg-word-len (/ (count sample-text) (count words))
        length-deviation (/ avg-word-len 4)

        ; Find which characters appear at which positions
        pos-map (pos-letters words)]

    ; Generate n-chars many characters by...
    (doseq [n (range n-chars)]
      ; ...printing a space, then a randomly generated word.
      (print ""
        (safe-rand-word (rand-word-len avg-word-len length-deviation)
                        pos-map
                        stripped-text
                        word-set)))

    (flush)))

```

Use it like:

```
(gobbly 256 "KNOW THAT BEFORE GOD, for the health of our soul and those of our\nancestors and heirs, to the honour of God, the exaltation of the holy\nChurch, and the better ordering of our kingdom, at the advice of our\nreverend fathers Stephen, archbishop of Canterbury, primate of all\nEngland,")

```

# Answer
> 2 votes
# Python 3

I chose not to assume almost anything about the source language. In particular, I chose not to give any special meaning to anything except for whitespace. Therefore the code doesn't generate sentence-like constructs or valid quotations, but doesn't get worse with another language with different "syntax".

The heart of my code is a Markov chain. The first part of `generate()` parses each word of the text, collecting the probabilities that a certain character appears after another one in the text, along with some extra data.

The second part of the code then generates words based on those probabilities, along with some validation and modification:

* The Markov chain only generates characters that appear after the previous generated character in the source text.
* The lengths of the words are distributed as in the input. If the Markov chain does not know how to continue generating a word, it is discarded.
* A character must have existed in the current position in a word, both from the start and end. (For example, for input `"a-bcd," e.` a dash may only exist as the third character of a word.) This removes lots of wonky punctuation. After 1000 tries the code may allow an invalid character.
* Each character is made uppercase with the same probability that the character in that position is uppercase in the source.
* "Real" words are discarded by a simple set lookup.
* The whitespace between words is picked from the whitespace sequences in the source.

## Code

```
def generate(text):
    import random
    def increment(dic, key, mid = None):
        if mid is not None:
            if mid not in dic:
                dic[mid] = {}
            dic = dic[mid]
        if key not in dic:
            dic[key] = 0
        dic[key] += 1
    def pick(dic):
        total = sum(dic.values())
        pos = random.randrange(total)
        for key in dic:
            if pos < dic[key]:
                return key
            pos -= dic[key]
    words = text.split()
    markov = {}
    allchrs = {}
    lens = {}
    white = {}
    poss = {}
    uppos = {}
    valpos = {}
    pos = 0
    prev = 0
    for word in words:
        increment(lens, len(word))
        if prev:
            pos += len(prev)
            whi = text[pos:text.index(word, pos)]
            pos += len(whi)
            increment(white, whi)
        prev = word
        curr = 0
        for p, char in enumerate(word):
            increment(allchrs, char.lower())
            increment(markov, char.lower(), curr)
            increment(poss, p)
            increment(valpos, p, char.lower())
            increment(valpos, p - len(word), char.lower())
            if char.isupper():
                increment(uppos, p)
            curr = char.lower()
    words = set(words)
    output = ""
    while True:
        append = pick(white) if output else ""
        wordlen = pick(lens)
        while True:
            prev = 0
            word = ""
            valid = True
            for i in range(wordlen):
                if prev not in markov:
                    valid = False
                    break
                for _ in range(1000):
                    char = pick(markov[prev])
                    if valpos[char].get(i) and valpos[char].get(i - wordlen):
                        break
                upp = random.random() < uppos.get(i, 0) / poss[i]
                word += char.upper() if upp else char
                prev = char
            if valid and word not in words:
                break
        append += word
        if len(output + append) > 256:
            break
        output += append
    return output

import os, sys
for file in os.listdir():
    if file.endswith(".txt"):
        print(file)
        with open(file, encoding="utf-8") as stream:
            print(generate(stream.read()) + "\n\n---\n")

```

## Output examples

### De Finibus

This one is probably the best for my code. Almost resembles lorem ipsum.

> do volllem ptem funsc sumoloduma arec aderodi iupen vonsteretae et, pt atisatus monce qupll remeris sasps am coria cecumaedaii ro an isii da vot esi Erenemonere lo vol lasuama min do oluaecodaer coluse ptrel bea ata, ctati vonditacetes mm oma oventquia

### The Magna Carta

Looks a bit like Spanish.

> bl oranr tr wighibintert han ma am mmpe "im noreervetord h
> olandiale tll afin ssh iany hor 48) touro oelllll ce rc ome bl tse pale ota Edeid fonnny," disen oc nd,- kindi ccofore mamar mo hakne fr
> beneth te byse me sur hindesweay
> ane me rciven asho shidi

### Pride and Prejudice

Again, English is hard.

> hendver gh th,”
>
> te ther y.” wherorath pprmyo it\_t un? stro wam wllyserinof hish ac Wfey’sm sar.” wenenonto ther chu The, L ryo jounddle.” asis i
> fto ok il warano rrithiel
> amsti hes weteran ay.’sthinsti
> merlisomos, asth “llle Hellye yerg
>
> mer ady syo

### Die Verwandlung

This one looks almost like German, but gets a lot of weird punctuation.

> h
> den. zunder an,« di grhtsck ieit erimie Len De ihttergommkor kkuc aledoht hrserogo ereschla Ateg seneichier-,« gonu imori hr sch demaßti aglfhl iht Rnde au Igeng,« ding üb ukrtl iemen dein Wehle nkt ieiei Ügenifregr En g mirgs sworer zwi blimmi er,« kb

### The program's own source code

```
what(wils(le uenc rumid dent pp ren
    ifot inc inos(itpendi pr iss imit
                wor f uenete me orditp ds ourdinorkemit()
                    ist(whar wori nserev[preval "
                    sp iminderreralin):
            m

um
        inc

```

# Answer
> 2 votes
# Python 3

This code is very heavily based on the text generation example program from the Keras machine learning library. It uses a Long Short-Term Memory (LSTM) recurrent neural network trained on the data to generate the output character by character. I would've written the LSTM implementation myself, but I didn't want to reinvent the wheel when there was already such a good implementation that was capable of performing the task at hand.

The input is taken in a file named `input.txt` and is output to `out.txt`. I originally just used STDOUT, but Windows CMD didn't like trying to output `utf-8`.

The output could be improved on longer corpuses (i.e. Pride and Prejudice in the four that were given) by increasing the number of epochs the model trained for, but the runtime for a long corpus was already quite high, so I didn't bother doing so.

```
from keras.models import Sequential
from keras.layers import Dense, Activation
from keras.layers import LSTM
from keras.optimizers import RMSprop
import numpy as np
import random
import re

PATH = 'input.txt'
DIVERSITY = 1.0

text = open(PATH, encoding='utf8').read()
print('Corpus length:', len(text))

chars = sorted(list(set(text)))
print('Total chars:', len(chars))
char_indices = dict((c, i) for i, c in enumerate(chars))
indices_char = dict((i, c) for i, c in enumerate(chars))

regex = re.compile('[^a-zA-Z ]')
words = {word for word in regex.sub('', text).split() if len(word) > 3}
print('Total words:', len(words))

maxlen = 40
step = 3
sentences = []
next_chars = []
for i in range(0, len(text) - maxlen, step):
    sentences.append(text[i: i + maxlen])
    next_chars.append(text[i + maxlen])
print('NB sequences:', len(sentences))

epochs = max(1, min(20, 200000 // len(sentences)))

print('Vectorization...')
X = np.zeros((len(sentences), maxlen, len(chars)), dtype=np.bool)
y = np.zeros((len(sentences), len(chars)), dtype=np.bool)
for i, sentence in enumerate(sentences):
    for t, char in enumerate(sentence):
        X[i, t, char_indices[char]] = 1
    y[i, char_indices[next_chars[i]]] = 1

print('Building model...')
model = Sequential()
model.add(LSTM(128, input_shape=(maxlen, len(chars))))
model.add(Dense(len(chars)))
model.add(Activation('softmax'))

optimizer = RMSprop(lr=0.01)
model.compile(loss='categorical_crossentropy', optimizer=optimizer)

def sample(preds, temperature=1.0):
    preds = np.asarray(preds).astype('float64')
    preds = np.log(preds) / temperature
    exp_preds = np.exp(preds)
    preds = exp_preds / np.sum(exp_preds)
    probas = np.random.multinomial(1, preds, 1)
    return np.argmax(probas)

model.fit(X, y,
          batch_size=128,
          epochs=epochs)

start_index = random.randint(0, len(text) - maxlen - 1)

generated = ''
sentence = text[start_index: start_index + maxlen]
generated += sentence

for i in range(1000):
    x = np.zeros((1, maxlen, len(chars)))
    for t, char in enumerate(sentence):
        x[0, t, char_indices[char]] = 1.

    preds = model.predict(x, verbose=0)[0]
    next_index = sample(preds, DIVERSITY)
    next_char = indices_char[next_index]

    generated += next_char
    sentence = sentence[1:] + next_char

generated = ' '.join(word for word in generated.split(' ') if regex.sub('', word.strip()) not in words)[:256]

file = open('out.txt', 'w', encoding='utf8')
file.write(generated)
file.close()

```

## Examples

### De Finibus

> uos et ndllitilum lollreaces vetnocoptam llpe calateciae dorlstem veluatirem.lu ex ept is eptlet neteceppir idararer laror pt lolor.aesuptis caut doquia fiis solopet sen et at nxt at ex ditor aem oond, eo er di iolletiu pllnetaisec cec caperi mi, nd rorxme

## Pride and Prejudice

> Let us at a too appear icovoim to seen adeain and misougnor. Mr. Coilins count; mander it had nearbaryt tordse sithing naly mone agains at tullnearn of alfactained, illed the eavougant one; but her tamed a retoufly gilliction of her may nos. Comberuable.

## Die Verwandlung

> rer du nur ers unbeilnmit und wortst zu dinmaunn.« raue gewisch, schof sau damach.« rang, den sie ihrel erspiefen.
>
> allech gegan kammer mihr ihr, als die Gertüs»allen; den BeHohden, umschof hatee und das höbem In zu neune Stume, daß vornpiel gemößtigeß, am

## Magna Carta

> s by as by geards, and the improved of we renaiss-fur others of any restice of by our welr the issuen the
>
> ard or is Gid insumed to a sarilly ragalint, marners, sim in.
>
> B2. And oney and rentershss lard bagean, in te heish in af any out itfordedvers foroth

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


title: Greek Syllabication (Simplified)

text:
# Question
Title: Greek Syllabication (Simplified)
## INTRO

Let's say you write a passage and you are close to the end of the line wanting to write down a large word. In most languages, you just leave some blank and move to the next line, like a sir.

> Example - English:

blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah this man is unaccountable

But if you are (un)lucky enough to be Greek, when you are close to terminate a line, you cannot just move to the next one. Everything must look nice and in balance, so you SEPARATE the word

> Example - Greek:

μπλα μπλα μπλα μπλα μπλα μπλα μπλα μπλα μπλα μπλα μπλα μπλα αυτός ο άνδρας είναι ανεξή-
γητος

Of course this separation is not done randomly, but instead there is a complicated set of rules, as to how & when to separate, which is actually an entire learning chapter back in primary school that every kid hates.

## OBJECTIVE

You are given a greek word (just a string of greek letters). You need to do a greek syllabication, i.e. separate the greek word in syllabes, according to the set of rules given below, so that the user will have the option to separate the word in the end of the line correctly.

Examples:
1) αγαπη (love) = α-γα-πη
2) ακροπολη (acropolis) = α-κρο-πο-λη
3) βασικα (basically) = βα-σι-κα

## ALPHABET & SIMPLIFIED RULES

**consonants:** β,γ,δ,ζ,θ,κ,λ,μ,ν,ξ,π,ρ,σ,τ,φ,χ,ψ

**vowels:** α,ε,η,ι,ο,υ,ω

**rule 0)** Every vowel defines a different syllable, unless rule 4

**rule 1)** When there is consonant between two vowels, it goes with the second vowel
(ex. γ --\> α-**γ**α-πη)

**rule 2)** When there are two consonants between two vowels, they go with the second vowel, if there is a greek word starting from these two consonants (we assume that that's always the case in our exercise)
(ex. βλ --\> βι-**βλ**ι-ο)

**rule 3)** When we have 3 consonants between two vowels--\>same as rule 2

**rule 4)** Following configurations are considered as "one letter" and are never separated: ει, οι, υι, αι, ου, μπ, ντ, γκ, τσ, τζ
(ex. α-**γκυ**-ρα)

**rule 5)** Always separate same consonants (ex. α**λ-λ**η)

## YOUR TASK

Your code should take as input string (or some other format you wish) a greek word and return the same word, with dashes in between, determining the points where the word can be separated, i.e. do a greek syllabication.

```
TestCases:

[πολη (city)] --> [πο-λη]
[τρεχω (run)] --> [τρε-χω]
[αναβαση (climbing)] --> [α-να-βα-ση]
[οαση (oasis)] --> [ο-α-ση]
[ουρα (tail)] --> [ου-ρα]
[μπαινω (enter)] --> [μπαι-νω]
[εχθροι (enemies)] --> [ε-χθροι]
[ελλαδα (greece)] --> [ελ-λα-δα]
[τυροπιτα (cheese pie)] --> [τυ-ρο-πι-τα]
[αρρωστη (sick)] --> [αρ-ρω-στη]

```

Shortest code wins, but every effort is appreciated :)

# Answer
> 2 votes
# Haskell, 222 201 bytes

```
s""=[]
s x|c?"ειοιυιαιου"=(a++c):s d|h:e:f:g<-b,e==f=(a++[h,e]):s(f:g)|e:f<-b=(a++[e]):s f|2>1=[a]where(a,b)=break(`elem`"αεηιουω")x;(c,d)=splitAt 2 b
i?(x:y:z)=i==[x,y]||i?z
i?""=1>2

```

Try it online!

# Answer
> 2 votes
# Python, 183 bytes

```
def f(s,r=''):
 for p,c in zip(' '+s,s):
  if p in'αεηιουω'and(p+c)not in 'ει,οι,υι,αι,ου,μπ,ντ,γκ,τσ,τζ'or p==c:yield r+p;r=''
  elif p>' ':r+=p
 yield r+c

```

Try it online!

# Answer
> 1 votes
# Bash + sed, ~~188~~ 187 bytes

```
sed -re $(echo 's/([^@\1/\1-\1/g;s/[εουα]ι|ου|μπ|ντ|γκ|τσ|τζ|./-&/g;s/!(!)?(!)?([@/\1\3\5\6/g;s/-([^@(-|$)/\1/g;s/-+/-/g;s/.//'|sed 's/!/([^-@-/g;s/@/αεηιουω])/g')

```

Try it online!

Uses a sed program compressed with... sed. The actual sed program looks like this:

```
# replace consecutive consonants: αρρωστη -> αρ-ρωστη
s/([^αεηιουω])\1/\1-\1/g
# separate "letters": αρ-ρωστη -> -α-ρ---ρ-ω-σ-τ-η
s/[εουα]ι|ου|μπ|ντ|γκ|τσ|τζ|./-&/g
# attach preceding consonants to vowels: -α-ρ---ρ-ω-σ-τ-η -> -α-ρ---ρω-στη
s/([^-αεηιουω])-(([^-αεηιουω])-)?(([^-αεηιουω])-)?([αεηιουω])/\1\3\5\6/g
# attach lone consonants to previous vowel: -α-ρ---ρω-στη -> -αρ--ρω-στη
s/-([^αεηιουω])(-|$)/\1/g
# remove extra dashes: -αρ--ρω-στη -> -αρ-ρω-στη
s/-+/-/g
# remove initial dash: -αρ-ρω-στη -> αρ-ρω-στη
s/.//

```

---
Tags: code-golf, natural-language, word-puzzle
---


# Question
Title: Write program which verifies Erdős–Straus conjecture
Write program, which verifies Erdős–Straus conjecture.
Program should take as input one integer`n` (`3 <= n <= 1 000 000`) and print triple of integers satisfying identity `4/n = 1/x + 1/y + 1/z`, `0 < x < y < z`.

Shortest code wins.

**Some examples:**

```
3 => {1, 4, 12}
4 => {2, 3, 6}
5 => {2, 4, 20}
1009 => {253, 85096, 1974822872}
999983 => {249996, 249991750069, 62495875102311369754692}
1000000 => {500000, 750000, 1500000}

```

Note that your program may print other results for these numbers because there are multiple solutions.

# Answer
### Ruby, 119 106 characters

```
f=->s,c,a{m=s.to_i;c<2?m<s||(p a+[m];exit):(1+m...c*s).map{|k|f[s/(1-s/k),c-1,a+[k]]}}
f[gets.to_r/4,3,[]]

```

The code uses minimal bounds for each variable, e.g. `n/4<x<3n/4`, similarly for `y`. Even the last example returns instantaneous (try here).

Examples:

```
> 12
[4, 13, 156]

> 123
[31, 3814, 14542782]

> 1234
[309, 190654, 36348757062]

> 40881241801
[10220310451, 139272994276206121600, 22828913614743204775214996005450198400]

```
> 12 votes

# Answer
# Mathematica 62

This plain-vanilla solution works fine--most of the time.

```
f@n_ := FindInstance[4/n == 1/x + 1/y + 1/z && 0 < x < y < z, {x, y, z}, Integers]

```

**Examples and Timings (in secs)**

```
AbsoluteTiming[f[63]]
AbsoluteTiming[f[123]]
AbsoluteTiming[f[1003]]
AbsoluteTiming[f[3003]]
AbsoluteTiming[f[999999]]
AbsoluteTiming[f[1000000]]

```

> {0.313671, {{x -\> 16, y -\> 1009, z -\> 1017072}}}
> {0.213965, {{x -\> 31, y -\> 3814, z -\> 14542782}}}
> {0.212016, {{x -\> 251, y -\> 251754, z -\> 63379824762}}}
> {0.431834, {{x -\> 751, y -\> 2255254, z -\> 5086168349262}}}
> {1.500332, {{x -\> 250000, y -\> 249999750052, z -\> 1201920673328124750000}}}
> {1.126821, {{x -\> 375000, y -\> 1125000, z -\> 2250000}}}

---

But it does not constitute a complete solution. There are a some numbers that it cannot solve for. For example,

```
AbsoluteTiming[f[30037]]
AbsoluteTiming[f[130037]]

```

> {2.066699, FindInstance\[4/30037 == 1/x + 1/y + 1/z && 0 \< x \< y \< z, {x, y, z}, Integers\]}
> {1.981802, FindInstance\[4/130037 == 1/x + 1/y + 1/z && 0 \< x \< y \< z, {x, y, z}, Integers\]}
> 7 votes

# Answer
# C#

*Disclamer: this is not a serious answer*

This just bruteforces all the possibilities from 1 to 1\<\<30. It's huge, it's slow, I don't even know if it works correctly, but it follows the specifications quite literally, as it checks the condition every single time, so that's nice. I haven't tested this because ideone has a 5 second time limit for programs and therefore this won't finish executing.

*(In case anyone was wondering: this is a whopping **308 bytes** long)*

```
static double[]f(double n)
{
    for(double x=1;x<1<<30;x++)
    {
        for(double y=1;y<1<<30;y++)
        {
            for(double z=1;z<1<<30;z++)
            {
                if(4/n==1/x+1/y+1/z)
                    return new[]{x,y,z};
            }
        }
    }
    return null;
}

```

*Update: fixed it so it actually works*
> 3 votes

# Answer
# Python 2, 171 bytes

```
from sympy import*
def f(n):
 for d in xrange(1,n*n):
  for p in divisors(4*d+n*n):
   q=(4*d+n*n)/p;x=(n+p)/4;y=(n+q)/4
   if (n+p)%4+(n+q)%4+n*x*y%d<1:return x,y,n*x*y/d

```

Try it online!

The first answer fast enough to be exhaustively tested. This is able to find solutions for all 3 ≤ *n* ≤ 1000000 in about 24 minutes *total*, for an average of about 1.4 milliseconds each.

### How it works

Rewrite 4/*n* = 1/*x* \+ 1/*y* \+ 1/*z* as *z* = *n*·*x*·*y*/*d*, where *d* = 4·*x*·*y**n*·*x**n*·*y*. Then we can factor 4·*d* \+ *n*2 = (4·*x**n*)·(4·*y**n*), which gives us a much faster way to search for *x* and *y* as long as *d* is small. Given *x* \< *y* \< *z*, we can at least prove *d* \< 3·*n*2/4 (hence the bound on the outer loop), although in practice it tends to be much smaller—95% of the time, we can use *d* = 1, 2, or 3. The worst case is *n* = 769129, for which the smallest *d* is 1754 (this case takes about 1 second).
> 3 votes

# Answer
# Python, 117

```
n=input();r=range;z=0
while 1:
 z+=1
 for y in r(z):
  for x in r(y):
    if 4*x*y*z==n*(y*z+x*z+x*y):print x,y,z;exit()

```

Example:

```
16 --> 10 12 15

```

Nothing too special.
> 1 votes

# Answer
## Mathematica, 99 bytes

```
f[n_]:=(x=1;(w=While)[1>0,y=1;w[y<=x,z=1;w[z<=y,If[4/n==1/x+1/y+1/z,Return@{x,y,z}];++z];++y];++x])

```

It's fairly naive brute force, so it doesn't really scale well. I'm definitely going to get to a million (so feel free to consider this invalid for the time being). `n = 100` takes half a second, but `n = 300` already takes 12 seconds.
> 1 votes

# Answer
# Golflua 75

Reads `n` from prompt (after invocation in terminal), but basically iterates as Calvin's Hobbies solution does:

```
n=I.r()z=1@1~@y=1,z-1~@x=1,y-1?4*x*y*z==n*(y*z+x*z+x*y)w(n,x,y,z)~$$$z=z+1$

```

An ungolfed Lua version of the above is

```
n=io.read()
z=1
while 1 do
   for y=1,z-1 do
      for x=1,y-1 do
         if 4*x*y*z==n*(y*z+x*z+x*y) then
            print(n,x,y,z)
            return
         end
      end
   end
   z=z+1
end

```

Examples:

```
n=6     -->     3      4     12
n=12    -->     6     10     15
n=100   -->    60     75    100
n=1600  -->  1176   1200   1225

```
> 1 votes

# Answer
# C# - 134

Well, I posted an answer here before, but it wasn't really that serious. As it so happens, I'm very often very bored, so I golfed it a little bit.

It calculates all the examples *technically* correctly (I haven't tried the last two because, again, ideone inforces a 5 second time limit) but the first ones yield the correct result (not necessarily the result you calculated, but a correct one). It strangely outputs the number out of order (I have no clue why) and it gives `10, 5, 2` for `5` (which is a valid answer according to wikipedia).

134 bytes for now, I could probably golf it up a bit more.

```
float[]f(float n){float x=1,y,z;for(;x<1<<30;x++)for(y=1;y<x;y++)for(z=1;z<y;z++)if(4/n==1/x+1/y+1/z)return new[]{x,y,z};return null;}

```
> 0 votes

# Answer
### Haskell - 150 characters

`main = getLine >>= \n -> (return $ head $ [(x,y,z) | x <- [1..y], y <- [1..z], z <- [1..], (4/n') == (1/x) + (1/y) + (1/z)])
 where n' = read n`

This ought to work, but I've not compiled it yet. It's almost certainly very very slow. It checks every possible triplet of valid integers, and should stop when it sees a set that works.
> 0 votes

---
Tags: code-golf, math, number-theory
---


title: Square root a number

text:
# Question
Title: Square root a number
The task is as follows: Given a positive integer `x` and a prime `n > x`, output the smallest positive integer `y` such that `(y * y) mod n = x`. An important part of this question is the time limit specified below which excludes brute force solutions.

If there is no such value `y` then your code should output `N`.

**Test cases**

```
(2, 5, N),
(3, 5, N),
(4, 5, 2),
(524291, 1048583, N),
(529533, 1048583, N),
(534775, 1048583, 436853),
(540017, 1048583, 73675),
(536870913, 1073741827, 375394238),
(542239622, 1073741827, 267746399),
(547608331, 1073741827, N),
(552977040, 1073741827, 104595351),
(1099511627676, 1099511627791, N),
(1099511627677, 1099511627791, 269691261521),
(1099511627678, 1099511627791, 413834069585),
(1267650600228229401496703204376, 1267650600228229401496703205653, 5312823546347991512233563776),
(1267650600228229401496703204476, 1267650600228229401496703205653, N)
(1267650600228229401496703204576, 1267650600228229401496703205653, N)
(1267650600228229401496703204676, 1267650600228229401496703205653, 79905476259539917812907012931)

```

**Input and output**

You may take input and give output in any way that is convenient. If you don't like to output `N` then any `Falsey` value will do.

**Restrictions**

Your code must answer all the test cases in under 1 minute on a standard desktop. This time limit is only to prevent brute force answers and I expect good answers to run almost instantly. You may not use any library or builtin that solves this problem or that tests if a number is a quadratic residue.

# Answer
> 8 votes
# Pyth, ~~83~~ 82 bytes

```
=eAQM.^GHQKf%=/H=2;1=gftgT/Q;1HJg~gGHh/H2WtG=*J=gT^2t-K=Kfq1gG^2T1=%*G=^T2Q;hS%_BJ

```

Test suite

This program implements the Tonelli-Shanks algorithm. I wrote it by closely following the Wikipedia page. It takes as input `(n, p)`.

The absence of a square root is reported by the following error:

```
TypeError: pow() 3rd argument not allowed unless all arguments are integers

```

---

This is very intricately golfed code, written in the imperative style, as opposed to the more common functional style of Pyth.

The one subtle aspect of Pyth I'm using is `=`, which, if not immediately followed by a variable, searches forward in the program for the next variable, then assigns the result of the following expression to that variable, then returns that result. I will refer throughout the explanation to the wikipedia page: Tonelli-Shanks algorithm, as that is the algorithm I am implementing.

**Explanation:**

```
=eAQ

```

`A` takes a 2-tuple as input, and assigns the values to `G` and `H` respectively, and returns its input. `Q` is the initial input. `e` returns the last element of a sequence. After this snippet, `G` is `n`, and `H` and `Q` are `p`.

```
M.^GHQ

```

`M` defines a 2 input function `g`, where the inputs are `G` and `H`. `.^` is Pyth's fast modular exponentiation function. This snippet defines `g` to mean exponentiation mod `Q`.

```
Kf%=/H=2;1

```

`f` defines a repeat until false loop, and returns the number of iterations it runs for, given `1` as its input. During each iteration of the loop, we divide `H` by 2, set `H` to that value, and check whether the result is odd. Once it is, we stop. `K` stores the number of iterations this took.

One very tricky thing is the `=2;` bit. `=` searches ahead for the next variable, which is `T`, so `T` is set to 2. However, `T` inside an `f` loop is the iteration counter, so we use `;` to get the value of `T` from the global environment. This is done to save a couple of bytes of whitespace that would otherwise be needed to separate the numbers.

After this snippet, `K` is `S` from the wikipedia article (wiki), and `H` is `Q` from the wiki, and `T` is `2`.

```
=gftgT/Q;1H

```

Now, we need to find a quadratic nonresidue mod `p`. We'll brute force this using the Euler criterion. `/Q2` is `(p-1)/2`, since `/` is floored division, so `ftgT/Q;1` finds the first integer `T` where `T ^ ((p-1)/2) != 1`, as desired. Recall that `;` again pulls `T` from the global environment, which is still 2. This result is `z` from the wiki.

Next, to create `c` from the wiki, we need `z^Q`, so we wrap the above in `g ... H` and assign the result to `T`. Now `T` is `c` from the wiki.

```
Jg~gGHh/H2

```

Let's separate out this: `~gGH`. `~` is like `=`, but returns the original value of the variable, not its new value. Thus, it returns `G`, which is `n` from the wiki.

This assigns `J` the value of `n^((Q+1)/2)`, which is `R` from the wiki.

Now, the following takes effect:

```
~gGH

```

This assigns `G` the value `n^Q`, which is `t` from the wiki.

Now, we have our loop variables set up. `M, c, t, R` from the wiki are `K, T, G, J`.

The body of the loop is complicated, so I'm going to present it with the whitespace, the way I wrote it:

```
WtG
  =*J
    =
      gT^2
        t-
          K
          =Kfq1gG^2T1
  =%*G=^T2Q;

```

First, we check whether `G` is 1. If so, we exit the loop.

The next code that runs is:

```
=Kfq1gG^2T1

```

Here, we search for the first value of `i` such that `G^(2^i) mod Q = 1`, starting at 1. The result is saved in `K`.

```
=gT^2t-K=Kfq1gG^2T1

```

Here, we take the old value of `K`, subtract the new value of `K`, subtract 1, raise 2 to that power, and then raise `T` to that power mod `Q`, and then assign the result to `T`. This makes `T` equal to `b` from the wiki.

This is also the line which terminates the loop and fails if there is no solution, because in that case the new value of `K` will equal the old value of `K`, 2 will be raised to the `-1`, and the modular exponentiation will raise an error.

```
=*J

```

Next, we multiply `J` by the above result and store it back in `J`, keeping `R` updated.

```
=^T2

```

Then we square `T` and store the result back in `T`, setting `T` back to `c` from the wiki.

```
=%*G=^T2Q

```

Then we multiply `G` by that result, take it mod `Q` and store the result back in `G`.

```
;

```

And we terminate the loop.

After the loop's over, `J` is a square root of `n` mod `p`. To find the smallest one, we use the following code:

```
hS%_BJ

```

`_BJ` creates the list of `J` and its negation, `%` implicitly takes `Q` as its second argument, and uses the default behavior of Pyth to apply `% ... Q` to each member of the sequence. Then `S` sorts the list and `h` takes its first member, the minimum.

# Answer
> 11 votes
# Python 2, 166 bytes

```
def Q(x,n,a=0):
 e=n/2
 while pow(a*a-x,e,n)<2:a+=1
 w=a*a-x;b=r=a;c=s=1
 while e:
    if e%2:r,s=(r*b+s*c*w)%n,r*c+s*b
    b,c=(b*b+c*c*w)%n,2*b*c;e/=2
 return min(r,-r%n)

```

# Answer
> 6 votes
# SageMath, 93 bytes

By reduction to a much harder problem for which SageMath happens to have fast enough builtins.

```
def f(x,n):g=primitive_root(n);k=Zmod(n)(x).log(g);y=pow(g,k//2,n);return k%2<1and min(y,n-y)

```

Try it on SageMathCell

# Answer
> 3 votes
# Haskell, 326 bytes

Usually I like brute force answers.. Since this is strongly discouraged by the time limit, here's the most efficient way I know of:

```
r p=((\r->min(mod(-r)p)r)$).f p
f p x|p==2=x|q x=f 0 0|mod p 4==3=x&div(p+1)4|let(r,s)=foldl i(p-1,0)[1..t 1o]=m$x&(d$r+1)*(b&d s)where q a=1/=a&o;m=(`mod`p);a&0=1;a&e|even e=m$a&d e^2|0<1=m$(a&(e-1))*a;b=[n|n<-[2..],q n]!!0;i(a,b)_|m(x&d a*b&d b)==p-1=(d a,d b+o)|0<1=(d a,d b);o=d p;t y x|even x=t(y+1)(d x)|0<1=y;d=(`div`2)

```

Try it online!

I'm sure this can be golfed down further, but this should do for now.

---
Tags: code-golf, math, abstract-algebra, restricted-time
---


title: Create unique ids

text:
# Question
Title: Create unique ids
You are to write a program that takes a list of strings as input. For every string in the list you are to determine the smallest **N** such that no other string in the list begins with the same **N** characters as the string in question. Now compose a new list with all these strings. Here is an example, on the left we have the input and on the right we have the output

```
aba                   aba
aababba               aa
abbaaabbb          -> abba
bbbbbbabababaaab      b
abbbabbaa             abbb

```

If a there is a string that is also the beginning of another string you should append a `$` to the end to represent the end of the string. Here is an example where that is the case

```
ababababbabab         abababa
ababbbaabababa        ababbb
ababb                 ababb$
bababba            -> bababb
bbbabababab           bb
bababababbabab        bababa
abababbababa          abababb

```

## Rules

* Input will only contain alphabetic characters.
* You will not receive a list with the same entry twice.
* You take input in any ordered container.
* This is , you should aim to minimize the byte size of your program.

# Answer
> 6 votes
# Husk, ~~14~~ ~~13~~ 12 bytes

```
Ṡzo↑▲‡Ṫ≠TT'$

```

Try it online!

Less than half the length of the previous best solution!

### Explanation

```
Ṡzo↑▲‡Ṫ≠TT'$
        TT'$     Pad all strings to equal length by appending dollar signs

     ‡Ṫ≠         Create a 2D matrix with all pairwise differences between
                 strings. ≠ returns the smallest index at wich two lists differ
                 (or 0, if they are equal)

Ṡzo↑▲            For each string, take as many characters as the maximum number
                 in its row of the table.

```

Since my explanation may not be that clear, here's a small worked example:

Starting list: `["abc","abd","b","bcd"]`

Table of differences:

```
     abc abd  b  bcd     max
 abc  0   3   1   1       3
 abd  3   0   1   1       3
 b    1   1   0   2       2
 bcd  1   1   2   0       2

```

So we take from each string (with added trailing '$') as many characters as stated in the "max" column.

Final result: `["abc","abd","b$","bc"]`

# Answer
> 3 votes
# Haskell, ~~83~~ 79 bytes

```
f l|let h=map(++"$")l;w x|y<-init x,2>sum[1|z<-h,y<=z,y++"{">z]=w y|1<3=x=w<$>h

```

Try it online! Example usage: `f ["abcd","abh","ab","bacd"]` yields `["abc","abh","ab$","b"]`.

Given a list of strings, the function `f` appends a trailing `$` and applies `w` to each string, where `w` iteratively drops the last character of the string (with `init`) until the next application of `init` would lead to the string now longer being a unique prefix.

**Edit:** Three bytes off thanks to Ørjan Johansen's shorter prefix test!

# Answer
> 3 votes
# Jelly,  ~~28 26~~  16 bytes

-10 bytes by implementing the algorithm found by Leo in their brilliant Husk answer.

```
i€0Ṁḣ@
;€”$µ=þç"

```

or...

```
;€”$µ=i0µþ⁸Ṁ€⁸ḣ"

```

A monadic link taking and returning lists of lists of characters.

**Try it online!** (the footer makes a full program which prints the result split by newlines.)

### How?

```
i€0Ṁḣ@ - helper link, create an entry of the output: equality row, string with trailing '$'
i€0    - first index of zero in €ach entry of the row
   Ṁ   - maximum
    ḣ@ - head to index with swapped @rguments (the prefix of the string)

;€”$µ=þç" - link: list of lists of characters (list of "strings")
  ”$      - literal '$'
;€        - concatenate for €ach
    µ     - monadic chain separation (call that x)
      þ   - table of (with x on the left and, implicitly, on the right):
     =    -   equals? (vectorises)
        " - zip with (with the table on the left and, implicitly, x on the right)
       ç  - call the last link as a dyad

```

---

My original:

-2 bytes thanks to Erik the Outgolfer (replace `ḣJ$` with `;\` and `ẎċÐ€Ð€$` with `ċ@€€Ẏ$`)

```
NMḢ⁹ḣ;⁸Ṃẋ@”$¤Ṗ
;\€ċ@€€Ẏ$ç"

```

A monadic link taking and returning lists of lists of characters.

**Try it online!** (the footer makes a full program which prints the result split by newlines.)

I'm ~~almost~~ certain this is beatable, and ~~probably~~ by a decent margin! (although I have attempted to golf the method.)

The same byte count may be achieved without a helper link too, with:

```
ḣJ$€ẎċÐ€Ð€$ðNMḢ⁹ḣ;⁸Ṃẋ@”$¤Ṗð"

```

### How?

Note: the reusable link is the second line of code, so start there.

```
NMḢ⁹ḣ;⁸Ṃẋ@”$¤Ṗ - helper link, create an entry of the output: prefix counts, string
               -   ("prefix counts" should be counts of the prefixes of the "string" in
                    the totality of prefixes of *all* the strings)
N              - negate the counts
 M             - maximal indexes (lengths of prefixes appearing least often, ascending)
  Ḣ            - head (finds the minimal length required), call that ml
   ⁹           - chain's right argument (prefixes)
    ḣ          - head (string) to index ml (gets the minimal length prefix)
            ¤  - nilad followed by links as a nilad:
      ⁸        -   chain's left argument (prefix counts)
       Ṃ       -   minimum (this will either be 1 or 2)
          ”$   -   literal '$'
        ẋ@     -   repeat with swapped @rguments (either "$" or "$$")
     ;         - concatenate
             Ṗ - pop (remove the last "$" - leaving one where the prefix occurs in another
               -      string's prefixes, and none otherwise)

;\€ċ@€€Ẏ$ç" - link: list of lists of characters (list of "strings")
  €         - for €ach string
 \          -   cumulative reduce with:
;           -     concatenation
            - (gets a list of lists of prefixes)
        $   - last two links as a monad:
       Ẏ    -   tighten (flatten by one to make a single list of all prefixes)
    @       -   swap arguments
     €€     -     for each prefix in each list of prefixes
   ċ        -       count occurrences in the tightened list (>=1 since it counts itself)
          " - zip with the dyad (right argument is this link's argument):
         ç  -   last link (helper) as a dyad

```

# Answer
> 2 votes
# Haskell, ~~109~~ ~~104~~ ~~98~~ ~~97~~ ~~90~~ ~~84~~ 83 bytes

Probably not very good but Hopefully this will kick things off a bit.

```
f s=[[x|x<-map(`take`(a++"$"))[0..],[1]==[1|d<-s,and$zipWith(==)x$d++"$"]]!!0|a<-s]

```

Try it online!

# Answer
> 1 votes
## JavaScript (ES6), ~~89~~ 86 bytes

```
a=>a.map(g=(s,i,a,t=s+'$')=>a.some((t,j)=>j-i&&!t.search(s))?t:g(s.slice(0,-1),i,a,s))

```

Edit: Saved 3 bytes thanks to @CraigAyre. (Supporting arbitrary characters would still have saved two bytes using `!t.indexOf(s)`.)

# Answer
> 0 votes
# PHP, ~~155 129~~ 102 bytes

```
for(;++$k<$argc;$t=!print"$t
")for($i=0;count(preg_grep("_^".($t.=$argv[$k][$i++]?:"$")._,$argv))>1;);

```

expects input to not contain regex special chars and that no argument is `-`.
Run with `php -nr <word> <word> ...` or try it online.

**breakdown**

```
for(;++$k<$argc;            # loop through arguments
    $t=!print"$t\n")            # 2. print $t, reset $t
    for($i=0;                   # 1. loop through string:
    1<count(preg_grep("_^".(        # 2. continue while more than one argument begins with $t
        $t.=$argv[$k][$i++]?:"$"    # 1. append current character or "$" to $t
    )._,$argv)););

```

# Answer
> 0 votes
# Mathematica, 141 ~~142~~ bytes

```
g[x_:0,___]:=x;f=#<>""&/@(Thread@h[x=#~PadRight~99&/@(Characters[#<>"$"]&/@#),Max/@Outer[g@@Join@@Position[#-#2,y_/;y!=0]&,x,x,1]]/.h->Take)&

```

I think I can golf it a bit. The code doesn't work on Mathics so you may use Wolfram Sandbox to test.

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


title: Write a Stepping Quine

text:
# Question
Title: Write a Stepping Quine
*Related*

Your goal, is to write a set of programs, that progresses from one to the other, one character at a time. For example. Given the starting program `abcd` and the ending program `wxyz`, you should have 5 valid programs, with the respective outputs.

```
abcd -> wbcd
wbcd -> wxcd
wxcd -> wxyd
wxyd -> wxyz
wxyz -> wxyz

```

As can be seen, the last program should be a quine.

## Rules

* Your start and end program may be any length, And they may also be different lengths
* Your start and end program must contain entirely unique characters at each position, but may share characters overall.
* Each program should affect a single character at a time, in any order, characters should only be added or removed from the end of the program.
* **None** of your programs need to follow the valid quine rules, they only need to output the correct string.
* Standard Loopholes Apply.

## Scoring

Programs are scored by the length of the start program plus the length of the end program in bytes. In the previous example, `4 + 4 = 8`, so the score is eight. This is , so shortest programs wins.

## Some Valid Programs

*In languages that hopefully don't exist*

```
abcd -> dbcd -> dccd -> dcbd -> dcba
a -> b
a -> b -> bc -> bcd -> bcde
ab -> aa -> ba
[BLANK PROGRAM] -> a
xyz -> xy -> x -> [BLANK PROGRAM]

```

# Answer
# Retina, Score 1

```

```

Try it online!

* The empty program outputs `1`, since the empty input matches the empty string exactly once.
* `1` outputs `0`, since `1` doesn't match the empty input.
* `0` outputs `0`, since `0` doesn't match the empty input. Since it outputs itself, it's a quine (as defined in this challenge).
> 5 votes

# Answer
# 05AB1E, Score 1

```
=

```

Try it online!

`=` prints top of stack (nothing) without newline.

(empty program) also generates no output.

Boring solution, but it works.
> 1 votes

# Answer
# Braingolf, Score 2

```
/

```

Try it online!

Niladic `/` pushes `5`, with implicit output, `5` also pushes `5`.
> 0 votes

# Answer
# Japt, Score 2

```
T

```

**Output:** `0` (Test it)

---

```
0

```

**Output:** `0` (Test it)

---

Any uppercase letter after `T` would also work in the same way.
> 0 votes

---
Tags: code-golf, quine
---


# Question
Title: Fibtraction - Fibonacci but with subtraction
The Fibtraction sequence (as I call it) is similar to the Fibonacci sequence except, instead of adding numbers, you subtract them.

**The first few numbers of this challenge are:**

```
1, 2, -1, 3, -4, 7, -11, 18, -29, 47, -76, 123, -199, 322, -521, 843, -1364...

```

The sequence **starts with 1 and 2**. Every next number can be calculated by subtracting the previous number from the number before it.

```
1
2
-1 = 1 - 2
3  = 2 - (-1) = 2 + 1
-4 = -1 - 3
7  = 3 - (-4) = 3 + 4
...

```

In other words:

```
f(1) = 1
f(2) = 2
f(n) = f(n - 2) - f(n - 1)

```

This is OEIS sequence A061084.

## Challenge

Write a **program/function** that takes a positive integer **n** as input and prints the **nth number of the Fibtraction sequence**.

### Specifications

* Standard I/O rules apply.
* Standard loopholes are **forbidden**.
* Your solution **can either be 0-indexed or 1-indexed** but please specify which.
* This challenge is not about finding the shortest approach in all languages, rather, it is about finding the **shortest approach in each language**.
* Your code will be **scored in bytes**, usually in the encoding UTF-8, unless specified otherwise.
* Built-in functions that compute this sequence are **allowed** but including a solution that doesn't rely on a built-in is encouraged.
* Explanations, even for "practical" languages, are **encouraged**.

## Test cases

These are 0-indexed.

```
Input      Output

1          2
2          -1
11         123
14         -521
21         15127
24         -64079
31         1860498

```

That pattern was totally not intentional. :P

This challenge was sandboxed.

> Before you go pressing any buttons that do scary things, hear me out. This might be considered a dupe of the regular Fibonacci challenge and I agree, to some extent, that it should be easy enough to port solutions from there. However, the challenge is old and outdated; is severely under-specified; allows for two types of solutions; has answers that don't have easy ways to try online; and in general, is lacking of answers. Essentially, in my opinion, it doesn't serve as a good "catalogue" of solutions.

plz send teh codez

# Answer
> 26 votes
# Oasis, 4 bytes

```
c-21

```

Try it online!

0-indexed.

I saw this language used for a similar challenge once, and immediately I knew I should try it here. Can't say I'm disappointed.

### Explanation

```
   1    a(0) = 1
  2     a(1) = 2
c       a(n) = a(n - 2)
 -                      - a(n - 1)

```

# Answer
> 12 votes
# Python 2, 35 34 bytes

 -1 byte thanks to ovs!

```
f=lambda n:n*(n<3)or f(n-2)-f(n-1)

```

Try it online!

Answers are 1-indexed. Takes advantage of `f(2)` and `f(1)` being equal to their respective inputs.

# Answer
> 10 votes
## Javascript, 24 bytes

```
f=n=>n<3?n:f(n-2)-f(n-1)

```

```
f=n=>n<3?n:f(n-2)-f(n-1)

for (let i = 1; i <= 20; i++) {
  console.log(f(i))
}
```

# Answer
> 9 votes
# Octave, 27 bytes

0-indexed.

```
@(n)([1,2]*[0,1;1,-1]^n)(1)

```

Try it online!

# Answer
> 8 votes
# Haskell, ~~29~~ 26 bytes

Inspired by alephalpha's answer I thought, I'd derive an explicit formula. It's been a while since I did an Eigenvalue decomposition, turns out the explicit formula (even after golfing it down) is longer and fails because of floating point issues.

0-indexed:

```
(g!!)
g=1:scanl(flip(-))2g

```

Try it online!

Saved 3 bytes thanks to @Laikoni

## Decomposition solution, 48 bytes

There are a couple eigenvector decompositions; the simplest is actually -1-indexed rather than 0-indexed or 1-indexed:

```
Prelude> map (\n -> ((-1 + sqrt 5)/2)**n + ((-1 - sqrt 5)/2)**n) [0..10]
[2.0,-1.0,3.0,-4.0,7.0,-11.0,18.0,-29.000000000000004,47.0,-76.0,123.0]

```

Since the `(-1 + sqrt 5)/2` term is less than 1, we can absorb that into the needed `round` at the cost of adding some leading terms,

```
Prelude> [round$((-1 - sqrt 5)/2)^n|n<-[0..10]]
[1,-2,3,-4,7,-11,18,-29,47,-76,123]

```

So e.g. one can get to a function by, but this is not much-more golfable and it's 48 bytes:

```
((1:2: -1:[round$(-(1+sqrt 5)/2)^n|n<-[2..]])!!)

```

Try it online!

# Answer
> 8 votes
# x86 Machine Code, 12 bytes

**Iterative solution; 0-indexed**

```
31 C0
40
8D 50 01
29 D0
92
E2 FB
C3

```

The above function takes a single input, *n* (passed in the `ECX` register, following Microsoft's fastcall calling convention), and returns the *n*th number of the Fibtraction sequence in the `EAX` register.

The implementation is based on the well-known trick for calculating a Fibonacci number using two variables, which Snowman's answer in Java reminded me of.

Not only is this solution *much smaller* in size than my first attempt (it even competes with Mathematica using a built-in), it will also be *much faster* because it is iterative, rather than recursive. Theoretical comp-sci's love for recursion is foiled once more!

**Ungolfed assembly mnemonics:**

```
Fibtraction:
   xor  eax, eax
   inc  eax                ; EAX = 1  (XOR+INC are 3 bytes; same as PUSH+POP)
   lea  edx, [eax + 1]     ; EDX = 2  (LEA is 3 bytes; same as PUSH+POP)
Iterate:
   sub  eax, edx           ; EAX = EAX - EDX
   xchg eax, edx           ; swap EAX and EDX
   loop Iterate            ; decrement ECX and keep looping as long as ECX != 0
   ret                     ; return, with result in EAX

```

**Try it online!**

A couple of things worth pointing out here…

* We start by loading the constants 1 and 2 into registers. These are our starting values. The standard way, of course, to load constants into registers is `mov reg, imm`. That's fast, but it takes a whopping *5 bytes* to encode. So, for code-golfing purposes, we make use of various other tricks to load values into registers. A 2-byte `PUSH` that pushes the immediate value onto the stack, followed by a 1-byte `POP` that pops the value off the top of the stack and into a register, is the workhorse trick—very common and very useful. But, if you are just setting the register to 1, you can do `XOR`+`INC`, which is the same 3 bytes. And, if you already have the value you want in a register, then you can build off of it using the magic `LEA` instruction, which is also only 3 bytes. Both of those tricks are showcased here, since they are more interesting and somewhat faster than the good old `PUSH`+`POP`.
* Inside of the body of the loop, we do a pretty neat optimization. The fundamental operation we're doing here is:

```
edx = (eax - edx)
eax -= edx

```

which would naively be translated to (indeed, this is what most C compilers do):

```
sub  eax, edx                              ; 2 bytes
mov  ebx, edx                              ; 2 bytes
mov  edx, eax                              ; 2 bytes
mov  eax, ebx                              ; 2 bytes

```

or, somewhat better—rewrite the subtraction as addition of a negative so that the operand order can be reversed, allowing the result to end up in the desired register without having to clobber a temporary register (ICC is able to apply this optimization):

```
neg  edx                                   ; 2 bytes
add  edx, eax     ; edx = (eax - edx)      ; 2 bytes
sub  eax, edx     ; eax -= edx             ; 2 bytes

```

but I have written it as:

```
sub  eax, edx                              ; 2 bytes
xchg eax, edx                              ; 1 byte

```

which is conceptually similar to the naive version (only one subtraction is done, then some moves), but much more compact because of the `XCHG` instruction. This avoids clobbering a register, and decreases the size of the code. (I guess you could have equally well used an `XOR` to avoid clobbering a register—the famous move-without-a-temporary trick—but `XCHG` is 1 fewer byte for golfing purposes.)

Now, to be fair, the `MOV`s are probably much faster in real-world code, especially on modern processors that can elide moves in the front end via register renaming. Exchanges can't be elided, and aren't known for being particularly fast. If it weren't for register renaming, ICC's code (the add-a-negative approach) would probably be the fastest in the real-world, since it's compact and arithmetic operations are extremely efficient.
* The `LOOP` instruction. This is an old CISC-style instruction that is equivalent to:

```
dec  ecx
jnz  Label

```

but is avoided in modern code (and by all compilers) because it's actually *slower* than the above sequence. It's also less versatile, because it has the `ECX` register hard-coded as the counter. However, for code-golf purposes, it's great! And since we used a calling convention that passes the parameter in `ECX`, we don't even have to do anything!

(If you wanted to use a different calling convention, you'd just have to do a `MOV` or `XCHG` at the very top of the function to copy the parameter into `ECX`; or, you could swap out the `LOOP` instruction for the expanded form shown above. Either of these would only cost a couple of bytes, maximum, so this optimization isn't really saving us much, but I think it does earn a couple of *style* points! :-)

Similarly, if you wanted to write this for x86-64, like my original answer, which uses a different calling convention, it would be easy to adapt. Either of these will do it, and both are only 14 bytes:

```
Fibtraction_64_A          |      Fibtraction_64_B:
   push 1                 |         mov  ecx, edi
   pop  rax               |         push 1
   lea  edx, [rax+1]      |         pop  rax
Iterate:                  |         lea  edx, [rax+1]
   sub  eax, edx          |      Iterate:
   xchg eax, edx          |         sub  eax, edx
   dec  edi               |         xchg eax, edx
   jg   Iterate           |         loop Iterate
   ret                    |         ret

```

# Answer
> 6 votes
# 05AB1E, 7 bytes

```
3XIFDŠ-

```

Try it online!

**Explanation**

```
3         # push 3
 X        # push 1
  IF      # input times do:
    D     # duplicate top of stack
     Š    # move the copy down 2 spaces on the stack
      -   # subtract top 2 numbers

```

# Answer
> 6 votes
# cQuents, 8 bytes

```
=1,2:y-z

```

1-indexed. Since cQuents isn't stack based it isn't as terse as Oasis. Prints the whole sequence if no input is given.

Try it online!

### Explanation

```
=1,2      Sequence start equals 1,2
    :     Mode: sequence. Prints the 1-indexed nth term for input n.
     y-z  Each item in the sequence equals the second to last item minus the last item

```

# Answer
> 6 votes
# Jelly, 5 bytes

```
1_@¡3

```

0-indexed.

Try it online!

# Answer
> 6 votes
# Perl 6, 19 bytes

```
{(1,2,*-*...*)[$_]}

```

test it

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣
  (

    1, 2,  # seed the sequence

    * - *  # WhateverCode lambda used to generate the rest of the values

    ...    # keep generating until:

    *      # never stop

  )[ $_ ]  # index into the sequence
}

```

# Answer
> 6 votes
## Mathematica (using a built-in), ~~18~~ 12 bytes

*Several bytes saved by user202729 !*

```
LucasL[2-#]&

```

Or the same idea without a built-in, for ~~32~~ ~~31~~ ~~30~~ 29 bytes:

```
Tr[{p=(1+5^.5)/2,1-p}^(2-#)]&

```

Uses 1-indexing. Try them at the Wolfram sandbox (they don't work in Mathics, unfortunately).

This uses the observation by ETHproductions and user202729 that the sequence is nearly the Lucas numbers (only with alternating sign, or reading backwards). The 29-byte function is the closed formula for the Lucas numbers.

# Answer
> 5 votes
# Mathics, 31 bytes

```
f@1=1
f@2=2
f@x_:=f[x-2]-f[x-1]

```

-2 thanks to @MartinEnder!

Try it online!

# Answer
> 5 votes
# Brainfuck, ~~51~~ 44 bytes

```
+++++>+>++<<[>[>>+<<-]>[<+>>-<-]>[<+>-]<<<-]

```

0-indexed, the input is on cell 0 and the output on cell 1.

Output is in two complement format.

Per this meta consensus, input for Turing machines may be written to the tape pre-execution, and the contents of the tape post-execution may be used as a Turing machine's output.

**How?**

```
# The tape: I O A B . . .
# I = input, O = output

>+     # O = 1
>++    # A = 2
<<[
    >[>>+<<-]     # B = O              [ I   0   A   O  ]
    >[<+>>-<-]    # B = B - A, O = A   [ I   A   0  O-A ]
    >[<+>-]<<<    # A = B = O - A      [ I   A  O-A  0  ]
-]     # Repeat I times

```

# Answer
> 4 votes
# PHP, 45 bytes

0-indexed

```
for($x=1,$y=2;$argn--;)$x=$x-$y=$x-$y;echo$x;

```

Try it online!

# PHP, 46 bytes

1-indexed recursive function

```
function f($i){return$i<3?$i:f($i-2)-f($i-1);}

```

Try it online!

# Answer
> 4 votes
# Java, ~~65~~ 61 bytes

Golfed:

```
n->{int a=1,b=2;for(;n-->0;a-=b)b=a-b;System.out.println(a);}

```

This uses the standard trick of calculating Fibonacci using only two variables to hold the state, but modified to work with subtraction. I am aware that theoretically, `System.out.print()` *should* work here but in practice it is inconsistent with flushing output and sometimes (often enough to be an issue) will literally print *nothing* using the Oracle JVM.

This function is zero-indexed.

Try it online!

Ungolfed:

```
public class FibtractionFibonacciButWithSubtraction {

  public static void main(String[] args) {
    for (int i : new int[] { 1, 2, 11, 14, 21, 24, 31 }) {
      f(n -> {
        int a = 1, b = 2;
        for (; n-- > 0; a -= b)
          b = a - b;
        System.out.println(a);
      } , i);
    }
  }

  private static void f(java.util.function.Consumer<Integer> function, int n) {
    function.accept(n);
  }
}

```

# Answer
> 3 votes
# C, 30 bytes

**Try Online** 1-indexed

```
s;f(n){s=n>2?f(n-2)-f(n-1):n;}

```

# Answer
> 2 votes
# Pari/GP, 26 bytes

```
n->([1,2]*[0,1;1,-1]^n)[1]

```

Try it online!

# Answer
> 2 votes
# Common Lisp, 46 bytes

```
(defun f(n)(if(< n 3)n(-(f(- n 2))(f(1- n)))))

```

Try it online!

1-indexed, plain recursive solution.

# Answer
> 2 votes
## R, 38 bytes

```
f=function(n)`if`(n<3,n,f(n-2)-f(n-1))

```

1-indexed solution

**Explanation :**

The `'if'` function has the same syntax as `ifelse` : `ifelse(test, TRUE, FALSE)`.

In this solution, we create a function `f` that begins to test if the input `n` is strictly inferior to `3` (i.e. equals to 1 or 2 ; `test` part of the `'if'`). If its the case, the output is simply the input (`TRUE` part).

The function otherwise recursively calls itself and outputs the final result (`FALSE` part)

# Answer
> 2 votes
# Mini-Flak, 72 bytes

(1-indexed)

```
({}(()()())(())[()()()()]){({}(([{}]({})))[({}([{}]{})[({})])][()])}{}{}
```

Try it online!

The TIO links have more comments, so it is easier to understand.

# Answer
> 2 votes
# Charcoal, 34 33 bytes

```
Ａ¹αＡ²βＦ…²θ¿﹪ι²Ａ⁻βαβＡ⁻αβα⎇﹪Ｉθ²ＩαＩβ

```

Try it online!

1-indexed. I insist on writing answers in a language with a totally different purpose... Link to the verbose version.

# Answer
> 2 votes
# x86-64 Machine Code, 29 bytes

**Simple recursive solution; 1-indexed**

The following is a function written according to the System V AMD64 calling convention that computes and returns the *n*th number of the Fibtraction sequence. The sole parameter, *n*, is passed in the `EDI` register. The function returns its result in the `EAX` register.

```
53
51
89 F9
83 EF 02
7E 10
E8 00 00 00 00
8D 79 FF
91
E8 00 00 00 00
29 C1
91
59
5B
C3

```

Try it online! (Hey, I finally figured out how to make TIO work for assembly language! Ignore the ugly boilerplate to print numbers… :-p)

**Ungolfed assembly mnemonics:**

```
Fibtraction:
   push     rbx           ; preserve original value in EBX
   push     rcx           ; preserve original value in ECX
   mov      ecx, edi      ; preserve original 'n' in ECX
   sub      edi, 2        ; EDI = n - 2
   jle      .Finished     ; if n <= 2, we're done (base case for recursion)
   call     Fibtraction   ; compute f(EDI), which is f(n - 2)
   lea      edi, [rcx-1]  ; EDI = n - 1
   xchg     eax, ecx      ; save result of f(n-2) in ECX (which we can now safely clobber)
   call     Fibtraction   ; compute f(EDI), which is f(n - 1)
   sub      ecx, eax      ; calculate f(n - 2) - f(n - 1)
.Finished:                ; fall through...
   xchg     eax, ecx      ; move result from ECX into EAX
   pop      rcx           ; restore original value to ECX
   pop      rbx           ; restore original value to EBX
   ret                    ; return, with result in EAX

```

Okay, it's assembly language, so there are no fancy built-ins to help us. But just look at all of those 1-byte opcodes! `PUSH`, `POP`, and `XCHG` are all very handy here.
These `XCHG` instructions are really just substitutions for register-to-register `MOV`es. We don't actually need to exchange the values; we just care about a one-way movement. But, although normally `MOV reg, reg` and `XCHG reg, reg` are both 2 bytes, there is a special 1-byte encoding for `XCHG` when one of the operands is the accumulator (`EAX`). Thus, this substitution saves us a few bytes (at the possible expense of speed).

The only long, ugly instructions are the `CALL`s, used to invoke the function recursively. (Technically, all of those 0s in the opcodes get replaced by the linker with the function's actual 32-bit relative displacement when the code gets linked, but the resulting binary will be the same size in bytes because this won't change the *length* of the instruction.) But there isn't really anything we can do to reduce the size. `CALL` can be emulated as `PUSH`+`JMP`, but just the `PUSH` instruction alone consumes more bytes than `CALL`!

The recursive nature of this algorithm made it a fun and interesting challenge—to me, at least. It's not very often in the real world that you get to write recursive code! It just isn't an efficient way to do things. (Double recursion leads to *exponential complexity*! Bleh!) Compilers also do a bad job, in general, optimizing it, so this hand-written assembly is head-and-shoulders above what a C compiler would generate for the naive solution:

```
int Fibtraction(int n)  { return n <= 2 ? n : f(n-2) - f(n-1); }

```

(although it has been optimized for *size*, rather than speed, obviously).

# Answer
> 2 votes
# Ruby, 26 bytes

Nothing fancy here, it's just a translation of Python or Javascript solutions :

```
f=->n{n<3?n:f[n-2]-f[n-1]}

```

The results are 1-indexed.

Try it online!

# Answer
> 2 votes
# SWI Prolog, 88bytes

Did I hear recursion? Prolog is here!

```
g(1,1).
g(2,2).
g(X,Y):-A is X-2,g(A,B),C is X-1,g(C,D),Y is B-D.
f(X):-g(X,Y),print(Y).

```

Try it: SWISH

# Answer
> 2 votes
# \>\<\>, 17+3 = 20 bytes

```
43\n;
?!\:@-{1-:}

```

Try it online!

Input is expected on the stack at the start of the program, so +3 bytes for the `-v` flag.

# Answer
> 2 votes
# Fortress 0.1 Alpha, 39 bytes.

```
f(n)=if n<3then n else f(n-2)-f(n-1)end

```

The interpreter is archived here (direct download).

This language is old and dead, very dead. (1-indexed: f(1)=1, f(2)=2).

Can be placed into a program like this:

```
export Executable
f(n)=if n<3then n else f(n-2)-f(n-1)end
run(args) = do
    println(f(3))
end

```

Does this **really** need explaining? This is just the definition.

# Answer
> 2 votes
# Julia, 24 bytes

```
f(n)=n>2?f(n-2)-f(n-1):n

```

1-indexed

Try it online!

# Answer
> 1 votes
# Mathematica, 37 bytes

```
LinearRecurrence[{-1,1},{1,2},{#+1}]&

```

# Answer
> 1 votes
# Go, 50 bytes

```
func f(n int)int{if n>2{n=f(n-2)-f(n-1)};return n}

```

Try it online!

# Answer
> 1 votes
# dc, 32 bytes

```
?3sb1sc[lblcdsb-sc1-d0<d]dsdxlbp

```

1-indexed.

Try it online!

## Explanation

```
?     # Take input and push it onto the main stack.
3sb   # Push 3 into register "b".
1sc   # Push 1 into register "c".
[     # Begin macro definition.
 lblc # Load the values in registers "b" and "c" onto the main stack.
 dsb  # Duplicate the top-of-stack value and push it into register "b".
 -sc  # Push the difference of the top two values into register "c".
 1-d  # Subtract 1 from the top-of-stack value and duplicate the result.
 0<d  # If the result is greater than 0, execute the macro in register "d".
]     # End macro definition.
dsdx  # Duplicate the macro, push a copy into register "d", and execute the
      # remaining copy.
lbp   # Output the value stored in register "b".

```

# Answer
> 1 votes
# VBA, 62 Bytes

Recursive function that takes input, `n`, as integer and outputs the 1-indexed element of A061084

```
Function f(n):If n<3Then f=n Else f=f(n-2)-f(n-1):End Function

```

# Answer
> 1 votes
# Braingolf, 22 bytes

```
[vl1-?!-|l1e2|l0e1|R]v

```

Try it online!

Why is it so long D:

# Answer
> 1 votes
# Positron, 63 bytes

```
a=function{k=$1;if(k>2)then{k=((a@(k-2))-(a@(k-1)))};return k;}

```

Try it online!

# Answer
> 0 votes
# Kotlin, 52 bytes

```
fun f(n:Int):Int{return if(n<3)n else f(n-2)-f(n-1)}

```

Try it online!

# Answer
> 0 votes
# Groovy, ~~27~~ 26 bytes

```
f={n->n<3?n:f(n-2)-f(n-1)}

```

Try it online!

Okay, so I feel like I stumbled upon a great language for golfing. This code is basically what most other answers are doing, if `n` is lesser than 3, then return `n` or else return `f(n - 2) - f(n - 1)`. But there are a few cool things about this.

For a language that compiles to the JVM, Groovy is surprisingly terse. Variable declarations need no type definition. Functions (called closures in Groovy) are denoted with the `{}` syntax. ~~`it` can be used to refer to the sole argument to the function, which means you don't need to specify the argument name and type.~~ Turns out naming the argument was shorter. Combined with the ternary operator, this code ended up quite golfy for a "practical" language.

# Answer
> 0 votes
# Pyth, 15 bytes

First time doing Pyth. ^^

```
L?<b3b-y-b2y-b1

```

Try it online!

## Explanation

```
L?<b3b-y-b2y-b1

L                define a function y that takes an argument b
 ?<b3            if b < 3...
     b           ...return b
      -y-b2y-b1  else return y(b - 2) - y(b - 1)

```

---
Tags: code-golf, number, sequence, fibonacci
---


title: Dodge your death!

text:
# Question
Title: Dodge your death!
## Introduction

"Muhuhuhahahah!" The mad scientist laughs. "You're trapped in my own little game!"

In front of you is a deadly pit of snakes, while behind you is a bottomless chasm. There's no way out, you're stuck!

"Two steps in front of you is the snake pit, and two steps behind you is the chasm. But! Before you move, you MUST write down a sequence of steps, forwards and backwards, and give them to me. But! because I'm feeling a bit *evil* today, I can make you take, instead of every step, every `n`th step, where `n` is less than your sequence length!

Choose wisely, now."

What's the maximum number of steps you can take before your imminent death?

## Task

The intro above is a twist on the Erdős discrepancy conjecture, which was recently proven true (if you want to understand more about this, go to this video, by James Grime - I "stole" the twist question off of him).

The answer to the intro is `11` steps, but I won't go too in-depth with a proof. The answer, if the distance between you and the two "dangers" were `3` steps, is `1160` steps, although that isn't validated properly yet.

Your task is to make a program that generates the longest sequence of steps you can achieve for a larger `x`, where `x` is the number of steps between you and the two "dangers". Your program must take an input for `x`, and output a valid sequence for that `x`.

For the purposes of this challenge, `+` represents a step forward, and `-` represents a step back.

So, an output for an input `2` is:

```
+--+-++--++

```

Which works, no matter what `n` the mad scientist chooses. For our challenge, `x = 5`.

**NOTE: This challenge is not a dupe of this challenge or this challenge, as my challenge focuses on the output, as opposed to the code itself - in other words, it's not a code golf challenge. As well as that, these challenges are based off of `x = 3`, which already has an established upper bound.**

## Rules:

* Your entire program should fit into your answer. However, if it doesn't fit, please provide an additional Github repository, or something similar.
* You may update both your answer and your program, if you can get a better score via optimising your code - but by doing so, you must update everything in the list below.
* In your answer, you must have:
    + Your program, in its entirety, or a link to a GH repository hosting your code
    + The amount of steps generated - **this will be your final score**.
        - You must also **provide an online version of the sequence** in a Pastebin, or something similar. This is so we can check your answer.
    + The time your final score was last updated, so I don't have to check your history
* You may NOT hardcode sequences beforehand.
* Your program **must work for all `x`** (where `x` is the number of steps between you and the pit & chasm), but you only need to provide the score for `x = 5`.

The answer with the largest score wins!

# Answer
> 6 votes
# Rust, score=4997216, time=2017-07-12 00:18 UTC

This improves on the best result I was able to find in the literature, which was 1148805 (Ronan Le Bras, Carla P. Gomes, Bart Selman, On the Erdős Discrepancy Problem, 2014), by a factor of 4.3.

Output sequence of length 4997216

Source code on GitHub

### Running

The program accepts the maximum discrepancy as an argument (this is *x* − 1 in the language of the challenge, to align with the more common mathematical convention). It produces incremental outputs in a slightly compressed format that looks like this for *x* = 3:

```
$ cargo run --release 2
add +--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-+
length 90
delete 12
add --++--+-++-++--+-++--+--+-++--+-
length 110
delete 4
add +-+--+-++-++--+-++--+--+-++-++--+-++-+
length 144
delete 6
add --++-++--+-++--+--++++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-+-
length 214
delete 208
add --+++--+++--+-+--+++--+-+--+++--++---+-+--+-+-++-+--+++--+++--+---++-+--+-++-+++---++--+-++-++--++--+--++--+++--+-+-++-+--+-+--+++---+++-+----+++--+-++--++-+-++--+-+--+-+-++-+--+++--++--+--+--+-++-++---++-++-++-+--+-++
length 224
delete 2
add -+++--+-+--+++---++--+--
length 246
done

```

where `add` means append a sequence of signs to the end of the current sequence, `delete` means remove some number of signs from the end of the current sequence, and `length` asserts the length of the current sequence. This scheme avoids the production of many gigabytes of intermediate results as longer and longer sequences are discovered. You can extract the best result so far with the following Python program:

```
import sys
s = ''
for line in sys.stdin:
    cmd = line.split()
    if cmd[0] == 'delete': s = s[:-int(cmd[1])]
    elif cmd[0] == 'add': s += cmd[1]
    elif cmd[0] == 'length': assert len(s) == int(cmd[1])
print(s)

```

### How it works

There are about a thousand lines of code here, so this is only going to be a very rough overview.

We limit the search to completely multiplicative sequences (those with *f*(*a*·*b*) = *f*(*a**f*(*b*)), because that means we need only concern ourselves with bounding the partial sums for *n* = 1, and the partial sums for *n* ≥ 2 will satisfy the same bound automatically.

For any substring *f*(*i* \+ 1), …, *f*(*j*) of a partially assigned sign sequence (so each element is ‘+’, ‘−’, or unknown), define danger+(*i*, *j*) to be twice the number of ‘+’s minus the length *j**i* (for convenience, we allow *i* to be as small as −*x* \+ 2 and assume *f*(−*x* \+ 3) = ⋯ = *f*(0) = ‘+’ for this purpose). Define danger(*i*, *j*) similarly. Then the bound on partial sums for *n* = 1 is equivalent to the condition that whenever *i**j**x* (mod 2), danger+(*i*, *j*) ≤ *x* − 2 and danger(*i*, *j*) ≤ *x* − 2.

We build an incremental data structure that supports constant time queries for the substring with largest danger, with logarithmic time updates. It works by associating four values:

* danger(*i*, *j*),
* max*i**k**j* danger(*i*, *k*),
* max*i**k**j* danger(*k*, *j*), and
* max*i**k**l**j* danger(*k*, *l*),

with every string of length 2, every other string of length 4, every fourth string of length 8, and so on. The values associated with a longer string can be computed in constant time from the values associated with its two halves.

This structure, augmented with some auxiliary information, lets us perform constraint propagation and conflict detection on partial sequences very quickly. We use it to do a CDCL-like search, with unit propagation, decision levels, and non-chronological backtracking (but without clause learning, for now), for full sequences of longer and longer lengths.

At each search step, we make a guess for the earliest unassigned sign. The heuristic used to make this guess is very important for avoiding a lot of backtracking; we use *f*(3·*k*) = −*f*(*k*), *f*(3·*k* \+ 1) = ‘+’, *f*(3·*k* \+ 2) = ‘−’.

### Results

The discrepancy 0, 1, and 2 searches immediately find the optimal completely multiplicative sequences of length 0, 9, and 246.

The discrepancy 3 search gets stuck within seconds at 41319, which is pretty far from the known optimal completely multiplicative sequence of length 127645 found by Le Bras et al., 2014 (and a very slightly longer non-multiplicative extension of length 130000 found shortly thereafter), but much better than the best known sequence before that of length 17000.

The discrepancy 4 search improves the longest sequence more or less continually for about five minutes until it gets stuck at 4997216. The best previously known sequence of length 1148805 = 9·127645 was expanded from the discrepancy 3 sequence by replacing every sign *s* with +−−+−++−*s*. As far as I can tell, sequences this long are too hard for a general SAT solver to reasonably improve directly (but maybe you, dear reader, can prove me wrong!).

I expect I’ll need to add some kind of clause learning to my program to get past these barriers.

### The sequence as a 2187×2285 bitmap

(Click to view at full resolution.)

# Answer
> 3 votes
# Haskell, score=9020, time=2017-06-09 00:52 UTC

```
f 1=""
f n="+-"++do c<-f(n-1)++"-";"-+-++-"++c:"+-"

```

Try it online!

This scores (9*n* − 1 − 1)⋅11/8 for all *n*. Here are the first few outputs:

```
n=1, length=0:
n=2, length=11: +--+-++--+-
n=3, length=110: +--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+-
n=4, length=1001: +--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+-
n=5, length=9020: [encoded data, 9020 characters]

```

---
Tags: math, code-challenge, optimized-output
---


title: Ducttape the Ducttape

text:
# Question
Title: Ducttape the Ducttape
Your boss has found out that quite a bunch of his employees (including you) like to steal code from others. He ordered you to write him a program that he can use to find people who steal code from others.

## Task:

Write a program/function that detects if somebody copied (part of) his code from somewhere else.

The program will get all the *existing programs and the program that it should test from two separate inputs*. **Edit:** Since there are no answers so far, you may use regular expressions!

## Output

* The program should then output **all** the stolen pieces of code, separated by either a space or a newline. (It may have a space or a newline at the end.)
* A piece of code is considered to be stolen/copied if it consists of 10 or more *successive* bytes. (Sorry, Java fans!)
* You have to output as much as possible, but if there are overlapping ones, you may ignore one of them or output both of them.

## Twist:

As mentioned before, you also love duct tape coding. That means, **everything** in your code will be copy-pasted from a stack exchange site! You can copy whatever you want (not limited to code in code blocks) and as much as you want. (But at least 10 bytes) (Same rule as above about what is considered to be stolen/copied.) (Please do note that any answers that were posted after this question may not be used.) Please provide links to where you got your code from.

## Examples:

**Input:**
`x = document.getElementById("ninja'd");` (The first input)
`y = document.getElementById("id");` (The second input)

**Output:**

```
 = document.getElementById("

```

**Input:**
`foo` (The first input)
`foo+bar` (The second input)

**Output:**
Nothing.

**Input:**
`public static void main(String[] args)` (The first input)
`public static void main(String[] args)` (The second input)

**Output:**

```
 main(String[] args)

```

**Input:**
`for(var i=0; i<x.length; i++){}` (The first input)
`for(var i=0; i<oops.length; i++){break;}` (The second input)

**Output:**

```
for(var i=0; i<
.length; i++){

```

or

```
for(var i=0; i< .length; i++){

```

# Answer
# Python 2, 224 bytes

```
from difflib import SequenceMatcher
def similar(a, b):
    return SequenceMatcher(None, a, b).get_matching_blocks()
a=raw_input()
b=raw_input()
for start, _, size in similar(a, b):
 if(size > 9):
  print a[start:start+size]

```

Copied from this answer:

```
from difflib import SequenceMatcher
def similar(a, b):
    return SequenceMatcher(None, a, b).

```

`get_matching_blocks()` is copied from this answer

```
a=raw_input()
b=raw_input()

```

is copied from this question

`for start, _, size in` is copied from this answer and the second occurence of `similar(a, b)` is copied from the same place as the first.

`if(size > 9)` is copied from this question.

```
:
    print

```

is copied from this question

`a[start:` is copied from this answer.

and finally, `start+size]` is copied from this questipn

Finally answered after one and a half years ...
> 11 votes

---
Tags: code-golf, duct-tape-coding
---


title: Color me a Pole

text:
# Question
Title: Color me a Pole
Lets say your job is to paint poles, and a client asks you to paint a pole with 4 red sections and 3 yellow sections. You can do that pretty easily as follows:

```
r y r y r y r

```

With just yellow and red stripes. Now lets say your client asks you to paint a pole with 2 red sections, 2 yellow sections, and *1 green section*. There are a couple of ways you could paint your pole

```
g y r y r
y g r y r
y r g y r
y r y g r
y r y r g
g r y r y
r g y r y
r y g r y
r y r g y
r y r y g
y r g r y
r y g y r

```

More precisely thats 12 ways to paint the pole. This blows up the more colors and sections that are involved

Now if your client says they want 3 red sections and 1 yellow section there is no way to paint a pole like that. Because no matter how you attempt to arrange the sections two red sections will touch, and when two red sections touch they become a single red section.

And that is pretty much our one rule for painting poles

> Adjacent sections may not be of the same color

## Task

Given a list of colors and sections required, output the number of possible ways to paint a pole as requested. You may represent colors in any reasonable way (integers, characters, strings), but you will never be given more than 255 different colors at a time. If you wish you can even choose to not have the colors assigned names and just take a list of section counts if that is easier.

## Test Cases

These are rather hard to calculate by hand, especially as they get larger. If anyone has a suggested test case I'll add it.

```
[4,3]    -> 1
[2,2,1]  -> 12
[3,1]    -> 0
[8,3,2]  -> 0
[2,2,1,1]-> 84

```

# Answer
> 9 votes
# Mathematica, 37 ~~44~~ ~~48~~ ~~60~~ ~~62~~ bytes

Take input as a list of integers `{1, 1, 1, 2, 2}`. Try it on Wolfram Sandbox.

## Pattern-matching method, thanks @Not a tree !

```
Count[Split/@Permutations@#,{{_}..}]&

```

`Split` splits a single list into sublists of consecutive elements, e.g. `{1, 1, 2, 3, 4, 4}` into `{{1, 1}, {2}, {3}, {4, 4}}`

`{{_}..}` is, namely, `{{_}, {_}, {_}, ...}`. The pattern matches a list of unary sublists.

## `Differences` method, 48 bytes:

```
Tr@Abs@Clip[1##&@@@Differences/@Permutations@#]&

```

The code uses `Differences` to determine whether adjacent elements are the same.

Step by step:

1. `Permutations@#` generates all permutations of input list to a N!\*N list.
2. `Differences/@` calculates the difference between N elements, and yields a N!\*(N-1) list.
3. `1##&@@@` calculates the multiplication of all lists. If a list contains `0` (two adjacent elements are the same), the result will be `0`, otherwise non-zero, to a N! list.
4. `Clip[]` acts like `Sign[]`, transform the list from (-inf, inf) to \[-1, 1\]
5. `Tr@Abs` turns all `-1` into `1` and now the N!-length list contains only `0` (invalid) and `1` (valid). So we just sum the list.

# Answer
> 7 votes
# Jelly, 7 bytes

```
Œ!QIẠ€S

```

Try it online!

Takes input as e.g. `[1,1,1,1,2,2,2]` for `[4,3]`. The `[8,3,2]` testcase takes too long to run on TIO.

**How it Works**

```
Œ!QIẠ€S - main link, input as a list
Œ!      - all permutations
  Q     - remove duplicates
   I    - take increments (returns a 0 for two adjacent identical numbers)
    Ạ€  - apply “all” atom to each: 0 for containing 0 and 1 otherwise
      S - sum

```

# Answer
> 5 votes
# 05AB1E, 7 bytes

```
œÙ€¥PĀO

```

Try it online!

-1 thanks to nmjcman101 on another answer.

# Answer
> 5 votes
## Mathematica, 50 bytes

```
Expand[1##&@@(LaguerreL[#,-1,x](-1)^#)]/._^i_:>i!&

```

Try it in Mathics, or at the Wolfram sandbox!

Takes input like in the test cases — e.g. `{4,3}` means "4 red stripes, 3 yellow stripes".

This is a naïve implementation of a formula I found here. "Naïve" means "I have no idea how the maths works so please don't ask me for an explanation…"

# Answer
> 5 votes
# Python 3.5, 65 bytes

```
f=lambda s,p=0:sum(f(s.replace(c,'',1),c)for c in{*s}-{p})or''==s

```

Try it online!

# Answer
> 3 votes
# Ruby 2.4, 47 bytes

Input is a list of characters: For the test case `[4,3]`, input can be `%w[a a a a b b b]`, `"1111222".chars`, or some other array formatting method that's valid in Ruby.

```
->x{x.permutation.uniq.count{|a|a*''!~/(.)\1/}}

```

Requires 2.4 for `Enumerator#uniq` (earlier versions only had it available on the `Array` class). As such, the TIO link adds 5 bytes to convert the permutation enumerator to an array first via `to_a`, since it does not have the above function.

Try it online!

# Answer
> 3 votes
# R, 72 bytes

```
pryr::f(sum(sapply(unique(combinat::permn(x)),pryr::f(!sum(!diff(x))))))

```

Creates the function

```
function (x)
{
    sum(sapply(unique(combinat::permn(x)), pryr::f(!sum(!diff(x)))))
}

```

Takes input in the form `[1,1,1,1,2,2,2]` as per Erik the Outgolfer's comment. Uses `combinat`'s `permn` function to create a list of all permutations, and then `unique` to get all distinct entries. `sapply` then applies the following function on all entries:

```
pryr::f(!sum(!diff(x)))

```

Which evaluates to

```
function (x)
!sum(!diff(x))

```

Note that this `x` is not the same as the `x` in the big function's input. Using another character in this function would fool `pryr::f` into believing the big function needs another argument.

Anyways, when given a permutation, this function takes the difference between the vector: `2 1 3 4 2 1 -> -1 2 1 -2 -1`. `!` converts nonzero's into `FALSE` and zeros into `TRUE`, so the vector becomes `FALSE FALSE FALSE FALSE FALSE`. Summing that to check if there are any `TRUE`s (`TRUE` would imply `diff=0` --\> two the same consecutive numbers). We can again invert this with `!` to get a boolean on whether or not there are consecutive values in the permutation.

Summing over these booleans gives us the total number of permutations where this is not the case.

Doesn't work for the `[8,3,2]` testcase because it requires a vector of 46GB to store those permutations.

# Answer
> 2 votes
# Jelly, 11 bytes

```
Œ!Q⁻2\Ạ$ÐfL

```

Try it online!

# Answer
> 2 votes
# Python 2, ~~140~~ 89 bytes

Input format is `'aaaabbb'` for test case `[4,3]`.

```
lambda s:len({p for p in permutations(s)if all(map(cmp,p,p[1:]))})
from itertools import*

```

Try it online!

# Answer
> 2 votes
# Ruby, ~~84~~ 76 bytes

```
f=->a,x=p{i=s=0;a.map{a[i-=1]-=1;a[i]<0||i!=x&&s+=f[a,i];a[i]+=1}.max>0?s:1}

```

A recursive lambda function. Looks at each possible color and dose a recursive tree search, counting the number of times it uses all stripes.

### Explanation (for old version):

```
f=->
  a, # a is the input array in [3,3,4] form
  x = -1 # x is the last color placed (-1 when run normaly, used in recursive calls)
{
  j = i = s = 0;
  # i is the index
  # s is the sum of valid final patterns (the answer)
  # j is used to count the total stripes

  a.map{|e| # Iterate over array of colors

    a[i] -= 1; # remove a stripe of current color (the array will be used in recursive call)

    s += f[a,i] if i!=x && e>0;
      # add to sum recursively if:
        # we are not using the same color as the last color AND
        # we have stripes of the current color left to paint

    a[i] += 1; # replace the stripe we removed above

    j += a[i]; # add stripes to j

    i+=1 # increment the index

  }; # End loop

  j == 0 ? 1 : s
  # if we had stripes, give the recursive sum, otherwise return 1
}

```

# Answer
> 2 votes
## Husk, 8 bytes

```
#ȯ¬ṁtguP

```

Try it online! Takes input in the format `"aaabb"` for `[3,2]`. Times out on the longest test case.

## Explanation

Nothing fancy here, just counting the unique permutations where all groups of adjacent elements have length 1.

```
#ȯ¬ṁtguP
       P  Permutations.
      u   Remove duplicates.
#ȯ        Count how many satisfy the following condition:
     g    group adjacent elements,
   ṁt     concatenate tails of groups
  ¬       and negate.

```

# Answer
> 1 votes
# MATL, ~~11~~ 8 bytes

```
Y@Xu!dAs

```

Input format is `[1 1 1 1 2 2 2]` for `[4 3]`, etc.

Runs out of memory for the last test case.

**Try it online!**

### Explanation

```
Y@    % Implicit input. Matrix of all permutations. Each row is a permutation
Xu    % Unique rows
!     % Transpose
d     % Consecutive differences along each column
A     % All: true for columns such that all its entries are nonzero
s     % Sum. Implicitly display

```

---
Tags: code-golf, permutations
---


title: Code Golfing Split String in Bash

text:
# Question
Title: Code Golfing Split String in Bash
Let us play a little golfing game. Given a single line of N space separated numbers from STDIN, one must output those numbers on N lines.

So far, I came up with the three following bash solutions :

* `xargs -n1` (9)
* `tr \ \\n` (8)
* `fmt -1` (6)

Can anyone do better? I am eager to learn new tricks

# Answer
Bash (22)

```
read X;printf %d\\n $X  (thanks to manatwork but without literal NL)

```

`~~30 read -aX;printf "%d\n" ${X[*]}
26 read X;echo -e ${X// /\n}
28 printf "%d\n" $(</dev/stdin)
27 printf "%d\n" $(</dev/fd/0)
26 printf %d\n $(</dev/fd/0)
23 read X;printf "%d\n" $X~~`
> 0 votes

---
Tags: code-golf, tips, bash
---