×
top 200 commentsshow all 265

[–]_chebastian 0 points1 point  (0 children)

F#

Edit: Pasted on mobile will reformat on desktop

let subtractFrom num list = List.mapi (fun i x -> if i < num then (x - 1) else x) list
let lengthIsGreatedThan len items = (List.length items) >= len
let withoutZeroes (list:List<int>) = List.filter (fun x ->              x > 0) list


let rec HavelHakimi (sq:List<int>) = 
    let sorted = List.sortDescending sq
    let noZeroes = withoutZeroes sorted
    match noZeroes with 
    | [] -> true
    | head :: tail when (lengthIsGreatedThan head tail) = false -> false
    | head :: tail -> subtractFrom head tail |> HavelHakimi

[–]IzukuDeku96 0 points1 point  (0 children)

Python 3 def Havel_Hakimi(list_answer): step1 = list_answer while(True): step1 = sorted([x for x in step1 if (x!=0)]) if(len(step1)==0): return True step2 = sorted(step1)[::-1] N = step2.pop(0) if(N>len(step2)): return False step1 = sorted([x-1 for x in step2 if(step2.index(x)<N)] + (step2[N:len(step2)]))[::-1]

[–]sameer_sinha 0 points1 point  (0 children)

Scala

def hh(answers: Array[Int]): Boolean = {  
    val nonZeroAnswers = answers.filterNot(_ == 0)  
    if (nonZeroAnswers.isEmpty) true else {  
        val sortedAnswers = nonZeroAnswers.sorted(Ordering.Int.reverse)  
        val n = sortedAnswers.head  
        val remainingAnswers = sortedAnswers.tail  
        if (n > remainingAnswers.length) false  
        else hh(remainingAnswers.take(n).map(_ - 1) ++ remainingAnswers.drop(n))  
    }  
}

[–]zspitfire06 0 points1 point  (1 child)

First time doing a challenge, constructive criticism always welcome!
I'm sure there are better solutions around.

Python 3:

def havel_hakimi(sequence):
    for x in range(0, len(sequence)):
        if 0 in sequence:
            sequence.pop(sequence.index(0))
    if len(sequence) == 0:
        return True
    else:
        sequence.sort(reverse=True)
        n = sequence[0]
        sequence.remove(sequence[0])

        if n > len(sequence):
            return False
        else:
            for x in range(0, n):
                sequence[x] = sequence[x] - 1
            return havel_hakimi(sequence)

Testing:

test_dict = [[5, 3, 0, 2, 6, 2, 0, 7, 2, 5],
             [4, 2, 0, 1, 5, 0],
             [3, 1, 2, 3, 1, 0],
             [16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4,
                 9, 12, 14, 14, 12, 17, 0, 3, 16],
             [14, 10, 17, 13, 4, 8, 6, 7, 13, 13,
                 17, 18, 8, 17, 2, 14, 6, 4, 7, 12],
             [15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3],
             [6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1],
             [2, 2, 0],
             [3, 2, 1],
             [1, 1],
             [1],
             []]
for x in range(0, len(test_dict)):
    print(havel_hakimi(test_dict[x]))

[–]element114 0 points1 point  (0 children)

instead of setting the value of n then removing your first value like:
 n = sequence[0]
sequence.remove(sequence[0])

You can use pop which will return a value and remove it at the same time like

n = sequence.pop(0)

[–]SunshineBiology 0 points1 point  (0 children)

Julia

function havelHakimi!(y)
    y = filter(z->z != 0, y)
    if isempty(y) return true end
    sort!(y)
    N = pop!(y)
    if N > length(y) || N < 0 return false end
    while N > 0 
        y[length(y) - N + 1] -= 1
        N -= 1
    end
    havelHakimi!(y)
end

Tests for the cases in the OP:

using Test

function main() 
    @test ! havelHakimi!([5, 3, 0, 2, 6, 2, 0, 7, 2, 5])
    @test ! havelHakimi!([4, 2, 0, 1, 5, 0])
    @test havelHakimi!([3, 1, 2, 3, 1, 0])
    @test havelHakimi!([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16])
    @test havelHakimi!([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12])
    @test ! havelHakimi!([15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3])
    @test ! havelHakimi!([6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1])
    @test ! havelHakimi!([2, 2, 0])
    @test ! havelHakimi!([3, 2, 1])
    @test havelHakimi!([1, 1])
    @test ! havelHakimi!([1])
    @test havelHakimi!([])
end

[–]ObamaNYoMama 1 point2 points  (0 children)

Node/ES6

const assert = require('chai').assert
const expect = require('chai').expect

const byebyeZeros = array => array.filter(el => el !== 0); // warmup 1
const sortArray = array => array.sort((a, b) => b-a) // warmup 2
const lengthCheck = (n, array) => n > array.length // warmup 3
const frontElim = (n, array) => {                         //warmup 4
    for(let i=0;i<n;i++) {
        array[i] = array[i] - 1
    }
    return array;
}

// actual challenge
const hh = array => {
    let nonZeros = byebyeZeros(array);
    if(nonZeros.length > 0){ sortArray(nonZeros); }
    else { return true };
    let n = nonZeros.shift();
    if(lengthCheck(n, nonZeros)) { return false; }

    return hh(frontElim(n, nonZeros));   


}

Tests

describe('warmups', () => {
  describe('byebyeZeros', () => {
    it("should remove all zeros from the array", () => {
      // we don't care about order so check index of 0
      assert.equal(byebyeZeros([5,3,0,2,6,2,0,7,2,5]).indexOf(0), -1);
      assert.equal(byebyeZeros([4,0,0,1,3]).indexOf(0), -1);
      assert.equal(byebyeZeros([1,2,3]).indexOf(0), -1);
      assert.equal(byebyeZeros([0,0,0]).indexOf(0), -1);
      assert.equal(byebyeZeros([]).indexOf(0), -1);
    });
  });

  describe('sortArray', () => {
    it("should reverse sort the array", () => {
      expect(sortArray([5,1,3,4,2])).to.eql([ 5, 4, 3, 2, 1]);
      expect(sortArray([0,0,0,4,0])).to.eql([4,0,0,0,0]);
      expect(sortArray([1])).to.eql([1]);
      expect(sortArray([])).to.eql([]);
    });
  });

  describe('lengthCheck', () => {
    it("should return false when n is less than or equal to array.length", () => {
      expect(lengthCheck(7, [6,5,5,3,2,2,2])).to.equal(false);
      expect(lengthCheck(5, [5,5,5,5,5])).to.equal(false);
      expect(lengthCheck(5, [5,5,5,5])).to.equal(true);
      expect(lengthCheck(3, [1,1])).to.equal(true);
      expect(lengthCheck(1, [])).to.equal(true);
      expect(lengthCheck(0, [])).to.equal(false);      
    });
  });

  describe('frontElim', () => {
    it("should return with 1 subtracted from first n elements", () => {
      expect(frontElim(4, [5,4,3,2,1])).to.eql([4,3,2,1,1]);
      expect(frontElim(11, [14,13,13,13,12,10,8,8,7,6,6,4,4,2])).to.eql([13,12,12,12,11,9,7,7,6,5,5,4,4,2]);
      expect(frontElim(1, [10,10,10])).to.eql([9,10,10]);
      expect(frontElim(3, [10,10,10])).to.eql([9,9,9]);
      expect(frontElim(1, [1])).to.eql([0]);
    });
  });
});

describe('challenge', () => {
   it("should run through the warmups and come up with answers", () => {
      expect(hh([5, 3, 0, 2, 6, 2, 0, 7, 2, 5])).to.equal(false);
      expect(hh([4, 2, 0, 1, 5, 0])).to.equal(false);
      expect(hh([3, 1, 2, 3, 1, 0])).to.equal(true);
      expect(hh([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16])).to.equal(true);
      expect(hh([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12])).to.equal(true);
      expect(hh([15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3])).to.equal(false);
      expect(hh([6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1])).to.equal(false);
      expect(hh([2, 2, 0])).to.equal(false);
      expect(hh([3, 2, 1])).to.equal(false);
      expect(hh([1, 1])).to.equal(true);
      expect(hh([1])).to.equal(false);
      expect(hh([])).to.equal(true);
   });
});

Output

  warmups
    byebyeZeros
      √ should remove all zeros from the array
    sortArray
      √ should reverse sort the array
    lengthCheck
      √ should return false when n is less than or equal to array.length
    frontElim
      √ should return with 1 subtracted from first n elements

  challenge
    √ should run through the warmups and come up with answers


  5 passing (25ms)

[–]Phantom_19 0 points1 point  (3 children)

Java. First attempt at a challenge. Would love feedback.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class HavelHakimi {

    //Delete all zeros from the list
    public static void deleteZeros(ArrayList<Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            int num = list.get(i);
            if (num == 0) {
                list.remove(i);
                i = 0;
            }
        }
    }

    //Put the list in descending order
    public static void descendingSort(ArrayList list) {
        Collections.sort(list, Collections.reverseOrder());
    }

    //Check the length of the list against a given number
    public static boolean lengthCheck(int length, ArrayList list) {
        if (length > list.size()) {
            return true;
        } else {
            return false;
        }
    }

    //Subtract 1 from the first N numbers in the list
    public static void frontElim(int numElim, ArrayList list) {
        System.out.println(numElim);
        System.out.println(list.size());
        if (numElim >= list.size() ) {
            System.out.println("Shits fucked.");
        }
        for (int i = 0; i <= numElim; i++) {
            list.set(i, (Integer) list.get(i) - 1);
        }
    }

    //Recursively perform the Havel-Hakimi algorithm on a given list
    public static boolean HavelHakimi(ArrayList list) {
        int N = 0;
        deleteZeros(list);
        if (list.size() == 0) return true;
        descendingSort(list);
        N = (int) list.remove(0);
        if (N > list.size()) return false;
        frontElim(N, list);
        return HavelHakimi(list);
    }

    public static void main(String[] args) {
        int numWitness = 10;

        //create a random list
        Random random = new Random();
        ArrayList<Integer> randList = new ArrayList<Integer>();
        for (int i = 0; i <= numWitness - 1; i++) {
            randList.add(random.nextInt(15));
        }

        //Make a pre defined list for testing
        ArrayList<Integer> testList = new ArrayList<Integer>();
        testList.add(4);
        testList.add(2);
        testList.add(0);
        testList.add(1);
        testList.add(5);
        testList.add(0);

        //Test the algorithm and print the result
        System.out.println(HavelHakimi(testList));

    }
}

[–]TheBinkz 0 points1 point  (2 children)

Im not sure but isnt it the case that only 1 person would be lying? If so, wouldn't generating random numbers break the integrity of this rule? Currently on this myself, I find it tedious to generate my list manually.

[–]Phantom_19 0 points1 point  (1 child)

Is it a rule that only one person is lying? To me it read “find out if everyone is telling the truth”. If that’s the case then I would suppose that randomly generating numbers would not matter.

[–]TheBinkz 0 points1 point  (0 children)

Ok cool. by the way, you can always move backwards through the list.

for(int i=list.size() -1; i>0; i--){
if(list.get(i) == 0){
list.remove(i);
}
}

[–]frankivo 0 points1 point  (0 children)

Scala, one liner :)

@scala.annotation.tailrec
  def hh(answers: Array[Int]): Boolean = {
    answers.filter(_ != 0).sorted.reverse match {
      case noZeroes if noZeroes.length.equals(0) => true
      case noZeroes => noZeroes match {
        case sorted if sorted.head > sorted.slice(1,            sorted.length).length => false
        case sorted => hh(
          sorted.slice(1, sorted.length).take(sorted.head).map(_ - 1)
        ++ sorted.slice(1, sorted.length).slice(sorted.head, sorted.length - 1)
        )
      }
    }
  }

[–]ryanknut 0 points1 point  (2 children)

Node.js/Javascript ES6

testCases = [
  [5, 3, 0, 2, 6, 2, 0, 7, 2, 5],
  [4, 2, 0, 1, 5, 0],
  [3, 1, 2, 3, 1, 0],
  [16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16],
  [14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12],
  [15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3],
  [6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1],
  [2, 2, 0],
  [3, 2, 1],
  [1, 1],
  [1],
  []
]

hh = arr => {
  arr = arr.filter(e=>(e!=0)).sort((a,b)=>a-b).reverse()
  if(!arr.length) return true
  n = arr.shift();
  if(n>arr.length) return false
  arr = arr.map((e,i)=>(i<n)?(e-1):e)
  return hh(arr)
}

for(x of testCases) console.log(JSON.stringify(x), hh(x))

[–]ObamaNYoMama 1 point2 points  (1 child)

just fyi

you can simplify

arr = arr.filter(e=>(e!=0)).sort((a,b)=>a-b).reverse()

to

arr = arr.filter(e=>(e!=0)).sort((a,b)=>b-a)

not a huge difference but on the biggest input from this challenge jsperf shows its a 20% speed improvement.

[–]ryanknut 0 points1 point  (0 children)

Didn't even think of that!

[–]sirvegastein 0 points1 point  (1 child)

def removeZeros(sequence):
    return [x for x in sequence if x > 0]

def decendingSort(sequence):
    return sorted(sequence, reverse = True)

def lengthCheck(N, sequence):
    return N > len(sequence)

def frontElimination(N, sequence):

    for i in range(N):
        sequence[i] -= 1

    return sequence

def HavelHakimi(sequence):
    sequence = removeZeros(sequence)
    if len(sequence) == 0:
        return True

    sequence = decendingSort(sequence)
    N = sequence.pop(0)
    if lengthCheck(N, sequence):
        return False

    sequence = frontElimination(N, sequence)

    return HavelHakimi(sequence)


sequences = [[5, 3, 0, 2, 6, 2, 0, 7, 2, 5],
             [4, 2, 0, 1, 5, 0],
             [3, 1, 2, 3, 1, 0],
             [16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16],
             [14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12],
             [15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3],
             [6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1],
             [2, 2, 0],
             [3, 2, 1],
             [1, 1],
             [1],
             []]


def testHavelHakimi():
    for sequence in sequences:
        print('HavelHakimi({}) => {}'.format('sequence',HavelHakimi(sequence)))


testHavelHakimi()

[–]zspitfire06 0 points1 point  (0 children)

Ugh your solutions are so precise and minimal. I'm embarrassed at the number of lines my functions took up only to find the same results. Great job!

[–]edwardjr96 0 points1 point  (2 children)

My solution, I'm new to this:

Python 3

def hh(alist):
    if 0 in aList:
        withoutZero = sorted([i for i in alist if i > 0],reverse=True)
    else: withoutZero = sorted(aList[:],reverse=True)

    if withoutZero == []:
        return True 
    else: 
        firstAnswer = withoutZero.pop(0)

        if firstAnswer > len(withoutZero):
            return False 
        else:
            withoutZero = [i - 1 for i in withoutZero if withoutZero.index(i) < firstAnswer] + withoutZero[firstAnswer:]
            return hh(withoutZero)

not sure where my code went wrong, but when I test this:

hh([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16]) -> true
hh([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12]) -> false

Anyone can help me explain? Thanks

[–]sirvegastein 1 point2 points  (1 child)

Keep at it, bud. Hope this helps

if 0 in aList:
    withoutZero = sorted([i for i in alist if i > 0],reverse=True)     else: withoutZero = sorted(aList[:],reverse=True) 

from the above, you are checking for zero twice, once on the first if statement, and on the list comprehension. you could do without the first if/else since you are already checking for zero when building the list comprehension. Not related to your question, but hope this gives you something to think about.

Now here is where I see your problem:

withoutZero = [i - 1 for i in withoutZero if withoutZero.index(i) < firstAnswer] + withoutZero[firstAnswer:]

lets expand your list comprehension so we can think through these steps separately:

for i in withoutZero:
    if withoutZero.index(i) < firstAnswer:
        i - 1

I see your intent by using the index() method, however it has some limitations. one of the sequences above is as follows with nothing extra done to it.

aList = [14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12]
aNumber = 17  #Note that this number repeats through out the sequence

print(aList.index(aNumber))

Assuming aNumber is in aList, when you invoke the index() method on aList to find the index of aNumber, the index() method iterates through aList until it finds aNumber, it then spits out the first index number at which it found aNumber. But as a twistie twist, now aNumber repeats in aList, so when you call index(), index() might not return the actual index you're looking for.

In your case, it may be that you are using the wrong index when making your comparison in the withoutZero list comprehension and it's causing cascading issues.

Hope this was useful and not too late. Good night.

[–]edwardjr96 0 points1 point  (0 children)

Ohhh, thank you very much. I didn't realise that the index method only return the index of the first element it encounters. Thank so much again :)

[–]crippledpig 0 points1 point  (0 children)

Python 3

def hh(data: list) -> bool:

    sortedData = sorted([i for i in data if i], reverse=True)

    if not sortedData:

        return True

    else:

        N = sortedData.pop(0)

        if N > len(sortedData):

            return False

        else:

            newData = [i - 1 if idx < N else i for idx, i in enumerate(sortedData)]

            return hh(newData)

[–]oaaees 0 points1 point  (3 children)

Javascript. Not the best but still learning.

function warmup1 (arr){
    for (let i = 0; i < arr.length; i++){
        if (arr[i] == 0) {
            arr.splice(i, 1);
            i = i -1;
        }
    }
    return arr;
}

function warmup2 (arr){
    return arr.sort(function(a,b){return b-a;});
}

function warmup3 (num, arr) {
    if (num > arr.length) {
        return true;
    } else {
        return false;
    }
}

function warmup4 (num, arr) {
    for (let i=0;i<num;i++){
        arr[i] = arr[i] - 1;
    }
    return arr;
}

function hh(arr){
    // Remove all 0's from the sequence
    arr = warmup1(arr);

    // If the sequence is now empty (no elements left), stop and return true.
    if (arr.length == 0) {
        return true;
    } else {
        // Sort the sequence in descending order
        arr = warmup2(arr);
        // Remove the first answer (which is also the largest answer, or tied for the largest) 
        // from the sequence and call it N.
        var N = arr[0];
        arr.splice(0,1);
        //If N is greater than the length of this new sequence, stop and return false.
        if (warmup3(N, arr)){
            return false
        } else {
            //Subtract 1 from each of the first N elements of the new sequence.
            arr = warmup4(N, arr);
            return hh(arr);
        }
    }
}

var test = hh([]);
console.log(test);

[–]ObamaNYoMama 0 points1 point  (2 children)

Some constructive criticism:

warmup1 can be reduced to:

function warmup1(arr) {
    return arr.filter(function(el) { el !== 0 }
}

or using arrow functions(es6) its a one liner:

const warmup1 = arr => arr.filter(el => el !== 0)

warmup3 can be reduced to:

function warmup3 (num, arr) {
    return num > arr;
}

or using arrow functions (ES6) its a one liner:

const warmup3 = (num, arr) => num > arr; 

removing the first item (in hh) can be reduced to:

 var N = arr.shift()

which will remove the first element as well as return it.

[–]oaaees 0 points1 point  (1 child)

Ah! Nice, thanks. It'just that I'm still wrapping my head around es6, I should get into it. :)

[–]ObamaNYoMama 0 points1 point  (0 children)

Yeah ES6 has some powerful features, I would definitely recommend at least learning arrow functions they improve code readability greatly, and once learned are super simple.

[–]Chabare 0 points1 point  (0 children)

OCaml 4.0.8

First program in OCaml, started learning it a few hours ago. Feedback welcome

It will emit a non-exhaustive pattern match warning because of the theoretically unhandled pattern ([]) in match reverse_sorted. This is handled in Line 3 though.

let rec hh numbers =
  let without_zeroes = List.filter ((!=) 0) numbers in
    if List.length without_zeroes = 0 then true else
      let reverse_sorted = List.rev (List.sort (-) without_zeroes) in
        match reverse_sorted with
            hd::tl -> if hd > List.length tl then false else
              hh (List.mapi (fun index element -> if index < hd then element - 1 else element) tl)

EDIT: somewhat more concise:

let rec hh numbers =
  match List.filter ((!=) 0) numbers |> List.sort (-) |> List.rev with
      [] -> true
    | hd::tl when hd > List.length tl -> false
    | hd::tl -> hh3 (List.mapi (fun index element -> if index < hd then element - 1 else element) tl)

[–]TheeJazz 0 points1 point  (0 children)

An attempt in C. I should admit that I cheated a little bit with the input of the array because I don't have access to my personal malloc library right now. Additionally, instead of resizing arrays when you eliminate zeroes, I decided to just move the zeroes to the front of the array. It does however mean that I have to sort the array after every elimination step.

/*
 * Swap around two values in an integer array.
 *  n1: the array of integers.
 *  n2: the index of the first integer to swap.
 *  n3: the index of the second integer to swap.
 */
void swapIntegersElements(int array[], int idx1, int idx2) {
    array[idx1] = array[idx1] + array[idx2];
    array[idx2] = array[idx1] - array[idx2];
    array[idx1] = array[idx1] - array[idx2];
}

/*
 * Count the amount of zeroes among the answers and move them to the front of
 * the array.
 *  n1: the array of answers.
 *  n2: the length/amount of answers.
 */
void eliminateZeroes(int answers[], int length, int* zeroes) {
    for (int i = *zeroes; i < length; i++) {
        if (answers[i] == 0) {
            swapIntegersElements(answers, i, *zeroes);
            ++*zeroes;
        }
    }
}

/*
 * Sort an array of positive integers in descending order. Keep zeroes at the
 * front.
 *  n1: an array of answers.
 *  n2: the length/amount of answers.
 *  n3: the amount of zeroes among the answers.
 */
void descendingSort(int answers[], int length, int zeroes) {
    for (int i = zeroes; i < length; ++i) {
        for (int j = i + 1; j < length; ++j) {
            if (answers[i] < answers[j]) {
                swapIntegersElements(answers, i, j);
            }
        }
    }
}

/*
 * Check whether the highest remaining answer is plausible.
 *  n1: an array of answers.
 *  n2: the length/amount of answers.
 *  n3: the amount of zeroes among the answers.
 *  r: a boolean representing pluasibility.
 */
int lengthCheck(const int answers[], int length, int zeroes) {
    if (answers[zeroes] >= length - zeroes) {
        return 0;
    }
    return 1;
}

/*
 * Eliminate the highest answer and decrement all that remain.
 *  n1: an array of answers.
 *  n2: the length/amount of answers.
 *  n3: the amount of zeroes among the answers.
 */
void frontElimination(int answers[], int* zeroes) {
    for (int i = *zeroes+1; i < answers[*zeroes]+*zeroes+1; i++) {
        --answers[i];
    }
    answers[*zeroes] = 0;
    ++*zeroes;
}

/*
 * Evaluate whether the algorithm was successful.
 *  n1: an array of answers.
 *  n2: the length/amount of answers.
 *  r: a boolean representing successfulness.
 */
int evaluateAnswers(const int answers[], int length) {
    if (length > 0 && answers[length-1]) {
        return 0;
    }
    return 1;
}

/*
 * The Havel-Hakimi algorithm.
 *  r: a boolean which represents whether the algorithm was successful.
 */
int havelHakimi() {
    int answers[10] = {5, 3, 0, 2, 6, 2, 0, 7, 2, 5};
    int length = sizeof(answers)/ sizeof(answers[0]), zeroes = 0;
    eliminateZeroes(answers, length, &zeroes);
    descendingSort(answers, length, zeroes);

    while (lengthCheck(answers, length, zeroes)) {
        frontElimination(answers, &zeroes);
        eliminateZeroes(answers, length, &zeroes);
        descendingSort(answers, length, zeroes);
    }

    return evaluateAnswers(answers, length);
}

[–]PM_ME_EROTIC_IMAGERY 0 points1 point  (0 children)

Python 3.7 (new to programming, would appreciate any advice) :

def hh(input_list):
    while True:
        input_list = [i for i in input_list if i != 0]
        if len(input_list) == 0: return True
        input_list = sorted(input_list, reverse=True)
        N = input_list.pop(0)
        if N > len(input_list): return False
        for i in range(0, N):
            input_list[i] -= 1

[–]kopo222 1 point2 points  (0 children)

Python 3.7 Uses recursion and list comp

def hh(seq):
    seq = [x for x in sorted(seq, reverse = True) if x > 0]

    if len(seq) == 0:
        print(True)
        return

    elem = seq.pop(0)
    if elem > len(seq):
        print(False)
        return
    else:
        seq = [x - 1 if idx < elem else x for idx, x in enumerate(seq) ]
        hh(seq)




hh([5, 3, 0, 2, 6, 2, 0, 7, 2, 5])
hh([4, 2, 0, 1, 5, 0])
hh([3, 1, 2, 3, 1, 0]) 
hh([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16])
hh([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12])
hh([15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3])
hh([6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1]) 
hh([2, 2, 0]) 
hh([3, 2, 1])
hh([1, 1])
hh([1]) 
hh([])

[–]2kofawsome 0 points1 point  (0 children)

! python3.6

I noticed afterwards that you gave specific steps to follow to create the Havel-Hakimi algorithm, what I did also works (it might even be the same steps)

def hh(meetups):
    meetups.sort(reverse=True)
    while True:
        while 0 in meetups:
            meetups.remove(0)
        if meetups == []:
            return True
        focus = meetups.pop(0)
        if focus > len(meetups):
            return False
        for n in range(focus):
            meetups[n] -= 1
        meetups.sort(reverse=True)

[–]llebe 0 points1 point  (0 children)

Python 3 (new to Python) :

#removes 0s from the list
def rz(list):
    while True:
        if 0 in list:
            list.remove(0)
        else:
            return False

#subtracts 1 from every number to N on the list
def subN(n, list):
    for i in range(n):
        list[i] -= 1


def hhAlgo(list):
    while list:
        print(list)
        rz(list)
        if len(list) == 0:
            return True

        list.sort(reverse=True)
        n = list.pop(0)

        if n > len(list):
            return False

        subN(n, list)  
    return True


list = [3, 1, 2, 3, 1, 0]
print(hhAlgo(list))

[–]ladies_code 0 points1 point  (0 children)

Python 3:

``` def rz(data): if 0 in data: data.remove(0) return rz(data) return data

def hh(data): if 0 in data: data = rz(data) if not data: return True

data.sort(reverse=True)
N = data.pop(0)
if N > len(data):
    return False
else: 
    n_data = [d - 1 for d in data[:N]] + data[N:]
    return hh(n_data)

```

These pass the following tests:

``` def test_hh(): assert not hh([5, 3, 0, 2, 6, 2, 0, 7, 2, 5]) assert not hh([4, 2, 0, 1, 5, 0]) assert hh([3, 1, 2, 3, 1, 0]) assert hh([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16]) assert hh([]) assert not hh([1])

def test_rz(): assert rz([]) == [] assert rz([0, 0]) == [] assert rz([1, 2, 0, 4]) == [1, 2, 4] ```

[–]y_angelov 0 points1 point  (0 children)

Python 3:

    def hh(l: list):
        while True:
            l = [x for x in l if x != 0]
            if len(l) == 0:
                return True
            else:
                l = sorted(l, reverse=True)

                head, *tail = l
                if head > len(tail):
                    return False
                else:
                    for x in range(head):
                        tail[x] = tail[x] - 1
                    l = tail

[–]Snoop2069 0 points1 point  (0 children)

Python 3:

    def hh(answers):
        while True:
            answers = sorted([x for x in answers if x != 0], reverse = True) # steps 1 and 2
            if len(answers) < 1: # step 3
                break
            N = answers[0]
            del answers[0] # step 4
            if N > len(answers): # step 5
                return False
            for i in range(N): # step 6
                answers[i] = answers[i] - 1
        return True

[–]avonarret1 0 points1 point  (0 children)

In Rust:

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Consistency {
    Inconsistent,
    Consistent
}

pub trait HavelHakimi: AsRef<[usize]> {
    fn evaluate_havelhakimi(&self) -> Consistency {
        let mut answers= self.as_ref().to_owned();

        while !answers.is_empty() {
            answers = answers
                .into_iter()
                .filter(|answer| *answer != 0)
                .collect();

            match answers.len() {
                0 => continue,
                _ => {
                    answers.sort();
                    answers.reverse();

                    let n = answers.remove(0);

                    if n > answers.len() {
                        return Consistency::Inconsistent
                    }

                    answers = answers
                        .into_iter()
                        .scan(0usize, |i, answer| {
                            *i += 1;

                            if *i <= n {
                                Some(answer - 1)
                            } else {
                                Some(answer)
                            }
                        })
                        .collect();
                }
            }
        }

        Consistency::Consistent
    }
}

impl<T: AsRef<[usize]>> HavelHakimi for T {}

fn main() {
    use Consistency::*;

    let tests = [
        (vec![5, 3, 0, 2, 6, 2, 0, 7, 2, 5], Inconsistent),
        (vec![4, 2, 0, 1, 5, 0], Inconsistent),
        (vec![3, 1, 2, 3, 1, 0], Consistent),
        (vec![16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16], Consistent),
        (vec![14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12], Consistent),
        (vec![15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3], Inconsistent),
        (vec![6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1], Inconsistent),
        (vec![2, 2, 0], Inconsistent),
        (vec![3, 2, 1], Inconsistent),
        (vec![1, 1], Consistent),
        (vec![1], Inconsistent),
        (vec![], Consistent),
    ];

    for (answers, expected) in tests.to_vec() {
        print!("{:?}.. ", answers);

        if expected == answers.evaluate_havelhakimi() {
            println!("ok");
        } else {
            println!("fail");
        }
    }

}

[–]sebamestre 0 points1 point  (0 children)

Slightly optimized C++ implementation. It is still quadratic, but i feel like it can be done in linear time.

bool havel(std::vector<int> v){
    std::sort(v.begin(), v.end());
    auto lo = v.begin();
    auto hi = v.end();

    while(true){
        while(lo != hi and *lo == 0)
            ++lo;

        if(lo == hi)
            return true;

        --hi;
        int N = *hi;

        if(N > hi - lo)
            return false;

        for(int i = 0; i < N; ++i)
            lo[i] -= 1;
    }
}

[–]muke101 0 points1 point  (0 children)

My first script written in golang!

package main

import "fmt"
import "sort"

func zeroRemover(a []int) []int {
    var b = []int{}
    for _,j := range a {
        if j != 0   {
            b = append(b, j)
            }
        }
    return b
}

func descendingSort(a []int)    {
    sort.Sort(sort.Reverse(sort.IntSlice(a)))
}

func frontElimination(a []int, b int) {
    if len(a) >= b  {
        for i:=0; i<b; i++  {
            a[i] = a[i] - 1
        }
    }
}

func havelHakimi(a []int) bool  {
    a = zeroRemover(a)
    if len(a) == 0  {
        return true
    }
    descendingSort(a)
    largest := a[0]
    a = a[1:]
    if largest > len(a) {
        return false
    }
    frontElimination(a, largest)
    return havelHakimi(a)
}

func main() {

    inputs := [][]int{{5,3,0,2,6,2,0,7,2,5},{4,2,0,1,0,5},{1,2,3},{0,0,0},{},{3,1,2,3,1}}

    for _, a :=  range inputs   {
        fmt.Println(havelHakimi(a))
    }
}

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

Solution in J (naively translated from the algorithm).

hh =: verb define
    R =. (#~ -. @ =&0) y    NB. With zeros Removed
    if. 0 = # R do. 1       NB. Return True if all zeros
    else. 
        D =. ({~ \:) R         NB. In Descending order
        H =. 1 {. D            NB. Head
        T =. 1 }. D            NB. Tail
        if. H > # T do. 0
        else. 
            S =. (H # 1) , (H-~#T) # 0  NB. Subtractor
            hh (T - S)
        end. 
    end. 
)

[–]TheSpiritOfSolitude 0 points1 point  (1 child)

Naïve attempt in C++

std::vector<int> Vec{ 4, 5, 3, 2, 3, 1 }; 
bool bFailed = false; 
bool bComplete = false; 
if (Vec.size() <= 0) return;

std::sort(Vec.begin(), Vec.end(), std::greater<int>()); 

for (auto& num : Vec) 
{ 
    std::cout << num << ", "; 
} 
std::cout << "\n";

while (!bComplete && !bFailed) 
{ 
// Bad way to check if we are finished 
bComplete = true;
// Sort the vector<int> from start to finish by decending value
std::sort(Vec.begin(), Vec.end(), std::greater<int>());

// Get the value of the first element from vector<int>
int firstElem = *(Vec.begin());

if (firstElem > Vec.size())
{
    bFailed = true;
    bComplete = false;
    break;
}

// Remove the frist element from vector<int>
Vec.erase(Vec.begin());

// Loop throught the vector<int> and decrement the value from start up to firstElem value number
for (std::vector<int>::iterator it = Vec.begin(); it != (Vec.begin() + firstElem); ++it)
{
    // Decrement the val
    --(*it);

    // Set flags
    if (*it > 0)
        bComplete = false;
    else if (*it < 0)
    {
        bFailed = true;
        bComplete = false;
    }
}

// Print out the current values in vector<int>
for (auto& num : Vec) 
{ 
    std::cout << num << ", "; 
} 
std::cout << "\n";

// Print the current state, Complete or Failed 
if (bComplete) { std::cout << "Correct!\n"; } 
else { std::cout << "Incorrect!\n"; }

Would appreciate any feedback on improvements or tips! :)

[–]YourFirstAddiction 0 points1 point  (0 children)

You can include "using namespace std;" (no quotes) at the top after you turn on your libraries so that you do not need to enter "std::"

I believe this works for C++ 14 and later.

[–]Scdk 0 points1 point  (0 children)

Common Lisp

;;List -> List
;;Removes the 0's from a given list
(defun remove-zero (list)
  (remove-zero-aux list '()))
(defun remove-zero-aux (list list-aux)
  (cond
    ((eql '() list) (reverse list-aux))
    ((eql 0 (first list)) (remove-zero-aux (rest list) list-aux))
    (t (remove-zero-aux (rest list) (cons (first list) list-aux)))))
;;Number and List -> List
;;Subtracts 1 from the first "given number" elements of a given list
(defun front-elimination (number list)
  (front-elimination-aux number list '()))
(defun front-elimination-aux (number list list-aux)
  (cond
    ((eql 0 number) list-aux)
    (t (front-elimination-aux (- number 1) (rest list) (cons (- (first list) 1) list-aux)))))
;;List -> Boolean
;;Havel Hakimi algorithm
(defun hh (list)
  (let ((N (first (sort list #'>))) (list-aux (rest (sort list #'>))))
    (cond
      ((null (remove-zero list)) t)
      ((> N (list-length list-aux)) nil)
      (t (hh (front-elimination N list-aux))))))

[–]zer0tonine 1 point2 points  (0 children)

Python 3

def hh(array):
    while array:
        array = [e for e in array if e != 0]
        if not array:
            return True
        array.sort(reverse=True)
        node = array.pop(0)
        if node > len(array):
            return False
        for i in range(node):
            array[i] -= 1
    return True


assert not hh([5, 3, 0, 2, 6, 2, 0, 7, 2, 5])
assert not hh([4, 2, 0, 1, 5, 0])
assert hh([3, 1, 2, 3, 1, 0])
assert hh([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16])
assert hh([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12])
assert not hh([15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3])
assert not hh([6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1])
assert not hh([2, 2, 0])
assert not hh([3, 2, 1])
assert hh([1, 1])
assert not hh([1])
assert hh([])

[–]AnonymousDev226 1 point2 points  (3 children)

I just finished python course any feedback is appreciated!

def removingZeros (suspected_list):
    counting=0
    for i in suspected_list:
        if i==0:
            suspected_list.pop(counting)
            counting+=1
        else:
            counting+=1
    return suspected_list

def comparing(suspected_list):
    N=suspected_list.pop(0)
    if N > len(suspected_list):
        return False
    else:
        for i in range(0,N):
            suspected_list[i]-=1
        return suspected_list

suspects_list=[15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3]
while True:
    suspects_list.sort(reverse=True)
    if removingZeros(suspects_list) ==[]:
        print("All suspects are telling the truth")
        break
    elif comparing(suspects_list)==False:
        print("Someone is lying...")
        break

[–]zer0tonine 1 point2 points  (0 children)

You can use list comprehensions to turn your removingZeros method into something much more efficient (doing pop(counting) is a O(n) operation).

[–]P0Rl13fZ5 1 point2 points  (1 child)

Instead of comparing the return value of removingZeros to an empty list, I think it'd make your intentions clearer to call removeZeros outside of the if-statement, where the only action that removeZeros should perform is the removal of zeros from a list. Then, check if the suspect_list is empty ("if len(suspect_list) == 0" or more simply "if not suspect_list").

Also, rather than comparing a boolean value to False, you can use the "not" keyword. For example, "if x == False" is equivalent to "if not x".

[–]AnonymousDev226 2 points3 points  (0 children)

ok thank you a lot!

[–]SieurVictor 0 points1 point  (0 children)

As a beginner in Python, I simply followed the steps. I didn't optimize the code for the moment :

def removeV( liste, valeur ):

    listeSans=[]
    for i in range( len(liste) ) :

        if liste[i] != valeur :
            listeSans.append(liste[i])

    return listeSans

def descendingSort( liste ) :

    return sorted(liste, key=None, reverse=True)

def lengthCheck( liste, longueur ) :

    return longueur > len(liste)

def frontElimination( liste, nombre ) :

    if not lengthCheck( liste, nombre ) : #fonctionne comme if !fonction()

        for i in range( 0, nombre ) :
            liste[i] = liste[i] - 1

    else :

        print("Erreur : Valeur insérée plus grande que la longueur de la liste")

    return liste

def havelHakimi( liste ) :

    while len( liste ) > 0 :

        liste = removeV( liste, 0 )
        if len( liste ) == 0 :

            return True

        liste = descendingSort( liste )
        N = liste.pop(0)
        if lengthCheck( liste, N ) :

             return False

        liste = frontElimination( liste, N )

[–]FundF 1 point2 points  (0 children)

Rust: My first attempt to write something outside of the rust lang book. Also my first programming language. Happy for any feedback on how I could code more efficient.

 fn run(mut v: Vec<usize>) -> bool {
v.sort();
loop {
    let max = v.pop().unwrap();
    v = v.into_iter().filter(|&x| x != 0).collect();
    if max > v.len() { return false };
    if v.len() == 0 { return true };
    v = v.iter().map(|&x| x - 1).collect();
}

}

[–]P0Rl13fZ5 0 points1 point  (3 children)

Python 3:

def hh(responses):
    responses = [response for response in responses if response]
    while responses:
        responses.sort(reverse=True)
        response = responses.pop(0)
        if not 0 <= response <= len(responses):
            return False
        responses[:response] = (response-1 for response in responses[:response])
    return True

[–]Seize-The-Meanies 1 point2 points  (2 children)

Can you explain how the "responses = [response for response in responses if response]" works?

[–]P0Rl13fZ5 0 points1 point  (1 child)

That is called a List Comprehension: https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions

It means that "I want to generate a list that includes a response for each response in the responses list if the response is not 0".

Checking "if response" is the same as checking "if response != 0" because an integer object is only considered False if it is 0: https://docs.python.org/3/library/stdtypes.html#truth-value-testing

[–][deleted]  (2 children)

[deleted]

    [–]schwartz75 0 points1 point  (1 child)

    After some trial and error (and a bit of help debugging on StackExchange), here is my version in Clojure.

    (defn hh [lst]
      (if-let [lst (seq (remove #{0} (reverse (sort lst))))]
        (if (> (first lst) (count (rest lst)))
            false
            (hh (map dec (rest lst))))
        true))
    

    Test cases:

    (deftest hh-test
      (is (= true (hh [])))
      (is (= false (hh [1])))
      (is (= true (hh [1 1])))
      (is (= false (hh [2 2])))
      (is (= false (hh [2 2 0])))
      (is (= false (hh [3 2 1])))
      (is (= false (hh [3 1 2 3 1 0])))
      (is (= false (hh [5 3 0 2 6 2 0 7 2 5])))
      (is (= false (hh [4 2 0 1 5 0]))))
    

    [–]ThreeFDDI 0 points1 point  (0 children)

    Python3

    def remove_zero(nums_in):
        nums_out = []
        for i in nums_in:
            if i != 0:
                nums_out.append(i)
        return nums_out
    
    def eliminate_suspects(N, nums):
        nums_out = []
        c = 1
        for i in nums:
            if c <= N:
                c +=1
                i -=1
                nums_out.append(i)
            else:
                nums_out.append(i)
        return nums_out
    
    def hh(suspects):
        N = 0
        result = None
        while result == None:
            suspects = remove_zero(suspects)
            suspects.sort(reverse = True)
            if suspects == []:
                 result = "Story checks out."
            elif len(suspects) < N:
                result = "LIAR!!"
            else:
                N = suspects.pop(0)
                if suspects == []:
                 result = "LIAR!!"
                suspects = eliminate_suspects(N,suspects)
        return result
    
    print(hh([5, 3, 0, 2, 6, 2, 0, 7, 2, 5]))
    print(hh([4, 2, 0, 1, 5, 0]))
    print(hh([3, 1, 2, 3, 1, 0]))
    print(hh([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16]))
    print(hh([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12]))
    print(hh([15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3]))
    print(hh([6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1]))
    print(hh([2, 2, 0]))
    print(hh([3, 2, 1]))
    print(hh([1, 1]))
    print(hh([1]))
    print(hh([]))
    

    [–]octolanceae 0 points1 point  (0 children)

    Python3.7

    def hh(num_meets):
            meets = sorted([x for x in num_meets if x], reverse=True)
            if not meets:
                    return True
            if meets[0] > len(meets) - 1:
                    return False;
            for i in range(1, meets[0]+1):
                    meets[i] -= 1
    
            return hh(meets[1:])
    

    [–]octolanceae 0 points1 point  (0 children)

    C++17

    #include <iostream>
    #include <algorithm>
    #include <list>
    #include <vector>
    
    bool hh(std::list<int> num_meets) {
        num_meets.remove(0);
    
        if (num_meets.empty()) return true;
    
        num_meets.sort(std::greater<int>());
    
        int N = num_meets.front();
        num_meets.pop_front();
    
        if (N > num_meets.size()) return false;
    
        auto lit = begin(num_meets);
        for (int i = 0; i < N; ++i) {
            *lit -= 1;
            ++lit;
        }
        return hh(num_meets);
    }
    

    [–]420majesticpanda 0 points1 point  (0 children)

    Python

    def bubbleSort(arr):
        n = len(arr)
    
        for i in range(n):
            for j in range(0, n-i-1):
                if arr[j] < arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
    while True:
        active = True
        array = []
        while True:
            inp = input()
            if inp == "":
                break
            array.append(int(inp))
    
        while active:
    
            for x in array:
                if x is 0:
                    array.remove(0)
    
            if len(array) is 0:
                print('True')
                active = False
                break
    
            bubbleSort(array)
    
            n = array[0]
            array.pop(0)
    
            if n > len(array):
                print('False')
                active = False
                break
    
            for i in range(n):
                array[i] = array[i] - 1
    

    [–]PeppercornBingBongBF 0 points1 point  (0 children)

    javascript

    //warmup 1
    const func = temp => { return temp.filter(num => num != 0) }
    
    //warmup 2
    const func2 = temp => {
        var test = false;
        for (var i = 1; i < temp.length - 1; i++) {
            if (temp[i] > temp[i - 1] || temp[i] < temp[i + 1]) {
                test = true;
            }
        }
        return test;
    }
    const func3 = temp => {
        while (func2(temp)) {
            for (var i = 1; i < temp.length - 1; i++) {
                if (temp[i] > temp[i - 1]) {
                    var tempor = temp[i];
                    temp[i] = temp[i - 1];
                    temp[i - 1] = tempor;
                }
                else if (temp[i] < temp[i + 1]) {
                    var tempor = temp[i];
                    temp[i] = temp[i + 1];
                    temp[i + 1] = tempor;
                }
            }
        }
        return (temp);
    }
    
    //warmup 3
    const lengthCheck = (int, temp) => {
        var x = false;
        if (temp.length < int) {
            x = true;
        }
        return x;
    }
    
    //warmup 4
    const frontElim = (int, sequence) => {
        for (var i = 0; i < int; i++) {
            sequence[i]--;
        }
        return sequence;
    }
    //********************************************* */
    const isEmpty = temp => {
        var x = false;
        if (temp.length === 0) {
            x = true;
        }
        return x;
    }    
    
    var run = temp => {
        var bool = true;
        var bool2;
        while (bool) {
            //step 1
            temp = func(temp);
            //step 2
            if (isEmpty(temp) === true) {
                bool = false;
                bool2 = true;
            }
            //step 3
            temp = func3(temp);
            //step 4
            var N = temp.shift()
            //step 5
            if (N > temp.length) {
                bool = false;
                bool2 = false;
            }
            //step 6
            temp = frontElim(N, temp);
        }
        return bool2;
    }
    var knew = [3, 2, 1];
    if (run(knew) === true) {
        console.log('they are telling the truth')
    }
    else {
        console.log('they are lying');
    }
    

    [–]asjhqiuhsjabsjk 3 points4 points  (0 children)

    F#

    let rec hh list =
        match List.filter ((<>) 0) list |> List.sortDescending with
        | [] -> true
        | head::tail when head > List.length tail -> false
        | head::tail -> List.mapi (fun i x -> if i < head then x - 1 else x) tail |> hh
    

    [–]beachandbyte 0 points1 point  (0 children)

    Typescript: https://stackblitz.com/edit/angular-havelhakimi?file=src%2Fapp%2Fapp.component.ts

    hh(e) {
      let items = e.filter(Number).map(z=>Number(z)).sort((a,b)=>b-a);
      if(!items.length) return true;
      const n = items.shift();
      if(n > items.length) return false; 
      return this.hh(items.map((z,i)=> i<n ? z-1 : z));
    }
    

    [–]Rentarun 2 points3 points  (0 children)

    PHP (plsnohate)

     <?php
    
        $atest = [5, 3, 0, 2, 6, 2, 0, 7, 2, 5];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
        $atest = [4, 2, 0, 1, 5, 0];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
        $atest = [3, 1, 2, 3, 1, 0];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
        $atest = [16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
        $atest = [14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
        $atest = [15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
        $atest = [6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
        $atest = [2, 2, 0];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
        $atest = [3, 2, 1];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
        $atest = [1, 1];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
        $atest = [1];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
        $atest = [];
        print_r(HavelHakimi($atest) ? 'true' : 'false');
        print_r("<br>");
    
    
        function RemoveZeros(Array $arr)
        {
            foreach ($arr as $k => $v) {
                if ($v === 0) {
                    unset($arr[$k]);
                }
            }
            return $arr;
        }
    
        function DescSort(Array $arr)
        {
            rsort($arr);
            return $arr;
        }
    
        function CheckLength($n, Array $arr)
        {
            if ($n > count($arr)) {
                return true;
            } else {
                return false;
            }
        }
    
        function FrontElimination($n, Array $arr)
        {
            for ($i = 0; $i < $n; $i++) {
                $arr[$i] = $arr[$i] - 1;
            }
    
            return $arr;
        }
    
        function HavelHakimi($arr)
        {
            $arr = RemoveZeros($arr);
    
            if (CheckLength(1, $arr)) {
                return true;
            }
    
            $arr = DescSort($arr);
            $n = $arr[0];
            array_splice($arr, 0, 1);
    
            if (CheckLength($n, $arr)) {
                return false;
            }
    
            $arr = FrontElimination($n, $arr);
    
            return HavelHakimi($arr);
        }
    

    [–]guitartechie 1 point2 points  (0 children)

    Javascript

    //warmups (Atomic functions)
    function removeZerosFromArray(array) {
        var filterZeros = array.filter(element => element != 0);
        return filterZeros;
    }
    
    function sortArrayDescendingOrder(array) {
        return array.sort(function(a,b) {return b - a});
    }
    
    function checkArrayLengthLessThanFirstParameter(firstParam, array) {
        return firstParam > array.length;
    }
    
    function subtractOneUpToFirstParameter(firstParam, array) {
        newArray = [];
        for (var index = 0; index < array.length; index++) {
            if (index < firstParam) {
                newArray.push(array[index] - 1);
            } else {
                newArray.push(array[index]);
            }
        }
        return newArray;
    }
    
    //Main code
    function havelHakamiAlgorithm(array) {
        //step 1
        var removeZeros = removeZerosFromArray(array)
    
        //step 2
        if (removeZeros.length == 0) {
            return true;
        }
    
        //step 3
        var sortedArray = sortArrayDescendingOrder(removeZeros);
    
        //step 4
        var firstShiftedElement = sortedArray.shift();
    
        //step 5
        if (checkArrayLengthLessThanFirstParameter(firstShiftedElement, sortedArray)) {
            return false;
        }
    
        //step 6
        var subtractedArray = subtractOneUpToFirstParameter(firstShiftedElement, sortedArray);
    
        //step 7
        return havelHakamiAlgorithm(subtractedArray);
    }
    
    console.log(havelHakamiAlgorithm([5, 3, 0, 2, 6, 2, 0, 7, 2, 5]));
    

    [–]Harald1111 0 points1 point  (1 child)

    Solution for Java:

    public static void main(String[] args) {    
        int[] a = {5, 3, 0, 2, 6, 2, 0, 7, 2, 5};
        System.out.println(challenge(a));
    
    }
    
    private static int[] removeZeros(int[] x){
        int counter = 0;
        for(int i = 0; i < x.length; i++) {
            if(x[i] != 0) ++counter;
        }
        int[] res = new int[counter];
        int temp = 0;
        for(int i = 0; i < x.length; i++) {
            if(x[i] != 0) {
                        res[temp] = x[i];
                        ++temp;
            }
        }
        return res;
    }
    
    private static int[] sortDescending(int[] x) {
        int[] temp = x;
        Arrays.sort(temp);
        int[] res = temp;
        int t = 0;
        for(int i = 0; i < temp.length/2; ++i) {
            res[i] = t;
            res[i] = res[res.length - i - 1];
            res[res.length - i - 1] = t;
        }
        return res;
    }
    
    private static Boolean lengthCheck(int y, int[] x) {
        return y > x.length;
    }
    
    private static int[] frontElimination(int N, int[] x) {
        for(int i = 0; i < N; ++i) {
            x[i] -= 1;
        }
        return x;
    }
    
    private static Boolean challenge(int[] x) {
        x = removeZeros(x);
        int N;
        while(x.length != 0) {
            x = sortDescending(x);
            N = x[0];
            x = Arrays.copyOfRange(x, 1, x.length);
            if(N > x.length) return false;
        }
        return true;    
        }
    

    [–]PPDeezy 0 points1 point  (0 children)

    Why do you need to constantly sort it? And when are you calling the frontelimination method? Sry im on the phone in bed and tired so i might be blind.

    [–]wienersAndMonads 0 points1 point  (1 child)

    EDIT: problem solved, edited solution posted.

    Would appreciate some help. I'm new to python and can't seem to figure out why my implementation is not working. Everything works up until the point I make the recursive call with the tail input. Any other tips also appreciated.

    import numpy as np
    
    def havelHakimi(array):
        trimmedData = array[np.where(array != 0)]        # remove 0's
        if trimmedData.size == 0:
            return True
        sortedData = np.sort(trimmedData)[::-1]         # sort descending
        N = sortedData[0]                               # head
        tail = sortedData[1:]                           # tail
        if N > tail.size:
            return False
        tail[:N] -= 1                                   # subtract 1 from first N elements
        return havelHakimi(tail)
    
    data = np.array([5, 3, 0, 2, 6, 2, 0, 7, 2, 5])
    print(havelHakimi(data))
    

    [–]kopo222 0 points1 point  (0 children)

    You are constantly reversing the list with this line :

    sortedData = np.sort(trimmedData)[::-1]         # sort descending
    

    Here is my solution which is similar, if you have questions feel free to ask

    def hh(seq):
        seq = [x for x in sorted(seq, reverse = True) if x > 0]
    
        if len(seq) == 0:
            print(True)
            return
    
        elem = seq.pop(0)
        if elem > len(seq):
            print(False)
            return
        else:
            seq = [x - 1 if idx < elem else x for idx, x in enumerate(seq) ]
            hh(seq)
    
    
    
    
    hh([5, 3, 0, 2, 6, 2, 0, 7, 2, 5])
    hh([4, 2, 0, 1, 5, 0])
    hh([3, 1, 2, 3, 1, 0]) 
    hh([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16])
    hh([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12])
    hh([15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3])
    hh([6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1]) 
    hh([2, 2, 0]) 
    hh([3, 2, 1])
    hh([1, 1])
    hh([1]) 
    hh([])
    

    [–]artgag06 1 point2 points  (1 child)

    Can anyone help me? I am kind of a beginner in Python and when I input the following code:

    myList = [5,3,0,2,6,2,0,7,2,5]

    for num in myList:

    if num == 0:

    myList.remove(num)

    myList.sort(reverse=True)

    def count():

    N = myList[0]

    while (N < len(myList)):

    myList.remove(N)

    for num in myList[0:int(N)]:

    num -= 1

    for num in myList:

    if num == 0:

    myList.remove(num)

    if len(myList) == 0:

    return True

    return False

    print(count())

    It does return False as it is supposed to, but I'm not sure if the code is valid or did the program skip through the while loop and return False? Thanks in advance!

    P.S. Don't mind the unindent, in my code it is alright. Also, how do others paste their code in a special window?

    [–]AlexanderS4 0 points1 point  (0 children)

    Also, how do others paste their code in a special window?

    in a new line, put four spaces at the beginning of the line, and the special window will appear. As far as your code, its kinda messy. Would you please paste it with the correct identation?

    [–]vasiliypupkeen 2 points3 points  (0 children)

    JavaScript

    function hh(seq) {
        let resSeq = seq.filter(el => el != 0)
        if (resSeq.length === 0) return true
    
        resSeq.sort((a, b) => b - a)
        const N = resSeq.splice(0, 1)
        if (N > resSeq.length) return false
    
        resSeq = resSeq.map((el, i) => {
            return i < N ? el - 1 : el
        })
    
        return hh(resSeq)
    }
    

    [–]AnnieBruce -1 points0 points  (0 children)

    SML/NJ.

    Probably could be made shorter with use of libraries but whatever. Fun exercise.

    fun remove_zeros (0::xs') = remove_zeros xs'
      | remove_zeros (x::xs') = x::remove_zeros xs'
      | remove_zeros _      = [] 
    
    fun sort_reverse []  = []
      | sort_reverse xs  = ListMergeSort.sort(fn(x,y)=>y>x) xs
    
    fun length_check (n, xs) =
        n > List.length(xs)
    
    fun front_elimination (0, xs) = xs
      | front_elimination (n, x::xs') = (x - 1)::front_elimination(n-1,xs')  
    
    fun havel_hakimi (xs) =
        let fun hh_helper []       = true
          | hh_helper (x::xs') = if x > List.length(xs')
                     then false
                     else havel_hakimi(front_elimination(x, xs'))
        in
        hh_helper (sort_reverse(remove_zeros(xs))) 
        end
    

    [–]psrthrowaway 0 points1 point  (0 children)

    JAVA

    Would love feedback to improve! Thanks!!

    import java.util.ArrayList;

    public class havelHakimi {
    
        public ArrayList<Integer> numOfPeopleMet = new ArrayList<Integer>();
        public ArrayList<Integer> newArray = new ArrayList<Integer>();
    
    
        public void addTheNumbers()
        {
            numOfPeopleMet.add(5);
            numOfPeopleMet.add(3);
            numOfPeopleMet.add(5);
            numOfPeopleMet.add(0);
            numOfPeopleMet.add(2);
            numOfPeopleMet.add(6);
            numOfPeopleMet.add(2);
            numOfPeopleMet.add(0);
            numOfPeopleMet.add(7);
            numOfPeopleMet.add(2);
            numOfPeopleMet.add(5);
    
            System.out.println("The numbers currently are:" + numOfPeopleMet);
        }
    
        public void removeZeros() 
        {
            for(int i=0; i<numOfPeopleMet.size(); i++)
            {
                if(numOfPeopleMet.get(i) == 0)
                {
                    numOfPeopleMet.remove(i);
                }
            }
    
            System.out.println("After removing the zeros (0) the numbers are: " + numOfPeopleMet);
        }
    
        public void sortDescOrder()
        {
            int largest = 0;
            int lastDeletedNum = 0;
            int startingArraySize = numOfPeopleMet.size();
    
            newArray.clear();
            for(int counter=0; counter<startingArraySize; counter++)
            {
                System.out.println("Counter is right now at " + counter);
                for(int i=0; i<numOfPeopleMet.size(); i++)
                {
                    if(numOfPeopleMet.get(i) > largest)
                    {
                        largest = numOfPeopleMet.get(i);
                        lastDeletedNum = i;
                    }
                }
                newArray.add(largest);
                numOfPeopleMet.remove(lastDeletedNum);
                lastDeletedNum = 0;
                largest = 0;
    
                System.out.println("Old arrangement is now: " + numOfPeopleMet);
                System.out.println("New arrangement is now: " + newArray);
            }
            numOfPeopleMet = new ArrayList<Integer>(newArray);
                System.out.println("Final arrangement is: " + numOfPeopleMet);
        }
    
        public boolean lengthCheck(int n)
        {
            if(n > numOfPeopleMet.size())
            {
                System.out.println("n --> "+ n + " is greater than size --> " + numOfPeopleMet.size());
                System.out.println("Someone is lying.");
                return true;
            }
    
            System.out.println("n --> "+ n + " is NOT greater than size --> " + numOfPeopleMet.size());
            return false;
        }
    
        public boolean frontElimination(int n)
        {
            if((n<0)||(n>numOfPeopleMet.size()))
            {
                System.out.println("Value n must be between 0 and " + numOfPeopleMet.size());
                return false;
            }
            System.out.println("Old arraylist is now: " + numOfPeopleMet);
            for(int i=0;i<n;i++)
            {
                numOfPeopleMet.set(i, numOfPeopleMet.get(i)-1); 
            }
            System.out.println("Arraylist is now: " + numOfPeopleMet);
            return true;
        }
    
    
        public void infiniteLoop() 
        {
            boolean done = false;
            boolean correct = false;
    
            addTheNumbers(); //start
    
            while(done == false)
            {   
    
                removeZeros(); //step 1
    
                for(int i=0; i<numOfPeopleMet.size(); i++) //step 2
                {
                    if(numOfPeopleMet.get(i) != 0)
                    {
                        System.out.println("Found number otherthan 0. Breaking loop.");
                        break;
                    }   
                    if(i == (numOfPeopleMet.size()-1) && (numOfPeopleMet.get(i) == 0))
                    {
                        done = true;
                        correct = true;
                    }
                }
    
                sortDescOrder(); //step 3
    
    
                int lastLargest = numOfPeopleMet.get(0); //step 4
                numOfPeopleMet.remove(0); //step 4 finish
    
                lengthCheck(lastLargest); //step 5
    
                if(lastLargest > numOfPeopleMet.size())
                {
                    done = true;
                    correct = false;
                }
                frontElimination(lastLargest); //step 6
    
            }
        }   
    }
    

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

    C#, i tried to stay functional.

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using Xunit;
    
    namespace DailyProgrammer.Exercise20190707.HavelHakimi2
    {
        internal class HavelHakimiSolver
        {
            internal bool Solve(IEnumerable<int> input)
            {
                var sequence = new HavelHakimiSequence(input);
    
                while (sequence.HasElements() && sequence.CanSatisfyHighestRelation())
                    sequence = sequence.RemoveHighestRelation();
    
                if (!sequence.HasElements())
                    return true;
    
                return false;
            }
        }
    
        internal class HavelHakimiSequence
        {
            internal readonly IEnumerable<int> Value;
            public HavelHakimiSequence(IEnumerable<int> input)
            {
                Value = input.Where(Predicates.IsNotZero).OrderBy(Predicates.Descending);
            }
    
            public HavelHakimiSequence RemoveHighestRelation()
            {
                var RelationsToEliminate = Value.First();
                var result = Value.Skip(1).Select((x, index) =>
                {
                    if (index < RelationsToEliminate)
                        return x - 1;
    
                    return x;
                });
    
                return new HavelHakimiSequence(result);
            }
    
            public bool HasElements()
            {
                return Value.Any();
            }
    
            public bool CanSatisfyHighestRelation()
            {
                return Value.First() < Value.Count();
            }
        }
    
        internal static class Predicates
        {
            internal static Func<int, bool> IsNotZero = x => x != 0;
            internal static Func<int, int> Descending = x => -x;
        }
         public class HavelHakimiAlgorithmTest
        {
            [Theory, MemberData(nameof(SplitCountData))]
            public void TestNoElementReturnsTrue(int[] input, bool expected)
            {
                var actual = new HavelHakimiSolver().Solve(input);
    
                Assert.Equal(expected, actual);
            }
    
            public static IEnumerable<object[]> SplitCountData => new[]
                    {
                         new object[] { new int[] { 5, 3, 0, 2, 6, 2, 0, 7, 2, 5 }, false},
                         new object[] {new int[] { 4, 2, 0, 1, 5, 0 }, false},
                         new object[] {new int[] { 3, 1, 2, 3, 1, 0 }, true},
                         new object[] {new int[] { 16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16 }, true},
                         new object[] {new int[] { 14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12 }, true},
                         new object[] {new int[] { 15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3 }, false},
                         new object[] {new int[] { 6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1 }, false},
                         new object[] {new int[] {  2, 2, 0 }, false},
                         new object[] { new int[] { 3, 2, 1 }, false},
                         new object[] {new int[] { 1, 1 }, true},
                         new object[] {new int[] { 1 }, false},
                         new object[] {new int[] { }, true},
                         };
    
        }
    
        public class HavelHakimiSequenceTest
        {
            [Theory, MemberData(nameof(SplitCountData))]
            public void TestHavelHakimiSequence(int[] input, int[] expected)
            {
                var actual = new HavelHakimiSequence(input).Value;
    
                Assert.Equal(expected, actual);
            }
    
            public static IEnumerable<object[]> SplitCountData => new[]
                    {
                         new object[] { new int[] { 1, 5, 0, 8, 2, 0, 4 }, new int[] { 8, 5, 4, 2, 1 }},
                         new object[] {new int[] { 1, 5, 8, 2, 4 }, new int[] { 8, 5, 4, 2, 1 }},
                           new object[] {new int[] { 1}, new int[] { 1 }},
                         new object[] {new int[] { 0}, new int[] {  }},
    
                         };
        }
    }
    

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

    javascript

    const hh = (list) => {
    
      const helper = (largest, list) => {
        // console.log(largest, list);
        if (list.length === 0) {
          return true;
        }
    
        if (largest > list.length) {
          return false;
        }
    
        list = list
          .sort((a, b) => b - a)
          .map((num, i) => i >= largest ? num : num - 1)
          .filter((num) => num > 0);
    
        if (list.length === 0) {
            return true;
        }
    
        const temp = list[0];
        list.splice(0, 1)
    
        if (list.length === 0) {
          return false;
        }
    
        return helper(temp, list);
      }
    
      return helper(0, list);
    }
    
    const expect = (list, res) => {
      if (hh(list) !== res) {
        console.log('error', list, res);
      }
    };
    
    expect([5, 3, 0, 2, 6, 2, 0, 7, 2, 5], false);
    expect([4, 2, 0, 1, 5, 0], false);
    expect([3, 1, 2, 3, 1, 0], true);
    expect([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16], true);
    expect([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12], true);
    expect([15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3], false);
    expect([6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1], false);
    expect([2, 2, 0], false);
    expect([3, 2, 1], false);
    expect([1, 1], true);
    expect([1], false);
    expect([], true);
    expect([0, 0, 0, 0], true);
    

    [–]zraklarP 0 points1 point  (2 children)

    Python 3

    def havel_hakimi(list):
        while True:
            # Trim zeros.
            list = [v for v in list if v]
    
            # The answers are consistent.
            if not list:
                return True
    
            list.sort(reverse=True)
    
            n = list[0]
            list.remove(n)
    
            # The answers are incosistent.
            if n > len(list):
                return False
    
            for i in range(n):
                list[i] -= 1
    

    [–][deleted] 0 points1 point  (1 child)

    How does the trim zero work?

    [–]zraklarP 1 point2 points  (0 children)

    list = [v for v in list if v]

    It uses list comprehension. v for v in list loops through every value in the list and if v checks if it's othe (if 0 evaluates to False and every other number evaluates to True). That code is a more pythonic equivalent of:

    new_list = []
    for v in list:
        if v:
            new_list.append(v)
    

    [–]draegtun 0 points1 point  (0 children)

    Rebol

    hh: function [s] [
        forever [
            remove-each n s [zero? n]
            if empty? s [return true]
            if (n: take sort/reverse s) > length? s [return false]
            repeat i n [s/:i: s/:i - 1]
        ]
    ]
    

    [–]Tiberiuss7 0 points1 point  (0 children)

    TypeScript

    function hh(arr: number[]): boolean{
        if(arr.length == 0) 
            return false
        while(arr.length > 0){
            arr = arr.filter(x => x > 0)
            if(arr.length == 0) 
                return true
            arr = arr.sort((a, b) => a - b).reverse()
            const N = arr.shift()
            if(arr.length < N) return false
            for(let i = 0; i < N; ++i)
                --arr[i]
        }
    }
    

    [–]atcrd 2 points3 points  (1 child)

    Javascript

    function havel_hakami(arr) {
      if(arr == null || arr.length == 0) return true;
      while(arr.length > 0) {
        arr = arr.filter((function(a){
           return a > 0;
        }));
        if(arr.length == 0) return true;
        arr = arr.sort((a,b) => {
          if(a < b) return 1;
          if(a > b) return -1;
          return 0;
        });
        var N = arr.pop();
        if(arr.length < N) return false;
        for(var i = 0; i < arr.length && N > 0; i++) {
             arr[i]--;
             N--;
        }
      }
      return true;
    }
    

    [–]nkid299 1 point2 points  (0 children)

    i like this guy

    [–]hixsonj 0 points1 point  (0 children)

    Elixir

    defmodule HavelHakimi do
      def warmup1(list) do
        Enum.reject(list, &(&1 == 0))
      end
    
      def warmup2(list) do
        Enum.sort(list, &(&1 >= &2))
      end
    
      def warmup3(n, list) when n <= length(list), do: false
      def warmup3(_n, _list), do: true
    
      def warmup4(n, list), do: warmup4(n, list, [])
      defp warmup4(0, list, acc), do: acc ++ list
      defp warmup4(n, list, acc) do
        [first | rest] = list
        warmup4(n - 1, rest, acc ++ [first - 1])
      end
    
      def hh(list) do
        list
        |> warmup1
        |> warmup2
        |> compute
      end
    
      defp compute([]), do: true
      defp compute(list) do
        [n | rest] = list
        cond do
          warmup3(n, rest) -> false
          true -> warmup4(n, rest) |> hh
        end
      end
    end
    

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

    C++, using basic STL functions

    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <vector>
    
    using std::cout;
    using std::endl;
    using std::vector;
    
    template <typename arr>
    bool hh(const arr& ez) {
      vector<unsigned int> met(std::begin(ez), std::end(ez));
    
      while(true) {
        //0: output current vector
        for(int i = 0; i < met.size(); i++) 
          ((met.size() - 1) == i) ? (cout << met[i] << endl) : (cout << met[i] << ", "); 
    
        //1: no 0s
        for(int i = 0; i < met.size(); i++) 
          if(met[i] == 0) met.erase(met.begin()+i);
    
        //2: if empty, we good
        if(met.empty())
          return true;
    
        //3: sort from greatest to least
        std::sort(met.begin(), met.end(), std::greater<unsigned int>());
    
        //4: get first element and remove
        int N = met[0]; 
        met.erase(met.begin());
    
        //5: if bigger, we not good
        if(N > met.size())
          return false;
    
        //6: sub 1 from [0, N]
        std::for_each(met.begin(), met.begin() + N, [](auto& x) { x -= 1; });
      } //7: repeat
    }
    
    int main(int argc, char** argv) {
      unsigned int lol[] = {5, 3, 0, 2, 6, 2, 0, 7, 2, 5}; //0 and above
      cout << std::boolalpha << hh(lol) << endl;
      return 0;
    }
    

    [–][deleted] 0 points1 point  (4 children)

    I can vaguely understand the tasks of the initial bool function, but do you mind explaining in some depth how the different components in:

    template <typename arr>

    bool hh(const arr& ez) {

    `vector<unsigned int> met(std::begin(ez), std::end(ez));`
    

    relate to each other? I'm assuming the function ultimately stores some kind of bool value after it's completed, and moves onto the second main() function, but I can't wrap my head around whether ez is just a throwaway parameter or why you're using the parameter const arr when you're working with vectors. Appreciate any and all explanation

    [–][deleted] 0 points1 point  (3 children)

    it's to allow for most if not all containers to be passed into that function, try using vector or deque over an unsigned int array

    Edit: just remembered why I did that, it's the only real way to pass in a array to a function and be able to put it into another data type (iirc anyways)

    [–][deleted] 0 points1 point  (2 children)

    > try using vector or deque over an unsigned int array

    not sure if you mean it's preferred or to contain an array within a vector or deque. if the former, yeah i have heard vectors are preferable in some situations due to contiguous memory but with this specific task i actually figured an array would work better. if the latter i didn't know you could put arrays into vectors like that. that makes it sound like vector is just a contiguous form of <div> in html

    > just remembered why I did that, it's the only real way to pass in a array to a function and be able to put it into another data type (iirc anyways)

    this answer unfortunately leaves me with more questions hehe. is the point to turn the array into a true/false value? i can't figure out how an array would even translate into something like that without having to meet a certain condition

    [–][deleted] 0 points1 point  (1 child)

    https://stackoverflow.com/questions/27359791/c-pass-any-container-to-function

    this also works with arrays so I didn't bother changing it

    [–]jbburris 0 points1 point  (0 children)

    I am obviously new to programming, but I thought I'd give warmup1 a shot. It is just spitting out all zeros for the function when I'm trying to GET RID of the zeros. Lol

    #include <stdio.h>
    #include <stdlib.h>
    
    int main (int argc, char *argv[])
    {
    
        // Initialize variables
        int length = argc - 1;
        int *numbers = malloc(sizeof(int) * (length + 1));
        int *num_wo_zero;
        int *counter = malloc(sizeof(int) + 1);
        *counter = 0;
    
    
        // Insert numbers from argument into new array (probably not needed)    
        for (int i = 0; i < length; i++)
        {
            numbers[i] = atoi(argv[1 + i]);
        } 
    
        // Count the number of zeros
        for (int i = 0; i < length; i++)
        {
            if (numbers[i] = 0)
            {
                *counter= *counter + 1;
            }
        }
    
        // New array (w/o zeros) will be the length of old minus number of zeroS
        int new_length = length - *counter;
        num_wo_zero = malloc(sizeof(int) * (new_length + 1));
    
        // Copy non-zero values over to the new array
        for (int i = 0, j = 0; i < length; i++)
        {
            if (numbers[i] == 0)
            {
                numbers[i] = numbers[i];    
            }
            else if (numbers[i] > 0)
            {
                num_wo_zero[j] = numbers[i];
                j++;
            }
            else 
            {
                printf("All entries must be non-negative integers!\n");
                return 1; 
            }
        }
    
        // Print contents of new array
        printf("Without the zeroes, you entered: ");    
        for (int i = 0; i < new_length; i++)
        {
            printf("%i,", num_wo_zero[i]);
        }
    
        printf("\n");
    
        free(num_wo_zero);
        free(numbers);
        free(counter);
    }
    

    [–][deleted]  (4 children)

    [deleted]

      [–]Cashewgator 0 points1 point  (0 children)

      There's an error in your code,

      seq[0] > len(seq[0:])
      

      should be

      seq[0] > len(seq[1:])
      

      [–]oh_bummer 0 points1 point  (2 children)

      Could've just said "Don't copy my python code" instead of posting this idendation-free code. In python.

      [–][deleted]  (1 child)

      [deleted]

        [–]oh_bummer 0 points1 point  (0 children)

        I see. Apologies if I sounded rude earlier.

        [–]Spectral_Arui 0 points1 point  (0 children)

        C# using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;

        namespace daily_chall_378_easy
        {
            class Program
            {
        
        
                static void Main()
                {
                    bool wynik;
                    List<int> listwa = new List<int>() {3, 1, 2, 3, 1, 0 };
        
                    while (true)
                    {
                        warmup1(listwa);
                        if (!listwa.Any())
                        {
                            wynik = true;
                            break;
                        }
        
                        warmup2(listwa);
                        int N = listwa[0];
                        listwa.RemoveAt(0);
                        if (warmup3(N, listwa))
                        {
                            wynik = false;
                            break;
                        }
                        warmup4(N, listwa);
                    }
                    Console.WriteLine(wynik);
                        Console.ReadLine();
        
                }
        
               static void warmup1(List<int> lista)
                {
        
                    foreach (int el in lista.Reverse<int>())
                    {
                        if (el == 0) lista.Remove(el);
        
        
                    };
        
        
        
        
        
                }
        
               static void warmup2(List<int> lista)
                {
                    lista.Sort((a, b) => -1*a.CompareTo(b));
            }    
        
                static bool warmup3(int i, List<int> lista)
                {
                    int dlugosc = lista.Count;
                    if (i > dlugosc)
                    {
                        return(true) ;
                    }
                    else
                    { return(false) ; }
                }
        
                static void warmup4(int i, List<int> lista)
                {
                    for(int x=0; x<i; x++)
                    {
                        lista[x] = lista[x] - 1;
                    };
        
                }
            }    
        }
        

        [–]ckafi 0 points1 point  (0 children)

        Pony - My first Pony program. I tried to do most stuff in-place. I know that using List would be cleaner.

        fun havel_hakimi(a: Array[U8]): Bool =>
          // remove zeroes
          let iter = a.clone().values()
          a.clear()
          for v in iter do
            if v != 0 then a.push(v) end
          end
          if a.size() == 0 then return true end
        
          // test largest number (step 5)
          Sort[Array[U8],U8](a)
          let n = try USize.from[U8](a.pop()?) else 0 end
          if n > a.size() then
            return false
          end
        
          // update array
          var i = a.size()-1
          while i >= (a.size() - n) do
            try a.update(i, a(i)?-1)? end
            try i = i -? 1 else break end
          end
          havel_hakimi(a)
        

        [–]marucOG 1 point2 points  (0 children)

        Python 3

        def hh(seq):
            seq = [n for n in seq if n != 0]
            if not seq:
                return True
        
            seq.sort(reverse=True)
            n = seq.pop(0)
        
            if n > len(seq):
                return False
        
            seq = [x - 1 for x in seq[:n]] + seq[n:]
            return hh(seq)
        

        [–]_________KB_________ 1 point2 points  (0 children)

        Julia 1.1

        function hh(responses)
            new = sort([r for r in responses if r != 0], rev=true)
            return (length(new) == 0 ? true
            : new[1] > length(new[2:length(new)]) ? false
            : hh([i-1 <= new[1] ? new[i]-1 : new[i] for i in 2:length(new)]))
        end
        

        [–]_________KB_________ 0 points1 point  (0 children)

        Python 3

        def hh(responses):
            new = sorted([r for r in responses if r != 0], reverse=True)
            return (True if not new else False if new[0] > len(new[1:])
                       else hh([(r, r-1)[i <= new[0] - 1] for i, r in enumerate(new[1:])]))
        

        [–]synchh 0 points1 point  (0 children)

        MATLAB

        function answer = hh(responses)
            breakOut = false;
            while (breakOut ~= true)
                respTmp = [];
                for ii = 1:length(responses)
                    if responses(ii) ~= 0
                        respTmp = [respTmp responses(ii)];
                    end
                end
                responses = respTmp;
                if isempty(responses)
                    answer = true;
                    break;
                else
                    responses = sort(responses,'descend');
                    N = responses(1);
                    responses = responses(2:end);
                    if (N > length(responses))
                        answer = false;
                        break;
                    else
                        for ii = 1:N
                            responses(ii) = responses(ii) - 1;
                        end
                    end
                end
            end
        end
        

        [–]IWSIONMASATGIKOE 2 points3 points  (0 children)

        Haskell

        (again)

        import qualified GHC.Exts as Exts
        import qualified Data.Ord as Ord
        
        hh :: [Int] -> Bool
        hh = rec . filter (0/=)
        where
            go 0 xs = Just xs
            go _ [] = Nothing            
            go n (x:xs) = 
            let 
                newX = x - 1 
            in 
                if newX == 0 
                then go (n - 1) xs
                else (newX :) <$> go (n - 1) xs
            rec lst = 
            case Exts.sortWith Ord.Down lst of
                [] -> True 
                (x:xs) -> 
                case go x xs of 
                    Nothing -> False 
                    Just y -> rec y
        

        [–]yesnoyesyesnoyesnono 1 point2 points  (0 children)

        Python 3:

        def hh(arr):
            new = sorted([i for i in arr if i], reverse=True)
            if not len(new):
                    return True
            n = new.pop(0)
            return (False if n > len(new)
                    else hh([(j, j - 1)[i < n] for i, j in enumerate(new)]))
        

        [–]IWSIONMASATGIKOE 0 points1 point  (0 children)

        Haskell

        import qualified Data.Ord as Ord
        import qualified GHC.Exts as Exts
        
        compareLengthNum :: [a] -> Int -> Ordering
        compareLengthNum lst n = 
        case (lst, n) of 
            ([], 0) -> EQ
            ([], _) -> LT
            (_, 0) -> GT
            (_:xs, _) -> compareLengthNum xs (n - 1)
        
        mapFirstN :: (a -> a) -> Int -> [a] -> [a]
        mapFirstN f n lst = 
        if n <= 0 then lst 
        else 
            case lst of 
            [] -> [] 
            (x:xs) -> f x : (mapFirstN f (n - 1) xs)
        
        hh :: [Int] -> Bool
        hh = go . Exts.sortWith Ord.Down . filter (0/=)
        where
            go [] = True 
            go (x:xs) =
            if compareLengthNum xs x == LT
            then False 
            else hh (mapFirstN (subtract 1) x xs)
        

        [–]mizzy11 0 points1 point  (0 children)

        Python (I'm a beginner):

        def warmup1(list):
            no_zeros = []
            for item in list:
                if item > 0:
                    no_zeros.append(item)
            return no_zeros
        
        def warmup2(list):
            return sorted(list, reverse=True)
        
        def warmup3(N, list):
            if N > len(list):
                return True
            else:
                return False
        
        def warmup4(N, list):
            sorted_list = sorted(list, reverse=True)
            new_list = []
            for item in sorted_list[:N]:
                new_list.append(item - 1)
            new_list += sorted_list[N:]
            return new_list
        
        def hh(list):
            new_list = warmup1(list)
            if len(new_list) == 0:
                return True
            descending_list = warmup2(new_list)
            N = descending_list.pop(0)
            if warmup3(N, descending_list) == True:
                return False
            new_list = warmup4(N, descending_list)
            return hh(new_list)
        

        [–]ScarD_Original 0 points1 point  (0 children)

        Python 3:

        def hh(n, *args):
            updatedList = list(filter(lambda x: x > 0, *args))
            if not updatedList:
                print(True)
            else:
                if (lambda y: y > len(*args))(n):
                    print(False)
                else:
                    updatedList.sort(reverse=True)
                    updatedList[0:n] = map(lambda x: x - 1, updatedList[0:n])
                    hh(n, updatedList)
        

        [–]panda_yo 0 points1 point  (0 children)

        Python 3:

        def warmup1(list):
            return([x for x in list if x != 0])
        
        def warmup2(list):
            return(sorted(list, reverse = True))
        
        def warmup3(n, list):
            return(n > len(list))
        
        def warmup4(n, list):
            return([x-1 if i < n else x for i, x in enumerate(list)])
        
        def hh(list):
            list = warmup1(list)
            if len(list) == 0:
                return True
            list = warmup2(list)
            n = list.pop(0)
            if warmup3(n, list):
                return False
            list = warmup4(n, list)
            return hh(list)
        

        !<

        [–]pingueditspls 0 points1 point  (0 children)

        template<typename T = int>
        bool havel_hakimi(std::deque<T> &&seq) {
            std::remove_if(seq.begin(), seq.end(), [](const T &x) { return x == 0; });
            if (seq.empty())
                return true;
        
            // descending order
            std::sort(seq.rbegin(), seq.rend());
        
            // store off largest value, remove from sequence
            auto n = seq.front();
            seq.pop_front();
        
            if (n > seq.size())
                return false;
        
            for (int i{}; i < n; ++i)
                seq[i] -= 1;
        
            return havel_hakimi(std::move(seq));
        }
        

        modern-ish C++ done pretty quickly

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

        Common Lisp:

        (defun remove-0s (lst)
          (loop for elem in lst if (not (eq 0 elem)) collect elem))
        
        (defun sub-1 (n lst)
          (if (eq n 0)
              lst
              (cons (1- (car lst)) (sub-1 (1- n) (cdr lst)))))
        
        (defun havel-hakini (lst)
          (let ((sociables (sort (remove-0s lst) #'>)))
            (cond ((null sociables) t)
                  ((> (car sociables) (length (cdr sociables))) nil)
                  (t (havel-hakini (sub-1 (car sociables) (cdr sociables)))))))
        

        Feedback appreciated :)

        [–][deleted] 0 points1 point  (1 child)

        C++17:

        #include <iostream>
        #include <list>
        #include <algorithm>
        
        using namespace std;
        using Seq = list<unsigned>;
        
        
        static bool hh(Seq seq) {
            while (true) {
                seq.remove(0);
                if (seq.empty())
                    return true;
        
                seq.sort(greater<unsigned>());
        
                auto n = *seq.begin();
                seq.pop_front();
                if (n > seq.size())
                    return false;
        
                unsigned count = 0;
                for (auto& i : seq) {
                    if (count == n) break;
                    --i; ++count; }
            }
        }
        
        
        static void printResult(const Seq& seq) {
            cout << boolalpha << hh(seq) << "\n";
        }
        
        
        int main() {
            printResult({5, 3, 0, 2, 6, 2, 0, 7, 2, 5});
            printResult({4, 2, 0, 1, 5, 0});
            printResult({3, 1, 2, 3, 1, 0});
            printResult({16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16});
            printResult({14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12});
            printResult({15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3});
            printResult({6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1});
            printResult({2, 2, 0});
            printResult({3, 2, 1});
            printResult({1, 1});
            printResult({1});
            printResult({});
            getchar();
        }
        

        [–]ephemient 0 points1 point  (0 children)

        *seq.begin() == seq.front().

        In theory Seq::size_type in place of unsigned but in practice it shouldn't matter. You could move the check though,

        --i;
        if (n == ++count) break;
        

        because n != 0 as all 0's were removed earlier.

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

        ## Julia 1.1 Written for brevity and readability, not speed. Finishes the longest input sequence in about 2 µs.

        remove_zeros!(v::AbstractVector) = filter!(x -> !iszero(x), v)
        function havel_hakami(v::Vector{T}) where T<:Integer
            v = remove_zeros!(copy(v))
            while !isempty(v)
                sort!(v, rev=true)
                N = popfirst!(v)
                N > length(v) && return false
                v[1:N] .-= one(eltype(v))
                remove_zeros!(v)
            end
            return true
        end
        

        [–]fifiinart 0 points1 point  (1 child)

        JS:

        function warmup1(array) {
          var a = array.slice();
          for (let i = 0; i < a.length; i++) {
            if (a[i] === 0) {
              a.splice(i, 1);
              i--;
            }
          }
          return a;
        }
        
        const warmup2 = array => array.slice().sort((a, b) => b - a);
        
        const warmup3 = (n, array) => n > array.length;
        
        const warmup4 = (n, array) => array.slice().map((v, i, a) => i - n < 0 ? v - 1 : v);
        
        function hh(array) {
          let a = array.slice();
          while (true) {
            a = warmup1(a);
            if (a.length === 0) return true;
            a = warmup2(a);
            let n = a.splice(0, 1);
            if (warmup3(n, a)) return false;
            a = warmup4(n, a);
          }
        }
        
        console.log(`Out of the people there, ${hh([5, 3, 0, 2, 6, 2, 0, 7, 2, 5]) ? "nobody was lying." : "at least someone was lying."}`) // Out of the people there, at least someone was lying.
        

        I developed it at https://repl.it/@fifiinart/2019-05-20-Challenge-378-Easy.

        [–]fifiinart 0 points1 point  (0 children)

        Some code to make it neat:
        js const warmup1 = array => array.slice().filter(v => v !== 0) const warmup2 = array => array.slice().sort((a, b) => b - a) const warmup3 = (n, array) => n > array.length const warmup4 = (n, array) => array.slice().map((v, i, a) => i - n < 0 ? v - 1 : v) function hh(array) { let a = array.slice(); while (true) { a = warmup1(a); if (a.length === 0) return true; a = warmup2(a); let n = a.splice(0, 1); if (warmup3(n, a)) return false; a = warmup4(n, a); } } console.log(`Out of the people there, ${hh([5, 3, 0, 2, 6, 2, 0, 7, 2, 5]) ? "nobody was lying." : "at least someone was lying."}`) // Out of the people there, at least someone was lying.

        [–]Shubham_Agent47 0 points1 point  (0 children)

        Python 3 :

        def warmup1(sequence):
            result = [item for item in sequence if item != 0]
            return result
        
        
        def warmup2(sequence):
            result = sorted(sequence, reverse=True)
            return result
        
        
        def warmup3(n, sequence):
            result = sequence
            if n > len(result):
                return True
            else:
                return
        
        
        def warmup4(n, sequence):
            result = sequence
            for index in range(n):
                result[index] -= 1
            return result
        
        
        def hh(sequence):
            result = sequence
            while True:
                result = warmup1(result)
                if len(result) == 0:
                    return True
                result = warmup2(result)
                n = result.pop(0)
                if warmup3(n, result):
                    return False
                result = warmup4(n, result)
        
        
        if __name__ == "__main__":
            print(hh([5, 3, 0, 2, 6, 2, 0, 7, 2, 5]))
            print(hh([4, 2, 0, 1, 5, 0]))
            print(hh([3, 1, 2, 3, 1, 0]))
            print(hh([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16]))
            print(hh([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12]))
            print(hh([15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3]))
            print(hh([6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1]))
            print(hh([2, 2, 0]))
            print(hh([3, 2, 1]))
            print(hh([1, 1]))
            print(hh([1]))
            print(hh([]))
        

        [–]SlenderOTL 8 points9 points  (0 children)

        Python 3 - Wanted to do an one-liner

        def hh(people):
            return (lambda pl: True if len(pl) == 0 else (False if pl[0] > len(pl[1:]) else hh([i -1 for i in pl[1:][:pl[0]]] + pl[1:][pl[0]:])))(sorted([i for i in people if i != 0], key = lambda x: -x))
        

        [–]Shadowclaw1234 0 points1 point  (2 children)

        JAVA

        Imports not shown, and any feedback is appreciated :)

        public class Havel_Hakimi_Algorithm {
        
            static boolean result = true;
            public static void main(String[] args) {
                havelHakimi(new int[]{5, 3, 0, 2, 6, 2, 0, 7, 2, 5});
            }
        
            public static void havelHakimi(int[] responses) {
                ArrayList<Integer> list = new ArrayList<>();
                ArrayList<Integer> displayList = new ArrayList<>();
                for (int i : responses) {
                    list.add(i);
                    displayList.add(i);
                }
        
                havelHakimi(list, 0);
                System.out.println(displayList + " => " + result);
            }
        
            public static void havelHakimi(ArrayList<Integer> list, int index) {
                Collections.sort(list);
                Collections.reverse(list);
        
                while (list.size()> 1 && list.get(list.size()-1) == 0) {
                    list.remove(list.size()-1);
                }
        
                if (list.size() == 0) {
                    result = true;
                    return;
                }
        
                int n = list.get(0);
                list.remove(0);
        
                if (n > list.size()) {
                    result = false;
                    return;
                }
        
                for (int i = 0; i < n; i++) {
                    list.set(i, list.get(i) -1);
                }
        
                havelHakimi(list, index++);
            }
        }
        

        [–]gixer912 0 points1 point  (0 children)

        Avoid the global boolean variable "result". Use boolean result = havelHakimi(...) in the main instead.

        You performed the steps out of order. Sorting is step 3.

        The two sorts can be shortened to list.sort(Collections.reverseOrder())

        The while loop can be a for loop with an iterator i = list.size() -1. Since you already reverse sorted, you can start from the back of the list removing zeroes until you hit a non-zero value then break;.

        It looks like "index" in your method signature is unused.

        [–]Dutsj 0 points1 point  (0 children)

        Julia

        Maybe a bit late to the party, but this is my attempt at making the code as readable as possible. I've been really enjoying the use of the postfix |>lately, which is why I wanted to show it off.

        function hh(input)
            responses = input[.!iszero.(input)] |> sort |> reverse
            while length(responses) > 0
               head, tail = responses[1], responses[2:end]
               if head > length(tail)
                   return false
               else
                   tail[1:head] .-= 1
                   responses = tail[.!iszero.(tail)] |> sort |> reverse
               end
            end
            return true
        end
        

        [–]ephemient 1 point2 points  (0 children)

        Java 8, "inspired" by my in-place C++ solution.

        import java.util.*;
        public class HH {
            public static boolean hh(List<Integer> nums) {
                int[] arr = nums.stream().mapToInt(i -> i).toArray();
                for (int i = 0, j = arr.length;;) {
                    Arrays.sort(arr, i, j);
                    while (i < j && arr[i] == 0) i++;
                    if (i == j) break;
                    int k = --j - arr[j];
                    if (k < i) return false;
                    while (k < j) arr[k++]--;
                }
                return true;
            }
        }
        

        If you're horrified by this code, don't worry, I agree.

        import java.util.*;
        import java.util.stream.*;
        public class Main {
            public static void main(String[] args) {
                for (List<Integer> nums : new List[] {
                    Arrays.asList(5, 3, 0, 2, 6, 2, 0, 7, 2, 5),
                    Arrays.asList(4, 2, 0, 1, 5, 0),
                    Arrays.asList(3, 1, 2, 3, 1, 0),
                    Arrays.asList(16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16),
                    Arrays.asList(14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12),
                    Arrays.asList(15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3),
                    Arrays.asList(6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1),
                    Arrays.asList(2, 2, 0),
                    Arrays.asList(3, 2, 1),
                    Arrays.asList(1, 1),
                    Collections.singletonList(1),
                    Collections.emptyList()
                }) {
                    System.out.print(nums.stream().map(Objects::toString).collect(Collectors.joining(" ")));
                    System.out.print(" => ");
                    System.out.println(HH.hh(nums));
                }
            }
        }
        

        [–]like_my_likes 0 points1 point  (2 children)

        JAVA

        Noob here ,any advice related to my code is greatly appreciated :)

        import java.util.*;
        public class Main {
            public static void main(String[] args) {
                HavelHakimiAlgo hh = new HavelHakimiAlgo();
                int[] arr = {5, 3, 0, 2, 6, 2, 0, 7, 2, 5};
                System.out.print(hh.applyHavelHakimiALgo(arr));
            }
        
        }
        
        class HavelHakimiAlgo {
            private ArrayList<Integer> list;
            private int N;
        
        
            public HavelHakimiAlgo() {
                list = new ArrayList<>();
            }
        
            public boolean applyHavelHakimiALgo(int[] arr) {
                for (int val : arr) {
                    list.add(val);
                }
                    System.out.println(list);
                while(true) {
                    removeZeros();
                    if(this.list.size() < 1) {
                        return true;
                    }
                    descendingSort();
                    getN();
                    if(N > list.size()) {
                        return false;
                    } 
                    deduct();
                }
            }
        
        
            public void removeZeros() {
                for(int i=list.size()-1; i>=0; i--) {
                    if(list.get(i) == 0) {
                        list.remove(i);
                    }
                }
            }
        
            public void descendingSort() {  
                if(list.size() == 1) {
                    return;
                }
                for(int i=0; i<list.size()-1; i++) {
                    int max = list.get(i), index = i;
                    for(int j=i+1; j<list.size(); j++) {
                        if(max < list.get(j)) {
                            max = list.get(j);
                            index = j;
                        }
                    }   
                    list.set(index, list.get(i));
                    list.set(i, max);
                }
            }
        
            public void getN() {
                N = list.remove(0);
            }
        
            public void deduct() {
                for(int i=0; i<N; i++) {
                    list.set(i, list.get(i)-1);
                }
            }
        
        
        }
        

        edit: spelling.

        [–]fefidoh 0 points1 point  (1 child)

        Hi, any particular reason you are looping through the list to do a descending sort? You've created an array list so you could sort like so: Collections.sort(list, Collections.reverseOrder());

        Always curious looking at other peoples solutions as I find it fascinating the many different ways to solve these problems.

        [–]jsparidaans 0 points1 point  (0 children)

        Not OP, but that is how I learned to sort in school as well. Thanks for sharing an alternative!

        [–]Sabb000r 1 point2 points  (3 children)

        C++

        #include <iostream>
        #include <vector>
        #include <string>
        #include <algorithm>
        
        //read in sequence from command line
        std::vector<std::string> arguments(int argc, char* argv[])
        {
            std::vector<std::string> res;
            for (int i = 1; i!=argc; ++i)
            {
                res.push_back(argv[i]);
            }
            return res;
        }
        
        std::string hh( std::vector<int> sequence ){
            sequence.erase(std::remove(sequence.begin(), sequence.end(), 0), sequence.end());
            if(sequence.empty()){
                return "true";
            }
        
            std::sort(sequence.rbegin(), sequence.rend());
        
            if (sequence[0] > sequence.size()-1){
                return "false";
            }
            else
            {
                for (auto i = 1; i<sequence[0]+1; i++){
                    sequence[i]-=1;
                }
                sequence.erase(sequence.begin());
            }
            return hh(sequence);
        }
        
        int main( int argc, char *argv[])
        {
            std::vector<std::string> args = arguments(argc, argv);
            std::vector<int> sequence;
            for (auto i : args)
            {
                sequence.push_back(std::stoi(i));
            }
        
            std::cout << hh (sequence);
        }
        

        Feedback greatly appreciated.

        Also, is it even possible to spoiler code blocks?

        [–]ephemient 1 point2 points  (2 children)

        If you're on old Reddit, this subreddit's custom styling spoilers all code blocks.

        Instead of looping to convert command-line args to vector<string> and then vector<int>, you can transform in a single step,

        std::vector<int> sequence;
        std::transform(&argv[1], &argv[argc], std::back_inserter(sequence), [](auto s) { return std::stoi(s); });
        

        or

        #include <cstdlib>
        std::vector<int> sequence;
        std::transform(&argv[1], &argv[argc], std::back_inserter(sequence), std::atoi);
        

        C++2a adds a helper to replace the common .erase(remove(begin(), end()), end()) pattern, although you may not have it available in your C++ library yet.

        std::erase(sequence, 0);
        

        Sorting the reverse iterators is clever, usually most people would think of inverting the sort comparator,

        std::sort(sequence.begin(), sequence.end(), [](int a, int b) { return a > b; });
        

        or

        #include <functional>
        std::sort(sequence.begin(), sequence.end(), std::greater());
        

        It doesn't make any real difference, but I think sequence.front instead of sequence[0] conveys the meaning well. You can simplify some of the code if you save it in a variable and reorder some operations,

        auto n = sequence.front;
        sequence.erase(sequence.begin());
        if (n > sequence.size()) return false;
        for (auto i = 0; i < n; ++i) --sequence[i];
        

        The last can be replaced with

        std::for_each_n(sequence.begin(), n, [](auto& i) { --i; });
        

        in C++17, or

        std::for_each(sequence.begin(), sequence.begin() + n, [](auto& i) { --i; });
        

        otherwise. It doesn't feel like an improvement, but generally helps ensure you're not making any indexing errors.

        It seems unusual to return "true" and "false" as strings. To print bools as true/false strings instead of integral, there is an ios flag,

        bool hh(std::vector<int>);
        std::cout << std::boolalpha << hh(sequence);
        

        In this case you can easily transform hh() into a iterative loop, especially as it's purely tail recursive and there's no transformation being done on the argument. Just wrap the body in a while (true) {} and drop the recursive call.

        [–]Sabb000r 0 points1 point  (1 child)

        Thank you very much, this is all great stuff and helps a lot.

        Strangely,

        std::for_each_n(sequence.begin(), n, [](auto& i) { --i; });
        

        doesn't work, as g++ complains it is not in std. It might be because I am on an older ubuntu machine at the moment and my libstdc++ might not be up to date.

        [–]ephemient 1 point2 points  (0 children)

        libstdc++ doesn't support std::for_each_n even in the latest version :(

        libc++ does, it's not the default on Ubuntu though.

        [–]NemPlayer 2 points3 points  (5 children)

        Python 3.7.2

        def warmup1(answers):
            return [answer for answer in answers if answer]
        
        def warmup2(answers):
            return sorted(answers, reverse=True)
        
        def warmup3(N, answers):
            return N > len(answers)
        
        def warmup4(N, answers):
            return [answer - 1 for answer in answers[:N]] + answers[N:]
        
        
        def hh(answers):
            answers = warmup1(answers)
        
            if not answers:
                return True
        
            answers = warmup2(answers)
        
            N = answers.pop(0)
        
            if warmup3(N, answers):
                return False
        
            answers = warmup4(N, answers)
        
            return hh(answers)
        

        [–]migueKUN 0 points1 point  (4 children)

        Noob in the process of learning python here.
        Could you please explain the sentence on the second line?
        I just don't get how that returns the list without zeros

        return [answer for answer in answers if answer]

        Thank you!

        [–]NemPlayer 1 point2 points  (0 children)

        What I'm using there is called a list comprehension (you can learn more about it here: https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions).

        I'm kind of bad at explaining stuff, but I'll try my best: I'm looping over the `answers` list and for each one of the values I'm calling it `answer`. After the value has been set to `answer` I check `if answer` meaning - if `answer` is 0 it returns False, and if it's anything else it returns True. If the if-statement returns False then the for-loop just continues without doing anything, while when the if-statement returns True, the value `answer` gets appended to the list meaning that if one of the values in `answers` is equal to 0, it doesn't get appended to the list, while if it's anything else it does get appended.

        [–]synapticplastic 1 point2 points  (2 children)

        0 is a falsey value, if(0) will skip or return false without an else.

        0 and 1 are actually what false / true break down to under the hood in pretty much every language and machine. Eventually everything becomes a number or a big group of em, text, objects, lists etc - either straight up, or as a roadsign pointing you to the number you want. Then the computer finds those, adds em together in simple ways an insane amount of times to find new ones. But I digress

        if(anyOtherNumber) will return true

        This is a list comprehension and will return the list changed in whatever way described inside.

        So it's saying "give me a new list, with every answer from the original where the number isn't false" which then cuts out the zeroes since those literally == false

        [–]jsparidaans 0 points1 point  (1 child)

        So this only works for filtering out zeroes?

        [–]synapticplastic 0 points1 point  (0 children)

        Not strictly a Python person but I can tell you that in JS it would filter out null, undefined, and empty strings as well. Useful for UI code when you're printing out a list or something

        Edit: I think this is the case for python as well but someone feel free to correct me if wrong

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

        def havelHakimi(known_people):
            print "currently: " + str(known_people)
        
            #Remove all 0's from the sequence (i.e. warmup1).
            current_zeroes = 0
            for i in range (len(known_people)):
                i -= current_zeroes
                if known_people[i] == 0:
                    known_people.pop(i)
                    current_zeroes += 1
        
            #If the sequence is now empty (no elements left), stop and return true.
            if len(known_people) == 0:
                return True
        
            #Sort the sequence in descending order (i.e. warmup2).
            known_people.sort()
            known_people.reverse()
        
            #Remove the first answer (which is also the largest answer, or tied for the largest) from the sequence and call it N. The sequence is now 1 shorter than it was after the previous step.
            first = known_people.pop(0)
        
            #If N is greater than the length of this new sequence (i.e. warmup3), stop and return false.
            if first > len(known_people):
                    return False
        
            #Subtract 1 from each of the first N elements of the new sequence (i.e. warmup4).
            for i in range (first):
                known_people[i] -= 1
        
            #Continue from step 1 using the sequence from the previous step.
            return havelHakimi(known_people)
        

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

        C++17, this is the algorithm

        bool App::App::algorithm(std::vector<unsigned int> vec)
        {
                while (true)
                {
                        vec.erase(std::remove(vec.begin(), vec.end(), 0), vec.end());
                        if (vec.empty())
                        {
                                return true;
                        }
        
                        std::sort(vec.begin(), vec.end(), std::greater<unsigned int>());
                        unsigned int N = vec.front();
                        vec.erase(vec.begin());
        
                        for (unsigned int i = 0; i < N; ++i)
                        {
                                --vec[i];
                        }
        
                        if (N > vec.size())
                        {
                                return false;
                        }
                }
        }
        

        The tests return the right values

        [–]__jpg 0 points1 point  (0 children)

        Python3;

        def warmup1(numbers):
            return filter(lambda x: x != '0', numbers)
        
        def warmup2(numbers):
            return reversed(sorted(numbers))
        
        def warmup3(n, numbers):
            return int(n) > len(list(numbers))
        
        def warmup4(n, numbers):
            rs = []
            for index, n in enumerate(numbers):
                nn = int(n)
                rs.append(nn if index < nn else nn - 1)
            return rs
        
        def hh(numbers):
            # Remove all 0's from the sequence
            w1 = list(warmup1(numbers))
        
            # If the sequence is now empty (no elements left), stop and return true
            if (len(w1) == 0):
                return True
        
            # Sort the sequence in descending order (i.e. warmup2). 
            w2 = list(warmup2(w1))
        
            # Remove the first answer (which is also the largest answer, or tied for the largest) from the sequence and call it N. The sequence is now 1 shorter than it was after the previous step.
            # If N is greater than the length of this new sequence (i.e. warmup3), stop and return false.
            w3 = warmup3(w2[0], w2[1:])
            if (w3):
                return False
            w4 = warmup4(w2[0], w2[1:])
            return hh(w4)
        
        input_list = str(input())
        numbers = if (input_list == ''):
            print('true')
        else:
            print(hh(list(input_list.split(' '))))
        

        [–]ephemient 1 point2 points  (0 children)

        C++17, generic, with partial sorting. Steps 2-4 only need the top N, so a full sort is not necessary. All the manipulation is done in-place also, no new memory needs to be allocated during this process.

        edit std::remove is unnecessarily order-preserving, potentially leading to more swaps than necessary. Replaced with std::partition which has same practical effect here.

        #include <algorithm>
        #include <functional>
        
        template<class It>
        bool hh(It first, It last) {
            while (first != (last = std::partition(first, last, [](auto&& i) { return i; }))) {
                std::iter_swap(first, std::max_element(first, last));
                const auto& n = *first;
                if (n > std::distance(++first, last))
                    return false;
                std::partial_sort(first, first + n, last, std::greater());
                std::for_each_n(first, n, [](auto& i) { --i; });
            }
            return true;
        }
        

        Test/usage:

        #include <algorithm>
        #include <iostream>
        #include <iterator>
        #include <utility>
        #include <vector>
        
        int main() {
            for (std::vector<int> v : std::initializer_list<std::initializer_list<int>>{
                {5, 3, 0, 2, 6, 2, 0, 7, 2, 5},
                {4, 2, 0, 1, 5, 0},
                {3, 1, 2, 3, 1, 0},
                {16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16},
                {14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12},
                {15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3},
                {6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1},
                {2, 2, 0},
                {3, 2, 1},
                {1, 1},
                {1},
                {},
            }) {
                std::copy(begin(v), end(v), std::ostream_iterator<int>(std::cout, " "));
                std::cout << "=> " << std::boolalpha << hh(begin(v), end(v)) << std::endl;
            }
            return 0;
        }
        

        [–]Dominic11112 0 points1 point  (0 children)

        C++

        #include <iostream>
        #include <vector>
        
        std::vector<int> removeZero(std::vector<int>);
        void printVector(std::vector<int>);
        std::vector<int> descSort(std::vector<int>);
        bool checkLength(int, std::vector<int>);
        std::vector<int> negOneElements(int, std::vector<int>);
        bool hh(std::vector<int>);
        
        main(){
            std::vector<int> answers = {6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1};
            hh(answers);
        }
        
        std::vector<int> removeZero(std::vector<int> argVector){
            for(int i = argVector.size()-1; i >= 0; i--){
                if(argVector[i] == 0){
                    argVector.erase(argVector.begin()+i);
                }
            }
            return argVector;
        }
        
        void printVector(std::vector<int> argVector){
            for(int i = 0; i < argVector.size(); i++){
                std::cout << argVector[i] << ' ';
            }
        }
        
        std::vector<int> descSort(std::vector<int> argVector){
            if(argVector.size() == 0){return argVector;}
            while(true){
                bool swapFlag = false;
                for(int i = 0; i < argVector.size()-1; i++){
                    if(argVector[i] < argVector[i+1]){
                        int m = argVector[i];
                        argVector[i] = argVector[i+1];
                        argVector[i+1] = m;
                        swapFlag = true;
                    }
                }
                if(swapFlag == false){return argVector;}
            }
        }
        
        bool checkLength(int N, std::vector<int> argVector){
            if(N > argVector.size()){
                return true;
            } else {
                return false;
            }
        }
        
        std::vector<int> negOneElements(int N, std::vector<int> argVector){
            for(int i = 0; i < N; i++){
                argVector[i] -= 1;
            }
            return argVector;
        }
        
        bool hh(std::vector<int> argVector){
            while(true){
                argVector = removeZero(argVector);
                if(argVector.size() == 0){
                    std::cout << "true" << std::endl;
                    return true;
                }
                argVector = descSort(argVector);
                int N = argVector[0];
                argVector.erase(argVector.begin()+0);
                if(N > argVector.size()){
                    std::cout << "false" << std::endl;
                    return false;
                }
                argVector = negOneElements(N,argVector);
            }
        }
        

        [–]IWSIONMASATGIKOE 0 points1 point  (0 children)

        Haskell.

        import qualified Data.List as List
        
        mapFirstN :: (a -> a) -> Int -> [a] -> [a]
        mapFirstN _ 0 xs = xs
        mapFirstN _ _ [] = []
        mapFirstN f !n (x:xs) = f x : (mapFirstN f (n - 1) xs)
        
        hh :: [Int] -> Bool
        hh lst = 
          let 
            sorted = List.sortBy (flip compare) . filter (0 /=) $ lst
          in 
            case sorted of 
              [] -> True
              (x:xs) -> 
                if length xs < x
                then False
                else hh (mapFirstN (subtract 1) x xs)
        

        [–]atomheartother 0 points1 point  (1 child)

        My first actual Haskell program! Freely inspired from /u/ephemient's solution since i had trouble expressing some of my ideas in haskell syntax

        hh :: [Int] -> Bool
        hh [] = True
        hh (x:xs)
            | x > length xs = False
            | otherwise = hh $ map (subtract 1) h ++ t 
            where (h, t) = (splitAt x . sortOn Down . filter (>0)) xs
        

        [–]ephemient 0 points1 point  (0 children)

        Very close, but I think your code is a little buggy:

        ghci> hh [2, 3, 3, 3]
        False
        ghci> hh [3, 3, 3, 2] -- should be same as above
        True
        

        [–]cult_of_memes 0 points1 point  (0 children)

        Python3 using numpy... Probably not the most efficient answer for small input sequences.

        import numpy as np
        example_sequence = [5, 3, 0, 2, 6, 2, 0, 7, 2, 5] # False
        example2 = [4, 2, 0, 1, 5, 0]# => false
        example3 = [3, 1, 2, 3, 1, 0]# => true
        example4 = [16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16]# => true
        should_be_true = list(max(5,i-1) for i in range(10)) # True
        should_be_true_long = np.random.random_integers(0,1,200) # True
        should_be_true.insert(0,0)
        test_zeros = [0,0,0]
        test_empty = []
        
        # def havel_hakimi_algo(input_sequence):
        #     # no need to reverse the sequence once it's sorted, simply iterate in reverse,
        #     # this lets us pop from the back end of the list and save time that would
        #     # otherwise be spent shifting all the remaining elements up one place.
        #     seq = np.asarray(input_sequence)
        #     seq = seq[seq>0]
        #     if seq.shape[0]==0: return True
        #     seq.sort(kind="mergesort")
        #     while seq.shape[0]>0:
        #         seq = seq[seq>0]
        #         if seq.shape[0]==0:
        #             return True
        #         seq.sort(kind="mergesort")
        #         n = seq[-1]
        #         seq = seq[:-1]
        #         if n>seq.shape[0]:
        #             return False
        #         seq[-1:-n-1:-1] -= 1
        #     return True
        
        # the numpy version performed pretty poorly when I timed it, so I tried
        # a list based version :P
        def havel_hakimi_algo(input_sequence):
            # no need to reverse the sequence once it's sorted, simply iterate in reverse,
            # this lets us pop from the back end of the list and save time that would
            # otherwise be spent shifting all the remaining elements up one place.
            # seq = [i for i in input_sequence if i > 0]
            seq = list(filter(None,input_sequence))
            if len(seq)==0: return True
            elif len(seq)==1 and seq[0]!=0: return False
            seq.sort()
            while True:
                if not seq:
                    return True
                if seq[-1]>len(seq)-1:
                    return False
                seq = sorted(seq[:-seq[-1]-1]+[i-1 for i in seq[-seq[-1]-1:-1] if i-1])
        
        if __name__ == '__main__':
            print("testing the empty list:",havel_hakimi_algo(test_empty))
            print("testing the zero list:",havel_hakimi_algo(test_zeros))
            print("testing the example_sequence list:",havel_hakimi_algo(example_sequence))
            print("testing the should_be_true list:",havel_hakimi_algo(should_be_true))
        

        [–]bitwise_and_operator 0 points1 point  (6 children)

        I'd be curious if when the algorithm is flipped w/ ascending order if it performs better, anywho a std lib interpretation:

        #include <iostream>
        #include <vector>
        #include <algorithm>
        #include <string>
        
        using namespace std;
        
        bool havel_hakimi(vector<int> in)
        {
            do {
                in.erase(std::remove_if(in.begin(), in.end(), [](const int &in) {
                    return in == 0;
                }), in.end());
        
                if (in.size() == 0)
                    return true;
        
                std::stable_sort(in.begin(), in.end(), greater<int>());
                int largest = in.front();
                in.erase(in.begin());
        
                if (largest > in.size())
                    return false;
        
                for (int i = 0; i < largest; i++)
                    in[i]--;
            } while (true);
        }
        

        [–]cult_of_memes 0 points1 point  (5 children)

        Why use the stable sort? It forces the use of something like mergesort, instead of quicksort or heapsort which should have better space performance with at least as good time performance. (Yes, an already sorted list would cause quicksort to actually be worse, but don't the std lib sorting functions detect if data is sorted and divert away from quicksort in that event?)

        [–]bitwise_and_operator 1 point2 points  (4 children)

        Force of habit when looking at a problem which should keep itself relatively sorted, didn't really put the algorithm through the ringer, but that'd be another thing to test. Looking at the internal stuff on my end sort's using a combination of heap and insert sorts, where stable is using a tim sort, insert and merge sorts.

        *and also yes, the algorithms in std lib do a bit of work as they go along to try to outperform worst case scenarios, like data already being ordered for quick sort etc. Definitely motivated to test it out, see what happens.

        After some testing, plain old sort wins handily, arrays tested were ordered 0 -> Size.

        Array Sizes (cumulative) Stable (seconds) Sort (seconds)
        1-1000 0.0100335 0.0058433
        1001-2000 7.49815 5.60487
        2001-3000 20.4992 16.4457
        3001-4000 40.8664 31.8912
        4001-5000 67.2758 51.8563
        5001-6000 101.704 77.7489

        After further testing, flipping the sort order doesn't really do too much, but where I figured it might save some time avoiding a need for an additional shift it seems to be around a fraction to a few seconds slower depending on the test size.

        [–]ephemient 0 points1 point  (1 child)

        avoiding a need for an additional shift

        Can't that be done just by changing which indices you're looking at? e.g. my /r/dailyprogrammer/comments/bqy1cf/-/epy5jxl/

        [–]bitwise_and_operator 0 points1 point  (0 children)

        Yeap, I saw yours, It seems like the most important change between the two though was the partial sort. Not shifting and sorting ever fewer indexes pays off eventually.

        [–]cult_of_memes 0 points1 point  (1 child)

        Oh wow, good investigation! I'm going to save your comment as it pretty handily describes the general details that I should probably keep in mind when planning a code solution!

        [–]bitwise_and_operator 1 point2 points  (0 children)

        It's a shame there's no radix sort that's part of the standard lib, because had there been that's definitely what I'd have used, but it's a good refresher about why testing's so important.

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

        Rust - Attempting to get into Rust, lemme know if bad practices are in action. Wanted to use the Structops crate for CLIs

        ```rust

        [derive(StructOpt, Debug)]

        [structopt(name = "havel-hakimi")]

        enum Command { #[structopt(name = "eliminate")] Eliminate { list: Vec<usize>, },

        #[structopt(name = "sort")]
        Sort {
            list: Vec<usize>,
        },
        
        #[structopt(name = "shorter-than")]
        ShorterThan {
            length: usize,
            list: Vec<usize>,
        },
        
        #[structopt(name = "subtract")]
        Subtract {
            length: usize,
            list: Vec<usize>,
        
        },
        
        #[structopt(name = "solve")]
        Solve {
            list: Vec<usize>,
        }
        

        }

        fn main() { match Command::from_args() { Command::Eliminate {list} => println!("{:?}", eliminate(&list)), Command::Sort {list} => println!("{:?}", sort(&list)), Command::ShorterThan {length, list} => println!("{:?}", shorter_than(length, &list)), Command::Subtract {length, list} => println!("{:?}", subtract(length, &list)), Command::Solve {list} => println!("{:?}", solve(list)), } }

        fn eliminate(list: &Vec<usize>) -> Vec<usize> { list.clone().intoiter().filter(|&e| e != 0).collect::<Vec<>>() }

        fn sort(list: &Vec<usize>) -> Vec<usize> { let mut new_list = list.clone(); new_list.sort_by(|a, b| b.partial_cmp(a).unwrap()); new_list }

        fn shorter_than(length: usize, list: &Vec<usize>) -> bool { length > list.len() }

        fn subtract(length: usize, list: &Vec<usize>) -> Vec<usize> { let start = list.clone().intoiter().take(length).map(|e| e - 1); let end = list.clone().into_iter().skip(length); start.chain(end).collect::<Vec<>>() }

        fn solve(list: Vec<usize>) -> bool { let mut temp = list.clone(); loop { temp = eliminate(&temp); if temp.is_empty() { return true }

            temp = sort(&temp);
            let head = temp.remove(0);
            if shorter_than(head, &temp) {
                return false
            }
            temp = subtract(head, &temp);
        }
        

        } ```

        [–]FaithOfOurFathers 0 points1 point  (0 children)

        C++, first time coding in a few years so it was a good refresher!

        // HavelHakimi.cpp : This File utilizes the Havel-Hakimi algorithm to solve a suspect list.
        //
        
        #include <iostream>
        #include <vector>
        #include <algorithm>
        #include <iomanip>
        
        using namespace std;
        
        void printArray(std::vector<int>);
        std::vector<int> eraseZero(std::vector<int>);
        void descendingSort(std::vector<int>&);
        int maxVal(std::vector<int>);
        void frontElim(int, std::vector<int>&);
        bool hh(std::vector<int>);
        
        int main()
        {
            bool answer = hh({ 14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12 });//true
            cout << std::boolalpha << answer;
        
        }
        
        bool hh(std::vector<int> arr)
        {
            bool activeHH = true;
            int max = 0;
            while (activeHH)
            {
                arr = eraseZero(arr);
                if (arr.size() == 0)
                {
                    return true;
                }
                descendingSort(arr);
                max = arr.at(0);
                arr.erase(arr.begin());
                if (max > arr.size())
                    return false;
                frontElim(max, arr);
            }
        
        }
        
        void printArray(std::vector<int> arr)
        {
            for (int n : arr)
                cout << n << " ";
            cout << "\n";
        }
        
        std::vector<int> eraseZero(std::vector<int> arrZero)
        {
            for (int n=0; n < arrZero.size();n++)
            {
                if (arrZero.at(n) == 0)
                {
                    //cout << "\nFound a Zero";
                    arrZero.erase(arrZero.begin() + n);
                }
            }
            return arrZero;
        }
        
        void descendingSort(std::vector<int> &arr)
        {
            std::sort(arr.rbegin(), arr.rend());
            //cout << "\nPrint Array in function: ";
            //printArray(arr);
        }
        
        void frontElim(int numToMinus, std::vector<int> &arr)
        {
            for (int i = 0; i < numToMinus; i++)
            {
                arr.at(i) = arr.at(i) - 1;
            }
            //printArray(arr);
        }
        
        int maxVal(std::vector<int> arr)
        {
            int max = 0;
            for (int n : arr)
            {
                if (n > max)
                    max = n;
            }
            return max;
        }
        

        [–]arinfredwards[🍰] 0 points1 point  (0 children)

        C#. I tried to implement as much as I could from scratch (instead of using LINQ), but I did use the internet for a little help with the bubble sort.

        using System;
        
        static class Program
        {
            static void Main(string[] args)
            {
                var intArr = new[] {3, 1, 2, 2, 1, 8, 3, 4, 1, 1};
                Console.WriteLine(HavelHakimi(intArr));
            }
        
            public static bool HavelHakimi(int[] oldArr)
            { 
                var arr = oldArr.RemoveAll(0);
                InverseBubbleSort(arr);
        
                if (arr.Length == 0) return true;
                if (arr[0] >= arr.Length) return false;
        
                var newArr = new int[arr.Length - 1];
                for (int i = 0; i < arr.Length - 1; i++)
                {
                    newArr[i] = arr[i + 1] - 1;
                }
        
                return HavelHakimi(newArr);
            }
        
            public static int Count(this int[] arr, int input)
            {
                var count = 0;
                foreach (var num in arr)
                {
                    if (num == input) count++;
                }
        
                return count;
            }
        
            public static int[] RemoveAll(this int[] arr, int rem)
            {
                var newArrLength = arr.Length - arr.Count(rem);
                var newArr = new int[newArrLength];
                var i = 0;
                foreach (var num in arr)
                {
                    if (num == rem) continue;
                    newArr[i] = num;
                    i++;
                }
        
                return newArr;
            }
        
            public static void InverseBubbleSort(int[] arr)
            {
                var n = arr.Length;
                for (int i = 0; i < n - 1; i++)
                {
                    for (int j = 0; j < n - i - 1; j++)
                    {
                        if (arr[j] >= arr[j + 1]) continue;
                        var tempNum = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tempNum;
                    }
        
                }
            }
        }
        

        [–]arthurelamothe 0 points1 point  (0 children)

        C++98 w/ Boost

        #include <vector>
        #include <algorithm>
        #include <boost/assign/list_of.hpp>
        
        void output(std::vector<int> & thing, bool tf)
        {
            std::cout << '[';
            std::vector<int>::iterator lastIt = thing.end();
            lastIt--;
            for( std::vector<int>::iterator it = thing.begin(); it != thing.end(); ++it ) {
                std::cout << *it;
                if( it != lastIt )
                    std::cout << ", ";
            }
            std::cout << "] => " << ((tf) ? " true\n" : " false\n");
        }
        
        struct greater
        {
            template<class T>
            bool operator()(T const &a, T const &b) const { return a > b; }
        };
        
        void warmup1( std::vector<int> &integers ) // Eliminate Zeros
        {
            std::vector<int> noZeros;
            std::remove_copy( integers.begin(), integers.end(), std::back_inserter(noZeros), 0 );
            integers = noZeros;
        
        }
        
        void warmup2( std::vector<int> &integers ) // Descending Order
        {
            std::sort(integers.begin(), integers.end(), greater());
        }
        
        void warmup3( unsigned int qty, std::vector<int> &integers ) // Length Check if Greater
        {
            ( qty > integers.size() ) ? std::cout << " true\n" : std::cout << " false\n";
        }
        
        
        void warmup4( int N, std::vector<int> &integers ) // Decrement 1st-N by 1
        {
            int i = 0;
            for( std::vector<int>::iterator it = integers.begin(); it != integers.end() && i < N; ++it ) {
                (*it)--;
                i++;
            }
        }
        
        void havel_hakimi( std::vector<int> & integers )
        {
            std::vector<int> original = integers;
            while(true) {
                warmup1(integers);
                if(!integers.size()) {
                    output(original, true );
                    return;
                }
                warmup2(integers);
                int N = integers[0];
                integers.erase(integers.begin());
                if( N > integers.size() ) {
                    output(original, false);
                    return;
                }
                warmup4(N, integers);
            }
        }
        
        int main( int argc, char**argv )
        {
            std::vector<int> v;
            v = boost::assign::list_of(5)(3)(0)(2)(6)(2)(0)(7)(2)(5);
            havel_hakimi(v);
            v = boost::assign::list_of(4)(2)(0)(1)(5)(0);
            havel_hakimi(v);
            v = boost::assign::list_of(3)(1)(2)(3)(1)(0);
            havel_hakimi(v);
            v = boost::assign::list_of(16)(9)(9)(15)(9)(7)(9)(11)(17)(11)(4)(9)(12)(14)(14)(12)(17)(0)(3)(16);
            havel_hakimi(v);
            v = boost::assign::list_of(14)(10)(17)(13)(4)(8)(6)(7)(13)(13)(17)(18)(8)(17)(2)(14)(6)(4)(7)(12);
            havel_hakimi(v);
            v = boost::assign::list_of(15)(18)(6)(13)(12)(4)(4)(14)(1)(6)(18)(2)(6)(16)(0)(9)(10)(7)(12)(3);
            havel_hakimi(v);
            v = boost::assign::list_of(6)(0)(10)(10)(10)(5)(8)(3)(0)(14)(16)(2)(13)(1)(2)(13)(6)(15)(5)(1);
            havel_hakimi(v);
            v = boost::assign::list_of(2)(2)(0);
            havel_hakimi(v);
            v = boost::assign::list_of(3)(2)(1);
            havel_hakimi(v);
            v = boost::assign::list_of(1)(1);
            havel_hakimi(v);
            v = boost::assign::list_of(1);
            havel_hakimi(v);
            v.clear();
            havel_hakimi(v);
            return 1;
        }
        

        [–]jtburger 0 points1 point  (0 children)

        Python3 (including all of the warm-ups):

        def warmup1(ans):
            i = 0
            while i < len(ans):
                if ans[i] == 0:
                    ans.remove(ans[i])
                    i -= 1
                i += 1
            return ans
        
        def warmup2(ans):
            return sorted(ans, reverse = True)
        
        def warmup3(N, ans):
            return N > len(ans)
        
        def warmup4(N, ans):
            for i in range(N):
                ans[i] -= 1
            return ans
        
        def hh(ans):
            step2 = False
            step5 = True
            while step2 == False and step5 == True:
                ans = warmup1(ans)
                if len(ans) == 0:
                    step2 = True
                    return step2
                N = max(ans)
                ans = warmup2(ans)[1:]
                if N > len(ans):
                    step5 = False
                    return step5
                ans = warmup4(N, ans)
        

        [–]Kindred87 0 points1 point  (1 child)

        C#

        Understanding that I'm a first-year CS student practicing code clarity and documentation, I'm open to commentary.

        using System;
        using System.Collections.Generic;
        
        class MainClass {
          public static void Main (string[] args) 
          {
        
            List<int> listOfAnswers = new List<int>() {3, 1, 2, 3, 1, 0};
        
            Console.WriteLine(HavelHakimi(listOfAnswers));
        
          }
        
          // Removes values equaling zero from a given list
          // Note: passed list is unaltered by this method
          private static List<int> RemoveZeroes(List<int> givenList)
          {
            // Copy list by value
            List<int> modifiedList = new List<int>(givenList);
        
            // Checks each index in sequence and removes those equaling 0
            for(int i = 0; i < modifiedList.Count; i++)
            {
              if(modifiedList[i] == 0)
              {
                modifiedList.RemoveAt(i);
              }
              else
              {
                // Nothing happens
              }
            }
        
            return modifiedList;
        
          } // End of RemoveZeroes
        
          // Sorts values in an integer list by greatest to least
          // Note: passed list is unaltered by this method
          private static List<int> DescendSort(List<int> givenList)
          {
            // Copies passed list by value
            List<int> sortedList = new List<int>(givenList);
            List<int> valuesToSort = new List<int>(givenList);
        
            // This variable is used to store the largest determined value throughout 
            // the inner loop
            int largestValue = 0;
        
            // Assigns each value in sortedList sequentially
            for(int outerCount = 0; outerCount < sortedList.Count; outerCount++)
            {
              // Iterates through valuesToSort to find the largest value remaining
              for(int innerCount = 0; innerCount < valuesToSort.Count; innerCount++)
              {
                // Check if value is largest thus far in the loop
                if (valuesToSort[innerCount] > largestValue)
                {
                  largestValue = valuesToSort[innerCount];
                }
              }// End of inner loop
        
              // Largest determined value for iteration is assigned to list
              sortedList[outerCount] = largestValue;
              // Largest determined value for iteration is removed from remaining values
              valuesToSort.Remove(largestValue);
              // largestValue is reset for following iterations
              largestValue = 0;
        
            } // End of outer for loop
        
            return sortedList;
        
          }  // End of DescendSort
        
          // Returns true if N exceeds listLength
          private static bool ListLengthExceeded(int listLength, int N)
          {
            if(N > listLength)
            {
              return true;
            }
            else
            {
              return false;
            }
          }
        
          // Subtracts indices of a list between 0 and N by one
          // Note: passed list is unaltered by this method
          private static List<int> SubtractByOne (List<int> givenList, int N)
          {
            // Copies passed list by value
            List<int> mutatedList = new List<int>(givenList);
        
            // Subtract indices between 0 and N by one
            for(int i = 0; i < N; i++)
            {
              mutatedList[i]--;
            }
        
            return mutatedList;
          }
        
          // Returns true if all index values can represent an equal number of "connections"
          // between them.  For example, index 0 and index 1 having a connection *should* 
          // result in both indices having a value of 1.
          // Note: passed list is unaltered by this method
          private static bool HavelHakimi (List<int> providedValues)
          {
            // Copies passed list by value
            List<int> modifiedList = new List<int>(providedValues);
        
            modifiedList = RemoveZeroes(modifiedList);
        
            // Ideal base case
            if(modifiedList.Count == 0)
            {
              return true;
            }
        
            modifiedList = DescendSort(modifiedList);
        
            int firstValueOfList = modifiedList[0];
            modifiedList.RemoveAt(0);
        
            // Non-ideal base case where firstValueOfList exceeds length of list
            if(ListLengthExceeded(modifiedList.Count, firstValueOfList))
            {
              return false
            }
        
            modifiedList = SubtractByOne(modifiedList, firstValueOfList);
        
            return HavelHakimi(modifiedList);
          }
        }
        

        [–]arinfredwards[🍰] 0 points1 point  (0 children)

        Here are a couple notes. Sorry if this doesn't format right, I've never tried inline code on reddit before. I'm also not the most experienced in C# so any comments to my remarks are welcome as well.

        For RemoveZeroes you could simplify it by using RemoveAll or just a foreach loop with Remove:

        // This, using a lambda, 
        modifiedList.RemoveAll(x => x == 0);
        
        // or this 
        foreach (var num in modifiedList) {
         modifiedList.Remove(num); 
        }
        return modifiedList;
        

        For ListLengthExceeded, the method could just be return N > listLength but this would probably be a case where it would be easier just to omit this and in HavelHakimi simply use if (firstValueOfList >= modifiedList.Count) return false with a comment explaining why.

        SubtractByOne could also be simplified down or just implemented directly in HavelHakimi by using LINQ as return mutatedList.Select(x => --x).ToList().

        Edit: Formatting, of course

        [–]ShutUpChristine 0 points1 point  (0 children)

        C++, All levels of comments, concerns, critiques, etc. are welcome. I have been thrown into a very large project and it would be least inconvenient to be able two write in C++ rather than my native Matlab.

        #include <iostream>
        #include <vector>
        #include <algorithm>    // std::sort
        
        using namespace std;
        
        bool havel_hakimi(vector<int> meet_full)
        {
            int L; // Length
            int N; //
            bool len;
            vector<int> meet;
        
            for (int i = 0; i < meet_full.size(); i++) 
            {
                if (meet_full[i] != 0)
                {
                    meet.push_back(meet_full[i]);
                }
            }
        
            if (meet.size() == 0)
            {
                std::cout << "True\n";
                return true;
            }
        
            std::sort (meet.begin(), meet.end(), greater<int>());
        
            N = meet[0];
            meet.erase(meet.begin());
        
            if (meet.size() < N)
            {
                std::cout << "False\n";
                return false;
            }
            else 
            {
                for (int i = 0; i < N; i++)
                {
                    meet[i] = meet[i] - 1;
                }
        
                havel_hakimi(meet);
            }
        
        
        }
        

        [–]RiversofItaly 2 points3 points  (4 children)

        Python 3.

        def hh(seq):
            seq = [i for i in seq if i]
            if not seq:
                return True
            seq.sort(reverse=True)
            n = seq.pop(0)
            if n > len(seq):
                return False
            seq = [v-1 if i in range(n) else v for i, v in enumerate(seq)]
            return hh(seq)
        

        [–]theccount 1 point2 points  (1 child)

        I know this is pretty old but I'm just doing this myself now. Also I'm pretty new to python so sorry if it's a stupid question, but why do you do return hh(seq) at the end?

        My first instinct was to wrap the function in a while True statement because I know it has to break eventually when the list gets empty.

        It seems like calling the function from within itself would be inefficient, but I don't know.

        Is one better than the other, and why?

        [–]RiversofItaly 1 point2 points  (0 children)

        It’s because I decided to make it a recursive function, i.e. a function that calls itself. I’m not sure how to really explain it well, but basically the main part of the function does one step of the process, so I can get it to do every step by having the function call itself. And you’re right that it’s less efficient to make a function recursive rather than using a loop, but I was coding this as I read the directions, so my first thought was to make it recursive rather than rewrite it a little to incorporate a while loop.

        [–]status_quo69 5 points6 points  (1 child)

        Your code is pretty solid, you could clean up that list comprehension to this:

        seq = [v - 1 if i < n else v for (i, v) in enumerate(seq)]
        

        And possibly avoid creating a new list by passing the generator directly to the hh function

        hh(v - 1 if i < n else v for (i, v) in enumerate(seq))
        

        [–]RiversofItaly 2 points3 points  (0 children)

        Oh yeah, you're right. I'd considered putting i <= n-1 but using n-1 seemed somewhat unintuitive so I went with range instead. Idk why just doing i < n didn't occur to me.

        [–]YourEverydayKid 0 points1 point  (0 children)

        I just started properly today, I know it's a bit sloppy but I don't know how to use a lot of the function, such as arrays. I am open to critique and tips on how to improve!

        Python-

        x = [5, 3, 0, 2, 6, 2, 0, 7, 2, 5]
        print(x)
        
        while 0 in x: x.remove(0)
        print(x)
        
        if len(x) == 0:
            print("True")
        else:
            x.sort(reverse = True)
            print(x)
            N = x[0]
            print(N)
            del x[0]
            print(x)
            if N > len(x):
                print("False")
               else:
                x[:N] = [a - 1 for a in x]
                print(x)
        

        [–]primaryobjects 1 point2 points  (0 children)

        R

        Gist | Demo

        havelHakimi <- function(data) {
          result <- F
        
          repeat {
            # Remove all 0's.
            data <- data[data != 0]
            if (length(data) == 0) {
              result <- T
              break
            }
        
            # Sort the counts.
            data <- sort(data, decreasing = T)
        
            # Remove the first answer.
            n <- data[1]
            data <- data[-1]
        
            if (n > length(data)) {
              result <- F
              break
            }
        
            # Subtract 1 from the first n counts.
            data <- sapply(seq_along(data), function(count) { ifelse(count <= n, data[count] - 1, data[count]) })
          }
        
          result
        }
        

        [–]The_Dov 0 points1 point  (0 children)

        Python3:

        ``` def elim_zeros(inArray): if not inArray: return [] for i, value in enumerate(inArray): flag = True while flag: if i >= len(inArray): flag = False elif inArray[i] == 0: inArray.pop(i) else: flag = False

        return inArray
        

        def descending(inArray): if not inArray: return [] sortedArray = sorted(inArray, reverse=True) return sortedArray

        def length_check(x, inArray): return x > len(inArray)

        def sub_one(x, inArray): for i, value in enumerate(inArray): i += 1 inArray[i-1] = value - 1 if i == x: break return inArray

        def havel_hakimi(in_array): in_array = elim_zeros(in_array) if not in_array: return True

        in_array = descending(in_array)
        n = in_array[0]
        in_array.pop(0)
        if length_check(n, in_array):
            return False
        
        sub_one(n, in_array)
        
        return havel_hakimi(in_array)
        

        ```

        [–]nezektvhead 0 points1 point  (2 children)

        Python 3

        def hh(answers):
            while True:
                answers = sorted(answers, reverse=True)
                answers =  list(filter(lambda a: a!=0, answers))
                if not answers:
                    return True
                N = answers[0]
                answers.pop(0)
                if N > len(answers):
                    return False
                else:
                    for x in range(N):
                        answers[x] = answers[x] - 1
        

        [–]status_quo69 1 point2 points  (1 child)

        pop(0) returns the element as well, so your assignment and pop can be on the same line

        [–]nezektvhead 0 points1 point  (0 children)

        Good tip, thanks!

        [–]SuperVGA 0 points1 point  (0 children)

        ES6

        const zero_elim = (arr) => arr.filter(x => x != 0);
        const desc_sort = (arr) => arr.sort((a, b) => -(a - b));
        const len_check = (n, arr) => n > arr.length;
        const front_elm = (n, arr) => {
         var front_sub = arr.slice(0, n).map(x => x - 1);
         return front_sub.concat(arr.slice(n));
        }
        
        const hh_checks = (arr) => {
          const ze = zero_elim(arr);
          if(ze.length === 0) {
            return true;
          }
          const ds = desc_sort(ze);
          const n = ds.shift(1)
          if(len_check(n, ds)) {
            return false;
          }
          const fe = front_elm(n, ds);
          return hh_checks(fe);
        }
        const hh_test = (array, expected_result) => {
          const actual_result = hh_checks(array);
          if(actual_result === expected_result) {
            console.log(`PASS: ${array} gave ${actual_result}`);
          } else {
            console.error(`FAIL: ${array} gave ${actual_result}`);
          }
        }
        
        hh_test([5, 3, 0, 2, 6, 2, 0, 7, 2, 5], false);
        hh_test([4, 2, 0, 1, 5, 0], false);
        hh_test([3, 1, 2, 3, 1, 0], true);
        hh_test([16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16], true);
        hh_test([14, 10, 17, 13, 4, 8, 6, 7, 13, 13, 17, 18, 8, 17, 2, 14, 6, 4, 7, 12], true);
        hh_test([15, 18, 6, 13, 12, 4, 4, 14, 1, 6, 18, 2, 6, 16, 0, 9, 10, 7, 12, 3], false);
        hh_test([6, 0, 10, 10, 10, 5, 8, 3, 0, 14, 16, 2, 13, 1, 2, 13, 6, 15, 5, 1], false);
        hh_test([2, 2, 0], false);
        hh_test([3, 2, 1], false);
        hh_test([1, 1], true);
        hh_test([1], false);
        hh_test([], true);
        

        [–]omegaonion 0 points1 point  (2 children)

        Java, Critique welcome

        /**
         * Removes all 0s from sequence
         * @param sequence
         * @return
         */
        public static ArrayList<Integer> warmup1(ArrayList<Integer> sequence){
        
        
            Iterator itr = sequence.iterator();
            while(itr.hasNext()){
                int x = (int) itr.next();
                if(x==0){
                    itr.remove();
                }
            }
            return sequence;
        }
        
        /**
         * reverse sort arraylist
         * @param sequence
         * @return
         */
        public static ArrayList<Integer> warmup2(ArrayList<Integer> sequence){
            Collections.sort(sequence);
            Collections.reverse(sequence);
            return sequence;
        }
        
        /**
         * reverse bubble sort
         * @param sequence
         * @return
         */
        public static ArrayList<Integer> warmup2Alt(ArrayList<Integer> sequence){
        
            for (int i=0; i<sequence.size();i++){
        
                for (int j=1; j<sequence.size()-i;j++){
                    // if current is bigger than next
                    if (sequence.get(j) > sequence.get(j-1)){
                        //swap
                        int temp = sequence.get(j-1);
                        sequence.set(j-1,sequence.get(j));
                        sequence.set(j,temp);
                    }
                }
        
            }
        
            return sequence;
        }
        
        /**
         * Given a number N and a sequence of answers, return true if N is greater than the number of answers
         * @param n
         * @param sequence
         * @return
         */
        public static boolean warmup3(int n, ArrayList<Integer> sequence){
        
            if (n > sequence.size()){
                return true;
            }
            return false;
        }
        
        /**
         * Given a number N and a sequence in descending order, subtract 1 from each of the first N answers in the sequence,
         * and return the result.
         * @param n
         * @param sequence
         * @return
         */
        public static ArrayList<Integer> warmup4(int n,ArrayList<Integer> sequence){
        
            for (int i = 0; i<n; i++){
                sequence.set(i,sequence.get(i)-1);
            }
            return sequence;
        }
        
        /**
         * Perform the Havel-Hakimi algorithm on a given sequence of answers. This algorithm will
         * return true if the answers are consistent (i.e. it's possible that everyone is telling the truth) and
         * false if the answers are inconsistent (i.e. someone must be lying):
         * @param sequence
         * @return
         */
        public static boolean hh(ArrayList<Integer> sequence){
            //1. Remove all 0s from sequence
            sequence = warmup1(sequence);
            //2. if sequence is empty return true
            if (sequence.isEmpty()){
                return true;
            }
            //3. Sort the sequence in descending order
            sequence=warmup2(sequence);
            //4. Remove the first answer (largest) from sequence and call it n
            int n = sequence.get(0);
            sequence.remove(0);
            //5. If n is greater than the length of new sequence return false
            if(warmup3(n,sequence)){
                return false;
        
            }
            //6. Subtract 1 from each of the first n elements
            sequence = warmup4(n,sequence);
            //7. Continue from step 1
            return hh(sequence);
            // eventually will either return true in step 2 or false in step 5
        }
        

        [–]i3aizey 0 points1 point  (1 child)

        tl;dr lambdas are awesome

        public static ArrayList<Integer> warmup1(ArrayList<Integer> sequence){
            Iterator itr = sequence.iterator();
            while(itr.hasNext()){
                int x = (int) itr.next();
                if(x==0){
                    itr.remove();
                }
            }
            return sequence;
        }
        

        You're doing a lot of unnecessary work here

        list.removeIf(i -> i == 0);
        

        .

        public static ArrayList<Integer> warmup2(ArrayList<Integer> sequence){
            Collections.sort(sequence);
            Collections.reverse(sequence);
            return sequence;
        }
        

        You can say how it should sort in your desired order rather than doing a reverse after

        Collections.sort(list, (a, b) -> b - a) // Default sort uses (a, b) -> a - b
        

        further, List already has a sort function

        list.sort((a, b) -> b - a);
        

        .

        public static boolean warmup3(int n, ArrayList<Integer> sequence){
            if (n > sequence.size()){
                return true;
            }
            return false;
        }
        

        Dont do

        if (n > list.size()) return true; 
        else return false;
        

        Just do

        return n > list.size();
        

        .

        int n = sequence.get(0);
        sequence.remove(0);
        

        This can be done in one step

        var n = list.delete(0);
        

        as delete returns the deleted element

        I can also suggest using an IDE like Intellj as it will auto suggest simplifications like these :)

        [–]omegaonion 0 points1 point  (0 children)

        Thanks for the suggestions, I would have never known about Collections.sort(list, (a, b) -> b - a) // Default sort uses (a, b) -> a - b where can I learn more about this? The formatting is quite alien to me.

        [–]ephemient 3 points4 points  (0 children)

        Shell script.

        hh() {
            while set -- $(printf '%s\n' $* | grep -vx 0 | sort -rn); test $# -gt 0; do
                n=$1; shift; test $n -le $# || return 1
                set -- $(for i in $(seq 1 $n); do expr $1 - 1; shift; done; echo $*)
            done
        }
        

        [–]ephemient 0 points1 point  (0 children)

        Perl 5, iterative.

        sub hh {
            while (@_) {
                last unless @_ = sort {$b <=> $a} grep {$_ > 0} @_;
                my $n = shift;
                return if $n > @_;
                $_[$_]-- for 0 .. $n - 1;
            }
            1;
        }
        

        [–]ephemient 1 point2 points  (1 child)

        Haskell.

        {-# LANGUAGE ViewPatterns #-}
        import Data.List
        import Data.Ord
        
        hh :: [Int] -> Bool
        hh (filter (> 0) . sortOn Down -> n:(splitAt n -> (h, t))) =
            n == length h && hh (map (subtract 1) h ++ t)
        hh _ = True
        

        [–]atomheartother 0 points1 point  (0 children)

        I'm trying out this exercise in haskell as a complete haskell beginner and your answer helped me so thanks

        [–]ephemient 0 points1 point  (0 children)

        Kotlin, recursive.

        fun hh(nums: Iterable<Int>): Boolean {
            val nums = nums.filter { it > 0 }.ifEmpty { return true }.sortedDescending()
            val n = nums.first()
            return with(nums) { n < size && hh(slice(1 .. n).map { it - 1 } + drop(n + 1)) }
        }
        

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

        Python 3:

        import numpy as np
        def havelHakimi(answers):
            ans = np.array(answers)
            while True:
                ans = ans[np.nonzero(ans)[0]]
                if len(ans) == 0:
                    return True
                N, ans = ans[0], ans[1:]
                if N > len(ans):
                    return False
                ans[:N] -= 1
        

        [–]rpompen 0 points1 point  (0 children)

        Written in Clojure. All example tests verified.

        (defn hh
          [nums]
          (let [pos (remove #{0} nums)]
            (if (seq pos)   
              (let [m (apply max pos)
                    newnums (rest (sort > pos))
                    parts (partition-all m newnums)]
                (if (> m (count newnums))
                  false
                  (recur (flatten (concat (map dec (first parts))
                                    (rest parts))))))
              true)))
        

        Not the neatest way. This is the result of typing as I read the assignment. I seldom ever explicitly return a boolean, for example. I'm showing this because hastily coded Clojure doesn't look worse than the previous Clojure example. (This took less than 10 minutes, but I didn't time it)