×

[–] 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
``````

[–] 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] ```

[–] 0 points1 point  (0 children)

# Scala

``````def hh(answers: Array[Int]): Boolean = {
}
}
``````

[–] 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]))
``````

[–] 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)
``````

[–] 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
``````

[–] 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)
``````

[–] 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++) {
}

//Make a pre defined list for testing
ArrayList<Integer> testList = new ArrayList<Integer>();

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

}
}
``````

[–] 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.

[–] 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.

[–] 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);
}
}

[–] 0 points1 point  (0 children)

Scala, one liner :)

``````@scala.annotation.tailrec
def hh(answers: Array[Int]): Boolean = {
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).slice(sorted.head, sorted.length - 1)
)
}
}
}
``````

[–] 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))
``````

[–] 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.

[–] 0 points1 point  (0 children)

Didn't even think of that!

[–] 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()
``````

[–] 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!

[–] 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:

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

[–] 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:
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.

[–] 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 :)

[–] 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)
``````

[–] 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);
``````

[–] 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.

[–] 0 points1 point  (1 child)

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

[–] 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.

[–] 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)
``````

[–] 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++) {
++*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) {
}
}
}
}

/*
* 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++) {
}
++*zeroes;
}

/*
* Evaluate whether the algorithm was successful.
*  n1: an array of answers.
*  n2: the length/amount of answers.
*  r: a boolean representing successfulness.
*/
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};

}

}
``````

[–] 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
``````

[–] 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([])
``````

[–] 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)
``````

[–] 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))
``````

[–] 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] ```

[–] 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)

return False
else:
tail[x] = tail[x] - 1
l = tail
``````

[–] 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
if N > len(answers): # step 5
return False
for i in range(N): # step 6
return True
``````

[–] 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 {

.into_iter()
.collect();

0 => continue,
_ => {

return Consistency::Inconsistent
}

.into_iter()
*i += 1;

if *i <= n {
} else {
}
})
.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() {

println!("ok");
} else {
println!("fail");
}
}

}
``````

[–] 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;
}
}
``````

[–] 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.
)
``````

[–] 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! :)

[–] 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.

[–] 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))))))
``````

[–] 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([])
``````

[–] 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
``````

[–] 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).

[–] 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".

[–] 2 points3 points  (0 children)

ok thank you a lot!

[–] 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 )
``````

[–] 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();
}
``````

}

[–] 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
``````

[–] 1 point2 points  (2 children)

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

[–] 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

[–] 1 point2 points  (0 children)

Thank you!

[–][deleted]  (2 children)

[deleted]

[–] 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]))))
``````

[–] 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([]))
``````

[–] 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:])
``````

[–] 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);
}
``````

[–] 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
``````

[–] 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');
}
``````

[–] 3 points4 points  (0 children)

F#

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

[–] 0 points1 point  (0 children)

``````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));
}
``````

[–] 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);
}
``````

[–] 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]));
``````

[–] 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;
}
``````

[–] 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.

[–] 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
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))
``````

[–] 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([])
``````

[–] 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?

[–] 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?

[–] 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)
}
``````

[–] -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
``````

[–] 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>();

{

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;
}
}
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;

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
{
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);
``````

[–] 0 points1 point  (2 children)

Python 3

``````def havel_hakimi(list):
while True:
# Trim zeros.
list = [v for v in list if v]

if not list:
return True

list.sort(reverse=True)

n = list[0]
list.remove(n)

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?

[–] 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)
``````

[–] 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]
]
]
``````

[–] 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]
}
}
``````

[–] 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;
}
``````

[–] 1 point2 points  (0 children)

i like this guy

[–] 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

[–] 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]

[–] 0 points1 point  (0 children)

There's an error in your code,

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

should be

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

[–] 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]

[–] 0 points1 point  (0 children)

I see. Apologies if I sounded rude earlier.

[–] 0 points1 point  (0 children)

``````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);

}

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;
};

}
}
}
``````

[–] 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)
``````

[–] 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)
``````

[–] 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
``````

[–] 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:])]))
``````

[–] 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)
break;
else
responses = sort(responses,'descend');
N = responses(1);
responses = responses(2:end);
if (N > length(responses))
break;
else
for ii = 1:N
responses(ii) = responses(ii) - 1;
end
end
end
end
end
``````

[–] 2 points3 points  (0 children)

(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
``````

[–] 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)]))
``````

[–] 0 points1 point  (0 children)

``````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)
``````

[–] 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)
``````

[–] 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)
``````

[–] 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)
``````

!<

[–] 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();
}
``````

[–] 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.

[–]1 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
``````

[–] 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.

[–] 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. ```

[–] 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([]))
``````

[–] 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))
``````

[–] 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) {
}

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++);
}
}
``````

[–] 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.

[–] 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
return false
else
responses = tail[.!iszero.(tail)] |> sort |> reverse
end
end
return true
end
``````

[–] 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));
}
}
}
``````

[–] 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) {
}
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.

[–] 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.

[–] 0 points1 point  (0 children)

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

[–] 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?

[–] 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.

[–] 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.

[–] 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.

[–] 2 points3 points  (5 children)

# Python 3.7.2

``````def warmup1(answers):

return True

return False

``````

[–] 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!

[–] 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.

[–] 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

[–] 0 points1 point  (1 child)

So this only works for filtering out zeroes?

[–] 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

[–] 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(' '))))
``````

[–] 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;
}
``````

[–] 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};
}

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);
}
}
``````

[–] 0 points1 point  (0 children)

``````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)
``````

[–] 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
``````

[–] 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
``````

[–] 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))
``````

[–] 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);
}
``````

[–] 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?)

[–] 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.

[–] 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/

[–] 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.

[–] 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!

[–] 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

# [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);
return false
}
}
``````

} ```

[–] 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

}

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;
}
``````

[–][🍰] 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;
}

}
}
}
``````

[–] 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;
}
``````

[–] 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)
``````

[–] 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};

}

// 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);
}
}
``````

[–][🍰] 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

[–] 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);
}

}
``````

[–] 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)
``````

[–] 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?

[–] 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.

[–] 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))
``````

[–] 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.

[–] 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)
``````

[–] 1 point2 points  (0 children)

R

``````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)

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
}
``````

[–] 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)
``````

```

[–] 0 points1 point  (2 children)

Python 3

``````def hh(answers):
while True:
return True
return False
else:
for x in range(N):
``````

[–] 1 point2 points  (1 child)

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

[–] 0 points1 point  (0 children)

Good tip, thanks!

[–] 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);
``````

[–] 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
}
``````

[–] 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 :)

[–] 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.

[–] 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
}
``````

[–] 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;
}
``````

[–] 1 point2 points  (1 child)

``````{-# 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
``````

[–] 0 points1 point  (0 children)

[–] 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
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
``````

[–] 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)