571
\$\begingroup\$

This "sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to main. This is useful because writing a clear and fully specified challenge on your first try can be difficult, and there is a much better chance of your challenge being well received if you post it in the sandbox first.

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

  • Parts of the challenge you found unclear
  • Comments addressing specific points mentioned in the proposal
  • Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

\$\endgroup\$
2
  • \$\begingroup\$ What if I posted on the sandbox a long time ago and get no response? \$\endgroup\$
    – None1
    Commented May 15 at 14:05
  • \$\begingroup\$ @None1 If you don't get feedback for a while you can ask in the nineteenth byte \$\endgroup\$
    – mousetail
    Commented May 29 at 13:27

4704 Answers 4704

1
140 141
142
143 144
157
0
\$\begingroup\$

Counting rankings

\$\endgroup\$
0
\$\begingroup\$

State compression


A long time ago in a challenge far, far away, golfers were tasked with outputting one of three different outputs, depending on whether the input was: OR, one of the other 49 American states' two-letter abbreviations, or something else entirely. The list of these letter pairs looks like this:

AL, AK, AZ, AR, CA, CO, CT, DE, FL, GA, HI, ID, IL, IN, IA, KS, KY, LA, ME, MD, MA, MI, MN, MS, MO, MT, NE, NV, NH, NJ, NM, NY, NC, ND, OH, OK, OR, PA, RI, SC, SD, TN, TX, UT, VT, VA, WA, WV, WI, WY

The standard approach to achieve the task was to search for the input in this string, bar the commas but not the spaces. If the spaces were to be removed, unintended letter pairs would appear within the string. For example, this string would start with ALAKAZ and while the newly formed LA is one of the valid pairs (and hence, did not need to appear again in the search string), the same cannot be said for KA. (And you'd probably anger some people from Kansas. I dunno, I've no idea what people from Kansas get up to.)

But, with some careful rearrangement, the technique could be used in certain places to save a handful of bytes. The string that most solutions ended up using looked like this:

MINCALA MSCTNMNVAKY WAZ PAR FL GA NHID COKSD ME MDE MA MTX NE NJ NY ND MOH ORIA UT WVT WIL WY

Pretty unrecognizable, right? If you look at the first "word", MINCALA, it contains MI, IN, NC, CA, AL, and LA, which are all valid pairs. But if you were to remove the space after it, then you would end up with AM, which is not a valid pair.

Thing is though, I'm still not entirely certain this string is optimal, which is why I'm asking you to...

Challenge

Write a program/function that takes a list of strings of uniform length and outputs the shortest list of combinations that, when combined into a string with some delimiter, contains all the input strings, but no other string of the same length without that delimiter.

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.
  • This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
  • Your code will be scored in bytes, unless otherwise specified.
  • Built-in functions that achieve this (now that's unlikely) are allowed but including a solution that doesn't rely on a built-in is encouraged.
  • Explanations, even for "practical" languages, are encouraged.

Test cases

Yet to come.

This challenge was sandboxed.


Sandbox

  • This title still sucks.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Is it allowed for a string to appear multiple times in the search string? I'm not sure how this could work with nonuniform lengths. What do you mean by a decision-problem? Testing if a given search string is valid? This seems very different, and IMO this question is more interesting. \$\endgroup\$ Commented Feb 3 at 17:47
  • \$\begingroup\$ @CommandMaster I'm not against strings appearing multiple times in the output inherently but I don't know if that can happen in the optimal output. As for the kind of challenge it is, I have decided it'll be a code-golf. \$\endgroup\$ Commented Feb 7 at 12:10
  • \$\begingroup\$ A typical solution may works in \$O((n+1)!k)\$ where \$n\$ is the number of candidate strings and \$k\$ is the size of strings. As the result, it could probably cannot handle any large testcases. \$\endgroup\$
    – tsh
    Commented Mar 6 at 11:17
  • \$\begingroup\$ Maybe testcase "EAB ABC BCA CAB BCE" -> "EABCABCE" use "ABC" twice \$\endgroup\$
    – tsh
    Commented Mar 6 at 11:20
0
\$\begingroup\$

Generate a sequence of \$n\$ consecutive composite numbers

\$\endgroup\$
0
\$\begingroup\$

TYPOGLYCEMIA - Cna Yuo Raed Tihs?

\$\endgroup\$
0
\$\begingroup\$

NDos' Well-Temperament

Objective

Given a positive integer \$n\$, output the ratios in the NDos' well-temperament with \$n\$ notes, as defined below.

NDos' well-temperament

NDos' well-temperament (abbr. NWT) is a musical temperament whose every step is a superparticular ratio. A ratio is superparticular if it equals \$\frac{n+1}{n}\$ for some positive integer \$n\$.

By being octave-periodic, NWT with \$n\$ notes is essentially a multiplicative partition of the rational number \$2\$ with \$n\$ entries.

There is one restriction that ensures NWT to exist uniquely. Amongst such multiplicative partitions, NWT is the partition that comes the last co-lexicographically (That is, the last ratio must be the biggest as possible, the second-to-last ratio is a tiebreaker, the third-to-last ratio is another tiebreaker, and so on) when the ratios are sorted in descending order.

I/O format

Flexible. In particular, since the outputted list consists of superparticular ratios, you can output their denominators only, or output their numerators only. Note that, by doing this, NWT becomes the first partition in co-lexicographic order when the denominators (or the numerators) are sorted in ascending order.

Notes

Musically, NWT will sound better if its ratios are rearranged in a particular way. This challenge won't ask to rearrange them.

Examples

Only denominators are shown for the ratios.

Input, Output
1, [1]
2, [2,3]
3, [3,4,5]
4, [4,5,6,7]
5, [6,6,7,7,8]
6, [6,7,8,9,10,11]
7, [8,9,9,10,10,11,11]
8, [9,10,10,11,11,12,13,14]
9, [10,11,12,12,13,13,14,14,15]
10, [12,12,13,13,14,14,15,15,16,17]
11, [12,13,14,15,15,16,16,17,17,18,19]
12, [15,15,16,16,16,17,17,17,18,18,19,19]

Ungolfed solution (Haskell)

This particular implementation is quite slow upon bigger inputs. Haven't analyzed the time complexity exactly, but I doubt this runs in polynomial time.

import Data.List

colex :: Ord a => [a] -> [a] -> Ordering
colex [] [] = EQ
colex [] _  = LT
colex _  [] = GT
colex (x:xs) (y:ys) = colex xs ys <> compare x y

ndosWT :: Int -> [Int]
ndosWT = go [1] where
    go :: [Int] -> Int -> [Int]
    go [] _ = []
    go [x] 1 = [x]
    go [x] n = minimumBy colex $ do
        m <- [2 .. n]
        let ys = take m [m*x ..]
        pure (go ys n)
    go xs@(x:xs1) n = case compare n (length xs) of
        LT -> []
        EQ -> xs
        _  -> minimumBy colex $ do
            m <- [quot (n + (length xs - 1)) (length xs) .. n - (length xs - 1)]
            pure (sort (go [x] m ++ go xs1 (n-m)))

Optimized version:

import Data.List
import Data.Maybe

colex :: Ord a => [a] -> [a] -> Ordering
colex [] [] = EQ
colex [] _  = LT
colex _  [] = GT
colex (x:xs) (y:ys) = colex xs ys <> compare x y

ndosWT :: Int -> [Int]
ndosWT n = fromJust (go [1] n)
  where
    threshold :: Int
    threshold = 2 * n

    colex_maybe_min :: Ord a => Maybe [a] -> Maybe [a] -> Maybe [a]
    colex_maybe_min Nothing mys = mys
    colex_maybe_min mxs Nothing = mxs
    colex_maybe_min (Just xs) (Just ys) = if GT == colex xs ys
        then Just ys
        else Just xs

    weave :: Ord a => [a] -> [a] -> [a]
    weave [] ys = ys
    weave xs [] = xs
    weave xs@(x:xs1) ys@(y:ys1) = if x <= y
        then x : weave xs1 ys
        else y : weave xs ys1

    go :: [Int] -> Int -> Maybe [Int]
    go [] _ = Nothing
    go [x] 1 = if x < threshold
        then Nothing
        else Just [x]
    go [x] n = foldr1 colex_maybe_min $ do
        m <- [2 .. n]
        let ys = take m [m*x ..]
        pure $ if last ys < threshold
            then go ys n
            else Nothing
    go xs@(x:xs1) n = case compare n (length xs) of
        LT -> Nothing
        EQ -> Just xs
        _  -> foldr1 colex_maybe_min $ do
            m <- [quot (n + (length xs - 1)) (length xs) .. n - (length xs - 1)]
            pure (fmap (\[xs, ys] -> weave xs ys) (sequence [go [x] m, go xs1 (n-m)]))
\$\endgroup\$
0
\$\begingroup\$

String to Lojban!

In the constructed language Lojban, you can express ASCII strings with a literal quote, for example
zoi zoi \d+(\.?\d+) zoi. However, how would you pronounce that?

zoi zoi backslash d plus opening bracket backspash dot question mark 
backslash d plus closing bracket zoi

? Non-English speakers won't understand you. However, there are several ways to assign Lojban words or phrases to ASCII characters. One is shown in the challenge.

So here is the challenge:

The input is a string. You can assume it is composed of only the 95 printable ASCII characters.

The output is a Lojban representation of the string. It should start with me'o , followed by the following substrings in order:

SP -> canlu bu
!  -> saibu
"  -> lubu
#  -> libu
$  -> meryru'u bu
%  -> ce'obu
'  -> y'y
&  -> joibu
(  -> tobu
)  -> toibu
*  -> pi'ibu
+  -> su'ibu
,  -> slaka bu
-  -> vu'ubu
.  -> denpa bu
/  -> fe'ibu
0  -> no
1  -> pa
2  -> re
3  -> ci
4  -> vo
5  -> mu
6  -> xa
7  -> ze
8  -> bi
9  -> so
:  -> zo'ubu
;  -> pi'ebu
<  -> me'ibu
=  -> dubu
>  -> za'ubu
?  -> paubu
@  -> zvati bu
[  -> veibu
\  -> lu'ebu
]  -> ve'obu
^  -> te'abu
_  -> dizlo bu
{  -> lu'ibu
|  -> jabu
}  -> lu'ubu
~  -> nabu

This is a modification of an existing system which can represent all 95 printable ASCII characters.

For lowercase letters, just add y after the letter, with these exceptions:

a  -> abu
e  -> ebu
h  -> y'y bu
i  -> ibu
o  -> obu
q  -> ky bu
u  -> ubu
w  -> vy bu

You can also use tau y'y for h.

For uppercase letters, use tau followed by the corresponding lowercase letter, however h must be
tau y'y bu.

After that, the substrings are joined with a single space, however for readability, no spaces are used between digits.

However, if the string is empty, output lo kutyuenzi.

Examples:

Input -> Output
1 2 -> me'o pa canlu bu re
Hello -> me'o tau y'y bu ebu ly ly obu
1234 -> me'o parecivo
12>1 -> me'o pare za'ubu pa
\d+(\.?\d+) -> me'o lu'ebu dy su'ibu tobu lu'ebu denpa bu paubu lu'ebu dy su'ibu toibu
 -> lo kutyuenzi

This is code-golf, so shortest answer in bytes wins.

\$\endgroup\$
0
\$\begingroup\$

Spot The Difference

\$\endgroup\$
1
0
\$\begingroup\$

Infinite monkeys with autocomplete

You've probably heard of the infinite monkey theorem, which states that a monkey pressing keys on a keyboard at random will eventually type any possible string, the most well-known example being the complete works of Shakespeare. Of course, as the string grows longer and longer, the time taken to type that string becomes exponentially longer. But what if the monkey had an autocomplete?

Our hypothetical monkey starts with an alphabet, containing every possible character that it can type, and a dictionary that initially only contains every letter in the alphabet. At every step, it'll choose a random item from the dictionary and type it. But, the monkey has a helpful autocomplete guiding it to the correct string - if the last two items that were typed, concatenated, are a substring of the correct word that's not yet in the dictionary, it'll add that substring to the dictionary.

For example, let's start with the monkey trying to type the word hello, with the alphabet helo.

l o

It first types l and o and adds lo to the dictionary.

l o h lo l h e

It then types various random dictionary items before typing h and e, and adding he to the dictionary.

l o h lo l h e e e l

After some more random items, it types e and l and adds l to the dictionary.

l o h lo l h e e e l h lo o el e h el

Next, it types h and el and adds hel.

l o h lo l h e e e l h lo o el e h el lo

After typing the el, it types lo and adds ello to the dictionary.

l o h lo l h e e e l h lo o el e h el lo he hel he l o

Next, it types he and l, but because hel is already in the dictionary it's not added. For the same reason, lo is also not added.

l o h lo l h e e e l h lo o el e h el lo he hel he l o h ello

Finally, it types h and ello, creating hello after 24 attempts.

Your challenge is to, given a target word and alphabet containing only lowercase ASCII letters and spaces, simulate this behaviour, choosing random items and building up the dictionary until you eventually create the desired word. The alphabet will not contain any character more than once, and will at least contain every character in the target word.

At every step, you should choose a (not necessarily uniformly) random item from the dictionary, and the words you print should be separated by some consistent and unambigiuous delimiter. Although you do not have to uniformly randomly choose an item, it should be possible for any possible output sequence of strings to occur.

This is , shortest wins!

Examples

Note that this is just one possible output for each input.


word = "abcba", alphabet = "abc" -> "a,a,c,b,b,cb,c,bcb,bcb,a,a,b,cb,ab,cb,b,bcba,bcba,c,b,cb,c,ab,bcba,c,bcb,ab,c,bcba,bcb,bcb,b,bcb,bcba,ab,a,b,a,c,cb,c,bcba,cb,abcb,abcb,ba,ba,abc,a,b,bcb,ab,bcb,a,ba,b,bcb,abc,c,abcb,a"
word = "hello", alphabet = "helo" -> "o,l,h,o,e,e,h,l,e,o,l,o,lo,lo,l,e,h,h,o,lo,h,l,lo,h,o,llo,o,llo,e,o,llo,lo,l,e,e,o,e,o,lo,l,l,ll,llo,h,l,ll,e,h,e,l,he,llo"
word = "hello", alphabet = "abcdefghijklmnopqrstuvwxyz" ->
"k,p,o,d,t,s,c,e,j,b,n,f,h,u,k,b,z,q,f,j,m,e,h,y,m,k,f,q,o,r,q,m,y,o,a,w,b,j,r,d,q,u,k,m,b,j,c,p,p,i,e,h,a,y,l,q,a,k,b,s,l,g,t,f,v,w,c,l,p,b,n,u,h,b,u,e,r,g,u,f,x,b,x,j,p,q,p,i,e,n,x,o,y,u,b,l,b,z,z,x,w,d,p,q,p,i,h,c,i,h,m,j,q,b,b,v,d,e,b,f,f,u,q,z,d,r,a,q,p,v,t,z,o,c,z,c,t,u,n,q,l,i,a,t,f,j,a,d,g,h,s,l,t,v,l,a,t,z,i,l,j,z,x,t,q,o,a,v,q,t,p,e,d,n,p,t,i,d,c,o,r,k,y,t,b,s,l,c,w,l,a,o,y,k,e,u,r,v,t,f,f,e,f,m,v,r,a,k,b,q,q,a,l,y,u,u,m,c,e,l,m,q,b,u,r,n,m,n,f,j,t,s,n,b,t,q,el,b,el,w,d,g,w,c,h,h,x,p,o,q,o,y,r,p,t,t,p,o,j,h,d,g,q,z,d,s,b,g,i,f,g,d,v,w,k,c,u,h,w,c,z,r,el,w,y,b,s,j,l,i,v,o,q,h,l,t,j,n,u,h,p,b,t,s,g,h,i,b,o,r,g,o,q,w,z,p,t,p,k,x,a,g,x,h,k,u,h,a,h,v,b,n,e,u,f,d,k,m,h,e,d,d,c,j,el,i,u,b,n,f,d,x,t,j,t,c,d,j,r,v,r,i,k,d,m,z,n,h,x,p,e,t,q,q,a,b,u,y,r,j,v,l,f,k,el,m,he,c,a,j,r,r,b,he,g,z,t,c,y,x,b,u,i,j,j,x,b,d,he,he,l,g,t,o,v,o,e,f,o,u,j,e,g,z,h,t,i,w,c,a,m,m,i,n,g,t,u,t,q,m,n,c,y,o,t,h,i,h,w,l,t,p,h,i,g,t,he,f,x,n,k,d,g,p,i,w,p,r,g,j,r,e,he,h,t,v,x,e,el,n,e,r,n,y,v,r,f,o,w,d,y,g,n,hel,c,he,k,x,q,k,q,h,l,d,l,he,i,w,h,l,b,k,y,k,h,e,s,s,g,y,x,n,p,c,k,l,he,l,g,k,s,hel,f,a,el,s,w,w,s,h,d,o,w,x,p,el,q,o,b,j,h,p,i,o,j,v,n,q,q,he,d,y,l,s,w,he,v,w,k,a,hel,b,h,t,a,u,s,s,x,y,b,p,d,e,l,y,m,x,w,s,t,hel,m,hel,x,h,p,c,u,h,q,a,i,hel,i,j,hel,x,hel,a,q,el,z,x,m,z,e,t,a,e,z,s,l,j,u,x,q,h,a,c,k,h,y,c,y,a,j,h,m,d,hel,r,q,v,a,f,el,v,p,i,el,c,n,p,a,r,o,s,o,a,hel,c,i,h,he,g,x,j,f,g,c,v,a,he,q,i,e,f,r,y,w,g,e,u,i,q,f,v,o,m,hel,c,u,h,d,o,p,y,s,p,he,el,v,hel,z,he,f,z,h,h,c,r,p,c,p,j,v,z,m,f,y,k,n,a,u,l,x,t,d,v,x,el,hel,e,i,p,c,n,hel,z,k,p,j,d,c,el,y,e,t,h,h,f,e,a,f,w,h,hel,e,el,n,el,m,l,x,t,el,o,t,n,t,o,h,el,c,x,v,hel,j,v,t,i,i,c,hel,p,t,h,z,q,p,w,h,w,x,u,k,q,b,e,w,q,j,s,y,b,i,h,a,c,q,g,hel,hel,l,he,b,d,y,m,hel,v,i,m,l,h,e,j,z,t,x,hell,k,m,y,v,d,n,s,hell,c,x,hel,a,u,hel,f,e,v,hel,c,hel,f,e,j,k,hel,y,x,t,e,hel,j,h,d,u,h,i,h,s,i,c,w,d,he,n,t,y,hel,he,m,hell,x,n,n,x,c,c,i,he,hel,b,j,j,y,v,a,a,g,n,he,v,r,i,p,c,o,r,t,s,hel,hel,y,l,y,e,r,g,b,h,he,el,u,q,i,hel,b,hel,i,w,m,u,q,j,c,b,j,l,s,w,o,s,u,s,c,l,el,s,d,o,q,j,j,e,hell,c,m,x,a,he,n,q,v,s,u,hell,n,e,n,c,x,m,v,v,z,v,b,h,f,o,u,m,l,h,he,el,n,el,b,z,a,o,w,l,i,j,el,n,f,i,e,p,m,c,hel,p,b,j,k,e,u,y,he,v,e,h,i,x,j,o,f,j,o,o,hell,q,d,n,m,j,n,a,a,el,n,b,n,y,a,t,y,f,f,l,p,c,w,el,g,el,hel,j,d,n,he,he,z,a,e,c,w,b,e,el,b,x,n,a,a,x,y,a,hel,a,hell,he,g,g,c,q,l,z,o,x,y,h,r,o,he,q,x,q,x,hell,a,l,o,e,l,k,l,m,w,lo,he,x,l,l,x,o,z,j,i,b,d,g,h,he,i,el,q,l,k,k,a,hel,ll,h,z,m,b,m,j,y,ll,s,v,u,ll,ll,f,f,p,p,m,d,g,g,lo,e,l,w,el,s,el,k,r,c,u,g,hell,o"
word = "hello world", alphabet = "abcdefghijklmnopqrstuvwxyz" -> " ,k,l,q,x,w,d, ,a,o,b,v,h,n,n,i,l,f,u,t,u,n, ,g,j,s,t,i,g,d,f,g,b, ,o,f,t,x,d,q,w,k,d,t,n,d,v,h,e,m,he,s,b,h,w,l,h,x,e,j,o,g,i,f,f,c,h,k,a,y,z,r,j,l,v,k,i,he,p,x, ,f,u,m,d,p,c,s,p,y,e,k,w,u,q,f,f,s,f,f,a,z,w,l,e,v,q,a,r,y,l,u,he,x,z,z, ,k,k,k,i,u,m,q,k,t, ,l,k,he,y, ,z,l,he,x,x,w,n,w, ,l,v,c,o,h,g,e,b,n,q,j,a,c,p,j,he,p,r,w,c,s,l,j,g,j,x,y,i,c, ,q,c,i,j,v,s,r,a,z,c,d,m,f,w,i,z,a,s,t,l,he,a,r,r,he,a, ,v,q,o,r,y,b,n,j,k,d,m,i,t,b,v,q,y, ,y,l,he,r,or,r,t,b, ,a,q,z,h,l,e,w,y,l,t,o,or,d,l,j,h,g,e,h,y,g, ,x,k,g,he,b,r,or,he,he,g,m,t,he,s,j,c,d,v,l,he,e,a, ,or,h,h,g,or,j,u,l,f,o, ,p,k,z,g,q,u,h,j,k,o , ,r,he,o ,e, ,g,x,o,v,b,t,f,q,d,w,p,o,u,j,c,q, ,t,k,q,or,a,he,h,g,v,t,j,g,or,x,h,t,s,t,i,he,d,q,y,t,d,b,d,o ,g,l,l,he,n,e,v,y,x,or,y,g,he,p,k, ,x,d,c,o ,n,o ,or,s,v,q,o ,g,n,he,o,m,o,u,d,z,he,n,o,t,r,p,n,g,g,w,m,o ,b,h,s,or,or,a,n,m,z,r,u,e,i,h,m,v,g,o,g,f,k,p,j,t,v,d,k,c,m,h,x,z,f,f,d,e,o,h,a,m,b,or,ll,k,m,b,e,f,y,or,l,u,v,x,u,h,x,n,p,orl,p,k,p,b,y,x,x, ,a,a,he,a,i,h,d,x,w,or,j,w,wor,ll,h,x,orl,f,j,b, ,c,z,h,z,q,s,h,n,u,he,k,v,x,orl,w,u,r,m,h,g,p,b,j,a,g,i,h,b,d,r,a,k,i,orl,he,l,l,t,ll,or,o,q,ll,j,q,d,h,k,o,n,d,k,e,x,a,d,h,p,c,h,f,i,x,i,e,p,hel,o,he,or,r,s,e,g,j,u,v,v,f, ,e,y,o,u,ll,hel,f,c,n,v,x,f,h,w,x,b,o ,r,h,k,a,x,g,f,s,o,s, ,a,orl,l,v,o ,d,i,orl,x,e,wor,orl,hel,v,wor,f,l,t,j,i,f,w,o ,e,c,y,f,z,v,t,hel,or,s,n,y,g,w,hel,c,v,x,i,j,f,o,j,z,a,p,ll,x,m,e,r,o ,g,q,f,i,j,b,y,v,b,q,e,o ,y,orl,g,v,wor,p,wor,w,d,s,o ,k,h,t,or,a,v,r,p,s,i,t,y,g,l,z,y,a,u,f,c,p,p,b,orl,h,a,g,x,g,s,n,f,x,u,s,b,i,wor,orl,r,orl,f,ll,or,hel,wor,d,d,a,x,hel,o,hel,e,m,wor,f,e,k,x,a,d,p,o ,k,orl,m,m,hel,z,g,j,c,f,j,u,ll,h,d,e, ,t,j,c,f,wor,he,p,orl,d,r,orl,hel,q,b,b,wor,y,p,u,he,z,b,he,h,s,ll,y,wor,a,t,b,c,z,y,y,v,b,o ,d,b,or,s,d,k,q,l,x,b,p,orl,e,x,wor,ll,orl,y,o,l, ,a,g, ,x,d,e,wor,y,t,w,orl,c,f,s,i,c,hel,z,i,w,hel,f,i,y,ll,e,x,g,orld,wor,he,n,c,or,x,ll,ll,s,l,t,ll,l,p,q, ,w,worl,a,q,he,i,x,l,hel,g,o , w,m,c,o ,l,z,worl,j,i,y,n,b, w,b,wor,f,r,u,j,l,u,f,z,z,m,c,orld,c,e, w,ll,m,x,y,u,j,t,hel,o ,b,wor,he,m,d,n,f,orld,or,u,i,i,e,c,q,b,t, w,p,c,t,orl,p,c,o ,q,hel,w,orld,c,e, w,orl,b,r,u,y,ll,g,wor,hel,n,s,d,g,y,j,b,t,q,wor,hel,hel,s,y,b,a,or,n,h,orld,hel,orl,k,ll, ,f,z,o ,u,o, worl,he,o,v,e,or,r,wor,wor, worl,h,he,q,c,q,hel,orld,or,u,p,v,hel,ll,or,x,he,o ,q,ll,he,d,x,o ,orl,o ,z,o,b,world,g,or,s,v,a,o ,r,f,hel,i,r,c,s,q,ll,s,u,h,n,u, w,or,u,world,v,m,w,l,x,wor,o ,n,x, wor,a,g,orl,c, ,n,l,o ,w,k,orld,a,w,x, w,g,hel, ,k,orl,orl,r,v,l,o,o,j,orl,o worl,r,s,worl,wor,l,v,o , worl,z,n,lo ,orl,or,s,hel,world,orl,c,u,hel,z,n,z,c,orl,o w,worl,he,e,b,h,f,u,w,k,orl, wor,k,wor,c,f,orl,o worl,f,y,lo ,x,v,l,o ,c,c,z,lo,a,u,hel,orld,world, worl,orl,y,k,ll,ll,e, wor,d,h,j,a,he,j,orl, w,s, wor,he,j,orld,worl,k,hel,u,b,hel,r,w,hel,g,hel,lo, w,o worl,lo ,w,world,o ,lo w,b,t,l,b,u,q,hello, worl,or,p,hello worl,u, ,o ,o w,hel,or,or,u,z, , ,h,hello,o ,z,t,k,q,b,o w,t,m,he,m,w,worl,t,p,hello worl,k,hel,world,z,c, , w,z,b,f,hel,world,r,x,d,o worl,he,x, w,s,i,orld,o,d,t,hello,r,world,j,hello worl,o worl,he,w,f,e, worl,wor,o, worl,o w,lo, wor,lo wor,s,i,b,o worl,m,b,p,v, worl,b,lo ,worl,world,lo wor,f,orl,y,e,x,k,a,x,e,g,s,j,orl, w,d,orl,worl,s,a,worl,lo wor,lo ,o worl,s,lo worl,w,t,hel,orld,orl, worl,b,ll,g,o ,j,he,lo worl,n, ,he,c,n, worl, ,o worl,orl,p,k,b,he,o worl,z,orl,e,a,k,or,o w,z,w,lo w,z,f,u,k,s,o,he,o worl,m,h,a,k,o w,m,b,a,o,lo w,m,o w,he,a,hello,z,lo ,r,b,ll,l,he,or,hel,u, wor,he,g,t,o ,x,v,world,he,p,w,orl,lo,worl,o w, worl,lo w,b,orl,o worl, wor,r,he,h,hel,q,t,u,lo,w, w,lo wor,d,lo worl,n,hello,lo ,he,hello,lo wor,ll,lo worl,he,z,worl,orl, w, worl,lo worl,g,world,j,z,j,o, wor, wor,b,c,p,orl, wor,p,g,y, worl, ,b,k,q,g,o w,o worl,o ,p,d,orl,lo w,lo w,z,he,n,world,wor,d, worl,or,lo wor, wor,l,t,wor,worl,e,m, worl,z,j,hel,h,or,x,k, w,s,s,hello,b,p,lo w,l,g,p,o worl,j,wor,m, w,o,t,u,u,o,orld,s,u, w,orl,he,world,d,t,g,l,u,hello,n,worl,o w,lo worl,d,p,orl,q,o wor,u,v,or,q,d,c,hello worl,he,j,r,world,wor,o wor,hel,world,l,orld,q,x,wor,x,o ,ll,hello, wo,r,lo wor, ,or,j,o worl,t,hel,n,o,p, w,b,world,world,he,lo world,v,or,wor,o,lo world,lo worl,f,hello worl,u,orl,d, ,wor,z,r,lo w,p,o worl,o wor,b,he,f,hello wo,j,o ,o,or,f, ,o w,d, worl,wor,hel,k,y,hel,x,o worl, wor,g,ll, worl, wor,n, wo,orl,hel, wo,s,orld,he,lo,he, worl,o w,lo world,p,lo ,a,o ,v,c,p,t,or, w,q,f,o , wor,o worl,p,s,world,v,m,w,s,r,a,g,orl, ,z,p,v,j,o,o,r,l,c,q,orld,r,l,g,d,rl,lo wor,k,w,o , ,x,k,o,i,z,h,n,t,n, worl,w,w,s, wo,hel,he,f,lo , ,o worl,s,p,hello worl,r,o w,o worl,o w,j,c,world,lo worl,o ,wor,z,y,lo world,lo world,orld,s,u,hello,orl,lo wor,r,or,t,l,m,ll,worl,b,u, wo,o ,t, ,or,ll,ll,o,o w,llo,e,s,b,t,z,d,u,world,p,orld,wor,hello worl,lo worl,p,a,lo w,orld,w,wor,o w,lo worl,w,j,lo worl, worl,s,g,k,a,o w, ,o,hel,o,s,wor,u,w,p, wor,y,ll,he,j,orld,hello worl, worl,g,ll,o,lo worl,n,o,o worl,orld,m,lo,rl,o ,wor,hello worl,e,t,ll,g,d,d,orl,n,k,x,lo worl,a,q,wor,lo wor,lo worl,rl,o ,a,ll, wo,s,w,o w,e,h,lo,wor,o ,c,or,f,z,hel,lo worl,j,i,b,d,rl,lo ,j,j,o w,llo,i,b,z,c, worl,worl,e,o w,m, worl,wor,v,lo worl, ,r,u,y,g, w,m,r,ll,b, worl,g,o wor,b,a,m,n,orld,he,wor,hello,lo worl,orld, worl, , worl,o,q,b,o,e,rl,u,or, wo,u,o wor,hello worl,ll, ,llo,h, , ,wor,rl,y,l,z,he,orld,lo wor,x,g,n,b,world,j,ll,m,x,x,rl,n,lo worl,o worl,b, w, wo,b,z,x,o,v,or,t,hello,w,p,a,o,p,llo, ,y,d,p,h,c, wor,b,r,rl,u,c, worl,llo ,i,lo ,o ,q,p,w,he,he,b,lo,a,z,a,e, wor,v,or,hello wo,lo wor,m,hello worl,lo world,hello,v,worl,hel,s,llo ,e,d,o w,world,lo wor,lo ,hello worl,worl,w,w,orld,hello,o w,q,u,o ,worl,l,a,w, , wor,u,y,rl,s,p,o w,g,a,rl,v,y,orl,worl,o worl,rl,wor,x,u,or,s,orld,x,o ,q,p, w,z,u,t,d,a,orl,ll,o ,r,i,k,lo wor,p,b,a,ll,d,z,hello worl, ,hello worl, wor,o w,world,ll,world,hello,lo worl,k,llo ,hel,e,or,rl,hello,v,q, wo,lo wor,e,s,o,wor,lo ,o w,o ,or,x,wor,d,q,d,wor,hello wo,world, wo,a,llo ,worl,orld, wor,y,y,lo wor,o w, w,o,k,k,o ,b,llo worl,orld,worl,llo worl,ll,y,lo worl, wo,llo,hello,p, wo,u,hello worl,lo wor,m,n,orl,r,s,a, wor,wor,x,lo,u,lo world,lo world,s,o wor,o ,a,he,q,b,o,rl,o w,q,n, w, worl,e,a,k,o w, wor,a,f,o,hello worl, worl,o wor,z,g,s,o w, ,hello,hel,lo,i,lo worl,g,t,lo,lo world,rl,lo wor,o,t,ll,x,w,g,k,v,rl,he,y,hel,world,o wor,a,lo ,b,orl,lo, worl,q,o worl,world, w,hello wo,h,o ,o ,wor,hello,hel,lo ,b,q,o w,l,t,n,llo,e,q,q,q,lo worl,hello wo,orld,hello wo,h,x,p,z,hel,n,w,f,o wor,w,h,or,u,s,hello worl,hello ,d,d,rl,hello worl,wor,orl,hello,world,ll,lo,m,hello ,d,lo ,i,lo wor,orld,o ,z,m,hello wo,llo worl,ll,lo worl,world,hello ,llo,hello,e,rl,worl,h,llo worl,u,llo ,world,r,y,lo wor,g,z,d,worl,m,or,llo, wo,or,he,x,o worl,i,hello worl,k,f,w, w,o ,lo world,lo w,i,a,w,o ,z,r,hello ,hello ,hello worl,x,s,llo wo,u,worl,hello, worl,hello worl, ,world,t,llo world,rl, ,p,l,lo,lo w,worl,l, , ,rl,llo wo,h,o worl,llo worl,s,s,a,he,orld,p,lo ,i,f,hello wo,a,llo worl,llo,llo wo,he,llo ,b,ll, w,lo worl,i,t,k,world,r,llo ,lo worl,o w,d,j,lo worl,t,w,world,a,s,hello worl,or,hello wo,o ,llo wo, wo,u,orld,hello ,hello , worl,u,n,z,lo,o worl,llo , , wo,e,o wor,x,lo , w, world,s,hello ,lo world, world,worl, worl,b,h,h,q,world,s,c,lo w,d, ,l,hello worl,g,wor,or,t,x,i, worl,lo wor,s,p,s,llo worl,lo world,p,orld,f,k, w,orl, world,i,lo,orld,d,p,b, worl, ,world,b,b,ll,orl,l,a,llo ,p,k,world,i,hel,m,lo world,lo world,rl,world,d,q,r,he,j,hello worl,t,v,llo wo,p,d,g, world,world,r,hello,c,hello worl,llo world,lo world,z,m,t,q,j,t,m,d,n, worl,r,hello worl,lo worl,orl,p,hello ,g,o,rl,c,d,ll,lo w,o w,w,wor,orl, worl,llo world,y,llo world,o w, worl,c,g,lo worl, ,q,lo ,h,he,lo w,worl,lo worl,orld,m,u,wor, w,llo world,q,e,p,hello wo,hello worl,worl, world,s,o ,o ,d,o worl,n,x,world,hello worl,hello ,lo world, wo,x,rl,x,s,llo,lo ,a,hello ,e,q,lo w,world,x,i,o wor,w,z,s,o ,k,k,g,llo ,i,hello wo,lo w, worl, w,c, wor,c,c,lo , wo,lo world,lo,o wor,k,world,o wor,y,lo ,q,s,s, worl,hello ,lo , wor,orl,lo wor,llo,hello wo,wor, w,f, wo,w,k,r,j,o ,orld,i,or,p,b,rl,l,llo,e,rl,o,or,v,hello wo,lo ,w,j,w,hello,o w,hello worl,lo worl,e,i,llo,r,llo ,u,x,w,m,worl,h,wor,o, ,lo,o w,f,hel,c,lo world,b,a,llo worl,g,d,j,k,x,hello wo, world,o wor,llo world,hel,h,llo world,t,q,llo worl,x,h,lo ,v,or,b,u, wor,d,e,b,h,x,w,llo ,h,w, worl,o,hello, w, w,d,hello w,t,q,hello wo,llo wo,rl,m,lo wor,r,lo ,o w,hello,llo world,s,k,q,orld,y,v,hel,l,hello wo,w,a,orld,e, ,p, wor, wo,llo,wor,t,hello worl,f,hello w,wor,lo world,or,j,lo,d,i, worl, ,l,o ,wor,lo worl,g,b,m,s,s,ll,worl,orld,he,hello,rl,q,q,c,o worl,x,llo world,b,rl, ,d,ll,o, ,x,rl, wo,v,hel,llo world,l,hello,n,or,d,he,llo world"
word = "code golf and coding challenges", alphabet = "abcdefghijklmnopqrstuvwxyz " -> too large to fit in post
\$\endgroup\$
1
0
\$\begingroup\$

Morph a string into another

Given two strings consisting of only printable ascii, at least how many operations are needed to morph string a into string b?

The allowed operations are:

  • Take two characters x and y and make every instance of x in string a y.
  • Pick a letter l and delete all instances of it from either a or b, but not both. After deleting a letter l once, you may not delete that same letter l from either a or b again.

For instance, given a = "abc" and b = "ccc", the minimum number of operations is 2.

morph a -> b => bbc
morph b -> c => ccc

If no such sequence of morphs exists, output a value that is distinctable and would never be outputted with any possible input.

Test cases

"abc", "ccc" => 2
"abc", "abcz" => 1
"abbac", "ccbab" => -1
\$\endgroup\$
2
  • \$\begingroup\$ You should be more clear about what string a and b are in the example given. It can't be a -> b -> c if you are trying to get from a to b. also, is it really morphing a to b when you are changing both a and b? \$\endgroup\$
    – Tbw
    Commented Feb 26 at 21:01
  • \$\begingroup\$ Also, you can do the last test case in 4 moves. "ccbab" -> "cca", "abbac" -> "bbc" -> "bba" -> "cca" \$\endgroup\$
    – Tbw
    Commented Feb 26 at 21:03
0
\$\begingroup\$

There are way too few proof golf challenges for my taste, so I'd like to introduce a permanent one.

  • Is it too long or complicated?
  • My data is a work in progress, so there is still time before this challenge could potentially be ready.

The hardest logic puzzle game: Help me reduce my oversized proofs!

I put a lot of work into finding small proofs that elevate smallest-known single axioms to more practical (and popular) proof systems. Some are still large, can you find better proofs based on my data?

This challenge is all about finding some shorter proof(s) based on existing ones. The problems are similar to [CG question: (A → B) → (¬B → ¬A)], but based on different Hilbert systems, and vary in how to display and measure proofs. It also leaves much more choice on what to solve to the contestant. All parts are interconnected and might lead to improve each other. Choosing wisely which of the given pieces to tackle is part of the challenge!

For the sake of this logic challenge, the length of condensed detachment proofs in a certain prefix notation (so-called D-proofs) serves to measure the quality of solutions. The shorter the better!

Note that we use the same metric to measure proofs as in the reference of the best answer to the aforementioned question, in contrast to the amount of formulas that occur in a proof. So looking for multiple occurrences of a formula in the same proof and reducing by referencing only one of them is intentionally not a part of this.

Tournament Rules

All of the following rules are subject to be refined based on experience gained over time.

Rewards

This is an infinite challenge (up until I die and nobody maintains it anymore or I edit the question accordingly – planned: never). I will reward all my reputation points gathered here, down to 101, to best answers, provided they improve by at least 50 steps in total (for 50 points) w.r.t. to the previously given best answer (or my data if there is none), with points up to the number of improved steps (but capped at the maximum bounty of 500 points per solution). Once an improvement is confirmed, I will start the according bounty and award it as soon as possible.
Since I consider this question to be very challenging, I do not expect there to be many best answers in small time frames, but if that happens, I'll schedule the bounties according to timestamps of answers, and put in up to whichever spare reputation points are available when starting the bounty.
(If I do not react in reasonable time due to being absent here, you may comment in the discussions forum related to my project that this question arose from. This will drop me an email.)

There are no plans of using the accepted answer feature. This is in order to not give newcomers the false impression that this challenge has somehow already been ”solved”.
I consider each improvement quite the accomplishment, so I will of course upvote each improving answer, as soon as I found and verified it.

If this endless riddle fascinates you as well and you have spare reputation points (unlike me, at the time of writing this), feel free to contact me and/or edit this section on how you would like to contribute to these rewards.

Regardless, I would very much apprechiate if you could upvote this question so that I am able to reward deserving participants.

Challenge

There are seven theorems to prove in seven similar proof systems. The challenge is to minimize the proofs as much as possible. You may pick any number of theorems to prove in any of these systems, so there can be at most 49 evaluated proofs per solution.
Each combination varies in difficulty, and I will state a subjectively perceived difficulty (range 1 to 10) for each system. In the hardest system (called w2), three proofs are still missing (i.e. finding a proof is worth infinitely many steps regardless of its length). I initially provide D-proofs for all other combinations.

Some proofs are so long that surely there must be shorter ones, but several are already minimal or likely close to minimal, which can be seen by the number of steps covered by an exhaustive search, which I will also provide.

To avoid infinite scoring loopholes, I may treat all subproofs of intermediate theorems to be at most as long as previously shortest-known such proofs.
These proofs and my data are to be used as valuable hints. Starting from scratch would be way too hard, encourage terrible solutions, and break the unlimited scoring system.

Scoring

The score is the number of improved steps. As such it is always relative to the last best solution (which initially I provide). There are no negative scores: If you state a proof longer than a previously known proof, it will be worth 0 points.

For example, say there are two challengers A and B starting based on my data. Now challenger A improves proofs X and Y by 42 and 120 steps, respectively, and challenger B afterwards improves proofs Y and Z (≠ X) by 52 and 330 steps, respectively. Then first A receives a reward of up to 150 reputation points (which is the closest multiple of 50 that is at most 162 = 42 + 120). B improved by 340 = 10 + 330 = (52 - 42) + 330 steps relative to the previously shortest-known proofs, thus receives a reward of up to 300 points. Further assume that I only have 301 (thus 200 spare) reputation points when rewarding A, then A receives the full 150 points, leaving me at only 50 (above 101) left. Afterwards, B receives those 50 points together with those which I acquired in the meantime (multiples of 50, still capped at 300).

Note that there are not only timestamps but also increasing answer IDs to determine sequence of answers, so there can never be a tie in which answer came first. The answer ID acts as a tiebreaker for edits (which could potentially occur in the same second).

Answers

Answers should somehow provide an abstract representation similar to the one I provide, unless a D-proof is short enough to be stated in full (at most a few thousand characters), in which case it can be stated concretely. Of course, you can additionally provide the proof in whichever representation you like, e.g. with all used logical formulas, in infix notation, etc. An explanation on how you succeeded and where you failed would be nice, but is not required.

Only one (the first) answer per user is taken into account, but a proof-shortening edit is treated and scored like a new contribution at the time of editing. When there are multiple edits with multiple improvements, only the last edit is rewarded.

Improvements can be summarized in the title like “(<system>:<theorem>:<steps before>-><steps after>, ...)”, e.g. “(w2:A3:9001->1337, w4:id:465->379)”. However, the scoring will follow a procedure independent from such statements, and I might comment and/or request to edit relevant scoring information.

In case you would like to be mentioned by name (or pseudonym) for your contribution in my corresponding project and potential publications, please state so in your answer or via forum or email, and how. By default, I will use your username on Code Golf Stack Exchange.

You may even do some conventional code golfing to print your solution with as little code as possible. This may grant you upvotes, but no extra tournament points.
But in case your answer has already been rewarded and you find a further improvement, you can edit your answer and receive another reward – after dropping me a message so that I notice your edit. If there was no message and another answer received the corresponding reward due to your edit being unnoticed, your reward is lost (to another person).

Winning

Apart from the relative score, I'd like to treat this like a global game for which one can lead a “highscore” (but with lower numbers being better). Starting with three proofs unknown, the initial value is 3ω+c, where c is the sum of steps of smallest-known proofs, one for each solved target theorem. The game becomes even harder once it progresses, but latest successes automatically grant a top ranking. For that, I'll maintain a table below.

I have hopes that it will someday reach a finite amount close to several thousand steps. It seems plausible that this is possible when looking at high exponential growths in the amounts of theorems when doing exhaustive generations. Quantum computers might help a lot in the forseeable future.

One could say that somebody won this competition, when no other individual is able to find any shorter proofs anymore. But due to the complexity of the problem, this might as well take billions of years. I would guess that there are some alien races doing the same thing: After all, this concerns a few very special systems – all minimal 1-bases for {→,¬}‑propositional calculus.

Hall of Fame

Competitor Total Steps Date Recent Improvements
1. xamidi (profile) 3ω+20869754 Feb 03, 2024 initial proofs

Consecutive entries of the same user will be combined. Please let me know what you wish to be called or whether to link to a different site than only your Code Golf user profile.

Proof Systems

We are exploring the seven minimal 1-bases for classical propositional logic that use operators → (read: “implies”) and ¬ (read: “not”) with modus ponens (⊢ψ,⊢ψ→φ ⇒ ⊢φ, sometimes called “detachment”) as a rule of inference.

This rule can be read as “if (the proposition) ψ is provable and (the proposition) ψ→φ is provable, then thereby (the proposition) φ is provable”. An operator '⊢' for ”is provable” is not part of the propositional language. Propositions merely argue about truth, using '→', '¬', and other propositions. For example, the formula ψ→φ can be read as ”if (the proposition) ψ is true, then (the proposition) φ is true”. Suppose ψ→φ is true. When also ”(the proposition) ψ is true”, it follows via modus ponens that ”(the proposition) φ is true”. This kind of argument is the only one allowed in our proofs. Variables (such as ψ and φ) can be instantiated with arbitrary propositions (i.e. formulas in our propositional language).

Axioms

The axioms of our systems are Meredith's axiom and Walsh's six axioms. These can be stated in our propositional language as follows.

Different axioms are not allowed to be combined with each other. Indeed, each of these formulas is capable of deducing all theorems of propositional logic using only modus ponens as a rule of inference.

In order to save space, I will use standard Polish notation, a most concise (and well-googleable) prefix notation with (→,¬)=(C,N) for up to 26 different variables p,q,...,z,a,...,o, to state conclusions in proof summaries. You may use whichever well-defined formula representation suits you. Actually, a formula is simply a tree structure – follow the links in the leftmost column for graphical representations. A general way (which works for more than 26 different variables) to concisely state formulas is to use numbers as variables and separate them via ., e.g. CCCCC0.1CN2N3.2.4CC4.0C3.0 for Meredith's axiom.

Target Theorems

The target theorems are themselves axioms of popular proof systems, such as {A1,A2,A3} (“Łukasiewicz (L_3)-system”) and {L1,L2,L3} (“Łukasiewicz (L_1)-system”). Propositional axioms of Metamath's main proof database set.mm are also A1-A3.

Infix notation Polish notation
A1 ψ→(φ→ψ) CpCqp
A2 (ψ→(φ→χ))→((ψ→φ)→(ψ→χ)) CCpCqrCCpqCpr
A3 (¬ψ→¬φ)→(φ→ψ) CCNpNqCqp
id ψ→ψ Cpp
L1 (ψ→φ)→((φ→χ)→(ψ→χ)) CCpqCCqrCpr
L2 (¬ψ→ψ)→ψ CCNppp
L3 ψ→(¬ψ→φ) CpCNpq

Proving all axioms of a different proof system that is known to be complete (such as A1-A3 and L1-L3 both are under modus ponens) proves that the original system is complete by itself. There are also non-constructive ways to prove this, which is how we know that w2 is complete under modus ponens, despite such proofs still being unknown. The length of such proofs could help in finding proof theoretic bounds, which are still a big mystery in the field of proof complexity.

The authors of Walsh's paper called the task to find D-proofs from w2 to another system an “open challenge problem for automated reasoning”. Based on my data, it only remains to find a D-proof for L1. This is, however, by far the hardest optional part in this callenge, and I sure do not recommend it to anyone who does not wish to put an outstanding amount of effort into this.

Proof Notation

The operator for condensed detachment is the so-called D-rule, which takes two formulas as arguments, on which it applies tree unification to form the most general unifiers of ψ→φ and ψ, respectively, then applies modus ponens, which results in φ. Axioms in D-proofs are referred to by 1,2,…,9,a,b,…,z in their given order.

This way, given a sequence of axioms, a proof can be defined by a single prefix formula, e.g. DD211, which is evaluated like D(D(2,1),1), i.e. D is a 2-ary (partially defined) operator over the language of logical formulas.
The D-rule is only partially defined because unifiers to apply modus ponens on certain formulas may not exist.

Example

Let's determine DD211 for axioms (1,2):=(A1,A2). At first D21 entails that ψ→φ and ψ are instances of A2 and A1, respectively. Most general such unifiers are the instances (χ→(ξ→χ))→((χ→ξ)→(χ→χ)) and χ→(ξ→χ) of A2 and A1, which implies ψ := χ→(ξ→χ) and φ := (χ→ξ)→(χ→χ). Therefore, (χ→ξ)→(χ→χ) (i.e. CCpqCpp in Polish notation) is an intermediate theorem in DD211 = D(CCpqCpp)1. This entails that now ψ→φ and ψ are instances of (χ→ξ)→(χ→χ) and A1, respectively. Most general such unifiers are (χ→(τ→χ))→(χ→χ) and χ→(τ→χ), thus ψ := χ→(τ→χ) and φ := χ→χ. Therefore, DD211 proves the theorem χ→χ (i.e. Cpp in Polish notation). Combined, the D-proof DD211 w.r.t. (A1,A2) actually means:

Proposition Reason
1. ψ→(φ→ψ) (A1)
2. ψ→((φ→ψ)→ψ) (A1)
3. (ψ→((φ→ψ)→ψ))→((ψ→(φ→ψ))→(ψ→ψ)) (A2)
4. (ψ→(φ→ψ))→(ψ→ψ) (MP):2,3
5. ψ→ψ (MP):1,4

Alternatively, using Polish notation:

  1. CpCqp (1)
  2. CpCCqpp (1)
  3. CCpCCqppCCpCqpCpp (2)
  4. CCpCqpCpp (D):2,3
  5. Cpp (D):1,4

There are no such small examples in our single axiom systems, for example D11 in Meredith's system is already

  1. CCCCCqsCNCNpNtNrCNpNtpCCpqCrq (1)
  2. CCCCCCqsCNCNpNtNrCNpNtpCCpqCrqCCCCpqCrqCqsCtCqs (1)
  3. CCCCpqCrqCqsCtCqs (D):1,2

and formulas tend to blow up in size for longer proofs.
This illustrates that using formula-based proofs is extremely inefficient, whereas D-proofs are much lighter and can be processed by machines more efficiently.

Challenge Proofs

I will try to keep this information up to date.

The smallest-known D-proofs of target theorems have the following amounts of steps.

exhausted A1 A2 A3 id L1 L2 L3 overall difficulty
m 83 (+2) 13 7001 175 19 619 163 41 not easy - 5/10
w1 161 (+2) 33 1927 363 143 151 323 87 not easy - 5/10
w2 43 (+2) 53 - - 35 - 781 57 horrible - 10/10
w3 73 (+2) 67 18391835 1193987 135 1196969 6541 127 very hard - 8/10
w4 169 (+2) 59 16277 12959 465 14261 1889 53 bulky - 6/10
w5 55 (+2) 83 157 95 65 15 107 51 convenient - 3/10
w6 95 (+2) 19 18339 297 13 2743 125 37 not too bad - 4/10

For example, to the best of my knowledge I searched Meredith's system exhaustively for D-proofs of up to 83 steps. Since all its D-proofs have an odd length, all its smallest-known D-proofs with up to 85 steps are thereby minimal and cannot be reduced further. That is, if my search was actually exhaustive.

My (subjective) overall difficulty rating accounts for how hard I find searching and handling proofs, not for the apparent complexity of a system (which is indicated by “exhausted” – the higher the longer proofs are on average). The issue with a lower difficulty rating is that the given proofs might be so short already that it is very hard to find a smaller one (if it even exists). On the other hand, more difficult systems potentially give higher rewards.

Compact representations of these proofs are given below. Unfolding some of them results in exponential blowup, which explains the high number of steps asserted for concrete D-proofs. Index numbers of target theorems are highlighted as bold. More detailed and commented variants representing the same D-proofs are linked over the system names right to the bullet points (and as “[sample]” in my project's readme).

Puzzle Board (Abstract Representation)
    CCCCCpqCNrNsrtCCtpCsp = 1
[0] CCCppqCrq = D1D1D11
[1] CpCqp = DDD11[0]1
[2] CCCpqrCqr = D1D1D[0][0]
[3] Cpp = DDD[0][0]11
[4] CpCNpq = DD1[2][2]
[5] CCCpNCCCqrCNNqrNstCst = D1D1D[0]D1DD11DDDD1D1DD1DD11[0]111D1DD1D1D[1]D1D111
[6] CCpCpqCrCpq = DDD1D1D1D[0][5]11
[7] CCCpCqNCCrCNNssNqtCut = D1D1DD1DD1DDD1D1D[2]1D111D1D1D[0]D1DD11DDDD1D1DD1DD11[0]111D1DD1DD1D1D[0]1[1]D11DD1D11D11
[8] CCNppp = DD[6]DDD1D1DD1D1D[1]D1D11D[2]D[2]1111
[9] CCNpNqCqp = DDDDD1D1DD[2]1D[2]D[5]D1D1111DD1D1DD1D1D[2]1D11[1]1
[10] CCpqCCqrCpr = DD1DD1DDD[6][6]1[7]D1DDD[6][6]1[7]1
[11] CCpqCCrpCrq = DD[10]DD1DD1[7]1DD[6][6]1D[10][10]
[12] CCpCqrCCpqCpr = DD[11]D[10][10]DD[10][10]D[11]DD[6][6]1
    CCpCCNpqrCsCCNtCrtCpt = 1
[0] CCNpCCqrpCrp = DD1D1D111
[1] CCCCpCCNpqrstCst = D[0]D1D11
[2] CCCpqrCqr = D[0]D1D1D11
[3] CpCCNqCrqCrq = D1D[2]D[0]D11
[4] CpCCNqCCNrsqCrq = D1DDDD[2]111D1D1D11
[5] CpCqp = D[2][1]
[6] CpCNpq = DD[0][4]D[0][3]
[7] CCCCNNpCpNpqrCpr = D[0]D1D[1]D[1]DD[0]D11DD[0]D11[2]
[8] CCNpCqpCrCCNsCpsCqs = DD[0]DD[2]1DDD1DDD[1]1D1111D1DDD[1]1D111D[2]1
[9] Cpp = DD[4]1D[7][2]
[10] CCpqCCqrCpr = D[2]DD[0]D1[8][2]
[11] CCCCpqCrqsCCrps = D[0]DD[2]1DD[0]D1DDD[1]1D1D1D111[10]
[12] CCCCNpCqpprCqr = D[0]D1DD[0]D1D[1]D[1]1DD[0]D11D[0]DD[1]D[1]1D[7]D[0]DD[2]1[5]
[13] CCNppp = D[0]D[12]D[0][3]
[14] CCNpNqCqp = DD[2]DD1DD[0]D1D[2][8]D[0]DD[2]D[1]D[2]1D[7][2]1D[4]1
[15] CCpCqrCCpqCpr = DD[11]D[0]D1DD[0]D1D[1]D[2]1DD[0]DD[2]1DD[0]D1DDD[1]1D111[2]DD[0]D11D[0]DD[1]D[2]1D[7]D[0]DD[2]1[5]D[11]DDD[3]1DD[0]DDD1D111DD[0]D1DDDD[1]D[2]1D[1]D[2]DD[0]D11[6]1D1DDD[1]1D1D1D111D[2]D[2]DD[0][4]1D[12][2]DD[0]DDD1D111DD[0]DD[2]1D[0]D1DD[0]D1D[1]D[2]1DDDD[2]1D[0]DD[2]1DD[3]1DD[0][4]D[0]D1DDD[1]1D1111D11DD[0][4]1D[1]D[1]DD[0]D1DD[0]DD[1]1DD[0]D1DD[0]D1DDD[1]1D1111[2]1[2]
  • w2:   (missing: CCNpNqCqp,CCpCqrCCpqCpr,CCpqCCqrCpr)
    CpCCqCprCCNrCCNstqCsr = 1
[0] CpCCNqCCNrsCNqCCNCCNtCCNuvNpCutwNCxCCyCxzCCNzCCNabyCazCrq = DDDDD111111
[1] Cpp = DDD11DDD11D11[0][0]
[2] CpCqCrCsCtq = DDDDD1DDD11DD1D111[0]1[0]11
[3] CpCqp = DDD1D[2]1D111
[4] CpCNpq = DDDDD1D111[0]DDD11DDD1D111[0][0]1
[5] CpCqCrp = DDD11DD11DDD1D111[0][2]
[6] CCNppp = DDDDD1[1]1DDDD11DDD1[5]D11DDD11DDD1D111[0]1DDD1DDDD11D1DD1DDD1[0]D1111[0]DDD11D1[0][0]DDD1D1D[2]11[0]DDDDD11111[0]1DDDD11[5]DDD1DDD11D1DDD11DDD1D111[0]1DDD11DDD1DDD1DD1D111111[0]1DDD1DDD1DDD1DDD1[0]D1111[0]1[0]1[0]DDDDD11111[0]1DDD1DDDDD1D111[0]DDD11DDD1D111[0][0]DDD11DDD1111DDD11DDD1DDD1DDD11D11[0]111[0]1D1[1]DDDD11D11[0]DD1[3]1
    CpCCNqCCNrsCptCCtqCrq = 1
[0] CCCpCCqrCsrtCCCqrCsrt = DD1D111
[1] CCCpCqrsCCqrs = DD1DDDD111D[0]D11D111
[2] CCCpqrCqr = DDDDD[1]D111D[0]DD1111D11
[3] CCCNpqrCpr = DD11DDDDD111D[0]D11D1D11[1]
[4] CCNpCCNqrCCCCCCstuCtuvCCvwCxwyCCypCqp = D1DDD1[0]1D[0]DDDD[1]D11111
[5] CCNppCqp = DD11D[3]D11
[6] CpCqp = DDDDD[1]D111DD[1]D11111
[7] CpCCpqCrq = DDD1D11DDD[0]D[0]D1D[0]D1D11[0][1]D11
[8] CpCqCrp = D[2]D[1]DDDD111D[0]D11D11
[9] CCCNpqCCCCNrsCCtCutvCCvwCrwxCCxyCpy = D[1]D1D[1]D1[6]
[10] CCCCCpqrCsrtCqt = DD[1]DD[0]D[1]1[5]1
[11] CpCNpq = D[3]DD[0]D11[5]
[12] CCCpCqrsCrs = DD1[5]DDD[0]D[0]D1D[0]D11DD1[0]1[1]
[13] Cpp = DD[3]DD11[7]1
[14] CpCNNCqrCsCqr = DDD11DDD[1]DD[0]111DD[0]D[0]D1D11[0]DD[1]D[0]D1D[1]D1[6]DDD11DDD[1]DD[0]111DD[0]D[0]D1D11[0]DD1D11DDD11DDDDD111D[0]D11D1D11DD11DDD[0]D[0]D1[0]DD1DD1111[1]DDD11DDD[0]D[0]D1DDD1[0]1[0][1][1]DDDD111D[0]D11D1D11
[15] CCNCCppNqrCqr = D[9]DD1[13]D[14][14]
[16] CCNNpqCpq = D[9]D[4]D[2]DD[9]D[4]D[15][8][8]
[17] CpCqCrNNp = D[16][8]
[18] CCpqCNNpq = D[9]D[4][17]
[19] CCNpqCNCrpq = D[9]D[4]D[18]D[2][17]
[20] CCNpqCNCrCspq = D[9]D[4]D[18]D[12][17]
[21] CCCpqCNprCsCNpr = D[4]DD[9]D[4]D[18]D[3][17]D[10]D[7]D[3][15]
[22] CCNppp = D[16]DD[5]DD[9]D[4]D[3][17][5]D[5]DD[9]D[4]D[3][17][5]
[23] CCpNCNppCqNCNpp = D[4]D[18]D[10]D[7]DDD1[13]DD[4]D[19][8][7][22]
[24] CNCpqCrCsp = DDDDD1[13]DD[4]D[19][8][7][16]DD[4]DD[9]D[4]D[18]D[3][17][8]D[18]D[4]D[19][8]D[20]DD[21]DDD11DDD[0]D[0]D1[0]DD1[0]1[1]DDDD111D[0]D11D1D11DD[21][21]D[21][21]
[25] CCpCpqCpq = DDD[4][24]D[4][24]DD[4][24]D[4][24]
[26] CCpqCNCprq = D[9]D[4]DD[25][21]D[16]D[2]D[1]D[1]DDDD111D[0]D11D11
[27] CCCpqrCNpr = D[9]D[4]D[26][17]
[28] CCpqCCNppq = DD[1]D1D1D11D[4]DD[9]DD[9]D[4]D[18]DD[9][23][8]D[27][23][8]
[29] CpCCpqq = DDD[25]D[4]D[19][24]DDD[1]DD[0]111D[0]D[0]D1D[0]D11DDD1[6]DD[4]D[19][8][7][25]
[30] CCpqCCNqpq = D[4]DDD[1][4]D[28]D[10][25][28]
[31] CCNpNqCqp = D[16]DD[25]D[4]D[19][24]DD[30]D[2]D[3][15]D[19]D[25]DD[9]D[4]D[3][17][20]
[32] CCpqCCqrCpr = DDD1[26]D[6]D[28][29]DD[28][12]D[20]1
[33] CCpCqrCqCpr = DD[32][32]D[32][29]
[34] CCpCqrCCpqCpr = D[33]DD[32][32]DDD[28][12]D[20]1DD[33]D[27][30]D[33]DD[32][32][27]
    CpCCNqCCNrsCtqCCrtCrq = 1
[0] CpCCNqCCNrsCtqp = DDD1111
[1] CpCNCqrp = DDD111DDDD111D[0]11
[2] CCpCNqCCNrsCtqCpCCrtCrq = DD11D[1]1
[3] CCpqCpCCNrCCNstCurq = DD11D[1]D[0][0]
[4] CpCNpq = DDD11D[1][0]DDDD111D[0]11
[5] CpCqp = DDD111DDD11DDDD11D[1]DDD111D[0]1111
[6] CCpqCpCrq = DD11D[1]D[0][5]
[7] CCpNNqCpq = DD11DDD11D[1]D[3][0]DDDD111D[0]11
[8] CCpqCCrpCrq = D[2]D[6][0]
[9] CCpCqNqCpCqr = DD11D[1]D[0]DD11D[2]DDDD111DD111DDD11D[1]D[3][0]DDDD111D[0]11
[10] CCpqCpNNq = DD[2][3]D[9]DDD11D[1]D[0][7][5]
[11] Cpp = DDDDD[2]DD11D[1]D[0]D[3][5]D[6]DDD11D[1]D[0]DD11DDD11D[1]D[0]DD11D[1]D[0]DDD11D[1][0]DDDD111D1111DDD111D[1]1111
[12] CCNppp = D[7]DDD11DDD[2][3]D[1]D[6]D[9][5]DDD[2][3]D[9]DDDD11D[3]D[2]DDD11D[1]D[0]DD11D[1][4][1]DD1111DDDD11D[3]D[2]DDD11D[1]D[0]DD11D[1][4]DDD111D[1]1DD1111D[9][10]
[13] CpCCpqq = DDD[8][12]D[9]D[8]D[10][5]DDD[2][3]D[1]D[9][5]DDD[8][12]DD11D[1]D[0][4]DDD11D[1]D[0][6]DDD11D[3]DDD11D[1]D[0][4][5][11]
[14] CCNpNqCqp = DD[8]D[13][11]D[2]D[8][13]
[15] CCpqCCqrCpr = DDDD[8]D[13][11]D[2][3]DD[8][13]DDD11DDD11D[1]D[0]DDD11D[1]D[3][5]DDDD111D[0]11D[6]D[9][5][11]DDD11D[1]D[0][6][8]
[16] CCpCqrCCpqCpr = D[2]D[6]D[15][12]
    CCpqCCCrCstCqCNsNpCps = 1
[0] CCpqCCqrCpr = DD11D1DD11D1D11
[1] CCCpCqrCCCsqtCNqNsCsq = DDD11DD1D11D1DD1D11DD11D1DD11D1DD1D1DD11D11D1D111
[2] CpCNpq = D[1]1
[3] Cpp = D[1][0]
[4] CpCqp = DDD11DDD11DDD11D11D1DDD11DD11D1DD11D1DD1D1DD11D11DD11D1DD11D1DD1D1DD11D11D1D111D111
[5] CCNpNqCqp = DD1DD11DD1D1DD1D1D1D11D1D11D1DD1D11D1D11D1D1[2]
[6] CCNppp = DD1[0]DD11D1DD11D1DDD11D1D1DD11D1D1DD11D1DD11D1DD1D1DD11DD1D1DD1D1D1D11D1D11D1DD1D11D1D11D11D11
[7] CCpCqrCCpqCpr = DDD11D1D11DD1DD11D1DDD11D1[1]DD11D1DD1D1DD11D1DD11D1DD1D11D11D1D11D1DD11D1D1DD11D1DD11D1DD1D11D1[0]
[...989 bytes in 19 lines ommitted to fit into the sandbox...]

Where do I even start?

I called this a puzzle game for good reasons: Proofs for different theorems are components which can be used to build new components when arranged in a specific (and potentially very difficult to find) way. When it comes to snapping formulas together in order to create another one, things behave the same in all D-systems.

The above abstract proof representations hide many utilized formulas, but these can be viewed using pmGenerator to display the “full summary” mentioned in the linked proof files – deriving them by hand is probably too much of a workload. It may be useful, however, to write your own code to assist with this kind of work, and to follow your own ideas.

[...] (Does not fit into the sandbox.)

Data & Tools

pmGenerator

[...]

Prover9

[...]

TPTP / Vampire

[...]

\$\endgroup\$
2
  • 4
    \$\begingroup\$ So, uh, I didn't really read this, but it looks long and complicated. Is there a small simpler part that you could split off into a self-contained bite-size challenge? It's common here to post an easier version as Part 1 and follow it up with a Part 2 later. \$\endgroup\$
    – xnor
    Commented Feb 14 at 23:58
  • \$\begingroup\$ There are a few problems with splitting up, like big gaps in difficulty for different systems and theorems, and potential loss of focus for what is essentially a never-ending interconnected challenge. I am currently thinking that Puzzling might be the better platform for this. \$\endgroup\$
    – xamid
    Commented Feb 15 at 2:48
0
\$\begingroup\$

Contract a tensor

\$\endgroup\$
0
\$\begingroup\$

Find the odd one out

\$\endgroup\$
3
  • \$\begingroup\$ I don't think this is a duplicate, but I hope you realize this is extremely easy, Vyxal and a few other golfing languages have 1-byte solutions for this \$\endgroup\$ Commented Feb 27 at 3:02
  • \$\begingroup\$ I don’t think that’s a good reason to add arbitrary tasks to your still simple challenge \$\endgroup\$ Commented Feb 27 at 16:59
  • \$\begingroup\$ If you create a new challenge you should create a new sandbox post, not edit an old one \$\endgroup\$ Commented Feb 28 at 8:04
0
\$\begingroup\$

Define a set containing N elements

Consider a simple language that allows making basic statements about sets. It is defines as follows:

  • = 0 1 Sets 0 and 1 are equal. Variables are referenced using De Bruijn Indexes
  • < 0 1 Set 0 is an element of set 1
  • & a b Expression A and expression B
  • ! a Not A
  • A a b B holds for all elements of A. Defines a new variable

We use polish notation here, a simpler format that avoids much parsing.

Challenge

Given a number N. give an expression in this language that will return true if the first variable is a set that contains exactly N elements. The formula does not need to be optimal.

Examples

  • 0: A 0 ! = 0 0 (All elements must not be equal to themselves)
  • 1: & ! A ! = 0 0 A 0 A 1 = 0 1 (Not all elements are not equal to themselves, and all elements must equal all other elements)
  • 2 & ! A ! = 0 0 & ! A 0 A 1 = 0 1 & A 0 A 1 A 2 ! & ! & ! = 0 1 ! = 1 2 ! = 0 2 (For each set of 3 elements, at least 2 must be equal)

There are many different ways to encode a given number, you may pick any of them arbitrarily.

Goal is to make the generating code as short as possible.

\$\endgroup\$
0
\$\begingroup\$

Soundex

Note: This question was asked previously but it was not very well specified. I'd like to ask it again with a proper spec

Given a string containing only ASCII lowercase letters, output its Soundex code. Soundex is an algorithm originally described by Donald Knuth to give words that sound similar the same index, as a form of fuzzy searching.

We'll use a slightly modified version that removes the padding step. It works as follows:

  • Remove all instances of h, w, or y except the first letter
  • Replace all remaining consonants, except the first letter, based on the following table:
Consonant Code
b, f, p, v 1
c, g, j, k, q, s, x, z 2
d, t 3
l 4
m, n 5
r 6
  • Remove any successive instances of the same number. Also remove any numbers after the first that would have the same number as the first letter
  • Finally, remove all the vowels, except the first letter

Worked out example

  • Lets take the string "squeezers"
  • First, we remove all h, w, or ys. There aren't any.
  • Then, we replace all consonants except the first with numbers. This creates s2uee2e62
  • Now we remove all successive duplicates. We remove the first 2 since s would map to 2. This creates suee2e62
  • Finally, we remove vowels to create s262

Test Cases

Word Soundex
squeezers s262
batman b355
robert r163
roberto r163
clarinet c4653
amazing a5252
whole w4
hole h4
asbestos a21232
yankee y52
\$\endgroup\$
0
\$\begingroup\$
\$\endgroup\$
1
  • \$\begingroup\$ Cyclic maximal words are also known as Lyndon words (the usual definition is for minimal words, but that doesn't really matter) \$\endgroup\$ Commented Mar 19 at 18:45
0
\$\begingroup\$

Find the missing side in a right triangle

You've solved for the legs when you have the hypotenuse. You've solved for the hypotenuse when you have the legs. But can you code golf a program to do both?

Input: three lines from stdin, for leg a, leg b, and hypotenuse. One line will be blank, which is the variable your program must solve for. All input will be integers.

Output: The missing side, as a float with at least 3 digits after the decimal. Leading and trailing whitespace is OK.

Scoring: Least bytes wins!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I suggest not being so strict with input and output. We typically allow function input in addition to stdin, as well as fractions in addition to floats. \$\endgroup\$
    – chunes
    Commented Mar 20 at 22:57
0
\$\begingroup\$

Given a non-negative integer,

  1. Write the integer into base64, and store into bytes
  2. Set each bit 7 to 1 but the last byte.
  3. Set each bit 6 to 1 but the first byte.

In this way an integer has clear edges. Notice that 0x80 is unused.

Questions:

  1. Given an input, encode it.
  2. Given some bytes, decide whether it's complete, incomplete or invalid.
  3. Given some bytes, assuming not invalid, decode all numbers inside.

Test cases

         0 => 00
        63 => 3F
        64 => 81 40
       132 => 82 44
      4096 => 81 C0 40

Sandbox Notes

  • Is such encoding named?
\$\endgroup\$
0
\$\begingroup\$

Choose a language or its subset, write a program in it that, compute some function bool f(Program P, Int T) such that:

  • If f(P,T), then f(P, T+1)
  • lim[T->∞] f(P,T)=true iff P halts

Notes:

  • This is a component for a bounded busy beaver solver, by storing the program with largest running time. This task actually asks for a definition of running time.
\$\endgroup\$
1
  • \$\begingroup\$ This is fairly similar to Compute the Uncomputable. Also, does the program have to be in the same language or just in any turing complete language? \$\endgroup\$ Commented Mar 23 at 13:06
0
\$\begingroup\$

Input part of staff, output its midi.

Symbols:

  • 0-9: octave symbol. Set O = the value.
  • CDEFGAB: a note.
    • If octave is just set, then use the octave.
    • Otherwise, if the distance to last note is larger than 5 (C-A, D-B or C-B),
      • Increase O by 1 if the new note is C or D; decrease if A or B.
    • Output O*12+{C:0, D:2, E:4, F:5, G:7, A:9, B:11}+K[O,c]
  • #, b, ##, bb, %: accidentals. Set K[next note] to 1, -1, 2, -2, 0, respectively.
  • |: bar line. Reset accidentals. (Since beats are not given, bar line doesn't have other meaning.)
  • You can assume all outputs are in [0,127], accidentals appear before octave if both exist, no double octave, octave or accidental to bar line, first note has octave provided

Test cases:

4CCGG|AAG => 48,48,53,53,55,55,53
4CDEFGAB|C4G5C => 48,50,52,53,55,57,59,60,55,60
5E#DEDE4B%DCA => 64,63,64,63,64,59,62,60,57
4C#CFAC => 48,49,53,57,60
#0D#E||##F#G#A#B||##C#D => 3,5,7,8,10,12,14,15
0EDCB => (invalid)
A#|B => (invalid)
10C => (invalid)
#9B => 120
9BCDEFG => 119,120,122,124,125,127
9BCDEFGA => (invalid)

  • Should I have key signatures?
  • Should I shift octave by 1?
  • s and f or # and b?
  • are triple accidentals allowed?
\$\endgroup\$
3
  • \$\begingroup\$ I would keep it simple: note to midi rather than staff to midi to avoid confusing nonmusicians, so no key signatures and no multiple flats/sharps. #`` and b` are used almost universally. That leaves the choice of natural symbol, I would probably go for something nonalphanumeric like ~ or & . I suppose you could keep the bar to reset accidentals to avoid making it too simple. \$\endgroup\$ Commented Mar 24 at 15:09
  • \$\begingroup\$ The octave change needs some thinking about. I would suggest sticking with the standard octave CDEFGAB, although this means octave change when you move between nearby B and C. I appreciate what you're trying to do with your "larger than 5" system but the interval (at least if expressed in letters) needs to be smaller. C to F could be a default up change, and C to G a default down change. C to G is known as a fifth in 1-indexed musical notation, though it's actually only a change of 4 letters in 0- indexed. \$\endgroup\$ Commented Mar 24 at 15:13
  • \$\begingroup\$ @LevelRiverSt I'm recently on Braille Music, where 4th and 5th by default remain in same octave. Lilypond just use the nearest one, though \$\endgroup\$
    – l4m2
    Commented Mar 25 at 2:54
0
\$\begingroup\$

Number houses in a street

House numbering varies across the world, and sometimes within a country, but the traditional numbering system in my country is to have the odd numbers ascending on one side of the street and the even numbers ascending in the same direction on the other side of the street. Here is an example:

9 |
  | 10
  | 8
7 |
5 |
  | 6
  | 4
3 |
1 |
  | 2

Here there are two detached houses, one at each end of the street, and four pairs of semi-detached houses. The empty spaces are probably where the garages and driveways are, but they are not relevant here, so I have left them out.

Your challenge is to write a program or function that will take an unnumbered street and number it.

You can input the houses in any convenient way, so you could take input as a diagram but with the houses marked by a fixed placeholder (e.g. ?), or you could take a pair of lists of distances of each house from the start of the street (so for the above example the input could be [[1, 2, 5, 6, 9], [0, 3, 4, 7, 8]].) Note that there may be two houses directly opposite each other, and there may also be different number of houses on each side of the street.

As well as numbering from the bottom left up, you may also number from the top right down, like this:

 2 |
   | 1
   | 3
 4 |
 6 |
   | 5
   | 7
 8 |
10 |
   | 9

The house numbers on the left of the street must be right-justified and those on the right of the string must be left-justified. The street can be marked with any fixed non-empty non-numeric string of your choice; it doesn't have to be | .

In addition to the above two output formats, I will also allow any rotations (but not transpositions) of the above output formats, in case that is helpful for you, e.g.

 0
 18  64  2
==========
9  75  31
\$\endgroup\$
0
\$\begingroup\$

Input:

a byte array of length 1 to 31, inclusive.

Take an example, oxDE, 0xAD

Objective:

Write each byte into 8-bit binary, big-endian 1101111010101101

Average split into 8 parts 11 01 11 10 10 10 11 01

Convert each part from binary to number [3,1,3,2,2,2,3,1]


  • Which endian, or allow both?
\$\endgroup\$
5
  • \$\begingroup\$ @greybeard Title not decided. Average mean with total=m, each given m/8. I say number cuz lots of language at the moment is just number, you need to printf %d to convert it to decimal, or %x hex \$\endgroup\$
    – l4m2
    Commented Apr 1 at 0:31
  • 1
    \$\begingroup\$ Average split -> Evenly split \$\endgroup\$
    – Bubbler
    Commented Apr 1 at 4:33
  • \$\begingroup\$ I don’t understand the question Which endian […]? Endianness is only relevant if multiple bytes together represent one number. In this challenge we have up 31 independent bytes/numbers so endianness is not an issue. \$\endgroup\$ Commented Apr 2 at 10:12
  • \$\begingroup\$ @KaiBurghardt That reverse the array, it seems reasonable to allow both \$\endgroup\$
    – l4m2
    Commented Apr 2 at 10:16
  • \$\begingroup\$ I see. Well, it does not seem “reasonable” to me. Could you explain? I say, KISS – keep it simple. An array element with a lower index comes first, there is no ambiguity in that. \$\endgroup\$ Commented Apr 2 at 10:50
0
\$\begingroup\$

Vending Machine Simulator

Alternate title: Linear Logic Simulator

Objective

Write an interactive program that asks you to design a vending machine, and then simulate the vending machine.

The fuss is, the vending machine is designed for simulation of linear logic.

Design

The vending machine has some items available for purchasing, identified by words consisting of ASCII capital Latin letters.

Upon accepting a penny, the vending machine will or will not output an item, owing to its design.

The vending machine's design is defined as a logical expression consisting of the items and the binary operators. The binary operators and their semantics are:

  • P times Q: This vending machine has one slot. Upon accepting a penny, the vending machine will output the items P and Q together.

  • P with Q: This vending machine has two slots. The left slot, upon accepting a penny, will let the machine output P. The right slot, upon accepting a penny, will let the machine output Q.

  • P plus Q: This vending machine has one slot. Upon accepting a penny, the machine has fifty-fifty chance to output P or output Q.

  • P par Q: This vending machine has two slots, and one of them, chosen with fifty-fifty chance, has a pre-installed coin.

    • If you insert a penny in the other slot, the vending machine will consume one of the two pennies with fifty-fifty chance, and will output the item that corresponds to the consumed penny.

    • However, if you insert a penny in the slot that already had a penny pre-installed, the machine will reject the inserted coin, giving it back to you. You will try again with the rejected penny.

I/O format

(WIP)

Worked Examples

Example #1

Design your vending machine: (CANDY with CHIPS) times CHOCOLATE
Simulating (CANDY with CHIPS) times CHOCOLATE...
    Simulating (CANDY with CHIPS)...
        Which slot will you insert a penny? (Left|Right): Left
        Simulating CANDY...
            You get the CANDY.
    Simulating CHOCOLATE...
        You get the CHOCOLATE.

Example #2

Design your vending machine: CANDY par (CHIPS plus CHOCOLATE)
Simulating CANDY par (CHIPS plus CHOCOLATE)...
    Which slot will you insert a penny? (Left|Right): Left
    Wrong guess! The machine rejects the penny.
    Which slot will you insert a penny? (Left|Right): Right
    Correct guess!
    The machine decides to simulate CANDY.
    Simulating CANDY...
        You get the CANDY.

Example #3

Design your vending machine: CANDY par (CHIPS plus CHOCOLATE)
Simulating CANDY par (CHIPS plus CHOCOLATE)...
    Which slot will you insert a penny? (Left|Right): Right
    Correct guess!
    The machine decides to simulate (CHIPS plus CHOCOLATE).
    Simulating (CHIPS plus CHOCOLATE)...
        The machine decides to simulate CHOCOLATE.
        Simulating CHOCOLATE...
            You get the CHOCOLATE.

Meta Question

Any misunderstanding I have? Especially for par?

\$\endgroup\$
1
0
\$\begingroup\$

Construct the largest number by combining

Given an array, each time you can remove two values \$a\leq b\$, and add value \$\min\left(2a\color{red}{+1},a+b\right)\$.

Return the largest value you can get.

Duplicate Checker

  • The red part is +0 or +1
  • Is it fine to leave some values?
\$\endgroup\$
2
  • \$\begingroup\$ By "Largest value you can get", do you mean: Repeat the function until only 1 value remains, or Return the highest value obtained by a pair in the original list? \$\endgroup\$
    – ATaco
    Commented Apr 4 at 20:52
  • \$\begingroup\$ @ATaco Not decided, ref "Is it fine to leave some values?" \$\endgroup\$
    – l4m2
    Commented Apr 5 at 4:09
0
\$\begingroup\$

Is this function communative?

Given a function of the form of a valid mathematical expression with at least two variables named a through z, determine if it is impossible to rearrange the values of the variables so that the result is different. For example:

$$ x + y - 3 $$

would be commutative, because let's \$x = 2\$ and \$y = 6\$. Then the result would be 33, but even if you made \$x = 6\$ and \$y = 2\$, the result would be the same.

Clarifications

  • The expression consists of digits (0-9), addition (+), subtraction (-), multiplication (*), and division (/). No ab, it will always be written as a * b.
  • You may evaluate the expression left-to-right or adhere to the order of operations, but it must be consistent.
  • Variables can be any positive integer including zero unless that might result in division by zero.

Test cases

x + y - 3 => True
x * 3 / y => False
3 * x + y / x * 0 => True
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Case x/x, x-y+0/0 ? \$\endgroup\$
    – l4m2
    Commented Apr 10 at 1:00
  • \$\begingroup\$ What about x+2 + (y*y - 4) / (y - 2)? \$\endgroup\$ Commented Apr 11 at 8:35
  • 1
    \$\begingroup\$ Do you have a solution? Is this problem always solvable? \$\endgroup\$
    – Tbw
    Commented Apr 12 at 20:54
  • 1
    \$\begingroup\$ Typo in the title. And if the input can't contain parentheses, aren't left to right and order of operations solutions on totally different playing fields? (Maybe allow/encourage looser I/O, like prefix notation or even a pre-parsed tree structure.) \$\endgroup\$ Commented Apr 17 at 2:01
  • 2
    \$\begingroup\$ Test cases with more than two variables would be good. \$\endgroup\$
    – pxeger
    Commented Apr 17 at 10:12
  • \$\begingroup\$ Things to avoid: parsing expressions \$\endgroup\$
    – xnor
    Commented Apr 19 at 22:33
0
\$\begingroup\$

Given a piece of notes, make accidentals clear.

Accidentals include b, % and #. Pitch names include uppercase A to G1. In input, every note is an accidental and a pitch name. Besides, bar lines exist to split bars.

For each note in output,

  • Default1 claims that a note share the recent accidental with same pitch name in this bar, or % if same pitch name never appeared in this bar. If this is false, preserve accidental as-is. Otherwise,
  • Default2 claims that a note share the recent accidental with same pitch name if there are less than 8 notes between it and current note, % otherwise. If this is false, surround the accidental with (). Otherwise, remove the accidental in output.

Test cases:

%C%C%C%C|#C#C#C#C|#C#C#C#C|%C%C%C%C| =>
CCCC|#CCCC|#CCCC|(%)CCCC|

enter image description here

1 Whether CDEFGAB or ABCDEFG doesn't matter here

Sandbox Notes

  • Any nouns incorrect
  • Name of Default1 and Default2
  • How does this work in real?
\$\endgroup\$
3
  • \$\begingroup\$ I'm pretty sure for default 2 that a note shares the accidental if there is a same note in the same measure, might be wrong. \$\endgroup\$ Commented Apr 11 at 13:41
  • \$\begingroup\$ @LarryBagel Don't quite understand. Example? \$\endgroup\$
    – l4m2
    Commented Apr 11 at 21:30
  • \$\begingroup\$ I mean that if there is a c-sharp in a measure and a normal c after that c-sharp in the same measure, that c will also be sharp. But if that c is in any other measure (without a c accidental preceding it), it's natural. \$\endgroup\$ Commented Apr 12 at 12:34
0
\$\begingroup\$

Decode Caesar cipher based on a given text

I can't think of a better name. This is similar to this challenge, but a lot easier.

Read three strings which contain only uppercase letters. The length of the first and second strings are the same. The second string and the third string are encrypted using Caesar cipher using the same key. The original string of the second string is the first string. You have to decrypt the third string. Obviously, there is exactly one possible original string of the third string.

Examples

AAA BBB CCC -> BBB
I U TQXXAIADXP -> HELLOWORLD
HELLO FCJJM QRPGLM -> STRING

Rule

This is , so code in the fewest bytes.

\$\endgroup\$
0
\$\begingroup\$

Divisibility patterns

\$\endgroup\$
0
\$\begingroup\$

Given a function f: N->N and non-negative integer n, output integer k s.t. f(f(...f(n)..)) (repeat k times) = 0, or some non-natural number if no k exist.

You can assume f is bounded, i.e. there's some number M s.t. for each n, f(n)<M.

\$\endgroup\$
0
\$\begingroup\$

*Trivial* near-repdigit perfect powers

\$\endgroup\$
0
\$\begingroup\$

Create a random Triling

Over in the Puzzling SE, user23087 came up with an interesting new puzzle type. (https://puzzling.stackexchange.com/questions/126659/try-triling-triangular-tiling).

Given two positive integers N and M, display a randomized "Triling" gameboard layout of N x M tiles, made of (N+1) x (M+1) dots placed at the corners of each tile, marking out a board, with some of the tiles containing numbers.

The board layout can be validly "Triled" if a player can join dots on the board to create triangles, with the tile of each number wholly contained by a non-overlapping triangle with an area equal to the number, and with the whole board covered in such triangles with no gaps.

I don't think it's possible to Trile a board with odd values of both N and M. It's also impossible to Trile one with an N or M less than 2. You can assume you'll only be given Trilable values of N and M.

How exactly the dots and letters are spaced doesn't matter, so long as it looks reasonable and you can tell which tiles are meant to be number-tiles, and the value they're meant to handle. Single-digit numbers may may be zero-padded or space-padded.

N = 2, M = 2 - Output must randomly be a board like either:

.  .  .
 2
.  .  . 
     2
.  .  . 

or:

.  .  .
     2
.  .  . 
 2
.  .  . 

Those are the only two legal layouts for a 2 x 2 board.

The former would be solvable by drawing just one line like so, placing both "2" tiles entirely within non-overlapping triangles of area 2:

.  .  /
 2  ,`
.  /  . 
 ,`  2
/  .  . 

N = 4, M = 4 - Layouts such as:

. . . . .
.2. . .2.
. . .4. .
. .4. . .
.2. . .2.

Or:

. . . . . 
.2. . .4. 
. .4. . . 
. . .4. . 
.2. . . . 

Or:

. . . . . 
. .4. . . 
.2. . . . 
.2. .8. . 
. . . . . 

...Or many others, though I think this size only allows tile values of 2, 4, and 8.

Scoring: It's trivial to generate boards that use only the values "2" and "3". To encourage more novel algorithms, this is code golf with handicapping, and lowest score wins. Shortest code will have a good head start, but then:

  • Double the score if your solution is only trivially-random (eg produces the same board just with alternative rotations, even for larger boards with many alternative solutions). I don't think it's possible to prove that an answer can generate all possible valid solutions, and that's OK.
  • Double your score if your answer can only generate layouts solvable entirely with right-angle triangles.
  • Double your score if your answer cannot generate layouts containing obtuse triangles.
  • Multiply your score by the count of the numbers in the list [1, 2, 3, 4, 5, 6, 7, 8, 9, and 10] that your answer can't/won't place in its generated boards. (As "1" is impossible to legally place, even an ideal solution will still multiply by 1, rather than 0.)

These handicapping penalties stack. Mention in your answer which ones you applied.

To further encourage novel algorithms rather than mere re-golfing of the first efficient one people come up with, each person posting an answer that uses a new layout-generation algorithm can use an exclamation-mark in the title of their answer. Nobody else gets to use exclamation marks in their answer title! So, just a completely cosmetic and self-policed reward, as opposed to the scores, which are made of authentic, bona fide Internet Points, probably tradable for food in some countries.

\$\endgroup\$
1
140 141
142
143 144
157

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .