title: Sunset in every capital

text:
# Question
Title: Sunset in every capital
This is a very simple challenge.

# Task

Whenever your code is run, your code should output the next sunset date and time in GMT for all capital cities on Earth. You should get the list of capitals from the below table. The dates and times should be outputted sorted by the name of the capital. You don’t need to output the capital name.

Here is a copy of the list of capitals. Where there is more than one option your code may choose any one of them.

$$\begin{array}{l|l} \text{COUNTRY} & \text{CAPITAL CITY} \\ \hline \text{United Arab Emirates} & \text{Abu Dhabi} \\ \hline \text{Nigeria} & \text{Abuja} \\ \hline \text{Ghana} & \text{Accra} \\ \hline \text{Ethiopia} & \text{Addis Ababa} \\ \hline \text{Algeria} & \text{Algiers} \\ \hline \text{Jordan} & \text{Amman} \\ \hline \text{Netherlands} & \text{Amsterdam} \\ \hline \text{Andorra} & \text{Andorra la Vella} \\ \hline \text{Turkey} & \text{Ankara} \\ \hline \text{Madagascar} & \text{Antananarivo} \\ \hline \text{Samoa} & \text{Apia} \\ \hline \text{Turkmenistan} & \text{Ashgabat} \\ \hline \text{Eritrea} & \text{Asmara} \\ \hline \text{Paraguay} & \text{Asuncion} \\ \hline \text{Greece} & \text{Athens} \\ \hline \text{Iraq} & \text{Baghdad} \\ \hline \text{Azerbaijan} & \text{Baku} \\ \hline \text{Mali} & \text{Bamako} \\ \hline \text{Brunei} & \text{Bandar Seri Begawan} \\ \hline \text{Thailand} & \text{Bangkok} \\ \hline \text{Central African Republic} & \text{Bangui} \\ \hline \text{Gambia} & \text{Banjul} \\ \hline \text{Saint Kitts and Nevis} & \text{Basseterre} \\ \hline \text{China} & \text{Beijing} \\ \hline \text{Lebanon} & \text{Beirut} \\ \hline \text{Northern Ireland} & \text{Belfast} \\ \hline \text{Serbia} & \text{Belgrade} \\ \hline \text{Belize} & \text{Belmopan} \\ \hline \text{Germany} & \text{Berlin} \\ \hline \text{Switzerland} & \text{Bern} \\ \hline \text{Kyrgyzstan} & \text{Bishkek} \\ \hline \text{Guinea-Bissau} & \text{Bissau} \\ \hline \text{Colombia} & \text{Bogota} \\ \hline \text{Brazil} & \text{Brasilia} \\ \hline \text{Slovakia} & \text{Bratislava} \\ \hline \text{Congo, Republic of the} & \text{Brazzaville} \\ \hline \text{Barbados} & \text{Bridgetown} \\ \hline \text{Belgium} & \text{Brussels} \\ \hline \text{Romania} & \text{Bucharest} \\ \hline \text{Hungary} & \text{Budapest} \\ \hline \text{Argentina} & \text{Buenos Aires} \\ \hline \text{Egypt} & \text{Cairo} \\ \hline \text{Australia} & \text{Canberra} \\ \hline \text{Venezuela} & \text{Caracas} \\ \hline \text{Wales} & \text{Cardiff} \\ \hline \text{Saint Lucia} & \text{Castries} \\ \hline \text{Moldova} & \text{Chisinau} \\ \hline \text{Sri Lanka} & \text{Colombo} \\ \hline \text{Guinea} & \text{Conakry} \\ \hline \text{Denmark} & \text{Copenhagen} \\ \hline \text{Senegal} & \text{Dakar} \\ \hline \text{Syria} & \text{Damascus} \\ \hline \text{Bangladesh} & \text{Dhaka} \\ \hline \text{East Timor} & \text{Dili} \\ \hline \text{Djibouti} & \text{Djibouti} \\ \hline \text{Tanzania} & \text{Dodoma} \\ \hline \text{Qatar} & \text{Doha} \\ \hline \text{Ireland} & \text{Dublin} \\ \hline \text{Tajikistan} & \text{Dushanbe} \\ \hline \text{Scotland} & \text{Edinburgh} \\ \hline \text{Sierra Leone} & \text{Freetown} \\ \hline \text{Tuvalu} & \text{Funafuti} \\ \hline \text{Botswana} & \text{Gaborone} \\ \hline \text{Guyana} & \text{Georgetown} \\ \hline \text{Burundi} & \text{Gitega} \\ \hline \text{Guatemala} & \text{Guatemala City} \\ \hline \text{Vietnam} & \text{Hanoi} \\ \hline \text{Zimbabwe} & \text{Harare} \\ \hline \text{Cuba} & \text{Havana} \\ \hline \text{Finland} & \text{Helsinki} \\ \hline \text{Solomon Islands} & \text{Honiara} \\ \hline \text{Pakistan} & \text{Islamabad} \\ \hline \text{Indonesia} & \text{Jakarta} \\ \hline \text{South Sudan} & \text{Juba} \\ \hline \text{Afghanistan} & \text{Kabul} \\ \hline \text{Uganda} & \text{Kampala} \\ \hline \text{Nepal} & \text{Kathmandu} \\ \hline \text{Sudan} & \text{Khartoum} \\ \hline \text{Ukraine} & \text{Kiev} \\ \hline \text{Rwanda} & \text{Kigali} \\ \hline \text{Jamaica} & \text{Kingston} \\ \hline \text{Saint Vincent and the Grenadines} & \text{Kingstown} \\ \hline \text{Congo, Democratic Republic of the} & \text{Kinshasa} \\ \hline \text{Malaysia} & \text{Kuala Lumpur} \\ \hline \text{Kuwait} & \text{Kuwait City} \\ \hline \text{Bolivia} & \text{La Paz (administrative), Sucre (official)} \\ \hline \text{Gabon} & \text{Libreville} \\ \hline \text{Malawi} & \text{Lilongwe} \\ \hline \text{Peru} & \text{Lima} \\ \hline \text{Portugal} & \text{Lisbon} \\ \hline \text{Slovenia} & \text{Ljubljana} \\ \hline \text{Togo} & \text{Lome} \\ \hline \text{England} & \text{London} \\ \hline \text{United Kingdom} & \text{London} \\ \hline \text{Angola} & \text{Luanda} \\ \hline \text{Zambia} & \text{Lusaka} \\ \hline \text{Luxembourg} & \text{Luxembourg} \\ \hline \text{Spain} & \text{Madrid} \\ \hline \text{Marshall Islands} & \text{Majuro} \\ \hline \text{Equatorial Guinea} & \text{Malabo} \\ \hline \text{Maldives} & \text{Male} \\ \hline \text{Nicaragua} & \text{Managua} \\ \hline \text{Bahrain} & \text{Manama} \\ \hline \text{Philippines} & \text{Manila} \\ \hline \text{Mozambique} & \text{Maputo} \\ \hline \text{Lesotho} & \text{Maseru} \\ \hline \text{Eswatini (Swaziland)} & \text{Mbabana} \\ \hline \text{Palau} & \text{Melekeok} \\ \hline \text{Mexico} & \text{Mexico City} \\ \hline \text{Belarus} & \text{Minsk} \\ \hline \text{Somalia} & \text{Mogadishu} \\ \hline \text{Monaco} & \text{Monaco} \\ \hline \text{Liberia} & \text{Monrovia} \\ \hline \text{Uruguay} & \text{Montevideo} \\ \hline \text{Comoros} & \text{Moroni} \\ \hline \text{Russia} & \text{Moscow} \\ \hline \text{Oman} & \text{Muscat} \\ \hline \text{Chad} & \text{N'Djamena} \\ \hline \text{Kenya} & \text{Nairobi} \\ \hline \text{Bahamas} & \text{Nassau} \\ \hline \text{Myanmar (Burma)} & \text{Nay Pyi Taw} \\ \hline \text{India} & \text{New Delhi} \\ \hline \text{Niger} & \text{Niamey} \\ \hline \text{Cyprus} & \text{Nicosia} \\ \hline \text{Nauru} & \text{No official capital} \\ \hline \text{Mauritania} & \text{Nouakchott} \\ \hline \text{Tonga} & \text{Nuku'alofa} \\ \hline \text{Kazakhstan} & \text{Nur-Sultan} \\ \hline \text{Norway} & \text{Oslo} \\ \hline \text{Canada} & \text{Ottawa} \\ \hline \text{Burkina Faso} & \text{Ouagadougou} \\ \hline \text{Federated States of Micronesia} & \text{Palikir} \\ \hline \text{Panama} & \text{Panama City} \\ \hline \text{Suriname} & \text{Paramaribo} \\ \hline \text{France} & \text{Paris} \\ \hline \text{Cambodia} & \text{Phnom Penh} \\ \hline \text{Montenegro} & \text{Podgorica} \\ \hline \text{Haiti} & \text{Port au Prince} \\ \hline \text{Mauritius} & \text{Port Louis} \\ \hline \text{Papua New Guinea} & \text{Port Moresby} \\ \hline \text{Trinidad and Tobago} & \text{Port of Spain} \\ \hline \text{Vanuatu} & \text{Port Vila} \\ \hline \text{Benin} & \text{Porto Novo} \\ \hline \text{Czech Republic (Czechia)} & \text{Prague} \\ \hline \text{Cape Verde} & \text{Praia} \\ \hline \text{South Africa} & \text{Pretoria, Bloemfontein, Cape Town} \\ \hline \text{Kosovo} & \text{Pristina} \\ \hline \text{North Korea} & \text{Pyongyang} \\ \hline \text{Ecuador} & \text{Quito} \\ \hline \text{Morocco} & \text{Rabat} \\ \hline \text{Iceland} & \text{Reykjavik} \\ \hline \text{Latvia} & \text{Riga} \\ \hline \text{Saudi Arabia} & \text{Riyadh} \\ \hline \text{Italy} & \text{Rome} \\ \hline \text{Dominica} & \text{Roseau} \\ \hline \text{Grenada} & \text{Saint George's} \\ \hline \text{Antigua and Barbuda} & \text{Saint John's} \\ \hline \text{Costa Rica} & \text{San Jose} \\ \hline \text{San Marino} & \text{San Marino} \\ \hline \text{El Salvador} & \text{San Salvador} \\ \hline \text{Yemen} & \text{Sana'a} \\ \hline \text{Chile} & \text{Santiago} \\ \hline \text{Dominican Republic} & \text{Santo Domingo} \\ \hline \text{Sao Tome and Principe} & \text{Sao Tome} \\ \hline \text{Bosnia and Herzegovina} & \text{Sarajevo} \\ \hline \text{South Korea} & \text{Seoul} \\ \hline \text{Singapore} & \text{Singapore} \\ \hline \text{North Macedonia (Macedonia)} & \text{Skopje} \\ \hline \text{Bulgaria} & \text{Sofia} \\ \hline \text{Sweden} & \text{Stockholm} \\ \hline \text{Fiji} & \text{Suva} \\ \hline \text{Taiwan} & \text{Taipei} \\ \hline \text{Estonia} & \text{Tallinn} \\ \hline \text{Kiribati} & \text{Tarawa Atoll} \\ \hline \text{Uzbekistan} & \text{Tashkent} \\ \hline \text{Georgia} & \text{Tbilisi} \\ \hline \text{Honduras} & \text{Tegucigalpa} \\ \hline \text{Iran} & \text{Tehran} \\ \hline \text{Israel} & \text{Tel Aviv (Jerusalem has limited recognition)} \\ \hline \text{Bhutan} & \text{Thimphu} \\ \hline \text{Albania} & \text{Tirana (Tirane)} \\ \hline \text{Japan} & \text{Tokyo} \\ \hline \text{Libya} & \text{Tripoli} \\ \hline \text{Tunisia} & \text{Tunis} \\ \hline \text{Mongolia} & \text{Ulaanbaatar} \\ \hline \text{Liechtenstein} & \text{Vaduz} \\ \hline \text{Malta} & \text{Valletta} \\ \hline \text{Vatican City} & \text{Vatican City} \\ \hline \text{Seychelles} & \text{Victoria} \\ \hline \text{Austria} & \text{Vienna} \\ \hline \text{Laos} & \text{Vientiane} \\ \hline \text{Lithuania} & \text{Vilnius} \\ \hline \text{Poland} & \text{Warsaw} \\ \hline \text{United States} & \text{Washington D.C} \\ \hline \text{New Zealand} & \text{Wellington} \\ \hline \text{Namibia} & \text{Windhoek} \\ \hline \text{Côte d'Ivoire (Ivory Coast)} & \text{Yamoussoukro} \\ \hline \text{Cameroon} & \text{Yaounde} \\ \hline \text{Armenia} & \text{Yerevan} \\ \hline \text{Croatia} & \text{Zagreb} \\ \hline \end{array}$$

Your code may use any libraries you like and may even access the Internet to get relevant data. It may also output the dates and times in any easily human readable form you choose. You should assume the code is run in 2020. The time you give for sunset will be deemed correct if there is at least one website or data source (that existed before this question was posed) that agrees with you.

# Answer
# 05AB1E, 106 bytes

```
’»‚†Ò‚Ÿ.ŒŒ/‚ïŒÇíÇ.htm’.w’¡Õ="17">’¡ε'<¡н„,(S¡н}¦āÈÏ{ε’Š¹.ŒŒ/€±?q=¿Ô+ÿ+ƒÜ’.w©’ƒ£-c·¼:2">’¡θ5£®žg…ÿ (¡θ')¡н‚

```

Couple of assumptions, which are allowed and/or required for the challenges:

1. The program is run in 2020.
2. The url https://geographyfieldwork.com/WorldCapitalCities.htm is accessible and contains the html shown in the second TIO below
3. Google is accessible and contains the html shown in the fourth TIO below
4. *\[Temporarily\]* Assumes Elixir (in which 05AB1E is built) accessing a website makes adjustments similar to a browser (i.e. implicitly adds `https://` and converts spaces to `%20`). I'll try to verify this locally in a moment. If this isn't true, I'll delete this answer and fix it.

Outputs all times in their respective time zones instead of all in GMT as the challenge description states, which OP allowed in the comments.
This will be output as a list of pairs, where each pair is the time with a timezone (i.e. `["21:46","CEST"]`).

No direct TIO, since the `.w` builtin (to access a website) is disabled on TIO. But:

```
’»‚†Ò‚Ÿ.ŒŒ/‚ïŒÇíÇ.htm’

```

Try this part online to see the generation of the URL.

```
’¡Õ="17">’¡ε'<¡н„,(S¡н}¦āÈÏ{

```

Try this part online to see it creates the sorted list of cities based on the website's HTML content.

```
’Š¹.ŒŒ/€±?q=¿Ô+ÿ+ƒÜ’

```

Try this part online to see the generation of the Google-search URL.

```
©’ƒ£-c·¼:2">’¡θ5£®žg…ÿ (¡θ')¡н‚

```

Try the TIO in this pastebin (the link of the TIO itself is too large.. -\_-) to see it creates the correct result for a given city based on the Google's search result HTML content.

**Explanation:**

```
’»‚†Ò‚Ÿ.ŒŒ/‚ïŒÇíÇ.htm’ # Push dictionary string "geographyfieldwork.com/worldcapitalcities.htm"
 .w                    # Access this website and read its HTML content
   ’¡Õ="17">’          # Push dictionary string 'height="17">'
             ¡         # Split the html on that
              ε        # Map each string-part to:
               '<¡    '#  Split it on "<"
                  н    #  And only leave the first part
               „,(S¡   #  Split that part by "," and "("
                    н  #  And again only leave the first part
              }¦       # After the map: remove the first empty string
                       # (we now have a list of all unordered countries + cities)
                ā      # Push a list in the range [1,length] (without popping)
                 È     # Check for each value whether it's odd
                  Ï    # Only leave the strings at those truthy values
                   {   # And sort those alphabetically

```

We now have a sorted list of all cities.

```
ε                      # Map each city to:
 ’Š¹.ŒŒ/€±?q=¿Ô+ÿ+ƒÜ’  #  Push dictionary string "google.com/search?q=sunset+ÿ+today",
                       #  where the `ÿ` is automatically filled with the city
 .w                    #  Access this website and read its HTML content
   ©                   #  Store it in variable `®` (without popping)
    ’ƒ£-c·¼:2">’      "#  Push dictionary string 'line-clamp:2">'
                ¡      #  Split the content on that
                 θ     #  Only leave the last (second) part
                  5£   #  Only leave the first 5 characters (the time)
   ®                   #  Push the HTML content again
    žg                 #  Push the current year (2020)
      …ÿ (             #  Push string "ÿ (", where the `ÿ` is filled with 2020: "2020 ("
          ¡            #  Split the content on that
           θ           #  Only leave the last (second) part
            ')¡       '#  Split it on ")"
               н       #  And leave the first item (the timezone)
   ‚                   #  Pair the time and timezone strings together
                       # (after which the resulting mapped pair of strings is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `’»‚†Ò‚Ÿ.ŒŒ/‚ïŒÇíÇ.htm’` is `"geographyfieldwork.com/worldcapitalcities.htm"`; `’¡Õ="17">’` is `'height="17">'`; `’Š¹.ŒŒ/€±?q=¿Ô+ÿ+ƒÜ’` is `"google.com/search?q=sunset+ÿ+today"`; and `’ƒ£-c·¼:2">’` is `'line-clamp:2">'`.
> 4 votes

---
Tags: code-golf
---


title: Gamma Function Golf

text:
# Question
Title: Gamma Function Golf
Given a real number `t` in `(-10^9,13)` (not including `-10^9` or `13`) as input, output `Γ(t)`, also known as the Gamma function, which is defined as follows:

You may not use a built-in Gamma function to solve this task, nor may you use built-in numeric or symbolic integration functions. Your output should be accurate to 6 significant figures or within `10^-6` of the actual value, whichever is less restrictive for the given value. Python's built-in Gamma function will be used for determining the actual value. You may assume `Γ(t)` is defined - that is, `t` is either a positive real number or a non-integer negative real number - and that `|Γ(t)| ≤ 10^9`. Here is a reference program that you may use to get the actual values, using Python's built-in Gamma function.

### Examples

```
1 -> 1.000000
-2.5 -> -0.945309
3.14159265 -> 2.288038
-2.71828182846 -> -0.952682
12 -> 39916800.000000
0.5 -> 1.772454
8.675309 -> 20248.386956
-10.1 -> -0.000002

```

## Rules

* This is , so shortest answer (in bytes) wins.
* Standard loopholes are forbidden.
* Input and output may be performed in whatever manner is considered standard for your language.
* You may write a full program, a function, or anything that is normally considered a valid answer for your language

# Leaderboard

The Stack Snippet at the bottom of this post generates the leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

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

```
## Language Name, N bytes

```

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

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

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 63887; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 45941; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>
```

# Answer
# Pyth, 21 bytes

As with my TI-BASIC answer, I haven't been able to test this with the full 8^10 iterations, but everything seems good with smaller cases.

```
cu*Gc^hc1HQhcQHS^8T1Q

```

Explanation:

```
                            [implicit: Q=input]
                ^8T         8**10
               S^8T         [1,2,3,...,8**10]
  *Gc^hc1HQhcQH             lambda G,H:G*(1+1/H)**Q/(1+Q/H)
                   1        Base case
 u*Gc^hc1HQhcQHS^8T1        Reduce with base case 1
c                   Q       Divide by Q

```

Try it here with 2000 iterations instead of 8^10.
> 3 votes

# Answer
# C++14, ~~86~~ ~~85~~ 81 bytes

```
    [](auto t){auto v=1.;for(int x=1;x<1e9;++x)v*=pow(1+1./x,t)/(1+t/x);return v/t;};

```

I didn't spend much time on this one. I just looked an approximation that seemed the easiest to implement (in the manner of bytes). It will take some time to compute the value (since the loop is over all positive integers), but time limitation is not specified in the challenge. It is anonymous function (lambda), which takes any argument (convertible to `T` on which `pow(double, T)` and `operator/(T, int)` can be called) and returns `double`.

Ungolfed with usage

```
    #include <iostream>
    int main()
    {
        auto r = [](auto t)
        {
            auto v = 1.;
            for (int x = 1; x < 1e9; ++x)
                v *= pow(1 + 1. / x, t) / (1 + t / x);
            return v / t;
        };
        std::cout << r(-2.71828182846); // outputs -0.952682
    }

```
> 9 votes

# Answer
## Minkolang 0.12, ~~35~~ ~~34~~ 25 bytes

```
n$zl8;dz;z$:r[i1+dz+$:*]N

```

This does halt with an error (on trying to divide by 0), but that is allowed as per Meta consensus. Add a `.` at the end for a program that halts normally. Try all test cases at once. (The loop iterates only 1e4 times so it would finish sooner rather than later.)

### Explanation

Zereges used one of the alternative, infinite product definitions. As it turns out, the other is much more amenable to implement in Minkolang.

This is a limit as `n` goes to infinity, which means that I can calculate both `n!` and `(t+n)` as I go. So I take out `1/t` (because `0!=1`) and `n^t` because that one cannot be calculated sequentially without knowing the ending value of `n`. As it happens, because `n` is the limit, I can use it twice. Once as a factor in the calculation and once as the number of times to run the loop.

An sequential infinite product has to start with something, usually 1. In this case, it's `n^t/t`. In the body of the loop, I calculate `k/(t+k)` and multiply this with the product so far. At the end, the whole product has been calculated and output. This is essentially what my program does, with `n` high enough that the answer is precise enough.

```
n                            Take number from input
 $z                          Store it in the register (this is t; retrieved with z)
   l8;                       10^8 (this is n, the limit)
      d                      n,n
       z;                    n,n^t
         z$:                 n,n^t/t
            r                Reverse stack -> n^t/t,n
             [               For loop that runs n times
              i1+            k
                 d           k,k
                  z+         k,t+k
                    $:       k/(t+k)
                      *      Multiply
                       ]N    Close for loop and output as integer

```

As there is no `.`, it wraps around and starts over. However, `n` now produces `-1` because the input is empty, which eventually leads to attempting to divide by 0, which halts the program.
> 6 votes

# Answer
# Julia, 141 bytes

```
z->(z-=1;a=90;c(k)=(k=big(k);(-1)^(k-1)/factorial(k-1)*(a-k)^(k-.5)*exp(a-k));(z+a)^(z+.5)*exp(-z-a)*(√(2π)+sum([c(k)/(z+k)for k=1:a-1])))

```

This creates an unnamed lambda function that accepts a real number and returns a real number. It uses Spounge's approximation to compute Gamma.

Ungolfed:

```
function Γ(z::Real)
    # Spounge's approxmation is for Γ(z+1), so subtract 1
    z -= 1

    # Choose a number for the constant a, which determines the
    # bound on the error
    a = 90

    # Define a function for the sequence c_k
    function c(k::Integer)
        # Convert k to a BigInt
        k = big(k)
        return (-1)^(k-1) / factorial(k-1) * (a-k)^(k-1/2) * exp(a-k)
    end

    # Compute the approximation
    return (z+a)^(z+1/2) * exp(-z-a) * (√(2π) + sum([c(k)/(z+k) for k=1:a-1]))
end

```
> 4 votes

# Answer
# Python, ~~348~~ ~~448~~ ~~407~~ ~~390~~ 389 bytes

Special thanks to @Mego!

A crossed out 448 is (almost) still a 448! :p

This is based on the Lanzcos approximation. Golfed from here

```
from cmath import*
C=[0.9999999999998099,676.5203681218851,-1259.1392167224028,771.3234287776531,-176.6150291621406,12.507343278686905,-0.13857109526572012,9.984369578019572e-6,1.5056327351493116e-7]
def g(z):
 z-=1;if z.real<0.5:return pi/(sin(pi*z)*gamma(1-z))
 else:
  x=C[0]
  for i in range(1,9):x+=C[i]/(z+i)
  t=z+7.5;return sqrt(2*pi)*t**(z+0.5)*exp(-t)*x

```
> 3 votes

# Answer
# Japt, 45 bytes

**Japt** is a shortened version of **Ja**vaScri**pt**. Interpreter

```
$for(V=X=1;X<1e9;)$V*=(1+1/X pU /(1+U/X++;V/U

```

Of course, 1e9 = 1,000,000,000 iterations takes forever, so for testing, try replacing the `9` with a `6`. (1e6 is accurate to ~5 significant figures. Using 1e8 on an input of `12` is enough to get the first six.)

Test-case results: (using 1e7 precision)

```
       1:  1
    -2.5: -0.9453083...
      pi:  2.2880370...
      -e: -0.9526812...
      12:  39916536.5...
     0.5:  1.7724538...
8.675309:  20248.319...
   -10.1: -0.0000022...

```

### How it works

```
         // Implicit: U = input number
$for(    // Ordinary for loop.
V=X=1;   //  Set V and X to 1.
X<1e9;)$ //  Repeat while X is less than 1e9.
V*=      // Multiply V by:
(1+1/X   //  1 plus (1 over X),
pU /     //  to the power of U, divided by
(1+U/X++ //  1 plus (U over X). Increment X by 1.
;V/U     // Output the result of (V over U).

```
> 3 votes

# Answer
# Python 3, ~~74~~ ~~68~~ ~~78~~ 73 bytes

Thanks @Mego and @xnor

This is a translation of the C++ answer by Zereges. Basically, this is an alternate definition of the gamma function, hence more accurate (and what is great is that is uses less bytes!)

I am sorry for all the mistakes!

```
def g(z,v=1):
 for i in range(1,10**9):v*=(1+1/i)**z/(1+z/i)
 return v/z

```
> 3 votes

# Answer
# TI-BASIC, 35 bytes

```
Input Z
1
For(I,1,ᴇ9
Ans(1+I⁻¹)^Z/(1+Z/I
End
Ans/Z

```

This uses the same algorithm as Zereges.

Caveat: I haven't actually tested this with the full 1e9 iterations; based on the time taken for smaller values, I expect the runtime to be on the order of *months*. However, it appears to converge, and there should be no problems with rounding errors. TI stores numbers as decimal floats with 14 digits of precision.
> 3 votes

# Answer
# APL (Dyalog Unicode), 13 bytes

```
1e8∘(*÷⊣!+)÷⊢

```

Try it online!

The above code uses the `!` function, but it is used as generalized binomial coefficient, not factorial. A version without the `!` symbol altogether:

# APL (Dyalog Unicode), 20 bytes

```
1e8∘(*×(×/⊢÷+)∘⍳⍨)÷⊢

```

Try it online!

In both cases, `1e7` is used instead of `1e8` to show that the actual values calculated are close enough to the true values.

### How it works: the math

Uses the formula used in TanMath's Python answer and therefore Zereges' C++ answer.

Basically, the solutions by TanMath/Zereges compute the following, which I developed further to suit better to APL:

$$ \begin{align} \Gamma(x) &\approx \frac1x \prod\_{i=1}^{n}{\Bigl(1+\frac{1}{i}\Bigr)^x \div \Bigl(1+\frac{x}{i}\Bigr)} \\ &= \frac1x \prod\_{i=1}^{n}{\Bigl(\frac{i+1}{i}\Bigr)^x \times \Bigl(\frac{i}{x+i}\Bigr)} \\ &= \frac1x \Bigl(\prod\_{i=1}^{n}{\frac{i+1}{i}}\Bigr)^x \times \prod\_{i=1}^{n}{\Bigl(\frac{i}{x+i}\Bigr)} \\ &\approx \frac{n^x}x \times \prod\_{i=1}^{n}{\Bigl(\frac{i}{x+i}\Bigr)} \tag{1}\label{eq1}\\ &= \frac{n^x}x \div \binom{x+n}{n} \tag{2}\label{eq2}\\ \end{align} $$

The second solution uses equation \\$\eqref{eq1}\\$ while the first uses equation \\$\eqref{eq2}\\$, both using \\$n=10^8\\$ in order to get enough precision.

### How it works: the code

```
1e8∘(*÷⊣!+)÷⊢  ⍝ Input←x; n←1e8
1e8∘(    +)    ⍝ n+x
       ⊣!      ⍝ binom(n+x, n)
     *÷        ⍝ n^x ÷ binom(n+x, n)
           ÷⊢  ⍝ Divide by x

1e8∘(*×(×/⊢÷+)∘⍳⍨)÷⊢  ⍝ Input←x; n←1e8
1e8∘(  (     )∘⍳⍨)    ⍝ Generate 1..n; for each i in 1..n,
          ⊢÷+         ⍝ i÷(x+i)
        ×/            ⍝ Product over all i
     *×               ⍝ Multiply n^x
                  ÷⊢  ⍝ Divide by x

```
> 2 votes

# Answer
# Julia, 41 bytes

```
x->prod([(1+1/i)^x/(1+x/i)for i=1:1E7])/x

```

This is a translation of Zereges' C++ answer. While my other Julia answer finishes instantaneously, this is rather slow. It computes the test cases in a couple seconds each on my computer.

Ungolfed:

```
function f(x::Real)
    prod([(1 + 1/i)^x / (1 + x/i) for i = 1:1E7]) / x
end

```
> 1 votes

# Answer
# Mathematica, 40 bytes

```
NProduct[(1+1/n)^#/(1+#/n),{n,1,∞}]/#&

```
> 1 votes

# Answer
# Prolog, 114 bytes

This is a translation of Zereges' C++ answer.

```
q(F,F,V,Z):-X is V/Z,write(X).
q(F,T,V,Z):-W is(1+1/F)**Z/(1+Z/F)*V,I is F+1,q(I,T,W,Z).
p(N):-q(1.0,1e9,1,N),!.

```

Try it out online here
Run it with a query of the form:

```
p(12).

```

Running it with 1e9 recursions takes about 15 minutes.
If you decrease it to 1e6 it takes about 1 second which makes for easier (but less acurate) testing.
Running it in an interpreter on you computer/laptop is most likely faster for most people as well.
> 0 votes

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


title: Closest to a square

text:
# Question
Title: Closest to a square
# The task

Given a positive integer `c`, output two **integers** `a` and `b` where `a * b = c` and each `a` and `b` is closest to `sqrt(c)` while still being integers.

# Test cases

```
Input: 136
Output: 17 8

```

```
Input: 144
Output: 12 12

```

```
Input: 72
Output: 9 8

```

```
Input: 41
Output: 41 1

```

```
Input: 189
Output: 21 9

```

# Rules

1. `a`, `b` and `c` are all positive integers
2. You may give `a` and `b` in any order, so for the first case an output of `8 17` is also correct
3. This is , so lowest byte count wins!

# Answer
> 5 votes
# 05AB1E, 3 bytes

Given an input \\$ c \\$, it outputs \\$ a \\$ and \\$ b \\$ as a list in increasing order. If \\$ c \\$ is a square, it outputs a single integer (which according to the OP is allowed).

```
ÑÅs

```

Try it online!

## Explanation

```
Ñ     # All divisors
Ås    # Middle elements

```

# Answer
> 4 votes
# JavaScript (ES7), 35 bytes

```
f=(n,d=n**.5)=>n%d?f(n,-~d):[d,n/d]

```

Try it online!

### How?

If \\$n\\$ is a square, \\$d=\sqrt{n}\\$ is an integer which obviously divides \\$n\\$, so we immediately have an answer. Otherwise, the first `-~d` will act as \\$\lceil{d}\rceil\\$ and the next ones as \\$d+1\\$. Either way, we stop as soon as \\$n\equiv 0\pmod{d}\\$ which in the worst case (i.e. if \\$n\\$ is prime) happens when \\$d=n\\$.

# Answer
> 4 votes
# Python 2, 45 bytes

```
i=n=input()
while(i*i>n)+n%i:i-=1
print n/i,i

```

Try it online!

# Answer
> 3 votes
# Jelly, 8 bytes

```
ÆDżṚ$SÞḢ

```

A monadic Link accepting a positive integer which yields a list of two positive integers.

**Try it online!**

### How?

```
ÆDżṚ$SÞḢ - Link: positive integer, X   e.g. 12
ÆD       - divisors of X                    [1,2,3,4,6,12]
    $    - last two links as a monad:
   Ṛ     -   reverse                        [12,6,4,3,2,1]
  ż      -   zip                            [[1,12],[2,6],[3,4],[4,3],[6,2],[12,1]]
      Þ  - sort by:
     S   -   sum                            [[3,4],[4,3],[2,6],[6,2],[1,12],[12,1]]
       Ḣ - head                             [3,4]

```

# Answer
> 2 votes
# MATL, 9 bytes

```
Z\J2/)Gy/

```

Try it online!

### Explanation

```
Z\   % Implicit input. Array of divisors
J2/  % Push imaginary unit, divide by 2: gives 0.5j
)    % Index into the array. When used as an index, the imaginary unit means "end".
     % Thus the index 0.5j for [1 2 3 6] would give the 2nd entry (end=4th entry,
     % end/2 = 2nd entry, indexing is 1-based), whereas for [1 2 3 6 12] it would
     % give the "2.5-th" entry. This index is rounded up, so the result would be
     % the 3rd entry
G    % Push input again
y    % Duplicate second-top element in stack (that is, the selected entry)
/    % Divide
     % Implicitly display stack contents

```

# Answer
> 2 votes
# C (gcc), 51 bytes

```
i;f(a,c)int*a;{for(i=0;i*i++<c;)c%i||(*a=i);c/=*a;}

```

Try it online!

# Answer
> 2 votes
# Python 2, 47 bytes

```
f=lambda n,v=1:[n/v,v]*(n/v-v<1>n%v)or f(n,v+1)

```

A recursive function.

**Try it online!**

# Answer
> 2 votes
# Charcoal, 20 bytes

```
Ｎθ≔⊕⌈Φ₂θ¬﹪θ⊕ιηＩ⟦÷θηη

```

Try it online! Link is to verbose version of code. Technically only works up to `a=2⁵³`, but would be stupidly slow well before then anyway. Explanation:

```
Ｎθ

```

Input `c`.

```
≔⊕⌈Φ₂θ¬﹪θ⊕ιη

```

List all of the factors of `c` that do not exceed its floating-point square root, and take the largest `b`.

```
Ｉ⟦÷θηη

```

Calculate and output `a` and `b`.

# Answer
> 2 votes
# Julia 54 bytes

## Try it

```
n->begin i=findfirst(x->x^2>=n&&n%x==0,1:n);i,n÷i;end

```

# Answer
> 1 votes
# Python 2, ~~52~~ 48 bytes

```
f=lambda c,i=1:i*i>=c>c%i<1and(i,c/i)or f(c,i+1)

```

Try it online!

Simply increments `i` until it satisfies

```
i*i>=c and c%i==0

```

Then returns the pair `(i, c/i)`.

# Answer
> 1 votes
# Retina 0.8.2, 34 bytes

```
.+
$*
(?<-2>(^(1)+?|\1))+$
$.1 $#1

```

Try it online! Link includes test cases. Explanation:

```
.+
$*

```

Convert `c` to unary.

```
(?<-2>(^(1)+?|\1))+$

```

The `(1)+` matches a minimal substring `a` of `1`s individually into the `\2` stack, where they are popped off as the entire substring `\1` is repeatedly matched `b` times until it reaches `c`. This popping mechanism thus prevents `b` from exceeding `a`, but as `a` is minimal it must therefore be the smallest factor not less than the square root. Excitingly, .NET allows you to populate the `\2` stack on the first iteration of the `(?<-2>)` loop. (On the remainder of the loops, the `^` no longer matches, so the `\1` alternative is used.)

```
$.1 $#1

```

Output `a` and `b`.

# Answer
> 1 votes
# Erlang (escript), 68 bytes

```
f(X)->Y=lists:max([I||I<-lists:seq(1,X),X rem I==0,I*I=<X]),[Y,X/Y].

```

Try it online!

# Answer
> 1 votes
# Java (JDK), 52 bytes

```
n->{int i=n;for(;i*i>n|n%i>0;)i--;return n/i+","+i;}

```

Try it online!

# Answer
> 1 votes
# dc, 39 bytes

```
[d_3R/fq]sE?ddvd[_3R%0=E1-rd3RdlFx]dsFx

```

Try it online!

Or verify the test cases.

---

**How it works:**

```
Command  Stack (top on the right)

[        # Macro starts with stack at:
               # n d
               # Prints n/d and d, and then quits.
 d       # n d d
 _3R     # d n d
 /       # d n/d
 f       # Prints stack.
 q       # Quit this macro and the macro which called it.
]sE      # End macro and save it in register E.

?        # n  (Input values and push it on stack.)
dd       # n n n
v        # n n d
         #         d is a potential divisor of n;
         #         it's initialized to int(sqrt(n)).
d        # n n d d
[        # Start macro to be used as a loop.
 _3R     # n d n d
 %       # n d n%d
 0=E     # n d     If d divides n, call macro E to end.
 1-      # n d     New d = d - 1.
 r       # d n
 d       # d n n
 3R      # n n d
 d       # n n d d
         #         The stack is now set up correctly to
         #         go back to the top of the loop, with
         #         d now one step lower.
 lFx     # Call macro F to go back to the top of the loop.
]dsFx    # End macro, save it as F, and execute it.

```

# Answer
> 1 votes
# , ~~48~~ ~~46~~ ~~45~~ 41 bytes

```
x=scan();b=1:x;a=b[!x%%b&b^2>=x][1];a;x/a

```

Try it online!

Finds first (`[1]`) divisor (`which(!x%%b)`) that is equal-to or greater than square-root (`b^2>=x`); returns this & reciprocal (`a;x/a`).
Previous approach (46 bytes) found divisor closest to centre of list-of-divisors, but couldn't be golfed-down so effectively.

# Answer
> 1 votes
# Perl 5 `-pa`, 37 bytes

```
$_=0|sqrt;$_--while"@F"%$_;say"@F"/$_

```

Try it online!

# Answer
> 1 votes
# Python 3, 73 60 59 bytes

Not the shortest or best solution by any means, but I think it's a creative approach. Prints the two factors without separator between them and only (consistently) works for inputs up to 1008.

```
r=range(1000)
f=[a*b*(a*a>=a*b)for a in r for b in r].index

```

Try it online!

# Python 3, 57 bytes

Still not the shortest solution, but it's at least somewhat expressive and clear what's going on.

```
lambda n:max((x,n/x)for x in range(1,n+1)if n%x<(x*x<=n))

```

Try it online!

# Answer
> 0 votes
# Pyth, ~~14~~ 12 bytes

```
fsIJcQTs@Q2J

```

Try it online!

* `s@Q2` Starting from the floor of the square root of the input:

+ `f` find the first integer \\$T\\$ such that:
    + `sIcQT` \\$T\\$ divides the input
* `cQT` gives the input divided by \\$T\\$ (ie. the other divisor) so we assign that value to `J`
* The two divisors `T` and `J` are then implicitly printed

# Answer
> 0 votes
# Python 2, 66 bytes

```
def g(s):x=[[a,s/a]for a in range(1,s)if s%a==0];print x[len(x)/2]

```

Try it online!

# Answer
> 0 votes
# SageMath, <sup>~~63~~</sup> 60 bytes

```
def f(n):
 d=divisors(n)
 while len(d)>2:d=d[1:-1]
 return d

```

Try it online!

# Answer
> 0 votes
# MathGolf, 7 bytes

```
─h½§_@/

```

Try it online!

## Explanation

```
─          get a list of all divisors
 h½§       get the divisor at the middlemost index
           (if length is equal returns the smallest of the two middle elements)
    _      duplicate TOS
     @     rrot3 (pops input again and places it as the second item from the top)
      /    divides the input number by the extracted divisor, giving the other divisor

```

# Answer
> 0 votes
# C++ (gcc), 108 bytes 103 bytes

```
#import<iostream>
int n,a,b,i;main(){for(std::cin>>n;i*i++<=n;)n%i<1?a=i,b=n/i:0;std::cout<<a<<' '<<b;}

```

Try it online!

`Thanks to callingcat, for -5 bytes`

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


title: Tile the plane with squashed hexagons

text:
# Question
Title: Tile the plane with squashed hexagons
I came across an interesting tiling of the plane using squashed hexagons in a popular math book. All the six edges of the squashed hexagon are the same length. Two opposite corners are right angles and the rest four corners are 135 degrees each. This shape allows four squashed hexagons be arranged so that they meet at a point. Then “concentric rings” of squashed hexagons can outline the resulting cross indefinitely.

Write a full program or a function that accepts an integer 0 \< `n` \< 10 and renders `n` rings of this tessellation. You can rotate the image by 45 dergrees if it's more convenient for your algorithm. You can render directly to the screen, or save the result to a file. In either case, please provide an image demonstrating the the result of your code. You can crop the resulting image so that it contains only the hexagons.

## Examples:

n = 1

n = 2

n = 3

n = 4

The shortest code in bytes in each language wins.

# Answer
## JavaScript (ES6), ~~319~~ 313 bytes

```
f=
n=>{s=`<svg viewBox=${n*=-12},${n},${n*=-2},${n}><use href=#d transform=rotate(180) /><g id=d><use href=#s transform=rotate(90) /><path id=s fill=none stroke=#000 d=`
for(n/=24;n--;)for(j=0;j<=n;j++)s+=`M${n*5+j*7},${n*12-j*7}h7l5,5v7h-7l-5,-5z`+(j<n?`M${n*12},${n*5-j*10}h7l5,-5l-5,-5h-7l-5,5z`:``)
return s+`>`}
```

```
<input type=number min=1 oninput=o.innerHTML=f(this.value)><div id=o>
```

Output is an HTML5 SVG, which the snippet inserts into a DOM node so that you can see it. Output is rotated by 45° as allowed by the question. Edit: Saved 3 bytes thanks to @KevinCruijssen.
> 18 votes

# Answer
# GFA Basic 3.51 (Atari ST),  ~~187 181 174~~  171 bytes

A manually edited listing in .LST format. All lines end with `CR`, including the last one.

```
PRO f(n)
DR "MA166,94"
t$="FD8LT45PD"
h$=t$+"FD8LT90"+t$+t$+"FD8LT90FD8BK8LT90FD8RT45"
a$=""
F i=1TO n
DR STRING$(4,a$+h$+"LT45BK8"+a$+t$)+"PUFD8RT45"+t$
a$=a$+h$
N i
RET

```

### Expanded and commented

```
**PROCEDURE f(n)**
  ' move the pen at (166,94)
  **DRAW "MA166,94"**
  ' t$ = move forward by 8, left turn of 45 degrees, pen down
  **t$="FD8LT45PD"**
  ' h$ holds the directives to draw a single hexagon
  ' and get ready to draw a contiguous hexagon
  **h$=t$+"FD8LT90"+t$+t$+"FD8LT90FD8BK8LT90FD8RT45"**
  ' a$ is used to store a concatenation of hexagons
  **a$=""**
  ' draw n rings
  **FOR i=1 TO n**
    ' draw a full ring and move to the next ring
    **DRAW STRING$(4,a$+h$+"LT45BK8"+a$+t$)+"PUFD8RT45"+t$**
    ' append a new hexagon to a$
    **a$=a$+h$**
  **NEXT i**
**RETURN**
```

### Example output
> 15 votes

# Answer
## Logo, ~~276~~ 245 bytes

```
to i:n
repeat 2[repeat:n[repeat 2[fd 7
rt 45]fd 7
bk 7
lt 90]rt 90
fd 7
rt 90]end
to j:n
make"m:n
repeat:n[i:m
make"m:m-1
rt 90
repeat 2[fd 7
lt 45]]repeat:n[repeat 2[rt 45
bk 7]lt 90]end
to k:n
repeat 4[j:n
rt 90
fd 7
lt 45
j:n-1
rt 45
bk 7]end

```

Use `k <n>` to invoke. Output is rotated by 45° as allowed by the question. Example for `n=10`: Try it online!
> 8 votes

# Answer
# Python 3, ~~361~~ 342 bytes

```
from turtle import*
def t(a):r(a);fd(9)
def k(i):Q.add((o+i,pos(),heading(),m))
u=45;n=int(input());Q=set((1,(0,0),a*90,a>3)for a in range(8));ht()
while Q:
 o,p,a,m=Q.pop()
 if round(o)>n:continue
 r=(rt,lt)[m];g=not o%1;up();goto(*p);seth(a);pd();t(-u)
 if g:k(1.1)
 t(u)
 if g:k(1)
 t(u);t(-u);k(2+g/3);undo();undo();t(90);t(u);t(u)
done()
```
> 3 votes

# Answer
## Shadertoy (GLSL), ~~777 710 679 644 630~~ 609 bytes

```
#define V vec2
#define F float
#define R return
const int n=10;const F Z=2.2/F(n),W=.01*Z,L=.07*Z,K=L/2.,M=K*1.414;F h(V u,V c){u=abs(u-c);
if(u.x>.0&&u.x<K)R abs(u.y-M)<W/1.4?.0:1.;else if(u.x<K+M+W)R abs(u.y-M+u.x-K)<W?.0:1.;R 1.;}
F m(V u,V c){u=abs(u);R h(u,c)*h(u.yx,c);}void mainImage(out vec4 f,in V c){V S=iResolution.xy;V v=c/S-V(.5);
v.y/=S.x/S.y;F b=-atan(1.);mat2 o=mat2(cos(b),-sin(b),sin(b),cos(b));V w=o*v;F s=1.,a=K+M,k=.0,l;int i,j,J;
for(i=0;i<n;i++,k++){J=i/2+1;l=.0;for(j=0;j<J;j++,l++){F z=l*2.*M;if(i%2==1)z+=M;
s*=m(v,V(a+k*(L+M),z));if(i<n-1)s*=m(w,V(a+k*(L+M)+L,z));}}f.xyz=vec3(s);}

```

Shadertoy link

Happy to finally see this working, the tile layout can be a bit puzzling at first. It automatically "zooms in" for lower n values, but can also be manually adjusted by changing the `Z` variable because it's not optimal. Something is a bit wrong with the line drawing where diagonal and straight lines meet (which gets more apparent for lower `n` values), perhaps I'll find a way to get that fixed. There also is an ungolfed version with some comments on how it does things.

Output for `n` = 10:
> 2 votes

# Answer
# JavaScript + HTML + CSS, 82 + 39 + 204 = 325 bytes

### JavaScript

Function that takes a number `n`. An internal function `P` recursively generates an ASCII pyramid of  characters, formatted as a CSS string with `\a` line breaks. On the HTML element with `id="X"`, sets the custom CSS custom properties `--` and `---` to `P(n)` and `P(n-1)`, respectively.

```
n=>X.style=`--:"${(P=n=>(n?P(n-1)+`\\a`:'')+'⬡'.repeat(n))(n-1)}";---:"${P(n)}"`

```

### HTML

8 nested HTML elements whose `:after` pseudo-elements will contain hexagon pyramids; wrapped in a `<pre>` to show line breaks. `<center>` ensures pyramids are centered horizontally.

```
<pre><center id=X><i><b><i><b><i><b><i>

```

### CSS

Applies `transform: rotate(45deg)` to all elements; the rotation effect compounds for the 8 nested elements. Applies `content` such that `i:after` gets the bigger pyramid `---`, and `center:after` and `b:after` get the smaller pyramid `--`. Squishes the ASCII hexagon pyramids into a (decently accurate) tile pattern via `font-size`, `line-height`, `letter-spacing`, and `transform` – results may vary depending on your browser.

```
*{display:flex;place-content:center;transform:rotate(45deg)}:after{font:150%/.62 auto;letter-spacing:-5px;position:absolute;transform:matrix(.69,0,0,1,-1.75,-5);content:var(--)}i:after{top:-8px;--:var(---

```

---

Output for `n` = 10 (Chromium 81, macOS):

---

## Try it!

```
f=

n=>X.style=`--:"${(P=n=>(n?P(n-1)+`\\a`:'')+'⬡'.repeat(n))(n-1)}";---:"${P(n)}"`

f(+prompt())
```

```
head,script{display:none !important}
body{margin:50vmin}

*{display:flex;place-content:center;transform:rotate(45deg)}:after{font:150%/.62 auto;letter-spacing:-.23em;position:absolute;transform:matrix(.71,0,0,1,-1.75,-5);content:var(--)}i:after{top:-.34em;--:var(---
```

```
<pre><center id=X><i><b><i><b><i><b><i>
```
> 1 votes

---
Tags: code-golf, graphical-output
---


title: Bilibili AV/BV Code Conversion

text:
# Question
Title: Bilibili AV/BV Code Conversion
### Background

Bilibili is a China-based video sharing platform, similar to Nico Nico Douga in Japan, and Youtube around the world.

Since the establishment, Bilibili had been using the *AV code* to reference a video. An AV code is a string of 3 or more characters, starting with `av` and followed by a natural number, like `av82054919`.

However, since 23 March 2020, Bilibili introduced a new referencing system called the *BV code*. This time, the code is a string of exactly 12 characters, starting with `BV` and followed by 10 alphanumerical characters, like `BV1XJ41157tQ`. Still, users can use both codes to reference a video, and there is a conversion algorithm between the two.

*(For your information, the two examples reference the same video)*

### The algorithm

To convert from AV code to BV code:

1. Remove the `av` part of the AV code.
2. Do a bitwise XOR between the result in step 1 (as a number) and `177451812`.
3. Add `8728348608` to the result in step 2.
4. Convert the result in step 3 to a 6-digit base-58 number with digits `fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF` in place of `0, 1, ..., 57` respectively. Here, `0, I, O, l` are omitted to eliminate ambiguity. Assume the result is `abcdef`.
5. The BV code is then `BV1db4a1c7ef`.

To convert from BV code to AV code:

1. Remove the 1st to 3rd, the 6th, the 8th and the 10th characters. Assume the result is `abcdef`.
2. Rearrange the result in step 1 to `cbdaef`.
3. Treat the result in step 2 as a base-58 number with digits `fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF` in place of `0, 1, ..., 57` respectively. Convert this base-58 number into decimal.
4. Subtract `8728348608` from the result in step 3.
5. Do a bitwise XOR between the result in step 4 and `177451812`.
6. The AV code is then `av` followed by the result in step 5.

### Example

To convert `av82054919` to BV code:

1. Removing `av` from the code results in `82054919`.
2. \\$82054919\text{ XOR }177451812=242727971\\$
3. \\$242727971+8728348608=8971076579\\$
4. \\$8971076579\_{10} = (13,38,43,6,30,7)\_{58}\\$`1J5XtQ`
5. Substituting: `BV1[X][J]4[1]1[5]7[t][Q]``BV1XJ41157tQ`

To convert `BV1XJ41157tQ` back to AV code:

1. Remove the bracketed numbers: `[BV1]XJ[4]1[1]5[7]tQ``XJ15tQ`
2. Rearranging the characters results in `1J5XtQ`.
3. `1J5XtQ`\\$(13,38,43,6,30,7)\_{58} = 8971076579\_{10}\\$
4. \\$8971076579-8728348608=242727971\\$
5. \\$242727971\text{ XOR }177451812=82054919\\$
6. Prepending `av` to the result, we have `av82054919`.

### Challenge

Write two independent programs or functions, one receiving the AV code as input and outputting the corresponding BV code, and one receiving the BV code as input and outputting the corresponding AV code. Both the prefixes `av` and `BV` are case insensitive, you may choose either upper or lower case to accept or output. Each code should work even without the code from the other.

You may assume that the input for both programs must have a valid format, and the number in its corresponding AV code is between 1 and 2147483647 inclusive.

### Test cases

```
AV code <-> BV code
av82054919 <-> BV1XJ41157tQ
av123456789 <-> BV1yn411L7tG
av1 <-> BV1xx411c7mQ
av2147483647 <-> BV1Fr4k1q7G1

```

You may check your results through this tool (not developed by me). Click the first button after entering the AV/BV code into the input, then the textbox will show the result.

### Winning condition

The total length of the codes of the two programs (measured in bytes) will be your code length, and since this is a code-golf challenge, the submission with shortest code length for each language wins. No standard loopholes.

# Answer
> 5 votes
# Python 2, 170 + 150 = 320 bytes

### AV to BV, ~~180 179 173~~ 170 bytes:

```
lambda s:"BV1{2}{4}4{5}1{3}7{1}{0}".format(*["fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF"[((int(s[2:])^177451812)+8728348608)/58**i%58]for i in range(6)])

```

Try it online!

### BV to AV, ~~165 158~~ 150 bytes:

```
s=input()
n=0
for i in 6,4,8,3,10,11:n=n*58+"fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF".find(s[i])
print"av"+`n-8728348608^177451812`

```

Try it online!

# Answer
> 4 votes
# Python 3, 518 465 439 422 420 412 406 402 401 bytes

*-6 bytes thanks to Surculose Sputum. (I didn't know Python could be made that unreadable!)*
*-4 bytes thanks to Gavin S. Yancey.*
*-1 yet another byte gone thanks to Surculose Sputum*

Encode:

```
def s(x):
 b,a=(int(x[2:])^177451812)+8728348608,''
 while b:a+='fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'[b%58];b//=58
 return f'BV1{a[2::2]}4{a[5]}1{a[3]}7{a[1::-1]}'

```

Decode:

```
def z(i):
 i=i[3:5]+i[6:9:2]+i[10:];a,q,m=i[2]+i[1]+i[3]+i[0]+i[4:],0,1
 for c in a[::-1]:q,m=q+m*'fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'.index(c),m*58
 return'av'+str((q-8728348608)^177451812)

```

Try it online!

A fairly simple solution comprised of parts of this and this. Can probably be golfed down a lot, when I get the time. I think it is golfed down to a good-enough level now. *And now it works*

# Answer
> 3 votes
# 05AB1E, ~~192~~ ~~164~~ 163 (81+82) bytes

**AV to BV - ~~96~~ ~~82~~ 81 bytes:**

```
þ•A³ú[•^•2G&©I•+žL¨…lIOм{œ•F
mʒØà\ç×н˜=ˆ§kð€³ä‘λ°Ð‘ç«(вÍè\pÌ•èÅвA"BV1db4a1c7ef"r‡

```

Try it online or verify all test cases.

**BV to AV - ~~96~~ 82 bytes:**

```
•1ïÓî•S£ιθSƵª.IžL¨…lIOм{œ•F
mʒØà\ç×н˜=ˆ§kð€³ä‘λ°Ð‘ç«(вÍè\pÌ•èÅβ•2G&©I•-•A³ú[•^„avì

```

Try it online or verify all test cases.

NOTE: The TIO's use `S` with `.I` (convert to character-list and \\$n^{th}\\$ permutation builtin) instead of `œ` with `è` (get all permutations and index into the list), since generating all permutations is of course way too slow.

### Explanation:

**AV to BV**:

```
þ                     # Only leave digits of the (implicit) input (to remove "av")
 •A³ú[•               # Push compressed integer 177451812
       ^              # Bitwise-XOR the two integers together
        •2G&©I•       # Push compressed integer 8728348608
               +      # Add the two integers together
žL                    # Push builtin string "zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA9876543210"
  ¨                   # Remove the last character (the "0")
   …lIO               # Push string "lIO"
       м              # Remove those three as well
        {             # Sort the remaining characters in the string
         œ            # Get a list of all permutations of this string
•F\nmʒØà\ç×н˜=ˆ§kð€³ä‘λ°Ð‘ç«(вÍè\pÌ•
                      # Push compressed integer 1563341720558629316384554749509959660779122984425616460522557465911652079492533
 è                    # Index it into the list of permutations:
                      #  "fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF"
  Åв                  # Convert the integer to this custom base
    A                 # Push the lowercase alphabet
     "BV1db4a1c7ef"   # Push string "BV1db4a1c7ef"
                   r  # Reverse the three values on the stack
                    ‡ # Transliterate the lowercase alphabet to the base-converted
                      # characters in "BV1db4a1c7ef"
                      # (after which the result is output implicitly)

```

**BV to AV**:

```
•1ïÓî•                # Push compressed integer 32111112
      S               # Convert it to a list of digits: [3,2,1,1,1,1,1,2]
       £              # Split the (implicit) input-string into parts of that size
        ι             # Uninterleave it
         θ            # Only keep the last result
          S           # And convert it to a flattened list of characters
           Ƶª         # Push compressed integer 270
             .I       # And take the 270th 0-based permutation
žL¨…lIOм{œ•F\nmʒØà\ç×н˜=ˆ§kð€³ä‘λ°Ð‘ç«(вÍè\pÌ•è
                      # Same as in the AB to BV conversion above,
 Åβ                   # but the other way around (convert from the custom base to integer)
•2G&©I•-              # Subtract 8728348608
        •A³ú[•^       # Bitwise-XOR it with 177451812
               „avì   # Prepend "av"
                      # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•A³ú[•` is `177451812`; `•2G&©I•` is `8728348608`; `•F\nmʒØà\ç×н˜=ˆ§kð€³ä‘λ°Ð‘ç«(вÍè\pÌ•` is `1563341720558629316384554749509959660779122984425616460522557465911652079492533`; `•1ïÓî•` is `32111112`; and `Ƶª` is `270`.

The `1563341720558629316384554749509959660779122984425616460522557465911652079492533` is generated by this Jelly builtin (minus 1, since Jelly uses 1-based indexing and 05AB1E uses 0-based indexing).

# Answer
> 3 votes
# C (gcc), 191 + 181 = 372 bytes

Saved ~~4~~ ~~5~~ ~~8~~ 15 bytes thanks to ceilingcat!!!

# AV to BV

# C (gcc), ~~224~~ \\$\cdots\\$ ~~198~~ 191 bytes

```
r[]=L"BV1__4_1_7";e(a,w)long a,w;{w=(strtol(a+2,0,10)^177451812)+8728348608;for(a=6;a--;w/=58)r["6483:;"[a]-48]="fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF"[w%58];wprintf(r);}

```

Try it online!

# BV to AV

# C (gcc), ~~224~~ \\$\cdots\\$ ~~186~~ 181 bytes

```
char*d="fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF",b;long w;c(char*s){for(w=b=0;b<6;w+=index(d,s["6483:;"[b++]-48])-d)w*=58;printf("av%ld",w-8728348608^177451812);}

```

Try it online!

# Answer
> 2 votes
# Charcoal, 208 bytes

## AV code to BV code, 117 bytes:

```
≔⍘"0|7mγη≔Ｉ✂θ²χ¹θ≔⍘⁺⁻｜θη＆θη⍘!,/>#iγ”\`>⊟∨↖κ2¹W«ε➙⊗MιΦ/⁷Aêμ⁵Ｓ⁶Ｄt÷r≔l⪪≦｜⭆±⊗υ↓1↖Þ»χＺ⁹～”θ≔⁺×f⁻⁶Ｌθθθ⭆BV1db4a1c7ef⎇№βι§θ⌕βιι

```

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

```
≔⍘"0|7mγη

```

Get the constant `177451812` into a variable as we need it twice because we don't have a bitwise XOR builtin.

```
≔Ｉ✂θ²χ¹θ

```

Extract the value in the AV code as a number.

```
≔⍘⁺⁻｜θη＆θη⍘!,/>#iγ”\`>⊟∨↖κ2¹W«ε➙⊗MιΦ/⁷Aêμ⁵Ｓ⁶Ｄt÷r≔l⪪≦｜⭆±⊗υ↓1↖Þ»χＺ⁹～”θ

```

Subtract the bitwise AND from the bitwise OR giving the bitwise XOR, add the offset, then perform custom base conversion using a compressed version of the given string.

```
≔⁺×f⁻⁶Ｌθθθ

```

Pad the string to 6 characters.

```
⭆BV1db4a1c7ef⎇№βι§θ⌕βιι

```

Substitute the characters in the appropriate positions in the BV code.

## BV code to AV code: 91 bytes:

```
≔⍘"0|7mγη≔⁻⍘⭆684921§θ±Ｉι”\`>⊟∨↖κ2¹W«ε➙⊗MιΦ/⁷Aêμ⁵Ｓ⁶Ｄt÷r≔l⪪≦｜⭆±⊗υ↓1↖Þ»χＺ⁹～”⍘!,/>#iγθavＩ⁻｜θη＆θη

```

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

```
≔⍘"0|7mγη

```

Get the constant `177451812` into a variable again.

```
≔⁻⍘⭆684921§θ±Ｉι”\`>⊟∨↖κ2¹W«ε➙⊗MιΦ/⁷Aêμ⁵Ｓ⁶Ｄt÷r≔l⪪≦｜⭆±⊗υ↓1↖Þ»χＺ⁹～”⍘!,/>#iγθ

```

Extract the characters from the appropriate positions of the BV code, perform custom base conversion, and subtract the offset.

```
avＩ⁻｜θη＆θη

```

Print the bitwise XOR prefixed by `av`.

# Answer
> 2 votes
# JavaScript (Node.js), 322 bytes

```
f=(s,[a,b,c,d,e,f]=(g=n=>n?g(n/58|0)+'fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'[n%58]:'')((s.slice(2)^177451812)+8728348608))=>'BV1'+d+b+4+a+1+c+7+e+f
F=s=>'av'+([...'315078'].map(n=>'fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'.search(s[2-~n])).reduce((x,y)=>x*58+y)-8728348608^177451812)

```

Try it online!

A simple and stupid solution. Not so creative. But it at least works.

# Answer
> 2 votes
# JavaScript (Node.js), 295 bytes

```
F=t=>'bv1BD4E1C7A9'.replace(/[9-F]/g,c=>'fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'[((t.slice(2)^177451812)+8728348608)/58**('0x'+c-9)%58|0])
G=s=>'av'+([7,5,9,4,11,12].map(n=>x=x*58+'fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF'.search(s[n])|0,x=16717449)|x^177451812)

```

Try it online!

Thank Arnauld for -7 bytes

# Answer
> 2 votes
# perl -pl (+ bc), 186 + 189 = 375 182 + 187 = 369 bytes

## AV to BV

```
s/^..//;@_=(split//,fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF)[`echo "obase=58;@{[($_^177451812)+8728348608]}"|bc`=~/\d+/g];$_="BV1$_[3]$_[1]4$_[0]1$_[2]7$_[4]$_[5]"

```

Try it online!

This uses `bc` to do the decimal to base-58 conversion.

## BV to AV

```
$n=$x=0;%_=map{$_=>$x++}split//,fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF;@y=@_{/1(.)(.)4(.)1(.)7(.)(.)/};$n=58*$n+$_ for@y[2,1,3,0,4,5];$_=av.(($n-8728348608)^177451812)

```

Try it online!

If you have only 1 line of input, the first 8 bytes can be removed.

Update: Removed 4 + 2 = 6 bytes, because you don't need to quote the strings.

# Answer
> 0 votes
# Prolog, 725 bytes

```
:-use_module(library(clpz)).
:-use_module(library(lists)).
v(A,B):-var(A),var(B).
d(N,D):-v(N,D),!.
d(N,D):-nth0(N,"0123456789",D).
e(N,D):-v(N,D),!.
e(N,D):-nth0(N,"fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF",D).
b(0,_,[0]).
b(1,_,[1]).
b(A,B,C):-A#>1,E#>=0,L#=E+1,(nonvar(C),length(C,L);nonvar(A)),A#<B^(E+1),A#>=B^E,labeling([down],[E]),length(C,L),reverse(C,F),c(A,B,F).
c(0,_,[]).
c(A,B,[C|D]):-A#>0,C#>=0,C#=<B,E#>=0,C#=A mod B,E#=A//B,c(E,B,D).
a([a,v|A],['B','V','1',E,C,'4',B,'1',D,'7',F,G]):-H=[B,C,D,E,F,G],I=177451812,J=8728348608,K#>=0,L#>=0,K#=L xor I+J,L#=(K-J)xor I,O in 1..9,indomain(O),length(A,O),maplist(d,M,A),maplist(e,N,H),b(L,10,M),b(K,58,N),label([L,K]),maplist(d,M,A),maplist(e,N,H).

```

Clear version:

```
:- use_module(library(clpz)).
:- use_module(library(lists)).

v(A, B) :- var(A), var(B).

% Base 10.
d(N, D) :- v(N, D), !. % Keep variable.
d(N, D) :-
    nth0(N, "0123456789", D).

% Base 58.
e(N, D) :- v(N, D), !. % Keep variable.
e(N, D) :-
    nth0(N, "fZodR9XQDSUm21yCkr6zBqiveYah8bt4xsWpHnJE7jL5VG3guMTKNPAwcF", D).

% Base conversion. Base B, Number A, Array C.
b(0, _, [0]).
b(1, _, [1]).
b(A, B, C) :-
    A #> 1,
    nonvar(B),
    E #>= 0,
    L #= E + 1,
    (   nonvar(C), length(C, L)
    ;   nonvar(A)
    ),
    A #< B ^ (E + 1),
    A #>= B ^ E,
    labeling([down], [E]),
    length(C, L),
    reverse(C, F),
    c(A, B, F).

% Required for b.
c(0, _, []).
c(A, B, [C|D]) :-
    A #> 0,
    C #>= 0,
    C #=< B,
    E #>= 0,
    C #= A mod B,
    E #= A // B,
    c(E, B, D).

% Bidirectional decoder.
a([a, v|A], ['B', 'V', '1', E, C, '4', B, '1', D, '7', F, G]) :-
    H = [B, C, D, E, F, G],
    I = 177451812,
    J = 8728348608,
    K #>= 0,
    L #>= 0,
    K #= L xor I + J,
    L #= (K - J) xor I,
    O in 1..9,
    indomain(O),
    length(A, O),
    maplist(d, M, A),
    maplist(e, N, H),
    b(L, 10, M),
    b(K, 58, N),
    label([L, K]),
    maplist(d, M, A),
    maplist(e, N, H).

```

---
Tags: code-golf, conversion
---


title: Brainfuck movement

text:
# Question
Title: Brainfuck movement
A normal Brainfuck program starts out with an array of cells, all containing the number `0`. This program, on the other hand, must be able to run starting with any number `x` in the leftmost cell. The only rule is that at the end of program execution, the "pointed-to" cell must be cell `x`. (The leftmost cell is cell 0).

* Each cell contains a number from 0 to 255, and every cell but the leftmost one starts out with a value of 0.
* There are an infinite number of cells, but none to the left of the leftmost cell.

This is code golf, so the submission using the fewest bytes wins. Good luck!

# Answer
> 4 votes
# 10 bytes

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

```

Try it online!

Move `x` one cell to the right, and decrease it by 1. Repeat until `x` is 0.

# Answer
> 0 votes
# 20 bytes

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

```

Try it online.

This could be made shorter if there were a single cell to the left of cell 0.

---
Tags: code-golf, brainfuck
---


title: Get a middle-ish string

text:
# Question
Title: Get a middle-ish string
You are the first engineer in a hot new startup, Lexographical. Our company is making waves by digitizing and indexing all words, real or not. The core of our product... Our secret sauce... Well, that's why we hired you :)

Because we're bleeding edge, we're enforcing the latest standards. Even the latest ones aren't good enough. We need the ones that haven't been made yet. No language in existence is good enough for us, so you need to use Lexo to write your code (funnily enough, it looks identical to your favorite programming language).

**Your mission...**

Given 2 strings of arbitrary length and composition, return a string that is lexicographically between the 2 strings (i.e. `input_a` \< `output` \< `input_b`). Please use standard lexicographical comparisons.

We want ALL THE STRINGS, so the output doesn't have to resemble either of the inputs (though it might, and that's fine).

Because of legal hot water we're in, we can't actually process inputs longer than 10 characters. The output can be as long as we need it to be.

Inputs will always be printable ASCII characters and may not be in lexicographical order. They are gUaranteed to not be identical strings. Sample inputs and outputs (using Python string comparison):

`Lexo`, `Rules` =\> `M`

`qwerty`, `qwertyuiop` =\> `qwertyu`

`"123"`, `"124"` =\> `"1230"`

Oh yeah, we're running this on very *very* small computers... we're on a tight budget. So the smaller you can make the program, the better!

# Answer
> 1 votes
# JavaScript, 8 bytes

Appends a space to the first string.

```
a=>a+' '

```

# Answer
> 1 votes
# Keg, `-pn`, 5 bytes

```
᠀᠀⑭^,

```

Probably the only valid answer. Same as the 0 byter but it sorts the stack lexically.

# Keg and 05AB1E, 0 bytes

This is a port of the Javascript answer, but instead of appending a space to the string, it appends a newline. A `0`-byte Keg program is simply a cat program on the first input, meaning that it takes the first word and prints it, followed by a newline.

Try it online!

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


title: Plain Hunt Bell-Ringing

text:
# Question
Title: Plain Hunt Bell-Ringing
Your task is to create a plain hunt (a bell ringing pattern) with *n* bells. An example with 6 bells:

```
123456
214365
241635
426153
462513
645231
654321
563412
536142
351624
315264
132546
123456

```

Each number "bounces" off the side of the grid. From Wikipedia:

> Each bell moves one position at each succeeding change, unless they reach the first or last position, when they remain there for two changes then proceed to the other end of the sequence.

In other words, you swap the bells in adjacent pairs, alternating between taking pairs starting from the the first bell and from the second bell. (Thanks to @xnor for this explanation.) You finish in the same order as the start.

This rule be applied to *any* number of bells, taken as input. Standard loopholes are forbidden.

## Test Cases

6

```
123456
214365
241635
426153
462513
645231
654321
563412
536142
351624
315264
132546
123456

```

3

```
123
213
231
321
312
132
123

```

2

```
12
21
21
12

```

1

```
1

```

0: Falls in to "I don't care" situation.

# Answer
# Python 2, 93 bytes

```
lambda n:[[.5+abs((n+j-i*(-1)**(i+j))%(2*n)-n+.5)for j in range(n)]for i in range(2*n+(n>2))]

```

Try it online!

Outputs a list of lists of integer-valued floats.

The map `(i,j) -> j-i*(-1)**(i+j)` is very similar to multiplication in the dihedral group. This isn't a coincidence. If we let \\$a\\$ represent swapping every other element starting from the first, and \\$b\\$ doing so starting from the second, then these generate the dihedral group \\$D\_{2n}\\$ gives by relations \\$a^2 = b^2 =(ab)^n =1 \\$. Note that the sequence we're asked to output has us alternate applying \\$a\\$ and \\$b\\$, and the fact that \\$ (ab)^n =1 \\$ confirms that we return to where we started after \\$2n\\$ total steps.

We can see the dihedral connection more clearly if we extend the top row to \\$2n\\$ elements rather than \\$n\\$, and write it zero-indexed. Doing the alternating swaps as usual gives a pattern like below for \\$n=3\\$. This is almost a multiplication table for the dihedral group \\$D\_{2n}\\$, except that we invert the first group element before multiplying \\$g,h \to g^{-1} h \\$, giving zeroes (identity) on the diagonal \\$g=h\\$.

```
  012345
 +------
0|012345
1|103254
2|430521
3|345012
4|254103
5|521430

```

To return the values back into the range `[0,1,2]`, we need to map back `3->2, 4->1, 5->0`. In the code, surprisingly many characters as spent on the simple-looking mapping doing modular indexing into the palindromic "bouncing" list `[1,2,...,n-1,n,n,n-1,...,2,1]`, We implement this as `.5+abs((n+k)%(2*n)-n+.5)`. The Python 3.8 walrus can save at least 2 bytes, though I haven't optimized it.
> 7 votes

# Answer
## Haskell, 83 bytes

```
f(a:b:c)=b:a:f c
f c=c
q l|a:b<-f l=l:f l:q(a:f b)
g n=take(2*n+sum[1|n>2])$q[1..n]

```

Try it online!
> 4 votes

# Answer
# PHP, 120 bytes

```
for($b=$a=range(1,$argn);print join($b)."
",$a[1]&&!$i||$a!=$b;)for($j=$i++%2;$n=$b[++$j];$b[$j-2]=$n)$b[$j++]=$b[$j-2];

```

Try it online!

```
for(
  $b=$a=range(1,$argn); // set $a and $b to an array of [1...n]
  print join($b)."\n",  // on start of each iteration print $b
  $a[1]&&               // stop when input is 1 (we only print a single 1 for input of 1)
  !$i||                 // allows first iteration to happen since $a==$b on first iteration
  $a!=$b;               // stop when $a and $b are equal again
)
  for(
    $j=$i++%2;          // set $j to 0 or 1 (alternates each time)
    $n=$b[++$j];        // increment $j by one and set $n to
                        //   last number of next pair in $b, stop if it doesn't exist
    $b[$j-2]=$n         // swap one of bells in $b
  )
    $b[$j++]=$b[$j-2];  // increment $j by one and swap one of bells in $b

```
> 3 votes

# Answer
A much nicer approach if I can ignore case 1:

# , 42 bytes

```
[:/:"{i.+/\@|:@,.(2*-/\@i.)|."{[:(,-)i.<<:

```

Try it online!

---

# official , ~~68~~ ~~62~~ 59 bytes

```
[:>[:(]C.~_2<\(}.i.@#))&.>/@:|.\<@:>:@i.,(0;1)$~+:-1#.<&2 3

```

Try it online!

51 bytes if `1` case is allowed to return 2 lines: Try it online!

Another 48 byte solution which fails only case 1

---

## how for official answer

Could likely be golfed more but I was happy with the idea.

Essentially, everything flows from noting that to get from one element to the next, you apply 1 of two cyclic permutations:

For example, in this case of n=6, to get from a row with an even index to the next row you apply:

```
┌───┬───┬───┐
│1 2│3 4│5 6│
└───┴───┴───┘

```

To get from an odd row to an even you apply:

```
┌─┬───┬───┬─┐
│1│2 3│4 5│6│
└─┴───┴───┴─┘

```

Once you set that up, the result is just a right to left scan over those alternating permutations. Everything else is the boring details of constructing the permutations and the list to apply them to.
> 3 votes

# Answer
# Zsh, ~~75~~ 95 bytes

```
s(){echo $a;a=;for x y;a+=($y $x)}
a=({1..$1})
(($1-1))&&repeat $1 s $a&&s '' $a
(($1-2))&&s $a

```

~~Try it online!~~  Try it online!

Defines a function `s` which swaps each pair of arguments and assigns them to `a`. `s` is called once normally `ABCD -> BADC` and then once with an empty element prepended: `ABCD -> ACBD`; repeated `n` times. `s` is called once more at the end, just to print out the array once more.

`echo $a` is used instead of `<<<$a` to suppress the empty element causing extra space.
> 3 votes

# Answer
# Jelly, 25 bytes

```
s2UF
RÇŻÇfƊƭƬmn2$Ṃṭ$⁸>2¤¡

```

A monadic Link accepting a non-negative integer which yields a list of lists of non-negative integers.

**Try it online!** (The footer calls the Link and formats the result as a grid)

### How?

```
s2UF - helper Link: list                e.g. [4, 2, 5, 1, 3]
s2   - split into chunks of length two       [[4, 2], [5, 1], [3]]
  U  - reverse each                          [[2, 4], [1, 5], [3]]
   F - flatten                               [2, 4, 1, 5, 3]

RÇŻÇfƊƭƬmn2$Ṃṭ$⁸>2¤¡ - Main Link: non-negative integer, N
R                    - range = [1,2,...,N]
       Ƭ             - collect up while unique, applying (starting with X = range result):
      ƭ              -   apply previous (default 2) links in turn each time called:
 Ç                   -     1) call helper link as a monad
     Ɗ               -     2) last three links as a monad - i.e. g(X):
  Ż                  -          prefix a zero
   Ç                 -          call helper link as a monad
    f                -          filter keep only those values in X (i.e. remove the zero)
           $         - last two links as a monad:
          2          -   literal two
         n           -   not equal (N)?
        m            - modulo slice (m1 gives every element back,
                                     m0 performs reflection, which is required when N = 2)
                       [m0 reflecting is a very nice behaviour decision by Dennis IMO]
                   ¡ - repeat...
                  ¤  -   ...number of times: nilad followed by link(s) as a nilad:
               ⁸     -                         chain's left argument, N
                >2   -                         greater than 2?
              $      -   ...action: last two links as a monad:
            Ṃ        -                minimum (always [1,2,...,N])
             ṭ       -                tack (appending the final peel for N>2)

```
> 3 votes

# Answer
# Charcoal, 54 bytes

```
ＮθＦθ«Ｊι⁰≔⁻⁶∧‹⁺ι¬﹪ι²θ∨﹪ι²±¹ηＦ⎇‹θ³×θθ⊕⊗θ«✳ηＩ⊕ι≧⁺⁻¬ⅈ⁼⊕ⅈθη

```

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

```
Ｎθ

```

Input `n`.

```
Ｆθ«

```

Loop over each bell.

```
Ｊι⁰

```

Jump to its starting position.

```
≔⁻⁶∧‹⁺ι¬﹪ι²θ∨﹪ι²±¹η

```

Calculate its starting direction. For odd bells this is normally 7 (south east) and for even bells this is normally 5 (south west) but if the last bell its odd then its staring direction is 6 (south).

```
Ｆ⎇‹θ³×θθ⊕⊗θ«

```

Loop over each row, either  for `n<3` or `2n+1` for `n>3`.

```
✳ηＩ⊕ι

```

Print the current bell and move in the current direction.

```
≧⁺⁻¬ⅈ⁼⊕ⅈθη

```

Adjust the direction if the bell has reached the side so that it bounces.
> 2 votes

# Answer
# Perl 6, 52 bytes

```
{$_,|({S:g:p($++%2)/(.)(.)/$1$0/}...$_)}o{[~] 1..$_}

```

Try it online!

### Explanation

```
                                         {[~] 1..$_}  # Concat numbers 1..n
{                                      }o  # Feed into block
 $_,  # Start with first string
                                 ...  # Sequence constructor
      {                         }  # Compute next item by
       S:g         /      /    /   # replacing globally
          :p($++%2)  # starting at alternating positions 0, 1, 0, 1, ...
                    (.)(.)  # any two chars
                           $1$0  # swapped
                                    $_  # Until item equals original string
    |(                                )  # Flatten into result list

```
> 2 votes

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

```
x=>{var m=Enumerable.Range(1,x).ToList();for(int i=0,j=0;i<x*2+1-2/x;j=++i%2)for(Print(m);j<x-1;)(m[j],m[++j])=(m[j],m[~-j++]);}

```

Try it online!
> 1 votes

# Answer
# Jelly, 28 bytes

```
¹©Rµ¬ɼks€2UFµ⁺⁻J$Ð¿;@WẋL’ẸƊƊ

```

Try it online!

A monadic link that takes an integer as its input and returns a list of lists of integers. Could be 16 bytes if only needed to handle numbers 3 and above, and 22 if only 2 and above.
> 1 votes

# Answer
# Python 2, ~~110~~ 104 bytes

```
n=input()
R=range
s=R(1,n+1)
for k in R(n*2-2/n+1):
 print s
 for i in R(k%2,n-1,2):s[i:i+2]=s[i+1],s[i]

```

Try it online!

Full program that prints a list of integers for each "change" in the "hunt".
> 1 votes

# Answer
# JavaScript (ES6), 99 bytes

```
n=>(z=0,g=a=>[a=a.map((v,i)=>v?a[i+=i+z&1||-1]||v:i+1),...z++^2*n^'027'[n]?g(a):[]])([...Array(n)])

```

Try it online!

### Commented

```
n => (                  // n = input
  z = 0,                // z = counter
  g = a => [            // g = recursive function taking the list of bells a[]
    a =                 // update a[] and append it as a new entry
      a.map((v, i) =>   //   for each value v at position i in a[]:
        v ?             //     if v is defined:
          a[            //       take the bell
            i +=        //         at position:
              i + z & 1 //           i + 1 if i + z is odd
              || -1     //           i - 1 if i + z is even
          ]             //
          || v          //       or leave it unchanged if the above value is undefined
        :               //     else:
          i + 1         //       the array is not yet initialized: set the bell to i + 1
      ),                //   end of map()
    ...z++ ^ 2 * n      // we stop when z = 2n, except for
           ^ '027'[n]   // n = 1 (2n xor 2 -> z = 0) and n = 2 (2n xor 7 -> z = 3)
    ?                   // if the above result is not equal to 0:
      g(a)              //   do a recursive call
    :                   // else:
      []                //   stop
  ]                     //
)([...Array(n)])        // initial call to g with a[] = array of n entries

```
> 1 votes

# Answer
# C (gcc), ~~270~~ ~~224~~ ~~206~~ 190 bytes

Not a "winning" answer but a fun challenge.

Thanks @ceilingcat for some good cleanup. Learned something new.

Update: further golfed based on how I now know the game to be played.

Further golfed by @ceilingcat

```
#define w(x)for(i=x;i<n;i++)
#define pb w(0)printf(b+i);puts("");
i,x,n;z(int*b){n=*b;w(0)b[i+n*4]=b[i]=i+49;do{if(n-1)pb;w(x++%2+1)b[i++-1]^=b[i]^=b[i-1]^=b[i];}while(bcmp(b,b+n*4,n*4));pb}

```

Try it online!
> 1 votes

# Answer
# Red, 159 bytes

```
func[n][r: collect[repeat i n[keep i]]repeat i either n < 3[n * n][2 * n + 1][print r:
head r r: skip r i + 1 % 2 until[move r next r(index? r: skip r 2)> n]]]

```

Try it online!

If two `1`s are allowed as a solution for `1`:

# Red, 155 bytes

```
func[n][r: collect[repeat i n[keep i]]b: copy r t: on until[print b if t:
not t[b: next b]until[move b next b(index? b: skip b 2)> n]r = b: head b]print b]

```

Try it online!
> 0 votes

# Answer
# Icon, 119 bytes

```
procedure f(n)
a:="";a||:=1to n&\z;b:=a
n>1&o:=|(0|1)&write(b)&b[o+(k:=seq(1,2)\n)]:=:b[o+k+1]&b==a
write(b);return
end

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 35 bytes

```
≠iL[ˆ¯DÁ2£ËNĀ*#θNÈi2ôëćs2ôsš}ε¸˜}í˜

```

Try it online or verify all test cases.

Not too happy with it.. I have the feeling the duplicated  could be golfed somehow, and some of the workarounds could be more elegant (/shorter). Could be 33 bytes if `[1,1]` instead of `1` is allowed as output; and could be 28 bytes if we'd only had to handle \\$\geq3\\$.

**Explanation (of the 35 bytes version):**

```
≠i              # If the (implicit) input is NOT 1:
  L             #  Create a list in the range [1, (implicit) input]
   [            #  Start an infinite loop:
    ˆ           #   Add the top list to the global array
    ¯D          #   Push the entire global array twice
      Á         #   Rotate the copy once towards the right
       2£       #   Then only leave the first two items
         Ë      #   Check whether those two items are NOT the same
     N          #   Push the current loop-index
      Ā         #   Check whether it is NOT 0 (so not the first iteration)
          *     #   If both checks are truthy:
           #    #    Stop the infinite loop
                #    (after which the TOS global array is output implicitly as result)
     θ          #   Only leave the last list of the global array
      NÈi       #   If the loop-index is even:
         2ô     #    Split the list into parts of size 2
        ë       #   Else (the loop-index is odd):
         ć      #    Extract head; pop and push the remainder-list and first item separated
          s     #    Swap so the remainder-list is at the top of the stack
           2ô   #    Split it into parts of size 2
             s  #    Swap to get the extracted first item again
              š #    And prepend it back in front of the list
        }ε      #   After the if-else: map over the pairs (and potentially loose items):
          ¸     #    Wrap them into a list
           ˜    #    And flatten them
                #   (this is a workaround to wrap multi-digit integers into an inner list,
                #    otherwise an integer like 10 would be reversed to "01"..)
         }í     #   After this map: reverse each inner pair
           ˜    #   And flatten it to a single list again for the next iteration

```
> 0 votes

# Answer
# Ruby -p, 72 bytes

```
puts$_=s=[*?1..$_]*''
puts$_ until s[gsub /\B{#{1&$.+=1}}(.)(.)/,'\2\1']

```

Try it online!

Alternately replaces using the regexps `/\B{0}(.)(.)/` and `/\B{1}(.)(.)/`. The latter matches any two characters other than at the beginning of the string, while the former just matches any two characters--`{0}` means "repeated zero times" turning the `\B` into a no-op.
> 0 votes

# Answer
# Husk, 22 bytes

```
-;1ḟΓ€ḣ`Goṁ↔`C¢Se:1∞2ḣ

```

Try it online!

## Explanation

```
-;1ḟΓ€ḣ`Goṁ↔`C¢Se:1∞2ḣ  Implicit input, say n=5
                     ḣ  Range: [1,2,3,4,5]
                   ∞2   Infinite list of 2s.
               Se       Pair it with
                 :1     prepend 1: [[2,2,2,2..],[1,2,2,2..]]
              ¢         Cycle: [[2,2,2..],[1,2,2..],[2,2,2..],[1,2,2..]..]
       `G               Cumulative reduce this list using the range
                        as a starting point with the following function:
            `C            Split into chunks of given lengths: [[1,2],[3,4],[5]]
         oṁ↔              Reverse each and concatenate: [2,1,4,3,5]
                        Result is infinite list [[1,2,3,4,5],[2,1,4,3,5],[2,4,1,5,3],[4,2,5,1,3]..]
      ḣ                 Prefixes: [[[1,2,3,4,5]],[[1,2,3,4,5],[2,1,4,3,5]]..]
   ḟ                    Find the first one that satisfies this:
    Γ€                    The first element occurs in the tail.
                        The result is the plain hunt, except for n=1, which gives [[1],[1]]
-;1                     Remove an occurrence of [1] to account for it.

```
> 0 votes

---
Tags: code-golf, sequence, permutations
---


# Question
Title: Highest cardinality grouping of contiguous integers with minimum-sum threshold
# Challenge

**Given an array of positive integers and a threshold, the algorithm should output a set of consecutive-element-groupings (subarrays) such that each group/subarray has a *sum greater than the threshold*.**

# Rules

The solution should honor **two additional criteria**:

* be of highest cardinality of the groups (i.e. highest number of groups)
* having the maximum group-sum be as lowest as possible.

# Mathematical Description:

* input array \\$L = \[l\_1, l\_2, ..., l\_n\]\\$
* threshold \\$T\\$

output groups/subarrays \\$G = \[g\_1, g\_2, ..., g\_m\]\\$ where:

* \\$m \leq n\\$
* \\$\bigcap\limits\_{i=1}^m{g\_i}=\varnothing\\$
* \\$\bigcup\limits\_{i=1}^m{g\_i}=L\\$
* if we denote the sum of elements in a group as \\$s\_{g\_i} = \sum\limits\_{l \in g\_i}l\\$, then all groups have sum greater than threshold \\$T\\$. In other words: \\$\underset{g \in G}{\operatorname{min}}{\\{s\_g\\}} \ge T\\$
* if cardinality \\$|g\_i|=k\\$, then \\$g\_i=\[l\_j, ..., l\_{j+k-1}\]\\$ for an arbitrary \\$j\\$ (i.e. all elements are consecutive).
* optimal solution has highest cardinality: \\$|G\_{opt}| \ge \max\left(|G| \right),\\,\\,\forall G\\$
* optimal solution \\$G\_{opt}\\$ has lowest maximum group-sum: \\$\underset{g \in G\_{opt}}{\operatorname{max}}{\\{s\_g\\}} \le \underset{g \in G}{\operatorname{max}}{\\{s\_g\\}}, \\,\\,\\, \forall G\\$

# Assumption

for simplicity, we assume such a solution exists by having: \\$\sum\limits\_{i=1}^n l\_i \ge T\\$

# Example:

**Example input:**

```
L = [1, 4, 12, 6, 20, 10, 11, 3, 13, 12, 4, 4, 5]
T = 12

```

**Example output:**

```
G = {
  '1': [1, 4, 12, 6],
  '2': [20],
  '3': [10, 11],
  '4': [3, 13],
  '5': [12],
  '6': [4, 4, 5]
}

```

# Winning Criteria:

1. Fastest algorithm wins (computational complexity in \\$O\\$ notation).
2. Additionally, there might be situations where an element \\$l\_i \>\\!\\!\> T\\$ is really big, and thus it becomes its own group; causing the maximum subarray sum to be always a constant \\$l\_i\\$ for many potential solutions \\$G\\$.
Therefore, if two potential solutions \\$G\_A\\$ and \\$G\_B\\$ exists, the winning algorithm is the one which results in output that has the **smallest** max-subarray-sum amongst the **non-intersecting groups**.
*In other words*: if we denote \\$G\_{A \cap B}=\\{g\_i: \\,\\, g\_i \in G\_A \cap G\_B\\}\\$, then optimum grouping, \\$G\_{opt}\\$, is the one that has:

$$\underset{g \in \mathbf{G\_{opt}} - G\_{A \cap B}}{\operatorname{max}}{\\{s\_g\\}} = \min\left( \underset{g \in \mathbf{G\_A} - G\_{A \cap B}}{\operatorname{max}}{\\{s\_g\\}}\\, , \\,\\,\underset{g \in \mathbf{G\_{B}} - G\_{A \cap B}}{\operatorname{max}}{\\{s\_g\\}} \right)$$

# Answer
# Java (JDK), 1248 bytes

```
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class TestCG{
	public static void main(String [] args) {
		int [] input = new int[] {1,4,12,6,20,10,11,3,13,12,4,4,5};
		int threshold = 12;
		List<List<Integer>> groups = new ArrayList<>();

		int currentGroupSum = 0;
		int previousGroupSum = 0;

		int maxGroupSum = 0;
		int boundaryValue = 0;
		List<Integer> currentGroup =  new ArrayList<>();

		for(int i=0; i<input.length; i++) {
			currentGroup.add(input[i]);
			currentGroupSum+=input[i];

			if(currentGroupSum>=threshold) {
				if(i<input.length-1) {
					boundaryValue = input[i+1];
				}

				if(currentGroupSum>maxGroupSum) {
					maxGroupSum = currentGroupSum;
				}

                if(currentGroupSum > previousGroupSum && (currentGroupSum - boundaryValue)>=threshold) {

                	groups.get(groups.size()-1).add(boundaryValue);
                	currentGroup.remove(0);
                }

				previousGroupSum = currentGroupSum;

				currentGroupSum = 0;
				groups.add(currentGroup);
				currentGroup = new ArrayList<>();
			}
		}
		System.out.println(groups.size());

		for(List<Integer> group : groups) {
			System.out.println(group);
		}
	}

}

```

Try it online!

Complexity O(n)
> 2 votes

# Answer
# Prolog: \\$ O(n^2) \\$, 785 bytes

```
:- use_module(library(clpz)).
:- use_module(library(lists)).

sum(Ls, S) :-
    sum_(Ls, 0, S).

sum_([], S, S).
sum_([L|Ls], S0, S) :-
    S1 #= L + S0,
    sum_(Ls, S1, S).

solve([], _, _, []).
solve(Ls, T, M, Ms) :-
    T > 0,
    solve_(Ls, T, M, [], Ms1),
    reverse(Ms1, Ms).

solve_([], _, _, Ms, Ms).
solve_(Ls, T, M, Ms0, Ms) :-
    append(As, Bs, Ls),
    As = [_|_],
    sum(As, S),
    S #>= T,
    S #=< M,
    solve_(Bs, T, M, [As|Ms0], Ms).

solution(Ls, T, Ms, M) :-
    solution_(Ls, T, Ms, sup, M).

solution_(Ls, T, Ms, M0, M) :-
    M1 in 0..M0,
    solve(Ls, T, M1, _),
    !,
    clpz:fd_get(M1, from_to(n(M2), _), _),
    M3 #= M2 - 1,
    (   solution_(Ls, T, Ms, M3, M), !
    ;   end_(Ls, T, Ms, M2, M)
    ).
end_(Ls, T, Ms, M, M) :- solve(Ls, T, M, Ms).

```

To run it:

```
?- solution([1, 4, 12, 6, 20, 10, 11, 3, 13, 12, 4, 4, 5], 12, Ms, M).
   Ms = [[1,4,12,6],[20],[10,11],[3,13],[12],[4,4,5]], M = 23.
?-

```
> 0 votes

---
Tags: array, subsequence, fastest-algorithm
---


title: Compute xkcd's Wrong Times Table

text:
# Question
Title: Compute xkcd's Wrong Times Table
The 2020-05-29 xkcd comic showed us the numbers that Randall Munroe feels would be most likely to result from multiplication, other than the correct answers. The table does seem to have some sort of twisted logic to it.

For your convenience, the Wrong Times Table is reproduced here in selectable format:

```
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|     | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 1   | 0   | ½   | 4   | 5   | 6   | 7   | 8   | 9   | 10  | 9   |
| 2   | ½   | 8   | 5   | 6   | 12  | 14  | 12  | 18  | 19  | 22  |
| 3   | 4   | 5   | 10  | 16  | 13  | 12  | 24  | 32  | 21  | 33  |
| 4   | 5   | 6   | 16  | 32  | 25  | 25  | 29  | 36  | 28  | 48  |
| 5   | 6   | 12  | 13  | 25  | 50  | 24  | 40  | 45  | 40  | 60  |
| 6   | 7   | 14  | 12  | 25  | 24  | 32  | 48  | 50  | 72  | 72  |
| 7   | 8   | 12  | 24  | 29  | 40  | 48  | 42  | 54  | 60  | 84  |
| 8   | 9   | 18  | 32  | 36  | 45  | 50  | 54  | 48  | 74  | 56  |
| 9   | 10  | 19  | 21  | 28  | 40  | 72  | 60  | 74  | 72  | 81  |
| 10  | 9   | 22  | 33  | 48  | 60  | 72  | 84  | 56  | 81  | 110 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+

```

Flattened text version without headers:

```
0 ½ 4 5 6 7 8 9 10 9 ½ 8 5 6 12 14 12 18 19 22 4 5 10 16 13 12 24 32 21 33 5 6 16 32 25 25 29 36 28 48 6 12 13 25 50 24 40 45 40 60 7 14 12 25 24 32 48 50 72 72 8 12 24 29 40 48 42 54 60 84 9 18 32 36 45 50 54 48 74 56 10 19 21 28 40 72 60 74 72 81 9 22 33 48 60 72 84 56 81 110

```

# Challenge

Your goal is to write a program or function that accepts two numbers as input and returns the corresponding value of the Wrong Times Table as output.

* The inputs and output can be in any format and data type, as long as it is self-evidently clear which number a given value represents. So representing ½ as the floating point number `0.5` or the string `"1/2"` is fine, but representing it as `-1` is not.
* The inputs can be assumed to be integers in the range 1 to 10 inclusive.
* Standard rules and loophole restrictions apply. The shortest code in bytes wins.

# Example Input and Output

Input:

> 5
> 3

Output:

> 13

# Some possible avenues for golfing

* The table is symmetric across the diagonal.
* There are some patterns in the numbers, e.g. *f*(1, *n*) = *n* \+ 1 for 3 ≤ *n* ≤ 9.
* The values in the table are usually numerically close to the actual multiplication table, so you could store the differences instead.
* The explain xkcd wiki page for this comic has a table showing how each number might have been derived. It may take fewer bits to store these offsets than to store the output numbers directly.

# Answer
> 14 votes
# Python 3, ~~119 ... 110~~ 105 bytes

*-14 bytes thanks to @xnor*

Takes as input an array \\$ a\\$ consisting of the two integers. Outputs the product of the two numbers based on the *Wrong Times Table*. For the case `[1, 2]` or `[2, 1]`, it outputs `.5`.

```
lambda a:b' \0\n \r2 (0*	 $-260\n(H<JH	!0<HT8Qn'[max(a)*~-max(a)//2+min(a)]%126.5

```

Try it online!

## Explanation

We use a compressed string which stores the answers as ASCII values. And since multiplication is commutative, it doesn't matter in which order the two numbers appear, effectively reducing the compression size by a half.

For the `.5` edge case, we assign the character with the ASCII value `127` to it. Then we apply modulo `126.5` to it. This results in `127 % 126.5` returning `.5`, but all the other values stay the same.

# Answer
> 7 votes
# Charcoal, 86 bytes

```
§⪪§⪪”#｜D⟦ⅈＱ\Ｓ4,▷-³◨⟦v≔[Q!ξ№﹪⪪wQＣ.≡r¿I↗⎇B⁸⟧“¿*⪫Y<h\/Ｅ¿M‴$ε¬{a⸿Ｒ⁷⊙ZＮU{Ｕⅈ⪪mδp^｜⎇υＯ”¶⌈θ ⌊θ

```

Try it online! Takes input as a tuple. Explanation:

```
    ”...”       Compressed string of rotated lower left half of table
   ⪪     ¶      Split on newlines
  §       ⌈θ    Cyclically indexed by maximum of both inputs
 ⪪              Split on spaces
§            ⌊θ Cyclically indexed by minimum of both inputs
                Implicitly print

```

Because Charcoal is 0-indexed and the input is 1-indexed I've rotated the diagonal of the lower left half of the table to the left of the first column and then rotated the last row to above the first row so that the cyclic indexing picks up the desired result.

# Answer
> 5 votes
# Jelly,  ~~75~~  71 bytes

```
“µẎḂƬḌƑ®ṢṄḶ+/ḤƇ’BT3+.;Żṃ@“¦¦SȤSḢ⁺ḥȧ⁹ .rOƘ,ṃȯJƓṄƭ3ƝṁṫY-ŻḂƇS|~Ƭø’
ṀḶS+Ṃị¢

```

A monadic Link accepting a pair of integers in \\$\[1..10\]\\$ which yields a number.

**Try it online!**

### How?

```
“...’BT3+.;Żṃ@“...’ - Link 1, get lower left of table as a flat list: no arguments
“...’               - a large number in base 250
     B              - convert to binary
      T             - truthy indices
       3+           - add three to them all -> all distinct values except 0 and 0.5)
         .;         - prepend a 0.5
           Ż        - prepend a zero -> all 37 distinct values
              “...’ - a large number in base 250
            ṃ@      - convert the large number to base 37 using the values as the digits
                      -> [0, 0.5, 8, 4, 5, 10, 5, 6, 16, 32, 6, 12, 13, 25, 50, 7, 14, 12, 25, 24, 32, 8, 12, 24, 29, 40, 48, 42, 9, 18, 32, 36, 45, 50, 54, 48, 10, 19, 21, 28, 40, 72, 60, 74, 72, 9, 22, 33, 48, 60, 72, 84, 56, 81, 110]

ṀḶS+Ṃị¢ - Link, get answer: list of two integers in [1..10], [a,b]
Ṁ       - maximum ([a,b])
 Ḷ      - lowered range -> [0,1,...,max(a,b)-1]
  S     - sum these up
    Ṃ   - minimum ([a,b])
   +    - add
      ¢ - call last Link (2) as a nilad -> lower left of table as a flat list
     ị  - index into

```

# Answer
> 3 votes
# 05AB1E, 100 bytes

-2 thanks to Kevin Cruijssen.

```
•k?-…ÚêQïBJÿ}Å0ß7E'ûcŒa’н
[α¡¥jεĆ3fΣòZεgǝ/ζân[Qx¯#g)zòš¤¥Ägq)†c³±!Ãæwª“‹í«“ε®™â©₂ÿQ`•ƵAв1;š¬9ǝ0šs<Jè

```

Try it online!

# 05AB1E, 102 bytes

The number `2` never appears in the multiplication table, so I used it to compress the list of the numbers.

```
•AjĆмÁмyÌÁÅÿ‰™ªŸ∞mÇ,—.¿b!:ý₆¥p¶ço₃w`2å,3‚ĆžáààÄd±íŠH¢Xζ±-ε₁ÎZ₆ºλΓm.Óc9˜}‘UÔœ`Ÿā£ƒn¨£T•111в2¸1;¸‡0šs<Jè

```

Try it online!

## Explanation

<pre><code>•AjĆмÁмyÌÁÅÿ‰™ªŸ∞mÇ,—.¿b!:ý₆¥p¶ço₃w`2å,3‚ĆžáààÄd±íŠH¢Xζ±-ε₁ÎZ₆ºλΓm.Óc9˜}‘UÔœ`Ÿā£ƒn¨£T•111в

The huge compressed table

2¸1;¸‡ Translate all 2's into 0.5's
0š     Prepend a 0 (which is removed during base conversion)
s      Swap up the list of indices.
<      Decrement both indices.
J      Join these indices into a single number.
è      Index into the table.
```
</code></pre>

# Answer
> 2 votes
# JavaScript, ~~114~~ 113 bytes

Input as `f(1)(2)`. Port of @dingledooper's Python 3 answer.

```
a=>b=>` \0
 \r2 (0*	 $-260\n(H<JH	!0<HT8Qn`.charCodeAt((M=a>b?a:b)*~-M/2+(a<b?a:b))%126.5

```

Try it online!

---
Tags: code-golf, number, arithmetic
---