title: Write a near crystalline program

text:
# Question
Title: Write a near crystalline program
A pristine program is a program that does not have any errors itself but will error if you modify it by removing any contiguous substring other than the entire program.

A crystalline program is sort of the opposite. It is a program which doesn't have any errors itself but will error if you modify it by adding any 1 character anywhere. We call these crystalline because adding an impurity will cause it to break.

Now a true crystalline program is quite hard to come by so in this challenge we will be just trying to get as close as possible.

You will write a program which does not error and count the number of 1 character insertions that also *don't* error. If your program were crystalline this number would be 0. Also count the number of total 1 character insertions possible.

Your score is then:

\\$ \dfrac{\mathrm{number\\,\\,of\\,\\,nonbreaking\\,\\,insertions}+2}{\mathrm{number\\,\\,of\\,\\,total\\,\\,insertions}} \\$

And your goal is to minimize this measure.

## Specifics

* Since different languages use different codepages and different ranges of characters, for this challenge a character is just any byte. The number of characters in your program is just the number of bytes it occupies and insertions are just that, the insertion of a new byte between any existing bytes or at the beginning and end of the program. You may select which characters you want to consider relevant for this challenge. When we insert any byte it will be one of those selected. The selected bytes must include:

+ At least 96 distinct characters
    + All characters used in your program
* For counting, insertions are considered different if they produce different programs. For example if your program is `ABBA`, then inserting a `B` after the first `A`, after the first `B` and after the second `B` all produce `ABBBA`, this counts as 1 insertion.
* A program errors if any of the following happens:

+ The compiler exits with a non-zero return code when run on the program.
    + The program exits with a non-zero return code when run.
    + The compiler produces non-empty output to STDERR when run on the program.
    + The program produces non-empty output to STDERR when run.

If your programming language of choice always triggers some of these options, ignore those specific options and treat them as non-errors. If your programming language of choice doesn't have a compiler just ignore options that mention a compiler.

# Answer
> 17 votes
# Ellipsis, score → 0

The program consists of \\$144 \times 8^n + 23\\$ ASCII periods `.` for \\$n \geq 0\\$, and gets a perfect score (i.e. every possible insertion causes an error, and any of the 256 possible octets can be inserted). As such, this is a true crystalline program, in addition to scoring arbitrarily close to 0 (even though being a true crystalline program isn't required for a perfect score). Because the scoring gives an advantage to longer programs, you can get a score arbitrarily close to 0 by increasing *n*.

Try it online! for \\$n=1\\$

The Ellipsis implementation is a compiler to brainfuck, so for this answer to be valid, the resulting brainfuck program needs to be executed via using a brainfuck compiler that will notice a syntax error (but there are plenty of those to choose from).

## Explanation

Ellipsis is a Lenguage variant, caring only about the length of the program it's compiling. It divides the length of the program by 3 (using floor division), interprets it as an octal number, and maps each octal digit to a brainfuck command.

If the program has length \\$144 \times 8^n + 23\\$, then floor-dividing this by 3 gives us \\$48 \times 8^n + 7\\$. In octal, that's `6`, followed by \\$n\\$ `0`s, followed by `7`; the brainfuck program is therefore of the form `[>…>]` with \\$n\\$ `>` characters. This is a valid brainfuck program that does nothing (it's a zero-iteration loop).

Any insertion will cause the program to have length \\$144 \times 8^n + 24\\$. Floor-dividing that by 3 will give us \\$48 \times 8^n + 8\\$, i.e. slightly higher, which will corrupt the `]` at the end of the program. For \\$n=0\\$, the program is now `]>` which is a syntax error due to the unmatched brackets. For larger \\$n\\$, the program is now `[` followed by \\$n-1\\$ `>` followed by `<>`; again, a syntax error due to unmatched brackets.

## How does this program work in other comparable languages?

* I couldn't find a valid Unary interpreter; the web interpreter seems to have fallen off the Internet. As such, I couldn't verify its error behaviour. Essentially the same program as the Ellipsis can be written in Unary according to the spec, though.
* Lenguage does *not* work (unless you consider a very slow memory leak to be an error because it will eventually exhaust all of memory); the Lenguage interpreter, upon finding an unmatched `[` or `]`, will go into an infinite loop trying to find the other, because (probably by mistake) the search for matching brackets wraps around the program. Eventually its count of unmatched brackets will overflow, but it's a bignum that uses memory proportional to the logarithm of its value, so this will take a very, very long time.
* The Ecstatic and MGIFOS implementations ignore invalid characters, so wouldn't notice insertions of things other than exclamation marks and asterisks respectively, and thus wouldn't score very well.
* Unary Except Every Zero Is Replaced with the Title of This Programming Language or, Alternately, Is Replaced with the Smallest Counter-Example to the Goldbach Conjecture. Compilers and Interpreters Only Have to Implement the Former Option almost works (with a character being placed inside the title of the language reducing the count, something that could break the bracket matching), but would not notice a character being inserted between two copies of the title of the programming language, and as such couldn't get a perfect score.

## ais523, this looks like a challenge that could be cheesed by checksums, why didn't you write an answer in A Pear Tree

A Pear Tree prints its main error message `a partridge` to standard *output*. Although this is an error by any normal definition, it doesn't fit the definition of an error in the question.

Additionally, the scoring favours longer programs. In A Pear Tree, the size of the checksum doesn't scale with the length of the program, so very long programs tend to have checksum collisions that prevent the normal checksumming behaviour of the language working correctly.

# Answer
> 8 votes
# Java `-encoding utf-16`, \\$2^{-37}\\$

Try to insert a single byte to UTF-16 file would resulting invalid encoding. So `javac` reports invalid utf-16 and refuse to compile the source code. That doesn't really matter what your source code is doing as long as it is a valid Java source code. Java supports at most 1GB source code. So maybe there are 256G different insertions, and the score should be 1/128G here. I'm not sure if this is a valid submission through.

---

# Java, \\$2^{-37}\\$

After thinking this twice. I just found out that you doesn't really need the `-encoding utf-16` compile parameter. Since `javac` will fail to compile your source code if it is larger that 1GB. So you simply need to submit a valid 1GB-1B program in Java. Any insertion would simply cause `javac` refuse to compile due to source code too long.

# Answer
> 7 votes
# , score=0.000000000202, 2000000021 bytes

*Edit: corrected score (increased by 1.04-fold) thanks to JDL*

```
t(1)[nchar("aaaaaaaaaa...2000 million and 1 letter 'a's...aaaaaaaaaaa")-2e9,]

```

Try it online with a smaller version of the program!

Score calculated by hand so may contain (hopefully small) errors.
The longest allowed string in  is `2^31-1` ≈ 2e9 bytes.

**Nonbreaking insertions:** '#' at the start, position 4, or end (3 insertions), '!', '.', '+' or '-' at position 3 (4 insertions), '.' or 'i' at position 4 (2 insertions), any digit at positions 3 or 4 (20 insertions), whitespace (space or tab) at positions 0,3,4,6 or at positions 0,2,3,6,7,8 from the end (20 insertions), for a total of 49 insertions.

**Total possible insertions:** All ASCII except 'a' (126 possible characters) at 2000000021 positions, plus 'a' at 21 positions, for a total of 2.52e11 possible insertions.

**Score:** `(49+2)/(126*2000000021+21)` = 2.02381e-10

---

We could also improve the score by gaming the relevant character set to exclude most of the nonbreaking characters: that is, excluding any of '#!.+-01345678i \t'. This leaves 4 nonbreaking insertions (by inserting one of '2' or '9' at positions 3 or 4), giving a score of `(4+2)/(110*2000000021+21)` = 2.727273e-11

---

Of course, an even more extreme (but boring) extension of this approach would be just the string `"aaaaaaaaaa...2147483647 letter 'a's...aaaaaaaaaa"`. Any single character added within the string will trigger an `Error in "aaa...aaa" : R character strings are limited to 2^31-1 bytes` error. Once we exclude whitespace and the '#' character from our character set, this would give a score of `2/(124*2147483649)` = 7.510666e-12.

# Answer
> 5 votes
# Zsh, score \\$ \frac {2+0} {497} \approx 0.00402 \\$ (1 byte)

```
;
```

Attempt This Online!

For the purposes of this answer, the "character set" of Zsh shall be all bytes except tab, newline, space, `#`, `-`, `:`, `w`, making the total number of characters 249. Since the program is only 1 byte, there are \\$ 2 * 249 - 1 = 497 \\$ unique possible insertions.

Every one of these 497 insertions breaks the program - Zsh is particularly good at producing errors :)

Validator / auto-scoring program: Attempt This Online!

This scoring program can be modified to test almost any language if you run it on TIO, where a Zsh program can access the interpreters of any other language (which is not the case on ATO).

# Answer
> 5 votes
# Python 3, score \\$\frac{2}{6841}\approx0.00029\\$

```
ConnectionRefusedError.with_traceback.__subclasshook__.__subclasshook__

```

Try it online! Footer verifies and scores the program.

The 96 bytes are codepoints from 27 to 127, without , `#`,`\\`,`,` and `;`. In theory I could append `.__subclasshook__` arbitrarily many times to get a lower score.

# Answer
> 4 votes
# Ruby, score \\$ \to 0 \\$

```
<<abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz
```

Attempt This Online!

Add arbitrarily more letters to `abcdefghijklmnopqrstuvwxyz` in both places to achieve a lower and lower score, asymptotically approaching zero. (with \\$ n \\$ letters, the score is \\$ \frac 1 {279+239n} \\$). The example shown here has a score of \\$ \frac 1 {6693} \approx 0.00015 \\$. With 1 million letters, the score would be \\$ \approx 0.0000000042 \\$.

The charset is all bytes except `\x00`, `\x04`, tab, newline, `\x0b`, `\x0c`, `\x0d`, `\x1a`, space, `!`, `#`, `+`, `-`, `;`, `\`, and `~`.

Explanation:

`<<` starts a "here-doc", which takes a single word, and turns the rest of the source code upto the first occurrence of that word again as a literal string.

This was originally going to be another) answer in Zsh, which also has here-docs, but unlike Zsh, Ruby produces an error when a heredoc isn't closed. (compare lone `<<abcdefghijklmnopqrstuvwxyz` in Ruby to in Zsh).

By having an error whenever the same word is not used twice, we can detect any single-character insertion to inside that word.

A few quirks of Ruby's syntax mean we can discard some ASCII characters, but they can be more than made up for by invalid UTF-8 bytes.

# Answer
> 3 votes
# BitCycle, score 0.0737

```
1...v
...^ ^

```

where `...` is an arbitrary number of spaces

Try it online!

Bitcycle has 70 operating bytes: `><^=+/\|-10!?~{}@abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ` (plus newline)
Per the challenge, I am considering 26 more, all of which are no-ops: `23456789#$%&*()_,.;:'"[]` (plus "\`")

Note that any position other than the first will have a duplicate case in a previous insertion location, and thus will only be `95` insertions instead of `96`. Insertion space will be indicated by an asterisk `*`. For the examples, the region `...` will be indicated by quotation marks `""`.

```
*1""v   any char except newline offsets   1 nonbreaking
""^ ^   "v", so "1" enters a loop         96 total

```

```
1"*"v   like case 1, but chars "^vV^/\+{~!?@"   13 nonbreaking
""^ ^   will also redirect the "1" elsewhere    95 total

```

```
1""v*   no chars   95 nonbreaking
""^ ^   will err   95 total

```

```
1""v     identical   1 nonbreaking
"*"^ ^   to case 1   95 total

```

```
1""v     no chars   95 nonbreaking
""^* ^   will err   95 total

```

```
1""v     no chars   95 nonbreaking
""^ *^   will err   95 total

```

```
1""v     no chars   95 nonbreaking
""^ ^*   will err   95 total

```

The score can be expressed as a fraction: \\$\frac{3+4c+14n}{1+5c+2cn}\\$ where \\$c\\$ is the number of characters in the set minus 1, and \\$n\\$ is the length of `...`. To generate the score listed, \\$c=95, n \to\infty\\$, which evaluates to \\$\frac{7}{95}\\$.
*Previously, I had missed a nonbreaking insertion, but this didn't change my score because of the assumed infinitely large \\$n\\$*

# Answer
> 1 votes
# Python 3, score \\$\frac2{239}\\$ (0 bytes)

And our hero program is...

NOTHING!!!

Same approach as above. The "bad characters" are:

`\t` (tab), `\n` (newline), `\x0c` (something IDK), `\r` (newline sort of), `#` (comment), `\` (line continuation), (space) , and `0123456789` (numbers).

Thus we define the range of bytes that can be added to be all single byte characters that are not in the above list.

Python testing script:

```
characterset=[chr(x) for x in range(256)]
noerr=''
for char in characterset:
 try: exec(char)
 except: pass
 else: noerr+=char; print(char)

noerr
len(noerr)

```

(Designed to be directly runned in the interactive console.)

However, sometimes `_` will work in REPL and the `\` somehow works, so be warned.

# Answer
> 1 votes
**C(gcc)**

```
m\
a\
i\
n(){}

```

score:
118/3840 -\> 120/3840

**Explanation**

main must be a part of the program, so almost no characters are valid there. To lower the score I expanded that part of the code with backslash-newline, which allows for very few characters(and thus more errors).

test code:

```
#include <stdio.h>
char prog[]="m\\\na\\\ni\\\nn(){}";
char tofile[0xff];
main(){
  long long bad=0;
  long long total=0;
  for(int i=0; i<sizeof(prog);i++){
    char c=0;
    do{
      FILE* tmpc=fopen("/tmp/tmp.c", "w");
      int j;
      for(j=0;j<i;j++) tofile[j]=prog[j];
      tofile[i]=c;
      for(j=i;prog[j];j++)tofile[j+1]=prog[j];
      fwrite(tofile, sizeof(prog), 1, tmpc);
      fclose(tmpc);

      FILE* gcc=popen("gcc /tmp/tmp.c", "r");
      char gccc=getc(gcc);
      while(gccc!=EOF){}
      int status=pclose(gcc);
      printf("code: \"%s\" Exit Status: %d\n", tofile, status);
      if(!status)
        bad++;
      total++;
    }while(++c!=0);
  }
  printf("score:\n %lld\n----\n %lld\n", bad, total);
}

```

It could be possible to do better, but the above code takes too long to run.

# Answer
> 0 votes
# Forth, Score 0.001736111 4 bytes

```
: abcdefghijklmnopqrstuvwxyz01234 ;

```

When run from a terminal, this program will correctly return nothing and the interpreter will return OK to the terminal.

Any insertion into the 31 character name will result in the correct program name not compiling, so the program will not exist and will not run.

Any insertion that puts anything but a blank character beside the `:` or `;` will result in the program not compiling correctly.

Possible insertions are

* blank before `:`,
* blank after `:`,
* blank before `;`, and
* blank after `;`.

The language parses with blanks and does not recognize any difference between one blank and two blanks between nonblank words. So there is no program that lacks these 4 insertions.

35 character program. At 36 locations we can insert any of 96 characters. 36\*96 = 3456.

(4+2)/3456 = 0.001736111

Standard compilers must allow names up to 31 characters, and may allow larger names. So this program could be, say 259 characters long, but then it would not run on all Forth compilers.

By stuffing the program with more 31-character functions, in the limit we would have 1 valid insertion per 31-character name, and that's as low as it gets.

However, if we only consider an insertion valid if it changes the program, and `: test ;` compiles the same as `: test ;` then maybe we should not consider those insertions.

In that case the program

```
: abcdefghijklmnopqrstuvwxyz01234 ;
: test
abcdefghijklmnopqrstuvwxyz01234
abcdefghijklmnopqrstuvwxyz01234
abcdefghijklmnopqrstuvwxyz01234
abcdefghijklmnopqrstuvwxyz01234 ;

```

is also entirely crystalline and we can add as many lines as we like to reduce the score toward zero.

# Answer
> 0 votes
# Wolfram Language (Mathematica), score \\$ \to 0 \\$

```
abcdef-abcdef+Null

```

Try it online!

Similar to the Ruby answer, add arbitrarily more letters to `abcdef` in both places to achieve a lower and lower score, asymptotically approaching zero. (with \\$ n \\$ letters, the score is \\$ \frac {16}{315+92n} \\$). Thanks Mathematica for no limits to variable names! The example shown here has a score of \\$ \frac 2 {95} \approx 0.0210526 \\$. With 1 million letters, the score would be \\$ \approx 0.000000173912 \\$.

The charset is 0x20 to 0x7F, printable ASCII, though there is nothing stopping any characters being input.

The 16 exceptions, in no order, include multiplying by one, replacing subtraction with adding a negative, and calling the local namespace:

```
+abcdef-abcdef+Null
`abcdef-abcdef+Null
 abcdef-abcdef+Null
1abcdef-abcdef+Null
abcdef+-abcdef+Null
abcdef -abcdef+Null
abcdef-+abcdef+Null
abcdef-`abcdef+Null
abcdef- abcdef+Null
abcdef-1abcdef+Null
abcdef-abcdef;+Null
abcdef-abcdef +Null
abcdef-abcdef+ Null
abcdef-abcdef+1Null
abcdef-abcdef+Null;

```

Other attempts included (0.0740741):

```
Quiet[0/0,{Power::infy,Infinity::indet}];

```

Which nicely throws an error if you mess with most of it, and (0.00126984)

```
If[#0==#1,,1,1]&[If[#0==#1,,1,1]&]

```

Which is a quine-like solution that tries to actively detect tampering.

---
Tags: code-challenge, radiation-hardening, pristine-programming
---


title: Track listings to time tables

text:
# Question
Title: Track listings to time tables
## Introduction

Don't you hate it when someone uploads an album you like to YouTube, but the description only contains a **track listing**? Like this:

```
1. Everything in Its Right Place - 4:11
2. Kid A - 4:44
3. The National Anthem - 5:50
4. How to Disappear Completely - 5:55
5. Treefingers - 3:42
6. Optimistic - 5:16
7. In Limbo - 3:31
8. Idioteque - 5:09
9. Morning Bell - 4:29
10. Motion Picture Soundtrack - 6:59

```

Now you don't know when *Morning Bell* starts unless you sum a bunch of times in your head! Usually, some good soul will come by and leave a handy **time table** in the (dreaded) comments section, which looks something like this:

```
(0:00:00) Everything in Its Right Place
(0:04:11) Kid A
(0:08:55) The National Anthem
(0:14:45) How to Disappear Completely
(0:20:40) Treefingers
(0:24:22) Optimistic
(0:29:38) In Limbo
(0:33:09) Idioteque
(0:38:18) Morning Bell
(0:42:47) Motion Picture Soundtrack

```

## Specification

* Your task is to write a program or function that takes a track listing as input and a time table as output.

+ You may choose to read input from STDIN, or an argument string, or an argument list of lines. Similarly, you may choose to print output to STDOUT, or return a string, or return a list of lines. Failing these, do whatever makes sense for your language.
* You may assume each input line has the format `(\d+)\. [A-Za-z0-9 ]{1,100} - (\d+):(\d\d)`. For the regex-impaired, this essentially means you can assume each line is well-formatted (as above) and **song titles consist only of alphanumeric ASCII characters and spaces**, and are no longer than 100 bytes long.
* A track's length is always at least `0:01` and no more than `59:59`.
* The track numbers are increasing order, starting from `1`, and counting up to no more than `99`.
* The total length of an album is no more than `9:59:59`.

This is , so shortest code (in bytes) wins.

## Test case

Your program should correctly perform the conversion presented in the introduction (Radiohead's *Kid A*). Here is a bigger test case (Sufjan Stevens' *Illinois*1) with long strings your program should also work on:

```
1. Concerning the UFO Sighting Near Highland Illinois - 2:08
2. The Black Hawk War - 2:14
3. Come On Feel the Illinoise - 6:45
4. John Wayne Gacy Jr - 3:19
5. Jacksonville - 5:24
6. A Short Reprise for Mary Todd Who Went Insane but for Very Good Reasons - 0:47
7. Decatur or Round of Applause for Your Stepmother - 3:03
8. One Last Whoo Hoo for the Pullman - 0:06
9. Chicago - 6:04
10. Casimir Pulaski Day - 5:53
11. To the Workers of the Rock River Valley Region - 1:40
12. The Man of Metropolis Steals Our Hearts - 6:17
13. Prairie Fire That Wanders About - 2:11
14. A Conjunction of Drones Simulating the Way - 0:19
15. The Predatory Wasp of the Palisades Is Out to Get Us - 5:23
16. They Are Night Zombies They Are Neighbors They Have Come Back from the Dead Ahhhh - 5:09
17. Lets Hear That String Part Again Because I Dont Think They Heard It All the Way Out in Bushnell - 0:40
18. In This Temple as in the Hearts of Man for Whom He Saved the Earth - 0:35
19. The Seers Tower - 3:53
20. The Tallest Man the Broadest Shoulders - 7:02
21. Riffs and Variations on a Single Note - 0:46
22. Out of Egypt into the Great Laugh of Mankind and I Shake the Dirt from My Sandals as I Run - 4:21

```

The correct output is:

```
(0:00:00) Concerning the UFO Sighting Near Highland Illinois
(0:02:08) The Black Hawk War
(0:04:22) Come On Feel the Illinoise
(0:11:07) John Wayne Gacy Jr
(0:14:26) Jacksonville
(0:19:50) A Short Reprise for Mary Todd Who Went Insane but for Very Good Reasons
(0:20:37) Decatur or Round of Applause for Your Stepmother
(0:23:40) One Last Whoo Hoo for the Pullman
(0:23:46) Chicago
(0:29:50) Casimir Pulaski Day
(0:35:43) To the Workers of the Rock River Valley Region
(0:37:23) The Man of Metropolis Steals Our Hearts
(0:43:40) Prairie Fire That Wanders About
(0:45:51) A Conjunction of Drones Simulating the Way
(0:46:10) The Predatory Wasp of the Palisades Is Out to Get Us
(0:51:33) They Are Night Zombies They Are Neighbors They Have Come Back from the Dead Ahhhh
(0:56:42) Lets Hear That String Part Again Because I Dont Think They Heard It All the Way Out in Bushnell
(0:57:22) In This Temple as in the Hearts of Man for Whom He Saved the Earth
(0:57:57) The Seers Tower
(1:01:50) The Tallest Man the Broadest Shoulders
(1:08:52) Riffs and Variations on a Single Note
(1:09:38) Out of Egypt into the Great Laugh of Mankind and I Shake the Dirt from My Sandals as I Run

```

## Leaderboard

For your score to appear on the board, it should be in this format:

```
# Language, Bytes

```

```
var QUESTION_ID=58231,OVERRIDE_USER=3852;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

1. Apologies to Sufjan, whose amazing track names I had to mangle a bit in order to make them fit the simple format this problem is limited to.

# Answer
> 12 votes
# CJam, ~~60~~ ~~57~~ 55 bytes

*Thanks to Sp3000 for saving 2 bytes.*

```
qN/{T60bZ0e["(%d:%02d:%02d) "e%\S/1>)':/60bT+:T;W<S*N}/

```

Test it here.

## Explanation

```
qN/{      e# Read input and split into lines.
  T60b    e# Push T (initially zero, we use this to keep track of the total time in
          e# seconds), and convert it to base 60.
  Z0e[    e# Pad it with zeroes to 3 digits to get hours, minutes, seconds.
  "(%d:%02d:%02d) "e%
          e# Get the (h:mm:ss) part using a format string.
  \S/     e# Pull up the current line, split on spaces.
  1>      e# Discard the first segment, i.e. the track number.
  )':/    e# Pull off the last segment, i.e. the time, and split on colons.
  60b     e# Interpret the two parts as base-60 digits to get the amount of seconds
          e# for the track.
  T+:T;   e# Add this to T and discard it.
  W<      e# Discard the last segment of the remaining string (the hyphen).
  S*N     e# Join the song name back together with spaces and push a line feed.
}/

```

# Answer
> 6 votes
# Perl, (93 chars plus `-p`) 94 bytes

```
s!\d+\. (.+) - (\d+:(\d+))!sprintf"(%d:%02d:%02d) $1",$n/3600,$n%3600/60,$n%60,$n+=$3+60*$2!e

```

To run:

```
perl -pe 's!\d+\. (.+) - (\d+:(\d+))!sprintf"(%d:%02d:%02d) $1",$n/3600,$n%3600/60,$n%60,$n+=$3+60*$2!e' <<< '<input>'

```

# Answer
> 5 votes
# Python 2, ~~170~~ 160 Bytes

Been a while since I've done a golf, hopefully this isn't too bad :P

```
t=0
for i in input().split('\n'):i=i.split(' - ');print'(%d:%02d:%02d)'%(t/3600,t%3600/60,t%60),i[0].split('. ')[1];k=i[-1].split(':');t+=int(k[0])*60+int(k[1])

```

The input should be surrounded by quotes, and split by newlines, like so:

```
"1. Concerning the UFO Sighting Near Highland Illinois - 2:08\n2. The Black Hawk War - 2:14\n3. Come On Feel the Illinoise - 6:45\n4. John Wayne Gacy Jr - 3:19\n5. Jacksonville - 5:24\n6. A Short Reprise for Mary Todd Who Went Insane but for Very Good Reasons - 0:47\n7. Decatur or Round of Applause for Your Stepmother - 3:03\n8. One Last Whoo Hoo for the Pullman - 0:06\n9. Chicago - 6:04\n10. Casimir Pulaski Day - 5:53\n11. To the Workers of the Rock River Valley Region - 1:40\n12. The Man of Metropolis Steals Our Hearts - 6:17\n13. Prairie Fire That Wanders About - 2:11\n14. A Conjunction of Drones Simulating the Way - 0:19\n15. The Predatory Wasp of the Palisades Is Out to Get Us - 5:23\n16. They Are Night Zombies They Are Neighbors They Have Come Back from the Dead Ahhhh - 5:09\n17. Lets Hear That String Part Again Because I Dont Think They Heard It All the Way Out in Bushnell - 0:40\n18. In This Temple as in the Hearts of Man for Whom He Saved the Earth - 0:35\n19. The Seers Tower - 3:53\n20. The Tallest Man the Broadest Shoulders - 7:02\n21. Riffs and Variations on a Single Note  - 0:46\n22. Out of Egypt into the Great Laugh of Mankind and I Shake the Dirt from My Sandals as I Run - 4:21"

```

# Answer
> 5 votes
# C++, ~~212~~ ~~209~~ ~~202~~ 189 bytes

C++ because.. why not?

```
#include<iostream>
long d,t,u;main(){std::string a,b(8,0);while(getline(std::cin>>t>>a[0],a,'-')>>t>>b[0]>>u){strftime(&b[0],9,"%T",gmtime(&d));b[0]='(';std::cout<<b+")"+a+'\n';d+=t*60+u;}}

```

Live: ~~212~~ ~~209~~ ~~202~~ 189

# Answer
> 3 votes
# Python 2, ~~207~~ 206 bytes

```
h=m=s=0
for i in raw_input().splitlines():
 print("(%d:%.2d:%.2d) "%(h,m,s),i.split('-')[0].split('. ')[1])
 t=i.split('-')[1].split(':')
 m+=int(t[0]);s+=int(t[1]);r=s//60;s-=r*60;m+=r;r=m//60;m-=r*60;h+=r

```

## Usage

```
$ python test.py
'1. Concerning the UFO Sighting Near Highland Illinois - 2:08\n2. The Black Hawk War - 2:14\n3. Come On Feel the Illinoise - 6:45'
(0:00:00) Concerning the UFO Sighting Near Highland Illinois
(0:02:08) The Black Hawk War
(0:04:22) Come On Feel the Illinoise

```

# Answer
> 3 votes
# Gema, 151 characters

```
\B=@set{t;}
<D>. * - <D>\:<D>=(@div{$t;3600}:@fill-right{00;@div{@mod{$t;3600};60}}:@fill-right{00;@mod{$t;60}}) *@set{t;@add{@add{$t;$4};@mul{$3;60}}}

```

Sample run:

```
bash-4.3$ gema '\B=@set{t;};<D>. * - <D>\:<D>=(@div{$t;3600}:@fill-right{00;@div{@mod{$t;3600};60}}:@fill-right{00;@mod{$t;60}}) *@set{t;@add{@add{$t;$4};@mul{$3;60}}}' tracklist.txt
(0:00:00) Concerning the UFO Sighting Near Highland Illinois
(0:02:08) The Black Hawk War
(0:04:22) Come On Feel the Illinoise
(0:11:07) John Wayne Gacy Jr
(0:14:26) Jacksonville
(0:19:50) A Short Reprise for Mary Todd Who Went Insane but for Very Good Reasons
(0:20:37) Decatur or Round of Applause for Your Stepmother
(0:23:40) One Last Whoo Hoo for the Pullman
(0:23:46) Chicago
(0:29:50) Casimir Pulaski Day

```

# Answer
> 1 votes
# awk, ~~119~~ 101 bytes

```
{split($NF,t,":");$1=$(--NF)="";--NF;print"("substr(strftime("%H:%M:%S",s,1),2)")"$0;s+=t[1]*60+t[2]}

```

~~This is *way* longer than I wanted it to be. The problem is that `%H` doesn't format the hours like requested, so I needed to calculate the hours myself.~~

Ack, I'm stupid. The results of `strftime` were wrong because I needed to tell it to use UTC time. That cut 18 bytes off!

## 119-byte version

```
{split($NF,t,":");$1=$(--NF)="";--NF;print"("(h||0)":"strftime("%M:%S",s)")"$0;s=(r=s+t[1]*60+t[2])%3600;h=int(r/3600)}

```

# Answer
> 0 votes
# Python 3 (3.8\>=), 115 bytes

```
a=0
while 1:_,*s,_,t=input().split();print(f"({a//3600}:%02d:%02d)"%(a//60%60,a%60),*s);a+=int(t[0])*60+int(t[2:4])

```

Ungolfed version:

```
a = 0
while True:
    _,*s,_,t = input().split()                         # Skip firt element and the second to last
    print(f"({a//3600}:%02d:%02d)"%(a//60%60,a%60),*s) # Print time + what is between the number and the -
    a+=int(t[0])*60+int(t[2:4])                        # Increment time

```

Exit with error.

Attempt This Online!

# Answer
> 0 votes
# Ruby, ~~112~~ 109 bytes

*-3 bytes thanks to Steffan*

```
a=0
loop{_,*s,_,t=gets.split;puts "(%d:%02d:%02d) "%[a/3600,a/60%60,a%60]+s*' ';a+=t[0].to_i*60+t[2..4].to_i}

```

Exit with error

Attempt This Online!

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


title: Add in the blanks

text:
# Question
Title: Add in the blanks
In this challenge you will be given a list of positive integers which represents some range of integers which has been truncated for display. Your job is to find the missing bits and insert ellipses to show that that part has been truncated.

The input will always be strictly ascending and if two consecutive values differ by more than 1 then we know some data has been removed in between them.

For example if the input is:

```
1,2,3,4,20,21,22

```

Then since `4` and `20` differ by more than 1 we insert an ellipsis between them:

```
1,2,3,4,...,20,21,22

```

However if the consecutive values differ by *exactly two*, then we just reinsert the missing value (their mean), since an ellipsis doesn't actually save any space when it's just covering 1 value.

So for example if the input is:

```
1,2,3,5,6

```

Then `3` and `5` differ by more than 1 so data has been removed between them, but they differ by 2 so we just insert the missing `4`.

```
1,2,3,4,5,6

```

Additionally if the first value is greater than `1` we know that something has been truncated off the front. So we add an ellipsis, or if the first value is `2`, a `1` as the first value. We can't know that something has been truncated off the end so we never add anything there.

## Task

Given a list of positive strictly-ascending integers as input output the list with the proper insertions. You can represent ellipses in the output as any constant value other than a positive integer. For the convenience of strongly typed programming, you may also output a list of optional values with the null value representing ellipses.

This is so the goal is to minimize the size of your source code as measured in bytes.

## Test cases

```
[1,2,3,4,20,21,22] -> [1,2,3,4,...,20,21,22]
[1,2,3,5,6] -> [1,2,3,4,5,6]
[2,3,4,9] -> [1,2,3,4,...,9]
[3,5,7,8,10] -> [...,3,4,5,6,7,8,9,10]
[1,20,23] -> [1,...,20,...,23]

```

# Answer
# JavaScript (ES10),  ~~45~~  43 bytes

Uses `undefined` for ellipses.

```
a=>a.map(p=v=>[[[],v-1][v+~p],p=v]).flat(2)

```

Try it online!

### Commented

```
a =>             // a[] = input array, e.g. [ 1, 3, 6 ]
  a.map(p =      // initialize p to a zero'ish value
  v =>           // for each value v in a[]:
    [            //   build an array:
      [          //     according to v - p - 1, append:
        [],      //       an empty array if it's 0
        v - 1    //       v - 1 if it's 1
                 //       implicitly: undefined for anything else
      ][v + ~p], //
      p = v      //     append v and update p to v
    ]            //   end of array
  )              // end of map(); this gives:
                 //   [ [ [], 1 ], [ 2, 3 ], [ undefined, 6 ] ]
  .flat(2)       // apply .flat() at depth 2 to clean this up:
                 //   [ 1, 2, 3, undefined, 6 ]

```
> 9 votes

# Answer
# K (ngn/k), 24 bytes

```
,/0{((0;();x-1)x-y),x}':

```

Try it online!

Uses `0N` for ellipses.

## Explanation

* `0{...}':` pairwise map with placeholder 0 (*y* is prev elem, *x* is next elem)...
    + `(0;();x-1)x-y` get elem of list `(0;();x-1)` at index *x* \- *y*
    + `,x` append *x*
* `,/` flatten
> 6 votes

# Answer
# , ~~69~~ 68 bytes

*Edit: -1 byte thanks to pajonk*

```
\(x){F[i<-cumsum(2-!(j=diff(c(0,x))-1))]=x;F[-i]=(x*(j<2))[j>0]-1;F}
```

Attempt This Online!

Uses `-1` as the ellipsis character.

**How?**

```
j=diff(c(0,x))-1    # get the differences between adjacent elements -1
!j                  # zero for consecutive integers, 1 otherwise
i=cumsum(2-!j)      # indices of original elements, leaving gaps for ellipses or new elements-in-gaps
F[i]=x              # fill-in the elements into vector F
F[-i]=              # fill-in the gaps with...
      (x...)[j>0]-1 # one less than the subsequent original value...
        *(j<2)      # ...adjusted to zero if the gap was >2
F                   # finally, return F

```
> 6 votes

# Answer
# 05AB1E, ~~22~~ ~~19~~ ~~17~~ 15 bytes

```
0šüŸε¦¤®s‚‚éн}˜

```

Uses `-1` for ellipsis, but could alternatively use another 1-byte alternative (e.g. `0`, `""`, `" "`, `"\n"`, `"abcdefghijklmnopqrstuvwxyz"`, etc.) by replacing the `®`.

-3 bytes porting *@MamaFunRoll*'s K (ngn/k) answer
-2 bytes porting *@DominicVanEssen*'s Husk answer
-2 bytes thanks to *@CommandMaster* with yet another different approach

Try it online or verify all test cases.

**Explanation:**

```
          #  Example input: [2,3,5,9,13]
0š        # Prepend a 0 to the (implicit) input-list
          #  STACK: [0,2,3,5,9,13]
  ü       # For each overlapping pair {a,b}:
   Ÿ      #  Push a list in the range [a,b]
          #   STACK: [[0,1,2],[2,3],[3,4,5],[5,6,7,8,9],[9,10,11,12,13]]
ε         # Map over each inner list:
          #   STACK1: [0,1,2] ;        STACK2: [5,6,7,8,9]
 ¦        #  Remove the first item
          #   STACK1: [1,2] ;          STACK2: [6,7,8,9]
  ¤       #  Push the last item (without popping the list)
          #   STACK1: [1,2],2 ;        STACK2: [6,7,8,9],9
   ®      #  Push -1, the ellipsis value
          #   STACK1: [1,2],2,-1 ;     STACK2: [6,7,8,9],9,-1
    s     #  Swap the top two values on the stack
          #   STACK1: [1,2],-1,2 ;     STACK2: [6,7,8,9],-1,9
     ‚    #  Pair them together
          #   STACK1: [1,2],[-1,2] ;   STACK2: [6,7,8,9],[-1,9]
      ‚   #  Pair the two lists together
          #   STACK1: [[1,2],[-1,2]] ; STACK2: [[6,7,8,9],[-1,9]]
       é  #  Sort by length (shortest to longest)
          #   STACK1: [[1,2],[-1,2]] ; STACK2: [[-1,9],[6,7,8,9]]
        н #  Pop and leave the first inner list
          #   STACK1: [1,2] ;          STACK2: [-1,9]
}         # After the map
          #  STACK: [[1,2],[3],[4,5],[-1,9],[-1,13]]
 ˜        # Flatten the resulting list of lists
          #  STACK: [1,2,3,4,5,-1,9,-1,13]
          # (after which the result is output implicitly)

```
> 5 votes

# Answer
# Python 3, 62 bytes

```
lambda a:sum([[~-i*(i-2in[0]+a),i][i-1in[0]+a:]for i in a],[])

```

Try it online!

Use `0` for ellipses.

For each value `i` in input:

* If `i - 1` is already included in input, or `i - 1` is `0`, we need insert nothing before it;
* Otherwise, if `i - 2` is already included in input, or `i - 2` is `0`, we need insert `i - 1` before it;
* Otherwise, we insert `...` before it.
> 4 votes

# Answer
# Wolfram Language (Mathematica), 40 bytes

```
##&[Pick[#>p+2||++p,p<#],p=#]&/@(p=0;#)&

```

Try it online!

Represents ellipses by `True`.

```
##&[Pick[#>p+2||++p,p<#],p=#]&/@(p=0;#)&
                                 p=0    starting from 0,
                              /@(   ;#) for each element:
         #>p+2                            True if current-previous>2,
              ||++p                         otherwise previous+1,
    Pick[          ,p<#]                      but omit if =current
##&[                    ,p=#]           prepend and update previous

```
> 3 votes

# Answer
# Jelly, ~~13~~ 11 bytes

```
ŻṖ‘ż¹FQµIỊa

```

Try it online!

`0` for ellipses.

```
Ż              Prepend a 0,
 Ṗ             trim the last element,
  ‘            increment,
   ż¹F         flat-interleave with the original input,
      Q        and uniquify.
       µ  a    Zero out any elements of the result which
        I      have a difference with the next element
         Ị     greater than 1.

```
> 3 votes

# Answer
# Haskell, 69 bytes

```
g x y|x+1==y=[y]|x+2==y=[x+1,y]|True=[0,y]
f a=concat$zipWith g(0:a)a
```

Attempt This Online!
> 2 votes

# Answer
# PARI/GP, 50 bytes

```
a->b=0;concat([if(c-b<3,[b+1..b=c],[x,b=c])|c<-a])
```

Attempt This Online!

Use `x` for ellipses.
> 2 votes

# Answer
# Vyxal, 15 bytes

```
Gɾ‡?cḊƛḢ[h?c∧;f

```

Try it Online!

Uses `0` for ellpisis.
> 2 votes

# Answer
# Perl 5 \+ `-p -M5.10.0`, 35 bytes

If using a `0` is acceptable this would be 31 bytes, but that feels a bit cheaty...

```
$;=$_*say$--1?"...":$_-1if$-=$_-1-$
```

Try it online!
> 2 votes

# Answer
# , 34 31 bytes

```
0(}.(+_*_1>])2-/\])@~.@,<:,@,.]

```

Try it online!

This was surprisingly difficult to golf in J and the K approach ended up being longer than either of these.

## Idea

We take a two pass strategy:

* First we insert the numbers below each number.
* Then we check if there are any gaps greater than 1. If so, we replace those gaps with infinity `_`.

## How

Consider `2 3 4 9`:

* `<:...,.]` Decrement zipped with original input:

```
1 2
2 3
3 4
8 9

```
* `0...~.@,...,@` Flatten, prepend 0, and take the unique:

```
0 1 2 3 4 8 9

```
* `}.(...)2-/\]` On the left hand side, kill the 0, on the right hand side take consecutive deltas:

```
1 2 3 4 8 9  (...) _1 _1 _1 _1 _4 _1

```
* `_*_1>]` Turn every entry less than \_1 on the right into infinity:

```
0 0 0 0 _ 0

```
* `+` And add that to the left side:

```
1 2 3 4 _ 9

```

## , first approach, 34 bytes

```
[:;]<@~.@,~"+]+_3>.@%@+3<.2-~/\0,]

```

Try it online!
> 2 votes

# Answer
# Python 2, 57 bytes

```
p=1
for n in input():
 if p<n:print-~p/n*p
 print n;p=n+1

```

Try it online!

A program that takes in a list on STDIN and prints the output values on separate lines.
> 2 votes

# Answer
# Rust, ~~135~~ 130 bytes

*-5 bytes thanks to @alpehalpha*

```
|v:Vec<i8>|v.iter().scan(0,|c,&a|Some((match a-*c{1=>vec![a],2=>vec![a-1,a],_=>vec![-1,a]},*c=a).0)).flatten().collect::<Vec<_>>()
```

Attempt This Online!
> 1 votes

# Answer
# Brainfuck, 71 bytes

```
,[[->+>+<<]>>[-<<+>>]<<<[->-<]+>-[-[<<.>-]<[>>-.+<<-<]>]<[-<]>>[-]>.>,]
```

Ungolfed program (a port of my Haskell solution)

Script to test it
> 1 votes

# Answer
# Husk, ~~16~~ 14 bytes

*Edit: -2 bytes by stealing Kevin Cruijssen's improvements in his port of this!*

```
ΣẊö◄LSeoe0→t…Θ

```

Try it online!

Uses `0` for ellipsis; could use any other integer by exchanging the `0` at position 10 in the code.

```
             Θ     # add a zero at the start of the list;
 Ẋȯ                # now, for every pair of elements:
            …      #  fill gaps with numeric ranges,
           t       #  and discard the first element,
     Se            #  then make a 2-element list of this and
       oe0→        #  just the last element preceded by zero,
   ◄L              #  and select the element with minimum length;
Σ                  # finally, flatten the resulting list-of-lists.

```
> 1 votes

# Answer
# C (clang), ~~76~~ 71 bytes

```
p;f(*a,n){for(p=0;n--;)printf("%d %d "+(++p==*a)*3,p+1<*a?0:p,p=*a++);}

```

Try it online!

*Saved 5 bytes thanks to att!!!*

Inputs a pointer to an array of positive integers and its length (because pointers in C carry no length info).
Prints out the filled in array using \\$0\\$ for ellipses.
> 1 votes

# Answer
# Ruby, ~~50~~ 45 bytes

```
->l{a=0;l.map{|x|p x-a<2?a:0if x>a+=1;p a=x}}

```

Try it online!

Thanks Jonah for -2 bytes and a different approach which saved 3 more bytes.
> 1 votes

# Answer
# AWK, 44 bytes

```
{d=$0-a;if(d>1)print d==2?$0-1:0;print a=$0}

```

Try it online!

*Thanks to Dominic van Essen for pointing out that 5 bytes needed to initialize the variable `a` on TIO aren't needed on GNU awk, and so shouldn't count in the score.*

Outputs 0 for `...`.
> 1 votes

# Answer
# Pyth, 17 bytes

*Inspired by Arnauld's JavaScript answer*

```
.n,Le<[YtdG)aZ=Zd

```

Try it online! or Try all test cases

Uses the lowercase alphabet as the ellipsis (could alternatively use `0` or empty string).

```
.n,Le<[YtdG)aZ=Zd
                    Implicitly initialize Z to 0
   L                Left map over the input with variable d
      [    )        3-element list of...
       Y              ... the empty list
        td            ... (d - 1)
          G           ... the lowercase alphabet
     <              Keep the first N elements of that list, where...
            aZd      ... N = the absolute difference of Z and d
              =Zd   (Set Z to d)
    e               Take the last element of the resulting list
  ,                 Create a two-element list of (result, current element)
.n                  Flatten

```
> 1 votes

# Answer
# Retina 0.8.2, 73 bytes

```
\d+
$*
^
,
(^|\b1+),(?=11\1\b)
$&1$1,
(^|\b1+),(?=11\1)
$&...,
^,

1+
$.&

```

Try it online! Link includes test cases. Explanation:

```
\d+
$*

```

Convert to unary.

```
^
,

```

Prefix `0` (in unary).

```
(^|\b1+),(?=11\1\b)
$&1$1,

```

Where two consecutive integers differ by `2`, insert the missing integer.

```
(^|\b1+),(?=11\1)
$&...,

```

Where two consecutive integers differ by more than `1`, insert an ellipsis.

```
^,

```

Remove the leading `0`.

```
1+
$.&

```

Convert to decimal.
> 0 votes

# Answer
# , 75 bytes

```
\(x,y=c(0,x))for(i in x-1){if(!i%in%y)show(`if`((i-1)%in%y,i,0));show(i+1)}
```

Attempt This Online!
> 0 votes

# Answer
# Charcoal, 24 bytes

```
ＩＥ⊕Φ⌈θ№⁺θ⊖θ⊕ι∧№⊞Ｏ⁺θ⊕θ¹ιι

```

Try it online! Link is to verbose version of code. Uses `0` to represent an ellipsis. Explanation:

```
     θ                      Input array
    ⌈                       Maximum
   Φ                        Filter on implicit 0-indexed range
        θ                   Input array
       ⁺                    Concatenated with
          θ                 Input array
         ⊖                  Vectorised decrement
      №                     Contains
            ι               0-indexed value
           ⊕                Incremented (i.e. 1-indexed)
  ⊕                         Incremented (back to 1-indexed values)
 Ｅ                          Map over values
                  θ         Input array
                 ⁺          Concatenated with
                    θ       Input array
                   ⊕        Vectorised increment
               ⊞Ｏ           Concatenated with
                     ¹      Literal integer `1`
              №             Contains
                      ι     Current value
             ∧              Logical And
                       ι    Current value
Ｉ                           Cast to string
                            Implicitly print

```
> 0 votes

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


title: Incremental Ranges!

text:
# Question
Title: Incremental Ranges!
Your task is to, given two positive integers, \\$x\\$ and \\$n\\$, return the first \\$x\\$ numbers in the incremental ranges sequence.

The incremental range sequence first generates a range from one to \\$n\\$ inclusive. For example, if \\$n\\$ was \\$3\\$, it would generate the list \\$\[1,2,3\]\\$. It then repeatedly appends the last \\$n\\$ values incremented by \\$1\\$ to the existing list, and continues.

An input of \\$n=3\\$ for example:

```
n=3
1. Get range 1 to n. List: [1,2,3]
2. Get the last n values of the list. List: [1,2,3]. Last n=3 values: [1,2,3].
3. Increment the last n values by 1. List: [1,2,3]. Last n values: [2,3,4].
4. Append the last n values incremented to the list. List: [1,2,3,2,3,4]
5. Repeat steps 2-5. 2nd time repeat shown below.

2nd repeat:
2. Get the last n values of the list. List: [1,2,3,2,3,4]. Last n=3 values: [2,3,4]
3. Increment the last n values by 1. List: [1,2,3,2,3,4]. Last n values: [3,4,5].
4. Append the last n values incremented to the list. List: [1,2,3,2,3,4,3,4,5]

```

**Test cases:**

```
n,   x,   Output
1,  49,   [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49]
2, 100,   [1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48,48,49,49,50,50,51]
3,  13,   [1,2,3,2,3,4,3,4,5,4,5,6,5]

```

# Answer
# Python 2, 39 bytes

```
lambda n,x:[v/n+v%n+1for v in range(x)]

```

**Try it online!**
> 9 votes

# Answer
# , 33 bytes

```
function(n,x,z=1:x-1)z%%n+z%/%n+1

```

Try it online!

Ports Jonathan Allan's Python solution.

# , 36 bytes

```
function(n,x)outer(1:n,0:x,"+")[1:x]

```

Try it online!

My original solution; generates an \\$n\times x\\$ matrix with each column as the increments, i.e., \\$1 \ldots n, 2\ldots n+1,\ldots\\$, then takes the first \\$x\\$ entries (going down the columns).
> 7 votes

# Answer
# Jelly, 4 bytes

```
Ḷd§‘

```

A dyadic Link accepting two positive integers, `x` on the left and `n` on the right, which yields a list of positive integers.

**Try it online!**

### How?

```
Ḷd§‘ - Link: x, n              e.g   13, 3
Ḷ    - lowered range (x)             [0,1,2,3,4,5,6,7,8,9,10,11,12]
 d   - divmod (n)                    [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2],[3,0],[3,1],[3,2],[4,0]]
  §  - sums                          [0,1,2,1,2,3,2,3,4,3,4,5,4]
   ‘ - increment (vectorises)        [1,2,3,2,3,4,3,4,5,4,5,6,5]

```
> 7 votes

# Answer
# , ~~13~~ 12 bytes

```
[$[:,1++/&i.

```

Try it online!

## how

We take `x` as the left arg, `n` as the right. Let's take `x = 8` and `n = 3` for this example:

* `+/&i.`: Transform both args by creating integer ranges `i.`, that is, the left arg becomes `0 1 2 3 4 5 6 7` and the right arg becomes `0 1 2`. Now we create an "addition table `+/` from those two:

```
 0 1 2
 1 2 3
 2 3 4
 3 4 5
 4 5 6
 5 6 7
 6 7 8
 7 8 9

```
* `1 +`: Add 1 to every element of this table:

```
 1 2  3
 2 3  4
 3 4  5
 4 5  6
 5 6  7
 6 7  8
 7 8  9
 8 9 10

```
* `[: ,`: Flatten it `,`:

```
 1 2 3 2 3 4 3 4 5 4 5 6 5 6 7 6 7 8 7 8 9 8 9 10

```
* `[ $`: Shape it `$` so it has the same number of elements as the original, untransformed left arg `[`, ie, `x`:

```
 1 2 3 2 3 4 3 4

```
> 6 votes

# Answer
# Perl 6, 18 bytes

```
{(1..*X+ ^*)[^$_]}

```

Try it online!

Curried function `f(x)(n)`.

### Explanation

```
{                }  # Anonymous block
      X+     # Cartesian product with addition
  1..*       # of range 1..Inf
         ^*  # and range 0..n
 (         )[^$_]  # First x elements

```
> 5 votes

# Answer
# 05AB1E, 6 bytes

```
L<s‰O>

```

Port of *@JonathanAllan*'s Jelly answer, so make sure to upvote him!

First input is \\$x\\$, second input is \\$n\\$.

Try it online or verify all test cases.

**Explanation:**

```
L       # Push a list in the range [1, (implicit) input]
        #  i.e. 13 → [1,2,3,4,5,6,7,8,9,10,11,12,13]
 <      # Decrease each by 1 to the range [0, input)
        #  → [0,1,2,3,4,5,6,7,8,9,10,11,12]
  s‰    # Divmod each by the second input
        #  i.e. 3 → [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2],[3,0],[3,1],[3,2],[4,0]]
    O   # Sum each pair
        #  → [0,1,2,1,2,3,2,3,4,3,4,5,4]
     >  # And increase each by 1
        #  → [1,2,3,2,3,4,3,4,5,4,5,6,5]
        # (after which the result is output implicitly)

```

---

My own initial approach was **8 bytes**:

```
LI∍εN¹÷+

```

First input is \\$n\\$, second input is \\$x\\$.

Try it online or verify all test cases.

**Explanation:**

```
L         # Push a list in the range [1, (implicit) input]
          #  i.e. 3 → [1,2,3]
 I∍       # Extend it to the size of the second input
          #  i.e. 13 → [1,2,3,1,2,3,1,2,3,1,2,3,1]
   ε      # Map each value to:
    N¹÷   #  The 0-based index integer-divided by the first input
          #   → [0,0,0,1,1,1,2,2,2,3,3,3,4]
       +  #  Add that to the value
          #   → [1,2,3,2,3,4,3,4,5,4,5,6,5]
          # (after which the result is output implicitly)

```
> 5 votes

# Answer
# Octave, 25 bytes

```
@(n,x)((1:n)'+(0:x))(1:x)

```

Anonymous function that inputs numbers `n` and `x`, and outputs a row vector.

Try it online!

## How it works

Consider `n=3` and `x=13`.

The code `(1:n)'` gives the column vector

```
1
2
3

```

Then `(0:x)` gives the row vector

```
0  1  2  3  4  5  6  7  8  9 10 11 12 13

```

The addition `(1:n)'+(0:x)` is element-wise with broadcast, and so it gives a matrix with all pairs of sums:

```
1  2  3  4  5  6  7  8  9 10 11 12 13 14
2  3  4  5  6  7  8  9 10 11 12 13 14 15
3  4  5  6  7  8  9 10 11 12 13 14 15 16

```

Indexing with `(1:x)` retrieves the first `x` elements of this matrix in column-major linear order (down, then across), as a row vector:

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

```
> 5 votes

# Answer
# Haskell, 31 bytes

```
n#x=take x$[1..n]++map(+1)(n#x)

```

Try it online!

This might be my favorite kind of recursion. We start with the values from 1 to n and then concatenate those same values (via self-reference) +1. then we just take the first x values.
> 5 votes

# Answer
# Brain-Flak, 100 bytes

```
(<>)<>{({}[()]<(({}))((){[()](<{}>)}{}){{}{}<>(({})<>)(<>)(<>)}{}({}[()]<(<>[]({}())[()]<>)>)>)}{}{}

```

With comments and formatting:

```
# Push a zero under the other stack
(<>)<>

# x times
{
    # x - 1
    ({}[()]<

        # Let 'a' be a counter that starts at n
        # Duplicate a and NOT
        (({}))((){[()](<{}>)}{})

        # if a == 0
        {
            # Pop truthy
            {}
            <>

            # Reset n to a
            (({})<>)

            # Push 0 to each
            (<>)(<>)
        }

        # Pop falsy
        {}

        # Decrement A, add one to the other stack, and duplicate that number under this stack
        ({}[()]<
            (<>[]({}())<>)
        >)
    >)
}

```

Try it online!
> 4 votes

# Answer
# Jelly, 5 bytes

```
+þẎḣ’

```

Try it online!
> 2 votes

# Answer
# MATL, ~~16~~, 10 bytes

```
:!i:q+2G:)

```

Try it online!

-6 bytes saved thanks to Guiseppe and Luis Mendo!

Explanation:

```
:!          % Push the array [1; 2; ... n;]
  i:q       % Push the array [0 1 2 ... x - 1]
     +      % Add these two arrays with broadcasting
      2G    % Push x again
        :)  % Take the first x elements

```
> 2 votes

# Answer
# Forth (gforth), 34 bytes

```
: f 0 do i over /mod + 1+ . loop ;

```

Try it online!

### Code Explanation

```
: f            \ start a new word definition
  0 do         \ start a loop from 0 to x-1
    i          \ put the current loop index on the stack
    over       \ copy n to the top of the stack
    /mod       \ get the quotient and remainder of dividing i by n
    + 1+       \ add them together and add 1
    .          \ output result
  loop         \ end the counted loop
;              \ end the word definition

```
> 2 votes

# Answer
# Gaia, 8 bytes

```
…@┅+‡t_<

```

Try it online!

Does basically the same thing as the Octave and MATL answers.
> 2 votes

# Answer
# Japt `-m`, ~~12~~ 7 bytes

Port of Jonathan's Python solution.

Takes `x` as the first input.

```
%VÄ+UzV

```

Try it
> 1 votes

# Answer
# Ruby, 32 bytes

```
->n,x{(0...x).map{|i|i/n+i%n+1}}

```

Try it online!
> 1 votes

# Answer
## Haskell, ~~34~~ 33 bytes

```
n#x=take x$do j<-[1..];[j..j+n-1]

```

Try it online!
> 1 votes

# Answer
# JavaScript, 36 bytes

```
n=>g=x=>x?[...g(--x),1+x%n+x/n|0]:[]

```

Try It Online!
> 1 votes

# Answer
# Perl 5 `-na`, 43 bytes

```
@r=map$_..$_+$F[1]-1,1..$_;say"@r[0..$_-1]"

```

Try it online!
> 1 votes

# Answer
# K (oK), ~~17~~ 16 bytes

```
{y#,/1_y(1+)\!x}

```

Try it online!
> 1 votes

# Answer
# Stax, 6 bytes

```
⌐çYæ▄9

```

Run and debug it

Unpacked & explained:

```
rmx|%+^ Full program, implicit input (n, x on stack; n in register X)
r       Range [0 .. x)
 m      Map:
  x|%     Divide & modulo x
     +    Add quotient and remainder
      ^   Add 1
          Implicit output

```
> 1 votes

# Answer
# APL (Dyalog Unicode), ~~8~~ 10 bytesSBCS

```
⊢↑∘∊⊣,/∘⍳⌈

```

Try it online!

A dyadic train. Left arg = interval (n), right arg = number of terms (x). `⎕IO←1`.

### How it works

```
⊢↑∘∊⊣,/∘⍳⌈  ⍝ Left: interval n, Right: terms x
       ∘⍳⌈  ⍝ Generate range [1..max(n,x)]
            ⍝ (Too short array will complain at N-wise reduce)
    ⊣,/     ⍝ Extract length-n intervals (dyadic N-wise reduce)
  ∘∊        ⍝ Flatten and list the elements into a vector
⊢↑          ⍝ Take first x terms from the above

```

---

Porting Jonah's J answer would be 10 bytes in Extended (traditional APL doesn't have an equivalent to J's `&`):

# APL (Dyalog Extended), 10 bytes

```
⊣↑∘,1++\⍥⍳

```

Try it online!

Uses `⎕IO←0`. If `⎕IO←1` were used, I'd need to replace `1+` with `¯1+`, costing one more byte (instead of saving two bytes).

### How it works

```
⊣↑∘,1++\⍥⍳  ⍝ Left: x, Right: n
        ⍥⍳  ⍝ Create 0-based ranges for both args
      +\    ⍝ Outer product by addition (shortcut of ∘.+)
    1+      ⍝ Increment
  ∘,        ⍝ Flatten the matrix into a vector
⊣↑          ⍝ Take first x elements

```
> 1 votes

# Answer
# Alchemist, 77 bytes

```
_->In_n+In_x
x+n+0y+0z->a+Out_a+Out_" "+m+y
y+n->n
y+0n->z
z+m+a->z+n
z+0m->a

```

Try it online!

Increments and outputs a counter n times, then subtracts n-1 before repeating.
> 0 votes

# Answer
# Charcoal, 18 bytes

```
ＮθＦＮ⊞υ⊕⎇‹ιθι§υ±θＩυ

```

Try it online! Link is to verbose version of code. I had dreams of seeding the list with a zero-indexed range and then slicing it off again but that was actually 2 bytes longer. Explanation:

```
Ｎθ                  Input `n` into variable
   Ｎ                Input `x`
  Ｆ                 Loop over implicit range
         ι          Current index
        ‹           Less than
          θ         Variable `n`
       ⎇   ι        Then current index else
               θ    Variable `n`
              ±     Negated
            §υ      Cyclically indexed into list
      ⊕             Incremented
    ⊞υ              Pushed to list
                Ｉυ  Cast list to string for implicit output

```
> 0 votes

# Answer
# APL+WIN, ~~29 23~~ 16 bytes

```
 x↑,1+(⍳x←⎕)∘.+⍳⎕

```

Index origin = 0 and prompts for n and x

Try it online! Courtesy of Dyalog Classic
> 0 votes

# Answer
# **JS, 54 bytes**

```
f=(n,x)=>Array.from(Array(x),(_,i)=>i+1-(i/n|0)*(n-1))

```

Try it online!
> 0 votes

# Answer
# C (gcc), 49 44 bytes

Using recursion to save some bytes.

```
f(n,x){x&&printf("%d ",x%n+x/n+1,f(n,--x));}

```

Try it online!
> 0 votes

# Answer
# Perl 5, 39 bytes

```
say 1+int($_/$F[1])+$_%$F[1]for 0..$_-1

```

Try it online!
> 0 votes

# Answer
# Icon, 48 bytes

```
procedure f(x,n)
write((0to n)+(1to x))\n&\z
end

```

Try it online!
> 0 votes

# Answer
# C(clang), 843 bytes

```
#include <stdlib.h>
main(int argc, char* argv[]){
        int x,n;
        if (argc == 3 && (n = atoi(argv[1])) > 0 && (x = atoi(argv[2])) > 0){
                int* ranges = calloc(x, sizeof *ranges);
                for (int i = 0; i < x; i++){
                        if (i < n){
                                ranges[i] = i+1;
                        }
                        else {
                                ranges[i] = ranges[i-n] + 1;
                        }
                }
        printf("[");
        for (int j = 0; j < x - 1; j++){
                printf("%d",ranges[j]);
                printf(",");
        }
        printf("%d",ranges[x - 1]);
        printf("]\n");
        free(ranges);
        }
        else {
                printf("enter a number greater than 0 for n and x\n");
        }
}

```
> 0 votes

# Answer
# C# (Visual C# Interactive Compiler), 41 bytes

```
x=>n=>new int[x].Select((_,a)=>a/n+a%n+1)

```

Try it online!
> 0 votes

# Answer
# Factor, 55 bytes

```
: f ( a b -- c ) [0,b) [ over /mod + 1 + . ] with map ;

```

Try it online!
> 0 votes

# Answer
# Julia 1.0, 34 bytes

```
f(n,x)=[v÷n+v%n+1 for v in 0:x-1]

```

Ports Jonathan Allan's Python solution.

Try it online!
> 0 votes

# Answer
# Io, 50 bytes

Port of Jonathan Allan's answer.

```
method(n,x,Range 0 to(x-1)map(v,(v/n)floor+v%n+1))

```

Try it online!
> 0 votes

# Answer
# Husk, 6 bytes

```
↑Σ¡m→ḣ

```

Try it online!

```
↑Σ¡m→ḣ
     ḣ  Make a range [1, n]
  ¡     Make an infinite list of ranges by repeatedly
   m→   incrementing each element in that range
 Σ      Flatten that into a 1-D list
↑       Take the first x elements of that

```
> 0 votes

# Answer
# Factor, 35 bytes

```
[ iota swap '[ _ /mod + 1 + ] map ]

```

Try it online!
> 0 votes

# Answer
# Vyxal, 6 bytes

```
ʁ$vḋṠ›

```

Try it Online!

Port of Jelly.

```
ʁ$vḋṠ›
ʁ       # Range [0, first input)
 $      # Swap so the second input is at the top
  vḋ    # For each in the range, divmod by that
    Ṡ   # Sum each
     ›  # Increment

```
> 0 votes

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


title: Is it an ordinal?

text:
# Question
Title: Is it an ordinal?
# Background (feel free to skip)

Ordinals are the abstract representation of well-orders. A well-order of a set is a total order, which basically means that every element in the set can be compared against any other element in the set, and one of them is either smaller or larger. Also there are no cycles.

The crucial difference between total orders and well-orders is that a well order is always well-founded. This means that every nonempty subset of a well-ordered set has a least element, which implies that an infinite descending chain is impossible; An infinite sequence \\$a\_1\gt a\_2\gt a\_3\gt a\_4 \gt ...\\$ doesn't exist.

This is useful for many things, one of them being proving that recursion terminates. For example, here is the definition of the Ackermann function:

\\$ A(0,n)=n+1\\ A(m+1,0)=A(m,1)\\ A(m+1,n+1)=A(m,A(m+1,n)) \\$

Can you see why it always terminates? We call the Ackermann function with a 2-tuple of natural numbers, and when we recurse, the tuple is smaller under the standard tuple ordering (lexicographic ordering: first compare the first elements, then the second ones). Because the standard tuple ordering is a well-ordering (\\$\omega^2\\$ in fact), the recursion must eventually terminate.

With the knowlege that \\$\omega^2\\$ is well-founded we were able to prove that the Ackermann function is total. There are of course larger ordinals, one of them being \\$\varepsilon\_0\\$. All ordinals below \\$\varepsilon\_0\\$ can be represented with a simple ordinal notation using ragged lists.

We can use the standard lexicographic ordering of ragged lists. However there is a problem. The ordering, while a total order, is not a well order. For example, `[ [[]] ] > [ [], [[]] ] > [ [], [], [[]] ] > [ [], [], [], [[]] ] > ...`

There is a solution though. We can just make sure that in every list, the elements are in decreasing order. This means that `[ [], [[]] ]` is not an ordinal, since `[[]]` is larger than `[]`

Here is a table of some valid ordinal notations

| Notation | Value |
| --- | --- |
| `[]` | \\$0\\$ |
| `[[]]` | \\$\omega^0=1\\$ |
| `[[],[]]` | \\$\omega^0+\omega^0=2\\$ |
| `[[[]]]` | \\$\omega^{\omega^0}=\omega\\$ |
| `[[[[]],[]],[],[]]` | \\$\omega^{\omega^{\omega^0}+\omega^0}+\omega^0+\omega^0=\omega^{\omega+1}+2\\$ |

# Task

You are given a ragged list containing only lists. Your task is to determine if that list is an ordinal. A list is an ordinal iff each of its elements are ordinals, and the list is decreasing.

Comparison between ordinals can be done with simple lexicographic comparison. That is, given two lists, compare the first elements. If they are equal, compare the second ones and so on. If one of the lists runs out of elements, that list is smaller.

For example, say you got the ragged list `[a,b,c,d]`. You must first make sure that `a`, `b`, `c` and `d` are ordinals. Then, make sure that \\$a\ge b\ge c\ge d\\$, using lexicographic ordering. If both conditions are true, then it's an ordinal. When there is just one element in the list, the second condition is always true. And when the list is empty, both conditions are vacuously true.

Standard rules apply.

# Test cases

```
[] -> True
[[]] -> True
[[[]]] -> True
[[], []] -> True
[[[[]]]] -> True
[[[], []]] -> True
[[[]], []] -> True
[[], [[]]] -> False
[[], [], []] -> True
[[[[[]]]]] -> True
[[[[], []]]] -> True
[[[[]], []]] -> True
[[[], [[]]]] -> False
[[[], [], []]] -> True
[[[[]]], []] -> True
[[[], []], []] -> True
[[[]], [[]]] -> True
[[[]], [], []] -> True
[[], [[[]]]] -> False
[[], [[], []]] -> False
[[], [[]], []] -> False
[[], [], [[]]] -> False
[[], [], [], []] -> True
[[[[[[]]]]]] -> True
[[[[[], []]]]] -> True
[[[[[]], []]]] -> True
[[[[], [[]]]]] -> False
[[[[], [], []]]] -> True
[[[[[]]], []]] -> True
[[[[], []], []]] -> True
[[[[]], [[]]]] -> True
[[[[]], [], []]] -> True
[[[], [[[]]]]] -> False
[[[], [[], []]]] -> False
[[[], [[]], []]] -> False
[[[], [], [[]]]] -> False
[[[], [], [], []]] -> True
[[[[[]]]], []] -> True
[[[[], []]], []] -> True
[[[[]], []], []] -> True
[[[], [[]]], []] -> False
[[[], [], []], []] -> True
[[[[]]], [[]]] -> True
[[[], []], [[]]] -> True
[[[[]]], [], []] -> True
[[[], []], [], []] -> True
[[[]], [[[]]]] -> False
[[[]], [[], []]] -> False
[[[]], [[]], []] -> True
[[[]], [], [[]]] -> False
[[[]], [], [], []] -> True
[[], [[[[]]]]] -> False
[[], [[[], []]]] -> False
[[], [[[]], []]] -> False
[[], [[], [[]]]] -> False
[[], [[], [], []]] -> False
[[], [[[]]], []] -> False
[[], [[], []], []] -> False
[[], [[]], [[]]] -> False
[[], [[]], [], []] -> False
[[], [], [[[]]]] -> False
[[], [], [[], []]] -> False
[[], [], [[]], []] -> False
[[], [], [], [[]]] -> False
[[], [], [], [], []] -> True
[[[[[[[]]]]]]] -> True
[[[[[[], []]]]]] -> True
[[[[[[]], []]]]] -> True
[[[[[], [[]]]]]] -> False
[[[[[], [], []]]]] -> True
[[[[[[]]], []]]] -> True
[[[[[], []], []]]] -> True
[[[[[]], [[]]]]] -> True
[[[[[]], [], []]]] -> True
[[[[], [[[]]]]]] -> False
[[[[], [[], []]]]] -> False
[[[[], [[]], []]]] -> False
[[[[], [], [[]]]]] -> False
[[[[], [], [], []]]] -> True
[[[[[[]]]], []]] -> True
[[[[[], []]], []]] -> True
[[[[[]], []], []]] -> True
[[[[], [[]]], []]] -> False
[[[[], [], []], []]] -> True
[[[[[]]], [[]]]] -> True
[[[[], []], [[]]]] -> True
[[[[[]]], [], []]] -> True
[[[[], []], [], []]] -> True
[[[[]], [[[]]]]] -> False
[[[[]], [[], []]]] -> False
[[[[]], [[]], []]] -> True
[[[[]], [], [[]]]] -> False
[[[[]], [], [], []]] -> True
[[[], [[[[]]]]]] -> False
[[[], [[[], []]]]] -> False
[[[], [[[]], []]]] -> False
[[[], [[], [[]]]]] -> False
[[[], [[], [], []]]] -> False
[[[], [[[]]], []]] -> False
[[[], [[], []], []]] -> False
[[[], [[]], [[]]]] -> False
[[[], [[]], [], []]] -> False
[[[], [], [[[]]]]] -> False
[[[], [], [[], []]]] -> False
[[[], [], [[]], []]] -> False
[[[], [], [], [[]]]] -> False
[[[], [], [], [], []]] -> True
[[[[[[]]]]], []] -> True
[[[[[], []]]], []] -> True
[[[[[]], []]], []] -> True
[[[[], [[]]]], []] -> False
[[[[], [], []]], []] -> True
[[[[[]]], []], []] -> True
[[[[], []], []], []] -> True
[[[[]], [[]]], []] -> True
[[[[]], [], []], []] -> True
[[[], [[[]]]], []] -> False
[[[], [[], []]], []] -> False
[[[], [[]], []], []] -> False
[[[], [], [[]]], []] -> False
[[[], [], [], []], []] -> True
[[[[[]]]], [[]]] -> True
[[[[], []]], [[]]] -> True
[[[[]], []], [[]]] -> True
[[[], [[]]], [[]]] -> False
[[[], [], []], [[]]] -> True
[[[[[]]]], [], []] -> True
[[[[], []]], [], []] -> True
[[[[]], []], [], []] -> True
[[[], [[]]], [], []] -> False
[[[], [], []], [], []] -> True
[[[[]]], [[[]]]] -> True
[[[], []], [[[]]]] -> False
[[[[]]], [[], []]] -> True
[[[], []], [[], []]] -> True
[[[[]]], [[]], []] -> True
[[[], []], [[]], []] -> True
[[[[]]], [], [[]]] -> False
[[[], []], [], [[]]] -> False
[[[[]]], [], [], []] -> True
[[[], []], [], [], []] -> True
[[[]], [[[[]]]]] -> False
[[[]], [[[], []]]] -> False
[[[]], [[[]], []]] -> False
[[[]], [[], [[]]]] -> False
[[[]], [[], [], []]] -> False
[[[]], [[[]]], []] -> False
[[[]], [[], []], []] -> False
[[[]], [[]], [[]]] -> True
[[[]], [[]], [], []] -> True
[[[]], [], [[[]]]] -> False
[[[]], [], [[], []]] -> False
[[[]], [], [[]], []] -> False
[[[]], [], [], [[]]] -> False
[[[]], [], [], [], []] -> True
[[], [[[[[]]]]]] -> False
[[], [[[[], []]]]] -> False
[[], [[[[]], []]]] -> False
[[], [[[], [[]]]]] -> False
[[], [[[], [], []]]] -> False
[[], [[[[]]], []]] -> False
[[], [[[], []], []]] -> False
[[], [[[]], [[]]]] -> False
[[], [[[]], [], []]] -> False
[[], [[], [[[]]]]] -> False
[[], [[], [[], []]]] -> False
[[], [[], [[]], []]] -> False
[[], [[], [], [[]]]] -> False
[[], [[], [], [], []]] -> False
[[], [[[[]]]], []] -> False
[[], [[[], []]], []] -> False
[[], [[[]], []], []] -> False
[[], [[], [[]]], []] -> False
[[], [[], [], []], []] -> False
[[], [[[]]], [[]]] -> False
[[], [[], []], [[]]] -> False
[[], [[[]]], [], []] -> False
[[], [[], []], [], []] -> False
[[], [[]], [[[]]]] -> False
[[], [[]], [[], []]] -> False
[[], [[]], [[]], []] -> False
[[], [[]], [], [[]]] -> False
[[], [[]], [], [], []] -> False
[[], [], [[[[]]]]] -> False
[[], [], [[[], []]]] -> False
[[], [], [[[]], []]] -> False
[[], [], [[], [[]]]] -> False
[[], [], [[], [], []]] -> False
[[], [], [[[]]], []] -> False
[[], [], [[], []], []] -> False
[[], [], [[]], [[]]] -> False
[[], [], [[]], [], []] -> False
[[], [], [], [[[]]]] -> False
[[], [], [], [[], []]] -> False
[[], [], [], [[]], []] -> False
[[], [], [], [], [[]]] -> False
[[], [], [], [], [], []] -> True

```

# Answer
> 5 votes
# Haskell + free, 34 bytes

To represent ragged lists we use the free package and represent them as free monads generated by the list.

```
f(Free x)=all f x&&scanl1 min x==x

```

ATO seems to be broken and TIO doesn't have free so no link for now. :(

Since there are now elements in the list a better representation of this type would be `Fix []`. However I don't know of any Haskell libraries (other than hgl) which export a fully featured version of this.

# Answer
> 4 votes
# Python, 43 bytes

```
f=lambda a:1in map(f,a)or a<sorted(a)[::-1]
```

Attempt This Online!

Outputs inverted: `False` for valid ordinals, and `True` for invalid ordinals.

This is a DeMorgan's Law conversion of the below, which would be a completely direct translation of the problem statement:

### 46 bytes

```
f=lambda a:all(map(f,a))and a==sorted(a)[::-1]
```

Attempt This Online!

But by inverting it, `all` becomes `any`, which can then be changed to `1in` (using this tip of mine), which saves a byte on parentheses.

Also, `and` becomes `or`, for another -1.

Finally, by the magic of the properties of lexicographic comparison, we can use `<` instead of `!=` in the inverted form, for a total of 3 bytes saved.

---

# Python, 44 bytes

```
f=lambda a:{*map(f,a)}<={a==sorted(a)[::-1]}
```

Attempt This Online!

Bonus answer, outputting non-inverted.

# Answer
> 3 votes
# Rust Nightly + `#![feature(is_sorted)]`, 101 bytes

```
#[derive(PartialOrd,PartialEq)]
struct T(Vec<T>);fn f(t:&T)->bool{t.0.is_sorted()&&t.0.iter().all(f)}

```

Playground Link

# Answer
> 3 votes
# Python 2, 35 bytes

```
f=lambda a:[`a`][a<sorted(a,key=f)]
```

Attempt This Online!

Heavily based on (same logic as) @pxeger's python answer.

My additions:

1. Use the fact that string representation of lists has the correct ordering.
2. Use `sort` `key` to save `map` construction.
3. Use exit code for signalling freeing up return value for use with 1,2.

# Answer
> 2 votes
# Factor, 40 bytes

```
[ [ [ after=? ] monotonic? ] deep-all? ]

```

Try it online!

Using a depth-first search, is every element non-increasing?

# Answer
> 2 votes
# Jelly, 7 bytes

```
ṢṚ⁼ȧß€Ạ

```

Try it online!

Test all cases given

## Explanation

```
ṢṚ⁼ȧß€Ạ    given a candidate list:
   ȧ        check that the following two conditions are satisfied:
  ⁼          1. the list is equal to
 Ṛ              the reverse of
Ṣ               the sorted version of the list
     ß€Ạ     2. and the same is true for every element in the list

```

# Answer
> 1 votes
# Charcoal, 22 bytes

```
¹⊞υＡＦυＷι«⊞υ§ι±¹¿‹⌊ι⊟ι⎚

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a valid ordinal, nothing if invalid. Explanation:

```
¹

```

Assume the input is an ordinal.

```
⊞υＡ

```

Start by checking the input.

```
Ｆυ

```

Loop through the ragged lists to check.

```
Ｗι«

```

Loop though the elements of the current ragged list.

```
⊞υ§ι±¹

```

Add the last element of the current ragged list to the list of lists to check.

```
¿‹⌊ι⊟ι⎚

```

Check that the last element is also the minimum element, and also remove it from the current ragged list, so that the rest of the current ragged list can be checked.

Note that Charcoal's input format is a list of inputs, so if you accidentally enter `[[], [[]]]` you're actually providing two inputs, and the program will happily tell you that the first input is a valid ordinal.

---
Tags: code-golf, decision-problem, ragged-list
---


title: Pangram "Hello, World!"

text:
# Question
Title: Pangram "Hello, World!"
*Your challenge*: The code must print "Hello, World!" and nothing else.

*Your restrictions*: Your program must satisfy these requirements:

1. The program must be a pangram.

* It must use every character in printable ASCII, or, if you chose a particularly strange language, characters which are stored as one byte.
    * You are allowed to use other characters.
2. The program may not have unnecessary characters.

* No subset of individual characters may be removed from the program while the program still outputs "Hello, World!"
    * For example, if code `ABBC` outputs `Hello, World!` then neither codes `AC` nor `BC` may output "Hello, World!", although code `BA` may.
    * This also means you cannot have a statement to print "Hello, World!" *per se* anywhere in your program, as everything other than that statement could be deleted and the program would do the same thing.
3. The program must not take input.
4. Your program does not create any errors.
5. You must not use any "Hello, World!" builtins.

*Your score*: Your score is calculated by \[length of the program in characters\] - \[number of different characters\]. Lowest score wins. (Tie-breakers are oldest post.)

*Nota Bene*: the second requirement is almost impossible to verify, so an answer is valid only after a week has passed for anyone who wishes to do so to be able to disprove the validity of your answer.

# Answer
> 8 votes
# Husk, 256 bytes, 256 characters, score=0

```
m←`C₁†ȯ→*2c¨abqnpsyhkzjwf
¢"H½↕↑↓↔∟¦¡¿‼…‰‡√≤≥±∂∫∞≈≠≡⌐¬÷×τ►#$%&'()+Φ-./013456789:;<=>?@ABDEFG¤IJKLMNOPQRSTUVṄXYZ[\]^_⁵ı§χituvxg¹{|}~·₀₂₃₄₅₆₇₈₉⌈⌉⌊⌋ΓΔΘΛΞΠΣ€ΨΩαβγδεζηθλμξπρςσ▲φƒψω⁰r²³⁴d⁶⁷⁸⁹£,¥o´ ▼!◄lȦḂĊḊĖḞĠḢİĿṀWȮṖṘṠṪẆẊẎŻȧḃċḋėḟġḣeȷŀṁṅṗṙṡṫẇẋẏżÄËÏÖÜŸØäëïöüÿø◊□¶«»

```

Try it online!

I *think* this is irreducible. It certainly took a bit of effort to build, but striving for a score of zero is inviting pretty close scrutiny...

Husk has 256 characters on its codepage, so this pangram needs to use all of them. Aiming for a zero score also means that (a) the 'program' code cannot easily include any of the letters of 'Hello, World!', and (b) we need to find a way to 'recycle' the letters 'l' and 'o', which each occur more-than-once in the output.
Unfortunately, Husk uses '!' as its indexing function, which rules-out the most straightforward approach to extracting elements from a long string, so we need to find a different way to do this.

Here's my approach:

**line 2: the encoding string (228 characters, + 2 characters `¢"`)**

```
¢"H½↕↑↓↔∟¦¡¿ ... öüÿø◊□¶«»      # A 228-character string, repeated forever.
                                # Since one of the characters is a '\', though,
                                # this is read by Husk as a 227-character array.
                                # The characters of 'Hello, World!' are inserted
                                # at specific positions in the infinite string,
                                # (so they occur out-of-order in the single copy).

```

**line 1: the indexing program (26 characters)**

```
     †ȯ   c¨abqnpsyhkzjwf       # For all the codepoints of the index string "abqnpsyhkzjwf":
        *2                      # double them
       →                        # and add 1.
  `C₁                           # Now divide the encoding string into substrings with these lengths
m←                              # and get the first letter of each.

```

The indexing string `"abqnpsyhkzjwf"` is constructed to 'hit' the letters 'o' and 'l' 2 and 3 times, respectively, by 'wrapping around' in the infinite list, so that those letters only need to occur once in the encoding string. The largest index needs to be the same as the length of the encoding string, in order to 'hit' the same target ('l') twice in a row: this is achieved with 'q' (2x codepoint 113 + 1 = 227).

# Answer
> 8 votes
# C (gcc),  ~~111~~  109 bytes, score = 14

```
main(){printf("H%cllo, Wo\x72ld!",39+sizeof"14568:<=>?@ABCDEFGIJKLMNOPQRSTUVXYZ[]`bghjkquvwy0|~#$&'*-./^_");}

```

Try it online!

Edit: bugfix thanks to Noodle9

Edit 2: changed order of numbers and operators in the string to fix a problem found by G B, replaced `"Hello, World!"` with `"Hello, Wo\x72ld!"`

## shorter solution based on Sheik Yerboutis Code (107 bytes, score = 12)

```
main(){printf("H%cllo, Wo\x72ld!","_:?=<#$&*-+^|./4138596@ABCDEFGIJKLMNOPQRSTUVXYZ`bghjkquvwysz0~e"['>']);}

```

Try it online!

# Answer
> 7 votes
# Ruby,  ~~119~~  112 bytes / score 17

```
puts ["%x"%(("!\#&+,-01245:;<>?@ABDEFIJKLNOQRUVWXYZ`dflqnry{|}"=~/$/)^"s8j9bePwGp7SgMTCvznH".to_i(36))].pack'h*'

```

Try it online!

# Answer
> 6 votes
# Python 3, 101 bytes, 101 - 95 = 6

```
print('o#$%&*./0W368;<=>? @ABCDEFG,IJKLMNOPoQRSTUVXY\154Z^_`abcflghjkmqsuevwyz{|}~H'[::-9]+"\x72ld!")

```

Try it online!

# Answer
> 6 votes
# Backhand, 100 - 95 = 5

```
M#$%&"()*+H-./0e1234l5678l9:;<o=>?@,ABCD FGIJWKLNOoPQRSrTUVXlYZ[\c^_`b"dfgh]ikmn'pqst!uvwxryz{}a|~jE

```

Try it online!

Note that the version on TIO is missing a couple of instructions (notably `'`), so I've copied the interpreter here. This program works because Backhand executes every fifth instruction thanks to the first `M` (it's actually a little more complex than this), so the actual code is more like:

```
M    "    H    e    l    l    o    ,         W    o    r    l    c    "    ]    '    !    r    a   j

```

However, since you can't remove the spaces inbetween without breaking the flow of the program, you can replace them with whatever you want. The final check is that the `j` jumps to the 10th character (`H`) to halt and output,, which is less feasible if you modify the program. It's possible you might be able to form a valid program from this mishmash, but it is unlikely, and I'm sure that there's another permutation that fixes that.

### Explanation:

```
M                      Increase the step count from 3 to 5
 "Hello, Worlc"        Push the string to the stack
               ]       Increment c to d
                '!     Push !
                  r    Reverse the stack
                   aj  Jump back to the 10th character
  H                    Halt and output the stack

```

# Answer
> 5 votes
# JavaScript (ES6), score ~~30~~ 124 - 95 = 29

```
alert(`Hell`+String.fromCharCode(057^"#$%&*-/1234689:;<=>?@ABDEFGIJKLMNOPQRTUVXYZ][_bcjkpqsuvwxyz{|}~\\".length)+', World!')
```

The `o`s of `fromCharCode` cannot be put inside quotes. Its char code is 111, which can't be uses directly as an argument to `String.fromCharCode`. You can't XOR to get it because you need 64, 86, 104 or 106, which are also impossible, I think.

# Answer
> 4 votes
# JavaScript (Node.js), 118 117 116 - 95 = 21

shoutout to tsh for spotting 2 issues

```
alert(`Hello, Wo${('\71'+";#%&*/8025:<=>[]?@ABCDEFGIJKLMNOPQRTUVXYZ|_bcfjkpmqsuvwxyz".length^-~94).toString(36)}d!`)

```

Try it online!

# Answer
> 4 votes
# BASIC, 129 bytes

```
FOR i=8-2 TO 79 STEP 3+3:PRINT MID$("9*./!H065<>e?@ABClGJKLQlUVYZ[o\]^_`,abcf  ghjksWmnpqxotuvwyrz4{|}l~#%&'d",MOD(i,73),1);:NEXT

```

Try it online!

Updated to a valid version thanks to Dominic van Essen.

# Answer
> 3 votes
# , ~~119~~ 117 bytes, score=~~24~~ 22

Thanks to Dominic van Essen for spotting a bug.

```
cat('Hello, Wo',intToUtf8(nchar("#$%&*-./012479:;<>?@ABDEFGIJKLMNOPQRSVXYZ[]^_`bgjkmquvwyz{|}~")+53),"\x6Cd!",sep="")

```

Try it online!

Uses the hex code trick to encode the last `l` as `\x6C`. This saves 2 bytes: 1 by avoiding the reuse of the `l` (none of the other characters are used anywhere else), and 1 by avoiding having to escape the `\` (as `\\`) in the string.

The long string in the middle is 61 characters long. They are all necessary to get the character `r` (ASCII code 114), which is produced by the `intToUtf8(nchar("...")+53)` part.

# Answer
> 3 votes
# C (gcc), score 114 - 95 = 19

Saved 2 bytes and removed 3 points thanks to Sheik Yerbouti!!!

```
j;main(){for(;j<74;j+=6)putchar("H#$%&'e*-./0l12358l9:>?@oABCDE,FGIJK LMNOPWQRSTUoVXYZ\\r^_`bglkqsvwdxyz|~!"[j]);}

```

Try it online!

All characters outside of the double-quotes are needed in order for the program to compile and run properly. Taking any of the characters out from the double-quoted string will mess-up `Hello, World!` from being printed properly. That string is *exactly* `Hello, World!` with 5 characters in between each character.

# Answer
> 0 votes
# Zsh, score \\$ 116 - 108 = 8 \\$

```
1=`wc -m<<<'␀␁␂␃␄␅␆␇␈␎␏ABCDEFGIJKMNOPQRSTUVXYZabfghjkqsuvxyz234567890_+[];:~./>?\|"%^&*'`
print   He${(L#)@}lo, World!
```

Attempt This Online!

`␀␁␂␃␄␅␆␇␈␎␏` should be the unprintable characters `0x00` to `0x08` and `0x0E` to `0x0F`, but these don't render in SE markdown.

---
Tags: string, code-challenge, restricted-source, hello-world
---