Миссия по извлечению Лисп

19

В языках стиля Лисп список обычно определяется так:

(list 1 2 3)

Для целей этой задачи все списки будут содержать только положительные целые числа или другие списки. Мы также пропустим listключевое слово в начале, поэтому список теперь будет выглядеть так:

(1 2 3)

Мы можем получить первый элемент списка, используя car. Например:

(car (1 2 3))
==> 1

И мы можем получить исходный список с первым элементом, удаленным с помощью cdr:

(cdr (1 2 3))
==> (2 3)

Важно: cdrвсегда будет возвращать список, даже если этот список будет иметь один элемент:

(cdr (1 2))
==> (2)
(car (cdr (1 2)))
==> 2

Списки также могут быть внутри других списков:

(cdr (1 2 3 (4 5 6)))
==> (2 3 (4 5 6))

Напишите программу, которая возвращает код, который использует carи cdrвозвращает определенное целое число в списке. В коде, который возвращает ваша программа, вы можете предполагать, что список хранится в нем l, целевое целое число находится lгде-то, и что все целые числа уникальны.

Примеры:

Входные данные: (6 1 3) 3

Выход: (car (cdr (cdr l)))

Входные данные: (4 5 (1 2 (7) 9 (10 8 14))) 8

Выход: (car (cdr (car (cdr (cdr (cdr (cdr (car (cdr (cdr l))))))))))

Входные данные: (1 12 1992) 1

Выход: (car l)

абсент
источник
Можем ли мы взять ввод с первым целым числом и вторым списком?
Мартин Эндер,
@ MartinBüttner Конечно.
абсент
Как насчет (1 2 3) 16, мы вернемся ()?
coredump
@coredump Хороший вопрос. Вы можете предположить, что целевое целое число всегда будет в выражении, поэтому такой случай (1 2 3) 16никогда не будет отображаться.
Абсент
Можем ли мы получить два ввода, один для списка и один для целого числа?
Черная

Ответы:

1

CJam, 59

q"()""[]"er~{:AL>{0jA1<e_-_A(?j'l/"(car l)"@{2'dt}&*}"l"?}j

Попробуйте онлайн

Объяснение:

q                 read the input
"()""[]"er        replace parentheses with square brackets
~                 evaluate the string, pushing an array and a number
{…}j              calculate with memoized recursion using the array as the argument
                   and the number as the memozied value for argument 0
  :A              store the argument in A
  L>              practically, check if A is an array
                   if A is a (non-empty) array, compare with an empty array
                   (result 1, true)
                   if A is a number, slice the empty array from that position
                   (result [], false)
    {…}           if A is an array
      0j          get the memoized value for 0 (the number to search)
      A1<         slice A keeping only its first element
      e_          flatten array
      -           set difference - true iff the number was not in the array
      _           duplicate the result (this is the car/cdr indicator)
      A(          uncons A from left, resulting in the "cdr" followed by the "car"
      ?           choose the cdr if the number was not in the flattened first item,
                   else choose the car
      j           call the block recursively with the chosen value as the argument
      'l/         split the result around the 'l' character
      "(car l)"   push this string
      @           bring up the car/cdr indicator
      {…}&        if true (indicating cdr)
        2'dt      set the character in position 2 to 'd'
      *           join the split pieces using the resulting string as a separator
    "l"           else (if A is not an array) just push "l"
                   (we know that when we get to a number, it is the right number)
    ?             end if
aditsu
источник
10

Common Lisp, 99

Следующее 99-байтовое решение является CL-версией хорошего ответа схемы .

(defun g(l n &optional(o'l))(if(eql n l)o(and(consp l)(or(g(car l)n`(car,o))(g(cdr l)n`(cdr,o))))))

Изначально я пытался использовать positionи position-if, но он оказался не таким компактным, как хотелось бы (209 байт):

(lambda(L x &aux(p'l))(labels((f(S &aux e)(cons(or(position x S)(position-if(lambda(y)(if(consp y)(setf e(f y))))S)(return-from f()))e)))(dolist(o(print(f L))p)(dotimes(i o)(setf p`(cdr,p)))(setf p`(car,p)))))

расширенный

(lambda
  (l x &aux (p 'l))
  (labels ((f (s &aux e)
             (cons
              (or (position x s)
                  (position-if
                   (lambda (y)
                     (if (consp y)
                         (setf e (f y))))
                   s)
                  (return-from f nil))
              e)))
    (dolist (o (print (f l)) p)
      (dotimes (i o) (setf p `(cdr ,p)))
      (setf p `(car ,p)))))

пример

(funcall *fun* '(4 5 (1 2 (7) 9 (10 8 14))) 14)

Список цитируется, но если вы действительно хотите, я могу использовать макрос. Возвращаемое значение [1] :

(CAR (CDR (CDR (CAR (CDR (CDR (CDR (CDR (CAR (CDR (CDR L)))))))))))

Для тестов я использовал лямбда-форму, где lбыла переменная:

(LAMBDA (#:G854) (CAR (CDR (CDR (CAR (CDR (CDR (CDR (CDR (CAR (CDR (CDR #:G854))))))))))))

Вызов этого с первоначальным списком возвращает 14.


[1] (caddar (cddddr (caddr l)))тоже было бы неплохо

CoreDump
источник
2
Вы ответили на вопрос о Лиспе с Лиспом! Это Лисп-чепче!
DanTheMan
4
@DanTheMan Lisp-ception - в значительной степени то, что определяет Lisp ;-)
coredump
9

Сетчатка , 170 142 125 115 114 87 84 83 75 73 70 69 68 67 байт

Да, менее 50% из более чем 100 байтов от моей первой попытки. :)

\b(.+)\b.* \1$
(
^.
l
\(
a
+`a *\)|\d


d
+`(.*[l)])(\w)
(c$2r $1)

Чтобы запустить код из одного файла, используйте -sфлаг.

Я все еще не уверен, что это оптимально ... У меня не будет много времени в течение следующих нескольких дней, я добавлю объяснение в конце концов.

Мартин Эндер
источник
5

Pyth, 62 байта

JvXz"() ,][")u?qJQG&=J?K}Quu+GHNY<J1)hJtJ++XWK"(cdr "\d\aG\)\l

Попробуйте онлайн: демонстрация или тестовый набор

Объяснение:

Первый бит JvXz"() ,][")заменяет символы "() "на символы "[],"входной строки, которая заканчивается представлением списка в стиле Python. Я оцениваю это и сохраняю в J.

Затем я уменьшаю строку G = "l"с u...\l. Я ...неоднократно применяю внутреннюю функцию до Gтех пор, пока значение Gбольше не изменится, а затем печатаю G.

Внутренняя функция делает следующее: Если число Jуже равно номеру ввода, то не изменять G( ?qJQG). В противном случае я сведу список J[:1]и проверим, есть ли введенный номер в этом списке, и сохраню его в переменной K( K}Quu+GHNY<J1)). Обратите внимание, что у Pyth нет оператора flatten, так что это занимает довольно много байтов. Если Kэто правда, то я обновляю J с помощью J[0], в противном случае с J[1:]( =J?KhJtJ). А потом я заменяю Gс "(cdr G)"и заменить , если верно ( ).daK++XWK"(cdr "\d\aG\)

Jakube
источник
5

Схема (R5RS), 102 байта

(let g((l(read))(n(read))(o'l))(if(pair? l)(or(g(car l)n`(car,o))(g(cdr l)n`(cdr,o)))(and(eq? n l)o)))
Андерс Касеорг
источник
1

PHP - 177 байт

Я добавил несколько строк для удобства чтения:

function f($a,$o,$n){foreach($a as$v){if($n===$v||$s=f($v,$o,$n))return
'(car '.($s?:$o).')';$o="(cdr $o)";}}function l($s,$n){echo f(eval(strtr
("return$s;",'() ','[],')),l,$n);}

Вот негольфированная версия:

function extractPhp($list, $output, $number)
{
    foreach ($list as $value)
    {
        if (is_int($value))
        {
            if ($value === $number) {
                return '(car '. $output .')';
            }
        }
        else
        {
            $subOutput = extractPhp($value, $output, $number);
            if ($subOutput !== null) {
                return '(car '. $subOutput .')';
            }
        }

        $output = '(cdr '. $output .')';
    }
}

function extractLisp($stringList, $number)
{
    $phpCode = 'return '. strtr($stringList, '() ','[],') .';';
    $list = eval($phpCode);
    echo extractPhp($list, 'l', $number);
}
Черная дыра
источник
1

Haskell, 190 188 байт

l "(4 5 (1 2 (7) 9 (10 8 14)))" 8

оценивает

"(car (cdr (car (cdr (cdr (cdr (cdr (car (cdr (cdr l))))))))))"

l(h:s)n=c$i(show n)s""""
i n(h:s)t l|h>'/'&&h<':'=i n s(t++[h])l|t==n='a':l|h=='('=j$'a':l|h==')'=j$tail$dropWhile(=='d')l|0<1=j$'d':l where j=i n s""
c[]="l"
c(h:s)="(c"++h:"r "++c s++")"
Лейф Виллертс
источник
1
Вы можете превратить (и cв функцию cв строку:c(h:s)="(c"++h:...
Ними
Ух ты, не думал, что это сработает с hЧаром!
Лейф Виллертс
0

Common Lisp, 168 155 байт

Некоторая глупая вещь рекурсии, это, вероятно, может быть сжато немного больше:

(lambda(l e)(labels((r(l o)(setf a(car l)d(cdr l)x`(car,o)y`(cdr,o))(if(equal e a)x(if(atom a)(r d y)(if(find e l)(r d y)(if d(r d y)(r a x)))))))(r l'l)))

Довольно напечатано:

(lambda (l e)
  (labels ((r (l o)
             (setf a (car l) d (cdr l)
                   x `(car ,o) y `(cdr ,o))
             (if (equal e a) x
                 (if (atom a)
                     (r d y)
                     (if (find e l)
                         (r d y)
                         (if d
                             (r d y)
                             (r a x)))))))
    (r l 'l)))
няня
источник