Consejos para jugar golf en J

33

GolfScript se sale con la suya con demasiada frecuencia y creo que un depósito de consejos prácticos para jugar golf en J podría ayudar en la lucha contra el imperio del mal. ¿Qué consejos tienes para acortar este lenguaje ya conciso?

Para aquellos que quieran aprender J, el lugar obvio para comenzar es el sitio jsoftware y particularmente el vocabulario , la guía Learning J y la guía J for C para programadores .

Gareth
fuente
1
Hay algo divertido sobre leer GolfScript gets its own way far too oftenen 2019.
Cadena no relacionada

Respuestas:

14

Hay una serie de sutilezas para exprimir los últimos caracteres en J. Para lo siguiente, suponga que cada letra mayúscula es un verbo primitivo (es decir, estoy eliminando los espacios que de otro modo serían necesarios para delimitar nombres).

  • Cuando tienes un tren en marcha, y necesitas aplicar una función encima de otra a mitad de camino, ([:FLGR)y (LF@:GR)tener el mismo número de caracteres, pero (LF@GR)guarda uno. Si el marco de G es mayor o igual que el rango de mónada de F, esta es una transformación válida. Notablemente, todos los trenes tienen un rango infinito, al igual que la , ,. ,: ~. /: \: [ ]mayoría de los usos de #y |..

  • Si tiene que elegir cadenas de una lista, y estas cadenas no tienen espacios, use >i{ab`cd`ef. Está sucio, pero guarda caracteres para cada nueva cadena con la que tiene que lidiar, a menos que solo extraiga caracteres individuales, e incluso entonces la lista de caracteres debe ser de longitud 4 para ser más corta. Lo que sucede es que los nombres indefinidos se tratan como referencias a los verbos, y cuando tomas los gerundios de esos verbos obtienes una cadena encuadrada del nombre. Cualquier nombre que ya esté definido como que tenga tipo de sustantivo, adverbio o conjunción no se puede usar de esta manera, porque esos nombres se resuelven antes y `pueden tenerlos.

  • Si tiene la suerte de tener una expresión con la que trabajar y no solo un verbo tácito, casi siempre vale la pena asignar los bits que reutiliza a las variables, ya sean sustantivos, verbos o adverbios. Los padres a veces se pagan a sí mismos al ajustarse directamente a donde tenía espacios antes, y la mayoría de esas definiciones valen la pena si se reutilizan una vez más.

  • Las conjunciones como (FGH)^:(u`v`w)se pueden reescribir u`v`w(FGH^:). Esto funciona para cualquier longitud de tren, incluso 1, aunque solo guarda algo si este truco elimina a los padres del argumento correcto. Este truco solo funciona cuando precarga el operando izquierdo. (¿No tiene idea de lo que acaba de pasar? Busque 'adverbios tácitos' y estudie la sección Análisis y ejecución del Diccionario J).

  • ¡No uses a.&i., usa u:! {&a.y 3&u:son equivalentes en longitud, sin embargo, y el primero podría ser más útil en una conjunción (dependiendo de la conjunción).

  • Cosas como (2%~F)y (F%2:)son equivalentes en longitud. Esto es útil porque a veces, dependiendo de cómo se vea el resto de tu tren, puedes reestructurarlo con @trucos como están escritos en el primer punto, para salvar a algunos personajes desesperados. (Y, por supuesto, si Fes así ]y el tren es una mónada, usando %&2salva un char, duh).

  • Trenes en forma de gancho con ]o [como el verbo más a la izquierda, p (]FGH).

    • ]le permite romper una aplicación diádica y usar solo el argumento correcto. (Cambia a la izquierda con (]FGH)~una penalización de al menos 1 personaje, tal vez más). ¡Salva un char (FGH)@], y es muy útil en gerundios!
    • [en un gancho aplicado de forma monádica le permite hacer algo por los efectos secundarios en el lado derecho, luego devolver el argumento nuevamente. El uso más común es con 1!:2, posiblemente con formato de basura.
  • I / O es una mierda. Acelere el proceso haciendo bucles de todo lo que pueda. 1!:1tiene rango 0, y ambos 1!:2 3tienen rango _ 0, por ejemplo, así que utilícelo haciendo matrices de 1s y corra 1!:1directamente sobre ellos. Tenga en cuenta que ".también tiene rango 1, por lo que generalmente puede colocarlo directamente después 1!:1, y no tener que adjuntarlo a través de @travesuras de rango.

  • No es fácil encontrar lugares para colocar esto, pero ::puede ser útil.

    • ::]^:_es una combinación particularmente poderosa, por ejemplo, que te permite hacer algo peligroso hasta que ya no puedas hacerlo. (Sujeto a las ^:_advertencias habituales como un bucle).

    • Esto también le permite usar {en listas que no tienen el índice deseado, porque arroja un error de dominio cuando eso sucede. Útil para, por ejemplo, tomar el encabezado de una lista solo si existe (intente usar ::]para devolver la lista vacía, o ::_1:para devolver un código de error, y así sucesivamente).

  • ]`($:@u)@.vgeneralmente se puede hacer más corto que u^:v^:_, especialmente en las definiciones de uy con las vque se puede jugar. Un caso similar es válido para el condicional como u^:(1-v)vs ]`[email protected]. Considere sus opciones, especialmente cuando tiene muchos verbos nombrados flotando. También es un poco más flexible, pero recuerde, si lo usa $:, hay una profundidad de recursión con la que es fácil toparse. (¿Suele ser algo así como 1800 iteraciones?)

Algoritmo de tiburón
fuente
El truco adverso es realmente genial.
FUZxxl
"salva a algunos personajes desesperados" Cuando estudias iluminado, ¡todo parece un epíteto transferido! :)
Soham Chowdhury
1
"usando %&2salva un char, duh". ¡Y -:salva a otro!
Lynn
11

Lo más importante al jugar golf en J es no solo entender el problema, sino reducirlo a una serie de transformaciones de matriz. Debe comprender esta forma de pensar para tener éxito con el código J.

Por ejemplo, un desafío reciente pidió resolver el mayor problema de subarreglos . El algoritmo estándar para resolver este problema es el algoritmo de Kadane que tiene la siguiente descripción informal:

Ir a través de la matriz y en cada posición y encontrar la suma del subarreglo más grande que termina aquí, que es el máximo de 0 o el valor en el índice actual más la suma del subarreglo más grande que termina en la posición anterior. Calcule el máximo de estas submatrices a medida que avanza para encontrar la submatriz más grande de toda la matriz.

Una traducción al código imperativo es sencilla:

  1. deje que A sea la matriz de entrada.
  2. hmi ← 0.
  3. si i ≥ len (A) devuelve m .
  4. h ← max (0, h + A [ i ]).
  5. m ← max ( m , h ).
  6. ii + 1.
  7. ir a 3.

Este algoritmo parece complicado para J de un vistazo, ya que hay un ciclo explícito que al principio no parece una reducción. Si se da cuenta de lo que está haciendo el algoritmo, puede desenredar los pasos individuales y ver que realmente realiza dos operaciones de matriz simples:

  1. Escanee la matriz para calcular las longitudes de las submatrices más grandes que terminan en cada índice.
  2. Reduzca estas longitudes con la función max para encontrar el máximo.

Ahora estos dos pasos son muy fáciles de implementar en J. Aquí hay una traducción:

  1. (0 >. +)/\. y , 0- Este paso opera desde el otro extremo de la matriz para adaptarse mejor al paradigma de J. 0 >. +es tácito 0 >. x + y.
  2. >./ y

En conjunto, obtenemos una implementación muy concisa del algoritmo:

>./ (0 >. +)/\. y , 0

Si aprende esta forma de abordar la implementación de algoritmos, sus soluciones serán tan claras como este código.

Aquí hay algunos trucos que acumulé con el tiempo. Esta lista se ampliará a medida que obtenga más conocimiento en J golf.

  • Aprende el diccionario. Contiene muchos verbos realmente oscuros que no tienen ningún sentido hasta que veas lo útiles que son. Por ejemplo, lo monádico =es extraño al principio, pero es muy útil en los desafíos de arte ASCII.
  • Use dyadic &en contextos tácitos cuando desee una conjunción de poder. El vocabulario sugiere u@[&0como un reemplazo tácito 4 : 'u^:x yy yo también.
  • En muchos casos, puede evitar una [:o @:en una secuencia como u@vsi eligiera una variante uque tenga un argumento izquierdo. Por ejemplo, para descartar el primer elemento del resultado de v, use en 1}.vlugar de [:}.vsi }.@vno es posible por alguna razón.
  • ] va menudo es más corto que v@]si desea usar monádico ven un contexto diádico. Esto resulta útil especialmente cuando se vtrata de un largo tren de verbos.
  • A veces puedes escribir en m (n v w) ylugar de (n v m&w) y. Esto puede hacer posible evitar espacios y paréntesis.
  • #\en lugar de >:@i.@#.
  • u &. vEs útil cuando vtiene un anverso. Cuando no, es posible que desee utilizar [: vinv u & vo en su u & (v :. vinv)lugar.
  • Comprender el rango y cómo usarlo. Intenta jugar con la conjunción de rango hasta que obtengas algo que encaje. Ayuda a comprender cómo el rango influye en su código.
  • ^:_ es extremadamente útil para algoritmos en los que desea alcanzar la convergencia, como un relleno de inundación o simulaciones.
  • Conoce tu biblioteca estándar. Contiene funciones muy útiles que le ahorran toneladas de caracteres.
  • El copulæ =.y =:se puede incrustar en cualquier parte de una frase. Use esto para hacer frases donde la notación tácita no sea suficiente.
  • Use ,reducciones monádicas en lugar de múltiples cuando reduzca arreglos multidimensionales.
  • Comprenda qué frases admite el código especial cuando el desafío impone límites de tiempo de ejecución. Algunas cosas útiles operan en O ( n ) en lugar de O ( n 2 ) de forma contraintuitiva.
  • Las cajas son útiles para los árboles.
FUZxxl
fuente
¿Es J lo suficientemente inteligente como para ejecutar su solución de submatriz máxima en O (n) almacenando en caché los cálculos reutilizados, o hará lo sencillo y lo ejecutará en O (n ^ 2)?
Jonás
@ Jonás, creo que se ejecuta en tiempo cuadrático.
FUZxxl
10

Tenga cuidado con el uso de bucles.

Mientras que J ha estructuras de bucle ( for. do. end., while. do. end.y variaciones), si usted se encuentra usarlos hay una posibilidad de que su algoritmo no está jugando al golf fortalezas de J y que hay un ahorro de caracteres que se harán.

^:La conjunción de poder es tu amigo. Para ejecutar un verbo xveces:

verb^:x

Si necesita el resultado de cada iteración en una lista:

verb^:(i.x)

También puedes usar ^:para ejecutar un verbo condicionalmente:

  +:^:(3<])"0[ 1 2 3 4 5 6
1 2 3 8 10 12

Duplique +:si ^:el elemento es mayor que 3 3<]( "0cambia el rango del verbo para que funcione un elemento a la vez).

Gareth
fuente
Los valores encuadrados actúan como el (i.x)ejemplo, f^:(<x)es decir, es equivalente a f^:(i.x).
FireFly
9

Entrada

1!:1[1 tomará una línea de entrada terminada presionando la tecla enter.

1!:1[3 tomará una serie de líneas de entrada (terminadas por Ctrl-D en mi Mac, Ctrl-C en Windows).

Si está tratando de ingresar números, el uso ".evaluará la cadena y devolverá una lista de números listos para ser manipulados. Si toma un número pero necesita operar los dígitos individualmente ".,.(gracias al comentario de Jan Dvorak por esto) o "."0dividirá la cadena en dígitos separados:

   "."0[1!:1[1
12345
1 2 3 4 5

   ".,.1!:1[1
12345
1 2 3 4 5

Si está leyendo en cadenas, la forma más corta de obtener una lista en caja de cadenas separadas es usar ;:. Esto funciona mejor para cadenas separadas por espacios:

   ;:1!:1[1
hello world
┌─────┬─────┐
│hello│world│
└─────┴─────┘
Gareth
fuente
Por curiosidad, (solo he jugado un poco con J), ¿cómo 1!:1[2funcionaría (si acaso)?
Gaffi
De lo que puedo reunir en la 1!:página (no soy un experto en J) 2 es la pantalla, por lo que la entrada desde la pantalla no tiene mucho sentido.
Gareth
Gracias por el enlace. A partir de ahí, ¿parece que 2no es válido? No tengo mi computadora J en mí para probarlo en este momento. Donde veo 2, justo debajo de las notas sobre 1!:1, es para 1!:2.
Gaffi
@Gaffi Los números de archivo para entrada y salida parecen ser secuenciales, por lo que supongo que son fijos y que 2, 4 y 5 solo aparecen debajo de la salida porque no tiene sentido intentar ingresarlos. Lo mismo ocurre al revés para 1 y 3.
Gareth
Dado que ".es rango 1-xx y ,.siempre produce una matriz 2D, ".,' ',.(puntada con espacio, deshilachado y evaluación; 8 caracteres) puede reemplazarse por solo ".,.(deshilachado y evaluación; 4 caracteres).
John Dvorak
6

Usando iteración para calcular secuencias

Típicamente, resolver un desafío de secuencia OEIS requerirá usar una de las fórmulas dadas en su página. Algunos de estos se adaptan bien para J, y otros no tanto. Las fórmulas recursivas son sencillas, sin embargo, la iteración podría no ser simple. Un patrón que comencé a usar es

(s(]f)^:[~]) n
          ]  Gets n
 s           The first value in the sequence
         ~   Commute the argument order, n is LHS and s is RHS
        [    Gets n
      ^:     Nest n times with an initial argument s
  (]f)         Compute f s
             Returns (f^n) s

donde ses el primer valor de la secuencia, fes un verbo que calculará el siguiente término dado el término anterior, y nes el índice basado en cero del término que desea calcular. Este método se basa en el hecho de que al calcular el poder de una díada, el LHS está unido a la díada para formar una nueva mónada, y esa mónada se anida en el valor inicial. La diada dada al adverbio de potencia es un gancho donde (]f)se le da el índice nen el LHS y el valor de un término en la secuencia s. El gancho se aplicará fen scomo una mónada, y luego ignorar na devolver el resultado de f s.

Biblioteca estándar

A veces, puede encontrar que J tendrá soporte para un verbo en su biblioteca estándar . Por ejemplo, la mayoría de las operaciones enteras a nivel de bits están vinculadas a nombres que son más cortos que el uso de la llamada primitiva.

AND =: (17 b.) NB. it is actually '$:/ :(17 b.)'

Fecha y hora incorporadas también están disponibles.

Rangos

Si tiene un conjunto de valores [a, b, c]y desea formar un rango basado en su producto [0, 1, 2, ..., a*b*c-1], el enfoque típico sería encontrar su producto y luego formar un rango que podría [:i.*/costar 6 bytes. Una forma más corta es ,@i.para 4 bytes, ya que i.puede formar matrices multidimensionales mientras sigue contando, y al aplanarla producirá un rango equivalente.

Imprimir continuamente

Una forma tácita de imprimir un valor y continuar usándolo sin un ciclo explícito es ([echo)para un caso monádico. echoes un verbo en la biblioteca estándar que imprime sus contenidos stdouten el mismo formato utilizado en el intérprete. El gancho luego pasa el mismo valor de entrada usando el [verbo izquierdo .

Base 10 dígitos de un entero

¡La forma estándar de adquirir los 10 dígitos básicos de un entero es lo 10#.inv]que cuesta 8 bytes, demasiado! Una alternativa es convertirlo en una cadena y analizarlo en el rango 0 "."0@":que guarda un byte, pero una forma aún mejor es ,.&.":que guarda otro byte haciendo que el costo final sea de 6 bytes en lugar de 8.

millas
fuente
5

Considere usar una definición explícita en lugar de escribir un verbo tácito; seguro 3 :'y 'cuesta 5 bytes, pero puede ahorrar mucho @, @:y de [:esa manera.

Omar
fuente
5

Algunos trucos (bastante) comunes que he visto

Estoy compartiendo algunas cosas que me han sido útiles. Básicamente, todos estos son consejos que he recibido, pero no tengo créditos para la mayoría.

Suma de una matriz de rango uno

En lugar de usar el +/@:(FGH)uso (1#.FGH). Esto significa degradar a la base 1, lo que efectivamente significa sumar una matriz. Aunque es más largo que +/, no requiere una tapa o composición, lo que a menudo lo hace mucho más corto que el uso +/.

Contando verdades finales

Si tiene una lista booleana y desea contar el número de verdades finales, use #.~. Vea aquí . La respuesta APL proporciona una buena explicación de cómo funciona esto. De acuerdo, esto solo me ha sido útil dos veces, pero pensé que lo compartiría de todos modos.

Debajo (&.)

No es un truco específico, sino solo una sugerencia general: el adverbio &. debajo a menudo conduce a soluciones elegantes y (más importante) cortas. Tenlo en cuenta cuando juegues al golf.

Muchas veces es útil para desafíos de conversión de base y otros , por ejemplo, este código que elimina el bit más significativo de un número: }.&.#:(convertir a la lista de dígitos binarios, eliminar el primer dígito, luego deshacer la conversión a una lista de dígitos binarios y convertir volver al decimal). La solución directa es dos bytes más:#.@}.@#: .

Under también es útil para desafíos en los que necesita trabajar con dígitos decimales, ya que puede usarlos u&.":. Por ejemplo, el camino corto que las millas dan para dividir en dígitos decimales se usa en:,.&.": .

Un último ejemplo es encontrar la magnitud de un vector: +/&.:*:tenga en cuenta que necesita recopilar todos los resultados de *:-square con &.:-under ya que *:-square es rango cero.

col
fuente
4

Formas más cortas de meterse con los rangos

A veces, tendrá un código como <"0 i.3 3, donde desea aplicar un verbo ven el rango r. Sin embargo, si usa un sustantivo (como 0), a menudo tendrá que incluir un espacio. Para evitar esto, puede usar otro verbo ude rango equivalente y usar u"ven su lugar. Por ejemplo, dado que +tiene rango 0 0 0, podemos usarlo en <"+lugar de <"0.

Aquí hay una tabla de todos los verbos y sus rangos (que se pueden obtener mediante el uso v b. 0):

0 0 0     > + * - % ^ | ! ? <. <: >. >: +. +: *. *: %: ^. j. o. q: r.
0 _ _     -. -: E. i: p:
1 0 1     p..
1 0 _     { A.
1 1 0     p.
1 1 1     #.
1 1 _     C.
1 _ _     ;: ". i. I.
2 _ 2     %.
_ 0 0     = < ~. ~: {: }: ?. L.
_ 1 0     #:
_ 1 _     $ # |. |: {. }. ": {::
_ _ _     , ; [ ] _: $. $: ,. ,: /: \: [: e. s: u: x: 0:

Para usar esta tabla, encuentre el rango deseado ren el lado izquierdo, luego elija un verbo apropiado vdel lado derecho. Por ejemplo, si necesito vectorizar un verbo ven profundidad 2 _ 2, entonces encuentro ese rango a la izquierda y elijo %.desde la derecha. Luego uso en v"%.lugar de v"2 _ 2.

Conor O'Brien
fuente
3

strings biblioteca: consejos de golf

La biblioteca de cadenas es muy útil para hacer cualquier cosa con la manipulación de cadenas. Claro, toma include'strings'(lo cual es muy costoso, considerando J), pero a veces puede cosechar los beneficios.

stringreplace

¿Te encuentras usando el reemplazo de cuerdas? Observe que A stringreplace Bes lo mismo queB rplc A .

De hecho, así es como rplcse implementa:

   rplc
 stringreplace~

cuts

El verbo cutsproporciona así:

cortar y en x (conjunción)
texto de cadena (el verbo corta n)
  n = _1 hasta pero sin incluir cadena
  n = 1 hasta e incluyendo cadena
  n = _2 después pero sin incluir cadena
  n = 2 después e incluyendo cadena

Entonces, realmente está cortando una cuerda.

Conor O'Brien
fuente
3

Obtener números del 0 al 4

Si hay una restricción en el uso de números en su código:

0 %_ : uno dividido por infinito.
1 #_ : ¿cuántos infinitos?
2 #_ _ : dos infinitos.
3 verb : hay un incorporado.
4 dyad : otro incorporado.

Obtener números del 10 al 35

Literales Base-Inifinity: 11 : _bb, 26 : _bqetc.

FrownyFrog
fuente
3

Programación tácita

Lo esencial

Verbo diádico

x (F G H) y == (x F y) G (x H y)
x (F G) y == x F (G y)
x ([: G H) y == G (x H y)  NB. G is called monadically

NB. Verbs are grouped from the right by units of 3.
NB. For the following, think like G, I, K are replaced by the results of (x G y) etc.
NB. and then the sentence is run as usual.
x (F G H I J K) y == x (F (G H (I J K))) y
                  == x F ((x G y) H ((x I y) J (x K y)))

NB. Using conjunctions for dyadic verb
x F@G y == F (x G y)  NB. Atop; Same as x ([: F G) y; Consider as golfing alternatives
x F&G y == (G x) F (G y)  NB. Compose; G is applied monadically to both arguments

Verbo monádico

(F G H) y == (F y) G (H y)
(G H) y == y G (H y)  NB. Note that this is different from APL
([: G H) y == G (H y)
(F G H I J K) y == (F (G H (I J K))) y
                == y F ((G y) H ((I y) J (K y)))
F@G y == F (G y)

Misceláneos

x&F y == x F y
F&y x == x F y
y F~ x == x F y
F~ y == y F y

Trucos

(F x) G (H y)

Solución tácito: (G~F)~H; dependiendo de los verbos reales, considere reorganizar los argumentos izquierdo y derecho para eliminar ~.

x ((G~F)~H) y
x (G~F)~ (H y)
(H y) (G~F) x
(H y) G~ (F x)
(F x) G (H y)

Reemplazos monádico-diádicos

>:y == 1+y
<:y == 1-~y or _1+y
+:y == 2*y
-.y == 1-y
-:y == 2%~y
*:y == 2^~y
#.y == 2#.y
#.inv y == 2#.inv y  NB. #: doesn't work this way
{.y == 0{y
{:y == _1{y
}.y == 1}.y
+/y == 1#.y
Bubbler
fuente
1
(G~F)~Hes pura bondad burbujeante!
Jonás
2

& es tu amigo, úsalo sabiamente

ves un verbo, nes un sustantivo xyy son argumentos izquierdo y derecho, respectivamente.

Mónada &: Introducir~ dentro del adverbio / cadena de conjunción

Una cadena de adverbio / conjunción se evalúa desde la izquierda. Entonces, algo así _2&+/\&.>no funcionará porque se analiza (_2&+)/\&.>mientras queramos _2&(+/\)&.>. En este caso, intercambiar la izquierda / derecha de +/\puede guardar un byte, +/\~&_2&.>ya que este se analiza como ((+/\)~)&_2&.>. Para ver por qué esto funciona:

+/\~&_2 y
is equivalent to
y +/\~ _2
is equivalent to
_2 +/\ y
is equivalent to
_2&(+/\) y

Pareja & : repetir xtiempos

¿Sabías que si le das un argumento xa la izquierda &, la función se aplica a xvecesy ? Muchos desafíos le piden que realice ciertas operacionesx tiempos de . Se puede lograr principalmente de dos maneras:

  • Use el operador de potencia ^:sin el operando correcto

Si la operación es v, entonces se v^:convierte en un tren adverbio que, cuando se le da un operando izquierdo, se convierte en un verbo monádico. Por lo tanto v, se aplica a y, xveces.

x(v^:)y
is equivalent to
(v^:x)y
  • Usa la diádica &como la conjunción más externa

Para usar esto, debe identificar un nverbo constante y un verbo diádico u, de modo que n u yo y u nsea ​​equivalente a v. Luego puedes escribir n&uo u&nresolver toda la tarea. Esta forma es más efectiva cuando la elección de la constante es obvia, por ejemplo, 3 in 3 u:(convertir caracteres a valores ASCII).

Además, u&nse prefiere un poco n&ucuando la estructura más externa de ues una conjunción o un adverbio (en cuyo caso n&udebería ser n&(u); puede hacerlo en su u~&nlugar).

Tenga en cuenta que puede colocar la diádica &en cualquier lugar de un tren para lograr la repetición de funciones arbitrarias a argumentos arbitrarios, en el mismo sentido que dinámico ^:.

Bubbler
fuente