title: Construct a Ladder

text:
# Question
Title: Construct a Ladder
# Introduction

I want to build a ladder. For this, I have scavenged from the junkyard two long boards with holes in them, and I want to place the steps into these holes. However, the holes are not evenly placed, so the steps will be a little wonky, and I find it hard to estimate the amount of rod I need for them. Your job is to do the calculations for me.

# Input

Your input is two bit vectors, given as arrays of integers, which represent the two boards. A `0` represents a segment of one aud (*arbitrary unit of distance*) without a hole, and a `1` represents a segment of one aud with a single hole. The arrays may be of different lengths and contain a different number of `1`s, but they will not be empty.

I will construct my ladder as follows. First, I place the two boards exactly one aud apart, and align their left ends. For each index `i`, I measure the distance between the `i`th hole of the first board with the `i`th hole of the second board, cut a piece of rod, and attach it between the two holes. I stop once I run out of holes in one of the boards.

# Output

Your output is the total amount of rod I'll need for the steps, measured in auds. The output should be correct to at least six significant digits.

# Example

Consider the inputs `[0,1,1,0,1,1,1,1,0,0]` and `[1,0,0,1,1,1,0,0,1]`. The resulting ladder looks like this:

The total length of the rod in this ladder is `7.06449510224598` auds.

# Rules

You can write either a function or a full program. The lowest byte count wins, and standard loopholes are disallowed.

# Test Cases

```
[0] [0] -> 0.0
[0] [1,0] -> 0.0
[1,0,0] [1,1,1,1,1] -> 1.0
[0,1,0,1] [1,0,0,1] -> 2.414213562373095
[0,1,1,0,1,1,1,1,0,0] [1,0,0,1,1,1,0,0,1] -> 7.06449510224598
[1,1,1,1,1] [0,0,1,1,0,1,0,0,1] -> 12.733433128760744
[0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0] [0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1] -> 20.38177416534678

```

# Answer
# J, 20 bytes

```
4+/@:o.(<0 1)|:-/&I.

```

It uses the trick in MickyT's answer in R.

`(<0 1)|:` gives the diagonal of a matrix. For the explanations of the other parts, see FUZxxl's answer.
> 3 votes

# Answer
## J, 22 characters

Not inspired by the answer of randomra. The `I.` part is equal as that is the immediately obvious way of finding the holes.

```
(4+/@:o.<.&#$-/@,:)&I.

```
* `I. y` – all the indices of `y` repeated as often as the corresponding item of `y`. Incidentally, if `y` is a vector of booleans, `I. y` contains the indices at which `y` is `1`. For instance, `I. 1 0 0 1 1 1 0 0 1` yields `0 3 4 5 8`.
* `x u&v y` – the same as `(v x) u (v y)`. Applied as `x u&I. y`, we get `(I. x) u (I. y)`. Let's continue with the transformed input.
* `x <.&# y` – the lesser of the lengths of `x` and `y`.
* `x -/@,: y` – the difference of the items of `x` and `y`. If one vector is longer, it is padded with zeroes.
* `x $ y``y` reshaped to the shape specified by `x`. Specifically, if `x` is a scalar, `x` elements are taken from `y`. In this usage, `x (<.&# $ -/@,:) y` makes sure that trailing holes are ignored.
* `4 o. y` – the function `%: 1 + *: y`, that is, sqrt(1 + *y*²). Incidentally, this function maps from hole distance to length of rods.
* `+/ y` – the sum of the elements of `y`.
> 10 votes

# Answer
# Python, 85

```
lambda*A:sum(abs(x-y+1j)for x,y in zip(*[[i for i,x in enumerate(l)if x]for l in A]))

```

This turned out similar to Mac's solution. Convert the lists of 0's and 1's to ordered lists of the one-indices, and then sum the distance between respective elements.
> 10 votes

# Answer
# J, ~~32~~ 28 bytes

The verb `I.` returns the positions of `1`s in a binary string which is a huge help.

```
   +/@,@(=/&(#\)*[:>:&.*:-/)&I.

   0 1 0 1 (+/@,@(=/&(#\)*[:>:&.*:-/)&I.) 1 0 0 1
2.41421

```

For a better J solution check FUZxxl's answer.
> 6 votes

# Answer
# Haskell, 77 73 bytes

```
r x=[a|(a,1)<-zip[1..]x]
i#j=sum$zipWith(\n m->sqrt((n-m)**2+1))(r i)$r j

```

Usage: `[0,1,0,1] # [1,0,0,1]` which outputs `2.414213562373095`

How it works: the function `r` returns a list of the positions of the holes of a board, e.g. `r [0,1,0,1]` -\> `[2,4]`. `#` zips two of those lists and turns it into a list of distances between corresponding holes and finally sums it.
> 5 votes

# Answer
# R, 67

Uses outer to do a difference for indexed holes. Diag returns required differences. Then sum the calculated distances

```
function(a,b)sum((diag(outer(which(a==1),which(b==1),"-"))^2+1)^.5)

```

Test run in R Fiddle. I have wrapped it in a print to show the return complies with spec.

```
> print((function(a,b)sum((diag(outer(which(a==1),which(b==1),"-"))^2+1)^.5))(c(0,1,1,0,1,1,1,1,0,0),c(1,0,0,1,1,1,0,0,1)),digits=10)
[1] 7.064495102
> print((function(a,b)sum((diag(outer(which(a==1),which(b==1),"-"))^2+1)^.5))(c(1,1,1,1,1),c(0,0,1,1,0,1,0,0,1)),digits=10)
[1] 12.73343313
>

```
> 5 votes

# Answer
# CJam, ~~36~~ 33 bytes

```
l~]{:L,{L=},}%z{,(},0\{~-_*)mq+}/

```

Very naive approach... it expects the input as CJam-style arrays on STDIN

```
[0 1 1 0 1 1 1 1 0 0] [1 0 0 1 1 1 0 0 1]

```

Here is a test harness for all the example inputs. The results in the input field are used before the actual code is called. You can remove them if you don't trust me. ;)

## Explanation

```
l~]                               "Read and eval input, wrap in an array.";
   {        }%                    "Map this block onto both input arrays.";
    :L,                           "Store array in L, get its length N.";
       {L=},                      "In the range [0 .. N-1] get all elements where L is 1.";
                                  "At this point we've converted each array into a list of its
                                   non-zero indices.";
              z                   "Transpose the array, pairing up indices at the same position.";
               {,(},              "Filter the extraneous elements of the longer input.";
                    0\            "Put a 0 before the array.";
                      {        }/ "For each pair of holes...";
                       ~-         "Unwrap the pair, take the difference.";
                         _*)mq    "Square, increment, square root.";
                              +   "Add to the running total.";

```
> 4 votes

# Answer
# Python, 105 102 100 bytes

```
i=lambda l:(i for i,h in enumerate(l)if h)
l=lambda*a:sum(((a-b)**2+1)**.5for a,b in zip(*map(i,a)))

```

Pretty basic, just converts the input lists to lists of hole indices, then computes distance between each pair of such indices.

Test case:

```
>>> print l([0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1])
7.06449510225

```

Credit to @FryAmTheEggman for a couple of byte-saving suggestions. Turns out this can be golfed further, as demonstrated in xnor's answer.
> 4 votes

# Answer
# Python, 86

```
f=lambda a,b,i=1j:a>[]<b and a[0]*b[0]*abs(i)+f(a[a[:1]<=b:],b[b[:1]<=a:],i+a[0]-b[0])

```

A low-level and naive recursive solution without any list searching.

The input lists are `a` and `b`. If either is empty, return `0`.

Otherwise, let `x` and `y` be their first elements (the code doesn't actually assign these because you can't do assignments in a `lambda`, but it will make explaining easier). If both are 1, i.e. their product is 1, then they contribute rod distance. We keep track of distance in the complex number `i`, so that distance is the absolute value. Actually, we compute it regardless, then multiply it by `x*y`.

Then, we recurse. The idea is to shift both lists one step, unless one list starts with a 0 and the other with a one, in which case we shift only the 0 list. That way, 1's are always consumed in pairs. We could check these conditions with `x<y` and `y<x`, but it's shorter to take advantage of list comparison as `a[:1]<=b`. Finally, we adjust the complex displacement between the current elements by `x-y`.
> 4 votes

# Answer
# Pyth, 30 bytes

```
s+0m^h^-hded2 .5CmfTm*hb@kblkQ

```

Try it online with the input `[0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1]`.

### Explanation:

I convert the lists into lists of indices `[2, 3, 5, 6, 7, 8]` and `[1, 4, 5, 6, 9]` and zip them together `[(2,1), (3,4), (5,5), (6,6), (7,9)]`. Then I subtract the values, square them, add 1 and sum over all square roots.

```
CmfTm*hb@kblkQ
 m           Q     map each list k in input() to the following list:
    m      lk         map each value b of [0, 1, 2, ..., len(k)-1] to the value:
     *hb@kb              (b + 1) * k[b]
  fT                  filter the list for positive values
C                  zip these two resulting lists

s+0m^h^-hded2 .5...
   m            ...  map each pair of values d to:
    ^h^-hded2 .5         ((d[0] - d[1])^2 + 1)^0.5
 +0                  insert 0 at the front of the list
s                    sum

```

Shame that `sum` doesn't work for empty lists.
> 3 votes

# Answer
# Clip 3, ~~55 47~~ 38

```
[cr+`j[v[w#)#mvw2B}}(c)c]sl`{%ky1%kx1`

```

For the list with the fewer holes, the program iterates through it, and connects each hole with the corresponding hole of the other list. The sizes are calculated and summed.

```
>java -jar Clip3.jar ladder.clip
{0,1,1,0,1,1,1,1,0,0}
{1,0,0,1,1,1,0,0,1}
7.064495102245980096000721459859050810337066650390625

```

## Explanation

```
[c          .- Assign c to the lists, in order of size    -.
  r+`       .- The sum of...                              -.
   j[v[w    .- Join the lists with a function on v, w     -.
     #      .- Square root                                -.
      )     .- 1 plus                                     -.
       #    .- The square of                              -.
        mvw .- The distance between v and w               -.
       2
     B      .- (one-half, so #...B means square root)     -.
   }}(c)c   .- Apply joining function to the lists        -.
  ]sl`{     .- c is the (sorted by size) list of...       -.
    %ky1    .- Indices of y (the second input) which are 1-.
    %kx1    .- Indices of x (the first input) which are 1 -.
  `

```

If we are very liberal about the input format, we can reduce this to 36 bytes by removing each `k`. This requires the input to be a string of the control characters characters `\0` and `\1`.
> 3 votes

# Answer
# Python, ~~116~~ 115 bytes

This is a recursive solution.

It became pretty annoying when I found that `index()` just throws an error when no value is found, but I made it work. Unfortunately, I cannot use a lambda. It also annoyed me that `list.remove()` doesn't return the list, but instead returns `None`.

```
def f(x,y,r=0):
    try:i,j=x.index(1),y.index(1)
    except:return r
    x.pop(i);y.pop(j);return f(x,y,r+((i-j)**2+1)**.5)

```

Run online here: http://repl.it/c5L/2
> 3 votes

# Answer
# ECMAScript 6, 86 bytes

This originally started out using reduce (I wanted to see if it could be done in one loop as opposed to @edc65 answer).

```
f=(c,b,a=[0,...c],j)=>a.reduce((c,v,i)=>c+=v&&(j=b.indexOf(1,j)+1,v=i-j,j)?Math.sqrt(1+v*v):0)

```

But using @edc65 for `map` and `&&t` to return the value I was able to shorten it quite a bit.

```
f=(a,b,j,c=0)=>a.map((v,i)=>c+=v&&(j=b.indexOf(1,j)+1,v=i+1-j,j)&&Math.sqrt(1+v*v))&&c

f=(a,b,j,c=0)        //variables note the j can be undefined
=>a.map((v,i)=>      //loop through the first array
c+=                  //add
v&&                  //test to see if we have a hole
(j=b.indexOf(1,j)+1, //if so see if there is a whole on the other board
v=i+1-j,             //calculate index difference
j)                   //the last var gets evaluated so check to see if indexOf returned -1
&&Math.sqrt(1+v*v))  //calculate
&&c                  //return sum

```
> 3 votes

# Answer
# Java, 151

This just walks along `a` looking for ones, then walks along `b` when it finds one. If `float` accuracy is acceptable I could save a couple bytes, but I went with `double` to match the test output.

```
double d(int[]a,int[]b){double z=0;for(int x=-1,y=0,d=b.length;x++<a.length&y<d;z+=a[x]>0?Math.sqrt((y-x)*(y++-x)+1):0)for(;y<d&&b[y]<1;y++);return z;}

```

With whitespace:

```
double d(int[]a,int[]b){
    double z=0;
    for(int x=-1,y=0,d=b.length;
            x++<a.length&y<d;
            z+=a[x]>0?Math.sqrt((y-x)*(y++-x)+1):0)
        for(;y<d&&b[y]<1;y++);
    return z;
}

```
> 2 votes

# Answer
# JavaScript (ES6) 108

The main point is the f function that maps the input 0..1 arrays in arrays of holes positions. Then the arrays are scanned computing a total rods length using the pythagorean theorem. The `|0` near the end is needed to convert NaNs that can result when the driver array (the first) is longer than the second.

```
F=(a,b,f=a=>a.map(v=>++u*v,u=0).filter(x=>x))=>
  f(a,b=f(b)).map((v,i)=>t+=Math.sqrt((w=b[i]-v)*w+1|0),t=0)&&t

```

**Test** In Firefox / FireBug console

```
;[[[0],[0]]
 ,[[0],[1,0]]
 ,[[1,0,0],[1,1,1,1,1]]
 ,[[0,1,0,1],[1,0,0,1]]
 ,[[0,1,1,0,1,1,1,1,0,0],[1,0,0,1,1,1,0,0,1]]
 ,[[1,1,1,1,1],[0,0,1,1,0,1,0,0,1]]
 ,[[0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0],[0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1]]]
.forEach(v=>console.log('['+v[0]+']','['+v[1]+']',F(...v)))

```

> \[0\] \[0\] 0
> \[0\] \[1,0\] 0
> \[1,0,0\] \[1,1,1,1,1\] 1
> \[0,1,0,1\] \[1,0,0,1\] 2.414213562373095
> \[0,1,1,0,1,1,1,1,0,0\] \[1,0,0,1,1,1,0,0,1\] 7.06449510224598
> \[1,1,1,1,1\] \[0,0,1,1,0,1,0,0,1\] 12.733433128760744
> \[0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0\] \[0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1\] 20.38177416534678
> 2 votes

# Answer
# Octave, ~~60~~ ~~59~~ 42

```
@(a,b)trace(sqrt((find(a)'-find(b)).^2+1))

```
> 1 votes

# Answer
# Perl 98

```
sub l{$r=0;@a=grep$a->[$_],0..$#$a;@b=grep$b->[$_],0..$#$b;$r+=sqrt 1+(shift(@a)-shift@b)**2 while@a&&@b;$r}

```

## Readable:

```
sub l {
    $r = 0;
    @a = grep $a->[$_], 0 .. $#$a;
    @b = grep $b->[$_], 0 .. $#$b;
    $r += sqrt 1 + (shift(@a) - shift @b) ** 2 while @a && @b;
    $r
}

```

## Testing:

```
use Test::More;
for (<DATA>) {
    my ($A, $B, $r) = /\[ ([0-9,]+) \] \s \[ ([0-9,]+) \] \s -> \s ([0-9.]+) /x;
    $a = [split /,/, $A];
    $b = [split /,/, $B];
    cmp_ok l(), '==', $r, "test $_";
}
done_testing($.);
__DATA__
[0] [0] -> 0.0
[0] [1,0] -> 0.0
[1,0,0] [1,1,1,1,1] -> 1.0
[0,1,0,1] [1,0,0,1] -> 2.414213562373095
[0,1,1,0,1,1,1,1,0,0] [1,0,0,1,1,1,0,0,1] -> 7.06449510224598
[1,1,1,1,1] [0,0,1,1,0,1,0,0,1] -> 12.733433128760744
[0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0] [0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1] -> 20.38177416534678

```
> 0 votes

# Answer
## APL, ~~35~~ 28 bytes

Uses a similar algorithm to the J solution, but APL has fewer builtins.

```
{+/4○⊃-/{⍵⍴¨⍨⌊/⍴¨⍵}⍵/¨⍳¨⍴¨⍵}

```

Example input:

```
      {+/4○⊃-/{⍵⍴¨⍨⌊/⍴¨⍵}⍵/¨⍳¨⍴¨⍵}(1 0 0 1)(0 1 0 1)
2.414213562

```
> 0 votes

---
Tags: code-golf, arithmetic, array
---


# Question
Title: Can an ant spell words by walking on cube?
Write a function that takes two parameters: a positive integer *n* and a list of words.

Given a cube of *n*-by-*n*-by-*n* units, assign a random letter (A-Z) to each surface unit. (For a 3x3x3 cube, there would be 9 surface units on each face.)

Then determine whether it's possible for an ant walking along the surface (with the ability to cross faces) to spell each of the supplied words. Assume that to spell a word, the letters must be up/down or left/right adjacent, but not necessarily on the same face. \[**Edit, for clarity:** The ant can reverse its path and use letters more than once. Each surface unit counts as one character, so to spell a word with repeated letters (e.g. "see") the ant would have to visit three adjacent units.\]

The function should output two things:

1) Each of the letters on each face, in such a way that the topology can be inferred. For instance, for a 2x2x2 cube, an acceptable output would look like:

```
   QW
   ER
TY OP UI
DF JK XC
   AS
   GH
   LZ
   VB

```

2) Each of the words, along with a boolean representing whether it's possible for the ant to spell the word by walking along the surface of the cube. For instance:

```
1 ask
0 practical
1 pure
0 full

```

**Bonus challenge (will not factor into score, just for fun):** Instead of *n* representing only the size of the cube, let *n* also represent the dimensionality of the shape. So, an *n* of 2 would yield a 2x2 square; an *n* of 3 would yield a 3x3x3 cube; and an *n* of 4 would yield a 4x4x4x4 tesseract.

# Answer
> 4 votes
# Ruby, 272 bytes

Two unnecessary newlines are added to the code either side of nested function `g` to improve readability. These are excluded from the score. The characters `f=` which assign the anonymous function to a variable are also excluded.

Output format is `0` or `1` per the question instead of Ruby's native `true` and `false`. A newline (rather than a space) is used to separate the boolean and the word. My understanding is that this is an acceptable interpretation of the output requirements, but if not, the impact on the byte count would be minor.

```
f=->n,l{c=''
x=[p=6*n,1,-p,-1]
(m=3*p*n).times{|i|c<<(5+i/n%6-i/n/p&6==6?65+rand(26):i%p==p-1?10:46)}
q=m+3*n
puts c

g=->w,i,d{w==''?$r=1:c[i]<?A?g[w,(i+x[d])%q,d^1]:w[0]==c[i]&&4.times{|j|g[w[1..-1],(i+x[j])%q,j^1]}}

l.each{|w|$r=0
m.times{|i|c[i]>?@&&g[w,i,0]}
puts $r,w}}

```

**Output**

After about 50 calls like this:

```
f[4,['PPCG','CODE','GOLF','ANT','CAN','CUBE','WORD','WALK','SPELL']]

```

I finally got the following output with 2 hits. `ANT` is at the bottom right going upwards, and the `AN` is shared by `CAN`, with the `C` wrapping round to top left.

```
....KCAAXRHT...........
....ALRZXRKL...........
....NDDLCMCT...........
....ETQZHXQF...........
........FYYUSRZX.......
........CFNPAUVX.......
........ZTJVHZVQ.......
........AUWKGVMC.......
............XWKSDWVZ...
............DPLUVTZF...
............DMFJINRJ...
............ZRXJIAFT...
0
PPCG
0
CODE
0
GOLF
1
ANT
1
CAN
0
CUBE
0
WORD
0
WALK
0
SPELL

```

**Explanation**

The particular unfolding of the cube selected, was chosen partly for its ease of drawing, but mainly for its ease of searching.

The non-alphabet characters (the dots plus the newline at the end of each line) are an important part of the field where the ant may be found walking.

Searching is performed by the recursive function `g`, which is nested in function `f` . If the word passed is an empty string the search is complete and `$r` is set to 1. If the ant is on a letter square which corresponds to the first letter of the word, the search is continued in all four directions: the function is called again with the word shortened by removing its first letter. In this case the direction parameter is ignored. The moving is done by recursively calling with the cell index altered by the values in `x.` The result of the addition is taken modulo the size of the grid plus an extra half line. This means that the bottom line wraps round to the top and vice versa, with the correct horizontal offset.

If the ant is on a non-letter square, she must zigzag in a staircase motion until she finds a letter square. She will zizag in southeast or northwest direction. This is simulated by recursive calls with the `d` parameter being XORed with 1 each time to keep track of her movement. Until she reaches the next letter square, there is no shortening of the input word. Conveniently, this may be done by the same recursion as is used when we are searching in the area with letters. The difference is, the recursion has only one branch when the ant is in the whitespace area, as opposed to 4 in the letter area.

**Commented code**

```
->n,l{                                   #n=square size, l=list of words to search
  c=''                                   #empty grid
  x=[p=6*n,1,-p,-1]                      #offsets for south, east, north, west. p is also number of characters per line
  (m=3*p*n).times{|i|                    #m=total cells in grid. for each cell
    c<<(5+i/n%6-i/n/p&6==6?              #apppend to c (according to the formula)
      65+rand(26):                       #either a random letter
      i%p==p-1?10:46)                    #or a "whitespace character" (newline, ASCII 10 or period, ASCII 46)
  }
  q=m+3*n                                #offset for vertical wraparound = grid size plus half a row.
  puts c                                 #print grid

  g=->w,i,d{                             #search function. w=word to search for, i=start index in grid, d=direction
    w==''?                               #if length zero, already found,
      $r=1:                              #so set flag to 1. Else
      c[i]<?A?                           #if grid cell is not a letter
        g[w,(i+x[d])%q,d^1]:             #recursively call from the cell in front, with the direction reflected in NW-SE axis
        w[0]==c[i]&&                     #else if the letter on the grid cell matches the start of the word
          4.times{|j|                    #for each direction (iterate 4 times, each time a different direction is "in front")
            g[w[1..-1],(i+x[j])%q,j^1]}  #recursively call from the cell in front. Chop first letter off word.
   }                                       #Direction parameter is XORed (reflected in NW-SE axis) in case ant hits whitespace and has to zigzag.

   l.each{|w|                            #for each word in the list
     $r=0                                #set global variable $r to zero to act as a flag
     m.times{|i|c[i]>?@&&g[w,i,0]}       #call g from all cells in the grid that contain a letter
     puts $r,w}                          #output flag value and word
}

```

---
Tags: code-golf
---


title: Find that zipcode!

text:
# Question
Title: Find that zipcode!
Italian zipcodes are 5-digit numbers. Each number is linked to a province. There are 4610 zipcodes and 110 provinces (as of 2015) in Italy.

Given the list of zipcodes and the related province (in this file - Gist here) write a function (any language would be fine) that, accepting in input an Italian zipcode, writes out the related province. For unknown zipcodes (for example '99999'), the result should be "XX" ('unknown zipcode').

This is , so the function with the shortest amount of bytes wins.

Rules: you can't use Internet resources, files (including the list of zipcodes-provinces of before, even if you can include the list, but then that would count as chars in your source file), built-ins or libraries/modules that provide a mapping from zipcodes to provinces or any other external entity in your function.

**Some test cases:**

> f("00185")="RM"
>
> f("00014")="XX"
>
> f("86071")="IS"
>
> f("20020")="MI"
>
> f("08010") can be "OR" or "NU" (they share the same zipcode)

Happy coding!

# Answer
## Mathematica, 2973 bytes

```
Uncompress@"1:eJzt3U3O47gRgOEAWecQc5OR1f4cI7alkd1Go5e5QO6/y7ALBVIUJdMSRUru9ynoh8UiWfKmMX+YP/77v+7+57/++Y8fQ91VwrzZUZrw93PHgVYSC3cUypfLAQCQxvNhQp9jYeaHNeV6LnUyAADb1J3d8Mea6+dDVXYuR885TgEAYD++Og33fX7k6TnHKQAA7MflERel+3RtqxsAAMp7dH74OXcs77qyXM+lTgYAYJvak3+Nh50N12nWnR1W9qtC3disPz+VDVeGT39nDwAAtu8e0DxC4dfI098hT885TgEAYD9u3000nb6Zd31zo67k3nTmrTn9qvz7r3Gb09+5k408Pec4BQCA/air+vzr0qhMPO/Puzz7l85JyFji106/nnGa7lWYmnBd/Cluh7ZPmZnza4W+I80+AAAsEfxb642bj3nX8dh+MRFa28/Zfud/3bzcer8/AAApVI0foVy1qT/RttUNAADl1bc1w+zvnxFzpu0s3HPe3wgAgK171ib6o2HEz4TPSN1z2v0AAHMczoez3CU0Z0daZ/PDnO7jrnXr+vFeLpz/TNXjVYTr4la6O6TsOfWOAADsW3WZE6F1c/dyd4jtec1fBACA/Tkd58T4ujw9x1fGdD43t+Y3AgDwjrv9z8mfZtTPuDNjo/7McG6NntPvCQDAnp2vU1HfzH2srlzPpU4GAGCb7q0fktNZvbvzbkWZnuMr+337uf4MAAB7NfmX570wtXaVvU/tPXWG30V8L0u+bnku/nQA+GzXg43YnOaHmXS5qY5Tfv+2PKv1I33PqXcEAGDf6mZJuHtMnTG8j+8W0/P87wUA4BPdm9cRrirZc7mzAeD3dKkvtdwlJOdm/IrxnO4XqrN3/9zh/fXZoapPdTjFx3vVr/Za0vP8r1tyLgAAW3W45413zwz3PP/r+rlUvyIAAGXVXdrI03OOUwAA0y5NP2JzJjsvt7zjpTtsV/tcL3T39D2n3hEAgH27Nf0wGbn0bp+htVov7/5K9wz/OYz4nud8KQBgvudBI5Szc8OM5uRNrnn72bV62Wy/Vvfz93zvi5f8Xvm1dVyU7tO1rW4AACjveZS7hObiomzPcZXDbnXk7jL/a7bwewAA8Hj6Ecoti/Q9p94RAIB9O1zMpaG54butsbOhXK6eAQCA9f3b92/mLm/rROjc9qbXePh1Wh3esQzpEgCAsh53E/qU9xxOzTBi18b3aL/Kfl18Lu47YnsBAGA97bd3wq0Prc3Vc3zl1Bf4uTV7BgBgTc+zG6Gc5MN1ktfZ0NpXZ7hv8T2n+34AAD7Bs5sKM+/W6IrwuvHddMZWLOt5/teFc+/sCQDA9jxuEvbt/ZhaO2dfd02459y/EgAA23b4uXas0XP6PQEA2LND8zqkzq+1q+UZqgll7Or5Pc//urHckn4AACjt2ozH9KxfIe+hNel7Tr0jAAD71h1jol9nRmMr8/Sc4xQAAPaj7WyERrbGPP0VY2vtat0jbc951gAAsBdfRxP2qW9u1p8zT73csVat33OOUwAA2I+uMSFPHflh64b5Mj2XOhkAgG263jTckZvvh86MVeTpOccpAADsx1cdDjOj13AkK3V9/p7jK/N3BwC/l+42HHc3E27ODZsJ7fZqZcpeP0lX2ZCRueul+W3ZXkcAAAAAACzzdTaXCR3bsCN/xs4P9wvv4OeX9hxbOex3OresMwAAymgfEvZNxyajNTLr15frudTJAABsk/kH5PqU0Hc3N5zVVf2qXD3nOQcAgP24n1+FVrnV/Xe5NL9+xzlOAQBgP653N2xWLjs/zJfo1nYBAACsy3c3dCxPc5crVGdrbZ1b75/Rzy3rOc0+AAB8ivZswo40o2Fr/JC8nZXVeXqOrxx+DQAAn+tyNtflLO8SblZz7nvJXmMr+7FmVwAAlHPqTMhTR+6bjKSyX2UztsatO632b6GvtzMAAHvVNnq1jZuTTLvB/5fZFnsCAKCk6lbdzF0uGUvYd7fOD52Rmlw9x1eG+l2zNwAASmi/a4RykveffkW/OkfPOU4BAGA/rrUJeerIzdmRGfv1pXoudTIAAPtRtfHZ2B39iMv5a5d3AgBI5etqI5TTvJ8z2Zi69B1/8p8fj6MbZiy5/oxfF8ro6hw95zgFAID9aI82zEgy/bxktiO+G/8r7PcBAPBJ6n+b0Gc/ZN6tc2uHa/r7rdnzensDALBH1V/mkuiP4uK9evesZT0DAAAAAAAAALAlh+pQyX06bO3wTd/7+8q1Ts/xlcPvWKsrAADK+TotD7OL7JSr5zznAACwF4fOXK+jdJ+ubXUDAEB5l+P6kb7n1DsCALBvjyomSnfZt7V+AAAo7fqIi9J9urbVDQAAW3B4uFG6m7TM9+gFAAAAAAAAAAAAAMC4W6Xhvr+K6XVjO2nef9r52J7f/7qp3ub2AQDAVtRHDXnv52zWzQ1juip9z6l3BABg3w63w83c5S0mtLJkz+XOBgBgi6qnH6FczNzUqtQ9p94RAIB9u1dLYny9ztgK/7SY0+0u8uaO532dm1vnFwUAIL/2px+h3Fho7fSa9D2n3hEAgH2rD2kj9tzz3UZ/NB3S83q/x7ukIwAAyqrvUzE1H5qbypmnvA+r3u15nd8CAIBPUv80Ic/YOvfNnZN3vfrV8/ubvxYAkMp/Oj/c3Hid5kp0nP/MXLraj1DunTDr9XLHOpJTl/Wc5uuW9AAA+PHj6bGZUFVcLnxCePb9fpet37K2Sht5eo6vHPYXn1vzGwAASOnRxkXpPl3b6gYAgPKqU1yU7tO1rW4AACivvgyjdE+vbL9DAADyOt6GUbqnV7bfIQAAedWPsZC5qYrwqhw9x1eGvmrN3gAAKOHeDaN0T69sv0MAAPLqTsMo3dMr2+8QAIDyrkcJ+/ZezF8X29+7XzLd2/zcvN8XAAAAAPCb+z/cceZL"~StringTake~{a=2FromDigits@#,a+1}&

```

Looking for a better way to compress this... Currently, it just uncompresses to this long string, and looks up the ZIP code in it.
> 3 votes

# Answer
# MATLAB, ~~3987 2827~~ 2813

Not sure it is worth posting this given the enormity of it, but anyway:

```
b=java.io.ByteArrayOutputStream;org.apache.commons.io.IOUtils.copy(java.util.zip.InflaterInputStream(java.io.ByteArrayInputStream(typecast(org.apache.commons.codec.binary.Base64.decodeBase64(uint8('eJxtV0mS4zgM/BIArjraHpfHMd5GdvvQN2r7/xMmAVIudcV0harLJEUsmUjA/ZWIGI+jgN9JoiwUXSIfJ+pSRzk7PBPlLlEujGegPATK7xdR1HeEPM3scU2kFApRfyYaO+xEypRZsOMp8ECj7n71xDJh11MU1pXLi7iDD+z00wv7i96bqVDE254zMeMN3X2cSILerXb1DrWiZydO5HikThKJDOQdU3KFxM0wn3C0w/9LvSUulBEbp5Ho/iIZJvXx+cRfOEEDTRQ97r39IidM9Z9mKBx2WFHLxfZc2ys0UrKVoh/1VA6fPfwgA4VnChJI7j12B0275sbOaj4KwytBbKJe4UxnN7zu5Oau2fAtHx53RYGHknmEp2oshEzSIltRC7s7eT+1bHYa++FGfkBMMqvzTig+31hRrJztJTg2MZPABr0PQK6inGhAFAPyEfGW5XF/pgAOIBAggT34hbOGBPKIk4J4GTEF54DGRAlIpADrAZ93LwrwVV/3lHjC8QXo4t7dhcKkmBQgmiWCEFg9HYEKt9Vhg+OWoxpNLOpxgMdEHXWNfQP8MH6er9jRjC74EexaXp4PSnHNFGOHGnM93uVmTf3N1zOlSf3wYDyxIjlrPi2bxTtsRHb/4xtf94hGsxWQK81rQp4i/IrIT3TKugQcYeu9o+wQhTPLhzve10zN4J5o9m0v4xmomPc4sWjGmF2N53Kgzo8bbEhZDZsZNhNsZtiEm3hwM2xbCVfv8WA/OOb9ibqosQZO4tec75/UjeoBKozDBolw6KkYhy3TlzsVrTPlDmKttnOzHa2e31SU/TKt2N/wzqI1VzFSv+eGBSpZqxFVJ4LYUeWacUEMgko3Rrz3NGgcFnFuGRbBklVLB10AHog2eKw1XQDpSUwbKjN9wM0B2Urq4QE3h1Wd3kcahq7pgUPNug0zJCES4M1YCq83jdz4VLOxv9CYuWkX9IAsGOP+XJn56y8a52CKrMUZZHzcsDJs9G5qSkuqinYeVUVOzy1VL540aUxmw5/u+KSa1ul60DvoBw6kZ6qmPv6iqSiLYtOY/KPK5H2G1rOpbsEt0HDjvgJUUUmqKG4kh0qtGetpTurZrK+ZfoERTakH54FdJveHHUT4utE8dVV1ecTdI8iYgZNxcP+bFmCom/rpTkth437NTTTMgUNVSPjEtUo2kdD1rmBbVUAHEIHHadUqi7k/Qua04qSpBwFLu+PRM41T05cAbjJiEkOkA9IB9YxaclQ1I8GjryOKkhsiAlZ7WEQ94a16LzV/SbuDWb8zd2tv1eopq0pdb8xLZ0wA6ugIA6zK6tvXgSVMrYORaRjqf8sYtSb00TPubyxAXPvoaJUmn/yhJtYq7XcsI7eYkcvPacPt68wurz1ZwPcAy66xTPMfEdqa/5hQc8AgaiUAB/94sZun1l/jp9YRN/x1a9/f9eyDEcjUDLWDkx1iXzuNqdDzzB6zCfP3+3Pt0mtmr08oWZ1NqiLq8OOAhaJHYKVZu/zioLVsE4zQ2PqBaT6yM5oWrYih7E1ZrG83PaqzypnDzK13aifSaaY0FXMSP7NIupw5+tCmGc2v22DnISdrfaRTz7F0G2YoB0Lrusyldm1tEObRUKN+3LE7tTlPUeSmq7Xb3jgl/lYd0yyv6FoWU+1ZG3+1hujxi9MUjIl1TlPmyDrlXQ+c3dZPrZTQWCjIoDFw9+DczcacwXKYmzon64NY/rpynqfWMdOmeyV9d4mmeEdVlIYWWfeGvteZAr6nhgZOxe1cwDqzbafBw9/cjavPnSWkZl9zmsBjkcaP3b9cbIbVs67ex5hmOaxatt/xYJqKnLJWH+sUAVzsDp0Vtrn8OvGgM6hw45RlZ99D+Vq/4DopH3nMn6ngteNxNo2yjL940kmvdqQ9Pg3a+yNskKKbcPNtx4tOUDp7Y3rBPIl5IoElBRO/OK34pVb8Rinj4chLqUhXdobGzBl9lZFfq+39TYi6bxZB8krj1xstYZ2sRs5c562dkE1RM94bkE1Bohz8CPBBW5kEzcP3TOsfv4Vd+2bA3nKJfmjz0V64s6nj/MRfS0WZva4X63m6bnVDB/ylk5L1o1F7HJDNa90CP0YejBeH34KvQyuHEa80RRKdwmwCKVb1jNnFHPunh2xq1nObhXX6MKz6A4BffZ/be8qDOs15RD78wQn/fotqqM3dpqaqdFrVqsoOftbK3on7nrd+zJz0eoh9t6ic2J0A7+d71uGCeU49MjSON/E219TvCC8JNruM1t+Yt5ygZy/B5hg7258kzJ97rkeJvrS+XUBbIw7qLv/wLf0HznFGvw==')),'uint8'))),b);s=char(b.toByteArray)';
i=input('');h=@hex2dec;r=@reshape;t=cellfun(@(x){x(1:2),h(x(3:6)),h(r(x(7:end),2,[])')},strsplit(strtrim(regexprep(s,'([A-Z]{2,})',' $1'))),'Un',0);z='XX';for l=t
a=l{1};g=a{3};for g=r(a{3},2,[])
s=a{2}*10+g(1);e=s+g(2);if any(s:e==i);z=a{1};end
end
end;disp(z)

```

Yeah. Not really code golf material. Although much better now

---

After a bit of messing around, I managed to get MATLAB to directly access the Java Virtual Machine to be able to decompress a base64 encoded zip representation of the original data, which quite literally knocks 25% of the size of the code. I am being quite naughty here in that I don't block closing the InputStream and OutputStream during decompression, but who cares, it doesn't crash!.

---

After decompression, the zip codes are encoded in a format which is:

```
CCbbbboollooll...

```

Where `CC` is the two letter zip code. `bbbb` is a base (starting point) for this zip code which was divide by 10 and converted to hex so that only 4 characters are needed. For each base there is one or more `ooll` entries which is two hex numbers where `oo` is the offset from the base, and `ll` is the number of codes in the range minus 1.

All of the hex numbers are lower case, and all of the zip codes are upper case. This allows each entry to be separated based on whenever a two upper case letters appear (because the are only present as the first two letters in an entry).

Once each entry is split up, the hex numbers are parsed and converted into decimal, and we basically work through every entry to find a match.

The ranges for a given `ooll` pair are calculated as:

```
start = 10*dec(bbbb) + dec(oo)
end = start + dec(ll)

```

A new entry (`CCbbbb`) occurs at each point that the a new zip code appears. Some of the codes appear at more than one base address as there are some which are not all grouped together. Allowing multiple entries costs some bytes of `CCbbbb` headers, but it means that all of the lengths and ranges need only be 2 characters which saves quite a few.

---

Matlab is not good at encoding in different bases, so of the ideas I had for how to encode the data, this is the best I could think of. It turns out, that I can actually save quite a lot of bytes by resorting to directly accessing the Java Virtual Machine that Matlab is running to perform base64 decoding, followed by zip decompression. The input string was made by doing the reverse (compress then encode).
> 3 votes

# Answer
**Python2.7 ~~2645~~ 2573**

```
def X(n):
    import zlib,base64
    a=(ord(zlib.decompress(base64.b64decode("eNrt0wl31UQUwPGvdMEFsSJSqBsuqAgii1pFLYoFpC1Q2Qpu4IIVV9TP6qzJJJnkZXs503P+vyQzN3eSO333vYp4uxTZZaYWpDBLV0EhqdTsFQFoYffu3foKSZ4ZVJnmAol4zPKzjqScMnfdK9NcIBGPa3Zs1KMyzQUS8UTESJVpLpCIJz0pzGrUi4Mq01wgEXv8USDZkN/LnkLSpfIye+wcVI5tF7wefwLA6J7K7I0SP3e2l+YCiXh6YWFBFiqeUfYpss/pXnkfzQUS8Wxmfy3RV0TkwTDX+Ip6VPa3+Pv28xUBgz2Xk5pRz+FzVVKOTN3G7aTpZQCjOuDl0YGRKtNcIBGL3ciiZNHi4sECETN4B2kukIhDhw65KRO9Cd5oW5nmYudbWlKnIn7SOfGhiSRbtbmlpfCNchTEE3q+LMhFFu0D7SrzGwES8UI9iUR1j8Yq01wgES/WK6z1qNy4XbuI7wcY7/9cwn9qif6bd/6H558USMVLFWFuUGWaCyTiZU9F+laf9t4mBlSu3664MYA5Oxwjh82S2Dl8uviGLxGt0rzdzIivBil4xYhFOs6CVlGx8KQf49XOWlfmNwIk4rVm9oniG9lZeKxameYCiXi9IkgNq0xzsVMdOaJORUU2OJLNQSSFnDn9u9lZeTtPTemNqJp0+anmyo3b8VMCpvNmT3VvBpUbt5Py4wDm5q2WelSmudj5jjqx6GhTNLPwpB/j7U70460r8xsBEnHMEX3o01z5qs4fsyvHsjf8lYlWprnYqY5reWTuskDsIMebnhP3iA2PZ09mdWo2ntMHeidipMr8WoBEnFCnInYqG1g5kszK6umEyzVVGfx3AHjXy6MZWlemuUAiTspJTUfZeNKRIOpTGUAaTp0SdXSRv3taHwU+J/ZmBKf5ioDBzpw5oy81dvdeJrra+Eo8alkFQCfvx0kwmqhH5cbtihHfAzBPH1h5pOIgJ/Y2Xy2/IS6OVKa5QCKWi2TZZvSChOnl4o3YhxorN24XRLLM1wDM1YeKGWpJw111JahMc4FEfNRV+8o0F0jE2QqVkzw8q2/yzFkpPNlYuXG7MOJbAObr44LSrU9IuNK6Ms0FEvFJlfgpXOxRmeYCifjUyCeTkU/9QrhqlvUTLSv3WAEwDysrK+bSgw39nZhjxY/dK9NcIBHnzp0Tc2ZEwnhAZZoLJOIzzU42dqSU6FGZ5gKJ+Dwg5sgmtSh27lc5vh0txw5zPpvPn7fxeUuyhEsWF9tVncYXhuhTHzoeqzI/EAAAJrIqq6urejbM5G/MffZc8ICPZ1WOJbO6pYhvApifC4oZ9CwXdEZMZPKDKtNcIBEXL+pLEXc5JlRLLtWnMs0FUnGpTKds2o2XxMSdC9NbIBFfWiZUh7gbGw+rTHOBRFy2xF6ijzxnsnJZfN6/4aIZlWkukIi1tTUz6WDN3KzlZM3mZa1P5Zrt3DYAJrUu6+tqVGy4bkM9DKoaSzo0HZjQxsaGmNMNalJJlxK3IC630akyzQVScUUfV2ykgisjFgaQhqtXRR9qvqpDPYgLfEo/1adyfLusLr0HpnJNyyMV+8snruWPdKtMc4FEbG5uijk3N/NJNn1+SGWaCyTnq2gYe9CLRH51ZhFgR7hu5JGOr2dhNde+8KQf44Yl6rghPr5RCvRy98r8RoBE3DREHTddrIJxKtdvZ3a8SfOBidy6dUtfjrq3OZuVIK/vulWmuUAibsttxU0R0pCeVRkAAADAOLa21FlistmwlT8rW10qx7fze2zRe2Aqd2YSddzpU5nmAom4K3crxqoMIA1fd9a6Ms0FEvFN1ViVaS6QiG8jRqpMc4FUfGdNtZs5AAAAAABAwfeaHctKa1JakiAXrVy7XbFaUw0AY7inqdFFJrxXVEq1rkxzgUTcvy/qiNDJYZVpLpCIH7w8qt4Vl9pWprlAIn5sJuUbk/CvVV8Xl7Vzw3biCgCYv5+8PApJdaV1ZZoLJOLnlmLvPjDcVKJWR/n7HvAVAYP9UiQ1d8VI9Jil6irTXCA529vb6orl7GDv1Cjmue3t8sPlerQUO9+vno0KOR31Lzzpx3jo5VGcmOOhGx/qV2dUbrEdPyOk7jfHBHkqEgUvBLe1dSf9FL+31KNy43bxiF8VMA9/RIxUmeYCifgzYqTKNBdIxF+Z0SvTXCARf2dGr0xzgUQ8Cok5o3pUbtxOHtF7YCr/ZEavTHOBRPybGb0yzQWS859ihhqNa7F6dZuUqjVF/wNUv6A7"))[n])-48)*2
    return 'XXRMVTRIFRLTTRPGSSOTORNUCAOGCIVSTOAOCNSVVCBIATALGEIMSPMIMBVACOSOLCBGBSCRLOPVNOVBPCVETVBLUDPNTSGOPDVIVRTNBZBOMOREPRFEROMNFCRNRAFIPTARSIMSLUPILIGRPOANPUMCAPFMTEPECHAQBAFGBRLETAMTBTNACEBNAVSAPZCBISCSCZKRRCVVPATPAGCLENCTSRRGME'[a:a+2]

```

Each zip has it's own character, use that as indice to grab code.

Compressing the lookup didn't work well, slight decrease in hash length, but penalty in decoding. Instead adapted to take in strings and inlined. Slight improvement. A lot uglier. Mmm

**2572**

```
import zlib,base64;a=(ord(zlib.decompress(base64.b64decode("eNrt0/l31UQUwPELLogVkULdcEFFEFnUKmpRLCBtgcpWcAMXrLii/v8/OmsySSZ52V7O9JzvJ8nMzZ3kTt99ryLeLkV2makFKczSVVBIKjV7RQBa2L17t75CkmcGVaa5QCIes/ysIymnzF33yjQXSMTjmh0b9ahMc4FEPBExUmWaCyTiSU8Ksxr14qDKNBdIxB5/FEg25Peyp5B0qbzMHjsHlWPbBa/HnwAwuqcye6PEz53tpblAIp5eWFiQhYpnlH2K7HO6V95Hc4FEPJvZX0v0FRF5MMw1vqIelf0t/r79fEXAYM/lpGbUc/hclZQjU7dxO2l6GcCoDnh5dGCkyjQXSMRiN7IoWbS4eLBAxAzeQZoLJOLQoUNuykRvgjfaVqa52PmWltSpiJ90TnxoIslWbW5pKXyjHAXxhJ4vC3KRRftAu8r8RoBEvFBPIlHdo7HKNBdIxIv1Cms9Kjdu1y7i+wHG+z+X8J9aov/mnf/h+ScFUvFSRZgbVJnmAol42VORvtWnvbeJAZXrtytuDGDODsfIYbMkdg6fLr7hS0SrNG83M+KrQQpeMWKRjrOgVVQsPOnHeLWz1pX5jQCJeK2ZfaL4RnYWHqtWprlAIl6vCFLDKtNc7FRHjqhTUZENjmRzEEkhZ07/bnZW3s5TU3ojqiZdfqq5cuN2/JSA6bzZU92bQeXG7aT8OIC5eaulHpVpLna+o04sOtoUzSw86cd4uxP9eOvK/EaARBxzRB/6NFe+qvPH7Mqx7A1/ZaKVaS52quNaHpm7LBA7yPGm58Q9YsPj2ZNZnZqN5/SB3okYqTK/FiARJ9SpiJ3KBlaOJLOyejrhck1VBv8dAN718miG1pVpLpCIk3JS01E2nnQkiPpUBpCGU6dEHV3k757WR4HPib0ZwWm+ImCwM2fO6EuN3b2Xia42vhKPWlYB0Mn7cRKMJupRuXG7YsT3AMzTB1YeqTjIib3NV8tviIsjlWkukIjlIlm2Gb0gYXq5eCP2ocbKjdsFkSzzNQBz9aFihlrScFddCSrTXCARH3XVvjLNBRJxtkLlJA/P6ps8c1YKTzZWbtwujPgWgPn6uKB06xMSrrSuTHOBRHxSJX4KF3tUprlAIj418slk5FO/EK6aZf1Ey8o9VgDMw8rKirn0YEN/J+ZY8WP3yjQXSMS5c+fEnBmRMB5QmeYCifhMs5ONHSklelSmuUAiPg+IObJJLYqd+1WOb0fLscOcz+bz52183pIs4ZLFxXZVp/GFIfrUh47HqswPBACAiazK6uqqng0z+Rtznz0XPODjWZVjyaxuKeKbAObngmIGPcsFnRETmfygyjQXSMTFi/pSxF2OCdWSS/WpTHOBVFwq0ymbduMlMXHnwvQWSMSXlgnVIe7GxsMq01wgEZctsZfoI8+ZrFwWn/dvuGhGZZoLJGJtbc1MOlgzN2s5WbN5WetTuWY7tw2ASa3L+roaFRuu21APg6rGkg5NBya0sbEh5nSDmlTSpcQtiMttdKpMc4FUXNHHFRup4MqIhQGk4epV0Year+pQD+ICn9JP9akc3y6rS++BqVzT8kjF/vKJa/kj3SrTXCARm5ubYs7NzXySTZ8fUpnmAsn5KhrGHvQikV+dWQTYEa4beaTj61lYzbUvPOnHuGGJOm6Ij2+UAr3cvTK/ESARNw1Rx00Xq2CcyvXbmR1v0nxgIrdu3dKXo+5tzmYlyOu7bpVpLpCI23JbcVOENKRnVQYAAAAwjq0tdZaYbDZs5c/KVpfK8e38Hlv0HpjKnZlEHXf6VKa5QCLuyt2KsSoDSMPXnbWuTHOBRHxTNVZlmgsk4tuIkSrTXCAV31lT7WYOAAAAAABQ8L1mx7LSmpSWJMhFK9duV6zWVAPAGO5panSRCe8VlVKtK9NcIBH374s6InRyWGWaCyTiBy+PqnfFpbaVaS6QiB+bSfnGJPxr1dfFZe3csJ24AgDm7ycvj0JSXWldmeYCifi5pdi7Dww3lajVUf6+B3xFwGC/FEnNXTESPWapuso0F0jO9va2umI5O9g7NYp5bnu7/HC5Hi3FzverZ6NCTkf9C0/6MR56eRQn5njoxof61RmVW2zHzwip+80xQZ6KRMELwW1t3Uk/xe8t9ajcuF084lcFzMMfESNVprlAIv6MGKkyzQUS8Vdm9Mo0F0jE35nRK9NcIBGPQmLOqB6VG7eTR/QemMo/mdEr01wgEf9mRq9Mc4Hk/KeYoUbjWqxe3Salak3R/6ditYM="))[int(raw_input())]))*2;print("XXRMVTRIFRLTTRPGSSOTORNUCAOGCIVSTOAOCNSVVCBIATALGEIMSPMIMBVACOSOLCBGBSCRLOPVNOVBPCVETVBLUDPNTSGOPDVIVRTNBZBOMOREPRFEROMNFCRNRAFIPTARSIMSLUPILIGRPOANPUMCAPFMTEPECHAQBAFGBRLETAMTBTNACEBNAVSAPZCBISCSCZKRRCVVPATPAGCLENCTSRRGME"[a:a+2])

```

**Some thoughts**

Further optimization could include finding better arrangement of characters for compression. Limiting factor here is getting the data down.

This approach works fairly well since, since using only indices has inherently less entropy than trying to encode the entire zip. Given such long streaks of characters, the entire thing compresses pretty well. I initially tried compressing only the numbers of interest (so that I could implement a binary search) but ended up using more bytes than just the ordinal string I'm using here. There might be a smarter means of storing, but it's hard to beat the built-in compression.

I considered using a statistical approach, but it would be at best heuristic. A true functional representation would probably require just as many bytes if not more.
> 1 votes

# Answer
## Long "demo" answer in Python, 3755 chars

```
def f(c):
    import zlib
    import base64
    s=zlib.decompress(base64.b64decode('eJxN2VtyIzkOBdAtJQnw9SmpXR7H2JZGUumj97+QIe4FCXV0V5xGMZlMvkmdPk/fp9/T9XQ7/e90Pz1Pr/Pp/Hn+On+ff8/X8/38OD/P/15Ol/Pl4/Kfy9fl+/J7uV7ul8flefn34/fP5c/Hn88/X39+/tw/Pz6vn/evn6/Hf+/fl++P76/v6/fz++/P+efy8/Hz9fP7c/15/Dx/T7/X37/Xz+v9+rydbpfbP7eP2+ft6/Z7u97ut+ft7+11+/d+ul/uH/eZ4f3n/nu/Pk6Pr8f1cXvcH4/H63l6fjx/nzOD5/35eL7+/vOaRX9dXh+vr9f9NRO8XkfPx3Gk+Z84y/zD2Q7pZGnHUck6EyiY0jiOQcrMgmmTBkuwBluwB4cxzf9LKE52KjI0yoGSgvOBBlrSAw9mPFadHfkac98JLIfibEfKoOcwA4Ic1FkPEdATaJ9/laygoEdHmzmaO4kacnbLDBS1kpNjPeY51D4fSG/MQQ3W4PxsIWcJj8VubQHqfEUmi1gZyBlt5PxjJWhW9WRP+xVdIjpW9K28KaPdQKuf5ER58Z4EVJnMIKLWAI1R6TutoLygCqoPrcu3ZTQ4eHiDJ49KRAvqAVGWd/ZmvNgTeHktgUSURZ9PdNSkv41fwWiJtGwA63SzU+xoR3EsqsdOoHnnoBJRtd5XD6/o+c0yvzQdXobhLc8o2o1Re0WadTPwQZnRLBEt/rbJitwQbRHtER07BxtDmVH7zMKo9Wt/sTb0EmuZZgOY7N0rCk1q5ZvwDwJZ1SCHDqnrsdQ4cAoq3/4Fc8ZoAfumPeZUjiyw7xwKkg9ONBiFxoGBTqKvG71koAQ16BlKSj6kQfZf42q3kjDZaCVL39GKQpLd6gzsqEkjc5gTWJI1y4FzwCQS7UpiMJB1P7aqOiXpHAwkKgrMadMbAMRUAWpE7RXZ2XZmrAfQRn0jW7AHR2Q2xKJz6HKerCTHPDl2tKBKjP5BMwtMpNaFjYIZHFQfqWlNmfNzq6cFBfOC8S2BNzcoQQ2WoD04O1dKnLmKE12VxFIHSiSwVSSRBVViXOtFSpi55sfOlu8+TBHFN5KCzmVcK1lPw3sfyOWZLDuBL2pGy0GdbaV9ywz1UEjWQxFM+pY1KJh3yLbJ+QwsdRMlJxveBnaMcqPXOhhv81oHS7Ci/9qiia5cyBwUVCqoaCGwBGuwBfvOYfh4s2LZsBjgGsc1YxyL0yboTNZIUCVYg4MdMK/9Q28ZQ3p2BTBzbzS5+oNmYYdwYsSCLBCJBRBkTYKsB1AjWiKzosG2M6uRoEaC2jbbEZSdb+eEdGSMY9TcpO2GKrimIKPP9jVj8JZCVqy4xpW2+uzHtOgas31axjiWAa6KmkSVNDIH2aNADZYg+4ORLX+0kjGktZCcd4z+tjIyNxjNOXaUTUtqsG8qaoGUiNqaRJZ4RYkE1os8QdUgJjHjWiRy7iiaklYlnUSVkMImAut+TPqmRg4lcrCKKs5I21JQgmW/oo0d7ZHWtov+ihHRweVrcmTuaUsevoM2rs9U4QFk0RYq0o8FKsdbWs5npH88WHYCxWIBNs7VQ9aKDmZ0OePqnlnyegeI+Q/0PRdYN7mogbq5CmlDBdXglIgWm2SakbsgMgfVkoMjEoxIMJRbOWPDx0/6V1h07a66KDcYTkw2MkTx4oGoPwb63sgoQQ1yJFsO/opahQt2JrlVAxVVbfRXgL4HN0pQ2YRFeAiqpH1wJyWi3JiTOH+SZedgfaCRNR6z8oqzLK7GqtK4SpO+gwY7erXROldy2jmLnOes5NHKzTRY8YrJt1fw40kJ8qAwlAvDIU6cHcH5bbMvgvP8NmchsOMIblz9twtG1twpGVdU9fAlCZSIcikH0QDOgrUS7DttYQcHOX5Vj7dXrHndKEF2r1IUQ2/2atDWiUIqBhmJYxTo24PJ1auHYmzOzRLI7RfZdgJ+v3E9ln3aKM62mTmGQJwOQO6CSHRsUHHxAZayHyt98e1tCX1njkFdQ4/U4MAoNGYcuUCRnYAfRI5NthBZItpWdO1AVIu/mMRnkujjIDecxrUAqla/+CCb9RTQtkeJFC5qIKra6DlIVo6hRGbZUW5ZSWw7QInHWOukRoKxoxjo4Nvb0OXmt4m2zksSkMsMiVoH2ddB1iRYZJObBuPaNDTtq++AKDqYIwHfRmJ0GVch2VmCGY0FdrS8MePaAvQTipHtCVrtVSdKZHx7BeqhOseOSkQlojzaN5uUOdmQBR3cyE0O2Te5epG6H2O+Ri+OLel+mUFiOQC5hJKKs7RR8PGg92BQ8NWTq1fXYsdWOziCLA6J4oB6BMt+jEPEuPp6LRyblfQdHijBihFglIjyLojsi2vLOrxdqhPTCpjRf8my0/J2BpR4jPmCeuwcNB7TeEzHJkcyqZs1cqg7utbjUapPFWSLqDUPyY0xyJ0uyTtHsK/H3vJNvl+vpfkFJskzrzGjsciyE3B+AHmkJetKu6ra6K/wQWGfCfKMA2ISA60BCsluQMpOK3XnwDMvmXcOJR7jrGFcE3+yNTEFJcj1wpgjAScm4xo4vA049uWHRLQEcSfGLaj6kfXwwUDi/Ab6hhrsK4e3t/mCDbJKms3lXANA3mKTXCGNuDF04vrcuEbWPNZ5W5BoCxIrL5h10y8dQN2P8T7VuMqr8/ydgz6SjfxFAWxBXk2BVsMFXFPm3HH6TQPIbgT6/GvUiJadma8MQ+qaQMi+o7yoITGJgTwokAObaSMHr3ENnFaLrzhki+jA0DNaV27g22NrX23khXbOdY1uEpMuyC0KyEFG1p2WpxmwRA6cVoyrWUptq0uBGC1ki+jg6Ku42Me5rfoGGVyZjbZHAIhfX0C/qQLbpqIjgiwZWRff8l193chuILaTSBgwoG+pQG5RJtf2trR9LgTRm41rNipNeLEEenTkpr5lNa56aq348de4XtFaxQRSQb8iJiXIxaf3Y23VQByUQOk7ahv1RhYUDqzcwIFjs+G6qfS+G9Pod3hGCfIGLttNJctAYvYC8UOhs+2o8ArUqJFWeX+W+q7qORy9E5ASUQwCkD3VL7nxD26rDrSxMXOvZRTusntfzdJLR7OIU7G9BbEbcw5sJYwVWzCw4fAOjmOnHZjiyb6iXn2gcM9V+/qREGT3BdmVyYqzP++zDr5kXY9p7jzHFmdjJn1fms2ojzy7puExjcSMT/JgDpYgdwqk7hwqGwvEb3PrfuhA/XTf1pHcuhs1ojxzkmNHi27WyKzmYGRW28phfaZ0vwgj+VsH6HekRlwAgWtDb/IGMHK2AkveCTiXkOhnYI0cKp4jx4qmeIW3PIiWn+tBHz3x12oj7mtICWoQv3+RNaLWFoz6B1Udh3eNyqG0oms5MEpQg+xeo47ks5FxDSe7a2LUuDqiDg6yAa5OkIZ61LjSjsFZLpPsGqQtLOBbWi8vyJznR1bP17gG75rYB7imqzy67yfJYt0dnHOf8y3tmtqMEtQg7h/+D74BxmY=')).decode("utf-8")
    c=int(c)
    i=220
    while i<len(s):
        p=int(s[i:i+3])
        x=int(s[i+3:i+8])
        g=int(s[i+8:i+11])
        if c>=x and c<=(x+g):
            return s[p*2:p*2+2]
        i+=11
    return'XX'

```

Data is packed in a base64-encoded and zlib-compressed string with the format:

pppcccccddd

where ppp is province index, ccccc is starting zipcode and ddd is delta. For example, zipcodes for "RM" province (Rome) would be:

```
08200010004 (from 00010 to 00013)
08200015000 (from 00015 to 00015)

```

and so on.
> 0 votes

# Answer
# Python 2, 2714

```
e='x\x9c5X\xcbr\xeb:\x0e\xdc\xeb[\xe4*\x91 Ar\xe9\xf8\xe6dR\x93\xc4\x1e\xdb\xc7\x8b\xfb\xff\x1f2\xdd\rd\x83\xa6(\x8a\x0f<\x1a\xa0\xde>j;\xcaq\xaaeG\xc3\xecd\x8eF9\x0e\xcaZNs{;\x8f\x83#\xcaN\xb4Sq6\xacF\x87\x8d\xc0VO\x95\xd8\x9b$\xc7p\x12HNB\xb4\xb2\xbd}YE\xf7NYO\x8dX\xb1\xb4\xd0\x03\xed8\rb\x0b\xc4\x1c\xdb\xdb\xcf\xac\xb1\x01\xa2I\xf6SYl\x18?\x9b1\xec\xdab\x9fcG\xc3\x0e\xc9zrb+\x18F\xc4w\xc2I\xd9\xb9\x06q\x9d\n\x87s\xc3-7\xdc\xb8\xe1\xc0\x86\x8d\x7f\x16\x9b\xa5\xe0cb\xc3\xd6\x81\x18\'4\xf5Ru\xc4\xa6\xa7fX\x908\xe2\x9b^N\x9d\xe8\x05K\x02G\xe2L\\\x1a\xb5\xec4\xb6\xb7\xe7\xf0\x03kA\x85\x8e\xbdH\x9ad\xdf\xde\xeeC\n\x1cR N:\xe2\xe8\x8f\xday\xf4\xdew4|\xca\x9a]F\xecq\x1c \x8e\x83\t\xfe\xb5\xc5\x91P\x80-~z\x7fo\xa1\\\x1cU\xda\xef\xc2!\x19z\xd1\x12\xf7\x8fE\x8b\x9e\xd6\xbe\x86\x9e\xcfmj\xc9\x9d\xc8S\x02\xeb!Y%\x1b\xf4\xd1\xa6\xc6^\xa6\x16\x9d;\x10\x06\x87m\xd0\xe8U\xb2I\xca\x8c\xebp\xbd\xf1\x8aO\x89017I\xa9S\x00q\x8a\xb6\xdd\xbf1\x1b\xb4\r\x95\x8e\x93\xcd\xbd\x0fh\xcb;\xcdQ\x16\xb6\x18\xa6\x83\xe1(\xbb\xa4K\x0e\xc9)\xb9\xe8\xdc\xf7\x9f6`\xd0\x1d\x92\xdb\x86l\'ax\xce\x98\xe19cv\x0b\xf4\xa2\xfe\xc5c]\x9b\xb4\x8e~`\xa3\n\xbaTq\xb0a\xd4U\xeb:\xff\xa7T\x8c\xc0:\xca\xa41\x8eJ!eWEP\xdd\xa5\xe4\x8f{\x9f1#\x913v)\xd7\x88\xb5b8\xd0\xd4\x0bw\x0b\xf4\x18\xdd\x0e\xc9\x1ac\xbb\xdei\xcf]&\xf8x/\xae\x99\x1d\xaa8l\x9eJ\xa1N\xa0\xdb\xe2\xa1[\xa0%\xb6\xc4_\xcd\xf1\xcc\xdb\xc7\xd5\xda1x(ke\x1c\xdb\xf5c\xd2M\xb42\x17\xa6h\xf0\xb0\xebs\xd0\xc6tR\xac\xb3\xd3)\xb6\xeb\x9d\xc7B\x9b\xd1{0r\x19\x9f\x10m_\x9c\x13\x94\xb2\x8e9!\x96<\x8c\xf3\xdf\xee\xcd\xd2\xc1\x8c:\x10Vi\x198\xa9uC|Kv\xe9\xdc\x8eF?\x00\xf6\x1e\xc3\xfa\x14*\xae\xadT\xdfn\xaf*/nP\xfc8\xe06P\xbc\xdc\xf9\xf6\x84\xa5\xe4T\xc4\x8ei\x80\xb5INJ#\xff\x10[\x8c\xb1\x05\xa9/\xff\xba\xbel;\xb0\xd2\xcaD\xee\x0fh5Q6\xf6\xf8\xe0\xdf\xd93\x1a\xba\xe8\xef`C\xfcI\xf4\x13\x95$\xbf\xb9]\xaa\xe2\x06\n\xab\n\xd6\xdby\x89\xe2\xb0\xf8\x12[\xadd\xab\x95l\xb5\x8e0\x1e\xb0\x97\xed\xf6A\x9b\xef\x10\x95\xa2Q8\xc5\xe4\x1a.\xb6\xdf\xe5\r\x0b\xd0\x16\xf7J\xa7\xe1@p\xe2\x00\xb8\x0er\x0c\xb2\xbd\x1fS\xc2\xa2\xbdv\xf9O\xba\x8f\xbc\xa7\x10\xdav\xfb\xc7"0\xc0\xe8\x9d\x1ak\xc4\xc6#\x9bX\xc9\x92\x95\xac\xc7\xb6\x81\x8c\xb3\xed\xf6\xee\xc1c;qH.\xce\xda\xe9\xfd|\xd6\x8a\xf9\xb5\xebk\x1c\xf3\xb3{F\x8d\xf3+\xcaE\x0b:\xed\x00\x05\xa0\xd1d> \x8fL\x84Q\xb5\xfd\xae\xfd\x8f\xed\xf6c\x06W\xdc)\xabd\xa3\x92\xd0X\xea\\\xea\\\xf4?"=\xc7L~z\xed\xd06&\xa7\r$\xe9|\xc0\x1a\x92|\xd2e\xbd\xf7\x9f\xd5\x92B\x99`\xb7\xef\xf75E\x87;\xb136W\x04-\x1b2\xefL\xf3\xce4\xefL\xf3\xce\x88M \x13\xca\xf6}\xf1\x1a\x1a r\x8fD\xc6\x0c\x10;\x10\x9a\xdeZ\x8bQ\xa4\x00\xa0\xf6\xf1V\x0f&7\x92\x11\x93\x9a\xd0\x98\x98\x80\xad\x88\xb7\x98\xc0\x84\x9e8\x12g\x8c\'\x1f~_\x9b"\x01j@\x03\x07\x02?\xa3\xd1\x98\xe9\x89\n\xc6rh\xe7M\xa1\xf0\xfd\xd3<b\x87H\x9e\x03\xc2\xd2P\'\x1a\x08\xeb*\x8c4\xe4\xfa\x02T\xaa\x93"\xb51\xbdKr\xa3\xa4\xa1\xaa\xc2\x03\xd2\xc5?h\x0c&&\xe0\x8c \xcah\xa9\x19-5\xa3\x85\xf5D\xa2\xd3\xa1\xbe\x9f\xa3g\xdc\r\x05\xe2\xf9\xde\xb3\x02\xe9\xd2o#\xaar\xe9\xd2\xef"b\xbbFl\x1a\x05G\x03[\x87~\x1f\xbd\x05\xff\x03\xe9\x15\x90&\xe9\'\xa1\x85\xec\x92pLy\xc7\xe7w\x99Y\xce\x94\x19\xd9\xa4\x88\xca\xff\xdc-t\x06\xc0\x04\xf0Q\xf5^\x9a\x98\x8d\xaa\x1b\x9c\x9f\xb2K*9\x0fUDC\x8c9\xe8\x05\xd1\xb7([\xd5\x93hrPEe\xfb\xf3\xdeZ\xe66V@\x89\x8b\x96j4m\'\x9aE?\xab\x85\xa6\xb9ZVZ@\x8dhCO\xda\xe0\xc7\x08\x86E-S\xf8\x9aR\xc5\xa3\\\xe1\xcfg\xa7awJR!qR\x85\x07\x973\xa2l\xd6\x0f)X\xc5\x9b\x0b#\xc4E\x87]\x06v\xe1\xa2\xb4|2=5\xd6\x0e\x7f\xbe\xdd\xc2\xdb]%\xdc jjg\xf1\x16\xcf\x9dQ\xf5s\xad\xb2\x00\xdcKI\x0b\x92u\x15K\x1b\xc9I)b!\x9a$]\x16\xd8\x0fI\xf5\xf9\x11}\xde\x12\x95|\xabl\xf9s\x9eG\x18\x93\xe8\xca\x05\x07cS\x1d\xc8\xa7L\xb0\xa4\x04e\xcf\xc39=q\x05\x0e\xc3\xf1\xa6\x8e>\xd3\xb7g\xfa\xf6\xd4q}\xfb\xfb\x8fY\xb8.Q\x84\x06\x82j\x8d\xec\xc5\r\xfc\xcd\x82c\xb2\xdb\x94\xae\x99\xaaXXP0f\xb5\xd3\xcbg\xa4"\xa5\x1a\xa8\xf1\xf2\x1fO\xd2%2\x04\x80 .HS2\xf4(M\xdc\xa3\x94\x07\xf6\x1c\xdd\xf9Vs^\xab\xc2\n\x9e\x89F\x93~*k@J\x93tI\x11@U0]~\x8a\xbei(d*\x8cO\xe9t\x05\xe2d%Q\xc8N\xac\xbe\xab\xca\x1bR\xebv\xf9Z\x96\xd4\xabc_\xde\xa6g"\x9d\xb1\x95\xf3oIB\x1d \x14eQ\x1eY9\x96\x82\x99\x10|n\xd2\x01)\x9a\x1e\xb0\xf8\xd5\x8a<\xbfx\xd2N\xe0\xf2*\\\xb3ne\xd9J\x01\xb5\xbd\xcf\xac\x16\x88\x1e\xda\xad\xfc\x8c8\xe2\x99\xb5\x86\x06\xb4\x1c\xd0\xa4\x80\xa9@\xb9\xfc;gp\xcf\x9cQ\x0fMy\xa1\x9e\x1b\xab\x13\xe2\x8a\xe7\xde\x02YWCF;\xbf\xf1\xa1\xb1\x9a\xf31\x83<\xb0\xea -\xd1\x03Fdl`O\x94\'\x135\xcc\xb5\xb9A\xeb\xc0KUE]\xee\xf5W\xad5\xd4\xfa\\\xc1\xa4\xd0G\x8f\xdd\x12\x07K\x83\xa5d\xbe2\x99/&\xf3\xed\xf1\xc8K\xc6\x88\x8b \x19J\xf7\xcaFO\xd7\x1a\x8f\xfb\xf24\xa5\x96x\xdcJ^.\x8a.\x17E\xd8%\xd5\'w$\xea*&\xb3\x14\xd9\x85c\x14,\xdb\xe3\x05\xa7\x19x;\xa2\xfa \x0eI\xdd&F\x94\xea\xc4\xa1\xc2y0\x89q\x007\xf0\xdf\xfb\x9c$\x14\xa8h\xc6\x9d\x10\xa8\xf4\tlE\xcafz||v\xe3\xbd\x0e.\x8aF\xd4\x93\x96\xf5\xa4Q\xd7\x81]\x92\x1e\xd4\xe5\xaa\x8fk\xb5\xcc\x03hTn\xa8\xc6\x8b\xf3l\x19=h4eM4\xba8\xa2\xb1\x803\xa2\x93\xac\x81\xe0\x8a\xa2\xc6:b\xc0b\x9dB\x9czN\xfahq\xc3\xfaz\x1f\x91e`\n\xad\xf6u\xa9\x06\x8e \xd9\x01\x99\x02+iT\x92\xb6\xa9"\xd3I\x8c\xd2Ad\xaa\xe7\x9e_\xf5\x96\xa8\xb7\x9e\xbd\x9e\xbd>\x02\xc7\x91h\xf15\xcb\xcd\xb1=_V\xc2\xca\xa6x\x81\x87\x99\xc2\xe1\xebZ\x9d\xda\xc7\x9c\x1et\x0e\x8c\xec\xee\xb9\x03\x9f=1\x8a\x17\xa75\x9e\xf7,\xc2{\x14\xed\x9d\xb5"\xf2z\xa4\xc6\x1e\xf5=\xc7=,\x13\xa1\xb5H\xfd\xa6\xbf#\x96\n\xb3\x96%l\x8bZ\x02\x88\xca\xfby[%+\x88\x15\xdb\xfc\xec\x83\x158%\xe3\xa6\x8f\xa8\xfc\xba\xb2t\xcf,\xddGx+Q\xb5\x81rr\x1fQ\xa2>\x7fl\xc6\x1d\xc5\xc4\xd6poS\xcaAt\xa1\x01\x83#1\xa11y\x116\x05\xf6\xf3Z\xe2\x9f\x08|\xfe`e\xd5\x843P\x95ya\xe9D\xfe\xd4_\x91\xa2\xc4Z\xd5\x98\n\xaa\x83\x0e\xd3\x85t\x94\x92y\xa6d\x9e)YC\x15\xd5P}\xfbz\xb6<\xb8\xb2\xfe\xd7\xdf\xde\xb3\xf6\xe9A\xa1]\xb5|\x11v\xc9Ai9\x86\xf5O\x0f>#jD\xd3\x08\xb8"d\xd7\x97H!\x90\x9e\xa3\x9cO:\xee\xbbg\xa5E\x9c\x94b\x04"\xeb1\xa0h\x85\xb8Nz\x8fY];}\x9eG\xcb\x1f!C\x1d\xafs-\x19\x02U6|\xbd\xd5\xc9\x10`\xf6\x8f\x80\xaf3]N\x01_\x85.\xa9w-\xc7\xf6\x1c\xeb\xaa\x95\x81z\x1aE\xd2$\xa3n\x98\x83U\x06&\x97\xb4\xf8z\xe9i)\xc8\xe6\xaau{]\x8a\x85K\x16\xdd\x8c\xc9HA(j\x88*\x81\xe0\xfc\xa2\xd0}\xbd\x9bJ+\xd3\xef;#VY\xc8T9\xd8\x11dh\xb2h\x15\xeaI\xdc\xc5\x15`\xff\xed\xfc\xb1\xea\xafG+\x11\xbf>\xcdC\xd7\xc0\xaa\xc8\xf4\xb0\xa21\xe5K\xd2\xceD\x9e\xce<\xfe\xb7\x01=G\r\xf92\xb0\x0bU\xf5>\xa6\xfa\xc1T\xce\xea\x9d\x05\x91\xf3\x9au\xfe*\xfd\xf7\x07\x06\xbdD\x7fvx\xa7\xe0\xdf\xb7(\xd2\xaf%)\xa2\x88"@\xdc2\xdb\xf9\xc7\xf3\xff%\xd1$\xbb\xe4\xd4M7\xfeT\xf9\x11\x94L$\xf3\x00[\\t\x19\x16.My\xfa\xbe\xebg\xe6\xf9\x7f>t\xbd\xe6?N\xce\xa0\xa4\xe1J\x1aHo\xae\xa4\x85\x82\xd1\x95*\xf9^\xbb\xb9\xb9\xf1?\x19$v\x0e\xe9Qz\x1e#qF\tz\xac(Q\xb5\xae\x91\xb1^w\xfbM\xd2\xc6$-\xc9#\x00\xf9\x07D\xc8\xab<\x90\x05\x83:\x9c\x85\x89\xe5\x0eLtb#\x99k$s\x8d\xd2\xe0T\x8f\x15U\x85\x92\xe7bT.f\x1bv`\xf6\xbe\xbd\x9e%\x9dN7L\x12\x87\x91U\x8c\x17\xf3P\xf4\xb3D\x04\xc1D\x19hE\x81\x16\x1d\xfa\xdbR"\xb4^\x93W[\xa6\xc8\xc5\x08\xe2\xdf>F\x90\xb0%\xf6\xa2\x7f\x82\x8c\x1a={\xfc#\xa4*\xce\xafi\xf9\x0b\xc5~\x0bV\xa5Rl}\xca\xe7\xff\x0f.\x98vx'.decode('zlib').split();d={}
for s in e:
 d[s[:2]]=[]
 for g in s[2:].split(','):
  f=g.split('-');d[s[:2]].append(int(f[0]))
  if len(f)>1:
   for k in range(int(f[1])):
    d[s[:2]].append(int(f[0])+k+1)
def f(s):
 for g in d:
  if int(s) in d[g]:return g
 return'XX'

```

Provinces and zipcodes are stored in a zlib encoded file with the following structure:

```
BG24010-21,24033-36,24100,24121-8

```

Initially build a dictionary filled with all the values, then look up the province.
> 0 votes

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


title: Partition into increasing subsequences

text:
# Question
Title: Partition into increasing subsequences
## Specification

This challenge is simple to state: your input is a non-empty array of nonnegative integers, and your task is to partition it into as few increasing subsequences as possible. More formally, if the input array is `A`, then the output is an array of arrays `B` such that:

* Each arrays in `B` form a partition of `A` into disjoint (not necessarily contiguous) subsequences. Inductively, this means that either `B` is the singleton array containing `A`, or the first element of `B` is a subsequence of `A` and the rest form a partition of `A` with that subsequence removed.
* Every array in `B` is (not necessarily strictly) increasing.
* The number of arrays in `B` is minimal.

Both the input and output can be taken in the native array format of your language. Note that there may be several correct outputs.

## Example

Consider the input array `A = [1,2,1,2,5,4,7,1]`. One possible output is `B = [[1],[1,2,4,7],[1,2,5]]`. The partition condition is evident from this diagram:

```
A    1 2 1 2 5 4 7 1
B[0]               1
B[1] 1 2       4 7
B[2]     1 2 5

```

Also, each array in `B` is increasing. Finally, `A` can't be split into two increasing subsequences, so the length of `B` is also minimal. Thus it's a valid output.

## Rules and scoring

You can write a function or a full program. The lowest byte count wins, and standard loopholes are disallowed. There is no time bound, but you should evauate your solution on all test cases before submitting it.

## Test cases

Only one possible output is shown, but there may be several valid options. In particular, the order of the arrays in the result doesn't matter (but each individual array should be in increasing order).

```
[0] -> [[0]]
[3,5,8] -> [[3,5,8]]
[2,2,2,2] -> [[2,2,2,2]]
[1154,1012,976,845] -> [[845],[976],[1012],[1154]]
[6,32,1,2,34,8] -> [[1,2,8],[6,32,34]]
[1,12,1,12,1,13] -> [[1,1,1,13],[12,12]]
[6,4,6,13,18,0,3] -> [[0,3],[4,6,13,18],[6]]
[1,2,3,2,3,4,7,1] -> [[1,1],[2,2,3,4,7],[3]]
[0,9,2,7,4,5,6,3,8] -> [[0,2,3,8],[4,5,6],[7],[9]]
[7,1,17,15,17,2,15,1,6] -> [[1,1,6],[2,15],[7,15,17],[17]]
[4,12,2,10,15,2,2,19,16,12] -> [[2,2,2,12],[4,10,15,16],[12,19]]
[10,13,9,2,11,1,10,17,19,1] -> [[1,1],[2,10,17,19],[9,11],[10,13]]
[3,7,3,8,14,16,19,15,16,2] -> [[2],[3,3,8,14,15,16],[7,16,19]]
[15,5,13,13,15,9,4,2,2,17] -> [[2,2,17],[4],[5,9],[13,13,15],[15]]

```

# Answer
> 3 votes
## Haskell, 54 bytes

```
n#[]=[[n]]
n#(l:c)|[n]<=l=(n:l):c|1<2=l:n#c
foldr(#)[]

```

Usage example: `foldr(#)[] [4,12,2,10,15,2,2,19,16,12]`-\> `[[2,2,2,12],[4,10,15,16],[12,19]]`

How it works: go through the input list starting at the right end. Build the output list (of lists) by prepending the current element `n` to first sublist `l` where `n` is less or equal to the head of `l`. If there's none, make a new singleton list of `n` at the end of the output list.

# Answer
> 1 votes
# Pyth, 20 bytes

```
fTu&ahfSI+THGHGQm[)Q

```

Try it online: Demonstration or Test Suite

Greedy approach. I create `len(input)` empty lists. Then I iterate over each number in the `input` an choose the first list, which is still sorted after appending the number.

### Explanation:

```
fTu&ahfSI+THGHGQm[)Q   implicit: Q = input list
                m[)Q   create a list of empty lists and assign to G
  u            Q       iterate over all numbers H in input:
      f     G             filter for lists T in G, which satisfy:
         +TH                 create a new list out of T and H
       SI                    and check if it is sorted
     h                    take the first such list T
    a        H            and append H
   &          G           logical and with G (so that u doesn't overwrite G)
fT                     remove all empty lists

```

---
Tags: code-golf, subsequence, set-partitions
---


title: When Bullets Collide

text:
# Question
Title: When Bullets Collide
This challenge is based off a riddle I read in some book a while ago, which I found again here. It is about bullets fired from a gun once per second at varying speeds that travel in a straight line forever. When one bullet hits another, both are destroyed completely. (Feel free to replace all instances of "bullet" with "missile".)

## The Task

Given a list of bullet speeds in the order they're fired in, determine whether all bullets are destroyed.

## The Rules

* Input is a list of non-negative integers, separated by any delimiter and with one optional character before and after. These are valid inputs: `1 2 3 4 5 6` and `[1,2,3,4,5,6]`. The programmer makes the choice.
* Output a truthy value if at least one bullet survives forever and a falsy value otherwise.
* Bullet speeds are given in units per second.
* Bullets move simultaneously and continuously.
* Bullets may collide at fractional offsets.
* Multiple bullets which simultaneously reach the exact same position, whether at an integral or fractional offset from the origin, all collide with each other.

## Examples

In these diagrams, `G` represents the gun, `>` the bullets, and `*` are times when bullets collide and explode.

### Truthy

Input: `0`

```
        0123456789
Time 0 G>
     1 G>
     2 G>
   ...

```

Output: `1`

---

Input: `0 0 0`

```
        0123456789
Time 0 G>
     1 G*
     2 G>
     3 G>
     4 G>
   ...

```

Output: `1`

---

Input: `1`

```
        0123456789
Time 0 G>
     1 G >
     2 G  >
     3 G   >
   ...

```

Output: `1`

---

Input: `2 1`

```
        0123456789
Time 0 G>
     1 G> >
     2 G >  >
     3 G  >   >
     4 G   >    >
   ...

```

Output: `1`

---

Input: `2 3 1`

```
        0123456789
Time 0 G>
     1 G> >
     2 G>  >>
     3 G >    *
     4 G  >
     5 G   >
   ...

```

Output: `1`

---

### Falsy

Input: `1 2 3 4 5 6`

```
        Unit      1111111111
        01234567890123456789
Time 0 G>
     1 G>>
     2 G> *
     3 G>  >
     4 G>   > >
     5 G>    >  >>
     6 G      >   > *
     7 G            >  >
     8 G                  > >
     9 G                        >>
    10 G                              *
                  111111111122222222223
        0123456789012345678901234567890

```

Output: `0`

---

Input: `1 0 0 3`

```
        Unit
        0123456789
Time 0 G>
     1 G>>
     2 G* >
     3 G>  >
     4 G   >>
     5 G     *

```

(The second collision is at time 4.5)
Output: `0`

---

Input: `2 1 2 3 6 5`

```
        Unit      1111111111
        01234567890123456789
Time 0 G>
     1 G> >
     2 G>>  >
     3 G> *   >
     4 G>  >    >
     5 G>     *   >
     6 G     >      >
     7 G          >   >
     8 G               >>
     9 G                *
                  1111111111
        01234567890123456789

```

Output: `0`

---

Input: `2 3 6`

```
        Unit
        0123456789
Time 0 G>
     1 G> >
     2 G>  >>
     3 G      *

```

Output: `0`

# Answer
## Python 2, ~~388~~ ~~392~~ ~~388~~ ~~346~~ ~~342~~ ~~336~~ 331 bytes

```
z=k=input();l=len(k);v=range;u=v(l)
while l<z:
 r="";o=[r]*l;z=l
 for h in v(l):
    if r:o[h-1]=o[m]=r;m=h;r=""
    for j in v(h+1,l):
     p=k[h];q=k[j];t=u[j];n=(1.0*q*t-p*u[h])/(q-p)if q-p else""if p>0 else t
     if t<=n<r<()>o[j]>=n<=o[h]:r=n;m=j
 i=0;s=o and min(o)
 while i<l:
    if o[i]==s!="":del k[i],o[i],u[i];l-=1
    else:i+=1
print l

```

My god this thing is huge, but I believe it actually does work. Once you see all the intricacies of it, this challenge is ridiculously hard.

I'm not sure if I can explain how it works in detail without typing for hours, so I'll just give an executive summary.

The big main while loop is looping until the input list does not shrink.

The nested for loop (can you believe a nested for loop is actually the shortest here?) loops over each bullet speed and ~~uses `numpy.roots` to calculate~~ calculates at which time that bullet will collide with each bullet that comes after. Here, `""` is being used to mean infinity (no intersection). An extra conditional has to be included to ensure that stopped bullets are marked as colliding the moment they appear rather than at time zero.

For each number we keep track of which bullet it will hit soonest, if any, and then `o` is updated with the minimum collision times for the involved bullets.

After this double loop terminates, we iterate over the input list and delete any bullet that will collide at the minimum of all collision times, if any. This allows us to simultaneously delete large numbers of bullets if they all happen to collide at the same moment.

Then we repeat the entire process on the remaining bullets, since they may be able to get by now that the bullets that they would have collided with have been destroyed.

As soon as no bullets are deleted (indicated by the list not shrinking), we escape the while loop and print the length of the remaining list. Thus, this program not only prints truthy if bullets survive, it actually prints exactly the number of bullets that survive.

EDIT: Special thanks to feersum for generating test cases to help me find bugs.

EDIT 2: Saved 42 bytes by solving the linear equation by hand instead of using numpy, and splitting out the starting times into a separate list and restructuring a conditional.

EDIT 3: Saved 4 bytes by renaming range

EDIT 4: Saved 6 more bytes by replacing double spaces with tabs. Also, feersum was kind enough to provide his implementation using fractions and sets for comparison. I've golfed it a bit and it comes out to 331 bytes, tying my solution.

EDIT 5: saved 5 bytes by removing an unnecessary initialization and rewriting a conditional
> 4 votes

---
Tags: code-golf, rational-numbers
---


title: Unfold musical jumps

text:
# Question
Title: Unfold musical jumps
The *Dal Segno* and *Da Capo* are two very commonly used musical terms. They mean "*from the sign*" () and "*from the beginning*" respectively.

There is also the idea of the *coda* (), which is the very end of a piece of music. It's what's played after the "main section" of the piece.

A *D.S. al coda* (*Dal Segno al coda*), for example, means "go to the *segno*, play until you're told to go to the *coda*, and then jump there."

## Description

Your job in this challenge is to take input composed of any number of notes which may or may not contain *Dal Segno*s and *Da Capo*s and output the same music with the aforementioned jumps "unfolded" so that the repetitions are expanded out verbatim.

## Input

Your code should take as input a sequence of either notes or *signals* (here defined as anything but a note), separated by spaces in one string.

* Notes are any of `a`, `b`, `c`, `d`, `e`, `f`, or `g`, with an optional `#` or `b` appended (for the purposes of this challenge, there is no rhythm).
* A `C` (capital c) represents a *coda* marking. There will always be either zero or two *coda* markings; the first *coda* marking represents where to jump from, and the second represents where to jump to.
* An `S` (capital s) represents a *signo* marking. There will always be either zero or one *signo* marking(s).
* An `F` (capital f) represents a *fine* marking. This "overrides" the end of the piece—more on that below. There will always be either zero or one *fine* marking(s).
* Any of the following exact strings of text represent:

+ `D.S. al fine`: go to the *signo* and play until either the end of the piece or the *fine* marking (if it exists).
    + `D.S. al coda`: go to the *signo*, play until the *coda*, then jump to the second *coda* marking and play until the end of the piece.
    + `D.C. al fine`: go to the beginning, play until the end or the *fine* marking.
    + `D.C. al coda`: go to the beginning, play until the *coda*, then jump to the second *coda* marking and play until the end of the piece.

There will always be a minimum of zero and a maximum of one of each string per piece. There will never be multiple `al fine`s or multiple `al coda`s in a piece.

## Output

Your code should output in a similar string format: a list of notes, separated by spaces.

You may always assume that the output will end up being one or more characters long.

## Test cases

In: `a# bb c b a`
Out: `a# bb c b a`

In: `a S b D.S. al fine c`
Out: `a b b c`

In: `a S b C c D.S. al coda d C e`
Out: `a b c b e`

In: `a b F c d D.C. al fine e f`
Out: `a b c d a b`

In: `a b D.C. al fine c d F e f`
Out: `a b a b c d`

In: `a b C c d D.C. al coda e f C g g#`
Out: `a b c d a b g g#`

In: `a b D.C. al coda c d C e f C g g#`
Out: `a b a b c d g g#`

In: `a b S c d C D.C. al coda C D.S. al fine e f F g`
Out: `a b c d a b c d c d e f`

In: `a S b C c D.S. al coda C d D.S. al fine e F f`
Out: `a b c b d b c d e`

In: `a b C c d D.C. al coda e f F g g# C gb a# D.C. al fine`
Out: `a b c d a b gb a# a b c d e f`

In: `a F b C D.C. al coda C D.C. al fine`
Out: `a b a b a`

In: `C a S b D.C. al coda C c D.S. al fine d`
Out: `a b c b c d`

In: `a S b D.S. al coda C C c D.C. al fine`
Out: `a b b c a b c`

In: `a F C b C D.C. al coda D.C. al fine`
Out: `a b a a`

## Rules

* The markings will always appear in a logical order. That is, there will never be an `S` after a `D.S.` and there will always be one before, etc.
* This is , so the shortest code in bytes will win.

# Answer
> 1 votes
# JavaScript (ES6), 253 bytes

```
x=>eval('n=(" "+x).replace(/D.{11}|[CSF]/g,d=>({C:4,S:5,F:6}[d]|(d[2]<"S")*2+(d[8]<"f"))).split` `;for(i=c=f=o="";v=n[++i];v<9?v<4?(n[i]=7,i=0,s=n.indexOf`5`,v==0?f=i=s:v==1?c=i=s:v==2?f=1:c=1):v==4&c?c=!(i=n.indexOf("4",i+1)):v==6&f?i=n:0:o+=v+" ");o')

```

## Explanation

Could be golfed better but I'm done for now.

```
x=>
  eval(`                                  // use eval to enable for loop without return
    n=(" "+x)                             // n = array of [ "", ...notes/commands ]
                                          // empty first element means f and c can be set
                                          //     to i (always true) in the cases below
      // DS fine => 0, DS coda => 1, DC fine => 2, DC coda => 3, C => 4, S => 5, F => 6
      .replace(/D.{11}|[CSF]/g,d=>({C:4,S:5,F:6}[d]|(d[2]<"S")*2+(d[8]<"f")))
      .split\` \`;
    for(
      i=                                  // i = position in note array
      c=                                  // c = look out for coda if true
      f=                                  // f = look out for fine if true
      o="";                               // o = output string
      v=n[++i];                           // v = note/command
      v<9?                                // if not a note
        v<4?(                             // if DS/DC
          n[i]=7,                         // change it to NOP
          i=0,                            // reset i here to save doing it in DC cases
          s=n.indexOf\`5\`,
          v==0?f=i=s:                     // case: D.S. al fine
          v==1?c=i=s:                     // case: D.S. al coda
          v==2?f=1:                       // case: D.C. al fine
          c=1                             // case: D.C. al coda
        ):
        v==4&c?c=!(i=n.indexOf("4",i+1)): // case: C
        v==6&f?i=n:                       // case: F
        0                                 // case: S
      :o+=v+" "                           // add the note
    );o                                   // return the output
  `)

```

## Test

```
var solution = x=>eval('n=(" "+x).replace(/D.{11}|[CSF]/g,d=>({C:4,S:5,F:6}[d]|(d[2]<"S")*2+(d[8]<"f"))).split` `;for(i=c=f=o="";v=n[++i];v<9?v<4?(n[i]=7,i=0,s=n.indexOf`5`,v==0?f=i=s:v==1?c=i=s:v==2?f=1:c=1):v==4&c?c=!(i=n.indexOf("4",i+1)):v==6&f?i=n:0:o+=v+" ");o')
```

```
<input type="text" id="input" value="a b C c d D.C. al coda e f F g g# C gb a# D.C. al fine" />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>
```

---
Tags: code-golf, music
---


# Question
Title: Bacon's cipher: An Intro to Steganography
*This little piggy went to market, this little piggy wrote some code...*

Ah wait, we're not talking about *that* bacon, we're talking about Sir Francis Bacon! Specifically, the cipher Bacon devised in the late 1500s, as a method of hiding a message within another message, a method of steganography.

The cipher works by concealing the message in the **presentation** of text, rather than its content. First, the letters of your message are encoded into binary (from 0 to 25) as follows:

Note: Please use the following encoding in your code and do not worry about numbers, spaces, or other symbols in the input, though I may devise some bonus for those who include these characters in their encoding. If you do include other symbols, the letters must still occupy spaces 0-25 in the encoding.

```
Letter  Encoding
A       AAAAA
B       AAAAB
C       AAABA
D       AAABB
E       AABAA
F       AABAB
G       AABBA
H       AABBB
I       ABAAA
J       ABAAB
K       ABABA
L       ABABB
M       ABBAA
N       ABBAB
O       ABBBA
P       ABBBB
Q       BAAAA
R       BAAAB
S       BAABA
T       BAABB
U       BABAA
V       BABAB
W       BABBA
X       BABBB
Y       BBAAA
Z       BBAAB

```

Having encoded all of the letters in your message into the `A`s and `B`s above, you must now select two **typefaces** for your code. For this example, I will use normal text for typeface `A` and **bold text** for typeface `B`.

So the message

```
HELLOWORLD

```

is encoded to

```
AABBB AABAA ABABB ABABB ABBBA BABBA ABBBA BAAAB ABABB AAABB

```

And now we conceal this binary with a **carrier text**.

> The quick brown fox jumps over the lazy dogs, gamboling in the fields where the shepherds keep watch.

It is alright if the carrier message is longer than the actual encoded message, though it cannot be shorter. Now we turn the carrier text into bold according to where the `B`s are in the encoded message,

> Th**e** **qu**ic**k** bro**w**n **fo**x **j**u**mp**s **ove**r **t**h**e** **l**az**y** **do**g**s**, gam**b**o**l**i**ng** in t**he** fields where the shepherds keeps watch.

Which without Markdown reads as

```
Th**e** **qu**ic**k** bro**w**n **fo**x **j**u**mp**s **ove**r **t**h**e** **l**az**y**
**do**g**s**, gam**b**o**l**i**ng** in t**he** fields where the shepherds keeps watch.

```

Note that I did not use the punctuation in the carrier message to encode the message, but whether the punctuation is encoded or not is up to you/.

**Rules**

* Your input will be the message you to be encoded and a carrier message. If the carrier message is too short, return some sort of error message.
* You must select two typefaces for encoding `A` and `B`, such as UPPERCASE, lowercase, *italic*, **bold**, ***bold italic***, ~~strikethrough~~, `in code format` and so on. You must use Stack Exchange's form of Markdown to encode these typefaces, i.e.

```
UPPERCASE, lowercase, *italic*, **bold**,
***bold italic***, <s>strikethrough</s>, `in code format`

```
* Your output must be your now-encoded carrier message, either shown with Markdown or shown without, as seen in the above example.
* You are only required to make an encoding algorithm. Any decoding algorithms you wish to provide are welcome, but **at time of writing** will not help or hinder your score.
* Your code must be a program or a function.
* This is code golf, so the smallest number of bytes wins.

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

# Answer
> 1 votes
## Pyth, 47 bytes

```
Vsm.[05jxGd2r~zw0#I}Jr@z~Z+1Z0GBpJ)p?NrJ1J;>zZ

```

Try it here.

Explanation:

```
             ~zw                               - Get the first line of input and
                                               - set z to the next line
            r   0                              - Turn it to lower case
  m                                            - Map each character
        xGd                                    - Get it's position in the alphabet
       j   2                                   - Turn it to base 2
   .[05                                        - Pad the start with 0's
 s                                             - Turn it to a 1d-array (flatten it)
V                                        ;     - For N in above array:
                 #                )            - While 1:
                      @z~Z+1Z                  - Get the current position in the
                                               - second line and increment the position
                    Jr       0                 - Set J to it lowercased
                  I}          GB               - If it's a letter, break
                                pJ             - Otherwise, print it
                                    ?N         - Is the character code
                                               - (the current 1d-array) 1
                                      rJ1      - Get the current char uppered
                                         J     - Leave it lowered
                                   p           - Print the character
                                           >zZ - Print out the rest of the second input

```

# Answer
> 1 votes
# Python 3, ~~216~~ ~~211~~ ~~231~~ ~~225~~ 207 bytes

~~This is a solution that uses normal text and Markdown-style italics for its two typefaces. And it encodes everything in the carrier message except the spaces.~~

**Edit:** Had to fix the code so that the result would print correctly and added examples below the code.

**Edit:** Edited the code to previously worse uppercase/lowercase solution, due to problems in printing the italics correctly.

```
def g(s,c):
 c=c.lower();w=[h.upper()for h in s if h.isalpha()];t=''.join("{:05b}".format(ord(i)-65)for i in w);r='';j=m=0
 while t[j:]:a=c[m];x=a!=" ";r+=[a,a.upper()][x*int(t[j])];j+=x;m+=1
 return r+c[m:]

```

**Examples**

```
>>> g('HELLOWORLD', 'The quick brown fox jumps over the lazy dogs, gamboling in the fields
where the shepherds keep watch')
'thE QUicK broWn FOx JuMPs OVEr ThE LazY DOgS, gaMbOlINg in THe fields where the shepherds keep watch'

```

**Ungolfed:**

```
def bacon(message, carrier):
    # Lowers the case of the carrier message
    carrier = carrier.lower()
    # Removing all non-alphabetic characters and making the rest uppercase
    words = ""
    for char in message:
        if char.isalpha():
            words += char.upper()
    # Encoding the message
    binary = ""
    for letter in words:
        encode = ord(letter) - 65
        binary += "{:05b}".format(encode)
    # Encoding the carrier message
    result = ""
    bin_index = 0
    char_index = 0
    while bin_index < len(binary):
        letter = carrier[char_index]
        # If letter isn't a space and it needs to be encoded
        if letter != " " and int(binary[bin_index]):
            letter = letter.upper()
        result += type + letter + type
        # The encoding only proceeds if letter wasn't a space
        bin_index += letter != " "
        # char_index increments whether or not letter was alphabetical
        char_index += 1
    # Return the encoded text and any leftover characters from the carrier message
    return result + carrier[char_index : ]

```

# Answer
> 0 votes
# C, 124 bytes

This requires the arguments to be in an ASCII-compatible encoding (e.g. ISO-8859.1 or UTF-8). It modifies the carrier in-place, and returns 0 on success, or non-zero otherwise. The encoding is `A`==lower-case and `B`==upper-case. Unused carrier letters are set to upper.

```
int f(char*p,char*s){int m=16;do{if(isalpha(*s)){*s|=32;*s-=(*p-1)&m?32:0;if(!(m/=2)){m=16;p+=!!*p;}}}while(*++s);return*p;}

```

### Explanation

Including a test program. Pass the letters to encode as the first argument, and the carrier string as the second.

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

/* ASCII or compatible encoding assumed */
int f(char *p, char *s)         /* plaintext, carrier */
{
    int m=16;                   /* mask */
    do {
        if (isalpha(*s)) {
            *s |= 32;
            *s -= (*p-1)&m ? 32 : 0;
            if (!(m/=2)) {
                /* reset mask and advance unless we reached the end */
                m=16;
                p+=!!*p;
            }
        }
    } while (*++s);

    /* 0 (success) if we finished p, else non-zero */
    return *p;
}

int main(int argc, char **argv)
{
    int r = argc < 3 || f(argv[1], argv[2]);
    if (r)
        puts("~!^%&$+++NO CARRIER+++");
    else
        puts(argv[2]);
    return r;
}

```

Test output:

```
$ ./66019 "HELLOWORLD" "The quick brown fox jumps over the lazy dogs, gamboling in the fields where the shepherds keep watch."
thE QUicK broWn FOx JuMPs OVEr ThE LazY DOgS, gamBoLiNG in tHE FIELDS WHERE THE SHEPHERDS KEEP WATCH.

```

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


title: Converging Sums of a Fractal Sequence

text:
# Question
Title: Converging Sums of a Fractal Sequence
## Background

A fractal sequence is an integer sequences where you can remove the first occurrence of every integer and end up with the same sequence as before.

A very simple such sequence is called Kimberling's paraphrases. You start with the positive natural numbers:

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

```

Then you riffle in some blanks:

```
1, _, 2, _, 3, _, 4, _, 5, _, 6, _, 7, _, 8, _, 9, ...

```

And then you repeatedly fill in the blanks with the sequence itself (including the blanks):

```
1, 1, 2, _, 3, 2, 4, _, 5, 3, 6, _, 7, 4, 8, _, 9, ...
1, 1, 2, 1, 3, 2, 4, _, 5, 3, 6, 2, 7, 4, 8, _, 9, ...
1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, _, 9, ...
1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, 1, 9, ...

```

That's our fractal sequence! Now let's take the partial sums:

```
1, 2, 4, 5, 8, 10, 14, 15, 20, 23, 29, 31, 38, 42, 50, 51, 60, ...

```

But what if we iterate this process? "Fractalise" the new sequence (i.e. the partial sums obtained from the steps above):

```
1, _, 2, _, 4, _, 5, _, 8, _, 10, _, 14, _, 15, _, 20, _, 23, ...
1, 1, 2, _, 4, 2, 5, _, 8, 4, 10, _, 14, 5, 15, _, 20, 8, 23, ...
1, 1, 2, 1, 4, 2, 5, _, 8, 4, 10, 2, 14, 5, 15, _, 20, 8, 23, ...
1, 1, 2, 1, 4, 2, 5, 1, 8, 4, 10, 2, 14, 5, 15, _, 20, 8, 23, ...
1, 1, 2, 1, 4, 2, 5, 1, 8, 4, 10, 2, 14, 5, 15, 1, 20, 8, 23, ...

```

And take the partial sums again:

```
1, 2, 4, 5, 9, 11, 16, 17, 25, 29, 39, 41, 55, 60, 75, 76, 96, ...

```

Rinse, repeat. It turns out that this process converges. Every time you repeat this process, a larger prefix of the sequence will remain fixed. After an infinite amount of iterations, you would end up with OEIS A085765.

**Fun fact:** This process would converge to the same sequence even if we didn't start from the natural numbers as long as the original sequence starts with `1`. If the original sequence starts with any other `x`, we'd obtain `x*A085765` instead.

## The Challenge

Given a positive integer `N`, output the `N`th element of the converged sequence.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may choose whether the index `N` is 0- or 1-based.

## Test Cases

The sequence starts with:

```
1, 2, 4, 5, 9, 11, 16, 17, 26, 30, 41, 43, 59, 64, 81, 82, 108, 117, 147, 151, 192, 203, 246, 248, 307, 323, 387, 392, 473, 490, 572, 573, 681, 707, 824, 833, 980, 1010, 1161, 1165, 1357, 1398, 1601, 1612, 1858, 1901, 2149, 2151, 2458, 2517

```

So input `5` should result in output `9`.

Here is a naive CJam reference implementation which generates the first `N` numbers (given `N` on STDIN). Note that your code should only return the `N`th element, not the entire prefix.

# Answer
> 7 votes
## CJam (23 22 bytes)

The partial sums are given at the even indexes of the fractal sequence, which is A086450. The recurrence given there as the definition of A086450 is the basis for these implementations.

Using an explicit "stack" (in scare quotes because it's not LIFO):

```
{),){2md~)\),>+$)}h+,}

```

Online demo

### Dissection

```
{         e# Anonymous function body; for clarify, pretend it's f(x)
          e# We use a stack [x_0 ... x_i] with invariant: the result is sum_j f(x_j)
  ),      e# Initialise the stack to [0 ... x]
  )       e# Uncons x, because our loop wants one value outside the stack
  {       e# Loop. Stack holds [x_0 ... x_{i-1}] x_i
    2md   e# Split x_i into (x_i)/2 and (x_i)%2
    ~)\   e# Negate (x_i)%2 and flip under (x_i)/2
    ),>   e# If x_i was even, stack now holds [x_0 ... x_{i-1}] [0 1 ... (x_i)/2]
          e# If x_i was odd, stack now holds [x_0 ... x_{i-1}] [(x_i)/2]
    +     e# Append the two arrays
    $     e# Sort to get the new stack
    )     e# Uncons the greatest element in the new stack
  }h      e# If it is non-zero, loop
          e# We now have a stack of zeroes and a loose zero
  +,      e# Count the total number of zeroes, which is equivalent to sum_j f(0)
}

```

---

At 23 bytes there's a much more efficient approach, with memoisation:

```
{2*1a{2md~)\){j}%>:+}j}

```

Online demo

# Answer
> 9 votes
# Python 2, ~~55 49~~ 42

I have no idea what's going on, but it seems hard to beat the Maple formula from the OEIS page. This uses 0-based indexing.

```
f=lambda n,t=0:n<1or f(n/2,n%2)-~-t*f(n-1)

```

Thanks to @PeterTaylor for -6 bytes.

# Answer
> 3 votes
# Haskell, 65

```
s l=[0..]>>=(\i->[l!!i,s l!!i])
r=1:(tail$scanl1(+)$s r)
f n=r!!n

```

# Answer
> 2 votes
# Templates Considered Harmful, 124

```
Fun<If<A<1>,Add<Ap<Fun<Ap<If<Sub<A<1>,Mul<I<2>,Div<A<1>,I<2>>>>,A<0>,A<0,1>>,Div<A<1>,I<2>>>>,A<1>>,Ap<A<0>,Sub<A<1>,T>>>,T>>

```

This is an anonymous function. It's more or less the same as  ~~my Python answer~~ the Maple formula on the OEIS page, except that I didn't implement modulus, so I had to use n-n/2\*2 instead of n%2.

Expanded:

```
Fun<If<
    A<1>,
    Add<
        Ap<
            Fun<Ap<
                If<
                    Sub<
                        A<1>,
                        Mul<
                            I<2>,
                            Div<A<1>,I<2> >
                        >
                    >,
                    A<0>,
                    A<0,1>
                >,
                Div<A<1>,I<2>>
            >>,
            A<1>
        >,
        Ap<
            A<0>,
            Sub<A<1>, T>
        >
    >,
    T
>>

```

# Answer
> 2 votes
# Mathematica, ~~47~~ 44 bytes

```
If[#<1,1,#0[Floor@#/2]+(1-2#~Mod~1)#0[#-1]]&

```

# Answer
> 0 votes
# Matlab ~~108~~ 103

I am using the fact that the desired series is the partial sum of https://oeis.org/A086450

But the computation complexity of my implementation is far from optimal, even for this simple recurrence.

```
n=input('')+1;
z=zeros(1,n);z(1)=1;
for k=1:n;
z(2*k)=z(k);
z(2*k+1)=sum(z(1:k+1));
end;
disp(sum(z(1:n)))

```

---
Tags: code-golf, number, sequence, number-theory, fractal
---