title: Decimal Digit Truncating

text:
# Question
Title: Decimal Digit Truncating
## Input:

A decimal

## Output:

The input truncated

**How to truncate them?**

The integer part of the input will remain the same. The decimal part of the input will be truncated based on the lowest digit in consecutive order. The two step-by-step examples below should clarify what I mean by that:

*Example 1:* Input: `17.46940822`

Step 1: Leave the integer part unchanged: `17`
Step 2: Look at the first decimal digit, and truncate it to that many decimal digits: `4``.4694`
Step 3: Look at the next decimal digit. If it's lower, adjust the truncation accordingly. If not, continue to the next decimal digit: `6` → remains `.4694`
Step 3 again: `9` → remains `.4694`
Step 3 again: `4` → remains `.4694`

So the output will be: `17.4694`.

*Example 2:* Input: `10.4521084`

Step 1: Leave the integer part unchanged: `10`
Step 2: Look at the first decimal digit, and truncate it to that many decimal digits: `4``.4521`
Step 3: Look at the next decimal digit. If it's lower, adjust the truncation accordingly. If not, continue to the next decimal digit: `5` → remains `.4521`
Step 3 again: `2` → truncation adjusted to: `.45`

So the output will be: `10.45`

## Challenge rules:

* You are allowed to take the input as decimal, string, list/array/stream of characters, etc. (Same applies to the output, although I doubt there are a lot of languages that have the proper truncation while remain working with decimal values.)
You are also allowed to use a comma `,` instead of a dot `.` (perhaps useful for regex-based solution/languages).
* If the decimal part is not long enough for the truncation, you are optionally allowed to add trailing zeros. I.e. `123.4` can be both `123.4` or `123.4000`
* If you have to truncate to `0` decimal digits we omit the decimal digits. The dot/comma may remain optionally if you use strings. I.e. `847.3072``847` (or `847.`)
* You can assume the input will always contain at least one decimal digit, so `123` won't be an input, but `123.0` can be an input.

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

```
Input:          Output:

17.46940822     17.4694
10.4521084      10.45
123.4           123.4000 (or 123.4)
-847.3072       -847 (or -847.)
123.0           123 (or 123.)
98.76543210     98.7654
0.3165          0.3
-0.1365         -0.1
82937.82937     82937.82
-0.1010101      -0.1
-1.0101010      -1 (or -1.)
28.684297       28.68
13.35           13.350 (or 13.35)
0.99999999999   0.999999999
28.321          28.32
0.56462         0.5646

```

# Answer
# 05AB1E, 18 bytes

2 bytes extra due to a bug with `£` not handling **0** correctly.

```
'.¡`DvÐgsNè-F¨]'.ý

```

Try it online! or as a Test Suite

**Explanation**

```
    '.¡                 # split input on "."
       `                # push int and decimals separately to stack
        D               # duplicate decimal digits
         v              # for each
          Ð             # triplicate the current decimal digits
           g            # get the length
            sNè         # get the Nth digit
               -        # subtract from the total length
                F¨]     # drop that many digits from the end
                        # end loop
                   '.ý  # join on "."

```
> 4 votes

# Answer
# Python 2, ~~103 101 98~~ ~~94~~ ~~93~~ 87 bytes

```
a,b=input().split('.');i,w=0,len(b)
while w>i:w=min(int(b[i]),w);i+=1
print a+'.'+b[:w]

```

Try it online!

---

Saved:

* -2 bytes, thanks to Kevin Cruijssen
* -3 bytes, thanks to Vedant Kandoi
* -4 bytes, thanks to Lynn
> 4 votes

# Answer
# JavaScript (Node.js), 58 bytes

```
f=(s,p=1/0,q=1,c=s[q])=>c?f(s.slice(0,p-~c),++c?p:q,q+1):s

```

Try it online!
> 3 votes

# Answer
# Charcoal, 28 bytes

```
≔⪪Ｓ.θＷ⊟ＥθΦκ‹ΣμＬκ⊞θ…⊟θＩ§ι⁰⪫θ.

```

Try it online! Link is to verbose version of code. Explanation:

```
≔⪪Ｓ.θ

```

Split the input on `.`.

```
Ｗ⊟ＥθΦκ‹ΣμＬκ

```

Filter each part on those digits that are less than the string's length. Then take the last result. (This saves 1 byte over filtering on just the decimals.) Loop until that is empty.

```
⊞θ…⊟θＩ§ι⁰

```

Take the first filtered digit and truncate the decimals to that length.

```
⪫θ.

```

Join the parts back together and implicitly print.
> 2 votes

# Answer
# C (gcc), ~~84~~, 78 bytes

Takes input as a pointer to a string buffer, outputs by modification. Note that providing a pointer to a buffer that is too small (`intPartLen + 1 + 9 > bufSize`) can cause `SEGFAULT`.

If assuming the size of the buffer to be sufficient is not allowed, +7 to the score.

```
l,M;f(char*F){F=strchr(F,46);for(l=47,M=57;*++F&&++l<M;*F<M?M=*F:0);F[M-l]=0;}

```

Try it online!

## Degolf

```
l,M;f(char*F){
    F=strchr(F,46); // Find the pointer to the period.
    for(l=47,M=57;  // Initialize variables (48='0', 57='9')
            *++F&&++l<M;  // Check for null terminator, and that we're not
                          // going through too many decimals
            *F<M?M=*F:0); // Keep smaller of M and the char pointed to by F.
        F[M-l]=0; // Explained below.
}

```

At the end of the loop, `F` is a pointer to the `n`th decimal after the decimal point (`ptr`). `M` is the smallest digit observed as its ASCII value. `l` is `'0'+n-1` (or `47+n`). Thus:

```
F[M-l] == *(F + M - l)
F[M-l] == *(ptr + n + M - '0' - n + 1)
F[M-l] == *(ptr + M - '0' + 1)

```

Which gives us a pointer to the first character to truncate; replacing this character with a `\0` results in the truncation of the remaining digits for most intents and purposes. This is also where the `SEGFAULT` happens; for example, if the input is `123.4`, the smallest digit is `4`, and the pointer will point to the character `*` in `123.4\0??*`.
> 2 votes

# Answer
# Ruby `-pl`, 48 bytes

```
c=i=j=$_=~/,/;$_=$_[0,c.to_i-~j]while c=$_[i+=1]

```

Try it online!

Uses a decimal comma instead of a dot.
> 2 votes

# Answer
# PHP, 92 bytes

several solutions, same length:

```
# any PHP:
for($n=$argn,$t=9;~$d=$n[$i+++$p=1+strpos($n,46)];$n=substr($n,0,$p+$t))$t<$d||$t=$d;echo$n;
for($t=9;$i<$t&&~$d=$n[$i+++$p=1+strpos($n=$argn,46)];)$t<$d||$t=$d;echo substr($n,0,$p+$t);
for($t=9;$i<$t&&~$d=$n[++$i+$p=strpos($n=$argn,46)];)$t<$d||$t=$d;echo substr($n,0,$p+$t+1);

# PHP 7:
for($t=9;~$d=($n=&$argn)[$i+++$p=1+strpos($n,46)];$n=substr($n,0,$p+$t))$t<$d||$t=$d;echo$n;
for($n=$argn;~$d=$n[$i+++$p=1+strpos($n,46)];$n=substr($n,0,$p+$t))($t??9)<$d||$t=$d;echo$n;

```

Run as pipe with `-nR` or try (most of) them online.
> 2 votes

# Answer
# JavaScript, 58 bytes

Input and output as a string, using a comma as the decimal separator.

```
s=>s.replace(/,.+/,g=d=>d[++n]?g(d.slice(0,-~d[n])):d,n=0)

```

Try it online
> 2 votes

# Answer
# JavaScript (Node.js), ~~78~~ 68 bytes

*-10 bytes from @tsh*

```
a=>eval('for([x,y]=a.split`.`,i=0;c=y[i++];y=y.slice(0,c));x+`.`+y')

```

Try it online!
> 1 votes

# Answer
# Perl 6 `-p`, ~~57~~ 41 bytes

```
$!=m/\./.to;.=substr(0,$!+$/)while m:c/./

```

Try it online!

### Explanation

```
$!=m/\./.to;       # Store position of decimal point in $!
.=substr(0,$!+$/)  # Truncate string to length $!+$/
while m:c/./       # while there's a match for the next digit

```
> 1 votes

# Answer
# Python 3, 77 bytes

```
g,h=input().split(".")
for i in h:h=h[:int(i)]if i in h else h
print(g+"."+h)

```

Try it online!

Somehow, despite slicing past the end of a string and modifying while iterating on that same string, the interpreter doesn't complain.

This answer has a similar structure to the other Python one, but uses a different method to find where to truncate and works in newer versions of Python.
> 1 votes

# Answer
# Clean, 115 bytes

```
import StdEnv,Text
$s#[i,d:_]=split['.']s
=i++['.':iter 9(\p=hd([take n\\n<-map digitToInt p|n<length p]++[id])p)d]

```

Try it online!

Defines the function `$ :: [Char] -> [Char]`. Link includes test suite.
> 1 votes

---
Tags: code-golf, number, floating-point
---


title: Convert a number to Hexadecimal

text:
# Question
Title: Convert a number to Hexadecimal
# Challenge

Here's a simple one.

Write a function or program when given a number in base 10 as input, it will return or print that number's value in Hexadecimal.

# Examples

```
15 -> F
1000 -> 3E8
256 -> 100

```

# Rules

* No built-in Hexadecimal functions whatsoever
* Letters may be lowercase or uppercase
* You will only need to worry about non-negative integers, no negatives or pesky decimals
* It should work with any arbitrarily large number up to language's default type's limit.
* Newline not mandatory
* As usual, this is , so shortest code measured in bytes wins!

# Answer
> 4 votes
# APL (Dyalog APL), 17 bytes

Must be run with `⎕IO←0`, which is default on many APL systems.

```
(⎕D,⎕A)[16⊥⍣¯1⊢⎕]

```

Try it online!

`(⎕D,⎕A)[``]`**D**igits concatenated to **A**lphabet, then indexed by…

`16⊥⍣¯1` the inverse of 16-Base-to-Number, i.e. Number-to-Base-16

applied to

numeric input

# Answer
> 14 votes
# Turing Machine Code, 412 bytes

As usual, I'm using the rule table syntax defined here. You can test it on that site or, alternatively, using this java implementation.

```
0 * * l B
B * * l C
C * 0 r D
D * * r E
E * * r A
A _ * l 1
A * * r *
1 0 9 l 1
1 1 0 l 2
1 2 1 l 2
1 3 2 l 2
1 4 3 l 2
1 5 4 l 2
1 6 5 l 2
1 7 6 l 2
1 8 7 l 2
1 9 8 l 2
1 _ * r Y
Y * * * X
X * _ r X
X _ _ * halt
2 * * l 2
2 _ _ l 3
3 * 1 r 4
3 1 2 r 4
3 2 3 r 4
3 3 4 r 4
3 4 5 r 4
3 5 6 r 4
3 6 7 r 4
3 7 8 r 4
3 8 9 r 4
3 9 A r 4
3 A B r 4
3 B C r 4
3 C D r 4
3 D E r 4
3 E F r 4
3 F 0 l 3
4 * * r 4
4 _ _ r A

```

Counts down from the input in base 10 while counting up from 0 in base 16. On decrementing zero, it erases the input block and terminates.

# Answer
> 9 votes
# Java, ~~92~~ 89 bytes

```
String x(int v){String z="";for(;v>0;v/=16)z="0123456789ABCDEF".charAt(v%16)+z;return z;}

```

# Answer
> 9 votes
# Javascript, ~~49~~ 43 bytes.

```
h=i=>(i?h(i>>4):0)+"0123456789abcdef"[i%16]

```

6 bytes saved by user81655.

Test it here.

This has two leading zeroes, which is allowed by the rules.

Here's a version without leading zeroes: (47 bytes).

```
h=i=>(i>15?h(i>>4):"")+"0123456789abcdef"[i%16]

```

Test it here.

Both of these uses exactly the same approach as my Python answer.

# Answer
> 8 votes
# CJam, ~~22~~ 21 bytes

```
ri{Gmd_A<70s=+\}h;]W%

```

*Thanks to @MartinBüttner for golfing off 1 byte!*

Try it online!

### How it works

```
ri                      e# Read an integer from STDIN.
  {             }h      e# Do:
   Gmd                  e#   Push qotient and residue of the division by 16.
      _A<               e#   Check if the residue is less than 10.
         70s            e#   Push "70".
            =           e#   Select the character that corresponds to the Boolean.
             +          e#   Add the character to the digit.
                        e#   This way, 10 -> 'A', etc.
               \        e#   Swap the quotient on top of the stack.
                        e# While the quotient is non-zero, repeat the loop.
                  ;     e# Pop the last quotient.
                   ]W%  e# Reverse the stack.

```

# Answer
> 6 votes
# Pyth, 33 26 21 20 bytes

This was a fun one.

```
sm@+jkUTGi_d2_c_.BQ4

```

Try it online.

Explained:

```
                .BQ      Convert input to a binary string, e.g. 26 -> '11010'
             _c_   4     Reverse, chop into chunks of 4, and reverse again. We reverse
                         because chop gives a shorter last element, and we want a shorter
                         first element: ['1', '0101']
                         Reversing three times is still shorter than using .[d4 to pad the
                         binary string to a multiple of 4 with spaces.
 m                       Map across this list:
         i_d2                Take the value of the reversed string in binary,
  @                          and use it as an index into the string:
   +jkUTG                    '0123456789abcdefghijklmnopqrstuvwxyz'
                             (The alphabet appended to the range 0 to 10)
s                        Concatenate to create the final string.

```

# Answer
> 5 votes
# Python, ~~59~~ 58 bytes

```
h=lambda i:(i>15 and h(i/16)or'')+"0123456789abcdef"[i%16]

```

1 byte saved by CarpetPython

Run as: `print h(15)`

Test it here (Ideone.com).

Explanation:

```
h=lambda i:                                                 # Define h as a function that takes two arguments
           (i>15 and h(i/16)or'')                           # Evaluate h(i/16) if i > 15, else, give ''
                                 +"0123456789abcdef"[i%16]  # Append (i%16)'th hexadecimal number.

```

# Answer
> 5 votes
## Haskell, ~~59~~ ~~58~~ ~~43~~ ~~41~~ 39 bytes

```
s="0123456789ABCDEF"
(sequence(s<$s)!!)

```

Usage example: `sequence(s<$s)!!) $ 1000` -\> `"00000000000003E8"`.

This creates a list of all hexadecimal numbers up to 16 hex-digits. Luckily this happens in order, so we can simply pick the `n`th one.

Edit: @Mauris squeezed out 2 bytes. Thanks!

# Answer
> 5 votes
# C (function), 51

Recursive function takes input integer as a parameter:

```
f(n){n>>4?f(n>>4):0;n&=15;n+=n>9?55:48;putchar(n);}

```

### Test driver:

```
#include <stdio.h>

f(n){if(n>>4)f(n>>4);n&=15;n+=n<10?48:55;putchar(n);}

int main (int argc, char **argv) {

    f(15);puts("");
    f(1000);puts("");
    f(256);puts("");
    f(0);puts("");

    return 0;
}

```

# Answer
> 4 votes
# dc, 37

```
?[16~rd0<m]dsmxk[A~r17*+48+Pz0<p]dspx

```

Recursively divmods by 16, pushing the remainder to the stack until nothing left to divide. Then print each element of the stack, using divmod by 10 to achieve A-F digits. Probably more detail tomorrow... (and hopefully less bytes).

# Answer
> 4 votes
# C (gcc), ~~45~~ 44 bytes

```
f(n){n&&f(n/16);n%=16;putchar(n+48+n/10*7);}

```

Try it online!

# Answer
> 3 votes
# Bash (function), 62

Thanks to @manatwork for suggesting using recursion.

```
h()(x=({0..9} {A..F})
echo `(($1>15))&&h $[$1/16]`${x[$1%16]})

```

# Answer
> 3 votes
# Perl 6,  ~~53~~  48 bytes

```
~~{[R~] (0..9,'A'..'F').flat[($_,*div 16...^0)X%16]||0}~~
{[R~] (0..9,'A'..'F').flat[.polymod(16 xx*)]||0}
```

This creates a sequence of values that are Integer divided (`div`), until the result is `0` excluding the `0` from the sequence

```
$_, * div 16 ...^ 0

```

It then crosses (`X`) that sequence using the modulus operator (`%`) with `16`

```
( … ) X[%] 16

```

It uses those values as indexes into a flattened list consisting of two Ranges `0..9` and `'A'..'Z'`

```
( 0 .. 9, 'A' .. 'Z' ).flat[ … ]

```

Finally it concatenates (`~`) them using the reverse (`R`) meta operator

```
[R[~]] …

```

If that results in a False value (empty string), return `0`

```
… || 0

```

---

Usage:

```
# (optional) give it a lexical name for ease of use
my &code = { … }

say <15 1000 256 0>.map: &code;
# (F 3E8 100 0)

say code 10¹⁰⁰;
# 1249AD2594C37CEB0B2784C4CE0BF38ACE408E211A7CAAB24308A82E8F10000000000000000000000000

```

# Answer
> 2 votes
# MATL, 27 bytes

```
i`16H#\wt9>?7+]wt]xN$hP48+c

```

This uses release 5.1.0 of the language/compiler, which is earlier than this challenge.

### Example

```
>> matl
 > i`16H#\wt9>?7+]wt]xN$hP48+c
 >
> 1000
3E8

```

### Explanation

```
i              % input number
`              % do...
  16H#\        % remainder and quotient of division by 16
  w            % move remainder to top of stack
  t9>          % does it exceed 9?
  ?            % if so
    7+         % add 7 (for letter ASCII code)
  ]            % end if
  w            % move quotient back to the top
  t            % duplicate
]              % ...while (duplicated) quotient is not zero
x              % delete last quotient (zero)
N$h            % create vector of all remainders
P              % flip vector
48+c           % add 48 and convert to char (will be implicitly displayed)

```

# Answer
> 2 votes
# , 31 chars / 62 bytes

```
↺a=⬯;ï;ï≫4@a=⩥ḊĀⒸª⩥⁽ṁṇ⸩⨝[ï%Ḑ]+a

```

`Try it here (Firefox only).`

Okay, I figured out some more stuff that golfed it down.

# Explanation

It's essentially the same solution as @SuperJedi224's ES6 solution - but with something different.

See `⩥ḊĀⒸª⩥⁽ṁṇ⸩⨝`? That's a really fancy way of writing `"0123456789ABCDEF"`. `⩥Ḋ` creates a range from 0 to 10, `Ⓒª⩥⁽ṁṇ⸩` creates a range from 65 to 71 and converts it to a string of ASCII, and `Ā...⨝` concatenates the two ranges and joins them into one string. This was probably the coolest part of my solution.

# Bonus non-competitive version, 24 chars / 45 bytes

```
↺;ï;ï≫4@ᵴ=(⩥Ḋ⨝+ᶐ)[ï%Ḑ]+ᵴ

```

I decided to add an alphabet string, like in Pyth.

# Answer
> 2 votes
# sed, 341 bytes

```
:
s/\b/_/2
s/[13579]/&;/g
y/123456789/011223344/
s/;0/5/g
s/;1/6/g
s/;2/7/g
s/;3/8/g
s/;4/9/g
s/;_;_;_;_/=/
s/;_;_;__/+/
s/;_;__;_/:/
s/;_;___/>/
s/;__;_;_/</
s/;__;__/?/
s/;___;_/(/
s/;____/*/
s/_;_;_;_/-/
s/_;_;__/^/
s/_;__;_/%/
s/_;___/$/
s/__;_;_/#/
s/__;__/@/
s/___;_/!/
s/____/)/
/[1-9_]/b
y/)!@#$%^-*(?<>:+=/0123456789ABCDEF/
s/^0*//

```

It's not the obvious language for this challenge, but it does have the advantage of supporting input numbers up to (depending on your implementation) between 4000 digits and the limit of your system's available (virtual) memory. I converted RSA-1024 to hex in about 0.6 seconds, so it scales reasonably well.

It works using successive division by two, accumulating every 4 bits of carry into a hex digit. We use non-letter characters to represent our output, so that we always accumulate carry between the decimal input and the hex output, and convert to conventional hexadecimal at the very end.

# Answer
> 2 votes
# PHP, ~~65 66 64+1 62~~ 59 bytes

```
function h($n){$n&&h($n>>4);echo"0123456789abcdef"[$n&15];}

```

recursive printing function, prints a leading zero (insert `>16` before `&&` to remove it)

---

programs, 64 bytes +1 for `-R` (run as pipe with `-nR`)

```
for(;$n=&$argn;$n>>=4)$s="0123456789abcdef"[$n&15].$s;echo$s?:0;

```

requires PHP 5.6 or later (5.5 cannot index string literals)

or

```
for(;$n=&$argn;$n>>=4)$s=(abcdef[$n%16-10]?:$n%16).$s;echo$s?:0;

```

requires PHP 5.6 or 7.0 (7.1 understands negative string indexes)

---

Run as pipe with `-nR` or try them online.

# Answer
> 1 votes
# Javascript ES6, ~~64~~ 58 bytes

```
v=>eval('for(z="";v;v>>=4)z="0123456789ABCDEF"[v%16]+z')

```

Saved 6 bytes thanks to ןnɟuɐɯɹɐןoɯ and user81655.

# Answer
> 1 votes
# Julia, 55 bytes

```
h(n)=(n>15?h(n÷16):"")"0123456789ABCDEF"[(i=n%16+1):i]

```

This is the basic recursive function implementation. It accepts an integer and returns a string.

If the input is less than 15, floor divide it by 16 and recurse, otherwise take the empty string. Tack this onto the front of the appropriately selected hexadecimal character.

# Answer
> 1 votes
# Pyre, 98 bytes

Doing this in a language without arithmetic operators was probably a mistake.

```
let h=def (n)(if n.gt(15)h(n.div(16).int!)else "").concat("0123456789abcdef".list!.get(n.mod(16)))

```

Use like this:

```
do
  let h = ...
  print(h(15))
end

```

Ungolfed:

```
let h = def (n) do
    if n.gt(15)
        let x = h(n.div(16).int!)
    else
        let x = ""
    x.concat("0123456789abcdef".list!.get(n.mod(16)))
end

```

# Answer
> 1 votes
# Ruby, 48 characters

(Copy of Loovjo's Python answer.)

```
h=->n{(n>15?h[n/16]:'')+[*?0..?9,*?a..?f][n%16]}

```

Sample run:

```
2.1.5 :001 > h=->n{(n>15?h[n/16]:'')+[*?0..?9,*?a..?f][n%16]}
 => #<Proc:0x00000001404a38@(irb):1 (lambda)>
2.1.5 :002 > h[15]
 => "f"
2.1.5 :003 > h[1000]
 => "3e8"
2.1.5 :004 > h[256]
 => "100"

```

# Answer
> 1 votes
# Befunge-93, 58

```
&:88+%"0"+:"9"`7*+\8/2/:!#|_#
,_@                       >:#

```

First time doing a real golfing challenge in Befunge, I bet there's a one-liner for this that's shorter since all those spaces in the middle of the second line seem wasteful.

You can step through it here. Partial explanation:

`&`: Take input.

`:88+%`: Take the remainder modulo 16.

`"0"+`: Add it to the ASCII value of 0.

`:"9"``: If the result is greater than the ASCII value of 9...

`7*+`: Add 7 to convert it to a letter.

`\`: Save the resulting character on the stack.

`8/2/`: Divide by 16 rounding down.

`:!#|_`: Exit the loop if the result is 0.

`#`: Otherwise go back to the modulus step.

`>:#,_@` (wrapping around): Once finished, output the stack in LIFO order.

# Answer
> 1 votes
## Seriously, 35 bytes

```
,`;4ª@%)4ª@\`╬Xε D`@;7ªD+@9<7*+c+`n

```

Hex Dump:

```
2c603b34a640252934a6405c60ce58ee204460403b37a6442b40393c372a2b632b606e

```

Try It Online

Explanation:

```
,                                    Get evaluated input
 `          `╬                       Repeat the quoted function until top of stack is 0
  ;4ª@%                              Make a copy of the number mod 16
       )                             Send it to bottom of stack
        4ª@\                         Integer divide the original copy by 16
              X                      Delete the leftover zero. At this point the stack is
                                     the "digits" of the hex number from LSD to MSD
               ε                     Push empty string
                 D`              `n  Essentially fold the quoted function over the stack.
                   @;                Roll up the next lowest digit, make a copy
                     7ªD+            Add 48
                         @           Bring up the other copy
                          9<         1 if it's at least 10, else 0
                            7*       Multiply with 7.
                              +      Add. This will shift 58->65 and so on.
                               c     Convert to character.
                                +    Prepend to current string.

```

Note that the `;7ªD+@9<7*+c` is equivalent to `4ª▀E`, which would save 8 bytes, but I thought that perhaps a function that pushes the base b digits as a string might be considered too much of a "heaxadecimal built-in".

# Answer
> 1 votes
# \>\<\>, 46 + 3 = 49 bytes

This would have been shorter if \>\<\> had integer division, which we now have to emulate by subtracting modulo 1. Still, I think this uses some pretty neat wrapping around tricks!

```
>:?!v:f1+%:a(?v  v
\-%1:,+1f}+"0"<+7<
!?:r/ro;

```

Try it online!

## Explanation

**First loop**

```
>:?!v:f1+%:a(?v  v
\-%1:,+1f}+"0"<+7<

```

The first loop performs the classic converting to hex algorithm. It does modulo 16 (`:f1+%`) and checks if the result is \< 10 (`:a(?`). If it's not, we need to add 7 (`7+`) in order to go from the decimals to the capital alphabet in the ASCII table. Else, we can proceed by adding the ASCII value for 0 (`"0"+`) and shifting the character to be output to the bottom of the stack because we'll have to output them in reverse order. The top value is then replaced by its result of integer division by 16. This is emulated by computing *a/b - (a/b)%1* (`f1+,:1%-`). When the loop is finished, the stack contains the hexadecimal characters in reversed output order and a 0.

**Second loop**

```
!?:r<ro;

```

The second loop reverses the list and checks if top element is 0. If it is, we know all nonzero were printed and we should terminate. Else, we output the character and reverse the list again to prepare for the next iteration. The `:` when entering the second loop will duplicate the 0 which has no effect.

# Answer
> 0 votes
# SpecBAS - 110 bytes

```
1 h$="0123456789ABCDEF",r$=""
2 INPUT d
4 q=INT(d/16),r=d-(q*16),r$=h$(r+1)+r$,d=q
5 IF q>15 THEN 4
6  ?h$(q+1)+r$

```

This uses an algorithm I found on WikiHow (2nd method).

Strings in SpecBAS are 1-based, hence the `+1` to pick out the correct element.

# Answer
> 0 votes
# C (clang), 83 bytes

```
f(n){char h[8]={0};int i=8;while(i>0){h[i-1]=n%16;n/=16;printf("%x",h[8-i]);i--;}}

```

Try it online!

Alternate solution in C

# Answer
> 0 votes
# Ruby, 40 bytes

~~Stolen from~~ Inspired by manatwork's answer, but using an interesting loophole to make it shorter.

```
h=->n{(n>15?h[n/16]:'')+(n%16).to_s(17)}

```

# Answer
> 0 votes
## REXX, ~~80~~ 78 bytes

```
arg n
h=
do while n>0
  h=substr('0123456789ABCDEF',n//16+1,1)h
  n=n%16
  end
say h

```

# Answer
> 0 votes
# C, 48 bytes

```
h(x){x/16&&h(x/16);x%=16;putchar(x+=48+x/10*7);}

```

This is not completely original, I shaved 5 bytes off of the version Digital Trauma put up.

# Answer
> 0 votes
# APL(NARS), chars 34, bytes 68

```
{⍵≤0:,'0'⋄(∇⌊⍵÷16),(1+16∣⍵)⊃⎕D,⎕A}

```

test:

```
  g←{⍵≤0:,'0'⋄(∇⌊⍵÷16),(1+16∣⍵)⊃⎕D,⎕A}
  g 0
0
  g 100
064
  g 1000
03E8
  g 1
01

```

# Answer
> 0 votes
# Charcoal, 25 bytes

```
Ｎθ≔⁺⭆χι…α⁶ηＰ0Ｗθ«←§ηθ≧÷¹⁶θ

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ

```

Input the number.

```
≔⁺⭆χι…α⁶η

```

Create the string of hexadecimal digits by joining the range `0..9` with the first six letters.

```
Ｐ0

```

Output a zero in case the input is zero.

```
Ｗθ«

```

Repeat while the number is nonzero.

```
←§ηθ

```

Cyclically index into the hex digits and move the cursor to the left after printing.

```
≧÷¹⁶θ

```

Integer divide the number by 16.

# Answer
> 0 votes
# Retina 0.8.2, 56 bytes

```
.+
$*#;
+`(#+)\1{15}
$1;
(#{10})?(#*);
$1$.2
T`#d`_L`#+.

```

Try it online! Link includes test cases. Retina doesn't actually have a built-in for this anyway. Explanation:

```
.+
$*#;

```

Convert the input to unary using `#`s and append a `;`.

```
+`(#+)\1{15}
$1;

```

Keep trying to divide the input by 16, leaving the remainder after another `;`.

```
(#{10})?(#*);
$1$.2

```

Convert each remainder to base 10, but if it's 10 or more, then just convert the last digit, leaving the 10 `#`s behind.

```
T`#d`_L`#+.

```

Change the digits after `#`s from `0-5` to `A-F` and delete the `#`s.

---
Tags: code-golf, math, base-conversion, hexadecimal
---


# Question
Title: One Ring to rule them all. One String to contain them all
Objectives: Output a String which contains every positive integer strictly below 1000.

The obvious answer would be to concatenate every one of them, and that would create a String of 2890 characters (thanks manatwork), to avoid this kind of easy answer, the length of the string must be under 1500 characters. Here is a straightforward Java code which outputs a 1200 chars String.

```
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

import static org.junit.Assert.assertTrue;

/**
 * Created with IntelliJ IDEA.
 * User: fab
 * Date: 05/11/13
 * Time: 09:53
 * To change this template use File | Settings | File Templates.
 */
public class AStringToContainThemAll {

    @Test
    public void testsubStrings() throws Exception {
        String a = generateNewString();
        boolean cool = true;
        for (int i = 0; i < 1000; i++) {
            assertTrue(a.contains(Integer.toString(i)));
        }
    }

    private String generateNewString() {
        List<Integer> myTree = new ArrayList<Integer>();
        String finalString = new String("100");
        for (int i = 10; i < 1000; i++) {
            myTree.add(i);
        }
        while (myTree.size() > 0) {
            if (finalString.contains(Integer.toString(myTree.get(0)))) {
                myTree.remove(0);
            } else {
                String substringLong = finalString.substring(finalString.length() - 2, finalString.length());
                boolean found = false;
                loop:
                for (Integer integer : myTree) {
                    if (integer.toString().startsWith(substringLong) && !finalString.contains(integer.toString())) {
                        finalString = finalString.concat(integer.toString().substring(2, 3));
                        myTree.remove(integer);
                        found = true;
                        break loop;
                    }
                }
                if(! found){
                    finalString = finalString.concat(myTree.get(0).toString());
                    myTree.remove(0);
                }
            }

        }
        return finalString;
    }
}

```

Shortest code win, bonus point for the shortest String!

# Answer
> 20 votes
## Golfscript - 13 bytes, 1315 output

```
991,{`.$2>>},

```

The above selects those numbers from *0-990* whose first digit is the largest digit of the number, i.e. the last digit of the sorted string representation is lexicographically less than the string itself. The logic is the following:

For a 3 digit number *abc*, if *a* is not the largest digit of the number, the number my be skipped, because it will be covered by one of two cases later on:

1. ***b \< c*** (e.g. *123*)
Because *c* is the largest digit, the number *cab* will not be skipped. In this example *312* will not be skipped, nor will the next value *313*, which when concatenated (*312 313*) contains *123*.
2. ***b ≥ c*** (e.g. *132*)
Because *b* is the largest digit, the number *bca* will not be skipped. In this example *321* will not be skipped, nor will the next value *322*, which when concatenated (*321 322*) contains *132*. If *b = c* (e.g. *122*), this case also applies. The value *bca* will not be skipped, as before, and because *a* is necessarily less than *b*, *bc\<a+1\>* will not be skipped either. In this example, *221 222* contains *122*.

Because the above code tests the third digit, rather than strictly the last, all values from *0-99* are included in the result. The values from *1-99* may be skipped, however, because if every 3-digit sequence is present, then every 1-digit and 2-digit sequence must also be present.

The values from *991-999* may also be skipped, as the are generated by (*909 910*, *919 920*, ... *989 990*).

At 1315 bytes of output, this is comfortably under the problem's specification of less than 1500.

Output:

```
0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

```

### Variation #1

**14 bytes, 1233 output**

```
991,{`.$-1>>},

```

By selecting strictly the last digit for comparison, rather than the third, many of the unnecessary values less than *100* are eliminated, shortening the resulting string.

```
101120212230313233404142434450515253545560616263646566707172737475767780818283848586878890919293949596979899100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

```

### Variation #2

**16 bytes, 1127 output**

```
991,99>{`.$2>>},

```

By prying off all values less than *99* beforehand, the resulting string can be shortened even more.

```
99100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

```

---

## Golfscript - 19 bytes, 1016 output

```
910,99>{`.2$\?)>+}/

```

The above counts from *99* to *909*, adding any value that hasn't already appeared (*909* would normally be the last value added in this way). Moving *99* to the front is an optimization to avoid needing *910* at the back.

Output:

```
99100101102103104105106107108109111112113114115116117118119120122123124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190192193194195196197198199200202203204205206207208209222223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333334335336337338339340344345346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390394395396397398399400404405406407408409444445446447448449450455456457458459460465466467468469470475476477478479480485486487488489490495496497498499500505506507508509555556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666667668669670677678679680687688689690697698699700707708709777778779780788789790798799800808809888889890899900909

```

---

## Golfscript 26 bytes, 999 output

```
909.,99>{`..$.2><3$@?+>+}/

```

Note that the *1016* character string produced by the previous solution is nearly optimal, except for having two extra digits for each multiple of *111* (i.e. `11111` instead of `111`, `22222` instead of `222`, etc.). The solution can be made optimal by removing these extra digits (only inserting one digit at each of these values, instead of three), and by rotating `909` to the front, eliminating a `9` (this differs from the previous versions, which moved `9100` to the back instead).

Unrolled and commented:

```
909.,99>  # add 909 to the stack, and duplicate
          # create an array from 0..908, and
          # remove the first 99 elements (99..908)
{
  `..     # stringify, duplicate twice

  $.2><   # non-divisibility by 111 check
          # true if the last char of the sorted
          # string is greater than the first char

  3$@?    # first position of this number in
          # the total string so far (-1 if not found)

  +>      # add the two previous results,
          # and slice from that point
          # (see explanation below)

  +       # concat what remains to the total string

}/        # loop over the set

```

The logic to choose which characters are appended follows three cases:

1. ***111**n*, *n**s***
The value from the first check is *1*, and from the second *-1*.
The slice will begin starting from index *0*; it will return the whole string.
2. ***111**n*, *n**s***
The value from the first check is *1*, and from the second something *≥ 2*.
The slice will begin staring from index *≥ 3*; it will return an empty string.
3. ***111**n*, *n**s***
The value from the first check is *0*, and from the second *-1*.
The slice will begin starting from index *-1*; it will return the last character only.

The sum of the logic is that any value which hasn't yet appeared will be appended in whole - unless it is a multiple of *111*, in which case only one character will be appended. All other values will be ignored.

Note that the string produced is different than the optimal one produced by Peter Taylor's answer.

History:

```
899,{101+.111%{`.2$\?0<*}{3/9%}if+}/

899,{101+`.2$\?0<\.~111%2*)<*+}/0

899,{101+`.2$\?0<\..2>-!2*>*+}/0

899,{101+`...2>|,1|<2$@?0<*+}/0

999,{`..$.2>>2*>2$@?0<*+}/3>0

899,{101+`..$.2><3$@?+>+}/0

```

Output:

```
909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900

```

# Answer
> 46 votes
## GolfScript (35 31 26 chars)

```
10,{:x),{:&x=x+,{x&@}/}/}/

```

Output is

```
000100110111200201210211220221222300301302310311312320321322330331332333400401402403410411412413420421422423430431432433440441442443444500501502503504510511512513514520521522523524530531532533534540541542543544550551552553554555600601602603604605610611612613614615620621622623624625630631632633634635640641642643644645650651652653654655660661662663664665666700701702703704705706710711712713714715716720721722723724725726730731732733734735736740741742743744745746750751752753754755756760761762763764765766770771772773774775776777800801802803804805806807810811812813814815816817820821822823824825826827830831832833834835836837840841842843844845846847850851852853854855856857860861862863864865866867870871872873874875876877880881882883884885886887888900901902903904905906907908910911912913914915916917918920921922923924925926927928930931932933934935936937938940941942943944945946947948950951952953954955956957958960961962963964965966967968970971972973974975976977978980981982983984985986987988990991992993994995996997998999

```

(1020 chars) This is a variant on the Lyndon word concatenation approach: rather than use the primitive 1-char words it uses multiples of 111 for shorter code but repeated occurrences of those numbers; and rather than use minimal elements of the conjugacy groups it uses maximal elements, because that shortens the loops.

---

```
10,:^{:x^>{x.@:&<+^>{.x>{x&@}*}/}/}%3>0.

```

at 40 chars (can probably still be improved) generates an optimal string, which is of length 999 chars:

```
100200300400500600700800901101201301401501601701801902102202302402502602702802903103203303403503603703803904104204304404504604704804905105205305405505605705805906106206306406506606706806907107207307407507607707807908108208308408508608708808909109209309409509609709809911121131141151161171181191221231241251261271281291321331341351361371381391421431441451461471481491521531541551561571581591621631641651661671681691721731741751761771781791821831841851861871881891921931941951961971981992223224225226227228229233234235236237238239243244245246247248249253254255256257258259263264265266267268269273274275276277278279283284285286287288289293294295296297298299333433533633733833934434534634734834935435535635735835936436536636736836937437537637737837938438538638738838939439539639739839944454464474484494554564574584594654664674684694754764774784794854864874884894954964974984995556557558559566567568569576577578579586587588589596597598599666766866967767867968768868969769869977787797887897987998889899900

```

Trying to make this do reverse strings runs into problems with omitting the multiples of 111.

To see that 999 is the optimal length (since my brief comments above don't convince everyone), start from the full de Bruijn sequence which (taken as a cyclic string) contains every 3-digit sequence of characters from 0 to 9. Since there are 1000 of them, it must be at least 1000 characters long; that it can be precisely 1000 characters long is usually proven by an Eulerian walk on a graph whose nodes are two-digit sequences `xy` with 10 edges, each labelled with one digit `z`, which take `xy` to `yz`.

We don't need sequences beginning `0`, so given a de Bruijn sequence we can rotate to put `000` at the end. Then we don't need either of the sequences which wrap round to the beginning, but we do need two of the `0`s to finish the sequence starting with the digit before `000`, so we can delete one of them to get a 999-character string. Every remaining `0` is used in a number which doesn't begin with `0`.

# Answer
> 30 votes
### GolfScript, 17 characters

```
999,{`1$1$?0<*+}/

```

Plain approach to add each number if not already present in the string (note: 999 is not checked or added, but contained already in the output).

Output is 1133 characters:

```
01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

```

# Answer
> 22 votes
I don't have any code, but I thought someone might appreciate this intuitive proof that 999 characters is the lower bound to the length of the output:

First, every 1- and 2-digit number is part of a 3-digit number, so ignore everything less than 100. 100-999 inclusive is 900 3-digit numbers.

The most optimal way to solve the problem is if every character is used as much as possible. That means the numbers overlap as much as possible, like this:

```
123
 234
  345

```

The first number will therefore add 3 characters, and each subsequent number will add 1 character. That gives 3 + 899 = 902 characters as a lower bound.

However, when there is a zero, we can't use it to start a new 3-digit number. We can reuse it in the middle of another 3-digit number though, as long as it is not followed by another zero:

```
120
 203  <- Ok.
  034 <- not a number 100-999.

```

But:

```
100
 002  <- not a number 100-999.
  023 <- not a number 100-999.

```

Therefore, each zero which appears in the output extends the output by 1 character - except for the last two characters which may be zero as they do not overlap any further numbers:

```
???
 ??0
  ?00

```

There are 81 numbers with strictly one zero in the middle (?0?), 81 with strictly one zero at the end (??0), and 9 with two zeros (?00).

Every ??0 number can share a zero with either a ?0? number or a ?00 number, but not both. ?0? and ?00 can never share zeros, so there must be at least 81 + 9\*2 zeros in the output.

This gives a lower bound of 3 + 899 + 81 + 9\*2 - 2 = 999 characters.

Apologies if this is considered off-topic, but it was too long to fit in a comment.

# Answer
> 18 votes
## Perl, ~~37 34 33~~ 32 (~~1136~~ 1132 characters)

```
for$@(1..999){$_.=$@x!/$@/}print

```

~~for$@(1..999){$\_.=$@if!/$@/}print~~

~~for$i(1..999){$\_.=$i if!/$i/}print~~

~~for(1..1e3){$s.=$\_ if$s!~/$\_/}print$s~~

Outputs:

```
12345678910111314151617181920212224252627282930323335363738394043444647484950545557585960656668697076777980878890991001021031041051061071081091101121141151161171181191201241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901931941951961971981992002032042052062072082092192202212232252262272282292302312352362372382392402432442452462472482492502532542552562572582592602632642652662672682692702732742752762772782792802832842852862872882892902942952962972982993003043053063073083093113293303323343363373383393403423463473483493503543553563573583593603643653663673683693703743753763773783793803843853863873883893903953963973983994004054064074084094224394404434454474484494504534574584594604654664674684694704754764774784794804854864874884894904964974984995005065075085095335495505545565585595605645685695705765775785795805865875885895905975985996006076086096446596606656676696706756796806876886896906986997007087097557697707767787807867907977998008098668778798808878888978988999009089329439549659769799879891000

```

### Shorter string: ~~38 37~~ 34 (1020 characters):

```
$_.=$@x!/$@/while$@=--$@%1e3;print

```

~~for($@=1e3;$@--;){$\_.=$@if!/$@/}print~~

~~for($i=1e3;$i--;){$\_.=$i if!/$i/}print~~

Outputs:

```
999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

```

Still not happy with the duplication especially the 99999 at the beginning! I think many more checks would create a lot more code though...

Edit: Added suggestion from @Peter Taylor

Edit 2: Some great suggestions from @primo! Thank you

# Answer
> 11 votes
## APL (20, output: 1020)

```
{∨/⍺⍷⍵:⍵⋄⍵,⍺}/⍕¨⍳999

```

Explanation:

* `{∨/⍺⍷⍵:⍵⋄⍵,⍺}`: if  is a substring of , return , else return `⍵,⍺`
* `/`: reduce over
* `⍕¨`: the string representation of each of
* `⍳999`: the integers from `1` to `999`.

Output:

```
9999989979969959949939929919909889879869859849839829819809789779769759749739729719709689679669659649639629619609589579569
      55954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913
      91291191090890790690590490390290190088888788688588488388288188087787687587487387287187086786686586486386286186085785
      68558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108
      07806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735
      73473373273173072672572472372272172071671571471371271171070670570470370270170066666566466366266166065565465365265165
      06456446436426416406356346336326316306256246236226216206156146136126116106056046036026016005555545535525515505445435
      42541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411
      410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

```

## APL (41, output: 999)

```
'0',⍨⊃{⍵,⍺⍴⍨(1=⍴∪⍺)∨3×~∨/⍺⍷⍵}/⌽⍕¨100+⍳898

```

Explanation:

* `⌽⍕¨100+⍳898`: `('999' '998' ... '101')` (in reverse order, because reduction goes right to left in APL, i.e. `F/a b c ≡ a F (b F c)`)
* `/`: reduce
* `⍵,⍺⍴⍨`: right argument, followed by the first `N` characters of the left argument, where `N` is:
* `3×~∨/⍺⍷⍵`: `3` if  is not a substring of , otherwise `0`
* `(1=⍴∪⍺)`: `1` if  only has one unique characcter, otherwise `0`
* : greatest common divisor of the previous two values, so: `1` if  is not already in  and only has one unique character, `3` if  is not already in  but has more than one unique character, `0` otherwise.
* `'0',⍨`: add a zero to the end of the result

Output:

```
10110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451
      46147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188
      18919019219319419519619719819920020220320420520620720820922232242252262272282292302332342352362372382392402432442452
      46247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294
      29529629729829930030330430530630730830933343353363373383393403443453463473483493503543553563573583593603643653663673
      68369370374375376377378379380384385386387388389390394395396397398399400404405406407408409444544644744844945045545645
      74584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566
      56756856957057657757857958058658758858959059659759859960060660760860966676686696706776786796806876886896906976986997
      00707708709777877978078878979079879980080880988898908999009099100

```

# Answer
> 9 votes
# Ruby: ~~50~~ 46 characters (1020 characters output)

```
s=""
999.downto(0){|i|s[n=i.to_s]||s+=n}
$><<s

```

Sample run:

```
bash-4.1$ ruby -e 's="";999.downto(0){|i|s[n=i.to_s]||s+=n};$><<s'
999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

```

Test run:

```
bash-4.1$ ruby -e 's="";999.downto(0){|i|s[n=i.to_s]||s+=n};$><<s' | ruby -ne 'p (0..999).reject{|i|$_[i.to_s]}'
[]

```

## Ruby: ~~102~~ 97 characters (999 characters output)

```
s=""
999.downto(0){|i|s[n=i.to_s]||[2,1].map{|j|n[0,j]==s[-j,j]&&s+=n[j,9]and break}&&s+=n}
$><<s

```

Sample run:

```
bash-4.1$ ruby -e 's="";999.downto(0){|i|s[n=i.to_s]||[2,1].map{|j|n[0,j]==s[-j,j]&&s+=n[j,9]and break}&&s+=n};$><<s'
999899799699599499399299199098898798698598498398298198097897797697597497397297197096896796696596496396296196095895795695595495395295195094894794694594494394294194093893793693593493393293193092892792692592492392292192091891791691591491391291191090890790690590490390290190088878868858848838828818808778768758748738728718708678668658648638628618608578568558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108078068058048038028018007776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666566466366266166065565465365265165064564464364264164063563463363263163062562462362262162061561461361261161060560460360260160055545535525515505445435425415405345335325315305245235225215205145135125115105045035025015004443442441440433432431430423422421420413412411410403402401400333233133032232132031231131030230130022212202112102012001110100

```

Test run:

```
bash-4.1$ ruby -e 's="";999.downto(0){|i|s[n=i.to_s]||[2,1].map{|j|n[0,j]==s[-j,j]&&s+=n[j,9]and break}&&s+=n};$><<s' | ruby -ne 'p (0..999).reject{|i|$_[i.to_s]}'
[]

```

# Answer
> 6 votes
# Mathematica (~~62~~ 64 chars, 1002 output)

Because this makes use of a native function, I appreciate all the more the beauty of shorter solutions from scratch. Output is 1002 chars long.

```
<< Combinatorica`
"79" <> DeBruijnSequence["0"~CharacterRange~"9", 3]

"799798787770760750740730720710980970960950940930920910108908708608508408308208889998988081009909008007006005004003002000190180170160150140130120119118117116115114113112912812712612512412312213913813713613513413313214914814714614514414314215915815715615515415315216916816716616516416316217917817717617517417317218918818718618518418318219919819719619519419319212111029028027026025024023022922822722622522422392382372362352342332492482472462452442432592582572562552542532692682672662652642632792782772762752742732892882872862852842832992982972962952942932322202103903803703603503403393383373363353349348347346345344359358357356355354369368367366365364379378377376375374389388387386385384399398397396395394343330320310490480470460450449448447446445945845745645546946846746646547947847747647548948848748648549949849749649545444043042041059058057056055955855755695685675665795785775765895885875865995985975965655505405305205106906806706696686679678677689688687699698697676660650640630620610790780779778978879"

```

# Answer
> 6 votes
# JavaScript, 39

```
for(k=i="999";~k.indexOf(--i)?i:k+=i;);

```

1020 character output:

```
999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

```

Verification: `for(i=0;i<1000;i++)console.assert(k.indexOf(i)>=0)`

# Answer
> 5 votes
# Mathematica, 51 chars

```
""<>Table[ToString/@({i,j,k}-1),{i,10},{j,i},{k,i}]

```

Output(1155 chars):

```
000100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999

```

# Answer
> 5 votes
# Python - 53 ~~63~~, 1134 output

This is pretty brute forcish, but it is valid. Yes it has a leading zero, but it saves two characters by not having `range(1,1000)`.

```
s=''
for i in range(1e3):s+=`i`*(not`i`in s)
print s

```

The above throws a `DeprecationWarning` over the use of 1e3 in the `range()` call, but it saves a character over using 1000.

There is a slightly more optimal length output version as well, by reversing the string at the cost of ~~6~~ 5 characters **(thanks to r.e.s and filmor for the tips)**:

# Python - 58, 1021 output

```
s=''
for i in range(999,9,-1):s+=`i`*(not`i`in s)
print s

```

# Answer
> 3 votes
# Java-~~126~~ 98 chars (Java 6)

```
class b{static{String s="";for(int a=999;a>0;a--)s=s.contains(""+a)?s:s+a;System.out.println(s);}}

```

Output (1020 chars):

```
999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

```

Can reach a good (according to Peter Taylor, but later he said 999 was optimal) String length by adding a few chars (+20 chars for ~~147~~ 118):

```
class b{static{String s="";for(int a=999;a>0;a--)s=s.contains(""+a)?s:(a+1)%111==0?s+a%10:s+a;System.out.println(s);}}

```

Output (1002 chars):

```
999899799699599499399299199098898798698598498398298198097897797697597497397297197096896796696596496396296196095895795695595495395295195094894794694594494394294194093893793693593493393293193092892792692592492392292192091891791691591491391291191090890790690590490390290190088878868858848838828818808778768758748738728718708678668658648638628618608578568558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108078068058048038028018007776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666566466366266166065565465365265165064564464364264164063563463363263163062562462362262162061561461361261161060560460360260160055545535525515505445435425415405345335325315305245235225215205145135125115105045035025015004443442441440433432431430423422421420413412411410403402401400333233133032232132031231131030230130022212202112102012001110101100

```

**Edit**: Thanks to Fabinout for pointing out that Java 6 can save 28 chars.

# Answer
> 2 votes
# Haskell, 75 bytes - 1002 output

A sieve approach that returns a minimal solution.

```
(\n->head.filter(\s->and[show k`isInfixOf`s|k<-[1..n]]).map show$[1..])1000

```

Note that this solution is impractically slow.

# Answer
> 2 votes
# K, 33

```
{$[#ss[x]@y;x;,/x,y]}/["";$!1000]

```

Basically the same as Howards solution - 1133 characters.

```
01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

```

# Answer
> 2 votes
## Windows PowerShell - 40, 1020 Output

```
999..0|%{$s+=if(!($s-match$_)){"$_"}};$s

```

Output:

```
999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

```

# Answer
> 2 votes
## Pyke, 13 bytes (noncompeting), string length 1133

Pyke is newer than the challenge and thus is noncompetitive .

```
k~mV~oi{!o`*+

```

Try it here!

```
              - o = 0
k~mV          - repeat 1000 times, i = ""
    ~oi{      -     str(o) in i
        !     -    not ^
         o`*  -   str(o++) * ^
            + -  i += ^

```

# Answer
> 2 votes
# Powershell, 36 bytes, 1020 output

```
999..9|%{$s+=(,"$_")[$s-match$_]};$s

```

Output:

```
999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

```

## Alternative, 69 bytes, 1000 output

```
999..9|%{$s+=("$_",($x="$_"[-1]))[2*($s-match$_)+($s+$x-match$_)]};$s

```

Output:

```
9998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888788688588488388288188087787687587487387287187086786686586486386286186085785685585485385285185084784684584484384284184083783683583483383283183082782682582482382282182081781681581481381281181080780680580480380280180077767757747737727717707667657647637627617607567557547537527517507467457447437427417407367357347337327317307267257247237227217207167157147137127117107067057047037027017006665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555455355255155054454354254154053453353253153052452352252152051451351251151050450350250150044434424414404334324314304234224214204134124114104034024014003332331330322321320312311310302301300222122021121020120011101100

```

## Alternative, ~~82~~ 73 bytes, 999 output (minimum)

```
for(;$z=9..0|?{"000$x"-notmatch-join"$x$_"[-3..-1]}|%{"$_"}){$x+=$z[0]}$x

```

This is simplified algorithm from Generate the shortest De Bruijn adapted for constants: alphabet=`9876543210` and length=`3`

Output:

```
999899799699599499399299199098898798698598498398298198097897797697597497397297197096896796696596496396296196095895795695595495395295195094894794694594494394294194093893793693593493393293193092892792692592492392292192091891791691591491391291191090890790690590490390290190088878868858848838828818808778768758748738728718708678668658648638628618608578568558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108078068058048038028018007776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666566466366266166065565465365265165064564464364264164063563463363263163062562462362262162061561461361261161060560460360260160055545535525515505445435425415405345335325315305245235225215205145135125115105045035025015004443442441440433432431430423422421420413412411410403402401400333233133032232132031231131030230130022212202112102012001110100

```

---

Test script:

```
$f= {

#999..0|%{$s+=if(!($s-match$_)){"$_"}};$s

#999..9|%{$s+=("$_",($x="$_"[-1]))[2*($s-match$_)+($s+$x-match$_)]};$s-replace'1100','100'
#999..9|%{$s+=("$_",($x="$_"[-1]))[2*($s-match$_)+($s+$x-match$_)]};$s
#999..9|%{$s+=(,"$_")[$s-match$_]};$s-replace'(.)\1{3,}','$1$1$1'
#999..9|%{$s+=(,"$_")[$s-match$_]};$s-replace'(.)\1{3,}','$1$1$1'-replace'1100','0'
 for(;$z=9..0|?{"000$x"-notmatch-join"$x$_"[-3..-1]}|%{"$_"}){$x+=$z[0]}$x
#999..9|%{$s+=(,"$_")[$s-match$_]};$s

}

$s=&$f

$s
"Length:"
$s.Length
"count(###)!=1:"
$x=@{}
0..($s.Length-3)|%{$s.Substring($_,3)}|Group|%{
    $x[+$_.Name]=$_.Count
}
100..999|?{$x.$_-ne1}|%{,($_,+$x.$_)}|%{"$_"}
"count(##)!=10:"
$x=@{}
0..($s.Length-2)|%{$s.Substring($_,2)}|Group|%{
    $x[+$_.Name]=$_.Count
}
10..99|?{$x.$_-ne10}|%{,($_,+$x.$_)}|%{"$_"}
"count(#)!=100:"
$x=@{}
0..($s.Length-1)|%{$s.Substring($_,1)}|Group|%{
    $x[+$_.Name]=$_.Count
}
0..9|?{$x.$_-ne100}|%{,($_,+$x.$_)}|%{"$_"}
"All numbers:"
999-eq(1..999|?{$s-match$_}).Count

```

# Answer
> 2 votes
# 05AB1E, 9 bytes and 1109 characters

```
₄FDNå_iNì

```

Outputs:

```
90990190089989088981980980880079979879078978878077977870970870770069969869769068968868768067967867767066966866760960860760660059959859759659058958858758658057957857757657056956856756656055955855755650950850750650550049949849749649549048948848748648548047947847747647547046946846746646546045945845745645545044944844744644540940840740640540440039939839739639539439038938838738638538438037937837737637537437036936836736636536436035935835735635535435034934834734634534434033933833733633533430930830730630530430330029929829729629529429329028928828728628528428328027927827727627527427327026926826726626526426326025925825725625525425325024924824724624524424324023923823723623523423323022922822722622522422320920820720620520420320220019919719619519419319219118918818718618518418318218017917817717617517417317217016916816716616516416316216015915815715615515415315215014914814714614514414314214013913813713613513413313213012912812712612512412312212011811711611511411311211110910810710610510410310210110099919089888079787770696867666059585756555049484746454440393837363534333029282726252423222018171615141312119876543210

```

Try it online or verify it contains all numbers below 1000.

**Explanation:**

```
₄            # Push 1000
 F           # Loop N in the range [0,1000):
  D          #  Duplicate the top value on the stack
   Nå_i      #  If it does not contain N as substring yet:
       Nì    #   Prepend N to it
             # (Output implicitly after the loop)

```

# Answer
> 1 votes
# PHP, ~~48~~ 44 bytes

Thanks to @primo for reminding me of `ereg`.

```
for($i=1e3;--$i;ereg($i,$s)?:$s.=$i);echo$s;

```

or

```
for($i=1e3;ereg(--$i,$s)?$i:$s.=$i;);echo$s;

```

output: 1020 chars. requires PHP\<7

## PHP 7, 48 bytes:

`ereg` has been removed in PHP 7

```
for($i=1e3;--$i;strstr($s,"$i")?:$s.=$i);echo$s;

```

If the second argument to `strstr` (or `strpos` and other string searching functions) is not a string, it will be used as an ascii code, so `$i` needs a cast to string.

# Answer
> 1 votes
# Groovy, 49 chars/bytes

I wasn't sure whether to do this as a function returning a string variable, or print out the result, so this just prints it to stdout. Using the regex matcher saved 2 bytes, using ternary operator instead of "if" saved another byte. The output string is 1133 characters.

```
a='';1000.times{a+=(a==~/.*$it.*/)?'':it};print a

```

Output:

```
01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

```

# Answer
> 0 votes
# Game Maker Language, 1014 - String 1000

`show_message(909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900)`

Also:

## Ruby, 1003 - String 1000

`p'909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900'`

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


# Question
Title: 0xDEADBEEF is not tasty, but still 0xFEEDBEEF
*Inspired by "You had me at hello"*

# Introduction

For those who don't know, hexadecimal is a base system like decimal. Contrary to decimal however, it uses 16 (hence the name) digits instead of 10.

Here are the first few numbers while counting up in hexadecimal to maybe give you a feel of things, although you should probably google it for more info.

`0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 1A, 1B, 1C, 1D, 1E, 1F, 20...`

From now on I'll refer to hexadecimal as hex.

---

# Challenge

Take a possibly infinite stream of bytes, and convert it to hex. This should be done as you read since you might get an infinite stream and keep on reading forever.

The twist, is that if a sequence of converted numbers equals the exact hex number `DEADBEEF` (3735928559 in decimal), you must output `FEEDBEEF` (4276993775 in decimal) instead.

If no `DEADBEEF` is found, print the string as it was

Inter-character matches work too, so `2D EA DB EE F0` works and should be converted to `2F EE DB EE F`

---

# Example

This might seem a bit vague, so here are 2 step-by-step examples.

### Example 1

Input: `Hello, World` (bytes represented as string)

> Step 1: Convert the input to ASCII: `072 101 108 108 111 044 032 087 111 114 108 100`
>
> Step 2: Convert the ASCII to hex: `48 65 6C 6C 6F 2C 20 57 6F 72 6C 64`
>
> Step 3: Print out everything until `DEADBEEF` is found. It wasn't found, so just print `Hello, World` again.

### Example 2

Input: `Hello,Þ¾ï,,`

> Step 1: Convert to ASCII: `72 101 108 108 111 44 222 173 190 239 44 44`
>
> Step 2: Convert to hex: `48 65 6C 6C 6F 2C DE AD BE EF 2C 2C`
>
> Step 3: Is there `DEADBEEF`? Yep. so take everything up to it. `48 65 6C 6C 6F 2C`
>
> Step 4: Append `FEEDBEEF` to it. `48 65 6C 6C 6F 2C FE ED BE EF`
>
> Step 5: Convert back to a string and print it. Output is `Hello,þí¾ï`

---

# Scoring

Try to make a program that does the above in the **fewest bytes of source code as possible**.

---

# Remember!

Make sure your program works for finite and infinite streams. The stream can be STDIN, file, function argument (if you can pass streams as arguments), or your language's closest alternative. Output is to STDOUT or function returning (if you can return streams).

# More test cases (contain invisible characters)

`eeþí¾Þ¾ïe (6565feedbedeadbeef65) -> eeþí¾þí¾ïe`
`Þ¾ï (deadbeef)-> þí¾ï`
`Þ=êÛîôV -> Þ?îÛîôV`

# Answer
# Python 3, 121 bytes

```
I=open(0).read
p=print
x=i=I(1)
while i:p(end=x[:-4]);x=x[-4:];x!='Þ¾ï'or+p(end='þí¾ï');i=I(1);x+=i
p(end=x[:5])

```

Try it online!
> 2 votes

# Answer
# Japt, ~~34~~ 30 bytes

*-4 bytes from @Shagy*

```
csG r`Ü%¼ef.+``fe‚¼ef` ò ®nG d

```

Try it online!
> 1 votes

# Answer
# Clean, 143 bytes

*uses octal escapes here and on TIO to prevent UTF-8 mangling, but it does work with the actual values and so each escape sequence is counted as one byte*

This one works with inter-character sequences.

```
import StdEnv
$l=:[a,'\352\333\356',b:t]|(toInt a)rem 16==13&&(toInt b)>>4==15=[a+'\002':['\356\333\356\015']]=[hd l: $(tl l)]
$['\336\255\276\357':_]=['\376\355\276\357']
$[h:t]=[h: $t]
$e=e

```

Try it online!

# Clean, 38 bytes

*uses octal escapes here and on TIO to prevent UTF-8 mangling, but it does work with the actual values and so each escape sequence is counted as one byte*

This one does not work with inter-character sequences.

```
$['\336\352\276\357':_]=['\376\355\276\357']
$[h:t]=[h: $t]
$e=e

```

Try it online!

Defines the function `$ :: [Char] -> [Char]` taking and returning a list of characters.
Since Clean is lazily-evaluated, this is equivalent to a stream.
> 1 votes

# Answer
# 05AB1E, 30 bytes

```
ÇhJl’–ìÀÜ’¡Dнsg1›’ŽåÀÜ’×«2ôHçJ

```

Try it online or verify a few more test cases.

**Explanation:**

```
Ç                               # Convert the (implicit) input-string to codepoint decimals
 h                              # Convert them to hexadecimal
  J                             # Join them together
   l                            # Convert to lowercase
    ’–ìÀÜ’                      # Push compressed string "deadbeef"
          ¡                     # Split the hexadecimal string by this "deadbeef"
           D                    # Duplicate
            н                   # Take the first item of the split-list
             s                  # Swap so the full list is at the top of the stack again
              g1›               # Check if its length is larger than 1
                 ’ŽåÀÜ’×«       # If it is: concat "feedbeef" to the head-string
                         2ô     # Split the string into parts of size 2
                           H    # Convert hexadecimal back to decimal
                            ç   # Decimal back to characters
                             J  # Join the characters (and output implicitly)

```

See this 05AB1E tips of mine (section *How to use the dictionary?*) to understand why `’–ìÀÜ’` is `"deadbeef"` and `’ŽåÀÜ’` is `"feedbeef"`.
> 0 votes

# Answer
# C (gcc), 137 bytes

```
i=16;n;long long u;c;R(k){u=u<<4|c>>k&15,u^=u+'!RA'<<32?0:' @';}main(){for(;n+=!!~(c=getchar(n-=!i&&~putchar(u>>32)));i/=2)R(4),R(0);}

```

Try it online!
> 0 votes

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


title: Repeat this GCD operation

text:
# Question
Title: Repeat this GCD operation
Problem A3 from the 2008 Putnam competition says:

> Start with a finite sequence \\$a\_1, a\_2, \dots, a\_n\\$ of positive integers. If possible, choose two indices \\$j \< k\\$ such that \\$a\_j\\$ does not divide \\$a\_k\\$, and replace \\$a\_j\\$ and \\$a\_k\\$ by \\$\gcd(a\_j, a\_k)\\$ and \\$\text{lcm}(a\_j, a\_k)\\$, respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made.

Your goal in this challenge is to take a finite sequence of positive integers as input, and output the result of repeating this process until no further progress is possible. (That is, until every number in the resulting sequence divides all the numbers that come after it.) You don't need to solve the Putnam problem.

This is : the shortest solution in every programming language wins.

## Test cases

```
[1, 2, 4, 8, 16, 32] => [1, 2, 4, 8, 16, 32]
[120, 24, 6, 2, 1, 1] => [1, 1, 2, 6, 24, 120]
[97, 41, 48, 12, 98, 68] => [1, 1, 2, 4, 12, 159016368]
[225, 36, 30, 1125, 36, 18, 180] => [3, 9, 18, 90, 180, 900, 4500]
[17, 17, 17, 17] => [17, 17, 17, 17]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => [1, 1, 1, 1, 1, 2, 2, 6, 60, 2520]

```

# Answer
> 14 votes
# Jelly, 9 bytes

```
ÆEz0Ṣ€ZÆẸ

```

Try it online!

### How it works

```
ÆEz0Ṣ€ZÆẸ  Main link. Argument: A (array)

ÆE         For each n in A, compute the exponents of n's prime factorization.
           E.g., 2000000 = 2⁷3⁰5⁶ gets mapped to [7, 0, 6].
  z0       Zip 0; append 0's to shorter exponent arrays to pad them to the same
           length, then read the resulting matrix by columns.
    Ṣ€     Sort the resulting arrays (exponents that correspond to the same prime).
      Z    Zip; read the resulting matrix by columns, re-grouping the exponents by
           the integers they represent.
       ÆẸ  Unexponents; map the exponent arrays back to integers.

```

# Answer
> 12 votes
# Pari/GP, 33 bytes

Calculate the elementary divisors of the diagonal matrix.

```
a->Vecrev(matsnf(matdiagonal(a)))

```

Try it online!

# Answer
> 5 votes
# , 17 bytes

```
/:~"1&.|:&.(_&q:)

```

Try it online!

Probably the first J answer on PPCG to use `&.` twice. After this and that, I'm starting to feel like a weird J hacker.

Basically a translation from Dennis' Jelly answer.

### How it works

```
/:~"1&.|:&.(_&q:)  Single monadic verb.
           (_&q:)  Convert each number to prime exponents
                   (automatically zero-filled to the right)
       |:&.        Transpose
/:~"1&.            Sort each row in increasing order
       |:&.        Transpose again (inverse of transpose == transpose)
           (_&q:)  Apply inverse of prime exponents; convert back to integers

```

# Answer
> 5 votes
# Wolfram Language (Mathematica), 44 bytes

```
Table[GCD@@LCM@@@#~Subsets~{i},{i,Tr[1^#]}]&

```

The \\$k\\$-th element of the result is the GCD of the LCM's of the subsets with \\$k\\$ elements.

\\$b\_k = \gcd(\\{\operatorname{lcm}(a\_{i\_1}, \cdots, a\_{i\_k}) | 1 \le i\_1 \< \cdots \< i\_k \le n\\})\\$

Try it online!

# Answer
> 5 votes
# Python 3, 103 bytes

```
import math
def f(a,i=0,j=-1):d=math.gcd(a[i],a[j]);a[j]*=a[i]//d;a[i]=d;a[i:j]and f(a,i,j-1)==f(a,i+1)

```

Try it online!

### Explanation

This problem is essentially a parallel sort on the prime factors, and (gcd(a,b), lcm(a,b)) is analogous to (min(a,b), max(a,b)). So let's talk in terms of sorting.

We will prove by induction that after f(i,j), a\[i\] becomes the smallest value in (the old value of) L, where L is the range between a\[i\] and a\[j\], including both ends. And if j = -1, f(i,j) will sort the range L.

The case when L contains one element is trivial. For the first claim, notice that the smallest of L can't stay in a\[j\] after the swap, so f(i,j-1) will put it in a\[i\], and f(i+1,-1) will not affect it.

For the second claim, note that a\[i\] is the smallest value, and f(i+1,-1) will sort the remaining values, so L becomes sorted after f(i,j).

# Answer
> 3 votes
# Retina, 65 bytes

```
\d+
*
+`\b((_+)(\2)+)\b(.*)\b(?!\1+\b)(\2+)\b
$2$4$5$#3*$5
_+
$.&

```

Try it online! Link includes the faster test cases. Explanation:

```
\d+
*

```

Convert to unary.

```
+`\b((_+)(\2)+)\b(.*)\b(?!\1+\b)(\2+)\b

```

Repeatedly match: any number with a factor, then a later number that is not divisible by the first number but is divisible by the factor.

```
$2$4$5$#3*$5

```

`$1` is the first number. `$2` is the factor. Because regex is greedy this is the largest factor i.e the gcd. `$4` is the part of the match between the original numbers. `$5` is the second number. `$#3` (in decimal rather than unary) is one less than `$1` divided by `$2`, since it doesn't include the original `$2`. This means that to calculate the lcm we need to multiply `$5` by one more than `$#3` which is most succintly written as the sum of `$5` and the product of `$#3` and `$5`.

```
_+
$.&

```

Convert to decimal.

# Answer
> 3 votes
# JavaScript (SpiderMonkey), 69 bytes

```
a=>a.map((q,i)=>a.map(l=(p,j)=>a[j]=j>i&&(t=p%q)?p/t*l(q,j,q=t):p)|q)

```

Try it online!

* Function `l` assign `lcm(p,q)` to `a[j]`, and assign `gcd(p, q)` to `q` if `j > i`, otherwise keeps everything unchanged.
    + `lcm(p,q) = if p%q=0 then p else p*lcm(q,p%q)/(p%q)`

---

Old answer:

# JavaScript (SpiderMonkey), 73 bytes

```
a=>a.map((u,i)=>a.map((v,j)=>i<j?a[j]*=u/(g=p=>p%u?g(u,u=p%u):u)(v):0)|u)

```

Try it online!

* Function `g` calculate `gcd(u, v)` and assign return value to `u`.

# Answer
> 3 votes
# 05AB1E, 10 bytes

Credit for the approach goes to alephalpha.

```
εIæN>ù€.¿¿

```

Try it online!

```
εIæN>ù€.¿¿     Full program. Takes a list from STDIN, outputs another one to STDOUT.
ε              Execute for each element of the input, with N as the index variable.
 Iæ            Powerset of the input.
   N>ù         Only keep the elements of length N+1.
      €.¿      LCM each.
         ¿     Take the GCD of LCMs.

```

# Answer
> 3 votes
# Perl 6, 53 bytes

```
{map {[gcd] map {[lcm] $_},.combinations: $^i},1..$_}

```

Try it online!

Port of alephalpha's Mathematica answer.

# Answer
> 2 votes
# 05AB1E, ~~15~~ ~~14~~ 13 bytes

```
Ó¾ζ€{øεgÅpymP

```

Port of *@Dennis♦*' Jelly answer, but unfortunately 05AB1E doesn't have an Unexponents-builtin, so that takes more than halve the program.. :(
-1 byte thanks to *@Mr.Xcoder*.
-1 byte thanks to *@Emigna*.

Try it online or verify all test cases.

**Explanation:**

```
Ó          # Prime exponents of the (implicit) input-list
 ¾ζ        # Zip, swapping rows and columns, with integer 0 as filler
   €{      # Sort each inner list
     ø     # Zip, swapping rows and columns again
ε          # Map each inner list:
 gÅp       #  Get the first `l` primes, where `l` is the size of the inner list
    ym     #  Take the power of the prime-list and inner list
      P    #  And then take the product of that result
           # (And output implicitly)

```

---
Tags: code-golf, array, number-theory
---


title: Find the minimal initial values

text:
# Question
Title: Find the minimal initial values
Consider a sequence `F` of positive integers where `F(n) = F(n-1) + F(n-2)` for `n >= 2`. The Fibonacci sequence is *almost* one example of this type of sequence for `F(0) = 0, F(1) = 1`, but it's excluded because of the positive integer requirement. Any two initial values will yield a different sequence. For example `F(0) = 3, F(1) = 1` produces these terms.

```
3, 1, 4, 5, 9, 14, 23, 37, 60, 97, ...

```

### Challenge

The task is to find `F(0)` and `F(1)` that minimize `F(0) + F(1)` given some term of a sequence `F(n)`. Write a function or complete program to complete the task.

### Input

Input is a single positive integer, `F(n)`. It may be accepted as a parameter or from standard input. Any reasonable representation is allowed, including direct integer or string representations.

Invalid inputs need not be considered.

### Output

The output will be two positive integers, `F(0)` and `F(1)`. Any reasonable format is acceptable. Here are some examples of reasonable formats.

* Written on separate lines to standard output
* Formatted on standard output as a delimited 2-element list
* Returned as a tuple or 2-element array of integers from a function

### Examples

```
60  -> [3, 1]
37  -> [3, 1]
13  -> [1, 1]
26  -> [2, 2]
4   -> [2, 1]
5   -> [1, 1]
6   -> [2, 2]
7   -> [2, 1]
12  -> [3, 2]
1   -> [1, 1]

```

### Scoring

This is code golf. The score is calculated by bytes of source code.

Sandbox

# Answer
# Jelly, 13 bytes

```
pWạ\Ṛ$</¿€SÞḢ

```

Try it online!

### How it works

```
pWạ\Ṛ$</¿€SÞḢ  Main link. Argument: n

 W             Wrap; yield [n].
p              Cartesian product; promote the left argument n to [1, ..., n] and take
               the product of [1, ..., n] and n, yielding [[1, n], ..., [n, n]].
         €     Map the link to the left over the pairs [k, n].
        ¿          While...
      </               reducing the pair by less-than yields 1:
  ạ\                       Cumulatively reduce the pair by absolute difference.
    Ṛ                      Reverse the result.
                   In essence, starting with [a, b] := [k, n], we keep executing
                   [a, b] := [b, |a - b|], until the pair is no longer increasing.
          SÞ   Sort the resulting pairs by their sums.
            Ḣ  Head; extract the first pair.

```
> 3 votes

# Answer
# Japt, 34 bytes

```

_Ì<U?[ZÌZx]gV:ZÌ
õ ïUõ)ñx æ_gV ¥U

```

Try it online!

The empty first line is important.

Explanation:

```
_                     Declare a function V:
 Ì<U?        :ZÌ        If the second number is >= n, return it
     [ZÌZx]gV           Otherwise call V again with the second number and the sum

õ ïUõ)                Get all pairs of positive integers where both are less than n
      ñx              Sort them by their sum
         æ_gV ¥U      Return the first (lowest sum) one where V returns n

```
> 2 votes

# Answer
# Perl 6, 52 bytes

```
->\n{(1..n X 1..n).max:{(n∈(|$_,*+*...*>n))/.sum}}

```

Try it online!

Brute-force solution.
> 1 votes

# Answer
# Haskell, ~~81~~ 80 bytes

```
f x=[(a,s-a)|s<-[2..],a<-[1..s-1],let u=s-a:zipWith(+)u(a:u),x`elem`take x u]!!0

```

Try it online!
> 1 votes

# Answer
# JavaScript, 216 bytes

```
function f(r){for(var n=1;;){var f=p(n);for(var u in f)if(s(f[u][0],f[u][1],r))return f[u];n++}}function p(r){for(var n=[],f=1;0<r;)n.push([r,f]),r--,f++;return n}function s(r,n,f){return n==f||(f<n?null:s(n,r+n,f))}

```

https://jsfiddle.net/twkz2gyb/

(Ungolfed code):

```
// For a given input n, return all combinations of positive integers that sum to n.
function findPairs(n) {
    var arr = [];
    var b = 1;
    while(n > 0) {
        arr.push([n, b]);
        n--;
        b++;
    }
    return arr;
}

// Run a sequence for a and b, and continue fibonacci'ing until r is found(or quit if past r).
function sequence(a, b, r) {
    if(b === r) {
        return true;
    } else if(b > r) {
        return null;
    }
    var nextFibo = a + b;
    return sequence(b, nextFibo, r);
}

// For a given n, find the first 2 numbers of the fibonacci sequence with the smallest sum that result in n.
function find(n) {
    var i = 1;
    while(i < 10) {
        var pairs = findPairs(i);
        for(var p in pairs) {
            var result = sequence(pairs[p][0], pairs[p][1], n);
            if(result) {
                return pairs[p];
            }
        }
        i++;
    }
}

```
> 0 votes

---
Tags: code-golf, math, sequence, fibonacci
---