# Question
Title: What is the Probability that a Knight Stays on Chessboard?
Given the size of the chess board and initial position of the knight, calculate the probability that after `k` moves the knight will be inside the chess board.

Note:

* The knight makes its all 8 possible moves with equal probability.
* Once the knight is outside the chess board it cannot come back inside.

**Input**

Inputs are comma separated in the form:

```
l,k,x,y

```

where `l` is the length and width of the chess board, `k` is the number of moves the knight will make, `x` is the x-position of the initial position of the knight, and `y` is the y-position of the initial position of the knight. Note that `0,0` is the bottom-left corner of the board and `l-1,l-1` is the top-right corner of the board.

**Algorithm:**

Start with the initial coordinates of the knight. Make all possible moves for this position and multiply these moves with their probability, for each move recursively call the function continue this process till the terminating condition is met. Terminating condition is if the knight is outside the chess board, in this case return 0, or the desired number of moves is exhausted, in this case return 1.

As we can see that the current state of the recursion is dependent only on the current coordinates and number of steps done so far. Therefore we can memorize this information in a tabular form.

### Credit

This challenge is originally from a blog post of crazyforcode.com published under the CC BY-NC-ND 2.5 IN licence. It was slightly modified to make it a bit more challenging.

# Answer
# Pyth, 38 bytes

```
M?smcgtGd8fq5sm^-Fk2C,TH^UhQ2G1g@Q1>Q2

```

Try it online: Demonstration

### Explanation:

```
                                        implicit: Q = evaluated input
M                                       define a function g(G,H): //G=depth, H=current cell
                         UhQ              the list [0,1,...,Q[0]-1]
                        ^   2             Cartesian product, gives all cells
          f                               filter for numbers numbers T, which satisfy:
                    C,TH                    zip(T,H)
              m                             map the two pairs k to:
                -Fk                           their difference
               ^   2                          squared
             s                              sum (distance squared)
           q5                               == 5
   m                                      map each valid cell d to:
     gtHd                                   g(G-1,d)
    c    8                                  divided by 8
  s                                       return sum
 ?                           G          if G > 0 else
                              1           return 1

                               g@Q1>Q2  call g(Q[1],Q[2:]) and print

```
> 10 votes

# Answer
# Ruby 134

```
->l,m,x,y{!((r=0...l)===x&&r===y)?0:m<1?1:(0..7).map{|i|a,b=[1,2].rotate i[2]
P[l,m-1,x+a*(i[0]*2-1),y+b*(i[1]*2-1)]/8.0}.inject(:+)}

```

Try it online: http://ideone.com/ZIjOmP

The equivalent non-golfed code:

```
def probability_to_stay_on_board(board_size, move_count, x, y)
  range = 0...board_size
  return 0 unless range===x && range===y
  return 1 if move_count < 1

  possible_new_locations = (0..7).map do |i|
    dx, dy = [1,2].rotate i[2]
    dx *= i[0]*2-1
    dy *= i[1]*2-1

    [x+dx, y+dy]
  end

  possible_new_locations.map do |new_x, new_y|
    probability_to_stay_on_board(board_size, move_count-1, new_x, new_y) / 8.0
  end.inject :+
end

```
> 8 votes

# Answer
# Matlab, ~~124~~ 119

Exactly implements the described algorithm.

I was able to shorten it by 5 bytes with some help of @sanchises, thanks!

```
function s=c(l,k,x,y);m=zeros(5);m([2,4,10,20])=1/8;s(l,l)=0;s(l-y,x+1)=1;for i=1:k;s=conv2(s,m+m','s');end;s=sum(s(:))

```

Expanded:

```
function s=c(l,k,x,y);
    m=zeros(5);
    m([2,4,10,20])=1/8;
    s(l,l)=0;s(l-y,x+1)=1;
    for i=1:k;
        s=conv2(s,m+m','s');
    end;
    s=sum(s(:))

```

Old version

```
function s=c(l,k,x,y);
    m =zeros(5);m([1:3,5,8,10:12]*2)=1/8;
    s=zeros(l);
    s(l-y,x+1)=1;
    for i=1:k
        s=conv2(s,m,'s');
    end
    s=sum(s(:));

```
> 5 votes

# Answer
# Haskell - 235

Implements a function `f` with parameters `l k x y`

```
import Data.List
g[]=[]
g((a,b):r)=[(a+c,b+d)|(c,d)<-zip[-2,-1,1,2,-2,-1,1,2][1,2,-2,-1,-1,-2,2,1]]++g r
h _ 0 a=a
h l a b=h l(a-1)$filter(\(a,b)->(elem a[0..l])&&(elem b[0..l]))$g b
f l k x y=(sum$map(\x->1.0) (h l k [(x,y)]))/(8**k)

```
> 5 votes

# Answer
# Mathematica - 137

```
q = # {1, 2} & /@ Tuples[{-1, 1}, 2]
q = Reverse /@ q~Union~q
g[l_, k_, x_, y_] :=

 Which[
  k < 1,
  1,

  !0 <= x < l || ! 0 <= y < l,
  0,

  0<1,
  Mean[g[l, k - 1, x + #[[1]], y + #[[2]]] & /@ q]
]

```

Usage:

```
g[5,5,1,2]

```

Output:

```
9/64

```
> 5 votes

# Answer
# MATLAB - 106

```
function s=c(l,k,x,y);m(5,5)=0;m([2,4,10,20])=1/8;s=ones(l);for i=1:k;s=conv2(s,m+m','s');end;s=s(l-y,x+1)

```

Improves on @flawr's solution by being more MATLAB-y.

## Expanded:

```
function s=c(l,k,x,y)
    m(5,5)=0;
    m([2,4,10,20])=1/8;
    s=ones(l);
    for i=1:k
        s=conv2(s,m+m','s');
    end
    s=s(l-y,x+1)

```
> 2 votes

# Answer
## \>\<\> - 620 (not counting whitespace)

Initial stack should be `l,k,x,y`

```
{:a2*0p   v
vp0*3a*}:{<
>{1+&a3*0g}v                   >          >       >          >~~01-01-v             >          >       >          >~~01-01-v             >          >       >          >~~01-01-v             >          >       >          >~~01-01-v
           >&1-:&?!v>:@@:@@:0(?^:a2*0g1-)?^2-$:0(?^:a2*0g1-)?^1-      >}}$:@@:@@:0(?^:a2*0g1-)?^2-$:0(?^:a2*0g1-)?^1+      >}}$:@@:@@:0(?^:a2*0g1-)?^2+$:0(?^:a2*0g1-)?^1-      >}}$:@@:@@:0(?^:a2*0g1-)?^2+$:0(?^:a2*0g1-)?^1+      >}}$:@@:@v
v1         ^}       ^!?=g0*3a:~~}}<      +2v?)-1g0*2a:v?(0:$+1v?)-1g0*2a:v?(0:@@:@@:$}}<      -2v?)-1g0*2a:v?(0:$+1v?)-1g0*2a:v?(0:@@:@@:$}}<      +2v?)-1g0*2a:v?(0:$-1v?)-1g0*2a:v?(0:@@:@@:$}}<-2      v?)-1g0*2a:v?(0:$-1v?)-1g0*2a:v?(0:@<
>a3*0g=   ?^\      &              ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <
\         :{/
v                  >~{~l2,&0
>@:0(?v:a2*0g1-)?v$:0(?v:a2*0g1-)?v1>@~~+l1=?v
      >          >     >          >0^        >&,n;

```

Test it out
> 1 votes

---
Tags: code-golf, chess
---


# Question
Title: Write the longest sentence using keywords of a programming language
**As the title said, the challenge is to write the longest sentence by only using the keywords of 1 programming language.**

For instance, using the keywords of C++, it is possible to write this sentence:

> do not try this float

What can you come up with?

# Answer
> 34 votes
## Mathematica ~~100~~ 80 unique words

Here's a start. All standard words in Mathematica begin with upper case. this includes `I`, the square root of negative 1.

On Sunday, And For All Times-- Assuming, On Opening Clear Dynamic Interactive Notebooks For Setting Contours, I Do Not Translate Missing Blue Arrays Which Span Temporary, Asynchronous, And Invisible Characters, Nor Do I Remove Undefined Arrowheads With Editable And Sound Outer Orange Roots Which Magnify Shallow Names Together With False Attributes (Because Most Axes Split Full Inner Kernels In Reverse Order)-- And While I Animate Undefined Quiet Ticks, I Begin With Tolerance And Operate On All Manual Matrices, Interleaving Circle With Cylinder, Boxed Skeleton With Compiled Cuboid, Red Cross With Nearest Timing Pattern, And Join Repeated Unique White Links With Heads ...

---

In case anyone is interested, here are 500+ words recognized by Mathematica (no additional libraries required). They are not all keywords, but experienced Mathematica programers will know and have used just about all of them.

---

{Abort, Above, Abs, Accumulate, Accuracy, AddTo, After, Alignment, All, Alternatives, Analytic, And, Animate, Animator, Annotation, Annuity, Antialiasing, Antisymmetric, Apart, Appearance, Append, Apply, Array, Arrays, Arrow, Arrowheads, Assert, Assuming, Assumptions, Asynchronous, Attributes, Automatic, Axes, Axis, Back, Background, Backslash, Backward, Band, Baseline, Because, Beep, Before, Begin, Below, Binarize, Binomial, Blank, Blend, Block, Blur, Bookmarks, Booleans, Bottom, Bounds, Boxed, Break, Button, Byte, Cancel, Cap, Cases, Cashflow, Catch, Ceiling, Cell, Cells, Censoring, Center, Character, Characters, Check, Checkbox, Chop, Circle, Clear, Clip, Clock, Close, Closed, Closing, Coarse, Coefficient, Collect, Colon, Colorize, Column, Commonest, Compile, Compiled, Complement, Complex, Compose, Composition, Compress, Condition, Cone, Congruent, Conjunction, Connect, Constant, Constants, Context, Contexts, Continue, Contours, Control, Convergents, Convolve, Copyable, Correlation, Cot, Count, Covariance, Cross, Cumulant, Cup, Curl, Cycles, Cylinder, Darker, Date, Debug, Decrement, Default, Defer, \[Degree\], Deinitialization, Deletable, Delimiter, Delimiters, Denominator, Deploy, Deployed, Depth, Derivative, Diagonal, Dialog, Diamond, Differences, Dilation, Dimensions, Direction, Directive, Disjunction, Disk, Dispatch, Display, Distribute, Distributed, Dithering, Divide, Dividers, Divisible, Divisors, Do, Dot, Down, Drop, Dynamic, Editable, Eigenvalues, Element, Eliminate, Empty, Enabled, Encode, End, Enter, Epilog, Equal, Equivalent, Evaluator, Except, Exists, Exit, Expand, Expectation, Exponent, Export, Expression, Extract, Factor, Factorial, Fail, False, File, Filling, Find, First, Fit, Flat, Flatten, Floor, Fold, Font, For, Forward, Frame, Front, Full, Function, Gather, General, Generic, Get, Graph, Graphics, Greater, Grid, Hash, Head, Heads, Histogram, Hold, Hue, Hyperlink, Hyphenation, I, Identity, If, Image, Implies, In, Increment, Inherited, Inner, Input, Insert, Inset, Install, Integer, Integers, Integral, Integrate, Interactive, Interleaving, Interval, Invisible, Item, Join, Joined, Kernels, Label, Labeled, Large, Larger, Last, Latitude, Launch, Left, Legended, Length, Less, Level, Lighting, Limit, Line, Links, List, Listable, Listen, Literal, Locked, Log, Longest, Longitude, Magnification, Magnify, Majority, Manipulate, Manual, Map, Masking, Material, Matrices, Maximize, Mean, Median, Medium, Menu, Mesh, Message, Messages, Method, Minimize, Minors, Missing, Modal, Mode, Modular, Module, Modulus, Moment, Monday, Monitor, Most, Mouseover, Multinomial, Multiplicity, Multiselection, Names, Nearest, Needs, Negative, Nest, Next, None, Nor, Norm, Normal, Normalize, Not, Notebook, Notebooks, Null, Number, Numerator, Off, Offset, On, Opacity, Open, Opening, Operate, Optional, Options, Or, Order, Ordering, Orderless, Orthogonalize, Out, Outer, Over, Overflow, Paclet, Pane, Panel, Paneled, Parallelize, Parameter, Parenthesize, Part, Partition, Paste, Path, Pattern, Pause, Permutations, Permute, Perpendicular, \[Pi\], Piecewise, Pivoting, Placed, Placeholder, Plain, Play, Plot, Plus, Point, Polygon, Polynomials, Position, Positive, Power, Precedence, Precedes, Precision, Prefix, Prepend, Previous, Print, Probability, Projection, Prolog, Properties, Property, Proportion, Protect, Protected, Pruning, Put, Pyramid, Quantile, Quantity, Quartics, Quartiles, Queueing, Quiet, Quit, Quotient, Radon, Random, Range, Raster, Rasterize, Rational, Rationals, Read, Real, Reap, Record, Rectangle, Reduce, Refine, Refresh, Reinstall, Release, Remove, Removed, Repeated, Replace, Resampling, Rescale, Residue, Resolve, Rest, Return, Reverse, Riffle, Right, Root, Roots, Rotate, Round, Row, Rule, Saturday, Save, Saveable, Scale, Scaled, Scan, Scrollbars, Select, Selection, Sequence, Series, Set, Setbacks, Setter, Setting, Shading, Shallow, Share, Sharpen, Short, Show, Sidebar, Sign, Signature, Simplify, Skeleton, Skip, Slot, Smaller, Socket, Solve, Sound, Sow, Spacer, Spacings, Span, Speak, Sphere, Splice, Split, Square, Stack, Star, Streams, String, Stub, Subfactorial, Subgraph, Subscripted, Subset, Subtract, Sum, Superset, Surd, Syntax, Table, Take, Tally, Temporary, Text, Texture, Therefore, Thread, Threshold, Through, Ticks, Times, Timing, Together, Toggle, Toggler, Tolerance, Tooltip, Top, Total, Trace, Tracers, Translate, Transpose, True, Tube, Tuples, Undefined, Underlined, Underscript, Unequal, Uninstall, Union, Unique, Unitize, Unset, Up, Variables, Vertical, Wedge, Weights, Which, While, Whitespace, With, Word, Write}

# Answer
> 46 votes
# C++, 25 unique words, 28 total

> True friend, do goto register for this new short public class for private auto operator (while inline, return this signed template), else break & void this long volatile union.

# Answer
> 19 votes
While making sentences is not really my strong suite, here goes nothing -

# Python 20 words

> Finally, continue with import and raise global yield while class lambda is in break and try and print exec pass.

To help with checking, I wrote some code to check whether the words are in the keyword list or not.

```
from keyword import kwlist
from re import findall

def kwcheck(sentence):
    """Check whether all the words of a sentence are Python keywords"""
    words= findall(r'\w+', sentence)
    for word in words:
        if word.lower() not in kwlist:
            return False
    return True, len(words)

if __name__ == '__main__':
    sen= raw_input("Enter your sentence: ")
    print kwcheck(sen)

```

# Answer
> 15 votes
## The Importance of Education

### -- by A. Coder Guy (written in Python)

```
Continue class, except if class is not for you.
With no class, raise and assert!  Or yield, pass,
and break.  Try and continue!  Or - finally - return from class.

```

# Answer
> 12 votes
### Common Lisp

```
:In :Common :Lisp :a :keyword :is :simply :a :symbol :which :has :the :KEYWORD :home :package :which :is :true :of :all :symbols :starting :with :a :colon :so :you :can :construct :arbitrarily :long :sentences. :Do :I :win?

```

This, for example:

```
(every #'keywordp '(:In :Common :Lisp :a :keyword :is :simply :a :symbol :which :has :the :KEYWORD :home :package :which :is :true :of :all :symbols :starting :with :a :colon :so :you :can :construct :arbitrarily :long :sentences. :Do :I :win?))

```

Evaluates to `T`

See http://www.lispworks.com/documentation/HyperSpec/Body/26\_glo\_k.htm

# Answer
> 9 votes
## c#, 17 words

This looks like pretty reasonable technical mumbo-jumbo.
I guess it can be extended a bit.
`foreach` is a bit stretching the rules.
Used this keyword list.

> Try explicit operator, in case implicit string foreach virtual struct is as unsafe as this volatile lock.

# Answer
> 9 votes
# Factor - 109

> "Take my-world and with happy? make items to-do. Pause. Self not happy?"
>
> "Yes\<\<."
>
> "From oldies?"
>
> "Yes\>\>. Self sad."
>
> "Haversin, listen, each and every formula become oldies. Become not sad, do-something greater-from-last. Or . My-arch self is\_gold\<\<. Change-is\_gold. Go-back where your\_event\_mask\<\< make happy? future. Fulfill promise of self. Remember-definition, light are-copies-of happy?"
>
> "Sweetest-day near\>\> me?. Handle-me, handle-me. Sad self. Home not near\>\>. Home not near\>\> at all. Out-of-memory. Sad self, old\<\< self. Most near\>\> ones left self long ago."
>
> "Haversin, change-known self. No sad, Haversin. Become happy? Forget what\<\< keep self from happy? My-arch self want\>\> self be\> not sad. Before leave, remember-error."
>
> "Not remember-error! Error not! My-array has-entry? not of error! Leave error!"
>
> "Smart-if remember-error."

A lot of these are stretches, but it somewhat tells a story, so it makes up for that.

# Answer
> 9 votes
# Applescript, 30 words

I never thought I would post an Applescript answer on PPCG, but given Applescript's natural language design philosophy, it is perfectly suited for this question.

I'm not much of a wordsmith, so here's one just to get us started, but I fully expect others will easily beat this:

```
Beneath the eighth error, my third script is ignoring the sixth local copy
of the fourth transaction to the seventh property whose reference is given
to repeat every tenth second.

```

This is constructed just from Applescript's keywords, which are:

### Keywords

> about above after against and "apart from" around as "aside from" at back before beginning behind below beneath beside between but by considering contain contains continue copy div does eighth else end equal equals error every exit FALSE fifth first for fourth from front get given global if ignoring in "instead of" into is it its last local me middle mod my ninth not of on onto or "out" of over prop property put ref reference repeat return returning script second set seventh since sixth some tell tenth that the then third through thru timeout times to transaction TRUE try until use where while whose with without

The following may or may not be considered valid for this challenge:

### Built-in classes and properties

> alias application boolean centimetres centimeters character class contents constant "cubic centimetres" "cubic centimeters" "cubic feet" "cubic inches" "cubic metres" "cubic meters" "cubic yards" date "date string" day "degrees Celsius" "degrees Fahrenheit" "degrees Kelvin" feet file frontmost gallons grams id inches integer item kilograms kilometres kilometers length list litres liters metres meters miles month name number ounces paragraph "POSIX file" "POSIX path" pounds quarts "quoted form" real record reference rest reverse "RGB color" running script "square feet" "square kilometres" "square kilometers" "square metres" "square meters" "square miles" "square yards" text time "time string" "unit types" version weekday word yards year

### Built-in Commands

> activate "ASCII character" "ASCII number" beep "choose application" "choose color" "choose file" "choose file name" "choose folder" "choose from list" "choose remote application" "choose URL" "clipboard info" "close access" copy count "current date" delay "display alert" "display dialog" "display notification" "do shell script" get "get eof" "get volume settings" "info for" launch "list disks" "list folder" "load script" "localized string" log "mount volume" offset "open for access" "open location" "path to" "path to resource" "random number" read round run "run script" say "scripting components" set "set eof" "set the clipboard to" "set volume" "store script" summarize "system attribute" "system info" "the clipboard" "time to GMT" write

### Considering/Ignoring attributes

> case diacriticals hyphens "numeric strings" punctuation "white space"

# Answer
> 8 votes
# Shakespeare

### 44 words, 28 unique

Yes, all of these words really have keyword-level significance in Shakespeare. Shakespeare character names, normal nouns and adjectives are also a core part of the language, but I thought they'd bloat the list too much for this exercise.

> You must listen to your heart to enter your mind: the heart shall recall the difference between the exit and the return, to let you remember you are your art, and so you are the product of yourself and an act better than yourself.

# Answer
> 7 votes
## **Ruby, 41 words**

> True self, do not begin class break, end class break, ensure class break, redo and redo class break, retry class break, rescue class break, or yield class break, until next class end (or next class module or next class return), or else!

That's just using words listed as actual keywords. There are a lot of other words that act like keywords because they're methods of the kernel or instance methods of Class.

A cheesier approach would start

> Do not def "alias","begin","break",...

# Answer
> 4 votes
C++.

A lot of repeated words, but a borderline sensible sentence:

```
If this volatile friend false and do return unsigned public union template throw union
template goto void for false friend not using class, and try switch for new protected
union using true friend, or else catch long, private break using this public operator
switch for explicit union using new virtual friend if union for this friend not long and
true.

```

Aka: If this moody girl won't sign the marriage license, throw away the license and find a nice new girl--and if that doesn't work out, just try a...virtual union over the "public operator switch".

Oh, as far as exact number of words goes, sorry but I'm too lazy to count.

# Answer
> 3 votes
# Python, 48 words

> class, try (if lambda is in class) and continue as if in break from global import and raise yield for return from exec; else, while lambda is not in class, continue with print import except for def, finally pass 'assert elif' or else del is not for class.

**This contains every keyword in `keyword.kwlist`**

I think some explanation is required here: This sentence is said to a school class that is currently in some place called `exec`. In the class, there are amongst others two people named `lambda` and `def`. `def` should pass the `assert elif` test because otherwise the DEL (German ice hockey league) is nothing for the class.

# Answer
> 2 votes
# ECMA

A bit of broken English due to the fact that ECMA reserved words contain neither conjunctions nor more than one conjugation of verb. It's really an imperative language!

> Do try this new typeof case, with this default catch function.
>
> In this case, break in with this switch. If catch break, return with this new switch; finally throw in with this new function.

# Answer
> 2 votes
# Perl - several entries

when given tied package untie, unpack and unlink until open, redo each package (link, pack and bind or tie) or dump if not open; next, read map, write state, reverse and return system. (28 distinct words)

bless (not hex) my rand-y flock; continue until values accept no sin; study END times, accept sleep and die; CHECK keys and close each crypt lock. (25 distinct words)

tell our next caller: "use fork and pipe; push, break, delete, kill, and DESTROY." (13 distinct words)

# Answer
> 1 votes
# Haskell (~29-ish)

> In case of foreign type, import data module; where as for all (`forall`) in qualified class, if hiding, then do default (let in, deriving instance of data family where qualified, otherwise data instance of type family); else type in fix (`infix`).

In Haskell, `data family` is a separate keyword from `data`, likewise with `type family`, and `deriving instance` is separate from `deriving` and `instance`. I am using `forall` as two words (counting only one), `where as` as one (counting two), and `infix` as two (counting one).

---
Tags: code-challenge
---


title: XKCD Bracket Probabilities

text:
# Question
Title: XKCD Bracket Probabilities
Today's XKCD is a sports-tournament style bracket, where the contestants are well-known names, put into groups of possibly confusing names.

Give the probability that a given contestant will win the entire tournament, based on each contestant in a given round having an equal chance of winning that round.

### Input

The name of a contestant.

* XKCD likes to use all upper case, but you may use whatever case makes sense for you or make your input case insensitive.
* You may assume all input names are valid.
* `Jeff Gordan` is probably a misspelling of `Jeff Gordon`. You may choose to accept either or both of these.
* Some names include punctuation, e.g. `H. G. Wells` and `Joseph Gordon-Levitt`. You may choose to accept names with or without punctuation (or both). The above without punctuation would be `H G Wells` and `Joseph Gordon Levitt`
* Similarly, you may choose to accept either `Beyoncé` or `Beyonce` or both
* The `Mister/Fred Astaire/Rogers` line is a bit odd. For this one, you must accept all of the following: `Fred Rogers`, `Mister Rogers` and `Fred Astaire`

### Output

The probability of the given contestant winning the whole tournament, in rational form (e.g. `1/64`)

### Examples

* Louis Armstrong will potentially play in 6 rounds, each with two contestants, so he has a 1/64 chance of winning.
* Alan Rickman will potentially play in 7 rounds, the first with 3 contestants and the rest with 2 contestants, so he has a 1/192 chance of winning.

To save you the effort of typing in all the names from the image, explainXKCD already has them tabulated. I've also dumped them to this pastebin.

Note the winning probabilities in the explainXKCD are wrong - they are twice as big as they should be because they are presumably forgetting the final round. Thanks for pointing this out @Geobits.

# Answer
> 6 votes
# CJam, 161 bytes

```
1'/l_"FRE"#\_'É#)\2b626%536%"òazíF.?§·»ùßóÿ÷ýÿÿ»×ï_ÿÿ¿ß÷ä¿ûïÿÏÅÿ¿ÿÿ~ÿþÿýó½ïÿþþ/ïþÿ®þü¾ùÿ®÷/"256b2b2*<1-,"ãÍÕý*ÔÞ)ð^sV? Ìöî²\ÅlÕáS{Á"260b5b=5,Z6t=2+1\?4?32*

```

This is a full program that expects uppercase input, with punctuation and accents exactly as shown in the pastebin.

Try it online in the CJam interpreter.

### How it works

```
1'/      e# Push a 1 and a slash.
l        e# Read a line of input from STDIN.
_"FRE"#  e# Push 0 if the input starts with "FRE" and a truthy value otherwise.
\_'É#)   e# Push 1 if the input doesn't contain "É" and a falsy value otherwise.

         e# Now we hash the input:
\2b      e#     Apply base 2 conversion to turn the input into an integer.
626%536% e#     Take that integer modulo 626, then modulo 536.

"òazíF.?§·»ùßóÿ÷ýÿÿ»×ï_ÿÿ¿ß÷ä¿ûïÿÏÅÿ¿ÿÿ~ÿþÿýó½ïÿþþ/ïþÿ®þü¾ùÿ®÷/"256b2b2*

         e# Convert the string from base 256 to base 2 and repeat it.
         e# The resulting array, [1 1 1 1 0 0 1 0 0 ...], contains a 0 at index X
         e# if and only if there is a possible input with hash X.

<        e# Keep the binary values before the index of the input hash.
<1-,     e# Count the number of zeroes.

"ãÍÕý*ÔÞ)ð^sV?  Ìöî²\ÅlÕáS{Á"260b5b

         e# Convert the string from base 260 to base 5.
         e# The resulting array, [2 2 2 2 2 0 4 4 0 0 ...], contains a diffrent
         e# integer for every different probability. The input with the lowest hash
         e# corresponds to the first index, the one with the highest to the last.

=        e# Retrieve the integer corresponding to the input.
5,Z6t=   e# Retrieve the corresponding element from [0 1 2 6 4].
2+       e# Add two.
1\?      e# Select the result from above or 1 for BEYONCÉ.
4?       e# Select the result from above or 4 for and FRED.
32*      e# Multiply by 32.

```

---
Tags: code-golf, kolmogorov-complexity, rational-numbers, probability-theory
---


title: Generalized integer casting in Python

text:
# Question
Title: Generalized integer casting in Python
### Background

I have a string in Python which I want to convert to an integer. Normally, I would just use `int`:

```
>>> int("123")
123

```

Unfortunately, this method is not very robust, as it only accepts strings that match `-?[0-9]+` (after removing any leading or trailing whitespace). For example, it can't handle input with a decimal point:

```
>>> int("123.45")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid literal for int() with base 10: '123.45'

```

And it *certainly* can't handle this:

```
>>> int("123abc?!")

```

On the other hand, exactly this behavior can be had without any fuss in Perl, PHP, and even the humble QBasic:

```
INT(VAL("123abc"))   ' 123

```

### Question

Here's my shortest effort at this "generalized `int`" in Python. It's 50 bytes, assuming that the original string is in `s` and the result should end up in `i`:

```
n="";i=0
for c in s:
 n+=c
 try:i=int(n)
 except:0

```

Fairly straightforward, but the `try`/`except` bit is ugly and long. Is there any way to shorten it?

### Details

Answers need to do all of the following:

* Start with a string in `s`; end with its integer value in `i`.
* The integer is the first run of digits in the string. Everything after that is ignored, including other digits if they come after non-digits.
* Leading zeros in the input are valid.
* Any string that does not start with a valid integer has a value of `0`.

The following features are *preferred*, though not required:

* A single `-` sign immediately before the digits makes the integer negative.
* Ignores whitespace before and after the number.
* Works equally well in Python 2 or 3.

(Note: my code above meets all of these criteria.)

### Test cases

```
"0123"   -> 123
"123abc" -> 123
"123.45" -> 123
"abc123" -> 0
"-123"   -> -123 (or 0 if negatives not handled)
"-1-2"   -> -1 (or 0 if negatives not handled)
"--1"    -> 0
""       -> 0

```

# Answer
# 40 bytes

```
import re;i=int("0"+re.split("\D",s)[0])

```

and you can do negatives for 8 characters more:

```
import re;i=int((re.findall("^-?\d+",s)+[0])[0])

```
> 4 votes

# Answer
# Python ~~2, 47~~, 46

It's not as short as using regex, but I thought it was entertainingly obscure.

```
i=int(('0%sx'%s)[:~len(s.lstrip(str(1<<68)))])

```

-1 due to KSab – `str` with some large integer works better than the repr operator since it does not put an `L` on the end.
> 6 votes

---
Tags: code-golf, tips, python
---


title: Save the Geese from Extinction

text:
# Question
Title: Save the Geese from Extinction
The species of geese known as *Alex A* are known for residing in triangular grids consisting of 64 cells:

<sup>(Picture taken from this unrelated Project Euler problem.)</sup>

We'll label each cell with the numbers `0` to `63` starting from the top row and then moving from left to right on each row below that. So the top cell is `0` and the bottom-right cell is `63`.

Each cell has three borders. We can label each border in the form `a,b` where `a` and `b` are the numbers of the cells that share that border. For instance, the border between cell `0` and `2` would be called `0,2` or `2,0` (it doesn't matter what order you put them in).

The labeling system for borders on the very edge of the grid are different, since the cells on the edge of the grid have a border that they don't share with other cells. If a border is only part of one cell, we will use the letter `X`. For instance, the three borders of cell `0` are `0,2`, `0,X`, and `0,X`.

Some of the cells contain *geese*. However, these geese will be killed by evil foxes (that come from outside the borders of the grid) if you don't protect them. And if all the geese die then BrainSteel will be sad. Therefore we will write a program that builds fences around the geese to protect them from the foxes. The geese should exist in a **single** fully enclosed polygon of fences. Our fence budget is quite low so use the least number of fences possible.

**Input Description**

A list of numbers, comma separated, from `0` to `63`, representing the cells that contain geese. Example:

```
6,12

```

**Output Description**

A list of borders that need to have fences built on them to protect the geese successfully. This should be the smallest number of fences possible. Example:

```
5,6 6,7 11,12 12,13

```

# Answer
# C#, 530 bytes

Complete C# program, takes input as a single line from STDIN, and outputs a single line to STDOUT, with a trailing " ".

This is rather long... and has way too much x/y/z repetition, but I've not been able to reduce it to anything sensible thus far, and have an exam in 2 hours, might come back to this tomorrow.

```
using Q=System.Console;class P{static void Main(){int q=9,w=0,e=9,r=0,t=9,u=0,i=0,x=0,y=0,z=0,p=0;System.Action V=()=>{z=(int)System.Math.Sqrt(i);p=(x=i-z*z)%2;x/=2;y=(++z*z--+~i)/2;},W=()=>{Q.Write(i+","+(x<0|y++<0|z>7?"X":""+(z*z+2*x+1-p))+" ");};foreach(var g in Q.ReadLine().Split(',')){i=int.Parse(g);V();q=q>x?x:q;w=w<x?x:w;e=e>y?y:e;r=r<y?y:r;t=t>z?z:t;u=u<z?z:u;}for(i=64;i-->0;){V();if(!(x<q|x>w|y<e|y>r|z<t|z>u))if(p>0){if(y==r)W();if(x++==w)W();x--;if(z--==t)W();}else{if(y--==e)W();if(x--==q)W();x++;if(z++==u)W();}}}}

```

This diagram explains most of what is going on.

Recognize that because we can't have 0-width sections, a "hexagon" is always going to be the cheapest shape (and has the benefit of giving the geese the maximum of space to move in).

The program works by first translating all the input cell indices into x/y/z coords, and finding the min/max of each of x/y/z.

```
z = floor(root(i))
x = floor((i - z^2) / 2)
y = floor((z+1)^2 - i - 1) / 2)
p = (i - z^2) % 2

```

Next, it goes through each cell index, and checking if it fits in the 'hexagon' bound we have described. If it is then it checks if it's on any of the extreme edges of the bounds (i.e. x = xmin, or y = ymax) and adds corresponding edges if it is. It has to work out the index of the edge it's next to. For x and z, we just increment/decrement them however we want, and then use the following formula:

```
i = z^2 + 2*x + (1-p)

```

Notice that the "parity" always changes, and that y is not involved. For y, we don't have to change anything, but the code is a bit of a mess because it has to perform "triangle" bounds checking to detect whether the cell next door should be an "X" or not.

Example solution (Cells with geese just in from the three corners):

```
Input
2,50,62

Output
62,63 61,X 59,X 57,X 55,X 53,X 51,X 50,49 48,X 36,X 35,X 25,X 24,X 16,X 15,X 9,X 8,X 4,X 3,X 2,0 1,X

```

Tidier code with comments:

```
using Q=System.Console;

class P
{
    static void Main()
    {
        int q=9,w=0,e=9,r=0,t=9,u=0, // min/max x/y/z/ (init min high, and max low)
        i=0, // index of cell we are looking at
        x=0,y=0,z=0,p=0; // x,y,z dimension

        System.Action V=()=>
            { // translates the index into x/y/z/p
                z=(int)System.Math.Sqrt(i);
                p=(x=i-z*z)%2; // 'parity'
                x/=2; // see p assignment
                y=(++z*z--+~i)/2; // ~i == -i - 1
            },
            W=()=>
            { // writes out the edge of i, and the cell described by x/z/inverse of p   (the inversion of p handles y +/-)
                Q.Write(i+","+ // write out the edge
                        (x<0|y++<0|z>7?"X":""+(z*z+2*x+1-p)) // either X (if we go out of 'trianlge' bounds), or we translate x/z/inverse of p into an index
                        +" "); // leaves a trailing space (as shown in example output)
            };

        foreach(var g in Q.ReadLine().Split(',')) // for each cell with geese
        {
            i=int.Parse(g); // grab index of cell
            V(); // compute x/y/z/p
            q=q>x?x:q; // sort out mins/maxes
            w=w<x?x:w;
            e=e>y?y:e;
            r=r<y?y:r;
            t=t>z?z:t;
            u=u<z?z:u;

            // code like the above suggests a solution with a couple of arrays would be better...
            // I've not had success with that yet, but maybe in a couple of days I will try again
        }

        for(i=64;i-->0;) // for each cell
        {
            V(); // compute x/y/z/p
            if(!(x<q|x>w|y<e|y>r|z<t|z>u)) // if we are inside the 'hex' bounds
                if(p>0)
                { // x max, y max, z min
                    // these checks check that we are on the extremes of the 'hex' bounds,
                    // and set up the appropriate vars for W calls to put the edges in
                    // must do y first, because W modifies it for us (saves 2 bytes in the next block)
                    if(y==r) // don't need the ++ (can't go out of 'trianlge' bounds)
                        W();
                    if(x++==w)
                        W();
                    x--;
                    if(z--==t)
                        W();
                    //z++; not used again
                }
                else
                { // x min, y min, z max
                    if(y--==e) // do need the -- (used for 'trianlge' bounds checking)
                        W();
                    // y is reset in W, as such
                    if(x--==q)
                        W();
                    x++;
                    if(z++==u)
                        W();
                    //z--; not used again
                }
        }
    }
}

```
> 10 votes

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


title: Packing Wood Pieces

text:
# Question
Title: Packing Wood Pieces
There are two pieces of wood. Both consist of a straight body and some extra blocks below the body. An example piece with extra blocks at (0-indexed) positions 0,4,7,9,10:

```
XXXXXXXXXXX
X   X  X XX

```

The piece can be represented as a `01` binary sequence with the `i`th character showing if there is a block at the `i`th position. The upper example can be represented as `10001001011`.

We can put together two pieces by vertically flipping the second one (and maybe flipping it horizontally too). After the flip(s) we can find an alignment where the two pieces can be put together to have a height of 3.

```
Two example pieces:

XXXXXXXXXXX   XXXXXXXX
X   X  X XX     XXX

Second piece flipped vertically and horizontally:

 XXXXXXXXXXX
 X   X  X XX
  XXX
XXXXXXXX

Pieces put together:

 XXXXXXXXXXX
 XXXXX  X XX
XXXXXXXX

```

The example resulted in a total width of 12 blocks.

You should write a program or function which receives two string as input representing the two pieces and outputs an integer the **minimal achievable width** with a height of 3.

## Input

* Two strings consisting of the characters `0` and `1`.
* Both strings contain at least one character.
* You may choose to receive the two strings as one joined by a single space.

## Output

* A single positive integer, the minimal total width achievable.

## Examples

```
0 0  =>  1

1 0  =>  1

1 1  =>  2

11 111  =>  5

010 0110  =>  5

0010 111  =>  5

00010 11011  =>  6

01010 10101  =>  5

1001 100001  =>  6

1110001100001 1100100101  =>  14

001101010000101 100010110000  =>  16

0010110111100 001011010101001000000  =>  21

0010110111100 001011010101001001100  =>  28

100010100100111101 11100101100010100100000001  =>  27

0010 10111  =>  5

0100 10111  =>  5

0010 11101  =>  5

0100 11101  =>  5

10111 0010  =>  5

10111 0100  =>  5

11101 0010  =>  5

11101 0100  =>  5

```

This is code golf so the shortest entry wins.

# Answer
> 7 votes
# Pyth, ~~37~~ ~~35~~ ~~34~~ ~~32~~ 31 bytes

```
eSX0lM.zff-\1@VhY>eYT*Fm,d_d.z0

```

Takes input newline separated.

Demonstration, Test Harness.

Explanation:

At the high level, for each combination of normal and reversed strings, we shift the second string to the left by a given number of positions, and check for overlaps with the first string. This is repeated until a shift amount with no overlaps is found. That shift amount is added to the first string length, and the result is compared with the second string length. The higher value is printed.

```
eSX0lM.zff-\1@VhY>eYT*Fm,d_d.z0

                            .z     The list of the two input strings.
                       m           Map to
                        ,d_d       The pair of each string and its reverse.
                     *F            Take the cartesisan product of those lists.
         f                         Filter those pairs of a first string and a
                                   second string, possibly reversed,
          -\1                      On the absence of the string "1" in
             @V                    The vectorized intersection (intersection
                                   of 0th position, 1st position, etc.) of
               hY                  the first string and
                 >eYT              the second string without the first T elements.
        f                    0     Starting at 0 and counting upwards, find the
                                   lowest T where the result is truthy.
                                   (where anything passes the inner filter)
    lM.z                           Map the input strings to their lengths.
  X0                               Add the above result to the first entry.
eS                                 Take the maximum of the two values and print.

```

# Answer
> 4 votes
# Pip, ~~72~~ ~~70~~ 48 bytes

```
Fp[aRVa]CP[bRVb]L#a+1{I2NI$+plAE:#$+^pp@1.:0}MNl

```

Takes the two strings as command-line arguments. Formatted, with comments:

```
                     a, b initialized from cmdline args; l is [] (implicit)
F p [aRVa]CP[bRVb]   For each possible pair p of a/reverse(a) with b/reverse(b):
 L #a+1 {            Loop for each potential offset of bottom piece:
  I 2 NI $+p         If no 2's in the sum of p:
   l AE: # $+ ^p     Append the max width of elements of p to l (see below for explanation)
  p@1 .: 0           Append a 0 to bottom piece
 }
MNl                  The answer is min(l); print it (implicit)

```

We're only calculating the overlaps where the bottom piece sticks out to the left, so we need to try it with both top and bottom pieces reversed. Each time through the inner loop, if there are no 2's in the sum, it is a fit; we then tack another zero onto the the end of the bottom piece and try again.

```
   0010
    111
   0121

   0010
   111_
   1120

   0010
  111__
  11110

   0010
 111___
 111010

   0010
111____
1110010

```

To find the total width, we split the elements of `p` into lists of characters and sum. Item-wise operations on uneven-length lists preserve the length of the longer one, so the length of this sum is exactly what we need. (Splitting is necessary because simply summing as numbers will eliminate leading zeros: `$+[0101 10] = 111`, but `$+^[0101 10] = [0 1 1 1]`.)

```
C:\> pip.py woodPacking.pip 0010 111
5

```

# Answer
> 3 votes
# Ruby 127 ~~130~~

This turned out to be *so* long... :(

```
->m,n{[[m,n],[m,n.reverse],[n,m],[n,m.reverse]].map{|u,d|[(0..l=u.size).find{|i|(d.to_i(2)<<i)&u.to_i(2)<1}+d.size,l].max}.min}

```

Tests: http://ideone.com/te8XWk

Readable Ruby:

```
def pack_length piece1, piece2
  min_possible_packed_length = [
    min_packed_length(piece1, piece2),
    min_packed_length(piece1, piece2.reverse),
    min_packed_length(piece2, piece1),
    min_packed_length(piece2, piece1.reverse)
  ].min

  min_possible_packed_length
end

def min_packed_length up_piece, down_piece
  x = up_piece.to_i 2
  y = down_piece.to_i 2

  # find the smallest shift for the piece placed down
  # so that they fit together
  min_packed_shift = (0..up_piece.size).find{|i| (y<<i)&x<1 }

  # min pack length cannot be smaller than any of the
  # two pieces
  [min_packed_shift + down_piece.size, up_piece.size].max
end

```

# Answer
> 1 votes
# JavaScript (*ES6*) 160

Couldn't make shorter ...

```
F=(a,b,c=[...b].reverse(),
K=(a,b,t=a.length)=>{
for(e=i=-1;e&&i++<t;)for(e=j=0;u=b[j];j++)e|=u&a[j+i];
return t<i+j?i+j:t
})=>Math.min(K(a,b),K(a,c),K(b,a),K(c,a))

// test

out=x=>O.innerHTML += x+'\n'

test=[
 ['0', '0', 1],['1', '0', 1],['1', '1', 2],['11', '111', 5]
,['010', '0110', 5],['0010', '111', 5],['0010', '10111', 5]
,['00010', '11011', 6],['01010', '10101', 5],['1001', '100001', 6]
,['1110001100001', '1100100101', 14]
,['001101010000101', '100010110000', 16]
,['0010110111100', '001011010101001000000', 21]
,['0010110111100', '001011010101001001100', 28]
,['100010100100111101', '11100101100010100100000001', 27]
,['0010','10111', 5],['0100','10111', 5]
,['0010','11101', 5],['0100','11101', 5]
,['10111','0010', 5],['10111','0100', 5]
,['11101','0010', 5],['11101','0100', 5]
]

test.forEach(t=>{
  r = F(t[0],t[1]),
  out(
    (r==t[2]?'Ok':'Fail')
    + ' A: '+t[0]+', B: '+t[1]
    + ', Result: '+r + ', Check:  '+t[2])
})
```

```
pre { font-size: 10px }
```

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

---
Tags: code-golf, packing
---


title: Clarence the Slow Typist

text:
# Question
Title: Clarence the Slow Typist
**Introduction**

Clarence is a data entry clerk who works at an internet service provider. His job is to manually enter the IP addresses of all of the ISP's customers into the database. He does this using a keypad which has the following layout:

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

The distance between the centre of horizontally or vertically adjacent keys is exactly one centimetre. For instance, the distance between the centres of `3` and `9` would be two centimetres. The distance between the centres of `3` and `5` would be √2cm. The Pythagoras theorem is sufficient to calculate the distance between any two keys.

Clarence, as you might expect from one who works in an ISP, uses a very slow and inefficient system of typing. He uses a single finger and searches for the key, and then moves his finger to the key, then presses it, and repeats for all of the digits in the number. You might know of this style as the "eagle search system" since the finger searches above the keyboard for the correct key before plunging down for the keypress, like an eagle plunging down for a kill.

For example, here is how Clarence would type out the number `7851`:

1. He starts his finger at `7` and pushes the key.
2. He moves his finger to the right 1cm to `8` and pushes the key.
3. He moves his finger upwards 1cm to `5` and pushes the key.
4. He moves his finger diagonally upwards and left √2cm to `1` and pushes the key.

Therefore the total distance that Clarence moved his finger to type in `7851` is `1 + 1 + √2` which is about 3.41cm.

Your task is to write a program that calculates the distance Clarence must move his finger to type in arbitrary IP addresses.

**Input Description**

Input is a string that will be in the form

`().().().()`

where each `()` is an integer in the range `0` \- `999`. This represents the IP address that Clarence must type in. An example input might be:

`219.45.143.143`

I would also like to point out that inputs such as `0.42.42.42` or `999.999.999.999` are still valid inputs, despite the fact that they are invalid IP addresses. So you don't need to include any IP address verification code in your program.

**Output Description**

Output the distance that Clarence must move his finger in order to type in the specified IP address. Round answers to two decimal places where needed, and use the `cm` unit in your output. The output for the example input is `27.38cm` (1 + √8 + √5 + 2 + 1 + √5 + 3 + 1 + √5 + √13 + 3 + 1 + √5).

# Answer
> 16 votes
# CJam, ~~46~~ ~~44~~ ~~43~~ ~~38~~ ~~37~~ 34 bytes

```
rA,sd`f#3fmd2/2ew::.-::mh:+2mO"cm"

```

*Thanks to @user23013 for suggesting `mh`, which made it possible to save 5 bytes.*

Try it online in the CJam interpreter.

### How it works

```
r     e# Read a token from STDIN.
A,    e# Push [0 1 2 3 4 5 6 7 8 9].
s     e# Stringify: [0 1 2 3 4 5 6 7 8 9] -> "0123456789"
d     e# Cast to Double: "0123456789" -> 123456789.0
`     e# Inspect: 123456789.0 -> "123456789.0"
f#    e# Push the index of each character from the input in "123456789.0".
3fmd  e# Push the quotient and residue of each index divided by 3.
2/    e# Split the resulting array into pairs.
2ew   e# Convert the array of pairs in the array of all overlapping pairs of pair.
::.-  e# Reduce each pair using vectorized difference: [[a b][c d]] -> [a-b c-d]
::mh  e# Reduce each reduced pair to its 2-norm distance: [a b] -> sqrt(aa + bb)
:+    e# Sum all distances.
2mO   e# Round to two decimal places.
"cm"  e# Push "cm".

```

# Answer
> 16 votes
# Pyth, ~~38~~ ~~35~~ 34 bytes

```
+.Rs.aM-M.:m.jF.Dx`ciUTT1b3z2 2"cm

```

Demonstration.

Indexing into the string of a float idea thanks to @Dennis.

Explanation, on the phony input `15.0`:

* First, we take the input. It is implicitly stored in `z`. '15.0'
* We map this list as follows: `m.jF.Dx`ciUTT1k3z`.

+ `UT`: We generate the list `[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]`.
    + `iUTT`: Next, we treat this list as a base 10 number giving us `123456789`.
    + `ciUTT1`: Next, we convert this number to a float by floating point dividing it by 1, giving `123456789.0`.
    + ```: Convert to a string. `'123456789.0'`
    + `x k`: Take the index of the input character in that string. `[0, 4, 9, 10]`.
    + `.D 3`: `.D` is the divmod function, outputing its first input divided and modulo'd by the second input. The second input is 3, here. This gives the physical location of the character on the numpad. `[(0, 0), (1, 1), (3, 0), (3, 1)]`.
    + `.jF`: `.j` is the complex number constructor. `F` applies it to the tuple. `[0j, (1+1j), (3+0j), (3+1j)]`.
* `.: 2`: Now, we take the 2 entry substrings of this list so we can find the pairwise distances. `[[0j, (1+1j)], [(1+1j), (3+0j)], [(3+0j), (3+1j)]]`.
* `-M`: Takes the difference of the two complex numbers. `[(-1-1j), (-2+1j), -1j]`.
* `.aM`: Takes the absolute value of the result. This is the distance between the keypad locations. `[1.4142135623730951, 2.23606797749979, 1.0]`
* `s`: Sum the distances. `4.650281539872885`.
* `.R 2`: Round to 2 decimal places. `4.65`.
* `+ "cm`: Add `'cm'` to the end and print. `4.65cm`.

# Answer
> 7 votes
## PHP - 108 Bytes

```
<?for(;$v=strpos(-.987654321,fgetc(STDIN));$l=$v)$l&&$t+=hypot($l/3%4-$v/3%4,$l%3-$v%3);printf('%.2fcm',$t);

```

Input is taken from stdin. The `-.987654321` sent to the `strpos` function evaluates to `'-0.987654321'` in a string context.

---

**Sample usage:**

```
$ echo 219.45.143.143 | php isp.php
27.38cm

```

# Answer
> 5 votes
## C, ~~192~~ ~~177~~ 159 bytes

Updated version, now complete program using command line argument. At the same time, improved to still be shorter than previous version:

```
#define G c=*a[1]++,c=c>48?c-49:c/2-14,u=c%3,v=c/3
float r;c,u,v,p,q;main(int n,char**a){for(G;*a[1];)p=u,q=v,G,p-=u,q-=v,r+=sqrt(p*p+q*q);printf("%.2fcm",r);}

```

Ungolfed:

```
#include <stdio.h>
#include <math.h>

float r;
int c, u, v, p, q;

int main(int n, char** a) {
    c = *a[1]++;
    c = c > 48 ? c - 49 : c / 2 - 14;
    u = c % 3;
    v = c / 3;
    for ( ; *a[1]; ) {
        p = u;
        q = v;
        c = *a[1]++;
        c = c > 48 ? c - 49 : c / 2 - 14;
        u = c % 3;
        v = c / 3;
        p -= u;
        q -= v;
        r += sqrt(p * p + q * q);
    }

    printf("%.2fcm",r);

    return 0;
}

```

The golfed version uses a preprocessor `#define` to shorten some of the repeated code in the full version.

# Answer
> 3 votes
# JavaScript (*ES6*), 132

I/O via popup. Run the snippet to test (Firefox only)

```
[for(a of prompt(d=''))[p,q,d]=[x=(a=a<'0'?9:-a?a-1:10)%3,y=a/3|0,d!==''?d+Math.sqrt((p-=x)*p+(q-=y)*q):0]],alert(d.toFixed(2)+'cm')
```

# Answer
> 3 votes
# Python 3, 108 bytes

```
L=[x//3*1j+x%3for x in map("123456789.0".find,input())]
print("%.2fcm"%sum(abs(a-b)for a,b in zip(L,L[1:])))

```

Admittedly not very well golfed, but at least it ties with PHP.

# Answer
> 2 votes
# Ruby 135 ~~139~~

```
s=0
gets.chars.each_cons(2).map{|a|i,j=a.map{|e|'123456789.0'.index e}
i&&j&&s+=((i%3-j%3)**2+(i/3-j/3)**2)**0.5}
print s.round(2),'cm'

```

Test it online: http://ideone.com/2CIQa5

# Answer
> 2 votes
# Python ~~199 171~~ 166

There's a shorter Python code (108) for this by SP3000:

https://codegolf.stackexchange.com/a/50854/41163

```
import sys
p=r=0
for i in sys.argv[1]:
 c=3,0
 if i!=".":c=divmod(int(i)-1,3)
 if i<1:c=3,1
 if p:r+=((p[1]-c[1])**2+(p[0]-c[0])**2)**0.5
 p=c
print"%.2fcm"%r

```

# Sample usage:

```
$ python isp.py 219.45.143.143
27.38cm

```

### Run online: http://codepad.org/h9CWCBNO

# Commented code

```
import sys

# p - last position as (y,x) tuple - initialized with 0, because "if 0" -> equals to "False"
p = 0
# r - result of adding all distances - ini with 0, because not moved any distances on start
r = 0

# Loop over chars
for char in sys.argv[1]:
   # c - current position of typist as (y,x) tuple

   # Always set c to position of "." key
   c = 3,0 # lazy for c=(3,0)

   # Check if char is not the "." key
   if char !=".":

      # Get position of char on keypad
      c=divmod(int(char)-1,3)

      if char<1:
         c=3,1

   # If this is the first char,
   # then STORE_OPERATION has not been executed,
   # so p is still p=0 from original initialization
   # calling "if 0" evaluates to False,
   # so we jump this code block, for the first char
   if p:
      # calculate delta of x, y from current and last position,
      # then add both deltas squared (**2),
      # then get square root of it (**0.5 = **1/2)
      # add to r (+=)
      r+=( (p[1]-c[1])**2 + (p[0]-c[0])**2 )**0.5

   # STORE_OPERATION - Store current position as last position
   p = c

# .2f returns r with 2 trailing digits
print"%.2fcm"%r

```

---
Tags: code-golf
---


title: Convert x-illion into standard form

text:
# Question
Title: Convert x-illion into standard form
Given a string, consisting of a prefix and then "illion", convert this number into standard form.

For example:

```
"million" -> 10^6
"trillion" -> 10^12
"quattuordecillion" -> 10^45

```

The program needs to be able to handle input going up to Centillion, which is 10^303. A list of names and their standard form values can be found here \- note that this gives values for every 10^3 increment up to 10^63, but then gives them in 10^30 increments, however the pattern is fairly straightforward.

The program needs to handle all 100 cases (even the ones not explicitly given by the website provided) - here are some examples of this:

```
"sexvigintillion" -> 10^81
"unnonagintillion" -> 10^276
"octotrigintillion" -> 10^117

```

Input can be given via STDIN, function argument or hard-coded as a string.

This is code-golf, so shortest code wins!

# Answer
# Python 2 (~~384~~ ~~368~~ ~~365~~ ~~348~~ 347 bytes)

```
def c(s):
 s=s[:-6].replace('int','');k=0;d=dict(un=1,doe=2,tre=3,quattuor=4,quin=5,sex=6,septen=7,octo=8,novem=9,b=3,tr=4,quadr=5,qu=6,sext=7,sept=8,oct=9,non=10,dec=11,vig=21,trig=31,quadrag=41,quinquag=51,sexag=61,septuag=71,octog=81,nonag=91,cent=101)
 for p in(s!='m')*list(d)*2:
    if s.endswith(p):s=s[:-len(p)];k+=3*d[p]
 return 10**(k or 6)

```

(The `if` line is indented with a single tab, and the rest with single spaces.)

Here `c('million') == 10**6` has to be a special case because `'novem'` also ends in `'m'`.

Examples:

```
c('million') == 10**6
c('trillion') == 10**12
c('quattuordecillion') == 10**45
c('novemnonagintillion') == 10**300
c('centillion') == 10**303

```

Thanks to Falko for obfuscating it down to 350 bytes.

---

For practice I tried rewriting this as a one-liner using lambdas. It's ~~404~~ ~~398~~ ~~390~~ ~~384~~ ~~380~~ 379 bytes:

```
c=lambda s:(lambda t=[s[:-5].replace('gint',''),0],**d:([t.__setslice__(0,2,[t[0][:-len(p)],t[1]+3*d[p]])for p in 2*list(d)if t[0].endswith(p)],10**t[1])[1])(un=1,doe=2,tre=3,quattuor=4,quin=5,sex=6,septen=7,octo=8,novem=9,mi=2,bi=3,tri=4,quadri=5,qui=6,sexti=7,septi=8,octi=9,noni=10,deci=11,vii=21,trii=31,quadrai=41,quinquai=51,sexai=61,septuai=71,octoi=81,nonai=91,centi=101)

```
> 11 votes

# Answer
## JS (ES6), ~~292~~ 270

Understands only the numbers written in the given list. The OP isn't clear about the others.

```
z=b=>{a="M0B0Tr0Quadr0Quint0Sext0Sept0Oct0Non0Dec0Undec0Doedec0Tredec0Quattuordec0Quindec0Sexdec0Septendec0Octodec0Novemdec0Vigint0Trigint0Quadragint0Quinquagint0Sexagint0Septuagint0Octogint0Nonagint0Cent".split(0);for(i in a)if(~b.indexOf(a[i]))return"10^"+(20>i?3*i+6:93+30*(i-20))}

```

Example:

```
z("Billion") // "10^9"
z("Centillion") // "10^303"

```
> 9 votes

# Answer
# C, 235

Handles all 100 cases. Program uses stdin and stdout.

Who needs regexes for camel-case splitting?

```
char*Z="UUUi+W<)E(<7-7-++*)('&%$,*$&%$",u[999]="\0MBRilDriPtiNiUnOeReTtUiXTeCtVeCiGRigRaUagInquiXaXsexPtuOgOoNaCeCeK1",s[99],*U=u+67;
main(n){
for(gets(s);*--U;)
*U<95?
*U|=32,
n+=!!strstr(s,U)*(*Z++-35),
*U=0:
3;puts(memset(u+68,48,3*n)-1);
}

```

### Example

```
octoseptuagintillion
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

```
> 9 votes

# Answer
# Clojure, 381 377 bytes

```
(defn c[x](let[l{"M"6"B"9"Tr"12"Quadr"15"Quint"18"Sext"21"Sept"24"Oct"27"Non"30"Dec"33"Undec"36"Doedec"39"Tredec"42"Quattuordec"45"Quindec"48"Sexdec"51"Septendec"54"Octodec"57"Novemdec"60"Vigint"63"Trigint"93"Googol"100"Quadragint"123"Quinquagint"153"Sexagint"183"Septuagint"213"Octogint"243"Nonagint"273"Cent"303}v(l(clojure.string/replace x #"illion$" ""))](Math/pow 10 v)))

```

Example:

`(c "Septuagintillion") ;; 1.0E213`
> 2 votes

# Answer
# Haskell, 204 bytes (+9 for formatted String)

```
import Data.List
x s=10^(f$[a|k<-tails s,i<-inits k,(b,a)<-zip["ce","ad","un","do","b","mi","vi","tr","at","ui","x","p","oc","no","ec","g"]$100:4:1:2:2:[1..],b==i])
f[]=3
f(x:11:r)=30*x+f r
f(x:r)=3*x+f r

```

In GHCi:

```
*Main> x "decillion"
1000000000000000000000000000000000

```

Replacing `10^(` with `"10^"++(show.` adds another 9 bytes:

```
import Data.List
x s="10^"++(show.f$[a|k<-tails s,i<-inits k,(b,a)<-zip["ce","ad","un","do","b","mi","vi","tr","at","ui","x","p","oc","no","ec","g"]$100:4:1:2:2:[1..],b==i])
f[]=3
f(x:11:r)=30*x+f r
f(x:r)=3*x+f r

```

In GHCi:

```
*Main> x "decillion"
"10^33"

```

**Edit:** I had to correct for `"quinquagintillion"` which contains `"qua"`.
> 2 votes

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