title: Is case sensitivity important?

text:
# Question
Title: Is case sensitivity important?
Tom is going to implement a new programming language of his invention. But before actually starting working on it, he wants to know whether his language should be case sensitive or not.

On one hand, case insensitivity seems more easy to implement to him, but he worries that it could cause a lack in the possibilities of combinations of characters that form a variable, meaning that longer variable names should then be used to avoid naming clashes (for an example, you can use `Hello`, `HEllo`, `heLLo` and a bunch of other possibilities if the language is case sensitive, but only `HELLO` if not).

But Tom is a meticulous person, so just a worry isn't enough for him. He wants to know the numbers.

# The challenge

Write a function (or a full program if your language doesn't support them) that, given an integer `n` as the input, outputs (or returns) the difference in the number of permutations possible for a string of length `n` with case sensitivity and without.

In Tom's language, variable names can include all alphabet letters, underscores and, starting from the second character, digits.

# Testcases

```
Input (length of the variable) -> Output (difference between the possibilities with case sensitivity and the possibilities with case insensitivity)
0 -> 0
1 -> 26
2 -> 2340
5 -> 784304586
8 -> 206202813193260
9 -> 13057419408922746

```

# Non-competing C++ reference implementation

```
void diff(int n) {
    long long total[2] = {0, 0}; //array holding the result for case insensivity ([0]) and case sensitivity ([1])

    for (int c = 1; c <= 2; c ++) //1 = insensitivity, 2 = sensitivity
        for (int l = 1; l <= n; l ++) //each character of the name
            if (l == 1)
                total[c - 1] = 26 * c + 1; //first character can't be a number
            else
                total[c - 1] *= 26 * c + 1 + 10; //starting from the second character, characters can include numbers

    std::cout << total[1] - total[0] << std::endl;
}

```

# Scoring

Tom likes golf, so the shortest program in bytes wins.

# Note

It's okay if maybe the last two testcases aren't right because of numerical precision. After all, I am not even sure *my* code handled number 9 correctly.

# Answer
# Jelly, ~~16~~ 15 bytes

```
“~J“6j”OH*"’ÆḊḞ

```

Try it online! or verify all test cases.

### How it works

```
“~J“6j”OH*"’ÆḊḞ  Main link. Argument: n

“~J“6j”          Yield ['~J', '6j'].
       O         Ordinal; replace the characters with it code points.
                 This yields [[126, 74], [54, 106]].
        H        Halve, yielding [[63, 37], [27, 53]].
           ’     Yield n-1.
         *"      Exponentiation (zipwith); elevate 63 and 37 to the power n-1.
            ÆḊ   Take the determinant of the matrix
                 [[63 ** (n-1), 37 ** (n-1)], [27, 53]], thus yielding
                 63 ** (n-1) * 53 - 37 ** (n-1) * 27.
              Ḟ  Floor; round the result down to the nearest integer.
                 This is required for n = 0.

```
> 5 votes

# Answer
## JavaScript (ES7), 43 bytes

```
f=(n,a=53,b=27)=>n?--n?f(n,a*63,b*37):a-b:0
```

```
<input type=number value=0 min=0 max=9 style=width:4ch oninput=o.textContent=f(+this.value)><div id=o>0</div>
```

Not `reduce`s day today - 55 bytes.
> 11 votes

# Answer
# TSQL, 41 bytes

```
DECLARE @ INT=10

PRINT 53*POWER(63.,@-1)-27*POWER(37.,@-1)

```

**Fiddle**
> 8 votes

# Answer
# Java, ~~77~~ 76 Bytes

~~O(1) solution, no loop involved~~

```
long x(long n){return 53*(long)Math.pow(63,n-1)-27*(long)Math.pow(37,n-1);}

```
> 5 votes

# Answer
# JavaScript (ES6) 47

```
n=>n&&eval("for(a=53,b=27;--n;a*=63)b*=37;a-b")

```

Note: the values are correct up to the 53 bits of precision of javascript numbers.

**Test**

```
F=n=>n&&eval("for(a=53,b=27;--n;a*=63)b*=37;a-b")

for(i=0;i<=10;i++)O.textContent+=i+' '+F(i)+'\n'
```

```
<pre id=O></pre>
```
> 4 votes

# Answer
# MATL, ~~17~~ 16 bytes

```
37iqY"27vt26+hpd

```

**Try it online!**

Last test case (input 9) is not exact due to numerical precision.

### Explanation

```
37      % Push number 37
iq      % Input number n and subtract 1
Y"      % Row array [37 ...37] of size n-1
27v     % Concatenate 27 vertically. Gives column array [37; ... 37; 27]
t26+    % Duplicate and add 26. Gives column array [63; ... 63; 53]
h       % Concatenate horizontallty. Gives 2D array [37 63; ... 37 63; 27 53]
p       % Product of each column
d       % Difference of the two values. Implicitly display

```
> 3 votes

# Answer
# Python 3, 36 bytes

```
lambda n:n and 53*63**~-n-27*37**~-n

```

An anonymous function that takes input via argument and returns the output.

Hooray for operator precedence!

**How it works**

```
lambda n:   Function with input string length n
n and ...   Base case: return 0 if n=0

(Case sensitive)

53*...      The first character can be any of [a-z], [A-Z] and _ , giving 53 possibilities
...63**~-n  63^(n-1): the remaining n-1 characters can be any of above and [0-9], giving
            63 possibilities

(Case insensitive)

27*...      The first character can be any of [A-Z] and _ , giving 27 possibilities
...37**~-n  37^(n-1): the remaining n-1 characters can be any of above and [0-9], giving
            37 possibilities
...-...     Subtract the case insensitive value from the case sensitive value
:...        Return the above

```

Try it on Ideone
> 3 votes

# Answer
## Pyth, 16 bytes

```
L*b^+TbtQ-y53y27

```

Try it here!

Works the same as my Pyke answer
> 2 votes

# Answer
# Factor, 54 bytes

```
[ 1 - [ 63 swap ^ 53 * ] [ 37 swap ^ 27 * ] bi - ⌊ ]

```

Test output (too lazy to make a test suite right now)

To 100 because I can:

```
0   0
1   26
2   2340
3   173394
4   11884860
5   784304586
6   50726849940
7   3244471004034
8   206202813193260
9   13057419408922746
10  825083183338785540
11  52071473691679633074
12  3283878468805254213660
13  207009241705220196670506
14  13046203459736972095009140
15  822081803558828931061964514
16  51797480091236011152730146060
17  3263475325027970876967575323866
18  205607606410125945699743561920740
19  12953599658372394455762938112142354
20  816088635295235866150191568376990460
21  51414022725857535138635748098295218826
22  3239099663712558709867478263942757120340
23  204063879397281956578587897577149556950594
24  12856046623614221305157697924464388847546860
25  809931759486357889731081403194103267502851386
26  51025731268991039110785546457483836346653407940
27  3214622195536403670115403894902928918116194213234
28  202521239965622254844299280697898069287570327415260
29  12758839658766868529390921590771079620628184030477546
30  803806955516821376897030535770307562553491969842783540
31  50639840307096567147692815348943369659664900009235194274
32  3190310017399946085222303356013750037654300219219990995660
33  200989533984152510500958383022988009088751140000471861713306
34  12662340747855976725442649179430749571102940189045387160447140
35  797727471068538170566530927116489907924415111563438806390997714
36  50256830823601535309646277474395913542200557575679083168097488060
37  3166180347299391055374044156331053378848244132513532459112333134666
38  199469362080123926730618942840288463417954913542445303046398068798740
39  12566569818457512122984997355621160915700234281355486142448958342967554
40  791693898836982339089426979801403683342770524668108612843741935926892460
41  49876715636873773150264669144187442239779806356971223086325671695231877626
42  3142233085498371482609012624501672238105982542695761132093804716877601438340
43  197960684400284383047634318675066295949671525651476192195155330966174637087794
44  12471523117731734378801823439793231607942107258123800020604874301575774756008860
45  785705956436110540996146747147743624935526399518788998053580353675424396549238186
46  49499475256178381262627624276616339615439587933192321957328073370569308698667165940
47  3118466941165264455200744360060243571819246756040935041269911532639516601510442382434
48  196463417294374638796889443817231669538334996131822201644459414237154601574451074437260
49  12377195289581232434616009278422739187922835424850800583245777641132746959324266250272346
50  779763303244935960426051634304306897098424666501802506291342869526467319662381170513981540
51  49125088104479743237515245802427284662794337274853034469588379271166298804053252422013315474
52  3094880550584028599998398220679389089143005829869601804793717698250434558272314733733240577660
53  194977474686860578513191784102480908365326982799277757130761257743954813314983341977611019396106
54  12283580905274687184722912157844434869740351690501733906101969819773718376165568553428918153085140
55  773865597032396709958041167041560489574457972145056938738392490176213167779330685193080529096190914
56  48753532613044375168215008464220671276081037423946152138715557367728779243091128221265244694777630060
57  3071472554621920785909306886048189626410042209324487489672362842172125030215492994941453756154541985466
58  193502770941185640073821503874720577896459322697230268331890319993036718605903879610376090231927542876740
59  12190674569294866655427556036093727770484123879787646494762754214200448415158073789829080317596516919552754
60  768012497865582938530677678077399109971765706771520893994639085516276250445445435611121365429028589509594460
61  48384787365531959679266134687605431564178077913367085420171928478326379788811073557020550322585378011481976426
62  3048241604028522138211603801162125831073621928852293338115689139494198039092774045292531129443472159001332956340
63  192039221053797215808791020159404322131263093269170657697148148666441012621558792067838210142400699755368808584994
64  12098470926389236476707853555431516900893696610762369998567143482483125633030622907206930951507336372904773737270860
65  762203668362522337620493487551580215201395390665800196764662013706838562882208746410562227308797606160712680915464986
66  48018831106838923534843342117447155624156332266892935209806189913015690437626492644356866682916159530830240509968123940
67  3025186359730852784490963892261982080781180571047313262322191837350928353684220676552666116434808733122402791782863511634
68  190586740663043747689376558750428888318209646590603894258160955047853260958314713301270755405603305445874988549550654259260
69  12006964661771756928289219042180208601520032747949102211343066331920312103393552933082810823150791387679177947309210580307146
70  756438773691620716964985145770771121482256588592212543618533446975485259045523696603018951464617833773583196421918482952379540
71  47655642742572106296656344989755045898082462523751897107212657077842278391541997773285863117697288652678155847014078432541996674
72  3002305492782042738420254124183837105633106144366742271546464242884371700319084040546949135905704694741593153841915859492202959660
73  189145246045268694064519472247264698574880394293808554997733720639986819101224007245165566663218089624766534104801769122964901718906
74  11916150500851927783194334861253945564257269006861979264798563913835211476678615826001618230525611319033999768874671043820165072923140
75  750717481553671452455038596317020544047680701587330184780139088571711872342908421711680887160599764988069185889174180556385321385544114
76  47295201337881301582877865070119107294484376103737744811768456374021309282152988680758316620704776514138665127670559852493727353570572060
77  2979597684286522002615091538996935841273293894973707820454341421941470553783979337065903514099119599226677240459390970372438551207353876266
78  187714654110050886271820850421245945023886308799558098889201870386303383441699317091742715367049125868210495633339022021080976659562384154740
79  11826023208933205839086306664722737056380582810772096959441117184084770483299475874473650445339864801023664915823061850169943403091896529897954
80  745039462162791968009016264140349407787379295265439767433382158538003861527346479306512775013394967703567826260992924685854583715749735525096460
81  46937486116255893989991445578566240700314790994634218730880971697698786156163569667253198313252271919170619707315735295839320298967762741317515226
82  2957061625324121321570127646145469600479097962199681775200883358217791614396112323461838552769003522200045367717199022141204995255363640622751674340
83  186294882395419643266342704970909052975476018411475813658404790794443290909593951451816650008709306376417822233966923239519043908642509112264039442194
84  11736577590911437526054302953925815658830824491260123147847219971438656837802057319192119334366383427393476471247901403340755546923998264934769791332860
85  739404388227420564151585450105392563397247850208862193146980429802018372669942231085027322266336949575917703497413242262756663341354137752789503193531786
86  46582476458327495541925964824938180038990133131758872257066173226778328178077627497465902058225655188337576695262466055088365154255573819716001935756281940
87  2934696016874632219155250798298147938620028574339029453481005940809327991114127409087391517619734089372293502673776337794350733176860886869847861631505600834
88  184885849063101829807295655822883896191116857103773014116879344289312516128313791212146134064249406693214458990720825405024094143116346113226785650902666881260
89  11647808490975415277878675971455406774188399103593023755623709580904708065544348130631903778853340506994629744339509897103777855276371884029063199627227132581946
90  733811934931451162507061423422398315397346516450407479655925206552083331459335365747677739381568683697580070526580745691266622080032985612974682610468596757977540
91  46230151900681423237970948652777278349101493334565409591233653622119458645149661082264806229649731647953525118602676998977756027354075699625721942715793229749237874
92  2912499569742929663993134687280117361718934603610641124045403705739039618883255370668643812466536563096293367462807981691433106666850680498728209106577023932078141660
93  183487472893804568831603187418387900340137879398192142647374723980743503786481677084105117925340131838249669694817958084526161366922717594045263062187188374662340681706
94  11559710792309687836392321785788836463846951378802809804587636359996649027031299439381903065674516455247507129925990403129885565051842823161990850791287794680559919961140
95  728261779915510333692765148706621450691833741003095095947733154400551795376841154655141276683483798209790732933978380017958074358887427604479576881170443366718075867057314
96  45880492134677151022646012787988367271956130436320159940279535084902990655674156472314911622261081963797134173540354372100044183752897139657357014922552487271422413276314060
97  2890471004484660514426765717163702125632948593353801325373787525582612830543998915730356846276907462752691218884931833388144147044723120219693807782246945239322406481520807066
98  182099673282533612408888715907569328452365119288317839716587156275352411836023432836069625636200164217658002129970617297449211712144308789428081576440224676102555002804992632740
99  11472279416799617581760080704048343190386108757724073082212416905402170675604281811039500754948545126089276981776285626117157164453181285710701891703604838257394970772074262003154
100 722753603258375907650888473624290214416147782711338423841877029262370595570657559163071778136871929817566895212667053691361603944309744782913331015678320105744441365668988373398460

```
> 2 votes

# Answer
# dc, 19 bytes

```
1-d63r^53*r37r^27*-

```

This is just a difference of two exponentials, `53 × 63^(n-1) - 27 × 37^(n-1)`. The special case of zero falls out naturally, as `dc` starts with a precision of `0`, meaning that *x*^-1 == `0` for all positive *x*.

As normal for `dc`, input is taken from top of stack, and output is pushed to top of stack. For a full program, enclose between `?` and `p` to make a pipeline filter.

## Test output

```
$ for i in {0..30}; do printf '%2d -> %s\n' "$i" `./85108.dc <<<$i`; done
 0 -> 0
 1 -> 26
 2 -> 2340
 3 -> 173394
 4 -> 11884860
 5 -> 784304586
 6 -> 50726849940
 7 -> 3244471004034
 8 -> 206202813193260
 9 -> 13057419408922746
10 -> 825083183338785540
11 -> 52071473691679633074
12 -> 3283878468805254213660
13 -> 207009241705220196670506
14 -> 13046203459736972095009140
15 -> 822081803558828931061964514
16 -> 51797480091236011152730146060
17 -> 3263475325027970876967575323866
18 -> 205607606410125945699743561920740
19 -> 12953599658372394455762938112142354
20 -> 816088635295235866150191568376990460
21 -> 51414022725857535138635748098295218826
22 -> 3239099663712558709867478263942757120340
23 -> 204063879397281956578587897577149556950594
24 -> 12856046623614221305157697924464388847546860
25 -> 809931759486357889731081403194103267502851386
26 -> 51025731268991039110785546457483836346653407940
27 -> 3214622195536403670115403894902928918116194213234
28 -> 202521239965622254844299280697898069287570327415260
29 -> 12758839658766868529390921590771079620628184030477546
30 -> 803806955516821376897030535770307562553491969842783540

```

Performance is reasonable for small *n*, but does start to tail off once it reaches a few hundred thousand or so:

```
   1024:   0.00s
   2048:   0.00s
   4096:   0.01s
   8192:   0.04s
  16384:   0.12s
  32768:   0.38s
  65536:   1.16s
 131072:   3.48s
 262144:  10.41s
 524288:  30.63s
1048576:  93.70s

```

That last example does produce a 1941435-digit result, so maybe it's not too bad for all that.
> 2 votes

# Answer
## Pyke, ~~17~~ 15 bytes

```
53[DT+Qt^*)27[-

```

Try it here!

```
  [DT+Qt^*)     - [ = lambda a: a*(a+10)^(input-1)
53[        27[- - [53)-[27)

```
> 1 votes

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


# Question
Title: A Peak Experience: Quickly Visit All the Peaks
I am standing at point `(0,0)` in a `H` x `W` map where the altitude is represented by digits, for example:

```
1132
2221
1230    # H = 3, W = 4

```

I'd like to experience the views from every peak, which in this case are the areas with altitude `3`. However, climbing up hills is not an easy task, and I am also running out of time.

# Challenge

The challenge is to find the quickest path to visit all the peaks and come back.

**Shortest program wins.**

## Input

* H, W - height and width of the map (Integers) (optional, may be a list/tuple or two separate integer inputs)
* The map, given as `H` sets of `W` digits (`0`-`9`), in any convenient format (2D list, string separated by newlines, etc.)

## Output

* Shortest time taken to visit every peak and come back to your starting point (Integer)

## Conditions

* The altitude of a given area is represented by a digit from `0` to `9`.
* The "peak" is defined by the area with the highest altitude.
* The path must both begin and end at the **top-left (0,0)** area.
* You can only move to areas adjacent to your current area, and you may not move diagonally.
    + It takes **3 minutes** to move from one area to another if there is no change in altitude.
    + It takes **11 minutes** to climb up; that is, moving from one area to another area that is exactly `1` unit higher.
    + It takes **2 minutes** to climb down; that is, moving from one area to another area that is exactly `1` unit lower.
    + **You cannot move** to areas that are more than `1` unit higher or lower than where you are. (You cannot go from an area with altitude `1` to an adjacent area with altitude, say, `3`)
* A path to all the peaks is guaranteed
* Maximum number of peaks is `15`.

# Samples

## Input

```
4 5
32445
33434
21153
12343

```

## Output

```
96

```

## Explanation

You start at the top-left `3`. You have to visit the two `5`s that are located at `(0,4)` and `(3,3)` and come back to the `3` at `(0,0)` in the shortest time possible.

```
3  2  4->4->5
V     ^
3->3->4  3  4

2  1  1  5  3

1  2  3  4  3    # 3 + 3 + 11 + 3 + 3 + 11 = 34 minutes to visit 1st peak

3  2  4  4  5
            V
3  3  4  3  4
            V
2  1  1  5  3
         ^  V
1  2  3  4<-3    # 2 + 2 + 3 + 11 + 11 = 29 minutes to visit 2nd

3  2  4  4  5
^
3  3  4  3  4
^
2  1  1  5  3
^        V
1<-2<-3<-4  3    # 2 + 2 + 2 + 2 + 11 + 11 + 3 = 33 minutes to come back

# 34 + 29 + 33 = 96 minutes total is the answer

```

## Input

```
2 7
6787778
5777679

```

## Output

```
75

```

# Answer
> 5 votes
# Mathematica ~~745~~ 681 bytes

The basic idea is to make a weighted graph of possible moves. Weights are the time it takes to move from one place to the next. The path with the least weight will be the quickest.

The input digits are placed in an r by c (rows by columns) rectangular array and then three distinct representations come into play: (1) an r by c grid graph, where each vertex corresponds to a cell in the array, (2) (r*c) by (r*c) weighted adjacency matrix that holds weights corresponding to the time it takes (2, 3, or 11 minutes) to move from one location (in the grid graph) to another, and (3) a directed, weighted adjacency graph constructed from the matrix.

The grid graph helps determine which cells (i.e. which vertices) are possibly reachable from each vertex--"possibly reachable" because a neighboring cell must not only be right, left, above or below a given cell. It's value must also be within 1 unit of distance from the neighbor (e.g., a 3 does not connect to a neighboring 5 or a 1). If vertex `a` is not connected to vertex `b` then the adjacency matrix cells {a,b} and {b,a} will have a value of ∞. Accordingly, the weighted adjacency graph will not have an edge from a to b, nor from b to a.

The weighted adjacency graph serves to determine the minimum distance (`GraphDistance`) and shortest route between any vertices. The optimal path must begin with 1, touch each of the peaks, and return to 1. In this case, "shortest route" is not necessarily the one with the fewest moves. It is the one with the shortest overall time, measured in edge weights.

---

## Golfed

```
o=Sequence;v[a_<->b_,z_]:=(m_~u~q_:={Quotient[m-1,q[[2]]]+1,1+Mod[m-1, q[[2]]]};j=z[[o@@u[a,i=Dimensions@z]]];k=z[[o@@u[b,i]]];Which[j==k,{{a,b}->3,{b,a}->3},j==k-1,{{a,b}->11,{b,a}->2},j==k+1,{{a,b}->2,{b,a}->11},2<4,{{a,b}->∞, {b, a}->∞}]);w@e_:=Module[{d,x,l,y},x=Map[ToExpression,Characters/@Drop[StringSplit@e,2],{2}];d_~l~c_:=d[[2]](c[[1]]-1)+c[[2]];g_~y~p_:=(Min[Plus@@(GraphDistance[g,#,#2]&@@@#)&/@(Partition[#,2,1]&/@({1,o@@#,1}&/@Permutations@p))]);y[WeightedAdjacencyGraph[ReplacePart[ConstantArray[∞,{t=Times@@(d=Dimensions@x),t}],Flatten[#~v~x &/@Union@Flatten[EdgeList[GridGraph@Reverse@d,#<->_]&/@Range@(Times@@d),1],1]]], l[Dimensions@x, #] & /@ Position[x, Max@x]]

```

---

## Longer, more readable form

```
(*determines a weight (number of minutes) to go from vertex a to b and from b to a*)
weight[a_ <-> b_, dat_]:=
  Module[{cellA,cellB,dim,valA,valB,vertexToCell},

  (*Convert graph vertex index to cell location*)
  vertexToCell[m_,dimen_]:={Quotient[m-1,dim[[2]]]+1,1+Mod[m-1,dimen[[2]]]};
     dim=Dimensions[dat];
     cellA = vertexToCell[a,dim];
     cellB = vertexToCell[b,dim];
     valA=dat[[Sequence@@cellA]];
     valB=dat[[Sequence@@cellB]];
     Which[
       valA==valB,{{a,b}-> 3,{b,a}-> 3},
       valA==valB-1,{{a,b}-> 11,{b,a}-> 2},
       valA==valB+1,{{a,b}-> 2,{b,a}-> 11},
       2<4,{{a,b}->∞,{b,a}->∞}]];

(* weights[] determines the edge weights (times to get from one position to the next), makes a graph and infers the shortest distance
from vertex 1 to each peak and back.  It tries out all permutations of peaks and
selects the shortest one. Finally, it returns the length (in minutes) of the shortest trip. *)

weights[str_]:=
  Module[{d,dat,neighbors,cellToVertex,peaks,z,gd},
  dat=Map[ToExpression,Characters/@Drop[StringSplit[str],2],{2}];
  cellToVertex[dim_,cell_]:=dim[[2]] (cell[[1]]-1)+cell[[2]];
  peaks[dat_]:= cellToVertex[Dimensions[dat],#]&/@Position[dat,peak =Max[dat]];

     (* to which cells should each cell be compared? neighbors[] is a function defined within weights[]. It returns a graph, g, from which graph distances will be derived in the function gd[] *)
  neighbors[dim_]:=
  Union@Flatten[EdgeList[GridGraph[Reverse@dim],#<->_]&/@Range@(Times@@dim),1];
    d=Dimensions[dat];
    m=ReplacePart[ConstantArray[∞,{t=Times@@d,t}],
     (*substitutions=*)
    Flatten[weight[#,dat]&/@neighbors[d],1]];
    g=WeightedAdjacencyGraph[m,VertexLabels->"Name",ImageSize->Full,GraphLayout->"SpringEmbedding"];

    (* finds shortest path.  gd[] is also defined within weights[] *)
  gd[g3_,ps_]:=
    Module[{lists,pairs},
    pairs=Partition[#,2,1]&/@({1,Sequence@@#,1}&/@Permutations@ps);
    Min[Plus@@(GraphDistance[g3,#,#2]&@@@#)&/@pairs]];

  gd[g,peaks[dat]]]

```

---

## Tests

```
weights["4 5
 32445
 33434
 21153
 12343"]

```

96.

---

```
weights@"2 7
 6787778
 5777679"

```

75.

---

```
weights@"3 4
 1132
 2221
 1230"

```

51.

---

## Explanation

Think of lines 2-5 of the following input

```
"4 5
 32445
 33434
 21153
 12343"

```

as representing an array with 4 rows and 5 columns:

where each vertex corresponds to a digit from the input array: 3 is at vertex 1, 2 is at vertex 2, 4 is at vertex 3, another 4 at vertex 4, 5 at vertex 5, etc. The grid graph is only a rough approximation of the graph we are aiming for. It is undirected. Furthermore, some of the edges will be unavailable. (Remember: we cannot move from a position to another that is more than 1 height unit above or below the current one.) But the grid graph let's us easily find those vertices that are next to any chosen vertex. This reduces the number of edges we need to consider, in the first example (a 4 by 5 grid), from 400 (20 * 20) to 62 (31 \*2 is the number of edges in the grid graph). In the same example, only 48 of the edges are operative; 14 are not.

The following 20 by 20 weighted adjacency matrix represents the distance between all pairs of vertices from the grid graph.

The key code which decides on which number to assign is below.

```
Which[
      valA==valB,{{a,b}-> 3,{b,a}-> 3},
      valA==valB-1,{{a,b}-> 11,{b,a}-> 2},
      valA==valB+1,{{a,b}-> 2,{b,a}-> 11},
      2<4,{{a,b}->∞,{b,a}->∞}]

```

Cell {1,2}--in one-indexing-- contains the value 2 because the move from vertex 1 to vertex 2 is downhill. Cell {2,1} contains 11 because the move from vertex 2 to vertex 1 is uphill. The 3's in cells {1,6} and {6,1} signify that the movement is neither up nor down. Cell {1,1} contains ∞ because it is not connected to itself.

The following graph shows the structure underlying the above input. The colored arrows show the optimal path from vertex 1 to the peaks (at 5 and 14) and back to 1. Blue arrows correspond to moves at the same level (3 min); red arrows mean ascent (11 min.) and green arrows indicate descent (2 min).

The path from vertex 1 (cell {1,1} to the two peaks and back to vertex 1:

```
3 + 3 + 11 + 3 + 3 + 11 + 2 + 2 + 3 + 11 + 11 + 2 + 2 + 2 + 2 + 11 + 11 + 3

```

96

# Answer
> 0 votes
# Pyth, 92 bytes

```
hSms@Lu.dm,bhS,@Gb+@G,hbH@G,HebG[FQ.dm,(Fb?|tsaMCb>.aJ-F@LQb1.n4@[3hT2)J*QQC.<B+]hSQd1.p.M@Q

```

The input format is a dict mapping coordinates to heights: `{(0, 0): 3, (0, 1): 2, (0, 2): 4, …}`. This finds the fastest paths between all pairs of points using the Floyd–Warshall algorithm, then minimizes the total time of the desired cycle over all permutations of peaks.

Try it online

---
Tags: code-golf, path-finding, puzzle-solver, graph-theory
---


title: Interpret Kipple!

text:
# Question
Title: Interpret Kipple!
# Introduction

Kipple is a stack-based, esoteric programming language invented by Rune Berg in March 2003.

Kipple has 27 stacks, 4 operators, and a control structure.

## Stacks

The stacks are named `a`-`z` and contain 32-bit signed integers. There is also a special stack, `@`, to make outputting numbers more convenient. When a number is pushed onto `@`, the ASCII values of that number's digits are in fact pushed instead. (For example, if you push 12 to `@`, it will push 49 and then 50 to `@` instead.)

Input is pushed onto the input stack `i` before the program is executed. The interpreter will ask for values to store in `i` before execution. After execution finishes, anything on the output stack `o` is popped to output as ASCII character . Since this is Kipple's only IO mechanism, interacting with a Kipple program is impossible.

## Operators

An operand is either a stack identifier or a signed 32 bit integer.

### Push: `>` or `<`

Syntax: `Operand>StackIndentifier` or `StackIndentifier<Operand`

The Push operator takes the operand to the left and pushes it onto the specified stack. For example, `12>a` will push the value 12 onto stack `a`. `a>b` will pop the topmost value from stack `a` and push it onto stack `b`. Popping an empty stack always returns 0. `a<b` is equivalent to `b>a`. `a<b>c` pops topmost value from `b` and pushes to both `c` and `a`.

### Add: `+`

Syntax: `StackIndentifier+Operand`

The Add operator pushes the sum of the topmost item on the stack and the operand onto the stack. If the operand is a stack, then the value is popped from it. For example, if the topmost value of stack `a` is 1, then `a+2` will push 3 onto it. If `a` is empty, then `a+2` will push 2 onto it. If the topmost values of stack `a` and `b` are 1 and 2, then `a+b` will pop the value 2 from stack `b` and push 3 onto stack `a`.

### Subtract: `-`

Syntax: `StackIndentifier-Operand`

The Subtract operator works exactly like the Add operator, except that it subtracts instead of adding.

### Clear: `?`

Syntax: `StackIndentifier?`

The Clear operator empties the stack if its topmost item is 0.

The interpreter will ignore anything that isn't next to an operator, so the following program would work: `a+2 this will be ignored c<i`. However, the proper way to add comments is by using the `#` character. Anything between a `#` and an end-of-line character is removed before execution. ASCII character #10 is defined as end-of-line in Kipple.

Operands may be shared by two operators, e.g. `a>b c>b c?` may be written as `a>b<c?`.

The program `1>a<2 a+a` will result in `a` containing the values `[1 4]` (from bottom to top) and not `[1 3]`. Likewise for the `-` operator.

## The Control Structure

There is only one control structure in Kipple: the loop.

Syntax: `(StackIndentifier code )`

As long as the specified stack is not empty, the code within the matching parentheses will be repeated. Loops may contain other loops. For example, `(a a>b)` will move all the values of stack `a` onto stack `b`, though the order will be *reversed*. A functionally identical, but more elegant way to do this is `(a>b)`.

## Examples

```
100>@ (@>o)

```

This will output `100`

```
33>o 100>o 108>o 114>o 111>o 87>o 32>o 111>o 108>o 108>o 101>o 72>o

```

This will print `"Hello World!"`. When the `o` stack is being output, it starts to pop characters from top of the stack to bottom.

```
#prime.k by Jannis Harder
u<200
#change 200

k<2>m
u-2
(u-1 u>t u>z u<t
  (k>e e+0 e>r)
  (e>k)
  m+1
  m>t
  m>z
  m<t
  t<0>z? t?
  1>g
  (r>b
    m+0 m>a
    b+0 b>w
    (a-1
      b+0 b>j
      j?
      1>s
      (j<0>s j?)
      s?
      (s<0 w+0 w>b s?)
      a>t
      a>z
      t>a
      b-1
      b>t
      b>z
      t>b
      z<0>t? z?
    a?)
    b?
    1>p
    (b<0 b? 0>p)
    p?
    (p 0>r? 0>p? 0>g)
  )
  g?
  (g m+0 m>k 0>g?)
u?)
(k>@
  10>o
  (@>o)
)

```

This is a prime number generator, but I'm not sure how it works.

# Rules

* You must write a program/function that interprets Kipple. This program/function may get a Kipple program via a source file, or get it via STDIN directly from the user. If STDIN is not available, it must get it from keyboard input, and continue getting input until a specific unprintable character is entered. For example, if your interpreter is written in x86 machine code, it would get the Kipple program character by character from keyboard, and continue to do so until `esc` (or any other key other that does not emit a printable character) is pressed.
* If there is an error, e.g. a syntax error or stack overflow, it must acknowledge it in some way, for example by returning 10 instead of 0 or error messages produced by the interpreter/compiler, **BUT NOT PRINTING ERROR MESSAGES**.
* Any other regular rules for code golf apply for this challenge.
* Your code will be tested with some of the examples in Kipple's samples archive

This is a . Shortest code in bytes will win. Good Luck!

---

Note that there is an optional operator in Kipple, `"`, but it is not a part of the specification and just an extra feature in official interpreter. I haven't mentioned it here so it does not need to be supported in your submission.

If you have any doubt about any part of specification , you can examine it with official interpreter written in Java . This will download a zip file containing compiled program and source code . It's licensed under the GPL.

# Answer
# C, 709 702 bytes

The byte score is with newlines (that can be removed) removed, but for ease of reading I post it here with newlines:

```
#define R return
#define C ;break;case
c[999]={};*P=c;*S[28];M[99999]={};t;*T;
u(s,v){S[s]+=28;*S[s]=v;
if(s>26){for(t=v/10;t;t/=10)S[s]+=28;T=S[s];do{*T=48+v%10;T-=28;}while(v/=10);}}
o(s){t=S[s]-M>27;S[s]-=28*t;R S[s][28]*t;}
I(s){R s<65?27:s-97;}
O(int*p){if(!isdigit(*p))R o(I(*p));
for(;isdigit(p[-1]);--p);for(t=0;isdigit(*p);t*=10,t+=*p++-48);R t;}

main(i,a){for(i=0;i<28;++i)S[i]=M+i;
for(;~(*++P=getchar()););P=c+1;
for(;;){i=I(P[-1]);switch(*P++){
case 35:for(;*P++!=10;)
C'<':u(i,O(P))
C'>':u(I(*P),O(P-2))
C'+':u(i,*S[i]+O(P))
C'-':u(i,*S[i]-O(P))
C'?':if(!*S[i])S[i]=M+i
C'(':for(i=1,T=P;i;++T)i+=(*T==40)-(*T==41);if(S[I(*P)]-M<28)P=T;else u(26,P-c)
C')':P=c+o(26)-1
C-1:for(;i=o(14);)putchar(i); R 0;}}}

```

Compile with `gcc -w golf.c` (`-w` silences warnings for your sanity).

Supports everything except the `i` input, as the asker has not responded yet to my inquiry on how to do it if you take the code from stdin. It does not report syntax errors.
> 6 votes

# Answer
# Ruby, 718 bytes (currently noncompeting)

i'm very tired

File is loaded as a command line argument, and input is sent through STDIN. Alternatively, pipe the file into STDIN if you don't need input in your `i` register.

~~Because of some confusion regarding the spec, the current version is not handling `a<b>c` properly, and therefore is noncompeting until it is fixed.~~

`a<b>c` is fixed now. However, it still returns the wrong result when running the primes function, so it still remains as a noncompeting answer.

```
(f=$<.read.gsub(/#.*?\n|\s[^+-<>#()?]*\s/m,' ').tr ?@,?`
t=Array.new(27){[]}
t[9]=STDIN.read.bytes
k=s=2**32-1
r=->c{c=c[0];c[0]==?(?(s[c[1..-2]]while[]!=t[c[1].ord-96]):(c=c.sub(/^(.)<(\D)>(.)/){$1+"<#{t[$2.ord-96].pop||0}>"+$3}.sub(/(\d+|.)(\W)(\d+|.)?/){_,x,y,z=*$~
a=x.ord-96
b=(z||?|).ord-96
q=->i,j=z{j[/\d/]?j.to_i: (t[i]||[]).pop||0}
l=t[a]
y<?-?(x==z ?l[-1]*=2:l<<(l.pop||0)+q[b]
l[-1]-=k while l[-1]>k/2):y<?.?(x==z ?l[-1]=0:l<<(l.pop||0)-q[b]
l[-1]+=k while l[-1]<-k/2-1):y<?>?t[a]+=a<1?q[b].to_s.bytes: [q[b]]:y<???
(t[b]+=b<1?q[a,x].to_s.bytes: [q[a,x]]): l[-1]==0?t[a]=[]:0
z||x}while c !~/^(\d+|.)$/)}
s=->c{(z=c.scan(/(\((\g<1>|\s)+\)|[^()\s]+)/m)).map &r}
s[f]
$><<t[15].reverse.map(&:chr)*'')rescue 0

```
> 3 votes

---
Tags: code-golf, interpreter
---


title: Cannonball Conundrum

text:
# Question
Title: Cannonball Conundrum
Your task is to, with an input number `p`, find the smallest positive cannonball number of order `p` that is NOT 1.

### Definition

A cannonball number (of order `p`) is a number which is both:

* An `p`-gonal number (See this page).
* and an `p`-gonal pyramid number.

+ The `n`th `p`-gonal pyramid number is the sum of the 1st to `n`th `p`-gonal numbers.
        - (e.g. `4th square pyramid number = 1 + 4 + 9 + 16 = 30`)
    + The picture below represents the 4th square pyramid number, as a square pyramid.
    + For more info, visit this link.

The cannonball number of order 3, for example, is 10, because it is:

* The fourth triangle number (`1 + 2 + 3 + 4 = 10`)
* and the third triangular pyramid number. (`1 + 3 + 6 = 10`)

### Formulas

**NOTE: If you can find (or make) more useful formulae than my ones here, please post it here (or message me on the question chat thing).**

* If you're interested, the formula for the `n`th `p`-gonal number is:

* And the `n`th `p`-gonal pyramid number is:

### Specs

* `p` is guaranteed to be larger than 2.
* The program must check values for a solution for `p` up to (and including) `2^16`. Your program may do anything if no solutions are found for `p`.
* Only positive indices for `n`.

### Test cases

* `3` outputs `10` (4th triangle number, 3rd triangle pyramid number)
* `4` outputs `4900` (70th square number, 24th square pyramid number)

This is code-golf, so shortest answer in bytes wins.

Note: If you do post a solution, please include a description of how the code works.

Should I start a bounty for a solution which is better and doesn't use my formulae?

# Answer
> 1 votes
# Python 3, ~~129~~ 127 bytes

```
def f(p):
 x=2
 while 1:
  for i in range(x*x):
   if i//x*((p-2)*i//x+4-p)/2==i%x*(i%x+1)*((p-2)*i%x+5-p)/6==x:return x
  x+=1

```

A function that takes input via argument and returns the output.

This is an *extremely* naïve brute force, and takes a very long time for even moderately large `p`; the execution time will be ridiculous for anything approaching the given maximum for `p` of `2^16`, but there is no reason why the program would not work, given sufficient time.

There are probably far shorter and faster ways of doing this, but I thought it would be good to post something to get this started off.

**How it works**

The return value `x` is initialised to `2`, and then the program simply loops over all the `p`-gonal and `p`-gonal pyramidal numbers up to order `x`. If the current `p`-gonal and `p`-gonal pyramidal numbers, calculated using the formulas, are equal to each other and to `x`, then `x` must be the relevant cannonball number and this is returned. Else, `x` is incremented, and the program tries again for the new value of `x`.

In terms of golfing, a Cartesian product is used to collapse the two for-loops for the `p`-gonal and `p`-gonal pyramidal numbers into a single loop, and the formulas were factorised further to save a few bytes.

# Answer
> 1 votes
# JavaScript, ~~111~~ 98 bytes

```
f=n=>{for(b=c=g=1;b++;)for(p=b*(b*3+b*b*(n-2)-n+5)/6;g<p;c++)if(p==(g=c*(c*n-c-c-n+4)/2))return p}

```

**ungolfed**

```
f=n=>{
for(b=2,c=g=1;b<1e6;b++)    // run index b from 2 (to 100k)
    for(
        p=(b*b*3+b*b*b*(n-2)-b*(n-5))/6 // p=the b-th n-pyramidal number
        ;g<p&&c<1e6;c++)   // run while n-gonal is lower than n-pyramidal (and c below 100k)
        if(p==(
            g=(c*c*(n-2)-c*(n-4))/2     // g=the c-th n-gonal number
        )) return p                     // if they are equal, return
}

```

c is not reinitialized in the inner loop because the next p\[b\] is definitely larger than the current g\[c\] (so we have to move *on* anyway)

**examples**

```
samples=[3,4,6,8,10,11,14,17,23,26,30,32,35,41,43,50,88]
for(i in samples) document.write('n='+(n=samples[i])+': '+f(n)+'<br>');

```

# Answer
> 0 votes
# old PHP program, ~~115~~ 106 bytes

<sup>+16 for current PHP, see below</sup>

```
<?for($b=2;1;$b++)for($p=$b*($b*3+$b*$b*($n-2)-$n+5)/6;$g<$p;++$c)if($p==$g=$c*($c*$n-2*$c-$n+4)/2)echo$p;

```
* loops forever
* usage: with PHP\<4.2: run from browser with `<scriptpath>?n=<number>`
with PHP\<5.4, add `register_globals=1` to `php.ini` (+18 ?)
* see my JavaScript answer for description
* +10 for PHP\>=5.4: replace `1` with `$n=$_GET[n]`. Or replace `1` with `$n=$argv[1]`, run `php -f <filename> <number>`.
* +6 for finite loop on success: replace `echo$p` with `die(print$p)`
* +/- 0 for function:

```
function f($n){for($b=2;1;$b++)for($p=$b*($b*3+$b*$b*($n-2)-$n+5)/6;$g<$p;++$c)if($p==$g=$c*($c*$n-2*$c-$n+4)/2)return$p;}

```

loops forever if it finds nothing. Replace `1` with `$p<1e6` to break at 100k or with `$p<$p+1` to loop until integer overflow. (tested with PHP 5.6)

**examples** (on function)

```
$samples=[3,4,6,8,10,11,14,17,23,26,30,32,35,41,43,50,88];
foreach($samples as $n)echo "<br>n=$n: ", f($n);

```

**examples output**

```
n=3: 10
n=4: 4900
n=6: 946
n=8: 1045
n=10: 175
n=11: 23725
n=14: 441
n=17: 975061
n=23: 10680265
n=26: 27453385
n=30: 23001
n=32: 132361021
n=35: 258815701
n=41: 55202400
n=43: 245905
n=50: 314755
n=88: 48280

```

# Answer
> 0 votes
# C, 107 bytes

```
#define X(x)(1+p/2.0*x)*++x
c(p,m,n,a,b){m=n=a=b=1;p-=2;do if(a>b)b+=X(n);else a=X(m);while(a^b);return a;}

```

Ungolfed with test parameters:

```
#include <stdio.h>

#define X(x)(1+p/2.0*x)*++x
int c(int p)
{
    int m = 1, n = 1, a = 1, b = 1;
    p -= 2;
    do
        if(b < X(m))
            b += X(n);
        else
            a = X(m);
    while(a != b);
    return a;
}

int main()
{
    printf("%d\n", c(3));
    printf("%d\n", c(4));
}

```

This uses the fact that the n-th p-gonal number can be defined as `n(1+(p-2)(n-1)/2)` and the pyramid number is the sum of the aforementioned numbers.

I think it can be further golfed, given that it's not really necessary for variable `a` to be saved.

---
Tags: code-golf
---


title: Walk the labyrinth

text:
# Question
Title: Walk the labyrinth
Or maybe it's not really a labyrinth, but still.

Rules:

1. **Input** is a two-line string, consisting of `*`, `1`, `x` and `X`. That string is a labyrinth to walk through. The lines have the **equal length**.

You could take the input as a string with `,` (comma) or any convenient separator between these two lines. Or you could take both lines as separate arguments to your function.
2. **Output** is the number of steps you have to take to exit the string (last step is the step which moves you out of the string).
3. You start in the top left corner (the higher line), **before** the first symbol.
4. For each step, you move forward by one symbol (from nth to (n+1)th *position*). Then, depending on the character you step on, the outcome is different. Here's what each char does:

* `*` \- nothing. You just step on it normally.
    * `x` \- once you stepped on it, switch the line, but remain on the same horizontal distance from the beginning. For example, you stepped on the third position of the higher line, and met a lowercase `x` here. Then you immediately move to the lower line, but again at the third position.
    * `X` \- switch the line and go to the next position. The example is the same there, but you also move from the third to the forth position (thus you're on the second line at the forth position).
    * `1` \- just move forward by yet another position.

Once each character does its job, it's replaced with a space and no longer "works".

Examples follow.

1. **Input**:

```
x
*

```

As said before, you start before the first symbol of the first line. The first step moves you on letter `x` and this letter switches you to the second line. The letter `x` no longer functions as `x`, but replaced with `*`. This will be more relevant in the latter examples. You're now on an asterisk on the lower line, and it did nothing to you.

The second step is moving you forward and you exit the string, so the labyrinth is completed, and it took 2 steps.

**Output** `2`.
2. **Input**:

```
xX*
x1*

```

**1st step**: you move on `x`, which moves you on the `x` of the lower line. Here comes the rule which says that the used character is replaced with asterisk. Then you move back on the first line, but it's no longer `x` there, since it has been used and became an asterisk. So you move safely on this asterisk and the step is completed (you are now on the first position of the first line).

**2nd step**: you move on `X`, it pushes you to the lower line and then pushes you forward. You now reside on the third position of the second line (asterisk), having never visited the second position (which contains `1`).

**3rd step**: you move forward, exiting the string.

**Output**: `3`.

Test cases:

1. Input:

```
*1*
xxx

```

Output: `3`. (because `1` makes you jump on the third position). There you never visit the second line, but it's required part of the input.
2. Input:

```
*X*1*x
x*1xx*

```

Output: `4`.
3. Input:

```
1x1x
***X

```

Output: `3`.
4. Input:

```
1*x1xxx1*x
x*x1*11X1x

```

Output: `6`.
5. Input:

```
xXXXxxx111*
**xxx11*xxx

```

Output: `6`.

# Answer
# Snails, 34 bytes

```
A^
\1r|\xud|\Xaa7},(\*|\xud=\x)r},

```

Expanded:

```
{
    {
        \1 r |
        \x ud |
        \X aa7
    },
    (\* | \x ud =\x)
    r
},

```

For a path that takes N steps, the program finds one successful match for each traversal of 0 steps, 1 steps, ..., N - 1 steps.
> 5 votes

# Answer
## Haskell, ~~68~~ ~~66~~ 65 bytes

```
(a:b)#l@(c:d)|a<'+'=1+b#d|a>'w'=l#('*':b)|a>'W'=d#b|1<2=b#d
_#_=1

```

Function `#` takes both lines as separate parameters. Usage example: `"1x1x" # "***X"` -\> `3`.

We just have to count the stars `*` we step on plus 1 for leaving.

```
(a:b)#l@(c:d)             -- bind: a -> first char of first line
                                   b -> rest of first line
                                   l -> whole second line
                                   c -> first char of second line (never used)
                                   d -> rest of second line
   |a < '+' = 1+b#d       -- stepped on a *, so add 1 and go on
   |a > 'w' = l#('*':b)   -- x switches lines and replaces the x with *
   |a > 'W' = d#b         -- X switch lines and go on
   |1<2     = b#d         -- the rest (-> 1) simply walks forward
_#_=1                     -- base case: the empty string counts 1 for leaving

```

Edit: @feersum saved a byte. Thanks!
> 3 votes

# Answer
# JavaScript (ES6), 119

```
l=>{z=-~l.search`
`,l=[...l+' '];for(n=p=0;(c=l[p%=2*z])>' ';p+=c>'X'?z:c>'1'?z+1:c>'0'?1:(++n,1))l[p]='*';return-~n}

```

*Less golfed*

```
l=>{
  z=1+l.search`\n`;
  l=[...l+' '];
  for( n = p = 0;
       (c=l[p%=2*z])>' ';
       p += c>'X' ? z : c>'1' ? z+1 : c>'0'? 1 : (++n,1) )
    l[p] = '*';
  return 1+n
}

```

**Test**

```
f=l=>{z=-~l.search`
`,l=[...l+' '];for(n=p=0;(c=l[p%=2*z])>' ';p+=c>'X'?z:c>'1'?z+1:c>'0'?1:(++n,1))l[p]='*';return-~n}

[['x\n*',2]
,['xX*\nx1*',3]
,['*1*\nxxx',3]
,['*X*1*x\nx*1xx*',4]
,['1x1x\n***X',3]
,['1*x1xxx1*x\nx*x1*11X1x',6]
,['xXXXxxx111*\n**xxx11*xxx',6]
].forEach(t=>{
  var i=t[0],k=t[1],r=f(i)
  console.log('Test result '+r+(r==k?' OK ':' KO (expected '+k+')')+'\n'+i)
})

```
> 2 votes

# Answer
# TSQL(sqlserver 2012+), 276 bytes

**Golfed:**

```
DECLARE @i VARCHAR(99)=
'xXXXxxx111*'+CHAR(13)+CHAR(10)+
'**xxx11*xxx'

,@t BIT=0,@c INT=1,@ INT=1WHILE @<LEN(@i)/2SELECT @t-=IIF(a like'[1*]'or'xx'=a+b,0,1),@c+=IIF(a='*'or'xx'=a+b,1,0),@+=IIF(a='x'and'x'>b,0,1)FROM(SELECT SUBSTRING(d,@t*c+@,1)a,SUBSTRING(d,(1-@t)*c+@,1)b FROM(SELECT LEN(@i)/2+1c,REPLACE(@i,'X','q'COLLATE thai_bin)d)x)x PRINT @c

```

**Ungolfed:**

```
DECLARE @i VARCHAR(99)=
'xXXXxxx111*'+CHAR(13)+CHAR(10)+
'**xxx11*xxx'

,@t BIT=0,@c INT=1,@ INT=1
WHILE @<LEN(@i)/2
  SELECT
    @t-=IIF(a like'[1*]'or'xx'=a+b,0,1),
    @c+=IIF(a='*'or'xx'=a+b,1,0),
    @ +=IIF(a='x'and'x'>b,0,1)
  FROM
    (
      SELECT
        SUBSTRING(d,@t*c+@,1)a,
        SUBSTRING(d,(1-@t)*c+@,1)b
      FROM
        (SELECT LEN(@i)/2+1c,REPLACE(@i,'X','q'COLLATE thai_bin)d)x
    )x

PRINT @c

```

**Fiddle**
> 2 votes

# Answer
# JavaScript, 211 bytes

I'm thinking about making a version that shows each step played after each other, displayed on a webpage.

```
(x,y)=>{t=0;l=0;n=1;while(t<x.length){c=(l?x:y);if(c[t]=='x'){l=!l;if(l){x=x.slice(0,t-2)+'*'+x.slice(t-1);}else{y=y.slice(0,t-2)+'*'+y.slice(t-1);}}if(c[t]=='X'){l=!l;t++;}if(c[t]=='1'){return n}

```

Used more bytes than I'd hoped to when replacing `x` with `*` because of JS immutable `Strings`. Suggestions to improve are appreciated, especially with the replacement part.
> 1 votes

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


title: Latin square compression

text:
# Question
Title: Latin square compression
**A Latin square is a square that has no repeated symbols in the rows or columns:**.

```
13420
21304
32041
04213
40132

```

And as many Sudoku players know, you don't need all of the numbers to deduce the remaining numbers.

**Your challenge is to compress a Latin square into as few bytes as possible.** You need to provide one or two program(s) that compresses/decompresses.

Various info:

* The numbers used will always be `0..N-1`, where `N` is the length of the square's edge, and `N<=25`
* On decompression, the latin square must be identical to the input.
* Your program(s) should be able to (de)compress *any* latin square (within the maximum square size), not just the ones I've provided. Compression ratios should be similar as well.
* You must actually run the compression and decompressor to obtain your score (No end-of-universe runtimes)

The test cases can be found on github. **Your score is total size of compressed test cases.**

**EDIT: As of 20:07 on July 7th, I updated the test cases (in order to fix a generation issue). Please rerun your program on the new test cases.** Thanks Anders Kaseorg.

# Answer
# Python, ~~1281.375~~ 1268.625 bytes

We encode the Latin square one “decision” at a time, where each decision is of one of these three forms:

* which number goes in row *i*, column *j*;
* in row *i*, which column the number *k* goes in;
* in column *j*, which row the number *k* goes in.

At each step, we make all the logical inferences we can based on previous decisions, then pick the decision with the smallest number of possible choices, which therefore take the smallest number of bits to represent.

The choices are provided by a simple arithmetic decoder (div/mod by the number of choices). But that leaves some redundancy in the encoding: if *k* decodes to a square where the product of all the numbers of choices was *m*, then *k* \+ *m*, *k* \+ 2⋅*m*, *k* \+ 3⋅*m*, … decode to the same square with some leftover state at the end.

We take advantage of this redundancy to avoid explicitly encoding the size of the square. The decompressor starts by trying to decode a square of size 1. Whenever the decoder finishes with leftover state, it throws out that result, subtracts *m* from the original number, increases the size by 1, and tries again.

```
import numpy as np

class Latin(object):
    def __init__(self, size):
        self.size = size
        self.possible = np.full((size, size, size), True, dtype=bool)
        self.count = np.full((3, size, size), size, dtype=int)
        self.chosen = np.full((3, size, size), -1, dtype=int)

    def decision(self):
        axis, u, v = np.unravel_index(np.where(self.chosen == -1, self.count, self.size).argmin(), self.count.shape)
        if self.chosen[axis, u, v] == -1:
            ws, = np.rollaxis(self.possible, axis)[:, u, v].nonzero()
            return axis, u, v, list(ws)
        else:
            return None, None, None, None

    def choose(self, axis, u, v, w):
        t = [u, v]
        t[axis:axis] = [w]
        i, j, k = t
        assert self.possible[i, j, k]
        assert self.chosen[0, j, k] == self.chosen[1, i, k] == self.chosen[2, i, j] == -1

        self.count[1, :, k] -= self.possible[:, j, k]
        self.count[2, :, j] -= self.possible[:, j, k]
        self.count[0, :, k] -= self.possible[i, :, k]
        self.count[2, i, :] -= self.possible[i, :, k]
        self.count[0, j, :] -= self.possible[i, j, :]
        self.count[1, i, :] -= self.possible[i, j, :]
        self.count[0, j, k] = self.count[1, i, k] = self.count[2, i, j] = 1
        self.possible[i, j, :] = self.possible[i, :, k] = self.possible[:, j, k] = False
        self.possible[i, j, k] = True
        self.chosen[0, j, k] = i
        self.chosen[1, i, k] = j
        self.chosen[2, i, j] = k

def encode_sized(size, square):
    square = np.array(square, dtype=int)
    latin = Latin(size)
    chosen = np.array([np.argmax(square[:, :, np.newaxis] == np.arange(size)[np.newaxis, np.newaxis, :], axis=axis) for axis in range(3)])
    num, denom = 0, 1
    while True:
        axis, u, v, ws = latin.decision()
        if axis is None:
            break
        w = chosen[axis, u, v]
        num += ws.index(w)*denom
        denom *= len(ws)
        latin.choose(axis, u, v, w)
    return num

def decode_sized(size, num):
    latin = Latin(size)
    denom = 1
    while True:
        axis, u, v, ws = latin.decision()
        if axis is None:
            break
        if not ws:
            return None, 0
        latin.choose(axis, u, v, ws[num % len(ws)])
        num //= len(ws)
        denom *= len(ws)
    return latin.chosen[2].tolist(), denom

def compress(square):
    size = len(square)
    assert size > 0
    num = encode_sized(size, square)
    while size > 1:
        size -= 1
        square, denom = decode_sized(size, num)
        num += denom
    return '{:b}'.format(num + 1)[1:]

def decompress(bits):
    num = int('1' + bits, 2) - 1
    size = 1
    while True:
        square, denom = decode_sized(size, num)
        num -= denom
        if num < 0:
            return square
        size += 1

total = 0
with open('latin_squares.txt') as f:
    while True:
        square = [list(map(int, l.split(','))) for l in iter(lambda: next(f), '\n')]
        if not square:
            break

        bits = compress(square)
        assert set(bits) <= {'0', '1'}
        assert square == decompress(bits)
        print('Square {}: {} bits'.format(len(square), len(bits)))
        total += len(bits)

print('Total: {} bits = {} bytes'.format(total, total/8.0))

```

Output:

```
Square 1: 0 bits
Square 2: 1 bits
Square 3: 3 bits
Square 4: 8 bits
Square 5: 12 bits
Square 6: 29 bits
Square 7: 43 bits
Square 8: 66 bits
Square 9: 94 bits
Square 10: 122 bits
Square 11: 153 bits
Square 12: 198 bits
Square 13: 250 bits
Square 14: 305 bits
Square 15: 363 bits
Square 16: 436 bits
Square 17: 506 bits
Square 18: 584 bits
Square 19: 674 bits
Square 20: 763 bits
Square 21: 877 bits
Square 22: 978 bits
Square 23: 1097 bits
Square 24: 1230 bits
Square 25: 1357 bits
Total: 10149 bits = 1268.625 bytes

```
> 10 votes

# Answer
# Python 3, 10772 bits (1346.5 bytes)

```
def compress(rows):
    columns = list(zip(*rows))
    size = len(rows)
    symbols = range(size)
    output = size - 1
    weight = 25
    for i in symbols:
        for j in symbols:
            choices = set(rows[i][j:]) & set(columns[j][i:])
            output += weight * sorted(choices).index(rows[i][j])
            weight *= len(choices)
    return bin(output + 1)[3:]

def decompress(bitstring):
    number = int('1' + bitstring, 2) - 1
    number, size = divmod(number, 25)
    size += 1
    symbols = range(size)
    rows = [[None] * size for _ in symbols]
    columns = [list(column) for column in zip(*rows)]
    for i in symbols:
        for j in symbols:
            choices = set(symbols) - set(rows[i]) - set(columns[j])
            number, index = divmod(number, len(choices))
            rows[i][j] = columns[j][i] = sorted(choices)[index]
    return rows

```

Takes 0.1 seconds to compress and decompress the combined test cases.

Verify the score on Ideone.
> 7 votes

# Answer
# MATLAB, ~~3'062.5~~ 2'888.125 bytes

This approach just ditches the last row and the last column of the square, and converts each entry into words of a certain bit depth. The bit depth is chosen minimal for the given size square. (Suggestion by @KarlNapf) These words are just appended to each other. Decompression is just the reverse.

The sum for all the test cases is 23'105 bits or 2'888.125 bytes. (Still holds for the updated test cases, as the size of my outputs is only dependent of the size of the input.)

```
function bin=compress(a)
%get rid of last row and column:
s=a(1:end-1,1:end-1);
s = s(:)';
bin = [];
%choose bit depth:
bitDepth = ceil(log2(numel(a(:,1))));
for x=s;
    bin = [bin, dec2bin(x,bitDepth)];
end
end

function a=decompress(bin)
%determine bit depth
N=0;
f=@(n)ceil(log2(n)).*(n-1).^2;
while f(N)~= numel(bin)
    N=N+1;
end
bitDepth = ceil(log2(N));
%binary to decimal:
assert(mod(numel(bin),bitDepth)==0,'invalid input length')
a=[];
for k=1:numel(bin)/bitDepth;
    number = bin2dec([bin(bitDepth*(k-1) + (1:bitDepth)),' ']);
    a = [a,number];
end
n = sqrt(numel(a));
a = reshape(a,n,n);
disp(a)
%reconstruct last row/column:
n=size(a,1)+1;
a(n,n)=0;%resize
%complete rows:
v = 0:n-1;
for k=1:n
    a(k,n) = setdiff(v,a(k,1:n-1));
    a(n,k) = setdiff(v,a(1:n-1,k));
end
end

```
> 6 votes

# Answer
# , 2444 bytes

Relies on the builtin `A.` to convert to and from a permutation of integers \[0, n) and a permutation index.

### Compress, 36 bytes

```
({:a.)joinstring<@(a.{~255&#.inv)@A.

```

The input is a 2d array representing the Latin square. Each row is converted to a permutation index, and that index is converted to a list of base 255 digits and replaced with an ASCII value. Each string is then joined using the ASCII character at 255.

### Decompress, 45 bytes

```
[:(A.i.@#)[:(_&,(255&#.&x:);._1~1,255&=)u:inv

```

Splits the input string at each ASCII value of 255, and parse each group as base 255 digits. Then using the number of groups, create a list of integers \[0, length) and permute it according to each index and return it as a 2d array.
> 3 votes

# Answer
# Python, ~~6052~~ ~~4521~~ 3556 bytes

`compress` takes the square as a multiline string, just like the examples and returns a binary string, whereas `decompress` does the opposite.

```
import bz2
import math

def compress(L):
 if L=="0":
  C = []
 else:
  #split elements
  elems=[l.split(',') for l in L.split('\n')]
  n=len(elems)
  #remove last row and col
  cropd=[e[:-1] for e in elems][:-1]
  C = [int(c) for d in cropd for c in d]

 #turn to string
 B=map(chr,C)
 B=''.join(B)

 #compress if needed
 if len(B) > 36:
  BZ=bz2.BZ2Compressor(9)
  BZ.compress(B)
  B=BZ.flush()

 return B

def decompress(C):

 #decompress if needed
 if len(C) > 40:
  BZ=bz2.BZ2Decompressor()
  C=BZ.decompress(C)

 #return to int and determine length
 C = map(ord,C)
 n = int(math.sqrt(len(C)))
 if n==0: return "0"

 #reshape to list of lists
 elems = [C[i:i+n] for i in xrange(0, len(C), n)]

 #determine target length
 n = len(elems[0])+1
 L = []
 #restore last column
 for i in xrange(n-1):
  S = {j for j in range(n)}
  L.append([])
  for e in elems[i]:
   L[i].append(e)
   S.remove(e)
  L[i].append(S.pop())
 #restore last row
 L.append([])
 for col in xrange(n):
  S = {j for j in range(n)}
  for row in xrange(n-1):
   S.remove(L[row][col])
  L[-1].append(S.pop())
 #merge elements
 orig='\n'.join([','.join([str(e) for e in l]) for l in L])
 return orig

```

Remove the last row+column and zip the rest.

* Edit1: well `base64` does not seem necessary
* Edit2: now converting the chopped table into a binary string and compress only if necessary
> 2 votes

# Answer
## Python3 - 3,572 3,581 bytes

```
from itertools import *
from math import *

def int2base(x,b,alphabet='0123456789abcdefghijklmnopqrstuvwxyz'):
    if isinstance(x,complex):
        return (int2base(x.real,b,alphabet) , int2base(x.imag,b,alphabet))
    if x<=0:
        if x==0:return alphabet[0]
        else:return  '-' + int2base(-x,b,alphabet)
    rets=''
    while x>0:
        x,idx = divmod(x,b)
        rets = alphabet[idx] + rets
    return rets

def lexicographic_index(p):
    result = 0
    for j in range(len(p)):
        k = sum(1 for i in p[j + 1:] if i < p[j])
        result += k * factorial(len(p) - j - 1)
    return result

def getPermutationByindex(sequence, index):
    S = list(sequence)
    permutation = []
    while S != []:
        f = factorial(len(S) - 1)
        i = int(floor(index / f))
        x = S[i]
        index %= f
        permutation.append(x)
        del S[i]
    return tuple(permutation)

alphabet = "abcdefghijklmnopqrstuvwxyz"

def dataCompress(lst):
    n = len(lst[0])

    output = alphabet[n-1]+"|"

    for line in lst:
        output += "%s|" % int2base(lexicographic_index(line), 36)

    return output[:len(output) - 1]

def dataDeCompress(data):
    indexes = data.split("|")
    n = alphabet.index(indexes[0]) + 1
    del indexes[0]

    lst = []

    for index in indexes:
        if index != '':
            lst.append(getPermutationByindex(range(n), int(index, 36)))

    return lst

```

`dataCompress` takes a list of integer tuples and returns a string.

`dateDeCompress` takes a string and returns a list of integer tuples.

In short, for each line, this program takes that lines permutation index and saves it in base 36. Decompressing takes a long time with big inputs but compression is really fast even on big inputs.

## Usage:

`dataCompress([(2,0,1),(1,2,0),(0,1,2)])`

result: `c|4|3|0`

`dataDeCompress("c|4|3|0")`

result: `[(2, 0, 1), (1, 2, 0), (0, 1, 2)]`
> 2 votes

# Answer
# Python 3, 1955 bytes

Yet another one that uses permutation indices...

```
from math import factorial

test_data_name = 'latin_squares.txt'

def grid_reader(fname):
    ''' Read CSV number grids; grids are separated by empty lines '''
    grid = []
    with open(fname) as f:
        for line in f:
            line = line.strip()
            if line:
                grid.append([int(u) for u in line.split(',') if u])
            elif grid:
                yield grid
                grid = []
    if grid:
        yield grid

def show(grid):
    a = [','.join([str(u) for u in row]) for row in grid]
    print('\n'.join(a), end='\n\n')

def perm(seq, base, k):
    ''' Build kth ordered permutation of seq '''
    seq = seq[:]
    p = []
    for j in range(len(seq) - 1, 0, -1):
        q, k = divmod(k, base)
        p.append(seq.pop(q))
        base //= j
    p.append(seq[0])
    return p

def index(p):
    ''' Calculate index number of sequence p,
        which is a permutation of range(len(p))
    '''
    #Generate factorial base code
    fcode = [sum(u < v for u in p[i+1:]) for i, v in enumerate(p[:-1])]

    #Convert factorial base code to integer
    k, base = 0, 1
    for j, v in enumerate(reversed(fcode), 2):
        k += v * base
        base *= j
    return k

def encode_latin(grid):
    num = len(grid)
    fbase = factorial(num)

    #Encode grid rows by their permutation index,
    #in reverse order, starting from the 2nd-last row
    codenum = 0
    for row in grid[-2::-1]:
        codenum = codenum * fbase + index(row)
    return codenum

def decode_latin(num, codenum):
    seq = list(range(num))
    sbase = factorial(num - 1)
    fbase = sbase * num

    #Extract rows
    grid = []
    for i in range(num - 1):
        codenum, k = divmod(codenum, fbase)
        grid.append(perm(seq, sbase, k))

    #Build the last row from the missing element of each column
    allnums = set(seq)
    grid.append([allnums.difference(t).pop() for t in zip(*grid)])
    return grid

byteorder = 'little'

def compress(grid):
    num = len(grid)
    codenum = encode_latin(grid)
    length = -(-codenum.bit_length() // 8)
    numbytes = num.to_bytes(1, byteorder)
    codebytes = codenum.to_bytes(length, byteorder)
    return numbytes + codebytes

def decompress(codebytes):
    numbytes, codebytes= codebytes[:1], codebytes[1:]
    num = int.from_bytes(numbytes, byteorder)
    if num == 1:
        return [[0]]
    else:
        codenum = int.from_bytes(codebytes, byteorder)
        return decode_latin(num, codenum)

total = 0
for i, grid in enumerate(grid_reader(test_data_name), 1):
    #show(grid)
    codebytes = compress(grid)
    length = len(codebytes)
    total += length
    newgrid = decompress(codebytes)
    ok = newgrid == grid
    print('{:>2}: Length = {:>3}, {}'.format(i, length, ok))
    #print('Code:', codebytes)
    #show(newgrid)

print('Total bytes: {}'.format(total))

```

**output**

```
 1: Length =   1, True
 2: Length =   1, True
 3: Length =   2, True
 4: Length =   3, True
 5: Length =   5, True
 6: Length =   7, True
 7: Length =  11, True
 8: Length =  14, True
 9: Length =  20, True
10: Length =  26, True
11: Length =  33, True
12: Length =  41, True
13: Length =  50, True
14: Length =  61, True
15: Length =  72, True
16: Length =  84, True
17: Length =  98, True
18: Length = 113, True
19: Length = 129, True
20: Length = 147, True
21: Length = 165, True
22: Length = 185, True
23: Length = 206, True
24: Length = 229, True
25: Length = 252, True
Total bytes: 1955

```
> 2 votes

# Answer
# Java, 2310 bytes

We convert each row of the square to a number representing which lexicographic permutation it is using factoradic numbers, also known as a factorial number system, which is useful for numbering permutations.

We write the square to a binary file where the first byte is the size of the square, and then each row has one byte for the number of bytes in the binary representation of a Java BigInteger, followed by the bytes of that BigInteger.

To reverse the process and decompress the square we read the size back and then each BigInteger, and use that number to generate each row of the square.

```
import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Latin {
    public static void main(String[] args) {
        if (args.length != 3) {
            System.out.println("java Latin {-c | -d} infile outfile");
        } else if (args[0].equals("-c")) {
            compress(args[1], args[2]);
        } else if (args[0].equals("-d")) {
            decompress(args[1], args[2]);
        } else {
            throw new IllegalArgumentException(
                "Invalid mode: " + args[0] + ", not -c or -d");
        }
    }

    public static void compress(String filename, String outname) {
        try (BufferedReader br = Files.newBufferedReader(Paths.get(filename))) {
            try (OutputStream os =
                    new BufferedOutputStream(new FileOutputStream(outname))) {
                String line = br.readLine();
                if (line == null) return;
                int size = line.split(",").length;
                if (size > 127) throw new ArithmeticException(
                    "Overflow: square too large");
                Permutor perm = new Permutor(size);
                os.write((byte) size); // write size of square

                do {
                    List<Integer> nums = Arrays.stream(line.split(","))
                        .map(Integer::new)
                        .collect(Collectors.toList());
                    byte[] bits = perm.which(nums).toByteArray();
                    os.write((byte) bits.length); // write length of bigint
                    os.write(bits); // write bits of bigint
                } while ((line = br.readLine()) != null);
            }
        } catch (IOException e) {
            System.out.println("Error compressing " + filename);
            e.printStackTrace();
        }
    }

    public static void decompress(String filename, String outname) {
        try (BufferedInputStream is =
                new BufferedInputStream(new FileInputStream(filename))) {
            try (BufferedWriter bw =
                    Files.newBufferedWriter(Paths.get(outname))) {
                int size = is.read(); // size of latin square
                Permutor perm = new Permutor(size);
                for (int i = 0; i < size; ++i) {
                    int num = is.read(); // number of bytes in bigint
                    if (num == -1) {
                        throw new IOException(
                            "Unexpected end of file reading " + filename);
                    }
                    byte[] buf = new byte[num];
                    int read = is.read(buf); // read bits of bigint into buf
                    if (read != num) {
                        throw new IOException(
                            "Unexpected end of file reading " + filename);
                    }
                    String row = perm.nth(new BigInteger(buf)).stream()
                        .map(Object::toString)
                        .collect(Collectors.joining(","));
                    bw.write(row);
                    bw.newLine();
                }
            }
        } catch (IOException e) {
            System.out.println("Error reading " + filename);
            e.printStackTrace();
        }
    }
}

```

Permutor is adapted from a class I wrote a few years ago to work with permutations:

```
import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import java.math.BigInteger;
import static java.math.BigInteger.ZERO;
import static java.math.BigInteger.ONE;

public class Permutor {
    private final List<Integer> items;

    public Permutor(int n) {
        items = new ArrayList<>();
        for (int i = 0; i < n; ++i) items.add(i);
    }

    public BigInteger size() {
        return factorial(items.size());
    }

    private BigInteger factorial(int x) {
        BigInteger f = ONE;
        for (int i = 2; i <= x; ++i) {
            f = f.multiply(BigInteger.valueOf(i));
        }
        return f;
    }

    public List<Integer> nth(long n) {
        return nth(BigInteger.valueOf(n));
    }

    public List<Integer> nth(BigInteger n) {
        if (n.compareTo(size()) > 0) {
            throw new IllegalArgumentException("too high");
        }
        n = n.subtract(ONE);
        List<Integer> perm = new ArrayList<>(items);
        int offset = 0, size = perm.size() - 1;
        while (n.compareTo(ZERO) > 0) {
            BigInteger fact = factorial(size);
            BigInteger mult = n.divide(fact);
            n = n.subtract(mult.multiply(fact));
            int pos = mult.intValue();
            Integer t = perm.get(offset + pos);
            perm.remove((int) (offset + pos));
            perm.add(offset, t);
            --size;
            ++offset;
        }
        return perm;
    }

    public BigInteger which(List<Integer> perm) {
        BigInteger n = ONE;
        List<Integer> copy = new ArrayList<>(items);
        int size = copy.size() - 1;
        for (Integer t : perm) {
            int pos = copy.indexOf(t);
            if (pos < 0) throw new IllegalArgumentException("invalid");
            n = n.add(factorial(size).multiply(BigInteger.valueOf(pos)));
            copy.remove((int) pos);
            --size;
        }
        return n;
    }
}

```

Usage:

With a Latin square in `latin.txt`, compress it:

```
java Latin -c latin.txt latin.compressed

```

And decompress it:

```
java Latin -d latin.compressed latin.decompressed

```
> 1 votes

---
Tags: code-challenge, compression
---


# Question
Title: Shortest simple regex matching a binary word
# Task

Define a *simple regex* as a non-empty regular expression consisting only of

* characters `0` and `1`,
* grouping parentheses `(` and `)`,
* one-or-more repetition quantifier `+`.

Given a non-empty string of `0`s and `1`s, your program should find the shortest simple regex matching the **full** input string. (That is, when matching a simple regex, pretend it’s bookended by `^` and `$`.) If there are multiple shortest regexes, print any or all of them.)

, so the shortest submission (in bytes) wins.

# Test cases

```
1 -> 1
00 -> 00 or 0+
010 -> 010
1110 -> 1+0
01010 -> 01010
0101010 -> 0(10)+ or (01)+0
011111 -> 01+
10110110 -> (1+0)+
01100110 -> (0110)+ or (01+0)+
010010010 -> (010)+
111100111 -> 1+001+ or 1+0+1+
00000101010 -> 0+(10)+ or (0+1)+0
1010110001 -> 1(0+1+)+ or (1+0+)+1

```

# Answer
# Pyth, 20 bytes

```
hf.x}z:zT1Zy*4"()01+

```

This takes approximately 30 seconds to run, so it needs to be run offline.

Explanation:

```
hf.x}z:zT1Zy*4"()01+
                        Implicit: z is the input string.
              "()01+    "()01+"
            *4          Repeated 4 times
           y            All subsequences in length order
hf                      Output the first one such that
      :zT1              Form all regex matches of z with the candidate string
    }z                  Check if the input is one of the strings
  .x      Z             Discard errors

```

I'm not completely sure that every shortest string is a subsequence of "()01+" * 4, but 4 can be increased to 9 at no byte cost if needed.
> 2 votes

# Answer
## JavaScript (ES6), ~~488~~ 341 bytes

```
s=>[s.replace(/(.)\1+/g,'$1+'),...[...Array(60)].map((_,i)=>`(${(i+4).toString(2).slice(1)})+`),...[...Array(1536)].map((_,i)=>`${i>>10?(i>>8&1)+(i&2?'+':''):''}(${i&1}${i&4?i>>4&1:i&16?'+':''}${i&8?''+(i>>7&1)+(i&64?i>>5&1:i&32?'+':''):''})+${i&512?(i>>8&1)+(i&2?'+':''):''}`)].filter(r=>s.match(`^${r}$`)).sort((a,b)=>a.length-b.length)[0]

```

Explanation: Since six regexes can express all possible binary words, and the longest two are nine characters long, it suffices to check those and all shorter regexes. One candidate is obviously the string with "run length encoding" (i.e. all digit runs replaced with appropriate `+`s), but also strings with one set of `()`s need to be checked. I generate 1596 such regexes (this includes duplicates and useless regexes but they'll just be eliminated) and test all 1597 to see which is the shortest match. The generated regexes fall into two types: `\(\d{2,5}\)\+` (60 regexes) and `(\d\+?)?\(\d[\d+]?(\d[\d+]?)?\)(\d\+?)?` (1536 regexes as I avoid generating regexes with both leading and trailing digit).
> 9 votes

# Answer
# Pyth - ~~31~~ ~~30~~ 29 bytes

Brute force! Can probably golf the iterator a little.

```
 f=+Yf.x:zjY"^$")Z^"10+()"T1Y

```

Test Suite.
> 2 votes

# Answer
# Ruby, 109 bytes

It's the boring brute force approach. Works because no regex ever need be longer than 9 characters (as Neil notes) and no individual character needs to be repeated more than 4 times (trying it with `'01()+'.chars*9` made my CPU unhappy).

```
10.times{|i|('01()+'.chars*4).combination(i).map{|s|begin
/^#{s*''}$/=~$*[0]&&[puts(s*''),exit]
rescue
end}}

```

```
$ for word in `grep -Po '^\S+' test_cases.txt`; do nice -n20 ruby sre.rb $word; done
1
0+
010
1+0
01010
0(10)+
01+
(1+0)+
(01+0)+
(010)+
1+0+1+
0+(10)+
1(0+1+)+

```
> 1 votes

# Answer
# Python 3, 186 bytes

I'm investigating whether there is an approach to this problem besides brute-forcing, but here is a Python brute-force solution for now.

```
import re,itertools
def a(b):
 for z in range(10):
  for i in itertools.combinations("01()+"*4,z):
   j=''.join(i)
   try:
    if re.fullmatch(j,b)and len(j)<=len(b):return j
   except:1

```
> 1 votes

---
Tags: code-golf, regular-expression, metagolf, search
---


title: Minimum Scalar Product

text:
# Question
Title: Minimum Scalar Product
**Minimum Scalar Product**

The inspiration for this code golf problem is from Google's code jam competition. The premise behind the problem is, given the input of two vectors of varying lengths, find the minimum possible scalar. A scalar can be found using the following formula:

```
x1 * y1 + x2 * y2 + ... + xn * yn

```

The problem, however, is that multiple values for the scalar can be found depending on the order of the numerals in the input case (seen below). Your goal is to determine the minimum possible scalar integer solution by plugging in the input case numbers into the equation and solving for it. You may use every number in the input only once, and must use all of the numbers.

Allow me to provide an example with the following vectors.

**Input**

```
3
1 3 -5
-2 4 1

```

**Output**

```
-25

```

The first integer on the line represents the number of numbers, n, in each vector. In this case, we have three numbers in each vector.

The number n may vary with each test case, but there will always be two vectors.

In the example input, the minimum scalar product would be -25.

```
(-5 * 4) + (1 * 1) + (3 * -2) = 25

```

**Rules**

* You may only use each integer in both vectors once.
* You must use all integers in the vectors.
* Your output must only include the final product
* I'll select the solution with the least amount of code, which follows all of the specifications listed above, in any language!

> Hint: You don't need to brute force this problem, unless it makes your code shorter. There is a specific method involved in finding the minimum spanning scalar :).

# Answer
> 8 votes
# Jelly, 6 bytes

```
ṢṚ×Ṣ}S

```

Try it online!

Using brute force is equally short:

```
Œ!×S€Ṃ

```

### How it works

```
ṢṚ×Ṣ}S  Main link. Arguments: u (vector), v (vector)

Ṣ       Sort the components of u.
 Ṛ      Reverse.
   Ṣ}   Sort the components of v.
  ×     Multiply the results, element by element.
     S  Compute the sum of the products.

```

# Answer
> 6 votes
## Seriously, 6 bytes

```
,SR,S*

```

Try it online!

Explanation:

```
,SR,S*
,SR     input first vector, sort, reverse
   ,S   input second vector, sort
     *  dot product

```

# Answer
> 5 votes
# APL, 15 bytes

```
{+/⍺[⍒⍺]×⍵[⍋⍵]}

```

This is a dyadic function that accepts arrays on the left and right and returns an integer. It uses the same approach as my Julia answer: dot product of the sorted arrays, one descending and one ascending.

Try it here

# Answer
> 5 votes
# MATL, 6 bytes

Code:

```
SiSP*s

```

My first MATL answer :)

Explanation:

```
S       # Sort the first array
 iS     # Take the second array and sort it
   P    # Flip the array
    *   # Multiply both arrays with each other
     s  # Sum of the result

```

Try it online!

# Answer
> 4 votes
# Mathematica, ~~30~~ 17 bytes

*-13 bytes by murphy*

```
Sort@#.-Sort@-#2&

```

Function, input is vector1(list),vector2(list) Several revisions:

```
Plus@@(Sort@#*Reverse@Sort@#2)&(*me*)
Total[Sort@#*Reverse@Sort@#2]&
Sort@#.Reverse@Sort@#2&        (*alephalpha*)
Sort@#.Sort[#2,#>#2&]&         (*murphy*)
Sort@#.SortBy[#2,-#&]          (*me*)
Sort@#.-Sort@-#2&              (*murphy*)

```

# Answer
> 3 votes
# Julia, ~~32~~ 25 bytes

```
x->y->-sort(-x)⋅sort(y)

```

This is an anonymous function that accepts two arrays and returns an integer. To call it, assign it to a variable and do `f(x)(y)`.

For inputs *x* and *y*, we simply compute the dot product of *x* sorted in reverse order with *y* sorted. We get *x* in reverse sorted order by negating all values, sorting, then negating again.

Saved 7 bytes thanks to Dennis!

# Answer
> 2 votes
# Pyth - ~~14~~ 8 bytes

I think I figured out the trick.

```
s*VSQ_SE

```

Try it online here.

# Answer
> 2 votes
# Perl 6, ~~33~~ 30 bytes

```
{sum @^a.sort Z*@^b.sort.reverse}

```

# Answer
> 2 votes
# Javascript ES6, 69 bytes

```
a=>b=>a.sort((x,y)=>x-y).map((x,y)=>i+=b.sort((x,y)=>y-x)[y]*x,i=0)|i

```

Wow, this is way too long.

# Answer
> 1 votes
# CJam, 11 Bytes

```
q~$\$W%.*:+

```

Try it online!

# Answer
> 1 votes
# Python, 139 bytes

```
def mdp(n, a, b):
    a = list(reversed(sorted(a)))
    b = sorted(b)
    res = sum([a[i] * b[i] for i in range(len(a))])
    return res

```

# Answer
> 1 votes
# C++, 124 bytes

```
#include<algorithm>
int m(int*a,int*b,int n){std::sort(a,a+n);std::sort(b,b+n);int r=0;while(--n>=0)r+=a[n]**b++;return r;}

```

ungolfed:

```
#include<algorithm>
int m(int*a,int*b,int n){
 std::sort(a,a+n);
 std::sort(b,b+n);
 int r=0;
 while(--n>=0)
  r+=a[n]*(*b++);
return r;
}

```

At first i used `std::greater<int>()` for the sort in `b` but just reversing the order in the summation is easier.

# Answer
> 1 votes
# Haskell, 59 bytes

```
import Data.List
v?u=sum$zipWith(*)(sort v)$reverse$sort u

```

# Answer
> 0 votes
# RETURN, 29 bytes

```
[{␆␃}\{␆}␄␅[¤¥][×␌]#}␁[¤][+]#]

```

`Try it here.`

Replace any `␆␃␄␇` with their unprintable counterparts.

Anonymous lambda that leaves result on stack2. Usage:

```
""{1 3 0 5-}""{0 2- 4 1}[{␆␃}\{␆}␄␅[¤¥][×␌]#}␁[¤][+]#]!

```

# Explanation

```
[                                 ]  lambda
 {␆␃}                              sort and reverse first stack
       \{␆}                         sort second stack
            ␄␅                     transpose and flatten
               [  ][  ]#             while loop
                ¤¥                     check if 2 items exist in stack
                    ×                  if so, multiply top 2 items
                     ␌                 and push to stack2
                        }␁          switch to stack2
                           [¤][+]#   sum stack2

```

# Answer
> 0 votes
# J, 14 bytes

```
+/@(*|.)&(/:~)

```

Uses the same principle as the others.

## Explanation

```
+/@(*|.)&(/:~)  Input: x on LHS and y on RHS
        &(/:~)  Sort both x and y
     |.         Reverse the sorted y
    *           Multiply the sorted x and reversed sorted y elementwise
+/@             Reduce the products using addition and return

```

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


title: Runs of Digits in Pi

text:
# Question
Title: Runs of Digits in Pi
Your goal is to output the strictly increasing sequence of consecutive, identical digits of pi (π). Each term in the sequence must be one digit longer than the previous. So `3` (0th digit of pi) is the first time a run of digits occurs (length 1). The next to occur is `33` (digits 24 and 25 of pi). Of course, this sequence requires the digits of pi to be **in base 10**.

**The ones known so far**, and the first six all occur within the first 800 digits:

```
3
33
111
9999
99999
999999
3333333
44444444
777777777
6666666666
... (not in first 2 billion digits)

```

Note that the consecutive nines all occur together, in the same run, so if the next larger run you found happened to be 1000 consecutive `0`s, this would fill in *multiple* terms of the sequence.

I have not found any more terms with my program. I know there are no more terms within the first 50000 digits or more. My program was taking too long with 500000 digits, so I gave up.

**Reference Implementation**

**You may:**

* Output the sequence forever
* Take an integer `n` and find the first `n` numbers in the sequence
* Take an integer `n` and find the numbers in the sequence contained in the first `n` digits of pi.

Make sure to specify which one your code does. The number `n` may be zero or one indexed.

Inspired by this mathoverflow question.

# Answer
# Mathematica, 85 bytes

```
FromDigits/@DeleteDuplicatesBy[Join@@Subsets/@Split@RealDigits[Pi,10,#][[1]],Length]&

```

Anonymous function. Takes *n* as input, and returns the elements of the sequence in the first *n* digits of π. Output is in the form of `{0, 3, 33, 111, ...}`.
> 5 votes

# Answer
## Python 2, 110 bytes

```
n=input()
x=p=7*n|1
while~-p:x=p/2*x/p+2*10**n;p-=2
l=m=0
for c in`x`:
 l=l*(p==c)+1;p=c
 if l>m:m=l;print p*l

```

The maximum number of digits to check is taken as from stdin. 10,000 digits finishes in about 2s with PyPy 5.3.

**Sample Usage**

```
$ echo 10000 | pypy pi-runs.py
3
33
111
9999
99999
999999

```

---

### Something Useful

```
from sys import argv
from gmpy2 import mpz

def pibs(a, b):
  if a == b:
    if a == 0:
      return (1, 1, 1123)
    p = a*(a*(32*a-48)+22)-3
    q = a*a*a*24893568
    t = 21460*a+1123
    return (p, -q, p*t)
  m = (a+b) >> 1
  p1, q1, t1 = pibs(a, m)
  p2, q2, t2 = pibs(m+1, b)
  return (p1*p2, q1*q2, q2*t1 + p1*t2)

if __name__ == '__main__':
  from sys import argv
  digits = int(argv[1])

  pi_terms = mpz(digits*0.16975227728583067)
  p, q, t = pibs(0, pi_terms)

  z = mpz(10)**digits
  pi = 3528*q*z/t

  l=m=0
  x=0
  for c in str(pi):
   l=l*(p==c)+1;p=c
   if l>m:m=l;print x,p*l
   x+=1

```

I've switched from Chudnovsky to Ramanujan 39 for this. Chudnovsky ran out of memory on my system shortly after 100 million digits, but Ramanujan made it all the way to 400 million, in only about 38 minutes. I think this is another case were slower growth rate of terms wins out in the end, at least on a system with limited resources.

**Sample Usage**

```
$ python pi-ramanujan39-runs.py 400000000
0 3
25 33
155 111
765 9999
766 99999
767 999999
710106 3333333
22931752 44444444
24658609 777777777
386980421 6666666666

```

---

### Faster Unbounded Generators

The reference implementation given in the problem description is interesting. It uses an unbounded generator, taken directly from the paper Unbounded Spigot Algorithms for the Digits of Pi. According to the author, the implementations provided are "deliberately obscure", so I decided to make fresh implementations of all three algorithms listed by the author, without deliberate obfuscation. I've also added a fourth, based on Ramanujan #39.

```
try:
  from gmpy2 import mpz
except:
  mpz = long

def g1_ref():
  # Leibniz/Euler, reference
  q, r, t = mpz(1), mpz(0), mpz(1)
  i, j = 1, 3
  while True:
    n = (q+r)/t
    if n*t > 4*q+r-t:
      yield n
      q, r = 10*q, 10*(r-n*t)
    q, r, t = q*i, (2*q+r)*j, t*j
    i += 1; j += 2

def g1_md():
  # Leibniz/Euler, multi-digit
  q, r, t = mpz(1), mpz(0), mpz(1)
  i, j = 1, 3
  z = mpz(10)**10
  while True:
    n = (q+r)/t
    if n*t > 4*q+r-t:
      for d in digits(n, i>34 and 10 or 1): yield d
      q, r = z*q, z*(r-n*t)
    u, v, x = 1, 0, 1
    for k in range(33):
      u, v, x = u*i, (2*u+v)*j, x*j
      i += 1; j += 2
    q, r, t = q*u, q*v+r*x, t*x

def g2_md():
  # Lambert, multi-digit
  q, r, s, t = mpz(0), mpz(4), mpz(1), mpz(0)
  i, j, k = 1, 1, 1
  z = mpz(10)**49
  while True:
    n = (q+r)/(s+t)
    if n == q/s:
      for d in digits(n, i>65 and 49 or 1): yield d
      q, r = z*(q-n*s), z*(r-n*t)
    u, v, w, x = 1, 0, 0, 1
    for l in range(64):
      u, v, w, x = u*j+v, u*k, w*j+x, w*k
      i += 1; j += 2; k += j
    q, r, s, t = q*u+r*w, q*v+r*x, s*u+t*w, s*v+t*x

def g3_ref():
  # Gosper, reference
  q, r, t = mpz(1), mpz(180), mpz(60)
  i = 2
  while True:
    u, y = i*(i*27+27)+6, (q+r)/t
    yield y
    q, r, t, i = 10*q*i*(2*i-1), 10*u*(q*(5*i-2)+r-y*t), t*u, i+1

def g3_md():
  # Gosper, multi-digit
  q, r, t = mpz(1), mpz(0), mpz(1)
  i, j = 1, 60
  z = mpz(10)**50
  while True:
    n = (q+r)/t
    if n*t > 6*i*q+r-t:
      for d in digits(n, i>38 and 50 or 1): yield d
      q, r = z*q, z*(r-n*t)
    u, v, x = 1, 0, 1
    for k in range(37):
      u, v, x = u*i*(2*i-1), j*(u*(5*i-2)+v), x*j
      i += 1; j += 54*i
    q, r, t = q*u, q*v+r*x, t*x

def g4_md():
  # Ramanujan 39, multi-digit
  q, r, s ,t = mpz(0), mpz(3528), mpz(1), mpz(0)
  i = 1
  z = mpz(10)**3511
  while True:
    n = (q+r)/(s+t)
    if n == (22583*i*q+r)/(22583*i*s+t):
      for d in digits(n, i>597 and 3511 or 1): yield d
      q, r = z*(q-n*s), z*(r-n*t)
    u, v, x = mpz(1), mpz(0), mpz(1)
    for k in range(596):
      c, d, f = i*(i*(i*32-48)+22)-3, 21460*i-20337, -i*i*i*24893568
      u, v, x = u*c, (u*d+v)*f, x*f
      i += 1
    q, r, s, t = q*u, q*v+r*x, s*u, s*v+t*x

def digits(x, n):
  o = []
  for k in range(n):
    x, r = divmod(x, 10)
    o.append(r)
  return reversed(o)

```

**Notes**

Above are 6 implementations: the two reference implementations provided by the author (denoted `_ref`), and four that compute terms in batches, generating multiple digits at once (`_md`). All implementations have been confirmed to 100,000 digits. When choosing batch sizes, I chose values that slowly lose precision over time. For example, `g1_md` generates 10 digits per batch, with 33 iterations. However, this will only produce ~9.93 correct digits. When precision runs out the check condition will fail, triggering an extra batch to be run. This seems to be more performant than slowly gainly extra, unneeded precision over time.

* **g1 (Leibniz/Euler)**
An extra variable `j` is kept, representing `2*i+1`. The author does the same in the reference implementation. Calculating `n` separately is far simpler (and less obscure), because it uses the current values of `q`, `r` and `t`, rather than the next.
* **g2 (Lambert)**
The check `n == q/s` is admittedly quite lax. That should read `n == (q*(k+2*j+4)+r)/(s*(k+2*j+4)+t)`, where `j` is `2*i-1` and `k` is `i*i`. At higher iterations, the `r` and `t` terms become increasingly less significant. As is, it's good for the first 100,000 digits, so it's probably good for all. The author provides no reference implementation.
* **g3 (Gosper)**
The author conjectures that it is unnecessary to check that `n` will not change in subsequent iterations, and that it only serves to slow the algorithm. While probably true, the generator is holding onto ~13% more correct digits than it has currently generated, which seems somewhat wasteful. I've added the check back in, and wait until 50 digits are correct, generating them all at once, with a noticable gain in performance.
* **g4 (Ramanujan 39)**
Calculated as
Unfortunately, `s` doesn't zero out, due to the initial (3528 ÷) composition, but it's still significantly faster than g3. Convergence is ~5.89 digits per term, 3511 digits are generated at a time. If that's a bit much, generating 271 digits per 46 iterations is also a decent choice.

**Timings**

Taken on my system, for purposes of comparison only. Times are listed in seconds. If a timing took longer than 10 minutes, I didn't run any further tests.

```
            |  g1_ref |  g1_md  |  g2_md  |  g3_ref |  g3_md  |  g4_md
------------+---------+---------+---------+---------+---------+--------
    10,000  |  1.645  |  0.229  |  0.093  |  0.312  |  0.062  |  0.062
    20,000  |  6.859  |  0.937  |  0.234  |  1.140  |  0.250  |  0.109
    50,000  |  55.62  |  5.546  |  1.437  |  9.703  |  1.468  |  0.234
   100,000  |  247.9  |  24.42  |  5.812  |  39.32  |  5.765  |  0.593
   200,000  |  2,158  |  158.7  |  25.73  |  174.5  |  33.62  |  2.156
   500,000  |    -    |  1,270  |  215.5  |  3,173  |  874.8  |  13.51
 1,000,000  |    -    |    -    |  1,019  |    -    |    -    |  58.02

```

It's interesting that `g2` eventually overtakes `g3`, despite a slower rate of convergence. I suspect this is because the operands grow at a significantly slower rate, winning out in the long run. The fastest implmentation `g4_md` is approximately 235x faster than the `g3_ref` implmentation on 500,000 digits. That said, there's still a significant overhead to streaming digits in this way. Calculating all digits directly using Ramanujan 39 (python source) is approximately 10x as fast.

**Why not Chudnovsky?**

The Chudnovsky algorithm requires a full precision square root, which I'm honestly not sure how to work in - assuming it could be at all. Ramanujan 39 is somewhat special in this regard. However, the method does seem like it might be conducive to Machin-like formulas, such as those used by y-cruncher, so that might be an avenue worth exploring.
> 4 votes

# Answer
# Python 2, 298 bytes

Note, the code for generating pi is taken from the OP's implementation.

```
def p():
 q,r,t,j=1,180,60,2
 while 1:
  u,y=3*(3*j+1)*(3*j+2),(q*(27*j-12)+5*r)//(5*t)
  yield y
  q,r,t,j=10*q*j*(2*j-1),10*u*(q*(5*j-2)+r-y*t),t*u,j+1
p=p()
c=r=0
d=[0]
while 1:
 t=p.next()
 if t==d[len(d)-1]:d.append(t)
 else:d=[t]
 if len(d)>r:r=len(d);print"".join([`int(x)`for x in d])
 c+=1

```

My first attempt at golfing in Python. Outputs the sequence forever.
> 3 votes

# Answer
# Haskell, 231 bytes

```
import Data.List
g(q,r,t,k,n,l)|4*q+r-t<n*t=n:g(10*q,10*(r-n*t),t,k,div(10*(3*q+r))t-10*n,l)|0<1=g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)
p=nubBy(\x y->length x==length y).concatMap inits.group$g(1,0,1,1,3,3)

```

This uses the Unbounded Spigot Algorithms for the Digits of Pi by Jeremy Gibbons, 2004. The result is `p`. Technically, it should support infinite output sequences, but that may take a while (and is bounded by your memory).
> 3 votes

# Answer
# Python 3.5, ~~278~~ 263 bytes:

```
import decimal,re;decimal.getcontext().prec=int(input());D=decimal.Decimal;a=p=1;b,t=1/D(2).sqrt(),1/D(4)
for i in[1]*50:z=(a+b)/2;b=(a*b).sqrt();t-=p*(a-z)**2;a=z;p*=2;pi=(z*2)**2/(4*t);i=0;C=lambda r:re.search(r'(\d)\1{%s}'%r,str(pi))
while C(i):print(C(i));i+=1

```

This takes in `n` as an input for the first `n` digits of `π` and then outputs the members of the sequence in those first `n` digits. Now, this uses Python's built in decimal module to go beyond Python's floating-point limitations, and then sets the precision, or epsilon, to however much the user inputs. Then, to calculate `π`, this goes through 50 iterations using the efficient Gausse-Legendre algorithm, since the algorithm apparently doubles the number of correct digits each time, and therefore, in 50 iterations, we can get up to `2^50` or `1,125,899,906,842,624` correct digits. Finally, after the calculations are done, it uses a regular expression with string formatting in a `while` loop to find and print `re` match objects (which I hope is okay) for all continuous, recurring digits 1 digit longer than in the previous iteration through the loop.

I was able to use this algorithm to successfully and accurately calculate `π` up to `10,000,000` (ten million) digits, which took about 4 hours and 12 minutes to complete. The following was the final output:

```
<_sre.SRE_Match object; span=(0, 1), match='3'>
<_sre.SRE_Match object; span=(25, 27), match='33'>
<_sre.SRE_Match object; span=(154, 157), match='111'>
<_sre.SRE_Match object; span=(763, 767), match='9999'>
<_sre.SRE_Match object; span=(763, 768), match='99999'>
<_sre.SRE_Match object; span=(763, 769), match='999999'>
<_sre.SRE_Match object; span=(710101, 710108), match='3333333'>

```

So, I can confidently say that the 8th number in the sequence does not even occur within the first 10 million digits! `π` is one random number...
> 3 votes

---
Tags: code-golf, sequence, pi
---