dailyprogrammer - Tumblr blog

[dailyprogrammer]

[2019-08-09] Challenge #380 [Hard] Smooshed Morse Code 3

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!

[dailyprogrammer]

[2019-08-07] Challenge #380 [Intermediate] Smooshed Morse Code 2

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!

[dailyprogrammer]

[2019-08-05] Challenge #380 [Easy] Smooshed Morse Code 1

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.

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.

autotomous encodes to .-..--------------..-..., which has 14 dashes in a row. Find the only word that has 15 dashes in a row.

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.

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.

--.---.---.-- 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!

[dailyprogrammer]

[2019-07-15] Challenge #379 [Easy] Progressive taxation

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) => 485327

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

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.

[dailyprogrammer]

[2019-05-20] Challenge #378 [Easy] The Havel-Hakimi algorithm for graph realization

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):

Remove all 0's from the sequence (i.e. warmup1).

If the sequence is now empty (no elements left), stop and return true.

Sort the sequence in descending order (i.e. warmup2).

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.

If N is greater than the length of this new sequence (i.e. warmup3), stop and return false.

Subtract 1 from each of the first N elements of the new sequence (i.e. warmup4).

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.

[dailyprogrammer]

[2019-04-08] Challenge #377 [Easy] Axis-aligned crate packing

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, 5, 100, 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

[dailyprogrammer]

[2019-03-13] Challenge #376 [Intermediate] The Revised Julian Calendar

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).

[dailyprogrammer]

[2019-02-15] Challenge #375 [Hard] Graph of Thrones

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.

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.

[dailyprogrammer]

[2019-02-13] Challenge #375 [Intermediate] A Card Flipping Game

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.

[dailyprogrammer]

[2019-02-11] Challenge #375 [Easy] Print a new number by adding one to each of its digit

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.

[dailyprogrammer]

[2019-02-01] Challenge #374 [Hard] Nonogram Solver

Description

A Nonogram (picross or griddlers) is a puzzle where you are given a grid with numbers indicating how many cells should be colored in that row/column. example. The more complex the grid is, the longer it can take to solve the puzzle.

Formal Inputs and Outputs

Inputs

num columns num rows columns rows

Output

Draw the solved nonogram.

Example Input

5 5 "5","2,2","1,1","2,2","5" "5","2,2","1,1","2,2","5"

Example Output

***** ** ** * * ** ** *****

Bonus Challenge

Include color in your input (note: colors don't necessarily have a space between the numbers)

Credit

This challenge was suggested by /u/bmac951, many thanks! Have a good challenge idea? Consider submitting it to /r/dailyprogrammer_ideas and there's a good chance we'll use it.

[dailyprogrammer]

[2019-01-30] Challenge #374 [Intermediate] The Game of Blobs

Description

You are give a list of blobs, each having an initial position in an discrete grid, and a size. Blobs try to eat each other greedily and move around accordingly.

During each cycle, all blobs move one step (Moore neighborhood) towards another blob of smaller size (if any). This blob is chosen as the closest one, with a preference for larger ones, breaking ties as clockwise (11H < 12H > 01H).

At the end of each cycle, blobs merge (with summed size) if they are on the same location.

Return the final state of the blobs.

Example:

Given: [(0,2,1),(2,1,2)] as a list of (x,y and size)

..1 ..1 ..3 ... ..2 ... .2. ... ...

Solution: [(0,2)]

Challenge

[(0,1,2), (10,0,2)] [(4, 3, 4), (4, 6, 2), (8, 3, 2), (2, 1, 3)] [(-57, -16, 10), (-171, -158, 13), (-84, 245, 15), (-128, -61, 16), (65, 196, 4), (-221, 121, 8), (145, 157, 3), (-27, -75, 5)]

Bonus

Help the blobs break out of flatland.

Given: [(1,2),(4,2)]

.1..2 .1.2. .12.. .3...

A solution: [(1,3)]

Given [(0,2,0,1),(1,2,1,2)]

..1 .21 ..3 ... ... ... / / / ... ... ... 2.. ... ...

A solution [(0,2,0)]

Bonus 2

Mind that the distances can be long. Try to limit run times.

Bonus Challenges

[(6,3), (-7,4), (8,3), (7,1)] [(-7,-16,-16,4), (14,11,12,1), (7,-13,-13,4), (-9,-8,-11,3)]

.

[(-289429971, 243255720, 2), (2368968216, -4279093341, 3), (-2257551910, -3522058348, 2), (2873561846, -1004639306, 3)]

Credits

This challenge was suggested by /user/tomekanco, many thanks! Have a good challenge idea? Consider submitting it to /r/dailyprogrammer_ideas and there's a good chance we'll use it.

[dailyprogrammer]

[2019-01-28] Challenge #374 [Easy] Additive Persistence

Description

Inspired by this tweet, today's challenge is to calculate the additive persistence of a number, defined as how many loops you have to do summing its digits until you get a single digit number. Take an integer N:

Add its digits

Repeat until the result has 1 digit

The total number of iterations is the additive persistence of N.

Your challenge today is to implement a function that calculates the additive persistence of a number.

Examples

13 -> 1 1234 -> 2 9876 -> 2 199 -> 3

Bonus

The really easy solution manipulates the input to convert the number to a string and iterate over it. Try it without making the number a strong, decomposing it into digits while keeping it a number.

On some platforms and languages, if you try and find ever larger persistence values you'll quickly learn about your platform's big integer interfaces (e.g. 64 bit numbers).

[dailyprogrammer]

[2019-01-25] Challenge #373 [Hard] Embeddable trees

Today's challenge requires an understanding of trees in the sense of graph theory. If you're not familiar with the concept, read up on Wikipedia or some other resource before diving in.

Today we're dealing with unlabeled, rooted trees. We'll need to be able to represent fairly large trees. I'll use a representation I just made up (but you can use anything you want that's understandable):

A leaf node is represented by the string "()".

A non-leaf node is represented by "(", followed by the representations of its children concatenated together, followed by ")".

A tree's representation is the same as that of its root node.

For instance, if a node has two children, one with representation (), and one with representation (()()), then that node's representation is ( + () + (()()) + ) = (()(()())). This image illustrates the following example trees:

((()))

(()())

((())(()))

((((()()))(()))((((()()))))((())(())(())))

In this image, I've colored some of the nodes so you can more easily see which parentheses correspond to which nodes, but the colors are not significant: the nodes are actually unlabeled.

Warmup 1: equal trees

The ordering of child nodes is unimportant. Two trees are equal if you can rearrange the children of each one to produce the same representation. This image shows the following pairs of equal trees:

((())()) = (()(()))

((()((())()))(())) = ((())(()(()(()))))

Given representations of two trees, determine whether the two trees are equal.

equal("((()((())()))(()))", "((())(()(()(()))))") => true equal("((()))", "(()())") => false equal("(((()())())()())", "(((()())()())())") => false

It's easy to make a mistake, so I highly recommend checking yourself before submitting your answer! Here's a list of 200 randomly-generated pairs of trees, one pair on each line, separated by a space. For how many pairs is the first tree equal to the second?

Warmup 2: embeddable trees

One tree is homeomorphically embeddable into another - which we write as <= - if it's possible to label the trees' nodes such that:

Every label is unique within each tree.

Every label in the first tree appears in the second tree.

If two nodes appear in the first tree with labels X and Y, and their lowest common ancestor is labeled Z in the first tree, then nodes X and Y in the second tree must also have Z as their lowest common ancestor.

This image shows a few examples:

(()) <= (()())

(()()) <= (((())()))

(()()()) is not embeddable in ((()())()). The image shows one incorrect attempt to label them: in the first graph, B and C have a lowest common ancestor of A, but in the second graph, B and C's lowest common ancestor is the unlabeled node.

(()(()())) <= (((((())()))())((()()))). There are several different valid labelings in this case. The image shows one.

Given representations of two trees, determine whether the first is embeddable in the second.

embeddable("(())", "(()())") => true embeddable("(()()())", "((()())())") => false

It's easy to make a mistake, so I highly recommend checking yourself before submitting your answer! Here's a list of 200 randomly-generated pairs of trees, one pair on each line, separated by a space. For how many pairs is the first embeddable into the second?

Challenge: embeddable tree list

Generate a list of trees as long as possible such that:

The first tree has no more than 4 nodes, the second has no more than 5, the third has no more than 6, etc.

No tree in the list is embeddable into a tree that appears later in the list. That is, there is no pair of indices i and j such that i < j and the i'th tree <= the j'th tree.

[dailyprogrammer]

[2019-01-14] Challenge #372 [Easy] Perfectly balanced

Given a string containing only the characters x and y, find whether there are the same number of xs and ys.

balanced("xxxyyy") => true balanced("yyyxxx") => true balanced("xxxyyyy") => false balanced("yyxyxxyxxyyyyxxxyxyx") => true balanced("xyxxxxyyyxyxxyxxyy") => false balanced("") => true balanced("x") => false

Optional bonus

Given a string containing only lowercase letters, find whether every letter that appears in the string appears the same number of times.

balanced("xxxyyyzzz") => true balanced("abccbaabccba") => true balanced("xxxyyyzzzz") => false balanced("abcdefghijklmnopqrstuvwxyz") => true balanced("pqq") => false balanced("fdedfdeffeddefeeeefddf") => false balanced("www") => true balanced("") => true

[dailyprogrammer]

[2018-12-31] Challenge #371 [Easy] N queens validator

For the purpose of this challenge, the N queens problem consists of putting one queen on every column (labeled a, b, c, ...) of an NxN chessboard, such that no two queens are in the same row or diagonal. An example valid solution for N = 6 is:

6 . . Q . . . 5 . . . . . Q 4 . Q . . . . 3 . . . . Q . 2 Q . . . . . 1 . . . Q . . a b c d e f

In chess notation, the squares with queens in this solution are called a2, b4, c6, d1, e3, and f5. We'll represent solutions by listing the rows that each column's queen appears in from left to right, so this solution is represented as the array {2, 4, 6, 1, 3, 5}.

Solving the N queens problem was #25 (difficult) on r/dailyprogrammer, but you don't need to actually solve it for today's challenge.

Challenge

Given an array of 8 integers between 1 and 8, determine whether it represents a valid 8 queens solution.

qcheck({4, 2, 7, 3, 6, 8, 5, 1}) => true qcheck({2, 5, 7, 4, 1, 8, 6, 3}) => true qcheck({5, 3, 1, 4, 2, 8, 6, 3}) => false (b3 and h3 are on the same row) qcheck({5, 8, 2, 4, 7, 1, 3, 6}) => false (b8 and g3 are on the same diagonal) qcheck({4, 3, 1, 8, 1, 3, 5, 2}) => false (multiple problems)

You may optionally handle solutions for any N, not just N = 8.

Optional bonus

In this bonus, you are given an invalid solution where it's possible to swap two numbers and produce a valid solution, which you must find. (Be aware that most invalid solutions will not have this property.)

For example, {8, 6, 4, 2, 7, 1, 3, 5} is invalid because c4 and f1 are on the same diagonal. But if you swap the 8 and the 4 (i.e. replace a8 and c4 with a4 and c8), you get the valid solution {4, 6, 8, 2, 7, 1, 3, 5}.

qfix({8, 6, 4, 2, 7, 1, 3, 5}) => {4, 6, 8, 2, 7, 1, 3, 5} qfix({8, 5, 1, 3, 6, 2, 7, 4}) => {8, 4, 1, 3, 6, 2, 7, 5} qfix({4, 6, 8, 3, 1, 2, 5, 7}) => {4, 6, 8, 3, 1, 7, 5, 2} qfix({7, 1, 3, 6, 8, 5, 2, 4}) => {7, 3, 1, 6, 8, 5, 2, 4}

[dailyprogrammer]

[2018-12-17] Challenge #370 [Easy] UPC check digits

The Universal Product Code (UPC-A) is a bar code used in many parts of the world. The bars encode a 12-digit number used to identify a product for sale, for example:

042100005264

The 12th digit (4 in this case) is a redundant check digit, used to catch errors. Using some simple calculations, a scanner can determine, given the first 11 digits, what the check digit must be for a valid code. (Check digits have previously appeared in this subreddit: see Intermediate 30 and Easy 197.) UPC's check digit is calculated as follows (taken from Wikipedia):

Sum the digits at odd-numbered positions (1st, 3rd, 5th, ..., 11th). If you use 0-based indexing, this is the even-numbered positions (0th, 2nd, 4th, ... 10th).

Multiply the result from step 1 by 3.

Take the sum of digits at even-numbered positions (2nd, 4th, 6th, ..., 10th) in the original number, and add this sum to the result from step 2.

Find the result from step 3 modulo 10 (i.e. the remainder, when divided by 10) and call it M.

If M is 0, then the check digit is 0; otherwise the check digit is 10 - M.

For example, given the first 11 digits of a UPC 03600029145, you can compute the check digit like this:

Sum the odd-numbered digits (0 + 6 + 0 + 2 + 1 + 5 = 14).

Multiply the result by 3 (14 × 3 = 42).

Add the even-numbered digits (42 + (3 + 0 + 0 + 9 + 4) = 58).

Find the result modulo 10 (58 divided by 10 is 5 remainder 8, so M = 8).

If M is not 0, subtract M from 10 to get the check digit (10 - M = 10 - 8 = 2).

So the check digit is 2, and the complete UPC is 036000291452.

Challenge

Given an 11-digit number, find the 12th digit that would make a valid UPC. You may treat the input as a string if you prefer, whatever is more convenient. If you treat it as a number, you may need to consider the case of leading 0's to get up to 11 digits. That is, an input of 12345 would correspond to a UPC start of 00000012345.

Examples

upc(4210000526) => 4 upc(3600029145) => 2 upc(12345678910) => 4 upc(1234567) => 0

Also, if you live in a country that uses UPCs, you can generate all the examples you want by picking up store-bought items or packages around your house. Find anything with a bar code on it: if it has 12 digits, it's probably a UPC. Enter the first 11 digits into your program and see if you get the 12th.