=Y]kFkY~Yf>ql{TlT%vTlTm+k`dr1T)pk
To test it, put the above code as standard input in the link in the title.
After compiling into Python 3.4:
k=''
T=10
Y=[k]
for k in Y:
Y+=list(filter(lambda T:(len(set(T))==len(T))>(eval(T)%len(T)),
map(lambda d:k+repr(d),range(1,T))))
print(k)
Explanation:
=Y]k:Y=['']
FkY: for k in F:
~Y: Add to Y
f: Filter by
>ql{TlT: All unique elements and
%vTlT: eval(element)%len(element)=0
m+k` d
On the list of k + repr(d)
r1T: for d from 1 to 9.
): End for loop
pk: print k
=ZwFY{Z=bkW'bZ~bY)p(Yltb
Test can be done here: link
Outputs in the format:
('a', 5)
('c', 2)
('b', 3)
Explanation:
=Zw Store one line of stdin in Z
FY{Z For Y in set(Z):
=bk b=''
W'bZ while b in Z:
~bY b+=Y
) end while
p(Yltb print (Y, len(b)-1)
Python:
k=""
Z=copy(input())
for Y in set(Z):
b=copy(k)
while (b in Z):
b+=Y
print(_tuple(Y,len(tail(b))))
For proper (a=5) output, use:
=ZwFY{Z=bkW'bZ~bY)p++Y"="`ltb
29 characters
=ZUwsVm;dSm[cZkk)UG
Try it here: http://ideone.com/fork/YlWpEJ
Learn more about Pyth here: http://esolangs.org/wiki/Pyth
Example:
Based off ETAOIN SHRDLU, your challenge is to write the shortest program or function in any language that outputs the 26 letters of the English alphabet based on their frequency in the input.
Gives:
TENOHARSIULGFPYDCBWQMZXVKJ
Explanation:
=ZUw: Convert input to uppercase and store in Z.
sV: Print the sum of the reverse of
m;d: The last entries of
S: Sorted by their first entry, in increasing order
m[cZkk): The lists [count of k in Z, k]
UG: For k in the uppercase letters.
Rough Python equivalent:
G='abcdefghijklmnopqrstuvwxyz'
Z=copy(upper(input()))
print(_sum(rev(_map(lambda d:d.pop(),sorted(_map(lambda k:_list(count(Z,k),k),upper(G)))))))
This is not entry, I just thought people might like to see it. In Pyth 1.0.4, the following program is a solution in 10 characters:
JUwo_cJNUG
Explanation:
JUw: Convert input to uppercase and store in J.
o: (Print) Sort by
_cJN: -1*(count of N in J)
UG: Over N in the uppercase letters.
It is not a legal solution because several of the changes from Pyth 1.0.2 to 1.0.4, including the addition of the o, sort by, function, were in response to this problem.
JPwd;ocJNJ
Unlike almost every solution above, this code doesn't just take the middlemost element.
Explanation:
JPwd J = input, split on spaces
; Print last element of
ocJN Order by count in J of N,
J For N in J
Bonus solution:
If you want pluralities to be correctly judged as well, that's one more character:
JtPwd;ocJNJ
This judges correctly the only case where the above fails for pluralities: When the last planet has one less vote than the plurality winner, the 10 character code will mistakenly select the last planet, because it counts the statement of the number of worlds as a vote.
This code corrects that error by using the tail function, t, to ignore the first number.
DgYb=Z0J'bWbK;bDiHNR*-'H'K-@N1@K1~Z>iYJiJY=JK)R!%Z3
Defines the function g, which takes two inputs: the test point, and then the list of the vertices of the triangle. Outputs True and False. Note: Destroys the input, specifically b, the list of the vertices of the triangle.
Try it here.
The last few characters, gvwvw call the function with a test case on the next two lines.
Based on this algorithm
Explanation:
DgYb Define g(Y,b):
=Z0 Z=0
J'b J=b[0] (No = is needed because j is special).
Wb While len(b)>0: (While b:)
K;b K=b.pop()
DiHN Define i(H,N):
R*-'H'K-@N1@K1 Return half of the linked equation.
~ZiYJiJY Z+=i(Y,J)>i(J,Y)
=JK J=K
) Wend
R!%Z3 return not Z%3==0 (True iff Z == 0 or 3)
The CJam - Pyth war rages on!
C"ߞ
Pretty straightforwards, just convert that character to an integer and print.
I didn't find the Pyth documentation. But it works.
W1~ddd
G
Pyth predefines certain variables. G is predefined as the lowercase alphabet. Pyth also implicitly prints each line with a reasonable return value.
Kf<T"n"GJKFbJI>lb9Bb~Jm+bdfXVb*Y3K
Explanation:
Kf<T"n"G K = list of letters in the alphabet before n.
JK J = copy of K
FbJ For b in J:
I>lb9B If length of b > 9: break
b print(b)
~J J+=
~Jm+bd J+=map(lambda d:b+d,
XVb*Y3 index of Y*3 in reversed(b)
fXVb*Y3K filter for non-zero for Y in K on function index of Y*3 in reversed(b)
~Jm+bdfXVb*Y3K J+=map(lambda d:b+d, filter(lambda Y:index of Y*3 in reversed(b), K))
JwqvJsm^vdlJJ
Explanation:
Jw J=input()
^vdlJ eval(d)^len(J)
m^vdlJJ map each character in J to eval(d)^len(J)
qvJsm^vdlJJ print(eval(J)==sum(map each character in J to eval(d)^len(J)))
0 1
3 2
In pyth, everything is printed by default, unless it is preceded by a space. Lines after the first line are for user input, and are not evaluated in this program.
Another way to get 9 characters:
"0"
3 1
"2"
While recent changes to pyth have made 2 digit numbers harder to generate (A change that I am considering reverting), older versions of Pyth have easy two digit number generation, which, combined with the implicit printing and the fact that all lines but the first are ignored, gives the following solution:
32
41
Prints 32,21,14,43.
DAdRsf!%dTr1dDMkRqkAAk
Explanation:
DAd def A(d):
Rs return sum(
f!%dT filter on condition (not d%T)
r1d for T in range(1,T)
DMk def M(k):
R return
qkAAk k==A(A(k))
Note: Does not fail even if there are more than 2 copies of duplicated numbers.
JPw)'ocJNJ
Explanation:
JPw) J=input.split()
'oJNJ print first element of J sorted by count of element in J.
G"qwertyuiopasdfghjklzxcvbnmpyfgcrlaoeuidhtnsqjkxbmwvz"VG
Alphabet, string, reversed alphabet. G is the alphabet. Print is implicit.
DcGHR?+m+]'HdctGtHcGtHH*]Y!G
This is (heavily) based on the Haskell answer.
Explanation:
DcGH def c(G,H):
R return
? Python's short circuiting _ if _ else _
m+]'Hd map to [head(H)]+d
ctGtH c(G-1,tail(H))
m+]'HdctGtH map [head(H)]+d for d in c(tail(G),tail(H))
+m+]'HdctGtHcGtH (the above) + c(G,tail(H))
? H (the above) if H else (the below)
*]Y!G [[]]*(not G)
Note: While the most recent version of Pyth, 1.0.9, was released tonight, and is therefore ineligible for this challenge, the same code works fine in 1.0.8.
G
My language is too new to count, by the way.
J"rps"K+wOJK%-XJ'KXJtK3
Output is in the form:
Tie: 0 Win: 1 Loss: 2
Explanation:
J"rps" J="rps"
K+wOJ K=input()+random_choice(J)
K print K
XJ'K index of K[0] in J
XJtK index of K[1] in J
-XJ'KXJtK difference of above indexes
%-XJ'KXJtK3 above difference mod 3
Run as follows:
$ cat rps
J"rps"K+wOJK%-XJ'KXJtK3
s
$ cat rps | python3 pyth.py
< Extraneous debug output removed>
sp
1
For only 4 more characters, we can use T for tie, W for win and L for loss:
J"rps"K+wOJKr@"TWL"-XJ'KXJtK
Everything is the same up until the difference of indexes, at which point we use the difference as the index into the string"TWL".
Note: while I did develop this language after the challenge was posted, I had not seen the challenge until today. The challenge did not influence any aspect of the language.
JVPwdWJ=Z+*ZlJXovNJ;J)Z
A port of my Python answer.
A Python translation (with some irrelevant stuff filtered out):
Z=0
J=rev(split(input()," "))
while J:
Z=plus(times(Z,len(J)),index(order(lambda N:eval(N),J),J.pop()))
print(Z)
The input numbers stay strings but are sorted as ints by using eval as the key. The list is reversed so that pop takes the the front rather than the back.
l=map(int,raw_input().split())
f=n=len(l)
o=s=n*' \ /'
while f+n%2:
f-=1;i=f+n&1;a=s[2*i:][:2*n]+'\n| '[::2-i]
while~i>-n:a+='|X'[l[i+1]<l[i]]+' ';l[i:i+2]=sorted(l[i:i+2]);i+=2
o=a+f%2*'|'+'\n'+o
print o[:-2*n]
I took a slightly different approach: I find the swaps necessary to sort the input, then vertically invert that to get the swaps necessary to turn the sorted list into the input. As an added bonus of this approach, it can take an arbitrary list of numbers and give the permutation path to turn the sort of the input into the input.
Example:
$ python sort_path.py <<< '3 1 4 5 9 2 6 8 7'
\ / \ / \ / \ / \
| | | | |
/ \ / \ / \ / \ /
| | | | |
\ / \ / \ / \ / \
| | | | |
/ \ / \ / \ / \ /
| | | | |
\ / \ / \ / \ / \
| | | | |
/ \ / \ / \ / \ /
| X | | X
\ / \ / \ / \ / \
| X | X |
/ \ / \ / \ / \ /
| | X X |
\ / \ / \ / \ / \
X | X | |
/ \ / \ / \ / \ /
| | | | X
\ / \ / \ / \ / \
Improvements:
264 -> 261: Switched outer loop from for to while.
261 -> 259: Used f%2 instead of (c^m), because in python arithmetic operators have higher priority than bitwise operators.
259 -> 252: Switched inner loop from for to while. Combined i and c variables.
252 -> 247: Changed build then reverse to just build in reverse order.
247 -> 243: Added newlines manually, instead of using join.
243 -> 227: Adopted grc's method of slash line generation (thanks grc!) and added s.
227 -> 224: Moved slash line generation to before inner while loop to remove a %4 and save a character by using extended slicing.
224 -> 222: Removed m.
222 -> 220: f%2+n%2 -> f+n&1
220 -> 219: | 1<n-1| -> |~i>-n| (removed leading space)
219 -> 218: Combined initializations of o and s and moved the slice to the end.
smCv+"0b"dPZ
Note that s is not a legal variable in Pyth, so I used Z instead.
Explanation:
print(
s sum(
m map(lambda d:
C chr(
v eval(
+"0b"d "0b"+d)),
P split(
Z Z))))
Example:
=Z"<the binary string from above>"smCv+"0b"dPZ
Hello World
W1sm?C+33@[8Z31 2 3 4 61 5tT7)vd}Cdr48 58dw
Uses 33+table lookup, instead of straight table lookup. No translate function here, just a normal map. Note that Z=0 and tT=9.
DsbR;fgb*TTL'b
Provides a named function, s, which calculates the square root by filtering the list from 0 to n for the square being larger than the input, then prints the last such number. Uses no exponentiation or floats.
Dsb def s(b):
R; return last element of
f filter(lambda T:
gb*TT b>=T*T,
L'b range(b+1))
Example usage:
python3 pyth.py <<< "DsbR;fgb*TTL'b \msd[0 1 2 3 4 8 9 15 16 65535 65536"
[0, 1, 1, 1, 2, 2, 3, 3, 4, 255, 256]
Precise index is 2124002227156710537549582070283786072301315855169987260450819829164756027922998360364044010386660076550764749849261595395734745608255162468143483136030403857241667604197146133343367628903022619551535534430377929831860918493875279894519909944379122620704864579366098015086419629439009415947634870592393974557860358412680068086381231577773140182376767811142988329838752964017382641454691037714240414750501535213021638601291385412206075763857490254382670426605045419312312880204888045665938646319068208885093114686859061215
Found by r.e.s., using the (old version of) code below, after 3.5 hours of searching.
Around that index, the string is: ...BCCBCBCCCBCCCCCCBCCB...
To verify, change the indicated line in the code below to start at 2946, instead of 5. Verification takes 20 seconds.
Update: Improved program. Old program searched ~10x more locations than necessary.
New version finds the CCCCCC in only 33 minutes.
How the code works: Basically, I only look at the regions which correspond to the ends of incremental strings, and calculate the letters by looking recursively back to the original string. Note that it uses a memo table, which may fill up your memory. Put a cap on the length of the memo table if necessary.
import time
import sys
sys.setrecursionlimit(4000)
ULIMIT=4000
end_positions=[]
current_end=2
while len(end_positions)<ULIMIT+3:
end_positions.append(current_end)
next_end=((current_end+1)*3+1)//2-1
current_end=next_end
memo={}
def find_letter(pos):
if pos in memo:
return memo[pos]
if pos<3:
return 'ABC'[pos]
for end_num in range(len(end_positions)-1):
if pos>end_positions[end_num] and pos<=end_positions[end_num+1]:
delta=end_positions[end_num+1]-end_positions[end_num]
if len(memo)>5*10**6:
return find_letter(pos-delta)
memo[pos]=find_letter(pos-delta)
return memo[pos]
time.clock()
for end_num in range(5,ULIMIT+1): # This line.
diff = 1 # Because end_num is guaranteed to be a C
while True:
last_letter=find_letter(end_positions[end_num]+diff)
if not last_letter=='C':
break
diff+=1
if end_num%100==0:
pos_str=str(end_positions[end_num])
print(end_num,'%s.%s*10^%i'%(pos_str[0],pos_str[1:5],len(pos_str)-1),
len(memo),diff,time.clock())
if diff>=6:
print(end_num,end_positions[end_num],diff,time.clock())
Current max searched to: 4000 iterations
CCCCCC found at iteration(s):
2946
tTFk"*+,-7;=?GHIKVWXYhiklnvwx"C-Ck7
Try it here.
Prints the characters in order except that 9 is at the beginning, newline separated.
String contains all characters 7 greater than the ones needed, except that 9 would become @, so it is special cased. Algorithm thanks to @Howard.
Explanation:
tT print(10-1) T=10, t(x)=x-1 if x is an int.
Fk"<string>" for k in "<string>":
C-Ck7 print(chr(ord(k)-7)) Note that C is overloaded as ord and chr.
Befunge-ified version of isaacg's Pyth entry:
"xwvnlkihYXWVKIHG?=;7-,+*">:5j2 ,-7_"?"1+:,s <
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111113111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
Found this one about 50 minutes after starting from 4000. Therefore, I would estimate this is the upper limit of this code approach.
Change: I've noticed that some lengths seem to be more fruitful for generating this sort of prime than others, so I've decided to only check 50 random locations of the digit that isn't 1 instead of all possible locations, before moving on. I'm not completely sure this will improve performance, or that 50 is correct, but we'll see.
Possibilities list is generated based on the fact that for the products requirement to be fulfilled, the number must be all ones except for a prime. In addition, the prime can't be 2 because of the sum and length relationship, and the digital sum must not be divisible by three, giving the %3 requirements.
is_prime taken from http://codepad.org/KtXsydxK , written by @primo
Note: this is_prime function is actually a Baillie-PSW pseudoprime test, but there are no known counter-examples, so I'm not going to worry about the distinction.
#http://codepad.org/KtXsydxK
from my_math import is_prime
import time,random
LLIMIT=2748
time.clock()
start_time=time.time()
checked=0
while time.time()-start_time<3600:
small_primes = [a for a in range(LLIMIT,2*LLIMIT) if is_prime(a)]
leng,dig=(0,0)
for a in small_primes:
if a+2 in small_primes:
leng,dig=(a,3)
break
if a+4 in small_primes:
leng,dig=(a,5)
break
if a+6 in small_primes:
leng,dig=(a,7)
break
start=time.clock()
print leng,dig,time.clock(),checked
for loc in random.sample(range(leng),50):
checked+=1
if is_prime(int('1'*loc+str(dig)+'1'*(leng-loc-1))):
print leng-1,loc,dig,time.clock(),time.clock()-start, \
int('1'*loc+str(dig)+'1'*(leng-loc-1))
break
LLIMIT=leng+1
m'XYdY
List is stored in Y to begin with. This is functionally the same as the 22 character ruby solution: map over d in Y to index of d in Y plus 1, then print.
Example:
$ echo "=Y[16 15 15 12 11 11 10 9 9 9 8 2 2 2 0)m'XYdY" | python3 pyth.py
[1, 2, 2, 4, 5, 5, 7, 8, 8, 8, 11, 12, 12, 12, 15]
p?kqZ4d@P"It is by a rope."dZ~Z1
Phrase: "It is by a rope."
Entropy: 3.5
How it works:
p means print with specified separator.
The first argument, ?kqZ4d, gives the separator. ?kqZ4d means k if Z==4 else d. k is '', while d is ' '.
The second argument, the value to be printed, is generated by splitting (P) on space (d), and the indexing into that list (@) at Z.
Finally, Z, which is automatically initialized to 0, is incremented by 1 (~Z1).
JvwKr2 4W-ZJ~@KgJZ1=YurGHK=Zu*NTY)Y
Note: My code actually finds the shortest representation of the input as a representation of consecutive integers >=2, so on invalid input it will print a 1 element list, possibly after a very long time. Since the problem statement says the input will be valid, I assume this is OK.
Short explanation:
Essentially, the program stores the upper and lower limits of a range, calculates the product of the numbers in the range using a reduce, adjusts the endpoints as necessary, and repeats until the product equals the input.
Long explanation:
For each snippet of code, I will give equivalent python, as well as a more detailed explanation and reasoning.
Jvw => J=eval(input())
Standard way to take input in Pyth.
Kr2 4 => K=range(2,4) => K=[2,3]
Here's the first weird part: Instead of storing the endpoints as separate variables, I'm storing them as elements of a list. The reason will soon be clear. Also, instead of doing a simple assignment, which in Pyth would be K[2 3), I'm using a range to save a character.
W-ZJ => while Z-J => while Z!=J
At this point, you might ask, "What is Z? You haven't defined it." In Pyth, all variables come predefined. Z happens to start as 0. However, Z will be set to the value of the product later, so this check will serve to end the while loop once the list is at the correct value.
~@K>JZ1 => K[J>Z] += 1
Here's why I'm storing the values in a list, not in separate variables: I want to increment one of the two endpoints, depending on whether the product is currently too high or too low. That would be a rather long conditional if the endpoints were separate variables, but with the magic of list indexing, it becomes short. Also, the fact that this check comes before the product, and the fact that Z is initialized to 0, ensure that K will be [2,4] by the time we first take the product, which are the proper endpoints.
=YurGHK => Y=reduce(lambda G,H: range(G,H),K) => Y=range(K[0],K[1])
Now, I need the actual list that the product will be taken over, and that will be printed out if we succeed. Clearly, we will use a range function. The trickiness lies in obtaining the inputs to the range function. The obvious way to do this, by indexing the list, would be =Yr'K@K1. However, by using a reduce function on this two element list, we can shorten that by a character.
=Zu*NTY => Z=reduce(lambda N,T: N*T,Y)
And now, for the whole point of this affair, the reduce operation to find the product of the list.
) => End while
Y => print(Y)
On success, print the list.
Example run:
$ cat seq_prod
JvwKr2 4W-ZJ~@K>JZ1=YurGHK=Zu*NTY)Y
$ cat seq_prod | python3 pyth.py
<debug stuff>
==================================================
[9, 10, 11, 12, 13, 14, 15, 16]
DAbKJ0W>b+JK~K1~JK)R++`K","`J
If the output format b, t instead of b,t is OK, then it's 28 characters:
DAbKJ0W>b+JK~K1~JK)R:`,KJ1_1
If (b, t) is OK, it's 23 characters:
DAbKJ0W>b+JK~K1~JK)R,KJ
Explanation:
def A(b):
K=J=0
while gt(b,plus(J,K)):
K+=1
J+=K
return plus(plus(repr(K),","),repr(J))
Test run - (input, output):
DAbKJ0W>b+JK~K1~JK)R++`K","`Jj"\n"m,dAdL11
(0, '0,0')
(1, '1,1')
(2, '1,1')
(3, '2,3')
(4, '2,3')
(5, '2,3')
(6, '3,6')
(7, '3,6')
(8, '3,6')
(9, '3,6')
(10, '4,10')
jd"QAPMFRLZ\nUINKSHXJ\n\0GTCVEWY
Output:
Q A P M F R L Z
U I N K S H X J
G T C V E W Y
Connections, thanks to @githubphagocyte's checker:
Q A P M F R L Z
\ / \ / / \ / / \ \ \
U I N K S H X J
/ \ / / \ / / \ / \ /
G T C V E W Y
Combines @grc's null byte trick and Pyth's extremely short syntax. Made my own grid for the hell of it.
Explanation:
j is python's string join. d is space. \0 is the escape sequence for the null byte. It is a NOP when printed, so the third line has exactly two spaces in front. Also, note that strings can be EOL-terminated in Pyth, as well as quote-terminated.
v_%"%032db0"vsc%Q^2 32
Explanation:
Q Evaluated input.
%Q^2 32 Q mod 2^32. Same 32 bit binary representation as Q.
vsc%Q^2 32 Convert to binary string, then that to decimal int.
%"%032db0"vsc%Q^2 32 Pad above number to 32 bits, and append b0.
_%"%032db0"vsc%Q^2 32 Reverse it.
v_%"%032db0"vsc%Q^2 32 Eval and print. Due to leading "0b", eval as binary.
Golfs:
33 -> 32: Moved add to before reversing to save an end-quote.
32 -> 22: Used Q mod 2^32 instead of complicated machinery. Combined both strings into one.
Test cases:
$ cat rev_bits
v_%"%032db0"vsc%Q^2 32
$ ./pyth.py rev_bits <<< -984802906
1704506019
$ ./pyth.py rev_bits <<< 486
1736441856
$ ./pyth.py rev_bits <<< 0
0
print int("{:032b}".format(input()%2**32)[::-1],2)
Broadly the same as my Pyth solution. Take the input mod 2**32, convert to 32-bit padded binary, reverse, convert binary sting back to decimal and print.
JVQXQjdJ=J+tJ]hJ
Prints the table with proper whitespace.
./pyth.py -c "JVQXQjdJ=J+tJ]hJ" <<< 5
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3
Explanation:
Automatic: Q=eval(input())
JVQ J = range(Q)
XQ repeat Q times
jdJ print J, joined on " "
=J J =
+tJ]hJ tail(J) + [head(J)] (J[1:] + [J[-1]]])
This answer uses multiple features of Pyth added after the challenge was asked.
I added another new feature, calling unary range on a 2 element tuple, which shortens the solution by two characters, to this:
hoePNUQ
Input is now taken comma separated. The rest is the same.
This answer uses a feature of Pyth that was added after this question was asked, specifically after seeing @aditsu's wonderful CJam solution. That being said, I wanted to demonstrate what adding that feature has made possible. The feature is P, which is an arity-1 function which on integer input returns a list of all prime factors of the input, sorted smallest to largest.
hoePNrQvw
Uses Python-style ranges, newline separated on STDIN. Outputs smallest solution to STDOUT.
Explanation:
Q = eval(input()) Implicit, because Q is present.
h head( First element of
o order_by( Sort, using lambda expression as key.
lambda N: Implicit in o
e end( Last element of
PN pfact(N)), List containing all prime factors of N.
r range( Python-style range, lower inc, upper exc.
Q Q, A variable, initialized as shown above.
vw eval(input())))) The second entry of the range, same way.
Tests:
$ newline='
'
$ echo "9${newline}16" | ./pyth.py -c 'hoePNrQvw'
9
$ echo "9${newline}17" | ./pyth.py -c 'hoePNrQvw'
16
$ echo "157${newline}249" | ./pyth.py -c 'hoePNrQvw'
162
$ echo "2001${newline}2014" | ./pyth.py -c 'hoePNrQvw'
2002
J*]0^T3Fkyw=@JkheS:J0k)eSJ
Port of @ray's solution. Passes official tests. Now uses space-separated STDIN input, not function call.
Run as follows:
./pyth.py -c "J*]0^T3Fkyw=@JkheS:J0k)eSJ" <<< "1 5 7 2 8 4 3 5"
4
Explanation:
J*]0^T3 J = [0]*10^3
Fkyw For k in space_sep(input()):
=@Jk J[k]=
heS:J0k max(J[0:k])+1
) end for
eSJ max(J)
Time unlimited:
L?eS,ytbhyf>Thbbb0
Technical note: I noticed a bug in my Pyth complier while writing this golf. L wasn't working. That's why there is a recent commit to the above git repository.
91,65>123,97>++
Outputs:
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
Explanation:
91, Make the list, [0 1 .. 90]
65> Take elements after the 65th, [65 66 .. 90]
123,97> Same, but [97 98 .. 122]
+ Add the list above to the newline character that is automatically pushed to
the stack. List + str coerces to string by ascii encoding.
+ Same, for the other list.
JhCeGLjkmCdbsrCdCPhGsrhCPeGChGsrJhhhhJ
Outputs:
!"#$%&'()*+,-./0123456789:;<=>?@
[\]^_`
{|}~
Explanation:
G = "abcdefghijklmnopqrstuvwxyz" Implicit.
k = "" Implicit.
d = " " Implicit.
JhCeG J = 1 + chr(end(G)) # J = 123
L def d(b): return
jk k.join(
m map(lambda d:
Cd chr(d),
b b))
s print(s( #print is implicit.
rCd range(chr(d), # chr(d) = 32
CPhG chr(upper(head(G)))) # chr("A") = 65
srhCPeGChG print(s(range(1+chr(upper(end(G))),chr(head(G)))
srJhhhhJ print(s(range(J, 1+1+1+1+J)))
%*$"%\143"$52(65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
Explanation:
$"%\143"$ => "%c". $ switches to and from Python parsing style, and in Python string parsing, \143 is the octal escape sequence for c. This answer is thus equivalent to the following Python-style code:
("%c" * 52) % (65, 66, 67, ...)
Of course, this doesn't work in Python, because printing in Python uses print, but printing in Pyth is implicit, so it works.
Pyth solutions do not use any of the features added since the question was asked.
V501?N&%N3-`3`N"bzzt
Explanation:
V501 for N in range(501):
? _ if _ else _
N print(N)
& _ and _
%N3 N mod 3
-`3`N Assymetric difference of str(3) and str(N)
"bzzt "bzzt" (Final " is implicit)
Essentially, the test is the logical and of N%3, which is only 0, and thus interpreted as false iff N is divisible by 3, with
-`3`N
which is the empty list iff 3 is present in str(N). Setwise minus removes all appearances of characters in the second string from the first string.
If this and returns true, we print N, otherwise we print "bzzt". Having "bzzt" in the else clause saves a character, because there is no need to end-quote the string.
Just a simple one to get things started - I fully expect this to be quickly cracked.
h_^ZqU5m-CGdQ
Takes comma separated input on STDIN.
Run it like this (-c means take program as command line argument):
$ echo '1,2,3,4,5' | python3 pyth.py -c h_^ZqU5m-CGdQ
0
Fixed the program - I had not understood the spec.
This language might be too esoteric for this competition - If OP thinks so, I will remove it.
Lnb_bWP`+QZ=Z-g0ZZ)Z
Updated to meet the new rules.
The program runs in an infinite loop which tests every possible increment, in the order 0, -1, 1, -2, -2 ...
Explanation:
Q=eval(input()) implicit
Z=0 implicit
Lnb_b def P(b): return b != rev(b)
WP`+QZ while P(repr(Q+Z)):
=Z-g0ZZ Z=(0>=Z)-Z
) <end while>
Z print(Z)
Example run:
python3 pyth.py programs/palin.pyth <<< 965376457643450
-2969881
This took 23 seconds.
Bonus solution, same character count:
Wn`+QZ_`+QZ=Z-g0ZZ)Z
q~:Q,:LQWf#:+/Q:*LW##Q:+L/_Q2f#:+L/_mq\@/]`
Reads an array of floats (e.g., [1.0 2.0 3.0 4.0 5.0]) from STDIN. Try it online.
{(N÷+/÷⍵)(×/⍵*÷N)A(Q*÷2),(Q←+/(⍵*2)÷N)÷A←+/⍵÷N←⍴⍵}
JyzKlJ=YcsJK=Zcsm^d2JK(cKsmc1kJ ^u*GHJc1K Y ^Z.5 cZY
Reads space-separated numbers (e.g., 1 2 3 4 5) from STDIN.
#!/usr/bin/octave -qf
[mean(I=input(''),"h") mean(I,"g") a=mean(I) q=mean(I.*I)**.5 q*q/a]
Not counting the shebang. Reads an array (e.g., [1 2 3 4 5]) from STDIN.
#!/usr/bin/bc -l
while(i=read()){h+=1/i;g+=l(i);a+=i;q+=i*i;n+=1}
n/h;e(g/n);a/n;sqrt(q/n);q/a
Counting the shebang as 1 byte (-l switch). Reads whitespace separated floats from STDIN, followed by a zero.
#!/usr/bin/awk -f
{h+=1/$0;g+=log($0);a+=$0;q+=$0^2;n++}END{print n/h,exp(g/n),a/n,(q/n)^.5,q/a}
Not counting the shebang. Reads one number per line from STDIN.
n%{~.2.-1:$??./*\`,10\?/\+\;}%..,:^0@{$?+}//p.{*}*^$??p.{+}*^/.p\0\{.*+}/^/.2$??p\/
GolfScript has no built-in support for floats, so the code is parsing them. Therefore, the input format is rather restrictive: you must input 1.0 and 0.1 rather than 1, 1. or .1.
Reads floats (as explained above) one by line, from STDIN. Try it online.
#!/usr/bin/perl -n
$h+=1/$_;$g+=log;$a+=$_;$q+=$_**2}{$,=$";print$./$h,exp$g/$.,$a/$.,($q/$.)**.5,$q/$a
Counting the shebang as 1 byte (-n switch). Reads one number per line from STDIN.
#!/usr/bin/python
h=a=q=n=0;g=1
for i in input():h+=1/i;g*=i;a+=i;q+=i*i;n+=1
print n/h,g**n**-1,a/n,(q/n)**.5,q/a
Not counting the shebang. Reads a list of floats (e.g., 1.0,2.0,3.0,4.0,5.0) from STDIN.
m=I=>{for(g=1,h=a=q=n=0,p=Math.pow;i=I.pop();h+=1/i,g*=i,a+=i,q+=i*i)n++;
return[n/h,p(g,1/n),a/n,p(q/n,.5),q/a]}
Not counting the LF. Expects an array (e.g., [1,2,3,4,5]) as argument.
#!/usr/bin/php
<?for($c=1;$c<$argc;$c++){$i=$argv[$c];$h+=1/$i;$g+=log($i);$a+=$i;$q+=$i*$i;$n++;}
print_r([$n/$h,exp($g/$n),$a/$n,sqrt($q/$n),$q/$a]);
Not counting shebang or LF. Reads floats as command-line arguments.
I have a shorter solution, but I don't know how to count the bytes:
php -R '$i=$argn;$h+=1/$i;$g+=log($i);$a+=$argn;$q+=$i^2;$n++;' \
-E 'print_r([$n/$h,exp($g/$n),$a/$n,sqrt($q/$n),$q/$a]);'
Counting the bytes in each code string and adding two for -R and -E, this approach would score 108.
float i,h,g=1,a,q,n;main(){for(;scanf("%f",&i)+1;n++)h+=1/i,g*=i,a+=i,q+=i*i;
printf("%f %f %f %f %f",n/h,pow(g,1/n),a/n,sqrt(q/n),q/a);}
Not counting the LF. Compile with gcc -lm. Reads whitespace separated floats from STDIN.
To get the ball rolling again, I decided to write a simple entry. As always with brute force methods, it's extremely slow.
def mult(x,y):
c=0
for i in range(len(x)):
if y[i]%x[i]==0:c+=1
if c==3:return True
return False
pyth=lambda x,y:True if (x**2+y**2)**0.5==int((x**2+y**2)**0.5) else False
prev=[]
ymax=245
zmax=269
try:
for x in range(44,10**30):
for y in range(117,ymax):
ymax+=1
for z in range(240,zmax):
zmax+=1
curr=[x,y,z]
eq=0
ml=0
for i in range(3):
for j in range(3):
if i!=j:
if curr[i]==curr[j]:
eq+=1
for k in prev:
if mult(curr, k):
ml+=1
if eq==0 and ml==0:
f=pyth(curr[0],curr[1])
s=pyth(curr[0],curr[2])
b=pyth(curr[1],curr[2])
if f and s and b:
prev.append(curr)
except KeyboardInterrupt:
print('\n\n'+str(len(prev)))
Another port of @edc65's answer, who is the clear winner (IMO):
t`+hQv*l`Q\8
$ for n in 0 1 10 11 42 100 110 111 800 1060 1110 1111 10270 100501; do echo "shortlex.pyth $n = \"$(pyth programs/shortlex.pyth <<< $n)\""; done
shortlex.pyth 0 = ""
shortlex.pyth 1 = "0"
shortlex.pyth 10 = "9"
shortlex.pyth 11 = "00"
shortlex.pyth 42 = "31"
shortlex.pyth 100 = "89"
shortlex.pyth 110 = "99"
shortlex.pyth 111 = "000"
shortlex.pyth 800 = "689"
shortlex.pyth 1060 = "949"
shortlex.pyth 1110 = "999"
shortlex.pyth 1111 = "0000"
shortlex.pyth 10270 = "9159"
shortlex.pyth 100501 = "89390"
Q = eval(input()) Implicit.
t` All but the first digit of
+hQ Q+1 +
v eval(
*l`Q len(repr(Q)) *
\8 "8"
/:+zz1_1z
Or
}z:+zz1_1
These are both close translations of @xnor's python answer, except that they take input from STDIN and print it. The first is equivalent to:
z = input()
print((z+z)[1:-1].count(z))
0 for False, 1 for True.
The second line is equivalent to:
z = input()
print(z in (z+z)[1:-1])
False for False, True for True.
Pyth's official compiler had a bug related to the second one, which I just patched, so the first is my official submission.
J"+K+N+J+N+\K+N+K+NJ"K"J"+K+N+J+N+\K+N+K+NJ
Best played with the fourth setting (amount + and - change interval) at around 20, rest at defaults. Sounds best on the piano.
~Q1Wn`Q_`ePQ~Q1)Q
Explanation:
Implicit: Q = eval(input())
~Q1 Q +=1
W while
n not equal
`Q repr(Q)
`ePQ repr(end(prime_factorization(Q)))
~Q1 Q += 1
) end while
Q print(Q)
10
In Golscript, PHP, CJam, Mathematica, bc, Pyth, ///, and TI-Basic, it outputs 10.
In R, it outputs [1] 10
In Octave, it outputs ans = 10
In Matlab and Scilab, it outputs ans = 10.
In Numeric Topline, it outputs 0.
If I understand Fueue properly, it outputs a newline, then acts as a cat program.
In huh?, it outputs
What?
?
h-U21Q
$ pyth -c h-U21Q <<< '[5, 4, 1, 5, 4, 8, 2, 1, 5, 4, 0, 7, 7]'
3
U21 range(21)
Q eval(input())
-U21Q setwisedifference(range(21), eval(input)) # Pyth function. Preserves order.
h-U21Q setwisedifference(range(21), eval(input))[0]
Now with correct formatting!
j\;mc-dhSQ-eSQhSQQ
Test:
$ pyth -c 'j\;mc-dhSQ-eSQhSQQ' <<< '[0,5,100,400]'
0.0;0.0125;0.25;1.0
Explanation:
(implicit) Q = eval(input())
j\; ';'.join(
m map(lambda d:
c float_div(
-dhSQ d-sorted(Q)[0],
-eSQhSQ sorted(Q)[-1]-sorted(Q)[0]),
Q Q))
K"/\\"Jt+*QdKVQpbJ=JjKsmcd"\ "cj*2dc+Jd_K" /"
$ pyth -c 'K"/\\"Jt+*QdKVQpbJ=JjKsmcd"\ "cj*2dc+Jd_K" /"' <<< 16
/\
/\/\
/\ /\
/\/\/\/\
/\ /\
/\/\ /\/\
/\ /\ /\ /\
/\/\/\/\/\/\/\/\
/\ /\
/\/\ /\/\
/\ /\ /\ /\
/\/\/\/\ /\/\/\/\
/\ /\ /\ /\
/\/\ /\/\ /\/\ /\/\
/\ /\ /\ /\ /\ /\ /\ /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
# Q = eval(input())
K"/\\" # K = "/\\"
Jt+*QdK # J = (Q * " " + K)[1:]
VQ # for N in range(Q):
pbJ # print(J, end="\n")
#
=JjK # J = K.join(
sm # sum(list(map(lambda d:
cd"\ " # d.split("\ "),
c # .split( )
j*2d # " ".join( )
c _K # .split(K[::-1])
+Jd # (J + " ")
" /" # " /"
# ))))
j\,o_mx_zdNchczd\,
Test:
$ pyth -c "j\,o_mx_zdNchczd\," <<< 'home,oval,cat,egg,network,green bcdfghjklmnpqrstvwxzaeiouy'
cat,green,home,network,egg,oval
Explanation:
Implicit: d=" "
Implicit: z=input()
j\, ",".join(
o order_by(lambda N:
_ rev(
m map(lambda d:
x_zd rev(z).index(d),
N N),
chczd\, z.split(" "[0].split(",")
Essentially, it sorts the chunks, with a key of the list of indexes of the characters in the string, then joins them on commas. The reversal businesses is shorter than spliting the string again.
VQ~Z!%vw3)Z
$ echo -e 10 \\n{1..10} | pyth -c 'VQ~Z!%vw3)Z'
3
Q, Z = eval(input()), 0
VQ for N in Q:
~Z Z +=
!%vw3 !(eval(input()) % 3)
) endfor
Z print Z
p*w3"STAA
Examples:
$ pyth -c 'p*w3"STAA' <<< 0
STAA000
$ pyth -c 'p*w3"STAA' <<< 677111
STAA677111677111677111
This is exactly equivalent to the following python 3 code:
print("STAA", end=input()*3)
The *3 is necessary to guarantee the result is at least 7 characters.
QW!}QY~Y]Q=Q_S+fTmtdQ]lQQ
This is pretty close to a translation of my python 2 answer.
Sample run:
Input:
[4,4,3,2,1]
Output:
[4, 4, 3, 2, 1]
[5, 3, 3, 2, 1]
[5, 4, 2, 2, 1]
[5, 4, 3, 1, 1]
[5, 4, 3, 2]
[4, 4, 3, 2, 1]
How it works:
Q Q = eval(input()) # automatic
W!}QY while not Q in Y:
~Y]Q Y += [Q]
fTmtdQ filter(lambda T: T, map(lambda d: d - 1, Q))
_S+ ]lQ sorted( + [len(Q)])[::-1]
=Q_S+fTmtdQ]lQ Q = sorted(filter(lambda T: T, map(lambda d: d - 1, Q)) + [len(Q)])[::-1]
Q print(Q)
QW!}QY~Y]Q=Q_S+fTmtdQ]lQQ
]l~{a+_W=_p:(_,+$W%{},1$1$a#0<}gp;
Test it here. Enter input as a CJam-style array, like [5 3], into the STDIN field. Output format is similar, so square brackets and spaces as delimiters.
Even if I golf this down further (which is definitely possible), there's no way to beat Pyth with this. Maybe it's time to learn J. Explanation coming later.
+"S"$"top giving me shift!".lower()
I can't seem to find Pyth's version of lower(), so I'll borrow from Python. The characters that can't be swapped are +"S"$, !, and .lower(), for a total of 14 chars. The quotes after the $ must match, adding another power of 2.
Note: This is actually 3 answers in one. I didn't see the point of splitting it into multiple answers when they are such literal translations of each other. If they should be split, let me know and I'll take care of that.
print''.join(map(chr,map(len,' '.split(' '))))
Just to provide a different style of solution. It encodes the ascii value of each character in tabs, split on spaces. The number of tabs is the number for the ascii value.
This is an identical solution in
j""mCldc" "d
Another identical solution - except spaces replaced with newlines - in
'
'n/{,}%+
Pyth has 3 categories of variables: generic pre-initialized variables, variables pre-initialized based on user input, and variables that implicitly generate an assignment on first use.
b = "\n"
d = " "
k = ""
G = "abcdefghijklmnopqrstuvwxyz"
H = {} # (empty dict)
N = '"'
T = 10
Y = []
Z = 0
Q = eval(input())
z = input()
Note that these initializations will only be run in a given program if the associated variable is used outside of a string in the code. In addition, the order is Q, then z, if both are used.
J and K. They are nearly identical, except that J makes a copy of the assignment target, while K does not. If you want to initialize them both to the same value, you can do so with an expression such as KJ0, which is equivalent to the lengthier J0K0.
Pyth is so similar to Python that it is pretty easy to translate Python programs to Pyth. However, because Pyth is a single-letter-per-command language, it is sometimes hard to write straight Pyth. By writing in Python first, there is less to think about at a time (since Python is a pretty easy language to code in).
I'm fairly regularly improving Pyth, removing less useful features and adding more useful ones, so keep an eye out for what's new and update your copy of the implementation regularly.
Some recently added features: (as of 10/19/14)
y: Acts as *2 on numbers, and as list of all subsets on strings and lists. For instance:
pyth -c 'y"abc'
['', 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc']
f: f is normally the filter command. Now, when called with a number as its second argument, it will filter over the infinite sequence starting with that number and counting up by ones, then return the first element of the resulting sequence.
For instance, here's the code to find the smallest prime over a billion:
pyth -c 'f!tPT^T9'
1000000007
j>", "qlQ2+_t_Q+?"and "tQkeQ
$ pyth programs/oxford.pyth <<< "['1']"
1
$ pyth programs/oxford.pyth <<< "['1','2']"
1 and 2
$ pyth programs/oxford.pyth <<< "['1','2','3']"
1, 2, and 3
hf}z*lzTm<zdUz
Explanation:
implicit: z = input()
h head(
f filter(lambda T:
}z z in
*lz len(z) *
T T,
m map(lambda d:
<zd z[:d],
Uz range(len(d)))))
Essentially, it generates all of the initial sequences of the input, repeats each one len(z) times, and sees whether z, the input, lies within the resultant string.
This is not a valid answer, but a feature was recently added to Pyth, after the question was asked, that allows a 12 character solution:
<zf}z*lz<zT1
This uses the filter on integer feature.
F: For loop. Just like Python's.
V: For loop over a range. Neither variable nor range must be given, so 2 characters shorter.
W: While loop. Just like Python's.
#: Infinite while loop. Escape with error or explicit break. Only try ... except feature now in Pyth.
D: General define. Just like Python.
L: 1 argument, no assignment function, like Python's lambda, but named. Function name, variable name and return (R) need not be given, so 3 characters shorter.
f: Filter - select elements of input sequence that return truthy on input lambda.
f: First integer greater than or equal to input which gives truthy filter result.
m: Map - transform elements of input sequence using input lambda.
u: Reduce - fold input sequence on input lambda, initializing accumulator to third argument.
o: Order - older elements of input sequence using input lambda as the key.
Usually, there will be multiple possibilities for any given problem, and only by writing test solutions with each of them can you figure out which is shortest.
V4+"Happy Birthday "?"to You"nN2"Dear Pyth
Demonstration:
$ pyth -c 'V4+"Happy Birthday "?"to You"nN2"Dear Pyth'
Happy Birthday to You
Happy Birthday to You
Happy Birthday Dear Pyth
Happy Birthday to You
How it works:
V4 sets up a for loop, with N iterating over 0, 1, 2, 3.
Then, we create the string starting with "Happy Birthday ", and ending with "to You" if N does not equal 2 (nN2 calculates this), or ending with "Dear Pyth" otherwise.
Exact tie with CJam - language name and character count.
Alternative, 43 character solution:
J"Happy Birthday to You"JJ+<J15"Dear Pyth"J
It's one character longer because it needs an end quote.
DaGHR?atG?aGtHH1GhH
Defines a, which works as the Ackermann function. Note that this requires a higher recursion depth than the official pyth compiler allowed up until today to compute a 3 10, so I increased the recursion depth. This is not a change to the language, just to the compiler.
$ time pyth -c "DaGHR?atG?aGtHH1GhH ;a 3 10"
8189
real 0m0.092s
user 0m0.088s
sys 0m0.000s
DaGH def a(G,H):
R return
? G (if G:
atG (a(G-1,
? H (if H:
aGtH a(G,H-1)
1 else:1)
hH else:H+1)
Essentially, it first conditions on the truth value of G whether to recurse or return H+1. If it is recursing, the first argument is always G-1, and it conditions on the truth value of H whether to use a(G,H-1) as the second argument, or to use 1 as the second argument.
*ltG%"The eigh%srum%snine%sfun%stwo-thousands are a time to run\na civilized classroom.\n"*hhZ("teen-hundreds were a time for "".\nThe
Note the trailing space.
Uses pretty much the same trick as @Geobits and his commenter friends in the Python answer to construct the string. Now also uses some of this answer.
This uses the built-in variable G, which contains abcdefghijklmnopqrstuvwxyz and gets one less than its length to produce the 25 outputs.
u+/*GHhyHy^T500r^3T1Z
Uses this algorithm:
pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + ...)))) found in the comments of the Golfscript answer. Note that Pyth is invalid for the question because it was created after the question was asked.
FN_SQFbYIgeeYeb~b]NB)E~Y]]N;sY
This is a direct golf of grc's awesome algorithm. Here is the precise equivalent of the above pyth program, in its compiled python code.
Q = eval(input())
Y = []
for N in sorted(Q)[::-1]:
for b in Y:
if Y[-1][-1] >= b[-1]:
b += [N]
break
else:
Y += [[N]]
print(Psum(Y))
In this context, the Psum(Y) function is equivalent to the python sum(Y,[]).
Actual compiled and run code (from pyth -d):
Y=[]
Q=copy(eval(input()))
for N in neg(Psorted(Q)):
for b in Y:
if gte(end(end(Y)),end(b)):
b+=[N]
break
else:
Y+=[[N]]
Pprint("\n",Psum(Y))
A silly answer:
from this import i
a="teen-hundreds were a time for ",".\nThe "
print"The eigh%srum%snine%sfun%stwo-thousands are a time to run\na civilized classroom.\n"%(a+a)*i
Note that the full count is 162. I left out all of from this import i.
Uses similar replacements to my pyth strategy, but I couldn't resist posting this after discovering the hilariousness of importing from this :)
Requires all 3 arguments as separate inputs.
#Vvw=z+tz*@Q%NlQshz)zq
Takes arguments like:
11001
["010","000","1111"]
4
Explanation:
: Implicit: z = input(); Q=eval(input())
# : Loop until an exception is thrown
Vvw ) : for N in range(eval(input()))
=z : assign to z
+tz : the sum of the tail of z and
*@Q%NlQ : Q[N%len(Q)] times
shz : the numeric value of the first character in z
zq : print z then throw exception
c=lambda p,w,g:g*w and c(p[1:]+p[:1],w[1:]+w[0]*p[0],g-1)or w
Pretty Joe-Basic answer. Assumes the empty production is [[]].
Thanks to @xnor, for pointing out that golfing at 2 a.m. is a poor decision.
Additional thanks to @xnor, to whom I seem to owe 50% of my score.
Sample:
>>> c([[0,1,0],[0,0,0],[1,1,1,1]],[1,1,0,0,1],4)
[1, 0, 1, 0, 0, 0, 0]
L?/1lbf!tfaYTbbsmy-b]db
Explanation:
L: defines a function, y, of one input, b. Returns the value of its body.
?: _ if _ else _
The first argument to ? will be the value returned if we terminate. The second will be the termination test, and the third will be the recursive case.
/1lb: If we terminate, there are two possibilities: we have reached a graph with 1 edge, or we have reached a clearly disconnected graph, which thus has more than one edge. /1lb is 1, floor divided by the length of the input graph. This returns 1 in the base case of a 1 edge graph, or 0 in any disconnected termination case.
faYTb: This is the inner filter of 2nd argument. It filters out every edge Y that overlaps with the edge T of the outer filter. a is setwise intersection.
!tfaYTb: ! is logical not, t is tail, so this will be True if there is exactly 1 edge sharing a vertex with T, or False otherwise.
f!tfaYTbb: This runs the above test on every edge in the graph. It is evaluated in a boolean context, and it is truthy if any edge in the graph shares no vertices with any other edge in the graph. If this is the case, we terminate, because the graph is either disconnected or has 1 edge. Note that there are some disconnected graphs that we do not terminate on, but their recursive calls will eventually terminate with a return value of 0.
smy-b]db: This is the recursive case. We take the sum, s, of the edge elimination number, y, of the graph with each edge removed. -b]d is b with the edge d removed, y-b]d is the EEN of that graph, and my-b]db is this value for d being each edge in the graph, and smy-b]db is the sum of those values.
Tests: (yQ runs the function on the input)
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1)]'
1
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1), (1,2), (2,3), (3,4)]'
8
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1), (1,2), (0,2), (0,3), (0,4)]'
92
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,2), (0,4), (1,2), (1,4), (2,5), (3,4), (3,5)]'
1240
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,2),(0,3),(1,3),(1,4),(1,5),(2,3),(3,4),(3,5)]'
16560
"Hello World!
This answer is a distance of 6 from the previous answer. Pyth strings do not need a closing quote if they are at the end of a line.
VQCN
Basically a translation of the Python 3 program:
for N in range(eval(input())):print(chr(N))
Reserved character: ~
println!~~~~~~~
puts (1,~~~~
echo '~~~~
"cWprintfn"Ja~~~
Eork~~~;'Jabbe~~
\ui)K00~~~~~br~~
]tteL~0~~~~~ew~~
]<~ln(0~~~~~ro~~
`<~~~ 0~~~~~wc~~
m"~~~ "~~~~~ok~~
rJ~~~'J~~~~~cy~~
j"<< "a~~~~~k'..
^~~~~~bberwoy");
f~~~~~~~~~~c' ;
t~~~~~~~~~~ky"
XX");); 5f+');
Languages:
01. Rust | println! ( "Jabberwocky") ; |
02. Groovy | println "Jabberwocky" |
03. E | println ( "Jabberwocky") |
04. Swift | println ( "Jabberwocky") ; |
05. Julia | println ( "Jabberwocky");; |
06. Processing | println ( "Jabberwocky") ; |
07. Falcon | printl ( "Jabberwocky") |
08. ALGOL 68 | print ( "Jabberwocky") |
09. Vala | print ( "Jabberwocky") ; |
10. Pawn | print ( "Jabberwocky");; |
11. Batsh | print ( "Jabberwocky") ; |
12. freeBASIC | print "Jabberwocky" |
13. Rebol | print "Jabberwocky" ; |
14. Red | print "Jabberwocky" ; |
15. AWK | print 'Jabberwocky' |
16. Perl | print 'Jabberwocky' ; |
17. bc | print 'Jabberwocky' ; |
18. Euphoria | puts (1,"Jabberwocky") |
19. C | puts ( "Jabberwocky") ; |
20. Tcl | puts "Jabberwocky" |
21. Ruby | puts 'Jabberwocky' |
22. Zsh | echo "Jabberwocky" |
23. Bash | echo "Jabberwocky" ; |
24. tcsh | echo "Jabberwocky" ; |
25. PHP | echo 'Jabberwocky' |
26. Fish | echo 'Jabberwocky' ; |
27. Dash | echo 'Jabberwocky' ; |
28. F# | printfn"Jabberwocky" ; |
29. C++ | cout<<"J"<< "abberwocky" ; |
30. D | Writeln( 'Jabberwocky'); |
31. Pascal | WriteLn( 'Jabberwocky'); |
32. Delphi | Writeln( "Jabberwocky"); |
33. GolfScript | print;'Jabberwocky'..;; |
34. CJam | "E\]]`mrj^ftXX");); 5f+'); |
35. Pyth | pk)K00000"Jabberwocky" |
(Pyth and CJam thanks to user23013)
Vzjdm?@zd}N,dt-lzd\ Uz
Test:
$ pyth -c 'Vzjdm?@zd}N,dt-lzd\ Uz' <<< "CODE-GOLF"
C F
O L
D O
E G
-
E G
D O
O L
C F
Explanation:
(Implicit) z = input()
(Implicit) d = ' '
Vz for N in range(len(z)):
jd print(d.join(
m map(lambda d:
?@zd z[d] if
}N N in
,dt-lzd (d,len(z)-d-1) else
\ " ",
Uz range(len(z)))))
eDSGRjkmCdGJC96P:Sj4142h118J:Sj9927h112J:Sjt11641t112J:Sj11154t115J:SjxT14142t122J:Sj4128h125J:Sj11154t115J:Sj4128h125J:Sj11196t112J:Sjt14254t122J:Sj12195t112J:Sj12752t114J:Sj5248h111J:Sj4142h118J:Sj4128h125J:Sj5181h112J:Sj4128h125J:Sj9116t111J:Sj12528h111J:Sj14126h121J:Sj11154t115J:Sj4128h125J:Sj8566t111J:Sj12528h111J:Sj11976t111J:Sj11646t111J:Sj12416h111J:Sj11711t116JJ
Output is quote 62:
"What a dump." - Rosa Moline
Uses the characters 12456789:CDGJPRSTdhjkmtx.
Previously forbidden: z" &'()*+,-./03;<=>@X[\]psy{
It's based on a series of regex substitutions - : in pyth, each replacing `, the backtick character, with a two character string containing a new character followed by a backtick.
The substitutions are all applied to an original string of just ` (J).
The two letter strings are generated by using the base changing function, j, on a number and a base to generate an list entry of numbers, which are then ASCII encoded into a 2 character string by the newly defined S function.
Explanation:
DSGRjkmCdG define S, which makes a string out of a list of ASCII numbers
JC96 J = "`"
P print all but the last character of
:Sj4142h118J "` <- `
:Sj9927h112J W` <- `
:Sjt11641t112J h` <- `
:Sj11154t115J a` <- `
:SjxT14142t122J t` <- `
:Sj4128h125J ` <- `
:Sj11154t115J a` <- `
:Sj4128h125J ` <- `
:Sj11196t112J d` <- `
:Sjt14254t122J u` <- `
:Sj12195t112J m` <- `
:Sj12752t114J p` <- `
:Sj5248h111J .` <- `
:Sj4142h118J "` <- `
:Sj4128h125J ` <- `
:Sj5181h112J -` <- `
:Sj4128h125J ` <- `
:Sj9116t111J R` <- `
:Sj12528h111J o` <- `
:Sj14126h121J s` <- `
:Sj11154t115J a` <- `
:Sj4128h125J ` <- `
:Sj8566t111J M` <- `
:Sj12528h111J o` <- `
:Sj11976t111J l` <- `
:Sj11646t111J i` <- `
:Sj12416h111J n` <- `
:Sj11711t116J e` <- `
J Starting with `
Encoder:
Jf-\'T'jdm@JdjswlJ
Takes two arguments: a dictionary on one line, and the date, in DDMMYYYY form on the next.
Filters out words with apostrophes from the dictionary, then converts the current date into a number with base equal to the dictionary length, and then chooses words from the filtered dictionary with indexes of the digits, and prints them out, space separated.
Today's result:
$ pyth -c "Jf-\'T'jdm@JdjswlJ" <<< '/usr/share/dict/words
30102014'
Annam pals
Future results:
31102014
Antarctica economical
01112014
Abernathy carousels
02112014
Acadia unsnarled
03112014
Actaeon oversimplifying
04112014
Adela dugouts
0511204
Adolph Maude
To decode, run the date through the program and see if the output matches the name given. I'm not going to list any more band names, but from how the program works it should be clear there are no repeats.
Here's something to get the ball rolling. I decided to do the elements in order because I don't know enough languages for the order to matter much.
public class P{public static void Main(){System.Console.Write("Hydrogen");}}
W forbiddenecho$e="Helium";
W$ forbidden?"Lithium"
W$? forbiddendir>nul&echo Beryllium
W$?& forbidden++++++[>+++++++++++<-]>.----------[>++<-]-.+++.---.-.
Outputs Boron.
W$?&+ forbidden#include<iostream>
main(){std::cout<<"Carbon";}
W$?&+< forbidden"n eg or ti N">,_@
Outputs Nitrogen.
W$?&+<@ forbiddenecho Oxygen 2>1
W$?&+<@> forbidden9 print "Fluorine"
W$?&+<@>9 forbidden#include"stdio.h"
main(){printf("Neon%c",10);}
W$?&+<@>9, forbidden(format t "~Codium" #\S)
W$?&+<@>9,# forbiddenif 1\=0:print"Magnesium";end if
W$?&+<@>9,#\ forbidden:-write('Aluminium').
(Test here.)
W$?&+<@>9,#\: forbiddenclass A{public static void main(String[]a){System.out.print("Silicon");}}
W$?&+<@>9,#\:. forbidden];"Phosphorus"
W$?&+<@>9,#\:.] forbidden|0"Sulfur
W$?&+<@>9,#\:.]| forbiddentrace("Chlorine");
W$?&+<@>9,#\:.]|; forbiddenwrite-host"Argon"
Fortunately, PowerShell commands can be written in lowercase, avoiding the forbidden W.
W$?&+<@>9,#\:.]|;- forbiddenalert("Potassium")
W$?&+<@>9,#\:.]|;-" forbiddenprint('Calcium')
W$?&+<@>9,#\:.]|;-"( forbiddenprint'Scandium'
W$?&+<@>9,#\:.]|;-"(' forbiddensay q{Titanium}
W$?&+<@>9,#\:.]|;-"('{ forbiddenputs %q!Vanadium!
W$?&+<@>9,#\:.]|;-"('{! forbidden67c104c114c111c108)c105c117c108)c
Outputs Chromium. ) increments were used to avoid the forbidden 9 in 109 (m).
I might add to this later, but here are 51 languages.
public class p{public static void main(String[]J){System.out.println("Tellurium");}}
J forbidden#include<cstdio>
main(){int Q=std::puts("Palladium");}
JQ forbiddenmain(W){puts("Neodymium");}
JQW forbiddenimport std.stdio;void main(string[]z){write("Zirconium");}
JQWz forbiddenvar q="Ruthenium"
echo q
JQWzq forbiddenprogram Y
print *,"Potassium"
end program Y
JQWzqY forbidden@set @c=Aluminium&echo %@c%
JQWzqY% forbidden"muinoloP">:#,_@
Output Polonium.
JQWzqY#% forbiddenint main(string[]@a){print("Manganese");return 0;}
JQWzqY#%@ forbiddencd /usr/bin ~/cake;./echo Germanium
JQWzqY#%@~ forbiddenalert(`Strontium`)
JQWzqY#%@~` forbidden$_=Magnesium;say
JQWzqY#%@~`_ forbiddenobject e{def main(args:Array[String]){print("\u0059tterbium")}}
JQWzqY#%@~`_: forbidden$j='Lanthanum';say
JQWzqY#%@~`_:j forbiddenprint'Lutetium'
JQWzqY#%@~`_:jL forbiddenprint('Krypton')
JQWzqY#%@~`_:jLK forbidden$n='Berkelium';echo$n;
JQWzqY#%@~`_:jLK$ forbiddenProgram f(X);begin write('Ununtrium');end.
JQWzqY#%@~`_:jLK$X forbiddenpoock!pogack?poock!pock!pock!pock!pock!pock!pock!pogack!pogaaack!pogaack!pogaack?pogack!poock!pogaaack?pogack?poock!pock!pock!pogack!pogaaack!pock!pock!pock!pock!pogaack!pogaack?pogack!pogaaack!pogaaack?poock!pock!pogack?poock!pogack!pogaaack!pock!pock!pogaack!pogaack?pogack!poock!pogaaack?pogaaack!pock!pock!pock!pock!pock!pock!pock!pock!pock!pock!pock!pock!pock!pogaaack?poock!pock!pock!pogaaack?poock!pock!pock!pock!pock!pock!pock!pock!pogaaack?poock!pock!pogaaack?pogaaack!pock!pock!pock!pock!pock!pock!pock!pogaaack?
Prints Hydrogen.
JQWzqY#%@~`_:jLK$Xg forbiddenMoOMoOMoOMoOMOOmoOMoOMoOMoOMoOMoOmOoMOomoomoOMOOmoOMoOMoOMoOMoOmOoMOomoomoOMooMoOMOOMOoMOoMOomoOMoOMoOMoOMoOmOomoomoOMooMoOMoOMoOMoOMoOMoOMoOMoOMoOMooMOoMooMOoMOoMOoMOoMOoMooMOoMooMOoMOoMOoMOoMOoMooMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMooMOoMOoMOoMOoMOoMOoMOoMOoMoo
Prints Plutonium.
JQWzqY#%@~`_:jLK$XgM forbiddenBlub!Blub!Blub!Blub?Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub.Blub?Blub.Blub.Blub?Blub.Blub?Blub!Blub.Blub?Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub.Blub!Blub!Blub!Blub!Blub!Blub?Blub!Blub!Blub!Blub!Blub!Blub!Blub.Blub?Blub.Blub.Blub?Blub.Blub?Blub!Blub.Blub?Blub!Blub.Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub!Blub.Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub!Blub.Blub!Blub?Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub.Blub?Blub.Blub.Blub?Blub.Blub?Blub!Blub.Blub?Blub!Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub.Blub!Blub.Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub!Blub.
Prints Flerovium.
JQWzqY#%@~`_:jLK$XgMB forbiddenOok!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook?Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook.Ook?Ook.Ook.Ook?Ook.Ook?Ook!Ook.Ook?Ook.Ook.Ook.Ook.Ook!Ook.Ook!Ook?Ook!Ook!Ook!Ook!Ook!Ook!Ook.Ook?Ook.Ook.Ook?Ook.Ook?Ook!Ook.Ook?Ook.Ook.Ook.Ook.Ook!Ook.Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook!Ook.Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook.Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook!Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook.Ook!Ook.Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook!Ook.
Prints Americium.
JQWzqY#%@~`_:jLK$XgMB! forbiddendef e?()return "Neptunium"end;print e?
JQWzqY#%@~`_:jLK$XgMB!? forbiddenf=2*4 if f==8then print("Titanium")end
JQWzqY#%@~`_:jLK$XgMB!?* forbiddenU<-"Rubidium";print(U)
JQWzqY#%@~`_:jLK$XgMB!?*U forbidden(display "Francium")
JQWzqY#%@~`_:jLK$XgMB!?*U) forbiddenDisp ("Vanadium"
JQWzqY#%@~`_:jLK$XgMB!?*U)( forbiddendo Z=1 to 1
say 'Europium'
end
return
JQWzqY#%@~`_:jLK$XgMB!?*U)(Z forbiddenPRINT "Chromium"
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI forbidden|0"Scandium
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI| forbidden"Nobelium"1\\-
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\ forbidden"Samarium"1/
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/ forbidden,>-[--->+<]>-----.+[--->++++<]>.-----------.--[--->+<]>-.-----------.+++++.+++++++.--------.
Takes an empty string as input.
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/, forbidden'Antimon'++['y']
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[ forbiddeniisiiiisiiiiiioiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiioiiiiiiiiioddddddoiiiodddddddddoiiiiiodddddddddo]
One of the few of these snippets to output a newline afterwards.
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[] forbiddenPR"Tungsten"
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P forbiddenputs "Actinium"
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P" forbiddena named a a a once was there Fred once a a fish named a a a a a once was was was there Fred once fish was was was was was was was fish a a a a a a a fish was was was was was was was was was fish a a a a a fish was was was was was was was was was was was was fish a a a a a a a a fish
Prints Selenium.
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"F forbiddeneris 23 eris eris eris fnord hail pineal 5 fnord eris eris eris eris eris eris eris kallisti 23 eris eris eris fnord hail hail hail hail pineal 5 fnord hail kallisti hail hail hail hail hail hail hail hail hail hail hail kallisti eris eris kallisti eris eris eris kallisti eris eris eris eris eris eris eris eris kallisti eris eris kallisti hail hail hail hail hail hail hail hail hail kallisti
Prints Nitrogen.
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fl forbiddenAstatine
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fln forbidden'Caesium'
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fln' forbidden3.4743302180342223222232222423222332223225222222427402331802252232322322343223322224434433435
Prints Tantalum.
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fln'. forbidden43686C7072696E65
-- }0
Prints Chlorine. This relies on the use of spaces for empty cells. Marbelous Interpreter
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fln'.} forbiddenATCGGCTAATCGATCGATCGATATATTAATGCGCCGATATATCGGCATGCTAATCGATCGATCGATCGATATATTAATTAATTAATTAATTAATGCGCCGATATATCGGCATATCGATCGATCGATCGATCGATCGATCGGCATATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAGCATGCATATCGATCGATCGGCATATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAGCATATCGATCGATCGATCGATCGATCGATCGATCGGCAT
Prints Thallium.
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fln'.}G forbiddenOoOOoOOoOOoOoOoOoOOoOOoOOoOoooOooOooOooooOoOOoooOooOOoOooOooOoooOoOooOooOooOooOoooooOoOooOoOOoooOooOOoOooOooOooOOoOooOooOOoOooOooOooOooOOoOoOOoOOoOOoOOoOOOoOooOooOooOooOooOooOooOooOooOOo
Prints Bromine.
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fln'.}GO forbiddenAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAAAAACAAAAAC
Prints Tin. Note that the interpreters on esolang are all unavailable. However, 4chan's implementation written in Scheme works (#59).
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fln'.}GOC forbiddenw1sssdwwa2dwwwe1sssdwa2dweessesssssssssewwwwwwwwwwwwesssssssse
Prints Yttrium.
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fln'.}GOCw forbidden99 105 110 101 115 114 65
if outputascii fi
Prints Arsenic.
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fln'.}GOCws forbidden1334726751425099782624362025339077479253628945660119316869724137277474322140
Prints Lithium.
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fln'.}GOCws1 forbiddenThe source is 0 repeated
40732627912143966203790325934799402365062057246763194506454552300861148
times.
Prints Hassium.
JQWzqY#%@~`_:jLK$XgMB!?*U)(ZI|\/,[]P"Fln'.}GOCws10 forbiddenThe source is > repeated
9305604867582777545366404070305393137665254080212227303922021923795365639900
times.
Prints Bohrium.
Please note that all brainfuck (and brainfuck derivatives) snippets were written with 8-bit cells in mind.
I set out to beat the 20 language answer... and now I can't be bothered to shoot for 52. ;)
J;"Krypton"
J forbiddenK=1;puts 'Vanadium'
JK forbiddenQ=1;print 'Xenon'
JKQ forbiddenX=1;print('Osmium')
JKQX forbidden$V=1;echo 'Oxygen';
JKQXV forbiddenO=1;println('Ytterbium')
JKQXVO forbiddenY=1;alert('Yttrium')
JKQXVOY forbiddenq=1;alert 'Zinc'
JKQXVOYq forbiddenmain(Z){printf("Zirconium");}
JKQXVOYqZ forbidden#include <cstdio>
int main(){int x;printf("Lawrencium");}
JKQXVOYqZx forbiddenw=1;'Nickel'
JKQXVOYqZxw forbidden$k=1;print "Berkelium";
JKQXVOYqZxwk forbidden$f=1;say'Darmstadtium';
JKQXVOYqZxwkf forbiddenpublic class p{public static void main(String[]v){System.out.println("Dubnium");}}
JKQXVOYqZxwkfv forbidden44797370726F7369756D
Prints Dysprosium.
JKQXVOYqZxwkfvD forbiddenG=1;print("Erbium")
JKQXVOYqZxwkfvDG forbiddenF=1;disp('Einsteinium');
JKQXVOYqZxwkfvDGF forbiddenfn main(){let E=1;println!("Europium");}
JKQXVOYqZxwkfvDGFE forbiddenprint *,"Indium"
JKQXVOYqZxwkfvDGFEp forbiddenH;"Iodine"
JKQXVOYqZxwkfvDGFEpH forbiddenU"Iridium"
JKQXVOYqZxwkfvDGFEpHU forbiddenI1"Iron
I think this should be
if 1:
print "Iron"
JKQXVOYqZxwkfvDGFEpHUI forbidden++++++++[>+>++>+++>++++>+++++>++++++>+++++++>++++++++>+++++++++>++++++++++>+++++++++++>++++++++++++>+++++++++++++>++++++++++++++>+++++++++++++++>++++++++++++++++<<<<<<<<<<<<<<<<-]>>>>>>>>++.--<<<<<<<<>>>>>>>>>>>>>---.+++<<<<<<<<<<<<<>>>>>>>>>>>>>>++.--<<<<<<<<<<<<<<>>>>>>>>>>>>>>>+.-<<<<<<<<<<<<<<<>>>>>>>>>>>>>>----.++++<<<<<<<<<<<<<<>>>>>>>>>>>>>>----.++++<<<<<<<<<<<<<<>>>>>>>>>>>>>+.-<<<<<<<<<<<<<>>>>>>>>>>>>>>>---.+++<<<<<<<<<<<<<<<>>>>>>>>>>>>>>---.+++<<<<<<<<<<<<<<.
Prints Beryllium.
JSrz7j\,-f%T2rhJeJJ
J is the list of integers, sorted. rhJeJ gives all of the possible integers between the min and max of the input. f%T2 filters out the even numbers. -_J filters out the original elements of J. j\, joins the resultant list on commas, and the string is automatically printed.
f=->s{" !#+/7OďǿȗϟЏ'"[%w{fa fp ^pe|co r..p ^gr x|ta sh|^b fl|b f.c ^c f.s .gu d|v ^g .}.index{|k|s[/#{k}/]}].ord-31}
$><<gets.sub(/ (.+ i)n /){" #{r=$1}s %0.4f ".%$`.to_f/f[$']*f[r]}
Takes input from STDIN and prints to STDOUT.
I'm using short regular expressions to match only the desired denominations for each value. There are two arrays, one with regexes and one with values, at corresponding indices. The regex array is a space delimited array literal, and the value array is packed into a string of UTF-8 characters.
I'm selecting the index into the values by searching for a regex that matches each denomination. I'm also defaulting to the tuppence/half-groat case (value 8), because that required the longest regex. Likewise, some of the patterns assume that other values have already been matched by earlier patterns, so each regex only distinguishes the desired value only from the remaining ones. Using this, I could probably shave off another couple of bytes by rearranging the order of the denominations.
Thanks to Ventero for helping me beat Pyth making it shorter!
smCid2c:?zv@z2_z3_4 7
Explanation:
?zv@z2_z Input if 3rd character of input is 1, else reversed input.
: 3_4 Slice out the middle portion, ASCII of the above string.
c 7 Chop into 7 character chunks.
mCid2 Convert each chunk from binary to integer, then to a character.
s Sum up the characters into a string and print.
Note that while the question is older than the language, the existence of the question did not influence the design of the language in any way, because I haven't seen the question before today.
Still rules are rules, so I'm making it CW.
K4J24L?*y>b-5>b\t?2>b\t.5}<b2"hatw"@[1K8K12K16J48J1008*JT96*2J960)xc"fapetucothengrsishtagucrflbo"2<b2AGHcz" in"++G%" is %0.4f"*vhcGdcyjdtcGdytHH
More readable (newlines and indents must be removed to run):
K4J24
L?*y>b-5>b\t?2>b\t.5
}<b2"hatw"
@[1K8K12K16J48J1008*JT96*2J960)
xc"fapetucothengrsishtagucrflbo"2<b2
AGHcz" in"
++G
%" is %0.4f"
*vhcGdcyjdtcGdytH
H
Update: Turns out, it's 1 character shorter (no space needed) to chop up the string into a list of 2 character strings before running the string index operation. /x"string"<b2 2 -> xc"string"2<b2. Nothing else needs to be changed.
How it works:
This uses @xnor's approach of looking up the value of currency using its first two letters, as well as the trick of detecting the initial half or two, removing it and calling the function again.
To lookup the value of the first two characters, it finds the location of the first two letters of the currency in a string, then divides by 2 and takes the value at that index in the list. This is much shorter than an dict in pyth.
Uses the fact that x (find within string) returns -1 on failure to avoid putting po (pounds) qu (quid) or so (sovereigns) in the string, and simply return the last element of the list, 960, by default.
By rearranging the order of currencies in the lookup system and initializing carefully, with K4 and J24, all spaces that would have been needed to separate numbers in the list were removed.
Uses pyth's dual assignment operator, A, on the input split on in to get the beginning and end of the input in separate variables.
Does essentially the same lookup at the end, though pyth has no .split(_,1), so it is somewhat more cumbersome.
Examples:
$ pyth programs/currency.pyth <<< '5 florins in half guineas'
5 florins is 0.9524 half guineas
$ pyth programs/currency.pyth <<< '0.4 quid in sixpenny bits'
0.4 quid is 16.0000 sixpenny bits
l$:L{L\/,~}${:DM+:MD/,LD/,d/}$
Takes the input string via STDIN
Inspired by recursive's approach, but a little different. No need of transpose or rectangle at all!.
How it works:
l$:L "Sort the input line and store it in L";
{ }$ "Sort the string based on this code block output";
L\/,~ "Sort based on number of occurrences of each";
"character in the full string";
{ }$ "Sort the sorted string again";
:DM+:M "Store each character in D, add to M and update M";
D/, "Count occurrences of D in M";
LD/, "Count occurrences of D in L";
d/ "Sort string based on the ratio of two occurrences";
(Sad that CJam can no longer complete with Pyth due to need of so much bloat as syntax)
*42qzsm*dhxGdG
Just constructs the necessary string, then compares with the input and multiplies by 42.
This could also almost certainly be golfed further ;)
Ko_/zNS{zFGK~Y]*+*t/u*GHm/zdK1/zG]k]G/zG)ssCY
Works by building a list of lists, where each inner list is a row of empty strings and the name of the candy. This list is transposed and then the inner lists are joined followed by these lists being joined.
Thanks @isaacg for reminding me about sum!
shCoc/NhN/zhNm>o_/zZSzdUz
Uses an all new algorithm, inspired by this answer.
(implicit) z = input()
(implicit) print
s combine list of strings into one string
h first list in
C matrix transpose of (e.g. first characters in first list, etc.)
o order_by(lambda N:
c float_div(
/NhN N.count(N[0]),
/zhN z.count(N[0])),
m map(lambda d:
> slice_head(
o order_by(lambda Z:
_/zZ -1*z.count(Z),
Sz sorted(z)),
d d),
Uz range(len(z))
Step by step:
First, we sorted the characters by their commonness, ties broken alphabetically. This is o_/zZSz. o is the same as Python's sorted(<stuff>,key=<stuff>), with a lambda expression for the key, except it keeps it as a string.
Then we generate a list of the prefixes of that string, from length len(z) to length 1. > is equivalent to python's <stuff>[<int>:].
Then, we reorder this list of prefix strings by the fractional location, 0 being the left edge and 1 being the right, of the first character of the prefix on the rectangular layout seen in the question. /NhN counts how many times the first character in the prefix occurs in the prefix, while /zhN gives the number of occurrences of the first character in the prefix in the string as a hole. This assigns each prefix being led by each character in a group a different fraction, from 1/k for the right most occurrence of that character to k/k for the left most. Reordering the prefix list by this number gives the appropriate position in the layout. Ties are broken using the prior ordering, which was first by count then alphabetical, as desired.
Finally, we need to extract the first character from each prefix string, combine them into a single string, and print them out. Extracting the first characters is hC. C performs a matrix transpose on the list, actually zip(*x) in Python 3. h extracts the first row of the resultant matrix. This is actually the only row, because the presence of the 1 character prefix prevents any other complete rows from being formed. s sums the characters in this tuple into a single string. Printing is implicit.
Test:
$ pyth -c 'shCoc/NhN/zhNm>o_/zZSzdUz' <<< 'oroybgrbbyrorypoprr'
rorbyroprbyorrobypg
Incremental program pieces on oroybgrbbyrorypoprr:
Sub-Piece Output
Sz bbbgoooopprrrrrryyy
o_/zNSz rrrrrroooobbbyyyppg (uses N because o uses N on first use.)
m>o_/zNSzdUz ['rrrrrroooobbbyyyppg', 'rrrrroooobbbyyyppg', 'rrrroooobbbyyyppg', 'rrroooobbbyyyppg', 'rroooobbbyyyppg', 'roooobbbyyyppg', 'oooobbbyyyppg', 'ooobbbyyyppg', 'oobbbyyyppg', 'obbbyyyppg', 'bbbyyyppg', 'bbyyyppg', 'byyyppg', 'yyyppg', 'yyppg', 'yppg', 'ppg', 'pg', 'g']
oc/NhN/zhNm>o_/zZSzdUz ['roooobbbyyyppg', 'obbbyyyppg', 'rroooobbbyyyppg', 'byyyppg', 'yppg', 'rrroooobbbyyyppg', 'oobbbyyyppg', 'pg', 'rrrroooobbbyyyppg', 'bbyyyppg', 'yyppg', 'ooobbbyyyppg', 'rrrrroooobbbyyyppg', 'rrrrrroooobbbyyyppg', 'oooobbbyyyppg', 'bbbyyyppg', 'yyyppg', 'ppg', 'g']
Coc/NhN/zhNm>o_/zZSzdUz [('r', 'o', 'r', 'b', 'y', 'r', 'o', 'p', 'r', 'b', 'y', 'o', 'r', 'r', 'o', 'b', 'y', 'p', 'g')]
shCoc/NhN/zhNm>o_/zZSzdUz rorbyroprbyorrobypg
Old answer:
ssCm*+t*u*G/zHS{-zd1]kd/zdo_/zNS{z
This program works by calculating how many times to replicate a certain sublist. The sub-list looks like ['', '', '', '', ... , 'r']. The total length of this sub-list is the product of the number of occurrences of all of the other candies, which is u*G/zHS{-zd1. The full sublist is constructed by replicating the list of the empty string ,]k, that many times, then removing and element with t and add the candy name to the end with +d.
Then, this sub-list is replicated as many times as that candy is found in the input, /zd, ensuring each candy's list is of equal length.
Now, with this function mapped over all of the unique candies in proper sorted order (o_/zNS{z), we have a rectangle similar to the one in the question statement, but with empty strings instead of periods. Doing a matrix transpose (C) followed by two summations (ss) gives the final string.
Verification:
$ pyth programs/candy.pyth <<< 'oroybgrbbyrorypoprr'
rorbyroprbyorrobypg
VhQIq`N_`NN
Example:
$ pyth -c 'VhQIq`N_`NN' <<< 200
0
1
2
3
4
5
6
7
8
9
11
22
33
44
55
66
77
88
99
101
111
121
131
141
151
161
171
181
191
\\,,"$: Ndw
",input(),"
:\\w$ ",d,N
That's some mean bug abuse right there. This compiles to:
Pprint("\n",at_slice("\",input(), ",d,N))
The relevant bug is that \\ compiles to "\" instead of "\\", which lets you compile Pyth into a string.
C-3P0: "Sir, the possibility,..."*
Han Solo: "Never Tell Me The Odds!"
3720
*Originally, George Lucas had Han interrupt C3-PO.**
**He called this his greatest idea since Jar-Jar.
ts,*s,y30 l" : : i i Han Solo "eP-C"h"TsrhT
The remaining characters go on the next line. Pyth only interprets the first line of a file.
ts,make a 2-tuple and get their sum -1.*multiply:s,y30 l"..."sum the 2-tuple containing 2*30 and the length of the string (18).eP-C"h"Tget the largest prime factor of h's ascii value minus 10 (47).srhTget the sum of numbers from 0-10.
All in all, this basically just computes: (30*2+18)*(47)+55-1. After reading @isaacg's answer I noticed there is an extremely simple solution:*h30tC"y"which is 31*120.
Sorry for poor explanation formatting, I don't know how to use spoiler blocks :S (@Sp3000 made it a bit nicer for you, though)
Now you can run Pyth online! Try it here. Thanks @isaacg :)
*tC"y"l"Han Solo: Never Tell Me The Odd
-3P0: Sir, the possibii,... s!"
There have to be a ridiculous number of possiblities here, but this seemed to be the easiest - get 120 from chr('y')-1, and 31 as the length of a string, and multiply. Newline is a super-comment.
In the spirit of @MartinBüttner:
"Programming Puzzles and Code Golf"
4.459431618637297
llo oCGd"ProgrammingPuzzesandef"
Simply lg(len("Length 22 string")), extra characters disposed of at the front.
Note that this is new software, so it may be buggy. Please report any problems to me.
=Z/lzQ=ks^lz.5Jm]dUzL[-bk+bk?tb%bkb?hb%hbkb)FNJIgNZB~Jm+NksmybN;|jbS{msm+@zk@S*Z<GQxsdkUzfqSsTUz^fqsmv@*ZzbY/smvdzQJQ"None
Changes:
130 -> 120: Switched to newline separated input.
120 -> 134: Fixed a bug involving groups not of size equal to the side length of the matrix.
134 -> 120: Prints all solutions, including ones equivalent under group renaming.
120 -> 122: Fixed a bug where only paths would be generated, instead of all legal groups.
Test run:
pyth programs/sum_group.pyth <<< '156790809
3'
1a5a6b7c9a0b8c0c9b
1a5a6c7b9a0c8b0b9c
1b5b6a7c9b0a8c0c9a
1b5b6c7a9b0c8a0a9c
1c5c6a7b9c0a8b0b9a
1c5c6b7a9c0b8a0a9b
pyth programs/sum_group.pyth <<< '156790808
3'
None
pyth programs/sum_group.pyth <<< '1111
2'
1a1a1b1b
1a1b1a1b
1b1a1b1a
1b1b1a1a
Explanation:
Pyth code (Pseudo)-Python code Comments
(implicit) z = input() z is the digit string
(implicit) Q = eval(input()) S is the number of groups
(implicit) G = 'abcdefghijklmnopqrstuvwxyz'
=Z/lzQ Z = len(z)/Q Z is the size of each group.
=ks^lz.5 k = int(len(z) ** .5) k is the side length of the matrix.
Jm]dUz J = map(lambda d:[d], range(len(z))) Locations are encoded as numbers.
L def y(b): return y will be the transition function.
[-bQ [b-k, Move up - the row above is k less.
+bQ b+k, Move down - the row below is k more.
?tb%bkb b-1 if b%k else b Move left, unless at the left edge.
?hb%hbkb) b+1 if (b+1)%k else b] Move right, unless at right edge.
FNJ for N in J: This constructs the list of all
IgNZB if N[Z-1]: break Z-length connected groups.
~Jm+Nk J+=map(lambda k: N+[k], Append to J the group of N +
smybN sum(map(lambda b: anything reachable from
y(b),N))) anywhere in N.
; (end for)
| or Print first truthy thing between
S{ sorted(set( Unique elements in sorted order of
ms map(lambda b:sum( Map+sum over allowable combinations
m+@zd map(lambda d:z[d]+ Character in original digit string
@S*Z<GQ sorted(G[:Q]*Z)[ Repeated and sorted early alphabet
xsbd sum(b).index(d)], At index of number in sum of groups
Uz range(len(z))) Over possible indexes.
f filter(lambda T: To generate allowable combinations,
we will filter all groups of Q paths.
qSsTUz sorted(sum(T)) == range(len(z)) Ensure all locations are visited.
^ Combinations of
f filter(lambda Y: Filter over connected Z-length groups
qsm equal(sum(map(lambda k: Sum of the values of the group
v@*ZzkY eval((z*Z)[k]),Y) In the original digit string
/smvbzQ sum(map(lambda b:eval(b),z))/Q must equal the sum of all values in z
divided by the number of groups.
J J Filter over connected Z-length groups
Q Q Combinations of length Q
"None "None" If the above was empty, print "None"
This is a direct translation of my CJam answer in Pyth
oc/|$Y.append(N)$YN/zNo_/zZSz
There is a rather long story behind this solution and @isaacg helped me a lot in understanding this new language.
Ideally this is the exact word to word translation of my CJam code (17 bytes):
oc/~kNN/zNo_/zZSz
which means:
o order_by(lambda N:
c div(
/ count(
~kN k+=N, #Update k (initially ""), add N
N N), #Count N in updated k
/zN count(z, N)),
o order_by(lambda Z:
_ neg(
/zZ count(z, Z)),
Sz sorted(z)))
But sadly Python does not return anything in a += call, so that was not a valid Python code, thus an invalid Pyth code too as in Pyth, a lambda can only be a return statement.
Then I looked into various methods and finally found that Python's list.append returns a None value, which I can use. Making the code to be (19 bytes):
oc/|aYNYN/zNo_/zZSz
which means:
o order_by(lambda N:
c div(
/ count(
|aYN (Y.append(N) or
Y Y) #Update Y (initially []), append N
N N), #Count N in updated Y
/zN count(z, N)),
o order_by(lambda Z:
_ neg(
/zZ count(z, Z)),
Sz sorted(z)))
But sadly, support of a (append) was removed from Pyth and the version which do has the support, does not have the support for o.
Update : a support has been added back in Pyth now so the above 19 byte code will work in the online compiler. But since this is a new feature which was added after the OP, I am not putting it up as my score and letting the 29 byte code as my solution.
Therefore I had to rely on raw Python in that case, making the code to be
o order_by(lambda N:
c div(
/ count(
|$Y.append(N)$ (Y.append(N) or
Y Y) #Update Y (initially []), append N
N N), #Count N in updated Y
/zN count(z, N)),
o order_by(lambda Z:
_ neg(
/zZ count(z, Z)),
Sz sorted(z)))
This answer could almost certainly be golfed further; I particularly don't like the distance calculation.
K^lJ.5VJFdUN~Z*i@JN@Jd+^-/dK/NK2^-%dK%NK2;Z
To set this up, store the linear-ized array in the variable J. You can do this by writing:
J[3 2 9 4 1 8 5 6 7)
Outputs a float. I think this is legitimate, please tell me if I've broken a rule :)
Explanation:
: Z=0 (implicit)
K^lJ.5 : K=sqrt(len(J))
VJ : for N in range(len(J))
FdUN : for d in range(N)
~Z* : Z+= the product of
i@JN@Jd : GCD(J[N],J[d])
+^-/dK/NK2^-%dK%NK2 : (d/K-N/K)^2 + (d%K-N%K)^2 (distance)
;Z : end all loops, and print Z
D(GHYZ)R?+G(tHGtZt-GY)ZhY
This defines a function, (. Example usage:
D(GHYZ)R?+G(tHGtZt-GY)ZhY(5 5 1 3
prints 23.
This is algorithmically identical to the Mathematica answer by Martin Büttner, though it was developed independently. As far as I can tell, that's the only good way to do it.
Note that Pyth cannot handle the full input range on my machine, it will overflow the stack and die with a segfault on large inputs.
No optimizations whatsoever, so far. Just using some trivial observations about fragile primes (thanks to Rainbolt in chat):
Just trying to get the ball rolling :)
This technically runs slightly over 15 minutes, but it only checks a single number in the extra time.
is_prime is taken from here (isaacg used it here) and is probabilistic.
def substrings(a):
l=len(a)
out=set()
for i in range(l):
for j in range(l-i):
out.add(a[:i]+a[len(a)-j:])
return out
import time
n=9
while time.clock()<15*60:
if is_prime(n):
if not any(map(lambda n: n!='' and is_prime(int(n)), substrings(`n`))):
print n
t=`n`
if n%10==9 and t[0]=='8':n+=2
elif n%10==1 and t[0]!='8':n+=8
elif t[0]=='1' or is_prime(int(t[0])):n+=10**~-len(t)
else:n+=10
Just a note, when I start this with n=429623069 I get up to 482704669. The extra digit really seems to kill this strategy...
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999799999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
'9' * 1944 + '7' + '9' * 323
There are at about len(n)^2 resulting numbers of Remove(n, startIndex, count). I tried to minimize those numbers. If there are lots of digits next to each other are the same, lots of these resulting numbers can be ignored, because they appear multiple times.
So I took it to the extreme, only 9s and a little prime in the middle. I also took a look at the fragile prime under 1 million, and saw, that there are such fragile prime. Searching for numbers with 2 9s at the end works really good, not sure why. 1 number, 3, or 4 9s at the end results in smaller fragile primes.
It uses the pyprimes module. I'm not sure, if it is any good. It uses the miller_rabin test, so it's probabilistic.
The program find this 126-digit fragile prime in about 1 minute, and for the rest of the time it searches without success.
biggest_found = 80651
n = lambda a,b,c: '9'*a + b + '9'*c
for j in range(1000):
for digit in '124578':
for i in range(2000):
number = int(n(i,digit,j))
if is_prime(number):
if (number > biggest_found):
if all(not is_prime(int(n(i,digit,k))) for k in range(j)):
biggest_found = number
print(i+j+1, biggest_found)
break
Just saw, that you removed the time limit. I will run the program over night, maybe some really big fragile primes appear.
Made my original program faster, so but still no solution with more than 126 digits. So I jumped on the train and searched for x 9s + 1 digit + y 9s. The advantage is, that you have to check O(n) numbers for primality, if you fixe y. It finds a 1221 rather quickly.
For the 2268 digit number I use the same program, only divided the work on multiple cores.
#G
(or # followed by any normal variable, actually).
# is while True. Variables are printed implicitly, and since G is 'abcdefghijklmnopqrstuvwxyz', that gets printed infinitely.
lambda n:'1i--'[n%4::-2]
Most credit belongs to @user2357112, I just golfed his answer from the comments on this answer a bit more.
Explanation: Starts at the index n%4 in the string '1i--'. Then iterates backwards in steps of two over each letter in the string. So, for example, n=6 would start at index 2, the first -, then skip the i and take the 1, to return -1.
@xnor pointed out a same-length solution:
lambda n:'--i1'[~n%4::2]
I can only seem to get 14, no matter how I try to reverse/slice/etc. :'(
%_2<"1i--"h%Q4
Which is essentially the same as the above python answer, but in 2 steps, because pyth doesn't support the full indexing options of python. Try it online.
I'm going to go have a talk with isaacg about Pyth indexing ;)
L?+y/hb3@"0+-"%b3bk|yQ0
This is a recursive solution, based on @xnor's 40 character recursive function. y constructs the baanced ternary of the input, by finding the last digit using the mod 3 index, and then uses the fact that the rest of the digits are equal to the balanced ternary for (n+1)/3, using floored division. Then, it calls the function, returning the result, or 0 if the input is 0.
Edit: Fixed an error with mini array size 1 or very large offset.
D:GHYKm0GFNG~@K%/HYlGN~H1)RfTK
Defines a function : that takes small_array, index_where_small_array_begins and divisor as arguments. You can call it like:
:[1 2 3) 5 3
Returns: [1, 5]
Explanation:
D:GHY : Define :
Km0G : Make K an array of len(G) zeroes
FNG ) : for N in small_array
~@K%/HYlGN : Add N to K[floor_div(H,Y)%len(G)]
~H1 : Increment H
RfTK : Return K without any zeroes
!f|!vT%vzvTz
This filters the characters in the string for being either zero (!vT) or not dividing the input (%vzvT), then takes the logical not of the resulting list.
!f%Q|vT.3`Q
This combines @isaacg's and @xnor's answers. It filters out digits from the input by checking the value of input % (eval(current_digit) or .3). Then it checks if the resulting string is empty or not.
Came across another couple same-length variants:
!f%Q|T.3jQT
!f|!T%QTjQT
DgGHKf<^-Hsm^d.5T2^10_12^r1hh*HHGR?jbmjdkKK"No
Shamelessly borrows from xnor's comment ;)
This will run out of memory on any sane computer even for a value like 5,5.0. Defines a function, g, that can be called like g 3 7.923668178593959.
This python 3 program uses essentially the same algorithm (just doesn't do the "No" printing at the end, which could be done by assigning a variable to all the results, then writing print(K if K else "No")), but uses a generator, so it doesn't get a memory error (it will still take extremely long, but I've made it print as it finds the values):
This gave the exact same results that @Sp3000 got. Also, this took several days to finish (I didn't time it, but around 72 hours).
from itertools import*
def g(G,H):
for x in product(range(1,int(H*H+2)),repeat=G):
if (H-sum(map(lambda n:n**.5,x)))**2<1e-12:print(*x)
K1.618Jm,s*dKs*d*KKU39M<smf|}TJ}_TJm,-Ghb-Hebt^,0hk2U99 1
Pretty similar to other answers, but that wikipedia page didn't give much else to go on ;) The magic number 39 is the number of cold positions with values < 99.
Defines a function g that you can call like g 30 25. Returns [] for failure, [(13,8)] on success.
Explanation
K1.618 : K=phi (close enough for first 39 values)
Jm,s*dKs*d*KKU39 : J=cold positions with the form (small,big)
M<s 1: Define g(G,H) to return this slice: [:1] of the list below
mf|}TJ}_TJ : map(filter: T or reversed(T) in J, where T is each member of..
m,-Ghb-Hebt^,0hk2 : [(G H) - (0 x+1),(x+1 0) and (x+1 x+1)]
U99 : for each x from 0 - 98
lambda l:reduce(lambda G,H:[H,G][(G>H)^(G>0)]*(G*H>0),l,l[0])
This is based off of my pyth answer, which was inspired by Mig's answer.
Old answer:
l=input()
m=l[0]
k=1-2*(m<0)
for i in l:m=[m,i][m>i*k]
print(k*m>0)*m
This is a very long answer. I feel like having 2 variables is a waste...? I was right...? ish? ;p
uhtS[0GH)QhQ
Probably not novel, but original :P
Pre-sorting allowed
u*?Gx>GH>G0H>*GHZQhQ
The idea to use reduce and ternary statements was shamelessly stolen from Mig's answer, but I have no idea if these algorithms are otherwise even similar, as I can't read ternary statements.
Explanation:
Q=eval(input) : implicit
u QhQ : print reduce(lambda G,H: ..., Q, Q[0])
* >*GHZ : ... * (G*H>0)
?G H : G if ... else H
x>GH>G0 : G>H xor G>0
J'f&qlTQ&}_TJ>_TTJ
This is a fairly straightforward solution.
J stores the list of words. Then we filter over the list of words (f J) on the length of the word being the input (qlTQ), the reversed word being in the list (}_TJ), and the reversal of the word being greater than the word (>_TT). The last condition ensures T is not palindromic, and that only one of the pair is printed. The resultant list is printed.
The way Pyth works, the only way to open a file is to receive its name on STDIN. This is why I have counted 5 of the STDIN bytes, w.txt, in my score.
Example run:
$ pyth -c "J'f&qlTQ&}_TJ>_TTJ" <<< '6
w.txt'
['animal', 'denier', 'diaper', 'drawer', 'pupils', 'recaps', 'redraw', 'sleets', 'snoops', 'sports']
ef&}TzqmaCd6T_mx4aCk6Tyz
Combining the tips from FryAmTheEggman and the reverse palindrome check trick from Peter, this is a super short version.
However, this only works with Pyth 3.0.1 which you can download from this link and run like
python3 pyth.py -c "ef&}TzqmaCd6T_mx4aCk6Tyz" <<< "ATTCGATCTATGTAAAGAGG"
(linux bash only. On windows, press Enter instead of the <<< and then type the input)
This is my previous submission - 28 bytes solution
J"ACGT"ef&}TzqTjk_m@_JxJdTyz
Thanks to FryAmTheEggman for this version. This one creates all possible subsets of the input DNA string, filters the subsets on the condition that the subset is a substring of input and the reverse of transform is equal to the subset itself.
Due to all possible subset creation, this takes up even more memory than Peter's answer.
This is my first submission - 36 byte solution.
J"ACGT"eolNfqTjk_m@_JxJdTm:zhkek^Uz2
This is the exact translation of my CJam answer. I was hoping that this would be much smaller but turns out that lack of translation method made it almost similar size (still 2 bytes smaller though)
Try it here.
Counter:
L@,cb)sm!cd)b1 0
Splitter:
L@,cb)sm!cd)b10
These each define a function, y, which takes a string input to solve the desired task.
Thanks to @FryAmTheEggman for the idea of using Pyth's feature of modular indexing into lists to shave a character.
Test cases:
L@,cb)sm!cd)b1 0y++"abc def"b"gh ij k"
L@,cb)sm!cd)b10y++"abc def"b"gh ij k"
Explanation:
L define a function, y, which takes one input, b.
@ Index into
, 2-tuple of
cb) b.split() (solution to splitter)
s sum over (solution to counter)
m map, with input d, to
!cd) logical negation of d.split() (empty list is falsy)
b over b.
Index is either:
10
1
Indexing is modulo the length of the list in Pyth.
0 In one case, a 0 with a leading space is outside the function.
Leading space suppresses print, so the 0 is invisible.
J2010fq+J4/*T+TJ^iTJ2U^T6
This uses your algorithm fairly naively... I might be able to come up with something better...
Basically filters out values that don't meet the criterion from range(10**6)
Thanks to @xnor for pointing out in chat that gcd(x,x+2010)==gcd(x,2010)
K"smh"J"\D\D+|\d+:(?=\d:)|:\d\D"W:QJ1=Q:QJd;FN_msdCfn2lTm+*]0</k\:2msbck\:cQ)~k+d+hK_`%+NZ60=Z/N60=KtK;_k
This requires input from STDIN in the same way that the Javascript answer does, as quoted text with newlines as \ns.
Sample:
"View the Welcome video.\nVideo: 10:37 min.\nView the video introduction to the course.\nVideo: 3:30 min. View the video of how to use the Lesson Overview.\nVideo: 9:13 min.\nView the video overview of how to use the Epsilen system to share your work.\nVideo: 03:15 min.\nView the video to learn about the State of Texas Assessment of Academic Readiness (STAAR).\nVideo: 1:05:26 min."
Output
1h 32m 1s
Example working with weirder dates:
"10:10:5 and 5:1:10 and 27 or 16: or 1:1:1 or 11:1\n"
Output
0h 11m 20s
(Only the 10:10 and the 1:10 are legitimate times)
The main reason that this is so long is that Pyth won't let you extract positive matches. This instead matches everything that isn't a valid time, and replaces it with a space character. Then, splitting on whitespace leaves only times and some wayward numbers. The excess numbers are removed by checking for : characters, which will have been removed from non-valid times. This could almost certainly be golfed further ;)
Jhxzd!f-@zT+" X"`sm/:+*JNztd+d2\Xm+T*kJU3Uz
Try it here.
Explanation:
Jhxzd: This is the location of the first space in the input + 1. (z in the input, d is space.) It is the separation in the input between vertically adjacent cells on the board.!f: This is the logical not (!) of a filter (f), which will be True if and only if the expression is falsy for every element of the sequence.-@zT: Take the character at location T (the lambda variable) from the input, and remove any appearances of: (This will be truthy if the character is not removed, and falsy if it is.+" X": Remove space, X, and`: Repr ofsm: sum of map to/ \X: count of "X" in:+*JNz: The slice of the input prefixed by J dummy characterstd+d2: From d-1 to d+2.m+T*kJU3: For d in [T, T+J, T+2*J].Uz For T in range(len(input)).^v"\107"8
v"\107" evals a string containing G, octal escaped, which is the pyth variable for the alphabet.
^G8, is the result, which prints all 8 letter strings in the lowercase alphabet, including codegolf. Runs out of memory on my machine, unfortunately.
#|zePG
I've been trying for ages to get one that I'm satisified with. Basically converts to:
# = while True
(implied print)
| = or
z = (automatically initialized from stdin)
ePG = second-to-last lowercase letter = 'y'
L-/bd/rb6dJcz\|KS{mydJFNJ+*d@_KxKyN>NyN
Uses the | delimiter option.
eo/QNQ
Expects input on stdin like [4,3,1,0,6,1,6,4,4,0,3,1,7,7,3,4,1,1,2,8]. Ties are resolved by last occurrence because Python performs stable sorts.
Sorts the list by count the value in the list, then prints the last number of the list.
Q could be replaced with d if you initialized d to contain the value before e.g. =d[4 3 1 0 6 4 4 0 1 7 7 3 4 1 1 2 8)
Python-esque pseudo-code:
Q=eval(input());print(sorted(Q,key=Q.count)[-1])
Full Explanation:
: Q=eval(input()) (implicit)
e : ... [-1]
o Q : orderby(lambda N: ...,Q)
/QN : count(Q,N)
Pyth's orderby runs exactly like Python's sorted with orderby's first argument being the key argument.
smr-QdhQUQ
Expects input on stdin. Independently discovered algorithm. Thanks @Sp3000 for helping me stick the last Q in there :P Also, irony? XD
Explanation:
Q=eval(input()) : implicit
s : The sum of...
m UQ : map(...,range(Q))
r-QdhQ : range(Q-d,Q+1)
smrhQhdUQ
With help from @FryAmTheEggman
s reduce + on list
m map
rhQhd lambda d: reversed(range(d+1, Q+1)), over
UQ range(Q)
where Q is the input.
V501?N&%N3-\3`N"bzzt
Explanation:
V501 for N in range(501):
?N print(N if
&%N3 N % 3 and
-\3`N "3" - repr(N)
"bzzt else "bzzt")
Try it here.
def f(x):
for i in 4,3,2,1:print" "*(4-i)+" ".join(".O"[i*~-i/2-~z in map(int,x.split())]for z in range(i))
Call with f("3 5 7 9 10").
i is the row number, with 4 being the first row and 1 being the last. z is the nth pin on that row, with 0 meaning it's the first pin in the row and i-1 meaning it's the last pin in the row.
The main hack is i*~-i/2-~z, which converts (i, z) -> pin number. For example, (4, 0) -> 7 as pin 7 is the first pin on row 4 (the first row). The derivation goes like this:
We want a function taking i to the first pin on row i, i.e. 4 -> 7, 3 -> 4, 2 -> 2, 1 -> 1. This is satisfied by (i**2-i)/2 + 1, and thus (i**2-i)/2 + 1 + z gives the correct pin number for input (i, z)
Then simplify:
(i**2-i)/2 + 1 + z
= (i*(i-1))/2 + 1 + z
= i*~-i/2 + 1 + z
= i*~-i/2-~z
V4~Z-4N+*dNjdm@".O"}+d-11Zrz7U-4N
The program roughly translates to:
z = input()
Z = 0
for N in range(4):
Z += 4-N
print(" "*N + " ".join(".O"[d+11-Z in map(int, z.split())] for d in range(4-N)))
(Thanks to isaacg for tips)
V4+*dNjdm?\O}+7+dZrz7\.rN4~Z-N4
Try it here.
V4 sets up a for loop, with N as the variable over [0,1,2,3].
*dN provides the initial spaces, because d is space.
To find the pin locations, it uses +7+dZ - 7 + d + Z.
d is:
0 1 2 3
1 2 3
2 3
3
while Z is 0 in the first line, -4 in the second, -7 in the third and -9 in the forth. This is becasue Z starts as 0, and ~Z-N4 decrements Z by 4, then 3, then 2.
Then, it checks if the pin location is in the input, using }+7+dZrz7. rz7 is the desired pins in list-of-int form.
Then, it creates an O if it was present, and . otherwise. This is space separated, with jd, and printed implicitly.
tf<l-QUTT1
Input in a form such as [22,33,1,2,4] on STDIN.
How it works:
-QUT is all of the numbers in the input (Q) at least as large as the number being checked, T.
<l-QUTT is true if the the length of that list is less than T.
f<l-QUTT1 finds the first integer which returns true for the inner check, starting at 1 and going up.
tf<l-QUTT1 decrements that by one, giving the largest value for which the condition is false, which is the h-index.
Starting at 1 ensures that 0 is returned when the test is always true, such as in the first test case.
This is my first time experimenting with Pyth. It's the same solution as in my Python solution.
VQIq/<QN@QN1~Y]:QZN=ZhN;+Y]>QZ
You can try it online: Pyth Compiler/Executor
E.g. The input
[2,1,1,2,3,2,2,4,5,6,7,3,7,0,5]
will print
[[2, 1], [], [3, 2, 2, 4, 5, 6, 7], [], [0], []]
# Q = input(), Y = [], Z = 0
VQ # for loop: N iterates over the indices of Q
I # if
q\<QN@QN1 # Q[N] appears exactly once in Q[:N]
~Y]:QZN # append the list [Q[Z:N]] to Y
=ZhN # and assign Z = N + 1
; # end if and for loop
+Y]>QZ # print Y + [Q[Z:]]
Just exercising my Pyth skills, not a serious contender.
L?bqb_by`+vbi_bTyz
Equivalent to Python 3:
y=lambda b:b if b==b[::-1] else y(str(eval(b)+int(b[::-1],10)))
print y(input())
This is surprisingly long. This can be golfed a lot, taking in tips from the Pyth translation.
q~a*{m*:s}*{:H\:G_+\#)GGHH,,{_H<G,@-G>=},W=>+?}*
The input goes like
3 "ABC"
i.e. - String of list of characters and the length.
and output is the De Bruijn string
AAABAACABBABCACBACCBBBCBCCC
This is the direct conversion of the algorithm used in my CJam answer. Tips for golfing welcome!
Mu?G}H+GG+G>Hefq<HT>G-lGTUH^GHk
This code defines a function g which takes two arguments, the string of list of characters and the number.
Example usage:
Mu?G}H+GG+G>Hefq<HT>G-lGTUH^GHkg"ABC"3
Output:
AAABAACABBABCACBACCBBBCBCCC
Code expansion:
M # def g(G,H):
u # return reduce(lambda G, H:
?G # (G if
}H # (H in
+GG # add(G,G)) else
+G # add(G,
>H # slice_end(H,
e # last_element(
f # Pfilter(lambda T:
q # equal(
<HT # slice_start(H,T),
>G # slice_end(G,
-lGT # minus(Plen(G),T))),
UH # urange(H)))))),
^GH # cartesian_product(G,H),
k # "")
WOyG~ZtOT)Z
Note: this program will probably crash with a memory error on any real computer. To test it, try replacing G with a shorter string, such as in this code, which generates numbers averaging around 28000:
pyth -c 'WOy"abcdefghijklm"~ZtOUT)Z'
This code loops, adding a random number from -1 to 8 to Z, with a 2^-26 probability of exiting the loop on each repetition. The 2^-26 probability is attained by selecting a random element (O) of the set of all subsets (y) of the alphabet (G).
Technical details & justification:
The probability 2^-26 is derived from two facts: y, when called on sequences, is the power-set function, an constructs the list of all subsets of the input. Since the input, G, is 26 characters long, this power-set, yG has 2^26 entries. OyG selects a random element from those 2^26 entries. Exactly one of those entries, the empty string, will evaluate as falsy when passed to W, the while loop. Therefore, there is a 2^-26 probability of exiting the loop each time.
In any fixed number of loop cycles K, the probability of getting the number K*3.5 + m and getting K*3.5 - m are equal, because each sequences of addends that achieves one total can be inverted, -1 -> 8, 0 -> 7, etc., to achieve the other. Additionally, numbers closer to K*3.5 are clearly more likely than numbers farther away. Thus, if K > 2000000/3.5 = 571428.5 the probability of getting a number over 1000000 is greater than 75%, because some of the results above that number can be put into a one-to-one correspondence with all of the results below that number, and the upper less-than-half, can be put into a one-to-one correspondence with those under 1000000. The probability of getting at least 571429 loops is (1-2^-26)^571429, which is no less than (1-2^-26 * 571429), the expected number of times leaving the loop over the first 571429 tries, which is 99.1%. Thus, on 99.1% or more of trials, there is a 75% or more chance of getting at least 1000000, so there is more than a 50% chance of getting over 1000000.
This code relies on a behavior of O where a bug was accidentally introduced 3 days ago and was fixed today. It should work on any version of Pyth 3 from before Dec 22nd, or after today. The following code is equivalent, and has always worked:
WOyG~ZtOUT)Z
0{)8.?rand}do.2&(*4/
Yeah, this one is also kind of slow.
Compared to languages like CJam and Pyth, GolfScript suffers from a verbose random number generation keyword (rand). To overcome this handicap, I needed to find a way to use it only once.
This code works by repeatedly picking a random number between 0 and 88−1 = 16,777,215 inclusive, and incrementing a counter until the random number happens to be 0. The resulting counter value has a geometric distribution with a median approximately -1 / log2(1 − 1/88) ≈ 11,629,080, so it meets the "over 1,000,000 at least 50% of the time" test.
Alas, the random number thus generated is always strictly positive. Thus, the extra .2&(*4/ part is needed to let it become negative or zero. It works by extracting the second-lowest bit of the number (which is thus either 0 or 2), decrementing it to make it -1 or 1, multiplying it with the original number, and dividing the result by 4 (to get rid of the lowest two bits, which are now correlated with the sign, and also to allow the result to become zero). Even after the division by 4, the absolute value of the random number still has a median of -1 / log2(1 − 1/88) / 4 ≈ 2,907,270, so it still passes the 50% test.
L?!b<b1sm&d*^_1tdy-b/*dt*3d2r_bhbJo^-QyN2U99<J-2qQyhJ
Explanation and more golfing to follow.
def T(m):o=[];exec'm=zip(*m)[::-1]\nfor r in m[::-1]:\n n=k=0\n for x in r:k+=x>n;n=max(x,n)\n o+=[k]\n'*4;return o
There's an awful lot of list flipping going on in there.
Takes input as a nested list (e.g. call with T([[4,3,5,2,1],[5,4,1,3,2],[1,5,2,4,3],[2,1,3,5,4],[3,2,4,1,5]])). Output is a single flat list.
Ungolfed:
def T(m):
o=[]
for _ in [0]*4:
m=zip(*m)[::-1]
for r in m[::-1]:
n=k=0
for x in r:k+=x>n;n=max(x,n)
o+=[k]
return o
Alternative 115:
def T(m):o=[];exec'm=zip(*m)[::-1];o+=[len(set([max(r[:i+1])for i in range(len(r))]))for r in m[::-1]];'*4;return o
I have no idea why this works with a list comprehension, but chucks a NameError with a set comprehension...
A bit too long, but if anyone's interested — yes, it's possible to get this down to a lambda!
T=lambda m:[len({max(r[:i+1])for i in range(len(r))})for k in[1,2,3,4]for r in eval("zip(*"*k+"m"+")[::-1]"*k)[::-1]]
V4=Q_CQ~Yml{meS<dhkUd_Q)Y
Obligatory Pyth port.
Input the list via STDIN, e.g. [[4, 3, 5, 2, 1], [5, 4, 1, 3, 2], [1, 5, 2, 4, 3], [2, 1, 3, 5, 4], [3, 2, 4, 1, 5]].
Try it online... is what I would say but unfortunately, for security reasons, the online interpreter disallows the use of eval on nested brackets. Try the workaround code JcQ5V4=J_CJ~Yml{meS<dhkUd_J)Y instead, and input as a flattened list like [4, 3, 5, 2, 1, 5, 4, 1, 3, 2, 1, 5, 2, 4, 3, 2, 1, 3, 5, 4, 3, 2, 4, 1, 5].
(Thanks to @isaacg who helped golf out a few bytes)
sm*hd+@QtdhSQUQ
Input should be given comma separated on STDIN, e.g.
3,5,4,3
This uses the same trick that many other solutions have used, of adding the minimum to each element to account for the bonus. The minimum is hSQ in the above code. To account for multiplying by 2, 3, 4, and 1, I map d over the list [0,1,2,3], and multiply the (d-l)th element of the input by d+1. Thus, the -1th element is multiplied by 1, the zeroth by 2, the first by 3 and the second by 4. Then I sum.
f@eo+/QN/Qm!dN_osZ^U2lhQTUhQ
Takes input in the form of a nested list, e.g.
[[0,0,1,0,0],[0,0,1,0,0],[0,0,1,1,0],[0,0,0,1,1],[0,0,0,1,1]]
Gives output 0-indexed, e.g.
[2]
^U2lhQ: Generates all possible lists of 0s and 1s of the right length.
_osZ: Orders these lists from most 1s to least.
+/QN/Qm!dN: Counts how many times each list (N) and its inverse, 0s and 1s swapped (m!dN) occur in the input. The former corresponds to a series of flips leaving all zeros, the latter to leaving all ones.
eo: Orders the list by the above key, and takes its last element, which will be the result with the most matching columns, and among them the one with the least ones.
f@ ... TUhQ: Converts this list of 1s and 0s to a list of indices to be flipped.
For 1-indexing, change the d to a k, then put mhd at the beginning.
#Jm+3O3U18IqsJ72JB
# infinite loop
U18 generate the list [0, 1, ..., 17]
m U18 map every value of this list to
+3O3 a random number between 3 and 5
Jm+3O3U18 and assign the resulting list to J
I if
qsJ72 the sum of J == 72
J print J
B and exit the loop
~3,{1$>~;}%+$(11*+{+}*
Reads input from stdin, in the format [3 5 4 3]. Writes output to stdout. (If taking the input as an array on the stack is allowed, the leading ~ may be omitted for a total of 21 bytes.)
This uses a somewhat different strategy than the CJam / Pyth / etc. solutions: I first build an array with 2 copies of the first input value, 3 of the second, 4 of the third and one of the fourth. Then I sort this array, pull out the smallest element, multiply it by 11 and sum it with the other elements.
JYFHQI!H~Y]]lY)IqH1=Y+m+dlYY]UhlY)VYI&Hq%l@YNH1~J]N))=Ymf!}TJ@YkUlYY;-lYl{J
I'm done. Maybe someone else has some golfing tips.
Y is the adjacency list of the graph. For golfing reasons, I also keep a node in this list, even after the node got deleted (Otherwise I would have to update all indices). Each node has itself as neighbor. The list J keeps track of the deleted nodes.
I show the changes of the adjacency list on the example input [0,1,0,1,0,1,3]:
input 0: Y=[[0]] J=[] input 1: Y=[[0,1],[0,1]] 0 J=[] input 0: Y=[[0,1],[0,1],[2]] J=[] input 1: Y=[[0,1,3],[0,1,3],[2,3],[0,1,2,3]] J=[] input 0: Y=[[0,1,3],[0,1,3],[2,3],[0,1,2,3],[4]] J=[] input 1: Y=[[0,1,3,5],[0,1,3,5],[2,3,5],[0,1,2,3,5],[4,5],[0,1,2,3,4,5]] J=[] input 3: Y=[[3,5],[3,5],[2,3,5],[2,3,5],[4,5],[2,3,4,5]] J=[0,1]
The algorithm then is pretty simple: Iterate over all inputs, if input==0: add a new node with itself as neighbour, if input==1: add a new node with all nodes as neighbors (also the deleted ones) and add this node to the adjacency list of all nodes, if input>1: determine the nodes with #neighbor-1%input==0 and add them to J, in each case, update the neighbors of each node using J. At the end print the length of Y minus the length of (the set of) J.
JYFHQI!H~Y]]lY)IqH1=Y+m+dlYY]UhlY)VYI&Hq%l@YNH1~J]N))=Ymf!}TJ@YkUlYY;-lYl{J
JY set J=[]
FHQ for H in: input()
I!H ) if H==0:
~Y]]lY Y.append([len(Y)])
IqH1 ) if H==1:
=Y+ Y= +
m+dlYY old nodes updated
]UhlY new node with all neighbors
VY ) for N in range(len(Q)):
I&Hq%l@YNH1 ) if H>0 and len(Y[N])%H==1:
~J]N J.append(N) //this node gets deleted
=Ym Y Y=[ for k in Y]
f!}TJ@YkUlY k-filtered //all items of J are removed
; end input for loop
-lYl{J print len(Y) - len(set(J))
Just call the script and give as input [0,1,0,1,0,1,3] or some other test-case.
lu?+GH<H2m@Gdf%+*@GTtTs>GTHUGQY
This solution uses a reduce function (u) to build up a list, where each entry corresponds to a node remaining in the list, and the value of the entry corresponding to whether the node was originally added under directive 0 or 1.
G is the accumulator variable in the reduce function, and holds the aforementioned list. It is initialized to the empty list, Y.
H takes the value of each member of Q, the input, one by one. The result of the expression is assigned to G each time, and the next entry of Q is assigned to H, and the expression is rerun.
To update G properly, there are two possibilities, one for directive 0 or 1, and one for the other directives. These case are distinguished with the ternary ? ... <H2 ...
If H is 0 or 1, then all we need to do is append H to G. +GH accomplishes this.
Otherwise, the first thing that is need is to determine, for every node in the graph, how many neighbors it has. This is accomplished in two steps:
First, s>GT counts the number of nodes at or after the input node which are 1s. These are all connected to the input node, except that we will over count by 1 if the input node is a 1.
Second, we need the number of nodes earlier than the input node which are connected to it. This is 0 if the input node is a 0, and the index of the input node, T, if the input node is a 1. This value would be given by *@GTT. However, there is still the over count from the first section which needs to be corrected. Thus, we calculate *@GTtT instead, which is 1 less if the input node is a 1. These values are summed, to give the number of nodes connected to the input node.
% ... H will give 0 is that number is divisible by H, and thus should be removed, and will not give 0 otherwise.
f ... UG will thus give the indices of the input which should not be removed, since f is a filter, and 0 is falsy.
m@Gd converts these indices to the 0s and 1s of the corresponding nodes.
Finally, once the resultant list of nodes labeled 0 and 1 is found, its length is computed (l) and printed (implicit).
Broad idea thanks to @PeterTaylor.
VhQJ`N+J*\.&nJX_J`69`96&eN!-J"0689
I must give thanks to @Sp3000 for helping me remove 4 bytes. I originally had an additional check &@JK which made sure there was a 6 or 9 in the number, but after perusing the answers before posting, I read his answer and noticed that my identical translation and reversal already took care of that.
Also thanks to @isaacg for pointing out that strings are iterables, and you can use set operations on them. Also for making the current code ;)
Explanation:
: (implicit) Q=eval(input())
VhQ : for N in range(Q+1):
J`N : J=str(N)
+J*\. : J + "." * ...
&nJX_J`69`96 : J!=translate(reversed(J),"69","96") and...
&eN : N%10 and...
!-J"0689 : not(setwise_difference(J, "0689"))
Fkr2^T6IqlPk1k
Thanks so much to @FryAmTheEggman for removing two chars from filter and ![1:] instead of ==1. As you probably can guess I learned Pyth literally yesterday. :)
jbf!tPTtU^T6
Omg I actually beat Mathematica builtins. Its very simple it just loops through 2 to a million and uses trick that prime numbers have one number in thier prime factorization which pyth happens to have a function for.
jb: Join with \n as sperator
f: filter by
!tPT: not tail of prime factorization of loop variable(tail would be falsey if len 1 so then negate)
tU^T6: filter through range 2-million
It does take a verrrrrry long time to run, but if you want to just see it run, you can change the 6 to a 2 for primes under hundred.
Ph+f!eTmu+G%+&H@G_3-@QH@QhH4UtQd^UT2]Y
edit 4: Realized, that the calculations Q[N]-Q[N+1]+solution[-3] and Q[-2]-Q[-1]+solution[-3] are ident. Therefore I overcalculate the solution by 1, and filter the solutions, where the last entry is 0. Then I pop the last entry. Luckily the special cases doesn't need an extra treatment with this approach. -27 character
edit 3: Applying some golfing tricks from FryAmTheEggman: -7 character
edit 2: Using filter, reduce and map: -3 character
edit 1:In my first version I didn't printed anything, if there was no solution. I don't think that's allowed, therefore +4 character.
Expects a list of integers as input [1,4,2] and outputs a valid solution [2,0,1] if there is one, otherwise an empty list [].
Let Q be the list of 5 levels and Y the list of the solution. The following equations have to hold:
Q0 + Y0 + Y1
= Q1 + Y0 + Y1 + Y2
= Q2 + Y1 + Y2 + Y3
= Q3 + Y2 + Y3 + Y4
= Q4 + Y3 + Y4
Therefore if we use any Y0 and Y1, we can calculate Y2, Y3 and Y4 in the following way.
Y2 = (Q0 - Q1 ) mod 4
Y3 = (Q1 - Q2 + Y0) mod 4
Y4 = (Q2 - Q3 + Y1) mod 4
Than all levels exept the last one are equal (because we didn't used the equation = Q4 + Y3 + Y4. To check, if this last one is also equal to the other levels, we can simply check if (Q3 - Q4 + Y2) mod 4 == 0. Notice, that the left part would be the value Y5. If I calculate the 6th part of the solution, I can simply check, if it is zero.
In my approach I simply iterate over all possible starts ([0,0], to [3,3]), and calculate length(input)-1 more entries and filter all solutions that end with a zero.
mu+G%+&H@G_3-@QH@QhH4UtQd^UT2 generates all possible solutions
it's basically the following:
G = start value //one of "^UT2", [0,0], [0,1], ..., [9,9]
//up to [3,3] would be enough but cost 1 char more
for H in range(len(Q)-1): //"UtQ"
G+=[(H and G[-3])+(Q(H)-Q(H+1))%4] //"+G%+&H@G_3-@QH@QhH4"
//H and G[-3] is 0, when H is empty, else G[-3]
then I filter these possible solutions for valid ones:
f!eT //only use solutions, which end in 0
to this list of solutions I append an empty list, so that it has at least one item in it
+....]Y
and take the first solution h, pop the last element p and print it
Ph
Notice, that this also works, if there is only one block. In my approach I get the starting position [0,0] and doesn't extend it. Since the last entry is 0, it prints the solution [0].
The second special case (2 blocks) isn't that special after all. Not sure, why I overcomplicated things earlier.
n=input()
for F in range(4):
t=[F];b=0;exec"x=(-n[b]-sum(t[-2:]))%4;t+=x,;b+=1;"*len(n)
if x<1:print t[:-1];break
This is the golfed version of the program I wrote while discussing the problem with Martin.
Input is a list via STDIN. Output is a list representing the last solution found if there is a solution, or zero if there isn't. For example:
>>>
[1, 4, 2]
[2, 1, 1]
>>>
[1, 2]
0
>>>
map(int,"3442223221221422412334")
[2, 3, 3, 2, 1, 3, 2, 0, 0, 2, 1, 3, 2, 2, 0, 0, 2, 2, 3, 1, 1, 3]
V4J]NVQaJ%_+s>J_2@QN4)I!eJPJB
The obligatory port. Thanks to @Jakube for the 3 byte saving.
Input method is the same as above, try it online.
First, two basic observations:
Observation 1: It doesn't matter which order you touch the blocks
Observation 2: If you touch a block 4 times, it's equivalent to touching it once
In other words, if there is a solution then there is a solution where the number of touches is between 0 and 3 inclusive.
Since modulo 4 is so nice, let's do that with the blocks too. For the rest of this explanation, block level 0 is equivalent to block level 4.
Now let's denote a[k] to be the current level of block k and x[k] to be the number of times we touch block k in a solution. Also let n be the total number of blocks. As @Jakube has noted, a solution must satisfy:
a[0] + x[0] + x[1]
= a[1] + x[0] + x[1] + x[2]
= a[2] + x[1] + x[2] + x[3]
= a[3] + x[2] + x[3] + x[4]
...
= a[n-1] ... + x[n-2] + x[n-1] + x[n]
= a[n] ... + x[n-1] + x[n]
= C
where C is the final level all blocks end up on, between 0 and 3 inclusive (remember we're treating level 4 as level 0) and all equations above are really congruences modulo 4.
Now here's the fun part:
0 <= C <= 3.There are three cases based on the number of blocks modulo 3. The explanation for each of them is the same — for any number of blocks, there exists a subset of blocks which, if you touch each of them once, increases all block levels by exactly 1.
0 mod 3 (touch every third block starting from the second):
.X. / .X. / .X.
1 mod 3 (touch every third block starting from the first):
X. / .X. / .X. / .X
2 mod 3 (touch every third block starting from either the first or second):
X. / .X. / .X. / .X.
.X. / .X. / .X. / .X
This explains why there are 4 solutions for 0 mod 3 and 1 mod 3, and usually 16 solutions for 2 mod 3. If you have a solution already, touching the blocks as above gives another solution which ends up at a higher block level (wrapping around).
So what does this mean? We can pick any final block level C we want! Let's pick C = 0, because this saves on bytes.
Now our equations become:
0 = a[0] + x[0] + x[1]
0 = a[1] + x[0] + x[1] + x[2]
0 = a[2] + x[1] + x[2] + x[3]
0 = a[3] + x[2] + x[3] + x[4]
...
0 = a[n-1] + x[n-2] + x[n-1] + x[n]
0 = a[n] + x[n-1] + x[n]
And rearrange:
x[1] = -a[0] - x[0]
x[2] = -a[1] - x[0] - x[1]
x[3] = -a[2] - x[1] - x[2]
x[4] = -a[3] - x[2] - x[3]
...
x[n] = a[n-1] - x[n-2] - x[n-1]
x[n] = a[n] - x[n-1]
So what we can see is, if we have x[0], then we can use all the equations except the last to find out every other x[k]. The last equation is an additional condition we must check.
This gives us an algorithm:
x[0]x[k]That gives the solution above.
So why do we sometimes get no solution for 2 mod 3? Let's take a look at these two patterns again:
X. / .X. / .X. / .X.
.X. / .X. / .X. / .X
Now consider the equations at those positions, i.e. for the first one:
0 = a[0] + x[0] + x[1]
0 = a[3] + x[2] + x[3] + x[4]
0 = a[6] + x[5] + x[6] + x[7]
0 = a[9] + x[8] + x[9] + x[10]
Add them up:
0 = (a[0] + a[3] + a[6] + a[9]) + (x[0] + x[1] + ... + x[9] + x[10])
For the second one:
0 = a[1] + x[0] + x[1] + x[2]
0 = a[4] + x[3] + x[4] + x[5]
0 = a[7] + x[6] + x[7] + x[8]
0 = a[10] + x[9] + x[10]
Add them up again:
0 = (a[1] + a[4] + a[7] + a[10]) + (x[0] + x[1] + ... + x[9] + x[10])
So if (a[1] + a[4] + a[7] + a[10]) and (a[0] + a[3] + a[6] + a[9]) are not equal, then we have no solution. But if they are equal, then we get 16 solutions. This was for the n = 11 case, but of course this generalises to any number that is 2 mod 3 — take the sum of every third element starting from the second, and compare to the sum of every third element starting from the first.
Now finally, is it possible to figure out what x[0] has to be instead of trying all of the possibilities? After all, since we restricted our target level C to be 0, there is only one x[0] which gives a solution in the 0 mod 3 or 1 mod 3 case (as 4 solutions / 4 final levels = 1 solution for a specific final level).
The answer is... yes! We can do this for 0 mod 3:
.X..X
.X..X.
Which translates to:
0 = a[2] + x[1] + x[2] + x[3] -> 0 = (a[2] + a[5]) + (x[1] + ... + x[5])
0 = a[5] + x[4] + x[5] /
0 = a[1] + x[0] + x[1] + x[2] -> 0 = (a[1] + a[4]) + (x[0] + x[1] + ... + x[5])
0 = a[4] + x[3] + x[4] + x[5] /
Subtracting gives:
x[1] = (a[2] + a[5]) - (a[1] + a[4])
Similarly for 1 mod 3 we can do this pattern:
.X..X.
X..X..X
Which gives:
x[0] = (a[2] + a[5]) - (a[0] + a[3] + a[6])
These of course generalise by extending the indices by increments of 3.
For 2 mod 3, since we have two subsets which cover every block, we can actually pick any x[0]. In fact, this is true for x[0], x[1], x[3], x[4], x[6], x[7], ... (basically any index not congruent to 2 mod 3, as they are not covered by either subset).
So we have a way of picking an x[0] instead of trying all possibilities...
... but the bad news is that this doesn't save on bytes (124 bytes):
def f(n):s=[];L=len(n);B=sum(n[~-L%3::3])-sum(n[-~L%3::3]);x=A=0;exec"s+=B%4,;A,B=B,-n[x]-A-B;x+=1;"*L*(L%3<2or B<1);print s
u*GeS,1ceHhHC,QtQ1
Explanation:
u reduce, G is accumulator, H iterates over sequence
*G multiply G by
eS max(
,1 1,
ceHhH H[1]/H[0])
C H iterates over zip(
,QtQ Q,Q[1:])
1 G is initialized to 1
max(H[1]/H[0],1) idea thanks to @xnor
https://github.com/isaacg1/pyth
J6ifqT++2010/JJ4U*2^TJ^TT
Here is the original answer (also written in pyth). I know that this is not a very competitive answer (there is python answer of length 26), but I really enjoyed coming up with this, and I think it comes out into a rather humourous answer.
Explanation:
J6 : J=6
i ^TT : convert_to_base(..., 10 BILLION)
fqT U*2^TJ : filter(lambda T: T==..., range(2*10^6)
++2010/JJ4 : 2010 + J/J + 4
Basically this is filtering a list of the first two million numbers for being equal to 2015. Then, it treats this list of numbers as the digits of a base 10 BILLION number. Thankfully, there is only one number equal to 2015 in the range, so you get 2015*10000000000^0, which is just 2015. This takes a couple seconds to run.
I thought I'd have fun and go meta by recycling the best of the recycled. Not going for any awards for brevity here.
+2012+1+1e1 or b+bbv+b+NN
"a"""""
p((('?'.ord-' '.ord )/(1.0/'A'.ord)).to_i)
<<id
1
!
_" fabaaaca"-.-.-.-.+"O"2::++p
aa
AaAAaAAaAAaAAaA
eEe ddd OoOOoOOoOOoOOoOOoOOoOOoOOoOOoO ddD Ccc eEE
ccc LLl
SssSss LLl
SsS LLl
SsSSsSSsSSsS LLl
cccccc
mMm
+ + a pppp pppp y y n n eeeee + + y y eeeee a rrr "
+ + a a p p p p y y nn n e + + + y y e a a r r "
+++++ aaaaa pppp pppp y n n n eee + + + y eee aaaaa rrr "
+ + a a p p y n nn e + + y e a a r r
+ + a a p p y n n eeeee + + y eeeee a a r r "
Hope to see another round of awesome programming puzzles and code golf challenges
===============================
"" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" " ' ' ' ' '
Big char dump below (will clean up if there's more languages to squeeze in):
$$$$$$$()++++++++++++++++++++++++++++--------------------------/////:::;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<>>>>>??AAACCDDEEEFHHLLMMMMM
NOOOOOOOOOOORRRRRRRRRSSSUUUUV[\]___aaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbcccccccccccccddddddddddddddddddddddddddddddddddddddd
ddddddddddddddddddddddddddddddddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeeffffffffffghhhhhhiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiilll
llllllllllmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmnnnnnnnnnnnnnnnnnnnnnnnnn
nnnnnnnnnnnnnoooooooooooooooooooooooooooooooooooooooooooooooooppppppppppppp
ppppppppppppprrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrsssssss
ssssssssssssssssssssssssstttttttttttttttttttttttttttttttttttttttttttttttttt
ttttttttttttttttttttttttttttttttttttttttttuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
uuuuuuuuuuuuvvvvvvvvwwxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
yyyyyyyyyyzz{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
"""
one=1
print(int(ord('A')/(one/(ord(' ')-one))))
id
"mOO"
This is actually also a polyglot for 5 languages: Befunge-93, oOo Code, Pyth, Python 3 and Ruby. However, since the original code is only syntactically valid for Befunge-93, I'm only counting that.
Unfortunately the original code had only one pair of [] and too many .s, so I wasn't able to actually fit Brainfuck in (hence the oOo Code).
This turned out to be surprisingly restrictive, because:
001111111222, requiring the use of ord for Ruby and Python. In particular there's no 5, which turned out to be a pain for Pyth.@ meant that p needed to be used to place an @ for Befunge.* meant that we had to multiply by dividing by the inverse of a number. Fun.The Befunge program is
v
1
!
_" fabaaaca"-.-.-.-.+"O"2::++p
where we've skipped the useless instructions. We encode each digit as the difference in ASCII values between chars, specifically cabf vs. a.
The corresponding BF is
>><->>->>>><>+++++[>++++++++++<-]>.--.+.++++.>>[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>>>>>>>><;;;;;;;;;;;;;;;;>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>->>>]
, of which the only relevant part is
+++++[>++++++++++<-]>.--.+.++++.
Pyth only executes the first line, so
+2012+1+1e1 or b+bbv+b+NN
Note that Pyth uses an prefix notation, so the first part of the line is actually
2012 + (1 + (1 + (1 % 10)))
(Note: e means %10)
Due to the nature of Pyth, this is automatically printed. The rest of the line is valid Pyth, but the preceeding space before the o suppresses the automatic printing.
The majority of the Python code is commented out using strings, especially a large triple-quoted string in the middle. Ignoring a few stray strings, we have:
+2012+1+1e1 or b+bbv+b+NN
"""
...
"""
one=1
print(int(ord('A')/(one/(ord(' ')-one))))
id
The first and last lines are syntactically valid, but do nothing. The middle two lines print what we need.
The Ruby code is similar, but we're using a heredoc instead of a triple quoted string to comment out most of the program. Ignoring some stray strings, we have:
+2012+1+1e1 or b+bbv+b+NN
p((('?'.ord-' '.ord )/(1.0/'A'.ord)).to_i)
<<id
...
id
Once again, the first line is syntactically valid, but does nothing. The second line prints what we need.
eSmhxtu+G%@Q+eG@QeGlQUQ]ddUQ
Try it here: Pyth Compiler/Executor
It expects a list of integers as input
[0,2,5,4,-9,0,-1,1,-1,1,-6]
I noticed one important property of the function loop: For each i there is a j, so that loop(a,i,0) == loop(a,j,1) and vice versa. Therefore we only need to compute the values loop(a,i,b) for b=0.
Proof: If the is a cycle i -> j -> k -> ... -> z -> i with b = 0, then there exists the cycle j -> k -> ... -> z -> i -> j with b = 1.
Therefore a simple script can work the following way. Iterate over all i and try to reach i by iteratively computing i = a[(i + a[i]) mod len(a)] mod len(a). Since this computation may ran into a cycle without i, we cancel the computation after len(a) steps. Then we print the maximum cycle.
A Python 2 implementation looks like this (125 character}:
a=input();A=len(a);m=[]
for i in range(A):
j=i
for c in range(A):
j=a[(j+a[j])%A]%A
if i==j:m+=[c+1];break
print max(m)
For the pyth implementation I used a little different approach. For each i I compute the list of positions, and look for i in this list.
eSmhxtu+G%@Q+eG@QeGlQUQ]ddUQ
m UQ for each d in [0, ..., len(input)-1] compute a
u ]d list G (using reduce),
which is first initialized with G = [d]
UQ for each H in [0, ..., len(input)-1]:
+G append to G the value
%@Q+eG@QeGlQ input[G[-1] +input[G[-1]] % len(input)
(notice that list lookups in pyth work with modular wrapping)
t remove the first value (which is d)
x d and find the index of d in this shortend list
(it's -1, if d is not in the list)
h add 1
eS print the maximum (end of sorted list)
@proud haskeller's solution was i few characters shorter than my Python solution, therefore I 'had' to shorten it a bit.
a=input();A=len(a);l=lambda j,i,c:c<=A and(c*(i==j)or l(a[(j+a[j])%A]%A,i,c+1));print max(l(i,i,0)for i in range(A))
The difference is, that I calculate the number recursively instead of iteratively.
This is not a serious golfing answer. With a different algorithm I reached 138 byte. Just wanted to post this here, because it doesn't use brute force. Complexity is Theta(#pictures).
f=lambda x:0**x or x*f(x-1)
def g(Q,n):
while sum(Q):
for j in 0,1,2,3:
p=f(sum(Q)-1)*Q[j]
for k in Q:p/=f(k)
if p<n:n-=p
else:print j;Q[j]-=1;break
g([1, 4, 3, 2], 65)
Same algorithm, just some golfing: don't import the factorial method and little changes in the order of the calculations.
Lu*GhHUb1WsPQV4J*@QNytsPQFZPQ=J/JyZ)I<JeQ XQ4-eQJ)EN XQNt@QNB
Nothing special here, exact translation of my python code. Way too long though. I had too use a few ugly (long) things. The first 9 letter alone is the definition of the factorial.
Lu*GhHUb1 def y(b): G=1; for H in range(b): G*= H+1; return G
Also stuff like Q[j]-=1 is way too long: XQNt@QN (1 character more than Python!!!)
Try it here: Pyth Compiler/Executor. Disable debug mode and use [2, 2, 3, 1, 86] as input.
@fqPQm/TdU4^U4sPQteQ
Input is in Python list form, e.g. [1, 2, 4, 1, 5]
Output is also in Python list form, e.g. [0, 1, 1, 3, 2, 2, 2, 2] for the above input.
The solution is brute force, and takes about 10 seconds, worst case, on my machine.
How it works:
@fqPQm/TdU4^U4sPQteQ
^U4sPQ All permutations of [0, 1, 2, 3] with length equal to the number
of paintings.
m/TdU4 Find the count (/) of paintings by painter in the input list.
fqPQ Filter the permutations on the counts being the desired counts
in the input.
This gives all possible orderings of the paintings.
@ teQ Index into this list at the given location - 1. (0-indexing)
=Q{cQdL+x"C D EF G A B"hb&tlbt%hx" #b"eb3FZQJx[188 212 199 213 200 224 2555 2411 2412 2556 2567 2398)u+*G12hHSm%-dyZ12mykQ0IhJ+Z@c"sus2 maj dim aug m sus4 7 m7 mmaj7 maj7 aug7 dim7"dJ=T0;ITQ
Not really happy with it. Used hard-coded chords.
Try it here: Pyth Compiler/Executor. Disable debug mode and use "C D# G" as input.
First some preparation:
=Q{cQd
cQd split chord into notes "C D# G" -> ["C", "D#", "G"]
{ set (eliminate duplicates)
=Q Q = ...
Then a function that converts notes into integer
L+x"C D EF G A B"hb&tlbt%hx" #b"eb3
defines a function g(b),
returns the sum of
index of "D" in "C D EF G A B"
and the index of "#" in " #b"
(if b than use -1 instead of 2)
Then for each note, shift the coord and look it up in a table
FZQJx[188 ...)u+*G12hHSm%-dyZ12mykQ0IhJ+Z@c"sus2 ..."dJ=T0;ITQ
implicit T=10
FZQ for note Z in chord Q:
mykQ map each note of Q to it's integer value
m%-dyZ12 shift it by the integer value of Z modulo 12
S sort it
u+*G12hH 0 convert it to an integer in base 12
x[188 ...) look it up in the list (-1 if not in list)
J and store the value in J
IhJ if J>=0:
+Z@c"sus2 ..."dJ print the note Z and the chord in the list
=T0 and set T=0
; end loop
ITQ if T:print chord (chord not in list)
K"23542 31463 12651 "h/x+K_Kz6
Requires the two digits as input, with no space in between (ex. 23 not 2 3).
Explanation:
Any two digit sequence that lies within 23542 represents two sides that have 1 on top. Likewise, 31463 for 2, etc. Reversing this string gives the sequences for 4 through 6.
This code just does a lookup in the string "23542 31463 12651 15621 36413 24532", divides the index by 6, and increments to determine what the top side must be.
Thanks to @FryAmTheEggman for tips on golfing this.
There's a nice polynomial expression modulo 7 for the third side given two sides a and b.
or factored
The modulo 7 maps to a remainder in {0,1,2,3,4,5,6}.
I explain why it works in this Math SE answer, though I do think there probably is a cleaner argument I'm missing. The only other two-term polynomial that works is
which I originally found by transforming my bit-bashing into arithmetic operations, then did a brute-force search over polynomials of this form to find the nicer one.
Please feel free to add ports of this into your favorite language; this is a CW post.
J, 9 by Synthetica
7|3***+*-
See my post
Dyalog APL, 11 by Zgarb
7|×(3××)+×-
That's four nested forks, found by trial and error.
TI-Basic, 14 by Timtech
7fPart((A³B-AB³)/21
Pyth, 16 by FryAmTheEggman
M%*3-*H^G3*^H3G7
Defines a function g of two values.
Golfscript, 18 by Peter Taylor (old polynomial)
~1$*.5?3*@.*@*- 7%
CJam, 18 by Martin Büttner (ported from Peter's GolfScript) (old polynomial)
l~1$*_5#3*@_*@*m7%
Mathematica, 20 by Martin Büttner
Mod[+##(#-#2)3##,7]&
Yes, that's a unary plus, and no, there's no shorter way that doesn't use a unary plus.
Julia, 24 by Martin Büttner
f(a,b)=3a*b*(a^2+6b^2)%7
CoffeeScript, 28 by rink.attendant.6
x=(a,b)->3*a*b*(a*a+6*b*b)%7
JavaScript (ES6), 28 by rink.attendant.6
x=(a,b)=>3*a*b*(a*a+6*b*b)%7
Essentially the same as CoffeeScript.
Python 28, by xnor
lambda a,b:3*a*b*(a*a-b*b)%7
Bash, 31
Nothing special:
echo $[3*($1**3*$2-$1*$2**3)%7]
Another (longer but perhaps interesting) approach.
Nim, 36 by Sillesta
proc(x,y:int):int=3*x*y*(x*x-y*y)%%7
Java, 46 by rink.attendant.6
int f(int a,int b){return(a*a+6*b*b)*a*b*3%7;}
PHP, 49 by rink.attendant.6
function x($a,$b){echo($a*$a+6*$b*$b)*3*$a*$b%7;}
Batch, 52 unclemeat
set/aa=(3*(%1*%1*%1*%2-%1*%2*%2*%2)%%7+7)%%7
echo %a%
CMD does not support true modulus natively (so can't handle negative numbers) - hence %%7+7)%%7.
LESS (as a parametric mixin), 62 by rink.attendant.6
.x(@a,@b){@r:mod(3*@a*@b*(@a*@a+6*@b*@b),7);content:~"'@{r}'"}
See my post below.
Lmsd^b2Msmsm>bkGHDPNK-ghNeNgeNhNR?^tZ<KZKZAGHmsdCm,PkP,yhkyekm,@Qb@QhbUQ?"none"|!G%G3s[*!+GH"Grime-"*qGH"strongly ""nontransitive
Try it here, or at least you could, but the online eval doesn't seem to like lists of lists :( If you want to try it there, manually store a list of 3 dice into a variable not used by the program and then replace all instances of Q with that variable. A sample initialization:
J[[3 3 3 3 3 6)[2 2 2 5 5 5)[1 4 4 4 4 4))
This passes all of Martin's test cases, I haven't the heart go through all of Peter's cases :P
Explanation (this is gonna be a doozy)
Lmsd^b2
Pretty simple, makes a function y that returns the sum of each Cartesian pair of values in an iterable. Equivalent to: def y(b):return map(lambda d:sum(d),product(b,repeats=2)). This is used to create many-sided dies that simulate throwing the regular dies twice.
Msmsm>bkGH
Defines a function g of 2 arguments that returns how many times a die beats another. Equivalent to def g(G,H):return sum(map(lambda k:sum(map(lambda b:b>k,G)),H).
DPNK-ghNeNgeNhNR?^tZ<KZKZ
Defines a funtion P that takes a list of two dice as its argument. This returns -1 if the first die 'loses', 0 for a tie and 1 if the first die 'wins'. Equivalent to:
def P(N):
K=g(N[0],N[-1]) - g(N[-1],N[0])
return -1**(K<0) if K else 0
The AGH assigns acts like a python 2-tuple assignment. Essentially G,H=(result)
msdCm,PkP,yhkyekm,@Qb@QhbUQ
Going to explain backwards through the maps. m,@Qb@QhbUQ iterates over b=0..2 and generates 2-tuples of dice with index b and index b+1. This gives us dice (A,B),(B,C),(C,A) (pyth automatically mods indexes by the length of the list).
Next, m,PkP,yhkyek iterates over the result of the previous map, with each dice pair being stored in k over each run. Returns tuple(P(k),P(tuple(y(k[0]),y(k[-1])))) for each value. That boils down to `((A beats B?, 2*A beats 2*B), (B beats C?, 2*B beats..)).
Finally, msdC sums the values of the previous map after it has been zipped. The zip causes all of the single dice 'beats' values in the first tuple, and the double dice values in the second.
?"none"|!G%G3s[*!+GH"Grime-"*qGH"strongly ""nontransitive
A gross thing that prints out the results. If G is 0 or not divisible by 3, this catches bot +/- 3, (|!G%G3), prints none, otherwise prints the sum of the follwing list: [not(G+H)*"Grime",(G==H)*"strongly ","nontransitive"]. I think the booleans are fairly self-explanatory with regard to the definitions in the question. Do note that G cannot be zero here, as that is caught by the previous check.
Sometimes, default values in functions can be useful for golfing. Pyth actually supports this (much to my surprise). For example:
DC=Z1RZ;C;C5
Will print:
1
5
You can also use J and K to save characters when doing this:
DgJ1K1R+JKg;g2;g2 3
prints:
2
3
5
This is usually useful for recursive algorithms.
As a side note, this is something that could easily break if small things about pyth are changed, I will try to keep this updated, but since it isn't overly common, no promises ;)
lambda x:max(sum((a+.5-m)*(a+.5-n)<0for m,n in zip(x,x[1:]))for a in x)+1
Just a straightforward lambda
Just to show another approach:
heSmsmq@S+k(d)1dC,QtQm+b.5Q
This one's roughly equivalent to
lambda x:max(sum(a+.5==sorted(n+(a+.5,))[1]for n in zip(x,x[1:]))for a in x)+1
applied to the input list from STDIN. Try it on the online interpreter.
heSmsm&<hSkdgeSkdC,tQQQ
Try it here: Pyth Compiler/Executor
It expects a list of integers as input
[-1, 3, 1, -2, 5, 2, 3, 4]
It's a straightforward translation of my Python program:
lambda s:1+max(sum(min(a)<i<=max(a)for a in zip(s,s[1:]))for i in s)
Just for archiving reasons.
heSmsm<*-dhk-dek0C,tQQm+b.5Q
A corresponding Python code would be:
f=lambda x:1+max(sum((i-a)*(i-b)<0for a,b in zip(x,x[1:]))for i in [j+.5 for j in x])
heSmsmq1xS+dSkdC,tQQQ
Give input as Python-style list, e.g. [-1, 3, 1, -2, 5, 2, 3, 4]
Closely based off of @jakube's program, but with an improved central algorithm. Instead of doing a > check and a >= check, I do a .index() on the three numbers combined and make sure the index is 1, meaning it's greater than minimum and less than or equal to the maximum.
def g(r):
for p in r:
for q in r:
for h in 0,1:
if p[h::2]==q[h::2]and p[1-h]+p[~h]==q[1-h]:p[~h]+=q[~h];r.remove(q);return g(r)
return r
f=lambda P:g([x+[1,1]for x in P])
My first solution used the exact same algorithm as KSFT, therefore I experimented with other methods.
First I do some preprocessing, I convert all points into small 1x1 rectangles {x+(1,1)for x in P}. With these rectangles, I call the function g. g iterates over each combination of rectangles. If it finds 2 rectangles, that can be merged into a bigger one, it deletes both and append the new one. Afterwards it calls itself with the new set of rectangles.
f([[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2]])
Here are the visualization of the results. Note that they may be a bit different in the current version. The idea is though, that there is no kind of noticeable pattern.
A U-shaped region:
A large triangle
A square with holes:
Disconnected regions:
D!HFGHFZHV2I&q%2>GN%2>ZNqs%2>G-1N@Z-1N X-3NG@Z-3NR!-H]Z)))RH!m+d*2]1Q
Works only in the offline version. Bug in the online version is fixed now. Try it here: Pyth Compiler/Executor. Expects a list of lists, not a list of tuples.
edit: Used an idea from @edc65: Instead of deleting both rectangles and creating a new one, I manipulate one and only delete one. In the Python solution I could get ride of the sets and the tuple-list-tuple casts. -11 chars in Python / -4 chars in Pyth
^G2
^ on sequence, int, gives the cartesian product of the first argument with itself n times, where n is the second argument.
In this case, since G is the alphabet (abcdefghijklmnopqrstuvwxyz), ^G2 gives all 2 letter strings, aa through zz.
lT
l, while normaly serving as len(), can also be used as log base 2. Since T is the variable initialized to 10, this prints 3.3219280948873626, log base 2 of 10.
H
H is the empty dictionary (hash-table) in Pyth, and is the only way to get a dictionary in Pyth, short of using v (eval) or $ (Python literal).
Pyth has no multi-character constructs other than literals. Also, Pyth compiles essentially one-to-one into Python.
u*GhH%2_UQ1
Q is the input value. UQ creates the list [0, 1, 2, ..., Q-1], _ inverts it, and %2 removes every other element [Q-1, Q-3, Q-5, ..., (1 or 0)]. u*GhH...1 reduces the list by multiplying the list elements (increased by 1) to 1.
Try it here: Pyth Compiler/Executor
Mho/<>GNHZUG
This defines a function g, which requires a list of numbers and a number as input.
E.g.
Mho/<>GNHZUGg[0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0)5
You can test it here: Pyth Compiler/Executor
Mho/<>GNHZUG
M defines a function g(G,H), G is the sequence, H the sequence length
o UG orders the numbers between 0 and len(G)-1 according to the following key
<>GNH take the subsequence G[N:N+5]
/ Z count the zeros in this subsequence (this is the key)
h return the first value of the sorted list (minimum)
Mho_s<>GNHUG
print" ".join([bin(ord(i))[2:]for i in raw_input()])
I'll work on translating this into Pyth. Someone else did a Pyth answer already.
If you don't care about it being a full program or about I/O format and use Python 3, you can do it in 23 bytes like this:
[bin(ord(i))for i in x]
x is the input.
I know this doesn't count because the interpreter wasn't released before the challenge was posted, but here it is in KSFTgolf:
oan
jdmjkjCd2z
Python mapping and explanation:
j # join( "Join by space"
d # d, "this space"
m # Pmap(lambda d: "Map characters of input string"
j # join( "Join by empty string"
k # k, "this empty string"
j # join( "This is not a join, but a base conversion"
C # Pchr( "Convert the character to ASCII"
d # d "this character"
# ),
2 # 2 "Convert to base 2"
# )
# ),
z # z))) "mapping over the input string"
Input is the string that needs to be converted without the quotes.
Input in pyth is only one line, so it accepts comma-delimited instead of newline delimited. Pyth is not on Spoj, but there wasn't any rule saying it had to be.
sf>TZtQ
Very simple:
s sum
f filter by
>TZ filter arg greater than zero
tQ run filter on all but first element of evaluated input
qS@cz", "0S@cz", "1
Try it here. Note that the two words in the input must be separated by a comma and a space.
Python Mapping and explanation
q # equal( "Check equality"
S # sorted( "Sort"
@ # list looku "Extract element from list"
c # chop( "Separate by delimiter"
z # input( "Input variable"
", " # ", " "This delimiter"
0 # 0 "The 0th element"
S@cz", "1 # .. "The same thing with the 1st element
I'm sure someone can come up with a shorter implementation, but I've only been learning Pyth for a few days. It would also be a lot shorter if I didn't stick strictly to the input format given in the question.
For instance:
qS@Q0S@Q1
Which is only 9 bytes, works if the input is formatted like 'parse','spare'. So which one do you count?
Good practice though!
MqSGSH
Defines function with two args, the two words.
M define function g with two args, G and H
q equals
SQ sorted first arg
SH sorted last arg
If that cheating golfscript program counts with hardcoded input, we can do that too with : qSS
And for just two more characters you can have it check an infinite number of words:
ql{mSdQ1
q 1 Equals 1
l Length
{ Set constructor (eliminate all duplicates)
m Q Map on evaluated input
Sd Sort each element
I,R=raw_input,range
P,T,L=map(int,I().split())
S=I()
D=R(P+1)
for r in R(P):D[1:r+2]=[min([D[c],D[c-1]+(S[r]<".")][c%L>0:])for c in R(1,r+2)]
print D[T*L]
A straightforward DP approach. A fair chunk of the program is just reading input.
Explanation
We calculate a 2D dynamic programming table where each row corresponds to the first n parking spots, and each column corresponds to the number of trucks (or parts of a truck) placed so far. In particular, column k means that we've placed k//L full trucks so far, and we're k%L along the way for a new truck. Each cell is then the minimal number of cars to clear to reach the state (n,k), and our target state is (P, L*T).
The idea behind the DP recurrence is the following:
k%L > 0 spaces along for a new truck, then our only option is to have come from being k%L-1 spaces along for a new truckk%L == 0 then we have either just finished a new truck, or we'd already finished the last truck and have since skipped a few parking spots. We take the minimum of the two options.If k > n, i.e. we've placed more truck squares than there are parking spots, then we put ∞ for state (n,k). But for the purposes of golfing, we put k since this is the worst case of removing every car, and also serves as an upper bound.
This was quite a mouthful, so let's have an example, say:
5 1 3
..##.
The last two rows of the table are
[0, 1, 2, 1, 2, ∞]
[0, 0, 1, 1, 1, 2]
The entry at index 2 of the second last row is 2, because to reach a state of 2//3 = 0 full trucks placed and being 2%3 = 2 spaces along for a new truck, this is the only option:
TT
..XX
But the entry at index 3 of the second last row is 1, because to reach a state of 3//3 = 1 full trucks placed and being 3%3 = 0 spaces along for a new truck, the optimal is
TTT
..X#
The entry at index 3 of the last row looks at the above two cells as options — do we take the case where we are 2 spaces along for a new truck and finish it off, or do we take the case where we have a full truck already finished?
TTT TTT
..XX. vs ..X#.
Clearly the latter is better, so we put down a 1.
JmvdczdKw=GUhhJVhJ=HGFTUhN XHhThS>,@GhT+@GTq@KN\#>%hT@J2Z)=GH)@G*@J1eJ
Basically a port of the above code. Not very well golfed yet. Try it online
Expanded
Jmvdczd J = map(eval, input().split(" "))
Kw K = input()
=GUhhJ G = range(J[0]+1)
VhJ for N in range(J[0]):
=HG H = G[:]
FTUhN for T in range(N+1):
XHhT H[T+1] =
hS sorted( )[0]
> [ :]
, ( , )
@GhT G[T+1]
+@GTq@KN\# G[T]+(K[N]=="#")
>%hT@J2Z (T+1)%J[2]>0
)=GH G = H[:]
)@G*@J1eJ print(G[J[1]*J[-1]])
Now, if only Pyth had multiple assignment to >2 variables...
|6# `.3i !|
|:" |
| |
| # $> 0 << |
| |
| |
| |
|print 02 ** 2 |
| |
| |
| |
| |
| |
| :Disp 5 |
| |
| |
| |
| |
| |
| |
L-^=v^Ej2tW8OxNOIecSt4m} j O%YRJ;PJ!M|0*oO77*Rs&2*<c"KI7e%FY^?I=];Y@`x)u)IBk%_a#<E6<yv5O*$kL):
KNGq)2Wa%b)j"(6U|{[UY@`l CSJ`u0RHX!1z7f,v} =GvRgkrEZ=YT:4H44bz] C<](:+FF?Ay'vX~h5QMF)0vaXk1sk@p
Zj).{+l;PBKHABvEP%FnSw>u_-4B^AI8Kay&5]vXZJ{fCF]UVZ<!ZpOI$7\Y%@:%HwPsX-`/l]ZZ?Q/d`\M<T@'t]zip
{[ovg:6E CT&'+vU4Heb^;}0AV|?}M0rAH/^DL"RkT~%$[VUlM]-&We4(P=66},hL~;a`:$'yty.W[g2OWcL~b:Ryj0*eN<
;&-n[F1F=oh0k[NI!xS"]pA@Y;K}'=ekG5yda8J$+`N;:FIx:l,f_LT@sV[]HF@2*vl?|q"GL1j&%e(CyYPqY%3W|@`z}]bp
4_'1Nx{G2&j6$UWt_#%`sTt2xC}s1P8J<gV24_RWge/aMuyVOjz=zS!1i2s@`Q#@^~@W/k@.YLbKxS:g9?J^p;7ju?B\yC5
x,ZApKS5G4}kx_iM)f4/|su>=[{XSV#{,j5Qn3U.v5LF;HXs%DYm4'+efmU;\}f6j$SFCRC`Gsd37:'3$q=bs;lvsW0Yj^:-
I[94@I|.IpR=}4KB4ZG4>8PR29'L?n\gk,*4X[-%T`\FC)jj0jl_x<xL8E:G2-"3tT8&E}"sE+SH[7jR%@V)a{ m8K>.rAO
2[dq7GX9nrz8p4}^ mn@q|dF%<.Tl8)Dk?O.<UoE(a*k_=4+u!h$^bVd:$jS#EHFh@Z=y=ib^~/~lEJ^SQ3E_t#&^IOov7v8
~j#I#OHgxg{ZDyCsq-(GVq}HbiG,JV?eJ~5wJ;bSt@;3LI!2(6gIT92>}`_dw;YF@ccTIEz\Gu@2(}J2I1"S{R(2niIYPp9
8A3iP[*!SH2*SN8'`V?w4Ufx2HAz%{}FlUdH31TJ5{:ge^N91^;9Gj`Uqf'$_|8P"kHR1w.(ASwmN)U-~q"[XcWbqPnns=
d.ZoPJ}$Xc2lA>HN28`(dy+UArsQ=?KE07=\FsVN(#?&hRabS%BVI <`O$o 4x5ZFFLGDcA4t?&Eh~Z$oBWwNSNv`^;vO'
2&9egng~L#\QkfMG?S/n@%-VA[?f9K&3"V%P#Sv0!D<,GV:Z;3c&zFe^k&^0b7fAjvrbMc^Lq7k$h=YL<h7<0\NK>~Q=uUv)
4cI$.'b-RVS-=rom:=8QR=c>9am-^5F[XGv>E/>|]~\']3{r{kTc?ee1v=;I7]52#NE)~A;}!z>5?hi{5<9FtWH6{VO_Y-Jy
Mw>{l8n#mD,kl'8cG^.7sy=QqU-3~SKG5(.Ta]:-Vfr'NS$o*q:w6e$&7spk3{CFT'l_hGY0-0Xui*5i^0^fO@6?2IdCn_C
lPKaJ6]0t!u>v8<d'Vby]8kEHh04p(YI)&7w82BrGB3PkI,s+%7ux5)gau`G!8F8hLa4[lfD55Xf3Hqy*-K,?;2'fxH3JWYE
Z.[N`[KCY@TzKX4TMXsm{Xbd:B3)Gy[mlwnC$>)z`:k=C\0ho/v{7#+2,*%]>~vI2^C:2DebJR>.ESw^wd2N<~]O9sOQ
`_yvIw&Ryf%JgT@W(G1wfU3.4G3U}x1jKJzJY\S9n$2~P;F}*eT9UXcTNBTrTs>~0v_Oi.y8ofX6i5u$;'^"q][QhTb*gO[U
n'R0"v1r+9fv;5G7Bg=D:c*a=1@[}7}dYOO{Mz2&@6`jnNq.QcBDM9Dd=R.*=MqZ93#'{AJJFqx<{qb':B!H8ig1L%T\Vuc"
(h$i3`,scX'hqpbw"=nY`*Lu:h1wR{+-`\^3cQkIWfq)3?&p;~pvDW$o7\O|RrB2{PX.s#G6A.s<OA_,TI_b*&lO@L3KrQv
Uses the old restricted source trick that Pyth only executes the first line of its source code (note that the online interpreter does not act this way). Any value in Pyth not used for something else is automatically printed.
The # `.3i runs a while 1 with a try .. except block. The `.3 would print 0.3 as the string representation of .3 but it is prefixed by a space character, which suppresses printing. The call to i requires 2 arguments, but it receives one a not function that also gets no arguments, so an exception is thrown, and the loop breaks.
Not a complicated solution. Will be golfing more. Just takes cartesian product of lists and filters. Same strategy as @optimizer (I'm guessing because of his comment, didn't actually decipher that CJam) Thanks to @FryAmTheEggman for 2 bytes and trick with M.
Ml{m`Sdfqu*GHT1G^r2GH
Defines a function g with args G and H
M function definition of g with args G and H
l length of
{ set (eliminates duplicates)
m map
`Sd repr of sorted factors so can run set (on bash escape ` as \`)
f filter
q G equals first arg
u*GHT1 reduce by multiplication
^ H cartesian product by repeat second arg
r2G range 2 to first arg
Worked on all test args except last, was too slow on that one but there is no time limit given.
Now reduced over 50 bytes from original!
=H" y "ANkmsdcz\:Kc"cero uno dos tres cuatro cinco seis siete ocho nueve diez once doce trece catorce cuarto veinte"dI>k30=k-60k=H" menos "=N?1qN12+N1)++?+"Son las "@KN>N1"Es la una"H??eKqk20?@Kk<k16+?"dieci"<k21+PeK\i@K%kT<k30"media"
Insanely long for Pyth but that's because there's some raw data. Can probably be golfed even further. Uses obvious technique of splitting task up into hours, y/menos, tens digit of minutes, and ones digit of minutes and then translates numbers using translation array and everything else using a crap-ton of ternaries.
=H" y " Set H to " y "
A Double Assignment
Nk The variables N and k (hours and mins)
m cz\: Map input split by ":"
sd Make both int
Kc"..."d Set K to string split by spaces
I>k30 If k>30
=k-60k Set k to 60-k
=H" menos " Set k to menos instead of y
=N Set N
? qN12 If N=12
1 Go back to one
+N1 Increment N
) Close entire if block
+ Concat of hours and minutes
+ Concat hours and y/menos
? >N1 If hour greater than one
+ Concat of son las and hour
"Son las " "Son las "
@KN Index translation array for hour
"Es la una" Else es la una
H " y " or " menos "
? <k30 If minutes less than 30
? qk20 If minutes is 20
ek Last element of array (veinte)
? <k16 Else check if minutes<16
@Kk Get minutes directly from array
+ Else tens and ones sum
? <k21 If minutes<21
"dieci" "dieci"
+PeK\i Else get veinti from veinte
@K%kT Ones digit of minutes
"media" Else get "media"
L+_tbbjbymy+>zd*\ dlz
Try it online: Pyth Compiler/Executor
&zhfTmf!/>zhxzYYm<>zkdUzUz
Note that due to a bug in the online compiler, the empty string case only works correctly on the command line version, which can be found here.
You can also cure the bug by giving a newline as the input for the online compiler.
z = input(), implicit.
&z Prints empty string if input is empty.
hfT Take the first non-empty list from
m Uz A list of list of substrings of z, divided by length
m<>zkdUz with some shorter strings repeated later, to no effect.
f Where the substrings are filtered on
!/ Y There being 0 occurrences of the substring in
>z The slice of z
hxzY from the character after the first character
of the first occurrence of the substring in z
to the end of z.
This will eventually guess the correct answer. On average 2500 tries. Literally just takes random guesses no matter what the input is. Since you can't define rateGuess in pyth just takes (uneeded) input from stdin and outputs to stdout.
Ofql{T4^UT4
O Pick random
f filter
ql{T4 set length is four (checks for duplicates)
^ 4 Caretesian product with 4 repeats
UT Unary range till 10
Sml{dCuS?+G,hhGtehGHm,_ekhkGQ],ZZ
Input is a list of ones and zeros, like in the question. Try it online: Pyth Compiler/Executor
It's a one-on-one translation of the following Python 2 code (126 bytes).
print sorted(map(len,map(set,zip(*reduce(lambda s,i:([[-b,a]for a,b in s],s+[[min(s)[0],min(s)[1]-1]])[i],input(),[[0,0]])))))
I create a list of coordinates of the single magnets. This is initialized with the magnet [0,0]. Then for each of the integers of the blueprint I manipulate the list in the following way. If the next integer is 0, I rotate the sculpture by changing the coordinates for each magnet [a,b] to [-b,a] (basically multiplying with a rotation matrix). If the next integer is a 1, I search for the minimal piece [a,b] (which is automatically the lowest magnet of the leftmost column) and append the magnet [a,b-1] to the list.
After all the input is processed, I create 2 sets (for removing duplicates), one for the x-values and one for the y values, and print the sizes of them in sorted order.
Sml{dCuS?+G,hhGtehGHm,_ekhkGQ],ZZ
],ZZ starting list G=[(0,0)]
u Q],ZZ for H in input(): manipulate G
S Sort G after each manipulation
? H G = ... if H==1 else ...
m,_ekhkG [(-b,a) for a,b in G)] (rotate)
+G,hhGtehG G+[(G[0][0],G[0][1]-1)]
(G[0] is the lowest magnet in the leftmost column)
C Zip the coords together
(creates 2 lists, x- and y-coords)
ml{d for each of those list compute number of unique values
S sort and print
An idea for improvement: Using complex numbers as coords for the magnets. A rotation is just a multiplication by j and subtracting j from the lowest magnet in the leftmost column. Sadly finding this lowest leftmost magnet takes way too many chars in Python, not even talking of finding the rectangle.
jku@[+eGPG+tGhG_Gms!dG)sHwsmjCk2z
Uses:
0 : rotate right
1 : rotate left
2 : reverse order
3 : flip values
This is a program that takes the string as it's first argument and the string of commands as the second argument. In the online version, you should give the strings separated by a newline, like so:
AbC
0321
Explanation:
: z=input() (implicit)
jk : join("", ...)
u@[ )sHw : reduce(select from [...] the value at int(H), input(), ...)
+eGPG : [ G[-1] + G[:1],
+tGhG : G[1:] + G[1],
_G : G[::-1],
ms!dG : map(lambda d: int(not(d)), G) ]
smjCk2z : first arg = sum(map(lambda k:convert_to_base(ord(k),2),z)
Something I couldn't quite squeeze in: Pyth's reduce automatically uses G for the previous value, and H for the next value.
Note: Pyth is much too new to be eligible to win. However, it was a fun golf and I thought I'd share it.
VQ<*QX*d2N\XQ
How it works:
Q = eval(input())
VQ for N in range(Q):
< Q [:Q]
*Q (Q* )
X*d2N\X assign_at(" "*2, N, "X")
Basically, this uses X to generate "X " or " X" alternately, then repeats that string Q times, and takes its first Q characters. This is repeated Q times.
How does the X (assign at) function work? It takes the original string, " " in this case, an assignment location, N in this case, and a replacement character, "X" in this case. Since Pyth's assignments are modular, this replaces the space at location N%2 with an X, and returns the resultant string, which is therefore "X " on the first, third, etc. lines, and " X" on the others.
j="".join
f=lambda S,I:reduce(lambda s,i:[s[1:]+s[0],s[-1]+s[:-1],s[::-1],j([`1^int(c)`for c in s])][int(i)],I,j([bin(ord(c))[2:]for c in S]))
Similar to my pyth answer in approach: I build a list of all the strings and index into it based on the value of the instruction string that I iterate over using reduce.
Uses:
0 -> Rotate left
1 -> Rotate right
2 -> Reverse order
3 -> Invert bits
KGJ@GrQZfqJusm@zxKdGUTJ!!J
There are quite a few unfortunate consequences that cost this program bytes, like having to store G in K to use it in the reduce, as well as needing to use not(not(J)) to start the filter. Because of this, I expect this can still be golfed.
This is a program that takes input like:
aebcdjfghiqklmnopzrstuvwxy
'John Doe'
(Note the lack of quotes in the first argument)
Explanation to come after crippling exhaustion ;)
Loops Fibonacci until array is length n but only adds to array if prime.
J2K1W<lYQAJK,+KJJI!tPK~Y]K;eY
Kind of slow, but reached n=10 in ~15 seconds. Can probably be golfed more.
J2 J=2
K1 K=1
W <lYQ While length of array<input
AJK,+KJJ J,K=K+J,J
I!tPK If K prime(not builtin prime function, uses prime factorization)
~Y]K append K to Y
; End loop so next is printed
eY last element of Y
JGfqzuXGJrQ0UTz1
Input should be given on two lines, name and then permutation. Permutation should be quoted. Name may be quoted or unquoted. For example:
"John Doe"
"aebcdjfghiqklmnopzrstuvwxy"
Gives 140.
Implicit:
z = input() z is the name.
Q = eval(input()) Q is the permutation.
G = 'abcdefghijklmnopqrstuvwxyz'
JG J = G
f 1 Starting at 1 and counting upwards, find
the first case where the following is true:
qz z ==
u UTz reduce, where the accumulator, G, is initialized to z on
XG translate G
J from the normal alphabet, J
rQ0 to Q.lower().
QWtQ=Q@,/Q2h*3QQQ
~Q1WttP*Q+Q2~Q1;Q+Q2
Both are programs that take input from STDIN and output the numbers on newlines. Just golfed both answers while using the same looping primitive for now. This could probably be improved quite a bit.
Edit: Added better condition checking stolen from @isaacg. Seems like using filter is still shorter than using a while loop for the prime pairs.
Collatz Sequence:
QWtQ=Q@,/Q2h*Q3QQ
Twin Primes:
=Qf!ttP*T+T2hQQ+Q2
Some ideas thanks to FryAmTheEggman.
<ussC,cG\_GUQ*zQQ
Input should be given with the string on the first line, and the length on the second, on STDIN. For example:
abc____
50
Explanation:
Implicit:
z = input() z is the string.
Q = eval(input()) Q is the length.
< Q First Q characters of
u UQ*zQ Reduce, with an initial value of z repeated Q times,
on the list range(len(Q)).
Since the reduce function doesn't use the sequence variable H
this function amounts to applying the inner code Q times to
the initial value, where the working variable is G.
ss Sum from list of tuples of strings, to tuple of strings,
to string.
C, Zip together
cG\_ G split on underscores
G with G.
This inserts a character of G between every underscore
separated group of G, which amounts to replacing the
underscores with characters of G, after summation.
n,s=input()
S='';c=0
for x in s*n:b=x=='_';S+=S[c:c+b]or x;c+=b
print S[:n]
This expects input like (30,"ab_c_").
In Python, strings don't allow assignment. So, replacing the blanks with the desired character is hard. One can get around this by converting to a list and back, but I found it shorter to just generate the output string from scratch, adding on the desired characters one at a time.
The output being constructed is S, which starts empty. We loop through the characters of the input s copied many times to simulate a circle. We check if it's a blank via the Boolean b. We check equality x=='_' rather than comparison because the underscore lies between capital and lowercase letters.
If the character is not a blank, we just add it onto S. If it is blank, we add the next unused letter of the output-so-far S. We track used letters by an index pointer c that starts at 0 and is incremented each time we encounter a blank.
At the end, we print the first n characters of the resulting string S.
We have to use S[c:c+b] in place of the shorter b*S[c] because the latter gives an out-of-bounds error when S starts empty and c is 0. It never matters because we're guaranteed the first character of s is non-blank, so this S[c] is never needed, but the code doesn't know it. Flipping the or to short-circuit could also solve this, but costs more characters.
A Pyth-to-Python port of isaacg's solution, which uses split and zip to perform the replacement:
n,s=input()
s*=n
exec"s=''.join(a+b for a,b in zip(s.split('_'),s));"*n
print s[:n]
It turned out longer because, suprise, named methods are long in python. But it can perhaps be improved by riffling s and s.split('_') together in a shorter way.
Yet another Fisher-Yates implementation. Is essentially the same as @Sp3000 python solution, just in pyth.
FNrlQ1KONJ@QN XQN@QK XQKJ)Q
Can probably be golfed further.
<implicit> Q=input()
FNrlQ1 For N in len(Q) to 1, only goes len Q-1 because how range implemented in pyth
KON K = random int 0-N
J@QN J=Q[N]
<space> Suppress print
XQN@QK Q[N]=Q[K]
<space> Suppress print
XQKJ Q[K]=J
) End for
Q Print Q
FkQJOhlYaY?@YtJJkIJ XYtJk;Y
This is an implementation of the incremental Fisher-Yates shuffle, mentioned second here.
r"questions tags users badges unanswered ask question"tyhgkk) (.?AHHRUaacccceeeeeeeeeeffiiilllmnnnnooooooooprrrrrrrrtttwww
Uses grc's How to guarantee uniqueness of a referrer who clicks on a link in a remote webpage("Request.UserHostAddress" not working correctly)?, which unfortunately requires an extra s to work.
*d*2Z~Z1
This relies on the fact that N2 is equal to the sum of N odd numbers. Now Pyth auto prints an new line, so I have to just print Z * 2 characters in each code where Z goes from 0 to N - 1.
Code Expansion:
*d "Print d whose value is a space character"
*2Z "2 * Z times where Z's initial value is 0"
~Z1 "Increment the value of Z";
Jiz8K+lzQ%"%0*o",KuxG/G8rQ^2KJ
Run it by input from stdin like (online interpreter: https://pyth.herokuapp.com/):
111
3
and the result will be written to stdout.
This is a direct translation of:
def i(s,k):
l=int(s,8);t=len(s)+k
while k<1<<t:l^=l/8;k+=1
print'%0*o'%(t,l)
Call it like i("111", 3), and the result will be written to stdout.
Note that we expect k not being too large, since for code-golfing purpose the inner loop will run for O(2k) times.
I think we usually call this operation "xorshift" or something. If we express the input as big-endian integers, then the function f is simply:
If we apply f twice we will get:
However applying 3 times will have a different pattern:
Applying 4 times get back to the basic form:
And so on:
Note that if we choose a big-enough 2k, then (x ≫ 2k) = 0, meaning f2k(x) = x, and the inverse is trivially the identity function!
So the strategy for finding f-k(x) without calling f-1(x) at all is:
Find K such that:
Express f-k(x) = f-K + (K-k)(x) = f-K(fK-k(x)) = fK-k(x)
Thus, the result is f called K-k times
25 chars profit :p
Update 1: Used octal representation instead of binary so that we could use % formatting to save lots of bytes.
Update 2: Exploit the periodic structure of f. Retired the iterative version since the non-iterative one is shorter even without the -25 bytes bonus.
Update 3: Reduced 3 bytes from Pyth, thanks isaacg!
um?d|-lHl{sHsmg{kdH-dsHGtyQQ
Input is a list of lists like [[1,2], [2,3], [1,3], [1,2,3,4]]. Try it online: Pyth Compiler/Executor
um?d|-lHl{sHsmg{kdH-dsHGtyQQ
u Q G = input array
u tyQQ For each H in powerset(input):
m G G = [ ... for d in G]
?d -dsH [d if ... else d-sum(H) for d in G]
-lHl{sH len(H)-len(set(sum(H)))!=0
| or
smg{kdH sum(d is subset of k for k in H)>0
lfq_TTCmmSm<>dbhkldldQ
Input are two strings like "abc","def". Try it online: Pyth Compiler/Executor
Quite some complicated code. But I'll start easy.
First we want to create all substrings of length k of the string d.
Sm<>dbhkld
m ld apply a function ... to all elements b
in the list [0, 1, 2, ..., len(d)-1]
>db take the string d starting from the position b
< hk but only hk = k + 1 characters
S Sort the resulting list.
For the string "acbde" and k = 3 this results in ['abc', 'bde', 'cbd', 'de', 'e']. Notice, that 'de' and 'e' are part of this list. This will be quite important in a bit.
I want the substrings for each k, one map again.
mSm<>dbhkldld
m ld apply a function (create all substrings of lenght k) to
all elements k in the list [0, 1, 2, ..., len(d)-1]
For the string "acbd" this results in [['a', 'b', 'c', 'd'], ['ac', 'bd', 'cb', 'd'], ['acb', 'bd', 'cbd', 'd'], ['acbd', 'bd', 'cbd', 'd']].
I want this for both strings, another map.
mmSm<>dbhkldldQ
m Q apply the function (see above) for all d in input()
[[['a', 'b', 'c'], ['ab', 'bc', 'c'], ['abc', 'bc', 'c']], [['d', 'e', 'f'], ['de', 'ef', 'f'], ['def', 'ef', 'f']]] for the input "abc","def", and after a
zip C, this looks [(['a', 'b', 'c'], ['d', 'e', 'f']), (['ab', 'bc', 'c'], ['de', 'ef', 'f']), (['abc', 'bc', 'c'], ['def', 'ef', 'f'])].
Now comes the exciting part: We are of course only interest in the ks, where the substrings of both words are the same.
lfq_TTCmmSm<>dbhkldldQ
f I filter the list for elements T, where
q_TT reversed(T) == T
(basically T[0] == T[1])
l print the lenght of the resulting list.
(= the number of times, where the substrings of length k
of string 1 are equal to the substrings of
length k of string 2)
Since we also have the suffixes of length < k in Ts, this also checks, if the suffixes are equal.
The only thing, which I don't check is, if the prefixes are equal. But as it turns out, this isn't necessary. Lemma 2.3 (4<=>5) of the linked paper says: If the substrings of length k are the same, than pref_{k-1}(string 1) = pref_{k-1}(string 2) is equivalent to suff_{k-1}(string 1) = suff_{k-1}(string 2). Since the suffixes are equal, the prefixes are also equal.
Su{smmu*/N^T/PdTv+`T`/PdTkdyft/PdT{PdGU^T3]Q
Fixed the multiple ^ bug. For instance:
Input: 58564
Output: [230, 456, 1311, 2508, 9975, 12768, 13794, 20748, 58564, 114114, 322102]
Note that this code relies on a couple of bugfixes to the official compiler that were pushed after the question was asked. However, it does not use any new language features.
FbQVbjd++*]0Z*b]b*]0--sQbZ)~Zb
A pretty naive program, takes the input on stdin. This can probably be golfed more ;)
Thanks @Jakube for pointing out a wasted char
Ju+G*]GHQYFNJjdmsqdNJ
Input is a list of integers, like [3, 1, 1, 2]. Try it online: Pyth Compiler/Executor
Uses a quite similar idea as randomra's J code. The first part of the code Ju+G*]GHQY generates n parts of similar things. For the example input [3, 1, 1, 2] the result looks like this:
[
[],
[],
[],
[[], [], []],
[[], [], [], [[], [], []]],
[[], [], [], [[], [], []], [[], [], [], [[], [], []]]],
[[], [], [], [[], [], []], [[], [], [], [[], [], []]]]
]
First three identical elements, than one element , then one element again and at the end two identical elements.
Ju+G*]GHQY
u QY reduce the input Q, start with empty list G=[]
for each H in input, replace the value of G by:
+G*]GH G+[G]*H
J store the result in J
The second part of the code is comparing the elements of the Cartesian product and printing it.
FNJjdmsqdNJ
FNJ for N in J:
m J map each element d of J to
qdN the boolean value of d == N
s and convert it to an integer (0 = False, 1 = True)
jd print the resulting list seperated by d (=space)
Just the python solution I had before but super-quoted in Pyth to save on the imports and loops. Will be trying to golf more.
$r=random.random$M|$random.seed(G)$m$(-2*math.log(r()))**.5*math.cos(2*math.pi*r())$H
Very simple method, uses Box-Mueller transform. PRNG is python's Mersenne-Twister, with an enormous period and allows seeding.
$ $ super quote (literal python)
... python golfing tricks
M def g(G, H):
| or (disregard the seed which returns None)
$ $ super quote
... seed python PRNG
m H map on range(0,H)
$ $
... Box-Mueller in Python
+_32Ce"c'MBBnx.Hq7:nN(+<#j&7yVE&M!Mwp,|4Qh)|/l-#%@wFw?*B(Yi[Ahpt+$++Egm{Q5TPK+mT`#)5Faetn'gpn#
The above code will obviously be messed up because SE removes control characters, so find the actual code here
The logic is simple, the string is the character representation of each number, except for the first 3 which are used by the conversion logic and some quotes and newlines which I replaced with dummy characters.
I will try to increase the score here.
L+\cPPb
Explanation:
L def y(b):return
+\c "c" +
PPb b[:-1][:-1]
Try this:
L+\cPPb
y"stdio.h
on the online Pyth Compiler/Executor
If full programs were allowed:
+\cPPQ
I would be surprised if any golfing languages were appropriate for genetic programming. Pyth, at least, is very unlikely to form a valid program with random bytes, and I believe the same is true of most golfing languages. This, if nothing else, probably invalidates them as genetic programming languages.
Mhosm^-*Ghded2C,HNfqsTGmms+*G@Hb}bklHyUH
This defines a function g with 2 parameters. You can call it like Mhosm^-*Ghded2C,HNfqsTGmms+*G@Hb}bklHyUHg5 [0.1 0.2 0.3 0.4.
Try it online: Pyth Compiler/Executor
mms+*G@Hb}bklHyUH (G is S, H is the list of weights)
m yUH map each subset k of [0, 1, ..., len(H)-1] to:
m lH map each element b of [0, 1, ..., len(H)-1] to:
*G@Hb G*H[b]
+ }bk + b in k
s floor(_)
This creates all possible solutions L, where L[i] = floor(S*W[i]) or L[i] = floor(S*W[i]+1). For instance, the input 4 [0.3 0.4 0.3 creates [[1, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 2], [2, 2, 1], [2, 1, 2], [1, 2, 2], [2, 2, 2]].
fqsTG...
f ... only use the solutions, where
qsTG sum(solution) == G
Only [[2, 1, 1], [1, 2, 1], [1, 1, 2]] remain.
Mhosm^-*Ghded2C,HN
o order the solutions by
s the sum of
m C,HN map each element d of zip(H, solution) to
^-*Ghded2 (G*d[0] - d[1])^2
h use the first element (minimum)
M define a function g(G,H): return _
n=input()
L=range(-1,n*n+9,2)
i=2
while L[i:]:L=sorted(set(L)-set(L[L[i]::L[i]]));i+=1
print L[1:n+1]
Just a straightforward implementation.
J%2r1h^Q2VJI>JhN=J-J%@JhN+2J;<JQ
Similar to the approach above, but things are 0-indexed rather than 1-indexed. Try it online.
Thanks to @Jakube for pointing out a byte saving.
<u-G%@GhH+0GQ%2r1^hQ2Q
Try it online: Pyth Compiler/Executor
<u-G%@GhH+0GQ%2r1^hQ2Q Q = input()
%2r1^hQ2 create the list [1, 2, ..., (Q+1)^2-1][::2]
u Q%2r1^hQ2 G = [1, 2, ..., (Q+1)^2-1][::2]
modify G for each H in [0, 1, 2, ..., Q]:
-G%:GhH+0G G = G - ([0] + G)[::G[H+1]]
(minus is remove in Pyth)
< Q print the first Q elements of the resulting list
The reduce actually calculates more than Q lucky numbers (the remove command is called Q+1 times, Q-1 should be enough).
Is similar to CJam solution. Outputs is PGM format, save output as foo.pgm and view here. Edited it to make it conform to PGM specs so that lines are less than 70 chars long, in fact they are only one pixel long.
K50"P2"*KKKKVKjbS*UKK
Generates: 
Is fifty fifty by fifty squares. Goes from black to 49/50 of the way to white.
K50 K=50
"P2" Prints P2 or pgm header magic #
*KK Prints the length: 50*50
K Prints width: 50
K Prints value of white: 50
V K Do 50 times to make height of square 50
j joins by
b linebreaks
S Sort to bring out make each shade consecutive
* K Times 50 to make length 50
UK Unary range 50 (0-49)
f=lambda n:sorted(set(sum(map(f,{n-x+n/x for x in range(2,n)if(n<x*x)>n%x}),[n])))
Since (a-1)*(b+1)+1 == a*b-(b-a) and b >= a, descendants are always less than or equal to the original number. So we can just start with the initial number and keep generating strictly smaller descendants until there are none left.
The condition (n<x*x)>n%x checks two things in one - that n<x*x and n%x == 0.
(Thanks to @xnor for taking 3 bytes off the base case)
LS{s+]]bmydm+-bk/bkf><b*TT%bTr2b
Direct translation of the above, except for the fact that Pyth seems to choke when trying to sum (s) on an empty list.
This defines a function y which can be called by appending y<number> at the end, like so (try it online):
LS{s+]]bmydm+-bk/bkf><b*TT%bTr2by60
{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}
Also using the same method, with a few modifications. I wanted to try CJam for comparison, but unfortunately I'm much worse at CJam than I am at Pyth/Python, so there's probably a lot of room for improvement.
The above is a block (basically CJam's version of unnamed functions) that takes in an int and returns a list. You can test it like so (try it online):
{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}:G; 60 Gp
b=input()
l=b.index('\n')+1
print''.join(('\n.'+('-'+v)[all([v>=b[j]for j in i-l,i-1,i+l,i+1if 0<=j<len(b)])])[('\n0'+v).index(v)]for i,v in enumerate(b))
Input has to be of the form "00001\n00000\n00000\n10000".
Converting a string to a 2D-matrix is quite lengthy in Python. So I keep the original string format. I enumerate over the input, i is the index, v is the char (Finally enumerate saved bytes in a golf solution!!). For each pair (i,v) I compute the correct char of output, and join them. How do I choose the correct output char? If v == '\n', the output char is \n, it v == '0', than the output char is '.'. Otherwise I test the 4 neighbors of v, which are b[i-b.index('\n')-1] (above), b[i-1] (left, b[i+1] (right) and b[i+b.index('\n')+1] (under), if they are <= v and choose the char '-' or v. Here I'm comparing chars not the numbers, but it works quite fine, because the ascii values are in the correct order. Also there are no problems, if b[i-1] or b[i+1] equal '\n', because ord('\n') = 10.
JhxQbVQK@QN~k@++b\.?\-f&&gT0<TlQ<K@QT[tNhN-NJ+NJ)Kx+b\0K)k
More or less a translation of the Python script. Quite ugly ;-)
Try it online: Pyth Compiler/Executor Same input format as the Python solution.
JhxQb Q = input()
xQb Q.index('\n')
h +1
J store in J
VQK@QN~k.....)k k is initialized as empty string
VQ ) for N in [0, 1, 2, ..., len(Q)-1]:
K@QN K = Q[n]
~k k += ... (a char, computed in the next paragraph)
) end for
k print k
@...x+b\0K ... is a char of len 3 (is constructed below)
+b\0 the string "\n0"
x K find Q[d] in this string and return index, if not found -1
@... lookup in string at the computed position (this is done mod 3 automatically!)
++b\.?\-f&&gT0<TlQ<K@QT[tNhN-NJ+NJ)K not to the string
[tNhN-NJ+NJ) the list [d-1, d+1, d-J, d+j]
f filter the list for indices T which
gT0 T >= 0
& and
<TlQ T < len(Q)
& and
<K@QT Q[d] < Q[T]
?\- K use "-" if len(filter) > 0 else Q[d]
this creates the third char
++b\. "\n" + "." + third char
Mlf!sm}_dHfq2lYyTfqSZUZ^UGG
Defines a 2 input function, g. First input is the number of vertices, second is the list of directed edges.
To test:
Code:
Mlf!sm}_dHfq2lYyTfqSZUZ^UGGghQeQ
Input:
6, [ [0, 1], [0, 2], [0, 3], [0, 5], [1, 2], [1, 4], [3, 2], [5, 3] ]
jb_u+G+*leGd*HNu+N+^3hTNUQ]1]k
This is a program that takes input from STDIN and uses grc's method of finding the Cantor set. Uses the " character to display the curve.
Explanation:
I will explain the code in two parts, first, the cantor set generation:
u+N+^3hTNUQ]1
u UQ]1 : reduce( ... , over range(input), starting with [1])
+N : lambda N,T: N + ...
+^3hTN : 3 ** (T+1) + N (int + list in pyth is interpreted as [int] + list)
And the output formatting:
jb_u+G+*leGd*HN ]k
jb_ : "\n".join(reversed(...)
u ]k : reduce(lambda G,H: ... , over cantor set, starting with [""])
+G+*leGd : G + len(G[-1]) * " " + ...
*HN : H * '"'
Note that in pyth N = '"' by default.
Uses pyth's prime factorization function to see if # is prime. Uses !tPT trick suggested to me at my answer for primes under million problem.
<f!tPTr2^T6Q
Since the filter only works for primes under n and not first n, I just looked up the inverse of pi(x) for 10,000 and got 104,000 so I use primes under 10⁶ and get first n. This doesn't actually run, so you should test by replacing ^T6 with ^T3 and restrict n to under 1000. Input from stdin and output to stdout.
< Q Slice first n
f r2^T6 filter on range 2->10⁶
! Logical not (gives true if tail is empty)
t Tail (all but first, so gives empty if prime fact is len 1)
PT Prime factorization of filter var (len 1 if num is prime)
Learned about a lot of new languages from this challenge, which I will probably using in golfs. A site that really helped me find these languages was http://www.tutorialspoint.com/codingground.htm. Just don't expect my programs to run in it, it requires a full program format, and I just used it to learn about the languages and used other REPLs to run them.
Pyth doesn't have a range by step function unlike python, so I used regular range and chopped (thanks @Jakube) used mod operator on it.
M%Hr+Z+Z+Z+Z+Z+Z+Z+Z+Z1hG
Defines a function g(until, step)
M Define g(G, H)
%H Every H elements
r1hG Range 1->G+1
This is my first golfscript program. Probably not the best way to do it.
0000000000000000;\),1>\%p
\ swap
) increment
, range
1> all but first element
\ swap
% take every top of stack elements
p print array
Uses the seq command which has INCREMENT param.
seq 000000000000001 $2 $1
Self-explanatory code.
lambda a,b:range(1,a+1,b)
Again, self-explanatory.
r[a_,b_]:=Range[0001,a,b]
Uses Matlab's range notation and defines an anonymous function.
@(a,b)000000000000001:b:a
Like Coffeescript it is a JS derivative. Has cool range syntax. Arrow notation again.
rr=((((a,b)->[1 to a by b])))
Learned erlang just for this. Pretty self explanatory, defines function r.
r(a,b)->lists:seq(01,a,b)
Kind of obvious, F#'s function definitions are like variables.
let r a b=seq{0000001..b..a}
Haskell's range notation has you give the first two in the range for the increment, and not an explicit increment.
r a b=[000000000001,a+1..b]
Very cool language, even if function definitions are a little verbose.
function(a,b)seq(001,a,b)
Awesome language, will be using for golfing in the future.
r(a,b)=[000000000001:b:a]
Like my old golfscript answer except with input parsing and padding.
00000000000000;q~\),1>\%p
Took this challenge as an opportunity to check out some new languages (CJam, Burlesque, zsh, gs2). First time I've worked with these languages.
The method behind creating the output is different in nearly each language. Only the CJam and the gs2 method are identical. The 4 methods are, creating a range [1, 100] and slice it with modulo (CJam and gs2), creating the range [1, ..., 100] and filter for elements that are 1 mod 7 (Pyth), creating the range [1, ..., 100], divide it into chunks of len 7 and use the first element of each chunk (Burlesque), and creating the sequence directly (zsh).
I tried to design each program in such a way, that it looks golfed to someone, who is not familiar with the language.
edit 1: added Burlesque, previous 2 languages with 10 characters = 0.2
edit 2: added gs2, previous 3 languages with 11 characters = 0.2727
edit 3: added zsh, previous 4 languages with 11 characters = 0.3636
q~\1+,0-\%p
Test it online with the input 100 7.
q~ push the evaluated input (100 7)
\ swap (7 100)
1 push 1 (7 100 1)
+ add last to elements (7 101)
, create the range (7, [0, 1, ..., 100])
0 push 0 (7, [0, 1, ..., 100], 0)
- delete 0 from the range (7, [1, 2, ..., 100])
\ swap ([1, 2, ..., 100], 7)
% use every 7th entry ([1, 8, ..., 99])
p print pretty
jrojcoq-]m[
Beside zsh, this is the only golfed program. Burlesque is quite awesome, it has a very large range of different functions, like ro. Sadly there's nothing like the Python [::a] slicing operator.
There is no online interpreter, but you can get Burlesque here. Since Burlesque doesn't support functions or IO, you have to put the values onto the stack first, like 100 7 jrojcoq-]m[
j Swap (7 100)
ro Range (7 {1 2 ... 100})
j Swap ({1 2 ... 100} 7)
co ChunksOf ({{1 2 .. 7} {8 ... 14} ... {99 100}})
q Create Block ({{1 2 .. 7} {8 ... 14} ... {99 100}} {})
-] head (first element) ({{1 2 .. 7} {8 ... 14} ... {99 100}} {-]})
m[ map the chunks to the head-block
read-nums dup head inc range tail swap reverse head mod unlines
Yep, this is only 11 chars. In gs2 each byte has a different meaning. But because writing in bytes is quite hard and not any fun, you can also write in mnemonics, which you can compile to the actual gs2 code. The gs2 code, which gets executed is
W@!'."B !4+
or as hex-dump:
57 40 21 27 2e 22 42 20 21 34 2b
Fun fact: I didn't write in mnemonics, but directly the numbers of the hex-dump.
You can test it by downloading the compiler. Compile the mnemonics file with python gs2c.py < mnemonics.txt > compiled or simply copy W@!'."B !4+ to a file named compiled and then execute it with echo 100 7 | python gs2.py compiled.
The mnemonics is pretty self explainable, but here's what's going on in the stack.
57 40 21 27 2e 22 42 20 21 34 2b
57 read-nums ([100 7])
40 dup ([100 7] [100 7])
21 head ([100 7] 100)
27 inc ([100 7] 101)
2e range ([100 7] [0 1 ... 100])
22 tail ([100 7] [1 2 ... 100])
42 swap ([1 2 ... 100] [100 7])
20 reverse ([1 2 ... 100] [7 100])
21 head ([1 2 ... 100] 7)
34 mod ([1 8 ... 99])
2b unlines ('1\n8\n...\n99')
everything on the stack gets printed
Btw, 8 bytes are possible, maybe even less.
edit: I forked gs2, slightly manipulated a command and made a pull request, which is already merged. So now the task can be done with 6 bytes: read-nums extract-array swap range1 mod unlines, which translates to 57 0e 42 2f 34 2b, which is even better than the optimal pyth.
f() seq 1 $2 $1
This defines a function f, that creates the a sequence. To use it on Windows, I installed the babun shell, where you can simply type these commands. Simply write f() seq 1 $2 $1 and in the next line f 100 7.
First I tried to write this in Bash, but there you have to write () around the code block, like f() ( seq 1 $2 $1 ). So I switched to zsh instead.
fq1%TeQUhhQ
This really hurts, since of course I see the obvious 7 byte golf. You can test it online with the input 100, 7.
Q = input()
UhhQ the range [0, 1, ..., Q[0]]
f filtered (only use those elements T, which satisfy the equation
q1%TeQ 1 == T % Q[1]
Uses http://stackoverflow.com/a/2163753/4230423 except that a)No cache since Pyth automatically memoizes, b)Prints each instead of appending to list, and c) is translated to Pyth.
M?smg-Gddr1h?H<HGGG1Akd,QOgQQWQFNr1h?k<kQQKg-QNNI<dKB=d-dK)N=kN=Q-QN
I'll post an explanation of this when I have the time, but here is the corresponding python code:
g=lambda G,H: sum(map(lambda d:g(G-d, d), range(1, (H if H<G else G) + 1))) if G else 1
Q=input()
k,d = Q,random.randrange(g(Q, Q))
while Q:
for N in range(1, min(k, Q) + 1):
K = g(Q-N, N)
if d < K:
break
d -= K
print N
k=N
Q -= N
Edit: I finally got around to doing the explanation:
M Lambda g(G,H)
? G If G truthy
s Sum
m Map
g Recursive call
-Gdd G-d,d
r Range
1 1 to
h +1
? <HG If H<G (this does min)
H H
G Else G
1 Else 1
A Double assign
kd Vars k and d
, To vals
Q Q (evaled input)
O Randrange 0 till val
gQQ Call g(Q, Q)
WQ While Q is truthy
FN For N in
r Range
1 From one
h Till +1
?k<kQQ Min(Q,K)
Kg K=g(
-QN Q-N
N N
I<dK If d<k
B Break (implicit close paren)
=d-dk Subtracts d-=k
) Close out for loop
N Prints N
=kN Set k=N
=Q-QN Subtracts Q-=N
I noticed a pattern! ~Does happy dance~ The transform is just really just looping through the string picking every other elements. It only works on odd since otherwise it would never get half the elements. This is equivalent to rotating a 2 wide matrix.
%2*2z
Python's step slicing doesn't loop around so I repeated the string.
%2 Take every other elements
*2z Double input string
K/hlz2%K*Kz
Again no wrap-around for step-slicing.
K/hlz2 K=length of (input+1)/2
%K Every kth element
*Kz From K*the input
osjN2U^2Q
order by the sum of the base 2 representation (jN2) over the range (U) of 2 ^ Q.
(Q = eval(input())).
Jf!-`sjT^10/l`T2\9UyQ|}QJho%l`N2o^-QZ2J
... or
A version that might be against the rules: 33
ho%l`N2o^-QZ2f!-`sjT^10/l`T2\9UyQ
The rules-breaking version just echoes the number if it is cyclic.
I believe this gives the correct output for all values, if you find something in my reasoning that is flawed, please tell me ;)
This begins by generating a list of all of the cyclic numbers from 0 to twice the input. This will obviously include each cyclic number less than the input, and includes the next cyclic number. You actually only need to add 10 ^ (digits_in_input / 2) to ensure this, but doubling takes fewer characters.
The numbers are found to be cyclic by converting them into base 10 ^ (digits_in_input / 2) and then summing the digits of this number together. All 9s are then removed from this list, and so if the list is empty the number is cyclic.
If the input is a member of this list, True is printed, otherwise the list is sorted, first by (input - value) ^ 2 and then by if the number contains an even or odd number of digits (sorting evens as less). Since pyth uses stable sorts, this is equivalent to sorting by both at once. Then the first number in this list is the nearest cyclic tag number.
This algorithm is fairly naive, but I believe it catches everything. I particularly think that the sorting could be golfed a lot.
s+0m^h^-hded2 .5CmfTm*hb@kblkQ
Try it online with the input [0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1].
I convert the lists into lists of indices [2, 3, 5, 6, 7, 8] and [1, 4, 5, 6, 9] and zip them together [(2,1), (3,4), (5,5), (6,6), (7,9)]. Then I subtract the values, square them, add 1 and sum over all square roots.
CmfTm*hb@kblkQ
m Q map each list k in input() to the following list:
m lk map each value b of [0, 1, 2, ..., len(k)-1] to the value:
*hb@kb (b + 1) * k[b]
fT filter the list for positive values
C zip these two resulting lists
s+0m^h^-hded2 .5...
m ... map each pair of values d to:
^h^-hded2 .5 ((d[0] - d[1])^2 + 1)^0.5
+0 insert 0 at the front of the list
s sum
Shame that sum doesn't work for empty lists.
V21++**6/-20N5d*5?d%N5\_<\|N
A pretty straightforward solution, with the "append five spaces or five underscores" trick from @xnor's solution, but with the loop from 0 to 20, not 20 to 0.
?Y!Qu[HG)_UtQ[tQ
Which is really saying, in Python:
Q = eval(input())
if not Q:
print []
else:
print reduce(lambda G,H:[H,G], reverse(range(Q-1)), [Q-1])
?hu]+HG_UQYQY
Implicit:
Q = eval(input())
Y = []
? QY If Q = 0, print Y
h else, print the first element of
u _UQY the reduce, where Y is the initial value, over the list
reversed(range(Q))
]+HG The reduce function: The list containing H prepended onto G.
The new number is inserted into the accumulated list,
then the resultant list is wrapped in another list.
!sm>vzs+0<QdhlQ
Try it online with the input
-5
[4, -3, 6]
Implicit: z and Q read 2 line from input
z = "-5" (this is not evaluated, it's a string)
Q = [4, -3, 6] (this is a list though)
m hlQ map each number d in [0, 1, 2, ..., len(Q)] to:
>vz the boolean value of: evaluated z >
s+0<Qd the sum of the first d elements in Q
!s print the boolen value of: 1 > sum(...)
And again the stupid s function wastes two bytes. I think I'm gonna report this as a bug to the Pyth repo.
Thanks to isaacg for one byte save (>1 to !) and for changing the implementation of s in the Pyth repo. Now the following code is possible (but of course not valid for this challenge).
!sm>vzs<QdhlQ
I've never really golfed in Pyth, maybe written a program or two. This is basically @steveverrill's solution translated to Pyth. Improvement suggestions are welcome.
Update: added 1 byte to make scrambles also start with U. Maybe the C solution is relying on undefined behavior to make it work...
=YO6V25JZK1WK=GO15=Z/+3G3=Kq9*ZJ)~YZpd+@"URFDLB"%Y6?@"'2"%G3>2%G3k
I believe this should be done with less assignments, but that would require me to modify the algorithm a lot. (Well, might try.)
Here's an explanation based on the C code:
=YO6 s = random.choice(range(6))
V25 for i in range(25):
JZ n = m
K1 t = 1
WK while t:
=GO15 r = random.choice(range(15))
=Z/+3G3 m = (r + 3) / 3
=Kq9*ZJ t = 9 == m * n
)
~YZ s += m
pd print(..., end = " ")
+ ... + ...
@"URFDLB"%Y6 "URFDLB"[s % 6]
?@"'2"%G3>2%G3k "'2"[G % 3] if 2 > G % 3 else ""
Basically a translation of xnor's Python answer. I'm still not great with Pyth, so improvement suggestions are welcome.
Defines a function y to return a list of lists of integers.
L?]]1<b2smm++*kdb*k_dy-b1,1_1
Update: Saved 2 bytes thanks to FryAmTheEggman.
Explanation:
L define a function y with argument b that returns
?*]]1<b2 [[1]] if b < 2 else
s sum(
m map(lambda d:
m map(lambda k:
++*kdb*k_d k*d + [b] + k*-d
y-b1 , y(b - 1))
,1_1) , (1, -1))
usCm,+dH+HdGr2hQ]]1
This is a full program that takes input from stdin.
This works in a similar way to xnor's solution, but generates the values a bit out of order, so they must be reordered. What happens at each level is that each previous list of values has the new value added to the end and to the beginning and these are each wrapped in a 2-tuple which are wrapped together in a list. For example, the first step does this:
[[1]]
[([1,2], [2,1])]
Then, this list of tuples is zipped (and then summed to remove the outermost list). In the first case this just gives the unwrapped value from above, as there is only one value in the list.
Steps showing 2->3:
([1,2], [2,1])
[([1,2,3],[3,1,2]),([2,1,3],[3,2,1])]
([1,2,3],[2,1,3],[3,1,2],[3,2,1])