# Question
Title: Quickly find length of n-th term of the look-and-say sequence
The look and say sequence is an example of a run length encoding sequence. To get the next term of the sequence one groups the sequence into runs of the same number, each group in the next term then becomes two digits, first the number of terms in the group, followed by the value in the group. The first term is `1`.

Here is how we would calculate the first couple of terms by hand:

> We start with `1`, grouping that gives us `[1]` a single group of 1 `1`. Thus our next term is `11`. We group this and get `[11]` a single group of 2 `1`s, so our next term is `21`. Grouping again we get `[2],[1]`, we translate each of these groups into 2 digits each, `12,11` and concatenate, `1211`. Group again `[1],[2],[11]`, then convert each group, `11,12,21` and concatenate, `111221`.

The first couple terms of the sequence are:

```
1
11
21
1211
111221
312211
13112221
1113213211

```

Write a program that when given **n** as input returns the length of the **n**th term of this sequence as output. Programs should have a runtime of **O(n log n)**.

Answers will be scored in bytes with less bytes being better.

# Answer
## GolfScript, 300 chars

```
~8-:m;'!5?HZi " A 9 "$??HLTZ^`eik 5Z`e <^ $k H ,Sds ?LT /5@MUav I " i ? "5i G  !#+.4;>@K]_cdhjy{| *HCRJD@:64122/42.,,*860-40-0.+9?B<862//?D<7=@:420-/5:60.-20.+./384/162.-HCRJD@:64122/42.,,*)! !""$&&('{32-}/]1,/~:&;:L;:T;]:S;0m>{&m=}{L,,{.49=\71=+}%:V{,(,{).V=\T?S={(V=+}/}%0+:V}m*,,0\{.V=\L=8-*+}/}if

```

Here's a slightly shorter entry. Reads a number *m* from stdin, writes the length of the *m*-th term in the look-and-say sequence to stdout.

For example, input `50` produces output `894810`, while input `1000` produces (after a few seconds):

```
21465050086246039983937316427688400486337379416867195943208935654503780844828013651860410256502890125611856727316762

```

I'll post a more detailed explanation of the code later, but basically this also works by repeatedly multiplying a vector with a sparse matrix, encoded as an ASCII string. Some clever compression tricks, such as leaving out the all-ones superdiagonal of the matrix, are employed.

Ps. Here's a link to an online demo. The server has been pretty slow lately, though, so if you see an error message about a timeout, try again (or just download the interpreter and run it yourself).

---

**Addendum:** Here's the promised detailed explanation. First, let me repost the code with whitespace and comments added:

```
# Parse input, subtract 8, save in variable m:
~ 8- :m;

# This long string encodes all the constants used by the program (I'll describe it below):
'!5?HZi " A 9 "$??HLTZ^`eik 5Z`e <^ $k H ,Sds ?LT /5@MUav I " i ? "5i G  !#+.4;>@K]_cdhjy{| *HCRJD@:64122/42.,,*860-40-0.+9?B<862//?D<7=@:420-/5:60.-20.+./384/162.-HCRJD@:64122/42.,,*)! !""$&&('

# Parse the data string:
# The data consists of several arrays of positive integers, encoded as printable ASCII
# characters and separated by spaces.  (Note that this means that the range of possible
# data values starts from 1, which requires some adjustment below.  Also, the values in
# L are actually shifted up by 8 to avoid having single quotes in the data string.)

{32-}/   # Subtract 32 (ASCII code of space) from each char and dump result on stack.
]        # Collect numbers from stack into an array.
1,/ ~    # Split array on zeros (formerly spaces) and dump pieces on stack.
:&;      # Save topmost piece (canned responses for inputs 1-7) in var &.
:L;      # Save second piece (element lengths) in var L.
:T;      # Save third piece (nonstandard decay targets) in var T.
]:S;     # Collect remaining pieces (nonstd decay sources) in array and save it in S.

# If m < 0, return a precomputed response from &, else run the indented code below:
0 m > { & m = } {
  # Set V to be the initial element abundance vector (1 Hf + 1 Sn):
  # (Note: both L and V have an extra sentinel 0 at the end to avoid overruns below.)
  L,, { . 49= \ 71= + } % :V
  # Update the element abundances m times:
  {
    # Run the following block for all numbers i from 0 to length(V)-2,
    # collecting the results in an array:
    ,(, {
      # Start with the abundance of element i+1 in V (all elements except H decay
      # downwards; the extra 0 at the end of V is needed to avoid a crash here):
      ).V=\
      # If this element is one of the decay targets listed in T, find the corresponding
      # list of source elements in S and add their abundances from V to the total:
      # (If this element is not in T, we just loop over an empty array at the end of S.)
      T? S= { ( V= + } /
    } %
    # Append a new sentinel 0 to the end of the array and save it as the new V:
    0+:V
  } m *
  # Multiply the element abundances from V with their lengths from L and sum them:
  ,,0\{.V=\L=8-*+}/
} if

```

The key fact that allows this code to work is that, as the look-and-say transformation is repeatedly applied to any string, it eventually splits into substrings which evolve independently, in the sense that we can obtain all the following elements of the look-and-say sequence starting from that string by taking each of the substrings, applying the look-and-say transformation to each of them independently *n* times and concatenating the results.

Furthermore, in his 1986 article "The Weird and Wonderful Chemistry of Audioactive Decay" (which basically introduced the look-and-say sequence to the world), John Conway proved a remarkable (and, for this challenge, crucial) result which he called the "cosmological theorem":

> **Cosmological theorem** (Conway): There is a set of 92 finite strings of numbers 1–3 (which Conway named after the chemical elements; see table here), and two infinite families of strings each consisting of a fixed prefix followed by some number higher than 3 (these can only appear if the initial string contained number higher than 3 or sequences of more than 3 identical numbers), such that, after at most 24 applications of the look-and-say transformation, *any* string splits into a chain of such elements, each of which thereafter evolves independently (and splits into further elements).

Thus, to determine the length of a string sufficiently far in the look-and-say sequence, it's sufficient to know how many times each element appears in it. And, since each element evolves independently, knowing these "elemental abundances" is also sufficient for calculating the corresponding abundances of the *next* string in the sequence, and so on.

As it happens, the look-and-say sequence starting from the string `1` splits into two Conway elements (**Hf**72 = `11132` and **Sn**50 = `13211`) after just seven iterations. Thus, thereafter, we only need to keep track of the abundances of the 92 "common" elements (as the two families of "transuranic" elements cannot arise from common elements).

Mathematically, we can treat the elemental abundances as a vector of length 92. Calculating the abundances in the next step of the look-and-say sequence is then just equivalent to multiplying this vector with a 92 × 92 matrix, which is what r.e.s.'s solution does literally.

In fact, r.e.s.'s solution actually tracks the abundance of each element *multiplied with its length* (i.e. the "total mass" of that element in the string), adjusting the matrix accordingly, so that the total length of the string is given simply by adding the numbers in the abundance vector together. However, I did not find that a particularly convenient representation for code golf. (It was convenient for Nathaniel Johnston's derivation of Conway's polynomial, since it encodes the lengths into the matrix and thus gives the right eigenvalue for the asymptotic growth rate, but we don't care about that here.)

Instead, I just track the raw abundances of the elements, and only multiply them with the lengths at the end. This has, combined with the convenient fact that none of the decay products of any element contain more than one copy of any element, means that the entries of the transition matrix are just zeros and ones. Also, by far most of them are, in fact, zeros (in math jargon, the matrix is sparse), so I can save a lot of space by only storing the indices of those entries which are ones.

Also, in his article, Conway ordered the elements such that (except for **H**1 = `22`, which is a fixed point of the look-and-say transformation), each element decays to the next lower element in the sequence (and possibly some others). In fact, most elements decay *only* to the next lower elements. Thus, by using Conway's ordering of the elements, I can hardcode this "standard decay" as part of the iteration, so that I only need to store the matrix entries corresponding to the other, "nonstandard" decays, saving even more space.

(In fact, what I actually do, for reasons mostly to do with how GolfScript's array operations work, is store one array listing the matrix rows containing non-zero entries (i.e. the elements which are produced in nonstandard decays) and another array of arrays listing, for each of these rows, the columns where the non-zero entries occur (i.e. the elements which produce these elements in such decays). See the code and comments above for how these arrays are actually used to calculate the updated element abundances.)

The final space-saving trick I used was to encode all these arrays as strings of ASCII characters. Conveniently, there are 95 printable ASCII characters from space (32) to `~` (126), and the largest value that appears in any of the arrays is 92, so they fit very well. One extra tweak I made was to shift the values in the element length array (which only go up to 42 anyway) up by 8 so that I could avoid the character `'` (39) and thus store my data in a single quoted string without having to add any backslash escape characters.

There are some other minor optimizations too, but those are just standard GolfScript coding tricks. I should note that the actual code is not all that carefully optimized — it's quite possible that it could be golfed down further.

In any case, despite the inherent slowness of a double-interpreted language like GolfScript, the code runs quite fast and scales well: computing the length of the 10,000th string in the look-and-say sequence takes about 1.5 minutes on my computer.

Conveniently, GolfScript stores all numbers as arbitrary-length integers (bignums), so I didn't have to do anything special to make it produce exact results even for large inputs. The expected time complexity of this program is **O(*n* log *n*)** (as the element abundances grow linearly with *n*, and bignum addition takes O(log *n*) time), and the actual runtime seems to fit that prediction pretty well, as the graph below shows:

(Time is in seconds; for what it's worth, the green curve is given by *y* = (*a x* log(*b* \+ *x*) + *c*) / *x*, where *a* = 0.00106462026133545, *b* = 2720.25843721031 and *c* = -0.0401630789530016. The spike on the left mainly comes from the roughly constant runtimes for *n* \< 8, which become relatively large when divided by small *n*. I did not include it in the curve fit.)
> 13 votes

# Answer
## Sage ~~(18664~~ ~~2021~~ 1977)

This is a version that uses Nathaniel Johhnston's matrix formulation. (The matrix could probably be golfed further using `eval`.)

```
def f(n):
 z=[0];a=z*10;b=z*15;c=z*18;d=z*25;e=z*31;g=z*68;T=Matrix([z*28+[2]+z*63,e+[7/23]+z*60,z*29+[4/3]+z*62,z*30+[4/3]+z*61,z*32+[2]+z*59,z*53+[1/2]+z*38,z*36+[3/2]+z*55,z*37+[2]+z*54,z*38+[8/5]+z*53,z*39+[5/3]+z*52,z*43+[5/3]+z*48,z*45+[7/4]+z*46,z*46+[12/7]+z*45,z*47+[7/4]+z*44,z*48+[3/2]+z*43,z*50+[21/17]+z*41,z*51+[21/17]+z*40,z*49+[13/10]+z*42,z*44+[7/5]+z*47,z*52+[7/5]+z*39,z*40+[7/5]+z*51,z*41+[4/3]+z*50,z*42+[4/3]+z*49,z*34+[5/32,5/32]+z*56,z*56+[7/11,7/13,1/3,7/17]+z*32,z*54+[10/7]+z*37,z*55+[10/7]+z*36,z*33+[4/3]+z*58,b+[1/21,1/21,0,1/7]+z*12+[2/23,0,0,1/16,1/16]+z*17+[1/5,0,0,2/11,2/13,2/21,4/17]+z*21+[1/8]+z*3+[1/3]+z*6,z*17+[9/26]+g+[9/10]+z*5,z*87+[9/10]+z*4,z*19+[23/28]+z*72,z*34+[1/16,1/16]+d+[2]+z*19+[1/8]+a,z*88+[2]+z*3,z*90+[32/27,0],z*89+[32/27,0,0],z*91+[8/5],z*66+[3/7]+z*7+[1/3]+a+[1/2,3/10,3/10]+z*4,z*66+[5/7]+d,z*62+[3/2]+z*29,z*63+[10/7]+z*28,z*64+[9/7]+z*27,z*65+[9/7]+z*26,z*67+[3/2]+z*24,z*82+[5/3]+z*9,z*83+[8/5]+z*8,z*74+[7/9,7/12,7/12,7/16,7/18,7/24,7/23,7/16]+a,g+[4/3]+z*23,z*70+[6/5]+z*21,z*71+[5/4]+z*20,z*72+[17/14]+z*19,z*73+[17/14]+c,z*84+[4/3]+z*7,z*69+[5/4]+z*22,z*6+[7/12]+g+[7/12]+z*16,z*76+[7/12]+b,z*77+[11/16]+z*14,z*78+[13/18]+z*13,z*79+[7/8]+z*12,z*80+[17/23]+z*11,e+[2/23,0,0,1/16,1/16]+z*17+[1/5]+z*5+[2/17,1]+z*20+[1/8]+a,[0,1/7]+z*90,[1]+z*91,[0,1]+z*90,[0,0,7/6]+z*89,z*3+[7/6]+z*88,z*57+[7/13]+z*34,z*4+[1]+z*54+[4/17]+z*32,z*5+[6/5]+z*86,z*7+[4/3]+z*84,z*8+[5/4]+z*83,z*20+[8/7]+z*71,z*21+[7/6]+z*70,z*22+[7/6]+z*69,c+[9/14,9/28]+z*72,z*9+[6/5]+z*82,a+[6/5]+z*81,z*12+[4/3]+z*79,z*13+[9/7]+z*78,z*14+[4/3]+z*77,b+[23/42,23/42,23/26]+z*74,z*11+[8/7]+z*80,z*23+[6/5]+g,z*6+[5/12]+z*85,e+[15/23]+z*26+[5/7]+z*33,z*24+[6/7]+z*67,d+[1]+z*66,z*26+[1]+z*65,z*27+[3/8]+e+[3/17]+d+[1/2]+z*6,z*16+[9/14]+c+[27/32]+z*56,b+[9/14]+c+[27/32]+z*57,c+[5/14]+z*8+[5/8]+d+[1/2,0,0,5/11]+z*24+[5/16]+a]);v=vector(z*23+[5]+z*14+[5]+z*53);L=[1,2,2,4,6,6,8,10]
 if n<9:return L[n-1]
 Q=T
 for i in[1..n-9]:Q=Q*T
 return sum(Q*v)

```

E.g., `[f(n) for n in [1..50]]` produces

```
[1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78, 102, 134, 176, 226, 302, 408, 528, 678, 904, 1182, 1540, 2012, 2606, 3410, 4462, 5808, 7586, 9898, 12884, 16774, 21890, 28528, 37158, 48410, 63138, 82350, 107312, 139984, 182376, 237746, 310036, 403966, 526646, 686646, 894810]

```
> 2 votes

---
Tags: code-golf, math, sequence, restricted-complexity
---


title: Write all possible Braille characters

text:
# Question
Title: Write all possible Braille characters
An interesting puzzle came to me looking at the elevator buttons this morning.

You are required to generate a list of all Braille patterns that fit in a 2x3 grid. Use a hash `#` to denote a bump and a hyphen `-` to denote a flat area.

Expected output sample:

```
#-
--
--

##
--
--

#-
#-
--

(and so on...)

```

Rules:

* Your program must separate each pattern by at least one character or line.
* The patterns may be generated in any order.
* All patterns, regardless of what the Braille alphabet actually uses, should be produced. The completely blank pattern is optional.
* Only unique bump patterns should be generated. The following patterns are considered equivilent as the bumps are in an identical arangement. In these cases, use the pattern that is closest to the top-left corner (ie. the first option in this example.)

```
#-  -#  --  --
#-  -#  #-  -#
--  --  #-  -#

```

Bonus points if you can make it work for any *x* by *y* sized grid. (**EDIT:** Within reasonable bounds. Up to 4x4 is enough for proof of concept.)

Reading the wiki article, it appears there are 45 patterns (including the blank) that meet this puzzle's rules.

# Answer
> 6 votes
## GolfScript, ~~34~~ 32 chars

```
44,{84+2base(;{'-#'=}/@\n.}%2/n*

```

Turns out that there *are* shorter solutions than simply generating all 64 patterns and filtering out the bad ones. In fact, by suitably mapping bits to grid positions, it's possible to map all valid (non-empty) patterns to a consecutive range of numbers, as this program does.

Specifically, the mapping I use is:

```
5 4
3 1
2 0

```

where the numbers denote the bit position (starting from the least significant bit `0`) mapped to that position in the grid. With this mapping, the valid grids correspond to the numbers 20 to 63 inclusive.

This is almost the same as the obvious mapping obtained by writing out the 6-bit number in binary and adding line breaks between every second bit, *except* that the bits `1` and `2` are swapped — and indeed, that's exactly how my program computes it. (I also add 64 to the numbers before converting them to binary, and then strip the extra high bit off; that's just to zero-pad the numbers to 6 bits, since GolfScript's `base` would otherwise not return any leading zeros.)

Ps. Online demo here. (Server seems overloaded lately; if you get a timeout, try again or download the interpreter and test it locally.)

**Edit:** Managed to save two chars by avoiding unnecessary array building and dumping. Phew!

# Answer
> 3 votes
# Mathematica 97

```
Grid /@ Cases[(#~Partition~2 & /@ Tuples[{"#", "-"}, 6]), x_ /;
         x[[All, 1]] != {"-", "-", "-"} && x[[1]] != {"-", "-"}]

```

---

Blank is not included:

```
Length[%]

```

> 44

N.B. != is a single character in Mathematica.

# Answer
> 3 votes
## C# – 205

```
class C{static void Main(){var s="---##-##";Action<int,int>W=(i,m)=>{Console.WriteLine(s.Substring((i>>m&3)*2,2));};for(int i=0;i<64;++i){if((i&3)>0&&(i&42)>0){W(i,0);W(i,2);W(i,4);Console.WriteLine();}}}}

```

Readable version:

```
class C
{
    static void Main()
    {
        var s = "---##-##"; // all two-bit combinations
        // a function to write one two-bit pattern (one line of a Braille character)
        Action<int,int> W = (i,m) => { Console.WriteLine(s.Substring(((i >> m) & 3) * 2, 2)); };
        // for all possible 6-bit combinations (all possible Braille characters)
        for(int i = 0; i < 64; ++i)
        {
            // filter out forbidden (non-unique) characters
            if ((i & 3) > 0 && (i & 42) > 0)
            {
                // write three rows of the Braille character and an empty line
                W(i,0);
                W(i,2);
                W(i,4);
                Console.WriteLine();
            }
        }
    }
}

```

# Answer
> 3 votes
## Perl, 71 67 65 char

```
y/10/#-/,s/../$&
/g,/^#/m&&print
for map{sprintf"%06b
",$_}18..63

```

Convert int to binary, perform transliteration, and add a newline after every two chars. The `/^#/m` test eliminates two patterns (20 and 21) that don't have a raised bump in the leftmost column.

## General solution, 150 106 103 100 char

Read `x` and `y` from command line args. Newlines are significant

```
y/01/-#/,s/.{$x}/$&
/g,/^#/m*/^.*#/&&print
for map{sprintf"%0*b
",$x*$y,$_-1}1..1<<($y=pop)*($x=pop)

```

Iterate over 0..2xy like before, converting each int to binary, substituting `-` and `#` for `0` and `1`, and inserting a newline after every `$x` characters.

`/^#/m` tests that there is a raised bump in the leftmost column, and `/^.*#/` tests that there is a raised bump in the top row. Only the patterns that pass both tests are printed.

# Answer
> 2 votes
# Python, ~~120~~ ~~118~~ ~~113~~ ~~95~~ 118

```
for j in range(256):
    if j/4&48and j/4&42:print''.join('_#'[int(c)]for c in bin(j/4)[2:].rjust(6,'0'))[j%4*2:j%4*2+2]

```

Edit: used Winston Ewert suggestion and added x by y grid solution

Edit: I somehow missed the last constraint about uniqueness. This script generates all the possible sequences, not just the 45.

Edit: Back up to 118 but now correct

# Answer
> 2 votes
## J, ~~35~~ 33 chars

```
3 2$"1'-#'{~(2 A.i.6){"1#:20+i.44

```

Uses the approach Ilmari Karonen came up with in their Golfscript solution. However, since the J verb `#:` (antibase) stores the bits (or, well, digits in the generic case) in a list, we need to index it from the left instead of right (i.e. index 0 is the leftmost, highest bit).

The solution is rather straightforward: `20+i.44` gives a list of the numbers `20..63`, inclusive. `#:` takes the antibase-2 of each element in this list, and thus produces a list of bitpatterns for each number in that range. `{` selects (basically reorders) the bits into the right pattern, and then `{` is used again in order to use the digits as indices in the string '-#' in order to prepare the output. Finally, we arrange each entry into a 2-by-3 rectangle with `$` (shape).

---

```
3 2$"1'-#'{~(2 A.i.6){"1#:20+i.44      N.B. use A. (anagram) to generate the right permutation

```

```
3 2$"1'-#'{~0 1 2 4 3 5{"1#:20+i.44

```

# Answer
> 1 votes
## Python - 121 112

blank is not included

```
from itertools import*
print'\n'.join('%s%s\n'*3%b for(b,n)in zip(product(*['_#']*6),range(64))if n&48and n&42)

```

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


title: The Major-Minor Dichotomy

text:
# Question
Title: The Major-Minor Dichotomy
Given a list of chords label them as either 'Major' or ' Minor'.

## Input

Input will be a list of chords, one per line, made up of 3 notes separated by a space. Each note will consist of the note name in uppercase (`A`-`G`) and an optional accidental (`#` or `b`). Chords may be in any inversion (i.e. the notes may be in any order).

## Output

If the chord is major, output 'Major'. If the chord is minor, output 'Minor'. If the chord is neither major nor minor, output a blank line.

## Example

**Input**

```
C E G
F Ab C
C Eb Gb
E G B
Db F Ab
Bb G D
D A Gb

```

**Output**

```
Major
Minor

Minor
Major
Minor
Major

```

## Test scripts

As in some of my past questions, I've once again butchered some test scripts originally created by Joey and Ventero to provide some test cases for this question:

Usage: `./test [your program and its arguments]`

## Rewards

Each entry which I can verify that meets the spec, passes the tests and has obviously had some attempt at golfing will receive an upvote from me (so please provide usage instructions with your answer). The shortest solution by the end of 13/10/2012 will be accepted as the winner.

## A little theory

For those of you with no musical theory knowledge here's enough information for you to be able to compete.

A major or minor chord is made up of three notes which are separated by a specific pattern of semitones. If we consider the root (bottom note) of the chord to be 0, then a major chord is the pattern 0-4-7 and a minor chord is the pattern 0-3-7. Things are made more awkward by the fact that some notes are a semitone apart and some are a tone apart. The spread of semitones from `Ab`-`G#` is as follows:

```
G#/Ab A A#/Bb B/Cb B#/C C#/Db D D#/Eb E/Fb E#/F F#/Gb G G#/Ab
  0   1   2    3     4    5   6   7    8     9    10  11  12

```

`G#/Ab` means that that `G#` is the same note as `Ab`. From this we can see that the chord `Ab C Eb` is a major chord, and that `Ab Cb Eb` is minor.

To complicate matters further, the chord `Eb Cb Ab` is considered to be the same as `Ab Cb Eb`, `Cb Eb Ab` and `Cb Ab Eb` and so on. Every one of these variations is still a minor chord.

# Answer
> 3 votes
## GolfScript, 83 chars

```
n%{' '%{1\{'A#BC D EF G'?+}/.}%$(+2/{~- 12%}%.(+.(+]$0=.$]10,7>?'MMaijnoorr

'>2%}%

```

This is a quick first solution; I'm sure this can be golfed further. Passes the bash test suite, after fixing the bug pointed out by flodel in the comments.

**Edit 1:** Saved 5 chars with a shorter way to recognize the canonicalized major and minor chord patterns.

**Edit 2:** Saved 2 more chars with more compact output encoding inspired by grc's solution. (Thanks!) As a side effect, the code now prints an extra blank line after the output, but the test harness seems to accept that, so I guess it's OK. :)

Here's how it works:

* The outer loop `n%{ }%n*` just splits the input into lines, runs the code inside the braces for each line and joins the results with newlines.
* `' '%` splits each line into an array of notes. For each of those notes, `1\{'A#BC D EF G'?+}/` then converts that note into a semitone number by searching for each of its characters in the string `'A#BC D EF G'` and adding up the positions (which will be -1 for any character not found in the string, notably including `b`). (I'm *sure* I've seen this trick used before.) Finally, the `.` duplicates each number, so that, at the end of the loop, e.g. the input `F Ab C` has been turned into `[9 9 0 0 4 4]`.
* We then sort the notes with `$`, move the first note to the end with `(+`, and split the array into pairs with `2/`, so that it now looks e.g. like `[[9 0] [0 4] [4 9]]`. Then `{~- 12%}%` maps each pair of notes into its difference modulo 12, turning our example array into `[9 8 7]`.
* Next, `.(+` makes a copy of the array and rotates its elements left by one position. We do this twice and collect the copies into an array with `]`, so that our example now looks like `[[9 8 7] [8 7 9] [7 9 8]]`.
* We then sort this array of arrays with `$` and take the first element — in this case `[7 9 8]` — with `0=`. We then make a copy of this array (`.`), sort it (`$`), collect both the unsorted and the unsorted array into another array of arrays (`]`), and search for the first occurrence of the array `[7 8 9]` (which is written as `10,7>` to save two chars) in it.
* This gives us either `0` (if the unsorted array was `[7 8 9]`, and thus the chord is major), `1` (if the unsorted array was a permutation of `[7 8 9]`, which, given that its first element must be smallest, can only be `[7 9 8]`, making the chord minor) or `-1` (if even the sorted array does not equal `[7 8 9]`).
* This number is then used as a starting index into the string `"MMaijnoorr\n\n"` (where the `\n`s are given as actual linefeeds in the code), from which we take that character and every second subsequent one as the output. If the index is -1, we start from the last character of the string, which is just a line feed.

# Answer
> 4 votes
## Python, 160

```
f='A#BC D EF G3453543'.find
try:
 while 1:x,y,z=sorted(map(lambda x:f(x[0])+f(x[1:])+1,raw_input().split()));print'MMianjoorrr'[f(`y-x`+`z-y`)/14:-1:2]
except:0

```

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


# Question
Title: m3ph1st0s's programming puzzle 2 (C++): "Call hard!"
I am back with a brand new puzzle for C/C++ addicts. Following the feedback received on the 1st puzzle, this time I will try to make the requirements crystal clear and to provide a perfectly valid code.

Here is the problem. Given the following code:

```
#include <iostream>

char message[6]="hello";

void print_hello_message() {
   std::cout << message;
}

int main() {
   char* q = &message[0];

   // insert your code here
}

```

You are required to insert two more lines where the comment specifies in order to make the program print "hello" and nothing more, with the following restrictions:

1. the first line will NOT call any function, including cout
2. the second line will contain AT MOST 5 letters (and as many other symbols as you want)
3. the first line may contain new variable declarations but may not initialize them
4. the symbols # and / will not be used at all.
5. no logical operators will be used

The shortest code wins!

# Answer
In thinking about it some more, the problem states "insert two more **lines** where the comment specifies" not "**statements**". Taking that into consideration, here is another shorter answer (though it depends on how you define "the first line will NOT call any function, including cout"):

```
std::
cout<<q;

```

The first line qualifies which cout will be used, and the second line includes the actual operator that results in calling operator\<\< for the std::ostream & const char\* operands.
> 13 votes

# Answer
If I understand what you're asking for, this is what I'd add:

```
using std::cout;
cout<<q;

```

The first line brings std::cout into the current name space so that we can use it without qualification. `using namespace std;` would have worked as well but is longer so I didn't use it.

The second line uses the limit of five letters (plus three symbols and no necessary white space beyond whatever the platform uses to denote end of line).

There may be something shorter, but I can't think of it at the moment.
> 9 votes

# Answer
Use `q` to store a pointer to `print_hello_message`, then cast it back to a function pointer and invoke it.

```
q = (char *) &print_hello_message;
(*(void(*)())q)();

```

Short version:

```
q=(char*)print_hello_message;
(*(void(*)())q)();

```
> 8 votes

---
Tags: programming-puzzle
---


# Question
Title: given prime factors of a number, what is the fastest way to calculate it's proper divisors?
Given prime factors of a number, what is the fastest way to calculate divisors?

```
clc; clear;
sms=0;
count = 1;
x=0;
for i=11:28123
    fac = factor(i);
    sm = 1;
    for j = 1:length(fac)-1
        sm = sm + sum(prod(unique(combntns(fac,j), 'rows'),2));
    end
    if sm>i
        x(count) = i;
        count = count + 1;
    end
end
sum1=0;
count = 1;
for i=1:length(x)
    for j=i:length(x)
        smss = x(i) + x(j);
        if smss <= 28123
            sum1(count) = smss;
            count = count + 1;
        end
    end
end
sum1 = unique(sum1);
disp(28123*28124/2-sum(sum1));

```

currently I'm using this `prod(unique(combntns(fac,j), 'rows'),2)` code which is awfully slow and I'm using Matlab.

# Answer
# Mathematica

```
Union[Prepend[Times @@@ Rest@Subsets@l, 1]]

```

**Usage**

I'm assuming that repeated factors would be repeated in the list of factors, as below:

```
l = {2, 2, 3, 5, 5, 11, 11, 11, 31, 37, 617};
Union[Prepend[Times @@@ Rest@Subsets@l, 1]]//AbsoluteTiming

```

This routine is much slower than the built in function `Divisors`, which has to first factor the Integer. I am fairly certain that `Divisors` is compiled.

```
Divisors[282584210700]; // AbsoluteTiming

```

> {0.000262, Null}
> 1 votes

# Answer
Haskell (with `Data.List`)

```
f :: [Int] -> [Int]
f [] = [1]
f (x:xs) = a ++ map (x*) a
    where a=f xs
factorsfromlist1 = nub . sort . f
-- may have better performance
factorsfromlist2 = map head . group . sort . f

```

On the list `[2, 2, 3, 5, 5, 11, 11, 11, 17, 31, 37, 47, 67, 103, 331, 617, 1093, 1597, 2309]`:

```
$ ghc -O test.hs
$ ./test
Prime factors of 2078661171193247994962581628700
Method 1: 1.077712s
Method 2: 0.863675s

```
> 1 votes

---
Tags: fastest-code
---


title: Find an unknown very large number

text:
# Question
Title: Find an unknown very large number
Let's suppose there is a finite unknown number `n` (`n` can be very large, does not necessarily fit 64-bits; think of `BigInteger` in Java or `long` in Python) and a function `cmp(x)` that returns `true` if `x <= n`.

Write a program to determine `n` in minimum number of calls to `cmp`.

# Answer
> 2 votes
Here's my solution in C, based on “binary search”:

```
#include <stdio.h>

int cmp(long x) {
    return (x <= 727695360);
}

int main(void)
{
    char *p = (char*)cmp;

    for (;;) {
        long x = *(long*)p++;
        if (cmp(x) && !cmp(x+1)) {
            printf("%ld\n", x);
            break;
        }
    }

    return 0;
}

```

Granted, there are a number of things that could go wrong, including:

* `cmp` might compute its secret indirectly rather than using it as a literal.
* The compiler might tweak the literal to generate faster or smaller code. For example, `x <= 727695360` could become `x < 727695361`.
* The literal may be broken in half due to the target having a fixed-width instruction set. I do not expect this code to work on PowerPC.
* The target CPU might not like those unaligned `long` reads. This code will cause an address error on a 68000 CPU.

# Answer
> 7 votes
Double our guess until we exceed `n`, then do binary search. This is a reasonable approach until `n` could be very large, at which point you probably want to do more than doubling at each step.

```
b=1;
while (cmp(b)) b *= 2;
a = b/2;
while (a < b-1) {  // invariant: a <= n < b
  m = (a+b)/2;
  if (cmp(m)) {
    a = m;
  } else {
    b = m;
  }
}
return a;

```

# Answer
> 3 votes
# Clojure - 161 chars

Solution using BigInteger arithmetic and successive squaring / square roots to home in on answer. I believe this usually results in less comparisons than binary search for large values of n - typically close to the number of bits in the binary representation of the answer, which is the theoretical optimum if you only have a binary comparison available.

```
(use'clojure.contrib.math)(defn find[](loop[l 0 h nil](let[t(+(if h((exact-integer-sqrt(* l h))0)(* l l))1)](if(= l h)l(if(cmp t)(recur t h)(recur l(dec t)))))))

```

Expanded for readability:

```
(use 'clojure.contrib.math)
(defn find[]
  (loop [l 0 h nil]
    (let [t (+ (if h ((exact-integer-sqrt(* l h)) 0) (* l l)) 1)]
       (if (= l h) l
         (if (cmp t) (recur t h) (recur l (dec t)))))))

```

Note that the conciseness of the solution is considerably helped by the fact that Clojure automatically uses BigIntegers once values go outside the 64-bit long range.

In action:

```
; counter for compares
(def counter (atom 0))

; value to find
(def n 100000000000000000000000000000000000000000000000000000000)

; compare function
(defn cmp [x]
  (do
    (swap! counter inc)
    (<= x n)))

;let's find it!
(find)
=> 100000000000000000000000000000000000000000000000000000000

; how many calls to cmp?
@counter
=> 203

; how close to theoretical optimum?
(.bitLength 100000000000000000000000000000000000000000000000000000000)
=> 187

```

# Answer
> 1 votes
Assuming a uniform probability distribution:

1. Assign x to the maximum value n could be, y to the minimum value
2. Guess n=ceiling((x+y)/2)
3. If cmp returns true, y = the guess; else x = the guess - 1
4. If x=y, done (n=x=y); else goto (2)

# Answer
> 1 votes
A solution in pseudocode (assuming x is nowhere near 0):

```
x=0
#Step 1: get upper and lower bounds on the number of digits
#double the number of digits until we go past the number
while cmp(2**(2**x)): x++
mindgt=2**(x-1)
maxdgt=2**x
#Step 2: find bounds on log(number)
while(maxdgt-mindgt!=1):
    n=(mindgt+maxdgt)/2
    if cmp(2**n):
        mindgt=n
    else:
        maxdgt=n
min=2**mindgt
max=2**maxdgt
#Step 3: straightforward binary search
while(max!=min):
    n=(max+min)/2
    if(cmp(n)):
        mindgt=n
    else:
        maxdgt=n-1
print max

```

For a value on the order of 1e40, this method takes 9 calls on step #1, 7 calls on step #2 and about 133 calls in step #3 for a total of 149.

# Answer
> 0 votes
Simple non-golf binary search:

```
num = 110134848298567717 # sample number
guess = 1
inc = 1
halved = 0
calls_to_cmp = 0

def my_cmp(x, n):
    global calls_to_cmp
    calls_to_cmp += 1
    return x <= n

while True:
    small = my_cmp(guess, num)
    if small: # add to guess, increase search field
        inc *= 2
        guess += inc
    else: # subtract from guess, decrease search field
        inc /= 2
        guess -= inc
    print "Guess: ", guess, ", inc: ", inc, "  calls so far: ", calls_to_cmp
    if inc == 0:
        break

print "Done."

```

One thing to consider is to initially try tripling or quadrupling for the first few loops: this will determine if the number is "small" (say under 1 million) or "large" and may speed the search up.

# Answer
> 0 votes
Just to be a cheeky bugger:

# JavaScript, 34 chars

calls to `cmp`, *technically* 0

```
c=cmp
i=0
while(c(++i));
alert(i-1)

```

**NOTE**: JavaScript isn't a reasonable language to perform this in as it is restricted to 64-bit numeric values, so a string library would be necessary for managing larger numbers.

---
Tags: code-challenge, math
---


title: Make an HTML page goto infinite loop?

text:
# Question
Title: Make an HTML page goto infinite loop?
Write a code using HTML, JavaScript, jQuery to make the page go into infinite loop.

Restrictions:

No looping or control structures of javascript and jQuery allowed. You can only use alert, events, etc.

# Answer
```
$($);

```

May not meet your conditions, but I like it. (And it does crash your browser.)

More information about this: Why does $($) crash my page?
> 8 votes

# Answer
How about a meta refresh?

```
<meta http-equiv=refresh content=1>

```

I removed the quotation marks around the parameter values because code golf.
> 3 votes

# Answer
This reloads the page as soon as it loads:

```
<html>
<head>
<script>window.location=window.location</script>
</head>
</html>

```

Or you could bring up infinite alert boxes (until the user disables them):

```
<html>
<body onfocus="alert('')"></body>
</html>

```
> 2 votes

# Answer
This will reload the browser indefinitely:

```
location.reload()

```

(Unless the browser specifically blocks repeated reloads.)
> 2 votes

---
Tags: code-challenge, javascript
---


# Question
Title: m3ph1st0s's programming puzzle 4 (C/C++): “3-way swap”
My last puzzle has generated some confusion and controversy so I decided to give up, for now, on those "replace one character"-type puzzles.

Hope this 4th puzzle will redeem myself after all the edits in puzzle 3 and will put your brains at work once more.

I've really put up all the effort to make this one as clear as possible and hope you will enjoy it!

So here it goes:

We start from a very short C program:

```
int main() {
   int a = 93;
   int b = 11;
   int c = 22528;

   // insert your code here

}

```

Your job will be to swap the values of the variables a,b,c like this: a \<= b, b \<= c, c \<= a. To make it even more clear: new a = old b, new b = old c, new c = old a.

You are required to do this by inserting **one single instruction** in the line indicated by the comment in the code. To be clear once again, this line will contain only one semicolon (;) indicating the end of the lone instruction. After the execution of this program, a will contain 11, b will contain 22528, c will contain 93. However, there are some conditions that need to be met. So we'll have 4 different puzzles with different cryteria.

**4.1.** Do it by using whatever you want. Just one statement. -\> **most creative** solution wins this one.

**4.2.** Do it without using any comma (,). -\> **most creative** wins

**4.3.** Do it without any comma and with no more than 4 letters (+any other characters). -\> **shortest** code wins

**4.4.** Do it without any comma and with no more than 4 letters and no more than 4 digits (+any other characters). -\> **shortest** code wins

To make sure you understood, here's some code that is **valid** under the condition required but does not solve the problem:

4.1:

```
I_hereby_call_my_beautiful_function(nice_argument), int q=w, who_the_hell_is(w)+1;

```

4.2:

```
one = single + assignment;

```

4.3:

```
int w=12345678;

```

4.4:

```
int w=1234;

```

P.S. In case you haven't already noticed, 4.4 is the tough one here (I hope :D).

# Answer
## 4.4 21 19 characters

**Edit:** Now meets all the criteria for 4.4.

```
c=(b<<=a>>=3)>>8|5;

```
> 6 votes

# Answer
For 4.4 (14 characters, 1 digit and 4 letters):

```
int main()
{
  int a = 93;
  int b = 11;
  int c = 22528;

  b<<=a=(c=a)/8;
}

```

VS2010 with /Wall didn't show any warnings, but I'm still a bit suspicious about using `a` twice in there (even though it's only modified once).
> 7 votes

# Answer
Classic inplace exchange (20 chars without spaces, category 4.1, 4.2):

```
c ^= b ^= c ^= b ^= a ^= b ^= a;

```

Total exist 9 xor-chains that implement this 3-way exchange

```
c ^= b ^= c ^= b ^= a ^= b ^= a;
c ^= a ^= c ^= b ^= c ^= b ^= a;
c ^= b ^= a ^= b ^= a ^= c ^= a;
a ^= c ^= b ^= c ^= b ^= a ^= b;
a ^= b ^= a ^= c ^= a ^= c ^= b;
a ^= c ^= a ^= c ^= b ^= c ^= b;
b ^= c ^= b ^= a ^= b ^= a ^= c;
b ^= a ^= b ^= a ^= c ^= a ^= c;
b ^= a ^= c ^= a ^= c ^= b ^= c;

```

and to continue of Gareth idea (No commas, 3 letters, 4 digits)

```
c=(b<<=a>>=3)/242;

```
> 4 votes

---
Tags: code-golf, code-challenge, c++, c
---


title: Print integers in any base up to 36

text:
# Question
Title: Print integers in any base up to 36
> **Possible Duplicate:**
> Integer to string with given radix

This question is inspired by Pythons builtin `int` function. `int` is used to convert other numbers or strings into integers. If you are converting a string you can provide the additional parameter `base`, that contains the base that your number is represented in within the string:

```
>>> int('137')
137
>>> int('137',base=8)
95
>>> int('ff',base=16)
255
>>> int('1AZ',base=36)
1691

```

Unfortunately Python doesn't provide a function for the reverse case, where you want to convert a number into a string in a specific base.

Your task is to write such a function.

* the function may return the value or print it
* you must provide support for all bases between 2 and 36
* digits to use are `0123456789abcdefghijklmnopqrstuvwxyz`
* all languages are allowed
* built in functions for this purpose are boring and thus forbidden
* shortest code wins

# Answer
> 2 votes
## APL (25)

```
{(⎕D,⎕A)[1+⍵⊤⍨⍺⍴⍨⌈⍺⍟⍵+1]}

```

The left argument is the base, and the right argument is the number.

i.e.

```
    16{(⎕D,⎕A)[1+⍵⊤⍨⍺⍴⍨⌈⍺⍟⍵+1]}1234
4D2

```

# Answer
> 3 votes
## Befunge, 17x4 = 68 characters

```
1-&00p&>:!#v_:00v
v-10<  ^/g00\%g <
< >:^@_.# #$v#:!`
"_^#`9::$  <<,+"W

```

Online interpreter: http://www.bedroomlan.org/tools/befunge-93-playground

First input is base, second is number.

Similar to other solutions here this does not output anything when the number is 0. I may look at fixing this at some point.

# Answer
> 3 votes
## C, 68

```
c(n,b,r){char*p=1+&r;for(r=0;n;n/=b)*--p=n%b+48+(n%b>9)*39;puts(p);}

```

testing:

```
main(){
  c(65,2);
  c(100,30);
  c(57005, 16);
}

```

output:

```
1000001
3a
dead

```

issues:

* 0 is printed as empty string.
* potential buffer overflows due to abuse of 'int' as a char array...
* works with Apple clang v4.0 - your milage may vary with other compilers.

# Answer
> 2 votes
## Python, 81 58 bytes

```
x=lambda n,b:(n/b and x(n/b,b)or'')+chr(48+n%b+39*(n%b>9))

```

Usage: `x(100,30)` returns `'3a'`, which is 100 in base 30.

# Answer
> 2 votes
## PHP, 92 Bytes

Quite new to code-golf, so probably can do better than this (suggestions would be very welcome!)

```
function b($n,$b){while($n>0){$r=$n%$b;$n=floor($n/$b);$s=($r>9?chr(87+$r):$r).$s;}echo$s;}

```

With (some) whitespaces:

```
function b($n,$b)
{
  while ($n>0)
  {
    $r=$n%$b;
    $n=floor($n/$b);
    $s=($r>9?chr(87+$r):$r).$s;
  }
  echo $s;
}

```

# Answer
> 2 votes
# C, 48 chars

```
i(n,b){n?i(n/b,b),putchar(n%b+48+(n%b>9)*39):0;}

```
* input of 0 produces empty string

# C, 77 49 chars, prints `0` for zero

```
I(n,b){putchar(n?i(n/b,b),48+n%b+(n%b>9)*39:48);}

```

To run, call i for first version, I for second.

# Answer
> 1 votes
## C# – 85 characters

```
string F(int n,int b){var s="";for(;n>0;n/=b)s=(char)(n%b+(n%b>9?87:48))+s;return s;}

```

# Answer
> 1 votes
## VBA, 99

(70 if you take out the function/endfunction lines)

```
Function F(a,b)
F="":q=a:Do:c=q Mod b:F=Chr(c+48-39*(c>9))&F:q=Int(q/b):Loop Until q=0
End Function

```

fixed for case when **a=0**

# Answer
> 1 votes
# Ocaml, 98 or 120

It prints out a leading zero, though. Usage: `16-0xBEEF`

```
let rec(-)b=function|0->"0"|n->b-n/b^String.make 1(Char.chr(n mod b+if n mod b>9 then 55 else 48))

```

Unfortunately a lot of characters are spent on converting to char then to string :/

This one is correct.

```
let rec(-)b=function|0->"0"|n->(if 0=n/b then""else b-n/b)^String.make 1(Char.chr(n mod b+if n mod b>9 then 55 else 48))

```

The strong typing in ocaml is sometimes unfortunate when golfing. Partial application and such somewhat make up for it, though.

# Answer
> 1 votes
## CoffeeScript (98 92)

```
z=(i,b)->a=parseInt(i)%b;return''if 1>i;(z i/b,b)+if a>9then String.fromCharCode(a+87)else a

```

The compiled (and readable) javascript for the interested:

```
z = function(i, b) {
  var a;
  a = parseInt(i) % b;
  if (1 > i) {
    return '';
  }
  return (z(i / b, b)) + (a > 9 ? String.fromCharCode(a + 87) : a);
};

```

What can I say? Unnecessary recursion gets me hot.

This could have been far shorter if I knew a shorter way to floor or convert from ASCII in Coffee-/Javascript. Tips would be greatly appreciated.

**Edited** to include "parseInt" to save a couple of characters on "Math.floor" and with some rearranging to reduce the "if ... then ..."s. Unfortunately, I don't think there even is a shorthand if in CoffeeScript ( "... ? ... : ..." doesn't work).

---
Tags: code-golf
---


title: Make a simple IRC bot.

text:
# Question
Title: Make a simple IRC bot.
## Task

> Make a simple IRC bot which does simple task like greeting user.

## Detail

(You may see this RFC document.)

Write a complete program that perform these:

1. The program inputs `nickname` and `realname` from the user.

* All `nickname` and `realname` which form is `[A-Za-z0-9]+` should be allowed, but it isn't important whether other forms are allowed. For example, if the user wants `1234qwerty` as `nickname` and `5319009` as `realname`, the program should use those names, but it isn't important whether the program can use `^^☆Rick Astley☆^^` (which includes non-alphabet&decimals) as (`nickname` or `realname`) or not, even thought this name may be rejected by the server.

2. The program inputs `serverAddress` from the user.

* The form of `serverAddress` is `serverIP:serverPort`, where `serverIP` is the IP address of the server and `serverPort` is the port num of the server.

3. The program connects to port `serverPort` at IRC server `serverIP`, and it should set it's nickname as `nickname` and realname as `realname` by sending `USER realname 0 * :realname` and `NICK nickname`.
4. The program inputs a single `channelName` which doesn't include `#`, and join to the channel `#channelName`.
5. Send a private message `Hello, world!` to the `#channelName` channel like this: `PRIVMSG #channelName :Hello, world!`
6. Then, the program does these:

A. If someone joins, greeting him by saying `Hello, @!` to `#channelName`, where @ is the nickname of him/her.

B. If the program is kicked, try re-joining.

C. If a person is kicked or banned, say `POW HAHA`.

D. If a person leaves (`PART` or `QUIT`), say `Goodbye, @!`, where @ is the nickname of him/her.

E. If someone says some text including `Turing test` or `turing test`, say `I'm a human!`.

F. If someone says some text including `6*9`, quit by sending `QUIT :42` to the server.

G. If someone says some text including `all your base are belong to us`(case-insensitive), quit by sending `QUIT :What you say!` to the server.

H. If someone says some text preceding with a space and above acts aren't performed by the text, say the sum of charcode of all (except the first space) chars in the text.

## If an error is occurred

If an error (such as connection error or invalid `nickname`) is occurred, you can do what you want to do. For example, if the `nickname` is already in use, the program may stop, gets a new `nickname` from the user, or automatically change the `nickname` and retry.

## Restriction

The program

* Should not use any internal functions or libraries which is for IRC client/bot making. i.e. something like IRC client libraries
* Should **prompt what it'll input, before it gets an input**. For example, before inputs `serverAddress`, it should prompt `Write the address of server:`, `serverIP:serverPort >` , `serverAddress >`, or some text that the user can recognize.
* Should work on several IRC servers using UTF-8. (i.e. not for single server)
* 's messages send to server shouldn't be `NOTICE`. (RFC 2812, 3.3.2 Notice : The difference between `NOTICE` and `PRIVMSG` is that automatic replies MUST NEVER be sent in response to a `NOTICE` message.)
* Should send a message where the request came from (`#channelName` or `nickname`).
* Should `PONG` when `PING`ed, of course.

## PS

Well, I just made this, because there was no puzzle about IRC bot.

## Edit

After reading @dmckee's comment, I changed the rule for choosing winner.

1. Default `bonus` = +0
2. If somehow the program can connect to a channel (even if it's not `#channelName`), `bonus` = 1
3. If the program can perform step 1~5, `bonus` \*= 2.
4. For each tasks A~H in step 6, if the program implements, `bonus` \*= `1.2`.
5. For each six restrictions, if the program follows that, `bonus` \*= `1.05`.

and `score = int(codelength/bonus)`.

Program with lowest score is winner. If two answers have same score, then the answer with highest votes wins.

EDIT Edit : I think `1.2` and `1.05` in step 4 and 5 should be adjusted slightly bigger.. What do you think about this?

The winner is decided, however, I think there was too few entries.

Anyone still may submit the code.. :P

# Answer
> 1 votes
# PHP - 121 points

* 1396 characters
* Follows all steps (including extra) and restrictions

## Score

```
<?php
$bonus = 1;                             //connects to channel
$bonus *= 2;                            //completes steps 1-5
for ($x=0;$x < 8;$x++) $bonus *= 1.2;   //all 8 extra steps
for ($y=0;$y < 6;$y++) $bonus *= 1.05;  //all 6 restrictions
echo (int)(1396 / $bonus);

> 121

```

## Code

```
<?php function w($t){global$s;echo$t."\n";socket_write($s,$t."\r\n");}function m($c,$t){w("PRIVMSG $c :$t");}@$y=fgets;$z=STDIN;echo"nickname>";$n=trim($y($z));echo"realname>";$r=trim($y($z));echo"serverIP:Port>";$a=explode(":",trim($y($z)));$s=socket_create(2,1,6);socket_connect($s,$a[0],$a[1]);w("NICK $n");w("USER $n 0 * :$r");while(1){if((!($l=trim(socket_read($s,512,1))))||(!preg_match("/^(?:\:(\S+)[ ]+)?([^: ][^ ]*)(?:[ ]+([^:].*?))?(?:[ ]+:(.+))?$/",$l,$m)))continue;echo$l."\n";if(preg_match("/(.+)!(.+)@(.+)/",$m[1],$o))$m[1]=$o;if(!empty($m[3]))$p=explode(" ",$m[3]);else$p=array();if(isset($m[4])) $p[]=$m[4];$p=array($m[1],$m[2],$p);$b=$p[2][0];@$e=$p[0][1];@$f=$p[2][1];if($p[1]=="PING")w("PONG :".$b);elseif($p[1]=="376"){echo"#channel>";$c=trim($y($z));$c=(!empty($c))?$c:"#rintaun";w("JOIN $c");}elseif($p[1]=="JOIN")if($e!=$n)m($b,"Hello, $e!");else m($b,"Hello, world!");elseif($p[1]=="KICK")if($f!=$n)m($b,"POW HAHA");else w("JOIN ".$b);elseif(($p[1]=="PART")&&($e!=$n))m($b,"Goodbye, $e!");elseif(($p[1]=="QUIT")&&($e!=$n))m($c,"Goodbye, $e!");elseif($p[1]=="PRIVMSG")if(preg_match("/[Tt]uring test/",$f))m(($b==$n)?$e:$b,"I'm a human!");elseif(strstr($f,"6*9")){w("QUIT :42");break;}elseif(stristr($f,"all your base are belong to us")){w("QUIT :What you say!");break;}elseif($f[0]==" "){$q=str_split(substr($f,1));$u=0;foreach($q AS $d)$u+=ord($d);m(($b==$n)?$e:$b,$u);}}

```

### Side Note

My answer actually differs from the instructions very slightly; the instructions say to use the `realname` as the first parameter to the `USER` command when registering, but I used the nickname instead. This is because the `realname` is allowed to have spaces, while this parameter is not. It's something of a moot point, though, since switching in the variable for `realname` would be the exact same character count.

# Answer
> 5 votes
# Python - 125 points

* 304 chars
* follows steps 1-5 (works for me on irc.freenode.net:6667. if you try there, remember IDENT might take a while, so give it 20+ seconds to connect and speak)
* follows 4 restrictions (assuming the NOTICE restriction which is a bit unclear. the UTF restriction counts because python won't choke if it doesn't need to parse any UTF).

## score math (python):

```
bonus = 1 # connects to channel
bonus *= 2 # steps 1-5
for i in xrange(4):
    bonus *= 1.05 # 4 restrictions

int(304.0/bonus)
> 125

```

## code:

```
import socket
i=raw_input
u=i('user# ')
n=i('nick# ')
h,p=i('host:port# ').split(':',1)
p=int(p)
c='#'+i('chan# ')
z=0
while 1:
 try:
  def s(m): z.send(m+'\r\n')
  z.recv(9)
 except:
  z=socket.socket();z.connect((h,p));s('USER '+n+' 0 * :'+n);s('NICK '+n);s('JOIN '+c);s('PRIVMSG '+c+' :Hello, world!')

```

# Answer
> 5 votes
# Perl, 66 points

* 666 characters
* all substeps
* half of the restrictions

## Score

```
use 5.010;
$bonus = 1;              # connects to channel
$bonus *= 2;             # steps 1 to 5
$bonus *= 1.2 for 1..8;  # substeps A to H
$bonus *= 1.05 for 1..3; # restrictions 3, 4, 6
say int(666 / $bonus);
> 66

```

## Code

(newlines for presentation only, not counted let alone acceptable)

```
use POE"Component::IRC";$_='sub _start{Zregister,all);Z"connect")}subX001{
Zjoin=>$c);ZY"Hello, world!")}*Xquit=*Xpart=*Xjoin=sub{$g=$_[STATE]=~/t/?G
oodbye:Hello;$_=$_[ARG0];/\w+/;ZY"$g, $&!")};subXkick{$_=$_[ARG2];/\w+/;Z$
&eq$n?"join":Y"POW HAHA")}subXpublic{$_=$_[ARG2];if(/turing test/i){ZY"I\'
m a human!")}elsif(/6\*9/){Zquit,42)}elsif(/all your base are belong to us
/i){Zquit,"What you say!")}elsif(/^ /){$t=-32;$t+=ord for/./g;ZY$t)}}chop(
($n,$r,$s,$c)=<>);$c="#$c";$i=POE::Component::IRC->spawn(nick,$n,ircname,$
r,server,$s)';s/Z/\$i->yield(/g;s/Y/privmsg,\$c,/g;S/X/ irc_/g;eval;POE::S
ession->create(package_states,[main,[grep*$_{CODE},%::]]);POE::Kernel->run

```

**Side Note**

The "ALL YOUR BASE ARE BELONG TO US" substep is most probably not worth its character count, but if I dropped it I wouldn't have the nice character count. Bugger.

# Answer
> 2 votes
# Ruby, 65 points

* 574 Chars
* Steps 1-5, 6(A-G) and restrictions on libs, UTF-8, no NOTICE & PONG
* Takes commandline args in the form of server:6667 botnick botuser channel

# Score

```
bonus = 0       # We've done nothing yet
bonus += 1      # Connects to channel
bonus *= 2      # Step 1 - 5

for n in 1..7
    bonus *= 1.2    # A - G
end

for n in 1..4
    bonus *= 1.05   # 4 constraints
end

puts (574/bonus).to_i
> 65

```

# Code

```
require'socket'
a=ARGV
c="##{a[3]}"
h,p=a[0].split':'
s=TCPSocket.open(h,p)
m="PRIVMSG #{c} :"
s.puts"USER #{a[2]} 0 * :#{a[2]}\nNICK #{a[1]}\nJOIN #{c}\n#{m}Hello, world!"
while l=s.gets
case l
when/\:(.+?)!(.+)JOIN/
s.puts"#{m}Hello, #{$1}!"
when/KICK (.+?) (.+?) \:(.+)/
if $2==a[1]
s.puts"JOIN #{c}"
else
s.puts"#{m}POW HAHA"
end
when/\:(.+?)\!(.+)(PART|QUIT)/
s.puts"#{m}Goodbye, #{$1}!"
when/turing test/i
s.puts"#{m}I'm a human!"
when/6\*9/
s.puts"QUIT :42"
when/all your base are belong to us/i
s.puts"QUIT :What you say!"
when/PING \:(.+)/
puts"PONG #{$1}"
end
end

```

# Answer
> 2 votes
# Ruby, 28 points

# Score

```
bonus = 0       # We've done nothing yet
bonus += 1      # Connects to channel
bonus *= 2      # Step 1 - 5

for n in 1..7
    bonus *= 1.2    # A - G
end

for n in 1..4
    bonus *= 1.05   # 4 constraints
end

puts (249/bonus).to_i
>  28

```

# Code

```
require 'zlib'
b=<<'E'
x�]�_o�0���)��q�-KFBcdf��߃�P�S�B�����(N�Л��s~�� ��(�_$U6��5G�)�r�BB������J�{��� nNhlO�f)QQdJ�g��'�yP�!!����K�ɫ��[Ё�Ə{0�F]ѽ�m�2���GŐP��p`   ��I����E�+�* z�                                                                                )jrmKR�ˮ�%�
#��nQaJ�H��<�ZT���虦T3.�$D('�hw��a�/'��&�_ei�}o��1���M$����H��J�$��������V"���"��'��|A�`<��3L)Y��Z|� e�� ���m�é��ǚ�ڎu��J�����Vq~(ح�
E
eval Zlib::Inflate.new.inflate b

```

---
Tags: code-golf, internet
---


title: Finding limits of functions

text:
# Question
Title: Finding limits of functions
A **limit** in math determines the value that a function `f(x)` **approaches** as `x` gets closer and closer to a certain value.

Let me use the equation `f(x)=x^2/x` as an example.
Obviously, `f(x)` is undefined if x is 0 (x=0, x2=0, 0/0 is undefined).
But, what happens when we calculate `f(x)` as `x` approaches 0?

`x=0.1, f(x)=0.01/0.1 = 0.1`
`x=0.01, f(x)=0.0001/0.01 = 0.01`
`x=0.00001, f(x)=0.0000000001/0.00001 = 0.00001`
We can easily see that `f(x)` is approaching 0 as `x` approaches 0.

What about when `f(x)=1/x^2`, and we approach 0?

`x=0.1, f(x)=1/0.01=100`
`x=0.01, f(x)=1/0.0001=10000`
`x=0.00001, f(x)=1/0.0000000001=10000000000`
As `x` approaches 0, `f(x)` approaches positive infinity.

You will be given two things in whatever input format you like:

* `f(x)` as an `eval`-able string in your language
* `a` as a floating point

Output the value that `f(x)` approaches when `x` approaches `a`. Do not use any built-in functions that explicitly do this.

**Input Limitations:**

* The limit of `f(x)` as `x` approaches `a` will always exist.
* There will be real-number values just before and just after `f(a)`: you will never get `f(x)=sqrt(x), a=-1` or anything of the sort as input.

**Output Specifications:**

* If `f(x)` approaches positive or negative infinity, output `+INF` or `-INF`, respectively.
* If `f(a)` is a real number, then output `f(a)`.

**Test Cases:**

```
f(x)=sin(x)/x, a=0; Output: 1
f(x)=1/x^2, a=0; Output: +INF
f(x)=(x^2-x)/(x-1), a=1; Output: 1
f(x)=2^x, a=3; Output: 8

```

Shortest code wins. Good luck!

# Answer
## Python ~~146~~ 185

Figured I'd post the obvious answer before anyone else does. Note, reads two lines from `stdin` with `f(x)` on the first and `a` on the second.

**Edit:** Made it actually work, as per `beary`'s comment **Edit 2:** `i` is much smaller, so there are much fewer inputs that it should fail for.

```
from math import*
f,a,i=eval("lambda x:"+input()),eval(input()),2e-308
while 1:
 try:
     r=str(f(a+i)).upper()
     if'NAN'!=r:break
 except:
     i*=-2
print('I'==r[0]and'+'+r or r)

```
> 0 votes

# Answer
## C, 402 bytes

Plenty of room for golfing, just proof of concept to begin with :P

Compiles under clang, osx.

Note: For linux you may have to change the code to use something like: "ld -shared f.o -o f.so -lm"

```
#include<dlfcn.h>
#include<stdio.h>
float e,r;
main(int i,char**v){
    // create and compile temporary c file for 'f(x)'
    // note: include offset within function
    FILE*s=fopen("f.c","w");
    fprintf(s,"#include<math.h>\nfloat f(float x){x+=%s;return %s;}",v[2],v[1]);
    fclose(s);
    system("cc -fPIC -c f.c;ld -bundle f.o -o f.so -lm");
    float(*f)(float)=dlsym(dlopen("f.so",0),"f");

    for(i=0;1;e=(e==0)?1e-37:e*2){
        r=f(e);
        if(isinf(r))i=1;else if(!isnan(r)){
            i?printf("%cINF\n",r>0?43:45):printf("%f\n",r);
            break;
        }
    }
}

```

Run as:

```
./a.out "sin(x)/x" 0
./a.out "1/(x*x)" 0
./a.out "(x*x-x)/(x-1)" 1
./a.out "pow(2,x)" 3

```

Results:

```
1.000000
+INF
1.000000
8.000000

```
> 4 votes

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


title: The real knapsack problem

text:
# Question
Title: The real knapsack problem
Given

* the number of goods N
* positive weight of each good weight\[N\]
* positive profit of each good profit\[N\]
* and a positive number W which is the knapsack capacity.

This problem is called “the zero-one knapsack” for choosing the most beneficial goods for the knapsack of limited capacity.

## Example:

* The number of goods (items) : 5
* Weight of each item (kg) : {2, 3, 5, 7, 8} which apply to item 1, item 2, ...... item 5 in that order
* Value of each item (10,000 yen) : {2, 4, 8, 9, 10} which apply to item 1, item 2, .... item 5 in that order
* Capacity of the knapsack : 10 kg

Among the five goods:

```
Goods chosen            Total weight    Total value
Goods 1, 2 and 3    2 + 3 + 5 = 10  2 + 4 + 8 = 14   <- Maximum

```

# Answer
# Python, 236 Charaters

Okay, I guess I'll bite.

```
from itertools import *
def k(w,p,c):
    n=len(w)
    r=range(n)
    return max(filter(lambda y:y[1]<=c,[(s,sum(map(lambda y:w[y],s)),sum(map(lambda y:p[y],s))) for s in chain.from_iterable(combinations(r,u) for u in r+[n])]),key=lambda y:y[2])[0]

```

### Usage

The `k` function takes three arguments: a list containing the weights, a list containing the profits, and the capacity of the knapsack. Here is how to call it given the example above:

```
> print k([2,3,5,7,8], [2,4,8,9,10], 10)
(0, 1, 2)

```

Meaning that items 0, 1, and 2 are the optimal solution.
> 1 votes

---
Tags: optimization
---


# Question
Title: Storing a DNS name as compactly as possible in memory (preferably in C#)
What is the most compact way to encode/save DNS names in memory?

For example, storing "www.google.com" as a string in .NET will result in the object being encoded as UTF-16, and it will consume twice as much memory as plain ASCII... but for the purpose of storing DNS names, ASCII is overkill.

The only characters that are needed are:

* A..Z (case insensitive)
* 0..9
* Hyphen
* underscore
* period
* Asterisk (not legal DNS, but used in ACLs such as \*.google.com) always as a leading character, never elsewhere.

A total of 40 characters.. which fits within single byte with plenty room to spare.

My code golf question/challenge is what is the most compact way to store a string of characters in memory and maximizing in memory storage?

The inspiration for this challenge came from this blog entry.

# Answer
> 3 votes
You could interpret it as a base 39 number. Since only the first character can be an asterisk, you can encode it as the sign. If i use the characters as digits in the order you named them, `www.google.com` would be `10903065870001232914011` in decimal and `24f0e6f41d8ecd3a65b` in hex, which could be stored in 10 bytes.

`*.google.com` would be `-310664672884413873` in decimal and `fbb04c2040762a4f` in hex, if you store it in 8 bytes.

# Answer
> 0 votes
Oh, that's easy. You just zip it.

---
Tags: string, compression, c#
---


title: Domino Effect Problem

text:
# Question
Title: Domino Effect Problem
Last week we had a programming contest in my university and I am very curious about one of the problems , one which only one team (but from another city) was able to solve. Maybe its not that hard, but I cant find any solutions that will take less than a second of execution time. The problem is the following:

# Problem

You have **N** domino tiles separated by different amounts (integer values that are given to you) and you know the height **H** of these tiles (all have the same height). They are all placed standing up so that if you push one it falls in the direction of the next one. This way, if tile **I** is close enough (**H** or less) to tile **I**+1, the first one will push the second one when it is pushed down, producing the domino effect. Suppose that not all the distances that separate the tiles are smaller than **H**, what's the minimum amount of moves you need to make in order to have all the distances be at most **H**? You can't move the first nor the last tile. Print a falsey value if it is not possible.

**Note:** You are only allowed to move integer amounts and only to spots on the line defined by tile i-1 and tile i+1. This means you cant grab one and place it wherever you want.

**Here are the input sizes:** **(3 ≤ N ≤ 1000) (1 ≤ H ≤ 50)** and the distances **(1 ≤ Di ≤ 100 for i = 1, 2, ..., N-1).** Someone uploaded it to SPOJ recently

> **Input:**
>
> N H
>
> d1 d2 d3 d4 ... d(n-1)
>
> **Output:**
>
> Minimum amount of moves.

**Sample**

> **Input1**
>
> 8 3
>
> 2 4 4 1 4 3 2
>
> **Output1**
>
> 3

Sample2

> **Input2**
>
> 10 2
>
> 1 2 2 2 2 2 2 2 3
>
> **Output2**
>
> 8

Sample3

> **Input3**
>
> 5 2
>
> 2 2 2 2
>
> **Output3**
>
> 0

Sample4

> **Input4**
>
> 5 3
>
> 1 6 2 4
>
> **Output4**
>
> -1 (NOT POSSIBLE)

I have only found a good solution for two cases (Pseudo-Code):

```
D=sum_of_all_distances
MaxPossible=(N-1)*H

if D==MaxPossible and there is no di such that di>H
    Answer=0

else if D>MaxPossible
    Answer=-1

```

# Answer
## Python

```
N, H = map(int, raw_input().split())
D = map(int, raw_input().split())

# map from (number of dominoes, distance to last domino) to
# the number of moves needed to adjust the first number of dominoes
# exactly that far.
M = {}
M[1,0] = 0

for i in xrange(2, N+1):      # i = number of dominos to try
  for d in xrange(H*(i-1)+1):
    M[i,d] = 1e9
  for d in xrange(H*(i-1)+1): # position of last domino
    for e in xrange(1, H+1):  # distance from last domino to previous one
      if d-e > H*(i-2): continue
      if d-e < 0: continue
      if sum(D[:i-1]) == d:
        # don't move last domino, arrange rest
        M[i,d] = min(M[i,d], M[i-1,d-e])
      else:
        # arrange rest, move last domino to right location
        M[i,d] = min(M[i,d], 1 + M[i-1,d-e])

print M.get((N,sum(D)), -1)

```

Standard dynamic programming. Runs pretty much instantaneously on the example inputs. How big a problem do we have to solve in under a second?
> 2 votes

# Answer
### I tried in Perl which tries immediate tile distance adjustment and then cascading movements to get required distance

Execution syntax perl programName N H d1 d2 ... dn-1
Test cases sample: perl domino\_slider.pl 8 3 2 4 4 1 4 3 2 output :3
```
use subs /dominochecker distancechecker subcheckright subcheckleft RigidMode/;

## Receive Input Tile Height D1 D2 ... Dn-1
$Tiles=$ARGV[0];
$Height=$ARGV[1];
$loop_count=0;
for $i (2...$#ARGV){
   $distance[$loop_count]=$ARGV[$i];
   $loop_count++;
}

$loop_count=$move=0;

sub dominochecker {
   $lc=0;$retflag=0;
   while ($lc<$Tiles-1) {
     if ($distance[$lc]>$Height) {
         $retflag=1;
     }
     $lc++;
   }
   return $retflag;
}

sub subcheckleft {
   $lc=0;$retflag=0;$c=$_[0];
   while ($lc<$c) {
     if ($distance[$lc]>$Height) {
         $retflag=1;
     }
     $lc++;
   }
   return $retflag;
}

sub subcheckright {
   $retflag=0;$c=$_[0];
   while ($c<$Tiles-1) {
     if ($distance[$c]>$Height) {
         $retflag=1;
     }
     $c++;
   }
   return $retflag;
}

$loop_count=$move=0;

if (dominochecker==0) { ## if already in Domino Effect
print "\n $move \n";
exit;
}

sub RigidMode{
$loopend=$_[0];
$loop_count_local=0;
while ($loop_count_local<$loopend) {
  if ($distance[$loop_count_local]<=$Height) {
    $loop_count_local++;
  } else {
    if ($distance[$loop_count_local-1]<$Height && $loop_count_local+1 !=1 && defined($distance[$loop_count_local-1]) ) {
       $move++;
       $available=$Height-$distance[$loop_count_local-1];
       $required=$distance[$loop_count_local]-$Height;
       if($available<=$required) {
       $distance[$loop_count_local-1]=$distance[$loop_count_local-1]+$available;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$available;
       }else{
       $distance[$loop_count_local-1]=$distance[$loop_count_local-1]+$required;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$required;
       }
       $loop_count_local=0;
    }elsif($distance[$loop_count_local+1]<$Height && $loop_count_local+2 !=$Tiles && defined($distance[$loop_count_local+1]) ){
       $available=$Height-$distance[$loop_count_local+1];
       $required=$distance[$loop_count_local]-$Height;
       if($available<=$required) {
       $distance[$loop_count_local+1]=$distance[$loop_count_local+1]+$available;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$available;
       }else{
       $distance[$loop_count_local+1]=$distance[$loop_count_local+1]+$required;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$required;
       }
       $move++;
       $loop_count_local=0;
    }
    else{
    $loop_count_local++;
    }
  }
}
}

RigidMode($Tiles-1);

if (dominochecker==0) {
    print "\n $move \n";
    exit;
}else{
    $loop_count=$move=0;
    for $i (2...$#ARGV){
        $distance[$loop_count]=$ARGV[$i];
        $loop_count++;
    }
    $loop_count=$move=0;
    while ($loop_count<$Tiles-1) {
    if ($distance[$loop_count]<$Height) {
       $available=$Height-$distance[$loop_count];
       if (subcheckleft($loop_count)>0){
         $move++ if $distance[$loop_count-1]-$available>0;
         $distance[$loop_count]=$Height if $distance[$loop_count-1]-$available>0 ;
         $distance[$loop_count-1]=$distance[$loop_count-1]-$available if $distance[$loop_count-1]-$available>0;
         RigidMode($loop_count+1);
         $loop_count=0 if $distance[$loop_count-1]-$available>0;
         $loop_count++ if $distance[$loop_count-1]-$available<=0;
       }elsif(subcheckright($loop_count)>0) {
         $move++ if $distance[$loop_count+1]-$available>0;
         $distance[$loop_count]=$Height if $distance[$loop_count+1]-$available>0;
         $distance[$loop_count+1]=$distance[$loop_count+1]-$available if $distance[$loop_count+1]-$available>0;
         RigidMode($loop_count+1);
         $loop_count=0 if $distance[$loop_count+1]-$available>0;
         $loop_count++ if $distance[$loop_count+1]-$available<=0;
       }else{
         $loop_count++;
       }
    }else{
         $loop_count++;
    }
    }
}

if (dominochecker==0) {
    print "\n $move \n";
    exit;
}
else{
    print "\n -1 \n";
    exit;
}

```
> 1 votes

---
Tags: code-challenge
---


title: Implementing a Traffic Light Checker

text:
# Question
Title: Implementing a Traffic Light Checker
A three-color traffic light must switch lights in the following order: red, green, yellow, red.

To indicate when crossing slowly without a stop is permitted, the yellow signal may be flashed. To indicate when crossing immediately after a full stop is permitted, the red signal may be flashed.

Either flash sequence may only be started after the red light is lit and must be followed with a red. All lights are initially off. All sequences must begin a red light. Lighting any light causes all other lights to turn off. No color may be repeated: e.g., red, red is not allowed.

Task:

Write a program that checks a sequence of light codes and determines if that sequence follows or violates the traffic light rules.

Input Read from STDIN a sequence of the follow codes: R (red), Y (yellow), G (Green), P (Pause - flash red), C (Caution - flash yellow), and X (off). Each code must be separated with a space. The entire sequence is submitted by an end-of-line (e.g., pressing the Enter key.) A sequence must have no more than 15 codes in total.

Winning criteria:

Output Write to STDOUT an evaluation of the sequence:

ACCEPT \>\> The entire input sequence meets all rules.

REJECT \>\> The input sequence violates any sequence constraint; for example G Y.

ERROR \>\> The input is malformed – undefined code, too short, too long, etc.

```
EXAMPLES:

1 - Input: R G Y R C R G Y R                  Output: ACCEPT
2 - Input: G Y R G Y R                        Output: REJECT
3 - Input: R Y G P                            Output: REJECT
4 - Input: R G Y                              Output: ERROR
5 - Input: X 8 S                              Output: ERROR
6 - Input: R G Y R C R P R G Y R G Y R G Y R  Output: ERROR

```

You do not have to worry about the reasons listed below, they are only used a reference as to why the input strings have either been Accepted, Rejected or Erroneous.

Reasons:

1. Correct
2. Doesn’t start with R
3. Invalid sequence
4. Undefined code
5. Undefined Codes e.g. X is not part of the grammar
6. The input is malformed – undefined code, too short, too long, etc.

# Answer
> 1 votes
^^ Neat line ardnew, but check yourself for cases

```
1: R G Y R P
2: R G Y C

```

This was one of the questions from the IEEE contest

To determine the next light in the sequence its simply (let c = color of light)

```
(c == 'R') ? ('G', 'P', 'C') : (c == 'G') ? ('Y') : ('R')

```

Those conditions follows from the question statement

* If the light is RED, the next light can only be (GREEN, PAUSE, CAUTION)
* If the light is GREEN, the next light can only be (YELLOW)
* Else (light is (YELLOW, PAUSE, CAUTION)) the next light is RED

The first conditions follow from the fact that its always RED GREEN YELLOW

The flashing lights PAUSE and CAUTION require there be a RED immediately before and after

# Answer
> 2 votes
## Perl, 83 chars

good grief, halfway through golfing this thing i realized its a code-*challenge*

```
$_=<>;chop;print/.{30}|[^RYGPCX ]|\S\S/?ERROR:s/^(R (C|P|G Y) )+R?$//?ACCEPT:REJECT

```

---
Tags: code-challenge, string
---


# Question
Title: Minimum number of transactions so everyone has paid the same
On a road trip, N people pay for fuel. Each pays a different amount. At the end of the trip, calculate the minimum number of transactions so that each person has paid the same amount.

e.g. on the road trip, these people pay for fuel

* Dave - $50
* John - $25
* George - $5
* Barry - $0

After the road trip:

* Barry pays Dave $20
* George pays John $5
* George pays Dave $10

---

Added: The output of the program should list the transactions.

Bonus points if the solution is written in Visual Basic.

# Answer
# Python, 308 Characters

I chose not to go after the bonus because the last time I used VB was over a decade ago, and I am still suffering from the PTSD ;-)

I didn't try and golf this very much because I'm not sure if that's the goal. This code is guaranteed to return a solution with the minimum number of transactions.

```
def t(p):
 a=sum(p)/float(len(p))
 q=[([],p)]
 l=len(p)
 r=range(l)
 while q:
  n=q.pop(0)
  g=1
  for i in r:
   d=n[1][i]-a
   if d>0:
    g=0
    for j in r:
     if n[1][j]<a:
      v=min(d,a-n[1][j])
      y=list(n[1])
      y[i]-=v
      y[j]+=v
      if i!=j:q+=[(n[0]+[(j,i,v)],y)]
  if g:return n[0]

```

## Usage

The `t` function takes a list of the amounts that each person paid. Using the example from the question:

```
> print t([50,25,5,0])
[(2, 0, 15.0), (3, 0, 15.0), (3, 1, 5.0)]

```

So the solution is for person 2 (George) to pay person 0 (Dave) $15 and for person 3 (Barry) to pay 0 (Dave) $15 and also to pay 1 (John) $5.
> 3 votes

---
Tags: popularity-contest, optimization
---


title: Program my microwave oven

text:
# Question
Title: Program my microwave oven
I'm very lazy so I try to always **program my microwave with the fewest possible button presses**. My microwave has the following buttons:

* A "minute plus" button which may only be pressed first and implies "start". It may be pressed multiple times for multiple minutes, but it will *not* add a minute to a manually entered time. **Output `+`**
* A set of 0-9 buttons. Time entry is MMSS (i.e. "130" means 1 minute 30 seconds). Seconds may range from 0..99. So "130" and "90" are equivalent entries. Obviously each minute is 60 seconds even if the seconds part of the entry exceeds 59. **Output `0`..`9`**
* A "start" button which must be pressed to start the microwave if the time is entered manually. **Output `S`**

My food packages **specify time in MM:SS** and so the program must accept that input.

### Examples

* 1:00 is `+` (remember "minute plus" implies start)
* 1:01 is `61S` (seconds can exceed 59, but "minute plus" does not work in conjunction with digits -- I think this is a design flaw in my microwave)
* 9:00 is `900S` (shorter than `+++++++++`)

# Answer
> 3 votes
## APL

APL has a bad reputation that it's unreadable, which is totally not the case if it's not golfed.

The rules:

* Whole minutes \<= 4 get +, ++, +++, and ++++
* 960-999 is preferred above 1000-1039. 9960-9999 is preferred above 10000-10039, etc.
* If the time can be rewritten such that the seconds are 66, 77, 88, or 99 then this is done. (This never gives a worse solution and usually gives a better one, i.e. 888 instead of 928.)

```
∇ Microwave;time;secs;mins;fmt;⎕ML

 ⎕ML←3

 ⎕←'Enter the time (m+:ss)'
 time←⍞
 mins secs←⍎¨(time≠':')⊂time

⍝ 'minute plus' can only be used on whole minutes ≤ 4
 :If (secs=0)∧(mins≤4)
     ⎕←mins⍴'+'
     :Return
 :EndIf
⍝ If possible, save a keypress by using seconds > 60
⍝ if mins is a power of ten
 :If (mins>0)
     :If ((⌈10⍟mins)=(⌊10⍟mins))∧(secs<40)
         ⎕←('BI2'⎕FMT mins-1),(⎕FMT secs+60),'S'
         :Return
     :EndIf
 :EndIf
⍝ For the 'finger movement' requirement we want as many
⍝ of the keypresses as possible to be of the same key.
⍝ So 888S i.p.v. 928S.
 :If secs∊66 77 88 99-60
     ⎕←('BI2'⎕FMT mins-1),(⎕FMT secs+60),'S'
     :Return
 :EndIf
⍝ Otherwise, just output mmssS, there was no better alternative.
 :If mins>0
    ⍝ output seconds with leading zero
     ⎕←('BI2'⎕FMT mins),('G⊂99⊃'⎕FMT secs),'S'
 :Else
    ⍝ only output seconds, not with leading zero
     ⎕←('BI2'⎕FMT secs),'S'
 :EndIf
∇

```

# Answer
> 4 votes
## JavaScript

```
var x = /(\d+):(\d\d)/.exec('<time here>');
x[1] === '0' ? +x[2] + 'S' :
x[1] < 4 && x[2] === '00' ? (
    x[1] === '1' ? '+' :
    x[1] === '2' ? '++' : '+++') :
x[2] < 40 ?
    (x[1] - 1 ? x[1] - 1 : '') + '' + (6 + +x[2][0]) + x[2][1] + 'S' :
x[1] + x[2] + 'S'

```

# Answer
> 3 votes
## Perl

meets the requirements, but it isn't how I would enter the buttons (e.g. "860S" vs "900S") handles exactly 60 seconds as a special case

```
use strict;
use warnings;

sub cook
{
  my ($mins, $secs) = @_;

  my $plus = $secs =~ /00/ ? $mins : undef;

  my $secs_total = $mins * 60 + $secs;
  my $mins_total = 0;

  while ($secs_total > 99)
  {
    ++$mins_total;
    $secs_total -= 60;
  }

  $plus = "+" x $plus if defined $plus;

  my $nums = "";
  my $even = ($mins_total > 0 and $secs_total == 60);

  $secs_total *= not $even;
  $mins_total += $even;

  if ($mins_total > 0)
  {
    $nums = sprintf "%s%02dS", $mins_total, $secs_total;
  }
  else
  {
    $nums = sprintf "%2dS", $secs_total;
  }

  return ($nums, $plus)
    [defined $plus and length $plus < length $nums];
}

die "usage:$/\tperl $0 <MINUTES>:<SECONDS>$/"
  unless @ARGV > 0 and shift =~ /([0-9]{1,2}):([0-9]{1,2})/;

print cook($1, $2), $/;

```

## Output

```
andrew@gidget:~$ perl mic.pl 9:00
900S
andrew@gidget:~$ perl mic.pl 1:00
+
andrew@gidget:~$ perl mic.pl 1:01
61S
andrew@gidget:~$ perl mic.pl 1:30
90S
andrew@gidget:~$ perl mic.pl 0:07
 7S
andrew@gidget:~$ perl mic.pl 4:00
400S

```

# Answer
> 1 votes
## ruby

```
#Build a string for the microwave
def build_result(minutes, seconds)
  duration = minutes * 60 + seconds
  if duration < 99
    result = "%iS" % [ duration]    #shortcut '90S' instead '130S'
  else
    result = "%i%02iS" % [ minutes, seconds]
  end
  result
end

#Call microwave optimizer
def microwave( input )
  minutes  = input.split(/:/).first.to_i
  seconds = input.split(/:/).last.to_i

  #build result
  result = build_result(minutes, seconds)
  #try a shorter result, make 999S out of '10:39':
  if seconds < 40 and minutes > 0
    result2 = build_result(minutes - 1, seconds + 60)   #try a
    result = ( result.size <= result2.size ? result : result2 )
  end

  #Check if a version with only '+' is shorter
  if seconds == 0 and minutes <= result.size
    result = '+' * minutes
  end
  result
end

#Test if called with an argument
if ARGV.empty?
  require 'test/unit'   #Exceute a test
  class MicrowaveTest < Test::Unit::TestCase
    def test_007
      assert_equal('7S', microwave('0:07'))
    end
    def test_100
      assert_equal('+', microwave('1:00'))
    end
    def test_101
      assert_equal('61S', microwave('1:01'))
    end
    def test_130
      assert_equal('90S', microwave('1:30'))
    end
    def test_400
      #~ assert_equal('400S', microwave('4:00'))
      assert_equal('++++', microwave('4:00'))
    end
    def test_500
      assert_equal('500S', microwave('5:00'))
    end
    def test_900
      assert_equal('900S', microwave('9:00'))
    end
    def test_1000
      #~ assert_equal('1000S', microwave('10:00'))
      assert_equal('960S', microwave('10:00'))
    end
    def test_1015
      #~ assert_equal('1015S', microwave('10:15'))
      assert_equal('975S', microwave('10:15'))
    end
    def test_1039
      #~ assert_equal('1039S', microwave('10:39'))
      assert_equal('999S', microwave('10:39'))
    end
  end
else  #started via shell, evaluate input
  puts microwave(ARGV.first)
end

```

Remarks:

* Start it with `ruby program-my-microwave-oven.rb` and a unit test is evaluated.
* Start it with `ruby program-my-microwave-oven.rb 10:00` and it writes `960S`

Some remarks on the rules (and my interpretation):

* The shortest for `10:00` is `960S` (9 minutes and 60 seconds -\> 10 minutes).
* The shortest for `10:39` is `999S` (9 minutes and 99 seconds -\> 10 minutes and 39 seconds).
* for `4:00` it prefers `++++` (less finger movements)

---
Tags: code-challenge, optimization
---


title: Score a game of Yahtzee

text:
# Question
Title: Score a game of Yahtzee
For each of the 13 rows of a Yahtzee scoresheet you are given (from stdin) a space separated list of 5 numbers (dice). Your task is to calculate the score for each line and **output the Grand Total** of the game.

## Example

Input and how to interpret it:

```
Input       Box              Score
6 1 4 1 3   Aces              2
3 2 2 1 2   Twos              6
6 3 2 3 3   Threes            9
4 2 3 6 5   Fours             4
6 3 5 5 1   Fives            10
1 5 6 5 6   Sixes            12
            Bonus             -
4 2 4 4 1   3 of a kind      15
2 2 3 2 4   4 of a kind       -
3 2 2 2 3   Full house       25
1 3 1 6 1   Small straight    -
2 5 4 6 3   Large straight   40
2 2 2 2 2   Yahtzee          50
5 5 4 5 2   Chance           21
            Grand Total     194

```

We will disregard the Yahtzee *Bonus* and Joker rules, and only sum up the scores from the Upper and Lower Section and the Bonus in the Upper Section. If in doubt, refer to these rules.

May the shortest code win!

# Answer
## APL (124)

```
S←{⍺∊+⌿⍵∘.=⍵}⋄+/(+/⎕)(50×∧/,A∘.=A←⎕)(+/10×{⍵×∨/(⍳⍵)⍷1+A-⊃A←A[⍋A←⎕]}¨N)(25×∧/S∘⎕¨2 3)(+/{(+/A)×⍵S⊢A←⎕}¨N←3 4)(+/{+/⍵×⍵=⎕}¨⍳6)

```
> 4 votes

# Answer
## R - 264

```
S=sum;
P=prod;
T=function(i)table(x[i,]);
Z=function(i,...)any(sapply(list(...),function(y)all(y%in%x[i,])))
S((x[1:6,]==(R=row(x[1:6,])))*R)+ # Upper section
S(x[7,])*any(T(7)>2)+             # 3 of a kind
S(x[8,])*any(T(8)>3)+             # 4 of a kind
25*(P(T(9))%in%5:6)+              # Full house
30*Z(10,1:4,2:5,3:6)+             # Small straight
40*Z(11,1:5,2:6)+                 # Large straight
50*(P(T(12))==5)+                 # Yahtzee
S(x[13,])                         # Chance

```

(264 characters when excluding the comments)

With the input

```
x <- as.matrix(read.table("http://pastebin.com/raw.php?i=ZRMC9B4x"))

```

Output

```
[1] 194

```
> 5 votes

# Answer
# Python 364

```
S=sum;R=range;D=[map(int,raw_input().split())for i in R(13)];s=S(x for i in R(6)for x in D[i]if x==i+1)
for i in R(2):d=D[6+i];s+=[0,S(d)][max(map(d.count,d))>2+i];d=sorted(set(D[9+i]));s+=[0,30+i*10]['1, 1, 1'+', 1'*i in`[d[x+1]-d[x]for x in R(len(d)-1)]`]
e=D[8];a=map(e.count,e);d=D[11];print s+S(D[12])+[0,50][d.count(d[0])==5]+[0,25][2in a and 3in a or 5in a]

```

As requested, input is on stdin:

```
$ yScore.py < dice.txt
194

```

If the data could be preloaded into a list, as some other solutions have done, I could remove 62 characters to get to 302.
> 4 votes

# Answer
# Mathematica 359

```
y = IntegerDigits@ImportString[x, "Table"][[1]];
l = Length; g = Gather; r = Range; b = SortBy; h = l@b[g[y[[#]]], l][[-1]] &;
Tr@Flatten@{# Count[y[[#]], #] & /@ r@6, If[h@7 == 3, 15, 0],
If[h@8 == 4, 20, 0], If[(l /@ b[g[y[[9]]], l]) == {2, 3}, 25, 0],
If[MatchQ[Sort@y[[10]], {___, n_, m_, o_, q_, ___} /; m == n + 1 && o == m + 1 && q == o + 1], 30, 0],
If[Sort[y[[11]]] == r[y[[11, 1]], y[[11, 1]] + 4], 40, 0],
If[l@g[y[[12]]] == 1, 50, 0], y[[13]]}

```

There must be a more efficient way to check for the short straight.
> 3 votes

# Answer
### GolfScript 180

```
n/{~]}%6,{)`['{''=},,''*']*}%[{.{+}*\{..|{'{'\'=},,'++1$\~}%$\;}:g~)\;2>*}{.{+}*\g)\;3>*}{g[2 3]=25*}{$:§;3,{).4+,\>§-}%1?)!!30*}{.$(\;.5+,\>\-!40*}{g)\;5=50*}{{+}*}]+]zip{~~}%{+}*

```

You can test the program here

Annotated program:

```
n/                          # split input by newline
{~]}%                       # parse an int array from each line

6,{)`['{''=},,''*']*}%      # create {X=},,X* code blocks,
                            # where X goes from 1 to 6
                            # (needed for processing the first
                            # half of the board)

[       # create an array of code blocks, for scoring:

        # three of a kind:
    {.{+}*\{..|{'{'\'=},,'++1$\~}%$\;}:g~)\;2>*}

        # four of a kind:
    {.{+}*\g)\;3>*}

        # full house:
    {g[2 3]=25*}

        # small straight:
    {$:§;3,{).4+,\>§-!}%1?)!!30*}

        # straight:
    {.$(\;.5+,\>\-!40*}

        # yahtzee:
    {g)\;5=50*}

        #chance:
    {{+}*}
]+              # concatenate the 1-6 code block array with this one

]zip            # distribute each line in the input
                # to the corresponding scoring rule (code block)

{~~}%           # evaluate each input/code pair
                # and get an array with score for each hand

{+}*            # sum up the partial scores.

```
> 1 votes

# Answer
# Perl 527 characters

```
while(<>){$l++;$q=$c=0;$q=1if(($_=~/1/&&$_=~/2/&&$_=~/3/&&$_=~/4/)||($_=~/5/&&$_=~/2/&&$_=~/3/&&$_=~/4/)||($_=~/5/&&$_=~/6/&&$_=~/3/&&$_=~/4/));@a=split//;for(@a){$c++if/$l/;}$s+=$l*($c)if$l<7;$s+=35if$s>=63&&$l==6;for$i(1...6){$t=0;$f+=$c if($l==9&&($c==2||$c==3));$c=0if!($l==11&&$c>1);for(@a){$t+=$_;$c++if/$i/;}$s+=$t if($c>=3&&$l==7);$s+=$t if($c>=4&&$l==8);$s+=50if($c==5&&$l==12);$s+=$t if($l==13&&$i==6);}$s+=25if($f==5&&$l==9);$s+=30if($q==1&&$l==10);$s+=40if($c<2&&($t==15||$t==20)&&$l==11);exit(print $s)if($l==13);}

```
> 1 votes

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


title: Determine the original sequence

text:
# Question
Title: Determine the original sequence
Write a program that will determine the original sequence given five variations. The original sequence will be contain n unique elements in any order. A variation is made by making a copy of the original sequence and choosing a random item from the copy and inserting it at any random location in the sequence (this could be the same index it was originally at). Also, each item can only be chosen once so that the five variations will each operate on a different item.

## Input

```
5          # number of items
1 2 3 4 5  # unknown
2 1 3 4 5  # 3,4,5 candidate
3 1 2 4 5  # 4,5 candidate
4 1 2 3 5  # 1,2 candidate
5 1 2 3 4  # 1,2,3 candidate
           # 1,2,3 + 3,4,5 = 1,2,3,4,5

```

## Output

```
1 2 3 4 5

```

In case it's not clear what I meant, here is Python code to generate an example

```
from random import shuffle,randint

n = 5 # can be any number
a = range(1, n+1)
shuffle(a)
s = set()
#print str(a[0])+"".join(" "+str(x) for x in a[1:]) #debug (print orig sequence)
for run in xrange(5):
    c = list(a)
    i = randint(0, n-1)
    while c[i] in s:
        i = randint(0, n-1)
    t = c.pop(i)
    s.add(t)
    c.insert(randint(0, n-1), t)
    print str(c[0])+"".join(" "+str(x) for x in c[1:])

```

Keep in mind, the numbers aren't necessarily consecutive or all positive. The shortest wins.

## Longer Example

Here's how the five variations are generated. Each is just one step away from the original.

```
6 3 4 5 7 1 2 # original

6 4 5 7 3 1 2 # 3 moved to index 3
3 6 4 5 7 1 2 # 6 moved to index 1
6 3 4 5 1 2 7 # 7 moved to index 6
6 3 4 7 1 5 2 # 5 moved to index 5
6 3 2 4 5 7 1 # 2 moved to index 2

```

Contiguous subsequences of the original will remain in each variation.

```
6 4 5 7 3 1 2
3 6 4 5 7 1 2
          x x # (1, 2) is a candidate

6 4 5 7 3 1 2
6 3 4 5 1 2 7
x             # (6) is a candidate but we can ignore it since one item
              # doesn't tell us much

6 4 5 7 3 1 2
6 3 4 7 1 5 2
x     x     x

6 4 5 7 3 1 2
6 3 2 4 5 7 1
x

3 6 4 5 7 1 2
6 3 4 5 1 2 7
    x x       # (4, 5)

3 6 4 5 7 1 2
6 3 4 7 1 5 2
    x

3 6 4 5 7 1 2
6 3 2 4 5 7 1

6 3 4 5 1 2 7
6 3 4 7 1 5 2
x x x         # (6, 3, 4)

6 3 4 5 1 2 7
6 3 2 4 5 7 1
x x           # (6, 3)

6 3 4 7 1 5 2
6 3 2 4 5 7 1
x x           # (6, 3)

```

Merging the candidates together we realize the sequence has

```
(6, 3, 4, 5) and (1, 2)

```

We can get the rest by realizing that by inserting an item, the sequence may be shifted by one in either direction, so repeat the above except using a unshifted sequence.

```
4 5 7 3 1 2
3 6 4 5 7 1 2

4 5 7 3 1 2
6 3 4 5 1 2 7
        x x   # (1, 2)

4 5 7 3 1 2
6 3 4 7 1 5 2
        x

4 5 7 3 1 2
6 3 2 4 5 7 1

6 4 5 7 1 2
6 3 4 5 1 2 7
x       x x   # (1, 2)

6 4 5 7 1 2
6 3 4 7 1 5 2
x     x x     # (7, 1) something new!

6 4 5 7 1 2
6 3 2 4 5 7 1
x

3 4 5 1 2 7
6 3 4 7 1 5 2

3 4 5 1 2 7
6 3 2 4 5 7 1
          x

3 4 7 1 5 2
6 3 2 4 5 7 1
        x

```

Merging those with our previous results give us

```
(6, 3, 4, 5) and (7, 1, 2)

```

Now do the same again except unshifting the other.

```
6 4 5 7 3 1 2
6 4 5 7 1 2
x x x x       # (6, 4, 5, 7)

6 4 5 7 3 1 2
3 4 5 1 2 7
  x x         # (4, 5)

6 4 5 7 3 1 2
3 4 7 1 5 2
  x

6 4 5 7 3 1 2
3 2 4 5 7 1

3 6 4 5 7 1 2
3 4 5 1 2 7
x

3 6 4 5 7 1 2
3 4 7 1 5 2
x

3 6 4 5 7 1 2
3 2 4 5 7 1
x   x x x x   # (4, 5, 7, 1)

6 3 4 5 1 2 7
3 4 7 1 5 2

6 3 4 5 1 2 7
3 2 4 5 7 1
    x x       # (4, 5)

6 3 4 7 1 5 2
3 2 4 5 7 1
    x

```

Merging those with our previous gives us

```
(6, 3, 4, 5, 7, 1, 2)

```

Each candidate gives the "general" order of the original sequence. For example (6, 4, 5, 7) just says "6 before 4 before 5 before 7" but doesn't say anything about numbers that max exist between say 6 and 4. However, we have (6, 3, 4, 5) which lets us know a 3 exists between 6 and 4 so when we merge the two candidates, we end up with (6, 3, 4, 5, 7).

## Additional example

## Input

```
6 1 7 2 5 3 4
1 7 2 5 6 3 4
1 7 5 6 3 4 2
1 7 2 6 5 3 4
7 2 5 6 1 3 4

```

## Output

```
1 7 2 5 6 3 4

```

Doing it similar to the above, we get candidates

```
(3, 4)
(5, 3, 4)
(1, 7)
(1, 7, 2)
(5, 6)
(1, 7, 2, 5)
(6, 3, 4)
(7, 2, 5, 6)
(7, 2)

```

Some are obviously self-contained, so simplifying we get

```
(5, 3, 4)
(1, 7, 2, 5)
(6, 3, 4)
(7, 2, 5, 6)

```

Then one is an obvious extension of the other, so we get

```
(1, 7, 2, 5, 6)
(5, 3, 4)
(6, 3, 4)

```

The first lets us know 5 goes before 6 and the other two say (3, 4) go after both 5 and 6, so we get

```
(1, 7, 2, 5, 6, 3, 4)

```

If you noticed, each of the items in a candidate can represent a vertex and an edge going from one item to another. Putting them all together will allow you to make a DAG. This is just the way I do it, there may be other and better ways to do it.

# Answer
> 3 votes
### GolfScript, 44 characters

```
n/{~]}%:^0=.,{{{.3$?\2$?>}^%$2={\}*}*]}*" "*

```

The solution can be tested online.

The algorithm is based on the fact, that the order in which two items can be may be reversed mostly twice: once when the first item is moved and once when the second is. Thus, in at least 3 out of the five cases the original order is preserved.

```
n/          # Split the input into lines
{~]}%       # and evaluate each line.
:^          # We now have an array of arrays
            # which we save to variable ^
0=          # Take the first item of this list
.,{{        # We now sort this list of items using bubble-sort
            # The following lines calculate the comparator
    {       #   For each line in the input
      .3$?  #     Determine position of first item
      \2$?  #     Determine position of second item
      >     #     Is first before/after second?
    }^%     #   End for each
    $2=     #   Take the middle element of the list.
            #   (i.e. was first item most of the time
            #   positioned after the second)
    {\}*    #   Swap if it was the case.
}*]}*       # End of bubble-sort loops
" "*        # Format output

```

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


# Question
Title: Compress data with context free grammars
It is possible to compress some kinds of data, such as human text or source code, with straight-line grammars. You basically create a grammar whose language has exactly one word – the uncompressed data. In this task, you have to write a program that implements this method of data compession.

## Input

The input is a string of not more than 65535 bytes length. It is guaranteed, that the input matches the regular expression `[!-~]+` (i.e. at least one printable ASCII character excluding whitespace).

An example input is

> abcabcbcbcabcacacabcabab

## Output

The output is a set of rules that form a grammar that describes exactly one word (the input). Each nonterminal is denoted by a decimal number greater than 9. The start symbol is symbol number ten. An example output corresponding to the example input is given below; its syntax is described further below:

```
10=11 11 12 12 11 13 13 11 14 14
11=a 12
12=b c
13=a c
14=a b

```

Each rule has the form `<nonterminal>=<symbol> <symbol> ...` with an arbitrary whitespace-separated number of symbols on the right side. Each output that obeys the following restrictions and derives exactly the input string is valid.

# Restrictions

In order to stop people from doing strange things, a number of restrictions are taking place:

* Each nonterminal must appear at least twice on the right side of a rule. For instance, the following grammar for the input `abcabc` is illegal because rule 12 appears only once:

```
  10=12
  11=a b c
  12=11 11

```
* No sequence of two adjacent symbols may appear more than once in all right-hand sides of all rules, except if they overlap. For instance, the following grammar for the input `abcabcbc` is illegal since the sequence `bc` appears twice:

```
  10=11 11 b c
  11=a b c

```

A valid grammar would be:

```
  10=11 11 12
  11=a 12
  12=b c

```
* Your program must terminate in less than one minute for each valid input that is not longer than 65535 bytes.
* As usual, you may not use any facility of your language or any library function that makes the solution trivial or implements a large part of it.

## Sample input

Generate sample input with the following C program.

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

int main(int argc, char **argv) {
  unsigned int i,j = 0,k;

  if (argc != 3
     || 2 != sscanf(argv[1],"%u",&i)
      + sscanf(argv[2],"%u",&k)) {
    fprintf(stderr,"Usage: %s seed length\n",argv[0]);
    return EXIT_FAILURE;
  }

  srand(i);

  while(j < k) {
    i = rand() & 0x7f;
    if (i > 34 && i != 127) j++, putchar(i);
  }

  return EXIT_SUCCESS;
}

```

The sample input generated by the program above will usually not result in good compression results. Consider using human text or source code as example input.

## Winning criteria

This is code golf; the program with the shortest source code wins. For extra credit, write a program that reconstructs the input from the output.

# Answer
> 3 votes
### GolfScript, 111 108 characters

```
1/{.}{:^1<{^1$/,2>.{;,)^<.0?)!}*}do-1<.,1>{^1$/[10):10]*0+\+}{;^}if(\}while][0]%.,,]zip{))9+`"="+\~" "*+}%n*

```

This is a quite clumsy approach using GolfScript. The second version performs much better than the initial one. It is much longer than the intended code but my implementation had nested do-loops and this caused issues with the interpreter.

Examples:

```
> abcba
10=a b c b a

> abcabcbc
10=11 11 12
11=a 12
12=b c

> abcabcbcbcabcacacabcabab
10=11 12 12 13 14 14 c 11 15
11=15 13
12=c b
13=14 b
14=c a
15=a b

```

---
Tags: code-golf, compression, restricted-time, grammars
---