# Question
Title: Invent your own Unicode 7.0.0 encoding (as efficient as possible)
As you may know, the Unicode standard has room for 1,114,111 code points, and each assigned code point represents a glyph (character, emoji, etc.).

Most code points are not yet assigned.

Current Unicode implementations take a lot of space to encode all possible code points (UTF-32 takes 4 bytes per code point, UTF-16: 2 to 4 bytes, UTF-8: 1 to 4 bytes, etc.)

## Task

Today, your task is to implement your own Unicode implementation, with the following rules:

* Write an encoder and a decoder in any language of your choice
* The encoder's input is a list of code points (as integers) and it outputs a list of bytes (as integers) corresponding to your encoding.
* The decoder does the opposite (bytes =\> code points)
* Your implementation has to cover all Unicode 7.0.0 assigned code points
* It has to stay backwards-compatible with ASCII, i.e. encode Basic latin characters (U+0000-U+007F) on one byte, with 0 as most significant bit.
* Encode all the other assigned code points in any form and any number of bytes you want, as long as there is no ambiguity (i.e. two code points or group of code points can't have the same encoding and vice versa)
* Your implementation doesn't have to cover UTF-16 surrogates (code points U+D800-U+DFFF) nor private use areas (U+E000-U+F8FF, U+F0000-U+10FFFF)
* Your encoding must be context-independant (i.e. not rely on previously encoded characters) and does NOT require self-synchronization (i.e. each byte doesn't have to infer where it's located in the encoding of a code point, like in UTF-8).

To sum up, here are the blocks that you have to cover, in JSON:

(source: http://www.unicode.org/Public/UNIDATA/Blocks.txt)

```
[
  [0x0000,0x007F], // Basic Latin
  [0x0080,0x00FF], // Latin-1 Supplement
  [0x0100,0x017F], // Latin Extended-A
  [0x0180,0x024F], // Latin Extended-B
  [0x0250,0x02AF], // IPA Extensions
  [0x02B0,0x02FF], // Spacing Modifier Letters
  [0x0300,0x036F], // Combining Diacritical Marks
  [0x0370,0x03FF], // Greek and Coptic
  [0x0400,0x04FF], // Cyrillic
  [0x0500,0x052F], // Cyrillic Supplement
  [0x0530,0x058F], // Armenian
  [0x0590,0x05FF], // Hebrew
  [0x0600,0x06FF], // Arabic
  [0x0700,0x074F], // Syriac
  [0x0750,0x077F], // Arabic Supplement
  [0x0780,0x07BF], // Thaana
  [0x07C0,0x07FF], // NKo
  [0x0800,0x083F], // Samaritan
  [0x0840,0x085F], // Mandaic
  [0x08A0,0x08FF], // Arabic Extended-A
  [0x0900,0x097F], // Devanagari
  [0x0980,0x09FF], // Bengali
  [0x0A00,0x0A7F], // Gurmukhi
  [0x0A80,0x0AFF], // Gujarati
  [0x0B00,0x0B7F], // Oriya
  [0x0B80,0x0BFF], // Tamil
  [0x0C00,0x0C7F], // Telugu
  [0x0C80,0x0CFF], // Kannada
  [0x0D00,0x0D7F], // Malayalam
  [0x0D80,0x0DFF], // Sinhala
  [0x0E00,0x0E7F], // Thai
  [0x0E80,0x0EFF], // Lao
  [0x0F00,0x0FFF], // Tibetan
  [0x1000,0x109F], // Myanmar
  [0x10A0,0x10FF], // Georgian
  [0x1100,0x11FF], // Hangul Jamo
  [0x1200,0x137F], // Ethiopic
  [0x1380,0x139F], // Ethiopic Supplement
  [0x13A0,0x13FF], // Cherokee
  [0x1400,0x167F], // Unified Canadian Aboriginal Syllabics
  [0x1680,0x169F], // Ogham
  [0x16A0,0x16FF], // Runic
  [0x1700,0x171F], // Tagalog
  [0x1720,0x173F], // Hanunoo
  [0x1740,0x175F], // Buhid
  [0x1760,0x177F], // Tagbanwa
  [0x1780,0x17FF], // Khmer
  [0x1800,0x18AF], // Mongolian
  [0x18B0,0x18FF], // Unified Canadian Aboriginal Syllabics Extended
  [0x1900,0x194F], // Limbu
  [0x1950,0x197F], // Tai Le
  [0x1980,0x19DF], // New Tai Lue
  [0x19E0,0x19FF], // Khmer Symbols
  [0x1A00,0x1A1F], // Buginese
  [0x1A20,0x1AAF], // Tai Tham
  [0x1AB0,0x1AFF], // Combining Diacritical Marks Extended
  [0x1B00,0x1B7F], // Balinese
  [0x1B80,0x1BBF], // Sundanese
  [0x1BC0,0x1BFF], // Batak
  [0x1C00,0x1C4F], // Lepcha
  [0x1C50,0x1C7F], // Ol Chiki
  [0x1CC0,0x1CCF], // Sundanese Supplement
  [0x1CD0,0x1CFF], // Vedic Extensions
  [0x1D00,0x1D7F], // Phonetic Extensions
  [0x1D80,0x1DBF], // Phonetic Extensions Supplement
  [0x1DC0,0x1DFF], // Combining Diacritical Marks Supplement
  [0x1E00,0x1EFF], // Latin Extended Additional
  [0x1F00,0x1FFF], // Greek Extended
  [0x2000,0x206F], // General Punctuation
  [0x2070,0x209F], // Superscripts and Subscripts
  [0x20A0,0x20CF], // Currency Symbols
  [0x20D0,0x20FF], // Combining Diacritical Marks for Symbols
  [0x2100,0x214F], // Letterlike Symbols
  [0x2150,0x218F], // Number Forms
  [0x2190,0x21FF], // Arrows
  [0x2200,0x22FF], // Mathematical Operators
  [0x2300,0x23FF], // Miscellaneous Technical
  [0x2400,0x243F], // Control Pictures
  [0x2440,0x245F], // Optical Character Recognition
  [0x2460,0x24FF], // Enclosed Alphanumerics
  [0x2500,0x257F], // Box Drawing
  [0x2580,0x259F], // Block Elements
  [0x25A0,0x25FF], // Geometric Shapes
  [0x2600,0x26FF], // Miscellaneous Symbols
  [0x2700,0x27BF], // Dingbats
  [0x27C0,0x27EF], // Miscellaneous Mathematical Symbols-A
  [0x27F0,0x27FF], // Supplemental Arrows-A
  [0x2800,0x28FF], // Braille Patterns
  [0x2900,0x297F], // Supplemental Arrows-B
  [0x2980,0x29FF], // Miscellaneous Mathematical Symbols-B
  [0x2A00,0x2AFF], // Supplemental Mathematical Operators
  [0x2B00,0x2BFF], // Miscellaneous Symbols and Arrows
  [0x2C00,0x2C5F], // Glagolitic
  [0x2C60,0x2C7F], // Latin Extended-C
  [0x2C80,0x2CFF], // Coptic
  [0x2D00,0x2D2F], // Georgian Supplement
  [0x2D30,0x2D7F], // Tifinagh
  [0x2D80,0x2DDF], // Ethiopic Extended
  [0x2DE0,0x2DFF], // Cyrillic Extended-A
  [0x2E00,0x2E7F], // Supplemental Punctuation
  [0x2E80,0x2EFF], // CJK Radicals Supplement
  [0x2F00,0x2FDF], // Kangxi Radicals
  [0x2FF0,0x2FFF], // Ideographic Description Characters
  [0x3000,0x303F], // CJK Symbols and Punctuation
  [0x3040,0x309F], // Hiragana
  [0x30A0,0x30FF], // Katakana
  [0x3100,0x312F], // Bopomofo
  [0x3130,0x318F], // Hangul Compatibility Jamo
  [0x3190,0x319F], // Kanbun
  [0x31A0,0x31BF], // Bopomofo Extended
  [0x31C0,0x31EF], // CJK Strokes
  [0x31F0,0x31FF], // Katakana Phonetic Extensions
  [0x3200,0x32FF], // Enclosed CJK Letters and Months
  [0x3300,0x33FF], // CJK Compatibility
  [0x3400,0x4DBF], // CJK Unified Ideographs Extension A
  [0x4DC0,0x4DFF], // Yijing Hexagram Symbols
  [0x4E00,0x9FFF], // CJK Unified Ideographs
  [0xA000,0xA48F], // Yi Syllables
  [0xA490,0xA4CF], // Yi Radicals
  [0xA4D0,0xA4FF], // Lisu
  [0xA500,0xA63F], // Vai
  [0xA640,0xA69F], // Cyrillic Extended-B
  [0xA6A0,0xA6FF], // Bamum
  [0xA700,0xA71F], // Modifier Tone Letters
  [0xA720,0xA7FF], // Latin Extended-D
  [0xA800,0xA82F], // Syloti Nagri
  [0xA830,0xA83F], // Common Indic Number Forms
  [0xA840,0xA87F], // Phags-pa
  [0xA880,0xA8DF], // Saurashtra
  [0xA8E0,0xA8FF], // Devanagari Extended
  [0xA900,0xA92F], // Kayah Li
  [0xA930,0xA95F], // Rejang
  [0xA960,0xA97F], // Hangul Jamo Extended-A
  [0xA980,0xA9DF], // Javanese
  [0xA9E0,0xA9FF], // Myanmar Extended-B
  [0xAA00,0xAA5F], // Cham
  [0xAA60,0xAA7F], // Myanmar Extended-A
  [0xAA80,0xAADF], // Tai Viet
  [0xAAE0,0xAAFF], // Meetei Mayek Extensions
  [0xAB00,0xAB2F], // Ethiopic Extended-A
  [0xAB30,0xAB6F], // Latin Extended-E
  [0xABC0,0xABFF], // Meetei Mayek
  [0xAC00,0xD7AF], // Hangul Syllables
  [0xD7B0,0xD7FF], // Hangul Jamo Extended-B
  [0xF900,0xFAFF], // CJK Compatibility Ideographs
  [0xFB00,0xFB4F], // Alphabetic Presentation Forms
  [0xFB50,0xFDFF], // Arabic Presentation Forms-A
  [0xFE00,0xFE0F], // Variation Selectors
  [0xFE10,0xFE1F], // Vertical Forms
  [0xFE20,0xFE2F], // Combining Half Marks
  [0xFE30,0xFE4F], // CJK Compatibility Forms
  [0xFE50,0xFE6F], // Small Form Variants
  [0xFE70,0xFEFF], // Arabic Presentation Forms-B
  [0xFF00,0xFFEF], // Halfwidth and Fullwidth Forms
  [0xFFF0,0xFFFF], // Specials
  [0x10000,0x1007F], // Linear B Syllabary
  [0x10080,0x100FF], // Linear B Ideograms
  [0x10100,0x1013F], // Aegean Numbers
  [0x10140,0x1018F], // Ancient Greek Numbers
  [0x10190,0x101CF], // Ancient Symbols
  [0x101D0,0x101FF], // Phaistos Disc
  [0x10280,0x1029F], // Lycian
  [0x102A0,0x102DF], // Carian
  [0x102E0,0x102FF], // Coptic Epact Numbers
  [0x10300,0x1032F], // Old Italic
  [0x10330,0x1034F], // Gothic
  [0x10350,0x1037F], // Old Permic
  [0x10380,0x1039F], // Ugaritic
  [0x103A0,0x103DF], // Old Persian
  [0x10400,0x1044F], // Deseret
  [0x10450,0x1047F], // Shavian
  [0x10480,0x104AF], // Osmanya
  [0x10500,0x1052F], // Elbasan
  [0x10530,0x1056F], // Caucasian Albanian
  [0x10600,0x1077F], // Linear A
  [0x10800,0x1083F], // Cypriot Syllabary
  [0x10840,0x1085F], // Imperial Aramaic
  [0x10860,0x1087F], // Palmyrene
  [0x10880,0x108AF], // Nabataean
  [0x10900,0x1091F], // Phoenician
  [0x10920,0x1093F], // Lydian
  [0x10980,0x1099F], // Meroitic Hieroglyphs
  [0x109A0,0x109FF], // Meroitic Cursive
  [0x10A00,0x10A5F], // Kharoshthi
  [0x10A60,0x10A7F], // Old South Arabian
  [0x10A80,0x10A9F], // Old North Arabian
  [0x10AC0,0x10AFF], // Manichaean
  [0x10B00,0x10B3F], // Avestan
  [0x10B40,0x10B5F], // Inscriptional Parthian
  [0x10B60,0x10B7F], // Inscriptional Pahlavi
  [0x10B80,0x10BAF], // Psalter Pahlavi
  [0x10C00,0x10C4F], // Old Turkic
  [0x10E60,0x10E7F], // Rumi Numeral Symbols
  [0x11000,0x1107F], // Brahmi
  [0x11080,0x110CF], // Kaithi
  [0x110D0,0x110FF], // Sora Sompeng
  [0x11100,0x1114F], // Chakma
  [0x11150,0x1117F], // Mahajani
  [0x11180,0x111DF], // Sharada
  [0x111E0,0x111FF], // Sinhala Archaic Numbers
  [0x11200,0x1124F], // Khojki
  [0x112B0,0x112FF], // Khudawadi
  [0x11300,0x1137F], // Grantha
  [0x11480,0x114DF], // Tirhuta
  [0x11580,0x115FF], // Siddham
  [0x11600,0x1165F], // Modi
  [0x11680,0x116CF], // Takri
  [0x118A0,0x118FF], // Warang Citi
  [0x11AC0,0x11AFF], // Pau Cin Hau
  [0x12000,0x123FF], // Cuneiform
  [0x12400,0x1247F], // Cuneiform Numbers and Punctuation
  [0x13000,0x1342F], // Egyptian Hieroglyphs
  [0x16800,0x16A3F], // Bamum Supplement
  [0x16A40,0x16A6F], // Mro
  [0x16AD0,0x16AFF], // Bassa Vah
  [0x16B00,0x16B8F], // Pahawh Hmong
  [0x16F00,0x16F9F], // Miao
  [0x1B000,0x1B0FF], // Kana Supplement
  [0x1BC00,0x1BC9F], // Duployan
  [0x1BCA0,0x1BCAF], // Shorthand Format Controls
  [0x1D000,0x1D0FF], // Byzantine Musical Symbols
  [0x1D100,0x1D1FF], // Musical Symbols
  [0x1D200,0x1D24F], // Ancient Greek Musical Notation
  [0x1D300,0x1D35F], // Tai Xuan Jing Symbols
  [0x1D360,0x1D37F], // Counting Rod Numerals
  [0x1D400,0x1D7FF], // Mathematical Alphanumeric Symbols
  [0x1E800,0x1E8DF], // Mende Kikakui
  [0x1EE00,0x1EEFF], // Arabic Mathematical Alphabetic Symbols
  [0x1F000,0x1F02F], // Mahjong Tiles
  [0x1F030,0x1F09F], // Domino Tiles
  [0x1F0A0,0x1F0FF], // Playing Cards
  [0x1F100,0x1F1FF], // Enclosed Alphanumeric Supplement
  [0x1F200,0x1F2FF], // Enclosed Ideographic Supplement
  [0x1F300,0x1F5FF], // Miscellaneous Symbols and Pictographs
  [0x1F600,0x1F64F], // Emoticons
  [0x1F650,0x1F67F], // Ornamental Dingbats
  [0x1F680,0x1F6FF], // Transport and Map Symbols
  [0x1F700,0x1F77F], // Alchemical Symbols
  [0x1F780,0x1F7FF], // Geometric Shapes Extended
  [0x1F800,0x1F8FF], // Supplemental Arrows-C
  [0x20000,0x2A6DF], // CJK Unified Ideographs Extension B
  [0x2A700,0x2B73F], // CJK Unified Ideographs Extension C
  [0x2B740,0x2B81F], // CJK Unified Ideographs Extension D
  [0x2F800,0x2FA1F], // CJK Compatibility Ideographs Supplement
  [0xE0000,0xE007F], // Tags
  [0xE0100,0xE01EF]  // Variation Selectors Supplement
]

```

Total: 116,816 code points.

## Scoring

Your score is not the size of your encoder/decoder, but the number of bytes that your encoder outputs when you feed it with all the 116,816 possible code points (in one time or separately).

## Winner

The most efficient encoding will win and will be the subject of a future code-golf challenge ;)

Good luck!

# Answer
> 10 votes
# Score: 318080 (~2.72 bytes/char)

1. I assume the encoding does not require self-synchronization (like UTF-8 / UTF-16).
2. Because there is no example text, I assume the encoding is *context-independent* (unlike e.g. SCSU), i.e. the encoder converts every code point to a unique bytes sequence.
3. log₂ 116816 = 16.83 \> 16, so any encoding chosen must contain some code point that map to 3 bytes.

For simplicity, let's assume we need to encode exactly 217 = 131072 code points. We could first map every code point to an integer from 0 to 131071. Then remaining is the optimization problem (a *mathematical* problem) on choosing a code which minimize L(E) = ∑0≤i\<131072 |E(i)|.

One possible encoding is *prefix code*. The specification already 0-prefixed sequence is for 0 ... 127 only. A simple, inefficient encoding is to use 1-prefixed sequence for the remaining code:

```
0xxxxxxx                   = x        (this encodes values < 128)
1xxxxxxx xxxxxxxx xxxxxxxx = x + 128  (this encodes values < 131072)

```

The value is (1 byte × 128 + 3 bytes × (131072 − 128)) = 392960 bytes.

We could also use 2-bit prefix, e.g.

```
0xxxxxxx                   = x       (< 128)
10xxxxxx                   = x + 128 (< 192)
11xxxxxx xxxxxxxx xxxxxxxx = x + 192 (< 131072)
    L(E) = 192×1 + 130880×3 = 392832

```

or

```
0xxxxxxx                   = x         (< 128)
10xxxxxx xxxxxxxx          = x + 128   (< 16512)
11xxxxxx xxxxxxxx xxxxxxxx = x + 16512 (< 131072)
    L(E) = 376576

```

etc. I think the most efficient coding is like this:

```
0xxxxxxx                   = x
10xxxxxx xxxxxxxx          = x + 128
110xxxxx xxxxxxxx          = x + 16512 \
1110xxxx xxxxxxxx          = x + 24704  | squeeze all possible values
11110xxx xxxxxxxx          = x + 28800  | encodable by 2 bytes
111110xx xxxxxxxx          = x + 30848  | until 17 bits remains.
1111110x xxxxxxxx          = x + 31872 /
1111111x xxxxxxxx xxxxxxxx = x + 32384 (up to 163456)
    L(E) = 360704

```

---

Since the encoding supports all numbers up to 163456, I have chosen to close some "narrow" gaps under 14000 code points to simply the code point → number conversion, so it will support the ranges:

```
 U+0000 .. U+17000
U+1b000 .. U+2b900
U+2f800 .. U+2fb00
U+e0000 .. U+e0200

```

Since the range of numbers are extended, **the score will be a few bytes above optimal**, but I would compromise that for simplicity of the encoder here.

So the encoder and decoders may be written as (Python 3):

```
def codepoint_to_number(codepoint):
    if 0 <= codepoint < 0x17000:
        return codepoint
    elif 0x1b000 <= codepoint < 0x2b900:
        return codepoint - 0x4000
    elif 0x2f800 <= codepoint < 0x2fb00:
        return codepoint - 0x7f00
    elif 0xe0000 <= codepoint < 0xe0200:
        return codepoint - 0xb8400
    else:
        raise UnicodeError('Cannot encode ' + hex(codepoint))

def number_to_bytes(number):
    if number < 0x80:
        return bytes([number])
    elif number < 0x7e80:
        number += 0x7f80
        return bytes([number >> 8, number & 0xff])
    else:
        number += 0xfd8180
        return bytes([number >> 16, (number >> 8) & 0xff, number & 0xff])

def bytes_to_number(bs):
    first_byte = bs[0]
    if first_byte < 0x80:
        return (first_byte, bs[1:])
    elif first_byte < 0xfe:
        return (0x80 + ((first_byte & 0x7f) << 8 | bs[1]), bs[2:])
    else:
        return (0x7e80 + ((first_byte & 1) << 16 | bs[1] << 8 | bs[2]), bs[3:])

def number_to_codepoint(number):
    if number < 0x17000:
        return number
    elif number < 0x27900:
        return number + 0x4000
    elif number < 0x27c00:
        return number + 0x7f00
    else:
        return number + 0xb8400

def encode(codepoints):
    result = bytearray()
    for codepoint in codepoints:
        result.extend(number_to_bytes(codepoint_to_number(codepoint)))
    return result

def decode(bytes_sequence):
    bs = memoryview(bytes_sequence)
    while bs:
        (number, bs) = bytes_to_number(bs)
        yield number_to_codepoint(number)

```

\# Test case:

```
import itertools
import unittest

# {{{
CODEPOINT_RANGES = [
    [0x0000,0x007F], # Basic Latin
    [0x0080,0x00FF], # Latin-1 Supplement
    [0x0100,0x017F], # Latin Extended-A
    [0x0180,0x024F], # Latin Extended-B
    [0x0250,0x02AF], # IPA Extensions
    [0x02B0,0x02FF], # Spacing Modifier Letters
    [0x0300,0x036F], # Combining Diacritical Marks
    [0x0370,0x03FF], # Greek and Coptic
    [0x0400,0x04FF], # Cyrillic
    [0x0500,0x052F], # Cyrillic Supplement
    [0x0530,0x058F], # Armenian
    [0x0590,0x05FF], # Hebrew
    [0x0600,0x06FF], # Arabic
    [0x0700,0x074F], # Syriac
    [0x0750,0x077F], # Arabic Supplement
    [0x0780,0x07BF], # Thaana
    [0x07C0,0x07FF], # NKo
    [0x0800,0x083F], # Samaritan
    [0x0840,0x085F], # Mandaic
    [0x08A0,0x08FF], # Arabic Extended-A
    [0x0900,0x097F], # Devanagari
    [0x0980,0x09FF], # Bengali
    [0x0A00,0x0A7F], # Gurmukhi
    [0x0A80,0x0AFF], # Gujarati
    [0x0B00,0x0B7F], # Oriya
    [0x0B80,0x0BFF], # Tamil
    [0x0C00,0x0C7F], # Telugu
    [0x0C80,0x0CFF], # Kannada
    [0x0D00,0x0D7F], # Malayalam
    [0x0D80,0x0DFF], # Sinhala
    [0x0E00,0x0E7F], # Thai
    [0x0E80,0x0EFF], # Lao
    [0x0F00,0x0FFF], # Tibetan
    [0x1000,0x109F], # Myanmar
    [0x10A0,0x10FF], # Georgian
    [0x1100,0x11FF], # Hangul Jamo
    [0x1200,0x137F], # Ethiopic
    [0x1380,0x139F], # Ethiopic Supplement
    [0x13A0,0x13FF], # Cherokee
    [0x1400,0x167F], # Unified Canadian Aboriginal Syllabics
    [0x1680,0x169F], # Ogham
    [0x16A0,0x16FF], # Runic
    [0x1700,0x171F], # Tagalog
    [0x1720,0x173F], # Hanunoo
    [0x1740,0x175F], # Buhid
    [0x1760,0x177F], # Tagbanwa
    [0x1780,0x17FF], # Khmer
    [0x1800,0x18AF], # Mongolian
    [0x18B0,0x18FF], # Unified Canadian Aboriginal Syllabics Extended
    [0x1900,0x194F], # Limbu
    [0x1950,0x197F], # Tai Le
    [0x1980,0x19DF], # New Tai Lue
    [0x19E0,0x19FF], # Khmer Symbols
    [0x1A00,0x1A1F], # Buginese
    [0x1A20,0x1AAF], # Tai Tham
    [0x1AB0,0x1AFF], # Combining Diacritical Marks Extended
    [0x1B00,0x1B7F], # Balinese
    [0x1B80,0x1BBF], # Sundanese
    [0x1BC0,0x1BFF], # Batak
    [0x1C00,0x1C4F], # Lepcha
    [0x1C50,0x1C7F], # Ol Chiki
    [0x1CC0,0x1CCF], # Sundanese Supplement
    [0x1CD0,0x1CFF], # Vedic Extensions
    [0x1D00,0x1D7F], # Phonetic Extensions
    [0x1D80,0x1DBF], # Phonetic Extensions Supplement
    [0x1DC0,0x1DFF], # Combining Diacritical Marks Supplement
    [0x1E00,0x1EFF], # Latin Extended Additional
    [0x1F00,0x1FFF], # Greek Extended
    [0x2000,0x206F], # General Punctuation
    [0x2070,0x209F], # Superscripts and Subscripts
    [0x20A0,0x20CF], # Currency Symbols
    [0x20D0,0x20FF], # Combining Diacritical Marks for Symbols
    [0x2100,0x214F], # Letterlike Symbols
    [0x2150,0x218F], # Number Forms
    [0x2190,0x21FF], # Arrows
    [0x2200,0x22FF], # Mathematical Operators
    [0x2300,0x23FF], # Miscellaneous Technical
    [0x2400,0x243F], # Control Pictures
    [0x2440,0x245F], # Optical Character Recognition
    [0x2460,0x24FF], # Enclosed Alphanumerics
    [0x2500,0x257F], # Box Drawing
    [0x2580,0x259F], # Block Elements
    [0x25A0,0x25FF], # Geometric Shapes
    [0x2600,0x26FF], # Miscellaneous Symbols
    [0x2700,0x27BF], # Dingbats
    [0x27C0,0x27EF], # Miscellaneous Mathematical Symbols-A
    [0x27F0,0x27FF], # Supplemental Arrows-A
    [0x2800,0x28FF], # Braille Patterns
    [0x2900,0x297F], # Supplemental Arrows-B
    [0x2980,0x29FF], # Miscellaneous Mathematical Symbols-B
    [0x2A00,0x2AFF], # Supplemental Mathematical Operators
    [0x2B00,0x2BFF], # Miscellaneous Symbols and Arrows
    [0x2C00,0x2C5F], # Glagolitic
    [0x2C60,0x2C7F], # Latin Extended-C
    [0x2C80,0x2CFF], # Coptic
    [0x2D00,0x2D2F], # Georgian Supplement
    [0x2D30,0x2D7F], # Tifinagh
    [0x2D80,0x2DDF], # Ethiopic Extended
    [0x2DE0,0x2DFF], # Cyrillic Extended-A
    [0x2E00,0x2E7F], # Supplemental Punctuation
    [0x2E80,0x2EFF], # CJK Radicals Supplement
    [0x2F00,0x2FDF], # Kangxi Radicals
    [0x2FF0,0x2FFF], # Ideographic Description Characters
    [0x3000,0x303F], # CJK Symbols and Punctuation
    [0x3040,0x309F], # Hiragana
    [0x30A0,0x30FF], # Katakana
    [0x3100,0x312F], # Bopomofo
    [0x3130,0x318F], # Hangul Compatibility Jamo
    [0x3190,0x319F], # Kanbun
    [0x31A0,0x31BF], # Bopomofo Extended
    [0x31C0,0x31EF], # CJK Strokes
    [0x31F0,0x31FF], # Katakana Phonetic Extensions
    [0x3200,0x32FF], # Enclosed CJK Letters and Months
    [0x3300,0x33FF], # CJK Compatibility
    [0x3400,0x4DBF], # CJK Unified Ideographs Extension A
    [0x4DC0,0x4DFF], # Yijing Hexagram Symbols
    [0x4E00,0x9FFF], # CJK Unified Ideographs
    [0xA000,0xA48F], # Yi Syllables
    [0xA490,0xA4CF], # Yi Radicals
    [0xA4D0,0xA4FF], # Lisu
    [0xA500,0xA63F], # Vai
    [0xA640,0xA69F], # Cyrillic Extended-B
    [0xA6A0,0xA6FF], # Bamum
    [0xA700,0xA71F], # Modifier Tone Letters
    [0xA720,0xA7FF], # Latin Extended-D
    [0xA800,0xA82F], # Syloti Nagri
    [0xA830,0xA83F], # Common Indic Number Forms
    [0xA840,0xA87F], # Phags-pa
    [0xA880,0xA8DF], # Saurashtra
    [0xA8E0,0xA8FF], # Devanagari Extended
    [0xA900,0xA92F], # Kayah Li
    [0xA930,0xA95F], # Rejang
    [0xA960,0xA97F], # Hangul Jamo Extended-A
    [0xA980,0xA9DF], # Javanese
    [0xA9E0,0xA9FF], # Myanmar Extended-B
    [0xAA00,0xAA5F], # Cham
    [0xAA60,0xAA7F], # Myanmar Extended-A
    [0xAA80,0xAADF], # Tai Viet
    [0xAAE0,0xAAFF], # Meetei Mayek Extensions
    [0xAB00,0xAB2F], # Ethiopic Extended-A
    [0xAB30,0xAB6F], # Latin Extended-E
    [0xABC0,0xABFF], # Meetei Mayek
    [0xAC00,0xD7AF], # Hangul Syllables
    [0xD7B0,0xD7FF], # Hangul Jamo Extended-B
    [0xF900,0xFAFF], # CJK Compatibility Ideographs
    [0xFB00,0xFB4F], # Alphabetic Presentation Forms
    [0xFB50,0xFDFF], # Arabic Presentation Forms-A
    [0xFE00,0xFE0F], # Variation Selectors
    [0xFE10,0xFE1F], # Vertical Forms
    [0xFE20,0xFE2F], # Combining Half Marks
    [0xFE30,0xFE4F], # CJK Compatibility Forms
    [0xFE50,0xFE6F], # Small Form Variants
    [0xFE70,0xFEFF], # Arabic Presentation Forms-B
    [0xFF00,0xFFEF], # Halfwidth and Fullwidth Forms
    [0xFFF0,0xFFFF], # Specials
    [0x10000,0x1007F], # Linear B Syllabary
    [0x10080,0x100FF], # Linear B Ideograms
    [0x10100,0x1013F], # Aegean Numbers
    [0x10140,0x1018F], # Ancient Greek Numbers
    [0x10190,0x101CF], # Ancient Symbols
    [0x101D0,0x101FF], # Phaistos Disc
    [0x10280,0x1029F], # Lycian
    [0x102A0,0x102DF], # Carian
    [0x102E0,0x102FF], # Coptic Epact Numbers
    [0x10300,0x1032F], # Old Italic
    [0x10330,0x1034F], # Gothic
    [0x10350,0x1037F], # Old Permic
    [0x10380,0x1039F], # Ugaritic
    [0x103A0,0x103DF], # Old Persian
    [0x10400,0x1044F], # Deseret
    [0x10450,0x1047F], # Shavian
    [0x10480,0x104AF], # Osmanya
    [0x10500,0x1052F], # Elbasan
    [0x10530,0x1056F], # Caucasian Albanian
    [0x10600,0x1077F], # Linear A
    [0x10800,0x1083F], # Cypriot Syllabary
    [0x10840,0x1085F], # Imperial Aramaic
    [0x10860,0x1087F], # Palmyrene
    [0x10880,0x108AF], # Nabataean
    [0x10900,0x1091F], # Phoenician
    [0x10920,0x1093F], # Lydian
    [0x10980,0x1099F], # Meroitic Hieroglyphs
    [0x109A0,0x109FF], # Meroitic Cursive
    [0x10A00,0x10A5F], # Kharoshthi
    [0x10A60,0x10A7F], # Old South Arabian
    [0x10A80,0x10A9F], # Old North Arabian
    [0x10AC0,0x10AFF], # Manichaean
    [0x10B00,0x10B3F], # Avestan
    [0x10B40,0x10B5F], # Inscriptional Parthian
    [0x10B60,0x10B7F], # Inscriptional Pahlavi
    [0x10B80,0x10BAF], # Psalter Pahlavi
    [0x10C00,0x10C4F], # Old Turkic
    [0x10E60,0x10E7F], # Rumi Numeral Symbols
    [0x11000,0x1107F], # Brahmi
    [0x11080,0x110CF], # Kaithi
    [0x110D0,0x110FF], # Sora Sompeng
    [0x11100,0x1114F], # Chakma
    [0x11150,0x1117F], # Mahajani
    [0x11180,0x111DF], # Sharada
    [0x111E0,0x111FF], # Sinhala Archaic Numbers
    [0x11200,0x1124F], # Khojki
    [0x112B0,0x112FF], # Khudawadi
    [0x11300,0x1137F], # Grantha
    [0x11480,0x114DF], # Tirhuta
    [0x11580,0x115FF], # Siddham
    [0x11600,0x1165F], # Modi
    [0x11680,0x116CF], # Takri
    [0x118A0,0x118FF], # Warang Citi
    [0x11AC0,0x11AFF], # Pau Cin Hau
    [0x12000,0x123FF], # Cuneiform
    [0x12400,0x1247F], # Cuneiform Numbers and Punctuation
    [0x13000,0x1342F], # Egyptian Hieroglyphs
    [0x16800,0x16A3F], # Bamum Supplement
    [0x16A40,0x16A6F], # Mro
    [0x16AD0,0x16AFF], # Bassa Vah
    [0x16B00,0x16B8F], # Pahawh Hmong
    [0x16F00,0x16F9F], # Miao
    [0x1B000,0x1B0FF], # Kana Supplement
    [0x1BC00,0x1BC9F], # Duployan
    [0x1BCA0,0x1BCAF], # Shorthand Format Controls
    [0x1D000,0x1D0FF], # Byzantine Musical Symbols
    [0x1D100,0x1D1FF], # Musical Symbols
    [0x1D200,0x1D24F], # Ancient Greek Musical Notation
    [0x1D300,0x1D35F], # Tai Xuan Jing Symbols
    [0x1D360,0x1D37F], # Counting Rod Numerals
    [0x1D400,0x1D7FF], # Mathematical Alphanumeric Symbols
    [0x1E800,0x1E8DF], # Mende Kikakui
    [0x1EE00,0x1EEFF], # Arabic Mathematical Alphabetic Symbols
    [0x1F000,0x1F02F], # Mahjong Tiles
    [0x1F030,0x1F09F], # Domino Tiles
    [0x1F0A0,0x1F0FF], # Playing Cards
    [0x1F100,0x1F1FF], # Enclosed Alphanumeric Supplement
    [0x1F200,0x1F2FF], # Enclosed Ideographic Supplement
    [0x1F300,0x1F5FF], # Miscellaneous Symbols and Pictographs
    [0x1F600,0x1F64F], # Emoticons
    [0x1F650,0x1F67F], # Ornamental Dingbats
    [0x1F680,0x1F6FF], # Transport and Map Symbols
    [0x1F700,0x1F77F], # Alchemical Symbols
    [0x1F780,0x1F7FF], # Geometric Shapes Extended
    [0x1F800,0x1F8FF], # Supplemental Arrows-C
    [0x20000,0x2A6DF], # CJK Unified Ideographs Extension B
    [0x2A700,0x2B73F], # CJK Unified Ideographs Extension C
    [0x2B740,0x2B81F], # CJK Unified Ideographs Extension D
    [0x2F800,0x2FA1F], # CJK Compatibility Ideographs Supplement
    [0xE0000,0xE007F], # Tags
    [0xE0100,0xE01EF]  # Variation Selectors Supplement
]
#}}}

ALL_CODEPOINTS = list(itertools.chain.from_iterable(range(x, y+1) for x, y in CODEPOINT_RANGES))

ENCODE_RESULT = encode(ALL_CODEPOINTS)

print(len(ENCODE_RESULT), '/', len(ALL_CODEPOINTS))

DECODE_RESULT = list(decode(ENCODE_RESULT))

tc = unittest.TestCase()
tc.assertListEqual(ALL_CODEPOINTS, DECODE_RESULT)

```

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


title: Four color theorem

text:
# Question
Title: Four color theorem
The Four color theorem States that no more than four colors are required to color the regions of a map.

## The challenge

Given a list of State borders assign each state ID a color so that no two adjacent states have the same color. The output Should be a CSS stylesheet assigning the color to the state's 2 letter ID code. Here is a SVG map which the stylesheet could be applied to. http://upload.wikimedia.org/wikipedia/commons/3/32/Blank\_US\_Map.svg

The rules

* Shortest code wins
* any state border list can be used
* only 4 colors can be used.
* the state list can be hardcoded

Advice: Use the CSS `fill:` property to change the color, For example `#AL{fill:green}`

Here is a list of state borders

```
AL-FL
AL-GA
AL-MS
AL-TN
AR-LA
AR-MO
AR-MS
AR-OK
AR-TN
AR-TX
AZ-CA
AZ-CO
AZ-NM
AZ-NV
AZ-UT
CA-NV
CA-OR
CO-KS
CO-NE
CO-NM
CO-OK
CO-UT
CO-WY
CT-MA
CT-NY
CT-RI
DC-MD
DC-VA
DE-MD
DE-NJ
DE-PA
FL-GA
GA-NC
GA-SC
GA-TN
IA-MN
IA-MO
IA-NE
IA-SD
IA-WI
ID-MT
ID-NV
ID-OR
ID-UT
ID-WA
ID-WY
IL-IA
IL-IN
IL-KY
IL-MO
IL-WI
IN-KY
IN-MI
IN-OH
KS-MO
KS-NE
KS-OK
KY-MO
KY-OH
KY-TN
KY-VA
KY-WV
LA-MS
LA-TX
MA-NH
MA-NY
MA-RI
MA-VT
MD-PA
MD-VA
MD-WV
ME-NH
MI-OH
MI-WI
MN-ND
MN-SD
MN-WI
MO-NE
MO-OK
MO-TN
MS-TN
MT-ND
MT-SD
MT-WY
NC-SC
NC-TN
NC-VA
ND-SD
NE-SD
NE-WY
NH-VT
NJ-NY
NJ-PA
NM-OK
NM-TX
NM-UT
NV-OR
NV-UT
NY-PA
NY-VT
OH-PA
OH-WV
OK-TX
OR-WA
PA-WV
SD-WY
TN-VA
UT-WY
VA-WV

```

# Answer
## Python, 320 chars

```
import sys,random
S=[]
E={}
for x in sys.stdin:a=x[:2];b=x[3:5];S+=[a,b];E[a,b]=E[b,a]=1
C={0:0}
while any(1>C[s]for s in C):
 C={s:0for s in S};random.shuffle(S)
 for s in S:
    A=set([1,2,3,4])-set(C[y]for x,y in E if x==s)
    if A:C[s]=random.choice(list(A))
for s in C:print'#%s{fill:%s}'%(s,' bglrloieulmdede'[C[s]::4])

```

Uses a randomized algorithm. Assign colors to states in random order by selecting a color that doesn't conflict with adjacent states that have already been colored. Seems to work in a tenth of a second or so on the given input.

Example output:

```
$ 4color.py < stategraph
#WA{fill:red}
#DE{fill:gold}
#DC{fill:blue}
#WI{fill:blue}
#WV{fill:red}
#FL{fill:lime}
#WY{fill:gold}
#NH{fill:red}
#NJ{fill:lime}
#NM{fill:gold}
#TX{fill:red}
#LA{fill:blue}
#NC{fill:blue}
#ND{fill:gold}
#NE{fill:blue}
#TN{fill:red}
#NY{fill:gold}
#PA{fill:blue}
#RI{fill:gold}
#NV{fill:red}
#VA{fill:gold}
#CO{fill:red}
#CA{fill:gold}
#AL{fill:blue}
#AR{fill:gold}
#VT{fill:lime}
#IL{fill:red}
#GA{fill:gold}
#IN{fill:lime}
#IA{fill:gold}
#OK{fill:blue}
#AZ{fill:lime}
#ID{fill:lime}
#CT{fill:red}
#ME{fill:blue}
#MD{fill:lime}
#MA{fill:blue}
#OH{fill:gold}
#UT{fill:blue}
#MO{fill:lime}
#MN{fill:red}
#MI{fill:red}
#KS{fill:gold}
#MT{fill:blue}
#MS{fill:lime}
#SC{fill:red}
#KY{fill:blue}
#OR{fill:blue}
#SD{fill:lime}

```

Example pasted into svg.
> 4 votes

# Answer
# Prolog, ~~309~~ ~~307~~ 283 chars

```
:-initialization m.
a-X:-assert(X);retract(X),1=0.
r:-maplist(get_char,[A,B,E,C,D,F]),(E=F;X=[A,B],Y=[C,D],a-X/Y,a-Y/X,(s/X;a-s/X),(s/Y;a-s/Y),r).
s+[]:- \+ (X*C,writef('#%s{fill:#%w}',[X,C]),1=0).
s+[X|T]:-member(C,[911,191,119,991]),a-X*C,\+ (X/Y,Y*C),s+T.
m:-r,bagof(X,s/X,L),s+L.

```

The algorithm uses backtracking / depth-first search to fill out the map.

A bit more readable:

```
:- initialization(main).

% Found on http://awarth.blogspot.de/2008/08/asserts-and-retracts-with-automatic.html
assert2(X) :- assert(X).
assert2(X) :- retract(X), fail.

% Reads all states into clauses "state-State",
% and all connections into "State-Neighbor" and "Neighbor-State".
read_states :-
    % Read a line "AB-CD\n"
    maplist(get_char, [A,B,E,C,D,F]),
    (   A = F;
        State = [A, B],
        Neighbor = [C, D],
        % Memorize the connection between State and Neighbor in both directions.
        assert(State/Neighbor),
        assert(Neighbor/State),
        % Memorize State and Neighbor for the list of states.
        (state/State; assert(state/State)),
        (state/Neighbor; assert(state/Neighbor)),
        % Continue for all lines.
        read_states
    ).

% Print out all colors.
solve([]) :-
    once((
        State*Color,
        writef('#%s{fill:%w}', [State, Color]),
        fail
    )); !.

% Use depth-first search to color the map.
solve([State|FurtherStates]) :-
    member(Color, ['#911', '#191', '#119', '#991']),
    assert2(State*Color),
    \+ (State/Neighbor, Neighbor*Color),
    solve(FurtherStates).

main :-
    read_states,
    bagof(State, state/State, States),
    solve(States).

```

Invocation:

```
cat borders.txt | swipl -q ./fourcolors.pl

```

Result (newlines are not needed):

```
#AL{fill:#911}#FL{fill:#191}#GA{fill:#119}#MS{fill:#191}#TN{fill:#991}#AR{fill:#911}#LA{fill:#119}#MO{fill:#191}#OK{fill:#119}#TX{fill:#191}#AZ{fill:#911}#CA{fill:#191}#CO{fill:#191}#NM{fill:#991}#NV{fill:#991}#UT{fill:#119}#OR{fill:#911}#KS{fill:#911}#NE{fill:#119}#WY{fill:#911}#CT{fill:#911}#MA{fill:#191}#NY{fill:#119}#RI{fill:#119}#DC{fill:#911}#MD{fill:#191}#VA{fill:#119}#DE{fill:#119}#NJ{fill:#191}#PA{fill:#911}#NC{fill:#911}#SC{fill:#191}#IA{fill:#911}#MN{fill:#191}#SD{fill:#991}#WI{fill:#119}#ID{fill:#191}#MT{fill:#119}#WA{fill:#119}#IL{fill:#991}#IN{fill:#191}#KY{fill:#911}#MI{fill:#911}#OH{fill:#119}#WV{fill:#991}#NH{fill:#911}#VT{fill:#991}#ME{fill:#191}#ND{fill:#911}

```

Pasted into an SVG: http://jsbin.com/toniseqaqi/
> 3 votes

# Answer
# JavaScript (ES6) 269 ~~279~~

Recursive search with backtracking. ~80 bytes spent for state list parsing.

```
 F=l=>{
   S=(a,b)=>S[a]=(S[a]||[]).concat(b),
   l.replace(/(..)-(..)/g,(_,a,b)=>S(a,b)+S(b,a)),
   k=Object.keys(S),
   R=(p,c=k[p])=>!c||['blue','gold','red','tan'].some(i=>!c.some(t=>S[t].c==i)&&(c.c=i,R(p+1)||(c.c='')),c=S[c]),
   R(0),
   k.map(k=>console.log('#'+k+'{fill:'+S[k].c+'}'))
 }

```

**Ungolfed**

```
F=l=>{
  var states = {}; // hash table with adiacent list for each state
  S=(a,b)=>states[a]=(states[a]||[]).concat(b);
  l.replace(/(..)-(..)/g,(_,a,b)=>S(a,b)+S(b,a)); // build the hash table from the param list

  keys = Object.keys(states); // get the list of hashtable keys as an array (the 49 states id)
  Scan=(p)=> // Recursive scan function
  {
    var sId = keys[p]; // in sid the current state id, or undefined if passed last key
    if (!sId) return true; // end of keys, recursive search is finished
    var sInfo = states[sId]; // in sInfo the aarray of adiacent states id + the color property

    return ['blue','gold','red','tan'].some( (color) => // check the four avaialabe colors
      {
        var colorInUse = sInfo.some( (t) => states[t].color == color); // true if an adiacent state already has the currnet color
        if (!colorInUse) // if the color is usable
        {
          sInfo.color = color; // assign the current color to the current state
          var ok = Scan(p+1); // proceed with the recursive scan on the next state
          if (!ok) // if recursive scan failed, backtrack
          {
            sInfo.color = ''; // remove the assigned color for the current state
          }
          return ok;
        }
      }
    )
  },
  Scan(0), // start scan
  keys.forEach( (sId) => console.log('#'+sId+'{fill:'+states[sId].color+'}')) // output color list
}

```

**Test** in FireFox/FireBug console

```
list = "AL-FL AL-GA AL-MS AL-TN AR-LA AR-MO AR-MS AR-OK AR-TN AR-TX AZ-CA AZ-CO AZ-NM "+
"AZ-NV AZ-UT CA-NV CA-OR CO-KS CO-NE CO-NM CO-OK CO-UT CO-WY CT-MA CT-NY CT-RI "+
"DC-MD DC-VA DE-MD DE-NJ DE-PA FL-GA GA-NC GA-SC GA-TN IA-MN IA-MO IA-NE IA-SD "+
"IA-WI ID-MT ID-NV ID-OR ID-UT ID-WA ID-WY IL-IA IL-IN IL-KY IL-MO IL-WI IN-KY "+
"IN-MI IN-OH KS-MO KS-NE KS-OK KY-MO KY-OH KY-TN KY-VA KY-WV LA-MS LA-TX MA-NH "+
"MA-NY MA-RI MA-VT MD-PA MD-VA MD-WV ME-NH MI-OH MI-WI MN-ND MN-SD MN-WI MO-NE "+
"MO-OK MO-TN MS-TN MT-ND MT-SD MT-WY NC-SC NC-TN NC-VA ND-SD NE-SD NE-WY NH-VT "+
"NJ-NY NJ-PA NM-OK NM-TX NM-UT NV-OR NV-UT NY-PA NY-VT OH-PA OH-WV OK-TX OR-WA "+
"PA-WV SD-WY TN-VA UT-WY VA-WV";
F(list);

```

*Output*

```
#AL{fill:blue}
#FL{fill:gold}
#GA{fill:red}
#MS{fill:gold}
#TN{fill:tan}
#AR{fill:blue}
#LA{fill:red}
#MO{fill:gold}
#OK{fill:red}
#TX{fill:gold}
#AZ{fill:blue}
#CA{fill:gold}
#CO{fill:gold}
#NM{fill:tan}
#NV{fill:tan}
#UT{fill:red}
#OR{fill:blue}
#KS{fill:blue}
#NE{fill:red}
#WY{fill:blue}
#CT{fill:blue}
#MA{fill:gold}
#NY{fill:red}
#RI{fill:red}
#DC{fill:blue}
#MD{fill:gold}
#VA{fill:red}
#DE{fill:red}
#NJ{fill:gold}
#PA{fill:blue}
#NC{fill:blue}
#SC{fill:gold}
#IA{fill:blue}
#MN{fill:gold}
#SD{fill:tan}
#WI{fill:red}
#ID{fill:gold}
#MT{fill:red}
#WA{fill:red}
#IL{fill:tan}
#IN{fill:gold}
#KY{fill:blue}
#MI{fill:blue}
#OH{fill:red}
#WV{fill:tan}
#NH{fill:blue}
#VT{fill:tan}
#ME{fill:gold}
#ND{fill:blue}

```
> 1 votes

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


# Question
Title: Factor a polynomial over a finite field or the integers
Without using any built-in factoring/polynomial functions, factor a polynomial completely into irreducibles over the integers or a finite field.

# Input

Your program/function will receive some prime (or zero) number `n` as input. The field/ring is the finite field of that order (ie `Z/nZ`), or just `Z` if `n` is `0`. Your program may fail if `n` is not `0` or a prime. The polynomial will be in `F[x]`.

Your program/function will also receive the polynomial as input.

There is some flexibility in the input, be sure to specify how you intend to receive input. For example, the polynomial could be input as a list of coefficients, or in the form most people expect (ex:`50x^3 + x^2`), or some other reasonable form. Or the format of inputting the field/ring could also be different.

# Output

Your program/function will output the polynomial factored completely. You may leave multiple roots expanded (ie `(x + 1)(x + 1)` instead of `(x + 1)^2`). You may remove whitespace between binary operators. You may replace juxtaposition with `*`. You may insert whitespace in weird places. You may reorder the factors into whatever order you want. The `x` term could just be `(x)`. `x` can be written as `x^1`; however the constant term **may not** have `x^0`. Extraneous `+` signs are allowable. You **may not** have a term with a `0` in front, they **must** be left out. The leading term of each factor **must** be positive, negative signs must be outside.

Test cases, your program should be able to produce output for each of these in reasonable time (say, \<= 2 hours):

Input: `2, x^3 + x^2 + x + 1`

Output: `(x + 1)^3`

Input: `0, x^3 + x^2 + x + 1`

Output: `(x + 1)(x^2 + 1)`

Input: `0, 6x^4 – 11x^3 + 8x^2 – 33x – 30`

Output: `(3x + 2)(2x - 5)(x^2 + 3)`

Input: `5, x^4 + 4x^3 + 4x^2 + x`

Output: `x(x + 4)(x + 4)(x + 1)`

Input: `0, x^5 + 5x^3 + x^2 + 4x + 1`

Output: `(x^3 + 4x + 1)(x^2 + 1)`

Special thanks to Peter Taylor for critiquing my test cases

# Answer
> 18 votes
## GolfScript (222 bytes)

```
~.@:q@.0\{abs+}/2@,2/)?*or:^{\1$^base{^q- 2/-}%.0=1=1$0=q>+{{:D[1$.,2$,-)0:e;{.0=0D=%e|:e;(D(@\/:x@@[{x*~)}%\]zip{{+}*q!!{q%}*}%}*e+])0-{;0}{@;@\D.}if}do}*;\).^3$,)2/?<}do;][[1]]-{'('\.,:x;{.`'+'\+'x^'x(:x+x!!*+\!!*}%')'}/

```

Online demo

### Notes

1. The input format is `n` followed by a GolfScript array of coefficients from most to least significant. E.g. `0, x^5 + 5x^3 + x^2 + 4x + 1` should be formatted as `0 [1 0 5 1 4 1]`.
2. Over a finite field, there are only finitely many polynomials of sufficiently small degree to be relevant. However, this is not the case over `Z`. I handle `Z` by using a relaxed form of Mignotte's height bound. A great paper on height bounds in factoring is Bounds on Factors in Z\[x\], John Abbott, 2009 (link is to arxiv preprint; his CV says that it has been accepted by the *Journal of Symbolic Computation*). The most relaxed form given there is in terms of the L-2 norm, but to save bytes I relax further and use the L-1 norm instead. Then it's a case of brute forcing by trial division.
3. Over a finite field, every polynomial is a constant times a monic polynomial, so I only do trial division by monic polynomials and save a reciprocal in the field. However, `Z` is only a ring and so it's necessary to do trial division by non-monic candidate factors. I manage to get away with not implementing rational numbers by doing a leading factor division test and accumulating an "error" flag in `e`.
4. Both points 2 and 3 imply that the case of factoring over `Z` is generally slower, and can't be tested with the online demo. However, the slowest of the official test cases takes 10 minutes, which is well within the "reasonable" time limit.

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


title: Find a representative submatrix

text:
# Question
Title: Find a representative submatrix
You have a matrix of size *m* x *n*.

Each cell in the matrix has a uniformly random integer value *v*, where 0 ≤ *v* \< *i*, and *i* ≤ (*m* x *n*). (Meaning, the matrix contains a maximum of *m* x *n* distinct values, but it may have fewer.)

1) Write a function that accepts input values of *m*, *n*, *i*, and returns a matrix that meets the criteria above.

2) Write a second function that accepts the output of the first function as input, and returns the smallest contiguous submatrix that contains every value of *v* (by returning the submatrix itself, or its coordinates). By “smallest” I mean the submatrix containing the fewest cells.

(If it helps you visualize, the original inspiration for this problem was wondering how to find the smallest rectangle within a GIF that contained all the colors in its palette.)

# Answer
## APL (23 + 56 = 79)

### Function 1 (23):

```
{¯1+⍵⍴(V⍴⍺?⍺)[V?V←×/⍵]}

```

This takes `i` as its left argument and `m n` as its right argument, like so:

```
      +mat←8 {¯1+⍵⍴(V⍴⍺?⍺)[V?V←×/⍵]} 5 5
2 4 7 1 3
7 5 6 7 3
3 1 2 4 6
0 4 2 6 1
5 5 0 0 6

```

### Function 2 (56):

```
{⊃V[⍋≢∘∊¨V←V/⍨{∧/⍵∊⍨∪∊M}¨V←⊃,/{↓∘⍵¨¯1+,⍳⍴⍵}¨↑∘⍵¨,⍳⍴M←⍵]}

```

This takes the output from the first function as its right argument, like so:

```
      {⊃V[⍋≢∘∊¨V←V/⍨{∧/⍵∊⍨∪∊M}¨V←⊃,/{↓∘⍵¨¯1+,⍳⍴⍵}¨↑∘⍵¨,⍳⍴M←⍵]} mat
7 5 6
3 1 2
0 4 2

```
> 2 votes

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


title: Make your country proud!

text:
# Question
Title: Make your country proud!
You are from the tiny country of Que-Wopistan. The Que-Wopistonion's are a proud people, and every Que-Wopistonian dreams of making their country proud by representing their country in the Olympics.

You have been given the incredible honor of competing in the 100-meter-dash. You are the nations sole representative, so there is a huge amount of pressure on you to do well. Unfortunately though, Que-Wopistan's training program is *awful!* Absolutely terrible. You can't work with this, so you decide to train yourself.

You try a few practice runs. On the first run, you make it 0.3 meters forward, and then fall on your face. You are dedicated though, so you get up and try again. This time, you actually go backwards -1.7 meters, before falling on your face again. You try again. And again. And agin. And again, but every time you fall on your face before making even 2 meters forward. You just aren't coordinated enough to run. Or walk. Or even-- *not* fall on your face.

This is where your programming expertise comes in handy.

# The challenge

In case you haven't realized yet, I am talking about the game QWOP. Once you have wasted 60 minutes, mashed your face into the keyboard, and now returned to this page after rage-quitting (don't worry, I did the same thing), here is your challenge. You must write a program that uses simulated key-presses to play the game of QWOP for you. The following actions do not have to be done by your program (you can do them manually yourself)

1. Opening the web browser and going to the correct page.
2. Starting and re-starting the game.
3. Make a screen recording.

Everything else must be automated by your program.

# Judging criteria

The winner of this contest will be the program that makes it the farthest. In the unlikely event of a tie (Which will happen if anyone actually makes it 100 meters), the winner will be decided by who made it there quicker. This is not code-golf, byte-count makes no difference.

If your program automatically detects the game being over (the game ends if you fall on your face or make it 100 meters) and exits, you will get a +10 meter bonus.

# Answer
# AutoHotkey, 100.5 m

After running the following script, it can be activated by pressing Windows+H (yes, it only works on Windows). It can be stopped by pressing Escape.

```
#SingleInstance force

Esc::ExitApp

#h::
    Loop,5 {
        Send, {w down}
        Sleep, 300
        Send, {w up}
        Sleep, 300
    }
    Loop,9999 {
        Loop, 23 {
            Send, {q down}
            Sleep, 200
            Send, {q up}
            Sleep, 400
            Send, {w down}
            Sleep, 350
            Send, {w up}
            Sleep, 400
        }
        Loop,6 {
            Send, {w down}
            Sleep, 250
            Send, {w up}
            Sleep, 400
        }
    }
return

```

This particular code reached the finish line the first time it was run. I don't want to test it again now, because it takes forever and I can't do anything else while running it (Please comment if you figure out how to send keys to the Flash player without it being in focus). Caveat: At around 30 m, no keys were sent for a few seconds because a Windows pop-up jacked the focus. It was tested in Chrome browser.

When the script reached the obstacle at 50 m, the script somehow jumped over it right away, which may be a lucky and unusual occurrence. As for the time, the game irritatingly does not tell you how long the run took, but it does have a built-in tiebreaker by allowing you to jump as far as possible beyond the finish line at the end.

Also, this game's code does not seem very robust:

Huh?
> 9 votes

---
Tags: code-challenge, game, keyboard
---


title: Edge Elimination Number

text:
# Question
Title: Edge Elimination Number
From Erich Friedman's Math Magic, (problem #2 on that page) your challenge is to find the edge elimination number of a connected graph.

A single **edge elimination** is the removal of an edge from a graph, without disconnecting the graph, except for creating lone vertices. For instance, in the graph below, the two leftmost edges and the rightmost edge may be legally eliminated, but the center edge may not, because that would lead to two disconnected components larger than a single vertex.

An **edge elimination sequence** is the elimination of every edge in a graph in a specified order. Each elimination must be legal at the point in the sequence when it is performed. For instance, one legal edge elimination sequence on the above graph would be to remove the rightmost edge, then the center edge, then the top-left edge, then the bottom-left edge.

The **edge elimination number** of a graph is the number of different edge elimination sequences that a graph has. For instance, the above graph has an edge elimination number of 14. There are 4 sequences starting with the top left edge, 4 with the bottom left edge, and 6 with the right edge.

**Input:** The input graph is guaranteed to be connected. The graph will be given as a list of edges with labeled vertices. for instance, the above graph might be given as:

```
[(0,2), (1,2), (2,3), (3,4)]

```

Within that requirement, whatever format is most convenient for your language/code is fine. Don't cheese this. (e.g. no code in the vertex labels.)

**Code:** You may write a program taking input from the command line or from STDIN, or a function, or a verb, or your language's equivalent.

This is code golf, fewest bytes wins.

**Tests:**

```
One edge:
[(0,1)]
1

Path:
[(0,1), (1,2), (2,3), (3,4)]
8

Triangle with two additional edges off one vertex:
[(0,1), (1,2), (0,2), (0,3), (0,4)]
92

Randomly generated:
[(0, 2), (0, 4), (1, 2), (1, 4), (2, 5), (3, 4), (3, 5)]
1240

[(0, 2), (0, 3), (1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (3, 5)]
16560

```

Again, this is code golf, fewest bytes wins. Please ask any clarifying questions, or tell me if I've done something wrong.

# Answer
> 2 votes
# Pyth, 23

```
L?/1lbf!tfaYTbbsmy-b]db

```

Explanation:

`L`: defines a function, `y`, of one input, `b`. Returns the value of its body.

`?`: _ if _ else _

The first argument to `?` will be the value returned if we terminate. The second will be the termination test, and the third will be the recursive case.

`/1lb`: If we terminate, there are two possibilities: we have reached a graph with 1 edge, or we have reached a clearly disconnected graph, which thus has more than one edge. `/1lb` is 1, floor divided by the length of the input graph. This returns 1 in the base case of a 1 edge graph, or 0 in any disconnected termination case.

`faYTb`: This is the inner filter of 2nd argument. It filters out every edge `Y` that overlaps with the edge `T` of the outer filter. `a` is setwise intersection.

`!tfaYTb`: `!` is logical not, `t` is tail, so this will be `True` if there is exactly 1 edge sharing a vertex with `T`, or `False` otherwise.

`f!tfaYTbb`: This runs the above test on every edge in the graph. It is evaluated in a boolean context, and it is truthy if any edge in the graph shares no vertices with any other edge in the graph. If this is the case, we terminate, because the graph is either disconnected or has 1 edge. Note that there are some disconnected graphs that we do not terminate on, but their recursive calls will eventually terminate with a return value of 0.

`smy-b]db`: This is the recursive case. We take the sum, `s`, of the edge elimination number, `y`, of the graph with each edge removed. `-b]d` is `b` with the edge `d` removed, `y-b]d` is the EEN of that graph, and `my-b]db` is this value for `d` being each edge in the graph, and `smy-b]db` is the sum of those values.

Tests: (`yQ` runs the function on the input)

```
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1)]'
1
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1), (1,2), (2,3), (3,4)]'
8
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1), (1,2), (0,2), (0,3), (0,4)]'
92
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,2), (0,4), (1,2), (1,4), (2,5), (3,4), (3,5)]'
1240
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,2),(0,3),(1,3),(1,4),(1,5),(2,3),(3,4),(3,5)]'
16560

```

# Answer
> 3 votes
## APL (77)

```
{0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵}

```

This is a function that takes a list of edges as a graph, i.e.:

```
      {0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵} (0 2)(0 3)(1 3)(1 4)(1 5)(2 3)(3 4)(3 5)
16560

```

(Incidentally, this takes about half a second on my computer.)

So the format is `[[v1,v2], [v1,v2], ...]`. To pass in a single-edge graph, you need to enclose it first, otherwise you get `[0,1]` instead of `[[0,1]]`:

```
      {0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵} ⊂0 1
1

```

Explanation:

* Base case 1 (empty graph):
    + `0=⍴,⍵:1`: if the graph is empty, return `1`: the current path has emptied the graph while keeping it connected.
* Base case 2 (unconnected graph):
    + `C←0/⍨⍴V←∪∊G←⍵`: store the list of edges in `G`, the vertices in `V`, and a `0` for each vertex in `C`.
    + `{`...`}⊃V`: See if the graph is connected. Starting with the first vertex:
        - `C[V⍳⍵]:⍬`: if the vertex has already been visited, do nothing
        - `C[V⍳⍵]←1`: mark the current vertex as visited
        - `G/⍨⍵∊¨G`: find each edge this vertex is connected to
        - `⍵~⍨∊`: find all vertices involved in those edges, except the current vertex
        - `∇¨`: visit all those vertices
    + `0∊C`...`:0`: afterwards, if one of the vertices is not visited, the graph is no longer connected. The current path is invalid, so return `0`.
* Recursive case:
    + `⍵∘~∘⊂¨⍵`: For each edge, create the graph formed by removing that edge, along with any orphaned vertices, from the current graph.
    + `∇¨`: For each of those graphs, find its edge elimination number.
    + `+/`: Sum those.

# Answer
> 2 votes
# Python, 228 bytes

```
p=lambda l,r,d:reduce(lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x]),d,(l,r))
def c(h):
  k=0
  for i in range(len(h)):g=h[:i]+h[i+1:];k+=len(g)<2 or p(set(g[0]),[],g)[1]==[]and c(g)
  return k

```

One edge:

```
c([(0,1)])
1

```

Path:

```
c([(0,1), (1,2), (2,3), (3,4)])
8

```

Triangle with two additional edges off one vertex:

```
c([(0,1), (1,2), (0,2), (0,3), (0,4)])
92

```

Randomly generated:

```
c([(0, 2), (0, 4), (1, 2), (1, 4), (2, 5), (3, 4), (3, 5)])
1240
c([(0, 2), (0, 3), (1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (3, 5)])
16560

```

Explanation:

In the first Statement I create a function that checks if a given graph d is connected.

```
 p=lambda l,r,d:reduce(lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x]),d,(l,r))

```

The idea of this is: You have to reduce a graph with the given edge-tuples to a list which contains every connected point, called connected\_set and a list with all not-connected-yet tuples, called not\_connected. Core is the reduce-function, which is a built-in what calls every a given function with two parameters for each element in a list. Reduce works so: reduce(callable, list, initial)

```
1. callable(initial, list[0]) returns element
2. callable(element, list[1]) ...
3. callable(element, list[n])

```

For given code I return a tuple contained of (connected\_set, not-connected-yet). The initial value is the connected\_set containing of the first found point of the graph. the not-connected-yet is initial en empty list.

```
lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x])

```

means:

```
def reducer((connected_set, not-connected-yet), element):
    #an edge is connected, if left or right point is in connected_set
    if element[0] in connected_set or element[1] in connected_set:
        #add both points to connected_set
        connected_set |= set([x[0], x[1])
        #resolve not-connected-yets
        check_graph(connected_set, not-connected-yet=[], list=not-connected-yet)
        return (connected_set, not-connected-yet)
    else
        return (connected_set, not-connected-yet + [element]

def check_graph(connected_set, not-connected-yet, list):
    return reduce(reducer, list, (connected_set, not-connected-yet))

```

A Graph is connected, when check\_graph returns a tuple, which second element is an empty list.

The rest is addition:

```
def c(h):
  k=0
  for i in range(len(h)):g=h[:i]+h[i+1:];k+=len(g)<2 or p(set(g[0]),[],g)[1]==[]and c(g)
  return k

```

means readable:

```
def count_graph(graph)
    sequences = 0
    #iterate over the possibilities to eliminate an edge on given graph
    # e.g.: graph = [1, 2, 3]
    # i=0: parted_graph = [2, 3]
    # i=1: parted_graph = [1, 3]
    # i=2: parted_graph = [2, 3]
    for i in range(len(graph)):
        parted_graph = graph[:i] + graph[i+1:]
        if len(parted_graph) < 2:
            # a graph with one edge is result of a sequence so raise num
            sequences += 1
        else:
            # continue eliminating if graph is connected
            if check_graph(set(parted_graph[0]), [], parted_graph)[0] == []:
                sequences += count_graph(parted_graph)
    return sequences

```

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


title: Simulate a Cyclic Tag System

text:
# Question
Title: Simulate a Cyclic Tag System
A **cyclic tag system** is a tiny, Turing-complete computational model consisting of a two-symbol alphabet (I'll use `{0,1}`), a finite, nonempty cyclic list of *productions* that consist of those two symbols, and an unbounded *word* which also consists of those two symbols.

At each step:

* the first element in the *word* is removed
* if it was `0` the current *production* is skipped
* if it was `1` the current *production* is appended to the end of the *word*.
* the next *production* becomes active. If this was the last production, go back to the first one.

The system *halts* when the *word* becomes empty.

An example (from Wikipedia):

```
Productions: (010, 000, 1111)
Initial word: 11001

Generation  Production   Word (before)            Word (after)
   0           010           11001             →     1001010
   1           000            1001010          →      001010000
   2           1111            001010000       →       01010000
   3           010              01010000       →        1010000
   4           000               1010000       →         010000000
   5           1111               010000000    →          10000000
   6           010                 10000000    →           0000000010
   7           000                  0000000010 →            000000010
   8           1111                  000000010 →             00000010
   9           010                    00000010 →              0000010

```

Your task, if you choose to accept it, is to write a program or function that takes:

* a list of productions,
* the initial word, and
* a generation,

and prints or returns the *word* at that generation.

For example,

```
cyclic_tag(
      prod=[[0,1,0],[0,0,0],[1,1,1,1]],
      word=[1,1,0,0,1],
      gen=4) => [1,0,1,0,0,0,0]

```

Implementation details:

* The alphabet does not matter. You may use `0` and `1`, `True` and `False`, `T` and `NIL`, `A` and `B`, or even `1` and `0`, or whatever else you may come up with, as long as you are consistent. All input and output must use the same alphabet, and you must indicate what you are using for `0` and what for `1`.
* The length of the *word* must be theoretically unbounded. That is, you may not hardcode a maximum word length. If I run your program on an ideal computer with an infinite amount of memory, your program must theoretically be able to make use of it. (You may ignore your interpreter's/compiler's limits.)
* If the given system halts before the given generation is reached, you must return or print the empty word.
* The empty production exists, and you must be able to handle it. If you write a full program, your I/O must also be able to handle it.

**Edit**: I had originally intended for generation `0` to be the input word itself, and generation `1` to be the result of the first step. I.e., I had intended for you to return the *before* column. *However*, as I have not been clear enough in stating this, **I will accept both options**; for each generation you may return the value in either the *before* or the *after* column. **You must state that you are following the *after* column, if you are doing so.** You must also be consistent in which column you choose.

I will award the smallest code a week from now (10/27/2014).

# Answer
## GolfScript (17 to 19 bytes depending on input format and accepted output format)

18 bytes:

```
~.@*<{\1,or(@*+}/`

```

Takes input in the form `[1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 4` and gives output in the form `[1 0 1 0 0 0 0]`. (Could be **17 bytes** without the last ``` if output as `1010000` is acceptable).

Online demo

19 bytes:

```
~.@*<{\0`or(1&@*+}/

```

Takes input in the form `"11001" ["010" "000" "1111"] 4`.

Online demo

### Dissection

```
~        # Evaluate input: stack: word productions gen
.@*<     # Produce a list of the right number of productions with suitable repetition
{        # For each of those productions:
  \      #   Bring the word to the top
  0`or   #   Ensure that we don't get an error if the word is empty
  (1&    #   Pop the first char from the word and evaluate it
  @*     #   Repeat the production that many times
  +      #   Concatenate 0 or 1 copies of the production to the rest of the word
}/       # Endforeach

```

Credit to Martin Büttner's CJam solution for the idea of generating the list of productions by repetition and truncation.
> 4 votes

# Answer
# Haskell, ~~55~~ ~~53~~ 51

```
(t:w)%p|t=w++p|0<1=w
x%_=x
e w=(!!).scanl(%)w.cycle

```

this uses `True` as `1` and `False` as `0`. example run:

```
*Main> let t=True ; f=False
*Main> e [t,f,t] [[f,f,f],[t,t,t]] 4
[False,False,False,False,False]

```
> 5 votes

# Answer
## CJam, ~~31~~ ~~30~~ ~~28~~ ~~27~~ ~~24~~ 18 bytes

```
{_@*<{\_0a?(@*+}/}

```

This defines a block (the closest thing to a functioN), which expects the input to reside on the stack like this

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

```

It will similarly leave an array of `0`s and `1`s on the stack.

Test it here. Paste the input one the first line, the code on the third line, and append a `~` to actually evaluate the block. E.g.

```
[1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 9
{_@*<{\_0a?(@*+}/}~

```

If output does not have to have the same form as input

Explanation:

```
_@*<{\_0a?(@*+}/
_@               "Duplicate the generation and pull the productions to the top.";
  *<             "Repeat the productions N times and take the first N elements.";
    {         }/ "For each element in that list, run this block.";
     \           "Swap production and current word W.";
      _0a?       "W = (W != []) ? W : [0]. This is to ensure we can unshift an element.";
          (      "Unshift the first 0 or 1 from the word.";
           @     "Rotate the stack, pulling the production to the top.";
            *    "Repeat it 0 or 1 times.";
             +   "Append to the word.";

```

The final state of the word is left on the stack.

Thanks to Peter Taylor for making me revisit this.
> 3 votes

# Answer
## Pyth 22

Requires all 3 arguments as separate inputs.

```
#Vvw=z+tz*@Q%NlQshz)zq

```

Takes arguments like:

```
11001
["010","000","1111"]
4

```

Explanation:

```
                        : Implicit: z = input(); Q=eval(input())
#                       : Loop until an exception is thrown
 Vvw               )    : for N in range(eval(input()))
    =z                  : assign to z
      +tz               : the sum of the tail of z and
         *@Q%NlQ        : Q[N%len(Q)] times
                shz     : the numeric value of the first character in z
                    zq  : print z then throw exception

```

---

## Python 2 - 61 ~~67 91 105 124~~

```
c=lambda p,w,g:g*w and c(p[1:]+p[:1],w[1:]+w[0]*p[0],g-1)or w

```

Pretty Joe-Basic answer. Assumes the empty production is `[[]]`.

Thanks to @xnor, for pointing out that golfing at 2 a.m. is a poor decision.

Additional thanks to @xnor, to whom I seem to owe 50% of my score.

Sample:

```
>>> c([[0,1,0],[0,0,0],[1,1,1,1]],[1,1,0,0,1],4)
[1, 0, 1, 0, 0, 0, 0]

```
> 2 votes

# Answer
# Mathematica, ~~84 80~~ 77 chars

```
f[_,w_,_]=w;f[p_,{x_,y___},n_/;n>0]:=f[RotateLeft@p,Flatten@{y,p~Take~x},n-1]

```

Example:

```
f[{{0, 1, 0}, {0, 0, 0}, {1, 1, 1, 1}}, {1, 1, 0, 0, 1}, 4]

```

> {1, 0, 1, 0, 0, 0, 0}
> 2 votes

# Answer
# Javascript ES6 - 88 bytes

```
f=(p,w,g,n)=>g?w.replace(/(.)(.*)/,(_,a,b)=>f(p,a*1?b+p[(n=n||0)%p.length]:b,g-1,n+1)):w

```

Looks eerily similar to Fry's answer which just popped up in my browser. (No copying, I do solemnly swear.)

It would appear he went the array route while I went the string/regex route, however.

### Expanded:

```
f = (p,w,g,n) =>
    g ?
        w.replace( /(.)(.*)/, (_,a,b) =>
            f( p, a*1 ? b + p[(n=n||0)%p.length] : b, g-1, n+1 )
        )
    :
        w

```

### Sample Output

```
f(['010','000','1111'],'11001',4)
"1010000"

```

Now watch the golf languages come in and massacre both of us. :D
> 1 votes

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


title: Can you hear me now?

text:
# Question
Title: Can you hear me now?
## Background

You are a rich executive of a software empire. Your time is worth a lot of money. As such, you must always travel in the most efficient route possible. However, as an executive, you spend a lot of time participating in important phone calls. It is paramount that you never drop calls, so you must never travel through areas which don't have cell service!

## The Challenge

You'll be given a list of three-tuples, each of which represents the location and power of a cell tower. As an example, `[50, 25, 16]` would represent a cell tower located at `<x,y> = <50, 25>` with a circle of radius 16 representing its circle of influence. With this list in mind, you must travel from your starting position at `<0, 0>` to your destination at `<511, 511>`, in the shortest distance possible without losing cell service. This is , so shortest code wins!

## Input / Output

You are free to manipulate the input into a form that makes it easy to read, such as in a file, or as a nested array through STDIN using `eval`, etc. You may hardcode the input, so long as your code works for other inputs as well. The exact characters used to hardcode the input will not be counted, but the variable name and assignment characters will. You should not assume that the input is in any specific order, or that every cell tower is relevant to the problem. If you have any questions please leave a comment and I will try to clarify it.

The output is to be a list of coordinates, marking points that when connected in order form a path to the exit. The accuracy need only be rounded to the nearest integer, and if you are 1-2 units off of what I have in me output example, that is fine. I have included images below to clarify this.

Best of luck!

## Examples

```
input:
[ 32,  42,  64]
[112,  99,  59]
[141, 171,  34]
[157, 191,  28]
[177, 187,  35]
[244, 168,  57]
[289, 119,  20]
[299, 112,  27]
[354,  59,  58]
[402,  98,  23]
[429,  96,  29]
[424, 145,  34]
[435, 146,  20]
[455, 204,  57]
[430, 283,  37]
[432, 306,  48]
[445, 349,  52]
[424, 409,  59]
[507, 468,  64]

```

```
output:
0 0
154 139
169 152
189 153
325 110
381 110
400 120
511 511

```

```
input2
[ 32,  42,  64]
[112,  99,  59]
[141, 171,  34]
[157, 191,  28]
[177, 187,  35]
[244, 168,  57]
[289, 119,  20]
[299, 112,  27]
[354,  59,  58]
[402,  98,  23]
[429,  96,  29]
[424, 145,  34]
[435, 146,  20]
[455, 204,  57]
[430, 283,  37]
[432, 306,  48]
[445, 349,  52]
[424, 409,  59]
[507, 468,  64]
[180, 230,  39]
[162, 231,  39]
[157, 281,  23]
[189, 301,  53]
[216, 308,  27]
[213, 317,  35]
[219, 362,  61]
[242, 365,  42]
[288, 374,  64]
[314, 390,  53]
[378, 377,  30]
[393, 386,  34]

```

```
output2:
0 0
247 308
511 511

```

The previous path is highlighted in blue, but you can see the addition of more towers allows a more optimal route.

# Answer
> 19 votes
# Python, ~~1,291 1,271~~ 1,225 bytes

As Martin noted, this problem can be largely reduced to his excellent rubber band challenge. Using that challenge's terminology, we can take as the second set of nails the points of intersection between the circles *on the boundary* of the enclosed area:

As the rubber band we can take any path *P* between the two endpoints that runs inside the enclosed area. We can then invoke a solution to the rubber-band problem to produce a (locally) minimal path. The challenge is, of course, to find such a path *P*, or more precisely, to find *enough* paths so that at least one of them produces the globally minimal path (note that in the first test-case we need at least one path to cover all possibilities, and in the second test-case at least two.)

A naive approach would be to just try all possible paths: For every sequence of adjacent (i.e. intersecting) circles that connects the two endpoints, take the path along their centers (when two circles intersect, the segment between their centers is always within their union.) Though this approach is technically correct, it can lead to a ridiculously large number of paths. While I was able to solve the first test-case using this approach within a few seconds, the second one took forever. Still, we can take this method as a starting point and try to minimize the number of paths we have to test. This is what follows.

We construct our paths by basically performing a depth-first search on the graph of circles. We're looking for a way to eliminate potential search directions at each step of the search.

Suppose that at some point we're at a circle *A*, that has two adjacent circles *B* and *C*, which are also adjacent to each other. We can get from *A* to *C* by visiting *B* (and vice versa,) so we might think that visiting both *B* and *C* directly from *A* is unnecessary. Unfortunately, this is wrong, as this illustration shows:

If the points in the illustration are the two endpoints, we can see that by going from *A* to *C* through *B* we get a longer path.

How about this one: if we're testing both the moves *A**B* and *A**C*, then it's unnecessary to test *A**B**C* or *A**C**B*, since they can't result in shorter paths. Wrong again:

The point is that using purely adjacency-based arguments is not going to cut it; we have to use the geometry of the problem as well. What the two above examples have in common (as well as the second test-case on a larger scale,) is that there's a "hole" in the enclosed area. It manifests itself in the fact that some of the points-of-intersection on the boundary—our "nails"—are within the triangle △*ABC* whose vertices are the circles' centers:

When this happens, there's a chance that going from *A* to *B* and from *A* to *C* will result in different paths. More importantly, when it *doesn't* happen (i.e. if there wasn't a gap between *A*, *B* and *C*) then it's guaranteed that all paths starting with *A**B**C* and with *A**C* and which are otherwise equivalent will result in the same locally minimal path, hence if we visit *B* we don't need to also visit *C* directly from *A*.

This leads us to our elimination method: When we're at a circle *A*, we keep a list *H* of the adjacent circles we've visited. This list is initially empty. We visit an adjacent circle *B* if there are any "nails" in *all* the triangles formed by the centers of *A*, *B* and any of the circles in *H* adjacent to *B*. This method dramatically drops the number of paths we have to test to just 1 in the first test-case and 10 in the second one.

A few more notes:

* It's possible to decrease the number of paths we test even further, but this method is good enough for the scale of this problem.
* I used the algorithm from my solution to the rubber-band challenge. Since this algorithm is incremental it can be pretty easily integrated into the path-finding process, so that we minimize the path as we go along. Since many paths share a starting-segment, this can significantly improve performance when we have lots of paths. It can also hurt performance if there are much more dead-ends than valid paths. Either way, for the given test-cases performing the algorithm for each path separately is good enough.
* There's one edge-case where this solution may fail: If any of the points on the boundary is the point of intersection of two tangent circles then under some conditions the result can be wrong. This is due to the way rubber-band algorithm works. With some modifications it's possible to handle these cases as well, but, hell, it's already long enough.

---

```
# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}
# Second test case
#I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.),((180.,230.),39.),((162.,231.),39.),((157.,281.),23.),((189.,301.),53.),((216.,308.),27.),((213.,317.),35.),((219.,362.),61.),((242.,365.),42.),((288.,374.),64.),((314.,390.),53.),((378.,377.),30.),((393.,386.),34.)}

from numpy import*
V=array;X=lambda u,v:u[0]*v[1]-u[1]*v[0];L=lambda v:dot(v,v)
e=V([511]*2)
N=set()
for c,r in I:
 for C,R in I:
  v=V(C)-c;d=L(v)
  if d:
    a=(r*r-R*R+d)/2/d;q=r*r/d-a*a
    if q>=0:w=V(c)+a*v;W=V([-v[1],v[0]])*q**.5;N|={tuple(t)for t in[w+W,w-W]if all([L(t-T)>=s**2-1e-9 for T,s in I])}
N=map(V,N)
def T(a,b,c,p):H=[X(p-a,b-a),X(p-b,c-b),X(p-c,a-c)];return min(H)*max(H)>=0
def E(a,c,b):
 try:d=max((X(n-a,b-a)**2,id(n),n)for n in N if T(a,b,c,n)*X(n-b,c-b)*X(n-c,a-c))[2];A=E(a,c,d);B=E(d,c,b);return[A[0]+[d]+B[0],A[1]+[sign(X(c-a,b-c))]+B[1]]
 except:return[[]]*2
def P(I,c,r,A):
 H=[];M=[""]
 if L(c-e)>r*r:
    for C,R in I:
     if L(C-c)<=L(r+R)and all([L(h-C)>L(R+s)or any([T(c,C,h,p)for p in N])for h,s in H]):v=V(C);H+=[(v,R)];M=min(M,P(I-{(C,R)},v,R,A+[v]))
    return M
 A+=[e]*2;W=[.5]*len(A)
 try:
  while 1:
    i=[w%1*2or w==0for w in W[2:-2]].index(1);u,a,c,b,v=A[i:i+5];A[i+2:i+3],W[i+2:i+3]=t,_=E(a,c,b);t=[a]+t+[b]
    for p,q,j,k in(u,a,1,i+1),(v,b,-2,i+len(t)):x=X(q-p,c-q);y=X(q-p,t[j]-q);z=X(c-q,t[j]-q);d=sign(j*z);W[k]+=(x*y<=0)*(x*z<0 or y*z>0)*(x!=0 or d*W[k]<=0)*(y!=0 or d*W[k]>=0)*d
 except:return[sum(L(A[i+1]-A[i])**.5for i in range(len(A)-1)),id(A),A]
print V(P(I,e*0,0,[e*0]*2)[2][1:-1])

```

Input is given through the variable `I` as a set of tuples `((x, y), r)` where `(x, y)` is the center of the circle and `r` is its radius. The values must be `float`s, not `int`s. The result is printed to STDOUT.

## Example

```
# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}

[[   0.            0.        ]
 [ 154.58723733  139.8329183 ]
 [ 169.69950891  152.76985495]
 [ 188.7391093   154.02738541]
 [ 325.90536774  109.74141936]
 [ 382.19108518  109.68789517]
 [ 400.00362897  120.91319495]
 [ 511.          511.        ]]

```

---
Tags: code-golf, math, geometry, path-finding
---


# Question
Title: Program an Artistically Rich Comic Strip
### The Challenge

**Program a comic strip.** As artistically rich and detailed as you can possibly make it, so long as it complies with the following rules:

* the comic must be your own original work, *not* a duplicate or approximation of an existing comic (you may however use characters from an existing strip as an homage, if you desire)
* the comic must contain at least one panel, and all panels must be surrounded by a clear border
* the comic must contain at least one blurb of readable text with ≥ 10 characters that is clearly recognizable as text; this may come in the form of a caption, a text bubble, a thought bubble, a sign, etc.
* the comic may be graphic-based or text-based (more on this below)
    + if text-based, the comic must have dimensions of at least 30x25 chars, and no greater than 160x80 chars
    + if graphic-based, the comic must have dimensions of at least 300x300 pixels, but no greater than 1600x1000 pixels
* the comic must be generated by a program whose **core code** contains at most **512 bytes**
* the comic must comply with the StackExchange content policy

### What is "Core Code"?

This is a somewhat novel concept, hence please bear with me in patience.

For programming language *X*, consider the most elementary code that outputs a single (black) circle or ASCII letter `o` at coordinates (10,10) on a (white) canvas and then terminates. The colours *black* and *white* above may refer to any two colours. "Output" refers to text being printed to **stdout**/console, text being outputted to a file, a graphic being drawn to a window, or a graphic being saved to a file. The two key points are that

* the code is able to render this most basic output
* the code contains nothing nonessential (within reason, and subject to reader scrutiny) for rendering this specific output, which includes comments (whitespace is fine)

This elementary program is called your **shell**. From the shell, delete as many or as few commands as you wish and identify at most two *insertion points* where new code can/will go. Any code inserted at these points is called your **core code**. The length of your core code is the total length (in bytes) of code inserted at these points.

The following are six representative examples of acceptable shells:

```
--- Text Output with C (type 1) ---

#include <stdio.h>
#include <Windows.h>

void P( int x, int y, char c ) {
    COORD p = { x, y };

    SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HANDLE ), p );
    printf( "%c", c );
}

int main() {
    system( "cls" );
    P( 10, 10, 'o' );
    return 0;
}

--- Text Output with C (type 2) ---

int main() {
    puts( "\n\n\n\n\n\n\n\n\n         o" );
    return 0;
}

--- Graphical Output with Javascript ---

(function(){
    document.body.innerHTML = '<canvas id="cvs1" width="300" height="300"></canvas>';

    with( document.getElementById('cvs1').getContext('2d') ) {
        fillStyle = 'rgb(192,192,192)';
        strokeStyle = 'rgb(0,0,0)';
        fillRect( 0, 0, 300, 300 );
        beginPath();
        arc( 10, 10, 5, 0, 2*Math.PI );
        stroke();
    }
})();

--- Text Output with HTML ---

<html><body bgcolor="#CCCCCC">
    <br><br><br><br><br><br><br><br><br>
             o
</body></html>

--- Graphical Output with Python (Turtle Library) ---

from turtle import*

fd( 10 );
rt( 90 );
fd( 10 );
circle( 5, 360 );

--- Text Output with MATLAB ---

G = repmat( ' ', 30, 30 );
G(10,10) = 'o';
disp( G );

```

If you prefer, your shell may be empty.

I have started a discussion here for readers unsure of what the community considers appropriate in this respect. Note that this is a **popularity contest**, so making sure the community doesn't consider you to be breaking the rules is important.

### What To Present

1. your **core code**, either as a single block or as two separate blocks if you have two separate insertion points
2. your **shell**, using the distinctive ✰ character (Unicode U+2730) to mark any insertion points (or simply say "no shell")
3. your comic in a text block, or as an image, or as a link to either of the aforementioned. If your comic is text-based and looks better in a different font, charset, etc., you can provide a screenshot or a link to an online environment where the text can be viewed.

### Scoring

This is a **popularity contest** and hence your score is at the whim of the voters.

This is a competition about artistically rich comic book (or graphic novel) style artwork. Humour is a nice touch, but should not be used as a principle criterion for judging entries.

Voters can of course vote any way they want, but as a rough set of guidelines they (you) might wish to consider:

* artistry (whether the comic is especially artful within the artist's chosen medium), with emphasis on features such as
    + beautiful art
    + texturing
    + detailed and/or recognizable characters
    + rich embellishments such as call-outs, fancy borders, shading effects, etc.
* complexity (whether the artist/programmer really gets his/her money's worth out of 512 characters)
* creativity (special additional "wow" factors that make the comic stand out in some way)

Feel free to raise questions or concerns in the comments section.

# Answer
> 8 votes
# HTML (with JS)

## Shell

```
<canvas id='cnv' width=410 height=300></canvas>
<script>
var c = document.getElementById('cnv');
with (C = c.getContext('2d')) {
✰~~beginPath();
    arc(10, 10, 5, 0, 2*Math.PI);
    stroke();~~}
</script>
```

## Full code (511 characters of core code)

It's a runnable Stack Snippet! You can try it yourself, right here, from your own browser. (Note: text may overflow if you have a different font than me.)

```
<canvas id='cnv' width=410 height=300></canvas>
<script>
var c = document.getElementById('cnv');
with (C = c.getContext('2d')) {
font='9px serif'
r=(m=Math).random;p=m.PI
function f(x,y,t,l,T){for(i=0;i<(l||100);++i)C.fillRect(x+r(),y+r(),3,3),x+=m.sin(t),y+=m.cos(t),t+=(T||0)}
for(n=0;n<5;++n){f((N=100*n),n,0)
f(N+10,y=20,0,0,0.1)
f(N+y,30,0,30)
for(v=40;v<70;v+=20)f(N+y,v,0.3,30),f(N+y,v,-0.3,30)
j=0;["Wow, I don't0know why I0wrote this awful0code for0Programming0Puzzles &0Code Golf.".split(0),["Isn't that...",'PUZZLING?'],[''],['...no? Okay.'],['']][n].map(function(x){
fillText(x,N+40,(j++)*9+y)})}
f(0,0,p/2,400);f(0,100,p/2,400)
}
</script>
```

XKCD-style! (The hand-drawn effect is a bit subtle; I might make it more pronounced later.)

---
Tags: popularity-contest, ascii-art, graphical-output
---