title: Write an Antiquine

text:
# Question
Title: Write an Antiquine
# Definitions:

I define a "true antiquine" as follows:

> A true antiquine is a non-empty computer program of length `n` which takes no input and produces a copy of every valid program of length `n` in the same language, except the original program.

I define a "modified antiquine" as follows:

> A modified antiquine is a non-empty computer program of length `n` which takes no input and produces a copy of every valid ASCII (0-127/7-Bit ASCII, specifically) string of length `n`, except the original program.

Here's what I mean when I say "produces":

> A program is said to produce a string if it, were it allowed to run for an arbitrary finite period of time, would print and/or save and/or display a string that contains the string to be produced. In other words, the output must only contain the produced string as a substring. Inversely, any string that is a substring of the output is considered produced, and conversely, any string which does not contain a substring has not produced that substring.

---

# Problem:

Write either a true antiquine or modified antiquine. The program doesn't need to finish in any reasonable amount of time, but has to finish eventually.

The program must be at least 20 characters long. If writing a true antiquine, there must be at least two other valid programs of the same length in the same language as that the program is written in.

If writing a "modified antiquine", the character length restriction is lifted, but of course, a bigger score penalty is received.

---

# Scoring:

The lowest score wins. The formula for scoring programs is as follows:

**(Bytes of Code) \[ * 10 if a modified antiquine \]**

# Answer
> 4 votes
# CJam, 2400

```
'¡G42#{(_128b:co0c24*o}h

```

This takes advantage of what seems to be yet another loophole in the question. My code contains the character `¡` (codepoint 161 in Unicode or ISO-8559-1) to avoid checking if the output may produce the original source codes).

Also, after every program with 24 or less bytes, 24 NUL bytes are printed to avoid generating the original source code as part of two outputs and to make sure all strings starting with a run of NUL characters are generated.

# How it works

```
'¡        " Push a non-ASCII character.                   ";
G42#      " Push I := 16 ** 42 = 128 ** 24.               ";
{         " Do:                                           ";
  (_      " Decrement I and push a copy.                  ";
  128b:co " Get the associated ASCII string and print it. ";
  0c24*o  " Print 24 NUL bytes.                           ";
}h        " While I is positive, repeat.                  ";

```

# Answer
> 3 votes
# C, 392 * 10 = 3920

Nobody's submitted a true answer yet, so I'll offer up a baseline solution:

```
char*s="char*s=%c%s%c;n;main(){char b[999],t[392]={0};sprintf(b,s,34,s,34);while(1){n=0;while(n<392&&t[n]==127)t[n++]=0;if(n==392)break;t[n]++;if(strcmp(b,t)){for(n=0;n<392;n++)putchar(t[n]);putchar(10);}}}";n;main(){char b[999],t[392]={0};sprintf(b,s,34,s,34);while(1){n=0;while(n<392&&t[n]==127)t[n++]=0;if(n==392)break;t[n]++;if(strcmp(b,t)){for(n=0;n<392;n++)putchar(t[n]);putchar(10);}}}

```

**Testing is not recommended outside of a debugging environment--this program will not terminate on its own for the foreseeable future.** Prints every combination of 392 characters that *isn't* the source, separated by newlines. Because the source contains no newlines, the full source will never appear in the output. I've run it through most of the tests I can think of, and it seems to work, but this is of course difficult to verify. This program is essentially a modified quine--rather than printing the source out, it saves it in the string `b`. It generates a unique string, checks it against `b`, and outputs it if it is different. This could probably be shortened a bit.

---
Tags: code-golf
---


# Question
Title: Generate unique non-sequential string of length n without memory of previously generated strings
# Scenario:

Imagine a situation where you wish to share a unique alphanumeric code. Perhaps it is a one-time-use coupon code you hand write on business cards, or some other scenario where it is desirable to have a code where mis-keying the entry is unlikely to produce valid result and the another valid code is not readily guessed.

However, when you are issuing these codes you do not have access to the list of codes that have already been issued. Rather, you know only *how many* have been issued before.

# Challenge:

Write a function that generates a unique string of length n, subject to the following constraints:

* **Available Characters**: Each character in resultant string shall be from a configurable list of allowed values, which may be "hard-coded" into the algorithm.
    + Sample List: A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q, R, S, T, U, V, W, X, Z, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (A-Z and 0-9, omitting "I" and "J")
* **Configurable Length Output**: The length n of the generated string shall be configurable within the algorithm, for n\<=8.
* **Input**: A seed is available (unique sequential positive integer \>=1 and up to 10 digits)
* **Stateless**: The algorithm has no memory of previously generated strings (no database calls)
* **Repeatable**: The same seed shall yield the same result
* **Unordered Output**: Sequential seed values shall not generate strings in any obvious order (that is to say, results should superficially "appear" random)
    + *For example,* `1:"AAAA", 2:"AAAB", 3:"AAAC", ...` *would NOT qualify, while* `1:"RR8L", 2:"1D9R", 3:"TXP3", ...` *is on the right track.*
    + ***Note:*** While this criterion is admittedly subjective, "degree of randomness" is not intended to be the core aspect of this function. Given the *Popularity Contest* format, I'll leave it up to the community to decide whether a pattern is too obvious.
* **Unique Output**: String shall be unique, at least within limitations of available characters and requested string length. Therefore, each possible permutation is to be used exactly once before any combination may be reused.
    + *For example, if configured to generate a string of length n=5 and the available characters include A-Z and 0-9 except for "O", "I" (34 possible characters), then the string may not repeat between seed\>=1 and seed\<=45,435,424.*
    + *However, if length n=4 with 34 available characters, then the same string need only be unique on seed\>=1 and seed\<=1,336,336*

# **Winning Criteria:**

***Popularity Contest*** \- Submission with the most upvotes will be selected as the winner no sooner than two weeks after the first valid solution. Please upvote any and all submissions you feel adequately meet the above criteria.

# Answer
> 5 votes
# C(++) - we don't need no friggin' primes

The problem is to generate a different permutation of **n** characters taken from an **a** size alphabet for each seed value.

There are **an** such permutations, and they can be represented as values of a **n** digits number in base **a**.

The number of bits necessary to represent all these values is **log2(an)**, rounded up.

We have at most 8 characters per code, and the alphabet contains at most 256 characters, so a 64 bits word is just what we need to cover all possible codes with all possible alphabets.

Now we just need something that maps all possible 232 seed values to the possible range of code values (and looks random enough).

I settled for a basic 32 bits reversal, which gives highest variability for low seed values.

If the possible codes range is smaller than the seed's, there will be duplicates anyway, and the codes will be like the n first digits of a greater number.

If the 232 seed values are not enough to cover all code values, the scrambled seed is extended to the smallest power of two inferior to code max value, by injecting 0s in the lower bits.

This should spread the range of code values while guaranteeing no duplicates.
However, the last digit will have a slightly lower frequency due to the rounding to a power of 2.
If alphabet size is much greater than 2, the difference will be hardly noticeable.

The scrambled seed is then converted as a number in base a, the digits being the symbols of the alphabet.

## A few (pseudo) random thoughts

The big weakness of this method is that it won't work well with alphabets whose size is a power of two. The apparent randomness is due to the non-integer number of bits needed to encode a digit.

On second thought maybe we *do* need some friggin primes after all...

At any rate, even the most magnificent pseudo-random repartition is useless as far as data protection is concerned, since the encryption method is stateless and could be easily cracked by brute-force.

## The code

I used the excellent bit shuffling generator of Mr. Jasper Neumann to produce the bit reverser, though other solutions are possible.

I compiled with g++4.8 under MinGW/Win7, but the code is nothing but glorified C and should work with any C++ compiler.

```
#include <cstdlib> // atoi
#include <cstdio>  // printf
#include <cmath>   // pow

#define Alphabet "ABCDEFGHKLMNOPQRSTUVWXYZ0123456789"
#define Length 8

unsigned bit_permute_step_simple(unsigned x, unsigned m, unsigned shift)
{
  return ((x & m) << shift) | ((x >> shift) & m);
}

unsigned shuffle (unsigned x)
{
    x = bit_permute_step_simple(x, 0x55555555, 1);  // Bit index complement 0
    x = bit_permute_step_simple(x, 0x33333333, 2);  // Bit index complement 1
    x = bit_permute_step_simple(x, 0x0f0f0f0f, 4);  // Bit index complement 2
    x = bit_permute_step_simple(x, 0x00ff00ff, 8);  // Bit index complement 3
    x = bit_permute_step_simple(x, 0x0000ffff, 16);  // Bit index complement 4
    return x;
}

#define Base (sizeof(Alphabet)-1)
typedef char Code[Length+1];

void gen_code (unsigned seed, Code code)
{
    // shuffle seed bits (the inversion is to avoid zero value for seed = 0)
    unsigned long long scrambled = shuffle(~seed);

    // if maximal code size is less than seed max value, there will be duplicates anyway
    int extra_bits = floor(Length * log(Base)/log(2)) - 32;
    if (extra_bits > 0) scrambled <<= extra_bits;

    // basic base conversion.
    // The last code digit might have a slightly lower frequency than others
    int i;
    for (i = 0 ; i != Length ; i++)
    {
        int digit = scrambled % Base;
        code[i] = Alphabet[digit];
        scrambled /= Base;
    }
    code[i] = '\0';
}

int main (int argc, char * argv[])
{
    if (argc != 2) exit(-1);
    unsigned seedm = atoi(argv[1]);
    Code code;

    for (unsigned seed = 0 ; seed != seedm ; seed++)
    {
        gen_code (seed, code);
        printf ("code (%u) = %s\n", seed, code);
    }

    return 0;
}

```

The `main()` prints a specified number of codes for consecutive seeds.

Sample output:

n=8, alphabet = `ABCDEFGHKLMNOPQRSTUVWXYZ0123456789`

```
code (0) = 215GVK7B
code (1) = MPPT46CX
code (2) = 4AF2E28Y
code (3) = GLGGAS6W
code (4) = U3MSPN2Y
code (5) = CR42Y97H
code (6) = WCWB943L
code (7) = CZW2XAAB
code (8) = UBHMSV6C
code (9) = CZ0W1HCY
code (10) = WMS5BD8Z
code (11) = 8UTL725X
code (12) = MDYVMY1Z
code (13) = 40F6VM7K
code (14) = OO7E6F3M
code (15) = U5L28BA5
code (16) = 08GMUH56
code (17) = KW0W35AS
code (18) = 2HS5D16T
code (19) = ESTL9Q4R

```

n=4, alphabet = `ABCDE`

```
code (0) = AEBD
code (1) = CEAE
code (2) = BEDD
code (3) = DECE
code (4) = DBAB
code (5) = ACEB
code (6) = EBCB
code (7) = BCBC
code (8) = ECDE
code (9) = BDCA
code (10) = ADAA
code (11) = CDEA
code (12) = CACC
code (13) = EABD
code (14) = DAEC
code (15) = ABDD
code (16) = CDCB
code (17) = EDBC
code (18) = DDEB
code (19) = AEDC

```

# Answer
> 4 votes
# Python 3:

The main task of this challenge is to find a bijection between `[0, 1, ..., #alphabet^length-1]` to itself, which appears to be random.

I stumbled about linear congruential generators, which generate a permutations of the numbers, when the parameters of it satisfy some properties. But interestingly the resulting strings didn't looked random at all. So I decided to do some own stuff.

One obvious bijection is the function `f(x) = (a * x + c) % m`, where `m = #alphabet^length`, `a` and `m` are random numbers with `gcd(a,m) = 1`. Since the function has to be repeatable, I used the fixed values `a = 0.4 * m` and `c = 0.3 * m`. Of course this is nowhere near random.

The second bijection is based on primitive roots. When `p` is a prime (or 4, or (prime\>2)^alpha, or 2\*(prime\>2)^alpha), then there exists values `g`, where `g^i` generates a permutation of all numbers. Therefore I search for next primes smaller than `m` and `g` is approximately `m/3`. Since `p` is smaller than `m`, not all numbers are effected by this approach, I have to use it twice, once for the first `p` numbers and once for the last `p` numbers.

My program first applies the first and than the second bijection. And the result looks quite random to me. E.g. the output for the alphabet `ABC` and length `3` is: `BCB, ACA, BCC, BBC, CCA, ABC, CAA, ABB, CAB, AAC, AAA, BAC, BBB, CBC, BAB, ACB, BBA, BCA, CBA, CCC, AAB, ABA, CAC, BAA, ACC, CCB, CBB`.

```
from fractions import gcd
from numbthy import is_prime, is_primitive_root

def random_linear_congruence(length, seed):
    multiplier = int(length * 0.4)
    while gcd(multiplier, length) > 1:
        multiplier += 1

    start_value = int(length * 0.3)
    return (start_value + seed*multiplier) % length

def random_primitive_root(length, seed):
    prime = length
    while not is_prime(prime):
        prime -= 1

    prim_root = prime // 3
    while not is_primitive_root(prim_root, prime):
        prim_root = (prim_root - 1 ) % prime

    random_number = seed
    if 0 < seed < prime:
        random_number = (prim_root ** seed) % prime

    t = length - prime
    if random_number > t:
        random_number = ((prim_root ** (random_number - t)) % prime) + t

    return random_number

def unique_nonsenquential_string(alphabet, length, seed):
    alphabet = sorted(alphabet)
    modulus = len(alphabet)**length

    random_number = seed
    random_number = random_linear_congruence(modulus, random_number)
    random_number = random_primitive_root(modulus, random_number)

    # convert to base len(alphabet)
    word = []
    for i in range(length):
        word.append(random_number % len(alphabet))
        random_number //= len(alphabet)

    return ''.join(map(lambda x: alphabet[x], word))

outputs = set()
alphabet = "ABC"
length = 3
for seed in range(len(alphabet)**length):
    random_string = unique_nonsenquential_string(alphabet, length, seed)
    outputs.add(random_string)
    print("Seed {:2d}: {}".format(seed, random_string))
if len(outputs) == len(alphabet)**length:
    print("Unique output")

```

You can find `numbthy.py` here: Basic Number Theory functions implemented in Python

# Answer
> -1 votes
# Simplicity (python 2)

This may not be in the spirit of the challenge, but it works, and is far simpler than the other algorithms.

```
import random
from string import uppercase

def unique_code(n, seed, alphabet):
    pre_state = random.getstate() #so we don't interfere outside scope
    random.seed(seed)
    code = ''.join([random.choice(alphabet) for _ in xrange(n)])
    random.setstate(pre_state)
    return code

length = 4
for i in range(20):
    print '{} [seed {:d}]'.format(unique_code(length, i, uppercase), i)

```

Running this code gives:

```
VTKG [seed 0]
DWTG [seed 1]
YYBC [seed 2]
GOJP [seed 3]
GCKE [seed 4]
QTUY [seed 5]
UVMG [seed 6]
IDQB [seed 7]
FZDS [seed 8]
MJDW [seed 9]
OLPF [seed 10]
LOYM [seed 11]
MRRD [seed 12]
GRRW [seed 13]
CSQY [seed 14]
ZATE [seed 15]
JMKL [seed 16]
NUYH [seed 17]
ERIF [seed 18]
RUNN [seed 19]

```

---
Tags: string, popularity-contest, repeated-transformation
---


title: Code Explanation Formatter

text:
# Question
Title: Code Explanation Formatter
Successful code golf submissions are, by nature, filled with crazy symbols all over the place. To make their submission easier to understand, many code-golfers choose to include an explanation of their code. In their explanation, the line of code is turned into a vertically exploded diagram.

For example, if this were my code:

```
1_'[3:~2@+]`

```

One of the many possible diagrams I could create would look like this:

```
1
 _'
   [      ]
   [3:    ]
   [  ~   ]
   [   2@ ]
   [     +]
           `

```

---

**The Goal**

In this challenge, you will write an explanation auto-formatting tool which takes a line of code and creates a diagram to which explanatory text can be easily added.

In order to make this a more *useful* challenge, the user will be able to specify the contents of each line, by providing a formatting string. The formatting string will be a second line, containing only letters `A-Za-z`, that is the same length as the program. The letters show the order in which the characters of the program should be printed in the explanation.

Here is an example of I/O *without any bracket-like formatting*:

```
123423
AabcBC

1
    2
     3
 2
  3
   4

```

**Brackets**

If more than one character in the program has the same priority level, then that set of characters acts as a single block of code (if they form a group) or a set of brackets (if they contain other characters in-between). The general rules are simple:

1. Characters do not appear in a line of the diagram until all other characters of greater priority have already appeared on the lines above it in the diagram.
2. Characters of equal priority are always printed on the same lines. If a certain character appears on a line, all other characters of equal priority appear on the line.
3. A set of characters of equal priority continue to appear on each line until all other characters enclosed by it have appeared at least once. This allows for "bracket-like" constructions. If `bceab` are the priorities, then the `b` characters will appear on the second line (they are second-highest priority) and will continue to appear until all of the `cea` characters have appeared. If the priority string is `abcadeafga`, then all of `bcdefg` are considered contained within it, an all 4 `a`s will continue to appear until the `g` has appeared.

**More formatting requirements**

All lines of output should be the same length (the length of the input lines), padded with spaces as necessary. The input program line may contain spaces, although those spaces will also be given a priority letter. Trailing newlines on output/input are optional.

**Scoring**

This is code golf, fewest bytes wins.

---

**Examples**

Here is a commented example of a piece of code with more complex formatting.

```
1_'[3:~2@+]`
abbcddeffgch

1            #highest priority is denoted by the lowercase letter a
 _'          #priority b
   [      ]  #all characters with priority c
   [3:    ]  #priority d, but priority c still printed because it encloses more
   [  ~   ]  #priority e
   [   2@ ]  #priority f
   [     +]  #priority g, last line of c because all enclosed characters have appeared
           ` #priority h

```

An example in Perl:

```
$_=<>;s/[^aeiou\W]/$&o$&/gi;print
aaaaaabbccccccccccbdddddbbbbeeeee

$_=<>;
      s/          /     /gi;
      s/[^aeiou\W]/     /gi;
      s/          /$&o$&/gi;
                            print

```

Here are a few examples in CJam, courtesy of Martin Büttner:

```
l~2*{_2%{3*)}{2/}?_p_(}g;
aabbcdddefffeeggeehhiiccj

l~
  2*
    {                 }g
    {_2%              }g
    {   {   }{  }?    }g
    {   {3*)}{  }?    }g
    {   {   }{2/}?    }g
    {             _p  }g
    {               _(}g
                        ;

q{_eu'[,66>"EIOU"-#)g{'o1$}*}/
abcccddddddeeeeeeefgghiijjhhbb

q
 {                          }/
 {_eu                       }/
 {   '[,66>                 }/
 {         "EIOU"-          }/
 {                #         }/
 {                 )g       }/
 {                   {    }*}/
 {                   {'o  }*}/
 {                   {  1$}*}/

```

Here is a crazy example just to mess with you:

```
1_'[3:~2@+]`
azTABACBDCAT

   [ :    ]
   [3: 2  ]
   [3:~2 +]
   [ :~ @+]
  '        `
1
 _

```

Here is a more explicit example of what happens when brackets overlap like `abab`. (Normally, this is not the way you would choose to format your explanation.)

```
aabbccddaaeebb
aabbccddaaeebb

aa      aa
aabb    aa  bb
aabbcc  aa  bb
aabb  ddaa  bb
  bb      eebb #"aa" no longer appears because all of "bbccdd" have already appeared.

```

# Answer
> 15 votes
# Pyth, ~~33~~ 40 bytes

```
JwFHS{Js.e?@zk&gHYsm&gdH}d>_>JxJYx_JYJdJ

```

Try it online: Pyth Compiler/Executor

## Explanation:

Generated with the string `aabbbbbzccdeeegfffqhjiiikkpnmmllloooohec`:

```
                                          implicit: z = first input line
Jw                                        J = second input line
  FHS{J                                   for H in sorted(set(J)):
        .e                             J    map each k,Y of enumerate(J) to:
        .e?                            J      .... if ... else ...
        .e @zk                        dJ      z[k] if ... else " "
                                              condition:
        .e @zk gHY                    dJ        H >= Y
        .e @zk&                       dJ        and
        .e @zk     m                 JdJ        map each d of J to:
        .e @zk     m gdH             JdJ          d >= H
        .e @zk     m&                JdJ          and
        .e @zk     m    }d           JdJ          d in ...
        .e @zk     m          xJY    JdJ          index of Y in J
        .e @zk     m        >J       JdJ          substring of J (from index to end)
        .e @zk     m       _         JdJ          reverse substring
        .e @zk     m             x_JYJdJ          index of Y in reversed J
        .e @zk     m      >          JdJ          substring of reversed (from index to end)
        .e @zk    s                   dJ       sum up the booleans (acts as any)
       s                                    sum up the chars and print

```

So the first input line is `z`, the second input line is `J`.

The loop iterates over all chars of `J` in sorted order and without duplicates. The current char is called `H`.

Then for each `Y` of `J` I print the correspondent char of `z` or a whitespace, depending on if both of the following conditions are satisfied:

* `Y <= H` (a char first appears in the line `H`)
* there is a char `d >= H`, which appears in a block starting and ending with `Y` (brackets).

## Examples

This shows how the forth line of the input `abcdaeb`, `abcdaeb` is printed. The fourth line is a good representation, since most of the possible cases happen:

```
code input:  "abcdaeb"
order input: "abcdaeb"

printing the fourth line, H = "d":

   "a" is printed, because "a" <= "d" and ("d" >= "d" and "d" is in "abcda")
   "b" is printed, because "b" <= "d" and ("d" >= "d" and "d" is in "bcdaeb")
   "c" are not printed, because neither "d" nor "e" (chars >= "d") are not in "c"
   "d" is printed, because "d" <= "d" and ("d" >= "d" and "d" is in "d")
   "a" is printed, because "a" <= "d" and ("d" >= "d" and "d" is in "abcda")
   "e" is not printed, because "e" > "d"
   "b" is printed, because "b" <= "d" and ("d" >= "d" and "d" is in "bcdaeb")

therefore the fourth line is: aabb__ddaa__bb

```

And another example based on a test-case, @Optimizer gave me. (which destroyed my 33 solution).

```
code input:  "acab"
order input: "acab"

printing the second line, H = "b":

   "a" is printed, because "a" <= "b" and ("c" >= "b" and "c" is in "aca")
   "c" is not printed, because "c" > "b"
   "a" is printed, because "a" <= "b" and ("c" >= "b" and "c" is in "aca")
   "b" is printed, because "b" <= "b" and ("b" >= "b" and "b" is in "b")

therefore the second line is: a_ab

```

# Old version: ~~58~~ ~~57~~ 52 bytes

```
JwKNFHS{J=K.e?eS>_>JxJHx_JHqYH@KkJs.e?@zknYNdK=KXKHN

```

Try it online: Pyth Compiler/Executor

This creates a mask, which I'll modify before and after printing each line. For more information see the edit history.

# Answer
> 10 votes
# CJam, 48 bytes

```
ll:i:T.{___T#TW%@#~T<>+:e>)1$-@*123Se]m>}z_|(;N*

```

### Explanation

```
l                                                Code.
 l                                               Priority.
  :i                                             Convert priority to integer.
    :T                                           Save to T.
      .{                                }        For corresponding items:
      .{___                             }        Copy the current priority 3 times.
      .{   T#                           }        First position with this priority.
      .{     TW%                        }        Reverse T.
      .{        @#                      }        First (last) position with this priority.
      .{          ~T<                   }        Cut T at the end of this priority.
      .{             >                  }        Cut at the beginning of this priority.
      .{              +                 }        Insert the current priority to
                                                 prevent the array being empty.
      .{               :e>              }        Array maximum.
      .{                  )1$-          }        Count of integers between the current
                                                 priority and the maximum, inclusive.
      .{                      @*        }        That number of the current character.
      .{                        123Se]  }        Fill irrelevant priorities with spaces.
      .{                              m>}        Rotate the array to make non-spaces
                                                 starting at the current priority.
                                                 Returns a column containing 123 items.
                                         z       Zip to get the rows from columns.
                                          _|     Remove duplicate rows, including
                                                 unused priorities and all-space rows.
                                            (;   Remove the first row (an all-space row).
                                              N* Insert newlines.

```

# Answer
> 9 votes
# CJam, 82 bytes

Pretty long currently and I think I can shave off a few more bytes.

```
leel:F]z::+F$_&\f{{W=1$=},\;}{]_{0f=_W=),\0=>Lf&Ra#)},F,S*\:+{~;1$L+:L;t}%oNo~}%];

```

**Algorithm**

Basic algorithm is as following:

* `leel:F]z::+` : Group the code, the formatting and the index of each character together
* `F$_&\f{{W=1$=},\;}` : Group the above triplets into priority of printing using the formatting string. This code also makes sure that the priorities are sorted.
* `]_{0f=_W=),\0=>Lf&Ra#)},` : For each priority group of triplets, get the bounding index range and see if any index is not printed yet. If there is an unprinted index, include this priority group into the "to be printed in this step" group.
* `F,S*\:+{~;1$L+:L;t}%oNo~}%` : After getting all groups to be printed in this step, fill the code into the correct index of an empty space string and then print that string. Also update the array containing the list of printed indexes.

Code explanation to be followed when I am done golfing this.

**Example**

Here is the code run on the code itself:

Input:

```
leel:F]z::+F$_&\f{{W=1$=},\;}{]_{0f=_W=),\0=>Lf&Ra#)},F,S*\:+{~;1$L+:L;t}%oNo~}%];
aaabbbcccccdddddeefgghhiffggejkklmmmnoooopppqrrrssssllttttuuuvwwxxxxxxxyvvzzzzjjjj

```

Output:

```
lee
   l:F
      ]z::+
           F$_&\
                f{          }
                f{{     },  }
                f{{W=   },\;}
                f{{W=1$ },\;}
                f{{W=  =},\;}
                             {                                                }%];
                             {]_                                              }%];
                             {  {                   },                        }%];
                             {  {0f=                },                        }%];
                             {  {   _               },                        }%];
                             {  {    W=),           },                        }%];
                             {  {        \0=        },                        }%];
                             {  {           >       },                        }%];
                             {  {            Lf&    },                        }%];
                             {  {               Ra#)},                        }%];
                             {                        F,S*                    }%];
                             {                            \:+                 }%];
                             {                               {          }%    }%];
                             {                               {~;        }%    }%];
                             {                               {  1$L+:L; }%    }%];
                             {                               {         t}%    }%];
                             {                                            oNo~}%];

```

Try it online here

# Answer
> 7 votes
# IDL 8.4, ~~316~~ ~~318~~ 304 bytes

New version, still too long, but shorter! And, in the true spirit of IDL, completely vectorized, which means (since there's no for loop) that I can now do it as one line, and run it on itself, once I get my version completely upgraded to 8.4. That'll be edited in later.

One line version:

```
c=(f='')&read,c,f&l=[0:strlen(f)-1]&c=strmid(c,l,1)&s=strmid(f,l,1)&u=s.uniq()&k=value_locate(u,s)&n=[0:max(k)]&d=hash(n,u.map(lambda(x,y,z:max(z[(r=stregex(y,'('+x+'(.*))?'+x,len=w)):r+w-1])),f,k))&print,n.map(lambda(n,l,c,d,i:i.reduce(lambda(x,i,l,c,d,n:x+(d[l[i]]ge n?c[i]:' ')),l,c,d,n)),k,c,d,l)&end

```

With line breaks (same number of bytes, subbing \n vs &), and commented:

```
c=(f='') ;initialize code and format as strings
read,c,f ;read two lines of input from the prompt
l=[0:strlen(f)-1] ;index array for the strings
c=strmid(c,l,1) ;split the code string into an array, via substrings of length 1
s=strmid(f,l,1) ;same for the format string, saving f for regex later
u=s.uniq() ;get the sorted unique values in the format string (sorts A->a)
k=value_locate(u,s) ;assign layer values to the format characters
n=[0:max(k)] ;index array for the unique format characters
d=hash(n,u.map(lambda(x,y,z:max(z[(r=stregex(y,'('+x+'(.*))?'+x,len=w)):r+w-1])),f,k))
print,n.map(lambda(n,l,c,d,i:i.reduce(lambda(x,i,l,c,d,n:x+(d[l[i]]ge n?c[i]:' ')),l,c,d,n)),k,c,d,l)
end ;end the script

```

Here's an algorithmic breakdown for line 9:

```
r=stregex(y,'('+x+'(.*))?'+x,len=w) ; r, w = starting position & length of substring in y {format string} bracketed by x {character} (inclusive)
z[(r=...):r+w-1] ; grab a slice of z {layer array} from r to r+w-1 -> layer values for each character in the substring
max(z[...]) ; max layer (depth) of any characters in that slice
u.map(lambda(x,y,z:max(...)),f,k) ;map an inline function of the above to every element of the unique-formatting-character array
d=hash(n,u.map(...)) ; create a hash using the unique indices, the result is a hash of (character:max_substring_depth)

```

...and 10:

```
x+(d[l[i]]ge n?c[i]:' ')) ; ternary concatenation: if maxdepth for this character >= current depth, add the character, otherwise add ' '
i.reduce(lambda(x,i,c,d,l,n:...)),,l,c,d,n) ;accumulate elements of i {code/format index array} by passing them through the inline ternary concatenation function
print,n.map(lambda(n,l,c,d,i:i.reduce(...)),k,c,d,l) ;map the depth index through the reduction, ending up with a string for each depth layer, then print it

```

Lines 9 and 10 do the real work, the rest of it sets up the variables you need for the end. I think this is about as golfed as it's going to get, I can't find anywhere else to do it better.

## Old version (everything below here is out of date):

This is nowhere near short enough to win, because this is a terrible golfing language, but no one ever answers in IDL so I'm just gonna go for it.

```
a=(b='')
read,a,b
c=[0:strlen(b)-1]
d=strmid(b,c,1)
a=strmid(a,c,1)
e=d[uniq(d,sort(d))]
f=list(value_locate(e,d),/e)
s=hash()
for i=0,max(f)do begin
g=stregex(b,'('+e[i]+'(.*))?'+e[i],l=l)
s[i]=max(f[g:g+l-1])
print,f.reduce(lambda(x,y,z:x+(s.haskey(y)?z[y]:' '),s,a)
s=s.filter(lambda(x,y:x[1]gt y),i)
endfor
end

```

I'm not sure if there's any way I can cut it down more... I could call strmid on both a and b at the same time, but then I spend more bytes indexing d and it works out the same. I'll keep working on it, though! (And tomorrow I'll edit in an explanation of the algorithm.)

---
Tags: code-golf, whitespace, balanced-string
---


title: Hodorize a String

text:
# Question
Title: Hodorize a String
Hodor is a slow-minded but endearing character on the show Game of Thrones (he's in the books as well of course). The only word he ever says is 'hodor'.

Surprisingly, despite not having much of a vocabulary, Hodor always speaks in complete sentences with correct capitalization and punctuation, and does in fact convey meaning.

Hodor is capable of expressing all 128 ASCII characters, though it takes him an entire sentence to say each one. Each character has a single, exact representation as a sentence. An ASCII string is *Hodorized* by translating all the characters in the string to their Hodor sentence equivalents, then joining all the sentences. Since all characters map to exact sentences, all ASCII strings have a single, unique Hodorized representation.

### Hodorizing Characters

Hodor divides his 128 expressible characters into 4 sets of 32 by using 4 different types of punctuation for the sentences that represent characters.

The sentence ends with...

* `.` if the ASCII character code mod 4 is 0.
* `.[newline][newline]` (for a new paragraph) if the code mod 4 is 1.
* `?` if the code mod 4 is 2.
* `!` if the code mod 4 is 3.

For example, the ASCII character code for `b` is 98, and 98 mod 4 is 2, so Hodor's sentence for `b` is sure to end in `?`.

The content of the sentence is one of 32 distinct strings only containing the word 'hodor'. Each of the 32 characters of a particular punctuation type map to a different sentence content string. So with 32 sentence content strings and 4 punctuation types, all 128 ASCII character can be represented as distinct Hodor sentences.

To determine the sentence content for a character with ASCII code C, compute `(floor(C / 4) + 16) mod 32`; everything after the colon on that line in this list is the sentence content:

```
0:Hodor
1:HODOR
2:Hodor hodor
3:Hodor, hodor
4:Hodor hodor hodor
5:Hodor, hodor hodor
6:Hodor hodor hodor hodor
7:Hodor hodor, hodor hodor
8:Hodor hodor hodor hodor hodor
9:Hodor hodor, hodor hodor hodor
10:Hodor hodor hodor hodor hodor hodor
11:Hodor hodor hodor, hodor hodor hodor
12:Hodor hodor hodor hodor hodor hodor hodor
13:Hodor hodor hodor, hodor hodor hodor hodor
14:Hodor hodor hodor hodor hodor hodor hodor hodor
15:Hodor hodor hodor hodor, hodor hodor hodor hodor
16:Hodor hodor hodor hodor hodor hodor hodor hodor hodor
17:Hodor hodor hodor hodor, hodor hodor hodor hodor hodor
18:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor
19:Hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor
20:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor
21:Hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor
22:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor
23:Hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor
24:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor
25:Hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor
26:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor
27:Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor
28:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor
29:Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor
30:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor
31:Hodor hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor

```

It can be seen that, apart from the `HODOR` special case, these strings are generated by joining more and more `hodor`'s, and every other string has a comma halfway between all the words (with the "larger half" right of the comma for an odd number of words).

Joining sentence content with punctuation, we can form the Hodor sentences for all 128 characters (the number on the left is the character code):

```
0:Hodor hodor hodor hodor hodor hodor hodor hodor hodor.
1:Hodor hodor hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
2:Hodor hodor hodor hodor hodor hodor hodor hodor hodor?
3:Hodor hodor hodor hodor hodor hodor hodor hodor hodor!
4:Hodor hodor hodor hodor, hodor hodor hodor hodor hodor.
5:Hodor hodor hodor hodor, hodor hodor hodor hodor hodor.[newline][newline]
6:Hodor hodor hodor hodor, hodor hodor hodor hodor hodor?
7:Hodor hodor hodor hodor, hodor hodor hodor hodor hodor!
8:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.
9:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
10:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor?
11:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor!
12:Hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor.
13:Hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor.[newline][newline]
14:Hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor?
15:Hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor!
16:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.
17:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
18:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor?
19:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor!
20:Hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor.
21:Hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor.[newline][newline]
22:Hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor?
23:Hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor!
24:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.
25:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
26:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor?
27:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor!
28:Hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor.
29:Hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor.[newline][newline]
30:Hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor?
31:Hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor!
32:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.
33:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
34:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor?
35:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor!
36:Hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor.
37:Hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
38:Hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor?
39:Hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor!
40:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.
41:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
42:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor?
43:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor!
44:Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor.
45:Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
46:Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor?
47:Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor!
48:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.
49:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
50:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor?
51:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor!
52:Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor.
53:Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
54:Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor?
55:Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor!
56:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.
57:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
58:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor?
59:Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor!
60:Hodor hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor.
61:Hodor hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
62:Hodor hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor?
63:Hodor hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor!
64:Hodor.
65:Hodor.[newline][newline]
66:Hodor?
67:Hodor!
68:HODOR.
69:HODOR.[newline][newline]
70:HODOR?
71:HODOR!
72:Hodor hodor.
73:Hodor hodor.[newline][newline]
74:Hodor hodor?
75:Hodor hodor!
76:Hodor, hodor.
77:Hodor, hodor.[newline][newline]
78:Hodor, hodor?
79:Hodor, hodor!
80:Hodor hodor hodor.
81:Hodor hodor hodor.[newline][newline]
82:Hodor hodor hodor?
83:Hodor hodor hodor!
84:Hodor, hodor hodor.
85:Hodor, hodor hodor.[newline][newline]
86:Hodor, hodor hodor?
87:Hodor, hodor hodor!
88:Hodor hodor hodor hodor.
89:Hodor hodor hodor hodor.[newline][newline]
90:Hodor hodor hodor hodor?
91:Hodor hodor hodor hodor!
92:Hodor hodor, hodor hodor.
93:Hodor hodor, hodor hodor.[newline][newline]
94:Hodor hodor, hodor hodor?
95:Hodor hodor, hodor hodor!
96:Hodor hodor hodor hodor hodor.
97:Hodor hodor hodor hodor hodor.[newline][newline]
98:Hodor hodor hodor hodor hodor?
99:Hodor hodor hodor hodor hodor!
100:Hodor hodor, hodor hodor hodor.
101:Hodor hodor, hodor hodor hodor.[newline][newline]
102:Hodor hodor, hodor hodor hodor?
103:Hodor hodor, hodor hodor hodor!
104:Hodor hodor hodor hodor hodor hodor.
105:Hodor hodor hodor hodor hodor hodor.[newline][newline]
106:Hodor hodor hodor hodor hodor hodor?
107:Hodor hodor hodor hodor hodor hodor!
108:Hodor hodor hodor, hodor hodor hodor.
109:Hodor hodor hodor, hodor hodor hodor.[newline][newline]
110:Hodor hodor hodor, hodor hodor hodor?
111:Hodor hodor hodor, hodor hodor hodor!
112:Hodor hodor hodor hodor hodor hodor hodor.
113:Hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
114:Hodor hodor hodor hodor hodor hodor hodor?
115:Hodor hodor hodor hodor hodor hodor hodor!
116:Hodor hodor hodor, hodor hodor hodor hodor.
117:Hodor hodor hodor, hodor hodor hodor hodor.[newline][newline]
118:Hodor hodor hodor, hodor hodor hodor hodor?
119:Hodor hodor hodor, hodor hodor hodor hodor!
120:Hodor hodor hodor hodor hodor hodor hodor hodor.
121:Hodor hodor hodor hodor hodor hodor hodor hodor.[newline][newline]
122:Hodor hodor hodor hodor hodor hodor hodor hodor?
123:Hodor hodor hodor hodor hodor hodor hodor hodor!
124:Hodor hodor hodor hodor, hodor hodor hodor hodor.
125:Hodor hodor hodor hodor, hodor hodor hodor hodor.[newline][newline]
126:Hodor hodor hodor hodor, hodor hodor hodor hodor?
127:Hodor hodor hodor hodor, hodor hodor hodor hodor!

```

(`[newline]`'s are to be replaced with actual newlines.)

### Hodorizing Strings

Hodorizing a string really just involves concatenating all the character sentences of the string's characters together. There are only a couple caveats:

* A space is inserted after every sentence except for the `.[newline][newline]` punctuated ones and the very last sentence.
* If the last sentence is punctuated with `.[newline][newline]`, the punctuation becomes `...` so there is no trailing whitespace.

### Examples

The string `F0` is Hodorized as

```
HODOR? Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor.

```
* `F` has ASCII code 70. 70 mod 4 is 2, so the first sentence ends in `?`. `(floor(70 / 4) + 16) mod 32` is 1 so the content is `HODOR`.
* `0` has ASCII code 48. 48 mod 4 is 0, so the second sentence ends in `.`. `(floor(48 / 4) + 16) mod 32` is 28 so the content is 15 `hodor`'s strung together with no comma.
* Notice that there is no trailing space.

The string `CEE` is Hodorized as

```
Hodor! HODOR.

HODOR...

```
* Notice that there is no space before the last sentence.
* Notice that the the last sentence punctuation was changed to `...`.

The string

```
Hodor's real name is Walder.
Did you know?

```

is Hodorized as

```
Hodor hodor. Hodor hodor hodor, hodor hodor hodor! Hodor hodor, hodor hodor hodor. Hodor hodor hodor, hodor hodor hodor! Hodor hodor hodor hodor hodor hodor hodor? Hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor! Hodor hodor hodor hodor hodor hodor hodor! Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor. Hodor hodor hodor hodor hodor hodor hodor? Hodor hodor, hodor hodor hodor.

Hodor hodor hodor hodor hodor.

Hodor hodor hodor, hodor hodor hodor. Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor. Hodor hodor hodor, hodor hodor hodor? Hodor hodor hodor hodor hodor.

Hodor hodor hodor, hodor hodor hodor.

Hodor hodor, hodor hodor hodor.

Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor. Hodor hodor hodor hodor hodor hodor.

Hodor hodor hodor hodor hodor hodor hodor! Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor. Hodor, hodor hodor! Hodor hodor hodor hodor hodor.

Hodor hodor hodor, hodor hodor hodor. Hodor hodor, hodor hodor hodor. Hodor hodor, hodor hodor hodor.

Hodor hodor hodor hodor hodor hodor hodor? Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor? Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor? HODOR. Hodor hodor hodor hodor hodor hodor.

Hodor hodor, hodor hodor hodor. Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor. Hodor hodor hodor hodor hodor hodor hodor hodor.

Hodor hodor hodor, hodor hodor hodor! Hodor hodor hodor, hodor hodor hodor hodor.

Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor. Hodor hodor hodor hodor hodor hodor! Hodor hodor hodor, hodor hodor hodor? Hodor hodor hodor, hodor hodor hodor! Hodor hodor hodor, hodor hodor hodor hodor! Hodor hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor!

```

(assuming the newline is a single `\n`)

# Challenge

Write a program or function that takes in an ASCII string and Hodorizes it, printing or returning the resulting string. Take input in any standard way (from text file, command line, stdin, function arg).

**The solution with the fewest bytes wins. Tiebreaker is earlier post.** (Handy byte counter.)

# Answer
> 26 votes
### Hodor! Hodor hodor? Hodor hodor hodor hodor hodor.

### Hodor hodor hodor, hodor hodor hodor.

### Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor. Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor. Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor. Hodor hodor hodor hodor hodor hodor hodor, hodor hodor hodor hodor hodor hodor hodor hodor.

### Hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor hodor. Hodor hodor hodor hodor hodor? Hodor hodor hodor hodor hodor hodor hodor hodor.

### Hodor hodor hodor, hodor hodor hodor hodor. Hodor hodor, hodor hodor hodor.

### Hodor hodor hodor hodor hodor hodor hodor!

That's just the language and size header!? Nevermind then, let's just encode the post in boring old ASCII. Sorry if you have trouble understanding the post, Hodor.

---

# CJam, 85 bytes

Here's my attempt. Some parts of this code felt rather clunky when I wrote them, so there's likely potential to beat this!

```
qW%{'@^4md('.X1$N?_++a"?!."XLS?f++=\(_)2md","*1$)"hodor":Ha*H@+@(2/\tS*0:X'HtHeu?}%W%

```

Try it online.

### Explanation

```
qW%             "Read and reverse the input.";
{               "Map each character c:";
  '@^4md          "Calculate (c^64)/4, which is the sentence content determiner,
                    and c%4, which is the sentence ending determiner.";
  (               "Calculate c%4-1 for later.";
  '.X1$N?_++      "Produce the sentence ending string for the case that c%4==1,
                   which is '.' followed by two copies of:
                    - '.' if this is the first processed (last actual) character
                    - or a newline otherwise.
  a"?!."XLS?f     "Produce a list of the sentence ending strings for the cases
                   that c%4 is 2, 3, or 0, which are:
                    - '?', '!', and '.' if this is the first processed character
                    - or these punctuation marks each followed by a space
                      otherwise.";
  ++=\            "Prepend the sentence ending string for the case that c%4==1
                   to the list for the other cases and select the element at the
                   index (c%4-1)%4 as the correct sentence ending string.";
  (               "Calculate (c^64)/4-1 for later.";
  _)2md           "Calculate the quotient and remainder of the sentence content
                   content determiner divided by 2.";
  ","*            "Produce a string of commas with a length of the remainder
                   calculated above (either 0 or 1).";
  1$)"hodor":Ha*  "Produce a list of copies of 'hodor' with a length of the
                   quotient calculated above plus one.";
  H@+@(2/\t       "Append the string of commas (either empty or one comma) to
                   the middle 'hodor'.";
  S*              "Join the sentence words into a string a space between each.";
  0:X             "Signal that later characters are not the first processed.";
  'Ht             "Capitalize the first letter of the sentence (always 'h').";
  Heu             "Produce the string 'HODOR'.";
  ?               "Select the correct sentence content, which is 'HODOR' if
                   (c^64)/4-1 is zero or the full sentence produced before that
                   otherwise.";
}%
W%              "Reverse the reversed translation to obtain the forward one.";
                "Implicitly print the result.";

```

# Answer
> 106 votes
# Hodor, ~~602~~ 582 bytes

```
HoDoRHoDoR HODOR! (Hodor ){r='';Hodor!? =Hodor .Hodor!? hodor? HODOR? hodor! hodor. h;HODOR{}(Hodor? =0;Hodor? <Hodor!? ;++Hodor? ){hodor =Hodor .hodor hHODOR rHodor... odhodor? hodor?!? hodor. (Hodor? );HODOR? =(0|hodor /4+16)%32;r+='H';HODOR =HHHOOODDDDOOORRR!!! hodor?!? rrHODOR HODOR!?! (0|HODOR? /2+2);HOdor!!!(HODOR? %2)HODOR [0|(HODOR? +1)/4]=',';r+=HODOR? ==1?'ODOR':HODOR .HODOR?! oHodor? HODOR? (' hodor').Hodor Hodor!? Hodor? hodor hodor? (2);r+=['. ',Hodor? ==Hodor!? -1?'....':'.\HODOR? \HODOR? ','? ','! '][hodor %4]}HODOR:: r.Hodor Hodor!? Hodor? hodor hodor? (0,-1)}

```

Here is an ungolfed version... you know... for readability:

```
HoDoRHoDoR HODOR! (Hodor ){
    r='';
    Hodor!? =Hodor .Hodor!? hodor? HODOR? hodor! hodor. h;
    HODOR{}(Hodor? =0;Hodor? <Hodor!? ;++Hodor? ){
        hodor =Hodor .hodor hHODOR rHodor... odhodor? hodor?!? hodor. (Hodor? );
        HODOR? =(0|hodor /4+16)%32;
        r+='H';
        HODOR =HHHOOODDDDOOORRR!!! hodor?!? rrHODOR HODOR!?! (0|HODOR? /2+2);
        HOdor!!!(HODOR? %2)HODOR [0|(HODOR? +1)/4]=',';
        r+=HODOR? ==1?'ODOR':HODOR .HODOR?! oHodor? HODOR? (' hodor').Hodor Hodor!? Hodor? hodor hodor? (2);
        r+=['. ',Hodor? ==Hodor!? -1?'....':'.\HODOR? \HODOR? ','? ','! '][hodor %4]
    }
    HODOR:: r.Hodor Hodor!? Hodor? hodor hodor? (0,-1)
}

```

Yep, there is a language called Hodor. (And it's rather new.) It's essentially just a string substitution for JavaScript. The corresponding JS looks like this:

```
function f(s){
  r='';
  l=s.length;
  for(i=0;i<l;++i){
    c=s.charCodeAt(i);
    n=(0|c/4+16)%32;
    r+='H';
    a=new Array(0|n/2+2);
    if(n%2)a[0|(n+1)/4]=',';
    r+=n==1?'ODOR':a.join(' hodor').slice(2);
    r+=['. ',i==l-1?'....':'.\n\n','? ','! '][c%4]
  }
  return r.slice(0,-1)
}

```

Hence, my submission is a function taking a string and returning the Hodorised equivalent.

Unfortunately, there doesn't seem to be any information about how Hodor actually works (apart from the source code of the interpreter), but it comes with a JS2HD translation script.

Note that Hodor's substitutions are also applied within string literals. So while you may just call the above function as

```
HODOR! ("CEE")

```

You can also use the following:

```
HODOR! ("Hodor... HooodorrHodor HooodorrHodor ")

```

where `Hodor... HooodorrHodor HooodorrHodor` will be substituted with `CEE`. Note that this means, that if your string itself contains certain forms of `Hodor` you'll *have* to encode it, or else it will be substituted. E.g. `"Hodor. "` is actually `"m"` in JavaScript. The catch is that the letters `[dhor]` (case insensitively) are not replaced at all, so you can't even encode this. One solution is to split up the literal, like `"Hod"+"or. "`, such that the substitution step doesn't find anything to decode.

# Answer
> 5 votes
# Python 2, ~~219~~ 198 bytes

Try it here

Uses the same method as Martin's JavaScript, and it's several bytes shorter in Python. I make use of Python 2.7's handy integer division. Thanks to Sp3000 for some golfing.

```
def f(s,r='',i=2):
    for j in s:c=ord(j);n=(c/4+16)%32;a=['']*(n/2+2);a[-~n/4]=','[:n%2];r+='H'+[' hodor'.join(a)[2:],'ODOR'][n==1]+['. ',['.\n\n',4*'.'][i>len(s)],'? ','! '][c%4];i+=1
    return r[:-1]

```

And for your own entertainment and my own enjoyment and curiosity...

Here it is as a **lambda function**!!!

### Python 2, 349

Try it here, along with an older version of the program above.

```
f=lambda s:'H'.join(['']+[('ODOR'if(ord(s[i])/4+16)%32==1 else' hodor'.join((['']*(((ord(s[i])/4+16)%32)/2+2))[:((ord(s[i])/4+16)%32+1)/4]+([',']if ord(s[i])/4%2 else[''])+(['']*(((ord(s[i])/4+16)%32)/2+2))[((ord(s[i])/4+16)%32+1)/4+1*(ord(s[i])/4%2<1):])[2:])+['. ',4*'.'if i+2>len(s)else'.\n\n','? ','! '][ord(s[i])%4]for i in range(len(s))])[:-1]

```

Creating this involved deeper and deeper substitutions as well as some extra creativity.

* Every `j` is replaced with `s[i]`.
* Every `c` is replaced with `ord(s[i])`.
* Every `n` is replaced with `(ord(s[i])/4+16)%32`.

+ *Except* where I only need `n%2`, so I use `(ord(s[i])/4%2` instead.
* Finally, `a` is replaced with `(['']*(((ord(s[i])/4+16)%32)/2+2))[:((ord(s[i])/4+16)%32+1)/4]+([',']if ord(s[i])/4%2 else[''])+(['']*(((ord(s[i])/4+16)%32)/2+2))[((ord(s[i])/4+16)%32+1)/4+1*(ord(s[i])/4%2<1):]`.

+ This is because we cannot assign a value, so we must split the list in half, conditionally append the comma, then append the last half again.

# Answer
> 4 votes
## MUMPS, 284 236 bytes

New version: After looking at it for a while I came up with a shorter version (236 bytes):

```
H(H) S L=$L(H) F O=1:1:L D
 .S D=$A($E(H,O)),R=D#4,P=$S('R:".",R=2:"?",R=3:"!",O=L:"...",1:"."_$C(10,10)),E=D\4+16#32,(S,Q)="hodor" F F=1:1:E\2 S Q=S_$S(E#2&(F=(E\4+1)):", ",1:" ")_Q,$E(Q)="H" S:E=1 Q="HODOR"
 .W Q_P_$S(L=O:"",1:" ")
 Q

```

First version:

```
H(H) S L=$L(H) F O=1:1:L D
 .S S=$C(10),D=$A($E(H,O)),R=D#4,P=$S('R:".",R=2:"?",R=3:"!",O=L:"...",1:"."_S_S),E=D\4+16#32,(S,Q)="hodor ",G=6*(E+1\4) F F=1:1:E\2 S Q=S_Q
 .S Q=$E(Q,1,$L(Q)-1) S:E=1 Q="HODOR" S:E#2&(E>2) Q=$E(Q,1,G-1)_","_$E(Q,G,99) S $E(Q)="H" W Q_P_$S(L=O:"",1:" ")
 Q

```

Damn you, CJam! *Maybe* I could save some bytes using ObjectScript (there're list operators), but I doubt it.

Here's a somewhat verbose version:

```
VH(H)
 F I=1:1:$L(H) D              ; iterate over input string H
 .S O=$E(H,I)                 ; O is a single char
 .S D=$A(O)                   ; ascii code (dec)
 .S R=D#4                     ; #: mod, $S: $SELECT(condition:result,cond...)
 .S P=$S(R=0:".",R=2:"?",R=3:"!",I=$L(H):"...",1:"."_$C(10)_$C(10))
 .S E=D\4+16#32               ; \: integer division
 .S (S,Q)="hodor "            ; hodor
 .F J=1:1:E\2 S Q=S_Q         ; build hodor -"list"
 .I E=1 S Q="HODOR"           ; HODOR
 .I E'=1 S Q=$E(Q,1,$L(Q)-1)  ; remove trailing _
 .;                           ; insert ,
 .I E#2,E>2 S Q=$E(Q,1,6*(E+1\4)-1)_","_$E(Q,6*(E+1\4),99)
 .S $E(Q)="H"                 ; ^h->^H
 .W Q_P_$S($L(H)=I:"",1:" ")  ; Write and remove trailing _
 Q

```

# Answer
> 1 votes
# C# 378 Bytes

```
string x(string h){string[]f={". ",".\n\n","? ","! "};string[]a=new string[32];string s="";int i,j,c=0;for(i=0;i<32;i++){a[i]="hodor";if(i==1)a[i]=a[i].ToUpper();else{for(j=0;j<i/2;j++){if(i%2==1&&j==c/2)a[i]+=",";a[i]+=" hodor";}if(i%2==1)c++;a[i]=char.ToUpper(a[i][0])+a[i].Substring(1);}}foreach(char b in h){s+=a[(int)(Math.Floor((double)b/4)+16)%32]+f[(int)b%4];}return s;}

```

It's my first time golfing, so bare with me.

# Answer
> 0 votes
## C++, ~~547~~ 452 bytes

```
void H(string s){string e[4]={".",".\n\n","?","!"};string r;char c,m;int n=s.size();for(int i=0;i<n;i++){r.clear();c=s.at(i);m=c%4;r.append(A(c));r.append(e[m]);if(i==n-1){int k=r.size();r.pop_back();if(m==1){r.pop_back();r.append("..");}}cout<<r.c_str();}}string A(char x){string h("Hodor");int c=((int )floor(x/4)+16)%32;int n=c;bool o=(c%2==1);if(n==1)h="HODOR";else{while(n>1){h.append("hodor");if(o&&n==(int )(c/2)){h.append(",");}n--;}}return h;}

```

Ungolfed:

```
#include <iostream>
#include <math.h>
using namespace std;
void Hodorise(string s);
string FromAscii(char c);

void Hodorise(string s)
{
string end[4] = {". ",".\n\n","? ","! "};
string res;
char c, m;
int n = s.size();
for (int i = 0; i < n; i++)
{
res.clear();
c = s.at(i);
m = c % 4;
res.append(FromAscii(c));
res.append(end[m]);
if (i == n - 1)
{
int k = res.size();
res.pop_back();
if (m == 1)
{
res.pop_back();
res.append("..");
}

}
cout << res.c_str();
}
}

string FromAscii(char c)
{
string hodor("Hodor");
int code = ((int)floor(c / 4) + 16) % 32;
int n = code;
bool odd = (code % 2 == 1);
if (n == 1)hodor = "HODOR";
else
{
while (n > 1)
{
hodor.append(" hodor");
if (odd && n==(int)(code/2))
{
hodor.append(",");
}
n--;
}
}
return hodor;
}
#define N 3
int main()
{
string x[N] = { "F0", "CEE", "Hodor's real name is Walder.\nDid you know ?" };
for (size_t i = 0; i < N; i++)
{
cout << endl << x[i].c_str() << ":\n";
Hodorise(x[i]);
}

char c;
cin >> c;
return 0;
}

```

---
Tags: code-golf, string
---


title: Tips for golfing in Element

text:
# Question
Title: Tips for golfing in Element
Since my use of Element has increased recently, I am interested in tips for golfing programs written in it.

What general tips do you have for golfing in Element? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Element.

Please post one tip per answer.

# Answer
> 2 votes
# Ways to put extra 0s on the stack

A lot of times, you will be faced with the following 4-character piece of code:

```
0 2@

```

Element's stack-item-movement operator @ is very general-purpose, sometimes *too much* so for golfing, since it always takes two arguments, which may need to be separated by a space. So, it can take several characters to perform a single movement.

Usually, there is a better way to do this.

You can often produce empty values from the hash. The code `2:0 2@` can almost always be shortened to `3:~2@` to save one character because chances are that nothing is stored in the hash for that particular key.

If the top thing on the stack is the input, you can sacrifice the newline at the end of it like so:

```
_0 2@
_)2@

```

In a limited number of cases, usually with `0 1@`, you don't need the `@` at all. This works with input or when putting a constant on the stack.

```
_0 1@
'_"

text 0 1@
'text"

```

# Answer
> 1 votes
## Performing logic operations on a list of numbers.

Let's say you had a simple task: Take a list of 5 numbers and verify that all of them are multiples of 7. (You can replace "multiple of 7" with any other test.) You will soon run into a problem: in order to perform a loop, you must put a value on the control stack, but this this can interfere with the logic that you are performing on the list of numbers.

The following solution does not work because the value `5` is accidentally included as one of the arguments in the chain of ORs.

```
5'[_7%?|]!"`  #does not work

```

There are a few ways to overcome this.

```
5'0[_7%+]?!"` #self-contained
5'[_7%+]?!"`  #if main stack is empty
5'[_7%?!&]"`  #main stack untouched, but consumes the 5

```

If the numbers you need to compare are already on the stack, then the above approach will not work.

```
2 3 7 4 8 5'[7%?|]!"`  #does not work
2 3 7 4 8 5'[!7%?|!]"` #works
2 3 7 4 8 5'[7%?!&]"`  #shorter, notice the | -> &
5'2 3 7 4 8[7%?!&]"`   #can save a space in some cases

```

# Answer
> 0 votes
# Using the hash as an array

Element does not have native support for arrays, but the hash can be used as a makeshift array for simple operations. This is done by using numbers as keys. The following code initializes an array \[7,32,12,8,3\]

```
7 0;32 1;12 2;8 3;3 4;

```

For a much larger array, this is a more compact way to go:

```
7 32 12 8 3 13 5 1 0 67 12 54 11 13'["1-+2:';]

```

As you can tell, using the hash to hard-code an array is a measure of last resort. They work nicer when the array is created in a less hard-coded fashion. Here is code that can take as input an array size and a list of values and put it in an array.

```
_'0[2:_)1@;1+]

```

Retrieving a value is easy though and can be where this convoluted scheme pays off. If `i` contains the index you want to retrieve, then the code is simple:

```
i~~

```

To give an array a name, you can append a single letter to the index when storing and retrieving.

# Answer
> 0 votes
# "Factoring Out" things from If-Else constructions

If you ever have the code

```
?[...]![..]

```

Then you probably have an If-Else construction. You really want to minimize the amount of duplicate code you put in these things. Generally speaking, if V W X Y Z are blocks of code, then the following compression should be tried:

```
?[WXVZ]![WVYZ]
?W[X]V![Y]Z

```

This usually works even if V/W/Z is a `~`;` type of operator, but probably does not work if V/W/Z is `"`.

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


# Question
Title: Print the prime factorization of the greatest common divisor of two numbers
Title says it all. Two input 32-bit positive integers `m, n >= 2`, output `gcd(m,n)` in prime factorization form.

## Input

Command line args or 1 line of stdin okay, whatever's better for golf.

## Output

Single space delimited with exponents (no additional spaces). Output nothing if the inputs are relatively prime.

Examples:

```
$ ./factorize 96 162
2^1 3^1

$ ./factorize 14 15

$ ./factorize 196 294
2^1 7^2

```

## Rules

* You may not use external resources, math libraries or built-in functions for factorization or GCD. Examples: Java, no `java.lang.Math`. ruby, no `prime_division`, perl, no `factor`, etc.

# Answer
> 10 votes
# Python 3, ~~255~~ ~~250~~  ~~237~~ ~~226~~ ~~188~~ ~~180~~ ~~150~~ ~~142~~ ~~137~~ 136 chars

```
a,b=map(int,input().split())
t,g='',1
while g<a:
 g,p=g+1,0
 if a%g+b%g<1:
  while a%g+b%g<1:a/=g;b/=g;p+=1
  t+='%d^%d '%(g,p)
print(t)

```

It's amazing how much I could shorten this by just skipping stuff (like, you know, finding the gcd)! Also I could reduce 10 more chars by making this a function that expects 2 ints, like some other answers, instead of reading from stdin.

# Answer
> 8 votes
# Ruby - ~~168~~ ~~117~~ ~~114~~ ~~101~~ ~~100~~ 97

Edit: After thinking about it, realized I didn't need the sieve since the primality of the factor is taken care of in the factorization loop. Also, as informed by answers of others (laindir's and Tal's are the ones I had seen it in, though it looks like others have also done it), removed separate gcd calculation, since that also occurs in the factorization.
Edit 2: Don't need `do`.
Edit 3: Squeezing it down more.
Edit 4: Pulled out one more space.
Edit 5: `upto` instead of `each`; `?^ == "^"`!

```
a,b=ARGV.map{|i|i.to_i}
2.upto(a){|d|c=0
[c+=1,a/=d,b/=d]while a%d+b%d<1
print d,?^,c," "if c>0}

```

Output (same after edit):

```
$ ruby factorize.rb 96 162
2^1 3^1
$ ruby factorize.rb 14 15

$ ruby factorize.rb 196 294
2^1 7^2

```

Certainly could be made better, but not bad for my first one.

# Answer
> 6 votes
# Python 2 - ~~254~~ ~~252~~ ~~196~~ ~~185~~ ~~156~~ ~~151~~ ~~134~~ ~~126~~ 121

```
i=1
a,b=map(int,raw_input().split())
while b:a,b=b,a%b
while~-a:
 i+=1;j=0
 while a%i<1:j+=1;a/=i
 if j:print`i`+'^'+`j`,

```

**Interpreter**

repl.it

**Example Input - stdin**

> 100 50

**Example Output - stdout**

> 2^1 5^2

# Answer
> 4 votes
# Java - ~~184~~ 175

This is inspired by @Geobits (and a little of @Tal's answer) answer, but enough of it is different that I decided to create my own answer.

```
class G{public static void main(String[]a){for(Integer i=1,q,n=i.valueOf(a[0]),m=i.valueOf(a[1]);m>=++i;System.out.print(q>0?i+"^"+q+" ":""))for(q=0;n%i+m%i<1;n/=i,m/=i)q++;}}

```

Ungolfed (sort of) with (human verification) test harness:

```
class G {
    public static void mainMethod(String[] a) {
        for (Integer i = 1, q, n = i.valueOf(a[0]), m = i.valueOf(a[1]); m >= ++i;
                 System.out.print(q > 0 ? i + "^" + q + " " : ""))
            for (q = 0; n % i + m % i < 1; n /= i, m /= i)
                q++;
    }

    public static void main(String[] a) {
        m(3, 3);
        m(196, 294);
        m(294, 196);
        m(14, 15);
        m(15, 14);
        m(96, 162);
        m(162, 96);
        m(300, 400);
        m(400, 300);
        m(100, 100);
        m(7, 7);
        m(4, 8);
    }

    public static void m(int one, int two) {
        mainMethod(new String[] { String.valueOf(one), String.valueOf(two) });
        System.out.println();
    }
}

```

# Answer
> 4 votes
# dc, 96 bytes

```
?sbsa2sf[q]sk[lalf~lblf~szrlz+0<ksbsale1+selsx]ss[lfn[^]Plen[ ]P]sp[0selsxle0<plf1+dsflb!<w]dswx

```

It reads one line of standard input. Its output does not end with a newline. (EDIT: It does also output an extra space after every factorization. Some of the other answers trim the space, but this one doesn't.)

Example:

```
$ echo 301343045 421880263 | dc factorize.dc
1021^1 59029^1 $

```

Code with comments:

```
# dc(1) is a stack language, like Forth. Programs push values on the
# stack, then operate on them. For example, to calculate
#  (2 + 3) * (9 - 4)
# the dc code is
#  [2 3 + 9 4 - *]

# [?] reads a line of input.  We expect two integers >= 2.
# [sb sa] stores the integers in variables.
? sb sa     # a, b = two integers from input

# This program sucks common factors from a and b, looping for
# f = 2, 3, 4, 5, and so on.  This method only sucks prime factors,
# but wastes time when f is not prime.
2 sf        # f = 2

# Code in [...] does not run until the program calls it.

# k = code to break a loop
[
 q           # [q] breaks two levels of [...]
] sk        # k = break

# s = loop to suck factor f from a and b
#  This loop increments e, the exponent for factor f.
#  Please set e = 0 before entering this loop.
[
 # [la lf] puts ( a f ) on the stack.
 # [~] does division and remainder.
             # STACK:
 la lf ~     # ( a/f a%f )
 lb lf ~     # ( a/f a%f b/f b%f )

 # [r] swaps the top two stack values.
 # Hold z = b%f and swap a%f with b/f.
             # STACK:
 sz r lz     # ( a/f b/f a%f b%f )

 # f is a common factor if a%f and b%f are zero.  Because a and b are
 # non-negative, a%f and b%f are zero only if a%f+b%f is zero.
             # STACK:
 +           # ( a/f b/f a%f+b%f )

 # Call k to break loop unless a%f+b%f is zero.  [<k] conditionally
 # calls k if the comparison is true.  Comparisons in dc are
 # backwards, so [3 0 <k] would check 0 < 3.  Because a%f+b%f is never
 # negative, [0 <k] is golf for [0 !=k].
             # STACK:
 0 <k        # ( a/f b/f )

 # f is a common factor, so suck it!
 sb sa       # a = a/f, b = b/f, STACK: ( )
 le 1 + se   # increment e, the exponent for this factor
 ls x        # continue loop, [x] executes s
] ss        # s = loop

# p = code to print "f^e "
[
 # [n] prints a number without a newline.
 # [P] prints a string.
 lf n [^]P
 le n [ ]P

 # DEBUG: Uncomment to print a and b.
 #[(a = ]P la n [, b = ]P lb n [)]P 10P
] sp        # p = print

# w = loop to iterate factors
[
 # Call s loop to suck factor f from a and b, and set exponent e.
 0 se        # e = 0
 ls x        # call s loop

 # DEBUG: Uncomment [c] to clear the stack.  Loop s leaves two junk
 # values ( a/f b/f ) on the stack.  Deleting [c] for code golf saves
 # 1 byte but leaks junk on the stack.
 #c

 # Print "f^e " if 0 < e.  Comparisons in dc are backwards, so
 # [0 le <p] would check e < 0, [le 0 <p] checks 0 < e.
 le 0 <p

 # Increment f.  [d] duplicates top value on stack.
             # STACK:
 lf 1 +      # ( f+1 )
 d           # ( f+1 f+1 )
 sf          # ( f ) as f+1 becomes f

 # Continue loop if b >= f.  This is golf for f <= a and f <= b, as
 # extra iterations of the loop cause no harm.
             # STACK:
 lb          # ( f b )
 !<w         # ( ), continue loop if not b < f
] d sw      # w = loop; STACK: ( w )
x           # enter loop unconditionally; STACK: ( ) at entrance

```

# Answer
> 3 votes
# JavaScript (ECMAScript 6 Draft) - 89 Characters

```
f=(m,n,i=2,k=0)=>(m%i|n%i?(k?i+'^'+k+' ':'')+(i>m?'':f(m,n,i+1)):f(m/i,n/i,i,k+1)).trim()

```

Converts the original (iterative) answer, below, into a recursive one.

**Explanation**

```
f=(m,n,i=2,k=0)=>           // A function with arguments m and n and optional arguments
                            // i (defaults to 2) and k (defaults to 0)
  (
    m%i|n%i                 // if i is not a divisor of m or n then:
      ?(k?i+'^'+k+' '       //   if k is non-zero append  "i^k " to the output
         :'')               //   else append nothing
        +(i>m?''            //   if i>m then terminate
             :f(m,n,i+1))   //   else increment i and reset k to 0
      :f(m/i,n/i,i,k+1)     // else divide m and n by i and increment k
  ).trim()                  // finally strip any extra spaces from the output.

```

# Iterative Answer: JavaScript (ECMASCript 6) - ~~108 (or 121)~~ 98 Characters

**Version 2:**

```
f=(m,n)=>{for(s='',i=1;++i<=m;s+=k?' '+i+'^'+k:'')for(k=0;m%i+n%i<1;k++)m/=i,n/=i;return s.trim()}

```

**Version 1:**

Answering the question as originally asked:

```
f=(m,n)=>{for(o=[],i=2;i<=m;)m%i|n%i?i++:(m/=i,n/=i,o[i]=(o[i]|0)+1);return o.map((x,i)=>i+"^"+x).join(' ')}

```

Or to comply with the rule changes after the fact:

```
f=(m,n)=>{for(o=[],i=2;i<=m;)m%i|n%i?i++:(m/=i,n/=i,o[i]=(o[i]|0)+1);return o.map((x,i)=>i+"^"+x).filter(x=>x).join(' ')}

```

**Explanation**

```
f=(m,n)=>                        // Create a function f with arguments m and n
{
  o=[]                           // Initialise an empty array for the output
  i=2                            // Start with a divisor of 2
  for(;i<=m;)                    // Loop while the divisor is not greater than m
    m%i|n%i                      // Test the bitwise OR of m%i and n%1 (i.e. whether
                                 // at least one is non-zero)
      ?i++                       // If m%i>0 or n%i>0 then increment i
      :(m/=i,                    // Otherwise: divide m by i;
        n/=i,                    //                   n by i;
        o[i]=(o[i]|0)+1);        // and add 1 to the i-th element of o
  return o.map((x,i)=>i+"^"+x)   // finally map the sparse array o to a sparse array
                                 // of the strings (index+"^"+value)
          .filter(x=>x)          // turn sparse array into non-sparse array
          .join(' ')             // then concatenate and return.
}

```

**Output**

```
f(96,162)
"2^1 3^1"

f(14,15)
""

f(80, 80)
"2^4 5^1"

f(196,294)
"2^1 7^2"

```

# Answer
> 3 votes
## PowerShell - 82

```
$a,$b=$args
2..$a|%{$p=0;while(!($a%$_+$b%$_)){$a/=$_;$b/=$_;$p++}if($p){"$_^$p"}}

```

# Answer
> 3 votes
# Perl, ~~144~~ ~~133~~ ~~118~~ ~~114~~ ~~97~~ 93

```
($a,$b)=<>=~/\d+/g;for(2..$a){for($n=0;$a%$_+$b%$_<1;$n++,$a/=$_,$b/=$_){}$n&&print"$_^$n ";}

```

Ungolfed version:

```
($a,$b)=<>=~/\d+/g;
for(2..$a){
    for($n=0 ; $a%$_+$b%$_<1 ; $n++,$a/=$_,$b/=$_) {}
    $n&&print"$_^$n ";
}

```

I've literally just started learning Perl just to answer this question (this is my first Perl code ever), so I suspect that this can be golfed down further.

# Answer
> 3 votes
# Perl 6: 90 characters, 94 bytes

```
sub MAIN(*@n){@n.any%$_||(my$p=$p⊎$_;@n»/=»$_;redo)for
2..@n[0];$p.pairs.fmt("%d^%d").say}

```

Somewhat de-golfed and commented:

```
sub MAIN (*@n) { # accept any number of input numbers as @n
    (
        # $p is a Bag, e.g., it holds the primes and the number of times each was added
        my $p = $p ⊎ $_; # Add the prime to the bag
        @n »/=» $_; # Divide all the input numbers by the prime

        redo # Redo the loop iteration with the same prime, in case
             # the numbers can be divided by it multiple times
    )
    if @n.all %% $_ # Do the above only if all of @n are divisible by $_
    for 2..@n[0];   # Do the above for all numbers from 2 .. @n[0]

    $p.pairs.fmt("%d^%d").say # Print join " ", "$prime^$count"
}

```

Usage is like:

```
$ perl6 -e'sub MAIN(*@n){@n.any%$_||(my$p=$p⊎$_;@n»/=»$_;redo)for
2..@n[0];$p.pairs.fmt("%d^%d").say}' 51 153
3^1 17^1

```

# Answer
> 2 votes
# Java : ~~247~~ 241

Keeps track of factors in an array and just prints them out in a loop.

Decent size for Java, it seems.

```
class G{public static void main(String[]a){Integer i=1;int n=i.valueOf(a[0]),m=i.valueOf(a[1]),f[]=new int[n>m?n:m+1];for(;m>=++i||n>i;){if(n%i+m%i<1){f[i]++;n/=i;m/=i--;}}for(i=2;i<f.length;System.out.print(f[i]>0?i+"^"+f[i]+" ":""),i++);}}

// line breaks below

class G{
    public static void main(String[]a){
        Integer i=1;int n=i.valueOf(a[0]),m=i.valueOf(a[1]),f[]=new int[n>m?n:m+1];
        for(;m>=++i||n>i;){
            if(n%i+m%i<1){
                f[i]++;n/=i;m/=i--;
            }
        }
        for(i=1;i<f.length;System.out.print(f[i]>0?i+"^"+f[i]+" ":""),i++);
    }
}

```

# Answer
> 2 votes
# JavaScript (ECMAScript 5) 170 164 163 113

I pretty much couldn't resist following MT0's lead. I had considered recursion before, but it had seemed too easy to mess up. And it really is. The slightest variation wrecks everything.

There's a fiddle for those who like fiddles.

```
function f(a,b,i,e){return i?a%i|b%i?(e?i+'^'+e+' ':'')+(i>a?'':f(a,b,i+1,0)):f(a/i,b/i,i,e+1):f(a,b,2,0).trim()}

```

Ungolfed:

```
function f(a,b,i,e){
    return i // Check for factor.
        ?a%i|b%i // Check for indivisibility.
            ?(
                e // Check for exponent.
                    ?i+'^'+e+' ' // Add the current factor to result string.
                    :'' // Omit the current non-factor.
             )+(
                i>a // Check for termination state.
                    ?'' // Stop recursion.
                    :f(a,b,i+1,0) // Go to the next factor.
            )
            :f(a/i,b/i,i,e+1) // Failed indivisibility check. Increment exponent and divide subject values.
        :f(a,b,2,0) // Add default factor and exponent.
        .trim() // Get rid of one extra space that's usually on the end.
}

```

### Old Version

```
function f(a,b){for(var r=[],j=-1,i=2;i<=a;)a%i|b%i?++i:(r[j]&&r[j][0]==i?r[j][1]++:r[++j]=[i,1],a/=i,b/=i);for(j=0;i=r[j];++j)r[j]=i.join('^');return r.join(' ')}

```

Ungolfed:

```
function f(a,b){
    for(var r=[],j=-1,i=2;i<=a;)
        // We (mis)use conditional expression `?:` instead of `if(){}else{}`.
        a%i|b%i ? // Bitwise OR saves one character over logical OR, where applicable.
             // In the truth case, `i` has become uninteresting. Just move on.
            ++i : // We don't mind hitting composites because their prime factors have already been drained from `a` and `b`.
            (
                r[j]&&r[j][0]==i ? // Check if `i` is already a listed factor.
                    r[j][1]++ : // Increment the exponent count.
                    r[++j]=[i,1], // Otherwise, add a new factor with exponent 1.

                a/=i,b/=i // Drain a used-up factor from `a` and `b`.
            );

    // The real work's done. Now we just format.
    for(j=0; i=r[j]; ++j)
        r[j]=i.join('^'); // Join each factor to its exponent.

    return r.join(' ') // Join all factors into result string.
}

```

Here are a few tests:

```
[
    f(4, 12),
    f(80, 80),
    f(96,162),
    f(196,294)
];

```

# Answer
> 2 votes
# GolfScript, 68 bytes

```
~..),2>*${1$1$%3$2$%+!{.@@/@2$/.}*;}/;;]:D.&{`.[~]D\/,(`"^"\++}%" "*

```

Note that this approach requires O(b2) time and space for integers “a” and “b”.

At the cost of one extra byte, "only" O(b) time and space are necessary:

```
~.),2>31*${1$1$%3$2$%+!{.@@/@2$/.}*;}/;;]:D.&{`.[~]D\/,(`"^"\++}%" "*

```

### How it works

```
~.        # Interpret the input string (“a” and “b”) and duplicate “b”.
.),2>     # Push the array [ 2 3 4 ... b ].
*$        # Repeat each element b times and sort: [ 2 ... 2 3 ... 3 ... b ... b ]
{         # For each element “d” of the array:
  1$1$%   # Calculate a % d.
  3$2$%   # Calculate b % d.
  +!      # Add and negate.
  {       # If both “a” and “b” are divisible by “d”:
    .@@/  # Calculate a / d.
    @2$/  # Calculate b / d.
    .     # Create a dummy value.
  }*      #
  ;       # Pop the topmost stack element (non-divisor “d” or dummy value).
}/        #
;;]       # Pop “a” and “b” and collect the remaining stack elements in an array.
:|.&      # Save that array in “D” and intersect it with itself to deduplicate it.
{         # For each element “d” of “D”:
  `.[~]   # Push string "d" and array [d].
  D\/,(`  # Split “D” around [d] and take the length minus 1. This count the occurrences.
  "^"\    # Push the string "^" and swap it between "d" and it's number of occurrences.
  ++      # Concatenate the three strings.
}%        # Collect all strings into an array.
]" "*     # Join by spaces.

```

# Answer
> 1 votes
# awk - ~~115~~ ~~111~~ ~~96~~ 85

New version can only handle one line of input. Thanks to durron597 for pointing out that I only need to make sure `i <= $1`.

```
{for(i=1;++i<=$1;)for(;$1%i+$2%i==0;f[i]++){$1/=i;$2/=i}$0=z;for(i in f)$i=i"^"f[i]}1

```

Ungolfed:

```
{
    #skip finding gcd as a separate step, get it from the factors
    for(i = 1; ++i <= $1;) {
        for(;$1 % i == 0 && $2 % i == 0; f[i]++) {
            $1 /= i;
            $2 /= i;
        }
    }
    $0 = "";
    for(i in f) {
        $i = i "^" f[i];
    }
    print;
}

```

Previously could take pairs of numbers repeatedly

```
{a=$1;b=$2;for($0=c;a-b;)if(a>b)a-=b;else b-=a;for(i=2;i<=a;i++){for(j=0;a%i==0;j++)a/=i;$0=$0(j?i"^"j" ":c)}}1

```

Ungolfed:

```
{
    a = $1;
    b = $2;
    $0 = "";
    #rip off Euclid
    for(; a != b;) {
        if(a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    #but not Eratosthenes
    for(i = 2; i <= a; i++) {
        for(j = 0; a % i == 0; j++) {
            a /= i;
        }
        $0 = $0 (j ? i "^" j " " : "");
    }
    print;
}

```

# Answer
> 1 votes
# Python 3 (123)

This uses basically the same structure as Tal's answer.

```
a,b=map(int,input().split())
s='';p=1
while p<a:
 c=0;p+=1
 while a%p+b%p<1:a/=p;b/=p;c+=1
 if c:s+='%d^%d '%(p,c)
print(s)

```

It suffices to loop up to p=a-1, since we increment immediately to get p=a and a\>=min(a,b). If b\>a, there's no harm in trying useless values of p above a.

In 2.X, I think we could save characters by printing each piece as we get it rather than accumulating a string: `if c:print'%d^%d'%(p,c),`. Python 3, unfortunately, doesn't seem to have a compact way to print without a trailing newline.

# Answer
> 1 votes
# PHP, 96

```
<?php
list(,$a,$b)=$argv;for($s=1;$s++<$a;$c&&print"$s^$c ")for($c=0;1>$a%$s+$b%$s;$a/=$s,$b/=$s)$c++;

```

# Answer
> 1 votes
# Pip, 41 bytes

**Not a competing answer, since language is newer than question.** But that GolfScript mark of 68 needed to come down.

```
Fi2,++a{p:0T$|g%i{++pg/:i}Ipx.:i.'^.p.s}x

```

Output ends in a space; if that's a problem, the following version is also 41 bytes (including the `-s` flag):

```
Fi2,++a{p:0T$|g%i{++pg/:i}IplAE:i.'^.p}l

```

Formatted, with explanations:

```
F i 2,++a {      For i in range(2,a+1); note ++ used to avoid parentheses in 2,(a+1)
  p:0            p will store the greatest power of i that divides both numbers
  T $+(g%i) {    Loop till the sum of g%i is nonzero, where g is a list initialized
                  from cmdline args
    ++p          As long as g%i is [0 0], increment p...
    g/:i         ...and divide both numbers in g by i
  }
  I p            If p is nonzero, i went into both numbers at least once
    x.:i.'^.p.s  Append i^p and a space to the result
}
x                Print the result

```

Pip, unlike GolfScript, CJam, et al. is an imperative language with infix operators; it also takes some inspiration from array-programming languages. This task nicely displays both paradigms at work.

(Note that the 2015-4-20 commit is needed to run this, since I just fixed a couple of bugs.)

# Answer
> 0 votes
# Python 2 - 262 bytes

```
n,m=input(),input()
f=lambda i:set(filter(lambda x:i%x<1,range(1,i+1)))
g=max(f(n)&f(m))
p=[]
while g-1:
 p+=[min(filter(lambda x:x>1 and x%2!=(x==2)and not any(map(lambda y:x%y<1,range(2,x))),f(g)))]
 g/=p[-1]
print ' '.join(`a`+^+`p.count(a)`for a in set(p))

```

Line 6 needs work.

# Answer
> 0 votes
## Groovy : 174 chars

This is a port of Geobits' solution to Groovy 2.2.1:

```
int i=1, n=args[0]as int, m=args[1]as int;s=n>m?n:m+1;f=new int[s];while(m>=++i||n>i){if(n%i+m%i<1){f[i]++;n/=i;m/=i--;}};(s-1).times{y=it+1;x=f[y];print"${x>0?"$y^$x ":""}"}

```

Here is the ungolfed version:

```
int i = 1, n = args[0] as int, m = args[1] as int

s = n>m?n:m+1
f = new int[s]

while (m>=++i||n>i) {
    if (n%i+m%i<1) {
        f[i]++;n/=i;m/=i--;
    }
}
(s-1).times {
    y=it+1
    x=f[y]
    print"${x>0?"$y^$x ":""}"
}

```

# Answer
> 0 votes
## R: 139

```
a=scan();q=1:a[1];n=max(q[!a[1]%%q&!a[2]%%q]);m=rep(0,n);for(i in 2:n){while(!n%%i){m[i]=m[i]+1;n=n/i};if(m[i])cat(paste0(i,"^",m[i])," ")}

```

With indentations:

```
a=scan() #Take space-separated numeric input from stdin
q=1:a[1]
n=max(q[!a[1]%%q&!a[2]%%q]) #gcd
m=rep(0,n)
for(i in 2:n){
    while(!n%%i){ #prime factorization
        m[i]=m[i]+1
        n=n/i
        }
    if(m[i])cat(paste0(i,"^",m[i])," ")
    }

```

Usage:

```
> a=scan();q=1:a[1];n=max(q[!a[1]%%q&!a[2]%%q]);m=rep(0,n);for(i in 2:n){while(!n%%i){m[i]=m[i]+1;n=n/i};if(m[i])cat(paste0(i,"^",m[i])," ")}
1: 196 294
3:
Read 2 items
2^1  7^2

```

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


title: Code-Challenge:The Nearest Prime

text:
# Question
Title: Code-Challenge:The Nearest Prime
## Challenge

> In this task you would be given an integer N you have to output the nearest prime to the integer.

If the number is prime itself output the number.

The input N is given in a single line,the inputs are terminated by EOF.The number of inputs would not exceed 10000 values.

The challenge is to implement the fastest solution so that it can process a maximum of 10000 values as fast as possible.

**Input**

```
 299246598
 211571591
 71266182
 645367642
 924278231

```

**Output**

```
 299246587
 211571573
 71266183
 645367673
 924278233

```

**Constraints**

* N is less than 2^64
* Take care of your fingers do not use more than 4096 bytes in your solution.
* You can use any language of your choice as long as you are not using it's any inbuilt things for the primes.
* Fastest solution,with the most efficient time complexity wins!

**ADDED:**

This is a easier version of the this same problem (with N \< 2^31) so that you may try checking your approach in smaller cases before building it up for this actual problem.

# Answer
## Python

```
import sys,random

# Miller-Rabin primality test, error rate 2^-200.
def prime(N):
  if N<3:return N==2
  s=0
  d=N-1
  while (d&1)==0:s+=1;d>>=1
  for i in xrange(100):
    a=random.randrange(1,N)
    if pow(a,d,N)!=1 and all(pow(a,d<<r,N)!=N-1 for r in xrange(s)):return 0
  return 1

for N in map(int,sys.stdin):
  d=0
  while 1:
    if prime(N+d):print N+d;break
    if prime(N-d):print N-d;break
    d+=1

```
> 6 votes

# Answer
## PARI GP

```
a(n)=x=[precprime(n),nextprime(n)];print(if(x[1]-n<n-x[2],x[1],x[2]))
while(1,print(a(input())))

```
> 2 votes

# Answer
# Haskell

```
import Data.Numbers.Primes

-- Assuming, we are on x64
nearestPrime :: Int -> Int
nearestPrime n | n - s < l - n = s
               | otherwise     = l where
  l = head $ dropWhile (not . isPrime) [n..]
  s = head $ dropWhile (not . isPrime) [n,n-1..]

main = readLine >>= print . nearestPrime . read

```

Should be quite fast. Requires the package `primes`, available from hackage.
> 0 votes

# Answer
**Ruby**

```
require 'prime'
gets(p).split.each{|n|
    a=b=n.to_i
    a,b = a-1,b+1 while !a.prime?  and !b.prime?
    p a.prime? ? a : b
}

```
> 0 votes

# Answer
# Java

This takes \<1 second until num starts being greater than 10^8. Not efficient enough, considering 2^64 is about 1.8\*10^19. (Started 10^15 6 minutes ago, and is still running D:)

```
import java.util.*;

class ClosestPrime {

    public static double closest(double num) {
        double returnme = 0;
        if (isPrime(num)){returnme = num;}
        for (double i = 0; i < num / 2; i++) { //checks each side of num
            if (isPrime(num - i)) {returnme = num - i;
                break;}
            if (isPrime(num + i)) {returnme = num + i;
                break;}
        }
        return returnme;
    }

    private static boolean isPrime(double num) {
        long sqrtnum = (long) Math.sqrt(num); //no need to check for factors above sqrt(num)
        List<Double> primes = new LinkedList<Double>();
        primes.add((double) 2);
        for (double i = 3; i < sqrtnum; i+=2) {primes.add(i);} //fill list with odd numbers

        for (long i = 2; i <= sqrtnum; i++) {
            if (num / i % 1 == 0) {return false;}
            ListIterator<Double> iter = primes.listIterator();
            while (iter.hasNext()) {if ((iter.next()) / i % 1 == 0){iter.remove();}} //sieving by Eratosthenes
        }
        return true;
    }
}

```

This gives a surefire answer every time, since it doesn't use a probabilistic algorithm, but pays heavily for that in terms of efficiency - 10^18 would have over 5 million primes in the list, and even more before sieving. May improve this sometime with a better sieve algorithm. I don't expect this to beat any of the others :)
> 0 votes

# Answer
# Haskell

This is pretty fast, and non-deterministic up to a large limit. Also my first ever Haskell :). `wc` says 903b uncompiled.

Edit: If anyone wants to estimate the time complexity, be my guest...

```
import System.Environment
import Math.NumberTheory.Moduli -- arithmoi
import Data.List.Ordered -- data-ordlist

main :: IO ()
main = interact processInputStrings

processInputStrings :: String -> String
processInputStrings input = unlines $ map show $ getClosestMembers $ map read $ lines $ input

isPrime :: Integer -> Bool
{- Implement the Miller–Rabin test with basis valid up to somewhere > 2^64 -}
isPrime 2 = True
isPrime 3 = True
isPrime t =  let
        factor :: (Integer, Integer) -> (Integer, Integer)
        factor (d,s) = if even d then factor (d `div` 2, s+1) else (d,s)
        (d,s) = factor (t-1, 0)
    in
        and $ map (\a ->
            or [(powerMod a d t) == 1, or [(powerMod a (2^r * d) t) == t-1 | r <- [0..s-1]]]
        ) $ filter (<t) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

getClosestMembers :: [Integer] -> [Integer]
getClosestMembers inputs = map (\i -> head [n | n <- concat [[i-d, i+d] | d <- [0..]], isPrime n]) inputs

```
> 0 votes

---
Tags: primes, fastest-algorithm
---


title: Build a Simple Roguelike

text:
# Question
Title: Build a Simple Roguelike
This challenge is based on one proposed on the usenet group **rec.games.roguelike.development** a few years ago. I can't find the original newsgroup post, but you can have a look a the Github repo of solutions. It was only golfed in a couple of languages and I'd love to see some more!

## Objective

The aim is to build a program that presents a top-down view of a dungeon using ascii characters. There will be an `@` sign representing the player that can be moved through the free space in the dungeon (represented by ), though it cannot pass through the walls (represented by `#`).

The map of the dungeon must look like this:

```
####  ####
#  #  #  #
#  ####  #
#        #
##      ##
 #      #
 #      #
##      ##
#        #
#  ####  #
#  #  #  #
####  ####

```

The player must begin at location {2,2}, where {0,0} is the top left-hand corner.

## Interface

The user needs to be able to move the player in the four cardinal directions using the arrow keys on the keyboard.

There needs to be some way for the user to exit the program. It does not need to be a graceful exit (for example, it doesn't matter if an exception is printed).

The map and player need to be drawn before any input has been taken, and the player needs to be updated after each input.

## Libraries

Feel free to use established libraries for console input or output, such as Curses. Just mention in your answer what you are using.

## Scoring

This is code golf, shortest code wins!

# Answer
> 6 votes
## C, 257 253 222 220

Uses `system("cls")` instead of curses (use `system("clear")` for Linux systems) and a clever algorithm to fit the map into an 8-digit number. Non-extended keys end the program, e.g. escape.

EDIT: Now also shows your hero below the map by using `a<230` instead of `a<132`:

```
    ##
   ####
 ###  ###
 # #  # #
## #  # ##
   ####
  #    #
 ##    ##

```

Code:

```
a,p=14,w=11,X,Y;m(I){X=I%w-1,Y=I/w;return 70313263>>(Y>5?w-Y:Y)*5+(X>4?9-X:X)&1;}main(){do{system("cls");a=a&4?1:a&2?-1:a&8?-w:w;p+=!m(p+a)*a;for(a=0;++a<230;)putch(a%w?a-p?m(a)*35:64:10);}while(a=getch()>>7?getch():0);}

```

# Answer
> 4 votes
## Ruby 1.9 + Curses (248)

```
require'curses';include Curses;noecho;curs_set 0
b=0xf3e499e601c0d0240b0380679927cf.to_s(2).tr'01',' #'
s=init_screen<<b.scan(/.{10}/)*$/;s.keypad 1
p=22;d=->t=?@{setpos p/10,p%10;addch t;6};d[]
loop{p=b[v=p+[10,-10,-1,1][getch%d[32]]]<?#?v:p;d[]}

```

# Answer
> 3 votes
# Python 332 319 317

```
from curses import*
M=0xf3e499e601c0d0240b0380679927cf;S=initscr();S.keypad(1);x,y=2,2;A=S.addstr;[A(a,b,[' ','#'][M>>(10*a+b)&1])for a in range(12)for b in range(10)]
while 1:A(y,x,'@');k=S.getch();A(y,x,' ');X=[[x,x-1],[x+1,1]][k==261][k==260];Y=[[y,y-1],[y+1,y+1]][k==258][k==259];x,y=[(X,Y),(x,y)][M>>(10*Y+X)&1]

```

The python curses library is only officially supported on linux. There are unofficial ones available for windows, but I can't guarantee that this will work with it.

To save a few characters I hard coded the keycodes for up, down, left, and right. This may cause problems for some people. If this doesn't work for anyone I can post a version that should.

Use ctrl+c to exit. You will probably have to reset your terminal after exiting, but the challenge specifically said the exit didn't have to be graceful.

# Answer
> 1 votes
# QBasic, ~~314~~ 313 bytes

This sort of problem simply begs for a QBasic solution.

```
DIM w(12,10)
FOR r=1TO 12
READ d
FOR c=1TO 10
w(r,c)=(d*2AND 2^c)>0
?CHR$(35+3*w(r,c));
NEXT
?
NEXT
i=3
j=3
1LOCATE i,j
?"@"
a$=""
9a$=INKEY$
IF""=a$GOTO 9
k=ASC(RIGHT$(a$,1))
x=i+(k=72)-(k=80)
y=j+(k=75)-(k=77)
LOCATE i,j
?" "
IF w(x,y)THEN i=x:j=y
IF k>9GOTO 1
DATA 48,438,390,510,252,765,765,252,510,390,438,48

```

This is golfed QBasic, which will be expanded significantly by the autoformatter. But, if you type this exact code into the IDE and hit F5, it should run. Tested on QB64.

**Explanation:**

The map is encoded row-wise as the bits of the integers in the `DATA` statement (1 for space, 0 for wall). The nested `FOR` loop unpacks them, storing truth values in the 2D array `w`, and printing `#` or  accordingly. (Note that true in QBasic is `-1`, thus why we're adding to 35 instead of subtracting!) The player starts at 3,3 because most things are 1-indexed in QBasic.

We then enter a `GOTO` loop: print the `@`, get keyboard input, convert to extended character code, and modify `x` and `y` based on whether the user pressed L/U/R/D. If `w(x,y)` is true, then it's a space and we can move there; otherwise, stay put. Finally, the shortest way I found to exit is by pressing the tab key (ASCII `9`). Any other input loops us back up to the first `LOCATE` statement.

I must say, I'm rather tickled to have beaten Python with a QBasic answer.

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


title: Smoothing out a list

text:
# Question
Title: Smoothing out a list
You should write a program or function which takes a non-negative integer `k` and a sorted integer list `L`as input and outputs or returns a smoothed list `M`.

`M` is created from the ascending list `L` by inserting at most `k` integer elements while keeping the list sorted. The inserted integers should be chosen in a way that the maximum forward difference of `M` will be as small as possible. We will call this smallest value "smoothness".

The forward differences of the list `-1 3 8 11 15` are `4 5 3 4` and the maximum forward difference is `5`.

With `2` insertions the smoothness of `2 10 15` is `4` and a possible output is `2 6 10 11 15` with forward differences `4 4 1 4`.

## Input

* A non-negative integer `k`.
* An ascending integer list `L` with at least 2 elements.

## Output

* The ascending integer list `M`.
* If multiple correct answers exists output exactly one of them (any one is sufficient).
* **Your solution has to solve any example test case under a minute** on my computer (I will only test close cases. I have a below-average PC.).

## Examples

Input (`k`, `L`) =\> A possible output and the maximum forward difference (which is not part of the output) in parentheses

```
0, 10 20 => 10 20 (10)

2, 1 10 => 1 4 7 10 (3)

2, 2 10 15 => 2 6 10 11 15 (4)

3, 2 10 15 => 2 5 8 10 12 15 (3)

5, 1 21 46 => 1 8 15 21 27 33 39 46 (7)

5, 10 20 25 33 => 10 14 18 20 24 25 29 33 (4)

3, 4 4 6 9 11 11 15 16 25 28 36 37 51 61 => 4 4 6 9 11 11 15 16 22 25 28 36 37 45 51 59 61 (8)

15, 156 888 2015 => 156 269 382 495 608 721 834 888 1001 1114 1227 1340 1453 1566 1679 1792 1905 2015 (113)

8, -399 -35 -13 56 157 => -399 -347 -295 -243 -191 -139 -87 -35 -13 39 56 108 157 (52)

5, 3 3 3 => 3 3 3 3 (0)

```

This is code-golf so the shortest entry wins.

# Answer
> 5 votes
# Pyth, ~~28~~ 27 bytes

```
S+Qu?smt%hHrFdC,QtQ>GvzGhvz

```

Input given like:

```
3
[2, 10, 15]

```

Demonstration. Test harness.

Note: At the time the question was asked, there was a small bug in Pyth related to using `rFd` inside `u`, which I just fixed. The bug rendered it impossible to ever use `F` inside `u`, which was definitely not intended.

```
S+Qu?smt%hHrFdC,QtQ>GvzGhvz

                               Implicit:
                               z is the number of insertions, in string form.
                               Q is the input list.
              C,QtQ            Pairs of elements, e.g. [(2, 10), (10, 15)]
           rFd                 d = (a, b) -> range(a, b)
        %hH                    Take every H+1th element of that range
       t                       And throw out the first one.
      m                        Perform this process for each element pair
     s                         And combine the results into one list.

                               The above is a minimal set of additional elements
                               To reduce the maximal difference to H+1.

  u                     hvz    Repeat until the result stops changing, where
                               the prior result is G, H starts at 0 and
                               increases by 1 each repetition, and
                               G is initialized to eval(z)+1.
   ?               >GvzG       If not G[eval(z):], return G. In other words,
                               if the prior result was short enough, stop.
                               Also, this is always false on the initial call.
    smt%hHrFdC,QtQ             Otherwise, recalculate with H incremented.
S+Q                            Take the result, add the original list, and sort.

```

---

Here's a version which would have worked with the interpreter at the time the question was asked. It's 28 bytes, and works exactly the same way:

```
S+Qu?smt%hHr.udC,QtQ>GvzGhvz

```

Demonstration.

Git commit of the appropriate version, f6b40e62

# Answer
> 8 votes
# Python 2, 104

```
def f(L,k,d=1):
 M=[];p=L[0]
 for x in L:M+=range(p+d,x,d);p=x
 return M[k:]and f(L,k,d+1)or sorted(L+M)

```

Tries different maximum increments `d`, starting from 1 and counting up. Fills in gaps of each pair `(p,x)` of successive elements by taking every `d`'th number in the gap. If `M` is longer than the quota allows, recurses to try a higher `d`. Otherwise, returns a list of the added and original elements, sorted.

This does all the test cases without delay on my machine.

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