Python - Star Transform Turned Huffman [ratio=55% (decimal), and 45.4% (base36)]

This started out as a star transformation algorithm, but morphed into a Huffman-style frequency based encoding.

I generated a frequency dictionary of lorem ipsum words (using the NLTK) from the samples, and then assigned them decimal values. Words are then substituted for their decimal values. There are some special cases for new lines and capital letters.

There are 3 different compression options: normal, strict, and stricter. Normal uses decimal encoding, strict uses hex encoding, and stricter uses base 36 encoding. Both strict and stricter will have problems if there are new words.

compress.py

#!/usr/bin/env python
import sys,re,lorem

strict = len(sys.argv) == 2 and sys.argv[1] == '-s'
stricter = len(sys.argv) == 2 and sys.argv[1] == '-ss'

text = sys.stdin.read()
dict = lorem.dictionary

splitter = re.compile(r'([a-zA-Z]+|\s+|[,\.]*)')
words = splitter.findall(text)
for w in words:
    if w.lower() in dict:
        code = int(dict[w.lower()])
        if strict:
            code = lorem.strict_code(code)
        elif stricter:
            code = lorem.base36encode(code)
        if w.istitle():
                code = '^%s' %(code)
        sys.stdout.write(str(code))
    elif w == '\n\n ':
        sys.stdout.write('~')
    else:
        sys.stdout.write(w)

decompress.py

#!/usr/bin/env python
import sys,re,lorem

strict = len(sys.argv) == 2 and sys.argv[1] == '-s'
stricter = len(sys.argv) == 2 and sys.argv[1] == '-ss'

text = sys.stdin.read()

# create the inverse of the dictionary
dict = dict((v,k) for k, v in lorem.dictionary.iteritems())

splitter = re.compile(r'(\s+|\^?[0-9a-zA-Z]+|[a-zA-Z]+|\^?\d+|[,\.~]?)')
words = splitter.findall(text)
for w in words:
    code = w
    upper = False
    if len(code) > 1 and code[0] == '^':
        code = code[1:]
        upper = True
    if strict:
        #print code, lorem.strict_str(code)
        code = lorem.strict_str(code)
    elif stricter:
        try:
            #print "\n'"+code+"'", lorem.base36decode(code)
            code = str(lorem.base36decode(code))
        except ValueError:
            pass
    if code in dict:
        sys.stdout.write(dict[code].title() if upper else dict[code])
    elif w == '~':
        sys.stdout.write('\n\n ')
    else:
        sys.stdout.write(w)

lorem.py - library file

dictionary ={'consul': '64', 'discere': '378', 'virtute': '78', 'salutatus': '430', 'appareat': '362', 'doctus': '452', 'definiebas': '285', 'labitur': '399', 'vel': '34', 'te': '7', 'audire': '447', 'libris': '232', 'delicatissimi': '290', 'consequat': '194', 'veri': '351', 'fierent': '307', 'solet': '166', 'aliquip': '359', 'vero': '173', 'torquatos': '346', 'urbanitas': '483', 'habeo': '309', 'clita': '369', 'ferri': '390', 'integre': '313', 'nemore': '46', 'aeterno': '183', 'partem': '103', 'nusquam': '467', 'cetero': '191', 'natum': '465', 'fabulas': '215', 'eleifend': '454', 'voluptatibus': '79', 'apeirian': '187', 'diam': '291', 'interpretaris': '314', 'essent': '304', 'nec': '35', 'mollis': '319', 'erroribus': '52', 'mea': '30', 'ludus': '235', 'mel': '31', 'sint': '112', 'error': '51', 'mei': '39', 'decore': '126', 'repudiandae': '161', 'imperdiet': '393', 'soluta': '113', 'saperet': '337', 'aliquam': '184', 'invidunt': '460', 'dicta': '85', 'viderer': '441', 'nulla': '99', 'takimata': '263', 'insolens': '312', 'dicunt': '294', 'tractatos': '266', 'vim': '36', 'vis': '18', 'causae': '368', 'modus': '408', 'iusto': '143', 'vix': '16', 'oporteat': '74', 'zzril': '80', 'assentior': '189', 'meliore': '241', 'liber': '402', 'molestiae': '318', 'efficiendi': '87', 'usu': '29', 'lucilius': '403', 'ocurreret': '100', 'indoctum': '396', 'solum': '478', 'luptatum': '236', 'legendos': '230', 'voluptatum': '271', 'democritum': '128', 'detracto': '376', 'officiis': '153', 'sententiae': '477', 'salutandi': '429', 'prompta': '332', 'dictas': '202', 'accusamus': '355', 'alia': '81', 'conclusionemque': '449', 'phaedrum': '328', 'reque': '60', 'exerci': '305', 'minimum': '463', 'antiopam': '186', 'nullam': '246', 'similique': '261', 'regione': '258', 'quot': '335', 'mnesarchum': '147', 'inimicus': '92', 'aeque': '274', 'animal': '121', 'quod': '424', 'vitae': '43', 'dissentias': '296', 'affert': '119', 'numquam': '414', 'abhorreant': '273', 'gloriatur': '308', 'mutat': '410', 'disputando': '379', 'conceptam': '193', 'sit': '40', 'honestatis': '311', 'iracundia': '461', 'maluisset': '240', 'dicant': '377', 'electram': '134', 'petentium': '156', 'propriae': '333', 'recusabo': '336', 'adversarium': '118', 'oblique': '72', 'possim': '254', 'elit': '209', 'euripidis': '385', 'nonumy': '151', 'possit': '472', 'iudico': '462', 'omnes': '249', 'ius': '28', 'nostro': '152', 'eum': '25', 'repudiare': '427', 'etiam': '384', 'omittam': '247', 'ornatus': '154', 'suavitate': '262', 'civibus': '192', 'comprehensam': '84', 'dicit': '50', 'nibh': '321', 'facilis': '306', 'patrioque': '155', 'laboramus': '316', 'nihil': '243', 'odio': '468', 'ipsum': '315', 'tollit': '61', 'scribentur': '432', 'docendi': '204', 'quaerendum': '106', 'diceret': '200', 'fastidii': '136', 'liberavisse': '317', 'ei': '11', 'ea': '3', 'recteque': '425', 'ex': '4', 'eu': '10', 'et': '8', 'molestie': '98', 'aliquid': '446', 'aliquyam': '276', 'mediocritatem': '405', 'efficiantur': '133', 'menandri': '406', 'dissentiet': '67', 'pericula': '251', 'tamquam': '481', 'hendrerit': '310', 'tritani': '436', 'cibo': '83', 'scriptorem': '260', 'disputationi': '295', 'euismod': '455', 'qui': '17', 'equidem': '135', 'quo': '15', 'saepe': '163', 'accusata': '180', 'tibique': '265', 'homero': '140', 'referrentur': '257', 'neglegentur': '148', 'bonorum': '448', 'principes': '158', 'enim': '211', 'appellantur': '122', 'volumus': '443', 'graeco': '90', 'graeci': '138', 'persecuti': '56', 'posidonium': '253', 'percipitur': '470', 'dolorum': '297', 'option': '250', 'quando': '256', 'veritus': '172', 'quas': '421', 'epicuri': '300', 'gubergren': '139', 'accumsan': '354', 'graece': '457', 'nominati': '150', 'splendide': '343', 'ponderum': '75', 'sonet': '77', 'instructior': '141', 'omnis': '415', 'intellegam': '93', 'habemus': '392', 'verear': '439', 'corrumpit': '284', 'pri': '14', 'vocent': '484', 'expetendis': '387', 'duis': '132', 'soleat': '342', 'ridens': '162', 'tale': '480', 'latine': '228', 'aperiam': '277', 'mazim': '69', 'ignota': '222', 'elitr': '210', 'scripta': '259', 'argumentum': '188', 'veniam': '350', 'perpetua': '104', 'expetenda': '386', 'esse': '213', 'erant': '383', 'philosophia': '416', 'constituam': '282', 'ceteros': '124', 'sale': '428', 'inani': '394', 'oratio': '47', 'adipiscing': '116', 'alienum': '445', 'errem': '68', 'dolor': '205', 'probo': '418', 'elaboraret': '208', 'laoreet': '401', 'blandit': '123', 'quaestio': '476', 'delenit': '287', 'nobis': '244', 'sadipscing': '110', 'platonem': '329', 'contentiones': '374', 'quem': '422', 'dico': '201', 'oportere': '102', 'dolore': '453', 'laudem': '229', 'reprehendunt': '426', 'invenire': '95', 'consequuntur': '450', 'vocibus': '177', 'his': '38', 'signiferumque': '111', 'utroque': '348', 'congue': '372', 'intellegat': '142', 'qualisque': '58', 'complectitur': '371', 'meis': '70', 'unum': '438', 'prima': '474', 'nisl': '149', 'accommodare': '178', 'tation': '435', 'ancillae': '185', 'suscipit': '345', 'sed': '33', 'sea': '32', 'incorrupte': '395', 'labore': '400', 'postulant': '473', 'temporibus': '482', 'nostrum': '245', 'nostrud': '413', 'posse': '471', 'partiendo': '469', 'debitis': '197', 'aliquando': '358', 'eirmod': '207', 'detraxit': '130', 'malorum': '96', 'verterem': '267', 'melius': '54', 'viris': '442', 'altera': '120', 'mandamus': '145', 'magna': '237', 'amet': '361', 'omnium': '101', 'summo': '167', 'tempor': '169', 'facer': '216', 'facilisis': '217', 'placerat': '57', 'maiestatis': '404', 'doming': '206', 'evertitur': '456', 'quodsi': '76', 'assum': '278', 'cu': '13', 'mentitum': '71', 'quis': '59', 'duo': '23', 'eros': '302', 'puto': '475', 'feugiat': '137', 'pro': '21', 'inciderint': '45', 'lobortis': '233', 'dolores': '86', 'consulatu': '283', 'vituperatoribus': '269', 'senserit': '433', 'atqui': '190', 'suas': '479', 'pertinax': '327', 'eligendi': '381', 'impedit': '224', 'corpora': '196', 'agam': '275', 'vulputate': '115', 'fuisset': '220', 'volutpat': '272', 'noster': '322', 'rationibus': '160', 'offendit': '323', 'semper': '340', 'erat': '212', 'prodesset': '419', 'accusam': '179', 'in': '0', 'debet': '375', 'id': '20', 'cotidieque': '65', 'minim': '55', 'movet': '464', 'sensibus': '341', 'paulo': '324', 'omittantur': '248', 'audiam': '365', 'commune': '370', 'vivendo': '270', 'commodo': '280', 'fabellas': '88', 'brute': '367', 'persius': '252', 'delicata': '289', 'iuvaret': '144', 'graecis': '391', 'appetere': '363', 'deleniti': '288', 'legere': '231', 'aperiri': '82', 'choro': '63', 'deseruisse': '129', 'utamur': '347', 'iisque': '53', 'inermis': '91', 'concludaturque': '281', 'scripserit': '339', 'theophrastus': '264', 'eruditi': '303', 'noluisse': '412', 'impetus': '459', 'vide': '440', 'hinc': '221', 'dissentiunt': '131', 'cum': '37', 'has': '19', 'percipit': '325', 'tantas': '168', 'eripuit': '301', 'sumo': '434', 'perfecto': '42', 'interesset': '397', 'primis': '255', 'copiosae': '451', 'kasd': '227', 'munere': '409', 'facilisi': '44', 'scaevola': '431', 'explicari': '214', 'omnesque': '73', 'vidisse': '174', 'velit': '349', 'facete': '388', 'iudicabit': '225', 'timeam': '170', 'augue': '279', 'eloquentiam': '382', 'tota': '62', 'est': '41', 'persequeris': '105', 'iriure': '398', 'per': '22', 'epicurei': '299', 'reprimique': '109', 'necessitatibus': '411', 'adipisci': '182', 'atomorum': '48', 'sapientem': '338', 'definitionem': '127', 'definitiones': '286', 'stet': '114', 'probatus': '417', 'moderatius': '97', 'rebum': '107', 'intellegebat': '94', 'justo': '226', 'simul': '164', 'modo': '407', 'autem': '366', 'falli': '389', 'putant': '159', 'vituperata': '268', 'delectus': '198', 'adolescens': '356', 'praesent': '331', 'putent': '334', 'feugait': '218', 'maiorum': '238', 'dolorem': '380', 'singulis': '165', 'vivendum': '176', 'ubique': '171', 'forensibus': '219', 'illum': '223', 'eam': '27', 'illud': '458', 'mediocrem': '146', 'voluptaria': '444', 'admodum': '117', 'postea': '157', 'deserunt': '66', 'adhuc': '181', 'wisi': '353', 'ut': '9', 'malis': '239', 'reformidans': '108', 'eius': '298', 'vidit': '175', 'ad': '1', 'mundi': '320', 'fugit': '89', 'an': '2', 'consetetur': '373', 'at': '5', 'pertinacia': '326', 'albucius': '357', 'constituto': '125', 'no': '6', 'quaeque': '420', 'ne': '12', 'nam': '26', 'mucius': '242', 'dignissim': '203', 'alterum': '360', 'convenire': '195', 'denique': '199', 'dicam': '292', 'quidam': '423', 'assueverit': '364', 'lorem': '234', 'suscipiantur': '344', 'dicat': '293', 'voluptua': '352', 'ullamcorper': '437', 'nominavi': '466', 'eos': '24', 'porro': '330', 'consectetuer': '49'}

# base 36 impl from wikipedia
# http://en.wikipedia.org/wiki/Base_36#Python_implementation
def base36encode(number, alphabet='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
    """Convert positive integer to a base36 string."""
    if not isinstance(number, (int, long)):
        raise TypeError('number must be an integer')

    # Special case for zero
    if number == 0:
        return alphabet[0]

    base36 = ''

    sign = ''
    if number < 0:
        sign = '-'
        number = - number

    while number != 0:
        number, i = divmod(number, len(alphabet))
        base36 = alphabet[i] + base36

    return sign + base36

def base36decode(number):
    return int(number, 36)

def strict_code(code):
    return hex(int(code))[2:]

def strict_str(code):
    try:
        return str(int(code,16))
    except ValueError:
        return code

process.py - creates the encoding dictionary

#!/usr/bin/env python

from nltk.probability import *
from nltk.tokenize import *
from sets import Set

txt = open('lorem', 'r').read()
tokens = list(WordTokenizer().tokenize(txt))
freq = FreqDist()
for w in tokens:
    freq.inc(w.lower())
tokens_sorted = sorted(freq, key=freq.get, reverse=True)

d = {}
star_count = 0
for i in tokens_sorted:
    d[i] = str(star_count)
    star_count += 1

print d

First test case compressed

^M 8 6B 4F 2O, 1F 7A M C. ^BB 2H 18 2 10, 25 1P AG 13 D. ^I 1G 92 1, 7 8R 3Q S. ^0 11 5M 9D 9J. ^M 2 2O B1.~^5 Z 4N 5H 1D, M 9F 19 1. ^5 2V 1G 3E E, AU 1Z E 3. ^5 7Q 22 2K H, T 4V AO 0, W 7 5K 3Y. ^9Z 2M G 8, T 7 3C 1A.~^1P 4P 3M 6 O, I 4O 4P 4G 4, 1H CJ 57 S 1. ^1R 1A P 3, B J 5R 4W 4Y. ^V 1 B6 AW 42, BQ 17 7B C X, 1J 2Q 18 0 G. ^7 4T 2U V. ^V 4 2D A3 3H.~^0 Z 17 6D 9G, 2 Q 51 3A, 0 77 6K BL R. ^6 16 31 M, Y 0 96 89. ^R 5 1Q 6D 58, C 49 2N Y. ^7 2B 3Y P. ^2R 17 2Y U 1, 2A 2E 7A W 3.~^4J 7O L C. ^6 T 8V 6W 7Y, 1 3W D4 P, 1B 1L 43 N 9. ^4 CK 7P 4E S, N 4 4T 7O. ^D 12 6X 4J CM, X 1F 9G 9. ^G C9 4X C, V 67 5U 2N 1. ^7 W AN 5H 37, 66 4W 3P P 4.~^V 6D 2L 78 6, 2R 6F 4 H. ^A 3W 2A 8D X. ^0 O 76 1D. ^CX 3S R 3, 2 16 3P L, 5 Y B7 5D. ^U 1 3U AI BY, 4 49 43 8Q X. ^1B 1S 24 X K, 1Q 6A 2L L 8.~^E 1 5V 2Z 9J. ^K S 6A AQ 7U, 2H 7K 7X 1 J. ^2H 75 1D Q 1. ^4T 78 3E B L, 51 2L B 11, 4K 5B 41 D S. ^0 5C 7H G, 1H 9J X 7.~^11 6L 46 A. ^5 U 9P BI 23, O 2U 6W 2. ^X 3 2D 4Q 3F, M 5L 3R 0, B5 B9 2 Z. ^60 3K 4 X, V K 9Q 8O 2Y. ^P 5 7S 2N 7X. ^G B 35 98, 8W 3V B 15.~^2 V 4S 95 5E, J 0 5R A3. ^P 0 1B 27. ^E BW AH 5, 1A 3Q Q 2. ^25 8P 1L T A, I 7Q 6X 5.~^Q 8 39 3G 55. ^42 4H T 1. ^1 11 24 AL 2C. ^9 P 8A DA 9N, E K 6C 8I, 3 G 1Y 2U 7J.~^4N 2P L A, 54 8T 3 E. ^93 9W 88 K E, C 83 1R 44 E, D7 17 4G Y D. ^13 D 7D AQ 63. ^V 2 C2 5J 3Y, 51 5G B G. ^3 16 5D 1D L. ^8G BO I 7.~^M 4 6A 16 7W, 3 E 2A 3M, J 2 5M 2S. ^8J B9 V 1. ^74 7K O D, 2 2G 5N 3H Y. ^1B 62 1M T 9, 1N 73 CB B G, X C 1E 7H. ^R 1 2J 9U, 49 AE A S, B 9R 5F 3A 13. ^Q 26 61 2, M A 50 3V BF.~^5 16 41 27 10. ^5X 1R 7K 5 G, A 15 1J CN 9S. ^11 6J 2K 7K D, 12 7M 4S 19 K. ^0 6P 6T 27 R, 1U 9C 8N 3 Z. ^N 0 5V CB A2, S 5H 2X 4.~^2Z 5U F 1. ^2 I CS 1T, 7L 1T J 8. ^7I 3F 7T W 1. ^R 8 9E 19. ^F 3T 3N 2, 2Q 2Y F 4. ^H 5 7Z 3Y, A 1O 57 A4 W, I 25 2L A.~^0 9B 9A G, X 5 72 2K 3N, 4 F 6U 22. ^9 4W AX T, W 1 2T 71 AB. ^E 85 60 6F 6. ^51 7F BX A H, M 4 7Z BN.~^A L 47 6E. ^8X 6S 5Y 2 12, 93 4C B Q. ^1 I 7N 1V 33, 1 13 36 2P 27. ^4 9U 97 10. ^L 0 5A 3W, M 9X 56 6. ^7 5I 75 Q.~^7M 2T 0 Q, AK 2W 4B U 8. ^7N 1I 92 12 8, 9S 2W F 4. ^V 7 5T 1I 64, 14 66 9L 6. ^O 2 4V 4S, 74 5C P 4.~^5 O 25 2Q, 15 62 1V 0, 3G 2X 10 9. ^9G 38 58 M 7, 11 B 84 BL 52. ^2D 41 F 1. ^K 7S 7P F.~^3 7Q 30 T. ^4 G 4F 89, Q 1E 1I D2 K. ^B Z 3S 7V. ^5 AY 23 Q, 4Q 23 6E T 2, E 8 A7 5J 82.~^9L 94 8 E. ^B 62 8K U. ^S 3 67 6I 1R, BS 26 L 7, B3 3E K H. ^72 3D 30 10 2, A 45 83 22 F.~^4N 6R 5 L, 12 D 65 3Z AA. ^K M 60 6C, 9 4V 88 3A N. ^D V 5W 4G. ^H 1 5I 52 79, S 4 34 C0. ^36 7X 30 L 9. ^P 3D 1V 5. ^Q 1E 70 1.~^6 12 1Q 3L, 5P 77 49 2 13. ^7R 2A 3E 5 W, 8 BH 5O 55 T, 8W 1B 0 N. ^DC 5V 9T 6 H, V 26 3V A. ^2 7O 2P 32 E. ^D 38 6W M.~^16 50 31 A 10, X 3 5Q DG 9F, A8 99 0 11. ^3I 7J B H, 5B D1 5S 6 P. ^E A 6U 2O, E 1J 62 5S 6. ^I 2 6N 35, 1W 28 9 U, J 34 8C A. ^Z 4D 37 7C 1, L 6 5K BZ 9M.~^7W 2Y Z 0. ^4M 4H U 5, 0 15 2V 9V 63, 2D 4G P 4. ^AH 2E F 3, 0 15 91 6O 1T, 3 N 2G 6Z. ^U K 1J 4K 46, 3 H BD DF AJ, 11 D D6 1H.

Sources in my github repo.


Python 2, 22 bytes

lambda n:n*~n*~(n*2)/6

Try it online!

This uses the closed-form formula n * (n+1) * (2*n+1) / 6. The code performs the following operations:

Multiplies n by (n*):

The bitwise complement of n (~n), which essentially means -1-n.
And by the bitwise complement of 2n (*~(n*2)), which means -1-2n.

Divides by 6 (/6).

Python 2, 27 bytes

f=lambda n:n and f(n-1)+n*n

Try it online!

Saved 1 byte thanks to Rod and 1 thanks to G B.


Java 8, 153 141 135 131 129 bytes

a->{int l=a.length,t,r=0,i=-1;for(;++i<l;r+=(t=a[i]=a[i]>4?t<3?t^3:3:a[i]>3?t:a[i])>2?0:3-t*2)t=a[i>0?i-1:i<l-1?i+1:i];return r;}

Uses an integer array as input with A=1, B=2, N=3, X=4, Y=5 and outputs a positive integer (>= 1) if A wins, a negative integer (<= -1) if B wins, or 0 if it's a draw.
-18 bytes thanks to @OlivierGrégoire.
Try it online.
Explanation:
a->{                      // Method with int-array parameter and boolean return-type
  int l=a.length,         //  Length of the input-array
      t,                  //  Temp integer, uninitialized
      r=0,                //  Result-integer, starting at 0
  i=-1;for(;++i<l         //  Loop `i` in the range [0, l):
           ;              //    After every iteration:
            r+=           //     Increase the result by:
             (t=a[i]=     //       Change `i`'th item in the array to:
                 a[i]>4?  //        If the `i`'th item is a 5:
                  t<3?    //         If `t` is 1 or 2:
                   t^3    //          Use `t` Bitwise-XOR 3 to invert it
                          //          (1 becomes 2; 2 becomes 1)
                  :       //         Else (`t` is 3, 4, or 5 instead):
                   3      //          Set it to 3
                 :a[i]>3? //        Else-if the `i`'th item is a 4:
                  t       //         Set it to `t`
                 :        //        Else (the `i`'th item is a 1, 2 or 3):
                  a[i])   //         Leave it unchanged
             )>2?         //      And if this new `i`'th value is 3, 4, or 5:
              0           //       Leave the result the same by increasing it with 0
             :            //      Else (it's 1 or 2 instead):
              3-t*2;      //       Increase it by 3 minus two times the `i`'th value
                          //       (which is 1 for 1; and -1 for 2)
         t=               //   Set `t` to:
           a[i>0?         //    If `i` is not the first item:
              i-1         //     Set `t` to the previous (`i-1`'th) value
             :i<l-1?      //    Else-if `i` is not the last item:
              i+1         //     Set `t` to the next (`i+1`'th) value
             :            //    Else (`i` is the first or last item):
              i];         //     Set `t` to the current item itself
  return r;}              //  Return the result
                          //  (positive if A wins; negative if B wins; 0 if it's draw)


Retina, 103 74 71 bytes

<
>>>
+`(>(\^*>){3})\^
^$1
+`\^(>\^*>)\^
$1
>>(\^*)>(\^+)
<$2<$1
<?>*$

Try it online! Link includes test cases. Explanation:

<
>>>

Turn left turns into triple right turns.

+`(>(\^*>){3})\^
^$1

Reduce all turns modulo 4.

+`\^(>\^*>)\^
$1

Cancel out movements in opposite directions.

>>(\^*)>(\^+)
<$2<$1

Turn a triple right turn back into a left turn. This also handles the case of >>^>^ which needs to become <^<^.

<?>*$

Delete unnecessary trailing turns.


JavaScript (ES7), 282 273 251 250 bytes
Takes a keyboard layout ID k and an array of characters a in currying syntax (k)(a). Returns an array of translated characters.
The layout IDs are:

DVORAK: \$-32\$
COLEMAK: \$64\$
WORKMAN: \$160\$

k=>a=>a.map(c=>1/(t=`1_3-2}w[vz8SsW]VZ1XJE>UIDCHTN0BRL"POYGK<QF:/0=0{1xje.uidchtn0brl'poygk,qf;?0+995Oo6SFTD0UNEI0KY:0PRGL2J8sftd0unei0ky;0prgl2j998Ii5VMHRT0YUNEOLKP:0W0BFCD0J6vmhrt0yuneolkp;0w0bfcd0j5`.replace(/\d/g,n=>15**n)[c.charCodeAt()+k])?c:t)

Try it online!
How it works
Compression
All three target layouts are stored in a single compressed string, where each character is either:

a translation character from QWERTY
a digit representing the number of consecutive characters that do not need to be translated

More specifically, a digit \$n\$ is interpreted as the length of the number \$15^n\$ in base \$10\$:
n | 15**n       | length
--+-------------+-------------
0 | 1           | 1
1 | 15          | 2
2 | 225         | 3
3 | 3375        | 4
4 | 50625       | 5 (not used)
5 | 759375      | 6
6 | 11390625    | 8
7 | 170859375   | 9 (not used)
8 | 2562890625  | 10
9 | 38443359375 | 11

For instance, #$%&-()* in DVORAK is stored as 3-2 because #$%& and ()* have identical mappings in QWERTY and only - is an actual translation.
In particular, 0123456789 is mapped the same way on all layouts and never has to be translated. Therefore, there's no possible ambiguity between a digit used for compression and a digit used for translation.
Decompression
To decompress the layout string, we replace each digit \$n\$ with \$15^n\$. For instance, 3-2 is decompressed as 3375-225.
Translation
For each character c in a, we extract the translation character t, using k as an offset in the uncompressed layout string, and test whether it's a digit with 1/t. If so, we output the original character c instead.


05AB1E, 13 bytes
Generates a random integer \$k\$ until both \$k\$ and \$k+n\$ are prime.
[Î‚[>₄Ω#}DpP#

Try it online! Runs the program 1000 times and shows the unique results.
Commented:
[              # loop:
 Î‚            # push [0, input]
   [    }      # loop:
    >          #   increment both integers
     ₄Ω        #   draw a random digit of 1000
       #       #   if this is 1, stop the loop
         D     # duplicate the current pair
          p    # for both integers: are they prime?
           P   # take the product
            #  # if both are prime, end the main loop

Old answer that always just generates one random integer, 22 bytes:
∞+∞ø.ΔpP}D[₄Ω#>}DpP_i\

Try it online! Runs the program 100 times to demonstrate different outputs.
∞+∞ø.ΔpP} finds the first valid pair.
[₄Ω#>} is a loops which increments the pair and has a \$50\%\$ probability to stop at every iteration.
DpP_i\ removes the new pair if any of the numbers is not prime.


Haskell, LD = 13, cracked

((snd.span(<'1').reverse.show.(^2)=<<[1..])!!)

Try it online!

I double-checked that leading zeros are trimmed ;)

Explanation:

                    [1..]     -- for each element in [1,2,3,4,5,...]
                 =<<          -- apply the following functions
             (^2)             -- square [1,4,9,16,25,...]
           show.              -- convert to string ["1","4","9","16","25",...]
       reverse.               -- reverse ["1","4","9","61","52",...,"001",...]
   span(<'1').                -- split into leading zeros and remainder [("","1"),("","4"),...,("00","1"),...]
  snd.                        -- only keep remainder ["1","4","9","61","52",...,"1",...]
                              -- and concatenate the result "1496152..."
((                       )!!) -- index into the sequence


JavaScript (ES6), 121 bytes
Expects (month)(year). The day is ignored.

m=>y=>"9512444".replace(/./g,n=>(100+(y-(m<3))%50+50*(m<3|m>8)+n)[n]||'ABCDEFGHKLMNOPRSVWYJTUXZ'[Math.random()*(28-n)|0])

Try it online!


Haskell, 21 bytes

(!!).([(<0),(>0)]<*>)

Try it online!

Outputs a boolean with True being move forward and False being turn right.

Haskell, 28 bytes

Here's a version that is easy to understand / translate into any language.

f(x,y)d=[x<0,y<0,x>0,y>0]!!d

Try it online!

Explanation

The idea here is two-fold

We notice that we only ever need to turn in one direction.  A turn left is just 3 turns right.  So we will limit ourselves to only right turns.
Now we notice that given a direction there is a simple condition that can check if we ought to move forward.  Namely the sign of one of the two variables.

With this information we construct out solution, by making a list of the conditions and indexing the list with the direction.  True means the condition was passed and we can move forward (so we do), False means the condition was failed and we should not move forward, so we rotate.

Now the specification allows us to just output these values as is, since they are distinct and we have no intention of turning left.


Make any number by repeatedly adding 2 numbers

Perl 107 97

First post, so here goes.

sub h{($i)=@_;return if(($i%=65536)==0);($i%4==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}

Which fits all of the register addition criteria, but I didn't run an exhaustive check to see if my answer was always within 2n+2 of the optimal number of steps.  It is well inside the limit for every Fibonacci number, though.

Here is a more detailed breakdown

sub h{                           # Declare the subroutine, it should be called referencing an integer value
   ($i)=@_;                      # Assign the i variable to the integer used in the call
   return if(($i%=65536)==0);    # Check for base condition of called by 0, and enforce modulo from the start.
   ($i%4==0) ?                   # If the value passed is even, and will result in an even number if we halve it
   do{h($i/2);say"y+=y";}        # Then do so and recurse
   :do{h($i-1);say"y+=x";}       # Otherwise "subtract one" and recurse
}                                # Note that the print statements get called in reverse order as we exit.

As I mentioned, this is my first attempt at golfing, so I'm sure this can be improved upon.  Also, I'm not sure if the initial subroutine call has to be counted in a recursive call or not, which could drive us up a few chars.

Interestingly we can reduce the code by 11 bytes* and improve our "efficiency" in terms of the number of register operations, by relaxing the requirement that only even values can be "doubled".  I've included that for fun here:

sub h{($i)=@_;return if(($i%=65536)==0);($i%2==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}

Begin addendum:

Really liked this problem, and I've been fiddling with it off and on for the last couple weeks.  Thought I would post my results.

Some numbers:

Using a BFS algorithm to find an optimal solution, in the first 2^16 numbers there are only 18 numbers that require 23 steps.  They are: 58558, 59894, 60110, 61182, 61278, 62295, 62430, 62910, 63422, 63462, 63979, 64230, 64314, 4486, 64510, 64698, 64854, 65295.

Using the recursive algorithm described above, The "most difficult" number to reach is 65535, at 45 operations.  ( 65534 takes 44, and there are 14 numbers that take 43 steps)  65535 is also the largest departure from optimal, 45 vs 22.  The 23 step difference is 2n+1.  (Only three numbers hit 2n: 65534, 32767, 32751.)  Excepting the trivial (zero-step) cases, over the defined range, the recursive method averages approximately 1.4 times the optimal solution.

Bottom line: For the numbers 1-2^16, the recursive algorithm never crosses the defined threshold of 2n+2, so the answer is valid.  I suspect that it would begin to depart too far from the optimal solution for larger registers/more bits, however.

The code I used to create the BFS was sloppy, memory intensive, not commented, and quite deliberately not included.  So... you don't have to trust my results, but I'm pretty confident in them.


MATL, 47 43 bytes
nW:qB!ts2#Sw2>)PZ)"1G@)XJ2XN!"@sJ@X-m~*]?J.

Try it online!
Explanation
This uses two loops: an outer loop to generate all possible subsets, and an inner loop to take all pairs of elements and see if the sum equals any other element of the subset.
Subsets of at least 3 elements are tested in order of decreasing number of elements. The code stops as soon as a valid subset is found.
          % Take input implicitly
nW:q      % Generate [0 1 ... 2^n-1] where n is input length
B!        % Convert to binary. Gives a matrix. Each number corresponds to a column.
          % This will be used to select the elements of each subset
ts        % Duplicate. Sum of each column
2#S       % Sort. Output the sorted array and the indices of the sorting. Each index
          % corresponds to one possible subset
w2>       % Swap. Logical index of values that exceed 2. This is used to pick only
          % subsets of more than 2 elements
)         % Keeps only indices of subsets that have at least 3 elements
P         % Flip. This moves subsets with more elements to the front. As soon as a
          % subset fulfills the condition the outer loop will be exited, so we need
          % to start with the bigger subsets
Z)        % Index into columns of binary matrix. Each column is the binary pattern
          % defining a subset with at least 3 elements, starting with bigger subsets
"         % For each column. Each iteration corresponds to a subset
  1       %   Push 1
  G@)     %   Pick actual elements of each subset (logical index into input)
  XJ      %   Copy to clipboard J
  2XN!    %   All pairs of 2 elements from that subset. Each pair is a column
  "       %   For each column. Each iteration corresponds to a pair of elements
    @s    %     Sum of those two elements
    J@X-  %     Array with the other elements (obtained with set difference)
    m~    %     True if the sum of the two elemens is not a member of the array
    *     %     Multiply. Corresponds to logical AND
  ]       %   End for
  ?       %   If result is true: no sum of two elements equalled any element
    J     %     Push found subset (will be displayed implicitly)
    .     %     Exit loop
          %   End if implicitly
          % End for implicitly
          % Display stack implicitly


Retina 0.8.2, 43 50 bytes

^.*\.(..)*1(.)((..)+)1.((..)*)$
$2$*-$3.$5
0(.)
$1

Try it online! I/O is as a binary string. Encode a binary number y close to another binary number a as follows:

If a does not contain a ., suffix one.
If a contains an odd number of digits after the ., suffix a 0.
If y is negative then suffix 11 otherwise suffix 10.
For each digit in y, suffix 0 followed by that digit.
If y contains a ., suffix 11 at that point, otherwise suffix it after all the digits in y.

Explanation:

^.*\.(..)*1(.)((..)+)1.((..)*)$
$2$*-$3.$5

Pair the digits starting at the binary point. If the number is a valid encoding, then decode the last 1x digit pair to a . and the second last to an optional - sign. Digits before that are ignored.

0(.)
$1

This should just leave pairs that begin with 0, so delete the 0s.


Python

N, H = map(int, raw_input().split())
D = map(int, raw_input().split())

# map from (number of dominoes, distance to last domino) to
# the number of moves needed to adjust the first number of dominoes
# exactly that far.
M = {}
M[1,0] = 0

for i in xrange(2, N+1):      # i = number of dominos to try
  for d in xrange(H*(i-1)+1):
    M[i,d] = 1e9
  for d in xrange(H*(i-1)+1): # position of last domino
    for e in xrange(1, H+1):  # distance from last domino to previous one
      if d-e > H*(i-2): continue
      if d-e < 0: continue
      if sum(D[:i-1]) == d:
        # don't move last domino, arrange rest
        M[i,d] = min(M[i,d], M[i-1,d-e])
      else:
        # arrange rest, move last domino to right location
        M[i,d] = min(M[i,d], 1 + M[i-1,d-e])

print M.get((N,sum(D)), -1)

Standard dynamic programming.  Runs pretty much instantaneously on the example inputs.  How big a problem do we have to solve in under a second?


Wolfram Language (Mathematica), 59 bytes
FromDigits@MapAt[RotateLeft@*List@@#&,RealDigits@#,{1,-1}]&

Try it online!
Explanation
RealDigits@#

Find the decimal digits of the input.
MapAt[RotateLeft@*List@@#&, ..., {1,-1}]

If there are repeating digits, RotateLeft them. (List@@# prevents the code from attempting to rotate the last decimal digit if the rational number is terminating).
FromDigits@

Convert to rational.


Simulate a (gravity-based) billiard-ball-type computer

JavaScript (392 423)

Assumes machine is set in a variable called m, then alerts the final output.

l=m.split(q='\n');o='';for(r=Array(z=l[i=0].length);i<l.length;i++){L=l[i];n=Array(z);for(c=0;c<z;n[c]=N,r[c++]=R){C=L[c];N=~~n[c];R=~~r[c];if(C>'`'){N+=x=~~prompt(C);R+=x;o+=C+': '+x+q}else if(C=='\\'||C=='/'){for(d=c+(g=C=='/'?-1:1);L[d]=='_';r[d]+=R,d+=g);if(L[d]>'@'&L[d]<'[')r[d]+=r[c];n[d]=~~n[d]+R}else if(C<'2')N+=R+=~~C;else if(C!='_')o+=C+': '+R+q}for(c=0;c<z;c++)if(L[c]=='_')n[c]+=(r[c]%2)?0:r[c]>0;r=n}alert(o)

Sample source (runs adder machine, see history for less golfed sources): http://jsfiddle.net/96yLj/12/

Spoilers:

   - r tracks the # of balls across current row, n tracks # of balls across next row.
 - Algorithm: process each row character by character, but process _'s last.
 - Algorithm: \ -> follow _ and increase r until non-_. Same for / but in reverse direction.  At the end increase n for gravity pulling balls down. g holds direction.
 - if(L[d]>'@'&L[d]<'[')r[d]+=r[c]; is for the bug mentioned in Edit 1.  The reason we can't just say r[d]+=r[c]; is because \_/ will double-count balls when processing /
 - else if(C<'2') handles both cases '1' and ' ', which ~~C turns into 1 and 0, respectively.

Edit 1: Fix bug with ball running over _ not included in A for sample code.


Python 2,  134 131 128 124 120 117 109  107 bytes

p=input();s=0
for X,Y in p[1:]:x,y=p.pop(0);n=y-max(zip(*p)[1]);s+=n*(1+((X-x)/(y-Y))**2)**.5*(n>0)
print s

Try it online!

Takes input as a list of tuples / two-element lists of floating-point numbers.

Explanation

We basically iterate through the pairs of points in the graph, and if
\$y_1 > y_2\$, then we calculate how much of the line is exposed to light. The pairwise iteration is performed with a for loop to get the next point, \$(x_2, y_2)\$, popping the first element in the list each time to retrieve the current point, \$(x_1, y_1)\$.

Maths – What part of the line segment is exposed to light?

Let \$(x_1, y_1)\$ be the coordinates of the current point. Let \$y_{max}\$ be the maximum height of a point after the current one (local maxima after the current point)  and \$(x_2, y_2)\$ be the coordinates of the next point. In order to calculate the length exposed to the sun, \$L\$, we ought to find \$x_3\$, as shown in the diagram. Naturally, if \$y_1 \le y_{max}\$, the  segment is not exposed to light at all.

In the triangle formed, the line segment of length \$x_3\$ is parallel to the base, of length \$x_2 - x_1\$, so all three angles are congruent. Therefore, from the Fundamental Theorem of Similarity (case Angle-Angle), we can deduce that \$\frac{x_3}{x_2 - x_1} = \frac{y_1-y_{max}}{y_1}\$. Hence, \$x_3 = \frac{(y_1-y_{max})(x_2 - x_1)}{y_1}\$. Then, we can apply the Pythagorean Theorem to find that:

$$L = \sqrt{(y_1-y_{max})^2+x_3^2}$$

By joining the two formulas, we arrive at the following expression, which is the core of this approach:

$$L = \sqrt{(y_1-y_{max})^2+\left(\frac{(y_1-y_{max})(x_2 - x_1)}{y_1}\right)^2}$$
$$L = \sqrt{(y_1-y_{max})^2\left(1+\frac{(x_2 - x_1)^2}{y_1^2}\right)}$$

Code – How does it work?

p=input();s=0                             # Assign p and s to the input and 0 respectively.
for X,Y in p[1:]:                         # For each point (X, Y) in p with the first
                                          # element removed, do:
    x,y=p.pop(0)                          # Assign (x, y) to the first element of p and
                                          # remove them from the list. This basically
                                          # gets the coordinates of the previous point.
    n=y-max(zip(*p)[1])                   # Assign n to the maximum height after the
                                          # current one, subtracted from y.
    s+=n*(1+((X-x)/(y-Y))**2)**.5         # Add the result of the formula above to s.
                                 *(n>0)   # But make it null if n < 0 (if y is not the
                                          # local maxima of this part of the graph).
print s                                   # Output the result, s.

Changelog

Gradually optimised the formula for golfing purposes.
Saved 1 byte thanks to FlipTack.
Saved 2 bytes by removing the unnecessary condition that y>Y, since if the local maxima of the Y-coordinate after the current point subtracted from y is positive, then that condition is redundant. This unfortunately invalidates FlipTack’s golf, though.
Saved 3 bytes by changing the algorithm a bit: instead of having a counter variable, incrementing it and tailing the list, we remove the first element at each iteration.
Saved 8 bytes thanks to ovs; changing (x,y),(X,Y) in the loop condition with a list.pop() technique.
Saved 2 bytes thanks to Ørjan Johansen (optimised the formula a little bit).


Brachylog, 8 bytes

ḃ₁₀₀₀↰₁ᵐ

Try it online!

The blackbox function goes on the second line (or the "Footer" on TIO) and the integer is read from STDIN. Prints true. or false. accordingly.

ḃ₁₀₀₀      Compute the base-1000 digits of the input.
     ↰₁ᵐ   Map the blackbox predicate over each digit. We don't care about the
           result of the map, but the predicate must succeed for each digit,
           otherwise the entire map fails.


JavaScript (Node.js), 61 55 54 bytes

Saved 1 byte thanks to @nwellnhof

Takes input as an array of characters.

s=>s.map(p=c=>r+=p>(p=(+c?~c:1-Buffer(c)[0])%6),r=0)|r

Try it online!

How?

For all characters but digits greater than \$0\$, the 0-indexed column \$x\$ is given by:

$$x=(c-1)\bmod 6$$

where \$c\$ is the ASCII code of the character.

For positive digits \$n\$, we need to do instead:

$$x=(n+1)\bmod 6$$

Examples:

"a" --> (97 - 1) mod 6 = 96 mod 6 = 0
"b" --> (98 - 1) mod 6 = 97 mod 6 = 1
"0" --> (48 - 1) mod 6 = 47 mod 6 = 5
"3" --> ( 3 + 1) mod 6 =  4 mod 6 = 4

Commented

s =>                       // s = input string (as array)
  s.map(p =                // initialize p to a non-numeric value
  c =>                     // for each character c in s:
    r +=                   //   update the result r:
      p > (                //   compare p with
        p = (              //   the new value of p defined as:
          +c ?             //     if c is a positive digit:
            ~c             //       -(int(c) + 1)
          :                //     else:
            1-Buffer(c)[0] //       -(ord(c) - 1)
        ) % 6              //     apply modulo 6
      ),                   //   yields 1 if the previous value is greater than the new one
    r = 0                  //   start with r = 0
  ) | r                    // end of map(); return r


Mathematica, 69 68 bytes

Thanks to Martin Ender for finding an extra –1 byte for me!

Last@Nest[{##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&,{},#]&

Unnamed function taking a positive integer n as input and returning a positive integer. We construct the entire list of the first n elements of this sequence, then take the Last element. The list is constructed by starting with the empty list {} and operating on it with a function n times in a row (via Nest).

The function in question is {##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&, which takes a partial list of sequence values (essentially ##&@@#) and appends the next value to it. The next value is computed by starting with x=1, then repeatedly replacing x by x+1 as long as the condition x==Last@#||#~Count~x==#[[x]] is met—in other words, if either x is the previous element, or else x is already in the list the correct number of times. This function spits some errors, since (for example) we shouldn't be calling the xth element of the initial list {}; however, the values are all correct.


Japt, 3 bytes
o ï

Try it
o       :Range [0,input)
  ï     :Cartesian product with itself


43 bytes

(4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n<1

Try it online!

The method is similar to Dennis' second (deleted) answer, but this answer is easier to be proved correct.

Proof

Short form

The most significant digit of (4**n+1)**n%4**n**2 in base \$2^n\$ that is not divisible by \$n\$ will make the next (less significant) digit in (4**n+1)**n%4**n**2/n nonzero (if that "next digit" is not in the fractional part), then a & with the bitmask 2**(2*n*n+n)/-~2**n is executed to check if any digit at odd position is nonzero.

Long form

Let \$[a_n,\dots,a_1,a_0]_b\$ be the number having that base \$b\$ representation, i.e., \$a_nb^n+\dots+a_1b^1+a_0b^0\$, and \$a_i\$ be the digit at "position" \$i\$ in base \$b\$ representation.

\$\texttt{2**(2*n*n+n)/-~2**n}
=\lfloor{2^{(2n+1)n}\over1+2^n}\rfloor
=\lfloor{4^{n^2}\times 2^n\over1+2^n}\rfloor
=\lfloor{{(4^{n^2}-1)\times 2^n\over1+2^n}
+{2^n\over1+2^n}}\rfloor
\$.

Because \$2^n\times{4^{n^2}-1\over1+2^n}
=2^n(2^n-1)\times{(4^n)^n-1\over4^n-1}
=[2^n-1,0,2^n-1,0,2^n-1,0]_{2^n}\$ (with \$n\$ \$2^n-1\$s) is an integer,
and \$\lfloor{2^n\over1+2^n}\rfloor=0\$,
2**(2*n*n+n)/-~2**n = \$[2^n-1,0,2^n-1,0,2^n-1,0]_{2^n}\$.

Next, consider
$$\begin{align}
\texttt{(4**n+1)**n}
&=(4^n+1)^n \\
&=\binom n04^{0n}+\binom n14^{1n}+\dots+\binom nn4^{n^2} \\
&=\left[\binom nn,0,\dots,0,\binom n1,0,\binom n0\right]_{2^n}
\end{align}$$

\$4^{n^2}=(2^n)^{2n}\$, so %4**n**2 will truncate the number to \$2n\$ last digits - that excludes the \$\binom nn\$ (which is 1) but include all other binomial coefficients.

About /n:

If \$n\$ is a prime, the result will be \$\left[\binom n{n-1}/n,0,\dots,0,\binom n1/n,0,0\right]_{2^n}\$. All digits at odd position are zero.
If \$n\$ is not a prime:

Let \$a\$ be the largest integer such that \$n\nmid\binom na\$ (\$n>a>0\$). Rewrite the dividend as

\$\left[\binom n{n-1},0,\binom n{n-2},0,\dots,\binom n{a+1},
    0,0,0,\dots,0,0,0\right]_{2^n} +
\left[\binom na,0,\binom n{a-1},0,\dots,\binom n0\right]_{2^n}\$

The first summand has all digits divisible by \$n\$, and the digit at position \$2a-1\$ zero.

The second summand has its most significant digit (at position \$2a\$) not divisible by \$n\$ and (the base) \$2^n>n\$, so the quotient when dividing that by \$n\$ would have the digit at position \$2a-1\$ nonzero.

Therefore, the final result ((4**n+1)**n%4**n**2/n) should have the digit (base \$2^n\$, of course) at position \$2a+1\$ nonzero.

Finally, the bitwise AND (&) performs a vectorized bitwise AND on the digits in base \$2^n\$ (because the base is a power of 2), and because \$a\texttt &0=0,a\texttt&(2^n-1)=a\$ for all \$0\le a<2^n\$, (4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n is zero iff (4**n+1)**n%4**n**2/n has all digits in first \$n\$ odd positions zero - which is equivalent to \$n\$ being prime.


Jelly, 5 bytes

DḤ+¥/

Try it online!

Explanation

The cast

D is a monad (single argument function): digits, turning 1234 into [1, 2, 3, 4].
Ḥ is a monad that doubles its single argument.
+ is a dyad (two argument function) that adds its left and right arguments.

From there, it gets a little tricky.

Here’s what happens at parse time

D, Ḥ, and + are read. The chain looks like [D, Ḥ, +].
The next two characters are quicks, which act like parse-time postfix operators on the links (functions) we've read so far.
When ¥ is read, the last two links get popped and replaced by a link that acts like the dyad formed by composing them. So now the chain looks like [D, dyad(Ḥ+)].
When / is read, the last link (which ought to be a dyad) gets popped and replaced by a monad that folds using this dyad (intuitively: f/ takes a list, replaces the commas in it with f, and evaluates the result.)
The final chain looks like [D, fold(dyad(Ḥ+))], two monads.

Here's what happens at run time

Input (a number) is implicitly read into the working value (say, 101010).
D is executed, replacing the working value with its digits ([1,0,1,0,1,0]).
fold(dyad(Ḥ+)) is executed, replacing the working value with 1∗0∗1∗0∗1∗0, where ∗ is the dyad Ḥ+.

So what does x∗y evaluate to?

In a dyadic definition, the working value is initially the left argument, x.
Ḥ, the double monad, doubles this value. The working value is now 2x.
+, the plus dyad, lacks a right argument, so this is a hook: a special syntactical pattern where the right argument of this dyad gets injected into +. This yields 2x + y as the final working value, which is returned.

So the whole expression evaluates to:

1∗0∗1∗0∗1∗0 = 2×(2×(2×(2×(2×1+0)+1)+0)+1)+0
            = 32×1 + 16×0 + 8×1 + 4×0 + 2×1 + 1×0
            = 42


Wolfram Language (Mathematica), 22 bytes
#!~IntegerExponent~#2&

Try it online!


Dyalog APL (10)

⎕TSYNC⎕TID

⎕TSYNC makes the thread wait until the given thread ends,  ⎕TID gives the current thread.

Dyalog APL can recognize deadlocks though, so it immediately responds with

DEADLOCK

The fun thing is, you don't even need to spawn any extra threads, making the UI thread wait for itself is plenty.

If this is cheating and new threads are actually required, you can do it in 27 characters:

{∇⎕TSYNC&{⎕TSYNC⎕TID+1}&0}0

F & x runs F in a new thread on value x, and returns the thread ID. So:

{⎕TSYNC⎕TID+1}&0 creates a thread that will synchronize with the thread whose ID is one higher than its own,
⎕TSYNC& creates a new thread that will synchronize with the previous thread, and which gets an ID one higher than the thread that was just created (assuming nothing else is creating threads).
∇ causes an infinite loop (so we keep creating threads until there's a deadlock).

This will deadlock as soon as the second thread gets created before the first one starts running, which is pretty soon:

9:DEADLOCK


JavaScript (ES6),  44  43 56 bytes

Saved 1 byte thanks to ETHproductions
Edit: fixed to comply with output requirements

(a,b,c,d)=>{for(s='';eval(a+b+c);a+=d)s+=a+`
`;alert(s)}

Test

let f =

(a,b,c,d)=>{for(s='';eval(a+b+c);a+=d)s+=a+`
`;alert(s)}

f(1,'<',7,2)


Python 3, 113 62 bytes

for i in[1]*3:x|={a+b for a in x for b in x}
while{i+1}&x:i+=1

Here x is the input as a set of ints, and i is the output.

Try it online!

(Thanks: Erik the Outgolfer, Mr. Xcoder, Lynn)


Python 2, 338 335 330

Try it online!

from itertools import*
n,k=input()
O=[([0]*k,)]
R=range(k)
exec"O={min(tuple(sorted(zip(*[[x-min(p)for x in p]for p in f])))for q in permutations(zip(*(o+(r,))))for f in product(*[[p,[-x for x in p]]for p in q]))for o in O for s in o for r in[tuple(s[i]+x*(i==j)for i in R)for j in R for x in-1,1]if not r in o};"*~-n
print len(O)

Reads n,k as a list from stdin (e.g. [4,2]) and prints the number of polyominoes.

Starts with a single polyomino with a single cell at the origin.

n-1 times, replaces the polyominoes with all possible polyominoes created by adding an adjacent cell to an existing polyomino, and canonizing that polyomino by finding the minimum of all possible rotations of it.

-6 bytes thanks to math junkie, -2 bytes thanks to Surculose Sputum.


GNU Prolog, 105 points

s(U,L/M,C):-prefix(A,C),length(A,M),suffix(U,A),length(U,L).
o(A-B,C-X-Y):-length(C,_),s(A,X,C),s(B,Y,C).

(This requires GNU Prolog because prefix and suffix are not portable.)

Prolog has one interesting, major advantage for this challenge; you can write a function to handle multiple call patterns (i.e. not only can you give the function an input to get a corresponding output, you can give the function an output to get the corresponding input). As such, we can define a function that can handle both compression and decompression, leading to a 105-byte submission that defines a function o that works both ways round. (Incidentally, I mostly wrote it as a decompressor – as it's simpler – and got the compressor "for free". ) In general, we could expect a very short program in Prolog for this task, if not for the fact that it's so bad at string handling (both in terms of missing primitives, and in terms of the primitives in question having terribly long names).

The first argument to o is a tuple of strings, e.g. "abcd"-"deab". The second argument has a form like "deabcd"-4/6-4/4; this is a fairly standard nested tuple, and means that the string is "deabcd", the first string has length 4 and ends at the sixth character, the second string has length 4 and ends at the fourth character. (Note that a string in GNU Prolog is just a list of character codes, which makes debugging annoying because the implementation prefers the latter interpretation by default.) If you give o one argument, it'll output the other for you (thus working as a compressor if you give the first argument, and a decompressor if you give the second). If you give it both arguments, it'll verify that the compressed representation matches the strings given. If you give it zero arguments, it'll generate output like this:

| ?- o(X,Y).
X = []-[]
Y = []-0/0-0/0 ? ;

X = []-[]
Y = [_]-0/0-0/0 ? ;

X = []-[A]
Y = [A]-0/0-1/1 ? ;

…many lines later…

X = [A]-[B,A,C]
Y = [B,A,C]-1/2-3/3 ? ;

The above description of the I/O format is pretty much entirely just a description of the program, too; there's not very much in the program at all. The only subtlety is to do with evaluation order hints; we need to ensure that the program doesn't just use a search strategy that's guaranteed to terminate, but also produces the shortest possible output string.

When compressing, we start with length(C,_) ("C has a length"), which is a trick that I've used in many Prolog and Brachylog answers; if this is the first thing Prolog sees, it'll cause it to prioritise reducing the length of C over anything else. This ensures that we have a minimum-length C. The ordering of the constraints in s is carefully chosen so that the search will take a finite time for each possible candidate length of C; A is constrained by C (we don't know C, but we do know the target value we have for its length), M by A, U by A, and L by U, so none of the searches can take unlimited time.

When decompressing, we're given C directly by the user. This again ensures the program will run in finite time, due to the same sequence of constraints. (People who are aware of Prolog's evaluation order will note that the definition of s is very inefficient when decompressing; placing length(A,M) and length(U,L) first would be faster, but moving length(A,M) to the start could cause an infinite loop when compressing because neither A nor M is bound by anything at the time.)


JavaScript 65 bytes

s=>(q=s.split(/[()]/))[1].replace(/(\D?)(\d+)/g,`$1(${q[0]}*$2)`)

This will take the input. Get the + or -, then the digits, then replace it in the correct order.

Explanation

s=>   // Function with argument "s"
  (q= // Set q to...
    s.split(/[()]/) // Splits on parenthesis, returns array
  )
  [1] // Gets second match or text inside brackets
  .replace(/ // Replaces string
     (\D?)  // Try to match a non-digit, the +-/* (group 1)
     (\d+)  // Then match one or more digits (group 2)
  /,
      // $1 is group 1 and $2 is group 2 q[0] is the text before the parenthesis
  `$1(${q[0]}*$2)`
  )

Usage

This only works in Firefox and Safari Nightly maybe Edge? because it uses ES6 features. You can run it by:

var t=s=>(q=s.split(/[()]/))[1].replace(/(\D?)(\d+)/g,`$1(${q[0]}*$2)`)

t("5(-6+7+3-8+9)"); // -(5*6)+(5*7)+(5*3)-(5*8)+(5*9)


Take first letter of each word, leave spaces and punctuation

CJam, 13 bytes
r{(\'A,f&Sr}h

Works if I can consider only the common punctuation characters, and the output can have trailing spaces. (Thanks to Dennis.)
This question needs much more clarification...
CJam, 17 16 bytes
r{(\eu_elf&Sr}h&

Try it online.
Explanation
r          e# Read one word from input.
{          e# While it is not EOF:
    (\     e# Extract the first character.
    eu     e# Convert the rest to uppercase.
    _el    e# And lowercase.
    f&     e# Delete characters in the first string if not in the second string.
    S      e# Append a space.
    r      e# Read the next word.
}h
&          e# Discard the last space by intersecting with empty string.


Pyth, 35 bytes (38 - 15% = 31.45 farther down)

#I!sm><FhMds<MCeMd^JC,mOQK^UQvzK2JB

Demonstration

Input is in the format:

n
s

Output is in the format:

[[value, tuple], [value, tuple], ...]

Simply generates random possibilities and tests them.

Alternative 37 byte version which I believe qualifies for the bonus:

Of!sm><FhMds<MCeMd^T2mC,d^UQvz^UQ^Qvz

Demonstration

This starts by generating all possible monotonic functions, then outputs one at random. It is much slower, and tops out at 2,2.


JavaScript (ES6) 152
First time ever that .reduceRight seems useful. (But probably the good old .map can do better). The point is, I need to see the next character before deciding whether to output a short or long octal escape.
f=s=>[...s].reduceRight((a,c)=>
((x=c.charCodeAt())==34|c==(q='\\')?q+c:x>31&x<127?c:q+('abtnvvr'[x-7]||(a>='0'&a<'8'?512+x:x).toString(8).slice(-3)))+a
)


Anti-golfscript anti-golf: create a task where GolfScript or J is outgolfed by your (conventional) lang

My previous question, Print a sinusoidal wave (vertically), qualifies at this moment. I'm posting it here as a solution, also hoping that you guys can come up with some shorter solutions to my original question.

As required by Vi., I will post a summary of the question.

Print a continuous sinusoidal wave scrolling vertically on a terminal. The program should not terminate and should continuously scroll down the wave (except until SIGINT). You may assume overflow is not a problem (i.e. you may use infinite loops with incrementing counters, or infinite recursion).

The wave should satisfy the following properties:

Amplitude = 20 chars (peak amplitude)
Period = 60 to 65 lines (inclusive)
The output should only consist of spaces, newline and |
After each line of output, pause for 50ms

There is a sample output on my original question, but I'm not posting it here, because this will make my answer ridiculously long. My original question can be seen here: Print a sinusoidal wave (vertically)

Shortest A currently: a Perl solution with 48 chars:
https://codegolf.stackexchange.com/a/18655/12205

print$"x(25+20*sin).'|
';$_+=.1;`sleep .05`;do$0

Shortest B currently: a J solution with 54 chars: https://codegolf.stackexchange.com/a/18649/12205

($:+&0.1[6!:3@]&0.05[2:1!:2~' |'#~1,~[:<.20*1+1&o.)0

Currently, the score of this answer is 1.113 (an awfully low score)


Haskell, 222 201 bytes

s""=[]
s x|c?"ειοιυιαιου"=(a++c):s d|h:e:f:g<-b,e==f=(a++[h,e]):s(f:g)|e:f<-b=(a++[e]):s f|2>1=[a]where(a,b)=break(`elem`"αεηιουω")x;(c,d)=splitAt 2 b
i?(x:y:z)=i==[x,y]||i?z
i?""=1>2

Try it online!


05AB1E, 3 bytes

Uses CP-1252 encoding.

.p»

Try it online!

Explanation

     # implicit input
.p   # list of prefixes
  »  # join by newlines


Interpreter for a 99 Bottles of Beer program

JavaScript interpreter for C (3834)

Interpreter (180 * 10 = 1800)

f() is the function to be called.

function prvarf(x){a=arguments;i=0;s+=(t=x.replace(/%./g,function(){return a[++i]}));return t}function f(x){Function(x.replace(/int/g,'var').replace(/#|ma/g,'f//'))(s='');return s}

99-Bottles (1074)

http://99-bottles-of-beer.net/language-c-844.html

FizzBuzz (96 * 10 = 960)

Adapted from one of the programs at http://perl.guru.org/scott/misc/golf.html:

main()
{int b=0;for(;++b<101;)printf(printf("%s%s",b%3?"":"Fizz",b%5?"":"Buzz")?"\n":"%d\n",b);}


APL (15)

∆≡⍕+/(⍎¨∆)*⍴∆←⍞

Outputs 1 if true and 0 if false.

Explanation:

∆←⍞: read a line (as characters), store in ∆
(⍎¨∆)*⍴∆: evaluate each character in ∆ and raise it to the power ⍴∆
∆≡⍕+/: see if the input equals the string representation of the sum of these


Pyth - 66 62 60 bytes
Pretty straightforward approach. Checks if any of substrings len 3 are in any of the rotations of the keyboard. Will be using base encoding for keyboard.
.E}Rjb+J+Kc+jkS9"0
qwertyuiop
asdfghjkl
zxcvbnm"b.tKN_MJ.:z3

Test Suite.


List of possible birth years of living humans

Pyke, 6 bytes
wC7m-

Try it here!
w     - 121
   m- - for i in range(^):
 C7   -  current_year-i

(After w, the codepoint for 153 is present but it isn't printable)


MUMPS - 30 characters,  circa 1966 (ANSI standard first in 1977)

My first attempt at code golf, here we go!

f  w "4 8 15 16 23 42" h 6420

MUMPS is still a popular language for EHR software, created by Massachusetts General Hospital in Boston. Most known implementation is Epic Systems in Verona, WI.


Change the innermost element type of a jagged array — any .NET language: C#, F#, VB.NET, MSIL, C++/CLI, etc

C# - 396 440 595

I'm not entirely sure why I did this, and I can't help but feel I'm missing something. Rewrote the old c (for copy) method as a for-loop in the ChangeElementType method (f). Unless I find something substantial, I think I'll not be making this any shorter.

Golfed code:

using A=System.Array;using T=System.Type;class P{T g(T o){return o.IsArray?g(o.GetElementType()).MakeArrayType(o.GetArrayRank()):typeof(long);}A f(A a){var R=a;int i,r;for(var x=new int[i=r=a.Rank];;){if(i<1){if(a!=R)return R;R=A.CreateInstance(g(a.GetType().GetElementType()),x);i=1;}if(--i<r)if(x[i]-->0)i+=2;else x[i]=a.GetLength(i);else{var o=a.GetValue(x);R.SetValue(o is A?f((A)o):o,x);}}}}

Readable code with an excuse for a test:

using A=System.Array;
using T=System.Type;

class P
{
    // turns a type like "int[,][]" into "long[,][]"
    T g(T o)
    {
        return o.IsArray?g(o.GetElementType()).MakeArrayType(o.GetArrayRank()):typeof(long);
    }

    // ChangeElementType
    A f(A a)
    {
        var R=a; // R is the result, a gives us the type and a nice default value
        int i,r; // i is a counter, r is the rank

        // this loop first counts backwards filling the x array with the dimension lengths
        // then it does a tree traversal and copies things about
        for(var x=new int[i=r=a.Rank];;) // create the x array, and sets i and r
        {
            if(i<1)
            { // gone off start
                if(a!=R) // been here before
                    return R; // return the result
                R=A.CreateInstance(g(a.GetType().GetElementType()),x); // create the array to fill
                i=1; // move to start of x
            }

            if(--i<r) // move back
                if(x[i]-->0) // decrement index
                    i+=2; // move forward instead
                else
                    x[i]=a.GetLength(i); // reset index
            else
            {
                var o=a.GetValue(x); // get the int/array
                R.SetValue(o is A?f((A)o):o,x); // if it's an array, Change it, if not, pass it directly (the int)
            }
        }
    }

    // test method (prints True if the code works, might print False if it doesn't)
    static void Main()
    {
        string old = "";

        var a = new int[10][,];

        for (int i = 0; i < 10; i++)
        {
            a[i] = new int[3,5];

            for (int j = 0; j < 3; j++)
            {
                for (int k = 0; k < 5; k++)
                {
                    int v = i * j * k;
                    a[i][j,k] = v;
                    old += v.ToString();
                }
            }
        }

        long[][,] l = (long[][,])(new P().f(a));

        string nwe = "";

        for (int i = 0; i < 10; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                for (int k = 0; k < 5; k++)
                {
                    nwe += l[i][j,k].ToString();
                }
            }
        }

        System.Console.WriteLine(old == nwe);

        System.Console.ReadKey(true);
    }
}


C# (213 characters)

I'm sure this wont stand long, but at least I got the technique here first!

class P{static void Main(string[] a){foreach(var t in a[0]){var c="";for(int i=" ETIANMSURWDKGOHVF L PJBXCYZQ  54 3   2       16       7   8 90".IndexOf(t);i>0;i/=2)c="-."[i--%2]+c;System.Console.Write(c+"  ");}}}

And in readable format:

class P
{
    static void Main(string[] a)
    {
        foreach(var t in a[0])
        {
            var c="";
            for(int i=" ETIANMSURWDKGOHVF L PJBXCYZQ  54 3   2       16       7   8 90".IndexOf(t);i>0;i/=2)c="-."[i--%2]+c;
            System.Console.Write(c+" ");
        }
    }
}

For a brief explanation, the string of characters is a heap in which the left child is a dot and the right child is a dash.  To build the letter, you traverse back up and reverse the order.


Conway's Game of Life with smallest *set* of source characters


Jelly, 31 29 27 bytes

“×Ɗ¡‘ŒP»Ṫ¦209ṗ€3Fd⁴ịØHs3ṢQY

Try it online!

How it works

“×Ɗ¡‘ yield the code points of the characters between the quotes in Jelly's SBCS, which are 0x11 = 17, 0x91 = 145, and 0x00 = 0.

ŒP constructs the powerset of the array of code points, yielding

[[], [17], [145], [0], [17, 145], [17, 0], [145, 0], [17, 145, 0]]

The last two entries correspond to combinations that contain both 80 and FF, so we have to discard them.

»Ṫ¦209 consists of three parts:

Ṫ (tail) removes the last array of code points, i.e., [17, 145, 0].
»209 takes the maximum of each integer in the remainder of the powerset and 0xD1 = 209, replacing all of them with 209.
¦ (sparse) iterates over the elements of the remainder of the powerset. If the corresponding index is found in [17, 145, 0], the element is replaced with all 209's. If not, it is left untouched.

¦ isn't modular, so this modifies only the last array (index 0) in the remainder of the powerset. The indices 17 and 145 are too large and have no effect.

The result is as follows.

[[], [17], [145], [0], [17, 145], [17, 0], [209, 209]]

ṗ€3 computes the third Cartesian power of each array, i.e., the array of all 3-tuples of elements of each array.

Fd⁴ flattens the result and computes quotient and remainder of each integer divided by 16.

ịØH indexes (1-based) into "0123456789ABCDEF, so 0x11, 0x91, 0x00, and 0xD1 get mapped to "00", "80", "FF", and "C0" (resp.).

s3ṢQ splits the character pairs into 3-tuples, sorts the tuples, and deduplicates.

Finally, Y joins the unique tuples, separating by linefeeds.


MATL, 28 bytes

This uses MATL version 1.0.0, which was published in Esolangs on December 12, earlier than this challenge.

1Hi:"`tb+t16YAt58<)YtZp~]]1$

Example

>> matl 1Hi:"`tb+t16YAt58<)YtZp~]]1$
> 10
121393

Explanation

The code is similar to that in Martin Büttner's answer.

1           % number literal
H           % paste from clipboard H. Initial contents: 2
i:          % vector of equally spaced values from 1 to input value
"           % for
  `         % do...while
    t       % duplicate
    b       % bubble up element in stack
    +       % addition
    t       % duplicate
    16YA    % convert integer to string representation in base 16
    t       % duplicate
    58      % number literal: first ASCII code after '9'
    <       % is less than? (element-wise)
    )       % reference () indexing with logical index from previous comparison
    Yt      % convert string to number
    Zp      % true for prime numbers
    ~       % logical 'not'
  ]         % end
]           % end
1$          % input specification for final implicit display function


Python 2.7 - 122 109 111 109 108 103

f=lambda n,e,m=1:any(all(t*m//m**a%m!=t*m//m**b%m for(a,b)in e)for t in range(m**n))and m or f(n,e,m+1)

Usage:

print f(5, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])

Brute force by increasing the chromatic number (m) and check all possible colorings. One coloring can be described as a number in base m. So the possible colorings are 0, 1, ..., m^n-1.

edit: The complete graph of 8 vertices takes quite long. But my laptop solves it in about 10 minutes. The other test cases take only a few seconds.

edit 2: Read that preprocessing is allowed, so I let the index of the vertices start with 0: shortens t*m//m**x%m to t//m**a%m (-2). Dissolve lambda and put m into function params (-11)

edit 3: preprocessing is not allowed -> back to t*m (+4), simplified // to / (-2).

edit 4: remove square brackets in any (-2), thanks xnor.

edit 5: instead of taking modulo m twice, simply subtract them and afterwards use modulo (-1). This is also quite a performance improvement. All testcases together take about 25 seconds on my laptop.

edit 6: recursive call instead of while 1: and m+=1 (-5). Thanks again, xnor.


How do I ask a teller for money at the bank?

JavaScript (ES6), 485 476 bytes

Alright ... this is a monster. :-(
But it's a rather fast monster that solves all test cases almost instantly.

I may attempt some more advanced golfing later, but I've already spent far too much time on it.

f=(b,a,L=[...a])=>L.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).sort((a,b)=>a[b.length]||-1).find(L=>(Y=G(U(b)-U(L),L.sort((a,b)=>a-b)),Y[0]&&!Y.some(a=>P(b.map(a=>G(a,[]))).every(b=>b+''!=a))),U=a=>~~eval(a.join`+`),P=(e,C=[],R=[])=>e[0].map(v=>R=(c=v.map((x,i)=>x+(C[i]|0)),e[1])?[...P(e.slice(1),c),...R]:[c,...R])&&R,G=(n,l)=>(S=[],g=(n,l)=>n?a.map(x=>x<l[0]|x>n||g(n-x,[x,...l])):S=[l.map(v=>s[a.indexOf(v)]++,s=[...a].fill(0))&&s,...S])(n,l)&&S)||f(b,a,[...a,...L])

Test cases

f=(b,a,L=[...a])=>L.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).sort((a,b)=>a[b.length]||-1).find(L=>(Y=G(U(b)-U(L),L.sort((a,b)=>a-b)),Y[0]&&!Y.some(a=>P(b.map(a=>G(a,[]))).every(b=>b+''!=a))),U=a=>~~eval(a.join`+`),P=(e,C=[],R=[])=>e[0].map(v=>R=(c=v.map((x,i)=>x+(C[i]|0)),e[1])?[...P(e.slice(1),c),...R]:[c,...R])&&R,G=(n,l)=>(S=[],g=(n,l)=>n?a.map(x=>x<l[0]|x>n||g(n-x,[x,...l])):S=[l.map(v=>s[a.indexOf(v)]++,s=[...a].fill(0))&&s,...S])(n,l)&&S)||f(b,a,[...a,...L])

console.log(JSON.stringify(f([22,8], [1,2,5,10,20,50])))
console.log(JSON.stringify(f([2,1,2], [1,5])))
console.log(JSON.stringify(f([20,10], [1,2,5,10,20,50])))
console.log(JSON.stringify(f([1,1,1,1], [1,2])))
console.log(JSON.stringify(f([20,6], [1,4,5])))
console.log(JSON.stringify(f([2,6], [1,2,7])))
console.log(JSON.stringify(f([22,11], [1,3,30,50])))
console.log(JSON.stringify(f([44,22], [1,3,30,50])))

How?

NB: This is not matching the current version anymore, but is much easier to read that way.

// b = list of payments, a = list of bills,
// L = list from which the requested bills are chosen
f = (b, a, L = [...a]) => (
  // U = helper function that computes the sum of an array
  U = a => ~~eval(a.join`+`),

  // P = function that computes the summed Cartesian products of arrays of integers
  // e.g. P([[[1,2],[3,4]], [[10,20],[30,40]]]) --> [[33,44], [13,24], [31,42], [11,22]]
  P = (e, C = [], R = []) => e[0].map(v => R =
    (c = v.map((x, i) => x + (C[i] | 0)), e[1]) ? [...P(e.slice(1), c), ...R] : [c, ...R]
  ) && R,

  // G = function that takes a target amount and a list of requested bills and returns
  // all combinations that contain the requested bills and add up to this amount;
  // each combination is translated into a list of number of bills such as [2,0,0,1,0]
  G = (n, l) => (
    S = [],
    g = (n, l) => n ?
      a.map(x => x < l[0] | x > n || g(n - x, [x, ...l])) :
      S = [l.map(v => s[a.indexOf(v)]++, s = [...a].fill(0)) && s, ...S]
  )(n, l) && S,

  // compute X = list of possible bill combinations to process all payments
  X = P(b.map(a => G(a, []))),

  // compute the powerset of L and sort it from shortest to longest list
  L.reduce((a, x) => [...a, ...a.map(y => [x, ...y])], [[]])
  .sort((a, b) => a[b.length] || -1)

  .find(L => (
    // compute Y = list of possible combinations to reach the total amount,
    // using the requested bills
    Y = G(U(b) - U(L), L.sort((a, b) => a - b)),

    // exit if Y is not empty and all combinations in Y allow to generate all payments
    Y[0] && !Y.some(a => X.every(b => b + '' != a)))
  )

  // if no solution was found, enlarge the set of requested bills and try again
  || f(b, a, [...a, ...L])
)


CJam, 14 bytes

E,_T9t\]ze~es=

Test it here.

Explanation

E,   e# Push [0 1 2 ... 12 13].
_    e# Make a copy.
T9t\ e# Set the first element to 9. Swap with the original range.
]z   e# Wrap them in an array and transpose to get [[9 0] [1 1] [2 2] ... [13 13].
e~   e# Run-length decode to get `[0 0 0 0 0 0 0 0 0 1 2 2 3 3 3 ... 13 13 ... 13 13].
es=  e# Use the current timestamp as a cyclic index into this array.


Mathematica 341 304 298 288 293 bytes
This uses a pure or anonymous function, that is, a function without its own name.
DateString returns an error message if the date is ambiguous. Checkcatches the ambiguity and sends the offending date to DateList, which transforms it into list of 3 integers (which it believes to be {year, month, day}). The month and day integers are sorted by size and used to determine the month and day as per the OP's instructions.
Quiet silences error printing.
t=StringSplit;v=ToString;x=t[#,"-"]&/@t["Janu-ary Febr-uary Mar-ch Apr-il Ma-y Ju-ne Ju-ly Aug-ust Septe-mber Octo-ber Nove-mber Dece-mber"];
Quiet@Check[#~DateString~{"MonthName"," ","DayShort",", ","Year"},
{m,n,o}=DateList@#;{p,q}=Sort@d[[2;;3]];x[[p,1]]<>x[[q,2]]<>" "<>v@Floor@Mean@{n,o}<>", "<>v@d[[1]]]&

t=StringSplit;v=ToString;x=t[#,"-"]&/@t["Janu-ary Febr-uary Mar-ch Apr-il Ma-y Ju-ne Ju-ly Aug-ust Septe-mber Octo-ber Nove-mber Dece-mber"];
Quiet@Check[#~DateString~{"MonthName"," ","DayShort",", ","Year"},
{m,n,o}=DateList@#;{p,q}=Sort@d[[2;;3]];x[[p,1]]<>x[[q,2]]<>" "<>v@Floor@Mean@{n,o}<>", "<>v@d[[1]]]& /@
{"10/31/1998","25/12/1989", "10/8/2011", "8/5/1957", "9/12/2012", "1/1/2012"}

{"October 31, 1998", "December 25, 1989", "Augber 9, 2011", "Maust 6,
1957", "September 10, 2012", "January 1, 2012"}


APL (Dyalog Classic), 54 53 50 bytes

⍴⍴{'OXRYTPZQUWSV'[⌊5÷⍨⍋⍋,{×/+⌿↑|(⊢-+/÷≢)⍸⍵}¨⍵=⊂⍵]}

Try it online!

Compute an invariant for each pentomino in the input: measure (∆x,∆y) from each of its squares to its centre of gravity, take abs(∆x) and abs(∆y), sum the x components and separately the y components, and multiply the two sums. This gives 12 distinct results. Then, find the index of each pentomino's invariant in the sorted collection of all invariants. Replace 0 with 'O', 1 with 'X', 2 with 'R', etc.


A simple recursion will do the work

def build_nested_helper(path, text, container):
    segs = path.split('/')
    head = segs[0]
    tail = segs[1:]
    if not tail:
        container[head] = lambda: msg(text)
    else:
        if head not in container:
            container[head] = {}
        build_nested_helper('/'.join(tail), text, container[head])

def build_nested(paths):
    container = {}
    for path in paths:
        build_nested_helper(path, path, container)
    return container

menu = build_nested(items)

squashed code: 159 chars

def f(p,t,c):
 s=p.split('/');a=s[0];b=s[1:]
 if b:
  if a not in c:c[a]={}
  f('/'.join(b),t,c[a])
 else:c[a]=lambda:msg(t)
menu={}
for i in items:f(i,i,menu)


Rust, score = 104

This is an implementation of the algorithm noted by Grønlund et al. (2017) at the end of §3.3.1, though I had to follow a long citation chain and fill in some missing details.  It runs in O(N log A[N − 1]) time.

Compile with rustc -O. Input format is K on the first line, followed by the entries of A, one entry per line, all on stdin.

(Note: I’m submitting this an hour after the bounty deadline, but I expect the last version I submitted before the bounty deadline, which ran in O(N log N log A[N − 1]) time, to score about 94.)

use std::cmp::min;
use std::io::{self, BufRead};
use std::iter::{once, Cloned};
use std::num::Wrapping;
use std::ops::Range;
use std::slice;
use std::time::Instant;
use std::u64;

type Cost = u64;
const INF: Cost = u64::MAX;

trait ColsTrait<Col>: Clone {
    type Iter: Iterator<Item = Col>;
    fn len(&self) -> usize;
    fn iter(&self) -> Self::Iter;
    fn slice(&self, range: Range<usize>) -> Self;
}

impl<'a, Col: Clone> ColsTrait<Col> for &'a [Col] {
    type Iter = Cloned<slice::Iter<'a, Col>>;
    fn len(&self) -> usize {
        (*self).len()
    }
    fn iter(&self) -> Self::Iter {
        (*self).iter().cloned()
    }
    fn slice(&self, range: Range<usize>) -> Self {
        unsafe { self.get_unchecked(range) }
    }
}

impl ColsTrait<usize> for Range<usize> {
    type Iter = Range<usize>;
    fn len(&self) -> usize {
        self.end - self.start
    }
    fn iter(&self) -> Range<usize> {
        self.clone()
    }
    fn slice(&self, range: Range<usize>) -> Self {
        Range {
            start: self.start + range.start,
            end: self.start + range.end,
        }
    }
}

fn smawk<Col: Copy, Cols: ColsTrait<Col>, Key: Ord, F: Copy + Fn(usize, Col) -> Key>(
    n: usize,
    shift: u32,
    cols: Cols,
    f: F,
) -> Vec<usize> {
    if n == 0 {
        Vec::new()
    } else if cols.len() > n {
        let mut s = Vec::with_capacity(n);
        let mut sk = Vec::with_capacity(n);
        for (jk, j) in cols.iter().enumerate() {
            while match s.last() {
                Some(&l) => f(!(!(s.len() - 1) << shift), j) <= f(!(!(s.len() - 1) << shift), l),
                None => false,
            } {
                s.pop();
                sk.pop();
            }
            if s.len() < n {
                s.push(j);
                sk.push(jk);
            }
        }
        smawk1(
            n,
            shift,
            cols,
            f,
            smawk(n / 2, shift + 1, &s[..], f)
                .into_iter()
                .map(|h| unsafe { *sk.get_unchecked(h) }),
        )
    } else {
        smawk1(
            n,
            shift,
            cols.clone(),
            f,
            smawk(n / 2, shift + 1, cols, f).into_iter(),
        )
    }
}

fn smawk1<
    Col: Copy,
    Cols: ColsTrait<Col>,
    Key: Ord,
    F: Fn(usize, Col) -> Key,
    Iter: Iterator<Item = usize>,
>(
    n: usize,
    shift: u32,
    cols: Cols,
    f: F,
    iter: Iter,
) -> Vec<usize> {
    let mut out = Vec::with_capacity(n);
    let mut range = 0..0;
    for (i, k) in iter.enumerate() {
        range.end = k + 1;
        out.push(
            range
                .clone()
                .zip(cols.slice(range.clone()).iter())
                .min_by_key(|&(_, col)| f(!(!(2 * i) << shift), col))
                .unwrap()
                .0,
        );
        out.push(k);
        range.start = k;
    }
    if n % 2 == 1 {
        range.end = cols.len();
        out.push(
            range
                .clone()
                .zip(cols.slice(range.clone()).iter())
                .min_by_key(|&(_, col)| f(!(!(n - 1) << shift), col))
                .unwrap()
                .0,
        );
    }
    out
}

fn solve(k: usize, a: &[Cost]) -> Cost {
    if k >= a.len() {
        return 0;
    }
    let sa = once(Wrapping(0))
        .chain(a.iter().scan(Wrapping(0), |s, &x| {
            *s += Wrapping(x);
            Some(*s)
        }))
        .collect::<Vec<_>>();
    let c = |i: usize, j: usize| {
        let h = (i - j) / 2;
        unsafe {
            (sa.get_unchecked(i) - sa.get_unchecked(i - h) - sa.get_unchecked(j + h)
                + sa.get_unchecked(j))
                .0
        }
    };
    let cost1 = c(a.len(), 0);
    if k == 1 {
        return cost1;
    }
    let cost2 = (1..a.len()).map(|j| c(j, 0) + c(a.len(), j)).min().unwrap();
    let mut low = 0;
    let mut high = cost1 - cost2;
    let mut ret = INF;
    while low <= high {
        let penalty = low + (high - low) / 2;
        let mut out = vec![(INF, 0); a.len() + 1];
        out[0] = (0, 0);
        let mut begin = 0;
        let mut chunk = 1;
        loop {
            let r = min(a.len() + 1 - begin, 2 * chunk);
            let edge = begin + chunk;
            let (out0, out1) = out.split_at_mut(edge);
            let f = |i: usize, j: usize| {
                let h = (edge + i - j) / 2;
                let &(cost, count) = unsafe { out0.get_unchecked(j) };
                (
                    cost.saturating_add(
                        unsafe {
                            sa.get_unchecked(edge + i) - sa.get_unchecked(edge + i - h)
                                - sa.get_unchecked(j + h)
                                + sa.get_unchecked(j)
                        }.0 + penalty,
                    ),
                    count + 1,
                )
            };
            for ((i, j), o) in smawk(r - chunk, 0, begin..edge, &f)
                .into_iter()
                .enumerate()
                .zip(out1.iter_mut())
            {
                *o = min(f(i, begin + j), *o);
            }
            let x = unsafe { out1.get_unchecked(r - 1 - chunk) };
            if let Some(j) = (edge..begin + r - 1).find(|&j| &f(r - 1 - chunk, j) <= x) {
                begin = j;
                chunk = 1;
            } else if r == a.len() + 1 - begin {
                break;
            } else {
                chunk *= 2;
            }
        }
        let &(cost, count) = unsafe { out.get_unchecked(a.len()) };
        if count > k {
            low = penalty + 1;
        } else {
            ret = cost.wrapping_sub(k as Cost * penalty);
            if count == k {
                return ret;
            }
            high = penalty - 1;
        }
    }
    ret
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let k = lines.next().unwrap().unwrap().parse().unwrap();
    let a = lines
        .map(|s| s.unwrap().parse().unwrap())
        .collect::<Vec<_>>();
    let start = Instant::now();
    let cost = solve(k, &a);
    let time = start.elapsed();
    println!(
        "cost: {}\ntime: {}.{:09} sec",
        cost,
        time.as_secs(),
        time.subsec_nanos()
    );
}

Try it online!

Rust, pretest score = 73

Compile with rustc -O.  Input format is K on the first line, followed by the entries of A, one entry per line, all on stdin.

use std::io::{self, BufRead};
use std::iter::once;
use std::num::Wrapping;
use std::time::Instant;
use std::u64;

type Cost = u64;
const INF: Cost = u64::MAX;

fn smawk<Col: Clone, Key: Ord, F: Clone + Fn(usize, &Col) -> Key>(
    n: usize,
    shift: u32,
    cols: &[Col],
    f: F,
) -> Vec<usize> {
    if n == 0 {
        Vec::new()
    } else if cols.len() > n {
        let mut s = Vec::with_capacity(n);
        let mut sk = Vec::with_capacity(n);
        for (jk, j) in cols.iter().enumerate() {
            while match s.last() {
                Some(l) => f(!(!(s.len() - 1) << shift), j) <= f(!(!(s.len() - 1) << shift), l),
                None => false,
            } {
                s.pop();
                sk.pop();
            }
            if s.len() < n {
                s.push(j.clone());
                sk.push(jk);
            }
        }
        smawk1(
            n,
            shift,
            cols,
            f.clone(),
            smawk(n / 2, shift + 1, &s, f)
                .into_iter()
                .map(|h| unsafe { *sk.get_unchecked(h) }),
        )
    } else {
        smawk1(
            n,
            shift,
            cols,
            f.clone(),
            smawk(n / 2, shift + 1, &cols, f).into_iter(),
        )
    }
}

fn smawk1<Col: Clone, Key: Ord, F: Clone + Fn(usize, &Col) -> Key, Iter: Iterator<Item = usize>>(
    n: usize,
    shift: u32,
    cols: &[Col],
    f: F,
    iter: Iter,
) -> Vec<usize> {
    let mut out = Vec::with_capacity(n);
    let mut range = 0..0;
    for (i, k) in iter.enumerate() {
        range.end = k + 1;
        out.push(
            range
                .clone()
                .zip(unsafe { cols.get_unchecked(range.clone()) })
                .min_by_key(|&(_, col)| f(!(!(2 * i) << shift), col))
                .unwrap()
                .0,
        );
        out.push(k);
        range.start = k;
    }
    if n % 2 == 1 {
        range.end = cols.len();
        out.push(
            range
                .clone()
                .zip(unsafe { cols.get_unchecked(range.clone()) })
                .min_by_key(|&(_, col)| f(!(!(n - 1) << shift), col))
                .unwrap()
                .0,
        );
    }
    out
}

fn solve(k: usize, a: &[Cost]) -> Cost {
    let mut cost = vec![INF; a.len() + 1 - k];
    let sa = once(Wrapping(0))
        .chain(a.iter().scan(Wrapping(0), |s, &x| {
            *s += Wrapping(x);
            Some(*s)
        }))
        .collect::<Vec<_>>();
    cost[0] = 0;
    let cols = (0..a.len() + 1 - k).collect::<Vec<_>>();
    for m in 0..k {
        cost = {
            let f = |i: usize, &j: &usize| {
                if i + 1 >= j {
                    let h = (i + 1 - j) / 2;
                    unsafe {
                        cost.get_unchecked(j).saturating_add(
                            (sa.get_unchecked(i + m + 1) - sa.get_unchecked(i + m + 1 - h)
                                - sa.get_unchecked(j + m + h)
                                + sa.get_unchecked(j + m))
                                .0,
                        )
                    }
                } else {
                    INF
                }
            };
            smawk(a.len() + 1 - k, 0, &cols, &f)
                .into_iter()
                .enumerate()
                .map(|(i, j)| f(i, &j))
                .collect()
        };
    }
    cost[a.len() - k]
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let k = lines.next().unwrap().unwrap().parse().unwrap();
    let a = lines
        .map(|s| s.unwrap().parse().unwrap())
        .collect::<Vec<_>>();
    let start = Instant::now();
    let cost = solve(k, &a);
    let time = start.elapsed();
    println!(
        "cost: {}\ntime: {}.{:09} sec",
        cost,
        time.as_secs(),
        time.subsec_nanos()
    );
}

Try it online!


BBC BASIC, 273 ASCII characters (not golfed yet)

Emulator at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

Parsing the direction is a dirty hack. I simply take a walk through a cartesian grid for each letter input. They aren´t echoed to the screen, and the input is terminated when a space is received.

As this is codegolf, I don't bother to normalise the direction vector. Therefore the size of the symbol drawn is dependent on the number of characters input. The proportions are the same for all inputs, however. Also, for the 3-letter inputs the angle is 4 degrees closer to the diagonal than it should be. For example, NNE is atan(0.5)=26.57 degrees instead of the correct 22.5 degrees, but it is barely noticeable. Both these points could be corrected for about 20-30 characters.

After the direction, the speed is input (this is echoed to the screen and terminated with a newline.)

  x=0
  y=0
  REPEAT
    d=GET                             :REM get character from keyboard
    x+=(d=87)-(d=69)                  :REM d=87 evaluates to -1 if "W", d=69 is -1 if "E"
    y+=(d=83)-(d=78)                  :REM d=83 evaluates to -1 if "S", d=69 is -1 if "N"
  UNTILd=32
  x*=20                               :REM boost the sizes of x and y
  y*=20                               :REM normalization code would go here
  INPUTs
  s=INT(s/5+.5)                       :REM divide s by 5 and round to nearest int. 50-tick=10, 10-tick=2, 5-tick=1
  MOVE600,500                         :REM move to centre of circle
  PLOT145,x,y                         :REM draw circle centred at 600,500 with 600+x,500+y on its edge. cursor remains at the latter position.
  IFs=0END                            :REM exit if wind=0
  DRAWBY 9*x,9*y                      :REM draw the shaft of the arrow, 9 units long, from current position
  IFs>1 MOVEBY x,y                    :REM if rounded windspeed >5 move one more space out.
  WHILEs>1                            :REM while there are still 50-ticks and 10-ticks to draw
    MOVEBY 2*y,-2*x                   :REM move 2 units clockwise of the shaft
    PLOT1-(s>9)*80,-2*y-x,2*x-y       :REM draw a diagonal line back to the shaft. If s is 10 or over, plot mode 81 will take the last 2 positions of the graphics cursor and draw a triangle.
    s-=2-(s>9)*8                      :REM Decrement s by 2 or 10, according to the last barb drawn.
  ENDWHILE
  IFs MOVEBY -x,-y:DRAWBY x/2+y,y/2-x :REM If s=1 draw the 5-tick. Unlike the other ticks, it is drawn from its root outwards.

Output

All the test cases from the quesion are shown, plus two more to illustrate 2-letter directions:

50 knots, NNE
0 knots
12 knots S
112 knots WNW
195 knots SE
5 knots SW

In order to show them all together, I didn't clear the screen between runs. The different sizes (but constant proportions) of the arrows can be seen.


Minimal maximum byte for Turing Completeness

Haskell, score 61 (=)
Characters used: !#$%&()=
The SKI combinator calculus can be implemented in Haskell with nothing but basic function definition, using !#%& as identifiers. Infix function application $ is used to save on parentheses and strip down one character from both S and fix. Finally, K only takes two arguments and can be more shortly defined as an infix operator.
S combinator: s x y z = x z (y z)
(!)(#)(%)(&)=(#)(&)$(%)(&)

K combinator: k x y = x
(!)#($)=(!)

fix combinator: fix f = f (fix f)
(&)(!)=(!)$(&)(!)

Since Haskell is a strongly typed language, the fixed-point combinator fix is needed in order to make (typed) combinatory logic Turing-complete.
The I combinator is not strictly required since it is extensionally equivalent to SKK, but it can be defined as (*)(!)=(!).
Try it online!


Wolfram Language (Mathematica), 44 bytes

ContinuedFraction[2FromContinuedFraction@#]&

Try it online!

Mathematica has a builtin! Yay! Mathematica's builtin is super long. Aww.

Mathematica's continued fractions look like {integer, ...prefix, {...repeating}}

-1 thanks to JungHwan Min


JavaScript (ES6), 123 110 100 97 bytes

Saved 3 bytes thanks to @Neil

s=>s.replace(/\(?(.*?)\)?\s*=>\s*([^]*)/,(_,a,b)=>`function(${a})${b[0]=='{'?b:`{return ${b}}`}`)

Assumes the input is a syntactically valid arrow function and nothing else. Correctly handles the case a =>\na, though not handling is not any shorter as far as I can tell.

Output when the code is run through itself:

function(s){return s.replace(/\(?(.*?)\)?\s*=>\s*([^]*)/,(_,a,b)=>`function(${a})${b[0]=='{'?b:`{return ${b}}`}`)}

I can save 9 bytes with a possibly invalid format:

s=>s.replace(/\(?(.*?)\)?\s*=>\s*({?)([^]*?)}?$/,(_,a,z,b)=>Function(a,z?b:'return '+b))

Output for itself:

function anonymous(s) {
return s.replace(/\(?([^=)]*)\)?\s*=>\s*({?)([^]*?)}?$/,(_,a,z,b)=>Function(a,z?b:'return '+b))
}

(Specifically, the function anonymous is what I'm worried about.)


JavaScript (ES7), 55 bytes

f=(a,b,c=2)=>b>1?b%c?f(a,b,c+1):a+['^'+b,f(a**c,b/c)]:a

Uses , in place of = (2^15,8^5,32768).

Test cases

f=(a,b,c=2)=>b>1?b%c?f(a,b,c+1):a+['^'+b,f(Math.pow(a,c),b/c)]:a
g=(a,b)=>console.log(`f(${a}, ${b}):`,f(a,b))

g(4,8)
g(5,11)
g(2,15)

Note: the snippet uses Math.pow instead of ** for cross-browser compatibility.


Perl → Befunge, 868 bytes

OK, I'll get the ball rolling. This could be golfed down a bit more, but my head is starting to hurt...

$_=" f,j f,jjj f,lgdlH,b >llb ,l,b lb ,lb , f,j f j f >>l>,lb ,9vb >lb,Hlb,H>vb >999*+,
mg8Hg8Ha8c8g8Hgb8Hab8,8k/ 8Ha8Hi /H8HgH8g8k >H9ghgH9b 'bhbhgH9ghg9+gH9ga//
ma8Hg8Ha8c8ahgbhabhh /bhah VdhibHH9ghb >H9ghgH9abhbhgH*g9+g ii /b>l,^b //
>H^>>Hned*angne ned* eneknabnn<b nangn idH*gned*gneb*>>,b *kngH5g*6 Adb><aha//b
H*g2HgH3a4Hg5Ha6c7gHHgb1Hab2+3H ib4Ha5Hg6kiHH7g8c, id1H iabHk3k4+g >+ ,^>^dd 7/ ib *k //b
+1g+HgH+g+Hg+Ha+c+g,Hgb+kk >^+ki +Ha+Hg+HgH+g+cki'+ki ,gk+k>^gbHc^H 9*gb8+b//a
^<b ^>^ebe^'>^e >^e>>^a >^>> >^gd>^ke> >^b '>^e>>^g>^g e^ >^a >^~'i>^b i >2+^b >^b e>gHaV V >^gb>^bHHHHHH";
s/n/*H/g;s/m/H8g8HgH8/g;s/l/v>/g;s/k/Hb/g;s/j/f>,/g;s/i/\\/g;s/h/9H/g;s/g/bd/g;s/f/ve/g;s/e/>>>/g;s/d/ H/g;s/c/HaH/g;s/b/  /g;s/a/    /g;@f=split$/;
@s=split('',$ARGV[0]);foreach$r(0..6){for($i=0;$i<@s;$i++){print substr($f[$r],(ord($s[$i])-65)*6,6).$"}print$r?'':' @',$/}

Examples:

The shorter examples can be copy-pasted into online interpreters like this one, but UNCOPYRIGHTABLE appears to result in a program that is too long for all the online interpreters to handle.

$ perl bf.pl ABCDEFGHI
 v>>>, v>>>>,  v>>>, v>>>>, v>>>>, v>>>>,  v>>>, v>   H  Hv>H,  @
H8   H 8H   H H8   H 8H   H 8H     8H     H8   H 8H   H   8H
H8   H 8H   H H8     8H   H 8H     8H     H8     9H   H   9H
>H^>>H *H>>>  H*     *H   H *H>>>  *H>>>  H* >>> *H>>>H   *H
H*   H 2H   H H3     4H   H 5H     6H     H7   H HH   H   1H
+1   H +H   H H+   H +H   H +H     +H     H+   H ,H   H   +H
^<   ^ >^>>>   >>>^' >^>>>  >^>>>> >^      >^>>  >^   H  H>^H

$ perl bf.pl JKLMNOPQR
   >v> v>   , v>,    v>   , v>   ,  v>>>, v>>>>,  v>>>  v>>>>,  @
    8, 8H  /  8H     8H\ /H 8H   H H8   H 8H   > H9   H 9H   H
    9H 9H /   9H     9H V H 9H\  H H9   H 9H   > H9   H 9H   H
    *H *H<    *H     *H   H *H \ H H*   H *H>>>  H*   H *H>>>
    2+ 3H \   4H     5H   H 6H  \H H7   H 8H     H, \ H 1H \
H   >^ +H  \  +H     +H   H +H   H H+   H +H     HH  \' +H  \
 >>>>  >^   ' >^>>>> >^   H >^   H  >>>^  >^      >^~'\ >^   \

$ perl bf.pl STUVWXYZ
 v>>>  >>v>>, v>   , 9v   > v>  ,H v>  ,H >v   > 999*+,  @
H9   '   9H   9H   H H9   H 9H   H 9+   H H9   H     //
H9       9H   9H   H H*   H 9+   H  \\ /   >v>,^    //
 *>>,    *H   *H   H H5   H *6 A H   ><     9H     //
    HH   3H   4+   H  >+ ,^ >^ H H  7/ \    *H    //
,   HH   +H   >^   H   HH     H^H  9*   H   8+   //
 >2+^    >^    >>>>    HH     V V  >^   H   >^   HHHHHH

$ perl bf.pl UNCOPYRIGHTABLE
v>   , v>   ,  v>>>,  v>>>, v>>>>, >v   > v>>>>,  Hv>H,  v>>>, v>   H >>v>>,  v>>>, v>>>>, v>,    v>>>>,  @
9H   H 8H   H H8   H H8   H 8H   > H9   H 9H   H   8H   H8   H 8H   H   9H   H8   H 8H   H 8H     8H
9H   H 9H\  H H8     H9   H 9H   >  >v>,^ 9H   H   9H   H8     9H   H   9H   H8   H 8H   H 9H     8H
*H   H *H \ H H*     H*   H *H>>>    9H   *H>>>    *H   H* >>> *H>>>H   *H   >H^>>H *H>>>  *H     *H>>>
4+   H 6H  \H H3     H7   H 8H       *H   1H \     1H   H7   H HH   H   3H   H*   H 2H   H 4H     5H
>^   H +H   H H+   H H+   H +H       8+   +H  \    +H   H+   H ,H   H   +H   +1   H +H   H +H     +H
 >>>>  >^   H  >>>^'  >>>^  >^       >^   >^   \  H>^H   >^>>  >^   H   >^   ^<   ^ >^>>>  >^>>>> >^>>>>

Note:

The @ character at the end of the first line of output tells Befunge to stop running. Without it, the program would keep repeating the same word forever.


Random number generation, without built-in random number generation libraries

C (46)

The stack pointer is sort of a random number

main(x){printf("%d",((unsigned char)&x)%100);}

Numbers I got:

20
40
4
52
36


Mathematica: 103 chars

Spaces can be removed

Select[Flatten@
       Table[
        Solve[Log@#/Log@b == k, k, Integers] /. k -> #, {b, 2, #}] & /@ Range@#,
Length@# > 2 &][[All, 1, 1]] &

Usage:

%[81]
{16, 64, 81}


Swaps needed to sort an array in bubble sort method

Python - 262 chars * 45 / 60 = 196.5

Edit: much faster sorting algorithm.

First it will sort all the items in the list by what hundred they are in (0, 100, 200, etc), in a list in m (note: I count these as 1 step each, so a list of 1,000,000 items will automatically have 1,000,000 steps initially)

Then it will sort the lists within m using the bubble sorting function c

This is greatly sped up from using c on the original list to be sorted, because the amount of time it takes to sort 1000 items is small (~0.04 seconds), but exponentially increases the larger the list gets (~45 seconds at 10,000 items). But if you sort 100 lists of 100 items, it only takes .4 seconds, to sort, more than 100 times faster than sorting 1 list of 10,000 items. It should therefor take 4 seconds to sort 100,000 items, and 40 seconds to finally sort 1,000,000

In actuality, it took 45 seconds to sort the reversed 1,000,000 item list this way, and results in 50,500,000 steps:

python bubblesortcount.py
50500000
44.6600000858

This functon works with the given case (reverse ordered list), as well as any random case. No negative integers, though.

r=range
def b(l):
 m=[[]for i in r(len(l)//100+1)];t=[];o=0
 for e in l:m[e//100].append(e);o+=1
 for e in m:x=c(e);t+=x[0];o+=x[1]
 return t,o
def c(l):
 s=0
 for p in r(len(l)-1,0,-1):
  for i in r(p):
   if l[i]>l[i+1]:l[i],l[i+1]=l[i+1],l[i];s+=1
 return l,s

test:

import random,time
a=time.time()
d=b(range(1000000)[::-1]) #reversed list
#d=b(random.sample(range(1000000),1000000)) #scrambled list
z=(time.time()-a)
#print d[0] # comment to not print a gigantic list
print d[1] # number of steps
print z # time it took

Edit: by changing the amount the helper function sorts by to 100, I reduced the average time it takes to sort the list to 45 seconds. also reduces character count by 2

edit again: you know what? maybe what I'm doing isn't valid. I can change the amount the helper function sorts by to just 1 and it will sort a million items in 5 seconds.. is this valid?


J, 15 bytes

p:@i.+/ .*i.!<:

Explanation:

Basically the same as my Mathematica answer.

p:@i.+/ .*i.!<:
          i.!<:    binomial coefficients
p:@i.              first n primes
     +/ .*         dot product


Smallest C code to Crash an Operating System?

29 chars

Linux

int main(){system("init 6");}

I know, very lame. But hey, it reboots the system. Wasn't that the task?

Windows 38 chars

int main(){system("shutdown.exe /r");}

Works as normal user.


Pyth, 12 bytes

.e**Qsb^Tk_w

Test suite

Takes input newline separated, e.g.

361
674

Explanation:

.e**Qsb^Tk_w
                Implicit: Q = eval(input()),T = 10
           w    Input the second number as a string.
          _     Reverse it.
.e              Enumerated map, where b is the character and k is the index.
     sb         Convert the character to an int.
   *Q           Multiply by Q.
  *    ^Tk      Multiply by T ^ k. (10 ^ index)


Retina, 54 53 bytes

T`au`ie`y.
wa
we
T`\oeuia`ao
T`ko`stn\hmyr\w`.a
^a
ka

Try it online.

Explanation

Wooo, showing off even more features from today's 0.7.2 release. :) (The release predates this challenge by about 7 hours.)

T`au`ie`y.

This is a transliteration which replaces a with i and u with e, but only in matches of y.. The purpose of that is to treat ya and yu like yi and ye, respectively, in order to skip the gaps.

wa
we

Replace wa with we to skip that gap as well.

T`\oeuia`ao

Here is the new feature. When rotating sets of characters, the "from" and "to" set in a transliteration are usually almost identical. So now we've got o (without a backslash) to refer to the other set, which allows us to get rid of some duplication. The \o just stands for a literal o in that case. So the two sets expand to:

oeuia
aoeuia

The extraneous a in the second set is ignored and the vowels are replaced cyclically as expected.

T`ko`stn\hmyr\w`.a

This does the same thing for the consonants, but using o in the first set (just because we can...). h and w need escaping because they are character classes. The expanded sets are:

kstnhmyrw
stnhmyrw

The .a restricts this operation to syllables that end in a, i.e. those that wrap to the next line of the table.

^a
ka

Finally, we replace a single a with ka, because that case cannot be handled by the previous transliteration.


Make StackOverflow Explode (bookmarklet)

Here's my entry, which I'll call the drunkenator:

javascript:void(setInterval(function(){c='1234567890poiuytrewqasdfghjklmnbvcxzZXCVBNMLKJHGFDSAQWERTYUIOP=)(/&%25$%23"!1';$(':not(iframe,script,style)').contents().each(function(){if(this.nodeType==3&&/\S/.test(this.nodeValue)){a=this.nodeValue.split('');x=0;for(i=0;i<a.length;i++){r=Math.random()*9999;if(r<10){x=1;j=c.indexOf(a[i]);a[i]=(r<4%3F(t=a[i-1],a[i-1]=a[i],t):r<5%3F'':r<6%3Fa[i]+a[i]:j<0%3Fa[i]:c.charAt(j+(r<8%3F1:-1)))}}if(x)this.nodeValue=a.join('')}})},100))

At 474 chars, it's probably not going to win any golf prizes, but I'm hoping to make up for it in upvotes. :)

Here's the same code de-obfuscated:

setInterval(function () {
  var c = '1234567890poiuytrewqasdfghjklmnbvcxzZXCVBNMLKJHGFDSAQWERTYUIOP=)(/&%$#"!1';
  $(':not(iframe,script,style)').contents().each(function () {
    if (this.nodeType==3 && /\S/.test(this.nodeValue)) {
      var a = this.nodeValue.split('');
      var x = 0;
      for (i = 0; i < a.length; i++) {
        r = Math.random() * 9999;
        if (r < 10) {
          x = 1;
          j = c.indexOf(a[i]);
          a[i] = ( r < 4 ? (t = a[i-1], a[i-1] = a[i], t)
                 : r < 5 ? ''
                 : r < 6 ? a[i] + a[i]
                 : j < 0 ? a[i] : c.charAt(j + (r < 8 ? 1 : -1)) );
        }
      }
      if (x) this.nodeValue = a.join('');
    }
  });
}, 100);

What it does is randomly mutate the text on the page, swapping adjacent characters, deleting or duplicating characters or replacing them with ones adjacent to them on the keyboard.  The effect is kind of subtle at first, but leave it running for a while, and the page content will inevitably decay into a mess of drunken typing:

Ps. The code isn't in any way SO-specific, so it'll work on any website that uses jQuery.  Try it on Wikipedia for hilarious results.  The idea is based on something I wrote years ago as a creative interpretation of the "99 bottles of beer" challenge: my version introduced a slowly increasing number of typos into each verse, until the last ones were all but unrecognizable.  If anyone wants to see it, here's the original Perl code.


Find elements in an array computing a given function value

Python3, O(n^3 log n)
from math import gcd
from functools import reduce

def lcm(x,y):
    return x//gcd(x,y)*y

def label(l):
    res=[(v,i) for i,v in enumerate(l)]
    res.sort()
    return res

def sortcombine(l):
    l.sort()
    res=[]
    oldval=None
    for val,how in l:
        if val==oldval:
            res[-1][1].append(how)
        else:
            oldval=val
            res.append((val,[how]))
    return res

def getabc(L,xl):
    N=len(xl)
    res=[]
    lasta=None
    for ai in range(N):
        a,al=xl[ai]
        if a==lasta:
            continue
        lasta=a
        lastb=None
        for bi in range(ai+1,N):
            b,bl=xl[bi]
            if b==lastb:
                continue
            lastb=b
            lastc=None
            for c,cl in xl:
                if c in [0,lastc] or cl in [al,bl]:
                    continue
                lastc=c
                res.append((L//c*a*b,(al,bl,cl)))
    return sortcombine(res)

def getde(L,xl):
    res=[]
    xl.reverse()
    lastd=None
    for d,dl in xl:
        if lastd==d:
            continue
        lastd=d
        laste=None
        for e,el in xl:
            if e in [0,laste] or el==dl:
                continue
            laste=e
            res.append((L//e*d,(dl,el)))
    return sortcombine(res)

def solve(l,k):
    xl=label(l)
    L=reduce(lcm,[v for v in l if v!=0],1)
    k*=L
    abc=getabc(L,xl)
    de=getde(L,xl)
    i=0
    j=len(de)-1
    while i<len(abc) and j>=0:
        v1,ls1=abc[i]
        v2,ls2=de[j]
        s=v1+v2
        if s==k:
            for l1 in ls1:
                s=set(l1)
                for l2 in ls2:
                    if s.isdisjoint(l2):
                        return list(l1+l2)
            i+=1
            j-=1
        elif s<k:
            i+=1
        else:
            j-=1
    return None

Try it online!
Multiply the equation by the LCM of the x values to avoid floating point or fractions.
Find all possible values of ab/c (using ab=ba but that's only for a factor of 1/2) and d/e, sort them and try to add them to the wanted result. The sorting means we don't have to try all combinations.
There are O(n^3) possible values for ab/c, sorting them gives the log. The other steps are faster than that.
The while loop may be repeated O(n^3) times, but the case s==k can only occur O(n^2) times. If we don't find a solution and stop in this case, then the sizes of ls1 and ls2 (number of ways to obtain the corresponding value) must be in O(n) resp. O(1) (except in the case when the value is 0, but luckily that doesn't happen O(n) times).


MATL, 15 13 bytes

t3$)&Gw&St3$)

Inputs u,  then A.

Outputs B, then C without a separator, as there is no ambiguity.

Try it online!

Explanation

t     % Take input u implicitly. Duplicate u
3$)   % Take input A implicitly. Index A with u as row and column indices
&G    % Push the two inputs again: u, A
w     % Swap
&S    % Push indices that would make u sorted. Call that v
t     % Duplicate v
3$)   % Index A with v as row as column indices. Display implcitly


Haskell, ~2^(2^18)
f x=(x,x)
g=f.f.f.f
h=g.g.g.g
i=h.h.h.h
j=i.i.i.i
k=j.j.j.j
l=k.k.k.k
m=l.l.l.l
n=m.m.m.m
n.n.n.n$0

Each application of f roughly double the type signature by transforming the type signature T to (T,T). For example, the fourfold composition f.f.f.f$0 has type
Num a => ((((a, a), (a, a)), ((a, a), (a, a))), (((a, a), (a, a)), ((a, a), (a, a))))

Each line quadraples the number of applications of f, giving 4^9 = 2^18 at the end. So, the type signature has size of the order of 2^(2^18).