Утка, утка, джозефус

49

Учитывая массив Integer:

  1. Начните с первого номера
  2. Перейти вперед на n позиций, где n - значение текущей позиции
  3. Удалить текущую позицию, сделав следующую позицию текущей позицией.
  4. Переходите к шагу 2, пока не останется один номер
  5. Распечатать этот номер

правила

Обтекание массива (следующее число после последнего числа в массиве является первым числом).

Ноль удаляет себя (очевидно).

Отрицательные числа не допускаются в качестве входных данных.

Тестовые случаи

[1] => 1
[1,2] => 1
[1,2,3] => 3
[1,2,2] => 1
[1,2,3,4] => 1
[6,2,3,4] => 4
[1,2,3,4,5] => 5
[0,1] => 1
[0,0,2,0,0] => 0

Пошаговый пример

[1,4,2,3,5]
 ^          start from the first position
   ^        jump 1 position (value of the position)
[1,  2,3,5] remove number in that position
     ^      take next position of the removed number (the 'new' 'current' position)
         ^  jump 2 positions
[1,  2,3  ] remove number in that position
 ^          take next position (looping on the end of the array)
     ^      jump 1 position
[1,    3  ] remove number in that position
       ^    take next position (looping)
 ^          jump 3 positions (looping on the end of the array)
[      3  ] remove number in that position
print 3

Пример № 2

[4,3,2,1,6,3]
 ^            start from the first position
         ^    jump 4 positions
[4,3,2,1,  3] remove number in that position    
           ^  take next position
     ^        jump 3 positions
[4,3,  1,  3] remove number in that position    
       ^      take next position
           ^  jump 1 positions
[4,3,  1    ] remove number in that position    
 ^            take next position
   ^          jump 4 positions
[4,    1    ] remove number in that position    
       ^      take next position
 ^            jump 1 position
[      1    ] remove number in that position
print 1

Это код-гольф , выигрывает самый короткий ответ в байтах!

code-golf array-manipulation workoverflow
источник
14
Хороший первый вызов!
Луис Мендо
2
@LuisMendo Да ... проблемы "пропустить как ..."
J42161217
2
@Jenny_mathy Я не думал, что будет похожий, но, как сказал Луис, набор с закруткой создает интересную проблему для игры в гольф. Я думаю: /
workoverflow
3
@EriktheOutgolfer Не совсем дурак. Элементы там неразличимы, а размер шага фиксирован. Луис намного ближе, но все же достаточно отличается, я думаю.
Мартин Эндер
3
Нужно ли печатать окончательное число или просто вернуть? Нужно ли на самом деле возвращать число, или он может просто работать с массивом на месте, чтобы после запуска функции массив содержал только число?
Восстановить Монику iamnotmaynard

Ответы:

9

Шелуха , 7 байт

Это возвращает результат в виде одноэлементного списка

ΩεSotṙ←

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

объяснение

Ω               Until
 ε              the result is a singleton list
     ṙ          Rotate left by
  S   ←         the first element
   ot           Then remove the first element
H.PWiz
источник
7

Haskell , 54 50 48 байтов

f[x]=x
f(x:r)=f$snd<$>zip r(drop(x+1)$cycle$x:r)

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

Объяснение:

  • f[x]=x: Если данный список является одноэлементным списком, вернуть его элемент.
  • f(x:r)=f$ ...: В противном случае рекурсивно применимо fк следующему списку:
    • Элементы текущего списка циклически бесконечно ( cycle$x:r),
    • с x+1удаленными первыми элементами ( drop(x+1)$),
    • и усечено до длины r. ( snd<$>zip rэто более короткая альтернатива take(length r)).

Предыдущая 54-байтовая версия:

f=(%)=<<head
_%[x]=x
n%(x:r)|n<1=f r|s<-r++[x]=(n-1)%s

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

Laikoni
источник
7

Рубин , 37 байт

->r{r.rotate!(r[0]).shift while r[1]}

Изменяет массив на месте, что представляется приемлемым в качестве вывода. Попробуйте онлайн!

Восстановить Монику Ямнотмайнард
источник
6

MATL , 21 байт

1`yy)+ynX\[]w(5Mynq]x

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

1        % Push 1: current position in the array
`        % Do...while
  yy     %   Duplicate top two elements in the stack. Takes input implicitly
         %   in the first iteration.
         %   STACK: array, position, array, position
  )      %   Get specified entry in the array
         %   STACK: array, position, selected entry
  +      %   Add
         %   STACK: array, position (updated)
  y      %   Duplicate from below
         %   STACK: array, position, array
  n      %   Number of elements of array
         %   STACK: array, position, number of elements or array
  X\     %   1-based modulus
         %   STACK: array, position (wrapped around)
  []     %   Push empty array
         %   STACK: array, position, []
  w      %   Swap
         %   STACK: array, [], position
  (      %   Write value into specified entry in array. Writing [] removes
         %   the entry
         %   STACK: array (with one entry removed)
  5M     %   Push latest used position. Because of the removal, this now
         %   points to the entry that was after the removed one
         %   STACK: array, position
  y      %   Duplicate from below
         %   STACK: array, position, array
  n      %   Number of elements of array
         %   STACK: array, position, number of elements of array
  q      %   Subtract 1
         %   STACK: array, position, number of elements of array minus 1
]        % End. If top of the stack is nonzero, proceed with next iteration
         % STACK: array (containing 1 entry), position
x        % Delete. Implicitly display
         % STACK: array (containing 1 entry)
Луис Мендо
источник
1
Примечание: использование поворотов списка вместо удержания указателя, вероятно, сделает это намного короче.
Эрик Outgolfer
1
@Erik Спасибо. Но теперь, когда я добавил объяснение, я думаю, что я оставлю это так
Луис Мендо
Ну, вы всегда можете удалить объяснение, оно будет сохранено в истории :)
Эрик Outgolfer
6

Python 3 , 54 51 байт

f=lambda x:x and f((x+x*x[0])[x[0]:][1:len(x)])or x

Выход представляет собой одноэлементный список.

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

Деннис
источник
Совершенно несвязанный, но мне нравится твоя шляпа единорога, Деннис. xD (И, как всегда, хороший ответ!)
Кевин Круйссен,
5

CJam , 15 байтов

l~_,({_0=m<1>}*

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

объяснение

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

l~     e# Read and evaluate input.
_,(    e# Get its length L and decrement to L-1.
{      e# Run this block L-1 times...
  _0=  e#   Get the first element X.
  m<   e#   Rotate the array left by X positions.
  1>   e#   Discard the first element.
}*
       e# The final element remains on the stack and gets printed implicitly.

Интересная альтернатива, которая, к сожалению, не сохраняет байтов:

l~_{;m<1>_0=}*;
Мартин Эндер
источник
5

Brain-Flak , 88 байт

([[]]()){({}<(({})){({}<({}<([]){({}{}<>)<>([])}{}>)<>{({}[<>[]])<>}<>>[()])}{}{}>())}{}

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

объяснение

([[]]())                      Push negative N: the stack height - 1
{({}< … >())}{}               Do N times
     (({}))                     Duplicate M: the top of the stack
     {({}< … >[()])}{}          Do M times 
                                  Rotate the stack by 1:
          ({}< … >)               Pop the top of the stack and put it back down after
          ([]){({}{}<>)<>([])}{}  Pushing the rest of the stack on to the other one, in reverse, with the stack height added to each element (to ensure that all are positive)
          <>{({}[<>[]])<>}<>      Push the rest of the stack back, unreversing, and subtracting the stack height from each element
                      {}        Pop the top of stack
H.PWiz
источник
1
Очень странный гольф, но здесь он в 88 байтах .
Wheat Wizard
1
@WheatWizard Хорошо, удивительно, я попробовал что-то подобное ранее.
H.PWiz
Я никогда не могу знать, как люди могут так кодировать! есть ли переводчик псевдокода или что-то еще?
workoverflow
1
@workoverflow нет, честно говоря, проще, чем кажется. Это было очень сложно до того, как я начал, но когда команды настолько просты, их легко освоить.
H.PWiz
5

Python 2 , 55 байт

def f(a):
 while a[1:]:l=a[0]%len(a);a[:]=a[-~l:]+a[:l]

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

Выводится в виде одноэлементного списка, как это разрешено по умолчанию . Благодаря Деннису удалось сэкономить несколько байтов , напомнив мне, что изменение аргумента функции разрешено.

Как это устроено

  • def f(a)- Определяет функцию с параметром a.

  • while a[1:]:- Хотя aс первым удаленным элементом является правдой, запустите блок кода, чтобы следовать. Список с одним или несколькими элементами является правдивым, а пустые списки ложными в Python, поэтому это остановится, как только aдостигнет длины 1.

  • l=a[0]%len(a)- Возьмите первый элемент и получите остаток от его деления на длину a. Присвойте результат l.

  • a[:]=a[-~l:]+a[:l]- Поверните aвлево по lэлементам и удалите первый, назначая его на aместо.

Python 2 , 63 байта

f=lambda a,i=0:a[1:]and f(a,a.pop(((a*-~i)[i]+i)%len(a))+1)or a

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

Хотя и дольше, это выглядит намного элегантнее. Также спасибо ovs за помощь в чате.

Мистер Xcoder
источник
1
Не могли бы вы сделать что-то вроде a,*b=input()(python3) и сохранить несколько байтов? Однако я не уверен, как это повлияло бы lи на ломтик
Rod
1
@ Род Я так не думаю, мне бы тоже нужно было оценить ввод в Python 3
г-н Xcoder
4

Желе , 7 байт

ṙḷ/ḊµḊ¿

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

Полная программа.

Эрик Outgolfer
источник
3
Это ḷ/чертовски умно.
г-н Xcoder
Не могли бы вы добавить объяснение, пожалуйста? Теперь я посмотрел на Quicks и Atoms на связанных GIT-страницах и добавил +1 на основе этого, но я могу представить, что не у всех есть пациенты, которые делают то же самое. ;)
Кевин Круйссен
4

Желе , 9 байт

ṙḷ/ḊµL’$¡

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

-2 байта благодаря пользователю 202729

объяснение

ṙḷ/ḊµL’$¡  Main Link
     L’$¡  Repeat <length - 1> times
ṙ          Rotate left by
 ḷ/        The first element (from JHT; thanks to user202729)
   Ḋ       Take all but the first element
HyperNeutrino
источник
3

Mathematica, 36 байт

использует алгоритм Мартина 

#//.l:{x_,__}:>Rest@RotateLeft[l,x]&

-5 байтов от Миши Лаврова и Мартина Эндера

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

J42161217
источник
1
Вы можете сохранить два байта, используя шаблон для выбора первого элемента #//.{x_,y__}:>Rest@RotateLeft[{x,y},x]&. (Это останавливается, когда есть только один элемент, потому что он {a}больше не соответствует шаблону {x_,y__}.)
Миша Лавров
1
@MishaLavrov не может тестировать прямо сейчас, но вы, вероятно, можете сократить его еще больше, опустив y, вызвав весь список, lа затем используя lвместо {x,y}.
Мартин Эндер
1
@MartinEnder Вы имеете в виду, как это - #//.l:{x_,__}:>Rest@RotateLeft[l,x]&?
Миша Лавров
1
@ МишаЛавров да.
Мартин Эндер
3

J , 21 17 байт

-4 байта благодаря FrownyFrog

((1<#)}.{.|.])^:_

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

Оригинал:

([:}.{.|.])^:(1<#)^:_

Как это устроено:

^:_ повторяйте, пока результат не перестанет меняться

^:(1<#) если длина списка больше 1

{.|.] поверните список влево его первый элемент раз

[:}. бросьте первый элемент и закройте вилку

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

Гален Иванов
источник
@ FrownyFrog Спасибо, я не пробовал это - это намного лучше!
Гален Иванов
3

JavaScript (ES6), 54 60 байт

Сохранено 1 байт благодаря исправленной версии @Shaggy
(+6 байт)

Модифицирует входной массив , который уменьшается до одиночного.

f=(a,p=0)=>1/a||f(a,p=(p+a[p%(l=a.length)])%l,a.splice(p,1))

Контрольные примеры

Показать фрагмент кода

Как?

Мы рекурсивно применяем алгоритм, описанный в задаче. Только условие остановки 1/aможет показаться немного странным. При применении арифметического оператора:

  • Массивы более чем одного элемента приводятся NaNи 1/NaNтакже NaN(ложно).
  • Массивы ровно один целочисленный принуждают к этому целому числу, что приводит либо 1/0 = +Infinityили 1/N = positive floatдля N> 0 (как truthy).
f = (a, p = 0) =>                 // a = input array, p = pointer into this array
  1 / a ||                        // if a is not yet a singleton:
    f(                            //   do a recursive call with:
      a,                          //     a
      p = (                       //     the updated pointer
        p + a[p % (l = a.length)] //
      ) % l,                      //
      a.splice(p, 1)              //     the element at the new position removed
    )                             //   end of recursive call
Arnauld
источник
Видя, как spliceмодифицирует исходный массив, вы могли бы сделать f=(a,p=0)=>1/a||f(a,p=p+a[p]%a.length,a.splice(p,1))для 52 байтов
Shaggy
кажется, что это не дает правильного результата для второго пошагового примера, f=(a,p=0)=>1/a?a:f(a,p=(p%a.length+a[p%a.length])%a.length,a.splice(p,1))это нормально, но может быть оптимизировано
Науэль Фуйе
@NahuelFouilleul Ой. В какой-то момент я подумал, что круглые скобки p+a[p]могут быть удалены. Что, конечно, не так. Спасибо за сообщение об этом!
Арно
Посмотрите на этот консенсус , который @Neil привлек мое внимание здесь .
Лохматый
@ Шэгги О, понятно. Спасибо! (Я пропустил вашу ссылку
Арно
3

Java 8, 79 байт

Эта лямбда принимает Stack<Integer>и возвращает intили Integer.

l->{for(int i=0,s=l.size();s>1;)l.remove(i=(i+l.get(i%s))%s--);return l.pop();}

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

Ungolfed

l -> {
    for (
        int i = 0, s = l.size()
        ; s > 1
        ;
    )
        l.remove(
            i = (i + l.get(i % s)) % s--
        );
    return l.pop();
}

Подтверждения

  • -2 байта благодаря Nahuel Fouilleul
Jakob
источник
1
i%=sможет быть удалено в случае l.get(i)измененияl.get(i%s)
Науэль Фуйе
2

Pyth , 9 байт

.WtHt.<Zh

Попробуй это здесь!

Это выводит результат в виде одноэлементного списка, как это разрешено по умолчанию .

Как это устроено

.WtHt.<Zh ~ Full program.

.W        ~ Functional while. It takes three arguments, two functions: A and B
            and a starting value, which in this case is automatically assigned
            to the input. While A(value) is truthy, value is set to B(value).
            Returns the ending value. A's argument is H and B's is Z.
  tH      ~ A (argument H): Remove the first element of H. A singleton list
            turns into [], which is falsy and thus breaks the loop. Otherwise,
            it is truthy and the loops goes on until the list reaches length 1.
     .<Zh ~ B (argument Z): Cyclically rotate Z by Z[0] places, whereas Z[0]
            represents the first element of Z.
    t     ~ And remove the first element.

Примечание. Если вы не хотите видеть эти скобки, просто добавьте hили eперед целым кодом.

Мистер Xcoder
источник
2

Swift , 87 байт

func f(a:inout[Int]){var i=0,c=0;while(c=a.count,c>1).1{i=(i+a[i%c])%c;a.remove(at:i)}}

Возвращает как одноэлементный список путем изменения ввода . Попробуйте онлайн!

объяснение

func f(a:inout[Int]){
  var i=0,c=0;            // Set the index i to 0
  while(c=a.count,c>1).1{ // While the length of the list > 0:
    i=(i+a[i%c])%c;       //  Add a[i] to i and loop back using modulo
    a.remove(at:i)        //  Remove a[i]
  }
}
Герман Л
источник
2

Perl 6 , 46 45 байт

(-1 байт благодаря Брэду Гилберту)

{($_,{(|$_ xx*)[.[0]+(1..^$_)]}...1)[*-1][0]}

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

($_, { ... } ... 1)генерирует последовательность списков, начиная со входного списка $_, каждый последующий элемент генерируется выражением фигурной скобки и заканчивая, когда список smart-совпадает 1--ie, имеет длину 1. Трейлинг [* - 1]получает последний элемент и последний [0]удаляет единственный элемент из этого списка.

(|$_ xx *)генерирует плоскую, бесконечно реплицированную копию текущего элемента. Этот список индексируется с диапазоном .[0] + (1 ..^ $_)для извлечения следующего конечного списка в серии.

Шон
источник
1
с ума
Адриан
[*-1][0]может быть объединен в [*-1;0]сохранение байта. И 1..$_-1лучше написано как 1..^$_снова сохранение байта.
Брэд Гилберт b2gills
@ BradGilbertb2gills Я пытался [*-1;0], но, похоже, это не эквивалентно. Затем функция возвращает список, а не число.
Шон
Это не останавливает 1..^$_оптимизацию
Брэд Гилберт b2gills
1

Perl 5 , 47 43 41 + 2 ( -ap) = 43 байта

$\=splice@F,($_+=$F[$_%@F])%@F,1while@F}{

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

Принимает ввод в виде разделенных пробелами чисел.

Xcali
источник
кажется, что это не совсем то же самое, что пошаговый пример, который следуют, но дольше$x%=@F,splice@F,$x=($x+$F[$x])%@F,1while$#F;$_="@F"
Науэль Фуйе
1
вау oO Нужно поднять мою игру.
Адриан
1

Java 8 , 325 байт

Golfed:

static void n(Integer[]j){Integer[]h;int a=0;h=j;for(int i=0;i<j.length-1;i++){if(h.length==a){a=0;}a=(a+h[a])%h.length;h[a]=null;h=m(h);}System.out.print(h[0]);}static Integer[] m(Integer[]array){Integer[]x=new Integer[array.length-1];int z=0;for(int i=0;i<array.length;i++){if(array[i]!=null){x[z]=array[i];z++;}}return x;}

Ungolfed:

 interface ArrayLeapFrog {
static void main(String[] z) throws Exception {
    Integer[] j = {6, 2, 3, 4};
    n(j);
}

static void n(Integer[] j) {
    Integer[] h;
    int a = 0;
    h = j;
    for (int i = 0; i < j.length - 1; i++) {
        if (h.length == a) {
            a = 0;
        }
        a = (a + h[a]) % h.length;
        h[a] = null;
        h = m(h);
    }
    System.out.print(h[0]);
}

static Integer[] m(Integer[] array) {
    Integer[] x = new Integer[array.length - 1];
    int z = 0;
    for (int i = 0; i < array.length; i++) {
        if (array[i] != null) {
            x[z] = array[i];
            z++;
        }
    }
    return x;
  }
}
DevelopingDeveloper
источник
4
Добро пожаловать! Пара советов: здесь не нужно считать staticключевые слова. Обычно мульти-методические решения реализуются как нестатические члены класса и mainсоздают экземпляр для тестирования. Кроме того, если вы делаете это таким образом, вы поддерживаете Java 7 и можете представить просто «решение Java». Для дальнейшего использования формат ввода здесь достаточно гибок, поэтому, например, вы можете принять входные данные как List(что весьма полезно для этой проблемы).
Якоб
1

APL + WIN, 36 байт

¯1↑⍎¨(1⌈¯1+⍴v←,⎕)⍴⊂'v←(1<⍴v)↓v[1]⌽v'

Объяснение:

Подсказки для ввода с экрана. 

'v←(1<⍴v)↓v[1]⌽v' Loop logic as a string

 (1<⍴v)↓ only drop the first when number of elements n>1

 (1⌈¯1+⍴v←,⎕)⍴⊂ create a nested vector of logic of length 1 max n-1

 ⍎¨ execute each element of the nested vector in turn

¯1↑ take answer from executing final element
Грэхем
источник
1

Python 2, 61 байт

def f(x):
 while x[1:]:y=x[0]%len(x);x=x[y+1:]+x[:y]
 print x
Rɪᴋᴇʀ
источник
1
Я знаю, что существует множество ответов на языке Python, но я решил, что могу добавить свои собственные.
Rɪᴋᴇʀ
1

JavaScript, 58 56 59 байт

let f =

a=>{for(i=0,k=a.length;k>1;)i+=a[i%=k],a.splice(i%=k--,1)}
<h2>Test</h2>
Enter or paste a valid array literal within square brackets and click Run.
<blockquote>
   <input id = "array" type="text" length="20">
   <button type="button" onclick="run()">Run</button>
</blockquote>
Result: <pre id="o"></pre>

<script>
    function run() {
       let a = JSON.parse(array.value);
       f(a);
       o.textContent = a;
    }
</script>
Развернуть фрагмент

Возвращает результат как единственный элемент, оставшийся во входном массиве, который обновляется на месте.

Два байта сохраняются с помощью оператора, разделенного запятыми, вместо оператора блока в теле цикла for! Три байта потеряны, чтобы пропустить элемент, удаленный в конце массива (:

Менее гольф:

a => {
    for(i=0,k=a.length;k>1;) // once less than array length
        i+=a[i%=k],          // the new index
        a.splice(            // delete an element
           i%=k--,           // ensuring index is within array,
                             // and post decrement loop count
           1
        )
}
traktor53
источник
Это, кажется, дает неправильный ответ для [3, 5, 7, 9].
Нил
Неправильно для [3,5,7,9]. Ожидаемое значение 5
edc65
Функция не возвращает значение, я не уверен, что количество байтов является правильным, учитывая это, поскольку он не может работать сам по себе ...
Брайан Х.
@ edc65 и Нил, спасибо - индекс элемента, удаленного в конце массива, не корректировался в начале сокращенного массива.
traktor53
@BrianH. функция изменяет свой параметр, существует мнение, что codegolf.meta.stackexchange.com/a/4942/21348
edc65
1

Brain-Flak , 104 байта

H.PWiz имеет более короткий ответ здесь , что я помог сделать, вы должны проверить его.

([[]]()){({}()<(({})){({}[()]<({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}{}>)}{}

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

объяснение

([[]]())   #Push 1 minus stackheight
{({}()<    #N times
 (({}))    #Get a copy of the top
 {({}[()]< #N times
  ({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>
           #Roll the top to the bottom (From the wiki)
 >)}{}     #End loop
 {}        #Remove one value
>)}{}      #End loop
Мастер пшеницы
источник
Я думал, что буду соревноваться . Тогда я понял, что мой был почти таким же, как ваш , за исключением другого «главного броска»
H.PWiz
Я видел это ;). Использование того факта, что все неотрицательно, довольно умно.
Пшеничный Волшебник
1

R 111 117 126 байт

Спасибо @Giuseppe за то, что он проиграл 11 байтов, переключившись на цикл while, получил еще 4, удалив функцию и непосредственно прочитав ввод пользователя.

Я не очень хорошо себя чувствую о том, что потребовалось, чтобы попасть туда - я уверен, что существует более элегантное решение.

i=scan();m=1;while((l=sum(i|1))-1){j=i[m];p=`if`(j+m>l,j%%l+!m-1,j+m);p=`if`(!p,m,p);i=i[-p];m=`if`(p-l,p,1)};i

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

Код без правил

i=scan()
m=1
while((l=sum(i|1))-1){
  j=i[m]
  p=`if`(j+m>l,j%%l+!m-1,j+m)
  p=`if`(!p,m,p)
  i=i[-p]
  m=`if`(p-l,p,1)
}
i
отметка
источник
117 байт - обратите внимание, что, поскольку это рекурсивная функция, f=необходимо включить имя
Джузеппе
1
Я нашел это довольно сложной задачей с языком с 1 индексным индексом без вращения массивов; whileя думаю, это потенциально на 1-3 байта короче с циклом.
Джузеппе
115 байтов с whileциклом
Джузеппе
мой предыдущий 115-байтовый код был недействительным, так как мы оба забыли f=часть рекурсивной функции. :(
Джузеппе
Я обновил старый счет и новый счет, чтобы отразить рекурсивность :) С помощью цикла while я отсканировал еще 4 байта с помощью сканирования.
Mark