title: ASCII Art of the Day #4 - Zodiac Signs

text:
# Question
Title: ASCII Art of the Day #4 - Zodiac Signs
We all love horoscopes, *don't we*? But I have a serious problem in this *Horoscope App* installed on my *Smart Phone* that it only displays the icon of the Zodiac Sign for each day's horoscope. Now, I do remember my horoscope, but its hard to remember others' whose horoscope I am interested in.

# Challenge

So here is your challenge for an another addition to the ASCII Art of the Day series. Given a date and month input, output the corresponding Zodiac sign in ASCII format as shown below. Each Zodiac Sign is followed after the name and date range (`DD MM` format) for the zodiac sign.

```
Aries - 21 03 - 20 04
 .-.   .-.
(_  \ /  _)
     |
     |
Taurus - 21 04 - 20 05
 .     .
 '.___.'
 .'   '.
:       :
:       :
 '.___.'
Gemini - 21 05 - 20 06
._____.
  | |
  | |
 _|_|_
'     '
Cancer - 21 06 - 20 07
   .--.
  /   _'.
 (_) ( )
'.    /
  '--'
Leo - 21 07 - 20 08
  .--.
 (    )
(_)  /
    (_.
Virgo - 21 08 - 20 09
 _
' ':--.--.
   |  |  |_
   |  |  | )
   |  |  |/
        (J
Libra - 21 09 - 20 10
     __
___.'  '.___
____________
Scorpio - 21 10 - 20 11
 _
' ':--.--.
   |  |  |
   |  |  |
   |  |  |  ...
         '---':
Sagittarius - 21 11 - 20 12
      ...
      .':
    .'
'..'
.''.
Capricorn - 21 12 - 20 01
        _
\      /_)
 \    /'.
  \  /   :
   \/ __.'
Aquarius - 21 01 - 20 02
.-"-._.-"-._.-
.-"-._.-"-._.-
Pisces - 21 02 - 20 03
'-.    .-'
   :  :
 --:--:--
   :  :
.-'    '-.

```

# Input

* You would be provided two integers corresponding to the date of month and month of year (in that order) of the birthday.
* The date and month will be `1` indexed like in normal calendars.
* You can take input form STDIN/ARGV/function arguments or the closest equivalent

# Output

* Based on what date range the input date falls in, output to STDOUT, the corresponding Zodiac Sign.
* You can have upto 4 trailing spaces in each line but no leading spaces that are not part of the output.
* You can either write a full program or a named function.

This is so the shortest code in bytes wins!

---

# Leaderboard

**The first post of the series generates a leaderboard.**

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

# Answer
# CJam, ~~296~~ ~~284~~ ~~272~~ ~~265~~ 264 bytes

```
"03½åÙªWË#å¥ÜZ2ò'ýðDc}¦Ð£RÞ5ä<Üå§ÖÞYÏuäOe¤¶è2²|ZëßB«ô¬cm"257b2bSf*Qa/"®=&ðS¢Òpût£Ð`ç«^º,[öÄ©3¸YÝæ[%$>\D£(´õÓÆeUØRHáÄ¡ããîùK½ÊÆÇ:UBÍm¥·fèäBÓEwWOkQq×tÌVfè£g8·¨    q©ñäp-ÁgUÚ´Éõ'>r    Ê#"256bDb"
.\"'()-/:\_|J"f=.+sSN+/l~\K>+=

```

Try it online in the CJam interpreter.

### Idea

We start by joining all twelve signs using the string `<SP><LF>` as separator. We opt for the zodiac signs not to contain trailing spaces, so this allows to separate them easily.

The joined string is 542 bytes long. 236 of these bytes are spaces, which is almost half of them. We build an array that contains a 1 for every space and a 0 for every non-space. This way, encoding a space will only cost 1 bit.

Removing all spaces from the joined string, we are left with the characters `<LF>."'()-/:J\_|`. Assigning each of them a value (e.g., the index in this string) between 0 and 12

Finally, we decode the above base 2 and base 13 arrays as byte arrays.

In the final program, for a given input `DD MM`, we compute `(int(MM) + (int(DD) > 20)) % 12`, reverse the above process to obtain the array of all zodiac signs and select the proper one.

### Code

```
"03½åÙªWË#å¥ÜZ2ò'ýðDc}¦Ð£RÞ5ä<Üå§ÖÞYÏuäOe¤¶è2²|ZëßB«ô¬cm"

        e# Push the encoded space positions.

257b2b  e# Convert from base 257 to base 2.
Sf*     e# Replace 1's with spaces and 0's with empty strings.
Qa/     e# Split at empty strings.

"®=&ðS¢Òpût£Ð`ç«^º,[öÄ©3¸YÝæ[%$>\D£(´õÓÆeUØRHáÄ¡ããîùK½ÊÆÇ:UBÍm¥·fèäBÓEwWOkQq×tÌVfè£g8·¨ q©ñäp-ÁgUÚ´Éõ'>r    Ê#"

        e# Push the encoded non-space characters.

256bDb  e# Convert from base 256 to base 13.

"
.\"'()-/:\_|J"f=

        e# Replace each digit in base 13 by the corresponding character.

.+s     e# Interleave both arrays to create a string.
SN+/    e# Split at trailing spaces.
l~      e# Evaluate the input from STDIN.
\K>+    e# Add 1 to the month if the day is larger than 20.
=       e# Retrieve the corresponding element from the array.

```
> 7 votes

# Answer
# CJam, 324 bytes

```
"%[hÿìs5!zaÆT=ªñ=Û]ÌUMàûÓ»¦f¼³ëµ1þÈUÑyéC4¬u1T9KÍü!+Úøöà&J~âZ®uRtkRÿ+*ÐFeÜPý¤SÙËU7óÎ?LXÝ2D@0¶ÆÀ¡kÚçaçªñÜ§#iµ3L®ó&Ë'iºyè½?JS÷SjS`ösÓò»zjRoaÃIYrµ&M>ÍKaaúcg®Ð\p¨²:LqÜÝ¶o¯ÆkµúÒ4Ezú©æ¼xP»¸¯gd^ßg±>ï ÃºDÎÅ§@3Bßt\<GÒcû)ËûwíUÑdØoiTv>¤&ý°mÊ13ÛUÿØjª¬Ì±(¦¿çÍX4tõãÜÑ*ÃmÜ9ãSÁ3IþÜìÙ,"{_'~>33*32+-}%191bEb428Et"
 \"'()-./:\_a|J"f='a/q~\K>+=

```

My first attempt. Try it online
> 3 votes

# Answer
# Python 2, ~~961~~ ~~698~~ ~~692~~ 687 Bytes

Definitely still going to golf further, just wanted to put an idea down. Now using a dictionary.

```
a,b=raw_input().split()
b=int(b)
c='.-"-._.-"-._.-'
print{0:c+'\n'+c,1:"'-.    .-'\n   :  :\n --:--:--\n   :  :\n.-'    '-.",2:" .-.   .-.\n(_  \ /  _)\n     |\n     |",3:" .     .\n '.___.'\n .'   '.\n:       :\n:       :\n '.___.'",4:"._____.\n  | |\n  | |\n _|_|_\n'     '",5:"   .--.\n  /   _'.\n (_) ( )\n'.    /\n  '--'",6:"  .--.\n (    )\n(_)  /\n    (_.",7:" _\n' ':--.--.\n   |  |  |_\n   |  |  | )\n   |  |  |/\n        (J",8:"     __\n___.'  '.___\n"+'_'*12,9:" _\n' ':--.--.\n   |  |  |\n   |  |  |\n   |  |  |  ...\n         '---':",10:"      ...\n      .':\n    .'\n'..'\n.''.",11:"        _\n\      /_)\n \    /'.\n  \  /   :\n   \/ __.'"}[[[b-2,11][b<2],b-1][int(a)>20]]

```

Old method, using interleaving.

```
d,m=raw_input().split()
m=int(m)
print'.\'  .       --.._  _ _  ".- _ .\n \n  - . _.-\' \'  .   _--     _   _-.\'_\'  .   ..\n:_:. -...\n\n -\n-. "--\n  (-_-._-\'.    ._.\n\n.\n\n\'|/ -_- \\_ (.   -.-  . __|  .\'.  -  _\n )\n \n  \n: _ _\n     . \\. \'( \'   -  \'|._ . . ":/\n \n)|_|\'/-\n  |   _ :_.  .\n(  _ \n)_-_\' _/|\n| \n.-) _)\n _   -:\n |   _  \\"-  _( |_|  -- \'|  __\n. .: ._) \n_ \' _- \n\n\n( _ \n .- :\'\'_ _ \'/-\n|  .. _|.\'  \n    |_ ..        _ \'\n        _|\n  :     |_ .     \'/    \'\\     \n   |\'  :|:   | \n.  \n \n       / . : \' )     -   - \n     \'   -   |       \'     :           \n       | |               \'           - :   | | \\ . \n       /               \'   | . _   .   / . _   _   \n . .   _     \n \'   _           .           \'                                                               (           J             \'           -           -           -           \'           :  '[[m-2,m-1][int(d)>21]::12].rstrip()

```
> 2 votes

# Answer
# Python 2, ~~565~~ ~~568~~ 553 bytes

```
def z(d,m):b="\n "+"  |"*3;c=" _\n' ':--.--.";a="  ...\n      ";print["\      /_)\n \    /'.\n  \  /   :\n   \/ __.'",'.-"-._.-"-._.-\n'*2,"'-.    .-'\n   :  :\n --:--:--\n   :  :\n.-'    '-.",' .-.   .-.\n(_  \ /  _)'+'\n     |'*2," .     .\n '.___.'\n .'   '.\n:       :\n:       :\n '.___.'","._____.\n  | |\n  | |\n _|_|_\n'     '","   .--.\n  /   _'.\n (_) ( )\n'.    /\n  '--'",'  .--.\n (    )\n(_)  /\n    (_.',c+b+"_"+b+" )"+b+"/\n        (J","     __\n___.'  '.___\n"+"_"*12,c+b*3+a+"   '---':","    "+a+".':\n    .'\n'..'\n.''."][m%12-(d<21)]

```

So I was a bit lazy and decided not to golf this AAotD. Instead, I decided to let python golf itself.

The above solution was created using the code below:

```
full_string = """
\      /_)
 \    /'.
  \  /   :
   \/ __.'
*
.-"-._.-"-._.-
.-"-._.-"-._.-
*
...               # The others in this list as well
*
      ...
      .':
    .'
'..'
.''.
"""

# Golf the input string
string_list = full_string.split('*')
# Remove begin and end \n
string_list = [s[1:-1] for s in string_list]
# Remove unnescessary repr characters
golf = repr(string_list).replace(r'\\ ', r'\ ').replace(r'\\/', r'\/').replace(', ', ',')
# Special case for the Aquarius as it's a full duplicate
middle = golf.find('\\n', 50)
end = golf.find(',', middle)
golf = golf[0:middle+2] + "'*2" + golf[end:]
# Special case for the 12 underscores
golf = golf.replace('____________"', '"+"_"*12')
# Replace the three bars and their whitespace
golf = golf.replace('\\n   |  |  |', '"+b+"')
# Replace the bar-cover
cover = '" _\\n\' \':--.--."'
golf = golf.replace(cover, 'c')
# Replaces aries' foot
golf = golf.replace("\\n     |\\n     |'", "'+'\\n     |'*2")
# Replace dots
golf = golf.replace('  ...\\n      ', '"+a+"')
# Remove empty strings and optimize b's
golf = golf.replace('""+', '').replace('b+b+b', 'b*3')

# Surround the lookup table with the function that that prints the correct zodiac sign for the day/month
golf = 'def z(d,m):a="  ...\\n      ";b="\\n "+"  |"*3;c=" _\\n\' \':--.--.";print' + golf + '[m%12-(d<21)]'

```
> 2 votes

# Answer
# Perl, 414

Not a lot to do here, just applied dictionary compression:

```
#!perl -p
/ /;$i=$'%12-($`<21);
$_="cc_
\\ct_s \\c/'ga\\thlh\\/ __ijkee
keej'-.ck'n q:q:qnk'c'-gA k.hkg(_a\\ /a_sm|
m|j .mg oi
 ih'g:chl:chl oij.d__grr _|_|_
'm'jhk-gth_'g (_) ( s'.c/
a'q'jak-g (cs(_)t
c(_.f_b )b/
cc(Jjm__
diao
ddddfbbpm'q-':jcpailci
'.i
i'g";
1while s![a-t]!(split z,"  z
a |a|a|zaaz___z\"-._.-z
A _
' ':--.--.bz.
za z.'z
Az.-z:
zc z
h:alz'.dza..gcz--za| |
z)
za/")[(ord$&)%97]!e;$_=(split A)[$i]

```

Test me.
> 1 votes

---
Tags: code-golf, ascii-art, kolmogorov-complexity
---


title: Chute-A-Pearing

text:
# Question
Title: Chute-A-Pearing
Here are five images of pears and a steel chute:

> **A:** **B:** **C:** **D:** **E:**
>
> **These are only thumbnails, click them for full size!**

<sup>(I made these with Algodoo.)</sup>

This class of images always has the following properties:

1. They are always 400×400 pixels with a white background. (It may not be exactly white since SE images are lossily compressed.)
2. They have 1 to 4 identical pears, each rotated and positioned in (almost) any way.
3. They have one vertical steel chute that reaches to the bottom of the image.
4. Other than the bottom of the chute, the chute and the pear bounding boxes (bounding box example) never touch or go out of the image bounds.
5. The bounding boxes of the pears never overlap each other nor overlap the chute.
6. The pears may be under the sloped part of the chute, as in **B**, **C**, and **D**. (So the bounding box of the chute may overlap the bounding box of a pear.)
7. The chute may have any horizontal and vertical position as long as there is enough room for all the bounding boxes of the pears to fit freely above it (no "barely fits" cases will be tested) and part of the column portion is visible.

# Challenge

Write a program that takes in such an image and outputs another 400×400 image with the chute in the same place, but with the pears repositioned so they are all above the chute (so they can fall into it and be juiced and whatnot).

The requirements for the output image are:

1. All the pears in the input image must be repositioned such that they are above the chute, between the left and right edge of its funnel. (Above an edge is **not** ok.)
2. Each pear must maintain its rotation angle. (So you should be cutting and pasting the pears, not redrawing them.)
3. The pears must not overlap or touch each other or the chute. (The pear *bounding boxes* may overlap though.)
4. The pears must not touch or go out of the image bounds.

Here are examples of valid outputs for the five sample images:

> **A:** **B:** **C:** **D:** **E:**
>
> **These are only thumbnails, click them for full size!**

Note that the input image for **E** was already a valid output, but rearranging the pears when not technically necessary is just fine.

## Details

* Take the filename of the image or the raw image data via stdin/command line/function call.
* Output the image to a file with the name of your choice or output the raw image file data to stdout or simply display the image.
* Any common lossless image file format may be used.
* Graphics and image libraries may be used.
* A few incorrect pixels here and there (due to lossiness or something) is not a big deal. If I can't tell anything is wrong visually then it's probably alright.

**The shortest code in bytes wins. Tiebreaker is highest voted post.**

# Answer
# Python 2.7, 636 bytes

```
import sys;from PIL.Image import*
_,m,R,I,p,H=255,400,range,open(sys.argv[1]).convert('RGB'),[],0
w,h=I.size;W,A,P,L=(_,_,_),[(x,y)for x in R(w)for y in R(h)],I.load(),I.copy()
try:
 while 1:
    s,x,y,X,Y=[[a for a in A if P[a][0]<50][0]],m,m,0,0
    while s:c=(a,b)=s.pop();x,y,X,Y=min(x,a),min(y,b),max(X,a),max(Y,b);P[c]=W;s+=[n for n in[(a+1,b),(a,b+1),(a-1,b),(a,b-1)]if n in A and P[n]!=W]
    p+=[((x,y,X,Y),X-x,Y-y)]
except:0
def G(a):r,g,b=P[a];return r==g==b and r<_
g=[a for a in A if G(a)]
(z,t),W=g[0],max([x for x,y in g]);t-=1
for r,w,h in p:
 if z+w>W:z,_=g[0];t-=H;H=0
 I.paste(L.crop(r),(z,t-h,z+w,t));z+=w;H=max(h,H)
I.show()

```

**EDIT** : now removes the alpha channel before handling the image, and aligns the pears on several rows if necessary

Produced images :

and with vertical pears (takes around 3 minutes on my computer):
> 6 votes

---
Tags: code-golf, graphical-output, geometry, image-processing
---


title: Build a readability index

text:
# Question
Title: Build a readability index
The Flesch-Kincaid readability algorithm depends on the measures of word count and syllable count, neither of which is entirely objective, or easily automatable using a computer. For example, does "code-golf", with the hyphen, count as one word or two? Is the word "million" two or three syllables? In this task, you will need to approximate, as counting exactly will take too much time, space, and most importantly, code.

Your task is to build the smallest possible program (i.e. a function) in any language that will take an English reading passage (assumed to be in complete sentences), and calculate the Flesch Reading Ease index to a tolerance of eight points (to account for variations in syllable counting and word counting). It is calculated as follows:

```
FRE = 206.835 - 1.015 * (words per sentence) - 84.6 * (syllables per word)

```

Your program must be aligned to the reference passages below, whose indices were calculated using manual counting:

```
I would not, could not, in the rain.
Not in the dark, not on a train.
Not in a car, not in a tree.
I do not like them, Sam, you see.
Not in a house, not in a box.
Not with a mouse, not with a fox.
I will not eat them here or there.
I do not like them anywhere!

```

Index: 111.38 (64 syllables in 62 words in 8 sentences)

```
It was a bright cold day in April, and the clocks were striking thirteen.
Winston Smith, his chin nuzzled into his breast in an effort to escape
the vile wind, slipped quickly through the glass doors of Victory Mansions,
though not quickly enough to prevent a swirl of gritty dust from entering
along with him.

```

Index: 65.09 (74 syllables in 55 words in 2 sentences)

```
When in the Course of human events, it becomes necessary for one people to
dissolve the political bands which have connected them with another, and to
assume among the powers of the earth, the separate and equal station to
which the Laws of Nature and of Nature's God entitle them, a decent respect
to the opinions of mankind requires that they should declare the causes
which impel them to the separation.

```

Index: 3.70 (110 syllables in 71 words in 1 sentence)

If you have any other passages for which you have manually counted the syllables and words and calculated the index, you may show them as verification.

# Answer
## Perl 120 bytes

```
#!perl -pa0
s@\w+|([.!?])@$s+=$#-,lc($&)=~s![aeiou]+\B|([aeiouy]$)!$y+=1-$#-/3!ger@ge}
{$_=206.835-1.015*@F/$s-84.6*$y/@F

```

Sample I/O:

```
$ perl flesch-kincaid.pl < input1.dat
110.730040322581

$ perl flesch-kincaid.pl < input2.dat
65.6097727272728

$ perl flesch-kincaid.pl < input2.dat
1.71366197183096

```

Counting of syllables is done by assuming that each vowel cluster is a single syllable, except for lone vowels at the end of a word, which are only counted two thirds of the time; a heuristic that seems to be fairly accurate.
> 6 votes

# Answer
## K&R c -- 188 ~~196~~ ~~199~~ ~~229~~ characters

With the spec changed to specify a function I can get of lot of the c overhead out of the count. Also changing to use Strigoides' syllable counting hack which is better than my formula tweak and extended to deal with overcounting of words.

After I found a shorter way to do the vowel detection which was sadly based on `stdchr`, I had incentive to squeeze a few more out of the bit-twiddling abomination I've been using so that I didn't have to be boring.

```
d,a,v,s,t,w;float R(char*c){for(;*c;++c){s+=*c=='.';if(isalpha(*c)){
w+=!a++;d=(*c&30)>>1;if(*c&1&(d==7|((!(d&1))&(d<6|d>8)))){t+=!v++;}
else v=0;}else v=a=0;}return 206.835-1.*w/s-82.*t/w;}

```

The logic here is a simple state machine. It counts sentences by periods only, words by strings of alphabetic characters, and syllables as strings of vowels (including y).

I had to diddle the constants a little to get it to come out with the right figures, but I've borrowed Strigoides' trick of just undercounting the syllables by a fixed fraction.

**Un-golfed**, with comments and some debugging tools:

```
#include <stdlib.h>
#include <stdio.h>
d,a,/*last character was alphabetic */
  v,/*lastcharacter was a vowel */
  s, /* sentences counted by periods */
  t, /* syllables counted by non-consequtive vowels */
  w; /* words counted by non-letters after letters */
float R/*eadability*/(char*c){
  for(;*c;++c){
    s+=*c=='.';
    if(isalpha(*c)){ /* a letter might mark the start of a word or a
               vowel string */
      w+=!a++; /* It is only the start of a word if the last character
              wasn't a letter */
      /* Extract the four bits of the character that matter in determining
       * vowelness because a vowel might mark a syllable */
      d=(*c&30)>>1;
      if( *c&1  & ( d==7 | ( (!(d&1)) & (d<6|d>8) ) )
      ) { /* These bits 7 or even and not 6, 8 make for a
         vowel */
    printf("Vowel: '%c' (mangled as %d [0x%x]) counts:%d\n",*c,d,d,!v);
    t+=!v++;
      } else v=0; /* Not a vowel so set the vowel flag to zero */
    }else v=a=0; /* this input not alphabetic, so set both the
            alphabet and vowel flags to zero... */
  }
  printf("Syllables: %3i\n",t);
  printf("Words:     %3i       (t/w) = %f\n",w,(1.0*t/w));
  printf("Sentences: %3i       (w/s) = %f\n",s,(1.0*w/s));
  /* Constants tweaked here due to bad counting behavior ...
   * were:       1.015     84.6 */
  return 206.835-1.   *w/s-82. *t/w;
}
main(c){
  int i=0,n=100;
  char*buf=malloc(n);
  /* Suck in the whole input at once, using a dynamic array for staorage */
  while((c=getc(stdin))!=-1){
    if(i==n-1){ /* Leave room for the termination */
      n*=1.4;
      buf=realloc(buf,n);
      printf("Reallocated to %d\n",n);
    }
    buf[i++]=c;
    printf("%c %c\n",c,buf[i-1]);
  }
  /* Be sure the string is terminated */
  buf[i]=0;
  printf("'%s'\n",buf);
  printf("%f\n",R/*eadability*/(buf));
}

```

**Output:** (using the scaffold from the long version, but the golfed function.)

```
$ gcc readability_golf.c
readability_golf.c:1: warning: data definition has no type or storage class
$ ./a.out < readability1.txt
'I would not, could not, in the rain.
Not in the dark, not on a train.
Not in a car, not in a tree.
I do not like them, Sam, you see.
Not in a house, not in a box.
Not with a mouse, not with a fox.
I will not eat them here or there.
I do not like them anywhere!
'
104.074631
$ ./a.out < readability2.txt
'It was a bright cold day in April, and the clocks were striking thirteen.
Winston Smith, his chin nuzzled into his breast in an effort to escape
the vile wind, slipped quickly through the glass doors of Victory Mansions,
though not quickly enough to prevent a swirl of gritty dust from entering
along with him.
'
63.044090
$ ./a.out < readability3.txt
'When in the Course of human events, it becomes necessary for one people to
dissolve the political bands which have connected them with another, and to
assume among the powers of the earth, the separate and equal station to
which the Laws of Nature and of Nature's God entitle them, a decent respect
to the opinions of mankind requires that they should declare the causes
which impel them to the separation.
'
-1.831667

```

**Deficiencies:**

* The sentence counting logic is wrong, but I get away with it because only one of the inputs has a `!` or a `?`.
* The word counting logic will treat contractions as two words.
* The syllable counting logic will treat those same contractions as one syllable. But probably overcounts on average (for instance `there` is counted as two and many words ending in `e` will be counted one too many), so I've applied a constant factor of 96.9% correction.
* Assumes a ASCII character set.
* I believe the vowel detection will admit `[` and `{`, which clearly isn't right.
* Lots of reliance on K&R semantics makes this ugly, but hey, it's code golf.

**Things to look at:**

* I am (momentarily) ahead of both python solution here, even if I am trailing the perl.
* Get a load of the horrible thing I did for detecting vowels. It makes some sense if you write the ASCII representations out in binary and read the comment in the long version.
> 3 votes

# Answer
## Python, ~~202~~ ~~194~~ ~~188~~ ~~184~~ ~~171~~ 167 characters

```
import re
def R(i):r=re.split;w=len(r(r'[ \n]',i));s=r('\\.',i);y=r('[^aeiou](?i)+',i);return 206.835-1.015*w/(len(s)-s.count('\n'))-84.6*(len(y)-y.count(' ')-2)*.98/w

```

First, get the total number of words by splitting along spaces and newlines:

```
w=len(r(r'[ \n]',i))

```

Then, the formula. Sentence and syllable counts are only used once, so they are embedded in this expression.

Sentences are simply the input split along `.`, with newlines filtered out:

```
s=r('\\.',i);s=len(s)-s.count('\n')

```

Syllables consist of the input split along non-vowels, with spaces removed. This seems to consistently slightly over-estimate the number of syllables, so we need to adjust it down (about .98 seems to do it):

```
y=r('[^aeiou](?i)+',i);y=len(y)-y.count(' ')-2;

```

**202 -\> 194:** `len(x)-2` rather than `len(x[1:-1])`. Removed unnecesary brackets. Made syllable regex case-insensitive

**194 -\> 188:** The file was previously saved as dos rather than unix file format, causing `wc -c` to count newlines as two characters. Whoops.

**188 -\> 184:** Get rid of those nasty `x for x in ... if x!=...`s by storing the intermediate result and subtracting `x.count(...)`

**184 -\> 171:** Remove input/output, and convert to function

**171 -\> 167:** Insert the `len(x)-x.count(...)`s into the formula
> 2 votes

# Answer
# Python 380 characters

```
import re
def t(p):
 q=lambda e: e!=''
 w=filter(q,re.split('[ ,\n\t]',p))
 s=filter(q,re.split('[.?!]',p))
 c=len(w)*1.0
 f=c/len(s)
 return w,f,c
def s(w):
 c= len(re.findall(r'([aeiouyAEIOUY]+)',w))
 v='aeiouAEIOU'
 if len(w)>2 and w[-1]=='e'and w[-2]not in v and w[-3]in v:c-= 1
 return c
def f(p):
 w,f,c=t(p)
 i=0
 for o in w:
  i+=s(o)
 x=i/c
 return 206.835-1.015*f-84.6*x

```

This is a rather long solution, but it works well enough, at least of the 3 test cases provided it does.

Testing code

```
def test():
 test_cases=[['I would not, could not, in the rain.\
        Not in the dark, not on a train.\
        Not in a car, not in a tree.\
        I do not like them, Sam, you see.\
        Not in a house, not in a box.\
        Not with a mouse, not with a fox.\
        I will not eat them here or there.\
        I do not like them anywhere!', 111.38, 103.38, 119.38],\
        ['It was a bright cold day in April, and the clocks were striking thirteen.\
        Winston Smith, his chin nuzzled into his breast in an effort to escape\
        the vile wind, slipped quickly through the glass doors of Victory Mansions,\
        though not quickly enough to prevent a swirl of gritty dust from entering\
        along with him.', 65.09, 57.09, 73.09],\
        ["When in the Course of human events, it becomes necessary for one people to\
        dissolve the political bands which have connected them with another, and to\
        assume among the powers of the earth, the separate and equal station to\
        which the Laws of Nature and of Nature's God entitle them, a decent respect\
        to the opinions of mankind requires that they should declare the causes\
        which impel them to the separation.", 3.70, -4.70, 11.70]]
 for case in test_cases:
  fre= f(case[0])
  print fre, case[1], (fre>=case[2] and fre<=case[3])

if __name__=='__main__':
 test()

```

Result -

```
elssar@elssar-laptop:~/code$ python ./golf/readibility.py
108.910685484 111.38 True
63.5588636364 65.09 True
-1.06661971831 3.7 True

```

I used the syllable counter from here - Counting syllables

A more readable version is available here
> 1 votes

# Answer
# Javascript, 191 bytes

```
t=prompt(q=[]);s=((t[m="match"](/[!?.]+/g)||q)[l="length"]||1);y=(t[m](/[aeiouy]+/g)||q)[l]-(t[m](/[^aeiou][aeiou][s\s,'.?!]/g)||q)[l]*.33;w=(t.split(/\s+/g))[l];alert(204-1.015*w/s-84.5*y/w)

```

First test case gives 112.9 (correct answer is 111.4, off by 1.5 points)

Second test case gives 67.4 (correct answer is 65.1, off by 2.3 points)

Third test case gives 1.7 (correct answer is 3.7, off by 2.0 points)
> 0 votes

---
Tags: code-golf, natural-language
---


title: What's the time?

text:
# Question
Title: What's the time?
I like to save time quite literally, by wearing three watches on my wrist... Problem is they each give a different time. One watch is x minutes behind the actual time. One watch is x minutes ahead of the actual time. The last watch shows the actual time.

Problem is, I can't tell which watch has the correct time...

From the time displayed on each watch, determine the actual time. If it is not possible to determine the time, print "Look at the sun".

**Input:** Three readings, separated by single space characters: `H1:M1 H2:M2 H3:M3` In each reading H1,H2,H3 represent the hours displayed (0 \< H1,H2,H3 \< 13), and M1,M2,M3 represent the minutes displayed (0 \<= M1,M2,M3 \< 60). If the number of minutes is less than 10, a leading 0 is prepended in the input. Similarly, is the number of hours is less than 10, a leading 0 is prepended in the input.

**Output:** `The correct time is HH:MM` where HH:MM is the correct time. If no correct time can be determined, it displays `Look at the sun`.

**Input 1:** `05:00 12:00 10:00`

**Output 1:** `The correct time is 05:00`

**Input 2:** `11:59 12:30 01:01`

**Output 2:** `The correct time is 12:30`

**Input 3:** `12:00 04:00 08:00`

**Output 3:** `Look at the sun`

Shortest code wins... No special penalties apply. Also, bear in mind that we're dealing with a 12-hour clock... I don't care about AM or PM... Imagine we're dealing with analogue watches...

# Answer
# CJam, ~~86~~ ~~83~~ ~~77~~ ~~75~~ 71 bytes

```
"The correct time is "ea{aea+':f/60fb(f-:+720%!},{];"Look at the sun"}*

```

*Thanks to @jimmy23013 for golfing off 6 bytes from my code.*

Try it online in the CJam interpreter.

### Test cases

```
$ cjam time.cjam 05:00 12:00 10:00; echo
The correct time is 05:00
$ cjam time.cjam 11:59 12:30 01:01; echo
The correct time is 12:30
$ cjam time.cjam 12:00 04:00 08:00; echo
Look at the sun

```

### How it works

```
"The correct time is "
        e# Push that string.
ea      e# Push the array of command-line arguments.
{       e# Filter; for each time T:
  a     e#   Wrap T in an array.
  ea+   e#   Concatenate with the array of all times.
  ':f/  e#   Split each time at the colon.
  60fb  e#   Consider it a base 60 integer.
  (f-   e#   Shift out the converted T and subtract it from the remaining times.
  :+    e#   Add them.
  720%! e#   Push 1 is the sum is 0 modulo 720 and 0 if not.
},      e#   Keep the time iff a 1 has been pushed.

        e# The array on the stack now contains one or three times.

{       e# Reduce; for each time but the first:
  ];    e#   Discard the entire stack.
  "Look at the sun"
        e#   Push that string.
}*      e#

```
> 10 votes

# Answer
# JavaScript (*ES6*), 164 ~~168 172~~

For each reading, calc the distance from the other two. The one that have the same distance is what you need. If there is more than one, then you can't tell.

```
F=s=>(s=s.split(' '))
  .map(x=>([h,m]=x.split(':'),+m+(h%12)*60))
  .map((v,i,z)=>(v+v-z[++i%3]-z[++i%3])%720||'The correct time is '+s[k+=i],k=-2)
[k]||'Look at the sun'

// TEST

out=x=>O.innerHTML += x+'\n';

['12:30 01:01 11:59', '11:50 11:55 12:00', '05:00 12:00 10:00', '12:10 04:10 08:10', '07:00 06:00 08:00']
.forEach(x => out(x + ' -> ' + F(x)))

go=_=>out(I.value + ' -> ' + F(I.value))
```

```
<pre id=O></pre>
<input id=I><button onclick="go()">Test</button>
```
> 7 votes

# Answer
# Python 3, ~~166~~ 163 bytes

```
L=input().split()
f=lambda x:int(x[:2])*60+int(x[3:])
s=""
for a in L:s=[s,s and"Look at the sun"or"The correct time is "+a][(sum(map(f,L))-3*f(a))%720<1]
print(s)

```

Uses

```
      a-b == b-c
<==>  a+c-2*b == 0
<==>  (a+b+c)-3*b == 0

```

with arithmetic being minutes modulo 720.
> 4 votes

# Answer
# Python 2, ~~254~~ ... ~~199~~ ~~207~~ ~~203~~ ~~194~~ 200 Bytes

Probably a few ways to shorten this, give me some time..

```
t=[x.split(':')for x in raw_input().split()]
a,b,c=[int(x[0])*60+int(x[1])for x in t]
print["The correct time is "+':'.join(t[[(c+a)%720%(b/2)<1,2][(a+b)%720%(c/2)<1]]),"Look at the sun"][(a-b)%240<1]

```

Thanks to Sp3000 helping me fix this.
> 2 votes

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


title: Translate RoboCritters into Brainf***

text:
# Question
Title: Translate RoboCritters into Brainf***
RoboCritters (etymology) is a brand new esoteric programming language (don't bother searching for it, I just invented it). It's a variant of Brainfuck (BF), slightly more complex than the usual operator substitution schemes. Every program in RoboCritters is a rectangular grid of text that only contains the seven characters `. []/\|`, plus newlines to shape the grid.

Example RoboCritters program:

```
|\/||./|[]||
[..][][]   |
|/\|[..][..]
[..]    \/\/

```

To translate a RoboCritters program into BF, look at each non-newline character in the grid in the normal reading order (left-to-right then top-to-bottom), e.g. `|\/||./|[]||[..][][] ||/\|[..][..][..] \/\/`.

If the 4×2 section of the grid extending right and down from the current character exactly matches one of the eight *robot critters* listed below, append the corresponding BF command (`><+-.,[]`) to the (initially empty) BF program.

If the 4×2 grid section **does not match** any of the robot critters or **goes out of bounds**, nothing is added to the BF program.

1. Joybot, `>` command:

```
[..]
\][/

```
2. Calmbot, `<` command:

```
[..]
/][\

```
3. Squidbot, `+` command:

```
[..]
//\\

```
4. Spiderbot, `-` command:

```
[..]
||||

```
5. Bunnybot, `.` command:

```
[][]
[..]

```
6. Toothbot, `,` command:

```
[..]
|/\|

```
7. Foxbot, `[` command:

```
|\/|
[..]

```
8. Batbot, `]` command:

```
[..]
\/\/

```

So, reading the example program

```
|\/||./|[]||
[..][][]   |
|/\|[..][..]
[..]    \/\/

```

we can see that we first encounter a Foxbot (at column 1, row 1), then a Toothbot (c1,r2), then a Bunnybot (c5,r2), and finally a Batbot (c9,r3). This corresponds to the BF program `[,.]`.

Notice that the Foxbot and Toothbot overlap. This is intentional; **robot critters are not interpreted any differently when they overlap**.

# Challenge

Write the shortest program possible that takes in a RoboCritters program and outputs its BF equivalent. You don't need to run the BF or check that it's valid, only translate the RoboCritters code to BF code.

### Details

* All input RoboCritters programs will be valid, that is they will be an exactly rectangular block of text only containing the seven characters `. []/\|`, plus newlines to shape it. The newlines may be in any convenient common representation. You may optionally assume the programs have a single trailing newline.
* **You must support RoboCritters programs that are smaller than 4×2, including the 0×0 empty (or single newline) program. These all correspond to the empty BF program (the empty string).**
* The output BF program should be a one-line string only containing the eight BF command characters `><+-.,[]`. There may optionally be a single trailing newline.
* Take input in any usual way (stdin/text file/command line) and output to stdout or your language's closest alternative.
* Instead of a program you may write a function that takes the RoboCritters program as a string and prints or returns the BF program string.

# Examples

1. Input: (variant of example above)

```
|\/|[][]
[..][][]
|/\|[..]
    \/\/

```

Output: `[,.]`
2. Input: (tests all robot critters)

```
[..][[[[[..]]. ]|\/|
\][/[..]//\\[..][..]
[..]/][\[][]|/\|[..]
||||/\| [..]|  |\/\/

```

Output: `>+[<,-.]`
3. Input:

```
[..] [..] [..] [..] [..] [..] [..] [..] |\/| [..] [..] [..] [..] [..] |\/| [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] [..] |\/| [..] [..] [..] [..] [..] [..] [..] [][] [..] [..] [..] [..] [][] [..] [..] [..] [..] [..] [..] [..] [][] [][] [..] [..] [..] [][] [..] [..] [][] [..] [..] [][] [..] [][] [..] [..] [..] [][] [..] [..] [..] [..] [..] [..] [][] [..] [..] [..] [..] [..] [..] [..] [..] [][] [..] [..] [..] [][] [..] [..] [..] [][]
//\\ //\\ //\\ //\\ //\\ //\\ //\\ //\\ [..] \][/ //\\ //\\ //\\ //\\ [..] \][/ //\\ //\\ \][/ //\\ //\\ //\\ \][/ //\\ //\\ //\\ \][/ //\\ /][\ /][\ /][\ /][\ |||| \/\/ \][/ //\\ \][/ //\\ \][/ |||| \][/ \][/ //\\ [..] /][\ \/\/ /][\ |||| \/\/ \][/ \][/ [..] \][/ |||| |||| |||| [..] //\\ //\\ //\\ //\\ //\\ //\\ //\\ [..] [..] //\\ //\\ //\\ [..] \][/ \][/ [..] /][\ |||| [..] /][\ [..] //\\ //\\ //\\ [..] |||| |||| |||| |||| |||| |||| [..] |||| |||| |||| |||| |||| |||| |||| |||| [..] \][/ \][/ //\\ [..] \][/ //\\ //\\ [..]

```

Output: (BF Hello World program)

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

```
4. Input: (no robot critters present)

```
/\\\[].
]..[..]
\\//||\

```

Output: (empty string)

# Scoring

The shortest submission in bytes wins. (Handy byte counter.) Tiebreaker is highest voted post.

# Answer
> 9 votes
# CJam, ~~86~~ 85 bytes

```
qN/S4*f+_W<\1>]z:z4few:~"¨Ý³5&ágûò{wÉ](Ý"296b6b"|[\.]/"f=2/4/"><+-.,[]":Ler{L&},

```

Test it here.

## Explanation

```
qN/    e# Read input and split into lines.
S4*f+  e# Append four spaces to each line. This has two purposes. a) We can later join all
       e# the lines together without worrying about critters appearing across the line
       e# edges because no critter contains spaces. b) It works around a bug in CJam where
       e# the command `ew` crashes when the substring length is longer than the string.
_W<    e# Copy the lines and discard the last one.
\1>    e# Swap with the other copy and discard the first one.
]z     e# Wrap both in an array and zip them up. Now we've got an array which contains
       e# all consecutive pairs of lines.
:z     e# Zip up each of those pairs, such it becomes an array of two-character strings.
       e# We can now find the critters as 4-element subarrays in each of those arrays.
4few   e# Turn each of those arrays into a list of its (overlapping) 4-element subarrays.
:~     e# Flatten those lists, such that we get one huge array of all 4x2 blocks, in order.
"gibberish"296b6b
       e# This is an encoded form of the critters. The above produces a string of the
       e# critters in column-major order, all joined together, where the characters are
       e# represented by numbers 0 to 5.
"|[\.]/"f=
       e# Turn each number into the correct character.
2/4/   e# Split first into columns, then into critters. Now all we need to do is find these
       e# the elements of this array in the processed input.
"><+-.,[]":L
       e# A string of all BF characters in the same order as the critters. Store this in L.
er     e# Do an element-wise replacement. This will leave non-critter blocks untouched.
{L&},  e# Filter the result. The elements are now either characters, or still full 4x2
       e# blocks. We take the set intersection with the array (string) of BF characters.
       e# If the current element is itself a character, it will be coerced into an array
       e# containing that character, such that we get a non-empty intersection. If the
       e# current element is a block instead, if contains arrays itself, so the set
       e# intersection will always be empty.

       e# The resulting array of characters is the desired BF program and will be printed
       e# automatically at the end of the program.

```

The critters were encoded with this script. I found the base 296 for the encoding with the following, rather naive Mathematica script (which is still running in search for a better base):

```
b = 256;
While[True,
  If[
    FreeQ[
      d = IntegerDigits[15177740418102340299431215985689972594497307279709, b],
      x_ /; x > 255
    ],
    Print@{b, Length@d}
  ];
  b += 1;
]

```

# Answer
> 4 votes
# JavaScript ES6, ~~209~~ ~~198~~ 192 bytes

```
f=c=>{s=''
b=o=>c.substr(o,4)||1
for(i in c)s+=!~(d='1\\][/1/][\\1//\\\\1||||[][]11|/\\||\\/|11\\/\\/'.replace(/1/g,'[..]').indexOf(b(i)+b(++i+c.search(`
`))))|d%8?'':'><+-.,[]'[d/8]
return s}

```

The Stack Snippet below contains ungolfed code that you can easily run in any browser.

```
var f = function(c) {
  var s = '';
  var b = function(o) {
    // If it is looking on the last line, this will return an empty string
    // the second time, which could cause an inaccurate match.
    // `||1` makes it return 1 instead of '', which won't match.
    return c.substr(o, 4) || 1;
  }
  for (var i in c) {
    r = b(i) + b(++i + c.search('\n'));
    d = '1\\][/1/][\\1//\\\\1||||[][]11|/\\||\\/|11\\/\\/'.replace(/1/g, '[..]').indexOf(r);
    s += !~d || d % 8 ? '' : '><+-.,[]' [d / 8];
  }
  return s;
}

// GUI code below
function run(){document.getElementById('s').innerHTML=f(document.getElementById('t').value);};document.getElementById('run').onclick=run;run()
```

```
<textarea id="t" cols="30" rows="10">
[..][[[[[..]]. ]|\/|
\][/[..]//\\[..][..]
[..]/][\[][]|/\|[..]
||||/\| [..]|  |\/\/</textarea><br /><button id="run">Run</button><br /><code id="s"></code>
```

---
Tags: code-golf, ascii-art, brainfuck, code-generation
---


title: Rearranging Words

text:
# Question
Title: Rearranging Words
You should write a program which receives two strings as input and outputs a sequence of movements which rearrange the first string into the second. You should use as few moves as you can.

Both strings will contain only lowercase letters and the second (goal) string is a permutation of the first (original) one.

Every move is described as `char_index:direction` where

* `char_index` is the 0-based index of the character in the original (first) string
* `direction` is one of `u d l r` corresponding to moving the selected character one step up, down, left or right.

You can only move a character to another position if **no other character is there**. The grid on which you can move the characters is infinite in every direction.

Your goal is to rearrange the letters of the first string so they take up the same area as at start but spell out the second string.

For example a valid move sequence for `abc` =\> `acb` would be `2:d 1:r 2:l 2:u` (4 moves):

```
| abc | ab  | a b | a b | acb |
|     |   c |   c |  c  |     |

```

Another move sequence for the same input is `2:r 2:d 1:u 1:u 1:r 1:d 1:d 2:l 2:l 2:u` (10 moves):

```
|      |      |      |      |  b   |   b  |      |      |      |      |      |
|      |      |      |  b   |      |      |   b  |      |      |      |      |
| abc  | ab c | ab   | a    | a    | a    | a    | a b  | a b  | a b  | acb  |
|      |      |    c |    c |    c |    c |    c |    c |   c  |  c   |      |

```

## Input

* Two strings (original and goal string) containing only the letters \[a-z\].
* The two strings are separated by a newline.

## Output

* A space separated list of moves.
* Each move has the format `char_index:direction` as described above.

## Scoring

* Your score is the **total number of moves** your program uses on the test case inputs. Lower score is better.
* In the event of a tie the earlier submission wins.
* Your submission is valid only if you ran your program on all the test cases and counted your score.
* You can validate your solutions with this python program. Provide input and output filenames as arguments or input and output as stdin (2 lines input and then 1line output).

## Test cases

*(Test cases are delimited by empty lines.)*

```
ehmwgzcyoaedeyvckivf
chacfveyvwdeyoigezkm

ymnrpltwdyvlgdrgndgx
ggydpnrwgrdyvtnmldxl

gfceetyxotezibswjcdh
oeefgjciehyxswtcdbtz

qdjqiffrqokkitndmufl
oqfrmfudqktikfjqilnd

sxgsugcylgsfgznrktgp
cgsylsgnggkzurgptfxs

izzbcpvwpkackqykurghocpptmbtfcdorlmterhyellurudblqlbldaheorilrfzoonicbfwksdqjjeujvqluktamaurafberdcua
lwrkcbnlllycaorcfklebodkrjuapdbdforulqosofieeqcpzaebuqmuthdurvtpkbmageurlzbiwkaymcvctfhuzprajtlrqjdih

wdbyrdzneneydomipmrjoposrgjvdwmeijrnozapnroqtnayqbfdiojnddcijpdkkmglrwktpsyaoctpenqbmcooksjpeqfrjkgym
wamcedyibsopqckcrdomrzgpirmfrdmdqonmyknpgrbnbkdotrejonyelioaqoksoinzgprtwfednvpjsntjdyoadkwyjjjqpjepm

bwfgxpbxiztsasxkhvdwuhtylvzcmctwxfjahbnbbolcbysbtxfmmrlvptqpvrxfbvfoqjwgrsarvngvigmixlcfpvqyrhcddjiyv
qpjbwvrvgbccptmwxofuqvvltpxacrsanwcmjbkolyhjzbithyqhvxfrsttdmzdbilmhvrfcwrvafygipgbvfnblxvxsybfgsxdxi

gozvqtqxmpjqjftuvbaevdkmjtzylyyjsryfahzsotygxsuzihfwfzfmrvvcaqejpkjqzxyzeoxotdabpmmbknycvvkqlpxpkfory
jvaboapseayzbymyjfvkrozyutvqqsjfxjxfqnttuvejyhqiqzctlfkyxrcmvxjmdooksdvyzrlhpakpbfpzfpgvkgmyzzqmtoxew

ishatpmxygjhxnndyzmmhpjregfmdvtfstgiojcxbstwcghtuckftwrwchepgojxkfgwnynximhnnovhdytmrtiugcmzkwweuudoi
fekopnynwgjvyojnizxcxmustpihhursiwhdhegrcgtkimxutmbgfchoeawmdmwfpkwwyhxdnftthsiuzmtmgtcjvngntrcoxydgj

ehigvxohaivehtdemdjofhkjrxtzsukaccxzyjpufyspfokjxkxztrcmchykhiwfnsgibnjfagntdowkpcogndrafknymzsrkqnelkfrfoltkhfvrwguwpgbkwovfyqpnzmagiakbaduurkgsdeylqemfjklglybdihxptzzxcffqqfoykfrtexhqxdpuwnqjwrnyugkrghwvazaihvjtofrcympsvgaeuorctqmabkokqmwraifdwmphxbbdqjm
gyotpajrrtelqgfezwacfvsinulknmzfpfrplwjxzawkarxkgiookfokjvxbhdqcphohcqmxfdwxksohgrhybzhtrfeksrqedznggxxfamjorwyomaqnliyapdnhvypfkzcdyjknnyxstpyrvggmhxcwrbpfguomksffqyrzhrcmukqaaabaehugifowtpdxiakuhtowvwttnkdbcjtuzfvueieukgdkmfncfwbmjkkdisblrkmhyigqfqvejjqd

lbudhpvhdrlsqmwhsrlzozowdkpesrawprfoqdilpcacboqdxbohnpgeogcqtlhruidvytylckgpdfnfqqvstivzkduttqjgfifcglhajmnzithbyzohiviwuudohppebyqnvhogsqwtywyfegkryxpjphoipiunnhfsbkdsieoqyebluppatgsawnwsaieujsxmanysxcdmjvvymcbqsxiqlihxidajwqrthhjhfncwoxmwumguvhtvxjtgoimd
tqzgsaafjtieekfrsjmxcvqshtxlyltqyoqwdwwowlszlhktiovciigewsdpwxcnhgglwmslcjinnsluxsooimkrpuytupgohfhycdpvcmshxfebqcxpaodiawfsgbwhqahdnvnrvmtqiddmjopdtxhvbwgqvhaihhhkiwjxfnidertpujupoiqrspavyjcqguhdedbpzhnyhhjbuiytqorrgypbbinslmfyqvpykziatulogfdmdqbunpeuzvoo

ryhphfyvyzgaabyqjyjhbsfixgxwdubtlljgjlmzlrbnsmkvjuxgszafnayywvrcbwmttocfppxhbjcqpvyunxkfvinfhnozgvolcowbcppvejiiljiagdmwxvrsblzxsyrsnaivkbnffdduwzkgtpvhmbxavzdcrhpxhnzzcupmekvufvfcfpxnqyoiruofwddwjzihffuvmfeyelwevqbjtsrkujalsambaepbajziptrujjorwhcozmegohho
fafdfvzedydrkyuudnngnzftohdwjrcvyfbtdwbjcmapgmeffpxicrvjuhszpvpplcrqkojvwbatngxizzkrdaehovampctaptrjgsyubawbvuirkvmzoziyozhbhurnflqmplsbhhhllhbxswrxbflxyylruyoftvpwephjowzaiajfehgkyiyobgxemobmjopmnufwswjxpqbsanjjficcmqvxzvfilucbjhcvuwenxzlsvvsxfznyvkjgjagi

zpsnvzghldshvllfrnwjwltecaopsuuucrnsjggcsirymywtmdzpmdoqylbtjavdtvwviohvjtldjdwjoumffmzjjmltcjqtjsryualzqfjdrcunbmquirqcdpcedlyznzkgtrpxldelkmogiutyfjwntjvzfmowcjzlnrivtlajrpowkxykbsxzvhsahsigobkunfxashtcbqmepiyhbuuyfwrbfoknivocyivznnethpcbmztyxfvekqfejcfe
oyetfwkgskcygvszugygtumojmljdcrhnlljgomnrzubcjjlcnyzvzfuyshdchxytbiljjirvvxdkfosfuitdedocwlnsmjmbemowpftabyltjumlwfzfufkurozzichcqwkqasdnimvdbdsjfpmhrkhlnzisvjpapmyrwedcgmudtqtjvtqwluawtqviktxnzyirlspqbnthfxtapbescjvcbohyqejfialrznrojnlfeevxrnpzczvtvyojupw

hhhhyyvnnbqgmiiaaabzoamiudppplwhmjkwjxstcgzprhjknhijcpqqwmcpkbzlngugifmdzyclsokhgogtntheztvwmugitijbmukjllxsgcazdwlfwyzhbkkvhdllfzhpnltfbbijcrpxyjpupqifevxxfbhzqjfjqfgadwgumqxkcocugjdwxkhorjsspdswqlzsdobtjeucpbfthumsscmfwkovwljvunikttgcgcawsevmlfhcpeupwazs
pdqpkzdfmlkjqagwmkyohwdkbchinefzcjmsngxbuptsultmytgagjkfvkscjdlswuujbrachvspfmlfgwplqfipeaobiiupghyoxeswuqschtrccwzpijcbotklzjmtvhgljfzerujmafwvphuhkcfhixacjalxjhlsxshzzdgwiqopxmdvtwhkfzwbgfsknvmgwthogbbvtphuwyqpmtpuqcobwkjihisldelcphylajcdigqbxunzjnmgznnz

```

# Answer
> 93 votes
# CJam, ~~58,598~~ ~~58,494~~ ~~57,898~~ ~~57,772~~ ~~57,704~~ 57,680 moves

This approach takes the family of *all* unordered sets of horizontal moves of minimum cardinality (with some false positives) and adds the minimum number (over all sets) of vertical moves required to avoid superpositions.

If the resulting number of horizontal moves is suboptimal (a false positive), it starts adding more vertical moves until the number of horizontal ones is optimal.

Finally, it orders the generated moves to form a valid sequence.

Try it online in the CJam interpreter.

### Animated test cases

Test case 1 | Test case 2 | Test case 3 | Test case 4 | Test case 5

Test case 6 | Test case 7 | Test case 8 | Test case 9 | Test case 10

*Thanks to @Doorknob for his help with the animations.*

### Test cases

```
$ time for f in xx*; do python3 val.py $f <(cjam prog.cjam < $f); done
move sequence verified with step count 156
move sequence verified with step count 126
move sequence verified with step count 120
move sequence verified with step count 124
move sequence verified with step count 112
move sequence verified with step count 2228
move sequence verified with step count 1862
move sequence verified with step count 2066
move sequence verified with step count 1738
move sequence verified with step count 1932
move sequence verified with step count 8200
move sequence verified with step count 10770
move sequence verified with step count 10360
move sequence verified with step count 8716
move sequence verified with step count 9170

real    0m22.672s
user    0m37.372s
sys     0m1.869s

```

### Pairing characters

Let's analyze the following example (provided by @randomra):

```
012345678
axabababa
abababaxa

```

By inspection, it suffices to swap the **x** with the **b** that takes its place, which can be done in 16 moves:

```
1:u 1:r 1:r 1:r 1:r 1:r 1:r 7:d 7:l 7:l 7:l 7:l 7:l 7:l 1:d 7:u

```

The minimum number of horizontal moves can always be achieved by pairing the nth occurrence of each letter in the first line with the nth occurrence in the second line. However, this is highly suboptimal in this case, since we have to add too many vertical moves to avoid superpositions.

The letter **x** occurs only once and there is only one optimal choice for pairing the **a**s, so we already know which horizontal moves will be required to get them to their targets.

However, the letter **b** is trickier:

```
012345678
   b b b
 b b b

```

Pairing the **b**s in order would require moving either the **b**s itself or the **a**s between them either up or down, since no **b** can take the place currently occupied by an **a**.

The right choice is to pair the **b** at index 7 of line 1 with the **b** at index **1** of line 2 and not to move the other **b**s at all. We'll refer to the pairings by their initial and final position, which are **\[7 1\]**, **\[3 3\]** and **\[5 5\]** in our example.

But how to find these pairings? In theory, we could just go through all sets of possible pairings for each letter and select the set that requires the least amount of total moves. However, for a letter that occurs **n** times, there are **n!** possible sets of pairings, which is impractical.

In this approach, we determine all possible pairings of two letters that, by themselves, won't increase the number of horizontal moves. To achieve this, we take all possible pairs of letters of lines 1 and 2 and, if the letters are the same, replace both by an underscore and determine to number of moves needed to move nth occurrences to nth occurrences.

For our example, this yields the following:

```
[0 0] [1 7] [2 2] [3 1] [3 3] [4 4] [5 1] [5 3] [5 5] [6 6] [7 1] [7 3] [7 5] [8 8]

```

As we already knew, the letters at indexes 0, 2, 4, 6 and 8 (the **a**s) should not be moved horizontally and the **x** has to move from index 1 to index 7.

For the **b**s, there are several choices to be considered. The **b** at index **3**, for example, can move to index **1** or index **3**.

To minimize the number of vertical moves over all possible sets of pairings, we select as many non-overlapping pairings as possible, since moving the corresponding characters to their destinations will require no vertical moves at all.

Finding these proper pairings is a variant of the longest common subsequence problem. and can be done as follows.

We start by replacing the letters of each line by their indexes:

```
012345678
012345678

```

The first column (**\[0 0\]**) is one of the precomputed pairings, so we select it and remove it from the lines.

We now have

```
12345678
12345678

```

The pairing **\[1 1\]** is invalid (**x** would stay in its position). We now remove the first element of the line 1 and the first element of line 2 (not simultaneously) and apply the process exemplified above to

```
2345678
12345678

```

and

```
12345678
2345678

```

The higher amount of pairings resulting from the two choices will get appended to **\[0 0\]**.

Thanks to memoization, CJam completes this recursive process almost instantly.

For our example, this selects the following pairings:

```
[0 0] [2 2] [3 3] [4 4] [5 5] [6 6] [8 8]

```

This way, all letters except the **x** and the **b** that takes its place won't have to move at all.

### Moving characters

Consider the input

```
0123456789AB
xaxxbycydyye
yyabcydxxxey

```

for which the moves

```
[1 2] [4 3] [6 4] [7 5] [8 6] [10 11]

```

get selected. The corresponding characters won't have to move vertically and we can pair the remaining characters in order.

To implement the pairing, we use the same algorithm we have already used to determine the minimum number of horizontal moves.

We start by replacing characters corresponding to selected pairings with underscores:

```
0123456789AB
x_xx_y___y_e
yy_____xxxe_

```

Now, we enumerate each character's occurrences on both lines:

```
['x 0] ['_ 0] ['x 1] ['x 2] ['_ 1] ['y 0] ['_ 2] ['_ 3] ['_ 4] ['y 1] ['_ 5] ['e 0]
['y 0] ['y 1] ['_ 0] ['_ 1] ['_ 2] ['_ 3] ['_ 4] ['x 0] ['x 1] ['x 2] ['e 0] ['_ 5]

```

Now, we compute the indexes of all pairs in both the second and first line:

```
[0 7] [1 2] [2 8] [3 9] [4 3] [5 0] [6 4] [7 5] [8 6] [9 1] [10 11] [11 10]

```

As before, the pair **\[0 7\]** means that the character at index 0 has to move to index 7.

We eliminate the pairs that had been selected been selected before and examine the remaining pairs:

```
[0 7] [2 8] [3 9] [5 0] [9 1] [11 10]

```

We divide these pairs into two groups, differentiating between characters that move left and those who do not:

```
[0 7] [2 8] [3 9]
[5 0] [9 1] [11 10]

```

Now, we move each character from the second group one unit up and then right until it is below its target. To avoid superpositions, we sort the characters by their final positions (rightmost comes first).

Similarly, we move each character from the first group one unit down and then left until it is below its target. Again, we sort the characters by their final positions (leftmost comes first).

With the vertically moving characters out of the way, we can move the characters of the firstly selected pairs to their destinations.

We already know how many times we have to move each character in which direction; what is left to figure out is the correct order of these moves.

There are several ways of doing this. My implementation simply removes all characters that are already at its destination, moves each character one unit towards its destination if that position is not occupied and repeats the process.

For the pairs

```
[1 2] [4 3] [6 4] [7 5] [8 6] [10 11]

```

this gives the following move order:

```
1:r 4:l 6:l 10:r 6:l 7:l 7:l 8:l 8:l

```

Finally, we move each character that has moved vertically one unit down or up to reach its destination.

### False positives

A cornerstone of this approach is the way it differentiates "good" from "bad" pairings. A good pairing, by itself, won't increase the number of horizontal moves.

However, we select several of these pairings to minimize the number of vertical moves. Certain combinations of good pairings *can* increase the number of horizontal moves, leading to suboptimal results.

The following example illustrates this.

```
01234567
a a a
   a a a

```

For this input, we obtain this list of good moves:

```
[0 3] [0 5] [0 7] [2 3] [2 5] [2 7] [4 5] [4 7]

```

Indeed, neither **\[0 5\]** nor **\[2 7\]** is a bad move by itself.

However, if both moves get selected, we are forced to use the paring **\[4 3\]**, which is a bad move since **a** goes in the wrong direction.

We define a false positive in the selection of pairings as a set of good moves that force us to select a bad one later.

These false positives seem to be rather uncommon. Of all fifteen test cases, there was only one false positive.

In the eleventh test case, the distribution of the letter **h** is the following:

```
 h     h    h        h                                   h  h                                                h                                                    h                    h                  H      H                                      h
                                                            h    h h           h  h   h                                    h                        h                   H            H              h                                              h

```

The uppercase **H**s highlight two good pairings that both get selected and cause the **h**s between them to make a bad pair.

For the general case, we'd either have to avoid these false positives during the selection process or remove the good pairs that caused them afterwards and repeat the selection.

For the test cases, it suffices to proceed as follows:

1. After selecting all pairings, count the number of horizontal moves we have to make.
2. If it is suboptimal, remove each pair of the selection and recount.
3. If the number of horizontal moves is optimal after removing one of the pairs, remove it permanently.
4. If no pair can be removed to achieve the minimum number of horizontal moves, give up and keep all original pairings.

Step 4 is never reached for the test cases.

### Code

```
[l:Al:B]    e# Read two lines from STDIN and store them in A and B.
{           e# Define a function:
  {         e#   Define a function:
    {       e#     For each line:
      :Lee  e#       Save the line in L and enumerate its characters.
      {     e#         For each pair (index, character):
        ~_  e#           Dump the pair and copy the character.
        @L< e#           Cut L off at that index.
        e=  e#           Count the occurrences of the same character to its left.
        a+  e#           Push the pair (character, occurrence).
      }%    e#         This turns "aba" into [['a 0] ['b 0] ['a 1]].
    }/      e#
    f{\a#}  e#     Push the indexes of the pair of line 1 in line 2.
    ee      e#     Enumerate them.
            e#     This turns ["aba" "baa"] into [[0 1] [1 0] [2 2]].
  }:I~      e#   Name the function I and execute it.
  ::-:z     e#   Compute the absolute difference of each pair.
  :+        e#   Add those differences.
}:C~        e# Name the function C and execute it.
            e# C counts the minimum number of horizontal moves to get each
            e# character to its destination.
:O;         e# Save the result for the original input in O.

A,2m*       e# Push an array of all pairs of non-negative integers below len(A).
{           e# Filter those pairs:
  :P[AB].=  e#   Save a pair in P and select the corresponding chars of A and B.
  :=        e#   Check if the characters match.
  {         e#   If they do:
     [      e#
       AP0= e#     Push A and the first index of P.
       '_t  e#     Replace the corresponding char of A with an underscore.
       BP1= e#     Push B and the second index of P.
       '_t  e#     Replace the corresponding char of B with an underscore.
     ]      e#
     C      e#     Execute C on the modified lines.
     O=     e#     Check if the minimum over the modified lines matches O.
  }         e#
  0?        e#   Else, push 0.
},          e# If the result was 1, keep the pair.
:M;         e# Save the result in M and pop it form the stack.
            e# M contains all possible pairings of characters of line 1 and line
            e# 2 that do not increase the minimum number of horizontal moves.

[A,,_]      e# Push the array [[0 ... len(A)-1][0 ... len(A)-1]].
Q{          e# Set up a memoized recursive function j:
  _:e&      e#   Check if if both arrays are non-empty.
  {         e#   If they are:
    _0f=:P  e#     Retrieve the first element of each array and save in P.
    M\e=    e#     Check if P belongs to M.
    {       e#     If it does:
      Pa\   e#       Push [P] and swap it with the arrays.
      1f>j  e#       Remove P from the arrays and execute j.
      +     e#       Concatenate [P] and the result of j.
    }{      e#     Else:
      _2,W% e#       Copy the arrays and push [1 0].
      .>    e#       Vectorized tail. Removes the first element of array 1.
      j     e#       Execute j on the result.
      \2,   e#       Swap with the arrays and push [0 1].
      .>    e#       Vectorized tail. Removes the first element of the array 2.
      j     e#       Execute j on the result.
      _,2$, e#       Push the lengths of both results of j.
      <@@?  e#       Select the longer array.
    }?      e#
  }{        e#   Else:
    ;Q      e#     Remove the arrays and push an empty array.
  }?        e#
}j          e# Execute j on the initial arrays.
            e# This pushes a set of non-overlapping pairings of maximal size.

W\+W+       e# Prepend and append -1 (dummy value) to the pairings.
:G,,        e# Save in G and push [0 ... len(G)-1].
{           e# Find in G:
  G\Wt      e#   Replace the element in G at that index with -1.
  W-:H      e#   Remove all -1's and save the result in H.
  z         e#   Zip the array of parings. This groups the indexes of the first
            e#   line in one array and the indexes of the second line in another.
  [AB]\     e#   Push the array of lines.
  .{        e#   Vectorized foreach:
    {'_t}/  e#     Replace the corresponding characters by underscores.
  }         e#
  :T        e#   Save the result in T.
  CO=       e#   Count the minimum number of horizontal moves and compare with O.
}#          e#   Stop if they match.
;           e#   Discard the index returned by {}#.
            e# This saves G itself in H if the number of horizontal moves was
            e# already optimal and discards at most one element of G to achieve
            e# optimality. T now equals [A B], where characters that will
            e# move only horizontally have been replaced by underscores.

TIH-        e# Execute I on T and remove the elements from H.
            e# This pairs all characters that will have to move vertically.
{           e# Sort by the following key:
  _1=       e#   Retrieve the second element (index of line 2).
  \:>       e#   Push 1 if the index of line 1 is bigger than the one of line 2.
  2*(       e#   1 -> 1 and 0 -> -1
  *         e#   Multiply by the index of line 2.
}$          e# This sorts the pairings by direction, then final position.

{           e# For each pair [X Y]:
  _:>:D;    e#   Set D := 1 if X > Y and D :=0 otherwise.
  ~\:I      e#   Save X in I.
  ":d :u "  e#   Push that string.
  3/        e#   Split it into [":d " ":u "].
  f+        e#   Prepend I to both strings.
  Dm>       e#   Swap the order of the array's elements if D == 1.
  ~o        e#   Dump the array and print its second element.
            e#   The first element will be left on the stack. CJam will print it
            e#   after executing the rest of the program.
  \I-z      e#   Compute abs(Y - I).
  ":r :l "  e#   Push that string.
  3/        e#   Split it into [":r " ":l "].
  D=        e#   Retrieve the string at index D.
  I\ +      e#   Prepend I.
  *o        e#   Repeat the string abs(Y - I) times and print.
}/          e#

H{          e# For each pair in H:
  [         e#
    ~\:I    e#   Save the initial position in I.
    I@I-    e#   Subtract the initial position from the final position (D).
    _ga     e#   Push [sign(D)].
    \z*~    e#   Repeat the array abs(D) times and dump it.
  ]         e#
}%          e# The result contains I twice, followed by abs(D) copies of sign(D).

{           e#
  {2>},     e# Filter out elements with length two.
  _         e# Push a copy.
}{          e# While the copy is non-empty:
  _0f=:P;   e#   Save the positions the elements currently occupy in P.
  {         e#   For each array:
    __,(%   e#     Retrieve the first and last element (position, direction).
    :+:J    e#     Add them and save the result in J.
    P&      e#     Intersect with P.
    {       e#     If J is not in P:
      _1=o  e#       Print the character's identifier.
      ':o   e#       Print a colon
      )0>   e#       Retrieve the direction.
      "lr"= e#       Push 'l' or 'r'.
      S+o   e#       Append a space and print.
      0Jt   e#       Save the new position in the array element.
      PJ+   e#       Append the new position to P.
      :P;   e#       Save in P.
    }|      e#
  }%        e#
}w          e#

```

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


title: place vials in your centrifuge

text:
# Question
Title: place vials in your centrifuge
This question originates in this reddit thread by reddit user taho\_teg but it is expanded to a more general 'puzzle'.

You have a centrifuge with 24 holes for the vials uniformly distributed in a circle around the central axis. If you now have a number of vials and you want to start the centrifuge, you need to make sure that they are placed in a balanced manner. The only numbers of vials you cannot balance are 1 and 23. You can for example balance 4 obviously, but you can also balance 5 by making a 'triangle' with 3 vials and placing the other two on two opposite sites.

# Goal

You have to write a program that accepts the number of holes (that are uniformly distributed in a circle around the rotating axis) of your centrifuge as input, and that outputs a list of numbers of vials that cannot be balanced in the centrifuge.

You have to do the calculation and cannot just hardcode the precomputed solutions.

Input and output have to be implemented in a way so that the program code does not have to be changed for calling the program for different inputs. It is also acceptable to write a function (or a similar construct in your language) that can be called via a console.

Be also aware that if you have 6 holes in your centrifuge, you can centrifuge 2 and 3 vials, but you cannot balance 5 since the 'triangle' and the opposite two will overlap at one point. Another example would be for n=15 you cannot balance 11 vials, you can balance 6 and 5 vials, but the combination of those solutions will overlap (this is of course not yet the criterion that it is impossible to do so).

### Update

It seems some people did not understand the given example, so I made a graphic here. **PLEASE** write a short description of how your algorithm works as well as some example outputs for verification. Please include following examples:

```
n = 1, 6, 10, 24, 63, 100 = 10^2, 163 (prime), 40320 = 8!, 65536=2^2^2^2^2, 105953 (prime)

```

Note that 40320 and 65536 will produce huge lists, it will perhaps be a good idea to only indicate the length of those lists.

If you know some interesting numbers to add to that list please let me know! The algorithm should work at least up to n = 1'000'000.

### Example outputs:

These are some example outputs-but perhaps faulty because I just calculated them manually.

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

```

### Hint

If you have a centrifuge with *n* holes, and you cannot balance e.g. *6* vials, you will also not be able to blance *n-6* vials - it is basically the same task to balance *m* vials on an empty centrifuge or to balance a filled centrifuge by taking away *m* vials. So you if you have the number *m* in your list you will also have to include *n-m*.

# Answer
> 5 votes
# Sage – ~~102~~ 104/115

Why use number theory, when there is brute force?

```
v=lambda n:[j for j in range(n+1)if all(sum(e^(i*2*I*pi/n)for i in c)for c in Combinations(range(n),j))]

```

For a given number of vials, this goes over all ways to position the vials and calculates their center of mass by using complex arithmetics. If the center of mass is zero for none of these ways, the number is returned.

Unfortunately, this does not work in certain cases (10,14), because Sage fails to simplify some expressions to zero (which may be related to this bug). One could regard this as a flaw of the interpreter and not the program and still say that the algorithm and program are fine.

The following 113-character alternative relies on floats instead of symbols and does not suffer from these problems:

```
v=lambda n:[j for j in range(n+1)if all(abs(sum(exp(i*2j*pi/n)for i in c))>1e-9for c in Combinations(range(n),j))]

```

---

Test output of the 113-character version (`for n in range(14): print n,v(n)`):

```
0 []
1 [1]
2 [1]
3 [1, 2]
4 [1, 3]
5 [1, 2, 3, 4]
6 [1, 5]
7 [1, 2, 3, 4, 5, 6]
8 [1, 3, 5, 7]
9 [1, 2, 4, 5, 7, 8]
10 [1, 3, 7, 9]
11 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
12 [1, 11]
13 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
14 [1, 3, 5, 9, 11, 13]

```

I did not want to wait the runtime for higher `n`.

---

This originates from the following Python solution. Exact arithmetics and not having to import some modules is quite something.

# Python – ~~173 154~~ 156

```
from itertools import*
from cmath import*
v=lambda n:[j for j in range(n+1)if all(abs(sum(exp(i*2j*pi/n)for i in c))>1e-9for c in combinations(range(n),j))]

```

Test output of this variant (`for n in range(24): print n,v(n)`):

```
0 []
1 [1]
2 [1]
3 [1, 2]
4 [1, 3]
5 [1, 2, 3, 4]
6 [1, 5]
7 [1, 2, 3, 4, 5, 6]
8 [1, 3, 5, 7]
9 [1, 2, 4, 5, 7, 8]
10 [1, 3, 7, 9]
11 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
12 [1, 11]
13 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
14 [1, 3, 5, 9, 11, 13]
15 [1, 2, 4, 7, 8, 11, 13, 14]
16 [1, 3, 5, 7, 9, 11, 13, 15]
17 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
18 [1, 17]
19 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
20 [1, 3, 17, 19]
21 [1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20]
22 [1, 3, 5, 7, 9, 13, 15, 17, 19, 21]
23 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
24 [1, 23]

```

I did not want to wait the runtime for higher `n`.

# Answer
> 4 votes
# Lua - 197

A non brute force method, it creates a list of factors and rules them out. It also rules out numbers that can be gotten with the addition of those factors as long as the greatest factor used is less than the amount of unfilled holes. One is always printed and isn't used in the algorithm.

```
i=io.read("*n")f={}print(1)for z=2,i do
x=z
if i%x<1 then
table.insert(f,1,x)end
for q=1,#f do
y=f[q]x=x*math.min(1,z%y)while x>=y and x-1~=y and y<=i-z do x=x-y end
end
if x>0 then print(z)end
end

```

Example output: (some put as ranges so I don't exceed the character limit)

```
1: 1

6: 1,5

10:1,3,7,9

24:1,23

63:1,2,4,5,8,11,13,17,20,22,23,25,26,29,32,34,38,41,44,47,50,53,58,59,61,62

100:1,3,13,23,33,43,53,63,73,83,93,97,99

163:1-162

40320:1,11,13,17,19,29,31,37,41,43,61,71,73,97,113,121,127,139,157,169,179,181,191,193,209,211,221,223,241,251,253,263,269,271,277,281,289,299,307,313,331,337,347,349,353,361,373,377,379,397,401,403,409,421,431,433,437,439,449,461,467,473,479,481,491,493,499,517,521,523,529,533,541,547,571,577,587,589,593,601,607,613,617,619,631,641,653,659,671,673,683,689,691,697,701,703,709,713,731,733,737,739,751,757,761,769,781,793,811,817,841,851,853,857,859,869,871,877,881,883,907,913,929,937,953,961,971,977,979,989,991,997,1003,1009,1019,1021,1027,1033,1037,1039,1049,1051,1069,1073,1079,1081,1093,1121,1133,1139,1151,1153,1163,1171,1177,1181,1189,1193,1201,1213,1217,1223,1237,1243,1249,1261,1271,1273,1277,1279,1289,1291,1297,1301,1303,1321,1331,1333,1357,1361,1363,1369,1373,1381,1387,1409,1417,1429,1441,1451,1453,1457,1459,1469,1471,1481,1483,1489,1501,1511,1513,1531,1537,1553,1567,1579,1597,1601,1609,1619,1621,1633,1643,1649,1651,1661,1663,1681,1691,1693,1697,1699,1709,1711,1717,1721,1723,1741,1751,1753,1777,1793,1801,1807,1819,1837,1849,1859,1861,1871,1873,1889,1891,1901,1903,1921,1931,1933,1937,1949,1951,1957,1961,1963,1969,1991,1993,2011,2017,2027,2029,2033,2041,2047,2053,2057,2059,2077,2081,2087,2089,2101,2113,2129,2137,2143,2161,2171,2173,2197,2207,2209,2221,2227,2237,2239,2251,2257,2269,2273,2281,2297,2311,2321,2353,2369,2381,2419,2431,2449,2461,2477,2491,2503,2509,2521,2531,2533,2537,2539,2549,2551,2557,2561,2563,2581,2591,2593,2617,2633,2641,2647,2659,2677,2689,2699,2701,2707,2713,2717,2719,2729,2731,2749,2753,2759,2761,2773,2801,2809,2827,2833,2843,2857,2867,2869,2879,2881,2893,2897,2899,2909,2911,2917,2921,2923,2929,2941,2951,2953,2971,2977,2993,3001,3007,3019,3037,3041,3049,3061,3071,3083,3089,3091,3103,3121,3131,3133,3149,3151,3161,3169,3179,3181,3187,3193,3211,3217,3229,3233,3251,3253,3257,3259,3277,3281,3289,3293,3301,3313,3317,3319,3329,3341,3347,3359,3361,3371,3373,3377,3379,3389,3391,3397,3401,3403,3421,3431,3433,3457,3473,3481,3487,3499,3517,3529,3539,3541,3551,3553,3569,3571,3581,3583,3601,3611,3613,3623,3629,3631,3637,3641,3649,3659,3667,3673,3691,3697,3707,3709,3713,3721,3733,3737,3739,3757,3761,3763,3769,3781,3791,3793,3797,3799,3809,3821,3827,3833,3839,3841,3851,3853,3859,3877,3881,3883,3889,3893,3901,3907,3931,3937,3947,3949,3953,3961,3967,3973,3977,3979,3991,4001,4013,4019,4031,4033,4043,4049,4051,4057,4061,4063,4069,4073,4093,4097,4103,4117,4129,4153,4159,4171,4177,4187,4189,4201,4211,4213,4223,4237,4241,4243,4253,4267,4273,4283,4297,4301,4303,4309,4313,4321,4331,4337,4339,4363,4369,4379,4381,4387,4393,4409,4411,4427,4429,4433,4441,4447,4453,4463,4469,4471,4477,4481,4493,4499,4511,4513,4517,4523,4537,4541,4553,4561,4577,4601,4607,4609,4619,4621,4637,4649,4661,4673,4691,4703,4717,4721,4733,4751,4757,4769,4787,4793,4801,4811,4813,4817,4829,4841,4853,4859,4877,4883,4889,4897,4901,4913,4919,4939,4957,4961,4973,4979,4997,5003,5009,5017,5021,5027,5041,5051,5053,5057,5059,5069,5071,5077,5081,5083,5101,5111,5113,5137,5153,5161,5167,5179,5197,5209,5219,5221,5231,5233,5249,5251,5261,5263,5281,5291,5293,5303,5309,5311,5317,5321,5329,5339,5347,5353,5371,5377,5387,5389,5393,5401,5413,5417,5419,5437,5441,5443,5449,5461,5471,5473,5477,5479,5489,5501,5507,5513,5519,5521,5531,5533,5539,5557,5561,5563,5569,5573,5581,5587,5611,5617,5627,5629,5633,5641,5647,5653,5657,5659,5671,5681,5693,5699,5711,5713,5723,5729,5731,5737,5741,5743,5749,5753,5771,5773,5777,5779,5791,5797,5801,5809,5821,5833,5851,5857,5881,5899,5917,5921,5939,5941,5951,5953,5963,5969,5981,5983,6001,6011,6023,6029,6031,6037,6049,6059,6061,6067,6073,6091,6107,6109,6113,6121,6131,6133,6137,6157,6161,6163,6169,6173,6191,6193,6197,6199,6221,6227,6233,6239,6241,6253,6257,6259,6277,6281,6283,6289,6301,6313,6331,6337,6347,6353,6361,6367,6373,6379,6401,6413,6431,6443,6449,6451,6457,6463,6469,6473,6481,6491,6493,6497,6499,6509,6511,6521,6523,6529,6541,6551,6553,6571,6577,6593,6611,6613,6617,6619,6631,6637,6641,6649,6667,6673,6689,6697,6721,6731,6733,6737,6739,6749,6751,6757,6761,6763,6781,6791,6793,6817,6833,6841,6847,6859,6877,6889,6899,6901,6911,6913,6929,6931,6941,6943,6961,6971,6973,6983,6989,6991,6997,7001,7009,7019,7027,7033,7051,7057,7067,7069,7073,7081,7093,7097,7099,7117,7121,7123,7129,7141,7151,7153,7157,7159,7169,7181,7187,7193,7199,7201,7211,7213,7219,7237,7241,7243,7249,7253,7261,7267,7291,7297,7307,7309,7313,7321,7327,7333,7337,7339,7351,7361,7373,7379,7391,7393,7403,7409,7411,7417,7421,7423,7429,7433,7451,7453,7457,7459,7471,7477,7481,7489,7501,7513,7531,7537,7561,7571,7573,7577,7579,7589,7591,7597,7601,7603,7627,7633,7649,7657,7673,7681,7691,7697,7699,7709,7711,7717,7723,7729,7739,7741,7747,7753,7757,7759,7769,7771,7789,7793,7799,7801,7813,7841,7853,7859,7871,7873,7883,7891,7897,7901,7909,7913,7921,7933,7937,7943,7957,7963,7969,7981,7991,7993,7997,7999,8009,8011,8017,8021,8023,8041,8051,8053,8077,8081,8083,8089,8093,8101,8107,8129,8137,8149,8161,8177,8191,8203,8209,8219,8221,8233,8243,8257,8269,8273,8287,8299,8317,8327,8329,8333,8341,8353,8363,8369,8371,8377,8401,8411,8413,8417,8419,8437,8441,8443,8459,8461,8467,8473,8479,8497,8501,8503,8509,8513,8531,8537,8543,8557,8563,8569,8579,8581,8587,8593,8597,8599,8609,8611,8641,8651,8653,8657,8669,8671,8677,8681,8683,8689,8717,8723,8737,8747,8749,8753,8761,8767,8773,8777,8779,8797,8801,8803,8809,8821,8833,8849,8857,8881,8917,8921,8923,8929,8933,8941,8947,8971,8977,8989,8993,9001,9017,9041,9043,9049,9053,9061,9067,9073,9083,9089,9091,9097,9101,9103,9109,9113,9133,9137,9143,9157,9169,9197,9203,9209,9217,9227,9229,9241,9253,9257,9259,9277,9281,9287,9301,9307,9313,9337,9341,9343,9349,9353,9361,9367,9389,9397,9409,9419,9421,9427,9433,9437,9439,9449,9451,9469,9473,9479,9481,9493,9517,9521,9523,9529,9533,9547,9553,9577,9589,9601,9617,9631,9643,9649,9659,9661,9673,9683,9697,9707,9713,9727,9739,9757,9761,9763,9769,9773,9781,9787,9809,9817,9829,9841,9857,9871,9883,9889,9899,9901,9913,9923,9937,9949,9953,9967,9979,9997,10001,10009,10013,10021,10027,10033,10049,10057,10069,10081,10091,10093,10097,10099,10109,10111,10117,10121,10123,10141,10151,10153,10177,10193,10201,10207,10219,10237,10249,10259,10261,10271,10273,10289,10291,10301,10303,10321,10331,10333,10343,10349,10351,10357,10361,10369,10379,10387,10393,10411,10417,10427,10429,10433,10441,10453,10457,10459,10477,10481,10483,10489,10501,10511,10513,10517,10519,10529,10541,10547,10553,10559,10561,10571,10573,10579,10597,10601,10603,10609,10613,10621,10627,10651,10657,10667,10669,10673,10681,10687,10693,10697,10699,10711,10721,10733,10739,10751,10753,10763,10769,10771,10777,10781,10783,10789,10793,10811,10813,10817,10819,10831,10837,10841,10849,10861,10873,10891,10897,10921,10931,10933,10937,10939,10949,10951,10957,10961,10963,10987,10993,11009,11017,11033,11041,11051,11057,11059,11069,11071,11077,11083,11089,11099,11101,11107,11113,11117,11119,11129,11131,11149,11153,11159,11161,11173,11201,11213,11219,11231,11233,11243,11251,11257,11261,11269,11273,11281,11293,11297,11303,11317,11323,11329,11341,11351,11353,11357,11359,11369,11371,11377,11381,11383,11401,11411,11413,11437,11441,11443,11449,11453,11461,11467,11489,11497,11509,11521,11531,11533,11537,11539,11549,11551,11561,11563,11569,11581,11591,11593,11611,11617,11633,11647,11659,11677,11681,11689,11699,11701,11713,11723,11729,11731,11741,11743,11761,11771,11773,11777,11779,11789,11791,11797,11801,11803,11821,11831,11833,11857,11873,11881,11887,11899,11917,11929,11939,11941,11951,11953,11969,11971,11981,11983,12001,12011,12013,12017,12029,12031,12037,12041,12043,12049,12071,12073,12091,12097,12107,12109,12113,12121,12127,12133,12137,12139,12157,12161,12167,12169,12181,12193,12209,12217,12223,12241,12251,12253,12277,12287,12289,12301,12307,12317,12319,12331,12337,12349,12353,12361,12377,12391,12401,12433,12449,12461,12499,12511,12529,12541,12557,12571,12583,12589,12601,12611,12613,12617,12619,12629,12631,12637,12641,12643,12661,12671,12673,12697,12713,12721,12727,12739,12757,12769,12779,12781,12787,12793,12797,12799,12809,12811,12829,12833,12839,12841,12853,12881,12889,12907,12913,12923,12937,12947,12949,12959,12961,12973,12977,12979,12989,12991,12997,13001,13003,13009,13021,13031,13033,13051,13057,13073,13081,13087,13099,13117,13121,13129,13141,13151,13163,13169,13171,13183,13201,13211,13213,13229,13231,13241,13249,13259,13261,13267,13273,13291,13297,13309,13313,13331,13333,13337,13339,13357,13361,13369,13373,13381,13393,13397,13399,13409,13421,13427,13439,13441,13451,13453,13457,13459,13469,13471,13477,13481,13483,13501,13511,13513,13537,13553,13561,13567,13579,13597,13609,13619,13621,13631,13633,13649,13651,13661,13663,13681,13691,13693,13703,13709,13711,13717,13721,13729,13739,13747,13753,13771,13777,13787,13789,13793,13801,13813,13817,13819,13837,13841,13843,13849,13861,13871,13873,13877,13879,13889,13901,13907,13913,13919,13921,13931,13933,13939,13957,13961,13963,13969,13973,13981,13987,14011,14017,14027,14029,14033,14041,14047,14053,14057,14059,14071,14081,14093,14099,14111,14113,14123,14129,14131,14137,14141,14143,14149,14153,14171,14173,14177,14179,14191,14197,14201,14209,14221,14233,14251,14257,14281,14291,14293,14297,14299,14309,14311,14317,14321,14323,14347,14353,14369,14377,14393,14401,14411,14417,14419,14429,14431,14437,14443,14449,14459,14461,14467,14473,14477,14479,14489,14491,14509,14513,14519,14521,14533,14561,14573,14579,14591,14593,14603,14611,14617,14621,14629,14633,14641,14653,14657,14663,14677,14683,14689,14701,14711,14713,14717,14719,14729,14731,14737,14741,14743,14761,14771,14773,14797,14801,14803,14809,14813,14821,14827,14849,14857,14869,14881,14891,14893,14897,14899,14909,14911,14921,14923,14929,14941,14951,14953,14971,14977,14993,15007,15019,15037,15041,15049,15059,15061,15073,15083,15089,15091,15101,15103,15121,15131,15133,15137,15139,15149,15151,15157,15161,15163,15181,15191,15193,15217,15233,15241,15247,15259,15277,15289,15299,15301,15311,15313,15329,15331,15341,15343,15361,15371,15373,15377,15389,15391,15397,15401,15403,15409,15431,15433,15451,15457,15467,15469,15473,15481,15487,15493,15497,15499,15517,15521,15527,15529,15541,15553,15569,15577,15583,15601,15611,15613,15637,15647,15649,15661,15667,15677,15679,15691,15697,15709,15713,15721,15737,15751,15761,15793,15809,15821,15859,15871,15889,15901,15917,15931,15943,15949,15961,15971,15973,15977,15979,15989,15991,15997,16001,16003,16021,16031,16033,16057,16073,16081,16087,16099,16117,16129,16139,16141,16147,16153,16157,16159,16169,16171,16189,16193,16199,16201,16213,16241,16249,16267,16273,16283,16297,16307,16309,16319,16321,16333,16337,16339,16349,16351,16357,16361,16363,16369,16381,16391,16393,16411,16417,16433,16441,16447,16459,16477,16481,16489,16501,16511,16523,16529,16531,16543,16561,16571,16573,16589,16591,16601,16609,16619,16621,16627,16633,16651,16657,16669,16673,16691,16693,16697,16699,16717,16721,16729,16733,16741,16753,16757,16759,16769,16781,16787,16799,16801,16811,16813,16817,16819,16829,16831,16837,16841,16843,16861,16871,16873,16897,16913,16921,16927,16939,16957,16969,16979,16981,16991,16993,17009,17011,17021,17023,17041,17051,17053,17063,17069,17071,17077,17081,17089,17099,17107,17113,17131,17137,17147,17149,17153,17161,17173,17177,17179,17197,17201,17203,17209,17221,17231,17233,17237,17239,17249,17261,17267,17273,17279,17281,17291,17293,17299,17317,17321,17323,17329,17333,17341,17347,17371,17377,17387,17389,17393,17401,17407,17413,17417,17419,17431,17441,17453,17459,17471,17473,17483,17489,17491,17497,17501,17503,17509,17513,17533,17537,17543,17557,17569,17593,17599,17611,17617,17627,17629,17641,17651,17653,17663,17677,17681,17683,17693,17707,17713,17723,17737,17741,17743,17749,17753,17761,17771,17777,17779,17803,17809,17819,17821,17827,17833,17849,17851,17867,17869,17873,17881,17887,17893,17903,17909,17911,17917,17921,17933,17939,17951,17953,17957,17963,17977,17981,17993,18001,18017,18041,18047,18049,18059,18061,18077,18089,18101,18113,18131,18143,18157,18161,18173,18191,18197,18209,18227,18233,18241,18251,18253,18257,18269,18281,18293,18299,18317,18323,18329,18337,18341,18353,18359,18379,18397,18401,18413,18419,18437,18443,18449,18457,18461,18467,18481,18491,18493,18497,18499,18509,18511,18517,18521,18523,18541,18551,18553,18577,18593,18601,18607,18619,18637,18649,18659,18661,18671,18673,18689,18691,18701,18703,18721,18731,18733,18743,18749,18751,18757,18761,18769,18779,18787,18793,18811,18817,18827,18829,18833,18841,18853,18857,18859,18877,18881,18883,18889,18901,18911,18913,18917,18919,18929,18941,18947,18953,18959,18961,18971,18973,18979,18997,19001,19003,19009,19013,19021,19027,19051,19057,19067,19069,19073,19081,19087,19093,19097,19099,19111,19121,19133,19139,19151,19153,19163,19169,19171,19177,19181,19183,19189,19193,19211,19213,19217,19219,19231,19237,19241,19249,19261,19273,19291,19297,19321,19339,19357,19361,19379,19381,19391,19393,19403,19409,19421,19423,19441,19451,19463,19469,19471,19477,19489,19499,19501,19507,19513,19531,19547,19549,19553,19561,19571,19573,19577,19597,19601,19603,19609,19613,19631,19633,19637,19639,19661,19667,19673,19679,19681,19693,19697,19699,19717,19721,19723,19729,19741,19753,19771,19777,19787,19793,19801,19807,19813,19819,19841,19853,19871,19883,19889,19891,19897,19903,19909,19913,19921,19931,19933,19937,19939,19949,19951,19961,19963,19969,19981,19991,19993,20011,20017,20033,20051,20053,20057,20059,20071,20077,20081,20089,20107,20113,20129,20137,20161,20171,20173,20177,20179,20189,20191,20197,20201,20203,20221,20231,20233,20257,20273,20281,20287,20299,20317,20329,20339,20341,20351,20353,20369,20371,20381,20383,20401,20411,20413,20423,20429,20431,20437,20441,20449,20459,20467,20473,20491,20497,20507,20509,20513,20521,20533,20537,20539,20557,20561,20563,20569,20581,20591,20593,20597,20599,20609,20621,20627,20633,20639,20641,20651,20653,20659,20677,20681,20683,20689,20693,20701,20707,20731,20737,20747,20749,20753,20761,20767,20773,20777,20779,20791,20801,20813,20819,20831,20833,20843,20849,20851,20857,20861,20863,20869,20873,20891,20893,20897,20899,20911,20917,20921,20929,20941,20953,20971,20977,21001,21011,21013,21017,21019,21029,21031,21037,21041,21043,21067,21073,21089,21097,21113,21121,21131,21137,21139,21149,21151,21157,21163,21169,21179,21181,21187,21193,21197,21199,21209,21211,21229,21233,21239,21241,21253,21281,21293,21299,21311,21313,21323,21331,21337,21341,21349,21353,21361,21373,21377,21383,21397,21403,21409,21421,21431,21433,21437,21439,21449,21451,21457,21461,21463,21481,21491,21493,21517,21521,21523,21529,21533,21541,21547,21569,21577,21589,21601,21617,21631,21643,21649,21659,21661,21673,21683,21697,21709,21713,21727,21739,21757,21767,21769,21773,21781,21793,21803,21809,21811,21817,21841,21851,21853,21857,21859,21877,21881,21883,21899,21901,21907,21913,21919,21937,21941,21943,21949,21953,21971,21977,21983,21997,22003,22009,22019,22021,22027,22033,22037,22039,22049,22051,22081,22091,22093,22097,22109,22111,22117,22121,22123,22129,22157,22163,22177,22187,22189,22193,22201,22207,22213,22217,22219,22237,22241,22243,22249,22261,22273,22289,22297,22321,22357,22361,22363,22369,22373,22381,22387,22411,22417,22429,22433,22441,22457,22481,22483,22489,22493,22501,22507,22513,22523,22529,22531,22537,22541,22543,22549,22553,22573,22577,22583,22597,22609,22637,22643,22649,22657,22667,22669,22681,22693,22697,22699,22717,22721,22727,22741,22747,22753,22777,22781,22783,22789,22793,22801,22807,22829,22837,22849,22859,22861,22867,22873,22877,22879,22889,22891,22909,22913,22919,22921,22933,22957,22961,22963,22969,22973,22987,22993,23017,23029,23041,23057,23071,23083,23089,23099,23101,23113,23123,23137,23147,23153,23167,23179,23197,23201,23203,23209,23213,23221,23227,23249,23257,23269,23281,23297,23311,23323,23329,23339,23341,23353,23363,23377,23389,23393,23407,23419,23437,23441,23449,23453,23461,23467,23473,23489,23497,23509,23521,23531,23533,23537,23539,23549,23551,23557,23561,23563,23581,23591,23593,23617,23633,23641,23647,23659,23677,23689,23699,23701,23711,23713,23729,23731,23741,23743,23761,23771,23773,23783,23789,23791,23797,23801,23809,23819,23827,23833,23851,23857,23867,23869,23873,23881,23893,23897,23899,23917,23921,23923,23929,23941,23951,23953,23957,23959,23969,23981,23987,23993,23999,24001,24011,24013,24019,24037,24041,24043,24049,24053,24061,24067,24091,24097,24107,24109,24113,24121,24127,24133,24137,24139,24151,24161,24173,24179,24191,24193,24203,24209,24211,24217,24221,24223,24229,24233,24251,24253,24257,24259,24271,24277,24281,24289,24301,24313,24331,24337,24361,24371,24373,24377,24379,24389,24391,24397,24401,24403,24427,24433,24449,24457,24473,24481,24491,24497,24499,24509,24511,24517,24523,24529,24539,24541,24547,24553,24557,24559,24569,24571,24589,24593,24599,24601,24613,24641,24653,24659,24671,24673,24683,24691,24697,24701,24709,24713,24721,24733,24737,24743,24757,24763,24769,24781,24791,24793,24797,24799,24809,24811,24817,24821,24823,24841,24851,24853,24877,24881,24883,24889,24893,24901,24907,24929,24937,24949,24961,24971,24973,24977,24979,24989,24991,25001,25003,25009,25021,25031,25033,25051,25057,25073,25087,25099,25117,25121,25129,25139,25141,25153,25163,25169,25171,25181,25183,25201,25211,25213,25217,25219,25229,25231,25237,25241,25243,25261,25271,25273,25297,25313,25321,25327,25339,25357,25369,25379,25381,25391,25393,25409,25411,25421,25423,25441,25451,25453,25457,25469,25471,25477,25481,25483,25489,25511,25513,25531,25537,25547,25549,25553,25561,25567,25573,25577,25579,25597,25601,25607,25609,25621,25633,25649,25657,25663,25681,25691,25693,25717,25727,25729,25741,25747,25757,25759,25771,25777,25789,25793,25801,25817,25831,25841,25873,25889,25901,25939,25951,25969,25981,25997,26011,26023,26029,26041,26051,26053,26057,26059,26069,26071,26077,26081,26083,26101,26111,26113,26137,26153,26161,26167,26179,26197,26209,26219,26221,26227,26233,26237,26239,26249,26251,26269,26273,26279,26281,26293,26321,26329,26347,26353,26363,26377,26387,26389,26399,26401,26413,26417,26419,26429,26431,26437,26441,26443,26449,26461,26471,26473,26491,26497,26513,26521,26527,26539,26557,26561,26569,26581,26591,26603,26609,26611,26623,26641,26651,26653,26669,26671,26681,26689,26699,26701,26707,26713,26731,26737,26749,26753,26771,26773,26777,26779,26797,26801,26809,26813,26821,26833,26837,26839,26849,26861,26867,26879,26881,26891,26893,26897,26899,26909,26911,26917,26921,26923,26941,26951,26953,26977,26993,27001,27007,27019,27037,27049,27059,27061,27071,27073,27089,27091,27101,27103,27121,27131,27133,27143,27149,27151,27157,27161,27169,27179,27187,27193,27211,27217,27227,27229,27233,27241,27253,27257,27259,27277,27281,27283,27289,27301,27311,27313,27317,27319,27329,27341,27347,27353,27359,27361,27371,27373,27379,27397,27401,27403,27409,27413,27421,27427,27451,27457,27467,27469,27473,27481,27487,27493,27497,27499,27511,27521,27533,27539,27551,27553,27563,27569,27571,27577,27581,27583,27589,27593,27611,27613,27617,27619,27631,27637,27641,27649,27661,27673,27691,27697,27721,27731,27733,27737,27739,27749,27751,27757,27761,27763,27787,27793,27809,27817,27833,27841,27851,27857,27859,27869,27871,27877,27883,27889,27899,27901,27907,27913,27917,27919,27929,27931,27949,27953,27959,27961,27973,28001,28013,28019,28031,28033,28043,28051,28057,28061,28069,28073,28081,28093,28097,28103,28117,28123,28129,28141,28151,28153,28157,28159,28169,28171,28177,28181,28183,28201,28211,28213,28237,28241,28243,28249,28253,28261,28267,28289,28297,28309,28321,28337,28351,28363,28369,28379,28381,28393,28403,28417,28429,28433,28447,28459,28477,28487,28489,28493,28501,28513,28523,28529,28531,28537,28561,28571,28573,28577,28579,28597,28601,28603,28619,28621,28627,28633,28639,28657,28661,28663,28669,28673,28691,28697,28703,28717,28723,28729,28739,28741,28747,28753,28757,28759,28769,28771,28801,28811,28813,28817,28829,28831,28837,28841,28843,28849,28877,28883,28897,28907,28909,28913,28921,28927,28933,28937,28939,28957,28961,28963,28969,28981,28993,29009,29017,29041,29077,29081,29083,29089,29093,29101,29107,29131,29137,29149,29153,29161,29177,29201,29203,29209,29213,29221,29227,29233,29243,29249,29251,29257,29261,29263,29269,29273,29293,29297,29303,29317,29329,29357,29363,29369,29377,29387,29389,29401,29413,29417,29419,29437,29441,29447,29461,29467,29473,29497,29501,29503,29509,29513,29521,29527,29549,29557,29569,29579,29581,29587,29593,29597,29599,29609,29611,29629,29633,29639,29641,29653,29677,29681,29683,29689,29693,29707,29713,29737,29749,29761,29777,29791,29803,29809,29819,29821,29833,29843,29857,29867,29873,29887,29899,29917,29921,29923,29929,29933,29941,29947,29969,29977,29989,30001,30017,30031,30043,30049,30059,30061,30073,30083,30097,30109,30113,30127,30139,30157,30161,30169,30173,30181,30187,30193,30209,30217,30229,30241,30251,30253,30257,30259,30283,30299,30301,30307,30313,30323,30329,30337,30347,30349,30353,30361,30367,30383,30389,30391,30397,30413,30419,30431,30433,30449,30451,30467,30469,30473,30481,30487,30493,30497,30523,30529,30539,30547,30553,30557,30559,30571,30577,30593,30617,30623,30637,30641,30643,30649,30661,30673,30683,30689,30691,30697,30701,30703,30713,30721,30733,30743,30757,30763,30769,30803,30809,30811,30817,30823,30829,30833,30841,30859,30881,30889,30913,30923,30929,30931,30937,30941,30943,30949,30953,30973,30977,30983,30997,31009,31033,31039,31051,31057,31067,31069,31081,31091,31093,31103,31117,31121,31123,31133,31147,31153,31163,31177,31181,31183,31189,31193,31201,31211,31217,31219,31243,31249,31259,31261,31267,31273,31289,31291,31307,31309,31313,31321,31327,31333,31343,31349,31351,31357,31361,31373,31379,31391,31393,31403,31411,31417,31427,31429,31433,31441,31447,31453,31457,31459,31483,31489,31499,31501,31513,31517,31519,31529,31531,31537,31543,31553,31571,31583,31597,31601,31603,31609,31613,31621,31627,31643,31649,31651,31657,31663,31669,31673,31681,31693,31697,31723,31729,31753,31763,31769,31771,31777,31781,31783,31789,31793,31819,31837,31841,31849,31873,31883,31889,31891,31897,31901,31903,31909,31921,31931,31933,31937,31939,31949,31951,31957,31961,31963,31981,31991,31993,32017,32033,32051,32057,32063,32077,32083,32089,32093,32101,32107,32113,32129,32149,32161,32173,32183,32189,32191,32197,32201,32203,32209,32213,32233,32237,32243,32257,32267,32269,32273,32281,32293,32297,32299,32317,32321,32323,32329,32341,32351,32353,32357,32359,32369,32381,32387,32393,32399,32401,32411,32413,32419,32437,32441,32443,32449,32453,32461,32467,32491,32497,32507,32509,32513,32521,32527,32533,32537,32539,32551,32561,32573,32579,32591,32593,32603,32609,32611,32617,32621,32623,32629,32633,32651,32653,32657,32659,32671,32677,32681,32689,32701,32713,32731,32737,32761,32779,32797,32801,32819,32821,32831,32833,32843,32849,32861,32863,32881,32891,32903,32909,32911,32917,32929,32939,32941,32947,32953,32971,32987,32989,32993,33001,33011,33013,33017,33037,33041,33043,33049,33053,33071,33073,33077,33079,33101,33107,33113,33119,33121,33133,33137,33139,33157,33161,33163,33169,33181,33193,33211,33217,33227,33233,33241,33247,33253,33259,33281,33293,33311,33323,33329,33331,33337,33343,33349,33353,33361,33371,33373,33377,33379,33389,33391,33401,33403,33409,33421,33431,33433,33451,33457,33473,33491,33493,33497,33499,33511,33517,33521,33529,33547,33553,33569,33577,33601,33611,33613,33617,33629,33641,33653,33659,33683,33689,33697,33701,33713,33739,33757,33773,33779,33797,33809,33821,33827,33833,33841,33851,33853,33857,33869,33871,33877,33881,33883,33889,33911,33913,33931,33937,33953,33961,33967,33979,33997,34001,34009,34019,34021,34031,34033,34043,34049,34051,34061,34063,34081,34091,34093,34103,34109,34117,34121,34129,34141,34147,34171,34177,34187,34189,34193,34201,34211,34213,34217,34219,34241,34243,34249,34253,34261,34271,34273,34277,34289,34301,34313,34319,34331,34333,34337,34339,34357,34361,34369,34373,34381,34387,34393,34411,34417,34427,34429,34441,34453,34457,34459,34471,34481,34493,34499,34511,34513,34523,34529,34537,34541,34543,34549,34553,34561,34571,34577,34579,34603,34609,34619,34621,34627,34633,34649,34651,34667,34669,34673,34681,34687,34693,34703,34709,34711,34717,34721,34733,34739,34751,34753,34757,34763,34777,34781,34793,34801,34817,34841,34847,34849,34859,34861,34877,34889,34901,34913,34931,34943,34957,34961,34973,34991,34997,35009,35027,35033,35041,35051,35053,35057,35069,35081,35093,35099,35117,35123,35129,35137,35141,35153,35159,35179,35197,35201,35213,35219,35237,35243,35249,35257,35261,35267,35281,35291,35293,35297,35309,35321,35327,35333,35339,35351,35377,35389,35393,35411,35417,35423,35429,35449,35453,35473,35477,35489,35513,35519,35521,35531,35533,35537,35549,35561,35573,35597,35603,35617,35627,35629,35633,35657,35663,35669,35681,35699,35713,35723,35729,35741,35747,35753,35771,35789,35801,35807,35809,35813,35831,35837,35851,35857,35867,35869,35879,35881,35887,35893,35897,35921,35923,35929,35947,35953,35963,35969,35971,35977,35989,35993,36011,36013,36017,36019,36031,36037,36047,36049,36053,36061,36077,36083,36089,36097,36107,36109,36121,36131,36133,36137,36139,36149,36151,36157,36161,36163,36187,36193,36203,36209,36217,36221,36223,36229,36233,36241,36247,36257,36269,36287,36289,36299,36301,36307,36313,36317,36319,36329,36331,36349,36353,36359,36361,36373,36401,36409,36427,36433,36443,36457,36467,36469,36479,36481,36493,36497,36499,36509,36511,36517,36521,36523,36529,36541,36551,36553,36571,36577,36593,36601,36607,36619,36637,36641,36649,36661,36671,36683,36689,36691,36703,36721,36731,36733,36749,36751,36761,36769,36779,36781,36787,36793,36811,36817,36829,36833,36851,36853,36857,36859,36877,36881,36889,36893,36901,36913,36917,36919,36929,36941,36947,36959,36961,36979,36991,37003,37021,37063,37069,37081,37091,37097,37099,37109,37111,37117,37123,37129,37141,37151,37153,37171,37193,37201,37207,37237,37241,37249,37259,37267,37273,37277,37279,37291,37297,37309,37313,37319,37321,37333,37339,37361,37369,37393,37403,37409,37417,37427,37439,37447,37453,37477,37481,37483,37489,37493,37501,37507,37529,37537,37549,37561,37577,37591,37603,37609,37619,37621,37633,37649,37661,37699,37711,37729,37741,37757,37771,37783,37789,37801,37817,37831,37841,37867,37873,37889,37897,37913,37921,37927,37937,37969,37997,38011,38047,38077,38081,38089,38107,38113,38123,38137,38147,38149,38159,38161,38173,38177,38179,38189,38191,38203,38209,38219,38221,38233,38237,38239,38249,38251,38257,38273,38279,38281,38293,38299,38317,38321,38329,38341,38351,38363,38369,38371,38383,38401,38411,38413,38417,38419,38429,38431,38441,38443,38449,38461,38471,38473,38491,38497,38513,38527,38539,38557,38561,38569,38579,38581,38593,38603,38609,38611,38621,38623,38641,38653,38657,38663,38677,38683,38701,38711,38713,38719,38729,38737,38741,38743,38749,38761,38771,38797,38803,38809,38813,38821,38827,38833,38849,38869,38881,38893,38903,38909,38911,38917,38921,38923,38929,38933,38953,38957,38963,38977,38981,38989,38993,39001,39013,39017,39023,39037,39043,39049,39061,39073,39089,39097,39121,39149,39161,39167,39169,39173,39211,39217,39229,39233,39241,39257,39281,39283,39289,39293,39301,39307,39313,39329,39337,39353,39379,39397,39401,39409,39433,39451,39457,39481,39493,39497,39499,39511,39521,39533,39539,39551,39553,39563,39569,39577,39581,39583,39589,39593,39601,39607,39617,39629,39647,39649,39653,39659,39671,39691,39701,39703,39709,39713,39721,39761,39773,39779,39791,39793,39803,39811,39821,39827,39833,39839,39841,39857,39863,39869,39877,39881,39883,39889,39901,39913,39923,39929,39931,39937,39947,39953,39961,39979,40003,40007,40009,40013,40021,40037,40051,40057,40067,40081,40093,40109,40127,40129,40139,40141,40157,40171,40219,40241,40247,40253,40267,40273,40277,40289,40297,40301,40307,40319

65536: This makes my answer go over the character limit (32768 numbers)

105953: 1-105952

```

# Answer
> 0 votes
# Pyth - 39 37 bytes

A direct translation of @Wrzlprmft's python answer.

```
f.Am>.asm^.n1c*.jZyk.nZQd^10_9.cUQTSQ

```

Explanation and probably further golfing coming soon.

Try it online here.

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