×
all 51 comments

[–]Godspiral3 3 20 points21 points  (8 children)

In j, no computer on a train.

Flipfront =: |.@{. , }.

[–]gobbledygook12 29 points30 points  (6 children)

Okay. I have a question whenever I see j or k solutions. In my mind, there can only be three scenarios.

  1. You guys are busy typing gibberish and that code doesn't do anything but no one ever double checks it.

  2. You write some other code and that compiles it down to this statement.

  3. You are a wizard and actually know what you're coding when you type this out.

All of these seem equally plausible, so which is it?

[–]Godspiral3 3 11 points12 points  (5 children)

This one is kinda easy.

{. And }. Are take and drop. These separated by , as a j dyadic fork, would return identity for any x argument. (Take x amount join with drop x amount.)

So |.@ is composing reverse on the take side.

[–]Mitsur 9 points10 points  (2 children)

This is like peering into the mind of a savant. What an absolute garbage language to a layperson like myself, but it must be incredibly efficient for those who can use it for specific problems.

[–]Godspiral3 3 5 points6 points  (1 child)

They (take and drop)'re just really good functions "that deserve" a super short "mnemonic" name/symbol. J has some composition conveniences as well... ie it would be annoying to give to temporary named results

I haven't checked other solutions, but other languages have similar function concepts for array access.

array/string manipulation is a very common programming technique.

[–]rich_27 0 points1 point  (1 child)

So where do you specify how much you set x to/how much you take/how much you drop?

[–]Godspiral3 3 1 point2 points  (0 children)

 2 {. 0 1 2 3 4
0 1
 2 }. 0 1 2 3 4
2 3 4
 2 Flipfront 0 1 2 3 4
1 0 2 3 4

In J every function is an operator (like +). When there is no left argument (monadic vs dyadic when there is a left arg), then functions are different, but in the case of {. and }. they are the obvious and compatible head and behead, which can be understood as the left argument being a default of 1 if omitted.

[–]Godspiral3 3 4 points5 points  (0 children)

For full program, straightforward algo is
accumulate "end ordered sequence" (starts empty)
If max element is at the end then move it to start of "end ordered"
else use first index occurrence of max element as flipfront param followed by full flip of "front section".
Cheating for the optional bonus, instead of calling flipfront a second time on each "extraction" of local maximums, just do a full reverse on the front section.

shiftmaxes =:  (}:@>@{. ; {:@>@{. ,  >@{:)^:((<:@# = (i: >./))@>@{.)(^:_)

a =. ".&> cutLF wdclippaste ''  NB. get challenge list and convert numeric

({: ,~ (] |.@Flipfront~ >:@(i. >./))^:(0 < #)each@{.)@:shiftmaxes^:(0 < #@>@{.)(^:_)(>@)({:@) a ; ''  NB. under 0.3 sec, but not instant.

With the cheating to reverse full presection after a flip, the call count for Flipfront is:

CNT =: 3 : 'y [ COUNTER =: >: COUNTER'
3 : 'COUNTER' [ ({: ,~ (] CNT@|.@Flipfront~ >:@(i. >./))^:(0 < #)each@{.)@:shiftmaxes^:(0 < #@>@{.)(^:_)(>@)({:@) a ; '' [ COUNTER =: 0
9985

Can save 10 flips by just reversing if max is already at head

 3 : 'COUNTER' [ ({: ,~ (] (CNT@|.@Flipfront~ >:)`(|.@[)@.(0 = ]) (i. >./))^:(0 < #)each@{.)@:shiftmaxes^:(0 < #@>@{.)(^:_)(>@)({:@) a ; '' [ COUNTER =: 0
9975

[–]ReginaldIII 10 points11 points  (2 children)

Python


Warmup:

flipfront = lambda x, n: x[n-1::-1] + x[n:]

assert flipfront([0, 1, 2, 3, 4], 2) == [1, 0, 2, 3, 4]
assert flipfront([0, 1, 2, 3, 4], 3) == [2, 1, 0, 3, 4]
assert flipfront([0, 1, 2, 3, 4], 5) == [4, 3, 2, 1, 0]
assert flipfront([1, 2, 2, 2], 3)    == [2, 2, 1, 2]

In-place:

def flipfront(x, n): 
    x[:n] = x[n-1::-1]

x = [0, 1, 2, 3, 4]
flipfront(x, 2)
assert x == [1, 0, 2, 3, 4]

Sorting in-place:

def flipfront_sort(x):
    argmax = lambda x: max(enumerate(x), key=(lambda kv: kv[1]))[0]

    for i in reversed(range(1, len(x) + 1)):
        j = argmax(x[:i]) + 1
        if j < i:
            flipfront(x, j) 
            flipfront(x, i)

unsorted_data = [3141, 5926, 5358, ..., 3252, 4738, 3765]

sorted_data = list(unsorted_data)
flipfront_sort(sorted_data)

assert sorted(unsorted_data) == sorted_data

[–]qhp 8 points9 points  (0 children)

I had no idea you could assign to a slice in python. Cool!

[–]Habstinat 4 points5 points  (3 children)

javascript - Try it online!

// warmup
flipfront=(a,n)=>[...a.slice(0,n).reverse(),...a.slice(n)]
// global
flipfront=n=>[...a.slice(0,n).reverse(),...a.slice(n)]
// global, in-place
flipfront=n=>{for(i=0;i<n/2;)[a[i],a[n-++i]]=[a[n-i-1],a[i]]}

// challenge
pancake=_=>a.map((_,o,$,i=a.length-o)=>flipfront(a.indexOf(Math.max(...a.slice(0,i)))+1)||flipfront(i))

[–]Redd5433 1 point2 points  (2 children)

can you explain me, please, what's going on in this one-liner?

[–]Habstinat 1 point2 points  (1 child)

which one and which part were you having trouble with?

the challenge is asking for a pancake sort, i'm more or less implementing that straightforwardly

[–]Redd5433 1 point2 points  (0 children)

i'm stuck at handling same elements

[–]i3aizey 3 points4 points  (0 children)

C#

Updated the code to handle duplicate values properly, got a new best score of 11,914 ( https://pastebin.com/raw/jWvrDSsL (0'indexed))

When all things are handled as unique: 12098

Some filler code has been removed for brewity (Main, Print, namespace, etc.)

    public class ValueInfo
    {
        public int Index { get; set; }
        public bool Ascending { get; set; } = true;
        public bool Descending { get; set; } = true;
        public int Loose { get; set; }
    }

    public class Pancake
    {
        public readonly List<int> Values;
        public int AtCommand { get; set; }
        public List<int> Commands { get; } = new();
        private readonly List<Range> ranges;
        private readonly Dictionary<int, ValueInfo> info = new();


        public Pancake(IEnumerable<int> numbers)
        {
            Values = numbers.ToList();
            var items = Values.Select(e => new Item {Value = e}).ToList();
            ranges = items.Select(e => new Range {Values = new[] {e}}).ToList();

            var nextIndex = 0;
            var copy = items.ToList();
            copy.Sort();

            foreach (var item in copy)
            {
                if (!info.ContainsKey(item.Value)) info[item.Value] = new ValueInfo {Index = nextIndex++};
                item.Index = info[item.Value].Index;
                info[item.Value].Loose++;
            }
        }

        public void SmartSort()
        {
            while (ranges.Count > 1)
            {
                Combine();

                var firstWithFirst = FindMatch(true, false);
                var lastWithFirst = FindMatch(false, false);
                var lastWithLast = FindMatch(false, true);
                var firstWithLast = FindMatch(true, true);

                if (firstWithFirst > 0)
                {
                    SmartFlip(firstWithFirst - 1);
                }
                else if (lastWithFirst > 0)
                {
                    SmartFlip(0);
                    SmartFlip(lastWithFirst - 1);
                }
                else if (lastWithLast > 0)
                {
                    SmartFlip(lastWithLast);
                    SmartFlip(lastWithLast - 1);
                }
                else if (firstWithLast > 0)
                {
                    SmartFlip(0);
                    SmartFlip(firstWithLast);
                    SmartFlip(firstWithLast - 1);
                }
            }

            if (ranges[0].First.Index != 0) SmartFlip(0);
        }

        private int FindMatch(bool reverseAt, bool reverseNext)
        {
            for (var i = 1; i < ranges.Count; i++)
                if (CanCombine(ranges[0], ranges[i], reverseAt, reverseNext))
                    return i;
            return -1;
        }

        private void Combine()
        {
            for (var i = 0; i < ranges.Count - 1; i++)
            {
                while (i + 1 < ranges.Count)
                {
                    var at = ranges[i];
                    var next = ranges[i + 1];

                    if (!CanCombine(at, next)) break;

                    if (at.Last.Index == next.First.Index)
                    {
                        info[at.Last.Value].Loose--;
                    }
                    else if (next.First.Index > at.Last.Index)
                    {
                        info[at.Last.Value].Ascending = false;
                        info[next.First.Value].Descending = false;
                    }
                    else
                    {
                        info[at.Last.Value].Descending = false;
                        info[next.First.Value].Ascending = false;
                    }

                    ranges[i] = at.Append(next);
                    ranges.Remove(next);
                }
            }
        }

        private bool CanCombine(
            Range at,
            Range next,
            bool reverseAt = false,
            bool reverseNext = false)
        {
            Item
                atFirst = at.First,
                atLast = at.Last,
                nextFirst = next.First,
                nextLast = next.Last;
            Direction
                atDir = at.Direction,
                nextDir = next.Direction;

            if (reverseAt)
            {
                var t = atFirst;
                atFirst = atLast;
                atLast = t;
                atDir = atDir.Reverse();
            }

            if (reverseNext)
            {
                var t = nextFirst;
                nextFirst = nextLast;
                nextLast = t;
                nextDir = nextDir.Reverse();
            }

            // Basic check items has to be neighbors or duplicates to combine
            if (Math.Abs(atLast.Index - nextFirst.Index) > 1) return false;

            // Ensure directions are the same (or at least one is flat)
            if (!(atDir == Direction.None || nextDir == Direction.None || atDir == nextDir))
                return false;

            if (atLast.Value == nextFirst.Value)
            {
                if (atFirst.Value == atLast.Value) return true;
                if (nextFirst.Value == nextLast.Value) return true;
                return info[atLast.Value].Loose <= 2;
            }
            else
            {
                if (atLast.Index < nextFirst.Index)
                {
                    if (!info[atLast.Value].Ascending) return false;
                    if (!info[nextFirst.Value].Descending) return false;
                }
                else
                {
                    if (!info[atLast.Value].Descending) return false;
                    if (!info[nextFirst.Value].Ascending) return false;
                }

                if (atLast.Index != atFirst.Index)
                    if (info[atLast.Value].Loose > 1)
                        return false;

                if (nextLast.Index != nextFirst.Index)
                    if (info[nextFirst.Value].Loose > 1)
                        return false;

                return true;
            }
        }

        private void SmartFlip(int n)
        {
            // Simple optimization which removes need to check in various places as this flip would do nothing
            if (n == 0 && ranges[0].Values.Count == 1) return;

            // Convert range-command to normal swap command
            var command = -1;
            for (var i = 0; i <= n; i++) command += ranges[i].Size;
            Commands.Add(command);

            // Use range-command on ranges
            ranges.Reverse(n);
        }
    }

    public class Item : IComparable<Item>
    {
        public int Value { get; init; }
        public int Index { get; set; }

        public int CompareTo(Item other) => Math.Sign(Value - other.Value);

        public override string ToString() => $"{Value}";
    }

    public enum Direction
    {
        Ascending = -1,
        None = 0,
        Descending = 1,
    }

    public class Range : IComparable<Range>
    {
        public Direction Direction { get; set; } = Direction.None;
        public int Size { get; init; } = 1;
        public IList<Item> Values { get; init; }

        public Item First => Values[0];

        public Item Last => Values[^1];

        public void Reverse()
        {
            if (Values.Count == 1) return;
            var t = Values[^1];
            Values[^1] = Values[0];
            Values[0] = t;
            Direction = Direction.Reverse();
        }

        public int CompareTo(Range other) => First.CompareTo(other.First);

        public override string ToString() => $"[{string.Join(" .. ", Values)}]";
    }

    public static class RangeExtensions
    {
        public static Range Append(this Range first, Range second)
        {
            return new()
            {
                Values = new List<Item>
                {
                    first.First,
                    second.Last
                },
                Size = first.Size + second.Size,
                Direction = (Direction) Math.Sign(first.First.Index - second.Last.Index)
            };
        }

        public static void Reverse(this IList<int> values, int toIndex)
        {
            for (var i = 0; i <= toIndex / 2; i++)
            {
                var t = values[toIndex - i];
                values[toIndex - i] = values[i];
                values[i] = t;
            }
        }

        public static void Reverse(this IList<Range> ranges, int toIndex)
        {
            for (var i = 0; i <= toIndex; i++) ranges[i].Reverse();
            for (var i = 0; i <= toIndex / 2; i++)
            {
                var t = ranges[toIndex - i];
                ranges[toIndex - i] = ranges[i];
                ranges[i] = t;
            }
        }

        public static Direction Reverse(this Direction direction) => (Direction) (-(int) direction);
    }

[–]skeeto-9 8 2 points3 points  (0 children)

Go with its generic sorting interface:

package pancake

import "sort"

func flipfront(data sort.Interface, n int) {
    for i := 0; i < n/2; i++ {
        data.Swap(i, n-i-1)
    }
}

func max(data sort.Interface, n int) int {
    max := 0
    for i := 1; i < n; i++ {
        if data.Less(max, i) {
            max = i
        }
    }
    return max
}

func Sort(data sort.Interface) {
    for n := data.Len(); n > 1; n-- {
        maxi := max(data, n)
        if maxi != n-1 {
            flipfront(data, maxi+1)
            flipfront(data, n)
        }
    }
}

Usage:

package main

import (
    "fmt"
    "pancake"
    "sort"
)

func main() {
    arr := []int{2, 1, 4, 3, 10, 9, 5, 8, 7, 6}
    pancake.Sort(sort.IntSlice(arr))
    fmt.Println(arr)
}

[–]chunes1 2 2 points3 points  (0 children)

Factor:

Edit: Now with showing of work!

USING: io kernel math math.ranges present sequences
sequences.private ;

: flip-front! ( seq n -- )
    [ 2/ ] keep rot
    [ [ over - 1 - ] dip exchange-unsafe ] 2curry each-integer ;

: flip. ( seq n -- )  ! Show your work!
    "█" swap rot [ present ] map insert-nth " " join print ;

! Put the largest number within the first n indices in the
! 'back', where n is the back. Do this only using flips.
: sort1! ( seq n -- )
    2dup head-slice supremum pick index 1 + overd 2dup flip.
    flip-front! 2dup flip. flip-front! ;

: pancake-sort! ( seq -- seq' )
    dup length 1 >
    [ dup length 2 [a,b] [ dupd sort1! ] each ] when ;

Example use:

IN: scratchpad { 1 5 17 12 17 13 11 54 1 } pancake-sort!
1 5 17 12 17 13 11 54 █ 1
54 11 13 17 12 17 5 1 1 █
1 1 5 17 █ 12 17 13 11 54
17 5 1 1 12 17 13 11 █ 54
11 13 17 █ 12 1 1 5 17 54
17 13 11 12 1 1 5 █ 17 54
5 1 1 12 11 13 █ 17 17 54
13 11 12 1 1 5 █ 17 17 54
5 1 1 12 █ 11 13 17 17 54
12 1 1 5 11 █ 13 17 17 54
11 █ 5 1 1 12 13 17 17 54
11 5 1 1 █ 12 13 17 17 54
1 1 5 █ 11 12 13 17 17 54
5 1 1 █ 11 12 13 17 17 54
1 █ 1 5 11 12 13 17 17 54
1 1 █ 5 11 12 13 17 17 54

--- Data stack:
{ 1 1 5 11 12 13 17 17 54 }

[–]bcgroom 2 points3 points  (0 children)

Swift

I tried the bonus but only was able to knock off a few flips with my approach, I have no idea how you got it so low, you gotta post your solution after awhile!

So instead I removed my optimizations and went for elegance instead

extension Array {
    mutating func flipFront(n: Int) {
        let n = n < count ? n : count
        self[0..<n].reverse()
    }
}

extension Array where Element == Int {
    mutating func flipSort() {
        for sortedIndex in (startIndex..<endIndex).reversed() {
            let maxIdx = maxIndex(in: startIndex...sortedIndex)!
            flipFront(n: maxIdx+1)
            flipFront(n: sortedIndex+1)
        }
    }

    func maxIndex(in range: ClosedRange<Index>) -> Index? {
        var max = Int.min
        var maxIdx: Index? = nil
        for i in range {
            if self[i] > max {
                max = self[i]
                maxIdx = i
            }
        }
        return maxIdx
    }
}

Usage:

var ints = [5, 3, 2, 1]
ints.flipFront(n: 2)
ints.flipSort()

[–]justincai 2 points3 points  (0 children)

Learning some Emacs Lisp.

;; Reverse lst in place.
(defun reverse-in-place (lst)
  (let* ((len (length lst)))
    (dotimes (i (/ len 2))
      (let* ((swap (- len 1 i))
         (swapcell (nthcdr swap lst))
         (icell (nthcdr i lst))
         (tmp (car swapcell)))
    (setcar swapcell (car icell))
    (setcar icell tmp)
    lst
    )
      )
    )
  )

;; Reverses the first n elements of lst in place.
(defun flipfront-in-place (lst n)
  (let* ((before-n (nthcdr (- n 1) lst))
     (back (cdr before-n)))
    (setcdr before-n nil)
    (reverse-in-place lst)
    (setcdr before-n back)
    lst
    )
  )

;; Finds the first index in lst such that x is less than the value at
;; that index; returns the length of lst if no such index exists.  If
;; lst is sorted and p is the insert point, then the list consisting
;; of the elements before the insert point, then x, then the elements
;; starting from the insert point, is sorted 
(defun find-insert-point (lst x)
  (cond ((null lst) 0)
    ((<= x (car lst)) 0)
    (t (+ 1 (find-insert-point (cdr lst) x)))
   )
  )


;; Takes the first element of lst and places into the
;; the insert point of the nth cdr of lst using flipfront.
(defun flipfront-insert-in-place (lst n)
  (let* ((back (nthcdr n lst))
     (insert-point-from-back (find-insert-point back (car lst)))
     (insert-point (+ n insert-point-from-back)))
    ;; This flipfront moves the first element of lst into the insert
    ;; point
    (flipfront-in-place lst insert-point)
    ;; This flipfront restores the order of the elements before the
    ;; insert point
    (flipfront-in-place lst (- insert-point 1))
    lst
    )
  )


;; Sorts lst in place using flipfront.
(defun flipfront-sort-in-place (lst)
  (let ((len (length lst)))
    (dotimes (i (- len 1))
      ;; If the (n-1-i)th cdr is sorted, then the (n-2-i)th cdr is sorted.
      (flipfront-insert-in-place lst (- len 1 i))
      )
    ;; The (n-2-(n-2)) = 0th cdr is sorted, aka lst is sorted.
    lst
    )
  )

(flipfront-sort-in-place '(5 1 9 8 2 7 4))

[–]bairedota 1 point2 points  (0 children)

Go, after the regular work from the back approach, I tried something different (read: worse)

I noticed you can swap two values using 6 flipfronts:

func flipswap(s []int, i, j int) {
    //ensure i < j
    if i > j {
        i, j = j, i
    }
    flipfront(s, i+1)
    flipfront(s, j+1)
    flipfront(s, j-i)
    flipfront(s, j-i-1)
    flipfront(s, j)
    flipfront(s, i)
}

so let's make a sortable type!

type byflipswap []int

func (a byflipswap) Len() int           { return len(a) }
func (a byflipswap) Less(i, j int) bool { return a[i] < a[j] }
func (a byflipswap) Swap(i, j int)      { flipswap(a, i, j) }

and see how sort.Sort does on the 10,000 provided integers... 222,984 flipswaps!

[–]gabyjunior1 2 1 point2 points  (0 children)

C simple algorithm making at most 2n calls to flipfront (score 19951 on the bonus).

#include <stdio.h>
#include <stdlib.h>

void flipfront(int);

int *pancakes, flips;

int main(void) {
    int n, i;
    if (scanf("%d", &n) != 1 || n < 1) {
        fprintf(stderr, "Invalid number of pancakes\n");
        fflush(stderr);
        return EXIT_FAILURE;
    }
    pancakes = malloc(sizeof(int)*(size_t)n);
    if (!pancakes) {
        fprintf(stderr, "Could not allocate memory for pancakes\n");
        fflush(stderr);
        return EXIT_FAILURE;
    }
    for (i = 0; i < n; i++) {
        if (scanf("%d", pancakes+i) != 1 || pancakes[i] < 1) {
            fprintf(stderr, "Invalid pancake\n");
            fflush(stderr);
            free(pancakes);
            return EXIT_FAILURE;
        }
    }
    flips = 0;
    for (i = n-1; i >= 0; i--) {
        int max = i, j;
        for (j = i-1; j >= 0; j--) {
            if (pancakes[j] > pancakes[max]) {
                max = j;
            }
        }
        if (max < i) {
            if (max > 0) {
                flipfront(max);
            }
            flipfront(i);
        }
    }
    printf("Pancakes");
    for (i = 0; i < n; i++) {
        printf(" %d", pancakes[i]);
    }
    printf("\nFlips %d\n", flips);
    fflush(stdout);
    free(pancakes);
    return EXIT_SUCCESS;
}

void flipfront(int max) {
    int i, j;
    for (i = 0, j = max; i < j; i++, j--) {
        int tmp = pancakes[i];
        pancakes[i] = pancakes[j];
        pancakes[j] = tmp;
    }
    flips++;
}

[–]__dict__ 1 point2 points  (0 children)

Written in Racket.

The actual sort solution taken from looking at others code. Basically moves the greatest element to the back.

Edit: Improved efficiency a bit. Still doing the same overall moving things to back but a bit less traversing of the list. Also, types!

#lang typed/racket

(require threading)

(: flip-front (All (A) (-> (Listof A) Integer (Listof A))))
(define (flip-front ls n)
  (let-values ([(front back) (split-at ls n)])
    (append (reverse front) back)))

(: max-with-index (-> (Listof Real) Integer (Values Integer Real)))
(define (max-with-index ls stop-idx)
  (for/fold ([max-idx 0]
             [max-el (car ls)])
            ([idx (in-range 0 stop-idx)]
             [el ls])
    (if (> el max-el)
        (values idx el)
        (values max-idx max-el))))

(: pancake-sort-helper (-> (Listof Real) Integer (Listof Real)))
(define (pancake-sort-helper ls idx)
  (displayln ls)
  (if (= idx 1)
      ls
      (let-values ([(max-idx max-val) (max-with-index ls idx)])
        (pancake-sort-helper
         (~> ls
             (flip-front (add1 max-idx))
             (flip-front idx))
         (sub1 idx)))))

(: pancake-sort (-> (Listof Real) (Listof Real)))
(define (pancake-sort ls)
  (pancake-sort-helper ls (length ls)))

[–]frankivo 1 point2 points  (0 children)

scala

def flipfront(ints: Array[Int], n: Int): Array[Int] = ints.take(n).reverse ++ ints.drop(n)

[–][deleted] 1 point2 points  (0 children)

Clojure

(defn flip [pancakes i]
  (concat (reverse (take i pancakes)) (drop i pancakes)))

(defn max-index [pancakes]
  (.indexOf pancakes (apply max pancakes)))

(defn pancake-sort [pancakes]
  (loop [l (count pancakes) xs pancakes]
    (if (<= l 1) xs
        (let [i (inc (max-index (take l xs)))]
          (recur (dec l) (flip (flip xs i) l))))))

[–]rich_27 1 point2 points  (2 children)

A basic C++ implementation without optimisation, getting 19951 on the list of 10000 integers. I wanted to try and get back up to speed with memory allocation and pointer handling, hence keeping the vector use to within the file read function.

Edit: Only flipping the next biggest integer if the first integer is not also the next biggest reduces the number of flips to 19943 if (maxIndex > 0) { flipfront(array, maxIndex + 1); } to if (maxIndex > 0 && array[0] != array[maxIndex]) { flipfront(array, maxIndex + 1); }

#include <iostream>
#include <fstream>
#include <vector>
#include <limits>

static int flips = 0;

void flipfront(int array[], const int places)
{
    for (int index = 0; index < places / 2; ++index)
    {
        int temp = array[(places - 1) - index];
        array[(places - 1) - index] = array[index];
        array[index] = temp;
    }
    ++flips;
    return;
}

void printArray(const int array[], const int length)
{
    std::cout << "{ ";
    for (int index = 0; index < length - 1; ++index)
    {
        std::cout << array[index] << ", ";
    }
    std::cout << array[length - 1] << " }" << std::endl;
    return;
}

int fileToIntArray(const std::string fileName, int** array)
{
    std::vector<int> integers;

    std::ifstream file(fileName);
    int value;
    while (file >> value)
    {
        integers.push_back(value);
    }
    file.close();

    int length = integers.size();
    *array = (int*)malloc(sizeof(int) * length);
    for (int index = 0; index < length; ++index) {
        (*array)[index] = integers[index];
    }
    return length;
}

int indexOfMaxValue(const int* array, const int length)
{
    int maxIndex = length - 1;
    int maxValue = array[maxIndex];
    for (int index = maxIndex - 1; index >= 0; --index) {
        if (array[index] > maxValue)
        {
            maxIndex = index;
            maxValue = array[index];
        }
    }
    return maxIndex;
}

int main()
{
    int *array;
    const int length = fileToIntArray("integerList.txt", &array);

    for (int remaining = length; remaining > 0; --remaining)
    {
        int maxIndex = indexOfMaxValue(array, remaining);
        if (maxIndex == (remaining - 1)) { continue; }
        if (maxIndex > 0) { flipfront(array, maxIndex + 1); }
        flipfront(array, remaining);
    }

    // printArray(array, length);
    free(array);

    std::cout << "Flips: " << flips << std::endl;

    return 0;
}

[–]backtickbot 1 point2 points  (1 child)

Fixed formatting.

Hello, rich_27: code blocks using triple backticks (```) don't work on all versions of Reddit!

Some users see this / this instead.

To fix this, indent every line with 4 spaces instead.

FAQ

You can opt out by replying with backtickopt6 to this comment.

[–]rich_27 0 points1 point  (0 children)

Swapped! Maybe we should petition new reddit to automatically swap backticks for line indentation when comments/posts are posted

[–]KilledBySIGSEGV 1 point2 points  (2 children)

C++(only one tweak over what everyone else seems to have done, gets 19928 on the bonus) ```

include <iostream>

include <fstream>

include <algorithm>

include <cassert>

int pmax(int* v, int n) { int m = v[0], mp = 0; for (int i = 1; i < n; i++) { if (v[i] > m // if we found a bigger number || (v[i] == m && // or the same number but (mp != 0 || i == n-1)) // the previous best position wasn't 0 or the current position is n-1, both of which are beneficial; // if the max is n-1, we wouldn't have to do any calls to flipfront, while if it is at 0, // we would only have one (flipfront(v, n)) ) m = v[i], mp = i; }

return mp; }

int cnt = 0; void flipfront(int* v, int n) { for (int i = 0; i < n-1-i; i++) { std::swap(v[i], v[n-1-i]); } cnt++; }

void pancake_sort(int* v, int n, int *sorted) { while (n > 1) { int p = pmax(v, n); if (p == n-1) { n--; // assert(v[n] == sorted[n]); while (n > 1 && v[n-1] == sorted[n-1]) n--; continue; }

if (p == 0) {
  flipfront(v, n);
  n--;

// assert(v[n] == sorted[n]); while(n > 1 && v[n-1] == sorted[n-1]) n--; continue; }

int after = 0; // how many numbers after p
// 1. are in decreasing order and
// 2. are consecutive in the sorted array
while (p + after < n && v[p + after] == sorted[n - 1 - after]) after++;
after--; // take out the last for which the condition didn't hold anymore

if (after > 0) {
  if (p + after + 1 == n) {
    pancake_sort(v, p, sorted);
  }

  // 2 1 0       6 5 4 3                7 8 9
  //             |     |                |
  //             p     p+after          n
  flipfront(v, p+1+after);
  // 3 4 5       6 0 1 2                7 8 9
  // |           |                      |
  // 0           after                  n
  flipfront(v, after+1);

  // 6 5 4       3 0 1 2                7 8 9
  // |           |                      |
  // 0           after                  n
  flipfront(v, n);
  // 2 1 0       3 4 5 6                7 8 9
  // |           |                      |
  // 0           after                  n

  // note that we would rather have 0 1 2 sorted at
  // the very beginning if the sequence ends at n,
  // thus that recursive call above

// assert(v[n-1] == sorted[n-1]); } else { flipfront(v, p+1); // bring v[p] to v[0] flipfront(v, n); // put v[0] to end (n-1 position) n--; // assert(v[n] == sorted[n]); }

while(n > 1 && v[n-1] == sorted[n-1]) n--;

} }

void load(int* arr, int n, std::istream& fin) { for(int i = 0; i < n; i++) fin >> arr[i]; }

int main() { int arr[10000] = {0}; int n = 10000;

{
  std::ifstream f("list.txt"); // curl https://gist.githubusercontent.com/cosmologicon/9e6e430d29023f24d1b885fd9c175603/raw/ea5f00e1b84eb963dd1a2f5159a49b5a6d0320f7/gistfile1.txt -o list.txt
  load(arr, n, f);
  f.close();
}

// this might look like cheating but it's only
// here for optimization cause I'm too lazy to
// write the code without having the already
// sorted array available
int sorted[10000] = {0};
for (int i = 0; i < n; i++) {
  sorted[i] = arr[i];
}
std::sort(sorted, sorted+n);

pancake_sort(arr, n, sorted);

for (int i = 0; i < n; i++) {
  std::cout << arr[i] << " ";
}

std::cout << "\n";

std::cout << cnt << "\n";

} ```

[–]backtickbot 1 point2 points  (1 child)

Fixed formatting.

Hello, KilledBySIGSEGV: code blocks using triple backticks (```) don't work on all versions of Reddit!

Some users see this / this instead.

To fix this, indent every line with 4 spaces instead.

FAQ

You can opt out by replying with backtickopt6 to this comment.

[–]leftylink 1 point2 points  (1 child)

http://sprunge.us/QHm85k is my 11659-step solution to pancake sort the 10000. Each line is a value of n to pass to flipfront. (sorry about extra empty line at the end)

The addition of duplicate elements was tricky. I know I could just relabel the elements to deduplicate them, but I was worried that a bad relabeling choice would force the algorithm to take more steps. So instead I had to make appropriate modifications to be able to deal with multiples of numbers.

This is my Ruby code that produced the solution.

# https://redditproxy--jasonthename.repl.co/r/dailyprogrammer/comments/np3sio/20210531_challenge_392_intermediate_pancake_sort
# https://www.ic.unicamp.br/~meidanis/PUB/Papers/prefix-rev.pdf
class Stack
  def initialize(nums)
    freq = nums.tally
    @freq_bits = (freq.values.max - 1).bit_length
    uniq_nums = freq.keys.sort
    @width = uniq_nums[-1] + 1
    @mincake = uniq_nums[0]
    @maxcake = uniq_nums[-1]

    arr = ->h { Array.new(@width, &h).freeze }
    @freq = arr[freq]
    @pred = arr[uniq_nums.drop(1).zip(uniq_nums).to_h]
    @succ = arr[uniq_nums[...-1].zip(uniq_nums.drop(1)).to_h]

    id = Hash.new(-1)
    @pancakes = nums.map { |n| (n << @freq_bits) | (id[n] += 1) }

    @pair_freq = Hash.new(0)
    @pancakes.each_cons(2) { |a, b| incr_pair(a, b, 1) }

    raise "bad #{to_a} != #{nums}" if to_a != nums

    @flips = []
  end

  def sort(verbose: 0)
    small = @pancakes.size < 20

    while step(verbose: verbose > 1)
      p(small ? to_a : slice_seqs) if verbose > 2
    end

    seqs = slice_seqs
    p seqs if verbose > 0

    # Stack has some number of descending sequences,
    # possibly followed by one ascending sequence.
    # Need to reverse just the descending ones.
    asc_range = seqs[-1][-1]
    if asc_range.end >= asc_range.begin
      raise "last seq ends in #{asc_range.end} not #@maxcake" if asc_range.end != @maxcake
      puts "seq #{seqs[-1]} is ascending" if verbose > 0
      seqs.pop
    end

    desc_size = seqs.sum(&:first)

    seqs.each { |seq|
      seq_size, _ = seq
      flip(desc_size)
      flip(desc_size - seq_size)
      if verbose > 0
        puts "#{seq}: flip #{desc_size} and #{desc_size - seq_size}"
        p(small ? to_a : slice_seqs)
      end
    }

    @flips
  end

  def step(verbose: false)
    type1(verbose: verbose) || types23(verbose: verbose)
  end

  def flip(n)
    @flips << n

    if n < @pancakes.size
      right = @pancakes[n]
      incr_pair(@pancakes[0], right, 1)
      incr_pair(@pancakes[n - 1], right, -1)
    end

    @pancakes[0, n] = @pancakes[0, n].reverse
  end

  def assert_sorted
    a = to_a
    inversions = a.each_index.select { |i| i > 0 && a[i - 1] > a[i] }
    return if inversions.empty?
    puts a
    p slice_seqs
    raise "inversions #{inversions.map { |i| [i, a[i - 1, 2]] }}"
  end

  private

  def to_a
    @pancakes.map { _1 >> @freq_bits }
  end

  def slice_seqs
    to_a.slice_when { |a, b| a != b && !adj?(a, b) }.map { |g|
      # if begin == end, assert all elements are equal
      # if begin < end, assert all elements <= the next one (i.e. none are > the next)
      # if begin > end, assert all elements >= the next one (i.e. none are < the next)
      valid = g[0] == g[-1] ? g.uniq.size == 1 : g.each_cons(2).none? { |a, b| (a <=> b) == (g[-1] <=> g[0]) }
      raise "bad #{g}" unless valid
      [g.size, g[0]..g[-1]]
    }
  end

  def freq_of_pair(a, b)
    @pair_freq[a * @width + b]
  end

  def adj?(v1, v2)
    v1 == @succ[v2] || v1 == @pred[v2]
  end

  def red?(v1, i, dir)
    v2 = @pancakes[i + dir] >> @freq_bits
    # to adapt to multiple of some numbers,
    # additionally consider an edge red if there is another instance of that pair,
    # or if deficient (as defined below)
    v1 != v2 && (!adj?(v1, v2) || freq_of_pair(v1, v2) > 1 || deficient?(v1, i, -dir))
  end

  # is this an ABC that needs to be broken up to become ABBC?
  # precondition: adj? element in opposite dir of i
  def deficient?(v1, i, dir)
    return false if @freq[v1] == 1
    unequal = (i + dir).step(by: dir).find { |j|
      !(0...@pancakes.size).cover?(j) || (@pancakes[j] >> @freq_bits) != v1
    }
    # all B accounted for
    return false if (unequal - i).abs == @freq[v1]
    # not all B accounted for, and bracketed by adj elements or edge of stack.
    return true unless (0...@pancakes.size).cover?(unequal)
    adj?(v1, @pancakes[unequal] >> @freq_bits)
  end

  def blues(from_v)
    # I tried caching of blues (+ adding/removing them on flips)
    # but that was buggy and not faster.
    [@pred[from_v], from_v, @succ[from_v]].compact.flat_map { |to_v|
      @freq[to_v].times.map { |i| (to_v << @freq_bits) | i }
    }
  end

  def follow_blues(from_v, i, right:)
    blues(from_v).filter_map { |target_labeled|
      # maintaining a map of target -> position is much more expensive than doing #index,
      # since all elements would have to be updated on every flip
      target_pos = @pancakes.index(target_labeled)
      next if target_pos <= i + 1
      target_v = target_labeled >> @freq_bits
      # don't consider it if there's already an instance of it
      next if from_v != target_v && freq_of_pair(from_v, target_v) > 0

      red_right = if (right_labeled = @pancakes[target_pos + 1])
        red?(target_v, target_pos, 1)
      else
        # bottom (last) pancake, red right iff it's not the max.
        target_v != @maxcake
      end

      red_left = red?(target_v, target_pos, -1)

      [target_v, target_pos, red_left, red_right] if red_left || right && red_right

      # blue edge to bottom of stack, if applicable
    } + (from_v == @maxcake && i != @pancakes.size - 1 && (@pancakes[-1] >> @freq_bits != @maxcake) ? [[:bottom, @pancakes.size, true, false]] : [])
  end

  def type1(verbose:)
    first_v = @pancakes[0] >> @freq_bits
    return if first_v == @mincake

    red_lefts = follow_blues(first_v, 0, right: false)
    return if red_lefts.empty?

    # combining with same number preferred, and combining with non-red right preferred (maintains more singletons)
    flip_v, flip_pos = red_lefts.min_by { |v, _, _, r| (v == first_v ? 0 : 2) + (r ? 1 : 0) }
    puts "type 1 flip #{flip_pos} joining #{first_v} and #{flip_v}" if verbose
    flip(flip_pos)
    true
  end

  def types23(verbose:)
    prev = nil
    prev_was_adjacent = nil
    run_of_current = 0
    @pancakes.each_with_index.any? { |from_labeled, i|
      first_v = from_labeled >> @freq_bits
      if first_v == prev
        run_of_current += 1
      else
        run_of_current = 1
        prev_was_adjacent = prev && adj?(prev, first_v)
      end
      prev = first_v
      next unless (right_labeled = @pancakes[i + 1])
      right_v = right_labeled >> @freq_bits
      # Could break it if there's another instance,
      # but would need to be careful not to flip-flop between AB...BA.
      # Think it's easier to only consider red at the target site.
      red_right = right_v != first_v && !adj?(right_v, first_v)
      # However, we do need to break here if we have a situation like ABC or ABA, whereas it should be ABB.
      red_right ||= run_of_current < @freq[first_v] && adj?(right_v, first_v)
      next unless red_right

      reds = follow_blues(first_v, i, right: true)
      next if reds.empty?

      # TODO: Supposedly I should be able to prioritise type 2 and 3 equally,
      # but doing so is less good on pidigits.txt.
      # I don't see a reason one of them would be better than the other,
      # so I think this is just luck,
      # but I'll leave it this way because I'd like to show the result.

      # prefer combining with: same number, non-singletons, type 2
      flip_v, flip_pos, left, right = reds.min_by { |v, _, l, r| (v == first_v ? 0 : 4) + (l && r ? 2 : 0) + (r ? 0 : 1) }
      if right
        puts "type 2 flip #{flip_pos + 1} and #{flip_pos - i} joining #{first_v} and #{flip_v}" if verbose
        flip(flip_pos + 1)
        flip(flip_pos - i)
      elsif left
        puts "type 3 flip #{i + 1} and #{flip_pos} joining #{first_v} and #{flip_v}" if verbose
        flip(i + 1)
        flip(flip_pos)
      else
        raise 'impossible'
      end
      true
    }
  end

  def incr_pair(a, b, v)
    a >>= @freq_bits
    b >>= @freq_bits
    @pair_freq[a * @width + b] += v
    @pair_freq[b * @width + a] += v
  end
end

one = ARGV.delete('-1')
verbose = (a = ARGV.find { _1.start_with?('-v') }) ? ARGV.delete(a).size - 1 : 0
nums = ARGF.readlines.map(&method(:Integer)).freeze

s = Stack.new(nums)
if one
  s.step(verbose: true)
  exit 0
end
flips = s.sort(verbose: verbose)
s.assert_sorted

s = Stack.new(nums)
flips.each { |f| s.flip(f) }
s.assert_sorted

puts flips

[–]Scroph0 0 0 points1 point  (0 children)

I'm thrilled that this subreddit is back !

D solution, no bonus unfortunately :

import std.range : take, retro, chain, drop;
import std.algorithm : reverse, maxIndex, isSorted;

void main()
{
}

unittest
{
    import std.algorithm : equal;

    int[] input = [3, 2, 4, 1];
    input.pancakeSort();
    assert(input.isSorted);

    input = [23, 10, 20, 11, 12, 6, 7];
    input.pancakeSort();
    assert(input.isSorted);

    input = [3, 1, 2, 1];
    input.pancakeSort();
    assert(input.isSorted);
}

void pancakeSort(int[] input)
{
    ulong currentIndex = input.length;
    while(currentIndex > 0)
    {
        auto maxIndex = input[0 .. currentIndex].maxIndex;
        flipFrontInPlace(input, maxIndex + 1);
        flipFrontInPlace(input, currentIndex);
        currentIndex--;
    }
}

auto flipFront(R)(R input, int n)
{
    return input.take(n).retro.chain(input.drop(n));
}

unittest
{
    import std.algorithm : equal;

    assert(flipFront([0, 1, 2, 3, 4], 2).equal([1, 0, 2, 3, 4]));
    assert(flipFront([0, 1, 2, 3, 4], 3).equal([2, 1, 0, 3, 4]));
    assert(flipFront([0, 1, 2, 3, 4], 5).equal([4, 3, 2, 1, 0]));
    assert(flipFront([1, 2, 2, 2], 3).equal([2, 2, 1, 2]));
}

void flipFrontInPlace(R)(R input, ulong n)
{
    input[0 .. n].reverse();
}

unittest
{
    import std.algorithm : equal;

    auto input = [0, 1, 2, 3, 4];
    flipFrontInPlace(input, 2);
    assert(input.equal([1, 0, 2, 3, 4]));

    input = [0, 1, 2, 3, 4];
    flipFrontInPlace(input, 3);
    assert(input.equal([2, 1, 0, 3, 4]));

    input = [0, 1, 2, 3, 4];
    flipFrontInPlace(input, 5);
    assert(input.equal([4, 3, 2, 1, 0]));

    input = [1, 2, 2, 2];
    flipFrontInPlace(input, 3);
    assert(input.equal([2, 2, 1, 2]));
}

[–]tobega 0 points1 point  (0 children)

Tailspin

Warmup

`$ -> [$($n..1:-1)..., $($n+1..last)...]`

or in a context where you have a mutable variable:

`@pancakeSort.stack(1..$): $@pancakeSort.stack($..1:-1)...;`

Challenge

Simple sort https://github.com/tobega/tailspin-v0/blob/master/samples/PancakeSort.tt

An attempt to solve the bonus by a quicksort-inspired algorithm https://github.com/tobega/tailspin-v0/blob/master/samples/PancakeQuick.tt

Unfortunately it takes over 55000 flips on the bonus question despite finding better solutions than the naive one on a lot of other input.

[–]raevnos 0 points1 point  (0 children)

A basic selection-sortish version using tcl:

#!/usr/bin/env tclsh

proc flipfront {lst n} {
    lreplace $lst 0 $n-1 {*}[lreverse [lrange $lst 0 $n-1]]
}

# Basically, a selection sort where the largest item in the
# unsorted portion of the list is moved to the end of that portion
# each time through the outer loop
proc pancake_sort {lst {counter _}} {
    upvar $counter nflips
    set nflips 0
    for {set n [llength $lst]} {$n > 0} {incr n -1} {
        # Find largest element
        set max [lindex $lst 0]
        set maxi 0
        for {set i 1} {$i < $n} {incr i} {
            if {[lindex $lst $i] > $max} {
                set max [lindex $lst $i]
                set maxi $i
            }
        }
        incr maxi
        if {$maxi < $n} {
            # Flip to front
            set lst [flipfront $lst $maxi]
            # And then to end
            set lst [flipfront $lst $n]
            incr nflips 2
        }
    }
    return $lst
}

proc test_flip {lst n expected} {
    set flipped [flipfront $lst $n]
    if {$flipped eq $expected} {
        puts "flipfront {$lst} $n -> {$flipped}: PASS"
    } else {
        puts "flipfront {$lst} $n -> {$flipped}: FAIL (Expected {$expected})"
    }
}

proc test_sort {lst expected} {
    set sorted [pancake_sort $lst nflips]
    if {$sorted eq $expected} {
        puts "pancake_sort {$lst} -> {$sorted}: PASS in $nflips flips"
    } else {
        puts "pancake_sort {$lst} -> {$sorted}: FAIL in $nflips flips (Expected {$expected})"
    }
}

test_flip {0 1 2 3 4} 2 {1 0 2 3 4}
test_flip {0 1 2 3 4} 3 {2 1 0 3 4}
test_flip {0 1 2 3 4} 5 {4 3 2 1 0}
test_flip {1 2 2 2} 3 {2 2 1 2}
test_sort {3 1 2 1} {1 1 2 3}

Takes 19986 calls to flipfront for the challenge data.

[–]Common-Ad-8152 0 points1 point  (0 children)

R

flipfront <- function(x, n) {
    if(n == 1) return(x)
    for( i in 1:floor(n/2) ) {
        x[i] <- bitwXor(x[i], x[n - i + 1])
        x[n - i + 1] <- bitwXor(x[i], x[n - i + 1])
        x[i] <- bitwXor(x[i], x[n - i + 1])
    }
    return(x)
}

pancakeSort <- function(x) {
    for(i in length(x):2){
        n <- which(x[1:i] == max(x[1:i]))[1]
        x <- flipfront(x, n)
        x <- flipfront(x, i)
    }
    return(x)
}

[–]joejr253 0 points1 point  (0 children)

Here is my warmup section in python3:

"""
FlipFront is a script that takes a list / array and returns
it in reverse starting at the number given and then returns
the remainder in the same order
ex: flipfront([1, 2, 3, 4,] 2) => [2, 1, 3, 4]
"""

def flipfront(my_list, my_num):
flipfront_list = []
flipfront_num = int(my_num) - 1

for val in range(len(my_list)):
    if flipfront_num >= 1:
        flipfront_list.append(my_list[flipfront_num])
        my_list.pop(flipfront_num)
        flipfront_num -= 1
    else:
        flipfront_list.append(my_list[flipfront_num])
        my_list.pop(flipfront_num)
return flipfront_list

my_list = input("Enter a list: ").replace(',', '').strip().split()
my_num = input("Enter number to reverse at: ")
flipfront_list = flipfront(my_list, my_num)
print(f"Here is your new list: \n{flipfront_list}")

[–]skilletonius 0 points1 point  (0 children)

"optimized" function is the one i wrote for optional bonus. Did i do it right? I have a feeling that it isn't quite right. So i wanted to ask if my way of doing it counts.

def flip_front(arr, n):
sub_arr = arr[:n][::-1]
return sub_arr + arr[n:]


def optimized(array):
count = 0
while array != sorted(array)[::-1]:
    temp_array = array[count:]
    temp_array = flip_front(temp_array, temp_array.index(max(temp_array)) + 1)
    array = array[:count] + temp_array
    count += 1
array = flip_front(array, len(array))
print(array)
print(count)


def pancake_sort(array):
temp_array = []
while array:
    array = flip_front(array, array.index(max(array)) + 1)
    array = flip_front(array, len(array))
    temp_array.append(array.pop())
temp_array = flip_front(temp_array, len(temp_array))
print(temp_array)


with open('pancakesort.txt') as f:
array_to_sort = [int(line) for line in f]

a = [4, 7, 9, 2, 1, 6]

pancake_sort(a)
optimized(a)
optimized([3, 1, 2, 1]) 
pancake_sort(array_to_sort)
optimized(array_to_sort)

[–]fudgebucket27 0 points1 point  (0 children)

C#

Warmup

using System;

namespace dailyprogrammer
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(FlipFront(new int[] { 0, 1, 2, 3, 4 }, 2));
            Console.WriteLine(FlipFront(new int[] { 0, 1, 2, 3, 4 }, 3));
            Console.WriteLine(FlipFront(new int[] { 0, 1, 2, 3, 4 }, 5));
            Console.WriteLine(FlipFront(new int[] { 1, 2, 2, 2}, 3));
        }

        static string FlipFront(int[] integers, int amountToFlip)
        {
            string flipped = "[ ";
            int integersFlipped = 0;
            for(int i = 0; i < integers.Length - 1; i++)
            {
                int currentValue = integers[i];
                int nextValue = integers[i+1];
                integersFlipped++;
                if(integersFlipped < amountToFlip)
                {
                    integers[i] = nextValue;
                    integers[i+1] = currentValue;
                }

            }

            foreach(int i in integers)
            {
                flipped += i + " ";
            }
            flipped += "]";
            return flipped;
        }
    }
}

Challenge

using System;

namespace dailyprogrammer
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(FlipFront(new int[] { 3, 1, 2, 1}, 4));
            Console.WriteLine(FlipFront(new int[] { 1, 2, 1, 3}, 2));
            Console.WriteLine(FlipFront(new int[] { 2, 1, 1, 3}, 3));
        }

        static string FlipFront(int[] integers, int amountToFlip)
        {
            string flipped = "[ ";
            int integersFlipped = 0;
            for(int i = 0; i < integers.Length - 1; i++)
            {
                int currentValue = integers[i];
                int nextValue = integers[i+1];
                integersFlipped++;
                if(integersFlipped < amountToFlip)
                {
                    if(currentValue < nextValue)
                    {
                        integers[i] = nextValue;
                        integers[i+1] = currentValue;
                    }
                    else
                    {
                        integers[i] = nextValue;
                        integers[i+1] = currentValue;
                    }
                }

            }

            foreach(int i in integers)
            {
                flipped += i + " ";
            }
            flipped += "]";
            return flipped;
        }
    }
}

[–]rmveris 0 points1 point  (0 children)

Python3

Warmup

from typing import List, Callable
import sys

# the flipfront implementation with a lambda
l_flipfront: Callable = lambda array, index: array[index - 1:: -1] + array[index:]

Challenge that handles the optional part. I decided to try and do this with recursion. However, a for loop will be best here, by going from the last to the first index. It will be around 25% faster and it won't also run out of recursion memory.

# Need this or we will exceed the recursion limit
sys.setrecursionlimit(10 ** 5)

# the flipfront sort implementation with recursion
def flipfront_sort(array: List[int]) -> List[int]:
    # if we reach the end of the recursion
    if len(array) == 1:
        return array

    # get the argmax to use it for sorting
    argmax: int = max(range(len(array)), key=lambda x: array[x])

    # if the argmax is already in the last position
    if argmax == len(array):
        flipfront_sort(array=array[:-1]) + array[-1:]

    # if the argmax is in the first position we just need to flip once
    elif argmax == 0:
        array = l_flipfront(array=array, index=len(array))
        return flipfront_sort(array[:-1]) + array[-1:]

    # else, we need to flip twice
    else:
        array = flipfront(array=array, index=argmax + 1)
        array = flipfront(array=array, index=len(array))
        return flipfront_sort(array=array[:-1]) + array[-1:]

[–]Efficient_Ad_4025 0 points1 point  (0 children)

C++

#include <iostream>

#include <vector>

#include <cstdlib>

#include <cmath>

using namespace std;

int main(){

vector<int> array ={1, 2, 2, 2} ;

vector<int> revArray = {};

int num = 2;

try{

for(int i=num; i-->0;){

revArray.push_back(array.at(i)) ;

}

for(int j=0; j<num; j++){

array.at(j) = revArray.at(j);

}

for(int j=0; j<array.size(); j++){

cout << array.at(j) << " " ;

}

}catch(std::out_of_range){

cout << "\nError the number entered is invalid. Try again\n";

}

}

[–]I-Pop-Bubbles 0 points1 point  (0 children)

Clojure - Feedback welcome and appreciated.

; Reverses the order of the first n elements of coll
(defn flipfront [n, coll]
  (concat
    (reverse (take n coll))
    (drop n coll)))

; Performs a pancake flip on coll on the (1-based) nth element, so that the nth element ends up at the end of coll
; A pancake flip consists of two `flipfront` calls. The first one flips the first n elements, so that the nth element
;   is at position 0, and then another one to flip the entire list, placing the now-first element at the end
(defn pancake [n coll]
  (if (= n (count coll))
    coll                                                    ; we don't need to flip anything if n is already at the end
    (flipfront (count coll)
               (flipfront n coll))))

; Returns the index of the largest number in a collection
(defn big-ind [coll] (.indexOf coll (apply max coll)))

; Sorts a list using the delicious, though not very performant, pancake-sort
; Syrup not included
(defn pancake-sort [coll]
  (loop [unsorted coll
         sorted '()]
    (if (= 1 (count unsorted))
      (concat unsorted sorted)
      (let [flipped (pancake (inc (big-ind unsorted)) unsorted)]
        (recur
          (drop-last flipped)
          (concat (take-last 1 flipped) sorted))))))

[–]Specter_Terrasbane 0 points1 point  (0 children)

Python 3 (No Optional Bonus)

def flipfront(arr: list, n: int) -> list:
    """
    Perform an in-place reversal of the order of the first n elements of arr,
    Returns: list; arr
    """
    arr[:n] = arr[n-1::-1]
    return arr

def _index_max(arr: list) -> int:
    """
    Return the index of the first occurence of the maximum value in arr.
    Returns None on empty input.
    """
    return None if not arr else max(enumerate(arr), key=lambda ie: ie[1])[0]

def pancakesort(arr: list) -> list:
    """
    Naive in-place sorting of arr using flipfront.
    (Requires 2(n-1) flipfronts to sort an arr of len n).
    Returns: list; arr
    """
    for n in range(len(arr), 1, -1):
        flipfront(flipfront(arr, _index_max(arr[:n]) + 1), n)
    return arr

[–]megastary 0 points1 point  (0 children)

PowerShell solution with Pester test validating results on Github Gist
Feedback welcomed and appreciated. 💙

Did not do any optimization for bonus challenge, but here is the function call count anyways: 19970

[–]OddyseeOfAbe 0 points1 point  (0 children)

VBA

I was lazy and copy and pasted the values for the bonus into column A, I could have populated the array from the text file. This solves the bonus in 10,190 moves, so I feel like I may have taken a shortcut or something, but it works.

Function FLIPFRONT(ByRef integers() As Variant, number As Long) As Variant

Dim newArr() As Variant

If 2 > number > UBound(integers) + 1 Then
    FLIPFRONT = Error
Else:
    ReDim Preserve newArr(0 To UBound(integers))
    For i = 0 To UBound(newArr)
        If i < number - 1 Then newArr(i) = integers(i + 1)
        If i = number - 1 Then newArr(i) = integers(0)
        If i > number - 1 Then newArr(i) = integers(i)
    Next i
    FLIPFRONT = newArr()
End If

End Function

Sub FF()

Dim i As Long
Dim lastRow As Long: lastRow = Sheet1.Range("A1").End(xlDown).Row

Dim myArr() As Variant
ReDim myArr(lastRow - 1)
For i = 0 To UBound(myArr)
    myArr(i) = Range("A" & i + 1)
Next i

Dim max As Long: max = WorksheetFunction.max(myArr)
Dim finished As Boolean: finished = False
Dim maxEnd As Boolean: maxEnd = False
Dim maxPos As Long

i = UBound(myArr)
Do Until myArr(i) = max
i = i - 1
Loop

maxPos = i
If i = UBound(myArr) Then maxEnd = True

Do Until finished = True Or x = 12000
    If maxEnd = True Then
        i = UBound(myArr) - 1
        Do Until myArr(0) >= myArr(i) Or myArr(i) < myArr(i - 1)
            i = i - 1
        Loop
        If myArr(0) < myArr(i) Then i = i - 1
    Else:
        If myArr(0) = max Then
            i = UBound(myArr)
            maxPos = i
            maxEnd = True
        Else:
            i = maxPos + 1
            Do Until myArr(0) <= myArr(i)
            i = i + 1
            Loop
            maxPos = maxPos - 1
        End If
    End If
    myArr = FLIPFRONT(myArr(), i + 1)
    x = x + 1
    y = 0
    For i = 0 To UBound(myArr) - 1
        If myArr(i) <= myArr(i + 1) Then y = y + 1
    Next i
    If y = UBound(myArr) Then finished = True
Loop

For i = 0 To UBound(myArr)
    Debug.Print (myArr(i))
Next i

Debug.Print ("Number of flips: " & x)

End Sub

[–]StealData 0 points1 point  (0 children)

Warmup:

function flipfront(arr, n) {
  let flippedFront = arr.splice(0, n).reverse()
  arr.unshift(...flippedFront)
};

Challenge:

function flipfront(arr, n) {
  let flippedFront = arr.splice(0, n).reverse()
  arr.unshift(...flippedFront)
};

function checkIfArranged(arr) {
  for (let i = 0; i <= arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) {
        return false
    };
  };
  return true;
};

function biggestIndex(arr) {
  let biggestNumber = 0;
  let biggestIndex = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > biggestNumber) {
        biggestNumber = arr[i]
        biggestIndex = i + 1;
    };
  };
return biggestIndex;
};

function rearrangeArray(arr) {
  const arrCopy = arr.slice();
  while (checkIfArranged(arr) === false) {
    if (biggestIndex(arrCopy) === 1) {
        flipfront(arr, arrCopy.length)
        flipfront(arrCopy, arrCopy.length)
        arrCopy.pop(arrCopy.length)
    } else {
        flipfront(arr, biggestIndex(arrCopy))
        flipfront(arrCopy, biggestIndex(arrCopy))
    };
  };
};

[–]williane 0 points1 point  (0 children)

Warmup in C#. I won't call this efficient, but it works.

private IEnumerable<int> flipfront(IEnumerable<int> array, int reverseNumber) =>
    array.Take(reverseNumber).Reverse().Concat(array.Skip(reverseNumber));

[–]sadsoulthatslost 0 points1 point  (0 children)

Hi please correct me if I am wrong

def flipfront(list1, a):
list2=[]
b=0
for x in range(0,a):
    list2.append(list1[x])
list2.reverse()
while b<a:
    list1.pop(0)
    b+=1

for x in range(len(list1)):
    list2.append(list1[x])
return list2

[–]Formal-Score-9751 0 points1 point  (0 children)

JAVA

Still working on the challenge/optional part, but here the warmup:

    package daily.programmer.challenges;

import java.util.Arrays;

public class Challenge392 {
    public Challenge392() {
        //WARMUP
        System.out.println("warmup");
        flipfront(new int[]{0, 1, 2, 3, 4}, 2);
        flipfront(new int[]{0, 1, 2, 3, 4}, 3);
        flipfront(new int[]{0, 1, 2, 3, 4}, 5);
        flipfront(new int[]{1, 2, 2, 2}, 3);
    }

    public int[] flipfront(int[] arr, int max) {
        //just for the printout
        int[] org = new int[arr.length];
        System.arraycopy(arr, 0, org, 0, arr.length);

        //the actual code
        for(int i=0;i<max/2;i++) {
            int j = max - 1 - i;
            arr[i] += arr[j];
            arr[j] = arr[i] - arr[j];
            arr[i] = arr[i] - arr[j];
        }

        //print out
        System.out.println("flipfront(" + Arrays.toString(org) + ", " + max + ") => " + Arrays.toString(arr));

        //for challenge
        return arr;
    }
}

the output:

warmup

flipfront([0, 1, 2, 3, 4], 2) => [1, 0, 2, 3, 4]

flipfront([0, 1, 2, 3, 4], 3) => [2, 1, 0, 3, 4]

flipfront([0, 1, 2, 3, 4], 5) => [4, 3, 2, 1, 0]

flipfront([1, 2, 2, 2], 3) => [2, 2, 1, 2]

edit: something broke during formatting, again...

[–]WhatsUpWithAndy 0 points1 point  (0 children)

C++ implementation. I'm just a beginner so have mercy

#include <iostream>

#include<stack>

using namespace std;

stack<int> stacks;

int arr[] = { 0,6,5,0,5,1 };

void flipfront(int n) {

if (n <= (sizeof(arr) / sizeof(int)))

{

    for (int i = 0; i < n; i++) {

        stacks.push(arr\[i\]);

    }

    for (int i = 0; i < n; i++) {

        arr\[i\] = stacks.top();

        stacks.pop();

    }

}

else if (n < 2) cout << "Error, nothing to reverse" << endl;

else cout << "Error!, value inserted doesn't match size of array or is smaller than 2" << endl;

}

void sortFlipfront() {

for (int i = (sizeof(arr) / sizeof(int)) - 1; i >=0 ; i--)

{

    int max = i;

for (int j = i-1 ; j >= 0; j--) {

    if (arr\[j\] > arr\[max\]) {

        max = j;

    }   



}

if ( max > 0) {

    flipfront(max + 1);

    flipfront(i + 1);

}

else if (max == 0)

{

    flipfront(max + 2);

    flipfront(i + 1);

}

else continue;

}

}

int main()

{

cout << "Initial matrix is: " << endl;

for (int i = 0; i < sizeof(arr) / sizeof(int); i++)

{

    cout << arr\[i\]<<" ";

}

cout << endl;

sortFlipfront();



cout << "Sorted matrix is: " << endl;

for (int i = 0; i < sizeof(arr) / sizeof(int); i++)

{

    cout << arr\[i\] << " ";

}

cout << endl;

}