Background

A practical number is a positive integer N such that all smaller positive integers can be represented as sums of distinct divisors of N. For example, 12 is a practical number because all the numbers from 1 to 11 can be expressed as sums of the divisors of 12, which are 1, 2, 3, 4, and 6. (Wikipedia.) However, 10 is not a practical number, because 4 and 9 cannot be expressed as a sum of 1, 2, and 5. For more detailed explanation and examples, see this recent Numberphile video.

Challenge

Write a function that returns whether a given positive integer is a practical number.

practical(1) => true
practical(2) => true
practical(3) => false
practical(10) => false
practical(12) => true

You should be able to handle numbers up to 10,000 efficiently. The sum of all practical numbers up to 10,000 inclusive is 6,804,107. Test your code by verifying this value.

Optional bonus challenge

Consider the numbers X in the range 1 to 10,000 inclusive. The sum of all X such that 10^19 + X is a practical number is 1,451,958. Find the sum of all X such that 10^20 + X is a practical number. I found the section Characterization of practical numbers in the Wikipedia article useful here.

I do not have any plans to resume posting here regularly. I just saw the Numberphile video and thought it would make a good challenge.

Challenge

Assign every lowercase letter a value, from 1 for a to 26 for z. Given a string of lowercase letters, find the sum of the values of the letters in the string.

lettersum("") => 0
lettersum("a") => 1
lettersum("z") => 26
lettersum("cab") => 6
lettersum("excellent") => 100
lettersum("microspectrophotometries") => 317

Optional bonus challenges

Use the enable1 word list for the optional bonus challenges.

1. microspectrophotometries is the only word with a letter sum of 317. Find the only word with a letter sum of 319.
2. How many words have an odd letter sum?
3. There are 1921 words with a letter sum of 100, making it the second most common letter sum. What letter sum is most common, and how many words have it?
4. zyzzyva and biodegradabilities have the same letter sum as each other (151), and their lengths differ by 11 letters. Find the other pair of words with the same letter sum whose lengths differ by 11 letters.
5. cytotoxicity and unreservedness have the same letter sum as each other (188), and they have no letters in common. Find a pair of words that have no letters in common, and that have the same letter sum, which is larger than 188. (There are two such pairs, and one word appears in both pairs.)
6. The list of word { geographically, eavesdropper, woodworker, oxymorons } contains 4 words. Each word in the list has both a different number of letters, and a different letter sum. The list is sorted both in descending order of word length, and ascending order of letter sum. What's the longest such list you can find?

(This challenge is a repost of Challenge #52 [easy], originally posted by u/rya11111 in May 2012.)

It's been fun getting a little activity going in here these last 13 weeks. However, this will be my last post to this subreddit for the time being. Here's hoping another moderator will post some challenges soon!

Example

Consider this 5x5 matrix of numbers:

123456789   752880530   826085747  576968456   721429729
173957326   1031077599  407299684  67656429    96549194
1048156299  663035648   604085049  1017819398  325233271
942914780   664359365   770319362  52838563    720059384
472459921   662187582   163882767  987977812   394465693

If you select 5 elements from this matrix such that no two elements come from the same row or column, what is the smallest possible sum? The answer in this case is 1099762961 (123456789 + 96549194 + 663035648 + 52838563 + 163882767).

Challenge

Find the minimum such sum when selecting 20 elements (one from each row and column) of this 20x20 matrix. The answer is a 10-digit number whose digits sum to 35.

There's no strict runtime requirement, but you must actually run your program all the way through to completion and get the right answer in order to qualify as a solution: a program that will eventually give you the answer is not sufficient.

Optional Bonus

What's the smallest sum you can find for this 97x97 matrix? It's okay to give a result that's not optimal in this case. If you want to prove that you found a certain sum, you can you post the indices of each element you selected from each row in order. For the 5x5 example, for instance, you could post [0,4,1,3,2].

(This challenge is a repost of Challenge #67 [difficult], originally posted by u/oskar_s in June 2012. See that post for the formula to algorithmically generate the matrices if you prefer to do it that way.)

For the purpose of today's challenge, a Roman numeral is a non-empty string of the characters M, D, C, L, X, V, and I, each of which has the value 1000, 500, 100, 50, 10, 5, and 1. The characters are arranged in descending order, and the total value of the numeral is the sum of the values of its characters. For example, the numeral MDCCXXVIIII has the value 1000 + 500 + 2x100 + 2x10 + 5 + 4x1 = 1729.

This challenge uses only additive notation for roman numerals. There's also subtractive notation, where 9 would be written as IX. You don't need to handle subtractive notation (but you can if you want to, as an optional bonus).

Given two Roman numerals, return whether the first one is less than the second one:

numcompare("I", "I") => false
numcompare("I", "II") => true
numcompare("II", "I") => false
numcompare("V", "IIII") => false
numcompare("MDCLXV", "MDCLXVI") => true
numcompare("MM", "MDCCCCLXXXXVIIII") => false

You only need to correctly handle the case where there are at most 1 each of D, L, and V, and at most 4 each of C, X, and I. You don't need to validate the input, but you can if you want. Any behavior for invalid inputs like numcompare("V", "IIIIIIIIII") is fine - true, false, or error.

Try to complete the challenge without actually determining the numerical values of the inputs.

(This challenge is a repost of Challenge #66 [Easy], originally posted by u/rya11111 in June 2012. Roman numerals have appeared in several previous challenges.)

Scenario

This is a pretty common problem. You may have seen it before.

You work for a mobile phone developer known for their robust design. The marketing division is working on a slogan for the latest model: "Able to survive a K-meter drop!". They just need to know the largest possible whole number value of K they can truthfully claim. Someone has already dropped one from 101 meters up and it broke, so they know the largest possible value is somewhere between 0 and 100 inclusive.

Here's where you come in. You must find the value of K such that a phone will not break if dropped from K meters, but will break if dropped from K+1 meters. For the purpose of this challenge, these tests are completely reliable, so a single test at both K and K+1 meters is enough to establish this. Also, as long as a phone survives the drop, it suffers no damage whatsoever and can be reused in subsequent tests. Also, dropping a phone that's already broken gives you no information.

Your boss gives you a prototype and tells you to go rent the 100-meter tower nearby and find K. The tower owner needs to know how long you'll be renting the tower for, and you rent by the minute, so assuming each trial takes the same amount of time, you need to know the maximum number of trials you'll need, without knowing the value of K. You realize you'll need to rent it long enough to conduct 100 trials, one for each floor. This is because you need to conduct one trial 1 meter up, then 2 meters up, and so on up to 100. If you skip any, then it's possible you won't know the exact value of K before the phone breaks. And then if K = 100, this strategy will require 100 trials.

You tell your boss, who says it's too expensive to rent the tower for 100 tests. Your boss asks, what's the maximum number of trials you'll need if you have two phone prototypes? After some work, you find the answer is 14. Can you see how to find this number? There are many explanations online that can help, like this one. Feel free to read up on this problem if you don't understand the general approach.

If you have three phones, you only need a maximum of 9 trials.

Challenge

Given N, the number of phone prototypes you have, and H, the maximum height that needs to be tested, determine the maximum number of trials required by an optimal strategy to determine K.

phonedrop(1, 100) => 100
phonedrop(2, 100) => 14
phonedrop(3, 100) => 9
phonedrop(1, 1) => 1
phonedrop(2, 456) => 30
phonedrop(3, 456) => 14
phonedrop(4, 456) => 11
phonedrop(2, 789) => 40
phonedrop(3, 789) => 17
phonedrop(4, 789) => 12

You should be able to at least handle values of H up to 999.

Optional bonus

With an unlimited number of phones (N = infinity), it takes a maximum of 27 trials to find K when H = 123456789. Find the smallest N such that phonedrop(N, 123456789) = 27.

(This challenge is a repost of Challenge #68 [intermediate], originally posted by u/rya11111 in June 2012.)

This challenge is inspired by nonogram puzzles, but you don't need to be familiar with these puzzles in order to complete the challenge.

A binary array is an array consisting of only the values 0 and 1. Given a binary array of any length, return an array of positive integers that represent the lengths of the sets of consecutive 1's in the input array, in order from left to right.

nonogramrow([]) => []
nonogramrow([0,0,0,0,0]) => []
nonogramrow([1,1,1,1,1]) => [5]
nonogramrow([0,1,1,1,1,1,0,1,1,1,1]) => [5,4]
nonogramrow([1,1,0,1,0,0,1,1,1,0,0]) => [2,1,3]
nonogramrow([0,0,0,0,1,1,0,0,1,0,1,1,1]) => [2,1,3]
nonogramrow([1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]) => [1,1,1,1,1,1,1,1]

As a special case, nonogram puzzles usually represent the empty output ([]) as [0]. If you prefer to do it this way, that's fine, but 0 should not appear in the output in any other case.

(This challenge is based on Challenge #59 [intermediate], originally posted by u/oskar_s in June 2012. Nonograms have been featured multiple times on r/dailyprogrammer since then (search).)

If you're not familiar with some of the background topics for today's challenge, you'll need to do some reading on your own. Feel free to ask if you're lost, but try to figure it out yourself first. This is a difficult challenge.

Implement the RSA key generation process following the specification on Wikipedia, or some other similar specification. Randomly generate 256-bit or larger values for p and q, using the Fermat primality test or something similar. Use e = 65537. Provide functions to encrypt and decrypt a whole number representing a message, using your selected n. Verify that when you encrypt and then decrypt the input 12345, you get 12345 back.

It's recommended that you use a large-number library for this challenge if your language doesn't support big integers.

(This is a repost of Challenge #60 [difficult], originally posted by u/rya11111 in June 2012.)

The country of Examplania has coins that are worth 1, 5, 10, 25, 100, and 500 currency units. At the Zeroth Bank of Examplania, you are trained to make various amounts of money by using as many ¤500 coins as possible, then as many ¤100 coins as possible, and so on down.

For instance, if you want to give someone ¤468, you would give them four ¤100 coins, two ¤25 coins, one ¤10 coin, one ¤5 coin, and three ¤1 coins, for a total of 11 coins.

Write a function to return the number of coins you use to make a given amount of change.

change(0) => 0
change(12) => 3
change(468) => 11
change(123456) => 254

(This is a repost of Challenge #65 [easy], originally posted by u/oskar_s in June 2012.)

Warmup

Implement the flipfront function. Given an array of integers and a number n between 2 and the length of the array (inclusive), return the array with the order of the first n elements reversed.

flipfront([0, 1, 2, 3, 4], 2) => [1, 0, 2, 3, 4]
flipfront([0, 1, 2, 3, 4], 3) => [2, 1, 0, 3, 4]
flipfront([0, 1, 2, 3, 4], 5) => [4, 3, 2, 1, 0]
flipfront([1, 2, 2, 2], 3) => [2, 2, 1, 2]

Optionally, as an optimization, modify the array in-place (in which case you don't need to return it). It's also fine to have the array be a global variable or member variable, in which case you only need to pass in the argument n.

Challenge

Given an array of integers, sort the array (smallest to largest) using the flipfront function on the entire array. For example, the array:

[3, 1, 2, 1]

may be sorted with three calls to flipfront:

flipfront([3, 1, 2, 1], 4) => [1, 2, 1, 3]
flipfront([1, 2, 1, 3], 2) => [2, 1, 1, 3]
flipfront([2, 1, 1, 3], 3) => [1, 1, 2, 3]

Make sure you correctly handle elements that appear more than once in the array!

You may not modify the array by any other means, but you may examine it however you want. You can even make a copy of the array and manipulate the copy, including sorting it using some other algorithm.

Optional bonus (hard!)

Try to minimize the number of times you call flipfront while sorting. Note that this is different from minimizing the runtime of your program.

How many flipfront calls do you require to sort this list of 10,000 integers? My record is 11,930. Can you do better?

(This is a repost of Challenge #63 [intermediate], originally posted by u/oskar_s in June 2012.)

Background

The ABACABA sequence is defined as follows: the first iteration is the first letter of the alphabet (a). To form the second iteration, you take the second letter (b) and put the first iteration (just a in this case) before and after it, to get aba. For each subsequent iteration, place a copy of the previous iteration on either side of the next letter of the alphabet.

Here are the first 5 iterations of the sequence:

a
aba
abacaba
abacabadabacaba
abacabadabacabaeabacabadabacaba

The 26th and final iteration (i.e. the one that adds the z) is 67,108,863 characters long. If you use one byte for each character, this takes up just under 64 megabytes of space.

Challenge

Write a program to print the 26th iteration of the ABACABA sequence.

If it's easier for you, it's also fine to print one character per line, instead of all the characters on a single line.

Just printing the output can take a few minutes, depending on your setup. Feel free to test it out on something smaller instead, like the 20th iteration, which is only about 1 megabyte.

Optional bonus

Complete the challenge using O(n) memory, where n is the iteration number.

If you don't know what that means, here's another way to say it that's roughly equivalent in this case. You can have as many variables as you want, but they must each hold either a single number or character, or a structure (list, vector, dict, string, map, tree, etc.) whose size never gets much larger than 26. If a function calls itself recursively, the call stack must also be limited to a depth of about 26. (This is definitely an oversimplification, but that's the basic idea. Feel free to ask if you want to know about whether any particular approach uses O(n) memory.)

(This is a repost of Challenge #56 [easy], originally posted by u/oskar_s in May 2012.)

Warmup

Given a number n, determine the number of times the digit "1" appears if you write out all numbers from 1 to n inclusive.

f(1) = 1
f(5) = 1
f(10) = 2
f(20) = 12
f(1234) = 689
f(5123) = 2557
f(70000) = 38000
f(123321) = 93395
f(3^35) = 90051450678399649

You should be able to handle large inputs like 3^(35) efficiently, meaning much faster than iterating over all numbers from 1 to n. Find f(5^(20)) before posting your solution. The answer is 15 digits long and the sum of its digits is 74.

Challenge

f(35199981) = 35199981. Efficiently find the sum of all n such that f(n) = n. This should take a fraction of a second, depending on your programming language.

The answer is 11 digits long and the sum of its digits is 53.

(This is a repost of Challenge #45 [difficult], originally posted by u/oskar_s in April 2012. Check that post for hints and more detail.)

Background

For the purpose of today's challenge, the Monty Hall scenario goes like this:

1. There are three closed doors, labeled #1, #2, and #3. Monty Hall randomly selects one of the three doors and puts a prize behind it. The other two doors hide nothing.
2. A contestant, who does not know where the prize is, selects one of the three doors. This door is not opened yet.
3. Monty chooses one of the three doors and opens it. The door that Monty opens (a) does not hide the prize, and (b) is not the door that the contestant selected. There may be one or two such doors. If there are two, Monty randomly selects one or the other.
4. There are now two closed doors, the one the contestant selected in step 2, and one they didn't select. The contestant decides whether to keep their original choice, or to switch to the other closed door.
5. The contestant wins if the door they selected in step 4 is the same as the one Monty put a prize behind in step 1.

Challenge

A contestant's strategy is given by their choices in steps 2 and 4. Write a program to determine the success rate of a contestant's strategy by simulating the game 1000 times and calculating the fraction of the times the contestant wins. Determine the success rate for these two contestants:

Alice chooses door #1 in step 2, and always sticks with door #1 in step 4.

Bob chooses door #1 in step 2, and always switches to the other closed door in step 4.

Optional bonus

Find success rates for these other contestants:

Carol chooses randomly from the available options in both step 2 and step 4.

Dave chooses randomly in step 2, and always sticks with his door in step 4.

Erin chooses randomly in step 2, and always switches in step 4.

Frank chooses door #1 in step 2, and switches to door #2 if available in step 4. If door #2 is not available because it was opened, then he stays with door #1.

Gina always uses either Alice's or Bob's strategy. She remembers whether her previous strategy worked and changes it accordingly. On her first game, she uses Alice's strategy. Thereafter, if she won the previous game, then she sticks with the same strategy as the previous game. If she lost the previous game, then she switches (Alice to Bob or Bob to Alice).

It's possible to calculate all of these probabilities without doing any simulation, of course, but today's challenge is to find the fractions through simulation.

(This is a repost of Challenge #49 [easy], originally posted by u/oskar_s in May 2012.)

A palindrome is a whole number that's the same when read backward in base 10, such as 12321 or 9449.

Given a positive whole number, find the smallest palindrome greater than the given number.

nextpal(808) => 818
nextpal(999) => 1001
nextpal(2133) => 2222

For large inputs, your solution must be much more efficient than incrementing and checking each subsequent number to see if it's a palindrome. Find nextpal(3^(39)) before posting your solution. Depending on your programming language, it should take a fraction of a second.

(This is a repost of Challenge #58 [intermediate], originally posted by u/oskar_s in May 2012.)

Warmup

Given a lowercase letter and a number between 0 and 26, return that letter Caesar shifted by that number. To Caesar shift a letter by a number, advance it in the alphabet by that many steps, wrapping around from z back to a:

warmup('a', 0) => 'a'
warmup('a', 1) => 'b'
warmup('a', 5) => 'f'
warmup('a', 26) => 'a'
warmup('d', 15) => 's'
warmup('z', 1) => 'a'
warmup('q', 22) => 'm'

Hint: taking a number modulo 26 will wrap around from 25 back to 0. This is commonly represented using the modulus operator %. For example, 29 % 26 = 3. Finding a way to map from the letters a-z to the numbers 0-25 and back will help.

Challenge

Given a string of lowercase letters and a number, return a string with each letter Caesar shifted by the given amount.

caesar("a", 1) => "b"
caesar("abcz", 1) => "bcda"
caesar("irk", 13) => "vex"
caesar("fusion", 6) => "layout"
caesar("dailyprogrammer", 6) => "jgorevxumxgsskx"
caesar("jgorevxumxgsskx", 20) => "dailyprogrammer"

Hint: you can use the warmup function as a helper function.

Optional bonus 1

Correctly handle capital letters and non-letter characters. Capital letters should also be shifted like lowercase letters, but remain capitalized. Leave non-letter characters, such as spaces and punctuation, unshifted.

caesar("Daily Programmer!", 6) => "Jgore Vxumxgsskx!"

If you speak a language that doesn't use the 26-letter A-Z alphabet that English does, handle strings in that language in whatever way makes the most sense to you! In English, if a string is encoded using the number N, you can decode it using the number 26 - N. Make sure that for your language, there's some similar way to decode strings.

Optional bonus 2

Given a string of English text that has been Caesar shifted by some number between 0 and 26, write a function to make a best guess of what the original string was. You can typically do this by hand easily enough, but the challenge is to write a program to do it automatically. Decode the following strings:

Zol abyulk tl puav h ulda.

Tfdv ef wlikyvi, wfi uvrky rnrzkj pfl rcc nzky erjkp, szx, gfzekp kvvky.

Qv wzlmz bw uiqvbiqv iqz-axmml dmtwkqbg, i aeittwe vmmla bw jmib qba eqvoa nwzbg-bpzmm bquma mdmzg amkwvl, zqopb?

One simple way is by using a letter frequency table. Assign each letter in the string a score, with 3 for a, -1 for b, 1 for c, etc., as follows:

3,-1,1,1,4,0,0,2,2,-5,-2,1,0,2,3,0,-6,2,2,3,1,-1,0,-5,0,-7

The average score of the letters in a string will tell you how its letter distribution compares to typical English. Higher is better. Typical English will have an average score around 2, and strings of random letters will have an average score around 0. Just test out each possible shift for the string, and take the one with the highest score. There are other good ways to do it, though.

(This challenge is based on Challenge #47 [easy], originally posted by u/oskar_s in May 2012.)

Today's challenge comes from a recent Mathologer video.

Background

There are 7 ways to partition the number 5 into the sum of positive integers:

5 = 1 + 4 = 1 + 1 + 3 = 2 + 3 = 1 + 2 + 2 = 1 + 1 + 1 + 2 = 1 + 1 + 1 + 1 + 1

Let's express this as p(5) = 7. If you write down the number of ways to partition each number starting at 0 you get:

p(n) = 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, ...

By convention, p(0) = 1.

Challenge

Compute p(666). You must run your program all the way through to completion to meet the challenge. To check your answer, p(666) is a 26-digit number and the sum of the digits is 127. Also, p(66) = 2323520.

You can do this using the definition of p(n) above, although you'll need to be more clever than listing all possible partitions of 666 and counting them. Alternatively, you can use the formula for p(n) given in the next section.

If your programming language does not handle big integers easily, you can instead compute the last 6 digits of p(666).

Sequence formula

If you wish to see this section in video form, it's covered in the Mathologer video starting at 9:35.

The formula for p(n) can be recursively defined in terms of smaller values in the sequence. For example,

p(6) = p(6-1) + p(6-2) - p(6-5)
    = p(5) + p(4) - p(1)
    = 7 + 5 - 1
    = 11

In general:

p(n) =
    p(n-1) +
    p(n-2) -
    p(n-5) -
    p(n-7) +
    p(n-12) +
    p(n-15) -
    p(n-22) -
    p(n-26) + ...

While the sequence is infinite, p(n) = 0 when n < 0, so you stop when the argument becomes negative. The first two terms of this sequence (p(n-1) and p(n-2)) are positive, followed by two negative terms (-p(n-5) and -p(n-7)), and then it repeats back and forth: two positive, two negative, etc.

The numbers that get subtracted from the argument form a second sequence:

1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, ...

This second sequence starts at 1, and the difference between consecutive values in the sequence (2-1, 5-2, 7-5, 12-7, ...) is a third sequence:

1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, ...

This third sequence alternates between the sequence 1, 2, 3, 4, 5, 6, ... and the sequence 3, 5, 7, 9, 11, 13, .... It's easier to see if you write it like this:

1,    2,    3,    4,    5,     6,     7,
   3,    5,    7,    9,    11,    13,    ...

Okay? So using this third sequence, you can generate the second sequence above, which lets you implement the formula for p(n) in terms of smaller p values.

Optional Bonus

How fast can you find the sum of the digits of p(666666).

Today's challenge is to implement the solution to a well-known math puzzle involving prisoners and a chessboard. I won't state the puzzle or give the solution here, but you can find many writeups online:

• Yet another prisoner puzzle blog post
• Impossible Escape? blog post
• The Almost Impossible Chessboard Puzzle video on Stand-Up Maths: 32 minutes

You need to know the solution for today's challenge, but you're welcome to look it up, either in those links or others. If you try to find the solution yourself, be warned it's pretty hard!

Challenge

First, assume that there exists a function flip that takes a series of 64 bits (0 or 1) and a number from 0 to 63. This function returns the same series of bits with the corresponding bit flipped. e.g.:

flip([0, 0, 0, 0, ...], 2) => [0, 0, 1, 0, ...]
flip([0, 1, 0, 1, ...], 1) => [0, 0, 0, 1, ...]

Now, you need to write two functions.

Function prisoner1 takes two inputs: a series S of 64 bits, and a number X from 0 to 63 (inclusive). It returns a number Y from 0 to 63.

Function prisoner2 takes one input: a series T of 64 bits. It returns a number from 0 to 63.

Now, you must make it so that if you flip S using the output of prisoner1 and pass the result to prisoner2, you get back the number X. Put another way, the following function must return True for every possible valid input S and X.

def solve(S, X):
    Y = prisoner1(S, X)
    T = flip(S, Y)
    return prisoner2(T) == X

Essentially, prisoner1 is encoding the value X into the sequence with a single flip, and prisoner2 is decoding it. In the puzzle statement, X is the location of the key, Y is the coin that gets flipped, S is the starting state of the board, and T is the state after the flip occurs.

Good luck!

For the purpose of this challenge, a k-ary necklace of length n is a sequence of n letters chosen from k options, e.g. ABBEACEEA is a 5-ary necklace of length 9. Note that not every letter needs to appear in the necklace. Two necklaces are equal if you can move some letters from the beginning to the end to make the other one, otherwise maintaining the order. For instance, ABCDE is equal to DEABC. For more detail, see challenge #383 Easy: Necklace matching.

Today's challenge is, given k and n, find the number of distinct k-ary necklaces of length n. That is, the size of the largest set of k-ary necklaces of length n such that no two of them are equal to each other. You do not need to actually generate the necklaces, just count them.

For example, there are 24 distinct 3-ary necklaces of length 4, so necklaces(3, 4) is 24. Here they are:

AAAA  BBBB  CCCC
AAAB  BBBC  CCCA
AAAC  BBBA  CCCB
AABB  BBCC  CCAA
ABAB  BCBC  CACA
AABC  BBCA  CCAB
AACB  BBAC  CCBA
ABAC  BCBA  CACB

You only need to handle inputs such that k^n < 10,000.

necklaces(2, 12) => 352
necklaces(3, 7) => 315
necklaces(9, 4) => 1665
necklaces(21, 3) => 3101
necklaces(99, 2) => 4950

The most straightforward way to count necklaces is to generate all k^n patterns, and deduplicate them (potentially using your code from Easy #383). This is an acceptable approach for this challenge, as long as you can actually run your program through to completion for the above examples.

Optional optimization

A more efficient way is with the formula:

necklaces(k, n) = 1/n * Sum of (phi(a) k^b)
    for all positive integers a,b such that a*b = n.

For example, the ways to factor 10 into two positive integers are 1x10, 2x5, 5x2, and 10x1, so:

necklaces(3, 10)
    = 1/10 (phi(1) 3^10 + phi(2) 3^5 + phi(5) 3^2 + phi(10) 3^1)
    = 1/10 (1 * 59049 + 1 * 243 + 4 * 9 + 4 * 3)
    = 5934

phi(a) is Euler's totient function, which is the number of positive integers x less than or equal to a such that the greatest common divisor of x and a is 1. For instance, phi(12) = 4, because 1, 5, 7, and 11 are coprime with 12.

An efficient way to compute phi is with the formula:

phi(a) = a * Product of (p-1) / Product of (p)
    for all distinct prime p that divide evenly into a.

For example, for a = 12, the primes that divide a are 2 and 3. So:

phi(12) = 12 * ((2-1)*(3-1)) / (2*3) = 12 * 2 / 6 = 4

If you decide to go this route, you can test much bigger examples.

necklaces(3, 90) => 96977372978752360287715019917722911297222
necklaces(123, 18) => 2306850769218800390268044415272597042
necklaces(1234567, 6) => 590115108867910855092196771880677924
necklaces(12345678910, 3) => 627225458787209496560873442940

If your language doesn't easily let you handle such big numbers, that's okay. But your program should run much faster than O(k^(n)).

Challenge

Imagine a necklace with lettered beads that can slide along the string. Here's an example image. In this example, you could take the N off NICOLE and slide it around to the other end to make ICOLEN. Do it again to get COLENI, and so on. For the purpose of today's challenge, we'll say that the strings "nicole", "icolen", and "coleni" describe the same necklace.

Generally, two strings describe the same necklace if you can remove some number of letters from the beginning of one, attach them to the end in their original ordering, and get the other string. Reordering the letters in some other way does not, in general, produce a string that describes the same necklace.

Write a function that returns whether two strings describe the same necklace.

Examples

same_necklace("nicole", "icolen") => true
same_necklace("nicole", "lenico") => true
same_necklace("nicole", "coneli") => false
same_necklace("aabaaaaabaab", "aabaabaabaaa") => true
same_necklace("abc", "cba") => false
same_necklace("xxyyy", "xxxyy") => false
same_necklace("xyxxz", "xxyxz") => false
same_necklace("x", "x") => true
same_necklace("x", "xx") => false
same_necklace("x", "") => false
same_necklace("", "") => true

Optional Bonus 1

If you have a string of N letters and you move each letter one at a time from the start to the end, you'll eventually get back to the string you started with, after N steps. Sometimes, you'll see the same string you started with before N steps. For instance, if you start with "abcabcabc", you'll see the same string ("abcabcabc") 3 times over the course of moving a letter 9 times.

Write a function that returns the number of times you encounter the same starting string if you move each letter in the string from the start to the end, one at a time.

repeats("abc") => 1
repeats("abcabcabc") => 3
repeats("abcabcabcx") => 1
repeats("aaaaaa") => 6
repeats("a") => 1
repeats("") => 1

Optional Bonus 2

There is exactly one set of four words in the enable1 word list that all describe the same necklace. Find the four words.

Given the numbering of a crossword puzzle's clues, find its grid.

Background

For the purpose of today's challenge, a standard American crossword grid (like you would typically find in the New York Times) is an odd-dimension square grid of black and white squares with the following requirements:

1. The grid has 180 degree rotational symmetry.
2. The white squares form a single connected component. Squares are connected horizontally or vertically.
3. Every word is at least 3 letters long. A word is a horizontal (Across) or vertical (Down) run of white squares.
4. Every white square is checked, meaning it appears in both an Across word and a Down word. (Equivalently, there are no 1-letter words either.)

Here are some examples of valid and invalid grids, using . for white squares and # for black squares.

Some of the squares in the crossword grid are numbered (here's an example if you're not familiar with crosswords). The numbers that appear in the grid are determined by the layout of black and white squares in the grid as follows:

The first white square in each word is numbered, starting at 1, then 2, 3, etc. "First" here means the leftmost square for Across clues, and the topmost square for Down clues. If a square is the first square in both an Across word and a Down word, it only gets one number. The numbering starts at the top left and goes left to right and then top to bottom.

The set of Across word numbers is the numbers in the squares that start Across clues, and the set of Down word numbers is the numbers in the squares that start Down clues.

Challenge

Given a grid size and two lists of Across word numbers and Down word numbers, find a valid grid that matches the numbers. Inputs are guaranteed to have at least one valid solution, but it's not guaranteed to be unique. Any valid output that matches the input is acceptable.

To complete this challenge, you must run your program all the way through to completion for at least one challenge input.

Example input

You are not required to use any particular input/output format. Feel free to hard code the input into your program.

EXAMPLE: 15x15
A: 1,4,7,10,13,14,16,17,18,20,21,23,24,26,28,29,33,35,36,38,39,42,44,45,47,49,50,52,55,56,58,59,61,63,67,69,70,71,72,73,74,75,76
D: 1,2,3,4,5,6,7,8,9,11,12,15,19,22,25,27,29,30,31,32,34,37,40,41,43,46,48,51,53,54,57,60,62,64,65,66,68

Example output

. . . # # # . . . # . . . # #
. . . . . # . . . # . . . . #
. . . . . # . . . # . . . . .
. . . . . # . . . . # . . . .
# # # . . . # . . . . # . . .
. . . . . . . # . . . . . . .
. . . # # . . . # . . . . . .
. . . . . # . . . # . . . . .
. . . . . . # . . . # # . . .
. . . . . . . # . . . . . . .
. . . # . . . . # . . . # # #
. . . . # . . . . # . . . . .
. . . . . # . . . # . . . . .
# . . . . # . . . # . . . . .
# # . . . # . . . # # # . . .

Challenge inputs

#1: 15x15
A: 1,6,10,12,13,14,16,17,19,20,21,23,25,27,29,30,31,33,34,35,37,38,40,41,42,44,45,46,49,50
D: 1,2,3,4,5,6,7,8,9,10,11,12,15,17,18,20,21,22,24,26,28,32,33,36,39,41,43,45,47,48

#2: 21x21
A: 1,4,7,10,12,14,16,17,18,19,21,24,25,26,27,29,30,32,34,35,36,38,39,40,42,45,46,48,49,51,52,54,55,56,57,58,59,61,63,64,66,67,69,70,73,74,75,76,77,79,81,82,84,85,87,89,90,92,94,96,97,99,100,101,102,103,104,105
D: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,19,20,22,23,24,28,31,33,37,38,41,42,43,44,45,47,50,52,53,60,62,63,64,65,67,68,71,72,74,78,80,81,83,84,86,88,89,91,93,95,98

#3: 27x27
A: 1,5,10,15,18,22,25,27,29,32,33,34,35,36,37,38,39,40,42,44,46,47,48,49,51,52,54,55,56,57,59,61,65,67,69,70,71,73,74,77,80,82,84,86,87,88,89,91,93,94,96,99,101,102,103,104,106,108,110,112,114,115,116,119,121,123,125,126,128,129,132,133,135,136,138,139,140,142,144,147,148,149,151,153,154,156,158,162,166,167,169,170,171,173,174,176,177,178,179,181,182,185,186,187,188,189,191,192,193,195,201,202,203,204,205,206,207,208
D: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,23,24,26,28,30,31,37,39,40,41,43,45,46,47,50,53,54,55,56,58,60,62,63,64,66,68,72,74,75,76,78,79,81,83,85,88,90,92,94,95,97,98,100,103,105,106,107,109,111,113,117,118,120,122,124,127,128,130,131,134,137,139,141,143,144,145,146,148,150,152,155,157,159,160,161,163,164,165,168,172,175,176,177,178,180,181,183,184,185,186,190,192,193,194,196,197,198,199,200

#4: 33x33
A: 1,5,13,19,23,25,28,29,30,33,34,35,36,37,38,42,43,48,49,50,51,56,58,60,61,62,64,65,66,67,68,69,70,71,72,73,76,78,79,80,81,83,86,88,89,90,93,94,96,100,101,102,105,107,108,109,110,111,112,114,116,117,118,120,121,122,126,127,128,130,131,133,134,135,138,139,141,142,143,145,146,149,151,152,154,155,159,160,163,165,166,167,168,172,173,174,175,176,178,180,181,183,185,187,188,189,190,191,192,193,194,197,199,200,201,202,203,205,207,208,209,210,212,213,215,216,217,220,222,223,224,226,227,228,230,233,234,235,236,238,242,244,246,247,248,249,250,252,253,254,255,256,259,260,263,265,271,276,277,278,279,280,281,282
D: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,31,32,33,35,38,39,40,41,42,43,44,45,46,47,51,52,53,54,55,56,57,59,61,63,73,74,75,77,82,83,84,85,87,88,89,90,91,92,95,97,98,99,100,101,102,103,104,106,110,113,115,116,118,119,123,124,125,126,127,129,132,134,135,136,137,140,142,143,144,147,148,149,150,151,153,154,156,157,158,159,160,161,162,164,167,168,169,170,171,176,177,178,179,182,184,185,186,187,192,194,195,196,198,201,202,204,206,208,209,211,213,214,215,216,217,218,219,221,223,225,226,229,231,232,233,237,239,240,241,243,244,245,248,251,253,255,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275

Description

The game of Yahtzee is played by rolling five 6-sided dice, and scoring the results in a number of ways. You are given a Yahtzee dice roll, represented as a sorted list of 5 integers, each of which is between 1 and 6 inclusive. Your task is to find the maximum possible score for this roll in the upper section of the Yahtzee score card. Here's what that means.

For the purpose of this challenge, the upper section of Yahtzee gives you six possible ways to score a roll. 1 times the number of 1's in the roll, 2 times the number of 2's, 3 times the number of 3's, and so on up to 6 times the number of 6's. For instance, consider the roll [2, 3, 5, 5, 6]. If you scored this as 1's, the score would be 0, since there are no 1's in the roll. If you scored it as 2's, the score would be 2, since there's one 2 in the roll. Scoring the roll in each of the six ways gives you the six possible scores:

0 2 3 0 10 6

The maximum here is 10 (2x5), so your result should be 10.

Examples

yahtzee_upper([2, 3, 5, 5, 6]) => 10
yahtzee_upper([1, 1, 1, 1, 3]) => 4
yahtzee_upper([1, 1, 1, 3, 3]) => 6
yahtzee_upper([1, 2, 3, 4, 5]) => 5
yahtzee_upper([6, 6, 6, 6, 6]) => 30

Optional Bonus

Efficiently handle inputs that are unsorted and much larger, both in the number of dice and in the number of sides per die. (For the purpose of this bonus challenge, you want the maximum value of some number k, times the number of times k appears in the input.)

yahtzee_upper([1654, 1654, 50995, 30864, 1654, 50995, 22747,
    1654, 1654, 1654, 1654, 1654, 30864, 4868, 1654, 4868, 1654,
    30864, 4868, 30864]) => 123456

There's no strict limit on how fast it needs to run. That depends on your language of choice. But for rough comparison, my Python solution on this challenge input, consisting of 100,000 values between 1 and 999,999,999 takes about 0.2 seconds (0.06 seconds not counting input parsing).

If you're preparing for a coding interview, this is a good opportunity to practice runtime complexity. Try to find a solution that's linear (O(N)) in both time and space requirements.

Thanks to u/Foenki for inspiring today's challenge in r/dailyprogrammer_ideas!

Smooshed Morse code means Morse code with the spaces between encoded letters left out. See this week's Easy challenge for more detail. We'll also be stripping all punctuation, capitalization, and spacing, so the only encoded characters are the letters a-z.

Your challenge today is to decode smooshed Morse code representations of English text. As I said in the Easy challenge, the decoding is ambiguous. You're not expected to do a perfect job, but the more your output resembles English, the better you're doing. You are not expected to reproduce the punctuation, just the spacing between words.

A standard approach involves training on a corpus of English text. Last time I posted a similar challenge, u/dreugeworst got excellent results this way. You can use any training data sources you want, but your program must run autonomously on the input, without human intervention.

The challenge inputs this time are all English-language movie quotes, some of which involve proper names, contractions (without the apostrophe), or other words you might not find in a standard word list.

(I have no idea how difficult this is, so I'll be happy to provide challenge inputs that are easier/harder/shorter/longer/whatever.)

Example input

-.---..--.....--.--..-..-.--....--.--..-.--.-.....--.-......-....-......-...-.-......-.--.--.--

Example output

no im simply saying that life uh finds a way

Challenge inputs

Input 1

......---.--..--...-....-..-----.....-..-.--.-.-.-..-.--.-....-.-.-.....--..-..-...-.--.-...--..--.----.-.--..--...-.-.-.....--.--.....----.-.....-.-..----..-.-.-..-....--...-........-.---.-.....-..-.-.-.---.--.--...-....-...----....----.---.-..-..--...-...-..-.-.-..----.

Input 2 (contains proper names)

...--.--.-----.......---.---.-----..-...-----.-......-.--.....----.--.-.-..-..---......-...--.-...-..-------.--.-..-..---.....-...-....-....-.-...-.-.....-.--.---...-..-.-.--.-.-....--..-.-....-.--..--....-.---.....-...-..-..----...--.....-.-.-----..--.-..--......-...-.-.-----.---.--..-.-..-......--..-...-.-..----..-..-.---.........----..-.-..--.-....-.-..--.-....-.-..-..--.-.----.-.-.---.-...-...-..-...-.--.---..-...-.-..--....-.....-...-..--...-.---......---.-.--..--...........--...-.-.----.-.-..--.-.----.-.....--....---.-.-.....---.....-.--..--..-.-----.....-..-.-..-.-.-..-.--.--.-.--.-..-...-..-...--....---.-...-..-.-----.---..-.......--........-.....-.-.......---..-......--..-...-...-.-....-...-.-.......

Input 3

-.-----..-.-..-......-.......-..........------..-..-.-..--.-..-.-....-.---..-..--...--.-....-.-...--.-.-..-...--.-..-.--..----...-.......-..-.------......--..-.-----..-..-----..-.--.---..-.-.....--.--.-...-..--.-----..-.-.-..-.........-.-.-..-.-.-....--.-----..-..--..--.-----.-.-..-.--.--......-.-.....-.......--...-.---.--.....-.-.-...-.....-...-...-.---.-.-..........-...-.-.....-...--..--....-...----..-....--..-..--...-..-.-----.--.....--.....----......-..--.......-.....-.-.------.-.-----..-.--.--.....--.--..-.-..-.-...--..-..-.-........----..--.......-.....-.-..--.-..-.....--.....-.-.-...-..-........-....----..-....-..-.--.-...----..-...-....-.....-.----..--..-..-.--..-.-.-.-...--.-..-......-...-.-----....-.------.-...---..-.....-.-..---..-.-.-.----.-.-.---.-...--......-.-..........-....-...-..-.-----..-..-..-..----.-..--....-..-.--......-..

Thanks to u/Separate_Memory for inspiring this challenge on r/dailyprogrammer_ideas!

Smooshed Morse code means Morse code with the spaces or other delimiters between encoded letters left out. See this week's Easy challenge for more detail.

A permutation of the alphabet is a 26-character string in which each of the letters a through z appears once.

Given a smooshed Morse code encoding of a permutation of the alphabet, find the permutation it encodes, or any other permutation that produces the same encoding (in general there will be more than one). It's not enough to write a program that will eventually finish after a very long period of time: run your code through to completion for at least one example.

Examples

smalpha(".--...-.-.-.....-.--........----.-.-..---.---.--.--.-.-....-..-...-.---..--.----..")
    => "wirnbfzehatqlojpgcvusyxkmd"
smalpha(".----...---.-....--.-........-----....--.-..-.-..--.--...--..-.---.--..-.-...--..-")
    => "wzjlepdsvothqfxkbgrmyicuna"
smalpha("..-...-..-....--.---.---.---..-..--....-.....-..-.--.-.-.--.-..--.--..--.----..-..")
    => "uvfsqmjazxthbidyrkcwegponl"

Again, there's more than one valid output for these inputs.

Optional bonus 1

Here's a list of 1000 inputs. How fast can you find the output for all of them? A good time depends on your language of choice and setup, so there's no specific time to aim for.

Optional bonus 2

Typically, a valid input will have thousands of possible outputs. The object of this bonus challenge is to find a valid input with as few possible outputs as possible, while still having at least 1. The following encoded string has 41 decodings:

......-..--...---.-....---...--....--.-..---.....---.-.---..---.-....--.-.---.-.--

Can you do better? When this post is 7 days old, I'll award +1 gold medal flair to the submission with the fewest possible decodings. I'll break ties by taking the lexicographically first string. That is, I'll look at the first character where the two strings differ and award the one with a dash (-) in that position, since - is before . lexicographically.

Thanks to u/Separate_Memory for inspiring this week's challenges on r/dailyprogrammer_ideas!

For the purpose of this challenge, Morse code represents every letter as a sequence of 1-4 characters, each of which is either . (dot) or - (dash). The code for the letter a is .-, for b is -..., etc. The codes for each letter a through z are:

.- -... -.-. -.. . ..-. --. .... .. .--- -.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.-- --..

Normally, you would indicate where one letter ends and the next begins, for instance with a space between the letters' codes, but for this challenge, just smoosh all the coded letters together into a single string consisting of only dashes and dots.

Examples

smorse("sos") => "...---..."
smorse("daily") => "-...-...-..-.--"
smorse("programmer") => ".--..-.-----..-..-----..-."
smorse("bits") => "-.....-..."
smorse("three") => "-.....-..."

An obvious problem with this system is that decoding is ambiguous. For instance, both bits and three encode to the same string, so you can't tell which one you would decode to without more information.

Optional bonus challenges

For these challenges, use the enable1 word list. It contains 172,823 words. If you encode them all, you would get a total of 2,499,157 dots and 1,565,081 dashes.

1. The sequence -...-....-.--. is the code for four different words (needing, nervate, niding, tiling). Find the only sequence that's the code for 13 different words.
2. autotomous encodes to .-..--------------..-..., which has 14 dashes in a row. Find the only word that has 15 dashes in a row.
3. Call a word perfectly balanced if its code has the same number of dots as dashes. counterdemonstrations is one of two 21-letter words that's perfectly balanced. Find the other one.
4. protectorate is 12 letters long and encodes to .--..-.----.-.-.----.-..--., which is a palindrome (i.e. the string is the same when reversed). Find the only 13-letter word that encodes to a palindrome.
5. --.---.---.-- is one of five 13-character sequences that does not appear in the encoding of any word. Find the other four.

Thanks to u/Separate_Memory for inspiring this challenge on r/dailyprogrammer_ideas!

Challenge

The nation of Examplania has the following income tax brackets:

income cap      marginal tax rate
  ¤10,000           0.00 (0%)
  ¤30,000           0.10 (10%)
 ¤100,000           0.25 (25%)
    --              0.40 (40%)

If you're not familiar with how tax brackets work, see the section below for an explanation.

Given a whole-number income amount up to ¤100,000,000, find the amount of tax owed in Examplania. Round down to a whole number of ¤.

Examples

tax(0) => 0
tax(10000) => 0
tax(10009) => 0
tax(10010) => 1
tax(12000) => 200
tax(56789) => 8697
tax(1234567) => 473326

Optional improvement

One way to improve your code is to make it easy to swap out different tax brackets, for instance by having the table in an input file. If you do this, you may assume that both the income caps and marginal tax rates are in increasing order, the highest bracket has no income cap, and all tax rates are whole numbers of percent (no more than two decimal places).

However, because this is an Easy challenge, this part is optional, and you may hard code the tax brackets if you wish.

How tax brackets work

A tax bracket is a range of income based on the income caps, and each tax bracket has a corresponding marginal tax rate, which applies to income within the bracket. In our example, the tax bracket for the range ¤10,000 to ¤30,000 has a marginal tax rate of 10%. Here's what that means for each bracket:

• If your income is less than ¤10,000, you owe 0 income tax.
• If your income is between ¤10,000 and ¤30,000, you owe 10% income tax on the income that exceeds ¤10,000. For instance, if your income is ¤18,000, then your income in the 10% bracket is ¤8,000. So your income tax is 10% of ¤8,000, or ¤800.
• If your income is between ¤30,000 and ¤100,000, then you owe 10% of your income between ¤10,000 and ¤30,000, plus 25% of your income over ¤30,000.
• And finally, if your income is over ¤100,000, then you owe 10% of your income from ¤10,000 to ¤30,000, plus 25% of your income from ¤30,000 to ¤100,000, plus 40% of your income above ¤100,000.

One aspect of progressive taxation is that increasing your income will never decrease the amount of tax that you owe, or your overall tax rate (except for rounding).

Optional bonus

The overall tax rate is simply the total tax divided by the total income. For example, an income of ¤256,250 has an overall tax of ¤82,000, which is an overall tax rate of exactly 32%:

82000 = 0.00 × 10000 + 0.10 × 20000 + 0.25 × 70000 + 0.40 × 156250
82000 = 0.32 × 256250

Given a target overall tax rate, find the income amount that would be taxed at that overall rate in Examplania:

overall(0.00) => 0 (or anything up to 10000)
overall(0.06) => 25000
overall(0.09) => 34375
overall(0.32) => 256250
overall(0.40) => NaN (or anything to signify that no such income value exists)

You may get somewhat different answers because of rounding, but as long as it's close that's fine.

The simplest possibility is just to iterate and check the overall tax rate for each possible income. That works fine, but if you want a performance boost, check out binary search. You can also use algebra to reduce the number of calculations needed; just make it so that your code still gives correct answers if you swap out a different set of tax brackets.

It was a dark and stormy night. Detective Havel and Detective Hakimi arrived at the scene of the crime.

Other than the detectives, there were 10 people present. They asked the first person, "out of the 9 other people here, how many had you already met before tonight?" The person answered "5". They asked the same question of the second person, who answered "3". And so on. The 10 answers they got from the 10 people were:

5 3 0 2 6 2 0 7 2 5

The detectives looked at the answers carefully and deduced that there was an inconsistency, and that somebody must be lying. (For the purpose of this challenge, assume that nobody makes mistakes or forgets, and if X has met Y, that means Y has also met X.)

Your challenge for today is, given a sequence of answers to the question "how many of the others had you met before tonight?", apply the Havel-Hakimi algorithm to determine whether or not it's possible that everyone was telling the truth.

If you're feeling up to it, skip ahead to the Challenge section below. Otherwise, try as many of the optional warmup questions as you want first, before attempting the full challenge.

Optional Warmup 1: eliminating 0's.

Given a sequence of answers, return the same set of answers with all the 0's removed.

warmup1([5, 3, 0, 2, 6, 2, 0, 7, 2, 5]) => [5, 3, 2, 6, 2, 7, 2, 5]
warmup1([4, 0, 0, 1, 3]) => [4, 1, 3]
warmup1([1, 2, 3]) => [1, 2, 3]
warmup1([0, 0, 0]) => []
warmup1([]) => []

If you want to reorder the sequence as you do this, that's fine. For instance, given [4, 0, 0, 1, 3], then you may return [4, 1, 3] or [1, 3, 4] or [4, 3, 1] or any other ordering of these numbers.

Optional Warmup 2: descending sort

Given a sequence of answers, return the sequence sorted in descending order, so that the first number is the largest and the last number is the smallest.

warmup2([5, 1, 3, 4, 2]) => [5, 4, 3, 2, 1]
warmup2([0, 0, 0, 4, 0]) => [4, 0, 0, 0, 0]
warmup2([1]) => [1]
warmup2([]) => []

Optional Warmup 3: length check

Given a number N and a sequence of answers, return true if N is greater than the number of answers (i.e. the length of the sequence), and false if N is less than or equal to the number of answers. For instance, given 7 and [6, 5, 5, 3, 2, 2, 2], you would return false, because 7 is less than or equal to 7.

warmup3(7, [6, 5, 5, 3, 2, 2, 2]) => false
warmup3(5, [5, 5, 5, 5, 5]) => false
warmup3(5, [5, 5, 5, 5]) => true
warmup3(3, [1, 1]) => true
warmup3(1, []) => true
warmup3(0, []) => false

Optional Warmup 4: front elimination

Given a number N and a sequence in descending order, subtract 1 from each of the first N answers in the sequence, and return the result. For instance, given N = 4 and the sequence [5, 4, 3, 2, 1], you would subtract 1 from each of the first 4 answers (5, 4, 3, and 2) to get 4, 3, 2, and 1. The rest of the sequence (1) would not be affected:

warmup4(4, [5, 4, 3, 2, 1]) => [4, 3, 2, 1, 1]
warmup4(11, [14, 13, 13, 13, 12, 10, 8, 8, 7, 7, 6, 6, 4, 4, 2]) => [13, 12, 12, 12, 11, 9, 7, 7, 6, 6, 5, 6, 4, 4, 2]
warmup4(1, [10, 10, 10]) => [9, 10, 10]
warmup4(3, [10, 10, 10]) => [9, 9, 9]
warmup4(1, [1]) => [0]

You may assume that N is greater than 0, and no greater than the length of the sequence. Like in warmup 1, it's okay if you want to reorder the answers in your result.

Challenge: the Havel-Hakimi algorithm

Perform the Havel-Hakimi algorithm on a given sequence of answers. This algorithm will return true if the answers are consistent (i.e. it's possible that everyone is telling the truth) and false if the answers are inconsistent (i.e. someone must be lying):

1. Remove all 0's from the sequence (i.e. warmup1).
2. If the sequence is now empty (no elements left), stop and return true.
3. Sort the sequence in descending order (i.e. warmup2).
4. Remove the first answer (which is also the largest answer, or tied for the largest) from the sequence and call it N. The sequence is now 1 shorter than it was after the previous step.
5. If N is greater than the length of this new sequence (i.e. warmup3), stop and return false.
6. Subtract 1 from each of the first N elements of the new sequence (i.e. warmup4).
7. Continue from step 1 using the sequence from the previous step.

Eventually you'll either return true in step 2, or false in step 5.

You don't have to follow these steps exactly: as long as you return the right answer, that's fine. Also, if you answered the warmup questions, you may use your warmup solutions to build your challenge solution, but you don't have to.

hh([5, 3, 0, 2, 6, 2, 0, 7, 2, 5]) => false
hh([4, 2, 0, 1, 5, 0]) => false
hh([3, 1, 2, 3, 1, 0]) => true
hh([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16]) => true
hh([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12]) => true
hh([15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3]) => false
hh([6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1]) => false
hh([2, 2, 0]) => false
hh([3, 2, 1]) => false
hh([1, 1]) => true
hh([1]) => false
hh([]) => true

Detailed example

Here's the first pass through the algorithm using the original example:

• [5, 3, 0, 2, 6, 2, 0, 7, 2, 5] - Starting sequence
• [5, 3, 2, 6, 2, 7, 2, 5] - After step 1, removing 0's.
• Step 2: This sequence is not empty, so go on to step 3.
• [7, 6, 5, 5, 3, 2, 2, 2] - After step 3, sorting in descending order.
• [6, 5, 5, 3, 2, 2, 2] - After step 4, removing the first answer N = 7.
• Step 5: N (7) is less than or equal to the number of answers remaining in the sequence (7), so go on to step 6.
• [5, 4, 4, 2, 1, 1, 1] - After step 6, subtracting 1 from each of the first 7 answers (which is all of them in this case).

At this point you would start over at step 1 with the sequence [5, 4, 4, 2, 1, 1, 1]. After your second pass through the algorithm, your sequence will be [3, 3, 1, 0, 0, 1], so start back at step 1 with this sequence. After your third pass you'll have [2, 0, 0]. On your fourth pass, you'll stop at step 5, because you'll have N = 2 and an empty sequence ([]), and 2 > 0, so you will return false.

Description

You have a 2-dimensional rectangular crate of size X by Y, and a bunch of boxes, each of size x by y. The dimensions are all positive integers.

Given X, Y, x, and y, determine how many boxes can fit into a single crate if they have to be placed so that the x-axis of the boxes is aligned with the x-axis of the crate, and the y-axis of the boxes is aligned with the y-axis of the crate. That is, you can't rotate the boxes. The best you can do is to build a rectangle of boxes as large as possible in each dimension.

For instance, if the crate is size X = 25 by Y = 18, and the boxes are size x = 6 by y = 5, then the answer is 12. You can fit 4 boxes along the x-axis (because 6*4 <= 25), and 3 boxes along the y-axis (because 5*3 <= 18), so in total you can fit 4*3 = 12 boxes in a rectangle.

Examples

fit1(25, 18, 6, 5) => 12
fit1(10, 10, 1, 1) => 100
fit1(12, 34, 5, 6) => 10
fit1(12345, 678910, 1112, 1314) => 5676
fit1(5, 100, 6, 1) => 0

Optional bonus fit2

You upgrade your packing robot with the latest in packing technology: turning stuff. You now have the option of rotating all boxes by 90 degrees, so that you can treat a set of 6-by-5 boxes as a set of 5-by-6 boxes. You do not have the option of rotating some of the boxes but not others.

fit2(25, 18, 6, 5) => 15
fit2(12, 34, 5, 6) => 12
fit2(12345, 678910, 1112, 1314) => 5676
fit2(5, 5, 3, 2) => 2
fit2(5, 100, 6, 1) => 80
fit2(5, 5, 6, 1) => 0

Hint: is there an easy way to define fit2 in terms of fit1?

Note that this is not the maximum possible number of boxes you could get if you rotated them independently. For instance, if you're fitting 3-by-2 boxes into a 5-by-5 crate, it's possible to fit 4 by varying the orientations, but fit2(5, 5, 3, 2) is 2, not 4. Handling the general case is much more complicated, and beyond the scope of today's challenge.

Optional bonus fit3

You upgrade your warehouse to the third dimension. You're now given six parameters, X, Y, Z, x, y, and z. That is, you're given the X, Y, and Z dimensions of the crate, and the x, y, and z dimensions of the boxes. There are now six different possible orientations of the boxes. Again, boxes cannot be rotated independently: they all have to have the same orientation.

fit3(10, 10, 10, 1, 1, 1) => 1000
fit3(12, 34, 56, 7, 8, 9) => 32
fit3(123, 456, 789, 10, 11, 12) => 32604
fit3(1234567, 89101112, 13141516, 171819, 202122, 232425)) => 174648

Optional bonus fitn

You upgrade your warehouse to the Nth dimension. Now you take a list of N crate dimensions, and N box dimensions. Assume that the boxes may be rotated in any of N! orientations so that each axis of the crate aligns with a different axis of the boxes. Again, boxes cannot be rotated independently.

fitn([3, 4], [1, 2]) => 6
fitn([123, 456, 789], [10, 11, 12]) => 32604
fitn([123, 456, 789, 1011, 1213, 1415], [16, 17, 18, 19, 20, 21]) => 1883443968

EDIT: if you want even more of a challenge, do this in fewer than O(N!) operations. There's no specific time goal, but my Python program finds the following solution for N = 20 in about 10 seconds:

fitn([180598, 125683, 146932, 158296, 171997, 204683, 193694, 216231, 177673, 169317, 216456, 220003, 165939, 205613, 152779, 177216, 128838, 126894, 210076, 148407], [1984, 2122, 1760, 2059, 1278, 2017, 1443, 2223, 2169, 1502, 1274, 1740, 1740, 1768, 1295, 1916, 2249, 2036, 1886, 2010]) => 4281855455197643306306491981973422080000

Background

The Revised Julian Calendar is a calendar system very similar to the familiar Gregorian Calendar, but slightly more accurate in terms of average year length. The Revised Julian Calendar has a leap day on Feb 29th of leap years as follows:

• Years that are evenly divisible by 4 are leap years.
• Exception: Years that are evenly divisible by 100 are not leap years.
• Exception to the exception: Years for which the remainder when divided by 900 is either 200 or 600 are leap years.

For instance, 2000 is an exception to the exception: the remainder when dividing 2000 by 900 is 200. So 2000 is a leap year in the Revised Julian Calendar.

Challenge

Given two positive year numbers (with the second one greater than or equal to the first), find out how many leap days (Feb 29ths) appear between Jan 1 of the first year, and Jan 1 of the second year in the Revised Julian Calendar. This is equivalent to asking how many leap years there are in the interval between the two years, including the first but excluding the second.

leaps(2016, 2017) => 1
leaps(2019, 2020) => 0
leaps(1900, 1901) => 0
leaps(2000, 2001) => 1
leaps(2800, 2801) => 0
leaps(123456, 123456) => 0
leaps(1234, 5678) => 1077
leaps(123456, 7891011) => 1881475

For this challenge, you must handle very large years efficiently, much faster than checking each year in the range.

leaps(123456789101112, 1314151617181920) => 288412747246240

Optional bonus

Some day in the distant future, the Gregorian Calendar and the Revised Julian Calendar will agree that the day is Feb 29th, but they'll disagree about what year it is. Find the first such year (efficiently).

Description

We'll focus in this challenge on what's called a complete graph, wherein every node is expressly connected to every other node. We'll also work assuming an undirected graph, that relationships are reciprocal.

In social network analysis, you can analyze for structural balance - a configuration wherein you'll find local stability. The easy one is when everyone enjoys a positive relationship with everyone else - they're all friends. Another structurally balanced scenario is when you have - in a graph of three nodes - two friends and each with a shared enemy, so one positive relationship and two negative ones.

With larger graphs, you can continue this analysis by analyzing every three node subgraph and ensuring it has those properties - all positive or one positive and two negative relationsgips.

A structurally balanced graph doesn't indicate complete future stability, just local stability - remember, factions can arise in these networks, akin to the Axis and Allies scenario of WW1 and WW2.

Today's challenge is to take a graph and identify if the graph is structurally balanced. This has great applicability to social network analysis, and can easily be applied to stuff like fictional universes like the Game of Thrones and the real world based on news events.

Example Input

You'll be given a graph in the following format: the first line contains two integers, N and M, telling you how many nodes and edges to load, respectively. The next M lines tell you relationships, positive (friendly, denoted by ++) or negative (foes, denoted by --). Example (from a subset of the Legion of Doom and Justice League):

6 15
Superman ++ Green Lantern
Superman ++ Wonder Woman
Superman -- Sinestro
Superman -- Cheetah
Superman -- Lex Luthor
Green Lantern ++ Wonder Woman
Green Lantern -- Sinestro
Green Lantern -- Cheetah
Green Lantern -- Lex Luthor
Wonder Woman -- Sinestro
Wonder Woman -- Cheetah
Wonder Woman -- Lex Luthor
Sinestro ++ Cheetah
Sinestro ++ Lex Luthor
Cheetah ++ Lex Luthor

Example Output

Your program should emit if the graph is structurally balanced or not. Example:

balanced

Challenge Input

This is the Game of Thrones Season 7 house list I found via this list of alliances on the Vulture website - I don't watch GoT so I have no idea if I captured this right.

120 16
Daenerys Targaryen ++ Jon Snow
Daenerys Targaryen ++ Tyrion Lannister
Daenerys Targaryen ++ Varys
Daenerys Targaryen ++ Jorah Mormont
Daenerys Targaryen ++ Beric Dondarrion
Daenerys Targaryen ++ Sandor “the Hound” Clegane
Daenerys Targaryen ++ Theon and Yara Greyjoy
Daenerys Targaryen -- Sansa Stark
Daenerys Targaryen -- Arya Stark
Daenerys Targaryen -- Bran Stark
Daenerys Targaryen -- The Lords of the North and the Vale
Daenerys Targaryen -- Littlefinger
Daenerys Targaryen -- Cersei Lannister
Daenerys Targaryen -- Jaime Lannister
Daenerys Targaryen -- Euron Greyjoy
Jon Snow ++ Tyrion Lannister
Jon Snow ++ Varys
Jon Snow ++ Jorah Mormont
Jon Snow ++ Beric Dondarrion
Jon Snow ++ Sandor “the Hound” Clegane
Jon Snow -- Theon and Yara Greyjoy
Jon Snow -- Sansa Stark
Jon Snow -- Arya Stark
Jon Snow -- Bran Stark
Jon Snow -- The Lords of the North and the Vale
Jon Snow -- Littlefinger
Jon Snow -- Cersei Lannister
Jon Snow -- Jaime Lannister
Jon Snow -- Euron Greyjoy
Tyrion Lannister ++ Varys
Tyrion Lannister ++ Jorah Mormont
Tyrion Lannister ++ Beric Dondarrion
Tyrion Lannister ++ Sandor “the Hound” Clegane
Tyrion Lannister ++ Theon and Yara Greyjoy
Tyrion Lannister -- Sansa Stark
Tyrion Lannister -- Arya Stark
Tyrion Lannister -- Bran Stark
Tyrion Lannister -- The Lords of the North and the Vale
Tyrion Lannister -- Littlefinger
Tyrion Lannister -- Cersei Lannister
Tyrion Lannister -- Jaime Lannister
Tyrion Lannister -- Euron Greyjoy
Varys ++ Jorah Mormont
Varys ++ Beric Dondarrion
Varys ++ Sandor “the Hound” Clegane
Varys ++ Theon and Yara Greyjoy
Varys -- Sansa Stark
Varys -- Arya Stark
Varys -- Bran Stark
Varys -- The Lords of the North and the Vale
Varys -- Littlefinger
Varys -- Cersei Lannister
Varys -- Jaime Lannister
Varys -- Euron Greyjoy
Jorah Mormont ++ Beric Dondarrion
Jorah Mormont ++ Sandor “the Hound” Clegane
Jorah Mormont ++ Theon and Yara Greyjoy
Jorah Mormont -- Sansa Stark
Jorah Mormont -- Arya Stark
Jorah Mormont -- Bran Stark
Jorah Mormont -- The Lords of the North and the Vale
Jorah Mormont -- Littlefinger
Jorah Mormont -- Cersei Lannister
Jorah Mormont -- Jaime Lannister
Jorah Mormont -- Euron Greyjoy
Beric Dondarrion ++ Sandor “the Hound” Clegane
Beric Dondarrion ++ Theon and Yara Greyjoy
Beric Dondarrion -- Sansa Stark
Beric Dondarrion -- Arya Stark
Beric Dondarrion -- Bran Stark
Beric Dondarrion -- The Lords of the North and the Vale
Beric Dondarrion -- Littlefinger
Beric Dondarrion -- Cersei Lannister
Beric Dondarrion -- Jaime Lannister
Beric Dondarrion -- Euron Greyjoy
Sandor “the Hound” Clegane ++ Theon and Yara Greyjoy
Sandor “the Hound” Clegane -- Sansa Stark
Sandor “the Hound” Clegane -- Arya Stark
Sandor “the Hound” Clegane -- Bran Stark
Sandor “the Hound” Clegane -- The Lords of the North and the Vale
Sandor “the Hound” Clegane -- Littlefinger
Sandor “the Hound” Clegane -- Cersei Lannister
Sandor “the Hound” Clegane -- Jaime Lannister
Sandor “the Hound” Clegane -- Euron Greyjoy
Theon and Yara Greyjoy -- Sansa Stark
Theon and Yara Greyjoy -- Arya Stark
Theon and Yara Greyjoy -- Bran Stark
Theon and Yara Greyjoy -- The Lords of the North and the Vale
Theon and Yara Greyjoy -- Littlefinger
Theon and Yara Greyjoy -- Cersei Lannister
Theon and Yara Greyjoy -- Jaime Lannister
Theon and Yara Greyjoy -- Euron Greyjoy
Sansa Stark ++ Arya Stark
Sansa Stark ++ Bran Stark
Sansa Stark ++ The Lords of the North and the Vale
Sansa Stark ++ Littlefinger
Sansa Stark -- Cersei Lannister
Sansa Stark -- Jaime Lannister
Sansa Stark -- Euron Greyjoy
Arya Stark ++ Bran Stark
Arya Stark ++ The Lords of the North and the Vale
Arya Stark ++ Littlefinger
Arya Stark -- Cersei Lannister
Arya Stark -- Jaime Lannister
Arya Stark -- Euron Greyjoy
Bran Stark ++ The Lords of the North and the Vale
Bran Stark -- Littlefinger
Bran Stark -- Cersei Lannister
Bran Stark -- Jaime Lannister
Bran Stark -- Euron Greyjoy
The Lords of the North and the Vale ++ Littlefinger
The Lords of the North and the Vale -- Cersei Lannister
The Lords of the North and the Vale -- Jaime Lannister
The Lords of the North and the Vale -- Euron Greyjoy
Littlefinger -- Cersei Lannister
Littlefinger -- Jaime Lannister
Littlefinger -- Euron Greyjoy
Cersei Lannister ++ Jaime Lannister
Cersei Lannister ++ Euron Greyjoy
Jaime Lannister ++ Euron Greyjoy

Notes

You can learn more about the ideas behind this challenge in these resources:

• Positive and Negative Relationships, in D. Easley and J. Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World (2010).
• Network Mathematics and Rival Factions from the PBS Digital YouTube channel Infinite Series. It was this video that inspired this challenge.
• The Graph of Thrones [Season 7 Contest], from the Neo4j site referencing how to use their software to answer a Kaggle challenge about predicting GoT's future.

Description

This challenge is about a simple card flipping solitaire game. You're presented with a sequence of cards, some face up, some face down. You can remove any face up card, but you must then flip the adjacent cards (if any). The goal is to successfully remove every card. Making the wrong move can get you stuck.

In this challenge, a 1 signifies a face up card and a 0 signifies a face down card. We will also use zero-based indexing, starting from the left, to indicate specific cards. So, to illustrate a game, consider this starting card set.

0100110

I can choose to remove cards 1, 4, or 5 since these are face up. If I remove card 1, the game looks like this (using . to signify an empty spot):

1.10110

I had to flip cards 0 and 2 since they were adjacent. Next I could choose to remove cards 0, 2, 4, or 5. I choose card 0:

..10110

Since it has no adjacent cards, there were no cards to flip. I can win this game by continuing with: 2, 3, 5, 4, 6.

Supposed instead I started with card 4:

0101.00

This is unsolvable since there's an "island" of zeros, and cards in such islands can never be flipped face up.

Input Description

As input you will be given a sequence of 0 and 1, no spaces.

Output Description

Your program must print a sequence of moves that leads to a win. If there is no solution, it must print "no solution". In general, if there's one solution then there are many possible solutions.

Optional output format: Illustrate the solution step by step.

Sample Inputs

0100110
01001100111
100001100101000

Sample Outputs

1 0 2 3 5 4 6
no solution
0 1 2 3 4 6 5 7 8 11 10 9 12 13 14

Challenge Inputs

0100110
001011011101001001000
1010010101001011011001011101111
1101110110000001010111011100110

Bonus Input

010111111111100100101000100110111000101111001001011011000011000

Credit

This challenge was suggested by /u/skeeto, many thanks! If you have a challenge idea please share it in /r/dailyprogrammer_ideas and there's a good chance we'll use it.

Description

A number is input in computer then a new no should get printed by adding one to each of its digit. If you encounter a 9, insert a 10 (don't carry over, just shift things around).

For example, 998 becomes 10109.

Bonus

This challenge is trivial to do if you map it to a string to iterate over the input, operate, and then cast it back. Instead, try doing it without casting it as a string at any point, keep it numeric (int, float if you need it) only.

Credit

This challenge was suggested by user /u/chetvishal, many thanks! If you have a challenge idea please share it in /r/dailyprogrammer_ideas and there's a good chance we'll use it.