Xah Talk Show 2022-09-16 Coding Challenge, Get the Odd Count. WolframLang vs Python Ruby JavaScript PHP Haskell

Georrg's Coding Challenge 2022-09-15 Get the Odd Count

Create a function f that when given an array of numbers, returns the number that appears an odd amount of times.

Only one number will ever appear an odd number of times, and there will always be one number that appears an odd amount of times.

e.g.
f([4]) //=> 4
f([0]) //=> 0
f([1,1,2,3,3]) //=> 2
f([1,7,1,7,3,7,3]) //=> 7

Try to think of the shortest solution possible in your language.

Put your solutions in threads and I'll judge the winners 🥇🥈🥉 D

WolframLang solution

count number of occur for each and every item, return the item that's odd count.

most intuitive algorithm: build a dict, by go thru the list, for each item, add to the hash. if it already exist, inc value by 1. else, add to hash with value of 1.

another, get all unique items in the list. (because, the most of the time, the unique items will be a small subset of the list). then, you still need to count, the occurrence of each uniq item.

another way, sort the whole list first. advantage being that, when you go thru the list, and when you see a diff number, then you know, the current number no longer occur.

xlist = {1,7,1,7,3,7,3};

(* result of Tally, essentially is the solution *)
Tally[ xlist ] === {{1, 2}, {7, 3}, {3, 2}};

(* first solution *)
getOdd1 = Function[ First@SelectFirst[ Tally@#, ((OddQ[ #[[2]] ]) &) ] ];

(* 2nd solution. pattern matching *)
getOdd2 = (( Cases[Tally[ # ], {_, _?OddQ }, {1}, 1 ][[1, 1]]) &) ;

(* 3rd solution. use transpose to avoid lots of taking parts. *)
getOdd3 = ((Module[{x = Transpose@Tally@#}, First[ x ][[ Position[ x[[2]], _?OddQ, {1}, 1 ][[1, 1]] ]] ]) &) ;

(* 4th solution. faster *)
getOdd4 = ((Module[{x = Transpose@Tally@#}, First@ Extract[ First@ x, Position[ x[[2]], _?OddQ, {1}, 1 ] ] ]) &);

getOdd1[xlist]
getOdd2[xlist]
getOdd3[xlist]
getOdd4[xlist]

code to generate input

xNlengh = 11;
xMaxDistinctSetLength = Ceiling[ xNlengh/2 ]
xValMin = 1;
xValMax = xMaxDistinctSetLength * 2;
xDistinctSet = Table[ RandomInteger[{ xValMin, xValMax }], {xMaxDistinctSetLength} ]

• so, am thinking about this problem of generating valid input to georrg's challenge. gonna type out as i think.
• we want to generate a list. items are positive integers.
• all item should have even number of occurence. except one of them, should be odd.
• so, first of all, the length of this list would be odd.
• so first of all, let's have a nlength. nlength is odd.
• then, what about how many distinct items? that would be, at max, half of the nlength, floor.
• so, if nlen is 5, it'd be 3. eg 2 2 1 3 3.
• ok, so it's the ceiling of the nlen/2.
• because each item must occur at least twice, except the odd one.
• so we got dN = ceiling(nleng/2).
• where dN is distinct number of items.
• now, we need to generate these... and consider how many times to repeat...
• ok, to generate distinct number of items, each would be random, starting with 1, to a max.
• for max, let's just say .... hum, it seems need to depends on dN. .
• shit, more complexity.
• ok, the range of the distinct number (aka an item in the list), should be from 1 to max, where max is some generally smaller than max int of common comp lang. but max needs to be greater than dN.
• ok. jargon getting confusing.
• let's call distinct number as item value. so , iV.
• possible value of iV would be: 1 <= iV <= max .
• where, max is some smallest common greatest int in comp langs.
• and we need dN count of iV.
• ok. that seems easy to do.
• so we get a set of distinct item values, let's call it distinctItemsSet .
• ok. so far, good, but still, the problem isn't half solved.
• we need now to, for each item in distinctItemsSet, ... determine how many times they should repeat.
• and one of them need to repeat odd number of times. we need to determine that number.
• ok, now there's another var. which is, the min or max number of times an item should repeat.
• shiit, much bigger problem than it looks.
• provided we do want some sorta random.
• and efficient way to generate them.

• a much simpler way to gen the list, is just start to push random int, untill we reach some desired length, then, check if any item isn't repeated even times, if found, add that item by insert into random position. do this till only one item is odd number of repeat. if not, fix.
• but this is much less controlled. e.g. we don't have a precise length of the generated list.
• also, this way, most of the items would repeat a minimal number of times, like 2, or 4.
• this means, testing efficiency of a function on this input would be skewed.
• very much.