# Question
Title: Reducing Leibniz perl code in characters
This Perl code is supposed to calculate the Leibniz formula. The original problem is here.

The input format is:

```
T
<T test cases, each on their own line>

```

Each test case is a number \< 10^7. The output format should be the same, minus the first line.

For example, an input:

```
2
10
20

```

And for output:

```
0.760459904732351
0.77290595166696

```

My first solutions, at 62 and 61 characters respectively.

```
for(1..<>){$s=0;map{$s+=($_&1||-1)/(2*$_-1)}1..<>;print"$s\n"}

for(1..<>){$s=0;$s+=($_&1||-1)/(2*$_-1)for 1..<>;print"$s\n"}

```

Edit: The best solution so far is 53 characters, by @teebee:

```
<>;print${\map$a-=(-1)**$_/(2*$_-1),1..$_},$a=$/for<>

```

# Answer
> 3 votes
## Perl 55 bytes

```
<>;map($s-=(-1)**$_/(2*$_-1),1..$_),$s=!print$s,$/for<>

```

Without using any Perl non-standard features (such as `say`). 3 bytes are wasted removing the first value from the input.

Sample usage:

in.dat

```
2
10
20

```

```
$ perl leibniz.pl < in.dat
0.760459904732351
0.77290595166696

```

---

## Alternative, also 55 bytes

```
map{$s-=(-1)**$_/($_*2-1)for 1..<>;$s=!print$s,$/}1..<>

```

The alternative may be run interactively, without requiring an input file. Which, as I understand, is what you meant by running indefinitely.

# Answer
> 5 votes
# Perl 53 bytes

You can save two more strokes:

```
<>;print${\map$a-=(-1)**$_/(2*$_-1),1..$_},$a=$/for<>

```

---
Tags: code-golf, tips, perl
---


title: Alex the Truck Driver

text:
# Question
Title: Alex the Truck Driver
Alex is a Truck Driver who wants to find the quickest way to deliver goods to multiple cities. He knows the distances between his destinations, but you need to write a program to help him find the quickest way to deliver goods to them.

**Input**

The first line of input gives the number of cities Alex needs to deliver goods to. Every line that follows gives the distance between the cities. The second line of input is always the distance between the first and second cities. If there is a third city, the third line of input is the distance between the first and third city. When to distance to the first city has been given for all cities, the next lines of input gives the distance between the the second city and every other city (except the first, as that information as already been given). This continues until every combination has been given. Sample inputs:

```
//Number of cities
4
//A -> B
2
//A -> C
4
//A -> D
3
//B -> C
5
//B -> D
1
//C -> D
3

3
6
4
2

```

**Output**

The output should print the quickest way to deliver goods to every destination in the form `A -> C -> D -> C -> A` (For every output, the reverse of will also work. You only need to print one solution). Alex ALWAYS starts at `A` and must always return to `A` at the end (as `A` is where he lives). Here are the outputs for the sample inputs above:

```
A -> B -> D -> C -> A

A -> C -> B -> A

```

**Rules**

The shortest code wins.

Happy Golfing!

# Answer
# Python 2, ~~210~~ 205

```
from itertools import*
r=range(input())
d={t:input()for t in combinations(r,2)}
n=0,
print" -> ".join(chr(65+c)for c in n+min(permutations(r[1:]),key=lambda p:sum(d[min(t),max(t)]for t in zip(n+p,p+n)))+n)

```

**Edit:** Shortened according to Volatility's suggestion. I'm amazed that it gets more readable and Pythonic the shorter it gets.
> 2 votes

# Answer
# C++ - 380

```
#include<iostream>
#include<algorithm>
#define I new int[n]
#define f for(i=0;i<n;++i)
using namespace std;int main(){int*a,**d,*s,n,i,j,t,b=2e9;cin>>n;d=new
int*[n];a=I;s=I;f{a[i]=i;d[i]=I;}f
for(j=i+1;j<n;++j){cin>>d[i][j];d[j][i]=d[i][j];}do{t=0;f
t+=d[a[i]][a[(i+1)%n]];if(t<b){b=t;copy(a,a+n,s);}}while(next_permutation(a+1,a+n));f
cout<<(char)(65+s[i])<<" -> ";cout<<"A\n";}

```
> 0 votes

# Answer
This a commentary rather than an entry.

If I am not mistaken, the sample data appear to correspond to an impossible set of distances between cities located in the plane.

The inter-city distances might be represented by a matrix

or, perhaps more conveniently, by a graph in which the edge labels are distances. (Note: The graph is not a geographical map.)

The figure below arbitrarily sets A at the origin of a coordinate plane. The distances from A to B, C, and D constrain the latter three cities to positions on circles with center at A and radii of 2, 4, and 3 units. We may arbitrarily place B at (0,2) and continue. Now, because D is one unit away from B and 3 units away from A, it must lie at (0, 3).

But there would appear to exist no position in the plane that is simultaneously 4, 5, and 3 units away from A, B, and D respectively.

---

The impossibility of the data would not detected by most approaches, although I suspect that a multidimensional scaling analysis would return a stress value that should raise a flag.
> 0 votes

# Answer
### Ruby, 242 characters

```
s,a,c,i=gets.to_i-1,[],[],0
0.upto(s){|x|x.upto(s){|y|a[y]||=[];a[x][y]=a[y][x]=x==y ?0:gets.to_f}}
(0..s).to_a.permutation{|x|x[0]<1&&c<<[(0..s).reduce(0){|y,z|y+a[x[z]][x[z-1]]},x]}
puts c.min_by{|x|x[0]}[1].map{|x|(x+65).chr+" -> "}*""+"A"

```

This finds the shortest path that never visits the same city twice. If triangle inequality is satisfied, no city should be visited twice. If the triangle inequality is broken, visiting the same city twice may be beneficial. If there are negative cycles, no optimal solution exists, as you can keep driving along the cycle to travel back in time. In practice, triangle inequality (and thus non-negativity) is safe to assume.

The algorithm itself is brute-force and inefficient. Don't use for maps with more than 10 or 12 cities. Three words: `O(n!)`
> 0 votes

# Answer
### GolfScript, 118 108 characters

```
~](:€,{.€-~:§2$>\)[0]*@§<+}%€.?,{€base}%{$€,1>=},{[0].@+\+.0\{.@[\]$~\5$==@+\}*;[\]}%$\;0=1={65+}%""+" -> "*

```

A quite clumsy (i.e. really slow) 118 characters GolfScript program.

Example:

```
> 4 2 4 3 5 1 3
A -> B -> D -> C -> A

> 3 6 4 2
A -> B -> C -> A

```
> 0 votes

---
Tags: code-golf, graph-theory
---


title: letter combinations to make words

text:
# Question
Title: letter combinations to make words
Find the combination of N number of letters that make up the most words of length N.

For example:

```
n r u  ->  run, urn
dstu -> dust, stud
(these are just examples, not the best combination of 3,4 length sets of letters)

```

The challenge in the case is to start with length N=3 and end at N=11. Which combination of letters gives you the most words and what are those words?

For the contest, please use this word list. It contains 71,193 words. Please also let us know the time (in seconds) and CPU type/speed that you are using.

# Answer
> 2 votes
# k (39)

Expects the wordlist to be in a file called `w` in the current directory.

```
{i?max i:#:'=:{x@<x}'(w@=:#:'w:0:`:w)x}

```

Example usage (calculating result for every permissible input, runs in 640 ms on single core of Pentium E2160)

```
k){i?max i:#:'=:{x@<x}'(w@=:#:'w:0:`:w)x}'3+!9
("AET";"AELS";"AELST";"ACERST";"ADEEGNR";"AEGILNRT";"AACEINRST";"ADIIMNNOOT";..

```

# Answer
> 4 votes
### Ruby, 116 97 92 characters

```
9.times{|n|p IO.read('w').split.group_by{|s|s.chars.sort}.max_by{|k,v|k.size!=n+3?0:v.size}}

```

The wordlist is expected in the file `w` in the local directory. Program runs less than a second.

*Output:*

```
[["A", "E", "T"], ["ATE", "EAT", "ETA", "TAE", "TEA"]]
[["A", "E", "L", "S"], ["ALES", "ELSA", "LEAS", "LESA", "SALE", "SEAL"]]
[["A", "E", "L", "S", "T"], ["LEAST", "SLATE", "STAEL", "STALE", "STEAL", "TALES", "TEALS", "TESLA"]]
[["A", "C", "E", "R", "S", "T"], ["CARETS", "CASTER", "CATERS", "CRATES", "REACTS", "RECAST", "TRACES"]]
[["A", "D", "E", "E", "G", "N", "R"], ["ANGERED", "DERANGE", "ENRAGED", "GRANDEE", "GRENADE"]]
[["A", "E", "G", "I", "L", "N", "R", "T"], ["ALERTING", "ALTERING", "INTEGRAL", "RELATING", "TRIANGLE"]]
[["A", "A", "C", "E", "I", "N", "R", "S", "T"], ["ASCERTAIN", "CARTESIAN", "SECTARIAN"]]
[["A", "D", "I", "I", "M", "N", "N", "O", "O", "T"], ["ADMONITION", "DOMINATION"]]
[["A", "C", "G", "H", "I", "I", "L", "M", "O", "R", "T"], ["ALGORITHMIC", "LOGARITHMIC"]]

```

# Answer
> 2 votes
# Haskell, 341 chars

Takes the word list on standard input, and return **all possible solutions** for each `2 < n < 12` a quadruple of the form:

```
(n, s, l, w)

```

where

```
n = Selected number of letter (between 3 and 11)
s = Size of the biggest sets of words of given size
l = The ordered sets of letters that compose words
w = The sets of words for each set of letters

```

for example: `(3,5,["AET"],[["ATE","EAT","ETA","TAE","TEA"]])`

## Compressed code

```
import Data.List;import Data.Function;main=do interact$unlines.map(show.(\x->(length.head.head$x,length.head$x,map(sort.head)$x,x)).last.groupBy((==)`on`length).sortBy(compare`on`length)).groupBy((==)`on`(length.head)).sortBy(compare`on`(length.head)).groupBy((==)`on`sort).sortBy(compare`on`sort).filter(\x->length x>=3&&length x<=11).lines

```

## A bit more readable code

```
import Data.List
import Data.Function

main = do
    interact $ unlines . map ( show . (\x -> (length . head . head $ x, length . head $ x, map (sort . head) $ x, x)) . last . groupBy ((==) `on`length) . sortBy (compare `on` length)) . groupBy ((==) `on` (length . head)) . sortBy (compare `on ` (length . head)) . groupBy ((==) `on` sort) . sortBy (compare `on` sort) . filter (\x -> length x >= 3 && length x <= 11) . lines

```

## Execution

Compiling with: `ghc -O2 letter.hs`
Running with: `time ./letter < wordlist`
Result: `1.75s user 0.03s system 99% cpu 1.784 total`
CPU info: `Intel i7 8x3.4 GHz 64 bits`

## Output

```
(3,5,["AET"],[["ATE","EAT","ETA","TAE","TEA"]])
(4,6,["AELS","AEST","OPST"],[["ALES","ELSA","LEAS","LESA","SALE","SEAL"],["ATES","EAST","EATS","SATE","SEAT","TEAS"],["OPTS","POST","POTS","SPOT","STOP","TOPS"]])
(5,8,["AELST"],[["LEAST","SLATE","STAEL","STALE","STEAL","TALES","TEALS","TESLA"]])
(6,7,["ACERST"],[["CARETS","CASTER","CATERS","CRATES","REACTS","RECAST","TRACES"]])
(7,5,["ACDEILM","ADEEGNR","ADEHRST","ADEIRST","AEIRSTT","AELPRSY","EIPRSST"],[["CLAIMED","DECIMAL","DECLAIM","MALICED","MEDICAL"],["ANGERED","DERANGE","ENRAGED","GRANDEE","GRENADE"],["DEARTHS","HARDEST","HATREDS","THREADS","TRASHED"],["ARIDEST","ASTRIDE","STAIDER","TARDIES","TIRADES"],["ARTIEST","ARTISTE","ATTIRES","IRATEST","TASTIER"],["PARLEYS","PARSLEY","PLAYERS","REPLAYS","SPARELY"],["PERSIST","PRIESTS","SPRIEST","SPRITES","STRIPES"]])
(8,5,["AEGILNRT","AEGINRST"],[["ALERTING","ALTERING","INTEGRAL","RELATING","TRIANGLE"],["ANGRIEST","GANTRIES","INGRATES","RANGIEST","TANGIERS"]])
(9,3,["AACEINRST","ABEEILRST","ACDEINOTU","ACEGINRRT","ACEINSSTT","ADEGGINNR","ADEGINRRW","AEEGNRSST","AEGHILNRT","AEGIMNRST","AEILMSTTU","CEINORSTU","DEEINRSST","EGIILNNST","EGIINPRRS","EGINORRST"],[["ASCERTAIN","CARTESIAN","SECTARIAN"],["BEASTLIER","BLEARIEST","LIBERATES"],["AUCTIONED","CAUTIONED","EDUCATION"],["CRATERING","RETRACING","TERRACING"],["CATTINESS","SCANTIEST","TACITNESS"],["DANGERING","DERANGING","GARDENING"],["REDRAWING","REWARDING","WARDERING"],["ESTRANGES","GREATNESS","SERGEANTS"],["EARTHLING","HALTERING","LATHERING"],["EMIGRANTS","MASTERING","STREAMING"],["MUTILATES","STIMULATE","ULTIMATES"],["COUNTRIES","CRETINOUS","NEUROTICS"],["DISSENTER","RESIDENTS","TIREDNESS"],["ENLISTING","LISTENING","TINSELING"],["REPRISING","RESPIRING","SPRINGIER"],["RESORTING","RESTORING","ROSTERING"]])
(10,2,["AAAILNRSTU","AABEIILNST","AACDEGLOTU","AACEGLOSTU","AACEINRSST","AAEILNORST","AAEINOPRRT","AAGILLMNRY","AAGINNOSTT","ABDDEIORSS","ACCEHIMSST","ACDEEILNRT","ACDEGIIMNT","ACDEIIMNOT","ACDEIIPRST","ACDEINOORT","ACEEILMSST","ACEEINNRST","ACEEINRSST","ACEGHINRTT","ACEIINOTTX","ACEILNOSST","ACGIINNOTU","ACGILLNOPS","ADEEGINNRS","ADEEHILPRS","ADEEIMNNOT","ADEEINRSTT","ADEEINRSTU","ADEFORRSTW","ADEGIILMNS","ADEILPSTTU","ADEINNOOTT","ADIIMNNOOT","AEEGIMNPRT","AEEGINNRST","AEEGINNRTV","AEEHILRSTT","AEEHINRSST","AEEHORSSUW","AEEINNORTV","AEEIPRSSTT","AEEMNSSTTT","AEGHILNRST","AEGHINRSTT","AEGIINNPRT","AEGINRRSTT","AEHIRSSTTW","AEIILORSST","AFIILNORTT","AGHILMORST","AGIILMNTTU","AIILNOOPST","BDEGILNORU","BEGILNORST","CCEEGHIKNR","CCEEGINORT","CCEGINNORT","CDDEINOSTU","CDEEIINRST","CDEEIORRSV","CDEEMOPRSS","CDEEOPRRSU","CDEGIINNRS","CDEIINORST","CDEIINRSTT","CDEINORSTU","CEFGIINRTY","CEFGINORSU","CEGHIIKNNT","CEGINNNOTT","CEGINNORSV","CEGINNORTU","CEIINNOPST","CEINOPRSSU","DEEEINNRTV","DEEEIPRSTX","DEEELOPRSV","DEEFIILNRS","DEEFORRSST","DEEIMNORSZ","DEGILNOSTU","DEGINNRSSU","DEIINOOPST","EEGINNPRST","EEGLNORSTT","EEIIMPRSSV","EEIINOPRTT","EEINPRSSTT","EELOPRSSTY","EFIMNORSTU","EGIINPRSST","EGILMNOOSS","EIIMNOPRSS","EIMNNRSTTU","EIMNOPRSTU","GHILOPSSTT"],[["AUSTRALIAN","SATURNALIA"],["BANALITIES","INSATIABLE"],["CATALOGUED","COAGULATED"],["CATALOGUES","COAGULATES"],["ASCERTAINS","SECTARIANS"],["RATIONALES","SENATORIAL"],["PRAETORIAN","REPARATION"],["ALARMINGLY","MARGINALLY"],["ANTAGONIST","STAGNATION"],["BROADSIDES","SIDEBOARDS"],["CATECHISMS","SCHEMATICS"],["CREDENTIAL","INTERLACED"],["DECIMATING","MEDICATING"],["DECIMATION","MEDICATION"],["PATRICIDES","PEDIATRICS"],["COORDINATE","DECORATION"],["CLEMATISES","TIMESCALES"],["NECTARINES","TRANSIENCE"],["ANCESTRIES","RESISTANCE"],["CHATTERING","RATCHETING"],["EXCITATION","INTOXICATE"],["COASTLINES","SECTIONALS"],["AUCTIONING","CAUTIONING"],["COLLAPSING","SCALLOPING"],["GRENADINES","SERENADING"],["DEALERSHIP","LEADERSHIP"],["DENOMINATE","EMENDATION"],["REINSTATED","STRAITENED"],["UNREADIEST","UNSTEADIER"],["AFTERWORDS","FORWARDEST"],["MISDEALING","MISLEADING"],["PLATITUDES","STIPULATED"],["DENOTATION","DETONATION"],["ADMONITION","DOMINATION"],["IMPREGNATE","PERMEATING"],["ARGENTINES","TANGERINES"],["ENERVATING","VENERATING"],["EARTHLIEST","STEALTHIER"],["EARTHINESS","HEARTINESS"],["HOUSEWARES","WAREHOUSES"],["ENERVATION","VENERATION"],["STRIPTEASE","TAPESTRIES"],["STATEMENTS","TESTAMENTS"],["EARTHLINGS","SLATHERING"],["SHATTERING","STRAIGHTEN"],["PERTAINING","REPAINTING"],["REGISTRANT","RESTARTING"],["SWARTHIEST","SWEATSHIRT"],["SOLITAIRES","SOLITARIES"],["FILTRATION","FLIRTATION"],["ALGORITHMS","LOGARITHMS"],["MUTILATING","ULTIMATING"],["POSITIONAL","SPOLIATION"],["BOULDERING","REDOUBLING"],["BOLSTERING","LOBSTERING"],["CHECKERING","RECHECKING"],["EGOCENTRIC","GEOCENTRIC"],["CONCERTING","CONCRETING"],["DEDUCTIONS","DISCOUNTED"],["INDISCREET","IRIDESCENT"],["DISCOVERER","REDISCOVER"],["COMPRESSED","DECOMPRESS"],["PROCEDURES","REPRODUCES"],["DISCERNING","RESCINDING"],["DIRECTIONS","DISCRETION"],["DISTINCTER","INTERDICTS"],["INTRODUCES","REDUCTIONS"],["CERTIFYING","RECTIFYING"],["CONFIGURES","REFOCUSING"],["KITCHENING","THICKENING"],["CONTENTING","CONTINGENT"],["CONSERVING","CONVERSING"],["COUNTERING","RECOUNTING"],["INCEPTIONS","INSPECTION"],["PERCUSSION","SUPERSONIC"],["INTERVENED","REINVENTED"],["EXPEDITERS","PREEXISTED"],["DEVELOPERS","REDEVELOPS"],["FRIENDLIES","INFIELDERS"],["DEFROSTERS","FORTRESSED"],["MODERNIZES","SERMONIZED"],["LONGITUDES","UNGODLIEST"],["UNDERSIGNS","UNDRESSING"],["DEPOSITION","POSITIONED"],["PRESENTING","SERPENTING"],["LONGSTREET","LORGNETTES"],["IMPRESSIVE","PERMISSIVE"],["PETITIONER","REPETITION"],["PERSISTENT","PRETTINESS"],["POLYESTERS","PROSELYTES"],["MISFORTUNE","UNIFORMEST"],["PERSISTING","SPRINGIEST"],["GLOOMINESS","NEOLOGISMS"],["IMPRESSION","PERMISSION"],["INSTRUMENT","NUTRIMENTS"],["IMPORTUNES","RESUMPTION"],["SPOTLIGHTS","STOPLIGHTS"]])
(11,2,["AABCDEORRST","AACGGILNOTU","AACGHILLPRY","AAEIILNORTZ","AAEILMNPRST","ABCEEEILRSV","ABCEEFIILRT","ACDEEINORST","ACDEFIIINOT","ACDEINOORST","ACEEIIPPRTT","ACEINOOPRRT","ACGHIILMORT","ACIILLNOOST","ADEEILMNRST","ADEEIMNNOST","ADEIINOPRTT","ADEINNOOSTT","AEEIIMPRSTV","AEEILNTTTVY","AEEIMNNORTU","AEGHILNOOST","AEGIINNORTT","AEGIINNRSTT","AEIMNOPRTTU","CDEEEOPRRSS","CDEEIORRSSV","CDEIINNOORT","CDEIINOPRST","DEEFIIINNST","EEEINPRRSST","EEEIOPRRRST","EEGIINNNRTV","EEHLOPRRSTU","EEIINOPRSTT","EIIMNOPRSSS"],[["BROADCASTER","REBROADCAST"],["CATALOGUING","COAGULATING"],["CALLIGRAPHY","GRAPHICALLY"],["RATIONALIZE","REALIZATION"],["PARLIAMENTS","PATERNALISM"],["RECEIVABLES","SERVICEABLE"],["CERTIFIABLE","RECTIFIABLE"],["CONSIDERATE","DESECRATION"],["DEIFICATION","EDIFICATION"],["COORDINATES","DECORATIONS"],["PERIPATETIC","PRECIPITATE"],["INCORPORATE","PROCREATION"],["ALGORITHMIC","LOGARITHMIC"],["COLONIALIST","OSCILLATION"],["DERAILMENTS","STREAMLINED"],["DENOMINATES","EMENDATIONS"],["PARTITIONED","TREPIDATION"],["DENOTATIONS","DETONATIONS"],["IMPERATIVES","SEMIPRIVATE"],["ATTENTIVELY","TENTATIVELY"],["ENUMERATION","MOUNTAINEER"],["ANTHOLOGIES","THEOLOGIANS"],["INTEGRATION","ORIENTATING"],["REINSTATING","STRAITENING"],["IMPORTUNATE","PERMUTATION"],["PREDECESSOR","REPROCESSED"],["DISCOVERERS","REDISCOVERS"],["CONDITIONER","RECONDITION"],["DESCRIPTION","PREDICTIONS"],["INDEFINITES","INTENSIFIED"],["ENTERPRISES","INTERSPERSE"],["REPERTOIRES","REPERTORIES"],["INTERVENING","REINVENTING"],["REUPHOLSTER","UPHOLSTERER"],["PETITIONERS","REPETITIONS"],["IMPRESSIONS","PERMISSIONS"]])

```

# Answer
> 1 votes
## GolfScript (53 chars)

```
n/{[.$\]}%$'']({.1<2$<{1>+}*}/]9,{3+\{(,2$=*,}$)p}/];

```

or

```
n/{[.$\]}%$'']({.1<2$<{1>+}*}/]3{\{(,2$=*,}$)p\)}9*;;

```

I assume that there is at least one word of each length in the range processed: otherwise things will go badly wrong.

```
["AET" "ATE" "EAT" "ETA" "TAE" "TEA"]
["AELS" "ALES" "ELSA" "LEAS" "LESA" "SALE" "SEAL"]
["AELST" "LEAST" "SLATE" "STAEL" "STALE" "STEAL" "TALES" "TEALS" "TESLA"]
["ACERST" "CARETS" "CASTER" "CATERS" "CRATES" "REACTS" "RECAST" "TRACES"]
["ADEEGNR" "ANGERED" "DERANGE" "ENRAGED" "GRANDEE" "GRENADE"]
["AEGINRST" "ANGRIEST" "GANTRIES" "INGRATES" "RANGIEST" "TANGIERS"]
["AACEINRST" "ASCERTAIN" "CARTESIAN" "SECTARIAN"]
["EEINPRSSTT" "PERSISTENT" "PRETTINESS"]
["EEIINOPRSTT" "PETITIONERS" "REPETITIONS"]

```

Took about 2 minutes on my 2GHz 64-bit CPU.

# Answer
> 1 votes
# Mathematica 192

A bit wordy, but it returns multiple correct answers for the same word length (when they exist):

```
w = Flatten[Characters@Import["words.txt", "Data"], 1];
Table[Cases[#, {x_, Max[#[[All, -1]]]} :> {Characters@x[[1]], x}] &[{StringJoin /@ #,
Length[#]} & /@ GatherBy[Select[w, Length[#] == k &], Sort[#1] &]], {k, 3, 11}]

```

Timing: `1.228453 s`; 2.8 GHz Intel i7 Mac OS X 10.8.3

Results for lengths 3-9 are displayed below. There are too many winning combinations for sets of 10, 11 letters to be displayed here.

>

# Answer
> 0 votes
## J (96)

```
(echo@(((~.#~([=>./)@(#/.~))="0/[)@:((/:{[)&.>)#[)@((LF cut 1!:1[3)&([#~]=>@(#&.>)@[)))&.>3+i.9

```

It runs in a few seconds on my 2Ghz Pentium 4. It expects the wordlist on `stdin`, i.e. `cat wordlist | jconsole combinations.ijs`

Output:

```
┌───┬───┬───┬───┬───┐
│ATE│EAT│ETA│TAE│TEA│
└───┴───┴───┴───┴───┘
┌────┬────┬────┬────┬────┬────┐
│ALES│ELSA│LEAS│LESA│SALE│SEAL│
├────┼────┼────┼────┼────┼────┤
│ATES│EAST│EATS│SATE│SEAT│TEAS│
├────┼────┼────┼────┼────┼────┤
│OPTS│POST│POTS│SPOT│STOP│TOPS│
└────┴────┴────┴────┴────┴────┘
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│LEAST│SLATE│STAEL│STALE│STEAL│TALES│TEALS│TESLA│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
┌──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│CARETS│CASTER│CATERS│CRATES│REACTS│RECAST│TRACES│
└──────┴──────┴──────┴──────┴──────┴──────┴──────┘
┌───────┬───────┬───────┬───────┬───────┐
│ANGERED│DERANGE│ENRAGED│GRANDEE│GRENADE│
├───────┼───────┼───────┼───────┼───────┤
│ARIDEST│ASTRIDE│STAIDER│TARDIES│TIRADES│
├───────┼───────┼───────┼───────┼───────┤
│ARTIEST│ARTISTE│ATTIRES│IRATEST│TASTIER│
├───────┼───────┼───────┼───────┼───────┤
│CLAIMED│DECIMAL│DECLAIM│MALICED│MEDICAL│
├───────┼───────┼───────┼───────┼───────┤
│DEARTHS│HARDEST│HATREDS│THREADS│TRASHED│
├───────┼───────┼───────┼───────┼───────┤
│PARLEYS│PARSLEY│PLAYERS│REPLAYS│SPARELY│
├───────┼───────┼───────┼───────┼───────┤
│PERSIST│PRIESTS│SPRIEST│SPRITES│STRIPES│
└───────┴───────┴───────┴───────┴───────┘
┌────────┬────────┬────────┬────────┬────────┐
│ALERTING│ALTERING│INTEGRAL│RELATING│TRIANGLE│
├────────┼────────┼────────┼────────┼────────┤
│ANGRIEST│GANTRIES│INGRATES│RANGIEST│TANGIERS│
└────────┴────────┴────────┴────────┴────────┘
┌─────────┬─────────┬─────────┐
│ASCERTAIN│CARTESIAN│SECTARIAN│
├─────────┼─────────┼─────────┤
│AUCTIONED│CAUTIONED│EDUCATION│
├─────────┼─────────┼─────────┤
│BEASTLIER│BLEARIEST│LIBERATES│
├─────────┼─────────┼─────────┤
│CATTINESS│SCANTIEST│TACITNESS│
├─────────┼─────────┼─────────┤
│COUNTRIES│CRETINOUS│NEUROTICS│
├─────────┼─────────┼─────────┤
│CRATERING│RETRACING│TERRACING│
├─────────┼─────────┼─────────┤
│DANGERING│DERANGING│GARDENING│
├─────────┼─────────┼─────────┤
│DISSENTER│RESIDENTS│TIREDNESS│
├─────────┼─────────┼─────────┤
│EARTHLING│HALTERING│LATHERING│
├─────────┼─────────┼─────────┤
│EMIGRANTS│MASTERING│STREAMING│
├─────────┼─────────┼─────────┤
│ENLISTING│LISTENING│TINSELING│
├─────────┼─────────┼─────────┤
│ESTRANGES│GREATNESS│SERGEANTS│
├─────────┼─────────┼─────────┤
│MUTILATES│STIMULATE│ULTIMATES│
├─────────┼─────────┼─────────┤
│REDRAWING│REWARDING│WARDERING│
├─────────┼─────────┼─────────┤
│REPRISING│RESPIRING│SPRINGIER│
├─────────┼─────────┼─────────┤
│RESORTING│RESTORING│ROSTERING│
└─────────┴─────────┴─────────┘
┌──────────┬──────────┐
│ADMONITION│DOMINATION│
├──────────┼──────────┤
│AFTERWORDS│FORWARDEST│
├──────────┼──────────┤
│ALARMINGLY│MARGINALLY│
├──────────┼──────────┤
│ALGORITHMS│LOGARITHMS│
├──────────┼──────────┤
│ANCESTRIES│RESISTANCE│
├──────────┼──────────┤
│ANTAGONIST│STAGNATION│
├──────────┼──────────┤
│ARGENTINES│TANGERINES│
├──────────┼──────────┤
│ASCERTAINS│SECTARIANS│
├──────────┼──────────┤
│AUCTIONING│CAUTIONING│
├──────────┼──────────┤
│AUSTRALIAN│SATURNALIA│
├──────────┼──────────┤
│BANALITIES│INSATIABLE│
├──────────┼──────────┤
│BOLSTERING│LOBSTERING│
├──────────┼──────────┤
│BOULDERING│REDOUBLING│
├──────────┼──────────┤
│BROADSIDES│SIDEBOARDS│
├──────────┼──────────┤
│CATALOGUED│COAGULATED│
├──────────┼──────────┤
│CATALOGUES│COAGULATES│
├──────────┼──────────┤
│CATECHISMS│SCHEMATICS│
├──────────┼──────────┤
│CERTIFYING│RECTIFYING│
├──────────┼──────────┤
│CHATTERING│RATCHETING│
├──────────┼──────────┤
│CHECKERING│RECHECKING│
├──────────┼──────────┤
│CLEMATISES│TIMESCALES│
├──────────┼──────────┤
│COASTLINES│SECTIONALS│
├──────────┼──────────┤
│COLLAPSING│SCALLOPING│
├──────────┼──────────┤
│COMPRESSED│DECOMPRESS│
├──────────┼──────────┤
│CONCERTING│CONCRETING│
├──────────┼──────────┤
│CONFIGURES│REFOCUSING│
├──────────┼──────────┤
│CONSERVING│CONVERSING│
├──────────┼──────────┤
│CONTENTING│CONTINGENT│
├──────────┼──────────┤
│COORDINATE│DECORATION│
├──────────┼──────────┤
│COUNTERING│RECOUNTING│
├──────────┼──────────┤
│CREDENTIAL│INTERLACED│
├──────────┼──────────┤
│DEALERSHIP│LEADERSHIP│
├──────────┼──────────┤
│DECIMATING│MEDICATING│
├──────────┼──────────┤
│DECIMATION│MEDICATION│
├──────────┼──────────┤
│DEDUCTIONS│DISCOUNTED│
├──────────┼──────────┤
│DEFROSTERS│FORTRESSED│
├──────────┼──────────┤
│DENOMINATE│EMENDATION│
├──────────┼──────────┤
│DENOTATION│DETONATION│
├──────────┼──────────┤
│DEPOSITION│POSITIONED│
├──────────┼──────────┤
│DEVELOPERS│REDEVELOPS│
├──────────┼──────────┤
│DIRECTIONS│DISCRETION│
├──────────┼──────────┤
│DISCERNING│RESCINDING│
├──────────┼──────────┤
│DISCOVERER│REDISCOVER│
├──────────┼──────────┤
│DISTINCTER│INTERDICTS│
├──────────┼──────────┤
│EARTHINESS│HEARTINESS│
├──────────┼──────────┤
│EARTHLIEST│STEALTHIER│
├──────────┼──────────┤
│EARTHLINGS│SLATHERING│
├──────────┼──────────┤
│EGOCENTRIC│GEOCENTRIC│
├──────────┼──────────┤
│ENERVATING│VENERATING│
├──────────┼──────────┤
│ENERVATION│VENERATION│
├──────────┼──────────┤
│EXCITATION│INTOXICATE│
├──────────┼──────────┤
│EXPEDITERS│PREEXISTED│
├──────────┼──────────┤
│FILTRATION│FLIRTATION│
├──────────┼──────────┤
│FRIENDLIES│INFIELDERS│
├──────────┼──────────┤
│GLOOMINESS│NEOLOGISMS│
├──────────┼──────────┤
│GRENADINES│SERENADING│
├──────────┼──────────┤
│HOUSEWARES│WAREHOUSES│
├──────────┼──────────┤
│IMPORTUNES│RESUMPTION│
├──────────┼──────────┤
│IMPREGNATE│PERMEATING│
├──────────┼──────────┤
│IMPRESSION│PERMISSION│
├──────────┼──────────┤
│IMPRESSIVE│PERMISSIVE│
├──────────┼──────────┤
│INCEPTIONS│INSPECTION│
├──────────┼──────────┤
│INDISCREET│IRIDESCENT│
├──────────┼──────────┤
│INSTRUMENT│NUTRIMENTS│
├──────────┼──────────┤
│INTERVENED│REINVENTED│
├──────────┼──────────┤
│INTRODUCES│REDUCTIONS│
├──────────┼──────────┤
│KITCHENING│THICKENING│
├──────────┼──────────┤
│LONGITUDES│UNGODLIEST│
├──────────┼──────────┤
│LONGSTREET│LORGNETTES│
├──────────┼──────────┤
│MISDEALING│MISLEADING│
├──────────┼──────────┤
│MISFORTUNE│UNIFORMEST│
├──────────┼──────────┤
│MODERNIZES│SERMONIZED│
├──────────┼──────────┤
│MUTILATING│ULTIMATING│
├──────────┼──────────┤
│NECTARINES│TRANSIENCE│
├──────────┼──────────┤
│PATRICIDES│PEDIATRICS│
├──────────┼──────────┤
│PERCUSSION│SUPERSONIC│
├──────────┼──────────┤
│PERSISTENT│PRETTINESS│
├──────────┼──────────┤
│PERSISTING│SPRINGIEST│
├──────────┼──────────┤
│PERTAINING│REPAINTING│
├──────────┼──────────┤
│PETITIONER│REPETITION│
├──────────┼──────────┤
│PLATITUDES│STIPULATED│
├──────────┼──────────┤
│POLYESTERS│PROSELYTES│
├──────────┼──────────┤
│POSITIONAL│SPOLIATION│
├──────────┼──────────┤
│PRAETORIAN│REPARATION│
├──────────┼──────────┤
│PRESENTING│SERPENTING│
├──────────┼──────────┤
│PROCEDURES│REPRODUCES│
├──────────┼──────────┤
│RATIONALES│SENATORIAL│
├──────────┼──────────┤
│REGISTRANT│RESTARTING│
├──────────┼──────────┤
│REINSTATED│STRAITENED│
├──────────┼──────────┤
│SHATTERING│STRAIGHTEN│
├──────────┼──────────┤
│SOLITAIRES│SOLITARIES│
├──────────┼──────────┤
│SPOTLIGHTS│STOPLIGHTS│
├──────────┼──────────┤
│STATEMENTS│TESTAMENTS│
├──────────┼──────────┤
│STRIPTEASE│TAPESTRIES│
├──────────┼──────────┤
│SWARTHIEST│SWEATSHIRT│
├──────────┼──────────┤
│UNDERSIGNS│UNDRESSING│
├──────────┼──────────┤
│UNREADIEST│UNSTEADIER│
└──────────┴──────────┘
┌───────────┬───────────┐
│ALGORITHMIC│LOGARITHMIC│
├───────────┼───────────┤
│ANTHOLOGIES│THEOLOGIANS│
├───────────┼───────────┤
│ATTENTIVELY│TENTATIVELY│
├───────────┼───────────┤
│BROADCASTER│REBROADCAST│
├───────────┼───────────┤
│CALLIGRAPHY│GRAPHICALLY│
├───────────┼───────────┤
│CATALOGUING│COAGULATING│
├───────────┼───────────┤
│CERTIFIABLE│RECTIFIABLE│
├───────────┼───────────┤
│COLONIALIST│OSCILLATION│
├───────────┼───────────┤
│CONDITIONER│RECONDITION│
├───────────┼───────────┤
│CONSIDERATE│DESECRATION│
├───────────┼───────────┤
│COORDINATES│DECORATIONS│
├───────────┼───────────┤
│DEIFICATION│EDIFICATION│
├───────────┼───────────┤
│DENOMINATES│EMENDATIONS│
├───────────┼───────────┤
│DENOTATIONS│DETONATIONS│
├───────────┼───────────┤
│DERAILMENTS│STREAMLINED│
├───────────┼───────────┤
│DESCRIPTION│PREDICTIONS│
├───────────┼───────────┤
│DISCOVERERS│REDISCOVERS│
├───────────┼───────────┤
│ENTERPRISES│INTERSPERSE│
├───────────┼───────────┤
│ENUMERATION│MOUNTAINEER│
├───────────┼───────────┤
│IMPERATIVES│SEMIPRIVATE│
├───────────┼───────────┤
│IMPORTUNATE│PERMUTATION│
├───────────┼───────────┤
│IMPRESSIONS│PERMISSIONS│
├───────────┼───────────┤
│INCORPORATE│PROCREATION│
├───────────┼───────────┤
│INDEFINITES│INTENSIFIED│
├───────────┼───────────┤
│INTEGRATION│ORIENTATING│
├───────────┼───────────┤
│INTERVENING│REINVENTING│
├───────────┼───────────┤
│PARLIAMENTS│PATERNALISM│
├───────────┼───────────┤
│PARTITIONED│TREPIDATION│
├───────────┼───────────┤
│PERIPATETIC│PRECIPITATE│
├───────────┼───────────┤
│PETITIONERS│REPETITIONS│
├───────────┼───────────┤
│PREDECESSOR│REPROCESSED│
├───────────┼───────────┤
│RATIONALIZE│REALIZATION│
├───────────┼───────────┤
│RECEIVABLES│SERVICEABLE│
├───────────┼───────────┤
│REINSTATING│STRAITENING│
├───────────┼───────────┤
│REPERTOIRES│REPERTORIES│
├───────────┼───────────┤
│REUPHOLSTER│UPHOLSTERER│
└───────────┴───────────┘

```

# Answer
> 0 votes
## APL (91)

```
{⎕ML←3⋄{⎕←⍵/S}¨↓⍉K∘.≡Z/⍨T=⌈/T←+⌿K∘.≡Z←∪K←{⍵[⍋⍵]}¨S←W/⍨⍵=↑∘⍴¨W←W⊂⍨~⎕TC∊⍨W←80 ¯1⎕MAP'w'}¨2+⍳9

```

Expects the word list to be in a file called `w` in the current directory. Takes about four minutes to run (but it was running in a virtual machine).

The default workspace size in Dyalog APL is 64kb, this is not enough so you need to increase it (I set it to a megabyte).

Explanation:

* `⎕ML←3`: to make  work as partition
* `{`...`}¨2+⍳9`: for \[3..11\]
* `W←W⊂⍨~⎕TC∊⍨W←80 ¯1⎕MAP'w'`: read the `w` file and split on terminal control characters (newlines and tab)
* `S←W/⍨⍵=↑∘⍴¨W`: filter out the words of the current length
* `K←{⍵[⍋⍵]}¨S`: sort the letters of each word
* `T←+⌿K∘.≡Z←∪K`: for each unique bag of letters, see how many times it appears
* `Z/⍨T=⌈/T`: select those groups of letters that occur as many times as the most occuring one
* `↓⍉K∘.≡Z/⍨T`: for each group of letters and each word, select those words that have the same letters
* `{⎕←⍵/S}`: for each set of words, select those words from the non-sorted list and display them.

---
Tags: code-golf, word
---


# Question
Title: Smallest C code to Crash an Operating System?
A shortest C program, that can crash the Operating system, either on a Windows or a Linux PC...

**Rules**:

* The code is to be developed in C language, but it may use other api, specific to linux or windows systems.
* The Operating System is said to have been put out of commission, if either it has come to a state\[Standstill or otherwise\] , where no matter how much time passes, the system is rendered inoperable or (even better), self restarts itself, or something similar to a blue screen of death.
* To be most effective, the program will be run as a normal user and not as superuser or an administrator.
* For every valid program that is able to crash the PC, countermeasures can be suggested by others in the comments, successful measures that can nullify the effect of the program gets the answer invalidated. For Example - If an answer suggests use of fork Bombs, i would suggest measures like this in the comments.
* Since Linux OS is considered more stable, a program that crashes linux is always a better one, even if it takes extra code than it takes to crash windows, but still the smallest program to crash the OS wins, independent of the platform.
* The community is free to edit the question to add more *sensible* rules, provided the new rules maintain compatibility with existing answers.

Note: This above question is asked with the purpose of demonstrating the raw power of C\[or the lack of it\] as a low level/mid level language. Also hopefully, to become more aware of OS security, and possible measures that can be taken.

**EDIT:**

A similar question lies here Code Golf of Death...

But here are the reasons my question differs from the above mentioned one...

1. I am looking for the answers to only be in C language.
2. Though the above question has one answer in C, the code works only for a rare version of pentium 5. So in short there is no C language based answer in the above question to achieve the end purpose.
3. In the other question Kernel-mode drivers are allowed, but my question concentrates mainly on user space processes.
4. Some of the answers in the above question allow the programs to run in supervisor/administrator mode, but such privileged execution of the program is not allowed in the rules stated by my question.
5. In the similar question the answer with highest upvotes win, in my question answer which crashes the OS , using the shortest code, and does so without any suggestion of countermeasure to be taken against the method employed by the answer.
6. **In short, apart from the same intention of crashing the OS , the two questions differ in every other aspect.**

# Answer
> 6 votes
## 29 chars

### Linux

```
int main(){system("init 6");}

```

I know, very lame. But hey, it reboots the system. Wasn't that the task?

### Windows 38 chars

```
int main(){system("shutdown.exe /r");}

```

Works as normal user.

---
Tags: code-golf, c
---


# Question
Title: Write a program to print squares of integers up to 25 in java without using variables?
I asked this question on programmers 10 days back but wasn't able to get the answer that I wanted.

Write program in java to print the squares of first 25 integers(1-25) without using any variables.

I am not looking for any theory explaining concepts about java or functional programming. I just want to know if its possible in java, the way the author has described in the original context.

--------Edit-------------------- Actually making it mutable variable makes it quite easy. The original context was

> (take 25 (squares-of (integers))) Notice that it has no variables. Indeed, it has nothing more than three functions and one constant. Try writing the squares of integers in Java without using a variable. Oh, there’s probably a way to do it, but it certainly isn’t natural, and it wouldn’t read as nicely as my program above.

So try writing same program without using any variables.

# Answer
> 5 votes
Ugly hack in 216 characters, this does not even use method args:

```
class M{static void m(){System.out.println((Thread.currentThread().getStackTrace().length-2)*(Thread.currentThread().getStackTrace().length-2));if(Thread.currentThread().getStackTrace().length-2<25)m();}static {m();}}

```

Formatted, this looks like:

```
class M {
    static void m()
    {
        System.out.println((Thread.currentThread().getStackTrace().length-2)*(Thread.currentThread().getStackTrace().length-2));
        if (Thread.currentThread().getStackTrace().length-2 < 25) m();
    }
    public static void main(String[] a)
    {
        m();
    }
    // We can comply fully with the question (no variables),
    // but then cannot avoid the "java.lang.NoSuchMethodError: main":
    static
    {
        m();
    }
}

```

For those who don't understand: It takes the stacks length squares it. This works because I'm recursively calling `m()`, always increasing the stack by 1. Maybe this could be written even shorter.

# Answer
> 10 votes
Obligatory cheat:

```
public class PrintTwentyFiveSquares {

    public static void main() {
        System.out.println("1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625");
    }

}

```

# Answer
> 1 votes
How about this?

```
public class Squares {
    public static void printSquares(final int n) {
        if (n > 1) {
            printSquares(n - 1);
        }
        System.out.println(n * n);
    }

    public static void main(final String... args) {
        printSquares(25);
    }
}

```

Now that you completely changed the question, my solution depends on whether you consider function arguments to be variables or not. I'd say it still stands.

I should add that the Closure solution depends on the pre-availability of several functions in the standard library. The same functions could be written in Java, leading to a nearly identical main program:

```
import java.util.AbstractList;
import java.util.List;

public class Squares2 {
    public static List<Integer> integers() {
        return new AbstractList<Integer>() {
            @Override
            public Integer get(final int index) {
                return index + 1;
            }

            @Override
            public int size() {
                return Integer.MAX_VALUE;
            }
        };
    }

    public static List<Integer> squaresOf(final List<Integer> l) {
        return new AbstractList<Integer>() {
            @Override
            public Integer get(final int index) {
                return l.get(index) * l.get(index);
            }

            @Override
            public int size() {
                return l.size();
            }
        };
    }

    public static List<Integer> take(final int n, final List<Integer> l) {
        return l.subList(0, n);
    }

    public static void main(final String... args) {
        System.out.println(take(25, squaresOf(integers())));
    }
}

```

---
Tags: code-challenge, java
---


# Question
Title: exp function to an arbitrary double precision
Write a function to find the solution of e^x given x, and a precision in the form 0.000001.

sample input and output: `e(4,0.00001)` will return `54.5981494762146`, and the precision is +/- `.00001`. The output would be acceptable in the range `54.59814 <= output <= 54.59816`, you are not required to truncate the answer to the number of significant figures in the input precision.

Your example will be expected to take a precision of at least size `double` (64 bits) and an x of at least size `int` (32 bits). Overflows will not be counted against you; I do not expect passing INT\_MAX as x to work.

Use whatever algorithm suits you, but do not use math library functions such as builtin `pow`, `factorial`, `exp`, or builtin predefined constants for `e`, `pi`, etc.

The objective primary winning criterion is size of submission in bytes, ignoring comments and unnecessary whitespace.

Ties will be broken via runtime speed.

This will last at least one week (ending Thursday, May 16) with each new entry extending the deadline to three days from the entry date.

# Answer
> 0 votes
## APL (36)

```
{x t←⍺⍵⋄0{t>i←(x*⍵)÷!⍵:⍺⋄∇/⍺⍵+i 1}0}

```

The left argument is the number and the right argument is the tolerance, i.e.

```
      4 {x t←⍺⍵⋄0{t>i←(x*⍵)÷!⍵:⍺⋄∇/⍺⍵+i 1}0}  0.00001
54.59814722

```

It uses a power series expansion.

Explanation:

* `x t←⍺⍵`: store the left argument (x) in `x` and the right argument (tolerance) in `t`
* `0{`...`}0`: iterator function,  is the accumulator and  is the iteration
* `t>i←(x*⍵)÷!⍵`: calculate the current iteration's value, and see if it is higher than the tolerance
* `:⍺`: if so, return the accumulator
* `⋄∇/⍺⍵+i 1`: if not, increment the accumulator by `i` and the iteration by `1` and try again.

# Answer
> 2 votes
# Mathematica, 90

```
f[x_,p_]:=Piecewise[{{Sum[x^i/i!,{i,0,50}],x>0},{1/Sum[(-x)^i/i!,{i,0,50}],x<0},{1,x==0}}]

```

I also ignore the precision `p` and assume that 20 decimal points will be the most accuracy desired. It also works for negative values of `x`! To be worked on more later.

# Python, 88

```
def E(x,p):
 t=n=s=1.;y=x
 if x<0:y=-x
 while t:t*=y/n;n+=1;s+=t
 if x<0:s=1/s
 return s

```

**Why the Power Series approach does not work without cases:**

The issue with the taylor series for `e(x)` centered at the origin is that it is alternating for negative `x`. When the distance from the origin is small, say `x= -1 or -2` then this is not an issue as we get convergence to 20 decimal places after about 20-30 terms of the power series. However when the distance from the origin grows all hell breaks loose. Observe the pattern for `x= -1` where `f[x,n]` refers to the taylor series with `n+1` terms.

```
Exp[-20] = 2.0611536224385578280*10^-9
f[-20,1] = -19.000000000000000000
f[-20,2] = 181.00000000000000000
f[-20,3] = -1152.3333333333333333
f[-20,4] = 5514.3333333333333333
...
f[-20,10] = 1.8596236807760141093*10^6
f[-20,15] = -1.4140053694562736891*10^7
f[-20,20] = 2.1277210342544299144*10^7
f[-20,30] = 1.5996940964229284082*10^6
f[-20,40] = 4442.0343631250907290
f[-20,50] = 1.0469169720658217252
f[-20,60] = 0.000034317328370370852087
f[-20,70] = 2.2782871646157681977*10^-9

```

It takes until term 70 to get within .000000001 of the true value, and I was being kind using `x= -20`. If we try numbers as low as `x= -500` we are more than `10^200` off at term 500. Now lets see, what are we even working with at this point, iteration 500, this should include the term `x^500/500!`. `500!` if of the order `10^1134`, but python and other programming languages are not equipped to deal with numbers much larger than `2^63` as integers or `10^308` for doubles (unless you have some sort of arbitrary precision library...?)

# Answer
> 1 votes
## Python, 59 57 chars

```
def E(x,p):
 t=n=s=1.
 while t:t*=x/n;n+=1;s+=t
 return s

```

Uses the power series expansion of `e^x`. Ignores `p` and just calculates the result to full double precision.

# Answer
> 0 votes
## C, ~~88~~ 69

~~```
double e(int e, double l) {double a,p=1,i=0,f=1,r=1;while ((a=(p*=e)/(f*=++i))>l) r+=a;return r;}

```~~
```
double e(int x, double l) {double i=0,t=1,r=1;while (t*=x/++i) r+=t;return r;}

```

call `e`. if you change the first argument to `e` from `int` to `double`, it will even work for floating point exponents.

Code counted without any white space or comments.

Edited some ideas from Keith into it (combine `p` and `f` into `t`, ignore `l`).

Yes, power series is the way to go. Sure, once one got the idea, everyone copy it.

# Answer
> 0 votes
**JavaScript, 50 Chars**

Given that javascript has variable args support, this will work with the input `e(4,0.00001)`. Otherwise, it would be 52 chars.

```
function e(x){for(t=n=s=1;t*=x/n++;s+=t);return s}

```

ideone

If it is going to factor in the precision as the problem states, it can be done in 56 chars.

```
function e(x,p){for(t=n=s=1;(t*=x/n++)>p;s+=t);return s}

```

---
Tags: code-golf, math
---


title: ASCII-visualize a graph

text:
# Question
Title: ASCII-visualize a graph
Your mission, should you choose to accept it, is to input a series of point pairs that form a graph, like this:

> A,B C,A B,A A,D A,E F,G C,G

You must then output an ASCII visualization of the graph.

For example, `A,B C,A C,D` could be:

```
A-----------------B
 \
  \
   C---------D

```

Edit: As per the comments, here are some input constraints:

* each node has at most 5 connections (+20 if you can handle more)
* the graph is planar, i.e. no lines cross (+200 if you can handle even one crossover!)
* there are at most 16 nodes (+20 if you can handle more)

Your score is **999 - (your code length) + (any bonuses)**.

Start your engines :)

# Answer
# Python 3, 168 chars, Score = 999- 168 + 240 = 1071

Just shortening **Keith Randalls great answer**.

1. In Python 3, `print` is a function, and therefore can be abbreviated by `p=print`. Saves `3 * (4 - 1) - 8 = 1` character.
2. In Python 3, `input` is used instead of `raw_input`, saves 4 characters.
3. Instead of `' '*len(V)` you can use `' '*80` (or something similar). This leads to an increased number of trailing spaces, but who cares... if it saves another 4 characers!
4. Now it gets interesting: Instead of strings, use lists! This makes the updating of `S` much easier, but complicates printing somewhat. I'll call the list `T` so I'll not confuse it with the string `S` from marinus.
5. Let's start by turning the *vertices* into a list, not a space-seperated string, which saves 4 characters. The output line `T` has to become a list (`T=[' ']*40`), which costs 2 characters.
6. The printing of the *current line* `T` becomes 5 characters longer: I need brackets to concatenate the lists of strings correctly, I need two more `-` characters (because x and y are only about half as large now), and I need a `*` to make the `print` function take the elements of the list as seperate arguments and print them out seperated by spaces (and not as a list!). (This step was *hard*.)
7. The current line can be updated with a simple `T[x]=T[y]="|"` instead of `S=S[:x]+'|'+S[x+1:y]+'|'+S[y+1:]`, which saves 19 characters.
8. For printing `T` again, and for the final spaced printing of the vertices, asterisks are needed, which costs 2 characters.
9. And just while I am typing this, I see that there is no harm in having an unconnected invisible vertex (`' '`). This allows to create the set of vertices much shorter, saving 4 more characters.

Altogether, the saving is `1 + 4 + 4 + 4 - 2 - 5 + 19 - 2 + 4 = 27`.

```
R=input()
p=print
V=list(set(R)-{','})
T=[' ']*40
for e in R.split():x,y=sorted(map(V.index,e[::2]));p(*T[:x]+["+"+"--"*(y-x-1)+"-+"]+T[y+1:]);T[x]=T[y]="|";p(*T)
p(*V)

```

Example showing the effect of 9.: input `A,B A,C` leads to output

```
+-----+
|     |
+---+ |
|   | |
A   C B

```
> 7 votes

# Answer
## APL (~~171~~ ~~166~~ 162 chars, all bonuses: 999 - ~~171~~ ~~166~~ 162 + 20 + 20 + 200 = ~~1068~~ ~~1073~~ 1077)

This is the longest golfed APL program I've written so far. This might be slightly cheating, but there's nothing in the question that actually disallows this. What I'm doing is putting all the nodes on a vertical line and drawing the graph as an arc diagram. It is obviously still a graph though.

It still took me a few hours.

```
V←' '⍴⍨99,⍨2×⍴P←∪,C←(2,⍨2÷⍨⍴G)⍴G←G/⍨⎕A∊⍨G←⍞⋄V[2×⍳⍴P;50]←P⋄M←1⋄G←⍴D←{⍵[⍋⍵]}¨↓P⍳C⋄{V[A B←⍵;L←50+M×⌽⍳G]∘←'-'⋄V[A+⍳B-A;⊃L]∘←'|'⋄V[⍵;⊃L]∘←'+'⋄M×←¯1⋄G-←1}¨2×D[⍒|-/↑D]⋄V

```

The nodes must be single uppercase letters, so it supports 26 nodes maximum. It can handle crossed lines, and each node can have as many connections as the display will handle.

Example output:

```
A,B C,A C,D

      +-A--+
      |    |
      +-B  |
           |
        C+-+
         |
        D+

A,B C,A B,A A,D A,E F,G C,G

          +--A-+-+-+
          |    | | |
          |  B-+ | |
          |      | |
        +-+--C   | |
        |        | |
        |    D---+ |
        |          |
        |    E-----+
        |
        |   +F
        |   |
        +---+G

 T,H E,Q U,I C,K B,R O,W N,F O,X J,U M,P S,O V,E R,T H,E L,A Z,Y D,O G,S

               +---+----------T
               |   |
               |   +-------+--H
               |           |
               |           +--E---------+-------+
               |                        |       |
               |              Q---------+       |
               |                                |
               |     +--------U---------------+ |
               |     |                        | |
               |     +--------I               | |
               |                              | |
               |              C-------+       | |
               |                      |       | |
               |              K-------+       | |
               |                              | |
               |       +------B               | |
               |       |                      | |
               +-------+------R               | |
                                              | |
             +----------------O-----+-----+-+ | |
             |                      |     | | | |
             |                W-----+     | | | |
             |                            | | | |
             |           +----N           | | | |
             |           |                | | | |
             |           +----F           | | | |
             |                            | | | |
             |                X-----------+ | | |
             |                              | | |
             |                J-------------|-+ |
             |                              |   |
             |                M---+         |   |
             |                    |         |   |
             |                P---+         |   |
             |                              |   |
             |   +------------S-------------+   |
             |   |                              |
             |   |            V-----------------+
             |   |
             |   |            L-+
             |   |              |
             |   |            A-+
             |   |
             |   |           +Z
             |   |           |
             |   |           +Y
             |   |
             +---|------------D
                 |
                 +------------G

```
> 20 votes

# Answer
## Python, 195 chars, score = 999 - 195 + 20 + 200 + 20 = 1044

```
R=raw_input()
V=' '.join(set(R)-set(' ,'))
S=' '*len(V)
for e in R.split():x,y=sorted(map(V.index,e[::2]));print S[:x]+'+'+'-'*(y-x-1)+'+'+S[y+1:];S=S[:x]+'|'+S[x+1:y]+'|'+S[y+1:];print S
print V

```

Each edge gets a row. S is a string with the vertical connections we need to keep as we build the graph.

Here are some sample input/output:

```
A,B C,A B,A A,D A,E F,G C,G
+---+
|   |
+-+ |
| | |
+---+
| | |
+-------+
| | |   |
+-----+ |
| | | | |
| | | | | +-+
| | | | | | |
| +-------+ |
| | | | | | |
A C B E D G F

```

and stolen from marinus:

```
T,H E,Q U,I C,K B,R O,W N,F O,X J,U M,P S,O V,E R,T H,E L,A Z,Y D,O G,S
                +-----------------------+
                |                       |
      +-----------------------+         |
      |         |             |         |
      |       +-----------------------+ |
      |       | |             |       | |
  +---------------+           |       | |
  |   |       | | |           |       | |
  | +-------------------------------+ | |
  | | |       | | |           |     | | |
  | | |       | | |       +---------------+
  | | |       | | |       |   |     | | | |
  | | |     +---------------+ |     | | | |
  | | |     | | | |       | | |     | | | |
  | | |     | | | |       +---------------------+
  | | |     | | | |       | | |     | | | |     |
  | | |     | | | | +-----------------+ | |     |
  | | |     | | | | |     | | |     | | | |     |
  | | |     | | | | | +---------+   | | | |     |
  | | |     | | | | | |   | | | |   | | | |     |
  | | |     | | | | | |   +-------+ | | | |     |
  | | |     | | | | | |   | | | | | | | | |     |
  | | +-------------------------------------+   |
  | | |     | | | | | |   | | | | | | | | | |   |
  | | |     | | | | | |   | | | | | +---+ | |   |
  | | |     | | | | | |   | | | | | | | | | |   |
  | | +---------+ | | |   | | | | | | | | | |   |
  | | |     | | | | | |   | | | | | | | | | |   |
+-----------------------+ | | | | | | | | | |   |
| | | |     | | | | | | | | | | | | | | | | |   |
| | | |     | | | | | | | | | | | | | | | | | +---+
| | | |     | | | | | | | | | | | | | | | | | | | |
| | | | +-----------------+ | | | | | | | | | | | |
| | | | |   | | | | | | | | | | | | | | | | | | | |
| | | | | +-----------------------+ | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | |
A C B E D G F I H K J M L O N Q P S R U T W V Y X Z

```
> 8 votes

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


title: Number of holes in a polygon

text:
# Question
Title: Number of holes in a polygon
**The Problem**: Count the number of holes in a connected polygon. Connectivity of the polygon is guaranteed by the condition that every triangle in the input triangulation shares at least 1 side with another triangle and that there is only one such connected set of triangles.

Input is a list `L` of `n` points in the plane and a list `T` of 3-tuples with entries from `0...n-1`. For each item in `T` the tuple `(t_1,t_2,t_3)` represents the three vertices (from the list `L`) of a triangle in the triangulation. Note that this is a triangulation in the sense of 'polygon triangulation', because of this there will never be two triangles in `T` that overlap. An additional stipulation is that you will not have to sanitize the input, `L` and `T` do not contain any repeats.

**Example 1**: If `L = {{0,0},{1,0},{0,1},{1,2}}` and `T = {{0,1,2},{1,2,3}}` then the polygon specified has a hole count of 0.

**Example 2**: If `L = {{0,0},{1,0},{2,0},{2,1},{2,2},{1,2},{0,2},{0,1},{.5,.5},{1.5,.5},{1.5,1.5},{.5,1.5}}` and `T = {{5,6,11},{5,10,11},{4,5,10},{3,8,10},{2,3,9},{2,8,9},{1,2,8},{0,1,8},{0,8,11},{0,7,11},{6,7,11},{3,4,10}}` then the polygon input should result in an output of 2.

The task is to write the shortest program (or function) that takes `L` and `T` as input and returns the number of holes. The 'winner' will be recognized as the entry with the least character count (tentative end date 1st of June).

Sample input formatting (note the 0 indexing):

```
0,0
1,0
0,1
1,2
0,1,2
1,2,3

```

# Answer
> 5 votes
## GolfScript (23 chars)

```
~.{2*2/~}%{$}%.&,@@+,-)

```

Assumes input format using GolfScript array notation and quoted (or integral) coordinates. E.g.

```
$ golfscript codegolf11738.gs <<<END
[["0" "0"] ["1" "0"] ["2" "0"] ["2" "1"] ["2" "2"] ["1" "2"] ["0" "2"] ["0" "1"] [".5" ".5"] ["1.5" ".5"] ["1.5" "1.5"] [".5" "1.5"]] [[5 6 11] [5 10 11] [4 5 10] [3 8 10] [2 3 9] [2 8 9] [1 2 8] [0 1 8] [0 8 11] [0 7 11] [6 7 11] [3 4 10]]
END
2

```

(Online equivalent)

or

```
$ golfscript codegolf11738.gs <<<END
[[0 0] [1 0] [0 1] [1 2]] [[0 1 2] [1 2 3]]
END
0

```

(Online equivalent)

# Answer
> 5 votes
# Python, 71

What follows is a *program* (not a *function*) that calculates the desired number.

```
len(set().union(*(map(frozenset,zip(t,t[1:]+t))for t in T)))-len(L+T)+1

```

Example usage:

```
>>> L = ((0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,1),(.5,.5),(1.5,.5),(1.5,1.5),(.5,1.5))
>>> T = ((5,6,11),(5,10,11),(4,5,10),(3,8,10),(2,3,9),(2,8,9),(1,2,8),(0,1,8),(0,8,11),(0,7,11),(6,7,11),(3,4,10))
>>> len(set().union(*(map(frozenset,zip(t,t[1:]+t))for t in T)))-len(L+T)+1
2

```

# Answer
> 3 votes
## APL, 36

```
{1+(⍴⊃∪/{{⍵[⍋⍵]}¨,/3 2⍴⍵,⍵}¨⍵)-⍴⍺,⍵}

```

The function takes `L` as its left argument and `T` as its right.

For example:

```
      L←(0 0)(1 0)(0 1)(1 2)
      T←(0 1 2)(1 2 3)
      L{1+(⍴⊃∪/{{⍵[⍋⍵]}¨,/3 2⍴⍵,⍵}¨⍵)-⍴⍺,⍵}T
0
      L←(0 0)(1 0)(2 0)(2 1)(2 2)(1 2)(0 2)(0 1)(.5 .5)(1.5 .5)(1.5 1.5)(.5 1.5)
      T←(5 6 11)(5 10 11)(4 5 10)(3 8 10)(2 3 9)(2 8 9)(1 2 8)(0 1 8)(0 8 11)(0 7 11)(6 7 11)(3 4 10)
      L{1+(⍴⊃∪/{{⍵[⍋⍵]}¨,/3 2⍴⍵,⍵}¨⍵)-⍴⍺,⍵}T
2

```

---

Explanation, going from right to left:

* `⍴⍺,⍵` concatenates the two input vectors and returns their length (`V + F`)
* Stepping inside the next block:
    + `¨⍵` applies the function on the left to every element of the right argument and returns the result
    + `⍵,⍵` returns the right argument concatenated with itself
    + `3 2⍴` shapes the vector argument into three pairs. In this case it pairs together the first and second, third and first, and second and third items of the vector.
    + `,/` joins the vector argument together
    + `⍵[⍋⍵]` sorts the right argument
    + `∪/` filters out any duplicates
    + `⍴⊃` turns a nested scalar into a vector, and it returns the length of it.
    + The whole function returns the number of edges in the shape (`E`)
* `1` is self-explanatory (I hope...)

The whole function then returns `1+E-(V+F)`, or `1-(F+V-E)`.

# Answer
> 2 votes
## Mathematica, 93 (not much golfed yet)

```
f[l_, t_] :=  Max@MorphologicalComponents[Erosion[Graphics[
                                                        GraphicsComplex[l, Polygon[t + 1]]], 1]] - 1

```

(Spaces added for clarity)

Testing:

```
f[{{0, 0}, {1, 0}, {0, 1}, {1, 2}}, {{0, 1, 2}, {1, 2, 3}}]
(*
 -> 0
*)

{l, t} = {{{0, 0}, {1,   0}, {2,    0}, {2,     1}, {2,    2}, {1, 2}, {0, 2},
           {0, 1}, {.5, .5}, {1.5, .5}, {1.5, 1.5}, {.5, 1.5}},

           {{5, 6, 11}, {5, 10, 11}, {4, 5, 10}, {3, 8, 10}, {2, 3,  9},
            {2, 8,  9}, {1,  2,  8}, {0, 1,  8}, {0, 8, 11}, {0, 7, 11}, {6, 7, 11}, {3, 4, 10}}};
f[l, t]
 (*
  -> 2
 *)

```

# Answer
> 2 votes
# Mathematica 76 73 72 67 62

After much experimentation, I came to realize that the precise location of the vertices was of no concern, so I represented the problem with graphs. The essential invariants, the number of triangles, edges and vertices stayed invariant (provided line crossing was avoided).

There were two kinds of internal "triangles" in the graph: those were there was presumably a face, i.e. a "filled" triangle, and those where there were not. The number of internal faces did not have any relation to the edges or vertices. That meant that poking holes in fully "filled" graphs only reduced the number of faces. I played systematically with variations among triangles, keeping track of the faces, vertices and edges. Eventually I realized that the number of holes always was equal to 1 - #faces -#vertices + #edges. This turned out to be 1 minus the Euler characteristic (which I only had known about in the context of regular polyhedra (although the length of the edges was clearly of no importance.

The function below returns the number of holes when the vertices and triangles are input. Unlike my earlier submission, it does not rely on a scan of an image. You can think of it as 1 - Euler's characteristic, i.e. 1 - (F +V -E) where`F`= #faces, `V`=#vertices, `E`=#edges. The function returns the number of holes, `1 - (F + V -E)`, given the actual faces (triangles) and vertices.

It can be easily shown that the removal of any triangle on the outside of the complex has no affect on the Euler characteristic, regardless of whether it shares one or 2 sides with other triangles.

Note: The lower case `v` will be used in place of the `L` from the original formulation; that is, it contains the vertices themselves (not V, the number of vertices)

`f` is used for the `T` from the original formulation; that is, it contains the triangles, represented as the ordered triple of vertex indices.

**Code**

```
z=Length;1-z@#2-z@#+z[Union@@(Sort/@{#|#2,#2|#3,#3|#}&@@@#2)]&

```

(Thanks to Mr. Wizard for shaving off 5 chars by eliminating the replacement rule.)

---

**Example 1**

v = {{0, 0}, {1, 0}, {0, 1}, {1, 2}}; f = {{0, 1, 2}, {1, 2, 3}};

```
z=Length;1-z@#2-z@#+z[Union@@(Sort/@{#|#2,#2|#3,#3|#}&@@@#2)]&[v, f]

```

> 0

Zero holes.

---

**Example 2**

v = {{0, 0}, {1, 0}, {2, 0}, {2, 1}, {2, 2}, {1, 2}, {0, 2}, {0, 1}, {.5, .5}, {1.5, .5}, {1.5, 1.5}, {.5, 1.5}}; f = {{5, 6, 11}, {5, 10, 11}, {4, 5, 10}, {3, 8, 10}, {2, 3, 9}, {2, 8, 9}, {1, 2, 8}, {0, 1, 8}, {0, 8, 11}, {0, 7, 11}, {6, 7, 11}, {3, 4, 10}};

```
z=Length;1-z@#2-z@#+z[Union@@(Sort/@{#|#2,#2|#3,#3|#}&@@@#2)]&[v, f]

```

> 2

Thus, 2 holes are in example 2.

# Answer
> 2 votes
### Ruby, 239 characters (227 body)

```
def f t
e=t.flat_map{|x|x.permutation(2).to_a}.group_by{|x|x}.select{|_,x|x.one?}.keys
n=Hash[e]
(u,n=n,n.dup;e.map{|x|a,b=*x;n[a]=n[n[a]]=n[b]})until n==u
n.values.uniq.size+e.group_by(&:last).map{|_,x|x.size}.reduce(-1){|x,y|x+y/2-1}
end

```

note that I'm only considering the topology. I'm not using the vertex positions in any way.

caller (expects T in Mathematica or JSON format):

```
input = gets.chomp
input.gsub! "{", "["
input.gsub! "}", "]"
f eval(input)

```

Test:

```
f [[0,1,2],[1,2,3]]
#=> 0
f [[5, 6, 11], [5, 10, 11], [4, 5, 10], [3, 8, 10], [2, 3, 9], [2, 8, 9], [1, 2, 8], [0, 1, 8], [0, 8, 11], [0, 7, 11], [6, 7, 11], [3, 4, 10]]
#=> 2
f [[1,2,3],[3,4,5],[5,6,1],[2,3,4],[4,5,6],[6,1,2]]
#=> 1

```

# Answer
> 1 votes
### Python, 107

I realized that taking the pairs directly was shorter than `from itertools import*` and typing `combinations()`. Yet I also noticed that my solution relied on the input triangular faces having their vertices listed in consistent order. Therefore the gains in character count are not that large.

```
f=lambda l,t:1-len(l+t)+len(set([tuple(sorted(m))for n in[[i[:2],i[1:],[i[0],i[2]]]for i in t]for m in n]))

```

### Python, 115

Euler characteristic approach, the verbosity of itertools seems impossible to avoid. I wonder if it would be cheaper to use a more direct technique for making pairs of vertices.

```
from itertools import*
f=lambda l,t:1-len(l+t)+len(set([m for n in[list(combinations(i,2)) for i in t]for m in n]))

```

Usage example:

```
> f([[0,0],[1,0],[0,1],[1,2]],[[0,1,2],[1,2,3]])
> 0
> f([[0,0],[1,0],[2,0],[2,1],[2,2],[1,2],[0,2],[0,1],[.5,.5],[1.5,.5],[1.5,1.5],[.5,1.5]],[[5,6,11],[5,10,11],[4,5,10],[3,8,10],[2,3,9],[2,8,9],[1,2,8],[0,1,8],[0,8,11],[0,7,11],[6,7,11],[3,4,10]])
> 2

```

---
Tags: code-golf, geometry
---


title: Find real roots of a polynomial

text:
# Question
Title: Find real roots of a polynomial
Write a self-contained program which when given a polynomial and a bound will find all real roots of that polynomial to an absolute error not exceeding the bound.

### Constraints

I know that Mathematica and probably some other languages have a one-symbol solution, and that's boring, so you should stick to primitive operations (addition, subtraction, multiplication, division).

There is certain flexibility on the input and output formats. You may take input via stdin or command-line arguments in any reasonable format. You may allow floating point or require that some representation of rational numbers be used. You may take the bound or the reciprocal of the bound, and if you're using floating point you may assume that the bound will not be less than 2 ulp. The polynomial should be expressed as a list of monomial coefficients, but it may be big- or little-endian.

You must be able to justify why your program will always work (modulo numerical issues), although it's not necessary to supply full proofs inline.

The program must handle polynomials with repeated roots.

### Example

```
x^2 - 2 = 0 (error bound 0.01)

```

Input could be e.g.

```
-2 0 1 0.01
100 1 0 -2
1/100 ; x^2-2

```

Output could be e.g.

```
-1.41 1.42

```

but not

```
-1.40 1.40

```

as that has absolute errors of about 0.014...

### Test cases

Simple:

```
x^2 - 2 = 0 (error bound 0.01)

x^4 + 0.81 x^2 - 0.47 x + 0.06 (error bound 10^-6)

```

Multiple root:

```
x^4 - 8 x^3 + 18 x^2 - 27 (error bound 10^-6)

```

Wilkinson's polynomial:

```
x^20 - 210 x^19 + 20615 x^18 - 1256850 x^17 + 53327946 x^16 -1672280820 x^15 +
    40171771630 x^14 - 756111184500 x^13 + 11310276995381 x^12 - 135585182899530 x^11 +
    1307535010540395 x^10 - 10142299865511450 x^9 + 63030812099294896 x^8 -
    311333643161390640 x^7 + 1206647803780373360 x^6 -3599979517947607200 x^5 +
    8037811822645051776 x^4 - 12870931245150988800 x^3 + 13803759753640704000 x^2 -
    8752948036761600000 x + 2432902008176640000  (error bound 2^-32)

```

---

*NB This question was in the Sandbox for approximately 3 months. If you think it needed improving before posting, visit the Sandbox and comment on the other proposed questions* before *they are posted on Main.*

# Answer
> 8 votes
### Mathematica, 223

```
r[p_,t_]:=Module[{l},l=Exponent[p[x],x];Re@Select[NestWhile[Table[#[[i]]-p[#[[i]]]/Product[If[i!=j,#[[i]]-#[[j]],1],{j,l}],{i,l}]&,Table[(0.9+0.1*I)^i,{i,l}],2*Max[Table[Abs[#1[[i]]-#2[[i]]],{i,l}]]>t&,2],Abs[Im[#]]<t^.5&]]

```

This solution implements the Durand–Kerner method for solving polynomials. Note that this is not a complete solution (as will be shown below) because I cannot yet handle Wilkinson's Polynomial to the specified precision. First an explanation of what I'm doing:

`#[[i]]-p[#[[i]]]/Product[If[i!=j,#[[i]]-#[[j]],1],{j,l}]&`: Thus function computes for each index `i` the next Durand-Kerner approximation. Then this line is encapsulated in a Table and applied using a NestWhile to the input points generated by `Table[(0.9+0.1*I)^i,{i,l}]`. The condition on the NestWhile is that the max change (over all terms) from one iteration to the next is greater than the specified precision. When all terms have changed less than this, the NestWhile ends and `Re@Select` removes the zeros that do not fall on the real line.

Example output:

```
> p[x_] := x^2 - 2
> r[p, .01]
{1.41421, -1.41421}

> p[x_] := x^4 - 8 x^3 + 18 x^2 - 27
> r[p, 10^-6]
{2.99999, 3., 3.00001, -1.}

> p[x_] := x^20 - 210 x^19 + ... + 2432902008176640000 (Wilkinson's)
> Sort[r[p, 2^-32]]
{1., 2., 3., 4., 5., 6., 7.00001, 7.99994, 9.00018, 10.0002, 11.0007, \
11.9809, 13.0043, 14.0227, 14.9878, 16.0158, 16.9959, 17.9992, \
19.0001, 20.}

```

As you can probably see, when the degree grows higher this method begins to bounce around the correct values, never really homing in completely. If I set the stopping condition of my code to be anything stricter than "from one iteration to next the guesses changed by no more than epsilon" then the algorithm never stops. I guess I should just use Durand-Kerner as input to Newton's method?

---
Tags: code-golf, math, polynomials
---


title: Shortest common superstring

text:
# Question
Title: Shortest common superstring
Given a list of strings `s_0, s_1, ..., s_n` find the shortest string `S` that contains each of `s_0, s_1, ..., s_n` as a substring.

*Examples*:

* `S('LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE')='SEDOLOREMAGNAD'`
* `S('ABCDE', 'BCD', 'C')='ABCDE'`

Write the shortest program (or function) that solves this problem. You can represent strings as arrays or lists of characters/integers if you want. Standard libraries are OK. For input/output you can use whatever is more convenient: STDIN/STDOUT, user prompt, parameter/return value of a function etc.

Performance is not critical - let's say, for an input of total length \< 100 characters the result must be computed in \< 10 second on average modern hardware.

# Answer
> 10 votes
# Python 2, 170 153/157/159

Shortened thanks to some of Baptiste's ideas.

```
from itertools import*
print min((reduce(lambda s,w:(w+s[max(i*(s[:i]==w[-i:])for i in range(99)):],s)[w in s],p)
for p in permutations(input())),key=len)

```

The second line break is not needed.

Input: `'LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE'`
Output: `SEDOLOREMAGNAD`

Even with long input strings, this runs in less than 2 seconds if there are at most 7 input strings (as is the case in the example given, which runs in 1.7 1.5 seconds on my machine). With 8 or more input strings, however, it takes more than 10 seconds, since the time complexity is `O(n!)`.

As Baptiste pointed out, `range(99)` needs to be replaced with `range(len(w))` if arbitrary input lengths should be supported (making the total length of the code 157 characters). If empty input strings should be supported, it has to be changed to `range(len(w)+1)`. I think `range(99)` works correctly for any total input length less than 200, though.

More tests:

```
>>> "AD", "DO", "DOLOR", "DOLORE", "LOREM", "MAGNA", "SED", "ORE",  "R"
SEDOLOREMAGNAD

>>> 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz', 'abcdefghijklmnopqrstuvw
... xyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstu
... vwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ZOOM', 'aZ', 'Za', 'ZA'
aZABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZOOM

```

# Answer
> 6 votes
# Mathematica 337 418 372

After trying unsuccessfully to implement using Mathematica's `LongestCommonSubsequencePositions`, I turned to pattern matching.

```
v=Length;
p[t_]:=Subsets[t,{2}];
f[w_]:=Module[{c,x,s=Flatten,r={{a___,Longest[y__]},{y__,b___}}:>{{a,y},{y,b},{y},{a,y,b}}},
c=p@w;
x=SortBy[Cases[s[{#/.r,(Reverse@#)/.r}&/@c,1],{_,_,_,_}],v[#[[3]]]&][[-1]];
Append[Complement[w,{x[[1]],x[[2]]}],x[[4]]]]

g[r_]:=With[{h=Complement[r,Cases[Join[p@r,p@Reverse@r],y_/;!StringFreeQ@@y:>y[[2]]]]},
FixedPoint[f,Characters/@h,v@h-1]<>""]

```

The pattern-matching rule,

```
r={{a___,Longest[y__]},{y__,b___}}:> {{a,y},{y,b},{y},{a,y,b}}},

```

takes an ordered pair of words (represented as lists of characters) and returns: (1) the words,`{a,y}` and `{y,b}` followed by (2) the common substring,`y`, that links the end of one word with the beginning of the other word, and, finally, the combined word `{a,y,b}` that will replace the input words. See Belisarius for a related example: https://mathematica.stackexchange.com/questions/6144/looking-for-longest-common-substring-solution

Three consecutive underscore characters signify that the element is a sequence of zero or more characters.

`Reverse` is employed later to ensure that both orders are tested. Those pairs that share linkable letters are returned unchanged and ignored.

**Edit**:

The following removes from the list words that are "buried" (i.e. fully contained) in another word, (in response to @flornquake's comment).

```
h=Complement[r,Cases[Join[p@r,p@Reverse@r],x_/;!StringFreeQ@@x:> x[[2]]]]

```

---

**Example**:

```
 {{"D", "O", "L", "O", "R", "E"}, {"L", "O", "R", "E", "M"}} /. r

```

returns

> {{"D", "O", "L", "O", "R", "E"}, {"L", "O", "R", "E", "M"}, {"L", "O", "R", "E"}, {"D", "O", "L", "O", "R", "E", "M"}}

---

**Usage**

```
g[{"LOREM", "ORE", "R"}]

AbsoluteTiming[g[{"AD", "DO", "DOLOR", "DOLORE", "LOREM", "MAGNA", "SED", "ORE",  "R"}]]

```

> "LOREM"
>
> {0.006256, "SEDOLOREMAGNAD"}

# Answer
> 2 votes
# Python 2, 203 187 200

```
from itertools import permutations as p
def n(c,s=''):
 for x in c:s+=x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if s.endswith(l)),0):]
 return s
print min(map(n,p(input())),key=len)

```

Input: `['LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE']`
Output: `SEDOLOREMAGNAD`

**Edit**

Using `reduce` and some dirty import trickery, I can reduce this further (and to one line only!):

```
print min((reduce(lambda a,x:a+x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if a.endswith(l)),0):],P,'')for P in __import__('itertools').permutations(input())),key=len)

```

**Edit 2**

As flornquake noted, this gives incorrect results when one word is contained in another. The fix for this adds another 13 chars:

```
print min((reduce(lambda a,x:a+(x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if a.endswith(l)),0):],'')[x in a],P,'')for P in __import__('itertools').permutations(input())),key=len)

```

Here's the cleaned up version:

```
from itertools import permutations

def solve(*strings):
    """
    Given a list of strings, return the shortest string that contains them all.
    """
    return min((simplify(p) for p in permutations(strings)), key=len)

def prefixes(s):
    """
    Return a list of all the prefixes of the given string (including itself),
    in ascending order (from shortest to longest).
    """
    return [s[:i+1] for i in range(len(s))]
    return [(i,s[:i+1]) for i in range(len(s))][::-1]

def simplify(strings):
    """
    Given a list of strings, concatenate them wile removing overlaps between
    successive elements.
    """
    ret = ''
    for s in strings:
        if s in ret:
            break
        for i, prefix in reversed(list(enumerate(prefixes(s)))):
            if ret.endswith(prefix):
                ret += s[i+1:]
                break
        else:
            ret += s
    return ret

print solve('LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE')

```

It's possible to shave off a few characters at the cost of theoretical correctness by using `range(99)` instead of `range(len(x))` (credits to flornquake for thinking of this one).

# Answer
> 1 votes
## Python, 144 chars

```
S=lambda A,s:min(S(A-set([a]),s+a[i:])for a in A for i in range(len(a)+1)if i==0 or s[-i:]==a[:i])if A else(len(s),s)
T=lambda L:S(set(L),'')[1]

```

`S` takes a set of words `A` that still need placing and a string `s` containing words placed so far. We pick a remaining word `a` from `A` and overlap it from `0` to `len(a)` characters with the end of `s`.

Takes only about 0.15 seconds on the given example.

# Answer
> 1 votes
# Haskell, 121

```
import Data.List
a p []=[(length p,p)]
a p s=[r|w<-s,t<-tails w,isInfixOf w$p++t,r<-a(p++t)(s\\[w])]
s=snd.minimum.a ""

```

Minus two if the function doesn't need to be bound to a name

---
Tags: code-golf, string, restricted-time
---


title: Generate Pascal's Pyramid

text:
# Question
Title: Generate Pascal's Pyramid
Pascal's Pyramid is an extension of Pascal's Triangle to the third dimension. Starting with a 1 as the apex, the elements of each successive layer can be determined by summing the three numbers that are above it. The nth layer contains the coefficients of `(a + b + c)^(n-1)`.

You are to create a program that, given an input n, outputs the first n layers of Pascal's Pyramid. There must be two newlines between the different layers, and they must be in order. Within each layer, each row must be on a separate line, with the elements separated by spaces. Apart from that, you may format the pyramid however you like.

Your code should be reasonably fast generating a pyramid with 10 layers.

For example, your program, when given 4 as input, should output something like this:

```
1

1
1 1

1
2 2
1 2 1

1
3 3
3 6 3
1 3 3 1

```

May the shortest code win!

# Answer
## Python, 110

```
l=1
exec"print;n=1;r=0;exec\"c=0;exec'print n,;n*=r-c;c+=1;n/=c;'*r;print n;r+=1;n=n*l/r-n;\"*l;l+=1;"*input()

```

Original, ungolfed solution:

```
for layer in range(1, input() + 1):
    print
    n = 1
    for row in range(1, layer + 1):
        for col in range(1, row):
            print n,
            n *= row - col
            n /= col
        print n
        n *= layer - row
        n /= row

```
> 2 votes

# Answer
## Python (~~134~~ 128)

Factorials are probably more space-efficient, but I wanted to be fancy.

```
for n in range(1,input()+1):
 a=r=1.
 while a:
  b=a;j=1.;a*=(n-r)/r
  while b:print int(b),;b*=(r-j)/j;j+=1
  print;r+=1
 print

```

Uses the ratio property of Pascal's Triangle.
e.x. `1 4 6 4 1`, `1:4, 4:6, 6:4, 4:1` = `1:4, 2:3, 3:2, 4:1`

```
for n in range(1,input()+1): #Generate layers
 a=r=1.               #a is the first value of a row in a layer; r represents the row
 while a:          #when a is 0, there are no more rows in the pyramid.
  b=a;i=1.;a*=(n-r)/r #b will calculate the values of that row
                      #use ratio property to determine next value of a
                      #i is a counter representing the ith item in row r
  while b:print int(b),;b*=(r-i)/i;i+=1 #Output values using ratio property
  print;r+=1          #increment row; loop
 print

```
> 1 votes

# Answer
## Mathematica (112)

```
For[j = 0, j < 11, j++, For[i = 0, i <= j, i++, Print[Row[Array[Binomial[i, # - 1] &, i + 1], " "]]]; Print[""]]

```

Older method(166):

```
b = "stdout"; For[k = 0, k < 11, k++, For[i = 0, i <= k, i++, For[j = 0, j <= i, j++, WriteString[b, Binomial[i, j], " "]]; WriteString[b, "\n"]]; WriteString[b, "\n"]]

```

The following prints it in a different format, but is only 94 characters:

```
For[i = 0, i < 11, i++, Print[Column[Table[Binomial[n, k], {n, 0, i}, {k, 0, n}]]]; Print[""]]

```
> 1 votes

# Answer
## Mathematica ~~65~~ 64

```
c=Column;c[c@Table[n~Binomial~k,{n,0,p},{k,0,n}]~Table~{p,0,#}]&

```

Usage

```
c=Column;c[c@Table[n~Binomial~k,{n,0,p},{k,0,n}]~Table~{p,0,#}]&@5

```
> 1 votes

# Answer
**k 31**

```
q)k)f:{,/{x**|x}{x{0+':x,0}\1}@'!x}
q)f 4
1
1
1 1
1
2 2
1 2 1
1
3 3
3 6 3
1 3 3 1

```
> 1 votes

# Answer
```
q)k)f:{,/{p**|p:x{0+':x,0}\1}'!x}

q)f 4

1
1
1 1
1
2 2
1 2 1
1
3 3
3 6 3
1 3 3 1

```
> 0 votes

---
Tags: code-golf, math
---


title: Print element from the periodic table

text:
# Question
Title: Print element from the periodic table
Your task is simple: given a number as an input, you have to print the English name of the chemical element with that atomic number, up to and including ununoctium. For example, for an input of 77, your program has to print `Iridium`, and nothing else.

You can use any language, but no library (or other, in-built feature) which includes the names of the elements is allowed, your program has to store or generate the names on its own. Use names in wikipedia for the spelling of the names of the elements.

Shortest code wins, not sooner than 1 days after first valid answer.

# Answer
## Tcl, 567 ~~577~~

```
puts [lindex [zlib i =SÑä\ ü(EH¡Îmöêþý2û0%C¤éÆæï¿Tï¢r\"§ÔVOÔfÝçzgQáA\;¸Í¸.ß÷>^´Dcb´¯CÊ®èp2ÞxG£QËvåª2ì§k¤±èµ4åJzî\v2axqÊ^w¶\töÏäªÒ£%`M15g+Ð4¶ù\vÉþ\]júiÓ\t¡êDí:Ð.¦86¦ñùÒû¦ëhÞmv\;ºçÔ\}þ45Q\;â&º¼éb®~_×¬®5ftÐ`y»\fÅ´VN`ÍºðmHDË6«6jßÈþ&1åüÙý\n»sFO\\\n¥ÜË¿Ñeú0^y@Z\\*ÏP<ÙDuIåVâªC<_f\]ôãÉÐ¡¸Â+@ÔvAÏ1Í2úLBFèÕîE`7¡:j^jÊëó^PÒÑF·IG(¦cî*Lj´Í\nìÑ-äùH1Ç=Òçoriñ2rÁaÍØ4Ê1xÛ¯Ø³e\{ú5llîer\ ³ÒÛ¡åxÖ\nþ(>Ü¶ÔbYGì-Ú\vW5F\{Ð±M- Ý\$0\ Ï3iG£ä\r/\{¾UÞÜa^jæ·Ùùaú?±äþ] [gets stdin]]

```

Who said that you can not embed binary data in your program code?
(`zlib` requires Tcl 8.6)

base64 encoded version:

```
cHV0cyBbbGluZGV4IFt6bGliIGkgPVPRkuRcIAj8FX+NKBOtRUihzm326v79EDL7MCVDpOnG5u+/VO+i
clwip4rUVk/UZt3ngXqTZw5R4ZRBD1w7uM24Lt/3Pl60RBtjYrSvQ8qu6HAyjh0Brd54R6NRy3blqjLs
p2uksei1NOVKAQF67lx2MmF4cQbKXpqBHXe2XHQO9gYGz+Sq0qMln2BNMTVnKwfQNLb5XHbJ/lxdF2r6
aZzTXHSh6kTtAQY60C6mgYSeODam8fnS+5oGputo3m2Ydp5cO7rn1Fx9/jQ1UVw74iaHExG6j4K86WKu
jH5f16wBrjVmdBmP0GCTeRu7XGbFlbSPVk5gzbrwbUhEyxs2qzZq38j+JjHlA/wb2f1cbrtzRk9cXFxu
A6Xcjsu/0WX6MF55QI9aXFwql88FilA82UR1SeUeVuKdqpBDPF9mXF30jOPJ0JqhuMIrQIzUdkGai88x
zTL6TEJG6NUY7kVgmjcDoZI6al5qyuvzXoRQ0tFGt0maRyimDmPuKkxqtM2NXG7sltEYLeT5SDHHPdLn
b3JpGIDxMnLBYc0H2Ag0h8oxeNuHr9gQs2Vce4n6NWxsmgLuZY5yB1wgF7PS26HleNZcbv4oPty2F9QQ
nGJZR+wHgi3aGVx2VzVGGFx70LFNjhctoN1cJJcwlVwgzzOGaRZHo+RcchYvDlx7vghV3p/chWFeaua3
HgPZ+WH6P7HkHf4HXSBbZ2V0cyBzdGRpbl1d

```

**History**:

* changed compression mechanism. Saves me 10 chars.
> 3 votes

# Answer
## Python, 69 + 536 = 605 (lazy solution)

I took the liberty of not capitalizing the names of the elements. That allows me to shave off extra 41 bytes. zlib is most likely not the best compressor for plaintext, it takes 1292 bytes down to 536.

**python file:**

```
import zlib
print (eval(zlib.decompress(open('a').read())))[input()]

```

**data file `a` (b64 encoded for web):**

```
eJxNVNGS5CAI/Jd5vj+62gdUJlpDMIU6t9mvPzSQ2YetZVCbpmny9/H488hnkrohzxCpjF0DKj1f
UUA5ybKhSp3XIkhYAZfuT+v3eQVPGlUK4zzGdavVdL3fYWNsVww09sJX3AqVuK4euTb9k9FmetBz
yKyXySFBtuti7dAMKgJFA4rAVquXDgb/BgbLxix1dzK8gdKZqMX6qgGor77iC2lljgMnhZ/CUf9t
4FpsKLsXAGmoTyYBJLRkmJUW55ecR18FZIRiTJoqx/2Kz97lin6KqBBXzKUGo1rpDAn5agxjZrSX
Mnr2gpJd50NZeseq7Xt1ECFZ5+Wj0SQFSmOvfC5somFUiqIt+t/INnWfXQC7Q/o2w8UroiUPgYY1
nVaNf8WHaoLurAa74+CQepiukCq5MTqKSZDOpo+tfq5kgPd5z4NuMe8sje5KZXg6qJKe7pvh4K31
ZVu5dazNdRIf1kGgWl38KqU5EpQ4ZGmWb08QwjwLpe06l+VS8mlC6xNjCira4toUATbjio8LYr+b
1z24Zeu/Doa48RgPbcE5jn4XU3rFoKMPVDf55futK1OeVew6FlYVHP6pzjbfISc19NuK1XB/HuCf
4M19elAUzVpII/heI+gnY/OPRxYfhW/ujqWz+yaB7CpScmtX5L75UHQRUelaycGDfWWehFLfn/yB
vlZU1Pm7izjPmur1+VXj+vH1H5EjvoY=

```
> 3 votes

# Answer
### GolfScript, 577 characters

```
~(
'ž�®Ñ/ž!Z!Ó1ã„9î¸dÊÓªí[o@ÁlD®�K®ÆšTB˜Þ6(ËH¼¡)ßÝ•|O¨U˜É/Œ�DÚvU$.âxŠ²¤Æ³n’t8[¢êqHyÍlÂSbYÈ*1~˜|†ï¨ŸÊ*Þk0âg%&‘Ÿ¶2ö¼Eë˜Áaq[¦Ä;ø7[–Î¯_ªtë½¢Ÿ\‰`Ãö”{ÉOUÈÜ¿Ò‰Fös–ß<µ‰x�#¶w+ìÊ®¼äH$Ìª¦ùoh�7™ÐbÙÑîâóÂø8Ö;•9ÁÃ)T°¤vWOUð~È¡jžK¯V¹8K?«à‚ª–0)ÚFj]îõc„ ¼´¢�Ã#æ¯Uƒ¡Mh$Šº^9V$Ùš`½†2±Žžk™+®5ª.„bC x%XJ<ç†78N¥5á2ù@<ù��ž£ªØ¸ÅÆŒç™ Î½¨ñøŽjZ±@,, íªluzÀ¡‹ØÈ[$5† S¾,‰‚TÊ_"ñÍÈ�Â» Úïº @ð_D«�.kX©(0ÎX]®c´c.Åm,‰æªQ)•‚t®§>‰j)tŸ.Z!�|0Å‡Ì¢‰ùc êš™‡ãÂÓT<xsY(ª2!¦93ãœ¤¡�Ç"mÎç£COKcÎ}¶!0Ö·£—sÂÃžíÛê”[lœX£€Ã6{È‚¡�ˆFâóVP8‡4�ës†´ïç]Ó{±éˆñz~bºs8¿U/ªY²Öm4 ÍP3CI7‹'
{32-}%218base 32base{96+}%''+'j'/'ium`'*'`'/=([32-]\+

```

Base64 encoded version:

```
fignnp2u0S+eIVoh0zHjhDnuuGTK06rtW29AwWxEroFLrsaaVEKY3jYoy0i8oSnf3ZV8T6hVmMkv
jIFE2nZVJC7ieIqypMazbpJ0OFui6nFIec1swlNiWcgqMX6YfIat76ifyireazDiZyUmkZ+2Mva8
ReuYwWFxW3+mxDv4N1uWzq9fqnTrvaKfXIlgw/aUe8lPVcjcv9KJRvZzlt88tYl4nSO2dyvsyq68
5EgkzKqm+W9okDeZ0GLZ0e7i88L4ONY7lTnBwylUsKR2V09V8H7IoWqeS69WuThLP6vggqqWMCna
Rmpd7vVjhKC8tKKdwyPmr1WDoU1oJIq6XjlWJNmaYL2GMrGOnmuZK641qi6EYkMgeCVYSjznhjc4
TqV/NeEy+UA8+YGNnqOq2LjFxoznmSDOvajx+I5qWrFALCwg7apsdXrAoYvYyFskNYYgU74siYJU
yl8i8c3IncK7oNrvuqBA8F9Eq50ua1ipKDDOWF2uY7RjLsVtLInmqlEplYJ0rqc+iWopdJ8uWiGQ
fDDFh8yiifljIOqamYfjwtNUPHhzWSiqMiGmOTPjnKShkMcibc7no0NPS2POfbYhMNa3o5dzrcLD
nu3b6pRbbJxYo4DDNnvIgqGdiEbi81ZQOIc0getzhrTv513Te7HpiPF6fmK6czi/VS+qf1my1m00
IM1QM0NJN4snezMyLX0lMjE4YmFzZSAzMmJhc2V7OTYrfSUnJysnaicvJ2l1bWAnKidgJy89KFsz
Mi1dXCsNCg==

```

It also does the capitalization correct. No libraries, no zlib, just base encoding. With a little bit tweaking it might be possible to shave off a few chars.
> 3 votes

---
Tags: code-golf, kolmogorov-complexity
---


# Question
Title: Floating points: Make Gaussian elimination go wrong
You know that some decimal numbers can't be expressed as IEEE 754 floating points. You also know that arithmetic with floating points can give results that seem to be wrong:

* `System.out.print(4.0-3.1);` (source)
* `0.2 + 0.04 = 0.24000000000000002` (source)

While one wrong number with an error that is this small might not be significant, more of those error might be.

## Task

Find a system of linear equations in form of a matrix A \in R^{n \times n} and b \in R^n, such that the result vector is as wrong as possible. Reference is the script below, executed with Python 2.7.

## Points

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

def pprint(A):
    n = len(A)
    for i in range(0, n):
        line = ""
        for j in range(0, n+1):
            line += str(A[i][j]) + "\t"
            if j == n-1:
                line +=  "| "
        print(line)
    print("")

def gauss(A):
    n = len(A)

    for i in range(0,n):
        # Search for maximum in this column
        maxEl = abs(A[i][i])
        maxRow = i
        for k in range(i+1,n):
            if abs(A[k][i]) > maxEl:
                maxEl = A[k][i]
                maxRow = k

        # Swap maximum row with current row (column by column)
        for k in range(i,n+1):
            tmp = A[maxRow][k]
            A[maxRow][k] = A[i][k]
            A[i][k] = tmp

        # Make all rows below this one 0 in current column
        for k in range(i+1,n):
            c = -A[k][i]/A[i][i]
            for j in range(i,n+1):
                if i==j:
                    A[k][j] = 0
                else:
                    A[k][j] += c * A[i][j]

    # Solve equation Ax=b for an upper triangular matrix A
    x=[0 for i in range(n)]
    for i in range(n-1,-1,-1):
        x[i] = A[i][n]/A[i][i]
        for k in range(i-1,-1,-1):
            A[k][n] -= A[k][i] * x[i]
    return x;

if __name__ == "__main__":
    from fractions import Fraction
    datatype = float # Fraction
    n = input()

    A = [[0 for j in range(n+1)] for i in range(n)]

    # Read input data
    for i in range(0,n):
        line = map(datatype, raw_input().split(" "))
        for j, el in enumerate(line):
            A[i][j] = el
    raw_input()

    line = raw_input().split(" ")
    lastLine = map(datatype, line)
    for i in range(0,n):
        A[i][n] = lastLine[i]

    # Print input
    pprint(A)

    # Calculate solution
    x = gauss(A)

    # Print result
    line = "Result:\t"
    for i in range(0,n):
       line += str(x[i]) + "\t"
    print(line)

```

Let `x` be the correct answer and `x'` the answer that the script above gives.

Your points are `(||x-x'||^2)/n`, where `|| . ||` is the euclidean distance.

Your solution gets 0 points if it gives `nan` as result.

## Example

bad.in:

```
2
1 4
2 3.1

1 1

```

The first line is `n`, the next n lines describe the matrix A and the last line describes b.

```
$ python gauss.py < bad.in
1.0 4.0 | 1.0
2.0 3.1 | 1.0

Result: 0.183673469388  0.204081632653

```

The answer should be:

```
Result: 9/49    10/49

```

So the score would be:

```
((0.183673469388-9/49)^2+(0.204081632653-10/49)^2)/2
= 3.186172428154... × 10^-26

```

The last step was calculated with Wolfram|Alpha.

# Answer
Ok, this feels kind of cheating.

# Tcl, score 1234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234569876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876544

```
gets stdin a
puts $a
for {set i 0} {$i<$a} {incr i} {
    set r {}
    for {set j 0} {$j<$a} {incr j} {
        lappend r [expr {$i==$j?1:0}]
    }
    puts $r
}
puts ""
puts [join [lrepeat $a [string repeat 8 308]]]

```
> 3 votes

# Answer
Taking this as a question about numerical inaccuracy in calculations rather than in conversion from numbers which can't be exactly represented in 64 bits to 64-bit representations, we're interested in nearly singular matrices.

Let's take the simplest possible case:

```
[a b] [x] = [p]
[c d] [y]   [q]

```

has solution

```
[x] = [(dp - bq) / (ad - bc)]
[y]   [(aq - cp) / (ad - bc)]

```

so that if `ad - bc` is very small we find that errors in `dp - bq` and `aq - cp` are magnified.

We also find that scaling `p` and `q` scales the absolute error linearly, which points out a massive flaw in the scoring system of this question.

How can we get a nearly singular matrix? In order of ill-conditionedness:

1. `a=1+e, b=c=d=1` gives `ad - bc = e`. This allows us to get a determinant of 1 ulp (which for IEEE 64-bit is on the order of 10^-16).
2. `a=1+e, d=1-e, b=c=1` gives `ad - bc = -e^2`. This allows us to get a determinant on the order of 10^-32.

```
2
1.000000000000001 1
1 0.999999999999999

1 1

```

gives output:

```
1.0 1.0 | 1.0
1.0 1.0 | 1.0

Result: -9.0    10.0

```

rather than `x = 100000000000000, y = -100000000000000`

Similarly,

```
2
1.000000000000001 1
1 0.999999999999999

1E307 1E307

```

gives

```
1.0 1.0 | 1e+307
1.0 1.0 | 1e+307

Result: -9.1120238836e+307  1.01120238836e+308

```

rather than `x = 1E321, y = -1E321`. This seems to roundly beat Johannes' solution (it gives a score on the order of 10^642 vs 10^588), and moreover it would continue to generate about the same score even if the input numbers were tweaked to be exactly representable in IEEE 64-bit, whereas his would then score 0.
3. `a=d=e, bc=0` gives `ad - bc = e^2` but this time we can choose `e` to be a very small number rather than 1 ULP. In principle this allows us to get a determinant on the order of 10^-600 (i.e. underflowing IEEE 64-bit). However, so far I haven't managed to get a decent score without an infinity in the answer, and I gather from your chat with Johannes that even though the question doesn't rule out infinite scores, in practice you do.
> 7 votes

---
Tags: code-challenge, arithmetic
---


title: Save money with price rounding

text:
# Question
Title: Save money with price rounding
In Canada, the penny is no longer circulated. Cash payments are rounded to the nearest 5 cents.

Money can be saved by splitting purchases. For example, two $1.02 items cost $2.04 which rounds up to $2.05, but when buying the items in separate purchases, each price rounds to $1.00 for a total of $2.00. However, when buying two items at $1.03 each, it is better to buy them in a single purchase.

Another way to save money is using a credit card when rounding is unfavourable, because credit payments are not rounded. If we want two $1.04 items, the total price will round up to $2.10 regardless of how we split the purchases. Therefore, we should pay for these items with a credit card.

Write a function or program which accepts a list of prices of items as integers in cents and outputs the lowest possible total price (in cents) for those items which can be achieved through a sequence of purchases, each either by cash or by credit.

Shortest code wins.

## Test cases

```
[] : 0
[48] : 48
[92, 20] : 110
[47, 56, 45] : 145
[55, 6, 98, 69] : 225
[6, 39, 85, 84, 7] : 218
[95, 14, 28, 49, 41, 39] : 263
[92, 6, 28, 30, 39, 93, 53] : 335
[83, 33, 62, 12, 34, 29, 18, 12] : 273
[23, 46, 54, 69, 64, 73, 58, 92, 26] : 495
[19, 56, 84, 23, 20, 53, 96, 92, 91, 58] : 583
[3, 3, 19, 56, 3, 84, 3, 23, 20, 53, 96, 92, 91, 58, 3, 3] : 598
[2, 3, 4, 4, 4, 4, 4] : 19

```

# Answer
> 5 votes
### Ruby, 119 105 characters (93 body)

```
def f s
a,b,c,d=(1..4).map{|i|s.count{|x|x%5==i}}
s.reduce(0,:+)-a-(c-m=c>d ?d:c)/2-2*(b+m+(d-m)/3)
end

```

Two characters may be saved if the algorithm is allowed to crash when fed an empty shopping list.

# Answer
> 5 votes
## GolfScript (54 chars)

```
~]4,{){\5%=}+1$\,,}%~.2$>$:m- 3/m+@+2*@@m- 2/++~)+{+}*

```

This is a program which takes input from stdin as space-separated values. One character could be saved by forcing the input format to instead be as GolfScript arrays.

Test cases online

The most interesting trick is `.2$>$` for a non-destructive `min` operator.

---

My analysis of the maths is essentially the same as Jan's and Ray's: considering values mod 5, the only saving is on transactions worth 1 or 2. The credit card option means that we never round up. So an item which costs 5n+2 cents can't benefit from bundling; nor can an item worth 5n+1 cents (because combining two 1-cent savings into a 2-cent saving doesn't give any benefit). 0 is the additive identity, so the only interesting cases involve values of 3 and 4. `3+3 = 1` and `3+4 = 4+4+4 = 2`; if we have mixed 3s and 4s then we optimise by preferring `3+4` over `3+3` (strictly better) or `4+4+4` (equivalent).

# Answer
> 3 votes
**C++: 126 character**

```
int P(int*m,int i){int t=0,h=0,d;while(i>-1){d=m[i]%5;t+=m[i--];d<3?t-=d:d==4?h++,t-=2:h--;}h<0?t+=h/2:t+=(h-h/3)*2;return t;}

```

Welcome to give guidance to put this program becomes shorter.Here is the test program,compile with tdm-gcc 4.7.1 compiler and run normally.

```
#include<iostream>
using namespace std;

//m[i]表示单个商品的价格,t表示所有商品总价格,
//d为单个商品价格取模后的值,h为单个商品价格取模后值为3的个数,
//f为单个商品价格取模后值为4的个数
int P(int*m,int i){int t=0,h=0,d;while(i>-1){d=m[i]%5;t+=m[i--];d<3?t-=d:d==4?h++,t-=2:h--;}h<0?t+=h/2:t+=(h-h/3)*2;return t;}

int main() {
int p1[1]={48};
int p2[2]={92,20};
int p3[3]={47,56,45};
int p4[4]={55,6,98,69};
int p5[5]={6,39,85,84,7};
int p6[6]={95,14,28,49,41,39};
int p7[7]={92,6,28,30,39,93,53};
int p8[8]={83,33,62,12,34,29,18,12};
int p9[9]={23,46,54,69,64,73,58,92,26};
int p10[10]={19,56,84,23,20,53,96,92,91,58};
int p11[10]={1,2,3,4,5,6,7,8,9,10};
cout<<P(p1,0)<<endl
    <<P(p2,1)<<endl
    <<P(p3,2)<<endl
    <<P(p4,3)<<endl
    <<P(p5,4)<<endl
    <<P(p6,5)<<endl
    <<P(p7,6)<<endl
    <<P(p8,7)<<endl
    <<P(p9,8)<<endl
    <<P(p10,9)<<endl
    <<P(p11,9)<<endl;

return 0;
}

```

# Answer
> 1 votes
## Python 3 (115 chars)

```
m=eval(input());t=a=b=0
for v in m:d=v%5;t+=v-d*(d<3);a+=d==3;b+=d==4
d=min(a,b);a-=d;b-=d;print(t-d*2-a//2-b//3*2)

```

## Python 2 (106 chars)

```
m=input();t=a=b=0
for v in m:d=v%5;t+=v-d*(d<3);a+=d==3;b+=d==4
d=min(a,b);a-=d;b-=d;print t-d*2-a/2-b/3*2

```

# Answer
> 1 votes
## R 143

```
function(x)min(sapply(rapply(partitions::listParts(length(x)),
                             function(i)min(sum(x[i]),5*round(sum(x[i])/5)),h="l"),
                      function(x)sum(unlist(x))))

```

Tests (where `P` is an alias for the code above)

```
> P(c(48))
[1] 48
> P(c(92, 20))
[1] 110
> P(c(47, 56, 45))
[1] 145
> P(c(55, 6, 98, 69))
[1] 225
> P(c(6, 39, 85, 84, 7))
[1] 218
> P(c(95, 14, 28, 49, 41, 39))
[1] 263
> P(c(92, 6, 28, 30, 39, 93, 53))
[1] 335
> P(c(83, 33, 62, 12, 34, 29, 18, 12))
[1] 273
> P(c(23, 46, 54, 69, 64, 73, 58, 92, 26))
[1] 495
> P(c(19, 56, 84, 23, 20, 53, 96, 92, 91, 58))
[1] 583

```

# Answer
> 1 votes
# Mathematica 112 126 167 157

**Edit**: Cases of {3, 3} and {4,4,4} now handled thanks to Peter Taylor and cardboard\_box.

```
n_~g~o_ := {a___, Sequence @@ n, b___} :> {a, b, o};
f@s_ := Tr@Join[#[[2]], Sort@#[[1]] //. {1 -> 0, 2 -> 0, g[{3, 4}, 5], g[{3, 3}, 5],
   g[{4, 4, 4}, 10]}] &[Transpose[{m = Mod[#, 5], # - m} & /@ s]]

```

Note: Non-purchases (test case #1) are entered as `f[{0}]`.

**How it works**

1. For each item, the greatest multiple of 5 less than the respective price will be paid regardless of form of payment. (No getting around that.)
2. The remainders of `Mod[n, 5]` are then processed: 1's and 2's become 0's. Zeros stay unchanged.
3. Each pair {3, 4} -\> {5}; afterwards each pair {3, 3} -\> {5}; then the triple, {4,4,4}-\> {10}, if applicable.
4. The remaining 4's, if any, remain unchanged (paid by credit card).
5. Original multiples of 5 summed with remainders that were tweaked (or not) in steps (2) to (4).

**Testing**

`a12` adjusts for {3,3} `a13` adjusts for {4,4,4}

```
a1={0};
a2={48};
a3={92,20};
a4={47,56,45};
a5={55,6,98,69} ;
a6={6,39,85,84,7};
a7={95,14,28,49,41,39};
a8={92,6,28,30,39,93,53};
a9={83,33,62,12,34,29,18,12};
a10={23,46,54,69,64,73,58,92,26};
a11={19,56,84,23,20,53,96,92,91,58};
a12={3,3,19,56,3,84,3,23,20,53,96,92,91,58,3,3};
a13={2,3,4,4,4,4,4};

f /@ {a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13}

```

> {0, 48, 110, 145, 225, 218, 263, 335, 273, 495, 583, 598, 19}

# Answer
> 0 votes
## APL, 58 characters

```
{a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}

```

The program is essentially a direct translation of Jan Dvorak's Ruby solution.

---

```
      {a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}⍬
0
      {a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}95 14 28 49 41 39
263
      {a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}19 56 84 23 20 53 96 92 91 58
583

```

is the empty vector.

# Answer
> 0 votes
# Julia 83C

```
C=L->let
w,z,x,y=map(i->[i==x%5for x=L]|sum,1:4)
L|sum-(x+2w+3min(x,y)+4z)>>1
end

```

## Explaination:

In one purchase, you can save 2 cent at most. ~~So if you have a combination that can save you 2 cents, just buy it that way and it will be optimial~~. For example, if you have `x` items with price 3(mod 5) and `y` items with price 4(mod 5), you can make `min(x, y)` number of (3, 4) pairs, which save you `2 min(x, y)` cents. Then you use the rest 3's, if any, to save you `max(0, x-min(x,y)) / 2` cents. This can also be calculated by `(max(x,y)-y)/2`

```
w = sum(1 for p in prices if p % 5 == 1)
z = sum(1 for p in prices if p % 5 == 2)
x = sum(1 for p in prices if p % 5 == 3)
y = sum(1 for p in prices if p % 5 == 4)

ans = sum(prices) - (w + 2 z + 2 min(x, y) + div(max(x, y) - y, 2))
    = sum(prices) - (2w + 4z + 4 min(x, y) + x + y - min(x, y) - y) `div` 2
    = sum(prices) - (2w + 4z + 3 min(x, y) + x) `div` 2

```

## Edit

This solution is wrong.

---
Tags: code-golf, number
---


# Question
Title: Write 'hello world' to standard output without using certain common words - C# only
The challenge is to write the string `hello world` to your processes standard output, using as few characters of code as possible.

The following restrictions apply:

* The following words may not appear anywhere in the code in any casing (this includes as part of another word)

1. Console
    2. Debug
    3. Write
    4. Print
    5. Line
    6. Put
* Your code must compile as C# 4/4.5
* No external libraries are permitted.
* Your process may not spawn any new processes.

A working (but not necessarily the shortest) solution will be provided after a number of answers have been provided.

The winner is the author of the shortest code by character count that satisfies the above criteria.

# Answer
# 75 chars

New answer, new approach.

```
class M{static void Main(){System.\u0043onsole.\u0057rite("hello world");}}

```

It looks like you can hide every character with a `\uXXXX` sequence. Which makes this thing...
Easy.
> 3 votes

# Answer
Ok, I try my luck:

## 118 chars

```
class M{static void Main(){System.Type.GetType("System.\x43onsole").GetMethods()[78].Invoke(0,new[]{"hello world"});}}

```

Based on this solution.

Idone

As noted in the original answer, the index of the Write method might be different on your system.
> 0 votes

# Answer
Here's my current best that runs anywhere:

## 158 Characters

```
using System;class M{static void Main(){Type.GetType("System.\x43onsole").GetMethod("\x57rite\x4cine",new[]{typeof(string)}).Invoke(0,new[]{"hello world"});}}

```

`.Invoke` ignores the first param entirely if its a static method, so you can use `0` instead of `null` to save 3 characters.

Additionally, a variation that bans the use of the `\` character:

## 234 Characters

```
using System;using System.Linq;class M{static void Main(){Func<string,string>f=(i)=>new string(i.Reverse().ToArray());Type.GetType(f("elosnoC.metsyS")).GetMethod(f("eniLetirW"),new[]{typeof(string)}).Invoke(0,new[]{"hello world"});}}

```
> 0 votes

# Answer
# 183 chars

Without reflection "cheats"! (but using the deprecated overload of FileStream to avoid using SafeFilePointer)

```
using System;using System.IO;public class M{static void Main(){new MemoryStream(Convert.FromBase64String("SGVsbG8gV29ybGQ=")).CopyTo(new FileStream(new IntPtr(-11),(FileAccess)2));}}

```
> 0 votes

---
Tags: code-golf, c#
---